局所化されたスケール空間特性を使用してピクチャイメージ内で安定したキーポイントを検出するシステムおよび方法
【課題】ピクチャイメージ内で安定したキーポイントを検出する。
【解決手段】キーポイントを検出する方法は、入力イメージのインテグラルイメージを計算するステップと、複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成するステップであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、ステップと、スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせるステップと、前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別するステップと、前記安定したキーポイント位置をメモリストレージに格納するステップと、を含む。
【解決手段】キーポイントを検出する方法は、入力イメージのインテグラルイメージを計算するステップと、複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成するステップであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、ステップと、スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせるステップと、前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別するステップと、前記安定したキーポイント位置をメモリストレージに格納するステップと、を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、局所化されたスケール空間特性を使用してピクチャイメージ内で安定したキーポイントを検出するシステムおよび方法に関する。
【背景技術】
【０００２】
イメージ（画像）内のキーポイントの検出の技術の一例として、非特許文献１及び非特許文献２に記載されたＳＩＦＴ（Ｓｃａｌａｂｌｅ Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅ Ｔｒａｎｓｆｏｒｍ）がある。処理速度を改善するために、ＳＩＦＴでは、ディファレンス・オブ・ガウシアン（Ｄｉｆｆｅｒｅｎｃｅ ｏｆ Ｇａｕｓｓｉａｎ，ＤｏＧ，ガウス関数の差分）のイメージピラミッドにより、ラプラシアン・オブ・ガウシアン（Ｌａｐｌａｃｉａｎ ｏｆ Ｇａｕｓｓｉａｎ，ＬｏＧ）をさらに近似する。入力イメージは、連続的にガウシアンカーネルによって平滑化され、ダウンサンプリングされる。ディファレンス・オブ・ガウシアンは、２つの連続する平滑化されたイメージの差をとることで取得される。したがって、すべてのＤｏＧレベルは、平滑化およびサブサンプリングの組み合わせにより構成される。空間次元およびスケールのイメージピラミッド表現における局所的な３Ｄ（３次元）の最大値は、キーポイントの位置およびスケールを決定する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】ロウエ（D. G. Lowe），「Distinctive Image Features from Scale-Invariant Keypoints」，International Journal of Computer Vision，２００４年，第６０巻（Vol. 60），第２号（No. 2），ｐ．９１−１１０
【非特許文献２】ブラウン（Matthew Brown）およびロウエ（D.G. Lowe），「Invariant Features from Interest Point Groups」，British Machine Vision Conference，BMVC 2002，カーディフ（Cardiff），ウェールズ（Wales），２００２年９月， ｐ．６５６−６６５
【発明の概要】
【発明が解決しようとする課題】
【０００４】
キーポイントを検出する技術において特別な問題は、ノイズに対する頑健性（ｒｏｂｕｓｔｎｅｓｓ）の程度と、回転、スケール、および、キーポイントの検出の実行が要求されるときに生じる他の一般的なイメージ劣化による変化の程度である。
【０００５】
従来技術では、かなり多くの計算量を必要とし、これは全体の性能を制限する。
【課題を解決するための手段】
【０００６】
本発明の一態様の方法は、入力イメージのインテグラルイメージを計算するステップと、複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成するステップであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、ステップと、スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせるステップと、前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別するステップと、前記安定したキーポイント位置をメモリストレージに格納するステップと、を含むことを特徴とする、局所化されたスケール空間特性を使用してピクチャイメージ内の安定したキーポイントを見つける方法である。前記フィルタは、異なるサイズの長方形フィルタであってよい。前記構成するステップは、前記フィルタサイズに関わりなく所定の回数の演算を含んでいてよい。
【０００７】
また、本発明の１つの態様のシステムは、電子データ処理システムであって、前記電子データ処理システムのメモリに格納されたソフトウェア動作を処理できる少なくとも１つのプロセッサを含み、動作の前記処理が、入力イメージのインテグラルイメージを計算することと、複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成することであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、構成することと、スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせることと、前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別することと、前記安定したキーポイント位置をメモリストレージに格納することと、を含むことを特徴とする、電子データ処理システムである。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態の概念を実施できる環境を示す図である。
【図２Ａ】安定したキーポイント識別動作の応用を表し、スクリーンに表示されたクエリカメライメージを示す図である。
【図２Ｂ】安定したキーポイント識別動作の応用を表し、スクリーンに表示されたクエリカメライメージにおける識別されたキーポイントの位置を示す図である。
【図２Ｃ】安定したキーポイント識別動作の応用を示し、カメライメージの印刷された版（バージョン）を表す図である。
【図２Ｄ】安定したキーポイント識別動作の応用を示し、カメライメージの印刷された版において定義されたキーポイントを示す図である。
【図２Ｅ】安定したキーポイント動作の応用のさらなる例を示し、ターゲットイメージを示す図である。
【図２Ｆ】安定したキーポイント動作の応用のさらなる例を示し、ターゲットイメージのキーポイントを示す図である。
【図３】インテグラルイメージ（ｉｎｔｅｇｒａｌ ｉｍａｇｅ）を計算する効率的な方法を示す図である。
【図４Ａ】３つの基本的なフィルタタイプのうちの水平フィルタを示す図である。
【図４Ｂ】３つの基本的なフィルタタイプのうちの垂直フィルタを示す図である。
【図４Ｃ】３つの基本的なフィルタタイプのうちの対角フィルタを示す図である。
【図５Ａ】単位分散ガウス関数を示す図である。
【図５Ｂ】水平軸Ｘに関する単位分散ガウス関数の二次偏導関数を示す図である。
【図５Ｃ】垂直軸Ｙに関する単位分散ガウス関数の二次偏導関数を示す図である。
【図５Ｄ】ＸとＹの両方のカスケードされた一次偏導関数に関する、対角線方向に関する単位分散ガウス関数二次偏導関数を示す図である。
【図６Ａ】図４Ａのフィルタタイプの単純化された版を示す図である。
【図６Ｂ】図４Ｂのフィルタタイプの単純化された版を示す図である。
【図６Ｃ】図４Ｃのフィルタタイプの単純化された版を示す図である。
【図７Ａ】スケール空間ピラミッドを作成する、ＳＩＦＴのＤｏＧ法を示す図である。
【図７Ｂ】スケール空間ピラミッドを作成する、ＳＩＦＴのＤｏＧ法を示す図である。
【図８Ａ】水平フィルタのスケール空間ピラミッドを構成する方法を示す図である。
【図８Ｂ】垂直フィルタのスケール空間ピラミッドを構成する方法を示す図である。
【図８Ｃ】対角フィルタのスケール空間ピラミッドを構成する方法を示す図である。
【図９】スケール空間ピラミッド層を作成するのに使用されるフィルタのセットを示す図である。
【図１０】スケール空間領域でＤ（ｘ，ｙ，ｓ）の極値点を検索する方法を示す図である。
【図１１】現在の層スケールでの対でのピクセルのテストを示す図である。
【図１２】３つの連続する層スケールの間の候補ピークに関する対でのピクセルテスティングを示す図である。
【図１３Ａ】スケール空間手法を使用するキーポイント識別プロセスを示し、入力イメージを示す図である。
【図１３Ｂ】スケール空間手法を使用するキーポイント識別プロセスを示し、水平フィルタの出力を示す図である。
【図１３Ｃ】スケール空間手法を使用するキーポイント識別プロセスを示し、垂直フィルタの出力を示す図である。
【図１３Ｄ】スケール空間手法を使用するキーポイント識別プロセスを示し、対角フィルタの出力を示す図である。
【図１３Ｅ】スケール空間手法を使用するキーポイント識別プロセスを示し、水平フィルタ、垂直フィルタ、及び対角フィルタの組み合わせの出力を示す図である。
【図１４】スケール空間ピラミッド層から安定したキーポイントの位置を識別するプロセスを示す図である。
【図１５】図の最下部に入力イメージがある、スケール空間イメージピラミッドを示す図である。
【発明を実施するための形態】
【０００９】
本明細書で説明されるシステムおよび方法は、図１に示されたコンピュータネットワークのパラメータ内で働くことができる。コンピュータネットワーク１００は、一連のワイヤ１０２からなるものとすることができ、ワイヤ１０２の多くは、分岐するかワイヤジャンクション１０４で第３のワイヤ１０６と接続されてもよく、独立型周辺デバイスに接続されるか、コンピュータ１０８，１０９などの他のデバイスに接続するために周辺機器を通過してもよく、ここで、コンピュータは、周辺デバイスと考えることができる。ネットワークは、カラープリンタ１１０またはカラー以外のプリンタ１１２、ならびに少なくともカラーレーザプリンタ１２０，１２２またはカラー以外のレーザプリンタ１２４を組み込んでもよい。ネットワークは、スキャナ１３０、またはファクシミリ機１４０、写真複写機１５０、カラー写真複写機１５２、あるいは組合せカラープリンタ／スキャナ／ファクシミリ機１５４を組み込むこともできる。ネットワークは、パーソナルコンピュータおよび／または独立型コンピュータ端末１６０、あるいは独立型ハードドライブデータストレージ媒体１６４を含むこともできる。ネットワークは、無線ネットワーク送受信器１７０を含み、少なくとも１つのラップトップコンピュータ１７２または複数のラップトップコンピュータ１７４とインターフェースすることもできる。ネットワークは、インターネット、イントラネット、または他の通信ネットワークを含むがこれらに限定されない任意の形のネットワーク１８０に相互接続されてもよい。別の形のネットワークとのインターフェースの使用を介して、本システムおよび方法は、ディジタルスチルカメラ１９１、ディジタルビデオカメラ１９２、セル電話機１９３、スキャナ１９４、携帯情報端末１９５、または文書インデクシングシステム１９６を含むがこれらに限定はされない複数の周辺データ取り込みデバイス１９０とインターフェースすることができる。本概念を、単一のデバイスを有するネットワークから数千個以上の接続されたデバイスを含むネットワークにいたる、上記のコンポーネントのさまざまな組合せを有するネットワーク内で実施できることを理解されたい。さらに、上のコンポーネントのうちのさまざまなコンポーネントは、説明される概念を実施するのに有用である可能性がある複数の既知の構成のいずれかに配置されたメモリストレージエリアを有することができる。このストレージエリアは、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、フラッシュメモリ、または本発明の実施形態の概念を組み込んだソフトウェアを保持できる他のメモリタイプとすることができる。他のメモリストレージエリアを、複数のデータベースフォーマットのいずれかのさまざまなディジタルイメージを保持するように構成してもよい。
【００１０】
コンピュータなどであるがこれに限定はされない図１のコンポーネントのうちのさらなるさまざまなコンポーネントは、そのコンポーネントにロードされるか他の形でそのコンポーネントによってアクセス可能なソフトウェアからの命令を処理するプロセッサを含む。プロセッサを有するコンポーネントのうちのさまざまなコンポーネントが、複数のプロセッサを有してもよく、これによって、命令の処理を複数のプロセッサの間で分割できることを理解されたい。代替案では、単一のプロセッサが、命令を分割するように動作でき、これによって、処理をマルチスレッド環境で行うことができる。
【００１１】
図２Ａ〜図２Ｆに、本発明の実施形態のシステムおよび方法を使用する安定したキーポイント識別の成功した適用の例を示す。図２Ａに、スクリーンに表示されたカメライメージを示すが、このカメライメージは、多数のイメージのデータベース内にあるものとすることができる、図２Ｅのイメージなどのターゲットイメージを識別する試みに使用される劣化したクエリイメージである。同様に、図２Ｃのイメージは、やはり図２Ｅに示されたターゲットイメージから劣化した（たとえば、イメージの一部の上に妨害を有する）印刷された版のクエリカメライメージのもう１つの例である。図２Ａ、図２Ｃ、および図２Ｅのイメージに対して本発明の実施形態のシステムおよび方法を動作させて得られるキーポイント位置を、それぞれ図２Ｂ、図２Ｄ、および図２Ｆに示す。３つのスケールで得られたキーポイント位置が示され、最小スケール位置は「ｘ」でマークされ、中間スケール位置は「□」でマークされ、最大スケール位置は「ｏ」でマークされている。最小スケール位置は、最小サイズのフィルタの使用によって識別され、中間スケール位置は、最小サイズのフィルタのスケールアップ版（スケールをより大きくした版）である中間サイズのフィルタの使用によって識別され、最大スケール位置は、中間サイズのフィルタのスケールアップ版である最大サイズのフィルタの使用によって識別される。したがって、図２Ａ〜図２Ｆは、以下でより詳細に開示する本発明の実施形態のシステムおよび方法の動作の結果を示す。
【００１２】
イメージの間のイメージ品質、解像度、および変化する照明のかなりの差にもかかわらず、図２Ｅのターゲットイメージに対応する図２Ｆのキーポイントの多くは、それぞれ図２Ａおよび図２Ｃの劣化したイメージに対応する図２Ｂおよび図２Ｄにも見られる。
【００１３】
本発明の実施形態のシステムおよび方法の概要は、次の概念を含む。
【００１４】
（ａ）フィルタサイズに関わりなく少数の加算だけで入力イメージ上の任意のサイズの長方形フィルタ形状の出力をすばやく計算できるようにするために入力イメージのインテグラルイメージを計算する。
【００１５】
（ｂ）複数のスケールで入力イメージのスケール空間ピラミッド層表現を構成する。各スケールでは、特定のフィルタのセットを入力イメージに適用して、入力イメージの少なくとも一部の近似を作る。一実施形態で、近似は、ラプラシアン・オブ・ガウシアン（ＬｏＧ）関数の形とすることができる。各連続するフィルタは、前のフィルタのスケールアップ版である。フィルタの出力を一緒に組み合わせて、スケールおよび空間の単一の関数Ｄ（ｘ，ｙ，ｓ）を形成する。
【００１６】
（ｃ）安定したキーポイント位置は、各スケールで、関数Ｄ（ｘ，ｙ，ｓ）がスケール空間近傍内で局所的なピーク値（最大値または最小値のいずれか）を達成するピクセル位置として識別される。
【００１７】
上のステップを採用することによって、ＳＩＦＴを含む既存の方法より計算において高速であり、なおかつイメージ内の安定したキーポイントの識別において同等に効率的と思われる手順がもたらされる。
【００１８】
本発明の実施形態は、ＳＩＦＴによって提案される入力イメージの事前の補間を主張しない。
【００１９】
本発明の実施形態のシステムおよび方法の詳細を、以下で提供する。
【００２０】
Ｉ．１ インテグラルイメージ
インテグラルイメージを計算する効率的な方法を図３に示す。処理される入力イメージを、図３の上側部分３００に示し、対応するインテグラルイメージの出力を、図３の下側部分３０１に示す。
【００２１】
現在のピクセル３０２でのインテグラルイメージの値は、３００の左上角の原点３０５を含み、右下角としての現在のピクセル位置３０２までで現在のピクセル位置３０２を含む長方形区域内のすべてのピクセル値の合計として定義される。効率の一態様は、前に計算された結果を可能な範囲まで活用することである。入力イメージは、一般に、ラスタスキャン順で一時に１ラインずつ処理され、１ライン内では、たとえば左から右へ一時に１ピクセルずつ処理される。
【００２２】
任意の現在のピクセル位置３０２でのインテグラルイメージの値は、次の２つの量すなわち、（１）前のサブ区域３０４（現在のピクセル位置の正確に１つ前のラインのピクセル位置のインテグラルイメージ値として既に計算済み）と、（２）現在のライン上の最初のピクセルから始まり現在のピクセル値３０２までで現在のピクセル値３０２を含む、現在のサブライン３０３上のピクセル値の和と、を一緒に合計することによって構成することができる。
【００２３】
インテグラルイメージは、長方形区域のピクセル値の合計に基づく。この方法は、ここで、入力イメージが共通のラスタスキャン順で得られると仮定する。しかし、行および列の役割は、イメージが通常のラスタスキャン行順ではなく列順で得られる場合に、簡単に逆転することができる。
【００２４】
インテグラルイメージを計算する効率的な方法は、ラインアレイ３０６および３０７を使用して、正確に１イメージライン前のインテグラルイメージの結果を保持することによる。ラインアレイ内の要素の総数は、入力イメージの単一ライン内のピクセル数と正確に同一である。このアレイは、一次ストレージ用の環状バッファとして使用されている。
【００２５】
ラインの始めから現在のピクセル位置３０２までのラインアレイピクセル値３０６は、前に処理されたインテグラルイメージ値および現在のライン上のピクセルの更新されたインテグラルイメージ値を含む。これらの値は、次のイメージラインの後続処理のために格納されている。それと同時に、現在のピクセル位置３０２から順方向にラインアレイの終りまでのラインアレイピクセル値３０７は、まだ更新されていない、前のライン上の前のインテグラルイメージ値を含む。現在のピクセル位置３０２のそれぞれで、前のラインのインテグラルイメージ値が、現在のアレイピクセル位置３０２から読み取られ、現在のインテグラルイメージ値を計算するために適用され、その後、更新された結果が、ラインアレイ３０７に書き戻されて、この位置の以前の値を上書きする。次に、このプロセスは、現在のライン上の次のピクセルに進む。このリード（読出し）・モディファイ（更新）・ライト（書込み）サイクルは、ラインの終りに達するまで、ピクセル位置ごとに継続する。
【００２６】
各ピクセル位置で、現在のピクセル値３０２が、まず、図３の最下部に示された加算器３０９を使用して、前の行の和３０８に加算される。行の和は、現在の行の始めから現在のピクセル位置３０２までのピクセル値のランニングサム（ｒｕｎｎｉｎｇ ｓｕｍ）を累算するのに使用される内部レジスタである。行和レジスタは、各ラインの始めに０にリセットされる。加算器３０９の出力は、行和レジスタに書き戻されて、各ピクセル位置でのその値を更新する。更新された行和値は、現在のサブライン３０３と現在のピクセル値３０２との合計と同等である。
【００２７】
更新された行和値３０８は、次に、第２の加算器３１０を使用して、正確に１ライン戻った前のラインのインテグラルイメージ値３０７に加算される。というのは、その内容が、まだ現在のピクセル位置３０２によって更新されていないからである。加算器３１０の出力は、結果として得られる現在のピクセル位置３０２でのインテグラルイメージ値である。この結果は、次のラインの後続処理のためにその値を保持するために、現在のピクセル位置３０２でのラインアレイに書き戻される。したがって、各ラインアレイ要素は、一時に１ピクセルずつ単一のリード・モディファイ・ライトサイクルを受け、これによって、後に続くラインでの連続した再利用のためにインテグラルイメージ値を一時的に保持するためにラインアレイに連続的な１ラインランニングバッファウィンドウを同時に提供する。
【００２８】
上で提案した方法を使用すると、インテグラルイメージ全体の計算が、１ピクセルあたり２つの加算だけを必要とする。動作全体を、もちろん、並列に動作する２つの別々の加算器を使用してパイプライン化して、インテグラルイメージ計算を１ピクセルあたり単一の二重加算に減らすことができる。したがって、インテグラルイメージは、計算が速く、所定のイメージについて１回だけ計算すればよい。インテグラルイメージを計算した後に、その結果を繰り返して効率的に使用して、以下で説明する形で、さまざまな長方形フィルタ形状の計算を劇的に加速することができる。カスケードされたフィルタリングの伝統的な手法とは異なって、インテグラルイメージは、区域サイズに関わりなく固定された一定の時間で任意の長方形フィルタ区域の出力を計算する能力を提供する。
【００２９】
Ｉ．２ 個々のスケール空間層の構成
スケール空間表現を作成する伝統的な手法は、イメージピラミッドによるものである。既存の方法の短所は、イメージピラミッドが、通常はガウシアンフィルタを繰り返して適用することと、その後、より大きいスケールに対応するより上のピラミッドレベルを入手するために入力イメージをダウンサンプリングすることとによって構成されることである。既存の方法によるイメージピラミッド構成プロセスを、次のように示すことができる。入力イメージを、まず補間して、たとえばＳＩＦＴ法と同様に、各方向でイメージ寸法を２倍にしてよい。次に、０平均および分散σのガウシアンフィルタを、サイズを増やされたイメージに適用して、第１の最小スケールのピラミッド層である出力イメージを作る。次に、結果の第１イメージ層を、２倍だけダウンサンプリングし、０平均および（√２）σの同等の分散の第２ガウシアンフィルタを適用して、第２の１つ大きいスケールの第２イメージピラミッド層を作る。各後続層は、前のピラミッド層出力をダウンサンプリングし、徐々により大きくなるガウシアンフィルタを結果のイメージに効果的に適用して、次のピラミッド層を作ることによって作られる。したがって、イメージピラミッドを作るプロセス全体は、順次的性質を有し、各後続空間スケールピラミッド層は、より小さいスケールの前のすべてのピラミッド層に完全に依存し、したがって、すべての他の層と同時に計算することはできない。さらに、各方向でサイズＮピクセルの一般的な分離不能正方形ガウシアンフィルタは、計算にオーダーＯ（Ｎ2）の乗算および加算を必要とし、Ｏは、演算の回数である。演算の回数は、フィルタ面積サイズに比例し、したがって、各後続層は、増加したフィルタサイズに起因して前の層に対して相対的に計算により長い時間を要し、やはり、後続する層の結果を後のステージでキーポイント抽出に同時に使用可能にするために、後続する層の結果をメモリに格納することが必要になる。フィルタ動作の数は、フィルタが分離可能である場合にはＯ（Ｎ）回の乗算およびＯ（２Ｎ）回程度の加算に減らすことができるが、それでも、複数のスケールについて計算するのにかなりの時間を要する。
【００３０】
さらに、再帰的にフィルタリングし、ダウンサンプリングする必要のゆえに、このプロセス全体が、直列の性質を有し、より高い次数のレベルの計算を、すべてのピラミッドレベルについて同時に得ることはできない。しかし、キーポイント識別プロセスは、ある個数のレベル（通常、少なくとも３つから４つ）の同時使用可能性に依存する。したがって、中間ピラミッドレベルを、後の使用のためにメモリ内に格納しなければならない。
【００３１】
既存の手法のように複数スケールイメージピラミッドを作成するために入力イメージを繰り返してフィルタリングし、ダウンサンプリングするのではなく、本システムおよび方法は、水平方向、垂直方向、および対角線方向での入力イメージの局所化可能な特性の直接識別に基づく異なる手法を使用する。さまざまなフィルタ出力を一緒に組み合わせて、入力イメージ内の局所化可能な「しみ様（blob-like）」の特徴および「接合点様（junction-like）」の特徴を識別する。
【００３２】
さらに、以前の方法のように、予めフィルタリングされダウンサンプリングされた版の入力イメージの（徐々に小さくなる）出力にガウシアンフィルタを反復的に適用するのではなく、本発明の実施形態のシステムおよび方法は、フィルタをアップサンプリングし、より大きいフィルタ版をオリジナルの入力イメージに直接に適用する。したがって、より大きいスケールのそれぞれで、入力イメージは一定のままにしながら、以前のフィルタ形状を、たとえばサイズにおいて２倍にすることができる。
【００３３】
一見すると、この見た目には良好なスケーリング透視の変化は反直観的に見える。しかし、本システムおよび方法において、固定されたフィルタおよび順次小さくなるイメージサイズを固定されたイメージおよび順次大きくなるフィルタサイズに置換することが、性能の改善をもたらし得ることがわかった。
【００３４】
この手法の利益は、より大きいフィルタを、既存の方法のように以前のフィルタ出力を使用して反復的にカスケードする必要なしに、オリジナルの入力イメージに直接に適用できることである。さらに、インテグラルイメージおよび特定のフィルタ形状の使用に起因して、任意のサイズのフィルタを処理するのに、正確に同一の長さの時間を要する。したがって、すべてのフィルタを、そのサイズと独立に、正確に同一の速度で計算することができる。さらに、各長方形フィルタ領域は、そのサイズに関わりなく、インテグラルイメージを使用して計算するのに少数の加算だけを必要とする。
【００３５】
その結果、提案されるシステムおよび方法は、既存の伝統的な反復手法に対する相対的な性能改善を入手しながら、なおかつイメージ内の堅牢なスケール不変キーポイントの位置の識別において同等に効果的である。
【００３６】
図４Ａ〜図４Ｃに、本発明の実施形態によるスケール空間ピラミッドの個々の層を構成するのに使用される３つの基本的なフィルタタイプを示す。
【００３７】
各スケールで、３つの別々のフィルタすなわち、（ａ）図４Ａの水平フィルタ、（ｂ）図４Ｂの垂直フィルタ、および（ｃ）図４Ｃの対角フィルタが入力イメージに適用される。「Ｘ」を用いてマークされた各フィルタの中央位置は、その回りにフィルタウィンドウが位置決めされる、入力イメージの現在のピクセル位置である。
【００３８】
各フィルタのサイズは、それに適用されるスケールに比例する。各フィルタが、長方形区域のセットからなることに留意されたい。というのは、その意図が、高速計算のためにインテグラルイメージを適用することであるからである。また、図４Ｂの垂直フィルタが、図４Ａの水平フィルタ形状を９０度回転した版であることに留意されたい。
【００３９】
図４Ａの水平フィルタ形状は、すべてのピクセル値が所定の極性、たとえば＋ｐをとる中央領域（斜めの線のパターンを用いて図示）と、すべてのピクセル値が反対の極性、たとえば−ｍをとる２つの外側領域（水平線のパターンを用いて図示）とからなり、ここで、「ｐ」および「ｍ」は、２つのゼロでない整数値である。
【００４０】
中央領域が正であり、外側領域が負であるか、または、その反対であるかという２つの領域タイプの間の極性割り当ての意味は、一貫性をもって適用される限り、任意である。
【００４１】
図４Ａで白い領域として図示されたオプションの「ガードバンド」は、領域をお互いから分離するために、反対の領域タイプの間の境界に沿って導入される。この「ガードバンド」の目的は、フィルタ安定性を改善し、極性において変動する可能性がある、領域境界に沿ったノイズのあるピクセルを除外することによって、ノイズに対する感度を最小化することである。「ガードバンド」領域の内側のすべてのピクセル値に、０の値が割り当てられる。
【００４２】
したがって、各フィルタピクセルの値は、３つの可能な値｛−ｍ，０，＋ｐ｝のうちの１つをとる。「ｐ」および「ｍ」の値は、一実施形態では整数値であり、相対領域面積サイズに基づいて一定の入力イメージの場合の偏りのないフィルタ出力をもたらすように選択される。たとえば、水平フィルタまたは垂直フィルタの場合に、式
ｐ／ｍ＝ｂ1／（ｃ−ｂ2）
を満足するように「ｐ」および「ｍ」の値の対を選択する。
【００４３】
ｂ1、ｂ2、およびｃのすべてが、整数ピクセル番号値なので、「ｐ」および「ｍ」の対を見つけることが可能である。
【００４４】
各フィルタの形状は、４つのパラメータ値｛ａ，ｂ1，ｂ2，およびｃ｝のセットによってパラメータ化される。これらのパラメータの値は、スケールに比例する。フィルタサイズがスケールアップされると、すべてのパラメータ値が比例して増やされる。ただし、フィルタ形状は比例して正規化されたままに保たれる。また、４つのパラメータ値｛ａ，ｂ1，ｂ2，およびｃ｝が、必ずしも、水平フィルタまたは垂直フィルタについて対角フィルタと同一である必要がないことに留意されたい。
【００４５】
水平フィルタは、水平方向でよく局所化可能な、入力イメージ内の候補の高く狭い「細長い」特徴を検出するように設計される。外側領域に対して相対的により暗いまたはより明るい中央領域などであるがこれに限定はされない特徴極性は、後述するように、フィルタ出力の大きさを使用することによって無視される。フィルタ出力の大きさは、現在のピクセル位置ごとの中央フィルタ領域と外側フィルタ領域との間のコントラスト差に効果的に比例する。
【００４６】
図４Ａの水平フィルタは、一般に、幅２×ｂ1および高さ２×ｃの狭く高い中央領域を有し、ｂ1＜ｃである。同様に、この水平フィルタは、組み合わされた幅２×（ａ−ｂ2）および高さ２×ｃの２つの外側領域をも有する。幅（ｂ2−ｂ1）および高さ２×ｃを有するオプションの狭く高い垂直「ガードバンド」を、中央領域と外側領域との間に挿入してもよい。あるいは、パラメータ値ｂ2＝ｂ1をセットすることによって、「ガードバンド」を完全に除去することが可能である。
【００４７】
図４Ｂの垂直フィルタは、垂直方向でよく局所化可能である入力イメージ内の候補の幅広く短い「細長い」特徴を検出するように設計される。垂直フィルタの形状は、図４Ａの水平フィルタを９０度回転した版である。
【００４８】
図４Ｃの対角フィルタは、対角線方向でよく局所化可能である入力イメージ内の候補の「細長い」特徴を検出するように設計される。対角フィルタの形状は、４つの長方形領域からなり、そのうちの２つは（対角線パターンを用いて図示）、一方の対角線方向に向けられ、他方の２つ（水平線パターンで図示）は、他方の対角線方向に向けられる。すべての領域サイズが、対角フィルタの場合には同一なので、フィルタ応答は、設計によって既に偏りをなくされており、上述の「ｐ」および「ｍ」ではなく＋１または−１の値を、上記で示したように領域タイプに応じてこれらの領域のそれぞれのすべてのピクセル値に割り当てることで十分であることに留意されたい。
【００４９】
対角フィルタが、図４Ｃでその主軸に沿った白い領域として示されたオプションの「ガードバンド」をも含むことに留意されたい。「ガードバンド」領域は、フィルタ安定性およびノイズに対する免疫性を改善するために、対向する領域タイプの境界に沿って導入される。「ガードバンド」領域内のすべてのピクセル値には、０の値が割り当てられる。長方形対角フィルタの一般的なケースについて、「ガードバンド」は、水平軸の回りで２×ｂ2の幅および垂直軸の回りで２×ｂ1の幅を有する。「ガードバンド」の幅は、ｂ1＝ｂ2を選択することによって対称にすることができ、または、ｂ1＝ｂ2＝０を選択することによって完全に除去することができる。「ガードバンド」区域を含まない各領域タイプの総面積は、対角フィルタについて２×（ａ−ｂ1）（ｃ−ｂ2）である。
【００５０】
パラメータ値｛ａ，ｂ1，ｂ2，およびｃ｝の適当な選択を用いると、フィルタの各１つを、それぞれ水平方向、垂直方向、および対角線方向のガウシアンカーネルの二次偏導関数の近似とみなすことができる。より具体的には、図５Ａに、単位分散ガウシアンフィルタ関数を示す。これは、より一般的なケースの分散σではなく正規化された分散１を有することを除いて、最小スケールで図２Ａの入力イメージに適用される平滑化フィルタである。
【００５１】
単位分散ガウス関数の水平、垂直、および対角の二次偏導関数を、それぞれ図５Ｂ、図５Ｃ、および図５Ｄに示す。この文脈での対角二次導関数は、水平一次偏導関数と垂直一次偏導関数との積である。平滑化ガウシアン二次導関数は、各ケースで長方形のトライナリ（すなわち、３つの）フィルタ形状を用いて近似される。
【００５２】
本システムおよび方法は、入力イメージのダウンサンプリングを利用しないので、平滑化および事前フィルタリングの必要が大幅に減らされる。したがって、本手法によれば、図４Ａ〜図４Ｃのフィルタのそれぞれは、スケールが増えるにつれてますます大きくなる区域サイズにまたがる平均化フィルタである。しかし、ある平滑化を、ノイズに対する高められた頑健性を提供し、ブロッキングアーティファクト（blocking artifact）を最小化するために、後続フィルタ位置をわずかにオーバーラップさせることによって実現することができる。１／４から１／２までのフィルタオーバーラップ方式を各方向で使用することが、優れた結果をもたらす。これは、所定のスケールでの次のフィルタ位置を、ａ／２とａの間の値だけ水平方向で前進させ、これによって、前のフィルタ位置に部分的にオーバーラップさせることを意味する。ラインの終りに達した時に、次のフィルタ位置も、ｃ／２とｃの間の値だけ垂直方向で下に移動され、前のフィルタ位置との部分的垂直オーバーラップにもつながる。
【００５３】
この手法の第１の態様は、インテグラルイメージの長方形のフィルタ形状に起因して、フィルタ結果を計算するのに少量の加算だけを要することである。各長方形フィルタ領域は、インテグラルイメージを使用して計算するのに、そのサイズに関わりなく４回の加算だけを必要とする。追加の節約を、隣接領域区域が共通の境界を共有する時に行うことができる。たとえば、図４Ａの水平フィルタを計算するには、通常は３×４＝１２回の加算が必要になる。というのは、このフィルタが１つの中央領域および２つの外側領域を含むからである。しかし、「ガードバンド」領域がない場合には、外側領域をフィルタ区域全体［（−ａ，−ｃ）から（ａ，ｃ）］に延長することと、余分な外側区域の加算を無にするためにそれ相応に「ｐ」および「ｍ」の値を調整することとによって、水平フィルタ全体を１２ではなく８クロックだけで計算することができる。「ノイズバンド」領域なしの単純化された水平フィルタ、垂直フィルタ、および対角フィルタの形状を、それぞれ図６Ａ〜図６Ｃに示す。図６Ａ〜図６Ｃの単純化されたフィルタ形状は、図４Ａ〜図４Ｃのオリジナル形状より計算が高速であるが、「ノイズバンド」領域の欠如に起因して、ノイズに対して図４Ａ〜図４Ｃのオリジナル形状ほど頑健（robust）ではない。ノイズの多い入力イメージの状況では、図６Ａ〜図６Ｃの単純化されたフィルタ形状ではなく、図４Ａ〜図４Ｃのオリジナルフィルタ形状を適用することが好ましい場合がある。
【００５４】
本手法の第２の態様は、フィルタを計算するのに要する動作および時間の量が、フィルタサイズに関わりなく正確に同一のままになる固定された定数であることである。たとえば、図４Ａの水平フィルタが、サイズにおいて２倍にされる場合に、このフィルタは、計算に同一回数の加算を要する。というのは、より大きいフィルタ形状が、それでも、比例して調整された角の点を有する３つの長方形領域からなるからである。これは、ガウシアンフィルタを繰り返して使用し、前のフィルタ出カをダウンサンプリングする場合と対照的であり、この場合に、各より高いピラミッドレベルは、追加の計算を必要とし、前のレベルに加えて余分な時間を要する。
【００５５】
本手法の第３の態様は、任意の順次ピラミッドレベル処理の除去である。これは、本システムおよび方法が、必ず、どのスケールレベルでもフィルタタイプごとに正確に同一の入力イメージを適用するという事実の直接の結果である。入力イメージをフィルタリングする必要は全くなく、したがって、すべての前のピラミッドレベルの完了時に、後続レベル用の入力を得るために前のレベルの出力をフィルタリングし、ダウンサンプリングする必要がある、１つのピラミッドレベルの順次依存性は、除去される。したがって、あるピラミッドレベルの計算は、他のすべてのピラミッドレベルから完全に分離される。
【００５６】
本手法の第４の態様は、並列処理および／またはマルチスレッド環境での実行に理想的に適することである。これは、本システムおよび方法が、未知の入力イメージではなくフィルタをスケーリングすることを選択するからである。フィルタ形状は前もってすべてわかっているので、すべてのタイプ、サイズ、およびスケールのスケーリングされたフィルタ形状のセット全体を、前もって生成し、複数のプロセッサが使用可能な場合には並列に、または別々のスレッドで、入力イメージに適用することができる。ピラミッドレベルの間の任意の依存性の欠如に起因して、スケール空間ピラミッドを作成する処理方式全体を、並列に実行することができる。
【００５７】
本手法の第５の態様は、複数のプロセッサまたはスレッドの間で計算負荷を平衡化することのたやすさである。これは、ほぼすべてのフィルタが、本手法に従って計算される時に、フィルタサイズに関わりなく計算に正確に同一の時間を要するという特性の結果である。したがって、スケール空間ピラミッドを作成する作業は、それぞれが実行にほぼ同一の時間を要する複数のプロセッサまたはスレッドの間で均等に分割することができ、このプロセスの終りに、必要な個数のピラミッドレベルが、結果をメモリに格納する必要なしに、および／または不均一な計算負荷に起因するアイドル状態のプロセッサを有することなく、後続のキーポイント識別に使用可能にされる。
【００５８】
この手法の第６の態様は、より大きいスケールのさらにより大きいフィルタを有するより高いピラミッドオクターブについて、後続のフィルタの位置の間の距離を、計算負荷をさらに減らすために比例して増やすこともできることである。より高いオクターブについて、対応する「しみ様」および／または「接合点様」の特徴は、さまざまなフィルタ出力を一緒に組み合わせた後に、やはり非常に大きくなり、したがって、詳細なサブピクセル精度でその位置を正確に指摘する必要なしに処理することができる。しかし、望まれる場合に、より高いピラミッドオクターブについて追加の補間方式を導入することができる。というのは、結果として得られる後続のフィルタの位置の間の距離が、大きくなる可能性があるからである。
【００５９】
Ｉ．３ スケール空間ピラミッドの作成
スケール変化に対して不変のキーポイントの位置を識別する伝統的手法は、スケール空間として知られるスケールと空間との両方の連続関数を構成し、複数のスケールにまたがって安定した特徴を検索することである。
【００６０】
前述のように、スケール空間ピラミッドを生成する１つの既存の方法は、ＳＩＦＴ法に見られる。ＳＩＦＴ法は、代替のディファレンス・オブ・ガウシアン（ＤｏＧ）関数を用いるラプラシアン・オブ・ガウシアン（ＬｏＧ）法の近似（最初は、リンドバーグ、「Ｓｃａｌｅ Ｓｐａｃｅ Ｔｈｅｏｒｙ： Ａ Ｂａｓｉｃ Ｔｏｏｌ ｆｏｒ Ａｎａｌｙｚｉｎｇ Ｓｔｒｕｃｔｕｒｅｓ ａｔ Ｄｉｆｆｅｒｅｎｔ Ｓｃａｌｅｓ」、Ｊｏｕｒｎａｌ ｏｆ Ａｐｐｌｉｅｄ Ｓｔａｔｉｓｔｉｃｓ，Ｖｏｌ．２１，Ｎｏ．２，２２４〜２７０ページ、１９９４年で提案された）に基づく。
【００６１】
スケール空間ピラミッドを作成するＳＩＦＴ法の概念を、図７Ａ〜図７Ｂに示す。スケール空間のオクターブごとに（図７Ａは、１つのスケールを示し、図７Ｂは、追加のフィルタリングおよびダウンサンプリングの後のより高いスケールを示す）、初期入力イメージが、ガウシアンフィルタのセットを用いて繰り返して畳み込まれて、図７Ａ〜７Ｂの左側に示されたスケール空間イメージのセットを作る。隣接するガウシアンフィルタリングされたイメージは、減算されて、図７Ａ〜７Ｂの右側のディファレンス・オブ・ガウシアンＤ１〜Ｄ３イメージを作る。各オクターブの後に、前のオクターブからのガウシアンイメージが、２倍ダウンサンプリングされ、この処理が、繰り返される。スケール空間ピラミッドを作成する反復処理の概念を、図１５に示す。入力イメージは、図１５の最下部に示され、その上に、特定のスケールのガウシアンフィルタを用いるガウシアンフィルタリングおよびダウンサンプリングの３つの連続する反復の後のカスケードされた結果がある。隣接するガウシアンイメージを減算した後に、結果のディファレンス・オブ・ガウシアンＤ１〜Ｄ３イメージが、識別されたキーポイントを円によって強調表示された状態で図１４に示されている。
【００６２】
次では、既存概念からの進歩を開示するが、オリジナルラプラシアンオブガウシアン（ＬｏＧ）関数は、上で説明したインテグラルイメージの特性を活用する機会を可能にするＳＩＦＴ法の（ＤｏＧ）と異なる新しい近似に置換される。
【００６３】
上のセクションＩ．２で説明したように、図４Ａ〜図４Ｃのフィルタは、ガウス関数の二次偏導関数のトライナリ近似を提供する。したがって、フィルタ出力を一緒に組み合わせて、ラプラシアン・オブ・ガウシアン（ＬｏＧ）の近似を提供することができる。ラプラシアン・オブ・ガウシアン（ＬｏＧ）は、ある形では、（ＤｏＧ）の近似でもある。本手法が、ＳＩＦＴとは異なり、近似の精度に応じて異なる結果につながる可能性が高いことに留意されたい。
【００６４】
ここで、本概念によるスケール空間差ピラミッドの構成に注意を向ける。
【００６５】
図８Ａ〜図８Ｃでは、少なくとも３つのスケール空間差ピラミッド層が、キーポイント位置を識別するのに必要である。これは、近傍スケールにまたがる安定した特徴を識別するために、現在のスケールと、現在のスケールの下の少なくとも１つのスケールおよび現在のスケールの上の少なくとも１つのスケールを含む。図８Ａは、水平フィルタリング（たとえば、Ｆ１ｈ〜Ｆ３ｈ）を表し、図８Ｂは、垂直フィルタリング（たとえば、Ｆ１ｖ〜Ｆ３ｖ）を表し、図８Ｃは、対角フィルタリング（たとえば、Ｆ１ｄ〜Ｆ３ｄ）を表す。図８Ａ〜８Ｃに示されているように、入力イメージは、連続してより大きくなるフィルタＦ１からＦ３までのセットを用いて処理される。その後、水平フィルタ、垂直フィルタ、および対角フィルタからの結果の出力が、一緒に組み合わされて、キーポイント位置が識別される単一の尺度が形成される。
【００６６】
フィルタＦ１からＦ３は、前のセクションで説明した形でインテグラルイメージを使用して効率的に計算される。
【００６７】
本願の一実施形態で、スケール空間の１つのオクターブは、図８Ａ〜図８Ｃに示された３つのフィルタの最小限のセットを使用することによって形成される。
【００６８】
もう１つの実施形態で、追加のますます大きくなるフィルタが、スケール範囲を拡張するためにＦ３を超えて適用される。たとえば、Ｆ４フィルタ（図示せず）を、図８Ａ〜８Ｃに追加することができ、その水平フィルタ、垂直フィルタ、および対角フィルタの出力を一緒に組み合わせて、キーポイント位置を識別するもう１つの尺度層を形成することができる。しかし、１オクターブ内のフィルタの最大個数は、イメージサイズによって制限される。というのは、これが、イメージサイズより大きい特徴を探すために利益をもたらさないからである。したがって、最大のフィルタサイズは、イメージサイズによって決定される。
【００６９】
１つのオクターブ内に３つを超える異なる層がある時には、層は、近傍スケールにまたがる特徴安定性を保証するために隣接する３つの層を含む組で処理される。すなわち、安定したキーポイント位置は、まず、最初の３つの層｛Ｆ１，Ｆ２，Ｆ３｝の内容に基づいて識別され、３つの層の後続セット｛Ｆ２，Ｆ３，Ｆ４｝からの安定したキーポイント位置が続き、新しい最も高い層｛Ｆ４｝は、最下位の層｛Ｆ１｝を置換し、層｛Ｆ２，Ｆ３｝は、両方のセットに共通する。同様に、３つの層の次のセットは、｛Ｆ３，Ｆ４，Ｆ５｝を含むことができ、以下同様である。しかし、ほとんどの場合に、通常、最初の３つを超える多数の層を使用することは必要ではない。というのは、イメージがサイズにおいて１メガピクセルから２メガピクセルを超えない限り、フィルタサイズおよび対応するイメージ特徴のスケールが、オリジナルイメージサイズによってすばやく制限されるようになるからである。１メガピクセルから２メガピクセルを超える場合には、より多くの層を追加することが有益である可能性がある。
【００７０】
スケール空間ピラミッドの４層オクターブを作成するのに使用される水平フィルタのセットを、図９に示す。所定のオクターブ内で、各後続フィルタＦｉは、さらに、前のフィルタＦ（ｉ−１）に対して相対的に係数「ｓ」だけスケールアップされ、または、最高スケールの最初のフィルタＦ１に対して相対的に合計（ｓ×ｉ）だけスケールアップされる。水平フィルタだけが、図９に示されていることに留意されたい。垂直フィルタおよび対角フィルタは、正確に同じ態様でスケールアップされる。
【００７１】
ＳＩＦＴ法のカスケーディングフィルタの手法では、キーポイント位置を第１オクターブについて識別した後に、結果のイメージが、もう一度ダウンサンプリングされ、フィルタリングされ、隣接フィルタ出力が減算され、その結果が、より高いスケールでの追加のキーポイント位置の検出に使用される。このプロセスは、追加のスケールごとに繰り返される。
【００７２】
しかし、本システムおよび方法では、フィルタリングされたイメージをダウンサンプリングするのではなく、基本的なＦ１〜Ｆ３のフィルタサイズのそれぞれが、２倍にされ、スケール空間層が再度計算され、その後、より高いスケールでの任意の新しい安定したキーポイントが識別される。フィルタ形状Ｆ１〜Ｆ３は、事前に十分にわかっているので、Ｆ１〜Ｆ３のスケールアップされた版のすべてを、事前に計算でき、図１のコンポーネントに含まれるメモリなどであるがこれに限定はされないメモリに格納することができる。したがって、本システムおよび方法は、同時に並列にキーポイント位置を別々に識別することを可能にするという点で、並列処理および／またはマルチスレッド処理に理想的に適する。
【００７３】
オクターブごとにフィルタサイズを２倍にするプロセスは、必要なだけ何度でも繰り返される。やはり、ＳＩＦＴ法とは異なって、任意のスケールでのフィルタへの入力イメージが、必ず同一すなわちオリジナル入力イメージであることに留意されたい。
【００７４】
上の説明では、フィルタを２倍にすることによってフィルタのサイズを変更する。しかし、フィルタのセットを任意の比率について設計できることを理解されたい。これは、連続するライン上のピクセルの間の補間の問題にすぎない。
【００７５】
たとえば、提案される１．５倍の比率をとり、３×３最小サイズ水平フィルタから開始されたい（１つの中央線と２つの反対の極性の外側領域、「ガードバンド」なし）。次に、連続して１．５を乗算することによって、３は４．５、６．７５、１０．１２５などになる。したがって、第２フィルタは、サイズにおいて４．５×４．５であり、それぞれ１．５ラインの高さ（スケーリングによって）の３つの水平領域からなる。
【００７６】
４．５フィルタ高さを半分に分割し、中央領域は、この分割線のそれぞれの側で０．７５ラインを含む。したがって、中央領域は、分割の両側の両方のラインのピクセル値の合計の０．７５倍から計算される。
【００７７】
同様に、外側領域は、
（ａ）分割の両側の両方の周辺のラインのピクセル値の合計の０．２５倍と、
（ｂ）分割の両側の１ライン離れたラインのピクセル値の合計と、
（ｃ）分割の両側の２ライン離れたラインのピクセル値の合計の０．２５倍と、
の合計によって計算される。
【００７８】
後続のより大きいフィルタは、類似する形で得られる。
【００７９】
分かる通り、境界上の共有されるイメージピクセルは、単純に、領域の間の境界線までの距離によって線形に重みを付けられる（すなわち、補間される）。
【００８０】
したがって、この説明は、非整数比が多少の追加の補間および丸めを必要とすることを除いて、任意の比率に拡張することができる。
【００８１】
Ｉ．４ スケール空間での安定したキーポイント位置の識別
本手法の目的は、ターゲットイメージのターゲットのノイズのある（すなわち、ダウングレードされた）版内で高い確率で信頼できる形で見つけることができるイメージ内の安定したキーポイントを識別することである。
【００８２】
ＤｏＧ関数に基づくＳＩＦＴ法とは異なって、本願で説明される手法は、「しみ様」のイメージ特徴および「接合点様」のイメージ特徴の検出に基づく。要件は、これらの「しみ」特徴および「接合点」特徴を、ターゲットイメージのノイズのある版で信頼できる形で見つけることができることと、これらの特徴が、シーン照明および類似物の変動に堅牢であり、また、イメージに対する相対的なある分散特性を有する（すなわち、これらの特徴を、イメージがスケーリングされ回転された版においても高い確率で見つけることができる）ことである。
【００８３】
上のセクションＩ．２で示したように、本システムおよび方法の水平フィルタは、現在のスケールでのフィルタサイズに対応するサイズの水平の「細長い」イメージ特徴について大きい大きさの信号を作る傾向がある。そのような特徴は、水平方向でよく局所化可能であるが、必ずしも垂直方向でよく局所化可能ではない。同様に、垂直フィルタは、垂直方向に局所化可能な特徴について強い大きさの信号を作る。この２つの応答を一緒に組み合わせることによって、水平方向と垂直方向との両方で局所化できるイメージ内の「しみ様」特徴位置を識別することが可能である。
【００８４】
同様に、対角フィルタは、現在のスケールでの対角フィルタサイズに対応するサイズの斜めの「角」イメージ特徴または「接合点様」イメージ特徴について出力で大きい大きさの信号を作るように働く。そのような特徴は、対角線方向でよく局所化可能でもある。このタイプの例は、交番するチェッカーボードの黒白／白黒パターンまたはその逆の４つの隣接する正方形の間の接合点あるいは任意の９０度の暗い角または明るい角を含む。もちろん、イメージ内の他の位置を、接合点として判定することができる。
【００８５】
２つの特徴タイプすなわち「しみ様」イメージ特徴および「接合点様」イメージ特徴を異なるフィルタ出力で別々に見つけることを試みるのではなく、この実施形態では、２つの特徴タイプが、次の単一の特徴尺度に組み合わされる。
【００８６】
Ｄ（ｘ，ｙ，ｓ）＝ＦH（ｘ，ｙ，ｓ）×ＦV（ｘ，ｙ，ｓ）−［ｋ×ＦD（ｘ，ｙ，ｓ）］2
ここで、ＦH（ｘ，ｙ，ｓ）、ＦV（ｘ，ｙ，ｓ）、およびＦD（ｘ，ｙ，ｓ）は、それぞれ図４Ａ〜図４Ｃに示された水平フィルタ出力、垂直フィルタ出力、および対角フィルタ出力であり、ｋ2は、異なるフィルタ形状を有する可能性および整数ピクセル境界での離散値への変換に起因する２つの特徴タイプの間の正規化パラメータである。
【００８７】
「しみ様」イメージ特徴について、対角フィルタの出力での信号の大きさは、小さい可能性が高いが、水平フィルタおよび垂直フィルタの出力での大きさは、大きい。同様に、「接合点様」イメージ特徴について、水平フィルタまたは垂直フィルタの出力は小さい可能性が高いが、対角フィルタの出力の大きさは大きい。したがって、この２つの特徴タイプを、Ｄ（ｘ，ｙ，ｓ）の出力の大きさを最大にするすなわち、Ｄ（ｘ，ｙ，ｓ）の最大点または最小点のいずれかの極値を探すという単一の目標に一緒に組み合わせることができる。したがって、キーポイント位置は、関数Ｄ（ｘ，ｙ，ｓ）がスケールｓと空間（ｘ，ｙ）との両方でその極値点を達成する、イメージ内の位置として識別される。
【００８８】
スケール空間領域での極値点を検索する方法を図１０に示す。差関数Ｄ（ｘ，ｙ，ｓ）は、スケール空間全体にまたがって計算される。（ｘ，ｙ，ｓ）内のピクセル位置（２ｅ）は、関数Ｄ（ｘ，ｙ，ｓ）の値が、図１０に示されているようにその直接近傍に対して最大値または最小値のいずれかのピークである場合に、候補キーポイント位置であると判定される。
【００８９】
あるイメージ内で識別できる安定したスケール不変キーポイント位置の個数は、イメージ内容および以下で定義する所望のキーポイント強さに依存して、かなり変化する。キーポイントの最終的な個数は、所定の通常の自然シーンイメージ内で、数百個から数千個まで変化する可能性がある。したがって、イメージピクセルの大多数は、候補キーポイント位置ではない。したがって、性能の理由から、特定のピクセルが有効なキーポイント位置ではない時に候補キーポイント位置としてのそのピクセル位置をすばやく除外できる方法を探すことが望ましい。明らかに、各ピクセル位置の周囲の近傍ピクセルのすべてをチェックする必要を実際には伴わずに、できる限り高速にそれを行うことが望ましい。
【００９０】
この問題を解決する本願の実施形態の手法は、３重ピクセル比較テストの順序付きセットに基づく。この方法は、ルールベースである。各テストでは、中央ピクセルの両側の対向するピクセルの対を調べる。この方法は、現在のフィルタスケールで空間ピクセル近傍（ｘ，ｙ）平面を調べることによって開始される。近傍は、図１０の中央の平面で９個のピクセル（すべて数字２から始まる）を含む。この近傍の拡大図を、図１１に示す。この方法の目的は、中央ピクセル位置（２ｅ）を候補キーポイント位置にすることができるかどうかを判定することである。
【００９１】
この方法の第１のルールは、図１１の前のピクセル位置（２ｄ）がキーポイント位置として識別されたかどうかをチェックすることである。そうである場合には、位置（２ｄ）での関数Ｄ（ｘ，ｙ，ｓ）の値は、その近傍に対して最大値または最小値でなければならない。したがって、Ｄ（ｘ，ｙ，ｓ）は、１ピクセル離れた位置（２ｅ）でもピーク（すなわち、キーポイント）になることはできず、この場合に、（２ｅ）のテストは、終了し、このプロセスは、次のピクセルに進むことができる。
【００９２】
しかし、前のピクセル位置（２ｄ）がキーポイントではなかった場合に、この方法は、（２ｅ）の両側の対向するピクセル対位置（２ｄ）および（２ｆ）でのＤ（ｘ，ｙ，ｓ）の値を取り出す。中央ピクセル（２ｅ）でのＤ（ｘ，ｙ，ｓ）の値は、（２ｅ）が図１１の方向１に沿ったＤ（ｘ，ｙ，ｓ）の局所極値点としての資格を有するために、最大値の場合には（２ｄ）および（２ｆ）のいずれよりも大きくなければならず、あるいは（２ｄ）および（２Ｆ）より小さくなければならない（最小値の場合）。
【００９３】
さらに、ノイズの存在および／またはあるピクセルから次のピクセルへのＤ（ｘ，ｙ，ｓ）の小さい丸め誤差に起因するランダムな弱いキーポイント位置の偶然の識別の尤度を除去するために、しきい値「Ｔ」を導入する。このしきい値は、次のように定義される。
すべての近傍ｘ，ｙ，ｓについて、
｜Ｄ（ｘ，ｙ，ｓ）−Ｄ(2e)（ｘ，ｙ，ｓ）｜＞Ｔ
すなわち、中央ピクセル位置でのＤ（ｘ，ｙ，ｓ）の値は、そのピクセル近傍位置のいずれかのＤ（ｘ，ｙ，ｓ）のすべての他の値より少なくともＴだけ大きいまたは小さいものでなければならない。しきい値Ｔの値は、識別できるキーポイントの個数を決定する。
【００９４】
Ｔが大きい時には、最も強いピーク大きさ値Ｄ（ｘ，ｙ，ｓ）を有する最も強いキーポイント位置だけが識別される。Ｔの値を減らすにつれて、より弱いピーク大きさの追加キーポイントを識別することができる。したがって、Ｔの値は、キーポイントの所望の個数および識別されるキーポイントの結果の強さを制御するのに使用することができる。
【００９５】
本願の一実施形態で、Ｔの値は、イメージの期待されるタイプ、キーポイントの所望の個数、およびキーポイントの相対的な強さに基づいて事前に予め決定される定数値である。
【００９６】
本願の他の１つの実施形態で、Ｔの値は、上記で示したように最小キーポイント強さを決定する固定された定数部分と、当該の現在のピクセル位置の周囲の局所領域内のＤ（ｘ，ｙ，ｓ）大きさの平均変動に基づく動的に可変な部分と、の合計からなる。Ｔの動的な調整は、他のより静かなイメージ区域に対して騒がしいイメージ区域内で識別されるキーポイントの個数を制御するのに使用することができる。
【００９７】
本願の第３の実施形態で、対向する対のピクセルのＤ（ｘ，ｙ，ｓ）値と（２ｅ）での中央Ｄ（ｘ，ｙ，ｓ）値との間の大きさの差が、キーポイント強さの尺度を提供するために、ピクセル対にまたがって累算され、正規化される。キーポイントの強さは、その後、より弱くより不安定なキーポイントを除去し、その強さに従ってキーポイントをソートするのに使用することができる。
【００９８】
図１１を継続して参照すると、（２ｅ）での中央Ｄ（ｘ，ｙ，ｓ）値が、対向する近傍位置（２ｄ）および（２ｆ）に関してピーク値になるためのすべての必要条件を満足してはいない場合に、やはり、（２ｅ）をキーポイント位置にすることができないと結論することができ、このプロセスは、次のピクセル位置に移ることができる。
【００９９】
そうではなく、中央位置（２ｅ）が、まだキーポイント位置であり得る場合に、この方法は、図１１の方向２に沿った（２ｅ）の両側のピクセル位置（２ａ）および（２ｉ）の次の対向する対のＤ（ｘ，ｙ，ｓ）の値を取り出す。この方法は、中央位置（２ｅ）がまだキーポイント位置として識別され得るかどうかを判定するために、上の分析を繰り返す。この対でのピクセル比較テストは、図１１に示された残りのピクセル対方向３および４について、中央位置（２ｅ）の周囲の円で継続される。
【０１００】
この方法は、候補キーポイント位置として中央位置（２ｅ）を識別することに失敗するピクセル対が最初に出現した時に終了するように設計される。検索は、しばしば、追加テストにより長い時間を費やすことなく、これらの対でのピクセルテストのうちの２〜３回のみの後に、すばやく終了する。しかし、この実施形態では、ピクセル位置は、すべての可能な対でのテストおよびすべての他の追加のルールがすべて完全に満足された後に限って、安定したキーポイント位置として識別される。
【０１０１】
もう１つの実施形態では、すべての可能な対でのテストを行う必要はないものとすることができる。たとえば、計算の回数を減らすために、対でのテストの一部を除去することができる（たとえば、図１２の遠い角１ａ、１ｃ、１ｇ、１ｉから）。１ピクセルだけ離れた近傍のみを使用することによって、これは、テストの回数をこのケースで９回から５回に減らす（スケールの間で）。したがって、この実施形態では、すべての可能な対でのテストが使用されるわけではない。
【０１０２】
上で述べた追加ルールの例を、以降の段落で展開する。さらに、そのような追加ルールは、たとえば１ピクセルを超えて離れたさらなる対向するピクセル対を調べ、または中央ピクセルの両側の両方が同一の符号を有するかどうかをチェックすることによって、現在の同一スケールのケースにも適用可能である。たとえば、２ａの左に１ピクセルおよび２ｉの右に１ピクセルは、図１１の１と２との間の新しい方向での新しいテストをもたらすなどである。
【０１０３】
現在のスケール平面のテストにおいて、上で概要を示した図１１の方向１〜４に沿った４つの対でのピクセルテストを完了したならば、この方法は、中央ピクセル位置（２ｅ）をそのスケールに関してキーポイント位置として識別できるかどうかのチェックに進む。
【０１０４】
９つの追加の対向する対でのテストを、図１２に示された方向１〜９に沿って適用する。各対でのピクセルテストは、本質的に、キーポイントの強さのしきい値Ｔを含めて、上で説明したものと同一である。しかし、すべてのピクセル位置が同一の現在のスケールにある、４つの対でのテストの前のケースとは異なって、今回は、対向するピクセル位置が、必ず異なるスケールから選択され、一方は現在のスケールより小さいスケール、他方はより大きいスケールから選択される。これは、中央位置（２ｅ）が実際にすべての可能な方向でＤ（ｘ，ｙ，ｓ）の真のスケール空間ピークであることを保証するために行われる。
【０１０５】
やはり、この方法は、前述の対でのピクセルテストのいずれかの最初の失敗で終了するようにセットされる。
【０１０６】
本願の他の実施形態では、追加の対でのルールを追加して、識別できる結果のキーポイントに対するさらなる制約を設けることができる。たとえば、Ｄ（ｘ，ｙ，ｓ）の符号一貫性に関する追加の制約、または、１つ小さいスケールおよび１つ大きい平面でのさらに離れた対向するピクセルの対を追加して、より多くの角度での追加の方向テストを実現することによるものなどである。
【０１０７】
図１３Ａ〜図１３Ｅに、本発明の実施形態に従って実行されるキーポイント識別手順の結果を示す。より具体的には、入力イメージが、図１３Ａに示されている。図１３Ｂは、水平フィルタによって生成された出力であり、図１３Ｃは、垂直フィルタによって生成された出力であり、図１３Ｄは、対角フィルタによって生成された出力であり、このすべてが同一の特定のスケールである。最後に、図１３Ｅは、３つすべてのフィルタを組み合わせた時の出力を示す。
【０１０８】
図１３Ａの入力イメージは、グレイスケールイメージに変換されたオリジナルイメージとすることができる。次に、異なるサイズのフィルタのセットをグレイスケールイメージに適用して、図９に示されたスケール空間ピラミッド層を作成する。ある特定のスケールでの水平フィルタ、垂直フィルタ、および対角フィルタの通常の出力を、それぞれ図１３Ｂ、図１３Ｃ、および図１３Ｄに示す。この３つのフィルタ出力を一緒に組み合わせて、少なくとも３つの連続するスケールで関数Ｄ（ｘ，ｙ，ｓ）を形成する。最後に、３つのスケールのうちの１つすなわち現在のスケールの出力を、図１３Ｅに示す。Ｄ（ｘ，ｙ，ｓ）がそのすべての近傍に対してスケール空間内で極値を達成するピクセル位置が、現在のスケール空間ピラミッド層の安定したキーポイント位置として識別される。
【０１０９】
追加のキーポイントをより高いピラミッド層から抽出することができる。
【０１１０】
図１４に、より高いピラミッド層内で追加のキーポイント（円によって示される）を識別するプロセスを示す。参照のために、図１５に、各ピラミッド層でフィルタサイズを２倍にすることに起因するイメージサイズの対応する縮小を考慮に入れた後の「同等の」ＤｏＧイメージピラミッドを示す。図１５が、参照のみのために提供され、提案される方法実施態様の一部と混同されてはならないことに留意されたい。
【０１１１】
本願の提案される方法は、ＳＩＦＴなどの既存の方法のどれよりも計算がかなり高速でありながら、イメージ内の安定したキーポイントの識別において同様に効果的であると認められる。
【０１１２】
ガウシアンフィルタは、非常に高速に計算でき、既存の方法に対してはるかに少数の計算を必要とする、はるかにより単純なハールライク（Ｈａａｒ−ｌｉｋｅ）特徴突出インジケータ長方形フィルタに置換される。既存の方式の多くとは異なって、ガウシアンフィルタリングは、現在説明されている複数スケール分析で直接には使用されない。ガウシアンフィルタリングは、その優れた平滑化特性に起因して、空間スケール分析に望ましいと判定された。しかし、実際には、ガウシアン形状は、離散値にディジタル化することと、さらに、切り捨てなければ無限の尾をある点を超えて切り捨てることとによって近似されなければならないという点で、理想的ではない。さらに、正確なガウシアンフィルタリングを用いても、エイリアシングアーティファクトが、イメージをダウンサンプリングする時に導入され得る。非常に重要視されている技法のいくつかは、ガウシアン形状のさらなる近似の下であっても優れた結果を実証した（たとえば、ＳＩＦＴ法の一部としてのディファレンス・オブ・ガウシアン（ＤｏＧ）イメージピラミッドとしてのラプラシアン・オブ・ガウシアン（ＬｏＧ）イメージピラミッドのＤ．Ｌｏｗｅの近似）。
【０１１３】
本システムおよび方法は、再帰的フィルタリングを使用せずに、オリジナルイメージに直接に異なる長方形形状サイズを適用することによって、イメージピラミッド全体を便利に効率的に計算することができる。したがって、本システムおよび方法は、反復的にイメージをスケールダウンするのではなく、フィルタサイズをスケールアップすることによって複数スケール分析を実行することができる。
【０１１４】
本願の実施形態のシステムおよび方法は、非常に高速のレートを達成するだけではなく、その速度は、すべてのフィルタサイズについて正確に同一である。長方形フィルタ形状を用いると、これを達成するための面積合計積分の特性が活用される。まず、所定の左下のイメージ角に対するオリジナルイメージの各ピクセルの面の積合計を計算する。これは、行および列を記憶しながら前の面積の合計に現在のピクセル値を再帰的に加算することによって、１ピクセルあたり約１回の加算で効率的に行うことができる。面積合計積分をイメージ全体について計算し、メモリに格納したならば、任意の長方形フィルタ形状の下の面積を、任意の長方形フィルタサイズについて２回の加算だけを使用して計算でき、性能の改善につながる。
【０１１５】
たとえばヘッセ行列ベースの技法と同様にガウシアン二次導関数を使用するのではなく、本願の実施形態では、他の点では複数スケール分析として知られる、２つの空間イメージ次元空間内ならびにさまざまなスケール内で局所化できる独特なキーポイントを見つけることを試みる。この方法は、そのようなキーポイントの位置を識別するのに単純な長方形フィルタ形状を使用する。本願の実施形態では、イメージ内の最も特徴的なキーポイントのセットを探すので、フィルタの正確な形状は、決定的ではない。すなわち、鋭いビルディングの角または目の角などの明確に局所化されたイメージキーポイントは、より単純なフィルタを用いて同様によく見つけられる可能性が高い。本願の実施形態では、垂直方向、水平方向、および対角線方向でイメージ特徴を取り込むように設計されたフィルタ形状を利用する。特定のフィルタ形状は、ガウシアン形状の長方形近似と解釈することができる。入力イメージの品質および予想される取り込みデバイスに応じて、これらのフィルタは、さらに、ノイズおよびサンプリングアーティファクトを除去するのを助けるために分離「ガードバンド」を含むことができる。基本的なフィルタ形状は、複数スケールイメージ分析をもたらすためにスケールアップされる。しかし、フィルタ形状の実際のスケーリングは、必要ではない。長方形のフィルタ形状に起因して、スケーリングを、前もって新しい角の座標を記録し、その後、新しい異なるサイズのフィルタ結果を得るためにイメージ積分を使用することによって、効率的に行うことができる。
【０１１６】
本システムおよび方法は、各ピラミッドレベルを、上記で概要を示した面積合計を使用して入力イメージから直接に計算できるので、並列な実施態様に特に適する。各ピラミッドレベルの計算は、他のピラミッドレベルと完全に独立であり、フィルタサイズに関わりなく正確に同一の時間を要する。
【０１１７】
本願の実施形態では、イメージ内の独特なキーポイントの位置を判定するのにルールベースの方法を使用する。数百万個のピクセルを含む通常のイメージは、数百個から数千個の候補キーポイントを生じる場合がある。ほとんどのイメージピクセルはキーポイントではないので、任意の所定のイメージピクセルで費やされる時間の最小化が探される。本システムおよび方法は、現在のピクセルを強いキーポイント候補にすることができるかどうかをすばやく判定するために、さまざまなスケールおよび方位で当該の現在のピクセルの両側の近傍ピクセルの対などの間で一連の連続するテストを実行する。これらのテストは、尤度順によって編成される。各連続するテストで、現在のピクセルとその隣接物との間の関係が、要求される条件を満足しない場合には、この方法は、キーポイントとしての現在の位置を除外し、次のピクセルに移る。したがって、全体的な時間が最小化されると同時に、各最終的なキーポイントは、有効なキーポイントであるためのすべての条件を満足する。本システムおよび方法は、複数のそのようなルールを使用して、ありそうなキーポイント候補を判定する。
【０１１８】
本願の実施形態では、結果の滑らかさを改善し、フィルタ境界に沿った潜在的不連続性の影響を減らすために、各後続フィルタ位置のサンプリングのオーバーラップという概念も導入される。長方形フィルタは、スケーリングの後に一定のままになるように正規化される。さらに、フィルタサイズが、各より大きいスケールの分析のために増やされる時に、サンプリング位置をも対応して増やして、キーポイントの識別に関するより高いピラミッド層の有効解像度を便利に下げることができる。
【０１１９】
キーポイントの候補それぞれのキーポイントの強さの尺度も導入される。結果のキーポイントを、イメージ内の最良の最も特徴的なキーポイントを識別し、イメージの劣化したノイズのある版で見つかる可能性が高くはないすべての他の弱いキーポイントを破棄するために、強さの順でソートすることができる。通常、最も強いキーポイントのうちの最上位の数百個が、イメージ照合のために最も有用である。したがって、性能の改善を、最も強いキーポイントの小さいサブセットに集中することと、照合結果が結論に達しない場合に限ってより弱いキーポイントを追加することとによって得ることができる。代替案では、キーポイントの所望の個数および強さを前もって決定することができ、キーポイント識別プロセスを、十分な個数の適切なキーポイントが識別されるや否や停止することができ、これによって、さらなるキーポイントを識別するために時間を浪費しなくなる。キーポイントの強さは、各テストの個々の寄与を使用して、テストのシーケンス中にオンザフライで計算される。キーポイントの強さの尺度は、さらなる下流処理でアンカキーポイントを選択するためなどであるがこれには限定されないある種の特定用途向け処理に特に有用である。
【符号の説明】
【０１２０】
１００ コンピュータネットワーク、１０２，１０６ ワイヤ、１０４ ワイヤジャンクション、１０８，１０９ コンピュータ、１１０ カラープリンタ、１１２ カラー以外のプリンタ、１２０，１２２ カラーレーザプリンタ、１２４ カラー以外のレーザプリンタ、１３０ スキャナ、１４０ ファクシミリ機、１５０ 写真複写機、１５２ カラー写真複写機、１５４ 組合せカラープリンタ／スキャナ／ファクシミリ機、１６０ パーソナルコンピュータおよび／または独立型コンピュータ端末、１６４ 独立型ハードドライブデータストレージ媒体、１７０ 無線ネットワーク送受信器、１７２，１７４ ラップトップコンピュータ、１８０ ネットワーク、１９０ 周辺データ取り込みデバイス、１９１ ディジタルスチルカメラ、１９２ ディジタルビデオカメラ、１９３ セル電話機、１９４ スキャナ、１９５ 携帯情報端末、１９６ 文書インデクシングシステム。
【技術分野】
【０００１】
本発明は、局所化されたスケール空間特性を使用してピクチャイメージ内で安定したキーポイントを検出するシステムおよび方法に関する。
【背景技術】
【０００２】
イメージ（画像）内のキーポイントの検出の技術の一例として、非特許文献１及び非特許文献２に記載されたＳＩＦＴ（Ｓｃａｌａｂｌｅ Ｉｎｖａｒｉａｎｔ Ｆｅａｔｕｒｅ Ｔｒａｎｓｆｏｒｍ）がある。処理速度を改善するために、ＳＩＦＴでは、ディファレンス・オブ・ガウシアン（Ｄｉｆｆｅｒｅｎｃｅ ｏｆ Ｇａｕｓｓｉａｎ，ＤｏＧ，ガウス関数の差分）のイメージピラミッドにより、ラプラシアン・オブ・ガウシアン（Ｌａｐｌａｃｉａｎ ｏｆ Ｇａｕｓｓｉａｎ，ＬｏＧ）をさらに近似する。入力イメージは、連続的にガウシアンカーネルによって平滑化され、ダウンサンプリングされる。ディファレンス・オブ・ガウシアンは、２つの連続する平滑化されたイメージの差をとることで取得される。したがって、すべてのＤｏＧレベルは、平滑化およびサブサンプリングの組み合わせにより構成される。空間次元およびスケールのイメージピラミッド表現における局所的な３Ｄ（３次元）の最大値は、キーポイントの位置およびスケールを決定する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】ロウエ（D. G. Lowe），「Distinctive Image Features from Scale-Invariant Keypoints」，International Journal of Computer Vision，２００４年，第６０巻（Vol. 60），第２号（No. 2），ｐ．９１−１１０
【非特許文献２】ブラウン（Matthew Brown）およびロウエ（D.G. Lowe），「Invariant Features from Interest Point Groups」，British Machine Vision Conference，BMVC 2002，カーディフ（Cardiff），ウェールズ（Wales），２００２年９月， ｐ．６５６−６６５
【発明の概要】
【発明が解決しようとする課題】
【０００４】
キーポイントを検出する技術において特別な問題は、ノイズに対する頑健性（ｒｏｂｕｓｔｎｅｓｓ）の程度と、回転、スケール、および、キーポイントの検出の実行が要求されるときに生じる他の一般的なイメージ劣化による変化の程度である。
【０００５】
従来技術では、かなり多くの計算量を必要とし、これは全体の性能を制限する。
【課題を解決するための手段】
【０００６】
本発明の一態様の方法は、入力イメージのインテグラルイメージを計算するステップと、複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成するステップであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、ステップと、スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせるステップと、前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別するステップと、前記安定したキーポイント位置をメモリストレージに格納するステップと、を含むことを特徴とする、局所化されたスケール空間特性を使用してピクチャイメージ内の安定したキーポイントを見つける方法である。前記フィルタは、異なるサイズの長方形フィルタであってよい。前記構成するステップは、前記フィルタサイズに関わりなく所定の回数の演算を含んでいてよい。
【０００７】
また、本発明の１つの態様のシステムは、電子データ処理システムであって、前記電子データ処理システムのメモリに格納されたソフトウェア動作を処理できる少なくとも１つのプロセッサを含み、動作の前記処理が、入力イメージのインテグラルイメージを計算することと、複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成することであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、構成することと、スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせることと、前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別することと、前記安定したキーポイント位置をメモリストレージに格納することと、を含むことを特徴とする、電子データ処理システムである。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施形態の概念を実施できる環境を示す図である。
【図２Ａ】安定したキーポイント識別動作の応用を表し、スクリーンに表示されたクエリカメライメージを示す図である。
【図２Ｂ】安定したキーポイント識別動作の応用を表し、スクリーンに表示されたクエリカメライメージにおける識別されたキーポイントの位置を示す図である。
【図２Ｃ】安定したキーポイント識別動作の応用を示し、カメライメージの印刷された版（バージョン）を表す図である。
【図２Ｄ】安定したキーポイント識別動作の応用を示し、カメライメージの印刷された版において定義されたキーポイントを示す図である。
【図２Ｅ】安定したキーポイント動作の応用のさらなる例を示し、ターゲットイメージを示す図である。
【図２Ｆ】安定したキーポイント動作の応用のさらなる例を示し、ターゲットイメージのキーポイントを示す図である。
【図３】インテグラルイメージ（ｉｎｔｅｇｒａｌ ｉｍａｇｅ）を計算する効率的な方法を示す図である。
【図４Ａ】３つの基本的なフィルタタイプのうちの水平フィルタを示す図である。
【図４Ｂ】３つの基本的なフィルタタイプのうちの垂直フィルタを示す図である。
【図４Ｃ】３つの基本的なフィルタタイプのうちの対角フィルタを示す図である。
【図５Ａ】単位分散ガウス関数を示す図である。
【図５Ｂ】水平軸Ｘに関する単位分散ガウス関数の二次偏導関数を示す図である。
【図５Ｃ】垂直軸Ｙに関する単位分散ガウス関数の二次偏導関数を示す図である。
【図５Ｄ】ＸとＹの両方のカスケードされた一次偏導関数に関する、対角線方向に関する単位分散ガウス関数二次偏導関数を示す図である。
【図６Ａ】図４Ａのフィルタタイプの単純化された版を示す図である。
【図６Ｂ】図４Ｂのフィルタタイプの単純化された版を示す図である。
【図６Ｃ】図４Ｃのフィルタタイプの単純化された版を示す図である。
【図７Ａ】スケール空間ピラミッドを作成する、ＳＩＦＴのＤｏＧ法を示す図である。
【図７Ｂ】スケール空間ピラミッドを作成する、ＳＩＦＴのＤｏＧ法を示す図である。
【図８Ａ】水平フィルタのスケール空間ピラミッドを構成する方法を示す図である。
【図８Ｂ】垂直フィルタのスケール空間ピラミッドを構成する方法を示す図である。
【図８Ｃ】対角フィルタのスケール空間ピラミッドを構成する方法を示す図である。
【図９】スケール空間ピラミッド層を作成するのに使用されるフィルタのセットを示す図である。
【図１０】スケール空間領域でＤ（ｘ，ｙ，ｓ）の極値点を検索する方法を示す図である。
【図１１】現在の層スケールでの対でのピクセルのテストを示す図である。
【図１２】３つの連続する層スケールの間の候補ピークに関する対でのピクセルテスティングを示す図である。
【図１３Ａ】スケール空間手法を使用するキーポイント識別プロセスを示し、入力イメージを示す図である。
【図１３Ｂ】スケール空間手法を使用するキーポイント識別プロセスを示し、水平フィルタの出力を示す図である。
【図１３Ｃ】スケール空間手法を使用するキーポイント識別プロセスを示し、垂直フィルタの出力を示す図である。
【図１３Ｄ】スケール空間手法を使用するキーポイント識別プロセスを示し、対角フィルタの出力を示す図である。
【図１３Ｅ】スケール空間手法を使用するキーポイント識別プロセスを示し、水平フィルタ、垂直フィルタ、及び対角フィルタの組み合わせの出力を示す図である。
【図１４】スケール空間ピラミッド層から安定したキーポイントの位置を識別するプロセスを示す図である。
【図１５】図の最下部に入力イメージがある、スケール空間イメージピラミッドを示す図である。
【発明を実施するための形態】
【０００９】
本明細書で説明されるシステムおよび方法は、図１に示されたコンピュータネットワークのパラメータ内で働くことができる。コンピュータネットワーク１００は、一連のワイヤ１０２からなるものとすることができ、ワイヤ１０２の多くは、分岐するかワイヤジャンクション１０４で第３のワイヤ１０６と接続されてもよく、独立型周辺デバイスに接続されるか、コンピュータ１０８，１０９などの他のデバイスに接続するために周辺機器を通過してもよく、ここで、コンピュータは、周辺デバイスと考えることができる。ネットワークは、カラープリンタ１１０またはカラー以外のプリンタ１１２、ならびに少なくともカラーレーザプリンタ１２０，１２２またはカラー以外のレーザプリンタ１２４を組み込んでもよい。ネットワークは、スキャナ１３０、またはファクシミリ機１４０、写真複写機１５０、カラー写真複写機１５２、あるいは組合せカラープリンタ／スキャナ／ファクシミリ機１５４を組み込むこともできる。ネットワークは、パーソナルコンピュータおよび／または独立型コンピュータ端末１６０、あるいは独立型ハードドライブデータストレージ媒体１６４を含むこともできる。ネットワークは、無線ネットワーク送受信器１７０を含み、少なくとも１つのラップトップコンピュータ１７２または複数のラップトップコンピュータ１７４とインターフェースすることもできる。ネットワークは、インターネット、イントラネット、または他の通信ネットワークを含むがこれらに限定されない任意の形のネットワーク１８０に相互接続されてもよい。別の形のネットワークとのインターフェースの使用を介して、本システムおよび方法は、ディジタルスチルカメラ１９１、ディジタルビデオカメラ１９２、セル電話機１９３、スキャナ１９４、携帯情報端末１９５、または文書インデクシングシステム１９６を含むがこれらに限定はされない複数の周辺データ取り込みデバイス１９０とインターフェースすることができる。本概念を、単一のデバイスを有するネットワークから数千個以上の接続されたデバイスを含むネットワークにいたる、上記のコンポーネントのさまざまな組合せを有するネットワーク内で実施できることを理解されたい。さらに、上のコンポーネントのうちのさまざまなコンポーネントは、説明される概念を実施するのに有用である可能性がある複数の既知の構成のいずれかに配置されたメモリストレージエリアを有することができる。このストレージエリアは、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、フラッシュメモリ、または本発明の実施形態の概念を組み込んだソフトウェアを保持できる他のメモリタイプとすることができる。他のメモリストレージエリアを、複数のデータベースフォーマットのいずれかのさまざまなディジタルイメージを保持するように構成してもよい。
【００１０】
コンピュータなどであるがこれに限定はされない図１のコンポーネントのうちのさらなるさまざまなコンポーネントは、そのコンポーネントにロードされるか他の形でそのコンポーネントによってアクセス可能なソフトウェアからの命令を処理するプロセッサを含む。プロセッサを有するコンポーネントのうちのさまざまなコンポーネントが、複数のプロセッサを有してもよく、これによって、命令の処理を複数のプロセッサの間で分割できることを理解されたい。代替案では、単一のプロセッサが、命令を分割するように動作でき、これによって、処理をマルチスレッド環境で行うことができる。
【００１１】
図２Ａ〜図２Ｆに、本発明の実施形態のシステムおよび方法を使用する安定したキーポイント識別の成功した適用の例を示す。図２Ａに、スクリーンに表示されたカメライメージを示すが、このカメライメージは、多数のイメージのデータベース内にあるものとすることができる、図２Ｅのイメージなどのターゲットイメージを識別する試みに使用される劣化したクエリイメージである。同様に、図２Ｃのイメージは、やはり図２Ｅに示されたターゲットイメージから劣化した（たとえば、イメージの一部の上に妨害を有する）印刷された版のクエリカメライメージのもう１つの例である。図２Ａ、図２Ｃ、および図２Ｅのイメージに対して本発明の実施形態のシステムおよび方法を動作させて得られるキーポイント位置を、それぞれ図２Ｂ、図２Ｄ、および図２Ｆに示す。３つのスケールで得られたキーポイント位置が示され、最小スケール位置は「ｘ」でマークされ、中間スケール位置は「□」でマークされ、最大スケール位置は「ｏ」でマークされている。最小スケール位置は、最小サイズのフィルタの使用によって識別され、中間スケール位置は、最小サイズのフィルタのスケールアップ版（スケールをより大きくした版）である中間サイズのフィルタの使用によって識別され、最大スケール位置は、中間サイズのフィルタのスケールアップ版である最大サイズのフィルタの使用によって識別される。したがって、図２Ａ〜図２Ｆは、以下でより詳細に開示する本発明の実施形態のシステムおよび方法の動作の結果を示す。
【００１２】
イメージの間のイメージ品質、解像度、および変化する照明のかなりの差にもかかわらず、図２Ｅのターゲットイメージに対応する図２Ｆのキーポイントの多くは、それぞれ図２Ａおよび図２Ｃの劣化したイメージに対応する図２Ｂおよび図２Ｄにも見られる。
【００１３】
本発明の実施形態のシステムおよび方法の概要は、次の概念を含む。
【００１４】
（ａ）フィルタサイズに関わりなく少数の加算だけで入力イメージ上の任意のサイズの長方形フィルタ形状の出力をすばやく計算できるようにするために入力イメージのインテグラルイメージを計算する。
【００１５】
（ｂ）複数のスケールで入力イメージのスケール空間ピラミッド層表現を構成する。各スケールでは、特定のフィルタのセットを入力イメージに適用して、入力イメージの少なくとも一部の近似を作る。一実施形態で、近似は、ラプラシアン・オブ・ガウシアン（ＬｏＧ）関数の形とすることができる。各連続するフィルタは、前のフィルタのスケールアップ版である。フィルタの出力を一緒に組み合わせて、スケールおよび空間の単一の関数Ｄ（ｘ，ｙ，ｓ）を形成する。
【００１６】
（ｃ）安定したキーポイント位置は、各スケールで、関数Ｄ（ｘ，ｙ，ｓ）がスケール空間近傍内で局所的なピーク値（最大値または最小値のいずれか）を達成するピクセル位置として識別される。
【００１７】
上のステップを採用することによって、ＳＩＦＴを含む既存の方法より計算において高速であり、なおかつイメージ内の安定したキーポイントの識別において同等に効率的と思われる手順がもたらされる。
【００１８】
本発明の実施形態は、ＳＩＦＴによって提案される入力イメージの事前の補間を主張しない。
【００１９】
本発明の実施形態のシステムおよび方法の詳細を、以下で提供する。
【００２０】
Ｉ．１ インテグラルイメージ
インテグラルイメージを計算する効率的な方法を図３に示す。処理される入力イメージを、図３の上側部分３００に示し、対応するインテグラルイメージの出力を、図３の下側部分３０１に示す。
【００２１】
現在のピクセル３０２でのインテグラルイメージの値は、３００の左上角の原点３０５を含み、右下角としての現在のピクセル位置３０２までで現在のピクセル位置３０２を含む長方形区域内のすべてのピクセル値の合計として定義される。効率の一態様は、前に計算された結果を可能な範囲まで活用することである。入力イメージは、一般に、ラスタスキャン順で一時に１ラインずつ処理され、１ライン内では、たとえば左から右へ一時に１ピクセルずつ処理される。
【００２２】
任意の現在のピクセル位置３０２でのインテグラルイメージの値は、次の２つの量すなわち、（１）前のサブ区域３０４（現在のピクセル位置の正確に１つ前のラインのピクセル位置のインテグラルイメージ値として既に計算済み）と、（２）現在のライン上の最初のピクセルから始まり現在のピクセル値３０２までで現在のピクセル値３０２を含む、現在のサブライン３０３上のピクセル値の和と、を一緒に合計することによって構成することができる。
【００２３】
インテグラルイメージは、長方形区域のピクセル値の合計に基づく。この方法は、ここで、入力イメージが共通のラスタスキャン順で得られると仮定する。しかし、行および列の役割は、イメージが通常のラスタスキャン行順ではなく列順で得られる場合に、簡単に逆転することができる。
【００２４】
インテグラルイメージを計算する効率的な方法は、ラインアレイ３０６および３０７を使用して、正確に１イメージライン前のインテグラルイメージの結果を保持することによる。ラインアレイ内の要素の総数は、入力イメージの単一ライン内のピクセル数と正確に同一である。このアレイは、一次ストレージ用の環状バッファとして使用されている。
【００２５】
ラインの始めから現在のピクセル位置３０２までのラインアレイピクセル値３０６は、前に処理されたインテグラルイメージ値および現在のライン上のピクセルの更新されたインテグラルイメージ値を含む。これらの値は、次のイメージラインの後続処理のために格納されている。それと同時に、現在のピクセル位置３０２から順方向にラインアレイの終りまでのラインアレイピクセル値３０７は、まだ更新されていない、前のライン上の前のインテグラルイメージ値を含む。現在のピクセル位置３０２のそれぞれで、前のラインのインテグラルイメージ値が、現在のアレイピクセル位置３０２から読み取られ、現在のインテグラルイメージ値を計算するために適用され、その後、更新された結果が、ラインアレイ３０７に書き戻されて、この位置の以前の値を上書きする。次に、このプロセスは、現在のライン上の次のピクセルに進む。このリード（読出し）・モディファイ（更新）・ライト（書込み）サイクルは、ラインの終りに達するまで、ピクセル位置ごとに継続する。
【００２６】
各ピクセル位置で、現在のピクセル値３０２が、まず、図３の最下部に示された加算器３０９を使用して、前の行の和３０８に加算される。行の和は、現在の行の始めから現在のピクセル位置３０２までのピクセル値のランニングサム（ｒｕｎｎｉｎｇ ｓｕｍ）を累算するのに使用される内部レジスタである。行和レジスタは、各ラインの始めに０にリセットされる。加算器３０９の出力は、行和レジスタに書き戻されて、各ピクセル位置でのその値を更新する。更新された行和値は、現在のサブライン３０３と現在のピクセル値３０２との合計と同等である。
【００２７】
更新された行和値３０８は、次に、第２の加算器３１０を使用して、正確に１ライン戻った前のラインのインテグラルイメージ値３０７に加算される。というのは、その内容が、まだ現在のピクセル位置３０２によって更新されていないからである。加算器３１０の出力は、結果として得られる現在のピクセル位置３０２でのインテグラルイメージ値である。この結果は、次のラインの後続処理のためにその値を保持するために、現在のピクセル位置３０２でのラインアレイに書き戻される。したがって、各ラインアレイ要素は、一時に１ピクセルずつ単一のリード・モディファイ・ライトサイクルを受け、これによって、後に続くラインでの連続した再利用のためにインテグラルイメージ値を一時的に保持するためにラインアレイに連続的な１ラインランニングバッファウィンドウを同時に提供する。
【００２８】
上で提案した方法を使用すると、インテグラルイメージ全体の計算が、１ピクセルあたり２つの加算だけを必要とする。動作全体を、もちろん、並列に動作する２つの別々の加算器を使用してパイプライン化して、インテグラルイメージ計算を１ピクセルあたり単一の二重加算に減らすことができる。したがって、インテグラルイメージは、計算が速く、所定のイメージについて１回だけ計算すればよい。インテグラルイメージを計算した後に、その結果を繰り返して効率的に使用して、以下で説明する形で、さまざまな長方形フィルタ形状の計算を劇的に加速することができる。カスケードされたフィルタリングの伝統的な手法とは異なって、インテグラルイメージは、区域サイズに関わりなく固定された一定の時間で任意の長方形フィルタ区域の出力を計算する能力を提供する。
【００２９】
Ｉ．２ 個々のスケール空間層の構成
スケール空間表現を作成する伝統的な手法は、イメージピラミッドによるものである。既存の方法の短所は、イメージピラミッドが、通常はガウシアンフィルタを繰り返して適用することと、その後、より大きいスケールに対応するより上のピラミッドレベルを入手するために入力イメージをダウンサンプリングすることとによって構成されることである。既存の方法によるイメージピラミッド構成プロセスを、次のように示すことができる。入力イメージを、まず補間して、たとえばＳＩＦＴ法と同様に、各方向でイメージ寸法を２倍にしてよい。次に、０平均および分散σのガウシアンフィルタを、サイズを増やされたイメージに適用して、第１の最小スケールのピラミッド層である出力イメージを作る。次に、結果の第１イメージ層を、２倍だけダウンサンプリングし、０平均および（√２）σの同等の分散の第２ガウシアンフィルタを適用して、第２の１つ大きいスケールの第２イメージピラミッド層を作る。各後続層は、前のピラミッド層出力をダウンサンプリングし、徐々により大きくなるガウシアンフィルタを結果のイメージに効果的に適用して、次のピラミッド層を作ることによって作られる。したがって、イメージピラミッドを作るプロセス全体は、順次的性質を有し、各後続空間スケールピラミッド層は、より小さいスケールの前のすべてのピラミッド層に完全に依存し、したがって、すべての他の層と同時に計算することはできない。さらに、各方向でサイズＮピクセルの一般的な分離不能正方形ガウシアンフィルタは、計算にオーダーＯ（Ｎ2）の乗算および加算を必要とし、Ｏは、演算の回数である。演算の回数は、フィルタ面積サイズに比例し、したがって、各後続層は、増加したフィルタサイズに起因して前の層に対して相対的に計算により長い時間を要し、やはり、後続する層の結果を後のステージでキーポイント抽出に同時に使用可能にするために、後続する層の結果をメモリに格納することが必要になる。フィルタ動作の数は、フィルタが分離可能である場合にはＯ（Ｎ）回の乗算およびＯ（２Ｎ）回程度の加算に減らすことができるが、それでも、複数のスケールについて計算するのにかなりの時間を要する。
【００３０】
さらに、再帰的にフィルタリングし、ダウンサンプリングする必要のゆえに、このプロセス全体が、直列の性質を有し、より高い次数のレベルの計算を、すべてのピラミッドレベルについて同時に得ることはできない。しかし、キーポイント識別プロセスは、ある個数のレベル（通常、少なくとも３つから４つ）の同時使用可能性に依存する。したがって、中間ピラミッドレベルを、後の使用のためにメモリ内に格納しなければならない。
【００３１】
既存の手法のように複数スケールイメージピラミッドを作成するために入力イメージを繰り返してフィルタリングし、ダウンサンプリングするのではなく、本システムおよび方法は、水平方向、垂直方向、および対角線方向での入力イメージの局所化可能な特性の直接識別に基づく異なる手法を使用する。さまざまなフィルタ出力を一緒に組み合わせて、入力イメージ内の局所化可能な「しみ様（blob-like）」の特徴および「接合点様（junction-like）」の特徴を識別する。
【００３２】
さらに、以前の方法のように、予めフィルタリングされダウンサンプリングされた版の入力イメージの（徐々に小さくなる）出力にガウシアンフィルタを反復的に適用するのではなく、本発明の実施形態のシステムおよび方法は、フィルタをアップサンプリングし、より大きいフィルタ版をオリジナルの入力イメージに直接に適用する。したがって、より大きいスケールのそれぞれで、入力イメージは一定のままにしながら、以前のフィルタ形状を、たとえばサイズにおいて２倍にすることができる。
【００３３】
一見すると、この見た目には良好なスケーリング透視の変化は反直観的に見える。しかし、本システムおよび方法において、固定されたフィルタおよび順次小さくなるイメージサイズを固定されたイメージおよび順次大きくなるフィルタサイズに置換することが、性能の改善をもたらし得ることがわかった。
【００３４】
この手法の利益は、より大きいフィルタを、既存の方法のように以前のフィルタ出力を使用して反復的にカスケードする必要なしに、オリジナルの入力イメージに直接に適用できることである。さらに、インテグラルイメージおよび特定のフィルタ形状の使用に起因して、任意のサイズのフィルタを処理するのに、正確に同一の長さの時間を要する。したがって、すべてのフィルタを、そのサイズと独立に、正確に同一の速度で計算することができる。さらに、各長方形フィルタ領域は、そのサイズに関わりなく、インテグラルイメージを使用して計算するのに少数の加算だけを必要とする。
【００３５】
その結果、提案されるシステムおよび方法は、既存の伝統的な反復手法に対する相対的な性能改善を入手しながら、なおかつイメージ内の堅牢なスケール不変キーポイントの位置の識別において同等に効果的である。
【００３６】
図４Ａ〜図４Ｃに、本発明の実施形態によるスケール空間ピラミッドの個々の層を構成するのに使用される３つの基本的なフィルタタイプを示す。
【００３７】
各スケールで、３つの別々のフィルタすなわち、（ａ）図４Ａの水平フィルタ、（ｂ）図４Ｂの垂直フィルタ、および（ｃ）図４Ｃの対角フィルタが入力イメージに適用される。「Ｘ」を用いてマークされた各フィルタの中央位置は、その回りにフィルタウィンドウが位置決めされる、入力イメージの現在のピクセル位置である。
【００３８】
各フィルタのサイズは、それに適用されるスケールに比例する。各フィルタが、長方形区域のセットからなることに留意されたい。というのは、その意図が、高速計算のためにインテグラルイメージを適用することであるからである。また、図４Ｂの垂直フィルタが、図４Ａの水平フィルタ形状を９０度回転した版であることに留意されたい。
【００３９】
図４Ａの水平フィルタ形状は、すべてのピクセル値が所定の極性、たとえば＋ｐをとる中央領域（斜めの線のパターンを用いて図示）と、すべてのピクセル値が反対の極性、たとえば−ｍをとる２つの外側領域（水平線のパターンを用いて図示）とからなり、ここで、「ｐ」および「ｍ」は、２つのゼロでない整数値である。
【００４０】
中央領域が正であり、外側領域が負であるか、または、その反対であるかという２つの領域タイプの間の極性割り当ての意味は、一貫性をもって適用される限り、任意である。
【００４１】
図４Ａで白い領域として図示されたオプションの「ガードバンド」は、領域をお互いから分離するために、反対の領域タイプの間の境界に沿って導入される。この「ガードバンド」の目的は、フィルタ安定性を改善し、極性において変動する可能性がある、領域境界に沿ったノイズのあるピクセルを除外することによって、ノイズに対する感度を最小化することである。「ガードバンド」領域の内側のすべてのピクセル値に、０の値が割り当てられる。
【００４２】
したがって、各フィルタピクセルの値は、３つの可能な値｛−ｍ，０，＋ｐ｝のうちの１つをとる。「ｐ」および「ｍ」の値は、一実施形態では整数値であり、相対領域面積サイズに基づいて一定の入力イメージの場合の偏りのないフィルタ出力をもたらすように選択される。たとえば、水平フィルタまたは垂直フィルタの場合に、式
ｐ／ｍ＝ｂ1／（ｃ−ｂ2）
を満足するように「ｐ」および「ｍ」の値の対を選択する。
【００４３】
ｂ1、ｂ2、およびｃのすべてが、整数ピクセル番号値なので、「ｐ」および「ｍ」の対を見つけることが可能である。
【００４４】
各フィルタの形状は、４つのパラメータ値｛ａ，ｂ1，ｂ2，およびｃ｝のセットによってパラメータ化される。これらのパラメータの値は、スケールに比例する。フィルタサイズがスケールアップされると、すべてのパラメータ値が比例して増やされる。ただし、フィルタ形状は比例して正規化されたままに保たれる。また、４つのパラメータ値｛ａ，ｂ1，ｂ2，およびｃ｝が、必ずしも、水平フィルタまたは垂直フィルタについて対角フィルタと同一である必要がないことに留意されたい。
【００４５】
水平フィルタは、水平方向でよく局所化可能な、入力イメージ内の候補の高く狭い「細長い」特徴を検出するように設計される。外側領域に対して相対的により暗いまたはより明るい中央領域などであるがこれに限定はされない特徴極性は、後述するように、フィルタ出力の大きさを使用することによって無視される。フィルタ出力の大きさは、現在のピクセル位置ごとの中央フィルタ領域と外側フィルタ領域との間のコントラスト差に効果的に比例する。
【００４６】
図４Ａの水平フィルタは、一般に、幅２×ｂ1および高さ２×ｃの狭く高い中央領域を有し、ｂ1＜ｃである。同様に、この水平フィルタは、組み合わされた幅２×（ａ−ｂ2）および高さ２×ｃの２つの外側領域をも有する。幅（ｂ2−ｂ1）および高さ２×ｃを有するオプションの狭く高い垂直「ガードバンド」を、中央領域と外側領域との間に挿入してもよい。あるいは、パラメータ値ｂ2＝ｂ1をセットすることによって、「ガードバンド」を完全に除去することが可能である。
【００４７】
図４Ｂの垂直フィルタは、垂直方向でよく局所化可能である入力イメージ内の候補の幅広く短い「細長い」特徴を検出するように設計される。垂直フィルタの形状は、図４Ａの水平フィルタを９０度回転した版である。
【００４８】
図４Ｃの対角フィルタは、対角線方向でよく局所化可能である入力イメージ内の候補の「細長い」特徴を検出するように設計される。対角フィルタの形状は、４つの長方形領域からなり、そのうちの２つは（対角線パターンを用いて図示）、一方の対角線方向に向けられ、他方の２つ（水平線パターンで図示）は、他方の対角線方向に向けられる。すべての領域サイズが、対角フィルタの場合には同一なので、フィルタ応答は、設計によって既に偏りをなくされており、上述の「ｐ」および「ｍ」ではなく＋１または−１の値を、上記で示したように領域タイプに応じてこれらの領域のそれぞれのすべてのピクセル値に割り当てることで十分であることに留意されたい。
【００４９】
対角フィルタが、図４Ｃでその主軸に沿った白い領域として示されたオプションの「ガードバンド」をも含むことに留意されたい。「ガードバンド」領域は、フィルタ安定性およびノイズに対する免疫性を改善するために、対向する領域タイプの境界に沿って導入される。「ガードバンド」領域内のすべてのピクセル値には、０の値が割り当てられる。長方形対角フィルタの一般的なケースについて、「ガードバンド」は、水平軸の回りで２×ｂ2の幅および垂直軸の回りで２×ｂ1の幅を有する。「ガードバンド」の幅は、ｂ1＝ｂ2を選択することによって対称にすることができ、または、ｂ1＝ｂ2＝０を選択することによって完全に除去することができる。「ガードバンド」区域を含まない各領域タイプの総面積は、対角フィルタについて２×（ａ−ｂ1）（ｃ−ｂ2）である。
【００５０】
パラメータ値｛ａ，ｂ1，ｂ2，およびｃ｝の適当な選択を用いると、フィルタの各１つを、それぞれ水平方向、垂直方向、および対角線方向のガウシアンカーネルの二次偏導関数の近似とみなすことができる。より具体的には、図５Ａに、単位分散ガウシアンフィルタ関数を示す。これは、より一般的なケースの分散σではなく正規化された分散１を有することを除いて、最小スケールで図２Ａの入力イメージに適用される平滑化フィルタである。
【００５１】
単位分散ガウス関数の水平、垂直、および対角の二次偏導関数を、それぞれ図５Ｂ、図５Ｃ、および図５Ｄに示す。この文脈での対角二次導関数は、水平一次偏導関数と垂直一次偏導関数との積である。平滑化ガウシアン二次導関数は、各ケースで長方形のトライナリ（すなわち、３つの）フィルタ形状を用いて近似される。
【００５２】
本システムおよび方法は、入力イメージのダウンサンプリングを利用しないので、平滑化および事前フィルタリングの必要が大幅に減らされる。したがって、本手法によれば、図４Ａ〜図４Ｃのフィルタのそれぞれは、スケールが増えるにつれてますます大きくなる区域サイズにまたがる平均化フィルタである。しかし、ある平滑化を、ノイズに対する高められた頑健性を提供し、ブロッキングアーティファクト（blocking artifact）を最小化するために、後続フィルタ位置をわずかにオーバーラップさせることによって実現することができる。１／４から１／２までのフィルタオーバーラップ方式を各方向で使用することが、優れた結果をもたらす。これは、所定のスケールでの次のフィルタ位置を、ａ／２とａの間の値だけ水平方向で前進させ、これによって、前のフィルタ位置に部分的にオーバーラップさせることを意味する。ラインの終りに達した時に、次のフィルタ位置も、ｃ／２とｃの間の値だけ垂直方向で下に移動され、前のフィルタ位置との部分的垂直オーバーラップにもつながる。
【００５３】
この手法の第１の態様は、インテグラルイメージの長方形のフィルタ形状に起因して、フィルタ結果を計算するのに少量の加算だけを要することである。各長方形フィルタ領域は、インテグラルイメージを使用して計算するのに、そのサイズに関わりなく４回の加算だけを必要とする。追加の節約を、隣接領域区域が共通の境界を共有する時に行うことができる。たとえば、図４Ａの水平フィルタを計算するには、通常は３×４＝１２回の加算が必要になる。というのは、このフィルタが１つの中央領域および２つの外側領域を含むからである。しかし、「ガードバンド」領域がない場合には、外側領域をフィルタ区域全体［（−ａ，−ｃ）から（ａ，ｃ）］に延長することと、余分な外側区域の加算を無にするためにそれ相応に「ｐ」および「ｍ」の値を調整することとによって、水平フィルタ全体を１２ではなく８クロックだけで計算することができる。「ノイズバンド」領域なしの単純化された水平フィルタ、垂直フィルタ、および対角フィルタの形状を、それぞれ図６Ａ〜図６Ｃに示す。図６Ａ〜図６Ｃの単純化されたフィルタ形状は、図４Ａ〜図４Ｃのオリジナル形状より計算が高速であるが、「ノイズバンド」領域の欠如に起因して、ノイズに対して図４Ａ〜図４Ｃのオリジナル形状ほど頑健（robust）ではない。ノイズの多い入力イメージの状況では、図６Ａ〜図６Ｃの単純化されたフィルタ形状ではなく、図４Ａ〜図４Ｃのオリジナルフィルタ形状を適用することが好ましい場合がある。
【００５４】
本手法の第２の態様は、フィルタを計算するのに要する動作および時間の量が、フィルタサイズに関わりなく正確に同一のままになる固定された定数であることである。たとえば、図４Ａの水平フィルタが、サイズにおいて２倍にされる場合に、このフィルタは、計算に同一回数の加算を要する。というのは、より大きいフィルタ形状が、それでも、比例して調整された角の点を有する３つの長方形領域からなるからである。これは、ガウシアンフィルタを繰り返して使用し、前のフィルタ出カをダウンサンプリングする場合と対照的であり、この場合に、各より高いピラミッドレベルは、追加の計算を必要とし、前のレベルに加えて余分な時間を要する。
【００５５】
本手法の第３の態様は、任意の順次ピラミッドレベル処理の除去である。これは、本システムおよび方法が、必ず、どのスケールレベルでもフィルタタイプごとに正確に同一の入力イメージを適用するという事実の直接の結果である。入力イメージをフィルタリングする必要は全くなく、したがって、すべての前のピラミッドレベルの完了時に、後続レベル用の入力を得るために前のレベルの出力をフィルタリングし、ダウンサンプリングする必要がある、１つのピラミッドレベルの順次依存性は、除去される。したがって、あるピラミッドレベルの計算は、他のすべてのピラミッドレベルから完全に分離される。
【００５６】
本手法の第４の態様は、並列処理および／またはマルチスレッド環境での実行に理想的に適することである。これは、本システムおよび方法が、未知の入力イメージではなくフィルタをスケーリングすることを選択するからである。フィルタ形状は前もってすべてわかっているので、すべてのタイプ、サイズ、およびスケールのスケーリングされたフィルタ形状のセット全体を、前もって生成し、複数のプロセッサが使用可能な場合には並列に、または別々のスレッドで、入力イメージに適用することができる。ピラミッドレベルの間の任意の依存性の欠如に起因して、スケール空間ピラミッドを作成する処理方式全体を、並列に実行することができる。
【００５７】
本手法の第５の態様は、複数のプロセッサまたはスレッドの間で計算負荷を平衡化することのたやすさである。これは、ほぼすべてのフィルタが、本手法に従って計算される時に、フィルタサイズに関わりなく計算に正確に同一の時間を要するという特性の結果である。したがって、スケール空間ピラミッドを作成する作業は、それぞれが実行にほぼ同一の時間を要する複数のプロセッサまたはスレッドの間で均等に分割することができ、このプロセスの終りに、必要な個数のピラミッドレベルが、結果をメモリに格納する必要なしに、および／または不均一な計算負荷に起因するアイドル状態のプロセッサを有することなく、後続のキーポイント識別に使用可能にされる。
【００５８】
この手法の第６の態様は、より大きいスケールのさらにより大きいフィルタを有するより高いピラミッドオクターブについて、後続のフィルタの位置の間の距離を、計算負荷をさらに減らすために比例して増やすこともできることである。より高いオクターブについて、対応する「しみ様」および／または「接合点様」の特徴は、さまざまなフィルタ出力を一緒に組み合わせた後に、やはり非常に大きくなり、したがって、詳細なサブピクセル精度でその位置を正確に指摘する必要なしに処理することができる。しかし、望まれる場合に、より高いピラミッドオクターブについて追加の補間方式を導入することができる。というのは、結果として得られる後続のフィルタの位置の間の距離が、大きくなる可能性があるからである。
【００５９】
Ｉ．３ スケール空間ピラミッドの作成
スケール変化に対して不変のキーポイントの位置を識別する伝統的手法は、スケール空間として知られるスケールと空間との両方の連続関数を構成し、複数のスケールにまたがって安定した特徴を検索することである。
【００６０】
前述のように、スケール空間ピラミッドを生成する１つの既存の方法は、ＳＩＦＴ法に見られる。ＳＩＦＴ法は、代替のディファレンス・オブ・ガウシアン（ＤｏＧ）関数を用いるラプラシアン・オブ・ガウシアン（ＬｏＧ）法の近似（最初は、リンドバーグ、「Ｓｃａｌｅ Ｓｐａｃｅ Ｔｈｅｏｒｙ： Ａ Ｂａｓｉｃ Ｔｏｏｌ ｆｏｒ Ａｎａｌｙｚｉｎｇ Ｓｔｒｕｃｔｕｒｅｓ ａｔ Ｄｉｆｆｅｒｅｎｔ Ｓｃａｌｅｓ」、Ｊｏｕｒｎａｌ ｏｆ Ａｐｐｌｉｅｄ Ｓｔａｔｉｓｔｉｃｓ，Ｖｏｌ．２１，Ｎｏ．２，２２４〜２７０ページ、１９９４年で提案された）に基づく。
【００６１】
スケール空間ピラミッドを作成するＳＩＦＴ法の概念を、図７Ａ〜図７Ｂに示す。スケール空間のオクターブごとに（図７Ａは、１つのスケールを示し、図７Ｂは、追加のフィルタリングおよびダウンサンプリングの後のより高いスケールを示す）、初期入力イメージが、ガウシアンフィルタのセットを用いて繰り返して畳み込まれて、図７Ａ〜７Ｂの左側に示されたスケール空間イメージのセットを作る。隣接するガウシアンフィルタリングされたイメージは、減算されて、図７Ａ〜７Ｂの右側のディファレンス・オブ・ガウシアンＤ１〜Ｄ３イメージを作る。各オクターブの後に、前のオクターブからのガウシアンイメージが、２倍ダウンサンプリングされ、この処理が、繰り返される。スケール空間ピラミッドを作成する反復処理の概念を、図１５に示す。入力イメージは、図１５の最下部に示され、その上に、特定のスケールのガウシアンフィルタを用いるガウシアンフィルタリングおよびダウンサンプリングの３つの連続する反復の後のカスケードされた結果がある。隣接するガウシアンイメージを減算した後に、結果のディファレンス・オブ・ガウシアンＤ１〜Ｄ３イメージが、識別されたキーポイントを円によって強調表示された状態で図１４に示されている。
【００６２】
次では、既存概念からの進歩を開示するが、オリジナルラプラシアンオブガウシアン（ＬｏＧ）関数は、上で説明したインテグラルイメージの特性を活用する機会を可能にするＳＩＦＴ法の（ＤｏＧ）と異なる新しい近似に置換される。
【００６３】
上のセクションＩ．２で説明したように、図４Ａ〜図４Ｃのフィルタは、ガウス関数の二次偏導関数のトライナリ近似を提供する。したがって、フィルタ出力を一緒に組み合わせて、ラプラシアン・オブ・ガウシアン（ＬｏＧ）の近似を提供することができる。ラプラシアン・オブ・ガウシアン（ＬｏＧ）は、ある形では、（ＤｏＧ）の近似でもある。本手法が、ＳＩＦＴとは異なり、近似の精度に応じて異なる結果につながる可能性が高いことに留意されたい。
【００６４】
ここで、本概念によるスケール空間差ピラミッドの構成に注意を向ける。
【００６５】
図８Ａ〜図８Ｃでは、少なくとも３つのスケール空間差ピラミッド層が、キーポイント位置を識別するのに必要である。これは、近傍スケールにまたがる安定した特徴を識別するために、現在のスケールと、現在のスケールの下の少なくとも１つのスケールおよび現在のスケールの上の少なくとも１つのスケールを含む。図８Ａは、水平フィルタリング（たとえば、Ｆ１ｈ〜Ｆ３ｈ）を表し、図８Ｂは、垂直フィルタリング（たとえば、Ｆ１ｖ〜Ｆ３ｖ）を表し、図８Ｃは、対角フィルタリング（たとえば、Ｆ１ｄ〜Ｆ３ｄ）を表す。図８Ａ〜８Ｃに示されているように、入力イメージは、連続してより大きくなるフィルタＦ１からＦ３までのセットを用いて処理される。その後、水平フィルタ、垂直フィルタ、および対角フィルタからの結果の出力が、一緒に組み合わされて、キーポイント位置が識別される単一の尺度が形成される。
【００６６】
フィルタＦ１からＦ３は、前のセクションで説明した形でインテグラルイメージを使用して効率的に計算される。
【００６７】
本願の一実施形態で、スケール空間の１つのオクターブは、図８Ａ〜図８Ｃに示された３つのフィルタの最小限のセットを使用することによって形成される。
【００６８】
もう１つの実施形態で、追加のますます大きくなるフィルタが、スケール範囲を拡張するためにＦ３を超えて適用される。たとえば、Ｆ４フィルタ（図示せず）を、図８Ａ〜８Ｃに追加することができ、その水平フィルタ、垂直フィルタ、および対角フィルタの出力を一緒に組み合わせて、キーポイント位置を識別するもう１つの尺度層を形成することができる。しかし、１オクターブ内のフィルタの最大個数は、イメージサイズによって制限される。というのは、これが、イメージサイズより大きい特徴を探すために利益をもたらさないからである。したがって、最大のフィルタサイズは、イメージサイズによって決定される。
【００６９】
１つのオクターブ内に３つを超える異なる層がある時には、層は、近傍スケールにまたがる特徴安定性を保証するために隣接する３つの層を含む組で処理される。すなわち、安定したキーポイント位置は、まず、最初の３つの層｛Ｆ１，Ｆ２，Ｆ３｝の内容に基づいて識別され、３つの層の後続セット｛Ｆ２，Ｆ３，Ｆ４｝からの安定したキーポイント位置が続き、新しい最も高い層｛Ｆ４｝は、最下位の層｛Ｆ１｝を置換し、層｛Ｆ２，Ｆ３｝は、両方のセットに共通する。同様に、３つの層の次のセットは、｛Ｆ３，Ｆ４，Ｆ５｝を含むことができ、以下同様である。しかし、ほとんどの場合に、通常、最初の３つを超える多数の層を使用することは必要ではない。というのは、イメージがサイズにおいて１メガピクセルから２メガピクセルを超えない限り、フィルタサイズおよび対応するイメージ特徴のスケールが、オリジナルイメージサイズによってすばやく制限されるようになるからである。１メガピクセルから２メガピクセルを超える場合には、より多くの層を追加することが有益である可能性がある。
【００７０】
スケール空間ピラミッドの４層オクターブを作成するのに使用される水平フィルタのセットを、図９に示す。所定のオクターブ内で、各後続フィルタＦｉは、さらに、前のフィルタＦ（ｉ−１）に対して相対的に係数「ｓ」だけスケールアップされ、または、最高スケールの最初のフィルタＦ１に対して相対的に合計（ｓ×ｉ）だけスケールアップされる。水平フィルタだけが、図９に示されていることに留意されたい。垂直フィルタおよび対角フィルタは、正確に同じ態様でスケールアップされる。
【００７１】
ＳＩＦＴ法のカスケーディングフィルタの手法では、キーポイント位置を第１オクターブについて識別した後に、結果のイメージが、もう一度ダウンサンプリングされ、フィルタリングされ、隣接フィルタ出力が減算され、その結果が、より高いスケールでの追加のキーポイント位置の検出に使用される。このプロセスは、追加のスケールごとに繰り返される。
【００７２】
しかし、本システムおよび方法では、フィルタリングされたイメージをダウンサンプリングするのではなく、基本的なＦ１〜Ｆ３のフィルタサイズのそれぞれが、２倍にされ、スケール空間層が再度計算され、その後、より高いスケールでの任意の新しい安定したキーポイントが識別される。フィルタ形状Ｆ１〜Ｆ３は、事前に十分にわかっているので、Ｆ１〜Ｆ３のスケールアップされた版のすべてを、事前に計算でき、図１のコンポーネントに含まれるメモリなどであるがこれに限定はされないメモリに格納することができる。したがって、本システムおよび方法は、同時に並列にキーポイント位置を別々に識別することを可能にするという点で、並列処理および／またはマルチスレッド処理に理想的に適する。
【００７３】
オクターブごとにフィルタサイズを２倍にするプロセスは、必要なだけ何度でも繰り返される。やはり、ＳＩＦＴ法とは異なって、任意のスケールでのフィルタへの入力イメージが、必ず同一すなわちオリジナル入力イメージであることに留意されたい。
【００７４】
上の説明では、フィルタを２倍にすることによってフィルタのサイズを変更する。しかし、フィルタのセットを任意の比率について設計できることを理解されたい。これは、連続するライン上のピクセルの間の補間の問題にすぎない。
【００７５】
たとえば、提案される１．５倍の比率をとり、３×３最小サイズ水平フィルタから開始されたい（１つの中央線と２つの反対の極性の外側領域、「ガードバンド」なし）。次に、連続して１．５を乗算することによって、３は４．５、６．７５、１０．１２５などになる。したがって、第２フィルタは、サイズにおいて４．５×４．５であり、それぞれ１．５ラインの高さ（スケーリングによって）の３つの水平領域からなる。
【００７６】
４．５フィルタ高さを半分に分割し、中央領域は、この分割線のそれぞれの側で０．７５ラインを含む。したがって、中央領域は、分割の両側の両方のラインのピクセル値の合計の０．７５倍から計算される。
【００７７】
同様に、外側領域は、
（ａ）分割の両側の両方の周辺のラインのピクセル値の合計の０．２５倍と、
（ｂ）分割の両側の１ライン離れたラインのピクセル値の合計と、
（ｃ）分割の両側の２ライン離れたラインのピクセル値の合計の０．２５倍と、
の合計によって計算される。
【００７８】
後続のより大きいフィルタは、類似する形で得られる。
【００７９】
分かる通り、境界上の共有されるイメージピクセルは、単純に、領域の間の境界線までの距離によって線形に重みを付けられる（すなわち、補間される）。
【００８０】
したがって、この説明は、非整数比が多少の追加の補間および丸めを必要とすることを除いて、任意の比率に拡張することができる。
【００８１】
Ｉ．４ スケール空間での安定したキーポイント位置の識別
本手法の目的は、ターゲットイメージのターゲットのノイズのある（すなわち、ダウングレードされた）版内で高い確率で信頼できる形で見つけることができるイメージ内の安定したキーポイントを識別することである。
【００８２】
ＤｏＧ関数に基づくＳＩＦＴ法とは異なって、本願で説明される手法は、「しみ様」のイメージ特徴および「接合点様」のイメージ特徴の検出に基づく。要件は、これらの「しみ」特徴および「接合点」特徴を、ターゲットイメージのノイズのある版で信頼できる形で見つけることができることと、これらの特徴が、シーン照明および類似物の変動に堅牢であり、また、イメージに対する相対的なある分散特性を有する（すなわち、これらの特徴を、イメージがスケーリングされ回転された版においても高い確率で見つけることができる）ことである。
【００８３】
上のセクションＩ．２で示したように、本システムおよび方法の水平フィルタは、現在のスケールでのフィルタサイズに対応するサイズの水平の「細長い」イメージ特徴について大きい大きさの信号を作る傾向がある。そのような特徴は、水平方向でよく局所化可能であるが、必ずしも垂直方向でよく局所化可能ではない。同様に、垂直フィルタは、垂直方向に局所化可能な特徴について強い大きさの信号を作る。この２つの応答を一緒に組み合わせることによって、水平方向と垂直方向との両方で局所化できるイメージ内の「しみ様」特徴位置を識別することが可能である。
【００８４】
同様に、対角フィルタは、現在のスケールでの対角フィルタサイズに対応するサイズの斜めの「角」イメージ特徴または「接合点様」イメージ特徴について出力で大きい大きさの信号を作るように働く。そのような特徴は、対角線方向でよく局所化可能でもある。このタイプの例は、交番するチェッカーボードの黒白／白黒パターンまたはその逆の４つの隣接する正方形の間の接合点あるいは任意の９０度の暗い角または明るい角を含む。もちろん、イメージ内の他の位置を、接合点として判定することができる。
【００８５】
２つの特徴タイプすなわち「しみ様」イメージ特徴および「接合点様」イメージ特徴を異なるフィルタ出力で別々に見つけることを試みるのではなく、この実施形態では、２つの特徴タイプが、次の単一の特徴尺度に組み合わされる。
【００８６】
Ｄ（ｘ，ｙ，ｓ）＝ＦH（ｘ，ｙ，ｓ）×ＦV（ｘ，ｙ，ｓ）−［ｋ×ＦD（ｘ，ｙ，ｓ）］2
ここで、ＦH（ｘ，ｙ，ｓ）、ＦV（ｘ，ｙ，ｓ）、およびＦD（ｘ，ｙ，ｓ）は、それぞれ図４Ａ〜図４Ｃに示された水平フィルタ出力、垂直フィルタ出力、および対角フィルタ出力であり、ｋ2は、異なるフィルタ形状を有する可能性および整数ピクセル境界での離散値への変換に起因する２つの特徴タイプの間の正規化パラメータである。
【００８７】
「しみ様」イメージ特徴について、対角フィルタの出力での信号の大きさは、小さい可能性が高いが、水平フィルタおよび垂直フィルタの出力での大きさは、大きい。同様に、「接合点様」イメージ特徴について、水平フィルタまたは垂直フィルタの出力は小さい可能性が高いが、対角フィルタの出力の大きさは大きい。したがって、この２つの特徴タイプを、Ｄ（ｘ，ｙ，ｓ）の出力の大きさを最大にするすなわち、Ｄ（ｘ，ｙ，ｓ）の最大点または最小点のいずれかの極値を探すという単一の目標に一緒に組み合わせることができる。したがって、キーポイント位置は、関数Ｄ（ｘ，ｙ，ｓ）がスケールｓと空間（ｘ，ｙ）との両方でその極値点を達成する、イメージ内の位置として識別される。
【００８８】
スケール空間領域での極値点を検索する方法を図１０に示す。差関数Ｄ（ｘ，ｙ，ｓ）は、スケール空間全体にまたがって計算される。（ｘ，ｙ，ｓ）内のピクセル位置（２ｅ）は、関数Ｄ（ｘ，ｙ，ｓ）の値が、図１０に示されているようにその直接近傍に対して最大値または最小値のいずれかのピークである場合に、候補キーポイント位置であると判定される。
【００８９】
あるイメージ内で識別できる安定したスケール不変キーポイント位置の個数は、イメージ内容および以下で定義する所望のキーポイント強さに依存して、かなり変化する。キーポイントの最終的な個数は、所定の通常の自然シーンイメージ内で、数百個から数千個まで変化する可能性がある。したがって、イメージピクセルの大多数は、候補キーポイント位置ではない。したがって、性能の理由から、特定のピクセルが有効なキーポイント位置ではない時に候補キーポイント位置としてのそのピクセル位置をすばやく除外できる方法を探すことが望ましい。明らかに、各ピクセル位置の周囲の近傍ピクセルのすべてをチェックする必要を実際には伴わずに、できる限り高速にそれを行うことが望ましい。
【００９０】
この問題を解決する本願の実施形態の手法は、３重ピクセル比較テストの順序付きセットに基づく。この方法は、ルールベースである。各テストでは、中央ピクセルの両側の対向するピクセルの対を調べる。この方法は、現在のフィルタスケールで空間ピクセル近傍（ｘ，ｙ）平面を調べることによって開始される。近傍は、図１０の中央の平面で９個のピクセル（すべて数字２から始まる）を含む。この近傍の拡大図を、図１１に示す。この方法の目的は、中央ピクセル位置（２ｅ）を候補キーポイント位置にすることができるかどうかを判定することである。
【００９１】
この方法の第１のルールは、図１１の前のピクセル位置（２ｄ）がキーポイント位置として識別されたかどうかをチェックすることである。そうである場合には、位置（２ｄ）での関数Ｄ（ｘ，ｙ，ｓ）の値は、その近傍に対して最大値または最小値でなければならない。したがって、Ｄ（ｘ，ｙ，ｓ）は、１ピクセル離れた位置（２ｅ）でもピーク（すなわち、キーポイント）になることはできず、この場合に、（２ｅ）のテストは、終了し、このプロセスは、次のピクセルに進むことができる。
【００９２】
しかし、前のピクセル位置（２ｄ）がキーポイントではなかった場合に、この方法は、（２ｅ）の両側の対向するピクセル対位置（２ｄ）および（２ｆ）でのＤ（ｘ，ｙ，ｓ）の値を取り出す。中央ピクセル（２ｅ）でのＤ（ｘ，ｙ，ｓ）の値は、（２ｅ）が図１１の方向１に沿ったＤ（ｘ，ｙ，ｓ）の局所極値点としての資格を有するために、最大値の場合には（２ｄ）および（２ｆ）のいずれよりも大きくなければならず、あるいは（２ｄ）および（２Ｆ）より小さくなければならない（最小値の場合）。
【００９３】
さらに、ノイズの存在および／またはあるピクセルから次のピクセルへのＤ（ｘ，ｙ，ｓ）の小さい丸め誤差に起因するランダムな弱いキーポイント位置の偶然の識別の尤度を除去するために、しきい値「Ｔ」を導入する。このしきい値は、次のように定義される。
すべての近傍ｘ，ｙ，ｓについて、
｜Ｄ（ｘ，ｙ，ｓ）−Ｄ(2e)（ｘ，ｙ，ｓ）｜＞Ｔ
すなわち、中央ピクセル位置でのＤ（ｘ，ｙ，ｓ）の値は、そのピクセル近傍位置のいずれかのＤ（ｘ，ｙ，ｓ）のすべての他の値より少なくともＴだけ大きいまたは小さいものでなければならない。しきい値Ｔの値は、識別できるキーポイントの個数を決定する。
【００９４】
Ｔが大きい時には、最も強いピーク大きさ値Ｄ（ｘ，ｙ，ｓ）を有する最も強いキーポイント位置だけが識別される。Ｔの値を減らすにつれて、より弱いピーク大きさの追加キーポイントを識別することができる。したがって、Ｔの値は、キーポイントの所望の個数および識別されるキーポイントの結果の強さを制御するのに使用することができる。
【００９５】
本願の一実施形態で、Ｔの値は、イメージの期待されるタイプ、キーポイントの所望の個数、およびキーポイントの相対的な強さに基づいて事前に予め決定される定数値である。
【００９６】
本願の他の１つの実施形態で、Ｔの値は、上記で示したように最小キーポイント強さを決定する固定された定数部分と、当該の現在のピクセル位置の周囲の局所領域内のＤ（ｘ，ｙ，ｓ）大きさの平均変動に基づく動的に可変な部分と、の合計からなる。Ｔの動的な調整は、他のより静かなイメージ区域に対して騒がしいイメージ区域内で識別されるキーポイントの個数を制御するのに使用することができる。
【００９７】
本願の第３の実施形態で、対向する対のピクセルのＤ（ｘ，ｙ，ｓ）値と（２ｅ）での中央Ｄ（ｘ，ｙ，ｓ）値との間の大きさの差が、キーポイント強さの尺度を提供するために、ピクセル対にまたがって累算され、正規化される。キーポイントの強さは、その後、より弱くより不安定なキーポイントを除去し、その強さに従ってキーポイントをソートするのに使用することができる。
【００９８】
図１１を継続して参照すると、（２ｅ）での中央Ｄ（ｘ，ｙ，ｓ）値が、対向する近傍位置（２ｄ）および（２ｆ）に関してピーク値になるためのすべての必要条件を満足してはいない場合に、やはり、（２ｅ）をキーポイント位置にすることができないと結論することができ、このプロセスは、次のピクセル位置に移ることができる。
【００９９】
そうではなく、中央位置（２ｅ）が、まだキーポイント位置であり得る場合に、この方法は、図１１の方向２に沿った（２ｅ）の両側のピクセル位置（２ａ）および（２ｉ）の次の対向する対のＤ（ｘ，ｙ，ｓ）の値を取り出す。この方法は、中央位置（２ｅ）がまだキーポイント位置として識別され得るかどうかを判定するために、上の分析を繰り返す。この対でのピクセル比較テストは、図１１に示された残りのピクセル対方向３および４について、中央位置（２ｅ）の周囲の円で継続される。
【０１００】
この方法は、候補キーポイント位置として中央位置（２ｅ）を識別することに失敗するピクセル対が最初に出現した時に終了するように設計される。検索は、しばしば、追加テストにより長い時間を費やすことなく、これらの対でのピクセルテストのうちの２〜３回のみの後に、すばやく終了する。しかし、この実施形態では、ピクセル位置は、すべての可能な対でのテストおよびすべての他の追加のルールがすべて完全に満足された後に限って、安定したキーポイント位置として識別される。
【０１０１】
もう１つの実施形態では、すべての可能な対でのテストを行う必要はないものとすることができる。たとえば、計算の回数を減らすために、対でのテストの一部を除去することができる（たとえば、図１２の遠い角１ａ、１ｃ、１ｇ、１ｉから）。１ピクセルだけ離れた近傍のみを使用することによって、これは、テストの回数をこのケースで９回から５回に減らす（スケールの間で）。したがって、この実施形態では、すべての可能な対でのテストが使用されるわけではない。
【０１０２】
上で述べた追加ルールの例を、以降の段落で展開する。さらに、そのような追加ルールは、たとえば１ピクセルを超えて離れたさらなる対向するピクセル対を調べ、または中央ピクセルの両側の両方が同一の符号を有するかどうかをチェックすることによって、現在の同一スケールのケースにも適用可能である。たとえば、２ａの左に１ピクセルおよび２ｉの右に１ピクセルは、図１１の１と２との間の新しい方向での新しいテストをもたらすなどである。
【０１０３】
現在のスケール平面のテストにおいて、上で概要を示した図１１の方向１〜４に沿った４つの対でのピクセルテストを完了したならば、この方法は、中央ピクセル位置（２ｅ）をそのスケールに関してキーポイント位置として識別できるかどうかのチェックに進む。
【０１０４】
９つの追加の対向する対でのテストを、図１２に示された方向１〜９に沿って適用する。各対でのピクセルテストは、本質的に、キーポイントの強さのしきい値Ｔを含めて、上で説明したものと同一である。しかし、すべてのピクセル位置が同一の現在のスケールにある、４つの対でのテストの前のケースとは異なって、今回は、対向するピクセル位置が、必ず異なるスケールから選択され、一方は現在のスケールより小さいスケール、他方はより大きいスケールから選択される。これは、中央位置（２ｅ）が実際にすべての可能な方向でＤ（ｘ，ｙ，ｓ）の真のスケール空間ピークであることを保証するために行われる。
【０１０５】
やはり、この方法は、前述の対でのピクセルテストのいずれかの最初の失敗で終了するようにセットされる。
【０１０６】
本願の他の実施形態では、追加の対でのルールを追加して、識別できる結果のキーポイントに対するさらなる制約を設けることができる。たとえば、Ｄ（ｘ，ｙ，ｓ）の符号一貫性に関する追加の制約、または、１つ小さいスケールおよび１つ大きい平面でのさらに離れた対向するピクセルの対を追加して、より多くの角度での追加の方向テストを実現することによるものなどである。
【０１０７】
図１３Ａ〜図１３Ｅに、本発明の実施形態に従って実行されるキーポイント識別手順の結果を示す。より具体的には、入力イメージが、図１３Ａに示されている。図１３Ｂは、水平フィルタによって生成された出力であり、図１３Ｃは、垂直フィルタによって生成された出力であり、図１３Ｄは、対角フィルタによって生成された出力であり、このすべてが同一の特定のスケールである。最後に、図１３Ｅは、３つすべてのフィルタを組み合わせた時の出力を示す。
【０１０８】
図１３Ａの入力イメージは、グレイスケールイメージに変換されたオリジナルイメージとすることができる。次に、異なるサイズのフィルタのセットをグレイスケールイメージに適用して、図９に示されたスケール空間ピラミッド層を作成する。ある特定のスケールでの水平フィルタ、垂直フィルタ、および対角フィルタの通常の出力を、それぞれ図１３Ｂ、図１３Ｃ、および図１３Ｄに示す。この３つのフィルタ出力を一緒に組み合わせて、少なくとも３つの連続するスケールで関数Ｄ（ｘ，ｙ，ｓ）を形成する。最後に、３つのスケールのうちの１つすなわち現在のスケールの出力を、図１３Ｅに示す。Ｄ（ｘ，ｙ，ｓ）がそのすべての近傍に対してスケール空間内で極値を達成するピクセル位置が、現在のスケール空間ピラミッド層の安定したキーポイント位置として識別される。
【０１０９】
追加のキーポイントをより高いピラミッド層から抽出することができる。
【０１１０】
図１４に、より高いピラミッド層内で追加のキーポイント（円によって示される）を識別するプロセスを示す。参照のために、図１５に、各ピラミッド層でフィルタサイズを２倍にすることに起因するイメージサイズの対応する縮小を考慮に入れた後の「同等の」ＤｏＧイメージピラミッドを示す。図１５が、参照のみのために提供され、提案される方法実施態様の一部と混同されてはならないことに留意されたい。
【０１１１】
本願の提案される方法は、ＳＩＦＴなどの既存の方法のどれよりも計算がかなり高速でありながら、イメージ内の安定したキーポイントの識別において同様に効果的であると認められる。
【０１１２】
ガウシアンフィルタは、非常に高速に計算でき、既存の方法に対してはるかに少数の計算を必要とする、はるかにより単純なハールライク（Ｈａａｒ−ｌｉｋｅ）特徴突出インジケータ長方形フィルタに置換される。既存の方式の多くとは異なって、ガウシアンフィルタリングは、現在説明されている複数スケール分析で直接には使用されない。ガウシアンフィルタリングは、その優れた平滑化特性に起因して、空間スケール分析に望ましいと判定された。しかし、実際には、ガウシアン形状は、離散値にディジタル化することと、さらに、切り捨てなければ無限の尾をある点を超えて切り捨てることとによって近似されなければならないという点で、理想的ではない。さらに、正確なガウシアンフィルタリングを用いても、エイリアシングアーティファクトが、イメージをダウンサンプリングする時に導入され得る。非常に重要視されている技法のいくつかは、ガウシアン形状のさらなる近似の下であっても優れた結果を実証した（たとえば、ＳＩＦＴ法の一部としてのディファレンス・オブ・ガウシアン（ＤｏＧ）イメージピラミッドとしてのラプラシアン・オブ・ガウシアン（ＬｏＧ）イメージピラミッドのＤ．Ｌｏｗｅの近似）。
【０１１３】
本システムおよび方法は、再帰的フィルタリングを使用せずに、オリジナルイメージに直接に異なる長方形形状サイズを適用することによって、イメージピラミッド全体を便利に効率的に計算することができる。したがって、本システムおよび方法は、反復的にイメージをスケールダウンするのではなく、フィルタサイズをスケールアップすることによって複数スケール分析を実行することができる。
【０１１４】
本願の実施形態のシステムおよび方法は、非常に高速のレートを達成するだけではなく、その速度は、すべてのフィルタサイズについて正確に同一である。長方形フィルタ形状を用いると、これを達成するための面積合計積分の特性が活用される。まず、所定の左下のイメージ角に対するオリジナルイメージの各ピクセルの面の積合計を計算する。これは、行および列を記憶しながら前の面積の合計に現在のピクセル値を再帰的に加算することによって、１ピクセルあたり約１回の加算で効率的に行うことができる。面積合計積分をイメージ全体について計算し、メモリに格納したならば、任意の長方形フィルタ形状の下の面積を、任意の長方形フィルタサイズについて２回の加算だけを使用して計算でき、性能の改善につながる。
【０１１５】
たとえばヘッセ行列ベースの技法と同様にガウシアン二次導関数を使用するのではなく、本願の実施形態では、他の点では複数スケール分析として知られる、２つの空間イメージ次元空間内ならびにさまざまなスケール内で局所化できる独特なキーポイントを見つけることを試みる。この方法は、そのようなキーポイントの位置を識別するのに単純な長方形フィルタ形状を使用する。本願の実施形態では、イメージ内の最も特徴的なキーポイントのセットを探すので、フィルタの正確な形状は、決定的ではない。すなわち、鋭いビルディングの角または目の角などの明確に局所化されたイメージキーポイントは、より単純なフィルタを用いて同様によく見つけられる可能性が高い。本願の実施形態では、垂直方向、水平方向、および対角線方向でイメージ特徴を取り込むように設計されたフィルタ形状を利用する。特定のフィルタ形状は、ガウシアン形状の長方形近似と解釈することができる。入力イメージの品質および予想される取り込みデバイスに応じて、これらのフィルタは、さらに、ノイズおよびサンプリングアーティファクトを除去するのを助けるために分離「ガードバンド」を含むことができる。基本的なフィルタ形状は、複数スケールイメージ分析をもたらすためにスケールアップされる。しかし、フィルタ形状の実際のスケーリングは、必要ではない。長方形のフィルタ形状に起因して、スケーリングを、前もって新しい角の座標を記録し、その後、新しい異なるサイズのフィルタ結果を得るためにイメージ積分を使用することによって、効率的に行うことができる。
【０１１６】
本システムおよび方法は、各ピラミッドレベルを、上記で概要を示した面積合計を使用して入力イメージから直接に計算できるので、並列な実施態様に特に適する。各ピラミッドレベルの計算は、他のピラミッドレベルと完全に独立であり、フィルタサイズに関わりなく正確に同一の時間を要する。
【０１１７】
本願の実施形態では、イメージ内の独特なキーポイントの位置を判定するのにルールベースの方法を使用する。数百万個のピクセルを含む通常のイメージは、数百個から数千個の候補キーポイントを生じる場合がある。ほとんどのイメージピクセルはキーポイントではないので、任意の所定のイメージピクセルで費やされる時間の最小化が探される。本システムおよび方法は、現在のピクセルを強いキーポイント候補にすることができるかどうかをすばやく判定するために、さまざまなスケールおよび方位で当該の現在のピクセルの両側の近傍ピクセルの対などの間で一連の連続するテストを実行する。これらのテストは、尤度順によって編成される。各連続するテストで、現在のピクセルとその隣接物との間の関係が、要求される条件を満足しない場合には、この方法は、キーポイントとしての現在の位置を除外し、次のピクセルに移る。したがって、全体的な時間が最小化されると同時に、各最終的なキーポイントは、有効なキーポイントであるためのすべての条件を満足する。本システムおよび方法は、複数のそのようなルールを使用して、ありそうなキーポイント候補を判定する。
【０１１８】
本願の実施形態では、結果の滑らかさを改善し、フィルタ境界に沿った潜在的不連続性の影響を減らすために、各後続フィルタ位置のサンプリングのオーバーラップという概念も導入される。長方形フィルタは、スケーリングの後に一定のままになるように正規化される。さらに、フィルタサイズが、各より大きいスケールの分析のために増やされる時に、サンプリング位置をも対応して増やして、キーポイントの識別に関するより高いピラミッド層の有効解像度を便利に下げることができる。
【０１１９】
キーポイントの候補それぞれのキーポイントの強さの尺度も導入される。結果のキーポイントを、イメージ内の最良の最も特徴的なキーポイントを識別し、イメージの劣化したノイズのある版で見つかる可能性が高くはないすべての他の弱いキーポイントを破棄するために、強さの順でソートすることができる。通常、最も強いキーポイントのうちの最上位の数百個が、イメージ照合のために最も有用である。したがって、性能の改善を、最も強いキーポイントの小さいサブセットに集中することと、照合結果が結論に達しない場合に限ってより弱いキーポイントを追加することとによって得ることができる。代替案では、キーポイントの所望の個数および強さを前もって決定することができ、キーポイント識別プロセスを、十分な個数の適切なキーポイントが識別されるや否や停止することができ、これによって、さらなるキーポイントを識別するために時間を浪費しなくなる。キーポイントの強さは、各テストの個々の寄与を使用して、テストのシーケンス中にオンザフライで計算される。キーポイントの強さの尺度は、さらなる下流処理でアンカキーポイントを選択するためなどであるがこれには限定されないある種の特定用途向け処理に特に有用である。
【符号の説明】
【０１２０】
１００ コンピュータネットワーク、１０２，１０６ ワイヤ、１０４ ワイヤジャンクション、１０８，１０９ コンピュータ、１１０ カラープリンタ、１１２ カラー以外のプリンタ、１２０，１２２ カラーレーザプリンタ、１２４ カラー以外のレーザプリンタ、１３０ スキャナ、１４０ ファクシミリ機、１５０ 写真複写機、１５２ カラー写真複写機、１５４ 組合せカラープリンタ／スキャナ／ファクシミリ機、１６０ パーソナルコンピュータおよび／または独立型コンピュータ端末、１６４ 独立型ハードドライブデータストレージ媒体、１７０ 無線ネットワーク送受信器、１７２，１７４ ラップトップコンピュータ、１８０ ネットワーク、１９０ 周辺データ取り込みデバイス、１９１ ディジタルスチルカメラ、１９２ ディジタルビデオカメラ、１９３ セル電話機、１９４ スキャナ、１９５ 携帯情報端末、１９６ 文書インデクシングシステム。
【特許請求の範囲】
【請求項１】
入力イメージのインテグラルイメージを計算するステップと、
複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成するステップであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、ステップと、
スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせるステップと、
前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別するステップと、
前記安定したキーポイント位置をメモリストレージに格納するステップと、
を含むことを特徴とする、局所化されたスケール空間特性を使用してピクチャイメージ内の安定したキーポイントを見つける方法。
【請求項２】
請求項１に記載の方法であって、前記フィルタは、異なるサイズの長方形フィルタであることを特徴とする方法。
【請求項３】
請求項１に記載の方法であって、前記構成するステップは、前記フィルタサイズに関わりなく所定の回数の演算を含むことを特徴とする方法。
【請求項４】
電子データ処理システムであって、前記電子データ処理システムのメモリに格納されたソフトウェア動作を処理できる少なくとも１つのプロセッサを含み、動作の前記処理が、
入力イメージのインテグラルイメージを計算することと、
複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成することであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、構成することと、
スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせることと、
前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別することと、
前記安定したキーポイント位置をメモリストレージに格納することと、
を含むことを特徴とする、電子データ処理システム。
【請求項１】
入力イメージのインテグラルイメージを計算するステップと、
複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成するステップであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、ステップと、
スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせるステップと、
前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別するステップと、
前記安定したキーポイント位置をメモリストレージに格納するステップと、
を含むことを特徴とする、局所化されたスケール空間特性を使用してピクチャイメージ内の安定したキーポイントを見つける方法。
【請求項２】
請求項１に記載の方法であって、前記フィルタは、異なるサイズの長方形フィルタであることを特徴とする方法。
【請求項３】
請求項１に記載の方法であって、前記構成するステップは、前記フィルタサイズに関わりなく所定の回数の演算を含むことを特徴とする方法。
【請求項４】
電子データ処理システムであって、前記電子データ処理システムのメモリに格納されたソフトウェア動作を処理できる少なくとも１つのプロセッサを含み、動作の前記処理が、
入力イメージのインテグラルイメージを計算することと、
複数のスケールで前記入力イメージのスケール空間ピラミッド層表現を構成することであって、各スケールで、特定のフィルタのセットが、前記入力イメージの少なくとも一部の近似を作るために前記入力イメージに適用される、構成することと、
スケールおよび空間の単一の関数を形成するために前記フィルタの出力を一緒に組み合わせることと、
前記単一の関数が局所ピーク値を達成するピクセル位置として各スケールでの安定したキーポイント位置を識別することと、
前記安定したキーポイント位置をメモリストレージに格納することと、
を含むことを特徴とする、電子データ処理システム。
【図１】
【図２Ｂ】
【図２Ｄ】
【図２Ｆ】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図５Ｄ】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７Ａ】
【図７Ｂ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図９】
【図１０】
【図１１】
【図１２】
【図２Ａ】
【図２Ｃ】
【図２Ｅ】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１３Ｄ】
【図１３Ｅ】
【図１４】
【図１５】
【図２Ｂ】
【図２Ｄ】
【図２Ｆ】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５Ａ】
【図５Ｂ】
【図５Ｃ】
【図５Ｄ】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７Ａ】
【図７Ｂ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図９】
【図１０】
【図１１】
【図１２】
【図２Ａ】
【図２Ｃ】
【図２Ｅ】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１３Ｄ】
【図１３Ｅ】
【図１４】
【図１５】
【公開番号】特開２０１０−９５９９（Ｐ２０１０−９５９９Ａ）
【公開日】平成２２年１月１４日（２０１０．１．１４）
【国際特許分類】
【出願番号】特願２００９−１５０２８４（Ｐ２００９−１５０２８４）
【出願日】平成２１年６月２４日（２００９．６．２４）
【出願人】（５０２０９６５４３）パロ・アルト・リサーチ・センター・インコーポレーテッド (393)
【氏名又は名称原語表記】Ｐａｌｏ Ａｌｔｏ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ Ｉｎｃｏｒｐｏｒａｔｅｄ
【Ｆターム（参考）】
【公開日】平成２２年１月１４日（２０１０．１．１４）
【国際特許分類】
【出願日】平成２１年６月２４日（２００９．６．２４）
【出願人】（５０２０９６５４３）パロ・アルト・リサーチ・センター・インコーポレーテッド (393)
【氏名又は名称原語表記】Ｐａｌｏ Ａｌｔｏ Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ Ｉｎｃｏｒｐｏｒａｔｅｄ
【Ｆターム（参考）】
[ Back to top ]