第14回 データ圧縮

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

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

プログラムを実行してしばらく待つとコンソールに「完了」が表示され、実行画面上に3つの元画像が並んで表示される。
dataフォルダには9個のデータファイルとそれを元に復元されたものを横に結合した画像、さらに圧縮率の情報が書き込まれた画像「結果.png」が作られる。
そのあとでキーボードの0~4のキーを押すとこれらの画像が画面に表示される。
(すべての画像は自動的に作成されるので、キーボードを使うのは結果確認のためだけ)
キー 画像 意味 特徴
0 元.png 3つの元画像を横に並べたもの
1 1無圧縮.png 無圧縮でデータ化したものから復元したものを横に並べたもの 元.pngと完全に同じ
2 2非等長.png 非等長符号でデータ化したものから復元したものを横に並べたもの 元.pngと完全に同じ
3 3ランレングス.png ランレングス符号でデータ化したものから復元したものを横に並べたもの 元.pngと完全に同じ
4 結果.png 画像・データ化の方法ごとの圧縮率が書き込まれたもの 黒背景の白文字画像
そのほかにdataフォルダの中に存在する・できるもの
復元した画像はいずれも元画像と完全に同じになる。

キーと表示される画像

1. 無圧縮のデータ化

概要

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

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

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

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

課題 1

  1. Processingを起動する。
  2. 以下のコードをコピー&ペーストする。
  3. // 画像の変数
    PImage[][] img = new PImage[4][3]; // 元画像と復元画像[元,無圧縮,非等長,ランレングス][A, B, C]
    PImage[] imgr = new PImage[5]; // 保存用に結合した画像と圧縮結果画像[元,無圧縮,非等長,ランレングス,圧縮結果]
    PGraphics[] pg = new PGraphics[5]; // imgrに対応するグラフィックス
    
    // 画像名
    String[] fName = {"元", "1無圧縮", "2非等長", "3ランレングス", "結果"};
    int w, h; // 元画像の横と縦のサイズ
    // 非等長符号の0000~1111の置き換え先
    String[] code = {"", "", "", "", "", "", "", "", "", "", "", "", "", "", "", ""};
    String[] bt = new String[16]; // codeの逆の置き換え先
    
    void setup() {
      size(750, 250);
      for (int i=0; i<16; i++) {
        bt[i]=binary(i, 4);
      }
      noSmooth();
      // 元画像のロードと変換結果保存用画像の準備
      for (int i=0; i<3; i++) {
        img[0][i]=loadImage(char('A'+i)+"元.bmp");
        w=img[0][i].width;
        h=img[0][i].height;
        for (int j=1; j<=3; j++) {
          img[j][i]=createImage(w, h, ARGB);
        }
      }
      // 結果表示用画像とそのグラフィックスの準備
      for (int i=0; i<=4; i++) {
        imgr[i] = createImage(w*3, h, RGB);
        pg[i] = createGraphics(imgr[i].width, imgr[i].height);
        pg[i].beginDraw();
      }
      pg[4].textFont(createFont("MS Pゴシック", 16));
      // 元画像の結合画像作成
      for (int i=0; i<3; i++) {
        pg[0].image(img[0][i], w*i, 0, w, h);
      }
      textFont(createFont("MS Pゴシック", 48));
      for (int k=0; k<3; k++) {
        // k番目の画像を無圧縮でデータ化する
        // 無圧縮のデータファイルを読み込んでk番目の画像を復元する
      }
      for (int k=0; k<3; k++) {
        // k番目の画像を非等長符号でデータ化する
        // 非等長符号のデータファイルを読み込んでk番目の画像を復元する
      }
      for (int k=0; k<3; k++) {
        // k番目の画像をランレングス符号でデータ化する
        // ランレングス符号のデータファイルを読み込んでk番目の画像を復元する
      }
      // 結果をファイルに保存
      for (int i=0; i<=4; i++) {
        pg[i].endDraw();
        imgr[i].pixels = pg[i].pixels;
        imgr[i].updatePixels();
        imgr[i].save("data/" + fName[i] + ".png");
      }
      image(imgr[0], 0, 0, width, height);
      println("完了");
    }
    
    void draw() {
    }
    
    // 押したキーに応じて対応する画像を表示
    void keyPressed() {
      int k = key-'0';
      if (k>=0 && k<=4) {
        background(0);
        image(imgr[k], 0, 0, width, height);
        fill(255, 0, 0);
        text(fName[k], 30, height-30);
        fill(0, 0, 100);
      }
    }

  4. 「img14」という名前で保存する。
  5. ペイントで次のような3つのモノクロビットマップの元画像をつくる。
    • A元.bmp : サイズ250x250ピクセルで、白背景に太さ1ピクセルの黒い輪郭のみの図形を描いたもの
    • B元.bmp : A元.bmpの図形の中を黒で塗りつぶしたもの
    • C元.bmp : サイズ250x250ピクセルで、「テキスト」の機能でMSゴシック、8ポイントの設定でできる限り英語の文字で埋め尽くしたもの


  6. 「A元.bmp」「B元.bmp」「C元.bmp」をProcessingのエディタにドラッグ&ドロップする。
  7. draw関数の下に以下のコードをコピー&ペーストする。
    // 元画像kを無圧縮でバイナリ化したデータをファイルに保存
    void encode1(int k) {
      ArrayList<Byte> b = new ArrayList();
      int pos=0; // 1バイト中の位置
      byte b0=0; // 8bit (1バイト)分の情報を入れる変数
      for (int j=0; j<h; j++) {
        for (int i=0; i<w; i++) {
          // (i, j)のピクセルの明度に応じたビットをb0に追加
          pos++;
          if (pos<8) {
            b0*=2; // 2進数的な桁上げ
          } else {
            b.add(b0);
            pos=0;
            b0=0;
          }
        }
      }
      // 最後に8bitに達しなかった分の後ろに0を詰めてリストに追加
      for (; pos<7; pos++) {
        b0*=2;
      }
      b.add(b0);
      // リストから配列にデータをコピーする
      byte[] bytes = new byte[b.size()];
      for (int i=0; i<bytes.length; i++) {
        bytes[i]=b.get(i);
      }
      // 圧縮結果を画像に書き込む
      String result = char('A'+k) + fName[1] + ":" + bytes.length + "バイト";
      result += "(" + int(100*bytes.length/(w*h/8)) + "%)";
      pg[4].text(result, 10, 16*(1+k));
      // バイナリデータをファイルに保存
      saveBytes("data/" + char('A'+k) + fName[1] + ".dat", bytes);
    }

  8. encode1関数の「// (i, j)のピクセルの明度に応じたビットをb0に追加」の下に、それに応じたコードを追加する。
  9. (調べる画像は img[0][k] (k番目の元画像))
    (その画像の(i, j)のピクセルはimg[0][k].pixels[i+j*w])
    (brightness関数にそれを入れれば明度 (黒なら0、白なら255) が得られる)
    (それを255で割れば黒なら0、白なら1になる)
    (その結果をb0に加える)

  10. encode1関数の下に、以下のコードをコピー&ペーストする。
    // 無圧縮データから画像kを復元
    void decode1(int k) {
      // ファイル読み込み
      byte[] bytes = loadBytes("data/" + char('A'+k) + fName[1] + ".dat");
      String data=""; // バイナリデータを文字列化して入れるもの
      for (int i=0; i<bytes.length; i++) {
        data += binary(bytes[i]);
      }
      for (int i=0; i<w*h; i++) {
        // i番目のデータが'0'なら黒、'1'なら白を画像[1][k]のi番目のピクセルに設定する
      }
      img[1][k].updatePixels();
      pg[1].image(img[1][k], w*k, 0);
    }

  11. decode1関数の「// i番目のデータが'0'なら黒、'1'なら白を画像[1][k]のi番目のピクセルに設定する」の下に、それに応じたコードを追加する。
  12. (画像[1][k]のi番目のピクセルはimg[1][k].pixels[i])
    (i番目のデータは data.charAt(i)で、その文字は'0'か'1')
    (data.charAt(i)-'0'は数値としての0か1)
    (それに255をかければ0か255)
    (「color()」のカッコの中にそれを入れれば白か黒になる)

  13. setup関数の「// k番目の画像を無圧縮でデータ化する」「// 無圧縮のデータファイルを読み込んでk番目の画像を復元する」の左にそれぞれ必要なコードを追加する。
  14. (呼ぶのはそれぞれencode1関数とdecode1関数)
    (引数は画像番号)

  15. プログラムを実行する。
    • しばらく待つと3つの元画像が並んで表示される。
    • dataフォルダには元画像の情報を無圧縮でバイナリデータ化した「A1無圧縮.dat」「B1無圧縮.dat」「C1無圧縮.dat」ができる。
    • 1キーを押すと無圧縮でデータ化したものから復元した画像が表示される (元画像と完全に同じになる)。
    • 4キーを押すとこの方法でデータ化したもののファイルサイズが表示される。
      (概要にある通り、色によらずピクセルあたりのデータ量が同じなのでA~Cのファイルサイズは同じになる)
      (2, 3キーを押すと画面が真っ黒になる。これは課題2以降が未実装なため)

    キーと表示される画像

