2007.4.2.
石立 喬
Visual C++ 2005 Express Editionを用いた易しい画像処理（１２）
――― 分かり易いアルゴリズムで二値画像を細線化する―――
画像処理では、平滑化、鮮鋭化、エッジ検出などに次いで、細線化も良く用いられる。文字や物体を認識するには、それらの特徴を抽出する必要があり、太い線や塊では判別し難いからである。
概要
二値化された原画像を４方向から順次スキャンし、黒のピクセルを囲む周辺の８個のピクセルを調べて、３種類のパターン条件のうち、少なくとも一つに合致すれば、その中心の黒のピクセルを白に変して消去する。これを、消去が生じなくなるまで繰り返す。
細線化の必要性
細線化は、ThinningやSkeletonizationと呼ばれ、二値画像を幅１ピクセルの線画像に変換する処理である。短くなったり、線が途中で切れたり、孔が開いたりしてはいけない。得られた線は、元の図形の幅の中心に来ることが望ましい。
エッジ検出によって得られたエッジ画像は、元の画像の変化が比較的緩やかな所では、幅が広くなる。エッジ検出の閾値を高くすると幅は狭くなるが、より緩やかな変化を検出できない。したがって、エッジ検出処理後に細線化を行って、文字認識やパターン認識に使うことが多い。
細線化のアルゴリズム
細線化の手法は古くから研究され、種々の方法が知られている。ここでは、筆者による比較的分かりやすい方法を使用した。細線化の結果として得られた線が元の図形の中心部に来るように、左上→右下、右下→左上、右上→左下、左下→右上の順に周囲から狭めてゆく。消去できるかどうかを判断すべき１（黒）の点を中心に、左右または斜め方向の片方の半分が１（黒）で他方が０（白）の場合は、判断すべき点を０（白）にしても良いと考える。Hilditchのアルゴリズムに似ている点もあるが、線が途切れる欠点が無く、プログラムが単純化できる。
◎注目するピクセルとその周辺の呼び方
図１に示すように、消去できるかどうかを調べるピクセルをcenterとし、周囲のピクセルは、反時計回りに、p[0]からp[7]と呼ぶ。center、p[0]〜p[7]は、このプログラムでは、true（黒）またはfalse（白）の値を持つbool型にしてある。ただし、特にcenterと言う変数（オブジェクト）名は用いない。
図１ 消去できるかどうかを判定する周辺ピクセルの名称
◎画面左上から右下に向かって探索する場合に使用するパターン
画面左上から右下に向かって探索する場合には、左上が白（０）に、右下が黒（１）になっている場合を探し、下記のような状態の場合は中央のピクセル（丸で囲まれている）を１から０に変更する。XはDon't
care（どちらでも良い）を示す。
図２ 左上から右下に向かって探索する場合に消去できる条件
この条件を表す式は、左から
p[2]*p[3]*p[4]=1 で、かつ p[6]+p[7]+p[0]=0
p[3]*p[4]*p[5]=1 で、かつ p[7]+p[0]+p[1]=0
p[4]*p[5]*p[6]=1 で、かつ p[0]+p[1]+p[2]=0
である。
実際にプログラム上で記述する場合には、p[0] 〜 p[8]はbool型であるので、たとえば、「p[2]*p[3]*p[4]=1
で、かつ p[6]+p[7]+p[0]=0」の代わりに、「(p[2] && p[3] &&
p[4]) && !(p[6] || p[7] || p[0])」のようにする。「!」はbool型の変数に対して否定の演算を行う。
このような条件式は、添え字を１ずつ増やし（７の次は０）ながらforループで実行できる。上の例の場合には、添え字が２から始まるので、この値をstartと呼んでいる。１が３個並んでいる、反時計回りで最初のピクセルの添え字の値がstartであると考えると良い。
上記の場合は、start=2 であり、プログラムでは、start=UPPRER_LEFT として指定する（UPPER_LEFTは定数2として、別途定義しておく）。
◎画面右下から左上に向かって探索する場合に使用するパターン
図３ 右下から左上に向かって探索する場合に消去できる条件
この条件を表す式は、左から
p[6]*p[7]*p[0]=1 で、かつ p[2]+p[3]+p[4]=0
p[7]*p[0]*p[1]=1 で、かつ p[3]+p[4]+p[5]=0
p[0]*p[1]*p[2]=1 で、かつ p[4]+p[5]+p[6]=0
である。start=LOWER_RIGHTによって指定する（LOWER_RIGHT=2）。
◎画面右上から左下に向かって探索する場合に使用するパターン
図４ 右上から左下に向かって探索する場合に消去できる条件
この条件を表す式は、左から
p[0]*p[1]*p[2]=1 で、かつ p[4]+p[5]+p[6]=0
p[1]*p[2]*p[3]=1 で、かつ p[5]+p[6]+p[7]=0
p[2]*p[3]*p[4]=1 で、かつ p[6]+p[7]+p[0]=0
である。start=UPPER_RIGHTによって指定する（UPPER_RIGHT=0）。
◎画面左下から右上に向かって探索する場合に使用するパターン
図５ 左下から右上に向かって探索する場合に消去できる条件
この条件を表す式は、左から
p[4]*p[5]*p[6]=1 で、かつ p[0]+p[1]+p[2]=0
p[5]*p[6]*p[7]=1 で、かつ p[1]+p[2]+p[3]=0
p[6]*p[7]*p[0]=1 で、かつ p[2]+p[3]+p[4]=0
である。start=LOWER_LEFTによって指定する（LOWER_LEFT=4）。
プログラムの概要
◎ Form1_Paint()の内容
１）細線化したい二値原画像（幅WIDTH=320, 高さHEIGHT=240）をファイルから読み込み、Bitmapクラスのbmap_srcとし、パソコン画面左に表示する。
２）細線化を繰り返し実行する対象として、原画像の四辺をそれぞれ１ピクセルずつ拡張したBitmapクラスのbmap_thin（幅WIDTH+2,高さHEIGHT+2）を用意し、一旦全体を白で描画した後に、中央部にbmap_srcをコピーする。
３）bmap_thinから、細線化の対象とするbool型の配列target_pixels[i,j]を求める。
４）細線化処理として、change_flagがfalseのまま（変化がなかった）になるまで、以下を繰り返す。
・change_flagをfalseに設定する。
以下は、左上→右下、右下→左上、右上→左下、左下→右上の順で４回実行する。
・メソッドcopyTargetToCopied()により、target_pixels[i,j]をcopied_pixels[i,j]にコピーする。これは、消去したピクセルを直ちに次の判断に使用しないためである。
・copied_pixels[i,j]をスキャンして、もしそれが黒（true）であれば、そのピクセルを消去できるかを判断するメソッドthinImage(i,j,UPPER_LEFT)などを呼び出す。最初はUPPER_LEFTを使用するが、順次、LOWER_RIGHT、UPPER_RIGHT、LOWER_LEFTと指定を変えてゆく。
・四方からの細線化が一回終わると、得られたtarget_pixels[i,j]からbmap_thinを作り、画面の右側に描画する。
４）thinImage(i,j,UPPER_LEFT)など、四方向の細線化をすべて実施してもchange_flagがtrueで返されない場合は、それ以上消去するピクセルが無いことを表しているので、細線化の繰り返しを終了する。
◎メソッドthinImage(i,j,start)の内容
このメソッドは、指定された場所の黒ピクセルを、条件により白に変更する。引数として、場所と、探索の方向（左上→右下をあらわすUPPER_LEFTなど）が与えられる。
１）指定された場所（i,j）の周辺の８個のピクセルの値を、配列copied_pixelsから配列pにコピーする。
２）startによって指定された連続した３個のピクセルが黒（true）で、かつcenterに対して点対象の反対側の連続した３個のピクセルが白（false）の場合には、centerすなわち指定された場所（i,j）に対応するtarget_pixels[i,j]をfalseに設定し（消去する）、消去が行われたことを示すchange_flagをtrueに設定する。それ以上調べる必要は無いので、直ちにreturnで呼び出し元に戻る。
プログラム
array<bool,2>^ target_pixels;
array<bool,2>^ copied_pixels;
bool change_flag;
static int WIDTH=320,HEIGHT=240;
private: System::Void Form1_Load(System::Object^ sender, System::EventArgs^ e)
{
copied_pixels=gcnew array<bool,2>(WIDTH+2,HEIGHT+2);
target_pixels=gcnew array<bool,2>(WIDTH+2,HEIGHT+2);
}
private: System::Void Form1_Paint(System::Object^ sender, System::Windows::Forms::PaintEventArgs^
e) {
Graphics^ gr=e->Graphics;
int X0=10,Y0=10; //原画像の描画位置
int X1=339,Y1=10; //細線化画像の描画位置
int UPPER_LEFT=2,LOWER_RIGHT=6,UPPER_RIGHT=0,LOWER_LEFT=4;
Color color1;
int i,j;
Bitmap^ bmap_src=gcnew Bitmap("A:/sample.gif"); //原画像
Bitmap^ bmap_thin=gcnew Bitmap(WIDTH+2,HEIGHT+2); //周辺拡張画像で細線化の対象
gr->DrawImage(bmap_src,X0,Y0,WIDTH,HEIGHT); //原画像を左に表示する
//bmap_thinを全部白に設定する
for(j=0;j<HEIGHT+2;j++)
for(i=0;i<WIDTH+2;i++)
bmap_thin->SetPixel(i,j,Color::White);
//原画像をbmap_thinの中心にコピーする
for(j=0;j<HEIGHT;j++)
for(i=0;i<WIDTH;i++){
color1=bmap_src->GetPixel(i,j);
bmap_thin->SetPixel(i+1,j+1,color1);
}
//bmap_thinをtarget_pixels配列に変換する
for(j=0;j<HEIGHT+2;j++)
for(i=0;i<WIDTH+2;i++){
color1=bmap_thin->GetPixel(i,j);
if(color1.R<128) target_pixels[i,j]=true;
else target_pixels[i,j]=false;
}
//細線化を実行する
do{
change_flag=false;
//左上から
copyTargetToCopied();
for(j=1;j<=HEIGHT;j++)
for(i=1;i<=WIDTH;i++)
if(copied_pixels[i,j]) thinImage(i,j,UPPER_LEFT);
//右下から
copyTargetToCopied();
for(j=HEIGHT;j>=1;j--)
for(i=WIDTH;i>=1;i--)
if(copied_pixels[i,j]) thinImage(i,j,LOWER_RIGHT);
//右上から
copyTargetToCopied();
for(j=1;j<=HEIGHT;j++)
for(i=WIDTH;i>=1;i--)
if(copied_pixels[i,j]) thinImage(i,j,UPPER_RIGHT);
//左下から
copyTargetToCopied();
for(j=HEIGHT;j>=1;j--)
for(i=1;i<=WIDTH;i++)
if(copied_pixels[i,j]) thinImage(i,j,LOWER_LEFT);
//target_pixels[i,j]をbmap_thinに変換する
for(int j=0;j<HEIGHT+2;j++)
for(int i=0;i<WIDTH+2;i++){
if(target_pixels[i,j]) bmap_thin->SetPixel(i,j,Color::Black);
else bmap_thin->SetPixel(i,j,Color::White);
}
//bmap_thnを表示する
gr->DrawImage(bmap_thin,X1,Y1,WIDTH+2,HEIGHT+2);
}while(change_flag);
}
private: void thinImage(int i,int j,int start){
array<bool>^ p=gcnew array<bool>(8);
bool product,sum;
//周辺のデータをコピーする
p[0]=copied_pixels[i-1,j-1];
p[1]=copied_pixels[i-1,j];
p[2]=copied_pixels[i-1,j+1];
p[3]=copied_pixels[i,j+1];
p[4]=copied_pixels[i+1,j+1];
p[5]=copied_pixels[i+1,j];
p[6]=copied_pixels[i+1,j-1];
p[7]=copied_pixels[i,j-1];
//周辺の黒（true）の三個連続と白（false）の三個連続があれば、そのピクセルを白（false）にする
for(int k=start;k<start+3;k++){
product=p[k % 8] && p[(k+1) % 8] && p[(k+2) % 8];
//黒（true）の三個連続でtrueになる
sum=p[(k+4) % 8] || p[(k+5) % 8] || p[(k+6) % 8]; //白（false）の三個連続でfalseになる
if(product && !sum){
target_pixels[i,j]=false; //ピクセルを黒（true）から白（false）に変更
change_flag=true; //変更があった（消去した）ことを知らせる
return;
}
}
}
private: void copyTargetToCopied(void){
for(int j=0;j<HEIGHT+2;j++)
for(int i=0;i<WIDTH+2;i++)
copied_pixels[i,j]=target_pixels[i,j];
}
得られた結果
図６は英文字の場合の例で、左は細線化の前の二値原画像、右は細線化後の画像である。
図６ 英文字の細線化例
図７は図形の場合を示したもので、四方向から追って行くため、円形の図形に対してＸの形が現れる。
図７ 色々な図形の細線化例
細線化を四方から行うのは必須条件であるが、参考までに、左上→右下のみの例を図７の左に、左上→右下と右下→左上のみの例を図７の右に示す。
図７ 細線化を四方から行わなかった場合の例