圧縮アルゴリズム

(1) ランレングス法

この章から新たに、データや画像などを圧縮するためのアルゴリズムを紹介します。まずは、もっとも古典的でシンプルな「ランレングス(連長)法」について説明します。

1) ランレングス法 (連長法)

FAX で送られる画像のような白色と黒色のみで構成された画像 ( 二値画像 ) や、色の変化が少ないアニメなどの画像は、隣り合ったピクセルの色の変化が少なく、値が連続して出現する傾向があります。この冗長性を利用して「同じ色が連続する長さ」を符号化する方法が「ランレングス(連長)法 ( Run Length Encoding ; RLE )」です。

例えば、次のような 10 x 10 ピクセルの二値画像の場合

□■□□■□□■□□
□■■□□■□■□□
□■■■□□■■□□
□■■■■□□■□□
□■■■■■□■□□
□■■■■■■■□□
□■■■■□□■□□
□■■■□□■■□□
□■■□□■■■□□
□■□□■■■■□□

二値画像は白と黒が必ず交互に現れるので、はじめの色がどちらなのかを保持しておけば、連続するピクセル数の情報だけあれば復元が可能になります。ライン右端のピクセルはその下のラインの左端とつながっていると考えた場合、上の例では

1,1,2,1,2,1,3,
2,2,1,1,1,3,
3,2,2,3,
4,2,1,3,
5,1,1,3,
7,3,
4,2,1,3,
3,2,2,3,
2,2,3,3,
1,2,4,2

となり、100 ピクセルの情報を 43 個の数字に変換することができます。もちろん、二値画像の場合 1 ピクセルは 1 ビットで表せるため、これでは圧縮になりませんが ( ピクセル数を 1 byte で表す場合 : 43 bytes、1 ピクセルを 1 ビットで表した場合 : 13 bytes )、ピクセル数が大きくなり、さらに FAX で送受信する画像のように白地の部分が多くなると、この方法を利用するだけでもかなりの圧縮が期待できます。

多値画像の場合は、その色コードも保持しておく必要があります。次のような、0 から 255 までの色コードを持った 10 x 10 ピクセルの多値画像では

[255][255][255][255][255][255][255][255][255][255]
[255][100][100][100][100][100][100][100][100][255]
[255][100][255][255][255][255][255][255][100][255]
[255][100][255][100][100][100][100][255][100][255]
[255][100][255][255][100][100][255][255][100][255]
[255][100][255][255][100][100][255][255][100][255]
[255][100][255][100][100][100][100][255][100][255]
[255][100][255][255][255][255][255][255][100][255]
[255][100][100][100][100][100][100][100][100][255]
[255][255][255][255][255][255][255][255][255][255]

次のように変換されます

255,11,
100,8,255,2,
100,1,255,6,100,1,255,2,
100,1,255,1,100,4,255,1,100,1,255,2,
100,1,255,2,100,2,255,2,100,1,255,2,
100,1,255,2,100,2,255,2,100,1,255,2,
100,1,255,1,100,4,255,1,100,1,255,2,
100,1,255,6,100,1,255,2,
100,8,255,11

この場合、100 ピクセルの画像を 74 個からなる 255 以下の数値に変換したことになり、74% の圧縮比になります。

ランレングス法を使った画像の圧縮プログラムを以下に示します。

/**********************************************
 DrawingArea_IF : 描画用オブジェクト用基底クラス
**********************************************/
class DrawingArea_IF
{
public:

  // 指定した座標のパレットを取得する
  virtual bool point( Coord<int> c, RGB& palet ) const = 0;

  // 指定した座標にドットを描画する
  virtual bool pset( Coord<int> c, const RGB& palet ) = 0;

  // 画像サイズを返す
  virtual Coord<int> size() const = 0;

  // 画像サイズを変更する
  virtual void resize( const Coord<int>& sz ) = 0;

  // 仮想デストラクタ
  virtual ~DrawingArea_IF() {}
};

/*****************************
  RGB : RGB成分用パレットクラス
*****************************/
class RGB
{
  :

public:

  // RGB 成分を返す
  unsigned char r() const;
  unsigned char g() const;
  unsigned char b() const;

  // RGB 成分をまとめて取得する
  void get( unsigned char& r, unsigned char& g, unsigned char& b );

  // RGB 成分をセットする
  void set( unsigned char r, unsigned char g, unsigned char b );
};

/*******************************************
  RGB_Eq_Base : RGB要素の等値判定用基底クラス
*******************************************/
class RGB_Eq_Base
{
 public:

  // 等値判定用関数 (純粋仮想関数)
  virtual bool operator()( const RGB& rgb1, const RGB& rgb2 ) const = 0;

  // 仮想コンストラクタ
  virtual ~RGB_Eq_Base() {}
};

/**********************************
  RGB_Eq : RGB要素が正確に一致するか
**********************************/
class RGB_Eq : public RGB_Eq_Base
{
 public:

  // 等値判定用関数
  virtual bool operator()( const RGB& rgb1, const RGB& rgb2 ) const
  { return( rgb1.r() == rgb2.r() && rgb1.g() == rgb2.g() && rgb1.b() == rgb2.b() ); }
};

/*
  PushRGB : RGB 成分をまとめて unsigned char 型配列へ追加する

  const RGB& palet : 対象の RGB 成分
  vector<unsigned char>& buffer : データを保持するバッファ
*/
void PushRGB( const RGB& palet, vector<unsigned char>& buffer )
{
  buffer.push_back( palet.r() );
  buffer.push_back( palet.g() );
  buffer.push_back( palet.b() );
}

/*
  PopRGB : unsigned char 型配列から RGB 成分の一つを抽出する

  vector<unsigned char>::const_iterator& it : データを取り出す配列の反復子
  vector<unsigned char>::const_iterator e : 配列の終端の反復子
  unsigned char& palet : 抽出した RGB 成分の一つ

  戻り値 : true ... 抽出成功 ; false ... 配列の終端に達した
*/
bool PopRGB( vector<unsigned char>::const_iterator& it, vector<unsigned char>::const_iterator e, unsigned char& palet )
{
  if ( it == e ) return( false );
  palet = *it++;

  return( true );
}

/*
  PopRGB : unsigned char 型配列から RGB 成分を抽出する
           RGB の順に並んでいることを前提とする

  vector<unsigned char>::const_iterator& it : データを取り出す配列の反復子
  vector<unsigned char>::const_iterator e : 配列の終端の反復子
  RGB& palet : 抽出した RGB 成分

  戻り値 : true ... 抽出成功 ; false ... 配列の終端に達した
*/
bool PopRGB( vector<unsigned char>::const_iterator& it, vector<unsigned char>::const_iterator e, RGB& palet )
{
  unsigned char r, g, b;

  if ( ! PopRGB( it, e, r ) ) return( false );
  if ( ! PopRGB( it, e, g ) ) return( false );
  if ( ! PopRGB( it, e, b ) ) return( false );

  palet.set( r, g, b );

  return( true );
}

/*
  WriteCoordToCharArray : int型の座標値をunsigned char型配列に登録する

  const Coord<int>& coord : 登録する座標
  vector<unsigned char>& buffer : 登録先の配列
*/
void WriteCoordToCharArray( const Coord<int>& coord, vector<unsigned char>& buffer )
{
  unsigned int intSz = sizeof( coord.x ) / sizeof( char ); // int 型のサイズ

  // 上位側から順に書き込む
  for ( unsigned int i = intSz ; i > 0 ; --i ) {
    unsigned char c = ( coord.x >> ( i - 1 ) * CHAR_BIT ) & UCHAR_MAX;
    buffer.push_back( c );
  }
  for ( unsigned int i = intSz ; i > 0 ; --i ) {
    unsigned char c = ( coord.y >> ( i - 1 ) * CHAR_BIT ) & UCHAR_MAX;
    buffer.push_back( c );
  }
}

