第12回 細線化

OCRソフトでの文字認識や指紋の判別などでは、対象画像との直接的な一致の度合いよりも、構造が同じかどうかを調べて判定する手法が使われる。そのためには、元画像の特定のエリアを単純な線にまで細くして、線の構造を見る必要がある。この処理のことを細線化という。
例えば、下の図のような文字の画像があった場合、5つの「A」の文字は大きさや傾き、フォント、向きなどが異なるので、これらが同じかどうかをピクセルの一致度などで判定するのは難しい。


そこで、この画像の白いエリアを周辺から1ピクセルずつ削っていく処理を最後の線だけになるまで行うと、図のような画像が得られる。


残った線の構造に注目すると、どれも図の5箇所に分岐があり、線のつながり方は右図のようになっていることがわかる (さらに先端が枝分かれしているものもあるが)。ほかの文字もそれぞれこのように枝分かれなどの固有の情報を持つので、これらが一致しているかどうかを調べれば、画像の大小や傾き、歪みなどによらずにかなりの精度で文字を判定することができる。指紋も人によって枝分かれのしかたが異なるので、このような情報を取り出して比較すれば形の歪みや大きさの影響を受けずに判定できる。

今回のプログラムの最終的な機能

プログラムを実行すると実行画面の左側に元画像をネガ・ポジ反転して二値化したものが表示される。
さらに実行画面上でクリックすると、dataフォルダに の4つの画像が作られる。
コンソールに「完了」が表示されてからキーボードの0~4のキーを押すとこれらの画像が画面に表示される。
(「2細線化.png」では、左側はほぼ元の線の骨格にあたる太さ1の線が取り出されるが、右側は文字の中にダマができてきれいな線にならない)
(「3ノイズ消し.png」では右側のノイズはほぼ消えるが、左右どちらも小さい字のものは途切れたりつぶれたりする)
(「2細線化.png」では右側の大きい文字はほぼ左側と同じ状態になるが、左右どちらも小さい字のものは断片的な線になる)

1反転+ノイズ.png (1キーで表示)


2細線化.png (2キーで表示)


3ノイズ消し.png (3キーで表示)


3細線化.png (4キーで表示)

ノイズ追加

概要

やることは基本的に第10回の「収縮・膨張」のときと同じ。ただし、今回は縦でなく横に画像を並べるので、そのときの関数を再利用し、事情に合わせて変更を加える。

課題 1

ベースのプログラム (クリックしても400x200サイズの黒い画像が4つ作られるだけ)
// 出力用画像の変数
PImage[] img = new PImage[5];
// 出力ファイル名
String[] fName = {"1反転+ノイズ", "2細線化", "3ノイズ消し", "3細線化"};
int w, h;

void setup() {
  size(800, 400);
  img[0] = loadImage("元.png");
  img[0].filter(THRESHOLD); // 二値化
  img[0].filter(INVERT);    // ネガ・ポジ反転
  w = img[0].width;
  h = img[0].height;
  if (w!= 200 || h!=200) {
    println("サイズが違います");
    exit();
  }
  noSmooth();
  background(0);
  image(img[0], 0, 0, width/2, height);
}

void draw() {
}

// ノイズ追加 (課題1で変更を加える)
void addNoise() {
  for (int i=1; i<img.length; i++) {
    img[i] = createImage(w*2, h, ARGB);
  }
}

// n番目の画像を細線化する
void thining(int n) {
  // 4方向から削り、削れるものがなくなるまで繰り返す
  while (true) {
    int count=0;
    count += removeLayer(n, 0); // 左上から削り、削ったピクセル数をcountに加える
    count += removeLayer(n, 1); // 右下から削り、削ったピクセル数をcountに加える
    count += removeLayer(n, 2); // 右上から削り、削ったピクセル数をcountに加える
    count += removeLayer(n, 3); // 左下から削り、削ったピクセル数をcountに加える
    if (count==0) {
      break;
    }
  }
}

