オプティカルフローについて知りたいが、聞いて恥ずかしかったこと

オプティカルフロー（オプティカルフロー）-シフト、セグメンテーション、オブジェクトの選択、ビデオ圧縮を決定するためにコンピュータービジョンのさまざまな分野で使用される技術。 しかし、ウィキペディアまたは他の場所で読んでプロジェクトにすばやく実装したい場合は、非常にうまく機能せず、すでに1〜2のオーダーのシフトを決定するときに失敗するという事実につまずくでしょうピクセル（少なくとも私と一緒に）。 次に、たとえばOpenCVでの既製の実装を使用します。 そこではさまざまな方法で実装されており、略語PyrLKがFarnebackまたはそのようなものよりも優れているか悪いのかは完全に理解不能であり、いくつかの実装では非常に多くのパラメーターの意味を処理する必要があります。 そして、興味深いことに、これらのアルゴリズムは、私たち自身が書いたものとは対照的に、何らかの形で機能します。 その秘密は何ですか？

オプティカルフローとは何ですか？

オプティカルフロー（OP）は、目に見える動きの画像であり、2つの画像間の各ポイントのシフトです。 実際、これは速度フィールドです（スケールに対して正確なシフトは瞬間速度に等しいため）。 OPの本質は、画像の各ポイントに対して このようなシフト（dx、dy）は、2番目の画像上の点が開始点に対応することがわかります 。 ポイントの対応を判断する方法は別の問題です。 これを行うには、変位の結果として変化しない点の何らかの関数を取る必要があります。 一般に、ポイントは強度（つまり、カラー画像の明るさまたは色）を保持すると考えられていますが、同じ勾配値、ヘッセ行列、その値またはその行列式、ラプラシアン、およびその他の特性を持つポイントは同一と見なすことができます。 明らかに、照明または光の入射角が変化すると、強度の維持は失敗します。 それでも、ビデオストリームについて話している場合、2つのフレーム間で照明があまり変化しないのは、それらの間に短い時間が経過した場合だけです。 したがって、強度は多くの場合、そのポイントに残る関数として使用されます。



このような記述によれば、OPは特徴点の検索および比較と混同される可能性があります。 しかし、これらは異なるものであり、光学ストリームの本質は、特別なポイントを探すのではなく、任意のポイントがシフトした画像のパラメーターによって決定しようとすることです。



光束の計算には、高密度と選択的（疎）の2つのオプションがあります。 スパースストリームは、個々の特定のポイント（たとえば、いくつかの特徴検出器によって選択されたポイント）のシフトを計算し、高密度ストリームは画像内のすべてのポイントのシフトを考慮します。 当然、サンプルストリームはより高速に計算されますが、一部のアルゴリズムでは差はそれほど大きくなく、一部のタスクでは画像のすべてのポイントでストリームを見つける必要があります。



縮退した場合には、シフトを決定するためのより単純な方法を適用できます。 特に、画像のすべてのポイントに同じシフトがある場合（画像全体がシフトする場合）、位相相関法を適用できます：両方の画像のフーリエ変換を計算し、位相の畳み込みを見つけ、そのシフトを決定します（ en.wikipedia.orgを参照） / wiki / Phase_correlation ）。 ブロックマッチングを使用することもできます。ウィンドウ内の画像の差の標準を最小化するシフトを見つけます。 純粋な形では、このようなアルゴリズムは長時間機能し、曲げやその他の歪みに対して不安定です。 英語版ウィキペディアには、これらのアルゴリズムがオプティカルフローを計算するための異なるオプションとしてリストされていますが、これらのアルゴリズムは他の目的に使用でき、この問題を完全には解決しないため、あまり正確ではないようです。 画像の局所的な特性に基づいてオプティカルフローメソッド（英語版ウィキペディアでは差分法と呼ばれます）を呼び出します。

標準アプローチ（ルーカス-カナダ法）

アルゴリズムの数学的な説明はこの記事で十分詳細に説明されていますが 、理論的な側面のみが影響を受けます。



変位の結果としてのポイントの強度が変化していないと仮定して、オプティカルフローの数学モデルを検討します。