/*
  ReadCoordFromCharArray : int型の座標値をunsigned char型配列から取り出す

  vector<unsigned char>::const_iterator& it : 座標を取り出す配列の反復子
  vector<unsigned char>::const_iterator e : 配列の終端の反復子
  Coord<int>& coord : 抽出した座標値

  戻り値 : true ... 抽出成功 ; false ... 配列の終端に達した
*/
bool ReadCoordFromCharArray( vector<unsigned char>::const_iterator& it, vector<unsigned char>::const_iterator e, Coord<int>& coord )
{
  unsigned int intSz = sizeof( coord.x ) / sizeof( char ); // int 型のサイズ

  // 上位側から順に登録されていることを前提
  for ( unsigned int i = intSz ; i > 0 ; --i ) {
    if ( it == e ) return( false );
    coord.x |= ( *it++ << ( i - 1 ) * CHAR_BIT );
  }
  for ( unsigned int i = intSz ; i > 0 ; --i ) {
    if ( it == e ) return( false );
    coord.y |= ( *it++ << ( i - 1 ) * CHAR_BIT );
  }

  return( true );
}

/*
  RLE_Pack : ランレングス法による圧縮(RGBまとめて圧縮)

  const DrawingArea_IF& draw : 描画オブジェクト
  vector<unsigned char>& buff : 圧縮データを保持するバッファ
  const RGB_Eq_Base& eq : RGB成分等値判定用関数オブジェクト
*/
void RLE_Pack( const DrawingArea_IF& draw, vector<unsigned char>& buff, const RGB_Eq_Base& eq )
{
  Coord<int> sz = draw.size(); // 画像サイズ
  buff.clear();

  // バッファの先頭に画像サイズを書き込む
  WriteCoordToCharArray( sz, buff );

  // 現在の色コードは読込開始ピクセル(左上)の色コードで初期化して
  // バッファに登録
  RGB curPalet;
  draw.point( Coord<int>( 0, 0 ), curPalet );
  PushRGB( curPalet, buff );

  unsigned char count = 0; // 同じ色コードが連続した回数
  RGB palet; // 次のピクセルの色コード取得用

  Coord<int> c;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.point( c, palet );

      if ( ! eq( palet, curPalet ) ) {
        buff.push_back( count );
        // count が UCHAR_MAX と等しい場合、次のカウンタはゼロとしておく
        if ( count == UCHAR_MAX ) buff.push_back( 0 );
        PushRGB( palet, buff );
        curPalet = palet;
        count = 0;
      }

      // count を 1 つ増加し、最大値に達したらいったんバッファに登録
      if ( ++count == UCHAR_MAX ) {
        buff.push_back( count );
        count = 0;
      }
    }
  }
  // 最後のカウント結果を登録
  buff.push_back( count );
}

/*
  RLE_Unpack : ランレングス法による伸長(RGBまとめて伸長)

  const vector<unsigned char>& buff : 圧縮データを保持するバッファ
  DrawingArea_IF& draw : 描画オブジェクト
*/
void RLE_Unpack( const vector<unsigned char>& buff, DrawingArea_IF& draw )
{
  Coord<int> sz( 0, 0 ); // 画像サイズ
  vector<unsigned char>::const_iterator it = buff.begin(); // バッファの現在位置

  // buff の先頭から画像サイズを読み込んで画像をリサイズ
  if ( ! ReadCoordFromCharArray( it, buff.end(), sz ) ) return;
  draw.resize( sz );

  RGB palet; // 次のピクセルの色コード取得用
  if ( ! PopRGB( it, buff.end(), palet ) ) return;
  if ( it == buff.end() ) return;

  unsigned char count = *it++;  // 連続した同色ピクセルの個数
  unsigned char iniCnt = count; // count の初期値

  Coord<int> c;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.pset( c, palet );
      if ( --count > 0 ) continue;
      // カウンタがゼロになったら次の色コードをバッファから取得
      // 但しカウンタの初期値が UCHAR_MAX ならカウンタのみ初期化
      do {
        if ( iniCnt != UCHAR_MAX )
          if ( ! PopRGB( it, buff.end(), palet ) ) return;
        if ( it == buff.end() ) return;
        iniCnt = count = *it++;
      } while ( count == 0 ); // カウンタがゼロなら読み直し
    }
  }
}

このサンプル・プログラムは、RGB と DrawingArea_IF という二つのクラスがあることを前提としています。RGB クラスは色コードの RGB 成分を保持するためのもので、r(), g(), b() 各メンバ関数によって RGB それぞれの成分を返す他、メンバ関数 get, set によって RGB 成分をまとめて取得・セットすることができます。これは構造体として用意するだけでも充分で、get, set もヘルパ関数としてクラスの外側に実装しても問題はありません。これは少々凝り過ぎのような気もします。
DrawingArea_IF は描画そのものを行うためのクラスで、画像サイズを返す size、画像サイズを変更する resize、描画用の pset、色コードを取得するための point という 4 つのメンバ関数を持ちます。実際の DrawingArea_IF はインターフェースのみを定義した抽象クラスで、環境に応じて異なる描画対象が利用できるようにしています。
この他、Coord は座標を表すために利用する構造体ですが、テンプレートを使って座標値の型を任意に切り替えることができます。

RGB 成分どうしの比較は、関数オブジェクト用のクラス RGB_Eq を利用して行なっています。このクラスは RGB_Eq_Base から派生したもので、比較方法を切り替えることができるようになっています。具体的な利用法についてはこの章の最後の方で説明します。

RGB 成分とピクセル数はどちらも unsigned char 型として扱い、可変長配列である unsigned char 型の vector インスタンスに変換結果を保持しています。RGB 成分は通常 8 ビットであり、unsigned char 型ならほとんどの場合、問題はありません。なお、RGB クラスの各メンバ関数は unsigned char 型でアクセスすることを前提としています。連続したピクセルの数も unsigned char 型であることから桁あふれが発生する可能性があります。そのため、もし unsigned char 型の最大値 ( 通常は 255 ) を超えたら、いったんバッファに登録した上でカウンタを初期化しています。よって、多少は圧縮率が犠牲になった形となっています。

コンピュータ上で利用される画像の一般的な色数を「色深度 (Color Depth)」といいます。主なものを以下に列挙します。

色深度色 数Bit数Byte数
Monochrome (白黒)211/16
4-bit Color (16色)1641/2
8-bit Color (256色)25681
High Color65536162
True Color約1677万24(32)3(4)

「モノクローム (Monochrome)」は Fax などで利用される他、初期のラップトップ PC に搭載された液晶ディスプレイでも使われたことがあったそうです。しかし、現在の PC で利用されることはほとんどないでしょう。「4-bit Color (16色)」や「8-bit Color (256色)」もまず利用されている方はいないのではないでしょうか。一般的に利用されている色深度は「High Color」か「True Color」のいずれかになると思います。
PC の場合、色コードは光の三原色 ( 赤・緑・青 ) で表されるのが一般的です。「High Color」は 16 ビットの情報を扱うことができるので、一つの原色あたり 5 ビットが割り当てられます。これは、一つの原色について 25 = 32 階調 の明るさを表現することが可能であることを意味します。さらに「True Color」では 28 = 256 階調もの明るさを表現することができます。
人間が識別することのできる色数はだいたい 1000 万色と言われているので、「True Color」は自然画を表現するためのスペックとして充分であるといわれています (これが本当に成り立つかは疑問の余地があります)。グラフィックボードのスペックで「32-bit Color」と言われているものがありますが、実際の色深度は「True Color」と同じで、残りの 8 ビットは利用されていないか、別の情報 ( 一般的にはピクセルの不透明度 ) を書き込んでいます。32 ビットというのは、32 ビット環境においては一般的な Integer 型の大きさになるので、この単位で扱うことで処理速度を速くするというのが「32-bit Color」にする理由です。

前述のサンプル・プログラムは、RGB 成分をまとめて比較するようにしていました。これを個々の成分だけで比較するように変更することはそれほど難しいことではありません。以下に、個々の成分で比較するコーディング例を示します。

class RGB
{
  :
public:

  // 色定義用列挙体(公開)
  enum COLOR
  {
    RED = 0,
    GREEN = 1,
    BLUE = 2,
    RGB_SIZE = 3,
  };

  // 各パレット成分を返す
  unsigned char palet( COLOR index ) const;
};

