第12回 細線化

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


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


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

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

プログラムを実行してしばらく待つとコンソールに「完了」が表示され、実行画面上に元画像を縦横2倍に拡大した画像が表示される。
dataフォルダには8枚の画像が作られる。
そのあとでキーボードの0~8のキーを押すとこれらの画像が画面に表示される。
(すべての画像は自動的に作成されるので、キーボードを使うのは結果確認のためだけ)
キー 画像 意味 特徴
0 元.bmp 元画像
1 1元細線化.png 元画像を細線化したもの 文字の形に太さ1の中心線が残る
2 2ノイズ.png 元画像にノイズを加えたもの
3 2ノイズ細線化.png 2ノイズ.pngを細線化したもの 細線化されるが、黒ノイズの周りがダマになって残る
4 2OC.png 2ノイズ.pngにオープニング・クロージングの処理を順に加えたもの 白黒両方のノイズが消え、白黒エリアの境界は元画像とほぼ同じ
5 2OC細線化.png 2OC.pngを細線化したもの 元画像を細線化したものとほぼ同じ状態になる
6 3元細線化.gif 1元細線化.pngを作る過程のアニメーション 白エリアの端から徐々に削られる過程が見られる
7 3ノイズ細線化.gif 2ノイズ細線化.pngを作る過程のアニメーション 白エリアの端から徐々に削られる過程が見られる
8 3OC細線化.gif 2OC細線化.pngを作る過程のアニメーション 白エリアの端から徐々に削られる過程が見られる
キーと表示される画像

1. 細線化

概要

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

1. 左上から削る
左上から削るときは、「白エリアの左上の端にあるピクセル」「白エリアの上端にあるピクセル」「白エリアの左端にあるピクセル」を黒に変える。
特定のピクセルが白エリアの左上の端にあるかどうかの判定には、このようなマスクを使う。
マスクの数値の0は黒、1は白に対応する。2は「その部分は判定に使用しない」ということを意味する。
つまり、「自分の左上・上・左のピクセルがすべて黒で、右下・下・右のピクセルがすべて白」なら、参照ピクセルが白エリアの左上の端にあると判定する。
0 0 2
0 2 1
2 1 1

同様に、「白エリアの上端にあるかどうか」はこういうマスク、
0 0 0
2 2 2
1 1 1

「白エリアの左端にあるかどうか」はこういうマスクで判定する。
0 2 1
0 2 1
0 2 1

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


×のピクセルが「左上マスク」「上マスク」「左マスク」のどれかに引っかかる。


×のピクセルを黒に変えるとこのようになる。これで左上から1層削ったことになる。

2. 右下から削る
右下から削るときは、以下の3つのマスクを使って調べる。
右下
1 1 2
1 2 0
2 0 0
1 1 1
2 2 2
0 0 0
1 2 0
1 2 0
1 2 0
さっき削った画像のうち、×のピクセルがこれら3つのマスクによるチェックのどれかに引っかかる。


引っかかったものを黒に変える、つまり右下から1層削るとこのようになる。

3. 右上から削る
右上から削るときは、以下の3つのマスクを使って調べる。
右上
2 0 0
1 2 0
1 1 2
0 0 0
2 2 2
1 1 1
1 2 0
1 2 0
1 2 0
さっき削った画像のうち、×のピクセルがこれら3つのマスクによるチェックのどれかに引っかかる。


引っかかったものを黒に変える、つまり右上から1層削るとこのようになる。

4. 左下から削る
左下から削るときは、以下の3つのマスクを使って調べる。
左下
2 1 1
0 2 1
0 0 2
1 1 1
2 2 2
0 0 0
0 2 1
0 2 1
0 2 1
さっき削った画像のうち、×のピクセルがこれら3つのマスクによるチェックのどれかに引っかかる。


引っかかったものを黒に変える、つまり左下から1層削るとこのようになる。

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


それらを黒に変えるとこのようになり、これ以上はどの方向から調べても削れるものはなくなる。
元画像がどのような形でも、最終的には太さ1の白い線になるまで削られる。

プログラムでは、上下左右と斜めの合計8方向の端にいるかどうかの判定に対応するマスクを用意し、削る方向に応じてどのマスクを使うかを決める。
マスクに対応する配列は 上:top、 下:bottom、 左:left、 右:right の t, b, l, r を付けた名前にする。
左上:m_lt 上:m_t 右上:m_rt
0 0 2 0 0 0 2 0 0
0 2 1 2 2 2 1 2 0
2 1 1 1 1 1 1 1 2

左:m_l 右:m_r
0 2 1 1 2 0
0 2 1 1 2 0
0 2 1 1 2 0

