(57)【特許請求の範囲】
【請求項１】
複数の画像を撮影し、各々画像に映った物体あるいは場所をもとに、画像間の対応位置を求めるマッチング処理において、
各々の画像を基準画像として基準以外の画像との対応点候補を探索する対応点候補探索処理と、
該対応点候補から、すべての画像における対応点を決定する対応点決定処理と、
各々画像中の未対応点を対応点として決定する未対応点決定処理を設け、
該未対応点決定処理は、
各々画像の該未対応点の近傍の該対応点を複数用意し、
該複数の対応点から該未対応点を補間し、
さらに補間した点を中心として基準以外の画像の再探索領域を決め、該未対応点を再探索する
ことを特徴とする画像のマッチング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像から地図を作成する分野や、撮影画像をもとに画像を加工処理する分野に関する。
【０００２】
【従来の技術】
本発明に関する複数の画像から対応点を求める画像マッチング技術の従来技術は、高木幹雄、下田陽久監修「画像解析ハンドブック」、707頁から712頁、（東京大学出版会、平成３年１月発行）に記載されているように、テンプレートマッチング（チップマッチングとも言う、以下チップマッチングと記す）が、一般的によく知られている。チップマッチングは、基準の画像から小領域のチップ画像を切り出し、もう一方の画像中に設定した探索領域（サーチエリア）内で類似度（マッチ度）の大きな所を求め、対応点として算出するものである。マッチ度は、小領域での差の絶対値の平均、あるいは相互相関係数を用いて算出する。
【０００３】
チップ画像の切り出しでは、基準となる画像の着目画素I(x,y)を中心としたmxm(mは任意の定数）の領域の画素にて作成する。また、着目画素I(x,y)をx:0〜x軸の最大値、y:0〜y軸の最大値として、順次処理することにより、基準画像の全点に対応するもう一方の画像の対応点を求めることができる。
【０００４】
【発明が解決しようとする課題】
前記従来技術では、基準の画像からチップ画像をとり、もう一方の画像の対応点を求めるマッチングを行っていた。このため、基準の画像を換えると得られる対応点が異なる結果になった。
【０００５】
例として、左視点から撮影した画像（左画像）と右視点から撮影した画像（右画像）との対応点を求めるマッチングを以下に述べる。
【０００６】
左画像を基準としてチップ画像を切り出し、右画像でマッチング度の大きな場所を求めると、仮に、左画像で映っているビルディングの側面が右画像では映ってない場合には、間違った対応点を算出してしまう可能性がある。右画像を基準としたとき、右画像で映っていないビルディングの側面はチップ画像として切り出されることはなく、対応点として算出されることはない。しかし、右画像に映っている場所が左画像では映っていない場合もあり、上記左画像を基準としたときと同様のことが言える。
【０００７】
以上、従来技術のマッチングでは、基準画像を中心に対応点を求めていたため、精度よく対応点を探索することができなかった。
【０００８】
【課題を解決するための手段】
上記課題を解決するために、以下の手段を考案した。
【０００９】
複数の画像を撮影し、各々画像に映った物体あるいは場所をもとに画像間の対応位置を求めるマッチング処理において、各々の画像を基準画像として基準以外の画像との対応点候補を探索する対応点候補探索処理と、対応点候補から、すべての画像における対応点を決定する対応点決定処理を設け、対応点候補探索処理は、各々基準の画像の小領域と基準以外の画像の探索領域を決定し、小領域および探索領域内での類似度の大きな場所を対応点として求め、対応点決定処理は、各々画像の対応点候補を比較し、一致した対応点候補のみを対応点として決定する。
【００１０】
このことにより、精度よく対応点を探索することができる。
【００１１】
【発明の実施の形態】
（実施の形態１）
複数の画像の対応位置を求めるマッチングについて、実施の形態を述べる。マッチング処理の構成を図１に示す。本実施の形態では、２枚の画像を入力とした例を示す。以下、図に従い説明する。
【００１２】
図に示すマッチング処理１００は、左視点の画像Ｌ１１０と右視点の画像Ｒ１２０を入力とし、各々の画像の対応位置を示す対応点１５０を出力する。マッチング処理１００は、対応点候補探索処理１０１および対応点決定処理１０２よりなる。本発明の実施の形態１では、マッチング処理１００を前記２つの処理で構成したことに特徴がある。
【００１３】
以下、マッチング処理１００の詳細を（１．１）および（１．２）にて述べる。
【００１４】
（１．１）対応点候補探索処理１０１
入力した画像をもとに、各々の画像に対する対応点候補を求める。本実施の形態では、画像Ｌ１１０および画像Ｒ１２０を入力としたため、対応点候補探索処理１０１は、画像Ｌを基準としたチップマッチング１０３および画像Ｒを基準としたチップマッチング１０４よりなる。チップマッチングの詳細は以下に示す文献に記載されており、本発明の実施の形態では省略する。
【００１５】
高木幹雄、下田陽久監修「画像解析ハンドブック」、707頁から712頁、（東京大学出版会、平成３年１月発行）
図２に画像Ｌを基準としたチップマッチング１０３および画像Ｒを基準としたチップマッチング１０４の概要を示す。以下、順に説明する。
【００１６】
（１．１．１）画像Ｌを基準としたチップマッチング１０３
図２に示すように、画像Ｌ１１０では、チップ画像２１０を作成する。チップ画像２１０は、着目点を中心としたｍｘｍ（ｍは定数）近傍の切り出し画像となる。
【００１７】
画像Ｒ１２０では、サーチエリア２２０を設定する。サーチエリア２２０は、画像Ｌ１１０の着目点の座標をもとに、画像Ｒ１２０上にｎｘｎ（ｎは定数、ｍ＜ｎ）の領域として設定される。
【００１８】
上記設定したチップ画像２１０およびサーチエリア２２０をもとに、チップ画像に対するサーチエリア内の類似度の大きな場所を算出する。算出した場所を画像Ｌに対する対応点候補１３０とする。
【００１９】
画像Ｌの着目点を順次移動させることで、画像Ｌ上の全画素に対する対応点候補１３０を求める。対応点候補１３０は、図３に示すように座標位置を表す表形式で出力する。
【００２０】
（１．１．２）画像Ｒを基準としたチップマッチング１０４
図２に示すように、画像Ｒ１２０では、チップ画像２３０を作成する。チップ画像２３０は、着目点を中心としたｍｘｍ（ｍは定数）近傍の切り出し画像となる。
【００２１】
画像Ｌ１１０では、サーチエリア２４０を設定する。サーチエリア２４０は、画像Ｒ１２０の着目点の座標をもとに、画像Ｌ１１０上にｎｘｎ（ｎは定数、ｍ＜ｎ）の領域として設定される。
【００２２】
上記設定したチップ画像２３０およびサーチエリア２４０をもとに、チップ画像に対するサーチエリア内の類似度の大きな場所を算出する。算出した場所を画像Ｒに対する対応点候補１４０とする。
【００２３】
画像Ｒの着目点を順次移動させることで、画像Ｒ上の全画素に対する対応点候補１４０を求める。対応点候補１４０は、図３に示すように座標位置を表す表形式で出力する。
【００２４】
（１．２）対応点決定処理１０２
この処理は、画像Ｌに対する対応点候補１３０と画像Ｒに対する対応点候補１４０から、対応点２０３を求める。
【００２５】
図４のフローチャートに基づき、図番号をステップ番号として、手順を以下に説明する。
【００２６】
ステップ４０１：対応点候補の入力
画像Ｌに対する対応点候補１３０および画像Ｒに対する対応点候補１４０を入力する。
【００２７】
ステップ４０２：画像Ｌに対する対応点候補の取り出し
画像Ｌに対する対応点候補１３０から１つの対応点候補を順に取り出す。
【００２８】
ステップ４０３：画像Ｒに対する対応点候補の検索
前記ステップで取り出した対応点候補において画像Ｒの対応点位置ＬR(xr,yr)に着目し、この画像Ｒの対応点位置ＬR(xr,yr)と同一の点を、画像Ｒに対する対応点候補から検索する。
【００２９】
ここで、画像Ｌに対する対応点候補をＬL(xl,yl)およびＬR(xr,yr)、画像Ｒに対する対応点候補をＲR(xr,yr)およびＲL(xl,yl)とおく。
【００３０】
ステップ４０４：検索分岐
画像Ｌに対する対応点候補ＬR(xr,yr)と同一の位置である画像Ｒに対する対応点候補ＲR(xr,yr)が見つかったとき、ステップ４０５を実行する。見つからなかったときは、ステップ４０８へ分岐する。
【００３１】
ステップ４０５：両対応点候補の比較
上記ステップで用いた画像Ｌに対する対応点候補と画像Ｒに対する対応点候補で、ＬL(xl,yl)およびＲL(xl,yl)の座標が一致するか判断する。
【００３２】
ステップ４０６：一致分岐
上記ステップで一致した場合、ステップ４０７を実行する。不一致の場合には、ステップ４０８へ分岐する。
【００３３】
ステップ４０７：対応点の登録
一致した対応点候補を対応点１５０として登録する。
ステップ４０８：ループ終了
対応点候補の全てが処理されるまで、ステップ４０２からステップ４０７を繰り返し実行する。
【００３４】
以上、実施の形態１では、各画像を基準とした対応点候補をあらかじめ探索し、各々画像の対応点候補を比較し、一致した対応点候補のみを対応点として決定する。このことにより、精度よく対応点を探索することができる。
【００３５】
（実施の形態１の変更例）
（変更例１）
本実施の形態１では、２枚の入力画像を用いたが、ｎ枚（ｎは２以上）の画像を入力してもよい。この場合、対応点候補探索処理１０１では、各画像を基準としたマッチングを行い、対応点決定処理１０２では、全画像の座標が一致する対応点１５０のみを選択すればよい。
【００３６】
（変更例２）
対応点候補探索処理１０１では、画像Ｌを基準としたマッチング１０３と画像Ｒを基準としたマッチング１０４を独立に行っていたが、両処理を同期しながら実行することもできる。この場合、（１．１．２）で述べた、チップ画像２３０の着目点は、サーチエリア２２０のマッチング位置とし、サーチエリア２４０は、チップ画像２１０の着目点の座標をもとにした領域とする。
【００３７】
以後、実施の形態１と同様の処理を実行する。
【００３８】
（変更例３）
対応点決定処理１０２では、複数の対応点候補を処理するものであったが、１組の対応点候補を処理することもできる。この場合、ステップ４０５からステップ４０７の手順のみを実行する。
【００３９】
以上の変更例により、実施の形態１と同様の効果が得られる。
【００４０】
（実施の形態２）
実施の形態１の代替案として、未対応点決定処理を伴うマッチング処理の実施の形態を示す。以下、変更点のみを述べる。
【００４１】
図５に実施の形態２の構成を示す。以下、図に従い説明する。
【００４２】
（２．１）マッチング処理１００
マッチング処理１００は、実施の形態１と同様である。画像Ｌ１１０および画像Ｒ１２０を入力し、対応点１５０を出力する。
【００４３】
（２．２）未対応点決定処理５００
図６のデータフローに基づき、図番号をステップ番号として、手順を以下に説明する。
【００４４】
ステップ６０１：画像変換
対応点１５０において、画像Ｌの座標(xl,yl)に基づき、画像Rの座標(xr、yr)の数値を各々データ値として埋め込み、座標データによる欠損画像６１０および６２０として作成する。
【００４５】
ステップ６０２：補間
補間では、上記穴空き画像の欠損データを周囲のデータをもとに復元する。復元の方法は、欠損部分の境界値をもとに距離による加重平均して求める。この方法は、数学的な解釈であるディリクレ問題の解法として一般的に知られている。ディリクレ問題の解法の詳細は以下に示す文献に記載されており、本発明の実施の形態では省略する。
【００４６】
黒田成俊、「関数解析」、83頁から88頁、（共立出版株式会社、１９８５年１０月発行）
このステップにて欠損部分が補間され、対応点画像６３０および６４０として出力する。
【００４７】
ステップ６０３：表変換
上記ステップにて得られた補間画像から新対応点５１０へ変換する。画像Lの座標(xl,yl)の位置のデータ値を画像Ｒの座標(xr,yr)とすることで、新対応点５１０を作成することができる。
【００４８】
以上、実施の形態２では、各画像を基準とした対応点候補をあらかじめ探索し、各々画像の対応点候補を比較し、一致した対応点候補のみを対応点として決定する。未対応点の部分は未対応点決定処理により対応位置を推定する。このことにより、精度よく対応点を探索することができる。
【００４９】
（実施の形態２の変更例）
（変更例１）
未対応点決定処理５００では、ステップ６０２の補間にて欠損部分の未対応点を補間して求めたが、欠損部分の未対応点を再度マッチングすることで、対応点として求めることができる。この場合、未対応点による画像Ｌのチップ画像２１０の着目画素および画像Ｒのチップ画像２３０の着目画素をもとに、サーチエリア２２０およびサーチエリア２４０をｐｘｐ（ｐは定数、ｍ＜ｐ＜ｎ）の領域として設定しマッチングを実行する。
【００５０】
（変更例２）
上記変更例では、サーチエリア２２０およびサーチエリア２４０を、未対応点による画像Ｌのチップ画像２１０の着目画素および画像Ｒのチップ画像２３０の着目画素をもとに設定したが、補間画像をもとに設定することもできる。この場合、補間画像の座標(xl,yl)の位置のデータ値を画像Ｒの着目点(xr, yr)とし、この着目点を中心にｐｘｐ（ｐは定数、ｍ＜ｐ＜ｎ）の領域として設定しマッチングを実行する。
【００５１】
以上の変更例により、実施の形態２と同様の効果が得られる。
【００５２】
【発明の効果】
本発明によれば、以下の効果がある。
【００５３】
複数の画像から各画像を基準とした対応点の候補となる位置を求め、対応点候補から一致した点のみを対応点として決定することにより、確信度の高い対応点のみを決定することができ、また、未対応点を補間あるいは再探索することにより、欠損部分の対応点を求めることができ、対応点探索の精度を向上することができる。
【図面の簡単な説明】
【図１】本実施の形態１のマッチング処理を示す図である。
【図２】本実施の形態１の対応点候補探索処理の概要を示す図である。
【図３】本実施の形態１の対応点を示す図である。
【図４】本実施の形態１の対応点決定処理のフローチャート示す図である。
【図５】本実施の形態２のマッチング処理および未対応点決定処理を示す図である。
【図６】本実施の形態２の未対応点決定処理のデータフローを示す図である。
【符号の説明】
１００…マッチング処理、１０１…対応点候補探索処理、
１０２…対応点決定処理、１０３…画像Ｌを基準としたマッチング、
１０４…画像Ｒを基準としたマッチング、    １１０…画像Ｌ、
１２０…画像Ｒ、        １３０…画像Ｌに対する対応点候補、
１４０…画像Ｒに対する対応点候補、        １５０…対応点、
２１０…画像Ｌのチップ画像、              ２２０…画像Ｒのサーチエリア、
２３０…画像Ｒのチップ画像、              ２４０…画像Ｌのサーチエリア、
３１０…対応点または対応点候補、          ４０１…対応点候補の入力、
４０２…画像Ｌに対する対応点候補の取り出し、
４０３…画像Ｒに対する対応点候補の検索、  ４０４…検索分岐、
４０５…両対応点候補の比較、              ４０６…一致分岐、
４０７…対応点の登録、４０８…ループ終了、５００…未対応点決定処理、
５１０…新対応点、    ６０１…画像変換、  ６０２…補間、
６０３…表変換、      ６１０…欠損画像（データ値xr）、
６２０…欠損画像（データ値yr）、
６３０…補間画像（データ値xr）、
６４０…補間画像（データ値yr）。
【図１】
0003794199.tif 000002
【図２】
0003794199.tif 000003
【図３】
0003794199.tif 000004
【図４】
0003794199.tif 000005
【図５】
0003794199.tif 000006
【図６】
0003794199.tif 000007