より速いcvFindContour（）への代替

Question

私のコンピュータビジョンでは、輪郭検出が大部分の時間を要し、より高速にする必要があります。私はNEON命令で他のすべてを最適化し、ベクトル化しています。輪郭検出がプロファイルを支配しています。残念ながら、これをどのように最適化するかは明らかではありません。

私は古典的な矩形検出処理を行って、基準マーカー、つまりcvFindContours（）を見つけ、次に輪郭から四角形を近似します。多くのマーカーが目に見える（または致死的に、マーカではない矩形の密集したグリッドが見える）場合、cvFindContours（）の呼び出しだけでiPhoneで30msを超えることができます。

私はすでに信じられないほど高価なC++のcv :: FindContours（）をcvFindContours（）に置き換えました。特にvector>が渡された場合、C++バージョンは内部のcvFindContours（）よりもベクトルの割り当てと移植に時間がかかりました！

今、私は完全に時間をcvFindContours、より具体的にはcvFindNextContour（）にバインドされています。 cvFindNextContour内のコードはブランチヘビーなので、明らかにベクトル化するのは容易ではありません。また、私は自分自身を信用しない複雑なアルゴリズムを実装して、最適化しようとすると間違っていないようにします。

私はすでにcvBlobLib（曖昧さ回避のために、これを意味する：http://code.google.com/p/cvblob/）を見て、同じことをより速く実行できる代替アルゴリズムを提供しているかどうかを確認しました。輪郭をstd :: list（）に記録し、メモリ割り当てにほとんどすべての時間を費やすので、ソースの基本ダウンロードは非常に遅いです。このリストを256個の要素にプリセットしたstd :: vectorに置き換えると、push_back（）で最初のコピーを取り除くにはまだcvFindContours（）よりも3倍長い関数が残っています.cvb :: cvLabelではその66％ ）。だからこのように実行可能ではないようです。

多くの矩形の検出を最適化する方法はありますか？私の漠然としたhandwavingが含まれています：私はそこに、マルチプラットフォームだとして

1. はcvFindContourと同等の任意の高速実装では、理想的には、ソースコードとして、（）はありますか？

2. 輪郭の大部分は必須ではなく、「成功した」矩形だけが有効です。特に、それらの内部輪郭は有用ではない。理論的には、私はcvFindContoursを呼び出すことはできませんでした。代わりに、cvStartFindContours/cvFindNextContourを呼び出して、見つかった各輪郭をテストし、私が探している矩形を見つけたら再帰しません。

3. 古典的なFindContours（）/ ApproxPoly（）アプローチで使用できる全く異なる矩形検出アルゴリズムがありますか？

4. 興味深い関心領域でcvFindContoursを「プライミング」する方法はありますか？例えば。 FASTコーナー検出は、非常に攻撃的な閾値であっても、ほとんど常に私の基準マーカーコーナーを返します。検出を制限するためにそのポイントセットを使用する方法はありますか？ （残念なことに、多くのマーカーやマーカーに無関係な濃いグリッドラインの場合にも、これがどの程度役立つかはわかりません。

5. 上記と同じですが、 Blobの検出は、（正しく理解すれば）再帰的なflood-fillingとして実装できますか？これを素早くベクタライズした実装があり、それで何とか面白いBlobの四角形を引っ張ってそこからシードの輪郭を検出できますか？

どのようなアイデアも歓迎されます！

Answer 1

あなたの目標は輪郭検出ではなく矩形検出であるため、計算には積分画像を使用することをお勧めします。積分画像の説明はhereです。あなたの望む画像の積分画像を計算した後、矩形の画素合計を計算することは、3つの操作で行うことができます。

黒以外のオブジェクトの周囲に四角形を描画すると仮定すると、次のような方法を使用できます。再帰的に、画像とその部分画像を4に分割し、希望する閾値以下の画素合計で矩形を破棄します。あなたはあなたのオブジェクトに近似する多くの小さな四角形を残します。隣接する四角形をマージすると、検出されたオブジェクトの高速近似が得られます。