第13回 データ圧縮

画像ファイルの形式にはビットマップ形式(拡張子「bmp」)、JPEG形式(拡張子「jpg」または「jpeg」)、PNG形式(拡張子「png」)などがある。このうち、ビットマップ形式ではピクセルごとのデータを圧縮せずにそのまま保存しているが、JPEG形式やPNG形式では固有のアルゴリズムでデータを圧縮し、ファイルサイズを小さくしている。JPEG形式の圧縮は非可逆圧縮であり、元の画像の情報がいくらか失われる。一方、PNG形式の圧縮は可逆圧縮で、すべてのピクセルの色情報が完全に保存される。いずれもそれなりに複雑な処理になるので、今回はこれらとは別に圧縮の基本的な方法を2つ紹介する。

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

プログラムを実行すると実行画面に3つの元画像 (を二値化したもの) が並んで表示される。
さらに実行画面上でクリックすると、dataフォルダに が作られる。
「完了」が表示されたあとで0~3キーを押すと、元画像、復元された画像が表示される (左上の赤文字は確認用)。正しく復元できていればこれらはすべて同じになる。
また、コンソールにそれぞれの画像から作られたデータのサイズ、非圧縮の場合を基準とした圧縮率が表示される。

無圧縮のデータ化

概要

二値化された画像では、どのピクセルも黒か白のどちらかになる。これを0, 1に置き換えれば




のようになり、データサイズは(幅)×(高さ)ビット、つまり(幅)×(高さ)/8 バイトになる。
この方法ではデータサイズは画像の大きさだけに依存し、画像の中の絵や文字がどのような形であっても変わらない。

Processingでは、あらかじめbyte型の変数の配列にデータを格納しておいて、以下の命令を実行すればファイルにデータを保存できる。
saveBytes(ファイルのパス, 配列名);

逆に、以下の命令でデータを配列に読み込める。
byte[] 配列名 = loadBytes(ファイルのパス);

無圧縮の場合は画像のサイズだけでデータ配列の要素数が決まるので最初から配列を宣言して書き込んでもよいが、画像によって要素数が変わる課題2, 3と処理を共用するため、要素数が可変な ArrayList にいったんデータを書き込み、その要素数に合わせた配列を作ってデータをコピーするという手順を踏む。

課題 1

ベースのプログラム (クリックしても空っぽのデータファイルと黒い画像が作られるだけ)
// 出力用画像の変数
PImage[][] img = new PImage[4][3];

String[] tName ={"元", "無圧縮", "非等長", "ランレングス"};

// 非等長符号での 00, 01, 10, 11の置き換え先の並び
String[] code = {"000", "001", "01", "1"};
// 逆の置き換え先
String[] bt = {"00", "01", "10", "11"};

int w, h;
int type=0;   // 画面に表示する画像(0:元, 1:無圧縮, 2:非等長, 3:ランレングス)

void setup() {
  size(750, 250);
  noSmooth();
  for (int i=0; i<3; i++) {
    img[0][i] = loadImage("元" + char(int('A')+i) + ".png");
    img[0][i].filter(THRESHOLD, 0.8);
    w = img[0][i].width;
    h = img[0][i].height;
    if (w!=250 || h!=250) {
      println("サイズが違います");
      exit();
    }
    for (int j=1; j<4; j++) {
      img[j][i] = createImage(w, h, ARGB);
    }
  }
}

void draw() {
  background(0);
  for (int i=0; i<3; i++) {
    image(img[type][i], width*i/3, 0, width/3, height);
  }
  fill(255, 0, 0);
  text(tName[type], 20, 20);
}

// バイナリ化
// tの値 1:無圧縮, 2:非等長, 3:ランレングス
// kの値 0:A, 1:B, 2:C
void encode(int t, int k) {
  ArrayList<Byte> b = new ArrayList<Byte>();
  switch(t) {
  case 1:
    b = encode1(k);
    break;
  case 2:
    b = encode2(k);
    break;
  case 3:
    b = encode3(k);
    break;
  }
  // リストから配列にデータをコピーする
  byte[] bytes = new byte[b.size()];
  for (int i=0; i<bytes.length; i++) {
    bytes[i] = b.get(i);
  }
  print(char(int('A')+k) + tName[t] + ":" + bytes.length + "バイト ");
  println("("+int(100*bytes.length/(w*h/8))+"%)");
  // ファイルに書き出す
  saveBytes("data/" + t + char(int('A')+k) + tName[t] + ".dat", bytes);
}

