画像検索装置、画像検索方法およびプログラム
【課題】高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる画像検索装置、画像検索方法およびプログラムを得る。
【解決手段】検索対象画像に対するテンプレート画像による検索位置を移動させつつ、各検索位置における検索対象画像とテンプレート画像との類似度を示す第１の類似度を算出する第１の算出手段と、第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された検索位置を特定する特定手段（Ｓ２）と、検索位置に対して、第１の類似度より算出精度が高い第２の類似度を算出する第２の算出手段（Ｓ３）と、第２の類似度を閾値の初期値として、検索対象画像に対するテンプレート画像による検索を行う検索手段（Ｓ４）とを備えた。
【解決手段】検索対象画像に対するテンプレート画像による検索位置を移動させつつ、各検索位置における検索対象画像とテンプレート画像との類似度を示す第１の類似度を算出する第１の算出手段と、第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された検索位置を特定する特定手段（Ｓ２）と、検索位置に対して、第１の類似度より算出精度が高い第２の類似度を算出する第２の算出手段（Ｓ３）と、第２の類似度を閾値の初期値として、検索対象画像に対するテンプレート画像による検索を行う検索手段（Ｓ４）とを備えた。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索対象画像内においてテンプレート画像と類似する画像領域を検索する画像検索装置、画像検索方法およびプログラムに関する。
【背景技術】
【０００２】
検索対象画像内でテンプレート画像と類似している画像領域を検索する画像処理技術として、フルサーチ法が最も使用されている。このフルサーチ法では、最も類似しているＴ箇所（Ｔは１以上の整数）を検出する場合、検索対象画像上でテンプレート画像を１ピクセル間隔でシフトしつつ、各位置で検索対象画像とテンプレート画像間の類似度を測る類似尺度として、例えば絶対差分値和Ｓｕｍ ｏｆ Ａｂｓｏｌｕｔｅ Ｄｉｆｆｅｒｅｎｃｅｓ（ＳＡＤ）を計算し、最も小さいＳＡＤからＴ番目に小さいＳＡＤまでを与えるＴ個の検索対象画像内のテンプレート画像、若しくはテンプレート画像の類似画像の位置を見つけるものである。
【０００３】
ここで、テンプレート画像Ａにおける位置（ｉ，ｊ）での画素値をａ（ｉ，ｊ）（１≦ｉ≦Ｎ，１≦ｊ≦Ｍ）、検索対象画像Ｂにおける位置（ｉ，ｊ）での画素値をｂ（ｉ，ｊ）（１≦ｉ≦Ｘ，１≦ｊ≦Ｙ，Ｎ≦Ｘ，Ｍ≦Ｙ）、検索位置としてテンプレート画像Ａの座標（１，１）と同じ位置の検索対象画像Ｂの座標値を（ｃ，ｄ）（１≦ｃ≦Ｘ−Ｎ＋１，１≦ｄ≦Ｙ−Ｍ＋１）とすると、検索位置（ｃ，ｄ）でのＳＡＤは以下の（１）式により求めることができる。
【０００４】
【数１】
…（１）
【０００５】
フルサーチ法では、閾値としてＴ個の値を準備し、検索位置までの中でＳＡＤが一番小さい値からＴ番目に小さいＳＡＤまでを、ＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔとし、検出位置でのＳＡＤがＴ番目に小さい値であるＳＡＤｍｉｎ,ｔよりも大きい場合は検出候補ではないとしてスキップし、ＳＡＤｍｉｎ,ｔ以下である場合は、ＳＡＤｍｉｎ,ｔを破棄し、検出位置のＳＡＤを新たに閾値として追加し、Ｔ個の中でソートしてＴ番目に小さい値を新たにＳＡＤｍｉｎ,ｔとする。全ての画素で以上の処理を実施後、Ｔ個の閾値が算出された位置をそれぞれ検出位置として出力する。また場合に応じて、小さい閾値順に結果を出力する。
【０００６】
一方、フルサーチ法における計算時間を削減する手法の一つとして、Ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ法が提案されている。この手法はテンプレート画像を１画素間隔でシフトしてＳＡＤを計算するフルサーチ法とは異なり、まず、粗い画素間隔で検索対象画像全体を探索して、最も小さいＳＡＤからＴ番目に小さいＳＡＤを与えるＴ個の位置を粗く推定し、その後探索で得られた位置の周囲をより細かい画素間隔で探索してより最適な位置を推定するという、ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅの探索戦略に基づいて、最も小さいＳＡＤからＴ番目に小さいＳＡＤまでの値を与えるＴ個の検索対象画像内のテンプレート画像の位置を見つけるものである。
【０００７】
また、フルサーチ法より高速に検索するための手法として、検索対象画像とテンプレート画像との類似度として、例えばＳＡＤやユークリッド距離等のフルサーチ法と同様の繰り返し演算によって得られる類似度を適用し、検索位置での演算途中の類似度が、それまでに得られた閾値を超えたところで当該演算を打ち切って次の検索位置に移動するＳｅｑｕｅｎｔｉａｌ Ｓｉｍｉｌａｒｉｔｙ Ｄｅｔｅｃｔｉｏｎ Ａｌｇｏｒｉｔｈｍ（ＳＳＤＡ法）（例えば、非特許文献１参照）が提案されている。以下、上記閾値を超えたところで当該演算を打ち切った時点における類似度を、「ｓｓｄａ距離」という。
【０００８】
また、フルサーチ法より高速な検索をするための別の手法として、Ｓｕｃｃｅｓｓｉｖｅ Ｅｌｉｍｉｎａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ（ＳＥＡ法）が提案されている（例えば非特許文献２参照）。ＳＥＡ法は、三角不等式｜ａ＋ｂ｜≦｜ａ｜＋｜ｂ｜を用いて、各検索位置においてＳＡＤを計算する必要があるか否かを判定することによりＳＡＤを計算する回数を削減して、画像検索処理を高速化する手法である。
【０００９】
図４は、ＳＥＡ法の処理動作の流れを示すフローチャートである。図４に示すように、ＳＥＡ法においては、各検索位置においてｓｅａ距離であるｓｅａ（ｃ，ｄ）を、以下の（２）式により計算する（ステップＳ３１）。
【００１０】
【数２】
…（２）
【００１１】
次に、このｓｅａ距離が、それまでの検索で得られたＴ番目に小さいＳＡＤであるＳＡＤｍｉｎ,ｔより大きいか否かを判定し（ステップＳ３２）、ｓｅａ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔであれば検索位置（ｃ，ｄ）をスキップし、次の検索位置に移る。一方、ｓｅａ（ｃ，ｄ）≦ＳＡＤｍｉｎ,ｔあれば、この検索位置でＳＡＤ（ｃ，ｄ）を計算し（ステップＳ３３）、このＳＡＤ（ｃ，ｄ）のＳＡＤｍｉｎ,ｔに対する大小を判定する（ステップＳ３４）。ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔの場合、そのまま次の検索位置に移る。ＳＡＤ（ｃ，ｄ）≦ＳＡＤｍｉｎ,ｔの場合は、既に記憶されているＳＡＤｍｉｎ,ｔを破棄し、検出位置のＳＡＤを新たに閾値として追加し、Ｔ個の中でソートしてＴ番目に小さい値を新たにＳＡＤｍｉｎ,ｔとし、この検索位置を記憶する（ステップＳ３５）。この処理を全ての検索位置で実施し（ステップＳ３６、Ｓ３７）、最後の検索位置まで検索が終了した後、最も小さいＳＡＤｍｉｎ,ｔの値、該値が算出された検索位置（ｃ，ｄ）を検索結果として出力する（ステップＳ３８）。これにより、テンプレート画像に最も類似している画像領域の検索位置が出力される。なお、この際の出力対象はＳＡＤｍｉｎ,ｔの値と検索位置（ｃ，ｄ）に限定されず、最終的なＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでが得られたＴ個の検索位置を検索結果として出力する形態としても良い。
【００１２】
ここで、ＳＥＡ法により、ＳＡＤを用いて類似する画像領域を検索する場合に、ｓｅａ（ｃ，ｄ）としてＳＡＤｍｉｎ,ｔより大きな値が得られた時点で、ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔとなり、検索位置をスキップすることができる理由について説明する。
【００１３】
三角不等式｜ｘ｜＋｜ｙ｜≧｜ｘ＋ｙ｜から、
【００１４】
【数３】
…（３）
となる。したがって、
【００１５】
【数４】
…（４）
であれば、
【００１６】
【数５】
…（５）
がｓｅａ距離であるため、
【００１７】
【数６】
…（６）
となるので、当該検索位置でのＳＡＤを計算する必要がなく、スキップ可能となる。
【００１８】
また、画像を複数の矩形に複数の階層で等分割し、閾値を超えるようになるまでより深い階層の矩形毎にｓｅａ距離およびｍｓｅａ距離を計算するＭｕｌｔｉｌｅｖｅｌ Ｓｕｃｃｅｓｓｉｖｅ Ｅｌｉｍｉｎａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ（ＭＳＥＡ法）が提案されている（例えば、非特許文献３参照）。
【００１９】
図５は、ＭＳＥＡ法の処理動作の流れを示すフローチャートである。図５に示すように、ＭＳＥＡ法においては、ＳＥＡ法と同様に、各検索位置においてｓｅａ距離であるｓｅａ（ｃ，ｄ）を計算する（ステップＳ４１）。
【００２０】
次に、このｓｅａ距離がそれまでの検索で得られたＴ番目に小さいＳＡＤであるＳＡＤｍｉｎ,ｔより大きいか否かを判定し（ステップＳ４２）、ｓｅａ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔであれば検索位置（ｃ，ｄ）をスキップし、次の検索位置に移る。ｓｅａ（ｃ，ｄ）≦ＳＡＤｍｉｎ,ｔの場合、この検索位置で第一段階のｍｓｅａ距離であるｍｓｅａ（ｃ，ｄ）を、以下の（７）式と（８）式とにより計算する（ステップＳ４３）。
【００２１】
【数７】
…（７）
【００２２】
【数８】
…（８）
【００２３】
ここで、Ｐ１（１）＝０，Ｐ１（２）＝Ｎ／２，Ｐ１（３）＝Ｎ，Ｑ１（１）＝０，Ｑ１（２）＝Ｎ／２，Ｑ１（３）＝Ｍである。
【００２４】
ｍｓｅａ距離は、テンプレート画像を分割した矩形領域内で個別に計算したｓｅａ距離であるｐｓｅａ距離を総計した値である。ＭＳＥＡ法では、矩形領域はテンプレート画像をｘ軸方向およびｙ軸方向ごとに等分割することにより得られる。
【００２５】
次に、このｍｓｅａ距離がＳＡＤｍｉｎ,ｔより大きいか否かを判定し（ステップＳ４４）、ｍｓｅａ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔであれば検索位置（ｃ，ｄ）をスキップし、次の検索位置に移る。ｍｓｅａ（ｃ，ｄ）＜ＳＡＤｍｉｎ,ｔの場合、事前に設定した全ての段階のｍｓｅａ（ｃ，ｄ）を計算したか否かを判定する（ステップＳ４５）。全ての段階のｍｓｅａ（ｃ，ｄ）を計算していない場合、ステップＳ４３に移行し、この検索位置で次の段階のｍｓｅａ距離を、（９）式と（１０）式とを用いて計算する。
【００２６】
【数９】
…（９）
【００２７】
【数１０】
…（１０）
【００２８】
ここで、Ｐ２（１）＝０，Ｐ２（２）＝Ｎ／４，Ｐ２（３）＝２×Ｎ／４，Ｐ２（４）＝３×Ｎ／４，Ｐ２（５）＝Ｎ，Ｑ２（１）＝０，Ｑ２（２）＝Ｎ／４，Ｑ２（３）＝２×Ｎ／４，Ｑ２（４）＝３×Ｎ／４，Ｑ２（５）＝Ｍである。
【００２９】
第２段階目のｍｓｅａ距離は、第１段階目の各矩形領域を更に等分割して得られる矩形領域を用いて計算する。続いて、同様に、このｍｓｅａ距離とＳＡＤｍｉｎ,ｔとの大小関係により、検索をスキップするか、次の段階のｍｓｅａ距離を計算するかを判定する（ステップＳ４５）。
【００３０】
事前に設定した全ての段階までｍｓｅａ距離を計算し、かつ最後の段階において得られたｍｓｅａ距離がｍｓｅａ（ｃ，ｄ）＜ＳＡＤｍｉｎ,ｔの場合、この検索位置でＳＡＤ（ｃ，ｄ）を計算し（ステップＳ４６）、このＳＡＤ（ｃ，ｄ）のＳＡＤｍｉｎ,ｔに対する大小を判定する（ステップＳ４７）。
【００３１】
ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔの場合、次の検索位置に移る。ＳＡＤ（ｃ，ｄ）≦ＳＡＤｍｉｎ,ｔの場合は、ＳＡＤｍｉｎ,ｔを破棄し、検出位置のＳＡＤを新たに閾値として追加し、Ｔ個の中でソートしてＴ番目に小さい値を新たにＳＡＤｍｉｎ,ｔとし、この検索位置を記憶する（ステップＳ４８）。
【００３２】
この処理を全ての検索位置で実施し（ステップＳ４９、Ｓ５０）、最後の検索位置まで検索が終了した後、最も小さいＳＡＤｍｉｎ,ｔの値、該値が算出された検索位置（ｃ，ｄ）を検索結果として出力する（ステップＳ５１）。これにより、テンプレート画像に最も類似している画像領域の検索位置が出力される。なお、この際の出力対象はＳＡＤｍｉｎ,ｔの値と検索位置（ｃ，ｄ）に限定されず、最終的なＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでが得られたＴ個の検索位置を検索結果として出力する形態としても良い。
【００３３】
ここで、ＭＳＥＡ法により、ＳＡＤを用いて類似する画像領域を検索する場合に、ｍｓｅａ（ｃ，ｄ）としてＳＡＤｍｉｎ,ｔより大きな値が得られた時点で、ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔとなり、検索位置をスキップすることができる理由について説明する。
【００３４】
ＭＳＥＡ法により、ＳＡＤを用いて類似する画像領域を検索する場合には、ＳＥＡ法により、ＳＡＤを用いる場合と同様に、三角不等式から、
【００３５】
【数１１】
…（１１）
が導出される。
【００３６】
【数１２】
…（１２）
がｍｓｅａ距離の第１段階であるため、
【００３７】
【数１３】
…（１３）
となり、第１段階（ｓｅａ距離）から順にチェックしていき、ＳＡＤｍｉｎ,ｔより大きな値が得られた時点で、ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔとなり、検索位置をスキップできる。
【００３８】
図６は、以上の従来技術における画像検索の処理動作の説明に供する模式図である。図６に示すように、フルサーチ法では、検索対象画像５０上でテンプレート画像５１を１画素ずつスライドさせながら、その位置での類似性を判断する。類似度としてＳＡＤを使用した場合、その検索位置（ｃ，ｄ）でのＳＡＤ（ｃ，ｄ）がそれまで検索した中で最小のＳＡＤｍｉｎ,ｔより小さければ、ＳＡＤｍｉｎ,ｔ＝ＳＡＤ（ｃ，ｄ）とし、検索位置（ｃ，ｄ）を記憶する。当該処理を検索対象画像の全ての画像領域において実施し、ＳＡＤｍｉｎ,ｔおよびＳＡＤｍｉｎ,ｔをとる位置（ｃ，ｄ）を出力する。
【００３９】
ＳＡＤ（ｃ，ｄ）は計算処理量が多い（すなわち処理が重い）ことを考慮し、各検索位置（ｃ，ｄ）においてＳＡＤ（ｃ，ｄ）を計算する前に、計算処理量が少ないＳＥＡ法、ＭＳＥＡ法を用いて、ＳＡＤを計算する必要があるのか、計算せずにスキップして次の検索位置に移って良いのかの判定を行うことにより、ＳＡＤの計算を回避した分の処理量を削減し、より高速な検索を行う。この際の判定方法として、簡略化した処理で求められるｓｅａ距離若しくはｍｓｅａ距離を用い、上記値とＳＡＤｍｉｎを比較する。
【００４０】
一方、ＳＥＡ法およびＭＳＥＡ法に対し、ｓｅａ距離若しくはｍｓｅａ距離を用いて、検索対象画像中でｓｅａ距離若しくはｍｓｅａ距離が最小若しくはそれに類する値となる複数の位置を検出し、この位置に対してのみＳＡＤを計算し、最小のＳＡＤをとる位置を検索結果とすることにより、ＳＡＤの計算処理回数を削減するＧｌｏｂａｌ Ｅｌｉｍｉｎａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ（ＧＥＡ法）が提案されている（例えば、非特許文献４参照）。ＧＥＡ法において、Ｔ個の結果を出力する場合、ｓｅａ距離若しくはｍｓｅａ距離が最小若しくはそれに類する値となるＴ個以上の位置を検出し、検出した位置に対してのみＳＡＤを計算し、最も小さいＳＡＤからＴ番目に小さいＳＡＤまでの値をとるＴ個の位置を検索結果とする処理が可能である。
【００４１】
また、ＳＥＡ法およびＭＳＥＡ法に対し、ｓｅａ距離若しくはｍｓｅａ距離を用いて、検索対象画像中でｓｅａ距離若しくはｍｓｅａ距離が最小となる位置を検出し、この位置でＳＡＤを計算し、計算したＳＡＤを閾値として用いて再度開始位置から検索を行い、最小のＳＡＤをとる位置を検索結果とすることにより、ＳＡＤの計算処理回数を削減するＩｎｉｔｉａｌ Ｔｈｒｅｓｈｏｌｄ Ｅｓｔｉｍａｔｉｏｎ（ＩＴＥ法）が提案されている（例えば、非特許文献５参照）。
【先行技術文献】
【非特許文献】
【００４２】
【非特許文献１】D. Barnea and H. Silverman 「A class of algorithms for fast digital image registration」IEEE Transaction on Computers, vol.C-21, no.2 pp.179-186, 1972
【非特許文献２】W. Li and E. Salari 「Successive Elimination Algorithm for Motion Estimation」IEEE Transactions on Image Processing, vol. 4, no.1, pp. 105-107, January 1995
【非特許文献３】X.Q. Gao, C.J. Duanmu, and C.R. Zou 「A Multilevel Successive Elimination Algorithm for Block Matching Motion Estimation」IEEE Transactions on Image Processing, vol.9, no. 3, pp. 501-504, March 2000
【非特許文献４】Y.W. Huang, S.Y. Chien, B.Y. Hsieh, and L.G. Chen 「Global Elimination Algorithm and Architecture Design for Fast Block Matching Motion Estimation」IEEE Transactions on Circuits and Systems for Video Technology, vol.14, no.6, pp.898-907, June 2004
【非特許文献５】森 稔, 柏野邦夫“適応的領域分割と初期閾値推定によるテンプレートマッチングの高速化,” 電子情報通信学会論文誌（D), vol.J94-D, No.5, pp.881-892
【発明の概要】
【発明が解決しようとする課題】
【００４３】
しかしながら、フルサーチ法では、必ず検索対象画像内で最小からＴ番目に小さいＳＡＤをとるＴ個の最適な位置が得られるが、ＳＡＤの計算処理に時間が掛かるという問題がある。
【００４４】
また、Ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ法では、フルサーチ法より高速に画像検索処理が実施できるが、粗い画素間隔で探索するために、必ずしも最適な位置が得られる保証がないという問題がある。
【００４５】
また、ＧＥＡ法も同様に、フルサーチ法より高速に画像検索処理が実施できるが、ｓｅａ距離若しくはｍｓｅａ距離が小さい位置が、必ずしもＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔなる位置とは限らないため、必ずしも最適な位置が得られる保証がないという問題がある。
【００４６】
また、ＩＴＥ 法では、最適な１箇所を検出する処理が想定されている為、ｓｅａ距離若しくはｍｓｅａ距離が最も小さい位置でのＳＡＤが、ＳＡＤｍｉｎ,ｔより小さい値をとる場合、当該値より大きい値であるＳＡＤｍｉｎ,ｔをとる位置が得られないという問題がある。
【００４７】
また、ＳＳＤＡ法ではｓｓｄａ距離を、ＳＥＡ法ではｓｅａ距離を、ＭＳＥＡ法ではｍｓｅａ距離を、各々それまでの検索で得られたＳＡＤｍｉｎ,ｔと比較して、この検索位置での計算処理の途中での打ち切り若しくはＳＡＤの計算を回避することにより、より少ない計算処理で最適な類似位置の検索が可能となる。したがって、最小となるＳＡＤの値が小さいほど、より効率的に処理量が削減されることになる。
【００４８】
しかしながら、ＳＡＤｍｉｎ,ｔが正しく得られる検索位置が検索対象画像中のどこに存在するかは不明のため、検索開始位置に近い場所でＳＡＤｍｉｎ,ｔが得られれば、その後の検索位置での計算の打ち切り回数や削減量がより多くなるが、ＳＡＤｍｉｎ,ｔが得られる位置が検索開始位置から遠くなるほど、その後の検索位置での計算の打ち切り回数や削減量は少なくなる。そのため、どの程度ＳＡＤの計算を打ち切り若しくはスキップできるかは、検索対象画像およびテンプレート画像に依存しており、適用例によってはあまり高速な画像検索処理を実現できないという問題がある。
【００４９】
本発明は、以上のような事情に鑑みてなされたものであり、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる画像検索装置、画像検索方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００５０】
上記目的を達成するために、請求項１に記載の画像検索装置は、検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度を算出する第１の算出手段と、前記第１の算出手段によって算出された前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置を特定する特定手段と、前記特定手段によって特定された前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度を算出する第２の算出手段と、前記第２の算出手段によって算出された前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索を行う検索手段と、を備えたことを特徴とする。
【００５１】
請求項１に記載の画像検索装置によれば、第１の算出手段により、検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度が算出される。また、本発明では、特定手段により、前記第１の算出手段によって算出された前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置が特定される。さらに、本発明では、第２の算出手段により、前記特定手段によって特定された前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度が算出される。なお、上記所定の個数は、複数の個数であっても１個のみであっても良い。
【００５２】
そして、本発明では、検索手段により、前記第２の算出手段によって算出された前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索が行われる。
【００５３】
このように、請求項１に記載の画像検索装置によれば、検索対象画像に対するテンプレート画像による検索位置を移動させつつ、各検索位置における検索対象画像とテンプレート画像との類似度を示す第１の類似度を算出し、算出した第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された検索位置を特定し、特定した検索位置に対して、第１の類似度より算出精度が高い第２の類似度を算出し、算出した第２の類似度を閾値の初期値として画像検索を行うことにより、第２の類似度より算出精度が低く、高速に算出することができる第１の類似度を用いて、検索開始時からより速い段階で類似度の計算の打ち切りや、より少ない計算処理および比較回数で類似度の計算をするか、検索位置をスキップするか否かの判定ができるようになるため、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５４】
なお、本発明に係る画像検索装置において、請求項２に記載したように、前記第１の類似度は、ｓｅａ距離およびｍｓｅａ距離の少なくとも一方であり、前記第２の類似度は、ＳＡＤであるようにしても良い。これにより、第１の類似度としてｓｅａ距離およびｍｓｅａ距離より演算負荷が大きい類似度を用いる場合に比較して、高速でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５５】
また、本発明に係る画像検索装置において、請求項３に記載したように、前記第１の類似度は、ｍｎｃｃであり、前記第２の類似度は、ＮＣＣであるようにしても良い。これにより、第１の類似度としてｍｎｃｃより演算負荷が大きい類似度を用いる場合に比較して、高速でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５６】
また、本発明に係る画像検索装置において、請求項４に記載したように、前記検索対象画像および前記テンプレート画像の積分画像、または前記検索対象画像および前記テンプレート画像の２乗値の積分画像を算出する画像算出手段をさらに備え、前記第１の算出手段および前記第２の算出手段の少なくとも一方は、前記画像算出手段によって算出された前記積分画像の類似度を算出するようにしても良い。これにより、上記積分画像を適用しない場合に比較して、高速でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５７】
一方、上記目的を達成するために、請求項５に記載の画像検索方法は、検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度を算出する第１の算出ステップと、前記第１の算出ステップによって算出した前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置を特定する特定ステップと、前記特定ステップによって特定した前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度を算出する第２の算出ステップと、前記第２の算出ステップによって算出した前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索を行う検索ステップと、を備えている。
【００５８】
従って、請求項５に記載の画像検索方法によれば、請求項１に記載の発明と同様に作用するので、請求項１に記載の発明と同様に、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５９】
一方、上記目的を達成するために、請求項６に記載のプログラムは、コンピュータを、請求項１乃至４の何れか１項記載の画像検索装置として機能させる。
【００６０】
従って、請求項６に記載のプログラムによれば、コンピュータを本発明の画像検索装置と同様に作用させることができるので、当該画像検索装置と同様に、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【発明の効果】
【００６１】
本発明によれば、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる、という効果が得られる。
【図面の簡単な説明】
【００６２】
【図１】実施の形態に係る画像検索装置の構成を示すブロック図である。
【図２】実施の形態に係る画像検索装置の動作の流れを示すフローチャートである。
【図３】図２に示すステップＳ２における処理の詳細動作の流れを示すフローチャートである。
【図４】従来技術による画像検索の処理動作（ＳＥＡ法）の流れを示すフローチャートである。
【図５】従来技術による画像検索の処理動作（ＭＳＥＡ法）の流れを示すフローチャートである。
【図６】従来技術における画像検索の処理動作の説明に供する模式図である。
【発明を実施するための形態】
【００６３】
以下、図面を参照して、本発明の実施の形態に係る画像検索装置を説明する。図１は本実施の形態の構成を示すブロック図である。図１において、符号１００は、コンピュータ装置で構成され、検索対象画像内でテンプレート画像と類似している画像領域を検索する画像検索装置である。画像検索装置１００は、入力部１０、初期閾値設定部２０、画像検索部３０および出力部４０を含んで構成される。
【００６４】
入力部１０は、検索対象画像を示す画像情報（以下、検索対象画像情報という。）と、検索対象画像上にて検索したい画像であるテンプレート画像を示す画像情報（以下、テンプレート画像情報という。）とを入力する。この際の入力方法は任意であり、有線通信や無線通信により外部装置から入力しても良く、画像検索装置１００に記録媒体を接続して当該記録媒体から入力しても良い。
【００６５】
初期閾値設定部２０は、入力部１０により入力された検索対象画像情報が示す検索対象画像上に、同じく入力部１０により入力されたテンプレート画像情報が示すテンプレート画像と同じ大きさの検索対象領域（検索位置）を設定し、テンプレート画像による検索位置を移動させつつ、各検索位置における検索対象画像とテンプレート画像との類似度を示す第１の類似度を算出する。
【００６６】
初期閾値設定部２０は、第１の類似度を算出する際、例えば検索対象画像の左上隅の座標（０，０）から検索位置を１画素ずつ移動させつつ、各検索位置における検索対象画像とテンプレート画像との第１の類似度を計算する。なお、この際の検索位置の開始位置は検索対象画像の左上隅に限らず、右上隅、左下隅、右下隅等、検索対象画像の何れの位置も採り得る。
【００６７】
初期閾値設定部２０は、算出した第１の類似度のうち、最も類似していることを示す値から予め定められた順位で類似していることを示す値までの類似度が算出された検索位置を特定する。なお、本実施の形態では、上記予め定められた順位Ｔとして、１以上の整数を適用する。
【００６８】
そして、初期閾値設定部２０は、特定した検索位置における第２の類似度を算出する。
【００６９】
さらに、初期閾値設定部２０は、Ｔが１でない場合には、算出したＴ個の第２の類似度を類似の度合いが高い順にソーティングした後、算出した第２の類似度の値を画像検索部３０に出力する。なお、出力した第２の類似度の値は、画像検索部３０による検索時に各種判定処理の初期閾値として用いられる。以下では、錯綜を回避するため、順位Ｔが２以上である場合について説明する。
【００７０】
本実施形態に係る第１の類似度および第２の類似度は、以下の（Ａ）および（Ｂ）に示す条件の何れか一方が成り立つものである。
（Ａ）演算負荷：「第１の類似度」＜「第２の類似度」
（Ｂ）算出精度：「第１の類似度」＜「第２の類似度」
【００７１】
なお、第１の類似度および第２の類似度は、上記（Ａ）及び（Ｂ）の双方の条件が成り立つものであってもよい。以下、本実施形態では、第１の類似度および第２の類似度が上記（Ａ）及び（Ｂ）の双方の条件を満たすものとして説明する。
【００７２】
本実施の形態では、第１の類似度として前述したｓｅａ距離およびｍｓｅａ距離を用いており（ｍｓｅａ距離において分割数が０（零）の場合がｓｅａ距離である）、第２の類似度として前述したＳＡＤを用いている。
【００７３】
なお、第１および第２の類似度は、値が小さいほど、類似していることを意味する。よって、各類似度において最も類似している画像領域とは、検索対象画像とテンプレート画像との間のｓｅａ距離、ｍｓｅａ距離ないしＳＡＤが最小となる画像領域を意味する。同様に、各類似度においてＴ番目に類似している画像領域とは、検索対象画像とテンプレート画像との間のｓｅａ距離、ｍｓｅａ距離ないしＳＡＤがＴ番目に小さい値となる画像領域を意味する。
【００７４】
また、初期閾値設定部２０は、検索対象画像内の各検索位置における第１の類似度を計算する際に、検索対象画像に対する積分画像とテンプレート画像に対する積分画像とをそれぞれ生成し、生成した各々の積分画像を用いて計算しても良い。
【００７５】
一方、画像検索部３０は、初期閾値設定部２０から入力した第２の類似度を初期閾値として、検索対象画像に対するテンプレート画像による画像検索を行う。この際、画像検索部３０は、第２の類似度の値を、最も小さい値からＴ番目に小さい値までのＴ個の初期閾値として設定し、検索対象画像においてテンプレート画像と同じ大きさの画像領域を切り出し、この切り出した画像領域（検索位置）において、予め定められた類似度を用いて画像検索を実行する。
【００７６】
例えば、検索方法としてＳＳＤＡ法を用いる場合、テンプレート画像と検索対象画像における検索位置との間の類似度の計算途中のｓｓｄａ距離と、それまで検索して得られたＴ番目に類似の度合いが高い閾値（ＳＡＤｍｉｎ,ｔ）とを比較し、ｓｓｄａ距離が当該閾値より大きい場合は、そのときの検索位置をスキップする。この検索位置において、一度もスキップせず類似度の計算を終えた場合は、最後に得られた類似度（ｓｓｄａ距離＝ＳＡＤ）とそれまで検索して得られたＴ番目に類似の度合いが高い閾値とを比較し、計算した類似度が当該閾値より小さい値である場合のみ、当該閾値を破棄し、計算した類似度を新たに閾値として追加し、Ｔ個の閾値をソートして最も類似の度合いが高い閾値からＴ番目に類似の度合いが高い閾値までをＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでのＴ個の閾値として新たに設定する。
【００７７】
また、検索方法としてフルサーチ法を用いた場合は、テンプレート画像と検索対象画像における検索位置と間のＳＡＤをＴ番目に類似の度合いが高い閾値（ＳＡＤｍｉｎ,ｔ）と比較し、ＳＡＤが当該閾値より大きい値である場合は、そのときの検索位置をスキップする。そうでない場合は、Ｔ番目に類似の度合いが高い閾値（ＳＡＤｍｉｎ,ｔ）を破棄し、計算したＳＡＤを新たに閾値として追加し、Ｔ個の閾値をソートして最も類似の度合いが高い閾値からＴ番目に類似の度合いが高い閾値までをＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでのＴ個の閾値として新たに設定する。この処理を検索対象画像上で検索位置をずらしながら繰り返し、テンプレート画像との間の類似度の、最も類似の度合いが高い値からＴ番目に類似の度合いが高い値までに対応するＴ個の検索位置を、検索対象画像内でテンプレート画像と類似しているＴ箇所の画像領域として検索する。
【００７８】
また、検索手法としてＳＥＡ法若しくはＭＳＥＡ法を用いる場合、テンプレート画像と検索対象画像における検索位置との間の各分割段階での類似度（ｓｅａ距離若しくはｍｓｅａ距離）を計算し、計算した類似度とそれまでの検索で得られたＴ番目に類似の度合いが高い閾値（ＳＡＤを用いた場合はＳＡＤｍｉｎ,ｔ）とを比較することにより、その時点の検索対象画像の検索位置についてテンプレート画像との詳細な類似度（ＳＡＤ）を計算するか否かを決定する。このとき、各検索位置において、最終段階での類似度がそれまでの検索で得られた類似度の最も類似の度合いが高い閾値よりも類似の度合いが高い場合には上記詳細な類似度を計算し、この類似度がそれまでの検索で得られているＴ番目に類似の度合いが高い閾値よりも値が小さい場合のみ、当該閾値を破棄し、計算した上記詳細な類似度を新たに閾値として追加した後、Ｔ個の閾値をソートして最も類似の度合いが高い値からＴ番目に類似の度合いが高い値までをＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔとして新たに設定する。この処理を検索対象画像上で検索位置をずらしながら繰り返し、テンプレート画像との上記詳細な類似度が最も類似の高い値からＴ番目に類似の度合いが高い値までに対応するＴ個の検索位置を、検索対象画像内でテンプレート画像と最も類似している画像領域として検索する。
【００７９】
出力部４０は、画像検索部３０による検索結果、すなわち、検索対象画像内でテンプレート画像と類似している画像領域を示す情報を出力する。なお、この画像領域を示す情報は、検索対象画像内におけるテンプレート画像と類似している画像領域の、検索対象画像内における位置を示す情報としても良い。この位置を示す情報は、例えば当該画像領域の検索対象画像における左上隅の座標値を例示することができる。
【００８０】
次に、図２を参照して、本実施の形態に係る画像検索装置１００の処理動作を説明する。図２は、本実施の形態に係る画像検索装置１００の処理動作の流れを示すフローチャートである。
【００８１】
まず、入力部１０は、検索対象画像情報を入力する。そして、入力部１０は、検索クエリーであるテンプレート画像情報を入力する（ステップＳ１）。双方の画像情報が入力された後、初期閾値設定部２０は、入力部１０により入力したテンプレート画像情報により示されるテンプレート画像に対して、第１の類似度の値が最も類似していることを示す値（最小値）から予め定められた順位Ｔで類似していることを示す値までのＴ個の第１の類似度となる検索位置を特定する（ステップＳ２）。
【００８２】
次に、初期閾値設定部２０は、特定したＴ個の検索位置における第２の類似度を求め、そして、Ｔ個の第２の類似度をソーティングし、最も値が小さい第２の類似度からＴ番目に値が小さい第２の類似度までのＴ個の値を画像検索部３０に対して出力する（ステップＳ３）。
【００８３】
続いて、画像検索部３０は、初期閾値設定部２０から入力したＴ個の値を初期閾値として、この初期閾値を用いて画像検索処理を行い、Ｔ個の画像領域を類似箇所として検出する（ステップＳ４）。
【００８４】
出力部４０は、画像検索部３０により検出された類似箇所を検索結果として出力する（ステップＳ５）。
【００８５】
以上の処理動作により、本実施の形態に係る画像検索装置１００は、検索対象画像内においてテンプレート画像と類似しているＴ個の画像領域を検索することができる。なお、出力部４０により出力される検索結果は、Ｔ個の画像領域を出力するものに限定されず、テンプレート画像に最も類似している１個の画像領域を出力するものとしても良い。また、出力部４０は、画像領域を出力する際、表示装置（図示省略。）に検索対象画像を表示させると共に、表示させた検索対象画像上に、テンプレート画像と類似しているＴ個の画像領域を、例えば矩形状の枠で表示させても良い。
【００８６】
次に、図３を参照して、図２に示すステップＳ２において実行される、初期閾値算出部２０による処理について詳細に説明する。まず、初期閾値設定部２０は、第１の類似度および第２の類似度を算出する際に画素値の積分値を高速に求めるため、テンプレート画像および検索対象画像から各々に対応する積分画像を作成する（ステップＳ２０）。例えば、テンプレート画像ａに対する積分画像ａｉの座標（ｉ，ｊ）における積分値ａｉ（ｉ，ｊ）は、（１４）式により算出する。
【００８７】
【数１４】
…（１４）
【００８８】
但し、ａ（０，０）＝ａ（０，１）＝ａ（１，０）＝０である。
【００８９】
同様に、検索対象画像ｂに対する積分画像ｂｉの座標（ｉ，ｊ）における積分値ｂｉ（ｉ，ｊ）は、（１５）式により算出する。
【００９０】
【数１５】
…（１５）
【００９１】
但し、ｂ（０，０）＝ｂ（０，１）＝ｂ（１，０）＝０である。
【００９２】
次に、初期閾値設定部２０は、検索対象画像上にテンプレート画像と同じ大きさの領域（検索位置）を設定し、例えば左上隅の座標（０，０）から検索位置を１画素ずつ移動させながら、各検索位置における検索対象画像とテンプレート画像との間の第１の類似度を計算する（ステップＳ２１）。この第１の類似度は、画像検索部３０における閾値検索向けの類似度であり、ｓｅａ距離を示す（２）式や、ｍｓｅａ距離を示す（７）式などを利用する。なお、以下のステップでは、ｓｅａ距離および１段階目のｍｓｅａ距離を利用する場合について説明する。
【００９３】
初期閾値設定部２０は、検索対象画像の検索位置（ｃ，ｄ）におけるｓｅａ距離を算出する処理を行う。続いて、初期閾値設定部２０は、このｓｅａ距離がそれまでの画像検索で得られたＴ番目に小さい閾値であるＴＨｍｉｎ,ｔ以上であるか否かを判定する（ステップＳ２２）。本実施の形態では、本ステップＳ２の実行を始める前の初期値として、ＴＨｍｉｎ,１からＴＨｍｉｎ,ｔまでのＴ個の各閾値は十分に大きい値に設定されている。この判定の結果が、ｓｅａ（ｃ，ｄ）≧ＴＨｍｉｎ,ｔである場合、初期閾値設定部２０は、検索位置（ｃ，ｄ）をスキップし、全ての位置での検索が終了しているか否かを判定する（ステップＳ２６）。ステップＳ２６で判定した結果が、全ての位置での検索が終了していない場合、初期閾値設定部２０は、次の検索位置に移る（ステップＳ２７）。
【００９４】
一方、ステップＳ２２の判定結果が、ｓｅａ（ｃ，ｄ）≧ＴＨｍｉｎ,ｔでない場合、初期閾値設定部２０は、この検索位置で第１段階のｍｓｅａ距離であるｍｓｅａ（ｃ，ｄ）を（１６）式により計算する（ステップＳ２３）。
【００９５】
【数１６】
…（１６）
【００９６】
ここで、初期閾値設定部２０は、各ｐｓｅａ距離を高速に算出するために、先に作成した積分画像ａｉおよびｂｉを用いる。ここで、Ｕ１（ｋ）＜ｘ≦Ｕ１（ｋ＋１）およびＶ１（ｋ）＜ｙ≦Ｖ１（ｋ＋１）のｐｓｅａ距離は、（１７）式、（１８）式および（１９）式により算出する。
【００９７】
【数１７】
…（１７）
【００９８】
【数１８】
…（１８）
【００９９】
【数１９】
…（１９）
【０１００】
このＵ１（１），…，Ｕ２（３）は、第１段階のｍｓｅａ距離を求める際のｘ軸方向の分割位置の各座標である。また、Ｖ１（１），…，Ｖ１（３）も、Ｕ１（１），…，Ｕ２（３）と同様に、第１段階のｍｓｅａ距離を求める際のｙ軸方向の分割位置の座標である。
【０１０１】
次に、初期閾値設定部２０は、計算したｍｓｅａ距離がＴＨｍｉｎ,ｔ以上であるか否かを判定する（ステップＳ２４）。この判定した結果がｍｓｅａ（ｃ，ｄ）≧ＴＨｍｉｎ,ｔである場合、初期閾値設定部２０は、検索位置（ｃ，ｄ）をスキップし、次の検索位置に移る（ステップＳ２６、Ｓ２７）。一方、判定した結果がｍｓｅａ（ｃ，ｄ）≧ＴＨｍｉｎ,ｔでない場合（ｍｓｅａ（ｃ，ｄ）＜ＴＨｍｉｎ,ｔの場合）、初期閾値設定部２０は、ＴＨｍｉｎ,ｔをこのｍｓｅａ（ｃ，ｄ）に更新し、ＴＨｍｉｎ，１からＴＨｍｉｎ，ｔまでのＴ個をソートし、最小の値からＴ番目に小さい各閾値を再度ＴＨｍｉｎ，１からＴＨｍｉｎ，ｔとして設定する。
【０１０２】
また、初期閾値設定部２０は、このときの検索位置（ｃ，ｄ）を記憶する（ステップＳ２５）。初期閾値設定部２０は、このような処理を検索対象画像における全ての検索位置で実行する（ステップＳ２６、Ｓ２７）。このようにして、検索対象画像における最後の検索位置まで検索が終了する。
【０１０３】
次に、画像検索部３０の処理動作（図２におけるステップＳ４の処理動作）の詳細を説明する。前述したように、ステップＳ３において、初期閾値設定部２０は、ＴＨｍｉｎ，１からＴＨｍｉｎ，ｔまでに対応するＴ個の検索位置（ｃ，ｄ）において、ＳＡＤ（ｃ，ｄ）を計算し、得られたＴ個のＳＡＤをソーティングし、画像検索部３０に出力する。これを受けて、画像検索部３０は、最も小さいＳＡＤからＴ番目に小さいＳＡＤであるＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでのＴ個の値を各々の初期閾値として設定する。画像検索部３０は、このＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでのＴ個の値を閾値として用いて、検索対象画像に対する画像検索を各検索位置で実行する。
【０１０４】
画像検索部３０は、例えば公知のＭＳＥＡ法（図５参照）を用いて、画像検索処理を行う。ここで、画像検索部３０は、ＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでを閾値として用いることにより、計算処理量の削減が可能である画像検索方法であれば、ＭＳＥＡ法でない手法を適用しても良い。例えば、ＳＥＡ法（図４参照）や前述したＳＳＤＡ法により画像検索処理を実行してもよい。その後、画像検索部３０は、ＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでの値が得られた各検索位置（ｃ，ｄ）およびＳＡＤを検索結果として、出力部４０を介して出力する。
【０１０５】
なお、以上の説明においては、全ての検索位置において、ｓｅａ距離およびｍｓｅａ距離の計算を行うが、ＳＡＤを用いたフルサーチ法とは異なり、極めて少ない計算量で実行することが可能である。この場合、ＳＥＡ法およびＭＳＥＡ法での検索結果の出力とは、ＳＡＤの計算を実施しない点が異なる。
【０１０６】
また、本実施の形態は、第１の類似度を算出する際にｓｅａ距離およびｍｓｅａ距離の双方を用いているが、これに限定されず、ｓｅａ距離およびｍｓｅａ距離のいずれか一方のみを用いるようにしても良い。例えば、ｍｓｅａ距離のみを用いる場合には、ステップＳ２１及びＳ２２の処理が省略される。一方、例えば、ｓｅａ距離のみを用いる場合には、ステップＳ２１及びＳ２２の処理が省略され、ステップＳ２３乃至Ｓ２５においてｍｓｅａ距離の代わりにｓｅａ距離が用いられる。
【０１０７】
以上説明したように、本実施の形態に係る画像検索装置１００は、初期閾値設定部２０が、検索対象画像に対して第１の類似度を用いて、この第１の類似度が最も小さい値からＴ番目に小さい値までのＴ個の検索位置を検出する。そして、初期閾値設定部２０が、これらの検索位置において、最終的な画像検索の判定に用いる第２の類似度であるＳＡＤを計算する。次に、初期閾値設定部２０が、このＴ個のＳＡＤをソーティングし、最も値が小さいＳＡＤからＴ番目に値が小さいＳＡＤまでを決定する。そして、初期閾値設定部２０は、決定したＴ個のＳＡＤを画像検索部３０に出力する。画像検索部３０は、初期閾値設定部２０から入力したＴ個のＳＡＤについて、最も値が小さいＳＡＤからＴ番目に値が小さいＳＡＤを、それぞれＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでの初期閾値として設定し、設定した初期閾値を用いて検索対象画像内を検索し、複数の画像領域との類似度が最も類似の度合いが高いものからＴ番目に類似の度合いが高いものまでの画像領域を、検索対象画像内でテンプレート画像と類似している画像領域として検索する。
【０１０８】
これにより、画像検索装置１００は、検索対象画像内でテンプレート画像と類似している複数の画像領域を検索する場合に、より少ない階層および処理回数でＳＡＤを計算するか、その時点の検索位置をスキップするか否かの判定や、より少ない計算回数でのｓｓｄａ距離の計算の打ち切り等を可能とし、検索対象画像内でテンプレート画像と類似している画像領域を高速に検索することができる。
【０１０９】
また、初期閾値設定部２０において、矩形領域内の画素値の積算値を、積分画像を用いて計算することにより、ｓｅａ距離およびｍｓｅａ距離の高速な計算が可能である。
【０１１０】
また、前述した説明では、第１の類似度としてｓｅａ距離およびｍｓｅａ距離の第１段階を用いたが、ｓｅａ距離のみ、若しくはｍｓｅａ距離の第２段階以降の距離を使用することも可能である。
【０１１１】
また、初期閾値設定部２０において、検索位置を１画素ずつ移動させながら第１の類似度を計算したが、さらに高速化する為に、２画素以上の間隔で移動しながら第１の類似度を計算する事も可能である。
【０１１２】
また、前述した説明では、Ｔ＞１を想定しているが、Ｔ＝１とすることで従来のＩＴＥ法と同等の処理を実施する事も可能である。
【０１１３】
また、前述した説明では、画素値の積分値を算出する際に積分画像を用いたが、当然ながら処理時間は増えるものの、都度画素値の加算処理を実行する手法も使用可能である。
【０１１４】
また、前述した説明では、画像検索部３０の画像検索処理の方法としてＭＳＥＡ法を用いたが、類似度の値（ＳＡＤｍｉｎ,ｔ等）を閾値として用いることにより画像検索処理の高速化を図る画像検索処理の方法（ＳＳＤＡ法やＳＥＡ法等）であれば、本発明を適用することが可能である。
【０１１５】
これらにより、従来手法より早い分割段階でＳＡＤ等の画像検索の最終結果の判定に用いる類似度の計算の途中打ち切りや、この類似度の計算を省略する回数が増加し、より高速な画像検索処理が可能となる。また、Ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ法と異なり、画像検索部３０で網羅的な検索を実行することで、必ず最適な結果を得ることが可能である。また、本発明による画像検索装置１００は、画像検索のみならず、ブロックマッチング動き予測法の手法として、ビデオシーケンスの圧縮処理において、２つの隣り合う時間軸の画面上で現在処理中のブロックに最も近いブロックをサーチする目的にも利用可能である。
【０１１６】
また、前述した説明では、初期閾値設定部２０において、画像間の類似性を判定する第１の類似度としてｓｅａ距離およびｍｓｅａ距離を用い、画像検索部３０における検索結果を判定する第２の類似度としてＳＡＤを用いたが、これらとは異なる類似度や判定基準を用いることも可能である。
【０１１７】
以下に、例えば、ＳＡＤの代わりに正規化相関（ＮＣＣ）を、ｓｅａ距離およびｍｓｅａ距離の代わりに、コーシー・シュワルツの不等式から得られるＮＣＣの近似値を各々用いる場合の形態例について説明する。
【０１１８】
なお、第１の類似度としてｓｅａ距離およびｍｓｅａ距離を用いる場合と異なり、第１の類似度としてＮＣＣを用いる場合、第１の類似度は、ＮＣＣの値が大きいほど、類似していることを意味する。
【０１１９】
ＮＣＣの値は、以下の（２０）式で与えられる。
【０１２０】
【数２０】
…（２０）
ここで、
【０１２１】
【数２１】
…（２１）
【０１２２】
【数２２】
…（２２）
【０１２３】
【数２３】
…（２３）
である。また、ここで‖Ａ‖は最初に一度計算すれば良く、また、‖Ｂ（ｃ，ｄ）‖は各検索箇所で１度計算すれば良く、それぞれ以後の計算は不要である。
【０１２４】
コーシー・シュワルツの不等式は、以下の（２４）式で与えられる。
【０１２５】
【数２４】
…（２４）
【０１２６】
この場合、ψ（ｃ，ｄ）にコーシー・シュワルツの不等式を適用すると、以下の（２５）式となる。
【０１２７】
【数２５】
…（２５）
【０１２８】
第ｑ段目に分割された状態から得られる値をｍｃｃｌｅｖｅｌｑとすると、
【０１２９】
【数２６】
…（２６）
となるので、ＭＳＥＡ法の場合と同様に、
【０１３０】
【数２７】
…（２７）
の関係が得られる。
【０１３１】
上記値に、‖Ａ‖と‖Ｂ（ｃ，ｄ）‖を用いて、検索位置のｍｎｃｃ（ｃ，ｄ）を以下の（２８）式により計算する。
【０１３２】
【数２８】
…（２８）
【０１３３】
従って、例えば前述の例における初期閾値設定部２０における検索でのｓｅａ距離およびｍｓｅａ距離の代わりに、ｍｎｃｃを第０段目から予め指定した段階までを利用して、最も大きいｍｎｃｃからＴ番目に大きいｍｎｃｃまでのＴ個の位置を検出し、この検出位置で得られるＴ個のＮＣＣをソーティングして大きい順に１番目からＴ番目までのＮＣＣの値を求め、各ＮＣＣの値を画像検索部３０に出力し、画像検索部３０で最も値が大きいＮＣＣからＴ番目に値が大きいＮＣＣまでを、ＮＣＣｍａｘ,１からＮＣＣｍａｘ,ｔまでの初期閾値として設定し、これらのＴ個の閾値を用いて、画像検索部３０において画像検索結果を判定する類似度としてＮＣＣを用いて画像検索処理をすることにより、より少ない計算量で画像検索を実行することが可能となる。
【０１３４】
また、ＳＡＤの計算時に事前に積分画像を作成しておくことで、各矩形領域内の値の加算（＝積分）を高速に計算可能なことと同様に、事前に２乗値の積分画像を作成しておけば、容易に各矩形領域内の２乗値の加算（＝積分）を計算することが可能となる。具体的には、テンプレート画像ａに対する２乗値の積分画像ａｉ２の座標（ｉ，ｊ）における積分値ａｉ２（ｉ，ｊ）は、以下の（２９）式により算出する。
【０１３５】
【数２９】
…（２９）
【０１３６】
ただし、ａｉ２（０，０）＝ａｉ２（１，０）＝ａｉ２（０，１）＝０である。
【０１３７】
同様に、検索対象画像ｂに対する２乗値の積分画像ｂｉ２の座標（ｉ，ｊ）における積分値ｂｉ２（ｉ，ｊ）は、以下の（３０）式により算出される。
【０１３８】
【数３０】
…（３０）
【０１３９】
ただし、ｂｉ２（０，０）＝ｂｉ２（１，０）＝ｂｉ２（０，１）＝０である。各座標値に囲まれた２乗積分値もＳＡＤを用いた場合の積分画像の例と同様の方法で求められる。
【０１４０】
なお、本実施の形態では、検索対象画像およびテンプレート画像がグレイスケールの画像であるものとして説明したが、これに限定されず、検索対象画像およびテンプレート画像がカラー画像であっても良い。この場合、カラー画像情報におけるＲ（赤）、Ｇ（緑）、Ｂ（青）の原色毎に本実施の形態に記載の第１の類似度および第２の類似度を演算し、これら類似度を用いて画像検索時の初期閾値の算出等を行う。
【０１４１】
また、本実施の形態に係る画像検索装置１００が備えている入力部１０、初期閾値設定部２０、画像検索部３０および出力部４０という各構成は、専用のハードウェアにより実現されるものであってもよく、また、メモリおよびマイクロプロセッサにより実現させるものであってもよい。また、この各構成は、メモリおよびＣＰＵ（中央演算装置）により構成され、各構成の機能を実現するためのプログラムをメモリにロードして実行することによりその機能を実現させるものであってもよい。
【０１４２】
以上説明したように、本発明では、テンプレート画像および検索対象画像間で、演算負荷が小さい第１の類似度を用いて当該類似度が最も類似していることを示すものからＴ番目に類似していることを示すものまでの検索位置を特定し、特定した検索位置においてＳＡＤ等の最終的な画像検索処理結果の判定に用いる第２の類似度を計算し、このＴ個の第２の類似度をソーティングして、最も類似の度合いが高い値からＴ番目に類似の度合いが高い値までのＴ個の第２の類似度を画像検索の各種判定処理に閾値として用いる初期閾値として設定し、このＴ個の初期閾値を用いて再度通常の検索処理を検索開始位置から実行する。本実施の形態では、第１の類似度としてｓｅａ距離やｍｓｅａ距離、若しくはコーシー・シュワルツの不等式から得られるＮＣＣの近似値であるｍｎｃｃを用い、さらにｓｅａ距離やｍｓｅａ距離及びｍｎｃｃを積分画像を用いて計算するようにした。
【０１４３】
これにより、適切な検索位置で得られるＳＡＤ等の検索結果の判定に用いられる類似度の値と同等、若しくは当該類似度の値により近い値を、判定処理で閾値として用いる最も類似の度合いが高い値からＴ番目に類似の度合いが高い値までの初期閾値として設定して画像検索を実行することにより、検索開始時からより速い段階でのＳＡＤ等の類似度の計算の打ち切りや、より少ない計算処理および比較回数で類似度の計算をするか、検索位置をスキップするか否かの判定ができ、検索対象画像内でテンプレート画像と類似している画像領域をより高速に検索することができる。また、本発明による初期閾値を用いて網羅的な画像検索処理を実行することにより、Ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ法やＧＥＡ法とは異なり、必ず最適な検索結果を得ることが可能になる。
【０１４４】
なお、本実施の形態に係る画像検索装置１００の各処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより画像検索処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【０１４５】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【０１４６】
以上、この発明の実施の形態を図面を参照して詳述してきたが、具体的な構成はこの実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１４７】
１０ 入力部
２０ 初期閾値設定部
３０ 画像検索部
４０ 出力部
１００ 画像検索装置
【技術分野】
【０００１】
本発明は、検索対象画像内においてテンプレート画像と類似する画像領域を検索する画像検索装置、画像検索方法およびプログラムに関する。
【背景技術】
【０００２】
検索対象画像内でテンプレート画像と類似している画像領域を検索する画像処理技術として、フルサーチ法が最も使用されている。このフルサーチ法では、最も類似しているＴ箇所（Ｔは１以上の整数）を検出する場合、検索対象画像上でテンプレート画像を１ピクセル間隔でシフトしつつ、各位置で検索対象画像とテンプレート画像間の類似度を測る類似尺度として、例えば絶対差分値和Ｓｕｍ ｏｆ Ａｂｓｏｌｕｔｅ Ｄｉｆｆｅｒｅｎｃｅｓ（ＳＡＤ）を計算し、最も小さいＳＡＤからＴ番目に小さいＳＡＤまでを与えるＴ個の検索対象画像内のテンプレート画像、若しくはテンプレート画像の類似画像の位置を見つけるものである。
【０００３】
ここで、テンプレート画像Ａにおける位置（ｉ，ｊ）での画素値をａ（ｉ，ｊ）（１≦ｉ≦Ｎ，１≦ｊ≦Ｍ）、検索対象画像Ｂにおける位置（ｉ，ｊ）での画素値をｂ（ｉ，ｊ）（１≦ｉ≦Ｘ，１≦ｊ≦Ｙ，Ｎ≦Ｘ，Ｍ≦Ｙ）、検索位置としてテンプレート画像Ａの座標（１，１）と同じ位置の検索対象画像Ｂの座標値を（ｃ，ｄ）（１≦ｃ≦Ｘ−Ｎ＋１，１≦ｄ≦Ｙ−Ｍ＋１）とすると、検索位置（ｃ，ｄ）でのＳＡＤは以下の（１）式により求めることができる。
【０００４】
【数１】
…（１）
【０００５】
フルサーチ法では、閾値としてＴ個の値を準備し、検索位置までの中でＳＡＤが一番小さい値からＴ番目に小さいＳＡＤまでを、ＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔとし、検出位置でのＳＡＤがＴ番目に小さい値であるＳＡＤｍｉｎ,ｔよりも大きい場合は検出候補ではないとしてスキップし、ＳＡＤｍｉｎ,ｔ以下である場合は、ＳＡＤｍｉｎ,ｔを破棄し、検出位置のＳＡＤを新たに閾値として追加し、Ｔ個の中でソートしてＴ番目に小さい値を新たにＳＡＤｍｉｎ,ｔとする。全ての画素で以上の処理を実施後、Ｔ個の閾値が算出された位置をそれぞれ検出位置として出力する。また場合に応じて、小さい閾値順に結果を出力する。
【０００６】
一方、フルサーチ法における計算時間を削減する手法の一つとして、Ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ法が提案されている。この手法はテンプレート画像を１画素間隔でシフトしてＳＡＤを計算するフルサーチ法とは異なり、まず、粗い画素間隔で検索対象画像全体を探索して、最も小さいＳＡＤからＴ番目に小さいＳＡＤを与えるＴ個の位置を粗く推定し、その後探索で得られた位置の周囲をより細かい画素間隔で探索してより最適な位置を推定するという、ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅの探索戦略に基づいて、最も小さいＳＡＤからＴ番目に小さいＳＡＤまでの値を与えるＴ個の検索対象画像内のテンプレート画像の位置を見つけるものである。
【０００７】
また、フルサーチ法より高速に検索するための手法として、検索対象画像とテンプレート画像との類似度として、例えばＳＡＤやユークリッド距離等のフルサーチ法と同様の繰り返し演算によって得られる類似度を適用し、検索位置での演算途中の類似度が、それまでに得られた閾値を超えたところで当該演算を打ち切って次の検索位置に移動するＳｅｑｕｅｎｔｉａｌ Ｓｉｍｉｌａｒｉｔｙ Ｄｅｔｅｃｔｉｏｎ Ａｌｇｏｒｉｔｈｍ（ＳＳＤＡ法）（例えば、非特許文献１参照）が提案されている。以下、上記閾値を超えたところで当該演算を打ち切った時点における類似度を、「ｓｓｄａ距離」という。
【０００８】
また、フルサーチ法より高速な検索をするための別の手法として、Ｓｕｃｃｅｓｓｉｖｅ Ｅｌｉｍｉｎａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ（ＳＥＡ法）が提案されている（例えば非特許文献２参照）。ＳＥＡ法は、三角不等式｜ａ＋ｂ｜≦｜ａ｜＋｜ｂ｜を用いて、各検索位置においてＳＡＤを計算する必要があるか否かを判定することによりＳＡＤを計算する回数を削減して、画像検索処理を高速化する手法である。
【０００９】
図４は、ＳＥＡ法の処理動作の流れを示すフローチャートである。図４に示すように、ＳＥＡ法においては、各検索位置においてｓｅａ距離であるｓｅａ（ｃ，ｄ）を、以下の（２）式により計算する（ステップＳ３１）。
【００１０】
【数２】
…（２）
【００１１】
次に、このｓｅａ距離が、それまでの検索で得られたＴ番目に小さいＳＡＤであるＳＡＤｍｉｎ,ｔより大きいか否かを判定し（ステップＳ３２）、ｓｅａ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔであれば検索位置（ｃ，ｄ）をスキップし、次の検索位置に移る。一方、ｓｅａ（ｃ，ｄ）≦ＳＡＤｍｉｎ,ｔあれば、この検索位置でＳＡＤ（ｃ，ｄ）を計算し（ステップＳ３３）、このＳＡＤ（ｃ，ｄ）のＳＡＤｍｉｎ,ｔに対する大小を判定する（ステップＳ３４）。ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔの場合、そのまま次の検索位置に移る。ＳＡＤ（ｃ，ｄ）≦ＳＡＤｍｉｎ,ｔの場合は、既に記憶されているＳＡＤｍｉｎ,ｔを破棄し、検出位置のＳＡＤを新たに閾値として追加し、Ｔ個の中でソートしてＴ番目に小さい値を新たにＳＡＤｍｉｎ,ｔとし、この検索位置を記憶する（ステップＳ３５）。この処理を全ての検索位置で実施し（ステップＳ３６、Ｓ３７）、最後の検索位置まで検索が終了した後、最も小さいＳＡＤｍｉｎ,ｔの値、該値が算出された検索位置（ｃ，ｄ）を検索結果として出力する（ステップＳ３８）。これにより、テンプレート画像に最も類似している画像領域の検索位置が出力される。なお、この際の出力対象はＳＡＤｍｉｎ,ｔの値と検索位置（ｃ，ｄ）に限定されず、最終的なＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでが得られたＴ個の検索位置を検索結果として出力する形態としても良い。
【００１２】
ここで、ＳＥＡ法により、ＳＡＤを用いて類似する画像領域を検索する場合に、ｓｅａ（ｃ，ｄ）としてＳＡＤｍｉｎ,ｔより大きな値が得られた時点で、ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔとなり、検索位置をスキップすることができる理由について説明する。
【００１３】
三角不等式｜ｘ｜＋｜ｙ｜≧｜ｘ＋ｙ｜から、
【００１４】
【数３】
…（３）
となる。したがって、
【００１５】
【数４】
…（４）
であれば、
【００１６】
【数５】
…（５）
がｓｅａ距離であるため、
【００１７】
【数６】
…（６）
となるので、当該検索位置でのＳＡＤを計算する必要がなく、スキップ可能となる。
【００１８】
また、画像を複数の矩形に複数の階層で等分割し、閾値を超えるようになるまでより深い階層の矩形毎にｓｅａ距離およびｍｓｅａ距離を計算するＭｕｌｔｉｌｅｖｅｌ Ｓｕｃｃｅｓｓｉｖｅ Ｅｌｉｍｉｎａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ（ＭＳＥＡ法）が提案されている（例えば、非特許文献３参照）。
【００１９】
図５は、ＭＳＥＡ法の処理動作の流れを示すフローチャートである。図５に示すように、ＭＳＥＡ法においては、ＳＥＡ法と同様に、各検索位置においてｓｅａ距離であるｓｅａ（ｃ，ｄ）を計算する（ステップＳ４１）。
【００２０】
次に、このｓｅａ距離がそれまでの検索で得られたＴ番目に小さいＳＡＤであるＳＡＤｍｉｎ,ｔより大きいか否かを判定し（ステップＳ４２）、ｓｅａ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔであれば検索位置（ｃ，ｄ）をスキップし、次の検索位置に移る。ｓｅａ（ｃ，ｄ）≦ＳＡＤｍｉｎ,ｔの場合、この検索位置で第一段階のｍｓｅａ距離であるｍｓｅａ（ｃ，ｄ）を、以下の（７）式と（８）式とにより計算する（ステップＳ４３）。
【００２１】
【数７】
…（７）
【００２２】
【数８】
…（８）
【００２３】
ここで、Ｐ１（１）＝０，Ｐ１（２）＝Ｎ／２，Ｐ１（３）＝Ｎ，Ｑ１（１）＝０，Ｑ１（２）＝Ｎ／２，Ｑ１（３）＝Ｍである。
【００２４】
ｍｓｅａ距離は、テンプレート画像を分割した矩形領域内で個別に計算したｓｅａ距離であるｐｓｅａ距離を総計した値である。ＭＳＥＡ法では、矩形領域はテンプレート画像をｘ軸方向およびｙ軸方向ごとに等分割することにより得られる。
【００２５】
次に、このｍｓｅａ距離がＳＡＤｍｉｎ,ｔより大きいか否かを判定し（ステップＳ４４）、ｍｓｅａ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔであれば検索位置（ｃ，ｄ）をスキップし、次の検索位置に移る。ｍｓｅａ（ｃ，ｄ）＜ＳＡＤｍｉｎ,ｔの場合、事前に設定した全ての段階のｍｓｅａ（ｃ，ｄ）を計算したか否かを判定する（ステップＳ４５）。全ての段階のｍｓｅａ（ｃ，ｄ）を計算していない場合、ステップＳ４３に移行し、この検索位置で次の段階のｍｓｅａ距離を、（９）式と（１０）式とを用いて計算する。
【００２６】
【数９】
…（９）
【００２７】
【数１０】
…（１０）
【００２８】
ここで、Ｐ２（１）＝０，Ｐ２（２）＝Ｎ／４，Ｐ２（３）＝２×Ｎ／４，Ｐ２（４）＝３×Ｎ／４，Ｐ２（５）＝Ｎ，Ｑ２（１）＝０，Ｑ２（２）＝Ｎ／４，Ｑ２（３）＝２×Ｎ／４，Ｑ２（４）＝３×Ｎ／４，Ｑ２（５）＝Ｍである。
【００２９】
第２段階目のｍｓｅａ距離は、第１段階目の各矩形領域を更に等分割して得られる矩形領域を用いて計算する。続いて、同様に、このｍｓｅａ距離とＳＡＤｍｉｎ,ｔとの大小関係により、検索をスキップするか、次の段階のｍｓｅａ距離を計算するかを判定する（ステップＳ４５）。
【００３０】
事前に設定した全ての段階までｍｓｅａ距離を計算し、かつ最後の段階において得られたｍｓｅａ距離がｍｓｅａ（ｃ，ｄ）＜ＳＡＤｍｉｎ,ｔの場合、この検索位置でＳＡＤ（ｃ，ｄ）を計算し（ステップＳ４６）、このＳＡＤ（ｃ，ｄ）のＳＡＤｍｉｎ,ｔに対する大小を判定する（ステップＳ４７）。
【００３１】
ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔの場合、次の検索位置に移る。ＳＡＤ（ｃ，ｄ）≦ＳＡＤｍｉｎ,ｔの場合は、ＳＡＤｍｉｎ,ｔを破棄し、検出位置のＳＡＤを新たに閾値として追加し、Ｔ個の中でソートしてＴ番目に小さい値を新たにＳＡＤｍｉｎ,ｔとし、この検索位置を記憶する（ステップＳ４８）。
【００３２】
この処理を全ての検索位置で実施し（ステップＳ４９、Ｓ５０）、最後の検索位置まで検索が終了した後、最も小さいＳＡＤｍｉｎ,ｔの値、該値が算出された検索位置（ｃ，ｄ）を検索結果として出力する（ステップＳ５１）。これにより、テンプレート画像に最も類似している画像領域の検索位置が出力される。なお、この際の出力対象はＳＡＤｍｉｎ,ｔの値と検索位置（ｃ，ｄ）に限定されず、最終的なＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでが得られたＴ個の検索位置を検索結果として出力する形態としても良い。
【００３３】
ここで、ＭＳＥＡ法により、ＳＡＤを用いて類似する画像領域を検索する場合に、ｍｓｅａ（ｃ，ｄ）としてＳＡＤｍｉｎ,ｔより大きな値が得られた時点で、ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔとなり、検索位置をスキップすることができる理由について説明する。
【００３４】
ＭＳＥＡ法により、ＳＡＤを用いて類似する画像領域を検索する場合には、ＳＥＡ法により、ＳＡＤを用いる場合と同様に、三角不等式から、
【００３５】
【数１１】
…（１１）
が導出される。
【００３６】
【数１２】
…（１２）
がｍｓｅａ距離の第１段階であるため、
【００３７】
【数１３】
…（１３）
となり、第１段階（ｓｅａ距離）から順にチェックしていき、ＳＡＤｍｉｎ,ｔより大きな値が得られた時点で、ＳＡＤ（ｃ，ｄ）＞ＳＡＤｍｉｎ,ｔとなり、検索位置をスキップできる。
【００３８】
図６は、以上の従来技術における画像検索の処理動作の説明に供する模式図である。図６に示すように、フルサーチ法では、検索対象画像５０上でテンプレート画像５１を１画素ずつスライドさせながら、その位置での類似性を判断する。類似度としてＳＡＤを使用した場合、その検索位置（ｃ，ｄ）でのＳＡＤ（ｃ，ｄ）がそれまで検索した中で最小のＳＡＤｍｉｎ,ｔより小さければ、ＳＡＤｍｉｎ,ｔ＝ＳＡＤ（ｃ，ｄ）とし、検索位置（ｃ，ｄ）を記憶する。当該処理を検索対象画像の全ての画像領域において実施し、ＳＡＤｍｉｎ,ｔおよびＳＡＤｍｉｎ,ｔをとる位置（ｃ，ｄ）を出力する。
【００３９】
ＳＡＤ（ｃ，ｄ）は計算処理量が多い（すなわち処理が重い）ことを考慮し、各検索位置（ｃ，ｄ）においてＳＡＤ（ｃ，ｄ）を計算する前に、計算処理量が少ないＳＥＡ法、ＭＳＥＡ法を用いて、ＳＡＤを計算する必要があるのか、計算せずにスキップして次の検索位置に移って良いのかの判定を行うことにより、ＳＡＤの計算を回避した分の処理量を削減し、より高速な検索を行う。この際の判定方法として、簡略化した処理で求められるｓｅａ距離若しくはｍｓｅａ距離を用い、上記値とＳＡＤｍｉｎを比較する。
【００４０】
一方、ＳＥＡ法およびＭＳＥＡ法に対し、ｓｅａ距離若しくはｍｓｅａ距離を用いて、検索対象画像中でｓｅａ距離若しくはｍｓｅａ距離が最小若しくはそれに類する値となる複数の位置を検出し、この位置に対してのみＳＡＤを計算し、最小のＳＡＤをとる位置を検索結果とすることにより、ＳＡＤの計算処理回数を削減するＧｌｏｂａｌ Ｅｌｉｍｉｎａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ（ＧＥＡ法）が提案されている（例えば、非特許文献４参照）。ＧＥＡ法において、Ｔ個の結果を出力する場合、ｓｅａ距離若しくはｍｓｅａ距離が最小若しくはそれに類する値となるＴ個以上の位置を検出し、検出した位置に対してのみＳＡＤを計算し、最も小さいＳＡＤからＴ番目に小さいＳＡＤまでの値をとるＴ個の位置を検索結果とする処理が可能である。
【００４１】
また、ＳＥＡ法およびＭＳＥＡ法に対し、ｓｅａ距離若しくはｍｓｅａ距離を用いて、検索対象画像中でｓｅａ距離若しくはｍｓｅａ距離が最小となる位置を検出し、この位置でＳＡＤを計算し、計算したＳＡＤを閾値として用いて再度開始位置から検索を行い、最小のＳＡＤをとる位置を検索結果とすることにより、ＳＡＤの計算処理回数を削減するＩｎｉｔｉａｌ Ｔｈｒｅｓｈｏｌｄ Ｅｓｔｉｍａｔｉｏｎ（ＩＴＥ法）が提案されている（例えば、非特許文献５参照）。
【先行技術文献】
【非特許文献】
【００４２】
【非特許文献１】D. Barnea and H. Silverman 「A class of algorithms for fast digital image registration」IEEE Transaction on Computers, vol.C-21, no.2 pp.179-186, 1972
【非特許文献２】W. Li and E. Salari 「Successive Elimination Algorithm for Motion Estimation」IEEE Transactions on Image Processing, vol. 4, no.1, pp. 105-107, January 1995
【非特許文献３】X.Q. Gao, C.J. Duanmu, and C.R. Zou 「A Multilevel Successive Elimination Algorithm for Block Matching Motion Estimation」IEEE Transactions on Image Processing, vol.9, no. 3, pp. 501-504, March 2000
【非特許文献４】Y.W. Huang, S.Y. Chien, B.Y. Hsieh, and L.G. Chen 「Global Elimination Algorithm and Architecture Design for Fast Block Matching Motion Estimation」IEEE Transactions on Circuits and Systems for Video Technology, vol.14, no.6, pp.898-907, June 2004
【非特許文献５】森 稔, 柏野邦夫“適応的領域分割と初期閾値推定によるテンプレートマッチングの高速化,” 電子情報通信学会論文誌（D), vol.J94-D, No.5, pp.881-892
【発明の概要】
【発明が解決しようとする課題】
【００４３】
しかしながら、フルサーチ法では、必ず検索対象画像内で最小からＴ番目に小さいＳＡＤをとるＴ個の最適な位置が得られるが、ＳＡＤの計算処理に時間が掛かるという問題がある。
【００４４】
また、Ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ法では、フルサーチ法より高速に画像検索処理が実施できるが、粗い画素間隔で探索するために、必ずしも最適な位置が得られる保証がないという問題がある。
【００４５】
また、ＧＥＡ法も同様に、フルサーチ法より高速に画像検索処理が実施できるが、ｓｅａ距離若しくはｍｓｅａ距離が小さい位置が、必ずしもＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔなる位置とは限らないため、必ずしも最適な位置が得られる保証がないという問題がある。
【００４６】
また、ＩＴＥ 法では、最適な１箇所を検出する処理が想定されている為、ｓｅａ距離若しくはｍｓｅａ距離が最も小さい位置でのＳＡＤが、ＳＡＤｍｉｎ,ｔより小さい値をとる場合、当該値より大きい値であるＳＡＤｍｉｎ,ｔをとる位置が得られないという問題がある。
【００４７】
また、ＳＳＤＡ法ではｓｓｄａ距離を、ＳＥＡ法ではｓｅａ距離を、ＭＳＥＡ法ではｍｓｅａ距離を、各々それまでの検索で得られたＳＡＤｍｉｎ,ｔと比較して、この検索位置での計算処理の途中での打ち切り若しくはＳＡＤの計算を回避することにより、より少ない計算処理で最適な類似位置の検索が可能となる。したがって、最小となるＳＡＤの値が小さいほど、より効率的に処理量が削減されることになる。
【００４８】
しかしながら、ＳＡＤｍｉｎ,ｔが正しく得られる検索位置が検索対象画像中のどこに存在するかは不明のため、検索開始位置に近い場所でＳＡＤｍｉｎ,ｔが得られれば、その後の検索位置での計算の打ち切り回数や削減量がより多くなるが、ＳＡＤｍｉｎ,ｔが得られる位置が検索開始位置から遠くなるほど、その後の検索位置での計算の打ち切り回数や削減量は少なくなる。そのため、どの程度ＳＡＤの計算を打ち切り若しくはスキップできるかは、検索対象画像およびテンプレート画像に依存しており、適用例によってはあまり高速な画像検索処理を実現できないという問題がある。
【００４９】
本発明は、以上のような事情に鑑みてなされたものであり、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる画像検索装置、画像検索方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００５０】
上記目的を達成するために、請求項１に記載の画像検索装置は、検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度を算出する第１の算出手段と、前記第１の算出手段によって算出された前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置を特定する特定手段と、前記特定手段によって特定された前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度を算出する第２の算出手段と、前記第２の算出手段によって算出された前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索を行う検索手段と、を備えたことを特徴とする。
【００５１】
請求項１に記載の画像検索装置によれば、第１の算出手段により、検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度が算出される。また、本発明では、特定手段により、前記第１の算出手段によって算出された前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置が特定される。さらに、本発明では、第２の算出手段により、前記特定手段によって特定された前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度が算出される。なお、上記所定の個数は、複数の個数であっても１個のみであっても良い。
【００５２】
そして、本発明では、検索手段により、前記第２の算出手段によって算出された前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索が行われる。
【００５３】
このように、請求項１に記載の画像検索装置によれば、検索対象画像に対するテンプレート画像による検索位置を移動させつつ、各検索位置における検索対象画像とテンプレート画像との類似度を示す第１の類似度を算出し、算出した第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された検索位置を特定し、特定した検索位置に対して、第１の類似度より算出精度が高い第２の類似度を算出し、算出した第２の類似度を閾値の初期値として画像検索を行うことにより、第２の類似度より算出精度が低く、高速に算出することができる第１の類似度を用いて、検索開始時からより速い段階で類似度の計算の打ち切りや、より少ない計算処理および比較回数で類似度の計算をするか、検索位置をスキップするか否かの判定ができるようになるため、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５４】
なお、本発明に係る画像検索装置において、請求項２に記載したように、前記第１の類似度は、ｓｅａ距離およびｍｓｅａ距離の少なくとも一方であり、前記第２の類似度は、ＳＡＤであるようにしても良い。これにより、第１の類似度としてｓｅａ距離およびｍｓｅａ距離より演算負荷が大きい類似度を用いる場合に比較して、高速でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５５】
また、本発明に係る画像検索装置において、請求項３に記載したように、前記第１の類似度は、ｍｎｃｃであり、前記第２の類似度は、ＮＣＣであるようにしても良い。これにより、第１の類似度としてｍｎｃｃより演算負荷が大きい類似度を用いる場合に比較して、高速でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５６】
また、本発明に係る画像検索装置において、請求項４に記載したように、前記検索対象画像および前記テンプレート画像の積分画像、または前記検索対象画像および前記テンプレート画像の２乗値の積分画像を算出する画像算出手段をさらに備え、前記第１の算出手段および前記第２の算出手段の少なくとも一方は、前記画像算出手段によって算出された前記積分画像の類似度を算出するようにしても良い。これにより、上記積分画像を適用しない場合に比較して、高速でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５７】
一方、上記目的を達成するために、請求項５に記載の画像検索方法は、検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度を算出する第１の算出ステップと、前記第１の算出ステップによって算出した前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置を特定する特定ステップと、前記特定ステップによって特定した前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度を算出する第２の算出ステップと、前記第２の算出ステップによって算出した前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索を行う検索ステップと、を備えている。
【００５８】
従って、請求項５に記載の画像検索方法によれば、請求項１に記載の発明と同様に作用するので、請求項１に記載の発明と同様に、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【００５９】
一方、上記目的を達成するために、請求項６に記載のプログラムは、コンピュータを、請求項１乃至４の何れか１項記載の画像検索装置として機能させる。
【００６０】
従って、請求項６に記載のプログラムによれば、コンピュータを本発明の画像検索装置と同様に作用させることができるので、当該画像検索装置と同様に、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる、という効果を奏する。
【発明の効果】
【００６１】
本発明によれば、高速かつ高精度でテンプレート画像に類似する画像領域を検索することができる、という効果が得られる。
【図面の簡単な説明】
【００６２】
【図１】実施の形態に係る画像検索装置の構成を示すブロック図である。
【図２】実施の形態に係る画像検索装置の動作の流れを示すフローチャートである。
【図３】図２に示すステップＳ２における処理の詳細動作の流れを示すフローチャートである。
【図４】従来技術による画像検索の処理動作（ＳＥＡ法）の流れを示すフローチャートである。
【図５】従来技術による画像検索の処理動作（ＭＳＥＡ法）の流れを示すフローチャートである。
【図６】従来技術における画像検索の処理動作の説明に供する模式図である。
【発明を実施するための形態】
【００６３】
以下、図面を参照して、本発明の実施の形態に係る画像検索装置を説明する。図１は本実施の形態の構成を示すブロック図である。図１において、符号１００は、コンピュータ装置で構成され、検索対象画像内でテンプレート画像と類似している画像領域を検索する画像検索装置である。画像検索装置１００は、入力部１０、初期閾値設定部２０、画像検索部３０および出力部４０を含んで構成される。
【００６４】
入力部１０は、検索対象画像を示す画像情報（以下、検索対象画像情報という。）と、検索対象画像上にて検索したい画像であるテンプレート画像を示す画像情報（以下、テンプレート画像情報という。）とを入力する。この際の入力方法は任意であり、有線通信や無線通信により外部装置から入力しても良く、画像検索装置１００に記録媒体を接続して当該記録媒体から入力しても良い。
【００６５】
初期閾値設定部２０は、入力部１０により入力された検索対象画像情報が示す検索対象画像上に、同じく入力部１０により入力されたテンプレート画像情報が示すテンプレート画像と同じ大きさの検索対象領域（検索位置）を設定し、テンプレート画像による検索位置を移動させつつ、各検索位置における検索対象画像とテンプレート画像との類似度を示す第１の類似度を算出する。
【００６６】
初期閾値設定部２０は、第１の類似度を算出する際、例えば検索対象画像の左上隅の座標（０，０）から検索位置を１画素ずつ移動させつつ、各検索位置における検索対象画像とテンプレート画像との第１の類似度を計算する。なお、この際の検索位置の開始位置は検索対象画像の左上隅に限らず、右上隅、左下隅、右下隅等、検索対象画像の何れの位置も採り得る。
【００６７】
初期閾値設定部２０は、算出した第１の類似度のうち、最も類似していることを示す値から予め定められた順位で類似していることを示す値までの類似度が算出された検索位置を特定する。なお、本実施の形態では、上記予め定められた順位Ｔとして、１以上の整数を適用する。
【００６８】
そして、初期閾値設定部２０は、特定した検索位置における第２の類似度を算出する。
【００６９】
さらに、初期閾値設定部２０は、Ｔが１でない場合には、算出したＴ個の第２の類似度を類似の度合いが高い順にソーティングした後、算出した第２の類似度の値を画像検索部３０に出力する。なお、出力した第２の類似度の値は、画像検索部３０による検索時に各種判定処理の初期閾値として用いられる。以下では、錯綜を回避するため、順位Ｔが２以上である場合について説明する。
【００７０】
本実施形態に係る第１の類似度および第２の類似度は、以下の（Ａ）および（Ｂ）に示す条件の何れか一方が成り立つものである。
（Ａ）演算負荷：「第１の類似度」＜「第２の類似度」
（Ｂ）算出精度：「第１の類似度」＜「第２の類似度」
【００７１】
なお、第１の類似度および第２の類似度は、上記（Ａ）及び（Ｂ）の双方の条件が成り立つものであってもよい。以下、本実施形態では、第１の類似度および第２の類似度が上記（Ａ）及び（Ｂ）の双方の条件を満たすものとして説明する。
【００７２】
本実施の形態では、第１の類似度として前述したｓｅａ距離およびｍｓｅａ距離を用いており（ｍｓｅａ距離において分割数が０（零）の場合がｓｅａ距離である）、第２の類似度として前述したＳＡＤを用いている。
【００７３】
なお、第１および第２の類似度は、値が小さいほど、類似していることを意味する。よって、各類似度において最も類似している画像領域とは、検索対象画像とテンプレート画像との間のｓｅａ距離、ｍｓｅａ距離ないしＳＡＤが最小となる画像領域を意味する。同様に、各類似度においてＴ番目に類似している画像領域とは、検索対象画像とテンプレート画像との間のｓｅａ距離、ｍｓｅａ距離ないしＳＡＤがＴ番目に小さい値となる画像領域を意味する。
【００７４】
また、初期閾値設定部２０は、検索対象画像内の各検索位置における第１の類似度を計算する際に、検索対象画像に対する積分画像とテンプレート画像に対する積分画像とをそれぞれ生成し、生成した各々の積分画像を用いて計算しても良い。
【００７５】
一方、画像検索部３０は、初期閾値設定部２０から入力した第２の類似度を初期閾値として、検索対象画像に対するテンプレート画像による画像検索を行う。この際、画像検索部３０は、第２の類似度の値を、最も小さい値からＴ番目に小さい値までのＴ個の初期閾値として設定し、検索対象画像においてテンプレート画像と同じ大きさの画像領域を切り出し、この切り出した画像領域（検索位置）において、予め定められた類似度を用いて画像検索を実行する。
【００７６】
例えば、検索方法としてＳＳＤＡ法を用いる場合、テンプレート画像と検索対象画像における検索位置との間の類似度の計算途中のｓｓｄａ距離と、それまで検索して得られたＴ番目に類似の度合いが高い閾値（ＳＡＤｍｉｎ,ｔ）とを比較し、ｓｓｄａ距離が当該閾値より大きい場合は、そのときの検索位置をスキップする。この検索位置において、一度もスキップせず類似度の計算を終えた場合は、最後に得られた類似度（ｓｓｄａ距離＝ＳＡＤ）とそれまで検索して得られたＴ番目に類似の度合いが高い閾値とを比較し、計算した類似度が当該閾値より小さい値である場合のみ、当該閾値を破棄し、計算した類似度を新たに閾値として追加し、Ｔ個の閾値をソートして最も類似の度合いが高い閾値からＴ番目に類似の度合いが高い閾値までをＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでのＴ個の閾値として新たに設定する。
【００７７】
また、検索方法としてフルサーチ法を用いた場合は、テンプレート画像と検索対象画像における検索位置と間のＳＡＤをＴ番目に類似の度合いが高い閾値（ＳＡＤｍｉｎ,ｔ）と比較し、ＳＡＤが当該閾値より大きい値である場合は、そのときの検索位置をスキップする。そうでない場合は、Ｔ番目に類似の度合いが高い閾値（ＳＡＤｍｉｎ,ｔ）を破棄し、計算したＳＡＤを新たに閾値として追加し、Ｔ個の閾値をソートして最も類似の度合いが高い閾値からＴ番目に類似の度合いが高い閾値までをＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでのＴ個の閾値として新たに設定する。この処理を検索対象画像上で検索位置をずらしながら繰り返し、テンプレート画像との間の類似度の、最も類似の度合いが高い値からＴ番目に類似の度合いが高い値までに対応するＴ個の検索位置を、検索対象画像内でテンプレート画像と類似しているＴ箇所の画像領域として検索する。
【００７８】
また、検索手法としてＳＥＡ法若しくはＭＳＥＡ法を用いる場合、テンプレート画像と検索対象画像における検索位置との間の各分割段階での類似度（ｓｅａ距離若しくはｍｓｅａ距離）を計算し、計算した類似度とそれまでの検索で得られたＴ番目に類似の度合いが高い閾値（ＳＡＤを用いた場合はＳＡＤｍｉｎ,ｔ）とを比較することにより、その時点の検索対象画像の検索位置についてテンプレート画像との詳細な類似度（ＳＡＤ）を計算するか否かを決定する。このとき、各検索位置において、最終段階での類似度がそれまでの検索で得られた類似度の最も類似の度合いが高い閾値よりも類似の度合いが高い場合には上記詳細な類似度を計算し、この類似度がそれまでの検索で得られているＴ番目に類似の度合いが高い閾値よりも値が小さい場合のみ、当該閾値を破棄し、計算した上記詳細な類似度を新たに閾値として追加した後、Ｔ個の閾値をソートして最も類似の度合いが高い値からＴ番目に類似の度合いが高い値までをＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔとして新たに設定する。この処理を検索対象画像上で検索位置をずらしながら繰り返し、テンプレート画像との上記詳細な類似度が最も類似の高い値からＴ番目に類似の度合いが高い値までに対応するＴ個の検索位置を、検索対象画像内でテンプレート画像と最も類似している画像領域として検索する。
【００７９】
出力部４０は、画像検索部３０による検索結果、すなわち、検索対象画像内でテンプレート画像と類似している画像領域を示す情報を出力する。なお、この画像領域を示す情報は、検索対象画像内におけるテンプレート画像と類似している画像領域の、検索対象画像内における位置を示す情報としても良い。この位置を示す情報は、例えば当該画像領域の検索対象画像における左上隅の座標値を例示することができる。
【００８０】
次に、図２を参照して、本実施の形態に係る画像検索装置１００の処理動作を説明する。図２は、本実施の形態に係る画像検索装置１００の処理動作の流れを示すフローチャートである。
【００８１】
まず、入力部１０は、検索対象画像情報を入力する。そして、入力部１０は、検索クエリーであるテンプレート画像情報を入力する（ステップＳ１）。双方の画像情報が入力された後、初期閾値設定部２０は、入力部１０により入力したテンプレート画像情報により示されるテンプレート画像に対して、第１の類似度の値が最も類似していることを示す値（最小値）から予め定められた順位Ｔで類似していることを示す値までのＴ個の第１の類似度となる検索位置を特定する（ステップＳ２）。
【００８２】
次に、初期閾値設定部２０は、特定したＴ個の検索位置における第２の類似度を求め、そして、Ｔ個の第２の類似度をソーティングし、最も値が小さい第２の類似度からＴ番目に値が小さい第２の類似度までのＴ個の値を画像検索部３０に対して出力する（ステップＳ３）。
【００８３】
続いて、画像検索部３０は、初期閾値設定部２０から入力したＴ個の値を初期閾値として、この初期閾値を用いて画像検索処理を行い、Ｔ個の画像領域を類似箇所として検出する（ステップＳ４）。
【００８４】
出力部４０は、画像検索部３０により検出された類似箇所を検索結果として出力する（ステップＳ５）。
【００８５】
以上の処理動作により、本実施の形態に係る画像検索装置１００は、検索対象画像内においてテンプレート画像と類似しているＴ個の画像領域を検索することができる。なお、出力部４０により出力される検索結果は、Ｔ個の画像領域を出力するものに限定されず、テンプレート画像に最も類似している１個の画像領域を出力するものとしても良い。また、出力部４０は、画像領域を出力する際、表示装置（図示省略。）に検索対象画像を表示させると共に、表示させた検索対象画像上に、テンプレート画像と類似しているＴ個の画像領域を、例えば矩形状の枠で表示させても良い。
【００８６】
次に、図３を参照して、図２に示すステップＳ２において実行される、初期閾値算出部２０による処理について詳細に説明する。まず、初期閾値設定部２０は、第１の類似度および第２の類似度を算出する際に画素値の積分値を高速に求めるため、テンプレート画像および検索対象画像から各々に対応する積分画像を作成する（ステップＳ２０）。例えば、テンプレート画像ａに対する積分画像ａｉの座標（ｉ，ｊ）における積分値ａｉ（ｉ，ｊ）は、（１４）式により算出する。
【００８７】
【数１４】
…（１４）
【００８８】
但し、ａ（０，０）＝ａ（０，１）＝ａ（１，０）＝０である。
【００８９】
同様に、検索対象画像ｂに対する積分画像ｂｉの座標（ｉ，ｊ）における積分値ｂｉ（ｉ，ｊ）は、（１５）式により算出する。
【００９０】
【数１５】
…（１５）
【００９１】
但し、ｂ（０，０）＝ｂ（０，１）＝ｂ（１，０）＝０である。
【００９２】
次に、初期閾値設定部２０は、検索対象画像上にテンプレート画像と同じ大きさの領域（検索位置）を設定し、例えば左上隅の座標（０，０）から検索位置を１画素ずつ移動させながら、各検索位置における検索対象画像とテンプレート画像との間の第１の類似度を計算する（ステップＳ２１）。この第１の類似度は、画像検索部３０における閾値検索向けの類似度であり、ｓｅａ距離を示す（２）式や、ｍｓｅａ距離を示す（７）式などを利用する。なお、以下のステップでは、ｓｅａ距離および１段階目のｍｓｅａ距離を利用する場合について説明する。
【００９３】
初期閾値設定部２０は、検索対象画像の検索位置（ｃ，ｄ）におけるｓｅａ距離を算出する処理を行う。続いて、初期閾値設定部２０は、このｓｅａ距離がそれまでの画像検索で得られたＴ番目に小さい閾値であるＴＨｍｉｎ,ｔ以上であるか否かを判定する（ステップＳ２２）。本実施の形態では、本ステップＳ２の実行を始める前の初期値として、ＴＨｍｉｎ,１からＴＨｍｉｎ,ｔまでのＴ個の各閾値は十分に大きい値に設定されている。この判定の結果が、ｓｅａ（ｃ，ｄ）≧ＴＨｍｉｎ,ｔである場合、初期閾値設定部２０は、検索位置（ｃ，ｄ）をスキップし、全ての位置での検索が終了しているか否かを判定する（ステップＳ２６）。ステップＳ２６で判定した結果が、全ての位置での検索が終了していない場合、初期閾値設定部２０は、次の検索位置に移る（ステップＳ２７）。
【００９４】
一方、ステップＳ２２の判定結果が、ｓｅａ（ｃ，ｄ）≧ＴＨｍｉｎ,ｔでない場合、初期閾値設定部２０は、この検索位置で第１段階のｍｓｅａ距離であるｍｓｅａ（ｃ，ｄ）を（１６）式により計算する（ステップＳ２３）。
【００９５】
【数１６】
…（１６）
【００９６】
ここで、初期閾値設定部２０は、各ｐｓｅａ距離を高速に算出するために、先に作成した積分画像ａｉおよびｂｉを用いる。ここで、Ｕ１（ｋ）＜ｘ≦Ｕ１（ｋ＋１）およびＶ１（ｋ）＜ｙ≦Ｖ１（ｋ＋１）のｐｓｅａ距離は、（１７）式、（１８）式および（１９）式により算出する。
【００９７】
【数１７】
…（１７）
【００９８】
【数１８】
…（１８）
【００９９】
【数１９】
…（１９）
【０１００】
このＵ１（１），…，Ｕ２（３）は、第１段階のｍｓｅａ距離を求める際のｘ軸方向の分割位置の各座標である。また、Ｖ１（１），…，Ｖ１（３）も、Ｕ１（１），…，Ｕ２（３）と同様に、第１段階のｍｓｅａ距離を求める際のｙ軸方向の分割位置の座標である。
【０１０１】
次に、初期閾値設定部２０は、計算したｍｓｅａ距離がＴＨｍｉｎ,ｔ以上であるか否かを判定する（ステップＳ２４）。この判定した結果がｍｓｅａ（ｃ，ｄ）≧ＴＨｍｉｎ,ｔである場合、初期閾値設定部２０は、検索位置（ｃ，ｄ）をスキップし、次の検索位置に移る（ステップＳ２６、Ｓ２７）。一方、判定した結果がｍｓｅａ（ｃ，ｄ）≧ＴＨｍｉｎ,ｔでない場合（ｍｓｅａ（ｃ，ｄ）＜ＴＨｍｉｎ,ｔの場合）、初期閾値設定部２０は、ＴＨｍｉｎ,ｔをこのｍｓｅａ（ｃ，ｄ）に更新し、ＴＨｍｉｎ，１からＴＨｍｉｎ，ｔまでのＴ個をソートし、最小の値からＴ番目に小さい各閾値を再度ＴＨｍｉｎ，１からＴＨｍｉｎ，ｔとして設定する。
【０１０２】
また、初期閾値設定部２０は、このときの検索位置（ｃ，ｄ）を記憶する（ステップＳ２５）。初期閾値設定部２０は、このような処理を検索対象画像における全ての検索位置で実行する（ステップＳ２６、Ｓ２７）。このようにして、検索対象画像における最後の検索位置まで検索が終了する。
【０１０３】
次に、画像検索部３０の処理動作（図２におけるステップＳ４の処理動作）の詳細を説明する。前述したように、ステップＳ３において、初期閾値設定部２０は、ＴＨｍｉｎ，１からＴＨｍｉｎ，ｔまでに対応するＴ個の検索位置（ｃ，ｄ）において、ＳＡＤ（ｃ，ｄ）を計算し、得られたＴ個のＳＡＤをソーティングし、画像検索部３０に出力する。これを受けて、画像検索部３０は、最も小さいＳＡＤからＴ番目に小さいＳＡＤであるＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでのＴ個の値を各々の初期閾値として設定する。画像検索部３０は、このＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでのＴ個の値を閾値として用いて、検索対象画像に対する画像検索を各検索位置で実行する。
【０１０４】
画像検索部３０は、例えば公知のＭＳＥＡ法（図５参照）を用いて、画像検索処理を行う。ここで、画像検索部３０は、ＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでを閾値として用いることにより、計算処理量の削減が可能である画像検索方法であれば、ＭＳＥＡ法でない手法を適用しても良い。例えば、ＳＥＡ法（図４参照）や前述したＳＳＤＡ法により画像検索処理を実行してもよい。その後、画像検索部３０は、ＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでの値が得られた各検索位置（ｃ，ｄ）およびＳＡＤを検索結果として、出力部４０を介して出力する。
【０１０５】
なお、以上の説明においては、全ての検索位置において、ｓｅａ距離およびｍｓｅａ距離の計算を行うが、ＳＡＤを用いたフルサーチ法とは異なり、極めて少ない計算量で実行することが可能である。この場合、ＳＥＡ法およびＭＳＥＡ法での検索結果の出力とは、ＳＡＤの計算を実施しない点が異なる。
【０１０６】
また、本実施の形態は、第１の類似度を算出する際にｓｅａ距離およびｍｓｅａ距離の双方を用いているが、これに限定されず、ｓｅａ距離およびｍｓｅａ距離のいずれか一方のみを用いるようにしても良い。例えば、ｍｓｅａ距離のみを用いる場合には、ステップＳ２１及びＳ２２の処理が省略される。一方、例えば、ｓｅａ距離のみを用いる場合には、ステップＳ２１及びＳ２２の処理が省略され、ステップＳ２３乃至Ｓ２５においてｍｓｅａ距離の代わりにｓｅａ距離が用いられる。
【０１０７】
以上説明したように、本実施の形態に係る画像検索装置１００は、初期閾値設定部２０が、検索対象画像に対して第１の類似度を用いて、この第１の類似度が最も小さい値からＴ番目に小さい値までのＴ個の検索位置を検出する。そして、初期閾値設定部２０が、これらの検索位置において、最終的な画像検索の判定に用いる第２の類似度であるＳＡＤを計算する。次に、初期閾値設定部２０が、このＴ個のＳＡＤをソーティングし、最も値が小さいＳＡＤからＴ番目に値が小さいＳＡＤまでを決定する。そして、初期閾値設定部２０は、決定したＴ個のＳＡＤを画像検索部３０に出力する。画像検索部３０は、初期閾値設定部２０から入力したＴ個のＳＡＤについて、最も値が小さいＳＡＤからＴ番目に値が小さいＳＡＤを、それぞれＳＡＤｍｉｎ,１からＳＡＤｍｉｎ,ｔまでの初期閾値として設定し、設定した初期閾値を用いて検索対象画像内を検索し、複数の画像領域との類似度が最も類似の度合いが高いものからＴ番目に類似の度合いが高いものまでの画像領域を、検索対象画像内でテンプレート画像と類似している画像領域として検索する。
【０１０８】
これにより、画像検索装置１００は、検索対象画像内でテンプレート画像と類似している複数の画像領域を検索する場合に、より少ない階層および処理回数でＳＡＤを計算するか、その時点の検索位置をスキップするか否かの判定や、より少ない計算回数でのｓｓｄａ距離の計算の打ち切り等を可能とし、検索対象画像内でテンプレート画像と類似している画像領域を高速に検索することができる。
【０１０９】
また、初期閾値設定部２０において、矩形領域内の画素値の積算値を、積分画像を用いて計算することにより、ｓｅａ距離およびｍｓｅａ距離の高速な計算が可能である。
【０１１０】
また、前述した説明では、第１の類似度としてｓｅａ距離およびｍｓｅａ距離の第１段階を用いたが、ｓｅａ距離のみ、若しくはｍｓｅａ距離の第２段階以降の距離を使用することも可能である。
【０１１１】
また、初期閾値設定部２０において、検索位置を１画素ずつ移動させながら第１の類似度を計算したが、さらに高速化する為に、２画素以上の間隔で移動しながら第１の類似度を計算する事も可能である。
【０１１２】
また、前述した説明では、Ｔ＞１を想定しているが、Ｔ＝１とすることで従来のＩＴＥ法と同等の処理を実施する事も可能である。
【０１１３】
また、前述した説明では、画素値の積分値を算出する際に積分画像を用いたが、当然ながら処理時間は増えるものの、都度画素値の加算処理を実行する手法も使用可能である。
【０１１４】
また、前述した説明では、画像検索部３０の画像検索処理の方法としてＭＳＥＡ法を用いたが、類似度の値（ＳＡＤｍｉｎ,ｔ等）を閾値として用いることにより画像検索処理の高速化を図る画像検索処理の方法（ＳＳＤＡ法やＳＥＡ法等）であれば、本発明を適用することが可能である。
【０１１５】
これらにより、従来手法より早い分割段階でＳＡＤ等の画像検索の最終結果の判定に用いる類似度の計算の途中打ち切りや、この類似度の計算を省略する回数が増加し、より高速な画像検索処理が可能となる。また、Ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ法と異なり、画像検索部３０で網羅的な検索を実行することで、必ず最適な結果を得ることが可能である。また、本発明による画像検索装置１００は、画像検索のみならず、ブロックマッチング動き予測法の手法として、ビデオシーケンスの圧縮処理において、２つの隣り合う時間軸の画面上で現在処理中のブロックに最も近いブロックをサーチする目的にも利用可能である。
【０１１６】
また、前述した説明では、初期閾値設定部２０において、画像間の類似性を判定する第１の類似度としてｓｅａ距離およびｍｓｅａ距離を用い、画像検索部３０における検索結果を判定する第２の類似度としてＳＡＤを用いたが、これらとは異なる類似度や判定基準を用いることも可能である。
【０１１７】
以下に、例えば、ＳＡＤの代わりに正規化相関（ＮＣＣ）を、ｓｅａ距離およびｍｓｅａ距離の代わりに、コーシー・シュワルツの不等式から得られるＮＣＣの近似値を各々用いる場合の形態例について説明する。
【０１１８】
なお、第１の類似度としてｓｅａ距離およびｍｓｅａ距離を用いる場合と異なり、第１の類似度としてＮＣＣを用いる場合、第１の類似度は、ＮＣＣの値が大きいほど、類似していることを意味する。
【０１１９】
ＮＣＣの値は、以下の（２０）式で与えられる。
【０１２０】
【数２０】
…（２０）
ここで、
【０１２１】
【数２１】
…（２１）
【０１２２】
【数２２】
…（２２）
【０１２３】
【数２３】
…（２３）
である。また、ここで‖Ａ‖は最初に一度計算すれば良く、また、‖Ｂ（ｃ，ｄ）‖は各検索箇所で１度計算すれば良く、それぞれ以後の計算は不要である。
【０１２４】
コーシー・シュワルツの不等式は、以下の（２４）式で与えられる。
【０１２５】
【数２４】
…（２４）
【０１２６】
この場合、ψ（ｃ，ｄ）にコーシー・シュワルツの不等式を適用すると、以下の（２５）式となる。
【０１２７】
【数２５】
…（２５）
【０１２８】
第ｑ段目に分割された状態から得られる値をｍｃｃｌｅｖｅｌｑとすると、
【０１２９】
【数２６】
…（２６）
となるので、ＭＳＥＡ法の場合と同様に、
【０１３０】
【数２７】
…（２７）
の関係が得られる。
【０１３１】
上記値に、‖Ａ‖と‖Ｂ（ｃ，ｄ）‖を用いて、検索位置のｍｎｃｃ（ｃ，ｄ）を以下の（２８）式により計算する。
【０１３２】
【数２８】
…（２８）
【０１３３】
従って、例えば前述の例における初期閾値設定部２０における検索でのｓｅａ距離およびｍｓｅａ距離の代わりに、ｍｎｃｃを第０段目から予め指定した段階までを利用して、最も大きいｍｎｃｃからＴ番目に大きいｍｎｃｃまでのＴ個の位置を検出し、この検出位置で得られるＴ個のＮＣＣをソーティングして大きい順に１番目からＴ番目までのＮＣＣの値を求め、各ＮＣＣの値を画像検索部３０に出力し、画像検索部３０で最も値が大きいＮＣＣからＴ番目に値が大きいＮＣＣまでを、ＮＣＣｍａｘ,１からＮＣＣｍａｘ,ｔまでの初期閾値として設定し、これらのＴ個の閾値を用いて、画像検索部３０において画像検索結果を判定する類似度としてＮＣＣを用いて画像検索処理をすることにより、より少ない計算量で画像検索を実行することが可能となる。
【０１３４】
また、ＳＡＤの計算時に事前に積分画像を作成しておくことで、各矩形領域内の値の加算（＝積分）を高速に計算可能なことと同様に、事前に２乗値の積分画像を作成しておけば、容易に各矩形領域内の２乗値の加算（＝積分）を計算することが可能となる。具体的には、テンプレート画像ａに対する２乗値の積分画像ａｉ２の座標（ｉ，ｊ）における積分値ａｉ２（ｉ，ｊ）は、以下の（２９）式により算出する。
【０１３５】
【数２９】
…（２９）
【０１３６】
ただし、ａｉ２（０，０）＝ａｉ２（１，０）＝ａｉ２（０，１）＝０である。
【０１３７】
同様に、検索対象画像ｂに対する２乗値の積分画像ｂｉ２の座標（ｉ，ｊ）における積分値ｂｉ２（ｉ，ｊ）は、以下の（３０）式により算出される。
【０１３８】
【数３０】
…（３０）
【０１３９】
ただし、ｂｉ２（０，０）＝ｂｉ２（１，０）＝ｂｉ２（０，１）＝０である。各座標値に囲まれた２乗積分値もＳＡＤを用いた場合の積分画像の例と同様の方法で求められる。
【０１４０】
なお、本実施の形態では、検索対象画像およびテンプレート画像がグレイスケールの画像であるものとして説明したが、これに限定されず、検索対象画像およびテンプレート画像がカラー画像であっても良い。この場合、カラー画像情報におけるＲ（赤）、Ｇ（緑）、Ｂ（青）の原色毎に本実施の形態に記載の第１の類似度および第２の類似度を演算し、これら類似度を用いて画像検索時の初期閾値の算出等を行う。
【０１４１】
また、本実施の形態に係る画像検索装置１００が備えている入力部１０、初期閾値設定部２０、画像検索部３０および出力部４０という各構成は、専用のハードウェアにより実現されるものであってもよく、また、メモリおよびマイクロプロセッサにより実現させるものであってもよい。また、この各構成は、メモリおよびＣＰＵ（中央演算装置）により構成され、各構成の機能を実現するためのプログラムをメモリにロードして実行することによりその機能を実現させるものであってもよい。
【０１４２】
以上説明したように、本発明では、テンプレート画像および検索対象画像間で、演算負荷が小さい第１の類似度を用いて当該類似度が最も類似していることを示すものからＴ番目に類似していることを示すものまでの検索位置を特定し、特定した検索位置においてＳＡＤ等の最終的な画像検索処理結果の判定に用いる第２の類似度を計算し、このＴ個の第２の類似度をソーティングして、最も類似の度合いが高い値からＴ番目に類似の度合いが高い値までのＴ個の第２の類似度を画像検索の各種判定処理に閾値として用いる初期閾値として設定し、このＴ個の初期閾値を用いて再度通常の検索処理を検索開始位置から実行する。本実施の形態では、第１の類似度としてｓｅａ距離やｍｓｅａ距離、若しくはコーシー・シュワルツの不等式から得られるＮＣＣの近似値であるｍｎｃｃを用い、さらにｓｅａ距離やｍｓｅａ距離及びｍｎｃｃを積分画像を用いて計算するようにした。
【０１４３】
これにより、適切な検索位置で得られるＳＡＤ等の検索結果の判定に用いられる類似度の値と同等、若しくは当該類似度の値により近い値を、判定処理で閾値として用いる最も類似の度合いが高い値からＴ番目に類似の度合いが高い値までの初期閾値として設定して画像検索を実行することにより、検索開始時からより速い段階でのＳＡＤ等の類似度の計算の打ち切りや、より少ない計算処理および比較回数で類似度の計算をするか、検索位置をスキップするか否かの判定ができ、検索対象画像内でテンプレート画像と類似している画像領域をより高速に検索することができる。また、本発明による初期閾値を用いて網羅的な画像検索処理を実行することにより、Ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ法やＧＥＡ法とは異なり、必ず最適な検索結果を得ることが可能になる。
【０１４４】
なお、本実施の形態に係る画像検索装置１００の各処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより画像検索処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【０１４５】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【０１４６】
以上、この発明の実施の形態を図面を参照して詳述してきたが、具体的な構成はこの実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１４７】
１０ 入力部
２０ 初期閾値設定部
３０ 画像検索部
４０ 出力部
１００ 画像検索装置
【特許請求の範囲】
【請求項１】
検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度を算出する第１の算出手段と、
前記第１の算出手段によって算出された前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置を特定する特定手段と、
前記特定手段によって特定された前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度を算出する第２の算出手段と、
前記第２の算出手段によって算出された前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索を行う検索手段と、
を備えたことを特徴とする画像検索装置。
【請求項２】
前記第１の類似度は、ｓｅａ距離およびｍｓｅａ距離の少なくとも一方であり、前記第２の類似度は、ＳＡＤである
ことを特徴とする請求項１記載の画像検索装置。
【請求項３】
前記第１の類似度は、ｍｎｃｃであり、前記第２の類似度は、ＮＣＣである
ことを特徴とする請求項１記載の画像検索装置。
【請求項４】
前記検索対象画像および前記テンプレート画像の積分画像、または前記検索対象画像および前記テンプレート画像の２乗値の積分画像を算出する画像算出手段をさらに備え、
前記第１の算出手段および前記第２の算出手段の少なくとも一方は、前記画像算出手段によって算出された前記積分画像の類似度を算出する
請求項１から請求項３の何れか１項記載の画像検索装置。
【請求項５】
検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度を算出する第１の算出ステップと、
前記第１の算出ステップによって算出した前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置を特定する特定ステップと、
前記特定ステップによって特定した前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度を算出する第２の算出ステップと、
前記第２の算出ステップによって算出した前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索を行う検索ステップと、
を備えたことを特徴とする画像検索方法。
【請求項６】
コンピュータを、
請求項１乃至４の何れか１項記載の画像検索装置として機能させるためのプログラム。
【請求項１】
検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度を算出する第１の算出手段と、
前記第１の算出手段によって算出された前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置を特定する特定手段と、
前記特定手段によって特定された前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度を算出する第２の算出手段と、
前記第２の算出手段によって算出された前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索を行う検索手段と、
を備えたことを特徴とする画像検索装置。
【請求項２】
前記第１の類似度は、ｓｅａ距離およびｍｓｅａ距離の少なくとも一方であり、前記第２の類似度は、ＳＡＤである
ことを特徴とする請求項１記載の画像検索装置。
【請求項３】
前記第１の類似度は、ｍｎｃｃであり、前記第２の類似度は、ＮＣＣである
ことを特徴とする請求項１記載の画像検索装置。
【請求項４】
前記検索対象画像および前記テンプレート画像の積分画像、または前記検索対象画像および前記テンプレート画像の２乗値の積分画像を算出する画像算出手段をさらに備え、
前記第１の算出手段および前記第２の算出手段の少なくとも一方は、前記画像算出手段によって算出された前記積分画像の類似度を算出する
請求項１から請求項３の何れか１項記載の画像検索装置。
【請求項５】
検索対象画像に対する、テンプレート画像による検索位置を移動させつつ、各検索位置における前記検索対象画像と前記テンプレート画像との類似度を示す第１の類似度を算出する第１の算出ステップと、
前記第１の算出ステップによって算出した前記第１の類似度のうち、類似度が高い方から順に所定の個数の第１の類似度について、前記所定の個数の第１の類似度それぞれが算出された前記検索位置を特定する特定ステップと、
前記特定ステップによって特定した前記検索位置に対して、前記第１の類似度より算出精度が高い第２の類似度を算出する第２の算出ステップと、
前記第２の算出ステップによって算出した前記第２の類似度を閾値の初期値として、前記検索対象画像に対する前記テンプレート画像による検索を行う検索ステップと、
を備えたことを特徴とする画像検索方法。
【請求項６】
コンピュータを、
請求項１乃至４の何れか１項記載の画像検索装置として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１３−１０９６５８（Ｐ２０１３−１０９６５８Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５５４２１（Ｐ２０１１−２５５４２１）
【出願日】平成２３年１１月２２日（２０１１．１１．２２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月２２日（２０１１．１１．２２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]