圧縮アルゴリズム

(7) JPEG法 (2)

前回に引き続き、JPEG 法のアルゴリズムを取り上げます。

前の章では、離散コサイン変換 ( DCT ) と YUV 変換・サンプリングを紹介しましたが、ここまでの変換ではまだサンプリングを除いてデータの圧縮を行なっていません。この章で、圧縮の方法について説明したいと思います。


1) 量子化

離散コサイン変換によって、画素ブロックは低周波領域 ( 左上側の方の成分 ) により多くの画像情報が集中する形でデータに偏りが生じます。高周波成分 ( 右下側 ) の値は情報量が少ないため、ある程度切り捨ててしまっても画質への影響はあまり大きくありません。また、人間の視覚は高周波成分の違いには鈍感で情報が切り捨てられた場合の違いにも気付きにくいので、左上側の低周波領域はあまり変化させず、逆に右下側の高周波領域の値を切り捨ててしまえば、見た目をそれほど変化させることなく圧縮率を上げることが可能になります。このような処理を量子化と言います。

量子化処理は非常に単純で、画素ブロックの各要素を定数で割り算するだけです。この定数は各要素によって決まっていますが、復元時に逆量子化 ( 各要素を定数で掛け算 ) する場合に同じ定数が用いられていれば、どんな値を使用しても問題はありません。量子化に使用されるデータを「量子化テーブル」と言いますが、画質を保ったまま圧縮率を上げるためには、左上側に対応する定数を小さく、右下側に対応するものは大きくした方が有利になり、量子化テーブルもそのようなデータ構成になっています。

表 1-1. 量子化テーブル (例)
輝度成分用
| 16  11  10  16  24  40  51  61 |
| 12  12  14  19  26  58  60  55 |
| 14  13  16  24  40  57  69  56 |
| 14  17  22  29  51  87  80  62 |
| 18  22  37  56  68 109 103  77 |
| 24  35  55  64  81 104 113  92 |
| 49  64  78  87 103 121 120 101 |
| 72  92  95  98 112 100 103  99 |

色差成分用
| 17  18  24  47  99  99  99  99 |
| 18  21  26  66  99  99  99  99 |
| 24  26  56  99  99  99  99  99 |
| 47  66  99  99  99  99  99  99 |
| 99  99  99  99  99  99  99  99 |
| 99  99  99  99  99  99  99  99 |
| 99  99  99  99  99  99  99  99 |
| 99  99  99  99  99  99  99  99 |

画素ブロックの各要素に対して、量子化テーブルの同じ行列にある要素を使って量子化・逆量子化するため、画素ブロックの各要素を S( u, v )、量子化テーブルの各要素を Q( u, v ) とすると、量子化・逆量子化の変換式は次のようになります。

量子化 : R( u, v ) = S( u, v ) / Q( u, v )

逆量子化 : S( u, v ) = R( u, v ) x Q( u, v )

ここで、量子化テーブルの要素をそのまま利用すると、圧縮率は高くなる代わりに画質は劣化しますが、定数で割って小さくすることによって、画質の劣化をある程度抑えることも可能です ( 当然圧縮率は下がります )。このように、この量子化処理では、画質と圧縮率をコントロールすることが可能になります。


量子化・逆量子化処理を行うためのサンプルプログラムを以下に示します。

/*
  JPEG_Quantize : 量子化用クラス
*/
class JPEG_Quantize
{
  unsigned int quality_; // 量子化レベル ( 0=量子化を行わない ; 1(最大)〜 )

public:

  // 量子化レベル quality を指定して構築
  JPEG_Quantize( unsigned int quality )
    : quality_( quality ) {}

  // 量子化ルーチン
  void quantize( Matrix< double >* mcu, const Matrix< unsigned char >& qTable );

  // 逆量子化ルーチン
  void invQuantize( Matrix< double >* mcu, const Matrix< unsigned char >& qTable );
};

/*
  MCUデータ列 mcu を量子化・逆量子化する
*/
template< class Op >
void QuantizeMain( Matrix< double >* mcu, const Matrix< unsigned char >& qTable, unsigned int quality, Op f )
{
  if ( quality == 0 ) return;

  assert( mcu != 0 && &qTable != 0 );

  Coord< int > sz = mcu->size();
  Coord< Matrix< unsigned char >::size_type > qSz = qTable.size();

  Coord< int > c;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      double rate = static_cast< double >( qTable( c.x % qSz.x, c.y % qSz.y ) ) / quality;
      if ( rate > 1 ) (*mcu)[c] = f( (*mcu)[c], rate );
    }
  }
}

/*
  MCUデータ列 mcu を量子化する
*/
void JPEG_Quantize::quantize( Matrix< double >* mcu, const Matrix< unsigned char >& qTable )
{ QuantizeMain( mcu, qTable, quality_, std::divides< double >() ); }

/*
  MCUデータ列 mcu を逆量子化する
*/
void JPEG_Quantize::invQuantize( Matrix< double >* mcu, const Matrix< unsigned char >& qTable )
{ QuantizeMain( mcu, qTable, quality_, std::multiplies< double >() ); }

