画像検索装置およびその方法
【課題】幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にし、無為に対応点候補個数を増やすことなく検索することを可能にする。
【解決手段】画像検索装置は、クエリ画像より互いに対応する特徴点の対を取得し、取得された特徴点の対に基づいて対称性を有する部分画像を抽出し、部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを、当該部分画像における画像特徴の傾向に基づいて第１領域と第２領域に決定する。クエリ画像と比較先画像の類似性の判定においては、両画像の第１領域に決定されている部分領域から抽出された特徴点の対に基づいて座標変換処理のための座標変換係数が設定され、当該両画像の第１領域以外の領域を含む領域から抽出された特徴点の対に対して上記座標変換係数を用いた座標変換処理を適用して、座標変換処理後の特徴点の対の座標が比較される。
【解決手段】画像検索装置は、クエリ画像より互いに対応する特徴点の対を取得し、取得された特徴点の対に基づいて対称性を有する部分画像を抽出し、部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを、当該部分画像における画像特徴の傾向に基づいて第１領域と第２領域に決定する。クエリ画像と比較先画像の類似性の判定においては、両画像の第１領域に決定されている部分領域から抽出された特徴点の対に基づいて座標変換処理のための座標変換係数が設定され、当該両画像の第１領域以外の領域を含む領域から抽出された特徴点の対に対して上記座標変換係数を用いた座標変換処理を適用して、座標変換処理後の特徴点の対の座標が比較される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像中の特徴点の類似度に基づく画像検索技術に関するものである。
【背景技術】
【０００２】
一般に、画像の回転に対応した画像検索は、クエリ画像を回転して特徴量を求める或いは特徴量を回転変換したものを用いることにより行われていた。
【０００３】
従来から提案されている画像中の特徴点の類似度に基づく画像検索技術として、特許文献１が挙げられる。特許文献１では、局所的な特徴同士の比較に基づく画像検索において、クエリ画像から無作為に選ばれた特徴点の対に類似する特徴点を登録画像中から求める。そして、対の特徴点の位置関係に基づいてクエリ画像と登録画像の間の幾何学変換関数を求め、対以外の特徴点が幾何学変換関数によって変換された場所に、登録画像の対応する特徴点が存在しているものをカウントし、類似性を判定していた。
（以下において、非特許文献１，２は「発明を実施するための最良の形態」の欄において参照されている文献である。）
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−０６５３９９号公報
【非特許文献】
【０００５】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記処理では、局所的な特徴同士の比較に基づく画像検索において、対称な（左右／上下対称）部分画像を有する画像の検索に関して適切に検索を行えなくなる場合があった。即ち、対称な部分画像において、図７で後述するように、類似する特徴点の組み合わせを誤抽出してしまい（類似する特徴点の対が対称領域をまたいでしまう）、最悪の場合正しい組み合わせに出くわさないで検索が失敗する事があった。このような事態の発生を防ぐために、対応点候補個数を増やし、１０００程度にして正しいものと出くわす確率を上げる方法もあるが、対応点候補個数による検索速度の低下を招いてしまう。
【０００７】
本発明は上記の課題に鑑みてなされたものであり、幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にし、無為に対応点候補個数を増やさないで検索することを可能にすることを目的とする。
【課題を解決するための手段】
【０００８】
上記の目的を達成するための本発明の一態様による画像検索装置は以下の構成を備える。即ち、
入力されたクエリ画像と類似する画像を登録されている画像から検索する画像検索装置であって、
前記クエリ画像において、特徴点の特徴量に基づいて互いに対応する特徴点の対を取得し、取得された特徴点の対に基づいて対称性を有する部分画像を抽出する抽出手段と、
前記部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを、当該部分画像における画像特徴の傾向に基づいて第１領域と第２領域に決定する決定手段と、
前記クエリ画像と登録されている比較先画像について、両画像の前記第１領域に決定されている部分領域に存在する特徴点から特徴量に基づいて少なくとも２組の対応する特徴点の対を抽出し、抽出した各対の特徴点の座標が一致するように前記両画像のうちの一方の画像の特徴点を変換するための座標変換係数を設定する設定手段と、
前記両画像の類似を判定するために、前記両画像に存在する特徴点から特徴量に基づいて互いに対応する特徴点の対を抽出し、前記一方の画像について抽出された特徴点の座標を前記座標変換係数を用いた座標変換処理によって変換し、変換後の特徴点の座標と前記両画像のうちの他方の画像における特徴点の座標とを比較する比較手段とを備える。
【発明の効果】
【０００９】
本発明によれば、幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にすることができ、無為に対応点候補個数を増やさないで検索することが可能となる。
【図面の簡単な説明】
【００１０】
【図１】実施形態による画像登録装置の構成例を示すブロック図。
【図２】実施形態による画像検索装置の構成例を示すブロック図。
【図３】実施形態による画像の登録処理を表すフローチャート。
【図４】局所特徴量の登録に関する処理を表すフローチャート。
【図５】縮小画像生成の例を示す図。
【図６】実施形態による画像の検索処理を表すフローチャート。
【図７】対称性の有る画像を検索する場合の弊害の一例を説明する図。
【図８】実施形態による、対称性を有する部分画像を抽出するための処理を示すフローチャート。
【図９】ハフ変換の原理を説明する図。
【図１０】対称性を有する部分画像が存在する場合の、対称性を有する部分画像の甲・乙の決定処理を示すフローチャート。
【図１１】対称性を有する画像と、甲・乙のラベル付けを説明する図。
【図１２】対称性を有する画像と、甲・乙のラベル付けを説明する図。
【図１３】対称性を有する画像と、甲・乙のラベル付けを説明する図。
【図１４】実施形態による、局所特徴量の比較処理を説明するフローチャート。
【図１５】クエリ画像が対称性を有する部分画像を含む場合の類似度判定処理を示すフローチャート。
【図１６】クエリ画像が対称性を有する部分画像を含まない場合の類似度判定処理を示すフローチャート。
【図１７】距離を類似度へ変換するルックアップテーブルの例を示す図。
【図１８】第２実施形態による、画像の対称性の有無を判定する処理を示すフローチャート。
【発明を実施するための形態】
【００１１】
まず、本実施形態の概要を説明する。本実施形態の画像検索装置におけるクエリ画像と比較先画像との類似性の判定においては、回転不変の性質をもつ特徴点および回転不変特徴量（スケール内の特徴量）が用いられる。そして、クエリ画像と比較先画像との間で対応する少なくとも２対の特徴点の座標に基づいて座標変換処理のための座標変換係数を決定する。本実施形態ではアフィン変換を採用しており、上記処理によりアフィン変換関数が決定される。そして、クエリ画像或いは比較先画像の一方の画像における特徴点座標をアフィン変換して、変換後の座標と他方の画像における特徴点の座標とを比較する比較処理により両画像の類似性を判定する。
【００１２】
本実施形態の登録処理時においては、登録画像中の特徴点抽出結果に基づき特徴点が対称となる部分領域、即ち対称性を有する部分領域に関して、対称軸で分割された領域に画像特徴の傾向に基づいて第１領域と第２領域に決定する。本実施形態では、一方の領域を甲に、他方の領域を乙にをラベル付けする。各特徴点は、対称画像領域中に有ることおよび甲或いは乙に属する事を示す情報と共に画像特徴データベースに登録される。他方、登録画像中の対称領域以外の特徴点は、対称領域中に無いことを示す情報と共に画像特徴データベースに登録される。
【００１３】
本実施形態の検索処理時においては、クエリ画像から抽出された特徴点に基づいて対称性を有する部分領域の有無を判定する。そして、対称性を有する部分領域が有る場合には、対称領域の対である甲乙のうち、甲が設定された領域から少なくとも２つの特徴点を選択して、比較先画像中の甲が設定された領域から対応する特徴点点を求める。そして、これら特徴点を用いて上記アフィン変換関数が決定される。これにより、対称図形の同じ側から対応する特徴点を推定する事が可能となる。
【００１４】
こうして決定されたアフィン変換関数により、特徴点の座標変換処理を行い、上記比較処理が実行される。ここで対象となる特徴点は、クエリ画像と比較先画像の甲に設定された領域以外の領域を含める。例えば、乙に設定された領域、対称性を有する領域以外の非対称領域を含める。
【００１５】
以上のように、クエリ画像と比較先画像の甲に設定された領域からアフィン変換関数を決定するための特徴点を選ぶ事により、対応する正しい対称領域から特徴点の対が選択され、対称性による弊害を軽減できる。即ち、幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にすることができる。
【００１６】
もちろん、クエリ画像中の特徴点抽出結果に基づき特徴点が対称となる部分領域の有無を求め、対称領域（対称性を有する部分画像）が無い場合には、通常の比較処理を行う。
【００１７】
以下の実施形態において、上述した対称領域の検出は、画像中の類似する特徴点ペアの中点群が直線的に並ぶのを確認し、この直線を対称軸とし、当該対称軸の近傍に中点を持つ特徴点ペアを求めることで実現される。
【００１８】
例えば、画像中の類似する特徴点ペアの中点群に対してハフ変換を行う事により対称軸を求め、対称軸近傍に中点を持つ特徴点ペアを求める事で、より厳密な対称領域の検出を実現できる。
【００１９】
尚、対称領域がある場合の領域甲乙の決定においては、画像特徴の偏りを用いることにより一意に甲乙を決定する事が可能となる。このような画像特徴の例としては、特徴点の個数あるいは領域中の画素濃淡平均など、領域固有の画像特徴を用いると良い。そして、例えば、その結果を用いて、対称性を有する部分画像を画像特徴の偏よりの大きい方或いは小さい方が上或いは下に来る様に回転したときに左側或いは右側の半分を甲に決定するというようなルールを定めれば良い。
【００２０】
他方、対称な領域がある画像の場合に、「対称領域あり」というメタデータを画像に付与し、クエリ画像が対称な画像の場合に、対称領域のある画像のみを検索対象とする絞込検索を行う事が出来る。
【００２１】
＜第１実施形態＞
図１は本発明の第１実施形態における画像登録装置の構成例を示すブロック図である。図１において、１００は画像登録装置であり、画像入力部１０２、縮小画像生成部１０３、局所特徴点抽出部１０４、局所特徴量算出部１０５、対称領域抽出部１０８、特徴量登録部１０６を備える。１０１は登録画像であり、画像登録装置１００によって後述する画像特徴データベースに登録される画像である。１０７は画像特徴データベースであり、画像登録装置１００により登録画像１０１から抽出された画像特徴が登録される。
【００２２】
図２は本発明の第１実施形態における画像検索装置の構成例を示すブロック図である。図２において、２００は画像検索装置であり、画像入力部２０２、縮小画像生成部２０３、局所特徴点抽出部２０４、局所特徴量算出部２０５、対称領域抽出部２０６、特徴比較部２０７を備える。２０１はクエリ画像である。画像検索装置２００は、画像特徴データベース１０７から当該クエリ画像２０１に類似した画像を検索する。２０８は検索結果画像であり、画像検索装置２００が画像特徴データベース１０７を検索した結果として出力される画像である。
【００２３】
以上のような構成を備えた本実施形態にかかる画像登録装置１００及び画像検索装置２００の動作例を以下に説明する。
【００２４】
［画像の登録処理］
まず、画像登録装置１００が行う画像の登録処理について説明する。図３は画像の登録処理の手順を表すフローチャートである。ステップＳ３０１において、画像入力部１０２は、登録画像１０１を読み込む。ステップＳ３０２において、画像入力部１０２の輝度成分画像生成部１１１は、当該登録画像１０１から輝度成分を抽出して輝度成分画像を生成し、当該輝度成分画像を縮小画像生成部１０３に渡す。また、画像入力部１０２は、登録画像１０１を特徴量登録部１０６に渡す。
【００２５】
次に、ステップＳ３０３において、縮小画像生成部１０３は、画像入力部１０２から渡された輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成し、生成した縮小画像を局所特徴点抽出部１０４に渡す。ただし、倍率ｐおよび縮小画像の枚数ｎはあらかじめ定めておく。図５は縮小画像生成の例を示す図であり、倍率ｐが２の−１／４乗、縮小画像の枚数ｎが９の場合に縮小画像生成部１０３が生成する縮小画像の例を示している。図５において、５０１は画像入力部１０２から渡された輝度成分画像、５０２は当該輝度成分画像から倍率ｐに従って４回縮小された縮小画像、５０３は当該輝度成分画像から倍率ｐに従って８回縮小された縮小画像である。図５の例においては、縮小画像５０２は画像入力部１０２から渡された輝度成分画像が１／２に縮小された画像となり、縮小画像５０３は画像入力部１０２から渡された輝度成分画像が１／４に縮小された画像となる。なお、本実施形態における縮小画像は、線形補間による縮小方法により生成するものとするが、他の縮小方法が用いられてもよい。
【００２６】
次に、ステップＳ３０４において、局所特徴点抽出部１０４は、縮小画像生成部１０３から渡されたｎ枚の縮小画像それぞれにおいて、画像の回転があってもロバストに抽出されるような特徴点（回転不変の性質を持つ特徴点）を抽出する。そして、局所特徴点抽出部１０４は、抽出した当該回転不変の性質を持つ特徴点を局所特徴量算出部１０５に渡す。なお、本実施形態では、回転不変の性質を持つ特徴点の抽出方法としてHarris作用素（非特許文献１）を用いる。具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素および当該画素の８近傍にある画素（合計９画素）の画素値を調べる。そして、当該画素が局所極大（当該９画素の中で当該画素の画素値が最大になる）になる点を回転不変の性質を持つ特徴点として抽出する。このとき、当該画素が局所極大になったときでも、当該画素の値がしきい値以下の場合には回転不変の性質を持つ特徴量として抽出しないようにする。なお、回転不変の性質を持つ特徴点を抽出可能な方法であれば、本実施形態で用いた特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部１０４に適用可能である。
【００２７】
次に、局所特徴量算出部１０５では、局所特徴点抽出部１０４から渡された回転不変の性質を持つ特徴点それぞれについて、ステップＳ３０５により画像の回転があっても不変となる局所特徴量（回転不変の性質を持つ局所特徴量）を算出する。抽出した当該回転不変の性質を持つ局所特徴量は座標情報と関連付けされた上で、特徴量登録部１０６に渡される。ここで、本実施形態では、回転不変の性質を持つ特徴量の算出方法としてLocalJet（非特許文献２）およびそれらの導関数の組み合わせを用いる。具体的には、式（１）に示す回転不変の性質を持つ特徴量を算出する。
【数１】
【００２８】
ただし、式（１）右辺で用いている記号は以下に示す式（２）から式（７）で定義される。ここで、式（２）はガウス関数と画像との畳み込み演算である。
【数２】
【００２９】
なお、回転不変の性質を持つ特徴量を算出可能な方法であれば、本実施形態で用いた特徴量算出方法に限らず、どのような特徴量算出方法でも局所特徴量算出部１０５に適用可能である。
【００３０】
次に、ステップＳ３０６において、対称領域抽出部１０８は局所特徴点及びそれらの局所特徴量を用いて登録画像１０１から対称性を有する部分画像（対称領域）を抽出する。そして、ステップＳ３０７において、特徴量登録部１０６は、局所特徴量算出部１０５から渡された回転不変の性質を持つ特徴量と画像入力部１０２から渡された登録画像１０１とを関連付けて画像特徴データベース１０７に登録する。このとき、特徴量登録部１０６は、対称領域抽出部１０８から渡された対称領域に基づいて画像特徴データベース１０７に登録される特徴点を分類する。以下、画像中から特徴点の類似性に基づいて対称な部分領域を抽出する処理（ステップＳ３０６）、及びそれらを登録する処理（ステップＳ３０７）について図４のフローチャートを用いて説明する。
【００３１】
ステップＳ４０１によって示されている、画像中の特徴点の抽出および特徴量の計算は、上述したステップＳ３０４，Ｓ３０５の処理に該当する。次に、ステップＳ４０２にて、対称領域抽出部１０８は、特徴点の類似性に基づく対称領域の抽出を行う。ステップＳ４０２の処理については図８のフローチャートを用いて後で詳しく説明を行う。ステップＳ４０３において、対称領域抽出部１０８は、ステップＳ４０２で抽出した対称領域においてアフィン変換係数を求めるのに用いる部分対称領域を決定する。以下、図７を用いてその目的を説明する。なお、ステップＳ４０３の処理の詳細は図８のフローチャートにより後述する。
【００３２】
図７の（ａ）がクエリ画像で、図７の（ｂ）が比較するべき比較先画像とする。クエリ画像から２点を選択して、これに類似する特徴点を図７の（ｂ）の比較先画像から決定する。このとき、図７の（ａ）、（ｂ）に示した画像は左右対称であるため、図７の（ａ）の左下の特徴点に対応する特徴点として、比較先画像における対称軸の反対側の領域から特徴点を選択してしまうことがありえる。この誤って選択された２点により画像を同じ回転状態、拡大縮小率に揃えようとすると、図７の（ｃ）の様な誤った変換を行ってしまう。これを避けるためには、図７の（ａ）のクエリ画像から選択する特徴点も、図７の（ｂ）の比較先画像から選択する特徴点も、アフィン変換決定のためには、対称領域の同じ側から取るようにする必要がある。以下、対称領域の一方の第１の領域を甲、他方の第２の領域を乙と称する。
【００３３】
次に、ステップＳ４０４にて、特徴量登録部１０６は、対称領域以外の非対称領域に存在する特徴点の特徴量を画像特徴データベース１０７に記憶する。ここで記憶される特徴点及び特徴量に関して、対称領域情報としてＮＵＬＬが記憶される。次いで、ステップＳ４０５にて、特徴量登録部１０６は、対称領域に存在する特徴点のうち、領域甲に含まれる特徴点の特徴量をデータベース１０７に記憶する。ここで記憶される特徴点及び特徴量に関して、対称領域情報として甲が記憶される。更に、ステップＳ４０６にて、特徴量登録部１０６は、対称な特徴点のうち、領域乙に含まれる特徴点の特徴量をデータベース１０７に記憶する。ここで記憶される特徴点及び特徴量に関して、対称領域情報として乙が記憶される。
【００３４】
本実施形態では、データベース１０７に記憶された対称領域情報を用いて、画像検索時においてアフィン変換の係数を求めるために使用する特徴点の対の選択を限定する。この点については、［画像の検索処理］において詳述する。
【００３５】
次に、図８を用いて、上述した対称領域の抽出処理（ステップＳ４０２、Ｓ４０３）について説明する。
【００３６】
まず、ステップＳ８０１にて、対称領域抽出部１０８は、画像中の特徴点について総当りで類似度を求め、閾値ＴＨ１以上の類似度を持つ特徴点の対（ペア）を求める。本例では、その対の個数をＮＰとする。この閾値処理により、良質な類似特徴点の候補ペアが作成される。
【００３７】
次に、ステップＳ８０２にて、対称領域抽出部１０８は、ステップＳ８０１で抽出されたＮＰ個の特徴点の対の中点を求め、当該中点に対して当該２つの特徴点の平均画素値を与える。そして、ステップＳ８０３にて、対称領域抽出部１０８は、これら複数組の特徴点の対から得られる中点群に関してハフ変換を行う。ハフ変換は公知のもので良く、画像上の直線成分を検出するのに一般的に用いられる方法である。目的は、中点からなる直線、即ち対称軸の直線を得る事に有る。
【００３８】
以下、図９を用いて、本実施形態によるハフ変換の概略を説明する。図９の（ａ）において、Ｘ−Ｙ平面上に、Ｐ1、Ｐ2、Ｐ3の３点が有り、今、Ｐ2に着目する。
【００３９】
この直線に原点から垂線を下ろし、その長さをρ、ｘ軸とのなす角をθとすれば、
ρ＝ｘ cosθ＋ｙ sinθ
と表す事が出来る。この様に、極座標系では、１点（ρ, θ）が判れば一つの直線が定まることになる。ここで、点（ρ,θ）を直線ｙ＝ａｘ＋ｂのハフ変換と呼ぶ。また、ｘ−ｙ座標系の一点（ｘ0, ｙ0）を通る傾きの異なる直線の集まりは、
ρ＝ｘ0 cosθ＋ｙ0sinθ
というように表現することができる。このとき、図９の（ａ）に示す３点の各点を通る直線群の軌跡をρ−θ平面に書いたグラフが図９の（ｂ）である。もし、この３点が同一直線上に乗っているとすればρとθの値は同じ値となるはずであり、それら３点に対応するρ−θ平面上の軌跡は１点で交わることになる。この原理を利用して、特徴点対の中点が直線上（対称軸）に乗っているかどうかを検証することが出来る。
【００４０】
ステップＳ８０４において、対称領域抽出部１０８は、ハフ平面ρ−θ上で各点での曲線の交差数に対して閾値処理を行い、閾値を超えた点をＮＬ個得る。値の高い点が、中点を通る直線を表す曲線の交点であるという推定に基づく処理である。この閾値処理により、尤もらしい対称軸を成す直線を得る。
【００４１】
ステップＳ８０５において、対称領域抽出部１０８は、ステップＳ８０４で得た閾値越えの点から着目するべき１つめの点をセットする。そして、ステップＳ８０６で閾値越えの点に対する処理が全て終えてなければ処理をステップＳ８０７に分岐する。閾値越えの点に対する処理が全て終えていれば、ステップＳ８１１で、対称領域数ＮＬと、各対称領域における対称な特徴点のペアと対称軸の直線の式とを記憶し、処理を終了する。
【００４２】
ステップＳ８０７において、対称領域抽出部１０８は、ｉ番目の点を逆ハフ変換し、ｉ番目の対称軸を得る。そして、ステップＳ８０８にて、ＮＰ個の特徴点対の中から、ｉ番目の対称軸近傍に中点があるペアを求める。
【００４３】
ステップＳ８０９にて、対称領域ｉにおける対称な特徴点のペアと、対称軸の直線の式を記憶し、ステップＳ８１０にて、着目する閾値超えの点を次に切り替えるべくｉをインクリメントする。その後、処理は再びステップＳ８０６に戻る。
【００４４】
以上の処理により、画像から複数の対称領域を得て、更に対称な特徴点のペアを得る事が出来る。
【００４５】
次に、図１０を用いて、対称性を有する部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを第１領域（甲）と第２領域（乙）に決定する方法を説明する。本実施形態では、対称性を有する部分画像における画像特徴の傾向に基づいて第１領域と第２領域が決定される。
【００４６】
ステップＳ１００１にて、対称領域抽出部１０８は、指定された対称軸の直線の式と対称な特徴点のペアから対称領域の矩形座標を推定する。より具体的には、指定された対称軸と対称な特徴点のペアを包含し、且つ当該対称軸に対して対称な矩形領域を推定する。
【００４７】
次に、ステップＳ１００２にて、対称領域抽出部１０８は、図１１に示す様に、対称軸と垂直な直線で推定された対称領域の矩形を均等４分割する。
【００４８】
次に、ステップＳ１００３にて、対称領域抽出部１０８は、４分割領域の各々の平均輝度を求める。そして、ステップＳ１００４にて、４分割領域のうち平均輝度の小さい分割領域を対称領域の反時計回り側に持つ対称領域の一方を甲、他方を乙と決定する。例えば、図１１に示されるように、平均輝度の小さい分割領域（輝度値＝２０）が反時計回り側に存在する領域が甲に、平均輝度の小さい分割領域が時計回り側に存在する領域が乙に決定される。このように、上記処理によれば、対称軸により分割された２つの部分領域の各々における濃度勾配の方向により、当該２つの部分領域のそれぞれを甲、乙のいずれかにラベル付けされる。
【００４９】
もちろん、平均輝度の大きい分割領域の方を選択しても良く、要は、一貫性の有る分割領域の選択が出来れば良い。また、平均輝度以外にも、各領域に含まれる特徴点の個数に着目するなど、他の特徴量を用いる事ももちろん可能である。即ち、対称性を有する部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれは、当該部分画像もしくは部分領域における画像特徴の傾向に基づいて第１領域（甲）と第２領域（乙）にラベル付けされる。
【００５０】
以上のようにして、対称領域における対の領域を甲、乙に決定することにより、例えば、図１２の様に時計回りに９０度回転された状態であっても、図１３の様に反時計回りに９０度回転された状態であっても、一意に着目すべき部分対称領域を決定できる。
【００５１】
以上のように甲と乙を決定した上で、特徴量登録部１０６は、ステップＳ３０６により局所特徴量算出部１０５から渡された回転不変の性質を持つ特徴量と画像入力部１０２から渡された登録画像１０１とを関連付け、画像特徴データベース１０７に登録する。以上で画像登録処理が終了する。
【００５２】
［画像の検索処理］
次に、画像検索の際に行う各部の動作について説明する。図６は画像検索装置２００による検索処理の手順を表すフローチャートである。
【００５３】
本処理例では、縮小変換と回転変換による合成した局所特徴量の揺らぎ考慮した処理構成とする。
【００５４】
ステップＳ６０１において、画像入力部２０２（図２）は、クエリ画像２０１を読み込む。
【００５５】
次に、ステップＳ６０２において、画像入力部２０２の輝度成分画像生成部２１１は、当該クエリ画像２０１から輝度成分を抽出して輝度成分画像を生成し、生成した輝度成分画像を縮小画像生成部２０３に渡す。
【００５６】
次に、ステップＳ６０３において、縮小画像生成部２０３は、画像入力部２０２から渡された輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成して当該縮小画像を局所特徴点抽出部２０４に渡す。ただし、倍率ｐおよび縮小画像の枚数ｎは前述の画像登録装置１００における画像の登録処理で用いた値と同じ値にする。
【００５７】
次に、ステップＳ６０４において、局所特徴点抽出部２０４は、縮小画像生成部２０３から渡されたｎ枚の縮小画像それぞれにおいて、画像の特徴点（回転不変の性質を持つ特徴点）を抽出する。抽出した当該回転不変の性質を持つ特徴点は局所特徴量算出部２０５に渡される。ここで本実施形態では、回転不変の性質を持つ特徴点の抽出方法として前述の画像の登録処理で用いた方法と同様に、Harris作用素を用いる。より具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素および当該画素の８近傍にある画素（合計９画素）の画素値を調べられる。そして、当該画素が局所極大（当該９画素の中で当該画素の画素値が最大になる）になる点が回転不変の性質を持つ特徴点として抽出される。このとき、当該画素が局所極大になったときでも、当該画素の値があらかじめ定められたしきい値以下の場合には回転不変の性質を持つ特徴量として抽出しないようにする。なお、回転不変の性質を持つ特徴点を抽出可能な方法であれば、本実施形態で用いた特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部２０４に適用可能である。
【００５８】
次に、ステップＳ６０５において、局所特徴量算出部２０５は、局所特徴点抽出部２０４から渡された回転不変の性質を持つ特徴点それぞれについて、画像の回転があっても不変となる局所特徴量（回転不変の性質を持つ局所特徴量）を算出する。ここで、回転不変の性質を持つ特徴量の算出方法は前述の画像の登録処理で用いた方法と同じ方法を使用する。すなわち、本実施形態では、LocalJetおよびそれらの導関数の組み合わせを用い、式（１）に示す回転不変の性質を持つ特徴量を算出する。
【００５９】
次に、ステップＳ６０６において、対称領域抽出部２０６は、ステップＳ６０４，Ｓ６０５で取得された特徴点及びその特徴量に基づいて、当該クエリ画像から対称領域（対称性を有する部分画像）を抽出する。この処理は、ステップＳ３０６の処理と同様である。そして、ステップＳ６０７において、特徴比較部２０７は、局所特徴点抽出部２０４及び局所特徴量算出部２０５から渡された回転不変の性質を持つ特徴点及びその特徴量と画像特徴データベース１０７に登録されている特徴量とを比較する。この比較は、画像特徴データベース１０７に登録されている登録画像ごとに、対称領域抽出部２０６から渡された対称領域の抽出結果を参照して実施される（詳細は後述）。そして、比較の結果として登録画像ごとに類似度を算出する。類似度の算出方法については後述する。
【００６０】
次に、ステップＳ６０７では、算出した当該類似度と当該類似度の算出元となった画像とを関連付けて検索結果リストを作成した後、当該類似度を降順にソートする。その後、類似度が大きい画像と当該画像の類似度とをソート順に検索結果２０８として出力する。
【００６１】
［類似度の算出方法］
次に、本実施形態における局所特徴量の比較方法（図６のＳ６０７）を、図１４〜図１６のフローチャートを参照して説明する。
【００６２】
図１４は、本実施形態による比較処理の全体を示すフローチャートである。ステップＳ１４０１にて、特徴比較部２０７は、クエリ画像２０１の対称性の有無（対称領域の存否）を判定する。クエリ画像２０１における対称性の有無に応じて、類似度演算の処理はステップＳ１４０２とステップＳ１４０３のいずれかに切り替わる。ステップＳ１４０４において、特徴比較部２０７は、ステップＳ１４０２とステップＳ１４０３のどちらかで得た類似度を出力する。
【００６３】
次に、ステップＳ１４０２の類似度演算処理の詳細を、図１５のフローチャートを用いて説明する。
【００６４】
ここで、局所特徴量算出部２０５から渡された回転不変の性質を持つ特徴量をＶｓ、回転不変の性質を持つ特徴量に関連付けされている座標をＳ（x，y）とする。また、画像特徴データベース１０７に登録されている比較先画像Ｒ上に存在する回転不変の性質を持つ特徴量をＶｑ、回転不変の性質を持つ特徴量に関連付けされている座標をＱ（x’，y’）とする。
【００６５】
以下、特徴比較部２０７による類似度の算出手順を図１５に示すフローチャートに従って説明する。類似度の算出では、まず、ステップＳ１５０１により、最終投票数を表す変数VoteMaxを０に初期化する。
【００６６】
次に、ステップＳ１５０２において、特徴比較部２０７は、画像特徴データベース１０７に登録されている画像Ｒ上に存在する特徴量のうち、領域甲に含まれるＶｑと、領域甲に含まれるＶｓとの特徴量間距離をすべての組み合せについて計算する。そして、クエリ画像２０１の領域甲に含まれるＶｑの各々について特徴量間距離が最短となる、比較先画像の領域甲に含まれるＶｓとの組み合わせを示す最短距離対応点リスト１を作成する。
【００６７】
換言すれば、クエリ画像が対称性のあるものである場合には、対称領域のうちの部分領域甲に含まれる特徴点だけから最短距離対応点リストを作成するという事である。
【００６８】
更に、ステップＳ１５０３にて、特徴比較部２０７は、画像特徴データベース１０７に登録されている画像Ｒ上に存在する回転不変の性質を持つ特徴量ＶｑとＶｓのうち、
・領域乙に含まれるＶｑとＶｓ、および
・非対称領域に含まれるＶｑとＶｓ、
のそれぞれで、すべての組み合せについて特徴量間距離を計算し、最短距離対応点リスト１に追記する形で最短距離対応点リスト２を作成する。
【００６９】
即ち、最短距離対応点リスト２は、領域甲、領域乙と非対称領域ごとに、類似する特徴点（対応する特徴点）を求めた結果がマージされたリストとなる。
【００７０】
この最短距離対応点を求める際に、先に、クエリ画像の各特徴点に対して記憶しているマハラノビスの距離を算出するための観測値をX=(X1,X2,…,Xp)'とし、母集団ｊの分散共分散行列Σjの逆行列Σj-1と平均（重心）μj=(μ1j,μ2j,…,μpj)'(j=1,2,…,k)とを用いて式（８）に基づいて距離ｄjを求める。そして、求めた距離と分散共分散逆行列を含む最短距離対応点リストを作成する。
【００７１】
ｄj2=(Ｘ−μj)'Σj-1(Ｘ−μj) …（８）
すなわち、計算した特徴量間距離がしきい値Ｔｖ以下となり、かつ、最短距離となるようなＶｑとＶｓとの組合せ（対応点）を抽出し、これを最短距離対応点リストに登録する。以後、本実施形態の説明では、最短距離対応点リストに登録された対応点について、当該対応点の回転不変の性質を持つ特徴量をそれぞれＶｑ（ｋ）とＶｓ（ｋ）と記載する。また、Ｖｑ（ｋ）とＶｓ（ｋ）に対応付けられている座標についてはそれぞれＱk（x’k，y’k）、Ｓk（xk，yk）などと添え字をあわせて記載する。また、ステップＳ１５０３で作成された最短距離対応点リスト２に登録された対応点の組数をｍ組とする。最短距離対応点リスト２には、対応点リスト１の対応点（甲の対応点）＋乙の対応点＋非対称領域の対応点が登録されている。
【００７２】
次に、ステップＳ１５０４において、特徴比較部２０７は、類似度算出処理の反復カウント数を表す変数Countを０に初期化する。そして、ステップＳ１５０５において、特徴比較部２０７は、反復カウント数Countがあらかじめ定めた最大反復処理回数Ｒｎを超えていないか判定する。超えている場合はステップＳ１５２０で類似度変換処理を行い、本処理を終了する。超えていない場合は、処理はステップＳ１５０６に移る。ステップＳ１５２０における総合類似度算出処理に関する詳細は、後に説明する。
【００７３】
ステップＳ１５０６において、特徴比較部２０７は、投票数を表す変数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を使って式（１１）から式（１４）で表される。
【００７７】
【数５】
【００７８】
次に、ステップＳ１５０９では、対応点選択変数ｋを０に初期化する。
【００７９】
次に、ステップＳ１５１０において、特徴比較部２０７は、対応点選択変数ｋが当該最短距離対応点リスト２に登録されている対応点の組数ｍを超えていないか判定する。超えていると判定された場合はステップＳ１５１７に処理を移すが、これについては後述する。ステップＳ１５１０における判定で対応点選択変数ｋが当該最短距離対応点リスト２に登録されている対応点の組数ｍを超えていない場合はステップＳ１５１１に処理を移す。
【００８０】
ステップＳ１５１１では、当該最短距離対応点リスト２からランダムに１組の点Ｓk（ｘk，ｙk）、Ｑk（x’k，y’k）を選択する。
【００８１】
次に、ステップＳ１５１２において、特徴比較部２０７は、Ｓk（ｘk，ｙk）が式（９）を使って変換される座標Ｓ’k（ｘ’k，ｙ’k）を求める。
【００８２】
その後、ステップＳ１５１３において、特徴比較部２０７は、座標Ｓ’k（ｘ’k，ｙ’k）と座標Ｑk（ｘ’k，ｙ’k）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離がしきい値Ｔｄ以下であるかどうかを判定する。当該ユークリッド距離がしきい値Ｔｄ以下の場合には、ステップＳ１５１４において、Voteに対する対応点の対Ｓ’k,Ｑkを記憶する。そして、ステップＳ１５１５において投票数Voteをインクリメントし、ステップＳ１５１６に処理を移す。一方、当該ユークリッド距離がしきい値Ｔｄより大きい場合には、何もせずにステップＳ１５１６に処理を移す。ステップＳ１５１６では、対応点選択変数ｋをインクリメントし、ステップＳ１５１０に処理を戻す。
【００８３】
次に、ステップS１５１０において対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていた場合の処理であるステップＳ１５１７を説明する。ステップＳ１５１７において、特徴比較部２０７は、投票数Voteの値と最終投票数VoteMaxの値とを比較し、投票数Voteの値が最終投票数VoteMaxの値よりも大きい場合はステップＳ１５１８の処理を実行する。特徴比較部２０７は、ステップＳ１５１８において最終投票数VoteMaxの値を投票数Voteの値で置き換え、ステップＳ１５１９でCountを１つインクリメントした後、ステップＳ１５０５に処理を戻す。一方、ステップＳ１５１７において投票数Voteの値が最終投票数VoteMaxの値以下の場合は、何もせずにステップＳ１５１９でCountを１つインクリメントした後、ステップＳ１５０５に処理を戻す。
【００８４】
ステップＳ１５２０では図１７に示す単調現象特性の最終投票数−類似度変換テーブルにより最終投票数について類似度変換を行い、最終的な類似度を得る。
【００８５】
なお、本実施形態における類似度の算出方法の説明では、相似変換を考慮して説明したが、アフィン変換などその他の幾何学変換についても、ステップＳ１５０８においてそれぞれに応じた変換行列を求めることにより対応可能である。たとえば、アフィン変換の場合は、まず、ステップＳ１５０７でランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ１５０８において式（９）ではなく前述した式（８）を使うこととし、ステップＳ１５０７で選択した３組の対応点（合計６点）を使って変数ａ〜ｆを求めればよい。
【００８６】
次に、図１４のステップＳ１４０１においてクエリ画像に対称性が無いと判定された場合の処理（ステップＳ１４０６）を図１６を用いて説明する。なお、図１５により上述した処理との差分について説明する。
【００８７】
先の図１５に示した処理との差は、クエリ画像に対称性が無いのでステップＳ１６０２にて画像全体の特徴点に対して最短距離対応点リスト１を作成する所である。（対Ｓ１５０２、Ｓ１５０３）
また、当然、Ｓ１６０６、Ｓ１６１０では最短距離対応点リスト１から、幾何変換を行う特徴点の対を選ぶ事になる。
【００８８】
更に、ステップＳ１６０６で選択した幾何変換の基準となる２対の点をステップＳ１６１０で再び選択しないように、ステップＳ１６０８でｋの初期値を３（ｋ＝３）とする所も異なる。
【００８９】
その他の処理（ステップＳ１６０１、Ｓ１６０３〜Ｓ１６０５、Ｓ１６０７、Ｓ１６０９、Ｓ１６１１〜Ｓ１６１９）は、図１５（Ｓ１５０１、Ｓ１５０４〜Ｓ１５０６、Ｓ１５０８、Ｓ１５１０、Ｓ１５１２〜Ｓ１５２０）と同様の処理を行う。
【００９０】
以上のように、第１実施形態によれば、幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にし、無為に対応点候補個数を増やさないで検索することが可能になる。
【００９１】
＜第２実施形態＞
第１実施形態では、対称軸を求めるにあたりハフ変換を用いたが、これに限られるものではない。第２実施形態は、ハフ変換を用いず、別の方法で対称領域を求める例であり、その他の処理は第１実施形態と同様である。
【００９２】
図１８にそのフローを示し、説明する。
【００９３】
まず、ステップＳ１８０１にて、対称領域抽出部１０８（２０６）は、画像中の特徴点を総当りで類似度を求め、閾値ＴＨ１以上の類似度を持つ特徴点の対を求めるその個数をＮＰとする。この閾値処理により、良質な類似特徴点の候補ペアを作成する。
【００９４】
次に、ステップＳ１８０２にてＮＰ個の類似特徴点ペアの中点を求め、ステップＳ１８０３にてカウンタｉを１にセットし、ＮＣ＜（ＮＰ＊（ＮＰ−１）／２）なるＮＣを定める。そして、ステップＳ１８０４においてｉ≦ＮＣを満たす間、ステップＳ１８０５〜Ｓ１８０７，Ｓ１８１８の処理を行い、満たさなくなった場合にステップＳ１８１９に分岐する。ここで、ＮＰ＊（ＮＰ−１）／２とは、ＮＰ個の点から任意の２点を選ぶ組合せの数である。
【００９５】
ステップＳ１８０５において、対称領域抽出部１０８（２０６）は、ＮＰ個の中点群からランダムに２点を選択し、ステップＳ１８０６にて２点間の直線を求める。
【００９６】
次に、Ｓ１８０７において、対称領域抽出部１０８（２０６）は、ＮＰ個の中点群と、直線の距離を求め、それらを足し合わせて累積距離を求める。そして、ステップＳ１８１８において、ｉと累積距離と選んだ２点とその直線の式を記憶し、ステップＳ１８０４に処理を戻す。
【００９７】
なお、ステップＳ１８０７で距離の総和としたが、もちろん二乗距離の総和を累積距離としても良い。
【００９８】
ステップＳ１８１９において、対称領域抽出部１０８（２０６）は、求めた距離の総和或いは二乗距離が最小と成るi_MINとその距離DMINを求める。そして、ステップＳ１８２０において、DMINが閾値ＴＨ２以下であれば対称軸・対称領域が有るとしてステップＳ１８２１に進む。一方、DMINが閾値ＴＨ２より大きい場合は、ステップＳ１８２０からステップＳ１８２４に進み、対称領域が無いと判断され、本処理は終了する。
【００９９】
ステップＳ１８２１において、対称領域抽出部１０８（２０６）は、i_MINに対応する直線を対称軸とする。そして、ステップＳ１８２２において、対称領域抽出部１０８（２０６）は、ＮＰ個の特徴点対の中から対称軸近傍に中点があるペアを求める。次に、ステップＳ１８２３において、対称領域抽出部１０８（２０６）は、対称軸近傍に中点を持つ特徴点ペアを包含し、対称軸を中心とする矩形領域を求め、これを対称領域として本処理を終了する。
【０１００】
これらの処理により、画像中の支配的な対称領域を検出する事が出来る。なお、上記処理では、最小の累積距離を持つ１つの直線に関して、その累積距離が閾値ＴＨ２より小さい場合に、対応する直線を対称軸とした。しかしながら、これに限られるものではなく、例えば、累積距離がある閾値よりも小さくなる１又は複数の直線を抽出して、これら直線を対称軸として扱うようにしてもよい。
【０１０１】
なお、上記の処理では、厳密な対称軸が求まらない恐れもあるが、発明の趣旨は、対称領域の部分対称領域甲乙を決定し、高と乙を意識して特徴点を扱う事であるので、厳密な対称軸を求める必要は無い。もちろん、その他の簡易な方法で対称領域ならびに甲乙を定める方法があれば、それを用いても構わない。
【０１０２】
＜第３実施形態＞
クエリ画像の対称性を検証して対称性が有る（対称領域が存在する）と判定された場合、対称性が無い（対称領域が存在しない）登録画像は比較する価値が無い。そこで、クエリ画像が対称性の有る画像の場合に、登録画像の対称性解析において求めた対称領域数ＮＬが０でない物のみを比較対象とすることで、大幅な処理の簡素化が行え、検索を高速に行うことが可能となる。
【０１０３】
なお、クエリ画像自体を回転や拡大・縮小して特徴点における特徴量の分布を求めておき、ある特徴点の比較の際に．回転や拡大・縮小による変動幅で正規化した類似距離を求めた上で複数の特徴点による総合類似度を求めるようにしてもよい。このようにすれば、それぞれの特徴点における距離が等価なものと出来、類似距離の精度向上、回転や拡大・縮小によるばらつきの低減が期待できる。
【０１０４】
以上のように、上記各実施形態によれば、幾何的に対称な画像（或いはそのような対称領域を有する画像）の検索に対する、検索処理の速度の向上、検索の高精度化を達成できる。
【０１０５】
＜その他の実施形態＞
以上、実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【０１０６】
尚、本発明は、ソフトウェアのプログラムをシステム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによって前述した実施形態の機能が達成される場合を含む。この場合、供給されるプログラムは実施形態で図に示したフローチャートに対応したコンピュータプログラムである。
【０１０７】
また、コンピュータが、コンピュータ読み取り可能な記憶媒体に格納されたプログラムを読み出し、読み出したプログラムを実行することによって、前述した実施形態の機能が実現され手もよい。また、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどとの協働で実施形態の機能が実現されてもよい。この場合、ＯＳなどが、実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される。
【技術分野】
【０００１】
本発明は、画像中の特徴点の類似度に基づく画像検索技術に関するものである。
【背景技術】
【０００２】
一般に、画像の回転に対応した画像検索は、クエリ画像を回転して特徴量を求める或いは特徴量を回転変換したものを用いることにより行われていた。
【０００３】
従来から提案されている画像中の特徴点の類似度に基づく画像検索技術として、特許文献１が挙げられる。特許文献１では、局所的な特徴同士の比較に基づく画像検索において、クエリ画像から無作為に選ばれた特徴点の対に類似する特徴点を登録画像中から求める。そして、対の特徴点の位置関係に基づいてクエリ画像と登録画像の間の幾何学変換関数を求め、対以外の特徴点が幾何学変換関数によって変換された場所に、登録画像の対応する特徴点が存在しているものをカウントし、類似性を判定していた。
（以下において、非特許文献１，２は「発明を実施するための最良の形態」の欄において参照されている文献である。）
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−０６５３９９号公報
【非特許文献】
【０００５】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記処理では、局所的な特徴同士の比較に基づく画像検索において、対称な（左右／上下対称）部分画像を有する画像の検索に関して適切に検索を行えなくなる場合があった。即ち、対称な部分画像において、図７で後述するように、類似する特徴点の組み合わせを誤抽出してしまい（類似する特徴点の対が対称領域をまたいでしまう）、最悪の場合正しい組み合わせに出くわさないで検索が失敗する事があった。このような事態の発生を防ぐために、対応点候補個数を増やし、１０００程度にして正しいものと出くわす確率を上げる方法もあるが、対応点候補個数による検索速度の低下を招いてしまう。
【０００７】
本発明は上記の課題に鑑みてなされたものであり、幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にし、無為に対応点候補個数を増やさないで検索することを可能にすることを目的とする。
【課題を解決するための手段】
【０００８】
上記の目的を達成するための本発明の一態様による画像検索装置は以下の構成を備える。即ち、
入力されたクエリ画像と類似する画像を登録されている画像から検索する画像検索装置であって、
前記クエリ画像において、特徴点の特徴量に基づいて互いに対応する特徴点の対を取得し、取得された特徴点の対に基づいて対称性を有する部分画像を抽出する抽出手段と、
前記部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを、当該部分画像における画像特徴の傾向に基づいて第１領域と第２領域に決定する決定手段と、
前記クエリ画像と登録されている比較先画像について、両画像の前記第１領域に決定されている部分領域に存在する特徴点から特徴量に基づいて少なくとも２組の対応する特徴点の対を抽出し、抽出した各対の特徴点の座標が一致するように前記両画像のうちの一方の画像の特徴点を変換するための座標変換係数を設定する設定手段と、
前記両画像の類似を判定するために、前記両画像に存在する特徴点から特徴量に基づいて互いに対応する特徴点の対を抽出し、前記一方の画像について抽出された特徴点の座標を前記座標変換係数を用いた座標変換処理によって変換し、変換後の特徴点の座標と前記両画像のうちの他方の画像における特徴点の座標とを比較する比較手段とを備える。
【発明の効果】
【０００９】
本発明によれば、幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にすることができ、無為に対応点候補個数を増やさないで検索することが可能となる。
【図面の簡単な説明】
【００１０】
【図１】実施形態による画像登録装置の構成例を示すブロック図。
【図２】実施形態による画像検索装置の構成例を示すブロック図。
【図３】実施形態による画像の登録処理を表すフローチャート。
【図４】局所特徴量の登録に関する処理を表すフローチャート。
【図５】縮小画像生成の例を示す図。
【図６】実施形態による画像の検索処理を表すフローチャート。
【図７】対称性の有る画像を検索する場合の弊害の一例を説明する図。
【図８】実施形態による、対称性を有する部分画像を抽出するための処理を示すフローチャート。
【図９】ハフ変換の原理を説明する図。
【図１０】対称性を有する部分画像が存在する場合の、対称性を有する部分画像の甲・乙の決定処理を示すフローチャート。
【図１１】対称性を有する画像と、甲・乙のラベル付けを説明する図。
【図１２】対称性を有する画像と、甲・乙のラベル付けを説明する図。
【図１３】対称性を有する画像と、甲・乙のラベル付けを説明する図。
【図１４】実施形態による、局所特徴量の比較処理を説明するフローチャート。
【図１５】クエリ画像が対称性を有する部分画像を含む場合の類似度判定処理を示すフローチャート。
【図１６】クエリ画像が対称性を有する部分画像を含まない場合の類似度判定処理を示すフローチャート。
【図１７】距離を類似度へ変換するルックアップテーブルの例を示す図。
【図１８】第２実施形態による、画像の対称性の有無を判定する処理を示すフローチャート。
【発明を実施するための形態】
【００１１】
まず、本実施形態の概要を説明する。本実施形態の画像検索装置におけるクエリ画像と比較先画像との類似性の判定においては、回転不変の性質をもつ特徴点および回転不変特徴量（スケール内の特徴量）が用いられる。そして、クエリ画像と比較先画像との間で対応する少なくとも２対の特徴点の座標に基づいて座標変換処理のための座標変換係数を決定する。本実施形態ではアフィン変換を採用しており、上記処理によりアフィン変換関数が決定される。そして、クエリ画像或いは比較先画像の一方の画像における特徴点座標をアフィン変換して、変換後の座標と他方の画像における特徴点の座標とを比較する比較処理により両画像の類似性を判定する。
【００１２】
本実施形態の登録処理時においては、登録画像中の特徴点抽出結果に基づき特徴点が対称となる部分領域、即ち対称性を有する部分領域に関して、対称軸で分割された領域に画像特徴の傾向に基づいて第１領域と第２領域に決定する。本実施形態では、一方の領域を甲に、他方の領域を乙にをラベル付けする。各特徴点は、対称画像領域中に有ることおよび甲或いは乙に属する事を示す情報と共に画像特徴データベースに登録される。他方、登録画像中の対称領域以外の特徴点は、対称領域中に無いことを示す情報と共に画像特徴データベースに登録される。
【００１３】
本実施形態の検索処理時においては、クエリ画像から抽出された特徴点に基づいて対称性を有する部分領域の有無を判定する。そして、対称性を有する部分領域が有る場合には、対称領域の対である甲乙のうち、甲が設定された領域から少なくとも２つの特徴点を選択して、比較先画像中の甲が設定された領域から対応する特徴点点を求める。そして、これら特徴点を用いて上記アフィン変換関数が決定される。これにより、対称図形の同じ側から対応する特徴点を推定する事が可能となる。
【００１４】
こうして決定されたアフィン変換関数により、特徴点の座標変換処理を行い、上記比較処理が実行される。ここで対象となる特徴点は、クエリ画像と比較先画像の甲に設定された領域以外の領域を含める。例えば、乙に設定された領域、対称性を有する領域以外の非対称領域を含める。
【００１５】
以上のように、クエリ画像と比較先画像の甲に設定された領域からアフィン変換関数を決定するための特徴点を選ぶ事により、対応する正しい対称領域から特徴点の対が選択され、対称性による弊害を軽減できる。即ち、幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にすることができる。
【００１６】
もちろん、クエリ画像中の特徴点抽出結果に基づき特徴点が対称となる部分領域の有無を求め、対称領域（対称性を有する部分画像）が無い場合には、通常の比較処理を行う。
【００１７】
以下の実施形態において、上述した対称領域の検出は、画像中の類似する特徴点ペアの中点群が直線的に並ぶのを確認し、この直線を対称軸とし、当該対称軸の近傍に中点を持つ特徴点ペアを求めることで実現される。
【００１８】
例えば、画像中の類似する特徴点ペアの中点群に対してハフ変換を行う事により対称軸を求め、対称軸近傍に中点を持つ特徴点ペアを求める事で、より厳密な対称領域の検出を実現できる。
【００１９】
尚、対称領域がある場合の領域甲乙の決定においては、画像特徴の偏りを用いることにより一意に甲乙を決定する事が可能となる。このような画像特徴の例としては、特徴点の個数あるいは領域中の画素濃淡平均など、領域固有の画像特徴を用いると良い。そして、例えば、その結果を用いて、対称性を有する部分画像を画像特徴の偏よりの大きい方或いは小さい方が上或いは下に来る様に回転したときに左側或いは右側の半分を甲に決定するというようなルールを定めれば良い。
【００２０】
他方、対称な領域がある画像の場合に、「対称領域あり」というメタデータを画像に付与し、クエリ画像が対称な画像の場合に、対称領域のある画像のみを検索対象とする絞込検索を行う事が出来る。
【００２１】
＜第１実施形態＞
図１は本発明の第１実施形態における画像登録装置の構成例を示すブロック図である。図１において、１００は画像登録装置であり、画像入力部１０２、縮小画像生成部１０３、局所特徴点抽出部１０４、局所特徴量算出部１０５、対称領域抽出部１０８、特徴量登録部１０６を備える。１０１は登録画像であり、画像登録装置１００によって後述する画像特徴データベースに登録される画像である。１０７は画像特徴データベースであり、画像登録装置１００により登録画像１０１から抽出された画像特徴が登録される。
【００２２】
図２は本発明の第１実施形態における画像検索装置の構成例を示すブロック図である。図２において、２００は画像検索装置であり、画像入力部２０２、縮小画像生成部２０３、局所特徴点抽出部２０４、局所特徴量算出部２０５、対称領域抽出部２０６、特徴比較部２０７を備える。２０１はクエリ画像である。画像検索装置２００は、画像特徴データベース１０７から当該クエリ画像２０１に類似した画像を検索する。２０８は検索結果画像であり、画像検索装置２００が画像特徴データベース１０７を検索した結果として出力される画像である。
【００２３】
以上のような構成を備えた本実施形態にかかる画像登録装置１００及び画像検索装置２００の動作例を以下に説明する。
【００２４】
［画像の登録処理］
まず、画像登録装置１００が行う画像の登録処理について説明する。図３は画像の登録処理の手順を表すフローチャートである。ステップＳ３０１において、画像入力部１０２は、登録画像１０１を読み込む。ステップＳ３０２において、画像入力部１０２の輝度成分画像生成部１１１は、当該登録画像１０１から輝度成分を抽出して輝度成分画像を生成し、当該輝度成分画像を縮小画像生成部１０３に渡す。また、画像入力部１０２は、登録画像１０１を特徴量登録部１０６に渡す。
【００２５】
次に、ステップＳ３０３において、縮小画像生成部１０３は、画像入力部１０２から渡された輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成し、生成した縮小画像を局所特徴点抽出部１０４に渡す。ただし、倍率ｐおよび縮小画像の枚数ｎはあらかじめ定めておく。図５は縮小画像生成の例を示す図であり、倍率ｐが２の−１／４乗、縮小画像の枚数ｎが９の場合に縮小画像生成部１０３が生成する縮小画像の例を示している。図５において、５０１は画像入力部１０２から渡された輝度成分画像、５０２は当該輝度成分画像から倍率ｐに従って４回縮小された縮小画像、５０３は当該輝度成分画像から倍率ｐに従って８回縮小された縮小画像である。図５の例においては、縮小画像５０２は画像入力部１０２から渡された輝度成分画像が１／２に縮小された画像となり、縮小画像５０３は画像入力部１０２から渡された輝度成分画像が１／４に縮小された画像となる。なお、本実施形態における縮小画像は、線形補間による縮小方法により生成するものとするが、他の縮小方法が用いられてもよい。
【００２６】
次に、ステップＳ３０４において、局所特徴点抽出部１０４は、縮小画像生成部１０３から渡されたｎ枚の縮小画像それぞれにおいて、画像の回転があってもロバストに抽出されるような特徴点（回転不変の性質を持つ特徴点）を抽出する。そして、局所特徴点抽出部１０４は、抽出した当該回転不変の性質を持つ特徴点を局所特徴量算出部１０５に渡す。なお、本実施形態では、回転不変の性質を持つ特徴点の抽出方法としてHarris作用素（非特許文献１）を用いる。具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素および当該画素の８近傍にある画素（合計９画素）の画素値を調べる。そして、当該画素が局所極大（当該９画素の中で当該画素の画素値が最大になる）になる点を回転不変の性質を持つ特徴点として抽出する。このとき、当該画素が局所極大になったときでも、当該画素の値がしきい値以下の場合には回転不変の性質を持つ特徴量として抽出しないようにする。なお、回転不変の性質を持つ特徴点を抽出可能な方法であれば、本実施形態で用いた特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部１０４に適用可能である。
【００２７】
次に、局所特徴量算出部１０５では、局所特徴点抽出部１０４から渡された回転不変の性質を持つ特徴点それぞれについて、ステップＳ３０５により画像の回転があっても不変となる局所特徴量（回転不変の性質を持つ局所特徴量）を算出する。抽出した当該回転不変の性質を持つ局所特徴量は座標情報と関連付けされた上で、特徴量登録部１０６に渡される。ここで、本実施形態では、回転不変の性質を持つ特徴量の算出方法としてLocalJet（非特許文献２）およびそれらの導関数の組み合わせを用いる。具体的には、式（１）に示す回転不変の性質を持つ特徴量を算出する。
【数１】
【００２８】
ただし、式（１）右辺で用いている記号は以下に示す式（２）から式（７）で定義される。ここで、式（２）はガウス関数と画像との畳み込み演算である。
【数２】
【００２９】
なお、回転不変の性質を持つ特徴量を算出可能な方法であれば、本実施形態で用いた特徴量算出方法に限らず、どのような特徴量算出方法でも局所特徴量算出部１０５に適用可能である。
【００３０】
次に、ステップＳ３０６において、対称領域抽出部１０８は局所特徴点及びそれらの局所特徴量を用いて登録画像１０１から対称性を有する部分画像（対称領域）を抽出する。そして、ステップＳ３０７において、特徴量登録部１０６は、局所特徴量算出部１０５から渡された回転不変の性質を持つ特徴量と画像入力部１０２から渡された登録画像１０１とを関連付けて画像特徴データベース１０７に登録する。このとき、特徴量登録部１０６は、対称領域抽出部１０８から渡された対称領域に基づいて画像特徴データベース１０７に登録される特徴点を分類する。以下、画像中から特徴点の類似性に基づいて対称な部分領域を抽出する処理（ステップＳ３０６）、及びそれらを登録する処理（ステップＳ３０７）について図４のフローチャートを用いて説明する。
【００３１】
ステップＳ４０１によって示されている、画像中の特徴点の抽出および特徴量の計算は、上述したステップＳ３０４，Ｓ３０５の処理に該当する。次に、ステップＳ４０２にて、対称領域抽出部１０８は、特徴点の類似性に基づく対称領域の抽出を行う。ステップＳ４０２の処理については図８のフローチャートを用いて後で詳しく説明を行う。ステップＳ４０３において、対称領域抽出部１０８は、ステップＳ４０２で抽出した対称領域においてアフィン変換係数を求めるのに用いる部分対称領域を決定する。以下、図７を用いてその目的を説明する。なお、ステップＳ４０３の処理の詳細は図８のフローチャートにより後述する。
【００３２】
図７の（ａ）がクエリ画像で、図７の（ｂ）が比較するべき比較先画像とする。クエリ画像から２点を選択して、これに類似する特徴点を図７の（ｂ）の比較先画像から決定する。このとき、図７の（ａ）、（ｂ）に示した画像は左右対称であるため、図７の（ａ）の左下の特徴点に対応する特徴点として、比較先画像における対称軸の反対側の領域から特徴点を選択してしまうことがありえる。この誤って選択された２点により画像を同じ回転状態、拡大縮小率に揃えようとすると、図７の（ｃ）の様な誤った変換を行ってしまう。これを避けるためには、図７の（ａ）のクエリ画像から選択する特徴点も、図７の（ｂ）の比較先画像から選択する特徴点も、アフィン変換決定のためには、対称領域の同じ側から取るようにする必要がある。以下、対称領域の一方の第１の領域を甲、他方の第２の領域を乙と称する。
【００３３】
次に、ステップＳ４０４にて、特徴量登録部１０６は、対称領域以外の非対称領域に存在する特徴点の特徴量を画像特徴データベース１０７に記憶する。ここで記憶される特徴点及び特徴量に関して、対称領域情報としてＮＵＬＬが記憶される。次いで、ステップＳ４０５にて、特徴量登録部１０６は、対称領域に存在する特徴点のうち、領域甲に含まれる特徴点の特徴量をデータベース１０７に記憶する。ここで記憶される特徴点及び特徴量に関して、対称領域情報として甲が記憶される。更に、ステップＳ４０６にて、特徴量登録部１０６は、対称な特徴点のうち、領域乙に含まれる特徴点の特徴量をデータベース１０７に記憶する。ここで記憶される特徴点及び特徴量に関して、対称領域情報として乙が記憶される。
【００３４】
本実施形態では、データベース１０７に記憶された対称領域情報を用いて、画像検索時においてアフィン変換の係数を求めるために使用する特徴点の対の選択を限定する。この点については、［画像の検索処理］において詳述する。
【００３５】
次に、図８を用いて、上述した対称領域の抽出処理（ステップＳ４０２、Ｓ４０３）について説明する。
【００３６】
まず、ステップＳ８０１にて、対称領域抽出部１０８は、画像中の特徴点について総当りで類似度を求め、閾値ＴＨ１以上の類似度を持つ特徴点の対（ペア）を求める。本例では、その対の個数をＮＰとする。この閾値処理により、良質な類似特徴点の候補ペアが作成される。
【００３７】
次に、ステップＳ８０２にて、対称領域抽出部１０８は、ステップＳ８０１で抽出されたＮＰ個の特徴点の対の中点を求め、当該中点に対して当該２つの特徴点の平均画素値を与える。そして、ステップＳ８０３にて、対称領域抽出部１０８は、これら複数組の特徴点の対から得られる中点群に関してハフ変換を行う。ハフ変換は公知のもので良く、画像上の直線成分を検出するのに一般的に用いられる方法である。目的は、中点からなる直線、即ち対称軸の直線を得る事に有る。
【００３８】
以下、図９を用いて、本実施形態によるハフ変換の概略を説明する。図９の（ａ）において、Ｘ−Ｙ平面上に、Ｐ1、Ｐ2、Ｐ3の３点が有り、今、Ｐ2に着目する。
【００３９】
この直線に原点から垂線を下ろし、その長さをρ、ｘ軸とのなす角をθとすれば、
ρ＝ｘ cosθ＋ｙ sinθ
と表す事が出来る。この様に、極座標系では、１点（ρ, θ）が判れば一つの直線が定まることになる。ここで、点（ρ,θ）を直線ｙ＝ａｘ＋ｂのハフ変換と呼ぶ。また、ｘ−ｙ座標系の一点（ｘ0, ｙ0）を通る傾きの異なる直線の集まりは、
ρ＝ｘ0 cosθ＋ｙ0sinθ
というように表現することができる。このとき、図９の（ａ）に示す３点の各点を通る直線群の軌跡をρ−θ平面に書いたグラフが図９の（ｂ）である。もし、この３点が同一直線上に乗っているとすればρとθの値は同じ値となるはずであり、それら３点に対応するρ−θ平面上の軌跡は１点で交わることになる。この原理を利用して、特徴点対の中点が直線上（対称軸）に乗っているかどうかを検証することが出来る。
【００４０】
ステップＳ８０４において、対称領域抽出部１０８は、ハフ平面ρ−θ上で各点での曲線の交差数に対して閾値処理を行い、閾値を超えた点をＮＬ個得る。値の高い点が、中点を通る直線を表す曲線の交点であるという推定に基づく処理である。この閾値処理により、尤もらしい対称軸を成す直線を得る。
【００４１】
ステップＳ８０５において、対称領域抽出部１０８は、ステップＳ８０４で得た閾値越えの点から着目するべき１つめの点をセットする。そして、ステップＳ８０６で閾値越えの点に対する処理が全て終えてなければ処理をステップＳ８０７に分岐する。閾値越えの点に対する処理が全て終えていれば、ステップＳ８１１で、対称領域数ＮＬと、各対称領域における対称な特徴点のペアと対称軸の直線の式とを記憶し、処理を終了する。
【００４２】
ステップＳ８０７において、対称領域抽出部１０８は、ｉ番目の点を逆ハフ変換し、ｉ番目の対称軸を得る。そして、ステップＳ８０８にて、ＮＰ個の特徴点対の中から、ｉ番目の対称軸近傍に中点があるペアを求める。
【００４３】
ステップＳ８０９にて、対称領域ｉにおける対称な特徴点のペアと、対称軸の直線の式を記憶し、ステップＳ８１０にて、着目する閾値超えの点を次に切り替えるべくｉをインクリメントする。その後、処理は再びステップＳ８０６に戻る。
【００４４】
以上の処理により、画像から複数の対称領域を得て、更に対称な特徴点のペアを得る事が出来る。
【００４５】
次に、図１０を用いて、対称性を有する部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを第１領域（甲）と第２領域（乙）に決定する方法を説明する。本実施形態では、対称性を有する部分画像における画像特徴の傾向に基づいて第１領域と第２領域が決定される。
【００４６】
ステップＳ１００１にて、対称領域抽出部１０８は、指定された対称軸の直線の式と対称な特徴点のペアから対称領域の矩形座標を推定する。より具体的には、指定された対称軸と対称な特徴点のペアを包含し、且つ当該対称軸に対して対称な矩形領域を推定する。
【００４７】
次に、ステップＳ１００２にて、対称領域抽出部１０８は、図１１に示す様に、対称軸と垂直な直線で推定された対称領域の矩形を均等４分割する。
【００４８】
次に、ステップＳ１００３にて、対称領域抽出部１０８は、４分割領域の各々の平均輝度を求める。そして、ステップＳ１００４にて、４分割領域のうち平均輝度の小さい分割領域を対称領域の反時計回り側に持つ対称領域の一方を甲、他方を乙と決定する。例えば、図１１に示されるように、平均輝度の小さい分割領域（輝度値＝２０）が反時計回り側に存在する領域が甲に、平均輝度の小さい分割領域が時計回り側に存在する領域が乙に決定される。このように、上記処理によれば、対称軸により分割された２つの部分領域の各々における濃度勾配の方向により、当該２つの部分領域のそれぞれを甲、乙のいずれかにラベル付けされる。
【００４９】
もちろん、平均輝度の大きい分割領域の方を選択しても良く、要は、一貫性の有る分割領域の選択が出来れば良い。また、平均輝度以外にも、各領域に含まれる特徴点の個数に着目するなど、他の特徴量を用いる事ももちろん可能である。即ち、対称性を有する部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれは、当該部分画像もしくは部分領域における画像特徴の傾向に基づいて第１領域（甲）と第２領域（乙）にラベル付けされる。
【００５０】
以上のようにして、対称領域における対の領域を甲、乙に決定することにより、例えば、図１２の様に時計回りに９０度回転された状態であっても、図１３の様に反時計回りに９０度回転された状態であっても、一意に着目すべき部分対称領域を決定できる。
【００５１】
以上のように甲と乙を決定した上で、特徴量登録部１０６は、ステップＳ３０６により局所特徴量算出部１０５から渡された回転不変の性質を持つ特徴量と画像入力部１０２から渡された登録画像１０１とを関連付け、画像特徴データベース１０７に登録する。以上で画像登録処理が終了する。
【００５２】
［画像の検索処理］
次に、画像検索の際に行う各部の動作について説明する。図６は画像検索装置２００による検索処理の手順を表すフローチャートである。
【００５３】
本処理例では、縮小変換と回転変換による合成した局所特徴量の揺らぎ考慮した処理構成とする。
【００５４】
ステップＳ６０１において、画像入力部２０２（図２）は、クエリ画像２０１を読み込む。
【００５５】
次に、ステップＳ６０２において、画像入力部２０２の輝度成分画像生成部２１１は、当該クエリ画像２０１から輝度成分を抽出して輝度成分画像を生成し、生成した輝度成分画像を縮小画像生成部２０３に渡す。
【００５６】
次に、ステップＳ６０３において、縮小画像生成部２０３は、画像入力部２０２から渡された輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成して当該縮小画像を局所特徴点抽出部２０４に渡す。ただし、倍率ｐおよび縮小画像の枚数ｎは前述の画像登録装置１００における画像の登録処理で用いた値と同じ値にする。
【００５７】
次に、ステップＳ６０４において、局所特徴点抽出部２０４は、縮小画像生成部２０３から渡されたｎ枚の縮小画像それぞれにおいて、画像の特徴点（回転不変の性質を持つ特徴点）を抽出する。抽出した当該回転不変の性質を持つ特徴点は局所特徴量算出部２０５に渡される。ここで本実施形態では、回転不変の性質を持つ特徴点の抽出方法として前述の画像の登録処理で用いた方法と同様に、Harris作用素を用いる。より具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素および当該画素の８近傍にある画素（合計９画素）の画素値を調べられる。そして、当該画素が局所極大（当該９画素の中で当該画素の画素値が最大になる）になる点が回転不変の性質を持つ特徴点として抽出される。このとき、当該画素が局所極大になったときでも、当該画素の値があらかじめ定められたしきい値以下の場合には回転不変の性質を持つ特徴量として抽出しないようにする。なお、回転不変の性質を持つ特徴点を抽出可能な方法であれば、本実施形態で用いた特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部２０４に適用可能である。
【００５８】
次に、ステップＳ６０５において、局所特徴量算出部２０５は、局所特徴点抽出部２０４から渡された回転不変の性質を持つ特徴点それぞれについて、画像の回転があっても不変となる局所特徴量（回転不変の性質を持つ局所特徴量）を算出する。ここで、回転不変の性質を持つ特徴量の算出方法は前述の画像の登録処理で用いた方法と同じ方法を使用する。すなわち、本実施形態では、LocalJetおよびそれらの導関数の組み合わせを用い、式（１）に示す回転不変の性質を持つ特徴量を算出する。
【００５９】
次に、ステップＳ６０６において、対称領域抽出部２０６は、ステップＳ６０４，Ｓ６０５で取得された特徴点及びその特徴量に基づいて、当該クエリ画像から対称領域（対称性を有する部分画像）を抽出する。この処理は、ステップＳ３０６の処理と同様である。そして、ステップＳ６０７において、特徴比較部２０７は、局所特徴点抽出部２０４及び局所特徴量算出部２０５から渡された回転不変の性質を持つ特徴点及びその特徴量と画像特徴データベース１０７に登録されている特徴量とを比較する。この比較は、画像特徴データベース１０７に登録されている登録画像ごとに、対称領域抽出部２０６から渡された対称領域の抽出結果を参照して実施される（詳細は後述）。そして、比較の結果として登録画像ごとに類似度を算出する。類似度の算出方法については後述する。
【００６０】
次に、ステップＳ６０７では、算出した当該類似度と当該類似度の算出元となった画像とを関連付けて検索結果リストを作成した後、当該類似度を降順にソートする。その後、類似度が大きい画像と当該画像の類似度とをソート順に検索結果２０８として出力する。
【００６１】
［類似度の算出方法］
次に、本実施形態における局所特徴量の比較方法（図６のＳ６０７）を、図１４〜図１６のフローチャートを参照して説明する。
【００６２】
図１４は、本実施形態による比較処理の全体を示すフローチャートである。ステップＳ１４０１にて、特徴比較部２０７は、クエリ画像２０１の対称性の有無（対称領域の存否）を判定する。クエリ画像２０１における対称性の有無に応じて、類似度演算の処理はステップＳ１４０２とステップＳ１４０３のいずれかに切り替わる。ステップＳ１４０４において、特徴比較部２０７は、ステップＳ１４０２とステップＳ１４０３のどちらかで得た類似度を出力する。
【００６３】
次に、ステップＳ１４０２の類似度演算処理の詳細を、図１５のフローチャートを用いて説明する。
【００６４】
ここで、局所特徴量算出部２０５から渡された回転不変の性質を持つ特徴量をＶｓ、回転不変の性質を持つ特徴量に関連付けされている座標をＳ（x，y）とする。また、画像特徴データベース１０７に登録されている比較先画像Ｒ上に存在する回転不変の性質を持つ特徴量をＶｑ、回転不変の性質を持つ特徴量に関連付けされている座標をＱ（x’，y’）とする。
【００６５】
以下、特徴比較部２０７による類似度の算出手順を図１５に示すフローチャートに従って説明する。類似度の算出では、まず、ステップＳ１５０１により、最終投票数を表す変数VoteMaxを０に初期化する。
【００６６】
次に、ステップＳ１５０２において、特徴比較部２０７は、画像特徴データベース１０７に登録されている画像Ｒ上に存在する特徴量のうち、領域甲に含まれるＶｑと、領域甲に含まれるＶｓとの特徴量間距離をすべての組み合せについて計算する。そして、クエリ画像２０１の領域甲に含まれるＶｑの各々について特徴量間距離が最短となる、比較先画像の領域甲に含まれるＶｓとの組み合わせを示す最短距離対応点リスト１を作成する。
【００６７】
換言すれば、クエリ画像が対称性のあるものである場合には、対称領域のうちの部分領域甲に含まれる特徴点だけから最短距離対応点リストを作成するという事である。
【００６８】
更に、ステップＳ１５０３にて、特徴比較部２０７は、画像特徴データベース１０７に登録されている画像Ｒ上に存在する回転不変の性質を持つ特徴量ＶｑとＶｓのうち、
・領域乙に含まれるＶｑとＶｓ、および
・非対称領域に含まれるＶｑとＶｓ、
のそれぞれで、すべての組み合せについて特徴量間距離を計算し、最短距離対応点リスト１に追記する形で最短距離対応点リスト２を作成する。
【００６９】
即ち、最短距離対応点リスト２は、領域甲、領域乙と非対称領域ごとに、類似する特徴点（対応する特徴点）を求めた結果がマージされたリストとなる。
【００７０】
この最短距離対応点を求める際に、先に、クエリ画像の各特徴点に対して記憶しているマハラノビスの距離を算出するための観測値をX=(X1,X2,…,Xp)'とし、母集団ｊの分散共分散行列Σjの逆行列Σj-1と平均（重心）μj=(μ1j,μ2j,…,μpj)'(j=1,2,…,k)とを用いて式（８）に基づいて距離ｄjを求める。そして、求めた距離と分散共分散逆行列を含む最短距離対応点リストを作成する。
【００７１】
ｄj2=(Ｘ−μj)'Σj-1(Ｘ−μj) …（８）
すなわち、計算した特徴量間距離がしきい値Ｔｖ以下となり、かつ、最短距離となるようなＶｑとＶｓとの組合せ（対応点）を抽出し、これを最短距離対応点リストに登録する。以後、本実施形態の説明では、最短距離対応点リストに登録された対応点について、当該対応点の回転不変の性質を持つ特徴量をそれぞれＶｑ（ｋ）とＶｓ（ｋ）と記載する。また、Ｖｑ（ｋ）とＶｓ（ｋ）に対応付けられている座標についてはそれぞれＱk（x’k，y’k）、Ｓk（xk，yk）などと添え字をあわせて記載する。また、ステップＳ１５０３で作成された最短距離対応点リスト２に登録された対応点の組数をｍ組とする。最短距離対応点リスト２には、対応点リスト１の対応点（甲の対応点）＋乙の対応点＋非対称領域の対応点が登録されている。
【００７２】
次に、ステップＳ１５０４において、特徴比較部２０７は、類似度算出処理の反復カウント数を表す変数Countを０に初期化する。そして、ステップＳ１５０５において、特徴比較部２０７は、反復カウント数Countがあらかじめ定めた最大反復処理回数Ｒｎを超えていないか判定する。超えている場合はステップＳ１５２０で類似度変換処理を行い、本処理を終了する。超えていない場合は、処理はステップＳ１５０６に移る。ステップＳ１５２０における総合類似度算出処理に関する詳細は、後に説明する。
【００７３】
ステップＳ１５０６において、特徴比較部２０７は、投票数を表す変数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を使って式（１１）から式（１４）で表される。
【００７７】
【数５】
【００７８】
次に、ステップＳ１５０９では、対応点選択変数ｋを０に初期化する。
【００７９】
次に、ステップＳ１５１０において、特徴比較部２０７は、対応点選択変数ｋが当該最短距離対応点リスト２に登録されている対応点の組数ｍを超えていないか判定する。超えていると判定された場合はステップＳ１５１７に処理を移すが、これについては後述する。ステップＳ１５１０における判定で対応点選択変数ｋが当該最短距離対応点リスト２に登録されている対応点の組数ｍを超えていない場合はステップＳ１５１１に処理を移す。
【００８０】
ステップＳ１５１１では、当該最短距離対応点リスト２からランダムに１組の点Ｓk（ｘk，ｙk）、Ｑk（x’k，y’k）を選択する。
【００８１】
次に、ステップＳ１５１２において、特徴比較部２０７は、Ｓk（ｘk，ｙk）が式（９）を使って変換される座標Ｓ’k（ｘ’k，ｙ’k）を求める。
【００８２】
その後、ステップＳ１５１３において、特徴比較部２０７は、座標Ｓ’k（ｘ’k，ｙ’k）と座標Ｑk（ｘ’k，ｙ’k）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離がしきい値Ｔｄ以下であるかどうかを判定する。当該ユークリッド距離がしきい値Ｔｄ以下の場合には、ステップＳ１５１４において、Voteに対する対応点の対Ｓ’k,Ｑkを記憶する。そして、ステップＳ１５１５において投票数Voteをインクリメントし、ステップＳ１５１６に処理を移す。一方、当該ユークリッド距離がしきい値Ｔｄより大きい場合には、何もせずにステップＳ１５１６に処理を移す。ステップＳ１５１６では、対応点選択変数ｋをインクリメントし、ステップＳ１５１０に処理を戻す。
【００８３】
次に、ステップS１５１０において対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていた場合の処理であるステップＳ１５１７を説明する。ステップＳ１５１７において、特徴比較部２０７は、投票数Voteの値と最終投票数VoteMaxの値とを比較し、投票数Voteの値が最終投票数VoteMaxの値よりも大きい場合はステップＳ１５１８の処理を実行する。特徴比較部２０７は、ステップＳ１５１８において最終投票数VoteMaxの値を投票数Voteの値で置き換え、ステップＳ１５１９でCountを１つインクリメントした後、ステップＳ１５０５に処理を戻す。一方、ステップＳ１５１７において投票数Voteの値が最終投票数VoteMaxの値以下の場合は、何もせずにステップＳ１５１９でCountを１つインクリメントした後、ステップＳ１５０５に処理を戻す。
【００８４】
ステップＳ１５２０では図１７に示す単調現象特性の最終投票数−類似度変換テーブルにより最終投票数について類似度変換を行い、最終的な類似度を得る。
【００８５】
なお、本実施形態における類似度の算出方法の説明では、相似変換を考慮して説明したが、アフィン変換などその他の幾何学変換についても、ステップＳ１５０８においてそれぞれに応じた変換行列を求めることにより対応可能である。たとえば、アフィン変換の場合は、まず、ステップＳ１５０７でランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ１５０８において式（９）ではなく前述した式（８）を使うこととし、ステップＳ１５０７で選択した３組の対応点（合計６点）を使って変数ａ〜ｆを求めればよい。
【００８６】
次に、図１４のステップＳ１４０１においてクエリ画像に対称性が無いと判定された場合の処理（ステップＳ１４０６）を図１６を用いて説明する。なお、図１５により上述した処理との差分について説明する。
【００８７】
先の図１５に示した処理との差は、クエリ画像に対称性が無いのでステップＳ１６０２にて画像全体の特徴点に対して最短距離対応点リスト１を作成する所である。（対Ｓ１５０２、Ｓ１５０３）
また、当然、Ｓ１６０６、Ｓ１６１０では最短距離対応点リスト１から、幾何変換を行う特徴点の対を選ぶ事になる。
【００８８】
更に、ステップＳ１６０６で選択した幾何変換の基準となる２対の点をステップＳ１６１０で再び選択しないように、ステップＳ１６０８でｋの初期値を３（ｋ＝３）とする所も異なる。
【００８９】
その他の処理（ステップＳ１６０１、Ｓ１６０３〜Ｓ１６０５、Ｓ１６０７、Ｓ１６０９、Ｓ１６１１〜Ｓ１６１９）は、図１５（Ｓ１５０１、Ｓ１５０４〜Ｓ１５０６、Ｓ１５０８、Ｓ１５１０、Ｓ１５１２〜Ｓ１５２０）と同様の処理を行う。
【００９０】
以上のように、第１実施形態によれば、幾何的に対称な部分が存在する画像の検索に関して、類似する特徴点の組み合わせを適切にし、無為に対応点候補個数を増やさないで検索することが可能になる。
【００９１】
＜第２実施形態＞
第１実施形態では、対称軸を求めるにあたりハフ変換を用いたが、これに限られるものではない。第２実施形態は、ハフ変換を用いず、別の方法で対称領域を求める例であり、その他の処理は第１実施形態と同様である。
【００９２】
図１８にそのフローを示し、説明する。
【００９３】
まず、ステップＳ１８０１にて、対称領域抽出部１０８（２０６）は、画像中の特徴点を総当りで類似度を求め、閾値ＴＨ１以上の類似度を持つ特徴点の対を求めるその個数をＮＰとする。この閾値処理により、良質な類似特徴点の候補ペアを作成する。
【００９４】
次に、ステップＳ１８０２にてＮＰ個の類似特徴点ペアの中点を求め、ステップＳ１８０３にてカウンタｉを１にセットし、ＮＣ＜（ＮＰ＊（ＮＰ−１）／２）なるＮＣを定める。そして、ステップＳ１８０４においてｉ≦ＮＣを満たす間、ステップＳ１８０５〜Ｓ１８０７，Ｓ１８１８の処理を行い、満たさなくなった場合にステップＳ１８１９に分岐する。ここで、ＮＰ＊（ＮＰ−１）／２とは、ＮＰ個の点から任意の２点を選ぶ組合せの数である。
【００９５】
ステップＳ１８０５において、対称領域抽出部１０８（２０６）は、ＮＰ個の中点群からランダムに２点を選択し、ステップＳ１８０６にて２点間の直線を求める。
【００９６】
次に、Ｓ１８０７において、対称領域抽出部１０８（２０６）は、ＮＰ個の中点群と、直線の距離を求め、それらを足し合わせて累積距離を求める。そして、ステップＳ１８１８において、ｉと累積距離と選んだ２点とその直線の式を記憶し、ステップＳ１８０４に処理を戻す。
【００９７】
なお、ステップＳ１８０７で距離の総和としたが、もちろん二乗距離の総和を累積距離としても良い。
【００９８】
ステップＳ１８１９において、対称領域抽出部１０８（２０６）は、求めた距離の総和或いは二乗距離が最小と成るi_MINとその距離DMINを求める。そして、ステップＳ１８２０において、DMINが閾値ＴＨ２以下であれば対称軸・対称領域が有るとしてステップＳ１８２１に進む。一方、DMINが閾値ＴＨ２より大きい場合は、ステップＳ１８２０からステップＳ１８２４に進み、対称領域が無いと判断され、本処理は終了する。
【００９９】
ステップＳ１８２１において、対称領域抽出部１０８（２０６）は、i_MINに対応する直線を対称軸とする。そして、ステップＳ１８２２において、対称領域抽出部１０８（２０６）は、ＮＰ個の特徴点対の中から対称軸近傍に中点があるペアを求める。次に、ステップＳ１８２３において、対称領域抽出部１０８（２０６）は、対称軸近傍に中点を持つ特徴点ペアを包含し、対称軸を中心とする矩形領域を求め、これを対称領域として本処理を終了する。
【０１００】
これらの処理により、画像中の支配的な対称領域を検出する事が出来る。なお、上記処理では、最小の累積距離を持つ１つの直線に関して、その累積距離が閾値ＴＨ２より小さい場合に、対応する直線を対称軸とした。しかしながら、これに限られるものではなく、例えば、累積距離がある閾値よりも小さくなる１又は複数の直線を抽出して、これら直線を対称軸として扱うようにしてもよい。
【０１０１】
なお、上記の処理では、厳密な対称軸が求まらない恐れもあるが、発明の趣旨は、対称領域の部分対称領域甲乙を決定し、高と乙を意識して特徴点を扱う事であるので、厳密な対称軸を求める必要は無い。もちろん、その他の簡易な方法で対称領域ならびに甲乙を定める方法があれば、それを用いても構わない。
【０１０２】
＜第３実施形態＞
クエリ画像の対称性を検証して対称性が有る（対称領域が存在する）と判定された場合、対称性が無い（対称領域が存在しない）登録画像は比較する価値が無い。そこで、クエリ画像が対称性の有る画像の場合に、登録画像の対称性解析において求めた対称領域数ＮＬが０でない物のみを比較対象とすることで、大幅な処理の簡素化が行え、検索を高速に行うことが可能となる。
【０１０３】
なお、クエリ画像自体を回転や拡大・縮小して特徴点における特徴量の分布を求めておき、ある特徴点の比較の際に．回転や拡大・縮小による変動幅で正規化した類似距離を求めた上で複数の特徴点による総合類似度を求めるようにしてもよい。このようにすれば、それぞれの特徴点における距離が等価なものと出来、類似距離の精度向上、回転や拡大・縮小によるばらつきの低減が期待できる。
【０１０４】
以上のように、上記各実施形態によれば、幾何的に対称な画像（或いはそのような対称領域を有する画像）の検索に対する、検索処理の速度の向上、検索の高精度化を達成できる。
【０１０５】
＜その他の実施形態＞
以上、実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【０１０６】
尚、本発明は、ソフトウェアのプログラムをシステム或いは装置に直接或いは遠隔から供給し、そのシステム或いは装置のコンピュータが該供給されたプログラムコードを読み出して実行することによって前述した実施形態の機能が達成される場合を含む。この場合、供給されるプログラムは実施形態で図に示したフローチャートに対応したコンピュータプログラムである。
【０１０７】
また、コンピュータが、コンピュータ読み取り可能な記憶媒体に格納されたプログラムを読み出し、読み出したプログラムを実行することによって、前述した実施形態の機能が実現され手もよい。また、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどとの協働で実施形態の機能が実現されてもよい。この場合、ＯＳなどが、実際の処理の一部または全部を行ない、その処理によって前述した実施形態の機能が実現される。
【特許請求の範囲】
【請求項１】
入力されたクエリ画像と類似する画像を登録されている画像から検索する画像検索装置であって、
前記クエリ画像において、特徴点の特徴量に基づいて互いに対応する特徴点の対を取得し、取得された特徴点の対に基づいて対称性を有する部分画像を抽出する抽出手段と、
前記部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを、当該部分画像における画像特徴の傾向に基づいて第１領域と第２領域に決定する決定手段と、
前記クエリ画像と登録されている比較先画像について、両画像の前記第１領域に決定されている部分領域に存在する特徴点から特徴量に基づいて少なくとも２組の対応する特徴点の対を抽出し、抽出した各対の特徴点の座標が一致するように前記両画像のうちの一方の画像の特徴点を変換するための座標変換係数を設定する設定手段と、
前記両画像の類似を判定するために、前記両画像に存在する特徴点から特徴量に基づいて互いに対応する特徴点の対を抽出し、前記一方の画像について抽出された特徴点の座標を前記座標変換係数を用いた座標変換処理によって変換し、変換後の特徴点の座標と前記両画像のうちの他方の画像における特徴点の座標とを比較する比較手段とを備えることを特徴とする画像検索装置。
【請求項２】
前記比較手段は、前記両画像の、前記第１領域に決定された領域、前記第２領域に決定された領域、前記抽出手段で抽出された対称性を有する部分画像を除いた非対称領域、のそれぞれの領域ごとに、対応する特徴点の対を抽出することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記特徴点は回転不変の性質をもつ特徴点であり、前記特徴量は回転不変の性質を持つ局所特徴量であることを特徴とする請求項１又は２に記載の画像検索装置。
【請求項４】
前記抽出手段において前記クエリ画像から対称性を有する部分画像が抽出されなかった場合は、前記設定手段は、前記両画像の全体から少なくとも２組の対応する特徴点の対を抽出することを特徴とする請求項１に記載の画像検索装置。
【請求項５】
前記決定手段は、前記２つの部分領域の各々における濃度勾配の方向により、当該２つの部分領域のそれぞれを前記第１領域と前記第２領域に決定することを特徴とする請求項１乃至４のいずれか１項に記載の画像検索装置。
【請求項６】
前記決定手段は、前記２つの部分領域のそれぞれに存在する特徴点の個数の多い少ないにより、当該２つの部分領域のそれぞれを前記第１領域と前記第２領域に決定することを特徴とする請求項１乃至４のいずれか１項に記載の画像検索装置。
【請求項７】
前記第１領域に決定されている部分領域が存在しない比較先画像に対しては、前記クエリ画像との類似の判定を実施しないことを特徴とする請求項１乃至３のいずれか１項に記載の画像検索装置。
【請求項８】
前記抽出手段は、前記クエリ画像より取得された複数組の特徴点の対より得られる中点群に対してハフ変換を適用することにより対称軸を求め、該対称軸の近傍に中点を持つ特徴点の対を包含する領域を前記対称性を有する部分画像として抽出することを特徴とする請求項１乃至７のいずれか１項に記載の画像検索装置。
【請求項９】
前記抽出手段は、前記クエリ画像より取得された複数組の特徴点の対より得られる中点群から選択された２点を通る直線群のうち、前記中点群からの累積距離が最小となる直線を対称軸とし、該対称軸の近傍に中点を持つ特徴点の対を包含する領域を前記対称性を有する部分画像として抽出することを特徴とする請求項１乃至７のいずれか１項に記載の画像検索装置。
【請求項１０】
入力されたクエリ画像と類似する画像を登録されている画像から検索する画像検索方法であって、
前記クエリ画像において、特徴点の特徴量に基づいて互いに対応する特徴点の対を取得し、取得された特徴点の対に基づいて対称性を有する部分画像を抽出する抽出工程と、
前記部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを、当該部分画像における画像特徴の傾向に基づいて第１領域と第２領域に決定する決定工程と、
前記クエリ画像と登録されている比較先画像について、両画像の前記第１領域に決定されている部分領域に存在する特徴点から特徴量に基づいて少なくとも２組の対応する特徴点の対を抽出し、抽出した各対の特徴点の座標が一致するように前記両画像のうちの一方の画像の特徴点を変換するための座標変換係数を設定する設定工程と、
前記両画像の類似を判定するために、前記両画像に存在する特徴点から特徴量に基づいて互いに対応する特徴点の対を抽出し、前記一方の画像について抽出された特徴点の座標を前記座標変換係数を用いた座標変換処理によって変換し、変換後の特徴点の座標と前記両画像のうちの他方の画像における特徴点の座標とを比較する比較工程とを有することを特徴とする画像検索方法。
【請求項１１】
請求項１０に記載の画像検索方法をコンピュータに実行させるコンピュータプログラム。
【請求項１２】
請求項１０に記載の画像検索方法をコンピュータに実行させるコンピュータプログラムを格納したコンピュータ読み取り可能な記憶媒体。
【請求項１】
入力されたクエリ画像と類似する画像を登録されている画像から検索する画像検索装置であって、
前記クエリ画像において、特徴点の特徴量に基づいて互いに対応する特徴点の対を取得し、取得された特徴点の対に基づいて対称性を有する部分画像を抽出する抽出手段と、
前記部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを、当該部分画像における画像特徴の傾向に基づいて第１領域と第２領域に決定する決定手段と、
前記クエリ画像と登録されている比較先画像について、両画像の前記第１領域に決定されている部分領域に存在する特徴点から特徴量に基づいて少なくとも２組の対応する特徴点の対を抽出し、抽出した各対の特徴点の座標が一致するように前記両画像のうちの一方の画像の特徴点を変換するための座標変換係数を設定する設定手段と、
前記両画像の類似を判定するために、前記両画像に存在する特徴点から特徴量に基づいて互いに対応する特徴点の対を抽出し、前記一方の画像について抽出された特徴点の座標を前記座標変換係数を用いた座標変換処理によって変換し、変換後の特徴点の座標と前記両画像のうちの他方の画像における特徴点の座標とを比較する比較手段とを備えることを特徴とする画像検索装置。
【請求項２】
前記比較手段は、前記両画像の、前記第１領域に決定された領域、前記第２領域に決定された領域、前記抽出手段で抽出された対称性を有する部分画像を除いた非対称領域、のそれぞれの領域ごとに、対応する特徴点の対を抽出することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記特徴点は回転不変の性質をもつ特徴点であり、前記特徴量は回転不変の性質を持つ局所特徴量であることを特徴とする請求項１又は２に記載の画像検索装置。
【請求項４】
前記抽出手段において前記クエリ画像から対称性を有する部分画像が抽出されなかった場合は、前記設定手段は、前記両画像の全体から少なくとも２組の対応する特徴点の対を抽出することを特徴とする請求項１に記載の画像検索装置。
【請求項５】
前記決定手段は、前記２つの部分領域の各々における濃度勾配の方向により、当該２つの部分領域のそれぞれを前記第１領域と前記第２領域に決定することを特徴とする請求項１乃至４のいずれか１項に記載の画像検索装置。
【請求項６】
前記決定手段は、前記２つの部分領域のそれぞれに存在する特徴点の個数の多い少ないにより、当該２つの部分領域のそれぞれを前記第１領域と前記第２領域に決定することを特徴とする請求項１乃至４のいずれか１項に記載の画像検索装置。
【請求項７】
前記第１領域に決定されている部分領域が存在しない比較先画像に対しては、前記クエリ画像との類似の判定を実施しないことを特徴とする請求項１乃至３のいずれか１項に記載の画像検索装置。
【請求項８】
前記抽出手段は、前記クエリ画像より取得された複数組の特徴点の対より得られる中点群に対してハフ変換を適用することにより対称軸を求め、該対称軸の近傍に中点を持つ特徴点の対を包含する領域を前記対称性を有する部分画像として抽出することを特徴とする請求項１乃至７のいずれか１項に記載の画像検索装置。
【請求項９】
前記抽出手段は、前記クエリ画像より取得された複数組の特徴点の対より得られる中点群から選択された２点を通る直線群のうち、前記中点群からの累積距離が最小となる直線を対称軸とし、該対称軸の近傍に中点を持つ特徴点の対を包含する領域を前記対称性を有する部分画像として抽出することを特徴とする請求項１乃至７のいずれか１項に記載の画像検索装置。
【請求項１０】
入力されたクエリ画像と類似する画像を登録されている画像から検索する画像検索方法であって、
前記クエリ画像において、特徴点の特徴量に基づいて互いに対応する特徴点の対を取得し、取得された特徴点の対に基づいて対称性を有する部分画像を抽出する抽出工程と、
前記部分画像をその対称軸で分割して得られる２つの部分領域のそれぞれを、当該部分画像における画像特徴の傾向に基づいて第１領域と第２領域に決定する決定工程と、
前記クエリ画像と登録されている比較先画像について、両画像の前記第１領域に決定されている部分領域に存在する特徴点から特徴量に基づいて少なくとも２組の対応する特徴点の対を抽出し、抽出した各対の特徴点の座標が一致するように前記両画像のうちの一方の画像の特徴点を変換するための座標変換係数を設定する設定工程と、
前記両画像の類似を判定するために、前記両画像に存在する特徴点から特徴量に基づいて互いに対応する特徴点の対を抽出し、前記一方の画像について抽出された特徴点の座標を前記座標変換係数を用いた座標変換処理によって変換し、変換後の特徴点の座標と前記両画像のうちの他方の画像における特徴点の座標とを比較する比較工程とを有することを特徴とする画像検索方法。
【請求項１１】
請求項１０に記載の画像検索方法をコンピュータに実行させるコンピュータプログラム。
【請求項１２】
請求項１０に記載の画像検索方法をコンピュータに実行させるコンピュータプログラムを格納したコンピュータ読み取り可能な記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１０−２７２０９２（Ｐ２０１０−２７２０９２Ａ）
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願番号】特願２００９−１２５８４５（Ｐ２００９−１２５８４５）
【出願日】平成２１年５月２５日（２００９．５．２５）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２２年１２月２日（２０１０．１２．２）
【国際特許分類】
【出願日】平成２１年５月２５日（２００９．５．２５）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]