JP6094949B2 - 画像処理装置、画像処理方法、及びプログラム - Google Patents

Description

本発明に係るいくつかの態様は、画像処理装置、画像処理方法、及びプログラムに関する。

従来から、画像内の被写体（例えば、写真、建物、印刷物等）を、撮影サイズや角度の変化、オクルージョンに対して頑健に識別するために、画像内の特徴的な点（特徴点）を多数検出すると共に、各特徴点周辺の局所領域の特徴量（局所特徴量）を抽出する技術がある。例えば特許文献１は、ＳＩＦＴ（Ｓｃａｌｅ Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅ Ｔｒａｎｓｆｏｒｍ）特徴量を用いる装置を開示している。

ＳＩＦＴ特徴量を用いる装置では、まず、１の画像（第１の画像と呼ぶ）から特徴点を多数検出すると共に、これらの特徴点の座標位置、スケール（大きさ）、および角度から局所特徴量を生成する。この生成した多数の局所特徴量で構成される局所特徴量群について、第１の画像に係る局所特徴量群と、第２の画像に係る局所特徴量群とを照合することにより、画像間で同一または類似の被写体を識別することができる。

ここで類似とは、被写体の一部が異なる、被写体の一部のみが写っている、或いは画像間で被写体の撮影角度が異なるために被写体の見え方が異なる、ことなどを意味する。

米国特許第６７１１２９３号公報

Ｊｉａｎｂｏ Ｓｈｉ， Ｍａｌｉｋ， Ｊ．， "Ｎｏｒｍａｌｉｚｅｄ Ｃｕｔｓ ａｎｄ Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ，" ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ｖｏｌ． ２２， ｎｏ． ８， ｐｐ ８８８−９０５， ２０００． Ｓｔｉｊｎ ｖａｎ Ｄｏｎｇｅｎ著、「Ｇｒａｐｈ Ｃｌｕｓｔｅｒｉｎｇ ｂｙ Ｆｌｏｗ Ｓｉｍｕｌａｔｉｏｎ」、ＰｈＤ ｔｈｅｓｉｓ、Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｕｔｒｅｃｈｔ、２０００年 ＭａｃＱｕｅｅｎ Ｊ， "Ｓｏｍｅ Ｍｅｔｈｏｄｓ ｆｏｒ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｎｄ Ａｎａｌｙｓｉｓ ｏｆ Ｍｕｌｔｉｖａｒｉａｔｅ Ｏｂｓｅｒｖａｔｉｏｎｓ，" Ｐｒｏｃ． ５ｔｈ Ｂｅｒｋｅｌｅｙ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｍａｔｈ． Ｓｔａｔ． ａｎｄ Ｐｒｏｂ． １， Ｕｎｉｖ． ｏｆ Ｃａｌｉｆｏｒｎｉａ Ｐｒｅｓｓ， Ｂｅｒｋｅｌｅｙ ａｎｄ Ｌｏｓ Ａｎｇｅｌｅｓ， ｐｐ． ８４−９５， １９６７． Ｌｉｎｄｅ， Ｙ．， Ｂｕｚｏ， Ａ．， Ｇｒａｙ， Ｒ．， "Ａｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｖｅｃｔｏｒ Ｑｕａｎｔｉｚｅｒ Ｄｅｓｉｇｎ，" ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ｖｏｌ． ２８， ｐｐ． ８４−９５， １９８０． 目木義久， 金道敏樹， 黒川弘章， 笹瀬巌， "教師なしクラスタリングによって未知データの階層的なクラスタ構造を推定する競合モデル"， 電子情報通信学会論文誌Ｄ−ＩＩ， ｖｏｌ． Ｊ８１−Ｄ−ＩＩ， ｎｏ． ９， ｐｐ． ２２００−２２１０， １９９８．

上述の手法では、例えば、同一の商品が一列に多数陳列されている場合など、一方の画像に同一または類似の被写体が多数含まれる場合には、類似の局所特徴量が多数生成されることとなる。このような場合には、類似の局所特徴量を多数含む第１の局所特徴量群と、第２の局所特徴量群とを照合しても、第１の画像の個別の被写体を正確に識別するのは困難であることから、個別の被写体の識別制度が低下してしまう。

本発明のいくつかの態様は前述の課題に鑑みてなされたものであって、画像内に同一または類似の被写体が多数含まれる場合であっても、精度良く照合することのできる画像処理装置、画像処理方法、及びプログラムを提供することを目的の１つとする。

本発明に係る１の画像処理装置は、第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成する第１の特徴量生成手段と、前記第１の座標位置情報群に基づき、前記第１の画像の特徴点をクラスタリングする領域分割手段と、クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合する照合手段とを有する。

本発明に係る１の画像処理方法は、第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成するステップと、前記第１の座標位置情報群に基づき、前記第１の画像の特徴点をクラスタリングするステップと、クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合するステップとを備える。

本発明に係る１のプログラムは、第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成するステップと、前記第１の座標位置情報群に基づき、前記第１の画像の特徴点をクラスタリングするステップと、クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合するステップとを画像処理装置に実行させる。

尚、本発明において、「部」や「手段」、「装置」とは、単に物理的手段を意味するものではなく、その「部」や「手段」、「装置」が有する機能をソフトウェアによって実現する場合も含む。また、１つの「部」や「手段」、「装置」が有する機能が２つ以上の物理的手段や装置により実現されても、２つ以上の「部」や「手段」、「装置」の機能が１つの物理的手段や装置により実現されても良い。

本発明によれば、画像内に同一または類似の被写体が多数含まれる場合であっても、精度良く照合することのできる画像処理装置、画像処理方法、及びプログラムを提供することができる。

第１の実施形態に係る画像処理装置の構成を示す図である。 第１の実施形態に係る画像処理装置の処理の流れを示すフローチャートである。 第２の実施形態に係る画像処理装置の構成を示す図である。 第２の実施形態の領域分割部の構成を示す図である。 第２の実施形態に係る画像処理装置の処理の流れを示すフローチャートである。 第３の実施形態に係る画像処理装置の構成を示す図である。 第３の実施形態の領域分割部の構成を示す図である。 第３の実施形態に係る画像処理装置の処理の流れを示すフローチャートである。 第４の実施形態に係る画像処理装置の構成を示す図である。 第４の実施形態の領域分割部の構成を示す図である。 第４の実施形態に係る画像処理装置の処理の流れを示すフローチャートである。 第５の実施形態に係る画像処理装置の構成を示す図である。 第５の実施形態の領域分割部の構成を示す図である。 第５の実施形態の相対座標位置テーブルのデータ構成の具体例を示す図である。 第５の実施形態に係る画像処理装置の処理の流れを示すフローチャートである。 第６の実施形態に係る画像処理装置の構成を示す図である。 第６の実施形態の領域分割部の構成を示す図である。 第６の実施形態に係る画像処理装置の処理の流れを示すフローチャートである。 第７の実施形態に係る画像処理装置の構成を示す図である。 第７の実施形態の領域分割部の構成を示す図である。 第７の実施形態に係る画像処理装置の処理の流れを示すフローチャートである。 第８の実施形態に係る画像処理装置の構成を示す図である。 第８の実施形態の領域分割部の構成を示す図である。 第８の実施形態に係る画像処理装置の処理の流れを示すフローチャートである。

以下に本発明の実施形態を説明する。以下の説明及び参照する図面の記載において、同一又は類似の構成には、それぞれ同一又は類似の符号が付されている。

（１ 第１の実施形態）
（１．１ 機能構成）
以下、図１を参照しながら、本実施形態に係る画像処理装置１０の機能構成を説明する。図１は、本実施形態に係る画像処理装置１０の機能構成を示す機能ブロック図である。尚、画像処理装置１０の各機能構成は、メモリに一時記憶されると共にＣＰＵ（ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）上で動作するプログラムとして実現されても良い。

画像処理装置１０は、第１の局所特徴量生成部１０１と、第２の局所特徴量生成部１０３と、領域分割部１０５と、照合部１０７とを含む。以下、第１の画像には同一または類似の被写体が多数含まれており、また、第２の画像には被写体が１つだけ含まれているものとして説明する。この点、第２の実施形態以降についても同様である。

第１の局所特徴量生成部１０１は、第１の画像から多数の特徴点を検出すると共に、当該多数の特徴点の座標位置で構成される第１の座標位置情報群を領域分割部１０５へと出力する。また、第１の局所特徴量生成部１０１は、各特徴点の座標位置から、特徴点を含む周辺領域（近傍領域）の局所特徴量で構成される第１の局所特徴量群を照合部１０７へと出力する。

