(57)【要約】  画像に作用する方法および装置が記載されている。特に、複数の異なるスケールおよび異なる回転において機能する関心点検出および／または記述、例えば、スケール不変かつ回転不変な関心点検出および／または記述のための方法および装置が記載されている。本発明は、同一画像内または複数の異なる画像内において関心点をマッチングする、改良されたまたは代替的な装置および方法を提供することができる。本発明は、本発明の方法を実施する、代替的または改良されたソフトウェアを提供することができる。本発明は、フィルタリングされた複数の画像を生成する複数のフィルタリング動作によって生成された、代替的または改良されたデータ構造、および、フィルタリングされた上記画像を記憶する、メモリ内に記憶またはネットワークを介して転送される、データ構造を提供することができる。本発明は、画像内の関心点の記述子を含む、例えばメモリ内に記憶またはネットワークを介して転送される、代替的または改良されたデータ構造、および、そのような記述子を、原画または原画から生じる画像（例えばサムネイル画像）に関連付けるデータ構造を提供することができる。
2009535680.tif 000002
【特許請求の範囲】
【請求項１】
複数の画素を有する画像内における、当該画像内における位置および向きを有する関心点の記述子を導出する方法であって、
上記関心点の上記向きに整列していると共に、１セットの画素を含んでいる、上記関心点周囲の近傍を識別する工程と、
上記向きに対して固定関係（fixed relation）を有している少なくとも１つの方向において、上記関心点の上記近傍におけるコントラストを、少なくとも１つのデジタルフィルタを用いて調べると共に、これによって、各方向に対して独立して、第１のスカラーコントラスト測度（scalar contrast measure）を生成する工程と、
１つの方向のみからの上記第１のスカラーコントラスト測度の組み合わせである第２のスカラーコントラスト測度である第１の要素を含む、多次元記述子を生成する工程とを含む方法。
【請求項２】
複数の画素を有する画像内における、当該画像内における位置および向きを有する関心点の記述子を導出する方法であって、
上記関心点の上記向きと整列していると共に１セットの画素を含んでいる、上記関心点周囲の近傍内における一領域を識別する工程と、
上記領域のタイルを調べ、そして各タイルに対して、少なくとも１つのデジタルフィルタを用いてコントラスト関連の応答を生成する工程と、
少なくとも２つの直交方向に上記少なくとも１つのデジタルフィルタを適用した応答値を合計して、合計された値を生成する工程と、
合計された上記値に基づく第１の要素を有する多次元記述子を生成する工程とを含む方法。
【請求項３】
上記記述子は、上記関心点におけるラプラシアンの符号である第２の要素を含んでいる請求項１または２に記載の方法。
【請求項４】
上記少なくとも１つのデジタルフィルタは、ハールウェーブレットフィルタ（Haar wavelet filter）である請求項１〜３のいずれか一項に記載の方法。
【請求項５】
第１の要素は、少なくとも２つの方向に上記少なくとも１つのデジタルフィルタを適用した結果得られる、合計された絶対値に基づいている請求項１〜４のいずれか一項に記載の方法。
【請求項６】
複数の画素を有する画像内における、当該画像内における位置および向きを有する関心点であり、且つ当該関心点の当該向きと整列していると共に１セットの画素を含んでいる当該関心点の周囲に規定された近傍を有している当該関心点の記述子を導出する方法であって、
少なくとも１つのデジタルフィルタを用いて、上記関心点の上記近傍におけるコントラストを調べる工程と、
上記少なくとも１つのデジタルフィルタを適用した結果、およびこれらの結果の絶対値に基づいて、多次元記述子を生成する工程とを含む方法。
【請求項７】
上記記述子は、上記関心点におけるラプラシアンの符号を有している請求項６に記載の方法。
【請求項８】
複数の画素を有する画像内における、位置を有する関心点の向きを割り当てる方法であって、
上記関心点を取り囲む領域を識別する工程と、
上記関心点の向きを決定する工程とを含んでおり、
上記関心点の向きを決定する工程は、上記領域の複数の画素を含む複数のタイルを調べ、各タイルに対して、２つの方向におけるコントラストに関連するフィルタリングされた値を決定し、これによって、上記タイルの向きおよび当該向きの大きさを決定し、決定された最大の上記向きを選択することによって上記関心点の向きを割り当てる方法。
【請求項９】
複数の異なるスケールおよび／または回転で機能するのに適した複数の画素を有する上記画像内における上記関心点を決定する工程を含む方法であって、
少なくとも１つのデジタルフィルタを用いて上記画像をフィルタリングする工程と、
上記少なくとも１つのデジタルフィルタの適用の結果得られる測度の決定に基づいて関心点を選択する工程とをさらに含んでおり、
上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせであると共に、２つ以上の次元または方向における画像パラメータ変化量を取り込み、上記少なくとも１つのデジタルフィルタは、少なくとも１つが一画素よりも大きい空間範囲（spatial extent）を有している、複数のボックスフィルタの組み合わせである請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
上記少なくとも１つのデジタルフィルタの上記画像への適用は、積分画像を用いて行われる請求項９に記載の方法。
【請求項１１】
複数の異なるスケールおよび／または回転で機能するのに適した複数の画素を有する上記画像内における関心点を決定する工程を含んでおり、
少なくとも１つのデジタルフィルタを用いて上記画像をフィルタリングする工程と、
上記少なくとも１つのデジタルフィルタの適用の結果得られる測度の決定に基づいて関心点を選択する工程とをさらに含んでおり、
上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせであり、
上記少なくとも１つのデジタルフィルタの上記適用は積分画像を用いる請求項１〜８のいずれか一項に記載の方法。
【請求項１２】
上記少なくとも１つのデジタルフィルタは、複数のボックスフィルタの組み合わせであり、少なくとも１つのボックスフィルタは、一画素よりも大きい空間範囲を有している請求項１１に記載の方法。
【請求項１３】
複数のボックスフィルタの上記組み合わせは、２つ以上の方向において平滑化フィルタの微分係数を近似する請求項９〜１２のいずれか一項に記載の方法。
【請求項１４】
上記少なくとも１つのデジタルフィルタを用いて、複数の異なるスケールにおいて、フィルタリングされた複数の画像を提供する工程をさらに含んでいる請求項９〜１３のいずれか一項に記載の方法。
【請求項１５】
上記測度は、上記少なくとも１つのフィルタを適用した上記結果から構成されたヘッセ行列の行列式である請求項９〜１４のいずれか一項に記載の方法。
【請求項１６】
上記少なくとも１つのフィルタの適用は、少なくとも３つのデジタルフィルタの適用を含んでいる請求項９〜１５のいずれか一項に記載の方法。
【請求項１７】
上記少なくとも１つのデジタルフィルタは、上記平滑化フィルタの２階微分係数から導かれる請求項９〜１６のいずれか一項に記載の方法。
【請求項１８】
上記少なくとも１つのデジタルフィルタは、複数の異なるスケーリングにおいて上記画像に適用されて、フィルタリングされた複数の画像を生成する請求項９〜１７のいずれか一項に記載の方法。
【請求項１９】
関心点は、フィルタリングされた画像の領域を含む近傍内において、上記測度の局所極値（local extreme value）として決定される請求項９〜１８のいずれか一項に記載の方法。
【請求項２０】
上記近傍は、画像ピラミッド内に論理的に配置された、フィルタリングされた複数の画像のうち少なくとも３つによって規定される空間である請求項１９に記載の方法。
【請求項２１】
複数の異なるスケールおよび／または回転で機能するのに適した複数の画素を有する画像内における関心点を決定する方法であって、
少なくとも１つのデジタルフィルタを用いて上記画像をフィルタリングする工程と、
上記少なくとも１つのデジタルフィルタの適用の結果得られる測度の決定に基づいて関心点を選択する工程とを含んでおり、
上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせであると共に、２つ以上の次元または方向における画像パラメータの変化量を取り込み、上記少なくとも１つのデジタルフィルタは、少なくとも１つが一画素よりも大きい空間範囲を有している、複数のボックスフィルタの組み合わせである方法。
【請求項２２】
上記少なくとも１つのデジタルフィルタの上記画像への適用は、積分画像を用いて行われる請求項２１に記載の方法。
【請求項２３】
複数の異なるスケールおよび／または回転で機能するのに適した複数の画素を有する画像内における関心点を決定する方法であって、
少なくとも１つのデジタルフィルタを用いて上記画像をフィルタリングする工程と、
上記少なくとも１つのデジタルフィルタの適用の結果得られる測度の決定に基づいて関心点を選択する工程と、
上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせであり、
上記少なくとも１つのデジタルフィルタの上記適用は積分画像を用いる方法。
【請求項２４】
上記少なくとも１つのデジタルフィルタは、複数のボックスフィルタの組み合わせであり、少なくとも１つのボックスフィルタは、一画素よりも大きい空間範囲を有している請求項２３に記載の方法。
【請求項２５】
上記複数のボックスフィルタの組み合わせは、２つ以上の方向において平滑化フィルタの微分係数を近似する請求項２１〜２４のいずれか一項に記載の方法。
【請求項２６】
上記少なくとも１つのデジタルフィルタを用いて、複数の異なるスケールにおいて、フィルタリングされた複数の画像を提供する工程をさらに含んでいる請求項２１〜２５のいずれか一項に記載の方法。
【請求項２７】
上記測度は、上記少なくとも１つのフィルタを適用した上記結果から構成されたヘッセ行列の行列式である請求項２１〜２６のいずれか一項に記載の方法。
【請求項２８】
上記少なくとも１つのフィルタの適用は、少なくとも３つのデジタルフィルタの適用を含んでいる請求項２１〜２７のいずれか一項に記載の方法。
【請求項２９】
上記少なくとも１つのデジタルフィルタは、上記平滑化フィルタの２階微分係数から導かれる請求項２１〜２８のいずれか一項に記載の方法。
【請求項３０】
上記少なくとも１つのデジタルフィルタは、複数の異なるスケーリングにおいて上記画像に適用されて、フィルタリングされた複数の画像を生成する請求項２１〜２９のいずれか一項に記載の方法。
【請求項３１】
関心点は、フィルタリングされた画像の領域を含む近傍内において、上記測度の局所極値として決定される請求項２１〜３０のいずれか一項に記載の方法。
【請求項３２】
上記近傍は、画像ピラミッド内に論理的に配置された、フィルタリングされた複数の画像のうち少なくとも３つによって規定される空間である請求項３１に記載の方法。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
〔本発明の分野〕
本発明は、方法および装置に関し、特に画像に作用するコンピュータベースのシステム、特に複数の異なるスケールにおいて複数の異なる回転下において機能する関心点検出および／または記述、例えばスケール不変および回転不変である関心点検出および／または記述に関する方法および装置に関する。本発明はさらに、同一画像内あるいは複数の異なる画像内において関心点をマッチングする装置および方法に関する。本発明はさらに、本発明の方法を実施するソフトウェアに関する。本発明はさらに、フィルタリングされた複数の画像を生成する複数のフィルタリング動作によって生成されるデータ構造に関し、また、例えばメモリ内に記憶またはネットワークを介して転送された、フィルタリングされた複数の画像そのものに関する。本発明はさらに、１つ以上の画像内の関心点の記述子を含むデータ構造であって、例えばメモリ内に記憶またはネットワークを介して転送され、さらに必要に応じて上記のような記述子を、原画または原画から生じる画像（例えばサムネイル画像）に関連付けるデータ構造に関する。
【０００２】
〔技術的背景〕
同一のシーンまたは物体の２つの画像間における対応（correspondence）を探すタスクは、多くのコンピュータビジョンアプリケーションの一部である。カメラ較正、３Ｄ再構成（すなわち、立体的に関連していない連続した２Ｄ画像から３Ｄ画像を取得する）、画像レジストレーション、および物体認識は少数である。離散的画像の対応の検索は、３つの主な工程に分割することができる。まず、画像内の特徴的な位置において「関心点」が選択される。関心点検出器の最も有益な特性は、その再現性、すなわち、異なる視認条件下において同一の関心点を確実に検出することができる点にある。次に、全関心点の近傍が記述子によって示される。当該記述子は、特徴的でなければならないと同時に、ノイズ、検出誤差、構造的な変形、および光度的な変形（photometric deformation）に強くなければならない。そして最後に、上記記述子が、異なる画像間においてマッチングされる。このマッチング工程は、ベクトル間の距離（例えば、マハラノビス距離またはユークリッド距離）に基づいて行われる場合が多い。
【０００３】
今日まで、様々な検出器および記述子が文献において提案されている（例えば〔１〜６〕）。また、ベンチマークデータセットの詳細な比較および評価が行われている〔７〜９〕。
【０００４】
最も幅広く用いられている関心点検出器は、おそらく、１９８８年に提案されたハリスコーナー検出器（Harris corner detector）〔１０〕であり、また二次モーメント行列の固有値に基づいている。しかし、ハリスコーナーはスケール不変ではない。〔１〕では、Lindebergが、自動スケール選択の概念を導入している。これにより、画像における関心点の検出を、それぞれ自身の特性スケールと共に行うことができる。Lindebergは、ブロブ様構造を検出するために、ヘッセ行列およびラプラシアン（ヘッセ行列のトレースに対応している）の行列式を経験した。MikolajczykおよびSchmiｄは上記方法を改良して、強く、スケール不変で、高い再現性を有する特徴検出器を生み出し、これにハリス−ラプラス（Harris−Laplace）およびヘッセ−ラプラス（Hessian−Laplace）という名称を与えた〔１１〕。彼らはスケール調節されたハリス測度またはヘッセ行列の行列式を用いて位置を選択し、ラプラシアンを用いてスケール選択した。Loweは速度に焦点を置き、ガウシアン差分（Difference of Gaussians; DoG）フィルタによってラプラシアン・ガウシアン（Laplacian of Gaussians; LoG）を近似することを提案した〔１２〕。また、スケール不変であるその他いくつかの関心点検出器が提案されている。このような例としては、KadirおよびBradyによって提案された、領域内のエントロピーを最大化する突起領域検出器〔１３〕、および、Jurieらによって提案されたエッジベースの領域検出器〔１４〕が挙げられる。しかしこれらの検出器は、加速にあまり対応していないと思われる。また、より広い視認点の変化に対処できるアフィン不変特徴検出器がいくつか提案されている。
【０００５】
さらに幅広い種類の特徴記述子が提案されている。これらは、例えばガウシアン微分〔１６〕、モーメント不変量〔１７〕、複合特徴〔１８、１９〕、可操舵フィルタ〔２０〕、位相ベースの局所特徴〔２１〕、および関心点付近におけるより小さいスケール特徴の分布を示す記述子である。ローによって提案された後者〔２〕は、他より優れていることが明らかになっている〔７〕。これは、記述子が、空間強度パターンに関する相当量の情報を取り込むと同時に、微小な変形または局所化誤差に対して強いという事実によって説明することができる。〔２〕で提案されている記述子は、略してＳＩＦＴと称され、関心点の周囲において局所配向された勾配のヒストグラムを計算し、そして１２８次元ベクトル内のビン（各４×４位置ビンに対して８配向ビン）を記憶する。
【０００６】
この基本的なスキームに様々な改良を加えることが提案されている。KeおよびSukthankar〔２２〕は、勾配画像にＰＣＡを適用した。このＰＣＡ−ＳＩＦＴは、マッチングが速い３６次元記述子を生み出すが、Mikolajczykらによる第２の比較研究におけるＳＩＦＴよりも特徴的ではないことが証明されている。〔８〕、およびこれより遅い特徴計算は、高速な照合の効果を低減させる。著書らは、同論文〔８〕において、ＧＬＯＨと称されるＳＩＦＴの変量（variant）を提案している。これは、同次元数でさらに特徴的であることが証明されている。しかしＧＬＯＨは、データ圧縮に再びＰＣＡを用いるため、計算に掛かるコストが高くなる。実用的な記述子としては、ＳＩＦＴ記述子が依然として最も魅力的であると考えられており、今日において最も幅広く用いられている。ＳＩＦＴ記述子は、特徴的であると共に比較的早く、これはオンラインアプリケーションにおいて非常に重要である。近年、Seら〔４〕は、フィールド・プログラマブル・ゲート・アレイ（Field Programmable Gate Array; ＦＰＧＡ）においてＳＩＦＴを実施し、その速度を大幅に改善した。しかし、高次元の記述子は、マッチング工程においてＳＩＦＴの欠点となる。
【０００７】
オンラインアプリケーションでは、上記３つの各工程（検出、記述、マッチング）は迅速に行われなければならない。Loweは、マッチング工程の速度を上げるために、最適ビンを最優先する代替案を提案した〔２〕が、当該案では精度が低下する。
【０００８】
〔本発明の概要〕
本発明は、画像を動作させる代替的または改良された方法および装置を提供することを目的とし、特に、複数の異なるスケールおよび複数の異なる回転で機能する関心点検出および／または記述、例えば、スケール不変および回転不変の関心点検出および／または記述のための方法および装置を提供することを目的とする。本発明は、同一画像内または複数の異なる画像内において関心点をマッチングする、改良されたまたは代替的な装置および方法を提供することができる。本発明は、本発明の方法を実施する代替的または改良されたソフトウェアを提供することができる。本発明は、フィルタリングされた複数の画像を生成する複数のフィルタリング動作によって生成される代替的または改良されたデータ構造を提供することができ、さらに、例えばメモリ内に記憶またはネットワークを介して転送された、フィルタリングされた画像そのものを記憶するためのデータ構造を提供することができる。本発明は、例えばメモリ内に記憶またはネットワークを介して転送された画像内の関心点の記述子を含む代替的または改良されたデータ構造を提供することができ、さらに、そのような記述子を、原画または原画から生じた画像（例えばサムネイル画像）に関連付けるデータ構造を提供することができる。
【０００９】
本発明は、特に、複数の異なるスケールおよび／または回転で機能するのに適した複数の画素を有する画像内における関心点を決定する方法を提供する。これは例えば、画像内において関心点を自動的に決定する、コンピュータベースの方法である。当該方法は、少なくとも１つのデジタルフィルタを用いて上記画像をフィルタリングする工程と、当該少なくとも１つのデジタルフィルタの適用の結果得られる測度の決定に基づいて関心点を選択する工程とを含んでおり、上記測度は、上記少なくとも１つのデジタルフィルタリングの出力の非線形の組み合わせであり、上記測度は、２つ以上の次元または方向における画像パラメータの変化量を取り込み、上記少なくとも１つのデジタルフィルタは、複数のボックスフィルタの組み合わせであり、少なくとも１つのボックスフィルタは、一画素よりも大きい空間範囲を有している。
【００１０】
上記少なくとも１つのデジタルフィルタの画像への適用は、積分画像を用いて行うことができる。
【００１１】
本発明はさらに、複数の異なるスケールおよび／または回転で機能するのに適した複数の画素を有する画像内における関心点を決定する方法を提供する。当該方法は、少なくとも１つのデジタルフィルタを用いて上記画像をフィルタリングする工程と、上記少なくとも１つのデジタルフィルタの適用の結果得られる測度の決定に基づいて関心点を選択する工程とを含んでおり、上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせであり、上記少なくとも１つのデジタルフィルタの上記適用は、積分画像を用いる。
【００１２】
上記少なくとも１つのデジタルフィルタは、複数のボックスフィルタの組み合わせであってよく、少なくとも１つのボックスフィルタは、一画素よりも大きい空間範囲を有している。ボックスフィルタの上記組み合わせは、２つ以上の方向において、平滑化フィルタの微分係数を近似することができる。
【００１３】
異なるスケールにおけるフィルタリングされた複数の画像は、上記少なくとも１つのデジタルフィルタを用いて提供することができる。
【００１４】
測度は、少なくとも１つのフィルタを適用した結果によって構成されるヘッセ行列（例えばヘッセ行列の行列式）に関連する値であってよい。
【００１５】
上記少なくとも１つのフィルタの適用は、複数のフィルタ（例えば、少なくとも３つのデジタルフィルタ）の適用を含んでいる。
【００１６】
上記少なくとも１つのデジタルフィルタは、平滑化フィルタの２階微分係数（例えばガウス）から導くことができる。上記デジタルフィルタは、例えば二次ガウスまたはガボールフィルタ（Gabor filter）などの帯域通過フィルタであってよい。
【００１７】
上記少なくとも１つのデジタルフィルタは、異なるスケーリングで画像に適用することができ、これによって、フィルタリングされた複数の画像を生成することができる。
【００１８】
関心点は、フィルタリングされた画像の領域を含む近傍内における測度の局所極値（local extreme value）として決定することができる。上記近傍は、画像ピラミッド内に論理的に配置されたフィルタリングされた複数の画像のうちの少なくとも３つによって規定された空間であってよい。
【００１９】
複数の画像は、一旦生成されると、メモリ内に記憶させることができる。本発明は、本発明の方法によって生成された複数の画像を記憶するメモリ内のデータ構造を含んでいる。本発明はまた、メモリ内に記憶され、本発明の方法によって生成された関心点にメモリ内において関連する画像を含んでいる。
【００２０】
本発明はさらに、複数の画素を有する画像内における、関心点の記述子を導出する方法を示しており、上記方法は、上記関心点の上記向きと整列していると共に１セットの画素を含んでいる、上記関心点周囲の近傍を識別する工程と、上記関心点の上記近傍におけるコントラストを、上記向きに対して固定関係（fixed relation）を有している少なくとも１つの方向において、少なくとも１つのデジタルフィルタを用いて調べ、これによって、各方向に対して独立して第１のスカラーコントラスト測度を生成する工程と、第１の要素を含む多次元記述子を生成する工程とを含んでおり、各第１の要素は、１つの方向のみからの上記第１のスカラーコントラスト測度の組み合わせである、第２のスカラーコントラスト測度である。
【００２１】
本発明はさらに、複数の画素を有する画像内における、当該画像内における位置および向きを有する関心点の記述子を導出する方法を示しており、当該方法は、上記関心点の上記向きと整列していると共に１セットの画素を含んでいる、上記関心点周囲の近傍内における領域を識別する工程と、上記領域のタイルを調べ、そして各タイルに対して、少なくとも１つのデジタルフィルタを用いてコントラスト関連の応答を生成する工程と、少なくとも２つの直交方向への上記少なくとも１つのデジタルフィルタの適用からの応答値を合計して、合計された値を生成する工程と、合計された上記値に基づく第１の要素を有する多次元記述子を生成する工程とを含んでいる。
【００２２】
本発明に係る記述子は、関心点におけるラプラシアンの符号である第２の要素を含んでいてよい。
【００２３】
コントラスト応答を抽出する上記少なくとも１つのデジタルフィルタは、ハールウェーブレットフィルタ（Haar wavelet filter）、あるいはその他のウェーブレットフィルタ、あるいはガボールフィルタ等であってよい。
【００２４】
上記記述子の上記第１の要素は、少なくとも２つの方向への上記少なくとも１つのデジタルフィルタの適用の結果得られる、合計された絶対値に基づいていてよい。
【００２５】
本発明はさらに、複数の画素を有する画像内における関心点の記述子を導出する方法を提供するものであり、上記関心点は、上記画像内における位置および向きを有しており、且つ上記関心点の上記向きと整列していると共に１セットの画素を含んでいる近傍を有している。当該方法は、上記関心点の上記近傍におけるコントラストを、少なくとも１つのデジタルフィルタを用いて検査する工程と、上記少なくとも１つのデジタルフィルタの上記適用の上記結果およびこれらの結果の絶対値に基づいて、多次元記述子を生成する工程とを含んでいる。
【００２６】
本発明はさらに、複数の画素を有する画像内における、位置を有する関心点の向きを割り当てる方法を含んでいる。当該方法は、上記関心点を取り囲む領域を識別する工程と、、上記関心点の向きを決定する工程とを含んでいる。上記関心点の向きを決定する当該工程は、上記領域の複数の画素を含む複数のタイルを調べ、各タイルに対して、２つの方向におけるコントラストに関連するフィルタリングされた値を決定し、これによって、当該タイルの向きおよび当該向きの大きさを決定し、そして決定された最大の上記向きを選択することによって上記関心点に向きを割り当てることによって行われる。
【００２７】
メモリ内に複数の記述子を記憶させて、例えばこれらを用いて、アーカイブした画像を検索することができる。補助するため、複数の記述子は、画像または複数の画像に関連するメモリ内に記憶することができる。
【００２８】
本発明は、複数の異なるスケールおよび／または回転で機能するのに適した複数の画素を有する画像内における関心点を決定する、コンピュータベースのシステムを提供するものであり、当該コンピュータベースのシステムは、少なくとも１つのデジタルフィルタを用いて上記画像をフィルタリングする手段と、上記少なくとも１つのデジタルフィルタの適用の結果得られる測度の決定に基づいて関心点を選択する手段とを含んでおり、上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせであり、上記測度は、２つ以上の次元または方向における画像パラメータのを取り込み、上記少なくとも１つのデジタルフィルタは、複数のボックスフィルタの組み合わせであり、少なくとも１つのボックスフィルタは、一画素よりも大きい空間範囲を有している。
【００２９】
フィルタリングする上記手段は、積分画像を用いて上記少なくとも１つのパスフィルタを画像へ適用するように構成することができる。
【００３０】
本発明はさらに、複数の異なるスケールおよび／または回転で機能するのに適した複数の画素を有する画像内における関心点を決定する、コンピュータベースのシステムを提供するものであり、当該コンピュータベースのシステムは、少なくとも１つのデジタルフィルタを用いて上記画像をフィルタリングする手段と、上記少なくとも１つのデジタルフィルタの適用の結果得られる測度の決定に基づいて関心点を選択する手段とを含んでおり、上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせであり、上記少なくとも１つのデジタルフィルタの適用を選択する上記手段は、積分画像を用いる。
【００３１】
上記少なくとも１つのデジタルフィルタは、好ましくは、複数のボックスフィルタの組み合わせであり、少なくとも１つのボックスフィルタは、一画素よりも大きい空間範囲を有している。複数のボックスフィルタの上記組み合わせは、２つ以上の方向において、ガウスフィルタなどの平滑化フィルタの微分係数を近似することができる。
【００３２】
フィルタリングする上記手段は、フィルタリングされた複数の画像を、複数の異なるスケールにおいて、上記少なくとも１つのデジタルフィルタを用いて提供することができる。
【００３３】
用いられる上記測度は、上記少なくとも１つのフィルタを適用した上記結果から構成されたヘッセ行列の行列式であってよい。
【００３４】
フィルタリングする上記手段は、３つ以上のフィルタを適用することができ、例えば少なくとも３つまたはそれ以上のデジタルフィルタを適用することができる。
【００３５】
上記少なくとも１つのデジタルフィルタは、ガウスなどの平滑化フィルタの２階微分係数から導かれることが好ましい。
【００３６】
関心点は、フィルタリングされた画像の領域を含む近傍内における測度の局所極値として決定すると都合が良い。上記近傍は、画像ピラミッド内に論理的に配置された、フィルタリングされた複数の画像のうちの少なくとも３つによって規定することができる。
【００３７】
生成された上記複数の画像および／または関心点を記憶する、メモリを設けることができる。
【００３８】
本発明は、複数の画素を有する画像内における関心点の記述子を導くシステムを提供するものであり、上記関心点は、上記画像内における位置および向きを有しており、上記システムは、上記関心点周囲において、上記関心点の上記向きと整列していると共に１セットの画素を含んでいる近傍を識別する手段と、上記関心点の当該近傍におけるコントラストを、上記向きに対して固定関係を有している少なくとも１つの方向において、少なくとも１つのデジタルフィルタを用いて検査し、これによって、各方向に対して独立して第１のスカラーコントラスト測度を生成する手段と、第１の要素を含む多次元記述子を生成する手段とを含んでおり、各第１の要素は、１つの方向のみからの上記第１のスカラーコントラスト測度の組み合わせである、第２のスカラーコントラスト測度である。
【００３９】
本発明はさらに、複数の画素を有する画像内における関心点の記述子を導出するシステムを提供するものであり、上記関心点は、上記画像内における位置および向きを有しており、上記システムは、上記関心点周囲の近傍内において、上記関心点の上記向きと整列していると共に１セットの画素を含んでいる一領域を識別する手段と、当該領域のタイルを調べ、そして各タイルに対して、少なくとも１つのデジタルフィルタを用いてコントラスト関連の応答を生成する手段と、少なくとも２つの方向への上記少なくとも１つのデジタルフィルタの適用から得られる応答値を合計して、合計された値を生成する手段と、合計された当該値に基づく第１の要素を有する多次元記述子を生成する手段とを含んでいる。
【００４０】
本発明に係る記述子は、関心点におけるラプラシアンの符号である第２の要素など、他の要素を含んでいてよい。
【００４１】
コントラストに関連する情報を得るために用いられる上記少なくとも１つのデジタルフィルタは、ハールウェーブレットフィルタであってよい。
【００４２】
本発明に係る記述子は、少なくとも２つの方向への上記少なくとも１つのデジタルフィルタの適用結果から得られる合計された絶対値に基づいていてよい。
【００４３】
本発明は、複数の画素を有する画像内における関心点の記述子を導出するシステムを提供するものであり、上記関心点は、上記画像内における位置および向きを有しており、且つ上記関心点の上記向きと整列していると共に１セットの画素を含んでいる、上記関心点の周囲に規定された近傍を有しており、上記システムは、上記関心点の上記近傍におけるコントラストを、少なくとも１つのデジタルフィルタを用いて検査する手段と、第１の要素を有する多次元記述子を生成する手段とを含んでおり、上記第１の要素は、上記少なくとも１つのデジタルフィルタの上記適用の上記結果およびこれらの結果の絶対値に基づいている。
【００４４】
本発明はさらに、複数の画素を有する画像内における、位置を有する関心点の向きを割り当てるシステムを提供し、当該システムは、上記関心点を取り囲む領域を識別する手段と、向きを決定する手段とを含んでおり、向きを決定する当該手段は、上記領域の複数の画素を含む複数のタイルを調べる手段と、各タイルに対して、２つの方向におけるコントラストに関連するフィルタリングされた値を決定し、これによって当該タイルの向きおよび当該向きの大きさを決定する手段と、決定された最大の上記向きを選択することによって、上記関心点への向きを割り当てる手段とを含んでいる。各タイルの頂点は、上記関心点に位置していてよい。
【００４５】
上記関心点の周囲に、１セットの画素を含んだ第２の近傍を整列させる手段を、上記関心点の割り当てられた向きと共に備えることができ、上記関心点の近傍内におけるコントラストを検査する手段は、少なくとも１つのデジタルフィルタを用いて記述子を生成する。
【００４６】
本発明は、コンピュータシステム上において実行された際に本発明に係る任意の方法または本発明に係る任意の画像またはシステムを実施するソフトウェアコードを含んだ、コンピュータプログラムを提供する。当該コンピュータプログラムを記憶させるために、記憶媒体を読み出し可能なコンピュータを設けることができる。
【００４７】
本発明の目的は、その性能を犠牲にすることなく、それぞれ（または両方）を迅速に計算することのできる、検出器および／または記述子を開発することにある。本発明は、関心点検出および／または記述を、個々に、または組み合わせて提供する。本発明はさらに、１つの画像内において関心点のマッチングを行い、他の画像内にこれと同一の関心点を供給することができる。例えば、第１の画像からの関心点の記述子を、第２の画像または同一画像の関心点の記述子を用いてマッチングして、上記第１および第２の画像内における同一の関心点を識別するか、あるいは一方の画像において最も特徴的な関心点を識別する。
【００４８】
本発明はさらに、本発明の方法を実施するソフトウェアを提供する。本発明はさらに、フィルタリングされた複数の画像を生成する複数のフィルタリング動作によって生成されるデータ構造、および、メモリ内に記憶またはネットワークを介して転送されるフィルタリングされた画像そのものを提供する。
【００４９】
本発明は、記述子の低次元性と複雑性との均衡を保ちながらも、記述子を十分に特徴的に維持する。
【００５０】
本発明は、これまでに提案された方法よりも再現性、特徴性、および強さにおいて優れているという利点を提供することができ、さらに、計算および比較を迅速に行うことのできる関心点および／または記述子を提供することができる。記述子の次元は、１つの画像から別の画像内において関心点を識別するのに要する時間に直接影響を及ぼすため、次元数は少ないことが望ましい。特徴的なクラスタ化（feature clustering）に対しても、次元数は少ない方が好ましい。本発明は、特定の次元数に対して良好な水準の特徴性を有する記述子を提供する。
【００５１】
本発明の別の形態は、記述子および／または検出器を迅速に計算するために、画像畳み込みに対して積分画像を用いている。本発明のさらに別の形態は、２つ以上の次元または方向における画像パラメータの変分を取り込む測度を用いている。画像パラメータは、画素に関連する任意の画像関連の値（ilage-related value）であってよく、例えばグレースケール値、色調、距離画像の奥行き、強度等であってよい。上記測度は、画像に少なくとも１つのデジタルフィルタを適用した結果であり、上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせであってよい。上記測度は、少なくとも、近似ヘッセ行列ベースの測度であることが好ましい。このような測度は、行列式またはヘッセ行列のラプラシアンであってよい。本発明の別の形態は、２つ以上の方向において平滑化フィルタの微分係数を近似する少なくとも１つのデジタルフィルタの使用である。例えば、上記少なくとも１つのデジタルフィルタは、複数のボックスフィルタの組み合わせによって、２つ以上の方向において平滑化フィルタの微分係数を近似する。少なくとも１つのボックスフィルタは、複数のボックスフィルタの組み合わせを有しており、少なくとも１つのボックスフィルタは、一画素よりも大きい空間範囲を有している。本発明の別の形態は、例えばガウスまたはガボールフィルタの近似された２階微分係数に基づくデジタル帯域通過フィルタの使用である。本発明のさらに別の形態は、分布（distribution）ベースの記述子である。本発明の別の形態は、例えばマッチング工程の速度を上げるための、（例えばラプラシアンの符号を用いた）記述子内の関心点のコントラストのタイプの使用である。別の形態は、スケール空間の複数の連続した区域または容量を調べることによる、関心点の向きの割り当てである。本発明の別の形態は、符号付き（有向）画像コントラスト値の和に基づく関心点のための記述子である。
【００５２】
〔図面の簡単な説明〕
図１は、本発明の実施形態と共に用いることのできる積分画像の演算方法を示す図である。Ａ、Ｂ、Ｃ、およびＤは、始点（最上部左方の角）から表示点に及ぶ直立長方形内の全ての値の和である。
【００５３】
図２Ａおよび図２Ｂは、本発明の一実施形態に係る、それぞれｙ方向およびｘｙ方向におけるガウスの２階偏微分を示す離散化およびクロップされたデジタルフィルタを示す図であり、グレーの値はゼロを示し、暗い値は負であり、明るい値は正である。
【００５４】
図２Ｃ、図２Ｄ、および図２Ｅは、本発明の一実施形態に係る、それぞれｙ方向、ｘｙ方向、およびｘ方向におけるガウスの２階偏微分の近似を示す離散化およびクロップされたデジタルフィルタを示す図である。グレーの領域では、フィルタ値はゼロと等しい。
【００５５】
図３は、本発明の実施形態と共に用いることのできる画像ピラミッドの概略図である。
【００５６】
図４Ａは、デジタルフィルタサイズを拡大し、それを初期入力画像へ適用することによってスケール空間が解析される、本発明の一実施形態を示す図である。
【００５７】
図４Ｂは、ヘッセ行列の近似行列式などの測度の最大が決定される、画像内およびスケール全体における局所近傍の詳細を示す図である。
【００５８】
図５は、コントラストを見つけるために本発明の一実施形態において用いられる、コントラストに関連したハールウェーブレットデジタルフィルタを示す図である。用いられるウェーブレットのサイズは、抽出工程の２倍である。
【００５９】
図６Ａは、本発明の一実施形態において、再現可能な向きを決定するために用いられる画像の関心点周囲の離散的円形区域を示す図である。図６Ａは、各サンプルに対して計算されたｘ方向およびｙ方向におけるウェーブレット応答を示している。
【００６０】
図６Ｂは、本発明の一実施形態において、ウィンドウのための代表ベクトルがいかに得られるかを示す図である。ｘ方向およびｙ方向におけるウェーブレット応答が点として共に示されている図であり、これらの応答は、それぞれ、そのｘ座標およびｙ座標として示されている。ベクトルは、これらの応答に係数で重みを付けた後、ｘ方向およびｙ方向にウェーブレット応答を追加することによって、ウィンドウ内の全ての点から生じる。上記係数は、関心点に中心がある適切な重み関数（例えばガウス）によって決定されるため、ウェーブレット応答が測定される点が関心点からより多く除去されるとより小さくなる。ｘ方向およびｙ方向における重み付き応答のこれらの和は、それぞれ、ベクトルのｘ成分およびｙ成分を生み出す。このようなウィンドウの一部は、異なる向きで構成されている。最大のベクトルを生み出すウィンドウのためのベクトルの向きは、関心点の再現可能な向きであると見なされる。
【００６１】
図７は、本発明の一実施形態において、正方形領域が割り当てられた向きにどのように整列されるか、および、この向きに従ってウェーブレット応答がどのように計算されるかを示す図である。さらに、これらの応答およびその絶対値は別々に合計され、各細分に対して４次元ベクトルが生じる。
【００６２】
図８は、画像内の異なる強度パターンに対する、本発明の実施形態に係る記述子の性質を示す図である。同次領域では、記述子の全ての成分（entrry）は比較的低いままである（図８Ａ）。高周波（図８Ｂ）では、ウェーブレット応答の絶対値の和は周波数方向において高いが、正則和（regular sum）は低いままである。強度が漸次的に変化している領域では、ウェーブレット応答の絶対値の和および正則和が共に、漸次的変化の方向に対して比較的高い（図８Ｃ）。この結果、関心点の近傍の強度パターンが特徴的に記述される。これは、上記の組み合わせである場合が多い。
【００６３】
図９は、本発明の一実施形態に従って、ラプラシアンの符号を必要に応じて用いて、明るい背景上の暗いブロブを、逆の状況から区別することができることを示す図である。同一種のコントラストを有する関心点のみがマッチング工程において用いられるため、マッチング時間を早めることができる。
【００６４】
図１０は、本発明に係る方法と公知の方法との実験結果のコントラストを示す図である。「ＳＵＲＦ」は、本発明のアプリケーションを示している。ＳＵＲＦ３７は、用いられる記述子の次元数、すなわち３７を示しており、ＳＵＲＦ６５，１２９も同様である。
【００６５】
図１１は、本発明と共に用いることのできる、入力画像を取り込むデジタルカメラを備えた一般的なコンピュータシステムを示す図である。画像は、関心点が検出される計算ユニットへ転送されて、記述子を用いてマッチングされる。図１２は、本発明と共に用いることのできるシステムの一実施例として具体的な計算システムを示す図である。
【００６６】
〔実施形態の説明〕
本発明について、具体的な実施形態および特定の図面を参照しながら説明する。しかし、本発明はこれらに限定されるものではなく、特許請求の範囲のみよって限定される。示されている図面は単なる概略図であって、限定的なものではない。これらの図面では、一部の構成要素のサイズは、例示目的のために誇張されており、相対的な縮尺とはなっていない。また、寸法および相対寸法は、本発明を実施するための実際の縮尺とは対応していない。
【００６７】
また、説明および特許請求の範囲において用いられている第１、第２、および第３等の表現は、同様の構成要素を区別するために用いられているのであって、必ずしも連続的または時間的な序列を示すものではない。このように用いられている表現は、適切な状況下においては置き換え可能であり、本明細書に記載されている本発明の実施形態は、本明細書において説明および図示されている順番以外の順番でも実施することができることについて理解されたい。
【００６８】
また、特許請求の範囲において用いられている「含んでいる」という表現は、その前に列挙されている手段のみに限定されるものと解釈されるべきではなく、他の要素または工程を除外するものではない点に留意されたい。従って上記表現は、記載されている特徴、整数、工程、または成分の記載通りの存在を特定するものであると解釈されるべきであり、１つ以上の他の特徴、整数、工程、成分、あるいはこれらから成る群の存在または追加を除外するものではない。従って、「手段ＡおよびＢを含んでいるデバイス」という表現の範囲は、部品ＡおよびＢのみから成るデバイスのみに限定されるべきではない。本発明に関しては、そのデバイスの単なる関連部品がＡおよびＢである。
【００６９】
本発明は、画素（画像素子）の縦列および横列に論理的に組織化されているものと説明される、デジタル画像の処理に関する。「論理的に組織化されている」とは、各画素が、横列および縦列を介して（例えば、ｘ方向およびｙ方向に沿って）アドレスされることを意味している。しかし、これら画素の横列および縦列は、物理的にデカルトアレイを成していなくてよく、例えば極画像（polar image）を成していてよい。極画像である場合は、本発明を極画像に直接適用することができるか、あるいは、デジタルフィルタ生成の際にデカルト座標／極座標間の変換を尊重することができる。画像がいかなる形態であろうとも、画像の画素は、個々にアドレスおよび操作することができるものと仮定する。本発明は、主に２Ｄ画像を参照しながら説明するが、３Ｄベタ画像あるいは時空間的領域（映像）にも拡大することができる。また本発明は、主にグレースケール画像、黒色画像、または白色画像を参照しながら説明するが、これらに限定されるものではない。本発明はまた、カラー画像にも適用される。カラー画像は、通常は、例えば３つ（例えば赤、緑、青またはシアン、マゼンタ、黄）または４つ（例えばシアン、マゼンタ、黄、および黒）など、多数の色分解から成る。画像内における異なる色分解は、別々のカラーチャンネルとして説明される場合もある。本発明をカラー画像に適用する方法は多数ある。本発明を適用する１つの方法として、カラー画像をグレースケール画像に変更し、本発明をその画像に適用する方法がある。本発明を適用する別の方法としては、単一の色分解またはカラーチャンネルを用いる方法がある。別の方法としては、画素値を全ての色分解またはチャネルと組み合わせて（例えば追加して、または、その他の組み合わせを行って）、単一の平均値または各画素の全値を得る方法がある。
【００７０】
本発明は、画像の「画素」を参照する。この用語は、表示される画像要素の形態（例えば光度、色調等）を表す値を有する画像内における位置に関連している。本発明において用いられる画像は、いずれの時点においてもアップサンプルまたはダウンサンプルすることができる。従って、「サンプル」という用語は、表示されるか否かに関わらず本発明において用いられる画像のあらゆる個別部分に適用することができる。従って「画素」という用語は、本願および特許請求の範囲におけるあらゆる部分において、「サンプル」と置き換えることができる。
【００７１】
本発明は、複数の異なるスケールおよび／または回転において機能するのに適した複数の画素を有する画像内において、関心点を決定する検出器を提供し、これによって上記画像が少なくとも１つのデジタルフィルタを用いてフィルタリングされ、そして上記少なくとも１つのデジタルフィルタのアプリケーションから生じる測度の決定に基づいて関心点が選択される。上記測度は、上記少なくとも１つのデジタルフィルタの出力の非線形の組み合わせである。上記少なくとも１つのデジタルフィルタは、２つ以上の方向において、平滑化フィルタの微分係数を近似する。上記測度は、２つ以上の次元または方向において、画像パラメータの変化量を取り込む。当該画像パラメータは、画像の画素に割り当てられる任意の適切な値（例えば強度、グレースケール値、色調、距離画像の奥行き値等）であってよい。
【００７２】
上記検出器は、ヘッセベースの検出器であることが好ましいが、本発明はこれに限定されるものではない。ヘッセベースの検出器は、ハリスベースの検出器よりも安定性および再現性に優れている。上記測度は、ヘッセ行列（例えば、行列式またはトレース、あるいはこれら２つの組み合わせ）から誘導される任意の適切な測度であってよい。そのトレースではなくヘッセ行列の行列式（すなわちラプラシアン）を用いることによって、細長く局所不良化した構造へのファイヤが少なくなるため有利である。
【００７３】
本発明の上記方法は、３つの独立したスタンドアロン工程を有している。これらの工程は、任意に組み合わせることができ、あるいは他の方法と共に独立して用いることもできる。まず、画像にデジタルフィルタリングを掛けることによって、画像内の特徴的な位置において「関心点」が選択される。関心点は、例えばコーナー、ブロブ、およびＴ分岐であってよい。次に、全関心点の近傍が、例えば特徴ベクトルである記述子によって表される。当該記述子は、特徴的であると同時に、ノイズ、関心点探索における誤差、構造的な変形、および光度的な変形に強い。最後に、上記記述子が、異なる画像間または同一画像内においてマッチングされる。例えば、記述子特徴ベクトルがマッチングされる。このマッチングは、記述子間の１２距離（例えば、記述子特徴ベクトル間の距離、例えば、マハラノビス距離またはユークリッド距離）に基づいていてよい。このマッチングはまた、１１距離、l∞距離、あるいは他の任意の距離測度に基づいていてよい。これらのいずれの工程も、別の他の工程と組み合わせ行うことができる。従って、本発明の記述子は、他の関心点検出器と共に用いることができ、あるいは、本発明の関心点検出器は、他の公知の記述子と共に用いることができる。
【００７４】
局所特徴に対して作業するに当たり、解説すべき第１の問題は、不変性に対して求められるレベルである。これは明らかに、構造的な変形および光度的な変形に依存している。これらの変形は、視認条件において生じ得る変化によって決定される。本発明は、異なる回転および／またはスケーリングの下で機能する、関心点検出器および／または記述子を提供する。これらは例えば、スケール不変および／または画像回転不変の検出器および／または記述子である。これらは、特徴複雑性と一般的に生じる変形に対する強さとを良好に折衷する。非対称の（skew）異方性スケーリングおよび見込まれる効果は、二次効果であると見なされる。これらは、ある程度は、記述子の総体的な強さによって補填される。光度的な変形に関しては、本発明は、バイアス（オフセット）およびコントラスト変化（スケール係数）を有する単純線形モデルであると見なす。上記検出器および／または記述子は、グレースケール画像を用い、カラーを用いる必要はない。
【００７５】
以下では、本発明の一形態に係る検出器について、フィルタが掛けられた１つ以上の画像のヘッセ行列、特にヘッセ行列の行列式の使用に基づいて説明する。これは、複雑性を低減するために近似されることが好ましい。演算時間を短縮するために、積分画像が用いられることが好ましい。
【００７６】
本発明に係る記述子は、関心点近傍内におけるコントラスト情報の分布を記述する。当該記述子は、画像の縦列および横列と同一の方向である必要はない２つの方向（例えば２つの直交方向）におけるコントラストの分布に直接機能する。当該記述子は、スカラーコントラスト測度（scalar contrast measure）を利用する。当該スカラーコントラスト測度は、画像パラメータと画像の近傍区域（例えば、画素または画素群）とを比較することによって得られる。コントラストは、画像パラメータ内における変化であり、例えば強度、あるいは画像の画素に割り当てられた任意の他の値である。これらのスカラーコントラスト測度の組み合わせを形成することによって、上記記述子の要素が生成される。
【００７７】
上記方法は、必要に応じて、速度を高めるために積分画像を用い、また好ましくは、上記記述子に対して用いる次元数を例えば３０〜１５０に限定する。これによって、比較的小さいままであるにも関わらず強く特徴的であり、従って、同様に特徴的な最新の記述子よりもマッチングが速く、且つ集積化（clustering）により適した記述子が生み出される。本発明の範囲内には、上記よりも高い次元数が含まれている。しかし、より高い次元を用いることによって、視認点または視認条件が変化した場合にマッチング率を低下させる危険性のある近傍が優決定される可能性がある。
【００７８】
本発明はまた、ラプラシアン（例えばラプラシアンの符号）に基づいた指標付け（indexing）を用い、これによって記述子の強さのみならずマッチング速度を高めることができる。異なるコントラスト型の積分画像の関心点を区別できるのであれば、他の測度を用いることもできる。
【００７９】
積分画像
本発明の一形態は、例えば〔２３〕において規定されており、図１に概略的に示されている、積分画像を用いることである。これらの積分画像によって、ボックスタイプ畳み込みフィルタを迅速に実施することができる。本方法は本発明による方法の複数の場所において適用されるため、この時点において一度のみ説明する。開始点は、画像値がｘおよびｙ方向の複数の画素にある、少なくとも二次元であるデジタル画像Ｉである。ｘ＝（ｘ、ｙ）である位置における積分画像ＩΣ（ｘ）の成分（entry）は、原点（origin）およびｘによって形成される領域の入力画像Ｉ内における全画素の和を表している。従って、積分画像ＩΣ（ｘ）は、原点がその端点である画像領域での像点Ｉ（ｉ、ｊ）における画素値の和である。この領域は、長方形の領域であってよい。その場合は、次式の通りである：
【００８０】
【数１】
2009535680.tif 000003
（１）
積分画像が計算されると、４つの加法によって、任意の直立した長方形区域における強度の和が計算される。さらに、演算時間は、そのサイズとは無関係である。
【００８１】
積分画像について、画像の長方形部分を参照しながら説明したが、三角形または六角形など他の形状を用いることもできる。また、上記のような積分画像によって容易に処理されるように、本発明のデジタルフィルタを自身の形状に適合させることができる。
【００８２】
関心点検出
ヘッセ行列式および画像ピラミッド
まず、上記検出器について１つのスケールで説明し、続いて上記方法について複数のスケールで説明する。本発明に係る検出器は、その計算および精度における良好な性質ゆえ、ヘッセ行列に基づいている。しかし本発明は、位置およびスケールを選択するに当たり異なる測度を用いるのではなく、位置およびスケールの双方に対して、行列式またはヘッセの近似行列式（approximate determinant）に依存している。画像Ｉ内の点を点ｘ＝（ｘ、ｙ）であるとすると、スケールσにおけるｘ内のヘッセ行列Ｈ（ｘ、σ）は、次式のように定義される：
【００８３】
【数２】
2009535680.tif 000004
（２）
上記Ｌｘｘ（ｘ、σ）は、点ｘ等にデジタルフィルタを適用した結果である。添字ｘｘは、平滑化フィルタの２階微分係数の適用を示している。添字ｘｙは、第１の微分係数が一方の方向にあり、二次微分が他方の方向にある、平滑化フィルタの２階微分係数の適用を示している。基本的な平滑化フィルタは、ガウスのように鐘形であることが好ましい。鐘形とすることによって、点ｘからさらに離れた位置にある画素が、画素に割り当てられたフィルタリングされた値に与える影響が少ないという利点を有している。本発明に係る二次デジタルフィルタは、下記の特徴のうち少なくとも１つを有している：
ａ）平滑化フィルタの２階微分係数に関するデジタルフィルタである
ｂ）鐘形の２階微分係数に関するデジタルフィルタである
ｃ）ガウスの２階微分係数に基づいたフィルタである
ｄ）離散化されたフィルタである
ｅ）クロップされたフィルタである
ｆ）デジタルフィルタの離散的な部分領域によって規定されたローブ（lobe）を有している
ｇ）ボックスフィルタである
ｈ）上記部分領域のローブの形状は、「シルクハット」または「方形パルス」であってよい
ｉ）上記フィルタのうち少なくとも１つは、帯域通過フィルタである。
【００８４】
例えば、Ｌｘｘ（ｘ、σ）は、画像Ｉの点ｘにおける、ガウスの二次微分係数〔数３〕（あるいはその近似値）の畳み込み結果である。同様に、Ｌｘｙ（ｘ、σ）およびＬｙｙ（ｘ、σ）は、画像Ｉの点ｘにおける、ガウスの二次微分係数〔数４〕および〔数５〕（あるいはその近似値）の畳み込み結果である。フィルタＬｘｙ（ｘ、σ）はＬｙｘ（ｘ、σ）に関連しており、一方は他方から導き出すことができる。このため、フィルタリングされた４つの画像を生成するために画像に適用する必要があるデジタル帯域通過フィルタは３つのみである。ガウスは、スケール空間解析には最適であるが、実際には無限大であることができないため、離散化およびクロップされる必要がある。上記のような近似を行った後、図２Ａおよび図２Ｂに概略的に示されている帯域通過フィルタが得られる。各画素点におけるフィルタの値は、グレースケールで符号化されている。グレーは、値ゼロである。黒色は負の値であり、白色は正の値である。図示されているように、フィルタが各画素に対して有している値は１つのみである。すなわち、ガウスの二次微分係数などの連続関数は、画像の一画素の全区域に有効な値に離散化される。また、空間範囲は、無限大から、画素数（例えば、関心点を中心とするＭ×Ｍ画素のマスクサイズ）へと縮小されている。Ｍの値は、中心画素を提供するために奇数であることが好ましい。用いられる場合が多い値は、Ｍ＝９（９×９マスク）である。他の値としては、Ｍ＝１１、Ｍ＝１３、Ｍ＝１５等がある。従来の畳み込み方法では、このサイズは計算速度に影響を及ぼす。Ｍの値が大きいほど、そのマスクを用いた全画像の畳み込みが遅くなる。しかし、本発明の一実施形態では、積分画像を用いることによって、あらゆるフィルタサイズが一定の速度で適用される。
【００８５】
【数３】
2009535680.tif 000005
【００８６】
【数４】
2009535680.tif 000006
【００８７】
【数５】
2009535680.tif 000007
【００８８】
本来であれば、離散化およびクロップによって、画像回転下において再現性が失われるが、本発明において用いられる帯域通過フィルタは有用である。ガウスは鐘形をしており、またガウスの２階微分係数は、１つの中心ローブと、反対符号を有する２つの外部ローブとを有している。図２Ａに見られるように、微分係数がｘ方向に２回取られる、ガウスのデジタルフィルタの離散化およびクロップされた２階微分係数は、中心画素において負の値を有している、すなわち、中心画素付近において負のローブを有しており、中心画素の上下に２つのゼロ交差を形成し、そして正となる。すなわち、中心画素の上下に正のローブが１つ形成される。そして、上記フィルタはゼロとなる。すなわち、上記フィルタは、所定数の画素（例えば第４の画素）後に、中心画素から切り取られる。従って、上記デジタルフィルタは、１つの２値極性（binary polarity）の中心ローブ、２つのゼロ交差、反対の２値極性の２つの外部ローブ、および所定数の画素（例えば３つの画素）を中心画素から加算および減算した空間範囲を有している。上記ｙフィルタも同様であるが、９０°回転されている。図２Ｂには、ｘｙフィルタが概略的に示されている。中心画素は、ゼロ値などの値を有しており、（対角線に沿った）正のｘ−正のｙおよび負のｘ−負のｙ象限内に、２つの正のローブがある。また、（他の対角線に沿った）正のｘ−負のｙおよび負のｘ−正のｙ象限内に、２つの負のローブがある。上記中心画素が、ローブのうちの１つには含まれていない値を有しておらず（例えば、ボックスフィルタ）、フィルタの中心は複数のボックスフィルタの隣接し合う頂点の組み合わせによって形成されていないという事実は、図２Ｂに示されているタイプのフィルタが、図２Ａ、図２Ｃ、および図２Ｅに示されているタイプのフィルタとは異なっていることを意味している。
【００８９】
画像にデジタルフィルタを掛けるために、図２Ａおよび図２Ｂに示されているデジタルフィルタ、および図２Ａに示されているフィルタの回転されたタイプ（あるいは、図２Ｃ、図２Ｄ、および図２Ｅに示されているフィルタ。下記を参照）を用いて、その画素に中心がある各画素に対する新しい値が計算される。そしてこれを、一部または全部の画素に対して再現して、フィルタリングされた画像を生成する。値は、規則的に間隔が空けられた画素において計算することができる。ここでは、これらの画素サンプル間における段（step）が、ナイキスト抽出定理に従うように選択される。
【００９０】
本発明の別の形態では、平滑化フィルタ（例えばガウスフィルタ）の微分係数を近似して、少なくとも１つの帯域通過フィルタを形成することは、離散部分領域を有するデジタルフィルタを用いることによってさらに取られることが好ましい。これらの部分領域は、フィルタ値の離散領域であり、通常は少なくとも、中心画素の周囲に対角線を挟んで対称的に配置されており、例えば図２Ｃ、図２Ｄ、および図２Ｅに示されているように、ボックスフィルタが組み合わせられた形状をしている。これらのボックスは、１よりも大きい所定数の画素に伸びる、単一の正の値または単一の負の値のいずれかを有している。従って、鐘形のローブは、「シルクハット（シルクハット）」または「方形パルス」ローブによって置き換えられている。図２Ｃには、Ｎ個のブロック（例えば３つのブロック）があり、値は白色画素に対して＋１、黒色画素に対して−２であり、これらのフィルタはそれぞれｙおよびｘ方向に用いられる。フィルタの部分領域は、正方形または長方形のボックスとして示されているが、本発明の範囲には他の形状も含まれる。これらは例えば、二次溝付き正方形（quadratic, castellated square）または二次溝付き六角形（quadratic、castellated hexagonal）、溝付き円形（castellated circular）、三角形、六角形等である。本発明では、積分画像処理の使用を可能にする部分領域の形状が特に好ましい。複数のボックスフィルタの組み合わせは、図１に示されているタイプの積分画像の処理において特に容易である。図２Ｄでは、ｘｙフィルタは、フィルタ値（例えばゼロのフィルタ値）を有する中心画素の周囲に対称的に配置された、＋１（白色）または−１（黒色）のいずれかの値を有するＮ’個の画素ブロック（例えば４つの画素ブロック）として示されている。中心画素が、ローブのうちの１つ（例えばボックスフィルタ内）に含まれていない値を有しており、フィルタの中心はボックスフィルタの隣接し合う頂点の接合によって形成されていないという事実は、図２Ｄ（図２Ｂと同様）に示されているタイプのフィルタが、図２Ａ、図２Ｃ、および図２Ｅに示されているタイプのフィルタとは異なることを意味している。また、中心値はゼロであってよい。これは、プラスまたはマイナス１であってよいボックスフィルタの値とは異なる。従って、このフィルタは三値（−１、０、１）デジタルフィルタであり、他のフィルタは二値フィルタである。従って、本発明の一形態は、フィルタ（例えば図２Ａ〜図２Ｅに示されているフィルタ）のうち少なくとも１つは、三値フィルタであるか、あるいはより高値のフィルタ（例えば四値）である。これは、これらのデジタルフィルタのうち少なくとも１つの中心は、いずれかの側に対称的に配置されたボックスフィルタのローブのうちの１つの値ではない値を有する画素であると表現することができる。
【００９１】
本発明は、ｘおよびｙフィルタに対して３つのブロック、およびｘｙ（およびｙｘ）フィルタに対して４つのブロックに限定されるものではなく、用いられるブロック数はこれら以外であってもよい。
【００９２】
上記の説明はボックスフィルタに関するものであるが、本発明はこれに限定されるものではない。各ブロックまたはボックス内のフィルタ値は、（図２Ａおよび図２Ｂに概略的に示されているように）非整数であってもよいが、これによって積分画像を用いることができなくなる。また、フィルタ値は、ブロック内またはブロック毎に異なっていてもよい。しかし、ブロックおよび値が多いほど、フィルタの計算の負荷が高くなる。
【００９３】
図２Ｃ〜図２Ｅに示されているフィルタの一般的な特徴は以下の通りである：
ａ）ｘｙフィルタ（およびｙｘフィルタ）は、中心画素位置から対角線方向にローブを１つのみ有しており、中心画素におけるその値はゼロである。従って、対角線方向に沿って存在するローブは、一方の対角線方向におけるローブと、他方の方向におけるローブとの２つのみである。これらは、中心のゼロ値から増加して、再びゼロまで減少する。あらゆる対角線に沿った２つのローブは、同一の極性を有しており、両方とも正の値を有しているか、あるいは両方とも負の値を有している。一方の対角線方向におけるローブは、他の対角線に沿ったローブとは反対の極性を有している。
ｂ）ｘおよびｙフィルタは、中心ローブの各側にそれぞれ位置する、反対の符号を有する２つのローブと共に、中心画素に中心がある単一のローブを有しており、フィルタ方向がいずれの方向であるのかに応じてｘ軸またはｙ軸のいずれかに沿ってゼロ値まで減少する。
ｃ）全フィルタにおいて、フィルタの全フィルタ値の総和はゼロである。
ｄ）必要に応じて、フィルタ値は整数である。
ｅ）必要に応じて、一ローブのフィルタ値は全て同一であり、ローブ値の形状は「シルクハット」、すなわち長方形である。
【００９４】
近似二次ガウシアン微分に基づいており、また図２Ｃ、図２Ｄ、および図２Ｅに例示されているように複数のボックスフィルタの組み合わせを含んでいるこれらのフィルタは、サイズとは無関係に、すなわちその空間範囲とは無関係に、積分画像を用いて非常に迅速に評価することができる。その性能は、図２Ａおよび図２Ｂに示されている離散化およびクロップされたフィルタに匹敵するか、あるいはこれらよりも優れている。しかし本発明は、これらのフィルタの使用も含んでいる。複数のボックスフィルタの組み合わせは、Ｐ×Ｐ（例えば、図２Ｃおよび図２Ｄに示されているように、９×９フィルタ）の空間範囲を有しており、近似値はガウスから導き出される（例えばσ＝１．２）。ボックスフィルタのこれらの９×９の組み合わせは、スケールの最も低いフィルタとして、すなわち空間分解能の最も高いフィルタとして用いることができる。これらのフィルタは、Ｄｘｘ、Ｏｙｙ、およびＤｊｃｙで表される。Ｐの他の値としては、任意の奇数が適切である。有用な最小のフィルタサイズは９×９であるが、本発明ではこれよりも小さいフィルタを用いることができ（例えば３×３が有用である）、実際には３で割り切れる任意のフィルタサイズを用いることができる。より高いスケールでは、より大きい画像領域を網羅するためにフィルタサイズが拡大される。フィルタサイズは、理論的には、画像そのもののサイズまで拡大することができる。本発明の一実施形態では、Ｐと、全フィルタサイズの近似されたガウス関数の標準的な偏差との比率は一定である。この比率は、例えば７．５（９／１．２）に設定することができるが、１つのスケール分析に対して一定であるのであれば、異なる値の使用も検討することができる。
【００９５】
長方形領域に加えられる重みは、計算効率に対して簡素に維持することができる。ヘッセの行列式に対する式における相対的重みは、平衡されることが好ましい。これは、以下の一般式で規定される通りに行うことができる：
【００９６】
【数６】
2009535680.tif 000008
（３）
上記において、|Ｘ|Ｆはフロベニウスのノルムである。
具体的な例では、上記Ｐは９であり、σは１．２であるため、結果は下記の通りとなる：
【００９７】
【数７】
2009535680.tif 000009
【００９８】
（すなわち、約０．９）
上記において、|Ｘ|Ｆはフロベニウスのノルムである。
これによって、ヘッセの近似行列式が以下のように生み出される（方程式２を参照）：
ｄｅｔ（Ｈａｐｐｒｏｘ）＝ＤｘｘＤｙｙ−（０．９Ｄｘｙ）２            （４）
Ｐおよび／またはσの値が変わる場合、この近似公式は変わる。
【００９９】
ヘッセdet（Ｈａｐｐｒｏｘ）の近似された行列式は、画像の一部の画素または各画素（またはサンプル）に対して計算され、位置×におけるdet（Ｈａｐｐｒｏｘ）の値は、画像の位置×における関心点測度またはブロブ応答を表している。これらの応答は、ブロブ応答写像（blob response map）内に記憶される。関心点を探すためには、後述するするように、det（Ｈａｐｐｒｏｘ）の極大が検出される。
【０１００】
上記では、フィルタの１つのスケールのみについて説明した。関心点は、フィルタリングされた単一の画像内または異なるスケールにおいて見つけることができる。フィルタリングされた複数の画像を用いることが有用である。これは、異なる画像間における対応を探索する場合、異なるスケールに対応が存在する画像内において、それら対応の比較を行う必要があるからである。スケール空間は、画像ピラミッドとして実施されることが好ましい。画像ピラミッドは、概念的に互いに上下に配置された、フィルタリングされた一連の画像である。ピラミッドは底部から最上部へと横断しているため、画像は、図３に概略的に示されているように、ガウスフィルタの２階微分係数（あるいは上述のフィルタの近似値）から導き出されるフィルタなど、より大きい帯域通過フィルタによってフィルタリングされる。帯域通過フィルタは、大きいければ大きいほど、初期画像内のより低い周波数をより調べる。フィルタリングされた画像のピラミッドを形成するための方法は、様々に存在する。本発明の範囲内には、少なくとも３つの方法が含まれる。
ａ）新しい各画像は、それ以前の画像が二段抽出されたものであり、帯域通過フィルタサイズは同一に維持される。
ｂ）新しい各画像は同一のサイズを有しており、フィルタサイズは拡大している。画像は、例えば初期画像であってよく、あるいは当該画像が二段抽出またはアップサンプルされたものであってよい。
ｃ）新しい各画像は、それ以前の画像が二段抽出されたものであり、帯域通過フィルタサイズもまた拡大されている。
ピラミッドの異なる部分に対して、上記ａ）〜ｃ）を任意に組み合わせて用いることもできる。
【０１０１】
例えば同一または異なる帯域通過フィルタを用いて、例えば、それ以前にフィルタリングされた層の出力に同一のフィルタを掛けることによって、画像に繰り返しフィルタを掛けることができる。ピラミッド層を減算することによって、すなわち他方（例えば隣接する層）からピラミッド層を１つ減算することによって、エッジおよびブロブを見つけることのできるＤｏＧ画像が生み出される。ピラミッドの生成においては、最適なフィルタとしてガウス核が示されている〔２４〕。しかし実際には、ガウスを修正し、離散化およびクロップする必要がある。さらには、ガウスフィルタを用いることによって、得られる画像が二段抽出されるとすぐにエイリアシングが生じる。また、より低い分解能に向かっている間は新しい構造が生じないというような特性は、１Ｄの場合には照明されている可能性があるが、しかし関連する２Ｄの場合には当てはまらないことが知られている〔２６〕。当該分野の専門家らがこの点に関してガウスに置く理論的重要性にも関わらず、本発明の一実施形態に係る検出器は、より簡素なフィルタに基づいている。驚くことに、良好な結果が得られる。本発明は、ガウス平滑化フィルタに基づいたフィルタに限定されるものではない。
【０１０２】
従って、本発明の一実施形態は、複数のボックスフィルタを簡素に組み合わせて適用することによってスケール空間を生成し、その後スケール空間を分析することを含んでいる。これらの畳み込みフィルタは、図２を参照しながら説明したように、フィルタのボックス上の強度を合計することによって、２階平滑化フィルタの微分係数（例えば、異なるスケールにおける第２のガウシアン微分）を近似する。このでもまた、積分画像処理が用いられて、フィルタは極めて迅速に評価される。また、本発明の一実施形態は、以前にフィルタリングされた層の出力に同一のフィルタを繰り返し掛ける必要はなく、初期画像に任意のサイズ（および異なるサイズ）のフィルタを掛ける。これは、積分画像を用いることによって、サイズとは関係なく全く同一の速度で行うことができる。異なるフィルタスケールを用いた同一画像のフィルタは、必要に応じて、例えばパラレルプロセッサネットワークが用いられる場合はパラレルに行って、例えば時間を節約することができる。本実施形態では、次のスケールレベルに進むために画像サイズを縮小する必要はなく、フィルタサイズは、図４Ａに概略的に示されているように拡大される。積分画像の計算効率ゆえに、画像上のフィルタのサイズがどのようであっても、計算速度が大幅に損失することはない。従って、画像サイズを繰り返し縮小する代わりに（図３の実施形態）、フィルタサイズを拡大することが好ましい（図４Ａの実施形態）。また、異なるスケーリングのフィルタによって同一の画像が処理されるため、例えば方程式（４）によって決定される行列式の値は、その点における画素値として画像内に書き込むことができるというさらなる利点がある。従って、ボックスフィルタの作用は、各画素またはサンプルが少なくともヘッセの行列式の近似値である値を有する、新しい画像を生成することである。これらの新しい画像は、論理的に互いに上下に配置されて、スケール空間を形成する（図４Ａを参照）。従って本実施形態では、初期画像に３つの帯域通過フィルタが掛けられて、画素値のヘッセ行列の行列式の少なくとも近似値を含む新しい画像が１つ生成され、そしてこれが、フィルタの異なるスケーリングに対して繰り返されて、フィルタリングされた複数の画像が生成される。
【０１０３】
スケール空間は、オクターブに分割される。各オクターブは、２つの連続する、ますます二段抽出される画像間における間隔を示し、その長さは通常は２スケール変更分である。各オクターブは、一定数のスケールレベルに再分割される。積分画像の離散的性質ゆえに、オクターブが再分割される最大数は、一方の方向（ｘまたはｙ）における部分的な２階微分係数の正または負のローブの初期長さＬ０に依存している。図２を参照しながら説明した９×９フィルタマスクの場合、上記長さは３である。２つの連続した連続の場合、上記サイズ（またはデジタルフィルタの空間範囲）は、サブフィルタのサイズまたはデジタル帯域通過フィルタの離散部分領域（例えば、ボックスフィルタサイズ）を拡大することによって拡大することができる。例えば、サブフィルタ（すなわちボックスフィルタ）の横寸法は、Ｒ画素の最小数分、拡大される。Ｒ画素の最小数分とは、例えば、２画素（例えば、ボックスフィルタの空間範囲の各辺に１画素を加える）である。フィルタのサイズまたは空間範囲は、奇数の画素に維持されることが好ましい。図２Ｃ〜図２Ｅの完全なデジタルフィルタの横寸法の拡大の合計は、第１のスケールレベルに対して６画素である（すなわち、各ボックスフィルタは２拡大され、完全なフィルタは６画素分拡大される）。図２Ｄおよび図２Ｅのフィルタの場合、部分領域は２つのみであるが、これらもまた６拡大される（例えば、サイズは、ローブの高さと幅との比率を一定に保持するために拡大される）。
【０１０４】
本発明は、例えば第１のスケールレベルの分析に用いるフィルタマスクサイズに応じて、どのようにスケール分析を行うかに関して様々な態様を含んでいる。以下に、２つの例を挙げて説明する。本発明は、これら２つの例に限定されるものではない。最も簡素で計算が最も速いフィルタとして、図２の９×９フィルタから開始し、（上述のヘッセの近似行列式を探すことによって、）ｘおよびｙにおいて、抽出係数２を用いて第１のオクターブにおける画像のブロブ応答を計算する。次に、例えば１５×１５画素、２１×２１画素、および２７×２７画素のサイズのフィルタが適用される。この時間によって、２を超えるスケール変更が達成される。
【０１０５】
１．次のオクターブでは、関心点抽出の抽出間隔を二倍にすることができる。第２のオクターブは、別の数Ｓ分、サイズが成長するフィルタと共に機能する。例えば、複数のボックスフィルタの組み合わせは、上記オクターブ内のスケール間において横寸法が１２画素（各サブフィルタ領域またはボックスのいずれかの辺において２画素）成長する。第３のオクターブのフィルタは、別の数Ｔ（例えば２４画素）分、横寸法が成長する。第４のオクターブのフィルタは、別の数Ｔ（例えば４８画素）分、横寸法が成長する。以後、同様に成長する。Ｒ、Ｓ、Ｔ、Ｕ等の数は互いに関連しており、アプリケーションによって変更することができる。サイズの拡大は、例えば算術的、代数的、または幾何学的に行うことができる。大きいスケール変更、特に、これらのオクターブ内における第１のフィルタ間のスケール変更は（本実施例では、９から１５は１．７の変化である）、スケールの抽出が非常に粗い（crude）ことを示している。従って、代わりに、スケールがより良好に抽出されたスケール空間が達成されている。これは、まず線形補間を用いて画像サイズを二倍にし、そしてサイズ１５×１５のフィルタを用いてフィルタすることによって第１のオクターブを開始し、そして水平および垂直方向においてにおいて係数４で二段抽出する。追加的なフィルタサイズは、２１×２１、２７×２７、３３×３３、３９×３９、および４５×４５である。次に、第２のオクターブを開始する。ここでもまた、その横寸法を１２画素分拡大するフィルタを用いる。そして、第３および第４のオクターブが続いて開始される。フィルタサイズが最小入力画像サイズ（最小（幅、高さ））引く３サンプルよりも小さいかあるいは等しい値に維持されている限りは、さらなるオクターブを分析することができる。これは、少なくとも１つの非最大抑制反復を適用するためである。入力画像のサイズは、必ずしも取り込まれた画像のサイズを意味しているわけではない。関心点検出の前に、検出された画像を（より大きくまたは小さく）スケールすることができ、また必要に応じて、別の方法で平滑化または前処理して、積分画像の計算のための入力画像を生み出すことができる。ここで、２つの第１のフィルタ間におけるスケール変更は、わずか１．４である。以下では、上述したスケール空間の２つの例を「早く」また「正確な」例として参照する。これらは本発明の実施形態であるが、本発明はこれら２つのみに限定されるものではない。取り込まれた画像は、例えば補間を用いて、二倍またはより高い画像サイズへスケールすることができる。そして、より大きい初期フィルタサイズを用いて、小さいスケールにおいて詳細を損失することなく、第１のスケール変更をさらに低減することができる。例えば、画像サイズを三倍にし、２７×２７フィルタを用いると、初期画像サイズにおける９×９フィルタと同等である。次のフィルタサイズは、３３×３３である。これは、さらに良好な第１のスケール変更１．２２と対応している。本発明においては、より良好なスケーリングを用いることは必須事項ではない。全てのアプリケーションにおいて良好なスケール変更が望ましいわけではない。従って、次のフィルタサイズが９×９であるため��えばスケール変更３を用いて、半分の画像サイズにおいてより小さい初期フィルタサイズ３×３を用ることができる。
【０１０６】
関心点局所化
画像内および必要に応じてスケール上において関心点を抽出するために、画像およびスケール空間内における特定の近傍内の非極値（例えば、非最大または非最小または非最大および非最小）抑制が適用される。これについては図４Ｂを参照されたい。非極値抑制とは、ヘッセの行列式（例えば、ヘッセ行列の近似行列式）の値が各画像サンプルに対して計算され、そして各辺にＮ画素を有する（２Ｎ＋１）×（２Ｎ’＋１）×（２Ｎ"＋１）容積近傍内に極値（例えば最大および／または最小）を示しているかどうかが検査されることを意味している。Ｎ、Ｎ’、およびＮ"の値は、全て同一である必要はなく、（スケール方向における）Ｎ"はゼロであってもよい。この近傍を提供するフィルタリングされた画像の数はＮ"＋１であるため、本発明では、関心点を得るために計算される画像数はこの数のみである。
【０１０７】
上記近傍内では、画素またはサンプルは、その行列式値が、例えば、当該近傍内における他の全ての画素（またはサンプル）行列式値よりも大きいおよび／または小さい極値である場合に限り、関心点であると考えられる。つまり、このような極値（例えば最大行列式値）を有していない他の全ての画素（すなわち、非最大画素）が抑制される。非最小抑制が用いられる場合、サンプルは、ヘッセの行列式（例えばヘッセ行列の近似行列式）の最小が検査され、そして極小において関心点が選択される。全ての画素またはサンプルを考慮する必要はなく、時間を節約するために一部は考慮しなくてよい。
【０１０８】
本実施形態では、スカラーおよび空間次元が共に考慮され、非極値抑制（例えば非最大抑制および／または非最小抑制）が３次元（すなわちｘ、ｙ、およびスケール次元）に適用される。ヘッセ行列の局所的極値行列式値を有する画素またはサンプル、あるいはその近似値（すなわち、ヘッセ行列の極小または極大値、あるいはその近似値）が、関心点であると考えられる。
【０１０９】
このように、関心点は、画像ピラミッドの容積内、例えば容積近傍Ｖ×Ｖ×Ｖ（例えば、３×３×３近傍）内において抽出される。つまり、画像ピラミッドの３層および３画素×３画素の画像区域（すなわち、３×３×３の容積）が検査され、上述したヘッセの行列式（例えば、ヘッセの近似行列式）の極値が決定される。ヘッセ行列式の値またはヘッセ近似行列式は、ピラミッド内の離散スケーリングレベルおよび画像の離散画素またはサンプルにおいてのみ計算される必要があるため、ヘッセ行列式の真の極値は、実際に計算されたレベル間および／または画素またはサンプル間にある可能性がある。必要に応じて、ヘッセ行列の行列式またはヘッセの近似行列式の極値は、例えばBrownらによって提案された方法〔２７〕によって、スケールおよび／または画像空間を補間することによって調べることができる。このような補間は、当業者には公知であるように、例えば多項式的（polynomial）または三角法的な（trigonometric）補間であってよい。スケール空間の補間は、各オクターブにおける第１のスケール変更の誤差を低減するため重要となり得る。
【０１１０】
成分記述子（Sums of Components Descriptor）
本発明の一形態は、記述子を提供する。当該記述子は、粗い局所化情報（crude localization information）の使用と、良好な特徴的出力を生み出す特徴に関連したコントラストの分布との混合である一方で、スケールまたは空間に関する局所化誤差を回避することができる。相対強度および勾配の向きを用いることによって、光度的な変化による影響が低減される。第１の工程は、領域（例えば、関心点周囲の円形領域）からの情報に基づいて、再現可能な向きを関心点周囲に固定する工程から成る。次に、正方形または二次領域が選択された向きに揃えられ、上記記述子が、上記局所化および揃えられた正方形または二次領域から抽出される。関心点は、上記方法および他の適切な方法によって得ることができる。本発明のこの形態は、関心点の取得方法に限定されるものではない。しかし、関心点を取得する上記方法は、本発明による記述子との相乗効果を持つことができる。例えば、上述の方法と同様に簡素な方法でトレースの符号（sign of trace）（ラプラシアン）を提供する検出器方法（detector method）が特に好ましい。
【０１１１】
向きの割り当て
回転に対して不変であるために、例えば、異なる様々な向きに対して機能するために、関心点に対して再現可能な向きが識別される。回転不変性は、アプリケーションによっては望ましい場合があり、望ましくない場合もある。向きは、画像ピラミッドの領域内において抽出される。上記領域は、画像またはスケール空間の三次元領域であってよく、あるいは、画像面またはスケーリング方向における二次元領域であってよい。上記領域は、等方性、すなわち三次元の球形または二次元の円形であってよい。本発明の一実施形態では、上記領域は、半径がＺ×ｓ（ｓは現在のスケール）、例えば６ｓである、関心点周囲の円形区域であり、抽出工程サイズがｓ画素で抽出され、また画像面内に存在している。Ｚの値は、６ｓに限定されるものではない。６ｓは実用的で便利なサイズである。このサイズを用いた場合の向きは、視認点の変化および閉鎖（occlusion）に対して強いことが発見されている。これよりも小さいサイズは不利であり、ブロブまたは関心点のみを取り込み、有意な結果を生まない場合がある。また、上記よりも大きいサイズ（例えば８ｓ）もまた適切である。サイズを過剰に拡大した場合は、画像間をマッチングする際における視認点の変化および閉鎖に対する強さが失われる場合がある。
【０１１２】
調べられる領域としては、二次元領域を用いると特定の利点が得られる。第１の利点は、時間である。これによって特徴計算がより迅速になるため、より小さいスケールにより適している。異なるスケールを用いた実験によって、小さいスケールは多くの詳細を取り込みすぎる可能性があり、大きいスケールは寛大すぎる可能性があることが分かっている。本発明は２Ｄ領域に限定されるものではなく、本発明の範囲には、調べられる領域として様々な次元の領域が含まれており、このような様々な次元の領域が有利である場合もある。
【０１１３】
次に、水平および垂直スカラーコントラスト測度が、辺長が４ｓであるウェーブレット様マスクを用いて計算される。例えば、ハール−ウェーブレット応答（Haar-wavelet response）が、関心点周囲の半径が６ｓである円形の近傍内において、ｘおよびｙ方向に計算される。ｓは、関心点が検出されたスケールである。パラメータ４ｓおよび６ｓは、強い向きを有する関心点が得られるように、実験に基づいて慎重に選択されたものである。本発明は、これらの値に限定されるものではなく、本発明の範囲には異なる値も包含されている。
【０１１４】
抽出工程もまた、スケールに依存しており、ｓとなるように選択することができる。このように、現在のスケールにおいて、ｘおよびｙ方向のウェーブレット応答が計算される高いスケールでは、ウェーブレットのサイズは大きい。ここでもまた、迅速なフィルタリングのために積分画像を用いることができる。本発明の一実施形態ににおいて用いることのできるフィルタは、図５Ａおよび図５Ｂに示されている。これらの図は、反対符号（例えば負）の値のブロックと隣接する符号（例えば正）のフィルタ値のブロックを含む、２つのフィルタを示している。これらのフィルタの目的は、局所コントラストを抽出することである。このタイプであれば、他の任意のフィルタを用いることができる。これらのフィルタの目的は、大きいコントラスト、例えば、通常は高いコントラストを有する画像内のエッジを検出することである。ウェーブレットの辺長は４ｓであるが、本発明はこれに限定されるものではない。４ｓは、多くの状況およびアプリケーションにおいて非常に良好であることが実験によって証明されている。比較される画像同士を相同関係に置くことができる場合、４ｓよりも小さい値を用いることができる。他のアプリケーションでは、４ｓよりも大きい値が有利となり得る。
【０１１５】
円形（図６Ａ）内において得られる応答は、図６Ｂに概略的に示されている。
【０１１６】
あらゆるスケールにおいて、ｘまたはｙ方向の応答を計算するために必要なメモリアクセスは６のみである。メモリアクセスは、算術演算よりも時間が掛かる場合が多いため重要であり、従ってメモリアクセス数を最小限に抑えることは速度最適化のために重要である。また、メモリアクセスは出力を吸収するため、メモリアクセス数を減らすことによって電力消費が低減され、バッテリー式のコンピュータシステムにおいてはバッテリー寿命が向上する。例えば、図１の積分画像の表示（representation）の使用は、上記のような区域のうち２つは並んで配置されているものと仮定する。一方の区域（Ｏａ）は、負の重みを有しており、頂点Ａ、Ｂ、Ｃ、Ｄ、Ｏａ＝−Ａ＋Ｂ＋Ｃ−Ｄであり、第２の区域（Ｏｂ）は、正の重みを有しており、頂点Ｅ、Ｆ、Ｇ、Ｈ、Ｏｂ＝Ｅ−Ｆ−Ｇ＋Ｈである。Ｏｂは、Ｏａの右手側にある。従って、Ｇ＝ＡおよびＨ＝Ｂである。ウェーブレット応答は、Ｏａ＋Ｏｂ＝−Ａ＋Ｂ＋Ｃ−Ｄ＋Ｅ−Ｆ−Ｇ＋Ｈ＝−Ａ＋Ｂ＋Ｃ−Ｄ＋Ｅ−Ｆ−Ａ＋Ｂ＝−２Ａ＋２Ｂ＋Ｃ−Ｄ＋Ｅ−Ｆである。
【０１１７】
次に、必要に応じて、何らかの方法、例えば関心点に中心があるガウス（例えば、σ＝２．５ｓ）によって、ウェーブレット応答に重みが付けられる。これは、関心点の中心に近い応答が、遠くの応答よりも大きい影響を持つように重みがつけられることを意味している。このように、関心点に近い応答は、（別の関心点に関連している場合がある）遠くの応答よりも重要である。先に挙げた特定の実施例では、重み付けは、関心点に中心がある２Ｄガウス関数を用いて応答を乗算することによって行われる。しかし、例えば関心点からの距離に関する線形または非線形重み付けなど、他の重み付けを用いることもできる。これらの重み付けアルゴリズムによって、画像変形に対する記述子のより高い不変性が提供されることが好ましい。これは例えば、応答がさらに少なく計数されることによるものである。
【０１１８】
関心点周囲の複数の平均化ウィンドウ（averaging window）内の重み付けされたウェーブレット応答の和を用いて、関心点の優性な向きが導き出される。この向きを用いて、記述子が構築される。本発明の一実施形態では、スライド向きウィンドウ（sliding orientation window）、例えばサイズがπ／Ｗである円形部分内の全応答の和を計算することによって、優性な向きが推定される。上記において、Ｗは、０．５以上の任意の数である。調べられる領域が容積である場合、ウィンドウはその容積の容積タイル（volumetric tile）である。好ましくはその容積のスライド容積タイルである、すなわち、各ウィンドウ区域または容積は、別のウィンドウ区域または容積に隣接している。ウィンドウの完全数は、調査中の領域を充填する。好ましくは、各ウィンドウの先端は関心点に位置しており、例えば、ウィンドウは関心点に中心がある円形の部分である。
【０１１９】
調べられる領域内において用いられるウィンドウ数の上限は、どれほどの計算を行う必要があるのかという実用性のみによって決定される。Ｗの値は整数であってよく、例えば上記部分はπ／３である（図６Ｂを参照）。好ましい方法では、各ウィンドウ内の水平ウェーブレット応答および垂直応答が、それぞれ独立して合計される。合計された２つの応答は、局所向きベクトルのベクトル座標を生み出す。そして、異なるウィンドウからのベクトルの長さが比較または順位付けされて、最長のベクトルがその向きを関心点に与える。例えば、ウェーブレット応答が計算されて、何らかの方法（例えばガウス（σ＝２．５s））によって中心が関心点に重み付けされると、ウィンドウ内の個々の画素またはサンプルからの応答が、横座標に沿った水平応答強度と縦座標に沿った垂直応答強度と共に、空間内に点として表される。ウィンドウ内の水平応答は合計され、垂直応答もまた合計される。合計されたこれら２つの応答は、図６Ｂに概略的に示されているように、当該ウィンドウに対する新しいベクトルのｘおよびｙ値を生み出す。この手順は、関心点周囲の完全な区域全体における他のウィンドウに対して繰り返され、そしてウィンドウベクトルが互いに比較されて、全ウィンドウベクトルの中で最長のベクトルが決定される。最長ベクトルの向きは、関心点の向きとして選択される。なお、関心点の位置は浮動小数点数であるが、積分画像は補間されないことが好ましい点に留意されたい。積分画像は、有限の差近似（finite difference approximation）を迅速に抽出するために用いることができる。
【０１２０】
記述子生成
関心点の優性な向きを発見した後、記述子の抽出は、第１の工程を含んでいる。当該第１の工程は、（例えば、上記の向き割り当て手順によって）選択された向きを向いているか、あるいは、回転不変性が望ましい場合は垂直な向きに沿っている、関心点に抽出がある領域を構成する工程から成る。当該領域は、正方形領域であってよい（図７参照）。つまり、正方形の一辺が、割り当てられた向きに沿って平行に配置されている。上記ウィンドウのサイズは、その大域的な向きの抽出のためのサイズよりも大きくてよく、例えば２０ｓまたは別の値となるように選択することができる。上記新しい領域は、より小さい領域（例えば４×４、すなわち１６平方部分領域）へと規則的に分割される。これは、重要な空間情報を保持している。各部分領域に対して、少数の記述子特徴がある数で計算される（例えば、規則的に間隔が空けられたサンプル点５×５で計算され、結果として４×４×２５または１６×２５点となる）。このような記述子特徴の最初の２つは、応答ｄｘおよびｄｙの平均値によって規定される。１つの方向ｘにおけるハールウェーブレット応答は、ｄｘと称され（これは、ｘ方向に沿ったコントラスト変化または画像強度変化、すなわちｄＩ／ｄｘによって表すことができる）、別の方向（直交方向ｙであってよい）におけるハールウェーブレット応答は、ｄｙと称される（これは、ｙ方向に沿ったコントラスト変化または画像強度変化、すなわちｄＩ／ｄｙによって表すことができる）。ここで、ｘおよびｙ軸は、領域の境界に対して平行に向けることができ（図７参照）、あるいは、これに関連する任意の他の固定（foixed）方向に向けることができる。これらの特徴は、向きの割り当てのための特徴と同様に抽出される（例えば、マスクサイズは２ｓである）。強度変化の極性に関する状態を得るために、ｄｘおよびｄｙの絶対値の平均値、すなわち|ｄｘ|および|ｄｙ|の絶対値の平均値もまた含まれている。形状的変形および局所誤差に対する強さを上げるために、適切な方法によってｄｘおよびｄｙを重み付けすることがｄけいる。これらは例えば、適切な値のσ（例えば３．３ｓ）によってガウス重み付け（Gaussian weighted）し、関心点に中心を置くことができる。関心点付近の応答が遠くの応答よりも重み付けされる、他の重み付け方法を用いることができる。重み付けとは、応答を、和に加算する前に、関連する関心点からの距離に依存する重み付けアルゴリズムからの値（例えばガウス値）で乗算することを意味している。
【０１２１】
上記を要約すると、記述子は、以下の多次元ベクトルｖによって規定することができ、
【０１２２】
【数８】
2009535680.tif 000010
（５）
あるいは、ベクトル座標の等価平均値、すなわち、このベクトルの各和が、それを計算するために用いられる応答の数で除算される。ベクトル縦座標は、任意の適切な順番で配置することができる。
【０１２３】
あるいは、上記記述子の拡張版が、さらなる特徴を加える。これもまた、前と同一の和を用いるが、これらの値をさらに分割する。ｄｘおよび|ｄｘ|の和は、ｄｙ＜０またはｄｙ
０に対して別々に計算される。同様に、ｄｙおよび|ｄｙ|の和はｄｘの符号に従って分割され、これによって特徴の数が二倍になる。
【０１２４】
この記述子は、以下のように記述することができる：
【０１２５】
【数９】
2009535680.tif 000011
（６）
あるいは、ベクトル座標の等価平均値、すなわちこのベクトルの各和が、それを計算するために用いられる応答の数で除算される。ベクトル縦座標は、任意の適切な順番で配置することができる。
【０１２６】
記述子の次元数は、考慮される部分領域の数に依存しており、また、記述子（例えば、ｄｘおよび|ｄｘ||の和）の一部または部分領域が、その符号に従って分割されて、各部分領域の多次元ベクトルとなる。より正確には、ｄｘおよび|ｄｘ|の和は、ｄｙ
０およびｄｙ＞０に対して別々に計算される。ｄｙおよび|ｄｙ|の和はまた、ｄｘ
０およびｄｘ＞０に対して別々に計算される。例えば、この記述子は、規則的な４×４部分領域の領域に対して１２８次元の記述子を生み出す。
【０１２７】
有効な結果は、他の領域サイズで達成することができる。例えば、２×２部分領域を用いて、拡張された記述子が用いられるか否かに応じて１６次元の記述子または３２次元の記述子を得ることができる。
【０１２８】
図８は、画像内の異なる強度パターンに対して上述した記述子の性質を示している。同次領域においては、記述子の全成分は比較的低いままである（図８Ａ）。高周波（図８Ｂ）では、ウェーブレット応答の絶対値の和は高いが、正則和は低いままである。強度が次第に変化している場合、ウェーブレット応答の絶対値の和および正則和が共に比較的高い（図８Ｃ）。この結果、関心点近傍の強度パターンの特徴的な記述が得られ、これは多くの場合、上記の組み合わせである。
【０１２９】
記述子（ベクトル（６）参照）は、ベクトル（５）の記述子よりも特徴的であり、計算もそれほど遅くはないが、しかしマッチングが低い。これら２つのタイプの記述子は、「法線」（ベクトル（５））および「拡張」（ベクトル（６））記述子として記述される。
【０１３０】
マッチング段階において指標付けをより早くするためには、関心点のコントラストタイプを区別する要素を記述子に導入することが好ましい。例えば、基礎の関心点（underlying interest point）に対するラプラシアンの符号（すなわち、ヘッセのトレース）を記述子内に含ませることができる。ベクトル５および６は、それぞれ以下の通りになる：
【０１３１】
【数１０】
2009535680.tif 000012
（７）
【０１３２】
【数１１】
2009535680.tif 000013
（８）
あるいは、ベクトル座標の等価平均値、すなわちこのベクトルの各和が、それを計算するために用いられる応答の数で除算される。上記式において、Ｌはラプラシアンの符号である。ベクトル縦座標は、任意の適切な順番で配置することができる。
【０１３３】
ラプラシアンは、ヘッセ行列のトレース（対角和）である。ヘッセ行列については、関心点検出に関して既に説明した。この特徴は、検出段階において既に計算済みであるため、追加的な計算コストの必要なしに得ることができる。本発明に従って、記述子を別の関心点検出器（例えば、ハリス関心点検出器）と組み合わせる場合、ラプラシアンが事前に計算されていることはないため、別々に計算しなければならない。通常、関心点は、ブロブタイプの構造において発見される。ラプラシアンを用いることによって、暗い背景上の明るいブロブを逆の状況から区別する（図９参照）。従って、第３の工程（マッチング段階）においてラプラシアンの符号を用いることによって、特徴が同一タイプのコントラスト（例えば黒色または白色）を有している場合は、それらの特徴のみが比較される。早いタイプは、一部分領域において４つ（あるいは、ラプラシアンが含まれている場合は５つ）の特徴を有しており、拡張されたタイプは８つ（あるいは、ラプラシアンが含まれている場合は９つ）有している。従って、ラプラシアンの符号が含まれている場合、記述子の長さは、早いタイプは６５であり、正確なタイプは１２９である。勾配成分は、照明内のバイアスに対して不変である（オフセット）。コントラストに対する不変性（スケール係数）は、ラプラシアンに関する情報を加える前に、記述子ベクトルを正規化することによって達成される。
【０１３４】
これらの記述子を達成するために、いくつかのパラメータを修正する必要があった。選択を最適化するために、これらのパラメータに対して広範囲に渡る試験が行われた。例えば、異なる数のサンプル点および部分領域が試験された。４×４部分領域分割法は、最良の結果をもたらしたが、本発明はこれに限定されるものではない。再分割を細かくするほど強さが弱まり、さらにマッチング時間が増加すると考えられる。一方、３×３部分領域を有する短い記述子は、機能は低いが動作が速く、他の公知の記述子と比較しても全く許容可能である。
【０１３５】
実験結果
図１０では、上記パラメータの選択が、標準的な「落書き（Graffiti）」シーンに対して比較されている。これは、面外回転、面内回転、および輝度変化を含んでいるため、そのベンチマークセット（benchmarking set）において、全てのシーンの中で最も困難なシーンである。視認変化は３０度であった。関心点は、本発明に従って、初期マスクサイズが１５×１５である二倍の画像サイズにおいて、ヘッセ近似（ＳＵＲＦ）を用いて計算された。ＳＵＲＦ３７およびＳＵＲＦ６５は、それぞれ、３×３部分領域および４×４部分領域を有する短い記述子に対応している。ＳＵＲＦ１２９は、４×４部分領域を有する拡張された記述子に対応している。４×４部分領域に対する拡張された記述子が最良に機能する。また、同一数の部分領域に対する短い記述子は良好に機能し、また処理が速い。
【０１３６】
態様
本発明において用いる計算環境の例は、図１１に概略的に示されている。当該計算環境は、同一のシーンまたは複数の異なるシーンの少なくとも１つまたは少なくとも２つの画像を取り込むかあるいは転送するための、カメラ２（例えばデジタルカメラ）あるいはその他のデバイスを含んでいる。デバイス２はまた、記憶手段であってよく、あるいは記憶手段を含んでいてよい。当該記憶手段から、少なくとも１つまたは少なくとも２つの画像を取り出すことができる。あるいは、デバイス２は、少なくとも１つまたは少なくとも２つの画像をダウンロードすることのできる、ネットワーク（例えば、ローカルエリアネットワークまたは広域ネットワーク）接続を含んでいてよく、あるいはこのようなネットワーク接続であってよい。しかし、１つまたは複数の画像が取得され、これらはコンピュータまたはコンピュータシステム３へ転送される。コンピュータまたはコンピュータシステム３は、任意の適切なシステムであってよく、例えばパーソナルコンピュータ、ラップトップまたはパームトップ演算装置、ＰＤＡ、ワークステーション（例えばＵＮＩＸ（登録商標）ワークステーション）、あるいは並列処理コンピュータシステム、コンピュータシステム内のカード（例えばグラフィックアクセラレータカード）、（例えばロボット内の）組み込みシステム等であってよい。しかし、実施されるコンピュータシステム３は、プロセッサまたは処理エンジンを含んでおり、またこの装置を用いて、例えば関心点の検出および／または記述子の生成等、本発明のあらゆる方法が実施される。最後に、任意の適切な表示装置４（例えば、画像表示装置、プロッタ、プリンターの画面）に結果が表示される。あるいは、ネットワークを介して結果を遠隔部に送信し、さらなる処理および／または表示を行うこともできる。表示装置４は、本発明の必要要素ではない。この代わりに、あれはこれに加えて、アクチュエータシステム５への接続部を設けてもよい。このアクチュエータシステム５は、上記コンピュータシステムからの信号に基づいて動作するように構成することができる。例えば、２つの画像が比較されて、これら２つの画像に関心点が共通であることが発見された場合、この決定に応じて、何らの動作も行われないか、あるいは動作が行われる。動作が行われない例としては、上記システムが輸送システムの製品(例えばコンベヤーベルト）の品質管理に用いられて、同一の（複数の）関心点の識別によって上記製品が良好であることが示された場合である。この場合、上記製品は通過されて、何らの動作も行われない。動作が行われる例としては、輸送システムの製品の品質管理に同一のシステムが用いられて、共通の関心点が識別されず、あるいは全てではないが必要な共通点が識別されず、上記製品が不要であることが示された場合である。上記動作とは、装置（例えば気圧ラムまたはジェット）を作動させて上記製品を輸送システムから除去することであってよい。動作が行われる別の例としては、可動ロボットの誘導システムを移動して、（例えばカメラからの）取り込み画像と記憶された画像との共通の関心点によって識別された物体を回避する場合である。別の動作としては、例えば、或る人物の顔の特徴を��り込んだ画像が、望ましくない人物として記憶されている画像のマッチング記述子を有している場合に、アラームを鳴らすという動作がある。
【０１３７】
作動システム５は、上記コンピュータシステムの内部にあってよい。例えば、コンピュータシステム３を用いて大量の画像データベースを分析して、その画像または画像の一部が識別される。この場合、新しい画像の特定の関心点に基づいて、本発明に係る（複数の）記述子が生成されて、そして当該（複数の）記述子を用いてデータベースを検索して照合を見つける。照合が発見されない場合は、新しい画像が、データベース内に存在していないため、適切な不揮発性メモリデバイス（例えば、ハードディスク、テープメモリ、光ディスク、ソリッドステートメモリ等）に記憶される。あるいは、照合が発見された場合ｈ、例えば、新しい画像の表示、新しい画像の廃棄、アラームの作動など、別の動作を行うこともできる。
【０１３８】
図１１において、好ましくは、カメラ２は、様々な位置から物体の画像を取り込むことができるように当該物体周囲の複数の位置へ移動可能であり、また必要に応じて、複数の異なる照明条件が備えられている。あるいは、複数の異なる位置にいくつかのカメラ２が備えられている。カメラ２あるいは複数のカメラ２は、コンピュータ４に、例えば複数の異なる位置から複数の異なる照明条件で取り込まれた１つ以上の画像を提供するように構成されている。
【０１３９】
コンピュータまたはコンピュータシステム３は、上述したように、フィルタリングされた複数の画像を各画像から生成するようにプログラムされており、また必要に応じて、フィルタリングされたそのような画像をメモリ内または記憶装置に記憶するようにプログラムされている。上記コンピュータはまた、上述したヘッセ行列の行列式の少なくとも近似値における極値を調べることによって関心点を探すようにプログラムされている。これに加えて、あるいはこの代わりに、コンピュータ４は、上述の方法によって記述子を生成するようにプログラムされている。特に、上記コンピュータは、１つ以上の極値付近の一領域を識別し、この領域を複数のタイルに分割するように構成されている。各タイルに対して、１つ以上のデジタルフィルタ（例えばハールウェーブレットフィルタ）を適用することによって、コントラスト関連の値が少なくとも２つの直交方向において決定される。少なくとも１つのデジタルフィルタに対する応答が、上記少なくとも２つの直交方向において合計される。この合計は、これら応答の合計と、これら応答の絶対値の合計とを含んでいてよい。コンピュータ２はまた、関心点への向きを割り当てるように構成することもできる。このために、コンピュータ２は、関心点付近の一領域を識別し、この領域を連続したタイルに分割することができる。これらのタイルは全て、関心点に共通の頂点（apex）を有していてよい。各タイルに対して、コンピュータ２は、１つ以上のデジタルフィルタ（例えばハールウェーブレットフィルタ）を適用することによって、少なくとも２つの直交方向において決定されたコントラスト関連の値を計算するように構成することができる。少なくとも１つのデジタルフィルタに対する上記応答は、少なくとも２つの直交方向において合計され、２つのベクトル縦座標が与えられる。コンピュータ２は、上記タイルから最大強度のベクトルを選択し、当該ベクトルの方向を関心点の向きとして割り当てるように構成されている。
【０１４０】
図１２には、スタンドアロンコンピュータシステムの一形態の実施例が概略的に示されている。図１２に示されている構成要素は、離散ハードウェア部品内に必ずしも備えられてはないが必要に応じて分配されている、機能ブロックであってよい。演算装置１０は、パーソナルコンピュータあるいはワークステーションなどのコンピュータであってよい。演算装置１０は、インテルが供給するペンティアム（登録商標）プロセッサなどの中央演算処理装置（「ＣＰＵ」）またはマイクロプロセッサ２０を有している。ＲＡＭメモリ１２、および任意のキャッシュメモリ１４またはコプロセッサが備えられている。様々なＩ／Ｏ（入力／出力）インターフェース１５、１６、１７を備えることができる。これらは例えば、ＵＡＲＴ、ＵＳＢ、Ｉ２Ｃバスインターフェース、ファイヤライン（Fire Wire）等である。また、ネットワーク等に接続するために適切なソース（例えばカメラ、モデム）からデータを受信する、または、遠隔装置（例えば図１１の作動システム）へデータまたは信号を送信する、Ｉ／Ｏセレクタ１８を備えることができる。これらのインターフェースを介したデータ転送からプロセッサ２０を切り離すために、ＦＩＦＯバッファ２２を用いることができる。カウンタ／タイマーブロック２４および割り込みコントローラ２６を備えることができる。演算装置１０の様々なブロックは、適切なバス２１によって接続されている。
【０１４１】
様々なインターフェースアダプタ２７〜２９を備えることができる。アダプタ２７は、システムバス２１を任意のビデオディスプレイ端末３４に接続する、インターフェースアダプタ（例えばディスプレイアダプタ）である。別のアダプタ２９は、周辺機器（例えば、ＤＶＤまたはＣＤ−ＲＯＭドライブ２３などの光学ドライブ、ＰＣＭＣＩＡソリッドステートメモリデバイス、またはＵＳＢソリッドステートメモリデバイス等）をシステムバス２１へ接続する、入力／出力（Ｉ／Ｏ）アダプタを提供する。ビデオディスプレイ端末３４は、コンピュータ装置１０の視覚出力（visual output）であってよく、例えばＣＲＴベースのビデオディスプレイなど、コンピュータハードウェア分野において周知である任意の適切な表示装置であってよい。しかし、携帯用またはノートブックベースのコンピュータの場合、ビデオディスプレイ端末３４は、ＬＣＤベースまたはガスプラズマベースのフラットパネルディスプレイと置き換え可能である。コンピュータデバイス１０は、アダプタ２９を用いた、キーボード３６、マウス３８、および光学スピーカ等の接続をさらに有している。外部の不揮発性メモリ２５へのアクセスのために、このようなハードディスクを、アドレス、データ、および制御バスと共に外部バスインターフェース２８として備えることができる。
【０１４２】
必要に応じて、ソフトウェアプログラムは、内部ＲＯＭ（読み出し専用メモリ）２２および／または外部メモリ２５内に記憶させることができる。オペレーティングシステムは、プロセッサ２０上で実行されるソフトウェアとして実施することができ、例えば米マイクロソフトが供給するオペレーティングシステム、あるいはリナックスオペレーティングシステムであってよい。本発明において用いるのに適した画像プログラムは、プロセッサ２０のための本発明の任意の方法をプログラミングし、そして適切なコンパイラを用いて特定のプロセッサのためのソフトウェアをコンパイルすることによって得ることができる。本発明の方法および手順は、適切なコンピュータ言語（例えばＣ＋＋）でコンピュータプログラムとして書き、デバイス１０内の特定のプロセッサ２０用にコンパイルすることができる。
【０１４３】
このような回路１０の別の例について、例えば、埋め込みマイクロプロセッサ２０周囲のＶＬＳＩチップ（例えば、英国ＡＲＭ社によって設計されたＡＲＭ７ＴＤＭＩコア）として構成された、図１２を参照しながら説明する。これは、図示されている他の構成部品と共にシングルチップ上に合成することができる。ノーウエイト状態のＳＲＡＭメモリ１２およびキャッシュメモリ１４をチップ上に備えることができる。様々なＩ／Ｏ（入力／出力）インターフェース１５、１６、１７（例えば、ＵＡＲＴ、ＵＳＢ、Ｉ２Ｃバスインターフェース、ファイヤライン等）を備えることができ、また、上述したスタンドアロンコンピュータシステム用のＩ／Ｏセレクタ１８を同様の目的のために備えることができる。これらのインターフェースを介したデータ転送からプロセッサ２０を切り離すために、ＦＩＦＯバッファ２２を用いることができる。カウンタ／タイマーブロック２４および割り込みコントローラ２６を備えることができる。ソフトウェアプログラムは、内部ＲＯＭ（読み出し専用メモリ）２２あるいは不揮発性メモリ（例えば２５）内に記憶させることができる。外部メモリ２５へのアクセスは、アドレス、データ、および制御バスと共に外部バスインターフェース２８によって行うことができる。回路１０の様々なブロックは、適切なバス２１によって接続されている。これらのバス２１を介して、組み込みシステムを、パーソナルコンピュータまたはワークステーションなどのホストコンピュータシステムに接続することができる。
【０１４４】
プロセッサを参照した上記説明のいずれの箇所においても、これをプログラマブルハードウェア（例えばＦＰＧＡ）を用いて実現することができ、あるいはハードウェアとして実施することができる。
【０１４５】
上述した本発明の方法および手順は、適切なコンピュータ言語（例えばＣ）でコンピュータプログラムとして書くことができ、また埋め込み設計された特定のプロセッサ用にコンパイルすることができる。例えば、上述の埋め込みＡＲＭコアＶＬＳＩに対して、ソフトウェアをＣ言語で書き、ＡＲＭ  ＣコンパイラおよびＡＲＭアセンブラを用いてコンパイルすることができる。従って本発明は、上述したいずれかのコンピュータシステム上において実施された場合に本発明のいずれかの方法またはシステムを実施するコンピュータプログラムをさらに含んでいる。上記コンピュータプログラムは、例えば光ディスク（例えば、ＣＤ−ＲＯＭまたはＤＶＤ−ＲＯＭ）、磁気テープ、磁気ディスク（例えばハードディスク、ディスケット等）、ソリッドステートメモリ（例えばＵＳＢメモリスティック等）など、任意の適切な記憶媒体に記憶させることができる。
【０１４６】
〔参考文献〕
1. Lindeberg, T.: Feature detection with automatic scale selection. IJCV 30(2)(1998) 79-11613
2. Lowe, D.: Distinctive image features from scale-invariant keypoints, cascade filtering approach. IJCV 60 (2004) 91-110
3. Mikolajczyk, K., Schmid, C: An affine invariant interest point detector. In: ECCV.(2002) 128-142 
4. Se, S., Ng, H., Jasiobedzki, P., Moyung, T.: Vision based modeling and localization for planetary exploration rovers. Proceedings of International Astronautical Congress (2004)
5. Tuytelaars, T., Van Gool, L.: Wide baseline stereo based on local, affinely invariant regions. In: BMVC. (2000) 412-422
6. Matas, J., Chum, O., M., U., Pajdla, T.: Robust wide baseline stereo from maximally stable extremal regions. In: BMVC. (2002) 384-393
7. Mikolajczyk, K., Schmid, C: A performance evaluation of local descriptors. In:CVPR. Volume 2. (2003) 257-263
8. Mikolajczyk, K., Schmid, C: A performance evaluation of local descriptors.
PAMI, 27(10). (2005) 1615-1630
9. Mikolajczyk, K., Tuytelaars, T., Schmid, C, Zisserman, A., Matas, J.,
Schaffalitzky, F., Kadir, T., Van Gool, L.: A comparison of affine region detectors. IJCV, 65(1/2). (2005) 43-72
10. Harris, C, Stephens, M.: A combined corner and edge detector. In:
Proceedings of the Alvey Vision Conference. (1988) 147-151
11. Mikolajczyk, K., Schmid, C: Indexing based on scale invariant interest points. In: ICCV. Volume 1. (2001) 525-531
12. Lowe, D.: Object recognition from local scale-invariant features. In: ICCV. (1999)
13. Kadir, T., Brady, M.: Scale, saliency and image description. IJCV 45(2) (2001)83-105
14. Jurie, F., Schmid, C: Scale-invariant shape features for recognition of object categories. In: CVPR. Volume II. (2004) 90-96
15. Mikolajczyk, K., Schmid, C: Scale and affine invariant interest point detectors. IJCV 60 (2004) 63-86
16. Florack, L. M. J., Haar Romeny, B.M.t, Koenderink, J. J., Viergever, M. A.:
General intensity transformations and differential invariants. JMIV 4 (1994)
171-187
17. Moons, T., Van Gool, L., Pauwels, E., Oosterlinck, A.: Viewpoint invariant characteristics of articulated objects. Journal of Mathematical Imaging and
Vision (6) 37-58
18. Baumberg, A.: Reliable feature matching across widely separated views. In:
CVPR.(2000) 774-781 
19. Schaffalitzky, F., Zisserman, A.: Multi-view matching for unordered image sets, or "How do I organize my holiday snaps?". In: ECCV. Volume 1. (2002) 414-431
20. Freeman, W.T., Adelson, E.H.: The design and use of steerable filters. PAMI 13(1991) 891-906
21. Carneiro, G., Jepson, A.: Multi-scale phase-based local features. In: CVPR (l).(2003) 736-743
22. Ke, Y., Sukthankar, R.: Pea-sift: A more distinctive representation for local image descriptors. In: CVPR (2). (2004) 506-513
23. Viola, P., Jones, M.: Rapid object detection using a boosted cascade of simple features. In: CVPR (1). (2001) 51 1-518
24. Koenderink, J.: The structure of images. Biological Cybernetics 50 (1984) 363-370
25. Lindeberg, T.: Scale-space for discrete signals. PAMI (1990) 234-254
26. Lindeberg, T.: Discrete Scale-Space Theory and the Scale-Space Primal
Sketch, PhD, KTH Stockholm,. (1991)
27. Brown, M., Lowe, D.: Invariant features from interest point groups. In: BMVC (2002).
【図面の簡単な説明】
【０１４７】
【図１】本発明の実施形態と共に用いることのできる積分画像の演算方法を示す図である。
【図２】図２Ａおよび図２Ｂは、本発明の一実施形態に係る、それぞれｙ方向およびｘｙ方向におけるガウスの２階偏微分を示す離散化およびクロップされたデジタルフィルタを示す図である。図２Ｃ、図２Ｄ、および図２Ｅは、本発明の一実施形態に係る、それぞれｙ方向、ｘｙ方向、およびｘ方向におけるガウスの２階偏微分の近似を示す離散化およびクロップされたデジタルフィルタを示す図である。
【図３】本発明の実施形態と共に用いることのできる画像ピラミッドの概略図である。
【図４Ａ】デジタルフィルタサイズを拡大し、それを初期入力画像へ適用することによってスケール空間が解析される、本発明の一実施形態を示す図である。
【図４Ｂ】ヘッセ行列の近似行列式などの測度の最大が決定される、画像内およびスケール全体における局所近傍の詳細を示す図である。
【図５】コントラストを見つけるために本発明の一実施形態において用いられる、コントラストに関連したハールウェーブレットデジタルフィルタを示す図である。
【図６】図６Ａは、本発明の一実施形態において、再現可能な向きを決定するために用いられる画像の関心点周囲の離散的円形区域を示す図である。図６Ｂは、本発明の一実施形態において、ウィンドウのための代表ベクトルがいかに得られるかを示す図である。
【図７】本発明の一実施形態において、正方形領域が割り当てられた向きにどのように整列されるか、および、この向きに従ってウェーブレット応答がどのように計算されるかを示す図である。
【図８】画像内の異なる強度パターンに対する、本発明の実施形態に係る記述子の性質を示す図である。
【図９】本発明の一実施形態に従って、ラプラシアンの符号を必要に応じて用いて、明るい背景上の暗いブロブを、逆の状況から区別することができることを示す図である。
【図１０】本発明に係る方法と公知の方法との実験結果のコントラストを示す図である。
【図１１】本発明と共に用いることのできる、入力画像を取り込むデジタルカメラを備えた一般的なコンピュータシステムを示す図である。
【図１２】図１２は、本発明と共に用いることのできるシステムの一実施例として具体的な計算システムを示す図である。
【図１】
2009535680.tif 000014
【図２Ａ】
2009535680.tif 000015
【図２Ｂ】
2009535680.tif 000016
【図２Ｃ】
2009535680.tif 000017
【図２Ｄ】
2009535680.tif 000018
【図２Ｅ】
2009535680.tif 000019
【図３】
2009535680.tif 000020
【図４Ａ】
2009535680.tif 000021
【図４Ｂ】
2009535680.tif 000022
【図５Ａ】
2009535680.tif 000023
【図５Ｂ】
2009535680.tif 000024
【図６Ａ】
2009535680.tif 000025
【図６Ｂ】
2009535680.tif 000026
【図７】
2009535680.tif 000027
【図８】
2009535680.tif 000028
【図９】
2009535680.tif 000029
【図１０】
2009535680.tif 000030
【図１１】
2009535680.tif 000031
【図１２】
2009535680.tif 000032
【国際調査報告】
2009535680.tif 000033
2009535680.tif 000034
2009535680.tif 000035
2009535680.tif 000036
2009535680.tif 000037
2009535680.tif 000038