JP4982559B2 - 関心点の記述子を導出する方法 - Google Patents

関心点の記述子を導出する方法 Download PDF

Info

Publication number
JP4982559B2
JP4982559B2 JP2009506997A JP2009506997A JP4982559B2 JP 4982559 B2 JP4982559 B2 JP 4982559B2 JP 2009506997 A JP2009506997 A JP 2009506997A JP 2009506997 A JP2009506997 A JP 2009506997A JP 4982559 B2 JP4982559 B2 JP 4982559B2
Authority
JP
Japan
Prior art keywords
interest
image
point
filter
descriptor
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2009506997A
Other languages
English (en)
Other versions
JP2009535680A (ja
JP2009535680A5 (ja
Inventor
竜士 船山
弘道 柳原
ゴール，ルック ヴァン
トゥイトラールス，ティネ
バイ，ヘルベルト
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Katholieke Universiteit Leuven
Toyota Motor Europe NV SA
Original Assignee
Katholieke Universiteit Leuven
Toyota Motor Europe NV SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Katholieke Universiteit Leuven, Toyota Motor Europe NV SA filed Critical Katholieke Universiteit Leuven
Publication of JP2009535680A publication Critical patent/JP2009535680A/ja
Publication of JP2009535680A5 publication Critical patent/JP2009535680A5/ja
Application granted granted Critical
Publication of JP4982559B2 publication Critical patent/JP4982559B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/40—Extraction of image or video features
    • G06V10/44—Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
    • G06V10/443—Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components by matching or filtering
    • G06V10/446—Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components by matching or filtering using Haar-like filters, e.g. using integral image techniques
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/20—Image preprocessing
    • G06V10/25—Determination of region of interest [ROI] or a volume of interest [VOI]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/20—Image preprocessing
    • G06V10/36—Applying a local operator, i.e. means to operate on image points situated in the vicinity of a given point; Non-linear local filtering operations, e.g. median filtering
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/40—Extraction of image or video features
    • G06V10/46—Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features
    • G06V10/462—Salient features, e.g. scale invariant feature transforms [SIFT]

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Multimedia (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Nonlinear Science (AREA)
  • Image Processing (AREA)
  • Image Analysis (AREA)
  • Error Detection And Correction (AREA)

Description

発明の詳細な説明
〔本発明の分野〕
本発明は、方法および装置に関し、特に画像に作用するコンピュータベースのシステム、特に複数の異なるスケールにおいて複数の異なる回転下において機能する関心点検出および／または記述、例えばスケール不変および回転不変である関心点検出および／または記述に関する方法および装置に関する。本発明はさらに、同一画像内あるいは複数の異なる画像内において関心点をマッチングする装置および方法に関する。本発明はさらに、本発明の方法を実施するソフトウェアに関する。本発明はさらに、フィルタリングされた複数の画像を生成する複数のフィルタリング動作によって生成されるデータ構造に関し、また、例えばメモリ内に記憶またはネットワークを介して転送された、フィルタリングされた複数の画像そのものに関する。本発明はさらに、１つ以上の画像内の関心点の記述子を含むデータ構造であって、例えばメモリ内に記憶またはネットワークを介して転送され、さらに必要に応じて上記のような記述子を、原画または原画から生じる画像（例えばサムネイル画像）に関連付けるデータ構造に関する。
〔技術的背景〕
同一のシーンまたは物体の２つの画像間における対応（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）およびｘによって形成される領域の入力画像Ｉ内における全画素の和を表している。従って、積分画像ＩΣ（ｘ）は、原点がその端点である画像領域での像点Ｉ（ｉ、ｊ）における画素値の和である。この領域は、長方形の領域であってよい。その場合は、次式の通りである：
Figure 0004982559
 （１）
積分画像が計算されると、４つの加法によって、任意の直立した長方形区域における強度の和が計算される。さらに、演算時間は、そのサイズとは無関係である。
積分画像について、画像の長方形部分を参照しながら説明したが、三角形または六角形など他の形状を用いることもできる。また、上記のような積分画像によって容易に処理されるように、本発明のデジタルフィルタを自身の形状に適合させることができる。
関心点検出
ヘッセ行列式および画像ピラミッド
まず、上記検出器について１つのスケールで説明し、続いて上記方法について複数のスケールで説明する。本発明に係る検出器は、その計算および精度における良好な性質ゆえ、ヘッセ行列に基づいている。しかし本発明は、位置およびスケールを選択するに当たり異なる測度を用いるのではなく、位置およびスケールの双方に対して、行列式またはヘッセの近似行列式（approximate determinant）に依存している。画像Ｉ内の点を点ｘ＝（ｘ、ｙ）であるとすると、スケールσにおけるｘ内のヘッセ行列Ｈ（ｘ、σ）は、次式のように定義される：
Figure 0004982559
 （２）
上記Ｌｘｘ（ｘ、σ）は、点ｘ等にデジタルフィルタを適用した結果である。添字ｘｘは、平滑化フィルタの２階微分係数の適用を示している。添字ｘｙは、第１の微分係数が一方の方向にあり、二次微分が他方の方向にある、平滑化フィルタの２階微分係数の適用を示している。基本的な平滑化フィルタは、ガウスのように鐘形であることが好ましい。鐘形とすることによって、点ｘからさらに離れた位置にある画素が、画素に割り当てられたフィルタリングされた値に与える影響が少ないという利点を有している。本発明に係る二次デジタルフィルタは、下記の特徴のうち少なくとも１つを有している：
ａ）平滑化フィルタの２階微分係数に関するデジタルフィルタである
ｂ）鐘形の２階微分係数に関するデジタルフィルタである
ｃ）ガウスの２階微分係数に基づいたフィルタである
ｄ）離散化されたフィルタである
ｅ）クロップされたフィルタである
ｆ）デジタルフィルタの離散的な部分領域によって規定されたローブ（lobe）を有している
ｇ）ボックスフィルタである
ｈ）上記部分領域のローブの形状は、「シルクハット」または「方形パルス」であってよい
ｉ）上記フィルタのうち少なくとも１つは、帯域通過フィルタである。
例えば、Ｌｘｘ（ｘ、σ）は、画像Ｉの点ｘにおける、ガウスの二次微分係数〔数３〕（あるいはその近似値）の畳み込み結果である。同様に、Ｌｘｙ（ｘ、σ）およびＬｙｙ（ｘ、σ）は、画像Ｉの点ｘにおける、ガウスの二次微分係数〔数４〕および〔数５〕（あるいはその近似値）の畳み込み結果である。フィルタＬｘｙ（ｘ、σ）はＬｙｘ（ｘ、σ）に関連しており、一方は他方から導き出すことができる。このため、フィルタリングされた４つの画像を生成するために画像に適用する必要があるデジタル帯域通過フィルタは３つのみである。ガウスは、スケール空間解析には最適であるが、実際には無限大であることができないため、離散化およびクロップされる必要がある。上記のような近似を行った後、図２Ａおよび図２Ｂに概略的に示されている帯域通過フィルタが得られる。各画素点におけるフィルタの値は、グレースケールで符号化されている。グレーは、値ゼロである。黒色は負の値であり、白色は正の値である。図示されているように、フィルタが各画素に対して有している値は１つのみである。すなわち、ガウスの二次微分係数などの連続関数は、画像の一画素の全区域に有効な値に離散化される。また、空間範囲は、無限大から、画素数（例えば、関心点を中心とするＭ×Ｍ画素のマスクサイズ）へと縮小されている。Ｍの値は、中心画素を提供するために奇数であることが好ましい。用いられる場合が多い値は、Ｍ＝９（９×９マスク）である。他の値としては、Ｍ＝１１、Ｍ＝１３、Ｍ＝１５等がある。従来の畳み込み方法では、このサイズは計算速度に影響を及ぼす。Ｍの値が大きいほど、そのマスクを用いた全画像の畳み込みが遅くなる。しかし、本発明の一実施形態では、積分画像を用いることによって、あらゆるフィルタサイズが一定の速度で適用される。
Figure 0004982559
Figure 0004982559
Figure 0004982559
本来であれば、離散化およびクロップによって、画像回転下において再現性が失われるが、本発明において用いられる帯域通過フィルタは有用である。ガウスは鐘形をしており、またガウスの２階微分係数は、１つの中心ローブと、反対符号を有する２つの外部ローブとを有している。図２Ａに見られるように、微分係数がｘ方向に２回取られる、ガウスのデジタルフィルタの離散化およびクロップされた２階微分係数は、中心画素において負の値を有している、すなわち、中心画素付近において負のローブを有しており、中心画素の上下に２つのゼロ交差を形成し、そして正となる。すなわち、中心画素の上下に正のローブが１つ形成される。そして、上記フィルタはゼロとなる。すなわち、上記フィルタは、所定数の画素（例えば第４の画素）後に、中心画素から切り取られる。従って、上記デジタルフィルタは、１つの２値極性（binary polarity）の中心ローブ、２つのゼロ交差、反対の２値極性の２つの外部ローブ、および所定数の画素（例えば３つの画素）を中心画素から加算および減算した空間範囲を有している。上記ｙフィルタも同様であるが、９０°回転されている。図２Ｂには、ｘｙフィルタが概略的に示されている。中心画素は、ゼロ値などの値を有しており、（対角線に沿った）正のｘ−正のｙおよび負のｘ−負のｙ象限内に、２つの正のローブがある。また、（他の対角線に沿った）正のｘ−負のｙおよび負のｘ−正のｙ象限内に、２つの負のローブがある。上記中心画素が、ローブのうちの１つには含まれていない値を有しておらず（例えば、ボックスフィルタ）、フィルタの中心は複数のボックスフィルタの隣接し合う頂点の組み合わせによって形成されていないという事実は、図２Ｂに示されているタイプのフィルタが、図２Ａ、図２Ｃ、および図２Ｅに示されているタイプのフィルタとは異なっていることを意味している。
画像にデジタルフィルタを掛けるために、図２Ａおよび図２Ｂに示されているデジタルフィルタ、および図２Ａに示されているフィルタの回転されたタイプ（あるいは、図２Ｃ、図２Ｄ、および図２Ｅに示されているフィルタ。下記を参照）を用いて、その画素に中心がある各画素に対する新しい値が計算される。そしてこれを、一部または全部の画素に対して再現して、フィルタリングされた画像を生成する。値は、規則的に間隔が空けられた画素において計算することができる。ここでは、これらの画素サンプル間における段（step）が、ナイキスト抽出定理に従うように選択される。
本発明の別の形態では、平滑化フィルタ（例えばガウスフィルタ）の微分係数を近似して、少なくとも１つの帯域通過フィルタを形成することは、離散部分領域を有するデジタルフィルタを用いることによってさらに取られることが好ましい。これらの部分領域は、フィルタ値の離散領域であり、通常は少なくとも、中心画素の周囲に対角線を挟んで対称的に配置されており、例えば図２Ｃ、図２Ｄ、および図２Ｅに示されているように、ボックスフィルタが組み合わせられた形状をしている。これらのボックスは、１よりも大きい所定数の画素に伸びる、単一の正の値または単一の負の値のいずれかを有している。従って、鐘形のローブは、「シルクハット（シルクハット）」または「方形パルス」ローブによって置き換えられている。図２Ｃには、Ｎ個のブロック（例えば３つのブロック）があり、値は白色画素に対して＋１、黒色画素に対して−２であり、これらのフィルタはそれぞれｙおよびｘ方向に用いられる。フィルタの部分領域は、正方形または長方形のボックスとして示されているが、本発明の範囲には他の形状も含まれる。これらは例えば、二次溝付き正方形（quadratic, castellated square）または二次溝付き六角形（quadratic、castellated hexagonal）、溝付き円形（castellated circular）、三角形、六角形等である。本発明では、積分画像処理の使用を可能にする部分領域の形状が特に好ましい。複数のボックスフィルタの組み合わせは、図１に示されているタイプの積分画像の処理において特に容易である。図２Ｄでは、ｘｙフィルタは、フィルタ値（例えばゼロのフィルタ値）を有する中心画素の周囲に対称的に配置された、＋１（白色）または−１（黒色）のいずれかの値を有するＮ’個の画素ブロック（例えば４つの画素ブロック）として示されている。中心画素が、ローブのうちの１つ（例えばボックスフィルタ内）に含まれていない値を有しており、フィルタの中心はボックスフィルタの隣接し合う頂点の接合によって形成されていないという事実は、図２Ｄ（図２Ｂと同様）に示されているタイプのフィルタが、図２Ａ、図２Ｃ、および図２Ｅに示されているタイプのフィルタとは異なることを意味している。また、中心値はゼロであってよい。これは、プラスまたはマイナス１であってよいボックスフィルタの値とは異なる。従って、このフィルタは三値（−１、０、１）デジタルフィルタであり、他のフィルタは二値フィルタである。従って、本発明の一形態は、フィルタ（例えば図２Ａ〜図２Ｅに示されているフィルタ）のうち少なくとも１つは、三値フィルタであるか、あるいはより高値のフィルタ（例えば四値）である。これは、これらのデジタルフィルタのうち少なくとも１つの中心は、いずれかの側に対称的に配置されたボックスフィルタのローブのうちの１つの値ではない値を有する画素であると表現することができる。
本発明は、ｘおよびｙフィルタに対して３つのブロック、およびｘｙ（およびｙｘ）フィルタに対して４つのブロックに限定されるものではなく、用いられるブロック数はこれら以外であってもよい。
上記の説明はボックスフィルタに関するものであるが、本発明はこれに限定されるものではない。各ブロックまたはボックス内のフィルタ値は、（図２Ａおよび図２Ｂに概略的に示されているように）非整数であってもよいが、これによって積分画像を用いることができなくなる。また、フィルタ値は、ブロック内またはブロック毎に異なっていてもよい。しかし、ブロックおよび値が多いほど、フィルタの計算の負荷が高くなる。
図２Ｃ〜図２Ｅに示されているフィルタの一般的な特徴は以下の通りである：
ａ）ｘｙフィルタ（およびｙｘフィルタ）は、中心画素位置から対角線方向にローブを１つのみ有しており、中心画素におけるその値はゼロである。従って、対角線方向に沿って存在するローブは、一方の対角線方向におけるローブと、他方の方向におけるローブとの２つのみである。これらは、中心のゼロ値から増加して、再びゼロまで減少する。あらゆる対角線に沿った２つのローブは、同一の極性を有しており、両方とも正の値を有しているか、あるいは両方とも負の値を有している。一方の対角線方向におけるローブは、他の対角線に沿ったローブとは反対の極性を有している。
ｂ）ｘおよびｙフィルタは、中心ローブの各側にそれぞれ位置する、反対の符号を有する２つのローブと共に、中心画素に中心がある単一のローブを有しており、フィルタ方向がいずれの方向であるのかに応じてｘ軸またはｙ軸のいずれかに沿ってゼロ値まで減少する。
ｃ）全フィルタにおいて、フィルタの全フィルタ値の総和はゼロである。
ｄ）必要に応じて、フィルタ値は整数である。
ｅ）必要に応じて、一ローブのフィルタ値は全て同一であり、ローブ値の形状は「シルクハット」、すなわち長方形である。
近似二次ガウシアン微分に基づいており、また図２Ｃ、図２Ｄ、および図２Ｅに例示されているように複数のボックスフィルタの組み合わせを含んでいるこれらのフィルタは、サイズとは無関係に、すなわちその空間範囲とは無関係に、積分画像を用いて非常に迅速に評価することができる。その性能は、図２Ａおよび図２Ｂに示されている離散化およびクロップされたフィルタに匹敵するか、あるいはこれらよりも優れている。しかし本発明は、これらのフィルタの使用も含んでいる。複数のボックスフィルタの組み合わせは、Ｐ×Ｐ（例えば、図２Ｃおよび図２Ｄに示されているように、９×９フィルタ）の空間範囲を有しており、近似値はガウスから導き出される（例えばσ＝１．２）。ボックスフィルタのこれらの９×９の組み合わせは、スケールの最も低いフィルタとして、すなわち空間分解能の最も高いフィルタとして用いることができる。これらのフィルタは、Ｄｘｘ、Ｏｙｙ、およびＤｊｃｙで表される。Ｐの他の値としては、任意の奇数が適切である。有用な最小のフィルタサイズは９×９であるが、本発明ではこれよりも小さいフィルタを用いることができ（例えば３×３が有用である）、実際には３で割り切れる任意のフィルタサイズを用いることができる。より高いスケールでは、より大きい画像領域を網羅するためにフィルタサイズが拡大される。フィルタサイズは、理論的には、画像そのもののサイズまで拡大することができる。本発明の一実施形態では、Ｐと、全フィルタサイズの近似されたガウス関数の標準的な偏差との比率は一定である。この比率は、例えば７．５（９／１．２）に設定することができるが、１つのスケール分析に対して一定であるのであれば、異なる値の使用も検討することができる。
長方形領域に加えられる重みは、計算効率に対して簡素に維持することができる。ヘッセの行列式に対する式における相対的重みは、平衡されることが好ましい。これは、以下の一般式で規定される通りに行うことができる：
Figure 0004982559
 （３）
上記において、|Ｘ|Ｆはフロベニウスのノルムである。
具体的な例では、上記Ｐは９であり、σは１．２であるため、結果は下記の通りとなる：
Figure 0004982559
（すなわち、約０．９）
上記において、|Ｘ|Ｆはフロベニウスのノルムである。
これによって、ヘッセの近似行列式が以下のように生み出される（方程式２を参照）：
ｄｅｔ（Ｈａｐｐｒｏｘ）＝ＤｘｘＤｙｙ−（０．９Ｄｘｙ）２ （４）
Ｐおよび／またはσの値が変わる場合、この近似公式は変わる。
ヘッセ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）し、関心点に中心を置くことができる。関心点付近の応答が遠くの応答よりも重み付けされる、他の重み付け方法を用いることができる。重み付けとは、応答を、和に加算する前に、関連する関心点からの距離に依存する重み付けアルゴリズムからの値（例えばガウス値）で乗算することを意味している。
上記を要約すると、記述子は、以下の多次元ベクトルｖによって規定することができ、
Figure 0004982559
 （５）
あるいは、ベクトル座標の等価平均値、すなわち、このベクトルの各和が、それを計算するために用いられる応答の数で除算される。ベクトル縦座標は、任意の適切な順番で配置することができる。
あるいは、上記記述子の拡張版が、さらなる特徴を加える。これもまた、前と同一の和を用いるが、これらの値をさらに分割する。ｄxおよび|ｄx|の和は、ｄy＜０またはｄy ≧０に対して別々に計算される。同様に、ｄyおよび|ｄy|の和はｄxの符号に従って分割され、これによって特徴の数が二倍になる。
この記述子は、以下のように記述することができる：
Figure 0004982559
 （６）
あるいは、ベクトル座標の等価平均値、すなわちこのベクトルの各和が、それを計算するために用いられる応答の数で除算される。ベクトル縦座標は、任意の適切な順番で配置することができる。
記述子の次元数は、考慮される部分領域の数に依存しており、また、記述子（例えば、ｄxおよび|ｄ x |>の和）の一部または部分領域が、その符号に従って分割されて、各部分領域の多次元ベクトルとなる。より正確には、ｄxおよび|ｄx|の和は、ｄｙ≦０およびｄｙ＞０に対して別々に計算される。ｄyおよび|ｄy|の和はまた、ｄｘ≦０およびｄｘ＞０に対して別々に計算される。例えば、この記述子は、規則的な４×４部分領域の領域に対して１２８次元の記述子を生み出す。
有効な結果は、他の領域サイズで達成することができる。例えば、２×２部分領域を用いて、拡張された記述子が用いられるか否かに応じて１６次元の記述子または３２次元の記述子を得ることができる。
図８は、画像内の異なる強度パターンに対して上述した記述子の性質を示している。同次領域においては、記述子の全成分は比較的低いままである（図８Ａ）。高周波（図８Ｂ）では、ウェーブレット応答の絶対値の和は高いが、正則和は低いままである。強度が次第に変化している場合、ウェーブレット応答の絶対値の和および正則和が共に比較的高い（図８Ｃ）。この結果、関心点近傍の強度パターンの特徴的な記述が得られ、これは多くの場合、上記の組み合わせである。
記述子（ベクトル（６）参照）は、ベクトル（５）の記述子よりも特徴的であり、計算もそれほど遅くはないが、しかしマッチングが低い。これら２つのタイプの記述子は、「法線」（ベクトル（５））および「拡張」（ベクトル（６））記述子として記述される。
マッチング段階において指標付けをより早くするためには、関心点のコントラストタイプを区別する要素を記述子に導入することが好ましい。例えば、基礎の関心点（underlying interest point）に対するラプラシアンの符号（すなわち、ヘッセのトレース）を記述子内に含ませることができる。ベクトル５および６は、それぞれ以下の通りになる：
Figure 0004982559
 （７）
Figure 0004982559
 （８）
あるいは、ベクトル座標の等価平均値、すなわちこのベクトルの各和が、それを計算するために用いられる応答の数で除算される。上記式において、Ｌはラプラシアンの符号である。ベクトル縦座標は、任意の適切な順番で配置することができる。
ラプラシアンは、ヘッセ行列のトレース（対角和）である。ヘッセ行列については、関心点検出に関して既に説明した。この特徴は、検出段階において既に計算済みであるため、追加的な計算コストの必要なしに得ることができる。本発明に従って、記述子を別の関心点検出器（例えば、ハリス関心点検出器）と組み合わせる場合、ラプラシアンが事前に計算されていることはないため、別々に計算しなければならない。通常、関心点は、ブロブタイプの構造において発見される。ラプラシアンを用いることによって、暗い背景上の明るいブロブを逆の状況から区別する（図９参照）。従って、第３の工程（マッチング段階）においてラプラシアンの符号を用いることによって、特徴が同一タイプのコントラスト（例えば黒色または白色）を有している場合は、それらの特徴のみが比較される。早いタイプは、一部分領域において４つ（あるいは、ラプラシアンが含まれている場合は５つ）の特徴を有しており、拡張されたタイプは８つ（あるいは、ラプラシアンが含まれている場合は９つ）有している。従って、ラプラシアンの符号が含まれている場合、記述子の長さは、早いタイプは６５であり、正確なタイプは１２９である。勾配成分は、照明内のバイアスに対して不変である（オフセット）。コントラストに対する不変性（スケール係数）は、ラプラシアンに関する情報を加える前に、記述子ベクトルを正規化することによって達成される。
これらの記述子を達成するために、いくつかのパラメータを修正する必要があった。選択を最適化するために、これらのパラメータに対して広範囲に渡る試験が行われた。例えば、異なる数のサンプル点および部分領域が試験された。４×４部分領域分割法は、最良の結果をもたらしたが、本発明はこれに限定されるものではない。再分割を細かくするほど強さが弱まり、さらにマッチング時間が増加すると考えられる。一方、３×３部分領域を有する短い記述子は、機能は低いが動作が速く、他の公知の記述子と比較しても全く許容可能である。
実験結果
図１０では、上記パラメータの選択が、標準的な「落書き（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).
本発明の実施形態と共に用いることのできる積分画像の演算方法を示す図である。 図２Ａおよび図２Ｂは、本発明の一実施形態に係る、それぞれｙ方向およびｘｙ方向におけるガウスの２階偏微分を示す離散化およびクロップされたデジタルフィルタを示す図である。図２Ｃ、図２Ｄ、および図２Ｅは、本発明の一実施形態に係る、それぞれｙ方向、ｘｙ方向、およびｘ方向におけるガウスの２階偏微分の近似を示す離散化およびクロップされたデジタルフィルタを示す図である。 本発明の実施形態と共に用いることのできる画像ピラミッドの概略図である。 デジタルフィルタサイズを拡大し、それを初期入力画像へ適用することによってスケール空間が解析される、本発明の一実施形態を示す図である。 ヘッセ行列の近似行列式などの測度の最大が決定される、画像内およびスケール全体における局所近傍の詳細を示す図である。 コントラストを見つけるために本発明の一実施形態において用いられる、コントラストに関連したハールウェーブレットデジタルフィルタを示す図である。 図６Ａは、本発明の一実施形態において、再現可能な向きを決定するために用いられる画像の関心点周囲の離散的円形区域を示す図である。図６Ｂは、本発明の一実施形態において、ウィンドウのための代表ベクトルがいかに得られるかを示す図である。 本発明の一実施形態において、正方形領域が割り当てられた向きにどのように整列されるか、および、この向きに従ってウェーブレット応答がどのように計算されるかを示す図である。 画像内の異なる強度パターンに対する、本発明の実施形態に係る記述子の性質を示す図である。 本発明の一実施形態に従って、ラプラシアンの符号を必要に応じて用いて、明るい背景上の暗いブロブを、逆の状況から区別することができることを示す図である。 本発明に係る方法と公知の方法との実験結果のコントラストを示す図である。 本発明と共に用いることのできる、入力画像を取り込むデジタルカメラを備えた一般的なコンピュータシステムを示す図である。 図１２は、本発明と共に用いることのできるシステムの一実施例として具体的な計算システムを示す図である。

Claims (4)

  1. 複数の画素を有する画像内における、当該画像内における関心点の記述子を導出する方法であって、
    向き決定用ウィンドウ内の関心点近傍の各点について、ｘ方向とｙ方向のそれぞれにおけるデジタルフィルタ応答を求め、ｘ方向とｙ方向とのそれぞれについて該デジタルフィルタ応答の和Ｓｘ、Ｓｙを求め、（Ｓｘ、Ｓｙ）を成分とするベクトルである局所向きベクトルを求め、
    向き決定用ウィンドウの個数分、上記局所向きベクトルを求める処理を繰り返して、局所向きベクトルのうちで最も大きい局所向きベクトルの向きを、この関心点の向きとして決定し、
    上記関心点の向きと平行および垂直なｘ軸およびｙ軸を有する記述子生成用ウィンドウを生成し、この記述子生成用ウィンドウにおいて、１セットの画素を含んでいる、上記関心点の周囲の近傍を識別する工程と、
    上記関心点の向きに対して固定関係（fixed relation）を有している少なくとも１つの方向において、上記関心点の上記近傍におけるコントラストを、少なくとも１つのデジタルフィルタを用いて調べると共に、これによって、各方向に対して独立して、第１のスカラーコントラスト測度（scalar contrast measure）として、ｘ方向とｙ方向のそれぞれにおけるデジタルフィルタ応答ｄｘ、ｄｙを生成する工程と、
    １つの方向のみからの上記第１のスカラーコントラスト測度の組み合わせである第２のスカラーコントラスト測度である第１の要素を含む多次元記述子であって、
    ｄｘの和、ｄｙの和、ｄｘの絶対値の和、ｄｙの絶対値の和、
    をベクトル成分として有する多次元記述子を生成する工程とを含む方法。
  2. 複数の画素を有する画像内における、当該画像内における関心点の記述子を導出する方法であって、
    向き決定用ウィンドウ内の関心点近傍の各点について、ｘ方向とｙ方向のそれぞれにおけるデジタルフィルタ応答を求め、ｘ方向とｙ方向とのそれぞれについて該デジタルフィルタ応答の和Ｓｘ、Ｓｙを求め、（Ｓｘ、Ｓｙ）を成分とするベクトルである局所向きベクトルを求め、
    向き決定用ウィンドウの個数分、上記局所向きベクトルを求める処理を繰り返して、局所向きベクトルのうちで最も大きい局所向きベクトルの向きを、この関心点の向きとして決定し、
    上記関心点の向きと平行および垂直なｘ軸およびｙ軸を有する記述子生成用ウィンドウを生成し、この記述子生成用ウィンドウにおいて、１セットの画素を含んでいる、上記関心点の周囲の近傍を識別する工程と、
    上記関心点の向きに対して固定関係（fixed relation）を有している少なくとも１つの方向において、上記関心点の上記近傍におけるコントラストを、少なくとも１つのデジタルフィルタを用いて調べると共に、これによって、各方向に対して独立して、第１のスカラーコントラスト測度（scalar contrast measure）として、ｘ方向とｙ方向のそれぞれにおけるデジタルフィルタ応答ｄｘ、ｄｙを生成する工程と、
    １つの方向のみからの上記第１のスカラーコントラスト測度の組み合わせである第２のスカラーコントラスト測度である第１の要素を含む多次元記述子であって、
    ｄｙ＜０のときのｄｘの和、ｄｘ＜０のときのｄｙの和、ｄｙ＜０のときのｄｘの絶対値の和、ｄｘ＜０のときのｄｙの絶対値の和、
    ｄｙ≧０のときのｄｘの和、ｄｘ≧０のときのｄｙの和、ｄｙ≧０のときのｄｘの絶対値の和、ｄｘ≧０のときのｄｙの絶対値の和、
    をベクトル成分として有する多次元記述子を生成する工程とを含む方法。
  3. 上記多次元記述子は、上記関心点におけるラプラシアンの符号をベクトル成分の一つとしてさらに有している請求項１または２に記載の方法。
  4. 上記多次元記述子を生成する工程において、
    各和を求める前に、ｄｘ、ｄｙをそれぞれ、関心点付近の応答が遠くの応答よりも重み付けされるように重み付けする請求項１ないし３のいずれか１項に記載の方法。
JP2009506997A 2006-04-28 2007-04-30 関心点の記述子を導出する方法 Active JP4982559B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
EP06447060A EP1850270B1 (en) 2006-04-28 2006-04-28 Robust interest point detector and descriptor
EP06447060.2 2006-04-28
PCT/EP2007/003811 WO2007128452A2 (en) 2006-04-28 2007-04-30 Robust interest point detector and descriptor

Publications (3)

Publication Number Publication Date
JP2009535680A JP2009535680A (ja) 2009-10-01
JP2009535680A5 JP2009535680A5 (ja) 2010-06-24
JP4982559B2 true JP4982559B2 (ja) 2012-07-25

Family

ID=36954920

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2009506997A Active JP4982559B2 (ja) 2006-04-28 2007-04-30 関心点の記述子を導出する方法

Country Status (8)

Country Link
US (2) US8165401B2 (ja)
EP (2) EP1850270B1 (ja)
JP (1) JP4982559B2 (ja)
KR (2) KR101478840B1 (ja)
AT (1) ATE470912T1 (ja)
AU (1) AU2007247520B2 (ja)
DE (1) DE602006014803D1 (ja)
WO (1) WO2007128452A2 (ja)

Families Citing this family (199)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
ATE470912T1 (de) * 2006-04-28 2010-06-15 Toyota Motor Europ Nv Robuster detektor und deskriptor für einen interessenspunkt
US8285118B2 (en) * 2007-07-16 2012-10-09 Michael Bronstein Methods and systems for media content control
KR100944903B1 (ko) * 2008-03-18 2010-03-03 한국전자통신연구원 비디오 신호의 특징 추출 장치 및 그 추출 방법, 비디오인식 시스템 및 그 인식 방법
US8150165B2 (en) 2008-04-11 2012-04-03 Recognition Robotics, Inc. System and method for visual recognition
FR2931277B1 (fr) * 2008-05-19 2010-12-31 Ecole Polytech Procede et dispositif de reconnaissance invariante-affine de formes
US8189945B2 (en) * 2009-05-27 2012-05-29 Zeitera, Llc Digital video content fingerprinting based on scale invariant interest region detection with an array of anisotropic filters
US8195689B2 (en) 2009-06-10 2012-06-05 Zeitera, Llc Media fingerprinting and identification system
US8233716B2 (en) * 2008-06-27 2012-07-31 Palo Alto Research Center Incorporated System and method for finding stable keypoints in a picture image using localized scale space properties
US8233722B2 (en) 2008-06-27 2012-07-31 Palo Alto Research Center Incorporated Method and system for finding a document image in a document collection using localized two-dimensional visual fingerprints
JP4670976B2 (ja) * 2008-10-03 2011-04-13 ソニー株式会社 学習装置および方法、認識装置および方法、プログラム、並びに記録媒体
US8537409B2 (en) * 2008-10-13 2013-09-17 Xerox Corporation Image summarization by a learning approach
KR101522985B1 (ko) * 2008-10-31 2015-05-27 삼성전자주식회사 영상처리 장치 및 방법
KR101323439B1 (ko) 2008-11-12 2013-10-29 보드 오브 트러스티스 오브 더 리랜드 스탠포드 주니어 유니버시티 특징 디스크립터를 표현하고 식별하는 방법, 장치 및 컴퓨터 판독가능 저장 매체
US8406507B2 (en) * 2009-01-14 2013-03-26 A9.Com, Inc. Method and system for representing image patches
US20100189368A1 (en) * 2009-01-23 2010-07-29 Affine Systems, Inc. Determining video ownership without the use of fingerprinting or watermarks
US8818024B2 (en) 2009-03-12 2014-08-26 Nokia Corporation Method, apparatus, and computer program product for object tracking
US8548193B2 (en) 2009-09-03 2013-10-01 Palo Alto Research Center Incorporated Method and apparatus for navigating an electronic magnifier over a target document
FR2950451B1 (fr) 2009-09-18 2011-11-04 Imra Europ Sas Algorithme de detection des points de contour dans une image
WO2011048497A2 (en) * 2009-10-19 2011-04-28 National University Of Singapore Computer vision based hybrid tracking for augmented reality in outdoor urban environments
US8687891B2 (en) 2009-11-19 2014-04-01 Stanford University Method and apparatus for tracking and recognition with rotation invariant feature descriptors
JP5714599B2 (ja) 2009-12-02 2015-05-07 クゥアルコム・インコーポレイテッドＱｕａｌｃｏｍｍ Ｉｎｃｏｒｐｏｒａｔｅｄ イメージ認識のための記述子パッチの高速部分空間射影
US9712852B2 (en) * 2010-01-08 2017-07-18 Fatehali T. Dharssi System and method for altering images in a digital video
EP2629519A1 (en) * 2010-02-05 2013-08-21 Siemens Aktiengesellschaft A method and an apparatus for difference measurement of an image
US8798377B2 (en) 2010-02-08 2014-08-05 Telefonica, S.A. Efficient scale-space extraction and description of interest points
US8509526B2 (en) * 2010-04-13 2013-08-13 International Business Machines Corporation Detection of objects in digital images
US9530073B2 (en) * 2010-04-20 2016-12-27 Qualcomm Incorporated Efficient descriptor extraction over multiple levels of an image scale space
US8538205B2 (en) * 2010-05-14 2013-09-17 Mobileye Technologies Ltd. Multi-function summing machine
US20110293189A1 (en) * 2010-05-28 2011-12-01 Microsoft Corporation Facial Analysis Techniques
ES2384928B1 (es) 2010-06-25 2013-05-20 Telefónica, S.A. Método y sistema para la identificación rápida y robusta de productos específicos en imágenes.
JP5578965B2 (ja) * 2010-07-02 2014-08-27 富士フイルム株式会社 オブジェクト推定装置および方法ならびにプログラム
EP2407910B1 (de) 2010-07-14 2018-09-26 Deutsche Telekom AG Verfahren und Vorrichtung zum Erstellen einer Objekt-Datenbank und zum Auffinden von Objekten
US8971632B2 (en) 2010-08-19 2015-03-03 Sharp Laboratories Of America, Inc. System for feature detection for low contrast images
KR101715781B1 (ko) * 2010-08-31 2017-03-13 삼성전자주식회사 물체 인식 시스템 및 그 물체 인식 방법
JP2012053653A (ja) * 2010-09-01 2012-03-15 Nippon Hoso Kyokai <Nhk> 画像特徴点検出装置および画像特徴点検出プログラム
EP2617012B1 (en) 2010-09-16 2015-06-17 Mor Research Applications Ltd. Method and system for analyzing images
US9483677B2 (en) 2010-09-20 2016-11-01 Hid Global Corporation Machine-readable symbols
US8544747B2 (en) 2010-09-20 2013-10-01 Lumidigm, Inc. Machine-readable symbols
US8781234B2 (en) 2010-10-01 2014-07-15 Intel Corporation Optimized fast hessian matrix computation architecture
US9317133B2 (en) 2010-10-08 2016-04-19 Nokia Technologies Oy Method and apparatus for generating augmented reality content
US8548237B2 (en) 2010-10-18 2013-10-01 Hewlett-Packard Development Company, L.P. Ordinal and spatial local feature vector based image representation
US8554021B2 (en) 2010-10-19 2013-10-08 Palo Alto Research Center Incorporated Finding similar content in a mixed collection of presentation and rich document content using two-dimensional visual fingerprints
US8750624B2 (en) 2010-10-19 2014-06-10 Doron Kletter Detection of duplicate document content using two-dimensional visual fingerprinting
US8965130B2 (en) * 2010-11-09 2015-02-24 Bar-Ilan University Flexible computer vision
US8639034B2 (en) 2010-11-19 2014-01-28 Ricoh Co., Ltd. Multimedia information retrieval system with progressive feature selection and submission
JP5603258B2 (ja) * 2011-01-13 2014-10-08 パナソニック インテレクチュアル プロパティ コーポレーション オブ アメリカ 検出装置及び検出方法
US9057783B2 (en) * 2011-01-18 2015-06-16 The United States Of America As Represented By The Secretary Of The Army Change detection method and system for use in detecting moving targets behind walls, barriers or otherwise visually obscured
KR101165357B1 (ko) 2011-02-14 2012-07-18 (주)엔써즈 이미지 특징 데이터 생성 장치 및 방법
US8447137B2 (en) * 2011-04-12 2013-05-21 Csi Ricerca & Ambiente Srl Method of image fusion
US8538077B2 (en) 2011-05-03 2013-09-17 Microsoft Corporation Detecting an interest point in an image using edges
US8643522B2 (en) * 2011-06-07 2014-02-04 Microchip Technology Incorporated Multichannel analog to digital converter apparatus and method for using
CA2875891A1 (en) 2011-06-07 2012-12-13 In Situ Media Corporation System and method for identifying and altering images in a digital video
CN102254304B (zh) * 2011-06-17 2012-08-29 电子科技大学 一种目标物体轮廓检测方法
US20120328160A1 (en) * 2011-06-27 2012-12-27 Office of Research Cooperation Foundation of Yeungnam University Method for detecting and recognizing objects of an image using haar-like features
US20130004028A1 (en) * 2011-06-28 2013-01-03 Jones Michael J Method for Filtering Using Block-Gabor Filters for Determining Descriptors for Images
US8675997B2 (en) * 2011-07-29 2014-03-18 Hewlett-Packard Development Company, L.P. Feature based image registration
CN102930493B (zh) * 2011-08-12 2017-08-08 索尼公司 防篡改的图像处理方法和装置
US10607350B2 (en) * 2011-08-31 2020-03-31 Apple Inc. Method of detecting and describing features from an intensity image
EP2761535A1 (en) * 2011-08-31 2014-08-06 metaio GmbH Method of detecting and describing features from an intensity image
US8666169B2 (en) * 2011-10-24 2014-03-04 Hewlett-Packard Development Company, L.P. Feature descriptors
AT511968B1 (de) 2011-10-25 2013-04-15 Ait Austrian Inst Technology Verfahren zur bestimmung der position von kameras
US10006896B2 (en) 2011-11-14 2018-06-26 University of Pittsburgh—of the Commonwealth System of Higher Education Method, apparatus and system for food intake and physical activity assessment
WO2013076365A1 (en) * 2011-11-22 2013-05-30 Nokia Corporation Method for image processing and an apparatus
KR101509003B1 (ko) * 2011-12-16 2015-04-07 도꾸리쯔교세이호징 가가꾸 기쥬쯔 신꼬 기꼬 특징량 추출 방법, 피사체 분류 방법, 피사체 판별 방법, 특징량 추출 장치, 피사체 분류 장치, 피사체 판별 장치, 특징량 추출·피사체 분류 및 피사체 판별 프로그램, 및 그 프로그램을 기록한 기록 매체
KR101307031B1 (ko) * 2011-12-26 2013-09-11 경희대학교 산학협력단 영상 방향을 고려한 국부 콘트라스트 향상 방법
ITVI20120041A1 (it) 2012-02-22 2013-08-23 St Microelectronics Srl Rilevazione di caratteristiche di un'immagine
US10277933B2 (en) 2012-04-27 2019-04-30 Arris Enterprises Llc Method and device for augmenting user-input information related to media content
US10198444B2 (en) 2012-04-27 2019-02-05 Arris Enterprises Llc Display of presentation elements
US9386357B2 (en) 2012-04-27 2016-07-05 Arris Enterprises, Inc. Display of presentation elements
US10389779B2 (en) 2012-04-27 2019-08-20 Arris Enterprises Llc Information processing
KR101303124B1 (ko) 2012-05-31 2013-09-09 삼성에스디에스 주식회사 특징점 기술자에 의한 객체 추적장치 및 방법, 그리고 에러 특징점 제거장치 및 방법
US9064184B2 (en) 2012-06-18 2015-06-23 Ebay Inc. Normalized images for item listings
KR101904203B1 (ko) * 2012-06-20 2018-10-05 삼성전자주식회사 시프트 알고리즘을 이용하여 대용량 소스 이미지의 특징점 정보를 추출하는 장치 및 방법
US8687892B2 (en) * 2012-06-21 2014-04-01 Thomson Licensing Generating a binary descriptor representing an image patch
EP2720171B1 (en) 2012-10-12 2015-04-08 MVTec Software GmbH Recognition and pose determination of 3D objects in multimodal scenes
US9554049B2 (en) 2012-12-04 2017-01-24 Ebay Inc. Guided video capture for item listings
US9728008B2 (en) * 2012-12-10 2017-08-08 Nant Holdings Ip, Llc Interaction analysis systems and methods
US9361538B2 (en) 2012-12-26 2016-06-07 Microsoft Technology Licensing, Llc Real time photometric edge description
US9342930B1 (en) 2013-01-25 2016-05-17 A9.Com, Inc. Information aggregation for recognized locations
US9251419B2 (en) * 2013-02-07 2016-02-02 Digitalglobe, Inc. Automated metric information network
US9367761B2 (en) 2013-02-15 2016-06-14 Samsung Electronics Co., Ltd. Electronic device and object recognition method in electronic device
KR101988384B1 (ko) * 2013-03-08 2019-06-12 삼성전자주식회사 이미지 매칭 장치, 이미지 매칭 시스템 및 이미지 매칭 방법
US9191422B2 (en) 2013-03-15 2015-11-17 Arris Technology, Inc. Processing of social media for selected time-shifted multimedia content
JP5889820B2 (ja) 2013-03-22 2016-03-22 株式会社東芝 特徴量抽出装置、特徴量抽出方法、および画像識別装置
WO2014175480A1 (ko) * 2013-04-24 2014-10-30 전자부품연구원 하드웨어 장치 및 적분 이미지 생성 방법
US9158988B2 (en) 2013-06-12 2015-10-13 Symbol Technclogies, LLC Method for detecting a plurality of instances of an object
KR101491461B1 (ko) 2013-08-02 2015-02-23 포항공과대학교 산학협력단 공분산 기술자를 이용하는 물체 인식 방법 및 장치
FR3009635B1 (fr) 2013-08-08 2016-08-19 St Microelectronics Sa Procede de recherche d'une image similaire dans une banque d'images a partir d'une image de reference
EP4057215A1 (en) * 2013-10-22 2022-09-14 Eyenuk, Inc. Systems and methods for automated analysis of retinal images
US9286695B2 (en) 2014-03-13 2016-03-15 Bendix Commercial Vehicle Systems Llc Systems and methods for tracking points within an encasement
KR20150116260A (ko) 2014-04-07 2015-10-15 삼성전자주식회사 마커 추적 방법 및 그 전자 장치
US9400939B2 (en) 2014-04-13 2016-07-26 International Business Machines Corporation System and method for relating corresponding points in images with different viewing angles
EP2977931A1 (en) 2014-07-24 2016-01-27 Universität Zürich Method for tracking keypoints in a scene
JP5970512B2 (ja) * 2014-09-26 2016-08-17 エヌ・ティ・ティ・コムウェア株式会社 情報処理方法、情報処理装置、及びプログラム
US10013803B2 (en) 2014-09-30 2018-07-03 Fitfully Ltd. System and method of 3D modeling and virtual fitting of 3D objects
KR102286874B1 (ko) * 2014-10-20 2021-08-09 한국전자통신연구원 다중 방향성 적분 이미지를 이용한 객체 검출 장치 및 방법
US9576218B2 (en) * 2014-11-04 2017-02-21 Canon Kabushiki Kaisha Selecting features from image data
FR3030835B1 (fr) * 2014-12-18 2018-02-09 Sagemcom Documents Sas Procede de classification d'un document a partir de son aspect visuel
US10268886B2 (en) 2015-03-11 2019-04-23 Microsoft Technology Licensing, Llc Context-awareness through biased on-device image classifiers
US10055672B2 (en) 2015-03-11 2018-08-21 Microsoft Technology Licensing, Llc Methods and systems for low-energy image classification
US20180253590A1 (en) * 2015-03-20 2018-09-06 Inspirata, Inc. Systems, methods, and apparatuses for digital histopathological imaging for prescreened detection of cancer and other abnormalities
US9842268B1 (en) * 2015-03-27 2017-12-12 Google Llc Determining regions of interest based on user interaction
DE102015004943B4 (de) * 2015-04-17 2017-03-30 Diehl Bgt Defence Gmbh & Co. Kg Verfahren zur Richtungskalibration von Kameras eines Kamerasystems
US9489401B1 (en) 2015-06-16 2016-11-08 My EyeSpy PTY Ltd. Methods and systems for object recognition
RU2614494C2 (ru) * 2015-06-18 2017-03-28 Российская Федерация, от имени которой выступает Министерство обороны Российской Федерации Способ нахождения соответствия особых точек цифровых изображений
US9844881B2 (en) 2015-06-22 2017-12-19 GM Global Technology Operations LLC Robotic device including machine vision
US9875427B2 (en) 2015-07-28 2018-01-23 GM Global Technology Operations LLC Method for object localization and pose estimation for an object of interest
US9811760B2 (en) 2015-07-31 2017-11-07 Ford Global Technologies, Llc Online per-feature descriptor customization
FR3046691B1 (fr) 2016-01-13 2019-03-29 Commissariat A L'energie Atomique Et Aux Energies Alternatives Dispositif de selection et description de points d'interets dans une sequence d'images, par exemple pour l'appariement de points d'interets
US10352689B2 (en) 2016-01-28 2019-07-16 Symbol Technologies, Llc Methods and systems for high precision locationing with depth values
EP3433816A1 (en) 2016-03-22 2019-01-30 URU, Inc. Apparatus, systems, and methods for integrating digital media content into other digital media content
US10512395B2 (en) 2016-04-29 2019-12-24 Carl Zeiss Meditec, Inc. Montaging of wide-field fundus images
US10248876B2 (en) 2016-06-27 2019-04-02 Texas Instruments Incorporated Method and apparatus for avoiding non-aligned loads using multiple copies of input data
US10013765B2 (en) 2016-08-19 2018-07-03 Mitsubishi Electric Research Laboratories, Inc. Method and system for image registrations
US10165180B2 (en) 2016-08-26 2018-12-25 Cisco Technology, Inc. Dynamic deployment of executable recognition resources in distributed camera devices
JP6755764B2 (ja) * 2016-09-27 2020-09-16 株式会社Ｓｃｒｅｅｎホールディングス 位置計測装置および位置計測方法
CN108073857B (zh) 2016-11-14 2024-02-27 北京三星通信技术研究有限公司 动态视觉传感器dvs事件处理的方法及装置
US11042161B2 (en) 2016-11-16 2021-06-22 Symbol Technologies, Llc Navigation control method and apparatus in a mobile automation system
US11049274B2 (en) 2016-11-22 2021-06-29 Lego A/S System for acquiring a 3D digital representation of a physical object
EP3549332B1 (en) 2016-11-30 2020-11-25 Fraunhofer Gesellschaft zur Förderung der Angewand Image processing device and method for producing in real-time a digital composite image from a sequence of digital images
WO2018113911A1 (en) 2016-12-20 2018-06-28 Softkinetic Software Distance-independent keypoint detection
US10198858B2 (en) 2017-03-27 2019-02-05 3Dflow Srl Method for 3D modelling based on structure from motion processing of sparse 2D images
WO2018204342A1 (en) 2017-05-01 2018-11-08 Symbol Technologies, Llc Product status detection system
AU2018261257B2 (en) 2017-05-01 2020-10-08 Symbol Technologies, Llc Method and apparatus for object status detection
US11449059B2 (en) 2017-05-01 2022-09-20 Symbol Technologies, Llc Obstacle detection for a mobile automation apparatus
US10726273B2 (en) 2017-05-01 2020-07-28 Symbol Technologies, Llc Method and apparatus for shelf feature and object placement detection from shelf images
US10663590B2 (en) * 2017-05-01 2020-05-26 Symbol Technologies, Llc Device and method for merging lidar data
US10949798B2 (en) 2017-05-01 2021-03-16 Symbol Technologies, Llc Multimodal localization and mapping for a mobile automation apparatus
US10505057B2 (en) 2017-05-01 2019-12-10 Symbol Technologies, Llc Device and method for operating cameras and light sources wherein parasitic reflections from a paired light source are not reflected into the paired camera
US11367092B2 (en) 2017-05-01 2022-06-21 Symbol Technologies, Llc Method and apparatus for extracting and processing price text from an image set
US10591918B2 (en) 2017-05-01 2020-03-17 Symbol Technologies, Llc Fixed segmented lattice planning for a mobile automation apparatus
WO2018201423A1 (en) 2017-05-05 2018-11-08 Symbol Technologies, Llc Method and apparatus for detecting and interpreting price label text
WO2019023402A1 (en) 2017-07-26 2019-01-31 Canfield Scientific, Incorporated METHOD AND APPARATUS FOR AUTOMATIC GENERATION AND MONITORING OF NORMALIZED ANATOMICAL REGIONS
US10522186B2 (en) 2017-07-28 2019-12-31 Adobe Inc. Apparatus, systems, and methods for integrating digital media content
US10521914B2 (en) 2017-09-07 2019-12-31 Symbol Technologies, Llc Multi-sensor object recognition system and method
US10572763B2 (en) 2017-09-07 2020-02-25 Symbol Technologies, Llc Method and apparatus for support surface edge detection
US10489677B2 (en) 2017-09-07 2019-11-26 Symbol Technologies, Llc Method and apparatus for shelf edge detection
FR3072806B1 (fr) 2017-10-19 2019-09-27 Commissariat A L'energie Atomique Et Aux Energies Alternatives Procede de calcul d'un descripteur global d'une image
US10809078B2 (en) 2018-04-05 2020-10-20 Symbol Technologies, Llc Method, system and apparatus for dynamic path generation
US10832436B2 (en) 2018-04-05 2020-11-10 Symbol Technologies, Llc Method, system and apparatus for recovering label positions
US11327504B2 (en) 2018-04-05 2022-05-10 Symbol Technologies, Llc Method, system and apparatus for mobile automation apparatus localization
US10740911B2 (en) 2018-04-05 2020-08-11 Symbol Technologies, Llc Method, system and apparatus for correcting translucency artifacts in data representing a support structure
US10823572B2 (en) 2018-04-05 2020-11-03 Symbol Technologies, Llc Method, system and apparatus for generating navigational data
US10643329B2 (en) 2018-04-09 2020-05-05 The Boeing Company Automated paint quality control for aircraft
RU2683626C1 (ru) * 2018-04-16 2019-03-29 Российская Федерация, от имени которой выступает Министерство обороны Российской Федерации Способ идентификации опорных точек на космических изображениях местности при их трансформировании
CN108664982B (zh) * 2018-05-15 2022-03-22 中山大学 一种快速生成sift描述子的方法及其系统
US11748983B2 (en) 2018-05-21 2023-09-05 3M Innovative Properties Company Image-based personal protective equipment fit system using worker-specific fit test image data
KR101942219B1 (ko) * 2018-07-05 2019-01-24 고재성 컨볼루션 뉴럴 네트워크를 이용한 폐기물 이미지 식별 장치 및 방법
WO2020068784A1 (en) 2018-09-24 2020-04-02 Schlumberger Technology Corporation Active learning framework for machine-assisted tasks
US11506483B2 (en) 2018-10-05 2022-11-22 Zebra Technologies Corporation Method, system and apparatus for support structure depth determination
US11010920B2 (en) 2018-10-05 2021-05-18 Zebra Technologies Corporation Method, system and apparatus for object detection in point clouds
US11090811B2 (en) 2018-11-13 2021-08-17 Zebra Technologies Corporation Method and apparatus for labeling of support structures
US11003188B2 (en) 2018-11-13 2021-05-11 Zebra Technologies Corporation Method, system and apparatus for obstacle handling in navigational path generation
US11079240B2 (en) 2018-12-07 2021-08-03 Zebra Technologies Corporation Method, system and apparatus for adaptive particle filter localization
US11416000B2 (en) 2018-12-07 2022-08-16 Zebra Technologies Corporation Method and apparatus for navigational ray tracing
US11100303B2 (en) 2018-12-10 2021-08-24 Zebra Technologies Corporation Method, system and apparatus for auxiliary label detection and association
US11015938B2 (en) 2018-12-12 2021-05-25 Zebra Technologies Corporation Method, system and apparatus for navigational assistance
US10731970B2 (en) 2018-12-13 2020-08-04 Zebra Technologies Corporation Method, system and apparatus for support structure detection
CA3028708C (en) 2018-12-28 2025-12-09 Zebra Technologies Corporation Method, system and apparatus for dynamic loop closure in mapping trajectories
CN109754385A (zh) * 2019-01-11 2019-05-14 中南大学 未配准多聚焦图像的快速融合方法
US11189020B2 (en) 2019-02-06 2021-11-30 Thanh Phuoc Hong Systems and methods for keypoint detection
CN110135438B (zh) * 2019-05-09 2022-09-27 哈尔滨工程大学 一种基于梯度幅值预运算的改进surf算法
US10694148B1 (en) 2019-05-13 2020-06-23 The Boeing Company Image-based navigation using quality-assured line-of-sight measurements
US11341663B2 (en) 2019-06-03 2022-05-24 Zebra Technologies Corporation Method, system and apparatus for detecting support structure obstructions
US11960286B2 (en) 2019-06-03 2024-04-16 Zebra Technologies Corporation Method, system and apparatus for dynamic task sequencing
US11402846B2 (en) 2019-06-03 2022-08-02 Zebra Technologies Corporation Method, system and apparatus for mitigating data capture light leakage
US11080566B2 (en) 2019-06-03 2021-08-03 Zebra Technologies Corporation Method, system and apparatus for gap detection in support structures with peg regions
US11200677B2 (en) 2019-06-03 2021-12-14 Zebra Technologies Corporation Method, system and apparatus for shelf edge detection
US11662739B2 (en) 2019-06-03 2023-05-30 Zebra Technologies Corporation Method, system and apparatus for adaptive ceiling-based localization
US11151743B2 (en) 2019-06-03 2021-10-19 Zebra Technologies Corporation Method, system and apparatus for end of aisle detection
GB2599859B (en) 2019-07-10 2023-10-18 Schlumberger Technology Bv Active learning for inspection tool
US11374374B2 (en) 2019-08-09 2022-06-28 The Boeing Company Method and system for alignment and insertion of wire contact with wire contact insertion holes of a connector
US11171459B2 (en) 2019-08-09 2021-11-09 The Boeing Company Method and system for alignment of wire contact with wire contact insertion holes of a connector
DE102019126903B3 (de) * 2019-10-07 2020-09-24 Fachhochschule Bielefeld Verfahren und Robotersystem zur Eingabe eines Arbeitsbereichs
EP3809366A1 (fr) 2019-10-15 2021-04-21 Aisapack Holding SA Procédé de fabrication
CN114586072B (zh) 2019-10-23 2026-04-28 华为技术有限公司 特征检测器和描述符
US11507103B2 (en) 2019-12-04 2022-11-22 Zebra Technologies Corporation Method, system and apparatus for localization-based historical obstacle handling
US11107238B2 (en) 2019-12-13 2021-08-31 Zebra Technologies Corporation Method, system and apparatus for detecting item facings
US11397869B2 (en) * 2020-03-04 2022-07-26 Zerofox, Inc. Methods and systems for detecting impersonating social media profiles
US11822333B2 (en) 2020-03-30 2023-11-21 Zebra Technologies Corporation Method, system and apparatus for data capture illumination control
US11670894B2 (en) 2020-06-19 2023-06-06 The Boeing Company Method and system for error correction in automated wire contact insertion within a connector
US11151405B1 (en) 2020-06-19 2021-10-19 The Boeing Company Method and system for machine vision detection
US11450024B2 (en) 2020-07-17 2022-09-20 Zebra Technologies Corporation Mixed depth object detection
FR3113432B1 (fr) 2020-08-12 2022-08-05 Thibault Autheman Procede de classification automatique d’images
CN111861876B (zh) * 2020-08-17 2024-01-26 浙江港创智能机器人有限公司 一种基于形状特征的金具自动识别方法
US11593915B2 (en) 2020-10-21 2023-02-28 Zebra Technologies Corporation Parallax-tolerant panoramic image generation
US11392891B2 (en) 2020-11-03 2022-07-19 Zebra Technologies Corporation Item placement detection and optimization in material handling systems
US11847832B2 (en) 2020-11-11 2023-12-19 Zebra Technologies Corporation Object classification for autonomous navigation systems
CN112668452A (zh) * 2020-12-24 2021-04-16 杭州电子科技大学 一种基于双目视觉的遮挡目标识别与定位方法
US12198395B2 (en) 2021-01-19 2025-01-14 Objectvideo Labs, Llc Object localization in video
RU2768219C1 (ru) * 2021-03-18 2022-03-23 Федеральное государственное унитарное предприятие "18 Центральный научно-исследовательский институт" Министерства обороны Российской Федерации Способ идентификации опорных точек на космических изображениях местности при отсутствии параметров географической привязки
US11494880B2 (en) * 2021-03-19 2022-11-08 Apple Inc. Image pyramid generation for image keypoint detection and descriptor generation
HUP2100200A1 (hu) 2021-05-20 2022-11-28 Dermus Kft Mélységi-felületi képalkotó berendezés ultrahang képek egymáshoz, illetve felületi képekhez való regisztrálására felületi információ révén
CN113221857B (zh) * 2021-06-16 2024-05-07 深圳大学 一种基于草图交互的模型变形方法及装置
US11954882B2 (en) 2021-06-17 2024-04-09 Zebra Technologies Corporation Feature-based georegistration for mobile computing devices
WO2023126914A2 (en) 2021-12-27 2023-07-06 Yeda Research And Development Co. Ltd. METHOD AND SYSTEM FOR SEMANTIC APPEARANCE TRANSFER USING SPLICING ViT FEATURES
US20230334821A1 (en) * 2022-04-13 2023-10-19 The Curators Of The University Of Missouri Compressed spatial frequency transform for feature tracking, image matching, search, and retrieval
CN114782268A (zh) * 2022-04-19 2022-07-22 南京航空航天大学 一种改进surf算法的低照度图像增强方法
US12191619B2 (en) 2022-04-22 2025-01-07 The Boeing Company Method, system, and computer program product for wire connector assembly
EP4325430A1 (fr) 2022-08-19 2024-02-21 Aisapack Holding SA Procédé d'alimentation de pièces orientées

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3852125B2 (ja) 1996-03-14 2006-11-29 コニカミノルタホールディングス株式会社 ２次元多階調画像におけるパタン検出方法及び装置
US6711293B1 (en) * 1999-03-08 2004-03-23 The University Of British Columbia Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image
JP4086422B2 (ja) * 1999-07-21 2008-05-14 日本放送協会 被写体認識装置
JP4510237B2 (ja) * 2000-06-16 2010-07-21 キヤノン株式会社 パターン検出装置及び方法、画像処理装置及び方法
US7110602B2 (en) * 2002-08-21 2006-09-19 Raytheon Company System and method for detection of image edges using a polar algorithm process
JP2004287783A (ja) 2003-03-20 2004-10-14 Fuji Photo Film Co Ltd 画像の特徴量を抽出する方法および装置
ATE470912T1 (de) * 2006-04-28 2010-06-15 Toyota Motor Europ Nv Robuster detektor und deskriptor für einen interessenspunkt
JP4988408B2 (ja) * 2007-04-09 2012-08-01 株式会社デンソー 画像認識装置
FR2932586B1 (fr) * 2008-06-16 2010-08-13 Inst Nat Rech Inf Automat Dispositif d'aide a la reconnaissance d'images ameliore
US8189945B2 (en) * 2009-05-27 2012-05-29 Zeitera, Llc Digital video content fingerprinting based on scale invariant interest region detection with an array of anisotropic filters
US8953838B2 (en) * 2009-06-24 2015-02-10 Here Global B.V. Detecting ground geographic features in images based on invariant components

Also Published As

Publication number Publication date
AU2007247520A1 (en) 2007-11-15
US20090238460A1 (en) 2009-09-24
KR20140090701A (ko) 2014-07-17
JP2009535680A (ja) 2009-10-01
US20120201466A1 (en) 2012-08-09
KR20090074690A (ko) 2009-07-07
EP2027558A2 (en) 2009-02-25
EP2027558B1 (en) 2013-06-12
AU2007247520B2 (en) 2012-10-04
US8165401B2 (en) 2012-04-24
KR101478840B1 (ko) 2015-01-02
WO2007128452A2 (en) 2007-11-15
EP1850270B1 (en) 2010-06-09
EP1850270A1 (en) 2007-10-31
KR101562756B1 (ko) 2015-10-22
ATE470912T1 (de) 2010-06-15
DE602006014803D1 (de) 2010-07-22
WO2007128452A3 (en) 2008-05-22
US8670619B2 (en) 2014-03-11

Similar Documents

Publication Publication Date Title
JP4982559B2 (ja) 関心点の記述子を導出する方法
Bay et al. Surf: Speeded up robust features
Lowe Distinctive image features from scale-invariant keypoints
AU2011212422B2 (en) Efficient scale-space extraction and description of interest points
Mikolajczyk et al. A performance evaluation of local descriptors
Evans Notes on the opensurf library
Guo et al. 3D object recognition in cluttered scenes with local surface features: A survey
Fauqueur et al. Multiscale keypoint detection using the dual-tree complex wavelet transform
EP1530156A1 (en) Visual object detection
Marimon et al. DARTs: Efficient scale-space extraction of DAISY keypoints
CN105139013A (zh) 一种融合形状特征和兴趣点的物体识别方法
Davarzani et al. Robust image description with weighted and adaptive local binary pattern features
Chelluri et al. SIFT and it’s Variants: An Overview
Huang et al. A new scale invariant feature detector and modified SURF descriptor
Banerjee et al. Development of speed up robust feature algorithm for aerial image feature extraction
Sangeetha et al. Enhanced Approximated SURF Model For Object Recognition
Rozsa et al. Exploring in partial views: Prediction of 3D shapes from partial scans
Kerr et al. Fesid: Finite element scale invariant detector
Benseddik et al. Binary feature descriptor for omnidirectional images processing
Kangas Comparison of local feature detectors and descriptors for visual object categorization
Engel Graphic information processing using intelligent algorithms
Jessore Object Detection by Point Feature Matching using Matlab
Langer et al. New Hierarchical Approaches in Real-Time Robust Image Feature Detection and Matching
Yuk-Man Color Invariant Feature Descriptor for Object Recognition
Babaryka Recognition from collections of local features

Legal Events

Date Code Title Description
A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20100428

A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20100428

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20110707

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20110712

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20111004

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20111012

A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20111114

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20111121

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20111209

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20120327

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20120423

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20150427

Year of fee payment: 3

R150 Certificate of patent or registration of utility model

Ref document number: 4982559

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

Free format text: JAPANESE INTERMEDIATE CODE: R150

S111 Request for change of ownership or part of ownership

Free format text: JAPANESE INTERMEDIATE CODE: R313117

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250