2011. 1. 19.
2014. 2. 8.  訂正 LOWER_RIGJHT=2 → LOWER_RIGHT=6
石立 喬

Visual C++ 2010 Expressを用いた易しい画像処理(8)

――― 分かり易いアルゴリズムで二値画像を細線化する―――

 画像処理では、平滑化、鮮鋭化、エッジ検出などに次いで、細線化も多く用いられる。文字や物体を認識するには、それらの特徴を抽出する必要があり、太い線や塊では判別し難いからである。

概要
 細線化は、二値画像に対して行われる。二値化された原画像を4方向から順次スキャンし、黒のピクセルを囲む周辺の8個のピクセルを調べて、3種類のパターン条件のうち、少なくとも一つに合致すれば、その中心の黒のピクセルを白に変更して消去する。これを、消去が生じなくなるまで繰り返す。

細線化
 細線化は、ThinningやSkeletonizationと呼ばれ、二値画像を幅1ピクセルの線画像に変換する処理である。原画像に対して、線が短くなったり、線が途中で切れたり、孔が開いたりしてはいけない。得られた線は、元の図形の幅の中心に来ることが望ましい。
 エッジ検出によって得られたエッジ画像は、元の画像の変化が比較的緩やかな所では、幅が広くなる。エッジ検出の閾値を高くすると幅は狭くなるが、より緩やかな変化を検出できない。したがって、エッジ検出処理後に細線化を行って、文字認識やパターン認識に使うことが多い。

細線化のアルゴリズム
 細線化の手法は古くから研究され、種々の方法が知られている。ここでは、筆者による(「Visual C++ 6.0 を用いた易しい画像処理(12)」、2003. 1.18.で発表、以後、改版を重ねる)比較的分かりやすい方法を使用した。細線化の結果として得られた線が元の図形の中心部に来るように、左上→右下、右下→左上、右上→左下、左下→右上の順に周囲から狭めてゆく。消去できるかどうかを判断すべき注目する1(黒)の点を中心に、左右または斜め方向の片方の半分が1(黒)で他方が0(白)の場合は、該当する点を0(白)にすることができる判断する。Hilditchのアルゴリズムに似ている点もあるが、線が途切れる欠点が無く、プログラムが単純化できる。

◎注目するピクセルとその周辺の呼び方
 図1に示すように、消去できるかどうかを調べるピクセルをcenterとし、周囲のピクセルは、反時計回りに、左上から順に、p[0]からp[7]と呼ぶ。center、p[0]〜p[7]は、このプログラムでは、true(黒)またはfalse(白)の値を持つbool型にしてある。ただし、特にcenterと言う変数(オブジェクト)名は、プログラムで使用することはなく、ピクセルデータpixels_old[i,j]に相当する。周囲のピクセルは、配列の添え字を増加させながら選択する。8で割った剰余を採っているので、7の次は0になる。


図1 消去できるかどうかを判定する周辺ピクセルの名称


◎画面左上から右下に向かって探索する場合に使用するパターン
 画面左上から右下に向かって探索する場合には、左上が白(0)に、右下が黒(1)になっている場合を探す。ここでは「0」はfalse、「1」はtrueを表す。下記の3種類があり、いずれの場合も中央のピクセル(丸で囲まれている)を「1」から「0」に変更(消去)できる。XはDon't care(どちらでも良い、したがって判断の対象としない)を示す。


図2 左上から右下に向かって探索する場合に消去できる条件


 この条件を表す式は、左から
    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型の変数に対して否定の演算を行う。
 このような条件式は、添え字を1ずつ増やし(7の次は0)ながらforループで実行できる。上の例の場合には、添え字が2から始まるので、この値をstartと呼んでいる。「1」が3個並んでいる、反時計回りで最初のピクセルの添え字の値がstartであると考えると良い。
 上記の場合は、start=2 であり、プログラムでは、start=UPPRER_LEFT として指定する(UPPER_LEFTは定数2として、別途定義しておく)。

◎画面右下から左上に向かって探索する場合に使用するパターン


図3 右下から左上に向かって探索する場合に消去できる条件


 この条件を表す式は、左から
    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=6)。

◎画面右上から左下に向かって探索する場合に使用するパターン


図4 右上から左下に向かって探索する場合に消去できる条件


 この条件を表す式は、左から
    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)。

◎画面左下から右上に向かって探索する場合に使用するパターン


図5 左下から右上に向かって探索する場合に消去できる条件


 この条件を表す式は、左から
    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()の内容