させて 最初の画像（つまり、時間t）のある点（x、y）の強度です。 2番目の画像では、この点は（dx、dy）にシフトしますが、dtは通過し、 -テイラーに従って強度関数を第1項に分解しました（理由は第1項のみです） -座標と時間に関する、つまり本質的に偏微分 -2つのフレーム間のポイント（x、y）の輝度の変化。



ポイントは強度を保持していると考えています。つまり、

2つの未知数（dxとdy）を持つ1つの方程式が得られます。つまり、解くのに十分ではありません。つまり、この方程式を理解することはできません。



この問題の最も簡単な解決策は、ルーカスカナダアルゴリズムです。 画像オブジェクトには1ピクセルより大きいので、現在のポイントの近くでは、他のポイントもほぼ同じシフトを持っている可能性が高いことを意味します。 したがって、この点の周りにウィンドウを取り、ガウスに従って分布した重み係数を使用して、つまり、調査中のピクセルに最も近いピクセルの重みが最大になるように、（最小二乗法に従って）合計誤差を最小化します。 最も単純な変換の後、2つの未知数を持つ2つの方程式のシステムを取得します。



ご存じのように、このシステムには常に一意の解があるわけではありません（非常に頻繁ですが）。システムの行列式がゼロの場合、解がないか無限数になります。 この問題は、開口の問題として知られています-周期的な画像の視野が限られている変位のあいまいさ。 これは、ある程度の周期性がある画像の断片が視野に入る場合に対応します。 ここでも、写真がどこに移動したかを人が明確に判断することはできません。 問題は、このようなあいまいな状況でのノイズのために、ゼロの行列式ではなく、非常に小さな値が得られ、シフトの値が非常に大きくなる可能性があり、実際には特に相関しないことです。 そのため、特定の段階で、システムの行列式が十分に小さくないかどうかを確認する必要があります。もしそうであれば、そのような点を考慮したり、エラーとしてマークしないでください。

なぜ機能しないのですか？

この段階で停止してこのアルゴリズムを実装すると、正常に機能します。 しかし、隣接する画像間のシフトが非常に小さく、1ピクセルのオーダーである場合にのみ、常にではありません。 （品質分析のために異なる相対オフセットを持つ合成シーケンスが生成され、このシフトは非整数のピクセル数で表すことができ、結果のイメージはそれに応じて補間されます）2ピクセルのシフトではすでにエラーが大きくなり、3以上の場合、結果は一般に不十分になります。 問題は何ですか？



その後、数学が用意されました。 彼女は、周囲のすべての機能が何度も連続的で微分可能であるという感覚を私たちに植え付けました。 一般に、研究所では、テイラーの式を使用して、点の近傍に関数の近似を書くように教えられました。 ここで、この場所で派生物の物理的な意味は何ですか？ それらを使用して、点の有限近傍で関数の値の変化を決定し、導関数は無限に小さい近傍のアイデアを与えます。 この近傍を拡大するには、テーラー展開に高次の導関数を追加できますが、これはシステムの非線形性につながり、解決がはるかに困難になり、特に実際には連続的で微分可能な微分を扱っていないため、利点は疑わしいです関数であり、一般的にどの離散関数かは明確ではありません。 したがって、関数g（x）を探す方が論理的です。この場合、離散ケースでは、f（x）+ g（x）= f（x + 1）、f（x）+ 2g（x）= f（x +2）、f（x）-g（x）= f（x-1）などしたがって、この場合、導関数は必要ありませんが、元の関数の点に最も近い線形関数が必要です。 簡単な数学的計算が解決につながる どこで 。 各辺の1つの隣接点に導関数を構築した場合、幸運でした：この場合、式は導関数の近似計算の式と一致します：g（x）=（f（x + 1）-f（x-1））/ 2。 OpenCVで典型的なことは、ルーカスカナダの光束を計算するとき、この式が使用されます。これについては後で説明します。 しかし、より多くのポイントを取得すると、式はすでに一次導関数の古典的な差分スキームとは完全に異なります。



明らかに、たとえば元のポイントの左右の3つの隣接するポイントからこの関数を構築する場合、それはより遠くにあるポイントにまったく依存せず、したがって、3つ以上のポイントをシフトすると、不適切な結果が得られることがよくあります。 また、この関数を作成するポイントの数が多いほど、使用されるポイントからの結果の線の平均偏差が大きくなります-再び、線形に変化する画像はないが、悪魔はどの画像を知っているかという事実によります。 実際には、2ピクセルを超えるシフトでは、ポイント数に関係なく、すでに十分に大きなエラーが発生していません。