第２の局所特徴量生成部１０３は、第１の局所特徴量生成部１０１と同様の動作により、第２の画像に含まれる多数の特徴点を検出すると共に、各特徴点に対する局所特徴量を生成し、当該多数の局所特徴量から構成される第２の局所特徴量群を照合部１０７へと出力する。

領域分割部１０５は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群を用いて第１の画像の特徴点をクラスタリングすると共に、１以上の特徴点を含む複数のクラスタに係る複数のクラスタ情報で構成されるクラスタ情報群を、照合部１０７へと出力する。

照合部１０７は、第１の局所特徴量生成部１０１が出力した第１の局所特徴量群と、第２の局所特徴量生成部１０３が出力した第２の局所特徴量群と、領域分割部１０５が出力したクラスタ情報群とを用いて、クラスタ単位で、第１の局所特徴量群と第２の局所特徴量群とを照合することにより、各特徴点に対して同一性または類似性を判定する。この結果、照合部１０７は、第１の画像と第２の画像との間で同一または類似の被写体を識別すると共に、その識別結果（照合結果）を出力する。さらに照合部１０７は、同一または類似と判定した特徴点に関して、そのクラスタに属する特徴点の座標位置情報に基づき、第１の画像の同一または類似と判定された領域の情報を出力するようにしても良い。
以下、画像処理装置１０の各構成の動作の詳細を説明する。

（１．２ 機能の詳細）
（１．２．１ 特徴量生成）
前述の通り、第１の局所特徴量生成部１０１は、第１の画像から特徴点を多数検出すると共に、検出した多数の特徴点の座標位置で構成される第１の座標位置情報群を領域分割部１０５へと出力する。また、第１の局所特徴量生成部１０１は、検出した各特徴点の座標位置から局所特徴量を生成すると共に、生成した多数の局所特徴量で構成される第１の局所特徴量群を、照合部１０７へと出力する。

ここで、第１の局所特徴量生成部１０１は、例えば各特徴点の座標位置に加えて、局所特徴量を生成する領域のスケールや角度の情報を用いて、局所特徴量としても良い。例えば、局所特徴量は、ＳＩＦＴ（Ｓｃａｌｅ Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅ Ｔｒａｎｓｆｏｒｍ）特徴量としても良いし、その他の局所特徴量としても良い。

第２の局所特徴量生成部１０３は、第１の局所特徴量生成部１０１と同様の動作により、第２の画像の各特徴点の局所特徴量を生成するとともに、当該生成した多数の局所特徴量で構成される第２の局所特徴量群を、照合部１０７へと出力する。特徴点の検出や局所特徴量の生成方法としては色々考えられる。例えば、特許文献１に記載の手法などが考えられる。

尚、例えば、第２の画像の各特徴点の局所特徴量を事前に生成してデータベースなどに記憶しておくことで、第２の局所特徴量生成部１０３ではなく、当該データベースが第２の局所特徴量群を出力するようにしても良い。この点、第２の実施形態以降についても同様である。

（１．２．２ 領域分割）
領域分割部１０５は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群を用いて第１の画像の各特徴点をクラスタリングすると共に、１以上の特徴点から構成される各クラスタのクラスタ情報であるクラスタ情報群を照合部１０７へと出力する。特徴点のクラスタリングには、例えば、特徴点の座標位置が近い、すなわち、２つの特徴点間の距離（座標位置間の距離）が近い特徴点を同じクラスタに分類する方法を用いることが考えられる。ここで、２つの特徴点間の距離には、たとえばユークリッド距離を用いても良いし、マハラノビス距離を用いても良いし、市街地距離を用いても良い。

また、特徴点のクラスタリングには、たとえば、全ての特徴点間の距離を算出するとともに、算出した距離をグラフカットによりクラスタリングする方法を用いることも考えられる。この場合、例えば、特徴点をノードとして、特徴点間の距離をノード間のエッジとしたグラフを生成する。グラフカットには、例えば、ノーマライズドカットを用いても良いし、マルコフ・クラスタ（Ｍａｒｋｏｖ Ｃｌｕｓｔｅｒ）アルゴリズムを用いても良い。尚、ノーマライズドカットについては、非特許文献１に記載の手法を用いることができる。また、マルコフ・クラスタ・アルゴリズムについては、非特許文献２に記載の手法を用いることができる。更に、特徴点のクラスタリングには、例えば、ｋ−ｍｅａｎｓ法や、ＬＢＧ法や、ＬＢＱ法を用いること等が考えられる。ｋ−ｍｅａｎｓ法については非特許文献３に、ＬＢＧ法については非特許文献４に、ＬＢＱ法については非特許文献５に、それぞれ開示されている具体的手法を用いることができる。

また、特徴点のクラスタリングには、例えば、任意のサイズの分析領域ごとに当該領域に含まれる特徴点を計数し、計数値が所定の閾値以上であれば、当該領域に含まれる特徴点を同一のクラスタに分類するという方法を用いてもよい。

分析領域の生成には、例えば、第１の画像を任意のサイズのグリッドに分割し、各グリッドを分析領域とする方法を用いてもよい。また、分析領域は、例えば、重複していてもよいし、重複していなくてもよい。また、分析領域のサイズは、例えば、固定でもよいし、可変でもよい。可変の場合は、例えば、分析領域の中心と画像中心との間の距離が近いほど分析領域サイズを小さくし、分析領域の中心と画像中心との間の距離が遠いほど分析領域サイズを大きくするという方法を用いてもよい。

特徴点の分類には、例えば、計数値が所定の閾値以上の分析領域に含まれる特徴点を同一のクラスタに分類する方法を用いてもよいし、当該領域とその周囲の分析領域に含まれる特徴点を同一のクラスタに分類する方法を用いてもよい。また、計数値が所定の閾値以上の分析領域が隣接あるいは重複している場合は、例えば、これらの分析領域に含まれる特徴点を同一のクラスタに分類する方法を用いてもよいし、異なるクラスタに分類する方法を用いてもよい。

このように特徴点をクラスタリングすることで、非特許文献３乃至５のいずれか記載の手法を用いるよりも高速に処理できるという効果がある。

（１．２．３ 照合）
照合部１０７は、領域分割部１０５が出力したクラスタ情報群を用いて、クラスタ単位で、第１の局所特徴量群と第２の局所特徴量群とを照合すると共に、特徴量間で同一性または類似性を判定する。これにより、画像間で同一または類似の被写体を識別する。

クラスタ単位で第１の局所特徴量群と第２の局所特徴量群とを照合する方法の一例を以下説明する。対象とするクラスタに対して、まず第１の局所特徴量群の対象クラスタに属する局所特徴量群と、第２の局所特徴量群との間で、局所特徴量間の距離を算出するとともに、算出した距離に基づいて、第１の画像の特徴点と第２の画像の特徴点との対応関係（第１の画像の特徴点が第２の画像のどの特徴点に対応するか）を算出する。特徴点間の距離は、例えばＳＩＦＴ特徴量の場合にはユークリッド距離を用いても良い。ここで例えば、距離値が最も小さい特徴点を対応する特徴点としても良い。また、対応関係が存在しない特徴点があっても良い。例えば、最も小さい距離値と、２番目に小さい距離値との比率を評価尺度として、対応関係の有無を判定することが考えられる。例えば、こうして求められた対応関係を用いて、例えば対応する特徴点の数が閾値を超える場合に、対象クラスタと第２の画像とが、同一（または類似）と判定すれば良い。

また、求められた対応関係を用いて幾何学的検証を行うことで、同一性または類似性を判定しても良い。例えば、２つの画像間の幾何学的関係性を射影変換（ホモグラフィ）と仮定した上で、ロバスト推定手法を用いて射影変換のパラメータを推定すると共に、推定パラメータに対する入力された対応関係の外れ値を求めることで、外れ値の数に基づいて同一性または類似性を判定しても良い。ロバスト推定手法には、例えばＲＡＮＳＯＣ（Ｒａｎｄｏｍ Ｓａｍｐｌｅ Ｃｏｎｓｅｎｓｕｓ）や最小二乗法を使用することが考えられる。

（１．３ 処理の流れ）
次に、図２を参照しながら、本実施形態に係る画像処理装置１０の処理の流れを説明する。図２は、本実施形態に係る画像処理装置１０の処理の流れを示すフローチャートである。

