画像検索装置、画像検索方法及びプログラム
【課題】利用価値の高い順序で検索結果を得ることができるようにする。
【解決手段】特徴量間の距離が最小となる局所特徴量の組合せにおいて、縮小画像の生成処理において縮小画像のサイズが大きい方から順に解像度に応じて付与されるスケール番号の差を解像度の差と定義し、最も頻度の高い解像度の差を類似度の重み付け係数に反映させ、得られた最終投票数ＶｏｔｅＭａｘに掛け合わせて最終的な類似度として出力するようにして、画像の解像度が反映された検索結果を出力できるようにする。
【解決手段】特徴量間の距離が最小となる局所特徴量の組合せにおいて、縮小画像の生成処理において縮小画像のサイズが大きい方から順に解像度に応じて付与されるスケール番号の差を解像度の差と定義し、最も頻度の高い解像度の差を類似度の重み付け係数に反映させ、得られた最終投票数ＶｏｔｅＭａｘに掛け合わせて最終的な類似度として出力するようにして、画像の解像度が反映された検索結果を出力できるようにする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、局所特徴点及び局所特徴量に基づく検索を行うために用いて好適な画像検索装置、画像検索方法及びプログラムに関する。
【背景技術】
【０００２】
従来、画像の局所的な特徴量（局所特徴量）を用いて類似画像を検索する方法が提案されている。この方法では、まず、画像から特徴的な点（局所特徴点）を抽出する。抽出方法については例えば非特許文献１に開示されている方法が挙げられる。そして、当該特徴点とその周辺の画像情報とに基づいて、当該特徴点に対応する特徴量（局所特徴量）を計算する。局所特徴量については例えば非特許文献２に開示されている方法によって計算することができる。このように画像の検索は、局所特徴量同士のマッチングによって行われる。
【０００３】
局所特徴量を利用する手法においては、局所特徴量を回転不変、拡大・縮小不変となる複数の要素で構成される情報として定義する。これにより、画像を回転させたり、拡大又は縮小させたりした場合であっても、画像を検索することができる。また、局所特徴量は一般的にベクトルとして表現される。ただし、局所特徴量が回転不変、拡大・縮小不変であることは理論上の話であり、実際のデジタル画像においては、画像の回転や拡大・縮小処理前の局所特徴量と処理後の対応する局所特徴量との間に若干の変動が生じる。
【０００４】
例えば非特許文献２に記載の方法では、回転不変の局所特徴量を算出するために、局所特徴点周辺の局所領域の画素パターンから主方向を算出し、局所特徴量の算出時に主方向を基準に局所領域を回転させて方向を正規化する。また、拡大・縮小不変の局所特徴量を算出するために、異なる解像度の画像を内部で生成し、各解像度の画像からそれぞれ局所特徴点を抽出し、局所特徴量を算出する。ここで、内部で生成した一連の異なる解像度の画像集合は一般的にスケールスペースと呼ばれる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】C.Harris and M.J. Stephens,"A combined corner and edge detector," In Alvey Vision Conference,pages 147-152, 1988.
【非特許文献２】David G. Lowe, "Distinctive Image Features from Scale-Invariant Keypoints," International Journal of Computer Vision, 60, 2 (2004), pp.91-110.
【非特許文献３】J. J. Koenderink and A. J. van Doorn, "Representation of local geometry in the visual system," Riological cybernetics, vol.55, pp.367-375, 1987.
【非特許文献４】M. A. Fischler and R. C. Bollers, "Random sample consensus: A paradigm formodel fitting with applications to image analysis and automated cartography," Commum. ACM, no.24, vol.6, pp.381-395, June 1981.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
検索結果により画像が表示される順位は、多くの場合、クエリ画像と登録画像との間の類似度が局所特徴量のマッチングにより算出され、その類似度を用いて決定される。局所特徴量のマッチング方法としては、局所特徴量をベクトルに表現してベクトル間の距離を測るものや、ハッシュ表を用いる方法などがある。ところが、このような従来の方法では、検索結果の画像の利用価値の順序と結果の表示順序とが合致しないことがある。このような現象が生じる場合の例とその原因について以下に説明する。
【０００７】
例えば、クエリ画像と同じ解像度で回転のない第１の登録画像と、クエリ画像よりはるかに解像度が高いが若干回転している第２の登録画像とが検索される場合を考える。まず、局所特徴量をマッチングするために、前述のように、それぞれの画像に対してスケールスペースを生成し、各解像度の画像から回転不変の局所特徴量を算出する。
【０００８】
このとき、第２の登録画像からは、クエリ画像には存在しない高解像度の画像がスケールスペースに含まれ、その画像からも局所特徴量が算出される。ところが、これらの局所特徴量は検索時のクエリ画像との局所特徴量のマッチングには寄与しない。クエリ画像と重なる解像度のスケールスペースから算出された第２の登録画像の局所特徴量だけが、クエリ画像との局所特徴量同士のマッチングに寄与することになる。
【０００９】
ここで、第２の登録画像とクエリ画像との間でマッチした局所特徴量ペアのベクトル間距離は、第１の登録画像とクエリ画像との間でマッチした局所特徴量ペア間のベクトル間距離よりも大きくなる可能性が高い。これは、クエリ画像に対して第１の登録画像が回転していない一方で第２の登録画像は若干回転していることに起因する。すなわち、第２の登録画像は回転によって画像にノイズが付与され、そのノイズが局所特徴量を変動させるからである。
【００１０】
この結果、クエリ画像と第１の登録画像との類似度は、解像度の高い第２の登録画像との類似度よりも大きくなる。ところが、第２の登録画像の回転量がユーザの気にならない程度の回転量であった場合には、解像度の高い第２の登録画像の方が第１の登録画像よりも利用価値が高いことがある。例えば、解像度の高い画像の方が、画像の回転や拡大など画像加工時の画質劣化問題を回避しやすいため、再利用性に優れている。
【００１１】
このように、従来の方法では検索結果の画像の利用価値の順序と結果の表示順序とが合致しないという現象が容易に生じ得るという問題がある。
【００１２】
本発明は前述の問題点に鑑み、利用価値の高い順序で検索結果を得ることができるようにすることを目的としている。
【課題を解決するための手段】
【００１３】
本発明の画像検索装置は、入力画像を用いて予め登録されている登録画像を検索する画像検索装置であって、前記入力画像及び登録画像から局所的な局所特徴を抽出する局所特徴抽出手段と、前記局所特徴抽出手段によって抽出された局所特徴に基づいて前記入力画像と前記登録画像との間の第１の類似度を算出する第１の類似度算出手段と、前記第１の類似度算出手段によって算出された第１の類似度と、前記入力画像及び登録画像の解像度情報とに基づいて前記入力画像と前記登録画像との間の第２の類似度を算出する第２の類似度算出手段と、前記第２の類似度算出手段によって算出された第２の類似度に応じて検索結果を出力する出力手段とを備えることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、画像の解像度が反映された利用価値の高い順序で検索結果を出力することができる。
【図面の簡単な説明】
【００１５】
【図１】実施形態における画像検索装置の構成例を示すブロック図である。
【図２】実施形態において、画像の局所特徴点及び局所特徴量を抽出する処理手順の一例を示すフローチャートである。
【図３】図２のステップＳ２０４における縮小画像の生成処理の概要を説明する図である。
【図４】局所特徴点の抽出する概要を説明する図である。
【図５】解像度を考慮しないで類似度を算出する処理手順の一例を示すフローチャートである。
【図６】実施形態における類似度を算出する処理手順の一例を示すフローチャートである。
【図７】実施形態における画像検索装置のハードウェア構成例を示すブロック図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について、図面を参照しながら説明する。
図１は、本実施形態における画像検索装置１００の構成例を示すブロック図である。
図１において、画像検索装置１００は、第１の画像入力部１０２、第２の画像入力部１０５、第１の局所特徴点／局所特徴量抽出部１０３、第２の局所特徴点／局所特徴量抽出部１０６及び局所特徴量比較部１０７から構成されている。
【００１７】
画像検索装置１００では、入力画像１０１が第１の画像入力部１０２に入力されると、第１の局所特徴点／局所特徴量抽出部１０３は、局所特徴として局所特徴点とその局所特徴量とを抽出する。同様に、比較対象となる入力画像１０４が第２の画像入力部１０５に入力されると、第２の局所特徴点／局所特徴量抽出部１０６は、局所特徴として局所特徴点とその局所特徴量とを抽出する。本実施形態では、入力画像１０１をクエリ画像とし、比較対象となる入力画像１０４をデータベースに登録されている登録画像として説明する。また、局所特徴点とその局所特徴量とを抽出する処理の詳細については後述する。
【００１８】
局所特徴点／局所特徴量比較部１０７は、第１の局所特徴点／局所特徴量抽出部１０３及び第２の局所特徴点／局所特徴量抽出部１０６で抽出されたそれぞれの局所特徴点及び局所特徴量同士を比較し、画像表示順序として比較結果１０８を出力する。この局所特徴点及び局所特徴量の比較処理の詳細についても後述する。
【００１９】
図７は、本実施形態に係る画像検索装置１４００のハードウェア構成例を示すブロック図である。
図７において、画像検索装置１４００は例えばパーソナルコンピュータであり、ＲＯＭ１４３０には、後述するフローチャートの処理をＣＰＵ１４１０の制御により実現させるプログラムが格納されている。そして、プログラムを実行させる際には、ＲＯＭ１４３０に格納されたプログラムをＲＡＭ１４２０に読み出してＣＰＵ１４１０が処理できるようにしている。
【００２０】
バス１４５０は、ＲＯＭ１４３０、ＲＡＭ１４２０、ＣＰＵ１４１０及びＨＤＤ１４４０とデータのやりとりを行う。また、画像検索装置１４００は、ユーザインターフェース１４６０に接続されるキーボードやマウスなどの入出力機器からの入力を受ける。さらに、画像検索装置１４００は、ネットワークインターフェース１４７０を介してネットワーク１５００を経由し、データベース（ＤＢ）１５１０、クライアント端末（ＣＬＩＥＮＴ）１５２０、及びプリンタ（ＰＲＩＮＴＥＲ）１５３０とデータの入出力を行う。
【００２１】
また、複数のハードウェアとソフトウェアとの協働によって後述する実施形態の処理を実現してもよい。例えば、画像検索装置１４００がクライアント端末１５２０やプリンタ１５３０から検索依頼とクエリ画像とを受け付け、後述するフローチャートの処理を行い、データベース１５１０からクエリ画像に類似する画像を検索する形態が挙げられる。
【００２２】
［局所特徴抽出処理］
次に、画像の局所特徴（局所特徴点及び局所特徴量）抽出処理を説明する。画像の局所特徴抽出処理は、画像データを読み出すステップ、輝度成分の抽出ステップ、縮小画像の作成ステップ、局所特徴点の抽出ステップ、及び局所特徴量の算出ステップからなる。
【００２３】
図２は、本実施形態において、画像の局所特徴点及び局所特徴量を抽出する処理手順の一例を示すフローチャートである。
まず、ステップＳ２０１により処理を開始し、ステップＳ２０２において、第１の画像入力部１０２及び第２の画像入力部１０５は、それぞれの画像データを読み出す。そして、ステップＳ２０３において、第１の局所特徴点／局所特徴量抽出部１０３及び第２の局所特徴点／局所特徴量抽出部１０６はそれぞれ、画像データから輝度成分を抽出し、輝度成分画像を生成する。
【００２４】
次に、ステップＳ２０４において、第１の局所特徴点／局所特徴量抽出部１０３及び第２の局所特徴点／局所特徴量抽出部１０６はそれぞれ、ステップＳ２０３で作成した当該輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成する。ただし、倍率ｐ及び縮小画像の枚数ｎは予め決められているものとする。
【００２５】
図３は、図２のステップＳ２０４における縮小画像の生成処理の概要を説明する図である。なお、図３では、倍率ｐを２の−（１／４）乗とし、縮小画像の枚数ｎを９とした場合の例を示している。また、図３に示す例では、倍率ｐを面積比ではなく辺の長さの比としている。
【００２６】
図３において、３０１はステップＳ２０３で作成した輝度成分画像である。３０２は輝度成分画像３０１から倍率ｐに従って４回縮小された縮小画像であり、輝度成分画像３０１を１／２に縮小した画像に相当する。また、３０３は輝度成分画像３０１から倍率ｐに従って８回縮小された縮小画像であり、輝度成分画像３０１を１／４に縮小した画像に相当する。なお、画像を縮小する方法は単純に画素を間引く方法、線形補間を用いる方法、低域フィルタ適用後にサンプリングする方法などを用いることができるが、何れの方法でもよい。本実施形態では、線形補間による縮小方法を用いて画像を縮小するものとする。
【００２７】
３０４はスケール番号であり、縮小画像のサイズが大きい方から順に解像度に応じて付与される番号である。本実施形態では、スケール番号は１から始まるようにしているが、０から始まるようにしてもよい。
【００２８】
図２の説明に戻り、次に、ステップＳ２０５において、第１の局所特徴点／局所特徴量抽出部１０３及び第２の局所特徴点／局所特徴量抽出部１０６は、ステップＳ２０４で得られたｎ枚の縮小画像のそれぞれから局所的な特徴点（局所特徴点）を抽出する。ここで抽出する局所特徴点は、画像に回転や縮小などの画像処理を施しても同じ場所から安定的に抽出されるようなロバストな局所特徴点である。このような局所特徴点を抽出する方法として、本実施形態では、非特許文献１に記載されているＨａｒｒｉｓ作用素を用いる。
【００２９】
具体的には、Ｈａｒｒｉｓ作用素を作用させて得られた画像の画素それぞれについて、着目画素とその周辺にある８つの画素との合計９画素の画素値を調べる。そして、着目画素の画素値が予め定めた値以上であり、かつ局所極大になる（当該９画素の中で当該画素の画素値が最大になる）場合に、その着目画素が位置する点を局所特徴点として抽出する。なお、ロバストな局所特徴点を抽出可能な方法であれば、上述のＨａｒｒｉｓ作用素による特徴点抽出方法に限らず、どのような特徴点抽出方法でも適用可能である。
【００３０】
次に、ステップＳ２０６において、ステップＳ２０５で得られた局所特徴点それぞれについて、画像の回転があっても不変となるように定義された特徴量（局所特徴量）を算出する。この局所特徴量の算出方法として、本実施形態では非特許文献３に記載されているLocal Jet及びそれらの導関数の組み合わせを用いる。この方法により算出される局所特徴量は、拡大縮小、回転に対して、比較的高い耐性を持つような特性を持たせることができる。具体的には、以下の式（１）により局所特徴量を算出する。
【００３１】
【数１】
【００３２】
ただし、式（１）の右辺で用いている記号は、以下の式（２）から式（７）に示すように定義される。
【００３３】
【数２】
【００３４】
ここで、式（２）右辺のＧ（ｘ，ｙ）はガウス関数であり、Ｉ（ｘ，ｙ）は画像の座標（ｘ，ｙ）における画素値であり、"＊"は畳み込み演算を表す記号である。また、式（３）は式（２）で定義された変数Ｌのｘに関する偏導関数であり、式（４）は当該変数Ｌのｙに関する偏導関数である。式（５）は式（３）で定義された変数Ｌxのｙに関する偏導関数である。式（６）は式（３）で定義された変数Ｌxのｘに関する偏導関数であり、式（７）は式（４）で定義されたＬyのｙに関する偏導関数である。
【００３５】
なお、局所特徴量の算出方法は、上述の方法に限らず他の局所特徴量の算出方法も適用可能である。他の局所特徴量の算出方法として、例えば非特許文献２に記載されている方法がある。この方法では、局所特徴点周辺の局所領域内の各画素に対して画素値の勾配方向を算出し、そのヒストグラムを局所特徴量としている。
【００３６】
図４は、局所特徴点の抽出する概要を説明する図である。図４（ａ）は入力画像４１０を示しており、図４（ｂ）は、入力画像４１０から抽出した局所特徴点４２１、４２２を重畳した入力画像４２０を示している。図４に示す例では、局所特徴点４２１、４２２に対してそれぞれ局所特徴量が計算される。
【００３７】
［類似度算出方法］
まず、一般的な方法を用いて類似度を算出する方法について説明する。類似度の算出方法では様々な方法を用いることができるが、以下の説明では、例えば非特許文献４に記載されているＲＡＮＳＡＣを利用した類似度算出方法について説明する。
【００３８】
ここで、入力画像の局所特徴点をＱとし、その座標をＱ（ｘ'，ｙ'）とし、その局所特徴点Ｑの局所特徴量をＶqとする。また、比較対象となる入力画像の画像上の局所特徴点をＳとして、その座標をＳ（ｘ，ｙ）とし、その局所特徴点Ｓの局所特徴量をＶsとする。
【００３９】
図５は、解像度を考慮しないで類似度を算出する処理手順の一例を示すフローチャートである。
ステップＳ５０１で処理を開始すると、ステップＳ５０２において、局所特徴量Ｖqと局所特徴量Ｖsとを照合して最小距離対応点リストを作成する。具体的には、まず、局所特徴量Ｖqと局所特徴量Ｖsとの全ての組み合わせについて局所特徴量間の距離を計算する。次に、計算した局所特徴量間の距離が閾値Ｔｖ以下となり、かつ、最小距離となるような局所特徴量Ｖqと局所特徴量Ｖsとの組み合わせ（対応点）を抽出する。これらの対応点を最小距離対応点リストに登録することにより、最小距離対応点リストを作成する。
【００４０】
ここで、最小距離対応点リストには、例えばｋ番目の最小距離対応点をそれぞれＱk、Ｓkと表わし、これらの座標をＱk（ｘk'，ｙk'）、Ｓk（ｘk，ｙk）とし、添え字を合わせて記載する。なお、１つの局所特徴点に対応付けられる局所特徴量は２つ以上あってもよいが、以下の説明では説明を簡略化するため、１つの局所特徴点に対応付けられる局所特徴量は１つだけとする。そして、前記Ｑk、Ｓkの局所特徴量をそれぞれＶq（ｋ）、Ｖs（ｋ）とする。また、ステップＳ５０２では、ｍ組の対応点が最小距離対応点リストに登録されるものとする。
【００４１】
次に、ステップＳ５２１において、ｍが３以上であるか否かを判定する。この判定の結果、ｍが３未満である場合は、類似度を算出できないため、ステップＳ５２２に進み、処理を終了する。
【００４２】
一方、ステップＳ５２１の判定の結果、ｍが３以上である場合は、ステップＳ５０３において、最終投票数を表す変数ＶｏｔｅＭａｘを０に初期化する。そして、ステップＳ５０４において、類似度算出処理の反復カウント数を表す変数Ｃｏｕｎｔを０に初期化する。
【００４３】
次に、ステップＳ５０５において、反復カウント数Ｃｏｕｎｔが予め定められた最大反復処理回数Ｒｎを超えていないか否かを判定する。この判定の結果、反復カウント数Ｃｏｕｎｔが最大反復処理回数Ｒｎを超えていない場合はステップＳ５０６へ進み、投票数を表す変数Ｖｏｔｅを０に初期化する。一方、ステップＳ５０５の判定の結果、反復カウント数Ｃｏｕｎｔが最大反復処理回数Ｒｎを超えている場合には、ステップＳ５１９へ進み、最終投票数ＶｏｔｅＭａｘを類似度として出力し、ステップＳ５２０において処理を終了する。
【００４４】
次に、ステップＳ５０７において、最小距離対応点リストから対応点の組の座標をランダムに２組抽出する。ここで、抽出した２組の座標をＱ1（ｘ1'，ｙ1'）、Ｓ1（ｘ1，ｙ1）、及びＱ2（ｘ2'，ｙ2'）、Ｓ2（ｘ2，ｙ2）と定義する。そして、ステップＳ５０８において、変換行列Ｍ、Ｔを計算する。ここで、行列Ｍは、以下の式（８）において変数ａ〜ｄで構成される行列であり、行列Ｔは変数ｅ〜ｆで構成される行列である。
【００４５】
【数３】
【００４６】
ここで、以下の説明では説明を簡略化するため、相似変換だけを考える。この場合には、上記式（８）は以下の式（９）のように書き換えられる。
【００４７】
【数４】
【００４８】
また、式（９）における変数ａ、ｂ、ｅ、ｆは、座標Ｑ1（ｘ1'，ｙ1'）、Ｓ1（ｘ1，ｙ1）及びＱ2（ｘ2'，ｙ2'）、Ｓ2（ｘ2，ｙ2）の座標値を用いて以下の式（１０）〜式（１３）で表すことができる。
【００４９】
【数５】
【００５０】
次に、ステップＳ５０９において、ステップＳ５０７で最短距離対応点リストからランダムに抽出された２組の点以外の点を選択するために、対応点選択変数ｋを３に初期化する。そして、ステップＳ５１０において、対応点選択変数ｋが最短距離対応点リストに登録されている対応点の組数ｍを超えていないか否かを判定する。この判定の結果、組数ｍを超えている場合はステップＳ５１６へ進む。ステップＳ５１６の処理については後述する。
【００５１】
一方、ステップＳ５１０の判定の結果、組数ｍを超えていない場合は、ステップＳ５１１において、最小距離対応点リストから新たな対応点の組を１組抽出する。ここでは、抽出した座標をＳk（ｘk，ｙk）、Ｑk（ｘk'，ｙk'）と定義する。なお、抽出する際には、ステップＳ５０７と同様に付加情報を利用する。
【００５２】
次に、ステップＳ５１２において、式（９）によりＳk（ｘk，ｙk）を変換した座標Ｓk'（ｘk"，ｙk"）を求める。その後、ステップＳ５１３において、座標Ｓk'（ｘk"，ｙk"）と座標Ｑk（ｘk'，ｙk'）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離が閾値Ｔｄ以下であるか否かを判定する。この判定の結果、当該ユークリッド距離が閾値Ｔｄ以下の場合はステップＳ５１４へ進み、投票数Ｖｏｔｅをインクリメントした後、ステップＳ５１５へ進む。一方、ステップＳ５１３の判定の結果、当該ユークリッド距離が閾値Ｔｄより大きい場合は、何もせずにステップＳ５１５へ進む。
【００５３】
次に、ステップＳ５１５において、対応点選択変数ｋをインクリメントし、ステップＳ５１０に戻り、対応点選択変数ｋが最短距離対応点リストに登録されている対応点の組数ｍを超えるまで、上述の処理を繰り返す。
【００５４】
次に、ステップＳ５１０で、対応点選択変数ｋが当該対応点リストに登録されている対応点の組数ｍを超えた場合について説明する。ステップＳ５１６においては、投票数Ｖｏｔｅの値と最終投票数ＶｏｔｅＭａｘの値とを比較し、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値よりも大きいか否かを判定する。この判定の結果、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値よりも大きい場合にはステップＳ５１７へ進む。
【００５５】
ステップＳ５１７においては、最終投票数ＶｏｔｅＭａｘの値を投票数Ｖｏｔｅの値で置き換える。そして、ステップＳ５１８において反復カウント数Ｃｏｕｎｔをインクリメントし、ステップＳ５０５に戻る。一方、ステップＳ５１６の判定の結果、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値以下の場合にはステップＳ５１８へ処理を移し、反復カウント数ＣｏｕｎｔをインクリメントしてステップＳ５０５に処理を戻す。
【００５６】
なお、図５の説明では、相似変換だけを考慮して説明したが、アフィン変換などその他の幾何学変換についても、ステップＳ５０８でそれぞれに応じた変換行列を求めることにより、対応可能である。例えば、アフィン変換の場合には、まずステップＳ５０７で、ランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ５０８で、式（９）ではなく式（８）を用い、ステップＳ５０７で選択した３組の対応点（合計６点）を用いて変数ａ〜ｆを求めればよい。
【００５７】
また、図５の説明では、ステップＳ５１９で類似度として最終投票数ＶｏｔｅＭａｘを出力する例について説明したが、他の類似度を計算するようにしてもよい。例えば、ステップＳ５０３以降の処理を行わずに、ステップＳ５０２で作成された最小距離対応点リストに登録された対応点の組数ｍを類似度として出力する方法がある。
【００５８】
次に、本実施形態における類似度算出方法について、図６を参照しながら説明する。
図６は、本実施形態において、局所特徴点／局所特徴量比較部１０７により類似度を算出する処理手順の一例を示すフローチャートである。図６に示すフローチャートでは、図５の処理手順にステップＳ６０１の処理が追加され、さらに図５のステップＳ５１９の処理がステップＳ６０２の処理に入れ替わっている。なお、図５の同じ符号を付しているステップＳ５０１〜Ｓ５１８、Ｓ５２０〜Ｓ５２２については図５と同様であるため、説明は省略する。
【００５９】
まず、ステップＳ６０１の処理について説明する。
【００６０】
図５に示した手順では、まず、ステップＳ５０２で、局所特徴量Ｖqと局所特徴量Ｖsとの全ての組み合わせについて局所特徴量間の距離を計算する。次に、計算した局所特徴量間の距離が閾値Ｔｖ以下となり、かつ、最小距離となるような局所特徴量Ｖqと局所特徴量Ｖsとの組み合わせ（対応点）を抽出し、これらの対応点を登録することにより最小距離対応点リストを作成する。
【００６１】
このとき、図３に示したスケール番号３０４に着目することにより比較対象画像との間の解像度の差を推定することができる。以下にその方法を説明する。ここで、局所特徴量間の距離が閾値Ｔｖ以下となり、かつ、最小距離となるような局所特徴量Ｖqと局所特徴量Ｖsとの組み合わせ（対応点）があった場合に、それぞれのスケール番号をＳq、Ｓsとする。また、局所特徴量Ｖqが属する画像をクエリ画像とした場合に、局所特徴量Ｖsが属する画像の類似度を算出する場合を想定する。
【００６２】
解像度の差をΔＳ＝Ｓs−Ｓqとしたとき、局所特徴量Ｖqと局所特徴量Ｖsとが正しい対応点（正対応点）である場合には、解像度の差ΔＳは一定値となる。一方、対応が誤っている点（誤対応点）の解像度の差ΔＳは正対応点の解像度の差ΔＳと一致しないことが多い。つまり、特徴量間の距離で抽出した対応点すべてに対して解像度の差ΔＳを算出し、解像度の差ΔＳの最頻値ΔＳmodを求めることにより、最頻値ΔＳmodを持つ対応点を正対応点と推定できる。
【００６３】
また、最頻値ΔＳmodは比較画像間の解像度の差を表わし、ΔＳmod＞０の場合は局所特徴点Ｖsが属する画像の解像度の方が大きいことを示す。また、ΔＳmod＝０の場合は比較画像間に解像度の差がなく、ΔＳmod＜０の場合は、局所特徴点Ｖsが属する画像の解像度の方が小さいことを示す。
【００６４】
ステップＳ６０１では、局所特徴量Ｖsが属する画像の解像度の方が大きい場合は類似度が大きくなり、局所特徴量Ｖsが属する画像の解像度の方が小さい場合は類似度が小さくなるように、重み付けするための重み係数ｗを決定する。本実施形態では、以下の式（１４）により重み係数ｗを決定する。ここで決定した重み係数ｗは、後述するステップＳ６０２で用いられる。
【００６５】
【数６】
【００６６】
次に、ステップＳ６０２の処理について説明する。
【００６７】
図５のステップＳ５１９では、第１の類似度算出手段として機能することにより最終投票数ＶｏｔｅＭａｘを類似度として出力した。ここで、ステップＳ５１９で出力した類似度を第１の類似度とした場合、ステップＳ６０２では、第２の類似度算出手段として機能することにより第１の類似度とステップＳ６０１で算出した重み係数ｗとを用いて第２の類似度を算出する。本実施形態においては、第２の類似度Ｓｉｍ２を以下の式（１５）により算出し、これを総合類似度とする。このように検索結果の表示順序は、第２の類似度Ｓｉｍ２に応じて決定される。
【００６８】
【数７】
【００６９】
以上のように本実施形態によれば、比較対象画像間の対応点のスケール番号に着目して解像度の差を推定し、解像度の差を類似度に反映するようにした。これにより、ユーザの感覚により合致した類似度を算出することが可能になる。
【００７０】
なお、本実施形態では、スケール番号に着目することによって第１の類似度に重みを付けて第２の類似度を算出し、第２の類似度を総合類似度としたが、解像度情報を利用した類似度算出方法であれば、他の類似度算出方法でもよい。例えば、第１の類似度が所定の閾値以上の場合に、式（１４）の結果をそのまま総合類似度としもよい。
【００７１】
また、本実施形態では、スケール番号に着目することによって解像度の差を推定したが、解像度の差を推定することができれば他の推定方法を用いもよい。例えば、クエリ画像である入力画像１０１と登録画像である入力画像１０４との位置合わせに利用可能なパラメータを用いて解像度の差を求めることができる。以下、推定方法の一例として、最終投票数ＶｏｔｅＭａｘを算出した時の変換行列Ｍを用いる方法について説明する。具体的には、以下の式（１６）により、変換行列Ｍの要素値を用いて、入力画像１０４に対する入力画像１０１の縮小率Ｒを算出する。
【００７２】
【数８】
【００７３】
ここで、Ｒ＜１である場合は、登録画像である入力画像１０４の方がクエリ画像である入力画像１０１よりも解像度が高い。このように、縮小率Ｒを算出することによって解像度の差を推定することが可能となる。さらに、縮小率Ｒを類似度に反映させるために式（１４）及び式（１５）を用いる場合は、以下の式（１７）を用いて最頻値ΔＳmodを求める。
【００７４】
【数９】
【００７５】
また、クエリ画像である入力画像１０１と登録画像である入力画像１０４との位置合わせを行った後に、画像の周波数成分を比較することによっても解像度の差を求めることができる。以下、図５及び図６において、最終投票数ＶｏｔｅＭａｘを算出した時の変換行列Ｍ、Ｔを用いる方法について説明する。具体的には、以下の式（１８）により入力画像１０１に拡大・縮小、及び回転処理を施して入力画像１０４と位置合わせをする。
【００７６】
【数１０】
【００７７】
ここで、Ｑk（ｘk'，ｙk'）は位置合わせ前の入力画像１０１の画素座標であり、Ｑk'（Ｘk'，Ｙk'）は位置合わせ後の入力画像の画素座標である。すなわち、Ｑk（ｘk'，ｙk'）の位置にある画素値をＱk'（Ｘk'，Ｙk'）の位置の画素値として設定することにより、位置合わせ後の入力画像を生成する。このとき、線形補間を用いるように構成してもよい。
【００７８】
次に、周波数成分の比較方法としては、まず、入力画像１０４と前述の位置合わせ後の入力画像とを周波数変換する。ここで、入力画像１０４の最大周波数をｆｓmaxとし、位置合わせ後の入力画像の最大周波数をｆｑmaxとした場合、入力画像１０４に対する位置合わせ後の入力画像の縮小率Ｒは以下の式（１９）により推定できる。
【００７９】
【数１１】
【００８０】
さらに、この縮小率Ｒを類似度に反映させるために式（１４）及び式（１５）を用いる場合は、前述のように、式（１７）により最頻値ΔＳmodを求めればよい。なお、縮小率Ｒは、周波数成分の比ではなく周波数成分の差を用いるようにしてもよい。また、位置合わせを行った後の入力画像と登録画像とが重なりあう領域あるいはその一部に対して周波数成分を比較してもよい。
【００８１】
（その他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００８２】
１０３ 第１の局所特徴点／局所特徴量抽出部
１０６ 第２の局所特徴点／局所特徴量抽出部
１０７ 局所特徴点／局所特徴量比較部
【技術分野】
【０００１】
本発明は、例えば、局所特徴点及び局所特徴量に基づく検索を行うために用いて好適な画像検索装置、画像検索方法及びプログラムに関する。
【背景技術】
【０００２】
従来、画像の局所的な特徴量（局所特徴量）を用いて類似画像を検索する方法が提案されている。この方法では、まず、画像から特徴的な点（局所特徴点）を抽出する。抽出方法については例えば非特許文献１に開示されている方法が挙げられる。そして、当該特徴点とその周辺の画像情報とに基づいて、当該特徴点に対応する特徴量（局所特徴量）を計算する。局所特徴量については例えば非特許文献２に開示されている方法によって計算することができる。このように画像の検索は、局所特徴量同士のマッチングによって行われる。
【０００３】
局所特徴量を利用する手法においては、局所特徴量を回転不変、拡大・縮小不変となる複数の要素で構成される情報として定義する。これにより、画像を回転させたり、拡大又は縮小させたりした場合であっても、画像を検索することができる。また、局所特徴量は一般的にベクトルとして表現される。ただし、局所特徴量が回転不変、拡大・縮小不変であることは理論上の話であり、実際のデジタル画像においては、画像の回転や拡大・縮小処理前の局所特徴量と処理後の対応する局所特徴量との間に若干の変動が生じる。
【０００４】
例えば非特許文献２に記載の方法では、回転不変の局所特徴量を算出するために、局所特徴点周辺の局所領域の画素パターンから主方向を算出し、局所特徴量の算出時に主方向を基準に局所領域を回転させて方向を正規化する。また、拡大・縮小不変の局所特徴量を算出するために、異なる解像度の画像を内部で生成し、各解像度の画像からそれぞれ局所特徴点を抽出し、局所特徴量を算出する。ここで、内部で生成した一連の異なる解像度の画像集合は一般的にスケールスペースと呼ばれる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】C.Harris and M.J. Stephens,"A combined corner and edge detector," In Alvey Vision Conference,pages 147-152, 1988.
【非特許文献２】David G. Lowe, "Distinctive Image Features from Scale-Invariant Keypoints," International Journal of Computer Vision, 60, 2 (2004), pp.91-110.
【非特許文献３】J. J. Koenderink and A. J. van Doorn, "Representation of local geometry in the visual system," Riological cybernetics, vol.55, pp.367-375, 1987.
【非特許文献４】M. A. Fischler and R. C. Bollers, "Random sample consensus: A paradigm formodel fitting with applications to image analysis and automated cartography," Commum. ACM, no.24, vol.6, pp.381-395, June 1981.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
検索結果により画像が表示される順位は、多くの場合、クエリ画像と登録画像との間の類似度が局所特徴量のマッチングにより算出され、その類似度を用いて決定される。局所特徴量のマッチング方法としては、局所特徴量をベクトルに表現してベクトル間の距離を測るものや、ハッシュ表を用いる方法などがある。ところが、このような従来の方法では、検索結果の画像の利用価値の順序と結果の表示順序とが合致しないことがある。このような現象が生じる場合の例とその原因について以下に説明する。
【０００７】
例えば、クエリ画像と同じ解像度で回転のない第１の登録画像と、クエリ画像よりはるかに解像度が高いが若干回転している第２の登録画像とが検索される場合を考える。まず、局所特徴量をマッチングするために、前述のように、それぞれの画像に対してスケールスペースを生成し、各解像度の画像から回転不変の局所特徴量を算出する。
【０００８】
このとき、第２の登録画像からは、クエリ画像には存在しない高解像度の画像がスケールスペースに含まれ、その画像からも局所特徴量が算出される。ところが、これらの局所特徴量は検索時のクエリ画像との局所特徴量のマッチングには寄与しない。クエリ画像と重なる解像度のスケールスペースから算出された第２の登録画像の局所特徴量だけが、クエリ画像との局所特徴量同士のマッチングに寄与することになる。
【０００９】
ここで、第２の登録画像とクエリ画像との間でマッチした局所特徴量ペアのベクトル間距離は、第１の登録画像とクエリ画像との間でマッチした局所特徴量ペア間のベクトル間距離よりも大きくなる可能性が高い。これは、クエリ画像に対して第１の登録画像が回転していない一方で第２の登録画像は若干回転していることに起因する。すなわち、第２の登録画像は回転によって画像にノイズが付与され、そのノイズが局所特徴量を変動させるからである。
【００１０】
この結果、クエリ画像と第１の登録画像との類似度は、解像度の高い第２の登録画像との類似度よりも大きくなる。ところが、第２の登録画像の回転量がユーザの気にならない程度の回転量であった場合には、解像度の高い第２の登録画像の方が第１の登録画像よりも利用価値が高いことがある。例えば、解像度の高い画像の方が、画像の回転や拡大など画像加工時の画質劣化問題を回避しやすいため、再利用性に優れている。
【００１１】
このように、従来の方法では検索結果の画像の利用価値の順序と結果の表示順序とが合致しないという現象が容易に生じ得るという問題がある。
【００１２】
本発明は前述の問題点に鑑み、利用価値の高い順序で検索結果を得ることができるようにすることを目的としている。
【課題を解決するための手段】
【００１３】
本発明の画像検索装置は、入力画像を用いて予め登録されている登録画像を検索する画像検索装置であって、前記入力画像及び登録画像から局所的な局所特徴を抽出する局所特徴抽出手段と、前記局所特徴抽出手段によって抽出された局所特徴に基づいて前記入力画像と前記登録画像との間の第１の類似度を算出する第１の類似度算出手段と、前記第１の類似度算出手段によって算出された第１の類似度と、前記入力画像及び登録画像の解像度情報とに基づいて前記入力画像と前記登録画像との間の第２の類似度を算出する第２の類似度算出手段と、前記第２の類似度算出手段によって算出された第２の類似度に応じて検索結果を出力する出力手段とを備えることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、画像の解像度が反映された利用価値の高い順序で検索結果を出力することができる。
【図面の簡単な説明】
【００１５】
【図１】実施形態における画像検索装置の構成例を示すブロック図である。
【図２】実施形態において、画像の局所特徴点及び局所特徴量を抽出する処理手順の一例を示すフローチャートである。
【図３】図２のステップＳ２０４における縮小画像の生成処理の概要を説明する図である。
【図４】局所特徴点の抽出する概要を説明する図である。
【図５】解像度を考慮しないで類似度を算出する処理手順の一例を示すフローチャートである。
【図６】実施形態における類似度を算出する処理手順の一例を示すフローチャートである。
【図７】実施形態における画像検索装置のハードウェア構成例を示すブロック図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について、図面を参照しながら説明する。
図１は、本実施形態における画像検索装置１００の構成例を示すブロック図である。
図１において、画像検索装置１００は、第１の画像入力部１０２、第２の画像入力部１０５、第１の局所特徴点／局所特徴量抽出部１０３、第２の局所特徴点／局所特徴量抽出部１０６及び局所特徴量比較部１０７から構成されている。
【００１７】
画像検索装置１００では、入力画像１０１が第１の画像入力部１０２に入力されると、第１の局所特徴点／局所特徴量抽出部１０３は、局所特徴として局所特徴点とその局所特徴量とを抽出する。同様に、比較対象となる入力画像１０４が第２の画像入力部１０５に入力されると、第２の局所特徴点／局所特徴量抽出部１０６は、局所特徴として局所特徴点とその局所特徴量とを抽出する。本実施形態では、入力画像１０１をクエリ画像とし、比較対象となる入力画像１０４をデータベースに登録されている登録画像として説明する。また、局所特徴点とその局所特徴量とを抽出する処理の詳細については後述する。
【００１８】
局所特徴点／局所特徴量比較部１０７は、第１の局所特徴点／局所特徴量抽出部１０３及び第２の局所特徴点／局所特徴量抽出部１０６で抽出されたそれぞれの局所特徴点及び局所特徴量同士を比較し、画像表示順序として比較結果１０８を出力する。この局所特徴点及び局所特徴量の比較処理の詳細についても後述する。
【００１９】
図７は、本実施形態に係る画像検索装置１４００のハードウェア構成例を示すブロック図である。
図７において、画像検索装置１４００は例えばパーソナルコンピュータであり、ＲＯＭ１４３０には、後述するフローチャートの処理をＣＰＵ１４１０の制御により実現させるプログラムが格納されている。そして、プログラムを実行させる際には、ＲＯＭ１４３０に格納されたプログラムをＲＡＭ１４２０に読み出してＣＰＵ１４１０が処理できるようにしている。
【００２０】
バス１４５０は、ＲＯＭ１４３０、ＲＡＭ１４２０、ＣＰＵ１４１０及びＨＤＤ１４４０とデータのやりとりを行う。また、画像検索装置１４００は、ユーザインターフェース１４６０に接続されるキーボードやマウスなどの入出力機器からの入力を受ける。さらに、画像検索装置１４００は、ネットワークインターフェース１４７０を介してネットワーク１５００を経由し、データベース（ＤＢ）１５１０、クライアント端末（ＣＬＩＥＮＴ）１５２０、及びプリンタ（ＰＲＩＮＴＥＲ）１５３０とデータの入出力を行う。
【００２１】
また、複数のハードウェアとソフトウェアとの協働によって後述する実施形態の処理を実現してもよい。例えば、画像検索装置１４００がクライアント端末１５２０やプリンタ１５３０から検索依頼とクエリ画像とを受け付け、後述するフローチャートの処理を行い、データベース１５１０からクエリ画像に類似する画像を検索する形態が挙げられる。
【００２２】
［局所特徴抽出処理］
次に、画像の局所特徴（局所特徴点及び局所特徴量）抽出処理を説明する。画像の局所特徴抽出処理は、画像データを読み出すステップ、輝度成分の抽出ステップ、縮小画像の作成ステップ、局所特徴点の抽出ステップ、及び局所特徴量の算出ステップからなる。
【００２３】
図２は、本実施形態において、画像の局所特徴点及び局所特徴量を抽出する処理手順の一例を示すフローチャートである。
まず、ステップＳ２０１により処理を開始し、ステップＳ２０２において、第１の画像入力部１０２及び第２の画像入力部１０５は、それぞれの画像データを読み出す。そして、ステップＳ２０３において、第１の局所特徴点／局所特徴量抽出部１０３及び第２の局所特徴点／局所特徴量抽出部１０６はそれぞれ、画像データから輝度成分を抽出し、輝度成分画像を生成する。
【００２４】
次に、ステップＳ２０４において、第１の局所特徴点／局所特徴量抽出部１０３及び第２の局所特徴点／局所特徴量抽出部１０６はそれぞれ、ステップＳ２０３で作成した当該輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成する。ただし、倍率ｐ及び縮小画像の枚数ｎは予め決められているものとする。
【００２５】
図３は、図２のステップＳ２０４における縮小画像の生成処理の概要を説明する図である。なお、図３では、倍率ｐを２の−（１／４）乗とし、縮小画像の枚数ｎを９とした場合の例を示している。また、図３に示す例では、倍率ｐを面積比ではなく辺の長さの比としている。
【００２６】
図３において、３０１はステップＳ２０３で作成した輝度成分画像である。３０２は輝度成分画像３０１から倍率ｐに従って４回縮小された縮小画像であり、輝度成分画像３０１を１／２に縮小した画像に相当する。また、３０３は輝度成分画像３０１から倍率ｐに従って８回縮小された縮小画像であり、輝度成分画像３０１を１／４に縮小した画像に相当する。なお、画像を縮小する方法は単純に画素を間引く方法、線形補間を用いる方法、低域フィルタ適用後にサンプリングする方法などを用いることができるが、何れの方法でもよい。本実施形態では、線形補間による縮小方法を用いて画像を縮小するものとする。
【００２７】
３０４はスケール番号であり、縮小画像のサイズが大きい方から順に解像度に応じて付与される番号である。本実施形態では、スケール番号は１から始まるようにしているが、０から始まるようにしてもよい。
【００２８】
図２の説明に戻り、次に、ステップＳ２０５において、第１の局所特徴点／局所特徴量抽出部１０３及び第２の局所特徴点／局所特徴量抽出部１０６は、ステップＳ２０４で得られたｎ枚の縮小画像のそれぞれから局所的な特徴点（局所特徴点）を抽出する。ここで抽出する局所特徴点は、画像に回転や縮小などの画像処理を施しても同じ場所から安定的に抽出されるようなロバストな局所特徴点である。このような局所特徴点を抽出する方法として、本実施形態では、非特許文献１に記載されているＨａｒｒｉｓ作用素を用いる。
【００２９】
具体的には、Ｈａｒｒｉｓ作用素を作用させて得られた画像の画素それぞれについて、着目画素とその周辺にある８つの画素との合計９画素の画素値を調べる。そして、着目画素の画素値が予め定めた値以上であり、かつ局所極大になる（当該９画素の中で当該画素の画素値が最大になる）場合に、その着目画素が位置する点を局所特徴点として抽出する。なお、ロバストな局所特徴点を抽出可能な方法であれば、上述のＨａｒｒｉｓ作用素による特徴点抽出方法に限らず、どのような特徴点抽出方法でも適用可能である。
【００３０】
次に、ステップＳ２０６において、ステップＳ２０５で得られた局所特徴点それぞれについて、画像の回転があっても不変となるように定義された特徴量（局所特徴量）を算出する。この局所特徴量の算出方法として、本実施形態では非特許文献３に記載されているLocal Jet及びそれらの導関数の組み合わせを用いる。この方法により算出される局所特徴量は、拡大縮小、回転に対して、比較的高い耐性を持つような特性を持たせることができる。具体的には、以下の式（１）により局所特徴量を算出する。
【００３１】
【数１】
【００３２】
ただし、式（１）の右辺で用いている記号は、以下の式（２）から式（７）に示すように定義される。
【００３３】
【数２】
【００３４】
ここで、式（２）右辺のＧ（ｘ，ｙ）はガウス関数であり、Ｉ（ｘ，ｙ）は画像の座標（ｘ，ｙ）における画素値であり、"＊"は畳み込み演算を表す記号である。また、式（３）は式（２）で定義された変数Ｌのｘに関する偏導関数であり、式（４）は当該変数Ｌのｙに関する偏導関数である。式（５）は式（３）で定義された変数Ｌxのｙに関する偏導関数である。式（６）は式（３）で定義された変数Ｌxのｘに関する偏導関数であり、式（７）は式（４）で定義されたＬyのｙに関する偏導関数である。
【００３５】
なお、局所特徴量の算出方法は、上述の方法に限らず他の局所特徴量の算出方法も適用可能である。他の局所特徴量の算出方法として、例えば非特許文献２に記載されている方法がある。この方法では、局所特徴点周辺の局所領域内の各画素に対して画素値の勾配方向を算出し、そのヒストグラムを局所特徴量としている。
【００３６】
図４は、局所特徴点の抽出する概要を説明する図である。図４（ａ）は入力画像４１０を示しており、図４（ｂ）は、入力画像４１０から抽出した局所特徴点４２１、４２２を重畳した入力画像４２０を示している。図４に示す例では、局所特徴点４２１、４２２に対してそれぞれ局所特徴量が計算される。
【００３７】
［類似度算出方法］
まず、一般的な方法を用いて類似度を算出する方法について説明する。類似度の算出方法では様々な方法を用いることができるが、以下の説明では、例えば非特許文献４に記載されているＲＡＮＳＡＣを利用した類似度算出方法について説明する。
【００３８】
ここで、入力画像の局所特徴点をＱとし、その座標をＱ（ｘ'，ｙ'）とし、その局所特徴点Ｑの局所特徴量をＶqとする。また、比較対象となる入力画像の画像上の局所特徴点をＳとして、その座標をＳ（ｘ，ｙ）とし、その局所特徴点Ｓの局所特徴量をＶsとする。
【００３９】
図５は、解像度を考慮しないで類似度を算出する処理手順の一例を示すフローチャートである。
ステップＳ５０１で処理を開始すると、ステップＳ５０２において、局所特徴量Ｖqと局所特徴量Ｖsとを照合して最小距離対応点リストを作成する。具体的には、まず、局所特徴量Ｖqと局所特徴量Ｖsとの全ての組み合わせについて局所特徴量間の距離を計算する。次に、計算した局所特徴量間の距離が閾値Ｔｖ以下となり、かつ、最小距離となるような局所特徴量Ｖqと局所特徴量Ｖsとの組み合わせ（対応点）を抽出する。これらの対応点を最小距離対応点リストに登録することにより、最小距離対応点リストを作成する。
【００４０】
ここで、最小距離対応点リストには、例えばｋ番目の最小距離対応点をそれぞれＱk、Ｓkと表わし、これらの座標をＱk（ｘk'，ｙk'）、Ｓk（ｘk，ｙk）とし、添え字を合わせて記載する。なお、１つの局所特徴点に対応付けられる局所特徴量は２つ以上あってもよいが、以下の説明では説明を簡略化するため、１つの局所特徴点に対応付けられる局所特徴量は１つだけとする。そして、前記Ｑk、Ｓkの局所特徴量をそれぞれＶq（ｋ）、Ｖs（ｋ）とする。また、ステップＳ５０２では、ｍ組の対応点が最小距離対応点リストに登録されるものとする。
【００４１】
次に、ステップＳ５２１において、ｍが３以上であるか否かを判定する。この判定の結果、ｍが３未満である場合は、類似度を算出できないため、ステップＳ５２２に進み、処理を終了する。
【００４２】
一方、ステップＳ５２１の判定の結果、ｍが３以上である場合は、ステップＳ５０３において、最終投票数を表す変数ＶｏｔｅＭａｘを０に初期化する。そして、ステップＳ５０４において、類似度算出処理の反復カウント数を表す変数Ｃｏｕｎｔを０に初期化する。
【００４３】
次に、ステップＳ５０５において、反復カウント数Ｃｏｕｎｔが予め定められた最大反復処理回数Ｒｎを超えていないか否かを判定する。この判定の結果、反復カウント数Ｃｏｕｎｔが最大反復処理回数Ｒｎを超えていない場合はステップＳ５０６へ進み、投票数を表す変数Ｖｏｔｅを０に初期化する。一方、ステップＳ５０５の判定の結果、反復カウント数Ｃｏｕｎｔが最大反復処理回数Ｒｎを超えている場合には、ステップＳ５１９へ進み、最終投票数ＶｏｔｅＭａｘを類似度として出力し、ステップＳ５２０において処理を終了する。
【００４４】
次に、ステップＳ５０７において、最小距離対応点リストから対応点の組の座標をランダムに２組抽出する。ここで、抽出した２組の座標をＱ1（ｘ1'，ｙ1'）、Ｓ1（ｘ1，ｙ1）、及びＱ2（ｘ2'，ｙ2'）、Ｓ2（ｘ2，ｙ2）と定義する。そして、ステップＳ５０８において、変換行列Ｍ、Ｔを計算する。ここで、行列Ｍは、以下の式（８）において変数ａ〜ｄで構成される行列であり、行列Ｔは変数ｅ〜ｆで構成される行列である。
【００４５】
【数３】
【００４６】
ここで、以下の説明では説明を簡略化するため、相似変換だけを考える。この場合には、上記式（８）は以下の式（９）のように書き換えられる。
【００４７】
【数４】
【００４８】
また、式（９）における変数ａ、ｂ、ｅ、ｆは、座標Ｑ1（ｘ1'，ｙ1'）、Ｓ1（ｘ1，ｙ1）及びＱ2（ｘ2'，ｙ2'）、Ｓ2（ｘ2，ｙ2）の座標値を用いて以下の式（１０）〜式（１３）で表すことができる。
【００４９】
【数５】
【００５０】
次に、ステップＳ５０９において、ステップＳ５０７で最短距離対応点リストからランダムに抽出された２組の点以外の点を選択するために、対応点選択変数ｋを３に初期化する。そして、ステップＳ５１０において、対応点選択変数ｋが最短距離対応点リストに登録されている対応点の組数ｍを超えていないか否かを判定する。この判定の結果、組数ｍを超えている場合はステップＳ５１６へ進む。ステップＳ５１６の処理については後述する。
【００５１】
一方、ステップＳ５１０の判定の結果、組数ｍを超えていない場合は、ステップＳ５１１において、最小距離対応点リストから新たな対応点の組を１組抽出する。ここでは、抽出した座標をＳk（ｘk，ｙk）、Ｑk（ｘk'，ｙk'）と定義する。なお、抽出する際には、ステップＳ５０７と同様に付加情報を利用する。
【００５２】
次に、ステップＳ５１２において、式（９）によりＳk（ｘk，ｙk）を変換した座標Ｓk'（ｘk"，ｙk"）を求める。その後、ステップＳ５１３において、座標Ｓk'（ｘk"，ｙk"）と座標Ｑk（ｘk'，ｙk'）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離が閾値Ｔｄ以下であるか否かを判定する。この判定の結果、当該ユークリッド距離が閾値Ｔｄ以下の場合はステップＳ５１４へ進み、投票数Ｖｏｔｅをインクリメントした後、ステップＳ５１５へ進む。一方、ステップＳ５１３の判定の結果、当該ユークリッド距離が閾値Ｔｄより大きい場合は、何もせずにステップＳ５１５へ進む。
【００５３】
次に、ステップＳ５１５において、対応点選択変数ｋをインクリメントし、ステップＳ５１０に戻り、対応点選択変数ｋが最短距離対応点リストに登録されている対応点の組数ｍを超えるまで、上述の処理を繰り返す。
【００５４】
次に、ステップＳ５１０で、対応点選択変数ｋが当該対応点リストに登録されている対応点の組数ｍを超えた場合について説明する。ステップＳ５１６においては、投票数Ｖｏｔｅの値と最終投票数ＶｏｔｅＭａｘの値とを比較し、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値よりも大きいか否かを判定する。この判定の結果、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値よりも大きい場合にはステップＳ５１７へ進む。
【００５５】
ステップＳ５１７においては、最終投票数ＶｏｔｅＭａｘの値を投票数Ｖｏｔｅの値で置き換える。そして、ステップＳ５１８において反復カウント数Ｃｏｕｎｔをインクリメントし、ステップＳ５０５に戻る。一方、ステップＳ５１６の判定の結果、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値以下の場合にはステップＳ５１８へ処理を移し、反復カウント数ＣｏｕｎｔをインクリメントしてステップＳ５０５に処理を戻す。
【００５６】
なお、図５の説明では、相似変換だけを考慮して説明したが、アフィン変換などその他の幾何学変換についても、ステップＳ５０８でそれぞれに応じた変換行列を求めることにより、対応可能である。例えば、アフィン変換の場合には、まずステップＳ５０７で、ランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ５０８で、式（９）ではなく式（８）を用い、ステップＳ５０７で選択した３組の対応点（合計６点）を用いて変数ａ〜ｆを求めればよい。
【００５７】
また、図５の説明では、ステップＳ５１９で類似度として最終投票数ＶｏｔｅＭａｘを出力する例について説明したが、他の類似度を計算するようにしてもよい。例えば、ステップＳ５０３以降の処理を行わずに、ステップＳ５０２で作成された最小距離対応点リストに登録された対応点の組数ｍを類似度として出力する方法がある。
【００５８】
次に、本実施形態における類似度算出方法について、図６を参照しながら説明する。
図６は、本実施形態において、局所特徴点／局所特徴量比較部１０７により類似度を算出する処理手順の一例を示すフローチャートである。図６に示すフローチャートでは、図５の処理手順にステップＳ６０１の処理が追加され、さらに図５のステップＳ５１９の処理がステップＳ６０２の処理に入れ替わっている。なお、図５の同じ符号を付しているステップＳ５０１〜Ｓ５１８、Ｓ５２０〜Ｓ５２２については図５と同様であるため、説明は省略する。
【００５９】
まず、ステップＳ６０１の処理について説明する。
【００６０】
図５に示した手順では、まず、ステップＳ５０２で、局所特徴量Ｖqと局所特徴量Ｖsとの全ての組み合わせについて局所特徴量間の距離を計算する。次に、計算した局所特徴量間の距離が閾値Ｔｖ以下となり、かつ、最小距離となるような局所特徴量Ｖqと局所特徴量Ｖsとの組み合わせ（対応点）を抽出し、これらの対応点を登録することにより最小距離対応点リストを作成する。
【００６１】
このとき、図３に示したスケール番号３０４に着目することにより比較対象画像との間の解像度の差を推定することができる。以下にその方法を説明する。ここで、局所特徴量間の距離が閾値Ｔｖ以下となり、かつ、最小距離となるような局所特徴量Ｖqと局所特徴量Ｖsとの組み合わせ（対応点）があった場合に、それぞれのスケール番号をＳq、Ｓsとする。また、局所特徴量Ｖqが属する画像をクエリ画像とした場合に、局所特徴量Ｖsが属する画像の類似度を算出する場合を想定する。
【００６２】
解像度の差をΔＳ＝Ｓs−Ｓqとしたとき、局所特徴量Ｖqと局所特徴量Ｖsとが正しい対応点（正対応点）である場合には、解像度の差ΔＳは一定値となる。一方、対応が誤っている点（誤対応点）の解像度の差ΔＳは正対応点の解像度の差ΔＳと一致しないことが多い。つまり、特徴量間の距離で抽出した対応点すべてに対して解像度の差ΔＳを算出し、解像度の差ΔＳの最頻値ΔＳmodを求めることにより、最頻値ΔＳmodを持つ対応点を正対応点と推定できる。
【００６３】
また、最頻値ΔＳmodは比較画像間の解像度の差を表わし、ΔＳmod＞０の場合は局所特徴点Ｖsが属する画像の解像度の方が大きいことを示す。また、ΔＳmod＝０の場合は比較画像間に解像度の差がなく、ΔＳmod＜０の場合は、局所特徴点Ｖsが属する画像の解像度の方が小さいことを示す。
【００６４】
ステップＳ６０１では、局所特徴量Ｖsが属する画像の解像度の方が大きい場合は類似度が大きくなり、局所特徴量Ｖsが属する画像の解像度の方が小さい場合は類似度が小さくなるように、重み付けするための重み係数ｗを決定する。本実施形態では、以下の式（１４）により重み係数ｗを決定する。ここで決定した重み係数ｗは、後述するステップＳ６０２で用いられる。
【００６５】
【数６】
【００６６】
次に、ステップＳ６０２の処理について説明する。
【００６７】
図５のステップＳ５１９では、第１の類似度算出手段として機能することにより最終投票数ＶｏｔｅＭａｘを類似度として出力した。ここで、ステップＳ５１９で出力した類似度を第１の類似度とした場合、ステップＳ６０２では、第２の類似度算出手段として機能することにより第１の類似度とステップＳ６０１で算出した重み係数ｗとを用いて第２の類似度を算出する。本実施形態においては、第２の類似度Ｓｉｍ２を以下の式（１５）により算出し、これを総合類似度とする。このように検索結果の表示順序は、第２の類似度Ｓｉｍ２に応じて決定される。
【００６８】
【数７】
【００６９】
以上のように本実施形態によれば、比較対象画像間の対応点のスケール番号に着目して解像度の差を推定し、解像度の差を類似度に反映するようにした。これにより、ユーザの感覚により合致した類似度を算出することが可能になる。
【００７０】
なお、本実施形態では、スケール番号に着目することによって第１の類似度に重みを付けて第２の類似度を算出し、第２の類似度を総合類似度としたが、解像度情報を利用した類似度算出方法であれば、他の類似度算出方法でもよい。例えば、第１の類似度が所定の閾値以上の場合に、式（１４）の結果をそのまま総合類似度としもよい。
【００７１】
また、本実施形態では、スケール番号に着目することによって解像度の差を推定したが、解像度の差を推定することができれば他の推定方法を用いもよい。例えば、クエリ画像である入力画像１０１と登録画像である入力画像１０４との位置合わせに利用可能なパラメータを用いて解像度の差を求めることができる。以下、推定方法の一例として、最終投票数ＶｏｔｅＭａｘを算出した時の変換行列Ｍを用いる方法について説明する。具体的には、以下の式（１６）により、変換行列Ｍの要素値を用いて、入力画像１０４に対する入力画像１０１の縮小率Ｒを算出する。
【００７２】
【数８】
【００７３】
ここで、Ｒ＜１である場合は、登録画像である入力画像１０４の方がクエリ画像である入力画像１０１よりも解像度が高い。このように、縮小率Ｒを算出することによって解像度の差を推定することが可能となる。さらに、縮小率Ｒを類似度に反映させるために式（１４）及び式（１５）を用いる場合は、以下の式（１７）を用いて最頻値ΔＳmodを求める。
【００７４】
【数９】
【００７５】
また、クエリ画像である入力画像１０１と登録画像である入力画像１０４との位置合わせを行った後に、画像の周波数成分を比較することによっても解像度の差を求めることができる。以下、図５及び図６において、最終投票数ＶｏｔｅＭａｘを算出した時の変換行列Ｍ、Ｔを用いる方法について説明する。具体的には、以下の式（１８）により入力画像１０１に拡大・縮小、及び回転処理を施して入力画像１０４と位置合わせをする。
【００７６】
【数１０】
【００７７】
ここで、Ｑk（ｘk'，ｙk'）は位置合わせ前の入力画像１０１の画素座標であり、Ｑk'（Ｘk'，Ｙk'）は位置合わせ後の入力画像の画素座標である。すなわち、Ｑk（ｘk'，ｙk'）の位置にある画素値をＱk'（Ｘk'，Ｙk'）の位置の画素値として設定することにより、位置合わせ後の入力画像を生成する。このとき、線形補間を用いるように構成してもよい。
【００７８】
次に、周波数成分の比較方法としては、まず、入力画像１０４と前述の位置合わせ後の入力画像とを周波数変換する。ここで、入力画像１０４の最大周波数をｆｓmaxとし、位置合わせ後の入力画像の最大周波数をｆｑmaxとした場合、入力画像１０４に対する位置合わせ後の入力画像の縮小率Ｒは以下の式（１９）により推定できる。
【００７９】
【数１１】
【００８０】
さらに、この縮小率Ｒを類似度に反映させるために式（１４）及び式（１５）を用いる場合は、前述のように、式（１７）により最頻値ΔＳmodを求めればよい。なお、縮小率Ｒは、周波数成分の比ではなく周波数成分の差を用いるようにしてもよい。また、位置合わせを行った後の入力画像と登録画像とが重なりあう領域あるいはその一部に対して周波数成分を比較してもよい。
【００８１】
（その他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００８２】
１０３ 第１の局所特徴点／局所特徴量抽出部
１０６ 第２の局所特徴点／局所特徴量抽出部
１０７ 局所特徴点／局所特徴量比較部
【特許請求の範囲】
【請求項１】
入力画像を用いて予め登録されている登録画像を検索する画像検索装置であって、
前記入力画像及び登録画像から局所的な局所特徴を抽出する局所特徴抽出手段と、
前記局所特徴抽出手段によって抽出された局所特徴に基づいて前記入力画像と前記登録画像との間の第１の類似度を算出する第１の類似度算出手段と、
前記第１の類似度算出手段によって算出された第１の類似度と、前記入力画像及び登録画像の解像度情報とに基づいて前記入力画像と前記登録画像との間の第２の類似度を算出する第２の類似度算出手段と、
前記第２の類似度算出手段によって算出された第２の類似度に応じて検索結果を出力する出力手段とを備えることを特徴とする画像検索装置。
【請求項２】
前記第２の類似度算出手段は、前記解像度情報を用いて前記第１の類似度に重み付けすることにより前記第２の類似度を算出することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記解像度情報は、前記入力画像と前記登録画像との解像度の差であることを特徴とする請求項１又は２に記載の画像検索装置。
【請求項４】
前記解像度の差は、前記入力画像と前記登録画像との位置合わせに用いられるパラメータによって算出される値であることを特徴とする請求項３に記載の画像検索装置。
【請求項５】
前記解像度の差は、前記入力画像と前記登録画像との位置合わせが行われたた後に、それぞれの画像の周波数成分の比較によって算出される値であることを特徴とする請求項３に記載の画像検索装置。
【請求項６】
前記周波数成分の比較は、前記周波数成分の差又は比による比較であることであることを特徴とする請求項５に記載の画像検索装置。
【請求項７】
前記周波数成分の比較は、前記入力画像及び登録画像の最大周波数の比較であることを特徴とする請求項５又は６に記載の画像検索装置。
【請求項８】
前記周波数成分の比較は、前記位置合わせを行った後の前記入力画像と前記登録画像とが重なりあう領域あるいはその一部に対して行われることを特徴とする請求項５又は６に記載の画像検索装置。
【請求項９】
前記位置合わせは、前記入力画像又は前記登録画像に対する回転、拡大又は縮小によるものであることを特徴とする請求項４〜８の何れか１項に記載の画像検索装置。
【請求項１０】
前記解像度の差は、前記入力画像と前記登録画像とで局所特徴を照合することにより得られる対応点の前記解像度に応じて付与された番号の差であることを特徴とする請求項３に記載の画像検索装置。
【請求項１１】
入力画像を用いて予め登録されている登録画像を検索する画像検索方法であって、
前記入力画像及び登録画像から局所的な局所特徴を抽出する局所特徴抽出工程と、
前記局所特徴抽出工程において抽出された局所特徴に基づいて前記入力画像と前記登録画像との間の第１の類似度を算出する第１の類似度算出工程と、
前記第１の類似度算出工程において算出された第１の類似度と、前記入力画像及び登録画像の解像度情報とに基づいて前記入力画像と前記登録画像との間の第２の類似度を算出する第２の類似度算出工程と、
前記第２の類似度算出工程において算出された第２の類似度に応じて検索結果を出力する出力工程とを備えることを特徴とする画像検索方法。
【請求項１２】
入力画像を用いて予め登録されている登録画像を検索する画像検索装置を制御するためのプログラムであって、
前記入力画像及び登録画像から局所的な局所特徴を抽出する局所特徴抽出工程と、
前記局所特徴抽出工程において抽出された局所特徴に基づいて前記入力画像と前記登録画像との間の第１の類似度を算出する第１の類似度算出工程と、
前記第１の類似度算出工程において算出された第１の類似度と、前記入力画像及び登録画像の解像度情報とに基づいて前記入力画像と前記登録画像との間の第２の類似度を算出する第２の類似度算出工程と、
前記第２の類似度算出工程において算出された第２の類似度に応じて検索結果を出力する出力工程とをコンピュータに実行させることを特徴とするプログラム。
【請求項１】
入力画像を用いて予め登録されている登録画像を検索する画像検索装置であって、
前記入力画像及び登録画像から局所的な局所特徴を抽出する局所特徴抽出手段と、
前記局所特徴抽出手段によって抽出された局所特徴に基づいて前記入力画像と前記登録画像との間の第１の類似度を算出する第１の類似度算出手段と、
前記第１の類似度算出手段によって算出された第１の類似度と、前記入力画像及び登録画像の解像度情報とに基づいて前記入力画像と前記登録画像との間の第２の類似度を算出する第２の類似度算出手段と、
前記第２の類似度算出手段によって算出された第２の類似度に応じて検索結果を出力する出力手段とを備えることを特徴とする画像検索装置。
【請求項２】
前記第２の類似度算出手段は、前記解像度情報を用いて前記第１の類似度に重み付けすることにより前記第２の類似度を算出することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記解像度情報は、前記入力画像と前記登録画像との解像度の差であることを特徴とする請求項１又は２に記載の画像検索装置。
【請求項４】
前記解像度の差は、前記入力画像と前記登録画像との位置合わせに用いられるパラメータによって算出される値であることを特徴とする請求項３に記載の画像検索装置。
【請求項５】
前記解像度の差は、前記入力画像と前記登録画像との位置合わせが行われたた後に、それぞれの画像の周波数成分の比較によって算出される値であることを特徴とする請求項３に記載の画像検索装置。
【請求項６】
前記周波数成分の比較は、前記周波数成分の差又は比による比較であることであることを特徴とする請求項５に記載の画像検索装置。
【請求項７】
前記周波数成分の比較は、前記入力画像及び登録画像の最大周波数の比較であることを特徴とする請求項５又は６に記載の画像検索装置。
【請求項８】
前記周波数成分の比較は、前記位置合わせを行った後の前記入力画像と前記登録画像とが重なりあう領域あるいはその一部に対して行われることを特徴とする請求項５又は６に記載の画像検索装置。
【請求項９】
前記位置合わせは、前記入力画像又は前記登録画像に対する回転、拡大又は縮小によるものであることを特徴とする請求項４〜８の何れか１項に記載の画像検索装置。
【請求項１０】
前記解像度の差は、前記入力画像と前記登録画像とで局所特徴を照合することにより得られる対応点の前記解像度に応じて付与された番号の差であることを特徴とする請求項３に記載の画像検索装置。
【請求項１１】
入力画像を用いて予め登録されている登録画像を検索する画像検索方法であって、
前記入力画像及び登録画像から局所的な局所特徴を抽出する局所特徴抽出工程と、
前記局所特徴抽出工程において抽出された局所特徴に基づいて前記入力画像と前記登録画像との間の第１の類似度を算出する第１の類似度算出工程と、
前記第１の類似度算出工程において算出された第１の類似度と、前記入力画像及び登録画像の解像度情報とに基づいて前記入力画像と前記登録画像との間の第２の類似度を算出する第２の類似度算出工程と、
前記第２の類似度算出工程において算出された第２の類似度に応じて検索結果を出力する出力工程とを備えることを特徴とする画像検索方法。
【請求項１２】
入力画像を用いて予め登録されている登録画像を検索する画像検索装置を制御するためのプログラムであって、
前記入力画像及び登録画像から局所的な局所特徴を抽出する局所特徴抽出工程と、
前記局所特徴抽出工程において抽出された局所特徴に基づいて前記入力画像と前記登録画像との間の第１の類似度を算出する第１の類似度算出工程と、
前記第１の類似度算出工程において算出された第１の類似度と、前記入力画像及び登録画像の解像度情報とに基づいて前記入力画像と前記登録画像との間の第２の類似度を算出する第２の類似度算出工程と、
前記第２の類似度算出工程において算出された第２の類似度に応じて検索結果を出力する出力工程とをコンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１３−７３４７６（Ｐ２０１３−７３４７６Ａ）
【公開日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願番号】特願２０１１−２１２９８０（Ｐ２０１１−２１２９８０）
【出願日】平成２３年９月２８日（２０１１．９．２８）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願日】平成２３年９月２８日（２０１１．９．２８）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]