(57)【特許請求の範囲】
【請求項１】
画像の対の間のオプティカルフロー場を決定するための方法であって、
（ａ）非オクターブ・ピラミッド係数を使用して、前記画像の対の各々を画像ピラミッドに分解するステップ、
（ｂ）前記分解された画像の対における画素の明るさの勾配が一定であるという仮定の下に、前記分解された画像の対を、最初のピラミッド・スケールで、二次導関数表現に変換するステップ、
（ｃ）前記二次導関数画像表現の離散時間導関数を推定するステップ、
（ｄ）生のオプティカルフロー場を発生させるために、オプティカルフロー推定処理を前記離散時間導関数に適用するステップ、
（ｅ）前記生のオプティカルフロー場を、前記非オクターブ・ピラミッド係数によってスケーリングするステップ、および
（ｆ）最後のオプティカルフロー場を発生させるために、すべてのピラミッド・スケールが訪問されるまで、前記画像の対に対して、別のピラミッド・スケールで、ステップ（ｂ）〜（ｅ）を繰り返すステップを備え、ステップ（ｃ）における時空間勾配推定は、以前の生のオプティカルフロー推定によってワープされる方法。
【請求項２】
（ｇ）前記二次導関数画像表現を、色空間からスカラー色距離空間へ変換するステップをさらに備える、請求項１に記載の方法。
【請求項３】
ステップ（ｇ）は、色距離のベクトル減算のラプラシアンを使用して実装される、請求項２に記載の方法。
【請求項４】
ラプラシアン演算子は、前記二次導関数画像表現のすべての色チャネルの強度に別々に適用される、請求項３に記載の方法。
【請求項５】
前記非オクターブ・ピラミッド係数は、１．５以上２．０未満になるように選択される、請求項１に記載の方法。
【請求項６】
前記最初のピラミッド・スケールは、最低解像度のピラミッド・スケールであり、別のピラミッド・スケールは、次のより高い解像度のピラミッド・スケールである、請求項１に記載の方法。
【請求項７】
ステップ（ｃ）は、時空間勾配推定方法を使用して実施される、請求項１に記載の方法。
【請求項８】
前記オプティカルフロー推定処理は、最小二乗適合法を採用する、請求項１に記載の方法。
【請求項９】
非線形の区分線形制約を前記オプティカルフロー場に課す、少なくとも１つの非線形フィルタにより、前記生のオプティカルフロー場を処理するステップをさらに備える、請求項１に記載の方法。
【請求項１０】
前記少なくとも１つの非線形フィルタは、全変動最小化（Ｌ１およびＬ２ノルム）フィルタ、異方性拡散フィルタ、局所的画像構造に反応する楕円ステアラブル・フィルタ、および、カーネル回帰フィルタのうち、少なくとも１つである、請求項９に記載の方法。
【請求項１１】
画素サンプル毎に、前記生のオプティカルフロー場の逆の無矛盾性をチェックするために、複数画素動き補償および差分二乗和計算を、前記生のオプティカルフロー場において行うステップをさらに備える、請求項１に記載の方法。
【請求項１２】
後続のより低い解像度のピラミッド・スケールで、１．５以上２．０未満で非オクターブ（２．０）ピラミッド・スケーリング係数を選択するためのフィードバック機構を提供するために、２Ｄ構造テンソル固有システム解析を前記離散時間導関数に適用するステップをさらに備える、請求項１に記載の方法。
【請求項１３】
前記２Ｄ構造テンソル固有システム解析中に、他のピラミッド・スケールを超える単一のピラミッド・スケールについて、閾値画素割合を下回る小さい固有値に遭遇するとき、前記後続のピラミッド・スケールのうち少なくとも１つについて、より細かいピラミッド・スケールが使用される、請求項１２に記載の方法。
【請求項１４】
前記生のオプティカルフロー場は逆の順序で処理される、請求項１に記載の方法。
【請求項１５】
動きベクトルは、前記画像の対のうち第２の画像を、ロバートのクロス・コンフィギュレーションの５つ以上の位置においてサンプルするために使用される、請求項１４に記載の方法。
【請求項１６】
単一画素アウトライアを除去するために、すべてのピラミッド・スケールについての前記生のオプティカルフロー場を、（非線形）３ｘ３メジアンフィルタ演算によって処理し、前記フィルタされた生のオプティカルフロー場を、Ｌ２ノルム全変動演算子により、可変数の反復の間、処理するステップをさらに備える、請求項１に記載の方法。
【請求項１７】
画像の対の間のオプティカルフロー場を決定するコンピュータコードを格納するコンピュータ可読媒体であって、前記コードは少なくとも１つのプロセッサによって実行され、前記コンピュータコードは、
（ａ）非オクターブ・ピラミッド係数を使用して、前記画像の対の各々を画像ピラミッドに分解すること、
（ｂ）前記分解された画像の対における画素の明るさの勾配が一定であるという仮定の下に、前記分解された画像の対を、最初のピラミッド・スケールで、二次導関数表現に変換すること、
（ｃ）前記二次導関数画像表現の離散時間導関数を推定すること、
（ｄ）生のオプティカルフロー場を発生させるために、オプティカルフロー推定処理を前記離散時間導関数に適用すること、
（ｅ）前記生のオプティカルフロー場を、前記非オクターブ・ピラミッド係数によってスケーリングすること、および
（ｆ）最後のオプティカルフロー場を発生させるために、すべてのピラミッド・スケールが訪問されるまで、前記画像の対に対して、別のピラミッド・スケールで、ステップ（ｂ）〜（ｅ）を繰り返すことを行うためのコードを備え、ステップ（ｃ）における時空間勾配推定は、以前の生のオプティカルフロー推定によってワープされる、コンピュータ可読媒体。
【請求項１８】
（ｇ）前記二次導関数画像表現を、色空間からスカラー色距離空間へ変換するためのコードをさらに備える、請求項１７に記載のコンピュータ可読媒体。
【請求項１９】
（ｇ）は、色距離のベクトル減算のラプラシアンを使用して実装される、請求項１８に記載のコンピュータ可読媒体。
【請求項２０】
前記非オクターブ・ピラミッド係数は、１．５以上２．０未満になるように選択される、請求項１７に記載のコンピュータ可読媒体。
【請求項２１】
前記最初のピラミッド・スケールは、最低解像度のピラミッド・スケールであり、別のピラミッド・スケールは、次のより高い解像度のピラミッド・スケールである、請求項１７に記載のコンピュータ可読媒体。
【請求項２２】
（ｃ）は、時空間勾配推定方法を使用して実施される、請求項１７に記載のコンピュータ可読媒体。
【請求項２３】
前記オプティカルフロー推定処理は、最小二乗適合法を採用する、請求項１７に記載のコンピュータ可読媒体。
【請求項２４】
非線形の区分線形制約を前記オプティカルフロー場に課す、少なくとも１つの非線形フィルタにより、前記生のオプティカルフロー場を処理するためのコードをさらに備える、請求項１７に記載のコンピュータ可読媒体。
【請求項２５】
前記少なくとも１つの非線形フィルタは、全変動最小化（Ｌ１およびＬ２ノルム）フィルタ、異方性拡散フィルタ、局所的画像構造に反応する楕円ステアラブル・フィルタ、および、カーネル回帰フィルタのうち、少なくとも１つである、請求項２４に記載のコンピュータ可読媒体。
【請求項２６】
前記後続のより低い解像度のピラミッド・スケールで、１．５以上２．０未満で非オクターブ（２．０）ピラミッド・スケーリング係数を選択するためのフィードバック機構を提供するために、２Ｄ構造テンソル固有システム解析を前記離散時間導関数に適用するためのコードをさらに備える、請求項１７に記載のコンピュータ可読媒体。
【請求項２７】
前記生のオプティカルフロー場は逆の順序で処理される、請求項１７に記載のコンピュータ可読媒体。
【請求項２８】
動きベクトルは、前記画像の対のうち第２の画像を、ロバートのクロス・コンフィギュレーションの５つ以上の位置においてサンプルするために使用される、請求項２７に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、全体として参照によりその開示が本明細書に組み込まれている、２００８年１０月１５日に出願した米国仮特許出願第６１／１０５，５１５号の権利を主張するものである。
【０００２】
本発明は一般にデジタル画像処理に関し、より詳細には、画像の対の間のオプティカルフロー場（ｏｐｔｉｃａｌ  ｆｌｏｗ  ｆｉｅｌｄ）の自動決定のための方法およびシステムに関する。
【背景技術】
【０００３】
特にビデオフレームおよび／またはフィールドのシーケンスについて、２つの画像の間のオプティカルフロー場を決定することは、符号化、フレームレート変換、ノイズリダクション、その他など、多数の高価値ビデオ処理タスクにおいて、しばしば遭遇するステップである。オプティカルフローを計算するための既知の方法は、いくつかの障害に遭遇する。多数の方法は、低い正確度を欠点として有し、動きベクトルは実際の動きを反映しない場合があり、他のものは精度を欠き、動きベクトルが、制限された領域内の単一画素、または、画素の特定の小部分程度の精度に制限され、さらに他のものは、密度の欠如を欠点として有し、単一動きベクトルは、画素毎ではなく、画像の全体の領域またはブロックについてのみ使用可能である場合がある。加えて、広く様々な計算およびメモリ帯域幅コストが、これらの方法のうち、全部ではないとしても多数に生じる。
【０００４】
既存の方法は、大まかに３つのカテゴリに分類される場合があり、すなわち（１）ブロックベースのマッチング、（２）位相ベースの推定、および（３）勾配ベースの推定である。ブロックベースのマッチング方法は、それらの比較的小さい複雑性および直観性のため、ビデオ符号化および他のリアルタイムタスクにおいてしばしば使用される。しかし、ブロックベースのマッチング方法は、ブロック探索の範囲によって、ダイナミックレンジが制限され、ブロック探索の細かさによって精度が制限され、サブピクセルレベルで画素値をサンプルするために使用された補間器の正確度が制限され、「開口問題（ａｐｅｒｔｕｒｅ  ｐｒｏｂｌｅｍ）」として知られるものにより、正確度が制限される。勾配に沿ってテクスチャまたはエッジ差のないブロック間の十分な差の欠如により、ブロックマッチング法が誤った動きベクトルを推定するとき、「開口問題」は発生し、その結果、大域的最小ではなく局所的最小での動きベクトルとなる。従来技術のブロックベースのオプティカルフローおよび動き推定法は、開口問題を欠点として有し、開口問題は、探索の深度および幅を、網羅的探索のものから低減するために、マルチスケールまたは他の技術を使用することによって、探索の複雑性を低減しようと試みるブロックベースの方法において、さらに悪化される。多数のブロックベースの方法は、オプティカルフロー推定の絶対的な（または粗いものでさえ）正確度を必要としないことによって、開口問題を回避する。このような方法は、観察中の２つのフレームの間の動き補償ステップにおいてオプティカルフロー場を適用した後に残された、残りの差のみを符号化する。結果として、動き補償ブロックベースの方法は、低減された正確度という犠牲を払って、ビデオ符号化の分野において幅広い応用を見出している。
【０００５】
位相ベースの動き推定技術は、「Ｔｈｅ  Ｅｎｇｉｎｅｅｒ’ｓ  Ｇｕｉｄｅ  ｔｏ  Ｍｏｔｉｏｎ  Ｃｏｍｐｅｎｓａｔｉｏｎ」、Ｊｏｈｎ  Ｗａｔｋｉｎｓｏｎ著、１９９４年、Ｓｎｅｌｌ  ＆  Ｗｉｌｃｏｘ  Ｌｔｄ．、２３〜３８頁に記載された位相ベースの動き推定方法など、比較的正確、精密で、実質的に雑音免疫のオプティカルフローを計算するために採用されている。しかし、位相ベースの動き推定は、周波数領域において行われ、その中で計算された位相情報に従って動作し、したがって、入力画像が２Ｄ周波数領域に変換されることを必要とし、ビデオのためには非常に計算的に高価な処理である。計算効率を向上させようとして、ある他の位相ベースの動き推定処理は、ガボールベースの方向に基づいた変換フィルタリングなど、変換のタイプを大域的から局所的へと変更することによって、フーリエベースの位相計算に基づいた処理を超えて漸進的な改善を示している。残念ながら、これらの技術はなお、比較的、大きいフィルタバンクを各画素に順次適用することを含み、結果として高いメモリ帯域幅要件となり、相対的な全体の計算の複雑性およびメモリ帯域幅の要件がわずかに減少するのみである。勾配ベースの推定は、米国特許第５，６２７，９０５号で教示されたような、ＦＬＩＲ（前方監視赤外線）目標捕捉／拒絶のためのオブジェクト・セグメンテーション、および、ＴｈａｎａｋｏｒｎおよびＳａｋｃｈａｉｃｈａｒｏｅｎｋｕｌ、「ＭＣＦＩ−ｂａｓｅｄ  ａｎｉｍａｔｉｏｎ  ｔｗｅｅｎｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ２Ｄ  ｐａｒａｍｅｔｒｉｃ  ｍｏｔｉｏｎ  ｆｌｏｗ／ｏｐｔｉｃａｌ  ｆｌｏｗ」、Ｍａｃｈｉｎｅ  Ｇｒａｐｈｉｃｓ  ＆  Ｖｉｓｉｏｎ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ、ｖ．１５  ｎ．１、２９〜４９頁、２００６年１月で教示されたような、スローモーションおよびフレームレート変換効果のための時間補間ビデオフレーム（「トゥイーン・フレーム」）の計算を含む、いくつかのオフラインおよびリアルタイムの応用例において採用されている。Ｂ．Ｋ．Ｐ．ＨｏｒｎおよびＢ．Ｇ．Ｓｃｈｕｎｃｋ、「Ｄｅｔｅｒｍｉｎｉｎｇ  ｏｐｔｉｃａｌ  ｆｌｏｗ」、Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、ｖｏｌ．１７、１８５〜２０３頁、１９８１年（以下「ＨｏｒｎおよびＳｃｈｕｎｃｋ」）、ならびに、Ｌｕｃａｓ，Ｂ．Ｄ．およびＫａｎａｄｅ  Ｔ．、１９８１年、「Ａｎ  ｉｔｅｒａｔｉｖｅ  ｉｍａｇｅ  ｒｅｇｉｓｔｒａｔｉｏｎ  ｔｅｃｈｎｉｑｕｅ  ｗｉｔｈ  ａｎ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｓｔｅｒｅｏ  ｖｉｓｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｉｍａｇｉｎｇ  ｕｎｄｅｒｓｔａｎｄｉｎｇ  ｗｏｒｋｓｈｏｐ、１２１〜１３０頁（以下「ＬｕｃａｓおよびＫａｎａｄｅ」）で教示された、古典的なオプティカルフロー法は、画素毎に密なオプティカルフロー場を発生させるが、単一画素より大きい大きさの動きベクトルを、信頼性を有して生成することはできず、ひどい雑音、オブジェクト・オクルージョン、および、複雑な非並進運動の存在下で、矛盾したフロー場を欠点として有する。米国特許第５，６８０，４８７号に記載の方法およびシステムは、マルチスケール法を使用することによって、単一画素の制限を克服するが、雑音および／またはオクルージョンの存在下でロバストではない。勾配ベースの推定のさらなる改善は、米国特許第６，３４５，１０６号において教示され、ここでは、推定処理の数学的安定性を確かめるために、あらゆる画素に関連付けられた構造テンソルの固有解析（ｅｉｇｅｎ  ａｎａｌｙｓｉｓ）を介して、各画素の周囲の勾配領域に固有システム解析が適用される。これは、計算された結果を選択的に受け入れるか、または拒否するために使用される場合がある、信頼値の計算を可能にし、それにより、雑音に対する、かつ、開口問題に対するロバスト性を増す。
【０００６】
勾配ベースの推定のもう１つの改善は、Ｎａｇｅｌ，Ｈ．−Ｈ．およびＥｎｋｅｌｍａｎｎ，Ｗ．、「Ａｎ  ｉｎｖｅｓｔｉｇａｔｉｏｎ  ｏｆ  ｓｍｏｏｔｈｎｅｓｓ  ｃｏｎｓｔｒａｉｎｔｓ  ｆｏｒ  ｔｈｅ  ｅｓｔｉｍａｔｉｏｎ  ｏｆ  ｄｉｓｐｌａｃｅｍｅｎｔ  ｖｅｃｔｏｒ  ｆｉｅｌｄｓ  ｆｒｏｍ  ｉｍａｇｅ  ｓｅｑｕｅｎｃｅｓ」、ＩＥＥＥ  ｔｒａｎｓ．Ｐａｔｔｅｒｎ  Ａｎａｌ．Ｍａｃｈ．Ｉｎｔｅｌｌ．、１９８６年９月、８、５６５〜５９３頁（以下、「ＮａｇｅｌおよびＥｎｋｅｌｍａｎｎ」）において教示されたように、シーンおよびオブジェクトのライティングにおける変化に対する計算のロバスト性を増すために、検査中の実際の勾配を推定するために、明るさ（「明るさの恒常性（ｂｒｉｇｈｔｎｅｓｓ−ｃｏｎｓｔａｎｃｙ）の仮定」）ではなく、二次導関数（「勾配の不変性（ｇｒａｄｉｅｎｔ−ｃｏｎｓｔａｎｃｙ）の仮定」）を使用することである。ＮａｇｅｌおよびＥｎｋｅｌｍａｎｎによって使用された手法の欠点は、スケーリングおよび回転など、複雑な動きモデル下で、勾配の不変性の制約が違反されることである。加えて、ＮａｇｅｌおよびＥｎｋｅｌｍａｎｎの方式下での離散空間時空間微分（ｄｉｓｃｒｅｔｅ−ｓｐａｃｅ  ｓｐａｔｉｏ−ｔｅｍｐｏｒａｌ  ｄｅｒｉｖａｔｉｖｅｓ）の推定は、エラーのない実装を問題のあるものにすることが判明している。
【０００７】
前述の従来技術のオプティカルフロー法は、雑音およびオクルージョンの存在下で数学的不安定性を欠点として有し、推定処理の残りが依存する実際の時空間勾配計算の、無矛盾に適用された、しかし大変粗い近似（解析中の実際のサンプル位置でのサンプル値を完全に無視する、中心差分法など）によって、さらに損なわれる。これらの粗い近似は、初期推定処理における不要な誤りにつながり、さらなる複雑性というかなりの犠牲を払ってすべてが実施された、さらに不完全なヒューリスティックス、閾値または制約に基づいて、後続の段階に強制的に推定値をクリーンアップまたは拒否させるものである。
【０００８】
前述の従来技術のオプティカルフロー法は、（１）高い計算複雑性、（２）数値的不安定性による雑音感受性、（３）あるフレームから他のフレームへの画素のオクルージョンを補償できないこと、（４）制限された動きの範囲、（５）シーン内の、または、シーン内のオブジェクトのライティングの変化による明るさの変化の存在下で、フロー場を正確に計算できないこと、および／または（６）離散サンプリングされた勾配場のモデルにおける不正確または不適切な仮定による、正確度の問題、の問題のうち、１つまたは複数をさらに欠点として有する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国仮特許出願第６１／１０５，５１５号
【特許文献２】米国特許第５，６２７，９０５号
【特許文献３】米国特許第５，６８０，４８７号
【特許文献４】米国特許第６，３４５，１０６号
【非特許文献】
【００１０】
【非特許文献１】「Ｔｈｅ  Ｅｎｇｉｎｅｅｒ’ｓ  Ｇｕｉｄｅ  ｔｏ  Ｍｏｔｉｏｎ  Ｃｏｍｐｅｎｓａｔｉｏｎ」、Ｊｏｈｎ  Ｗａｔｋｉｎｓｏｎ著、１９９４年、Ｓｎｅｌｌ  ＆  Ｗｉｌｃｏｘ  Ｌｔｄ．、２３〜３８頁
【非特許文献２】ＴｈａｎａｋｏｒｎおよびＳａｋｃｈａｉｃｈａｒｏｅｎｋｕｌ、「ＭＣＦＩ−ｂａｓｅｄ  ａｎｉｍａｔｉｏｎ  ｔｗｅｅｎｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ２Ｄ  ｐａｒａｍｅｔｒｉｃ  ｍｏｔｉｏｎ  ｆｌｏｗ／ｏｐｔｉｃａｌ  ｆｌｏｗ」、Ｍａｃｈｉｎｅ  Ｇｒａｐｈｉｃｓ  ＆  Ｖｉｓｉｏｎ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ、ｖ．１５  ｎ．１、２９〜４９頁、２００６年１月
【非特許文献３】Ｂ．Ｋ．Ｐ．ＨｏｒｎおよびＢ．Ｇ．Ｓｃｈｕｎｃｋ、「Ｄｅｔｅｒｍｉｎｉｎｇ  ｏｐｔｉｃａｌ  ｆｌｏｗ」、Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ、ｖｏｌ．１７、１８５〜２０３頁、１９８１年
【非特許文献４】Ｌｕｃａｓ，Ｂ．Ｄ．およびＫａｎａｄｅ  Ｔ．、１９８１年、「Ａｎ  ｉｔｅｒａｔｉｖｅ  ｉｍａｇｅ  ｒｅｇｉｓｔｒａｔｉｏｎ  ｔｅｃｈｎｉｑｕｅ  ｗｉｔｈ  ａｎ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｓｔｅｒｅｏ  ｖｉｓｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｉｍａｇｉｎｇ  ｕｎｄｅｒｓｔａｎｄｉｎｇ  ｗｏｒｋｓｈｏｐ、１２１〜１３０頁
【非特許文献５】Ｎａｇｅｌ，Ｈ．−Ｈ．およびＥｎｋｅｌｍａｎｎ，Ｗ．、「Ａｎ  ｉｎｖｅｓｔｉｇａｔｉｏｎ  ｏｆ  ｓｍｏｏｔｈｎｅｓｓ  ｃｏｎｓｔｒａｉｎｔｓ  ｆｏｒ  ｔｈｅ  ｅｓｔｉｍａｔｉｏｎ  ｏｆ  ｄｉｓｐｌａｃｅｍｅｎｔ  ｖｅｃｔｏｒ  ｆｉｅｌｄｓ  ｆｒｏｍ  ｉｍａｇｅ  ｓｅｑｕｅｎｃｅｓ」、ＩＥＥＥ  ｔｒａｎｓ．Ｐａｔｔｅｒｎ  Ａｎａｌ．Ｍａｃｈ．Ｉｎｔｅｌｌ．、１９８６年９月、８、５６５〜５９３頁
【非特許文献６】Ｓｈｉｂａｔａ，Ｍ．、Ｙａｎａｇｉｓａｗａ，Ｔ．、「Ａ  ｓｔｕｄｙ  ｏｆ  ｏｐｔｉｍａｌ  ａｎｇｌｅ  ｏｆ  ｃｏｌｏｒ  ｖｅｃｔｏｒ  ｆｏｒ  ｏｐｔｉｃａｌ  ｆｌｏｗ  ｅｘｔｒａｃｔｉｏｎ」、ＳＩＣＥ、２００７  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ、ｖｏｌ．、ｎｏ．、２５１８〜２５２３頁、２００７年９月１７〜２０日
【非特許文献７】Ｋｅｎｎｅｄｙ，Ｈ．Ｌ．２００７．Ｇｒａｄｉｅｎｔ  Ｏｐｅｒａｔｏｒｓ  ｆｏｒ  ｔｈｅ  Ｄｅｔｅｒｍｉｎａｔｉｏｎ  ｏｆ  Ｏｐｔｉｃａｌ  Ｆｌｏｗ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  Ｂｉｅｎｎｉａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｆ  ｔｈｅ  Ａｕｓｔｒａｌｉａｎ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ  Ｓｏｃｉｅｔｙ  ｏｎ  Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｃｏｍｐｕｔｉｎｇ  Ｔｅｃｈｎｉｑｕｅｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ（２００７年１２月０３〜０５日）．ＤＩＣＴＡ．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ、Ｗａｓｈｉｎｇｔｏｎ，ＤＣ、３４６〜３５１
【非特許文献８】Ｃｈｒｉｓｔｍａｓ，Ｗ．Ｊ．、「Ｓｐａｔｉａｌ  Ｆｉｌｔｅｒｉｎｇ  Ｒｅｑｕｉｒｅｍｅｎｔｓ  ｆｏｒ  Ｇｒａｄｉｅｎｔ−Ｂａｓｅｄ  Ｏｐｔｉｃａｌ  Ｆｌｏｗ  Ｍｅａｓｕｒｅｍｅｎｔ」、Ｃｅｎｔｒｅ  ｆｏｒ  Ｖｉｓｉｏｎ，  Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｓｕｒｒｅｙ、Ｇｕｉｌｄｆｏｒｄ  ＧＵ２  ５ＸＨ，ＵＫ
【発明の概要】
【発明が解決しようとする課題】
【００１１】
したがって、変化するシーンおよびオブジェクトのライティング、複雑な動き、ならびに、オブジェクト・オクルージョンを含む、雑音の多いビデオ画像に操作を加えるためにより適している、正確で、精密で、計算複雑性が比較的低いデジタルオプティカルフロー推定方法およびシステムの必要性がある。
【課題を解決するための手段】
【００１２】
画像の対の間のオプティカルフロー場を決定するための方法およびシステムであって、（ａ）非オクターブ・ピラミッド係数（ｎｏｎ−ｏｃｔａｖｅ  ｐｙｒａｍｉｄ  ｆａｃｔｏｒ）を使用して、画像の対の各々を画像ピラミッドに分解するステップ、（ｂ）分解された画像の対における画素の明るさの勾配が一定であるという仮定の下に、分解された画像の対を、最初のピラミッド・スケール（ｐｙｒａｍｉｄ  ｓｃａｌｅ）で、二次導関数表現に変換するステップ、（ｃ）二次導関数画像表現の離散時間導関数（ｄｉｓｃｒｅｔｅ−ｔｉｍｅ  ｄｅｒｉｖａｔｉｖｅｓ）を推定するステップ、（ｄ）生のオプティカルフロー場（ｒａｗ  ｏｐｔｉｃａｌ  ｆｌｏｗ  ｆｉｅｌｄ）を発生させるために、オプティカルフロー推定処理を離散時間導関数に適用するステップ、（ｅ）生のオプティカルフロー場を、非オクターブ・ピラミッド係数によってスケーリングするステップ、および（ｆ）最後のオプティカルフロー場を発生させるために、すべてのピラミッド・スケールが訪問されるまで、画像の対に対して、別のピラミッド・スケールで、ステップ（ｂ）〜（ｅ）を繰り返すステップを備え、ステップ（ｃ）における時空間勾配推定は、以前の生のオプティカルフロー推定によってワープされる方法およびシステムを提供することによって、上記の問題への対処がなされ、技術的解決法が当技術分野において得られる。
【００１３】
本発明の一実施形態によれば、この方法は、（ｇ）二次導関数画像表現を、色空間からスカラー色距離空間（ｓｃａｌａｒ  ｃｏｌｏｒ−ｄｉｓｔａｎｃｅ  ｓｐａｃｅ）へ変換するステップをさらに備える場合がある。ステップ（ｇ）は、色距離（ｃｏｌｏｒ−ｄｉｓｔａｎｃｅｓ）のベクトル減算のラプラシアンを使用して実装される場合がある。ラプラシアン演算子は、二次導関数画像表現のすべての色チャネルの強度に別々に適用される場合がある。非オクターブ・ピラミッド係数は、１．５と２．０の間になるように選択される。
【００１４】
本発明の一実施形態によれば、最初のピラミッド・スケールは、最低解像度のピラミッド・スケールである場合があり、別のピラミッド・スケールは、次のより高い解像度のピラミッド・スケールである。ステップ（ｃ）は、時空間勾配推定方法を使用して実施される場合がある。オプティカルフロー推定処理は、最小二乗適合法を採用する場合がある。
【００１５】
本発明の一実施形態によれば、この方法は、最高解像度のピラミッド・スケールが幅および高さの整数画像サイズに移ることを保証するために、バイリニア補間を介したプレスケーリング（ｐｒｅ−ｓｃａｌｉｎｇ）・ステップを採用するステップをさらに備える場合がある。この方法は、非線形の区分線形制約（ｐｉｅｃｅｗｉｓｅ−ｌｉｎｅａｒｉｔｙ  ｃｏｎｓｔｒａｉｎｔ）をオプティカルフロー場に課す、少なくとも１つの非線形フィルタにより、生のオプティカルフロー場を処理するステップをさらに備える場合がある。少なくとも１つの非線形フィルタは、非線形ローパス、平滑化、および統計的正則化フィルタのうち少なくとも１つであり、全変動最小化（ｔｏｔａｌ  ｖａｒｉａｔｉｏｎ  ｍｉｎｉｍｉｚａｔｉｏｎ）（Ｌ１およびＬ２ノルム）フィルタ、異方性拡散フィルタ、局所的画像構造に反応する楕円ステアラブル・フィルタ（ｅｌｌｉｐｔｉｃ  ｓｔｅｅｒａｂｌｅ  ｆｉｌｔｅｒ）、および、カーネル回帰フィルタのうち、少なくとも１つである場合がある。
【００１６】
本発明の一実施形態によれば、この方法は、画素サンプル毎に、生のオプティカルフロー場の逆の無矛盾性（ｉｎｖｅｒｓｅ  ｃｏｎｓｉｓｔｅｎｃｙ）をチェックするために、複数画素動き補償および差分二乗和（ｓｕｍ−ｏｆ−ｓｑｕａｒｅ−ｄｉｆｆｅｒｅｎｃｅｓ）計算を、生のオプティカルフロー場において行うことを採用するステップをさらに備える場合がある。この方法は、後続のより低い解像度のピラミッド・スケールで、１．５と２．０の間で非オクターブ（２．０）ピラミッド・スケーリング係数（ｐｙｒａｍｉｄ  ｓｃａｌｉｎｇ  ｆａｃｔｏｒ）を選択するためのフィードバック機構を提供するために、２Ｄ構造テンソル固有システム解析（２Ｄ  ｓｔｒｕｃｔｕｒｅ  ｔｅｎｓｏｒ  ｅｉｇｅｎｓｙｓｔｅｍ  ａｎａｌｙｓｉｓ）を離散時間導関数に適用するステップをさらに備える場合がある。２Ｄ構造テンソル固有システム解析中に、他のピラミッド・スケールを超える単一のピラミッド・スケールについて、閾値画素割合（ｔｈｒｅｓｈｏｌｄ  ｐｅｒｃｅｎｔａｇｅ  ｏｆ  ｐｉｘｅｌｓ）を下回る小さい固有値に遭遇するとき、後続のピラミッド・スケールのうち少なくとも１つについて、より細かいピラミッド・スケールが使用される。
【００１７】
生のオプティカルフロー場は、逆の順序で処理される。動きベクトルは、画像の対のうち第２の画像を、ロバートのクロス・コンフィギュレーション（Ｒｏｂｅｒｔ’ｓ  Ｃｒｏｓｓ  ｃｏｎｆｉｇｕｒａｔｉｏｎ）の５つ以上の位置においてサンプルするために使用される。本発明の一実施形態によれば、この方法は、単一画素アウトライア（ｓｉｎｇｌｅ−ｐｉｘｅｌ  ｏｕｔｌｉｅｒｓ）を除去するために、すべてのピラミッド・スケールについての生のオプティカルフロー場を、（非線形）３ｘ３メジアンフィルタ演算によって処理し、フィルタされた生のオプティカルフロー場を、Ｌ２ノルム全変動演算子（Ｌ２  ｎｏｒｍ  ｔｏｔａｌ  ｖａｒｉａｔｉｏｎ  ｏｐｅｒａｔｏｒ）により、可変数の反復の間、処理するステップをさらに備える場合がある。
【００１８】
本発明は、添付の図面と共に考察された、以下に提示された例示的実施形態の詳細な説明から、より容易に明らかになるであろう。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施形態による、画像の対の間のオプティカルフロー場を計算するための例示的ステップを例示する処理流れ図を示す図である。
【図２】２次元のラプラシアン演算子の離散時間近似を示す図である。
【図３Ａ】１次元の離散時間中心差分演算子（ｄｉｓｃｒｅｔｅ−ｔｉｍｅ  ｃｅｎｔｒａｌ−ｄｉｆｆｅｒｅｎｃｅ  ｏｐｅｒａｔｏｒ）を示す図である。
【図３Ｂ】２次元の離散時間中心差分演算子を示す図である。
【図４Ａ】本発明の一実施形態による、３次元のサンプリング領域の時空間キューブ（ｓｐａｃｅ−ｔｉｍｅ  ｃｕｂｅ）の図である。
【図４Ｂ】本発明の一実施形態による、図４Ａの時空間キューブを使用する推定勾配法（ｅｓｔｉｍａｔｅｄ  ｇｒａｄｉｅｎｔ  ｍｅｔｈｏｄ）を示す図である。
【図４Ｃ】本発明の一実施形態による、図４Ａの時空間キューブを使用する推定勾配法（ｅｓｔｉｍａｔｅｄ  ｇｒａｄｉｅｎｔ  ｍｅｔｈｏｄ）を示す図である。
【図４Ｄ】本発明の一実施形態による、図４Ａの時空間キューブを使用する推定勾配法（ｅｓｔｉｍａｔｅｄ  ｇｒａｄｉｅｎｔ  ｍｅｔｈｏｄ）を示す図である。
【図４Ｅ】本発明の一実施形態による、図４Ａの時空間キューブを使用する推定勾配法（ｅｓｔｉｍａｔｅｄ  ｇｒａｄｉｅｎｔ  ｍｅｔｈｏｄ）を示す図である。
【図５】本発明の一実施形態による、画像の対の間のオプティカルフロー場を計算するためのシステムを示す図である。
【発明を実施するための形態】
【００２０】
添付の図面は本発明の概念を例示するためのものであり、縮尺通りのものではない場合があることを理解されたい。
【００２１】
図１は、本発明の一実施形態による、画像の対の間のオプティカルフロー場を計算するための例示的ステップを例示する処理流れ図を示す。ステップ１０で、画像の対の各々は画像ピラミッドに分解される。画像ピラミッドを生成する処理では、いくつかの線形および／または非線形フィルタのうち少なくとも１つが、分解された画像の対に適用される場合がある。後の推定ステップが大域的最小ではなく局所的最小で固定される問題を低減し、それにより、「開口問題」として知られるものを防ぐために、画像ピラミッドは、１レベルにつき１オクターブ未満の任意のスケーリング係数を使用して分解される場合がある。ステップ１２で、明るさの勾配（または、別法として、明るさの二次導関数）が一定であると仮定される、という仮定の下に、最低解像度の画像ピラミッド・スケールで、分解された画像の対は二次導関数表現に変換される。ステップ１４で、画像の対の二次導関数表現は、色空間からスカラー色距離空間へ変換される。ステップ１６で、二次導関数画像表現の離散時間導関数を推定するために、時空間勾配推定方法が使用される。ステップ１８で、後続のピラミッド・スケールで、１．５と２．０の間で非オクターブ（２．０）ピラミッド・スケーリング係数を選択するためのフィードバック機構を提供するために、２Ｄ構造テンソル固有システム解析が離散時間導関数に適用される。ステップ２０で、生のオプティカルフロー場を発生させるために、既知の制約ベースのオプティカルフロー推定処理が、最小二乗適合法を使用して、離散時間導関数に適用される。ステップ２２で、画素サンプル毎に、制約ベースのオプティカルフロー推定計算の逆の無矛盾性をさらにチェックするために、複数画素動き補償ステップおよび差分二乗和計算が、生のオプティカルフロー場において行われる。ステップ２４で、結果として生じる生のオプティカルフロー場計算は、非線形の、雑音に対してロバストな区分線形制約をフロー場に効率的に課す複合効果を有する、非線形フィルタリングステップによって、さらに処理される。ある実施形態では、非線形フィルタは、雑音に対する感受性を低減し、オプティカルフロー推定の正確度および精度を向上させる、さらなる統計的制約を効率的に課すための、統計的正則化フィルタである。ステップ２６で、オプティカルフロー場は、非オクターブ・ピラミッド係数で乗算され、空間的にスケーリングされ、次のより高い解像度のピラミッド・スケールへ伝播され、そこで、ステップ２８で、時空間勾配計算は、以前のオプティカルフロー推定によって動き補償（ワープ）される。最後のオプティカルフロー場を発生させるために、ピラミッド・スケールのすべてが訪問されるまで、ステップ１２〜２８が、各後続のピラミッド・スケールに対して繰り返される。
【００２２】
本発明の目的は、２つの画像の時空間勾配から正確なオプティカルフロー場を提供することである。ＨｏｒｎおよびＳｃｈｕｎｃｋ、ならびに、ＬｕｃａｓおよびＫａｎａｄｅで概略が述べられた、勾配ベースのオプティカルフローモデルで例示されたように、オブジェクトのシーン／セットの２つの任意の画像サンプルの間のオプティカルフロー場の決定は、複数の解を有するか、解をまったく有さないか、または、解の無限遠（ｉｎｆｉｎｉｔｙ  ｏｆ  ｓｏｌｕｔｉｏｎｓ）を有する場合がある、不良設定逆問題（ｉｌｌ−ｐｏｓｅｄ  ｉｎｖｅｒｓｅ  ｐｒｏｂｌｅｍ）である。不良設定逆問題を制約するには、１つまたは複数の制約が必要である。従来技術で採用されている周知の制約は、「明るさの恒常性の仮定」であり、動きにもかかわらず、２つのサンプルされた画像におけるオブジェクトの明るさは一定のままであると仮定する。サンプルされた画像におけるオブジェクトの表現は、式１によって記述される。
Ｉ（ｘ，ｙ，ｔ）＝オブジェクト（ｘ＋ｕｔ，ｙ＋ｖｔ）  （１）
ただし、ｘ、ｙおよびｔは、観察された光照射野の連続領域時空間位置であり、Ｉは、ｘ、ｙおよびｔによって指定された位置のオブジェクトの強度または輝度であり、ｕおよびｖは、オブジェクトの並進運動を記述するベクトルを表す。明るさの恒常性の仮定に基づく拘束方程式が、偏導関数に関して、式２で示される。
［∂Ｉ（ｘ，ｙ，ｔ）／∂ｘ］・ｕ＋［∂Ｉ（ｘ，ｙ，ｔ）／∂ｙ］・ｖ＋［∂Ｉ／（ｘ，ｙ，ｔ）／∂ｔ］＝０  （２）
【００２３】
ライティングがある画像時間サンプル点から他のものへと変化した２つの画像のセットについて、または、２つの画像サンプル時間の間で、オブジェクトがライトから、影にされた領域へと移動するとき、「明るさの恒常性の仮定」は崩れる。異なるが関連した制約は、ＮａｇｅｌおよびＥｎｋｅｌｍａｎｎにおいて記載されたような「勾配の不変性の制約」であり、「明るさの恒常性の仮定」のように、所与のオブジェクトについての定数を仮定するが、一定であると仮定されている動きに対するオブジェクトの明るさの代わりに、以下の式３に示すように、明るさの勾配（または、別法として、明るさの二次導関数）が一定であると仮定され、ただし、この二次導関数は、図２に例示するような（離散時間）ラプラシアン演算子∇の適用により近似される場合がある。
［∂Ｌ（ｘ，ｙ，ｔ）／∂ｘ］・ｕ＋［∂Ｌ（ｘ，ｙ，ｔ）／∂ｙ］・ｖ＋［∂Ｌ／（ｘ，ｙ，ｔ）／∂ｔ］＝０  （３）
ｂｍｗ
Ｌ（ｘ，ｙ，ｔ）＝∇（Ｉ（ｘ，ｙ，ｔ））
【００２４】
式３における「勾配の不変性の制約」の使用は、動きにもかかわらず、周囲のライティング変化の状況においてさえ、オプティカルフローを決定するために比較中である２つの画像におけるオブジェクトの相対的なエッジの輝度強度およびテクスチャ特徴の強度関係が一定のままであると仮定する効果を有する。この手法は、入力画像の各々を、図２に例示するように、ラプラシアン演算子∇の離散近似により畳み込み、次いで、離散領域内で、元の画像強度サンプルの代わりに、畳み込まれた画像サンプル上に、同じ勾配推定処理を適用することによって、離散領域において近似される場合がある。
【００２５】
画像サンプルの明るさまたは輝度の二次導関数は、色値自体を導入することによって、より具体的かつ選択的にされる場合があるのに対して、従来技術の手法は、典型的には、式４のある近い変分のように、単一の輝度／強度スカラー値を計算するために、カラー画像からのＲＧＢまたはＹＵＶ値を備える３ベクトルのドット積を使用することである。
Ｉ（ｘ，ｙ，ｔ）＝［０．３０，０．５９，０．１１］Ｔ・［ＩＲ（ｘ，ｙ，ｔ），ＩＧ（ｘ，ｙ，ｔ），ＩＢ（ｘ，ｙ，ｔ）］Ｔ  （４）
【００２６】
これは、ＲＧＢまたはＹＵＶ３ベクトルを単一のスカラー値に縮小することによって、この問題を簡素化する（また、元の仮定である、明るさに関して入力データを提示する）が、クロミナンスが輝度に加えて提供する場合があるいかなる潜在的情報をも無視する。例えば、深緑色画素は、より明るい青色画素と数学的に区別不可能となる。ある応用例では、この差は無視してよい場合があるが、他の応用例では、小さい差が重大となる場合がある。
【００２７】
本発明の一実施形態によれば、色距離関数Ｄが、式５において、２つのＲＧＢ（またはＹＵＶ）３ベクトルサンプルＩ１およびＩ２の間で定義される。
ＤＲＧＢ（ｘ１，ｙ１，ｔ１，ｘ２，ｙ２，ｔ２）＝Ｉ１（ｘ１，ｙ１，ｔ１）−Ｉ２（ｘ２，ｙ２，ｔ２）  （５）
ただし、式５における減算は、Ｒ３上の減算のベクトルの向きにおける意味である。色距離関数Ｄは、３次元の色キューブ内の２つの３ベクトル色の間の距離の大きさを効果的に定義することは、当業者には理解されよう。色距離関数Ｄを使用する利点は、なお単一のスカラー値に縮小しながら、輝度に加えて、クロミナンス／色を追加の制約として導入することである。大部分のオブジェクトが固有の明るさにおいて変化する場合、これらは固有の色および明るさを変更しないと仮定することは、妥当である。加えて、ビデオおよび画像処理システムに共通している、多数の同時代のＧＰＵおよびＤＳＰハードウェア・プラットフォームは、このタイプの演算を、単一クロックサイクルの原始的なマシン命令として実装する。
【００２８】
加えて、ＣＩＥ７６、または、より最近では、ＣＩＥＤＥ２０００で定義されたものなど、より精密な色差測定および方法もまた使用される場合があり、これらは参照により本明細書に組み込まれており、計算を、ＤＳＰおよびＧＰＵ計算に適している、容易にベクトル化された演算に縮小する場合があることは、当業者には理解されよう。色差の採用のわずかな副産物は、明るさにおける変化が、負（より薄暗くなる）または正（より明るくなる）の値に関して直観的に表される場合があるが、色ベクトルについての同時に生ずる概念は直観的ではなく、実際には任意であることである。選択されたマッピングは理想的には、所与の画像において起こり得る色の範囲の５０％を、より小さい／負のスカラーマップされた（ｓｃａｌａｒ  ｍａｐｐｅｄ）値として、また、他の５０％を、より大きい／正の値として、重みを加え、大部分の画像およびビデオについて、できる限り均一な分布にするようになる。この全体の手法は、Ｓｈｉｂａｔａ，Ｍ．、Ｙａｎａｇｉｓａｗａ，Ｔ．、「Ａ  ｓｔｕｄｙ  ｏｆ  ｏｐｔｉｍａｌ  ａｎｇｌｅ  ｏｆ  ｃｏｌｏｒ  ｖｅｃｔｏｒ  ｆｏｒ  ｏｐｔｉｃａｌ  ｆｌｏｗ  ｅｘｔｒａｃｔｉｏｎ」、ＳＩＣＥ、２００７  Ａｎｎｕａｌ  Ｃｏｎｆｅｒｅｎｃｅ、ｖｏｌ．、ｎｏ．、２５１８〜２５２３頁、２００７年９月１７〜２０日において前もって論じられているが、好ましい実施形態のために選択されたマッピングは単に、０．０から１．０に正規化された、現在の画素のＵおよびＶを備える２ベクトルの角度を計算することである。
【００２９】
好ましい実施形態は、ライティングおよび照明の変化に対するロバスト性についての強度のラプラシアンを使用することに関して、ＮａｇｅｌおよびＥｎｋｅｌｍａｎｎにおいて見出されたものと類似の技術を採用する場合がある。好ましい実施形態では、色距離のベクトル減算のラプラシアンが、強度−差のラプラシアンの代わりに採用される場合がある。この組み合わせを実践するために、好ましい実施形態では、式６に示すように、ＲＧＢ色空間内か、ＹＵＶ色空間内かにかかわらず、ラプラシアン演算子が画像のすべての「色」チャネルの強度に別々に適用される。
ＬＲ（ｘ，ｙ，ｔ）＝∇（ＩＲ（ｘ，ｙ，ｔ））  （６）
ＬＧ（ｘ，ｙ，ｔ）＝∇（ＩＧ（ｘ，ｙ，ｔ））
ＬＢ（ｘ，ｙ，ｔ）＝∇（ＩＢ（ｘ，ｙ，ｔ））
拘束方程式（複数可）はこのとき、したがって、式７のそれになる。
［∂ＬＲ（ｘ，ｙ，ｔ）／∂ｘ］・ｕ＋［∂ＬＲ（ｘ，ｙ，ｔ）／∂ｙ］・ｖ＋［∂ＬＲ（ｘ，ｙ，ｔ）／∂ｔ］＝０
．．．
［∂ＬＧ（ｘ，ｙ，ｔ）／∂ｘ］・ｕ＋［∂ＬＧ（ｘ，ｙ，ｔ）／∂ｙ］・ｖ＋［∂ＬＧ（ｘ，ｙ，ｔ）／∂ｔ］＝０
．．．
［∂ＬＢ（ｘ，ｙ，ｔ）／∂ｘ］・ｕ＋［∂ＬＢ（ｘ，ｙ，ｔ）／∂ｙ］・ｖ＋［∂ＬＢ（ｘ，ｙ，ｔ）／∂ｔ］＝０
【００３０】
色制約の、二次導関数仮定との組み合わせは、色変化自体ではなく、色値変化の加速度のみが考慮されることを意味し、等しい仮定の輝度強度の赤みを帯びた色から緑色を帯びた色へ変化するオブジェクトの周囲のライティングは、制約に逆らうものではないという意味では、オブジェクトの実際の動きによる可能性がより高いことは、当業者にはさらに理解されよう。強度に加えて、色の追加の情報の組み込みは、評価アパーチャの制限されたサイズの問題、および、解の劣決定性に関連する問題により、そうでなければ区別ができない勾配を区別する助けとなる。
【００３１】
前述の偏導関数の基礎となる時空間勾配の離散領域近似（ｄｉｓｃｒｅｔｅ−ｄｏｍａｉｎ  ａｐｐｒｏｘｉｍａｔｉｏｎ）を構築するとき、サンプリング位置および重み付け係数をモデル化する最善の方法を見出すことが望ましい。解決する必要のある１つの例示的問題は、無矛盾の局所性、上記で開示された近似を保証すること（例えば、ｄＩ／ｄｘ勾配近似が、同じ空間サンプリング位置内で、ｄＩ／ｄｙ勾配近似として行われることを保証すること）である。オプティカルフローの正確度は特に、これらの近似の小さい変動に対して敏感である。この主題への完全な処置のために、Ｋｅｎｎｅｄｙ，Ｈ．Ｌ．２００７．Ｇｒａｄｉｅｎｔ  Ｏｐｅｒａｔｏｒｓ  ｆｏｒ  ｔｈｅ  Ｄｅｔｅｒｍｉｎａｔｉｏｎ  ｏｆ  Ｏｐｔｉｃａｌ  Ｆｌｏｗ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  Ｂｉｅｎｎｉａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｆ  ｔｈｅ  Ａｕｓｔｒａｌｉａｎ  Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ  Ｓｏｃｉｅｔｙ  ｏｎ  Ｄｉｇｉｔａｌ  Ｉｍａｇｅ  Ｃｏｍｐｕｔｉｎｇ  Ｔｅｃｈｎｉｑｕｅｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ（２００７年１２月０３〜０５日）．ＤＩＣＴＡ．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ、Ｗａｓｈｉｎｇｔｏｎ，ＤＣ、３４６〜３５１、および、Ｃｈｒｉｓｔｍａｓ，Ｗ．Ｊ．、「Ｓｐａｔｉａｌ  Ｆｉｌｔｅｒｉｎｇ  Ｒｅｑｕｉｒｅｍｅｎｔｓ  ｆｏｒ  Ｇｒａｄｉｅｎｔ−Ｂａｓｅｄ  Ｏｐｔｉｃａｌ  Ｆｌｏｗ  Ｍｅａｓｕｒｅｍｅｎｔ」、Ｃｅｎｔｒｅ  ｆｏｒ  Ｖｉｓｉｏｎ，  Ｓｐｅｅｃｈ  ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｓｕｒｒｅｙ、Ｇｕｉｌｄｆｏｒｄ  ＧＵ２  ５ＸＨ，ＵＫにおいて見出された教示は、有益である。
【００３２】
一例として、１次元について、図３Ａにおいて例示された、しばしば適用される中心差分演算子を考察する。勾配の測定の局所性は、局所的に０に中心があるように見なされる場合があるが、位置０自体におけるサンプルされた情報は、完全に無視される。また、ｘ軸に沿った前方差分は、ｙ軸に沿った前方差分と共に考察されるとき、図３Ｂに示すように２次元を使用して空間的勾配を推定する。無矛盾に局所的な勾配計算を提供するため、本発明の別の態様によれば、離散サンプリングされた時空間勾配場は特に、図４Ａに示された８画素時空間領域について、式８に示すように、画素サンプルの強度、
【数１】
0005547739.tif 000002
または、別法として、式９に示すように、画素サンプルのラプラシアンの前述の色距離、
【数２】
0005547739.tif 000003
の、一連の近似離散領域偏微分としてモデル化される。
【００３３】
式８および９の勾配計算は、あらゆる近似された偏微分計算において、２×２×２の時空間画素領域のあらゆる画素を含めることによって、無矛盾の局所性を補償し、可能性のある正の２分の１画素の空間サンプリング・バイアス、および、４分の１画素の時間サンプリング・バイアス（すなわち、上記で表されたような勾配は、ＬＲＧＢ（０．０，０．０，０．０）ではなく、位置ＬＲＧＢ（０．５，０．５，０．２５）で測定されると言われる）のために、従来技術では回避されたストラテジである。この時空間バイアスは、前述の推定勾配法を利用する後のステップにおいて扱われる限り、回避される場合がある。実際に、式９の勾配推定方法は、図４Ｂ〜４Ｅに示すように、信号雑音および第１種不連続（ｆｉｒｓｔ−ｏｒｄｅｒ  ｄｉｓｃｏｎｔｉｎｕｉｔｉｅｓ）の存在下で安定している。
【００３４】
式９で表されたような前述の勾配を計算する方法は、例えば、時空間勾配計算によって包含された領域の１画素範囲内で、局所的動きベクトルを計算するためにのみ使用される場合がある限りにおいて、有用である。また、このような計算の局所性を拡大する（オプティカルフローに限定されず、ブロックマッチング、および多数の他の応用例も）目的で周知であるのは、計算が疎密スケール上で評価される疎密（ｃｏａｒｓｅ−ｔｏ−ｆｉｎｅ）ストラテジを実装し、次には、最後のスケールに達するまで、以前のスケールの計算の結果を次のスケールへ伝播させることを目的とした、マルチスケール画像ピラミッドの使用である。
【００３５】
オプティカルフロー推定の特殊な場合では、従来技術の疎密ストラテジは、画像ピラミッドを作成する形式を取り、そこで、周波数エイリアシング、および、元の高さおよび幅の半分の画像を作成する（１オクターブ空間デシメーション）後続の空間内デシメーション（ｄｅｃｉｍａｔｉｏｎ−ｉｎ−ｓｐａｃｅ）（典型的には、０次または１次補間）を防ぐために、ソース画像は、ガウス演算子を近似する畳み込みによりローパスフィルタされ、この処理は、固定数のスケールについて繰り返され、以前のスケールが後続のスケールのための入力を提供する。次いで、オプティカルフロー計算は、最高スケール（最小または最低解像度のピラミッド画像）で行われ、そこで、そのスケールについて、結果として生じるオプティカルフローの大きさのベクトルｕおよびｖ成分は、２で乗算される。それらの結果は、次のスケールの画像をワープさせるために使用され、残りのオプティカルフローが計算され、その結果は、次のスケールをワープさせるために使用される、などとなる。最後のスケールに達するとき、十分に有用な、非局所的なオプティカルフロー場が作成されている。
【００３６】
残念ながら、従来技術の２Ｘ疎密手法は、従来技術のブロックマッチング法について以前に開示された２Ｘ疎密「マルチスケール」手法を使用することによって直面する欠点に類似した、著しい欠点を有し、すなわち、真の、大域的最小の代わりに、問題を良設定にするために使用されるどのような制約にも従って、特定のスケールでの計算が、局所的最小上に固定する場合があることである。
【００３７】
本発明は、２つの重要な改善を有する画像ピラミッドを利用し、すなわち、最初に、本発明は、画像ピラミッドの作成のために、非線形、非ガウス、ローパス、平滑化、または、統計的正則化フィルタを採用し、限定ではないが、全変動最小化（Ｌ１およびＬ２ノルム）フィルタ、異方性拡散フィルタ、局所的画像構造に反応する楕円ステアラブル・フィルタ、カーネル回帰フィルタ、および、他の非線形フィルタが含まれる。線形フィルタリングは主として、画像がデシメートされるとき、空間周波数エイリアシング・アーチファクトを低減するために使用される。このような非線形フィルタリング動作は、雑音に対するロバスト性、および、後のステップの運動境界の周囲の性能を改善する場合がある。より詳細には、本発明の一実施形態によれば、ガウス演算子と共にＬ２ノルム全変動フィルタの単一の反復が、各スケールについて使用される場合があり、雑音感度特性における著しい改善を示すものである。
【００３８】
第２の改善は、本発明の一実施形態によれば、２．０以外のピラミッド生成係数の使用である。２．０以外のピラミッド生成係数は、ひどい雑音障害および強い１次勾配を有する画像の対を処理するために必要とされる。ピラミッド生成係数が整数のスカラー値２から、より小さい、１．０より大きい実数のスカラー値へと減少するにつれて、局所的最小の固定の問題はだんだん顕著でなくなる（特に、係数が１．０に近づくにつれて、メモリストレージ、帯域幅、および、計算複雑性を著しく犠牲にして）。本発明の一実施形態によれば、１．５と２．０の間の任意のピラミッド係数が使用される場合がある。局所的最小の問題は、スケーリング係数がそれぞれ１．７５から１．５へと減少するにつれて、徐々に顕著でなくなるが、雑音に対する感度が犠牲になる。好ましい係数１．７５では、追加のメモリストレージ要件、および、計算複雑性の要件は、５レベルのピラミッドのための係数２．０に対してよりも、約１３％大きく増す場合があるが、細かさにおいて２５％の改善があり、粗いスケールの局所的最小上で固定されるようになる可能性において、比較的大幅な、付随する減少があり、それにより、複雑性対正確度の良い兼ね合いを表すものである。多数の従来技術の手法は、この特定の問題を反復改良の解法により解決し、これらの解法は、所与のスケールで、そのような前述の雑音障害のあるソースに対して、好ましい実施形態の１３％の代わりに、１０，０００％も計算複雑性を増す場合があることに留意されたい。さらに他の手法は、後に非線形の後処理要件、または、統計的な正則化要件を課し（再度、反復の、著しい付随コストを伴う）、所与の画像位置において完全に使用不可能なオプティカルフロー場の結果となる場合がある、構造解析を介して、この問題を、所与の画像位置で完全に解決不可能であると特徴付ける。
【００３９】
非整数ピラミッド値の使用は、非整数サンプリング位置のために、所与のスケールの（１）画像ピラミッド値、および（２）後続の動きベクトル場の両方の反復バイリニア補間が必要とされる場合がある状況の可能性を増す場合があることは、当業者には理解されよう。０次補間が必要とされる場合があるが、０次補間を使用する利点は、大部分のＤＳＰおよびＧＰＵプラットフォームにおける非２Ｘ画像ピラミッドの使用と比較されるときに生じる、著しい推定誤りを上回るものではない。画像値の１次補間は、ＧＰＵプラットフォームにおいてハードウェア・プリミティブ（ｈａｒｄｗａｒｅ  ｐｒｉｍｉｔｉｖｅ）として提供される場合があるが、これは、ＤＳＰまたはＦＰＧＡシステムでは、（少なくとも、効率的には）そうではない場合がある。このため、好ましい実施形態によれば、最初のスケール（最初の、最高の、解像度）が（Ｗ’，Ｈ’）の整数画像サイズに移り、それにより、式１０におけるように、Ｎ個のスケールの深度に対して画像ピラミッドを適用するとき、反復のサンプル間補間の必要性を著しく減らすことを保証するために、バイリニア補間を介したプレスケーリング・ステップが使用される場合がある（または、キュービックまたはバイキュービックなど、より高次のスケーリング演算子）。
Ｗ’＝フロア（ｆｌｏｏｒ）（Ｗ／Ｎ）×ピラミッド＿係数Ｎ
Ｈ’＝フロア（Ｗ／Ｎ）×ピラミッド＿係数Ｎ  （１０）
【００４０】
最後のスケールの結果として生じるオプティカルフロー場は、その大きさが、通常の２．０の代わりに、式１０の幅および高さ係数の逆数で乗算されており、また、１オクターブ・デシメーションの代わりに、同じ逆の非整数の幅および高さ係数に従って、空間的にスケーリングされている。
【００４１】
偏導関数を使用するオプティカルフロー計算の不良設定性を低減することが望ましく、所与の偏導関数の次元に対する単一の計算は、潜在的適合値（ｐｏｔｅｎｔｉａｌｌｙ  ｆｉｔ  ｖａｌｕｅｓ）の連続線形範囲を与えるのみである。これらの偏導関数を単一解に縮小するために、多数の周囲のサンプル値の偏導関数がグループ化され（個々に、劣決定の解を形成する）、最小二乗適合が適用される場合がある。このために、好ましい実施形態では、勾配計算が、式８および９で描かれたように画素サンプル毎に、式１１に例示されるように画素サンプルの周囲の３ｘ３領域に対して適用される。
【数３】
0005547739.tif 000004
【００４２】
式１０では、重み関数が、中心にある勾配に向けて計算にバイアスをかけ、離れているものにより少ない重みを加える。本発明の好ましい実施形態では、式１１における重み関数は、式１２に従って定義される。
重み（ｎ，ｍ）＝｛０．１２５，０．７５，０．１２５｝×｛０．１２５，０．７５，０．１２５｝Ｔ  （１２）
【００４３】
数学的に安定した結果に達するために必要とされる情報は、なお欠けている場合がある。解析中の全体の領域は、実質的に同じ勾配値を有する場合があり、または、より厳しい場合、数値的に安定した推定を得るための勾配はない。他の状況では、解析中の領域は単一の顕著な垂直勾配を有し、その場合には、領域を評価するとき、主な勾配特徴の法線に垂直な動きがたとえ存在する場合、そのような動きを除いて、いかなる動きベクトル成分も決定することはできない。
【００４４】
本発明の一実施形態によれば、解析中の画像の対の領域の周囲の勾配特徴を表す２次元の構造テンソルが、式１３のように採用される場合がある。
【数４】
0005547739.tif 000005
各構造テンソルの２次元の固有システム解析により、評価中の現在の領域を、第１の、強い勾配を有する（最大固有値の大きさは、第２のものより著しく大きい）、強いテクスチャ成分を有する（両方の固有値が大きい）、または、同次かつ等方性である（両方の固有値が小さい）として特徴付けることができる。現在のＧＰＵおよびＤＳＰハードウェア上で、テーブル・ルックアップのためにメモリ読み取りを行うことは、メモリ・フェッチ・スケジューリングおよびレイテンシのために、明確な平方根計算を行うことよりも潜在的に高価である。したがって、本発明の一実施形態によれば、固有値の直接計算が採用される。本発明の好ましい実施形態では、前述の構造テンソルの２つの固有値の直接計算は、式１４の形式を取る。
【数５】
0005547739.tif 000006
【００４５】
加えて、好ましい実施形態によれば、使用するために最適なピラミッド・スケール係数（１．５から２．０に及ぶ）の決定は、前述の構造テンソル固有システム解析の無矛盾性、局所性および数値的安定性についての情報を組み込む、フィードバック機構によって指示される。具体的には、他のスケールを超える所与の単一のスケールについて、閾値画素割合を下回る小さい固有値（または、ゼロに近づく行列式）（典型的には、いずれかの所与の画像内の画素サンプルの１０％を超えるものについて、統計的に逸脱した、小さい固有値として定義される）によって示された、劣決定性（ｕｎｄｅｒ−ｄｅｔｅｒｍｉｎａｔｉｏｎ）または数値的不安定性が優勢であることは、より細かいピラミッド・スケールが使用されるべきであるという確かなしるしである。本発明の好ましい実施形態では、この条件にフラグが立てられた状況における、後続のピラミッド・レベルについての、後続のオプティカルフローの評価は、１．７５から、１．６６６、最終的には１．５へと進む、「格下げされた」ピラミッド係数を使用する場合がある。
【００４６】
ある状況では、各スケールについて計算されたオプティカルフロー場は、解析中の画像のいくつかのエリアがいかなる有用なオプティカルフロー情報もまったく提供しない場合がある（すなわち、１つまたは複数の式の分母がゼロに近づくか、またはゼロとなる）という点において、数値的不安定性によって損なわれる場合がある。例えば、動いているオブジェクトの中心が均一的に色付けされ、そのオブジェクトが、生成された画像ピラミッドによる評価の最大スケールによって与えられるアパーチャより大きい場合、そのようなオブジェクトの中心は、オブジェクトの残りと矛盾のない動きベクトルを示さないようになり、その理由は、分母の小さいサイズを使用する除算は、オプティカルフロー計算方法を実装するデジタルシステムの精度限界に近づくからである。勾配ベースのオプティカルフロー法は、オクルージョン境界に直面しているとき、矛盾した結果を欠点として有する場合がある（例えば、前景オブジェクトが、静止した背景に対して移動するにつれて、いくつかの背景画素は運動境界の前でオクルードされ、他のものは、オブジェクトの反対側で示される）。加えて、精度限界は、後続のスケールについての後の段階の評価ステップにおいて、不安定性を課す場合がある。
【００４７】
運動境界における、および、オクルージョンを含む画像の領域内の、数学的安定性に関連する問題に対処するため、本発明のある実施形態は、オプティカルフローを逆に（例えば、第１のフレームが第２のフレームであるかのように、および、逆もまた同じ）処理する場合がある。知覚できる動きの存在下で、順方向および逆方向のオプティカルフロー計算は共に、類似の大きさであるが、１８０度反対方向（すなわち、「可逆性の制約」）を有する動きベクトルの結果となるべきである。計算された動きベクトルは、好ましい実施形態によれば、構成画像の元のＲＧＢまたはＹＵＶ値の差分二乗和の合計を決定するために（すなわち、「動き補償ＳＳＤ制約」）、現在のスケールの第２の画像を５つ以上の位置において、すなわち、ロバートのクロス・コンフィギュレーションにおいて、サンプルするために使用される。３ｘ３画素、５ｘ５画素、その他など、他のサンプリング・エリア／サイズが可能であるが、５サンプルのロバートのクロス・コンフィギュレーションが経済的妥協を表すことは、当業者には理解されよう。可逆性の制約が満たされないか、または、動き補償ＳＳＤ制約が満たされない場合、現在のスケールについての残りの評価は、（０，０）にリセットされ、動きベクトルの以前のスケール（複数可）評価は、不変のまま保たれる。
【００４８】
前述の潜在的な数学的安定性の問題にさらに対処するため、生のオプティカルフロー場推定の各ピラミッド・スケールについてのある後処理ステップは、後続のピラミッド・スケールの計算の正確度および精度を向上させ、それにより、最終結果の正確度および精度を向上させる場合がある。形式的な意味では、これは一般に、上記で開示された明るさまたは勾配の不変性の制約への追加として、モデル化される。多くの場合、これらの追加の制約は、生のオプティカルフロー場についての平滑性の仮定または区分的不変性（ｐｉｅｃｅｗｉｓｅ  ｃｏｎｓｔａｎｃｙ）の仮定の形式を取る。本発明の好ましい実施形態によれば、すべてのスケールについての生のオプティカルフロー場出力は最初に、単一の（非線形）３ｘ３メジアンフィルタ演算によって、単一画素アウトライアを除去するように処理される。メジアンフィルタ演算の後で、Ｌ２ノルム全変動演算子が、ユーザにより供給された設定に応じて、可変数の反復（典型的には、１〜３反復）の間、生のオプティカルフロー場推定に対して実行される。文字通り、所与の全変動最小化が、２Ｄ離散サンプリングされた空間において、Ｌ１ノルム（区分的不変性）の意味で意図されるか、Ｌ２ノルム（区分的線形性）の意味で意図されるかについては、かなりの矛盾がある。明確にするため、本発明の好ましい実施形態では、Ｌ２ノルムＴＶ演算子が使用され、単一反復について、式１５の形式を取る。
【数６】
0005547739.tif 000007
ＩＴＶ＝０
ただし、式１５のＩは、前述の非線形処理の後で、生のオプティカルフロー場推定からの動きベクトル場の画像サンプルとして解釈される。この手法の利点は、オプティカルフロー場の本来の計算から後処理ステップを分離するＬ２ノルム全変動の制約と共に非線形統計的演算（メジアンなど）の使用を可能とし、それにより、並列処理のためのさらなる機会を与えることである。
【００４９】
図５は、本発明の一実施形態による、画像の対の間のオプティカルフロー場を計算するためのシステムを示す。限定しない例として、システム５１０は、デジタル化されたビデオまたは静止画像を、１つまたは複数のスチールまたはビデオカメラなど、１つまたは複数の画像取り込みデバイス５１２から受信する。システム５１０はまた、デジタルビデオ取り込みシステム５１４およびコンピューティング・プラットフォーム５１６を含む場合もある。デジタルビデオ取り込みシステム５１４は、デジタルビデオのストリームを処理し、または、アナログビデオをデジタルビデオへ、コンピューティング・プラットフォーム５１６によって処理することができる形式に変換する。デジタルビデオ取り込みシステム５１４は、スタンドアロンのハードウェア、または、コンピューティング・プラットフォーム５１６に直接プラグインすることができるファイヤワイヤ・カードなど、カードである場合がある。本発明の一実施形態によれば、画像取り込みデバイス５１２は、無線リンク（例えば、航空機と地上局の間）、および、デジタルデータリンク（例えば、イーサネット、地上局とコンピューティング・プラットフォーム５１６の間）など、異種データリンクを介して、ビデオ取り込みシステム５１４／コンピューティング・プラットフォーム５１６とインタフェースを取る場合がある。コンピューティング・プラットフォーム５１６は、ビデオデータストリーム５２４によって、１つまたは複数のプロセッサ５２０を介して、または直接、コンピュータ可読媒体５２６に供給される、バスシステム５２２を含む、１つまたは複数のプロセッサ５２０を備える、パーソナル・コンピュータまたはワーク・ステーション（例えば、Ｐｅｎｔｉｕｍ−Ｍ  １．８ＧＨｚ  ＰＣ−１０４以上）を含む場合がある。別法として、コンピューティング・プラットフォーム５１６は、ＦＰＧＡまたはＡＳＩＣに実装されたグラフィック処理装置（ＧＰＵ）またはデジタル信号プロセッサ（ＤＳＰ）など、集積回路として、または集積回路の一部として実装される場合がある。
【００５０】
コンピュータ可読媒体５２６はまた、ＷｉｎｄｏｗｓまたはＬｉｎｕｘオペレーティング・システムなど、任意選択のオペレーティング・システムを含む、１つまたは複数のプロセッサ５２０によって実行されるシステム５１０の命令を格納するために使用される場合もある。コンピュータ可読媒体５２６はさらに、１つまたは複数のデータベースにおいて、本発明のビデオクリップの格納および検索のために使用される場合がある。コンピュータ可読媒体５２６は、ＲＡＭメモリなど、揮発性メモリ、ならびに、フラッシュメモリ、光ディスク（複数可）および／またはハードディスク（複数可）など、不揮発性メモリの組み合わせを含む場合がある。処理されたビデオデータストリーム５２８の一部は、後のモニタ５３０への出力のために、コンピュータ可読媒体５２６に一時的に格納される場合がある。モニタ５３０は、処理されたビデオデータストリーム／静止画像を表示する場合がある。モニタ５３０は、解析者によって興味のあるオブジェクトを選択するための、キーボード５３２およびマウス５３４を備える場合がある。
【００５１】
本発明は、オプティカルフローを計算する従来技術の方法に勝るいくつかの利点を有する。正確で、密な、オプティカルフロー場は、入力画像に存在する定常および非定常雑音の厳しい条件下でさえ、大きいアーチファクトおよび障害なしに生成される。この処理は、同時代の、市販用の、大量に市場に出されたコンピュータ・ハードウェア上で、３０ｆｐｓの標準精細度および高精細度の放送解像度ビデオのために、リアルタイムを超えて行うために十分効率的であり、リアルタイムシーン解析、写真測量法、およびメトログラフィ（ｍｅｔｒｏｇｒａｐｈｙ）のための、改善されたビデオコーダ効率、超解像度ベースのスケーリング、動き補償デインターレーシングおよびフレームレート変換、深度マップ（ｄｅｐｔｈ−ｍａｐ）推定、ならびに、オブジェクト・セグメンテーションを含む、密なオプティカルフローのための新しい応用を広げるものである。
【００５２】
例示的実施形態は、単に本発明を例示するものであり、上記の実施形態の多数の変形形態は、本発明の範囲から逸脱することなく、当業者によって考案されてもよいことを理解されたい。したがって、すべてのそのような変形形態は、以下の特許請求の範囲およびそれらの均等物の範囲内に含まれることが意図される。
【図１】
0005547739.tif 000008
【図２】
0005547739.tif 000009
【図３Ａ】
0005547739.tif 000010
【図３Ｂ】
0005547739.tif 000011
【図４Ａ】
0005547739.tif 000012
【図４Ｂ】
0005547739.tif 000013
【図４Ｃ】
0005547739.tif 000014
【図４Ｄ】
0005547739.tif 000015
【図４Ｅ】
0005547739.tif 000016
【図５】
0005547739.tif 000017