第14回 データ圧縮

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


非等長符号
ランレングス符号

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

はじめに、これから作るプログラムが完成した時点の機能をざっと見ておく。


圧縮なしのデータ化


課題 1

    ベースのプログラム (このままでは1キーを押したときに空っぽのデータファイルが作られるだけ)
    PImage[] img = new PImage[3];       // 元画像
    PImage[] outputImg = new PImage[3]; // 出力画像
    
    void setup() {
      size(400, 300);
      for (int i=0; i<3; i++) {
        img[i] = loadImage("1元"+i+".png");
        img[i].filter(THRESHOLD, 0.99); // 二値化する(灰色は黒寄りに)
        outputImg[i] = img[i].get();
      }
    }
    
    void draw() {
      image(outputImg[millis()/500%3], 0, 0, width, height);
    }
    
    // 圧縮せずにテキストファイルに書き込む
    void encode1() {
      println("圧縮なし");
      for (int k=0; k<3; k++) { // 画像についての繰り返し
        int bits = 0; // ビット数
        String[] rowdata = new String[img[k].height]; // 1行ごとのデータの配列
        for (int j=0; j<img[k].height; j++) { // 縦座標に対する繰り返し
          rowdata[j] = "";
          for (int i=0; i<img[k].width; i++) { // 横座標に対する繰り返し
            // (i, j)の位置のピクセルの明度に応じてrowdata[j]にに0か1を追加する
            // ビット数をカウント
          }
        }
        saveStrings("data/1圧縮なし"+k+".txt", rowdata); // テキストファイル出力
        println("画像"+k+":"+bits+"ビット"); // ビット数表示
      }
      println();
    }
    
    // encode1で出力したファイルから画像を作成
    void decode1() {
      for (int k=0; k<3; k++) { // 画像についての繰り返し
        String[] line = loadStrings("data/1圧縮なし"+k+".txt"); // ファイルからデータを読み込む
        outputImg[k] = createImage(img[k].width, img[k].height, ARGB); // 出力ファイル
        for (int j=0; j<img[k].height; j++) {  // 縦座標に対する繰り返し
          for (int i=0; i<img[k].width; i++) { // 横座標に対する繰り返し
            // データの値に応じた色を作り、(i, j)のピクセルに設定する
          }
        }
        // 復元した画像ファイルを出力
        outputImg[k].save("data/1圧縮なし"+k+".png");
      }
    }
    
    // 非等長符号に置き換えてテキストファイルに書き込む
    void encode2() {
    }
    
    // encode2で出力したファイルから画像を作成
    void decode2() {
    }
    
    // ランレングス符号に置き換えてテキストファイルに書き込む
    void encode3() {
    }
    
    // encode3で出力したファイルから画像を作成
    void decode3() {
    }
    
    void keyPressed() {
      switch(key) {
      case '1': 
        encode1(); 
        break;
      case '2': 
        decode1(); 
        break;
      case '3': 
        encode2(); 
        break;
      case '4': 
        decode2(); 
        break;
      case '5': 
        encode3(); 
        break;
      case '6': 
        decode3(); 
        break;
      }
    }
    

  1. Processingのエディタに上のサンプルプログラムのコードをコピー&ペーストする。
  2. 「img14」という名前で保存する。
  3. ペイントを起動して画像サイズを横400、縦300にする。
  4. 図形描画機能を使い、線の幅1pxで適当な図形を描き、「1元0.png」という名前で保存する。


  5. 塗りつぶし機能を使って図形の中を黒で塗りつぶし、「名前を付けて保存」で「1元1.png」という名前で保存する。


  6. Ctrl+A, Deleteキーの順に押して画像を真っ白な状態に戻す。
  7. 適当なWebサイトの記事など、長めの文を選択してCtrl+Cでコピーする。
  8. 文字入力機能を使い、画像の範囲に収まるように領域を選択し、フォントサイズ10の細字状態にしてからCtrl+Vで文を貼り付けて (面倒でなければ自前の文を書いても良いが、下図くらいの文字数を入れること)、「名前を付けて保存」で「1元2.png」という名前で保存する。


  9. 「1元0.png」~「1元2.png」をProcessingのウインドウにドラッグ&ドロップする。
  10. encode1関数の「// (i, j)の位置のピクセルの明度に応じてrowdata[j]にに0か1を追加する」の下に、対応するコードを追加する。

  11. 「// ビット数をカウント」の下に、対応するコードを追加する。

  12. 実行して画面をクリックしてからキーボードの「1」キーを押す。
  13. 作成されたファイルをTerapadで開いてみる。「1圧縮なし0.txt」であれば、図のように黒線に対応する部分だけが0になっているはず。


  14. decode1関数の「// データの値に応じた色を作り、(i, j)のピクセルに設定する」の下に、対応するコードを追加する。

  15. 実行して画面をクリックしてからキーボードの「2」キーを押す。


  16. この時点でできる提出ファイル
    ※ うまくいかないときは最終的なencode1関数最終的なdecode1関数とコードを見比べる。

