(57)【要約】【課題】異なる2枚の画像間で特徴点マッチングを行い、かつ、マッチング点の数を増やす。【解決手段】特徴点検出部10は、画像において複数の特徴点を検出する。特徴量生成部20は、特徴点の画素構造を符号化して特徴量を生成する。特徴点マッチング判定部30は、第1の画像の第1の特徴点と、第2の画像の第2の特徴点との特徴量による特徴点マッチングを行い、同一の第1の特徴点とマッチングした複数の第2の特徴点を重複点と判定する。特徴点重複処理部40は、第1の特徴点と重複点との相対座標に基づく第1の移動ベクトル、および、第1の特徴点と重複点以外の第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、第1の移動ベクトルから、第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する。特徴点決定部50は、選択された第1の移動ベクトルに対応する第1の特徴点と第2の特徴点との座標を出力する。【選択図】図１
2015087941.tif 000002
【特許請求の範囲】
【請求項１】
画像において、複数の特徴点を検出する特徴点検出部と、
前記特徴点検出部によって検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成部と、
第1の画像の第1の特徴点と、第2の画像の第2の特徴点との前記特徴量による特徴点マッチングを行い、同一の前記第1の特徴点とマッチングした前記第2の特徴点が複数ある場合、マッチングした複数の前記第2の特徴点を重複点と判定する特徴点マッチング判定部と、
前記第1の特徴点と、当該第1の特徴点とマッチングした前記重複点との相対座標に基づく第1の移動ベクトル、および、前記第1の特徴点と、当該第1の特徴点とマッチングした、前記重複点以外の前記第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、前記第1の移動ベクトルから、前記第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理部と、
前記特徴点重複処理部によって選択された前記第1の移動ベクトルに対応する前記第1の特徴点と前記第2の特徴点との座標を出力する特徴点決定部と、
を有することを特徴とする特徴点マッチング処理装置。
【請求項２】
前記特徴点重複処理部は、同一の前記重複点に対応する複数の前記第1の移動ベクトルと、前記第2の移動ベクトルとを比較し、複数の前記第1の移動ベクトルから、前記第2の移動ベクトルと同一の移動ベクトルを1つ選択することを特徴とする請求項１に記載の特徴点マッチング処理装置。
【請求項３】
前記特徴点重複処理部は、同一の前記重複点に対応する複数の前記第1の移動ベクトルと、前記第1の特徴点とマッチングした、前記重複点以外の複数の前記第2の特徴点に対応する複数の前記第2の移動ベクトルとを比較し、複数の前記第1の移動ベクトルから、最も多くの前記第2の移動ベクトルと一致する移動ベクトルを1つ選択することを特徴とする請求項１に記載の特徴点マッチング処理装置。
【請求項４】
前記特徴点重複処理部は、前記第1の特徴点とマッチングした、前記重複点以外の複数の前記第2の特徴点に対応する複数の前記第2の移動ベクトルの中で最も多い移動ベクトルを第3の移動ベクトルとして選択し、同一の前記重複点に対応する複数の前記第1の移動ベクトルと、前記第3の移動ベクトルとを比較し、複数の前記第1の移動ベクトルから、前記第3の移動ベクトルの方向と最も近い方向を有する移動ベクトルを1つ選択することを特徴とする請求項１に記載の特徴点マッチング処理装置。
【請求項５】
前記特徴点重複処理部は、前記第1の特徴点とマッチングした、前記重複点以外の複数の前記第2の特徴点に対応する複数の前記第2の移動ベクトルの中で最も多い移動ベクトルを第3の移動ベクトルとして選択し、同一の前記重複点に対応する複数の前記第1の移動ベクトルと、前記第3の移動ベクトルとを比較し、複数の前記第1の移動ベクトルから、前記第3の移動ベクトルの方向および長さと最も近い方向および長さを有する移動ベクトルを1つ選択することを特徴とする請求項１に記載の特徴点マッチング処理装置。
【請求項６】
前記特徴点重複処理部は、複数の前記第1の移動ベクトルから、前記第1の移動ベクトルの方向を示す値と前記第3の移動ベクトルの方向を示す値との差が第1の閾値内となる移動ベクトルを1つ選択することを特徴とする請求項４に記載の特徴点マッチング処理装置。
【請求項７】
前記特徴点重複処理部は、複数の前記第1の移動ベクトルから、前記第1の移動ベクトルの方向を示す値と前記第3の移動ベクトルの方向を示す値との差が第1の閾値内であって、かつ、前記第1の移動ベクトルの長さと前記第3の移動ベクトルの長さとの差が第2の閾値内である移動ベクトルを1つ選択することを特徴とする請求項５に記載の特徴点マッチング処理装置。
【請求項８】
画像において、複数の特徴点を検出する特徴点検出ステップと、
前記特徴点検出ステップで検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成ステップと、
第1の画像の第1の特徴点と、第2の画像の第2の特徴点との前記特徴量による特徴点マッチングを行い、同一の前記第1の特徴点とマッチングした前記第2の特徴点が複数ある場合、マッチングした複数の前記第2の特徴点を重複点と判定する特徴点マッチング判定ステップと、
前記第1の特徴点と、当該第1の特徴点とマッチングした前記重複点との相対座標に基づく第1の移動ベクトル、および、前記第1の特徴点と、当該第1の特徴点とマッチングした、前記重複点以外の前記第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、前記第1の移動ベクトルから、前記第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理ステップと、
前記特徴点重複処理ステップで選択された前記第1の移動ベクトルに対応する前記第1の特徴点と前記第2の特徴点との座標を出力する特徴点決定ステップと、
を有することを特徴とする特徴点マッチング処理方法。
【請求項９】
画像において、複数の特徴点を検出する特徴点検出ステップと、
前記特徴点検出ステップで検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成ステップと、
第1の画像の第1の特徴点と、第2の画像の第2の特徴点との前記特徴量による特徴点マッチングを行い、同一の前記第1の特徴点とマッチングした前記第2の特徴点が複数ある場合、マッチングした複数の前記第2の特徴点を重複点と判定する特徴点マッチング判定ステップと、
前記第1の特徴点と、当該第1の特徴点とマッチングした前記重複点との相対座標に基づく第1の移動ベクトル、および、前記第1の特徴点と、当該第1の特徴点とマッチングした、前記重複点以外の前記第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、前記第1の移動ベクトルから、前記第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理ステップと、
前記特徴点重複処理ステップで選択された前記第1の移動ベクトルに対応する前記第1の特徴点と前記第2の特徴点との座標を出力する特徴点決定ステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の特徴点マッチングを行う技術に関する。
【背景技術】
【０００２】
特徴点マッチング情報の検出方法とは、異なる2枚の画像の特徴点を抽出し、特徴点の周辺の局所領域の特徴量を計算したのち、特徴量に基づいて対応点（マッチング点）を探索する方法である。ただし、動体の背景（走行中の車、通行人など）を撮影した場合に動体で隠される背景の領域では正しい特徴点が消失する。あるいは、動体の移動により動体がフレームアウトした場合、正しい特徴点が消失する。
【０００３】
このため、画像間において、各特徴点の特徴量の類似度から対応点を検索できない。さらに、間違ったマッチング点が選択されることにより、重複したマッチング点が存在する。以後、重複したマッチング点を重複点とする。重複点が存在する場合、一般的には重複点が除去される。このため、正しいマッチング点の数が減り、後処理の精度が下がるという問題点がある。
【０００４】
この問題を解決する方法として、特徴点が消失した場合や目的の特徴点の周囲にその特徴点と類似する点が存在する場合でも特徴点が重複しない技術がある。例えば、特許文献1では、時間的に連続した複数枚の画像を使用し、特徴点の移動先の場所を予測する技術が開示されている。この技術では、画像A上の特徴点と、画像B上の特徴点とが対応点の候補である場合、それぞれの特徴点において、またはそれぞれの特徴点の近傍において、2種類の評価基準により、対応付けが行われる。
【０００５】
第1の評価基準は、画像属性の一致度が高いほど、良い対応付けが得られる（対応する特徴点の先鋭度が類似しているほど、良い対応付けが得られる）という基準である。画像属性は、例えば小領域内の分散値や特徴点の周りの微分値の最大値などである。第2の評価基準は、画像Aと画像Bとの特徴点の関係と、画像Bと画像Cとの特徴点の関係とが類似しているほど、良い対応付けが得られる（特徴点の画像上の移動ベクトルが時間的に一定なほど、良い対応付けが得られる）という基準である。
【０００６】
例えば、画像A,B,Cそれぞれの対応する特徴点がa,b,cである場合、第1の評価基準により、特徴点aと特徴点cの先鋭度が類似し、第2の評価基準により、画像A,B,C間で移動ベクトルが時間的に一定であれば、特徴点aと特徴点cとを正しく対応付けることができる。この方法によれば、時間的に連続した画像の途中で、対象となる特徴点が消失している場合や、目的の点の周辺にその点と類似する点が多く含まれる場合でも、最適な特徴点追跡を実現することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−５０８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記の先行技術では、第2の評価基準が示すように、3枚以上の時間的に連続した画像を用いなければ、特徴点の時間的な対応付けを行うことができない。このため、2枚の画像間のみで特徴点の対応付けを行う処理などには対応できないという問題点がある。
【０００９】
本発明は、上述した課題に鑑みてなされたものであって、異なる2枚の画像間で特徴点マッチングを行い、かつ、マッチング点の数を増やすことを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記の課題を解決するためになされたもので、画像において、複数の特徴点を検出する特徴点検出部と、前記特徴点検出部によって検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成部と、第1の画像の第1の特徴点と、第2の画像の第2の特徴点との前記特徴量による特徴点マッチングを行い、同一の前記第1の特徴点とマッチングした前記第2の特徴点が複数ある場合、マッチングした複数の前記第2の特徴点を重複点と判定する特徴点マッチング判定部と、前記第1の特徴点と、当該第1の特徴点とマッチングした前記重複点との相対座標に基づく第1の移動ベクトル、および、前記第1の特徴点と、当該第1の特徴点とマッチングした、前記重複点以外の前記第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、前記第1の移動ベクトルから、前記第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理部と、前記特徴点重複処理部によって選択された前記第1の移動ベクトルに対応する前記第1の特徴点と前記第2の特徴点との座標を出力する特徴点決定部と、を有することを特徴とする特徴点マッチング処理装置である。
【００１１】
また、本発明は、画像において、複数の特徴点を検出する特徴点検出ステップと、前記特徴点検出ステップで検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成ステップと、第1の画像の第1の特徴点と、第2の画像の第2の特徴点との前記特徴量による特徴点マッチングを行い、同一の前記第1の特徴点とマッチングした前記第2の特徴点が複数ある場合、マッチングした複数の前記第2の特徴点を重複点と判定する特徴点マッチング判定ステップと、前記第1の特徴点と、当該第1の特徴点とマッチングした前記重複点との相対座標に基づく第1の移動ベクトル、および、前記第1の特徴点と、当該第1の特徴点とマッチングした、前記重複点以外の前記第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、前記第1の移動ベクトルから、前記第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理ステップと、前記特徴点重複処理ステップで選択された前記第1の移動ベクトルに対応する前記第1の特徴点と前記第2の特徴点との座標を出力する特徴点決定ステップと、を有することを特徴とする特徴点マッチング処理方法である。
【００１２】
また、本発明は、画像において、複数の特徴点を検出する特徴点検出ステップと、前記特徴点検出ステップで検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成ステップと、第1の画像の第1の特徴点と、第2の画像の第2の特徴点との前記特徴量による特徴点マッチングを行い、同一の前記第1の特徴点とマッチングした前記第2の特徴点が複数ある場合、マッチングした複数の前記第2の特徴点を重複点と判定する特徴点マッチング判定ステップと、前記第1の特徴点と、当該第1の特徴点とマッチングした前記重複点との相対座標に基づく第1の移動ベクトル、および、前記第1の特徴点と、当該第1の特徴点とマッチングした、前記重複点以外の前記第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、前記第1の移動ベクトルから、前記第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理ステップと、前記特徴点重複処理ステップで選択された前記第1の移動ベクトルに対応する前記第1の特徴点と前記第2の特徴点との座標を出力する特徴点決定ステップと、をコンピュータに実行させるためのプログラムである。
【発明の効果】
【００１３】
本発明によれば、異なる2枚の画像間で特徴点マッチングを行うことができ、かつ、マッチング点の数を増やすことができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の第1の実施形態による特徴点マッチング処理装置の構成を示すブロック図である。
【図２】本発明の第1の実施形態による特徴点マッチング処理装置の動作の手順を示すフローチャートである。
【図３】本発明の第1の実施形態による特徴点マッチング処理装置が行う処理の過程で生成される情報を示す参考図である。
【図４】本発明の第1の実施形態における重複点の一例を示す参考図である。
【図５】本発明の第2の実施形態による特徴点マッチング処理装置の動作の手順を示すフローチャートである。
【図６】本発明の第2の実施形態による特徴点マッチング処理装置の動作の手順を示すフローチャートである。
【図７】本発明の第2の実施形態における特徴点重複処理の一例を示す参考図である。
【図８】本発明の第2の実施形態における特徴点重複処理の一例を示す参考図である。
【図９】本発明の第2の実施形態における特徴点重複処理の一例を示す参考図である。
【図１０】本発明の第3の実施形態による特徴点マッチング処理装置の動作の手順を示すフローチャートである。
【図１１】本発明の第3の実施形態による特徴点マッチング処理装置の動作の手順を示すフローチャートである。
【図１２】本発明の第3の実施形態において移動ベクトルの角度を判定する処理を示す参考図である。
【図１３】本発明の第3の実施形態における特徴点重複処理の一例を示す参考図である。
【図１４】本発明の第3の実施形態における特徴点重複処理の一例を示す参考図である。
【図１５】本発明の第3の実施形態における特徴点重複処理の一例を示す参考図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照し、本発明の実施形態を説明する。
【００１６】
（第1の実施形態）
まず、本発明の第1の実施形態を説明する。図1は、本実施形態による特徴点マッチング処理装置の構成を示している。図1に示すように、特徴点マッチング処理装置は、特徴点検出部10と、特徴量生成部20と、特徴点マッチング判定部30と、特徴点重複処理部40と、特徴点決定部50とを有する。
【００１７】
特徴点マッチング処理装置には、処理の対象である入力画像信号が外部から入力され、装置内の図示していないメモリに一時記憶される。各ブロックは、適宜、メモリに記憶された入力画像信号を用いて処理を行う。
【００１８】
特徴点検出部10は、入力画像信号が示す画像において、複数の特徴点を検出する。
【００１９】
特徴量生成部20は、特徴点検出部10によって検出された特徴点の画素構造を符号化して特徴量を生成する。
【００２０】
特徴点マッチング判定部30は、第1の画像の第1の特徴点と、第2の画像（第1の画像と異なる画像）の第2の特徴点との特徴量による特徴点マッチングを行い、同一の第1の特徴点とマッチングした第2の特徴点が複数ある場合、マッチングした複数の第2の特徴点を重複点と判定する。
【００２１】
特徴点重複処理部40は、第1の特徴点と、当該第1の特徴点とマッチングした重複点との相対座標に基づく第1の移動ベクトル、および、第1の特徴点と、当該第1の特徴点とマッチングした、重複点以外の第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、第1の移動ベクトルから、第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する。
【００２２】
特徴点決定部50は、特徴点重複処理部40によって選択された第1の移動ベクトルに対応する第1の特徴点と第2の特徴点との座標を、マッチングした特徴点のペアの座標として出力する。また、任意であるが、特徴点決定部50は、第1の特徴点とマッチングした、重複点以外の第2の特徴点と当該第1の特徴点との座標も、マッチングした特徴点のペアの座標として出力する。
【００２３】
本実施形態による特徴点マッチング処理装置を構成する各ブロックの機能は、例えば図示していないROMに記憶されているプログラムを、特徴点マッチング処理装置のコンピュータ（CPU）が読み込んで実行することにより、ソフトウェアの機能として実現してもよい。また、このプログラムは、例えばフラッシュメモリのような「コンピュータ読み取り可能な記録媒体」により提供されてもよい。また、上述したプログラムは、このプログラムを記憶装置等に格納したコンピュータから、伝送媒体を介して、あるいは伝送媒体中の伝送波により特徴点マッチング処理装置に伝送されることで特徴点マッチング処理装置に入力されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように、情報を伝送する機能を有する媒体である。また、上述したプログラムは、前述した機能の一部を実現してもよい。さらに、上述したプログラムは、前述した機能をコンピュータに既に記録されているプログラムとの組合せで実現できる、いわゆる差分ファイル（差分プログラム）であってもよい。
【００２４】
図2は、特徴点マッチング処理装置の動作の手順を示している。ステップS100において、処理が開始される。ステップS101において、特徴点検出部10は、画像において、複数の特徴点を検出し、検出した複数の特徴点の座標を特徴量生成部20に出力する。このとき、特徴点検出部10は、少なくとも2枚の画像のそれぞれにおいて、特徴点を検出する。
【００２５】
ステップS102において、特徴量生成部20は、特徴点検出部10によって検出された特徴点の画素構造を符号化して特徴量を生成し、生成した特徴量と、複数の特徴点の座標とを特徴点マッチング判定部30に出力する。
【００２６】
ステップS103において、特徴点マッチング判定部30は、第1の画像の第1の特徴点と、第2の画像の第2の特徴点との特徴量による特徴点マッチングを行い、同一の第1の特徴点とマッチングした第2の特徴点が複数ある場合、マッチングした複数の第2の特徴点を重複点と判定する。つまり、同一の第1の特徴点とマッチングした第2の特徴点が複数ある場合、それら複数の第2の特徴点が重複点である。また、第1の特徴点とマッチングした第2の特徴点が1つのみである場合、その第2の特徴点は重複点ではない。特徴点マッチング判定部30は、複数の特徴点（第1の特徴点および第2の特徴点）の座標と、第2の特徴点が重複点であるか否かを示す情報とを特徴点重複処理部40に出力する。3枚以上の画像について、特徴点の検出と特徴量の生成とが既に行われている場合、特徴点マッチング判定部30は3枚以上の画像から2枚の画像を適宜選択して、上記の処理を行う。
【００２７】
ステップS104において、特徴点重複処理部40は、第1の特徴点と、当該第1の特徴点とマッチングした重複点との相対座標に基づく第1の移動ベクトル、および、第1の特徴点と、当該第1の特徴点とマッチングした、重複点以外の第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、第1の移動ベクトルから、第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する。例えば、特徴点重複処理部40は、第1の特徴点の座標(x0,y0)と、それとマッチングした第2の特徴点（重複点およびそれ以外の特徴点）の座標(xi,yi)[iは自然数とする]とから移動ベクトル(Δxi,Δyi)を算出する。移動ベクトル(Δxi,Δyi)は、以下の(1)式により算出される。
(Δxi,Δyi) ＝ (xi,yi) - (x0,y0)  ・・・(1)式
【００２８】
さらに、特徴点重複処理部40は、重複点を中心としたサーチエリアを設定し、サーチエリア内において、重複点についての複数の第1の移動ベクトルと、重複点以外の第2の特徴点についての第2の移動ベクトルとを比較する。さらに、特徴点重複処理部40は、重複点についての第1の移動ベクトルの中から、重複点以外の第2の特徴点についての第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択し、選択した移動ベクトルの情報と、複数の座標の情報とを特徴点決定部50に出力する。特徴点重複処理部40は、全ての特徴点について、上記の処理を行う。3枚以上の画像について特徴点の検出と特徴量の生成と特徴点マッチング（および重複点に関する判定）が既に行われている場合、特徴点重複処理部40は3枚以上の画像から2枚の画像を適宜選択して、上記の処理を行う。
【００２９】
ステップS105において、特徴点決定部50は、特徴点重複処理部40によって選択された、重複点に関する第1の移動ベクトルに対応する第1の特徴点と第2の特徴点との座標を、マッチングした特徴点のペアの座標として出力する。また、任意であるが、ステップS105において、特徴点決定部50は、第1の特徴点とマッチングした、重複点以外の第2の特徴点と当該第1の特徴点との座標も、マッチングした特徴点のペアの座標として出力する。したがって、第1の特徴点と第2の特徴点とが1対1に対応したペアの座標が出力される。その後、ステップS106において、処理が終了する。
【００３０】
上記の処理によれば、第1の画像の1つの第1の特徴点に対して、第2の画像の複数の第2の特徴点がマッチングする場合、重複点である複数の第2の特徴点に対応した複数の第1の移動ベクトルが得られる。また、第1の画像の1つの第1の特徴点に対して、第2の画像の1つの第2の特徴点のみがマッチングする場合、重複点ではない1つの第2の特徴点に対応した1つの第2の移動ベクトルが得られる。第1の特徴点と、重複点ではない第2の特徴点とのペアが複数ある場合、それぞれのペアから第2の移動ベクトルが得られる。
【００３１】
本実施形態では、第1の画像における複数の第1の特徴点に対して、第2の画像においてそれぞれ1つずつ第2の特徴点が正確にマッチングする場合、第1の特徴点と第2の特徴点との相対的な位置関係は同一となるという原理に基づいて、正確にマッチングする特徴点のペアが求まる。したがって、重複点に関する複数の第1の移動ベクトルの中で、重複点以外の特徴点に関する第2の移動ベクトルのいずれかと同一の移動ベクトルまたは類似する移動ベクトルに対応する第1の特徴点と第2の特徴点とのペアが、正確にマッチングする特徴点である。
【００３２】
図3は、上記の処理の過程で生成される情報の一例を示している。図3において、A〜Eは、特徴点を識別するために便宜上付与される識別情報である。(x0,y0)は、第1の画像における第1の特徴点の座標である。(x1,y1)〜(xn,yn)は、第2の画像において、特徴点マッチング判定部30の処理により第1の特徴点とマッチングした第2の特徴点（マッチング点）の座標である。特徴点A,C,Dに関しては、第1の特徴点の座標(x0,y0)に対して、1つの第2の特徴点の座標(x1,y1)のみがマッチングしている。一方、特徴点B,Eに関しては、第1の特徴点の座標(x0,y0)に対して、2つの第2の特徴点の座標(x1,y1)、(x2,y2)がマッチングしている。つまり、重複点が存在する。
【００３３】
図3において、(Δx1,Δy1)は、第1の特徴点の座標(x0,y0)に対する第2の特徴点の座標(x1,y1)の移動ベクトルである。移動ベクトル(Δx1,Δy1)は、(1)式においてi=1の場合に算出される。(Δx2,Δy2)は、第1の特徴点の座標(x0,y0)に対する第2の特徴点の座標(x2,y2)の移動ベクトルである。移動ベクトル(Δx2,Δy2)は、(1)式においてi=2の場合に算出される。(Δxn,Δyn)は、第1の特徴点の座標(x0,y0)に対する第2の特徴点の座標(xn,yn)の移動ベクトルである。移動ベクトル(Δxn,Δyn)は、(1)式においてi=nの場合に算出される。
【００３４】
図3において、重複点フラグは、第2の特徴点が重複点であるか否かを示す情報である。特徴点A,C,Dに関しては、第1の特徴点の座標(x0,y0)に対して、1つの第2の特徴点の座標(x1,y1)のみがマッチングしているため、第2の特徴点は重複点ではない。一方、特徴点B,Eに関しては、第1の特徴点の座標(x0,y0)に対して、2つの第2の特徴点の座標(x1,y1)、(x2,y2)がマッチングしているため、第2の特徴点は重複点である。
【００３５】
例えば、図2に示す処理において、図3に示す情報の生成および更新が行われる。図3に示す情報は、特徴点マッチング処理装置内の図示していないメモリに記憶されてもよい。
【００３６】
図4は、重複点の一例を示している。画像400は第1の画像である。画像401は、画像401とは異なる時刻に撮影された第2の画像である。第1の画像と第2の画像とのどちらが先に撮影されても構わない。画像400において、特徴点B,Cに関する第1の特徴点の座標(x0,y0)が示されている。また、画像401において、特徴点Bに関する第2の特徴点の座標(x1,y1)、(x2,y2)と、特徴点Cに関する第2の特徴点の座標(x1,y1)とが示されている。
【００３７】
図4では、特徴点Bに関して、1つの第1の特徴点の座標(x0,y0)に対して2つの第2の特徴点の座標(x1,y1)、(x2,y2)がマッチングしている。このため、特徴点Bに関する第2の特徴点の座標(x1,y1)、(x2,y2)は重複点である。図3に示すように、特徴点Bに関して、移動ベクトル(Δx1,Δy1)、(Δx2,Δy2)のうち、移動ベクトル(Δx1,Δy1)が、特徴点A,C,Dに関する移動ベクトル(Δx1,Δy1)と同一である。このため、特徴点Bに関して、第2の特徴点の座標(x1,y1)が、第1の特徴点の座標(x0,y0)と正確にマッチングするマッチング点の座標として得られる。同様に、特徴点Eに関して、第2の特徴点の座標(x1,y1)が、第1の特徴点の座標(x0,y0)と正確にマッチングするマッチング点の座標として得られる。
【００３８】
本実施形態によれば、画像において、複数の特徴点を検出する特徴点検出部10と、特徴点検出部10によって検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成部20と、第1の画像の第1の特徴点と、第2の画像の第2の特徴点との特徴量による特徴点マッチングを行い、同一の第1の特徴点とマッチングした第2の特徴点が複数ある場合、マッチングした複数の第2の特徴点を重複点と判定する特徴点マッチング判定部30と、第1の特徴点と、当該第1の特徴点とマッチングした重複点との相対座標に基づく第1の移動ベクトル、および、第1の特徴点と、当該第1の特徴点とマッチングした、重複点以外の第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、第1の移動ベクトルから、第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理部40と、特徴点重複処理部40によって選択された第1の移動ベクトルに対応する第1の特徴点と第2の特徴点との座標を出力する特徴点決定部50と、を有することを特徴とする特徴点マッチング処理装置が構成される。
【００３９】
また、本実施形態によれば、画像において、複数の特徴点を検出する特徴点検出ステップ（S101）と、特徴点検出ステップで検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成ステップ（S102）と、第1の画像の第1の特徴点と、第2の画像の第2の特徴点との特徴量による特徴点マッチングを行い、同一の第1の特徴点とマッチングした第2の特徴点が複数ある場合、マッチングした複数の第2の特徴点を重複点と判定する特徴点マッチング判定ステップ（S103）と、第1の特徴点と、当該第1の特徴点とマッチングした重複点との相対座標に基づく第1の移動ベクトル、および、第1の特徴点と、当該第1の特徴点とマッチングした、重複点以外の第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、第1の移動ベクトルから、第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理ステップ（S104）と、特徴点重複処理ステップで選択された第1の移動ベクトルに対応する第1の特徴点と第2の特徴点との座標を出力する特徴点決定ステップ（S105）と、を有することを特徴とする特徴点マッチング処理方法が構成される。
【００４０】
また、本実施形態によれば、画像において、複数の特徴点を検出する特徴点検出ステップ（S101）と、特徴点検出ステップで検出された特徴点の画素構造を符号化して特徴量を生成する特徴量生成ステップ（S102）と、第1の画像の第1の特徴点と、第2の画像の第2の特徴点との特徴量による特徴点マッチングを行い、同一の第1の特徴点とマッチングした第2の特徴点が複数ある場合、マッチングした複数の第2の特徴点を重複点と判定する特徴点マッチング判定ステップ（S103）と、第1の特徴点と、当該第1の特徴点とマッチングした重複点との相対座標に基づく第1の移動ベクトル、および、第1の特徴点と、当該第1の特徴点とマッチングした、重複点以外の第2の特徴点との相対座標に基づく第2の移動ベクトルを比較し、第1の移動ベクトルから、第2の移動ベクトルと同一の移動ベクトルまたは類似する移動ベクトルを1つ選択する特徴点重複処理ステップ（S104）と、特徴点重複処理ステップで選択された第1の移動ベクトルに対応する第1の特徴点と第2の特徴点との座標を出力する特徴点決定ステップ（S105）と、をコンピュータに実行させるためのプログラムが構成される。
【００４１】
本実施形態では、異なる2枚の画像を用いて、移動ベクトルの比較により、正確なマッチング点を求めることが可能となる。また、重複点が発生しても、特徴点マッチングの失敗を低減し、正確な特徴点を排除せずにマッチング点として残すことが可能となる。したがって、異なる2枚の画像間で特徴点マッチングを行うことができ、かつ、マッチング点の数を増やすことができる。異なる2枚の画像は、時間的に連続する画像でなくても構わない。
【００４２】
（第2の実施形態）
次に、本発明の第2の実施形態を説明する。本実施形態による特徴点マッチング処理装置の構成は、図1に示す特徴点マッチング処理装置の構成と同一であるので、構成についての説明を省略する。
【００４３】
本実施形態では、重複点を基準とする所定のサーチエリア内において、重複点の複数の第1の移動ベクトルのうち、重複点以外の第2の特徴点の第2の移動ベクトルと一致する移動ベクトルが選択される。具体的には、特徴点重複処理部40は、同一の重複点に対応する複数の第1の移動ベクトルと、第2の移動ベクトル（重複点以外の第2の特徴点の移動ベクトル）とを比較し、複数の第1の移動ベクトルから、第2の移動ベクトルと同一の移動ベクトルを1つ選択する。例えば、特徴点重複処理部40は、同一の重複点に対応する複数の第1の移動ベクトルと、第1の特徴点とマッチングした、重複点以外の複数の第2の特徴点に対応する複数の第2の移動ベクトルとを比較し、複数の第1の移動ベクトルから、最も多くの第2の移動ベクトルと一致する移動ベクトルを1つ選択する。
【００４４】
本実施形態による特徴点マッチング処理装置の動作は、図2における特徴点重複処理（ステップS104）を除いて、図2に示される動作と同一である。以下では、特徴点重複処理（ステップS104）についてのみ説明する。
【００４５】
図5および図6は、本実施形態における特徴点重複処理（ステップS104）の詳細を示している。図5および図6に示す処理は、図3における1行分の情報に対する処理に相当する。図5および図6に示す処理を繰り返すことで、2枚の画像から検出された全ての特徴点に対して処理を行うことが可能となる。また、第1の画像と第2の画像との少なくとも一方を変更して処理を繰り返すことで、3枚以上の画像から任意に選択した2枚の画像のそれぞれの組合せについて、特徴点重複処理を行うことができる。
【００４６】
ステップS200において、処理が開始される。ステップS201において、特徴点重複処理部40は、特徴点マッチング判定部30の処理によってマッチングした特徴点の全ての座標(x0,y0)、(x1,y1)、(x2,y2)、・・・を特徴点マッチング判定部30から取得する。
【００４７】
ステップS202において、特徴点重複処理部40は、第1の画像における第1の特徴点の座標(x0,y0)を基準とする移動ベクトルを、(1)式により算出する。ステップS203において、特徴点重複処理部40は、ステップS202で算出された移動ベクトルを図示していないメモリ等に一時保存する。
【００４８】
ステップS204において、特徴点重複処理部40は、第2の画像における第2の特徴点のうち、注目する重複点Prを選択する。ステップS205において、特徴点重複処理部40は、第2の画像において、注目する重複点Prを中心としたサーチエリアを設定する。ステップS206において、特徴点重複処理部40は、サーチエリア内の第2の特徴点である特徴点Ptx（重複点Prを除く）の第2の移動ベクトルである移動ベクトルVtx（Vt1,Vt2,Vt3,・・・）と、特徴点Ptx（Pt1,Pt2,Pt3,・・・）の重複点フラグとを特徴点マッチング判定部30から取得する。
【００４９】
特徴点Ptxが重複点である場合、その特徴点Ptxには複数の移動ベクトルVtxが対応している。特徴点Ptxが重複点ではない場合、その特徴点Ptxには1つだけの移動ベクトルVtxが対応している。
【００５０】
ステップS207において、特徴点重複処理部40は、重複点フラグに基づいて、特徴点Ptxが重複点であるか否かを判定する。特徴点Ptxが重複点であることを重複点フラグが示している場合、ステップS208において、特徴点重複処理部40は特徴点Ptxを無視する。すなわち、特徴点Ptxとして重複点が選択されている場合、特徴点Ptxに関する処理がスキップされる。続いて、サーチエリア内の第2の特徴点の中から、特徴点Ptxとして既に選択された特徴点を除く第2の特徴点が特徴点Ptxとして選択され、ステップS206の処理が行われる。
【００５１】
特徴点Ptxが重複点ではないことを重複点フラグが示している場合、ステップS209において、特徴点重複処理部40は、重複点Prの第1の移動ベクトルである移動ベクトルVry（Vra,Vrb,Vrc,・・・）の全てと、特徴点Ptxの移動ベクトルVtxとを比較する。移動ベクトルVryの添え字であるyは重複点Prの第2の移動ベクトルの方向a,b,c,・・・と同一である。特徴点重複処理部40は、1回の比較を行うごとに移動ベクトルVryを変更し、全ての移動ベクトルVryについて移動ベクトルVryと移動ベクトルVtxとを比較する。
【００５２】
ステップS210において、特徴点重複処理部40は、1つの移動ベクトルVryと移動ベクトルVtxとが一致するか否かを判定する。移動ベクトルVryと移動ベクトルVtxとの方向が一致した場合、または移動ベクトルVryと移動ベクトルVtxとの長さと方向とがそれぞれ一致した場合、移動ベクトルVryと移動ベクトルVtxとが一致すると判定される。
【００５３】
移動ベクトルVryと移動ベクトルVtxとが一致しなかった（同一でなかった）場合、ステップS213の処理が行われる。移動ベクトルVryと移動ベクトルVtxとが一致した（同一であった）場合、ステップS211において、特徴点重複処理部40は、移動ベクトルVryに対応するカウント数Cyを所定の数（例えば1）だけインクリメントする。カウント数Cyは、重複点の移動ベクトルVryと同一である移動ベクトルVtxの数を示す。カウント数Cyの初期値は、例えば0である。移動ベクトルVryと移動ベクトルVtxとが一致しなかった場合、移動ベクトルVryに対応するカウント数Cyは変化しない。
【００５４】
ステップS212において、特徴点重複処理部40は、全ての移動ベクトルVryについてステップS210の比較を行ったか否かを判定する。ステップS210の比較を行っていない移動ベクトルVryがある場合、その移動ベクトルVryについてステップS210の比較が行われる。全ての移動ベクトルVryについてステップS210の比較が行われた場合、ステップS213において、特徴点重複処理部40は、サーチエリア内の全ての特徴点Ptxの処理が完了したか否かを判定する。
【００５５】
サーチエリア内の一部の特徴点Ptxの処理が完了していない場合、サーチエリア内の第2の特徴点の中から、特徴点Ptxとして既に選択された特徴点を除く第2の特徴点が特徴点Ptxとして選択され、ステップS206の処理が行われる。サーチエリア内の全ての特徴点Ptxの処理が完了した場合、ステップS214において、特徴点重複処理部40は、カウント数Cyが最も多い移動ベクトルVry（以下、移動ベクトルVrmaxと記載）を選択する。最も多いカウント数Cyが複数個ある場合、特徴点重複処理部40は、複数のカウント数Cyに対応する複数の移動ベクトルVrmaxを選択する。ステップS214で選択された移動ベクトルVrmaxは、重複点である第2の特徴点のうち、第1の特徴点に正確に対応する第2の特徴点の候補に対応する。
【００５６】
ステップS215において、特徴点重複処理部40は、移動ベクトルVrmaxが複数個あるか否かを判定する。移動ベクトルVrmaxが複数個ある場合、ステップS216において、特徴点重複処理部40は、サーチエリアの大きさ（画素数等）が、予め設定された閾値よりも小さいか否かを判定する。サーチエリアの大きさが閾値よりも小さい場合、ステップS217において、特徴点重複処理部40は、サーチエリアを拡大すると決定する。続いて、ステップS205において、特徴点重複処理部40はサーチエリアを設定する。ステップS217の処理に続いてステップS205の処理が行われる場合、ステップS205では前回設定されたサーチエリアよりも大きいサーチエリアが設定される。
【００５７】
サーチエリアの大きさが閾値以上である場合、サーチエリアが十分大きくても、重複点Prの移動ベクトルVryと一致する移動ベクトルVtxが見つからない。このため、重複点Prは、第1の特徴点と正確にマッチングしない特徴点であると判断される。したがって、ステップS218において、特徴点重複処理部40は、特徴点の情報を管理するためのリストから、現在選択されている重複点Prの情報を削除することにより、リストを更新する。特徴点の情報を管理するためのリストは、例えば図3に示す情報を含むリストである。このリストは、特徴点マッチング処理装置内の図示していないメモリに記憶されてもよい。
【００５８】
移動ベクトルVrmaxが1つのみである場合、ステップS219において、特徴点重複処理部40は、特徴点の情報を管理するためのリストから、現在選択されている重複点Prに関して、移動ベクトルVrmax以外の移動ベクトルVryの情報を削除することにより、リストを更新する。この結果、重複点Prは、これ以降に他の重複点の処理が行われる際、重複点以外の第2の特徴点Ptxとして扱われる。
【００５９】
ステップS218,S219においてリストが更新された後、ステップS220において、特徴点重複処理部40は、全ての重複点の処理が完了したか否かを判定する。一部の重複点の処理が完了していない場合、ステップS204において、特徴点重複処理部40は、重複点である第2の特徴点の中から、重複点Prとして既に選択された特徴点を除く第2の特徴点を重複点Prとして選択する。全ての重複点の処理が完了した場合、ステップS221において、処理が終了する。
【００６０】
上記の処理によれば、特徴点重複処理部40は、同一の重複点に対応する複数の第1の移動ベクトル（Vry）と、第1の特徴点とマッチングした、重複点以外の複数の第2の特徴点に対応する複数の第2の移動ベクトル（Vtx）とを比較し（ステップS209）、複数の第1の移動ベクトルから、最も多くの第2の移動ベクトルと一致する移動ベクトルを1つ選択する（ステップS214）。
【００６１】
上記の処理では、カウント数Cyが最も多い移動ベクトルVrmaxが選択されるが、カウント数Cyが2番目に多い移動ベクトルVryあるいは3番目に多い移動ベクトルVry等を選択し、選択した移動ベクトル以外の移動ベクトルVryの情報をリストから削除してもよい。上記の処理によってリストから削除されずに残った移動ベクトルは、他の重複点の処理において、重複点以外の第2の特徴点Ptxの移動ベクトルVtxの情報として参照される。このため、カウント数Cyが最も多い移動ベクトルVrmaxを選択することで、他の重複点の処理で有益な、より信頼性の高い移動ベクトルの情報を残すことができる。
【００６２】
図7〜図9は、特徴点重複処理の一例を示している。図7(a)に示す例の場合、ステップS204において重複点Prが選択され、ステップS205において第2の画像にサーチエリア700が設定される。続いて、ステップS209において、重複点Prの移動ベクトルVra,Vrbと、サーチエリア700内の特徴点Ptx（x=1,2,3）の移動ベクトルVtxとが比較される。移動ベクトルVraと移動ベクトルVt1,Vt2,Vt3とが一致するため、ステップS211の処理によってカウント数Caが3となる。カウント数Caが3であり、カウント数Cbが0であるため、ステップS214において移動ベクトルVraが選択され、ステップS219において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【００６３】
図7(b)に示す例の場合、ステップS204において重複点Prが選択され、ステップS205において第2の画像にサーチエリア710が設定される。続いて、ステップS209において、重複点Prの移動ベクトルVra,Vrbと、サーチエリア710内の特徴点Ptx（x=1,2）の移動ベクトルVtxとが比較される。移動ベクトルVra,Vrbはいずれも移動ベクトルVt1,Vt2と一致しないため、移動ベクトルVra,Vrbに対応するカウント数Ca,Cbはともに0のままである。カウント数Ca,Cbが同一の数であるため、ステップS214において移動ベクトルVra,Vrbが選択される。移動ベクトルVrmaxが2個であるため、ステップS217,S205の結果、サーチエリア710がサーチエリア711に拡大される。
【００６４】
続いて、ステップS209において、重複点Prの移動ベクトルVra,Vrbと、サーチエリア711内の特徴点Ptx（x=1,2,3,4）の移動ベクトルVtxとが比較される。移動ベクトルVraと移動ベクトルVt3,Vt4とが一致するため、ステップS211の処理によってカウント数Caが2となる。カウント数Caが2であり、カウント数Cbが0であるため、ステップS214において移動ベクトルVraが選択され、ステップS219において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【００６５】
図8(a)に示す例の場合、ステップS204において重複点Prが選択され、ステップS205において第2の画像にサーチエリア800が設定される。続いて、ステップS209において、重複点Prの移動ベクトルVra,Vrbと、サーチエリア800内の特徴点Ptx（x=1,2,3）の移動ベクトルVtxとが比較される。移動ベクトルVrbと移動ベクトルVt1とが一致するため、ステップS211の処理によってカウント数Cbが1となる。カウント数Caが0であり、カウント数Cbが1であるため、ステップS214において移動ベクトルVrbが選択され、ステップS219において移動ベクトルVraの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点として扱われる。
【００６６】
図8(b)に示す例の場合、ステップS204において重複点Prが選択され、ステップS205において第2の画像にサーチエリア810が設定される。サーチエリア810内の特徴点Pt5は重複点であるため、ステップS208において特徴点Pt5は無視される。続いて、ステップS209において、重複点Prの移動ベクトルVra,Vrbと、サーチエリア810内の特徴点Ptx（x=1,2,3,4）の移動ベクトルVtxとが比較される。移動ベクトルVraと移動ベクトルVt1,Vt3,Vt4とが一致するため、ステップS211の処理によってカウント数Caが3となる。カウント数Caが3であり、カウント数Cbが0であるため、ステップS214において移動ベクトルVraが選択され、ステップS219において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【００６７】
図9に示す例の場合、ステップS204において重複点Prが選択され、ステップS205において第2の画像にサーチエリア900が設定される。続いて、ステップS209において、重複点Prの移動ベクトルVra,Vrbと、サーチエリア900内の特徴点Ptx（x=1,2,3,4）の移動ベクトルVtxとが比較される。移動ベクトルVraと移動ベクトルVt2,Vt3とが一致するため、ステップS211の処理によってカウント数Caが2となる。また、移動ベクトルVrbと移動ベクトルVt1,Vt4とが一致するため、ステップS211の処理によってカウント数Cbが2となる。カウント数Ca,Cbが同一の数であるため、ステップS214において移動ベクトルVra,Vrbが選択される。移動ベクトルVrmaxが2個であるため、ステップS217,S205の結果、サーチエリア900がサーチエリア901に拡大される。
【００６８】
続いて、ステップS209において、重複点Prの移動ベクトルVra,Vrbと、サーチエリア901内の特徴点Ptx（x=1,2,3,4,5,6）の移動ベクトルVtxとが比較される。移動ベクトルVraと移動ベクトルVt2,Vt3,Vt6とが一致するため、ステップS211の処理によってカウント数Caが3となる。また、移動ベクトルVrbと移動ベクトルVt1,Vt4とが一致するため、ステップS211の処理によってカウント数Cbが2となる。カウント数Caが3であり、カウント数Cbが2であるため、ステップS214において移動ベクトルVraが選択され、ステップS219において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【００６９】
本実施形態では、重複点Prの移動ベクトルVryが、重複点Prの周囲に存在する特徴点Ptxの移動ベクトルVtxと同一であった場合に重複点をマッチング点として残すことで、より正確なマッチング点の数を増やすことができる。また、カウント数Cyが最も多い移動ベクトルVrmaxを選択することで、他の重複点の処理で有益な、より信頼性の高い移動ベクトルの情報を残すことができる。
【００７０】
（第3の実施形態）
次に、本発明の第3の実施形態を説明する。本実施形態による特徴点マッチング処理装置の構成は、図1に示す特徴点マッチング処理装置の構成と同一であるので、構成についての説明を省略する。
【００７１】
本実施形態では、重複点を基準とする所定のサーチエリア内において、重複点以外の第2の特徴点の第2の移動ベクトルの統計的な数（本実施形態では同一の移動ベクトルの数）に基づいて、重複点の複数の第1の移動ベクトルの中から、第2の移動ベクトルと類似する移動ベクトルが選択される。具体的には、特徴点重複処理部40は、第1の特徴点とマッチングした、重複点以外の複数の第2の特徴点に対応する複数の第2の移動ベクトルの中で最も多い移動ベクトルを第3の移動ベクトルとして選択し、同一の重複点に対応する複数の第1の移動ベクトルと、第3の移動ベクトルとを比較し、複数の第1の移動ベクトルから、第3の移動ベクトルの方向と最も近い方向を有する移動ベクトルを1つ選択する。
【００７２】
例えば、特徴点重複処理部40は、複数の第1の移動ベクトルから、第1の移動ベクトルの方向を示す値と第3の移動ベクトルの方向を示す値との差が第1の閾値内となる移動ベクトルを1つ選択する。
【００７３】
あるいは、特徴点重複処理部40は、第1の特徴点とマッチングした、重複点以外の複数の第2の特徴点に対応する複数の第2の移動ベクトルの中で最も多い移動ベクトルを第3の移動ベクトルとして選択し、同一の重複点に対応する複数の第1の移動ベクトルと、第3の移動ベクトルとを比較し、複数の第1の移動ベクトルから、第3の移動ベクトルの方向および長さと最も近い方向および長さを有する移動ベクトルを1つ選択する。
【００７４】
例えば、特徴点重複処理部40は、複数の第1の移動ベクトルから、第1の移動ベクトルの方向を示す値と第3の移動ベクトルの方向を示す値との差が第1の閾値内であって、かつ、第1の移動ベクトルの長さと第3の移動ベクトルの長さとの差が第2の閾値内である移動ベクトルを1つ選択する。
【００７５】
本実施形態による特徴点マッチング処理装置の動作は、図2における特徴点重複処理（ステップS104）を除いて、図2に示される動作と同一である。以下では、特徴点重複処理（ステップS104）についてのみ説明する。
【００７６】
図10および図11は、本実施形態における特徴点重複処理（ステップS104）の詳細を示している。図10および図11に示す処理は、図3における1行分の情報に対する処理に相当する。図10および図11に示す処理を繰り返すことで、2枚の画像から検出された全ての特徴点に対して処理を行うことが可能となる。また、第1の画像と第2の画像との少なくとも一方を変更して処理を繰り返すことで、3枚以上の画像から任意に選択した2枚の画像のそれぞれの組合せについて、特徴点重複処理を行うことができる。
【００７７】
ステップS300において、処理が開始された後、ステップS301〜S308の処理は図5におけるステップS201〜S208の処理と同一であるので、ステップS301〜S308の処理に関する説明を省略する。本実施形態では、ステップS306において、特徴点Pt1,Pt2,Pt3,・・・の順に特徴点Ptxが選択される。
【００７８】
ステップS307において特徴点Ptxが重複点ではないことを重複点フラグが示している場合、ステップS309において、特徴点重複処理部40は、サーチエリア内の第2の特徴点である特徴点Ptx（重複点Prを除く）の第2の移動ベクトルである移動ベクトルVtx（Vt1,Vt2,Vt3,・・・）と、全ての処理済みの特徴点Ptj（j<x）の移動ベクトルVtjとを比較する。特徴点Pt1が選択されている場合、ステップS309の処理は行われない。特徴点Pt2が選択されている場合、移動ベクトルVt2と移動ベクトルVt1とが比較される。特徴点Pt3が選択されている場合、移動ベクトルVt3と移動ベクトルVt1とが比較され、移動ベクトルVt3と移動ベクトルVt2とが比較される。他の特徴点が選択されている場合も、これと同様である。
【００７９】
移動ベクトルの比較が行われた後、ステップS310において、特徴点重複処理部40は、移動ベクトルVtxと一致する移動ベクトルVtjがあるか否かを判定する。移動ベクトルVtxと一致する移動ベクトルVtjがある場合、ステップS311において、特徴点重複処理部40は、移動ベクトルVtjに対応するカウント数Cjを所定の数（例えば1）だけインクリメントする。カウント数Cjは、同一である特徴点Ptjの移動ベクトルVtjの数を示す。カウント数Cjの初期値は、例えば0である。移動ベクトルVtxと一致する移動ベクトルVtjが複数個ある場合、jが最も小さい移動ベクトルVtjに対応するカウント数Cjがインクリメントされる。移動ベクトルVtxと一致する移動ベクトルVtjがない場合、ステップS312において、特徴点重複処理部40は、移動ベクトルVtxに対応するカウント数Cxを所定の数（例えば1）だけインクリメントする。
【００８０】
例えば、移動ベクトルVt1,Vt2,Vt3が一致する場合、特徴点Pt1に関する処理の途中のステップS312においてカウント数C1が1となった後、特徴点Pt2に関する処理の途中のステップS311においてカウント数C1が2となる。その後、特徴点Pt3に関する処理の途中のステップS311においてカウント数C1が3となる。つまり、ステップS309〜S312の処理によって、同一である移動ベクトルVtxの数がカウントされる。
【００８１】
ステップS311,S312においてカウント数Cx,Cjがインクリメントされた後、ステップS313において、特徴点重複処理部40は、サーチエリア内の全ての特徴点Ptxの処理が完了したか否かを判定する。
【００８２】
サーチエリア内の一部の特徴点Ptxの処理が完了していない場合、サーチエリア内の第2の特徴点の中から、特徴点Ptxとして既に選択された特徴点を除く第2の特徴点が特徴点Ptxとして選択され、ステップS306の処理が行われる。サーチエリア内の全ての特徴点Ptxの処理が完了した場合、ステップS314において、特徴点重複処理部40は、カウント数Cxが最も多い第3の移動ベクトルである移動ベクトルVtx（以下、移動ベクトルVtmaxと記載）に関して、カウント数Cx（以下、移動ベクトルCmaxと記載）が2以上であるか否かを判定する。カウント数Cmaxが1以下である場合、ステップS316の処理が行われる。
【００８３】
カウント数Cmaxが2以上である場合、ステップS315において、特徴点重複処理部40は、移動ベクトルVtmaxが複数個あるか否かを判定する。移動ベクトルVtmaxが複数個ある場合、ステップS316において、特徴点重複処理部40は、サーチエリアの大きさ（画素数等）が、予め設定された閾値よりも小さいか否かを判定する。サーチエリアの大きさが閾値よりも小さい場合、ステップS317において、特徴点重複処理部40は、サーチエリアを拡大すると決定する。続いて、ステップS305において、特徴点重複処理部40はサーチエリアを設定する。ステップS317の処理に続いてステップS305の処理が行われる場合、ステップS305では前回設定されたサーチエリアよりも大きいサーチエリアが設定される。
【００８４】
サーチエリアの大きさが閾値以上である場合、ステップS318において、特徴点重複処理部40は、特徴点の情報を管理するためのリストから、現在選択されている重複点Prの情報を削除することにより、リストを更新する。
【００８５】
移動ベクトルVtmaxが1つのみである場合、ステップS319において、特徴点重複処理部40は、重複点Prの第1の移動ベクトルである移動ベクトルVry（Vra,Vrb,Vrc,・・・）の中から、移動ベクトルVtmaxに最も近い方向を有する移動ベクトルを選択する。このとき、特徴点重複処理部40は、重複点の移動ベクトルVryと、移動ベクトルVtmaxとのそれぞれの方向を示す角度を比較し、移動ベクトルVtmaxの角度に最も近い角度の移動ベクトルVryを選択する。移動ベクトル(Δxi,Δyi)の方向を示す角度θiは以下の(2)式により算出される。
θi ＝ tan-1(Δyi/Δxi)  ・・・(2)
【００８６】
ステップS320において、特徴点重複処理部40は、ステップS319で選択された移動ベクトルVryが、移動ベクトルVtmaxを基準とする閾値内にあるか否かを判定する。図12は、ステップS320における判定の内容を示している。特徴点重複処理部40は、(2)式を用いて算出された、移動ベクトルVryの角度と、移動ベクトルVtmaxの角度との差が閾値内にあるか否かを判定する。
【００８７】
移動ベクトルVryが、移動ベクトルVtmaxを基準とする閾値内にない場合、ステップS316の処理が行われる。移動ベクトルVryが、移動ベクトルVtmaxを基準とする閾値内にある場合、特徴点重複処理部40は、特徴点の情報を管理するためのリストから、現在選択されている重複点Prに関して、ステップS319で選択された移動ベクトルVry以外の移動ベクトルVryの情報を削除することにより、リストを更新する。この結果、重複点Prは、これ以降に他の重複点の処理が行われる際、重複点以外の第2の特徴点Ptxとして扱われる。
【００８８】
ステップS318,S321においてリストが更新された後、ステップS322において、特徴点重複処理部40は、全ての重複点の処理が完了したか否かを判定する。一部の重複点の処理が完了していない場合、ステップS304において、特徴点重複処理部40は、重複点である第2の特徴点の中から、重複点Prとして既に選択された特徴点を除く第2の特徴点を重複点Prとして選択する。全ての重複点の処理が完了した場合、ステップS323において、処理が終了する。
【００８９】
上記の処理によれば、特徴点重複処理部40は、同一の重複点に対応する複数の第1の移動ベクトル（Vry）と、第1の特徴点とマッチングした、重複点以外の複数の第2の特徴点に対応する第3の移動ベクトル（Vtmax）とを比較し、複数の第1の移動ベクトルから、第3の移動ベクトルと類似する移動ベクトル（第3の移動ベクトルの方向と最も近い方向を有する移動ベクトル）を1つ選択する（ステップS319）。
【００９０】
上記の処理では、移動ベクトルの方向に基づいて移動ベクトルVryが選択されるが、移動ベクトルの方向および長さに基づいて移動ベクトルVryが選択されてもよい。例えば、ステップS319において、特徴点重複処理部40は、重複点の移動ベクトルVryと、移動ベクトルVtmaxとの角度および長さを比較し、移動ベクトルVtmaxの角度および長さに最も近い角度および長さの移動ベクトルVryを選択する。移動ベクトル(Δxi,Δyi)の長さLiは以下の(3)式により算出される。
【００９１】
【数１】
2015087941.tif 000003
【００９２】
また、ステップS320において、特徴点重複処理部40は、移動ベクトルVryの角度と、移動ベクトルVtmaxの角度との差が第1の閾値内にあり、かつ、移動ベクトルVryの長さと、移動ベクトルVtmaxの長さとの差が第2の閾値内にあるか否かを判定する。角度の差と長さの差とがいずれも閾値内にある場合、ステップS321の処理が行われ、それ以外の場合、ステップS316の処理が行われる。
【００９３】
上記の処理では、ステップS320において、ステップS319で選択された移動ベクトルVryが、移動ベクトルVtmaxを基準とする閾値内にあるか否かの判定が行われる。これに対して、ステップS319で移動ベクトルVryが選択された後、ステップS320の判定を行わずに、ステップS321の処理を行ってもよい。
【００９４】
上記の処理によってリストから削除されずに残った移動ベクトルは、他の重複点の処理において、重複点以外の第2の特徴点Ptxの移動ベクトルVtxの情報として参照される。このため、移動ベクトルVtmaxの方向と最も近い方向を有する移動ベクトルVr（または、移動ベクトルVtmaxの方向および長さと最も近い方向および長さを有する移動ベクトル）を選択することで、他の重複点の処理で有益な、より信頼性の高い移動ベクトルの情報を残すことができる。
【００９５】
図13〜図15は、特徴点重複処理の一例を示している。図13(a)に示す例の場合、ステップS304において重複点Prが選択され、ステップS305において第2の画像にサーチエリア1300が設定される。続いて、ステップS309において、サーチエリア1300内の特徴点Ptx（x=1,2,3）の移動ベクトルVtx同士が比較される。移動ベクトルVt1,Vt2,Vt3が一致するため、ステップS311,S312の処理によってカウント数C1が3となる。移動ベクトルVt1のカウント数C1が最も多いため、ステップS319において、移動ベクトルVt1に最も方向が近い移動ベクトルVraが選択され、ステップS321において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【００９６】
図13(b)に示す例の場合、ステップS304において重複点Prが選択され、ステップS305において第2の画像にサーチエリア1310が設定される。続いて、ステップS309において、サーチエリア1310内の特徴点Ptx（x=1,2）の移動ベクトルVtx同士が比較される。移動ベクトルVt1,Vt2は一致しないため、ステップS312の処理によって、移動ベクトルVt1,Vt2に対応するカウント数C1,C2はともに1となる。カウント数C1,C2がともに1であるため、ステップS317,S305の結果、サーチエリア1310がサーチエリア1311に拡大される。
【００９７】
続いて、サーチエリア1311内の特徴点Ptx（x=1,2,3,4）の移動ベクトルVtx同士が比較される。移動ベクトルVt1は他の移動ベクトルVt2,Vt3,Vt4と一致しないため、ステップS312の処理によってカウント数C1が1となる。また、移動ベクトルVt2は他の移動ベクトルVt1,Vt3,Vt4と一致しないため、ステップS312の処理によってカウント数C2が1となる。また、移動ベクトルVt3,Vt4が一致するため、ステップS311,S312の処理によってカウント数C3が2となる。移動ベクトルVt3のカウント数C3が最も多いため、ステップS319において、移動ベクトルVt3に最も方向が近い移動ベクトルVraが選択され、ステップS321において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【００９８】
図14(a)に示す例の場合、ステップS304において重複点Prが選択され、ステップS305において第2の画像にサーチエリア1400が設定される。続いて、ステップS309において、サーチエリア1400内の特徴点Ptx（x=1,2,3）の移動ベクトルVtx同士が比較される。移動ベクトルVt1は他の移動ベクトルVt2,Vt3と一致しないため、ステップS312の処理によってカウント数C1が1となる。また、移動ベクトルVt2,Vt3が一致するため、ステップS311,S312の処理によってカウント数C2が2となる。移動ベクトルVt2のカウント数C2が最も多いため、ステップS319において、移動ベクトルVt2に最も方向が近い移動ベクトルVraが選択され、ステップS321において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【００９９】
図14(b)に示す例の場合、ステップS304において重複点Prが選択され、ステップS305において第2の画像にサーチエリア1410が設定される。サーチエリア1410内の特徴点Pt5は重複点であるため、ステップS308において特徴点Pt5は無視される。続いて、ステップS309において、サーチエリア1410内の特徴点Ptx（x=1,2,3,4）の移動ベクトルVtx同士が比較される。移動ベクトルVt2は他の移動ベクトルVt1,Vt3,Vt4と一致しないため、ステップS312の処理によってカウント数C2が1となる。また、移動ベクトルVt1,Vt3,Vt4が一致するため、ステップS311,S312の処理によってカウント数C1が3となる。移動ベクトルVt1のカウント数C1が最も多いため、ステップS319において、移動ベクトルVt1に最も方向が近い移動ベクトルVraが選択され、ステップS321において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【０１００】
図15に示す例の場合、ステップS304において重複点Prが選択され、ステップS305において第2の画像にサーチエリア1500が設定される。続いて、ステップS309において、サーチエリア1500内の特徴点Ptx（x=1,2,3,4）の移動ベクトルVtx同士が比較される。移動ベクトルVt1,Vt4が一致するため、ステップS311,S312の処理によってカウント数C1が2となる。また、移動ベクトルVt2,Vt3が一致するため、ステップS311,S312の処理によってカウント数C2が2となる。カウント数C1,C2がともに2であるため、ステップS317,S305の結果、サーチエリア1500がサーチエリア1501に拡大される。
【０１０１】
続いて、ステップS309において、サーチエリア1501内の特徴点Ptx（x=1,2,3,4,5,6）の移動ベクトルVtx同士が比較される。移動ベクトルVt5は他の移動ベクトルVt2,Vt3,Vt4,Vt6と一致しないため、ステップS312の処理によってカウント数C5が1となる。また、移動ベクトルVt1,Vt4が一致するため、ステップS311,S312の処理によってカウント数C1が2となる。また、移動ベクトルVt2,Vt3,Vt6が一致するため、ステップS311,S312の処理によってカウント数C2が3となる。移動ベクトルVt2のカウント数C2が最も多いため、ステップS319において、移動ベクトルVt2に最も方向が近い移動ベクトルVraが選択され、ステップS321において移動ベクトルVrbの情報がリストから削除される。特徴点重複処理の結果、重複点Prは、第1の特徴点と正確にマッチングする特徴点となる。
【０１０２】
本実施形態では、重複点Prの移動ベクトルVryが、重複点Prの周囲に存在する特徴点Ptxの移動ベクトルVtxと類似する場合に重複点をマッチング点として残すことで、より正確なマッチング点の数を増やすことができる。本実施形態では、第2の実施形態のように移動ベクトルVtxと完全に一致する移動ベクトルVryが存在しない場合でも、重複点をマッチング点として残すことができる。また、カウント数Cxが最も多い移動ベクトルVtmaxと類似する移動ベクトルVryを選択することで、他の重複点の処理で有益な、より信頼性の高い移動ベクトルの情報を残すことができる。
【０１０３】
以上、図面を参照して本発明の実施形態について詳述してきたが、具体的な構成は上記の実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【符号の説明】
【０１０４】
10  特徴点検出部、20  特徴量生成部、30  特徴点マッチング判定部、40  特徴点重複処理部、50  特徴点決定部
【図１】
2015087941.tif 000004
【図２】
2015087941.tif 000005
【図３】
2015087941.tif 000006
【図４】
2015087941.tif 000007
【図５】
2015087941.tif 000008
【図６】
2015087941.tif 000009
【図７】
2015087941.tif 000010
【図８】
2015087941.tif 000011
【図９】
2015087941.tif 000012
【図１０】
2015087941.tif 000013
【図１１】
2015087941.tif 000014
【図１２】
2015087941.tif 000015
【図１３】
2015087941.tif 000016
【図１４】
2015087941.tif 000017
【図１５】
2015087941.tif 000018