(57)【特許請求の範囲】
【請求項１】
画像に対応する信号を処理することによって該画像の表現を導出する方法であって、
前記画像のスケール空間表現を導出することと、
前記スケール空間表現を処理することによって、振幅の極値を有する複数の特徴点を検出することと、
前記検出された複数の特徴点のうちの１つ又は複数について、対応する特徴点に関連付けられるスケール依存の画像領域を確定することと、
前記確定されたスケール依存の各画像領域についての表現を導出することと
を含み、
前記確定されたスケール依存の各画像領域についての表現を導出することは、トレース変換又は均等物の距離パラメータをサブサンプリングしてサーカス関数を適用することで表現を導出することを含む、画像の表現を導出する方法。
【請求項２】
画像に対応する信号を処理することによって該画像の表現を導出する方法であって、
前記画像のスケール空間表現を導出することと、
前記スケール空間表現を処理することによって、振幅の極値を有する複数の特徴点を検出することと、
前記検出された複数の特徴点のうちの１つ又は複数について、対応する特徴点に関連付けられるスケール依存の画像領域を確定することと、
前記確定されたスケール依存の各画像領域についての表現を導出することと
を含み、
前記確定されたスケール依存の各画像領域についての表現を導出することは、トレース変換又は均等物の複数のバンドにサーカス関数を適用することで表現を導出することを含む、画像の表現を導出する方法。
【請求項３】
前記複数の特徴点は、前記画像のスケール空間表現に対して二次勾配に基づくオペレータを適用し、その結果として前記スケール空間表現内において最も高い値を有する特徴点を識別することによって検出される、請求項１又は２に記載の方法。
【請求項４】
前記画像のスケール空間表現に対して一次勾配に基づくオペレータを適用し、前記検出された複数の特徴点から閾値未満の値の特徴点を取り除くことにより、１つ又は複数の特徴点を選択することを含む、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記検出された複数の特徴点から、前記画像内におけるそれらの空間位置に従って特徴点を取り除くことと、画像内において他の特徴点と所定の距離未満の特徴点を取り除くことにより、１つ又は複数の特徴点を選択することを含む、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記スケール空間表現内の特徴点についてスケール依存の画像領域を確定することは、前記特徴点の空間位置に関連付けられる前記画像の空間領域を確定することを含み、該空間領域のサイズは前記特徴点のスケールに基づく、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記複数の特徴点のうちの１つ又は複数について、該特徴点の一次勾配から、該特徴点の特徴方向を確定することをさらに含む、請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記確定されたスケール依存の各画像領域についての表現を導出することは、該スケール依存の画像領域から得られた信号をフーリエ変換することを含む、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
前記確定されたスケール依存の各画像領域についての表現を導出することは、該スケール依存の画像領域のためのバイナリ画像記述子を導出することを含む、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
請求項１〜９のいずれか一項に記載の方法によって導出された画像の記述子を使用して画像を比較する方法であって、
第１の画像の前記記述子に関連付けられる１つ又は複数のスケール依存の画像領域の表現を、第２の画像の前記記述子に関連付けられる１つ又は複数のスケール依存の画像領域の表現と比較することを含む、画像を比較する方法。
【請求項１１】
請求項１〜１０のいずれか一項に記載の方法を実行するための装置。
【請求項１２】
請求項１〜１０のいずれか一項に記載の方法を実施する命令を備えるコンピュータ記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ロバストな画像識別の問題に関し、以前に出願された同時継続特許出願である、欧州特許出願第０６２５５２３９．３号、英国特許出願第０７００４６８．２号、英国特許出願第０７１２３８８．８号、英国特許出願第０７１９８３３．６号、及び英国特許出願第０８００３６４．２号において開示されている方法のような従来技術の方法に勝る利点を提供する新たな方法を開示する。
【０００２】
［関連技術］
マルチメディアコンテンツのロバストな識別の目的は、そのマルチメディアコンテンツに対して行われる可能性のある典型的な変更の下で保持される情報を抽出することである。この変更は、悪意のない目的或いは悪意のある目的であり得る。画像の場合、ロバストな識別子は、特に、圧縮、グレースケール変換、回転、ノイズ、色変更、クロップ、及び平行移動を受けたときに実質的に保持されなくてはならない。さらに、独立したコンテンツが十分に異なる識別子を有するように、識別子は弁別力（discrimination power）を提供しなくてはならない。
【背景技術】
【０００３】
欧州特許出願第０６２５５２３９．３号、並びに、英国特許出願第０７００４６８．２号、英国特許出願第０７１２３８８．８号、及び英国特許出願第０７１９８３３．６号は、それらが全て大域情報に基づいて識別子を抽出するという点で類似している。大域情報とは、全体画像に関する情報である。これらに係る識別子のファミリーは、非常に低い誤検出率（false alarm rate）で１００％に近いロバスト性を提供し（これは、それらが高い弁別能力を提供することを意味する）、通常の誤検出率は０．１百万分率未満である。
【０００４】
多数の画像が様々な画像データベース内に存在し、ウェブページ、プレゼンテーション、及び文書内に埋め込まれる。主要なウェブサイトの調査によると、Ｆｌｉｃｋｒは２０億を超える画像を有し、Ｐｈｏｔｏｂｕｃｋｅｔは４０億を超える画像を有し、Ｆａｃｅｂｏｏｋは１７億の画像を有することがわかっている。消費者は多くの場合に自身の個人的なコレクション内に数千枚の写真を有し、専門家ははるかに多くを有する。サイズの大きなデータセットを仮定して実用性のあるものとするためには、識別子は非常に高速な探索も可能にしなくてはならない。欧州特許出願第０６２５５２３９．３号、英国特許出願第０７００４６８．２号、英国特許出願第０７１２３８８．８号、及び英国特許出願第０７１９８３３．６号に開示されている技法は、１秒あたり１０００万画像を超える検索速度を可能にすることができる。
【０００５】
欧州特許出願第０６２５５２３９．３号、英国特許出願第０７００４６８．２号、英国特許出願第０７１２３８８．８号、及び英国特許出願第０７１９８３３．６号に開示されている従来技術の識別子は、多くの一般的な画像変更に対する高レベルのロバスト性にもかかわらず、画像コンテンツの大部分が失われるか又は置き換えられる平行移動及びクロップのような或る種の画像変更に対しては、要求されるレベルのロバスト性を提供することができない。英国特許出願第０８００３６４．２号において開示されている技法は、この種の画像変更の下での大幅に改善されたロバスト性を提供する。これは、ｉ）特徴検出及び特徴選択、ｉｉ）特徴領域及び識別子の抽出、ｉｉｉ）照合、を含むプロセスである。本発明は、従来技術の画像識別子のロバスト性に対する改善を提案する。
【０００６】
従来技術における特徴点手法は、コンピュータビジョン及びオブジェクト認識の分野において開発されてきた［文末の参考文献２、３］。これらの手法は、非常に多数の点に依存する：
「この手法の重要な側面は、画像を密に覆う多数の特徴を生成することである．．。サイズ５００×５００ピクセルの典型的な画像によって約２０００個の特徴が生じる。」［文末の参考文献２］
【０００７】
多数の特徴を抽出する結果、探索及び照合の計算が非常に低速になり、単純なケースでは、問い合わせ画像からの全ての特徴がデータベース内の全ての画像からの全ての特徴と比較されなくてはならない。探索時間を低減するために、従来技術の方法は様々な形態のデータベース構造を使用する。しかしながら、これらの構造は、さらなるデータベース初期化時間、さらなるストレージ及びメモリ要件を費やして成り立ち、多くの場合に、改善された探索速度をより低い検出率と引き換えにする何らかの概算（approximation）が行われる。
【０００８】
本発明は、画像及びその画像の変更されたバージョンを検出することに関する。これは、従来技術の多くの適用分野とは異なる。特に、画像重複検出は、たとえばクロップされた画像、圧縮された画像等の画像の変更されたバージョンを見つけることに関する。対照的に、ほとんどの従来技術の方法は、画像内の特定のオブジェクト或いはオブジェクトのクラス、たとえばＦｏｒｄ  Ｆｏｃｕｓ車或いは自動車を検出することに関する。これらの問題を区別することは些細なこと或いは僅かなことに見える場合があるが、これは重要である。たとえば、ロンドンのセント・ポール大聖堂の２つの画像を考えると、これらの画像は２つの異なる視点から撮られている。ここで、オブジェクト認識タスクの下では、これらの画像間の類似性が検出されるはずであるが、画像重複検出の下では類似性は検出されないはずである。これを考慮に入れると、２つの異なる問題を扱うために異なる技法が必要である。
【０００９】
英国特許出願第０８００３６４．２号において開示されている方法は、トレース変換に基づくバイナリ特徴点記述子を開発する。バイナリ記述子を使用する利点は、ハミング距離が特徴照合に使用されることにあり、これによって探索プロセスが非常に高速になる。さらに、選択プロセスは、特徴の数を小さなセットに制限し、これはクロップ及び平行移動のような困難な画像変更に対して非常にロバストであることがわかっている。ロバスト性は良好であるが、さらなる改善を提供することが望ましい。
【発明の概要】
【００１０】
第１の態様によると、本発明は、画像に対応する信号を処理することによって、その画像の表現、すなわち画像記述子を導出する方法を提供する。この方法は、画像のスケール空間表現（scale-space representation）を導出することを含む。スケール空間表現は、振幅の極値（すなわち、極大値又は極小値）を有するスケール空間表現内の複数の特徴点を検出するように処理される。この方法は、検出された複数の特徴点のうちの１つ又は複数について、対応する特徴点に関連付けられるスケール依存の画像領域を確定する。そして、確定されたスケール依存の各画像領域についての表現が導出される。
【００１１】
このため、最も高い特徴強度を有する画像の特徴に基づいて、画像記述子を導出することができる。
【００１２】
一つの実施形態では、複数の特徴点は、画像のスケール空間表現に対して二次画像勾配に基づく第１のオペレータを適用し、その結果としてスケール空間表現内において最も高い値を有する特徴点を識別することによって検出される。次に、第２のオペレータを検出された複数の特徴点に対して適用することができ、第２のオペレータは一次画像勾配に基づき、その結果として閾値未満の値を有する特徴点が取り除かれる。第１のオペレータ及び第２のオペレータを適用することによって検出される複数の特徴点から所定の数の特徴点を選択することができる。
【００１３】
他の実施形態では、複数の特徴点は、所望の用途に従って、異なる順序でオペレータを使用するか又は異なる技法を使用して検出されてもよい。
【００１４】
好ましくは、選択された１つ又は複数の検出された特徴点について、特徴点の空間位置に関連付けられる画像の空間領域を確定することによって、スケール依存の画像領域が確定される。ここで、空間領域のサイズは特徴点のスケールに基づく。
【００１５】
確定されたスケール依存の各画像領域についての表現は、トレース変換又はその均等物を使用すること等によって、画像領域にわたる線投影に基づいて導出することができる。
【００１６】
１つの例では、１つ又は複数の確定されたスケール依存の各画像領域について、画像領域の少なくとも一部分の関数が導出される。ここで、画像領域の平行移動、拡大縮小、又は回転されたバージョンの関数は、画像領域の関数の平行移動又は拡大縮小されたバージョンである。画像領域の少なくとも一部分の関数を導出することは、画像領域にわたる線に沿って第１の汎関数を適用することを含んでもよい。この方法は、第２の汎関数を導出された関数に適用して画像領域の少なくとも一部分の中間表現を得ることをさらに含んでもよい。
【００１７】
確定されたスケール依存の各画像領域についての表現は、バイナリ画像記述子を含んでもよい。
【００１８】
画像の表現は、スケール依存の画像領域の導出された表現のうちの２つ以上から導出されてもよい。
【００１９】
第２の態様によれば、本発明は、本発明の第１の態様による方法によって導出される画像の記述子を使用して画像を比較する方法を提供する。この方法は、第１の画像の記述子に関連付けられる１つ又は複数のスケール依存の画像領域の表現を、第２の画像の記述子に関連付けられる１つ又は複数のスケール依存の画像領域の表現と比較することを含む。
【００２０】
本発明のさらなる態様は、本発明の第１の態様による方法によって導出される画像の表現の送信又は受信を含む使用と、本発明の第１の態様若しくは第２の態様又は双方による方法を実行するための装置と、コンピュータによって実行されると本発明の第１の態様若しくは第２の態様又は双方による方法を実行する命令を備えるコンピュータ可読ストレージ媒体とを含む。
【００２１】
本発明の他の特徴及び利点は、以下の説明及び添付の特許請求の範囲から明らかとなろう。
【００２２】
本発明は、要求通りにロバスト性を改善する２つの主な態様、すなわち、ｉ）領域スケールが特徴の選択及び抽出のプロセスに組み込まれること、及び、ｉｉ）計算コストを最小にしながらロバスト性を維持する最大４つの段階の照合プロセスが展開されること、を含む。
【００２３】
特徴検出プロセスを使用して、空間及びスケールにおける位置を有する複数の特徴を選択する。特徴選択は、タスクに適しており且つトレース変換に基づく特徴記述子と共に良好に機能することが実験的に示された特徴を選択するための新規のプロセスを使用する。
【００２４】
画像照合の場合、検出性能と、独立性と、計算時間と、メモリ要件との間でのトレードオフが必要とされる。開示される実施の形態では、４ステップの照合プロセスが導入される。このプロセスは、計算時間及びメモリ要件の双方を最小にしながら、検出率及び独立性を最大にすることを目的とする。第１のステージでは、高い確率を有する仮説（すなわち候補）を迅速に確定し、確率の低い一致を除去する。第２のステージでは、これらの仮説を検定し、多数の誤った仮説を取り除く。第３のステージは、さらなる誤った仮説を除去する。各ステージは、前のステージに勝る増大されたレベルの複雑度を伴うため、プロセスの可能な限り早いうちに誤った仮説を除去することによって複雑度が管理され、最小にされる。
【００２５】
上述した態様と同様に、本発明の他の態様は、画像の選択及び抽出された特徴に基づいて画像の表現を導出すること、並びに、本発明の１つ又は複数の態様に従ってプロセスを実行するための装置及びコンピュータプログラムを含む。
【００２６】
ここで、添付の図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【００２７】
【図１】図１ａは、画像を示す図である。図１ｂは、図１ａの画像を縮小したバージョンを示す図である。図１ｃは、図１ａの画像を回転させたバージョンを示す図である。図１ｄは、図１ａの画像をぼかしたバージョンを示す図である。図１ｅは、図１ａの画像を（左右に）反転させたバージョンを示す図である。図１ｆは、図１ａの画像を高圧縮したバージョンを示す図である。図１ｇは、図１ａの画像をクロップしたバージョンを示す図である。
【図２】従来技術による画像とそのビット列表現を示す図である。
【図３】特徴検出器によって検出された画像の特徴点のセットの例を示す図である。
【図４】特徴の最終セットが選択された画像を示す図であり、特徴のスケールは円のサイズによって示され、特徴の方向は線によって示される。
【図５】原画像（ａ）と、（ａ）の回転させたバージョンである（ｂ）とに基づくハミング距離を使用して一致することがわかった関心点を示す図であり、関心点の間の線の長さを使用して幾何学的制約を適用する。
【図６】本発明の一つの実施形態による装置のブロック図である。
【図７】本発明の一つの実施形態による特徴識別子（ａ）及び画像識別子（ｂ）の構造を示す図である。
【発明を実施するための形態】
【００２８】
画像の表現（representation of an image）、具体的には画像識別子（image identifier）を導出し、そのような表現／識別子を、例えば１つ又は複数の画像の識別、照合、或いは検証のために使用する様々な実施形態を以下に説明する。本発明は、画像を識別するために特に有用であるが、画像の識別に限定されるものではない。説明する実施形態において、「画像識別子」（「識別子」、「記述子」、「画像記述子」、「シグネチャ」、又は「画像シグネチャ」とも称される）は画像の表現の一例であり、この用語は単に画像の表現又は記述子を表すのに使用される。
【００２９】
当業者であれば、本発明の一実施形態による画像識別装置及び画像識別方法の具体的設計の詳細、並びに、画像識別において使用するための画像識別子の導出は、ロバストであるべき画像変更の種類、識別子のサイズ、抽出及び照合の複雑度、目標誤検出率等に関連する要件によって確定されることを理解するであろう。
【００３０】
以下の例では、画像に対する以下の変更に対してロバストな識別子をもたらす一般的設計を示す（これは網羅的なリストではない）：
・減色
・ぼかし
・輝度値変更
・反転（左右及び上下）
・グレースケール変換
・ヒストグラム等化
・ＪＰＥＧ圧縮
・ノイズ
・回転
・クロップ
・スケーリング
・平行移動
・スキュー
・視点変更
【００３１】
提案される設計は通常、広範な画像に対して１ｐｐｍ（百万分率）未満の低い誤検出率を達成することができ、検出率は通常、９８．０％を超えることができることがわかっている。
【００３２】
図１は、画像の一例とその画像の変更バージョンを示す。より具体的には、図１ａは原画像であり、図１ｂは図１ａの画像を縮小した（スケーリングした）バージョンであり、図１ｃは図１ａの画像を回転させたバージョンであり、図１ｄは図１ａの画像をぼかしたバージョンであり、図１ｅは図１ａの画像を反転させたバージョンであり、図１ｆは図１ａの画像を圧縮したバージョンであり、図１ｇは図１ａの画像をクロップしたバージョンである。
【００３３】
本発明の実施形態は、画像の表現を導出する。より具体的には、画像に対応する信号及び／又は画像データを処理することによって画像識別子を導出する。
【００３４】
特徴点の検出及び選択
欧州特許出願第０６２５５２３９．３号、英国特許出願第０７００４６８．２号、英国特許出願第０７１２３８８．８号、英国特許出願第０７１９８３３．６号、及び英国特許出願第０８００３６４．２号と同じく、画像識別子の抽出の初期段階において、画像はサイズ変更及びフィルタリングによって任意選択で前処理される。サイズ変更ステップは、画像を処理前に正規化するために使用される。フィルタリングステップは、エイリアシング等の効果を除去するためのフィルタリングを含むことができ、また領域選択及びテーパリングも含むことができる。一つの実施形態では、画像は２５６×Ｎ又はＮ×２５６の解像度にサイズ変更される。ここでＮ≧２５６であり、画像の縦横比を維持する。別の実施形態では、画像は２５６×２５６の正方形にサイズ変更される。次に、画像は３×３のガウスカーネルを使用してローパスフィルタリングされる。前処理ステップは任意選択であり、上記のものの任意の組み合わせを含むことができる。
【００３５】
次の段階において、画像において特徴点が検出される。一つの実施形態では、特徴検出器を使用して、画像勾配の測定に基づいて画像内の潜在的な特徴とそれらの強度を検出する。一次の画像勾配に基づく１つの適切な画像特徴検出器は、英国特許出願第０８００３６４．２号において使用されるようなハリスである。
【００３６】
【数１】
0005427883.tif 000002
【００３７】
ここで、Ｉx（ｘ，ｙ）は位置（ｘ，ｙ）における画像強度Ｉ（ｘ，ｙ）の一次導関数であり、αは特徴検出を制御するパラメータである。
【００３８】
代替的な二次検出器は、ラプラシアン（二次の偏導関数ヘッセ行列のトレースに対応する）である。
【００３９】
【数２】
0005427883.tif 000003
【００４０】
ここで、Ｉxx（ｘ，ｙ）は位置（ｘｙ）における画像の二次導関数である。
【００４１】
英国特許出願第０８００３６４．２号では、特徴は単一のスケールおいてのみ選択され、これは原画像の正規化されたバージョンである。さらに、特徴の周囲のエリア（特徴シグネチャが抽出される画像領域を形成する）が固定されている。しかしながら、クロップによる変更の下では、画像の一部分が失われる。画像が（上述した前処理のように又はユーザによって）幾何学的に正規化されるとき、或る領域は原画像内の同じ領域よりも大きくなる。大量のクロップの下では、これら２つの領域のトレース変換に基づく記述子が受容不可能なほどに異なることになる。すなわち、距離が類似性を示す閾値を超える場合がある。
【００４２】
この問題に対処するために、本発明の第１の態様に従って、「スケール推定」を使用することができる。スケール推定は、各特徴の分析のための適切なスケールを選択しようと試みる。各特徴は、その特徴固有のスケールに関連付けられることに留意されたい。
【００４３】
まず、画像のスケール空間表現（scale-space representation）が導出される。実施形態では、画像のスケール空間表現は２つの方法のうちの１つで構築することができる（ただし、他の技法も可能であり検討される）。第１の方法では、原画像を連続して平滑化及びサンプリングする。第２の方法では、フィルタサイズを増加させながら反復的に画像を平滑化する。次に、位置スケール空間（location-scale space）における極大値を見つけることによって特徴が検出される。平滑化フィルタのための最適な選択は、ガウシアン（フィルタ）であることがわかっており、ガウシアン（フィルタ）によって平滑化された画像は以下によって表される。
【００４４】
【数３】
0005427883.tif 000004
【００４５】
ここで、＊は畳み込み演算子であり、Ｇ（σD）はガウシアンフィルタであり、σDはスケールを確定する平滑化フィルタの標準偏差である。
【００４６】
一つの実施形態では、２つの検出器を使用してスケール空間表現における特徴の位置及びスケールの良好な検出を提供する。一方の検出器は一次の勾配を使用し、他方は二次の勾配を使用する。
【００４７】
第１番目では、ガウシアンオペレータの修正型スケール補正ラプラシアン（modified scale corrected Laplacian）
【００４８】
【数４】
0005427883.tif 000005
【００４９】
を使用して、複数の特徴の位置及びスケール（すなわちスケール空間表現における特徴点）を検出する。ここで、Ｇ（σI）は導関数を平均化する積分に使用されるガウシアンフィルタであり、σIは積分スケールであり、γはスケール正規化パラメータである。スケールに適合したラプラシアンに積分平滑化を導入することは、特徴検出器の性能を改善するのに役立つ。
【００５０】
第２の検出器は、スケールに適合したハリスオペレータ（scale-adapted Harris operator）である。
【００５１】
【数５】
0005427883.tif 000006
【００５２】
ここで、
【００５３】
【数６】
0005427883.tif 000007
【００５４】
である。
【００５５】
したがって、ラプラシアンの式（４）がスケール空間において適用され、最も高い値を有する位置及びスケールが潜在的な特徴として選択される。そして、重要でない（すなわち閾値未満の）ハリス検出器応答を有する特徴は潜在的な特徴のセットから取り除かれる。下記で説明されるような選択手順が適用され、２つの検出器を使用した結果として生じる潜在的な特徴のセットから、特徴の代表的なセットが選択される。一つの実施形態では、所定の数に達するまで特徴が選択される。
【００５６】
検出された複数の特徴の中の許容可能な特徴から、ラプラシアン検出器の式（４）に従って最も強い特徴が最初に選択される。特徴は、その特徴が、特徴スケールから計算される半径ｒよりも画像のエッジに近い場合には拒否される。式（７）を参照されたい。後続の特徴は、その特徴が以前に選択された任意の特徴の周囲の除外ゾーン内にある場合には選択されないという制約を用いて、強度順に選択される。一つの実施形態では、半径１０ピクセルの円形領域が除外ゾーンとして使用される。選択プロセスは、所定の数の代表的な特徴（たとえば３２個の特徴）が選択されるか、これ以上特徴が残っていない場合に終了する。
【００５７】
図２の画像における図３に示すように検出された特徴から選択された特徴のセットが図４に示されている。スケールは円のサイズによって表され、特徴の方向は線によって表されている。検出される特徴とそれらを取り囲む画像領域は、全体としての画像を代表するもの、すなわち全体としての画像にとって重要なものであることが理解されるであろう。
【００５８】
特徴点（又は関心点）の位置が選択されると、それらの位置は、好ましくは、例えばhttp://opencvlibrary.sourceforge.net/CvReference、文末の参考文献［１］）においてインターネット上で入手することができるOpenCV(FindCornerSubPix)03/01/2008.に記載されているような方法を使用して、選択されたスケールでサブピクセル解像度に精緻化される。
【００５９】
特徴領域及び識別子の抽出
参照により本明細書に援用される英国特許出願第０７１９８３３．６号では、バイナリ画像識別子又は画像表現を抽出するための方法が開示されている。本発明の一つの実施形態では、英国特許出願第０７１９８３３．６号の方法を適用して、特徴点の周囲の領域からバイナリ「特徴識別子」を抽出する。それゆえ、各特徴識別子は、検出された特徴に関連付けられる画像領域のバイナリ表現である。画像領域は所定のサイズを有することができる。たとえば、一つの実施形態では、或る特徴点を中心とする半径３２ピクセル円形画像領域が選択され、その画像領域に関してバイナリシグネチャが計算される。円形領域は、例えばキュービック補間法を使用して、好ましくはサブピクセルレベルの精度まで抽出される。
【００６０】
好ましくは、固定された特徴領域半径を使用する代わりに、特徴が検出されるスケールを用いて領域サイズを適宜適合させる。スケールｓにおいて選択される領域の半径は以下によって与えられる。
【００６１】
【数７】
0005427883.tif 000008
【００６２】
ここで、ｒ0は基礎半径であり、σ0は初期スケールであり、κは設計パラメータであり定数である。積分スケールの良好な選択が以下であることも注目に値する。
【００６３】
【数８】
0005427883.tif 000009
【００６４】
好ましい実施形態では、κ＝０．６、σ0＝１．１４、ｒ0＝２０、ｓ∈（０，１，．．．，Ｓ）であり、Ｓ＝１４である。特徴位置（ｘ，ｙ）と半径ｒによって確定される領域は、キュービック補間法を使用して、サブピクセルの精度まで抽出される。次に、領域は、好ましい実施形態では３２である正規化された半径
【００６５】
【数９】
0005427883.tif 000010
【００６６】
によって与えられる所定のサイズに正規化される。次に、抽出された領域を処理して、英国特許出願第０７１９８３３．６号による方法を使用することによって対応する画像識別子を導出する。この方法の概要が下記に提供される。
【００６７】
ｄ、θによってパラメータ化された全ての可能な線を画像に射影し、これらの線にわたって第１の汎関数Ｔを適用することによって、画像領域のトレース変換Ｔ（ｄ，θ）を行う。英国特許出願第０７００４６８．２号において開示されている方法に従って、トレース変換の結果を分解して、その次元ｄ、θのうちのいずれか又は双方における解像度を低減することができる。欧州特許出願第０６２５５２３９．３号及び英国特許出願第０７００４６８．２号の方法におけるように、トレース変換の列に第２の汎関数Ｐを適用して、実数値ベクトル（すなわち一次元関数）を得ることができる。この第２の汎関数Ｐは、ダイアメトリック汎関数（diametrical functional）として知られ、結果として得られるベクトルはサーカス関数（circus function）として知られている。
【００６８】
第３の汎関数であるサーカス汎関数（circus functional）をサーカス関数に適用して、単一の数を得ることもができるが、このステップは好ましい実施形態では使用されない。
【００６９】
代替的に、英国特許出願第０７１９８３３．６号の方法によれば、上記で論考したサーカス関数の代替として、いわゆる「帯状サーカス（band-circus）」関数を得ることができる。「帯状サーカス」関数は、トレース変換の一部分の値のみを選択して処理することによって、トレース変換を画像の線のサブセットに制限する。
【００７０】
第１の汎関数、第２の汎関数、及び／又は第３の汎関数（トレース汎関数、ダイアメトリック汎関数、及びサーカス汎関数）の適切な選択によって、結果の特性を制御することができる。
【００７１】
画像領域のためバイナリ識別子が、周波数表現を介してサーカス関数（又は帯域サーカス関数）から抽出される。例えば、フーリエ変換の係数の大きさに対して、関数ｃ（ω）を定義することができる。この関数の１つの例示は、近傍の係数の差分をとることである。
【００７２】
【数１０】
0005427883.tif 000011
【００７３】
結果として得られるベクトルに以下のような閾値を適用することによって、バイナリ列を抽出することができる。
【００７４】
【数１１】
0005427883.tif 000012
【００７５】
Ｓの適切な選択には、Ｓ＝０及びＳ＝ｍｅａｎ（ｃ）が含まれる。次に、これらのバイナリ列の値Ｂ＝｛ｂ0．．．．．ｂn｝から画像領域のバイナリ表現が構成される。
【００７６】
本発明の一つの実施形態では、（英国特許出願第０７１９８３３．６号においては画像全体であるのに対して）局所画像領域が使用されるため、そこに記載されているシグネチャ抽出技法に対して変更を行う必要がある。特に、欧州特許出願第０６２５５２３９．３号において開示されている方法に従って、汎関数
【００７７】
【数１２】
0005427883.tif 000013
【００７８】
及び
【００７９】
【数１３】
0005427883.tif 000014
【００８０】
を使用した、フルトレース変換の（２つの）サーカス関数から２つの識別子が抽出される。
【００８１】
英国特許出願第０７００４６８．２号に開示されている方法に従って、トレース変換の距離（ｄ）パラメータを、８分の１、１６分の１、及び３２分の１に分解（又はサブサンプリング）して式（１０）及び（１１）の双方を適用することによって得られる（６つの）サーカス関数から、さらなる６つの「多重解像度」識別子を抽出することができる。
【００８２】
英国特許出願第０７１２３８８．８号に開示されている方法に従って、トレース変換における（３つの）帯からさらなる３つの関数が選択され、英国特許出願第０７１９８３３．６号に開示されている方法に従って、（２つの）トレース環形関数（trace-annulus function）から２つの関数が抽出され、トレース円形関数（trace-circular function）から１つの関数が抽出される。
【００８３】
これらの１４個の成分識別子のそれぞれは８ビットであり、各特徴識別子について計１１２ビットとなる。
【００８４】
さらに、各特徴の近傍にわたって積分することによって、スケールに適合した特徴方向が計算される。
【００８５】
【数１４】
0005427883.tif 000015
【００８６】
方向θは、好ましくは１６個のレベルに量子化される。これは４ビットのデータによって表すことができる。
【００８７】
画像識別子又は画像記述子は、特徴シグネチャの全て又は幾つかから形成される。特徴点の完全なセットのための画像識別子は、多数の形で表すことができる。好ましい実施形態では、画像記述子は多数の情報フィールドを含むビットストリームであり、その第１のフィールドは特徴の数である。そして、ビットストリームにおいて各特徴は、正規化された特徴点座標（ｘ及びｙ）、量子化された特徴方向、それに続くバイナリ特徴シグネチャとして表される。任意選択で、特徴数を格納するのではなく、使用されていないフィールドを表すためのフラグをセットしてパディングを使用することもできる。バイナリ特徴シグネチャは、１１２ビット全てを含むか、又は任意選択で１１２ビットのサブセットを選択、導出、若しくは格納することもできる。特徴識別子の構造が図７（ａ）に示され、画像シグネチャの構造が図７（ｂ）に示される。
【００８８】
特徴識別子を使用する画像照合
画像照合は、画像識別子の一部分を形成する特徴シグネチャを比較又は照合することによって行うことができる。上述したように、効率性のために、特徴シグネチャを比較することによる画像ペア間の全照合手順は、４つのステージから構成される。ステージ１及び３において仮説（hypothesis）が形成される。ステージ２及び４において一連の幾何学的検定（geometric test）が実施される。仮説が次のステージへと進むためには、これらの検定に通らなくてはならない。ステージごとに計算の複雑度を増していくため、各ステージは後続の処理に受容される仮説の数を最小にすることを目的とする。
【００８９】
第１のステップは、１つの画像からのＮ個の特徴シグネチャのうちの最初のＭ個を、第２の画像からのＮ個の特徴シグネチャのうちの最初のＭ個と比較することによって、潜在的に一致する特徴のための仮説を形成することを含む。Ｍ個から成るサブセットを使用することの利点は、ロバスト性を維持しながら高速化することである。好ましい実施形態では、Ｎは３２でありＭは２４である。
【００９０】
２つのシグネチャＢ1とＢ2の間で照合を行うために、ハミング距離がとられる。
【００９１】
【数１５】
0005427883.tif 000016
【００９２】
ここで、
【００９３】
【数１６】
0005427883.tif 000017
【００９４】
は排他的ＯＲ（ＸＯＲ）演算子である。
【００９５】
好ましい実施形態では、一致する特徴の３つのペアの全ての組み合わせについて仮説のセット（潜在的に一致する特徴の候補ペア）が生成される。特徴点の３つのペアから成るセット（ａ1，ａ2，ａ3，ｂ1，ｂ2，ｂ3）から仮説が構成される。特徴の３つのペアから成るセットは、各特徴ペアの距離が一定の閾値ＴA未満であり、且つ、累積距離が何らかの第２の一定の閾値ＴB未満である場合に、一致であると宣言される。好ましい仮説では、ＴA＝０．０６、ＴB＝０．２である。仮説のセットは、それらの累積距離の順に、最も小さい距離（すなわち一致である確率が最も高い）を先頭にして並べられる。複雑度を最小にするために、仮説の数を最も小さい距離に対応するＫ個の仮説に限定することもできる。好ましい実施形態では、Ｋは１８である。
【００９６】
第２のステップは、ステージ１で生成されたそれぞれに幾何学的制約を適用する。誤った一致を低減するために、２つの幾何学的制約、すなわち、ｉ）特徴方向、ｉｉ）線長比が適用される。
【００９７】
上述したように、各特徴には方向が関連付けられ、特徴ａnにおける方向はθanと表される。同一の画像からの特徴に対応する角の間の差分が取られ、角度距離計量値（angle distance measure）が回転の影響を受けないようにする。距離計量値は左右及び上下の反転変更の問題に対処しなくてはならず、ここでは角度距離のこれら２つの計量値を使用して行われる。
【００９８】
【数１７】
0005427883.tif 000018
【００９９】
２つの角度距離計量値Ω1、Λ1に閾値を適用して、それらが許容可能な間隔にあるか否かを検定する。角度距離における許容可能な値は、角度量子化Ｑのレベル数に依存し、以下によって与えられる。
【０１００】
【数１８】
0005427883.tif 000019
【０１０１】
ここで、ｑは角度の変化に対する感度を変動させるのに使用することができる定数である。好ましい実施形態では、ｑは１にセットされ、Ｑは１６である。
【０１０２】
図５に示すように、各仮説において選択された特徴の位置を用いることによって、特徴間の線の長さの比が制約として使用される。｜ａ1ａ2｜によって、特徴ａ1の位置と特徴ａ2の位置とをつなぐ線の長さを表す。３つの特徴点｜ａ1ａ2｜、｜ａ2ａ3｜、及び｜ａ3ａ1｜が線長比を求めるのに使用される。３つの線長比が以下のように計算される。
【０１０３】
【数１９】
0005427883.tif 000020
【０１０４】
２つの画像ＡとＢの線長比の間の類似度の計量値（Ｇ1，Ｇ2，Ｇ3）は、以下のように定義される。
【０１０５】
【数２０】
0005427883.tif 000021
【０１０６】
有利には、上記の幾何学的制約が、回転、平行移動、及び拡大縮小のような幾何学的変換を受けた画像を照合するのに適するように、画像内に定義された点の間の線長比は、そのような幾何学的変換に対して不変である。しかしながら、設計要件に合う他の適切な幾何学的制約を使用してもよい。
【０１０７】
一つの実施形態では、２つの閾値が距離計量値に適用される。一方は個々の計量値の大きさを制約するためのものであり、他方は距離の合計を制約するためのものである。
【０１０８】
上述した検定のうちの１つ又は複数に通らない仮説は、有効な仮説のセットから取り除かれる。全ての仮説を試験した後にセットが空になった場合、画像は非一致であると宣言される。仮説が全ての検定に通った場合、その仮説は次のステージに進み、４つの特徴仮説が生成される。
【０１０９】
照合の第３のステージでは、第１の画像からのＮ個の全ての特徴を、第２の画像からのＮ個の全ての特徴と比較する。ここでは、３つの特徴ペアに関する仮説が既に存在するため、４つのペアについての仮説のセットを見つけることが目的であり、その仮説は現在の３つの特徴ペアの仮説に対してさらに１つの特徴を付け加える。ステージ１と同様に、シグネチャ距離に基づいて潜在的な特徴が見つけられる。仮説のセットは４番目の特徴の距離の順に並べられる。
【０１１０】
ステージ４において、誤受入率をさらに低減するために、４つの特徴仮説から成るセットに対して幾何学的分析が実行される。第１の幾何学的制約は、３つの特徴についての特徴方向の式（１４）及び（１５）に基づく。先ほど使用された線の比は相似変換に対して不変である。下記で説明するように面積の比を使用することによって、特徴が４つの際の不変性をより一般的なアフィン変換に緩和することができる。これは、誤った一致を拒否しながら真の一致を受容するより厳密な閾値を設定することを可能にする。
【０１１１】
４つの特徴のセット（ａ1，ａ2，ａ3，ａ4）から、４つの三角形を構築することができる（ａ1ａ2ａ3，ａ2ａ3ａ4，ａ3ａ4ａ1，ａ4ａ1ａ2）。これらの三角形の面積は以下から求めることができる。
【０１１２】
【数２１】
0005427883.tif 000022
【０１１３】
ここで、ｓ＝（｜ａ1ａ2｜＋｜ａ2ａ3｜＋｜ａ3ａ1｜）／２である。面積比は以下のように計算することができる。
【０１１４】
【数２２】
0005427883.tif 000023
【０１１５】
続いて、画像Ａの面積比と画像Ｂの面積比との間の距離を、以下によって求めることができる。
【０１１６】
【数２３】
0005427883.tif 000024
【０１１７】
２つの閾値Ｔc及びＴDが特徴セット間の４つの面積比距離のセットに適用される。第１の閾値は、第１の閾値Ｔcを超える任意の面積比距離を有する仮説を拒絶する。第２の閾値は、距離の合計が閾値ＴDよりも大きい仮説を拒絶する。好ましい実施形態では、Ｔc＝０．１５、ＴD＝０．４である。
【０１１８】
本発明の上述した実施形態の画像照合技法は、英国特許出願第０７１９８３３．６号において開示されている方法のような他の画像照合技法と組み合わせることができる。記述子は、個々の識別子の全てを含む各画像について生成される。好ましい実施形態では、識別子ビットストリームは、英国特許出願第０７１９８３３．６号に基づく２つの識別子、及び本発明による１つの記述子を含む。英国特許出願第０７１９８３３．６号に基づく２つの識別子のうち、第１の識別子は画像の縦横比を維持するために画像を前処理することによって生成され、他方はその画像を正方形に処理するときに生成される。
【０１１９】
好ましくは、照合は、最初に英国特許出願第０７１９８３３．６号のより高速なアルゴリズムを用いて、非常に低い誤検出閾値で実行される。閾値未満の任意の画像ペアは一致であると見なされ、次に、閾値を超えるペア（英国特許出願第０７１９８３３．６号では一致であるとみなされない）が本発明に従って処理される。
【０１２０】
上記の方法を実行するための、一実施形態による、本発明を実施するための装置が図６に示されている。この実施態様は、画像データベース２３０内に格納される画像のための識別子のデータベース２４０を構築することを伴う。２つのデータベース２３０及び２４０は、同じデータベースであってもよいし、別個のデータベースであってもよい。本装置は、問い合わせ画像２５０から抽出される識別子２６０を探索することよって、識別子データベース１４０内において一致するものを見つけることを可能にする。場合によっては順序付けされた画像のリストが、ユーザ２９０又は問い合わせアプリケーションに返される。
【０１２１】
当業者であれば、説明した実施形態に対して多くの変形及び変更を行うことができることを理解するであろう。たとえば、説明した実施形態では、画像シグネチャが導出される画像領域を特徴検出に基づいて識別するが、他の技法を使用して画像を代表する或いは画像内で重要な画像領域を識別してもよい。さらに、説明した実施形態では、画像勾配法に基づく特徴検出器を使用するが、多くの他の適切な方法を画像内の関心点又は領域の検出に使用することができる。同様に、最も良好な又は最も強力な検出された特徴点又は関心点を選択するために他の技法も使用可能である。
【０１２２】
加えて、説明された実施形態において使用された３つの特徴点のセットに関連付けられる線長比に関連する距離計量値とは異なる、様々な幾何学的制約のうちの１つ又は複数を使用することが可能である。たとえば、任意の数の特徴点を距離計量値とあわせて使用することができる。代替的に、他の幾何学的制約は、特徴点間の角度に基づいてもよい。さらに、幾何学的制約を定義するためにアフィンモデルを使用してもよい。
【０１２３】
本発明の精神及び範囲内に入る全ての変形、変更、及び均等物を含むことが意図されている。
【０１２４】
代替的な実施態様
上記の説明は仮説を生成するのに総当り探索を使用したが、幾つかの状況では、ハミング距離の近似計算を可能にする構造を使用することが有益である場合がある。これは、或るレベルの検出と引き替えに検索速度の増大を提供するであろう。
【０１２５】
提示された特徴照合手法は、［下記の参考文献４］に示されているようなやり方で確率モデルに当てはめるのが容易である。
【０１２６】
参考文献
１．Open CV Reference Manual, Chapter 1: Image Processing Gradients, Edge and Corners - "FindCornerSubPix": http://opencvlibrary.sourceforge.net/CvReference２．D.G. Lowe「Distinctive Image Features from Scale Invariant Keypoints」（International Journal of Computer Vision, 60, 2, 2004. pp. 91-110）
３．D.G. Lowe「Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image」（２０００年３月、米国特許第６，７１１，２９３号）
４．C. Schmid「A Structured Probabilistic Model for Recognition」（Proc. Computer Vision and Pattern Recognition, 2, 485-490, Jun. 1999）
【図５】
0005427883.tif 000025
【図６】
0005427883.tif 000026
【図７】
0005427883.tif 000027
【図１】
0005427883.tif 000028
【図２】
0005427883.tif 000029
【図３】
0005427883.tif 000030
【図４】
0005427883.tif 000031