処理そのものに難しい部分はありません。量子化・逆量子化処理は関数 QuantizeMain で行い、引数として離散コサイン変換後の MCU データ列 mcu と量子化テーブル qTable、画質・圧縮率をコントロールするための定数 quality、量子化・逆量子化を切り替える関数オブジェクト f がそれぞれ渡されます。なお、前回の離散コサイン変換において、MCU は個々に作成するのではなく一つの行列の中にまとめて保持していたため、量子化処理でもそのような状態であることを想定した処理としてあります。
量子化・逆量子化の違いは、量子化テーブルにある定数で各値を除算するか、もしくは乗算するかの部分しかありません。そのため、処理の流れは一つにまとめ、除算と乗算をそれぞれ関数オブジェクトで切り替えるようにしています。関数オブジェクトとして、STL(Standard Template Library) にある dividesmultiplies を利用しています。


2) 符号化 / 復号化

量子化が済んだらいよいよ符号化処理になります。JPEG 法では符号化処理にハフマン符号化を利用していますが、符号化の処理フローは直流成分 ( DC ) と交流成分 ( AC ) で異なっています。

DC の場合、各 MCU ブロック間の値の差を求め、その有効ビット数 ( SSSS ) を符号化します。データ列には、符号化した SSSS と、差のデータ SSSS ビット分が加えられることになります。差のデータそのものは符号化されないことに注意して下さい。以下に、その処理フローを示します。

  1. 前の MCU にある DC 成分との差を求める。但し、最初のブロックについては 0 との差を求める。
  2. 差の値の有効ビット数 ( SSSS ) を符号化してデータ列に加える。
  3. 差の値の下位 SSSS ビットをデータ列に加える。但し、差の値が負数の場合は 1 を引く必要がある。

ここで、三番目の処理の中に「差の値が負数の場合は 1 を引く」という部分があるのが不思議な気がしますが、これは差の値の有効ビット上にある最上位のビットに関係しています。通常、差の値が正数か負数かを判断する場合は最上位ビットを見ることになりますが、ここでは有効ビット数が制限されているために最上位ビットも切り捨てられてしまいます。一番簡単にできる方法として、正負を決めるビットを追加することで対処できるわけですが、JPEG アルゴリズムではこの符号ビット分まで節約するため、代わりに負数に対して 1 を引くことで正負の判別が可能なようにしています。と言うのも、こうすることによって、有効ビットの最上位ビットで正負が判別できるようになるからです。ここでは、SSSS = 2 の場合を例に説明します。

SSSS = 2 となる差の値は下表のようになります。

表 2-1. SSSS = 2 での差の表現
差の値signed char型(8bit)での 2 進数表現SSSS(=2)bitでの 2 進数表現
-31111110101
-21111111010
20000001010
30000001111

有効ビット数 ( = 2 ) より上位のビットは負数の場合全て 1、正数の場合は全て 0 になります。最上位ビットについてもそれに従うため正負の判定ができるわけですが、有効ビット数分のデータでは正負の判定ができません。そこで負数についてのみ 1 を引いてみます。

表 2-2. 負数について 1 を引いた結果 ( SSSS = 2 )
差の値2進数表現
-301→00
-210→01
210
311

負数の場合、有効ビット上の最上位ビットが全て 0 になり、逆に正数の場合は全て 1 になっています。これは SSSS がどの値になっても常に成り立ちます。というのも、ある SSSS に対する負数の最大値 ( 上記の例では 11111110 = -2 ) と正数の最小値 ( 上記の例では 00000010 = 2 ) は SSSS ビット数分だけ抽出した結果が等しく、必ず抽出後の最上位ビットが 1 でそれ以外は 0 になるからです ( 絶対値がその範囲より小さい数は全て、SSSS ビットより少ないビット数で表現できます )。この規則を利用して正負の判別ができるような工夫がされています。


ACDC よりも複雑な処理を行っています。ACMCU ブロックごとに符号化を行いますが、ブロックの右下に向かうほど量子化によりゼロの発生する確率が高くなるため、左上側から斜め方向にデータを読むことによりゼロ成分が連続して発生しやすいようにしています。これを「ジグザグ・スキャン」と言います。ジグザグ・スキャンでは、ブロックの左上隅 ( DC を除く ) を起点として、最初に左下方向へ進みながらデータを読み、端まで到達したら今度は右上方向へ進みながらデータを読みます ( 図 2-1 参照 )。このようにデータを読むことで、ゼロ成分が連続して出現することが期待できるため、符号化処理もそれにあった形で行われ、AC の場合はゼロでないデータが見つかったとき、それまでに発生したゼロ成分の個数 ( run ) と SSSS の組合せを符号化してデータ列に加えます。

ジグザグ・スキャンの様子
図 2-1. ジグザグ・スキャン

以下に、AC の処理フローを示します。

  1. AC をジグザグ・スキャンして、連続するゼロ成分を数えながらゼロでない成分を見つける。
  2. ゼロでない成分の SSSS を求める。
  3. ゼロ成分の個数 ( run ) と SSSS の組合せを符号化して、データ列に加える。
  4. ゼロでない成分の下位 SSSS ビットをデータ列に加える。但し、差の値が負数の場合は 1 を引く必要がある。
  5. 上記操作を、各 MCU ブロックごとに行う。