このプログラムでは、画像の情報をencode1関数で変換して拡張子「dat」のデータファイルに保存し、逆にそのファイルから画像をdecode1関数で復元している。
うまくいっていれば、復元された画像は元のものと全く同じになっているはず。
ここでできる拡張子datのファイルは画像ファイルではないので「フォト」などの画像ビューアでは開けないが、元画像の情報をすべて含んでいる。
「A1無圧縮.dat」「B1無圧縮.dat」「C1無圧縮.dat」の中身はテキストエディタなどでは見られないが、バイナリエディタ を使えばデータの並びが見られる。
A元.bmp はほとんどのピクセルが白 → A1無圧縮.datをエディタでみるとほとんどが FF
B元.bmp は広い白エリアと黒エリアがある → B1無圧縮.datにはFF か 00 の部分が多い
C元.bmp は白と黒が短い間隔で入れ替わる → C1無圧縮.datにはどちらでもないものが多い

2. 非等長符号

概要

「A元.png」のようにはほとんどのピクセルが白で、黒がたまにしか出てこないような場合は、ビットの並びを別のものに置き換えると効率を上げられる。
黒→0, 白→1の置き換えをしたあとで 4bit ずつに区切り、
0000 → 000000000000000
0001 → 000000000000001
0010 → 00000000000001
0100 → 0000000000001
1000 → 000000000001
0011 → 00000000001
1100 → 0000000001
0110 → 000000001
1001 → 00000001
0101 → 0000001
1010 → 000001
1110 → 00001
1101 → 0001
1011 → 001
0111 → 01
1111 → 1

