Pythonで8-Connectivity Connected-Component Labelingを実装する

Question

教育的な目的のために、私はPythonで文字と記号の認識プログラムを作成しています。

CCL - Wikipedia

しかし、私は、それは言及したがための情報を提供していない8連結の精度で1必要があります。私はここで情報を使用して作業連結成分ラベリング機能を作りました。右側の図には、北西と北東のピクセルを含める必要があることが示されていますが、どのようにして情報が見つからないのかわかりません。私はコードを要求していませんが、この方法に精通している人は、それらを組み込む方法を記述できますか？

Answer 1

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に接続されたアルゴリズムを実装することをお勧めします。あなたは、次のような本で擬似コードを見つけることができます。

• マシンビジョン：理論、アルゴリズム、第3版でERデイヴィス ことで実用性、6.3節を参照してください、「オブジェクトラベリングと数える」
• デジタルを画像処理 Gonzalez and Woods 9.5.3「接続されたコンポーネントの抽出」を参照 プレゼンテーションはあまり明確ではありませんが、これは画像処理のための標準的なオールインワンの教科書です。二値化のための閾値処理に関するセクションは良いです。国際版の料金は約35ドルです。
• 古い教科書には簡単な説明があるかもしれません。 BalladとBrownのコンピュータビジョンの
  の使用コピーはかなり安いです。その本では、アルゴリズム5.1はブロブの色付けと呼ばれています。
• お気に入りの簡単な説明は、の画像とビデオ処理のハンドブック Al Bovikによって編集された「領域ラベル付けアルゴリズム」の節にあります。便利なことに、ページ44から45には、Googleブックスでオンラインで入手できます：OCR用 http://books.google.com/books?id=UM_GCfJe88sC&q=region+labeling+algorithm#v=snippet&q=region%20labeling%20algorithm&f=false

それは明るい背景に暗い連結領域（しみ）を探すことが一般的です。私たちの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のリファレンスをお勧めしますが、アルゴリズムの概要はここにあります。

1. 領域番号輪郭（例えば「= 0領域」）
2. を初期化は、後の処理のための「領域同値」データ構造を初期化します。
3. 2値化しきい値を使用して白黒画像を作成します。
4. イメージの各ピクセルを上から下、左から右へスキャンします。
5. 領域0を任意の白色背景（1）ピクセルに割り当てます。任意黒前景画素（x、y）は、次の条件試験のため
：
• 上部および左ピクセルが前景されている場合、ための領域番号とする領域の番号（X-1、Y）を使用する（X 、y）、左と上の領域番号の等価性を追跡します。
• （x、y）が前景ピクセルの場合、その領域番号を（x、y）に使用します。
• 先頭隣接ピクセルのみがフォアグラウンドピクセルの場合は、 （x、y）の領域番号
• 左隣および最隣接画素が背景ピクセルの場合、領域番号を増やして、この新しい領域番号を（x、y）に割り当てます。
7. イメージ全体に対してこの処理を完了した後、等価行列を分析し、等価領域の各集合を単一の領域に縮小します。

等価の削減は難しい部分です。下の画像では、領域はアルゴリズムに従って正しくラベル付けされています。画像は各地域番号ごとに異なる色を表示します。 3つの接触領域は、1つの接続領域に縮小されなければならない。

コードが1（黄色）で最も低い番号の領域に2（赤）及び3（ダークブルー）を再割り当てする等価データ構造をスキャンしなければなりません。リージョン番号の再割り当てが完了すると、リージョンのラベル付けが完了します。

等価性チェックの必要性を回避するワンパスアルゴリズムがありますが、このようなアルゴリズムは実装するのが少し困難です。まず、伝統的な4接続アルゴリズムを実装し、その問題を解決し、代わりに8接続を使用するオプションを導入することをお勧めします。 （このオプションは、画像処理ライブラリでは一般的です。）4連結および8連結領域のラベル付けが済むと、多くの用途に使用できる優れたアルゴリズムが得られます。サブジェクトに関する学術論文を検索する際には、「地域ラベル」、「ブロブ」、「輪郭」、「接続性」をチェックします。

バイナリ化する必要があるグレースケールアルゴリズムの場合、しきい値アルゴリズムは、アルゴリズムのチェーンの弱点になりがちです。閾値処理の助けを借りて、Gonzalez and Woodsの本のコピーを入手してください。 OCRの場合、Cheriet、Karma、Liu、Suenの書籍文字認識システムをチェックしてください。

Answer 2

この実装では、8clclabeling、posted on Githubを提案しています。