/*
  RLE_Pack : ランレングス法による圧縮(RGB個々に圧縮)

  const DrawingArea_IF& draw : 描画オブジェクト
  vector<unsigned char>& buff : 圧縮データを保持するバッファ
  RGB::COLOR index : RGB成分のいずれかを表す添字
*/
void RLE_Pack( const DrawingArea_IF& draw, const Coord<int>& sz, vector<unsigned char>& buff, RGB::COLOR index )
{
  if ( index >= RGB::RGB_SIZE ) return;

  Coord<int> c( 0, 0 ); // 画像上の座標
  RGB rgb;              // RGB取得用変数

  // 現在の色コード curPalet は読込開始ピクセル(左上)の色コードで初期化して
  // あらかじめバッファに登録
  draw.point( c, rgb );
  unsigned char curPalet = rgb.palet( index );
  buff.push_back( curPalet );

  unsigned char count = 0; // 同じ色コードが連続した回数
  unsigned char palet;     // 次のピクセルの色コード取得用

  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.point( c, rgb );
      palet = rgb.palet( index );

      if ( palet != curPalet ) {
        buff.push_back( count );
        // count が UCHAR_MAX と等しい場合、次のカウンタはゼロとしておく
        if ( count == UCHAR_MAX )
          buff.push_back( 0 );
        buff.push_back( palet );
        curPalet = palet;
        count = 0;
      }

      // count を 1 つ増加し、最大値に達したらいったんバッファに登録
      if ( ++count == UCHAR_MAX ) {
        buff.push_back( count );
        count = 0;
      }
    }
  }
  // 最後のカウント結果を登録
  buff.push_back( count );
}

/*
  RLE_PrimPack : ランレングス法による圧縮(RGB個々に圧縮)

  const DrawingArea_IF& draw : 描画オブジェクト
  vector<unsigned char>& buff : 圧縮データを保持するバッファ
*/
void RLE_PrimPack( const DrawingArea_IF& draw, vector<unsigned char>& buff )
{
  Coord<int> sz = draw.size(); // 画像サイズ
  buff.clear();

  // バッファの先頭に画像サイズを書き込む
  WriteCoordToCharArray( sz, buff );

  RLE_Pack( draw, sz, buff, RGB::RED );
  RLE_Pack( draw, sz, buff, RGB::GREEN );
  RLE_Pack( draw, sz, buff, RGB::BLUE );
}

/*
  RLE_Unpack : ランレングス法による伸長(RGB個々に圧縮)

  const vector< vector<unsigned char> >& buff : 圧縮データを保持するバッファ(RGB各成分)
  const Coord<int>& sz : 画像サイズ
  DrawingArea_IF& draw : 描画オブジェクト
*/
void RLE_Unpack( vector<unsigned char>::const_iterator& it, vector<unsigned char>::const_iterator e,
                 DrawingArea_IF& draw, const Coord<int>& sz, RGB::COLOR index )
{
  if ( index >= RGB::RGB_SIZE ) return;

  RGB rgb;               // 画像からのRGB成分取得用
  unsigned char r, g, b; // rgbの各成分
  unsigned char palet;   // 圧縮データから取得したRGB成分
  unsigned char count;   // 連続した同色ピクセルの個数
  unsigned char iniCnt;  // count の初期値

  // RGB成分とカウンタの初期化
  if ( ! PopRGB( it, e, palet ) ) return;
  if ( it == e ) return;
  iniCnt = count = *it++;

  Coord<int> c;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.point( c, rgb );
      rgb.get( r, g, b );
      if ( index == RGB::RED )
        r = palet;
      else if ( index == RGB::GREEN )
        g = palet;
      else
        b = palet;
      rgb.set( r, g, b );
      draw.pset( c, rgb );
      if ( --count > 0 ) continue;
      // 最後のピクセルを処理したらすぐに終了
      // 次の成分情報を読み込んでしまうため
      if ( c.x == sz.x - 1 && c.y == sz.y - 1 ) break;
      // カウンタがゼロになったら次の色コードをバッファから取得
      // 但しカウンタの初期値が UCHAR_MAX ならカウンタのみ初期化
      do {
        if ( iniCnt != UCHAR_MAX )
          if ( ! PopRGB( it, e, palet ) ) return;
        if ( it == e ) return;
        iniCnt = count = *it++;
      } while ( count == 0 ); // カウンタがゼロなら読み直し
    }
  }
}

/*
  RLE_PrimUnpack : ランレングス法による伸長(RGB個々に圧縮)

  const vector<unsigned char>& buff : 圧縮データを保持するバッファ
  DrawingArea_IF& draw : 描画オブジェクト
*/
void RLE_PrimUnpack( const vector<unsigned char>& buff, DrawingArea_IF& draw )
{
  Coord<int> sz( 0, 0 ); // 画像サイズ
  vector<unsigned char>::const_iterator it = buff.begin(); // バッファの現在位置

  // buff の先頭から画像サイズを読み込んで画像をリサイズ
  if ( ! ReadCoordFromCharArray( it, buff.end(), sz ) ) return;
  draw.resize( sz );

  RLE_Unpack( it, buff.end(), draw, sz, RGB::RED );
  RLE_Unpack( it, buff.end(), draw, sz, RGB::GREEN );
  RLE_Unpack( it, buff.end(), draw, sz, RGB::BLUE );
}

圧縮処理は RLE_PrimPack からスタートし、RGB 各成分ごとに RLE_Pack を呼び出しています。処理そのものは、RGB 成分を一括で処理した場合と全く同じです。伸長処理も同様で、RLE_PrimUnpack からスタートし、RGB 各成分ごとに RLE_Unpack を呼び出します。クラス RGB に対しては列挙子 COLOR を用意した上で、添え字を引数にそれぞれの成分を返すメンバ関数 palet を定義しています。

両者のどちらが高い圧縮率となるかについては、最後の性能評価で実例を使って示したいと思います。個々の成分で比較する方が一致する確率は増加するので圧縮率は高くなりますが、連続するピクセルの個数は個々の成分ごとに登録する必要があり、その分情報量は増加することになります。

2) PICフォーマット ( 縦方向の連鎖圧縮 )

その昔、まだ「True Color」はおろか「High Color」も一般的にはなくて、たいていの PC が 16 色しか扱えなかった頃、512 x 512 ピクセルで 65536 色同時表示可能という当時としてはビックリするようなスペックを持って X68000 が登場しました。しかし、このスペックの高さが逆に「一つの画像ファイルのサイズが大きくなる」という問題を生み出す結果となってしまいました。当時メーカーから提供された画像保存用のツールはなんと無圧縮方式であったため、一つの画像のサイズは最大 512K バイトとなってしまいます。この頃はまだ HDD も一般的ではなくて、データは FD で扱っていたわけですから、これでは作成した画像を保存・管理するのも大変になってしまいます。
X68000 が発表されてしばらくは利用できるツール類がほとんど存在していなかったので、「ないものは自分で作る」という考えのもと、メーカ純正のものなど比較にならないほど高品質なフリーウェアがたくさん発表されました。ここで紹介する「PIC フォーマット」はその中の一つであり、X68000 を利用する上で間違いなく重要かつ必要不可欠なアルゴリズムでした。

PIC 形式のアルゴリズムは非常に単純明快です。が、このような圧縮を発想するのは非常に難しいと思います。このアルゴリズムは「ランレングス法 (連長法)」を縦方向にも展開したようなもので、当時は「稲妻走る」のキャッチフレーズとともに話題になったようです ( ちなみに、このフォーマットが発表された頃は、私はまだ X68000 ユーザではありませんでした )。

それでは、ランレングス法で利用したものと同じサンプル画像でこのアルゴリズムについて説明したいと思います。
まず、左上から右方向に、色の変化点をチェックしていきます。このとき、右端のピクセルは、すぐ下のラインの左端に続いているとします。下の画像において、三角形は変化点を示しています。

□■□□■□□■□□△▲△□▲△□▲△□
□■■□□■□■□□□▲■△□▲△▲△□
□■■■□□■■□□□▲■■△□▲■△□
□■■■■□□■□□□▲■■■△□▲△□
□■■■■■□■□□ → □▲■■■■△▲△□
□■■■■■■■□□□▲■■■■■■△□
□■■■■□□■□□□▲■■■△□▲△□
□■■■□□■■□□□▲■■△□▲■△□
□■■□□■■■□□□▲■△□▲■■△□
□■□□■■■■□□□▲△□▲■■■△□