のように1の数が多いものが短く、0の数が多いものが長くなるように置き換えてみる (置き換え前の4ビットのうち、赤は1が1つ、青は1が2つ、緑は1が3つある)。
このように置き換えれば、白が続くエリアでは「1111」が「1」で表わせるので、データ量は1/4で済む。
逆に黒が続くエリアでは「0000」が「000000000000000」になり3.75倍にに増えてしまうが、白の割合が多い画像なら全体ではデータ量を減らせる。
例えばこのような8×8の画像をこの方法で変換すると、データの量は36ビットになり、無圧縮の場合 (64ビット) に比べて半分程度のデータ量で画像を表わすことができる。
このように置き換え先の並びの長さが異なるものを非等長符号という。
(これは非等長符号のうちの最適な置き換え方というわけではなく、工夫すればデータ量をさらに少なくすることもできる)
1 1 1 1 1 1 1 1
1 1 1 0 0 1 1 1
1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1
1111 1111
1110 0111
1101 1111
1011 1111
1011 1111
1101 1111
1110 0111
1111 1111
1 1
00001 01
0001 1
001 1
001 1
0001 1
00001 01
1 1

課題 2

  1. プログラム先頭の配列 code の中に、変換前のビットの並び0000~1111に対応した値を書き込む。
    概要の変換を、左側が昇順になるように並べ替えると以下のようになる。
    0000 → 000000000000000
    0001 → 000000000000001
    0010 → 00000000000001
    0011 → 00000000001
    0100 → 0000000000001
    0101 → 0000001
    0110 → 000000001
    0111 → 01
    1000 → 000000000001
    1001 → 00000001
    1010 → 000001
    1011 → 001
    1100 → 0000000001
    1101 → 0001
    1110 → 00001
    1111 → 1

  2. decode1関数の下に、以下のコードをコピー&ペーストする。
    // 元画像kを非等長符号でバイナリ化したデータをファイルに保存
    void encode2(int k) {
      ArrayList<Byte> b = new ArrayList();
      int pos=0; // 1バイト中の位置
      byte b0=0; // 8bit (1バイト)分の情報を入れる変数
      for (int j=0; j<h; j++) {
        for (int i=0; i<w; i+=4) {
          // 横に並んだ元画像のピクセルの色に対応する値(0, 1)
          int bb_[]={0, 0, 0, 0};
          for (int l=0; l<4; l++) {
            if (i+l<w) {
              bb_[l]+=(int)brightness(img[0][k].pixels[i+l+j*w])/255;
            }
          }
          // bb_のビットの並びを2進数として扱った値
          int bb = bb_[0]*8+bb_[1]*4+bb_[2]*2+bb_[3];
          // 置き換えた並びをb0に追加
          for (int cpos=0; cpos<code[bb].length(); cpos++) {
            // code[bb]の文字に応じたビットをb0に追加
            b0 += code[bb].charAt(cpos)-'0';
            pos++;
            if (pos<8) {
              // 2進数的な桁上げ
              b0 *= 2;
            }
            // 8ビット目の処理後ならリストにb0を追加してリセット
            else {
              b.add(b0);
              pos=0;
              b0=0;
            }
          }
        }
      }
      // 最後に8bitに達しなかった分の後ろに0を詰めてリストに追加
      for (; pos<7; pos++) {
        b0*=2;
      }
      b.add(b0);
      // リストから配列にデータをコピーする
      byte[] bytes = new byte[b.size()];
      for (int i=0; i<bytes.length; i++) {
        bytes[i]=b.get(i);
      }
      // 圧縮結果を画像に書き込む
      String result = char('A'+k) + fName[2] + ":" + bytes.length + "バイト";
      result += "(" + int(100*bytes.length/(w*h/8)) + "%)";
      pg[4].text(result, 10, 16*(5+k));
      // バイナリデータをファイルに保存
      saveBytes("data/" + char('A'+k) + fName[2] + ".dat", bytes);
    }

  3. encode2関数の下に、以下のコードをコピー&ペーストする。
    // 非等長符号で圧縮したデータから画像kを復元
    void decode2(int k) {
      // ファイル読み込み
      byte[] bytes = loadBytes("data/" + char('A'+k) + fName[2] + ".dat");
      String data=""; // バイナリデータを文字列化して入れるもの
      for (int i=0; i<bytes.length; i++) {
        data += binary(bytes[i]);
      }
      int x=0;
      int y=0;
      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<4; i++) {
          if (x+i<w) {
            img[2][k].pixels[x+i+y*w] = color((bt[bitnum].charAt(i)-'0')*255);
          }
        }
        // 読み込んだ分だけデータを削除
        data = data.substring(code[bitnum].length());
        // 次の位置に移動
        x+=4;
        if (x>=w) {
          // 最後のピクセルに達したらループを抜ける
          if (y==h-1) {
            break;
          }
          x=0;
          y++;
        }
      }
      img[2][k].updatePixels();
      pg[2].image(img[2][k], w*k, 0);
    }

  4. setup関数の「// k番目の画像を非等長符号でデータ化する」「// 非等長符号のデータファイルを読み込んでk番目の画像を復元する」の左にそれぞれ必要なコードを追加する。
  5. (呼ぶのはそれぞれencode2関数とdecode2関数)
    (引数は画像番号)

  6. プログラムを実行する。
    • dataフォルダには元画像の情報を非等長符号でバイナリデータ化した「A2非等長.dat」「B2非等長.dat」「C2非等長.dat」ができる。
    • 2キーを押すと非等長符号でデータ化したものから復元した画像が表示される (元画像と完全に同じになる)。
    • 4キーを押すと無圧縮・非等長符号でデータ化したもののファイルサイズと圧縮率 (無圧縮を基準としたもの) が表示される。
      (基本的には、元画像の白の割合が多い方が効率が良く (%の数値が小さく) なる)
      (A元.bmpはほとんど白なのでファイルサイズが小さくなり、B元.bmpは黒の割合が多いので無圧縮のときよりもファイルサイズが大きくなることが多い)
      (3キーを押すと画面が真っ黒になる。これは課題3が未実装なため)

    キーと表示される画像