左下:m_lb 下:m_b 右下:m_rb
2 1 1 1 1 1 1 1 2
0 2 1 2 2 2 1 2 0
0 0 2 0 0 0 2 0 0
左上から削るときは m_lt, m_t, m_l
右下から削るときは m_rb, m_b, m_r
右上から削るときは m_rt, m_t, m_r
左下から削るときは m_lb, m_b, m_l
を使ってチェックし、3つのマスクのどれかで「端にある」と判定されたらそのピクセルを黒に変える。

課題 1

  1. Processingを起動する。
  2. 以下のコードをコピー&ペーストする。
    int selected = 0; // 選択中の画像番号
    // 画像用の変数
    PImage[] img = new PImage[9];
    // 出力ファイル名
    String[] fName = {"元", "1元細線化", "2ノイズ", "2ノイズ細線化", 
      "2OC", "2OC細線化", "3元細線化", "3ノイズ細線化", "3OC細線化"};
    int w = 400;
    int h = 200;
    
    int [] m_t = {0, 0, 0, 2, 2, 2, 1, 1, 1};  // 上マスク
    int [] m_b = {1, 1, 1, 2, 2, 2, 0, 0, 0};  // 下マスク
    int [] m_l = {0, 2, 1, 0, 2, 1, 0, 2, 1};  // 左マスク
    int [] m_r = {1, 2, 0, 1, 2, 0, 1, 2, 0};  // 右マスク
    int [] m_lt = {0, 0, 2, 0, 2, 1, 2, 1, 1}; // 左上マスク
    int [] m_rt = {2, 0, 0, 1, 2, 0, 1, 1, 2}; // 右上マスク
    int [] m_lb = {2, 1, 1, 0, 2, 1, 0, 0, 2}; // 左下マスク
    int [] m_rb = {1, 1, 2, 1, 2, 0, 2, 0, 0}; // 右下マスク
    
    void setup() {
      size(800, 400);
      noSmooth();
      boolean isRightSize = true;
      boolean isBW = true;
      img[0] = loadImage("元.bmp");
      // サイズ判定
      if (img[0].width != w || img[0].height != h) {
        isRightSize = false;
      }
      // 白黒判定
      for (int j=0; j<h; j++) {
        for (int i=0; i<w; i++) {
          if (img[0].pixels[i+j*w]!=color(0) && img[0].pixels[i+j*w]!=color(255)) {
            isBW = false;
          }
        }
      }
      if (!isRightSize || !isBW) {
        println("サイズが違うか、白黒画像ではありません");
        exit();
      } else {
        // img[0]を細線化した画像をimg[1]に保存
        // img[0]にノイズを追加した画像をimg[2]に保存
        // img[2]を細線化した画像をimg[3]に保存
        // img[2]にオープニング→クロージングの処理を加えた画像をimg[4]に保存
        // img[4]を細線化した画像をimg[5]に保存
        println("完了");
        textFont(createFont("MS Pゴシック", 48));
        background(0);
        image(img[0], 0, 0, width, height);
      }
    }
    
    void draw() {
      background(0);
      // gif画像でなければ普通に表示
      if (selected <= 5) {
        image(img[selected], 0, 0, width, height);
      }
      // gif画像ならkeyPressedで設定した動画を表示
      else {
      }
      fill(255, 0, 0);
      text(fName[selected], 30, height-30);
      fill(255);
    }
    
    // ノイズ追加
    void addNoise(int n) {
      // n番を元画像と同じ画像にする
      img[n] = img[0].get();
      // 画素数の1/100回の繰り返し
      for (int i=0; i<w*h/100; i++) {
        // 0~w*h-1の範囲の乱数をint rに入れる
        int r = int(random(w*h));
        // n番目の画像のr番目のピクセルの明度をfloat bに入れる
        float b = brightness(img[n].pixels[r]);
        // n番目の画像のr番目のピクセルに明度255-bの色を設定する
        img[n].pixels[r] = color(255-b);
      }
      img[n].save("data/"+ fName[n] +".png");
    }
    
    // オープニング&クロージング
    void openClose(int a, int n) {
      img[n] = img[a].get();
      img[n].save("data/"+ fName[n] +".png");
    }
    
    // 画像aを画像nにコピーして細線化する
    void thinning(int a, int n) {
      img[n] = img[a].get();
      image(img[n], 0, 0, width, height);
      while (true) {
        int count=0;
        count += cutLayer(n, 0);
        count += cutLayer(n, 1);
        count += cutLayer(n, 2);
        count += cutLayer(n, 3);
        if (count == 0) {
          break;
        }
      }
      img[n].save("data/"+ fName[n] +".png");
      img[n].updatePixels();
    }
    
    // 指定された方向(dirが0~3なら左上,右下,右上,左下)から1層削る
    // 削った数を戻り値として返す
    int cutLayer(int n, int dir) {
      PImage temp = img[n].get(); // n番の画像を仮変数tempにコピー
      int dCount = 0; // 削ったピクセル数
      int[][] mask = new int[3][9];
      switch(dir) {
      case 0: // 左上から削る場合
        mask[0] = m_lt;
        mask[1] = m_t;
        mask[2] = m_l;
        break;
      case 1: // 右下から削る場合
        mask[0] = m_rb;
        mask[1] = m_b;
        mask[2] = m_r;
        break;
      case 2: // 右上から削る場合
        mask[0] = m_rt;
        mask[1] = m_t;
        mask[2] = m_r;
        break;
      case 3: // 左下から削る場合
        mask[0] = m_lb;
        mask[1] = m_b;
        mask[2] = m_l;
        break;
      }
      for (int j=1; j<h-1; j++) {
        for (int i=1; i<w-1; i++) {
          boolean hit = false; // マスクのどれかに一致したかどうかのフラグ
          // 3種類のマスクについての繰り返し
          for (int k=0; k<3; k++) {
            int count = 0; // マスクとの一致数カウント
            for (int l=0; l<9; l++) {
              // int x にマスク内横位置(-1~1)を入れる
              // int y にマスク内縦位置(-1~1)を入れる
              // tempの(i+x, j+y)のピクセルの明度をbに入れる
              // k番目のマスクのl番目の位置の値×255がbと一致していたらcountを増やす
            }
            // 6箇所がすべて一致していたらフラグをtrueにする
    
          }
          if (hit) {
            // 画像nの(i, j)のピクセルを黒にする
            // もともとそこが白だった場合はdCountを増やす
          }
        }
      }
      image(img[n], 0, 0, width, height);
      return dCount;
    }
    
    void keyPressed() {
      int k = key-'0';
      if (k>=0 && k<=8) {
        selected = k;
        if (k >= 6) {
        }
      }
    }
    
  3. 「img12」という名前で保存する。
  4. サイズ400x200ピクセルのモノクロビットマップの文字画像を作成する。
    • 背景は黒、文字の色は白にする
    • 左側に手書きの文字、右側に「テキスト」の機能による同じ文字を入れる

  5. 「元.bmp」をProcessingのエディタにドラッグ&ドロップする。
  6. cutLayer関数の以下のコメント文のところに対応するコードを追加する。
              // int x にマスク内横位置(-1~1)を入れる
              // int y にマスク内縦位置(-1~1)を入れる
              // tempの(i+x, j+y)のピクセルの明度をbに入れる
              // k番目のマスクのl番目の位置の値×255がbと一致していたらcountを増やす
    • 概要のように3x3の形で並べた場合の横位置・縦位置 (0~2) はそれぞれ「l%3」「l/3」で得られる。
    • それらから1を引けば中心を(0, 0)とした横・縦のずれ (-1~1) が得られる。

  7. cutLayer関数の以下のコメント文のところに対応するコードを追加する。
            // 6箇所がすべて一致していたらフラグをtrueにする

  8. cutLayer関数の以下のコメント文のところに対応するコードを追加する。
            // 画像nの(i, j)のピクセルを黒にする
            // もともとそこが白だった場合はdCountを増やす
    • 「黒」は「color(0)」で得られる。
    • img[n]は処理が進むにつれて変化するので、もとの色はtempから取得する。

  9. setup関数の「// img[0]を細線化した画像をimg[1]に保存」の左に必要なコードを追加する。
    • 呼ぶのはthinning関数。
    • 2つの引数には細線化前、細線化後の画像の番号を入れる。

  10. プログラムを実行する。
    • コンソールに「完了」が表示されてから0キー, 1キーを押すと、元画像とそれを細線化した画像が表示される。