次に、同じ色を持った変化点の連鎖をチェックします。これも左上から右方向に変化点を探して、変化点が見つかったら、その下のラインで近くに同じ色を持った変化点がないかをチェックします。もし存在した場合は、その変化点は位置情報を記録してから除外し、さらにその下のラインに対して同じ処理を行います。これを一番下のラインまでチェックしたか、あるいは連鎖が見つからなくなるまで繰り返していきます。例えば上のサンプル画像において、一番上のラインの左から二つ目にある変化点に注目すると、同じ色の変化点は真下に延びていることがわかると思います。
連鎖をチェックする範囲は、PICフォーマットの場合左右 2 ドットまでとなっています。また、位置情報は次のように記録されます。

連鎖の記録方法

よって、下に伸びた連鎖が 10 ドット分あった場合、その位置情報は"1101010101010101010000"となります。なお、画像の左右両端をまたいで連鎖を続けることはしません。
圧縮後のデータとしては、この位置情報の他に、次の変換点までの距離と色コードも記録していきます。PICフォーマットでは、これらのパラメータを記録するときに符号化やパレット管理などを使ってさらに圧縮効果を高めていますが、これらのアルゴリズムについては他の章で紹介したいと思います。

PIC 圧縮のアルゴリズムをまとめると以下のようになります。

  1. 画像から変化点を抽出する(画面右端は下のラインの左端に続く)
  2. 変化点を探し、変化点間の長さを記録する
  3. 変化点の色を記録する
  4. 変化点の下のラインに同じ色を持った変化点 (以下、連鎖点と略記) があるかチェックする
  5. 連鎖点があったらその位置情報を記録して、その点を変化点から外す
  6. 記録した連鎖点の下のラインにさらに連鎖点があるかチェックする
  7. 5-6の操作を連鎖点が見つからなくなるまで繰り返す
  8. 2-7の操作を変化点がなくなるまで繰り返す

PIC フォーマット圧縮処理のサンプルを以下に示します。

// 連鎖として認識する X 方向の幅
const int PIC_CHAIN_RANGE = 2;                         // 中央からの距離
const int PIC_CHAIN_BIT_CNT = PIC_CHAIN_RANGE * 2 + 1; // 左端から右端までの距離
const int PIC_CHAIN_TERM = PIC_CHAIN_BIT_CNT;          // 連鎖情報の終端

/*
  各 X 座標位置に対する連鎖情報
*/

// 連鎖情報保持用の構造体
struct PicChainBit
{
  unsigned char bitString; // ビット列
  unsigned char bitNum;    // ビット数

  // コンストラクタ
  PicChainBit( unsigned char bs, unsigned char bn )
  : bitString( bs ), bitNum( bn ) {}
};

// 連鎖情報配列
PicChainBit PicChainBitArray[] = {
  PicChainBit( 2, 4 ), // 左2
  PicChainBit( 1, 2 ), // 左
  PicChainBit( 2, 2 ), // 中
  PicChainBit( 3, 2 ), // 右
  PicChainBit( 3, 4 ), // 左2
  PicChainBit( 0, 3 ), // 終端
};

/*
  PIC_SearchChangePoint : 変化点の抽出

  const DrawingArea_IF& draw : 対象の画像
  vector< vector<bool> >& changePoint : 変換点の抽出結果
  const RGB_Eq_Base& eq : RGB成分等値判定用関数オブジェクト
*/
void PIC_SearchChangePoint( const DrawingArea_IF& draw, vector< vector<bool> >& changePoint, const RGB_Eq_Base& eq )
{
  Coord<int> sz = draw.size();
  RGB prePalet, palet; // 前の点の色コード, 現在の点の色コード
  changePoint.resize( sz.y );

  Coord<int> c;
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    changePoint[c.y].assign( sz.x, false );
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      draw.point( c, palet );
      if ( ( ! eq( prePalet, palet ) ) || ( c.x == 0 && c.y == 0 ) ) {
        // 前の点と色が異なる場合,変化点とする
        changePoint[c.y][c.x] = true;
        prePalet = palet;
      }
    }
  }
}

/*
  PIC_PushChainCode : 連鎖の登録

  const DrawingArea_IF& draw : 対象の画像
  vector< vector<bool> >& changePoint : 変換点の抽出結果

  vector<unsigned char>& buff : 満杯になった code を登録するバッファ
  unsigned char& code : 連鎖を表すビット列
  unsigned char& index : code に登録したビット数
  const PicChainBit& chainBit : 登録するビット列の内容
*/
void PIC_PushChainCode( vector<unsigned char>& buff, unsigned char& code, unsigned char& index, const PicChainBit& chainBit )
{
  // code が満杯になった場合
  if ( chainBit.bitNum + index >= CHAR_BIT ) {
    unsigned char c = CHAR_BIT - index; // code に登録できる上位側ビット数
    index = chainBit.bitNum - c;        // 残りの下位ビット数を index に登録

    // 上位側ビット列を code に登録して配列へ
    code = ( code << c ) | ( chainBit.bitString >> index );
    buff.push_back( code );

    // 残りを code へ登録
    code = chainBit.bitString & ( ~( 0xFF << index ) );
  } else {
    code = ( code << chainBit.bitNum ) | chainBit.bitString;
    index += chainBit.bitNum;
  }
}

/*
  PIC_SearchChainedLine : 連鎖の抽出

  const DrawingArea_IF& draw : 対象の画像
  vector< vector<bool> >& changePoint : 変化点
  Coord<int> c : 連鎖抽出の開始座標
  vector<unsigned char>& buff : 連鎖を格納するバッファ
  const RGB_Eq_Base& eq : RGB成分等値判定用関数オブジェクト
*/
void PIC_SearchChainedLine( const DrawingArea_IF& draw, vector< vector<bool> >& changePoint,
                            Coord<int> c, vector<unsigned char>& buff, const RGB_Eq_Base& eq )
{
  Coord<int> sz = draw.size(); // 画像サイズ
  RGB palet;      // 抽出用色コード

  // 連鎖部分の色コードを抽出
  RGB chainPalet;
  draw.point( c, chainPalet );

  unsigned char chainCode = 0;      // 連鎖を表すビット列
  unsigned char chainCodeIndex = 0; // chainCode に登録したビット数
  bool isFirst = true;              // 連鎖開始前か(初めて連鎖登録するか)

  while ( ++( c.y ) < sz.y ) {
    c.x -= PIC_CHAIN_RANGE;
    int i = 0;
    // 変化点の中から連鎖の色コードと同じものがあれば,変化点からはずす
    for ( ; i < PIC_CHAIN_BIT_CNT ; ++i, ++( c.x ) ) {
      if ( c.x < 0 ) continue;
      if ( c.x >= sz.x ) break;
      draw.point( c, palet );
      // 同色の連鎖が見つかった場合
      if ( changePoint[c.y][c.x] && ( eq( chainPalet, palet ) ) ) {
        changePoint[c.y][c.x] = false;
        // 初めて連鎖登録する場合は最上位 1 ビットを立てる
        if ( isFirst ) {
          PIC_PushChainCode( buff, chainCode, chainCodeIndex, PicChainBit( 1, 1 ) );
          isFirst = false;
        }
        PIC_PushChainCode( buff, chainCode, chainCodeIndex, PicChainBitArray[i] );
        break;
      }
    }
    if ( c.x >= sz.x || i >= PIC_CHAIN_BIT_CNT ) break; // 連鎖が見つからなければ終了
  }
  // 終端コードの登録
  PIC_PushChainCode( buff, chainCode, chainCodeIndex, PicChainBitArray[PIC_CHAIN_TERM] );
  // 途中まで連鎖が書き込まれていた場合はバッファに登録
  if ( chainCodeIndex > 0 )
    buff.push_back( chainCode << ( CHAR_BIT - chainCodeIndex ) );
}