// 無圧縮でバイナリ化したリストを返す
ArrayList<Byte> encode1(int k) {
  ArrayList<Byte> bytes = new ArrayList();
  int pos = 0; // 1バイト中の位置
  byte b = 0; // 8bit(1バイト)分の情報を入れる
  for (int j=0; j<h; j++) {
    for (int i=0; i<w; i++) {
      // (i, j)のピクセルの色に応じたビットをbに追加
      pos++;
      if (pos<8) {
        // 2進数的な桁上げ
      }
      // 8ビット目の処理後ならリストにbを追加してリセット
      else {
        bytes.add(b);
        pos=0;
        b=0;
      }
    }
  }
  // 最後に8bitに達しなかった分の後ろに0を詰めてリストに追加
  for (; pos<7; pos++) {
    b*=2;
  }
  bytes.add(b);
  return bytes;
}

// 非等長符号でバイナリ化したリストを返す
ArrayList<Byte>  encode2(int k) {
  ArrayList<Byte> bytes = new ArrayList();
  return bytes;
}

// ランレングス符号でバイナリ化したリストを返す
ArrayList<Byte>  encode3(int k) {
  ArrayList<Byte> bytes = new ArrayList();
  return bytes;
}

// バイナリファイルから画像を復元
// tの値 1:無圧縮, 2:非等長, 3:ランレングス
// kの値 0:A, 1:B, 2:C
void decode(int t, int k) {
  // ファイル読み込み
  byte[] bytes = loadBytes("data/" + t + char(int('A')+k) + tName[t] + ".dat");
  switch(t) {
  case 1:
    decode1(k, bytes);
    break;
  case 2:
    decode2(k, bytes);
    break;
  case 3:
    decode3(k, bytes);
    break;
  }
}

// 無圧縮データから画像を復元
void decode1(int k, byte[] bytes) {
  int x=0;
  int y=0;
  // 文字列化して結合する
  String data = "";
  for (int i=0; i<bytes.length; i++) {
    data += binary(bytes[i]);
  }
  for (int i=0; i<w*h; i++) {
    // データの値に応じて(x, y)の色を設定
    // 次の位置に移動
    x++;
    if (x==w) {
      x=0;
      y++;
    }
  }
  img[1][k].updatePixels();
}

// 非等長符号データから画像を復元
void decode2(int k, byte[] bytes) {
}

// ランレングス符号データから画像を復元
void decode3(int k, byte[] bytes) {
}

// 処理を実行
void mousePressed() {
  for (int k=0; k<3; k++) {
    for (int t=1; t<=3; t++) {
      encode(t, k);
      decode(t, k);
    }
    println();
  }
  for (int t=1; t<=3; t++) {
    background(0);
    for (int k=0; k<3; k++) {
      image(img[t][k], width*k/3, 0, width/3, height);
    }
    save("data/"+ t + tName[t] + ".png");
  }
}

// 押したキーに応じて対応する画像を表示
void keyPressed() {
  int k = key-'0';
  if (k>=0 && k<=3) {
    type = k;
  }
}
  1. Processingのエディタに上のサンプルプログラムのコードをコピー&ペーストする。
  2. 「img14」という名前で保存する。
  3. ペイント3Dまたはペイントで次のような3つの元画像をつくる。
    • 元A.png : サイズ250x250ピクセルで、白背景に太さ1ピクセルの黒い輪郭のみの図形
    • 元B.png : 元A.pngの中を黒で塗りつぶした図形
    • 元C.png : サイズ250x250ピクセルで、8ポイント、細字の設定でできる限り文字で埋め尽くしたもの


  4. 「元A.png」「元B.png」「元C.png」をProcessingのエディタにドラッグ&ドロップする。
  5. 実行してクリックしてから0, 1, 2, 3キーを押し、0のときは3つの元画像、1, 2, 3では真っ黒な画像が表示されることを確認する。


  6. encode1関数の「// (i, j)のピクセルの色に応じたビットをbに追加」の下に以下のコードを追加する。
  7. (調べる画像は img[0][k] (k番目の元画像))
    (二値化済みなので度のピクセルも明度は0, 255のどちらか)
    (白ならbの一番下のビットに1, 黒なら0を入れる)
          b += brightness(img[0][k].pixels[i+j*w])/255;

  8. encode1関数の「// 2進数的な桁上げ」の下に以下のコードを追加する。
  9. (データを格納する変数 b を2倍するだけ)
            b *= 2;

  10. decode1関数の「// データの値に応じて(x, y)の色を設定」の下に以下のコードを追加する。
  11. (作る画像は img[1][k])
    (dataは'0'か'1'のどちらかが元画像のピクセル数だけ並んだ (正確には文字数が8の倍数になるように後ろを詰めた) 文字列)
    (チェックするのは data の i 番目の文字)
    (それが'0'なら (x, y) のピクセルを黒、'1'なら白にする)
        img[1][k].pixels[x+y*w]=color((data.charAt(i)-'0')*255);

  12. 実行して画面をクリックし、0, 1キーを交互に押して赤字以外の部分が完全に同じになることを確認する。
  13. (dataフォルダにできる「1A無圧縮.dat」「1B無圧縮.dat」「1C無圧縮.dat」が元画像の情報をバイナリデータ化したもの)
    (img[1][0], img[1][1], img[1][2] がそのデータをもとに復元された画像)
    (1キーを押したときにこれらが並んで表示される)
    (その状態の画像が「1無圧縮.png」として保存される)
