(57)【要約】【課題】  画像の幾何学的な変動に基づく局所特徴量の変動を検定し、変動の大きい局所特徴量を検索時に使わないようにする。【解決手段】  入力画像に類似する画像を検索する際に、画像の局所的な特徴点を抽出し、抽出された特徴点における局所特徴量を算出する。そして局所特徴量における幾何学的な変動に基づく当該局所特徴量の変動を検定し、検定の結果に基づいて、画像の類似度を算出する。【選択図】      図２
2008257469.tif 000002
【特許請求の範囲】
【請求項１】
入力された画像に類似する画像を保持手段に保持された画像から検索する画像処理装置であって、
画像の局所的な特徴点を抽出する特徴点抽出手段と、
前記抽出された特徴点における局所特徴量を算出する局所特徴量算出手段と、
前記画像の幾何学的な変動に基づく当該局所特徴量の変動を検定する局所特徴量検定手段と、
前記検定の結果に基づく特徴点を用いて、前記入力された画像と前記保持手段に保持された画像との類似度を算出する類似度算出手段とを有することを特徴とする画像処理装置。
【請求項２】
前記局所特徴量検定手段は、前記局所特徴量毎に幾何学的な変動を算出し、しきい値に基づいて検定の合格、或いは不合格を判定し、
前記類似度算出手段は、前記局所特徴量算出手段で算出された局所特徴量から前記不合格と判定された局所特徴量を除いて前記類似度を算出することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記幾何学的な変動は、前記画像を回転させた際の前記局所特徴量の変動であることを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
前記類似度算出手段は、前記類似度に従って前記保持手段に保持された画像を検索結果として出力することを特徴とする請求項１乃至３の何れか１項に記載の画像処理装置。
【請求項５】
入力された画像に類似する画像を保持手段に保持された画像から検索する画像処理装置にて実行される画像検索方法であって、
画像の局所的な特徴点を抽出する特徴点抽出工程と、
前記抽出された特徴点における局所特徴量を算出する局所特徴量算出工程と、
前記画像の幾何学的な変動に基づく当該局所特徴量の変動を検定する局所特徴量検定工程と、
前記検定の結果に基づく特徴点を用いて、前記入力された画像と前記保持手段に保持された画像との類似度を算出する類似度算出工程とを有することを特徴とする画像検索方法。
【請求項６】
前記局所特徴量検定工程では、前記局所特徴量毎に幾何学的な変動を算出し、しきい値に基づいて検定の合格、或いは不合格を判定し、
前記類似度算出工程では、前記局所特徴量算出工程で算出された局所特徴量から前記不合格と判定された局所特徴量を除いて前記類似度を算出することを特徴とする請求項５に記載の画像検索方法。
【請求項７】
前記幾何学的な変動は、前記画像を回転させた際の前記局所特徴量の変動であることを特徴とする請求項５又は６に記載の画像検索方法。
【請求項８】
前記類似度算出工程は、前記類似度を算出し、該類似度に従って前記登録画像を検索結果として出力することを特徴とする請求項５乃至７の何れか１項に記載の画像検索方法。
【請求項９】
請求項５乃至８の何れか１項に記載の画像検索方法をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力された画像に類似する画像を検索する画像処理装置及び画像検索方法に関するものである。
【背景技術】
【０００２】
類似画像を検索するための技術が多く提案されている。例えば、画像を複数のブロックに分け、それぞれの画像特徴量（代表色）を用いてパターンマッチングを行うことで色の位置情報を利用して類似画像を検索する方法がある（特許文献１）。しかし、特許文献１に開示された方法の場合、検索時に画像全体から特徴量を計算する必要があるため、例えば画像内の特定オブジェクトが切り取られたり、背景色が変わったりした場合には検索が困難になってしまうという問題があった。
【０００３】
そこで、画像全体の特徴量を使うのではなく、画像の局所的な特徴量（局所特徴量）を使って類似画像を検索する方法が提案されている。これらの方法では、まず画像から特徴的な点（局所特徴点）を抽出する。次に、局所特徴点とその近傍の画像情報とから、その局所特徴点に対する特徴量（局所特徴量）を計算する。画像の検索は、局所特徴量同士のマッチングによって行う。
【０００４】
上述のような局所特徴量を利用する手法において、局所特徴量を回転不変となる複数の要素で構成される量として定義することにより、画像が回転した場合でも、精度良く検索可能な方法が提案されている（非特許文献１）。また同様に、局所特徴量を回転不変となる複数の要素で構成される量として定義することにより、局所特徴量を画像の位置合わせに利用しているものもある（特許文献２）。
【特許文献１】特開平８−２４９３４９号公報
【特許文献２】特開平９−４４６６５号公報
【非特許文献１】C. Schmid and R. Mohr, "Localgray value invariants for image retrieval," IEEE Trans. PAMI., Vol.19, No.5, pp550-534, 1997.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記特許文献２或いは非特許文献１に開示された方法の場合、当該方法で回転不変となるように定義された局所特徴量には、実際には画像回転時のノイズに起因する変動が発生する。図１０は、回転不変として定義された局所特徴量の変動の例を示す図である。図１０では、非特許文献１で定義された局所特徴量の変動を散布図として示している。即ち、画像を０°〜９０°まで１５°ずつ回転させた場合に、同一点で計算した７つの局所特徴量の要素をプロットしたものである。図１０に見られるような局所特徴量の変動が検索精度を低下させるという問題があった。
【０００６】
本発明は、上記課題を解決するためになされたもので、画像の幾何学的な変動に基づく局所特徴量の変動を検定し、変動の大きい局所特徴量を検索時に使わないようにすることを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、入力された画像に類似する画像を保持手段に保持された画像から検索する画像処理装置であって、画像の局所的な特徴点を抽出する特徴点抽出手段と、前記抽出された特徴点における局所特徴量を算出する局所特徴量算出手段と、前記画像の幾何学的な変動に基づく当該局所特徴量の変動を検定する局所特徴量検定手段と、前記検定の結果に基づく特徴点を用いて、前記入力された画像と前記保持手段に保持された画像との類似度を算出する類似度算出手段とを有することを特徴とする。
【０００８】
また、本発明は、入力された画像に類似する画像を保持手段に保持された画像から検索する画像処理装置にて実行される画像検索方法であって、画像の局所的な特徴点を抽出する特徴点抽出工程と、前記抽出された特徴点における局所特徴量を算出する局所特徴量算出工程と、前記画像の幾何学的な変動に基づく当該局所特徴量の変動を検定する局所特徴量検定工程と、前記検定の結果に基づく特徴点を用いて、前記入力された画像と前記保持手段に保持された画像との類似度を算出する類似度算出工程とを有することを特徴とする。
【発明の効果】
【０００９】
本発明によれば、画像の幾何学的な変動に基づく局所特徴量の変動を検定し、変動の大きい局所特徴量を検索時に使わないようにすることで、検索精度の低下を抑制することが可能になる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照しながら発明を実施するための最良の形態について詳細に説明する。
【００１１】
＜第１の実施形態＞
図１は、第１の実施形態における画像登録装置の構成例を示すブロック図である。図１に示すように、画像登録装置１００は、画像入力部１０２、縮小画像生成部１０３、局所特徴点抽出部１０４、局所特徴量算出部１０５、特徴量登録部１０６から構成される。
【００１２】
画像登録装置１００において、縮小画像生成部１０３が画像入力部１０２に入力された登録画像１０１の縮小画像を生成し、局所特徴点抽出部１０４が縮小画像から局所特徴点を抽出する。そして、局所特徴量算出部１０５がその局所特徴点の局所特徴量を算出し、特徴量登録部１０６が入力された登録画像１０１と算出された局所特徴量とを関連付けて画像特徴データベース１０７に登録する。尚、画像登録装置１００にて実行される画像の登録処理については、更に詳述する。また、画像特徴データベース１０７は、入力された画像に類似する画像を保持する保持手段である。
【００１３】
図２は、第１の実施形態における画像検索装置の構成例を示すブロック図である。図２に示すように、画像検索装置２００は、画像入力部２０２、縮小画像生成部２０３、局所特徴点抽出部２０４、局所特徴量算出部２０５、局所特徴量検定部２０６、特徴比較部２０７から構成される。
【００１４】
画像検索装置２００において、縮小画像生成部２０３が画像入力部２０２に入力されたクエリ画像２０１の縮小画像を生成し、局所特徴点抽出部２０４が縮小画像から局所特徴点を抽出する。そして、局所特徴量算出部２０５がその局所特徴点の局所特徴量を算出し、局所特徴量検定部２０６が局所特徴量を検定する。この検定結果は特徴比較部２０７に渡され、特徴比較部２０７が検定結果に基づき、画像特徴データベース１０７からクエリ画像２０１に類似した画像を検索し、検索結果２０８として出力する。尚、画像検索装置２００にて実行される画像の検索処理については、更に詳述する。
【００１５】
［画像の登録処理］
まず、画像を登録する際に行う各部の動作について説明する。図３は、画像の登録処理の手順を表すフローチャートである。ステップＳ３０１で、図１に示す画像入力部１０２が登録画像１０１を読み込み、ステップＳ３０２で、当該登録画像１０１から輝度成分を抽出する。そして、抽出した輝度成分に基づき輝度成分画像を生成し、生成した輝度成分画像を縮小画像生成部１０３に渡す。また、登録画像１０１を後段の特徴量登録部１０６に渡す。
【００１６】
次に、ステップＳ３０３では、縮小画像生成部１０３が画像入力部１０２から渡された当該輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成して当該縮小画像を局所特徴点抽出部１０４に渡す。ただし、倍率ｐ及び縮小画像の枚数ｎは予め決められているものとする。
【００１７】
図４は、縮小画像を生成する縮小画像生成部１０３の処理の一例を示す図である。図４に示す例は、倍率ｐが２の−（１／４）乗、縮小画像の枚数ｎが９の場合である。図４において、４０１は画像入力部１０２から渡された輝度成分画像である。４０２は当該輝度成分画像から倍率ｐに従って４回縮小された縮小画像である。４０３は当該輝度成分画像から倍率ｐに従って８回縮小された縮小画像である。
【００１８】
この例では、縮小画像４０２は画像入力部１０２から渡された輝度成分画像が１／２に縮小された画像となり、縮小画像４０３は画像入力部１０２から渡された輝度成分画像が１／４に縮小された画像となる。尚、画像を縮小する方法は何れの方法でも良く、第１の実施形態では、線形補間による縮小方法により縮小画像を生成するものとする。
【００１９】
次に、ステップＳ３０４では、局所特徴点抽出部１０４が、縮小画像生成部１０３から渡されたｎ枚の縮小画像の各々に画像の回転があってもロバスト（robust）に抽出されるような局所的な特徴点（局所特徴点）を抽出する。ここで、ロバストな局所特徴点とは、画像を回転するときの画像処理で消えることなく安定的に抽出される、強健で耐性のある局所特徴点を意味する。抽出した局所特徴点は局所特徴量算出部１０５に渡される。この局所特徴点の抽出方法として、第１の実施形態ではHarris作用素を用いる。C.Harris and M.J. Stephens, "A combined corner and edge detector," In Alvey Vision Conference, pages 147-152, 1988.参照
具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素及び当該画素の８近傍にある画素（合計９画素）の画素値を調べる。そして、当該画素が局所極大になる（当該９画素の中で当該画素の画素値が最大になる）点を局所特徴点として抽出する。ここで、当該画素が局所極大になったときでも、当該画素の値がしきい値以下の場合には局所特徴点として抽出しないようにする。画素値とは、各画素がどれぐらい局所としてふさわしいかを示す値である。
【００２０】
尚、局所特徴点を抽出可能な方法であれば、上述のHarris作用素による特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部１０４に適用可能である。
【００２１】
次に、ステップＳ３０５で、局所特徴量算出部１０５が、局所特徴点抽出部１０４から渡された局所特徴点の各々に画像の回転があっても不変となるように定義された特徴量（局所特徴量）を算出する。ここで抽出された局所特徴量は座標情報と関連付けられた上で局所特徴量登録部１０６に渡される。この局所特徴量の算出方法として、第１の実施形態ではLocal Jet及びそれらの導関数の組み合わせを用いる。J.J.Koenderink and A.J.van Doorn, "Representation of local geometry in the visual system," Riological Cybernetics, vol.55, pp.367-375, 1987.参照
具体的には、以下の式（１）により局所特徴量を算出する。
【００２２】
【数１】
2008257469.tif 000003
【００２３】
ただし、式（１）の右辺で用いている記号は、以下に示す式（２）から式（７）で定義される。ここで、式（２）右辺のＧ（ｘ，ｙ）はガウス関数、Ｉ（ｘ，ｙ）は画像の座標（ｘ，ｙ）における画素値であり、“＊”は畳み込み演算を表す記号である。また、式（３）は式（２）で定義された変数Ｌのｘに関する偏導関数、式（４）は当該変数Ｌのｙに関する偏導関数である。式（５）は式（３）で定義された変数Ｌｘのｙに関する偏導関数、式（６）は式（３）で定義された変数Ｌｘのｘに関する偏導関数、式（７）は式（４）で定義されたＬｙのｙに関する偏導関数である。
【００２４】
【数２】
2008257469.tif 000004
【００２５】
尚、局所特徴量を算出可能な方法であれば、上述したような特徴量算出方法に限らず、どのような特徴量算出方法でも適用可能である。
【００２６】
次に、ステップＳ３０６で、特徴量登録部１０６が局所特徴量算出部１０５から渡された局所特徴量と画像入力部１０２から渡された登録画像１０１とを関連付けて、画像特徴データベース１０７に登録する。以上で画像の登録処理が終了する。
【００２７】
［画像の検索処理］
次に、画像を検索する際に行う各部の動作について説明する。図５は、画像の検索処理の手順を表すフローチャートである。ステップＳ５０１で、図２に示す画像入力部２０２がクエリ画像２０１を読み込み、ステップＳ５０２で、当該クエリ画像２０１から輝度成分を抽出する。そして、抽出した輝度成分に基づき輝度成分画像を生成し、生成した輝度成分画像を縮小画像生成部２０３に渡す。
【００２８】
次に、ステップＳ５０３では、縮小画像生成部２０３が画像入力部２０２から渡された当該輝度成分画像を倍率ｐに従って順次縮小し、縮小画像をｎ枚生成して当該縮小画像を局所特徴点抽出部２０４に渡す。ただし、倍率ｐ及び縮小画像の枚数ｎは上述した画像の登録処理で用いた値と同じ値にする。
【００２９】
次に、ステップＳ５０４では、局所特徴点抽出部２０４が、縮小画像生成部２０３から渡されたｎ枚の縮小画像の各々に画像の回転があってもロバストに抽出されるような局所的な特徴点（局所特徴点）を抽出する。抽出した局所特徴点は局所特徴量算出部２０５に渡される。この局所特徴点の抽出方法として、上述の画像の登録処理で用いた方法と同様に、Harris作用素を用いる。
【００３０】
具体的には、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素及び当該画素の８近傍にある画素（合計９画素）の画素値を調べる。そして、当該画素が局所極大になる（当該９画素の中で当該画素の画素値が最大になる）点を局所特徴点として抽出する。ここで、当該画素が局所極大になったときでも、当該画素の値がしきい値以下の場合には局所特徴点として抽出しないようにする。
【００３１】
尚、局所特徴点を抽出可能な方法であれば、上述のHarris作用素による特徴点抽出方法に限らず、どのような特徴点抽出方法でも局所特徴点抽出部２０４に適用可能である。
【００３２】
次に、ステップＳ５０５で、局所特徴量算出部２０５が、局所特徴点抽出部２０４から渡された局所特徴点の各々に画像の回転があっても不変となるように定義された特徴量（局所特徴量）を算出する。ここで抽出された局所特徴量は座標情報と関連付けされた上で局所特徴量検定部２０６に渡される。この局所特徴量の算出方法は、上述した画像の登録処理で用いた方法と同じ方法を使用する。即ち、Local Jet及びそれらの導関数の組み合わせを用い、式（１）により局所特徴量を算出する。
【００３３】
次に、ステップＳ５０６で、局所特徴量検定部２０６が、局所特徴量算出部２０５から渡された各々の局所特徴量の変動を検定する。ここで、これ以降の説明を簡略化するため、局所特徴量算出部２０５から渡された局所特徴量を局所特徴量（０°）と記載する。
【００３４】
第１の実施形態における検定では、４５°回転検定を実施する。即ち、局所特徴量算出部１０５、２０５で局所特徴量算出に使ったガウスフィルタを４５°回転させたフィルタ（４５°回転フィルタ）を予め準備しておき、当該４５°回転フィルタを使って検定を実施する。ここで、フィルタを４５°回転させるとは、所定のフィルタ係数に対して幾何学的に回転変換を施すことを意味する。
【００３５】
図７は、ガウスフィルタの一例を示す図である。また、図８は、図７に示すフィルタを４５°回転させたガウスフィルタの一例を示す図である。クエリ画像２０１を回転させるのではなく、ガウスフィルタを回転させている。クエリ画像２０１を回転させた画像を生成するよりも処理負担が軽減され、以降の検定処理を速やかに実行できる。
【００３６】
ここで、第１の実施形態における具体的な検定方法を説明する。図８に示す４５°回転フィルタを使い、ステップＳ５０５で局所特徴量算出部２０５が算出した同じ方法により局所特徴量（４５°）を算出する。最後に、局所特徴量（０°）と局所特徴量（４５°）とのマハラノビス距離を比較し、マハラノビス距離が予め定められたしきい値以下となる場合を検定合格とし、それ以外の場合を不合格とする。つまり、合格となった局所特徴量だけが特徴比較部２０７に渡される。尚、マハラノビス距離を計算するための分散共分散行列は、予め多くの局所特徴量から求めたものを使用する。
【００３７】
このように、第１の実施形態では、回転させたフィルタを使用して局所特徴量の変動の程度を予め検定し、変動の少ない局所特徴量のみで照合を行うようにしているので、精度の良い検索が期待できる。
【００３８】
尚、第１の実施形態では、検定時のフィルタ回転度数を４５°として、４５°回転検定だけを実施する場合を説明したが、４５°回転検定だけでなく、例えば０°〜９０°までｔ°単位に回転検定を実施しても良い。ただし、ｔは予め定められた０＜ｔ＜９０を満たす値である。
【００３９】
また、ｔ°づつ回転検定を実施するのでなく、ｔ°以下になるまで、９０°から２分割を繰り返して得られる度数のフィルタ回転によって順次回転検定を行うことで、検定対象特徴点の削減を促進するようにしても良い。
【００４０】
ここで図５に戻り、ステップＳ５０７で、特徴比較部２０７が局所特徴量検定部２０６から渡された局所特徴量と画像特徴データベース１０７に登録されている局所特徴量とを比較する。この比較は、画像特徴データベース１０７に登録されている登録画像毎に実施され、比較の結果として登録画像毎に類似度を算出する。この類似度算出方法については、更に詳述する。
【００４１】
次に、ステップＳ５０８で、特徴比較部２０７は、算出した類似度と当該類似度の算出元となった画像とを関連付けて検索結果リストを作成した後、当該類似度を降順にソートする。その後、類似度が高い画像と当該画像の類似度とをソート順に検索結果２０８として出力する。
【００４２】
［類似度算出方法］
次に、類似度算出方法を説明する。ここで、局所特徴量検定部２０６から渡された局所特徴量をＶｑ、局所特徴量に関連付けされている局所特徴点をＱ，座標をＱ（x’，y’）とする。また、画像特徴データベース１０７に登録されている画像Ｒ上に存在する局所特徴量をＶｓ、局所特徴量に関連付けされている局所特徴点をＳ、座標をＳ（x，y）とする。
【００４３】
図６は、第１の実施形態における類似度の算出手順を示すフローチャートである。類似度の算出は投票処理（計数処理）によって行う。投票数＝類似度である。まず、ステップＳ６０１で、最大投票数を表す変数ＶｏｔｅＭａｘを０に初期化する。最大投票数は、複数回投票を行ったうち得られた最大の投票数である。次に、ステップＳ６０２で、ＶｑとＶｓとの特徴量間距離を全ての組み合わせについて計算し、最短距離対応点リストを作成する。即ち、計算した特徴量間の距離がしきい値Ｔｖ以下となり、かつ、最短距離となるようなＶｑとＶｓとの組み合わせ（対応点）を抽出し、最短距離対応点リストに登録する。
【００４４】
これ以降、最短距離対応点リストに登録されたｋ番目の対応点について、当該対応点の局所特徴量をそれぞれＶｑ（ｋ）とＶｓ（ｋ）と記載する。更にＶｑ（ｋ）とＶｓ（ｋ）に対応付けられている局所特徴点をそれぞれＱｋ、Ｓｋ、座標をＱｋ（x’ｋ，y’ｋ）、Ｓｋ（xｋ，yｋ）などと添え字を合わせて記載する。またステップＳ６０２で作成された最短距離対応点リストに登録された対応点の組数をｍ組とする。
【００４５】
次に、ステップＳ６０３で、類似度算出処理の反復カウント数を表す変数Ｃｏｕｎｔを０に初期化する。次に、ステップＳ６０４で、反復カウント数Ｃｏｕｎｔが予め定められた最大反復処理回数Ｒｎを超えていないことを判定する。ここで、超えている場合はステップＳ６１８へ進み、最大投票数ＶｏｔｅＭａｘを出力して、この処理を終了する。
【００４６】
また、ステップＳ６０４で、反復カウント数Ｃｏｕｎｔが最大反復処理回数Ｒｎを超えていない場合はステップＳ６０５へ進み、投票数を表す変数Ｖｏｔｅを０に初期化する。次に、ステップＳ６０６で、当該最短距離対応点リストから対応点の組の座標をランダムに２組抽出する。ここで、これらの座標をＱ１（ｘ’１，ｙ’１）、Ｓ１（ｘ１，ｙ１）及びＱ２（ｘ’２，ｙ’２）、Ｓ２（ｘ２，ｙ２）と記載する。次に、ステップＳ６０７で、抽出したＱ１（ｘ’１，ｙ’１）、Ｓ１（ｘ１，ｙ１）及びＱ２（ｘ’２，ｙ’２）、Ｓ２（ｘ２，ｙ２）が式（８）に示す変換を満たしていると仮定し、式（８）中の変数ａ〜ｆを求める。
【００４７】
ただし、図６に示すステップＳ６０７では、変数ａ〜ｄで構成される行列をＭで示し、変数ｅ〜ｆで構成される行列をＴで示している。
【００４８】
【数３】
2008257469.tif 000005
【００４９】
ここで、第１の実施形態では、簡略化のため、相似変換だけを考える。このとき、上記式（８）は以下の式（９）のように書き換えられる。
【００５０】
【数４】
2008257469.tif 000006
【００５１】
このとき、変数ａ、ｂ、ｅ、ｆはｘ’１、ｙ’１、ｘ１、ｙ１、ｘ’２、ｙ’２、ｘ２、ｙ２を使って式（１０）から式（１３）で表される。
【００５２】
【数５】
2008257469.tif 000007
【００５３】
次に、ステップＳ６０８で、上述のステップＳ６０６で当該最短距離対応点リストからランダムに抽出された２組の点以外の点を選択するために、対応点選択変数ｋを３に初期化する。そして、ステップＳ６０９で、対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていないかを判定する。ここで、超えている場合はステップＳ６１５へ処理を移すが、これについては後述する。ステップＳ６０９における判定で対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていない場合はステップＳ６１０へ処理を移す。
【００５４】
このステップＳ６１０では、上述のステップＳ６０６で当該最短距離対応点リストからランダムに抽出した２組の点Ｓ１（ｘ１，ｙ１）及びＳ２（ｘ２，ｙ２）以外の点を当該最短距離対応点リストから抽出する。第１の実施形態では、抽出された点をＳｋ（ｘｋ，ｙｋ）と記載する。
【００５５】
次に、ステップＳ６１１で、Ｓｋ（ｘｋ，ｙｋ）が式（９）を使って移される座標Ｓｋ’（ｘ’ｋ，ｙ’ｋ）を求める。
【００５６】
その後、ステップＳ６１２では、座標Ｓｋ’（ｘ’ｋ，ｙ’ｋ）と座標Ｑｋ（ｘ’ｋ，ｙ’ｋ）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離がしきい値Ｔｄ以下であるか否かを判定する。当該ユークリッド距離がしきい値Ｔｄ以下の場合はステップＳ６１３へ進み、投票数Ｖｏｔｅをインクリメントし、ステップＳ６１４へ処理を移す。また、当該ユークリッド距離がしきい値Ｔｄより大きい場合は、何もせずにステップＳ６１４へ処理を移す。当該ユークリッド距離がしきい値Ｔｄ以下の特徴点が、画像間で類似しているとみなす特徴点である。
【００５７】
このステップＳ６１４では、対応点選択変数ｋをインクリメントし、ステップＳ６０９に戻り、対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えるまで、上述の処理を繰り返す。つまり、ステップＳ６０６でまた別の２組の点を抽出し、ステップＳ６０７で式（９）のパラメータ変数ａ、ｂ、ｅ、ｆを求め、ステップＳ６０８乃至ステップＳ６１２の処理を行い、投票することを繰り返す。
【００５８】
次に、ステップＳ６０９で、対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えた場合の処理であるステップＳ６１５を説明する。ステップＳ６１５では、投票数Ｖｏｔｅの値と最大投票数ＶｏｔｅＭａｘの値とを比較し、投票数Ｖｏｔｅの値が最大投票数ＶｏｔｅＭａｘの値よりも大きい場合にはステップＳ６１６へ処理を移す。
【００５９】
このステップＳ６１６では、最大投票数ＶｏｔｅＭａｘの値を投票数Ｖｏｔｅの値で置き換えた後、ステップＳ６１７で反復カウント数Ｃｏｕｎｔをインクリメントし、上述のステップＳ６０４に処理を戻す。
【００６０】
また、ステップＳ６１５で、投票数Ｖｏｔｅの値が最大投票数ＶｏｔｅＭａｘの値以下の場合にはステップＳ６１７へ処理を移し、反復カウント数Ｃｏｕｎｔをインクリメントし、上述のステップＳ６０４に処理を戻す。
【００６１】
尚、第１の実施形態における類似度の算出方法の説明では、相似変換だけを考えて説明したが、アフィン変換などその他の幾何学変換についても、ステップＳ６０７でそれぞれに応じた変換行列を求めることにより、対応可能である。例えば、アフィン変換の場合には、まずステップＳ６０６で、ランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ６０７で、式（９）ではなく式（８）を使うこととし、ステップＳ６０６で選択した３組の対応点（合計６点）を使って変数ａ〜ｆを求めれば良い。
【００６２】
また、第１の実施形態における類似度の算出方法の説明では、ステップＳ６１８で類似度として最大投票数ＶｏｔｅＭａｘを出力する方法を説明したが、本発明はこれに限らず、他の類似度を計算するようにしても良い。即ち、ステップＳ６０３以降の処理を行わずに、ステップＳ６０２で作成された最短距離対応点リストに登録された対応点の組数ｍを類似度として出力するようにする。これにより、一定の検索精度を保ちつつ、検索速度を向上させることが可能になる。
【００６３】
以上の説明から明らかなように、第１の実施形態の画像検索装置では、クエリ画像から算出された局所特徴量の変動を検定し、変動の大きい局所特徴量を検索時に使わないように構成したので、検索精度の低下を抑制することが可能になる。
【００６４】
＜第１の実施形態の変形例＞
第１の実施形態では、局所特徴量検定部２０６が回転させたフィルタを使って局所特徴量を検定したが、フィルタを回転させるのではなく、画像自身を回転させた後に局所特徴量を算出し、算出した当該局所特徴量を使って検定しても良い。
【００６５】
第１の実施形態と同様に、クエリ画像２０１から算出した局所特徴量の変動を検定して変動の大きい局所特徴量を検索時に使わないように構成したので、検索精度の低下を抑制することが可能になる。
【００６６】
＜第２の実施形態＞
次に、図面を参照しながら本発明に係る第２の実施形態を詳細に説明する。第２の実施形態では、局所特徴量の検定を画像の登録処理の中でも行うものである。
【００６７】
図９は、第２の実施形態における画像登録装置の構成例を示すブロック図である。図９に示すように、第１の実施形態で説明した画像登録装置１００の局所特徴量算出部１０５と特徴量登録部１０６との間に局所特徴量検定部９０１を追加した構成である。
【００６８】
局所特徴量検定部９０１は、第１の実施形態の局所特徴量検定部２０６と同様の処理を行う。即ち、局所特徴量算出部１０５で局所特徴量の算出に使ったフィルタを４５°回転させたフィルタ（４５°回転フィルタ）を予め準備しておき、当該４５°回転フィルタを使って検定を行う。
【００６９】
第２の実施形態における具体的な検定方法を説明する。当該４５°回転フィルタを使い、ステップＳ３０５で局所特徴量算出部１０５と同じ方法により、局所特徴量（４５°）を算出する。最後に、局所特徴量（０°）と局所特徴量（４５°）とのマハラノビス距離を比較する。当該マハラノビス距離が予め定められたしきい値以下となる場合を検定合格とし、それ以外の場合を不合格とする。つまり、合格となった局所特徴量だけが特徴登録部１０６に渡される。
【００７０】
尚、検定時のフィルタ回転度数は４５°に限らず、例えば０°〜９０°までｔ°単位に回転度数を変化させて検定しても良い。ただし、ｔは予め定められた０＜ｔ＜９０を満たす値である。
【００７１】
また、ｔ°づつ回転検定を実施するのでなく、ｔ°以下になるまで、９０°から２分割を繰り返して得られる度数のフィルタ回転によって順次回転検定を行うことで、検定対象特徴点の削減を促進するようにしても良い。
【００７２】
また、フィルタを回転させるのではなく、画像自身を回転させることにより回転検定を実施するようにしても良い。
【００７３】
第２の実施形態によれば、画像の登録処理時に登録画像から算出した局所特徴量の変動を検定して変動の大きい局所特徴量を登録しないように構成したので、検索精度の低下を抑制することが可能になる。
【００７４】
＜変形例＞
第１及び第２の実施形態では、局所特徴量の検定処理で全ての局所特徴量に対して一律のしきい値を使って検定処理の合格と不合格とを判定したが、画像毎に検定基準を変化させるようにしても良い。即ち、検定に合格する局所特徴量数が一定数以下の場合は、予め定めた値ｒを使い、現在のしきい値をｒ倍した値を新たなしきい値として再設定して再度検定する処理を、検定に合格する特徴点数が一定数以上になるまで繰り返す。
【００７５】
このように、画像毎に検定基準を変化させることで、例えば回転に対して変動の大きい局所特徴量だけを持つ画像に対しても局所特徴量が求まるので、検索が可能になる。一方、検定基準を所定のしきい値に設定した場合は、このような画像では局所特徴量が求まらなくなり、検索ができなくなる。
【００７６】
また、Harris作用素を作用させて得られた出力画像Ｈ上の画素について、当該画素及び当該画素の８近傍にある画素（合計９画素）の画素値を調べ、当該画素が局所極大になる（９画素の中で画素の画素値が最大になる）点を特徴点として抽出する。そして、画素が局所極大になったときでも、画素の値がしきい値以下の場合には特徴点として抽出しないようにする方法について説明した。
【００７７】
しかし、本発明はこれに限らず、当該画素の値がしきい値以下の場合にも特徴点として抽出し、抽出した全ての当該特徴点から局所特徴量を算出し、当該局所特徴量に検定処理を実施するようにしても良い。
【００７８】
即ち、Harris作用素を作用させて得られた出力画像Ｈ上の画素が局所極大になったときに当該画素の値がしきい値以下の場合にも特徴点として抽出し、抽出した全ての当該特徴点から局所特徴量を算出し、当該局所特徴量に検定処理を実施する。これにより、今まで特徴点として抽出されなかった点についても、当該特徴点から算出される局所特徴量が検定に合格すれば、検索時に当該局所特徴量も利用されるようになる。
【００７９】
一方、今まで特徴点として抽出されていた点については、上述したした方法により影響を受けることはない。即ち、局所特徴量が増えることになり、検索精度を更に向上させることが可能になる。
【００８０】
また、局所特徴量の検定処理において、合格となった局所特徴量だけを利用し、不合格の局所特徴量を廃棄する方法について説明したが、検定に不合格の局所特徴量を廃棄するのではなく、検定結果に応じて局所特徴量に重み付けを変更するようにしても良い。この場合、当該重み付けは類似度の算出時に利用する。
【００８１】
例えば、局所特徴量の重みＷを式（１４）のように定める。
【００８２】
【数６】
2008257469.tif 000008
【００８３】
ただし、Ｄは局所特徴量と検定時のフィルタを４５°回転させた場合の局所特徴量とのマハラノビス距離である。
【００８４】
また、類似度の算出においては、第１の実施形態におけるステップＳ６１３で類似度の計算を行っているが、ここを以下の式（１５）のような重みを考慮した計算にすれば良い。
【００８５】
【数７】
2008257469.tif 000009
【００８６】
尚、ここでは、重み付け算出方法を式（１４）のように定義したが、変動の少ない局所特徴量の重み付けを大きくし、変動の多い局所特徴量の重み付けを小さくするような重み付け方法であれば、その方法で代用可能である。
【００８７】
即ち、局所特徴量を除去せずに局所特徴量毎に重み付けを行って類似度を計算するようにしたので、例えば回転に対して変動の大きい局所特徴量だけを持つ画像に対しても検索が可能になる。
【００８８】
上述した実施形態では、回転に対する検定を実施したが、本発明はこれに限らず、画像の拡大や縮小など他の画像処理に対しても局所特徴量の変動を検定し、変動の大きい局所特徴量を検索時に使わないようにしても良い。これにより、検索対象に回転以外の画像が含まれる場合でも、検索精度の低下を抑制することが可能になる。
【００８９】
尚、本発明は複数の機器（例えば、ホストコンピュータ，インターフェース機器，リーダ，プリンタなど）から構成されるシステムに適用しても、１つの機器からなる装置（例えば、複写機，ファクシミリ装置など）に適用しても良い。
【００９０】
また、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記録媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（ＣＰＵ若しくはＭＰＵ）が記録媒体に格納されたプログラムコードを読出し実行する。これによっても、本発明の目的が達成されることは言うまでもない。
【００９１】
この場合、コンピュータ読み取り可能な記録媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記録媒体は本発明を構成することになる。
【００９２】
このプログラムコードを供給するための記録媒体として、例えばフレキシブルディスク，ハードディスク，光ディスク，光磁気ディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリカード，ＲＯＭなどを用いることができる。
【００９３】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、次の場合も含まれることは言うまでもない。即ち、プログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部又は全部を行い、その処理により前述した実施形態の機能が実現される場合である。
【００９４】
更に、記録媒体から読出されたプログラムコードがコンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込む。その後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部又は全部を行い、その処理により前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【００９５】
【図１】第１の実施形態における画像登録装置の構成例を示すブロック図である。
【図２】第１の実施形態における画像検索装置の構成例を示すブロック図である。
【図３】画像の登録処理の手順を表すフローチャートである。
【図４】縮小画像を生成する縮小画像生成部１０３の処理の一例を示す図である。
【図５】画像の検索処理の手順を表すフローチャートである。
【図６】第１の実施形態における類似度の算出手順を示すフローチャートである。
【図７】ガウスフィルタの一例を示す図である。
【図８】図７に示すフィルタを４５°回転させたガウスフィルタの一例を示す図である。
【図９】第２の実施形態における画像登録装置の構成例を示すブロック図である。
【図１０】回転不変として定義された局所特徴量の変動の例を示す図である。
【符号の説明】
【００９６】
１００  画像登録装置
１０１  登録画像
１０２  画像入力部
１０３  縮小画像生成部
１０４  局所特徴点抽出部
１０５  局所特徴量算出部
１０６  特徴量登録部
１０７  画像特徴データベース
２００  画像検索装置
２０１  クエリ画像
２０２  画像入力部
２０３  縮小画像生成部
２０４  局所特徴点抽出部
２０５  局所特徴量算出部
２０６  局所特徴量検定部
２０７  特徴比較部
２０８  検索結果
【図１】
2008257469.tif 000010
【図２】
2008257469.tif 000011
【図３】
2008257469.tif 000012
【図４】
2008257469.tif 000013
【図５】
2008257469.tif 000014
【図６】
2008257469.tif 000015
【図７】
2008257469.tif 000016
【図８】
2008257469.tif 000017
【図９】
2008257469.tif 000018
【図１０】
2008257469.tif 000019