8接続性は正確ではなく、実際には特定のアプリケーションにのみ適しています。特に、テストのためにラボで作成されたイメージではなく、「自然な」イメージの場合、4接続を使用する方が一般的です。 8連結領域はチェッカーボードパターンとジグザグノイズを含む。 4つの接続されたフォアグラウンドは、8つの接続された背景を生成します。
OpenCV関数cvFindContours()のソースを掘り下げることができます。 PythonへのOpenCVバインディングがあります。 http://opencv.willowgarage.com/documentation/python/structural_analysis_and_shape_descriptors.html
はhttp://opencv.willowgarage.com/wiki/PythonInterface
私は、最初の4に接続されたアルゴリズムを実装することをお勧めします。あなたは、次のような本で擬似コードを見つけることができます。
それは明るい背景に暗い連結領域(しみ)を探すことが一般的です。私たちの2値化された画像は、1ビット画像の白い背景(1)上の黒い前景(0)になります。
4連結アルゴリズムでは、以下に示すような構造要素を使用します(これはBovikの書籍にも記載されています)。一度あなたは4接続でちょっと変わったことがありましたら、8接続への拡張は明らかです。
我々は、左から右に画像内のピクセルの各行、および上から下へのすべての行をスキャンします。どのピクセル(x、y)についても、左隣(x-1、y)および上隣(x、y-1)は既に走査されているので、領域番号が既に1つまたは両方その隣人の例えば、画素(x、y-1)が領域8とラベル付けされ、(x、y)が前景画素でもある場合、領域8を(x、y)に割り当てる。ピクセル(x、y)が前景ピクセルであるが、左および上の隣接ピクセルが背景ピクセルである場合、(x、y)に新しい領域番号を割り当てる。
私はBovikのリファレンスをお勧めしますが、アルゴリズムの概要はここにあります。
- 領域番号輪郭(例えば「= 0領域」)
- を初期化は、後の処理のための「領域同値」データ構造を初期化します。
- 2値化しきい値を使用して白黒画像を作成します。
- イメージの各ピクセルを上から下、左から右へスキャンします。
- 領域0を任意の白色背景(1)ピクセルに割り当てます。任意黒前景画素(x、y)は、次の条件試験のため
:
- 上部および左ピクセルが前景されている場合、ための領域番号とする領域の番号(X-1、Y)を使用する(X 、y)、左と上の領域番号の等価性を追跡します。
- (x、y)が前景ピクセルの場合、その領域番号を(x、y)に使用します。
- 先頭隣接ピクセルのみがフォアグラウンドピクセルの場合は、 (x、y)の領域番号
- 左隣および最隣接画素が背景ピクセルの場合、領域番号を増やして、この新しい領域番号を(x、y)に割り当てます。
- イメージ全体に対してこの処理を完了した後、等価行列を分析し、等価領域の各集合を単一の領域に縮小します。
等価の削減は難しい部分です。下の画像では、領域はアルゴリズムに従って正しくラベル付けされています。画像は各地域番号ごとに異なる色を表示します。 3つの接触領域は、1つの接続領域に縮小されなければならない。
コードが1(黄色)で最も低い番号の領域に2(赤)及び3(ダークブルー)を再割り当てする等価データ構造をスキャンしなければなりません。リージョン番号の再割り当てが完了すると、リージョンのラベル付けが完了します。
等価性チェックの必要性を回避するワンパスアルゴリズムがありますが、このようなアルゴリズムは実装するのが少し困難です。まず、伝統的な4接続アルゴリズムを実装し、その問題を解決し、代わりに8接続を使用するオプションを導入することをお勧めします。 (このオプションは、画像処理ライブラリでは一般的です。)4連結および8連結領域のラベル付けが済むと、多くの用途に使用できる優れたアルゴリズムが得られます。サブジェクトに関する学術論文を検索する際には、「地域ラベル」、「ブロブ」、「輪郭」、「接続性」をチェックします。
バイナリ化する必要があるグレースケールアルゴリズムの場合、しきい値アルゴリズムは、アルゴリズムのチェーンの弱点になりがちです。閾値処理の助けを借りて、Gonzalez and Woodsの本のコピーを入手してください。 OCRの場合、Cheriet、Karma、Liu、Suenの書籍文字認識システムをチェックしてください。
スピードを上げるために、私はチェンとチャンの「成分追跡アルゴリズムを使ったコンポーネントラベリングアルゴリズム」のシングルパスアルゴリズムをお勧めします http://www.google.com/url?sa=t&rct=j&q=a% 20成分ラベル%20アルゴリズム%20%20%%20%%20%%20%20%%20%%20and%20chang&source = web&cd = 1&ved = 0CCIQFjAA&url = http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10 .1.1.95.6330%26rep%3Drep1%26type%3Dpdf> pjf-Tq2uBujf0QGDwdirAg&usg = AFQjCNFIL2Khb3lvHsGa-tToddlwnXJ2Fg&cad = rja – Rethunk