(57)【要約】【課題】  画像全体の特徴を用いた検索方式（全体特徴方式）では画像の回転や切り取りに対応できない。一方、局所特徴を用いた検索方式（局所特徴方式）では、抽出された局所特徴点数が少ない場合又は多すぎる場合に検索精度が低下する場合がある。【解決手段】  全体特徴方式と局所特徴方式とが相互補完可能となるように構成する。すなわち，従来技術の局所特徴方式を使って検索結果候補を得た後，当該検索結果候補画像について，すでにデータベースに登録されている全体特徴をさらに照合する。なお，当該全体特徴の照合位置は，局所特徴を使って推定する。【選択図】  図１
2010266964.tif 000002
【特許請求の範囲】
【請求項１】
入力画像から局所的な特徴量である局所特徴量を抽出する抽出手段と、
前記局所特徴量と画像特徴データベースに登録されている各画像の局所特徴量との類似度である局所特徴類似度を算出し、算出した局所特徴類似度に基づいて複数の候補画像を取得する検索手段と、
前記局所特徴量を用いて各候補画像と前記入力画像との幾何変換パラメータを算出するパラメータ算出手段と、
前記幾何変換パラメータを用いて、各候補画像に対し予め計算されている全体特徴量の計算領域に対応する前記入力画像上の計算領域を確定する確定手段と、
前記確定手段により確定された計算領域の全体特徴量を算出する特徴量算出手段と、
各全体特徴量と前記全体特徴量とを比較して各候補画像と前記入力画像との類似度を算出する類似度算出手段と、
各候補画像を前記類似度の順に出力する出力手段と、
を有することを特徴とする画像検索装置。
【請求項２】
前記検索手段により算出された前記局所特徴類似度に基づいて、前記パラメータ算出手段、前記確定手段、前記特徴量算出手段、及び前記類似度算出手段による各処理の実行を制御する制御手段を更に有することを特徴とする請求項１に記載の画像検索装置。
【請求項３】
前記制御手段は、前記検索手段により算出された前記局所特徴類似度の最大値が所定のしきい値以上である場合、前記パラメータ算出手段、前記確定手段、前記特徴量算出手段、及び前記類似度算出手段による各処理を実行しないよう制御することを特徴とする請求項２に記載の画像検索装置。
【請求項４】
前記制御手段は、前記検索手段により算出された前記局所特徴類似度の最大値と２番目に大きい値との比が所定のしきい値以上である場合、前記パラメータ算出手段、前記確定手段、前記特徴量算出手段、及び前記類似度算出手段による各処理を実行しないよう制御することを特徴とする請求項２に記載の画像検索装置。
【請求項５】
前記確定手段により確定された前記入力画像上の計算領域内に存在するエッジを検出するエッジ検出手段と、
前記エッジ検出手段により前記入力画像上の計算領域内に存在するエッジが検出された場合、前記パラメータ算出手段、前記確定手段、前記特徴量算出手段、及び前記類似度算出手段による各処理を実行しないよう制御する制御手段と、
を更に有することを特徴とする請求項１に記載の画像検索装置。
【請求項６】
前記確定手段により得られた、前記入力画像上の全体特徴量の複数の計算領域を結合して得た結合計算領域を生成する生成手段を更に有し、
前記特徴量算出手段は、前記結合計算領域内で全体特徴量を結合全体特徴量として算出し、
前記類似度算出手段は、各候補画像の結合全体特徴量と前記入力画像の結合全体特徴量とを比較して各候補画像と前記入力画像との類似度を算出する
ことを特徴とする請求項１に記載の画像検索装置。
【請求項７】
前記複数の計算領域は互いに隣接していることを特徴とする請求項６に記載の画像検索装置。
【請求項８】
前記確定手段により得られた、前記入力画像上の全体特徴量の複数の計算領域に画像処理を施す画像処理手段を更に有し、
前記特徴量算出手段は、画像処理後の前記複数の計算領域から全体特徴量を計算し、
前記類似度算出手段は、前記入力画像上の各全体特徴量と前記画像処理後の全体特徴量とを比較して各候補画像と前記入力画像との類似度を算出する
ことを特徴とする請求項１に記載の画像検索装置。
【請求項９】
画像検索装置の制御方法であって、
抽出手段が、入力画像から局所的な特徴量である局所特徴量を抽出する抽出ステップと、
検索手段が、前記局所特徴量と画像特徴データベースに登録されている各画像の局所特徴量との類似度である局所特徴類似度を算出し、算出した局所特徴類似度に基づいて複数の候補画像を取得する検索ステップと、
パラメータ算出手段が、前記局所特徴量を用いて各候補画像と前記入力画像との幾何変換パラメータを算出するパラメータ算出ステップと、
確定手段が、前記幾何変換パラメータを用いて、各候補画像に対し予め計算されている全体特徴量の計算領域に対応する前記入力画像上の計算領域を確定する確定ステップと、
特徴量算出手段が、前記確定ステップで確定された計算領域の全体特徴量を算出する特徴量算出ステップと、
類似度算出手段が、各全体特徴量と前記全体特徴量とを比較して各候補画像と前記入力画像との類似度を算出する類似度算出ステップと、
出力手段が、各候補画像を前記類似度の順に出力する出力ステップと、
を有することを特徴とする画像検索装置の制御方法。
【請求項１０】
コンピュータを請求項１乃至８のいずれか１項に記載の画像検索装置が有する各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像検索装置及びその制御方法並びにプログラムに関する。
【背景技術】
【０００２】
類似画像を検索するための技術が多く提案されている。第一に、画像の全体的な特徴量（全体特徴量）を使って類似画像を検索する方法がある。例えば、画像を複数のブロックに分け、それぞれの代表色を用いてパターンマッチングを行うことで色の位置情報を利用して類似画像を検索する方法が提案されている（特許文献１）。あるいは、画像を複数のブロックに分割して各ブロックの特徴量を算出し、当該特徴量に応じたラベルを付与してラベル行列を生成して全体特徴量とし、当該全体特徴量を使って検索する方法もある（特許文献２）。
【０００３】
第二に、画像の局所的な特徴量（局所特徴量）を使って類似画像を検索する方法が提案されている。これらの方法では、まず画像から特徴的な点（局所特徴点）を抽出する。次に、局所特徴点とその近傍の画像情報とから、その局所特徴点に対する特徴量（局所特徴量）を計算する。画像の検索は、局所特徴量同士のマッチングによって行う。
【０００４】
上述のような局所特徴量を利用する手法においては、局所特徴量を回転不変、拡大・縮小不変となる複数の要素で構成される量として定義することで、画像を回転したり拡大・縮小したりした場合でも検索可能とする方法が提案されている（非特許文献１）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−２４９３４９号公報
【特許文献２】特開平１０−２６０９８３号公報
【非特許文献】
【０００６】
【非特許文献１】C. Schmid and R. Mohr, "Localgray value invariants for image retrieval," IEEE Trans. PAMI., Vol.19, No.5, pp530-534, 1997.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１あるいは特許文献２に開示されているような、画像を分割したブロックごとに特徴を算出し、画像全体の特徴使って検索する方法（全体特徴方式）の場合、検索時にはクエリ画像の画像全体から特徴量を計算することになる。この方法では、例えば画像内の特定オブジェクトが切り取られたり、画像が任意の角度で回転したり、画像の背景色が変わったりした場合には全体特徴量が変化してしまうので、検索が困難になってしまうという問題があった。
【０００８】
また、局所特徴量を使って検索する方法（局所特徴方式）の場合、一般的には局所特徴間のマッチング数あるいはマッチング率に基づいて検索結果を出力する。そのため、抽出された局所特徴点の数が少なすぎる場合には、マッチング数が少なすぎることに起因し、あるいは１つの誤対応がマッチング率に大きく影響することに起因して、精度良く検索できないことがあるという問題があった。
【０００９】
一方、局所特徴点の数が多すぎる場合には、画像を少し回転したりや拡大・縮小するだけで消えてしまうような再現性が低い不安定な局所特徴点が多く含まれる可能性が高くなる。このような不安定な局所特徴点は、画像検索に利用できないだけではなく、ノイズとして作用してしまい、検索精度低下の原因になる。
【００１０】
そのため、非特許文献１に開示された方法では、局所特徴点抽出時に利用する関数値の出力にしきい値を設け、しきい値以下となるような局所特徴点は廃棄することで、より安定した局所特徴点を取捨選択するようにしているが、十分ではない。
【００１１】
さらに、上記個別の方式に関わる課題に加え、全体特徴方式に基づく既存検索システムに局所特徴方式を追加する際、当該局所特徴方式の追加コストに見合う効果を得ることも課題となる。
【００１２】
本発明の目的は、例えば、回転画像や切取り画像の検索を可能としつつ、局所特徴点数が適切でない場合の検索精度低下を防止することである。
【課題を解決するための手段】
【００１３】
本発明の一側面によれば、入力画像から局所的な特徴量である局所特徴量を抽出する抽出手段と、前記局所特徴量と画像特徴データベースに登録されている各画像の局所特徴量との類似度である局所特徴類似度を算出し、算出した局所特徴類似度に基づいて複数の候補画像を取得する検索手段と、前記局所特徴量を用いて各候補画像と前記入力画像との幾何変換パラメータを算出するパラメータ算出手段と、前記幾何変換パラメータを用いて、各候補画像に対し予め計算されている全体特徴量の計算領域に対応する前記入力画像上の計算領域を確定する確定手段と、前記確定手段により確定された計算領域の全体特徴量を算出する特徴量算出手段と、各全体特徴量と前記全体特徴量とを比較して各候補画像と前記入力画像との類似度を算出する類似度算出手段と、各候補画像を前記類似度の順に出力する出力手段とを有することを特徴とする画像検索装置が提供される。
【発明の効果】
【００１４】
本発明によれば、回転画像や切取り画像の検索を可能としつつ、局所特徴点数が適切でない場合の検索精度低下を防止することができる。
【図面の簡単な説明】
【００１５】
【図１】実施形態における画像登録装置及び画像検索装置の構成例を示すブロック図。
【図２】実施形態における画像の登録処理の手順を表すフローチャート。
【図３】実施形態における画像の検索処理の手順を表すフローチャート。
【図４】実施形態における画像のブロック分割処理、入力画像全体特徴領域確定処理を説明する図。
【図５】幾何変換パラメータの算出手順を表すフローチャート。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の好適な実施形態について詳細に説明する。なお、本発明は以下の実施形態に限定されるものではなく、本発明の実施に有利な具体例を示すにすぎない。
【００１７】
本実施形態に係る画像検索装置は、全体特徴方式と局所特徴方式とが相互補完可能となるように構成される。すなわち、局所特徴方式を使って検索結果候補を得た後、当該検索結果候補画像について、すでにデータベースに登録されている全体特徴をさらに照合する。なお、当該全体特徴の照合位置は、局所特徴を使って推定する。かかる本発明の基本概念を実現する実施形態を以下詳しく説明する。
【００１８】
以下の実施形態の説明においては、特許文献１あるいは特許文献２に開示されているような画像全体の特徴を使って検索する方法で使用される特徴量を「全体特徴」と呼び、画像全体の特徴を使って検索する方法を「全体特徴方式」と呼ぶ。一方、画像の局所的な特徴を使って検索する方法で使用する特徴量を「局所特徴」と呼び、画像の局所的な特徴を使って検索する方法を「局所特徴方式」と呼ぶ。なお、実施形態では、説明を簡単にするため、算出されてデータベース（ＤＢ）に登録される全体特徴は、Ｒ，Ｇ，Ｂ各要素の平均値とする。
【００１９】
＜第１の実施形態＞
図１（ａ）は、本実施形態における画像登録装置１００の構成例を示すブロック図である。１０６は画像特徴データベースであり、画像登録装置１００により登録画像１０１から抽出された画像特徴がここに登録される。図１（ｂ）は、本実施形態における画像検索装置２００の構成例を示すブロック図である。クエリ画像２０１と類似した画像が画像特徴データベース１０６から検索される。２１１は検索結果であり、画像検索装置２００が画像特徴データベース１０６を検索した結果として出力される画像と当該画像の関連情報である。以下、本実施形態に係る画像検索装置の動作例を説明する。
【００２０】
［画像の登録処理］
図２のフローチャートを参照して、画像の登録処理の手順を説明する。まず、画像入力部１０２において登録画像１０１を読み込む（Ｓ３０１）。次に、局所特徴抽出部１０３で、登録画像１０１から局所特徴点を抽出する（Ｓ３０２）。次に、抽出した特徴点ごとに周辺画素値を使って局所特徴量を算出する（Ｓ３０３）。なお、局所特徴点の抽出方法および特徴量の算出方法については、非特許文献１をはじめとして様々な方法が提案されており、これら既存の方法を利用可能である。
【００２１】
一方、全体特徴抽出部１０４では、登録画像１０１をブロック分割する（Ｓ３０４）。ここで、図４（ａ）は画像のブロック分割例を示す図である。本実施形態の説明では図４（ａ）に示すように登録画像１０１を８×８の小ブロックに分割することを前提に説明する。図４（ａ）において、５０１は登録画像であり、５０２は登録画像５０１をブロック分割した様子を示した分割後登録画像である。さらに、説明のため分割後のブロック位置を特定することを目的に、分割後登録画像の各ブロックについて縦方向と横方向に番号を付ける。この番号を用いて、例えば分割後ブロック５０３の位置は、（８，３）と表現される。
【００２２】
その後、分割後のブロックごとにブロック内の画素値を使ってＲ，Ｇ，Ｂ各要素の平均値Ｒｓ，Ｇｓ，Ｂｓを計算する（Ｓ３０５）。次に、ブロックごとに算出したＲ，Ｇ，Ｂ平均値をまとめて全体特徴量とする（Ｓ３０６）。ここで、全体特徴量の構成は、ブロックごとに割り当てられたＲ，Ｇ，Ｂ平均値を参照できるような構成にする。たとえば、単純にＲ，Ｇ，Ｂ平均値を特定の順番に並べたものでもよいし、特許文献２にあるようにさらにラベル行列を生成してそのラベル行列も含むようにしてもよい。
【００２３】
特徴量登録部１０５では、Ｓ３０３で算出した局所特徴量とＳ３０５で得られた全体特徴量とを画像特徴データベース１０６に登録可能な特徴量表現形式に構成し、当該特徴量表現を画像特徴データベース１０６に登録する（Ｓ３０７）。
【００２４】
［画像の検索処理］
次に、図３のフローチャートを参照して、画像の検索処理の手順を説明する。まず、図１（ｂ）の画像入力部２０２においてクエリ画像２０１を読み込む（Ｓ４０１）。局所特徴抽出部２０３では、画像の登録処理と同じ方法により、クエリ画像２０１から局所特徴点を抽出する（Ｓ４０２）。次に、ステップＳ４０２で抽出された特徴点ごとに周辺画素値を使って局所特徴量を算出する（Ｓ４０３）。なお、局所特徴点の抽出方法および特徴量の算出方法については、非特許文献１をはじめとして様々な方法が提案されており、これら既存の方法を利用可能である。
【００２５】
候補画像検索部２０４では、抽出した局所特徴量を用いて画像特徴データベース１０６を検索し、類似度順に検索結果の上位からあらかじめ定めた枚数を検索結果候補画像として取得する（Ｓ４０４）。なお、本実施形態では、この類似度を「局所特徴類似度」と呼ぶ。局所特徴類似度は０〜１の範囲の実数で表されることとする。なお、検索結果候補画像は幾何変換パラメータ算出部２０５に渡され、局所特徴類似度は総合類似度算出部２０９に渡される。
【００２６】
幾何変換パラメータ算出部２０５では、クエリ画像２０１と各検索結果候補画像との間の幾何変換パラメータを算出する（Ｓ４０５）。幾何変換パラメータには、たとえば画像の回転角度や拡大・縮小率などがある。
【００２７】
よく用いられる幾何変換パラメータの算出方法においては、まず、クエリ画像中の局所特徴点（クエリ特徴点）と当該局所特徴点に対応するサンプル画像中の局所特徴点（サンプル特徴点）との組合せ（対応点）リストを作成する。ここで、対応点は通常クエリ特徴点での局所特徴量とサンプル特徴点での局所特徴量との特徴量間距離が最短距離かつ予め定めたしきい値以上になる組合せとして抽出される。次に、対応点リストから対応点を順に数組選び当該対応点のサンプル画像中の局所特徴点座標をクエリ画像中の局所特徴点座標にうまく変換する変換行列を見つけることで、当該変換行列を幾何変換パラメータとする。選ばれる対応点数は想定する幾何変換によって異なるが、本実施形態で想定する相似変換の場合は２組である。実際には上記対応点の中には間違った対応点（アウトライア）が含まれる。
【００２８】
そのため、幾何変換パラメータを算出するたびに当該幾何変換パラメータを使い、すべての対応点についてサンプル画像中の局所特徴点座標が対応するクエリ画像中の局所特徴点座標に変換されるか検査し検査結果を記録しておく。検査は変換後のサンプル画像中の局所特徴点座標とクエリ画像中の局所特徴点座標との平均座標間距離を求めることで行い、当該平均座標間距離が短いほど変換成績が良いものとする。すべての幾何変換パラメータの検査結果を調べ、最も変換成績が良かった幾何変換パラメータを採用する。
【００２９】
本実施形態では幾何変換パラメータの算出に際し、計算量を削減するためにRANSACの手法を用いる。RANSACでは上記対応点リストから対応点を順に選択して行くのではなくランダムに選択する。選択回数はアウトライアの割合を考慮してあらかじめ定めておくが、本実施形態では５０回から１００回程度としている。対応点を選ぶたびに、当該対応点のサンプル画像中の局所特徴点座標をクエリ画像中の局所特徴点座標に変換する変換行列を算出する。上記と同様、幾何変換パラメータを算出するたびにすべての対応点についてクエリ画像中の局所特徴点座標が対応するクエリ画像中の局所特徴点座標に変換されるか検査し検査結果を記録しておく。すべての幾何変換パラメータの検査結果を調べ、最も変換成績が良かった幾何変換パラメータを採用する。
【００３０】
幾何変換が相似変換の場合について、ステップＳ４０５における幾何変換パラメータ算出例を図５に示す。図５は幾何変換パラメータの算出手順を表すフローチャートである。図５において、クエリ画像２０１から抽出された局所特徴量をＶｑ、当該局所特徴量に関連付けされている局所特徴点をＱ、当該局所特徴点の座標をＱ（x’，y’）とする。また、検索結果候補画像Ｒ上に存在する局所特徴量をＶｓ、局所特徴量に関連付けされている局所特徴点をＳ、座標をＳ（x，y）とする。
【００３１】
まず、最終投票数を表す変数ＶｏｔｅＭａｘを０に初期化し、最終変換行列ＭｖおよびＴｖの全要素を０に設定する（Ｓ６０１）。次に、ＶｑとＶｓとの特徴量間距離をすべての組合せについて計算し、最短距離対応点リストを作成する（Ｓ６０２）。すなわち、計算した特徴量間距離があらかじめ定めたしきい値以下となり、かつ、最短距離となるようなＶｑとＶｓとの組合せ（対応点）を抽出し、最短距離対応点リストに登録する。以後、本実施形態の説明では、最短距離対応点リストに登録されたｋ番目の対応点について、当該対応点の局所特徴量をそれぞれＶｑ（ｋ）とＶｓ（ｋ）と記載し、Ｖｑ（ｋ）とＶｓ（ｋ）に対応付けられている局所特徴点をそれぞれＱｋ、Ｓｋ、座標をそれぞれＱｋ（x’ｋ，y’ｋ）、Ｓｋ（xｋ，yｋ）などと添え字をあわせて記載する。また、ステップＳ６０２で作成された最短距離対応点リストに登録された対応点の組数をｍ組とする。
【００３２】
次に、反復カウント数を表す変数Ｃｏｕｎｔを０に初期化する（Ｓ６０３）。次に、反復カウント数Ｃｏｕｎｔがあらかじめ定めた最大反復処理回数Ｒｎを超えていないか判定する（Ｓ６０４）。超えている場合はステップＳ６０４で最終投票数ＶｏｔｅＭａｘおよび最終変換行列ＭｖおよびＴｖを出力して処理を終了する。超えていない場合は、ステップＳ６０５に移る。
【００３３】
ステップＳ６０５では、投票数を表す変数Ｖｏｔｅを０に初期化する。次に、当該最短距離対応点リストから対応点の組の座標をランダムに２組抽出する（ステップＳ６０６）。本実施形態では、これらの座標をＱ１（ｘ’１，ｙ’１）、Ｓ１（ｘ１，ｙ１）およびＱ２（ｘ’２，ｙ’２）、Ｓ２（ｘ２，ｙ２）と記載する。次に、抽出したＱ１（ｘ’１，ｙ’１）、Ｓ１（ｘ１，ｙ１）およびＱ２（ｘ’２，ｙ’２）、Ｓ２（ｘ２，ｙ２）が式（１）に示す変換を満たしていると仮定し、式（１）中の変数ａ〜ｆを求める（ステップＳ６０７）。ただし、図５に示すフローチャート中のステップＳ６０７では、変数ａ〜ｄで構成される行列をＭ、変数ｅ〜ｆで構成される行列をＴで示している。
【００３４】
2010266964.tif 000003
【００３５】
ここで、本実施形態では、簡単のため相似変換だけを考える。このとき、式（１）は式（２）のように書き換えられる。
【００３６】
2010266964.tif 000004
【００３７】
このとき、変数ａ、ｂ、ｅ、ｆはｘ’１、ｙ’１、ｘ１、ｙ１、ｘ’２、ｙ’２、ｘ２、ｙ２を使って式（３）から式（６）で表される。
【００３８】
2010266964.tif 000005
【００３９】
次に、ステップ６０５において最短距離対応点リストからランダムに抽出された２組の点以外の点を選択するために、対応点選択変数ｋを３に初期化する（Ｓ６０８）。次に、対応点選択変数ｋが最短距離対応点リストに登録されている対応点の組数ｍを超えていないか判定する（Ｓ６０９）。超えている場合はステップＳ６１５に処理を移すが、これについては後述する。ステップＳ６０９における判定で対応点選択変数ｋが最短距離対応点リストに登録されている対応点の組数ｍを超えていない場合はステップＳ６１０に処理を移す。
【００４０】
ステップＳ６１０では、最短距離対応点リストからステップＳ６０５において最短距離対応点リストからランダムに抽出された２組の点Ｓ１（ｘ１，ｙ１）およびＳ２（ｘ２，ｙ２）以外の点を抽出する。本実施形態では、抽出された点をＳｋ（ｘｋ，ｙｋ）と記述する。
【００４１】
次に、Ｓｋ（ｘｋ，ｙｋ）が式（２）を使って移される座標Ｓｋ’（ｘ’ｋ，ｙ’ｋ）を求める（Ｓ６１１）。その後、座標Ｓｋ’（ｘ’ｋ，ｙ’ｋ）と座標Ｑｋ（ｘ’ｋ，ｙ’ｋ）との幾何学的距離をユークリッド距離で計算し、当該ユークリッド距離がしきい値Ｔｄ以下であるかどうかを判定する（Ｓ６１２）。当該ユークリッド距離がしきい値Ｔｄ以下の場合には、ステップＳ６１３により投票数Ｖｏｔｅをインクリメントし、ステップＳ６１４に処理を移す。当該ユークリッド距離がしきい値Ｔｄより大きい場合には、何もせずにステップＳ６１４に処理を移す。ステップＳ６１４では、対応点選択変数ｋをインクリメントし、ステップＳ６０９に戻る。
【００４２】
次に、ステップＳ６０９において対応点選択変数ｋが当該最短距離対応点リストに登録されている対応点の組数ｍを超えていた場合の処理であるステップＳ６１５を説明する。ステップＳ６１５では、投票数Ｖｏｔｅの値と最終投票数ＶｏｔｅＭａｘの値とを比較し、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値よりも大きい場合はステップＳ６１６の処理を実行する。ステップＳ６１６では、最終投票数ＶｏｔｅＭａｘの値を投票数Ｖｏｔｅの値で置き換えた後、最終変換行列ＭｖおよびＴｖをそれぞれステップＳ６０７で求めた変換行列Ｍ、Ｔに設定する。ステップＳ６１７で反復カウント数Ｃｏｕｎｔをインクリメントし、ステップＳ６０４に処理を戻す。投票数Ｖｏｔｅの値と最終投票数ＶｏｔｅＭａｘの値とを比較し、投票数Ｖｏｔｅの値が最終投票数ＶｏｔｅＭａｘの値以下の場合は、ステップＳ６１７で反復カウント数Ｃｏｕｎｔをインクリメントし、ステップＳ６０４に処理を戻す。
【００４３】
なお、本実施形態における類似度の算出方法の説明では、相似変換だけを考えて説明を実施したが、アフィン変換などその他の幾何学変換についても、ステップＳ６０７においてそれぞれに応じた変換行列を求めることにより、対応可能である。たとえば、アフィン変換の場合は、まず、ステップＳ６０６でランダムに選択する対応点の組の座標数を３とする。次に、ステップＳ６０７において式（２）ではなく式（１）を使うこととし、ステップＳ６０６で選択した３組の対応点（合計６点）を使って変数ａ〜ｆを求めればよい。
【００４４】
次に、入力画像全体特徴領域確定部２０６では、ステップＳ４０６により、検索結果候補画像が登録時に設定されたブロックごとにクエリ画像２０１上での対応領域を入力画像の全体特徴量の計算領域として確定する。入力画像の全体特徴量の計算領域の確定には幾何変換パラメータを利用する。本実施形態での入力画像の全体特徴量の計算領域の確定条件は入力画像からはみ出していないこととする。そのため、確定される入力画像の全体特徴量の計算領域数は複数の場合もあるし、ゼロの場合もあり得る。
【００４５】
図４（ｂ）はステップＳ４０６の入力画像の全体特徴領域確定処理を説明する図である。図４（ｂ）において、７０１はクエリ画像であり、７０２は幾何変換パラメータを使って登録画像５０１の各ブロックに対応する入力画像の全体特徴量の計算領域をクエリ画像７０１上に重畳した様子を表す図である。図４（ａ）における（８，３）の位置にあるブロック５０３は、クエリ画像２０１上に重畳されたブロックの中で（８，３）の位置にあるクエリ画像上の分割ブロック７０３に対応する。よってブロック７０３がブロック５０３に対応する入力画像の全体特徴量の計算領域となる。
【００４６】
入力画像全体特徴量算出部２０７では、クエリ画像２０１上での全体特徴量の計算領域ごとに、登録時と同じ全体特徴量を算出する（Ｓ４０７）。本実施形態における画像の登録処理では全体特徴量を領域内画素値のＲ、Ｇ、Ｂ各要素平均値として説明しているので、ステップＳ４０７でもクエリ画像２０１上での全体特徴量の計算領域内の画素値からＲ、Ｇ、Ｂ各要素の平均値Ｒｑ、Ｇｑ、Ｂｑを算出する。なお、本実施形態では、入力画像の全体特徴量の計算領域の一部がクエリ画像２０１からはみ出ている場合には当該領域の全体特徴を計算しないこととし、後の処理のために当該領域が画像からはみ出ていることがわかるように記録しておくことにする。
【００４７】
全体特徴量比較部２０８では、検索結果候補画像それぞれについて、クエリ画像の全体特徴量の各計算領域と入力画像の全体特徴量の各計算領域に対応する検索結果候補画像上の各ブロックとについてＲ、Ｇ、Ｂ各要素の平均値を比較する（Ｓ４０８）。比較結果は数値化され数値化比較結果として生成される。本実施形態では、入力画像の全体特徴量の計算領域ごとにＲ、Ｇ、Ｂ各要素の平均値の差分絶対値を計算し、当該差分絶対値の平均を数値化比較結果とする。すなわち、当該数値化比較結果Ｅは式（７）で求められる。ただし、入力画像の全体特徴量の計算領域の数をＮとする。また、検索結果候補画像における全体特徴量の計算領域ｉに対応するブロックのＲ、Ｇ、Ｂ各要素の平均値をそれぞれＲｓ（ｉ）、Ｇｓ（ｉ）、Ｂｓ（ｉ）とする。また、クエリ画像における全体特徴量の計算領域ｉのＲ、Ｇ、Ｂ各要素の平均値をそれぞれＲｑ（ｉ）、Ｇｑ（ｉ）、Ｂｑ（ｉ）とした。
【００４８】
2010266964.tif 000006
【００４９】
総合類似度算出部２０９では、候補画像検索部２０４から渡された局所特徴類似度とステップＳ４０８で算出した数値化比較結果とを用いて、総合類似度を算出する（ステップＳ４０９）。本実施形態では、総合類似度を式（８）で算出する。ただし、総合類似度をＳｔ、局所特徴類似度をＳｐ、数値化比較結果をＥとした。ここで、−１．０≦Ｓｐ≦２．０である。
【００５０】
2010266964.tif 000007
【００５１】
検索結果出力部２１０では、検索結果候補画像を総合類似度の順に検索結果２１１として出力する（ステップＳ４１０）。
【００５２】
上述の実施形態では、図１（ａ）で局所特徴抽出部と全体特徴抽出部とを並列に処理するよう構成し、図２では局所特徴量算出ステップ部分と全体特徴量算出ステップ部分とを並列に処理するように記載した。しかしこの代わりに、局所特徴抽出部と全体特徴抽出部とを直列に構成して局所特徴量算出ステップ部分と全体特徴量算出ステップ部分とを直列に処理するように構成してもよい。
【００５３】
また、上述の実施形態では、登録時に全体特徴と局所特徴とを同時に生成するように構成したが、全体特徴と局所特徴は別々のタイミングで作成してもよい。たとえば、すでに全体特徴量を使って構成された検索システムが存在する場合、局所特徴量だけを算出して追加登録するように構成可能である。
【００５４】
さらに、上述の実施形態では、全体特徴の算出例としてブロックごとにＲ、Ｇ、Ｂ各要素の平均値を算出する方法を示した。しかし、ブロックごとに特定の情報を保持および参照できるように構成すればよく、特定の情報として輝度平均値を持たせるようにしてもよいし、画素値の分散などの統計情報、周波数変換後の係数情報などを持たせることもできる。
【００５５】
さらに、上述の実施形態では、ブロック分割して全体特徴量を算出する例を説明した。しかし、部分領域に分割され当該部分領域ごとに情報を保持・参照できるならばブロックである必要はなく、ブロックの代わりに円領域や楕円領域など任意の領域を構成するようにしてもよい。
【００５６】
さらに、数値化比較結果Ｅを式（７）、総合類似度を式（８）として説明したが、本発明はこれらの式に限定されない。例えば、全体特徴の比較結果が総合類似度に適切に反映されるような数値化比較結果および総合類似度の算出式であれば他の式に置き換えることも可能である。
【００５７】
さらに、全体特徴量を領域内画素値のＲ、Ｇ、Ｂ各要素平均値として説明したが、全体特徴量はこれに限定されることなく、比較可能な量であればどのような量でも可能である。たとえば、分散値など他の統計情報を全体特徴量としてもよいし、領域内の画素値をあらかじめ定めた規則に従って一列に並べてベクトルを構成するようにしてもよい。
【００５８】
さらに、ステップＳ４０８での比較方法および比較結果として、入力画像の全体特徴量の計算領域ごとにＲ、Ｇ、Ｂ各要素の平均値の差分絶対値を計算し、当該差分絶対値の平均を計算する方法を示した。しかし、他の比較方法を使って比較結果を出力するように構成してもよい。たとえば、全体特徴量の相関を調査し、相関係数を比較結果とするように構成してもよい。
【００５９】
以上の説明から明らかなように、本実施形態に係る画像検索装置では、局所特徴方式を使って検索結果候補画像を得た後、当該検索結果候補画像について全体特徴をさらに照合するようにした。これにより、回転画像や切取り画像の検索を可能としつつ、局所特徴方式だけを用いて検索した場合に検索精度が低下するような画像の検索時にも、検索精度の低下を防止することが可能になる。
【００６０】
さらに、全体特徴方式に基づく既存検索システムに局所特徴方式を追加する際、既存の特徴量をそのまま利用可能となるだけではなく、既存特徴量を検索精度向上のために活用可能となり、局所特徴方式の追加コストに見合う効果を得ることが可能となる。
【００６１】
＜第２の実施形態＞
上記第１の実施形態では、候補画像検索部２０４において、局所特徴量を使って画像特徴データベース１０６を検索し、局所特徴類似度順に検索結果の上位からあらかじめ定めた枚数を検索結果候補画像として取得した。また、検索結果候補画像は幾何変換パラメータ算出部に渡され、局所特徴類似度は総合類似度算出部２０９に渡されるようにした。本実施形態では、局所特徴類似度に基づいてステップＳ４０５からＳ４０９の処理（全体特徴比較処理）を実行する／しないを制御する制御ステップを追加する。
【００６２】
本実施形態に係る画像検索装置によれば、全体特徴比較が不要な場合には検索精度低下を防ぎつつ計算コストの抑制が可能になる。
【００６３】
＜第３の実施形態＞
上記第２の実施形態では、局所特徴類似度に基づいて全体特徴比較処理の実行／非実行を制御する制御ステップを追加した。本実施形態では、局所特徴類似度の最大値が所定のしきい値より小さい場合にだけ全体特徴比較処理を実行するよう制御が行われる。本実施形態では、局所特徴類似度の最大値が所定のしきい値以上の場合には全体特徴比較処理をスキップするように構成する。このため、全体特徴比較が不要な場合には検索精度低下を防ぎつつ計算コストの抑制が可能になる。
【００６４】
＜第４の実施形態＞
上記第２の実施形態では、局所特徴類似度に基づいて全体特徴比較処理の実行／非実行を制御する制御ステップを追加した。本実施形態では、局所特徴類似度の最大値と２番目に大きい値との比を候補画像類似度比として算出する。そして、当該候補画像類似度比が所定のしきい値より小さい場合にだけ全体特徴比較処理を実施する。本実施形態では、局所特徴類似度の最大値があらかじめ定めたしきい値以上の場合には全体特徴比較処理をスキップするように構成する。これにより全体特徴比較が不要な場合には検索精度低下を防ぎつつ計算コストの抑制が可能になる。
【００６５】
＜第５の実施形態＞
上記第２の実施形態では、局所特徴類似度に基づいて全体特徴比較処理の実行／非実行を制御するステップを追加した。本実施形態では、局所特徴類似度の最大値が第１のしきい値より小さい場合にはさらに局所特徴類似度の最大値と二番目に大きい値との比を候補画像類似度比として算出する。当該候補画像類似度比が第２のしきい値より小さい場合にだけ全体特徴比較処理を実施する。本実施形態では、局所特徴類似度の最大値があらかじめ定めたしきい値以上の場合には全体特徴比較処理をスキップするように構成する。これにより全体特徴比較が不要な場合には検索精度低下を防ぎつつ計算コストの抑制が可能になる。
【００６６】
＜第６の実施形態＞
上記第１の実施形態では、入力画像全体特徴領域確定部２０６では、ステップＳ４０６により、幾何変換パラメータを使って検索結果候補画像が登録時に設定された各ブロックのクエリ画像２０１上での全体特徴量の計算領域を確定した。その後の処理は全体特徴量の計算領域内の情報は何の検査も受けることなくそのまま次のステップであるステップＳ４０７に移った。本実施形態では、全体特徴量の計算領域の確定後、当該計算領域ごとに当該計算領域内の情報を検査して入力画像の全体特徴量と候補画像の全体特徴量とを比較すべきか否かを判定する全体特徴量比較是非判定ステップを追加する。比較すべきでないと判定した場合には、当該計算領域についてはステップＳ４０８からステップＳ４０９の処理をスキップするように構成する。
【００６７】
すなわち、本実施形態に係る画像検索装置によれば、入力画像の全体特徴量の計算領域ごとに当該計算領域内の情報を検査して入力画像の全体特徴量と候補画像の全体特徴量とを比較すべきか否かを判定する。比較すべきでないと判定した場合には、当該計算領域についてはステップＳ４０８からステップＳ４０９の処理をスキップする。これにより、全体特徴量の比較が適当ではない計算領域の全体特徴が比較されないようになるので、不必要な類似度低下を防ぐことが可能となる。
【００６８】
＜第７の実施形態＞
上記第６の実施形態では、入力画像の全体特徴量の計算領域ごとに当該計算領域内の情報を検査して入力画像の全体特徴量と候補画像の全体特徴量とを比較すべきか否かを判定する全体特徴量比較是非判定ステップを追加した。比較すべきでないと判定した場合には、当該計算領域についてはステップＳ４０８からステップＳ４０９の処理をスキップした。本実施形態では、当該全体特徴量比較是非判定ステップにおいてエッジを検出するエッジ検出ステップを追加する。当該計算領域内にエッジが存在する場合には、当該計算領域についてはステップＳ４０８からステップＳ４０９の処理をスキップする。
【００６９】
これにより、全体特徴量の比較が適当ではない計算領域の全体特徴が比較されないようになるので、不必要な類似度低下を防ぐことが可能となる。
【００７０】
＜第８の実施形態＞
上記第７の実施形態では、計算領域内にエッジが含まれる場合には、当該計算領域についてはステップＳ４０８からステップＳ４０９の処理をスキップするようにした。本実施形態では、エッジ検出ステップにおいて、前記計算領域内の画素値の勾配振幅値を算出する。当該振幅値があらかじめ定めたしきい値以上となる画素だけを抽出したエッジとして出力するように構成する。
【００７１】
すなわち、本実施形態に係る画像検索装置によれば、エッジ抽出ステップにおいて、入力画像の全体特徴量の計算領域内の画素値の勾配振幅値を算出するようにした。当該振幅値があらかじめ定めたしきい値以上となる画素だけを抽出したエッジとして出力するように構成した。これにより、ノイズの影響を受けにくい条件下で全体特徴量の比較が適当ではない計算領域の全体特徴が比較されないようになるので、不必要な類似度低下を防ぐことが可能となる。
【００７２】
＜第９の実施形態＞
上記第７の実施形態では、入力画像の全体特徴量の計算領域内にエッジが含まれる場合には、当該計算領域についてはステップＳ４０８からステップＳ４０９の処理をスキップするようにした。本実施形態では、エッジ検出ステップにおいて、前記計算領域内の画素値の勾配振幅値を算出する。さらに当該振幅値の最大値を最大振幅値として求め、当該振幅値と当該最大振幅値との比があらかじめ定めたしきい値以上の画素だけを抽出したエッジとして出力するように構成する。
【００７３】
すなわち、本実施形態に係る画像検索装置によれば、エッジ検出ステップにおいて、入力画像の全体特徴量の計算領域内の画素値の勾配振幅値を算出するようにした。さらに当該振幅値の最大値を最大振幅値として求め、当該振幅値と当該最大振幅値との比があらかじめ定めたしきい値以上の画素だけを抽出したエッジとして出力するように構成した。これにより、ノイズの影響を受けにくい条件下で全体特徴量の比較が適当ではない入力画像全体特徴量計算領域の全体特徴が比較されないようになるので、不必要な類似度低下を防ぐことが可能となる。
【００７４】
＜第１０の実施形態＞
上記第１の実施形態では、入力画像全体特徴領域確定部２０６において、ステップＳ４０６により、前記幾何変換パラメータを使って検索結果候補画像が登録時に設定された各ブロックについてクエリ画像２０１上での全体特徴量の複数の計算領域を確定した。その後、計算領域それぞれについてステップＳ４０７およびステップＳ４０８の処理を実行するようにした。本実施形態では、入力画像上の全体特徴量の複数の計算領域を結合して結合計算領域を生成する。その後、結合計算領域内で全体特徴量を結合全体特徴量として算出し、候補画像の結合全体特徴量と入力画像の結合全体特徴量とを比較するように構成する。これにより、回転画像や切取り画像の検索を可能としつつ、局所特徴方式だけを使って検索した場合に検索精度が低下するような画像の検索時にも検索精度の低下を防止可能となる。さらに局所的に付加されるノイズの影響を抑えることが可能になる。
【００７５】
＜第１１の実施形態＞
上記第１０の実施形態では、入力画像上の全体特徴量の複数の計算領域を結合して結合計算領域を生成する。その後、当該結合計算領域内で全体特徴量を結合全体特徴量として算出し、候補画像の結合全体特徴量と入力画像の結合全体特徴量とを比較するように構成した。本実施形態では、結合計算領域の生成に利用する入力画像上の全体特徴量の計算領域は互いに隣接していることを条件とするように構成する。
【００７６】
すなわち本実施形態に係る画像検索装置によれば、結合計算領域の生成に利用する入力画像上の全体特徴量の計算領域は互いに隣接していることを条件とするように構成した。これにより、回転画像や切取り画像の検索を可能としつつ、局所特徴方式だけを使って検索した場合に検索精度が低下するような画像の検索時にも検索精度の低下を防止可能となる。さらに局所的に付加されるノイズの影響を抑えることが可能になる。
【００７７】
＜第１２の実施形態＞
上記第１の実施形態では、入力画像全体特徴領域確定部２０６において、ステップＳ４０６により、幾何変換パラメータを使って検索結果候補画像が登録時に設定された各ブロックについてクエリ画像２０１上での全体特徴量の複数の計算領域を確定した。その後、全体特徴量の複数の計算領域のそれぞれについてステップＳ４０７およびステップＳ４０８の処理を実施するようにした。本実施形態では、全体特徴量の計算領域の確定後、各計算領域に対して画像処理を施す。ステップＳ４０７では、画像処理後の計算領域から全体特徴を算出し、画像処理後全体特徴を生成する。その後ステップＳ４０８にて画像処理後全体特徴を比較する。ここで、画像処理はどのような処理でもよいが、本実施形態ではフーリエ変換や離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ Ｃｏｓｉｎｅ Ｔｒａｎｓｆｏｒｍ）などの空間周波数変換処理を例に説明する。
【００７８】
本実施形態では、画像処理を実施後、ステップＳ４０７により、クエリ画像２０１上での入力画像全体特徴量計算領域ごとに、登録時と同じ画像処理後全体特徴量を算出する。画像処理が離散コサイン変換処理の場合、画像処理後全体特徴量はたとえばＤＣＴ係数の交流成分の低域側からあらかじめ定めた数の係数を抽出し、当該係数を順に並べたものを全体特徴量とする。
【００７９】
すなわち本実施形態に係る画像検索装置によれば、入力画像の全体特徴量の計算領域の確定後、各計算領域に対して画像処理を施す。その後、画像処理後の計算領域から全体特徴を算出する。これにより、回転画像や切取り画像の検索を可能としつつ、局所特徴方式だけを使って検索した場合に検索精度が低下するような画像の検索時にも検索精度の低下を防止可能となる。さらに局所的に付加されるノイズの影響を抑えることが可能になる。
【００８０】
（他の実施形態）
以上、本発明の実施形態を詳述したが、前述の各実施形態における処理は、複数のハードウェアとソフトウエアの協働によって実現するようにしてもよい。この場合、ネットワーク又は各種記憶媒体を介して取得したソフトウエア（プログラム）をコンピュータ等の処理装置（ＣＰＵ、プロセッサ）にて実行することで実現できる。
【００８１】
また、本発明は前述した実施形態における機能をコンピュータに実現させるプログラムを記憶した記憶媒体を、システム或いは装置に供給することによって実現してもよい。
【図１】
2010266964.tif 000008
【図２】
2010266964.tif 000009
【図３】
2010266964.tif 000010
【図４】
2010266964.tif 000011
【図５】
2010266964.tif 000012