はじめに
細線化はThinningやSkeletonizationと呼ばれ、二値画像（白と黒の色だけで表現された2階調の画像）を幅1ピクセルの線画像に変換する処理です。線が途中で切れたり、孔が開いたりしてはいけません。得られた線は、元の図形の幅の中心にくることが望まれます。
エッジ検出によって得られた画像は、元の画像の変化が比較的緩やかで広範囲な場合には、幅が広くなってしまいます。エッジ検出の閾値を高くすると幅は狭くなりますが、緩やかな変化を見逃してしまいます。したがって、閾値を低く選んで、幅広くエッジ部分を出させ、その後に細線化処理を行って、文字認識やパターン認識に使うことが多いのです。
対象読者
画像処理に関心があり、パターン認識の前処理を学習したい人。
必要な環境
J2SE 5.0を使っていますが、それより若干古いバージョンでも大丈夫です。CPUパワーは、大きい方がストレスを感じません。
細線化のアルゴリズム
細線化の手法は古くから研究され、種々の方法が知られています。ここでは、プログラム化しやすく、比較的分かりやすい方法を述べます。得られた線が元の図形の中心部に来るように、左上→右下、右下→左上、右上→左下、左下→右上の順に周囲から狭めてゆく方法を採ります。注目する「1（黒）」のピクセルを中心に、3 x 3のピクセルの半分が「1（黒）」で他方が「0（白）」の場合は、注目する点を「0（白）」にしても良いと考えるのが基本原理です。Hilditchのアルゴリズムに似ていますが、線が途切れることがありません。
注目するピクセルとその周辺の呼び方
図1に示すように、消去できるかどうかを調べるピクセルを「center」と呼び、周囲のピクセルは、反時計回りに、p[0]からp[7]と呼びます。center、p[0]～p[7]は1（黒）または0（白）の値を持ちます。このプログラムでは、byte型にしてありますが、「1」または「0」の値しかとりません。なお、プログラムの中では、実際にcenterという名称を用いるわけではなく、プログラム中のnew_pixels[i][j]やold_pixels[i][j]に相当します。周囲のピクセルは、配列の添え字を増加させながら、選択します。8で割った剰余を採っていますので、7の次は0になります。
画面左上から右下に向かって探索する場合に使用するパターン
画面左上から右下に向かって探索する場合には、左上が「白（0）」に、右下が「黒（1）」になっている場合を探します。この条件は、下記のような3種類の状態があります。いずれの場合も、中央のピクセル（丸で囲まれている）を「1」から「0」に変更（消去）することができます。「X」はDon't care（「1」または「0」のどちらでも良い）を示します。
この条件を表す式は、左から
p[2]*p[3]*p[4]=1で、かつp[6]+p[7]+p[0]=0p[3]*p[4]*p[5]=1で、かつp[7]+p[0]+p[1]=0p[4]*p[5]*p[6]=1で、かつp[0]+p[1]+p[2]=0
です。
このような条件式は、添え字を1ずつ増やし（7の次は0）ながらforループで実行できます。上の場合には、添え字が2から始まるので、この値をstartと呼んでいます。「1」が3個並んでいる、最初の場所がstartであると考えるとわかりやすいと思います。start=2とは、左上から右下に向かって探索することを意味します。実際には、UPPER_LEFT=2と定義して、2の代わりにUPPER_LEFTを使っています。
画面右下から左上に向かって探索する場合に使用するパターン
画面右下から左上に向かって探索する場合には、右下が「白（0）」に、左上が「黒（1）」になっている場合を探します。この条件は、下記のような3種類の状態があります。
この条件を表す式は、左から
p[6]*p[7]*p[0]=1で、かつp[2]+p[3]+p[4]=0p[7]*p[0]*p[1]=1で、かつp[3]+p[4]+p[5]=0p[0]*p[1]*p[2]=1で、かつp[4]+p[5]+p[6]=0
です。
start = 6 (LOWER_RIGHT）です。
画面右上から左下に向かって探索する場合に使用するパターン
画面右上から左下に向かって探索する場合には、右上0が「白（0）」に、左下が「黒（1）」になっている場合を探します。この条件は、下記のような3種類の状態があります。
この条件を表す式は、左から
p[0]*p[1]*p[2]=1で、かつp[4]+p[5]+p[6]=0p[1]*p[2]*p[3]=1で、かつp[5]+p[6]+p[7]=0p[2]*p[3]*p[4]=1で、かつp[6]+p[7]+p[0]=0
です。
start = 0 (UPPER_RIGHT）です。
画面左下から右上に向かって探索する場合に使用するパターン
画面左下から右上に向かって探索する場合には、左下が「白（0）」に、右上が「黒（1）」になっている場合を探します。この条件は、下記のような3種類の状態があります。
この条件を表す式は、左から
p[4]*p[5]*p[6]=1で、かつp[0]+p[1]+p[2]=0p[5]*p[6]*p[7]=1で、かつp[1]+p[2]+p[3]=0p[6]*p[7]*p[0]=1で、かつp[2]+p[3]+p[4]=0
です。
start = 4 (LOWER_LEFT）です。
プログラムの概要
このプログラムは次の部分から成っています。なお、簡単化するために、使用する画像のサイズを、あらかじめ320 x 240に固定してあります。一般化するには、若干のコードを追加する必要があります。このプログラムで、もっとも頻繁に用いられるのはthinImageメソッドです。この中では、CPUのキャッシュを有効に活用できませんので、old_pixels[i][j]の代わりにold_pixels[j][i]を用いるなどの特別な配慮はしていません。
準備段階
- メソッド
readImageFileを使用して、細線化したい原画像を、画像img_srcとして読み込みます。 - メソッド
create2DBinaryExpandedを使用して、img_srcを一次元カラーデータrgb[]に変換し、原画像の周辺を上下左右1ピクセルずつ拡張した二次元二値データnew_pixels[][]の中央部に二値データとして書き込みます。この様子は、図6に示します。すなわち、原画像は一次元データrgb[]として、図の上部のように並んでいます。拡張した図形は、図の下部に示してあり、ここでは、二次元二値データnew_pixels[][]で表してあります。
rgb[(j-1)*WIDTH+(i-1)]をnew_pixels[i][j]に代入すればよいことが分かります。ここで、iとjは、拡張後の画像のものを使っていますので、拡張前の画像を参照するためには、i-1やj-1のように1を減じる必要があります。
実行段階
図7に示すように、細線化プログラムの実行部分は下記のようになっています。
- 細線化の前の拡張画像
img_expを画面左側に描画します（図7では省略）。 do～whileループ内では、変化があった（すなわち、「黒」のピクセルを「白」に置き換えた）ことを示すフラグchange_flagが1である間、下記を繰り返します。- 左上からの細線化
- 右下からの細線化（説明省略）
- 右上からの細線化（説明省略）
- 左下からの細線化（説明省略）
それまでの画像（new_pixels[i][j]による）を画面右側に描画し、new_pixels[i][j]を、細線化の対象となるold_pixels[i][j]にコピーします。以上は、メソッドdrawAndCopyで行います。次に、old_pixels[i][j]を細線化し、「黒」から「白」への変化があった場合は、new_pixels[i][j]に「0」を書き込み、変化があったことを示すために、change_flagを「1」にします。これらは、メソッドthinImageで行います。
new_pixels[i][j]を、一旦old_pixels[i][j]にコピーしてからold_pixels[i][j]上のみで細線化を行うのは、細線化による直前の消去を即時に次の細線化に反映させないためです（即時に反映させると、消去が一挙に進み、四方から徐々に狭めて行くことができなくなります）。一連のスキャンが終ってから、次のスキャンが始まるまでの間に、一斉にold_pixels[i][j]をnew_pixels[i][j]でアップデートします。
プログラム
import java.awt.*; import java.awt.image.*; import javax.swing.*; public class Thinning extends JApplet{ Image img_src,img_exp; byte change_flag; static final int WIDTH=320,HEIGHT=240,SIZE=76800; static final int UPPER_LEFT=2,LOWER_RIGHT=6,UPPER_RIGHT=0,LOWER_LEFT=4; byte[][] new_pixels=new byte[WIDTH+2][HEIGHT+2]; byte[][] old_pixels=new byte[WIDTH+2][HEIGHT+2]; public void init(){ //原画像を読み込む img_src=readImageFile("sample.gif"); //原画像を拡張し、二次元二値データを作る create2DBinaryExpanded(img_src); } //原画像を読み込むメソッド public Image readImageFile(String filename){ Image img=getImage(getDocumentBase(),filename); MediaTracker mtracker=new MediaTracker(this); mtracker.addImage(img,0); try{ mtracker.waitForAll(); }catch(Exception e){} return img; } //原画像を拡張し、細線化のための二次元二値データを生成するメソッド public void create2DBinaryExpanded(Image img){ int[] rgb=new int[WIDTH*HEIGHT]; Color color; int d; //原画像imgを一次元RGBデータrgb[]にする PixelGrabber grabber= new PixelGrabber(img,0,0,WIDTH,HEIGHT,rgb,0,WIDTH); try{ grabber.grabPixels(); }catch(InterruptedException e){} //拡張画像を作り、その二次元二値データをすべて白(0)に設定する for(int j=0;j<HEIGHT+2;j++) for(int i=0;i<WIDTH+2;i++) new_pixels[i][j]=0; //原画像の一次元RGBデータrgb[]を、 //拡張画像の中央部に二次元化して書き込む for(int j=1;j<HEIGHT+1;j++) for(int i=1;i<WIDTH+1;i++){ color=new Color(rgb[(j-1)*WIDTH+(i-1)]); d=color.getRed(); if(d<128) new_pixels[i][j]=1; //黒に設定 } } public void paint(Graphics g){ int width=WIDTH+2; int height=HEIGHT+2; int size=width*height; g.drawImage(img_src,10,10,null); //原画像を画面の左側に描画 //細線化を実施する do{ change_flag=0; drawAndCopy(g,width,height); //描画とコピー for(int j=1;j<height-1;j++) //左上から細線化 for(int i=1;i<width-1;i++) if(old_pixels[i][j]==1) thinImage(i,j,UPPER_LEFT); drawAndCopy(g,width,height); //描画とコピー for(int j=height-2;j>=1;j--) //右下から細線化 for(int i=width-2;i>=1;i--) if(old_pixels[i][j]==1) thinImage(i,j,LOWER_RIGHT); drawAndCopy(g,width,height); //描画とコピー for(int j=1;j<height-1;j++) //右上から細線化 for(int i=width-2;i>=1;i--) if(old_pixels[i][j]==1) thinImage(i,j,UPPER_RIGHT); drawAndCopy(g,width,height); //描画とコピー for(int j=height-2;j>=1;j--) //左下から細線化 for(int i=1;i<width-1;i++) if(old_pixels[i][j]==1) thinImage(i,j,LOWER_LEFT); }while(change_flag==1); } //描画とコピーのメソッド void drawAndCopy(Graphics g,int _width,int _height){ for(int j=0;j<_height;j++) for(int i=0;i<_width;i++){ if(new_pixels[i][j]==1) g.setColor(Color.black); else g.setColor(Color.white); //細線化画像を画面右側に描画 g.drawRect(WIDTH+40+i,10+j,1,1); //次の細線化のためのコピー old_pixels[i][j]=new_pixels[i][j]; } } //細線化のメソッド public void thinImage(int i,int j,int start){ byte[] p=new byte[8]; int product,sum; p[0]=old_pixels[i-1][j-1]; p[1]=old_pixels[i-1][j]; p[2]=old_pixels[i-1][j+1]; p[3]=old_pixels[i][j+1]; p[4]=old_pixels[i+1][j+1]; p[5]=old_pixels[i+1][j]; p[6]=old_pixels[i+1][j-1]; p[7]=old_pixels[i][j-1]; for(int k=start;k<start+3;k++){ product=p[k % 8]*p[(k+1) % 8]*p[(k+2) % 8]; sum=p[(k+4) % 8]+p[(k+5) % 8]+p[(k+6) % 8]; if(product==1 && sum==0){ new_pixels[i][j]=0; //消去する change_flag=1; return; } } } }
得られた画面
図8で、左は細線化前の画像、右は細線化後の最終的な画像です。CPUの能力にも依りますが、右側の画像は、時間と共に徐々に細線化されて行きます。円は、細線化すると一個の点になるべきですが、四方向から細線化して行く特徴が出て、「×」になっています。
まとめ
画像の細線化は、画像処理の中では、比較的利用度の高いものです。細線化の前処理として、画像の拡張を実施していますが、これも重要なテクニックです。細線化は、注目するピクセルの周辺のピクセルをプログラム上で回転させるという、シンプルで面白い方法を提案しました。円を細線化すると「×」になるのは、黒画像の周辺に沿って細かく移動しながら細線化すると防げますが、処理がやや複雑で実際にはあまり用いられません。
参考資料
この記事は、筆者のホームページ「Visual C++を用いた易しい画像処理（12）－画像処理では比較的実用性が高い、二値画像の細線化を試みる－」」（ただし、現在は Visual C++ 2005 Express Edition 版に改定）をJava言語に書き直し、分かりやすく加筆したものです。