1)細線化したい二値原画像(WIDTH=320, HEIGHT=240)をファイルから読み込み、Bitmapクラスのbmap_srcとし、パソコン画面左に表示する。
2)細線化を繰り返し実行する対象として、原画像の四辺をそれぞれ1ピクセルずつ拡張したBitmapクラスの拡張画像bmap_exp(WIDTH+2,HEIGHT+2)を用意し、一旦全体を白で描画した後に、中央部に原画像bmap_srcをコピーする。この操作は、原画像の周辺を1ピクセル分だけ拡張し、白で埋めたことに相当する(全体を白で描画する方がプログラム的には簡単なので)。
3)拡張画像bmap_expから、細線化の対象とするbool型のピクセルデータ配列pixels_new[i,j]を求める。
4)細線化処理として、change_flagがfalseのまま(変化がなかった)になるまで、以下を繰り返す。
4A)change_flagをfalseに設定する。
 以下は、左上→右下、右下→左上、右上→左下、左下→右上の順で4回細線化を実行する。
4B)メソッドcopyNewToOld()により、pixels_new[i,j]をpixels_old[i,j]にコピーする。これは、消去したピクセルを直ちに次の判断に使用しないためである。
4C)pixels_old[i,j]をスキャンして、もし対象ピクセルが黒(true)であれば、そのピクセルを消去できるかどうかを判断し、可能であれば消去する細線化メソッドthinImage(i,j,UPPER_LEFT)などを呼び出す。最初はUPPER_LEFTを使用するが、順次、LOWER_RIGHT、UPPER_RIGHT、LOWER_LEFTと指定を変えてゆく。
4D)四方からの細線化が一回終わると、得られたpixels_new[i,j]からbmap_expを作り、画面の右側に描画する。これにより、細線化の途中経過を見ることができる。
5)thinImage(i,j,UPPER_LEFT)など、四方向の細線化をすべて実施してもchange_flagがtrueで返ってこない場合は、それ以上消去するピクセルが無いことを表しているので、細線化の繰り返しを終了する。
6)得られた画像は、拡張されたままなので、拡張画像bmap_expの中心部(周辺を除く)を最終線画化画像bmap_thinにコピーする。
7)最終線画化画像bmap_thinをパソコン画面右に表示する。拡張画像bmap_expよりもサイズが小さいので、一旦、拡張画像bmap_expを背景色で消してから、その上に表示する。

◎メソッドthinImage(i,j,start)の内容
 このメソッドは、指定された場所の黒ピクセルを、条件により白に変更する。引数として、場所と、探索の方向(左上→右下をあらわすUPPER_LEFTなど)が与えられる。
1)指定された場所(i,j)の周辺の8個のピクセルの値を、ピクセルデータ配列pixels_oldから配列pにコピーする。
2)startによって指定された連続した3個のピクセルが黒(true)で、かつcenterに対して点対象の反対側の連続した3個のピクセルが白(false)の場合には、centerすなわち指定された場所(i,j)に対応するpixels_new[i,j]を白(false)に設定して消去し、消去が行われたことを示すchange_flagをtrueに設定する。それ以上調べる必要は無いので、returnで呼び出し元に戻る。

プログラム
 グローバルに下記を設定しておく。
static int WIDTH=320,HEIGHT=240;
static array<bool,2>^ pixels_new=gcnew array<bool,2>(WIDTH+2,HEIGHT+2);    //一回ごとの細線化結果を入れる
static array<bool,2>^ pixels_old=gcnew array<bool,2>(WIDTH+2,HEIGHT+2);     //一回ごとの細線化対象を入れる
bool change_flag;