尚、後述の各処理ステップは、処理内容に矛盾を生じない範囲で、任意に順番を変更して若しくは並列に実行することができ、また、各処理ステップ間に他のステップを追加しても良い。更に、便宜上１つのステップとして記載されているステップは複数のステップに分けて実行することもでき、便宜上複数に分けて記載されているステップを１ステップとして実行することもできる。この点、第２の実施形態以降についても同様である。

第１の局所特徴量生成部１０１は第１の画像から多数の特徴点を検出し、第２の局所特徴量生成部１０３は、第２の画像から多数の特徴点を検出する（Ｓ２０１）。次に、第１の局所特徴量生成部１０１及び第２の局所特徴量生成部１０３は、各特徴点の座標位置（前述の通り、必要に応じて、スケールおよび角度を用いても良い）から、局所特徴量を生成する（Ｓ２０３）。領域分割部１０５は、第１の画像の特徴点の座標位置である第１の座標位置情報群を用いて、第１の画像の各特徴点をクラスタリングする（Ｓ２０５）。照合部１０７は、第１の局所特徴量群と、第２の局所特徴量群とを、第１の局所特徴量のクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する（Ｓ２０７）。

（１．４ 本実施形態に係る効果）
以上説明したように、本実施形態にかかる画像処理装置１０は、第１の画像から検出した多数の特徴点を、それらの座標位置に基づいてクラスタリングすると共に、第１の局所特徴量群と第２の局所特徴量群とを、クラスタ単位で照合する。このようにクラスタ単位で局所特徴量を照合することにより、画像内の同一または類似の被写体を、精度よく多数識別できる。

（２ 第２の実施形態）
以下、第２の実施形態を説明する。以下の説明では、第１の実施形態と同一または類似の構成については同一の符号を振ると共に、説明を省略することがある。また、作用効果の記載についても、第１の実施形態と同様の場合には、説明を省略することがある。この点、第３の実施形態以降についても同様である。

（２．１ 機能構成）
図３は、第２の実施形態に係る画像処理装置１０の機能構成を示す図である。図３に示すように、画像処理装置１０は、第１の局所特徴量生成部１０１と、第２の局所特徴量生成部１０３と、領域分割部１０５と、照合部１０７とを含む。ここで、第２の局所特徴量生成部１０３及び照合部１０７の動作は、第１の実施形態と同様であるので説明を省略する。

第１の局所特徴量生成部１０１は、第１の実施形態と同様に、第１の画像の特徴点を多数検出するとともに、第１の座標位置情報群を領域分割部１０５へと出力する。また、第１の局所特徴量生成部１０１は、第１の実施形態と同様の動作により、第１の画像の各特徴点の局所特徴量である第１の局所特徴量群を生成するとともに、当該第１の局所特徴量群を領域分割部１０５と照合部１０７とに出力する。

領域分割部１０５は、第１の局所特徴量生成部１０１が出力した第１の局所特徴量群と第１の座標位置情報群とを用いて、第１の画像の特徴点をクラスタリングすると共に、当該クラスタリングした結果を示すクラスタ情報群を照合部１０７へと出力する。

図４に、本実施形態に係る領域分割部１０５の詳細な機能構成を示す。図５に示すように、領域分割部１０５は、類似度算出部４０１及び特徴点クラスタリング部４０３を含む。

類似度算出部４０１は、第１の局所特徴量生成部１０１が出力した第１の局所特徴量群内の任意の２つの局所特徴量の類似度を算出すると共に、算出した多数の類似度を、類似度情報群として特徴点クラスタリング部４０３へと出力する。局所特徴量の類似度の算出法には、例えば、任意の２つの局所特徴量間の特徴量間距離（例えばユークリッド距離）を算出すると共に、距離に基づいて類似度を算出すること等が考えられる。この時、例えば、距離値が小さい場合は類似度を大きく、距離値が大きい場合には類似度を小さくすればよい。また、特徴量間距離を所定の値で正規化すると共に、正規化した値から類似度を算出する方法を用いることも考えられる。

特徴点クラスタリング部４０３は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群と、類似度算出部４０１が出力した類似度情報群とを用いて、第１の画像の特徴点をクラスタリングするとともに、当該クラスタリングの結果を示すクラスタ情報群を照合部１０７へと出力する。ここで、特徴点クラスタリング部４０３は、例えば類似度が大きい（距離値が小さい）局所特徴量が異なるクラスタに分類されるようにクラスタリングすれば良い。特徴点のクラスタリングには、例えば、第１の画像の任意の特徴点と各クラスタ重心との距離を算出すると共に、算出した距離が最も小さくなるクラスタに当該特徴点を分類する方法を用いることが考えられる。この際、任意のクラスタ内に閾値以上の類似度の特徴点が含まれる場合には、例えば、クラスタ重心までの距離が長い特徴点を、当該クラスタから除外して別のクラスタに分類すれば良い。ここで、各特徴点とクラスタ重心との距離には、例えば、ユークリッド距離を用いても良いし、マハラノビス距離を用いても良いし、市街地距離を用いても良い。

また、グラフカットを用いてクラスタリングしても良い。例えば、特徴点をノードとして、特徴点間の距離と、その局所特徴量間の類似度とに基づいてエッジ値を算出（例えば、特徴点間の距離が小さく、局所特徴量間の類似度が大きいほど、２つのノード間のエッジ値を大きくするなど）して得られたグラフに対してグラフカットを提供しても良い。グラフカットには、例えば、ノーマライズドカットを用いても良いし、マルコフ・クラスタ・アルゴリズムを用いても良い。

（２．２ 処理の流れ）
以下、図５を参照しながら、本実施形態に係る画像処理装置１０の処理の流れを説明する。図５は、画像処理装置１０の処理の流れを示すフローチャートである。

第１の局所特徴量生成部１０１は第１の画像から多数の特徴点を検出し、また、第２の局所特徴量生成部１０３は第２の画像から特徴点を多数検出する（Ｓ５０１）。次に、第１の局所特徴量生成部１０１及び第２の局所特徴量生成部１０３は、各特徴点の座標位置から、各特徴点の特徴量を含む局所特徴量群（第１の局所特徴量群及び第２の局所特徴量群）を生成する（Ｓ５０３）。領域分割部１０５は、第１の座標位置情報群と第１の局所特徴量群とを用いて、第１の画像の特徴点をクラスタリングする（Ｓ５０５）。照合部１０７は、第１の局所特徴量群と、第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する（Ｓ５０７）。

（２．３ 本実施形態に係る効果）
以上説明したように、本実施形態では、第１の画像から検出した多数の特徴点を、それらの座標位置と類似度とに基づいてクラスタリングし、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する。これにより、第１の実施形態と同様の効果を得ることができる。

更に、本実施形態では、局所特徴量が類似している特徴点が同じクラスタに含まれにくくなるようにクラスタリングするため、同一または類似の被写体が近接する場合であっても、第１の実施形態よりも精度よく被写体を識別できる。

（３ 第３の実施形態）
（３．１ 機能構成）
図６を参照しながら、第３の実施形態に係る画像処理装置１０の機能構成を説明する。図６は、本実施形態に係る画像処理装置１０の機能構成を示す図である。

図６に示すように、画像処理装置１０は、第１の局所特徴量生成部１０１と、第２の局所特徴量生成部１０３と、領域分割部１０５と、照合部１０７とを含む。ここで、第１の局所特徴量生成部１０１の動作は第２の実施形態と、照合部１０７の動作は第１の実施形態と同様であるので、ここでは説明を省略する。以下、第２の局所特徴量生成部１０３及び領域分割部１０５の動作を中心に説明する。

第２の局所特徴量生成部１０３は、第１の実施形態と同様の動作により、第２の画像の各特徴点に係る局所特徴量を生成すると共に、当該局所特徴量の集合である第２の局所特徴量群を領域分割部１０５と照合部１０７とに出力する。領域分割部１０５は、第１の局所特徴量生成部１０１が出力した第１の局所特徴量群および第１の座標位置情報群と、第２の局所特徴量生成部１０３が出力した第２の局所特徴量群とを用いて、第１の画像の特徴点をクラスタリングすると共に、当該クラスタリングの結果に係るクラスタ情報群を照合部１０７へと出力する。以下、図７を参照しながら、領域分割部１０５の機能構成および動作を説明する。

図７は、本実施形態に係る領域分割部１０５の構成を示す図である。図７に示す通り、領域分割部１０５は、対応点探索部４０５と、特徴点クラスタリング部４０３とを含む。