この処理フローにはさらに、いくつかの例外処理があります。

まず、最後の ( 右下隅の ) AC がゼロだった場合、その前にゼロ成分がいくつ続いていても、EOB ( End Of Block ) を出力して、そのブロックに対する処理を終了します。EOB として、SSSS = 0, run = 0 が割り当てられています。
また、run の値が 15 を越えた場合、run の値をリセットして ZRL ( Zero Run Length ) を出力します。ZRL として、SSSS = 0, run = 15 が割り当てられています。

JPEG 法では、DCAC ともにハフマン符号表が用意されています。DC では SSSS が 0 から 15 までの値に対して用意されているため、-32767 から 32767 までの値を符号化することができます。また AC では SSSS に対して 0 から 10 まで、run に対して 0 から 15 までの値が符号化できます。よって、符号化できる値は -1023 から 1023 までになります。

ハフマン符号表は、DCAC とも Y データと UV データで異なるものが用意されています。

AC が ±1023 までの値しか符号化できないのは、MCU ブロックの大きさが 8 x 8 ならばその範囲の値を越えないことが保証されているためです。証明するのは大変そうですが、実際に離散コサイン変換式を計算してみれば理解できます。以下の perl スクリプトを使って、離散コサイン変換結果の値の最大値として正の値のみの和を計算した結果を表に示します。

#!/usr/bin/perl -W

my $size = 8;           # 係数行列のサイズ
my $pi = atan2(1,1) *4; # π の値

for ( my $v = 0 ; $v < $size ; $v++ ) {
  for ( my $u = 0 ; $u < $size ; $u++ ) {
    my $max = 0; # 最大値
    my $min = 0; # 最小値
    for( my $y = 0 ; $y < $size ; $y++ ) {
      for( my $x = 0 ; $x < $size ; $x++ ) {
        my $value = 255.0 * cos( ( 2 * $y + 1 ) * $u / ( $size * 2 ) * $pi ) * cos( ( 2 * $x + 1 ) * $v / ( $size * 2 ) * $pi );
        $max += $value if $value > 0;
        $min += $value if $value < 0;
      }
    }
    $max /= sqrt( 2 ) if $u == 0;
    $max /= sqrt( 2 ) if $v == 0;
    $min /= sqrt( 2 ) if $u == 0;
    $min /= sqrt( 2 ) if $v == 0;
    printf( "( %.3f - %.3f )", $min * 2 / $size, $max * 2 / $size );
  }
  print "\n";
}

このスクリプトは、係数が正値なら 255、負値なら 0 を成分として最大値を、逆に係数が正値なら 0、負値なら 255 を成分として最小値を求めています。結果は、DC を除いて最大値と最小値の絶対値が等しくなり ( DC はゼロが最小値となります )、その絶対値は以下のような値になります ( UV 成分は -127.5 から 127.5 までの値をとりますが、AC については値は同じになります )。

表 2-3. MCU ブロックの最大値
u/v01234567
02040.00924.250942.357924.2501020.00924.250942.357924.250
1924.250837.488853.896837.488924.250837.488853.896837.488
2942.357853.896870.624853.896942.357853.896870.624853.896
3924.250837.488853.896837.488924.250837.488853.896837.488
41020.00924.250942.357924.2501020.00924.250942.357924.250
5924.250837.488853.896837.488924.250837.488853.896837.488
6942.357853.896870.624853.896942.357853.896870.624853.896
7924.250837.488853.896837.488924.250837.488853.896837.488

但し、これはあくまでも MCU の大きさが 8 である場合の話です。MCU のサイズを大きくすると、最大値と最小値もそれだけ大きくなります。そうなると、デフォルトのハフマン符号表では対応できなくなるため、新たに符号表を用意するか、プログラム内で作成し直す必要があります。


DC 成分の符号化及び復号化処理のサンプルプログラムを以下に示します。復号は符号化の逆処理になるので、サンプルを見れば処理の内容は簡単に理解できると思います。

// ハフマン符号の型
typedef unsigned int HuffmanCode;

// ハフマン符号長の型
typedef unsigned char HuffmanLen;

// ハフマン符号型変数の構成
struct HuffmanCodeType
{
  HuffmanCode code; // 符号
  HuffmanLen len;   // 符号長

  // コンストラクタ
  HuffmanCodeType( HuffmanCode c, HuffmanLen l )
  : code( c ), len( l ) {}
};

const HuffmanLen SSSS_SIZE = 16; // SSSS の最大値

/*
  RoundHalfUp : 浮動小数点型のデータ d を小数点以下四捨五入して整数型として返す
*/
int RoundHalfUp( double d )
{
  if ( d > 0 )
    d += 0.5;
  else
    d -= 0.5;

  return( static_cast< int >( d ) );
}

