まえがき
良い一日！ 今日、私はあなたと最も奥深く、私のお気に入りのバイクの1つを共有することにしました。
私は遠くから始めます-かなり長い間、チェリャビンスクのラジオ工場で働いていましたが、私たちは（一般に、そして今はもう1つありますが、もうありません）、1つのメガプロジェクトがありました：物理オブジェクトの保護のための光電子モジュールです。 これは、あらゆる状況に対応する3台のカメラ（カラー-昼光、BW感光性-薄明かり用、サーマルイメージャー-夜間観測用）を備えた回転式設置では非常に便利です。 このようなモジュールは、高さ50メートルのタワーに設置され、昼夜を問わず、4〜5キロメートルの範囲内にエリアを維持できます。 その投稿についてではなく、詳細は書きません。 誰が気にする-彼らは自分自身を見つけるでしょう。
もちろん、画像処理には多くの興味深い問題がありました。 これらの1つについてお話したいと思います。 つまり、超並列コンピューティングを使用してリアルタイムで手振れを補正する方法、またはSURFが常に適切でない理由です。 猫へようこそ。
問題の本質
前述したように、モジュールはかなり高いタワーに配置されます。 このような高度での強風のため、彼らは絶えず細かく揺れ、カメラの視野角が小さいほど目立ちます。 そして、オペレーターはカメラ画像を長時間観察する必要があります（シフト）。 これは非常に難しく、些細なことです。 そのため、このようなシステムの主な要件の1つは、画像の揺れを最小限に抑えるメカニズムの存在です。 どこかにジャイロ安定プラットフォームが使用されていますが、どこでも使用されていません。 ほとんどの場合、ソフトウェア安定化が使用され、ほとんどの場合、それはSURFです。 しかし、これには適していません。
SURFおよび類似のアルゴリズムがこれに適さない理由
順番に：
1-SURFはこれを目的としていません。 この問題を解決するために必要なのは、前のフレームに対する新しいフレームのオフセットをピクセル単位で見つけることです。 カメラは画像平面に沿って回転せず、画像に近づいたり遠ざかったりしません。 SURFは、ビデオシーケンスで動いているオブジェクトを追跡するのに適していますが、画像全体の変位を見つけるのには適していません。
2-パフォーマンス。 詳細には触れませんが、時間制限は深刻だとしか言えません-アルゴリズムは最後の2つのフレーム間のオフセットを13ミリ秒以内に見つける必要があります。 できるだけ少ない。 SURFからは、これを達成することさえできませんでした。
3-干渉。 フレーム全体ではなく、制御点の変位が分析されます。 一致エラーのため、誤った一致を排除することには問題があり、それを解決するのは非常に困難です。 ライブ画像では、これにより、ある方向または別の方向に画像のまれな「ジャーク」が発生しました。
私の自転車
この問題を解決するまでに、 nVidia CUDAを使用した経験がありました。 明るさ、コントラスト-いくつかのビデオ処理フィルターを書き直しました。 CPUでの処理と比較して速度が向上したことは、私にとって非常に喜ばしいことでした。このときから、特に超並列コンピューティングとGPGPUに興味を持つようになりました。
この問題を解決するために使用することにしたのは、超並列コンピューティングでした。 最初は既製のソリューションを探していましたが、試しました。 CUDAでのSURFの実装を探していましたが、覚えている限り、適切なものは見つかりませんでした。 そして彼は自分で発明することを決めました。 ところで 、私はComrade BigObfuscator による素晴らしい記事に出会いまし た 。
このアルゴリズムは「Ratel Deshake」と呼ばれ、3つの段階で構成されています。
-新しいフレームの準備
-フレームのセグメント積分表現への変換
-ベストマッチを検索
3つのステップはすべて、大規模な並列処理に適しています。 CUDAに実装しましたが、理解しているように、これはすべてFPGAなどに実装できます。
新しいフレームの準備
この段階では、興味のないものをすべて入力から削除する必要があります。 より正確には、色、そして可能であれば干渉。 このために、白黒の画像の変換としきい値を使用した輪郭の選択を使用しました。 コードの形式の場合、次のようになります。
struct pixel { unsigned char R, G, B; } pixel Image[width, height]; unsigned int GSImage[width, height]; unsigned int processedImage[width, height]; for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { GSImage[x, y] = Image[x, y].R + Image[x, y].G + Image[x, y].B; } } for (int x = 1; x < width; x++) { for (int y = 1; y < height; y++) { preprocessedImage[x, y] = 0; if (GSImage[x, y] - GSImage[x - 1, y] > threshold) preprocessedImage[x, y]++; if (GSImage[x, y] - GSImage[x, y - 1] > threshold) preprocessedImage[x, y]++; if (GSImage[x, y] - GSImage[x + 1, y] > threshold) preprocessedImage[x, y]++; if (GSImage[x, y] - GSImage[x, y + 1] > threshold) preprocessedImage[x, y]++; } }
フレームのセグメント積分表現への変換
おそらく最も興味深いステージです。 まず、いくつかのポイントを明確にする必要があります。
まず、画像の積分表現は何ですか。 これは、上記のリンクからこの記事を読んでいない場合、こちらの記事を読むことで理解できます。 つまり、これは2次元（この場合）の配列であり、座標XとYを持つ要素は、座標[0..X、0..Y]を持つ元の配列のすべての要素の合計に等しくなります。
第二に-私はセグメント積分表現と呼んでいます。 私のアルゴリズムの特徴により、座標XとYの要素が座標[（XN）.. X、（YM）.. Y]の元の配列のすべての要素の合計に等しい2次元配列が必要です。ここで、NとMは任意の数字ですアルゴリズムの速度/精度比に影響します。 たとえば、値15と15を使用しました。 結果の配列の要素は、元の配列の256要素（16x16平方）の合計です。 はい、実際には一種の画像のぼかしです。
しかし、画像の積分表現に戻ります。 少し考えれば、1つのスレッドで次のように最適に計算できることを理解できます。
unsigned int Image[width, height]; unsigned int processedImage[width, height]; processedImage[0, 0] = Image[0, 0]; for (int x = 1; x < width; x++) { processedImage[x, 0] = Image[x, 0] + processedImage[x-1, 0]; } for (int y = 1; y < height; y++) { processedImage[0, y] = Image[0, y] + processedImage[0, y-1]; } for (int x = 1; x < width; x++) { for (int y = 1; y < height; y++) { processedImage[x, y] = Image[x,y]+processedImage[x-1,y]+processedImage[x,y-1]-processedImage[x-1,y-1]; } }
しかし、1つの問題があります。 アルゴリズムのこの部分を多数のスレッドに分割しても機能しません。 それともうまくいきますか？ もちろん。 水平と垂直の2つの別々の段階に分割するだけで十分です。 次に、これらの各ステージは、それぞれ水平および垂直のピクセル数に等しいスレッド数に完全に対応します。 このようなもの：
unsigned int Image[width, height]; unsigned int horizontalImage[width, height]; unsigned int processedImage[width, height]; // for (int y = 0; y < height; y++) { horizontalImage[0, y] = Image[0, y]; for (int x = 1; x < width; x++) { horizontalImage[x, y] = Image[x, y] + horizontalImage[x-1, y]; } } // for (int x = 0; x < width; x++) { processedImage[x, 0] = horizontalImage[x, 0]; for (int y = 1; y < height; y++) { processedImage[x, y] =horizontalImage[x, y] + processedImage[x, y-1]; } }
そして今、同じことですが、N = M = 15のセグメント積分表現の場合：
unsigned int Image[width, height]; unsigned int horizontalImage[width, height]; unsigned int processedImage[width, height]; // for (int y = 0; y < height; y++) { horizontalImage[0, y] = Image[0, y]; for (int x = 1; x < 16; x++) { horizontalImage[x, y] = Image[x, y] + horizontalImage[x-1, y]; } for (int x = 16; x < width; x++) { horizontalImage[x, y] = Image[x, y] + horizontalImage[x-1, y] - Image[x-16, y]; } } // for (int x = 0; x < width; x++) { processedImage[x, 0] = horizontalImage[x, 0] for (int y = 1; y < 16; y++) { processedImage[x, y] = horizontalImage[x, y] + processedImage[x, y-1]; } for (int y = 16; y < height; y++) { processedImage[x, y] = horizontalImage[x, y] + processedImage[x, y-1] - horizontalImage[x, y-16]; } }
そのような小さな魔術。 実際、画像をいくつかの個別の部分に分割すると、さらに並列化できますが、これらはタンバリンを使用した個別のダンスです。 いずれにせよ、このすべての後、画像のセグメント積分表現があります。 この段階では、もう1つ重要なことを行う必要があります。NとMを選択することに加えて、比較する「ブロック」の数を選択する必要があります。
この点も詳細に説明する価値があります。 実際には、最適な一致を検索する際に、前のフレームと新しいフレームとの正確な一致が検索され、逆の検索は行われません。 アルゴリズムの反復を通過した後、次の反復のために、前のフレームに関するデータは残りますが、すべてではなく、特定のブロックの値のみ（私の場合、16x16のサイズを持ちます）。 これは、速度/精度の比率に影響する別の要因です。 より少ないブロック-より多くの速度、より多くのブロック-より高い精度。
具体的には、私の場合、画像サイズは704x576ピクセルでした。 前のフレームのセグメント積分表現から、1140セグメントのみの値を残しました（画像の中心から38x30ブロック、重複しない、4560バイト）。 それは絵としてより明確になります：
ここに、256x256ピクセルの仮想画像があります。 便宜上、16x16ピクセルの個々のブロックに分割されます（ただし、ブロックのセグメント積分表現ははるかに大きく、互いに重なり合っています）。 中央には、10 x 10個のブロックの配列が割り当てられています。 これらのブロックの値は、アルゴリズムの次の反復で使用するために覚えておく必要があります。 コードでは、次のようになります。
unsigned int IntegralImage[256, 256]; unsigned int NextIteration[10, 10]; for (int x = 0; x < 10; x++) { for (int y = 0; y < 10; y++) { NextIteration[x, y] = IntegralImage[(x+4)*16-1, (y+4)*16-1]; } }
この配列が必要な理由-次のステップで明らかになります。
ベストマッチを検索
ほとんどすべて、フィニッシュライン。 1つのフレームのみがアルゴリズムを通過した場合、このステップはスキップする必要があります（これまで安定させるものはありません）。 これが最初のフレームではない場合、NextIteration配列は前の反復から残る必要があります。 前の反復から残る必要があるため、この段階ではPrevIterationと呼ばれます。混同しないでください。
したがって、新しいフレームのセグメント積分表現と、前のフレームからの制御ブロックの配列があります。 この段階では、新しいフレームのセグメント積分表現上の前のフレームのオーバーラップブロックが最小の差を与える位置を見つける必要があります。
重要な注意-すべての可能な位置をチェックすることはほとんど意味がありません。ピクセルで予想される最大偏差を定数として設定することをお勧めします。 たとえば、XおよびYのプラスまたはマイナス30ピクセル。
まず、1つまたは別のオフセットで差を表示する配列が必要です。 正方形のある画像のコードの例：
unsigned int IntegralImage[256, 256]; unsigned int PrevIteration[10, 10]; unsigned int Differences[61, 61]; for (int X = 0; X < 61; X++) { for (int Y = 0; Y < 61; Y++) { Differences[X, Y] = 0; } } // +-30 3721 for (int X = 0; X < 61; X++) { for (int Y = 0; Y < 61; Y++) { for (int x = 0; x < 10; x++) { for (int y = 0; y < 10; y++) { Differences[X, Y] += abs(PrevIteration[x,y]-IntegralImage[(x+4)*16-31+X,(y+4)*16-31+Y]; } } } }
以上です。 配列Differencesの最小要素を見つけるためだけに残ります。 [0、30]の場合-新しいフレームは30ピクセル右にシフトしています。 [60、30]の場合-左に30ピクセル。
まとめ
この記事では、革新的なことや非常に明白なことは言いませんでした。 しかし、これはこのトピックに関する私の経験の重要な部分であり、誰かに役立つことを心から願っています。 記事は長くてわかりにくいので、おそらくどこかに明らかな間違いがあるか、何か明確に説明していませんでした。フィードバック、建設的な批判、その他のフィードバックを喜んで受け取ります。 最後までマスターした人々に感謝します。
私の実装に関しては、多かれ少なかれ動作するテストソフトウェアが判明しました。 GeForce GTX560レベルのビデオカードでは、割り当てられたタスクを実行することが可能でした-サイズ704x576で毎秒75フレームを処理しました。 そして、まだ十分な時間的余裕がありました。 もちろん、この記事では一般的な原則のみを説明しましたが、ここでは多くを最適化できます。 残念ながら、プロジェクトでCUDAを使用しないことが決定されたため、1年以上もCUDAに触れていません。
繰り返しますが、素晴らしい記事をくれたBigObfuscatorに感謝します。
生
上で書いたように、1年以上の間、私はこのアルゴリズムの実装に従事していません。 情報源はありますが、見苦しいため、現在の形式で投稿することを恥ずかしく思います。 十分な人が興味を持っている場合、ファイルからほこりを払い落として、すべてを整理し、消すことができます。
素敵なコーディングと良いアイデアを持っています！