対応点探索部４０５は、第１の局所特徴量生成部１０１が出力した第１の局所特徴量群と、第２の局所特徴量生成部１０３が出力した第２の局所特徴量群とを用いて、第１の局所特徴量群に含まれる任意の局所特徴量が、第２の局所特徴量群のどの局所特徴量と一致するか、すなわち、第１の画像の任意の特徴点が第２の画像のどの特徴点と対応するかに関する情報である対応情報を生成する。更に、対応点探索部４０５は、生成した多数の対応情報を、対応情報群として特徴点クラスタリング部４０３へと出力する。

対応情報の生成には、例えば、第１の実施形態の照合部１０７と同様の手法を用いること等が考えられる。またここで、対応関係は、第２の画像の或る特徴点が、第１の画像の複数の特徴点に対応していても良い。更に、第１の画像の特徴点が、第２の画像の特徴点と１対１で対応していても良い。

特徴点クラスタリング部４０３は、第１の局所特徴量生成部１０１が出力した座標位置情報群と、対応点探索部４０５が出力した対応情報群とを用いて、第１の画像の特徴点のうち、第２の画像の特徴点と対応関係がある特徴点を選択した上で、選択した第１の画像の特徴点をそれらの座標位置に基づいてクラスタリングする。更に、特徴点クラスタリング部４０３は、当該クラスタリングに係る結果を示すクラスタ情報群を、照合部１０７へと出力する。特徴点のクラスタリングには、例えば、非特許文献３乃至５のいずれかに記載の手法を用いること等が考えられる。

また、特徴点クラスタリング部４０３は、第２の画像の特徴点が、第１の画像の複数の特徴点に対応している場合に、第１の画像の特徴点が異なるクラスタに分類されるようにクラスタリングしても良い。このために、例えば特徴点クラスタリング部４０３は、グラフカットによるクラスタリングを用いることなどが考えられる。この場合、第２の画像の特徴点が、第１の画像の複数の特徴点に対応している場合に、それらの第１の画像の複数の特徴点をノードとして、それらのノード間のエッジ値が小さくなるようにグラフを生成するとともに、エッジ値が小さいノード間を分割するようにグラフカットを適用することが考えられる。グラフカットには、例えば、ノーマライズドカットやマルコフ・クラスタ・アルゴリズムを用いても良い。

また、特徴点クラスタリング部４０３は、第１の画像の任意の２つの特徴点間の距離が近く（例えば、距離値がある閾値を下回る場合）、それらの特徴点に対応する第２の画像の特徴点間距離が遠い場合（例えば、距離値が別の閾値を上回る場合）に、第１の画像の２つの特徴点が異なるクラスタに分類されるようにしても良い。このために、上記と同様にグラフカットによるクラスタリングを用いることも考えられる。

また、特徴点クラスタリング部４０３は、例えば、第１の実施形態と同様に、任意のサイズの分析領域ごとに当該領域に含まれる特徴点を計数し、計数値が所定の閾値以上であれば、当該領域に含まれる特徴点を同一のクラスタに分類するという方法を用いてもよい。このように特徴点をクラスタリングすることで、非特許文献３乃至５のいずれか記載の手法を用いるよりも高速に処理できるという効果がある。
更に、第３の実施形態は、第２の実施形態と組み合わせることも考えられる。

（３．２ 処理の流れ）
以下、図８を参照しながら、本実施形態に係る画像処理装置１０の処理の流れを説明する。図８は、画像処理装置１０の処理の流れを示すフローチャートである。

第１の局所特徴量生成部１０１は第１の画像から特徴点を多数検出する。また、第２の局所特徴量生成部１０３は、第２の画像から特徴点を多数検出する（Ｓ８０１）。次に、第１の局所特徴量生成部１０１及び第２の局所特徴量生成部１０３は、各特徴点の座標位置から局所特徴量を生成する（Ｓ８０３）。領域分割部１０５は、第１の局所特徴量の対応関係、すなわち２画像間での特徴点の対応関係を求める（Ｓ８０５）。次に、領域分割部１０５は、第１の座標位置情報群と対応情報群とを用いて、第１の画像の特徴点のうち、第２の画像の特徴点と対応関係がある特徴点を選択すると共に、選択した第１の画像の特徴点を、それらの座標位置に基づいてクラスタリングする（Ｓ８０７）。照合部１０７は、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合すると共に、画像間で同一または類似の被写体を識別する（Ｓ８０９）。

（３．３ 本実施形態に係る効果）
以上説明したように、第３の実施形態に係る画像処理装置１０は、第１の画像から検出した多数の特徴点のうち、第２の画像の特徴点と一致した多数の特徴点をそれらの座標位置に基づいてクラスタリングするとともに、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する。これにより、第１の実施形態と同様の効果を得ることができる。

更に、２画像間で対応の取れた特徴点を、それらの座標位置に基づいてクラスタリングするため、第１の画像の特徴点が被写体以外から多数検出された場合であっても、第１の画像の同一または類似の被写体を第１の実施形態よりも精度よく多数識別できる。

（４ 第４の実施形態）
（４．１ 機能構成）
図９を参照しながら、第４の実施形態に係る画像処理装置１０の機能構成を説明する。図９は、本実施形態に係る画像処理装置１０の機能構成を示す図である。

画像処理装置１０は、第１の局所特徴量生成部１０１と、第２の局所特徴量生成部１０３と、領域分割部１０５と、照合部１０７とを含む。ここで、第１の局所特徴量生成部１０１の動作は第２の実施形態と、照合部１０７の動作は第１の実施形態と同様であるので、説明を省略する。以下、第２の局所特徴量生成部１０３及び領域分割部１０５の動作を中心に説明する。

第２の局所特徴量生成部１０３は、第１の実施形態と同様の動作により、第２の画像の特徴点を多数検出するとともに、第２の座標位置情報群を領域分割部１０５へと出力する。また、第２の局所特徴量生成部１０３は、第１の実施形態と同様の動作により、第２の画像の各特徴点の局所特徴量を生成すると共に、それらの局所特徴量からなる第２の局所特徴量群を領域分割部１０５と照合部１０７とに出力する。

領域分割部１０５は、第１の局所特徴量生成部１０１が出力した第１の局所特徴量群および第１の座標位置情報群と、第２の局所特徴量生成部１０３が出力した第２の局所特徴量群および第２の座標位置情報群とを用いて第１の画像の特徴点をクラスタリングするとともに、当該クラスタリング結果を示すクラスタ情報群を照合部１０７へと出力する。以下、図１０を参照しながら、領域分割部１０５の構成及び動作を説明する。

図１０は、本実施形態の領域分割部１０５の構成を示す図である。図１０に示すように、領域分割部１０５は、対応点探索部４０５と比率算出部４０７と特徴点クラスタリング部４０３とを含む。

対応点探索部４０５は、第３の実施形態と同様の動作により、対応情報群を生成するとともに、生成した対応情報群を、比率算出部４０７と特徴点クラスタリング部４０３とに出力する。

比率算出部４０７は、第１の局所特徴量生成部１０１が出力した第１の局所特徴量群と、第２の局所特徴量生成部１０３が出力した第２の局所特徴量群と、対応点探索部４０５が出力した対応情報群とを用いて、第１の画像の任意の２つの特徴点間の距離（以下、特徴点間距離という。）と、それらの特徴点に対応する第２の画像の特徴点間距離との比率を算出するとともに、算出した多数の比率を、比率情報群として特徴点クラスタリング部４０３へと出力する。ここで、特徴点間距離には、例えば、ユークリッド距離やマハラビノス距離、市街地距離を用いることが考えられる。

特徴点クラスタリング部４０３は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群と、対応点探索部４０５が出力した対応情報群と、比率算出部４０７が出力した比率情報群とを用いて、第１の画像の特徴点をクラスタリングするとともに、その結果を示すクラスタ情報群を照合部１０７へと出力する。ここで、例えば算出された比率の差が小さい特徴点を同じクラスタに分類する（比率の差が大きい特徴点を異なるクラスタに分類する）ように、クラスタリングすることが考えられる。この時には、例えば、グラフカットを用いてクラスタリングすれば良い。より具体的には、例えば、特徴点をノードとして、特徴点間の距離と、比率の差に基づいてノード間のエッジ値を大きくすることにより得られたグラフ対してグラフカットを行うことが考えられる。グラフカットには、例えば、ノーマライズドカットを用いても良いし、マルコフ・クラスタ・アルゴリズムを用いても良い。