アルゴリズムのもう1つの弱点は、ここでも滑らかな連続関数ではなく、任意の、さらには離散的な関数を扱っていることです。 そのため、画像の一部の断片では、強度が明白な規則性なしで、たとえばオブジェクトの境界で、またはノイズのために「スキップ」する可能性があります。 この場合、関数g（x）は、点の近くでの画像の変化を正確に記述できません。 これを（少なくとも部分的に）解決するには、元の画像を汚すことをお勧めします。非常に強く汚すのが便利です。つまり、全員のお気に入りのガウスぼかし（重み係数による平均化）ではなく、同じボックスフィルター（ウィンドウ全体の均一な平均​​化） ）、さらには数回続けて。 画像の滑らかさは、細部よりも重要です。



ただし、これらの手段によって、検出された2〜3ピクセルのシフトを制限することもできません。 ところで、OpenCV 1.0では、このような光学ストリームの実装があり、非常に小さなシフトでの理想的な条件でのみ機能しました。

どうする？

全体で普通のルーカス・カナダは、小さなシフトを明確に定義しており、その中の写真はその線形近似に似ています。 これを克服するために、標準のCVテクニック-マルチスケーリングを使用します。異なるスケールの画像の「ピラミッド」を構築し（ほとんどの場合、各軸で2倍にスケーリングされ、カウントしやすくなります）、小さな画像から大きな画像への光学ストリームでそれらを通過しますその後、小さな画像で検出された小さなシフトは、大きな画像での大きなシフトに対応します。 最小の画像では、1-2ピクセル以下のシフトが見つかり、小さいスケールから大きいスケールに移動します。前のステップの結果を使用して、シフト値を調整します。 実際、OpenCVでは、calcOptFlowPyrLK関数によって実装されます。 このピラミッドアルゴリズムを使用すると、多くのポイントで線形近似を計算する必要がなくなります。ピラミッドのレベルを増やし、各レベルでこの関数のかなり大まかな近似をとる方が簡単です。 したがって、OpenCVでは、2つの隣接ポイントのみの計算があります。 したがって、このアルゴリズムの実装に関連して、導関数に対する近似関数の利点に関する結論は役に立たないことが判明しました。このような数の制御点では、導関数が最良の近似関数です。

そして、他に何がありますか？

このアルゴリズムは、光束を計算するための唯一のオプションではありません。 OpenCVには、Lucas-Canadaストリームに加えて、FarnebackストリームとSimpleFlowもあります。これらは、しばしばHorn – Schunckアルゴリズムを指します。



Horn – Schunckメソッドは、Lucas-Canadaメソッドよりも多少グローバルです。 これは、画像全体の光束が非常に滑らかになるという仮定に基づいています。 同じ方程式から 機能に行くことを提案 、つまり、重み係数αでシフトの急激な変化がないという要件を追加します。 この関数を最小化すると、2つの方程式のシステムが得られます。







これらの方程式では、ラプラシアンはおよそ計算することを提案します： -平均値との差。 各ピクセルに対して記述する方程式系を取得し、一般的なシステムを反復的に解きます。







このアルゴリズムでは、マルチスケーリングを使用することも提案されており、画像を2倍ではなく、0.65の係数でスケーリングすることをお勧めします。



このアルゴリズムは、OpenCVの最初のバージョンで実装されましたが、後に放棄されました。



Farnebackは、2次形式を使用して近傍の強度の変化を近似することを提案しました：I = xAx + bx + c with symmetric matrix A（実際、Taylor展開を第1項に考慮して、線形近似I = bx + cを採用しました近似の精度を上げることに決めた回数）画像がこの近傍内でシフトした場合、 、二次展開に置き換えて、括弧を開きます。





。



これで、両方の写真のA、b、cの値を計算でき、このシステムはdに関して冗長になり（特に最初の式はわかりにくい）、一般にdは2番目の式から得られます： 。 次の近似に頼らなければなりません： 。 簡単にするために示す それから私達はちょうど得る 。