/*
  CalcSSSS : data からSSSSを求めて返す
*/
HuffmanLen CalcSSSS( int data )
{
  // int 型のビット数
  const unsigned int UINT_BIT = CHAR_BIT * sizeof( int );

  unsigned int i = UINT_BIT / 2;       // チェックするビット位置の初期値
  unsigned int gap = UINT_BIT / 4;     // 次の位置への増減分(二分探索用)

  if ( data < 0 ) data *= -1;

  // ビット位置がゼロになるまでチェック
  for ( ; ; ) {
    unsigned int upper = data >> i; // 上位ビット( i だけシフトした結果 )
    if ( upper == 0 ) {          // シフトしすぎ
      if ( i == 0 ) return( 0 ); // data = 0 なら SSSS もゼロ
      i -= gap;
    } else if ( upper > 1 ) {    // シフトが足りない
      i += gap;
    } else {                     // 最上位ビットが見つかった
      break;
    }
    if ( gap > 1 ) gap /= 2;     // 増減分を半分に
  }

  return( i + 1 );
}

/*
  DC_Encode : DC成分の符号化

  mcu : 符号化対象のMCUデータ列(個々のMCUが縦横に連続して並べられている)
  mcuSize : MCU一つのサイズ
  huffmanCode : ハフマン符号表
  encData : 符号化したデータ列を保持する配列へのポインタ
*/
void DC_Encode( const Matrix< double >& mcu, int mcuSize,
                const std::map< HuffmanLen, HuffmanCodeType >& huffmanCode,
                std::vector< HuffmanCode >* encData )
{
  int prev_dc = 0;               // 前のDC成分
  Coord< int > sz( mcu.size() ); // MCU全体のサイズ

  Coord< int > c;
  HuffmanCodeType cache( 0, 0 ); // ビット列書き込み用のキャッシュ
  for ( c.y = 0 ; c.y < sz.y ; c.y += mcuSize ) {
    for ( c.x = 0 ; c.x < sz.x ; c.x += mcuSize ) {
      int diff = RoundHalfUp( mcu[c] ) - prev_dc; // 前のDC成分との差
      HuffmanLen ssss = CalcSSSS( diff );         // diffのサイズからSSSSを取得する

      // SSSSに対応するハフマンコードの取得
      std::map< HuffmanLen, HuffmanCodeType >::const_iterator cit = huffmanCode.find( ssss );
      if ( cit == huffmanCode.end() )
        throw std::domain_error( "DC_Encode : Failed to find huffman code." );

      // 符号の書き込み
      WriteToArray( ( cit->second ).code, ( cit->second ).len, &( cache.code ), &( cache.len ), encData );

      // 差の値の符号化
      if ( diff < 0 ) diff -= 1; // 負の場合は1を引く
      if ( ssss > 0 ) {
        unsigned int buff = diff;
        buff &= ~( UINT_MAX << ssss );
        WriteToArray( buff, ssss, &( cache.code ), &( cache.len ), encData );
      }
      prev_dc = RoundHalfUp( mcu[c] );
    }
  }

  // キャッシュの残りを書き込む
  if ( cache.len > 0 )
    encData->push_back( cache.code << ( HUFFMAN_CODE_BIT - cache.len ) );
}

/*
  DC_Decode : DC成分の展開

  mcu はあらかじめ必要なサイズにリサイズされているものとする

  cit : 符号化データ列への反復子のポインタ
  encEnd : 符号化データ列の末尾の次の反復子
  huffmanCode : ハフマン符号表
  mcu : 展開したDC成分を書き込む行列へのポインタ
  mcuSize : MCU一つのサイズ
*/
void DC_Decode( std::vector< HuffmanCode >::const_iterator* cit, std::vector< HuffmanCode >::const_iterator encEnd,
                const std::map< HuffmanLen, HuffmanCodeType >& huffmanCode, Matrix< double >* mcu, int mcuSize )
{
  int prev_dc = 0;     // 前のDC成分
  HuffmanLen ssss = 0; // データ列から取得するSSSS
  Coord< int > sz( mcu->size() ); // MCU全体のサイズ

  // ハフマン符号からハフマン木を生成
  std::vector< HuffmanTreeNode< HuffmanLen > > huffmanTree;
  MakeTreeFromHuffmanCode( huffmanCode, &huffmanTree );

  Coord< int > c;
  HuffmanCodeType cache( 0, 0 ); // ビット列書き込み用のキャッシュ
  for ( c.y = 0 ; c.y < sz.y ; c.y += mcuSize ) {
    for ( c.x = 0 ; c.x < sz.x ; c.x += mcuSize ) {
      // ハフマン木からSSSSを読み込む
      if ( ! ReadFromTree( huffmanTree, 0, cit, encEnd, &ssss, &cache ) == huffmanTree.max_size() )
        throw std::domain_error( "DC_Decode : Failed to read huffman tree for DC." );

      if ( ssss > 0 ) {
        // 差分をデータ列から読み込む
        unsigned int buff = 0; // ビット列を読み込むバッファ
        if ( ! ReadFromArray( cit, encEnd, &( cache.code ), &( cache.len ), &buff, ssss ) )
          throw std::domain_error( "DC_Decode : Failed to read from array for DC." );

        // 最上位ビットがゼロの場合、負の数であることを示す
        if ( ( ( buff >> ( ssss - 1 ) ) & 1 ) == 0 ) {
          buff |= UINT_MAX << ssss;
          ++buff;
        }
        prev_dc += static_cast< int >( buff );
      }
      (*mcu)[c] = prev_dc;
    }
  }
}

