Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

パターン認識の前処理に必要な二値画像の細線化

プログラミングが容易で理解しやすい細線化アルゴリズムの実装

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2005/06/22 12:00

細線化とは、二値画像を幅1ピクセルの線画像に変換する処理のことで、画像処理の中では比較的利用頻度の高いものです。特に、文字認識やパターン認識の前処理として多く使われます。

はじめに

 細線化は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になります。

図1 消去の可否を調べるピクセルと周辺のピクセルの呼び方
図1 消去の可否を調べるピクセルと周辺のピクセルの呼び方

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

 画面左上から右下に向かって探索する場合には、左上が「白(0)」に、右下が「黒(1)」になっている場合を探します。この条件は、下記のような3種類の状態があります。いずれの場合も、中央のピクセル(丸で囲まれている)を「1」から「0」に変更(消去)することができます。「X」はDon't care(「1」または「0」のどちらでも良い)を示します。

図2 左上からの探索で消去できる条件
図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

 です。

 このような条件式は、添え字を1ずつ増やし(7の次は0)ながらforループで実行できます。上の場合には、添え字が2から始まるので、この値をstartと呼んでいます。「1」が3個並んでいる、最初の場所がstartであると考えるとわかりやすいと思います。start=2とは、左上から右下に向かって探索することを意味します。実際には、UPPER_LEFT=2と定義して、2の代わりにUPPER_LEFTを使っています。

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

 画面右下から左上に向かって探索する場合には、右下が「白(0)」に、左上が「黒(1)」になっている場合を探します。この条件は、下記のような3種類の状態があります。

図3 右下からの探索で消去できる条件
図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 = 6 (LOWER_RIGHT)です。

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

 画面右上から左下に向かって探索する場合には、右上0が「白(0)」に、左下が「黒(1)」になっている場合を探します。この条件は、下記のような3種類の状態があります。

図4 右上からの探索で消去できる条件
図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 = 0 (UPPER_RIGHT)です。

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

 画面左下から右上に向かって探索する場合には、左下が「白(0)」に、右上が「黒(1)」になっている場合を探します。この条件は、下記のような3種類の状態があります。

図5 左下からの探索で消去できる条件
図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 = 4 (LOWER_LEFT)です。

プログラムの概要

 このプログラムは次の部分から成っています。なお、簡単化するために、使用する画像のサイズを、あらかじめ320 x 240に固定してあります。一般化するには、若干のコードを追加する必要があります。このプログラムで、もっとも頻繁に用いられるのはthinImageメソッドです。この中では、CPUのキャッシュを有効に活用できませんので、old_pixels[i][j]の代わりにold_pixels[j][i]を用いるなどの特別な配慮はしていません。

準備段階

  1. メソッドreadImageFileを使用して、細線化したい原画像を、画像img_srcとして読み込みます。
  2. メソッドcreate2DBinaryExpandedを使用して、img_srcを一次元カラーデータrgb[]に変換し、原画像の周辺を上下左右1ピクセルずつ拡張した二次元二値データnew_pixels[][]の中央部に二値データとして書き込みます。この様子は、図6に示します。すなわち、原画像は一次元データrgb[]として、図の上部のように並んでいます。拡張した図形は、図の下部に示してあり、ここでは、二次元二値データnew_pixels[][]で表してあります。
  3. これより、rgb[(j-1)*WIDTH+(i-1)]new_pixels[i][j]に代入すればよいことが分かります。ここで、ijは、拡張後の画像のものを使っていますので、拡張前の画像を参照するためには、i-1j-1のように1を減じる必要があります。
図6 原画像と拡張画像の関係
図6 原画像と拡張画像の関係

実行段階

 図7に示すように、細線化プログラムの実行部分は下記のようになっています。

  1. 細線化の前の拡張画像img_expを画面左側に描画します(図7では省略)。
  2. dowhileループ内では、変化があった(すなわち、「黒」のピクセルを「白」に置き換えた)ことを示すフラグ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]でアップデートします。

図7 細線化プログラムの主要部分
図7 細線化プログラムの主要部分

プログラム

プログラム
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の能力にも依りますが、右側の画像は、時間と共に徐々に細線化されて行きます。円は、細線化すると一個の点になるべきですが、四方向から細線化して行く特徴が出て、「×」になっています。

図8 細線化前の画像と細線化後の画像
図8 細線化前の画像と細線化後の画像

まとめ

 画像の細線化は、画像処理の中では、比較的利用度の高いものです。細線化の前処理として、画像の拡張を実施していますが、これも重要なテクニックです。細線化は、注目するピクセルの周辺のピクセルをプログラム上で回転させるという、シンプルで面白い方法を提案しました。円を細線化すると「×」になるのは、黒画像の周辺に沿って細かく移動しながら細線化すると防げますが、処理がやや複雑で実際にはあまり用いられません。

参考資料

 この記事は、筆者のホームページ「Visual C++を用いた易しい画像処理(12)-画像処理では比較的実用性が高い、二値画像の細線化を試みる-」」(ただし、現在は Visual C++ 2005 Express Edition 版に改定)をJava言語に書き直し、分かりやすく加筆したものです。



  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2008/03/16 11:06 参考資料をVisual C++ 2005 Express Edition版に訂正

  • 2007/03/23 13:29 「Hilditchのアルゴリズム」のリンク先がリンク切れになったため、リンクを中止

  • 2007/03/23 13:29 「Hilditchのアルゴリズム」のリンク先がリンク切れになったため、リンクを中止

著者プロフィール

  • 石立 喬(イシダテ タカシ)

    1955年東京工大卒。同年、NECへ入社し、NEC初のコンピュータの開発に参画。磁気メモリ、半導体メモリの開発、LSI設計などを経て、1989年帝京大学理工学部教授。情報、通信、電子関係の教育を担当。2002年定年により退職し現在に至る。2000年より、Webサイト「Visual C++の勉強部屋」...

バックナンバー

連載:Javaで学ぶグラフィックス処理

もっと読む

All contents copyright © 2005-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5