画像検索装置およびその方法
【課題】処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にすることを可能にする。
【解決手段】入力されたクエリ画像と登録されている比較先画像との類似を判定して、該クエリ画像に類似する画像を検索する画像検索装置は、クエリ画像から選択された特徴点と比較先画像の特徴点とをそれら特徴点の特徴量に基づいて対応付けることにより、２つの画像において対応する複数対の特徴点を抽出する。そして、複数対の特徴点から、少なくとも２対の特徴点を取得し、それらの各対に関して、２つの画像のうちの一方の画像の特徴点の座標が他方の画像の特徴点の座標と一致するように座標変換処理するための座標変換係数を決定する。そして、上記座標変換係数を用いた座標変換処理による座標の変換量があらかじめ指定された制約条件を満足する場合にのみ、２つの画像の類似判定のために、上記複数対の特徴点に関して上記座標変換係数を用いた座標変換処理を施し、一方の画像の変換後の特徴点の座標と他方の画像の対応する特徴点の座標とを比較する。
【解決手段】入力されたクエリ画像と登録されている比較先画像との類似を判定して、該クエリ画像に類似する画像を検索する画像検索装置は、クエリ画像から選択された特徴点と比較先画像の特徴点とをそれら特徴点の特徴量に基づいて対応付けることにより、２つの画像において対応する複数対の特徴点を抽出する。そして、複数対の特徴点から、少なくとも２対の特徴点を取得し、それらの各対に関して、２つの画像のうちの一方の画像の特徴点の座標が他方の画像の特徴点の座標と一致するように座標変換処理するための座標変換係数を決定する。そして、上記座標変換係数を用いた座標変換処理による座標の変換量があらかじめ指定された制約条件を満足する場合にのみ、２つの画像の類似判定のために、上記複数対の特徴点に関して上記座標変換係数を用いた座標変換処理を施し、一方の画像の変換後の特徴点の座標と他方の画像の対応する特徴点の座標とを比較する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像中の特徴点の類似度に基づく画像検索技術に関するものである。
【背景技術】
【０００２】
一般に、画像の回転に対応した画像検索は、クエリ画像を回転して特徴量を求める或いは特徴量を回転変換したものを用いることにより行われていた。
【０００３】
従来から提案されている画像中の特徴点の類似度に基づく画像検索技術として、特許文献１が挙げられる。特許文献１では、局所的な特徴同士の比較に基づく画像検索において、クエリ画像から無作為に選ばれた特徴点の対に類似する特徴点を登録画像中から求める。そして、対の特徴点の位置関係に基づいてクエリ画像と登録画像の間の幾何学変換関数を求め、対以外の特徴点が幾何学変換関数によって変換された場所に、登録画像の対応する特徴点が存在しているものをカウントし、類似性を判定していた。
（以下で、非特許文献１，２は「発明を実施するための形態」の欄において参照されている文献である。）
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−０６５３９９号公報
【非特許文献】
【０００５】
【非特許文献１】C. Harris and M.J. Stephens, “Acombined 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,” RiologicalCybernetics, vol.55, pp.367-375, 1987.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記処理では、クエリ画像から無作為に選ばれた特徴点の対に対して登録画像に存在するその対に類似する特徴点が正しく対応していない場合に、クエリ画像の特徴点を幾何学変換する処理が大変重くなる。また、もし登録画像の同じ位置に特徴点が現われ無い場合には、特徴点の選び方が悪かったとし、再びクエリ画像から無作為に特徴点の対を選ぶ。
【０００７】
即ち、特許文献1の画像検索処理は、特徴点の選択から幾何変換までの処理を夥しい回数こなし、その処理回数の中で適切な特徴点の対が含まれることを期待する処理であり、多くの処理コストを要するため、その改善が必要であった。また、特徴点を無作為で選ぶので、反復回数が少ないと検索結果の再現性（同一の類似度で算出される事も含む）が乏しくなるという課題もあった。
【０００８】
また、検索結果に対して、回転角度や拡大・縮小率などによる絞り込みを行う場合、上記処理結果に対して処理をする場合には、更に処理が重いものと成ってしまう。
【０００９】
本発明は上記の課題に鑑みてなされたものであり、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事を可能にすることを目的とする。
【課題を解決するための手段】
【００１０】
上記の目的を達成するための本発明の一態様による画像検索装置は以下の構成を備える。すなわち、
入力されたクエリ画像と登録されている比較先画像との類似を判定して、該クエリ画像に類似する画像を検索する画像検索装置であって、
前記クエリ画像から選択された特徴点と前記比較先画像の特徴点とをそれら特徴点の特徴量に基づいて対応付けることにより、前記クエリ画像と前記比較先画像の２つの画像において対応する複数対の特徴点を抽出する抽出手段と、
前記複数対の特徴点から、少なくとも２対の特徴点を取得する取得手段と、
前記少なくとも２対の特徴点の各対に関して、前記２つの画像のうちの一方の画像の特徴点の座標が他方の画像の特徴点の座標と一致するように変換するための座標変換係数を決定する決定手段と、
前記決定手段で決定された前記座標変換係数を用いた座標変換処理による座標の変換量があらかじめ指定された制約条件を満足するか否かを判定する判定手段と、
前記判定手段で満足すると判定された場合にのみ、前記複数対の特徴点に関して、前記一方の画像の特徴点の座標を前記座標変換係数を用いた座標変換処理により変換し、変換後の特徴点の座標と前記他方の画像の対応する特徴点の座標とを前記２つの画像の類似を判定するために比較する比較手段とを備える。
【発明の効果】
【００１１】
本発明によれば、検索に対する絞り込み処理を、クエリからの特徴点の選択から幾何変換までの処理に適切に関連つける事が出来るので、余計な幾何変換処理を行わなくて済み、後処理で絞込条件に適うかの確認処理を行う必要も無くなる。
【図面の簡単な説明】
【００１２】
【図１】実施形態による画像登録装置の構成例を示すブロック図。
【図２】実施形態による画像検索装置の構成例を示すブロック図。
【図３】実施形態による画像の登録処理の手順を表すフローチャート。
【図４】縮小画像生成の例を示す図。
【図５】実施形態による画像の検索処理の手順を表すフローチャート。
【図６】実施形態による局所特徴の比較処理を示すフローチャート。
【図７】アフィン変換係数と幾何変換の関係を示す図。
【図８】幾何変換の制約を与えるユーザインターフェース（ＵＩ）の例を示す図。
【図９】幾何変換の制約を与えるユーザインターフェース（ＵＩ）の例を示す図。 従って、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事が出来、ひいては、検索の安定性や再現性に寄与する事が出来る。
【発明を実施するための形態】
【００１３】
以下、添付の図面を参照して本発明の好適な実施形態を説明する。
【００１４】
＜実施形態の概要について＞
本発明の特徴点の基づく画像検索方法では、回転不変の性質を持つの特徴点および回転不変の性質を持つ特徴量を用いる。登録時は従来技術と同様、登録画像の特徴点を決定し特徴点に対する特徴量を記憶しておく。この処理については、図１、図３、図４により後述する。
【００１５】
検索時には、クエリ画像の特徴点から少なくとも２点を選択して、比較先画像中の対応する特徴点を求め、少なくとも２対の特徴点の座標に基づくアフィン変換関数を決定する。そして、これら２つの画像の類似度を求めるために、クエリ画像及び比較先画像の一方の画像の特徴点群の座標をアフィン変換して、他方の画像の特徴点群の座標と比較する。この処理については、図２、図４、図５、図６により詳述する。
【００１６】
ここで、上述のごとく決定されたアフィン変換係数における、拡大縮小の率、回転角度、平行移動の量、変形の有無、鏡像変換の有無といた変換要素に関して、あらかじめ設定された制約条件を満たすか否かが判定される。そして、制約条件を満たすと判定された場合のみアフィン変換以降の処理を行うようにする。このようにすれば、計算負荷の重い特徴点のアフィン変換処理数を減らすことができ、最小限の計算コストで絞り込み処理が行われるので好都合である。この処理については、図６のフローチャート（特にステップＳ６０９）により詳述される。
【００１７】
例えば、アフィン変換係数のうち拡大／縮小に関わる係数から、当該アフィン変換による拡大／縮小に関わる変換量（拡大・縮小率）が好ましい拡大・縮小率の範囲内に有るかどうかが判定される。そして、好ましい範囲内にあると判定された場合のみ、後段のアフィン変換以降の処理を行うようにする。このようにすれば、最小限の計算コストで拡大・縮小率に関する絞り込み処理が行われるので好都合である。
【００１８】
なお、アフィン変換を用いなくとも、クエリ画像と比較先画像における選択された２つの特徴点間の距離の比率から求まる拡大・縮小率が、あらかじめ指定された拡大・縮小率の範囲内に有る場合のみアフィン変換以降の処理を行うようにしてもよい。この場合、アフィン変換係数を決定する前に拡大・縮小率に関する絞込を行なうことができ、最小限の計算コストで拡大・縮小率に関する絞り込み処理が行われるので好都合である。
【００１９】
また、例えば、アフィン変換係数のうち回転に関わる係数から、当該変換量があらかじめ設定された好ましい回転角度の範囲内に有るか否かが判定される。そして、好ましい範囲内にあると判定された場合のみ、後段の比較先画像の特徴点群の座標のアフィン変換以降の処理を行うようにすることもできる。この場合、最小限の計算コストで回転角度に関する絞り込み処理が行われるので好都合である。
【００２０】
また、例えば、アフィン変換係数のうち平行移動に関わる係数から、当該変換量があらかじめ指定された平行移動の距離の範囲内に有るか否かが判定される。そして、好ましい範囲内にあると判定された場合のみ、後段のアフィン変換以降の処理を行うようにすることができる。最小限の計算コストで平行移動に関する絞り込み処理が行われるので好都合である。
【００２１】
上記、アフィン変換係数のうち変形に関わる設定から、変形を検索しない設定の場合、変形のない場合のみ、後段のアフィン変換以降の処理を行うようにすることができる。最小限の計算コストで変形に関する絞り込み処理が行われるので好都合である。
【００２２】
なお、上述した制約条件は、例えば図８や図９に示したユーザインターフェース（ＵＩ）によりユーザが容易に指定できる。
【００２３】
以上により、処理負荷を多くすること無く、アフィン変換係数を決定するための特徴点対の選択の反復回数を大きい数にすることが出来、ひいては、検索の安定性や再現性に寄与することが可能となる。
【００２４】
＜第１実施形態＞
図１は本発明の第１実施形態における画像登録装置の構成例を示すブロック図である。図１において、１００は画像登録装置であり、画像入力部１０２、縮小画像生成部１０３、局所特徴点抽出部１０４、局所特徴量算出部１０５、特徴量登録部１０６を備える。１０１は登録画像であり、画像登録装置１００によって後述する画像特徴データベースに登録される画像である。１０７は画像特徴データベースであり、画像登録装置１００により登録画像１０１から抽出された画像特徴が登録される。
【００２５】
図２は本発明の第１実施形態における画像検索装置の構成例を示すブロック図である。図２において、２００は画像検索装置であり、画像入力部２０２、縮小画像生成部２０３、局所特徴点抽出部２０４、局所特徴量算出部２０５、局所特徴量検定部２０６、特徴比較部２０７を備える。２０１はクエリ画像である。画像検索装置２００は、画像特徴データベース１０７から当該クエリ画像２０１に類似した画像を検索する。２０８は検索結果画像であり、画像検索装置２００が画像特徴データベース１０７を検索した結果として出力される画像である。
【００２６】
以上のような構成を備えた本実施形態にかかる画像登録装置１００及び画像検索装置２００の動作例を以下に説明する。
【００２７】
［画像の登録処理］
まず、画像登録装置１００が行う画像の登録処理について説明する。図３は画像の登録処理の手順を表すフローチャートである。ステップＳ３０１において、画像入力部１０２は、登録画像１０１を読み込む。ステップＳ３０２において、画像入力部１０２の輝度成分画像生成部１１１は、当該登録画像１０１から輝度成分を抽出して輝度成分画像を生成し、当該輝度成分画像を縮小画像生成部１０３に渡す。また、画像入力部１０２は、登録画像１０１を特徴量登録部１０６に渡す。
【００２８】
次に、ステップＳ３０３において、縮小画像生成部１０３は、画像入力部１０２から渡された輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成し、生成した縮小画像を局所特徴点抽出部１０４に渡す。ただし、倍率ｐおよび縮小画像の枚数ｎはあらかじめ定めておく。図４は縮小画像生成の例を示す図であり、倍率ｐが２の−１／４乗、縮小画像の枚数ｎが９の場合に縮小画像生成部１０３が生成する縮小画像の例を示している。図４において、４０１は画像入力部１０２から渡された輝度成分画像、４０２は当該輝度成分画像から倍率ｐに従って４回縮小された縮小画像、４０３は当該輝度成分画像から倍率ｐに従って８回縮小された縮小画像である。図４の例においては、縮小画像４０２は画像入力部１０２から渡された輝度成分画像が１／２に縮小された画像となり、縮小画像４０３は画像入力部１０２から渡された輝度成分画像が１／４に縮小された画像となる。なお、本実施形態における縮小画像は、線形補間による縮小方法により生成するものとするが、他の縮小方法が用いられてもよい。
【００２９】
次に、ステップＳ３０４において、局所特徴点抽出部１０４は、縮小画像生成部１０３から渡されたｎ枚の縮小画像それぞれにおいて、画像の回転があってもロバストに抽出されるような特徴点（回転不変の性質を持つ特徴点）を抽出する。そして、局所特徴点抽出部１０４は、抽出した当該回転不変の性質を持つ特徴点を局所特徴量算出部１０５に渡す。なお、本実施形態では、回転不変の性質を持つ特徴点の抽出方法としてHarris作用素（非特許文献１）を用いる。具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素および当該画素の８近傍にある画素（合計９画素）の画素値を調べる。そして、当該画素が局所極大（当該９画素の中で当該画素の画素値が最大になる）になる点を回転不変の性質を持つ特徴点として抽出する。このとき、当該画素が局所極大になったときでも、当該画素の値がしきい値以下の場合には回転不変の性質を持つ特徴量として抽出しないようにする。なお、回転不変の性質を持つ特徴点を抽出可能な方法であれば、本実施形態で用いた特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部１０４に適用可能である。
【００３０】
次に、局所特徴量算出部１０５では、局所特徴点抽出部１０４から渡された回転不変の性質を持つ特徴点それぞれについて、ステップＳ３０５により画像の回転があっても不変となる局所特徴量（回転不変の性質を持つ局所特徴量）を算出する。抽出した当該回転不変の性質を持つ局所特徴量は座標情報と関連付けされた上で、特徴量登録部１０６に渡される。ここで、本実施形態では、回転不変の性質を持つ特徴量の算出方法としてLocalJet（非特許文献２）およびそれらの導関数の組み合わせを用いる。具体的には、式（１）に示す回転不変の性質を持つ特徴量を算出する。
【数１】
【００３１】
ただし、式（１）右辺で用いている記号は以下に示す式（２）から式（７）で定義される。ここで、式（２）はガウス関数と画像との畳み込み演算である。
【数２】
【００３２】
なお、回転不変の性質を持つ特徴量を算出可能な方法であれば、本実施形態で用いた特徴量算出方法に限らず、どのような特徴量算出方法でも局所特徴量算出部１０５に適用可能である。
【００３３】
次に、ステップＳ３０６において、特徴量登録部１０６は、局所特徴量算出部１０５から渡された回転不変の性質を持つ特徴量と画像入力部１０２から渡された登録画像１０１とを関連付け、画像特徴データベース１０７に登録する。以上で画像登録装置１００による画像登録処理が終了する。
【００３４】
［画像の検索処理］
次に、画像検索装置２００による画像の検索処理を説明する。図５は、第１実施形態による画像の検索処理の手順を表すフローチャートである。
【００３５】
ステップＳ５０１において、画像入力部２０２は、クエリ画像２０１を読み込む。次に、ステップＳ５０２において、画像入力部２０２の閾値指定処理部２１１が、検索結果に期待するクエリ画像に対する拡大率の範囲、回転角度の範囲、平行移動の範囲のユーザ指定を受け付ける。但し、これら３項目を全て指定する必要は無く、特に制限を設けたい項目に対して範囲の指定を行えるようにすることが好ましい。
【００３６】
図８にこの幾何変換の制約を与えるユーザインターフェース（ＵＩ）の例を示す。チェックボックスにチェックを入れた項目に対してのみ制約を行い、例えば、各項目に対する制約はＡＮＤで制約が掛かるようにする。もちろん、論理式で指定できるようにする事も当然可能である。また、当然であるが、テキストボックスに入力された値の範囲に対する大小関係の不整合のチェックおよびユーザへの警告は当然行う。
【００３７】
以上のようにして指定された制約の値は、閾値指定処理部２１１により一時記憶される。
【００３８】
次に、ステップＳ５０３において、画像入力部２０２の輝度成分画像生成部２１２は、当該クエリ画像２０１から輝度成分を抽出して輝度成分画像を生成し、生成した輝度成分画像を縮小画像生成部２０３に渡す。
【００３９】
次に、ステップＳ５０４において、縮小画像生成部２０３は、画像入力部２０２から渡された輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成して当該縮小画像を局所特徴点抽出部２０４に渡す。ただし、倍率ｐおよび縮小画像の枚数ｎは前述の画像登録装置１００における画像の登録処理で用いた値と同じ値にする。
【００４０】
次に、ステップＳ５０５において、局所特徴点抽出部２０４は、縮小画像生成部２０３から渡されたｎ枚の縮小画像それぞれにおいて、画像の特徴点（回転不変の性質を持つ特徴点）を抽出する。抽出した当該回転不変の性質を持つ特徴点は局所特徴量算出部２０５に渡される。ここで本実施形態では、回転不変の性質を持つ特徴点の抽出方法として前述の画像の登録処理で用いた方法と同様に、Harris作用素を用いる。より具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素および当該画素の８近傍にある画素（合計９画素）の画素値を調べられる。そして、当該画素が局所極大（当該９画素の中で当該画素の画素値が最大になる）になる点が回転不変の性質を持つ特徴点として抽出される。このとき、当該画素が局所極大になったときでも、当該画素の値があらかじめ定められたしきい値以下の場合には回転不変の性質を持つ特徴量として抽出しないようにする。なお、回転不変の性質を持つ特徴点を抽出可能な方法であれば、本実施形態で用いた特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部２０４に適用可能である。
【００４１】
次に、ステップＳ５０６において、局所特徴量算出部２０５は、局所特徴点抽出部２０４から渡された回転不変の性質を持つ特徴点それぞれについて、画像の回転があっても不変となる局所特徴量（回転不変の性質を持つ局所特徴量）を算出する。抽出した当該回転不変の性質を持つ局所特徴量は座標情報と関連付けされた上で局所特徴量検定部２０６に渡される。ここで、回転不変の性質を持つ特徴量の算出方法は前述の画像の登録処理で用いた方法と同じ方法を使用する。すなわち、本実施形態では、LocalJetおよびそれらの導関数の組み合わせを用い、式（１）に示す回転不変の性質を持つ特徴量を算出する。局所特徴量検定部２０６は局所特徴量の変動を検定し、変動の少ない局所特徴量のみ合格とする。
【００４２】
次に、ステップＳ５０７において、特徴比較部２０７は、局所特徴量検定部２０６から渡された回転不変の性質を持つ特徴量と画像特徴データベース１０７に登録されている回転不変の性質を持つ特徴量とを比較する。この比較は、ステップＳ５０２で与えたアフィン変換係数の閾値を考慮しながら、画像特徴データベース１０７に登録されている登録画像ごとに実施される。そして、比較の結果として登録画像ごとにスコアが算出される。なお、スコアの算出方法については図６のフローチャートにより後述する。
【００４３】
次に、ステップＳ５０８において、特徴比較部２０７は、算出した当該類似度と当該類似度の算出元となった画像とを関連付けて検索結果リストを作成した後、当該スコアを降順にソートする。そして、特徴比較部２０７は、スコアが大きい画像と当該画像のスコアとをソート順に検索結果２０８として出力する。
【００４４】
［スコアの算出方法］
次に、本実施形態における（ステップＳ５０７における）スコアの算出方法を説明する。ここで、局所特徴点抽出部２０４及び局所特徴量算出部２０５から渡された、回転不変の性質を持つ特徴量をＶｓ、回転不変の性質を持つ特徴量に関連付けされている座標をＳ（x，y）とする。また、画像特徴データベース１０７に登録されている画像Ｒ上に存在する回転不変の性質を持つ特徴量をＶｑ、回転不変の性質を持つ特徴量に関連付けされている座標をＱ（x’，y’）とする。
【００４５】
以下、特徴比較部２０７における類似度（スコア）の算出手順を図６に示すフローチャートに従って説明する。
【００４６】
ステップＳ６０１において、特徴比較部２０７は、検索されるべき画像のクエリ画像に対する拡大率の範囲、回転角度の範囲、平行移動の範囲、の指定を画像入力部２０２（閾値指定処理部２１１）より受け取る。ステップＳ５０２で上述したように、これら３項目を全て指定する必要は無く、特に制限を設けたい項目に対して範囲の指定を行えるようにすることが好ましい。
【００４７】
次に、ステップＳ６０２により、最終投票数を表す変数VoteMaxを０に初期化する。次に、ステップＳ６０３により、ＶｑとＶｓとの特徴量間距離をすべての組み合わせについて計算し、最短距離対応点リストを作成する。このように、クエリ画像から選択された特徴点を、その特徴量に基づいて、登録されている比較先画像の特徴点と対応付けることにより、クエリ画像と比較先画像で対応する複数対の特徴点が抽出される。
【００４８】
この最短距離対応点を求める際に、先に、クエリ画像の各特徴点に対して記憶しているマハラノビスの距離を算出するための観測値をX=(X1,X2,…,Xp)'とし、母集団ｊの分散共分散行列Σjの逆行列Σj-1と平均（重心）μを用いて式（８）に基づいて距離ｄjを求める。そして、求めた距離と分散共分散逆行列を含む最短距離対応点リストを作成する。
【００４９】
ｄj2=(Ｘ−μj)'Σj-1(Ｘ−μj) …（８）
すなわち、計算した特徴量間距離がしきい値Ｔｖ以下となり、かつ、最短距離となるようなＶｑとＶｓとの組み合わせ（対応点）を抽出し、最短距離対応点リストに登録する。以後、本実施形態の説明では、最短距離対応点リストに登録された対応点について、当該対応点の回転不変の性質を持つ特徴量をそれぞれＶｑ（ｋ）とＶｓ（ｋ）と記載する。また、それらＶｑ（ｋ）とＶｓ（ｋ）に対応付けられている座標についてはそれぞれＱk（x’k，y’k）、Ｓk（xk，yk）などと添え字をつけて記載する。また、ステップＳ６０３で作成された最短距離対応点リストに登録された対応点の組数をｍ組とする。
【００５０】
次に、ステップＳ６０４により、類似度算出処理の反復カウント数を表す変数Countを０に初期化する。次に、ステップＳ６０５により、反復カウント数Countがあらかじめ定めた最大反復処理回数Ｒｎを超えていないか判定する。超えている場合はステップＳ６２１により最終投票数VoteMaxを出力して処理を終了する。超えていない場合は、ステップＳ６０６に移る。Ｓ６２１で総合類似度算出処理に関する詳細説明は、後で行う。
【００５１】
ステップＳ６０６では、投票数を表す変数Voteを０に初期化する。次に、ステップＳ６０７において、複数対の特徴点から、少なくとも２対の特徴点が取得される。本実施形態では、ステップＳ６０３で生成された最短距離対応点リストから対応点の組の座標をランダムに２組抽出する。本実施形態では、これらの座標をＱ1（ｘ’1，ｙ’1）、Ｓ1（ｘ1，ｙ1）およびＱ2（ｘ’2，ｙ’2）、Ｓ2（ｘ2，ｙ2）と記載する。
【００５２】
次に、ステップＳ６０８において、ステップＳ６０７で抽出した２対の特徴点の各対の座標を、クエリ画像と比較先画像とで一致させるように、座標変換処理のための座標変換係数が決定される。本実施形態では、座標変換処理として、アフィン変換を用いる。即ち、ステップＳ６０７により、抽出したＱ1（ｘ’1，ｙ’1）、Ｓ1（ｘ1，ｙ1）およびＱ2（ｘ’2，ｙ’2）、Ｓ2（ｘ2，ｙ2）が式（９）に示す変換を満たしていると仮定し、式（９）中の変数ａ〜ｆを求める。ただし、図６に示すフローチャート中のステップＳ６０８では、変数ａ〜ｄで構成される行列をＭ、変数ｅ〜ｆで構成される行列をＴで示している。
【数３】
【００５３】
ここで、本実施形態では、簡単のため回転変換、相似変換および平行移動の組み合わせだけを考える。このとき、式（９）は式（１０）のように書き換えられる。
【数４】
【００５４】
このとき、変数ａ、ｂ、ｅ、ｆはｘ’1、ｙ’1、ｘ1、ｙ1、ｘ’2、ｙ’2、ｘ2、ｙ2を使って式（１１）から式（１４）で表される。
【数５】
【００５５】
図７に式（９）におけるアフィン変換係数と、幾何変換の関係を示す。ここで、式（１１）から式（１４）にて得たａ，ｂ，ｅ，ｆと、図８の表において敷き（１０）の導出の際に設けたｂ＝−ｃ、ｄ＝ａの制約を用いて考える。
【００５６】
回転行列に拡大・縮小行列を掛けても、単に回転行列をＳ倍したものになるだけである。
【００５７】
従って、ｃｏｓ２Θ ＋ ｓｉｎ２Θ ＝ １の制約を用い、
拡大率 Ｓ＝sqrt(ａ２＋ｂ２) …（１５）
で拡大率が求まる。従って、
回転角度 Θ＝ ｃｏｓ-1（ａ/Ｓ） …（１６）
となる。もちろん、
平行移動ベクトル Ｔ＝（ｅ，ｆ） …（１７）
となる。
【００５８】
そしてステップＳ６０９において、特徴比較部２０７は、上記のようにして決定された座標変換係数（アフィン変換係数）を用いた座標変換処理（アフィン変換処理）による座標の変換量が予め指定された制約条件を満足するか否かを判定する。即ち、ステップＳ６０１であらかじめ与えられ一時記憶しておいた拡大・縮小率の範囲、回転角度の範囲、平行移動ベクトルの範囲と、上記式（１５）、式（１６）および式（１７）で得たＳ、ΘおよびＴとをステップＳ６０９で比較する。この比較の結果、これらの条件を全て満たす場合にのみ処理はステップＳ６１０に進み、一つでも満たさないものがある場合にはステップＳ６０５で別の対応点の選択を行う事になる。
【００５９】
もちろん、範囲を与えなかった項目に関しては考慮する必要は無く、例えば、拡大率の範囲のみが指定されていれば、その範囲に式（１５）で得たＳが入っているかどうかだけを判断すれば良い。
【００６０】
次に、ステップＳ６１０では、ステップ６０７において当該最短距離対応点リストからランダムに抽出された２組の点以外の点を選択するために、対応点選択変数ｋを３に初期化する。次に、ステップ６１１により、対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていないか判定する。超えている場合はステップＳ６１８に処理を移すが、これについては後述する。ステップＳ６１１における判定で対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていない場合は、処理はステップＳ６１２に進む。
【００６１】
ステップＳ６１２において、特徴比較部２０７は、ステップ６０７において当該最短距離対応点リストからランダムに抽出された２組の点Ｓ1（ｘ1，ｙ1）およびＳ2（ｘ2，ｙ2）以外の点を、当該最短距離対応点リストから抽出する。本実施形態では、抽出された点をＳk（ｘk，ｙk）と記載する。
【００６２】
次に、ステップＳ６１３において、特徴比較部２０７は、Ｓk（ｘk，ｙk）が式（９）を使って移される座標Ｓ’（ｘ’k，ｙ’k）を求める。
【００６３】
その後、ステップＳ６１４において、特徴比較部２０７は、座標Ｓ’（ｘ’k，ｙ’k）と座標Ｑk（ｘ’k，ｙ’k）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離がしきい値Ｔｄ以下であるかどうかを判定する。当該ユークリッド距離がしきい値Ｔｄ以下の場合には、特徴比較部２０７は、ステップＳ６１５において、Voteに対する対応点の対Ｓ’ｋ，Ｑｋを記憶する。そして、更にステップＳ６１６において、投票数Voteをインクリメントし、ステップＳ６１７に処理を移す。当該ユークリッド距離がしきい値Ｔｄより大きい場合には、何もせずにステップＳ６１７に処理を移す。
【００６４】
ステップＳ６１７では、対応点選択変数ｋをインクリメントし、処理はステップＳ６１１に戻る。
【００６５】
次に、ステップ６１１において対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていた場合の処理であるステップＳ６１８を説明する。特徴比較部２０７は、ステップ６１８において、投票数Voteの値と最終投票数VoteMaxの値とを比較し、投票数Voteの値が最終投票数VoteMaxの値よりも大きい場合はステップＳ６１９の処理を実行する。ステップＳ６１９において、特徴比較部２０７は、最終投票数VoteMaxの値を投票数Voteの値で置き換えた後、ステップＳ６２０でCountをインクリメントし、ステップＳ６０５に処理を戻す。また、投票数Voteの値と最終投票数VoteMaxの値とを比較し、投票数Voteの値が最終投票数VoteMaxの値以下の場合は、ステップＳ６１９をスキップして、ステップＳ６２０でCountをインクリメントした後、ステップＳ６０５に処理を戻す。
【００６６】
以上のように、第１実施形態によれば、抽出された２対の特徴点に基づいて決定された座標変換係数を用いた座標変換処理の変換量が予め指定された制約条件を満足する可動化が判定される。そして、満足すると判定された場合にのみ、クエリ画像と比較先画像の類似を判定するべく、一方の画像の特徴点群の座標を当該座標変換係数を用いた座標変換処理により変換し、他方の画像の対応する特徴点群の座標と比較する処理が実行される。したがって、本実施形態にかかる画像検索装置は、クエリ画像から算出された回転不変の性質を持つ特徴量の変動を検定して変動の大きい回転不変の性質を持つ特徴量を検索時に使わないように構成されている。このため、無駄な座標変換処理を行うことなく、検索精度の低下を抑制することが可能になる。したがって、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事が出来るという利点が得られる。
【００６７】
なお、クエリ画像と比較先画像との拡大・縮小率は、複数対の特徴点（第１実施形態では２対の特徴点）について、クエリ画像における特徴点間の距離と比較先画像における特徴点間の距離との比率から求めることも可能である。そして、このようにして求めた拡大・縮小の率があらかじめ指定された制約条件を満足しない場合は、当該複数対の特徴点に関してステップＳ６０７、Ｓ６０８の処理を禁止して、次の新たな特徴点の対を取得するようにしてもよい。この場合、座標変換係数を算出する処理（ステップＳ６０８）から座標変換後の座標値を比較する処理（ステップＳ６１７）の実行が禁止されることになる。同様に、特徴点の各対を結ぶ直線のなす角から回転角度を求めることもできる。このような構成は、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事が出来るという本実施形態の利点に更に寄与するものである。
【００６８】
＜第２実施形態＞
第１実施形態におけるスコア算出方法の説明では、回転変換、相似変換および平行移動の組み合わせを説明したが、適用可能な幾何学変換はこれらに限られるものではない。上記以外の幾何学変換についても、図６のフローチャートのステップＳ６０８においてそれぞれに応じた変換行列を求めることにより、対応可能である。たとえば、アフィン変換の場合は、まず、ステップＳ６０７でランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ６０８において式（９）ではなく式（８）を使うこととし、ステップＳ６０６で選択した３組の対応点（合計６点）を使って変数ａ〜ｆを求めればよい。
【００６９】
図９に幾何変換の制約を与えるための、閾値指定処理部２１１によって提供されるＵＩの例を示す。
【００７０】
まず、変形を伴う拡大・縮小である場合には
ａ≠ｄ or ｂ≠（−ｃ） …（１８）
となるので、この条件を参照することにより変形を検索しないようにする事が可能である。即ち、変形が有るものを検索しない制約で検索を行う場合には、上記式（１８）を満たす場合に、次の対応点の処理ステップＳ６０５に移るようにすればよい。
【００７１】
他方、上記、ａ，ｂ，ｃ，ｄを式（１５）により求めたＳでわった結果が−１，０，０，１になるかで鏡像が検出できるので、鏡像画像の検索を制約に加えることも可能である。
【００７２】
この「鏡像画像を検索する」のチェックと、「変形を検索しない」のチェックはどちらか片方しかチェックできないように制御する必要がある。
【００７３】
尚、回転変換、相似変換および平行移動に関しては、第１実施形態と同様の方法で範囲の制約を掛ける事が可能である。
【００７４】
更に、回転に関しては、画像中の文字画像の文字認識（ＯＣＲ）結果に基づく方向検知処理を行い、方向補正を行った上で指定の回転角度範囲の画像を検索する事も当然考えられる。また、上記各実施形態では、クエリ画像の特徴点をアフィン変換し、アフィン変換後の座標と比較先画像の特徴点の座標とを比較したが、比較先画像の特徴点をアフィン変換し、アフィン変換後の座標とクエリ画像の特徴点の座標とを比較してもよい。
【００７５】
以上のように、第１及び第２実施形態によれば、検索に対する絞り込み処理を、クエリからの特徴点の選択から幾何変換までの処理に最適に関連つける事が出来る。そのため、余計な幾何変換処理を行わずに済み、後処理で絞込条件に適うかの確認処理を行う必要も無くなる。
【００７６】
従って、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事が出来、ひいては、検索の安定性や再現性に寄与する事が可能となる。
【００７７】
＜他の実施形態＞
以上、実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【００７８】
尚、本発明は、ソフトウェアのプログラムをシステム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによって前述した実施形態の機能が達成される場合を含む。この場合、供給されるプログラムは実施形態で図に示したフローチャートに対応したコンピュータプログラムである。
【００７９】
また、コンピュータが、コンピュータ読み取り可能な記憶媒体から格納されているプログラムを読み出し、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどとの協働で実施形態の機能が実現されてもよい。この場合、ＯＳなどが、実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される。
【技術分野】
【０００１】
本発明は、画像中の特徴点の類似度に基づく画像検索技術に関するものである。
【背景技術】
【０００２】
一般に、画像の回転に対応した画像検索は、クエリ画像を回転して特徴量を求める或いは特徴量を回転変換したものを用いることにより行われていた。
【０００３】
従来から提案されている画像中の特徴点の類似度に基づく画像検索技術として、特許文献１が挙げられる。特許文献１では、局所的な特徴同士の比較に基づく画像検索において、クエリ画像から無作為に選ばれた特徴点の対に類似する特徴点を登録画像中から求める。そして、対の特徴点の位置関係に基づいてクエリ画像と登録画像の間の幾何学変換関数を求め、対以外の特徴点が幾何学変換関数によって変換された場所に、登録画像の対応する特徴点が存在しているものをカウントし、類似性を判定していた。
（以下で、非特許文献１，２は「発明を実施するための形態」の欄において参照されている文献である。）
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−０６５３９９号公報
【非特許文献】
【０００５】
【非特許文献１】C. Harris and M.J. Stephens, “Acombined 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,” RiologicalCybernetics, vol.55, pp.367-375, 1987.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記処理では、クエリ画像から無作為に選ばれた特徴点の対に対して登録画像に存在するその対に類似する特徴点が正しく対応していない場合に、クエリ画像の特徴点を幾何学変換する処理が大変重くなる。また、もし登録画像の同じ位置に特徴点が現われ無い場合には、特徴点の選び方が悪かったとし、再びクエリ画像から無作為に特徴点の対を選ぶ。
【０００７】
即ち、特許文献1の画像検索処理は、特徴点の選択から幾何変換までの処理を夥しい回数こなし、その処理回数の中で適切な特徴点の対が含まれることを期待する処理であり、多くの処理コストを要するため、その改善が必要であった。また、特徴点を無作為で選ぶので、反復回数が少ないと検索結果の再現性（同一の類似度で算出される事も含む）が乏しくなるという課題もあった。
【０００８】
また、検索結果に対して、回転角度や拡大・縮小率などによる絞り込みを行う場合、上記処理結果に対して処理をする場合には、更に処理が重いものと成ってしまう。
【０００９】
本発明は上記の課題に鑑みてなされたものであり、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事を可能にすることを目的とする。
【課題を解決するための手段】
【００１０】
上記の目的を達成するための本発明の一態様による画像検索装置は以下の構成を備える。すなわち、
入力されたクエリ画像と登録されている比較先画像との類似を判定して、該クエリ画像に類似する画像を検索する画像検索装置であって、
前記クエリ画像から選択された特徴点と前記比較先画像の特徴点とをそれら特徴点の特徴量に基づいて対応付けることにより、前記クエリ画像と前記比較先画像の２つの画像において対応する複数対の特徴点を抽出する抽出手段と、
前記複数対の特徴点から、少なくとも２対の特徴点を取得する取得手段と、
前記少なくとも２対の特徴点の各対に関して、前記２つの画像のうちの一方の画像の特徴点の座標が他方の画像の特徴点の座標と一致するように変換するための座標変換係数を決定する決定手段と、
前記決定手段で決定された前記座標変換係数を用いた座標変換処理による座標の変換量があらかじめ指定された制約条件を満足するか否かを判定する判定手段と、
前記判定手段で満足すると判定された場合にのみ、前記複数対の特徴点に関して、前記一方の画像の特徴点の座標を前記座標変換係数を用いた座標変換処理により変換し、変換後の特徴点の座標と前記他方の画像の対応する特徴点の座標とを前記２つの画像の類似を判定するために比較する比較手段とを備える。
【発明の効果】
【００１１】
本発明によれば、検索に対する絞り込み処理を、クエリからの特徴点の選択から幾何変換までの処理に適切に関連つける事が出来るので、余計な幾何変換処理を行わなくて済み、後処理で絞込条件に適うかの確認処理を行う必要も無くなる。
【図面の簡単な説明】
【００１２】
【図１】実施形態による画像登録装置の構成例を示すブロック図。
【図２】実施形態による画像検索装置の構成例を示すブロック図。
【図３】実施形態による画像の登録処理の手順を表すフローチャート。
【図４】縮小画像生成の例を示す図。
【図５】実施形態による画像の検索処理の手順を表すフローチャート。
【図６】実施形態による局所特徴の比較処理を示すフローチャート。
【図７】アフィン変換係数と幾何変換の関係を示す図。
【図８】幾何変換の制約を与えるユーザインターフェース（ＵＩ）の例を示す図。
【図９】幾何変換の制約を与えるユーザインターフェース（ＵＩ）の例を示す図。 従って、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事が出来、ひいては、検索の安定性や再現性に寄与する事が出来る。
【発明を実施するための形態】
【００１３】
以下、添付の図面を参照して本発明の好適な実施形態を説明する。
【００１４】
＜実施形態の概要について＞
本発明の特徴点の基づく画像検索方法では、回転不変の性質を持つの特徴点および回転不変の性質を持つ特徴量を用いる。登録時は従来技術と同様、登録画像の特徴点を決定し特徴点に対する特徴量を記憶しておく。この処理については、図１、図３、図４により後述する。
【００１５】
検索時には、クエリ画像の特徴点から少なくとも２点を選択して、比較先画像中の対応する特徴点を求め、少なくとも２対の特徴点の座標に基づくアフィン変換関数を決定する。そして、これら２つの画像の類似度を求めるために、クエリ画像及び比較先画像の一方の画像の特徴点群の座標をアフィン変換して、他方の画像の特徴点群の座標と比較する。この処理については、図２、図４、図５、図６により詳述する。
【００１６】
ここで、上述のごとく決定されたアフィン変換係数における、拡大縮小の率、回転角度、平行移動の量、変形の有無、鏡像変換の有無といた変換要素に関して、あらかじめ設定された制約条件を満たすか否かが判定される。そして、制約条件を満たすと判定された場合のみアフィン変換以降の処理を行うようにする。このようにすれば、計算負荷の重い特徴点のアフィン変換処理数を減らすことができ、最小限の計算コストで絞り込み処理が行われるので好都合である。この処理については、図６のフローチャート（特にステップＳ６０９）により詳述される。
【００１７】
例えば、アフィン変換係数のうち拡大／縮小に関わる係数から、当該アフィン変換による拡大／縮小に関わる変換量（拡大・縮小率）が好ましい拡大・縮小率の範囲内に有るかどうかが判定される。そして、好ましい範囲内にあると判定された場合のみ、後段のアフィン変換以降の処理を行うようにする。このようにすれば、最小限の計算コストで拡大・縮小率に関する絞り込み処理が行われるので好都合である。
【００１８】
なお、アフィン変換を用いなくとも、クエリ画像と比較先画像における選択された２つの特徴点間の距離の比率から求まる拡大・縮小率が、あらかじめ指定された拡大・縮小率の範囲内に有る場合のみアフィン変換以降の処理を行うようにしてもよい。この場合、アフィン変換係数を決定する前に拡大・縮小率に関する絞込を行なうことができ、最小限の計算コストで拡大・縮小率に関する絞り込み処理が行われるので好都合である。
【００１９】
また、例えば、アフィン変換係数のうち回転に関わる係数から、当該変換量があらかじめ設定された好ましい回転角度の範囲内に有るか否かが判定される。そして、好ましい範囲内にあると判定された場合のみ、後段の比較先画像の特徴点群の座標のアフィン変換以降の処理を行うようにすることもできる。この場合、最小限の計算コストで回転角度に関する絞り込み処理が行われるので好都合である。
【００２０】
また、例えば、アフィン変換係数のうち平行移動に関わる係数から、当該変換量があらかじめ指定された平行移動の距離の範囲内に有るか否かが判定される。そして、好ましい範囲内にあると判定された場合のみ、後段のアフィン変換以降の処理を行うようにすることができる。最小限の計算コストで平行移動に関する絞り込み処理が行われるので好都合である。
【００２１】
上記、アフィン変換係数のうち変形に関わる設定から、変形を検索しない設定の場合、変形のない場合のみ、後段のアフィン変換以降の処理を行うようにすることができる。最小限の計算コストで変形に関する絞り込み処理が行われるので好都合である。
【００２２】
なお、上述した制約条件は、例えば図８や図９に示したユーザインターフェース（ＵＩ）によりユーザが容易に指定できる。
【００２３】
以上により、処理負荷を多くすること無く、アフィン変換係数を決定するための特徴点対の選択の反復回数を大きい数にすることが出来、ひいては、検索の安定性や再現性に寄与することが可能となる。
【００２４】
＜第１実施形態＞
図１は本発明の第１実施形態における画像登録装置の構成例を示すブロック図である。図１において、１００は画像登録装置であり、画像入力部１０２、縮小画像生成部１０３、局所特徴点抽出部１０４、局所特徴量算出部１０５、特徴量登録部１０６を備える。１０１は登録画像であり、画像登録装置１００によって後述する画像特徴データベースに登録される画像である。１０７は画像特徴データベースであり、画像登録装置１００により登録画像１０１から抽出された画像特徴が登録される。
【００２５】
図２は本発明の第１実施形態における画像検索装置の構成例を示すブロック図である。図２において、２００は画像検索装置であり、画像入力部２０２、縮小画像生成部２０３、局所特徴点抽出部２０４、局所特徴量算出部２０５、局所特徴量検定部２０６、特徴比較部２０７を備える。２０１はクエリ画像である。画像検索装置２００は、画像特徴データベース１０７から当該クエリ画像２０１に類似した画像を検索する。２０８は検索結果画像であり、画像検索装置２００が画像特徴データベース１０７を検索した結果として出力される画像である。
【００２６】
以上のような構成を備えた本実施形態にかかる画像登録装置１００及び画像検索装置２００の動作例を以下に説明する。
【００２７】
［画像の登録処理］
まず、画像登録装置１００が行う画像の登録処理について説明する。図３は画像の登録処理の手順を表すフローチャートである。ステップＳ３０１において、画像入力部１０２は、登録画像１０１を読み込む。ステップＳ３０２において、画像入力部１０２の輝度成分画像生成部１１１は、当該登録画像１０１から輝度成分を抽出して輝度成分画像を生成し、当該輝度成分画像を縮小画像生成部１０３に渡す。また、画像入力部１０２は、登録画像１０１を特徴量登録部１０６に渡す。
【００２８】
次に、ステップＳ３０３において、縮小画像生成部１０３は、画像入力部１０２から渡された輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成し、生成した縮小画像を局所特徴点抽出部１０４に渡す。ただし、倍率ｐおよび縮小画像の枚数ｎはあらかじめ定めておく。図４は縮小画像生成の例を示す図であり、倍率ｐが２の−１／４乗、縮小画像の枚数ｎが９の場合に縮小画像生成部１０３が生成する縮小画像の例を示している。図４において、４０１は画像入力部１０２から渡された輝度成分画像、４０２は当該輝度成分画像から倍率ｐに従って４回縮小された縮小画像、４０３は当該輝度成分画像から倍率ｐに従って８回縮小された縮小画像である。図４の例においては、縮小画像４０２は画像入力部１０２から渡された輝度成分画像が１／２に縮小された画像となり、縮小画像４０３は画像入力部１０２から渡された輝度成分画像が１／４に縮小された画像となる。なお、本実施形態における縮小画像は、線形補間による縮小方法により生成するものとするが、他の縮小方法が用いられてもよい。
【００２９】
次に、ステップＳ３０４において、局所特徴点抽出部１０４は、縮小画像生成部１０３から渡されたｎ枚の縮小画像それぞれにおいて、画像の回転があってもロバストに抽出されるような特徴点（回転不変の性質を持つ特徴点）を抽出する。そして、局所特徴点抽出部１０４は、抽出した当該回転不変の性質を持つ特徴点を局所特徴量算出部１０５に渡す。なお、本実施形態では、回転不変の性質を持つ特徴点の抽出方法としてHarris作用素（非特許文献１）を用いる。具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素および当該画素の８近傍にある画素（合計９画素）の画素値を調べる。そして、当該画素が局所極大（当該９画素の中で当該画素の画素値が最大になる）になる点を回転不変の性質を持つ特徴点として抽出する。このとき、当該画素が局所極大になったときでも、当該画素の値がしきい値以下の場合には回転不変の性質を持つ特徴量として抽出しないようにする。なお、回転不変の性質を持つ特徴点を抽出可能な方法であれば、本実施形態で用いた特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部１０４に適用可能である。
【００３０】
次に、局所特徴量算出部１０５では、局所特徴点抽出部１０４から渡された回転不変の性質を持つ特徴点それぞれについて、ステップＳ３０５により画像の回転があっても不変となる局所特徴量（回転不変の性質を持つ局所特徴量）を算出する。抽出した当該回転不変の性質を持つ局所特徴量は座標情報と関連付けされた上で、特徴量登録部１０６に渡される。ここで、本実施形態では、回転不変の性質を持つ特徴量の算出方法としてLocalJet（非特許文献２）およびそれらの導関数の組み合わせを用いる。具体的には、式（１）に示す回転不変の性質を持つ特徴量を算出する。
【数１】
【００３１】
ただし、式（１）右辺で用いている記号は以下に示す式（２）から式（７）で定義される。ここで、式（２）はガウス関数と画像との畳み込み演算である。
【数２】
【００３２】
なお、回転不変の性質を持つ特徴量を算出可能な方法であれば、本実施形態で用いた特徴量算出方法に限らず、どのような特徴量算出方法でも局所特徴量算出部１０５に適用可能である。
【００３３】
次に、ステップＳ３０６において、特徴量登録部１０６は、局所特徴量算出部１０５から渡された回転不変の性質を持つ特徴量と画像入力部１０２から渡された登録画像１０１とを関連付け、画像特徴データベース１０７に登録する。以上で画像登録装置１００による画像登録処理が終了する。
【００３４】
［画像の検索処理］
次に、画像検索装置２００による画像の検索処理を説明する。図５は、第１実施形態による画像の検索処理の手順を表すフローチャートである。
【００３５】
ステップＳ５０１において、画像入力部２０２は、クエリ画像２０１を読み込む。次に、ステップＳ５０２において、画像入力部２０２の閾値指定処理部２１１が、検索結果に期待するクエリ画像に対する拡大率の範囲、回転角度の範囲、平行移動の範囲のユーザ指定を受け付ける。但し、これら３項目を全て指定する必要は無く、特に制限を設けたい項目に対して範囲の指定を行えるようにすることが好ましい。
【００３６】
図８にこの幾何変換の制約を与えるユーザインターフェース（ＵＩ）の例を示す。チェックボックスにチェックを入れた項目に対してのみ制約を行い、例えば、各項目に対する制約はＡＮＤで制約が掛かるようにする。もちろん、論理式で指定できるようにする事も当然可能である。また、当然であるが、テキストボックスに入力された値の範囲に対する大小関係の不整合のチェックおよびユーザへの警告は当然行う。
【００３７】
以上のようにして指定された制約の値は、閾値指定処理部２１１により一時記憶される。
【００３８】
次に、ステップＳ５０３において、画像入力部２０２の輝度成分画像生成部２１２は、当該クエリ画像２０１から輝度成分を抽出して輝度成分画像を生成し、生成した輝度成分画像を縮小画像生成部２０３に渡す。
【００３９】
次に、ステップＳ５０４において、縮小画像生成部２０３は、画像入力部２０２から渡された輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成して当該縮小画像を局所特徴点抽出部２０４に渡す。ただし、倍率ｐおよび縮小画像の枚数ｎは前述の画像登録装置１００における画像の登録処理で用いた値と同じ値にする。
【００４０】
次に、ステップＳ５０５において、局所特徴点抽出部２０４は、縮小画像生成部２０３から渡されたｎ枚の縮小画像それぞれにおいて、画像の特徴点（回転不変の性質を持つ特徴点）を抽出する。抽出した当該回転不変の性質を持つ特徴点は局所特徴量算出部２０５に渡される。ここで本実施形態では、回転不変の性質を持つ特徴点の抽出方法として前述の画像の登録処理で用いた方法と同様に、Harris作用素を用いる。より具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素および当該画素の８近傍にある画素（合計９画素）の画素値を調べられる。そして、当該画素が局所極大（当該９画素の中で当該画素の画素値が最大になる）になる点が回転不変の性質を持つ特徴点として抽出される。このとき、当該画素が局所極大になったときでも、当該画素の値があらかじめ定められたしきい値以下の場合には回転不変の性質を持つ特徴量として抽出しないようにする。なお、回転不変の性質を持つ特徴点を抽出可能な方法であれば、本実施形態で用いた特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部２０４に適用可能である。
【００４１】
次に、ステップＳ５０６において、局所特徴量算出部２０５は、局所特徴点抽出部２０４から渡された回転不変の性質を持つ特徴点それぞれについて、画像の回転があっても不変となる局所特徴量（回転不変の性質を持つ局所特徴量）を算出する。抽出した当該回転不変の性質を持つ局所特徴量は座標情報と関連付けされた上で局所特徴量検定部２０６に渡される。ここで、回転不変の性質を持つ特徴量の算出方法は前述の画像の登録処理で用いた方法と同じ方法を使用する。すなわち、本実施形態では、LocalJetおよびそれらの導関数の組み合わせを用い、式（１）に示す回転不変の性質を持つ特徴量を算出する。局所特徴量検定部２０６は局所特徴量の変動を検定し、変動の少ない局所特徴量のみ合格とする。
【００４２】
次に、ステップＳ５０７において、特徴比較部２０７は、局所特徴量検定部２０６から渡された回転不変の性質を持つ特徴量と画像特徴データベース１０７に登録されている回転不変の性質を持つ特徴量とを比較する。この比較は、ステップＳ５０２で与えたアフィン変換係数の閾値を考慮しながら、画像特徴データベース１０７に登録されている登録画像ごとに実施される。そして、比較の結果として登録画像ごとにスコアが算出される。なお、スコアの算出方法については図６のフローチャートにより後述する。
【００４３】
次に、ステップＳ５０８において、特徴比較部２０７は、算出した当該類似度と当該類似度の算出元となった画像とを関連付けて検索結果リストを作成した後、当該スコアを降順にソートする。そして、特徴比較部２０７は、スコアが大きい画像と当該画像のスコアとをソート順に検索結果２０８として出力する。
【００４４】
［スコアの算出方法］
次に、本実施形態における（ステップＳ５０７における）スコアの算出方法を説明する。ここで、局所特徴点抽出部２０４及び局所特徴量算出部２０５から渡された、回転不変の性質を持つ特徴量をＶｓ、回転不変の性質を持つ特徴量に関連付けされている座標をＳ（x，y）とする。また、画像特徴データベース１０７に登録されている画像Ｒ上に存在する回転不変の性質を持つ特徴量をＶｑ、回転不変の性質を持つ特徴量に関連付けされている座標をＱ（x’，y’）とする。
【００４５】
以下、特徴比較部２０７における類似度（スコア）の算出手順を図６に示すフローチャートに従って説明する。
【００４６】
ステップＳ６０１において、特徴比較部２０７は、検索されるべき画像のクエリ画像に対する拡大率の範囲、回転角度の範囲、平行移動の範囲、の指定を画像入力部２０２（閾値指定処理部２１１）より受け取る。ステップＳ５０２で上述したように、これら３項目を全て指定する必要は無く、特に制限を設けたい項目に対して範囲の指定を行えるようにすることが好ましい。
【００４７】
次に、ステップＳ６０２により、最終投票数を表す変数VoteMaxを０に初期化する。次に、ステップＳ６０３により、ＶｑとＶｓとの特徴量間距離をすべての組み合わせについて計算し、最短距離対応点リストを作成する。このように、クエリ画像から選択された特徴点を、その特徴量に基づいて、登録されている比較先画像の特徴点と対応付けることにより、クエリ画像と比較先画像で対応する複数対の特徴点が抽出される。
【００４８】
この最短距離対応点を求める際に、先に、クエリ画像の各特徴点に対して記憶しているマハラノビスの距離を算出するための観測値をX=(X1,X2,…,Xp)'とし、母集団ｊの分散共分散行列Σjの逆行列Σj-1と平均（重心）μを用いて式（８）に基づいて距離ｄjを求める。そして、求めた距離と分散共分散逆行列を含む最短距離対応点リストを作成する。
【００４９】
ｄj2=(Ｘ−μj)'Σj-1(Ｘ−μj) …（８）
すなわち、計算した特徴量間距離がしきい値Ｔｖ以下となり、かつ、最短距離となるようなＶｑとＶｓとの組み合わせ（対応点）を抽出し、最短距離対応点リストに登録する。以後、本実施形態の説明では、最短距離対応点リストに登録された対応点について、当該対応点の回転不変の性質を持つ特徴量をそれぞれＶｑ（ｋ）とＶｓ（ｋ）と記載する。また、それらＶｑ（ｋ）とＶｓ（ｋ）に対応付けられている座標についてはそれぞれＱk（x’k，y’k）、Ｓk（xk，yk）などと添え字をつけて記載する。また、ステップＳ６０３で作成された最短距離対応点リストに登録された対応点の組数をｍ組とする。
【００５０】
次に、ステップＳ６０４により、類似度算出処理の反復カウント数を表す変数Countを０に初期化する。次に、ステップＳ６０５により、反復カウント数Countがあらかじめ定めた最大反復処理回数Ｒｎを超えていないか判定する。超えている場合はステップＳ６２１により最終投票数VoteMaxを出力して処理を終了する。超えていない場合は、ステップＳ６０６に移る。Ｓ６２１で総合類似度算出処理に関する詳細説明は、後で行う。
【００５１】
ステップＳ６０６では、投票数を表す変数Voteを０に初期化する。次に、ステップＳ６０７において、複数対の特徴点から、少なくとも２対の特徴点が取得される。本実施形態では、ステップＳ６０３で生成された最短距離対応点リストから対応点の組の座標をランダムに２組抽出する。本実施形態では、これらの座標をＱ1（ｘ’1，ｙ’1）、Ｓ1（ｘ1，ｙ1）およびＱ2（ｘ’2，ｙ’2）、Ｓ2（ｘ2，ｙ2）と記載する。
【００５２】
次に、ステップＳ６０８において、ステップＳ６０７で抽出した２対の特徴点の各対の座標を、クエリ画像と比較先画像とで一致させるように、座標変換処理のための座標変換係数が決定される。本実施形態では、座標変換処理として、アフィン変換を用いる。即ち、ステップＳ６０７により、抽出したＱ1（ｘ’1，ｙ’1）、Ｓ1（ｘ1，ｙ1）およびＱ2（ｘ’2，ｙ’2）、Ｓ2（ｘ2，ｙ2）が式（９）に示す変換を満たしていると仮定し、式（９）中の変数ａ〜ｆを求める。ただし、図６に示すフローチャート中のステップＳ６０８では、変数ａ〜ｄで構成される行列をＭ、変数ｅ〜ｆで構成される行列をＴで示している。
【数３】
【００５３】
ここで、本実施形態では、簡単のため回転変換、相似変換および平行移動の組み合わせだけを考える。このとき、式（９）は式（１０）のように書き換えられる。
【数４】
【００５４】
このとき、変数ａ、ｂ、ｅ、ｆはｘ’1、ｙ’1、ｘ1、ｙ1、ｘ’2、ｙ’2、ｘ2、ｙ2を使って式（１１）から式（１４）で表される。
【数５】
【００５５】
図７に式（９）におけるアフィン変換係数と、幾何変換の関係を示す。ここで、式（１１）から式（１４）にて得たａ，ｂ，ｅ，ｆと、図８の表において敷き（１０）の導出の際に設けたｂ＝−ｃ、ｄ＝ａの制約を用いて考える。
【００５６】
回転行列に拡大・縮小行列を掛けても、単に回転行列をＳ倍したものになるだけである。
【００５７】
従って、ｃｏｓ２Θ ＋ ｓｉｎ２Θ ＝ １の制約を用い、
拡大率 Ｓ＝sqrt(ａ２＋ｂ２) …（１５）
で拡大率が求まる。従って、
回転角度 Θ＝ ｃｏｓ-1（ａ/Ｓ） …（１６）
となる。もちろん、
平行移動ベクトル Ｔ＝（ｅ，ｆ） …（１７）
となる。
【００５８】
そしてステップＳ６０９において、特徴比較部２０７は、上記のようにして決定された座標変換係数（アフィン変換係数）を用いた座標変換処理（アフィン変換処理）による座標の変換量が予め指定された制約条件を満足するか否かを判定する。即ち、ステップＳ６０１であらかじめ与えられ一時記憶しておいた拡大・縮小率の範囲、回転角度の範囲、平行移動ベクトルの範囲と、上記式（１５）、式（１６）および式（１７）で得たＳ、ΘおよびＴとをステップＳ６０９で比較する。この比較の結果、これらの条件を全て満たす場合にのみ処理はステップＳ６１０に進み、一つでも満たさないものがある場合にはステップＳ６０５で別の対応点の選択を行う事になる。
【００５９】
もちろん、範囲を与えなかった項目に関しては考慮する必要は無く、例えば、拡大率の範囲のみが指定されていれば、その範囲に式（１５）で得たＳが入っているかどうかだけを判断すれば良い。
【００６０】
次に、ステップＳ６１０では、ステップ６０７において当該最短距離対応点リストからランダムに抽出された２組の点以外の点を選択するために、対応点選択変数ｋを３に初期化する。次に、ステップ６１１により、対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていないか判定する。超えている場合はステップＳ６１８に処理を移すが、これについては後述する。ステップＳ６１１における判定で対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていない場合は、処理はステップＳ６１２に進む。
【００６１】
ステップＳ６１２において、特徴比較部２０７は、ステップ６０７において当該最短距離対応点リストからランダムに抽出された２組の点Ｓ1（ｘ1，ｙ1）およびＳ2（ｘ2，ｙ2）以外の点を、当該最短距離対応点リストから抽出する。本実施形態では、抽出された点をＳk（ｘk，ｙk）と記載する。
【００６２】
次に、ステップＳ６１３において、特徴比較部２０７は、Ｓk（ｘk，ｙk）が式（９）を使って移される座標Ｓ’（ｘ’k，ｙ’k）を求める。
【００６３】
その後、ステップＳ６１４において、特徴比較部２０７は、座標Ｓ’（ｘ’k，ｙ’k）と座標Ｑk（ｘ’k，ｙ’k）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離がしきい値Ｔｄ以下であるかどうかを判定する。当該ユークリッド距離がしきい値Ｔｄ以下の場合には、特徴比較部２０７は、ステップＳ６１５において、Voteに対する対応点の対Ｓ’ｋ，Ｑｋを記憶する。そして、更にステップＳ６１６において、投票数Voteをインクリメントし、ステップＳ６１７に処理を移す。当該ユークリッド距離がしきい値Ｔｄより大きい場合には、何もせずにステップＳ６１７に処理を移す。
【００６４】
ステップＳ６１７では、対応点選択変数ｋをインクリメントし、処理はステップＳ６１１に戻る。
【００６５】
次に、ステップ６１１において対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていた場合の処理であるステップＳ６１８を説明する。特徴比較部２０７は、ステップ６１８において、投票数Voteの値と最終投票数VoteMaxの値とを比較し、投票数Voteの値が最終投票数VoteMaxの値よりも大きい場合はステップＳ６１９の処理を実行する。ステップＳ６１９において、特徴比較部２０７は、最終投票数VoteMaxの値を投票数Voteの値で置き換えた後、ステップＳ６２０でCountをインクリメントし、ステップＳ６０５に処理を戻す。また、投票数Voteの値と最終投票数VoteMaxの値とを比較し、投票数Voteの値が最終投票数VoteMaxの値以下の場合は、ステップＳ６１９をスキップして、ステップＳ６２０でCountをインクリメントした後、ステップＳ６０５に処理を戻す。
【００６６】
以上のように、第１実施形態によれば、抽出された２対の特徴点に基づいて決定された座標変換係数を用いた座標変換処理の変換量が予め指定された制約条件を満足する可動化が判定される。そして、満足すると判定された場合にのみ、クエリ画像と比較先画像の類似を判定するべく、一方の画像の特徴点群の座標を当該座標変換係数を用いた座標変換処理により変換し、他方の画像の対応する特徴点群の座標と比較する処理が実行される。したがって、本実施形態にかかる画像検索装置は、クエリ画像から算出された回転不変の性質を持つ特徴量の変動を検定して変動の大きい回転不変の性質を持つ特徴量を検索時に使わないように構成されている。このため、無駄な座標変換処理を行うことなく、検索精度の低下を抑制することが可能になる。したがって、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事が出来るという利点が得られる。
【００６７】
なお、クエリ画像と比較先画像との拡大・縮小率は、複数対の特徴点（第１実施形態では２対の特徴点）について、クエリ画像における特徴点間の距離と比較先画像における特徴点間の距離との比率から求めることも可能である。そして、このようにして求めた拡大・縮小の率があらかじめ指定された制約条件を満足しない場合は、当該複数対の特徴点に関してステップＳ６０７、Ｓ６０８の処理を禁止して、次の新たな特徴点の対を取得するようにしてもよい。この場合、座標変換係数を算出する処理（ステップＳ６０８）から座標変換後の座標値を比較する処理（ステップＳ６１７）の実行が禁止されることになる。同様に、特徴点の各対を結ぶ直線のなす角から回転角度を求めることもできる。このような構成は、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事が出来るという本実施形態の利点に更に寄与するものである。
【００６８】
＜第２実施形態＞
第１実施形態におけるスコア算出方法の説明では、回転変換、相似変換および平行移動の組み合わせを説明したが、適用可能な幾何学変換はこれらに限られるものではない。上記以外の幾何学変換についても、図６のフローチャートのステップＳ６０８においてそれぞれに応じた変換行列を求めることにより、対応可能である。たとえば、アフィン変換の場合は、まず、ステップＳ６０７でランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ６０８において式（９）ではなく式（８）を使うこととし、ステップＳ６０６で選択した３組の対応点（合計６点）を使って変数ａ〜ｆを求めればよい。
【００６９】
図９に幾何変換の制約を与えるための、閾値指定処理部２１１によって提供されるＵＩの例を示す。
【００７０】
まず、変形を伴う拡大・縮小である場合には
ａ≠ｄ or ｂ≠（−ｃ） …（１８）
となるので、この条件を参照することにより変形を検索しないようにする事が可能である。即ち、変形が有るものを検索しない制約で検索を行う場合には、上記式（１８）を満たす場合に、次の対応点の処理ステップＳ６０５に移るようにすればよい。
【００７１】
他方、上記、ａ，ｂ，ｃ，ｄを式（１５）により求めたＳでわった結果が−１，０，０，１になるかで鏡像が検出できるので、鏡像画像の検索を制約に加えることも可能である。
【００７２】
この「鏡像画像を検索する」のチェックと、「変形を検索しない」のチェックはどちらか片方しかチェックできないように制御する必要がある。
【００７３】
尚、回転変換、相似変換および平行移動に関しては、第１実施形態と同様の方法で範囲の制約を掛ける事が可能である。
【００７４】
更に、回転に関しては、画像中の文字画像の文字認識（ＯＣＲ）結果に基づく方向検知処理を行い、方向補正を行った上で指定の回転角度範囲の画像を検索する事も当然考えられる。また、上記各実施形態では、クエリ画像の特徴点をアフィン変換し、アフィン変換後の座標と比較先画像の特徴点の座標とを比較したが、比較先画像の特徴点をアフィン変換し、アフィン変換後の座標とクエリ画像の特徴点の座標とを比較してもよい。
【００７５】
以上のように、第１及び第２実施形態によれば、検索に対する絞り込み処理を、クエリからの特徴点の選択から幾何変換までの処理に最適に関連つける事が出来る。そのため、余計な幾何変換処理を行わずに済み、後処理で絞込条件に適うかの確認処理を行う必要も無くなる。
【００７６】
従って、処理負荷を多くする事無くクエリからの特徴点の選択の反復回数を大きい数にする事が出来、ひいては、検索の安定性や再現性に寄与する事が可能となる。
【００７７】
＜他の実施形態＞
以上、実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【００７８】
尚、本発明は、ソフトウェアのプログラムをシステム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによって前述した実施形態の機能が達成される場合を含む。この場合、供給されるプログラムは実施形態で図に示したフローチャートに対応したコンピュータプログラムである。
【００７９】
また、コンピュータが、コンピュータ読み取り可能な記憶媒体から格納されているプログラムを読み出し、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどとの協働で実施形態の機能が実現されてもよい。この場合、ＯＳなどが、実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される。
【特許請求の範囲】
【請求項１】
入力されたクエリ画像と登録されている比較先画像との類似を判定して、該クエリ画像に類似する画像を検索する画像検索装置であって、
前記クエリ画像から選択された特徴点と前記比較先画像の特徴点とをそれら特徴点の特徴量に基づいて対応付けることにより、前記クエリ画像と前記比較先画像の２つの画像において対応する複数対の特徴点を抽出する抽出手段と、
前記複数対の特徴点から、少なくとも２対の特徴点を取得する取得手段と、
前記少なくとも２対の特徴点の各対に関して、前記２つの画像のうちの一方の画像の特徴点の座標が他方の画像の特徴点の座標と一致するように変換するための座標変換係数を決定する決定手段と、
前記決定手段で決定された前記座標変換係数を用いた座標変換処理による座標の変換量があらかじめ指定された制約条件を満足するか否かを判定する判定手段と、
前記判定手段で満足すると判定された場合にのみ、前記複数対の特徴点に関して、前記一方の画像の特徴点の座標を前記座標変換係数を用いた座標変換処理により変換し、変換後の特徴点の座標と前記他方の画像の対応する特徴点の座標とを前記２つの画像の類似を判定するために比較する比較手段とを備えることを特徴とする画像検索装置。
【請求項２】
前記抽出手段は、前記クエリ画像と前記比較先画像とから、回転不変の性質を持つ複数の特徴点を抽出し、前記複数の特徴点の各々の特徴量を算出し、算出された特徴量に基づいて前記比較先画像の特徴点と対応付けることにより前記複数対の特徴点を抽出することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記座標変換はアフィン変換であり、
前記座標変換係数はアフィン変換係数であり、
前記制約条件は、アフィン変換による拡大縮小の率、回転角度の大きさ、平行移動の量、変形の有無、鏡像変換の有無の少なくとも何れかの変換量に関する制約条件であることを特徴とする請求項１に記載の画像検索装置。
【請求項４】
前記取得手段で取得した前記少なくとも２対の特徴点について、前記クエリ画像における特徴点間の距離と前記比較先画像における特徴点間の距離との比率から拡大縮小の率を求め、当該拡大縮小の率があらかじめ指定された制約条件を満足しない場合は、前記複数対の特徴点について前記取得手段、前記決定手段、前記比較手段による処理の実行を禁止する禁止手段を更に備えることを特徴とする請求項１乃至３のいずれか１項に記載の画像検索装置。
【請求項５】
前記制約条件をユーザに指定させるためのユーザインターフェースを提供する手段を更に備えることを特徴とする請求項１乃至４のいずれか１項に記載の画像検索装置。
【請求項６】
入力されたクエリ画像と登録されている比較先画像との類似を判定して、該クエリ画像に類似する画像を検索する画像検索方法であって、
前記クエリ画像から選択された特徴点と前記比較先画像の特徴点とをそれら特徴点の特徴量に基づいて対応付けることにより、前記クエリ画像と前記比較先画像の２つの画像において対応する複数対の特徴点を抽出する抽出工程と、
前記複数対の特徴点から、少なくとも２対の特徴点を取得する取得工程と、
前記少なくとも２対の特徴点の各対に関して、前記２つの画像のうちの一方の画像の特徴点の座標が他方の画像の特徴点の座標と一致するように変換するための座標変換係数を決定する決定工程と、
前記決定工程で決定された前記座標変換係数を用いた座標変換処理による座標の変換量があらかじめ指定された制約条件を満足するか否かを判定する判定工程と、
前記判定工程で満足すると判定された場合にのみ、前記複数対の特徴点に関して、前記一方の画像の特徴点の座標を前記座標変換係数を用いた座標変換処理により変換し、変換後の特徴点の座標と前記他方の画像の対応する特徴点の座標とを前記２つの画像の類似を判定するために比較する比較工程とを有することを特徴とする画像検索方法。
【請求項７】
前記抽出工程は、前記クエリ画像と前記比較先画像とから、回転不変の性質を持つ複数の特徴点を抽出し、前記複数の特徴点の各々の特徴量を算出し、算出された特徴量に基づいて前記比較先画像の特徴点と対応付けることにより前記複数対の特徴点を抽出することを特徴とする請求項６に記載の画像検索方法。
【請求項８】
前記座標変換はアフィン変換であり、
前記座標変換係数はアフィン変換係数であり、
前記制約条件は、アフィン変換による拡大縮小の率、回転角度の大きさ、平行移動の量、変形の有無、鏡像変換の有無の少なくとも何れかの変換量に関する制約条件であることを特徴とする請求項６に記載の画像検索方法。
【請求項９】
前記取得工程で取得した前記少なくとも２対の特徴点について、前記クエリ画像における特徴点間の距離と前記比較先画像における特徴点間の距離との比率から拡大縮小の率を求め、当該拡大縮小の率があらかじめ指定された制約条件を満足しない場合は、前記複数対の特徴点について前記取得工程、前記決定工程、前記比較工程による処理の実行を禁止する禁止工程を更に有することを特徴とする請求項６乃至８のいずれか１項に記載の画像検索方法。
【請求項１０】
前記制約条件をユーザに指定させるためのユーザインターフェースを提供する工程を更に有することを特徴とする請求項６乃至９のいずれか１項に記載の画像検索方法。
【請求項１１】
請求項６乃至１０のいずれか１項に記載の画像検索方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項１２】
請求項６乃至１０のいずれか１項に記載の画像検索方法をコンピュータに実行させるためのコンピュータプログラムを格納したコンピュータ読み取り可能な記憶媒体。
【請求項１】
入力されたクエリ画像と登録されている比較先画像との類似を判定して、該クエリ画像に類似する画像を検索する画像検索装置であって、
前記クエリ画像から選択された特徴点と前記比較先画像の特徴点とをそれら特徴点の特徴量に基づいて対応付けることにより、前記クエリ画像と前記比較先画像の２つの画像において対応する複数対の特徴点を抽出する抽出手段と、
前記複数対の特徴点から、少なくとも２対の特徴点を取得する取得手段と、
前記少なくとも２対の特徴点の各対に関して、前記２つの画像のうちの一方の画像の特徴点の座標が他方の画像の特徴点の座標と一致するように変換するための座標変換係数を決定する決定手段と、
前記決定手段で決定された前記座標変換係数を用いた座標変換処理による座標の変換量があらかじめ指定された制約条件を満足するか否かを判定する判定手段と、
前記判定手段で満足すると判定された場合にのみ、前記複数対の特徴点に関して、前記一方の画像の特徴点の座標を前記座標変換係数を用いた座標変換処理により変換し、変換後の特徴点の座標と前記他方の画像の対応する特徴点の座標とを前記２つの画像の類似を判定するために比較する比較手段とを備えることを特徴とする画像検索装置。
【請求項２】
前記抽出手段は、前記クエリ画像と前記比較先画像とから、回転不変の性質を持つ複数の特徴点を抽出し、前記複数の特徴点の各々の特徴量を算出し、算出された特徴量に基づいて前記比較先画像の特徴点と対応付けることにより前記複数対の特徴点を抽出することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記座標変換はアフィン変換であり、
前記座標変換係数はアフィン変換係数であり、
前記制約条件は、アフィン変換による拡大縮小の率、回転角度の大きさ、平行移動の量、変形の有無、鏡像変換の有無の少なくとも何れかの変換量に関する制約条件であることを特徴とする請求項１に記載の画像検索装置。
【請求項４】
前記取得手段で取得した前記少なくとも２対の特徴点について、前記クエリ画像における特徴点間の距離と前記比較先画像における特徴点間の距離との比率から拡大縮小の率を求め、当該拡大縮小の率があらかじめ指定された制約条件を満足しない場合は、前記複数対の特徴点について前記取得手段、前記決定手段、前記比較手段による処理の実行を禁止する禁止手段を更に備えることを特徴とする請求項１乃至３のいずれか１項に記載の画像検索装置。
【請求項５】
前記制約条件をユーザに指定させるためのユーザインターフェースを提供する手段を更に備えることを特徴とする請求項１乃至４のいずれか１項に記載の画像検索装置。
【請求項６】
入力されたクエリ画像と登録されている比較先画像との類似を判定して、該クエリ画像に類似する画像を検索する画像検索方法であって、
前記クエリ画像から選択された特徴点と前記比較先画像の特徴点とをそれら特徴点の特徴量に基づいて対応付けることにより、前記クエリ画像と前記比較先画像の２つの画像において対応する複数対の特徴点を抽出する抽出工程と、
前記複数対の特徴点から、少なくとも２対の特徴点を取得する取得工程と、
前記少なくとも２対の特徴点の各対に関して、前記２つの画像のうちの一方の画像の特徴点の座標が他方の画像の特徴点の座標と一致するように変換するための座標変換係数を決定する決定工程と、
前記決定工程で決定された前記座標変換係数を用いた座標変換処理による座標の変換量があらかじめ指定された制約条件を満足するか否かを判定する判定工程と、
前記判定工程で満足すると判定された場合にのみ、前記複数対の特徴点に関して、前記一方の画像の特徴点の座標を前記座標変換係数を用いた座標変換処理により変換し、変換後の特徴点の座標と前記他方の画像の対応する特徴点の座標とを前記２つの画像の類似を判定するために比較する比較工程とを有することを特徴とする画像検索方法。
【請求項７】
前記抽出工程は、前記クエリ画像と前記比較先画像とから、回転不変の性質を持つ複数の特徴点を抽出し、前記複数の特徴点の各々の特徴量を算出し、算出された特徴量に基づいて前記比較先画像の特徴点と対応付けることにより前記複数対の特徴点を抽出することを特徴とする請求項６に記載の画像検索方法。
【請求項８】
前記座標変換はアフィン変換であり、
前記座標変換係数はアフィン変換係数であり、
前記制約条件は、アフィン変換による拡大縮小の率、回転角度の大きさ、平行移動の量、変形の有無、鏡像変換の有無の少なくとも何れかの変換量に関する制約条件であることを特徴とする請求項６に記載の画像検索方法。
【請求項９】
前記取得工程で取得した前記少なくとも２対の特徴点について、前記クエリ画像における特徴点間の距離と前記比較先画像における特徴点間の距離との比率から拡大縮小の率を求め、当該拡大縮小の率があらかじめ指定された制約条件を満足しない場合は、前記複数対の特徴点について前記取得工程、前記決定工程、前記比較工程による処理の実行を禁止する禁止工程を更に有することを特徴とする請求項６乃至８のいずれか１項に記載の画像検索方法。
【請求項１０】
前記制約条件をユーザに指定させるためのユーザインターフェースを提供する工程を更に有することを特徴とする請求項６乃至９のいずれか１項に記載の画像検索方法。
【請求項１１】
請求項６乃至１０のいずれか１項に記載の画像検索方法をコンピュータに実行させるためのコンピュータプログラム。
【請求項１２】
請求項６乃至１０のいずれか１項に記載の画像検索方法をコンピュータに実行させるためのコンピュータプログラムを格納したコンピュータ読み取り可能な記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１０−２７２０９１（Ｐ２０１０−２７２０９１Ａ）
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願番号】特願２００９−１２５８４４（Ｐ２００９−１２５８４４）
【出願日】平成２１年５月２５日（２００９．５．２５）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願日】平成２１年５月２５日（２００９．５．２５）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]