プログラム内で使用されている関数 WriteToArray は、データとその長さを引数として受け取り、符号化データ列にその内容を書き込むためのもので、ReadFromArray は逆に取り出すために使用します。また、MakeTreeFromHuffmanCode はハフマン符号表からハフマン木を構築するための関数、ReadFromTree は構築したハフマン木をたどり、末端に達したらその値を返す関数です。WriteToArrayReadFromArray は、「圧縮アルゴリズム (4) ハフマン符号化 - 適応型ハフマン圧縮」のサンプル・プログラムで、MakeTreeFromHuffmanCodeReadFromTree は「圧縮アルゴリズム (3) ハフマン符号化 - 静的ハフマン圧縮」の中でそれぞれ紹介してあります。

符号化・復号化のいずれにおいても、ハフマン符号列は STL(Standard Template Library) にあるコンテナ・クラス map を使い、SSSS をキー、それに対応するハフマン符号を値として渡しています。ハフマン符号表が固定ならばハフマン木も固定になるので、最初からハフマン木の形で符号を用意しておいて、そこから符号を直接検索するような方式にすることもできます。また、ハフマン符号を画像ごとに作成しなおすのであれば、符号を正規化したり、適応型ハフマン符号化を採用することで符号列のサイズを小さくする(もしくは符号列そのものを保持しない)ような工夫も可能です。


次は AC 成分の符号化・復号化処理を行うためのサンプル・プログラムです。

const HuffmanLen RUN_SIZE = 16;  // run の最大値

const HuffmanLen EOB = 0;              // EOB : run = 0, SSSS = 0
const HuffmanLen ZRL = 15 * SSSS_SIZE; // ZRL : run = 15, SSSS = 0

/*
  ZigzagRun : ジグザグスキャン

  c : 更新対象の座標へのポインタ
  d : 更新方向(増分)へのポインタ

  戻り値 すでに末尾に達していたら false を返す
*/
bool ZigzagRun( Coord< int >* c, Coord< int >* d, int mcuSize )
{
  if ( c->x == mcuSize - 1 && c->y == mcuSize - 1 )
    return( false );

  c->x += d->x;
  c->y += d->y;
  if ( c->x < 0 || c->x >= mcuSize || c->y < 0 || c->y >= mcuSize ) {
    d->x *= -1;
    d->y *= -1;
    if ( c->x < 0 ) {
      if ( c->y >= mcuSize ) {
        c->x = 1;
        c->y = mcuSize - 1;
      } else {
        c->x = 0;
      }
    } else if ( c->x >= mcuSize ) {
      c->x = mcuSize - 1;
      c->y += 2;
    } else if ( c->y < 0 ) {
      c->y = 0;
    } else {
      c->x += 2;
      c->y = mcuSize - 1;
    }
  }

  return( true );
}

/*
  AC_MCU_Encode : AC成分のエンコード(ひとつのMCU成分を処理)

  mcu : 符号化対象のMCUデータ列(個々のMCUが縦横に連続して並べられている)
  mcuSize : MCU一つのサイズ
  mcuCoord : 対象のMCUの符号化開始位置(左上位置)
  huffmanCode : ハフマン符号表
  encData : 符号化データ列へのポインタ
  cache : データ列書き込み用のキャッシュ
*/
void AC_MCU_Encode
( const Matrix< double >& mcu, int mcuSize, const Coord< int >& mcuCoord,
  const std::map< HuffmanLen, HuffmanCodeType >& huffmanCode,
  std::vector< HuffmanCode >* encData, HuffmanCodeType* cache )
{
  // ハフマン符号表用反復子の型
  typedef std::map< HuffmanLen, HuffmanCodeType >::const_iterator HC_CIt;

  HuffmanLen run = 0; // ゼロが連続した回数
  HuffmanLen zrl_count = 0; // ZRLを出力する回数

  HC_CIt zrl = huffmanCode.find( ZRL ); // ZRL用符号の位置

  Coord< int > c( 1, 0 );  // MCU内の座標位置
  Coord< int > d( -1, 1 ); // 座標の増分(左下向きからスタート)

  do {
    int ac = RoundHalfUp( mcu( mcuCoord.x + c.x, mcuCoord.y + c.y ) );
    if ( ac == 0 ) {
      // ゼロ成分の時は、run を 1 増加
      if ( ++run >= RUN_SIZE ) {
        // run が RUN_SIZE を越えたら ZRL を出力
        ++zrl_count;
        run -= RUN_SIZE;
      }
    } else {
      // 最初に ZRL を出力
      for ( HuffmanLen i = 0 ; i < zrl_count ; ++i ) {
        if ( zrl == huffmanCode.end() )
          throw std::domain_error( "AC_MCU_Encode : Failed to find huffman code ZRL." );
        WriteToArray( ( zrl->second ).code, ( zrl->second ).len, &( cache->code ), &( cache->len ), encData );
      }
      HuffmanLen ssss = CalcSSSS( ac ); // ac のサイズから SSSS を求める

      // runとssssの組合せを符号化
      HC_CIt cit = huffmanCode.find( run * SSSS_SIZE + ssss );
      if ( cit == huffmanCode.end() )
        throw std::domain_error( "AC_MCU_Encode : Failed to find huffman code RUN+SSSS." );
      WriteToArray( ( cit->second ).code, ( cit->second ).len, &( cache->code ), &( cache->len ), encData );

      // AC成分を符号化して書き込む
      if ( ac < 0 ) ac -= 1; // 負の場合は1を引く
      unsigned int buff = ac;
      buff &= ~( UINT_MAX << ssss );
      WriteToArray( buff, ssss, &( cache->code ), &( cache->len ), encData );

      run = zrl_count = 0;
    }
  } while ( ZigzagRun( &c, &d, mcuSize ) );

  // ゼロ成分が連続したまま最後に達した場合、EOBを出力
  if ( run != 0 || zrl_count != 0 ) {
    HC_CIt cit = huffmanCode.find( EOB );
    if ( cit == huffmanCode.end() )
      throw std::domain_error( "AC_MCU_Encode : Failed to find huffman code EOB." );
    WriteToArray( ( cit->second ).code, ( cit->second ).len, &( cache->code ), &( cache->len ), encData );
  }
}