2. ノイズ画像とノイズを除去した画像の細線化

概要

課題1の結果からわかるように、多少文字の書体や大きさが違っても細線化すれば分岐のしかたが基本的に同じになるので、それを文字の判定の基準として使うことができる。
しかし、もしノイズがあった場合は、黒いノイズを囲むように白い線ができてしまうため、本来の分岐とは違う状態になってしまう。




そこで、例えば前回の「オープニング→クロージング」のような処理を事前に行えば白・黒のノイズを消せるので、元画像を細線化した場合とほぼ同じように分岐する画像が得られる。

課題 2

  1. setup関数の
        // img[0]にノイズを追加した画像をimg[2]に保存
        // img[2]を細線化した画像をimg[3]に保存
    の左に、それぞれに対応したコードを追加する。
    • ノイズを追加するのはaddNoise関数。引数は追加後の画像の番号。

  2. プログラムを実行する。
    • コンソールに「完了」が表示されてから2キーを押すと、元画像にノイズを加えた画像が表示される。
    • 3キーを押すと、ノイズ画像を細線化した画像が表示される。

  3. openClose関数の「img[n] = img[a].get();」の下に、img[n]に対してオープニング、クロージングの処理を順に加えるコードを追加する。
    • オープニングは収縮・膨張、クロージングは膨張・収縮の順に処理を行うことにあたる。
    • それぞれの処理はfilter関数にERODEまたはDILATEを引数として与えて行う。

  4. setup関数の
        // img[2]にオープニング→クロージングの処理を加えた画像をimg[4]に保存
        // img[4]を細線化した画像をimg[5]に保存
    の左に、それぞれに対応したコードを追加する。

  5. プログラムを実行する。
    • コンソールに「完了」が表示されてから4キーを押すと、ノイズ画像にオープニング&クロージングの処理を加えた画像が表示される。
    • 5キーを押すと、その画像を細線化した画像が表示される。