計算のノイズを補正するために、検討中のポイントの近くでは、すべてのポイントがほぼ同じシフトを持っているという仮定に再び戻ります。 したがって、エラーを再度統合します ガウスの重み係数wを使用してウィンドウ上で、この合計誤差を最小化するベクトルdを見つけます。 次に、最適な値を取得します および対応する最小誤差 。 つまり、各ポイントについて計算する必要があります 、ウィンドウ全体で平均し、行列を反転して結果を取得します。 したがって、これらの積は画像全体について計算でき、異なるポイントに対して事前に計算された値を使用できます。つまり、これは、高密度ストリームを考慮することが理にかなっている場合にのみ当てはまります。



いつものように、このアルゴリズムには多くの修正と改善があり、主に既知のアプリオリ情報（フローの所定の初期近似）の使用を可能にし、再びマルチスケーリングを可能にします。



SimpleFlowメソッドは、次の考え方に基づいています。導関数を検索したウィンドウのサイズ以上のシフトを決定する方法がまだわからない場合、なぜ導関数の計算に煩わされるのでしょうか。 ウィンドウ内で最も類似したポイントを見つけましょう！ また、あいまいさを解決し、ノイズを補正するために、流れが連続的であり、このポイントの近くではすべてのポイントがほぼ同じシフトを持つことを考慮します。 また、ウィンドウサイズの問題は、マルチスケーリングによって再び解決されます。



より厳密には、アルゴリズムは次のとおりです。ウィンドウ内のすべてのポイントに対して、開始ポイントからこのポイントへの遷移の確率に（逆対数依存性で）対応する「エネルギー」の関数があります。 。 さらに、このエネルギーとガウスウィンドウの畳み込みが考慮されます この関数を最小化する値（dx、dy）が見つかりました。 サブピクセルの精度を得るには、見つかった最適点（dx、dy）の小さな近傍を考慮し、その中のエネルギー関数のピークを放物面のピークとして探します。 また、前述のように、この手順はスケーリングされた画像のピラミッドに対して実行されます。 また、計算を高速化するためのcな方法もありますが、誰もが自分でそれを理解するのは興味深いことです。 このため、このアルゴリズムは（理論的に）非常に高速で、精度が高いことが重要です。 そして、彼は以前のものほど問題がなく、シフトが大きければ大きいほど、それはより悪く検出されます。

そして、あなたが強さではない場合？

上記では、ポイント間の対応は異なる値で決定できると言われましたが、なぜ強度だけを考慮するのですか？ そして、他の数量を減らすことができるため、適切なフィルターで画像をフィルター処理し、フィルター処理された画像を上記のアルゴリズムの入力に送ります。 したがって、光ストリームを使用する場合は、まず、どの画像特性が条件の下で最も安定するかを考え、適切なフィルタリングを実行して、この特性がアルゴリズムの入力での強度にならないようにします。

練習する

OpenCVが提供するアルゴリズムを実際に試してみましょう。



ここでは、さまざまなシフト、回転、射影変換、セグメント、さまざまなノイズなどを使用して、パラメータを変更し、入力シーケンスを変更して、各アルゴリズムのさまざまな研究を行うことができます。これには時間がかかり、現在の記事のサイズを超えますしたがって、ここでは、固定距離の小さな画像シフトと小さなノイズの単純な平行移動に限定することを提案します。 これにより、一般的な用語でアルゴリズムの実行方法とそれらのどれがよりクールであるかを理解できます。



手順の構文は、 マニュアルページで詳細に説明されています。ここでは、コメントとともにsqueeze-translationを示します。



従来のLucas-Canadaは、calcOpticalFlowPyrLKプロシージャにピラミッドを実装しています。 アルゴリズムは、スパースストリームを計算します。つまり、最初の画像の特定のポイントセットについて、2番目の画像の位置を推定します。 入力パラメーターは非常に明白です：2つの入力画像、ポイントの入力および出力セット、status-対応するポイントが正常に検出されたかどうかを示す出力ベクトル、err-対応するポイントの推定誤差の出力ベクトル、WinSize-ガウス平均が発生するウィンドウのサイズ、 21x21、それはうまく機能しました、maxLevel-ピラミッドのレイヤー数-1、つまり最後のレイヤーの数、私は5つの基準を取りました-シフトを決定する反復プロセスを終了するための条件（エラーを反復的に最小化する）-これ パラメータIはデフォルト、フラグを左 - 追加フラグは、初期の近似法または選択フロー推定誤差、minEigThresholdとして使用することができる - 勾配閾値、縮退行列と考えられるの下、私はデフォルトで左。 OpenCV 2.4.1以降では、事前に計算されたスケーリング画像のピラミッドを使用してストリームを計算できます。