/*
  AC_Encode : AC成分のエンコード

  mcu : 符号化対象のMCUデータ列(個々のMCUが縦横に連続して並べられている)
  mcuSize : MCU一つのサイズ
  huffmanCode : ハフマン符号表
  encData : 符号化データ列へのポインタ
*/
void AC_Encode
( const Matrix< double >& mcu, int mcuSize,
  const std::map< HuffmanLen, HuffmanCodeType >& huffmanCode,
  std::vector< HuffmanCode >* encData )
{
  // MCU全体のサイズ
  Coord< int > sz = mcu.size();
  if ( sz.x % mcuSize != 0 || sz.y % mcuSize != 0 )
    throw std::domain_error( "AC_Encode : Matrix size must be dividable by one MCU size" );

  Coord< int > c;
  HuffmanCodeType cache( 0, 0 ); // データ列書き込み用のキャッシュ
  for ( c.y = 0 ; c.y < sz.y ; c.y += mcuSize )
    for ( c.x = 0 ; c.x < sz.x ; c.x += mcuSize )
      AC_MCU_Encode( mcu, mcuSize, c, huffmanCode, encData, &cache );

  // キャッシュの残りを書き込む
  if ( cache.len > 0 )
    encData->push_back( cache.code << ( HUFFMAN_CODE_BIT - cache.len ) );
}

/*
  AC_MCU_Decode : AC成分のデコード(ひとつのMCU成分を処理)

  mcu はあらかじめ必要なサイズにリサイズされているものとする

  cit : 符号化データ列への反復子のポインタ
  encEnd : 符号化データ列の末尾の次の反復子
  huffmanTree : ハフマン木
  mcu : 展開したAC成分を書き込む行列へのポインタ
  mcuSize : MCU一つのサイズ
  mcuCoord : 対象のMCUの符号化開始位置(左上位置)
  cache : データ列書き込み用のキャッシュ
*/
void AC_MCU_Decode
( std::vector< HuffmanCode >::const_iterator* cit, std::vector< HuffmanCode >::const_iterator encEnd,
  const std::vector< HuffmanTreeNode< HuffmanLen > >& huffmanTree,
  Matrix< double >* mcu, int mcuSize, const Coord< int >& mcuCoord, HuffmanCodeType* cache )
{
  Coord< int > c( 1, 0 );  // MCU内の座標位置
  Coord< int > d( -1, 1 ); // 座標の増分(左下向きからスタート)
  bool isEnd = false;      // 最後のAC成分まで読み終えたか

  HuffmanLen ssssRun; // SSSSとRUNの組み合わせ
  unsigned int buff;  // 読み込み用バッファ

  do {
    // ハフマン木からSSSSとrunを抽出する
    if ( ! ReadFromTree( huffmanTree, 0, cit, encEnd, &ssssRun, cache ) == huffmanTree.max_size() )
      throw std::domain_error( "AC_MCU_Decpde : Failed to read from huffman tree." );

    if ( ssssRun == EOB ) {
      // EOB なら以降は全てゼロを書き込む
      do {
        (*mcu)( mcuCoord.x + c.x, mcuCoord.y + c.y ) = 0;
      } while ( ZigzagRun( &c, &d, mcuSize ) );
      break;
    } else if ( ssssRun == ZRL ) {
      // ZRL なら RUN_SIZE 分のゼロを書き込む
      for ( HuffmanLen i = 0 ; i < RUN_SIZE ; i++ ) {
        (*mcu)( mcuCoord.x + c.x, mcuCoord.y + c.y ) = 0;
        isEnd = ZigzagRun( &c, &d, mcuSize );
      }
    } else {
      // run と SSSS に分解
      HuffmanLen run = ssssRun / SSSS_SIZE;
      HuffmanLen ssss = ssssRun % SSSS_SIZE;

      // run の数だけゼロを書き込む
      for ( HuffmanLen i = 0 ; i < run ; i++ ) {
        (*mcu)( mcuCoord.x + c.x, mcuCoord.y + c.y ) = 0;
        ZigzagRun( &c, &d, mcuSize );
      }

      // AC成分の読み込み
      if ( ! ReadFromArray( cit, encEnd, &( cache->code ), &( cache->len ), &buff, ssss ) )
        throw std::domain_error( "AC_MCU_Decpde : Failed to read SSSS from array." );

      // 最上位ビットがゼロの場合、負の数であることを示す
      if ( ( ( buff >> ( ssss - 1 ) ) & 1 ) == 0 ) {
        buff |= UINT_MAX << ssss;
        ++buff;
      }
      (*mcu)( mcuCoord.x + c.x, mcuCoord.y + c.y ) = static_cast< int >( buff );
      isEnd = ZigzagRun( &c, &d, mcuSize );
    }
  } while ( isEnd );
}