/*
  PIC_Pack : PIC圧縮サンプルメイン

  const DrawingArea_IF& draw : 対象の画像
  vector<unsigned char>& buff : 連鎖を格納するバッファ
  const RGB_Eq_Base& eq1 : RGB成分等値判定用関数オブジェクト(変化点抽出用)
  const RGB_Eq_Base& eq2 : RGB成分等値判定用関数オブジェクト(連鎖取得用)
*/
void PIC_Pack( const DrawingArea_IF& draw, vector<unsigned char>& buff,
               const RGB_Eq_Base& eq1, const RGB_Eq_Base& eq2 )
{
  vector< vector<bool> > changePoint; // 変化点
  Coord<int> sz = draw.size();        // 画像サイズ
  unsigned char length = 0;           // 次の変化点までの距離

  // 画像サイズの登録
  WriteCoordToCharArray( sz, buff );

  // 変化点を抽出する
  PIC_SearchChangePoint( draw, changePoint, eq1 );

  Coord<int> c; // 現座標
  RGB palet;    // 抽出した色コード
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      // 次の変化点までの距離がCHARサイズに達したら圧縮用配列に挿入
      if ( length == UCHAR_MAX ) {
        buff.push_back( length );
        length = 0;
      }
      if ( changePoint[c.y][c.x] ) {
        // 変化点ならば前の変化点からの距離と色コードを圧縮用配列に追加
        buff.push_back( length );
        draw.point( c, palet );
        PushRGB( palet, buff );
        // 連鎖情報を圧縮用配列に追加する
        PIC_SearchChainedLine( draw, changePoint, c, buff, eq2 );
        length = 0;
      }
      ++length;
    }
  }
}

連鎖は、現在位置の X 座標から左右 2 ドット分までを対象に続くという条件から、連鎖情報は前述の通り計 5 つあります。また、終端を表す情報も必要なので、6 つの情報をまとめて PicChainBitArray という配列に登録します。この配列の要素は構造体 PicChainBit で、ビット列の bitString とビット数 bitNum をメンバ変数に持ちます。
メイン・ルーチンは PIC_Pack で、画像サイズを登録後、変化点の抽出を PIC_SearchChangePoint で行います。変化点の抽出が完了したら画像の左上側から順に変化点を探索し、変化点が見つかったら、前の変化点からの距離と変化点の色コードを登録してから PIC_SearchChainedLine を使って連鎖情報を抽出します。前の変化点からの距離も unsigned char 型の配列に登録するため、桁あふれが発生した場合に備え、unsigned char の最大値に達したらいったん配列に登録しています。従って、圧縮データを伸長する時は、前の変化点からの距離が unsigned char の最大値に等しい場合、次の要素も距離を表していると認識させる必要があります。なお、ちょうど unsigned char の最大値になった場合、次の要素はゼロが登録されるようにしているので、伸長の際は、unsigned char の最大値に等しい間は読み込みを続けるようにするだけで済みます。また、画像の左上 ( 読み込みの開始位置 ) は必ず変化点として扱われますが、前の変化点との距離は必ずゼロが登録されるようにしています。
連鎖情報の抽出を行う PIC_SearchChainedLine では、まず連鎖開始位置の色コードを抽出し、下側のラインから色コードが等しいと見なされた変化点を探します。もし見つからなければそこで処理終了となり、見つかったらその変化点を外して連鎖として登録します。連鎖が続いた状態が画像の下端まで達した場合も処理終了です。最後に終端を表すビット列を登録していますが、これは連鎖がひとつも見つからなかった場合でも行なっています。連鎖がない場合、連鎖情報は最上位のゼロビットのみなので、バイト単位ならゼロを書き込むだけでよく、終端を表すビット列は "000" なので処理をしても結果は同じになるのですが、連鎖がなくても 1 バイト分は書き込む必要があり、この後に続く、途中まで書き込んだビット列の登録時にまとめて処理させたい ( 連鎖がなかったときは、もし書き込みをしなければ chainCodeIndex がゼロのままなので、配列への登録もされなくなります ) のであえて処理を行うようにしています。ビット列の登録は PIC_PushChainCode で行い、引数として対象の連鎖情報 ( PicChainBitArray の要素 ) を渡します。このとき、添字の i がそのまま連鎖での X 座標の相対位置を表していることに注意して下さい。また PIC_PushChainCode の中では、ビット列を code にいったん登録しておき、ビット列が満杯になったら配列に書き込むようにしているので、ビット列の途中まで書き込んだら満杯になる場合に備えて場合分けをしています。また、前述の通り、途中まで書き込まれたビット列も必ず配列へ登録しなければなりません。

なお、RGB 成分が等しいかどうかを比較するための関数オブジェクト RGB_Eq_Base として、変化点抽出時と連鎖抽出時のそれぞれを別々に用意しています。この理由については後ほど説明します。

圧縮データを伸長するやり方は、ちょうど圧縮と逆の操作をすることで実現できます。まず、圧縮データに格納された前の変化点からの距離、色コード、連鎖の位置情報をもとに変化点をテーブルに展開し、展開した変化点情報に従って画像を描画します。圧縮の時、連鎖の部分は探索される前に変化点から外されるので、変化点として登録される位置は必ず連鎖の開始位置のみとなります。従って、連鎖となった変化点は連鎖の位置情報から展開され、連鎖とならなかった変化点だけが前の変化点からの距離と色コードによって展開されます。変化点とその色コードが展開されれば、あとは変化点に達するまで同じ色コードで描画すれば元の画像を復元することができます。以下に、PIC 圧縮したデータを伸長するサンプル・プログラムを示します。

/*
  PIC_GetChainBit : 連鎖から 1 ビット抽出

  vector<unsigned char>::const_iterator& it : 連鎖のある配列の現在の反復子
  vector<unsigned char>::const_iterator e : 連鎖のある配列の終端の反復子
  unsigned char& bitNum : 何番目のビットを取得するか ( 最下位を 1 番から数える )

  戻り値 : true(1)/false(0) ( 反復子が終端まで達したら必ず false )
*/
bool PIC_GetChainBit( vector<unsigned char>::const_iterator& it, vector<unsigned char>::const_iterator e, unsigned char& bitNum )
{
  // bitNum が 0 になっていたら全ビット読み込み完了を意味するので
  // 配列から次のビット列を読み込む
  if ( bitNum == 0 ) {
    ++it;
    if ( it == e ) return( false );
    bitNum = CHAR_BIT;
  }
  --bitNum;

  return( ( *it >> bitNum ) & 1 );
}

/*
  PIC_PopChainCode : 連鎖情報を抽出して変化点を復元する

  vector<unsigned char>::const_iterator& it : 連鎖のある配列の現在の反復子
  vector<unsigned char>::const_iterator e : 連鎖のある配列の終端の反復子
  DrawingArea_IF& draw : 描画対象
  const RGB& chainPalet : 連鎖の色コード
  vector< vector<bool> >& changePoint : 変化点
  Coord<int> c : 描画対象の現在の座標
*/
void PIC_PopChainCode( vector<unsigned char>::const_iterator& it, vector<unsigned char>::const_iterator e,
                       DrawingArea_IF& draw, const RGB& chainPalet, vector< vector<bool> >& changePoint, Coord<int> c )
{
  unsigned char bitNum = CHAR_BIT; // 連鎖情報から読み込むビット位置 ( 最下位を 1 番から数える )
  Coord<int> sz = draw.size();     // 画像サイズ

  // スタート位置の変化点
  changePoint[c.y][c.x] = true;
  draw.pset( c, chainPalet );

  if ( it == e ) return;
  if ( ! PIC_GetChainBit( it, e, bitNum ) ) return; // 連鎖なしならすぐ終了

  while ( it != e ) {
    ++( c.y );
    if ( PIC_GetChainBit( it, e, bitNum ) ) {
      if ( PIC_GetChainBit( it, e, bitNum ) )
        ++( c.x ); // 11 = 右
    } else {
      if ( PIC_GetChainBit( it, e, bitNum ) ) {
        --( c.x ); // 01 = 左
      } else {
        if ( ! PIC_GetChainBit( it, e, bitNum ) ) break; // 000 = 終端
        if ( PIC_GetChainBit( it, e, bitNum ) )
          c.x += 2; // 0011 = 右2
        else
          c.x -= 2; // 0010 = 左2
      }
    }
    if ( c.x < 0 || c.x >= sz.x ||
         c.y < 0 || c.y >= sz.y ) break;
    changePoint[c.y][c.x] = true;
    draw.pset( c, chainPalet );
  }
}