特徴点クラスタリング部４０３は、座標位置情報群と、対応情報群と、比率情報群とを用いて、例えば、次のように第１の画像の特徴点をクラスタリングすることも考えられる。この場合、ある特徴点と、その周囲の複数の特徴点との比率情報群を用いて、その特徴点が任意のクラスタに所属する所属確率を算出する。この場合、この算出された所属確率と、その特徴点の座標位置情報とに基づいて、特徴点クラスタリング部４０３はクラスタリングする。特徴点のクラスタリングには、例えば、第２の画像の任意の特徴点に対応する第１の画像の特徴点を対応情報群に基づいて選択するとともに、当該特徴点と各クラスタ重心との間の距離を座標位置情報と所属確率とに基づいて算出すると共に、算出した距離が最も小さくなるクラスタに当該特徴点を分類する方法を用いることが考えられる。
任意の特徴点とクラスタ重心との距離の算出には、例えば、次式を用いることが考えられる。

数１において、Ｇ_ｉは第１の画像の任意の特徴点とｉ番目のクラスタ重心との距離を、ｐ_ｉはｉ番目のクラスタのクラスタ内確率密度関数を、ｆ_ｉはｉ番目のクラスタのクラスタ生起確率を、ｓ_ｉは第１の画像の任意の特徴点がｉ番目のクラスタに所属する所属確率を示している。尚、確率密度分布ｐ_ｉは数２のようになる。

数２において、Ｄは入力データの次元数を、ｖは入力データを、ｒはｉ番目のクラスタのクラスタ重心を、Σ_ｉはｉ番目のクラスタのクラスタ内共分散行列を示す。
クラスタ内生起確率ｆ_ｉは０より大きく１以下の値であり、その更新方法には、例えば非特許文献５に記載の方法を用いることが考えられる。

次に、所属確率ｓ_ｉの算出方法を説明する。ｓ_ｉは、例えば、第１の画像の特徴点間距離と第２の画像の特徴点間距離とを用いて、以下のように算出することが考えられる。
まず、第１の画像での特徴点間距離と第２の画像での特徴点間距離との比率ｒａｔｉｏ_ｎｋを次式により算出する。

ここで、ｖ_ｎは第１の画像のｎ番目の特徴点の座標位置を、ｕ_ｎ’はｖ_ｎにある特徴点に対応する第２の画像のｎ’番目の特徴点の座標位置を、ｖ_ｋはｖ_ｎにある特徴点の近傍にある特徴点の中でｖ_ｎとの間の距離がｋ番目に短い特徴点の座標位置を、ｕ_ｋ’はｖ_ｋにある特徴点に対応する第２の画像のｋ’番目の特徴点の座標位置を示している。ここで、ｋとｋ’の値域は、０≦ｋ、ｋ’≦Ｋ（０＜Ｋ）である。

このようにして算出した特徴点間距離の比率ｒａｔｉｏ_ｎｋは、第１の画像から選択した２つの特徴点が、両方とも同じ被写体の特徴点である場合と、異なる被写体の特徴点である場合とで、その値が異なるという特性がある。
次に、算出したＫ個の特徴点間距離の比の中央値ｍｅｄｉａｎ_ｎを求めると共に、数４、数５、数６により所属確率ｓ_ｉを算出する。

ここで、ｌａｂｅｌ_ｎｋは第１の画像のｎ番目の特徴点の近傍にあるＫ個の特徴点の中のｋ番目の特徴点が所属するクラスタ番号を、Ｎ_ｉはＫ近傍の特徴点の中でｉ番目のクラスタに所属する特徴点の数を、α及びεは任意の値を示している。例えば、α＝０．５、ε＝０．０００００１等に設定することができる。

（４．２ 処理の流れ）
以下、図１１を参照しながら、本実施形態に係る画像処理装置１０の処理の流れを説明する。図１１は、画像処理装置１０の処理の流れを示すフローチャートである。

第１の局所特徴量生成部１０１は、第１の画像から特徴点を多数検出する。また第２の局所特徴量生成部１０３は、第２の画像から特徴点を多数検出する（Ｓ１１０１）。次に、第１の局所特徴量生成部１０１及び第２の局所特徴量生成部１０３は、各特徴点の座標位置から、局所特徴量（第１の局所特徴量群及び第２の局所特徴量群）を生成する（Ｓ１１０３）。

領域分割部１０５は、第１の局所特徴量群の各局所特徴量と、第２の局所特徴量群の各局所特徴量との間の距離に基づいて、局所特徴量の対応関係、すなわち似画像間での特徴点の対応関係を求める（Ｓ１１０５）。次に、領域分割部１０５は、第１の座標位置情報群と第２の座標位置情報群と対応情報群とを用いて、第１の画像の２つの特徴点間の距離と第２の画像の２つの特徴点間の距離との比率を算出する（Ｓ１１０７）。更に領域分割部１０５は、第１の座標位置情報群と対応情報群と比率情報群とを用いて第１の画像の特徴点をクラスタリングする（Ｓ１１０９）。照合部１０７は、第１の局所特徴量群と、第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する（Ｓ１１１１）。

（４．３ 本実施形態に係る効果）
以上説明したように、本実施形態に係る画像処理装置１０は、第２の画像の特徴点に対応する第１の画像の特徴点をそれらの座標位置と特徴点間距離の比率とに基づいてクラスタリングすると共に、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する。これにより、第３の実施形態と同様の効果を得ることができる。

さらに、座標位置と特徴点間距離との比率に基づいてクラスタリングするため、第１の画像の同一または類似の被写体が近接している場合であっても、第３の実施形態よりも特徴点を精度よくクラスタリングできる。従って、画像内の同一または類似の被写体を第３の実施形態よりも精度よく多数識別できる。

（５ 第５の実施形態）
（５．１ 機能構成）
図１２を参照しながら、本実施形態に係る画像処理装置１０の機能構成を説明する。図１２は、第５の実施形態に係る画像処理装置１０の機能構成を示す図である。図１２に示す通り、画像処理装置１０の構成は第４の実施形態と同様である。しかしながら、領域分割部１０５の機能構成及び動作は異なる。以下、図１３を参照しながら、領域分割部１０５の構成及び動作を説明する。

図１３は、本実施形態に係る領域分割部１０５の機能構成を示す図である。図１４に示すように、領域分割部１０５は、対応点探索部４０５と、比率算出部４０７と、回転量算出部４０９と、相対座標位置データベース４１１と、特徴点クラスタリング部４０３とを含む。ここで、比率算出部４０７の動作は第４の実施形態と同様であるので、説明を省略する。以下、対応点探索部４０５、回転量算出部４０９、相対座標位置データベース４１１、及び特徴点クラスタリング部４０３の動作を中心に説明する。

対応点探索部４０５は、第３の実施形態と同様の動作により対応情報群を生成するとともに、生成した対応情報群を比率算出部４０７と回転量算出部４０９と特徴点クラスタリング部４０３とに出力する。

回転量算出部４０９は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群と、対応点探索部４０５が出力した対応情報群と、第２の局所特徴量生成部１０３が出力した第２の座標位置情報群とを用いて、第１の画像の２つの特徴点で構成されるベクトルの方向と第２の画像の２つの特徴点で構成されるベクトルの方向とを算出する。更に回転量算出部４０９は、算出したベクトルの方向から第１の画像の被写体の回転量を算出すると共に、算出した多数の回転量を回転量情報群として特徴点クラスタリング部４０３へと出力する。
第１の画像の２つの特徴点で構成されるベクトルの方向θ_ij ¹の算出には、例えば、次式を用いれば良い。

ここで、ｘは特徴点のｘ座標値を、ｙは特徴点のｙ座標値を、ｉ及びｊは特徴点番号を示す。
次に、第２の画像の２つの特徴点で構成されるベクトルの方向θ_ｎｍ ^２の算出には、例えば次式を用いれば良い。

ここで、ｎは第１の画像のｉ番目の特徴点に対応する第２の画像の特徴点番号を、ｍは第１の画像のｊ番目の特徴点に対応する第２の画像の特徴点番号を示す。
次に、回転量は、例えば数７や数８に基づき算出したベクトル方向を用いて、次式に従って算出すれば良い。

ここで、θ_ｉｊは第１の画像のｉ番目とｊ番目の特徴点で構成されるベクトルの回転量を示す。

相対座標位置データベース４１１は、第２の画像の基準点（例えば、被写体中心）と第２の画像の各特徴点との相対座標位置を示すテーブルを有する。ここで基準点とは、予め定められた第２の画像での座標位置である。上述の通り、基準点は被写体中心であっても良いし、第２の画像の左上座標位置であっても良い。以下では、基準点は被写体中心を示すものとして説明する。