ここでできる拡張子datのファイルは画像ファイルではないので「フォト」などの画像ビューアでは開けないが、元画像の情報をすべて含んでいる。
(ペイント3Dではなく、旧版の) ペイントで、画像ファイルを「ファイル」→「名前をつけて保存」→「その他の形式」を選び、「ファイルの種類」を「モノクロビットマップ」(白黒の情報しか扱えない形式) として保存した場合のファイルサイズと、この課題でできる拡張子datのもののサイズはほぼ等しい。
「1A無圧縮.dat」「1B無圧縮.dat」「1C無圧縮.dat」の中身はテキストエディタなどでは見られないが、バイナリエディタ を使えばデータの並びが見られる。
元A.png はほとんどのピクセルが白 → データをエディタでみるとほとんどが FF
元B.png は広い白エリアと黒エリアがある → FF か 00 の部分が多い
元C.png は白と黒が短い間隔で入れ替わる → どちらでもないものが多い
  • この段階でdataフォルダの「1A無圧縮.dat」「1B無圧縮.dat」「1C無圧縮.dat」「1_無圧縮.png」が本来の状態になっている。
  • うまくいかない場合は、最終的なencode1関数最終的なdecode1関数とコードを見比べる。

非等長符号による圧縮

概要

「元A.png」のようにはほとんどのピクセルが白で、黒がたまにしか出てこないような場合は、ビットの並びを別のものに置き換えると効率を上げられる。
黒→0, 白→1の置き換えをしたあとで 2bit ずつに区切り、
00 → 000
01 → 001
10 → 01
11 → 1
のように置き換えてみると、白が続くエリアでは「1」の数が半分になるので、データ量はほぼ半分で済む。
このように置き換え先の並びの長さが異なるものを非等長符号という。





逆に、黒が続くエリアでは「0」の数が1.5倍になるのでデータが増えてしまう。
効率よく圧縮するには、置き換えのパターンを元画像の性質に合わせて工夫する (黒が多い画像では00を1ビットに、11を3ビットに置き換えるなど) 必要がある。

ここでは行わないが、色の偏りが十分に大きい時は4bitや8bitずつに区切って置き換えを行えばさらに圧縮率を上げられる。