private: System::Void Form1_Paint(System::Object^ sender, System::Windows::Forms::PaintEventArgs^ e) {

  Graphics^ g=e->Graphics;

  int X0=10,Y0=10;
  int X1=340,Y1=10;

  int UPPER_LEFT=2,LOWER_RIGHT=6,UPPER_RIGHT=0,LOWER_LEFT=4;

  Color color1;
  int i,j;

  Bitmap^ bmap_exp=gcnew Bitmap(WIDTH+2,HEIGHT+2);    //拡張画像
  Bitmap^ bmap_thin=gcnew Bitmap(WIDTH,HEIGHT);      //最終線画化画像

  //原画像を読み込む
  Bitmap^ bmap_src=gcnew Bitmap("sample.PNG");
  //原画像を左に表示する
  g->DrawImage(bmap_src,X0,Y0);

  //拡張画像bmap_expを全部白に設定する
  for(j=0;j<HEIGHT+2;j++)
    for(i=0;i<WIDTH+2;i++)
      bmap_exp->SetPixel(i,j,Color::White);

  //原画像を拡張画像bmap_expの中心にコピーする
  for(j=0;j<HEIGHT;j++)
    for(i=0;i<WIDTH;i++){
      color1=bmap_src->GetPixel(i,j);
      bmap_exp->SetPixel(i+1,j+1,color1);
    }
  //拡張画像bmap_expをピクセルデータ配列pixels_newに変換する
  for(j=0;j<HEIGHT+2;j++)
    for(i=0;i<WIDTH+2;i++){
      color1=bmap_exp->GetPixel(i,j);
      if(color1.R<128) pixels_new[i,j]=true;
      else pixels_new[i,j]=false;
    }

  //細線化を実行する
  do{
    change_flag=false;

    //左上から
    copyNewToOld();
    for(j=1;j<=HEIGHT;j++)
      for(i=1;i<=WIDTH;i++)
        if(pixels_old[i,j]) thinImage(i,j,UPPER_LEFT);
    //右下から
    copyNewToOld();
    for(j=HEIGHT;j>=1;j--)
      for(i=WIDTH;i>=1;i--)
        if(pixels_old[i,j]) thinImage(i,j,LOWER_RIGHT);
    //右上から
    copyNewToOld();
    for(j=1;j<=HEIGHT;j++)
      for(i=WIDTH;i>=1;i--)
        if(pixels_old[i,j]) thinImage(i,j,UPPER_RIGHT);
    //左下から
    copyNewToOld();
    for(j=HEIGHT;j>=1;j--)
      for(i=1;i<=WIDTH;i++)
        if(pixels_old[i,j]) thinImage(i,j,LOWER_LEFT);
    //ピクセルデータpixels_new[i,j]を拡張画像bmap_expに変換する
    for(j=0;j<HEIGHT+2;j++)
      for(i=0;i<WIDTH+2;i++){
        if(pixels_new[i,j]) bmap_exp->SetPixel(i,j,Color::Black);
        else bmap_exp->SetPixel(i,j,Color::White);
      }
    //拡張画像bmap_exp(途中経過)を表示する
    g->DrawImage(bmap_exp,X1-1,Y1-1);
  }while(change_flag);

  //拡張画像bmap_expを最終線画化画像bmap_thinに変換する
  for(j=0;j<HEIGHT;j++)
    for(i=0;i<WIDTH;i++){
      color1=bmap_exp->GetPixel(i+1,j+1);
      bmap_thin->SetPixel(i,j,color1);
    }

  //拡張画像bmap_expのあった部分を背景色で塗りつぶす
  Brush^ brush1=gcnew SolidBrush(BackColor);
  g->FillRectangle(brush1,X1-1,Y1-1,WIDTH+2,HEIGHT+2);
  //最終的細線化画像bmap_thinを右に表示する
  g->DrawImage(bmap_thin,X1,Y1);

}

private: void thinImage(int i,int j,int start){

  array<bool>^ p=gcnew array<bool>(8);
  bool product,sum;

  //周辺のデータをコピーする
  p[0]=pixels_old[i-1,j-1];
  p[1]=pixels_old[i-1,j];
  p[2]=pixels_old[i-1,j+1];
  p[3]=pixels_old[i,j+1];
  p[4]=pixels_old[i+1,j+1];
  p[5]=pixels_old[i+1,j];
  p[6]=pixels_old[i+1,j-1];
  p[7]=pixels_old[i,j-1];

  //周辺の黒(itrue)の三個連続と白(ifalse)の三個連続があれば、そのピクセルを白(ifalse)にする
  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 && !sum){
      pixels_new[i,j]=false;   //消去する
      change_flag=true;      //消去があった
      return;
    }
  }

}

private: void copyNewToOld(void){

  //引き続き細線化を繰り返すために、すでに細線化されたピクセルデータを、細線化対象ピクセルデータにコピーする
  for(int j=0;j<HEIGHT+2;j++)
    for(int i=0;i<WIDTH+2;i++)
      pixels_old[i,j]=pixels_new[i,j];

}


得られた結果
 図6は英文字の場合の例で、左は細線化の前の二値原画像、右は細線化後の画像である。


図6 英文字の細線化例


 図7は図形の場合を示したもので、四方向から追って行くため、円形の図形に対してXの形が現れる。


図7 色々な図形の細線化例


 図8と図9は、「易しい画像処理(7)」で得たエッジ検出結果画像を細線化したもので、2ピクセル以上あったエッジ部分が1ピクセルになっている。自然画像の場合には、細かい部分が強調され過ぎて、原画像のイメージから離れてしまっている。
 図10は、指紋パターンの細線化の例で、細線化の応用分野の一つである。


図8 図形のエッジ検出結果を細線化した場合の例



図9 自然画像のエッジ検出結果を細線化した場合の例



図10 指紋パターンを細線化した場合の例



「Visual C++ の勉強部屋」(目次)へ