ラベリング処理というのは入力画像に対して、連結する画素(同じ色とか、同じ領域とか)ごとに同じ番号を割り振る処理のことです。領域別に処理する際の前処理に使ったり、画像中の微小領域のサイズを測定してノイズ除去に使ったりと色々と有用です。アルゴリズム入門 : 第 3 章 画像処理入門 1を読むとイメージが湧くかと思います。
.gif "ラベリング処理のイメージ図")
ラベリング処理は1970年代から知られている処理ですが、高速なアルゴリズムが意外と知られていません。ネットで検索すると大学の授業での説明資料が見つかる程度で、文献をあたっても解説があまりにも少なく多くは役に立ちません。
古い本でラベリング処理のアルゴリズムが詳しく説明されたものを見つけたので多くの人に有用と思い、ここに書いておきます。参考にした本は近代科学社発行の長尾真さんによる「デジタル画像処理」で、1978年に発行されています。ラベリング処理の紹介は360ページ〜361ページに有ります。
１：値を隣接する画素に伝搬させる
Sの成分をラベル付けする簡単な手続きは、探索と”伝搬”からなるものである。1が見つかるまでSを走査し、その値をまだ使われてない最初のラベルの値、たとえばvに変える。そしてvを1に向けて繰り返し(必要なら並列に)伝搬させる。すなわち、vを近傍として持つ1をvに変える。もはや変化の可能性がなくなったとき、明らかに最初のvに連結した1は全てvになっている。ここでさらに走査を続ける。別の1が見つかれば、これはv成分には属してないので、新しいラベルを付けて同じ手続を繰り返す。
Sが処理対象の画像、ラベル付けする対象が1、割り振るラベル値がvです。
この手法は「この手続は簡単ではあるが、非常に時間がかかる。各々の伝搬の過程は、たとえ並列に処理しても、図形の面積の次数だけの反復を要するからである。」と紹介されています。最初に紹介したMSのサイトで使われているのがまさにこれです。おすすめできません。
２：境界線を抽出し、輪郭内部に同一の値を割り振る
成分のラベル付けの別な方法としては、9.1.2節で述べた境界を見つける手法を、いくつかの外側境界(すなわち、Sの成分でこれを囲むS^の成分に隣接している境界。演習9参照)を別々にマークを付けるよう修正し、各成分の外側境界に異なったラベルを用いる。これが済むと、必要に応じて外側境界のラベルを成分の内側へ”伝搬”させることができる。これを並列に行うなら、たかだか図形の半径に等しい反復数を要する。
手当たりしだいに伝搬させるのではなく、まずは領域の輪郭にユニークなラベル番号を付与し、必要であれば内側に値をコピーする。1番よりは効率的ですが、「外側境界のラベル付けの手続きは時間がかかる
」処理であり、図形の面積につれて増加する多数のステップを有します。
３：行毎に横のつながり(ラン)を求め、上下の対照表をもとにつなげて行く
たいていの目的には、境界よりむしろ1のランを追跡してラベル付けをする次の手法が最良策である。図形の第１行目において、各ランに異なったラベルを与える。第２(とそれ以下の)行では、１のランを調べて前行のランと位置を比べる。ランρが前行のどのランとも隣接していなければρに新しいラベルを付ける。ρが前行のちょうど１つのランに隣接しているなら、そのランのラベルを付ける。ρが前行の２つ以上のランに隣接しているなら、ρにはこれらのらべるの(たとえば)最小値を付けるが、これらのラベルはすべて同一成分に属することも控えておく。図形がこのようにしてすべて走査されたとき、控えを分類して等しいラベルの集まりを決定できる。必要なら、図形を再走査し各ラベルを、たとえば等価な最小の値のラベルに置き換えることが出来る。
ということで、3番目がおすすめです。処理時間が画像サイズに依存して決まるし、ラスタ走査のみなのでメモリ上のキャッシュも有効に動いてくれるでしょう。
上の説明文を素直に実装すれば効率のよいラベリング処理を実現出来るでしょう。