非等長符号による圧縮

課題 2

  1. encode2関数の中に以下のコード・コメント文を追加する。
  2.   println("非等長");
      String[] code = {"000", "001", "01", "1"}; // 00, 01, 10, 11に対応させるビット
      for (int k=0; k<3; k++) { // 画像についての繰り返し
        int bits = 0; // ビット数
        String[] rowData = new String[img[k].height]; // 1行ごとのデータの配列
        for (int j=0; j<img[k].height; j++) { // 縦座標に対する繰り返し
          rowData[j] = "";
          for (int i=0; i<img[k].width; i+=2) {  // 横座標に対する繰り返し(2ずつ)
            // (i, j)のピクセルに対応するビットの値をint aに入れる
            // (i+1, j)のピクセルに対応するビットの値をint bに入れる
            // abの並びに対応する2進数の値(10進)をint cに入れる
            // rowData[j]の後ろにabの並びに対応する変換後のビットを追加する
            // ビット数をカウント
          }
        }
        saveStrings("data/2非等長"+k+".txt", rowData); // テキストファイル出力
        println("画像"+k+":"+bits+"ビット("+int(bits*100/img[k].pixels.length)+"%)"); // ビット数・圧縮率表示
      }
      println();
    

  3. 「// (i, j)のピクセルに対応するビットの値をint aに入れる」の左に、対応するコードを追加する。

  4. 「// (i+1, j)のピクセルに対応するビットの値をint bに入れる」の左に、対応するコードを追加する。

  5. 「// abの並びに対応する2進数の値(10進)をint cに入れる」の左に、対応するコードを追加する。

  6. 「// rowData[j]の後ろにabの並びに対応する変換後のビットを追加する」の左に、対応するコードを追加する。

  7. 「// ビット数をカウント」の左に、対応するコードを追加する。

  8. 実行して画面をクリックしてからキーボードの「3」キーを押す。
  9. decode2関数の中に以下のコード・コメント文を追加する。
  10.   for (int k=0; k<3; k++) { // 画像についての繰り返し
        String[] line = loadStrings("data/2非等長"+k+".txt"); // ファイルからデータを読み込む
        outputImg[k] = createImage(img[k].width, img[k].height, ARGB); // 出力ファイル
        for (int j=0; j<img[k].height; j++) { // 縦座標に対する繰り返し
          String temp = ""; // データファイルから読み込んだビットを入れる仮変数
          String ldata = ""; // 1行分の復元データを入れる文字列
          for (int i=0; i<line[j].length(); i++) { // データの参照位置に対する繰り返し
            temp += line[j].charAt(i); // 仮変数に1ビット分データを追加
            if (line[j].charAt(i) == '1' || temp.length() == 3) { // 1が出現、またはトータル3文字になったら
              // 1ブロック分のデータに対応するビットをldataに追加
              switch(temp) {
              case "000":
                break;
              case "001":
                break;
              case "01":
                break;
              case "1":
                break;
              }
              temp=""; // 仮変数クリア
            }
          }
          for (int i=0; i<img[k].width; i++) { // 横座標に対する繰り返し
            // データの値に応じた色を作り、(i, j)のピクセルに設定する
            outputImg[k].pixels[i+j*img[k].width]=color(255*(ldata.charAt(i)-'0'));
          }
        }
        // 復元した画像ファイルを出力
        outputImg[k].save("data/2非等長"+k+".png");
      }
    

  11. switch構文の「case "000":」~「case "1":」それぞれの下に、「// 1ブロック分のデータに対応するビットをldataに追加」を実現するのに必要なコードを追加する。

  12. 実行して画面をクリックしてからキーボードの「4」キーを押す。


  13. ここで作る提出物
    ※ うまくいかないときは最終的なencode2関数最終的なdecode2関数とコードを見比べる。

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