/*
  AC_Decode : AC成分のデコード

  mcu はあらかじめ必要なサイズにリサイズされているものとする

  cit : 符号化データ列への反復子のポインタ
  encEnd : 符号化データ列の末尾の次の反復子
  huffmanCode : ハフマン符号表
  mcu : 展開したAC成分を書き込む行列へのポインタ
  mcuSize : MCU一つのサイズ
*/
void AC_Decode( std::vector< HuffmanCode >::const_iterator* cit, std::vector< HuffmanCode >::const_iterator encEnd,
                const std::map< HuffmanLen, HuffmanCodeType >& huffmanCode, Matrix< double >* mcu, int mcuSize )
{
  Coord< int > sz( mcu->size() ); // MCU全体のサイズ
  if ( sz.x % mcuSize != 0 || sz.y % mcuSize != 0 )
    throw std::domain_error( "AC_Decode : Matrix size must be dividable by one MCU size" );

  // ハフマン符号表からハフマン木を作成
  std::vector< HuffmanTreeNode< HuffmanLen > > huffmanTree;
  MakeTreeFromHuffmanCode( huffmanCode, &huffmanTree );

  Coord< int > c;
  HuffmanCodeType cache( 0, 0 ); // データ列書き込み用のキャッシュ
  for ( c.y = 0 ; c.y < sz.y ; c.y += mcuSize )
    for ( c.x = 0 ; c.x < sz.x ; c.x += mcuSize )
      AC_MCU_Decode( cit, encEnd, huffmanTree, mcu, mcuSize, c, &cache );
}

AC 成分は MCU ブロックごとに符号化処理を行うため、ブロック単位で処理するための関数として AC_MCU_EncodeAC_MCU_Decode が用意され、メイン・ルーチンとなる AC_EncodeAC_Decode はそれらを呼び出す形で作成されています。また、データの走査方法が複雑なため、走査専用のルーチンとして ZigzagRun を用意しています。符号化処理では、ゼロ以外の成分が見つかるまでの間、変数 run を使ってゼロが続く個数をカウントします。また、そのカウントが RUN_SIZE を超えたら、ZRL 符号出力用のカウンタ zrl_count をインクリメントして run はリセットします。ゼロ以外の成分が見つかったら、最初に ZRL 符号を zrl_count 分出力し、それから成分を符号化します。前述の通り、runSSSS の組み合わせをキーにハフマン符号を決めて出力し、そのあと成分そのものを SSSS サイズ分だけ出力します。MCU 内の全ての値を読み込んだ後、最後までゼロが続いていた場合は run または zrl_count のいずれかがゼロ以外となるので、EOB を符号化して出力します。復号化は、ちょうどこれと反対の処理を行なっているだけです。


3) 性能評価

サンプル・プログラムを使って符号化を行った結果を以下に示します。テストに使用した画像は前回と同じ "Lenna" (図 3-1) です ( 実際には 512 x 512 のサイズです )。

図 3-1. テスト画像 (Lenna)
Lenna

まずは量子化による圧縮率・画質への影響をテストしてみます。量子化をしない場合と、Quality を「1 (最も強い)」から「10 (量子化の強さを 1 / 10 に)」まで 3 段階で量子化した結果を以下に示します。ハフマン符号は「固定」とし、MCU のサイズもデフォルトの 8 としています。

表 3-1. 量子化と圧縮率の関係
量子化(Quality)符号サイズ
(Bytes)
圧縮率
(%)
なし44864057.05
1015807620.10
59275211.79
1303283.856
 
図 3-2. 量子化処理による画像の変化 (クリックで元のサイズの画像が見られます)
Quality = 10Quality = 5Quality = 1
Quality=10 Quality=5 Quality=1

量子化による圧縮率への効果はかなり大きく、「量子化なし」で半分強にしか圧縮できないのに対して最も強い量子化なら 5 % 以下とかなり圧縮することができます。このサンプル画像は自然画に属しますが、画質についても両者を並べて比較しない限りは劣化の度合いもわからないと思います。