// 指定された方向から1層分削り、削ったピクセル数を返す
// dirの値と方向の対応(0:左上, 1:右下, 2:右上, 3:左下)
// 課題2で変更を加える
int removeLayer(int n, int dir) {
  int cNum = 0; // 削ったピクセル数
  int [][] mask = {
    {0, 0, 2, 0, 2, 1, 2, 1, 1}, // 左上マスク
    {2, 2, 2, 2, 2, 2, 2, 2, 2}, // 上マスク
    {2, 2, 2, 2, 2, 2, 2, 2, 2}, // 右上マスク
    {2, 2, 2, 2, 2, 2, 2, 2, 2}, // 左マスク
    {}, // 欠番
    {2, 2, 2, 2, 2, 2, 2, 2, 2}, // 右マスク
    {2, 2, 2, 2, 2, 2, 2, 2, 2}, // 左下マスク
    {2, 2, 2, 2, 2, 2, 2, 2, 2}, // 下マスク
    {2, 2, 2, 2, 2, 2, 2, 2, 2}  // 右下マスク
  };
  // マスクの組み合わせの種類
  int [][] mTypes = {
    {0, 1, 3}, // 左上から削るときのマスクの組み合わせ
    {7, 8, 5}, // 右下から削るときのマスクの組み合わせ
    {1, 2, 5}, // 右上から削るときのマスクの組み合わせ
    {6, 7, 3}  // 左下から削るときのマスクの組み合わせ
  };
  // 出力画像の白、黒を1, 0に対応させた整数配列
  int [][] b = new int[w*2][h];
  for (int j=0; j<h; j++) {
    for (int i=0; i<w*2; i++) {
      b[i][j] = (int)brightness(img[n].pixels[i+j*w*2])/255;
    }
  }
  for (int j=1; j<h-1; j++) {
    for (int i=1; i<w*2-1; i++) {
      boolean hit = false; // マスクの白黒と一致したかどうか
      // 3つのマスクについて白黒の一致を調べる
      for (int m=0; m<3; m++) {
        int c = 0; // マスクとの一致回数
        for (int l=-1; l<=1; l++) {
          for (int k=-1; k<=1; k++) {
            // マスクの白黒とチェック位置の値が一致したらカウントする
            if (b[i+k][j+l] == mask[mTypes[dir][m]][k+1+(l+1)*3]) {
              c++;
              if (c==6) {
                hit = true;
              }
            }
          }
        }
      }
      // 3つのマスクの条件のうち1つでも満たしたらそこを黒に変える
      if (hit) {
        // 元はそこが白だった場合は変化数カウントを1増やす
        if (b[i][j]==1) {
          cNum++;
        }
        img[n].pixels[i+j*w*2] = color(0);
      }
    }
  }
  return cNum;
}

// 画像nに1段階の収膨膨収の処理を行う
// 課題3で変更を加える
void edde(int n) {
}

// フィルタ処理を実行
void mousePressed() {
  addNoise();
  thining(2);
  edde(3);
  edde(4);
  thining(4);
  for (int i=1; i<=fName.length; i++) {
    img[i].save("data/" + fName[i-1] + ".png");
  }
  println("完了");
}

