(57)【特許請求の範囲】
【請求項１】
コンピュータに実行させることで、対象画像上に１つ以上の認識対象パターンが含まれているかどうかを判定する方法であって、
（ａ）複数の画素から成る画像について、画像の濃淡パターンに基づいてキーポイントを検出するステップと、
（ｂ）検出されたキーポイントについて、その検出されたキーポイントの周りに分布されているところの複数の画素の候補座標に基づいて、ランダムに画素のペアを複数選択するステップと、
（ｃ）選択された画素のペアについて、その輝度差を計算するステップと、
（ｄ）選択した複数の前記ペアから計算された輝度差を要素とする特徴ベクトルを計算し、前記キーポイントの特徴量とするステップと、
（ｅ）計算された特徴ベクトルをもとに、K-D treeを生成するステップと、
（ｆ）あるキーポイントを検索の対象として、生成されたK-D treeより探索して、その特徴ベクトルとの距離が最も近い対応するキーポイントの特徴ベクトルとの距離を記録するステップと、
（ｇ）距離があるしきい値以下のキーポイントのみを選択するステップと、
（ｈ）選択されたキーポイントについて、特徴ベクトルの大きさ（Ｒｍ）および方向（θｍ）を含んでおり、かつ、画像中心の座標からその特徴点の座標へのオフセット（Ｏｘ、Ｏｙ）を含んでいる、データを提供するステップと、
（ｉ）複数の特徴点の座標（Ｔｘ、Ｔｙ）について、特徴ベクトルの大きさ（Ｒｔ）および方向（θｔ）を提供するステップと、
（ｊ）対象画像上において、Ｔｘ、Ｔｙ、Ｏｘ、Ｏｙ、Ｒｍ、Ｒｔ、θｍ、θｔから導かれるところの、仮想中心点の座標（Ｆｘ、Ｆｙ）を計算するステップと、
（ｋ）仮想中心点の座標（Ｆｘ、Ｆｙ）を中心とした所定の半径（ｒ）内に含まれる、他の仮想中心点の数をカウントするステップと、
（ｌ）カウントされた仮想中心点の数が所定の閾値（Ｎｃ）以上であるかどうかを判断するステップと、
（ｍ）所定の閾値（Ｎｃ）以上であると判断される場合には、その仮想中心点の座標（Ｆｘ、Ｆｙ）および、カウントされた仮想中心点の数を（認識対象パターンが含まれるであろうことを示す候補として）記憶する（残しておく）ステップと、
（ｎ）対象画像における複数の特徴点の全てについて、ステップ（ｋ）〜ステップ（ｍ）を繰り返すステップと、
を含む、方法。
【請求項２】
ステップ（ｉ）における特徴点が、対象画像上の特徴点と、認識対象パターン上の特徴点との、一致特徴点である、請求項１に記載の方法。
【請求項３】
ステップ（ｎ）が、さらにカウントされた仮想中心点の数が最大の仮想中心点の座標（Ｆｘ、Ｆｙ）を認識対象パターンの中心とするステップ
を含む、請求項１に記載の方法。
【請求項４】
対象画像に複数の認識対象パターンが存在する場合は、ステップ（ｎ）において、カウントされた仮想中心点の数が最大の仮想中心点の座標（Ｆｘ、Ｆｙ）を認識対象パターンの１つの中心として保存し、つぎに、仮想中心点の座標（Ｆｘ、Ｆｙ）を中心とした所定の半径（ｒ）内に含まれるすべての仮想中心点を除外して、ステップ（ｎ）を繰り返し、すべての仮想中心点の座標（Ｆｘ、Ｆｙ）について、カウントされた仮想中心点の数が所定の閾値（Ｎｃ）未満であれば、ステップ（ｎ）を終了すること、
を含む、請求項３に記載の方法。
【請求項５】
ステップ（ｊ）が、
Fx=Tx + (Ox・Rt/Rm)(cos (θt - θm) )+(Oy・Rt/Rm)(sin (θt - θm) )
Fy=Ty + (Ox・Rt/Rm)(-sin (θt - θm) )+(Oy・Rt/Rm)(cos (θt - θm) )
によって、計算されることを特徴とする、
請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模画像データベースの高速検索手法に関する。
【０００２】
より詳しくは、大量の画像データベースの中から、検索したい対象物を高速に検索するための手法に関する。
【背景技術】
【０００３】
スマートフォンやタブレットの普及に伴い、デバイス付属のカメラを対象物にかざすだけで、対象物に関連する情報を即座に取り出し、ネットショッピングなどの行動につなげたいという要求が高まっている。
【０００４】
一例として、ポスターや吊り広告で関心のある書籍を見つけた場合、その広告媒体にデバイスをかざして、書籍の情報を検索し、ネットで購入するというようなケースが考えられる。
【０００５】
通常、画像データベースに蓄積されている辞書画像セットに含まれる物体と、デバイスで撮影した検索対象物体の画像とは、例えばそれが同じ書籍の表紙画像であったとしても、サイズや撮影角度や照明条件が異なり、単純な画像ビットマップ同士のマッチングでは実用的な検索精度が得られない。
【０００６】
このような、サイズ、撮影角度あるいは照明条件が異なっていても、高い識別率で物体同士の照合が可能な技術として、キーポイントと呼ばれる回転・拡大縮小に不変な局所画像特徴を使用した物体認識手法が知られている（非特許文献１）。
【０００７】
SIFTと呼ばれる非特許文献１の手法では、画像に複数の空間的スケールをもつガウスフィルタを作用させて、隣接するスケールのフィルタ出力画像の差分をとり、DoG (Difference of Gaussians )と呼ばれる画像セットを得る。
【０００８】
DoG画像の絶対値が空間方向およびスケール方向で共に極大になる座標をキーポイントとよび、濃淡パターンのある画像では、通常、複数のキーポイントが検出される。
【０００９】
キーポイントの周囲の画素の濃度勾配より、キーポイントの方向が求められ、DoGの極大となるスケールが、キーポイントのスケールとなる。
【００１０】
キーポイントの周囲の画素を16ブロックに分割してそのブロックに含まれる画素の濃淡ヒストグラムをとり、キーポイントの特徴量とする。
【００１１】
SIFTでは、特徴量は実数の要素をもつ128次元のベクトルとして表現される。
【００１２】
この方式は回転・拡大縮小に対してロバストな物体認識手法として評価が定まっている。
【００１３】
しかし、計算量が膨大であるため、大量の画像データベースに含まれるキーポイントと、検索対象画像に含まれるキーポイントとを総当り方式で照合する方法では、実用的な検索速度を得ることは困難である。
【００１４】
大量の画像データベースの検索時間を短縮する方法として、K-D treeが知られている（非特許文献２）。
【００１５】
図１は、 K-D tree（簡単のため、３次元のtree）を表示する図である。
【００１６】
このK-D treeと呼ばれる、多次元ツリー構造を持つインデックスを、辞書画像セットのキーポイント特徴量を使用して予め作成する。
【００１７】
そして、検索時には、多次元ツリーをたどることにより、検索対象画像のキーポイントと最も近しい特徴量を持つ辞書画像のキーポイントを探索することができる。
【００１８】
この手法は、検索に要する時間は、O(log N)とされている。
【００１９】
ここで、Nは、辞書画像セットのキーポイントの数である。
【００２０】
しかし、検索時間の短縮は可能となるものの、辞書画像のキーポイント特徴量を計算する時間は同じであり、さらに、K-D treeのインデックス作成の時間が必要となる。  
【００２１】
特許文献１には、２つの特徴ベクトルの距離の計算について開示するものの、ＳＩＦＴを用いるものであって、本願の発明として開示するところの、ＧＩＦＴ特徴量と呼ぶ特徴量についての記載はない。
【００２２】
特許文献２および６には、ＳＩＦＴに関する記載はあるものの、本願の発明全体に関わる開示はない。
【００２３】
特許文献３、４、５、７、８および９は、パターンマッチングに関し、本願の発明に関して部分的な開示があるものの、本願の発明全体に関わる開示はない。
【００２４】
特許文献３、５および９は、参考程度のものにすぎない。
【００２５】
特許文献１０は、非特許文献１の内容に対応した特許文献である。
【先行技術文献】
【特許文献】
【００２６】
【特許文献１】特開２０１３−１０１４２３  −  出願から１８ヶ月経過後の日本国における強制的な公開
【特許文献２】日本国特許第５２０６５１７号（特開２０１０−２１８０５１）
【特許文献３】日本国特許第４９４６８７８号（特開２００９−１６３６８２）
【特許文献４】日本国特許第４２８４２８８号（特開２００６−２５２１６２）
【特許文献５】日本国特許第３９１４８６４号（特開２００３−２４２５０９）
【特許文献６】特開２０１１−２４８８７９
【特許文献７】特開２００５−１２２３５１
【特許文献８】特開２０００−２１６９７９
【特許文献９】特開平９−２４５１６６
【特許文献１０】米国特許第６７１１２９３Ｂ１号
【非特許文献】
【００２７】
【非特許文献１】David G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” InternationalJournal of Computer Vision, Vol. 60, No. 2, pp. 91-110, 2004
【非特許文献２】Marius Muja and David G. Lowe, “Fast Approximate Nearest Neighbors with Automatic AlgorithmConfiguration,” VISAPP'09, No. 1, pp. 331-340, 2009
【非特許文献３】Ethan Rublee, et.al., “ORB: an efficient alternative to SIFT or SURF,” ICCV2011, pp.2564-2571, 2011
【発明の概要】
【発明が解決しようとする課題】
【００２８】
本発明の目的は、大量の画像データベースの中から、検索したい対象物を高速に検索するための手法を実現することであって、従来技術における問題点を克服すべく、GIFT特徴量＋機械学習を使用して実用的な検索所要時間を達成することにある。
【課題を解決するための手段】
【００２９】
本発明のGIFT（Gaussian distributed scale InvariantFeature Transform）特徴量（特徴ベクトル）を使用したパターンマッチングは、以下の手順で実行する。
【００３０】
(Ａ)  回転・スケール不変な特徴点の検出：  oFAST （既知の手法にあたる部分） 
【００３１】
(Ｂ)  特徴点の近傍の画素値を使用した特徴量（特徴ベクトル）：GIFT（本願の発明にあたる部分）
【００３２】
(Ｃ)  2つの特徴ベクトルの距離の計算手法：  GIFT（本願の発明にあたる部分）
【００３３】
(Ｄ)  特徴ベクトル空間におけるインデックス生成のための機械学習:  K-D tree（既知の手法にあたる部分） 
【発明の効果】
【００３４】
本発明に従えば、従来手法の欠点である、トレーニングに要する処理時間を低減させることができる。
【００３５】
すなわち、手順（Ａ）（Ｂ）（Ｃ）（Ｄ）の組み合わせが、処理時間を低減させることに技術的に貢献しているものである。
【００３６】
具体的には、＜  処理速度（高速化）の検証  ＞  の項において説明する。
【００３７】
＜  処理速度（高速化）の検証  ＞  の項では、従来の手法  との比較がされているので、その効果が明らかになる。
【００３８】
手順（Ｄ）を効率化させているという点において、いわば準備手順としての手順（Ｂ）（Ｃ）においても技術的な貢献がある。
【図面の簡単な説明】
【００３９】
【図１】図１は、 K-D tree（簡単のため、３次元のtree）を表示する図である。
【図２】図２は、キーポイントの検出例を示す図である。
【図３】図３は、ガウス状分布の候補座標からランダムに128の座標ペアを選択し、その輝度差の数列を128次元の特徴ベクトルとすることを示す模式図である。
【図４】図４は、辞書画像におけるキーポイントを示す図である。
【図５】図５は、 検索対象画像における一致キーポイントと、その仮想中心点とを示す図である。
【図６】図６は、検索対象画像 (1280x720画素)を示す図である。
【図７】図７は、SIFTアルゴリズムのトレーニングに要する処理時間を示す図である。
【図８】図８は、SIFTアルゴリズムの逐次検索に要する処理時間を示す図である。
【図９】図９は、SIFTを使用した辞書画像のトレーニングに要する処理時間（K-D tree作成を含む）を示す図である。
【図１０】図１０は、SIFTを使用した辞書画像の高速検索に要する処理時間を示す図である。
【図１１】図１１は、GIFTアルゴリズムのトレーニングに要する処理時間（K-D treeを含む）を示す図である。
【図１２】図１２は、GIFTアルゴリズムの高速検索に要する処理時間を示す図である。
【発明を実施するための形態】
【００４０】
本発明では、従来技術における問題点を克服して、実用的な検索所要時間を達成するために、GIFT (Gaussian distributed scale Invariant Feature Transform)と命名した処理手段を考案したものである。
【００４１】
GIFTは、以下に示す処理手順より構成される。
【００４２】
A: 辞書画像のGIFTキーポイント特徴量の計算およびK-D treeの生成
【００４３】
A-1. 辞書画像 １枚ごとに、回転・拡大縮小に不変な特徴点であるGIFT キーポイントを検出し、各キーポイントの特徴量を計算し、これを記憶する。
【００４４】
計算方法は後述する。
【００４５】
A-2. 手順A-1を、辞書画像の枚数分にわたって繰り返す。
【００４６】
A-3. すべてのキーポイント特徴量をもとに、K-D treeを生成し、記憶する。
【００４７】
高速化のために、n個のツリーを作成し、すべてのキーポイント特徴量をランダムにn個のグループに分割して、並列処理を行うことも可能である。
【００４８】
また、辞書画像を複数のクラスに予め分類し、クラスごとにK-D treeを生成することで、クラスを限定した検索を高速に実行することも可能である。
【００４９】
B: 検索対象画像のGIFTキーポイント特徴量の計算および、検索
【００５０】
B-1. 検索対象画像からGIFT キーポイントを検出し、キーポイント特徴量を計算し、記憶する。
【００５１】
GIFTでは、SIFTと同様に、特徴量は実数の要素をもつ128次元のベクトルとして表現される。これは、SIFTとの性能比較の意味合いもある。
【００５２】
B-2. すべてのキーポイントについて、その特徴量ベクトルとの距離が最も近い、辞書画像のキーポイントの特徴ベクトルを、K-D treeより探索し、距離を記録する。
【００５３】
B-3. 距離が、あるしきい値以下の検索対象画像のキーポイントのみを選択し、辞書画像ごとに分類し、記憶する。
【００５４】
この手順で選択されたキーポイントと、対応する辞書画像のキーポイントとを、キーポイントペアと呼ぶ。
【００５５】
B-4. ある１つの辞書画像について、選択されたキーポイントペアより、検索対象画像のキーポイント座標(Tx,Ty)を、後述する変換式に従って仮想中心座標 (Fx,Fy)に変換する。
【００５６】
対象となるすべてのキーポイント座標についてこの手順を実行する。
【００５７】
B-5. 仮想中心座標(Fx,Fy)を中心とした所定の半径（ｒ）内に含まれる、他の仮想中心点の数をカウントし、そのカウントを記憶する。
【００５８】
B-6. すべての仮想中心点について、手順B-5を実行し、最もカウント数の多い仮想中心(Mx,My)が、対応する辞書画像の画像中心と一致するであろうことを示す候補として記憶する。
【００５９】
B-7. カウントされた仮想中心点の数が所定の閾値（Ｎｃ）以上である場合に、検索対象画像の仮想中心座標(Mx,My)付近に辞書画像中に存在する認識対象が含まれていたものと判定する。
【００６０】
B-8. 手順B-4からB-7を辞書画像の数だけ繰り返す。
【００６１】
GIFTキーポイントの検出方法は、非特許文献３のoFASTと同様に、画像の濃淡パターンのコーナーをキーポイントとする方法であり、SIFTと比較して、高速なキーポイント検出方法として知られている。
【００６２】
GIFTキーポイントの検出方法は、SIFT同様、スケールと方向とを有する。
【００６３】
図２は、キーポイントの検出例を示す図である。
【００６４】
図２(a)は 元画像であって、図２(b)においては、円が検出されたキーポイントとして示されている。
【００６５】
GIFT特徴量は、キーポイントの周囲31x31画素からランダムに128ペアの画素を選択し、その輝度差を特徴量とする。
【００６６】
GIFT特徴量は、SIFT同様、特徴量は実数の要素をもつ128次元のベクトルとして表現される。
【００６７】
図３は、ガウス状分布の候補座標からランダムに128の座標ペアを選択し、その輝度差の数列を128次元の特徴ベクトルとすることを示す模式図である。
【００６８】
128ペアの画素の選択方法の１つの実装形態として、選択する画素の密度を、キーポイント座標を原点としたガウス分布状にとることにより、キーポイントの近傍の濃淡パターンが、特徴ベクトルに反映されやすくなる（図３）。
【００６９】
計算された輝度差が、正の実数および負の実数の両方を混合して含むことが特徴となっているため、K-D treeの生成・探索を効率化させることとの相性がよく、技術的な親和性がある。
【００７０】
C-1. 辞書画像ごとに、すべてのキーポイントの辞書画像中心からのオフセット (Ox,Oy)、スケール Rm および方向 θm [radian]を記憶する。
【００７１】
図４は、辞書画像におけるキーポイントを示す図である。
【００７２】
点の網掛けで示された円（○）がキーポイントである。
【００７３】
図５は、 検索対象画像における一致キーポイントと、その仮想中心点とを示す図である。
【００７４】
図５において、点の網掛けで示された円（○）のキーポイントとは別に、格子の網掛けで示された円（○）が仮想中心点である。
【００７５】
キーポイントのスケールは、物体のサイズに比例するものとする(図４)。
【００７６】
C-2.   同様に手順 B-3で選択された検索対象画像におけるすべてのキーポイントのスケール Rt と方向 θt [radian]とを記憶する。そのキーポイントの検索対象画像での座標(Tx,Ty)も記憶しておく。
【００７７】
C-3. 手順 C-2で記憶されたすべてのキーポイント座標(Tx,Ty)について、対応する仮想中心点の座標(Fx,Fy)を次のように定義し、計算する(図５)。
【００７８】
Fx=Tx + (Ox・Rt/Rm)(cos (θt - θm) )+(Oy ・Rt/Rm)(sin (θt - θm) )
【００７９】
Fy=Ty + (Ox ・Rt/Rm)(-sin (θt - θm) )+(Oy ・Rt/Rm)(cos (θt - θm) )
【００８０】
＜  処理速度（高速化）の検証  ＞
【００８１】
図６は、検索対象画像 (1280x720画素)を示す図である。
【００８２】
処理速度の測定に使用した辞書画像は、インターネット上のサイトから9900枚および、実際に撮影した風景画像(100枚)を使用した (合計10000 画像)。
【００８３】
検索対象画像は、辞書画像の一部を組み合わせて加工した、図６の画像である。
【００８４】
すべて発明者自身で実際に撮影した画像を使用した。
【００８５】
使用したサーバーは、Power750 (3.3GHz、1coreのみ使用)である。
【００８６】
使用したOSは Linux (Linus Torvaldsの商標) である。
【００８７】
4.1 SIFT逐次処理  （既知の手法  その１）
【００８８】
SIFT（逐次比較）による辞書画像のキーポイント特徴量を計算する時間（トレーニング時間）と検索所要時間を測定した。
【００８９】
図７は、SIFTアルゴリズムのトレーニングに要する処理時間を示す図である。
【００９０】
図８は、SIFTアルゴリズムの逐次検索に要する処理時間を示す図である。
【００９１】
いずれも、辞書画像の枚数に比例して処理時間が増大していることがわかる。
【００９２】
4.2 SIFT + K-D tree  （既知の手法  その２）
【００９３】
次に、SIFT特徴量を使用した、辞書画像のキーポイント特徴量計算およびK-D treeのインデックス作成（トレーニング）時間と検索時間を実測した。
【００９４】
図９は、SIFTを使用した辞書画像のトレーニングに要する処理時間（K-D tree作成を含む）を示す図である。
【００９５】
図１０は、SIFTを使用した辞書画像の高速検索に要する処理時間を示す図である。
【００９６】
検索に要する時間は、辞書画像の数によらずほぼ一定で、逐次処理と比較して顕著な速度向上が見られるが、トレーニング時間は依然として辞書画像に比例する。
【００９７】
4.3 GIFT とSIFTとの比較    （本発明の適用）
【００９８】
GIFT特徴量を使用した画像検索手法の処理速度を測定した。
【００９９】
SIFTアルゴリズムを使用した手法と比較して、辞書画像の枚数が 10,000枚の場合、
【０１００】
図１１は、GIFTアルゴリズムのトレーニングに要する処理時間（K-D treeを含む）を示す図である。
【０１０１】
ドットのラインが GIFTであり、実線のラインの SIFTと比較して、4.0倍高速になっていることが分かる。
【０１０２】
トレーニングで4.0倍   (SIFT:4256[sec] vs. GIFT:1072[sec]) の高速化が確認できている（図１１）。
【０１０３】
図１２は、GIFTアルゴリズムの高速検索に要する処理時間を示す図である。
【０１０４】
ドットのラインが GIFTであり、実線のラインの SIFTと比較して、2.6倍高速になっていることが分かる。
【０１０５】
検索で 2.6倍 (SIFT:3.8[sec] vs. GIFT:1.5[sec]) の高速化が確認できている（図１２）。
【０１０６】
ここまでに説明してきた本発明の技術的思想としての特徴は、コンピュータに実行させる手法（方法、システム、コンピュータプログラム）として実現することができる。
【０１０７】
全てのパラメータは、ハードウェア資源としてのコンピュータのメモリ等に、ソフトウェア資源としてのコンピュータプログラムに配列等の形式をもって体系的に記憶して保存しておくことができる。
【０１０８】
辞書画像データの提供、座標変換の計算、仮想中心点のカウント、カウントされた数の記憶、などはすべてコンピュータに実行させることができる。
【０１０９】
キーポイントを抽出すること、特徴量をベクトルとして表現して記憶しておくことは、コンピュータを利用する上では非常に効率的である。
【図１】
0006474210.tif 000002
【図２】
0006474210.tif 000003
【図３】
0006474210.tif 000004
【図４】
0006474210.tif 000005
【図５】
0006474210.tif 000006
【図６】
0006474210.tif 000007
【図７】
0006474210.tif 000008
【図８】
0006474210.tif 000009
【図９】
0006474210.tif 000010
【図１０】
0006474210.tif 000011
【図１１】
0006474210.tif 000012
【図１２】
0006474210.tif 000013