(57)【特許請求の範囲】
【請求項１】
画像間の対応付けを行なう画像間対応付け方法をコンピュータに実行させる画像間対応付けプログラムであって、
画像から抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、前記最下位階層の特徴点集合から順に繰り返すことにより、前記複数の特徴点それぞれが、上位階層ごとの前記代表特徴点いずれかに連結されて最上位階層の前記代表特徴点いずれかに集約して連結される階層構造である特徴点集約階層構造を、対応付けの対象となる画像ごとに生成する特徴点集約階層構造生成手順と、
前記対応付けの対象となる２つの画像の間で対応付けを行なう際に、前記特徴点集約階層構造生成手順によって生成された前記２つの画像に対応する前記特徴点集約階層構造の前記最上位階層それぞれの前記代表特徴点すべての間で類似度を算出して特徴点間の対応付けを行なったうえで、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが前記代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出して特徴点間の対応付けを行なう階層間対応付け処理を、前記最上位階層の直下にある階層から順に繰り返すことにより、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付ける対応付け手順と、
をコンピュータに実行させることを特徴とする画像間対応付けプログラム。
【請求項２】
前記対応付け手順は、前記最下位階層より上位にある階層において前記階層間対応付け処理により対応付けられた特徴点間の類似度を用いて当該階層の直上にある階層における特徴点間の類似度を更新するとともに、類似度が更新された下位階層の直上にある上位階層にて対応付けられている特徴点間の類似度を当該下位階層にて更新された特徴点間の類似度を用いて更新する類似度更新処理と、上位階層にて対応付けられている特徴点間の更新された類似度を用いて当該上位階層の直下にある下位階層における特徴点間の対応付けを更新する階層間対応付け更新処理とを繰り返して、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付けることを特徴とする請求項１に記載の画像間対応付けプログラム。
【請求項３】
画像間の対応付けを行なう画像間対応付け装置であって、
画像から抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、前記最下位階層の特徴点集合から順に繰り返すことにより、前記複数の特徴点それぞれが、上位階層ごとの前記代表特徴点いずれかに連結されて最上位階層の前記代表特徴点いずれかに集約して連結される階層構造である特徴点集約階層構造を、対応付けの対象となる画像ごとに生成する特徴点集約階層構造生成手段と、
前記対応付けの対象となる２つの画像の間で対応付けを行なう際に、前記特徴点集約階層構造生成手段によって生成された前記２つの画像に対応する前記特徴点集約階層構造の前記最上位階層それぞれの前記代表特徴点すべての間で類似度を算出して特徴点間の対応付けを行なったうえで、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが前記代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出して特徴点間の対応付けを行なう階層間対応付け処理を、前記最上位階層の直下にある階層から順に繰り返すことにより、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付ける対応付け手段と、
を備えたことを特徴とする画像間対応付け装置。
【請求項４】
画像間の対応付けを行なう画像間対応付け方法であって、
画像から抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、前記最下位階層の特徴点集合から順に繰り返すことにより、前記複数の特徴点それぞれが、上位階層ごとの前記代表特徴点いずれかに連結されて最上位階層の前記代表特徴点いずれかに集約して連結される階層構造である特徴点集約階層構造を、対応付けの対象となる画像ごとに生成する特徴点集約階層構造生成ステップと、
前記対応付けの対象となる２つの画像の間で対応付けを行なう際に、前記特徴点集約階層構造生成ステップによって生成された前記２つの画像に対応する前記特徴点集約階層構造の前記最上位階層それぞれの前記代表特徴点すべての間で類似度を算出して特徴点間の対応付けを行なったうえで、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが前記代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出して特徴点間の対応付けを行なう階層間対応付け処理を、前記最上位階層の直下にある階層から順に繰り返すことにより、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付ける対応付けステップと、
を含んだことを特徴とする画像間対応付け方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像間対応付けプログラム、画像間対応付け装置および画像間対応付け方法に関する。
【背景技術】
【０００２】
従来より、画像に含まれる特徴的な情報を用いて、様々な処理が行われている。例えば、特許文献１では、３次元画像に含まれる物体の形状的特徴を解析することにより、３次元画像データベースの中から当該物体を撮影した他の３次元画像や、当該物体と類似した物体を撮影した３次元画像を検索する技術が開示されている。また、特許文献２では、文書を撮影した画像から、文字の大きさや文字間の距離などに基づいて当該文書のレイアウトの特徴を解析することにより、文書画像データベースに格納されている大量の文書画像を分類する技術が開示されている。  
【０００３】
ここで、画像に含まれる特徴的な情報を用いた代表的な処理としては、比較対象となる２つの画像を対応付ける処理がある。例えば、左右に配置されたカメラそれぞれによって同じ景色を撮影された２つの画像からステレオ画像を生成したり、移動体（例えば、歩行型ロボットなど）に搭載されたカメラによって撮影された時系列に沿った２つの画像から、当該移動体の移動方向を推定したりする場合などに、画像間の対応付け処理が行なわれる。
【０００４】
具体的には、まず、比較対象となる２つの画像それぞれをフィルタ処理することにより、画像に含まれる物体のコーナーやエッジなどを特徴点として複数抽出し、抽出した複数の特徴点それぞれの輝度、色、方向などを特徴量として算出する。そして、抽出された複数の特徴点それぞれの特徴量を、２つの画像の間で、総当りで比較して類似度を求め、類似度が高い特徴点のペアを対応付けることにより、画像間の対応付けを行なう。
【０００５】
【特許文献１】特開２００１−３３８２９４号公報
【特許文献２】特開２００３−１７８０８１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、上記した従来の技術は、抽出された複数の特徴点を総当りで比較して類似度を求めるために多大な計算量が必要とされるので、画像間の対応付け処理に時間がかかるという課題があった。
【０００７】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、画像間の対応付けを迅速に行なうことが可能となる画像間対応付けプログラム、画像間対応付け装置および画像間対応付け方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するため、このプログラムは、画像間の対応付けを行なう画像間対応付け方法をコンピュータに実行させる画像間対応付けプログラムであって、画像から抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、前記最下位階層の特徴点集合から順に繰り返すことにより、前記複数の特徴点それぞれが、上位階層ごとの前記代表特徴点いずれかに連結されて最上位階層の前記代表特徴点いずれかに集約して連結される階層構造である特徴点集約階層構造を、対応付けの対象となる画像ごとに生成する特徴点集約階層構造生成手順と、前記対応付けの対象となる２つの画像の間で対応付けを行なう際に、前記特徴点集約階層構造生成手順によって生成された前記２つの画像に対応する前記特徴点集約階層構造の前記最上位階層それぞれの前記代表特徴点すべての間で類似度を算出して特徴点間の対応付けを行なったうえで、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが前記代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出して特徴点間の対応付けを行なう階層間対応付け処理を、前記最上位階層の直下にある階層から順に繰り返すことにより、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付ける対応付け手順と、をコンピュータに実行させることを要件とする。
【発明の効果】
【０００９】
開示のプログラムは、特徴点の総当りによる比較を行う必要がなく、画像間の対応付けを迅速に行なうことが可能となる。
【発明を実施するための最良の形態】
【００１０】
以下に添付図面を参照して、この発明に係る画像間対応付けプログラム、画像間対応付け装置および画像間対応付け方法の実施例を詳細に説明する。なお、以下では、この発明に係る画像間対応付けプログラムを含む画像マッチング装置を実施例として説明する。また、以下では、実施例１における画像マッチング装置の構成および処理の手順、実施例１の効果を順に説明し、次に実施例１と同様に、実施例２に係る画像マッチング装置について説明し、最後に、他の実施例について説明する。
【実施例１】
【００１１】
［実施例１における画像マッチング装置の構成］
まず最初に、図１を用いて、実施例１における画像マッチング装置の構成を説明する。図１は、実施例１における画像マッチング装置の構成を示すブロック図である。図１に示すように、実施例１における画像マッチング装置１０は、画像記憶部１１ａと、ピラミッド特徴点グラフ記憶部１１ｂと、マッチングリスト記憶部１１ｃと、ピラミッド特徴点グラフ生成部１２ａと、マッチングリスト生成部１２ｂと、推定部１２ｃと、カメラコントローラ１２ｄとを備え、カメラ２０と接続される。以下に、これらの各部の処理を説明する。
【００１２】
なお、画像マッチング装置１０とカメラ２０とは、歩行型ロボットに搭載され、画像マッチング装置１０は、歩行型ロボットに搭載されたカメラ２０によって撮影された時系列に沿った２つの画像間を対応付けることにより、歩行型ロボットの移動量および移動方向を推定する。
【００１３】
カメラ２０は、歩行型ロボットの移動方向を推定するために用いられる画像を、一定時間ごとに撮影し、撮影した画像を、例えば、ＪＰＥＧ（Ｊｏｉｎｔ  Ｐｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）などの形式からなる画像データに変換し、変換された画像データを、順次、画像記憶部１１ａに送信し、画像記憶部１１ａは、カメラ２０から受信した画像データを記憶する。
【００１４】
ピラミッド特徴点グラフ生成部１２ａは、画像記憶部１１ａが記憶する画像データから抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、最下位階層の特徴点集合から順に、所定の設定回数にわたり繰り返すことにより、複数の特徴点それぞれが、上位階層ごとの代表特徴点いずれかに連結されて最上位階層の代表特徴点いずれかに集約して連結されるピラミッド型の階層構造であるピラミッド特徴点グラフを、対応付けの対象となる画像ごとに生成し、その結果を、ピラミッド特徴点グラフ記憶部１１ｂに格納する。なお、以下では、画像マッチング装置１０の管理者により、ピラミッド特徴点グラフ生成部１２ａが、４つの階層からなるピラミッド特徴点グラフを生成するように設定されている場合について説明する。
【００１５】
ピラミッド特徴点グラフ生成部１２ａの具体的な処理について、図２〜７を用いて説明する。図２は、ピラミッド特徴点グラフ生成部の原画像に対する処理を説明するための図であり、図３は、ピラミッド特徴点グラフ生成部のレベル１における処理を説明するための図であり、図４は、ピラミッド特徴点グラフ生成部のレベル２における処理を説明するための図であり、図５は、ピラミッド特徴点グラフ生成部のレベル３における処理を説明するための図であり、図６は、ピラミッド特徴点グラフ記憶部が記憶する画像Ａのピラミッド特徴点グラフを説明するための図であり、図７は、ピラミッド特徴点グラフ記憶部が記憶する画像Ｂのピラミッド特徴点グラフを説明するための図である。
【００１６】
まず、ピラミッド特徴点グラフ生成部１２ａは、画像記憶部１１ａが記憶する原画像としての画像データに対して、フィルタ処理を行ない、原画像に含まれる物体のコーナーやエッジなどを特徴点として複数個抽出し、抽出した複数の特徴点それぞれの輝度、色、方向などを特徴量として算出する。
【００１７】
例えば、ピラミッド特徴点グラフ生成部１２ａは、図２の（Ａ）に示すように、原画像である画像Ａに対してフィルタ処理を行なうことにより、９個の特徴点を抽出し、抽出した９個の特徴点に対して順に、特徴点ＩＤ「Ａ１〜Ａ９」を割り振る。ここで、「Ａ１〜Ａ９」のＩＤが割り振られた９個の特徴点が、画像Ａにおける最下位階層の特徴点集合となり、最終的な対応付けの処理対象となる。なお、以下では、最下位階層の特徴点集合のことを、「レベル０」の特徴点集合と記す。
【００１８】
さらに、ピラミッド特徴点グラフ生成部１２ａは、図２の（Ａ）に示すように、「Ａ１〜Ａ９」のＩＤが割り振られた特徴点それぞれの、画像Ａにおける座標「ＣＡ１〜ＣＡ９」を取得するとともに、「Ａ１〜Ａ９」のＩＤが割り振られた特徴点それぞれの特徴量を「ＦＡ１〜ＦＡ９」として算出する。なお、以下では、例えば、特徴点ＩＤ「Ａ１」が割り振られた特徴点のことを、単に、特徴点Ａ１と記す。
【００１９】
そして、ピラミッド特徴点グラフ生成部１２ａは、抽出された複数の特徴点ごとに、取得された座標データに基づいて、所定の距離内にある他の特徴点を検索し、検索された特徴点との類似度を算出する。例えば、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ１に対しては「特徴点Ａ２および特徴点Ａ４」が所定の距離内にあることから、図２の（Ｂ）に示すように、特徴点Ａ１と特徴点Ａ２との類似度として、「ＦＡ１」と「ＦＡ２」とを比較することで、「ＳＡ１−２」を算出し、特徴点Ａ１と特徴点Ａ４との類似度として、「ＦＡ１」と「ＦＡ４」とを比較することで、「ＳＡ１−４」を算出する。
【００２０】
また、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ２に対しては「特徴点Ａ１、特徴点Ａ３および特徴点Ａ４」が所定の距離内にあることから、図２の（Ｂ）に示すように、特徴点Ａ２と特徴点Ａ１との類似度として「ＳＡ１−２」を算出し、特徴点Ａ２と特徴点Ａ３との類似度として「ＳＡ２−３」を算出し、特徴点Ａ２と特徴点Ａ４との類似度として「ＳＡ２−４」を算出する。
【００２１】
以下、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ３に対しては「特徴点Ａ２および特徴点Ａ４」が、特徴点Ａ４に対しては「特徴点Ａ１、特徴点Ａ２および特徴点Ａ３」が、特徴点Ａ５に対しては「特徴点Ａ６」が、特徴点Ａ６に対しては「特徴点Ａ５」が、特徴点Ａ７に対しては「特徴点Ａ８および特徴点Ａ９」が、特徴点Ａ８に対しては「特徴点Ａ７および特徴点Ａ９」が、特徴点Ａ９に対しては「特徴点Ａ７および特徴点Ａ８」が、所定の距離内にあることから、特徴点Ａ３〜特徴点Ａ９それぞれにおいても、図２の（Ｂ）に示すように、類似度を算出する。
【００２２】
そして、ピラミッド特徴点グラフ生成部１２ａは、抽出された複数の特徴点すべての中から任意に代表特徴点を選択する。例えば、ピラミッド特徴点グラフ生成部１２ａは、図２の（Ｂ）に示すように、特徴点Ａ１と、特徴点Ａ４と、特徴点Ａ５と、特徴点Ａ９とを代表特徴点として選択する。
【００２３】
そして、ピラミッド特徴点グラフ生成部１２ａは、選択された代表特徴点それぞれにおいて、代表特徴点との類似度が算出されている特徴点の中で、所定の閾値以上の類似度となる類似度を検索し、検索された類似度と代表特徴点とを、「レベル０」の特徴点集合における部分集合として分類する。
【００２４】
例えば、ピラミッド特徴点グラフ生成部１２ａは、図２の（Ｂ）に示すように、特徴点Ａ１に対応付けられている類似度「ＳＡ１−２およびＳＡ１−４」を参照して、「ＳＡ１−２」のみが閾値以上であることから、特徴点Ａ１が代表特徴点である部分集合を、「特徴点Ａ１および特徴点Ａ２」とする。また、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ４に対応付けられている類似度「ＳＡ１−４、ＳＡ２−４およびＳＡ３−４」を参照して、「ＳＡ２−４およびＳＡ３−４」が、閾値以上であることから、特徴点Ａ４が代表特徴点である部分集合を「特徴点Ａ２、特徴点Ａ３および特徴点Ａ４」とする。
【００２５】
以下、同様に、特徴点Ａ５が代表特徴点である部分集合を「特徴点Ａ５および特徴点Ａ６」とし、特徴点Ａ９が代表特徴点である部分集合を「特徴点Ａ７、特徴点Ａ８および特徴点Ａ９」として、ピラミッド特徴点グラフ生成部１２ａは、「レベル０」の特徴点集合を、特徴点間の距離および特徴点間の類似度に基づいて、４つの部分集合に分類する。
【００２６】
なお、図２の（Ｂ）に示すように、特徴点Ａ２は、特徴点Ａ１を代表特徴点とする部分集合と、特徴点Ａ４を代表特徴点とする部分集合との両方において、構成要素となっている。
【００２７】
そして、ピラミッド特徴点グラフ生成部１２ａは、「レベル０」の特徴点集合にて分類された各部分集合における代表特徴点の集合を、「レベル１」の特徴点集合とする。例えば、ピラミッド特徴点グラフ生成部１２ａは、図３に示すように、レベル０の９個の特徴点それぞれが、レベル１の特徴点集合を形成する代表特徴点である特徴点Ａ１、特徴点Ａ４、特徴点Ａ５、特徴点Ａ９のいずれかにリンクされた階層構造を生成する。
【００２８】
なお、階層構造を示す情報として、ピラミッド特徴点グラフ生成部１２ａは、図３に示すように、「レベル１の特徴点Ａ１」は「レベル０の特徴点Ａ１および特徴点Ａ２」とリンクされるとするリンク情報を生成し、「レベル１の特徴点Ａ４」は「レベル０の特徴点Ａ２、特徴点Ａ３および特徴点Ａ４」とリンクされるとするリンク情報を生成し、「レベル１の特徴点Ａ５」は「レベル０の特徴点Ａ５および特徴点Ａ６」とリンクされるとするリンク情報を生成し、「レベル１の特徴点Ａ９」は「レベル０の特徴点Ａ７、特徴点Ａ８および特徴点Ａ９」とリンクされるとするリンク情報を生成する。
【００２９】
ここで、レベル０の特徴点Ａ２は、レベル１の特徴点Ａ１と、レベル１の特徴点Ａ４との両方にリンクされているが、「レベル０における特徴点Ａ２と特徴点Ａ１との類似度」と、「レベル０における特徴点Ａ２と特徴点Ａ４との類似度」とから、ピラミッド特徴点グラフ生成部１２ａは、レベル０の特徴点Ａ２がレベル１の特徴点Ａ１へリンクされる場合の重み付けは「０．６」であり、レベル１の特徴点Ａ４へリンクされる場合の重み付けは「０．４」であると算出し、算出した重み付けの情報は、上記したリンク情報に付与される。例えば、図３に示すように、「特徴点ＩＤ：Ａ１」のリンク情報は、「Ａ１，Ａ２（０．６）」となり、「特徴点ＩＤ：Ａ４」のリンク情報は、「Ａ２（０．４），Ａ３，Ａ４」となる。
【００３０】
そして、ピラミッド特徴点グラフ生成部１２ａは、上述した「レベル０」における「特徴量の算出処理、類似度の算出処理、代表特徴点の選択処理および部分集合の形成処理」を、「レベル１」においても実行する。
【００３１】
すなわち、ピラミッド特徴点グラフ生成部１２ａは、「レベル１」の特徴点集合を形成する代表特徴点である特徴点の特徴量を、再度、算出する。
【００３２】
例えば、ピラミッド特徴点グラフ生成部１２ａは、「レベル１」の特徴点Ａ１の特徴量「ＦＡ１（１）」を、リンク情報を参照して、レベル０にてリンクされている『特徴点Ａ１の特徴量「ＦＡ１」および特徴点Ａ２の特徴量「ＦＡ２」』の平均値として算出する。しかし、「レベル０」の特徴点Ａ２は、「レベル１」の特徴点Ａ１に対して、「重み付け：０．６」が付与されてリンクされているので、ピラミッド特徴点グラフ生成部１２ａは、「ＦＡ１（１）」を単に「ＦＡ１」と「ＦＡ２」との平均値として算出するのではなく、図３に示すように、「ＦＡ１」と「０．６×ＦＡ２」との平均値として算出する。
【００３３】
同様に、ピラミッド特徴点グラフ生成部１２ａは、「レベル１」の特徴点Ａ４の特徴量「ＦＡ４（１）」を、リンク情報およびリンク情報に付与されている重み付けを参照して、図３に示すように、「０．４×ＦＡ２」と、「ＦＡ３」と、「ＦＡ４」との平均値として算出する。
【００３４】
なお、「レベル１」の特徴点Ａ５および特徴点Ａ９においては、リンク情報に重み付けの情報が付与されていないので、ピラミッド特徴点グラフ生成部１２ａは、図３に示すように、「レベル１」における特徴量「ＦＡ５（１）」および「ＦＡ９（１）」を、レベル０にてリンクされている特徴点の特徴量の平均値として算出する。
【００３５】
そして、ピラミッド特徴点グラフ生成部１２ａは、「レベル１」の特徴点集合を形成する特徴点ごとに、座標データに基づいて、所定の距離内にある他の特徴点を検索し、検索された特徴点との類似度を算出する。なお、「レベル１」において、類似度算出対象を検索するために用いられる距離（距離１）は、「レベル０」において用いられた距離（距離０）とは異なる値（例えば、「距離１＝２×距離０」）が設定される。
【００３６】
例えば、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ１に対しては「特徴点Ａ４および特徴点Ａ５」が「距離１」内にあることから、図３に示すように、特徴点Ａ１と特徴点Ａ４との類似度として、「ＦＡ１（１）」と「ＦＡ４（１）」とを比較することで、「ＳＡ１−４（１）」を算出し、特徴点Ａ１と特徴点Ａ５との類似度として、「ＦＡ１（１）」と「ＦＡ５（１）」とを比較することで、「ＳＡ１−５（１）」を算出する。
【００３７】
以下、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ４に対しては「特徴点Ａ１および特徴点Ａ５」が、特徴点Ａ５に対しては「特徴点Ａ１および特徴点Ａ４」が、特徴点Ａ９に対しては「特徴点Ａ５」が、「距離１」内にあることから、特徴点Ａ４、特徴点Ａ５および特徴点Ａ９それぞれにおいても、図３に示すように、レベル１における特徴量に基づいて、類似度を算出する。
【００３８】
そして、ピラミッド特徴点グラフ生成部１２ａは、「レベル１」の特徴点集合を形成する特徴点すべての中から任意に代表特徴点を選択する。例えば、ピラミッド特徴点グラフ生成部１２ａは、図３に示すように、特徴点Ａ１と、特徴点Ａ５と、特徴点Ａ９とを代表特徴点として選択する。
【００３９】
そして、ピラミッド特徴点グラフ生成部１２ａは、選択された代表特徴点それぞれにおいて、代表特徴点との類似度が算出されている特徴点の中で、所定の閾値以上の類似度となる類似度を検索し、検索された類似度と代表特徴点とを、「レベル１」の特徴点集合における部分集合として分類する。なお、「レベル１」において、部分集合を分類するために用いられる閾値（閾値１）は、「レベル０」において用いられた閾値（閾値０）とは異なる値（例えば、「閾値１＝閾値０÷２」）が設定される。
【００４０】
例えば、ピラミッド特徴点グラフ生成部１２ａは、図３に示すように、特徴点Ａ１に対応付けられている類似度「ＳＡ１−４（１）およびＳＡ１−５（１）」を参照して、「ＳＡ１−４（１）」のみが「閾値１」以上であることから、特徴点Ａ１が代表特徴点である部分集合を、「特徴点Ａ１および特徴点Ａ４」とする。また、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ５に対応付けられている類似度「ＳＡ１−５（１）、ＳＡ４−５（１）」を参照して、すべてが、「閾値１」より小さいことから、特徴点Ａ５が代表特徴点である部分集合を「特徴点Ａ５」とする。
【００４１】
以下、同様に、特徴点Ａ９が代表特徴点である部分集合を「特徴点Ａ９」として、ピラミッド特徴点グラフ生成部１２ａは、「レベル１」の特徴点集合を、特徴点間の距離および特徴点間の類似度に基づいて、３つの部分集合に分類する。
【００４２】
そして、ピラミッド特徴点グラフ生成部１２ａは、「レベル１」の特徴点集合にて分類された各部分集合における代表特徴点の集合を、「レベル２」の特徴点集合とする。例えば、ピラミッド特徴点グラフ生成部１２ａは、図４に示すように、レベル１の４個の特徴点それぞれが、レベル２の特徴点集合を形成する代表特徴点である特徴点Ａ１、特徴点Ａ５、特徴点Ａ９のいずれかにリンクされた階層構造を生成する。
【００４３】
なお、階層構造を示す情報として、ピラミッド特徴点グラフ生成部１２ａは、図４に示すように、「レベル２の特徴点Ａ１」は「レベル１の特徴点Ａ１および特徴点Ａ４」とリンクされるとするリンク情報を生成し、「レベル２の特徴点Ａ５」は「レベル１の特徴点Ａ５」とリンクされるとするリンク情報を生成し、「レベル２の特徴点Ａ９」は「レベル１の特徴点Ａ９」とリンクされるとするリンク情報を生成する。
【００４４】
そして、ピラミッド特徴点グラフ生成部１２ａは、上述した「レベル０」および「レベル１」における処理を、「レベル２」においても実行する。
【００４５】
すなわち、ピラミッド特徴点グラフ生成部１２ａは、「レベル２」の特徴点集合を形成する代表特徴点である特徴点の特徴量を、再度、算出する。
【００４６】
例えば、ピラミッド特徴点グラフ生成部１２ａは、「レベル２」の特徴点Ａ１の特徴量「ＦＡ１（２）」を、図４に示すように、リンク情報を参照して、レベル１にてリンクされている『特徴点Ａ１の特徴量「ＦＡ１（１）」および特徴点Ａ４の特徴量「ＦＡ４（１）」』の平均値として算出する。
【００４７】
また、ピラミッド特徴点グラフ生成部１２ａは、図４に示すように、リンク情報を参照して、「レベル１」の特徴点Ａ５の特徴量「ＦＡ５（１）」をそのまま「レベル２」の特徴点Ａ５の特徴量「ＦＡ５（２）」として採用する。同様に、ピラミッド特徴点グラフ生成部１２ａは、「レベル１」の特徴点Ａ９の特徴量「ＦＡ９（１）」をそのまま「レベル２」の特徴点Ａ９の特徴量「ＦＡ９（２）」として採用する。
【００４８】
そして、ピラミッド特徴点グラフ生成部１２ａは、「レベル２」の特徴点集合を形成する特徴点ごとに、座標データに基づいて、所定の距離内にある他の特徴点を検索し、検索された特徴点との類似度を算出する。なお、「レベル２」において、類似度算出対象を検索するために用いられる距離（距離２）は、「レベル１」において用いられた距離（距離１）とは異なる値（例えば、「距離２＝２×距離１」）が設定される。
【００４９】
例えば、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ１に対しては「特徴点Ａ５」が「距離２」内にあることから、図４に示すように、特徴点Ａ１と特徴点Ａ５との類似度として、「ＦＡ１（２）」と「ＦＡ５（２）」とを比較することで、「ＳＡ１−５（２）」を算出する。
【００５０】
以下、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ５に対しては「特徴点Ａ１および特徴点Ａ９」が、特徴点Ａ９に対しては「特徴点Ａ５」が、特徴点Ａ９に対しては「特徴点Ａ５」が、「距離２」内にあることから、特徴点Ａ５および特徴点Ａ９それぞれにおいても、図４に示すように、レベル２における特徴量に基づいて、類似度を算出する。
【００５１】
そして、ピラミッド特徴点グラフ生成部１２ａは、「レベル２」の特徴点集合を形成する特徴点すべての中から任意に代表特徴点を選択する。例えば、ピラミッド特徴点グラフ生成部１２ａは、図４に示すように、特徴点Ａ１と、特徴点Ａ９とを代表特徴点として選択する。
【００５２】
そして、ピラミッド特徴点グラフ生成部１２ａは、選択された代表特徴点それぞれにおいて、代表特徴点との類似度が算出されている特徴点の中で、所定の閾値以上の類似度となる類似度を検索し、検索された類似度と代表特徴点とを、「レベル２」の特徴点集合における部分集合として分類する。なお、「レベル２」において、部分集合を分類するために用いられる閾値（閾値２）は、「レベル１」において用いられた閾値（閾値１）とは異なる値（例えば、「閾値２＝閾値１÷２」）が設定される。
【００５３】
例えば、ピラミッド特徴点グラフ生成部１２ａは、図４に示すように、特徴点Ａ１に対応付けられている類似度「ＳＡ１−５（２）」が「閾値２」以上であることから、特徴点Ａ１が代表特徴点である部分集合を、「特徴点Ａ１および特徴点Ａ５」とする。また、ピラミッド特徴点グラフ生成部１２ａは、特徴点Ａ９に対応付けられている類似度「ＳＡ５−９（２）」が、「閾値２」より小さいことから、特徴点Ａ９が代表特徴点である部分集合を「特徴点Ａ９」とする。
【００５４】
これにより、ピラミッド特徴点グラフ生成部１２ａは、「レベル２」の特徴点集合を、特徴点間の距離および特徴点間の類似度に基づいて、２つの部分集合に分類する。
【００５５】
そして、ピラミッド特徴点グラフ生成部１２ａは、「レベル２」の特徴点集合にて分類された各部分集合における代表特徴点の集合を、「レベル３」の特徴点集合とする。例えば、ピラミッド特徴点グラフ生成部１２ａは、図５に示すように、レベル２の３個の特徴点それぞれが、レベル３の特徴点集合を形成する代表特徴点である特徴点Ａ１、特徴点Ａ９のいずれかにリンクされた階層構造を生成する。
【００５６】
なお、階層構造を示す情報として、ピラミッド特徴点グラフ生成部１２ａは、図５に示すように、「レベル３の特徴点Ａ１」は「レベル２の特徴点Ａ１および特徴点Ａ５」とリンクされるとするリンク情報を生成し、「レベル３の特徴点Ａ９」は「レベル２の特徴点Ａ９」とリンクされるとするリンク情報を生成する。
【００５７】
ここで、ピラミッド特徴点グラフ生成部１２ａは、レベル３の特徴点集合を形成することで、４階層にわたるピラミッド特徴点グラフを生成したので、「レベル３」の特徴点集合を形成する代表特徴点である特徴点の特徴量を、再度、算出して、画像Ａに対する処理を終了する。
【００５８】
そして、ピラミッド特徴点グラフ生成部１２ａは、原画像としての画像Ａにおいて抽出したレベル０の特徴点それそれが、レベル１およびレベル２の特徴点とされた代表特徴点のいずれかに連結され、最終的に、最上位階層であるレベル３の特徴点とされた代表特徴点のいずれかに集約して連結された構造となるピラミッド特徴点グラフを、各レベルの特徴点情報として、各レベルにおける特徴点が「特徴点ＩＤ、座標、特徴量、リンク情報」と対応付けられたテーブルとともに、ピラミッド特徴点グラフ記憶部１１ｂに格納する。
【００５９】
具体的には、ピラミッド特徴点グラフ記憶部１１ｂは、図６に示すように、画像Ａのピラミッド特徴点グラフを、各レベルの特徴点情報とともに記憶する。
【００６０】
また、ピラミッド特徴点グラフ生成部１２ａは、画像記憶部１１ａに、新たな画像データが格納されると、新たに格納された画像データに対しても同様に、上記したピラミッド特徴点グラフ生成処理を実行する。
【００６１】
例えば、画像Ａの撮影から一定時間経過後にカメラ２０によって撮影された画像Ｂの画像データが、画像記憶部１１ａに新たに格納された場合、ピラミッド特徴点グラフ生成部１２ａは、画像Ｂに対して同様に、上記したピラミッド特徴点グラフ生成処理を実行し、ピラミッド特徴点グラフ記憶部１１ｂは、図７に示すように、生成された画像Ｂのピラミッド特徴点グラフを、各レベルの特徴点情報とともに記憶する。
【００６２】
ここで、図７に示す画像Ｂのピラミッド特徴点グラフは、図６に示す画像Ａのピラミッド特徴点グラフと同様のリンク構造からなり、特徴点情報におけるリンク情報に付与された重み付けの情報も同じ値からなるが、座標および特徴量に関しては、異なる値となっている。
【００６３】
図１に戻って、マッチングリスト生成部１２ｂは、対応付けの対象となる２つの画像の間で対応付けを行なう際に、ピラミッド特徴点グラフ生成部１２ａによって生成された２つの画像に対応するピラミッド特徴点グラフの最上位階層（レベル３）それぞれの代表特徴点としての特徴点すべての間で類似度を算出してマッチングリストを生成し、特徴点間の対応付けを行なう。
【００６４】
そして、マッチングリスト生成部１２ｂは、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出してマッチングリストを生成し、特徴点間の対応付けを行なう階層間対応付け処理を、最上位階層の直下にある階層（レベル２）から順に繰り返すことにより、２つの画像それぞれの最下位階層（レベル０）の特徴点集合に含まれる複数の特徴点の間を対応付け、その結果をマッチンリスト記憶部１１ｃに格納する。
【００６５】
マッチングリスト生成部１２ｂの具体的な処理について、図８〜１２を用いて説明する。図８は、マッチングリスト生成部のレベル３マッチングリスト生成処理を説明するための図であり、図９は、マッチングリスト生成部のレベル２マッチングリスト生成処理を説明するための図であり、図１０は、マッチングリスト生成部のレベル１マッチングリスト生成処理を説明するための図であり、図１１は、マッチングリスト生成部のレベル０マッチングリスト生成処理を説明するための図であり、図１２は、マッチングリスト生成部が生成したレベル０マッチングリストを説明するための図である。
【００６６】
まず、マッチングリスト生成部１２ｂは、図８に示すように、図６に示す画像Ａのピラミッド特徴点グラフにおけるレベル３の特徴点である「特徴点Ａ１および特徴点Ａ９」と、図７に示す画像Ｂのピラミッド特徴点グラフにおけるレベル３の特徴点である「特徴点Ｂ１および特徴点Ｂ９」との間で、総当りでの照合を行なう（レベル３での照合）。
【００６７】
すなわち、マッチングリスト生成部１２ｂは、図８に示すように、特徴点Ａ１と特徴点Ｂ１との類似度「Ｓ（Ａ１Ｂ１）」を、特徴点Ａ１の特徴量「ＦＡ１（３）」と特徴点Ｂ１の特徴量「ＦＢ１（３）」とを比較することにより算出する。また、マッチングリスト生成部１２ｂは、図８に示すように、特徴点Ａ１と特徴点Ｂ９との類似度「Ｓ（Ａ１Ｂ９）」を、特徴点Ａ１の特徴量「ＦＡ１（３）」と特徴点Ｂ９の特徴量「ＦＢ９（３）」とを比較することにより算出する。以下、同様に、特徴点Ａ９と特徴点Ｂ１との類似度「Ｓ（Ａ９Ｂ１）」、および特徴点Ａ９と特徴点Ｂ９との類似度「Ｓ（Ａ９Ｂ９）」も算出する。
【００６８】
そして、マッチングリスト生成部１２ｂは、図８に示すように、算出した類似度の値が高い順に並べ替えたレベル３マッチングリストを生成する。ここで、マッチングリスト生成部１２ｂは、レベル３マッチングリストの中で、類似度の値が高い上位２つの組み合わせ「特徴点Ａ１−特徴点Ｂ１」と「特徴点Ａ９−特徴点Ｂ９」とを、レベル３における特徴点間の対応付け結果とする。
【００６９】
そして、マッチングリスト生成部１２ｂは、レベル３の直下にあるレベル２において、レベル３にて対応付けられた特徴点それぞれが代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、レベル３にて対応付けられた代表特徴点間の類似度に基づく類似度を算出してマッチングリストを生成し、特徴点間の対応付けを行なう。
【００７０】
具体的には、マッチングリスト生成部１２ｂは、図９に示すように、レベル３のマッチングリストと、ピラミッド特徴点グラフ記憶部１１ｂにおいてピラミッド特徴点グラフとともに記憶されている画像Ａおよび画像Ｂの特徴点情報にあるリンク情報を参照して、レベル２での照合を行なう。
【００７１】
すなわち、マッチングリスト生成部１２ｂは、図９に示すように、レベル３の組み合わせ「特徴点Ａ１−特徴点Ｂ１」は、レベル２においては「（特徴点Ａ１，特徴点Ａ５）−（特徴点Ｂ１，特徴点Ｂ５）」の組み合わせであるので、４つの組み合わせで類似度を算出する。
【００７２】
また、マッチングリスト生成部１２ｂは、図９に示すように、レベル３の組み合わせ「特徴点Ａ９−特徴点Ｂ９」は、レベル２においては「特徴点Ａ９−特徴点Ｂ９」の組み合わせであるので、１つの組み合わせで類似度を算出する。
【００７３】
ここで、マッチングリスト生成部１２ｂは、レベル２においては、レベル３にて対応付けられた代表特徴点間の類似度を反映した類似度を算出する。すなわち、マッチングリスト生成部１２ｂは、図９に示すように、レベル２における特徴点Ａ１と特徴点Ｂ１との類似度「Ｓ２（Ａ１Ｂ１）」を、『レベル２における特徴点Ａ１の特徴量「ＦＡ１（２）」と、レベル２における特徴点Ｂ１の特徴量「ＦＢ１（２）」とを比較して算出された類似度』に、レベル３にて算出された親類似度である「Ｓ（Ａ１Ｂ１）」を掛け合わせて算出する。同様に、マッチングリスト生成部１２ｂは、図９に示すように、レベル２における「Ｓ２（Ａ１Ｂ５）」、「Ｓ２（Ａ５Ｂ１）」および「Ｓ２（Ａ５Ｂ５）」を、レベル２での類似度に親類似度である「Ｓ（Ａ１Ｂ１）」を掛け合わせて算出する。
【００７４】
また、マッチングリスト生成部１２ｂは、図９に示すように、レベル２における特徴点Ａ９と特徴点Ｂ９との類似度「Ｓ２（Ａ９Ｂ９）」を、『レベル２における特徴点Ａ９の特徴量「ＦＡ９（２）」と、レベル２における特徴点Ｂ９の特徴量「ＦＢ９（２）」とを比較して算出された類似度』に、レベル３にて算出された親類似度である「Ｓ（Ａ９Ｂ９）」を掛け合わせて算出する。
【００７５】
そして、マッチングリスト生成部１２ｂは、図９に示すように、算出した類似度の値が高い順に並べ替えたレベル２マッチングリストを生成する。ここで、マッチングリスト生成部１２ｂは、レベル２マッチングリストの中で、類似度の値が高い上位３つの組み合わせ「特徴点Ａ１−特徴点Ｂ１」と「特徴点Ａ９−特徴点Ｂ９」と「特徴点Ａ５−特徴点Ｂ５」とを、レベル２における特徴点間の対応付け結果とする。
【００７６】
そして、マッチングリスト生成部１２ｂは、レベル２の直下にあるレベル１において、レベル２にて対応付けられた特徴点それぞれが代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、レベル２にて対応付けられた代表特徴点間の類似度（親類似度）に基づく類似度を算出してマッチングリストを生成し、特徴点間の対応付けを行なう。
【００７７】
具体的には、マッチングリスト生成部１２ｂは、図１０に示すように、レベル２のマッチングリストと、ピラミッド特徴点グラフ記憶部１１ｂにおいてピラミッド特徴点グラフとともに記憶されている画像Ａおよび画像Ｂの特徴点情報にあるリンク情報を参照して、レベル１での照合を行なう。
【００７８】
すなわち、マッチングリスト生成部１２ｂは、図１０に示すように、レベル２の組み合わせ「特徴点Ａ１−特徴点Ｂ１」は、レベル１においては「（特徴点Ａ１，特徴点Ａ４）−（特徴点Ｂ１，特徴点Ｂ４）」の組み合わせであるので、４つの組み合わせで類似度を算出する。
【００７９】
また、マッチングリスト生成部１２ｂは、図１０に示すように、レベル２の組み合わせ「特徴点Ａ９−特徴点Ｂ９」は、レベル１においては「特徴点Ａ９−特徴点Ｂ９」の組み合わせであるので、１つの組み合わせで類似度を算出する。
【００８０】
また、マッチングリスト生成部１２ｂは、図１０に示すように、レベル２の組み合わせ「特徴点Ａ５−特徴点Ｂ５」は、レベル１においては「特徴点Ａ５−特徴点Ｂ５」の組み合わせであるので、１つの組み合わせで類似度を算出する。
【００８１】
ここで、マッチングリスト生成部１２ｂは、レベル１においては、レベル２にて対応付けられた代表特徴点間の類似度を反映した類似度を算出する。すなわち、マッチングリスト生成部１２ｂは、図１０に示すように、レベル１における特徴点Ａ１と特徴点Ｂ１との類似度「Ｓ１（Ａ１Ｂ１）」を、『レベル１における特徴点Ａ１の特徴量「ＦＡ１（１）」と、レベル１における特徴点Ｂ１の特徴量「ＦＢ１（１）」とを比較して算出された類似度』に、レベル２にて算出された親類似度である「Ｓ２（Ａ１Ｂ１）」を掛け合わせて算出する。同様に、マッチングリスト生成部１２ｂは、図１０に示すように、レベル１における「Ｓ１（Ａ１Ｂ４）」、「Ｓ１（Ａ４Ｂ１）」および「Ｓ１（Ａ４Ｂ４）」を、レベル１での類似度に親類似度である「Ｓ２（Ａ１Ｂ１）」を掛け合わせて算出する。
【００８２】
また、マッチングリスト生成部１２ｂは、図１０に示すように、レベル１における特徴点Ａ９と特徴点Ｂ９との類似度「Ｓ１（Ａ９Ｂ９）」を、『レベル１における特徴点Ａ９の特徴量「ＦＡ９（１）」と、レベル１における特徴点Ｂ９の特徴量「ＦＢ９（１）」とを比較して算出された類似度』に、レベル２にて算出された親類似度である「Ｓ２（Ａ９Ｂ９）」を掛け合わせて算出する。
【００８３】
また、マッチングリスト生成部１２ｂは、図１０に示すように、レベル１における特徴点Ａ５と特徴点Ｂ５との類似度「Ｓ１（Ａ５Ｂ５）」を、『レベル１における特徴点Ａ５の特徴量「ＦＡ５（１）」と、レベル１における特徴点Ｂ９の特徴量「ＦＢ５（１）」とを比較して算出された類似度』に、レベル２にて算出された親類似度である「Ｓ２（Ａ５Ｂ５）」を掛け合わせて算出する。
【００８４】
そして、マッチングリスト生成部１２ｂは、図１０に示すように、算出した類似度の値が高い順に並べ替えたレベル１マッチングリストを生成する。ここで、マッチングリスト生成部１２ｂは、レベル１マッチングリストの中で、類似度の値が高い上位４つの組み合わせ「特徴点Ａ１−特徴点Ｂ１」と「特徴点Ａ９−特徴点Ｂ９」と「特徴点Ａ４−特徴点Ｂ４」と「特徴点Ａ５−特徴点Ｂ５」とを、レベル１における特徴点間の対応付け結果とする。
【００８５】
そして、マッチングリスト生成部１２ｂは、レベル１の直下にあるレベル０において、レベル１にて対応付けられた特徴点それぞれが代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、レベル１にて対応付けられた代表特徴点間の類似度（親類似度）に基づく類似度を算出してマッチングリストを生成し、特徴点間の対応付けを行なう。ここで、レベル０における特徴点間の対応付け結果が、最終的な、画像Ａと画像Ｂとの対応付けの結果となる。
【００８６】
具体的には、マッチングリスト生成部１２ｂは、図１１に示すように、レベル１のマッチングリストと、ピラミッド特徴点グラフ記憶部１１ｂにおいてピラミッド特徴点グラフとともに記憶されている画像Ａおよび画像Ｂの特徴点情報にあるリンク情報を参照して、レベル０での照合を行なう。
【００８７】
すなわち、マッチングリスト生成部１２ｂは、図１１に示すように、レベル１の組み合わせ「特徴点Ａ１−特徴点Ｂ１」は、レベル０においては「（特徴点Ａ１，特徴点Ａ２）−（特徴点Ｂ１，特徴点Ｂ２）」の組み合わせであるので、４つの組み合わせで類似度を算出する。
【００８８】
また、マッチングリスト生成部１２ｂは、図１１に示すように、レベル１の組み合わせ「特徴点Ａ９−特徴点Ｂ９」は、レベル０においては「（特徴点Ａ７，特徴点Ａ８，特徴点Ａ９）−（特徴点Ｂ７，特徴点Ｂ８，特徴点Ｂ９）」の組み合わせであるので、９つの組み合わせで類似度を算出する。
【００８９】
また、マッチングリスト生成部１２ｂは、図１１に示すように、レベル１の組み合わせ「特徴点Ａ４−特徴点Ｂ４」は、レベル０においては「（特徴点Ａ２，特徴点Ａ３，特徴点Ａ４）−（特徴点Ｂ２，特徴点Ｂ３，特徴点Ｂ４）」の組み合わせであるので、９つの組み合わせで類似度を算出する。
【００９０】
また、マッチングリスト生成部１２ｂは、図１１に示すように、レベル１の組み合わせ「特徴点Ａ５−特徴点Ｂ５」は、レベル０においては「（特徴点Ａ５，特徴点Ａ６）−（特徴点Ｂ５，特徴点Ｂ６）」の組み合わせであるので、４つの組み合わせで類似度を算出する。
【００９１】
ここで、マッチングリスト生成部１２ｂは、レベル０においては、レベル１にて対応付けられた代表特徴点間の類似度を反映した類似度を算出する。
【００９２】
すなわち、マッチングリスト生成部１２ｂは、図１１に示すように、レベル０における『特徴点Ａ１と特徴点Ｂ１との類似度「Ｓ０（Ａ１Ｂ１）」』と『特徴点Ａ１と特徴点Ｂ２との類似度「Ｓ０（Ａ１Ｂ２）」』と『特徴点Ａ２と特徴点Ｂ１との類似度「Ｓ０（Ａ２Ｂ１）」』と『特徴点Ａ２と特徴点Ｂ２との類似度「Ｓ０（Ａ２Ｂ２）」』とを、各特徴点のレベル０における特徴量間の類似度に、レベル１にて算出された親類似度である「Ｓ１（Ａ１Ｂ１）」を掛け合わせて算出する。
【００９３】
また、マッチングリスト生成部１２ｂは、図１１に示すように、レベル０における『特徴点Ａ７と特徴点Ｂ７との類似度「Ｓ０（Ａ７Ｂ７）」』と『特徴点Ａ７と特徴点Ｂ８との類似度「Ｓ０（Ａ７Ｂ８）」』と『特徴点Ａ７と特徴点Ｂ９との類似度「Ｓ０（Ａ７Ｂ９）」』と『特徴点Ａ８と特徴点Ｂ７との類似度「Ｓ０（Ａ８Ｂ７）」』と『特徴点Ａ８と特徴点Ｂ８との類似度「Ｓ０（Ａ８Ｂ８）」』と『特徴点Ａ８と特徴点Ｂ９との類似度「Ｓ０（Ａ８Ｂ９）」』と『特徴点Ａ９と特徴点Ｂ７との類似度「Ｓ０（Ａ９Ｂ７）」』と『特徴点Ａ９と特徴点Ｂ８との類似度「Ｓ０（Ａ９Ｂ８）」』と『特徴点Ａ９と特徴点Ｂ９との類似度「Ｓ０（Ａ９Ｂ９）」』とを、各特徴点のレベル０における特徴量間の類似度に、レベル１にて算出された親類似度である「Ｓ１（Ａ９Ｂ９）」を掛け合わせて算出する。
【００９４】
また、マッチングリスト生成部１２ｂは、図１１に示すように、レベル０における『特徴点Ａ２と特徴点Ｂ２との類似度「Ｓ’０（Ａ２Ｂ２）」』と『特徴点Ａ２と特徴点Ｂ３との類似度「Ｓ０（Ａ２Ｂ３）」』と『特徴点Ａ２と特徴点Ｂ４との類似度「Ｓ０（Ａ２Ｂ４）」』と『特徴点Ａ３と特徴点Ｂ２との類似度「Ｓ０（Ａ３Ｂ２）」』と『特徴点Ａ３と特徴点Ｂ３との類似度「Ｓ０（Ａ３Ｂ３）」』と『特徴点Ａ３と特徴点Ｂ４との類似度「Ｓ０（Ａ３Ｂ４）」』と『特徴点Ａ４と特徴点Ｂ２との類似度「Ｓ０（Ａ４Ｂ２）」』と『特徴点Ａ４と特徴点Ｂ３との類似度「Ｓ０（Ａ４Ｂ３）」』と『特徴点Ａ４と特徴点Ｂ４との類似度「Ｓ０（Ａ４Ｂ４）」』とを、各特徴点のレベル０における特徴量間の類似度に、レベル１にて算出された親類似度である「Ｓ１（Ａ４Ｂ４）」を掛け合わせて算出する。
【００９５】
また、マッチングリスト生成部１２ｂは、図１１に示すように、レベル０における『特徴点Ａ５と特徴点Ｂ５との類似度「Ｓ０（Ａ５Ｂ５）」』と『特徴点Ａ５と特徴点Ｂ６との類似度「Ｓ０（Ａ５Ｂ６）」』と『特徴点Ａ６と特徴点Ｂ５との類似度「Ｓ０（Ａ６Ｂ５）」』と『特徴点Ａ６と特徴点Ｂ６との類似度「Ｓ０（Ａ６Ｂ６）」』とを、各特徴点のレベル０における特徴量間の類似度に、レベル１にて算出された親類似度である「Ｓ１（Ａ５Ｂ５）」を掛け合わせて算出する。
【００９６】
なお、画像Ａの特徴点Ａ２は、レベル１の代表特徴点としての特徴点Ａ１および特徴点Ａ４の両方にリンクされ、また、画像Ｂの特徴点Ｂ２は、レベル１の代表特徴点としての特徴点Ｂ１および特徴点Ｂ４の両方にリンクされているために、レベル０における特徴点Ａ２と特徴点Ｂ２との類似度は、「Ｓ０（Ａ２Ｂ２）」と「Ｓ’０（Ａ２Ｂ２）」との２種類算出され、「Ｓ０（Ａ２Ｂ２）」と「Ｓ’０（Ａ２Ｂ２）」とを足し合わせた値が、レベル０における特徴点Ａ２と特徴点Ｂ２との最終的な類似度として算出される。
【００９７】
そして、マッチングリスト生成部１２ｂは、図１２に示すように、算出した類似度の値が高い順に並べ替えたレベル０マッチングリストを生成する。ここで、マッチングリスト生成部１２ｂは、レベル０マッチングリストの中で、類似度の値が高い上位９つの組み合わせである「特徴点Ａ１−特徴点Ｂ１」〜「特徴点Ａ９−特徴点Ｂ９」を、レベル０における特徴点間の対応付け結果、すなわち、最終的な画像Ａと画像Ｂとの対応付けの結果とし、レベル０マッチングリストをマッチングリスト記憶部１１ｃに格納する。
【００９８】
推定部１２ｃは、マッチングリスト記憶部１１ｃが記憶するレベル０のマッチングリストを参照して、画像マッチング装置１０が搭載される歩行型ロボットの移動量および移動方向を推定し、カメラコントローラ１２ｄは、推定部１２ｃによって推定された移動量および移動方向に基づいて、カメラ２０のレンズの方向を、歩行型ロボットの移動方向に対して正対するように移動させる。
【００９９】
なお、本実施例では、最上位階層がレベル３であるピラミッド特徴点グラフを生成する場合について説明したが、本発明はこれに限定されるものではなく、例えば、最上位階層がレベル５であるピラミッド特徴点グラフを生成する場合など、最上位階層のレベル数は、任意に設定されるものである。
【０１００】
［実施例１における画像マッチング装置による処理の手順］
次に、図１３を用いて、実施例１における画像マッチング装置１０による処理を説明する。図１３は、実施例１における画像マッチング装置の処理を説明するためのフローチャートである。
【０１０１】
まず、実施例１における画像マッチング装置１０は、対応付けの対象となる新規画像の画像データが、画像記憶部１１ａに格納されると（ステップＳ１３０１肯定）、ピラミッド特徴点グラフ生成部１２ａは、新規画像の画像データから特徴点を抽出して、ピラミッド特徴点グラフを生成する（ステップＳ１３０２）。例えば、画像Ｂの画像データが、画像記憶部１１ａに格納されると、ピラミッド特徴点グラフ生成部１２ａは、画像Ｂの画像データから特徴点を抽出して、図７に示すように、ピラミッド特徴点グラフを生成する。
【０１０２】
そして、マッチングリスト生成部１２ｂは、すでにピラミッド特徴点グラフ記憶部１１ｂにおいて記憶されている画像（画像Ａ）のピラミッド特徴点グラフ（図６参照）と、新規にピラミッド特徴点グラフ記憶部１１ｂにおいて記憶された画像（画像Ｂ）のピラミッド特徴点グラフとの最上位レベル（レベル３）のマッチングリストを、総当りの照合により生成する（ステップＳ１３０３）。
【０１０３】
ここで、マッチングリスト生成部１２ｂは、最下位レベルのマッチングリストが生成されたか否かを判定し（ステップＳ１３０４）、最下位レベルのマッチングリストが生成されていない場合（ステップＳ１３０４否定）、次の下位レベルのマッチングリストを生成する（ステップＳ１３０５）。なお、最上位レベル以外のレベルでは、上述したように、上位レベルにて対応付けられた特徴点それぞれが、当該レベルにおいて代表特徴点となる部分集合それぞれの中でのみ照合を行なって、マッチングリストを、具体的には、レベル２、レベル１のマッチングリストを順次生成する。
【０１０４】
これに反して、最下位レベル（レベル０）のマッチングリストが生成された場合（ステップＳ１３０４肯定）、マッチングリスト生成部１２ｂは、画像間のマッチング（対応付け）が終了したと判断して（ステップＳ１３０６）、処理を終了する。なお、こののちは、推定部１２ｃによる、移動量および移動方向の推定と、カメラコントローラ１２ｄによるカメラ方向の移動制御が行なわれる。
【０１０５】
［実施例１の効果］
上記したように、実施例１によれば、ピラミッド特徴点グラフ生成部１２ａは、画像記憶部１１ａが記憶する画像データから抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、最下位階層の特徴点集合から順に、所定の設定回数にわたり繰り返すことにより、複数の特徴点それぞれが、上位階層ごとの代表特徴点いずれかに連結されて最上位階層の代表特徴点いずれかに集約して連結されるピラミッド型の階層構造であるピラミッド特徴点グラフを、対応付けの対象となる画像ごとに生成し、マッチングリスト生成部１２ｂは、対応付けの対象となる２つの画像の間で対応付けを行なう際に、ピラミッド特徴点グラフ生成部１２ａによって生成された２つの画像に対応するピラミッド特徴点グラフの最上位階層それぞれの代表特徴点としての特徴点すべての間で類似度を算出してマッチングリストを生成し、特徴点間の対応付けを行なう。
【０１０６】
そして、マッチングリスト生成部１２ｂは、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出してマッチングリストを生成し、特徴点間の対応付けを行なう階層間対応付け処理を、最上位階層の直下にある階層から順に繰り返すことにより、２つの画像それぞれの最下位階層（レベル０）の特徴点集合に含まれる複数の特徴点の間を対応付けるので、ピラミッド特徴点グラフを生成することで比較する特徴点の数を絞り込み、最上位階層から順に大まかな対応付けを行なって、最終的に最下位階層の特徴点を対応付けるので、特徴点の総当りによる比較を行う必要がなく、画像間の対応付けを迅速に行なうことが可能となる。
【実施例２】
【０１０７】
上述した実施例１では、ピラミッド特徴点グラフの最上位階層から順に類似度を算出して、一度に最下位階層における特徴点間の対応付けを行なう場合について説明したが、実施例２では、算出された類似度を用いて上位階層の類似度を更新する処理と、更新された上位階層に類似度を用いて下位階層におけるマッチングリストを更新する処理を繰り返すことにより、最下位階層における特徴点間の対応付けを行なう場合について説明する。
【０１０８】
［実施例２における画像マッチング装置の構成］
実施例２における画像マッチング装置１０は、図１に示す実施例１における画像マッチング装置１０と同様の機能ブロックからなるが、マッチングリスト生成部１２ｂの処理内容が、実施例１と異なる。以下、これを中心に説明する。
【０１０９】
実施例２におけるマッチングリスト生成部１２ｂは、最下位階層より上位にある階層において生成されたマッチングリストにより対応付けられた特徴点間の類似度を用いて当該階層の直上にある階層における特徴点間の類似度を更新するとともに、類似度が更新された下位階層の直上にある上位階層にて対応付けられている特徴点間の類似度を当該下位階層にて更新された特徴点間の類似度を用いて更新する類似度更新処理を行なう。
【０１１０】
そして、実施例２におけるマッチングリスト生成部１２ｂは、上位階層にて対応付けられている特徴点間の更新された類似度を用いて当該上位階層の直下にある下位階層におけるマッチングリストを更新して生成するマッチングリスト更新生成処理を行なうことにより、特徴点間の対応付けを更新する。
【０１１１】
そして、実施例２におけるマッチングリスト生成部１２ｂは、類似度更新処理とマッチングリスト更新生成処理とを繰り返して、２つの画像それぞれの最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付ける。
【０１１２】
例えば、実施例２におけるマッチングリスト生成部１２ｂは、図１４に示すように、レベル３から順に２回にわたってマッチングリストを生成して、レベル１マッチングリストを生成したのち、そのまま、レベル０のマッチングリストを生成するのではなく、レベル１マッチングリストの類似度を用いてレベル２マッチングリストの類似度を更新し、さらに、更新されたレベル２マッチングリストの類似度を用いてレベル３マッチングリストの類似度を更新する。すなわち、実施例２におけるマッチングリスト生成部１２ｂは、レベル１から順に２回にわたって類似度を更新する。
【０１１３】
そして、実施例２におけるマッチングリスト生成部１２ｂは、図１４に示すように、類似度が更新されたレベル３のマッチングリストを用いて、順に３回にわたってマッチングリストを更新して生成する。その結果、レベル０マッチングリストが更新生成されるので、画像間の対応付けを終了する。ここで、図１４は、実施例２における画像マッチング装置の概念を説明するための図である。
【０１１４】
上記した実施例２におけるマッチングリスト生成部１２ｂの具体的な処理について、図１５〜１７を用いて説明する。図１５は、実施例２において生成されたレベル２およびレベル１のマッチングリストを説明するための図であり、図１６は、実施例２におけるマッチングリスト生成部の類似度更新処理を説明するための図であり、図１７は、実施例２におけるマッチングリスト生成部のマッチングリスト更新処理を説明するための図である。
【０１１５】
例えば、図９にて示したレベル２マッチングリストとは異なり、実施例２においては、図１５に示すように、「特徴点Ａ９−特徴点Ｂ９」と「特徴点Ａ５−特徴点Ｂ５」と「特徴点Ａ１−特徴点Ｂ５」とが、レベル２における特徴点間の対応付け結果とするレベル２マッチングリストが生成されたとする。
【０１１６】
すると、実施例１と同様に、マッチングリスト生成部１２ｂは、図１５に示すように、レベル２のマッチングリストと、ピラミッド特徴点グラフ記憶部１１ｂにおいてピラミッド特徴点グラフとともに記憶されている画像Ａおよび画像Ｂの特徴点情報にあるリンク情報を参照して、レベル１での照合を行なう。
【０１１７】
すなわち、マッチングリスト生成部１２ｂは、図１５に示すように、レベル２の組み合わせ「特徴点Ａ９−特徴点Ｂ９」は、レベル１においては「特徴点Ａ９−特徴点Ｂ９」の組み合わせであるので、１つの組み合わせで類似度を算出する。
【０１１８】
また、マッチングリスト生成部１２ｂは、図１５に示すように、レベル２の組み合わせ「特徴点Ａ５−特徴点Ｂ５」は、レベル１においては「特徴点Ａ５−特徴点Ｂ５」の組み合わせであるので、１つの組み合わせで類似度を算出する。
【０１１９】
また、マッチングリスト生成部１２ｂは、図１５に示すように、レベル２の組み合わせ「特徴点Ａ１−特徴点Ｂ５」は、レベル１においては「（特徴点Ａ１，特徴点Ａ４）−（特徴点Ｂ５）」の組み合わせであるので、２つの組み合わせで類似度を算出する。
【０１２０】
なお、マッチングリスト生成部１２ｂは、図１５に示すように、レベル１における『特徴点Ａ９と特徴点Ｂ９との類似度「Ｓ１（Ａ９Ｂ９）」』を、各特徴点のレベル１における特徴量間の類似度に、レベル２にて算出された親類似度である「Ｓ２（Ａ９Ｂ９）」を掛け合わせて算出する。また、レベル１における『特徴点Ａ５と特徴点Ｂ５との類似度「Ｓ１（Ａ５Ｂ５）」』を、各特徴点のレベル１における特徴量間の類似度に、レベル２にて算出された親類似度である「Ｓ２（Ａ５Ｂ５）」を掛け合わせて算出する。
【０１２１】
また、マッチングリスト生成部１２ｂは、図１５に示すように、レベル１における『特徴点Ａ１と特徴点Ｂ５との類似度「Ｓ１（Ａ１Ｂ５）」』と『特徴点Ａ４と特徴点Ｂ５との類似度「Ｓ１（Ａ４Ｂ５）」』とを、各特徴点のレベル１における特徴量間の類似度に、レベル２にて算出された親類似度である「Ｓ２（Ａ１Ｂ５）」を掛け合わせて算出する。
【０１２２】
そして、マッチングリスト生成部１２ｂは、図１５に示すように、算出した類似度の値が高い順に並べ替えたレベル１マッチングリストを生成する。ここで、マッチングリスト生成部１２ｂは、レベル１マッチングリストの中で、類似度の値が高い上位４つの組み合わせ「特徴点Ａ９−特徴点Ｂ９」と「特徴点Ａ５−特徴点Ｂ５」と「特徴点Ａ１−特徴点Ｂ５」と「特徴点Ａ４−特徴点Ｂ５」とを、レベル１における特徴点間の対応付け結果とする。
【０１２３】
ここで、マッチングリスト生成部１２ｂは、実施例１とは異なり、上記した類似度更新処理を２回行なう。具体的には、まず、レベル１のマッチングリストにおける類似度を、レベル２のマッチングリストの類似度に反映させる。すなわち、マッチングリスト生成部１２ｂは、図１６の（Ａ）に示すように、レベル２にて算出されていた特徴点Ａ９と特徴点Ｂ９との類似度Ｓ２（Ａ９Ｂ９）を、レベル１にて算出された類似度Ｓ１（Ａ９Ｂ９）に更新し、レベル２にて算出されていた特徴点Ａ５と特徴点Ｂ５との類似度Ｓ２（Ａ５Ｂ５）を、レベル１にて算出された類似度Ｓ１（Ａ５Ｂ５）に更新する。
【０１２４】
さらに、マッチングリスト生成部１２ｂは、図１６の（Ａ）に示すように、レベル２にて算出されていた特徴点Ａ１と特徴点Ｂ５との類似度Ｓ２（Ａ１Ｂ５）を、レベル１にて算出された類似度Ｓ１（Ａ１Ｂ５）と類似度Ｓ１（Ａ４Ｂ５）とを掛け合わせた値に更新する。このように、マッチングリスト生成部１２ｂは、レベル２の特徴点間の類似度を、レベル２の特徴点が代表特徴点となっているレベル１における部分集合を形成する特徴点間で算出された類似度を用いて更新して算出する。
【０１２５】
そののち、マッチングリスト生成部１２ｂは、更新後類似度の値が高い順に、マッチングリストを再ソートする。これにより、レベル２マッチングリストにおいて、類似度の値が高い上位３つの組み合わせは、「特徴点Ａ９−特徴点Ｂ９」と「特徴点Ａ５−特徴点Ｂ５」と「特徴点Ａ１−特徴点Ｂ１」となる。
【０１２６】
続いて、マッチングリスト生成部１２ｂは、レベル２マッチングリストにおいて更新された類似度を、レベル３のマッチングリストの類似度に反映させる。すなわち、マッチングリスト生成部１２ｂは、図１６の（Ｂ）に示すように、レベル３にて算出されていた特徴点Ａ１と特徴点Ｂ１との類似度Ｓ（Ａ１Ｂ１）を、レベル２における更新後類似度である類似度Ｓ２（Ａ１Ｂ１）と類似度Ｓ１（Ａ５Ｂ５）とを掛け合わせた値に更新する。
【０１２７】
さらに、マッチングリスト生成部１２ｂは、図１６の（Ｂ）に示すように、レベル３にて算出されていた特徴点Ａ９と特徴点Ｂ９との類似度Ｓ（Ａ９Ｂ９）を、レベル２における更新後類似度であるＳ１（Ａ９Ｂ９）に更新する。
【０１２８】
そののち、マッチングリスト生成部１２ｂは、更新後類似度の値が高い順に、マッチングリストを再ソートする。これにより、レベル３マッチングリストにおいて、類似度の値が高い上位２つの組み合わせは、「特徴点Ａ１−特徴点Ｂ１」と「特徴点Ａ９−特徴点Ｂ９」とになる。なお、再ソート後のレベル３マッチングリストにおける上位２つの組み合わせは、再ソート前のレベル３マッチングリストにおける上位２つの組み合わせと同じとなっている。
【０１２９】
そして、マッチングリスト生成部１２ｂは、上記したマッチングリスト更新生成処理を３回行なう。まず、マッチングリスト生成部１２ｂは、図１７に示すように、「Ｓ２（Ａ１Ｂ１）×Ｓ１（Ａ５Ｂ５）」が、レベル３における特徴点Ａ１と特徴点Ｂ１との更新後類似度「Ｓ（Ａ１Ｂ１）」であり、「Ｓ１（Ａ９Ｂ９）」が、レベル３における特徴点Ａ９と特徴点Ｂ９との更新後類似度「Ｓ（Ａ９Ｂ９）」であるとして更新されたレベル３マッチングリストを用いて、レベル２マッチングリストを更新生成する。
【０１３０】
すなわち、マッチングリスト生成部１２ｂは、実施例１と同様に、レベル３のマッチングリストと、ピラミッド特徴点グラフ記憶部１１ｂにおいてピラミッド特徴点グラフとともに記憶されている画像Ａおよび画像Ｂの特徴点情報にあるリンク情報を参照して、図１７に示すように、レベル２における類似度である、「Ｓ２（Ａ１Ｂ１）」、「Ｓ２（Ａ９Ｂ９）」、「Ｓ２（Ａ５Ｂ５）」、「Ｓ２（Ａ１Ｂ５）」および「Ｓ２（Ａ５Ｂ１）」を、再度算出し、再度算出した類似度の値が高い順に並べ替えたレベル２マッチングリストを生成する。ここで、マッチングリスト生成部１２ｂは、レベル２マッチングリストの中で、類似度の値が高い上位３つの組み合わせ「特徴点Ａ１−特徴点Ｂ１」と「特徴点Ａ９−特徴点Ｂ９」と「特徴点Ａ５−特徴点Ｂ５」とを、レベル２における特徴点間の対応付け結果とする。
【０１３１】
こののち、マッチングリスト生成部１２ｂは、レベル２マッチングリストを用いたレベル１マッチングリストの更新生成およびレベル１マッチングリストを用いたレベル０マッチングリストの更新生成を行なって、画像間の対応付けを行なう。
【０１３２】
なお、本実施例においては、レベル０からレベル３からなるピラミッド特徴点グラフにおいて、レベル３から順に２回にわたってマッチングリストを生成し、レベル１マッチングリストの類似度を用いて、レベル１から順に２回にわたって類似度を更新し、類似度が更新されたレベル３のマッチングリストを用いて、順に３回にわたってマッチングリストを更新して生成することにより、レベル０マッチングリストを更新生成する場合について説明したが、本発明はこれに限定されるものではなく、マッチングリストの生成回数、類似度の更新回数およびマッチングリストの更新生成回数は、任意に変更して設定できるものである。これについて、図１８を用いて説明する。図１８は、実施例２における変形例を説明するための図である。
【０１３３】
例えば、図１８に示すように、レベル０からレベル５の構造からなるピラミッド特徴点グラフを用いて、まず、マッチングリスト生成部１２ｂは、レベル５から順に３回にわたってマッチングリストを生成する。
【０１３４】
そして、マッチングリスト生成部１２ｂは、生成されたレベル２マッチングリストの類似度を用いて、レベル２から順に３回にわたって類似度を更新し、類似度が更新されたレベル５のマッチングリストを用いて、順に４回にわたってマッチングリストを更新して生成する。
【０１３５】
続いて、マッチングリスト生成部１２ｂは、更新生成されたレベル１マッチングリストにおける類似度を用いて、レベル１から順に３回にわたって再度、類似度を更新し、類似度が更新されたレベル４のマッチングリストを用いて、順に再度４回にわたってマッチングリストを更新して生成する。これにより、レベル０マッチングリストが生成され、画像間の対応付けが終了する。
【０１３６】
［実施例２における画像マッチング装置による処理の手順］
次に、図１９を用いて、実施例２における画像マッチング装置１０による処理を説明する。図１９は、実施例２における画像マッチング装置の処理を説明するためのフローチャートである。
【０１３７】
まず、実施例２における画像マッチング装置１０は、対応付けの対象となる新規画像の画像データが、画像記憶部１１ａに格納されると（ステップＳ１９０１肯定）、ピラミッド特徴点グラフ生成部１２ａは、新規画像の画像データから特徴点を抽出して、ピラミッド特徴点グラフを生成する（ステップＳ１９０２）。
【０１３８】
そして、マッチングリスト生成部１２ｂは、すでにピラミッド特徴点グラフ記憶部１１ｂにおいて記憶されている画像のピラミッド特徴点グラフと、新規にピラミッド特徴点グラフ記憶部１１ｂにおいて記憶された画像のピラミッド特徴点グラフとの最上位レベル（レベル３）のマッチングリストを、総当りの照合により生成する（ステップＳ１９０３）。
【０１３９】
ここで、マッチングリスト生成部１２ｂは、設定回数分のマッチングリストが生成されたか否かを判定し（ステップＳ１９０４）、設定回数分のマッチングリストが生成されていない場合（ステップＳ１９０４否定）、次の下位レベルのマッチングリストを生成する（ステップＳ１９０５）。
【０１４０】
これに反して、設定回数分のマッチングリストが生成された場合（ステップＳ１９０４肯定）、マッチングリスト生成部１２ｂは、生成したマッチングリストの中で、最下位にあるマッチングリストの類似度を直上のマッチングリストに反映させて、マッチングリストの再ソートを行なう（ステップＳ１９０６）。
【０１４１】
ここで、マッチングリスト生成部１２ｂは、類似度を反映する類似度更新処理を、設定回数分行なったか否かを判定し（ステップＳ１９０７）、設定回数分の類似度更新処理が行なわれていない場合（ステップＳ１９０７否定）、次の上位レベルのマッチングリストに対して類似度を更新し（ステップＳ１９０８）、ステップＳ１９０７の判断を行なう。
【０１４２】
これに反して、設定回数分の類似度更新処理が行なわれた場合（ステップＳ１９０７肯定）、マッチングリスト生成部１２ｂは、類似度が更新されたマッチングリストの中で、最上位にあるマッチングリストから、直下のレベルのマッチングリストを更新生成する（ステップＳ１９０９）。
【０１４３】
そして、マッチングリスト生成部１２ｂは、最下位レベルのマッチングリストが生成されたか否かを判定し（ステップＳ１９１０）、最下位レベルのマッチングリストが生成されていない場合（ステップＳ１９１０否定）、マッチングリスト更新生成処理を設定回数分行なったか否かを判定する（ステップ１９１１）。
【０１４４】
マッチングリスト更新生成処理を設定回数分行なっていない場合（ステップＳ１９１１否定）、マッチングリスト生成部１２ｂは、次の下位レベルのマッチングリストを更新生成し（ステップＳ１９１２）、ステップＳ１９１０における判定処理に戻る。
【０１４５】
ここで、マッチングリスト更新生成処理を設定回数分行なった場合（ステップＳ１９１１肯定）、マッチングリスト生成部１２ｂは、再度、最下位レベルのマッチングリストが生成されたか否かを判定する（ステップＳ１９１３）。
【０１４６】
ステップＳ１９１３において、最下位レベルのマッチングリストが生成されていないと判定された場合（ステップＳ１９１３否定）、マッチングリスト生成部１２ｂは、再度、ステップＳ１９０６に戻って、再度、類似度更新処理を実行する。
【０１４７】
これに反して、ステップＳ１９１０、またはステップＳ１９１３において、最下位レベルのマッチングリストが生成されたと判断された場合（ステップＳ１９１０肯定、またはステップＳ１９１３肯定）、マッチングリスト生成部１２ｂは、画像間のマッチング（対応付け）が終了したと判断して（ステップＳ１９１４）、処理を終了する。なお、こののちは、推定部１２ｃによる、移動量および移動方向の推定と、カメラコントローラ１２ｄによるカメラ方向の移動制御が行なわれる。
【０１４８】
［実施例２の効果］
上記したように、実施例２によれば、マッチングリスト生成部１２ｂは、最下位階層より上位にある階層において生成されたマッチングリストにより対応付けられた特徴点間の類似度を用いて当該階層の直上にある階層における特徴点間の類似度を更新するとともに、類似度が更新された下位階層の直上にある上位階層にて対応付けられている特徴点間の類似度を当該下位階層にて更新された特徴点間の類似度を用いて更新する類似度更新処理を行なう。
【０１４９】
そして、マッチングリスト生成部１２ｂは、上位階層にて対応付けられている特徴点間の更新された類似度を用いて当該上位階層の直下にある下位階層におけるマッチングリストを更新して生成するマッチングリスト更新生成処理を行なうことにより、特徴点間の対応付けを更新する。そして、マッチングリスト生成部１２ｂは、類似度更新処理とマッチングリスト更新生成処理とを繰り返して、２つの画像それぞれの最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付けるので、下位階層の類似度を反映させることにより、上位階層において誤って対応付けられた代表特徴点の組み合わせを修正することができ、画像間の対応付けを精度よく行なうことが可能となる。
【実施例３】
【０１５０】
さて、これまで実施例１および２における画像マッチング装置について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてもよいものである。そこで、以下では、実施例３における画像マッチング装置として、種々の異なる実施例を（１）〜（２）に区分けして説明する。
【０１５１】
（１）対応付けの対象となる画像
上記の実施例１および２では、歩行型ロボットに搭載された１つのカメラ２０によって撮影された時系列に沿った２つの画像が、画像マッチング装置１０による対応付けの対象となる場合について説明したが、本発明はこれに限定されるものではなく、例えば、歩行型ロボットに搭載された左右２つのカメラ２０によって同時撮影された２つの画像が、画像マッチング装置１０による対応付けの対象となる場合であってもよい。この場合、対応付けられた２つの画像からステレオ画像が生成される。
【０１５２】
（２）システム構成等
また、上記の実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動でおこなうこともでき、あるいは、手動的におこなうものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文章中や図面中で示した処理手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に更新することができる。
【０１５３】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示された構成要素と同一であることを要しない。すなわち、各処理部および各記憶部の分散・統合の具体的形態（例えば、図１の形態など）は図示のものに限られず、例えば、ピラミッド特徴点グラフ生成部１２ａとマッチングリスト生成部１２ｂとを統合するなど、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１５４】
（３）画像間対応付けプログラム
ところで上記の実施例１では、ハードウェアロジックによって各種の処理を実現する場合を説明したが、本発明はこれに限定されるものではなく、あらかじめ用意されたプログラムをコンピュータで実行するようにしてもよい。そこで以下では、図２０を用いて、上記の実施例１に示した画像マッチング装置１０と同様の機能を有する画像間対応付けプログラムを実行するコンピュータの一例を説明する。図２０は、実施例１の画像間対応付けプログラムを実行するコンピュータを示す図である。
【０１５５】
図２０に示すように、情報処理装置としてのコンピュータ２００は、キーボード２０１、ディスプレイ２０２、ＣＰＵ２０３、ＲＯＭ２０４、ＨＤＤ２０５、ＲＡＭ２０６を有し、カメラ２０と接続される。なお、キーボード２０１、ディスプレイ２０２、ＣＰＵ２０３、ＲＯＭ２０４、ＨＤＤ２０５、ＲＡＭ２０６およびカメラ２０は、バス２０７などで接続される。
【０１５６】
ＲＯＭ２０４には、上記の実施例１に示した画像マッチング装置１０と同様の機能を発揮する画像間対応付けプログラム、つまり、図２０に示すように、ピラミッド特徴点グラフ生成プログラム２０４ａ、マッチングリスト生成プログラム２０４ｂ、推定プログラム２０４ｃ、カメラコントロールプログラム２０４ｄが予め記憶されている。なお、これらのプログラム２０４ａ〜２０４ｄについては、図１に示した画像マッチング装置１０の各構成要素と同様、適宜統合または分散してもよい。
【０１５７】
そして、ＣＰＵ２０３が、これらのプログラム２０４ａ〜２０４ｄをＲＯＭ２０４から読みだして実行することで、図２０に示すように、各プログラム２０４ａ〜２０４ｄは、ピラミッド特徴点グラフ生成プロセス２０３ａ、マッチングリスト生成プロセス２０３ｂ、推定プロセス２０３ｃ、カメラコントロールプロセス２０３ｄとして機能するようになる。なお、各プロセス２０３ａ〜２０３ｄは、図１に示した、ピラミッド特徴点グラフ生成部１２ａ、マッチングリスト生成部１２ｂ、推定部１２ｃ、カメラコントローラ１２ｄにそれぞれ対応する。
【０１５８】
また、ＨＤＤ２０５には、図２０に示すように、画像データ２０５ａと、ピラミッド特徴点グラフデータ２０５ｂと、マッチングリストデータ２０５ｃとが設けられる。画像データ２０５ａ、ピラミッド特徴点グラフデータ２０５ｂ、マッチングリストデータ２０５ｃは、図１に示した画像記憶部１１ａ、ピラミッド特徴点グラフ記憶部１１ｂ、マッチングリスト記憶部１１ｃに対応する。そしてＣＰＵ２０３は、画像データ２０６ａを画像データ２０５ａに対して登録し、ピラミッド特徴点グラフデータ２０６ｂをピラミッド特徴点グラフデータ２０５ｂに対して登録し、マッチングリストデータ２０６ｃをマッチングリストデータ２０５ｃに対して登録し、この画像データ２０６ａとピラミッド特徴点グラフデータ２０６ｂとマッチングリストデータ２０６ｃとを読み出してＲＡＭ２０６に格納し、ＲＡＭ２０６に格納された画像データ２０６ａとピラミッド特徴点グラフデータ２０６ｂとマッチングリストデータ２０６ｃとに基づいて画像間対応付け処理を実行する。
【０１５９】
なお、上記した各プログラム２０４ａ〜２０４ｄについては、必ずしも最初からＲＯＭ２０４に記憶させておく必要はなく、例えばコンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、または、コンピュータ２００の内外に備えられるＨＤＤなどの「固定用物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ２００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておき、コンピュータ２００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１６０】
以上の実施例１〜３を含む実施形態に関し、更に以下の付記を開示する。
【０１６１】
（付記１）画像間の対応付けを行なう画像間対応付け方法をコンピュータに実行させる画像間対応付けプログラムであって、
画像から抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、前記最下位階層の特徴点集合から順に繰り返すことにより、前記複数の特徴点それぞれが、上位階層ごとの前記代表特徴点いずれかに連結されて最上位階層の前記代表特徴点いずれかに集約して連結される階層構造である特徴点集約階層構造を、対応付けの対象となる画像ごとに生成する特徴点集約階層構造生成手順と、
前記対応付けの対象となる２つの画像の間で対応付けを行なう際に、前記特徴点集約階層構造生成手順によって生成された前記２つの画像に対応する前記特徴点集約階層構造の前記最上位階層それぞれの前記代表特徴点すべての間で類似度を算出して特徴点間の対応付けを行なったうえで、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが前記代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出して特徴点間の対応付けを行なう階層間対応付け処理を、前記最上位階層の直下にある階層から順に繰り返すことにより、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付ける対応付け手順と、
をコンピュータに実行させることを特徴とする画像間対応付けプログラム。  
【０１６２】
（付記２）前記対応付け手順は、前記最下位階層より上位にある階層において前記階層間対応付け処理により対応付けられた特徴点間の類似度を用いて当該階層の直上にある階層における特徴点間の類似度を更新するとともに、類似度が更新された下位階層の直上にある上位階層にて対応付けられている特徴点間の類似度を当該下位階層にて更新された特徴点間の類似度を用いて更新する類似度更新処理と、上位階層にて対応付けられている特徴点間の更新された類似度を用いて当該上位階層の直下にある下位階層における特徴点間の対応付けを更新する階層間対応付け更新処理とを繰り返して、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付けることを特徴とする付記１に記載の画像間対応付けプログラム。
【０１６３】
（付記３）画像間の対応付けを行なう画像間対応付け装置であって、
画像から抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、前記最下位階層の特徴点集合から順に繰り返すことにより、前記複数の特徴点それぞれが、上位階層ごとの前記代表特徴点いずれかに連結されて最上位階層の前記代表特徴点いずれかに集約して連結される階層構造である特徴点集約階層構造を、対応付けの対象となる画像ごとに生成する特徴点集約階層構造生成手段と、
前記対応付けの対象となる２つの画像の間で対応付けを行なう際に、前記特徴点集約階層構造生成手段によって生成された前記２つの画像に対応する前記特徴点集約階層構造の前記最上位階層それぞれの前記代表特徴点すべての間で類似度を算出して特徴点間の対応付けを行なったうえで、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが前記代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出して特徴点間の対応付けを行なう階層間対応付け処理を、前記最上位階層の直下にある階層から順に繰り返すことにより、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付ける対応付け手段と、
を備えたことを特徴とする画像間対応付け装置。
【０１６４】
（付記４）前記対応付け手段は、前記最下位階層より上位にある階層において前記階層間対応付け処理により対応付けられた特徴点間の類似度を用いて当該階層の直上にある階層における特徴点間の類似度を更新するとともに、類似度が更新された下位階層の直上にある上位階層にて対応付けられている特徴点間の類似度を当該下位階層にて更新された特徴点間の類似度を用いて更新する類似度更新処理と、上位階層にて対応付けられている特徴点間の更新された類似度を用いて当該上位階層の直下にある下位階層における特徴点間の対応付けを更新する階層間対応付け更新処理とを繰り返して、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付けることを特徴とする付記３に記載の画像間対応付け装置。
【０１６５】
（付記５）画像間の対応付けを行なう画像間対応付け方法であって、
画像から抽出した複数の特徴点を最下位階層の特徴点集合としたうえで、下位階層の特徴点集合を構成する特徴点を、特徴点間の距離および特徴点間の類似度に基づいて特徴点部分集合に分類し、分類された各特徴点部分集合を代表する特徴点である代表特徴点の集合を上位階層の特徴点集合として生成する処理を、前記最下位階層の特徴点集合から順に繰り返すことにより、前記複数の特徴点それぞれが、上位階層ごとの前記代表特徴点いずれかに連結されて最上位階層の前記代表特徴点いずれかに集約して連結される階層構造である特徴点集約階層構造を、対応付けの対象となる画像ごとに生成する特徴点集約階層構造生成ステップと、
前記対応付けの対象となる２つの画像の間で対応付けを行なう際に、前記特徴点集約階層構造生成ステップによって生成された前記２つの画像に対応する前記特徴点集約階層構造の前記最上位階層それぞれの前記代表特徴点すべての間で類似度を算出して特徴点間の対応付けを行なったうえで、上位階層の直下にある下位階層において、当該上位階層にて対応付けられた特徴点それぞれが前記代表特徴点とされる特徴点部分集合に含まれる特徴点それぞれの間で、当該上位階層にて対応付けられた代表特徴点間の類似度に基づく類似度を算出して特徴点間の対応付けを行なう階層間対応付け処理を、前記最上位階層の直下にある階層から順に繰り返すことにより、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付ける対応付けステップと、
を含んだことを特徴とする画像間対応付け方法。
【０１６６】
（付記６）前記対応付けステップは、前記最下位階層より上位にある階層において前記階層間対応付け処理により対応付けられた特徴点間の類似度を用いて当該階層の直上にある階層における特徴点間の類似度を更新するとともに、類似度が更新された下位階層の直上にある上位階層にて対応付けられている特徴点間の類似度を当該下位階層にて更新された特徴点間の類似度を用いて更新する類似度更新処理と、上位階層にて対応付けられている特徴点間の更新された類似度を用いて当該上位階層の直下にある下位階層における特徴点間の対応付けを更新する階層間対応付け更新処理とを繰り返して、前記２つの画像それぞれの前記最下位階層の特徴点集合に含まれる前記複数の特徴点の間を対応付けることを特徴とする付記５に記載の画像間対応付け方法。
【図面の簡単な説明】
【０１６７】
【図１】実施例１における画像マッチング装置の構成を示すブロック図である。
【図２】ピラミッド特徴点グラフ生成部の原画像に対する処理を説明するための図である。
【図３】ピラミッド特徴点グラフ生成部のレベル１における処理を説明するための図である。
【図４】ピラミッド特徴点グラフ生成部のレベル２における処理を説明するための図である。
【図５】ピラミッド特徴点グラフ生成部のレベル３における処理を説明するための図である。
【図６】ピラミッド特徴点グラフ記憶部が記憶する画像Ａのピラミッド特徴点グラフを説明するための図である。
【図７】ピラミッド特徴点グラフ記憶部が記憶する画像Ｂのピラミッド特徴点グラフを説明するための図である。
【図８】マッチングリスト生成部のレベル３マッチングリスト生成処理を説明するための図である。
【図９】マッチングリスト生成部のレベル２マッチングリスト生成処理を説明するための図である。
【図１０】マッチングリスト生成部のレベル１マッチングリスト生成処理を説明するための図である。
【図１１】マッチングリスト生成部のレベル０マッチングリスト生成処理を説明するための図である。
【図１２】マッチングリスト生成部が生成したレベル０マッチングリストを説明するための図である。
【図１３】実施例１における画像マッチング装置の処理を説明するためのフローチャートである。
【図１４】実施例２における画像マッチング装置の概念を説明するための図である。
【図１５】実施例２において生成されたレベル２およびレベル１のマッチングリストを説明するための図である。
【図１６】実施例２におけるマッチングリスト生成部の類似度更新処理を説明するための図である。
【図１７】実施例２におけるマッチングリスト生成部のマッチングリスト更新処理を説明するための図である。
【図１８】実施例２における変形例を説明するための図である。
【図１９】実施例２における画像マッチング装置の処理を説明するためのフローチャートである。
【図２０】実施例１の画像間対応付けプログラムを実行するコンピュータを示す図である。
【符号の説明】
【０１６８】
１０  画像マッチング装置
１１ａ  画像記憶部
１１ｂ  ピラミッド特徴点グラフ記憶部
１１ｃ  マッチングリスト記憶部
１２ａ  ピラミッド特徴点グラフ生成部
１２ｂ  マッチングリスト生成部
１２ｃ  推定部
１２ｄ  カメラコントローラ
【図１】
0004962382.tif 000002
【図２】
0004962382.tif 000003
【図３】
0004962382.tif 000004
【図４】
0004962382.tif 000005
【図５】
0004962382.tif 000006
【図６】
0004962382.tif 000007
【図７】
0004962382.tif 000008
【図８】
0004962382.tif 000009
【図９】
0004962382.tif 000010
【図１０】
0004962382.tif 000011
【図１１】
0004962382.tif 000012
【図１２】
0004962382.tif 000013
【図１３】
0004962382.tif 000014
【図１４】
0004962382.tif 000015
【図１５】
0004962382.tif 000016
【図１６】
0004962382.tif 000017
【図１７】
0004962382.tif 000018
【図１８】
0004962382.tif 000019
【図１９】
0004962382.tif 000020
【図２０】
0004962382.tif 000021