(57)【特許請求の範囲】
【請求項１】
オブジェクトについての３次元（３Ｄ）ポイント・クラウドを装置が取得するステップと、
前記オブジェクトについての２Ｄ画像における特徴ポイントに対するバイナリ特徴記述子を前記装置が取得するステップと、
各特徴ポイントに対する複数の指標値を、対応する前記バイナリ特徴記述子の多重ビットとして前記装置が割り当てるステップと、
データベース画像の複数のハッシュ・キー・テーブルのテーブル・エントリに前記バイナリ特徴記述子を表す前記指標値を前記装置が格納するステップと、
クエリ画像における特徴ポイントに対するクエリ・バイナリ特徴記述子を前記装置が取得するステップと、
前記クエリ・バイナリ特徴記述子を、前記データベース画像の前記バイナリ特徴記述子に対して、前記ハッシュ・キー・テーブルに格納された前記バイナリ特徴記述子を表す前記指標値に基づいて、前記装置がマッチングするステップと、
マッチした前記データベース画像の前記ハッシュ・キーの１ビットを前記装置が再選択するステップと、
前記データベース画像の前記ハッシュ・キー・テーブルのテーブル・エントリにおける前記特徴ポイントを前記装置が再指標付けするステップと、
を含む方法。
【請求項２】
前記テーブル・エントリのサイズの均一性およびマッチした特徴対のコリジョン率を定義するコスト関数が最小化されるように、マッチした前記データベース画像の前記ハッシュ・キーの前記１ビットを前記装置が再選択するステップ、をさらに含む、請求項１に記載の方法。
【請求項３】
前記コスト関数がＣ＝λ（１−ｐc）＋１／（１−ｕ'）であり、
ここで、λは予め設定された重みであり、
ｐcは、２つのマッチした特徴が、あるビットにおいて一致する確率であり、
ｕ'は、前記クエリ・バイナリ特徴記述子を、前記バイナリ特徴記述子に対してマッチングするための線形探索における時間短縮因子である、
請求項２に記載の方法。
【請求項４】
各特徴ポイントについての前記指標値の前記多重ビットは、対応する前記バイナリ特徴記述子からランダムに選択される、請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
前記クエリ・バイナリ特徴記述子は、近似最近傍（ＡＮＮ）探索を用いて前記データベース画像の前記バイナリ特徴記述子にマッチングされる、請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
前記ハッシュ・キーに対する前記１ビットを、前記特徴ポイントのランダムに構成されたサブセット内で前記装置が再選択する、請求項１ないし５のいずれか１項に記載の方法。
【請求項７】
新規のクエリ画像が取得されたとき、前記ハッシュ・キーの第１の半分の中から前記１ビットを前記装置が再選択するステップと、
次のクエリ画像が取得されたときに、前記ハッシュ・キーの第２の半分の中から前記１ビットを前記装置が再選択するステップと、
をさらに含む、請求項１ないし６のいずれか１項に記載の方法。
【請求項８】
少なくとも１つのプロセッサと、コンピュータ・プログラム・コードを含むメモリとを備えた装置であって、
前記メモリおよび前記コンピュータ・プログラム・コードは、前記少なくとも１つのプロセッサを用いて、前記装置に、少なくとも、
オブジェクトについての３次元（３Ｄ）ポイント・クラウドを取得させ、
前記オブジェクトについての２Ｄ画像における特徴ポイントについてバイナリ特徴記述子を取得させ、
各特徴ポイントについての複数の指標値を、対応する前記バイナリ特徴記述子の多重ビットとして割り当てさせ、
データベース画像の複数のハッシュ・キー・テーブルのテーブル・エントリに前記バイナリ特徴記述子を表す前記指標値を格納させ、
クエリ画像における特徴ポイントに対するクエリ・バイナリ特徴記述子を取得させ、
前記クエリ・バイナリ特徴記述子を前記データベース画像の前記バイナリ特徴記述子に対して前記装置が前記ハッシュ・キー・テーブルに格納されたバイナリ特徴を表す前記指標値に基づいてマッチングさせ、
マッチした前記データベース画像の前記ハッシュ・キーの１ビットを再選択させ、
前記データベース画像の前記ハッシュ・キー・テーブルのテーブル・エントリ内の前記特徴ポイントを再指標付けさせるように構成される、装置。
【請求項９】
前記装置に、前記テーブル・エントリのサイズの均一性およびマッチした特徴対のコリジョン率を定義するコスト関数が最小化されるように、マッチした前記データベース画像の前記ハッシュ・キーの前記１ビットを再選択 させるように構成されたコードをさらに含む、請求項８に記載の装置。
【請求項１０】
前記コスト関数がＣ＝λ（１−ｐc）＋１／（１−ｕ'）であり、
ここで、λは予め設定された重みであり、
ｐcは、２つのマッチした特徴が、あるビットにおいて一致する確率であり、
ｕ'は、前記クエリ・バイナリ特徴記述子を前記バイナリ特徴記述子とマッチングするための線形探索における時間短縮因子である、
請求項９に記載の装置。
【請求項１１】
前記装置は、更に、各特徴ポイントの前記指標値の前記多重ビットを、対応する前記バイナリ特徴記述子からランダムに選択するように構成される、請求項８ないし１０のいずれか１項に記載の装置。
【請求項１２】
前記装置は、更に、前記クエリ・バイナリ特徴記述子を、近似最近傍（ＡＮＮ）探索を用いて前記データベース画像の前記バイナリ特徴記述子とマッチングするように構成される、請求項８ないし１１のいずれか１項に記載の装置。
【請求項１３】
前記装置は、更に、前記ハッシュ・キーのための前記１ビットを、前記特徴ポイントのランダムに構成されたサブセットにおいて再選択するように構成される、請求項８ないし１２のいずれか１項に記載の装置。
【請求項１４】
前記装置は、更に、新規のクエリ画像が取得された場合に、前記ハッシュ・キーの第１の半分の中から前記１ビットを再選択し、
次のクエリ画像が取得されたとき、前記ハッシュ・キーの第２の半分の中から前記１ビットを再選択する
ように構成される、請求項８ないし１３のいずれか１項に記載の装置。
【請求項１５】
オブジェクトについての３次元（３Ｄ）ポイント・クラウドを取得するためのコードと、
前記オブジェクトについての２Ｄ画像において、特徴ポイントに対するバイナリ特徴記述子を取得するためのコードと、
各特徴ポイントについての複数の指標値を、対応する前記バイナリ特徴記述子の多重ビットとして割り当てるためのコードと、
データベース画像の複数のハッシュ・キー・テーブルのテーブル・エントリに、前記バイナリ特徴記述子を表す前記指標値を格納するためのコードと、
クエリ画像内の特徴ポイントに対するクエリ・バイナリ特徴記述子を取得するためのコードと、
前記クエリ・バイナリ特徴記述子を、前記データベース画像の前記バイナリ特徴記述子に対して、前記ハッシュ・キー・テーブルに格納されたバイナリ特徴を表す前記指標値に基づいてマッチングするためのコードと、
マッチした前記データベース画像の前記ハッシュ・キーの１ビットを再選択するためのコードと、
前記データベース画像の前記ハッシュ・キー・テーブルのテーブル・エントリ内の前記特徴ポイントを再指標付けするためのコードと、
を備えるコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理、より詳細には、ポイント・クラウドの位置特定およびマッピングを同時に行う技術に関する。
【背景技術】
【０００２】
３Ｄポイント・クラウドは、さまざまな画像処理およびコンピュータ・ビジョン・アプリケーションにおいて使用される。３Ｄポイント・クラウドは、典型的にオブジェクトの外部表面を表現する３Ｄ座標系内のデータ・ポイント・セットである。オブジェクトの表面上で多数の点が測定され、取得したポイント・クラウドをファイル内に格納することができる。コンピュータ・ビジョン・アプリケーションのためには、３Ｄポイントは典型的に、オブジェクトの２Ｄ画像の認識された特徴にマッピングされる。
【０００３】
ロボット工学およびコンピュータ・ビジョンの両方において、ＳＬＡＭ（Ｓｉｍｕｌｔａｎｅｏｕｓ  ｌｏｃａｌｉｚａｔｉｏｎ  ａｎｄ  ｍａｐｐｉｎｇ：位置特定およびマッピングを同時に行うこと）が広範に研究されてきた。ＳＬＡＭとは、未知の環境のマップを更新すると同時にその内部で観察者を位置特定する問題を意味する。ＳＬＡＭにおける１つの重要な特徴は、再位置特定、すなわち、追跡の失敗後のカメラの姿勢の回復である。カメラの姿勢は、マップ内の３Ｄポイントと画像内の２Ｄ特徴の間の対応を用いて推定可能であることから、再位置特定における主要な問題は、３Ｄ−２Ｄ対応を取得することにある。再位置特定プロセスは、マッピングに対する反転プロセスとみなすことができる。すなわち、特徴が２Ｄ画像から抽出され、３Ｄポイントの特徴に対しマッチングされる。
【０００４】
オブジェクトまたはシーンの３Ｄポイント・クラウドは、莫大なボリュームを有する可能性がある。例えばＳＬＡＭにおいて、３Ｄ−２Ｄ対応のコレクションを生み出すために、２Ｄ画像特徴の代りにバイナリ特徴を取得し、かくして処理すべきデータの量を削減するための方法が開発されてきた。特徴マッチングをさらに加速するための方法が、局所性鋭敏型ハッシュ（ＬＳＨ）と呼ばれ、これは、近似最近傍（ＡＮＮ）探索を行うために使用される。
【０００５】
しかしながら、ＳＬＡＭにおいては、再位置特定を実時間で行うことが極めて重要であり、処理すべき膨大なデータ量に起因して、先行技術の方法は満足のいく効率を提供していない。
【発明の概要】
【０００６】
現在、上述の問題を少なくとも軽減する、改良型の方法およびこの方法を実装する技術的設備が発明されている。該発明のさまざまな態様には、独立クレーム中に記載のことを特徴とする方法、装置およびコンピュータ・プログラムが含まれる。本発明のさまざまな実施形態が、従属クレームの中で開示されている。
【０００７】
第１の態様によると、本発明に係る方法は、オブジェクトについての３次元（３Ｄ）ポイント・クラウドを取得すること、オブジェクトについての２Ｄ画像内の特徴ポイントについてバイナリ特徴記述子を取得すること、各特徴ポイントについての複数の指標値を、対応するバイナリ特徴記述子の多重ビットとして割り当てること、データベース画像の複数のハッシュ・キー・テーブルのテーブル・エントリ内にバイナリ特徴記述子を格納すること、クエリ画像内の特徴ポイントのためのクエリ・バイナリ特徴記述子を取得すること、データベース画像のバイナリ特徴記述子に対してクエリ・バイナリ特徴記述子をマッチングすること、マッチしたデータベース画像のハッシュ・キーの１ビットを再選択することと、データベース画像のハッシュ・キー・テーブルのテーブル・エントリ内の特徴ポイントを再指標付けすること、という考え方に基づいている。
【０００８】
一実施形態によると、この方法は、テーブル・エントリのサイズの均一性およびマッチした特徴対のコリジョン率を定義するコスト関数が最小化されるように、マッチしたデータベース画像のハッシュ・キーの前記１ビットを再選択するステップ、をさらに含む。
【０００９】
一実施形態によると、前記コスト関数はＣ＝λ（１−ｐc）＋１／（１−ｕ’）であり、式中λは予め設定された重みであり、ｐcは、２つのマッチした特徴が、あるビットにおいて一致する確率であり、ｕ’はバイナリ特徴記述子に対してクエリ・バイナリ特徴記述子をマッチングするための線形探索における時間短縮因子である。
【００１０】
一実施形態によると、各特徴ポイントについての指標値の前記多重ビットは、対応するバイナリ特徴記述子から無作為に選択される。
【００１１】
一実施形態によると、クエリ・バイナリ特徴記述子は、近似最近傍（ＡＮＮ）探索を用いてデータベース画像のバイナリ特徴記述子にマッチングされる。
【００１２】
一実施形態によると、該方法は、ハッシュ・キーのための前記１ビットを、特徴ポイントの無作為に編成されたサブセット内で再選択するステップを含む。
【００１３】
一実施形態によると、該方法は、新規のクエリ画像が取得された場合に、ハッシュ・キーの第１の半分の中から前記１ビットを再選択するステップと、次のクエリ画像が取得された場合に、ハッシュ・キーの第２の半分の中から前記１ビットを再選択するステップと、をさらに含む。
【００１４】
第２の態様によると、少なくとも１つのプロセッサ、コンピュータ・プログラム・コードを含むメモリを備えた装置において、メモリおよびコンピュータ・プログラム・コードは、少なくとも１つのプロセッサを用いて、装置に、少なくとも、オブジェクトについての３次元（３Ｄ）ポイント・クラウドを取得させ、オブジェクトについての２Ｄ画像内の特徴ポイントについてバイナリ特徴記述子を取得させ、各特徴ポイントについての複数の指標値を、対応するバイナリ特徴記述子の多重ビットとして割り当てさせ、データベース画像の複数のハッシュ・キー・テーブルのテーブル・エントリ内にバイナリ特徴記述子を格納させ、クエリ画像内の特徴ポイントのためのクエリ・バイナリ特徴記述子を取得させ、データベース画像のバイナリ特徴記述子に対してクエリ・バイナリ特徴記述子をマッチングさせ、マッチしたデータベース画像のハッシュ・キーの１ビットを再選択させ、データベース画像のハッシュ・キー・テーブルのテーブル・エントリ内の特徴ポイントを再指標付けさせる、ように構成されている装置が提供されている。
【００１５】
第３の態様によると、プロセッサにより実行された場合に、装置に、オブジェクトについての３次元（３Ｄ）ポイント・クラウドを取得するステップと、オブジェクトについての２Ｄ画像内の特徴ポイントについてバイナリ特徴記述子を取得するステップと、各特徴ポイントについての複数の指標値を、対応するバイナリ特徴記述子の多重ビットとして割り当てるステップと、データベース画像の複数のハッシュ・キー・テーブルのテーブル・エントリ内にバイナリ特徴記述子を格納するステップと、クエリ画像内の特徴ポイントのためのクエリ・バイナリ特徴記述子を取得するステップと、データベース画像のバイナリ特徴記述子に対してクエリ・バイナリ特徴記述子をマッチングするステップと、マッチしたデータベース画像のハッシュ・キーの１ビットを再選択するステップと、データベース画像のハッシュ・キー・テーブルのテーブル・エントリ内の特徴ポイントを再指標付けするステップと、を行わせるコードが、前記装置による使用のために上に記載されているコンピュータ可読記憶媒体が提供されている。
【００１６】
本発明のこれらのおよび他の態様およびそれらに関係する実施形態は、さらに以下で示される実施形態の詳細な開示を考慮して明白になるものである。
【００１７】
以下では、添付図面を参照しながら、本発明のさまざまな実施形態について説明する。
【図面の簡単な説明】
【００１８】
【図１】一実施形態に係る３Ｄポイント・クラウド解析プロセスにおいて使用されるのに好適なコンピュータ・グラフィクス・システムを示す。
【図２】バイナリ特徴ベースのマッチング方法の一例を示す。
【図３】データベース特徴Ｆiを指標付けし、ハッシュ・キー・テーブル内にバイナリ特徴記述子を格納するための一実施例を示す。
【図４】本発明の一実施形態に係る、ハッシュ・キー構築プロセスについての流れ図を示す。
【図５ａ】本発明の一実施形態にしたがって実施された実験におけるＡＮＮ探索効率についてのグラフを示す。
【図５ｂ】本発明の一実施形態にしたがって実施された実験におけるＡＮＮ探索効率についてのグラフを示す。
【図５ｃ】本発明の一実施形態にしたがって実施された実験におけるＡＮＮ探索効率についてのグラフを示す。
【図６ａ】本発明の一実施形態にしたがって実施された実験における異なるパラメータ設定値を用いたＡＮＮ探索結果についてのグラフを示す。
【図６ｂ】本発明の一実施形態にしたがって実施された実験における異なるパラメータ設定値を用いたＡＮＮ探索結果についてのグラフを示す。
【図７】本発明の一実施形態にしたがって実施された実験における再位置特定精度のテーブルを示す。
【発明を実施するための形態】
【００１９】
図１は、例えば一実施形態に係る３Ｄポイント・クラウド解析プロセスなどの画像処理において使用するのに好適であるコンピュータ・グラフィクス・システムを示す。コンピュータ・グラフィクス・システムの一般化された構造について、システムの機能ブロックにしたがって説明する。当業者にとっては、複数の機能性を単一の物理的デバイスを用いて実施できるということは明白であり、例えば、全ての計算は、所望される場合、単一のプロセッサ中で行うことができる。図１の実施例に係る装置のデータ処理システムは、全てデータ・バス１１２を介して互いに接続されている主処理ユニット１００、メモリ１０２、記憶デバイス１０４、入力デバイス１０６、出力デバイス１０８およびグラフィクス・サブシステム１１０を含む。
【００２０】
主処理ユニット１００は、データ処理システムの内部でデータを処理するように配置された従来の処理ユニットである。メモリ１０２、記憶デバイス１０４、入力デバイス１０６および出力デバイス１０８は、当業者によって認知されている従来の構成要素である。メモリ１０２および記憶デバイス１０４は、データ処理システム１００の内部でデータを格納する。例えば３Ｄポイント・クラウド解析システムを実装するために、メモリ１０２内にコンピュータ・プログラム・コードが存在する。入力デバイス１０６は、システム内にデータを入力する一方、出力デバイス１０８はデータ処理システムからデータを受信しそのデータを例えばディスプレイに転送する。データ・バス１１２は、従来のデータ・バスであり、単一の線として示されているものの、プロセッサ・バス、ＰＣＩバス、グラフィカル・バスおよびＩＳＡバスの組合せであることができる。したがって、当業者であれば、装置がコンピュータ・デバイス、パーソナル・コンピュータ、サーバー・コンピュータ、モバイル・フォン、スマート・フォンまたはインターネット・アクセス・デバイス、例えばインターネット・タブレット・コンピュータなどの任意の従来のデータ処理デバイスであることができるということを容易に理解する。一実施形態に係る３Ｄポイント・クラウド解析プロセスおよび入力データを取得するための手段について、以下でさらに説明する。
【００２１】
異なる実施形態は、異なる要素中で異なる部分を実施できるようにする、ということを理解する必要がある。例えば、１つ以上の処理デバイス内、例えば、完全に１つのコンピュータ・デバイス内または１つのサーバー・デバイス内で、または多数のユーザー・デバイスを横断して、３Ｄポイント・クラウド解析のさまざまなプロセスを実施することができる。３Ｄポイント・クラウド解析プロセスの要素は、１つのデバイス内に存在するかまたは、上述のようにデバイスがいわゆるクラウドを形成するように複数のデバイスを横断して分散されたソフトウェア構成要素として実装されることができる。
【００２２】
３Ｄポイント・クラウドは、さまざまな画像処理およびコンピュータ・ビジョン・アプリケーションにおいて使用される。３Ｄポイント・クラウドは、典型的にオブジェクトの外部表面を表現する３Ｄ座標系内のデータ・ポイントのセットである。３Ｄポイント・クラウドは、３Ｄスキャナーなどの３Ｄ捕捉デバイスにより取得可能である。オブジェクトの表面上で多数の点が測定され、取得されたポイント・クラウドをファイル内に格納することができる。
【００２３】
３Ｄポイント・クラウドを取得するためのさまざまな検知方法が開発されてきた。ストラクチャ・フロム・モーション（ＳＦＭ）では、観察者および／または観察すべきオブジェクトが互いとの関係において運動する２次元画像シーケンスから、３次元構造が推定される。取得した幾何モデルは、３Ｄポイント・クラウドとして記憶される。
【００２４】
光検出と測距（ＬｉＤＡＲ）法においては、レーザー・ビーム（例えば紫外線、可視光線または近赤外線）でオブジェクトを照射し反射光を解析することによって、距離が測定される。結果としていられたデータは、ポイント・クラウドとして記憶される。ＬｉＤＡＲポイント・クラウドは、頂点を３Ｄベクトルにより定義される平面パッチにより表現できる、３次元座標系内の頂点のセットとみなすことができる。
【００２５】
コンピュータ・ビジョン・アプリケーションのためには、３Ｄポイントは典型的に、オブジェクトの２Ｄ画像の認識された特徴に対してマッピングされる。３Ｄポイント・クラウドのＳＬＡＭ（位置特定およびマッピングを同時に行うこと）は、ロボット工学およびコンピュータ・ビジョンの両方において、広範に研究されてきた。ＳＬＡＭとは、未知の環境のマップを更新すると同時にその内部で観察者を位置特定する問題を意味する。ＳＬＡＭシステムは、さまざまな方法で実装可能であるが、基本的には、背景マッピング・プロセスと前景追跡プロセスとを含むものとみなすことができる。
【００２６】
マッピング・プロセスは、映像シーケンスからキーフレームを収集し、環境のマップを構築するために、例えばストラクチャ・フロム・モーション（ＳＦＭ）プロセスを行う。このプロセスは、増分的に実施することができる。新しいキーフレームが挿入された場合、最初にコーナーの特徴ポイントを探索することができる。本明細書においては、例えば、コーナー点を抽出するためにＦＡＳＴ（加速化断片試験による特徴抽出）法を使用することができる。コーナーのいくつかは、旧３Ｄポイントの観察事実として識別することができ、一方、残りのコーナーは、新しい３Ｄポイントを三角測量するため、最も近いキーフレーム内のコーナーに対しマッチングされる。
【００２７】
マッピング・プロセスにおいて、処理すべきデータの量を削減するために、バイナリ特徴を取得することができる。図２は、１つの特徴ポイント２１０を有するクエリ画像２００が示されている、バイナリ特徴に基づくマッチング方法の一実施例を例示する。クエリ画像２００から、バイナリ特徴記述子が取得される。バイナリ特徴記述子は、特徴ポイント２１０の周囲のパッチについてのバイナリ・テストによって取得されるビット・ストリングである。「パッチ」なる用語は、１つの画素の周囲の部域を意味するために使用される。画素は、そのｘおよびｙ座標により定義される部域の中心画素であることができ、パッチは典型的に、複数の、可能な場合には全ての、隣接画素を含む。パッチの適切なサイズを、各特徴ポイントについて定義することもできる。
【００２８】
映像シーケンスから、データベース画像として一定数のキーフレームを選択することができる。データベース画像のために、例えばＳＦＭアプローチを用いて、データベース画像内の特徴ポイントトラックから３Ｄポイントを再構成することができる。まず、再構成された３Ｄポイントと結びつけられるデータベース特徴ポイントについて、バイナリ特徴記述子が抽出される。「データベース特徴ポイント」は、データベース画像から抽出される全ての特徴ポイントのサブセットである。いずれの３Ｄポイントとも結びつけることのできない特徴ポイントは、データベース特徴ポイントとして含まれない。各３Ｄポイントを多数の画像（視点）からビューできることから、多くの場合、同じ３Ｄポイントと結びつけられた多数の画像特徴ポイント（すなわち画像パッチ）が存在する。
【００２９】
データベース特徴ポイントは、好ましくは、特徴ポイントのその後の探索を容易にするために、指標付けされる。例えば、実質的に全てのデータベース特徴ポイントを指標付けするために、多数の無作為化ツリーをトレーニングすることができる。トレーニング・プロセスの後、データベース特徴ポイントおよびその指標を葉ノード内に格納することができる。
【００３０】
カメラ姿勢推定に使用される画像（「クエリ画像」と呼ばれる）が、その結果、処理される。クエリ画像については、クエリ画像２００内の特徴ポイントのための削減されたバイナリ特徴記述子（図２、２１０）が抽出される。「クエリ特徴ポイント」は、クエリ画像から抽出される全ての特徴ポイントのサブセットである。クエリ画像の特徴ポイントは、１−ｎ個のツリーの葉Ｌ＿１st〜Ｌ＿ｎthに付けられる（図２）。クエリ特徴ポイントを、ツリーの葉の上に、そのバイナリ形態により指標付けすることができる。
【００３１】
クエリ特徴ポイントは、一連の２Ｄ−３Ｄ対応を有するために、データベース特徴ポイントに対してマッチングされる。図２は単一のクエリ特徴ポイント２１０をデータベース特徴ポイントとマッチングするプロセスの一実施例を示す。クエリ画像のカメラ姿勢は、結果として得られた２Ｄ−３Ｄ対応を通して推定される。
【００３２】
追跡プロセスは、マップ内の３Ｄポイントを追跡することによって各フレームのカメラ姿勢を推定する。連続的カメラ・モーションの仮定下では、３Ｄポイントの観察事実を、その予測された場所の周囲で探索することができる。ひとたび観察事実が発見されたならば、すなわち３Ｄ−２Ｄ対応が確立されたならば、例えば非線形最適化ルーチンを使用することにより、カメラ姿勢を自明のものとして推定することができる。追跡プロセス中、例えば、照明の突然の変化、完全閉塞または極端なモーションぶれに起因して、追跡の失敗が発生する可能性がある。このような場合には、カメラ姿勢を再推定し追跡プロセスを再開させるために、再位置特定・プロセスを実施することができる。
【００３３】
再位置特定の目的は、追跡の失敗後、画像のカメラ姿勢を推定することにある。追跡プロセスの場合と同様に、再位置特定における中核となる問題も、３Ｄポイントの観察事実を見出すことにあるが、ただしこの場合、この観察事実は、先のフレームのカメラ姿勢からはもはや予測され得ない。観察事実がひとたび見出された場合、カメラ姿勢は、例えばＲＡＮＳＡＣ（ＲＡＮｄｏｍ  ＳＡｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ）および／またはＰｅｒｓｐｅｃｔｉｖｅ−ｎ−Ｐｏｉｎｔｓアルゴリズムなどにより、推定可能である。
【００３４】
３Ｄポイントの観察事実の取得は、特徴マッチングの問題として扱かわれる。例えば、３Ｄポイントの観察事実がキーフレーム内で見出された場合にはつねに、この観察事実におけるバイナリ記述子を抽出することができる。その結果、各々の３Ｄポイントは、データベース特徴と呼ばれるバイナリ記述子のセットに対応する。再位置特定されている画像の中で、ＦＡＳＴコーナーは、そのバイナリ記述子と共にクエリ特徴と呼ばれ、最初に抽出されることができる。次に、各クエリの上位２つの最近傍を、データベース特徴の中から探索することができ、充分に類似している場合には、最近傍をマッチングとみなすことができる。
【００３５】
特徴マッピングをさらに加速するための方法は、局所性鋭敏型ハッシュ（ＬＳＨ）と呼ばれ、これは近似最近傍（ＡＮＮ）探索を行うために使用される。ＬＳＨは、特徴を指標付けするためにハッシュ・キーを使用する。ＬＳＨは、各キーの下の特徴に対して指標値を割り当てる。ＡＮＮ探索を行う場合、データベース特徴は多数のハッシュ・テーブル内に格納される。各ハッシュ・テーブルは、１つのハッシュ・キーに対応する。データベース特徴が中に格納されなければならない指定されたテーブル・エントリすなわちハッシュ・バケットは、指標値によって決定される。クエリ特徴を仮定すると、指標値は最初に割り当てられ、対応するバケットは、データベース特徴と同じ方法で見出される。次に、近似最近傍を読み出しするために、これらのバケット内のデータベース特徴の中から、線形探索が行なわれる。バイナリ特徴については、ハッシュ・キーは単に、記述子ビットから無作為に選択されたビット・セットである。結果として、これらのビットにおいて値を連結することにより、バイナリコードを特徴に割り当てることができ、特徴の指標値は、バイナリコードにより変換された整数である。
【００３６】
図３は、いかにしてデータベース特徴Ｆiが指標付けされハッシュ・テーブル内に格納されるかについての単純な実施例を示す。データベース特徴Ｆｉは、複数の無作為に選択されたビット対が指標値として選択される記述子ビット・ストリングを含む。例えば、第１のビット対００が、ハッシュ・テーブル１のための指標として無作為に選択される。ハッシュ・テーブルは、４つのテーブル・エントリ、すなわちハッシュ・バケット０、１、２および３を含む。指標の値は、どのテーブル・エントリ内にデータベース特徴が格納されるかを決定する。ハッシュ・テーブル１のための指標としてのビット対００は、値０を表わし、こうしてデータベース特徴は、第１のハッシュ・テーブル内のバケット０の中に格納される。値３を表わす第２のビット対１１は、ハッシュ・テーブル２のための指標として無作為に選択される。結果として、データベース特徴は、第２のハッシュ・テーブルのバケット３の中に格納される。同様にして、値１を表わすｎ番目のビット対０１が、ハッシュ・テーブルｎのための指標として無作為に選択され、したがって、データベース特徴は、ｎ番目のハッシュ・テーブルのバケット１の中に格納される。
【００３７】
上述の実施例ではハッシュ・キーとして１ビット対（すなわち２ビット）が使用されているものの、３、４、５個などの任意の数の多重ビットをハッシュ・キー長として使用できる、という点を指摘しておかなければならない。
【００３８】
しかしながら、上述の配置がかなり高速で信頼性の高いリロケーション・プロシージャを提供するとしても、この配置には、リロケーション・プロシージャに幾分かの非効率性を本質的に導入して、その実時間での実施を妨げる特徴が関与する。例えば、指標付けプロセスにおける、つねに変化するデータベース特徴セットは、システムに幾分かのレイテンシを導入する。
【００３９】
以下では、純粋な無作為性の代りにオンライン学習プロセスを利用する、ハッシュ・キーを構築するための新規のアプローチが提示される。
【００４０】
実施形態に係る方法は、図４に例示されている。この方法においては、１つのオブジェクトを中心とする３次元（３Ｄ）ポイント・クラウドが取得され（４００）、同じオブジェクトを中心とする２Ｄ画像内の特徴ポイントについてのバイナリ特徴記述子も同様に取得される（４０２）。各特徴ポイントについての複数の指標値が、対応するバイナリ特徴記述子の多重ビットとして割り当てられ（４０４）、各特徴ポイントについての各指標値が、データベース画像のハッシュ・キー・テーブルのテーブル・エントリ内に格納される（４０６）。次に、クエリ画像について、クエリ画像内の特徴ポイントのためのクエリ・バイナリ特徴記述子が取得される（４０８）。クエリ・バイナリ特徴記述子は、データベース画像のバイナリ特徴記述子に対してマッピングされ（４１０）、その後、マッチしたデータベース画像のハッシュ・キーの１ビットが再選択され（４１２）、特徴ポイントは、データベース画像のハッシュ・キー・テーブルのテーブル・エントリ内に再度指標付けされる。
【００４１】
換言すると、システム内のレイテンシを軽減しデータベース特徴の絶えず変化するセットをハンドリングするために、ビット選択はＳＬＡＭプロセスへと分散される。最初に、各々のハッシュ・キーを編成しているビットは、ＬＳＨの場合と同様に無作為に選択される。新しいキーフレームが挿入されデータベース特徴のセットが更新された場合にはつねに、コスト関数を最小化するために、各ハッシュ・キーの１ビットが再度選択される。次に、データベース特徴が、新規のハッシュ・キーを用いて再度指標付けされる。
【００４２】
実施形態に内在する考慮事項は、ＡＮＮ探索のための指標付けスキームの効率と密に関係する因子が２つ存在するという事実に由来する。すなわちバケット・サイズの分布および、マッチした特徴対のコリジョン率である。バケット・サイズは、バケット内に格納されたデータベース特徴の数を標示する。通常、バケット・サイズが均一であればあるほど、ＡＮＮ探索は速くなることは、「Ｏｒｂ：Ａｎ  ｅｆｆｉｃｉｅｎｔ  ａｌｔｅｒｎａｔｉｖｅ  ｔｏ  ｓｉｆｔ  ｏｒ  ｓｕｒｆ」ｂｙ  Ｒｕｂｌｅｅ，Ｅ．，Ｒａｂａｕｄ，Ｖ．，Ｋｏｎｏｌｉｇｅ，Ｋ．，Ｂｒａｄｓｋｉ，Ｇ，ｉｎ  Ｐｒｏｃ．ＩＥＥＥ  Ｉｎｔ．Ｃｏｎｆ．Ｃｏｍｐｕｔｅｒ  Ｖｉｓｉｏｎ（２０１１）．ｐｐ．２５６４〜２５７１中で示されている。マッチした特徴対のコリジョン率は、２つのマッチした特徴が同じバケット内でコリジョンを起こす確率である。コリジョン率が高くなれば、探索精度は高くなる。両方の因子を考慮した上で、実施形態に係る指標付け方法は、ＡＮＮ探索を高速かつ高精度で行うことができるように、均一なバケットおよび高いコリジョン率を達成することを目的とする。
【００４３】
一実施形態によると、ハッシュ・キーを編成しているビットは、対応するコスト関数を最小化するように選択される。
【００４４】
バケット・サイズの均一性
ハッシュ・テーブルの正規化されたバケット・サイズを、Σｓn＝１という条件で、Ｎをバケットの総数として、｛ｓn、ｎ＝１、２、．．．、Ｎ｝と仮定する。このとき、バケット・サイズが均一である程度は、以下の式によって表現することができる：
【数１】
0006457648.tif 000002
【００４５】
ｕが小さくなればなるほど、バケット・サイズの均一性は高くなる。この式は、バケット・サイズの均一性とＡＮＮ探索の速度の間の関係と充分両立する。バケット内の線形探索の時間コストがＡＮＮ探索プロセスで最も重要であることから、クエリ特徴がデータベース特徴と類似の分散を有するという仮定の下で、時間コストは、Σn=1Nｓn2と正比例する。一度に１ビットだけが再選択されるため、均一性は同様に、次の形で表現することができる：
【数２】
0006457648.tif 000003
式中、｛ｓm、ｍ＝１、２、．．．、Ｎ／２｝は一定であり、不変ビットからなるキーでデータベース特徴を指標付けすることにより取得されるハッシュ・テーブルの正規化されたバケット・サイズを表わす。ｕ’の値が［０．５  １］に属することを確認することができる。ｕ’＝０．５の値は、ハッシュ・キー内に新たに選択されたビットがある状態では、ハッシュ・キー内に不変ビットのみの場合と比べて線形探索の時間コストを２分の１に削減することができるということを標示している。同じく、ｕ’＝１の値は、新たに選択されたビットが時間の節約を全くもたらさないことを標示する。コスト関数中、均一性に関する項は、小さいｕ’を促し、ｕ’＝１という状況を回避するために、１／（１−ｕ’）として設定される。
【００４６】
コリジョン率
マッチした特徴対のコリジョン率は、実際にはハッシュ・キーの全てのビットにおいて２つのマッチした特徴が互いに一致する確率である。あるビットにおいて２つのマッチした特徴が一致する確率をそのビットの安定性ｐcと呼ぶことにすると、欲張りアルゴリズムの原則にしたがって、ハッシュ・キーのためのビットを選択するとき、最も安定したビットが好まれる。こうして、コリジョン率についてのコスト項は、単純に１−ｐcとして設定される。３Ｄポイントの特徴は実際には互いのマッチングであることから、マッチした特徴対を、データベース内で容易に取得することができ、これらの対について統計を行うことによって、ｐcを推定することができる。
【００４７】
一実施形態によると、最小化すべきコスト関数Ｃは、以下のように表わされる：
Ｃ＝λ（１−ｐc）＋１／（１−ｕ’）    （３）
式中λは、予め設定された重みである。
【００４８】
ハッシュ・キーのために１つのビットを選択するプロセスは、以下のアルゴリズムにしたがって提示することができ、ここでハッシュ・キーはＨK＝｛ｂs1、ｂs2．．．、ｂsk｝という式で表わされ、式中ｂskは、記述子ｓkε［１Ｄ］のＳk番目のビットであり、Ｄは記述子の長さである。４０の乱数｛ｒ1、ｒ2、．．．、ｒ40｝は、単なる一例として示されており、乱数の実際の量は、選択された実装に応じて変動することができる。
【００４９】
入力：ｂskが再選択されている、ＨK＝｛ｂs1、．．．、ｂsk、．．．、ｂsK｝、Ｆ、全てのデータベース特徴
開始
ＨKからｂskを除去してＨK’＝｛ｂs1、．．．、ｂsK｝を得る、
ＨK’を用いてＦを指標付けする、
バケット・サイズ｛Ｓm、ｍ＝１、２、．．．、Ｎ／２｝を計数する、
４０の乱数｛ｒ1、ｒ2．．．、ｒ40｝ｒiε［１Ｄ］を生成する、
各ｂriの安定性を計算する、
ｉ＝１、ｉ≦４０、ｉ＋＋について、以下のことを行う。
ｂriでＨK内のｂskを置換してＨK’’を得る、
ＨK’’を用いてＦを指標付けする、
コスト関数Ｃを計算する、
終了
Ｃを最小化するように、｛ｒi｝からｒ*を選択する、
ｂskをＨK内のｂr*で置換する、
終了
出力：ＨK＝｛ｂs1、．．．、；ｂr*、．．．；ｂsK｝
【００５０】
アルゴリズムからわかるように、ビット選択プロセスの時間コストは、データベース特徴の数、すなわちＦ内の要素の数と線形である。
【００５１】
一実施形態によると、アルゴリズムをスケーラブルにするために、ハッシュ・キーのために１ビットを選択するプロセスにおいて、Ｆ内の要素の無作為に編成されたサブセットを使用することができる。こうして、「良いビット」、すなわち均一のバケット・サイズおよび高いコリジョン率を生成するビットを発見する能力を保持する一方で、ビット選択プロセスのための恒常な時間コストを提供することができる。
【００５２】
一実施形態によると、トレーニング時間をさらに短縮するため、新しいキーフレームが挿入された場合、半分のハッシュ・キー上で、ビット選択プロセスを行うことができ、２つの半分が順次選択される。こうして、良いビットの発見は減速される場合があるが、システムレイテンシは効果的に短縮される。
【００５３】
ＡＮＮ探索に対する上述の指標付け方法の効率性および再位置特定プロセスの性能を評価するために、さまざまな実験が実施されてきた。１つの実験においては、建物の周りで１２，８２１個のフレームを格納する長い映像Ｖ１が撮られ、そこから、ＳＬＡＭプロセス中に２９３個のキーフレームが抽出され、１７５，２０７個のバイナリ記述子と共に３７，６４１個の３Ｄポイントが取得された。
【００５４】
本明細書中、学習されたＬＳＨと呼ばれている上述の指標付け方法の利点を実証するために、該方法のＡＮＮ探索性能は、以下のセットアップで、当初のＬＳＨの性能と比較される：
−  当初のＬＳＨ。実験では、ハッシュ・テーブル数の３つの構成、すなわちそれぞれ２、６および１０が使用される。各構成において、ハッシュ・キーの長さは、１７から１３の範囲にあり、結果として異なる探索精度およびタイミングをもたらす。
−  学習されたＬＳＨ。ハッシュ・テーブルの数およびハッシュ・キーの長さの構成は、当初のＬＳＨと同一である。学習されたＬＳＨ内の各ハッシュ・キーは、当初のＬＳＨ内のハッシュ・キーと初めは同じであり、ＳＬＡＭプロセス中変更される。ＡＮＮ探索のために使用される最後のハッシュ・キーは、２９３のキーフレーム全てから学習されたハッシュ・キーである。
【００５５】
本明細書において、探索精度は、ＡＮＮ探索の成功率として定義されている。探索時間は、全ＡＮＮ探索プロセスの時間コストである。図５ａ、５ｂおよび５ｃは、それぞれ２、６、１０個のハッシュ・テーブルを使用することによって取得した探索精度および探索タイミングに関するＡＮＮ探索結果と示す。これらの構成下で、学習されたＬＳＨのＡＮＮ探索性能が、当初のＬＳＨに比べて一貫して改善されていることが分かる。学習されたＬＳＨを使用すると、当初のＬＳＨを使用する場合よりも、同じ探索精度に達するのに要する時間が少ない。例えば、２つのハッシュ・テーブルを使用した場合、時間コストをおよそ半分に削減することができる。これらの結果は、ビット選択プロセスが有効であることを標示している。より優れたハッシュ・キーは、無作為に生成されるよりもむしろ、ＳＬＡＭプロセスにおいて収集された特徴を活用することによって学習され得る。
【００５６】
学習されたＬＳＨの探索効率の進展を実証するために、以下のように別の実験が実施された。ビット選択プロセスは、ｋ個のキーフレームが挿入された後に停止され、結果として得られたハッシュ・キーを使用して、上述のデータセット中のクエリ特徴についてＡＮＮ探索が実施された。結果は、図６ａに示されており、この図から、探索効率がおおよそｋの増加につれて増大することが分かる。このことは、ｋの増加に伴って、良いビットを見出す確率を増大させるためにより多くのビット選択プロセスが行なわれ、より広いトレーニング・データ範囲、すなわちより多数のデータベース特徴を同様に利用可能であることから、合理的である。図６ａからは、同様に、ｋが、例えば７０といった一定の程度まで増大すると、性能はそれ以上改善しない、ということも分かる。この結果は、エンドレス学習が必要でなく、充分なビット選択プロセスが実施された後に学習を停止できるということを示唆している。
【００５７】
コスト関数（式３）中のパラメータλについて適切な値を決定するために、図６ｂは、指標付け方法の効率に対するその影響を示す。例えば０などの過度に小さい値または例えば２０などの過度に大きい値のいずれも、探索効率を劣化させることが分かる。したがって、１２などの適度な大きさの値が好まれる。
【００５８】
上述の再位置特定プロセスの性能を評価するために、２つの映像セグメントの各フレームを再位置特定する目的でこれらのセグメントを実行する実験がセットアップされた。第１の映像セグメントは、映像セグメントＶ１からの８０００フレームを格納する。第２の映像セグメントＶ２は、事務デスク上でカメラを移動させることによって撮られたものであり、１０６３フレームを格納する。第２の映像セグメントに関与するマップは、別の映像上でＳＬＡＭを実行することによって構築されたものであり、そこから３１のキーフレームが抽出され、４１７３の３Ｄポイントが、２０８４６のデータベース特徴と共に取得された。
【００５９】
実験では、３Ｄ−２Ｄ対応を確立するプロセスにおけるＡＮＮ探索のために、学習されたＬＳＨが使用される。比較のため、当初のＬＳＨも同様に使用される。Ｖ１では、当初のＬＳＨのおよび学習されたＬＳＨの両方が、キー長４で１０個のハッシュ・テーブルを有し、学習されたＬＳＨ内のハッシュ・キーは、全てのキーフレームから学習される。Ｖ２では、当初のＬＳＨは、キー長１４で１０個のハッシュ・テーブルを有し、学習されたＬＳＨは、１３というキー長で１０個のハッシュ・テーブルを有する。ここでもまた、学習されたＬＳＨ内のハッシュ・キーは、全てのキーフレームから学習される。
【００６０】
図７中のテーブルは、ＲＡＮＳＡＣにおける無作為性の効果を軽減するため５回の反復にわたり平均された再位置特定結果をまとめている。Ｖ１において、８０００フレームのうち７８５９フレーム、すなわち９８．２％が、フレーム・レートの速度で首尾よく再位置特定されることが示されており、これは、大きなマップのための再位置特定・モジュールの優れたスケーラビリティを実証するものである。その上、当初のＬＳＨに比べ学習されたＬＳＨの効率がより高いものであることに起因して、ＡＮＮ探索の時間コストを４２％削減することができ、わずかに多くのすなわち０．３％のフレームが首尾よく再位置特定され得る。Ｖ２では、クエリ・フレームとキーフレームの間の視点差はＶ１の場合よりも大きく、こうして、より低い登録レート、すなわち８９．６％が取得される。Ｖ２中のマップは比較的小さいことから、学習されたＬＳＨを使用することによる時間コストの節約は、Ｖ１の場合ほど顕著なものではない。ただし、２．４％という登録レートの改善は、ここでさらに注目に値する。この改善は、同様に、学習されたＬＳＨのより高い効率によるものとすべきであり、同じ時間をかけても、学習されたＬＳＨを使用すると、当初のＬＳＨを使用する場合よりも高い探索精度が生み出される。
【００６１】
当業者であれば、いくつかの実施形態が互いに代替案にすぎないことが明示的または黙示的に述べられているのでないかぎり、上述の実施形態のうちの任意のものを１つ以上の他の実施形態との組合せとして実装できるということを認識するものである。
【００６２】
実験により確認される通り、さまざまな実施形態は、技術的現状に比べた利点を提供できる。ハッシュ・キーは、均一なハッシュ・バケットおよび高いコリジョン率を取得することを目的として構築され、こうして該方法は、ＬＳＨに比べ近似最近傍探索に対しより効率の高いものになる。ＳＬＡＭ（位置特定およびマッピングを同時に行うこと）プロセス内にオンライン学習を分散させることにより、該方法をＳＬＡＭ再位置特定にうまく適用することができる。その上、実験は、マップ内に何万ものランドマークが存在する場合でも、カメラ姿勢を実時間で首尾よく回復できることを示している。
【００６３】
本発明のさまざまな実施形態は、メモリ内に存在し関連する装置に本発明を実施させるコンピュータ・プログラム・コードを用いて、実装可能である。例えば、装置は、データのハンドリング、受信および伝送のための回路および電子機器と、メモリ内のコンピュータ・プログラム・コードと、コンピュータ・プログラム・コードを実行した場合に、端末デバイスに一実施形態の特徴を実施させるプロセッサとを備えることができる。
【００６４】
本発明は、以上で提示された実施形態のみに限定されず、添付クレームの範囲内で修正可能であることは明白である。
【図１】
0006457648.tif 000004
【図２】
0006457648.tif 000005
【図３】
0006457648.tif 000006
【図４】
0006457648.tif 000007
【図５ａ】
0006457648.tif 000008
【図５ｂ】
0006457648.tif 000009
【図５ｃ】
0006457648.tif 000010
【図６ａ】
0006457648.tif 000011
【図６ｂ】
0006457648.tif 000012
【図７】
0006457648.tif 000013