(57)【要約】【課題】画像識別用の特徴記述子生成のシステムおよび方法を提供する。【解決手段】入力画像が受け取られる（３００１）。入力画像に対して段階的なガウスぼかしが行われてガウシアンピラミッドが構築される（３００２）。ガウシアンピラミッドにおける任意の連続する２つのガウスぼかし画像の差分を計算することによって、ＤｏＧピラミッドが構築される（３００３）。キーポイントが選択される（３００４）。一次標本点が、ガウシアンピラミッド空間の各キーポイント位置に基づいて特定される（３００５）。各一次標本点におけるスケール依存の勾配が計算される（３００６）。これらの勾配は、一次標本点とそれに関連する二次標本点各々との間の画像強度の差に基づいて得られる。キーポイントの一次標本点のすべてからの勾配が連結されて特徴記述子としてのベクトルを形成する（３００７）。【選択図】図３
2010086540.tif 000002
【特許請求の範囲】
【請求項１】
画像識別のための特徴記述子ベクトルの生成方法であって、
前記方法が、入出力インタフェース、記憶媒体、１つまたは複数のプロセッサ、および各手段間の通信を提供するリンクを含むコンピュータシステムで実行され、
前記方法が、
前記入出力インタフェースにより、入力画像を受け取り、
構築手段により、入力パラメータに基づく各々が異なるぼかしスケールを有するガウスぼかしフィルタを前記受け取った入力画像に適用してガウスぼかし画像を生成することにより前記入力画像のガウシアンピラミッド空間を構築し、
検出手段により、前記構築したガウシアンピラミッド空間中でキーポイントを検出し、
特定手段により、前記検出したキーポイント各々に対して該キーポイントからの３次元相対位置で定義される一次標本点を前記ガウシアンピラミッド空間中で特定し、
計算手段により、前記特定した一次標本点近傍における画像変化を示すベクトルである一次画像勾配を前記一次標本点に対応して計算し、
生成手段により、前記計算した一次画像勾配を連結することにより前記入力画像に対する特徴記述子ベクトルを生成する、
ことを含む、特徴記述子ベクトルの生成方法。
【請求項２】
前記ガウシアンピラミッド空間中で前記キーポイントを検出することが、
連続した前記ガウスぼかし画像間での差分をとることにより、差分ガウス空間を構築し、
前記差分ガウス空間内の平面における局所極大点又は局所極小点を前記キーポイントとして設定する、
ことを含む請求項１に記載の方法。
【請求項３】
前記一次標本点各々に対応する二次標本点が、前記一次画像勾配を取得するために用いられ、
対応する一次標本点に対する前記二次標本点の位置が、前記一次標本点のスケールに基づいて定義される
請求項１に記載の方法。
【請求項４】
前記ガウスぼかし画像が一連のガウスぼかしフィルタを適用することにより生成される請求項１に記載の方法。
【請求項５】
前記キーポイント各々に対する前記一次標本点を特定する３次元ベクトルが予め定められている請求項１に記載の方法。
【請求項６】
前記入力パラメータがスケール因子および標本パラメータを含み、前記標本パラメータは一次標本パラメータおよび二次標本パラメータを含む請求項１に記載の方法。
【請求項７】
前記キーポイント各々の３次元ベクトルが、該キーポイントを原点とする副座標系内で定義される請求項６に記載の方法。
【請求項８】
前記一次標本パラメータが第１のパラメータｄｒおよび第２のパラメータｓｄｒを含み、
前記一次標本点の座標が、前記一次標本パラメータおよび前記キーポイントのスケール因子ｓから、
ｄ＝ｄｒ×ｓ
ｓｄ＝ｓｄｒ×ｓ
に従って決定されるｄ、ｓｄに基づいて決定される
請求項７に記載の方法。
【請求項９】
指標ｉが０から４まで変化して５つの一次標本点を示し、
第１の一次標本点が前記キーポイントに対応して座標（０，０，０）を有し、
第２の一次標本点が座標（ｄ，０，ｓｄ）を有し、
第３の一次標本点が座標（０，ｄ，ｓｄ）を有し、
第４の一次標本点が座標（-ｄ，０，ｓｄ）を有し、
第５の一次標本点が座標（０，-ｄ，ｓｄ）を有する
請求項８に記載の方法。
【請求項１０】
前記二次標本パラメータが第３のパラメータｒｒを含み、
前記第３のパラメータｒｒ、前記一次標本パラメータの前記第２のパラメータｓｄｒ、および対応する前記一次標本点の前記キーポイントの前記スケール因子ｓに基づき、前記二次標本点が
ｒ0＝ｒｒ×ｓ
ｒ＝ｒ0（１＋ｓｄｒ）
に従って決定し、
前記二次標本点は、半径ｒの円周上の等間隔点に位置する
請求項８に記載の方法。
【請求項１１】
前記一次画像勾配は、前記二次標本点各々における二次画像勾配を含み、
前記二次画像勾配は、前記一次標本点各々と該一次標本点に対応する前記二次標本点との間の画像変化を、
Ｉij＝ｍａｘ（Ｉ（Ｏi）−Ｉ（Ｏij）），０）
に従って示し、
ここで、指標ｉは前記一次標本点を示し、ｉ＝０・・・ｎ,ｎ＋１は前記一次標本点の番号であり、
ここで、指標ｊは二次標本点を示し、ｊ＝０・・・ｍ,ｍ＋１は前記二次標本点の番号であり、
Ｏiは前記一次標本点ｉを定義する前記３次元ベクトルであり、
Ｏijは前記二次標本点ｉ，ｊを定義する前記３次元ベクトルであり、
Ｉ（Ｏi）は前記一次標本点ｉにおける画像強度レベルを示し、
Ｉ（Ｏij）は前記二次標本点ｉｊにおける画像強度レベルを示し、
Ｉijは前記一次標本点ｉと、前記一次標本点ｉに対応する前記二次標本点ｉｊとの間の画像強度の変化に対応する、負でないスカラーを示し、
前記一次標本点ｉ各々における前記一次画像勾配は
Ｖij＝Ｉij／［ＳＱＲＴ（Σ（Ｉij）2）］
ここで、ｊ＝０，…，ｍ
Ｖi＝［Ｖi0（Ｏi−Ｏi0）／｜（Ｏi−Ｏi0）｜，・・・，Ｖim（Ｏi−Ｏim）／｜（Ｏi−Ｏim）｜］
により得られ、
Ｖijは前記二次標本点ｉｊにおける前記二次画像勾配成分の大きさを示すスカラーを与え、
Ｖiは前記一次標本点ｉにおける前記一次画像勾配ベクトルを与え、各Ｖiはｊの総数に等しい次元を有し、
前記キーポイント各々における前記特徴記述子ベクトルは、
Ｖ＝［Ｖ0，…  Ｖi  …，Ｖn］
に従って前記一次画像勾配の連結から得られ、
ｎは前記キーポイントに対して特定される前記一次標本点の数である
請求項１に記載の方法。
【請求項１２】
画像識別のための特徴記述子ベクトル生成用のコンピュータシステムであって、
入力画像を受け取り、特徴記述子ベクトルを出力する入出力インタフェースと、
入力パラメータに基づく各々異なるぼかしスケールを有するガウスぼかしフィルタを前記受け取った入力画像に適用してガウスぼかし画像を生成することにより前記入力画像のガウシアンピラミッド空間を構築する構築手段と、
前記構築されたガウシアンピラミッド空間中でキーポイントを検出する検出手段と、
前記検出されたキーポイントからの３次元の相対位置で定義される一次標本点を、前記キーポイント各々に対して前記ガウシアンピラミッド空間中で特定する特定手段と、
前記特定された一次標本点近傍における画像変化を示すベクトルである一次画像勾配を前記一次標本点に対応して計算する計算手段と、
前記計算された一次画像勾配を連結することによって前記入力画像に対する前記特徴記述子ベクトルを生成する生成手段と、
を備える、コンピュータシステム。
【請求項１３】
前記ガウシアンピラミッド空間中で前記キーポイントを検出することが、
連続した前記ガウスぼかし画像の間の差分をとることにより、差分ガウス空間を構築し、
前記差分ガウス空間内の平面における局所極大点又は局所極小点を前記キーポイントとして設定する、
ことを含む請求項１２に記載のシステム。
【請求項１４】
前記一次標本点各々に対応する二次標本点が、前記一次画像勾配の取得に用いられ、
対応する一次標本点に関する前記二次標本点の位置が、前記一次標本点の前記スケールに基づいている
請求項１２に記載のシステム。
【請求項１５】
前記ガウスぼかし画像が一連のガウスぼかしフィルタを適用することにより生成される請求項１２に記載の方法。
【請求項１６】
前記キーポイント各々に対する前記一次標本点を特定する３次元ベクトルが予め定められている請求項１２に記載のシステム。
【請求項１７】
前記入力パラメータがスケール因子ｓiおよび標本パラメータｄｒ、ｓｄｒ、ｒｒを含み、
指標ｉが前記一次標本点各々を決定し、
前記標本パラメータが一次標本パラメータおよび二次標本パラメータを含む
請求項１２に記載のシステム。
【請求項１８】
前記キーポイント各々の３次元ベクトルが、該キーポイントを原点（０，０，０）とする副座標系内で定義される請求項１７に記載のシステム。
【請求項１９】
前記一次標本パラメータが第１のパラメータｄｒおよび第２のパラメータｓｄｒを含み、
前記一次標本点の座標が、前記一次標本パラメータおよび前記スケール因子ｓから、
ｄ＝ｄｒ×ｓ
ｓｄ＝ｓｄｒ×ｓ
に従って決定されるｄ、ｓｄに基づいて決定される請求項１８に記載のシステム。
【請求項２０】
指標ｉが０から４まで変化して５つの一次標本点を示し、
第１の一次標本点が前記キーポイントに対応する座標（０，０，０）を有し、
第２の一次標本点が座標（ｄ，０，ｓｄ）を有し、
第３の一次標本点が座標（０，ｄ，ｓｄ）を有し、
第４の一次標本点が座標（-ｄ，０，ｓｄ）を有し、
第５の一次標本点が座標（０，-ｄ，ｓｄ）を有する
請求項１９に記載の方法。
【請求項２１】
前記二次標本パラメータが第３のパラメータｒｒを含み、
前記第３のパラメータｒｒ、前記一次標本パラメータの前記第２のパラメータｓｄｒ、および対応する前記一次標本点の前記スケールｓiに基づき、前記二次標本点が
ｒ0＝ｒｒ×ｓ
ｒ＝ｒ0（１＋ｓｄｒ）
により決定し、
前記二次標本点は、半径ｒの円周上の等間隔点に位置する
請求項１９に記載のシステム。
【請求項２２】
前記一次画像勾配は、前記二次標本点各々における二次画像勾配を含み、
前記二次画像勾配は、前記一次標本点各々と前記一次標本点に対応する前記二次標本点との間の画像変化を、
Ｉij＝ｍａｘ（Ｉ（Ｏi）−Ｉ（Ｏij）），  ０）
に従って示し、
ここで、指標ｉは前記一次標本点を示し、ｉ＝０・・・ｎ,ｎ＋１は前記一次標本点の番号であり、
ここで、指標ｊは前記二次標本点を示し、ｊ＝０・・・ｍ,ｍ＋１は前記二次標本点の番号であり、
Ｏiは前記一次標本点ｉを定義する３次元ベクトルであり、
Ｏijは前記二次標本点ｉｊを定義する前記３次元ベクトルであり、
Ｉ（Ｏi）は前記一次標本点ｉにおける画像強度レベルを示し、
Ｉ（Ｏij）は前記二次標本点ｉｊにおける画像強度レベルを示し、
Ｉij  は前記一次標本点ｉと、前記一次標本点ｉに対応する前記二次標本点ｉｊとの間の画像強度の変化に対応する、負でないスカラーを示し、
前記一次標本点ｉ各々における前記一次画像勾配は
Ｖij＝Ｉij／［ＳＱＲＴ（Σ（Ｉij）2）］
ここで、ｊ＝０，…，ｍ
Ｖi＝［Ｖi0（Ｏi−Ｏi0）／｜（Ｏi−Ｏi0）｜，・・・，Ｖim（Ｏi−Ｏim）／｜（Ｏi−Ｏim）｜］
により得られ、
Ｖijは前記二次標本点ｉｊにおける前記二次画像勾配成分の大きさを示すスカラーを与え、
Ｖiは前記一次標本点ｉにおける前記一次画像勾配ベクトルを与え、各Ｖiはｊの総数に等しい次元を有し、
前記キーポイント各々における前記特徴記述子ベクトルは、
Ｖ＝［Ｖ0，…  Ｖi  …，Ｖn］
に従って前記一次画像勾配の連結から得られ、
ｎは前記キーポイントに対して特定される前記一次標本点の数である
請求項１２に記載のシステム。
【請求項２３】
コンピュータに、
前記入出力インタフェースにより入力画像を受け取り、
入力パラメータに基づく各々異なるぼかしスケールを有するガウスぼかしフィルタを前記入力画像に適用してガウスぼかし画像を生成することにより前記受け取った入力画像のガウシアンピラミッド空間を構築し、
前記構築したガウシアンピラミッド空間中でキーポイントを検出し、
前記検出したキーポイントからの３次元相対位置で定義される一次標本点を、前記キーポイント各々に対して前記ガウシアンピラミッド空間中で特定し、
前記特定した一次標本点近傍における画像変化を示すベクトルである一次画像勾配を前記一次標本点に対応して計算し、
前記計算した一次画像勾配を連結することにより前記入力画像に対する特徴記述子ベクトルを生成する、
画像識別のための特徴記述子ベクトル生成処理を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にコンピュータビジョンの分野に関し、特徴記述子ベクトル生成方法、システムおよびプログラムに係る。特には、スケール・回転、画像位置や照明といった環境因子に対して不変（invariant）であるように記述される特徴記述子ベクトルを利用した画像中の局所特徴の検出および記述子に関する。
【背景技術】
【０００２】
同一対象物の複数の画像間における点対応の検出は、画像検索、物体認識、シーン同定、および３Ｄ形状評価において重要である。画像検索、物体認識その他の目的のための画像中の注目点をキーポイントと呼ぶ。このキーポイントは、画像のスケールや回転に対して不変であり、かなりの範囲のひずみ、３次元上の視点の変化、照明のノイズや変化があってもしっかりと対応が取れるように、選択されかつ処理されなければならない。さらに、画像検索や物体認識などのタスクに好適であるためには、多数の画像からなる大量の特徴データベースの中から１つの特徴を高い確率で正確に一致検索できるという意味で、このキーポイントが高い弁別性を有する必要がある。
【０００３】
この注目点、すなわちキーポイントが検出され、場所が特定されると、さまざまな記述子を用いて表現される。それから、キーポイントに対応し、記述子で表された個別の特徴が、既知のオブジェクトの特徴データベースと照合される。従って、対応検索システムは３つのモジュールに分離できる。すなわち、注目点検出モジュール、画像点記述子モジュール、および対応特定モジュールである。これらの３つのモジュールの中で、記述子の構造の複雑さおよび次元が、システム全体としての性能に直接的かつ重大な影響をもっている（例えば、ＳＩＦＴ記述子を構成するのに、特徴抽出時間全体の約３／４がかかる）。以下の議論では、キーポイント近傍の記述子ベクトルの構築方法を中心に述べる。
【０００４】
これまでに文献でいくつかの画像点記述子が提案されてきた。ＳＩＦＴ（Ｓｃａｌｅ−ｉｎｖａｒｉａｎｔ  ｆｅａｔｕｒｅ  ｔｒａｎｓｆｏｒｍ）は、コンピュータビジョンにおいて、画像中の局所特徴の検知および記述に利用されるアルゴリズムの１つである。ＳＵＲＦ（Ｓｐｅｅｄｅｄ−ｕｐ  ｒｏｂｕｓｔ  ｆｅａｔｕｒｅｓ）が、画像中の局所特徴を検出し記述するもう１つのアルゴリズムである。ＳＩＦＴおよびＳＵＲＦは物体認識および３次元構造の復元に適用される。文献では、これらの画像点記述子の比較および評価も行われている。それらの比較によれば、ＳＩＦＴとＳＵＲＦは同じような弁別性を与えるが、ＳＵＲＦはスピードが早く、ＳＩＦＴは広い基線画像マッチングの割には有害なアーチファクト（偽信号）が少ない。ＳＩＦＴの場合には記述子の弁別性は、記述子の固有値の和で計測される。和が、異なる識別子で捕捉された分散量に対応し、従って弁別性に対応する。
【０００５】
図１はＳＩＦＴ記述子の構築方法のフローチャートである。
【０００６】
このフローチャートがＳＩＦＴ特徴計算の要約を示している。手法がステップ１０００で始まる。ステップ１００１で入力画像が受け取られる。
【０００７】
ステップ１００２で、入力画像に対して段階的なガウスぼかしが行われて（Ｇａｕｓｓｉａｎ−ｂｌｕｒｒｅｄ）ガウシアンピラミッド（Ｇａｕｓｓｉａｎ  ｐｙｒａｍｉｄ）が構築される。ガウスぼかしは通常、原画像Ｉ（ｘ，ｙ）をスケールｋiσのガウスぼかし関数Ｇ（ｘ，ｙ，ｋi，σ）で畳み込んだものを含み、ガウスぼかし関数Ｌ（ｘ，ｙ，ｋiσ）はＬ（ｘ，ｙ，ｋiσ）＝Ｇ（ｘ，ｙ，ｋiσ）＊Ｉ（ｘ，ｙ）で定義される。ここでｋiσは、画像のぼかしに利用されるガウス関数の標準偏差を表す。ｋiが変化すれば標準偏差ｋiσが変化し、段階的なぼかしが得られる。第１のぼかし関数の標準偏差をσで表し、ｋiが標準偏差を変える倍数である。原画像Ｉをガウス関数Ｇで漸進的に畳み込んでぼかし像を得る場合、ぼかし画像Ｌはスケール空間において一定ファクタｋiだけ分離している。
【０００８】
ステップ１００３において、ガウシアンピラミッドにおける任意の連続する２つのガウスぼかし画像の差分を計算することによって、ガウス関数の差分（ＤｏＧ（Ｄｉｆｆｅｒｅｎｃｅ  ｏｆ  Ｇａｕｓｓｉａｎ））ピラミッドが構築される。こうして、ＤｏＧ空間においてＤ（ｘ，ｙ，σ）＝Ｌ（ｘ，ｙ，ｋi σ）−Ｌ（ｘ，ｙ，（ｋi −１）σ）が得られる。ＤｏＧ画像Ｄ（ｘ，  ｙ，  σ）  は、スケール  ｋiσ  と（ｋi −１）σにおけるガウスぼかし画像の差分である。Ｄ（ｘ，ｙ，σ）のスケールはｋiσと（ｋi −１）σの間のどこかにあり、ガウスぼかし画像の数が増加し、ガウシアンピラミッドに与えられる近似が連続空間に近づくにつれ、２つのスケールは１つの値に近づく。畳み込まれた画像Ｌはオクターブでグループ分けされる。ここでオクターブは標準偏差σの値を２倍にすることに相当する。さらに、倍数ｋiの値はオクターブごとに一定数の畳み込み画像が得られるように選択される。そうして、オクターブごとに隣接するガウスぼかし画像からＤｏＧ画像Ｄが得られる。１つのオクターブが終わる度、ガウス画像が１／２にダウンサンプリングされて、上記のプロセスが反復される。
【０００９】
ステップ１００４において、ＤｏＧ空間における極大および極小が見つかり、これらの極大、極小の位置がＤｏＧ空間におけるキーポイント位置として利用される。極大および極小を見つけるために、ＤｏＧ画像Ｄの中の各ピクセルと、同一スケールの８つの隣接ピクセル、および上下両面の隣接スケール各々の中の９つの隣接ピクセルの計２６ピクセル（９×２＋８＝２６）との比較を行う。そのピクセルの値が比較した全部で２６のピクセルの中で最大もしくは最小である場合に、キーポイントとして選択される。この後、キーポイントはさらに処理されて、より正確に位置が特定され、コントラストの低いキーポイントやエッジにあるキーポイントは切り捨てられる。
【００１０】
ステップ１００５において、局所画像勾配の方向に基づいて、キーポイントに１つまたは複数の配向すなわち方向が割り当てられる。局所画像の特性に基づいて各キーポイントに一貫した配向を割り当てることにより、キーポイント記述子をこの配向に対して相対的に表現することができ、従って画像回転に対する不変性を実現できる。ガウスぼかし画像Ｌ中でキーポイントスケールにある、キーポイントの周りの近傍領域におけるすべてのピクセルに対して大きさおよび方向の計算がおこなわれる。位置（ｘ，ｙ）にあるキーポイントに対する勾配の大きさはｍ（ｘ，ｙ）で表され、位置（ｘ，ｙ）にあるキーポイントに対する勾配の配向はＴｈｅｔａ（ｘ，ｙ）で表される。キーポイントのスケールは、このキーポイントのスケールに最も近いスケールを有するガウスぼかし画像Ｌを選択するのに用いられ、その結果すべての計算がスケール不変で行うことができる。このスケールにおける各画像標本Ｌ（ｘ，ｙ）に対して、勾配の大きさｍ（ｘ，ｙ）と配向Ｔｈｅｔａ（ｘ，ｙ）が、ｍ（ｘ，ｙ）＝  ＳＱＲＴ［（Ｌ（ｘ＋１，ｙ）−Ｌ（ｘ−１，ｙ））2＋Ｌ（ｘ，ｙ＋１）−Ｌ（ｘ，ｙ−１））2］に従って、ピクセルの差分を用いて計算される。配向Ｔｈｅｔａ（ｘ，ｙ）はＴｈｅｔａ（ｘ，ｙ）＝ａｒｃｔａｎ［（Ｌ（ｘ，ｙ＋１）−Ｌ（ｘ，ｙ−１））／（Ｌ（ｘ＋１，ｙ）−Ｌ（ｘ−１，ｙ））］として計算される。ここで、Ｌ（ｘ，ｙ）は、キーポイントのスケールでもあるスケールσにおけるガウスぼかし画像Ｌ（ｘ，ｙ，σ）の１標本である。  
【００１１】
実際には、ＤｏＧ空間のキーポイントの面よりも高いスケールの、ガウシアンピラミッド中で上にある面、あるいはキーポイントの面よりも低いスケールの、ガウシアンピラミッド中で下にある面のいずれかに対して勾配は一貫して計算される。いずれの場合でも、キーポイント各々に対して、キーポイントを取り巻く矩形領域において１つの同一スケールで勾配が計算される。さらに、画像信号の周波数が、ガウスぼかし画像のスケールに反映される。しかも、ＳＩＦＴは矩形領域のすべてのピクセルの勾配の値を単純に使用する。矩形ブロックはキーポイントを囲んで画定され、サブブロックがブロックの内部に画定される。標本はサブブロックの中に画定され、この構造はキーポイントのスケールが異なる場合でもすべてのキーポイントに対して同様である。従って、同一オクターブ内でガウシアン平滑化フィルタを連続的に使用して、画像信号の周波数が変わったとしても、異なるスケールにおいて特定されるキーポイントとして、画像信号周波数の変化とは関係なしに、スケールで表わされる数と同一の数の標本がサンプリングされる。
【００１２】
ステップ１００６において、ガウス関数で重み付けされた勾配の分布が各ブロックに対して計算される。ここで、各ブロックは２サブブロック×２サブブロックの計４サブブロックである（実際には所望の弁別性を実現するためには、ＳＩＦＴでは４サブブロック×４サブブロックの計１６サブブロックを必要とする）。ガウス関数で重み付けされた勾配の分布を計算するために、キーポイントの周りの領域の一部を含むいくつかの階級（ｂｉｎ）で配向ヒストグラムを作成する。配向ヒストグラムは、３６０度の配向範囲の１０度ずつを含む３６階級に分けている。あるいはまた、ヒストグラムは、３６０度の配向範囲を４５度ずつの８つの階級に分けてもよい。
【００１３】
ヒストグラムに加えられた標本各々は、キーポイントのスケールの１．５倍の標準偏差を持つガウシアン荷重円ウィンドウ内の勾配の大きさで重み付けされる。配向ヒストグラムのピークは局所勾配の主方向に対応する。ヒストグラムの最高ピークが検出される。そして、たとえば最高ピークの８０％というようなあるパーセンテージ内にある他の任意の局所ピークも、その配向を有するキーポイントを生成するのに用いられる。従って、同じような大きさの複数のピークを有する場所に対しては、同一場所、同一スケールで、ただし配向の異なる複数のキーポイントが生成され得る。
【００１４】
ステップ１００７において、サブブロックからのヒストグラムを連結して、このキーポイントに対する特徴記述子ベクトルが得られる。１６サブブロックからの８階級ヒストグラムの中の勾配が用いられる場合には、１２８次元の特徴記述子ベクトルが生じる。ステップ１００８でこの方法が終了する。
【００１５】
一例では、特徴記述子は、キーポイント近傍の（４×４）ブロックの配向ヒストグラムのセットとして計算される。各ヒストグラムは８つの階級があり、各記述子がキーポイントの周りに８階級ヒストグラムの４×４＝１６のアレイを含む。このことは、ＳＩＦＴ特徴ベクトルが（４×４）×８＝１２８の要素を持つことになる。このベクトルは照明の変化に対する不変性を強化するために正規化される。
【００１６】
ＳＩＦＴにおいては、この記述子の次元、すなわち１２８は高い。しかしながら、より低い次元の記述子ではマッチング作業の範囲にわたって同じようには機能しなかった。記述子が長ければよりよい性能が続くが、それもそれほど顕著なものではない。しかも変形や遮蔽への感度が過敏となるという別の危険がある。
【００１７】
図２はＳＩＦＴ記述子の構築を概略的に表示したものである。
【００１８】
図１のフローチャートのステップが図２に概略的に示されている。例えば、ガウシアンピラミッドを構築するための画像のぼかしのステップ（１００２）および差分をとるステップ（１００３）が上の左隅に示されている。そして、上右隅の極大、極小を位置づけることによりキーポイントを計算するステップ（１００４）へ進む。勾配ベクトルの計算（１００５）が下左隅に示される。ヒストグラムでの勾配分布の計算（１００６）が下右隅に示される。最後に、ヒストグラムの連結（１００７）である特徴記述子ベクトルも下右隅に示されている。
【００１９】
図２においては、キーポイント２００が、キーポイント２００を囲む矩形ブロック２０２の中心に位置している。
【００２０】
下左（１００５）に、ピラミッドの各レベルに対して事前に計算された勾配が各標本領域２０６に小さい矢印で示されている。図に示すように、４×４の標本領域２０６がサブブロック２０４を形成し、２×２のサブブロック領域がブロック２０２を形成する。ブロック２０２は記述子ウィンドウとも呼ばれる。ガウシアン重み付け関数が円２２０で示され、各標本点２０６の大きさに重み付けを割り当てるのに用いられる。円形ウィンドウ２２０の荷重は滑らかに減少する。ガウシアンウィンドウ２２０の目的は、ウィンドウの位置のわずかな変化によって記述子に急激な変化が起きることを防ぐことであり、また記述子の中心から遠いところの勾配の影響を軽減することである。配向ヒストグラムの２×２＝４の配列が２×２のサブブロックから得られ、各ヒストグラムの階級が８つの配向を有するので、特徴記述子ベクトルは（２×２）×８＝３２次元となる。しかし、別の検討結果から、各々が８つの方向を持つヒストグラム（８階級ヒストグラム）の４×４の配列、すなわち（４×４）×８＝１２８次元の特徴記述子ベクトルを各々のキーポイントに用いることにより、より良い結果が得られることがわかっている。
【００２１】
特徴記述子ベクトルは、照明などの他の変数に対する不変性を実現するために、この後さらに修正されてもよい。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】米国特許第６,７１１,２９３号明細書
【非特許文献】
【００２３】
【非特許文献１】ベルナ・エロル（Ｂｅｒｎａ  Ｅｒｏｌ）、エミリオ・アンツネッツ（Ｅｍｉｌｉｏ  Ａｎｔｕｎｅｚ）、ジョナサン・ジェイ・ハル（Ｊｏｎａｔｈａｎ  Ｊ．Ｈｕｌｌ）、「ホットペーパ：携帯電話を用いたマルチメディアと紙との相互作用」（ＨＯＴＰＡＰＥＲ：ｍｕｌｔｉｍｅｄｉａ  ｉｎｔｅｒａｃｔｉｏｎ  ｗｉｔｈ  ｐａｐｅｒ  ｕｓｉｎｇ  ｍｏｂｉｌｅ  ｐｈｏｎｅｓ）、カナダ、第１６回マルチメディアに関するＡＣＭ国際学会議事録、２００８年１０月２６−３１日、ｐ３９９−４０８
【発明の概要】
【発明が解決しようとする課題】
【００２４】
本発明の方法は、特徴記述子を生成するための従来の技術に関連する、上記およびその他の問題の１つまたは複数を実質的に防ぐ方法およびシステムを対象とする。
【課題を解決するための手段】
【００２５】
本発明の第１の態様によれば、画像識別のための特徴記述子ベクトルの生成方法であって、前記方法が、入出力インタフェース、記憶媒体、１つまたは複数のプロセッサ、および各手段間の通信を提供するリンクを含むコンピュータシステムで実行され、前記方法が、前記入出力インタフェースにより、入力画像を受け取り、構築手段により、入力パラメータに基づく各々が異なるぼかしスケールを有するガウスぼかしフィルタを前記受け取った入力画像に適用してガウスぼかし画像を生成することにより前記入力画像のガウシアンピラミッド空間を構築し、検出手段により、前記構築したガウシアンピラミッド空間中でキーポイントを検出し、特定手段により、前記検出したキーポイント各々に対して該キーポイントからの３次元相対位置で定義される一次標本点を前記ガウシアンピラミッド空間中で特定し、計算手段により、前記特定した一次標本点近傍における画像変化を示すベクトルである一次画像勾配を前記一次標本点に対応して計算し、  生成手段により、前記計算した一次画像勾配を連結することにより前記入力画像に対する特徴記述子ベクトルを生成する、ことを含む、特徴記述子ベクトルの生成方法が提供される。
【００２６】
本発明の第２の態様によれば、第１の態様において、前記ガウシアンピラミッド空間中で前記キーポイントを検出することが、連続した前記ガウスぼかし画像間での差分をとることにより、差分ガウス空間を構築し、前記差分ガウス空間内の平面における局所極大点又は局所極小点を前記キーポイントとして設定する、ことを含んでもよい。
【００２７】
本発明の第３の態様によれば、第１の態様において、前記一次標本点各々に対応する二次標本点が、前記一次画像勾配を取得するために用いられてもよく、対応する一次標本点に対する前記二次標本点の位置が、前記一次標本点のスケールに基づいて定義されてもよい。
【００２８】
本発明の第４の態様によれば、第１の態様において、前記ガウスぼかし画像が一連のガウスぼかしフィルタを適用することにより生成されてもよい。
【００２９】
本発明の第５の態様によれば、第１の態様において、前記キーポイント各々に対する前記一次標本点を特定する３次元ベクトルが予め定められていてもよい。
【００３０】
本発明の第６の態様によれば、第１の態様において、前記入力パラメータがスケール因子および標本パラメータを含み、前記標本パラメータは一次標本パラメータおよび二次標本パラメータを含んでもよい。
【００３１】
本発明の第７の態様によれば、第６の態様において、前記キーポイント各々の３次元ベクトルが、該キーポイントを原点とする副座標系内で定義されてもよい。
【００３２】
本発明の第８の態様によれば、第７の態様において、前記一次標本パラメータが第１のパラメータｄｒおよび第２のパラメータｓｄｒを含み、前記一次標本点の座標が、前記一次標本パラメータおよび前記キーポイントのスケール因子ｓから、
ｄ＝ｄｒ×ｓ
ｓｄ＝ｓｄｒ×ｓ
に従って決定されるｄ、ｓｄに基づいて決定されてもよい。
【００３３】
本発明の第９の態様によれば、第８の態様において、指標ｉが０から４まで変化して５つの一次標本点を示し、第１の一次標本点が前記キーポイントに対応して座標（０，０，０）を有し、第２の一次標本点が座標（ｄ，０，ｓｄ）を有し、第３の一次標本点が座標（０，ｄ，ｓｄ）を有し、第４の一次標本点が座標（-ｄ，０，ｓｄ）を有し、  第５の一次標本点が座標（０，-ｄ，ｓｄ）を有してもよい。
【００３４】
本発明の第１０の態様によれば、第８の態様において、前記二次標本パラメータが第３のパラメータｒｒを含み、 前記第３のパラメータｒｒ、前記一次標本パラメータの前記第２のパラメータｓｄｒ、および対応する前記一次標本点の前記キーポイントの前記スケール因子ｓに基づき、前記二次標本点が
ｒ0＝ｒｒ×ｓ
ｒ＝ｒ0（１＋ｓｄｒ）
に従って決定し、前記二次標本点は、半径ｒの円周上の等間隔点に位置してもよい。
【００３５】
本発明の第１１の態様によれば、第１の態様において、前記一次画像勾配は、前記二次標本点各々における二次画像勾配を含んでもよく、前記二次画像勾配は、前記一次標本点各々と該一次標本点に対応する前記二次標本点との間の画像変化を、
Ｉij＝ｍａｘ（Ｉ（Ｏi）−Ｉ（Ｏij）），０）
に従って示してもよく、ここで、指標ｉは前記一次標本点を示し、ｉ＝０・・・ｎ,ｎ＋１は前記一次標本点の番号であり、ここで、指標ｊは二次標本点を示し、ｊ＝０・・・ｍ,ｍ＋１は前記二次標本点の番号であり、Ｏiは前記一次標本点ｉを定義する前記３次元ベクトルであり、Ｏijは前記二次標本点ｉ，ｊを定義する前記３次元ベクトルであり、Ｉ（Ｏi）は前記一次標本点ｉにおける画像強度レベルを示し、Ｉ（Ｏij）は前記二次標本点ｉｊにおける画像強度レベルを示し、Ｉijは前記一次標本点ｉと、前記一次標本点ｉに対応する前記二次標本点ｉｊとの間の画像強度の変化に対応する、負でないスカラーを示し、前記一次標本点ｉ各々における前記一次画像勾配は
Ｖij＝Ｉij／［ＳＱＲＴ（Σ（Ｉij）2）］
ここで、ｊ＝０，…，ｍ
Ｖi＝［Ｖi0（Ｏi−Ｏi0）／｜（Ｏi−Ｏi0）｜，・・・，Ｖim（Ｏi−Ｏim）／｜（Ｏi−Ｏim）｜］
により得られてもよく、Ｖijは前記二次標本点ｉｊにおける前記二次画像勾配成分の大きさを示すスカラーを与え、Ｖiは前記一次標本点ｉにおける前記一次画像勾配ベクトルを与え、各Ｖiはｊの総数に等しい次元を有し、前記キーポイント各々における前記特徴記述子ベクトルは、
Ｖ＝［Ｖ0，…  Ｖi  …，Ｖn］
に従って前記一次画像勾配の連結から得られてもよく、ｎは前記キーポイントに対して特定される前記一次標本点の数である。
【００３６】
また、第１の態様において、前記入出力インタフェースにより前記入力パラメータを受け取ることを更に含んでもよい。
【００３７】
本発明の第１２の態様によれば、画像識別のための特徴記述子ベクトル生成用のコンピュータシステムであって、入力画像を受け取り、特徴記述子ベクトルを出力する入出力インタフェースと、入力パラメータに基づく各々異なるぼかしスケールを有するガウスぼかしフィルタを前記受け取った入力画像に適用してガウスぼかし画像を生成することにより前記入力画像のガウシアンピラミッド空間を構築する構築手段と、前記構築されたガウシアンピラミッド空間中でキーポイントを検出する検出手段と、前記検出されたキーポイントからの３次元の相対位置で定義される一次標本点を、前記キーポイント各々に対して前記ガウシアンピラミッド空間中で特定する特定手段と、前記特定された一次標本点近傍における画像変化を示すベクトルである一次画像勾配を前記一次標本点に対応して計算する計算手段と、前記計算された一次画像勾配を連結することによって前記入力画像に対する前記特徴記述子ベクトルを生成する生成手段と、を備える、コンピュータシステムが提供される。
【００３８】
本発明の第１３の態様によれば、第１３の態様において、前記ガウシアンピラミッド空間中で前記キーポイントを検出することが、連続した前記ガウスぼかし画像の間の差分をとることにより、差分ガウス空間を構築し、前記差分ガウス空間内の平面における局所極大点又は局所極小点を前記キーポイントとして設定する、ことを含んでもよい。
【００３９】
本発明の第１４の態様によれば、第１２の態様において、前記一次標本点各々に対応する二次標本点が、前記一次画像勾配の取得に用いられ、対応する一次標本点に関する前記二次標本点の位置が、前記一次標本点の前記スケールに基づいていてもよい。
【００４０】
本発明の第１５の態様によれば、第１２の態様において、前記ガウスぼかし画像が一連のガウスぼかしフィルタを適用することにより生成されてもよい。
【００４１】
本発明の第１６の態様によれば、第１２の態様において、前記キーポイント各々に対する前記一次標本点を特定する３次元ベクトルが予め定められていてもよい。
【００４２】
本発明の第１７の態様によれば、第１２の態様において、前記入力パラメータがスケール因子ｓiおよび標本パラメータｄｒ、ｓｄｒ、ｒｒを含み、 指標ｉが前記一次標本点各々を決定し、前記標本パラメータが一次標本パラメータおよび二次標本パラメータを含んでもよい。
【００４３】
本発明の第１８の態様によれば、第１７の態様において、前記キーポイント各々の３次元ベクトルが、該キーポイントを原点（０，０，０）とする副座標系内で定義されてもよい。
【００４４】
本発明の第１９の態様によれば、第１８の態様において、前記一次標本パラメータが第１のパラメータｄｒおよび第２のパラメータｓｄｒを含み、前記一次標本点の座標が、前記一次標本パラメータおよび前記スケール因子ｓから、
ｄ＝ｄｒ×ｓ
ｓｄ＝ｓｄｒ×ｓ
に従って決定されるｄ、ｓｄに基づいて決定されてもよい。
【００４５】
本発明の第２０の態様によれば、第１９の態様において、指標ｉが０から４まで変化して５つの一次標本点を示し、第１の一次標本点が前記キーポイントに対応する座標（０，０，０）を有し、第２の一次標本点が座標（ｄ，０，ｓｄ）を有し、第３の一次標本点が座標（０，ｄ，ｓｄ）を有し、第４の一次標本点が座標（-ｄ，０，ｓｄ）を有し、第５の一次標本点が座標（０，-ｄ，ｓｄ）を有してもよい。
【００４６】
本発明の第２１の態様によれば、第１９の態様において、前記二次標本パラメータが第３のパラメータｒｒを含み、前記第３のパラメータｒｒ、前記一次標本パラメータの前記第２のパラメータｓｄｒ、および対応する前記一次標本点の前記スケールｓiに基づき、前記二次標本点が
ｒ0＝ｒｒ×ｓ
ｒ＝ｒ0（１＋ｓｄｒ）
により決定し、前記二次標本点は、半径ｒの円周上の等間隔点に位置してもよい。
【００４７】
本発明の第２２の態様によれば、第１２の態様において、前記一次画像勾配は、前記二次標本点各々における二次画像勾配を含み、前記二次画像勾配は、前記一次標本点各々と前記一次標本点に対応する前記二次標本点との間の画像変化を、
Ｉij＝ｍａｘ（Ｉ（Ｏi）−Ｉ（Ｏij）），  ０）
に従って示してもよく、ここで、指標ｉは前記一次標本点を示し、ｉ＝０・・・ｎ,ｎ＋１は前記一次標本点の番号であり、ここで、指標ｊは前記二次標本点を示し、ｊ＝０・・・ｍ,ｍ＋１は前記二次標本点の番号であり、Ｏiは前記一次標本点ｉを定義する３次元ベクトルであり、Ｏijは前記二次標本点ｉｊを定義する前記３次元ベクトルであり、  Ｉ（Ｏi）は前記一次標本点ｉにおける画像強度レベルを示し、Ｉ（Ｏij）は前記二次標本点ｉｊにおける画像強度レベルを示し、Ｉij  は前記一次標本点ｉと、前記一次標本点ｉに対応する前記二次標本点ｉｊとの間の画像強度の変化に対応する、負でないスカラーを示し、前記一次標本点ｉ各々における前記一次画像勾配は
Ｖij＝Ｉij／［ＳＱＲＴ（Σ（Ｉij）2）］
ここで、ｊ＝０，…，ｍ
Ｖi＝［Ｖi0（Ｏi−Ｏi0）／｜（Ｏi−Ｏi0）｜，・・・，Ｖim（Ｏi−Ｏim）／｜（Ｏi−Ｏim）｜］
により得られてもよく、Ｖijは前記二次標本点ｉｊにおける前記二次画像勾配成分の大きさを示すスカラーを与え、Ｖiは前記一次標本点ｉにおける前記一次画像勾配ベクトルを与え、各Ｖiはｊの総数に等しい次元を有し、前記キーポイント各々における前記特徴記述子ベクトルは、
Ｖ＝［Ｖ0，…  Ｖi  …，Ｖn］
に従って前記一次画像勾配の連結から得られてもよく、ｎは前記キーポイントに対して特定される前記一次標本点の数である。
【００４８】
本発明の第２３の態様によれば、コンピュータに、前記入出力インタフェースにより入力画像を受け取り、入力パラメータに基づく各々異なるぼかしスケールを有するガウスぼかしフィルタを前記入力画像に適用してガウスぼかし画像を生成することにより前記受け取った入力画像のガウシアンピラミッド空間を構築し、前記構築したガウシアンピラミッド空間中でキーポイントを検出し、前記検出したキーポイントからの３次元相対位置で定義される一次標本点を、前記キーポイント各々に対して前記ガウシアンピラミッド空間中で特定し、前記特定した一次標本点近傍における画像変化を示すベクトルである一次画像勾配を前記一次標本点に対応して計算し、前記計算した一次画像勾配を連結することにより前記入力画像に対する特徴記述子ベクトルを生成する、画像識別のための特徴記述子ベクトル生成処理を実行させるためのプログラムが提供される。
【発明の効果】
【００４９】
本発明の態様は、ＳＩＦＴがＳＵＲＦよりもすぐれている点を失わずに、ＳＩＦＴよりも高速に計算できる記述子を提供する。本発明の一態様によれば、高い弁別性を有し、かつ計算上の複雑さおよび次元を大幅に削減した、記述子が提供される。
【図面の簡単な説明】
【００５０】
本明細書に組み込まれ、本明細書の一部を成す添付の図面は、本発明の実施態様を例示し、説明と相俟って、本発明技術の原理の説明および例示に供する。具体的には以下のとおりである。
【図１】ＳＩＦＴ記述子の構築方法のフローチャートである。
【図２】ＳＩＦＴ記述子の構築を概略的に表示したものである。
【図３】本発明の態様による、新しい特徴セットを構築するための高速不変変換（ＦＩＴ）計算を実行する方法のフローチャートである。
【図４】本発明の態様による、ＦＩＴ画像記述子の構築を概略的に示す図である。
【図５Ａ】本発明の態様による、画像記述子構築方法のフローチャートである。
【図５Ｂ】本発明の態様による図５Ａに示した画像記述子構築方法の特定の実施例のフローチャートである。
【図６】本発明の態様による、画像記述子の構築を概略的に示す図である。
【図７】本発明のシステムが実装されているコンピュータプラットフォームの実施例である。
【図８】本発明の一態様と図７のコンピュータプラットフォームとの関係を示す図である。
【発明を実施するための形態】
【００５１】
以下の詳細な説明では添付の図面を参照する。ここで同一の機能的要素は同様の符号で示される。前述の添付の図面は、本発明の原理に合致する特定の実施態様および実装形態を限定としてではなく例示として示す。これらの実装形態は、当業者が本発明を実施できるように十分に詳細に説明される。また、本発明の趣旨および範囲を逸脱することなしに、他の実装形態が利用されてもよいこと、および様々な要素の構造上の変更および／または代用が行われてもよいことを理解されたい従って、以下の詳細な説明は、限定的な意味で解釈されるべきではない。さらに、説明される本発明の様々な実施形態は、汎用コンピュータ上で実行されるソフトウェアの形態、または専用ハードウェアの形態、あるいはソフトウェアとハードウェアの組合せ、のいずれで実装されてもよい。
【００５２】
本発明の態様は、画像識別用の特徴記述子の生成方法を提供する。この方法は、入力画像を受け取るステップと、入力パラメータを受け取るステップと、入力画像にガウスぼかしフィルタを適用してガウスぼかし画像を生成することにより入力画像のガウシアンピラミッド空間を構築するステップと、ガウシアンピラミッド空間に２つ以上の異なるスケールでキーポイントを見つけ出すステップと、ガウシアンピラミッド空間の３次元ベクトルを利用して、各キーポイントに対する一次標本点を特定するステップと、一次標本点に対応する一次画像勾配を計算するステップと、一次画像勾配を連結することにより入力画像に対する特徴記述子ベクトルを生成するステップと、を含む。特徴記述子ベクトルがユーザに提供される。ガウスぼかしフィルタは各々異なるスケールのぼかしを有し、そのスケールは入力パラメータに基づいている。各キーポイントの３次元ベクトルが、キーポイントに対して一次標本点を定義する。一次画像勾配は、一次標本点近傍における画像の変化を示すベクトルである。この方法は、入出力インタフェース、記憶媒体、１つまたは複数のプロセッサ、およびコンポーネント間の通信を提供するバス、を含むコンポーネントを有する計算機によって実装される。入力画像および入力パラメータは入出力インタフェースで受け取られ、特徴記述子ベクトルは入出力インタフェースを介してユーザに提供される。１つまたは複数のプロセッサが処理ステップを実行する。
【００５３】
本発明の態様は、画像識別用の特徴記述子の生成システムを提供する。システムは、入力画像を受け取るためおよび入力パラメータを受け取るための入出力インタフェースと、入力画像にガウスぼかしフィルタを適用してガウスぼかし画像を生成することにより入力画像のガウシアンピラミッド空間を構築するための１つまたは複数のプロセッサとを含む。１つまたは複数のプロセッサが、ガウシアンピラミッド空間に２以上の異なるスケールでキーポイントを見つけ出す。１つまたは複数のプロセッサが、ガウシアンピラミッド空間の３次元ベクトルを利用して、各キーポイントに対する一次標本点を特定する。ここで、各キーポイントの３次元ベクトルが、キーポイントに対して一次標本点を定義する。１つまたは複数のプロセッサが、一次画像勾配を、一次標本点に対応して計算する。一次画像勾配は、一次標本点近傍における画像の変化を示すベクトルである。１つまたは複数のプロセッサが、一次画像勾配を連結することによって入力画像に対する特徴記述子ベクトルを生成する。入出力インタフェースが、ユーザに対して入出力インタフェースを介して特徴記述子ベクトルを提供する。
【００５４】
前述および以下の説明はいずれも単に例示および説明を目的とするものであり、特許請求の範囲に記載の発明もしくはその適用を限定することは意図していないことを理解されたい。
【００５５】
本発明の態様は、文書画像あるいは従来の写真における対応点のマッチングをとるために設計された、新規の画像記述子の生成を対象とする。本発明の態様による新しい特徴セットを構築する方法は、本明細書においては、高速不変変換（ＦＩＴ（Ｆａｓｔ  Ｉｎｖａｒｉａｎｔ  Ｔｒａｎｓｆｏｒｍ））と称される。
【００５６】
本発明の態様が、ＳＩＦＴによる画像記述子よりもはるかに高速演算可能な（一実験例では、今のところ特徴抽出全体で約４倍、記述子構築だけに限れば約７０倍高速の）画像記述子を提供する。本発明の態様は、キーポイントスケールよりも上の多数の粗スケールでのスケール依存勾配を直接計算する。これは、すべての局所勾配をキーポイントのスケールで計算するＳＩＦＴとは異なる。さらに、本発明の態様においては、ＳＩＦＴで行われる多大な時間を必要とする勾配重み付けプロセスが除外される。その代わりに、ガウシアンピラミッドに生成されたデータが直接利用される。一方ＳＩＦＴでは、勾配が計算された後に、計算された局所勾配に対してガウシアン重み付けが行われ、これによって余計な計算ステップが追加される。
【００５７】
いくつかの例で，ＦＩＴで得られた結果とＳＩＦＴで得られた結果との違いを示す。ＳＩＦＴは１２８次元の記述子ベクトルを提供して、１つのスケールレベルでの情報を収集する。これとは対照的に、ＦＩＴは、たとえば４０次元の記述子ベクトルを提供し、これによって多数スケールでの情報を収集する。この設計により、空間領域を占有する記述子の自由度と共に記述子の次元を縮減する自由度が増す。本発明の態様の４０次元の記述子と１２８次元のＳＩＦＴ記述子とを、２００６年マルチメディア国際会議（ＩＣＭＥ０６）の論文１０００ページを対象に比較してみると、ＳＩＦＴは  ９９．９３％のページ認識率であったが、本発明の態様による方法では９９．９％のページ認識率を達成した。この２つの認識率は同等であるが、本発明の態様による方法が、識別子の構築およびその後の検索において著しく高速である。
【００５８】
さらに、ＳＩＦＴの１２８次元の記述子ベクトルに比べて、この例では記述子が４０次元しかないということから、ＦＩＴ記述子はＳＩＦＴ記述子が必要とする記憶容量の約１／３しか必要としない。この記憶容量の節約は、大量のデータを検索し指標付けするときに重要となる。本発明の態様が必要とする容量および計算の要求仕様は、認識率は同等であるにもかかわらず、ＳＵＲＦの要求仕様に比べて５０％低い。
【００５９】
ＳＩＦＴ記述子とＦＩＴ記述子との探索速度を、同じ近似最近傍探索（ＡＮＮ（ａｐｐｒｏｘｉｍａｔｅ  ｎｅａｒｅｓｔ  ｎｅｉｇｈｂｏｒ））アルゴリズムを用いて１０００ページの論文で比較してみると、ＦＩＴ記述子を利用するアルゴリズムの方が約９．１７倍速い。より大きなデータセットでの探索ではスピードはさらに増すと思われる。さらに、ＦＩＴアルゴリズムは、広い基線画像マッチング用のアクセシブルな情報システム（ＤＡＩＳＹ（ｄｉｇｉｔａｌ  ａｃｃｅｓｓｉｂｌｅ  ｉｎｆｏｒｍａｔｉｏｎ  ｓｙｓｔｅｍ））の記述子よりもはるかに高速であり得る。理論では、ＳＵＲＦが広い基線画像マッチングに対してもたらすような有害なアーチファクト（偽信号）をＦＩＴ記述子は持たない。
【００６０】
図３は本発明の態様による、新しい特徴セットを構築するための高速不変変換（ＦＩＴ）計算を実行する方法のフローチャートを示す。
【００６１】
本発明の概念の特徴に従った、ＦＩＴ特徴構築の例示的プロセスはステップ３０００から始まる。ステップ３００１で入力画像が受け取られる。この段階、あるいはその後で、その他の入力パラメータも受け取られる。ステップ３００２で、入力画像に対して段階的なガウスぼかしが行われてガウシアンピラミッドが構築される。ステップ３００３において、ガウシアンピラミッドにおける任意の連続する２つのガウスぼかし画像の差分を計算することによって、ＤｏＧピラミッドが構築される。ステップ３００４においてキーポイントが選択される。一例では、ＤｏＧ空間における極大および極小が決定され、これらの極大、極小の位置およびスケールがＤｏＧ空間およびガウシアンピラミッド空間におけるキーポイント位置として利用される。このステップまでは、ＦＩＴプロセスは図１のＳＩＦＴプロセスと同様に行われる。
【００６２】
ステップ３００５において、一次標本点（ｐｒｉｍａｒｙ  ｓａｍｐｌｉｎｇ  ｐｏｉｎｔ）と称される記述子の標本点が、ガウシアンピラミッド空間の各キーポイント位置に基づいて特定される。一次標本点という用語は、これらの記述子標本点を二次標本点（ｓｅｃｏｎｄａｒｙ  ｓａｍｐｌｉｎｇ  ｐｏｉｎｔ）と称されるポイントと区別するために用いられる。二次標本点のいくつかは、以下の図５Ａに関してさらに説明するように、一次標本点の各々に関連する。一次標本点各々とそれに対応するキーポイントとの間の関係は、空間型−スケール空間の３次元ベクトルによって定義される。より具体的には、キーポイントに始点を持ち、対応する一次標本点に終点を持つスケール依存の３次元ベクトルが、そのキーポイントの一次標本点を特定するために利用される。
【００６３】
ステップ３００６で、各一次標本点におけるスケール依存の勾配が計算される。これらの勾配は、一次標本点とそれに関連する二次標本点各々との間の画像強度の差に基づいて得られる。画像強度の差が負の場合には、二次標本点における画像強度が一次標本点における強度よりも高いことを示し、差はゼロに設定される。
【００６４】
ステップ３００７において、キーポイントの一次標本点のすべてからの勾配が連結されて特徴記述子としてのベクトルを形成する。
【００６５】
ステップ３００８でこの方法が終了する。
【００６６】
図３のフローチャートで示されるＦＩＴは、図１に示すＳＩＦＴよりも速く、その理由をこの節で検討する。１２８次元のＳＩＦＴ記述子各々に対しては、キーポイントの周りの４サブブロック×４サブブロックのブロックが使用され、各サブブロックは少なくとも４ピクセル×４ピクセルを含み、全体として１６ピクセル×１６ピクセルとなる。従って、勾配の値はキーポイントの周りの１６×１６＝２５６ピクセルすなわち標本点について計算する必要がある。さらに、各サブブロックが４ピクセル×４ピクセル以上の領域を含むことが一般的である。各サブブロックが４ピクセル×４ピクセル以上の領域を含む場合には、アルゴリズムとしてはさらに大きい数のポイントについて勾配を計算しなければならない。勾配はベクトルであり、大きさと方向すなわち配向の両方を有する。個々のピクセルについて勾配の大きさｍ（ｘ，ｙ）および配向Ｔｈｅｔａ（ｘ，ｙ）を計算するには、この方法では、足し算を５回、掛け算を２回、割り算を１回、平方根を１回、そしてアークタンジェントを１回計算しなければならない。本方法では、これらの２５６の勾配値に、１６×１６のガウシアンウィンドウで重み付けする必要もある。勾配値を各ポイントに対して正確に計算しようとすると、ＳＩＦＴではスケール空間での補間を必要とする。計算コストが絡むために、ＳＩＦＴの実装においては、適正なスケールでの勾配の評価は一般的にかなり大雑把である。
【００６７】
一方、ＦＩＴプロセスに反映された本発明の態様では、この例においては、基本操作として４０の加算を必要とする。４０の勾配値を補間する負担（コスト）はかなり小さいので、勾配をより正確に評価するためにスケール空間での補間が行われる。
【００６８】
図４は本発明の態様による、ＦＩＴ記述子の構築を概略的に示す。
【００６９】
図３のフローチャートのステップが図４に概略的に示されている。ガウシアンピラミッド（３００２）を構築するための画像のぼかし、およびＤｏＧ空間を得るための差分（３００３）が上左隅に示されており、キーポイントの計算の手順が右上隅（３００４）に示されている。個々のキーポイント６００１に対する５つの一次標本点６００２の特定、６００１の特定が下左隅（３００５）に示されている。空間型−スケール空間（３００６）における各一次標本点の勾配の計算、および特徴記述子ベクトル（３００７）に至る５つの一次標本点からの勾配の連結が、下右隅に示されている。
【００７０】
図５Ａは、本発明の態様による、画像記述子構築方法のフローチャートである。
【００７１】
図５Ａおよび図５Ｂは、図３のステップ３００４から３００７までのより詳細な例として示されている。しかし、図５Ａおよび図５Ｂに示されている画像記述子構築法は図３の方法に限定されるわけではなく、入力パラメータを受け取るステップと、スケールを定義するガウシアンピラミッドを構築すると共に入力画像を受け取るかあるいは直接キーポイントを受け取るステップとを含む別のプロセスがこの前に行われていてもよい。ただし、図５Ａおよび図５Ｂの方法に先行するステップに、図３に示した、キーポイントを探し出すために使用される差分ガウス空間の構築は含まれても、含まれなくてもよい。キーポイントはそれに代わる方法で抽出されてもよい。そしてキーポイントがスケール変化するガウシアンピラミッドの内部にありさえすれば、図５Ａおよび図５Ｂの方法は有効である。
【００７２】
この方法はステップ５０００で始まる。ステップ５００１でキーポイントが抽出される。キーポイントは多くの異なる方法で抽出することができる。そのうちの１つを図５Ｂの例示フローチャートに示す。ステップ５００２で一次標本点が、入力パラメータ（そのうちの１つはスケールである）に基づいて特定される。ステップ５００３で、二次標本点が、入力パラメータのいくつか（これにもスケールが含まれる）を利用して、各一次標本点について特定される。ステップ５００４で、各一次標本点における一次画像勾配が得られる。各一次標本点とそれに対応する二次標本点との間の画像強度ないしは別の画像特性の変化を示す二次画像勾配に基づいて、一次画像勾配が算出される。ステップ５００５で、キーポイントに対応するすべての一次標本点に対する一次画像勾配を連結することによって、キーポイントに対する記述子ベクトルが生成される。ステップ５００６でこの方法が終了する。
【００７３】
図５Ｂは本発明の態様による図５Ａに示した画像記述子構築方法の特定の実施例のフローチャートである。
【００７４】
ステップ５１００でこの方法が開始される。ステップ５１０１で差分ガウス空間の中にキーポイントが抽出され、各キーポイントが副座標系の中心に置かれる。ステップ５１０２で、いくつかの入力パラメータに基づいて一次標本点が特定される。これらの入力パラメータの１つがスケールを決定し、別の２つが、キーポイントを中心とする副座標系の中の一次標本点の座標を決定する。一次標本点は、キーポイントを起点とし、ガウシアンピラミッド内の異なるスケールにおける一次標本点を終点とするベクトルによって定義される。ステップ５１０３で、いくつかの入力パラメータを用いて各一次標本点に対して８つの二次標本点が定義される。ここで、このいくつかの入力パラメータにもスケールが含まれ、さらには、一次標本点を中心とする半径を決定するパラメータも含まれている。８つの二次標本点は一次標本点を中心とする円周に定義され、その半径は一次標本点のスケールに応じて変化する。二次標本点はキーポイントを起点とし、二次標本点を終点とするベクトルによって定義される。ステップ５１０４で、５つの一次標本点各々における一次画像勾配が得られる。一次画像勾配は、一次標本点の８つの二次画像勾配をその成分ベクトルとして含む。ステップ５１０５で、キーポイントに対応する５つの一次標本点すべてに対する一次画像勾配を連結することによって、キーポイントに対する記述子ベクトルが生成される。ステップ５１０６でこの方法が終了する。
【００７５】
図６は本発明の態様による、画像記述子の構築を概略的に示す図である。
【００７６】
本発明のさまざまな態様において、ガウシアンピラミッドおよびＤｏＧピラミッドは連続３次元空間型−スケール空間内にあると考えられる。連続３次元空間型−スケール空間の座標系において、空間平面は２つの直交軸ｕとｖで定義される。スケールの次元である、第３の次元が、空間軸ｕおよびｖで形成される平面に垂直な第３の軸ｗによって定義される。スケール次元とは、ガウシアンフィルタのスケールを指す。従って、空間型−スケール空間は、空間平面と、第３の次元を加えるスケールベクトルとによって構成される。画像は２次元空間平面中に形成される。画像の段階的ぼかしが第３の次元をもたらし、これがスケール次元である。キーポイント６００１各々は、局所副座標系の原点となり、ｕ、ｖ、ｗの各軸が原点とする。
【００７７】
この空間型−スケール座標系において、画像中の任意の点はＩ（ｘ，ｙ，ｓ）で表現される。ここで、（ｘ，ｙ）は空間型ドメイン（画像ドメイン）中の位置に対応し、ｓはスケールドメイン中のガウシアンフィルタスケールに対応する。空間型ドメインとは、画像が形成されるドメインである。従って、Ｉは位置（ｘ，ｙ）で、スケールｓのガウシアンフィルタによってぼかされた画像に対応する。キーポイントを原点とする局所副座標系は、空間型−スケール空間での記述子の詳細を記述するために定義される。この副座標系において、キーポイント６００１そのものは座標（０，０，０）を有し、ｕ方向は空間型ドメインのキーポイントの配向に一致する。キーポイントの配向は、ＳＩＦＴと同じようにして決められる勾配ヒストグラムの主要階級によって決定される。空間型ドメインのｖ方向は、空間型ドメインの中で原点を中心としてｕ軸を反時計方向に９０度回転して得られる。スケール変化に対応するｗ軸は空間型ドメインに垂直で、スケールの増大する方向に向いている。これらの方向は例示的なものであって、計算のやりやすさで選択される。副座標系に加えて、スケールパラメータｄ、ｓｄおよびｒが、一次標本点６００２の定義と、各一次標本点の周りの情報収集の制御のために用いられる。
【００７８】
図示された例示の態様においては、キーポイント６００１各々に対して、記述子情報が５つの一次標本点６００１、６００２で収集される。これにはキーポイントそのものは含まれても、含まれなくてもよい。図６は、キーポイント６００１が原点である副座標系における一次標本点の分布を示している。これらの一次標本点を、副座標系の原点（０，０，０）から標本点位置までの３次元ベクトルＯiで定義する。ここでｉ＝０，１，２，３，４である。従って、定義により原点（０，０，０）に位置するキーポイントに対応する一次標本点は次のベクトルで定義される。
Ｏ0＝［０  ０  ０］
Ｏ1＝［ｄ  ０  ｓｄ］
Ｏ2＝［０  ｄ  ｓｄ］
Ｏ3＝［−ｄ  ０  ｓｄ］
Ｏ4＝［０  −ｄ  ｓｄ］
【００７９】
一次標本点ベクトルＯi各々において、最初の２つの座標はベクトルの終点のｕ座標とｖ座標を示し、３番目の座標はスケールに対応するｗ座標を表す。各一次標本点ベクトルＯiはキーポイントを始点とする。
【００８０】
本発明の他の実施形態および態様においては、異なる数の一次標本点が用いられる。
【００８１】
図に示した例示の態様においては、一次標本点には原点すなわちキーポイント６００１そのものも含まれる。しかし、一次標本点はキーポイントを含まないように選択されてもよい。一次標本点の座標が示すように、これらのポイントは異なるスケールで選択される。示された例示の態様においては、一次標本点は２つの異なるスケール、０およびｓｄで選択されている。しかし、一次標本点は各々異なるスケールで選ばれてもよいし、異なるスケールの任意の組合せで選ばれてもよい。一次標本点がすべて同一のスケールで選択されたとしても、本発明の態様は、一次および二次標本点の両方の選択方法においてＳＩＦＴとは区別される。
【００８２】
例示した態様においては、５つの一次標本点各々で８つの勾配値が計算される。まず、ベクトルＯiで示される各一次標本点のまわりに、次式に従って、ベクトルＯijで表示される８つの二次標本点が定義される。
Ｏij−Ｏi，＝［ｒi ｃｏｓ（２πｊ／８）   ｒi ｓｉｎ（２πｊ／８）  ０］            ここで、ｉ＝０  ｆｏｒ  ｊ＝１，…，７
Ｏij−Ｏi，＝［ｒi ｃｏｓ（２πｊ／８）   ｒi ｓｉｎ（２πｊ／８）  ｓｄ］          ここで、ｉ≠０  ｆｏｒ  ｊ＝１，…，７
【００８３】
上の式によれば、これらの８つの二次標本点は、図６に示すように、一次標本点を中心とする円周上に均一に分布している。円の半径は一次標本点のある平面のスケールに依存し、従ってスケールが大きくなれば半径も大きくなる。半径の増大と共に、一次標本点からも、また相互にも遠く離れた二次標本点が収集され、高いスケールでは密にサンプリングする必要のないことを示している。８つの二次標本点Ｏijおよびそれに対応する中心の一次標本点Ｏiに基づいて、各一次標本点に対する一次画像勾配ベクトルＶiは次式で計算される。
Ｉij＝ｍａｘ（Ｉ（Ｏi）−Ｉ（Ｏij）），  ０）
この式において、Ｉij はスカラーである。
Ｖij＝Ｉij／［ＳＱＲＴ（Σ（Ｉij）2）］
この式において、ｊ＝０，…，７、Ｖijはスカラーである。
Ｖi＝［Ｖi0（Ｏi−Ｏi0）／｜（Ｏi−Ｏi0）｜，
Ｖi1（Ｏi−Ｏi1）／｜（Ｏi−Ｏi1）｜，
Ｖi2（Ｏi−Ｏi2）／｜（Ｏi−Ｏi2）｜，
Ｖi3（Ｏi−Ｏi3）／｜（Ｏi−Ｏi3）｜，
Ｖi4（Ｏi−Ｏi4）／｜（Ｏi−Ｏi4）｜，
Ｖi5（Ｏi−Ｏi5）／｜（Ｏi−Ｏi5）｜，
Ｖi6（Ｏi−Ｏi6）／｜（Ｏi−Ｏi6）｜，
Ｖi7（Ｏi−Ｏi7）／｜（Ｏi−Ｏi7）｜］
【００８４】
上の式においてＶiは、方向［Ｏi−Ｏi0，  Ｏi−Ｏi1，  Ｏi−Ｏi2，  Ｏi−Ｏi3，  Ｏi−Ｏi4，  Ｏi−Ｏi5，  Ｏi−Ｏi6，  Ｏi−Ｏi7］にスカラー成分  ［Ｖi0，  Ｖi1，  Ｖi2，  Ｖi3，  Ｖi4，  Ｖi5，  Ｖi6，  Ｖi7］を持つベクトルである。方向ベクトルはその大きさで割って正規化される。
【００８５】
スカラー値Ｉは特定の位置における画像強度レベルに対応する。スカラー値Ｉij  は、一次標本点の画像強度Ｉ（Ｏi）各々と、ある特定の標本点を中心とする円周上に等間隔で選択された、８つの二次標本点の画像強度Ｉ（Ｏij）各々との差を与えている。画像強度におけるこの差がゼロより小さく、負の値を持つ場合には、この値はゼロに設定される。従って、結果として成分の値Ｖijは負の成分とはならない。各円の周りに、つまりｉ＝０，…，４の５つの一次標本点各々に対してｊ＝０，…，７の８つの二次標本点がある。従って、８つの成分ベクトルＩi0Ｏi0／｜Ｏi0｜，  …  ，Ｉi7Ｏi7／｜Ｏi7｜が、５つの一次標本点各々に対する１つの成分ベクトルＶiとなる。成分ベクトルＶi各々は、それ自身が８つの成分を持っている。Ｉi0，…  ，Ｉi7  に対応する成分ベクトルは二次画像勾配ベクトルと呼ばれ、成分ベクトルＶiは一次画像勾配ベクトルと呼ばれる。
【００８６】
５つの一次標本点で計算される５つの一次画像勾配ベクトルを連結することにより、キーポイントに対する記述子ベクトルＶが次式で与えられる。
Ｖ＝［Ｖ0，Ｖ1，Ｖ2，Ｖ3，Ｖ4］
【００８７】
上の式において、パラメータｄ、ｓｄ、ｒはすべて副座標系におけるキーポイントのスケールに依存する。キーポイントスケールはスケールｓで表され、基準標準偏差すなわちスケールｓ0の整数あるいは非整数の倍数であってもよいし、別の方法で決められてもよい。決定方法にかかわらず、スケールｓはキーポイントの位置によって変わり得る。３つの一定値ｄｒ、ｓｄｒ、ｒｒが系への入力として与えられる。５つの一次標本点の座標を決定するｄ、ｓｄ、ｒiの値は、スケールｓと共に３つの定数ｄｒ、ｓｄｒ、  ｒｒを用いて得られる。二次標本点が位置する、一次標本点を中心とする円の半径も、同じ入力定数値で得られる。一次および二次標本点のどちらの座標も、このように以下の式により得られる。
ｄ＝ｄｒ×ｓ
ｓｄ＝ｓｄｒ×ｓ
ｒi＝ｒ0（１＋ｓｄｒ）
ここで  ｒ0＝ｒｒ×ｓ
【００８８】
上の式はすべてスケール因子ｓを含んでおり、座標がスケールの関数で変化するようにすべてスケールに依存している。例えば、各一次標本点が位置している平面のスケールは、別の一次標本点が位置している平面のスケールとは違う可能性がある。従って、一次標本点が変わると、スケールｓが変化し、すべての座標ｄ、ｓｄ  および  半径ｒiも同様に変わる。スケール依存性が組み込まれている限りは、一次および二次標本点の座標を得るのに他の式を用いてもよい。
【００８９】
ある状況においては、各勾配ベクトルのスケールｓはガウシアンピラミッド中の計算された画像平面の間にあってもよい。このような状況では、勾配値は一次標本点に最近接の２つの画像平面上でまず計算される。その後、ラグランジェ補間法を用いて一次標本点のスケールにおける勾配ベクトルを計算する。
【００９０】
本発明の１つの例示的態様においては、ガウシアンピラミッド構築に用いるガウシアンフィルタの標準偏差が既定値としてシステムに入力される。この標準偏差パラメータをｓ0で表す。そうすると、可変スケールｓは、ｓ＝ｍiｓ0のようにｓ0の整数倍もしくは非整数倍で定義される。他の例においては、ｓの変化は、図２および図４に示す各オクターブの最初と最後の平面の間にある３つの平面に合うように決定される。
【００９１】
本発明の態様による評価例を以下に示す。
【００９２】
実験的な評価例において、パラメータｓ0、ｄｒ、ｓｄｒ、ｒｒは実験的に決定され、本発明の方法およびシステムに入力された。パラメータｓ0は、異なるぼかし度合いでガウスぼかし画像を取得するのに用いた基準標準偏差である。
【００９３】
実験例として本発明の方法およびシステムを、ＩＣＭＥ０６会議録の１０００ページに適用した。各ページを３０６×３９６の画像に変換し、キーポイントおよび特徴ベクトルを抽出するトレーニング用画像としてシステムに供給した。各ページの画像を０．１８倍から２倍の間でランダムに拡大、縮小し、０度から３６０度の間の角度でランダムに回転させて、各入力ページに対応する３つのテスト画像を取得して３０００のテスト画像を生成した。同一の画像の異なるサイズおよび回転を用いたシステムのテストで、システムが拡大・縮小や回転に対して不変であるかどうかが示される。３０００のテスト画像がシステムに与えられた。結果として得られた出力は、この入力画像に対してページの認識率が９９．９％であった。一方で、同一の探索アルゴリズム、同一のトレーニング用画像、同一のテスト画像を用いたＳＩＦＴ記述子の場合には、ページ認識率が９９．９３％であった。本発明の方法およびシステムのより大きなデータセットに対する実現可能性を、ＩＣＭＥ０６会議録の２１８８ページを利用してテストした。このより大きなデータセットに対する本発明の方法およびシステムの認識率は９９．６％であった。これらの実験に基づけば、本発明の方法およびシステムを適用して得られる特徴セットは，ＳＩＦＴで得られる特徴セットに対して認識率において同等あるいはそれ以上である。
【００９４】
また同時に、本発明の態様による探索スピードはＳＩＦＴシステムのスピードを凌ぎ、本発明の態様の探索時間は，ＳＩＦＴシステムが要する時間よりも約１桁小さかった。本発明の態様による特徴セットに基づく探索時間と、ＳＩＦＴ特徴セットによる探索時間が記録され比較された。この比較では、探索は近似最近傍探索（ＡＮＮ）アルゴリズムに基づいており、前に述べたように、トレーニング用データセットは１０００ページであり、テスト画像は３０００画像である。本発明の態様による記述子ベクトルを用いた場合、実験的に得られた平均画像探索時間は２４ｍｓであった。一方、ＳＩＦＴ記述子を用いた場合の平均探索時間は２２０ｍｓであった。従って、ＳＩＦＴに比べて本発明の態様がより高速で同等の認識率を与えることが実験的に示された。
【００９５】
前述したように、本発明の態様は、各キーポイントを始点とし、異なるスケールに対応する位置を終点とする一連の３次元ベクトルを利用する。この３次元ベクトルの終点が、各キーポイントに対するガウシアンピラミッド空間における一次標本点を定義する。本発明の態様に対比してＳＩＦＴでは、標本点の代わりに標本矩形、すなわち標本を用い、そしてＳＩＦＴのすべての標本矩形は，ＳＩＦＴにおいて選択されたキーポイントと同一のスケール上にある。
【００９６】
さらに本発明の態様では、各一次標本点の周りのスケール依存勾配を計算し、１つのキーポイントに関するすべての一次標本点からの勾配を連結して特徴記述子ベクトルを形成する。一実施例では、各キーポイントのサンプリングに５つの一次標本点が用いられ、その５つの一次標本点各々を中心とする円の周りに８つの二次標本点が決定される場合、キーポイント各々に対し４０次元の特徴記述子ベクトルが得られる。この本発明の態様とは対照的に、ＳＩＦＴでは同一スケールの隣接ピクセル間だけで勾配が算出され、単一スケールレベルに関する大きな領域に亘って勾配が平均化される。画像認識において同等のレベルの精度を得ようとすると、ＳＩＦＴでは１２８次元の特徴記述子ベクトルの使用が必要となる。
【００９７】
従って本発明の態様では、不変画像特徴ベクトルの構築が高速化され、対応する画像特徴を探索する時間幅が短縮可能となり、大容量の画像データを指標付けするメモリスペースおよびディスクスペースが節約可能であり、ハード、ソフトおよびエネルギのコストが節約可能となる。
【００９８】
図７は、本発明による方法の実施形態を実装することが可能なコンピュータ／サーバ
システム７０００の実施形態を示すブロック図である。
【００９９】
システム７０００は、コンピュータ／サーバプラットフォーム７００１と、周辺装置７００２と、ネットワークリソース７００３とを含む。
【０１００】
コンピュータプラットフォーム７００１は、このコンピュータプラットフォーム７００１の全体に亘る情報あるいはコンピュータプラットフォーム７００１の様々な部分間での情報をやり取りするためのデータバス７００５または他の通信機構と、情報を処理し他の計算タスクおよび制御タスクを実行するためにバス７００１に連結されたプロセッサ７００５と、を含むことができる。また、コンピュータプラットフォーム７００１は、プロセッサ７００５で実行される命令および様々な情報を格納するためにバス７００４に連結された、ランダムアクセスメモリ（ＲＡＭ）のような揮発性ストレージ７００６や他の動的ストレージデバイスも含む。また、揮発性ストレージ７００６は、プロセッサ７００５による命令の実行中に一時変数や、その他の中間情報を格納するために使用することも可能である。コンピュータプラットフォーム７００１は、種々のシステム構成パラメータや基本入出力システム（ＢＩＯＳ）などのような、静的情報およびプロセッサ７００５用の命令を格納するために、バス７００４に連結された読み取り専用メモリ（ＲＯＭあるいはＥＰＲＯＭ）７００７や、その他の静的ストレージデバイスをさらに含むことができる。磁気ディスク、光ディスク、ソリッドステートフラッシュメモリデバイスなどの永続ストレージデバイス７００８が、情報および命令を格納するために提供され、バス７００１に連結される。
【０１０１】
コンピュータプラットフォーム７００１は、コンピュータプラットフォーム７００１のシステム管理者あるいはユーザに対して情報を表示するために、陰極線管（ＣＲＴ）、プラズマディスプレイ、液晶ディスプレイ（ＬＣＤ）のようなディスプレイ７００９にバス７００４を介して連結することができる。英数字キーおよびその他のキーを含む入力デバイス７０１０が、情報およびコマンド選択をプロセッサ７００５に通信するためにバス７００４に連結される。別のタイプのユーザ入力デバイスとして、マウスやトラックボールやカーソル方向キーのようなカーソル制御デバイス７０１１があり、方向情報およびコマンド選択をプロセッサ７００５に通信し、またディスプレイ７００９上のカーソル移動を制御する。通常、この入力デバイスは、第１の軸（たとえばｘ軸）および第２の軸（例えばｙ軸）の２つ軸における自由度２を有しており、これにより平面上の位置を特定することができる。
【０１０２】
コンピュータプラットフォーム７００１に付加的、あるいはリムーバブルなストレージ容量を提供するために、外部ストレージデバイス７０１２をバス７００４を介してコンピュータプラットフォーム７００１に接続することができる。コンピュータシステム７０００のある実施形態においては、他のコンピュータシステムとのデータ交換を容易にするために外部のリムーバブルストレージデバイス７０１２を使用することができる。
【０１０３】
本発明は、本明細書で説明する技術を実施するためのコンピュータシステム７０００の使用に関する。ある実施態様では、本発明のシステムがコンピュータプラットフォーム７００１のようなマシンに備わっている。本発明の一実施態様によれば、ここで説明する技術は、揮発性メモリ７００６に含まれる１つまたは複数の命令の１つまたは複数のシーケンスを、プロセッサ７００５が実行するのに応答して、コンピュータシステム７０００で実行される。このような命令は、永続ストレージデバイス７００８のような別のコンピュータ可読媒体から揮発性メモリ７００６に読み込むことができる。揮発性メモリ７００６に含まれる命令のシーケンスを実行することにより、プロセッサ７００５がここに説明するプロセスステップを遂行する。別の実施態様では、本発明を実施するのに、ソフトウェアによる命令の代わりに、あるいはソフトウェアによる命令と組み合わせて、配線による回路を使用することができる。したがって、本発明の実施態様は、ハードウェア回路とソフトウェアのいかなる特定の組み合わせにも限定されるものではない。
【０１０４】
本明細書で使用される「コンピュータ可読媒体」という用語は、プロセッサ７００５に実効命令を与えることに関与する任意の媒体を指す。コンピュータ可読媒体は、本明細書で説明する任意の方法および／または技術を実施するための命令を伝えることができる、マシン可読媒体の一例に過ぎない。このような媒体は多くの形態を取ることができ、不揮発性媒体、揮発性媒体および伝送媒体などが含まれる。ただしこれに限定されるものではない。不揮発性媒体には、ストレージデバイス７００８のような、例えば光ディスク、あるいは磁気ディスクが含まれる。揮発性媒体には、揮発性ストレージ７００６のようなダイナミックメモリが含まれる。伝送媒体には、データバス７００４を構成する配線を含め、同軸ケーブル、銅線および光ファイバが含まれる。
【０１０５】
コンピュータ可読媒体の一般的形態として、例えば、フロッピディスク(登録商標)、フレキシブルディスク、ハードディスク、磁気テープ、あるいは他の任意の磁気媒体、ＣＤ−ＲＯＭ、他の任意の光媒体、パンチカード、紙テープ、その他の孔でパターンを形成する任意の物理媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、フラッシュＥＰＲＯＭ、フラッシュドライブ、メモリカード、その他の任意のメモリチップまたはメモリカートリッジ、あるいはコンピュータが読み取ることができる他の任意の媒体、が含まれる。
【０１０６】
様々な形態のコンピュータ可読媒体が、プロセッサ７００５での実行のために、１つまたは複数の命令の１つまたは複数のシーケンスの伝送に関与し得る。例えば、命令が先ず、リモートコンピュータから磁気ディスクへ伝送されてもよい。もしくは、リモートコンピュータが命令をリモートコンピュータのダイナミックメモリに書込み、モデムを使用して電話線で命令を送信することもできる。コンピュータシステム７０００にローカルなモデムが電話線上でデータを受信し、赤外線送信機を使用してそのデータを赤外線信号に変換することができる。赤外線検出器が赤外線信号で伝送されるデータを受信し、適切な回路によってそのデータをデータバス７００４に乗せることができる。バス７００４がデータを揮発性ストレージ７００６に伝送し、そこからプロセッサ７００５が命令を取り出して、実行する。揮発性メモリ７００６によって受け取られる命令は、プロセッサ７００５の実行の前後のいずれかにオプションとして、永続ストレージデバイス７００８上に格納されてもよい。この命令は、当技術分野で周知の様々なネットワークデータ通信プロトコルを使用して、インタネットを介してコンピュータプラットフォーム７００１にダウンロードすることも可能である。
【０１０７】
コンピュータプラットフォーム７００１は、データバス７００４に連結されたネットワークインタフェースカード７０１３のような、通信インタフェースも含む。通信インタフェース７０１３は、ローカルエリアネットワーク（ＬＡＮ）７０１５に接続されたネットワークリンク７０１４に連結する双方向のデータ通信を提供する。例えば、通信インタフェース７０１３が、対応する型式の電話線とのデータ通信接続を提供する、総合デジタル通信網（ＩＳＤＮ）カードあるいはモデムであってもよい。別の例としては、通信インタフェース７０１３が、互換性のあるＬＡＮとのテータ通信接続を提供する、ローカルエリアネットワークインタフェースカード（ＬＡＮ  ＮＩＣ）であってもよい。よく知られた７００２．１１ａ、７００２．１１ｂ、７００２．１１ｇおよびブルートゥース（Ｂｌｕｅｔｏｏｔｈ（登録商標））などのような無線リンクもネットワーク実装に用いることができる。これらのいずれの実装においても、通信インタフェース７０１３が、種々のタイプの情報を表すデジタルデータストリームを伝送する電気信号、電磁信号、あるいは光信号を送受信する。
【０１０８】
ネットワークリンク７０１３が、通常、１つまたは複数のネットワークを介して他のネットワークリソースへのデータ通信を提供する。例えば、ネットワークリンク７０１４が、ＬＡＮ７０１５を介してホストコンピュータ７０１６、あるいはネットワークストレージ／サーバ７０１７への接続を提供することができる。これに加えて、もしくはこれに代わって、ネットワークリンク７０１３がゲートウェイ／ファイアウォール７０１７を介して、インタネットのような、広域ネットワークあるいはグローバルネットワーク７０１８へ接続することもできる。このようにしてコンピュータプラットフォーム７００１が、リモートネットワークストレージ／サーバ７０１９のような、インタネット７０１８上のどこにあるネットワークリソースへでもアクセスすることができる。その一方で、コンピュータプラットフォーム７００１も、ＬＡＮ７０１５、および／またはインタネット７０１８の上のどこにいるクライアントからでもアクセスされうる。ネットワーククライアント７０２０および７０２１自体が、プラットフォーム７００１と同様のコンピュータプラットフォームに基づいて実装されてもよい。
【０１０９】
ＬＡＮ７０１５およびインタネット７０１８はともに、デジタルデータストリームを伝送する電気信号、電磁信号あるいは光信号を使用する。コンピュータプラットフォーム７００１へ向けて、またはコンピュータプラットフォーム７００１から、デジタルデータを伝送する、さまざまなネットワークを介する信号、ならびにネットワークリンク７０１４上の信号および通信インタフェース７０１３を介する信号が、情報を搬送するキャリア波の例示的な形態である。
【０１１０】
コンピュータプラットフォーム７００１が、インタネット７０１８およびＬＡＮ７０１５を含む様々なネットワーク、およびネットワークリンク７０１４および通信インタフェース７０１３を介して、メッセージを送信し、プログラムコードを含むデータを受信することができる。インタネットの例では、システム７００１がネットワークサーバとして作用する場合に、インタネット７０１８、ゲートウェイ／ファイアウォール７０１７、ＬＡＮ７０１５および通信インタフェース７０１３を介して、クライアント７０２０および／または７０２１上で動作するアプリケーションプログラム用の所望のコードあるいはデータを送信することが可能である。同様に、システムが他のネットワークソースからコードを受け取ることもできる。
【０１１１】
受信されるコードはそのままでプロセッサ７００５で実行されるか、および／または、後での実行に備えて永続ストレージデバイス７００８あるいは揮発性ストレージデバイス７００６に格納されるか、あるいは、その他の不揮発性ストレージに格納されることが可能である。このように、コンピュータシステム７００１が伝送波の形式でアプリケーションコードを入手することができる。
【０１１２】
図８は本発明の一態様と図７のコンピュータプラットフォームとの関係を示す図である。
【０１１３】
本発明のいくつかの態様に関連して前述されたプロセスは図８に示すコンピュータプラットフォームシステム８０００上に実装されてもよい。入力画像は外部ストレージデバイス８０１２に格納されるか、ネットワークインタフェースカード８０１４を介してネットワークから受信するか、あるいはスキャナ８０１１を介して受信してもよい。入力パラメータはキーボード８０１０を介してシステムに提供される。入力画像および中間出力はユーザに対してディスプレイ８００９上に表示されてもよい。ＣＰＵ８００５、揮発性ストレージ８００６および永続ストレージ８００８は、データバス８００４を介して共に通信し、入力画像および入力パラメータを処理するさまざまなステップを実行して画像記述子ベクトルを取得し、それをユーザに対してディスプレイ８００９上に表示できるようにしてもよい。
【０１１４】
最後に、本明細書で説明したプロセスおよび技術は特定の装置に生得的に関係するものではなく、構成要素の任意の適切な組み合わせによって実施可能であることを理解されたい。さらに、種々のタイプの汎用デバイスを、ここで説明した教示にしたがって使用することが可能である。ここで説明した方法のステップを実行するための専用の装置を構築することが有利な場合もありうるであろう。本発明を特定の例に関連して説明したが、これらは全ての点において限定的ではなく説明的であることを意図している。ハードウェア、ソフトウェア、およびファームウェアの多くの異なる組み合わせが本発明の実行に適することが、当業者には理解されるであろう。例えば、説明したソフトウェアは、アセンブラ、Ｃ／Ｃ＋＋、ｐｅｒｌ、ｓｈｅｌｌ、ＰＨＰ、Ｊａｖａ（登録商標）、などの広範なプログラム言語あるいはスクリプト言語によって実施することが可能である。
【０１１５】
さらに本発明の他の実施態様が、ここに開示した本発明の明細書および実施を考慮することにより当業者には明らかとなるであろう。説明した実施態様の様々な態様および／または構成要素は、本発明のシステムに単独もしくは任意の組み合わせで使用することが可能である。明細書および実施例は例示としてのみ理解されるべきであり、本発明の真の範囲と精神は添付の特許請求の範囲およびその均等物によって示されるものとする。
【図１】
2010086540.tif 000003
【図２】
2010086540.tif 000004
【図３】
2010086540.tif 000005
【図４】
2010086540.tif 000006
【図５Ａ】
2010086540.tif 000007
【図５Ｂ】
2010086540.tif 000008
【図６】
2010086540.tif 000009
【図７】
2010086540.tif 000010
【図８】
2010086540.tif 000011