(57)【要約】      （修正有）【課題】ユーザにとってフレンドリーな検索結果を適切に出力できるようにする。【解決手段】ＧＰＳ情報を用いた検索処理により集合Ａを作成し、アノテーションの検索処理により集合Ｂを作成する。集合Ａの画像から部分画像検索を行い、集合Ｄを作成する。集合Ｂと集合Ｄとを合わせた集合Ｅを類似度順に並べ、検索結果を表示する。このとき、集合Ｂの画像については、縮小したサムネール画像を天地判定により９０°単位で回転して表示し、集合Ｄの画像については、特徴量に基づいて算出された領域情報及び回転角度に従って部分画像を切り出し、拡大又は縮小を行ってサムネール画像を表示する。【選択図】図６
2013161294.tif 000002
【特許請求の範囲】
【請求項１】
クエリ画像と関連する属性情報を保持する第１の比較先画像を検索する第１の検索手段と、
前記クエリ画像と撮影情報が関連する第２の比較先画像を検索する第２の検索手段と、
前記第１の検索手段によって検索された第１の比較先画像の属性情報の類似度を算出するとともに、前記第２の検索手段によって検索された第２の比較先画像の特徴量を抽出し、前記抽出した特徴量から前記第２の比較先画像の類似度、類似する領域及び回転角度を算出して第３の比較先画像を検索する算出手段と、
前記第１の比較先画像に係る代表画像を生成するとともに、前記算出手段によって算出された類似する領域及び回転角度に基づいて、前記第３の比較先画像のうち、前記クエリ画像と関連する領域に係る代表画像を生成する生成手段と、
前記算出手段によって算出された類似度に従って、前記生成手段によって生成された代表画像を検索結果として出力する出力手段とを有し、
前記生成手段は、前記第１の比較先画像に係る代表画像と前記第３の比較先画像に係る代表画像とで代表画像の生成方法を異なるようにすることを特徴とする画像検索装置。
【請求項２】
前記生成手段は、前記第１の比較先画像に係る代表画像を、天地判定に基づいて回転させて生成することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記生成手段は、前記第１の比較先画像を縮小して代表画像を生成することを特徴とする請求項１又は２に記載の画像検索装置。
【請求項４】
前記生成手段は、前記第３の比較先画像の中から前記類似する領域を抽出し、前記抽出した領域を前記回転角度により回転させて代表画像を生成することを特徴とする請求項１〜３の何れか１項に記載の画像検索装置。
【請求項５】
前記属性情報はアノテーションであり、前記第１の検索手段は、前記アノテーションの表記ゆれ及び同義語を含めて前記第１の比較先画像を検索することを特徴とする請求項１〜４の何れか１項に記載の画像検索装置。
【請求項６】
前記第２の検索手段は、前記撮影情報のＧＰＳ情報に基づいて、前記クエリ画像の座標から所定の範囲内である画像を前記第２の比較先画像として検索することを特徴とする請求項１〜５の何れか１項に記載の画像検索装置。
【請求項７】
前記第１の比較先画像及び第３の比較先画像で重複する画像が存在する場合は、前記生成手段は、前記第１の比較先画像及び第３の比較先画像のそれぞれから得られた情報を統合して前記第３の比較先画像として取り扱うことを特徴とする請求項１〜６の何れか１項に記載の画像検索装置。
【請求項８】
前記出力手段は、前記検索結果を表示装置に出力することを特徴とする請求項１〜７の何れか１項に記載の画像検索装置。
【請求項９】
前記出力手段は、前記検索結果を印刷装置に出力することを特徴とする請求項１〜７の何れか１項に記載の画像検索装置。
【請求項１０】
クエリ画像と関連する属性情報を保持する第１の比較先画像を検索する第１の検索工程と、
前記クエリ画像と撮影情報が関連する第２の比較先画像を検索する第２の検索工程と、
前記第１の検索工程において検索された第１の比較先画像の属性情報の類似度を算出するとともに、前記第２の検索工程において検索された第２の比較先画像の特徴量を抽出し、前記抽出した特徴量から前記第２の比較先画像の類似度、類似する領域及び回転角度を算出して第３の比較先画像を検索する算出工程と、
前記第１の比較先画像に係る代表画像を生成するとともに、前記算出工程において算出された類似する領域及び回転角度に基づいて、前記第３の比較先画像のうち、前記クエリ画像と関連する領域に係る代表画像を生成する生成工程と、
前記算出工程において算出された類似度に従って、前記生成工程において生成された代表画像を検索結果として出力する出力工程とを有し、
前記生成工程においては、前記第１の比較先画像に係る代表画像と前記第３の比較先画像に係る代表画像とで代表画像の生成方法を異なるようにすることを特徴とする画像検索方法。
【請求項１１】
クエリ画像と関連する属性情報を保持する第１の比較先画像を検索する第１の検索工程と、
前記クエリ画像と撮影情報が関連する第２の比較先画像を検索する第２の検索工程と、
前記第１の検索工程において検索された第１の比較先画像の属性情報の類似度を算出するとともに、前記第２の検索工程において検索された第２の比較先画像の特徴量を抽出し、前記抽出した特徴量から前記第２の比較先画像の類似度、類似する領域及び回転角度を算出して第３の比較先画像を検索する算出工程と、
前記第１の比較先画像に係る代表画像を生成するとともに、前記算出工程において算出された類似する領域及び回転角度に基づいて、前記第３の比較先画像のうち、前記クエリ画像と関連する領域に係る代表画像を生成する生成工程と、
前記算出工程において算出された類似度に従って、前記生成工程において生成された代表画像を検索結果として出力する出力工程とをコンピュータに実行させ、
前記生成工程においては、前記第１の比較先画像に係る代表画像と前記第３の比較先画像に係る代表画像とで代表画像の生成方法を異なるようにすることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に、検索結果を適切に出力するために用いて好適な画像検索装置、画像検索方法及びプログラムに関する。
【背景技術】
【０００２】
従来、画像検索結果を表示する際には、縮小して作成したサムネール画像を表示することが一般的である。例えば、特許文献１には、画像を複数の領域に分割し、分割された領域毎に属性情報を付与することにより、検索対象物を表す属性情報を含む領域のみを検索し、所望する画像の一部分を高速に取り出す技術が開示されている。この技術では、画像をタイル分割し、タイルごとに、属性情報／画像特徴量を記述し、ヒットする部分のタイルのみをタイル単位でサムネール化して検索結果を表示する。
【０００３】
さらに、特許文献２に記載の技術では、指定された画像の特徴に基づいて、部分画像の特徴を検索し、検索結果に基づいて得られた部分画像に対応付けられた画像を候補画像として決定する。そして、検索結果表示部は、決定された候補画像に含まれる部分画像を所定の大きさに拡大して候補画像の縮小画像を表示する。この技術についても、ヒットした領域を効果的に表示することが可能である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−５３３７２号公報
【特許文献２】特開２００４−２４０７５０号公報
【非特許文献】
【０００５】
【非特許文献１】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.
【非特許文献２】C.Harris and M.J. Stephens,"A combined corner and edge detector," In Alvey Vision Conference,pages 147-152, 1988.
【非特許文献３】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.
【非特許文献５】David G. Lowe, "Distinctive Image Features from Scale-Invariant Keypoints," International Journal of Computer Vision, 60, 2 (2004), pp.91-110.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところが、検索結果の中には、回転角度が異なるものが存在する場合がある。心理学の実験では、回転しているオブジェクトが同一であることを知覚する際、頭の中で回転したイメージを作ってからマッチングしているという定説がある。これを心的回転と呼ぶ。心的回転を伴う知覚時間は対象オブジェクトの回転角度におおよそ比例し、１８０度回転の場合には、回転なし場合に比べ約２倍の時間を要することが記載されている（例えば、非特許文献１参照）。
【０００７】
検索結果として表示される多数の画像を確認するとき、この心的回転を伴う知覚時間の増加を無視することはできない。この様に、知覚対象オブジェクト（検索結果）が回転している場合に、オブジェクトをそのまま表示するあるいは矩形で囲むだけでは検索結果の提示に際し、心的回転など、検索結果の確認時にユーザの負担を考慮した処理とはいえない。また、撮影した角度が異なるなどによって検索漏れを起こす場合もあり、ユーザにとって十分にフレンドリーな検索結果が表示されているとはいえない。
【０００８】
本発明は前述の問題点に鑑み、ユーザにとってフレンドリーな検索結果を適切に出力できるようにすることを目的としている。
【課題を解決するための手段】
【０００９】
本発明の画像検索装置は、クエリ画像と関連する属性情報を保持する第１の比較先画像を検索する検索手段と、前記検索手段によって検索された第１の比較先画像の属性情報の類似度を算出するとともに、前記クエリ画像と撮影情報が関連する第２の比較先画像を検索して特徴量を抽出し、前記クエリ画像との類似度、類似する領域及び回転角度を算出して第３の比較先画像を検索する算出手段と、前記第１の比較先画像に係る代表画像を生成するとともに、前記算出手段によって算出された類似する領域及び回転角度に基づいて、前記第３の比較先画像のうち、前記クエリ画像と関連する領域に係る代表画像を生成する生成手段と、前記算出手段によって算出された類似度に従って、前記生成手段によって生成された代表画像を出力する出力手段とを有し、前記生成手段は、前記第１の比較先画像に係る代表画像と前記第３の比較先画像に係る代表画像とで代表画像の生成方法を異なるようにすることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、ユーザにとってフレンドリーな検索結果を適切に出力させることができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態に係る画像検索装置のハードウェア構成例を示すブロック図である。
【図２】本発明の実施形態における画像検索装置の機能構成例を示すブロック図である。
【図３】実施形態において、画像の局所特徴点及び局所特徴量を抽出する処理手順の一例を示すフローチャートである。
【図４】図３のステップＳ３０４における縮小画像の生成処理の概要を説明する図である。
【図５】局所特徴点／局所特徴量比較部により類似度、回転角度及びヒットした領域を算出する処理手順の一例を示すフローチャートである。
【図６】実施形態において、検索部により画像を検索して検索結果を表示する処理手順の一例を示すフローチャートである。
【図７】クエリ画像の一例を示す図である。
【図８】検索によりヒットした比較先画像の一例を示す図である。
【図９】回転方向が反映されていない検索結果の表示例を示す図である。
【図１０】本発明の実施形態に係る検索結果の表示例を示す図である。
【発明を実施するための形態】
【００１２】
（第１の実施形態）
以下、本発明の実施形態について、図面を参照しながら説明する。
図１は、本実施形態に係る画像検索装置１００のハードウェア構成例を示すブロック図である。
図１に示す画像検索装置１００は、ＣＰＵ１０１、入力装置１０２、出力装置１０３、記憶装置１０４、ＲＡＭ１０５、ＲＯＭ１０６、及びＢＵＳ１０７を備えている。
【００１３】
ＣＰＵ１０１は、各種データ処理のための論理演算、判断等を行い、ＢＵＳ１０７に接続されている各構成要素の制御を行う。入力装置１０２には、アルファベットキー、ひらがなキー、カタカナキー、句点等の文字記号入力キー、カーソル移動を指示するカーソル移動キー等のような、各種の機能キーを備えた不図示のキーボードが接続されている。また、画像の局所特徴量を算出する画像を入力するカメラ等の撮像素子、もしくは撮像素子によって記録した画像を保持し入力するためのＨＤＤ等のストレージも接続することができる。さらに、ＧＵＩ（Graphical User Interface）上で画面の制御可能位置を指し示し、機能の選択指示などを行うポインティング機器、例えばマウスやスティックポインタ等を接続することもできる。
【００１４】
出力装置１０３は、液晶パネル等の各種表示装置である。記憶装置１０４には、入出力データや処理プログラム等、各種情報が格納される。これらのデータ及びプログラムを格納する記憶媒体としては、ハードディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、フラッシュメモリ等を用いることができる。ＲＡＭ１０５は、各構成要素からの各種データを一時的に記憶する際に用いられる。ＲＯＭ１０６は、本実施形態で実行される処理プログラム等の制御プログラムを記憶する。これら全ての構成要素はＢＵＳ１０７で接続されている。
【００１５】
図２は、本実施形態における画像検索装置１００の機能構成例を示すブロック図である。
図２において、画像検索装置１００は、クエリ画像入力部２０２、比較先画像入力部２０５、第１の局所特徴点／局所特徴量抽出部２０３、第２の局所特徴点／局所特徴量抽出部２０６、及び局所特徴点／局所特徴量比較部２０７を備えている。さらに、比較結果２０８から表示装置２１０に表示する画像を生成する検索部２０９を備えている。
【００１６】
画像検索装置１００では、入力画像であるクエリ画像２０１がクエリ画像入力部２０２に入力されると、第１の局所特徴点／局所特徴量抽出部２０３は、クエリ画像２０１から局所特徴として局所特徴点とその局所特徴量とを抽出する。同様に、比較対象となる比較先画像列２０４が比較先画像入力部２０５に入力されると、第２の局所特徴点／局所特徴量抽出部２０６は、比較先画像列２０４から局所特徴として局所特徴点とその局所特徴量とを抽出する。なお、局所特徴点とその局所特徴量とを抽出する処理の詳細については後述する。また、クエリ画像２０１及び比較先画像列２０４は不図示の画像ＤＢに格納されており、画像ＤＢからクエリ画像２０１及び比較先画像列２０４が入力される。また、詳細は後述するが、比較先画像列２０４は、クエリ画像のＧＰＳ情報に基づいて検索してヒットした画像群である。
【００１７】
局所特徴点／局所特徴量比較部２０７は、第１の局所特徴点／局所特徴量抽出部２０３及び第２の局所特徴点／局所特徴量抽出部２０６で抽出されたそれぞれの局所特徴点及び局所特徴量同士を比較する。そして、比較結果２０８を検索部２０９に出力する。この局所特徴点及び局所特徴量の比較処理の詳細についても後述する。
【００１８】
検索部２０９は、撮影場所のＧＰＳ情報、画像に付与されたアノテーション、及び部分画像検索の結果を用いて、出力装置１０３に相当する表示装置２１０に表示するための検索結果を算出する。そして、検索部２０９は、検索結果の代表画像としてサムネール画像を生成し、表示装置２１０に表示する。また、検索部２０９は、検索結果として表示させる画像に対し、天地判定などのシーン認識を行い、適切な角度に画像を回転させることができる。
【００１９】
次に、画像の局所特徴量やメタデータを用いた検索式により検索を行い、認知しやすい検索結果となる画像を生成して表示する例について説明する。
【００２０】
クエリ画像２０１及び比較先画像列２０４は、撮影情報として撮影場所を示すＧＰＳ情報、及びユーザの指示により入力された撮影物のアノテーションが一部付与された状態で不図示の画像ＤＢに格納されている。後述する部分画像検索では、画像ＤＢに格納されているクエリ画像２０１及び比較先画像列２０４から局所特徴点を求め、局所特徴点に対して回転や拡大縮小に対してロバストな局所特徴量を求める。そして、これらをマッチングすることにより部分位置の画像検索を実現する。
【００２１】
部分画像検索では、局所特徴量と、類似度と、クエリ画像と部分一致する領域を示す座標値ＭｉｎＸ、ＭａｘＸ、ＭｉｎＹ、ＭａｘＹと、その一致する領域のクエリ画像の合致領域に対する回転角度とが算出される。そして、これらの情報を用いて部分画像の検索を行う。
【００２２】
以下の説明では、「ランドマークＡ」という画像を検索する場合に、画像ＤＢに格納された「ランドマークＡ」の画像に属性情報としてアノテーション「ランドマークＡ」が付与されているものとそうでないものとが混在したケースを想定する。そして、「ランドマークＡ」の画像をなるべく漏れが少なくなるように検索する例について説明する。また、ＧＰＳ情報は全ての画像に付与されているものとする。
【００２３】
［部分画像の検索処理］
まず、部分画像検索の一部として、図２におけるクエリ画像入力部２０２、比較先画像入力部２０５、第１の局所特徴点／局所特徴量抽出部２０３及び第２の局所特徴点／局所特徴量抽出部２０６の処理を説明する。画像からの局所特徴抽出処理は、画像データを読み出すステップ、輝度成分の抽出ステップ、縮小画像の作成ステップ、局所特徴点の抽出ステップ、及び局所特徴量の算出ステップからなる。
【００２４】
図３は、本実施形態において、画像の局所特徴点及び局所特徴量を抽出する処理手順の一例を示すフローチャートである。
まず、ステップＳ３０１により処理を開始し、ステップＳ３０２において、クエリ画像入力部２０２及び比較先画像入力部２０５は、それぞれの画像データを読み出す。そして、ステップＳ３０３において、第１の局所特徴点／局所特徴量抽出部２０３及び第２の局所特徴点／局所特徴量抽出部２０６はそれぞれ、画像データから輝度成分を抽出し、輝度成分画像を生成する。
【００２５】
次に、ステップＳ３０４において、第１の局所特徴点／局所特徴量抽出部２０３及び第２の局所特徴点／局所特徴量抽出部２０６はそれぞれ、ステップＳ３０３で作成した当該輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成する。ただし、倍率ｐ及び縮小画像の枚数ｎは予め決められているものとする。
【００２６】
図４は、図３のステップＳ３０４における縮小画像の生成処理の概要を説明する図である。なお、図４では、倍率ｐを２の−（１／４）乗とし、縮小画像の枚数ｎを９とした場合の例を示している。また、図４に示す例では、倍率ｐを面積比ではなく辺の長さの比としている。
【００２７】
図４において、４０１はステップＳ２０３で作成した輝度成分画像である。４０２は輝度成分画像４０１から倍率ｐに従って４回縮小された縮小画像であり、輝度成分画像４０１を１／２に縮小した画像に相当する。また、４０３は輝度成分画像４０１から倍率ｐに従って８回縮小された縮小画像であり、輝度成分画像４０１を１／４に縮小した画像に相当する。なお、画像を縮小する方法は単純に画素を間引く方法、線形補間を用いる方法、低域フィルタ適用後にサンプリングする方法などを用いることができるが、何れの方法でもよい。本実施形態では、線形補間による縮小方法を用いて画像を縮小するものとする。
【００２８】
４０４はスケール番号であり、縮小画像のサイズが大きい方から順に解像度に応じて付与される番号である。本実施形態では、スケール番号は１から始まるようにしているが、０から始まるようにしてもよい。
【００２９】
図３の説明に戻り、次に、ステップＳ３０５において、第１の局所特徴点／局所特徴量抽出部２０３及び第２の局所特徴点／局所特徴量抽出部２０６は、ステップＳ３０４で得られたｎ枚の縮小画像のそれぞれから局所的な特徴点（局所特徴点）を抽出する。ここで抽出する局所特徴点は、画像に回転や縮小などの画像処理を施しても同じ場所から安定的に抽出されるようなロバストな局所特徴点である。このような局所特徴点を抽出する方法として、本実施形態では、非特許文献２に記載されているＨａｒｒｉｓ作用素を用いる。
【００３０】
具体的には、Ｈａｒｒｉｓ作用素を作用させて得られた画像の画素それぞれについて、着目画素とその周辺にある８つの画素との合計９画素の画素値を調べる。そして、着目画素の画素値が予め定めた値以上であり、かつ局所極大になる（当該９画素の中で当該画素の画素値が最大になる）場合に、その着目画素が位置する点を局所特徴点として抽出する。なお、ロバストな局所特徴点を抽出可能な方法であれば、上述のＨａｒｒｉｓ作用素による特徴点抽出方法に限らず、どのような特徴点抽出方法でも適用可能である。
【００３１】
次に、ステップＳ３０６において、ステップＳ３０５で得られた局所特徴点それぞれについて、画像の回転があっても不変となるように定義された特徴量（局所特徴量）を算出する。この局所特徴量の算出方法として、本実施形態では非特許文献３に記載されているLocal Jet及びそれらの導関数の組み合わせを用いる。この方法により算出される局所特徴量は、拡大縮小、回転に対して、比較的高い耐性を持つような特性を持たせることができる。具体的には、以下の式（１）により局所特徴量を算出する。
【００３２】
【数１】
2013161294.tif 000003
【００３３】
ただし、式（１）の右辺で用いている記号は、以下の式（２）から式（７）に示すように定義される。
【００３４】
【数２】
2013161294.tif 000004
【００３５】
ここで、式（２）右辺のＧ（ｘ，ｙ）はガウス関数であり、Ｉ（ｘ，ｙ）は画像の座標（ｘ，ｙ）における画素値であり、"＊"は畳み込み演算を表す記号である。また、式（３）は式（２）で定義された変数Ｌのｘに関する偏導関数であり、式（４）は当該変数Ｌのｙに関する偏導関数である。式（５）は式（３）で定義された変数Ｌ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）と定義する。そして、ステップＳ５０８において、変換行列Ｍ、Ｔを計算する。ここで、行列Ｍは、以下の式（８）において変数ａ〜ｄで構成される行列であり、行列Ｔは変数ｅ〜ｆで構成される行列である。
【００４５】
【数３】
2013161294.tif 000005
【００４６】
ここで、以下の説明では、説明を簡略化するため、相似変換だけを考える。この場合には、上記式（８）は以下の式（９）のように書き換えられる。
【００４７】
【数４】
2013161294.tif 000006
【００４８】
また、式（９）における変数ａ、ｂ、ｅ、ｆは、座標Ｑ1（ｘ1'，ｙ1'）、Ｓ1（ｘ1，ｙ1）及びＱ2（ｘ2'，ｙ2'）、Ｓ2（ｘ2，ｙ2）の座標値を用いて以下の式（１０）〜式（１３）で表すことができる。
【００４９】
【数５】
2013161294.tif 000007
【００５０】
次に、ステップＳ５０９において、ステップＳ５０７で最短距離対応点リストからランダムに抽出された２組の点以外の点を選択するために、対応点選択変数ｋを３に初期化する。そして、ステップＳ５１０において、対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていないか否かを判定する。この判定の結果、組数ｍを超えている場合はステップＳ５２０へ進む。ステップＳ５２０の処理については後述する。
【００５１】
一方、ステップＳ５１０の判定の結果、組数ｍを超えていない場合は、ステップＳ５１１において、最小距離対応点リストから新たな対応点の組を１組抽出する。ここでは、抽出した座標をＳk（ｘk，ｙk）、Ｑk（ｘk'，ｙk'）と定義する。なお、抽出する際にはステップＳ５０７と同様に付加情報を利用する。
【００５２】
次に、ステップＳ５１２において、式（９）によりＳk（ｘk，ｙk）を変換して座標Ｓk'（ｘk"，ｙk"）を求める。その後、ステップＳ５１３において、座標Ｓk'（ｘk"，ｙk"）と座標Ｑk（ｘk'，ｙk'）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離が閾値Ｔｄ以下であるか否かを判定する。この判定の結果、当該ユークリッド距離が閾値Ｔｄ以下の場合はステップＳ５１４へ進み、投票数Ｖｏｔｅをインクリメントした後、ステップＳ５１５へ進む。一方、ステップＳ５１３の判定の結果、当該ユークリッド距離が閾値Ｔｄより大きい場合は、何もせずにステップＳ５１９へ進む。
【００５３】
次に、ステップＳ５１５において、座標Ｓk（ｘk，ｙk）が比較先画像のヒット領域の下端であるか否かを判定する。この判定の結果、ヒット領域の下端である場合には、ステップＳ５１６において、下端候補の座標（ＭｉｎＸ，ＭｉｎＹ）を更新する。一方、ステップＳ５１５の判定の結果、比較先画像のヒット領域の下端でない場合は、そのままステップＳ５１７に進む。
【００５４】
次に、ステップＳ５１７において、座標Ｓk（ｘk，ｙk）がヒット領域の上端であるか否かを判定する。この判定の結果、ヒット領域の上端である場合には、ステップＳ５１８において、上端候補の座標（ＭａｘＸ，ＭａｘＹ）を更新し、ステップＳ５１９に進む。一方、ステップＳ５１７の判定の結果、ヒット領域の上端でない場合には、そのままステップＳ５１９に進む。
【００５５】
次に、ステップＳ５１９において、対応点選択変数ｋをインクリメントし、ステップＳ５１０に戻り、対応点選択変数ｋが最短距離対応点リストに登録されている対応点の組数ｍを超えるまで、上述の処理を繰り返す。
【００５６】
次に、ステップＳ５１０で、対応点選択変数ｋが当該対応点リストに登録されている対応点の組数ｍを超えた場合について説明する。ステップＳ５２０においては、投票数Ｖｏｔｅの値と最終投票数ＶｏｔｅＭａｘの値とを比較し、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値よりも大きいか否かを判定する。この判定の結果、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値より大きい場合にはステップＳ５２１へ進む。
【００５７】
ステップＳ５２１においては、最終投票数ＶｏｔｅＭａｘの値を投票数Ｖｏｔｅの値で置き換えるとともに、その時の変換行列Ｍを変数Ｍmaxで置き換える。このように類似度の算出過程で得られる変換行列Ｍの変数Ｍmaxから回転角度が決定される。そして、ステップＳ５２２において反復カウント数Ｃｏｕｎｔをインクリメントし、ステップＳ４０５に戻る。一方、ステップＳ５２０の判定の結果、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値以下の場合にはステップＳ５２２へ処理を移し、反復カウント数Ｃｏｕｎｔをインクリメントして、ステップＳ５０５に処理を戻す。
【００５８】
なお、図５の説明では、相似変換だけを考慮して説明したが、アフィン変換などその他の幾何学変換についても、ステップＳ５０８でそれぞれに応じた変換行列を求めることにより、対応可能である。例えば、アフィン変換の場合には、まずステップＳ５０７で、ランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ５０８で、式（９）ではなく式（８）を用い、ステップＳ５０７で選択した３組の対応点（合計６点）を用いて変数ａ〜ｆを求めればよい。
【００５９】
また、図５の説明では、ステップＳ５２３で類似度として最終投票数ＶｏｔｅＭａｘを出力する例について説明したが、他の類似度を計算するようにしてもよい。例えば、ステップＳ５０４以降の処理を行わずに、ステップＳ５０２で作成された最小距離対応点リストに登録された対応点の組数ｍを類似度として出力する方法がある。
【００６０】
また、本実施形態では、局所特徴量として非特許文献３に記載されている方法を用い、局所特徴点及び局所特徴量の比較に基づいて画像を照合する方法として非特許文献４に記載されているＲＡＮＳＡＣを利用した方法を説明した。しかしながら、２つの画像間の類似度が算出でき、類似度算出の過程において処理負荷の低い方法の回転角度算出方法であれば、他の方法を利用してもよい。
【００６１】
例えば、局所特徴量として非特許文献５に記載されているものを採用する場合には、局所特徴量ごとに局所領域の方向を正規化するための値（ここでは「主方向」と呼ぶ）が得られる。この場合、ステップＳ５０２と同様に最小距離対応点リストを作成する時に対応点の主方向の差を計算し、その後その主方向の差に簡単な統計分析を施すことにより処理の負荷を高めることなく回転角度を推定することができる。
【００６２】
なお、統計分析の方法としては、例えばヒストグラムのピーク検出や平均値算出などがある。この場合の類似度算出方法としては、例えば最小距離対応点リストに登録された対応点の組数ｍを類似度とする方法がある。もちろん前述のＲＡＮＳＡＣを利用した方法を用いてもよい。
【００６３】
［画像検索結果の表示］
次に、検索部２０９による画像検索結果を表示する手順について説明する。画像の検索を行う際には、まず、検索条件を論理式で与える。
図６は、検索部２０９により画像を検索して検索結果を表示する処理手順の一例を示すフローチャートである。
まず、図１の入力装置１０２より検索の指示がなされると処理を開始する。そして、ステップＳ６０１において、検索式を入力する。
【００６４】
画像の検索を行う場合は、「ランドマークＡ」のクエリ画像として、幾つかのアングルで検索したものを用いることが好ましい。例えば、図７（ａ）に示すようなクエリ画像と、アングルの異なる図７（ｂ）に示すようなクエリ画像とを用いて検索することが好ましい。また、部分画像検索で検索から漏れた画像であって、アノテーション「ランドマークＡ」が付与されている画像を第１の検索として論理和で演算し、検索漏れを少なくする。さらに、第２の検索において、ＧＰＳ情報により撮影場所に制約を与え、検索ノイズを削減するために、部分画像の検索条件にＡＮＤ演算する。以上により以下の式（１４）で表現される検索処理を行う。
（ランドマークＡの例示画１の部分画像検索  ＋  ランドマークＡの例示画２の部分画像検索）＊ＧＰＳ情報  ＋  「ランドマークＡ」のアノテーション    ・・・（１４）
【００６５】
本実施形態では、式（１４）に示すような論理式を検索式テンプレートとして用意しておき、局所特徴量、さらにアノテーション「ランドマークＡ」が有る場合にはアノテーションを検索条件にセットする。なお、式（１４）に示した例は、クエリ画像を２種類用意して検索する場合に用いるものであり、クエリ画像を１つもしくは３つ以上用いる場合は、その分の部分画像検索を条件に加える。ステップＳ６０１では、ユーザにより入力装置１０２から入力された検索条件に従って検索式を入力する。以下の説明では、式（１４）に示す検索式が入力されたものとして説明する。
【００６６】
次に、ステップＳ６０２において、クエリ画像２０１に付加されているＧＰＳ情報による検索処理を行う。ＧＰＳ情報を用いた検索処理では、クエリ画像２０１の指定座標から所定の範囲を適合領域として処理すればよい。例えば、指定座標から定められた半径の領域を適合領域として検索する。また、クエリ画像として例示画が複数ある場合は、それぞれについて検索を行う。そして、ステップＳ６０３において、ステップＳ６０２の検索結果を集合Ａとして保持する。
【００６７】
次に、ステップＳ６０４において、アノテーションによる検索処理を行う。クエリ画像２０１にアノテーションが付与されている場合には、そのアノテーションをそのまま用いる。一方、クエリ画像２０１にアノテーションが付与されていない場合には、ユーザによる入力によって検索するアノテーションを決定する。また、検索の際には、単純に関連するキーワードマッチングでもよく、表記ゆれ及び同義語を含めて検索し、キーワードマッチングの結果の論理和を取ってもよい。
【００６８】
次に、ステップＳ２０５において、ステップＳ２０４の検索結果（第１の比較先画像列）を集合Ｂとして保持する。このとき、集合Ｂのそれぞれの画像に対して、例えば、以下のスキーマで検索内部情報を保持する。
画像ＩＤ：１０
類似度：１００％
ヒット領域：０，０，０，０
回転角度：０
結果表示判別フラグ：ＯＦＦ
【００６９】
なお、画像ＩＤとは、画像ＤＢに登録されている比較先画像に付与されるユニークな番号である。類似度では、アノテーションそのものまたは表記ゆれ等でヒットした場合に類似度を１００％とし、同義語でヒットした場合に類似度を９０％とするなど、便宜的な類似度を付与する。ヒット領域及び回転角度に関しては、部分画像検索を行った際に用いられる項目であるため、アノテーションによる検索処理では０の無効値を入れておく。また、結果表示判別フラグとは、ヒットした領域をクリップし、更に回転正規化して表示することが可能かどうかを示すフラグ情報である。アノテーションによる検索処理ではそのような情報は得られないため、この項目ではＯＦＦとなる。
【００７０】
次に、ステップＳ６０６において、第２の比較先画像列である集合Ａの画像に対して、クエリ画像であるランドマークＡの例示画１の部分画像検索を前述した図５の手順により行う。そして、ステップＳ６０７において、ステップＳ６０６の検索結果を集合Ｃとして保持する。このとき、集合Ｃのそれぞれの画像に対しては、例えば、以下のスキーマで検索内部情報を保持する。
画像ＩＤ：１００
類似度：９０％
ヒット領域：１００，１００，２００，２００
回転角度：３０
結果表示判別フラグ：ＯＮ
【００７１】
部分画像検索は、局所特徴量を用いてマッチング処理を行うことにより実現する。上記に示した例は、類似度（最終投票数ＶｏｔｅＭａｘ）が９０％であり、類似領域は、（ＭｉｎＸ、ＭｉｎＹ）−（ＭａｘＸ、ＭａｘＹ）により示される（１００，１００）−（２００，２００）の対角で定められる矩形である。さらに、クエリ画像に対して３０度の回転を行っている。
【００７２】
次にＳ６０８において、ステップＳ６０６と同様に、集合Ａの画像に対して、クエリ画像であるランドマークＡの例示画２の部分画像検索を前述した図５の手順により行う。そして、ステップＳ６０９においては、例示画１と例示画２とで部分画像検索を行った結果の論理和を取り、第３の比較先画像列である集合Ｄを作成する。このとき、例示画１の比較先画像と例示画２の比較先画像とで画像ＩＤが重複している可能性がある。このように、集合Ｄの中に同じ画像ＩＤの画像が含まれている場合であって、例示画２との類似度が例示画１との類似度を上回った場合は、その類似度、ヒット領域及び回転角度を更新する。
【００７３】
例えば、集合Ｄの中に同じ画像ＩＤの画像が含まれており、例示画２との類似度が９２％である場合は、画像ＩＤが１００の画像に対して、以下のように検索内部情報を更新する。
画像ＩＤ：１００
類似度：９２％
ヒット領域：２００，２００，４００，４００
回転角度：２０
結果表示判別フラグ：ＯＮ
【００７４】
次に、ステップＳ６１０において、アノテーションによる検索結果の集合Ｂと部分画像検索による集合Ｄとの論理和を取り、画像の個数Ｎの集合Ｅを作成する。このとき、集合Ｂの一部と集合Ｄの一部とで画像ＩＤが重複している可能性がある。このように集合Ｂと集合Ｄとで同じ画像ＩＤの画像が含まれている場合には、以下のルールによりその画像の検索内部情報を更新し、その画像を実質的に集合Ｄの画像として取り扱う。
（１）類似度に関しては、類似度の高い方を用いる。
（２）ヒット領域に関しては、部分画像検索により得られた値を用いる。
（３）同様に、回転角度に関しても部分画像検索により得られた値を用いる。
（４）結果表示判別フラグはＯＮとする。
【００７５】
他方、集合Ｂと集合Ｄとで同じ画像ＩＤのものが存在しない場合には、検索内部情報の更新は行わず、そのまま論理和の集合Ｅを作成する。
【００７６】
次に、ステップＳ６１１において、統合したＮ個の検索内部情報を類似度の高い順にソートする。そして、ステップＳ６１２において、カウンタｉを０にセットし、ステップＳ６１３において、カウンタｉが個数Ｎに達したか否かを判定する。この判定の結果、カウンタｉが個数Ｎに達した場合は、処理を終了する。
【００７７】
一方、ステップＳ６１３の判定の結果、カウンタｉが個数Ｎに達していない場合には、ステップＳ６１５において、ｉ＋１番目の検索内部情報の結果表示判別フラグを参照し、その値がＯＮであるか否かを判定する。この判定の結果、結果表示判別フラグがＯＮである場合は、ステップＳ６１６において、その検索内部情報を有する画像を検索結果として表示するためのサムネール画像を作成する。このとき、ヒット領域を回転角度分逆回転させ、サムネールの大きさで正規化してサムネール画像を作成し、表示装置２１０に表示する。なお、複数のクエリ画像が含まれる場合には、その合計個数でサムネール画像を分割し、それぞれの分割領域に対して同様に大きさと回転角度とを補正したサムネール画像を作成する。
【００７８】
一方、ステップＳ６１５の判定の結果、結果表示判別フラグがＯＦＦである場合は、ステップＳ６１７において、画像全体を単純にサムネールの大きさに正規化してサムネール画像を作成し、表示装置２１０に表示する。なお、天地判定などの処理により画像全体の回転方向が判別可能である場合には、その角度に従って回転を行う。
【００７９】
次に、ステップＳ６１８において、カウンタｉを１つ増加させ、再びステップＳ６１３に戻り、処理すべき画像が終わるまでループする。これらの処理により、部分画像検索によりヒットした画像に関しては、クエリ画像と同様の回転角度に調整した状態で検索結果が表示されるので、視認性を向上させることができる。
【００８０】
次に、検索結果の表示例について説明する。図８（ａ）〜図８（ｄ）は、画像ＤＢへ登録されている画像のうち、図７に示すクエリ画像に対する検索結果としてヒットした画像の一例を示す図である。ここで、図８（ａ）〜図８（ｃ）に示す画像は、アノテーションはないが、部分画像検索によりマッチングが可能な画像である。一方、図８（ｄ）に示す画像は、「ランドマークＡ」というアノテーションを有しているが、局所特徴量を求めることができず、部分画像検索により検索できない画像である。ただしが、画像処理による天地判定により写真の向きを判別できる画像である。なお、これらの画像の全てのＧＰＥ情報は同じとみなせる範囲内のものである。
【００８１】
一般的な検索結果の表示方法では、図９に示すように、ヒットした画像を単純に縮小したサムネール画像を挿入した検索結果を生成することになる。これに対して本実施形態においては、図１０に示すように、クエリ画像と同様の回転角度に調整した後、ヒットした領域でクリッピングを行って表示する。
【００８２】
なお、図８（ｃ）に示す画像に関しては、同一形状のランドマークが２つ存在するので、サムネール画像の領域を２つに領域を分割し、夫々の分割領域において同様の回転角度に調整した後にクリッピングした画像を挿入して統合する。また、図８（ｄ）に示す画像は、天地判定が可能であるので、９０度単位で回転させた状態で画像全体を縮小したサムネール画像を生成し、検索結果に挿入する。
【００８３】
以上のように本実施形態によれば、検索結果を表示する際に、クエリ画像を基準に回転正規化した後で表示するようにしたので、検索結果を確認する時に心的回転によるユーザの負荷を軽減することが可能になる。また、検索に必要な局所特徴量を算出する過程で傾きパラメータが算出されるので、計算量が大幅に増加することなくクエリ画像を基準とした回転正規化が可能になる。
【００８４】
なお、本実施形態では、図５のステップＳ５１５〜Ｓ５１８において、ヒット領域を示す座標値ＭｉｎＸ、ＭａｘＸ、ＭｉｎＹ、ＭａｘＹを簡易的に算出した。一方、ステップＳ５１５の判定の結果、ｘ、ｙの一方のみが下端である場合に下端であるＸまたはＹの値を更新してもよい。また、ステップＳ５１７の判定の結果、ｘ、ｙの一方のみが上端である場合も同様である。これにより、最外接矩形を求めることが可能となる。この最外接矩形をヒット領域とすることにより、より広いヒット領域を求め、算出したヒット領域が小さくクリッピングしたい被写体の欠けてしまうことを防ぐことができる。
【００８５】
また、オブジェクト認識結果を用い、画像中からオブジェクト領域情報を得る方法を用いてもよい。オブジェクト領域情報の取得方法としては、様々な回転角度の学習画像を用いた機械学習により取得する。ところが、この方法を用いると、ヒット領域はわかるが回転角度が不明な場合がある。この場合には、ヒット領域によるクリップを行ってサムネール画像を作成する。一方、回転角度ごとに機械学習を行って判別機を作成する場合には、大まかな回転角度も得られる場合がある。この場合には、得られた回転角度を元に成立した状態で表示することも可能となる。
【００８６】
また、本実施形態では、検索結果として画像を表示する例について説明したが、検索結果を印刷装置に出力して印刷する場合にも適用できる。また、コンテンツを代表する内容を表す画像として、コンテンツと対応付けて検索結果を記憶するようにしてもよい。さらに本実施形態では、同様の回転角度に調整した後にクリッピングを行っているが、クリッピング処理を行った後に同様の回転角度に調整してもよい。この場合、クリッピングにより消滅した領域に対して黒や白などの画素で補完する必要が有り、画質がやや劣る可能性があるが、回転処理の対象領域が小さくなるので処理が高速になる。
【００８７】
（その他の実施形態）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００８８】
２０３  第１の局所特徴点／局所特徴量抽出部
２０６  第２の局所特徴点／局所特徴量抽出部
２０７  局所特徴点／局所特徴量比較部
２０９  検索部
【図１】
2013161294.tif 000008
【図２】
2013161294.tif 000009
【図３】
2013161294.tif 000010
【図４】
2013161294.tif 000011
【図５】
2013161294.tif 000012
【図６】
2013161294.tif 000013
【図７】
2013161294.tif 000014
【図８】
2013161294.tif 000015
【図９】
2013161294.tif 000016
【図１０】
2013161294.tif 000017