課題 2

  1. encode2関数の中の2行のコードを消し、そこにencode1関数の中のコードをコピー&ペーストする。
  2. encode2関数の i についてのfor文の「i++」を「i+=2」に変更する。
  3. (2bitずつセットで処理するため)

  4. そのすぐ下に以下のコードを追加する。
  5. (元の並び 00, 01, 10, 11 に対して bb には 0, 1, 2, 3の値が入る)
          // 横に並んだ元画像のピクセルの色に対応する値(0, 1)
          int b1 = (int)brightness(img[0][k].pixels[i+j*w])/255;
          int b0 = (int)brightness(img[0][k].pixels[i+1+j*w])/255;
          // b1, b0の並びを2進数として扱った値
          int bb = b1*2+b0;

  6. その下のコードを以下のように変更する。
  7. (置き換え用の配列 code はプログラム先頭で定義済み)
    (元のコードを cpos についてのfor文で囲む → 赤部分だけ追加して Ctrl+T で整形し、そのあと青部分を書き換える)
    (置き換える並びは1~3文字なので、途中で b が「満杯」になることもある。そのため、チェックは元の2bitの塊ごとではなく、置き換えた並びの追加1bitごとに行う)
          // (i, j)のピクセルの色に応じたビットをbに追加
          b += brightness(img[0][k].pixels[i+j*w])/255;
          pos++;
          if (pos<8) {
            // 2進数的な桁上げ
            b *= 2;
          }
          // 8ビット目の処理後ならリストにbを追加してリセット
          else {
            bytes.add(b);
            pos=0;
            b=0;
          }
          // 置き換えた並びをbに追加
          for (int cpos=0; cpos<code[bb].length(); cpos++) {
            // code[bb]の文字に応じたビットをbに追加
            b += code[bb].charAt(cpos)-'0';
            pos++;
            if (pos<8) {
              // 2進数的な桁上げ
              b *= 2;
            }
            // 8ビット目の処理後ならリストにbを追加してリセット
            else {
              bytes.add(b);
              pos=0;
              b=0;
            }
          }

  8. 実行して画面をクリックする。
  9. (まだバイナリデータがつくられるだけで、これをもとに復元した画像はできない)
    (非等長符号でデータ化したときのファイルサイズと圧縮率がコンソールに表示される)
    基本的には、元画像の白の割合が多い方が効率が良く (%の数値が小さく) なる。
    元B.pngで黒塗りの部分の面積が大きいと、無圧縮のときよりもファイルサイズが大きくなることもある。

  10. decode1関数の中のコードを消し、decode2関数の中にコピー&ペーストする。
  11. decode2関数の最後の「img[1][k].updatePixels();」を「img[2][k].updatePixels();」に変更する。
  12. decode2関数の色設定処理にかかわる部分を以下のように書き換える。
  13. (substring関数は文字列から指定部分だけを取り出す関数)
    (encode2関数で使った「置き換えの並び」との一致を調べ、それに対応する2bitの並びに応じてピクセルの色を設定する)
      for (int i=0; i<w*h; i++) {
        // データの値に応じて(x, y)の色を設定
        img[1][k].pixels[x+y*w]=color((data.charAt(i)-'0')*255);
        // 次の位置に移動
        x++;
        if (x==w) {
          x=0;
          y++;
        }
      }
    
      while (true) {
        int bitnum = -1; // 置き換えるビットの並びの番号(0~3)
        for (int j=0; j<code.length; j++) {
          // dataの先頭の文字列とcodeの並びを比較する
          if (code[j].length()<=data.length()) {
            if (code[j].equals(data.substring(0, code[j].length()))) {
              bitnum = j;
            }
          }
        }
        // 置き換え先の値に応じてピクセルの色を設定する
        for (int i=0; i<2; i++) {
          img[2][k].pixels[x+i+y*w] = color((bt[bitnum].charAt(i)-'0')*255);
        }
        // 読み込んだ分だけデータを削除
        data = data.substring(code[bitnum].length());
        // 次の位置に移動
        x+=2;
        if (x==w) {
          // 最後のピクセルに達したらループを抜ける
          if (y==h-1) {
            break;
          }
          x=0;
          y++;
        }
      }
    

  14. 実行して画面をクリックし、0, 1, 2キーを順に押して赤字以外の部分が完全に同じになることを確認する。
  15. (dataフォルダにできる「2A非等長.dat」「2B非等長.dat」「2C非等長.dat」が元画像の情報を非等長符号でバイナリデータ化したもの)
    (img[2][0], img[2][1], img[2][2] がそのデータをもとに復元された画像)
    (2キーを押したときにこれらが並んで表示される)
    (その状態の画像が「2非等長.png」として保存される)


  16. この段階でdataフォルダの「2A非等長.dat」「2B非等長.dat」「2C非等長.dat」「2_非等長.png」も本来の状態になる。
  17. うまくいかない場合は、最終的なencode2関数最終的なdecode2関数とコードを見比べる。

ランレングス符号による圧縮

概要

元画像のそれぞれの行について、「白ピクセルが何個続いたか」「黒ピクセルが何個続いたか」を交互にカウントし、そのデータを記録することで画像の情報を保存することもできる。(画像処理に限らないが) このような手法をランレングス符号という。
この例なら、赤線の1行のデータはたったの3バイトで済む。