// 押したキーに応じて対応する画像を表示
void keyPressed() {
  int k = key-'0';
  if (k>=0 && k<5) {
    background(0);
    if (k==0) {
      image(img[k], 0, 0, width/2, height);
    } else {
      image(img[k], 0, 0, width, height);
    }
  }
}
  1. Processingのエディタに上のサンプルプログラムのコードをコピー&ペーストする。
  2. 「img12」という名前で保存する。
  3. ペイント3Dで以下のような文字画像「元.png」を作る。
    • 画像サイズは200x200
    • 「48ポイントの太字」「48ポイントの細字」「24ポイントの太字」「24ポイントの細字」で同じひらがなを入れる


  4. 「元.png」をProcessingのエディタにドラッグ&ドロップする。
  5. addNoise関数の中の3行のコードを削除する。
  6. addNoise関数の中に第10回 (先々週) のプログラムのaddNoise関数のコードをコピー&ペーストする。
  7. (この時点でaddNoise関数はこうなるはず)
    (手入力はしないこと。先々週の分がOKになっていない場合は先にそちらを完成させる)


  8. コメント文「// 元画像を画像1にコピー」のすぐ下の行のコードの w を w*2 に、h*2 を h に変更する。
  9. (今回は画像を縦ではなく横に並べて作るため)

  10. コメント文「// 上半分には元画像のピクセルをそのままコピー」を「// 左半分には元画像のピクセルをそのままコピー」に変更する。
  11. 変更したコメント文のすぐ下の行のコードの左辺の w を w*2 に変更する。
  12. (変えるのは左辺だけ。img[1]の横幅は w*2 だが、img[0] の横幅は w なので)

  13. コメント文「// 下半分には元画像のピクセルの明度を反転してコピー」を「// 右半分にも元画像のピクセルをそのままコピー」に変更する。
  14. 変更したコメント文のすぐ下の行のコードの左辺を「img[1].pixels[i+w+j*w*2]」に変更し、右辺を消してそこに2行上のコードの右辺をコピー&ペーストする。
  15. (左辺のpixelsの[]の値に対応する座標は(i+w, j)。つまり、元画像の(i, j)のピクセルを w (元画像の幅) だけ右にずらした位置)

  16. コメント文「// 画像内の位置をランダムに決める」の下の2行のrandom関数の引数をそれぞれ 「w, w*2」と「h」に変更する。
  17. (これで x の範囲は w~2w-1, y の範囲は 0~h-1 になる)

  18. コメント文「// x, yのピクセルの明度を反転させる」のすぐ下の行の w を w*2 に変更する (左辺と右辺両方)。
  19. (左辺・右辺どちらも幅 2w の img[1] を対象としているため)

  20. コメント文「// 収縮・膨張用の画像をこれと同じにする」を「// 画像2~4をこれと同じにする」に変更する。
  21. 変更したコメント文のすぐ下の行のコードの「i<=5」を「i<=4」に変更する。

  22. 実行して画面をクリックする。
  23. (「完了」が表示されたあとでキーボードの1キーを押すと、左半分はそのままで、右半分はそれにノイズが入った状態になる)
    (この結果にならない場合はそのまま次に進まないこと。この画像を元に細線化などの処理を行う)
  • この段階でdataフォルダの出力画像「1ノイズ.png」だけが本来の状態になっている。
  • うまくいかない場合は、最終的なaddNoise関数とコードを見比べる。

細線化

概要

このページの先頭の説明では「白いエリアを周辺から1ピクセルずつ削っていく」としたが、具体的な処理の手順としては
  1. 白いエリアの左上から1層削る
  2. 白いエリアの右下から1層削る
  3. 白いエリアの右上から1層削る
  4. 白いエリアの左下から1層削る
という工程を、削るものがなくなるまで繰り返す。

1. 左上から削る
あるピクセルが左上から削れるかどうかは、以下の3つのマスクを使って調べる。
左上チェックマスク
上チェックマスク
左チェックマスク

それぞれのマスクは、「自分を中心として、黒マスのピクセルが全て黒で、白マスのピクセルがすべて白なら」という意味 (灰色のマスは白黒どちらでもよい)。
例えば左上チェックマスクなら、「自分の左上、上、左の3つがすべて黒で、自分の右下、下、右がすべて白なら」ということになる。この条件は要するに、「そのピクセルが白エリアの左上側の端だったら」にあたる。つまり、左上から削るときは「白エリアの左上端」「白エリアの上端」「白エリアの左端」にあるピクセルを削る。

これらのマスクを使ってこのような画像を調べると、


×のピクセルが3つの条件のどれかに引っかかる。


×のピクセルを黒に変えるとこのようになる。

