(57)【特許請求の範囲】
【請求項１】
第一画像の複数の特徴点ごとの第一局所特徴量と、撮像対象を撮像して得られた第二画像の複数の特徴点ごとの第二局所特徴量と、を抽出する抽出手段と、
前記第二画像のそれぞれの前記特徴点に対応する前記撮像対象の奥行情報を保持する保持手段と、
前記奥行情報に基づいて、少なくとも１つの距離範囲を特定する特定手段と、
前記距離範囲について得られた、前記第二局所特徴量と前記第一局所特徴量との類似度が、所定値以上であれば、前記第二画像が前記第一画像と類似すると判定する判定手段と、
を備え、複数の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の少なくとも二つ以上が、前記所定値以上であれば、前記判定手段は、前記所定値以上の前記類似度の合計に基づいて、前記第二画像が前記第一画像と類似するかを判定することを特徴とする画像処理装置。
【請求項２】
第一画像の複数の特徴点ごとの第一局所特徴量と、撮像対象を撮像して得られた第二画像の複数の特徴点ごとの第二局所特徴量と、を抽出する抽出手段と、
前記第二画像のそれぞれの前記特徴点に対応する前記撮像対象の奥行情報を保持する保持手段と、
前記奥行情報に基づいて、少なくとも１つの距離範囲を特定する特定手段と、前記距離範囲について得られた、前記第二局所特徴量と前記第一局所特徴量との類似度が、所定値以上であれば、前記第二画像が前記第一画像と類似すると判定する判定手段と、
を備え、
複数の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の少なくとも二つ以上が、前記所定値以上であれば、前記判定手段は、隣り合う二つ以上の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の合計に基づいて、前記第二画像が前記第一画像と類似するかを判定することを特徴とする画像処理装置。
【請求項３】
前記特定手段によって特定された一つの前記距離範囲は、前記第二画像における前景部分又は背景部分に対応し、前記前景部分又は前記背景部分と前記第一画像との類似度が、前記所定値以上であれば、前記判定手段は、前記第二画像が前記第一画像と類似すると判定することを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記特定手段によって特定された複数の前記距離範囲は、前記第二画像における前景部分および背景部分に対応し、前記前景部分と前記第一画像との類似度と、前記背景部分と前記第一画像との類似度との何れかが、前記所定値以上であれば、前記判定手段は、前記第二画像が前記第一画像と類似すると判定することを特徴とする請求項１に記載の画像処理装置。
【請求項５】
前記特定手段によって特定された複数の前記距離範囲は、前記第二画像における前景部分および背景部分に対応し、前記前景部分と前記第一画像との類似度と、前記背景部分と前記第一画像との類似度とが、それぞれ前記所定値以上であれば、前記判定手段は、前記第二画像が前記第一画像と類似すると判定することを特徴とする請求項１に記載の画像処理装置。
【請求項６】
前記保持手段は、前記抽出手段で抽出された前記第二画像の前記複数の特徴点ごとの前記第二局所特徴量と前記第二画像とを特定する情報と、前記第二画像のそれぞれの前記特徴点に対応する前記撮像対象の前記奥行情報と、を対応付けて保持することを特徴とする請求項１乃至５の何れか１項に記載の画像処理装置。
【請求項７】
前記特定手段は、前記距離範囲に対応する前記第二局所特徴量を特定し、前記保持手段は、前記距離範囲に対応する前記第二局所特徴量と前記距離範囲とを対応付けて保持することを特徴とする請求項１乃至６の何れか１項に記載の画像処理装置。
【請求項８】
前記第二局所特徴量と前記第一局所特徴量との前記類似度は、前記第二局所特徴量と類似する前記第一局所特徴量のペア数であることを特徴とする請求項１乃至７の何れか１項に記載の画像処理装置。
【請求項９】
前記奥行情報は、前記画像処理装置の外部にある生成手段によって生成され、前記生成手段から前記撮像対象までの距離を示す奥行値であることを特徴とする請求項１乃至８の何れか１項に記載の画像処理装置。
【請求項１０】
第一画像の複数の特徴点ごとの第一局所特徴量と、撮像対象を撮像して得られた第二画像の複数の特徴点ごとの第二局所特徴量と、を抽出する抽出工程と、
前記第二画像のそれぞれの前記特徴点に対応する前記撮像対象の奥行情報を保持手段に保持させる工程と、
前記奥行情報に基づいて、少なくとも１つの距離範囲を特定する特定工程と、
前記距離範囲について得られた、前記第二局所特徴量と前記第一局所特徴量との類似度が、所定値以上であれば、前記第二画像が前記第一画像と類似すると判定する判定工程と、
を備え、
複数の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の少なくとも二つ以上が、前記所定値以上であれば、前記判定工程では、前記所定値以上の前記類似度の合計に基づいて、前記第二画像が前記第一画像と類似するかを判定することを特徴とする画像処理方法。
【請求項１１】
第一画像の複数の特徴点ごとの第一局所特徴量と、撮像対象を撮像して得られた第二画像の複数の特徴点ごとの第二局所特徴量と、を抽出する抽出工程と、
前記第二画像のそれぞれの前記特徴点に対応する前記撮像対象の奥行情報を保持手段に保持させる工程と、
前記奥行情報に基づいて、少なくとも１つの距離範囲を特定する特定工程と、前記距離範囲について得られた、前記第二局所特徴量と前記第一局所特徴量との類似度が、所定値以上であれば、前記第二画像が前記第一画像と類似すると判定する判定工程と、
を備え、
複数の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の少なくとも二つ以上が、前記所定値以上であれば、前記判定工程では、隣り合う二つ以上の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の合計に基づいて、前記第二画像が前記第一画像と類似するかを判定することを特徴とする画像処理方法。
【請求項１２】
第一画像の複数の特徴点ごとの第一局所特徴量と、撮像対象を撮像して得られた第二画像の複数の特徴点ごとの第二局所特徴量と、を抽出する抽出ステップと、
前記第二画像のそれぞれの前記特徴点に対応する前記撮像対象の奥行情報を保持手段に保持させるステップと、
前記奥行情報に基づいて、少なくとも１つの距離範囲を特定する特定ステップと、
前記距離範囲について得られた、前記第二局所特徴量と前記第一局所特徴量との類似度が、所定値以上であれば、前記第二画像が前記第一画像と類似すると判定する判定ステップと、
をコンピュータに実行させ、
前記判定ステップでは、複数の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の少なくとも二つ以上が、前記所定値以上であれば、前記所定値以上の前記類似度の合計に基づいて、前記第二画像が前記第一画像と類似するかを判定することを特徴とするプログラム。
【請求項１３】
第一画像の複数の特徴点ごとの第一局所特徴量と、撮像対象を撮像して得られた第二画像の複数の特徴点ごとの第二局所特徴量と、を抽出する抽出ステップと、
前記第二画像のそれぞれの前記特徴点に対応する前記撮像対象の奥行情報を保持手段に保持させるステップと、
前記奥行情報に基づいて、少なくとも１つの距離範囲を特定する特定ステップと、前記距離範囲について得られた、前記第二局所特徴量と前記第一局所特徴量との類似度が、所定値以上であれば、前記第二画像が前記第一画像と類似すると判定する判定ステップと、
をコンピュータに実行させ、
前記判定ステップでは、複数の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の少なくとも二つ以上が、前記所定値以上であれば、隣り合う二つ以上の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の合計に基づいて、前記第二画像が前記第一画像と類似するかを判定することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像の局所特徴量を比較する技術に関するものである。
【背景技術】
【０００２】
画像の局所的な特徴量（局所特徴量）を用いて類似画像を検索する方法が提案されている。この方法では、まず、画像から特徴的な点（局所特徴点）を抽出する。次に、当該局所特徴点とその周辺の画像情報とに基づいて、当該局所特徴点に対応する特徴量（局所特徴量）を計算する。
【０００３】
局所特徴量を利用する手法においては、局所特徴量を回転不変、拡大・縮小不変となる複数の要素で構成される情報として定義する。これにより、画像を回転させたり、拡大又は縮小させたりした場合であっても、検索を可能にする。局所特徴量は一般的にベクトルとして表現される。ただし、局所特徴量が回転不変、拡大・縮小不変であることは理論上の話であり、実際のデジタル画像においては、画像の回転や拡大・縮小処理前の局所特徴量と処理後の対応する局所特徴量との間に若干の変動が生じる。
【０００４】
回転不変の局所特徴量抽出のために、局所特徴点周辺の局所領域の画素パターンから主方向を算出し、局所特徴量算出時に主方向を基準に局所領域を回転させて方向の正規化を行う。また、拡大・縮小不変の局所特徴量を算出するために、異なるスケールの画像を内部で生成し、各スケールの画像からそれぞれ局所特徴点の抽出と局所特徴量の算出を行う。ここで、内部で生成した一連の異なるスケールの画像集合は一般的にスケールスペースと呼ばれる。
【０００５】
上述の方式により、１枚の画像から複数の局所特徴点が抽出される。局所特徴量を用いた画像検索では、それぞれの局所特徴点から算出した局所特徴量同士の比較を行うことによりマッチングを行う。多く利用されている投票方式（特許文献１）では、入力画像から抽出された、各特徴点の局所特徴量に類似する特徴量を持つ特徴点が登録画像に存在すれば、その比較先の登録画像に対して１票を投票する。その投票数の多い登録画像ほど比較元画像と類似するとするものである。なお、入力画像は、比較元画像、クエリ画像または検索元画像とも言う。登録画像は、比較先画像または検索先画像とも言う。
【０００６】
また、画像照合処理又は画像検索処理を高精度に行うために、事前に画像から検索したい対象オブジェクトを切り出す方法がある（特許文献２）。この方法では、ユーザがペン入力部を介して画像上の対象オブジェクトの輪郭情報を入力し、背景を取り除いた部分のオブジェクト画像を抽出している。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００９−２８４０８４号
【特許文献２】特許平１０−２５４９０１号
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、特許文献１の投票方式では、撮像位置からの距離が異なる前景と背景の特徴量が混在した画像について、前景から抽出される特徴量と背景から抽出される特徴量について区別せずに、他の画像との類似度が決定されていた。例えば、図１に示すような前景よりも背景の特徴点が多い画像との類似度を求める場合は、背景にある特徴点の局所特徴量が所定値以上の類似度を持ってしまう可能性がある。この場合に、背景にある特徴量が投票値に影響し、得られた投票値がより大きくなることがあった。そのため、画像間の適正な類似度が得られないことがあり、照合精度を低下させていた。また、画像検索に適用して、複数の類似画像を類似度でソートして検索結果を作成する場合などに、適正な類似度が得られないので、検索精度を低下させていた。
【０００９】
また、特許文献２の方式では、ユーザが画像にあるすべての対象オブジェクトに対してユーザがペン入力による抽出処理のような特別な処理を行わなければならないので、ユーザの処理負荷が高い問題があった。
【００１０】
本発明は、上記の問題に鑑みてなされたものであり、ユーザが特別な処理をしなくても、比較対象の特徴点に絞って、画像照合又は画像検索を行うことを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、本発明の画像処理装置は、第一画像の複数の特徴点ごとの第一局所特徴量と、撮像対象を撮像して得られた第二画像の複数の特徴点ごとの第二局所特徴量と、を抽出する抽出手段と、前記第二画像のそれぞれの前記特徴点に対応する前記撮像対象の奥行情報を保持する保持手段と、前記奥行情報に基づいて、少なくとも１つの距離範囲を特定する特定手段と、前記距離範囲について得られた、前記第二局所特徴量と前記第一局所特徴量との類似度が、所定値以上であれば、前記第二画像が前記第一画像と類似すると判定する判定手段と、を備え、前記判定手段は、複数の前記距離範囲ごとに得られた、前記第二局所特徴量と前記第一局所特徴量との前記類似度の少なくとも二つ以上が、前記所定値以上であれば、前記所定値以上の前記類似度の合計に基づいて、前記第二画像が前記第一画像と類似するかを判定することを特徴とする。
【発明の効果】
【００１２】
本発明によれば、比較先画像の奥行情報を用いて、比較先画像の特徴量を距離範囲ごとに特定することによって、ユーザが特別な処理をしなくても、比較対象の特徴点に絞って、画像照合処理又は画像検索処理を行うことができる。
【図面の簡単な説明】
【００１３】
【図１】画像処理装置が処理する画像の一例である。
【図２】第１の実施形態におけるコンピュータ装置の構成例の図である。
【図３】第１の実施形態における画像照合装置の構成例の図である。
【図４】第１の実施形態における投票のデータ構造の例の説明図である。
【図５】第１の実施形態における画像照合処理の流れを説明するためのフローチャートである。
【図６】第１の実施形態における局所特徴量抽出処理の流れを説明するためのフローチャートである。
【図７】縮小画像の説明図である。
【図８】第２の実施形態における画像検索装置の構成例の図である。
【図９】（ａ）第２の実施形態における画像インデックス及び投票のデータ構造の例の説明図である。（ｂ）クラスタごとに生成された投票値の例の説明図である。（ｃ）投票値から類似度を求める例の説明図である。
【図１０】第２の実施形態における登録処理の流れを説明するためのフローチャートである。
【図１１】第２の実施形態における画像検索処理の流れを説明するためのフローチャートである。
【図１２】第２の実施形態における量子化空間の説明図である。
【図１３】第３の実施形態における画像検索処理の流れを説明するためのフローチャートである。
【図１４】投票値から類似度を求める例の説明図である。
【発明を実施するための形態】
【００１４】
［第１の実施形態］
本実施形態のサーバ装置やクライアント装置を構成するコンピュータ装置の構成について、図２のブロック図を参照して説明する。サーバ装置やクライアント装置はそれぞれ単一のコンピュータ装置で実現してもよいし、必要に応じた複数のコンピュータ装置に各機能を分散して実現するようにしてもよい。複数のコンピュータ装置で構成される場合は、互いに通信可能なようにＬｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＬＡＮ）などで接続されている。コンピュータ装置は、パーソナルコンピュータ（ＰＣ）やワークステーション（ＷＳ）等の情報処理装置によって実現することができる。
【００１５】
図２において、ＣＰＵ２０１はコンピュータ装置２００全体を制御するＣｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔである。ＲＯＭ２０２は変更を必要としないプログラムやパラメータを格納するＲｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙである。ＲＡＭ２０３は外部装置などから供給されるプログラムやデータを一時記憶するＲａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙである。記憶装置２０４はコンピュータ装置２００に固定して設置されたハードディスクやメモリカードなどの記憶装置である。なお、記憶装置２０４は、コンピュータ装置２００内部にあるハードディスクでもよい、コンピュータ装置２００から着脱可能なフレキシブルディスク（ＦＤ）やＣＤ等の光ディスク、磁気や光カード、ＩＣカード、メモリカードなどを含んでもよい。入力デバイスインターフェイス２０５はユーザの操作を受け、データを入力するポインティングデバイスやキーボードなどの入力デバイス２０９とのインターフェイスである。出力デバイスインターフェイス２０６はコンピュータ装置２００の保持するデータや供給されたデータを表示するためのモニタ２１０とのインターフェイスである。通信インターフェイス２０７はインターネットなどのネットワーク回線２１１や、デジタルカメラ２１２、デジタルビデオカメラ２１３、スマートフォン２１４などの撮像装置に接続するための通信インターフェイスである。システムバス２０８は各ユニット２０１〜２０７を通信可能に接続する伝送路である。
【００１６】
本実施形態で用いる撮像装置に、撮像対象の奥行情報を生成する生成手段（非図示）が含まれる。撮像対象の奥行情報は、生成手段から撮像対象までの距離を示す奥行値又は距離情報である。
【００１７】
後述する各動作は、ＲＯＭ２０２等のコンピュータ読み取り可能な記憶媒体に格納されたプログラムをＣＰＵ２０１が実行することにより実行される。
【００１８】
［画像照合装置の構成］
本実施形態の画像処理装置を画像照合装置として用いた例を説明する。画像照合装置では、２枚の画像が類似するか否かを判定する。本実施形態では、画像照合装置が処理する２枚の画像を比較元画像と比較先画像として説明する。以下、本実施形態の画像照合装置の構成について図３を用いて説明する。画像照合装置が、画像入力部３０１、特徴量抽出部３０２、データ保持部３０３、特徴量特定部３０５、特徴量比較部３０６、類似判定部３０７及び照合結果出力部３０８を含む。
【００１９】
画像入力部３０１は、入力デバイス２０９などを介して、画像照合装置の外部から比較元画像（クエリ画像）を入力する。なお、比較先画像（登録画像）が記憶装置２０４に記憶されているので、入力する必要はない。
【００２０】
特徴量抽出部３０２は、比較元画像及び比較先画像から特徴的な点（局所特徴点）を抽出し、抽出された局所特徴点とその周辺の画像情報とに基づいて、局所特徴点に対応する特徴量（局所特徴量）を計算する。局所特徴量抽出処理の詳細については、図６と図７を用いて後ほど説明する。
【００２１】
データ保持部３０３は撮像対象の奥行情報を保持しているので、データ保持部３０３から特徴量の算出領域の奥行情報を取得する。また、奥行値を保持している時は、画像における特徴点の位置に対応する撮像対象の奥行値を取得する。あるいは、撮像画像と距離画像が別々のデータとしてあるとき、撮像画像の画素と距離画像のマッピングを予め保持しておき、そのマッピングに従って特徴点の位置に対応する撮像対象の奥行値を取得する。また、距離画像にノイズが多い場合などは、予め距離画像に平滑化処理を行ってノイズを低減するなどしてから、奥行値を取得するようにしてもよい。なお、本実施形態における奥行情報の取得方法は、これらの方法に限定されるものではない。
【００２２】
特徴量特定部３０５は、まず、特徴点の位置に対応する撮像対象の奥行値に基づいて、複数の距離範囲を特定する。例えば、撮像対象の奥行値は１０〜１００メールの距離範囲に分布する場合は、１０〜１００メールの距離範囲を１０〜２０メール、２０〜３０メートル、３０〜４０メールなどの複数の１０メートル間隔の距離範囲に分ける。本実施形態では、この処理を奥行値の階調化と呼ぶ。奥行値を階調化した後に、奥行値に基づいて特徴量をクラスタリングする。具体的には、特徴量抽出部３０２で得た特徴量ごとに、奥行情報保持部３０３で奥行値を得る。そして、奥行値を階調化することで特徴量をクラスタリングする。例えば、予め階調化の幅を決めておき、この階調幅で特徴量の奥行値を割ったときの商を求める。この階調の幅は一定間隔を示す距離であり、先の例では１０メートルの間隔を示す距離である。そして、商が同じ特徴量を同じクラスタに割り当てることでクラスタリングを行う。これによって、所定の奥行値の幅（距離範囲）ごとに特徴量を特定して分離することができるため、前景にある撮像対象と背景にある撮像対象とに対応する画像の特徴量を分離することができる。
【００２３】
また、クラスタリングの一例として、画像の２値化処理などに使われる判別分析法等を用いてクラスタを決定してもよい。これによって、２つのクラスタに特徴量を分けることができるため、前景と背景に特徴量を分けることができる。
【００２４】
さらに、階層的クラスタリングなどを用いてクラスタリングしてもよい。本実施形態の階層的クラスタリングは、複数の連続した距離範囲に対応して特徴量をクラスタリングして複数のクラスタが得られた場合に行う。この場合に、隣り合う二つの距離範囲に対応する二つのクラスタに割り当てられた特徴量の数がそれぞれ所定値以上であれば、この二つのクラスタを一つのクラスタに統合する。この処理を繰り返すと、奥行値の異なる複数の撮像対象のそれぞれに対応した特徴量のクラスタが得られる。これによって、奥行値の異なる複数のオブジェクトが前景として存在するとき、複数のオブジェクトのそれぞれに対応した特徴量のクラスタを得ることができる。
【００２５】
なお、本実施形態では、奥行値の小さい撮像対象（オブジェクト）は撮像時の視点から見た前景部分であり、奥行値の大きい撮像対象（オブジェクト）は撮像時の視点から見た撮像対象の背景部分である。
【００２６】
また、本実施形態における奥行値を用いた特徴量のクラスタリング方法は、これらの方法に限定されるものではない。
【００２７】
特徴量比較部３０６は、比較元画像の特徴量と比較先画像の特徴量とを比較し、比較元画像の特徴量と類似する比較先画像の特徴量をペアとして求める。具体的には、特徴量抽出部３０２で抽出された比較元画像の特徴量と比較先画像の特徴量とのベクトル間のユークリッド距離を算出する。算出された二つの特徴量のベクトル間のユークリッド距離が所定値以下の場合、二つの特徴量が類似していると判断し、この比較元画像の特徴量と比較先画像の特徴量とをペアとして求める。
【００２８】
類似判定部３０７は、比較先画像のクラスタごとに、ペア数を数え上げる。具体的には、ペアをなした特徴量に対応する「クラスタ」に対して１票を投票していく。これによって、クラスタごとにペアの数を数え上げていく。
【００２９】
概念的には、図４に示すように、クラスタＩＤごとに投票値が生成されることになる。なお、ペア数４０１はクラスタＩＤ：００２の投票値を表している。ペア数４０２はクラスタＩＤ：００５の投票値を表している。この図では、クラスタＩＤが小さい方が、奥行きが手前にあるクラスタを表している。そのため、前景にあたるクラスタのペア数４０１と背景にあたるクラスタのペア数４０２が分かれて求まることが分かる。このように、所定距離範囲ごとにペア数を数え上げることがなされる。
【００３０】
類似判定部３０７は、比較先画像のクラスタをもとに、所定のペア数を有するクラスタを特定して、該クラスタのペア数から比較元画像と比較先画像の類似度を生成する。具体的には、最大のペア数を有するクラスタを特定して、該クラスタのペア数を類似度とする。あるいは、該最大値の８０％に相当する値以上のペア数を有するクラスタを特定して、特定されたクラスタのペア数を和算したものを類似度としてもよい。あるいは、予め定めた閾値以上のペア数を有するクラスタを特定して、特定されたクラスタのペア数を和算したものを用いてもよい。類似度が所定値以上であれば、類似判定部３０７は、比較先画像と比較元画像とが類似すると判定する。
【００３１】
また、確認したい対象オブジェクトの奥行値がどの距離範囲にあるのかを事前に分かっている場合は、類似判定部３０７は、クラスタＩＤごとに投票値を生成する必要はなく、特定の距離範囲に対応するクラスタＩＤだけに投票値を生成することもできる。図４の例では、距離範囲が正確に分かる場合は、クラスタＩＤ：００２の投票値だけを生成すればよい。距離範囲が正確に分からないが、対象オブジェクトが前景にあると分かっている場合は、クラスタＩＤ：００１〜００３の投票値だけを生成すればよい。
【００３２】
なお、本実施形態で求めた画像間の類似度は、特定されたクラスタのペア数又はペア数を和算したものであるが、これに限らない。例えば、ペア数を数えないで、所定値以下の二つの特徴量のベクトル間のユークリッド距離をパラメータとして用いて画像間の類似度を求めてもよい。
【００３３】
照合結果出力部３０８は、類似判定部３０７の判定した結果をモニタ２１０などに出力する。
【００３４】
本実施形態の画像照合処理の流れを図５に示すフローチャートを用いて説明する。
【００３５】
ステップＳ５０１では、比較元画像と比較先画像から局所特徴量を抽出する。詳細な処理内容については、局所特徴量抽出処理として図６、図７を用いて別途説明する。
【００３６】
ステップＳ５０２では、比較先画像（登録画像）の特徴量をクラスタリングする。具体的には、データ保持部３０３から画像における各特徴点の位置に対応する撮像対象の奥行き値を得る。そして、奥行値に基づいて、特徴量特定部３０５によって各特徴点に対応する特徴量はクラスタに分ける。
【００３７】
ステップＳ５０３〜ステップＳ５０６では、比較元画像から抽出された局所特徴量に類似する比較先画像の特徴量を見つけ、見つけた特徴量に対応する「クラスタ」に対して１票を投票する処理を行う。概念的には、図４に示すように、クラスタＩＤごとに投票値を生成することを行う。以下はステップごとに説明する。
【００３８】
ステップＳ５０３では、ステップＳ５０２で得た比較元画像の局所特徴量を順に処理するためのループであり、特徴量には１から順に番号が割り当てられているものとする。これを変数ｉとして用いて参照するため、はじめにｉを１に初期化する。さらに、ｉが局所特徴量の個数以下であるときステップＳ５０４へ移り、これを満たさないときループを抜けてステップＳ５０７へ移る。
【００３９】
ステップＳ５０４では、特徴量比較部３０６によって、比較元画像の特徴量ｉと類似する比較先画像の特徴量を見つける。具体的には、比較元画像の特徴量ｉと、比較先画像の全ての特徴量との間でユークリッド距離を求めて、所定閾値以下のユークリッド距離にある比較先画像の特徴量を特定する。
【００４０】
ステップＳ５０５では、類似判定部３０７によって、「クラスタ」に対してペア数を加算することが行われる。具体的には、図４に示すような情報を保持するために、クラスタＩＤと投票値を保持するリストなどを予め用意しておく。そして、ステップＳ５０４で得た類似する特徴量に対応するクラスタＩＤの投票値に１加算する。これをステップＳ５０４で見つけた全ての特徴量に対して行う。
【００４１】
ステップＳ５０６は、ループの終端であり、ｉに１を加算してステップＳ５０３へ戻る。
【００４２】
ステップＳ５０７では、類似判定部３０７によって、画像間の類似度が生成される。具体的には、最大の投票値を持つクラスタを特定して、このクラスタの投票値を類似度とする。これによって、比較元画像と比較先画像の類似度が生成される。類似度が所定値以上であれば、類似判定部３０７は、比較元画像と比較先画像とが類似すると判定する。
【００４３】
以下では、本実施例で用いた「局所特徴量抽出処理」の一例について説明を行う。
【００４４】
［局所特徴量抽出処理］
画像から局所特徴量を抽出する方法の一例について、図６を用いて説明する。
【００４５】
ステップＳ６０１で、入力された画像から輝度成分を抽出し、抽出した輝度成分に基づいて輝度成分画像を生成する。
【００４６】
次にステップＳ６０２で、輝度成分画像を倍率（縮小率）ｐに従って順次縮小することを繰り返し、オリジナルのサイズの画像から段階的に縮小した、オリジナルの画像を含めてｎ枚の縮小画像を生成する。ここで、倍率ｐ及び縮小画像の枚数ｎは予め決められているものとする。
【００４７】
図７は、縮小画像生成処理で得られた縮小画像の一例を示す図である。図７に示す例は、倍率ｐが「２の−（１／４）乗」、縮小画像の枚数ｎが「９」の場合である。もちろん、倍率ｐは必ずしも「２の−（１／４）乗」で無くとも良い。図７において、画像７０１はステップＳ６０１で生成された輝度成分画像である。縮小画像７０２は当該輝度成分画像７０１から倍率ｐに従って再帰的に４回の縮小処理を行って得られた縮小画像である。そして、縮小画像７０３は当該輝度成分画像７０１から倍率ｐに従って８回縮小された縮小画像である。
【００４８】
この例では、縮小画像７０２は輝度成分画像７０１が１／２に縮小された画像となり、縮小画像７０３は輝度成分画像７０１が１／４に縮小された画像となる。尚、画像を縮小する方法は何れの方法でも良く、本実施形態では、線形補間による縮小方法により縮小画像を生成するものとする。
【００４９】
次に、ステップＳ６０３では、ｎ枚の縮小画像の各々に画像の回転があってもロバスト（ｒｏｂｕｓｔ）に抽出されるような局所的な特徴点（局所特徴点）を抽出する。この局所特徴点の抽出方法として、本実施形態ではＨａｒｒｉｓ作用素を用いる。
【００５０】
具体的には、Ｈａｒｒｉｓ作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素及び当該画素の８近傍にある画素（合計９画素）の画素値を調べる。そして、当該画素が局所極大になる（当該９画素の中で当該画素の画素値が最大になる）点を局所特徴点として抽出する。ここで、当該画素が局所極大になったときでも、当該画素の値がしきい値以下の場合には局所特徴点として抽出しないようにする。
【００５１】
なお、局所特徴点を抽出可能な方法であれば、上述のＨａｒｒｉｓ作用素による特徴点抽出方法に限らず、どのような特徴点抽出方法を用いてもよい。
【００５２】
次に、ステップＳ６０４で、ステップＳ６０３で抽出された局所特徴点の各々について、画像の回転があっても不変となるように定義された特徴量（局所特徴量）を算出する。この局所特徴量の算出方法として、本実施形態ではＬｏｃａｌ  Ｊｅｔ及びそれらの導関数の組み合わせを用いる。
【００５３】
具体的には、以下の式（１）により局所特徴量Ｖを算出する。
【００５４】
【数１】
0006598480.tif 000002
【００５５】
ただし、式（１）の右辺で用いている記号は、以下に示す式（２）から式（７）で定義される。ここで、式（２）右辺のＧ（ｘ，ｙ）はガウス関数、Ｉ（ｘ，ｙ）は画像の座標（ｘ，ｙ）における画素値であり、“＊”は畳み込み演算を表す記号である。また、式（３）は式（２）で定義された変数Ｌのｘに関する偏導関数、式（４）は当該変数Ｌのｙに関する偏導関数である。式（５）は式（３）で定義された変数Ｌｘのｙに関する偏導関数、式（６）は式（３）で定義された変数Ｌｘのｘに関する偏導関数、式（７）は式（４）で定義されたＬｙのｙに関する偏導関数である。
【００５６】
【数２】
0006598480.tif 000003
【００５７】
なお、局所特徴量を算出可能な方法であれば、上述したような特徴量算出方法に限らず、どのような特徴量算出方法を用いてもよい。
【００５８】
以上によって、対象画像から局所特徴量を抽出することができる。
【００５９】
本実施形態の画像処理装置は、２画像間の類似度を求め、２画像間の類似判定の結果を出力する画像照合装置として構成される。本実施形態の構成により、比較先画像における撮像対象の奥行値に基づいて、撮像対象に対応した特徴量のクラスタを生成することができるので、距離範囲の異なる特徴量を区別して、照合精度を向上させることができる。なお、照合精度は比較元画像と比較先画像との２枚の画像が類似するか否かを判定した際の判定精度である。
【００６０】
［第２の実施形態］
本実施形態の画像処理装置を画像検索装置として用いた例を説明する。画像処理装置は、奥行情報をもつ画像を登録画像又は検索先画像として登録して、登録された複数枚の登録画像又は検索先画像から、クエリ画像又は検索元画像に類似する画像を検索する装置である。第１の実施形態の画像照合装置の比較先画像は一枚であるが、本実施形態の画像検索装置の登録画像又は検索先画像が複数ある。ここでは、本実施形態の画像検索装置と第１の実施形態の画像照合装置との共通部分について説明を省略するが、異なる部分について以下に説明する。
【００６１】
具体的には、登録画像又は検索先画像の登録の際に、奥行情報（奥行値）を用いて登録画像の特徴量をクラスタリングして、クラスタごとに特徴量を記憶する。検索の際には、クエリ画像の特徴量とペアをなす登録画像の特徴量の個数をクラスタごとに数え上げる。次に、所定のペア数を有するクラスタを求めて、求めたクラスタのペア数を用いて画像同士の類似度を生成する。画像同士の類似度の降順に登録画像の一覧を出力することで、クエリ画像に対する画像の検索を実現する。
【００６２】
本実施形態では、登録画像は奥行情報を有する画像を利用するが、クエリ画像は奥行情報を有していなくてもよい。
【００６３】
［画像検索装置の構成］
以下、本実施形態の画像検索装置の構成について図８を用いて説明する。
【００６４】
図８の画像検索装置の画像入力部８０１、特徴量抽出部８０２及びデータ保持部８０３の処理は、図３の画像照合装置の画像入力部３０１、特徴量抽出部３０２及びデータ保持部３０３の処理と同じである。また、図８の特徴量特定部８０５、特徴量比較部８０６、類似判定部８０７及び処理結果出力部８０８の処理は、図３の特徴量特定部３０５、特徴量比較部３０６、類似判定部３０７及び処理結果出力部３０８の処理と同じである。本実施形態では、これらの構成部分の説明を省略する。画像インデックス部８０４について説明する。
【００６５】
画像インデックス部８０４は、登録された画像の特徴量と画像ＩＤとクラスタＩＤを関連付けて管理する。
【００６６】
本実施形態の画像インデックス部８０４が管理するデータのデータ構造の一例を図９（ａ）に示す。量子化特徴量と対応づけて、画像ＩＤとクラスタＩＤを管理している。量子化特徴量は、後述する「局所特徴量量子化処理」によって生成される。この量子化値が同じとき、局所特徴量は所定以上の類似度があると判定することができる。なお、以降の説明において、図９（ａ）に示す１行をレコードと呼ぶことにする。
【００６７】
なお、本実施形態の画像インデックス部８０４が管理するデータのデータ構造では、同じ量子化値を持つレコードが複数作成されるが、これを避けるために、量子化値に対して「画像ＩＤとクラスタＩＤの組」のリストを対応づけてもよい。さらに、同じ量子化値を持つ特徴量が同じ画像の同じクラスタ内に複数あるとき、複数回同じ組が出現する。これを避けるために、「画像ＩＤとクラスタＩＤと個数の組」のリストを量子化値に対応づけるデータ構造にしてもよい。画像インデックス部８０４が管理するデータのデータ構造はこれらに限定されるのではない。例えば、量子化特徴量のクラスタＩＤは、さらに奥行値の属する複数の距離範囲のそれぞれに対応づけて管理することができる。
【００６８】
なお、画像インデックス部８０４が管理するデータは、データ保持部８０３に保持されるので、画像インデックス部８０４がデータ保持部８０３の一部として構成することができる。
【００６９】
特徴量比較部８０６は、クエリ画像の特徴量と類似する登録画像の特徴量をペアとして求める。具体的には、クエリ画像の特徴量を量子化して、画像インデックス部８０４から同じ量子化値を有するレコードを特定する。これによって、クエリ画像の特徴量に類似する特徴量を含む登録画像のクラスタが特定される。
【００７０】
類似判定部８０７は、画像ＩＤとクラスタＩＤの組ごとに、特徴量比較部８０６によって得たペアの数を数え上げる。具体的には、特徴量比較部８０６を用いて、クエリ画像から抽出された局所特徴量に類似する特徴量を画像インデックス部８０４から見つける。次に、見つけた特徴量に対応する「画像とクラスタの組」に対して１票を投票していく。これによって、画像ＩＤとクラスタＩＤの組ごとにペアの数を数え上げていく。
【００７１】
概念的には、図９（ｂ）に示すように、画像ＩＤとクラスタＩＤごとに投票値が生成されることになる。なお、ペア数９０１は画像ＩＤ：００１のクラスタＩＤ：００２の投票値を表している。ペア数９０２は画像ＩＤ：００１のクラスタＩＤ：００５の投票値を表している。この図では、クラスタＩＤが小さい方が、奥行値が小さい（撮像対象が手前にある）クラスタを表している。そのため、図９の例では、前景にあたるクラスタのペア数９０１と背景にあたるクラスタのペア数９０２が分かれて求まることが分かる。このように、所定の距離範囲ごとにペア数を数え上げることがなされる。
【００７２】
類似判定部８０７は、画像ＩＤごとに所定のペア数を有するクラスタを特定して、特定されたクラスタのペア数をクエリ画像と登録画像の類似度として生成する。具体的には、最大のペア数を有するクラスタを特定して、特定されたクラスタのペア数を類似度とする。例えば、類似判定部８０７によって図９（ｂ）に示すようにクラスタごとにペア数が得られたとき、図９（ｃ）に示すように画像ＩＤごとにペア数の最大値が類似度として生成される。
【００７３】
あるいは、ペア数の最大値の８０％に相当する値以上のペア数を有するクラスタを特定して、特定されたクラスタのペア数を和算したものを類似度としてもよい。あるいは、予め定めた閾値以上のペア数を有するクラスタを特定して、特定されたクラスタのペア数を和算したものを用いてもよい。
【００７４】
処理結果出力部８０８は、類似判定部８０７が画像ＩＤの全てに上記処理を適用することで、画像ＩＤごとに得られた類似度を出力することができる。あるいは、処理結果出力部８０８は、類似度の降順に画像又は画像ＩＤを出力してもよい。
【００７５】
［画像登録処理］
次に、画像登録処理についてフローチャート図１０を用いて説明する。本処理の実行時には登録画像および登録画像の画像ＩＤが与えられる。そして、登録画像から抽出した局所特徴量をクラスタに分けて画像インデックス部８０４に保存する。具体的な制御内容について図１０を用いて説明する。
【００７６】
ステップＳ１００１では、登録画像から局所特徴量を抽出する。画像から特徴的な点（局所特徴点）を抽出する。次に、当該局所特徴点とその周辺の画像情報とに基づいて、当該局所特徴点に対応する特徴量（局所特徴量）を計算する。局所特徴量抽出処理は、第１の実施形態と同じである。
【００７７】
ステップＳ１００２では、局所特徴量を量子化する。類似する特徴量は同じ量子化値を持つように量子化が行われる。具体的な処理内容については、局所特徴量量子化処理として後ほど図１２を用いて説明する。
【００７８】
ステップＳ１００３では、特徴量をクラスタリングする。具体的には、距離情報取得部７０２によって各特徴点の位置の奥行値を得る。そして、奥行値を用いて、特徴量特定部８０５によって特徴量はクラスタに分けられる。
【００７９】
ステップＳ１００４では、特徴量が画像インデックス部８０４に登録される。具体的には、ステップＳ１００３で得たクラスタに対してＩＤを割り当てる。例えば、奥行値が小さい（撮像対象が手前にある）距離範囲に対応する特徴量のクラスタから順に１から１ずつ加算して連続した整数をクラスタＩＤとして割り当てる。そして、各特徴量の量子化値と画像ＩＤとクラスタＩＤを対応付けた組にして画像インデックス部８０４に保存する。
【００８０】
［画像検索処理］
次に、画像検索処理についてフローチャート図１１を用いて説明する。本処理の実行時にはクエリ画像が与えられる。そして、クエリ画像から局所特徴量を抽出して、クエリ画像の特徴量とペアをなす登録画像の特徴量の個数をクラスタごとに数え上げる。次に、所定のペア数を有するクラスタを求めて、該クラスタのペア数を用いて画像同士の類似度を生成する。各画像の類似度と画像ＩＤの組の一覧を検索結果として生成する。具体的な制御内容については図１１を用いて説明する。
【００８１】
ステップＳ１１０１では、クエリ画像から局所特徴量を抽出する。局所特徴量抽出処理は、第１の実施形態と同じである。
【００８２】
ステップＳ１１０２では、局所特徴量を量子化する。具体的な処理内容については、局所特徴量量子化処理として後ほど図１２を用いて説明する。
【００８３】
ステップＳ１１０３〜ステップＳ１１０６では、クエリ画像から抽出された局所特徴量に類似する特徴量を画像インデックス部８０４から見つけ、見つけた特徴量に対応する「画像とクラスタの組」に対して１票を投票する処理を行う。概念的には、図９（ｂ）に示すように、画像ＩＤとクラスタＩＤごとに投票値を生成することを行う。以下ステップごとに説明する。
【００８４】
ステップＳ１１０３では、ステップＳ１１０２で得たクエリの量子化した局所特徴量を順に処理するためのループであり、特徴量には１から順に番号が割り当てられているものとする。これを変数ｉを用いて参照するため、はじめにｉを１に初期化する。さらに、ｉが局所特徴量の個数以下であるときステップＳ５０４へ移り、これを満たさないときループを抜けてステップＳ１１０７へ移る。
【００８５】
ステップＳ１１０４では、特徴量比較部８０６によって、クエリ画像の特徴量ｉと類似する登録画像の特徴量を見つける。具体的には、図９（ａ）に示す画像インデックス部８０４の量子化特徴量を走査して、クエリの量子化特徴量ｉに一致するレコードを特定する。同じ量子化値をもつレコードが複数あるとき、複数のレコードが得られることになる。
【００８６】
ステップＳ１１０５では、類似判定部８０７によって、「画像とクラスタの組」に対してペア数を加算することが行われる。具体的には、図９（ｂ）に示すような情報を保持するために、画像ＩＤとクラスタＩＤと投票値を保持するリストなどを予め用意しておく。そして、ステップＳ１１０４で得たレコードの画像ＩＤとクラスタＩＤの組の投票値に１加算する。これをステップＳ１１０４で見つけたレコード全てに対して行う。
【００８７】
ステップＳ１１０６は、ループの終端であり、ｉに１を加算してステップＳ５０３へ戻る。
【００８８】
ステップＳ１１０７〜ステップＳ１１０９の処理は、類似判定部７０６によって行われ、クエリ画像との類似度を生成する処理である。概念的には、図９（ｃ）に示すように、所定の投票値を有するクラスタを特定して、該クラスタの投票値を用いて類似度を生成する。以下ステップごとに説明する。
【００８９】
ステップＳ１１０７は、ステップＳ１１０３〜ステップＳ１１０６で得た画像ＩＤを順に処理するためのループである。ステップＳ１１０３〜ステップＳ１１０６で得た画像ＩＤは１から順番に番号が割り当てられているものとする。これを変数ｉを用いて参照するため、はじめにｉを１に初期化する。さらに、ｉがステップＳ１１０３〜ステップＳ１１０６で得た画像ＩＤの個数以下であるときステップＳ１１０８へ移り、これを満たさないときループを抜けてステップＳ１１１０へ移る。
【００９０】
ステップＳ１１０８では、類似判定部７０６によって、ｉ番目の画像ＩＤの類似度が生成される。具体的には、ｉ番目の画像ＩＤの中にあって、最大の投票値を持つクラスタを特定して、該クラスタの投票値を類似度とする。この類似度を画像ＩＤと対応づけて記憶する。
【００９１】
ステップＳ１１０９は、ループの終端であり、ｉに１を加算してステップＳ１１０７へ戻る。
【００９２】
ステップＳ１１１０では、ステップＳ１１０８で記憶していた画像ＩＤを類似度に基づいて降順にソートして、処理結果出力部８０８がソートされた画像又は画像を特定する情報（画像ＩＤ又はファイル名）の一覧を処理結果としてモニタ２１０などに出力する。これによって、クエリ画像に類似する登録画像の画像ＩＤを類似する順に得ることができる。なお、処理結果出力部８０８は、ステップＳ１１０８で記憶していた画像ＩＤで特定される全ての画像ではなく、類似度が所定値以上の登録画像だけを処理結果として出力してもよい。
【００９３】
なお、ステップＳ１１０８において、最大の投票値を持つクラスタを特定して、該クラスタの投票値を類似度としていた。しかし、クエリに映るオブジェクトが、登録画像側で撮像対象の奥行値が異なる距離範囲（例えば、前景と背景）にそれぞれ存在していることもある。このとき、最大の投票値をとるだけだと、前景又は背景の何れか一方のオブジェクトとの一致で類似度が決定してしまう。そこで、所定数以上の投票値を有するクラスタを特定して、該クラスタの投票値の和を類似度としてもよい。例えば、最大値の８０％に相当する値以上の投票値のクラスタを特定して、特定されたクラスタの投票値の和を類似度とすることができる。
【００９４】
これによって、類似する複数のオブジェクトが前景と背景のそれぞれに写る画像を検索したい場合にも適切な類似度が得られるようになる。
【００９５】
また、図９（ｂ）では投票値が０の画像ＩＤとクラスタＩＤの組も図示されている。しかし、ステップＳ１１０５で用いる画像ＩＤとクラスタＩＤと投票値を保持するリストでは、投票値が０のときはリスト上で保持しないようにしてもよい。このようにすることで、メモリの使用量を少なくすることができる。反対に、画像ＩＤとクラスタＩＤの全ての組み合わせに対して投票値を参照可能にする連想配列を予め構成しておいてもよい。このとき、高速に投票値を特定することができ、投票処理の高速化が期待できる。なお、この場合は画像ごとにクラスタ数が分かる必要があるため、画像インデックス部８０４にてクラスタ数を同時に管理するようにしてもよい。あるいは別の手段によってクラスタ数を管理するようにしてもよい。
【００９６】
以下では、本実施例で用いた「局所特徴量量子化処理」の一例について説明を行う。
【００９７】
［局所特徴量量子化処理］
局所特徴量同士のマッチングを行いやすくするために、上記の局所特徴量を量子化する。
【００９８】
例えば、局所特徴量をＮ次元ベクトルＶとし、各次元をＶｎと表記する。このとき、ｎ番目の次元の特徴量について、Ｋｎ階調の量子化は、以下の式（８）により行うことができる。なお、ＮおよびＫｎは予め決められた値である。
Ｑｎ＝（Ｖｎ＊Ｋｎ）／（Ｖｎ＿ｍａｘ−Ｖｎ＿ｍｉｎ＋１）      ・・・（８）
ここで、Ｑｎは、Ｎ次元のうちのｎ番目の次元の特徴量Ｖｎを量子化した値である。Ｖｎ＿ｍａｘとＶｎ＿ｍｉｎはそれぞれｎ番目の次元の特徴量の取りうる値の最大値、および、最小値である。
【００９９】
なお、上記の量子化では、次元ごとに量子化階調数を定めているが、全次元で共通の階調数を用いてもよい。この量子化方法は、図１２に示すように、特徴量空間を格子状に分割する方法である。この図で、格子１２０１は特徴量空間における量子化領域、点１２０２は各特徴を表している。図１２は二次元の特徴量空間を量子化分割している例であるが、これを局所特徴量の次元数分の多次元に拡張した分割を行う。
【０１００】
また、特徴量空間を分割可能な方法であれば、上述したような規則に基づいて量子化する方法に限らずに、どのような分割方法でも適用可能である。例えば、複数の画像を機械学習させることによりクラスタリングのルールを作成し、そのルールに則って特徴量空間を分割し、量子化するようにしてもよい。
【０１０１】
また、各次元についての量子化を行った後、以下の式（９）により、量子化値群のラベル化を行うことで、実質的に一次元の特徴量と同等に扱うことも可能である。
ＩＤＸ＝Ｑ１＋Ｑ２＊Ｋ１＋Ｑ３＊Ｋ１＊Ｋ２＋・・・＋Ｑｎ＊Ｋ１＊Ｋ２＊・・・＊Ｋｎ−１    ・・・（９）
また、全次元の階調数が共通の場合は、以下の式（１０）により、量子化値群のラベル化が可能である。ここで、Ｋは階調数である。
【０１０２】
【数３】
0006598480.tif 000004
【０１０３】
なお、ラベル化可能な算出方法であれば、上述したような算出方法に限らずに、どのようなラベル化方法を用いてもよい。
【０１０４】
量子化値をキーとして画像ＩＤなどを検索可能とするデータベースなどを構成することで、局所特徴量同士のマッチングを高速に行うことが可能になる。これを画像インデックスと呼ぶ。
【０１０５】
本実施形態の画像検索装置によって、図９（ｃ）に示すようにペア数の投票値を奥行方向の複数の距離範囲に対応する複数のクラスタごとに分けて得る。そのため、登録画像の前景にあるオブジェクトを写した画像がクエリ画像であるとき、「前景の特徴量との一致数（ペア数）」と「背景の特徴量との偶然の一致数」が分けて得られる。そして、偶然の一致は正しい一致に比べて少ないため、最大値を有するクラスタを特定することで、正しい一致により得られた投票値を得ることを可能としている。従って、登録画像又は検索先画像から、クエリ画像又は検索元画像に類似する画像を検索する検索精度を高めることができる。
【０１０６】
例えば、図９（ｃ）に示す例では、従来は画像ＩＤ００１と画像ＩＤ００２の類似度はともに２６０で同じであった。しかし、本実施形態の画像検索装置では、画像ＩＤ００１と画像ＩＤ００２の類似度は２００と１８０と異なり、画像ＩＤ００１の方がより類似していることが分かるようになる。
【０１０７】
［第３の実施形態］
第１の実施形態又は第２の実施形態において、奥行値を階調化して特徴量をクラスタリングすると、一つのクラスタにオブジェクトの特徴量がおさまらないことがありえる。例えば、クエリ画像に車のような奥行のあるオブジェクトが写っている場合は、車の特徴量は二つ以上の距離範囲に対応する複数のクラスタに割り当てられてしまう可能性がある。そこで、近傍のクラスタの投票値を加算して得られた投票値が所定値以上のクラスタを特定して、該クラスタからクエリ画像と登録画像の類似度を生成する画像検索装置について述べる。なお、第１の実施形態又は第２の実施形態と同様に、特徴量の複数のクラスタはそれぞれ距離範囲と対応する。
【０１０８】
本実施形態の画像検索装置の構成は、第２の実施形態で示した図８の構成と同じである。ただし、類似判定部８０７の動作が異なる。本実施形態の類似判定部８０７は、画像ＩＤごとに近傍のクラスタの投票値を加算する。次に、所定値以上の投票値を有するクラスタを特定して、該クラスタからクエリ画像と登録画像の類似度を生成する。
【０１０９】
例えば、類似判定部８０７によって図１４の上側に記載の画像とクラスタの組に対しての投票値が求まったとき、図１４の下側に示すように近傍のクラスタの投票値を加算する。この例では、左右あわせて３つのクラスタの投票値を足し合わせている。ただし、クラスタＩＤ：００１のように左にクラスタがないときは、その方向の投票値は無視して存在するクラスタの投票値のみを足し合わせている。このようにして、近傍のクラスタの投票値を足し合わせる。その後、第１の実施形態と同様に、所定以上の投票値を有するクラスタを特定して、該クラスタからクエリ画像と登録画像の類似度を生成する。具体的には、第１の実施形態と同様に、特定したクラスタの最大値を類似度として用いる。あるいは、最大値の８０％に相当する値以上のペア数を有するクラスタを特定して、該クラスタのペア数を和算したものを類似度としてもよい。あるいは、所定の閾値以上のペア数を有するクラスタを特定して、該クラスタのペア数を和算したものを用いてもよい。
【０１１０】
次に、本実施形態の画像検索処理についてフローチャート図１３を用いて説明する。フローチャート図１３は、第１の実施形態のフローチャート図１１のステップＳ１１０６とステップＳ１１０７の間に処理が追加されたところが異なる点である。そのため、ステップＳ１３０１〜ステップＳ１３０６はステップＳ１１０１〜ステップＳ１１０６と同じである。同様にステップＳ１３１２〜ステップＳ１３１５も、ステップＳ１１０７〜ステップＳ１１１０と同じである。以下、新たに追加された処理ステップＳ１３０７〜ステップＳ１３１１について、ステップごとに説明する。
【０１１１】
ステップＳ１３０７〜ステップＳ１３１１は、画像ＩＤごとに近傍のクラスタの投票値を加算することを行う。なお、近傍の数は予め与えられているものとする。この例では前後含めて３つのクラスタを近傍とする。以下ステップごとに説明する。
【０１１２】
ステップＳ１３０７は、ステップＳ１３０３〜ステップＳ１３０６で得た画像ＩＤを順に処理するためのループである。ステップＳ１３０３〜ステップＳ１３０６で得た画像ＩＤは１から順番に番号が割り当てられているものとする。これを変数ｉを用いて参照するため、はじめにｉを１に初期化する。さらに、ｉがステップＳ１３０３〜ステップＳ１３０６で得た画像ＩＤの個数以下であるときステップＳ１３０８へ移り、これを満たさないときループを抜けてステップＳ１３１２へ移る。
【０１１３】
ステップＳ１３０８では、画像ｉのクラスタを順に処理するためのループである。クラスタＩＤは１から順番に番号が割り当てられているものとする。これを変数ｊを用いて参照するため、はじめにｊを１に初期化する。さらに、ｊがクラスタの個数以下であるときステップＳ１３０９へ移り、これを満たさないときループを抜けてステップＳ１３１１へ移る。
【０１１４】
ステップＳ１３０９では、画像ｉのクラスタｊの近傍のペア数を足し合わせる。例えば、前述した図１４の例の通り、クラスタｊがクラスタＩＤ：００２であるとき、前後あわせた近傍３つのクラスタのペア数を足し合わせるため、クラスタＩＤ：００１〜００３のペア数を足し合わせる。これを別途用意した画像ＩＤとクラスタＩＤとペア数を記憶するリストに保存する。このリストは後段のステップＳ１３１２以降で使用される。
【０１１５】
ステップＳ１３１０は、クラスタのループの終端であり、ｊに１を加算してステップＳ１３０８へ戻る。
【０１１６】
ステップＳ１３１１は、画像のループの終端であり、ｉに１を加算してステップＳ１３０７へ戻る。
【０１１７】
なお、本実施形態では、近傍数は予め与えられることを想定していた。しかしながら、これをクエリ画像から求めてもよい。例えば、クエリ画像も奥行値を有するとき、奥行値をクラスタリングするなどして、クエリ画像に写っているオブジェクトの特徴量群のクラスタに対応する距離範囲からオブジェクトの厚みを得る。あるいは、最大の特徴量数を有するクラスタの厚みを得る。これによって得たクエリ画像にあるオブジェクトの厚みを、階調幅で割ることで、近傍数を求めることができる。例えば、クエリ画像に車が写っており、クラスタリングで得たオブジェクトの厚みが３ｍであったとき、さらに階調幅が１ｍであったとき、近傍数は３と求めることができる。
【０１１８】
あるいは、画像認識などの技術によって、クエリ画像のオブジェクト種別を得て、そのオブジェクト種別にあった厚みを用いて近傍数を得てもよい。例えば、人体検出等を適用した結果、クエリ画像から人物が検出されたとき、予め用意した一般的な人物の厚みを用いることが考えられる。あるいは単純に、クエリ画像とともにユーザ入力で得るようにしてもよい。本実施形態におけるオブジェクトの厚みの特定方法はこれらに限定されない。
【０１１９】
本実施形態の画像検索装置によって、奥行値を階調化する際の階調幅がオブジェクトの厚みより小さく、同じオブジェクトの特徴量を分断して異なるクラスタに登録してしまう場合に対応する。このときは、近傍のクラスタのペア数を足し合わせることで、適切に求めたペア数をもとに類似度を生成できる。例えば、画像インデックス部８０４に登録されるクラスタに対応する距離範囲の間隔（階調幅）が１ｍであるとする。このとき、車などのオブジェクトは奥行き方向に３ｍ程度の幅がある。そのため、いくつかのクラスタに車の特徴量が分けて登録されてしまう。第１の実施形態又は第２の実施形態では、この分かれたクラスタの１つから類似度が決定されてしまう。しかしながら、本実施形態では、近傍のクラスタのペア数を足し合わせる。そのため、近傍数を３つとすれば、およそ３ｍ程度の奥行き幅でペア数を求めることができるようになる。そのため、正しく車全体の特徴量と一致したペア数が求められることになる。
【０１２０】
［その他の実施形態］
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【符号の説明】
【０１２１】
３０１  画像入力部
３０２  特徴量抽出部
３０３  データ保持部
３０５  特徴量特定部
３０６  特徴量比較部
３０７  類似判定部
３０８  処理結果出力部
【図１】
0006598480.tif 000005
【図２】
0006598480.tif 000006
【図３】
0006598480.tif 000007
【図４】
0006598480.tif 000008
【図５】
0006598480.tif 000009
【図６】
0006598480.tif 000010
【図７】
0006598480.tif 000011
【図８】
0006598480.tif 000012
【図９】
0006598480.tif 000013
【図１０】
0006598480.tif 000014
【図１１】
0006598480.tif 000015
【図１２】
0006598480.tif 000016
【図１３】
0006598480.tif 000017
【図１４】
0006598480.tif 000018