(57)【特許請求の範囲】
【請求項１】
入力画像に基づいて、１または複数の比較画像を選択する選択手段と、
前記入力画像に対する、前記選択された比較画像の回転角度を算出する回転角度算出手段と、
前記回転角度算出手段によって算出された前記比較画像の回転角度が所定の値よりも大きい場合に、前記回転角度算出手段によって算出された回転角度に基づいて前記選択された比較画像を回転させる回転手段と、
前記回転手段によって回転された比較画像と、当該比較画像の回転の状態を示す補助画像と、を出力する出力手段とを有することを特徴とする画像検索装置。
【請求項２】
入力画像に基づいて、１または複数の比較画像を選択する選択手段と、
前記入力画像に対する、前記選択された比較画像の回転角度を算出する回転角度算出手段と、
前記選択された比較画像を出力する出力手段と、
前記出力手段により出力された比較画像に対して指示がなされ、かつ前記回転角度算出手段によって算出された前記比較画像の回転角度が所定の値よりも大きい場合に、前記回転角度算出手段によって算出された回転角度に基づいて前記比較画像を回転させる回転手段とを有し、
前記出力手段は前記比較画像と、当該比較画像の回転の状態を示す補助画像と、を出力することを特徴とする画像検索装置。
【請求項３】
入力画像に基づいて、１または複数の比較画像を選択する選択手段と、
前記入力画像に対する、前記選択された比較画像の回転角度を算出する回転角度算出手段と、
前記入力画像及び前記選択された比較画像の解像度の差が所定値よりも小さい場合に、前記回転角度算出手段によって算出された回転角度に基づいて前記比較画像を回転させる回転手段と、
前記回転手段によって回転された比較画像と、当該比較画像の回転の状態を示す補助画像と、を出力する出力手段とを有することを特徴とする画像検索装置。
【請求項４】
入力画像に基づいて、１または複数の比較画像を選択する選択手段と、
前記入力画像に対する、前記選択された比較画像の回転角度を算出する回転角度算出手段と、
前記回転角度が所定の値より大きい場合、または前記回転角度が前記所定の値以下であり、かつ前記入力画像及び比較画像の解像度の差が所定値よりも小さい場合に、前記回転角度算出手段によって算出された回転角度に基づいて前記比較画像を回転させる回転手段と、
前記回転手段によって回転された比較画像と、当該比較画像の回転の状態を示す補助画像と、を出力する出力手段とを有することを特徴とする画像検索装置。
【請求項５】
前記選択手段は、
前記入力画像及び前記比較画像から局所的な局所特徴を抽出する局所特徴抽出手段と、
前記局所特徴抽出手段によって抽出された前記入力画像及び比較画像の局所特徴を照合して類似度を算出する照合手段と、
を有することを特徴とする請求項１から４のいずれか１項に記載の画像検索装置。
【請求項６】
前記出力手段は、前記回転手段によって回転された比較画像を、前記照合手段によって算出された類似度に応じて出力することを特徴とする請求項５に記載の画像検索装置。
【請求項７】
前記補助画像は、前記比較画像の回転の状態を示す矩形であることを特徴とする請求項１から６のいずれか１項に記載の画像検索装置。
【請求項８】
入力画像に基づいて、１または複数の比較画像を選択する選択工程と、
前記入力画像に対する、前記選択された比較画像の回転角度を算出する回転角度算出工程と、
前記回転角度算出工程で算出された前記比較画像の回転角度が所定の値よりも大きい場合に、前記回転角度算出工程で算出された回転角度に基づいて前記選択された比較画像を回転させる回転工程と、
前記回転工程で回転された比較画像と、当該比較画像の回転の状態を示す補助画像と、を出力する出力工程とを有することを特徴とする画像検索方法。
【請求項９】
コンピュータを、請求項１から７のいずれか１項に記載の画像検索装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、局所特徴点及び局所特徴量に基づく検索を行うために用いて好適な技術に関する。
【背景技術】
【０００２】
従来、画像の局所的な特徴量（局所特徴量）を用いて類似画像を検索する方法が提案されている。この方法では、まず、画像から特徴的な点（局所特徴点）を抽出する。抽出方法については例えば非特許文献１に開示されている方法が挙げられる。そして、当該特徴点とその周辺の画像情報とに基づいて、当該特徴点に対応する特徴量（局所特徴量）を計算する。局所特徴量については例えば非特許文献２に開示されている方法によって計算することができる。このように画像の検索は、局所特徴量同士のマッチングによって行われる。
【０００３】
局所特徴量を利用する手法においては、局所特徴量を回転不変、拡大・縮小不変となる複数の要素で構成される情報として定義する。これにより、画像を回転させたり、拡大又は縮小させたりした場合であっても、画像を検索することができる。また、局所特徴量は一般的にベクトルとして表現される。ただし、局所特徴量が回転不変、拡大・縮小不変であることは理論上の話であり、実際のデジタル画像においては、画像の回転や拡大・縮小処理前の局所特徴量と処理後の対応する局所特徴量との間に若干の変動が生じる。
【０００４】
例えば非特許文献２に記載の方法では、回転不変の局所特徴量を算出するために、局所特徴点周辺の局所領域の画素パターンから主方向を算出し、局所特徴量の算出時に主方向を基準に局所領域を回転させて方向を正規化する。また、拡大・縮小不変の局所特徴量を算出するために、異なる解像度の画像を内部で生成し、各解像度の画像からそれぞれ局所特徴点を抽出し、局所特徴量を算出する。ここで、内部で生成した一連の異なる解像度の画像集合は一般的にスケールスペースと呼ばれる。
【０００５】
また、従来の検索結果の表示方法では、多くの場合、クエリ画像と検索先画像（サンプル画像）との間の類似度を局所特徴量のマッチングにより算出し、類似度順にサムネール画像を表示する。
【０００６】
一方、このように検索結果が表示され、回転しているオブジェクトが同一であることを知覚する際には、頭の中で回転したイメージを作ってからマッチングしているという定説がある。以下、このような感覚を心的回転と呼ぶ。非特許文献３には、心的回転を伴う知覚時間は、対象オブジェクトの回転角度に比例し、１８０度回転の場合には、回転なしの場合に比べて約２倍の時間を要することが記載されている。
【０００７】
検索結果として表示される多数の画像を確認するとき、この心的回転を伴うことにより知覚時間が増加し、ユーザの負担が大きくなってしまう場合がある。そこで、オブジェクトを囲む矩形を回転表示する例が知られているが、知覚対象オブジェクト（検索結果）が回転している場合に、オブジェクトを矩形で囲むだけではユーザの負担を考慮した処理とは言えない。
【０００８】
また、画像を回転処理する他の例として、人物画像が含まれる画像の天地方向を判別し、その判別結果に基づいて前記画像を実際の天地方向に修正した後、画像中の人物像が存在する領域を抽出する方法が提案されている（例えば、特許文献１参照）。
【０００９】
さらには、動画像のフレームの傾きを補正する方法も提案されている（例えば、特許文献２参照）。この方法では、まず、動きベクトルを利用して、フレーム画像を構成する領域を動き量が相対的に大きな領域と小さな領域とに分割する。次に、動き量が相対的に小さな領域から補正パラメータを検出する。最後にフレーム画像に対して動き補正を施す。この方法では、傾きの程度に関わらず必ず傾き判定処理を行うように構成している。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００５−２１５７６０号公報
【特許文献２】国際公開第２００９／００１５１０号
【非特許文献】
【００１１】
【非特許文献１】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.
【非特許文献３】Jacques Vauclair, Joel Fagot, William D Hopkins, "Rotation of mental images in baboons when the visual input is directed to the left cerebral hemisphere," Psychological Science, Vol. 4(2), pp.99-103, 1993.
【非特許文献４】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及びそれらの導関数の組み合わせを用いる。この方法により算出される局所特徴量は、拡大縮小、回転に対して、比較的高い耐性を持つような特性を持たせることができる。具体的には、以下の式（１）により局所特徴量を算出する。
【００３０】
【数１】
0006017005.tif 000002
【００３１】
ただし、式（１）の右辺で用いている記号は、以下の式（２）から式（７）に示すように定義される。
【００３２】
【数２】
0006017005.tif 000003
【００３３】
ここで、式（２）右辺のＧ（ｘ，ｙ）はガウス関数であり、Ｉ（ｘ，ｙ）は画像の座標（ｘ，ｙ）における画素値であり、"＊"は畳み込み演算を表す記号である。また、式（３）は式（２）で定義された変数Ｌのｘに関する偏導関数であり、式（４）は当該変数Ｌのｙに関する偏導関数である。式（５）は式（３）で定義された変数Ｌ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）と定義する。そして、ステップＳ５０８において、変換行列Ｍ、Ｔを計算する。ここで、行列Ｍは、以下の式（８）において変数ａ〜ｄで構成される行列であり、行列Ｔは変数ｅ〜ｆで構成される行列である。
【００５０】
【数３】
0006017005.tif 000004
【００５１】
ここで、以下の説明では、説明を簡略化するため、相似変換だけを考える。この場合には、上記式（８）は以下の式（９）のように書き換えられる。
【００５２】
【数４】
0006017005.tif 000005
【００５３】
また、式（９）における変数ａ、ｂ、ｅ、ｆは、座標Ｑ1（ｘ1'，ｙ1'）、Ｓ1（ｘ1，ｙ1）及びＱ2（ｘ2'，ｙ2'）、Ｓ2（ｘ2，ｙ2）の座標値を用いて以下の式（１０）〜式（１３）で表すことができる。
【００５４】
【数５】
0006017005.tif 000006
【００５５】
次に、ステップＳ５０９において、ステップＳ５０７で最短距離対応点リストからランダムに抽出された２組の点以外の点を選択するために、対応点選択変数ｋを３に初期化する。そして、ステップＳ５１０において、対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていないか否かを判定する。この判定の結果、組数ｍを超えている場合はステップＳ５１６へ進む。ステップＳ５１６の処理については後述する。
【００５６】
一方、ステップＳ５１０の判定の結果、組数ｍを超えていない場合は、ステップＳ５１１において、最小距離対応点リストから新たな対応点の組を１組抽出する。ここでは、抽出した座標をＳk（ｘk，ｙk）、Ｑk（ｘk'，ｙk'）と定義する。なお、抽出する際にはステップＳ５０７と同様に付加情報を利用する。
【００５７】
次に、ステップＳ５１２において、式（９）によりＳk（ｘk，ｙk）を変換して座標Ｓk'（ｘk"，ｙk"）を求める。その後、ステップＳ５１３において、座標Ｓk'（ｘk"，ｙk"）と座標Ｑk（ｘk'，ｙk'）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離が閾値Ｔｄ以下であるか否かを判定する。この判定の結果、当該ユークリッド距離が閾値Ｔｄ以下の場合はステップＳ５１４へ進み、投票数Ｖｏｔｅをインクリメントした後、ステップＳ５１５へ進む。一方、ステップＳ５１３の判定の結果、当該ユークリッド距離が閾値Ｔｄより大きい場合は、何もせずにステップＳ５１５へ進む。
【００５８】
次に、ステップＳ５１５において、対応点選択変数ｋをインクリメントし、ステップＳ５１０に戻り、対応点選択変数ｋが最短距離対応点リストに登録されている対応点の組数ｍを超えるまで、上述の処理を繰り返す。
【００５９】
次に、ステップＳ５１０で、対応点選択変数ｋが当該対応点リストに登録されている対応点の組数ｍを超えた場合について説明する。ステップＳ５１６においては、投票数Ｖｏｔｅの値と最終投票数ＶｏｔｅＭａｘの値とを比較し、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値よりも大きいか否かを判定する。この判定の結果、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値より大きい場合にはステップＳ５１７へ進む。
【００６０】
ステップＳ５１７においては、最終投票数ＶｏｔｅＭａｘの値を投票数Ｖｏｔｅの値で置き換えるとともに、その時の変換行列Ｍを変数Ｍmaxで置き換える。このように類似度の算出過程で得られる変換行列Ｍの変数Ｍmaxから回転角度が決定される。そして、ステップＳ５１８において反復カウント数Ｃｏｕｎｔをインクリメントし、ステップＳ５０５に戻る。一方、ステップＳ５１６の判定の結果、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値以下の場合にはステップＳ５１８へ処理を移し、反復カウント数Ｃｏｕｎｔをインクリメントして、ステップＳ５０５に処理を戻す。
【００６１】
なお、図５の説明では、相似変換だけを考慮して説明したが、アフィン変換などその他の幾何学変換についても、ステップＳ５０８でそれぞれに応じた変換行列を求めることにより、対応可能である。例えば、アフィン変換の場合には、まずステップＳ５０７で、ランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ５０８で、式（９）ではなく式（８）を用い、ステップＳ５０７で選択した３組の対応点（合計６点）を用いて変数ａ〜ｆを求めればよい。
【００６２】
また、図５の説明では、ステップＳ５１９で類似度として最終投票数ＶｏｔｅＭａｘを出力する例について説明したが、他の類似度を計算するようにしてもよい。例えば、ステップＳ５０４以降の処理を行わずに、ステップＳ５０２で作成された最小距離対応点リストに登録された対応点の組数ｍを類似度として出力する方法がある。
【００６３】
また、本実施形態では、局所特徴量として非特許文献４に記載されている方法を用い、局所特徴点及び局所特徴量の比較に基づいて画像を照合する方法として非特許文献５に記載されているＲＡＮＳＡＣを利用した方法を説明した。しかしながら、２つの画像間の類似度が算出でき、類似度算出の過程において処理負荷の低い方法の回転角度算出方法であれば、他の方法を利用してもよい。
【００６４】
例えば、局所特徴量として非特許文献２に記載されているものを採用する場合には、局所特徴量ごとに局所領域の方向を正規化するための値（ここでは「主方向」と呼ぶ）が得られる。この場合、ステップＳ４０３では、ステップＳ５０２と同様に最小距離対応点リストを作成する時に対応点の主方向の差を計算し、その後その主方向の差に簡単な統計分析を施すことにより処理の負荷を高めることなく回転角度を推定することができる。
【００６５】
なお、統計分析の方法としては、例えばヒストグラムのピーク検出や平均値算出などがある。この場合の類似度算出方法としては、例えば最小距離対応点リストに登録された対応点の組数ｍを類似度とする方法がある。もちろん前述のＲＡＮＳＡＣを利用した方法を用いてもよい。
【００６６】
このように本実施形態では、検索結果として画像を表示する際に、クエリ画像を基準にしてサンプル画像を回転正規化した後に表示するように構成した。これにより、検索結果を確認する時に心的回転によるユーザの負荷を軽減することが可能になる。また、検索に必要な局所特徴量の算出の過程で回転角度が算出されるので、計算量が大幅に増加しないようにしてクエリ画像を基準とした回転正規化が可能になる。
【００６７】
さらに、推定された回転角度が所定の値を超えるか否かによって回転正規化の要否を判定するようにしたので、機器のリソースに応じて動的に判定基準を調整し、機器の処理速度とユーザの心的回転による負荷の軽減度とのバランスを取ることが容易になる。
【００６８】
また、本実施形態では、ステップＳ４０８において、類似度順にソートされ必要に応じて回転正規化処理が施された比較先画像列を比較結果として出力するように構成した。一方、比較先画像列におけるクエリ画像に対応する領域だけを出力するように構成してもよい。あるいは、回転正規化前の比較先画像列を合わせて出力するように構成してもよい。このとき、例えば、回転正規化画像をサブウインドウに表示するようにする。
【００６９】
（第２の実施形態）
第１の実施形態では、ステップＳ４０７において回転正規化処理を実施するように構成したが、ユーザの心的回転を伴う知覚時間の軽減を実現できるなら他のタイミングで回転正規化を施すように構成してもよい。本実施形態では、異なるタイミングで回転正規化を施す例について説明する。以下、このような場合の構成例について図６及び図７を参照しながら説明する。なお、本実施形態における画像検索装置の構成については図１と同様であるため、説明は省略する。本実施形態では、第１の実施形態と異なる点についてのみ説明する。
【００７０】
図６は、本実施形態において、局所特徴点／局所特徴量比較部１０７により検索結果を出力する処理手順の一例を示すフローチャートである。なお、本実施形態では、図４のステップＳ４０１〜Ｓ４０５までの処理は第１の実施形態と同様であるため、説明は省略する。本実施形態では、回転正規化の要否判定とサンプル画像の回転正規化とを行わない。
ステップＳ６０１においては、回転正規化されていない比較結果１０８を出力する。本実施形態では、ユーザの指示に応じて回転正規化の要否判定とサンプル画像の回転正規化とを行う。
【００７１】
次に、比較結果１０８を表示するＧＵＩ上でユーザによるクリック動作が行われた場合を例に説明する。以下、ユーザがクリックした画像をクリック画像と呼ぶことにする。
【００７２】
図７は、局所特徴点／局所特徴量比較部１０７による、表示結果がクリックされた時の回転正規化の処理手順の一例を示すフローチャートである。
まず、操作部１０９からクリック動作による入力を受け付けると処理を開始し、ステップＳ７０１において、クエリ画像に対するサンプル画像の回転正規化が必要か否かを判定する。この判定の結果、回転正規化が必要である場合はステップＳ７０２に進み、回転正規化が不要である場合はステップＳ７０３に進む。
【００７３】
ここで、回転正規化の判定基準としては第１の実施形態と同様の判定基準を用いることにする。すなわち、推定回転角度が±６０°以上の場合に回転正規化が必要であると判定する。ただし、判定基準についても、合理的な基準であれば、本実施形態の基準以外の判定基準を採用してもよい。
【００７４】
ステップＳ７０２においては、ステップＳ４０３で推定した回転角度を用いて、クエリ画像を基準にした回転正規化処理をサンプル画像に施す。そして、ステップＳ７０３においては、必要に応じて回転正規化処理が施されたサンプル画像（クリック画像）を比較結果として出力する。
【００７５】
以上のように本実施形態によれば、ユーザのクリック動作をトリガにしてクエリ画像を基準に回転正規化したサンプル画像を表示するようにした。これにより、検索結果を確認する時に、ユーザの指示により心的回転によるユーザの負荷を軽減することが可能になる。また、検索に必要な局所特徴量の算出の過程で回転か独活が算出されるので、計算量が大幅に増加しないようにしてクエリ画像を基準とした回転正規化が可能になる。
【００７６】
さらに、推定した回転角度に基づいて回転正規化の要否を判定できるように構成したので、機器のリソースに応じて判定基準を調整し、機器の処理速度とユーザの心的回転による負荷の軽減度とのバランスを取ることが容易になる。
【００７７】
なお、クリックの方法としては、例えばマウスの右ボタンクリック時に前記回転正規化処理を実行し、マウスの左ボタンクリック時には通常用いられる拡大・原寸表示を行うように構成してもよい。
【００７８】
また、本実施形態では、ユーザの指示動作としてクリック動作を例に説明したが、ユーザの動作指示に応じて回転正規化の要否判定とサンプル画像の回転正規化とを行うのであれば、他の指示動作を採用してもよい。例えば、指示動作として画像名を入力する方法を用いてもよい。あるいは、既存の視線検出を用い、ユーザが視線を一定時間当てた画像に対して回転正規化処理を実行するように構成してもよい。
【００７９】
（第３の実施形態）
前述の第１及び第２の実施形態では、クエリ画像を基準にしたサンプル画像の回転角度に基づいて、表示するサンプル画像の回転正規化の要否を判定するように構成した。本実施形態では、回転正規化の要否の判定時に、クエリ画像を基準にしたサンプル画像の推定解像度の差を解像度情報として判定基準に用いる例について説明する。すなわち、本実施形態では、図３のスケール番号３０４に着目することにより比較対象画像間の解像度の差を推定する。以下、その具体的な推定方法について説明する。なお、本実施形態における画像検索装置の構成については図１と同様であるため、説明は省略する。本実施形態では、第１の実施形態と異なる点についてのみ説明する。
【００８０】
前述した手順では、まず、ステップＳ５０２で、局所特徴量Ｖqと局所特徴量Ｖsとの全ての組み合わせについて局所特徴量間の距離を計算する。次に、計算した局所特徴量間の距離が閾値Ｔｖ以下となり、かつ、最小距離となるような局所特徴量Ｖqと局所特徴量Ｖsとの組み合わせ（対応点）を抽出し、これらの対応点を登録することにより最小距離対応点リストを作成する。
【００８１】
ここで、局所特徴量間の距離が閾値Ｔｖ以下となり、かつ、最小距離となるような局所特徴量Ｖqと局所特徴量Ｖsとの組み合わせ（対応点）があった場合に、それぞれのスケール番号をＳq、Ｓsとする。また、局所特徴量Ｖqが属する画像をクエリ画像とした場合に、局所特徴量Ｖsが属する画像の類似度を算出する場合を想定する。
【００８２】
解像度の差をΔＳ＝Ｓs−Ｓqとしたとき、局所特徴量Ｖqと局所特徴量Ｖsが正しい対応点（正対応点）である場合には、解像度の差ΔＳは一定値となる。一方、対応が誤っている点（誤対応点）の解像度の差ΔＳは正対応点の解像度の差ΔＳと一致しないことが多い。つまり、局所特徴量間の距離で抽出した対応点すべてに対して解像度の差ΔＳを算出し、解像度の差ΔＳの最頻値ΔＳmodを求めることにより、最頻値ΔＳmodを持つ対応点を正対応点と推定できる。
【００８３】
また、最頻値ΔＳmodは比較画像間の解像度差を表わし、ΔＳmod＞０の場合は局所特徴点Ｖsが属する画像の解像度の方が大きいことを示す。ΔＳmod＝０の場合は比較画像間に解像度の差がなく、ΔＳmod＜０の場合は、局所特徴点Ｖsが属する画像の解像度の方が小さいことを示す。
【００８４】
本実施形態では、回転正規化の要否判定に解像度の差を用いる。ここで、回転正規化の判定基準としてはいろいろな基準が考えられるが、本実施形態では解像度の差の最頻値ΔＳmod≧４の場合に回転正規化が不要と判定する。すなわち、サンプル画像のクエリ画像に対する解像度比が４倍以上ある場合には回転正規化しない。ただし、判定基準は合理的な基準であれば、本実施形態の基準以外の基準を採用してもよい。また、第１及び第２の実施形態で説明した回転角度等を用いた回転正規化判定基準と組み合わせてもよい。判定の組み合わせ方法は論理積を用いてもよいし論理和を用いてもよい。
【００８５】
さらに、回転角度に応じて解像度の差を判定基準に用いるか否かを決定してもよい。例えば、回転角度が±３０°以内の場合にだけ解像度の差を判定基準に加え、それ以外の場合には解像度の差を判定基準に加えないように構成する。この場合、回転角度が±３０°以内であって、解像度の差の最頻値ΔＳmod≧４である場合には回転正規化を行わないようにする。一方で、回転角度が±３０°より大きいときには、サンプル画像のクエリ画像に対する解像度の差に関わらず必ず回転正規化を行うようにする。
【００８６】
以上のように本実施形態によれば、回転正規化要否の判定時にクエリ画像を基準にしたサンプル画像の解像度の差が所定値よりも小さいか否かという判定基準に用いるように構成した。これにより、機器のリソースに応じて判定基準を調整し、機器の処理速度とユーザの心的回転による負荷の軽減度とのバランスを取ることが容易になる。
【００８７】
（第４の実施形態）
第１の実施形態では、検索結果の画像を表示する際に、クエリ画像を基準に回転正規化した画像で表示するように構成した。一方、ユーザの心的回転を伴う知覚時間の軽減を実現できる場合には検索結果の画像を回転正規化する方法以外の方法を用いてもよい。
【００８８】
本実施形態では、クエリ画像と検索結果の画像との対応領域が画像の中でどのように存在するかを補助画像で明示すること、特に回転方向を明示することによりユーザの心的回転を伴う知覚時間を軽減する方法を説明する。なお、本実施形態における画像検索装置の構成については図１と同様であるため、説明は省略する。本実施形態では、第１の実施形態と異なる点についてのみ説明する。また、本実施形態では、補助画像として矩形を用いる場合について説明する。
【００８９】
図８は、本実施形態において、局所特徴点／局所特徴量比較部１０７により検索結果を出力する処理手順の一例を示すフローチャートである。図４と異なる点は、ステップＳ４０３の処理の代わりにステップＳ８０１の処理を行い、ステップＳ４０６及びＳ４０７の処理の代わりにステップＳ８０２の処理を行う点である。それ以外の処理については図４と同様である。
【００９０】
ステップＳ８０１においては、クエリ画像入力部１０２に入力されたクエリ画像１０１と比較先画像列１０４のサンプル画像との類似度を算出する。このとき、類似度の算出の過程で生成される値を用いて、サンプル画像とクエリ画像との対応領域に対する変形パラメータを推定する。なお、このステップＳ８０１の処理の詳細については後述する。また、クエリ画像との対応領域情報と変形パラメータについては、該当するサンプル画像と紐付けておく。
【００９１】
ステップＳ８０２においては、サンプル画像上にクエリ画像の対応する領域を矩形で描画する。描画にはステップＳ８０１の処理で得られるクエリ画像との対応領域情報及び変形パラメータを用いる。なお、本実施形態では、クエリ画像との対応領域情報をステップＳ５１３の条件を満たす対応点の組とする。また、前記矩形は、クエリ画像上で対応点をすべて含む最外接矩形を生成し、その最外接矩形を変形パラメータによりサンプル画像上に写像したものとする。
【００９２】
ここで、前記矩形のデザインとしてクエリ画像上で生成する矩形底辺の色を他の辺の色とは異なる色に設定し、その後その矩形を写像することとする。これにより、前記矩形の上下左右方向を認識しやすくする。
【００９３】
次に、ステップＳ８０１の処理の詳細について説明する。
図９は、ステップＳ８０１の詳細な処理であって、局所特徴点／局所特徴量比較部１０７により類似度及び変形パラメータを算出する処理手順の一例を示すフローチャートである。図５と異なる点は、ステップＳ５１７の代わりにステップＳ９０１の処理が行われ、ステップＳ５１９の代わりにステップＳ９０２の処理が行われる点である。それ以外の処理については、図５と同様である。
【００９４】
ステップＳ９０１では、最終投票数ＶｏｔｅＭａｘの値を投票数Ｖｏｔｅの値で置き換えるとともに、変数Ｍmax、Ｔmaxを、その時の変換行列Ｍ、Ｔに置き換える。また、ステップＳ９０２では、クエリ画像との対応領域情報、最終投票数ＶｏｔｅＭａｘ、及びその時の変形パラメータとして変換行列Ｍmax、Ｔmaxを設定する。
【００９５】
このように本実施形態では、検索結果として画像を表示する際に、サンプル画像上にクエリ画像の対応する領域を矩形で描画するように構成した。これにより、ユーザは矩形の上下左右方向を認識しやすくなり、検索結果を確認する時に心的回転によるユーザの負荷を軽減することが可能になる。
【００９６】
なお、本実施形態では、矩形底辺の色を他の辺の色とは異なる色に設定するようにしたが、ユーザによる矩形の上下左右方向の認識を容易にする方法であれば、上記の方法に限らず他の方法を用いてもよい。例えば、矩形の上下左右すべての辺の色を異なる色に設定するようにしてもよい。あるいは、色を変更するのではなく、異なる線幅や線種を用いるようにしてもよい。
【００９７】
また、矩形の辺のデザインを変化させるのではなく、矩形を描画した上で変形パラメータをテキスト表示するようにしてもよい。さらに、変形度合いに応じてテキストの色や線幅、フォントを変更するようにしてもよい。これにより、ユーザはクエリ画像に対するサンプル画像の変形度合いを認識しやすくなり、検索結果を確認する時に心的回転を補助することが可能になる。そのため、ユーザの負荷を軽減することが可能になる。
【００９８】
また、本実施形態では、検索結果を表示する際にサンプル画像上にクエリ画像の対応する領域を矩形で描画するようにしたが、サンプル画像上でのクエリ画像に対応する領域を容易に確認できれば他の補助画像を用いて描画するように構成してもよい。例えば、矩形ではなく、クエリ画像上での対応点をすべて含むような円あるいは楕円としてよく、任意の多角形としてもよい。さらには、矢印を用いてもよい。ただし、その場合は、前述の上下左右方向の認識を容易にする方法を適用するために、補助画像では、上下左右を表す範囲を設定する必要がある。さらに、クエリ画像上においても、対応する領域をサンプル画像上の補助画像と同じあるいは近いデザインの補助画像で示すようにしてもよい。
【００９９】
（その他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【０１００】
１０３  第１の局所特徴点／局所特徴量抽出部
１０６  第２の局所特徴点／局所特徴量抽出部
１０７  局所特徴点／局所特徴量比較部
【図１】
0006017005.tif 000007
【図２】
0006017005.tif 000008
【図３】
0006017005.tif 000009
【図４】
0006017005.tif 000010
【図５】
0006017005.tif 000011
【図６】
0006017005.tif 000012
【図７】
0006017005.tif 000013
【図８】
0006017005.tif 000014
【図９】
0006017005.tif 000015