とりあえずできればいいやという方法
以下の例では、8連結でラベリングを行います。
/* 2値画像に対するラベリング 入力画像は0か1の値を持つ 以下の例では、出力画像のビット数が8なので、ラベルの最大数は2〜255の256個 */ BOOL label_image ( BOOL *btaIn, BYTE *btaOut, int nRow, int nCol, int *pnLabel ) { int i, j, nLabel; for ( i = 0; i < nRow; i++ ) { for ( j = 0; j < nCol; j++ ) { btaOut[i*nCol+j] = btaIn[i*nCol+j]; } } nLabel = 2; /* 入力画像は1までの値を持つため、ラベル番号は2から */ for ( i = 0; i < nRow; i++ ) { for ( j = 0; j < nCol; j++ ) { if ( btaOut[i*nCol+j] ) { if ( nLabel >= 255 ) { fprintf( stderr, "Label Num is Over 255, Stop" ); return FALSE; } } search_label( btaOut, nRow, nCol, i, j, nLabel ); nLabel++; } } return TRUE; } /* 入力された開始位置のピクセルに連結する対象ピクセルに、すべてラベルをつける */ void search_label ( BYTE *btaIn, int nRow, in nCol, int nY, int nX, int nLabel ) { int i, j; int nNewPix /* 新しくラベルがつけられたピクセル数 */ int nPX, nPY, nQX, nQY; /* まずは、スタート位置にラベル */ btaIn[nY*nCOl+nX] = nLabel; while ( TRUE ) { nNewPix = 0; for ( i = 0; i < nRow; i++ ) { for ( j = 0; j < nCol; j++ ) { /* 現在のラベル番号がつけられた画素を探す */ if ( btaIn[i*nCol+j] == nLabel ) { iPX = j - 1; iPY = i - 1; iQX = j + 1; iQY = i + 1; if ( iPX < 0 ) iPX = 0; if ( iPY < 0 ) iPY = 0; if ( iQX > nCol-1 ) iQX = nCol-1; if ( iQY > nRow-1 ) iQY = nRow-1; if ( btaIn[iPY*nCol+iPX] ){ btaIn[iPY*nCol+iPX] = nLabel; nNewPix++; } if ( btaIn[iPY*nCol+j ] ){ btaIn[iPY*nCol+j ] = nLabel; nNewPix++; } if ( btaIn[iPY*nCol+iQX] ){ btaIn[iPY*nCol+iQX] = nLabel; nNewPix++; } if ( btaIn[i *nCol+iPX] ){ btaIn[i *nCol+iPX] = nLabel; nNewPix++; } if ( btaIn[i *nCol+iQX] ){ btaIn[i *nCol+iQX] = nLabel; nNewPix++; } if ( btaIn[iQY*nCol+iPX] ){ btaIn[iQY*nCol+iPX] = nLabel; nNewPix++; } if ( btaIn[iQY*nCol+j ] ){ btaIn[iQY*nCol+j ] = nLabel; nNewPix++; } if ( btaIn[iQY*nCol+iQX] ){ btaIn[iQY*nCol+iQX] = nLabel; nNewPix++; } } } } /* ラベル対象がなくなったら終了 */ if ( !nNewPix ) break; } }
かなり無駄が多いように思われるかもしれません。
とくに、search_label関数の最後の判定文がforループの外にあるのが
無駄に思えますが、こうでないと正しくラベリングされません。
このことからわかるように、このコードでは、ラベリング対象が1pixelの場合は1回、
ラベリング対象となるピクセルが2pixel以上の場合は、
大小にかかわらず画像全体が最低2回スキャンされます。
小さい領域を無視したい場合はあらかじめ何らかの方法でそれらを除去しておいてから
ラベリングを行わないと、処理時間がものすごくかかってしまいます。
ルックアップテーブル参照方式によるラベリング
上の例ではあまりにもダサいので、より効率がいいラベリングの方法がいくつかあります。
ここでは、そのうちのひとつのルックアップテーブルを使う方法を紹介します。
この方法は３段階でラベリングを行います。
第１段階は、まず画像を１回スキャンして以下の要領で仮ラベルをつけていきます。
- 注目画素の上にラベルがあったらそのラベルをつける
- 上にラベルが無く、左上にラベルがあったらそのラベルをつける。
このとき右上にもラベルがあって、つけたラベルと違う場合は接続情報に記録する。 - 上、左上にラベルが無く、右上にラベルがあったらそのラベルをつける。
- この時点で注目画素にラベルがつけられ、左にラベルがあってそれと異なる場合は
接続情報に記録する。 - 上の行がすべてラベルなしで、左にラベルありならそのラベルをつける。
- 上の行、左すべてにラベルが無いなら新しいラベルをつける。
接続情報とは、２つの仮ラベルを最終的には同じラベルにするためのものです。
ここまでのコードはこんな感じでしょうか。
なお、今回も入力画像は背景0、前景1になっているとして、ラベルは2からスタートとします。
typedef struct { int n1; int n2; } CONNECT_INFO; std::vector<CONNECT_INFO> vLUT; int nMaxLabel; void addInfo( int n1, int n2 ) { CONNECT_INFO sLUT; sLUT.n1 = n1 < n2 ? n1 : n2; sLUT.n2 = n1 > n2 ? n1 : n2; if ( sLUT.n2 > nMaxLabel ) nMaxLabel = sLUT.n2; vLUT.push_back( sLUT ); } int Labeling2( LPDWORD pImg, int nRow, int nCol ) { int i, j; int nLabel = 2; for ( i = 0; i < nRow; i++ ) { for ( j = 0; j < nCol; j++ ) { if ( pImg[i*nCol+j] == 1 ) { // 上がラベルありの場合 if ( i > 0 && pImg[(i-1)*nCol+j] >= 2 ) { pImg[i*nCol+j] = pImg[(i-1)*nCol+j]; } // 左上がラベルありの場合 else if ( i > 0 && j > 0 && pImg[(i-1)*nCol+(j-1)] >= 2 ) { pImg[i*nCol+j] = pImg[(i-1)*nCol+(j-1)]; // 右上がラベルありの場合は // LUTに記録 if ( j < nCol-1 && pImg[(i-1)*nCol+(j+1)] >= 2 && pImg[(i-1)*nCol+(j+1)] != pImg[i*nCol+j] ) { addInfo( pImg[i*nCol+j], pImg[(i-1)*nCol+(j+1)] ); } } // 上、左上ともにラベルなしで右上がラベルありの場合 // 右上のラベルをつける else if ( i > 0 && j < nCol-1 && pImg[(i-1)*nCol+(j+1)] >= 2 ) { pImg[i*nCol+j] = pImg[(i-1)*nCol+(j+1)]; } // 左がラベルありの場合 if ( j > 0 && pImg[i*nCol+(j-1)] >= 2 ) { // 今の画素にもうラベルがついていて、 // なおかつ違っていたらルックアップテーブルに記録 if ( pImg[i*nCol+j] >= 2 && pImg[i*nCol+j] != pImg[i*nCol+(j-1)] ) { addInfo( pImg[i*nCol+j], pImg[i*nCol+(j-1)] ); } } // まだなら左のラベルをつける if ( i > 0 && j > 0 && pImg[(i-1)*nCol+j] == 0 && pImg[(i-1)*nCol+(j-1)] == 0 && pImg[i*nCol+(j-1)] >= 2 ) { pImg[i*nCol+j] = pImg[i*nCol+(j-1)]; } if ( i == 0 && pImg[i*nCol+(j-1)] >= 2 ) { pImg[i*nCol+j] = pImg[i*nCol+(j-1)]; } // すべてまだなら新しいラベル if ( pImg[i*nCol+j] == 1 ) { pImg[i*nCol+j] = nLabel; nLabel++; } } } } // 続く
接続情報は、値の大小を考慮して記録するようにしています。
次に、接続情報からルックアップテーブルを作成します。
ルックアップテーブルは仮ラベルと本ラベルの変換テーブルとして使用するものです。
ここでは以下のような手順でルックアップテーブルを作成しています。
例として、接続情報が次のように記録されていたとします。
まず、現在のラベルを最小値の”2″として、ラベル”2″と接続するラベル番号をすべて拾います。
この場合、”4″と”7″を取り出します。
取り出された接続情報はもう使用しないので削除します。
つぎに、”2″と接続するラベルに接続するラベルを取り出します。
ここでは”7″に接続する”6″と”15″が取り出されます。
これを繰り返して、最終的に”2″と接続するラベルをすべて抽出します。
現在のラベルに接続するすべてのラベルを拾い終わったら、ルックアップテーブルに記録します。
ここでは簡単に配列を用意して、下のように記録します。
こんな要領でルックアップテーブルを作成します。
この部分のコードはこんな感じでしょうか。
bool operator<( CONNECT_INFO &a, CONNECT_INFO &b ) { return a.n1 == b.n1 ? a.n2 < b.n2 : a.n1 < b.n1; } bool operator==( CONNECT_INFO &a, CONNECT_INFO &b ) { return a.n1 == b.n1 && a.n2 == b.n2; } int *pRLUT; void InitLUT() { nMaxLabel = 0; } void RegulateLUT() { std::vector<CONNECT_INFO>::iterator pEnd, p; std::vector<int> vSubLabel; std::vector<int>::iterator q; int nCurLabel, nSubLabel; int i; UINT nSub; std::sort( vLUT.begin(), vLUT.end() ); pEnd = std::unique( vLUT.begin(), vLUT.end() ); vLUT.erase( pEnd, vLUT.end() ); pRLUT = new int[nMaxLabel+2]; memset( pRLUT, 0, nMaxLabel*sizeof(int) ); nCurLabel = 2; while ( TRUE ) { // pRLUTから最初の0のラベルを見つける while ( pRLUT[nCurLabel] != 0 ) { nCurLabel++; } pRLUT[nCurLabel] = nCurLabel; // 現在のラベルに接続するすべてのラベルを拾い出す p = vLUT.begin(); while ( p != vLUT.end() ) { if ( p->n1 == nCurLabel ) { vSubLabel.push_back( p->n2 ); p = vLUT.erase( p ); } else if ( p->n2 == nCurLabel ) { vSubLabel.push_back( p->n1 ); p = vLUT.erase( p ); } else p++; } // 次に、接続するラベルにさらに接続するのを拾い出す nSub = 0; while ( nSub < vSubLabel.size() ) { nSubLabel = vSubLabel[nSub]; p = vLUT.begin(); while ( p != vLUT.end() ) { if ( p->n1 == nSubLabel && p->n2 != nCurLabel ) { vSubLabel.push_back( p->n2 ); p = vLUT.erase( p ); } else if ( p->n2 == nSubLabel && p->n1 != nCurLabel ) { vSubLabel.push_back( p->n1 ); p = vLUT.erase( p ); } else p++; } nSub++; } // 関連するラベルをすべて拾い終わったらpRLUTに現在のラベルを書き込み for ( q = vSubLabel.begin(); q != vSubLabel.end(); q++ ) { pRLUT[*q] = nCurLabel; } vSubLabel.clear(); if ( ++nCurLabel > nMaxLabel ) break; } vLUT.clear(); }
あとは再度画像をスキャンして、
ルックアップテーブルにしたがって仮ラベルを本ラベルに書き換えれば完了です。
その部分はこんな感じでしょうか。
int GetLUT( int n ) { if ( n > nMaxLabel ) return 0; return pRLUT[n] == n ? n : pRLUT[n]; } void ClearLUT() { delete[] pRLUT; } //////////////////////////////////////////// // 続き // LUTを整理 RegulateLUT(); // ラベルつけなおし for ( i = 0; i < nRow; i++ ) { for ( j = 0; j < nCol; j++ ) { if ( pImg[i*nCol+j] != 0 ) { pImg[i*nCol+j] = GetLUT( pImg[i*nCol+j] ); } } } ClearLUT(); return nLabel-2; }
果たしてこんなので正しくできているでしょうか。下の画像が入力画像と実行結果です。
とりあえずできているようです。
この方法は画像のスキャンは２回で済みますが、ルックアップテーブル作成の部分で結構時間がかかります。
その部分はもうちょっと工夫する余地はあるかと思います。
OpenCV
プログラミングブック 第2版 OpenCV 1.1対応
にも紹介されているライブラリラベリングクラス
のほうが断然いいはずです。