3. 細線化の過程の動画作成

概要

課題1, 課題2では3つの画像の細線化を行ったが、ここでは順に1層ずつ削っていく過程を見られるように、gifアニメーションの動画を作成する。
これを行うために、Processingに「gifAnimation」というライブラリを導入する。

課題 3

  1. プログラム先頭に以下のコードを追記する。
    import gifAnimation.*;
    GifMaker gifMaker; // gifアニメーションを作るための変数
    Gif gif; // gifアニメーションを再生するための変数
    これらの行にエラーが出る場合は、以下のようにしてライブラリ「gifAnimation」をインポートする (これが完了すればエラーが消える)。
    • 「スケッチ」→「ライブラリをインポート」→「Manage Libraries」を選ぶ
    • 検索欄に「gif」と入力する
    • 検索に引っかかったものを選び、「Install」をクリックする

  2. draw関数の「else {」の下に以下のコードを追加する。
    (動画の表示は静止画とは異なり、Gif型の変数を経由する必要があるため)
          image(gif, 0, 0, width, height);

  3. thinning関数の前のコメント文と関数の初めの部分を以下のように変更する。
    (機能追加に応じた説明の追加と、動画ファイル番号指定のための引数追加)
    // 画像aを画像nにコピーして細線化する
    void thinning(int a, int n) {
    // 画像aを画像nにコピーして細線化し、その過程の動画を画像mに保存する
    void thinning(int a, int n, int m) {

  4. thinning関数の「img[n] = img[a].get();」の
    上に
      gifMaker = new GifMaker(this, "data/"+ fName[m] +".gif");
      gifMaker.setRepeat(0);
      gifMaker.setDelay(30);
    を、下に
      gifMaker.addFrame(img[n]);
    を追加する。
    (上に追加した方が動画作成の初期設定で、出力ファイル名指定、ループ再生の設定、1フレームあたりの時間(ミリ秒)を決めている)
    (下に追加したコードは動画にフレームを追加する命令。ここでは変換前の画像をそのまま入れている)

  5. thinning関数の最後に以下のコードを追加する。
    (gif画像の保存を完了させる命令)
      gifMaker.finish();

  6. cutLayer関数の最後の「return dCount;」の上に以下のコードを追加する。
    (これも動画にフレームを追加する命令。ここではその段階での (削っている途中での) n番目の画像を入れている)
      gifMaker.addFrame(img[n]);

  7. setup関数のthinning関数を呼んでいる3行 (エラーになっている) にそれぞれ第3引数を追加する。
    (第3引数は出力するgif動画の画像番号。上から順に6, 7, 8番)
    (これを追加すればエラーがなくなる)

  8. keyPressed関数の「if (k >= 6) {」の下に以下のコードを追加する。
    (1行目が動画を表示用の変数「gif」に読み込む命令で、その次が動画をループ再生させる命令)
          gif = new Gif(this, fName[k] +".gif");
          gif.loop();

  9. プログラムを実行し、画面をクリックする。コンソールに「完了」が表示されてからキーを押してできた画像を確認する。
    • 6キーを押すと、元画像を細線化する過程の動画が表示される。
    • 7キーを押すと、ノイズ画像を細線化する過程の動画が表示される。
    • 8キーを押すと、ノイズ画像にオープニング・クロージング処理を加えた画像を細線化する過程の動画が表示される。

提出

提出先フォーム (締切:7/9(火))

※ コードはTeamsのClass Notebookに保存してください。
※ このフォームから課題を提出すれば出席がつきます。ただし、あまりにも進捗が少ない場合は提出としてカウントされません。
※ 締切後はこちらから提出してください (通常と同様に点数がつきますが、出席はつきません)。
戻る