/*
  PIC_UnpackChainedLine : 圧縮データの伸長

  vector<unsigned char>::const_iterator& it : 連鎖のある配列の現在の反復子
  vector<unsigned char>::const_iterator e : 連鎖のある配列の終端の反復子
  DrawingArea_IF& draw : 描画対象
  vector< vector<bool> >& changePoint : 変化点
*/
void PIC_UnpackChainedLine( vector<unsigned char>::const_iterator& it, vector<unsigned char>::const_iterator e,
                            DrawingArea_IF& draw, vector< vector<bool> >& changePoint )
{
  Coord<int> sz = draw.size(); // 画像のサイズ
  RGB chainPalet;              // 連鎖の色コード

  // 変化点の初期化
  changePoint.resize( sz.y );
  for ( vector< vector<bool> >::iterator i = changePoint.begin() ;
        i != changePoint.end() ; ++i )
    i->assign( sz.x, false );

  Coord<int> c( 0, 0 ); // 現在の座標位置
  while ( it != e ) {
    // 次の変化点まで移動
    // 距離が UCHAR_MAX と等しい場合は次の要素も距離を表す
    do {
      c.x += *it++;
      if ( c.x >= sz.x ) {
        c.y += c.x / sz.x;
        c.x %= sz.x;
      }
    } while ( *( it - 1 ) == UCHAR_MAX && it != e );
    if ( ! PopRGB( it, e, chainPalet ) ) return;
    if ( c.x >= sz.x || c.y >= sz.y ) break;
    PIC_PopChainCode( it, e, draw, chainPalet, changePoint, c );
    ++it; // 連鎖情報抽出後はまだ末尾を指しているので 1 増加
  }
}

/*
  PIC_Unpack : PIC展開サンプルメイン

  const vector<unsigned char>& buff : 圧縮したデータ
  DrawingArea_IF& draw : 描画対象
*/
void PIC_Unpack( const vector<unsigned char>& buff, DrawingArea_IF& draw )
{
  // 圧縮データの読み込み位置を先頭に初期化
  vector<unsigned char>::const_iterator it = buff.begin();
  Coord<int> sz; // 画像サイズ

  if ( ! ReadCoordFromCharArray( it, buff.end(), sz ) ) return;
  draw.resize( sz );

  // 圧縮された情報を変化点テーブルに展開する
  // このとき、変化点は対象の色コードで描画される
  vector< vector<bool> > changePoint;
  PIC_UnpackChainedLine( it, buff.end(), draw, changePoint );

  RGB palet;    // 現在の色コード
  Coord<int> c; // 現在の座標位置
  for ( c.y = 0 ; c.y < sz.y ; ++( c.y ) ) {
    for ( c.x = 0 ; c.x < sz.x ; ++( c.x ) ) {
      // 変化点だった場合,色コードを変更 (変化点はすでに対象の色コードで描画済)
      // そうでなければ現在の色コードで描画
      if ( changePoint[c.y][c.x] )
        draw.point( c, palet );
      else
        draw.pset( c, palet );
    }
  }
}

メイン・ルーチンは PIC_Unpack で、最初に画像サイズを圧縮データから取得して描画対象をリサイズし、PIC_UnpackChainedLine で変化点を展開します。
PIC_UnpackChainedLine は、bool 型の二次元配列である変化点テーブル changePoint の要素を全て false で初期化しておいてから、変化点の位置だけを true に置き換える処理を行います。圧縮データから前の変化点からの距離と色コードを読み込み、座標に距離を加算して変化点テーブルにその位置を書き込み、さらに描画対象に直接色コードを描画します。なお、圧縮ルーチンのところで述べたように、距離は unsigned char の最大値に達したら次の要素にも距離の情報が書き込まれるので、unsigned char の最大値である間は連続で読み込む必要があります。また、最初のピクセルは前の変化点からの距離がゼロで登録されているので、位置は変化しないことにも注意して下さい。
連鎖情報の読み込みは PIC_PopChainCode で行います。圧縮の時とは異なり、ここではビット列の先頭から順番に 1 ビットずつ読み込んで処理を行います。連鎖として認識された位置は、変化点テーブルを true にして描画対象に連鎖の色コードをセットします。
変化点の展開が完了すれば、あとは変化点に達するまで同じ色コードで描画をするだけです。なお、圧縮・伸長のどちらについても今回は変化点テーブルとして bool 型の二次元配列を用意しています。X68000 はピクセルの色コードが 16 ビット ( High Color ) で、その内の 15 ビット ( 5 ビット x RGB 3 色 ) が色コード、残りの 1 ビットは輝度ビットとして全体の明るさを半段階だけ調整する用途に使っていました。オリジナルの PIC では、この輝度ビットの ON/OFF により変化点を表していたので、変化点用のテーブルを用意する必要がありませんでした。これにならって、32 ビット ( True Color ) のうち色成分として利用されていない 8 ビット分 ( これを一般に「アルファ・チャンネル (Alpha Compositing)」といいます ) を利用すれば変化点テーブルを不要とすることができます。

PIC 圧縮やランレングス法は、近くにあるピクセルどうしの色コードが同じであることを利用して圧縮を行うアルゴリズムです。よってアニメ調の画像などには威力を発揮しますが、自然画などに対しては圧縮効果はあまり期待できません。PIC 圧縮を開発された方も、自然画ではなくアニメ調の画像にスポットを当てて開発されたようです。
画像圧縮は、「これひとつあれば充分」というようなアルゴリズムは存在しないと思います。自然画に対しては JPEG 圧縮が効果的ですが、非可逆な圧縮であり、特にアニメ調の画像では画像の劣化が顕著に現れます。PNG や GIF などは可逆圧縮であり画像の劣化もありませんが、圧縮率は JPEG ほど高くなく、特に GIF は色数に制限があります ( もうひとつ、GIF は、内部で利用されている圧縮アルゴリズムの LZW に対して UNISYS 社が特許権を取得していたため、広く普及するようになってから利用料を請求し始めたという騒動もありました。しかし、アメリカでは 2003 年、日本でも 2004 年に特許権が失効し、現在では自由に利用可能な画像フォーマットと見なされているようです )。
結局はそれぞれの画像の性質に合わせて圧縮法を切り替えることになると思いますが、今のところ一般的には JPEG か GIF(PNG) が一般的に利用されている圧縮法だと思います。

3) 性能評価

サンプルプログラムを使って、いくつかの画像を圧縮してみました。サンプルに使った画像は下の 2 枚の画像の他に、自然画・アニメ調・モノクロのマンガの画像を google の画像検索機能を使って適当にサンプリングしています。それぞれの検索キーワードは「風景」「アニメ」「マンガ」で、マンガは白黒の絵のみを検索するように設定してます。また、いずれの画像も 1024 x 768 のサイズで、それぞれ 10 枚ずつ抽出しました。

表 3-1. サンプル画像 (画像サイズ 100 x 100)
画像 1画像 2
サンプル画像 1サンプル画像 2

まずは、二つのサンプル画像を処理した結果を以下に示します。圧縮率は、母数を元画像のサイズ ( ピクセル数 x 3 (RGB成分) )、とし、圧縮したデータの要素数から画像サイズ用の領域を減算した値との比率として求めています。

表 3-2. サンプル画像での処理結果
画像圧縮率
RLE法RLE法(RGB成分ごと)PIC圧縮法
画像 12.60%1.57%0.34%
画像 2133.33%66.94%11.40%

サンプル画像はかなり特殊な画像で、画像 1 は黒と赤の二種類の色のみで、しかも各色はそれぞれ一つの閉じた領域を塗りつぶした形になっているため、特に PIC フォーマットに対しては有利な画像です。どの処理方法においてもかなりの圧縮率となっていますが、特に PIC フォーマットでの圧縮率が最も高いという予想通りの結果となりました。画像 2 は、赤成分のみからなるグラデーションなので、ランレングス法の場合は全ての隣り合うピクセルの色が一致せず、カウンタの分だけ元画像よりもサイズが増えています。RGB 各成分に分けてランレングス圧縮をした場合は、緑・青成分が全てゼロであることから、これらがかなり圧縮され、通常の圧縮法より半分程度のサイズに抑えられています。PIC 圧縮では、斜め方向に同じ色コードがあるためにうまく圧縮できています。

次に、「風景」をキーワードに検索・サンプリングした 10 枚の画像を処理した結果を示します。圧縮率は、先ほどのサンプル画像での計算方法と同様にして求めました。

表 3-3. 「風景」画像での処理結果
画像圧縮率
RLE法RLE法(RGB成分ごと)PIC圧縮法
画像 1109.77%155.80%109.03%
画像 297.13%140.99%114.39%
画像 398.10%130.52%111.25%
画像 4129.19%187.65%157.61%
画像 5124.84%182.85%135.24%
画像 6131.32%189.17%160.78%
画像 7114.27%160.86%122.38%
画像 8118.82%166.20%136.20%
画像 9124.93%176.75%144.08%
画像 1073.95%103.21%62.78%
平均112.23%159.40%125.37%

