Loading article…
連結成分ラベリング( CCL )、連結成分分析( CCA )、ブロブ抽出、領域ラベリング、ブロブ検出、または領域抽出は、グラフ理論のアルゴリズム応用であり、連結成分のサブセットが、与えられたヒューリスティックに基づいて一意にラベル付けされます。連結成分ラベリングは、セグメンテーションと混同しないでください。
連結成分ラベリングは、コンピュータビジョンにおいて、バイナリデジタル画像内の連結領域を検出するために使用されますが、カラー画像や高次元のデータも処理できます。[1] [2]画像認識システムやヒューマンコンピュータインタラクションインターフェースに統合されると、連結成分ラベリングはさまざまな情報に対して操作できます。[3] [4] ブロブ抽出は、通常、しきい値処理の結果として得られるバイナリ画像に対して実行されますが、グレースケール画像やカラー画像にも適用できます。ブロブはカウント、フィルタリング、追跡できます。
ブロブ抽出はブロブ検出と関連していますが、異なるものです。
概要
関連する入力データから、頂点と接続辺を含むグラフが構築されます。頂点には比較ヒューリスティックに必要な情報が含まれ、辺は接続された「近隣」を示します。アルゴリズムはグラフをトラバースし、接続性と近隣の相対値に基づいて頂点にラベルを付けます。接続性は媒体によって決まります。たとえば、画像グラフは4 接続近隣または8 接続近隣になります。[5]
ラベル付け段階の後、グラフはサブセットに分割され、その後元の情報が復元され、処理される可能性があります。
意味
学術文献では、接続コンポーネント ラベリング (CCL) という用語の使用とその定義は非常に一貫していますが、接続コンポーネント分析 (CCA) は用語と問題の定義の両方において異なります。
Rosenfeldら[6]は、連結成分のラベリングを「バイナリ入力画像の同じ連結成分に関連付けられた位置に一意のラベルが付けられたラベル付き画像の作成」と定義しています。Shapiroら[7]は、 CCLを「入力がバイナリ画像で、[...]出力が各ピクセルに割り当てられたラベルが、そのピクセルが属する連結成分を一意に識別する整数であるシンボリック画像である」演算子と定義しています[8] 。
学術文献ではCCAの定義についてのコンセンサスはありません。CCAはCCLと互換的に使用されることが多いです。[9] [10]より広範な定義は、Shapiroらによって与えられています。[7]「連結成分分析は、黒ピクセルの連結成分ラベル付けと、それに続く成分領域の特性測定および意思決定で構成されます。」ここで提示される連結成分分析の定義は、[7] [9] [10]で表現された考えを考慮に入れた、より一般的なものです。
アルゴリズム
議論されたアルゴリズムは、時間と空間の複雑さは増すものの、任意の次元に一般化できます。
一度に1つのコンポーネント
これは、実装と理解が非常に簡単で高速な方法です。グラフ理論のグラフトラバーサル法に基づいています。簡単に言うと、連結コンポーネントの最初のピクセルが見つかると、その連結コンポーネントのすべての連結ピクセルにラベルが付けられ、その後、画像内の次のピクセルに進みます。このアルゴリズムは、Vincent と Soille のウォーターシェッドセグメンテーションアルゴリズムの一部であり、[11]他の実装も存在します。[12]
これを行うには、相互に接続されたピクセルのインデックスを保持するリンク リストが形成されます (以下の手順 (2) と (3))。リンク リストを定義する方法は、深さ優先検索または幅優先検索の使用を指定します。この特定のアプリケーションでは、どちらの戦略を使用しても違いはありません。単一のリンク リストとして実装された最も単純な種類の後入れ先出しキューは、深さ優先検索戦略になります。
入力画像はバイナリ画像であり、ピクセルは背景または前景のいずれかであり、前景ピクセル内の接続されたコンポーネントが必要であると 想定されます。アルゴリズムの手順は次のように記述できます。
- 画像の最初のピクセルから開始します。現在のラベルを1に設定します。（2）に進みます。
- このピクセルが前景ピクセルであり、まだラベルが付いていない場合は、現在のラベルを付けてキューの最初の要素として追加し、(3)に進みます。背景ピクセルであるか、すでにラベルが付いていた場合は、画像内の次のピクセルに対して(2)を繰り返します。
- キューから要素を取り出し、その隣接要素を確認します（接続の種類に基づいて）。隣接要素が前景ピクセルであり、まだラベルが付けられていない場合は、現在のラベルを付けてキューに追加します。キューに要素がなくなるまで（3）を繰り返します。
- 画像の次のピクセルについては（2）に進み、現在のラベルを1増やします。
ピクセルはキューに入れられる前にラベル付けされることに注意してください。キューは、隣接するピクセルをチェックし、必要に応じてキューに追加するためにピクセルのみを保持します。このアルゴリズムでは、各前景ピクセルの隣接するピクセルを 1 回だけチェックする必要があり、背景ピクセルの隣接するピクセルはチェックしません。
疑似コードは次のとおりです:
アルゴリズムOneComponentAtATime(データ)
入力 : imageData[xDim][yDim]
初期化 : label = 0、labelArray[xDim][yDim] = 0、statusArray[xDim][yDim] = false、queue1、queue2;
i = 0からxDimの場合、 j = 0からyDimの場合、 imageData[i][j] が処理されていない場合、 imageData[i][j] が前景ピクセルの場合、
4つの隣り合うもの(北、南、東、西)を確認してください:
隣接ピクセルが処理されていない場合は実行し、
隣接ピクセルが前景ピクセルの場合は実行します。
キューに追加する1
それ以外
ステータスを処理済みとして更新する
終了の場合
labelArray[i][j] = label (ラベルを付ける)
statusArray[i][j] = true (ステータスを更新)
キュー1が空でない間は
キュー内の各ピクセルに対して次の操作を実行します。
チェックイットフォーズネイバーズ
隣接ピクセルが処理されていない場合は実行し、
隣接ピクセルが前景ピクセルの場合は実行します。
キューに追加2
それ以外
ステータスを処理済みとして更新する
終了の場合
現在のラベルを付ける
ステータスを処理済みとして更新する
キュー1から現在の要素を削除する
キュー2をキュー1にコピーする
終了 ながら
ラベルを増やす
そうでなければ終了
ステータスを処理済みとして更新する
終了の場合
終了の場合
終了の場合終了の場合
2パス
実装と理解が比較的簡単な2パスアルゴリズム[13] （ホシェン・コペルマンアルゴリズムとも呼ばれる）は、2次元バイナリデータを反復処理します。このアルゴリズムは、画像に対して2つのパスを実行します。最初のパスでは一時的なラベルを割り当てて同等性を記録し、2番目のパスでは各一時ラベルを同等性クラスの最小のラベルに置き換えます。
入力データはその場で変更される可能性があります (データ破損のリスクがあります)。また、ラベル付け情報は追加のデータ構造で維持される可能性があります。
接続性チェックは、隣接ピクセルのラベル（ラベルがまだ割り当てられていない隣接要素は無視されます）をチェックすることによって実行されます。つまり、現在のピクセルの北東、北、北西、西（8 接続性を想定）をチェックします。4 接続性では、現在のピクセルの北と西の隣接ピクセルのみを使用します。現在のピクセルに割り当てるラベルの値を決定するために、次の条件がチェックされます（4 接続性を想定）
確認する条件:
- 左 (西) のピクセルは現在のピクセルと同じ値を持ちますか?
- はい– 同じ領域にいます。現在のピクセルに同じラベルを割り当てます
- いいえ– 次の条件を確認してください
- 現在のピクセルの北と西の両方のピクセルは、現在のピクセルと同じ値を持ちますが、同じラベルではありませんか?
- はい– 北と西のピクセルは同じ領域に属しており、結合する必要があることがわかっています。現在のピクセルに北と西のラベルの最小値を割り当て、それらの同値関係を記録します。
- いいえ– 次の条件を確認してください
- 左 (西) のピクセルの値は異なり、北のピクセルの値は現在のピクセルと同じでしょうか?
- はい– 北のピクセルのラベルを現在のピクセルに割り当てます
- いいえ– 次の条件を確認してください
- ピクセルの北と西の隣接ピクセルのピクセル値は現在のピクセルと異なりますか?
- はい– 新しいラベルIDを作成し、現在のピクセルに割り当てます
アルゴリズムはこのように継続し、必要に応じて新しい領域ラベルを作成します。ただし、高速アルゴリズムの鍵となるのは、このマージがどのように行われるかです。このアルゴリズムは、同値関係を追跡するための優れたパフォーマンスを提供するunion-findデータ構造を使用します。 [14] union-find は基本的に、同じ blob に対応するラベルをdisjoint-set データ構造に格納し、インターフェイス メソッド (例: findSet(l)) を使用して 2 つのラベルの同値性を簡単に覚えられるようにします。findSet(l) は、関数の引数 'l' と同等の最小のラベル値を返します。
最初のラベル付けと同等性の記録が完了すると、2 番目のパスでは、各ピクセル ラベルを同等の分離セットの代表要素に置き換えるだけです。
連結領域抽出のための高速スキャンアルゴリズムを以下に示す。[15]
最初のパスでは:
- データの各要素を列ごとに、次に行ごとに反復処理します (ラスタースキャン)
- 要素が背景でない場合
- 現在の要素の隣接要素を取得します
- 隣接要素がない場合、現在の要素に一意のラベルを付けて続行します。
- それ以外の場合は、最小のラベルを持つ隣接要素を見つけて、それを現在の要素に割り当てます。
- 隣接するラベル間の同等性を保存する
2回目のパス:
- データの各要素を列ごとに、次に行ごとに繰り返し処理します。
- 要素が背景でない場合
- 最も低い同等のラベルを持つ要素にラベルを付け直す
ここで、背景はデータに固有の分類であり、目立つ要素を前景から区別するために使用されます。背景変数が省略されている場合、2 パス アルゴリズムは背景を別の領域として扱います。
2パスアルゴリズムのグラフィカルな例
1. 連結領域を抽出する配列は以下のとおりです（8連結性ベース）。
まず、グラフ内の要素に異なるバイナリ値を割り当てます。次のグラフの各要素の中央にある値「0～1」は要素の値ですが、次の 2 つのグラフの「1、2、...、7」の値は要素のラベルです。この 2 つの概念を混同しないでください。
.png/500px-Screenshot-Pixel_Region_(Figure_1).png){kind=tracking}
2. 最初のパスの後、次のラベルが生成されます。
.png/500px-Screenshot-Pixel_Region_(Figure_2).png){kind=tracking}
上記の条件に従って合計 7 つのラベルが生成されます。
生成されるラベルの同値関係は、
3. ラベルの結合が行われた後に生成された配列。ここでは、特定の領域で最小だったラベル値が接続された領域全体に「あふれ」、2 つの異なるラベルが生成され、したがって 2 つの異なるラベルが生成されます。
.png/500px-Screenshot-Pixel_Region_(Figure_3).png){kind=tracking}
4. 配列内で見つかった 2 つの異なる領域を明確に確認できるように、最終結果をカラーで表示します。
疑似コードは次のとおりです。
アルゴリズムTwoPass(データ)は
リンク = []
labels = データの次元を持つ構造体。Background の値で初期化されます。
次のラベル = 0
最初のパス
行内のデータに対して実行
行内の列に対して実行データ[行][列]が背景でない場合
隣接要素 = 現在の要素の値を持つ接続された要素
neighborsが空の場合、
linked[NextLabel] = NextLabelを含むセット
ラベル[行][列] = 次のラベル
次のラベル += 1
それ以外
最小のラベルを見つける
L = 近隣ラベル
labels[行][列] = min (L)
for label in L do
linked[label] = union (linked[label], L)
2回目のパス
行内のデータに対して実行
行内の列に対して実行データ[行][列]が背景でない場合
ラベル[行][列] = find (ラベル[行][列])
返品ラベル
findおよびunionアルゴリズムは、 union findで説明されているとおりに実装されています。
シーケンシャルアルゴリズム
地域カウンターを作成する
画像をスキャンします (次の例では、スキャンは左から右、上から下に行われるものと想定しています)。
- すべてのピクセルについて、指定された領域基準（つまり、バイナリ画像内の強度値 1、またはグレースケール画像内の接続されたピクセルと同様の強度）に対して、北と西のピクセル（4接続を考慮する場合）または北東、北、北西、西のピクセルの 8 接続をチェックします。
- 近隣のいずれも基準に適合しない場合は、領域カウンタの領域値を割り当てます。領域カウンタを増分します。
- 基準に適合する隣接ピクセルが 1 つだけの場合は、その領域にピクセルを割り当てます。
- 複数の隣接ピクセルが一致し、すべて同じ領域のメンバーである場合は、その領域にピクセルを割り当てます。
- 複数の隣接ピクセルが一致し、異なる領域のメンバーである場合、ピクセルをいずれかの領域に割り当てます (どの領域でもかまいません)。これらの領域はすべて同等であることを示します。
- 画像を再度スキャンし、同等の領域すべてに同じ領域値を割り当てます。
その他
2パスアルゴリズムに存在するいくつかのステップは、効率化のために統合することができ、画像を1回スキャンするだけで済みます。マルチパスアルゴリズムも存在し、その一部は画像のピクセル数に応じて線形時間で実行されます。 [16]
1990年代初頭、各ピクセルを順次処理するというボトルネックのため、画像解析アプリケーションにおける連結コンポーネントアルゴリズムの並列化に大きな関心が寄せられていました。 [17]
CUDA を広範に使用すると、アルゴリズムへの関心が再び高まります。
1コンポーネントずつアルゴリズムの擬似コード
アルゴリズム：
- 連結成分行列は画像行列のサイズに初期化されます。
- 画像内で検出されたオブジェクトごとにマークが初期化され、増加します。
- オブジェクトの数をカウントするためにカウンターが初期化されます。
- 画像全体に対して行優先スキャンが開始されます。
- オブジェクトピクセルが検出された場合、(インデックス!=0)の間、以下の手順が繰り返されます。
- イメージ内の対応するピクセルを 0 に設定します。
- 現在設定されているピクセルの隣接するすべてのピクセルでベクトル (インデックス) が更新されます。
- 一意のピクセルは保持され、重複したピクセルは削除されます。
- インデックスで指定されたピクセルを、接続コンポーネント行列でマークするように設定します。
- 画像内の別のオブジェクトのマーカーを増やします。
一度に 1 つのコンポーネント(画像)
[M, N] := サイズ(画像)
接続 := ゼロ(M, N)
マーク := 値
差異 := 増分
オフセット := [-1; M; 1; -M]
インデックス := []
オブジェクト数 := 0
i: 1:M の
場合、 j: 1:N の場合、if ( image ( i, j) == 1) then no_of_objects := no_of_objects + 1
index := [((j-1) × M + i)]
connected ( index ) := mark while ~isempty( index ) do image ( index ) := 0
neighbors := bsxfun(@plus, index , offsets )
neighbors := unique( neighbors (:))
index := neighbors (find( image ( neighbors )))
connected ( index ) := mark end while mark := mark + Difference end if end for end for
アルゴリズムの実行時間は、画像のサイズと前景の量によって異なります。前景が画像の大部分を占める場合、時間の複雑さは 2 パス アルゴリズムと同程度です。それ以外の場合、時間の複雑さは低くなります。ただし、メモリ アクセスは 2 パス アルゴリズムよりも構造化されていないため、実際には実行時間が長くなる傾向があります。
パフォーマンス評価
過去20年間で、接続コンポーネントラベリングに対する多くの新しいアプローチが提案されましたが、それらのほとんどは同じデータセットを使用して比較パフォーマンス評価を受けていません。YACCLAB [18] [19] (Yet Another Connected Components Labeling Benchmarkの頭字語) は、接続コンポーネントラベリングアルゴリズムを収集、実行、テストするC++オープンソースフレームワークの例です。
ハードウェアアーキテクチャ
複雑な画像処理タスクを実行するのに十分な容量を持つFPGAの出現により、接続コンポーネントラベリングのための高性能アーキテクチャも生まれました。[20] [21]これらのアーキテクチャのほとんどは、 FPGAで利用できるメモリリソースが限られているため、このアルゴリズムのシングルパスバリアントを利用しています。これらのタイプの接続コンポーネントラベリングアーキテクチャは、複数の画像ピクセルを並列に処理できるため、高いスループットと低い処理遅延を実現できます。
参照
参考文献
- ^ Samet, H.; Tamminen, M. (1988). 「線形バイナリツリーで表現された任意次元の画像の効率的なコンポーネントラベル付け」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 10 (4): 579. doi :10.1109/34.3918. S2CID 15911227.
- ^ Michael B. Dillencourt、 Hannan Samet、Markku Tamminen ( 1992)。「任意の画像表現に対する接続コンポーネントラベル付けの一般的なアプローチ」Journal of the ACM。39 ( 2): 253。CiteSeerX 10.1.1.73.8846。doi : 10.1145/128749.128750。S2CID 1869184。
- ^ Weijie Chen、Maryellen L. Giger、Ulrich Bick (2006)。「ダイナミックコントラスト強調MR画像における乳房病変のコンピュータセグメンテーションのためのファジーC平均法(FCM)ベースのアプローチ」。学術放射線学。13 (1):63–72。doi :10.1016/ j.acra.2005.08.035。PMID 16399033 。
- ^ Kesheng Wu、Wendy Koegler、Jacqueline Chen、Arie Shoshani (2003)。「ビットマップ インデックスを使用した大規模データセットのインタラクティブな探索」。SSDBM。
- ^ R. Fisher、S. Perkins、A. Walker、E. Wolfart (2003)。「接続コンポーネントのラベル付け」。
- ^ Rosenfeld, Azriel; Pfaltz, John L. (1966 年 10 月). 「デジタル画像処理における順次操作」. J. ACM . 13 (4): 471–494. doi :10.1145/321356.321357. ISSN 0004-5411. S2CID 7391071.
- ^ abc Shapiro, Linda G. (1996). 「連結コンポーネントのラベル付けと隣接グラフの構築」。デジタル画像処理のためのトポロジカルアルゴリズム。機械知能とパターン認識。第 19 巻。pp. 1–30。doi : 10.1016/s0923-0459(96) 80011-5。ISBN 9780444897541。
- ^ Klaiber, Michael J. (2016).再構成可能なハードウェアのための並列かつリソース効率の高い単一ルックアップ接続コンポーネント分析アーキテクチャ。シュトゥットガルト大学。
- ^ ab Fu, Y.; Chen, X.; Gao, H. (2009 年 12 月)。「Max-Tree に基づく新しい連結コンポーネント分析アルゴリズム」。2009年第 8 回 IEEE 国際会議、信頼性、自律性、およびセキュリティ コンピューティング。pp. 843–844。doi : 10.1109 /DASC.2009.150。ISBN 978-1-4244-5420-4. S2CID 6805048。
- ^ ab Grana, C.; Borghesani, D.; Santinelli, P.; Cucchiara, R. (2010 年 8 月)。「FPGA での高性能接続コンポーネントのラベル付け」。2010データベースおよびエキスパート システム アプリケーションに関するワークショップ。pp. 221–225。doi : 10.1109/DEXA.2010.57。ISBN 978-1-4244-8049-4. S2CID 6905027。
- ^ Vincent, Luc; Soille, Pierre (1991 年6 月)。「デジタル空間の分水嶺: 浸漬シミュレーションに基づく効率的なアルゴリズム」IEEE Transactions on Pattern Analysis and Machine Intelligence。13 (6): 583. doi :10.1109/34.87344. S2CID 15436061。
- ^ Abubaker, A; Qahwaji, R; Ipson, S; Saleh, M (2007). 「ワンスキャン接続コンポーネントラベリングテクニック」2007 IEEE 国際信号処理および通信会議。p. 1283。doi : 10.1109 / ICSPC.2007.4728561。ISBN 978-1-4244-1235-8. S2CID 10710012。
- ^ Shapiro, L.; Stockman, G. (2002). コンピュータビジョン(PDF) . Prentice Hall. pp. 69–73.
- ^ アルゴリズム入門、[1]、pp498
- ^ Lifeng He、Yuyan Chao、Suzuki, K. (2008 年 5 月 1日)。「実行ベースの 2 スキャン ラベリング アルゴリズム」。IEEE Transactions on Image Processing。17 ( 5 ): 749–756。Bibcode :2008ITIP...17..749H。doi :10.1109/TIP.2008.919369。PMID 18390379 。
- ^鈴木健二、堀場功、杉江昇 ( 2003)。「逐次ローカル操作に基づく線形時間接続コンポーネントラベリング」。コンピュータビジョンと画像理解。89 :1–23。doi : 10.1016/S1077-3142(02)00030-9。
- ^ Yujie Han; Robert A. Wagner (1990). 「効率的で高速な並列接続コンポーネントアルゴリズム」Journal of the ACM . 37 (3): 626. doi : 10.1145/79147.214077 . S2CID 17867876.
- ^ Grana, C.; Bolelli, F.; Baraldi, L.; Vezzani, R. (2016). 「YACCLAB - 連結コンポーネントのラベル付けベンチマークのもう 1 つ」(PDF)。第 23 回国際パターン認識会議。カンクン。
- ^ 「Yet Another Connected Components Labeling Benchmark: Prittt/YACCLAB」。GitHub 。2019-02-18。
- ^ Bailey, DG; Johnston, CT; Ma, Ni (2008 年 9 月)。「ストリーミング画像の接続コンポーネント分析」。2008年国際フィールド プログラマブル ロジックおよびアプリケーション会議。pp. 679–682。doi : 10.1109 / FPL.2008.4630038。ISBN 978-1-4244-1960-9. S2CID 6503327。
- ^ MJ Klaiber、DG Bailey、Y. Baroud、S. Simon ( 2015)。「接続コンポーネント分析のためのリソース効率の高いハードウェアアーキテクチャ」。IEEE Transactions on Circuits and Systems for Video Technology。26 ( 7): 1334–1349。doi : 10.1109 /TCSVT.2015.2450371。S2CID 10464417 。
一般的な
- ホーン、ベルトルド KP (1986)。ロボットビジョン。MITプレス。pp . 69–71。ISBN 978-0-262-08159-7。
- Al Bovik (2000). 画像およびビデオ処理ハンドブック(PDF) . Academic Press . pp. [37–70]. ISBN 0-12-119790-5。
外部リンク
- C#での実装
- 画像からのオブジェクトの抽出と直接接続コンポーネントのラベル付けアルゴリズムについて