ランレングス符号では白・黒が切り替わるたびに1バイト分の情報を使うので、元A.png, 元B.pngのような単純な図形ならかなり効率よく圧縮できるが、元C.pngのように頻繁に白黒が入れ替わる画像では無圧縮のときよりもファイルサイズが大きくなってしまうこともある。
(1バイトでカウントできる数は実質 0~255 なので、画像の横幅が256ピクセル以上の場合はそこでも区切る必要があるが、今回の課題の画像のサイズは250x250なので、白黒の切り替わりのみを考慮してデータを作成するだけでよい)

課題 3

  1. encode3関数の中の2行のコードを消し、そこに以下のコードをコピー&ペーストする。
  2. (今回の元画像の作り方では、左端のピクセルはほぼ白になるので、各行の最初で previousColor(直前の色) を白に設定する)
    (一つずつ右に移動し、そこがpreviousColorと同じ色ならカウントを進める)
    (色が変わったらその時点のカウント数をリストに追加する)
      ArrayList<Byte> bytes = new ArrayList();
      for (int j=0; j<h; j++) {
        int count=0; // 連続個数カウント
        int previousColor=1; // 「直前の色」(最初は白とする)
        for (int i=0; i<w; i++) {
          int currentColor = int(brightness(img[0][k].pixels[i+j*w]))/255;
          // 色が変わったら
          if (currentColor != previousColor) {
            previousColor = currentColor; // 「直前の色」を更新
            bytes.add(byte(count)); // リストに連続個数を追加
            count = 1; // このピクセルの分をカウント
          }
          // 前と同じ色なら連続個数を追加
          else {
            count++;
          }
          // 行の最後に達したら
          if (i == w-1) {
            bytes.add(byte(count)); // リストに連続個数を追加
          }
        }
      }
      return bytes;

  3. 実行して画面をクリックする。
  4. (まだバイナリデータがつくられるだけで、これをもとに復元した画像はできない)
    (ランレングス符号でデータ化したときのファイルサイズと圧縮率がコンソールに表示される)
    元画像の白・黒の切り替わりの数が少ないほど圧縮の効率が良くなる。
    元C.pngで文字が密に詰まっている場合は、無圧縮のときよりもファイルサイズが大きくなることもある。

  5. decode3関数の中に以下のコードをコピー&ペーストする。
  6. (bytes に入っているのが「連続個数」そのものなので、decode1, decode2のときのように文字列化はせず、整数に変換して扱う)
    (currentColor には0か1の値が入る。0が黒、1が白に対応する)
      int x=0;
      int y=0;
      // 8ビットずつ画像のピクセルに置き換える
      int currentColor=1;
      for (int l=0; l<bytes.length; l++) {
        int n = bytes[l] & 0xff; // データを整数化
        for (int i=0; i<n; i++) {
          img[3][k].pixels[x+i+y*w] = color(currentColor*255);
        }
        x+=n; // 設定した分だけ現在位置を進める
        // 行末に達したら次の行に移って色を白に戻す
        if (x>=w) {
          x=0;
          y++;
          currentColor=1;
        }
        // 行の途中の場合は白黒反転
        else {
          currentColor=1-currentColor;
        }
      }
      img[3][k].updatePixels();

  7. 実行して画面をクリックし、0~3キーを順に押して赤字以外の部分が完全に同じになることを確認する。
  8. (dataフォルダにできる「3Aランレングス.dat」「3Bランレングス.dat」「3Cランレングス.dat」が元画像の情報をランレングス符号でバイナリデータ化したもの)
    (img[3][0], img[3][1], img[3][2] がそのデータをもとに復元された画像)
    (3キーを押したときにこれらが並んで表示される)
    (その状態の画像が「3ランレングス.png」として保存される)


  9. この段階で「3Aランレングス.dat」「3Bランレングス.dat」「3Cランレングス.dat」「3ランレングス.png」も然るべきものになる。
ランレングス符号で作ったデータをバイナリエディタで見ると、「元A.png」「元B.png」からできたものはいろいろな値が並んだ「密度の濃いデータ」になっていることがわかる。
それに比べて、「元C.png」からできたものは「01」~「05」くらいのものが多く、上位ビットがほとんど0の無駄の多いデータになっている。

提出

理解度確認テスト予告

次回の授業の初めに第10~14回の内容についての理解度確認テストを行う。

戻る

inserted by FC2 system