(57)【要約】  ビデオストリーム内で観測されたシーン内のオブジェクトの面法線を解くためのシステムおよび方法が本明細書で説明される。システムおよび方法は、キーフレームのセットを生成するために、ビデオストリームサンプリングするステップと、キーフレームの各々の中のマップ点のセットに関する仮説面法線を生成するステップと、仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の対応するマップ点のパッチを第2のキーフレームの視点にワープさせるステップと、2個のキーフレーム内の各仮説面法線同士の間のワーピング誤差をスコア付けするステップと、第1のキーフレームと第2のキーフレームとの間で高いワーピング誤差を有する仮説面法線を廃棄するステップとを含み得る。
2016500890.tif 000002
【特許請求の範囲】
【請求項１】
ビデオストリーム内のオブジェクトの面法線を解くための方法であって、
キーフレームのセットを生成するために、前記ビデオストリームをサンプリングするステップと、
キーフレームの前記セット内の対応する画像点を選択するステップと、
2つ以上のキーフレーム内の前記対応する画像点を使用して、キーフレームの前記セットによって画像化されたシーン内に3D特徴点を生成するステップと、
前記3D特徴点に関する仮説面法線を生成するステップと、
前記仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の3D特徴点に対応する画像画素パッチを第2のキーフレームの視点にワープさせるステップと、
前記第1のキーフレームと前記第2のキーフレームとの間の各仮説面法線から生じるワーピング誤差をスコア付けするステップと、
前記第1のキーフレームと前記第2のキーフレームとの間で高いワーピング誤差をもたらす仮説面法線を廃棄するステップと
を含む、方法。
【請求項２】
廃棄されない仮説面法線を正確な推定としてマーキングするステップ
をさらに含む、請求項1に記載の方法。
【請求項３】
マーキングされた面法線の前記セットが面法線の事前定義された数以上であるかどうかを判断するステップと、
マーキングされた面法線の前記セットが面法線の前記事前定義された数未満であることを判断する際に、キーフレームの新しいセットに関して、前記ワーピング動作、前記スコア付け動作、および前記廃棄動作を繰り返すステップと
をさらに含む、請求項2に記載の方法。
【請求項４】
最小ワーピング誤差を有する仮説面法線を判断するステップ
をさらに含む、請求項3に記載の方法。
【請求項５】
前記最小ワーピング誤差を有する前記判断された仮説面法線を使用して、前記ビデオストリーム内のカメラ追跡およびオブジェクト追跡のうちの1つを実行するステップ
をさらに含む、請求項4に記載の方法。
【請求項６】
マーキングされた面法線の前記セットを使用して、前記ビデオストリーム内のカメラ追跡およびオブジェクト追跡のうちの1つを実行するステップ
をさらに含む、請求項4に記載の方法。
【請求項７】
複数のキーフレームに関する前記ワーピング誤差を合計するステップ
をさらに含む、請求項4に記載の方法。
【請求項８】
前記ワーピング誤差が正規化相互相関スコアに基づく、請求項1に記載の方法。
【請求項９】
事前定義された分離範囲内の基線を有する、ワーピングさせるための前記第1のキーフレームおよび前記第2のキーフレームを選択するステップ
をさらに含む、請求項1に記載の方法。
【請求項１０】
前記第1のキーフレームおよび前記第2のキーフレームが、前記ビデオストリーム内の非順次キーフレームである、請求項1に記載の方法。
【請求項１１】
機械によって実行されるとき、前記機械に、ビデオストリーム内のオブジェクトの面法線を解くための動作を実行させる命令を備えた非一時的機械可読媒体であって、前記命令が、
キーフレームのセットを生成するために、前記ビデオストリームをサンプリングすることと、
キーフレームの前記セット内の対応する画像点を選択することと、
2つ以上のキーフレーム内の前記対応する画像点を使用して、キーフレームの前記セットによって画像化されたシーン内に3D特徴点を生成することと、
3D特徴点の前記セットに関する仮説面法線を生成することと、
前記仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の3D特徴点に対応する画像画素パッチを第2のキーフレームの視点にワープさせることと、
前記第1のキーフレームと前記第2のキーフレームとの間の各仮説面法線から生じるワーピング誤差をスコア付けすることと、
前記第1のキーフレームと前記第2のキーフレームとの間で高いワーピング誤差をもたらす仮説面法線を廃棄することと
を含む、非一時的機械可読媒体。
【請求項１２】
前記命令が、
廃棄されない仮説面法線を正確な推定としてマーキングすること
をさらに含む、請求項11に記載の非一時的機械可読媒体。
【請求項１３】
前記命令が、
マーキングされた面法線の前記セットが面法線の事前定義された数以上であるかどうかを判断することと、
マーキングされた面法線の前記セットが面法線の前記事前定義された数未満であることを判断する際に、キーフレームの新しいセットに関して、前記ワーピング命令、前記スコア付け命令、および前記廃棄命令を繰り返すことと
をさらに含む、請求項12に記載の非一時的機械可読媒体。
【請求項１４】
前記命令が、
最小ワーピング誤差を有する仮説面法線を判断すること
をさらに含む、請求項13に記載の非一時的機械可読媒体。
【請求項１５】
前記命令が、
前記最小ワーピング誤差を有する前記判断された仮説面法線を使用して、前記ビデオストリーム内のカメラ追跡およびオブジェクト追跡のうちの1つを実行すること
をさらに含む、請求項14に記載の非一時的機械可読媒体。
【請求項１６】
前記命令が、
マーキングされた面法線の前記セットを使用して、前記ビデオストリーム内のカメラ追跡およびオブジェクト追跡のうちの1つを実行すること
をさらに含む、請求項14に記載の非一時的機械可読媒体。
【請求項１７】
前記命令が、
複数のキーフレームに関する前記ワーピング誤差を合計すること
をさらに含む、請求項14に記載の非一時的機械可読媒体。
【請求項１８】
前記ワーピング誤差が正規化相互相関スコアに基づく、請求項11に記載の非一時的機械可読媒体。
【請求項１９】
前記命令が、
事前定義された分離範囲内の基線を有する、ワーピングさせるための前記第1のキーフレームおよび前記第2のキーフレームを選択すること
をさらに含む、請求項11に記載の非一時的機械可読媒体。
【請求項２０】
前記第1のキーフレームおよび前記第2のキーフレームが、前記ビデオストリーム内の非順次キーフレームである、請求項11に記載の非一時的機械可読媒体。
【請求項２１】
ビデオストリーム内のオブジェクトの面法線を解くためのコンピューティングデバイスであって、
キーフレームのセットを生成するために、前記ビデオストリームをサンプリングするためのサンプリング手段と、
キーフレームの前記セット内の対応する画像点を選択して、2個以上のキーフレーム内の前記対応する画像点を使用して、キーフレームの前記セットによって画像化されたシーン内の3D特徴点を生成して、前記3D特徴点に関する仮説面法線を生成するための仮説手段と、
前記仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の3D特徴点に対応する画像画素パッチを第2のキーフレームの視点にワープさせるためのワーピング手段と、
前記第1のキーフレームと前記第2のキーフレームとの間の各仮説面法線から生じるワーピング誤差をスコア付けするためのスコア付け手段と、
前記第1のキーフレームと前記第2のキーフレームとの間で高いワーピング誤差をもたらす仮説面法線を廃棄するための廃棄手段と
を備える、コンピューティングデバイス。
【請求項２２】
廃棄されない仮説面法線を正確な推定としてマーキングするためのマーキング手段
をさらに含む、請求項21に記載のコンピューティングデバイス。
【請求項２３】
マーキングされた面法線の前記セットが面法線の事前定義された数以上であるかどうかを判断するための判断手段であって、マーキングされた面法線の前記セットが面法線の前記事前定義された数未満であることを判断する際には、(1)前記ワーピング手段が、キーフレームの新しい対の中の対応する3D特徴点の画像画素パッチをワープさせて、(2)前記スコア付け手段が、キーフレームの前記新しい対の中の各面法線同士の間のワーピング誤差をスコア付けして、(3)前記廃棄手段が、新しいキーフレームの前記対の中の高いワーピング誤差を有する仮説面法線を廃棄する、判断手段
をさらに備える、請求項22に記載のコンピューティングデバイス。
【請求項２４】
前記マーキング手段が、最小ワーピング誤差を有する仮説面法線をさらに判断する、請求項23に記載のコンピューティングデバイス。
【請求項２５】
マーキングされた仮説面法線の前記セットが、前記ビデオストリーム内のカメラ追跡およびオブジェクト追跡のうちの1つを実行するために使用される、請求項24に記載のコンピューティングデバイス。
【請求項２６】
前記最小ワーピング誤差を有する前記判断された仮説面法線が、前記ビデオストリーム内のカメラ追跡およびオブジェクト追跡のうちの1つを実行するために使用される、請求項24に記載のコンピューティングデバイス。
【請求項２７】
前記スコア付け手段が、複数のキーフレームに関する前記ワーピング誤差を合計する、請求項24に記載のコンピューティングデバイス。
【請求項２８】
前記ワーピング誤差が正規化相互相関スコアに基づく、請求項21に記載のコンピューティングデバイス。
【請求項２９】
事前定義された分離範囲内の基線を有する、ワーピングさせるための前記第1のキーフレームおよび前記第2のキーフレームを選択するための選択手段
をさらに備える、請求項21に記載のコンピューティングデバイス。
【請求項３０】
前記第1のキーフレームおよび前記第2のキーフレームが、前記ビデオストリーム内の非順次キーフレームである、請求項21に記載のコンピューティングデバイス。
【請求項３１】
ビデオストリーム内のオブジェクトの面法線を解くためのプロセッサを備えたコンピューティングデバイスであって、
前記ビデオストリームを捕捉するためのカメラと、
キーフレームのセットを生成するために、前記ビデオストリームをサンプリングするためのサンプリングユニット、
キーフレームの前記セット内の対応する画像点を選択して、2個以上のキーフレーム内の前記対応する画像点を使用して、キーフレームの前記セットによって画像化されたシーン内の3D特徴点を生成して、前記3D特徴点に関する仮説面法線を生成するための仮説ユニット、
前記仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の3D特徴点に対応する画像画素パッチを第2のキーフレームの視点にワープさせるためのワーピングユニット、
前記第1のキーフレームと前記第2のキーフレームとの間の各仮説面法線から生じるワーピング誤差をスコア付けするためのスコア付けユニット、および
前記第1のキーフレームと前記第2のキーフレームとの間で高いワーピング誤差をもたらす仮説面法線を廃棄するための廃棄ユニット
を備えた面法線ソルバーと
を備える、コンピューティングデバイス。
【請求項３２】
前記面法線ソルバーが、
廃棄されない仮説面法線を正確な推定としてマーキングするためのマーキングユニット
をさらに備える、請求項31に記載のコンピューティングデバイス。
【請求項３３】
前記面法線ソルバーが、
マーキングされた面法線の前記セットが面法線の事前定義された数以上であるかどうかを判断するための判断ユニットであって、マーキングされた面法線の前記セットが面法線の前記事前定義された数未満であることを判断する際には、(1)前記ワーピング手段が、キーフレームの新しい対の中の対応する3D特徴点の画像画素パッチをワープさせて、(2)前記スコア付け手段が、キーフレームの前記新しい対の中の各面法線同士の間のワーピング誤差をスコア付けして、(3)前記廃棄手段が、新しいキーフレームの前記対の中の高いワーピング誤差を有する仮説面法線を廃棄する、判断ユニット
をさらに備える、請求項32に記載のコンピューティングデバイス。
【請求項３４】
前記マーキングユニットが、最小ワーピング誤差を有する仮説面法線をさらに判断する、請求項33に記載のコンピューティングデバイス。
【請求項３５】
マーキングされた仮説面法線の前記セットが、前記ビデオストリーム内のカメラ追跡およびオブジェクト追跡のうちの1つを実行するために使用される、請求項34に記載のコンピューティングデバイス。
【請求項３６】
前記最小ワーピング誤差を有する前記判断された仮説面法線が、前記ビデオストリーム内のカメラ追跡およびオブジェクト追跡のうちの1つを実行するために使用される、請求項34に記載のコンピューティングデバイス。
【請求項３７】
前記スコア付けユニットが、複数のキーフレームに関する前記ワーピング誤差を合計する、請求項34に記載のコンピューティングデバイス。
【請求項３８】
前記ワーピング誤差が正規化相互相関スコアに基づく、請求項31に記載のコンピューティングデバイス。
【請求項３９】
前記面法線ソルバーが、
事前定義された分離範囲内の基線を有する、ワーピングさせるための前記第1のキーフレームおよび前記第2のキーフレームを選択するための選択ユニット
をさらに備える、請求項31に記載のコンピューティングデバイス。
【請求項４０】
前記第1のキーフレームおよび前記第2のキーフレームが、前記ビデオストリーム内の非順次キーフレームである、請求項31に記載のコンピューティングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で開示される主題は、一般に、マッピング技術および追跡技術に関するコンピュータビジョンアプリケーションならびに拡張現実(AR)アプリケーションなどのアプリケーションで使用されるシステム、方法、および装置に関する。詳細には、並列化可能な(parallelizable)アーキテクチャ内のキーフレームのセット内の仮説法線(hypothesis normals)を比較することによって、面法線を計算するためのシステムおよびプロセス。
【背景技術】
【０００２】
ゲームシステム、コンピュータビジョンシステム、および拡張現実システムなどのアプリケーションは、オブジェクトの正確かつ効率的な検出および追跡に依存する。未知の環境でカメラを追跡すること、またはカメラの前を移動する未知のオブジェクトを追跡することは、まず、その環境またはオブジェクトの外観および構造表現を構築することを必要とする。その後、入ってくる画像からの画像特徴を、キーフレームとして記憶可能な、特徴パッチの記憶された外観表現と整合させることによって、追跡を進めることができる。
【０００３】
過去のキーフレーム(第1のフレーム)からの特徴を現在のフレーム(第2のフレーム)に整合させるために、類似の程度に関して、過去のキーフレーム(第1のフレーム)内の特徴点位置を取り囲む局所的な外観またはピクセル強度(pixel intensity)が、その特徴が特定されると予測される現在のフレーム(第2のフレーム)内の候補領域内の局所的外観またはピクセル強度と比較される。類似の程度を定量化または測定するために一般的に使用される1つの方法は、過去のキーフレーム内の画素のウィンドウと現在のキーフレーム内の画素のウィンドウとの間の正規化相互相関(NCC)スコアの使用による。フレーム/画像の両方の中の特徴の正確な位置において、2個のフレーム/画像からの画素のウィンドウ同士の間のNCCスコアは高く、良好な類似性を示す。しかしながら、2個の画像のカメラポーズがまったく異なり、2個の画像内の特徴の外観に変化が存在するとき、特徴ウィンドウを直接比較することはできず、NCCスコアは低い。この状況では、第2の視点からの第2のフレーム内で見られるその特徴の外観に類似して見えるようにするには、第1のフレーム内の特徴位置を取り囲む画像領域を第2のフレームの画像領域の視点にワープさせなければならない。その環境の局所的なジオメトリまたは局所的な面法線は、2つの異なる視点からの幅広い基線整合のための、ある視点から別の視点に外観をワープさせるためのこの整合に関して重要である。シーンのジオメトリは、一般に、3D特徴点位置を中心とし、3Dの任意の平面法線ベクトルを有する小さい平面パッチとして近似される。局所ジオメトリのこの表現の場合、画像内の特徴位置の周囲のウィンドウの外観をある視点から別の視点にワープさせるために、各3D特徴点位置を中心とする平面パッチの法線ベクトルが必要とされる。加えて、動的な形で環境と相互作用するための拡張の場合、面法線またはパッチ法線の推定が必要とされる。たとえば、弾むボールが跳ね返される表面の法線が知られている場合、そのボールの拡張を現実的にすることができ、拡張現実のアプリケーションでは、これらの法線は3D特徴点を中心とするパッチの面法線である。従来、これらの法線は、ワープされたパッチ同士間の二乗差の和を最小限に抑える反復的勾配降下アルゴリズム(iterative gradien
t descent algorithm)を使用して推定される。たとえば、Nicholas Molton、Andrew Davison、およびIan Reidは、2004 British Machine Vision Conferenceで提示された「Locally Planar Patch Features for Real-Time Structure from Motion」という名称の論文でそのような推定について述べている。この手法は本質的に反復アルゴリズムであり、並列化が困難である。加えて、このプロセスは、大域的最適条件に収束するために、比較的正確な初期解を必要とする。これは表現のためにより高い精度を必要とする勾配の計算を必要とする。計算上の限界により、大部分の従来の解はまた、照明変化に対して不変ではない。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Nicholas Molton、Andrew Davison、およびIan Reid、2004 British Machine Vision Conferenceで提示された「Locally Planar Patch Features for Real-Time Structure from Motion」
【非特許文献２】Richard HartleyおよびAndrew ZissermanによるMultiple View Geometry in Computer Vision
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の実施形態は、捕捉されたビデオストリーム内のオブジェクトの局所的なジオメトリまたは面法線を解くことによって、カメラおよびオブジェクトの追跡を実行することに関する。一実施形態では、ビデオストリーム内で可視的なシーン内の3D特徴点に関する仮説法線が生成される。仮説法線は、移動しているカメラによって見られるオブジェクトに対する面法線の近似を表す。ビデオストリームが第1のキーフレームから第2のキーフレーム内に表されたオブジェクトの異なる視点にパンすると、特定の3D特徴点に関して仮説が立てられたすべての法線のうち正確な面法線は、以下の特性を有するものであり、すなわち、第1のキーフレーム内の画像特徴位置を中心とする画素のウィンドウ/パッチを第2のキーフレームのカメラ視点にワープさせるために正確な法線が使用されるときに、第1のフレームからの画素のワープされたウィンドウは第2のキーフレーム内の画素の対応するウィンドウと高い相関を有するという特性を有する面法線である。第1のキーフレームから第2のキーフレームに画素をワープさせるために使用される不正確に仮説が立てられた法線は、結果として、第1のフレーム内の画素のワープされたウィンドウと第2のキーフレーム内の画素のウィンドウとの間に低い相関スコアをもたらすことになる。一実施形態では、画素のウィンドウ/パッチは、所定の位置を中心とする画素の正方または長方形の格子あるいはパッチ(たとえば、画素の8x8もしくは10x12格子)であり得る。一実施形態では、2つを超えるキーフレームが存在する場合、正確な法線は、結果として、このワーピング手順の後、任意の2個のキーフレーム同士の間で高い相関スコアをもたらし得る。正確な面法線の計算/推定に続いて、ビデオストリーム内のキーフレーム同士の間の対応するオブジェクトまたは点が正確に整合および追跡され得る。
【０００６】
一実施形態では、その正確さを判断するために、並列化可能なアーキテクチャ内のキーフレームのセットに関する仮説法線が解析され、この場合、法線のセットは、ワープされた後、キーフレームの対同士の間の高い相関スコアを判断するために並列して評価される。考えられる面法線の仮説を立てて、キーフレームの複数の対を使用して、その正確さを判断することは、勾配降下または類似の反復的手法を用いる代替案と比較して、画像ノイズに対して頑強な解を提供する。加えて、並列な形で計算を実装できることは、結果として、反復的な手法または類似の手法と比較して、より速い解をもたらす。
【０００７】
別の実施形態は、キーフレームを生成するために、ビデオストリームをサンプリングするステップと、キーフレームのセット内の対応する画像点を選択するステップと、2つ以上のキーフレーム内の対応する画像点を使用して、キーフレームのセットによって画像化されたシーン内に3D特徴点を生成するステップと、3D特徴点に関する仮説面法線を生成するステップと、仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の3D特徴点に対応する画像画素パッチを第2のキーフレームの視点にワープさせるステップと、第1のキーフレームと第2のキーフレームとの間の各仮説面法線から生じるワーピング誤差にスコア付けするステップと、第1のキーフレームと第2のキーフレームとの間で高いワーピング誤差を生み出す仮説面法線を廃棄するステップとを含む、ビデオストリーム内のオブジェクトの面法線を解くための方法に関する。
【０００８】
別の実施形態は、機械によって実行されるとき、機械に、ビデオストリーム内のオブジェクトの面法線を解くための動作を実行させる命令を備えた非一時的機械可読媒体であって、命令が、キーフレームのセットを生成するために、ビデオストリームをサンプリングすることと、キーフレームのセット内の対応する画像点を選択することと、2つ以上のキーフレーム内の対応する画像点を使用して、キーフレームのセットによって画像化されたシーン内に3D特徴点を生成することと、3D特徴点のセットに関する仮説面法線を生成することと、仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の3D特徴点に対応する画像画素パッチを第2のキーフレームの視点にワープさせることと、第1のキーフレームと第2のキーフレームとの間の各仮説面法線から生じるワーピング誤差をスコア付けすることと、第1のキーフレームと第2のキーフレームとの間で高いワーピング誤差をもたらす仮説面法線を廃棄することとを含む、非一時的機械可読媒体に関する。
【０００９】
別の実施形態は、キーフレームのセットを生成するために、ビデオストリームをサンプリングするためのサンプリング手段と、キーフレームのセット内の対応する画像点を選択して、2つ以上のキーフレーム内の対応する画像点を使用して、キーフレームのセットによって画像化されたシーン内に3D特徴点を生成して、3D特徴点に関する仮説面法線を生成するための仮説手段と、仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の3D特徴点に対応する画像画素パッチを第2のキーフレームの視点にワープさせるためのワープ手段と、第1のキーフレームと第2のキーフレームとの間の各仮説面法線から生じるワーピング誤差をスコア付けするためのスコア付け手段と、第1のキーフレームと第2のキーフレームとの間で高いワーピング誤差をもたらす仮説面法線を廃棄するための廃棄手段とを含む、ビデオストリーム内のオブジェクトの面法線を解くためのコンピューティングデバイスに関する。
【００１０】
別の実施形態は、ビデオストリームを捕捉するためのカメラと、キーフレームのセットを生成するために、ビデオストリームをサンプリングするためのサンプリングユニット、キーフレームのセット内の対応する画像点を選択して、2つ以上のキーフレーム内の対応する画像点を使用して、キーフレームのセットによって画像化されたシーン内に3D特徴点を生成して、3D特徴点に関する仮説面法線を生成するための仮説ユニット、仮説面法線の各々から計算されたワーピング行列を用いて、第1のキーフレーム内の3D特徴点に対応する画像画素パッチを第2のキーフレームの視点にワープさせるためのワーピングユニット、第1のキーフレームと第2のキーフレームとの間の各仮説面法線から生じるワーピング誤差をスコア付けするためのスコアリングユニット、および第1のキーフレームと第2のキーフレームとの間で高いワーピング誤差をもたらす仮説面法線を廃棄するための廃棄ユニットを備えた面法線ソルバー(solver)とを備えた、ビデオストリーム内のオブジェクトの面法線を解くためのプロセッサを備えるコンピューティングデバイスに関する。
【００１１】
上記の概要は、本発明のすべての態様の網羅的なリストを含まない。本発明は、上に要約された様々な態様のすべての適切な組合せから実現され得るすべてのシステムおよび方法、ならびに以下の発明を実施するための形態で開示され、本出願で出願される特許請求の範囲において具体的に指摘されるシステムおよび方法を含むことが企図される。そのような組合せは、上の概要で具体的に列挙されない特定の利点を有する。
【００１２】
本開示の特徴、性質、および利点は、全体を通じて同様の参照符号が同様のものを指す図面と併せ読めばより明らかになろう。
【図面の簡単な説明】
【００１３】
【図１】推定された面法線を使用して、未知の環境でカメラを追跡することができ、かつ/またはカメラの前を移動する未知のオブジェクトを追跡することができるコンピューティングデバイスに関する構成要素図である。
【図２】ビデオストリームの第1のキーフレーム内の本の上のマップ点に関する面法線を示す図である。
【図３】平面パッチを見る2つのカメラを示す図である。
【図４】並列化可能なアーキテクチャ内のオブジェクトの面法線を解くための仮説ベースプロセスを示す図である。
【図５】本4に関する仮説法線のセットを用いた例示的なキーフレームを示す図である。
【図６】捕捉されたビデオストリーム内のオブジェクトの局所的なジオメトリまたは面法線を解くことによって、カメラおよびオブジェクトの追跡を実行するための面法線ソルバーを示す図である。
【図７】マップ内の3D特徴点に関して生成された仮説法線方向を示す図である。
【発明を実施するための形態】
【００１４】
図1は、推定された面法線を使用して、未知の環境でカメラを追跡することができ、かつ/またはカメラの前を移動する未知のオブジェクトを追跡することができるコンピューティングデバイス100に関する構成要素図を示す。コンピューティングデバイス100は、デスクトップコンピュータ、ラップトップコンピュータ、モバイルフォン、セルラーフォン、セルラーもしくはその他のワイヤレス通信デバイス、パーソナル通信システム(PCS)デバイス、パーソナルナビゲーションデバイス(PND)、パーソナル情報マネージャ(PIM)、携帯情報端末(PDA)、タブレット、または他の類似のデバイスであり得る。
【００１５】
コンピューティングデバイス100は、メモリユニット102と、捕捉されたビデオストリーム内のカメラおよび/またはオブジェクト追跡に関する動作を実行するためのプロセッサ104とを含み得る。一実施形態では、コンピューティングデバイス100は、デバイス100内に統合されるか、あるいは有線またはワイヤレスの周辺接続を介してデバイス100に接続された、1つもしくは複数のビデオカメラ106a、bを含み得る。ビデオカメラ106a、bは、下でより十分に説明されるように、カメラおよび/またはオブジェクト追跡を実行するために使用されることになるビデオストリームを捕捉することができる。カメラ106a、bは、電荷結合デバイス(CCD)能動ピクセルセンサーおよび相補型金属酸化物半導体(CMOS)能動ピクセルセンサーを含めて、ビデオストリームを捕捉することができる任意のタイプの画像センサーを使用することができる。
【００１６】
一実施形態では、コンピューティングデバイス100は、1つもしくは複数の有線ネットワークまたはワイヤレスネットワークと通信するためのネットワークインターフェースユニット110を含み得る。ネットワークインターフェースユニット110は、遠隔デバイス/サーバ上に記憶されたデータにアクセスするための構成要素をコンピューティングデバイス100内に提供することができる。たとえば、ネットワークインターフェースユニット110は、インターネットを介してアクセス可能な遠隔サーバ上に記憶されたビデオストリームにアクセスするためのプロセッサ104を提供することができる。ネットワークインターフェースユニット110は、様々なプロトコルを使用して、遠隔デバイス/サーバと通信することが可能であり得る。たとえば、ネットワークインターフェースユニット110は、符号分割多元接続(CDMA)プロトコル、時分割多元接続(TDMA)プロトコル、周波数分割多元接続(FDMA)プロトコル、3GPP Long Term Evolution(LTE)プロトコル、Transmission Control Protocol and Internet Protocol(TCP/IP)、IEEE802.Xなどのうちの1つまたは複数で動作するようにプログラムされ得る。たとえば、ネットワークインターフェースユニット110は、ワイヤレスネットワークチャネルを使用して、遠隔サーバ上のビデオストリームにアクセスすること、およびそのビデオストリームを検索することができる。
【００１７】
一実施形態では、コンピューティングデバイス100内の面法線ソルバー108は、捕捉されたビデオストリーム内のオブジェクトの局所的なジオメトリまたは面法線を解くことによって、カメラおよびオブジェクトの追跡を実行するのを支援する。面法線ソルバー108は、コンピューティングデバイス100のプロセッサ104、メモリユニット102、統合デジタル信号プロセッサ112、および他の構成要素と連携して、ビデオストリームを処理して、面法線を解くことができる。正確な面法線の計算/推定に続いて、ビデオストリーム内のフレーム同士の間の対応するオブジェクトまたは点が正確に整合および追跡され得る。
【００１８】
図2は、ビデオストリームの第1のキーフレーム内の本204の上のマップ点(たとえば、3D特徴点)に関する面法線202を示す。本明細書で使用する場合、面法線は、キーフレーム内のオブジェクト上の指定されたマップ点に直交するベクトルまたは平面である。一実施形態では、キーフレーム内のマップ点に関する正確な法線ははじめ知られていない。しかしながら、マップ点に関する仮説法線を生成することができる。仮説法線は、キーフレーム内で見られるオブジェクトに対する面法線の近似を表す。ビデオストリームが第2のキーフレーム内のオブジェクト(たとえば、本204)の異なる視点にパンすると、そのマップ点に関して生成された仮説面法線は、仮説面法線のセット内の各法線を使用して、第1のキーフレームからの画像/特徴パッチを第2のキーフレーム内の画像/特徴パッチにワープさせ、次いで、第2のキーフレーム内の対応する画像/特徴パッチとの相関スコアまたはワーピング誤差を計算することによってスコア付けされ得る(相関スコアおよびワーピング誤差は反比例関係を有する)。特定の仮説面法線を使用する(やはり上で説明された)このワーピング手順の結果として、2個のフレームの特徴パッチ同士の間の相関スコアが(0.9または0.8など)セットしきい値未満である場合、その特定の仮説法線は廃棄され得る。この不正確さは、複数のキーフレーム内の同じマップ点のパッチ同士の間のワーピング手順の間に検出された高い誤差スコア(すなわち、低いNormalized Cross Correlation(NCC)スコア)によって示されることが可能である。正確な面法線は、物理的に妥当と思われる方法で表面と相互作用するための拡張にとって重要である。具体的には、各法線は、ある種の拡張現実アプリケーションに関して、およそ5〜10°以内に推定されなければならない。しかしながら、他のアプリケーションの場合、正確さの条件は異なる(より低いか、またはより高い)場合がある。したがって、不正確な仮説面法線を廃棄することは、後の処理手順における潜在的な誤差を削除する。
【００１９】
NCC整合は、2個の画像同士の間の類似性を見出す問題を解決する。NCCスコアの使用により、整合は平均偏差および標準偏差(一次効果)に対して不変である。画像データの場合、これは、NCCが輝度オフセットおよびコントラスト変化に対して不変であることを意味する。NCCスコアに関するこれらの特性は、異なるカメラで、または異なる時刻に撮影されている画像を比較することがより望まれる。
【００２０】
検索ウィンドウ上でNCCスコアを算出するとき、画像/特徴パッチが最も整合する、検索ウィンドウ内の位置を見出すために、基準パッチが考慮される。以下の式はこの動作を記述する。
【数１】
2016500890.tif 000003
【００２１】
上式で、
・x,yは、パッチ内の画素位置である
・u,vは、検索ウィンドウ内の画素位置である
・f()は、パッチデータにアクセスする
・t()は、検索ウィンドウ内の画像データにアクセスする
・
【数２】
2016500890.tif 000004
(favgとも書かれる)は、パッチ内のすべての画素の平均である
・
【数３】
2016500890.tif 000005
(tavgとも書かれる)は、そのパッチが現在比較されている領域のすべての画素の平均である
・
【数４】
2016500890.tif 000006
は、パッチの分散(二乗標準偏差)である
・
【数５】
2016500890.tif 000007
は、現在比較されている領域の分散(標準偏差)である
【００２２】
上の式では、画素位置の最適対<u,v>は最良の整合を得るために要求される。
【００２３】
2004 British Machine Vision Conferenceで提示された、Nicholas Molton、Andrew Davison、およびIan Reidによる「Locally Planar Patch Features for Real-Time Structure from Motion」という名称の論文の第2.1項は、パッチワーピングを実行するための方法を説明している。この方法は、図3に示すような平面パッチを見る2つのカメラのジオメトリを解析することによって始まる。具体的には、図3は、回転がゼロの起点における第1のカメラ(カメラ0)と、カメラ0からRだけ回転した位置tにおける第2のカメラ(カメラ1)と、法線nを有する局所的に平らな表面上にある位置xpにおける点とを含むシーンを示す。カメラ0背部の画像平面内の位置(u0,v0)の点は光線ρu0に投影し、この場合、u0=(u0,v0,1)Tである。平面p上の点xは、式nTx=nTxpを満たす。光線と平面の交差部において、x=ρu0であり、したがって、ρnTu0=nTxpであり、
【数６】
2016500890.tif 000008
である。この交差部は同次座標(ρv0,1)T=(nTxpu0,nTu0)Tを有する。これを第2の画像内に投影することは、式:
【数７】
2016500890.tif 000009
を与える。
【００２４】
式中、Iは3×3単位行列である。したがって、2つのカメラ画像内の理想的な画像位置はホモグラフィーによって関連付けられる。
HI=R[nTxpI-tnT]
【００２５】
カメラが内部行列C0およびC1を有する場合、ピクセル座標内のホモグラフィーは、
【数８】
2016500890.tif 000010
である。
【００２６】
この式を使用して、そのテンプレート画像と現在のカメラ画像との間の特徴の視覚的外観の変換を予測することができる。この予測と特徴の実際の外観との間の差を見出して、画像登録方法を使用して、面法線推定の関連する補正が行われる。この方法は逆組成調整を実現し、すなわち、元の画像変換Hn-1は、調整値Hiを用いて更新されて、次のように、変換Hnの新しい推定値を出す:
【数９】
2016500890.tif 000011
Hiは、面法線nに対する変化の点でパラメータ化され得る。法線nは、ベクトルdを追加することによって調整され、この場合、
【数１０】
2016500890.tif 000012
である。ベクトル
【数１１】
2016500890.tif 000013
および
【数１２】
2016500890.tif 000014
を、互いに、かつxpに直交する任意の単位ベクトルとして選ぶことができ、αおよびβは調整の量をパラメータ化する。追加調整dは、平面がカメラ0内で可視的になる方位の範囲に対して面法線を変化させるために十分である。上記の式を使用すると、調整変換Hi(すなわち、ワーピング行列)は、
【数１３】
2016500890.tif 000015
になる。
【００２７】
一実施形態では、その正確さを判断するために、並列化可能なアーキテクチャ内のキーフレームのセットに関する仮説法線が解析され、この場合、法線のセットは、ワープされた後、キーフレームの対同士の間の高い相関スコアまたは低いワーピング誤差を判断するために並列して評価される。考えられる面法線の仮説を立てて、キーフレームの複数の対を使用して、その正確さを判断することは、勾配降下手法または類似の反復的手法を用いる代替案と比較して、画像ノイズに対して頑強な解を提供する。たとえば、この仮説主導のシステムおよびプロセスには、初期化に応じて、最小値で止まってしまうという問題がない。さらに、勾配降下手法は、画像降下の正確な推定に依存するが、画像ノイズがある場合、画像勾配推定値は不正確になる。したがって、画像画素ノイズが存在する場合、仮説面法線計算はより頑強である。
【００２８】
図4は、並列化可能なアーキテクチャ内のオブジェクトの面法線を解くための仮説ベースプロセス300を示す。プロセス300は、図2に示すコンピューティングデバイス100の構成要素のうちの1つまたは複数によって実行され得る。たとえば、法線ソルバー108は、コンピューティングデバイス100のプロセッサ104、メモリユニット102、および他の構成要素と連携して、下で説明する動作を実行することができる。
【００２９】
プロセス300は、ビデオストリームの受信または検索で動作302を開始する。ビデオストリームは、カメラ106a、bのうちの1つから取得可能であるか、またはローカルメモリソースもしくは遠隔メモリソースから取得可能である。たとえば、ビデオストリームは、メモリユニット102内に記憶されて、面法線ソルバー108およびプロセッサ104によってアクセス可能であり得る。別の例では、ビデオストリームは、遠隔サーバ上に記憶されて、ネットワークインターフェースユニット110の使用により面法線ソルバー108にとってアクセス可能である。ビデオストリームは、任意のコーディングフォーマットまたはコーディング技法を使用して符号化され得る。たとえば、ビデオストリームは、Advanced Video Codec High Definition(AVCHD)、Audio Video Interleaved(AVI)、Adobe Flash Video Format(FLV)、Google Video File Format(GVI)、H.264、およびMoving Picture Experts Group(MPEG)の一連の標準を使用して符号化され得る。
【００３０】
動作302における受信または検索時に、動作304で、一連のキーフレームを生成するために、ビデオストリームをサンプリングする。ビデオストリームから取得されるキーフレームの数は、ビデオストリームの長さおよび指定されたサンプリングレートに依存し得る。たとえば、30秒のビデオストリームを5Hzのレートでサンプリングして、150個のキーフレームを出力することができる。他の実施形態では、異なるサンプリングレートが使われてもよい。動作304においてサンプリングによって生成された各キーフレームは、特定の瞬間におけるビデオストリーム内のシーンの完全な表現(たとえば、シーンの静止画像)である。サンプリングレートは、ビデオストリーム内のオブジェクトの著しい差または移動を表示するキーフレームを出力して、有用な基線を提供するように選ばれる。一実施形態では、コンピューティングデバイス100に統合された専用ビデオサンプリングユニットが、キーフレームのセットを生み出すために、ビデオストリームをサンプリングする。
【００３１】
動作305で、キーフレームのセット内の画像点が選択されて、これらの画像点を使用して、キーフレームのセットによって観測されたシーン内のマップ点(たとえば、3D特徴点)を生成する。画像点は、キーフレームによって観測されたシーン内の3次元要素(すなわち、3D特徴点)に対応する、キーフレーム内の2次元位置である。
【００３２】
動作306で、マップ点のセットに関する仮説法線を生成する。一実施形態では、仮説法線は、各キーフレームによって表されるシーンの単位球面内の異なる個別の方向に対応する。たとえば、第1のマップ点における第1の仮説法線は、x軸に対して45度に向いている可能性があるのに対して、第2のマップ点における第2の仮説法線は、x軸に対して90°に向いている可能性がある。これらの仮説法線の各々は、キーフレームによって画像化されたオブジェクトの面法線の推定を表す。一実施形態では、各マップ点に関する仮説法線のセットが生成される。たとえば、60個の別個のマップ点に関する60個の仮説面法線を生成することができる。他の例では、20〜100個の仮説面法線を生成することができる。たとえば、一実施形態では、30個の別個のマップ点に関する30個の仮説面法線を生成することができるのに対して、別の実施形態では、50個の別個のマップ点に関する50個の仮説面法線を生成することができる。これらの仮説面法線は概算推定であるが、その正確さは、下でさらに詳細に説明される比較およびスコア付けによって判断されることになる。正確な面法線を推定および判断することは、大きい基線を有する視点同士の間のキーフレーム内のパッチの外観をワープさせるために重要である。したがって、不正確な仮説面法線を廃棄することは、後の処理手順における潜在的な誤差を削除する。
【００３３】
動作308で、それぞれの仮説法線を比較するために、2個のキーフレームを選択する。選択されたキーフレームは、ビデオストリーム内の順次/隣接フレームまたはビデオストリーム内の非順次/非隣接フレームであり得る。一実施形態では、選択されたキーフレームは、キーフレームによって表されたシーン内のオブジェクトの移動を確実にするために、時間的に十分に離して選ばれる。たとえば、キーフレーム同士の間の必要な分離程度を示すために、より低い分離限度を設定することができる。キーフレームの分離は、仮説/推定法線をスコア付け/比較するために十分に区別できるよう十分広い基線を提供する。キーフレームは比較的分離するように選択されるが、一実施形態では、キーフレームが実質的に異ならないように、この分離は分離上限を超えるべきではない。たとえば、50個のキーフレームの連続セットでは、分離下限は3個のキーフレームであってよいのに対して、分離上限は5個のキーフレームであってよい。この例では、動作308で選択されたキーフレームは、フレーム5および9であってよい(すなわち、4個のキーフレームだけ分離する)。他の実施形態では、分離下限は1〜5個のキーフレームの範囲であってよいのに対して、分離上限は5〜10個のキーフレームの範囲であってよい。分離上限および分離下限はキーフレームの点で表されているが、他の実施形態では、分離限度は、元のビデオストリーム内のキーフレーム同士の間の時間差の点で表されてもよい。相対的な類似性および良好な基線を有するキーフレームを選ぶことによって、ワーピングおよび比較動作がより正確に実行され得る。
【００３４】
2個のキーフレームの選択に続いて、動作310は、そのパッチに対応するマップ点に関する仮説面法線の各々を使用して、画像画素パッチの外観をある選択されたキーフレームから別の選択されたキーフレームにワープさせる。一実施形態では、画素のウィンドウ/パッチは、キーフレーム内で表される画像内の所定の位置を中心とする画素の正方または長方形の格子あるいはパッチ(たとえば、画素の8x8もしくは10x12格子)であり得る。ワーピングは、上で説明したプロセスを介して計算されたワーピング行列を使用して実行され得る。各仮説面法線をスコア付けして、正確さ(すなわち、誤差の程度)を判断する。一実施形態では、スコアは、ワープを計算するために仮説法線が使用される、第1のキーフレームからワープされたパッチと第2のキーフレーム内のターゲットパッチとの間のNCC(正規化相互相関)スコアに基づく。事前定義された相関スコアレベルを超えるスコアをもたらす仮説法線は、正確な仮説であると判断されるのに対して、事前定義された相関スコアレベル未満のスコアは不正確であると判断されて、廃棄される。低い相関スコア仮説を廃棄することは、より可能性の高い推定値を維持すると同時に、起こりそうもない解を除去する。一実施形態では、複数のキーフレームに関するワーピング誤差とワーピング手順とを合わせて、複数のキーフレームを通した誤差推定の頑強さを改善することができる。
【００３５】
図5は、本404に関する仮説法線402のセットを用いた例示的なキーフレームを示す。影付き法線402a、bは、動作310で計算されたそのスコアが事前提示された相関スコアレベル未満である不正確な法線を表すのに対して、影が付いていない法線402c、d、eは、そのスコアが事前提示された相関スコアレベルを超える正確な法線を表す。上記のように、不正確な法線402a、b(たとえば、影付き面法線)は廃棄されるのに対して、正確な法線402c、d、eは、カメラおよびオブジェクトの追跡動作で使用するために保持される。
【００３６】
一実施形態では、動作308および310はキーフレームの複数の対に関して繰り返される。たとえば、キーフレーム5および9が比較およびワープされ、両方のフレーム内で正確な法線と不正確な法線とを明らかにした後、類似の形で、キーフレーム2を用いてキーフレーム5を処理することができる。フレームが繰り返し比較されると、仮説剪定(hypothesis pruning)(すなわち、フレームのすべての対を使用して仮説をテストせずに、起こりそうもない仮説を早期に除去すること)により、計算の数は経時的に減少する。
【００３７】
キーフレームの複数の対を使用することによって、推定および面法線解の頑強さは増大する。十分な数のキーフレーム対が比較/ワープされ、動作312で、正確であると思われる1つまたは複数の面法線の明らかなセットが判断された後、法線推定は収束されたとして、動作308および310は終了する。その後、動作314で、剪定された面法線の最終的なセットを使用して、カメラ追跡、オブジェクト追跡、または他のビデオ処理手順を実行することができる。一実施形態では、動作312は、最高相関スコアレベル(すなわち、最小ワーピング誤差)を有する面法線を判断することができる。その後、最高相関スコアを有する、この判断された面法線を使用して、動作314で、カメラ追跡、オブジェクト追跡、または他のビデオ処理手順を実行することができる。
【００３８】
仮説面法線は独立しており、対応する比較/ワーピング動作を別々に実行することができるため、上で説明した面法線を解くためのプロセスは並列化され得る。並列化可能であり、独自に動作可能であるこの能力は、キャッシュを局所的に利用する潜在的なハードウェア加速の可用性を実現する。
【００３９】
一実施形態では、各キーフレーム内の仮説法線を初期化および精緻化するために方位ヒストグラムが使用される。たとえば、キーフレーム内の各マップ点について、このマップ点を観測する各キーフレームに関して、マップ点からカメラの中心に向かう方向が計算される。マップ点に関する概算法線推定は、各マップ点に関するこれらのベクトルの平均である。
【００４０】
図6は、一実施形態による、面法線ソルバー108の機能ユニットブロック図およびある成分ハードウェア構成要素を示す。図6に示す構成要素は、面法線ソルバー108内に含まれた要素を表し、他の構成要素を排除するとして解釈されるべきではない。面法線ソルバー108の構成要素を使用して、上で説明したオブジェクトの面法線を解くための仮説ベースのプロセス300の動作のうちの1つまたは複数を実行することができる。
【００４１】
一実施形態では、面法線ソルバー108は、サンプリング手段/ユニット502を含む。サンプリング手段502は、一連のキーフレームを生み出すために、ビデオストリームをサンプリングする。ビデオストリームから取得されるキーフレームの数は、ビデオストリームの長さおよび指定されたサンプリングレートに依存し得る。サンプリングレートは、ビデオストリーム内のオブジェクトの著しい差または移動を表示するキーフレームを出力して、有用な基線を提供するように選ばれる。一実施形態では、サンプリング手段502は、DSP、汎用ハードウェアプロセッサ、フィルタのセット、および/または任意の類似のデバイスであってよい。
【００４２】
一実施形態では、面法線ソルバー108は、仮説手段/ユニット504を含む。仮説手段504は、サンプリング手段502が生み出したキーフレームの各々の中にマップ点のセットを生成する。一実施形態では、仮説法線は、各キーフレームによって表されるシーンの単位球面に対する異なる個別の方向に対応する。たとえば、図7は、マップ内の3D特徴点に関して生成された、球体から突出するライン701によって表される仮説法線方向を示す。仮説手段504は、DSP、汎用ハードウェアプロセッサ、フィルタのセット、および/または任意の類似のデバイスであってよい。一実施形態では、仮説手段504は、キーフレーム内の画像点を選択することができる。Multiple View Geometryでよく知られている技法を使用して、キーフレームによって画像化されたシーン内にマップ点(たとえば、3D特徴点)を生成するために、2つ以上のキーフレーム内の対応する画像点が使用され得る。たとえば、Richard HartleyおよびAndrew ZissermanによるMultiple View Geometry in Computer Visionという書籍は、マップ点(たとえば、3D特徴点)を生成するために使用され得る技法を説明する。画像点は、キーフレームによって画像化されたシーン内の3次元要素(すなわち、3D特徴点)に対応する、キーフレーム内の2次元位置である。
【００４３】
一実施形態では、面法線ソルバー108は、選択手段/ユニット506を含む。選択手段506は、サンプリング手段502が生み出したキーフレームのセットから2個のキーフレームを選択する。一実施形態では、選択されたキーフレームは、キーフレームによって表されたシーン内のオブジェクトの移動を確実にするために、時間的に十分に離して選ばれる。選択手段506は、DSP、汎用ハードウェアプロセッサ、フィルタのセット、および/または任意の類似のデバイスであってよい。
【００４４】
一実施形態では、面法線ソルバー108は、ワーピング手段/ユニット508を含む。ワーピング手段508は、そのパッチに対応するマップ点に関する仮説面法線の各々を使用して、画像画素パッチの外観をある選択されたキーフレームから別の選択されたキーフレームにワープさせる。ワーピング手段508は、DSP、汎用ハードウェアプロセッサ、フィルタのセット、および/または任意の類似のデバイスであってよい。
【００４５】
一実施形態では、面法線ソルバー108は、スコア付け手段/ユニット510を含む。スコア付け手段510は、各面法線をスコア付けして、正確さ(すなわち、誤差の程度)を判断する。一実施形態では、スコアは、ワープを計算するために仮説法線が使用される、第1のキーフレームからのワープされたパッチと第2のキーフレーム内のターゲットパッチとの間のNCC(正規化相互相関)スコアである。一実施形態では、スコア付け手段510は、複数のキーフレームに関するワーピング誤差を合計して、複数のキーフレームを通して誤差推定を改善する。スコア付け手段510は、DSP、汎用ハードウェアプロセッサ、フィルタのセット、および/または任意の類似のデバイスであってよい。
【００４６】
一実施形態では、面法線ソルバー108は、除去手段/ユニット512と、マーキング手段/ユニと514とを含む。除去手段512は、そのスコアが事前定義された相関スコアレベル未満の仮説法線を廃棄/除去するのに対して、マーキング手段514は、そのスコアが事前定義された相関スコアレベルを超える仮説法線をマーキングする。そのスコアが事前定義された相関スコアレベルを超える仮説法線は正確な仮説であると判断されるのに対して、事前定義された相関スコアレベル未満のスコアは不正確であると判断されて、廃棄される。低い相関スコア仮説を廃棄することは、より可能性の高い推定値を維持すると同時に、起こりそうもない解を除去する。除去手段512およびマーキング手段514は、DSP、汎用ハードウェアプロセッサ、フィルタのセット、および/または任意の類似のデバイスであってよい。
【００４７】
一実施形態では、面法線ソルバー108は、判断手段/ユニット516を含む。判断手段516は、マーキングされた面法線のセットが面法線の事前定義された数以上であるかどうかを判断する。マーキングされた面法線の数が事前定義された数未満であるとき、判断手段516は、ワーピング手段、スコア付け手段、および除去手段にキーフレームの新しい対を処理させる。判断手段516は、DSP、汎用ハードウェアプロセッサ、フィルタのセット、および/または任意の類似のデバイスであってよい。一実施形態では、判断手段516は、最高相関スコアレベル(すなわち、最小ワーピング誤差)を有する面法線を判断することができる。その後、最高相関スコアを有する、この判断された面法線を使用して、カメラ追跡、オブジェクト追跡、または他のビデオ処理手順を実行することができる。
【００４８】
本明細書に記載された方法論は、アプリケーションに依存する様々な手段によって実装され得る。たとえば、これらの方法論は、ハードウェア、ファームウェア、ソフトウェア、またはそれらの任意の組合せで実装され得る。ハードウェアを伴う実装形態の場合、処理ユニットは、1つもしくは複数の特定用途向け集積回路(ASIC)、デジタル信号プロセッサ(DSP)、デジタル信号処理デバイス(DSPD)、プログラマブル論理デバイス(PLD)、フィールドプログラマブルゲートアレイ(FPGA)、プロセッサ、コントローラ、マイクロコントローラ、マイクロプロセッサ、電子デバイス、本明細書で説明する機能を実行するように設計された他の電子ユニット、またはそれらの組合せの中で実装され得る。
【００４９】
ファームウェアおよび/またはソフトウェアを伴う実装形態の場合、本方法は、本明細書で説明する機能を実行するモジュール(たとえば、プロシージャ、関数など)を用いて実装され得る。本明細書で説明する方法を実装する際に、命令を有形に具現化する任意の機械可読媒体を使用してもよい。たとえば、ソフトウェアコードは、メモリに記憶され、処理ユニットによって実行され得る。メモリは、処理ユニット内に実装されるかあるいは処理ユニットの外部に実装され得る。本明細書で用いられる「メモリ」という用語は、任意の種類の長期メモリ、短期メモリ、揮発性メモリ、不揮発性メモリ、または他のメモリを指し、いずれかの特定のタイプのメモリもしくはいずれかの特定のメモリ数に限定すべきではなく、また、メモリが記憶される媒体としていずれかの特定のタイプの媒体に限定すべきではない。
【００５０】
ファームウェアおよび/またはソフトウェアで実装する場合、機能は、コンピュータ可読媒体上に1つもしくは複数の命令またはコードとして記憶されてもよい。例は、データ構造によって符号化されたコンピュータ可読媒体およびコンピュータプログラムによって符号化されたコンピュータ可読媒体を含む。コンピュータ可読媒体は、物理的なコンピュータ記憶媒体を含む。記憶媒体は、コンピュータによってアクセスされ得る任意の使用可能な媒体であり得る。限定ではなく、例として、そのようなコンピュータ可読媒体は、RAM、ROM、EEPROM、CD-ROMもしくは他の光ディスク(disk)ストレージ、磁気ディスク(disk)ストレージ、半導体ストレージ、または他のストレージデバイス、あるいは命令またはデータ構造の形態の所望のプログラムコードを記憶するために使用され得る、またはコンピュータによってアクセスされ得る、任意の他の媒体を含んでもよい。本明細書で使用するディスク(disk)およびディスク(disc)は、コンパクトディスク(disc)(CD)、レーザディスク(disc)、光ディスク(disc)、デジタル多用途ディスク(disc)(DVD)、フロッピー(登録商標)ディスク(disk)およびブルーレイディスク(disc)を含み、ディスク(disk)は、通常、データを磁気的に再生し、ディスク(disc)は、データをレーザで光学的に再生する。前述の組合せも、コンピュータ可読媒体の範囲内に含まれるべきである。
【００５１】
コンピュータ可読媒体における記憶に加えて、命令および/またはデータは、通信装置に含まれる送信媒体における信号として提供され得る。たとえば、通信装置は、命令およびデータを示す信号を有する送受信機を含み得る。命令およびデータは、1つまたは複数の処理ユニットに、特許請求の範囲で概説する機能を実装させるように構成される。すなわち、通信装置は、開示する機能を実行するための情報を示す信号をもつ伝送媒体を含む。第1の時間において、通信装置中に含まれる伝送媒体は、開示される機能を実行するための情報の第1の部分を含んでもよく、一方、第2の時間において、通信装置中に含まれる伝送媒体は、開示される機能を実行するための情報の第2の部分を含んでもよい。
【符号の説明】
【００５２】
100  コンピューティングデバイス
102  メモリユニット
104  プロセッサ
106a、106b  ビデオカメラ
108  面法線ソルバー
110  ネットワークインターフェースユニット
112  統合デジタル信号プロセッサ
202  表面法線
204  本
300  プロセス
402  仮説法線
402a、402b  影付き法線、不正確な法線
402c、402d、402e  影が付いていない法線、正確な法線
404  本
502  サンプリング手段/ユニット
504  仮説手段/ユニット
506  選択手段/ユニット
508  ワーピング手段/ユニット
510  スコア付け手段/ユニット
512  除去手段/ユニット
514  マーキング手段/ユニット
516  判断手段/ユニット
701  ライン
【図１】
2016500890.tif 000016
【図２】
2016500890.tif 000017
【図３】
2016500890.tif 000018
【図４】
2016500890.tif 000019
【図５】
2016500890.tif 000020
【図６】
2016500890.tif 000021
【図７】
2016500890.tif 000022
【国際調査報告】
2016500890.tif 000023
2016500890.tif 000024