図１４を参照しながら、本実施形態に係る相対座標位置データベース４１１について説明する。図１４は、相対座標位置データベース４１１の具体例を示す図である。相対座標位置データベース４１１は、データ項目として、例えば特徴点番号と相対座標位置とを有する。図１４に示す例では、１番目の特徴点の座標位置と、１番目の特徴点の被写体中心の座標位置との相対座標位置は（１００、１００）、２番目の特徴点の座標位置と、２番目の特徴点の被写体中心の座標位置との相対座標位置は（５０、−１０）である。
ここで、相対座標位置ｕ_ｎ’は次式のように算出すれば良い。

数１０中、ｎは特徴点番号を、ｘ_ｎはｎ番目の特徴点のｘ座標値を、ｙ_ｎはｎ番目の特徴点のｙ座標値を、ｘ_ｃは被写体中心のｘ座標値を、ｙ_ｃは被写体中心のｙ座標値を示す。

特徴点クラスタリング部４０３は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群と、対応点探索部４０５が出力した対応情報群と、比率算出部４０７が出力した比率情報群と、回転量算出部４０９が出力した回転量情報群と、相対座標位置データベース４１１に格納されている相対座標位置とを用いて、第１の画像の特徴点をクラスタリングする。また、特徴点クラスタリング部４０３は、当該クラスタリングの結果を示すクラスタ情報群を照合部１０７へと出力する。

ここで、特徴点のクラスタリングには、例えば、第１の画像の特徴点のうち、第２の画像の任意の特徴点に対応する特徴点を対応情報群に基づいて多数選択すると共に、選択された特徴点の座標位置に基づいて第１の画像の被写体中心点を推定し、更に、推定した被写体中心点をそれらの座標位置に基づいてクラスタリングする手法を用いることができる。
被写体中心点の座標位置の算出には、例えば次式を用いることができる。

ここで、ｉおよびｊは特徴点番号を、ｖ_ｉは第１の画像のｉ番目の特徴点の座標位置を、ｃ_ｉｊは被写体中心点の座標位置を、ｎは第１の画像のｉ番目の特徴点に対応する第２の画像の特徴点番号を示す。
被写体中心点のクラスタリングには、例えば、非特許文献３乃至５のいずれか記載の手法を用いることができる。

また、被写体中心点のクラスタリングには、例えば、任意のサイズの分析領域ごとに当該領域に含まれる被写体中心点を計数し、計数値が所定の閾値以上であれば、当該領域に含まれる被写体中心点を同一のクラスタに分類するという方法を用いてもよい。

分析領域の生成には、例えば、第１の画像を任意のサイズのグリッドに分割し、各グリッドを分析領域とするという方法を用いてもよい。また、分析領域は、例えば、重複していてもよいし、重複していなくてもよい。また、分析領域のサイズは、例えば、固定でもよいし、可変でもよい。可変の場合は、例えば、分析領域の中心と画像中心との間の距離が近いほど分析領域サイズを小さくし、分析領域の中心と画像中心との間の距離が遠いほど分析領域サイズを大きくするという方法を用いてもよい。

被写体中心点の分類には、例えば、計数値が所定の閾値以上の分析領域に含まれる被写体中心点を同一のクラスタに分類するという方法を用いてもよいし、当該領域とその周囲の分析領域に含まれる被写体中心点を同一のクラスタに分類するという方法を用いてもよい。また、計数値が所定の閾値以上の分析領域が隣接あるいは重複している場合は、例えば、これらの分析領域に含まれる被写体中心点を同一のクラスタに分類するという方法を用いてもよいし、異なるクラスタに分類するという方法を用いてもよい。

このように被写体中心点をクラスタリングすることで、非特許文献３乃至５のいずれか記載の手法を用いるよりも高速に処理できるという効果がある。
以上の処理の後、特徴点クラスタリング部４０３は、例えばｃ_ｉｊのクラスタ情報をｖ_ｉのクラスタ情報とすれば良い。

（５．２ 処理の流れ）
以下、図１５を参照しながら、本実施形態に係る画像処理装置１０の処理の流れを説明する。図１５は、画像処理装置１０の処理の流れを示すフローチャートである。

第１の局所特徴量生成部１０１は第１の画像から多数の特徴点を検出する。また、第２の局所特徴量生成部１０３は、第２の画像から多数の特徴点を検出する（Ｓ１５０１）。次に、第１の局所特徴量生成部１０１及び第２の局所特徴量生成部１０３は、各特徴点の座標位置から局所特徴量を生成する（Ｓ１５０３）。領域分割部１０５は、第１の局所特徴量群の各局所特徴量と第２の局所特徴量群の各局所特徴量との間の距離に基づいて、局所特徴量の対応関係、すなわち２画像間の特徴点の対応関係を求める（Ｓ１５０５）。次に、領域分割部１０５は、第１の座標位置情報群と第２の座標位置情報群と対応情報群とを用いて、第１の画像の２つの特徴点の間の距離と第２の画像の２つの特徴点間の距離との比率を算出する（Ｓ１５０７）。その上で領域分割部１０５は、第１の座標位置情報群と第２の座標位置情報群と対応情報群とを用いて、第１の画像の被写体の回転量を算出する（Ｓ１５０９）。そして、領域分割部１０５は、第１の座標位置情報群と対応情報群と比率情報群と回転情報群とを用いて、第１の画像の被写体中心点を推定するとともに、推定した被写体中心点をそれらの座標位置に基づいてクラスタリングする（Ｓ１５１１）。照合部１０７は、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する（Ｓ１５１３）。

（５．３ 本実施形態に係る効果）
以上説明したように、本実施形態に係る画像処理装置１０は、第１の画像の各特徴点の座標位置と、第２の画像の各特徴点の座標位置と、２画像間での特徴点の対応関係と、事前に生成した相対座標位置とを用いて被写体の中心点を推定する。そして、推定した被写体中心点をそれらの座標位置に基づいてクラスタリングすると共に、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する。これにより、本実施形態に係る画像処理装置１０も、第４の実施液体と同様の効果が得られる。

更に、本実施形態に係る画像処理装置１０は、第１の画像の各特徴点を被写体中心に集めてから、それらをクラスタリングするため、第４の実施形態よりも特徴点を精度よくクラスタリングできる。従って、画像内の同一または類似の被写体を第４の実施形態よりも精度高く多数識別できる。

（６ 第６の実施形態）
（６．１ 機能構成）
以下、第６の実施形態を説明する。まず、図１６を参照しながら、第６の実施形態に係る画像処理装置１０の機能構成を説明する。図１６は、第６の実施形態に係る画像処理装置１０の機能構成を示すブロック図である。

本実施形態に係る画像処理装置１０は、第３の実施形態と同様の構成である。しかしながら、領域分割部１０５の構成及び動作は第３の実施形態とは異なる。以下、図１７を参照しながら、領域分割部１０５の構成及び動作を説明する。

図１７は、領域分割部１０５の構成を示す図である。図１７に示すように、領域分割部１０５は、対応点探索部４０５と、相対座標位置データベース４１１と、特徴点クラスタリング部４０３とを含む。対応点探索部４０５の動作は第３の実施形態と、相対座標位置データベース４１１の構成は第５の実施形態と同様であるので、ここでは説明を省略する。以下、特徴点クラスタリング部４０３の動作を中心に説明する。

特徴点クラスタリング部４０３は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群と、対応点探索部４０５が出力した対応情報群と、相対座標位置データベース４１１に格納されている相対座標位置とを用いて、第１の画像の特徴点をクラスタリングするとともに、その結果であるクラスタ情報群を照合部１０７へと出力する。特徴点のクラスタリングには、例えば、第１の画像の特徴点のうち、第２の画像の任意の特徴点に対応する特徴点を対応情報群に基づいて多数選択する。その上で、選択した第１の画像の特徴点の座標位置に基づいて第１の画像の被写体中心点を推定すると共に、推定した被写体中心点を、それらの座標位置に基づいて第５の実施形態と同様の手法によりクラスタリングすることが考えられる。
被写体中心は、例えば、数１０と数１２とを用いて推定することが考えられる。

ここで、ｃ_ｉは被写体中心点の座標位置を、ｖ_ｉは第１の画像のｉ番目の特徴点の座標位置を、ｎは第１の画像のｉ番目の特徴点に対応する第２の画像の特徴点番号を、それぞれ示している。

（６．２ 処理の流れ）
図１８は、本実施形態に係る画像処理装置１０の処理の流れを示すフローチャートである。以下、図１８を参照しながら、画像処理装置１０の処理の流れを説明する。

