(57)【特許請求の範囲】
【請求項１】
複数の画像に対してエッジまたは輪郭線を抽出する抽出処理と、
上記各画像を複数のブロックに分割するとともに、上記各ブロック内に上記エッジまたは輪郭線の交差部分が含まれないようにブロックサイズを可変する分割処理と、
上記分割処理によって分割された複数の画像のうち、一方の画像のブロックと他方の画像のブロックとの類似度に基いて、上記画像間の対応点を決定する対応点決定処理とを行うことを特徴とする対応点マッチング方法。
【請求項２】
複数の画像に対してエッジまたは輪郭線を抽出する抽出手段と、
上記各画像を複数のブロックに分割するとともに、上記各ブロック内に上記エッジまたは輪郭線の交差部分が含まれないようにブロックサイズを可変する分割手段と、
上記分割手段によって分割された複数の画像のうち、一方の画像のブロックと他方の画像のブロックとの類似度に基いて、上記画像間の対応点を決定する対応点決定手段とを具備することを特徴とする対応点マッチング装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は対応点マッチング方法および装置に係わり、例えば、２つの画像間の対応点を抽出することにより、画像から視差または奥行き、あるいは動きベクトルまたは速度を求めるようにする方法および装置に用いて好適なものである。
【０００２】
【従来の技術】
従来、異なる撮像配置（例えば所定の基線長、輻輳角を有する２台のカメラ）、或いは異なる２時点、または異なる撮影位置（１台の単眼カメラを用いた場合）で得られる２つの画像間の対応点を求め、それらの相対位置ベクトル或いは視差に基いて、画像から奥行き（距離）情報を得たり、速度ベクトル（動き）情報を得る手法が数多く提案されている。
【０００３】
その中でも、画像を所定サイズのブロックに分割し、２つの画像のブロック間の相関、或いは輝度差の２乗和などに基いて最も類似度が高い２つのブロックの中心画素を対応点として抽出する手法が良く適用される。
【０００４】
最近、提案された方式の中には、分割ブロックのサイズを初めは大きく取り、次第に小さくすることにより、大まかな対応付けに基いて対応点探索範囲を限定していく方法（Ｑｕａｍ  "Ｈｉｅｒａｒｃｈｉｃａｌ  Ｗａｒｐ  Ｓｔｅｒｅｏ"Ｐｒｏｃ．ｏｆ  ｔｈｅ  ＤＡＲＰＡ  Ｉｍａｇｅ  Ｕｎｄｅｒｓｔａｎｄｉｎｇ  Ｗｏｒｋｓｈｏｐ  ｐｐ．１４９−１５５（１９８４））がある。
【０００５】
また、強度分布などの分散に基いてブロックサイズを適応的に変える相関法（Ｋａｎａｄｅ  ＆  Ｏｋｕｔｏｍｉ  "Ａ  ｓｔｅｒｅｏ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｗｉｔｈ  ａｎ  ａｄａｐｔｉｖｅ  ｗｉｎｄｏｗ：Ｔｈｅｏｒｙ  ａｎｄ  ｅｘｐｅｒｉｍｅｎｔ，Ｐｒｏｃ．  ｏｆ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，ｐｐ．３８３−３８８，（１９９０））などがある。
【０００６】
【発明が解決しようとする課題】
しかしながら、上記従来例では分割されたブロック内の画像にカメラから見て奥行きが変わる部分、または速度ベクトルが不連続に変わる部分が一方の画像には写っているが、他方の画像には写っていない部分が存在するような場合がある。
このような場合には、これらのブロック間の相関等に基いて対応点を推定しても正しい対応点が求まらないという問題点があった。
【０００７】
本発明は上述の問題点にかんがみ、複数の画像間におけるそれぞれの対応点をブロックベースで高精度な対応点抽出を行うことができるようにすることを目的とする。
また、本発明の他の目的は、画像中に不連続部が存在しても、より高精度な対応点抽出を行うことができるようにすることである。
【０００８】
【課題を解決するための手段】
本発明の対応点マッチング方法の特徴とするところは、複数の画像に対してエッジまたは輪郭線を抽出する抽出処理と、上記各画像を複数のブロックに分割するとともに、上記各ブロック内に上記エッジまたは輪郭線の交差部分が含まれないようにブロックサイズを可変する分割処理と、上記分割処理によって分割された複数の画像のうち、一方の画像のブロックと他方の画像のブロックとの類似度に基いて、上記画像間の対応点を決定する対応点決定処理とを行うようにしている。
【００１０】
また、本発明の対応点マッチング装置の特徴とするところは、複数の画像に対してエッジまたは輪郭線を抽出する抽出手段と、上記各画像を複数のブロックに分割するとともに、上記各ブロック内に上記エッジまたは輪郭線の交差部分が含まれないようにブロックサイズを可変する分割手段と、上記分割手段によって分割された複数の画像のうち、一方の画像のブロックと他方の画像のブロックとの類似度に基いて上記画像間の対応点を決定する対応点決定手段とを具備している。
【００１２】
【作用】
本発明は上記技術手段を有するので、エッジまたは輪郭線と交差しないようにしながら、各画素を中心とする複数のブロックに各画像が分割されるとともに、ブロックごとの類似度が検出され、かつ、これらの検出されたブロックごとの類似度から対応点が抽出されるようになるので、不連続部が画像中に存在しても、対応点抽出をブロックベースで行うことが可能となる。
【００１３】
【実施例】
以下、本発明の対応点マッチング方法および装置の一実施例を図面を参照して説明する。
図１は、本発明の対応点マッチング方法の第１の実施例を説明するフローチャート、図５は本実施例の対応点マッチング方法を行う装置の概略構成を示すブロック図である。なお、以下の実施例においては、便宜上、所定の輻輳角と基線長とを有するカメラ配置で撮像して得られる２つの画像間の対応点を抽出する場合について説明する。
【００１４】
図１に示したように、先ず、最初のステップＳ１では、左右カメラ（図５の左カメラ１L 、右カメラ１R ）からの画像を画像メモリ２にそれぞれ入力し、ステップＳ２で各画像のエッジ抽出処理を行う。
【００１５】
エッジ抽出方法としては、所定サイズのカウシアンと画像とのコンボリューションをとった後、ラプラシアン演算により２次微分を行ったデータのゼロクロス点を検出する方法などが適用されるが、本発明においては特定の方式に限定されるものではない。
【００１６】
一般的に、エッジ抽出処理によって不要なエッジ（画像中のノイズ、或いは方式特有の要因による）が生じる。本実施例では、このような不要なエッジを取り除くために、ステップＳ３で不要エッジ除去処理を行っている。この不要エッジ除去処理は、抽出されたエッジの長さが所定値より短い場合には、不要エッジとみなし、除去または無視するようにする処理である。
【００１７】
上記不要エッジ除去処理に関する他の方法としては、エッジ強度（例えば、ローパスフィルタ後の画像の階空間微分の絶対値の和｜∂Ｉ* ／∂ｘ｜＋｜Ｉ* ／∂ｙ｜、Ｉ* はフィルタ後の画像）が所定レベル以下の場合、不要エッジとみなす。なお、上記ステップＳ３の処理は省略してもかまわない。
【００１８】
次に、ステップＳ４では、画像の各画素を中心に一定サイズのブロックに分割する。そして、次のステップＳ５では、複数に分割した各ブロック内にエッジが存在するか否かを判定し、ステップＳ６で交差有りを判断した場合には、ステップＳ７に進み、ブロックの中心画像とエッジとの距離に基いてそのエッジと交差しないようにブロックサイズを縮小し、その後、ステップＳ５に戻る。
【００１９】
ステップＳ６の判断の結果、交差無しと判断した場合には、次に、ステップＳ８に進み、交差無しブロックに分割する処理が完了したか否かを判断し、完了していない場合は、ステップＳ４に戻る。そして、ステップＳ４において、ブロックサイズを所定幅だけ縮小して更にエッジ有無判定を行い、エッジが存在しなくなるまで、その処理過程を繰り返す。このようにして、各画素を中心とする全ブロックについてエッジ交差が存在しないように分割し直す。
【００２０】
そして、交差無しブロックに分割する処理が完了した場合には、ステップＳ９に進み、ブロック相関による対応点抽出を行う。
【００２１】
次に、ブロック間類似度による対応点抽出方法について説明する。本実施例では、前述したブロック分割の結果、画素によってブロックサイズが異なる場合があるが、これに対処するために類似度を計算する２つの画像から抽出された２つのブロックの形状の中心画素を一致させた状態での重なり部分について行う。いま、画素（ｉ，ｊ）を中心とするブロックを「Ｉk i,j 」とする（ｋは画像の番号）と、類似度の尺度としては，
【００２２】
【数１】
0003848294.tif 000002
【００２３】
【数２】
0003848294.tif 000003
【００２４】
【数３】
0003848294.tif 000004
【００２５】
【数４】
0003848294.tif 000005
【００２６】
などが用いられるが、これら以外の尺度を用いても、勿論構わない。但し、Ｃ1 、Ｃ2 、Ｃ3 、Ｃ4 のうち、基本的にはＣ2 、Ｃ4 は相互相関を表し、Ｃ1 、Ｃ3 は２つのブロック間を表す。したがって、対応点を抽出するためにはＣ2 、Ｃ4 については最大値を与えるブロックＩR （ｉ´、ｊ´）が最も良くマッチングする。また、Ｃ1 、Ｃ3 については、最小値を与えるブロックＩR （ｉ´、ｊ´）が左側画像中のブロックＩL （ｉ、ｊ）に最も良くマッチングする。
【００２７】
したがって、このような画素の組み合わせ（（ｉ、ｊ）と（ｉ´、ｊ´））が抽出されるべき対応点となる。
【００２８】
上述したように、図５は立体撮像系において、本実施例の処理部を組み込んだ立体情報抽出系のシステム構成図である。
図５中、１L および１R は左右カメラ、２は画像メモリ、３は図１に示す処理系を含む対応点抽出処理部、４は対応点から視差、或いは距離を求め、適当な補間処理を行って立体形状などを復元する形状復元処理部、５は結果を表示するモニタである。
【００２９】
図６は、本実施例の処理を実際の画像（立方体）に適用した場合のステップＳ３以降のブロック分割過程を示す。図中、Ｌの列は左のカメラで得た画像、Ｒの列は右カメラで得た画像を示している。
【００３０】
図６において、（Ａ）は、図１のフローチャートのステップＳ３における不要エッジ除去処理で不要エッジを除去した後のエッジ画像を示している。
【００３１】
また、（Ｂ）は、図１のフローチャートのステップＳ４の標準ブロック分割で標準サイズのブロックで分割した後の画像を示し、各ブロックの中心はそのブロックの代表点を表している。実際には、同じサイズのブロックを各画素ごとに設定するので、一般的には、ブロック同士は重なり合うが、便宜上、図中では重なり間隙のないように表示している。
【００３２】
さらに、（Ｃ）は、図１のフローチャートのステップＳ５→ステップＳ６→ステップＳ５などの各処理をループで行って得られるエッジ交差なしの分割を、上述した（Ｂ）と同様に示した図である。この場合、ブロックの形状は矩形または三角形（直角三角形）となる。特に、三角形のブロックは立方体の輪郭（エッジ）に沿ったブロック分割を行った結果生じる。一般的には、物体の輪郭の一部を含んだ形状のブロックが生じる。
【００３３】
次に、図２を参照しながら本発明の第２の実施例を説明する。図２は、本発明の第２の実施例の処理手順を示すフローチャートである。なお、図２におけるステップＳ１からステップＳ９までの各ステップは第１実施例と同じである。
【００３４】
しかし、本実施例ではステップＳ１０において、更にエッジに隣接するブロック間での視差或いは動きベクトル推定値、すなわち、対応点間距離の差（偏差）を求めるようにしている。
【００３５】
上記検出した対応点間距離の差（偏差）が基準値よりも大きいか否かを、次のステップＳ１１で判断し、そのエッジは遮蔽輪郭（或いは視差エッジ、速度エッジ）とみなして、これをはさむブロック分割は変更しないようにしている。そして、基準値より大きければステップＳ１２に進み、全対応点を算出したか否かを判断し、全て終了した場合にエンドとなる。
【００３６】
一方、ステップＳ１１の判断の結果、基準値以下であれば、そのエッジはなめらかな物体表面上の模様、照明の分布などによって生じる強度エッジとみなし、ステップＳ３に戻る。この場合には、第１の実施例で説明したようなエッジと交差しないブロック分割は不要であり、エッジ上の画素を含むブロック分割を行って対応点を求めるのが本実施例の特徴である。
なお、ステップＳ１０では、偏差として各点での視差勾配の差、動きベクトル勾配の差を求めるようにしてもよい。
【００３７】
次に、図３を参照しながら本発明の第３の実施例を説明する。図３は本発明の第３の実施例の処理手順を示すフローチャートである。
図３に示したように、この第３の実施例ではエッジ抽出処理（ステップＳ２）および不要エッジ除去（ステップＳ３）を行った後、ステップＳ４においてエッジまたはエッジセグメントベースでの対応点抽出を行う。
【００３８】
ステップＳ４によってエッジ上の点同士での左、右画像中の対応点（対応点の有無も含めて）が求まり、その距離（或いは視差、動きベクトル）がステップＳ５で算出される。
【００３９】
次のステップＳ６では、図２のステップＳ９で求めた距離が基準値より大きいか、対応点が存在しない場合に、そのエッジが画像をブロックに分割する際にブロックと交差したり、中に含まれることを禁止するためのフラグ、或いはラベルを立てる処理を行う。
【００４０】
具体的には、各画素（ｉ，ｊ）ごとにラベルｅ（ｉ，ｊ）を持ち、はじめにｅ（ｉ，ｊ）＝０に初期化しておいて、禁止フラグが立つ画素はｅ（ｉ，ｊ）＝１とする。
【００４１】
ステップＳ６以降の処理は、禁止フラグの立ったエッジと交差しないようにしながらブロック分割する処理（ステップＳ７，ステップＳ８，ステップＳ１０）と、その終了後にブロック間類似度に基づく対応点抽出（ステップＳ１２）が続く。特に、本実施例ではステップＳ８での交差判定は、禁止フラグの値に基いて行われるようにしている。
【００４２】
次に、図４のフローチャートを参照して第４の実施例を説明する。本実施例では、ステップＳ２において各画素を中心に所定サイズでブロック分割する。
次に、ステップＳ３において、上述した第１の実施例と同様に所定の尺度で求めたブロック間の類似度に基づき対応点を推定する。
【００４３】
次に、ステップＳ４に進み、近傍の画素での推定から対応点間距離の勾配（対応点間の画素値の変位の勾配）を算出する。次のステップＳ５では、前のステップＳ４で算出した勾配値が基準範囲外にあるときは２つの画像間でその画素において視差（或いは動きベクトル）が不連続に変化しているものとみなし、不連続ラベル（禁止フラグ）ｅ（ｉ，ｊ）を１にセットする（ｅ（ｉ，ｊ）は０に予め初期化されているものとする）。
【００４４】
次に、ステップＳ６においてブロック内の不連続性を判断し、ブロック内部でｅ（ｉ，ｊ）＝１なる不連続部が所定のサイズ（長さ）以上で存在する場合には不連続部ありと判定して、ステップＳ７に進む。
【００４５】
ステップＳ７では、ブロックサイズを所定の方法で縮小する処理を行い、その後、ステップＳ３に戻って再び対応点推定から不連続性判定での処理を行う。このような処理を繰り返し行う。
【００４６】
次に、ステップＳ８において、全ブロック内部に不連続部が存在するか否かを判断し、存在する場合にはステップＳ２に戻り、上述した処理を繰り返し行い、最終的に対応点を得る。
【００４７】
なお、以上の実施例ではブロックの形状を基本的に縦ｍ画素、横ｎ画素の長方形または正方形とした。しかし、本発明の場合には、必ずしもこれらの形状に限定されるものではなく、不連続部の形状に応じた任意の多角形でもよい。ただし、その場合はブロックの中心（或いは幾何学的重心）はそのブロックを代表する画素であることはいうまでもない。
【００４８】
次に、図７を参照しながら本発明の対応点マッチング装置の一例を説明する。図７において、▲１▼は画像メモリ、▲２▼は分割手段、▲３▼は分割画像記憶手段、▲４▼は推定手段、▲５▼は判定手段、▲６▼は再分割手段、▲７▼は再分割画像記憶手段、▲８▼は対応点決定手段、▲９▼はモニタである。
【００４９】
画像メモリ▲１▼は、外部から入力される映像信号を取り込んで格納しておくためのメモリであり、ここに記憶されている画像が分割手段▲２▼によって所定数に分割される。そして、上記分割手段▲２▼によって分割された画像が、分割画像記憶手段▲３▼に記憶される。
【００５０】
上記分割画像記憶手段▲３▼に記憶された分割画像は、推定手段により複数の画像間の各点の視差または動きベクトルが推定される。この推定は、一方の画像のブロックと他方の画像のブロックとの類似度に基いて行われるものであり、上記複数の画像間の各点の視差または動きベクトルに基づいて行われる。
【００５１】
上記推定手段▲４▼によって得られた推定値は、次段に設けられている判定手段▲５▼に与えられる。判定手段▲５▼は、与えられた推定値の勾配が基準範囲内になるか否かを判定し、その判定結果を再分割手段▲６▼に供給する。
【００５２】
再分割手段▲６▼は、上記分割画像記憶手段▲３▼に記憶されている分割画像を、上記判定手段▲５▼から与えられる判定結果に基いて再分割し、それを再分割画像記憶手段▲７▼に記憶する。
【００５３】
上記再分割画像記憶手段▲７▼に記憶されている再分割画像は、対応点決定手段▲８▼により対応点が決定される。上記決定は、ブロック同士の類似度に基いて行われ、その結果がモニタ▲９▼に表示されるようになされている。
【００５４】
【発明の効果】
本発明は上述したように、エッジまたは輪郭線と交差しないようにしながら、各画像を各画素を中心とする複数のブロックに分割するとともに、ブロックごとの類似度を検出し、上記検出したブロックごとの類似度から対応点を抽出するようにしたので、不連続部が画像中に任意の形、或いは任意の数だけ存在しても、高精度な対応点抽出をブロックベースで行うことができる。
【図面の簡単な説明】
【図１】本発明の第１の実施例の処理手順を示すフローチャートである。
【図２】本発明の第２の実施例の処理手順を示すフローチャートである。
【図３】本発明の第３の実施例の処理手順を示すフローチャートである。
【図４】本発明の第４の実施例の処理手順を示すフローチャートである。
【図５】本発明を適用した立体情報抽出システムの構成図である。
【図６】ブロック分割の過程（始めと終わり）の説明図である。
【図７】本発明の対応点マッチング装置の概略を示す機能構成図である。
【符号の説明】
▲１▼  画像メモリ
▲２▼  分割手段
▲３▼  分割画像記憶手段
▲４▼  推定手段
▲５▼  判定手段
▲６▼  再分割手段
▲７▼  再分割画像記憶手段
▲８▼  対応点決定手段
▲９▼  モニタ
【図１】
0003848294.tif 000006
【図２】
0003848294.tif 000007
【図３】
0003848294.tif 000008
【図４】
0003848294.tif 000009
【図５】
0003848294.tif 000010
【図６】
0003848294.tif 000011
【図７】
0003848294.tif 000012