次に、MCU のサイズに対する圧縮率の変化を以下に示します。量子化は行わず、ハフマン符号は全て再構築しています。

表 3-2. MCU のサイズと圧縮率の関係
MCU サイズ符号サイズ(Bytes)圧縮率(%)
247577260.50
442558854.12
840502851.50
1640062450.94
3240249651.18
6440858851.95
12841808053.16
25642446053.97
51242913254.57

MCU のサイズを大きくすればゼロになる成分も多くなり、圧縮率も向上するのではないかと思いましたが、実際には MCU のサイズが 16 のときが最も圧縮率が高く、それ以上大きくしてもかえって圧縮率が低くなるという結果になりました。MCU のサイズを大きくすると離散コサイン変換による値の幅は大きくなるので、ハフマン符号化の効率がかえって悪くなるのではないかと推測します。量子化に比べれば圧縮率への影響は小さいので、処理時間を考慮するとサイズはある程度小さい方が効率はよさそうです。なお、当然のことですが、MCU のサイズが 8 の場合での圧縮率はハフマン木を再構築した場合の方がよくなります。

LZ 法までに利用していたサンプル画像がほとんどが JPEG 形式の画像だったので、今回はアニメ調の GIF 画像のみを使って符号化をしてみます。その結果は以下のようになります。表の中には、「圧縮アルゴリズム (5) LZ法」で同じ画像に対して符号化を行った時の結果を併せて示してあります。LZ77 法については、対象の画像について最も圧縮率の高かった、符号サイズ 32bit (位置 16bit, 長さ 16bit) での結果になります。

表 3-3. JPEG 符号化による圧縮率 (「アニメ」調 GIF 画像 )
量子化なし量子化あり(Quality=10)量子化あり(Quality=1)LZW 符号化LZ77 符号化
符号サイズ
(Bytes)
圧縮率
(%)
符号サイズ
(Bytes)
圧縮率
(%)
符号サイズ
(Bytes)
圧縮率
(%)
符号サイズ
(Bytes)
圧縮率
(%)
符号サイズ
(Bytes)
圧縮率
(%)
44179618.732262049.588755283.201837843.551805283.413
60578425.6825964011.01780843.31024908010.5633294414.11
28473612.071496086.341607162.573795043.370797483.380
54979623.3026969211.43893723.7881574726.6751756127.443
43063218.252047208.677654962.776858803.640864803.666
25884410.97933403.956376881.597736243.121795803.373
1658047.0281020164.324478322.027756483.206815843.458
34760814.731709327.245682002.8911183125.0151573926.671
48525620.572315569.815726323.0791698407.1992067168.762
50672021.482257969.570664402.8161269685.3821197085.074

LZ77LZW での結果と比較すると、圧縮率はそれほどよくはありません。量子化を行うと圧縮率は高くなりますが、Quality = 1 にすると画像の劣化がかなり目立つようになります。アニメ調画像は単色での塗りつぶしが多いため、塗りつぶしの境界(エッジ)部分に「モスキート・ノイズ (Mosquito Noise)」と呼ばれるノイズが特に顕著になります。JPEG 法は、高周波領域の成分が小さいことを想定して圧縮しているの対し、アニメ調の画像のように境界がはっきりしている場合は高周波領域を無視することができなくなります。これが、JPEG 法がアニメ調画像には弱いと言われている理由になります。下図は、Quality = 1 の条件でテストした画像の一部を切り取って拡大したもので、左側が処理前、右側が処理後になります。処理後の画像において、モヤのかかったようなノイズが顕著に見られますが、これが蚊の大群が群がった様子に見えることからモスキート・ノイズという名で呼ばれています。

図 3-3. モスキート・ノイズの例
モスキート・ノイズ

JPEG 法が誕生してからすでにかなりの年月が経過しているのにもかかわらず、今でも主要な画像圧縮法として利用されています。そのアルゴリズムを調べてみると、細かいところまでよく考えられているなという印象を受けます。当初は処理の重い画像形式という認識がありましたが、処理の高速化に加えて CPU の性能も向上したことから、今ではどちらかというと処理の速いアルゴリズムの部類に入るのではないでしょうか。まだしばらくは JPEG フォーマットが利用され続けるのではないかと思います。


過去に作成したサンプル・プログラムにはいくつかバグがあり、正常に画像が復元できない場合が頻発していたので、致命的なバグを取り除いたソース・コードを再度アップロードしました。御自由にお使い下さい (過去のソース・コードなので C++ ではなく C で書かれています)。

サンプルでは gtk+-2.0 を利用しています。動作確認は VirtualBox 上の Vine Linux 6.3 (x86_64) 上で行いました。Gtk+のバージョンは 2.24 になります。

<参考文献>
  1. インターフェース 1991年12月号 「画像データ圧縮の理解と応用」
  2. JPEG File Interchange Format Version 1.02 (pdf)
  3. Wikipedia

[Go Back]前に戻る [Back to HOME]タイトルに戻る
inserted by FC2 system