3. ランレングス符号

概要

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


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

課題 3

  1. decode2関数の下に、以下のコードをコピー&ペーストする。
    // 元画像kをランレングス符号でバイナリ化したデータをファイルに保存
    void encode3(int k) {
      ArrayList<Byte> b = new ArrayList();
      for (int j=0; j<h; j++) {
        int count=0; // 連続個数カウント
        int previousColor=1; // 「直前の色」(最初は白とする)
        for (int i=0; i<w; i++) {
          // 元画像kの(i, j)のピクセルが黒なら0, 白なら1を int currentColorに入れる
          int currentColor = 0;
          // 色が変わったら
          if (currentColor != previousColor) {
            previousColor = currentColor; // 「直前の色」を更新
            b.add(byte(count)); // リストに連続個数を追加
            count = 1; // このピクセルの分をカウント
          }
          // 前と同じ色なら連続個数を追加
          else {
            count++;
          }
          // 行の最後に達したら
          if (i == w-1) {
            b.add(byte(count)); // リストに連続個数を追加
          }
        }
      }
      // リストから配列にデータをコピーする
      byte[] bytes = new byte[b.size()];
      for (int i=0; i<bytes.length; i++) {
        bytes[i]=b.get(i);
      }
      // 圧縮結果を画像に書き込む
      String result = char('A'+k) + fName[3] + ":" + bytes.length + "バイト";
      result += "(" + int(100*bytes.length/(w*h/8)) + "%)";
      pg[4].text(result, 10, 16*(9+k));
      // バイナリデータをファイルに出力
      saveBytes("data/" + char('A'+k) + fName[3] + ".dat", bytes);
    }

  2. encode3関数の「// 画像[0][k]の(i, j)のピクセルが黒なら0, 白なら1をcurrentColorに入れる」の下のコードを、コメント文に合うように変更する。
  3. (画像[0][k]の(i, j)のピクセルはimg[0][k].pixels[i+j*w])
    (brightness関数でその明度を取得できる。値は0.0か255.0のどちらか)
    (それを255で割ってから整数化すれば0か1が得られる)

  4. encode3関数の下に、以下のコードをコピー&ペーストする。
    // ランレングス符号で圧縮したデータから画像kを復元
    void decode3(int k) {
      // ファイル読み込み
      byte[] bytes = loadBytes("data/" + char('A'+k) + fName[3] + ".dat");
      int x=0;
      int y=0;
      // 8ビットずつ画像のピクセルに置き換える
      int currentColor=1;
      for (int l=0; l<bytes.length; l++) {
        int n = 0; // l番目のデータを整数化してnに入れる
        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();
      pg[3].image(img[3][k], w*k, 0);
    }

  5. decode3関数の「// l番目のデータを整数化してnに入れる」の左のコードを、コメント文に合うように変更する。
  6. (l番目のデータはbytes[l])
    (演算「Byte.toUnsignedInt」でそれを整数化した値が得られる)

  7. setup関数の「// k番目の画像をランレングス符号でデータ化する」「// ランレングス符号のデータファイルを読み込んでk番目の画像を復元する」の左にそれぞれ必要なコードを追加する。
  8. (呼ぶのはそれぞれencode3関数とdecode3関数)
    (引数は画像番号)

  9. プログラムを実行する。
    • dataフォルダには元画像の情報をランレングス符号でバイナリデータ化した「A3ランレングス.dat」「B3ランレングス.dat」「C3ランレングス.dat」ができる。
    • 3キーを押すとランレングス符号でデータ化したものから復元した画像が表示される (元画像と完全に同じになる)。
    • 4キーを押すと3つの方法でデータ化したもののファイルサイズと圧縮率 (無圧縮を基準としたもの) が表示される。
      (元画像A, Bはランレングス符号では非等長に比べてもかなり効率が良く (%の数値が小さく) なる)
      (元画像Cは白黒が頻繁に切り替わるため、ランレングス符号では無圧縮のときよりもファイルサイズが大きくなることが多い)

    キーと表示される画像



提出

提出先フォーム

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