(57)【特許請求の範囲】
【請求項１】
画像を解析して中間値を取得する取得手段と、
前記中間値を使用して、前記画像に特徴抽出領域を設定する設定手段と、
前記設定手段において使用された中間値を再利用して前記特徴抽出領域の局所的な特徴を抽出する抽出手段と、
を備え、
前記設定手段では、前記特徴抽出領域を設定する処理において前記特徴抽出領域の面積が予め定められた閾値を超える場合、当該処理を中断して前記画像の全領域に前記特徴抽出領域を設定することを特徴とする情報処理装置。
【請求項２】
前記画像の局所的な特徴には、画像の特徴点と、画像の特徴点に関する特徴量との少なくともいずれかが含まれることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記取得手段は、前記画像の各画素位置での輝度勾配値を取得することを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記設定手段は、前記輝度勾配値の強度が所定のしきい値以上である領域に前記特徴抽出領域を設定することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記取得手段は、前記画像を周波数変換し、当該周波数変換された画像においてピークとなる周波数係数を前記中間値として取得することを特徴とする請求項１に記載の情報処理装置。
【請求項６】
前記設定手段は、前記ピークとなる周波数係数が所定のしきい値以上である領域に前記特徴抽出領域を設定することを特徴とする請求項５に記載の情報処理装置。
【請求項７】
前記設定手段は、前記特徴抽出領域を設定する処理を開始してから設定済みの特徴抽出領域の面積を計測し、当該面積が予め定められた値以上になった場合は、当該処理を中断して、前記画像の全領域に前記特徴抽出領域を設定することを特徴とする請求項１に記載の情報処理装置。
【請求項８】
前記設定手段は、前記特徴抽出領域を設定する処理を開始してから、当該処理が完了するまでに予め定められた時間が経過した場合は、当該処理を中断して、前記画像の全領域に前記特徴抽出領域を設定することを特徴とする請求項１に記載の情報処理装置。
【請求項９】
前記設定手段は、前記画像を複数の部分領域に分割し、該部分領域をランダムな順序で選択し、選択された該順序で該部分領域毎に前記特徴抽出領域を設定することを特徴とする請求項１に記載の情報処理装置。
【請求項１０】
前記抽出手段で抽出された局所的な特徴をそれぞれ前記画像に対応づけて保持する保持手段を更に備えることを特徴とする請求項１に記載の情報処理装置。
【請求項１１】
前記画像は入力画像であって、
前記入力画像の局所的な特徴と、前記保持手段に保持された画像の局所的な特徴の各々とを比較して、該入力画像の類似画像を検索する検索手段を更に備える
ことを特徴とする請求項１０に記載の情報処理装置。
【請求項１２】
情報処理装置の制御方法であって、
取得手段が、画像を解析して中間値を取得する取得工程と、
設定手段が、前記中間値を使用して、前記画像に特徴抽出領域を設定する設定工程と、
抽出手段が、前記設定工程において使用された中間値を再利用して前記特徴抽出領域の局所的な特徴を抽出する抽出工程と、
を有し、
前記設定工程では、前記特徴抽出領域を設定する処理において前記特徴抽出領域の面積が予め定められた閾値を超える場合、当該処理を中断して前記画像の全領域に前記特徴抽出領域を設定することを特徴とする情報処理装置の制御方法。
【請求項１３】
コンピュータを請求項１に記載の情報処理装置が備える各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置及びその制御方法、プログラムに関し、特に、画像から局所的な特徴を抽出する技術に関する。
【背景技術】
【０００２】
画像内のオブジェクトに着目して類似画像を検索する構成として、画像の局所的な特徴を数値化した局所特徴量を使って検索を行うものが知られている（特許文献１）。この構成では、まず、画像の２次元の輝度分布に対して各種のフィルタ（Ｇａｕｓｓ、Ｓｏｂｅｌ、Ｐｒｅｗｉｔｔ等）を作用させることで画像中の特徴的な点（特徴点）を抽出する。次に、特徴点及びその近傍の画素の画素値を使用して、その特徴点に関する特徴量（局所特徴量）を計算する。画像の検索は、クエリとなる画像と検索対象の画像とについて、局所特徴量をマッチングして行う。このような処理によって、画像の回転や縮小、部分的な切取りや隠れがあっても、精度が安定した画像検索が実現される。
【０００３】
また、背景差分法を使って特徴点や局所特徴量を計算する領域を限定する手法が知られている（非特許文献１）。この手法では、固定カメラを使って物体を撮影することを前提とし、撮影画像とあらかじめ撮影した背景画像との差分を取ることによって前景領域を特定する。特定した前景領域をマスク領域として、マスク領域内だけで特徴点や局所特徴量を計算することで計算コストを削減している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−６５３９９号公報
【非特許文献】
【０００５】
【非特許文献１】古畑俊一郎，北原格，亀田能成，大田友一，“領域を限定したSIFT 特徴量の抽出”，情報処理学会第７０回全国大会（２００８）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１に記載の構成では、画像上のオブジェクトの有無や種類にかかわらず画像全体から局所特徴候補を抽出する。つまり、局所特徴が抽出される可能性が低い領域に対してもフィルタ適用時のコンボリューション処理など計算コストが高い処理を等しく実行している。このため、無駄な処理に起因して処理速度低下を招くことがある。
【０００７】
一方、非特許文献１の手法では確かに計算コストの削減が可能だが、あらかじめ背景画像を準備する必要がある。そのため背景画像が準備されていない一般的な画像の検索には適用できない。また、マスク領域の設定処理と特徴点や局所特徴量の計算処理とが独立して別個に行われる。このため、例えば、前景領域の範囲が広くなると逆に計算コストが増加する恐れがある。
【０００８】
本発明は上記課題に鑑みなされたものであり、画像の種類にかかわらず、検索精度を維持しつつ画像検索の処理速度を向上させるための技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明による情報処理装置は以下の構成を備える。即ち、
画像を解析して中間値を取得する取得手段と、
前記中間値を使用して、前記画像に特徴抽出領域を設定する設定手段と、
前記設定手段において使用された中間値を再利用して前記特徴抽出領域の局所的な特徴を抽出する抽出手段と、
を備え、
前記設定手段では、前記特徴抽出領域を設定する処理において前記特徴抽出領域の面積が予め定められた閾値を超える場合、当該処理を中断して前記画像の全領域に前記特徴抽出領域を設定することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、画像の種類にかかわらず、検索精度を維持しつつ画像検索の処理速度を向上させるための技術を提供することができる。
【図面の簡単な説明】
【００１１】
【図１】情報処理装置の機能構成例を示すブロック図。
【図２】情報処理装置の概略ハード構成例を示す図。
【図３】画像の登録処理の手順を表すフローチャート。
【図４】画像の縮小変換処理を示す模式図。
【図５】画像の検索処理の手順を表すフローチャート。
【発明を実施するための形態】
【００１２】
以下、添付図面を参照して本発明に係る実施の形態を詳細に説明する。
【００１３】
＜＜第１実施形態＞＞
（特徴点と局所特徴量）
まず、特徴量、局所特徴点、および局所特徴量について説明する。画像を検索条件（クエリ画像）として指定して、類似する画像を検索する場合は、２つの画像（クエリ画像とデータベース内画像）を比較する処理を繰り返し行う。画像の比較では予めその画像の内容をよく表す数値や数列を特徴として画像毎に算出する。そして、この特徴が似ている画像を類似する画像と判断し検索結果として出力する。画像を検索する際に、画像の内容を示すキーワードを用いる事もあるが、本実施形態では画像の画素値から算出した特徴量を検索・認識に用いる。なお、本明細書では、画像の特徴には、画像の特徴点と、画像の特徴点に関する特徴量との少なくともいずれかが含まれる。
【００１４】
このような画像検索の例として、クエリ画像に含まれる局所的な特徴を比較する手法がある。この方式では、画像の中から両者の対応を取り易い点を選び、更に画像間で点の対応をとる。この対応の取り易い点を本実施形態では局所特徴点（ｆｅａｔｕｒｅ  ｐｏｉｎｔ）と呼ぶ。このような局所特徴点はできるだけ画像内のコーナやエッジの近傍から抽出されるように構成する。局所特徴点が抽出されると、次に局所特徴点を中心とした局所的な領域を設定する。この領域内に含まれる画素値を使い、局所特徴点ごとに対応する特徴量を計算する。本実施形態ではこのように計算された特徴量を局所特徴量と呼ぶ。
【００１５】
（機能構成）
図１は、第１実施形態における装置の機能構成例を示すブロック図である。図１（ａ）は画像登録装置１００の機能構成であり、図１（ｂ）は画像検索装置２００の機能構成である。
【００１６】
□画像登録装置
まず、図１（ａ）に示す画像登録装置１００について説明する。画像登録装置１００は、入力された画像の局所特徴量を算出して画像特徴データベース１０９に登録する情報処理装置である。画像登録装置１００により、類似画像の検索対象となる画像の特徴量がデータベースに登録される。図１（ａ）に示すように、画像登録装置１００は、画像入力部１０２、縮小画像生成部１０３、要素値計算部１０４、マスク範囲設定部１０５、局所特徴点抽出部１０６、局所特徴量算出部１０７、特徴登録部１０８を有している。
【００１７】
画像登録装置１００において、画像入力部１０２は局所特徴量を算出する画像（登録画像）を入力する機能要素である。縮小画像生成部１０３は、画像入力部１０２に入力された登録画像１０１から縮小率が異なる複数の縮小画像を生成する。
【００１８】
要素値計算部１０４では、複数の縮小画像それぞれについて、後段のマスク範囲設定部１０５で利用する要素値（中間値）を計算する。ただし、要素値は、局所特徴点抽出部１０６での局所特徴点抽出処理あるいは局所特徴量算出部１０７での局所特徴量算出処理の少なくともどちらかで再利用可能な値である。本実施形態では、要素値として、入力画像の各画素位置で輝度勾配振幅を計算する例を説明するが、第２実施形態で説明するようにこれに限られない。なお、もちろん局所特徴点抽出部１０６と局所特徴量算出部１０７の両方で再利用可能であってもよい。
【００１９】
マスク範囲設定部１０５では、要素値を使って登録画像１０１上にマスク範囲を設定する。局所特徴点抽出部１０６では、マスク範囲内だけで局所特徴点の抽出処理を行う。局所特徴点の抽出処理において、要素値を利用可能であるならば利用する。
【００２０】
局所特徴量算出部１０７では、局所特徴点抽出部１０６で抽出した局所特徴点それぞれについて、局所特徴量を算出する。局所特徴量の算出処理において、要素値を利用可能であるならば利用する。特徴登録部１０８では、局所特徴点に関する情報と局所特徴量に関する情報とを登録画像１０１の画像特徴として、画像特徴データベース１０９に登録する。本実施形態における登録処理の詳細については後述する。
【００２１】
□画像検索装置
次に、図１（ｂ）に示す画像検索装置２００について説明する。画像検索装置２００は、クエリとして入力された画像に類似する画像を、画像特徴データベース１０９に局所特徴量が登録された画像から検索する情報処理装置である。すなわち、画像検索装置２００は、画像の特徴量がそれぞれ予めデータベースに登録された複数の登録画像から、入力画像と類似する画像を検索する。ただし、図１（ａ）の画像登録装置１００と同一機能を有する構成には同一符号を付すとともに、構成的、機能的にかわらないものについてはその説明を省略する。画像検索装置２００は、画像入力部１０２（クエリとなる画像を入力する）、縮小画像生成部１０３、要素値計算部１０４、マスク範囲設定部１０５、局所特徴点抽出部１０６、局所特徴量算出部１０７、特徴比較部２０２を有している。
【００２２】
比較手段としての特徴比較部２０２は、局所特徴量算出部１０７が算出した局所特徴量に基づいてクエリ画像２０１に類似した画像を画像特徴データベース１０９に局所特徴量が登録された画像から検索し検索結果２０３として出力する。本実施形態における検索処理の詳細については後述する。
【００２３】
（ハードウェア構成）
上記の画像登録装置１００又は画像検索装置２００は、コンピュータ（情報処理装置）が所定の処理を実行することにより実現される。このようなコンピュータのハードウェア構成について、図２を参照して説明する。図２は、コンピュータのハードウェア構成例を示すブロック図である。なお、本実施形態では、コンピュータに実行させるプログラムを記憶した記憶媒体を、システム或いは装置に供給してプログラムを実行させる。
【００２４】
図２に示すコンピュータ１４００は、ＲＯＭ１４３０の中に後述するフローチャートの処理をＣＰＵ１４１０に実行させるプログラムを格納している。そして、プログラムを実行させる際にＲＯＭ１４３０のプログラムをＲＡＭ１４２０に読出しＣＰＵ１４１０が処理できるようにする。ここで、１４５０はバスであり、ＲＯＭ１４３０、ＲＡＭ１４２０、ＣＰＵ１４１０およびＨＤＤ１４４０のデータをやりとりする。
【００２５】
また、コンピュータ１４００はユーザインターフェースに接続されるキーボードやマウスなどの入出力機器からの入力を受ける。コンピュータ１４００は、ネットワークインターフェース１４７０に対して入出力等を行う。コンピュータ１４００のネットワークインターフェース１４７０はネットワーク１５００を介して、データベース（ＤＢ）１５１０、クライアント（ＣＬＩＥＮＴ）１５２０、プリンタ（ＰＲＩＮＴＥＲ）１５３０と通信可能である。
【００２６】
コンピュータ１４００は、複数のハードウェアとソフトウェアの協同によって前述の実施形態の処理を実現してもよい。例えば、図１（ａ），（ｂ）で示す構成は、その構成の一部をソフトウェアで実現可能であるし、あるいは、特定の処理に特化したＩＣでも実現可能である。他にも、ネットワークで接続している複数の機器の協同によって実現してもよい。図２を用いて例を挙げると、コンピュータ１４００がプリンタ１５３０やクライアント１５２０から画像を受付けて、コンピュータ１４００が図３のフローチャートの処理を行い、データベース１５１０に登録する構成が挙げられる。また、例えば、コンピュータ１４００がクライアント１５２０やプリンタ１５３０から検索依頼とクエリ画像を受付けて、後述する図５のフローチャートの処理を行い、データベース１５１０からクエリ画像に類似する画像を検索する構成も挙げられる。
【００２７】
（登録処理）
次に、画像から抽出する局所特徴量を登録する際に行う処理の詳細について説明する。図３は、画像登録装置１００における登録処理の手順を表すフローチャートである。図３の各ステップは、ＣＰＵ１４１０がコンピュータ１４００の処理を制御して実行される。
【００２８】
Ｓ２０１で、画像入力部１０２が登録画像１０１を読み込む。Ｓ２０２〜Ｓ２０４では、入力画像を解析して要素値（中間値）を算出する処理を行う。Ｓ２０２で、画像入力部１０２が登録画像１０１から輝度成分を抽出する。以下、抽出した輝度成分からなる画像データを輝度成分画像とも呼ぶ。
【００２９】
Ｓ２０３では、画像入力部１０２が抽出した輝度成分を縮小画像生成部１０３が縮小変換し、ｎ種の異なる解像度の輝度成分画像を新たに生成する。具体的には、例えば、縮小画像生成部１０３が、画像入力部１０２から取得した輝度成分画像を所定の縮小率ｐに従ってｎ回縮小処理を行い、結果としてｎ枚の縮小画像を取得する（図４参照）。ここで、縮小率ｐ及び縮小回数ｎは予め決められているが、ｎは０以上の整数である必要がある。ただ好ましくは縮小変換を複数回実行することが好ましい。例えば、縮小して２×２画素になる回数を予め演算して決めておいてもよい。
【００３０】
図４は、縮小画像生成部１０３の縮小変換処理を示す図である。図４は、縮小率ｐが２-1/4、縮小画像の枚数ｎ（＝縮小回数）が８の場合である。図４において、画像３０１は画像入力部１０２が入力画像１０１から抽出した輝度成分画像である。画像３０２は輝度成分画像から縮小率ｐに従って４回縮小された縮小画像である。画像３０３は輝度成分画像から縮小率ｐに従って８回縮小された縮小画像である。図中のＳｃはスケール番号であり、縮小回数と一対一に対応している（縮小回数ｎ＝Ｓｃ−１）。
【００３１】
この例では、画像３０２は画像入力部１０２からの輝度成分画像３０１が１／２（＝ｐ4）に縮小された画像に相当し、画像３０３は輝度成分画像が１／４（＝ｐ8）に縮小された画像に相当する。
【００３２】
なお、本実施形態では線形補間による画像の縮小変換を想定して説明するが、これに限られない。例えば、画像を縮小変換する手法としては他にも、単純に画素を間引く手法や低域フィルタ適用後にサンプリングする手法などを用いてもよい。
【００３３】
次に、Ｓ２０４では、縮小画像ごとに要素値（中間値）を算出する。本実施形態では、以下に示す式（１）〜（３）の値を要素値として算出する。ここで、式（１）右辺のＧ（ｘ，ｙ）はガウス関数、Ｉ（ｘ，ｙ）は画像の座標（ｘ，ｙ）における画素値であり、“＊”は畳み込み演算を表す記号である。式（２）は式（１）で定義された変数Ｌのｘに関する偏導関数、式（３）は変数Ｌのｙに関する偏導関数である。ここで、Ｇ（ｘ，ｙ）は予め定められたガウス関数であり、通常は標準偏差σを変数として持つが、式（１）では省略している。本実施形態ではσ＝ａ・ｒとして予め定められる。ここでａは定数であり、ｒは後段の処理で局所特徴量を算出する際に参照する、局所特徴点を中心とした円形領域の半径である。
【００３４】
【数１】
0005507962.tif 000002
【００３５】
ステップＳ２０５では、要素値を使ってマスク範囲を設定する。本実施形態では、以下に示す式（４）を満たす画素位置にマスクを設定していく。ただし、ｔｈはあらかじめ定めるしきい値である。すなわち、本実施形態では輝度勾配の振幅がしきい値以上（ｔｈ以上）となる画素位置にマスクが設定されるようにした。これは、エッジとその近傍画素をマスク範囲に設定したと見ることもできる。
【００３６】
【数２】
0005507962.tif 000003
【００３７】
Ｓ２０６、Ｓ２０７では、マスク範囲を用いて入力画像中の特徴抽出領域を限定し、マスク範囲の設定において使用された要素値（中間値）を再利用して局所的な特徴を抽出する。まず、Ｓ２０６では、局所特徴点を抽出する。局所特徴点の抽出処理は、Ｓ２０５で設定したマスク範囲内の画素に対してＨａｒｒｉｓ作用素（非特許文献２）を作用させて実行する。
【００３８】
【非特許文献２】Ｃ．Ｈａｒｒｉｓ ａｎｄ Ｍ．Ｊ． Ｓｔｅｐｈｅｎｓ，“Ａ  ｃｏｍｂｉｎｅｄ  ｃｏｒｎｅｒ  ａｎｄ  ｅｄｇｅ  ｄｅｔｅｃｔｏｒ，”  Ｉｎ  Ａｌｖｅｙ  Ｖｉｓｉｏｎ  Ｃｏｎｆｅｒｅｎｃｅ，ｐａｇｅｓ  １４７−１５２，  １９８８。
【００３９】
具体的には、Ｈａｒｒｉｓ作用素を作用させて得られた出力画像Ｈ（ｘ，ｙ）上の画素について、当該画素及び当該画素の周囲８近傍にある画素（合計９画素）の画素値を調べる。そして、この画素値が局所極大になる（当該９画素の中で当該画素の画素値が最大になる）点を局所特徴点として抽出する。ただし、画素値が局所極大になったときでも、当該画素値があらかじめ定めたしきい値以下の場合には、強健で耐性のある局所特徴点ではないものと判断し、局所特徴点として抽出しないようにする。ここで、Ｈ（ｘ，ｙ）は以下に示す式（５）で計算される。ただし、“＊”は畳み込み演算を表す記号、ｋは予め定められた定数、Ｍは式（６）で計算される行列である。また、det（Ｍ）は行列Ｍの行列式、trace（Ｍ）は行列Ｍのトレースを表す。式（６）において、σhはあらかじめ定めた標準偏差を表す定数である。ＬxおよびＬyはそれぞれ式（２）および式（３）で計算された数であり、Ｓ２０４で算出した要素値ＬxおよびＬyを再利用することができる。
【００４０】
【数３】
0005507962.tif 000004
【００４１】
Ｓ２０７では、Ｓ２０６で抽出した局所特徴点ごとに局所特徴量を算出する。本実施形態では、局所特徴点とその近傍の画素パターンを数値化したＬｏｃａｌ  Ｊｅｔ及びそれらの導関数の組み合わせを用いて、式（７）で示す局所特徴量を算出する（非特許文献３）。ただし、式（７）の右辺で用いている記号は、式（１）〜（３）および以下に示す式（８）〜（１０）で定義される。式（８）は式（２）で定義された変数Ｌxのｘに関する偏導関数であり、式（９）は式（２）で定義された変数Ｌxのｙに関する偏導関数である。式（１０）は式（３）で定義されたＬyのｙに関する偏導関数である。
【００４２】
【非特許文献３】Ｃ．Ｓｃｈｍｉｄ  ａｎｄ  Ｒ．Ｍｏｈｒ“Ｌｏｃａｌｇｒａｙ  ｖａｌｕｅ  ｉｎｖａｒｉａｎｔｓ  ｆｏｒ  ｉｍａｇｅ  ｒｅｔｒｉｅｖａｌ，”ＩＥＥＥ  Ｔｒａｎｓ．  ＰＡＭＩ．Ｖｏｌ．１９，Ｎｏ．５，ｐｐ５３０−５３５，１９９７。
【００４３】
【数４】
0005507962.tif 000005
【００４４】
式（７）において、ＬxおよびＬyはそれぞれ式（２）および式（３）で計算された数である。ＬxおよびＬyは、例えば、Ｓ２０４で算出した要素値ＬxおよびＬyを再利用することができる。なお、式（８）〜（１０）で計算されるＬxx、Ｌxy、Ｌyyをそれぞれ式（１１）〜（１３）を使って計算してもよい。この場合、Ｌxx、Ｌxy、Ｌyyの算出時にもＳ２０４で算出した要素値ＬxおよびＬyを再利用できる。
【００４５】
【数５】
0005507962.tif 000006
【００４６】
このように、本実施形態では、要素値として算出された輝度勾配振幅を、画像データ値として再利用して、入力画像の局所特徴量を算出する。このため、処理を効率的に実行することが可能である。
【００４７】
ステップ２０８では、局所特徴点に関する情報と局所特徴量に関する情報とを登録画像１０１（画像データ、画像の識別情報など）と関連付けて画像特徴データベース１０９に登録する。本実施形態では、局所特徴点に関する情報として、局所特徴点の座標とスケール番号、局所特徴量に関する情報として、式（７）を使って算出される局所特徴量を登録する。
【００４８】
（検索処理）
次に、画像を検索する際に行う各部の動作について説明する。図５は、画像検索装置２００における検索処理の手順を表すフローチャートである。図５において、図３と同一の機能を有する工程については、同じ符号を付すとともに機能的に同等のものについてはその説明を省略する。図５の各ステップは、ＣＰＵ１４１０がコンピュータ１４００の処理を制御して実行される。
【００４９】
検索処理では、まず、クエリ画像に対してＳ２０１〜Ｓ２０７の処理を行い、局所特徴量を算出する。そして、Ｓ４０１、Ｓ４０２において、入力画像の特徴量と、複数の登録画像の特徴量の各々とを比較して、該入力画像の類似画像を検索する。
【００５０】
Ｓ４０１では、特徴比較部２０２において、局所特徴量算出部１０７がクエリ画像２０１から抽出した局所特徴量と画像特徴データベース１０９に登録されている局所特徴量とを比較する。この比較処理は、画像特徴データベース１０９に登録されている入力画像毎に実行し、比較処理の結果として入力画像毎に類似度を算出する。
【００５１】
次に、Ｓ４０２では検索結果２０３を出力する。検索結果２０３として、例えば、ステップ４０１で算出した類似度と当該類似度の算出元となった画像とを関連付けて類似度の高い順にソートしたものを出力することができる。検索結果として画像のサムネイルも合わせて出力してもよい。
【００５２】
（類似度算出法）
本実施形態における類似度算出法を説明する。説明を簡単にするために、クエリ画像をＱとし画像データベースから取り出した比較対象画像をＳとして、ＱとＳとの類似度を算出する手法（類似度算出法）の詳細を説明する。
【００５３】
クエリ画像Ｑ上にはｑn個局所特徴量が存在し、ｉ番目の局所特徴量をＶq（ｉ）と表す。比較対象画像Ｓ上にはｓn個の局所特徴量が存在し、ｊ番目の局所特徴量をＶs（ｊ）と表す。
【００５４】
まず、Ｖq（ｉ）とＶs（ｊ）のすべての組み合わせについて、それぞれベクトル間のユークリッド距離ｄ＿ｉｊを求める。ｄ＿ｉｊがあらかじめ定めたしきい値以下の時に、比較対象画像Ｓに対して一票投票する。Ｖq（ｉ）とＶs（ｊ）のすべての組み合わせについて比較対象画像Ｓに対する投票が終わったときの投票数をVote（Ｓ）とする。この場合、クエリ画像Ｑの比較対象画像Ｓに対する類似度Sim_QSを以下の式（１４）で算出する。
［数６］
Sim_QS＝Vote（Ｓ）／ｑn          ・・・（１４）
なお、本実施形態では、ベクトル間距離としてユークリッド距離を使ったが、ベクトルの変動との相関があるならば、マハラノビス距離など他の距離を採用してもよい。また、類似度算出に必ずしもベクトル間距離を使う必要はなく、ベクトルの変動との相関がある量であれば、それを使ってもよい。例えば、ベクトル間の角度に基づく類似度算出法を採用してもよい。この場合、ベクトル間の角度が小さいほど類似度が大きくなるような式を定義する必要がある。
【００５５】
上記のように本実施形態の構成においては、後段の特徴点抽出処理あるいは特徴量算出処理で再利用する値を要素値として算出し、この要素値を使って処理対象領域を限定する。このため、検索精度を維持しつつ処理速度を向上させることが可能になる。すなわち、本実施形態では、入力画像にマスク範囲を設定する際に使用した中間値（要素値）を、入力画像から局所的な特徴を抽出する際に再利用するため、高い検索精度と高速な処理速度が両立可能となる。
【００５６】
また、本実施形態では、中間値として輝度勾配振幅を算出する場合の例を説明したが、上述のように、輝度勾配振幅は比較的単純な演算で算出することができるため、全体の演算コストを低く抑えることが可能である。
【００５７】
＜＜第２実施形態＞＞
第１実施形態ではＳ２０６における局所特徴点の抽出法としてＨａｒｒｉｓ作用素を使った手法を説明したが、画像の回転時や縮小時などの画像処理後でも安定して抽出されるような局所特徴点の抽出法であれば他の局所特徴点の抽出法を使ってもよい。他の手法としては、例えば、ＤＯＧ（Ｄｉｆｆｅｒｅｎｃｅ ｏｆ Ｇａｕｓｓｉａｎ）を使った局所特徴点の抽出法などがある（非特許文献４）。
【００５８】
【非特許文献４】Ｄａｖｉｄ  Ｇ．  Ｌｏｗｅ，  “Ｄｉｓｔｉｎｃｔｉｖｅ  Ｉｍａｇｅ  Ｆｅａｔｕｒｅｓ  ｆｒｏｍ  Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｋｅｙｐｏｉｎｔｓ，”   Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ，６０，２（２００４），ｐｐ．９１−１１０。
【００５９】
また、Ｓ２０７における局所特徴量の算出法として、式（７）で示したようにＬｏｃａｌ  Ｊｅｔ及びそれらの導関数の組み合わせを使って算出したが、この算出法に限定されない。画像の回転時や縮小時などの画像処理後でも変動の少ない局所特徴量が算出可能であればよく、他の手法としては、例えば、ＳＩＦＴ特徴量（非特許文献４）やＰＣＡ−ＳＩＦＴ特徴量（非特許文献５）などを利用可能である。あるいはフーリエ変換などの周波数変換後の係数を組み合せて特徴量を構成してもよい。
【００６０】
【非特許文献５】Ｙ．Ｋｅ  ａｎｄ  Ｒ．Ｓｕｋｔｈａｎｋａｒ，“ＰＣＡ−ＳＩＦＴ：  Ａ  Ｍｏｒｅ  Ｄｉｓｔｉｎｃｔｉｖｅ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｆｏｒ  Ｌｏｃａｌ  Ｉｍａｇｅ  Ｄｅｓｃｒｉｐｔｏｒｓ，”  Ｐｒｏｃ．ＣＶＰＲ，２００４。
【００６１】
ただし、第１実施形態で説明した手法とは別の手法を適用する場合は、Ｓ２０４において算出する要素値は、Ｓ２０６あるいはＳ２０７のいずれかあるいは両方で再利用可能であることが好適である。さらに、Ｓ２０５において当該要素値を使って有効なマスク範囲を設定可能であることが好適である。
【００６２】
例えば、Ｓ２０６において局所特徴点抽出にＤＯＧを使う場合は、Ｓ２０４で算出する要素値として、式（１）で算出したＬの値を再利用可能である。また、Ｓ２０７において局所特徴量の算出にＳＩＦＴ特徴量又はＰＣＡ−ＳＩＦＴ特徴量を使う場合は、Ｓ２０４で算出する要素値として、式（２）及び式（３）で算出したＬx及びＬyの値を再利用可能である。これらいずれの場合でも、Ｓ２０５において第１実施形態で説明した手法と同じマスク範囲設定法を利用可能である。あるいは、フーリエ変換などの周波数変換後の係数を組み合せて局所特徴量を算出するように構成することも可能である。この場合、Ｓ２０４で算出する要素値は周波数係数となり、Ｓ２０５でのマスク範囲設定条件として、例えば、周波数変換された入力画像においてピークとなる周波数係数があらかじめ定めた周波数（所定のしきい値）以上であることを条件にする。これにより、Ｓ２０６の処理領域からエッジ成分が少ない画像領域を除くことが可能となり、局所特徴量の算出に要素値を再利用可能となる。
【００６３】
このように、Ｓ２０４において算出する要素値が、Ｓ２０６とＳ２０７との少なくともいずれかで再利用可能であり、Ｓ２０５において当該要素値を使って有効なマスク範囲を設定可能であればよい。この条件が満たされれば、上記の例だけでなく、例えば、色情報を使って要素値を算出し、マスク範囲を設定してもよい。
【００６４】
また、ステップ２０８で登録する情報として局所特徴点の座標とスケール番号、および式（７）を使って算出される局所特徴量を登録するように説明したが、登録情報はこれに限定されない。例えば、登録前にｋ−ｍｅａｎｓ法などを使って局所特徴量をクラスタリングし、クラスタ番号をインデクスとして登録するように構成してもよい。インデクスの登録により検索処理を高速化することができる。
【００６５】
上記のように、後段の特徴点抽出あるいは特徴量算出処理で利用する値を要素値として算出し、この要素値を使って処理対象領域を限定することで、検索精度を維持しつつ処理速度を向上させることが可能になる。
【００６６】
＜＜第３実施形態＞＞
なお、第１実施形態では、Ｓ２０５において輝度勾配の振幅があらかじめ定めたしきい値ｔｈ以上となる画素位置にマスクが設定されるようにしたが、マスク範囲をさらに拡張するように構成してもよい。マスク範囲の拡張法には特に制限はなく、例えば、太線化処理を用いてもよい。このように、マスク範囲をさらに拡張することでより多くの局所特徴点を抽出可能になる。そして、処理速度を向上させつつ、さらに検索精度の維持を確実にすることができる。
【００６７】
また、Ｓ２０５において、例えば、マスク範囲の面積があらかじめ定めた大きさ以上になった場合は、マスク範囲設定を中断してマスク範囲を全画面に設定してもよい。具体的には、マスク範囲を設定する処理を開始してから設定済みのマスク範囲の面積を計測し、当該面積が予め定められた値以上になった場合は、当該処理を中断して、入力画像の全領域に前記マスク範囲を設定してもよい。この場合、入力画像の全領域にマスク範囲を設定して、次の処理に移ることになる。このように構成することで、マスク範囲の設定処理が計算コスト増大の原因になることを避けることが可能になり、処理全体として検索精度を維持しつつ処理速度を向上させることが可能になる。
【００６８】
同様に、輝度勾配の振幅がしきい値ｔｈ以上の画素位置すべてにマスクを設定するのではなく、マスク範囲の設定処理時間があらかじめ定めた時間以上になった場合はマスク範囲設定処理を中断してマスク範囲を全画面に設定し次の処理に移行してもよい。すなわち、マスク範囲を設定する処理を開始してから、当該処理が完了するまでに予め定められた時間が経過した場合は、入力画像の全領域にマスク範囲を設定してもよい。このようにしても、マスク範囲の設定処理が計算コスト増大の原因になることを避けることが可能になり、処理全体として検索精度を維持しつつ処理速度を向上させることが可能になる。
【００６９】
また、Ｓ２０５でのマスク範囲設定において、通常は画面の走査順、すなわち画面右上から左下に向けて処理を実行するが、処理をランダムに実行してもよい。この場合、入力画像を複数の部分領域に分割し、該部分領域をランダムな順序で選択し、選択された順序で部分領域毎にエッジ部分から一定の範囲内の領域にマスク範囲を設定することになる。これにより、例えば、画面の上半分が空で下半分が草原であるような画像を処理する場合に、走査順にマスク設定処理を実行するよりも早い段階でマスク設定処理の計算コストの増大を検知できる。この処理と前述のマスク処理の中断処理とを組み合せることで、マスク範囲の設定処理が計算コスト増大の原因になることを避けることが可能になり、処理全体として検索精度を維持しつつ処理速度を向上させることが可能になる。
【００７０】
あるいは、Ｓ２０５のマスク範囲設定における画面の走査において、画面の走査順、すなわち画面右上から左下に向けて処理を実行するのではなく、この順番を逆順、すなわち左下から右上に向けて処理を実行してもよい。この構成によっても、例えば、画面の上半分が空で下半分が草原であるような画像を処理する場合に、早い段階でマスク設定処理の計算コストの増大を検知できるようになる。この構成と前述のマスク処理の中断処理とを組み合せることで、マスク範囲の設定処理が計算コスト増大の原因になることを避けることが可能になり、処理全体として検索精度を維持しつつ処理速度を向上させることが可能になる。
【００７１】
＜＜その他の実施形態＞＞
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
0005507962.tif 000007
【図２】
0005507962.tif 000008
【図３】
0005507962.tif 000009
【図４】
0005507962.tif 000010
【図５】
0005507962.tif 000011