作業の結果、小規模および大規模なシフトの両方が正常に安定して検出され、かなり大きなノイズに耐えることができます。動作時間は5層ピラミッド（コアi7 950）で400ポイントで約10 msです。



ちなみに、このアルゴリズムは、高密度バージョンと疎バージョンの両方のGpu（CUDA）にも実装されています。



FarnebackストリームはcalcOpticalFlowFarnebackプロシージャによって実装され、高密度ストリーム、つまり各ポイントのシフトが計算されます。 パラメーター：入力画像、フロートの2チャネルマトリックス形式の出力ストリーム、pyr_scaleはピラミッドのレイヤー間のスケールの比率を決定します。levels-ピラミッドのレベル数、winsize-平均化されるウィンドウのサイズ、iterations-各レベルでの反復数、poly_n- Aおよびbの値を推定する多項式のサイズ、poly_sigmaは微分を平滑化するときのガウスぼかしのシグマ、推奨パラメーター値はマニュアルに示され、フラグは追加フラグです。たとえば、初期近似を使用できます IX流れまたはその他のウィンドウ上で平均。



このアルゴリズムは（私の観察によれば）安定性がはるかに低く、かなり均一な画像を見逃しやすく（明らかに、問題は失敗したポイントのフィルタリングの欠如です）、大きなシフトを適切に判断できません。 512x512の画像で600ミリ秒働いた。



SimpleFlowストリームはcalcOpticalFlowSFプロシージャを実装し（再び、高密度ストリームが計算されます）、デフォルト値のない多くの神秘的なパラメーターを持ち、一般的に、現時点ではページの情報は非常に簡潔に提供されます。 それを理解してみましょう。 最初の3つは入力画像で、出力2チャンネルです。 レイヤー-ピラミッド内のレイヤーの数、つまり、元の画像がスケーリングされる回数。 averageing_block_size-ピクセルエネルギー関数を計算したウィンドウのサイズ。 max_flow-各ステップで決定できるようにする最大シフト。実際、ウィンドウのサイズによって決定されます（intである理由は完全には明らかではありません）。 ここで停止するか、さらにいくつかのパラメーターを設定することができますが、それらのいくつかの意味は私を惑わしています。



このサイトは、 calcOpticalFlowSF（frame1、frame2、flow、3、2、4、4.1、25.5、18、55.0、25.5、0.35、18、55.0、25.5、10）で始まる使用例を提供します。 ;



私のアルゴリズムは他のアルゴリズムよりもずっと遅く、512x512の画像につき約9〜12秒です。 作業の結果は、ファーンバックよりももっともらしいようです。少なくとも、均一な画像の変化はより明確に判断され、大きな変化の場合ははるかにうまく機能します。

結論

オプティカルストリームをどこかで使用する場合は、まずそれが必要かどうかを考えます。多くの場合、より簡単な方法で実行できます。 自分でフローを実装することは、数回考えられているだけです。各アルゴリズムには、多くのトリック、微妙さ、最適化があります。 , , OpenCV (, , ). SSE , , CUDA OpenCL . . (. . sparse ), calcOpticalFlowPyrLK, , . dense- calcOpticalFlowSF, . , calcOpticalFlowFarneback, , .

文学

docs.opencv.org/modules/video/doc/motion_analysis_and_object_tracking.html

Pyramidal Implementation of the Lucas Kanade Feature Tracker. Description of the algorithm — Jean-Yves Bouguet

Two-Frame Motion Estimation Based on Polynomial Expansion — Gunnar Farneback

SimpleFlow: A Non-iterative, Sublinear Optical Flow Algorithm — Michael Tao, Jiamin Bai, Pushmeet Kohli, and Sylvain Paris

Horn-Schunck Optical Flow with a Multi-Scale Strategy — Enric Meinhardt-Llopis, Javier Sanchez

en.wikipedia.org/wiki/Optical_flow