課題 3

  1. encode3関数の中に以下のコード・コメント文を追加する。
  2.   println("ランレングス");
      for (int k=0; k<3; k++) { // 画像についての繰り返し
        int bits = 0; // ビット数
        String[] rowData = new String[img[k].height]; // 1行ごとのデータの配列
        for (int j=0; j<img[k].height; j++) { // 縦座標に対する繰り返し
          rowData[j] = "";
          int prev=1;  // 直前のビット
          int count=0; // カウント数(同じビットが続いた数)
          for (int i=0; i<img[k].width; i++) { // 横座標に対する繰り返し
            count++; // 連続数をカウントする
            int a = int(brightness(img[k].pixels[i+j*img[k].width]))/255; // 元画像の(i, j)のピクセルの明るさに応じた値(0か1)
            if (a != prev || i== img[k].width-1) { // 直前と違う明るさ、またはその行の最後なら
              // それまでに同じ色が連続した数(9ビット)をデータに追加
              // 「直前のビット」を現在地のビットに変更
              // トータルのビット数をカウント
              // カウント数をリセット
            }
          }
        }
        saveStrings("data/3ランレングス"+k+".txt", rowData); // テキストファイル出力
        println("画像"+k+":"+bits+"ビット("+int(bits*100/img[k].pixels.length)+"%)"); // ビット数・圧縮率表示
      }
      println();
    

  3. 「// それまでに同じ色が連続した数(9ビット)をデータに追加」の左に、対応するコードを追加する。

  4. 「// 「直前のビット」を現在地のビットに変更」の左に、対応するコードを追加する。

  5. 「// トータルのビット数をカウント」の左に、対応するコードを追加する。

  6. 「// カウント数をリセット」の左に、対応するコードを追加する。

  7. 実行して画面をクリックしてからキーボードの「5」キーを押す。
  8. decode3関数の中に以下のコード・コメント文を追加する。
  9.   for (int k=0; k<3; k++) { // 画像についての繰り返し
        String[] line = loadStrings("data/3ランレングス"+k+".txt"); // ファイルからデータを読み込む
        outputImg[k] = createImage(img[k].width, img[k].height, ARGB); // 出力ファイル
        for (int j=0; j<img[k].height; j++) { // 縦座標に対する繰り返し
          int pos = 0; // 横方向の現在地
          int b=1; // その範囲のピクセルの明るさ(0なら黒、1なら白)
          for (int i=0; i<line[j].length(); i+=9) { // データの参照位置に対する繰り返し(9ずつ)
            // i番目から9ビット分切り出し、2進数にして整数化し、int nに入れる(これが連続数)
            // 連続数だけ繰り返し(カウンタ変数はl)
              // 明るさb*255の色を作り、(pos, j)から右にl個目のピクセルの色に設定する
            // }
            // 次のエリアの分を白黒反転
            // 描いた分だけ開始位置を移動
          }
        }
        // 復元した画像ファイルを出力
        outputImg[k].save("data/3ランレングス"+k+".png");
      }
    

  10. 「// i番目から9ビット分切り出し、2進数にして整数化し、int nに入れる(これが連続数)」の左に、対応するコードを追加する。

  11. 「// 連続数だけ繰り返し(カウンタ変数はl)」の左に、対応するコードを追加し、2行下の「// }」のコメントアウトを解除する

  12. 「// 明るさb*255の色を作り、(pos, j)から右にl個目のピクセルの色に設定する」の左に、対応するコードを追加する。

  13. 「// 次のエリアの分を白黒反転」の左に、対応するコードを追加する。

  14. 「// 描いた分だけ開始位置を移動」の左に、対応するコードを追加する。

  15. 実行して画面をクリックしてからキーボードの「6」キーを押す。

  16. プログラムを終了させ、もう一度実行して「1」「3」「5」キーを順に押す。
  17. コンソールでクリックしてからキーボードのキーをCtrl+A, Ctrl+Cの順に押す (コンソールの内容がコピーされる)。
  18. コピーした内容をメモ帳やTeraPadなどの適当なエディタに貼り付け、上の余計な改行を削除して「3サイズ.txt」という名前で保存する。

  19. ここで作る提出物
    ※ うまくいかないときは最終的なencode3関数最終的なdecode3関数とコードを見比べる。

提出

理解度確認テスト予告



戻る inserted by FC2 system