第１の局所特徴量生成部１０１は、第１の画像から特徴点を多数検出する。また、第２の局所特徴量生成部１０３は、第２の画像から特徴点を多数検出する（Ｓ１８０１）。次に、第１の局所特徴量生成部１０１及び第２の局所特徴量生成部１０３は、各特徴点の座標位置から各特徴点に係る局所特徴量を生成する（Ｓ１８０３）。領域分割部１０５は、第１の局所特徴量群の各局所特徴量と第２の局所特徴量群の各局所特徴量との間の距離に基づいて局所特徴量の対応関係、すなわち２画像間での特徴点の対応関係を求める（Ｓ１８０５）。

領域分割部１０５は、第１の座標位置情報群と対応情報とを用いて、第１の画像の特徴点のうち、第２の画像の任意の特徴点に対応する特徴点を多数選択すると共に、選択した第１の画像の特徴点と相対座標位置データベース４１１に格納された相対座標位置とに基づいて、第１の画像の被写体中心点を推定するとともに、推定した被写体中心点をそれらの座標位置に基づいてクラスタリングする（Ｓ１８０７）。照合部１０７は、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する（Ｓ１８０９）。

（６．３ 本実施形態に係る効果）
以上説明したように、第６の実施形態に係る画像処理装置１０は、第１の画像の各特徴点の座標位置と、２画像間での特徴点の対応関係と、事前に生成した相対座標位置とを用いて被写体中心点を推定する。更に、推定した被写体中心点を、それらの座標位置に基づいてクラスタリングすると共に、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する。従って、第１の画像の被写体の獲得頂点と第２の画像の被写体の獲得頂点との間に合同変換が成り立つ場合に、第１の実施形態と同様の効果を得ることができる。

（７ 第７の実施形態）
（７．１ 機能構成）
続いて、図１９乃至図２１を参照しながら、第７の実施形態を説明する。図１９は、本実施形態に係る画像処理装置１０の機能構成を示す図である。本実施形態に係る画像処理装置１０は、第５の実施形態と同様の構成であるが、領域分割部１０５の構成及び動作は異なる。以下、図２０を参照しながら、領域分割部１０５の構成及び動作を説明する。

図２０は、本実施形態に係る領域分割部１０５の構成を示す図である。図２０に示すように、本実施形態に係る領域分割部１０５は、対応点探索部４０５、比率算出部４０７、回転量算出部４０９、及び特徴点クラスタリング部４０３を含む。比率算出部４０７の動作は第４の実施形態と、対応点探索部４０５及び回転量算出部４０９の動作は第５の実施形態と同様であるため、ここでは説明を省略する。以下、特徴点クラスタリング部４０３の動作を説明する。

特徴点クラスタリング部４０３は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群と、対応点探索部４０５が出力した対応情報群と、比率算出部４０７が出力した比率情報群と、回転量算出部４０９が出力した回転量情報群とを用いて、第１の画像の特徴点をクラスタリングする。その上で特徴点クラスタリング部４０３は、クラスタリングした結果得られる各クラスタに係る情報であるクラスタ情報群を照合部１０７へと出力する。

ここで、例えば算出された比率の差と回転量の差が小さい特徴点を同じクラスタに分類する（比率の差と回転量の差とが大きい特徴点を、異なるクラスタに分類する）ようにしても良い。例えば、グラフカットを用いてクラスタリングすることが考えられる。例えば、特徴点をノードとして、特徴点間の距離と、比率の差と回転量の差とに基づいてエッジ値を算出して（例えば、特徴点間の距離値が小さく、比率の差と回転量の差とが小さいほど、２つのノード間のエッジ値を大きくするなど）得られたグラフに対してグラフカットを提供しても良い。ここで、グラフカットには、例えば、ノーマライズドカットや、マルコフ・クラスタ・アルゴリズムを用いることが考えられる。

（７．２ 処理の流れ）
図２１は、本実施形態に係る画像処理装置１０の処理の流れを示すフローチャートである。図２１を参照しながら、以下、本実施形態に係る画像処理装置１０の処理を説明する。

第１の局所特徴量生成部１０１は、第１の画像から多数の特徴点を検出する。また、第２の局所特徴量生成部１０３は第２の画像から特徴点を多数検出する（Ｓ２１０１）。次に、第１の局所特徴量生成部１０１および第２の局所特徴量生成部１０３は、各特徴点の座標位置から局所特徴量を生成する（Ｓ２１０３）。

領域分割部１０５は、第１の局所特徴量群の各局所特徴量と、第２の局所特徴量群の各局所特徴量との間の距離に基づいて、局所特徴量の対応関係、すなわち２画像間の特徴点の対応関係を求める（Ｓ２１０５）。次に、領域分割部１０５は、第１の座標位置情報群と第２の座標位置情報群と対応情報群とを用いて、第１の画像の２つの特徴点間の距離と第２の画像の２つの特徴点間の距離との比率を算出する（Ｓ２１０７）。そして、領域分割部１０５は、第１の座標位置情報群と第２の座標位置情報群と対応情報群とを用いて、第１の画像の被写体の回転量を算出する（Ｓ２１０９）。その上で領域分割部１０５は、第１の座標位置情報群と対応情報群と比率情報群と回転情報群とを用いて、第１の画像の各特徴点をクラスタリングする（Ｓ２１１１）。照合部１０７は、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合すると共に、画像間で同一または類似の被写体を識別する（Ｓ２１１３）。

（７．３ 本実施形態に係る効果）
以上説明したように、第７の実施形態に係る画像処理装置１０は、第１の画像の各特徴点の座標位置と、第２の画像の各特徴点の座標位置と、２画像間での特徴点の対応関係とを用いて、第１の画像の被写体の回転量および比率を推定する。更に、それらに基づいて第１の画像の各特徴点をクラスタリングすると共に、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する。従って、第１の画像の各被写体の大きさや回転量が、近接する同一または類似の被写体同士で異なる場合、第１の実施形態と同様の効果を得ることができる。

（８ 第８の実施形態）
（８．１ 機能構成）
以下、図２２乃至２４を参照しながら、第８の実施形態を説明する。まず、図２２を参照しながら、本実施形態に係る画像処理装置１０の機能構成を説明する。図２２は、本実施形態に係る画像処理装置１０の機能構成を示す機能ブロック図である。

図２２に示すように、本実施形態に係る画像処理装置１０の機能構成は第５の実施形態と同様であるが、領域分割部１０５の構成及び動作が異なる。以下、図２３を参照しながら、領域分割部１０５の構成及び動作を説明する。

図２３は、本実施形態に係る領域分割部１０５の構成を示す図である。図２３に示すように、領域分割部１０５は対応点探索部４０５と回転量算出部４０９と特徴点クラスタリング部４０３とを含む。対応点探索部４０５及び回転量算出部４０９の動作は第５の実施形態と同様であるため、ここでは説明を省略する。以下、特徴点クラスタリング部４０３の動作を中心に説明する。

特徴点クラスタリング部４０３は、第１の局所特徴量生成部１０１が出力した第１の座標位置情報群と、対応点探索部４０５が出力した対応情報群と、回転量算出部４０９が出力した回転量情報群とを用いて、第１の画像の特徴点をクラスタリングすると共に、その結果を示すクラスタ情報群を照合部１０７へと出力する。このクラスタリングする際に、例えば算出された回転量の差が小さい特徴点を同じクラスタに分類する（回転量の差が大きい特徴点は異なるクラスタに分類する）ようにしても良い。また、例えばグラフカットを用いてクラスタリングしても良い。例えば、特徴点をノードとして、特徴点間の距離と、回転量の差に基づいてエッジ値を算出して（例えば、特徴点間の距離値が小さく、回転量の差が小さいほど、２つのノード間のエッジ値を大きくする）得られたグラフに対して、グラフカットを提供することも考えられる。グラフカットには、例えば、ノーマライズドカットを用いても良いし、マルコフ・クラスタ・アルゴリズムを用いても良い。

（８．２ 処理の流れ）
図２４は、本実施形態に係る画像処理装置１０の処理の流れを示すフローチャートである。以下、図２４を参照しながら、画像処理装置１０の処理の流れを説明する。

第１の局所特徴量生成部１０１は、第１の画像から多数の特徴点を検出する。また、第２の局所特徴量生成部１０３は第２の画像から特徴点を多数検出する（Ｓ２４０１）。次に、第１の局所特徴量生成部１０１および第２の局所特徴量生成部１０３は、各特徴点の座標位置から局所特徴量を生成する（Ｓ２４０３）。