対象の画像はいわゆる「自然画」であり、ほとんど圧縮に失敗していることから、これらのアルゴリズムが自然画には弱いということがよくわかります。意外にも、ランレングス圧縮が PIC フォーマットより少し圧縮率がよくなっています。また、RGB 各成分に分解して圧縮した場合、隣り合う成分が等しくなる率は多少よくなるはずですが、各成分ごとにカウンタを持たなければならない分余計にデータが増えるので、結果として圧縮率は悪くなっています。

アニメ調の画像とモノクロのマンガの画像に対する処理結果を以下に示します。

表 3-4. 「アニメ調」画像での処理結果
画像圧縮率
RLE法RLE法(RGB成分ごと)PIC圧縮法
画像 176.65%106.63%83.90%
画像 281.88%89.88%74.24%
画像 385.16%112.16%77.17%
画像 471.97%95.66%66.58%
画像 535.82%44.92%34.41%
画像 6100.60%137.25%99.37%
画像 797.10%136.48%103.19%
画像 894.51%133.43%108.74%
画像 955.29%70.72%58.48%
画像 1089.59%124.03%88.28%
平均78.86%105.12%79.43%
 
表 3-5. 「マンガ」画像での処理結果
画像圧縮率
RLE法RLE法(RGB成分ごと)PIC圧縮法
画像 197.52%146.25%104.78%
画像 293.53%140.30%98.94%
画像 374.27%111.41%72.07%
画像 473.02%109.54%73.26%
画像 5105.99%158.96%113.32%
画像 6100.15%149.95%108.98%
画像 7122.03%183.06%135.69%
画像 884.96%127.33%86.07%
画像 983.02%124.54%84.63%
画像 1080.67%121.00%76.38%
平均91.52%137.23%95.41%

「風景」画像と比較すると圧縮率はある程度よくなるという結果が得られました。しかし、その圧縮率もアニメ調で平均 80% 程度、マンガ画像で平均 90% 以上とあまり高い圧縮率は得られませんでした。画像のほとんどは JPEG 形式であり、アニメ調とはいえ隣り合うピクセルが等しい色コードを持つ率は比較的低いことが予想できます。これらの圧縮法を利用することができる画像はかなり限られたものになります。

このままではくやしいので、今度はアニメ調の画像に対してさらに GIF 形式のものだけに絞って 10 個の画像を抽出しました。今回も画像サイズは 1024 x 768 のものだけを対象とし、背景などはシンプルなものだけに絞っています。

表 3-6. 「アニメ調」GIF画像での処理結果
画像圧縮率
RLE法RLE法(RGB成分ごと)PIC圧縮法
画像 16.83%10.00%4.95%
画像 230.08%44.36%25.83%
画像 37.86%10.74%5.97%
画像 416.65%24.12%10.92%
画像 57.45%11.12%4.70%
画像 611.24%14.91%8.20%
画像 76.46%9.73%5.16%
画像 815.41%21.97%11.84%
画像 917.90%21.03%13.72%
画像 1013.30%17.94%10.08%
平均13.32%18.59%10.14%

今度は予想通り、PIC フォーマットが最も高い圧縮率となりました。今回のサンプル・プログラムの中では、色コードの異なる個所への距離(カウンタ)を unsigned char 型の変数で扱い、その最大値を超えたら配列に書き込むようにしていました。最大値が 255 ( 8 ビット分 ) だった場合、必要な要素数は 256 以上になったら 2 となり、511 以上になったら 3 となりますが、実際には二つの要素で 65535 まで表すことができるので、このやり方は効率がいいとはいえません。このあたりを改善すればもう少し圧縮率を上げることができます。しかし、自然画の場合は連鎖がそれほど長くならないことから、改善したとしてもほとんど効果は見込めません。前述の通り、自然画に対しては他の手法を使う必要があります。

ランレングス法における横方向の、また PIC フォーマットの連鎖の RGB 成分は、必ず完全に一致することを前提に処理をしていたわけですが、この制限を少し緩めて、例えば RGB 成分それぞれの差が全てあるしきい値以下であれば一致したと見なすようにすれば、圧縮率が高くなるだけでなくモアレ ( 縞模様どうしの干渉 ) やかすれ等のノイズを除去する役割も期待できます。以下のような RGB 成分等値判定用の関数オブジェクトを用意して、ランレングス法と PIC フォーマットの両方で圧縮処理を行なってみます。

/*
  RGB_FuzzyEq : RGB要素が全てあるしきい値以下か
*/
class RGB_FuzzyEq : public RGB_Eq_Base
{
  unsigned char threshold_; // しきい値

 public:

  // コンストラクタ
  RGB_FuzzyEq( unsigned char threshold )
    : threshold_( threshold ) {}

  // 等値判定用関数
  virtual bool operator()( const RGB& rgb1, const RGB& rgb2 ) const;
};

/*
  RGB_FuzzyEq::operator() : 等値判定用関数

  RGB 各成分が全てあるしきい値内にあるかを判定する

  const RGB &rgb1, &rgb2 : 対象の RGB 成分
*/
bool RGB_FuzzyEq::operator()( const RGB& rgb1, const RGB& rgb2 ) const
{
  return(
         abs( rgb1.r() - rgb2.r() ) <= threshold_ &&
         abs( rgb1.g() - rgb2.g() ) <= threshold_ &&
         abs( rgb1.b() - rgb2.b() ) <= threshold_
         );
}

しきい値はコンストラクタにて引数として渡して調整することができます。今回は、しきい値を 1, 2, 4, 8, 16, 64, 128 の 7 パターンとして試してみました。なお、PIC 圧縮は等号判定を横方向 (変化点の抽出) と縦方向 (連鎖の抽出) の二種類設定することができるので、横方向は完全一致の場合のみ等しいとみなすようにして、連鎖方向だけしきい値により振り分けています。

表 3-7. 「アニメ調」画像でのしきい値別処理結果 [ () 内はしきい値 = 0 との比率 ]
圧縮法画像しきい値
012481664128
RLE法画像176.65% (100.00%)67.74% (88.37%)59.74% (77.93%)47.36% (61.79%)32.46% (42.35%)19.88% (25.94%)5.81% (7.58%)1.89% (2.47%)
画像281.88% (100.00%)50.23% (61.34%)38.17% (46.62%)27.71% (33.85%)19.99% (24.42%)14.92% (18.23%)5.49% (6.71%)2.40% (2.93%)
画像385.16% (100.00%)67.55% (79.33%)56.77% (66.67%)41.21% (48.39%)25.17% (29.56%)14.94% (17.54%)4.04% (4.74%)0.97% (1.14%)
画像471.97% (100.00%)55.53% (77.16%)44.38% (61.66%)34.74% (48.27%)27.69% (38.48%)21.27% (29.55%)6.92% (9.61%)1.80% (2.50%)
画像535.82% (100.00%)27.16% (75.82%)22.18% (61.92%)16.96% (47.35%)12.61% (35.20%)9.50% (26.52%)4.35% (12.13%)2.12% (5.93%)
画像6100.60% (100.00%)81.54% (81.06%)67.02% (66.62%)50.42% (50.12%)35.27% (35.06%)22.93% (22.80%)5.61% (5.58%)1.28% (1.27%)
画像797.10% (100.00%)83.00% (85.49%)71.17% (73.30%)55.38% (57.03%)38.63% (39.78%)24.37% (25.10%)6.60% (6.79%)2.36% (2.43%)
画像894.51% (100.00%)88.86% (94.03%)82.12% (86.90%)72.45% (76.66%)58.20% (61.58%)40.66% (43.03%)10.80% (11.42%)1.84% (1.95%)
画像955.29% (100.00%)49.32% (89.20%)43.56% (78.78%)35.99% (65.08%)26.66% (48.22%)17.31% (31.30%)5.42% (9.79%)2.26% (4.10%)
画像1089.59% (100.00%)72.10% (80.48%)58.21% (64.97%)43.67% (48.75%)29.17% (32.56%)17.15% (19.15%)5.34% (5.96%)2.26% (2.53%)
PIC法画像183.90% (100.00%)73.17% (87.22%)62.44% (74.43%)47.46% (56.57%)31.80% (37.91%)20.96% (24.98%)12.34% (14.71%)11.02% (13.14%)
画像274.24% (100.00%)47.32% (63.74%)37.50% (50.52%)29.14% (39.25%)23.00% (30.99%)19.03% (25.63%)13.57% (18.28%)12.67% (17.07%)
画像377.17% (100.00%)63.13% (81.81%)51.97% (67.34%)38.93% (50.44%)27.50% (35.64%)19.50% (25.27%)13.49% (17.48%)12.43% (16.10%)
画像466.58% (100.00%)53.71% (80.67%)43.89% (65.92%)34.89% (52.41%)28.21% (42.38%)22.10% (33.19%)14.48% (21.75%)13.17% (19.79%)
画像534.41% (100.00%)28.35% (82.40%)24.06% (69.92%)19.52% (56.73%)15.52% (45.12%)12.59% (36.58%)8.71% (25.32%)7.91% (22.98%)
画像699.37% (100.00%)81.56% (82.07%)65.97% (66.39%)48.61% (48.92%)34.45% (34.67%)24.98% (25.13%)16.78% (16.89%)15.94% (16.04%)
画像7103.19% (100.00%)84.74% (82.12%)68.22% (66.12%)49.27% (47.75%)33.80% (32.75%)23.82% (23.09%)14.97% (14.51%)14.01% (13.58%)
画像8108.74% (100.00%)100.03% (92.00%)89.99% (82.76%)74.51% (68.53%)55.68% (51.21%)37.90% (34.85%)16.22% (14.92%)12.62% (11.60%)
画像958.48% (100.00%)51.15% (87.47%)44.11% (75.44%)34.92% (59.72%)25.34% (43.34%)17.51% (29.95%)9.83% (16.82%)8.76% (14.97%)
画像1088.28% (100.00%)75.81% (85.87%)65.12% (73.76%)50.91% (57.67%)35.95% (40.73%)25.46% (28.84%)17.58% (19.91%)15.75% (17.84%)
 