2. 右下から削る
右下から削るときは、以下の3つのマスクを使って調べる。
右下チェックマスク
下チェックマスク
右チェックマスク

さっき削った画像をこれらのマスクで調べると、×のピクセルが引っかかる。


引っかかったものを黒に変えるとこのようになる。

3. 右上から削る
右上から削るときは、以下の3つのマスクを使って調べる。
右上チェックマスク
上チェックマスク
右チェックマスク

さっき削った画像をこれらのマスクで調べると、×のピクセルが引っかかる。


引っかかったものを黒に変えるとこのようになる。

4. 左下から削る
左下から削るときは、以下の3つのマスクを使って調べる。
左下チェックマスク
下チェックマスク
左チェックマスク

さっき削った画像をこれらのマスクで調べると、×のピクセルが引っかかる。


引っかかったものを黒に変えるとこのようになる。

この例だと、さらに1に戻って左上から調べると×のピクセルが引っかかる。


それらを黒に変えるとこのようになり、これ以上はどの方向から調べても削れるものはなくなる。

プログラムでは、これらのマスクの黒、白、灰色のマスに0, 1, 2の値を割り当てて、2重配列 mask で扱う。
たとえば「左チェックマスクの右上のマス」はmask[3][2]で、その値は1になる。
(ベースのプログラムでは、mask[0]に対応する部分のみ本来の値を入れてある)
mask[0]mask[1]mask[2]

mask[3]mask[5]

mask[6]mask[7]mask[8]

左上から削るときは mask[0], mask[1], mask[3]
右下から削るときは mask[7], mask[8], mask[5]
右上から削るときは mask[1], mask[2], mask[5]
左下から削るときは mask[6], mask[7], mask[3]
を使ってチェックすることになる。

課題 2

  1. 「概要」を参考にして removeLayer 関数の mask に正しい値を入れる。
  2. (図の黒が0, 白が1, 灰色が2に対応する)

  3. 実行し、画面をクリックしてコンソールに「完了」が表示されたあとでキーボードの1, 2キーを交互に押す。
  4. (2キーで表示されるのが細線化の結果)
    (左側は文字の骨格の線が取り出される)
    (右側には黒ノイズを取り囲む形のダマができる。また、白ノイズはそのまま残る)


  5. この段階でdataフォルダの出力画像のうち「2細線化.png」も然るべきものになる。
  6. うまくいかない場合は、最終的なremoveLayer関数の maskの部分とコードを見比べる。

収膨膨収による前処理との組み合わせ

概要

前回の結果から、収膨膨収、膨収収膨のどちらも白黒どちらのノイズもほとんど消せるが、黒背景に白の文字の場合は膨収収膨だと白ノイズの塊が残ることがわかったので、ここではノイズ画像に収膨膨収の処理を加えて、それに細線化の処理を行ってみる。

↓ 収膨膨収

↓ 細線化

課題 3

  1. edde()関数の中に、「img[n].filter(ERODE);を1回、img[n].filter(DILATE);を2回、img[n].filter(ERODE);を1回」を順に行う処理を記述する。
  2. (今回は回数は固定なので、for文は使っても使わなくても構わない)

  3. 実行し、画面をクリックしてコンソールに「完了」が表示されたあとでキーボードの1, 2, 3, 4キーを順に押す。
  4. (3キーで表示される収膨膨収の結果では、右側のノイズはほぼ消えてノイズ追加前の状態に近くなるが、小さい文字はつぶれたり途切れたりする)
    (4キーで表示される細線化の結果では、大きい文字は左右が近い状態になるが、小さい方は途切れがちになる)


  5. この段階でdataフォルダの出力画像のうち「3ノイズ消し.png」「3細線化.png」も然るべきものになる。
  6. うまくいかない場合は、最終的なedde関数とコードを見比べる。

提出

小テスト予告

次回の授業の初めに今回の内容についての小テストを行う。

戻る

inserted by FC2 system