(57)【特許請求の範囲】
【請求項１】
画像を表現するための方法であって、前記画像は、ガウスピラミッドとして表現されており、前記ガウスピラミッドは、複数のピラミッド画像を備えており、前記ピラミッド画像は、複数のピクセルを備えている、画像を表現するための方法において、
前記ピラミッド画像の中の前記複数のピクセルの間で複数の特徴点を識別することであって、前記複数の特徴点の内の１つの特徴点は、前記画像の変換に対して不変的である、特徴点を識別することと、
配向計算アルゴリズム一式に基づいて前記ピラミッド画像の中の前記特徴点の１つ又はそれ以上の配向を決定することと、
前記ピラミッド画像の前記１つ又はそれ以上の配向及び所定のサンプリング因子に基づいて前記複数の特徴点を包含する複数のパッチを前記ピラミッド画像から抽出することと、
前記パッチに対する特徴ベクトルを画定することであって、
前記パッチを複数の小パッチに分割することと、
前記複数の小パッチの内の１つの小パッチに対応する前記特徴ベクトルの成分であって、
前記小パッチの中に存在する前記ピラミッド画像の全ての正のｘ導関数の合計である、第１の成分と、
前記小パッチの中に存在するピラミッド画像の全ての負のｘ導関数の合計の前記負数である、第２の成分と、
前記小パッチの中に存在する前記ピラミッド画像の全ての正のｙ導関数の合計である、第３の成分と、
前記小パッチの中に存在する前記ピラミッド画像の全ての負のｙ導関数の合計の前記負数である、第４の成分と、を備えている、特徴ベクトルの成分を算出することと、を備えている、特徴ベクトルを画定することと、
前記ピラミッド画像の前記複数の特徴点及び特徴ベクトルに基づいて前記画像を表現することと、
から成る、前記方法。
【請求項２】
前記ピラミッド画像の境界上に存在する特徴点に対する前記パッチは、前記ピラミッド画像に追加のピクセルでパディングすることで抽出される、請求項１の方法。
【請求項３】
前記ピラミッド画像は、前記画像をダウンサンプリングすること及びガウス関数で前記画像をぼかすことにより形成され、前記ガウス関数は、所定の尺度パラメータで特徴付けられる、請求項１の方法。
【請求項４】
前記ピラミッド画像の中の前記複数のピクセルの間で前記複数の特徴点を前記識別することは、
前記複数のピクセルの内のピクセルでハリスコーナー測度を計算することと、
前記ハリスコーナー測度が局所的最大値を有する一連の点を識別することであって、前記識別された一連の点の内の１つの点は特徴点である、一連の点を識別することと、を備えている、請求項１の方法。
【請求項５】
前記ピラミッド画像の前記複数の特徴点の前記ハリスコーナー測度と所定の尺度パラメータを組み合わせたものに基づいて特定の数の特徴点を選択することを更に備えている、請求項４の方法。
【請求項６】
楕円放物面を所定の領域に嵌め合わせることによって前記特徴点の位置を推定することを更に備えており、前記所定の領域は、前記特徴点を包含している、請求項４の方法。
【請求項７】
前記ピラミッド画像の前記特徴点の前記１つ又はそれ以上の配向を決定することは、
前記配向計算アルゴリズム一式を使用することにより前記特徴点に対する一連の配向を計算することと、
互いの所定の角距離の中にある配向の群を前記一連の配向の平均値で置換することと、を備えている、請求項１の方法。
【請求項８】
前記特徴点の周囲で前記パッチを前記ピラミッド画像から抽出することは、複数の決定された位置で前記ピラミッド画像の勾配をサンプリングすることを備えており、前記複数の決定された位置は、前記ピラミッド画像の前記１つ又はそれ以上の配向及び前記所定のサンプリング因子に基づいて決定される、請求項１の方法。
【請求項９】
画像を表現するための方法であって、前記画像は、ガウスピラミッドとして表現されており、前記ガウスピラミッドは、複数のピラミッド画像を備えており、前記ピラミッド画像は、複数のピクセルを備えている、画像を表現するための方法において、
前記ピラミッド画像の中の前記複数のピクセルの間で複数の特徴点を識別することであって、前記複数の特徴点の内の１つの特徴点は、前記画像の変換に対して不変的である、特徴点を識別することと、
配向計算アルゴリズム一式に基づいて前記ピラミッド画像の中の前記特徴点の１つ又はそれ以上の配向を決定することと、
前記ピラミッド画像の前記１つ又はそれ以上の配向及び所定のサンプリング因子に基づいて前記複数の特徴点を包含する複数のパッチを前記ピラミッド画像から抽出することと、
前記パッチに対する特徴ベクトルを画定すること
前記ピラミッド画像の前記複数の特徴点及び特徴ベクトルに基づいて前記画像を表現することと、
前記パッチの前記特徴ベクトルを前記標準化することであって、
所定の閾値より小さい値を有する最初の特徴ベクトルの成分を決定することと、
計算された長さに対する前記所定の閾値より小さい値を有する成分を標準化することと、
からなる、前記方法。
【請求項１０】
前記計算された長さは、前記所定の閾値及び前記所定の閾値より大きい値を有する成分の前記数に基づいて計算される、請求項９の方法。
【請求項１１】
前記最初の特徴ベクトルの前記成分を減らし且つ前記所定の閾値より小さい値を有する前記成分を標準化する前記ステップは、前記所定の閾値より大きい値を有する成分がなくなるまで反復される、請求項１０の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、デジタル画像処理の分野に関する。より具体的には、本発明は、同じ内容を含む別の画像とマッチングさせることができるように、画像の内容を表現するための方法及びシステムに関する。
【背景技術】
【０００２】
画像マッチングは、コンピュータ・ビジョン、物体認識、動作追跡、三次元モデリングなどで使用される基礎的な技法である。画像マッチングは、２つの画像が同じ内容を有しているか否かを照査するために行われる。比較する必要がある２つの画像は、全く同じではない場合がある。例えば、１つの画像は、もう一方の画像と比べて、回転されている又は異なる視点から取得されている場合がある、若しくはもう一方の画像の拡大異形である場合がある。更に、２つの画像は、異なる照明条件下で取得される場合がある。２つの画像のその様な変差にもかかわらず、それらは、同じ内容、場面、物体を含んでいる。従って、画像マッチング技法は、画像を効果的にマッチングするために使用される。
【０００３】
典型的な画像マッチングアルゴリズムは、物体又は場面の画像が多くの特徴点を含むという事実を利用している。特徴点は、画像回転、尺度、視点又は照明条件の変化に対してロバスト性を有する画像の特定の点である。このことは、たとえ２つの画像が前述のように異なっていても、それらの特徴点は、両方の画像に存在することがしばしばあるものであることを意味している。それらの特徴点は、「重要な点」としても知られている。従って、画像マッチングアルゴリズムの第１の段階は、画像の中のそれらの特徴点を見つけることである。通常、画像ピラミッドは、画像の特徴点を決定するために構成されている。画像ピラミッドは、画像の尺度空間表現である、即ち画像ピラミッドは様々なピラミッド画像を含んでおり、それらの各々は、特有の尺度で画像を表現したものである。尺度空間表現は、画像マッチングアルゴリズムが、全体的な尺度が異なっている画像をマッチングすることができるようにする。
【０００４】
画像ピラミッドの中の全てのピラミッド画像の特徴点を決定した後、標準的な画像マッチングアルゴリズムは、それぞれの特徴点の配向を決定する。特徴点の配向は、特徴点における局所的な画像勾配に基づいて決定される。配向は、回転に対して不変性を得るために使用される。特徴点及びそれらの配向が決定された後、パッチは、配向ベクトルがパッチ用の基準フレームの１つの軸を形成するような方法で、特徴点の周囲で抽出される。このパッチ上の局所的な画像勾配は、計算され、特徴ベクトル表現に変換される。特徴ベクトル表現は、局所的な歪み及び照明の有意な変化を考慮する、即ち特徴ベクトルは、照明条件の歪み及び変化に対して不変的である。
【０００５】
ピラミッド画像全体に亘る特徴点、それらの配向及びそれらの特徴ベクトルは、画像の完全な表現を形成する。それらの表現を、マッチング画像を見つけるために、全画像に亘って比較することができる。
【０００６】
画像を表現する既存の方法に関連付けられる様々な限界が存在する。最初に、画像は、多数の特徴点を含む場合がある。それらの特徴点の幾つかは、画像の表現の中の他のものと比べて重要性に劣るものであり、画像マッチングアルゴリズムの複雑さを不必要に増やす。第２に、特徴点の配向を決定するために異なる方法が存在しており、それらの方法は、異なる結果を作り出す。従って、配向を決定するために、任意の単一の方法を信頼することはできない。更に、特徴点の２つ又はそれ以上の配向が作り出される場合、それらは、画像マッチングアルゴリズムの複雑性を増す。第３に、特徴点の周囲でパッチを抽出するために使用されるサンプリングアルゴリズムは、実際の尺度に感受性を持たない。従って、それらの方法は、たとえ画像の大きさが一定であっても、パッチの大きさは尺度が大きくなるにつれて大きくなるはずであるという事実を考慮しない。第４に、パッチは、画像の境界を越えて延在する場合があるので、画像の境界周囲のパッチは、抽出されない。境界のパッチは、多くの場合、特に画像の大きさが減少するにつれ、全体的な画像マッチングアルゴリズムに有意的に貢献するという理由から、これは望ましくないことである。最後に、特徴点の特徴ベクトルに存在する幾つかの成分は、パッチを通過するエッジが原因で大きくなる場合がある。そのような特徴ベクトルは、照明の変化に対してロバスト性を有していない。既存の方法は、特徴ベクトルを標準化することによってロバスト性を改善しているが、それを数値的に保証していない。
【０００７】
上述の数多くの限界を克服するために改良された画像表現方法の必要性が存在する。
【発明の概要】
【課題を解決するための手段】
【０００８】
本発明の目的は、２つ又はそれ以上の画像を効果的にマッチングすることができるように、画像の改良された表現のための方法、システム及びコンピュータプログラム製品を提供することである。
【０００９】
本発明の別の目的は、単一の配向を備えた特徴点の配向の群を知的に置換するための方法、システム及びコンピュータプログラム製品を提供することである。
【００１０】
本発明の更に別の目的は、特徴点の周囲でパッチをよりロバスト性を有して抽出するためにピラミッド画像の尺度を使用するための方法、システム及びコンピュータプログラム製品を提供することである。
【００１１】
本発明の更に別の目的は、画像を表現する一方で、画像の境界のパッチを抽出及び使用するための方法、システム及びコンピュータプログラム製品を提供することである。
【００１２】
本発明の更に別の目的は、特定の閾値より大きい成分を含んでいない、ロバスト性を有する特徴ベクトルの形態で画像を表現するための方法、システム及びコンピュータプログラム製品を提供することである。
【００１３】
本発明の様々な実施形態は、画像を表現するための方法、システム及びコンピュータプログラム製品を提供する。異なるピラミッド画像で構成される、画像のガウスピラミッドが形成される。ピラミッド画像は、特有の尺度パラメータで元の画像から変換された異形である。その後、ピラミッド画像の特徴点は、識別される。特定の数の特徴点は、全ての識別された特徴点から選択される。特徴点の配向は、配向計算アルゴリズム一式から得た配向を組み合わせることによって決定される。その後、パッチは、特徴点の周囲で抽出される。ピラミッド画像の境界に存在する特徴点の周囲のパッチは、ピラミッド画像に追加のピクセルでパディングすることによって抽出される。更に、パッチを抽出するために使用されるサンプリングは、ピラミッド画像の特徴点の配向及び所定のサンプリング因子に基づく。その後、特徴ベクトルは、抽出されたパッチのそれぞれに対して画定される。特徴ベクトルは、特定の閾値より大きい特徴ベクトルの成分はないように標準化される。
【図面の簡単な説明】
【００１４】
本発明に限定を課すためではなく、本発明を説明するために提供された添付の図面と関連付けながら本発明の様々な実施形態を、これより説明してゆくが、図中において類似の記号は類似の要素を表す。
【００１５】
【図１】本発明の様々な実施形態を実施することができる画像の環境を図示している。
【図２】本発明の様々な実施形態によって、画像を表現するための方法を図示する流れ図である。
【図３】本発明の様々な実施形態によって、画像を表現するための詳細な方法を図示する流れ図を表わしている。
【図４】本発明の様々な実施形態によって、画像を表現するための詳細な方法を図示する流れ図を表わしている。
【図５】本発明の様々な実施形態によって、画像を表現するために使用されるであろう様々なシステム構成要素を図示するブロック図である。
【発明を実施するための形態】
【００１６】
当業者には理解されるように、本発明の実施形態の理解を深めることを支援する目的で、図中の要素は、簡潔且つ明瞭にするために図示されている。
【００１７】
本発明の様々な実施形態は、画像を表現するための方法、システム及びコンピュータプログラム製品に関する。方法は、画像を描写するために画像に存在する特徴点を使用する。従って、方法の第１のステップは、画像の中の特徴点を決定することである。その後、特徴点の配向は、配向計算アルゴリズム一式から得られた配向を組み合わせることによって決定される。その後、パッチが、特徴点の周囲で抽出され、特徴ベクトルが、抽出されたパッチに対して画定される。特徴ベクトルは、特定の閾値より大きい特徴ベクトルの成分がないように標準化される。
【００１８】
図１は、本発明の様々な実施形態を実施することができる環境１００を図示している。本発明は、コンピュータ・ビジョン、物体認識、動作追跡及び３Ｄモデリングの分野で使用されてもよい。画像は、ＪＰＥＧ、ＧＩＦ、ＢＭＰなどのように異なる書式のものでもよい。更に、それらの画像の品質及び解像度は、適用ごとに様々であってもよい。更に、画像は、全く同じである必要はないが、互いに変換された異形である。従って、画像マッチングアルゴリズムでは、画像を互いにマッチングすることができるように、画像は、特有の書式で表現されている。
【００１９】
環境１００は、問い合わせ画像１０２及び画像１０４ａ〜１０４ｎのデータベースを含んでいる。データベースを、問い合わせ画像１０２とマッチングする単数（又は複数）の画像を見つけ出すために検索する。マッチング画像は、問い合わせ画像１０２と全く同じである必要はないが、問い合わせ画像１０２と同じ内容を含んでいなければならない。例えば、問い合わせ画像１０２は、マッチング画像の尺度変更した、回転した、若しくは拡大縮小した異形、又は何らかの他の可能な変換であってもよい。本発明の画像マッチングアルゴリズムは、画像１０４ａ〜１０４ｎの中で、上述のやり方が異なる、問い合わせ画像１０２とマッチングするものを見つけ出す。画像マッチングアルゴリズムは、特徴点、配向及び特徴ベクトルの観点から画像を表現することによって動作している。問い合わせ画像及びデータベース画像の表現を作成した後、画像の特徴点、配向及び特徴ベクトルは、使用して画像間のマッチングを決定するために使用される。本発明は、或る画像を他の画像とマッチングすることができるように、或る画像を表現するための方法及びシステムを説明する。
【００２０】
図２は、本発明の実施形態によって、画像を表現する方法を図示する流れ図である。図２は、画像を表現するために好ましくは画像に行われるべき主なステップの概要を提供している。図２の各ステップは、後ほど図３及び図４と関連させて詳細に説明する。
【００２１】
画像を表現する前、画像を、幾つかのピラミッド画像を含む画像ピラミッドとして表現する。ピラミッド画像は、元の画像の平滑化及びダウンサンプリングされた異形である。ダウンサンプリングは、元の画像から１つおきに行及び列を取ることによって行われる。更に、画像の平滑化又はぼかしは、ガウス関数で画像を畳み込むことによって行われる。平滑化及びダウンサンプリングによって画像ピラミッドを形成する工程は、後ほど詳細に説明される。
【００２２】
ステップ２０２では、ピラミッド画像の特徴点を識別する。識別された特徴点は、画像の拡大縮小、尺度変更、及び回転のような画像の或る種の変換に対して不変的である。特徴点は、ピラミッド画像の異なる点でハリスコーナー測度を見つけ出すことによって識別される。ハリスコーナー測度の局所的最大値が、特徴点として識別される。特徴点を識別した後、それらの配向をステップ２０４で決定する。配向は、配向計算アルゴリズム一式を使用することによって決定される。配向計算アルゴリズムは、特徴点の配向を得るために画像の勾配を使用する。例えば、１つのアルゴリズムは、配向のヒストグラムの主要ピークを探してもよく、一方で別のものは画像を大きく平滑化してもよい。その後、ステップ２０６では、特徴点を包含する画像のパッチを、特徴点の周囲で抽出する。パッチの抽出は、ピラミッド画像の特徴点の配向及び所定のサンプリング因子に基づく。更に、ピラミッド画像の境界上に存在する特徴点のパッチは、ピラミッド画像に追加のピクセルでパディングすることによって抽出される。その後、境界及び非境界パッチ用の特徴ベクトルを、ステップ２０８で画定する。境界パッチは、ピラミッド画像のパディングの追加のピクセルを含んでいる。ステップ２１０では、画像を、ピラミッド画像の特徴点、特徴点の配向及び特徴ベクトルに基づいて表現する。
【００２３】
画像マッチングアルゴリズムを画像に適用する前に、画像は画像ピラミッドの形態で表現される。画像ピラミッドは、幾つかのピラミッド画像を含んでいる。ピラミッド画像は、元の画像の平滑化及びダウンサンプリングされた異形である。画像の平滑化は、ガウス関数で画像を畳み込むことによって行われる。従って、画像ピラミッドは、ガウスピラミッドとも呼ばれる。ガウス関数は、ガウス関数の標準偏差である、σで示される所定の尺度パラメータで特徴付けられる。従って、全てのピラミッド画像は、所定の尺度パラメータσによって尺度変更され、σの値は、ピラミッド画像毎に変化する。
【００２４】
本発明の一実施形態では、ガウスピラミッドは、画像の幾つかのオクターブで構成される。各オクターブは、同じ大きさではあるが異なる尺度である画像で構成される。例えば、一オクターブは、４つの画像に共通して均一に分配されるσの値を有する、４つの画像で構成することができる。上の例の各画像用のσの値は、
【００２５】
【数１】
0005336607.tif 000002
【００２６】
とすることができる。σのそれらの値は、単なる例証のためのものであり、σの他の値をもオクターブを形成するために使用することもできる。更に、オクターブの最終画像は、次のオクターブの第１の画像を得るためにダウンサンプリングされる。例えば、上の例の最終画像（σ＝２を有する）は、次のオクターブの第１の画像を得るために２の因子によってダウンサンプリングされる。この事例では、画像の１つおきの行及び列が、ダウンサンプリングされた画像を形成するために取られる。画像は、画像の大きさが、パッチの大きさのような最小の大きさを下回るまでオクターブを作成するために更にダウンサンプリングされる。このようにして、画像の幾つかのオクターブを有するガウスピラミッド全体は作成される。
【００２７】
本発明の別の実施形態では、画像のガウスピラミッドを構築する前に、アップサンプリングアルゴリズムが、画像の大きさを上げるために使用される。画像の最初の大きさがアップサンプリング閾値より小さい場合、画像をアップサンプリングする。例えば、アップサンプリング閾値の値を、１２０，０００（４００×３００）と予め規定することができる。画像マッチングアルゴリズムの異なる適用によって、アップサンプリング閾値の任意の他の値を、他の実施形態では選んでもよいことに留意されたい。更に、画像は、ピクセルの行及び列を元の画像のあらゆる隣接する行及び列の間に挿入することによってアップサンプリングされる。挿入された行及び列の値は、双線形補間を元の画像の中に存在する値に適用することによって画定される。アップサンプリングは、画像に新しい情報を何も作成しないので、アップサンプリング工程は、繰り返すこと無く一回行われる。
【００２８】
本発明の別の実施形態では、元の画像の大きさがダウンサンプリング閾値より大きい時、画像のガウスピラミッドを構築する前に、画像を、繰り返して平滑化及びダウンサンプリングする。例えば、ダウンサンプリング閾値を、１，３００，０００として予め規定することができる。画像マッチングアルゴリズムの異なる適用によって、ダウンサンプリング閾値の任意の他の値を、他の実施形態では選んでもよいことに留意されたい。画像は、尺度パラメータσが０．８である、ガウス関数で画像を畳み込むことによって平滑化される。更に、ダウンサンプリングされた画像を得るために画像から１つおきの行及び列を選択することによって、画像を、２の因子でダウンサンプリングする。
【００２９】
画像ピラミッドの形態で画像を表現した後、画像は特徴点、特徴点配向及び特徴ベクトルの形態で表現される。図３及び図４は、画像を表現するための詳細な方法を図示する流れ図を表現している。図３及び図４のステップ３０２〜ステップ３２０は、ガウスピラミッドのピラミッド画像で別々に行われる。しかしながら、図３及び図４のステップを表示する間、簡潔さのために、用語「画像」を、用語「ピラミッド画像」の代わりに使用している。
【００３０】
画像を表示する工程全体での第１のステップは、図２のステップ２０２で述べたように、画像の中の特徴点を識別することである。特徴点は、画像を表現するために使用される一連の「重要な点」である。特徴点を識別する工程を、更に詳細に説明する。
【００３１】
画像の中の特徴点を識別するために、画像の中の特徴点の「重要さ」を計算する。画像の中の特徴点の「重要さ」は、画像の中の特徴点のハリスコーナー測度の観点から画定される。それらの特徴点は、画像の主な領域の中又は画像のエッジの上に存在することができる。ハリスコーナー測度は、ステップ３０２で計算される。当該測度は、画像の自己相関関数に基づく。ハリスコーナー測度を得るために、画像勾配はｘ方向及びｙ方向の画像の導関数である、それぞれＩx及びＩyから計算される。それらの導関数は、ｘ方向及びｙ方向で［−１０１］のようなカーネルで画像を畳み込むことによって得られる。
【００３２】
画像の導関数を、画像の任意点（ｘ、ｙ）における強度の推移の概算量を表現するために使用する。特徴点は、画像の特徴における強度の推移に基づいて識別される。点（ｘ、ｙ）における強度の推移をＥ（ｘ、ｙ）によって示し、関係式、
【００３３】
【数２】
0005336607.tif 000003
【００３４】
によって表示し、ここに、
【００３５】
【数３】
0005336607.tif 000004
【００３６】
である。
【００３７】
行列Ｍの固有値は、点（ｘ、ｙ）を取り囲む画像の領域の特性を画定する。両方の固有値が小さい場合、領域は平らであり、領域に変分は存在しないことを示している。まさしく１つの固有値が大きい場合、領域はエッジを含んでいることを示している。両方の固有値が大きい場合、領域は角又は接合部を含んでいることを示している。固有値は、それらの計算が複雑な工程であるため、直接的に決定されない。固有値を算出することを回避するため、行列Ｍの行列式及びトレースを計算する。行列式ｄｅｔ（Ｍ）及びトレースｔｒａｃｅ（Ｍ）は、固有値の積及び合計を生み出す。その後、点（ｘ、ｙ）におけるハリスコーナー測度（Ｈ）を以下のように画定する。
【００３８】
【数４】
0005336607.tif 000005
【００３９】
常にこの関数を画定されるように保つために、分母が常にゼロにならないように、少量のεが、分母に加算される。更に、点の行列Ｍのある点における要素
【００４０】
【数５】
0005336607.tif 000006
【００４１】
を、ガウス関数で画像勾配を畳み込むことによって得る。それらの要素を計算するための式は、以下のようになる。
【００４２】
【数６】
0005336607.tif 000007
【００４３】
ここに、Ｇσは、ガウス関数を示し、尺度パラメータσを特徴とする。乗法は、非線形関数であるので、ガウス関数を用いる畳み込みを、乗法の後行う。
【００４４】
画像の中の点におけるハリスコーナー測度を計算した後、特徴点を、ハリスコーナー測度が局所的最大値を有する画像の中の点としてステップ３０４で識別する。ハリスコーナー測度の局所的最大値を決定する方法を、以下で詳細に説明する。
【００４５】
本発明の一実施形態では、５×５ボックスを、画像のピクセルが局所的最大値であるか否かを照査するために使用する。５×５ボックスは２の半径を有しており、半径は、５×５ボックスの中心を中心として描かれた虚円の半径である。最大値を決定するために任意の他の適切な大きさを選んでもよいことに留意されたい。ボックスの中心を特徴点と一直線に揃え、ボックス内部に位置する点のハリスコーナーを中心点のハリスコーナー測度と比較する。ハリスコーナー測度がボックス内部のあらゆる他の点のハリスコーナー測度より大きい場合、中心点は、局所的最大値である。ある点が、局所的最大値として識別される時には、当該点を、一連の特徴点に加える。局所的最大値を検出するために使用されるボックスの大きさ又は半径は、様々とすることができる。しかしながら、特徴点が近接しすぎることを回避するという理由から、１より大きい半径を有するボックスを通常使用する。
【００４６】
ハリスコーナー測度に基づいて特徴点一式を識別した後、ステップ３０６では、特定の数の特徴点を一連の特徴点から選択する。画像が高解像度である又は大量のテキストを含んでいる時は、選択は重要になる。その様な画像は、画像マッチングアルゴリズムの効率を低下する場合のある数多くの特徴点を作り出す可能性がある。本発明の実施形態では、特定の数の特徴点が、特徴点のハリスコーナー測度に基づいて選択される。この事象では、特徴点は、リストを形成するためにハリスコーナー測度の降順でソートされ、特定の数の特徴点が、リストの最上位から選択される。本発明の別の実施形態では、特徴点の選択は、ピラミッド画像のハリスコーナー測度及び所定の尺度パラメータの積に基づくことができる。
【００４７】
ステップ３０８では、特徴点のより正確な位置を推定する。ステップ３０６で識別される特徴点は、整数座標を有している。しかしながら、画像のピクセルは、画像関数の離散サンプルである。更に、ダウンサンプリングされた画像の１つのピクセルは、元の画像のピクセルの２×２、４×４又は８×８ブロックを表現する。このような理由から、特徴点のより正確な位置をサブピクセルレベルで推定する。この工程は、サブピクセル位置確認と呼ばれる。
【００４８】
特徴点のサブピクセル位置確認は、楕円放物面を特徴点の周囲の所定の領域に嵌め合わせることによって行われる。楕円放物面が特徴点及びそれらの特徴点上に存在する強度の値を包含するように、楕円放物面は、嵌め合わされる。楕円放物面は、楕円断面を有する三次元の二次曲面である。楕円放物面が嵌め合わされる所定の領域は、特徴点を包含している。本発明の一実施形態では、所定の領域は、特徴点に中心があるピクセルの３×３ボックスである。３×３ボックスの中の値は、これによって楕円放物面の頂点の位置を決定する、楕円放物面の係数を決定するために使用される。頂点は、特徴点のサブピクセル位置を表現している。楕円放物面を嵌め合わせ、楕円放物面の頂点を見つけ出す工程を、更に詳細に説明する。
【００４９】
楕円放物面の方程式は、ｚ（ｘ，ｙ）＝ａｘ2＋ｂｙ2＋ｃｘｙ＋ｄｘ＋ｅｙ＋ｆ1であり、ここに、ａ及びｂは同じ符号であり、ここにａ、ｂ、ｃ、ｄ、ｅ、ｆは方程式の係数である。これらの係数は、実行時に生成され、パッチごとに変化する。この楕円放物面の頂点の座標は、楕円放物面の部分導関数をゼロに設定し、以下の方程式、
【００５０】
【数７】
0005336607.tif 000008
【００５１】
及び
【００５２】
【数８】
0005336607.tif 000009
【００５３】
を使用することで決定することができる。
【００５４】
上記の方程式は、楕円放物面の頂点のｘ及びｙ座標を得るために解かれる。ｘ及びｙの値は、以下のようにして得られる。即ち、
【００５５】
【数９】
0005336607.tif 000010
【００５６】
【数１０】
0005336607.tif 000011
【００５７】
であって、ここに、４ａｂ−ｃ2≠０である。
【００５８】
特徴点の周囲の所定の領域が楕円放物面で効果的に近似されない事例が存在する可能性がある。これは、頂点のｘ及びｙ座標を照査することで決定される。サブピクセル座標が中心ピクセルから１ピクセルより大きく離れている場合、サブピクセル座標を放棄して、特徴点の積分座標を使用する。
【００５９】
楕円放物面の頂点のサブピクセルｘ座標及びｙ座標を決定するため、楕円放物面の６つの係数を決定する。３×３ボックスは、９つの拘束を提供するので、係数を決定するために、最小二乗法を適用する。９つの拘束は、まとめて、Ａｘ＝ｂで表示することができ、以下の、
【００６０】
【数１１】
0005336607.tif 000012
【００６１】
の形態を有しており、ここに、ｘ1及びｙ1は、３×３ボックス内に存在するピクセルの座標である。座標ｘ1及びｙ1は、ボックスの中心と相対的であり、実際の座標は、ボックスの中心の絶対座標をｘ1及びｙ1座標に加算することで得ることができる。上記の方程式にｘ1及びｙ1の値を置換した後、以下の行列方程式、
【００６２】
【数１２】
0005336607.tif 000013
【００６３】
を得る。上記の行列方程式を解くために、以下の式、ｘ＝（ＡTＡ）-1ＡTｂ＝Ａ*ｂを使用することができる。行列Ａ*は、Ａ行列が周知であるので、
【００６４】
【数１３】
0005336607.tif 000014
【００６５】
と計算することができる。行列Ａ*を、楕円放物面の係数を算出するために使用する。この後、係数を、楕円放物面の頂点の座標を算出するために使用する。
【００６６】
特徴点のサブピクセル場所を算出した後、特徴点の配向を、ステップ３１０で決定する。特徴点の配向は、画像マッチングアルゴリズムが同じ画像の回転された異形をマッチングすることができるようにする。特徴点は、それらと関連付けられる１つより多い配向を有していてもよい。配向計算アルゴリズム一式を使用して、特徴点の配向一式を計算する。
【００６７】
第１の配向計算アルゴリズムは、配向を決定するために補間勾配法を使用する。この方法では、画像導関数Ｉx及びＩyは、ステップ３０８で計算されたサブピクセル場所で補間される。その後、配向を算出するために、四象限逆正接をサブピクセル場所で算出する。
【００６８】
第２の配向計算アルゴリズムは、画像上で平滑化作業を行うことで配向を計算する。平滑化作業は、ガウス関数を使用することによって行うことができる。本発明の一実施形態では、ガウス関数の尺度パラメータは、５である。この後、補間勾配画像法を、第１の配向計算アルゴリズムで説明したように、配向を得るために平滑化された画像に適用する。平滑化作業のおかげで、本方法の空間的な有効範囲は、パッチの大きさと概ね同じになる。
【００６９】
第３の配向計算アルゴリズムは、配向ヒストグラムを形成することで配向を計算する。配向ヒストグラムは、３６０度の配向の範囲に亘って３６のビンを有している。従って、１つのビンは、１０度の幅を有している。パッチを、特徴点の周囲で選択し、ガウス重量を、パッチ全体に適用する。その後、パッチの中の各点における画像勾配を、配向ヒストグラムのそれに対応するビンに対してマッピングする。画像勾配のビンへの貢献は、その点における勾配の大きさとガウス重量の積に相当する。配向ヒストグラムの全体が特徴点に関して完成されると、ヒストグラムの最高頂点及び最高頂点の少なくとも８５％の高さである他の頂点が識別される。それらの頂点は、特徴点での配向の支配的価値を表している。従って、配向ヒストグラム法は、特徴点毎に複数の配向をもたらすことができる。更に、頂点の正確な値を決定するために、ヒストグラムの各頂点値の場所を特定する。各頂点の場所特定は、放物線を各頂点に近い一連のヒストグラム値に嵌め合わせることで行われる。
【００７０】
上述の３つの方法の何れのものでも、特徴点の配向を決定するために使用することができる。しかしながら、配向を決定するために、２つ又は３つ全ての方法を使用する事象もあり得る。この場合、１つの特徴点に関して配向の複数の値を得る。それらの配向の幾つかは、互いに近接している場合がある。互いが所定の角距離以内にある配向の群は、配向の群の平均で置換される。本発明の実施形態では、２つ又はそれ以上の配向が互いから２０度の範囲内にある場合、それらの２つ又はそれ以上の配向は、２つ又はそれ以上の配向の平均値に相当する単一の配向に置換される。２０度範囲が３６０度配向を包含する時、角度のラップアラウンドが考えられる。
【００７１】
特徴点及びそれらの配向を決定した後、ステップ３１２で、特徴点を包含する画像のパッチを特徴点の周囲で抽出する。パッチは、画像勾配から抽出され、パッチは、対応する特徴点を包含している。より具体的には、特徴点は、パッチの中心に位置しており、パッチの大きさは、１６×１６である。これは、パッチの例証的な値であり、任意の他の適切な値を使用することもできる。画像の特徴点及び所定のサンプリング因子の配向に基づいて勾配をサンプリングすることで、パッチを抽出する。勾配は、複数の決定された位置でサンプリングされ、特徴点の配向及び所定のサンプリング因子に基づいて決定される。より具体的には、特徴点の配向は、例えばパッチの配向の方向にある正のｘ軸を選ぶことで、座標基準フレームを決定する。勾配画像のサンプルの間隔は、所定のサンプリング因子の値に等しく、それはオクターブ内の位置に等しい。例えば、オクターブに対する中間尺度が
【００７２】
【数１４】
0005336607.tif 000015
【００７３】
である場合、サンプルは、１．１９ピクセル離れているであろう。
【００７４】
特徴点が画像の境界に近接した位置にある場合、パッチの一部は、画像の境界の外側に位置している場合がある。画像表現にその様な特徴点の貢献を含めるため、画像の境界に沿って、画像に追加の白色ピクセルでパディングする。白は、例示的な色であり、他の色を使用してもよいことに留意されたい。
【００７５】
特徴点の周囲でパッチを抽出した後、特徴ベクトルをパッチに対して画定する。特徴ベクトルを画定するため、ステップ３１４ではパッチを幾つかの小パッチに分割する。本発明の一実施形態では、パッチを、各々の大きさが４×４ピクセルである４×４グリッドの小パッチに分割する。パッチの分割は、正確なやり方でパッチの様々な部分の相対的な位置関係を表現できるように行われる。その後、小パッチに対応する成分をステップ３１６で抽出する。各小パッチは、４成分を有する。４成分の各々は、対応する小パッチの中に存在する画像勾配から算出される。第１の成分は、画像の小パッチの中に存在する全ての正のｘ導関数の合計である。第２の成分は、画像の小パッチの中に存在する全ての負のｘ導関数の合計の負数である。第３の成分は、画像の小パッチの中に存在する全ての正のｙ導関数の合計である。第４の成分は、画像の小パッチの中に存在する全ての負のｙ導関数の合計の負数である。４成分は、
【００７６】
【数１５】
0005336607.tif 000016
【００７７】
と表現することができる。これらの４成分は、次に、特徴点に対応する単一の６４次元特徴ベクトルを画定するために小パッチにわたって連結される。
【００７８】
特徴点の特徴ベクトルを得た後、ステップ３１８で特徴ベクトルは標準化される。標準化は、特徴ベクトルの幾つかの高い値の成分が全特徴ベクトルを占めることを回避するために行われる。高コントラストエッジが特徴点の周囲のパッチの中に存在する状況があり得る。この場合、特徴ベクトルは、大きい値を有する数少ない成分を有するであろう。その様な特徴ベクトルは、少数の大きい成分が存在する時には小さい成分が無視されるという理由から、画像マッチングに対してより低いロバスト性を有しているであろう。当該特徴ベクトルは、更に、コントラストの全般的な変化に対して感受性を持つであろう。
【００７９】
１つの実施形態における本発明は、パッチの特徴ベクトルを標準化するために、高速集束比を有する反復手順を使用している。反復手順の第１のステップでは、値が所定の閾値を上回っている全ての成分は、所定の閾値まで下げられる。第２のステップでは、値が所定の閾値より小さい成分は、計算された長さに標準化される。計算された長さは、所定の閾値及び第１のステップが行われた後、所定の閾値と等しい値を有する成分の数に基づいて決定される。本発明の一実施形態では、計算された長さは、
【００８０】
【数１６】
0005336607.tif 000017
【００８１】
に等しく、ここに、ｔは、所定の閾値であり、ｎは、所定の閾値の値の成分の数である。所定の閾値の値は、特有の適用の要件に従って選ばれてもよい。第２のステップは、全ての特徴ベクトルが単位長さのものであることを確実にすることに留意されたい。更に、第１及び第２のステップは、全ての成分が所定の閾値以下になるまで反復される。この要件は、浮動小数点値を単一バイトに効果的に圧縮する場合には望ましい。
【００８２】
特徴点、配向及び特徴ベクトルを決定するための上述のステップは、ピラミッド画像上で行われる。従って、好ましくは各ピラミッド画像上の特徴点は識別され、それらの配向及び特徴ベクトルが計算される。ステップ３２０では、ピラミッド画像の特徴点、配向及び特徴ベクトルに基づいて画像が表現される。
【００８３】
図５は、本発明の様々な実施形態によって、画像を表現するために使用されるシステムの要素を図示するブロック図である。システムは、数多くの画像マッチングシナリオで画像を表現するために使用することができる。システムは、入力として画像を取り込み、画像を他の画像とマッチングすることを容易にする画像の表現を生成する。図５は、特徴点識別モジュール（ＦＰＩＭ）５０２、配向決定モジュール（ＯＤＭ）５０４、抽出モジュール（ＥＭ）５０６、特徴ベクトル決定モジュール（ＦＶＤＭ）５０８及びデータベース（ＤＢ）５１０を含んでいる。ＦＰＩＭ５０２は、画像の中の特徴点を識別するために使用される。ＯＤＭ５０４及びＥＭ５０６は、特徴点の配向を決定し、かつそれらの特徴点の周囲でパッチを抽出するために、それらの特徴点をそれぞれ使用している。ＦＶＤＭ５０８は、それらのパッチに対応する特徴ベクトルを決定するためにＥＭ５０６で抽出されたパッチを使用している。更に、ＤＢ５１０は、全ての、特徴点、それらの配向及び特徴ベクトルを記憶するために使用される。
【００８４】
ＦＰＩＭ５０２は、画像の中の特徴点を識別するために使用される。ＦＰＩＭ５０２は、ハリスコーナー測度モジュール（ＨＣＭＭ）５１２及び最大値識別モジュール（ＭＩＭ）５１４を含んでいる。ＨＣＭＭは、画像の各点でハリスコーナー測度を計算するために使用される。ハリスコーナー測度は、点の「重要さ」を表現しており、図３のステップ３０２に記載されるように計算される。更に、ＭＩＭ５１４は、ＨＣＭＭで計算されるような、ハリスコーナー測度が局所的最大値を有する一連の点を識別するために使用される。ハリスコーナー測度の局所的最大値は、図３のステップ３０４に記載されるように識別される。局所的最大値を有する一連の点は、画像の特徴点として識別される。
【００８５】
特徴点を識別した後、特徴点選択モジュール（ＦＰＳＭ）５１６は、特定の数の特徴点をＦＰＩＭ５０２によって識別された特徴点から選択するために使用される。ＦＰＳＭは、図３のステップ３０６に記載されるように特徴点を選択する。更に、位置推定モジュール（ＰＥＭ）５１８は、選択された特徴点の位置を推定するために使用される。ＰＥＭは、楕円放物面を特徴点を包含する所定の領域に嵌め合わせることによって特徴点の位置を推定する。ＰＥＭは、図３のステップ３０８に記載するように特徴点の位置を推定する。
【００８６】
ＯＤＭ５０４は、入力としてＥＰＩＭ５０２によって識別された特徴点を取り込み、図４のステップ３１０に記載するように、特徴点の配向を決定する。配向は、配向計算アルゴリズム一式に基づいて決定される。ＯＤＭ５０４は、配向計算モジュール５２０一式を含んでいる。各各配向計算モジュールは、対応する配向計算アルゴリズムを使用することによって特徴点の配向を算出する。ＯＤＭ５０４は、所定の角距離の中に位置する配向の群を配向の群の平均値と置換するために置換モジュール５２２を更に含んでいる。
【００８７】
ＥＭ５０６は、入力として、ピラミッド画像と、各々がＯＤＭ５０４によって識別された対応する単数又は複数の配向を有するＦＰＩＭ５０２によって識別された特徴点と、を取り込む。ＥＭ５０６は、図４のステップ３１２に記載するように、特徴点の周囲でパッチを抽出する。更に、ＥＭ５０６は、画像に追加のピクセルでパディングすることによって画像の境界に存在するパッチを抽出する。
【００８８】
ＥＭ５０６によって抽出されたパッチは、パッチに対応する特徴ベクトルを画定するためにＦＶＤＭ５０８によって使用される。ＦＶＤＭ５０８は、パッチ分割モジュール（ＰＤＭ）５２４及び成分算出モジュール（ＣＣＭ）５２６を含んでいる。ＰＤＭは、図４のステップ３１４に記載するように、パッチを幾つかの小パッチに分割するために使用される。その後、ＣＣＭは、ＰＤＭによって生成された小パッチに対応する特徴ベクトルの成分を算出する。ＣＣＭは、図４のステップ３１６に記載するように成分を算出する。
【００８９】
ＦＶＤＭ５０８によって画定された特徴ベクトルは、標準化モジュール５２８によって標準化される。標準化は、特徴ベクトルの幾つかの高い値の成分が全特徴ベクトルを占めることを回避するために行われる。標準化モジュール５２８は、図４のステップ３１８に記載するように特徴ベクトルを標準化する。
【００９０】
ＦＰＩＭ５０２、ＯＤＭ５０４及びＦＶＤＭ５０８の出力として得られたピラミッド画像の特徴点及び特徴ベクトルは、ＤＢ５１０に記憶される。それらの特徴点及び特徴ベクトルは、画像を表現するため及び幾つかの画像を互いにマッチングするために集合的に使用される。
【００９１】
本発明の様々な実施形態によれば、本発明は、画像を効果的に表現するための方法を提供する。方法は、数多くの特徴点が画像の中に存在する場合、特定の数の特徴点を知的に選ぶ。従って、多すぎる特徴点を有する画像も、同様に、本発明の方法を使用して記載することができる。更に、方法は、特徴点の不必要な配向を削除するために特徴点の配向を知的に組み合わせる。不必要な配向の削除は、方法全体の複雑さを低減する。更に、特徴点の周囲で抽出されたパッチは、特徴点の配向及び画像のサンプリング因子に基づいてサンプリングされる。この種のサンプリングは、画像の大きさが尺度の間で変わらない時、尺度変化を補正する。更に、方法は、画像を表現しながらも、更に画像の境界パッチを考慮する。境界パッチを含むことは、画像のより正確かつ完全な表現をもたらす。方法は、パッチを画定するために使用される特徴ベクトルの成分は、非常に大きいわけではないことも、確実にする。従って、特徴ベクトルの成分の全てが、画像表現に有意的に貢献している。
【００９２】
本発明に記載するような、画像を表現するためのシステム又はその構成要素の何れかを、コンピュータシステムと共に使用するためのコンピュータプログラム製品の形態で組み込んでもよい。コンピュータプログラム製品は、画像を表現するために、その中に組み込まれたコンピュータ可読コードを有するコンピュータ使用可能媒体を有している。コンピュータシステムの典型的な例は、汎用コンピュータ、プログラム済みマイクロプロセッサ、マイクロコントローラ、周辺集積回路素子及び本発明の方法を構成するステップを実施することができる他の装置又は装置の配置を含んでいる。
【００９３】
コンピュータシステムは、典型的には、コンピュータ、入力装置及びディスプレイユニットを備えている。コンピュータは、マイクロプロセッサを更に備えている。マイクロプロセッサは、通信バスに接続されている。コンピュータは、メモリを更に含んでいる。メモリは、ランダムアクセスメモリ（ＲＡＭ）又は読み取り専用メモリ（ＲＯＭ）であってもよい。コンピュータシステムは、ハードディスクドライブ又はフロッピディスクドライブ、光ディスクドライブなどのようなリムーバブル記憶ドライブであってもよい、記憶装置をさらに備える。記憶装置は、コンピュータプログラム又は他の命令をコンピュータシステムへロードする他の類似の手段であってもよい。コンピュータシステムは、通信ユニットも含む。通信ユニットは、コンピュータが入出力（Ｉ／Ｏ）インターフェイスを通じて他のデータベース及びインターネットに接続することを可能にし、他のデータベースからデータの送受信ができる。通信ユニットは、モデム、イーサネットカード又はコンピュータシステムがデータベース及びＬＡＮ、ＭＡＮ、ＷＡＮ及びインターネットなどのネットワークに接続することができるようにする任意の他の類似の装置を含んでいてもよい。コンピュータシステムは、Ｉ／Ｏインターフェイスを通じてシステムにアクセス可能な、入力装置を介したユーザーからの入力を容易にする。
【００９４】
コンピュータシステムは、入力データを処理するために１つ又はそれ以上の記憶要素に記憶される命令一式を実行する。記憶要素は、所望によりデータ又は他の情報をも保持してもよい。記憶要素は、処理機械の中に存在する情報源又は物理メモリ要素の形態であってもよい。
【００９５】
プログラム可能な命令は、処理機械に、本発明の方法を構成するステップのような特定のタスクを行うように命令する様々なコマンドを含んでもよい。記載する方法及びシステムは、ソフトウェアプログラミング又はハードウェアだけを使用して又は２つの技法の様々な組み合わせによって実施することもできる。本発明は、コンピュータ内で使用されるプログラミング言語及びオペレーティングシステムから独立している。本発明のための命令は、「Ｃ」、「Ｃ＋＋」、「Ｖｉｓｕａｌ  Ｃ＋＋」及び「Ｖｉｓｕａｌ  Ｂａｓｉｃ」を含むが、これらに限定されない、全てのプログラミング言語で書くことができる。更に、ソフトウェアは、本発明に記載するように、別個のプログラムの集合、大きいプログラムを伴うプログラムモジュール又はプログラムモジュールの一部の形態であってもよい。ソフトウェアは、オブジェクト指向プログラミングの形態のモジュラープログラミングを更に含んでいてもよい。処理機械による入力データの処理は、ユーザーコマンド、以前の処理結果又は別の処理機械によって為された要求に応えてもよい。本発明は、「Ｕｎｉｘ（登録商標）」、「ＤＯＳ」及び「Ｌｉｎｕｘ」を含むが、これらに限定されない、全てのオペレーティングシステム及びプラットフォームでも実施することができる。
【００９６】
プログラム可能命令は、コンピュータ可読媒体上に記憶及び伝送することができる。プログラム可能命令は、更に、搬送波を伝わるデータ信号によって伝送することができる。本発明は、更に、コンピュータ可読媒体、上記の方法及びシステムを実施することができる製品又は数多くの可能なその変換物を備えるコンピュータプログラム製品に組み込むこともできる。
【００９７】
付記項１．画像を表現するための方法であって、画像は、ガウスピラミッドとして表現されており、ガウスピラミッドは、複数のピラミッド画像を備えており、ピラミッド画像は、複数のピクセルを備えている、方法において、
ａ．ピラミッド画像の中の複数のピクセルの間で複数の特徴点を識別することであって、複数の特徴点の内の１つの特徴点は、画像の変換に対して不変的である、特徴点を識別することと、
ｂ．配向計算アルゴリズム一式に基づいてピラミッド画像の中の特徴点の１つ又はそれ以上の配向を決定することと、
ｃ．ピラミッド画像の１つ又はそれ以上の配向及び所定のサンプリング因子に基づいて複数の特徴点を包含する複数のパッチをピラミッド画像から抽出することと、
ｄ．パッチに対する特徴ベクトルを画定することと、
ｅ．ピラミッド画像の複数の特徴点及び特徴ベクトルに基づいて画像を表現することと、から成る方法。
【００９８】
付記項２．ピラミッド画像の境界上に存在する特徴点に対するパッチは、ピラミッド画像に追加のピクセルでパディングすることで抽出される、付記項１の方法。
【００９９】
付記項３．ピラミッド画像は、画像をダウンサンプリングすること及びガウス関数で画像をぼかすことで形成され、ガウス関数は、所定の尺度パラメータで特徴付けられる、付記項１の方法。
【０１００】
付記項４．ピラミッド画像の中の複数のピクセルの間で複数の特徴点を識別することは、
ａ．複数のピクセルの内のピクセルでハリスコーナー測度を計算することと、
ｂ．ハリスコーナー測度が局所的最大値を有する一連の点を識別することであって、識別された一連の点の内の１つの点は特徴点である、一連の点を識別することと、を備えている、付記項１の方法。
【０１０１】
付記項５．ピラミッド画像の複数の特徴点のハリスコーナー測度と所定の尺度パラメータを組み合わせたものに基づいて特定の数の特徴点を選択することを更に備えている、付記項４の方法。
【０１０２】
付記項６．楕円放物面を所定の領域に嵌め合わせることによって特徴点の位置を推定することを更に備えており、所定の領域は、特徴点を包含している、付記項４の方法。
【０１０３】
付記項７．ピラミッド画像の特徴点の１つ又はそれ以上の配向を決定することは、
ａ．配向計算アルゴリズム一式を使用して特徴点に対する一連の配向を計算することと、
ｂ．互いの所定の角距離の中にある配向の群を一連の配向の平均値で置換することと、を備えている、付記項１の方法。
【０１０４】
付記項８．特徴点の周囲でパッチをピラミッド画像から抽出することは、複数の決定された位置でピラミッド画像の勾配をサンプリングすることを備えており、複数の決定された位置は、ピラミッド画像の１つ又はそれ以上の配向及び所定のサンプリング因子に基づいて決定される、付記項１の方法。
【０１０５】
付記項９．パッチ用の特徴ベクトルを画定することは、
ａ．パッチを複数の小パッチに分割することと、
ｂ．複数の小パッチの内の１つの小パッチに対応する特徴ベクトルの成分を算出することと、を備えている、付記項１の方法。
【０１０６】
付記項１０．小パッチに対応する特徴ベクトルの成分は、
ａ．小パッチの中に存在するピラミッド画像の全ての正のｘ導関数の合計である、第１の成分と、
ｂ．小パッチの中に存在するピラミッド画像の全ての負のｘ導関数の合計の負数である、第２の成分と、
ｃ．小パッチの中に存在するピラミッド画像の全ての正のｙ導関数の合計である、第３の成分と、
ｄ．小パッチの中に存在するピラミッド画像の全ての負のｙ導関数の合計の負数である、第４の成分と、を備えている、付記項９の方法。
【０１０７】
付記項１１．パッチの特徴ベクトルを標準化することを更に備えている、付記項１の方法。
【０１０８】
付記項１２．特徴ベクトルを標準化することは、
ａ．所定の閾値より小さい値を有する最初の特徴ベクトルの成分を決定することと、
ｂ．計算された長さに対する所定の閾値より小さい値を有する成分を標準化することと、を備えている、付記項１１による方法。
【０１０９】
付記項１３．計算された長さは、所定の閾値及び所定の閾値より大きい値を有する成分の数に基づいて計算される、付記項１２の方法。
【０１１０】
付記項１４．最初の特徴ベクトルの成分を減らし且つ所定の閾値より小さい値を有する成分を標準化するステップは、所定の閾値より大きい値を有する成分がなくなるまで反復される、付記項１３の方法。
【０１１１】
付記項１５．画像を表現するための方法であって、画像は、ガウスピラミッドとして表現されており、ガウスピラミッドは、複数のピラミッド画像を備えており、ピラミッド画像は、複数のピクセルを備えている、方法において、
ａ．ピラミッド画像の中の複数のピクセルの間で複数の特徴点を識別することであって、複数の特徴点の内の１つの特徴点は、画像の変換に対して不変的である、特徴点を識別することと、
ｂ．配向計算アルゴリズム一式に基づいてピラミッド画像の中の特徴点の１つ又はそれ以上の配向を決定することと、
ｃ．ピラミッド画像の１つ又はそれ以上の配向及び所定のサンプリング因子に基づいて特徴点を包含するパッチをピラミッド画像から抽出することと、
ｄ．パッチに対する特徴ベクトルを画定することと、
ｅ．パッチの特徴ベクトルを標準化することであって、標準化することは、
ｆ．所定の閾値より大きい値を有する特徴ベクトルの成分を所定の閾値まで減らすことと、
ｇ．所定の閾値より小さい値を有する特徴ベクトルの成分を計算された長さに標準化することであって、計算された長さは、所定の閾値及び所定の閾値より小さくない値を有する成分の数に基づいて計算される、成分を標準化することと、を備えている標準化することと、
ｈ．ピラミッド画像の複数の特徴点及びそれらの対応する特徴ベクトルに基づいて画像を表現することと、から成る方法。
【０１１２】
付記項１６．ピラミッド画像は、画像をダウンサンプリングすること及びガウス関数で画像をぼかすことによって形成され、ガウス関数は、所定の尺度パラメータで特徴付けられる、付記項１５の方法。
【０１１３】
付記項１７．ピラミッド画像の中の複数のピクセルの間で複数の特徴点を識別することは、
ａ．複数のピクセルの内の１つのピクセルでハリスコーナー測度を計算することと、
ｂ．ハリスコーナー測度が局所的最大値を有する一連の点を識別することであって、識別された一連の点の内の１つの点は、特徴点である、一連の点を識別することと、を備えている、付記項１５の方法。
【０１１４】
付記項１８．ピラミッド画像の複数の特徴点のハリスコーナー測度と所定の尺度パラメータの組み合わせに基づいて特定の数の特徴点を選択することを更に備えている、付記項１７の方法。
【０１１５】
付記項１９．楕円放物面を所定の領域に嵌め合わせることによって特徴点の位置を推定することを更に備えており、所定の領域は、特徴点を包含している、付記項１７の方法。
【０１１６】
付記項２０．ピラミッド画像の中の特徴点の１つ又はそれ以上の配向を決定することは、
ａ．配向計算アルゴリズム一式を使用することによって特徴点に対する一連の配向を計算することと、
ｂ．互いの所定の角距離の中にある配向の群を一連の配向の平均値で置換することと、を備えている、付記項１５の方法。
【０１１７】
付記項２１．ピラミッド画像の境界上に存在する特徴点に対するパッチは、ピラミッド画像に追加のピクセルでパディングすることによって抽出される、付記項１５の方法。
【０１１８】
付記項２２．特徴点の周囲でパッチをピラミッド画像から抽出することは、複数の決定された位置でピラミッド画像の勾配をサンプリングすることを備えており、複数の決定された位置は、ピラミッド画像の１つ又はそれ以上の配向及び所定のサンプリング因子に基づいて決定される、付記項１５の方法。
【０１１９】
付記項２３．パッチに対する特徴ベクトルを画定することは、
ａ．パッチを複数の小パッチに分割することと、
ｂ．小パッチの内の１つのパッチに対応する特徴ベクトルの成分を算出することと、を備えている、付記項１５の方法。
【０１２０】
付記項２４．小パッチに対応する特徴ベクトルの成分は、
ａ．、小パッチの中に存在するピラミッド画像の全ての正のｘ導関数の合計である、第１の成分と、
ｂ．小パッチの中に存在するピラミッド画像の全ての負のｘ導関数の合計の負数である、第２の成分と、
ｃ．小パッチの中に存在するピラミッド画像の全ての正のｙ導関数の合計である、第３の成分と、
ｄ．小パッチの中に存在するピラミッド画像の全ての負のｙ導関数の合計の負数である、第４の成分と、を備えている、付記項２３の方法。
【０１２１】
付記項２５．最初の特徴ベクトルの成分を減らし且つ所定の閾値より小さい値を有する成分を標準化するステップは、所定の閾値より大きい値を有する成分がなくなるまで反復される、付記項１５の方法。
【０１２２】
付記項２６．画像を表現するためのシステムであって、画像は、ガウスピラミッドとして表現され、ガウスピラミッドは、複数のピラミッド画像を備えており、ピラミッド画像は、複数のピクセルを備えている、システムにおいて、
ａ．ピラミッド画像の中で複数の特徴点を識別するための特徴点識別モジュールと、
ｂ．ピラミッド画像の中の特徴点識別モジュールによって識別された特徴点の１つ又はそれ以上の配向を決定するための配向決定モジュールであって、配向計算アルゴリズム一式に基づき１つ以上の配向が決定される、配向決定モジュールと、
ｃ．ピラミッド画像の１つ又はそれ以上の配向及び所定のサンプリング因子に基づいて複数の特徴点を包含する複数のパッチをピラミッド画像から抽出するための抽出モジュールと、
ｄ．抽出モジュールにより抽出されたパッチに対する特徴ベクトルを定義するように構成される特徴ベクトル決定モジュールと、
ｅ．ピラミッド画像の複数の特徴点及び特徴ベクトルを記憶するためのデータベースと、を備えているシステム。
【０１２３】
付記項２７．ピラミッド画像の境界上に存在する特徴点に対するパッチは、ピラミッド画像に追加のピクセルでパディングすることによって抽出される、付記項２６のシステム。
【０１２４】
付記項２８．特徴点識別モジュールは、
ａ．複数のピクセルでハリスコーナー測度を計算するためのハリスコーナー測度モジュールと、
ｂ．ハリスコーナー測度モジュールによって計算されたハリスコーナー測度が、そこにおいて局所的最大値を有する一連の点を識別するための最大値識別モジュールであって、識別された一連の点の内の点は特徴点である、最大値識別モジュールと、を備えている、付記項２６のシステム。
【０１２５】
付記項２９．ピラミッド画像の複数の特徴点の内の１つの特徴点のハリスコーナー測度及び所定の尺度パラメータの組み合わせに基づいて特定の数の特徴点を選択するための特徴点選択モジュールを更に備えている、付記項２８のシステム。
【０１２６】
付記項３０．楕円放物面を所定の領域に嵌め合わせることによって特徴点の位置を推定するための位置推定モジュールを更に備えており、所定の領域は特徴点を包含している、付記項２６のシステム。
【０１２７】
付記項３１．配向決定モジュールは、
ａ．特徴点に対する一連の配向を計算するための配向計算モジュール一式と、
ｂ．互いの所定の角距離の中にある配向の群を配向の群の平均値で置換するための置換モジュールと、を備えている付記項２６のシステム。
【０１２８】
付記項３２．特徴ベクトル決定モジュールは、
ａ．パッチを複数の小パッチに分割するためのパッチ分割モジュールと、
ｂ．複数の小パッチに対応する特徴ベクトルの成分を算出するための成分算出モジュールと、を備えている、付記項２６のシステム。
【０１２９】
付記項３３．パッチに対する特徴ベクトルを標準化するための標準化モジュールを更に備えている、付記項２６のシステム。
【０１３０】
付記項３４．コンピュータと共に使用するためのコンピュータプログラム製品であって、コンピュータプログラム製品は、画像を表現するためにその中に統合されているコンピュータ可読プログラムコードを有するコンピュータ使用可能媒体内に記憶された一連の命令を備えており、画像は、ガウスピラミッドとして表現されており、ガウスピラミッドは、複数のピラミッド画像を備えており、ピラミッド画像は、複数のピクセルを備えており、コンピュータプログラムコードは、
ａ．ピラミッド画像の中の複数のピクセルの間で複数の特徴点を識別することであって、複数の特徴点の内の１つの特徴点は、画像の変換に対して不変的である、特徴点を識別することと、
ｂ．配向計算アルゴリズム一式に基づいてピラミッド画像の中の特徴点の１つ又はそれ以上の配向を決定することと、
ｃ．ピラミッド画像の１つ又はそれ以上の配向及び所定のサンプリング因子に基づいて特徴点を包含するパッチをピラミッド画像から抽出することと、
ｄ．パッチに対する特徴ベクトルを画定することと、
ｅ．ピラミッド画像の複数の特徴点及び特徴ベクトルに基づいて画像を表現することと、を行うコンピュータプログラム製品。
【０１３１】
本発明の様々な実施形態を図示及び説明してきたが、本発明は、それらの実施形態だけに限定されるものではないことは明瞭であろう。特許請求の範囲に記載される本発明の精神及び範囲から逸脱すること無しに、数多くの修正、変更、変換、代用及び等価物が当業者には自明であろう。
【図１】
0005336607.tif 000018
【図２】
0005336607.tif 000019
【図３】
0005336607.tif 000020
【図４】
0005336607.tif 000021
【図５】
0005336607.tif 000022