(57)【要約】  画像処理システム（１００）が、プロセッサ（１０２）と、ビデオの第１のフレーム及びビデオの第２のフレームにおける特徴の相対的動きを数量化するためのオプティカルフロー（ＯＦ）判定ロジック（１０４）とを含む。ビデオの第１のフレーム及び第２のフレームは、ビデオの２つのフレームに関して、時間的及び空間的に序列された画像（１１０）の少なくとも１つを提供する。ＯＦ判定ロジック（１０４）は、整数画素解像度を有するベースピラミッドレベルで初期オプティカルフロー（ＯＦ）推定を生成するために、ピラミッド状ブロックマッチング（ＰＢＭ）法を用いて第１のフレームと第２のフレームとの間でＯＦ推定を実施することと、分数画素解像度を有する修正されたＯＦ推定を提供するために、変形Ｌｕｃａｓ−Ｋａｎａｄｅ（ＬＫ）法の少なくとも１パスを用いて、初期ＯＦ推定を精密化することとを実装するようにプロセッサ（１０２）を構成する。
2019504394.tif 000002
【特許請求の範囲】
【請求項１】
画像処理システムであって、
プロセッサと、
ビデオの第１のフレーム及びビデオの第２のフレームに存在する特徴の相対的動きを数量化するためのオプティカルフロー（ＯＦ）判定ロジックであって、ビデオの前記第１のフレーム及び前記第２のフレームが、ビデオの前記第１のフレーム及びビデオの前記第２のフレームに関して時間的に序列された画像及び空間的に序列された画像の少なくとも１つを提供する、前記ＯＦ判定ロジックと、
を含み、
前記ＯＦ判定ロジックが、
整数画素解像度を有するベースピラミッドレベルにおいて、初期オプティカルフロー（ＯＦ）推定を生成するために、ピラミッド状ブロックマッチング（ＰＢＭ）法を用いて、前記第１のフレームと前記第２のフレームとの間でＯＦ推定を実施することと、
分数画素解像度を有する修正されたＯＦ推定を提供するために、変形Ｌｕｃａｓ−Ｋａｎａｄｅ（ＬＫ）法の少なくとも１パスを用いて、前記初期ＯＦ推定を精密化することと、
を実装するように、前記プロセッサを構成する、
画像処理システム。
【請求項２】
請求項１に記載の画像処理システムであって、前記ＰＢＭ法が、予測子及び動き平滑性因子を用いる階層式コース・ツー・ファインサーチ戦略、画素記述に対するバイナリセンサス変換、及び、コスト関数としてのハミング距離を利用する、画像処理システム。
【請求項３】
請求項１に記載の画像処理システムであって、前記ＰＢＭ法が、各々のパクセル全体に対する予測子の同じセットを用いる処理のパクセル順、及び予測子のセットに対する事前評価戦略を利用する、画像処理システム。
【請求項４】
請求項１に記載の画像処理システムであって、前記ＰＢＭ法が、前記ＰＢＭ法のブロックマッチングステップの間、空間的勾配及び時間的勾配の事前計算を用いる、画像処理システム。
【請求項５】
請求項１に記載の画像処理システムであって、前記ＯＦ判定ロジックが、ハードウェアアクセラレータ（ＨＷＡ）によって部分的に実装され、前記ＨＷＡが、ビデオの前記第１のフレーム及び前記第２のフレームからピクチャデータをグローイングウィンドウ様式でストアするための１つのメモリと、ビデオの前記第２のフレームから前記ピクチャのスライディングウィンドウをストアするためのもう１つのメモリとを備える、ローカルメモリの２つのレベルの組み合わせを利用する、画像処理システム。
【請求項６】
請求項１に記載の画像処理システムであって、前記変形ＬＫ法が、画像ワーピングステップを除くものであり、前記修正されたＯＦ推定を計算することを、空間的及び時間的勾配計算のサブタスクとその他の演算とに分離し、ＯＦ精密化に対して低減精度勾配データを用い、行列反転を含む計算タスクを実施するために整数演算のみを用いる、画像処理システム。
【請求項７】
請求項２に記載の画像処理システムであって、前記ＯＦ判定ロジックが、前記サーチ戦略の各シーケンシャルサーチに対する前記コスト関数に、動き平滑性因子、及びメディアンの予測子値と候補の画素との間の距離を組み合わせる動きベクトルコスト値を含むように、前記プロセッサを構成する、画像処理システム。
【請求項８】
請求項１に記載の画像処理システムであって、前記少なくとも１パスが、前記ＰＢＭ法が終了した後の前記ベースピラミッドレベルを含む前記ＰＢＭ法によって用いられるサーチピラミッドの全てのピラミッドレベルにおいて前記変形ＬＫ法を適用する単一パスから構成される、画像処理システム。
【請求項９】
請求項１に記載の画像処理システムであって、前記修正されたＯＦ推定からインパルス性ノイズを除去するために、疑似１Ｄ分離可能メディアンフィルタを用いる事後処理フィルタリングのための事後処理フィルタを更に含む、画像処理システム。
【請求項１０】
オプティカルフロー（ＯＦ）推定の方法であって、
時間的に序列された画像及び空間的に序列された画像の少なくとも１つを提供するビデオの第１のフレーム及びビデオの第２のフレームを取得すること、
ピラミッド状ブロックマッチング（ＰＢＭ）法を変形Ｌｕｃａｓ−Ｋａｎａｄｅ（ＬＫ）法と組み合わせる、ストアされた準パラメトリックオプティカルフロー測定（ＱＰ−ＯＦＭ）アルゴリズムを実装するプロセッサを用いること、
を含み、
前記ＱＰ−ＯＦＭアルゴリズムが、
整数画素解像度を有するベースピラミッドレベルで初期ＯＦ推定を生成するために、前記ＰＢＭ法を用いて、前記第１のフレームと前記第２のフレームとの間でオプティカルフロー（ＯＦ）を推定することと、
分数画素解像度を有する修正されたＯＦ推定を提供するために、前記変形ＬＫ法の少なくとも１パスを用いて、前記初期ＯＦ推定を精密化することと、
を実行する、
方法。
【請求項１１】
請求項１０に記載の方法であって、前記ＰＢＭ法が、予測子及び動き平滑性因子を用いる階層式コース・ツー・ファインサーチ戦略、画素記述に対するバイナリセンサス変換、及び、コスト関数としてのハミング距離を利用する、方法。
【請求項１２】
請求項１０に記載の方法であって、前記ＰＢＭ法が、各パクセル全体に対する予測子の同一セットを用いる処理のパクセル順、及び予測子のセットに対する事前評価戦略を利用する、方法。
【請求項１３】
請求項１０に記載の方法であって、前記ＰＢＭ法が、前記ＰＢＭ法のブロックマッチングステップの間、空間的勾配及び時間的勾配の事前計算を用いる、方法。
【請求項１４】
請求項１０に記載の方法であって、前記変形ＬＫ法が、画像ワーピングステップを除くものであり、前記修正されたＯＦ推定を計算することを、空間的勾配計算のサブタスクとその他の演算とに分離し、ＯＦ精密化に対して低減精度勾配データを用い、行列反転を含む計算タスクを実施するために整数演算のみを用いる、方法。
【請求項１５】
請求項１０に記載の方法であって、前記ＱＰ−ＯＦＭアルゴリズムが、ハードウェアアクセラレータ（ＨＷＡ）を含むシステム−オン−チップ（ＳＯＣ）として少なくとも部分的に実装され、前記ＨＷＡが、ビデオの前記第１のフレーム及び前記第２のフレームからピクチャデータをグローイングウィンドウ様式でストアするための１つのメモリと、ビデオの前記第２のフレームから前記ピクチャのスライディングウィンドウをストアするためのもう１つのメモリとを備える、ローカルメモリの２つのレベルの組み合わせを利用する、方法。
【請求項１６】
請求項１０に記載の方法であって、場面分析を生成するために構成されるプロセッサを含む画像処理システムによって実装される、方法。
【請求項１７】
請求項１６に記載の方法であって、前記場面分析が、障害物検出又は衝突回避自動緊急ブレーキのために、先進運転支援システム（ＡＤＡＳ）によって用いられる、方法。
【請求項１８】
請求項１１に記載の方法であって、前記方法が、前記サーチ戦略の各シーケンシャルサーチに対する前記コスト関数に、動き平滑性因子、及びメディアン予測子値と候補画素との間の距離を組み合わせる動きベクトルコスト値を含む、方法。
【請求項１９】
請求項１０に記載の方法であって、更に、前記修正されたＯＦ推定からインパルス性ノイズを除去するために疑似１Ｄ分離可能メディアンフィルタを用いる事後処理フィルタに対する事後処理フィルタリングを含む、方法。
【請求項２０】
請求項１０に記載の方法であって、前記少なくとも１パスが、前記ＰＢＭ法が終了した後の前記ベースピラミッドレベルを含む前記ＰＢＭ法によって用いられるサーチピラミッドの全てのピラミッドレベルにおいて前記変形ＬＫ法を適用する単一パスから構成される、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、ピラミッド状ブロックマッチングの使用を含むオプティカルフロー推定に関する。
【背景技術】
【０００２】
オプティカルフロー（又はオプティックフロー）は、カメラ等の光学センサと画像内に存在するオブジェクトとの間の相対的動きに起因する、一連の画像におけるオブジェクトの観測される動きである。用語「オプティカルフロー」は、例えば動き検出、オブジェクトセグメンテーション、接触までの時間情報、消失点（focus of expansion）計算、輝度、動き補償符号化、ステレオディスパリティ測定等の関連技法を画像処理及びナビゲーション制御から取り込むために、概してコンピュータビジョンドメインに適用される。そのような技法は、自動車運転支援システム、ロボット工学、及び機械ビジョンを応用するその他の用途において特に有用である。
【０００３】
画像データの２つのアレイ間で、最良のマッチングパッチを探すことが画像処理において必要なステップである。例えば、幾つかの立体画像形成システム（stereoscopic imaging system）は、左画像における所与の二次元（２Ｄ）パッチに最良にマッチする二次元（２Ｄ）パッチを右画像において探すことによって、左右の画像間のディスパリティを計算する。別の例では、ボリューム間で最良の３Ｄパッチマッチをサーチすることによって、２つの三次元（３Ｄ）ポイントクラウドのアライメントが達成され得る。別の例では、ビデオ圧縮アルゴリズムが、２つの画像間のパッチにマッチするオプティカルフローアルゴリズムを用いて２つの連続する画像間の動きを判定し得る。
【０００４】
オプティカルフローアルゴリズムマッチングに対してコース・ツー・ファイン解像度ピラミッドアプローチが用いられ得る。概して、ピラミッドアプローチにおいて、オリジナル画像より低い解像度で初期のサーチが実施され、初期サーチの結果がその後、１つ又はそれ以上高い解像度で精密化（refine）される。サーチピラミッドにおける解像度レベルの数は実装依存である。ピラミッド状サーチアプローチの使用は、概して、高解像度でのしらみつぶし探索に比べて、高速でありローカルミニマ（local minima）に対する許容度が高い。
【０００５】
カメラベースのシステムは、事故の可能性又は過酷さを低減するために、必須情報、警告、及び自動介入を提供することによって、ドライバーの状況認識及び道路安全性を増大させるように設計された先進運転支援システム（ＡＤＡＳ）を実装するために、種々のコンピュータビジョン（ＣＶ）技術を用いる。政府による安全性規制及び独立格付けシステムがＡＤＡＳの開発及び広範な普及を推進しており、カメラベースのシステムがＯＥＭによる主要差別化要素として浮上している。カメラベースのシステムは、その信頼度の堅牢性、種々の応用例をサポートする能力、及び最も重要なこととして、将来において更に増加するＡＤＡＳ応用例をサポートするための柔軟性のため、ＡＤＡＳに広範に採用されつつある。ＣＶ技法、特に、カメラ画像から高精細、高密度深度（ステレオ）、及び動き（オプティカルフロー）情報を抽出する低レベルのＣＶ技法は、複雑性、高性能、及び低電力計算の問題を示す。
【発明の概要】
【０００６】
説明される例は、広いオプティカルフロー（ＯＦ）範囲にわたって高精度推定を得るために、非パラメトリックアプローチであるピラミッド状ブロックマッチング（ＰＢＭ）法と、パラメトリックアプローチである変形Ｌｕｃａｓ−Ｋａｎａｄｅ（ＬＫ）法とを組み合わせる準パラメトリックオプティカルフロー測定（ＱＰ−ＯＦＭ）アルゴリズムを実装するオプティカルフローロジックを有する画像プロセッサを含む。ＰＢＭ法は、整数画素解像度を備えるＯＦ推定を実施し、その後、変形ＬＫ法の少なくとも１パスが用いられ、ＰＢＭ取得されたＯＦ推定を精密化し、分数画素解像度を備える修正されたオプティカルフロー推定を得る。変形ＬＫ法の１パスは、補間及びデータ再フェッチを必要としないので、概して、良好な費用便益バランスを提供する。
【０００７】
説明される例は画像処理システムを含み、この画像処理システムは、プロセッサと、第１のフレームのビデオ（例えば、クエリ画像）及び第２のフレームのビデオ（例えば、参照画像）において存在する特徴の相対的動きを数量化するためのＯＦ判定ロジックとを含む。第１のフレームのビデオ及び第２のフレームのビデオは、２つのフレームのビデオに関して時間的及び空間的に序列された画像の少なくとも１つを提供する。ＯＦ判定ロジックは、整数画素解像度を有するベース（最低）ピラミッドレベルで初期ＯＦ推定を生成するために、ＰＢＭ法を用いて第１のフレームと第２のフレームとの間でＯＦ推定を実施すること、及び分数画素解像度を有する修正されたＯＦ推定を提供するために、変形ＬＫ法を用いて初期ＯＦ推定を精密化することを実装するようにプロセッサを構成する。ＱＰ−ＯＦＭアルゴリズムは、既知のＰＢＭベースのデンス（dense）ＯＦ（ＤＯＦ）推定アルゴリズムに対し、有意にシンプル化し改善する。後述する例は、既知のＤＯＦ推定アルゴリズムに比べて改善された性能を示す。
【図面の簡単な説明】
【０００８】
【図１】例示の実施形態に従った、ＯＦを判定及び適用する、開示されるＱＰ−ＯＦＭアルゴリズムを実装するシステムに対するブロック図である。
【０００９】
【図２】例示の実施形態に従った、開示されるＱＰ−ＯＦＭを用いるオプティカルフロー測定の例示の方法におけるステップを示すフローチャートである。
【００１０】
【図３】開示される例示のＱＰ−ＯＦＭ配置の簡略化されたブロック図である。
【００１１】
【図４】例示の実施形態に従った、中央の画素ｘに対する２４ビットのセンサス記述子を、その２４個の近隣子（近傍の５×５）及びそれらの関係を考慮して計算するための方法を図示する。
【００１２】
【図５】画素のセンサス署名計算に用いられる５×５近傍画素を図示する。
【００１３】
【図６】例示のサポートウィンドウを図示する。
【００１４】
【図７】パクセル（paxel）における頂部左画素の４つの近隣子のオプティカルフロー推定を含む例示の予測子リストを示す。
【００１５】
【図８】現在のパクセルに対する候補予測子、及びそれらのうちのウィナー（winner）予測子を含む、予測子評価の図を提供する。
【００１６】
【図９】ウィナー予測子の周囲のコース・ツー・ファインサーチパターンを図示する。
【００１７】
【図１０Ａ】低レベル、計算集約的、及び反復的なＣＶタスクをオフロードすることによって、高いプログラマブル計算パワーをハードウェアアクセラレータ（ＨＷＡ）に提供する例示のＳｏＣを図示する。
【００１８】
【図１０Ｂ】ＨＷＡ内又はプログラマブルプロセッサ上のローカルメモリにおける、参照及び現在のピクチャデータをストア及びハンドリングする例示のスキームの実装詳細を図示する。これには、第１のフレームのビデオからの及び第２のフレームからのピクチャデータをグローイングウィンドウ様式でストアするための１つのメモリ、及び第２のフレームのビデオからのピクチャデータのスライディングウィンドウをストアするための別のメモリを備える、ローカルメモリの２つのレベルの組み合わせを利用することが含まれる。
【発明を実施するための形態】
【００１９】
図面において、類似又は同等の要素を示すために類似の参照番号が用いられる。幾つかの行為又は事象が、異なる順に、及び／又は他の行為又は事象と同時に起こり得る。また、幾つかの図示された動作又は事象が、本説明に従った方法論を実装するために必要とされない場合もある。
【００２０】
本説明において、用語「に結合される」又は「と結合する」等は、更なる条件無しに本明細書中に用いられる場合、間接的又は直接的な電気的接続を説明することを意図している。例えば、第１のデバイスが第２のデバイスに結合する場合、その接続は、その経路に寄生成分のみ存在する直接的電気的接続を介し得、又は他のデバイス又は接続を含む介在要素を介する間接的電気的接続を介し得る。間接的結合では、介在要素は、概して、信号の情報を変更しないが、その電流レベル、電圧レベル、及び／又はパワーレベルを調整し得る。
【００２１】
図１は、開示される種々の実施形態に従った、ＯＦを判定及び適用するシステム１００に対するブロック図である。システム１００は、少なくとも１つの画像センサ１０６、画像プロセッサ１０２、及び制御システム１０８を含む。画像プロセッサ１０２は、マイクロプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、又はマイクロコントローラユニット（ＭＣＵ）であり得る。画像プロセッサ１０２は、１つ又は複数のプロセッサ及びストレージを含む。画像センサ１０６は、電荷結合デバイス（ＣＣＤ）、相補型金属酸化物半導体（ＣＭＯＳ）画像センサ、又は光を電気信号に変換するその他の光検出器を含み得る。画像センサ１０６は、二次元アレイに配列された複数の光検出器を含み得る。画像センサ１０６は、画像センサ１０６の視野を表す画像を周期的に捕捉し得る。例えば、画像センサ１０６は、１秒間に１５、３０、６０、又は任意の適切な数の画像を捕捉し得る。画像センサ１０６はデジタルビデオカメラに組み込まれ得る。幾つかの開示される実施形態は、複数の画像センサ１０６を用いるとき等に、複数の画像センサ１０６を含み得る。
【００２２】
画像センサ１０６によって捕捉される画像は、バイナリ値の１つ又は複数のアレイとして画像プロセッサ１０２に提供され得、各バイナリ値が、画像センサ１０６の特定の光検出器（即ち、ピクチャエレメント（画素））で検出される光の強度又は色を表し得る。画像センサ１０６によって画像プロセッサ１０２に提供される各画像はフレームと称され得る。画像プロセッサ１０２は、画像１１０から情報を抽出するために、画像センサ１０６から受け取る画像１１０を分析又は操作する。画像プロセッサ１０２は、画像１１０に存在する種々のエレメント又は特徴のオプティカルフローを測定するために、画像センサ１０６から受け取る画像１１０を分析する、図１に「オプティカルフロー」１０４として示されるＯＦ判定ロジック（オプティカルフローロジック）を含む。本明細書において上述したように、説明される画像プロセッサ１０２はＨＷＡによって実装され得る。
【００２３】
オプティカルフローロジック１０４は、大きな範囲（即ち、様々な異なる距離値）にわたって正確で高精度のＯＦ推定を得るために、（上述したように）ＰＢＭ法と変形ＬＫ法と組み合わせる、開示されるＱＰ−ＯＦＭアルゴリズムを適用する。ＰＢＭ法は、整数画素解像度を備えるＯＦ推定を実施し、その後、得られたＯＦ推定を、変形ＬＫ法の少なくとも１パスを用いて精密化して、分数画素解像度を有する修正されたＯＦ推定を得る。精密化されたオプティカルフロー推定は、潜在的にノイズが多い推定をフィルタ除去するために、事後処理フィルタを用いてフィルタリングされ得る。後述するＨＷＡの実装では、概して、変形ＬＫの１パスのみが用いられる。しかしながら、他の実装では、繰り返しが多くなるとメモリからの画素データの補間及び反復フェッチが必要となり得るため、計算複雑性と便益との間でバランスをとることが一般的に最良である。
【００２４】
ＰＢＭ法は、本明細書において用いられる場合、ビデオのフレームの各々を階層的な画像ピラミッドに変換するＯＦ推定方法を指す。画像ピラミッドは複数の画像レベルを含む。画像レベルが１つ高くなる毎に画像解像度が下がる。各画像レベルに対して、及び第１のフレームにおける各画素に対して、プロセッサが、第２のフレームにおける画素の位置の初期推定を、コスト関数を最小化する所定の値又は候補位置に確立するように、及びコスト関数を最小化し、第２のフレームにおける画素の位置の精密化された推定を確立する、初期推定から開始する複数の連続サーチを適用するように構成される。
【００２５】
ＬＫ法は、本明細書で用いられる場合、Ｂｒｕｃｅ  Ｄ．Ｌｕｃａｓ及び金出武雄によって開発された差動ＯＦ推定方法の変形バージョンを指す。ＬＫ法は、オプティカルフローが、検討下の画素の局所的近傍において本質的に一定であることを想定し、その近傍における全ての画素に対し、基本的なオプティカルフローの式を最小二乗法規準によって解く。幾つかの近隣の画素からの情報を組み合わせることによって、ＬＫ法は、オプティカルフロー式の固有の曖昧性を解決することができる。
【００２６】
ＬＫ法は、画像における画素に対して定義されたＯＦ式を、その画素の近傍からの勾配情報及び最小二乗法原理を用いて、下記の関係を用いて、解くことができる。
2019504394.tif 000003
ここで、水平及び垂直フロー成分は、それぞれＵ及びＶであり、Ｇｘ、Ｇｙは、第１のフレームに対して計算された水平及び垂直空間的勾配であり、Ｇｔは、ＯＦが推定される２つの画像の間で計算された時間的勾配である。従来のＬＫ法は、第２の画像のワーピング（動き補償）を実施した後、各反復において、画素毎にＯＦを計算する。Ｇｘ、Ｇｙは、画素のｎ×ｎ（ｎ＝３、５、７等）近傍にわたる全ての画素に対して定義され、「°」演算子は２Ｄベクトルのエレメント幅積算を定義する。上記式において、２×２行列が非可逆である場合、即ち、その行列式がゼロである場合、それは正規化され得るか又はＵ及びＶがゼロに設定され得る。
【００２７】
開示されるＱＰ−ＯＦＭアルゴリズムによって用いられる変形ＬＫ法に関し、入力は、上述と同じＧｘ、Ｇｙ、及びＧｔであるが、それぞれ水平及び垂直フロー成分Ｕ及びＶを得るためステップサーチプロセス（後述する）の間に計算される。実数であるＵ及びＶフロー成分は、例えば分数部をストアするために割り当てられる４ビットを用いる等の、固定小数点表現で表される。これらのフロー値は、後述する方法２００において「初期ＯＦ推定」と称される既存のＯＦ推定Ｆ１ｉｎｔ（ＰＢＭ法によって整数画素解像度で得られる）の段階的に増加する精密化を表す。これは、分数画素解像度を備える一層高い正確性を有し、方法２００において、「修正されたＯＦ推定」を得るための処理を受ける。Ｕ及びＶの値は、最終フロー出力Ｆ１を得るために、既存のフロー推定に付加される前に、［−１、１］の範囲内にクランプされ得る。この演算は、下記の式で表され得る。
Ｆ１＝Ｆ１ｉｎｔ＋ｃｌａｍｐ（（Ｕ，Ｖ），−１，１）
【００２８】
一実装において、固定小数点におけるクランプ演算（その行列の随伴行列を用いる逆行列計算に含まれる除算を含む）が続く、Ｕ及びＶ計算が、下記に示すように、乗算、加算、及び比較のシンプルな整数演算のみを用いて実装され得る。
2019504394.tif 000004
2019504394.tif 000005
ここで、
2019504394.tif 000006
及び、
2019504394.tif 000007
である。Ｕ及びＶの全ての可能な値は、４ビットの分数部分を用いて適切な固定小数点表現において表され得る。
【００２９】
開示される変形ＬＫ法は、既知のＬＫ法において用いられる上述の画像ワーピングを除去する。画像ワーピングステップは、局所的な近傍におけるＯＦが本質的に一定であり、検討下の画素に等しいということを想定し、１パスを用いることによって除去される。有意義なこととして、これによって、ステップサーチプロセスの間にフェッチされる画素データを、Ｇｔ計算のために再利用することが可能になる。これは、メモリに対するランダムアクセスが回避できるため特に有用である。また、上述したように、変形ＬＫ法は計算を、空間的勾配計算と、演算の残りとのサブタスクに分離する。
【００３０】
修正されたＯＦ測定は、画像プロセッサ１０２によって生成される最終出力ＯＦ推定１１２を得るために、事後処理フィルタ（後述する図３の事後処理フィルタ３０６を参照）を用いてフィルタリングされ得る。最終出力ＯＦ推定１１２は制御システム１０８に提供され得る。制御システム１０８は、システム１００の動きを制御し、動き情報をシステム１００のユーザ等に提示する等のため、修正されたＯＦ測定１１２を適用し得る。例えば、システム１００が先進運転支援システム（ＡＤＡＳ）である場合、制御システム１０８は、画像プロセッサ１０２によって検出された車両及びオブジェクトの相対的動きに基づいて、車両が速度及び／又は方向を変更するべきか否かを判定するために、修正されたＯＦ測定１１２を適用し得る。幾つかのＡＤＡＳ実装において、制御システム１０８は、修正されたＯＦ測定１１２に少なくとも部分的に基づいて、車両の速度及び方向を自律的に変更し得、他の実施形態では、制御システム１０８は、修正されたＯＦ測定１１２に基づいて、速度及び／又は方向における変更が賢明であり得るという警告を車両の操作者に提供し得る。同様に、ロボット工学及び他の動き制御応用例において、制御システム１０８は、修正されたオプティカルフロー測定１１２に基づいて、システム１００のエレメントの動き（速度及び／又は方向）を制御し得る。
【００３１】
図２は、例示の実施形態に従った、開示されるＱＰ−ＯＦＭを用いるＯＦ測定の例示の方法２００におけるステップを示すフローチャートである。この例において、変形ＬＫ法はピラミッドのベースレベルでのみ適用される。ステップ２０１は、ビデオ（例えば、参照画像）の第１のフレーム及びビデオ（例えば、クエリ画像）の第２のフレームを取得することを含み、これらは、時間的及び空間的に序列された画像の少なくとも１つを提供する。任意選択で、画像速度のパラメトリックモデルから導出される、ストアされた履歴フロー推定又は予備推定も、ＰＢＭプロセスの間、予測子として用いられるべき画像速度の事前証拠（prior evidence）として提供され得る。通常動作において、ＱＰ−ＯＦＭアルゴリズムは、与えられる入力が２つの時間的に序列化された画像であり、任意選択で、画像速度の証拠を提供する事前／予備フロー推定を伴うとき、動きを瞬間画像速度（画素の動き）として推定する。
【００３２】
ステップ２０２は、ステップ２０３及び２０４を実施するストアされたＱＰ−ＯＦＭアルゴリズムを実装するプロセッサを用いることを含む。ステップ２０３は、整数画素解像度を有する初期取得フロー推定を生成するために、ＰＢＭ法を用いて第１のフレームと第２のフレームとの間でオプティカルフロー推定することを含む。ＰＢＭ法は、空間的予測子と、正確な動き推定を得るためのコスト関数値を最小化するステップサーチ方法（後述する）ベースのブロックマッチング（ＢＭ）プロセスとを用いて、最も高いピラミッドレベルでオプティカルフロー推定を開始する。これらのオプティカルフロー推定は、その後、（例えば、２Ｄ  ５×５のメディアンフィルタを用いて）フィルタリングされ、適切にスケールアップされ、更にその後、ベースピラミッドレベルまで順次、より低いピラミッドレベルにおいて精密化される（ここでも、空間的予測子及びステップサーチ方法を用いる）。ベース層でのＢＭプロセスの後、ＯＦ推定のフィルタリング又はスケーリングは必要ない。一実施形態において、適切なコスト関数はバイナリ特徴記述子に対するハミング距離である。
【００３３】
ベースピラミッドレベルにおいて、予測子構成は、時間的予測子又は予備予測子を含むように変えられ得るが、ステップサーチは同じままであり得る。ベースピラミッドレベルにおいて、ＰＢＭプロセスが完了した後、得られたフロー推定を精密化するように、変形ＬＫステップのパス（後述するステップ２０４）が実施されて、高精度の画素動きの判定を可能にする分数画素解像度を有する修正されたオプティカルフロー推定が得られる。別の実施形態に従って、変形ＬＫ法のパスは、ＢＭプロセスの後、一層高いピラミッドレベルを処理する間にも適用され得る。
【００３４】
計算及びデータ帯域幅を低減するために、各画素をＢＭ処理する代わりに、各ピラミッドレベルにおいて２×２パクセル（２×２ブロックの近隣の画素）粒度でＢＭプロセスが作動し得る。その場合、予測子評価及びステップサーチ等の異なる計算ブロックが４画素上で同時に作動し得る。この方法はまた、１×１（＝１画素）、３×３、２×４等を含む全ての可能なパクセル構成に適用され得るが、実験では、所望の品質及びＨＷＡ効率のためには、２×２パクセルが最良であることが分かっている。そのようなスキームにおいて、ＯＦの最良の推定（ウィナーの予測子）を判定するために、パクセルの中の１つの代表的な画素に対してのみ、予測子が評価される。ＯＦの最良の推定（ウィナーの予測子）は、その後、ステップサーチプロセスの間、そのグループの全ての画素に対して独立して精密化される。
【００３５】
フロー事後処理は、サイズが５×５（高さ×幅）等の２Ｄメディアンフィルタ（後述する図３のフロー事後処理フィルタ３０６参照）の利用に関与する。事後処理ブロックは、入力としてＯＦ推定（Ｆｉ）を受け取り、フィルタリングされたＯＦ出力（Ｆ）を生成する。代替的に、サイズ９×９等の疑似１Ｄ分離可能メディアンフィルタが用いられ得る。９×９フィルタは、３×９フィルタと９×３フィルタに分離され得、それらは、この順に（又は逆順に）逐次適用される。フィルタの高さ及び幅は、メディアン計算に用いられるフローサンプルの数（２７）が少なく、しかも高品質事後処理を提供するように構成される。このケースでは、境界画素をフィルタリングするために、全てのサイドのフローフィールドの４画素のボーダー拡張が実施される。コンフィデンスアサイメントブロック（後述する図３におけるコンフィデンスアサイメントブロック３０７）は、各画素に対してコンフィデンスレベルをアサインするために、学習ベースのフレームワークにおける取得されたフロー推定のＰＢＭステップ及び局所的変動の間に計算されるコスト関数値を用い得る。
【００３６】
ステップ２０４は、分数画素解像度を有する修正されたＯＦ推定を提供するために、変形ＬＫ法の少なくとも１パスを用いて、初期ＰＢＭ取得されたフロー推定を精密化することを含む。上述したように、変形ＬＫ法は、従来の画像ワーピングステップを除去するように既知のＬＫアルゴリズムを変更し、計算ステップを、勾配計算（空間的及び時間的）演算と残りの演算との２グループに分離する。そのため、このＬＫステップは、分数画素精密化を実施するために、ＰＢＭ法によってフェッチされたデータを再利用する。ＬＫステップは、ＯＦ精密化のために低精度勾配データを用い得る。ＬＫステップはまた、行列反転を含む計算タスクを実施するために、整数演算のみを用い得る。
【００３７】
上述したように、この方法は、事後処理フィルタリング（後述する図３のフロー事後処理フィルタ３０６参照。フロー事後処理フィルタ３０６は、ＱＰ−ＯＦＭアルゴリズムブロック３０４によって出力されるフローベクトルをフィルタリングする）を任意選択で含み得る。例えば、推定されたフローベクトルからインパルス性ノイズを除去するために、疑似１Ｄ分離可能メディアンフィルタが、用いられ得る。
【００３８】
図３は、ＱＰ−ＯＦＭアルゴリズムブロック３０４を含むＯＦ計算ブロック３０２に対する入力３１０を含む例示のＱＰ−ＯＦＭ配置３００の簡略化されたブロック図を示す。ＯＦ計算ブロック３０２は出力３１２を提供する。入力３１０は、概して、２つのグレースケール画像である。画素毎に１つのバイナリ値として表されるクロマチャネル情報の任意の１つを用いることもできる。クエリ画像が画像１として示され、参照画像が画像２として示され、それらの間で、ＱＰ−ＯＦＭスキーム配置によってＯＦが測定／推定される。事前／予備オプティカルフロー推定は、その他の入力として提供される。そのような事前推定は、現在のオプティカルフロー推定に時間的に先行し、概して、入力画像（画像１及び画像２）の解像度と同じ解像度で提供され、各画素又はパクセルに対して推定される期待密度の１００％を有する。
【００３９】
画像ピラミッド生成ブロック（ピラミッド生成として示される）３０４ａは、画像２及び画像１を含むグレースケール画像（Ｉ）、ピラミッドレベルのプログラムされた数Ｎ、及びガウス（Gaussian）フィルタカーネルを導出するために用いられるべき（例えば、プロセッサからの）シグマ値（Ｓｇ）を含む入力３１０を受け取る。画像ピラミッド生成ブロック３０４ａは、ピラミッドにおけるｎ番目毎の画像が、（ｎ−１）番目のレベルの画像の水平及び垂直の両寸法において半分の解像度となるように、画像のＮレベル多解像度表現の画像ピラミッドを出力する。画像ピラミッド生成ブロック３０４ａは概して事前処理を提供する。入力画像が寸法Ｗ×Ｈを有し、画像ピラミッドがＮレベルを有する場合、幾つかのケースでは結果の画像寸法Ｗ’×Ｈ’が２（Ｎ−１）又は２（Ｎ）の倍数であるように、画像は、底部及び右側でパディングされ得る。パディングされた画素は、値０を有し得る。パディングされた画像をＩ’と称する。
【００４０】
画像ピラミッド生成ブロック３０４ａに対する例示の処理を下に記載する。
Ｐｉはｉ番目のピラミッドレベルにおける画像を表す。
初期化：Ｐｉ＝Ｉ’、サイズ５×５の２ＤガウスフィルタカーネルＧを導く
（ｉ＝２；ｉ≦Ｎ；ｉ＋＋）の場合、％ｉは画像ピラミッドにおけるレベルを表す。
ガウスフィルタカーネルＧを用いてＰ（ｉ−１）をフィルタリングして、フィルタリングされた画像Ｐ’（ｉ−１）を得る。
両方の方向においてＰ’（ｉ−１）の交互の画素を選ぶことによって、スケールダウンされた画像Ｐｉを得る。
終了
【００４１】
ピラミッド生成ブロック３０４ａに加えて、ＱＰ−ＯＦＭアルゴリズムブロック３０４も、ブロックマッチングオプティカルフロー推定ブロック３０４ｂ（ＰＢＭプロセスに含まれるブロックマッチング、濾過、及びスケーリング機能性を実装する（ステップ２０３））及びオプティカルフロー推定ブロック３０４ｃ（変形ＬＫを実装する（ステップ２０４）ため）の差動技法ベースの局所的方法を含む。ブロック３０４ｂ及び３０４ｃは、ピラミッドの頂部から開始し、一度に１つのピラミッドレベルを処理する。ブロック３０４ｃは、一実施形態では、ピラミッドのベースに対してのみイネーブルされ、他の実施形態では、全てのレベルでイネーブルされる。ブロックマッチングオプティカルフロー推定ブロック３０４ｂは、整数画素精度を備えるＯＦ推定を提供する。オプティカルフロー推定ブロック３０４ｃは、分数画素解像度を備える修正されたＯＦ推定を提供する。ブロック３０４ｂの濾過及びスケーリング機能性は、ブロック３０４ｃがピラミッドのベースに対してのみイネーブルされる実施形態の場合、ピラミッドのベースでディセーブルされ得る。ブロック３０４ｃが全てのレベルでイネーブルされる実施形態では、ブロック３０４ｂの濾過及びスケーリング機能性は、ピラミッドのベースに対してディセーブルされ、また、一層高いレベルに対して、これらの機能性は、（ブロック３０４ｂによって得られた）ＯＦ推定の（ブロック３０４ｃによる）修正の後、用いられる。
【００４２】
上述したように、ピラミッド生成ブロック３０４ａに対する入力は、オプティカルフローが推定されるべき２つのグレースケール画像（クエリ画像及び参照画像）、及び履歴的画像速度推定又は時間的予測子（寸法Ｗ’×Ｈ’画素の全て）を含む。時間的予測子は、オプションの入力であり、それらのマルチスケール表現は、図３において点線の軌道で示されるように、ピラミッド生成ブロック３０４ａによって取得されない。
【００４３】
ＱＰ−ＯＦＭアルゴリズムブロック３０４は、ｉ＝＝１（即ち、ベース解像度）の場合、次のピラミッドレベル（Ｆｉ−１）又は精密化されたフロー推定（Ｆｉ）に対する、適切にフィルタリング及びスケーリングされたフローベクトルを含むフロー推定を出力する。ＱＰ−ＯＦＭアルゴリズムブロック３０４出力は、ベースレベルより高いレベルに対しては、ＱＰ−ＯＦＭアルゴリズムブロック３０４内で消費され、ベースレベルに対しては、フロー事後処理ブロック３０６に及びコンフィデンスアサイメントブロック３０７に送られる。上記に開示されるように、ベースレベル以外のレベルに対して、フローはシンプルな２Ｄメディアンフィルタを用いてフィルタリングされ得、その際、フロー推定解像度は、一層低いレベルにマッチするように増大され、フロー推定は適切なスケールファクタを用いてスケーリングされる。変形ＬＫのパスが全てのピラミッドレベルに適用される場合、その後に丸め演算が続き得る。ベースレベルに対して、ＱＰ−ＯＦＭアルゴリズムブロック３０４出力は、疑似１Ｄ分離可能メディアンフィルタによる事後処理等のためにフロー事後処理ブロック３０６に送られ、コンフィデンスアサイメントのためにコンフィデンスアサイメントブロック３０７に送られる。
【００４４】
また、事前計算処理は、全てのレベルが、整数寸法（dimensions）であり正確に同じスケールファクタ（例えば、０．５）を有するように、（底部及び右に向かって）ＱＰ−ＯＦＭアルゴリズムパディングの前に提供され得る。初期化は、レベルＮに対する０へのフロー推定（ＦＮ）を含む。
【００４５】
或るピラミッドレベルに対し、ＱＰ−ＯＦＭアルゴリズムブロック３０４ｂ及び３０４ｃによって提供される例示のプロセスを下記で説明する。説明されるプロセスは、バイナリセンサス変換ステップ以外のピラミッドレベルに対するものであるが、アルゴリズムブロック３０４ｂは、クエリ画像及び参照画像に対するバイナリセンサス変換によってバイナリ画素記述子を準備するための機能性も提供し得る。
（クエリ画像における全ての２×２パクセル）の場合、％ラスタースキャン順に処理される
・パクセルにおける頂部左画素に対して、予測子のリストを準備する
・予測子の水平及び垂直成分のメディアンを計算する。結果のフローベクトルをメディアン予測子と称する。
・参照画像においてコスト関数値を最小化する最良の予測子（ウィナー予測子）を見つける
・ウィナー予測子を、現在の２×２パクセルにおける全４画素に対して、現在のオプティカルフロー推定として設定する
（クエリ画像において現在の２×２パクセルにおける全画素）の場合、
○  ３−１  サーチ：コスト関数値を最小化する現在のオプティカルフロー推定の周囲で面内（in plane）コース・ツー・ファイン（スキップｐｅｌ−３  ＋  スキップｐｅｌ−１）ブロックマッチングサーチを実施する
・現在のレベルに対してＬＫステップがイネーブルされている場合、スキップ１サーチの間、クエリ画像及び動き補償された参照画像を用いて、クエリ画像に対する水平（Ｇｘ）及び垂直（Ｇｙ）画像勾配データを、時間的勾配（Ｇｔ）とともに計算する。スキップｐｅｌ−１サーチの間にこれらの計算が実施される場合、ＬＫステップは、動き補償に対して、メモリからのいかなるデータフェッチも要求しない。
注：勾配は、センサス変換データではなく、グレーレベル画素情報を用いて計算される。
○  変形ＬＫステップ（：現在のレベルに対してＬＫステップがイネーブルされている場合）
・オプティカルフロー推定における変化を求めるために、画像勾配データＧｘ、Ｇｙ、及びＧｔを用いる
・水平及び垂直両方向における［−１、１］範囲内の変化をクランプする
・このステップにおいて計算されたフロー値を付加することによって、ステップサーチプロセスの間に取得されたオプティカルフロー推定を更新する
終了
終了
（ｉ≠１）の場合、即ち、ベースレベルではない場合、
次のピラミッドレベルに対するフロー推定を取得する
入力：現在のレベルに対するフロー推定（Ｆｉ）
出力：次のピラミッドレベルに対するフロー推定（Ｆｉ−１）
プロセス：
−更新されたフロー推定Ｆｉの２Ｄメディアンフィルタリングを実施する
−フロー推定解像度をアップスケールする
−適切なスケールファクタを用いてフロー値をスケーリングし、一番近い整数値に丸める
そうでない場合、
入力：分数画素精度でのフロー推定（Ｆ１）
出力：事後処理されたオプティカルフロー（Ｆ）
プロセス：
−取得されたフロー推定Ｆ１の事後フィルタリングを実施して、オリジナル画像寸法に対する出力フローＦ  Ｃｒｏｐ  Ｆを得る
終了  
【００４６】
上述したように、ＯＦ計算ブロック３０２はまた、フロー事後処理フィルタ３０６を有して示される。フロー事後処理フィルタ３０６は、フィルタリングされていないフローベクトルデータをＱＰ−ＯＦＭアルゴリズムブロック３０４から受け取り、フィルタリングされたフローベクトルデータを出力する。ＯＦ計算ブロック３０２はまた、コンフィデンスアサイメントブロック３０７を有して示される。コンフィデンスアサイメントブロック３０７は、オプティカルフロー推定処理の間に生成されたハミング距離（ＨＤ）コスト、及びフィルタリングされていないフローベクトルをＱＰ−ＯＦＭアルゴリズムブロック３０４から受け取り、コンフィデンスデータを生成する。
【００４７】
フロー事後処理フィルタ３０６は、デンスＯＦ推定出力３１２ｂを提供する水平及び垂直フロー成分を有するフィルタリングされたフローベクトルデータを出力するように示される。アサインされるコンフィデンスデータは、コンフィデンスアサイメントブロック３０７による各画素に対するコンフィデンスレベルであり、コンフィデンスマップ３１２ａに提供されるように示される。デンスオプティカルフロー推定３１２ｂは、概して、入力画像（画像１及び画像２）の解像度と同じ解像度で提供される。その際、１００％の期待密度、及び１６ビットの固定小数点（それぞれ垂直及び水平フロー成分に対して７及び８整数ビット、及びそれら両方に対して４分数ビット）のフロー成分毎画素毎のビット解像度を備える。
【００４８】
ここで、種々のＱＰ−ＯＦＭアルゴリズムステップに対する計算詳細及び図面を説明する。ピラミッド生成ブロック３０４ａにおけるガウスフィルタリング処理について、フィルタリングされた画像から交互画素をドロップすることによって直ぐ上のピラミッドレベル画像が生成され得るように、ピラミッドレベル画像をフィルタリングするためにサイズ５×５のガウスフィルタが用いられ得る。ガウスカーネル微分（Gaussian kernel derivation）が下記で提供される。２−Ｄ（ｘ，ｙ）において、サイズ５×５の等方性ガウスカーネルが下記の形態を有する。
2019504394.tif 000008
ここで、Ｓｇはガウスフィルタカーネルを導出するための距離シグマ値であり、（ｘ、ｙ）はガウスカーネルにおけるフィルタ係数の行及び列位置を表す。５×５フィルタカーネルにおいて、可能な行及び列位置は範囲［０，４］にある。このスキームは１．６１のＳｇ値を用いる。このように得られたフィルタ係数は、固定小数点表現における実数である。フィルタリングプロセス（例えば、別個のＦＩＲフィルタによって実装されるもの）に関し、任意のピラミッドレベル「ｎ」で、上記で定義されたように画像ＰｎをガウスマスクＧと畳み込みをつくることによってガウスフィルタリングされた画像Ｐ’ｎが得られる。
Ｐ’ｎ＝Ｇ×Ｐｎ
畳み込みプロセスの間、境界画素は、各サイドで２つの画素のボーダー拡張を実施することによってフィルタリングされる。
【００４９】
また、バイナリ特徴ベースのコース・ツー・ファインブロックマッチングオプティカルフロー推定ブロック３０４ｂは、バイナリセンサス変換を実施し得る。中央の画素ｘに対する２４ビットのセンサス記述子を計算するための方法が、その２４の近隣子（５×５近傍）、及びそれとの関係を考慮して図４に図示されている。近傍画素に対応するビットが、画素ｘに等しいかそれより大きいグレースケール値を有する場合は、１に設定され、そうでない場合、そのビットは０に設定される。図５は、画素のセンサス署名計算に用いられる５×５近傍画素を図示する。ボーダー画素に対してセンサス変換を計算する間、紛失した画素をリプレースするためにボーダー拡張技法が用いられる。陰影がつけられた領域の中央の四角のボックスは、センサス変換が計算されている中央の画素である。
【００５０】
コスト関数に関し、上述したように、ＰＢＭ法は、予測子評価及びステップサーチの間、コスト関数として、画素記述に対するバイナリセンサス変換、及びハミング距離を用いる。予測／サーチ位置でコスト関数値を評価する一方、クエリ画像における現在の画素の周囲の９×９の四角の近傍（サポートウィンドウ）（サポートウィンドウの図については後述する図６を参照、）及び、参照画像における予測／サーチ位置の周囲の同じサイズの近傍が考慮される。これらの近傍は、クエリデータ及び参照データとして働き、これらは不一致を見つけるためにビット単位で比較される。これをするために、クエリ及び参照データにおける８１画素のバイナリ署名が、２つのバイナリベクトルに連結される。Ｑｖ及びＲｖがこれらのベクトルを表す場合、それらの間のバイナリハミング距離は下記のように計算される。
2019504394.tif 000009
ここで、
2019504394.tif 000010
は、２つのバイナリベクトル間のビット単位排他的論理和演算を定義する。ビットカウント演算は、ビット単位排他的論理和演算の後、１に設定されたビットの数を計算し、出力ＨＤはこれら２つのデータ間のハミング距離である。予測子リスト準備も用いられ得る。予測子は、空間的時間的近隣子に対する既存のＯＦ推定であり、画素に対するブロックマッチングサーチベースのＯＦ推定プロセスのための初期ＯＦ推定として用いられ得る。ＯＦ推定アルゴリズムは、パクセル毎に５つの異なる予測子を用い得る。これらは、図７においてラベリングされているパクセルにおける頂部左画素の４つの近隣子のＯＦ推定を含む。これらは、画像を、左から右、及び頂部から底部にラスタースキャン順で横切るとき、頂部左画素に先行する画素である。
【００５１】
ＨＷＡのパイプライン設計を考慮すると、一層高いピラミッドレベルにおいて導出され、現在のピラミッドレベルに対して適切にスケーリングされた画素に対するＯＦ推定が予測子値であるパクセルにおいて、左予測子は頂部左画素の左近隣子から来ると予期される。この予測子は、ピラミッドの左予測子と称される。代替の設計において、左予測子値は、ＯＦ推定が現在のピラミッドレベルにおいて精密化されており、何らかの画素距離で、頂部左画素の左にある画素から来る可能性がある。この予測子は遅延左予測子と呼ばれ得る。５番目の予測子は、現在の画素に対する既存のＯＦ推定であり、これは、一層高いピラミッドレベルにおいて導出され、現在のピラミッドレベルにおいて適切にスケーリングされる。ベースピラミッドレベルで、ピラミッドの左／遅延左がディセーブルされ、それがイネーブルされるとき、時間的予測子に交換される。予測子の使用が下記の表１に要約され、頂部及び左の空間的予測子を提供する（パクセルにおける頂部−左位置に対する）相対的な画素位置が図７に図示されている。
2019504394.tif 000011
【００５２】
時間的予測子は、分数画素解像度であり得、それは、最も近い整数位置に丸められる。他の空間的予測子値は、対応する画素に対するＯＦ推定の精密化のためのステップサーチの間に、又は一層高いピラミッドレベル推定から取得される。それらは、通常、整数画素解像度であるが、各ピラミッドレベルでＬＫステップを用いる場合は、それらは、分数画素精度であり得、最も近い整数に丸められるべきである。頂部予測子は概してピクチャの頂部行に対して利用可能ではなく、頂部左及び左予測子は、左ボーダー画素に対して利用可能ではなく、頂部右予測子は、右ボーダーに対して利用可能ではない。このシナリオでは、利用可能ではない予測子は、概して、ピラミッド状に同一場所に配置された（co-located）予測子で置き換えられるか、又は（０，０）値に設定されるべきである。最も高いピラミッドレベルでこの目的のためにピラミッド状に同一場所に配置された予測子を用いるとき、それは値（０，０）を取る。
【００５３】
メディアン予測子に対して計算が成され得る。サーチプロセスにおいて用いられるメディアン予測子は、選択された予測子の水平及び垂直成分のメディアンを独立的に探すことによって計算される。
【００５４】
最良の予測子の選択に関し、パクセルにおける頂部左画素の周囲の例示の９×９サポートウィンドウを考慮すると、コスト関数値は、参照画像における全ての予測位置において推定され、最小のコスト関数値を導く予測子がウィナー予測子として選択される。コスト関数値が複数の予測位置に対して同じである場合は、最小値を導く、評価順における第１番目の予測子がウィナー予測子として選択される。例示の評価順は、１）ピラミッドの現在、２）ピラミッドの左／遅延左／時間的、３）頂部右、４）頂部、及び５）頂部左である。頂部右、頂部、頂部左予測子に対する予測子評価は、メモリからのデータ読み出しを最小化するために、頂部行における対応する画素位置に対するステップサーチとマージされ得る。
【００５５】
図８は、現在のパクセルに対する５つの候補予測子と、その中のウィナー予測子とを含む、予測子評価の例示を提供する。ウィナー予測子は、ここでは、パクセルにおけるすべての画素に対する現在のＯＦ推定として設定され、後述するステップサーチプロセスによって更に精密化される。
【００５６】
ステップサーチプロセスの間、コスト関数値が最小化されるように現在のＯＦ推定を精密化するために、面内コース・ツー・ファインサーチが実施され得る。ステップサーチの間に用いられるコスト関数は、ＨＤ＋ＭＶコストとして定義される。ここで、ＭＶコストは、動き平滑性因子（サンプル値として、λ＝２４）と、サーチポイントとメディアン予測子との間のベクトル距離（シティブロック又は水平及び垂直成分の絶対差の和）との積として定義される。サーチは、より広い精密化範囲を提供しつつ、計算複雑性が最小化されるように、特定のパターンで実施される。
【００５７】
ステージ１（スキップ３）において、ウィナー予測子を中心にした９位置（３×３グリッド）位置にわたってスキップ３サーチが実施される。サーチポイントは、現在のオプティカルフロー推定又はウィナー予測子位置から３画素の距離である。３−１ステップサーチプロセス及びコース・ツー・ファインサーチ軌道を図示する図８において、これらの９位置は、パクセルにおける頂部左画素に対する点線のパターン画素によって描かれている。これらの９個の候補位置は、グリッドの頂部左位置から開始して、ラスタースキャン順に評価される。複数のサーチ位置に対してコスト関数値が同じである場合、最小値を導く、評価順における第１番目のサーチ位置が、位置として選択され、ＯＦが適宜推定される。
【００５８】
ステージ２（スキップ１）において、前のステージにおいて取得されたＯＦ推定が、ランダムフィルパターンによってマークされた３×３近傍（スキップ１）における９ポイントにわたってサーチすることによって精密化される。ステージ２のウィナーは、ウィナー予測子の周囲に最良の整数画素動き推定を提供する。複数のサーチ位置に対してコスト関数値が同じである場合、最小値を導く、評価順（ラスタースキャン）における第１番目のサーチ位置がウィナー位置として選択され、ＯＦ推定が適宜更新される。
【００５９】
サーチ範囲制約に関し、任意のピラミッドレベルで、コスト関数値が評価されるべき候補位置（予測子評価又はステップサーチの間）が、水平方向（１９１画素）又は垂直方向（６３画素）のサーチ範囲と称される閾値より大きい距離にある場合、対応するサーチ位置は無視され得る。予測子サーチステップの間の全ての候補位置がサーチ範囲より大きい距離にある場合、現在のオプティカルフロー推定は（０，０）に設定され得る。これは、ピラミッド状に同一場所に配置された予測子値を（０，０）に設定することによって達成され得る。
【００６０】
ウィナー予測子の周囲のコース・ツー・ファインサーチパターンは図９に図示されている。図９は、パクセルにおける２つの頂部画素に対する３−１サーチに対する例示のサーチ軌道、パクセルにおける１つの頂部左画素に対する精密化されたＯＦ、並びに、ステップサーチブロックによって提供される精密化範囲を図示する（異なるパターンの画素は、頂部左画素に対するステップサーチ精密化からの想定され得る結果を示す）。また、図９は、ステップサーチプロセスの開始時の２つの画素に対するＯＦ推定が同じであり得るが、ステップサーチプロセスの間、それらのＯＦ推定が分岐し得ることを図示する。
【００６１】
パクセルの下の方の行に対する予測子の事前評価に関し、ステップサーチプロセスの間の任意の画素で、画素が頂部予測子値の１つを提供するパクセルに対し、予測位置（スキップ１サーチ後の画素に対するＯＦ）は、既にフェッチされ、後の使用のためにストアされている、データ及びコストを用いて評価される。その結果、予測子選択ステップの間、データ読み出しを繰り返す必要がない。
【００６２】
或るレベルに対してＬＫステップがイネーブルされているとき、ＬＫステップにおいて用いられる空間的及び時間的勾配の計算に関し、ＬＫステップブロックによる繰り返しデータ読み出しを避けるために、ステップサーチプロセスの間、これらの計算は全ての画素に対して実施される。この変形ＬＫステップにおいて、クエリ画像における現在の画素の３×３近傍における全ての画素位置に対して空間的及び時間的画像勾配が（グレースケール画素値を用いて）計算される。
【００６３】
水平空間的勾配（Ｇｘ）及び垂直空間的勾配（Ｇｙ）は、中心差分演算子（マスク＝［−１  ０  １］）を用いて計算され、従って、画素が現在の画素の５×５近傍内である必要がある。空間的勾配を計算するために、画像境界でボーダー拡張（必要に応じて、２又は１画素）が用いられる。
【００６４】
３×３近傍における全ての画素に対する時間的画像勾配（Ｇｔ）は、クエリ画像における現在の画素の近傍と、参照画像において、それがそこまで移動されたことが推定される位置（これはスキップ１サーチの間に取得されたウィナー位置である）の同じサイズの近傍とを考慮して計算される。画素単位のＧｔ計算が、参照画像画素値をクエリ画像における対応する画素値から減算することによって実施される。画像境界で、勾配を計算するためにボーダー拡張（１画素）が用いられる。
【００６５】
１２ビット入力画像に対し、空間的及び時間的勾配値は１３ビット精度を有する。この精度は、２ビット右シフトを実施し、事後シフト値を−５１２〜５１１間にクランピングすることによって、１０ビットに低減される。
【００６６】
上述したＰＢＭ法は、整数画素解像度で画素レベルＯＦを推定し、この推定は概ね実際の画素動きに近い。しかしながら、実際の画素動きに一層正確にマッチさせるために、それは更に精密化される。上述したように、ＰＢＭ生成された初期ＯＦ推定を精密化して、分数画素正確性（「修正されたＯＦ推定」）を提供するために、ＱＰ−ＯＦＭアルゴリズムは変形ＬＫ法の少なくとも１パスを用いる。
【００６７】
フロー推定の２Ｄメディアンフィルタリングに関し、ベースピラミッドレベル以外のピラミッドレベルで全てのフロー推定を更新した後、それらはサイズ５×５の２Ｄメディアンフィルタを用いてフィルタリングされ得る。画像境界で、メディアン値を計算するためにボーダー拡張（２画素）が概して用いられる。フロー再サンプリングに関し、２Ｄメディアンフィルタリングの後、ベースピラミッドレベル以外の全てのピラミッドレベルに対し、最も近い近隣子補間を用い、解像度アップスケールファクタ（２）でフローベクトルをスケーリングして、次に低いピラミッドレベルに対するフロー推定が取得される。
【００６８】
フロー事後処理に関し、構成を通じてユーザによってイネーブルされている場合、ＱＰ−ＯＦＭアルゴリズムにおけるフロー事後処理は、サイズ５×５等の２Ｄメディアンフィルタの使用に関与する。事後処理ブロック３０６は、ＱＰ−ＯＦＭアルゴリズムブロック３０４からのオプティカルフロー推定（Ｆｉ）を入力として取り、フィルタリングされたフローベクトルデータとして示されるフィルタリングされたオプティカルフロー出力（Ｆ）を生成する。境界画素をフィルタリングするために、全てのサイドのフローフィールドで２画素のボーダー境界拡張が実施される。代替的に、サイズ９×９（高さ×幅）の疑似１Ｄ分離可能メディアンフィルタが用いられてもよい。９×９フィルタは、３×９フィルタと９×３フィルタとに分けられ、この順に又は逆順に適用される。分離されたフィルタの高さと幅は、メディアン計算に用いられるフローサンプルの数が少なく、しかも高品質事後処理を提供するように構成される。この場合、境界画素をフィルタリングするために、全てのサイドのフローフィールドで４画素の境界拡張が実施される。
【００６９】
ＬＫ及びＨｏｒｎ  Ｓｃｈｕｎｃｋ（ＨｎＳ）等の幾つかの従来のアプローチに比べて相対的に計算要件が低減されているため、これまで可能であったものより高い解像度及びフレーム速度がリアルタイムで達成可能である。
【００７０】
Ｂｅｒｇｅｎ、Ａｎａｎｄａｎ、Ｈａｎｎａ、及びＨｉｎｇｏｒａｎｉによって開示された階層的モデルベースの動き推定アプローチ等、その他のソリューションに対する、開示されるＱＰ−ＯＦＭアルゴリズムの他の幾つかの違いには、（ａ）予測子及び動き平滑性因子を用いるコース・ツー・ファインサーチの形態、（ｂ）オプティカルフロー推定正確性を改善するための履歴的画像速度推定（オプション）の使用、（ｃ）パクセル（画素の２×２ブロック）の処理順を選択すること、及びパクセル全体に対して同じセットの予測子を用いることによる、画素毎の予測子評価要件の低減、（ｄ）画素に対するステップサーチ精密化の間の、頂部右、頂部、及び頂部左予測子の事前評価による、予測子評価に対するランダムメモリアクセスの低減、（ｅ）分数画素動きを推定するためにブロックマッチング方法とＬＫステップとの組み合わせを全般的に用いること、及び計算要件において大きな削減を達成することによる、アルゴリズムから補間の除去、（ｆ）ブロックマッチング処理の間の空間的勾配及び時間的勾配の事前計算、（ｇ）疑似１Ｄ分離可能フィルタの使用、及び、（ｈ）予測子の数及びサーチ解像度を変更することによる、計算要件とオプティカルフロー正確性要件とのバランスを取る能力が含まれる。
【００７１】
開示されるＱＰ−ＯＦＭアルゴリズムの利点には、（ａ）サーチを実施するためのサポートウィンドウに対してバイナリ特徴記述子間で計算がシンプルな最適化関数「ハミング距離」のみを用いること、（ｂ）メモリへのランダムアクセスを最小化するために、画素のグループに対する予測子の共通セットを用い、計算を最小化するために、オプティカルフロー推定に対する非網羅的コース・ツー・ファインサーチ戦略のパターンを用いることによって、貴重なリソースを節約すること、（ｃ）頂部予測子の事前評価が、計算ブロックデータ帯域幅に対するメモリ（コスト関数評価に対する参照画素データをフェッチすること）を節約すること、及びそれにより、設計複雑性を最小化すること、（ｄ）変形ＬＫステップにおいて用いられる空間的勾配及び時間的勾配の事前計算が、メモリブロックデータ帯域幅（たとえば、時間的勾配計算のための参照画素データをフェッチすること）を更に節約すること、及びそれにより、設計複雑性を最小化すること、（ｅ）設計複雑性低減及びＤＤＲ帯域幅低減（後述）の一部として、所望の範囲にわたって、ブロックマッチングサーチ及びＬＫステップをイネーブルするために必要とされる画素をストアするために、現在及び参照ピクチャデータをグローイングウィンドウ様式でストアするためのＬ２、及び参照ピクチャデータのスライディングウィンドウをストアするためのＬ１の、２つのレベルのローカルメモリが用いられ得ること、（ｆ）新しいアルゴリズムを定義するためにパラメトリック（ＰＢＭ）アプローチと非パラメトリック（ＬＫ）アプローチとを組み合わせることによって、分数画素動き推定のために必要とされる多数の補完演算が除去され、これは、既存のアルゴリズムに対すう大きな利点であること、及び、（ｇ）ＬＫステップに含まれる演算であっても、整数演算に関与し、従って、非常に高精度の分数画素動き推定の計算を可能にするために一定数の積算及び加算／減算演算しか必要としないことが含まれる。
【００７２】
開示されるＱＰ−ＯＦＭアルゴリズムは、低レベルで計算集中的であり反復的なＣＶタスクをオフロードすることによって、一層高いプログラム可能計算パワーをＨＷＡに提供するシステムオンチップ（ＳｏＣ）ソリューションとして実装され得る。高レベルの情報を生成するためにあらゆるフレームに対して大量の画素データを処理するカメラベースのＡＤＡＳの基本的ビルディングブロックを形成するＯＦ技法は、ＨＷＡ設計に対する良好な候補として認識される。
【００７３】
図１０Ａは例示のＳｏＣ１０００を図示し、ＳｏＣ１０００は、半導体表面（例えば、シリコン基板）を有する基板１００５（チップ）上に形成され、低レベルで計算集中的であり反復的なＣＶタスクをオフロードすることによって、高いプログラム可能計算パワーをＨＷＡ１０１５に提供する。ＳｏＣ１０００は、汎用プロセッサ（ＧＰＰ）１０１０を含み、ＧＰＰ１０１０は、一般的なコンピュータビジョン及び信号処理及び制御タスクを行う。ＨＷＡ１０１５は、ＯＦ及びステレオディスパリティ測定等の低レベルＣＶタスクを実施する。ＤＳＰ１０２０として示される別のプロセッサが、オブジェクト検出、場面理解、及び再構築等、高レベルビジョン及び信号処理タスクを実施する。システム周辺ブロック１０３０が、プログラム及びデータストレージ１０３０ａを含む。システム周辺１０３０は、センサ、周辺、及び通信デバイスとインタフェースする。基板１０５上の１０２２として示される相互接続（例えば、１つ又は複数の相互接続金属レベル）が、ＧＰＰ１０１０、ＨＷＡ１０１５、及びＤＳＰ１０２０を、基板１００５上のシステム周辺ブロック１０３０に結合する。
【００７４】
図１０Ｂは、参照及び現在のピクチャデータを、ＨＷＡ（図１０Ａに示されるＨＷＡ１０１５等）内のレベル１ローカルメモリ（Ｌ１）及びレベル２ローカルメモリ（Ｌ２）として示されるローカルメモリにストアする、例示のスキーム１０９０の実装詳細を図示する。この実装は、メモリ（例えば、ランダムアクセスメモリ（ＲＡＭ））からＯＦロジックを実装するＨＷＡへのデータの動きを最小化することを目的としている。このスキーム１０９０において、クエリ画像１０５０における全てのパクセルに対してＯＦ推定プロセスの適切な機能を可能にするために用いられるクエリピクチャデータ及び参照ピクチャデータ両方が、それらがメモリ（例えば、ＲＡＭ）から一度のみフェッチされるような方式で、フェッチ及びストアされる。クエリ画像１０５０及び参照画像１０６０が、それらの間でＯＦが推定されるピラミッドレベル画像であり、ＨＷＡが、パクセル１０７０に対するＯＦを計算することに関わる計算タスクを実施している場合、図１０Ｂは、ローカルメモリ内にある必要がある画像画素データの程度を図示する。図１０Ｂにおいて、クエリ画像はＱＩと略され、参照画像はＲＩと略される。
【００７５】
２×２のパクセルサイズ、９×９のブロックマッチングサポートウィンドウ、及び５×５のセンサス署名を計算するために用いられる近傍サイズを用いる実施形態を考慮すると、オプティカルフロー計算に利用可能である必要があるサイズのクエリ画像データは、パクセル位置１０７０の周囲の１４×１４近傍１０５６である。同様に、予測子又はステップサーチ位置の各１つを評価する間、それらの位置の周囲の１３×１３近傍からの画素データが必要とされる。また、水平方向に±１９１画素、垂直方向に±６３画素のサーチ範囲を考慮すると、全ての可能性のある「有効な」予測子及びステップサーチ位置、並びに、必要に応じ、変形ＬＫ計算を評価するために、パクセル位置１０７０の周囲の画素ブロック１０６６において３９６×１４０画素の長方形範囲が必要とされる。画素ブロック１０６６の全体がピクチャ境界内にないとき、サーチ範囲制約の適切なロジック（評価されている位置がサーチ範囲及びピクチャ境界内ある必要がある）が適用される。画素ブロック１０５６及びサーチ位置の周囲の１３×１３近傍がピクチャ境界内に含まれない場合は、適切なボーダー拡張ロジックが適用される。
【００７６】
パクセルの処理の順番が、ラスタースキャン（即ち、左から右及び頂部から底部）であるので、画素ブロック１０５６及び１０６６が同一パターンにおいて画像の上をスライドすることが効果的である。これらの領域におけるデータアクセスの要件及びランダム性を考慮すると、このデータをＨＷＡの内部のローカルメモリにキープすることが有利である。しかし、画素のスライディングブロックのみがローカルメモリにストアされる場合、パクセル位置１０７５等でパクセルデータを処理する間、その位置の周囲の画素ブロック１０５６又は１０６６に類似するブロック全体がメモリ（例えば、ＲＡＭ）からフェッチされる必要があり、その結果、多数の画素を繰り返し読み出すことになり、帯域幅要件が大きく増加し、必要とされるデータでローカルメモリがポピュレートされて（populated）いる間、計算リソースはまたアイドル状態のままでなければならない可能性がある。
【００７７】
これらの制約を克服し、一度のみ画素データをフェッチし、それを近隣のパクセル及びパクセル行にわたって再利用するように、帯域幅要件を低減することが可能である。これに関し、パクセル位置１０７０における全てのパクセルを処理するために必要とされる１４の画素行１０５３全体に対するクエリ画像データが、オンチップローカルメモリの或るパーティションにフェッチされ得、ＨＷＡは、そこから１４×１４画素データの必要とされるセットにわたってアクセスし得る。パクセル位置１０７５に対する処理が開始するとき、画素データ１０５２は破棄され得、メモリブロック１０５３からの画素データの残りがストア（保持）され得、付加的な画素データ１０５４がローカルメモリにフェッチされる。同様に、パクセル位置１０７０におけるパクセルを処理する間に、物理メモリブロック１０６３上の１４０の参照画像画素行は、オンチップローカルメモリの別のパーティションにストアされ得、画素１０６６のスライディングブロックはそこからフェッチされ、データに対するより高速なアクセスを可能にするために、ＨＷＡに更に近い別のメモリにストアされ得る。
【００７８】
また、クエリ画像データに対して行われるメモリ管理と同様に、パクセル位置１０７５に対する処理が開始するとき、参照画像データ１０６２は破棄され得、物理メモリブロック１０６３からのデータの残りは保持され得、付加的な画素データ１０６４が、その行のパクセルの残りの処理のためにローカルメモリにフェッチされる。画素データの行全体を、ローカルメモリにおける１０５３及び１０６３等の物理メモリブロックにストアする様式はグローイングウィンドウと称され得、１０６６等の画素のスライディングブロックをストアすることはスライディングウィンドウと称され得る。一実装では、ｌ０５３、１０６３等の画素データのグローイングウィンドウをストアするために用いられるローカルメモリ、及び１０６６等の画素のスライディングブロックは、物理メモリブロックの論理パーティションであり得る。別の実装において、それらは、メモリブロック１０５３及び１０６３からの画素データがＬ２メモリにストアされ得、画素１０６６のスライディングブロックに対応するデータがＬ１メモリにストアされ得るなど、複数の物理メモリブロックにストアされ得る。別の実施形態において、ＯＦロジックを実装するためにプロセッサが用いられるとき、類似のマルチレベルローカルメモリアーキテクチャ及びピクチャデータ管理スキームが用いられ得る。
【００７９】
開示されるＯＦ推定に対する応用例には、動くオブジェクトのセグメンテーション、オブジェクト追跡、接触（衝突）時間推定、深度推定、及び場面理解等のＡＤＡＳタスクを解決することが含まれる。開示されるＯＦ推定は、既知のＤＯＦ推定アルゴリズムと比較して、障害物検出、衝突回避自動緊急ブレーキング等のＡＤＡＳ応用例において改善された性能を可能にする。
【００８０】
完全なＰＢＭベースのＤＯＦアルゴリズムとの比較において、例示の開示されるＱＰ−ＯＦＭアルゴリズムは、画素毎に約２４のサーチ位置のみ評価し、補完を用いず、画素毎におよそ、１．３３センサス変換のみ計算する。これは、変形ＬＫブロックを用いてＯＦ推定の計算の分数を追加することによって達成される、毎秒６千万画素を処理する際の大きな計算の節約を表す。ＱＰ−ＯＦＭアルゴリズムは更に、機能ブロックの計算演算を論理サブセットに分け、それらが、演算のためにフェッチされた画素データを再使用できるように、異なるサブブロックの演算のサブセットをセットに組み合わせることによって、ＨＷＡ設計を簡略化する。この種類の設計の一例は、頂部パクセルのステップサーチ演算の間のパクセルの頂部予測子の事前評価である。別の例は、ステップサーチプロセスの間にＬＫステップによって用いられる空間的及び時間的勾配の事前計算である。異なる機能ブロックの計算タスクのこのような再パッケージングは、開示されるＱＰ−ＯＦＭアルゴリズムに対して米国特許出願公開番号ＵＳ２０１５／０３６５６９６において開示されるアルゴリズムに比べて、ＳＬ２メモリ複雑性のほぼ６倍の低減となっている。
【特許文献１】米国特許出願公開番号  ＵＳ２０１５／０３６５６９６
【００８１】
特許請求の範囲内で、説明された実施形態における変更が可能であり、他の実施形態が可能である。
【図１】
2019504394.tif 000012
【図２】
2019504394.tif 000013
【図３】
2019504394.tif 000014
【図４】
2019504394.tif 000015
【図５】
2019504394.tif 000016
【図６】
2019504394.tif 000017
【図７】
2019504394.tif 000018
【図８】
2019504394.tif 000019
【図９】
2019504394.tif 000020
【図１０Ａ】
2019504394.tif 000021
【図１０Ｂ】
2019504394.tif 000022
【国際調査報告】
2019504394.tif 000023