表 3-8. 「風景」画像でのしきい値別処理結果 [ () 内はしきい値 = 0 との比率 ]
圧縮法画像しきい値
012481664128
RLE法画像1109.77% (100.00%)82.81% (75.44%)68.49% (62.39%)54.92% (50.03%)46.34% (42.21%)36.93% (33.64%)11.77% (10.72%)3.60% (3.28%)
画像297.13% (100.00%)89.54% (92.19%)84.69% (87.20%)78.51% (80.83%)69.21% (71.26%)54.40% (56.01%)13.38% (13.78%)2.11% (2.18%)
画像398.10% (100.00%)83.44% (85.06%)70.27% (71.63%)51.94% (52.95%)31.51% (32.12%)14.80% (15.08%)1.48% (1.51%)0.49% (0.50%)
画像4129.19% (100.00%)125.38% (97.05%)120.19% (93.03%)109.93% (85.09%)92.54% (71.63%)67.89% (52.55%)15.68% (12.14%)2.99% (2.31%)
画像5124.84% (100.00%)108.65% (87.03%)94.84% (75.97%)75.43% (60.42%)54.93% (44.00%)37.58% (30.10%)9.94% (7.96%)3.31% (2.65%)
画像6131.32% (100.00%)126.00% (95.95%)117.86% (89.75%)102.07% (77.73%)77.65% (59.13%)49.15% (37.42%)9.06% (6.90%)2.19% (1.67%)
画像7114.27% (100.00%)91.89% (80.41%)74.93% (65.58%)53.51% (46.83%)32.50% (28.44%)16.54% (14.47%)1.54% (1.35%)0.36% (0.31%)
画像8118.82% (100.00%)103.21% (86.86%)89.95% (75.70%)72.37% (60.91%)51.36% (43.23%)29.38% (24.73%)3.67% (3.09%)0.74% (0.62%)
画像9124.93% (100.00%)113.54% (90.89%)103.91% (83.18%)89.93% (71.99%)72.10% (57.72%)51.57% (41.28%)12.96% (10.37%)2.78% (2.23%)
画像1073.95% (100.00%)38.43% (51.96%)22.76% (30.77%)11.06% (14.96%)5.11% (6.90%)2.29% (3.10%)0.43% (0.58%)0.18% (0.24%)
PIC法画像1109.03% (100.00%)93.94% (86.16%)83.76% (76.83%)73.71% (67.61%)62.68% (57.49%)48.18% (44.19%)25.85% (23.71%)21.79% (19.98%)
画像2114.39% (100.00%)109.89% (96.06%)104.12% (91.02%)92.54% (80.90%)73.08% (63.89%)49.29% (43.09%)19.56% (17.10%)13.77% (12.04%)
画像3111.25% (100.00%)103.45% (92.99%)95.11% (85.50%)82.09% (73.79%)64.15% (57.66%)44.53% (40.03%)18.42% (16.56%)15.69% (14.11%)
画像4157.61% (100.00%)151.16% (95.91%)142.66% (90.51%)125.50% (79.63%)98.21% (62.31%)67.24% (42.66%)27.35% (17.35%)18.28% (11.60%)
画像5135.24% (100.00%)116.32% (86.01%)103.91% (76.83%)87.90% (65.00%)68.44% (50.60%)48.99% (36.22%)24.65% (18.22%)21.20% (15.67%)
画像6160.78% (100.00%)151.54% (94.25%)137.07% (85.25%)111.77% (69.52%)80.45% (50.04%)52.19% (32.46%)23.08% (14.36%)17.91% (11.14%)
画像7122.38% (100.00%)103.70% (84.73%)86.47% (70.66%)64.36% (52.59%)43.78% (35.78%)30.35% (24.80%)20.28% (16.57%)19.33% (15.80%)
画像8136.20% (100.00%)120.69% (88.61%)103.12% (75.71%)79.55% (58.41%)56.11% (41.19%)37.95% (27.87%)20.91% (15.35%)18.16% (13.34%)
画像9144.08% (100.00%)131.74% (91.43%)119.57% (82.99%)100.99% (70.09%)77.58% (53.84%)54.50% (37.83%)26.17% (18.17%)20.44% (14.19%)
画像1062.78% (100.00%)49.89% (79.48%)40.93% (65.19%)32.96% (52.51%)27.04% (43.07%)22.81% (36.33%)19.04% (30.34%)18.50% (29.47%)

しきい値がゼロの結果は、RGB 成分が完全に一致した場合に等しいとみなすやり方なので、先に示した結果と等しくなっています。また () 内は、このしきい値がゼロの時のサイズに対する比率を意味します。どの画像も、しきい値が大きくなるほど圧縮率はとうぜん高くなりますが、元の画像の状態を保持しながら圧縮できるのはせいぜいしきい値が 4 程度までです。それを超えると、ランレングス法の場合は横方向の同じ色のラインが増えていき、層を重ねたような画像になっていきます。また、PIC フォーマットは左下側方向の連鎖が増えていき、斜め方向の層が目立つようになります。いずれの場合も、しきい値があまりに高くなると、輪郭線自体が崩れてしまいます。また残念ながら、ノイズ除去の効果はあまり期待できません。しかし、しきい値を適当に調節すれば、あまり目立つことなく圧縮率を高める効果はあります。しきい値 4 の場合、アニメ調の画像なら元の圧縮率に比べて半分程度さらに小さくすることができています。また別の効果として、層を重ねたような画像に変化するため一種のフィルタとして利用することも可能です。風景画などでおもしろい効果が得られたものもあります。

フィルタとしての効果を高めるなら、PIC 圧縮に対して連鎖候補の中で最もしきい値の低かったものを選択する方法も考えられます。通常ならば、左側から順に候補を探索して見つかったら処理を完了しているので、どうしても連鎖が左側に寄ってしまう傾向がありますが、これを防止することが可能です。しかし、本当に連鎖を探索するのであれば、さらに下側のピクセル状態も加味した形で行うべきであり、処理もそれだけ複雑になります。また本来の圧縮処理としての範囲を超えてしまうので今回は割愛しました (他のところでチャレンジするかもしれません)。

<参考文献>
  1. インターフェース 1991 年 12 月号 画像データ圧縮の理解と応用
  2. 「PICフォーマットについて」 柳沢明 様 著
  3. Wikipedia
[Go Back]前に戻る [Back to HOME]タイトルに戻る
inserted by FC2 system