領域分割部１０５は、第１の局所特徴量群の各局所特徴量と第２の局所特徴量群の各局所特徴量との間の距離に基づいて、局所特徴量の対応関係、すなわち２画像間の特徴点の対応関係を求める（Ｓ２４０５）。次に領域分割部１０５は、第１の座標位置情報群と第２の座標位置情報群と対応情報群とを用いて、第１の画像の被写体の回転量を算出する（Ｓ２４０７）。そして、領域分割部１０５は、第１の座標位置情報群と対応情報群と回転情報群とを用いて、第１の画像の各特徴点をクラスタリングする（Ｓ２４０９）。照合部１０７は、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する（Ｓ２４１１）。

（８．３ 本実施形態に係る効果）
以上説明したように、第８の実施形態に係る画像処理装置１０は、第１の画像の各特徴点の座標位置と、第２の画像の各特徴点の座標位置と、２画像間の特徴点の対応関係とを用いて、第１の画像の被写体の回転量を推定する。そして、推定した回転量と第１の座標位置情報群とに基づいて第１の画像の各特徴点をクラスタリングすると共に、第１の局所特徴量群と第２の局所特徴量群とをクラスタ単位で照合することにより、画像間で同一または類似の被写体を識別する。従って、第１の画像の各被写体の回転量が、近接する同一または類似の被写体同士で異なる場合、第１の実施形態と同様の効果を得ることができる。

（９ 付記事項）
尚、前述の各実施形態の構成は、組み合わせたり或いは一部の構成部分を入れ替えたりしてもよい。また、本発明の構成は前述の実施形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加えてもよい。
尚、前述の各実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。

（付記１）
第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成する第１の特徴量生成手段と、前記第１の座標位置情報群に基づき、前記第１の画像の特徴点をクラスタリングする領域分割手段と、クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合する照合手段とを有する画像処理装置。

（付記２）
前記領域分割手段は、各特徴点間の距離に応じて前記第１の画像の特徴点をクラスタリングする、付記１記載の画像処理装置。

（付記３）
前記領域分割手段は、前記第１の局所特徴量群の各局所特徴量同士の類似度と、前記第１の座標位置情報群とを用いて前記第１の画像の特徴点をクラスタリングする、付記１又は付記２記載の画像処理装置。

（付記４）
前記領域分割手段は、前記第１の局所特徴量群と、前記第２の局所特徴量群との間の特徴量間距離に基づいて、前記第１の画像と前記第２の画像との特徴点の対応関係を示す対応情報群を算出すると共に、当該対応情報群と前記第１の座標位置情報群とを用いて前記第１の画像の特徴点をクラスタリングする、付記１乃至付記３のいずれか１項記載の画像処理装置。

（付記５）
前記領域分割手段は、第２の画像の各特徴点と第２の画像の予め定められた基準点との相対座標位置と、前記対応情報群と、前記第１の座標位置情報群とに基づいて推定した、前記第１の画像での前記基準点の座標位置に基づいて前記第１の画像の特徴点をクラスタリングする、付記４記載の画像処理装置。

（付記６）
前記領域分割手段は、前記第１の座標位置情報群と、前記第２の画像から検出された特徴点の座標位置情報である第２の座標位置情報群と、前記対応情報群とを用いて、前記第１の画像の任意の２つの特徴点間の距離と、当該２つの特徴点に対応する前記第２の画像の２つの特徴点間の距離との比率を算出すると共に、前記第１の座標位置情報群と、前記第２の座標位置情報群と、前記対応情報群とを用いて前記第１の画像の被写体の回転量を算出する、付記５に記載の画像処理装置。

（付記７）
前記領域分割手段は、前記比率と前記回転量との少なくとも一方と、前記第１の座標位置情報群とを用いて前記第１の画像の特徴点をクラスタリングする、付記６記載の画像処理装置。

（付記８）
前記領域分割手段は、前記回転量と、前記比率と、前記相対座標位置と、前記第１の座標位置情報群とを用いて推定した、前記第２の画像の基準点の前記第１の画像での座標位置を用いて、前記第１の画像の特徴点をクラスタリングする、付記６又は付記７に記載の画像処理装置。

（付記９）
第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成するステップと、前記第１の座標位置情報群に基づき、前記第１の画像の特徴点をクラスタリングするステップと、クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合するステップとを備える画像処理方法。

（付記１０）
第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成するステップと、前記第１の座標位置情報群に基づき、前記第１の画像の特徴点をクラスタリングするステップと、クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合するステップとを画像処理装置に実行させるプログラム。

この出願は、２０１２年６月２９日に出願された日本出願特願２０１２−１４７２３９を基礎とする優先権を主張し、その開示の全てをここに取り込む。

１０・・・画像処理装置、１０１・・・第１の局所特徴量生成部、１０３・・・第２の局所特徴量生成部、１０５・・・領域分割部、１０７・・・照合部、４０１・・・類似度算出部、４０３・・・特徴点クラスタリング部、４０５・・・対応点探索部、４０７・・・比率算出部、４０９・・・回転量算出部、４１１・・・相対座標位置データベース

Claims (9)

1. 第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成する第１の特徴量生成手段と、
   前記第１の局所特徴量群と、前記第２の局所特徴量群との間の特徴量間距離に基づいて、前記第１の画像と前記第２の画像との特徴点の対応関係を示す対応情報群を算出すると共に、当該対応情報群と前記第１の座標位置情報群とを用いて前記第１の画像の特徴点をクラスタリングする領域分割手段と、
   クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合する照合手段と
   を有する画像処理装置。
2. 前記領域分割手段は、各特徴点間の距離に応じて前記第１の画像の特徴点をクラスタリングする、
   請求項１記載の画像処理装置。
3. 前記領域分割手段は、前記第１の局所特徴量群の各局所特徴量同士の類似度と、前記第１の座標位置情報群とを用いて前記第１の画像の特徴点をクラスタリングする、
   請求項１又は請求項２記載の画像処理装置。
4. 前記領域分割手段は、第２の画像の各特徴点と第２の画像の予め定められた基準点との相対座標位置と、前記対応情報群と、前記第１の座標位置情報群とに基づいて推定した、前記第１の画像での前記基準点の座標位置に基づいて前記第１の画像の特徴点をクラスタリングする、
   請求項１記載の画像処理装置。
5. 前記領域分割手段は、
   前記第１の座標位置情報群と、前記第２の画像から検出された特徴点の座標位置情報である第２の座標位置情報群と、前記対応情報群とを用いて、前記第１の画像の任意の２つの特徴点間の距離と、当該２つの特徴点に対応する前記第２の画像の２つの特徴点間の距離との比率を算出すると共に、
   前記第１の座標位置情報群と、前記第２の座標位置情報群と、前記対応情報群とを用いて前記第１の画像の被写体の回転量を算出する、
   請求項４に記載の画像処理装置。
6. 前記領域分割手段は、前記比率と前記回転量との少なくとも一方と、前記第１の座標位置情報群とを用いて前記第１の画像の特徴点をクラスタリングする、
   請求項５記載の画像処理装置。
7. 前記領域分割手段は、前記回転量と、前記比率と、前記相対座標位置と、前記第１の座標位置情報群とを用いて推定した、前記第２の画像の基準点の前記第１の画像での座標位置を用いて、前記第１の画像の特徴点をクラスタリングする、
   請求項５又は請求項６に記載の画像処理装置。
8. 第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成するステップと、
   前記第１の局所特徴量群と、前記第２の局所特徴量群との間の特徴量間距離に基づいて、前記第１の画像と前記第２の画像との特徴点の対応関係を示す対応情報群を算出すると共に、当該対応情報群と前記第１の座標位置情報群とを用いて前記第１の画像の特徴点をクラスタリングするステップと、
   クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合するステップと
   を備える画像処理方法。
9. 第１の画像から検出される複数の特徴点に対して、それぞれの特徴点を含む複数の局所領域の特徴量である局所特徴量を含む第１の局所特徴量群と、座標位置情報を含む第１の座標位置情報群とを生成するステップと、
   前記第１の局所特徴量群と、前記第２の局所特徴量群との間の特徴量間距離に基づいて、前記第１の画像と前記第２の画像との特徴点の対応関係を示す対応情報群を算出すると共に、当該対応情報群と前記第１の座標位置情報群とを用いて前記第１の画像の特徴点をクラスタリングするステップと、
   クラスタ単位で、前記第１の局所特徴量群と、第２の画像から検出された特徴点の局所特徴量である第２の局所特徴量群とを照合するステップと
   を画像処理装置に実行させるプログラム。
   

Images