前章に引き続き、ハフマン符号化(Huffman coding)について説明します。
前回、静的ハフマン圧縮と符号表の表現方法について紹介しましたが、この章では符号表の表現方法の一つであるハフマン符号の正規化と、符号表を残さなくても元のデータに変換することが可能になる動的ハフマン圧縮(適応型ハフマン符号法; Adaptive Huffman Coding)を紹介し、またそれぞれの圧縮法に対する圧縮率を実際に評価してみたいと思います。
前回までに、符号表を表現する方法として、符号とその長さを配列に格納するやり方と、木構造の形のままで保持するやり方の2つを紹介しましたが、3つめのやり方として、符号そのものは残さずにその長さのみを保持するやり方があります。これが実現できれば、符号長は最大255 Bitsで表現できるため、その長さを1 Byteで収めることができ、符号表に必要なエリアは256 Bytesだけになります。
この方法を利用する場合、ハフマン木を、接頭符号の形を損なうことなく変形させる必要があります。この処理を、文献ではハフマン符号の正規化と名付けていますが、一般的にどう呼ばれているのかはわかりません。
具体的には、同じレベルの節をその下の部分木ごと交換して、ハフマン木の右側(左側でも可)ほどレベルが深くなるようにしてから、同じレベルにある葉の中のパレットコードを左側から昇順で並べ替えるだけです。
ハフマン符号の正規化
| 1 | 2 | 3 |
|---|---|---|
| |
|
| データ番号 | 元の接頭符号 | 正規化した接頭符号 |
|---|---|---|
| 4 | 11 | 00 |
| 6 | 01 | 01 |
| 1 | 100 | 100 |
| 3 | 000 | 101 |
| 5 | 101 | 110 |
| 2 | 0010 | 1110 |
| 0 | 00110 | 11110 |
| 7 | 00111 | 11111 |
上の例では、赤で塗られた同レベルの節を入れ替えて、木の右側ほどレベルが深くなるようにしてから、黄色で塗られた同レベルの葉を入れ替えて、データ番号が昇順に並ぶようにしています。
正規化によって得られたハフマン符号には強い規則性が見られます。最も符号長が短く、且つパレットコードの一番若い葉は、全てのビットが0になり、逆に符号長が最も長く、且つパレットコードが最大の葉は全てのビットが1になります。符号長の等しい葉の符号は、パレットコードの若いものから順に1ずつ増えていき、符号長が1ビット長くなると、符号に1を加えた後で、末尾に0を付加した形になっていることが、上の例からもわかると思います。
この規則性を利用して、次のような手順で符号長からハフマン符号を再現させることができます。
ハフマン符号の正規化サンプル
/* ハフマン木構造体 */
typedef struct Huffman_Tree {
unsigned char rgb;
unsigned char length; /* 符号長 */
unsigned int count;
struct Huffman_Tree *left;
struct Huffman_Tree *right;
} Huffman_Tree;
/* 2進数の出力 */
void print_bin( double value, unsigned long int size, char *header, char *footer, ... )
{
long int i;
double div;
va_list argp;
va_start( argp, footer );
vprintf( header, argp );
va_end( argp );
if ( size > 0 ) {
div = pow( 2, size - 1 );
for ( i = 0 ; i < size ; i++ ) {
printf( "%ld", (unsigned long int)( value / div ) & 1 );
div /= 2;
}
}
printf( "%s", footer );
}
/* ハフマン符号長の比較 */
int comp_length( d1, d2 )
Huffman_Tree *d1, *d2;
{
if ( d1->left != NULL || d1->right != NULL )
return( 1 );
if ( d2->left != NULL || d2->right != NULL )
return( -1 );
if ( d1->length > d2->length )
return( 1 );
if ( d1->length < d2->length )
return( -1 );
if ( d1->rgb > d2->rgb )
return( 1 );
if ( d1->rgb < d2->rgb )
return( -1 );
return( 0 );
}
/* ハフマン符号の正規化 */
int normalize_huffman_tree( s, e )
Huffman_Tree *s, *e;
{
double huffman_sign = 0;
unsigned long int huffman_length;
qsort( s, e - s, sizeof( Huffman_Tree ), comp_length );
for ( huffman_length = s->length ; s < e ; s++ ) {
if ( s->left != NULL || s->right != NULL ) break;
if ( huffman_length < s->length ) {
for ( huffman_length = s->length - huffman_length ; huffman_length > 0 ; huffman_length-- )
huffman_sign *= 2;
huffman_length = s->length;
}
print_bin( huffman_sign, huffman_length, "palet %d = ", "\n", s->rgb );
huffman_sign++;
}
return( 1 );
}
|
前回、静的ハフマン符号化のサンプルコードで定義したハフマン木の構造体と比較すると、符号長が新たに定義されています。符号長は、親の節のそれから簡単に計算できるので、ハフマン木の生成をするときに格納するようにしておけば、わざわざ計算をしなおす必要はなくなります。
normalize_huffman_treeが正規化のためのメインルーチンになり、引数として、ハフマン木配列の先頭と末尾 + 1のアドレスを渡しています。最初に配列を符号長でソートしていますが、ソート時に使用する比較用の関数がcomp_lengthです。この関数を使うことで、(1)葉の方が優先、(2)葉の中でも符号長が長いものが優先、(3)符号長が同じなら、パレットコードの若い方が優先になり、より配列の前側に集められます。
静的ハフマン符号化では、まず全データからパレット毎のピクセル数をカウントしてからハフマン木を作成、圧縮を行うため、最初に全てのデータを読み込んでから処理を行うことになります。そのため、データを逐次読み込みながら同時に処理を行い、結果を出力するようなことは不可能です。
また、処理後の符号を保持する必要があることから、データ量はその分若干増えることになり、圧縮率は低下してしまいます。
上記問題は、ハフマン木の作成を前処理で行っている以上、避けることのできないものです。この前処理を省略することはできるのでしょうか。
まず、ハフマン木の作成をせずに、はじめからパレットコードに対するハフマン符号を決めておくやり方が考えられます。しかし、よほど特殊な画像に限定しない限り、どの画像にも対応させることなど不可能です。様々な画像パターン用のハフマン符号を作っておいて、最も圧縮率の高いものを利用するようにするのはどうでしょうか。しかしこれも全ての画像に対応することなど不可能に近いし、圧縮率の高いハフマン符号を選択するために、全てのパターンに対して一度圧縮をしなければならないのでは意味がありません。
しかし、このやり方は画像ではなくテキストファイルに限定すれば、そこそこ利用できそうです。アルファベットの出現比率は、普通の英文の場合、'E'が最も高く、逆に'Q'や'J'などはほとんど使われなくなります。この性質を利用して、あらかじめハフマン符号を固定しておくのも一つの手でしょう。ただ、この方式ですと、日本語などの多バイト文字には対応できません。
ハフマン木の作成と、データの圧縮処理を、同時に行うのはどうでしょうか。パレットコードを一つ読み込む毎にハフマン木を更新し、その時のハフマン木を使って符号化するようにしても、データ圧縮は可能です。
データの展開はどうでしょうか。符号を読み込みながらハフマン木を作成し、初めて出現した符号であったのならば、データ列(または別のエリア)からその符号に対するパレットコードを読み込みます(初めて符号化されたパレットコードは、その符号の次に格納するのが一番処理しやすいでしょう)。そうやって、逐次符号を取り出しながらハフマン木を更新して、対応する符号からパレットコードを決定していけば、展開も可能です。
このやり方ならば、ハフマン符号を符号表などにまとめる必要はなく(対応するパレットコードがデータ列の中に埋め込まれるだけで、圧縮率にはほとんど影響しません)、さらにデータを読み込みながら同時に圧縮を行うことも可能になります。
このようなハフマン圧縮の方法を、動的ハフマン符号法(Dynamic Huffman Coding)、または適応型ハフマン符号法(Adaptive Huffman Coding)といいます。それに対して、前回のような符号法は静的ハフマン符号法(Static Huffman Coding)と呼ばれています。
動的ハフマン圧縮の処理の流れを以下に示します。
圧縮データを展開する処理の流れは以下のようになります。
データ列"001211"を処理した場合のハフマン木と出力符号
| 初期状態 | 0,00000000を出力 | 0を出力 | 1,00000001を出力 |
|---|---|---|---|
 |  |
 |  |
| 11,00000010を出力 | 10を出力 | 10を出力 | |
 |  |
 |
上記ハフマン木の節の中にある数値がパレットコードを、外側の数値は出現回数を示しています。
ハフマン木の更新前に、符号を出力しているところに注意してください。更新後の符号を出力してしまうと、正常な復元ができなくなります。
動的ハフマン符号化の処理方法はわかりましたが、ハフマン木の更新はどのようにすればいいでしょうか。データを読み込む度に、静的ハフマン圧縮法でハフマン木を一から作り直しているのでは、処理時間が大幅に増えてしまうことは容易に想像できます。
動的ハフマン符号化を高速に行うための手法としては、 N. Faller, R.G. Gallager, D.E. Knuthがそれぞれ考案・改良を加えたFGK符号化が有名です。この手法は、ハフマン木が成り立つための必要十分条件として
「全ての節は必ず二つの子を持ち、それぞれに重みの小さい順に番号を付けたとき、二つの子の番号は連続しており、且つ親の節の番号は子の節の番号よりも大きくなる」
が成り立つことを利用しています。この条件は、兄弟条件と呼ばれています。
ここで言う重みとは、各データの出現回数を表わし、葉ではない節の部分では、二つの子の節の重みの和となります。つまり、根は全ての葉の重みを合計した値を持つことになります。静的ハフマン圧縮でハフマン木を作成するときに行っている処理を思い浮かべてもらえば、少なくともハフマン木がこの兄弟条件を満たしていることは理解できると思います。
FGK符号化の処理は以下のような流れになります。
FGK符号化ルーチンのサンプル
#define PALET_MAX ( UCHAR_MAX + 1 ) /* パレットコードの最大数 */
#define HUFFMAN_TREE_MAX ( ( PALET_MAX + 1 ) * 2 - 1 ) /* ハフマン木の節の最大数(0-nodeのための節を一つ分追加) */
#define ROOT_INDEX PALET_MAX /* 根のための節のインデックス */
#define RED( color ) ( ( ( color ) >> 16 ) & 0xFF )
#define GREEN( color ) ( ( ( color ) >> 8 ) & 0xFF )
#define BLUE( color ) ( ( color ) & 0xFF )
/* ハフマン木用構造体 */
typedef struct Huffman_Tree {
unsigned char rgb; /* 色成分 */
unsigned char length; /* 符号長 */
double sign; /* ハフマン符号 */
unsigned long int count; /* ノードの重さ */
struct Huffman_Tree *parent; /* 親へのポインタ */
struct Huffman_Tree *left; /* 左側の節へのポインタ */
struct Huffman_Tree *right; /* 右側の節へのポインタ */
} Huffman_Tree;
/* 節に符号と符号長を付加する */
void set_node_length_and_sign( tree, length, sign )
Huffman_Tree *tree;
unsigned char length;
double sign;
{
if ( tree->left != NULL )
set_node_length_and_sign( tree->left, length + 1, sign * 2 );
if ( tree->right != NULL )
set_node_length_and_sign( tree->right, length + 1, sign * 2 + 1 );
tree->length = length;
tree->sign = sign;
}
/* 0-node節の作成 */
void make_zero_node( tree )
Huffman_Tree *tree; /* ハフマン木配列の節 */
{
Huffman_Tree z_node = {
0, /* 色成分 */
0, /* 符号長 */
0, /* ハフマン符号 */
0, /* ノードの重さ */
NULL, /* 親へのポインタ */
NULL, /* 左側の節へのポインタ */
NULL, /* 右側の節へのポインタ */
};
*tree = z_node;
}
/* 新たな0-node節の追加(parentがNULLならば根の作成) */
Huffman_Tree * add_zero_node( parent, tree_end )
Huffman_Tree *parent; /* 親の節 */
Huffman_Tree **tree_end; /* ハフマン木配列の末尾 */
{
make_zero_node( *tree_end );
if ( parent != NULL ) {
( *tree_end )->length = parent->length + 1;
( *tree_end )->sign = parent->sign * 2;
( *tree_end )->parent = parent;
parent->left = *tree_end;
}
( *tree_end )++;
return( *tree_end - 1 );
}
/* 色成分の節(葉)を親につなげる */
Huffman_Tree * add_new_node( rgb, parent, tree_start )
unsigned char rgb; /* 色成分 */
Huffman_Tree *parent; /* 親の節 */
Huffman_Tree *tree_start; /* ハフマン木配列の先頭 */
{
Huffman_Tree *p;
p = &( tree_start[rgb] );
make_zero_node( p );
p->rgb = rgb;
p->length = parent->length + 1;
p->sign = parent->sign * 2 + 1;
p->parent = parent;
return( p );
}
/* 0-nodeに新たな0-nodeと色成分を追加し、0-nodeを返す */
Huffman_Tree * add_new_rgb( rgb, tree_start, tree_end, z_node )
unsigned char rgb; /* 色成分 */
Huffman_Tree *tree_start, **tree_end; /* ハフマン木配列の末尾 */
Huffman_Tree *z_node; /* 0-nodeへのポインタ */
{
Huffman_Tree *parent; /* 親の節(古い0-node) */
parent = z_node;
/* 左側 : 0-node */
z_node = parent->left = add_zero_node( parent, tree_end );
/* 右側 : 新たな色成分 */
parent->right = add_new_node( rgb, parent, tree_start );
return( z_node );
}
/* 通し番号の比較 */
int check_node_id( s, d )
Huffman_Tree *s, *d; /* 自分と相手 */
{
if ( d == NULL ) return( 1 );
/* 符号長は短い方が通し番号が大きい */
if ( s->length < d->length ) return( 1 );
if ( s->length > d->length ) return( -1 );
/* 同じ符号長ならば符号が大きい方が通し番号が大きい */
if ( s->length == d->length ) {
if ( s->sign > d->sign ) return( 1 );
if ( s->sign < d->sign ) return( -1 );
}
return( 0 );
}
/* 同じcountで自分より上位の節を探す */
Huffman_Tree * search_swap_node( s, root_tree )
Huffman_Tree *s;
Huffman_Tree *root_tree;
{
Huffman_Tree *buffer[HUFFMAN_TREE_MAX];
Huffman_Tree **d, **e;
buffer[0] = root_tree;
d = buffer;
e = d + 1;
while ( d < e ) {
/* 0-nodeの兄弟は,自分の親を拾う可能性あるためcheckが必要 */
if ( ( s->count == ( *d )->count ) && ( s->parent != *d ) )
return( *d );
if ( check_node_id( s, ( *d )->right ) < 0 ) {
*e = ( *d )->right;
e++;
}
if ( check_node_id( s, ( *d )->left ) < 0 ) {
*e = ( *d )->left;
e++;
}
d++;
}
return( NULL );
}
/* 節の交換 */
void swap_node( t1, t2, root_tree )
Huffman_Tree *t1, *t2, *root_tree;
{
Huffman_Tree *p;
if ( t1 == t2 ) return;
/* 親とのリンクを交換 */
if ( ( t1->parent ) == ( t2->parent ) ) {
p = ( t1->parent )->left;
( t1->parent )->left = ( t1->parent )->right;
( t1->parent )->right = p;
} else {
if ( ( t1->parent )->left == t1 )
( t1->parent )->left = t2;
else
( t1->parent )->right = t2;
if ( ( t2->parent )->left == t2 )
( t2->parent )->left = t1;
else
( t2->parent )->right = t1;
}
p = t1->parent;
t1->parent = t2->parent;
t2->parent = p;
set_node_length_and_sign( t1->parent, ( t1->parent )->length, ( t1->parent )->sign );
set_node_length_and_sign( t2->parent, ( t2->parent )->length, ( t2->parent )->sign );
}
/* 節を交換しつつ,重さを更新する */
void update_huffman_tree( tree, root_tree )
Huffman_Tree *tree, *root_tree;
{
Huffman_Tree *p;
while ( tree != root_tree ) {
if ( ( p = search_swap_node( tree, root_tree ) ) != NULL ) {
swap_node( tree, p, root_tree );
}
( tree->count )++;
tree = tree->parent;
}
( tree->count )++;
}
/* 入力した色成分からハフマン木を更新し,0-node節のポインタを返す */
Huffman_Tree * fgk_update_huffman( rgb, tree_start, tree_end, z_node )
unsigned char rgb;
Huffman_Tree *tree_start, **tree_end, *z_node;
{
Huffman_Tree *p;
p = &( tree_start[rgb] );
if ( p->parent == NULL )
z_node = add_new_rgb( rgb, tree_start, tree_end, z_node );
update_huffman_tree( p, tree_start + ROOT_INDEX );
return( z_node );
}
/* 動的ハフマン圧縮メイン */
void dynamic_huffman_encode( tree_start )
Huffman_Tree *tree_start;
{
unsigned int color;
unsigned int datasize = 0;
int x, y;
Huffman_Tree *z_node, *root_tree, *tree_end;
for ( x = 0 ; x < PALET_MAX ; x++ )
( tree_start[x] ).parent = NULL;
tree_end = root_tree = tree_start + ROOT_INDEX;
z_node = add_zero_node( NULL, &tree_end );
for ( y = 0 ; y < draw->height ; y++ ) {
for ( x = 0 ; x < draw->width ; x++ ) {
point( x, y, color );
z_node = fgk_update_huffman( RED( color ), tree_start, &tree_end, z_node );
z_node = fgk_update_huffman( GREEN( color ), tree_start, &tree_end, z_node );
z_node = fgk_update_huffman( BLUE( color ), tree_start, &tree_end, z_node );
}
}
}
|
上記サンプル・プログラムは、データを読みながらハフマン木の更新を行っているだけで、圧縮した結果の出力などは全く行っていません。
dynamic_huffman_encodeがメイン・ルーチンになりますが、これは画像から色コードを抽出して、RGB成分に分解しながらfgk_update_huffmanを呼び出す処理だけを行っています。fgk_update_huffmanは、もしパレットコードが初めて出現した場合はadd_new_rgbを使って新たな葉を追加し、その後update_huffman_treeを使ってハフマン木の更新を行っています。パレットコードが初めて出現したかどうかをチェックするために、通常ならばハフマン木の節を検索する必要がありますが、葉の部分は全て、配列の0から255までの間でパレットコードをインデックスとする要素に登録するようにして、一発で検索が完了するようにしています。update_huffman_treeは、交換すべき節がないかをsearch_swap_nodeでチェックして、見つかったらswap_nodeで節を部分木ごと交換します。また、節の重みに1を加える処理もここで行います。この操作を根に到達するまで、親の節をたどりながら繰り返していきます。search_swap_nodeで、重みが一致する節の中から通し番号の一番大きいものを選択するわけですが、実際には通し番号をつける処理は行わず、符号長と符号そのものを使って、自分より符号長が短いか、符号長が同じ場合は符号そのものがより大きい節を見つけるようにします。このような節は、必ず通し番号が自分より大きくなります。この処理は、根から始めてより上位の、同じレベルならより右側の節を常に優先して処理するようにしています。これによって、重みの同じ節が見つかった段階ですぐに結果を返し、それ以降の比較処理を省略することができます。
今まで紹介してきたサンプルを使って、実際にいくつかの画像に対して圧縮処理を行い、その圧縮率を計算してみましょう。
サンプルとして、下に示したようなテストパターンと、以前利用した自然画を使いました。
 |
 |
 |
 |
| テストパターン(1) | テストパターン(2) | テストパターン(3) | 自然画サンプル |
| 画像ファイル | 画像データサイズ (Bits) | ハフマン符号の平均ビット数理論値 (Bits) | 理論値 (%) | 静的ハフマン圧縮 | 動的ハフマン圧縮 | ||
|---|---|---|---|---|---|---|---|
| 圧縮データサイズ (Bits) | 圧縮率 (%) | 圧縮データサイズ (Bits) | 圧縮率 (%) | ||||
| テストパターン(1) | 393216 | 3.42 | 42.78 | 170413 | 43.34 | 173344 | 44.08 |
| テストパターン(2) | 240000 | 3.37 | 42.16 | 103872 | 43.28 | 105920 | 44.13 |
| テストパターン(3) | 1572864 | 7.88 | 98.44 | 1548288 | 98.44 | 1551232 | 98.62 |
| 自然画サンプル | 2062080 | 7.52 | 94.02 | 1946641 | 94.40 | 1950720 | 94.60 |
| 256階調→8階調変換 + 誤差拡散法 | 2062080 | 2.59 | 32.41 | 682142 | 33.08 | 688864 | 33.41 |
| 256階調→4階調変換 + 誤差拡散法 | 2062080 | 1.66 | 20.78 | 445396 | 21.60 | 463552 | 22.48 |
圧縮率は、圧縮後のデータ量と画像データサイズの比率で計算してあります。よって、値が低いほど、圧縮率が高いということになります。
テストパターン(1)は、4色のパレットを使った単純な絵ですが、圧縮率は50%以下と、まずまずの結果が得られました。テストパターン(2)のグラデーション画像についても、半分以下までデータが圧縮されていますが、同じグラデーション画像のテストパターン(3)ではほとんど圧縮効果が見られません。
自然画サンプルに対する圧縮効果はほとんどありません。また、この自然画を減色化処理した場合、階調が小さくなるほど圧縮率は高くなっていることが上の結果からわかると思います。
テスト結果からわかるように、ハフマン圧縮処理は出現するパレットコードの数によってその圧縮率が大きく変化します。使われているパレットコードの数が少ないことがはじめからわかっているような場合には、この処理方法は有効に利用できますが、自然画のようなたくさんの色が使われている画像では、ほとんど効果が望めません。
グラデーション画像は、あらゆる階調のパレットが使用されているため、ほとんど効果が望めないはずですが、テストパターン(2)についてはそこそこの圧縮率を得ることができました。このグラデーション画像は赤成分のみで構成されており、青、緑成分は常に"0"になります。よって、パレットコード"0"の出現回数が他に比べて大幅に高くなり、結果として圧縮率が上がったわけです。このように、データの出現比率の差によっても、圧縮率が変化することが、テスト結果にも表れています。
静的ハフマン圧縮と動的ハフマン圧縮の圧縮率を比較すると、動的ハフマン圧縮の方が若干圧縮率が下がります。上記結果では、符号表のサイズは加えていないのですが、正規化によって符号表を256 Bytesまで小さくしてしまえば、ほとんど差はないと見てよいでしょう。実際にサンプルプログラムを走らせるとわかるのですが、動的ハフマン圧縮処理にかかる時間は静的ハフマン圧縮と比較すると圧倒的に長いので(もっと高速にするための方法はあると思いますが)、圧縮率がほとんど変わらないのなら、よほどの理由がない限りは動的ハフマン圧縮を選択する意味はないように思えます。
圧縮率の理論値に対して、実際の圧縮率が若干低い理由は、計算上最適なビット長が整数に切り上げられる際の誤差が蓄積するためです。例えば、a,b両データの出現比率がそれぞれ75%,25%だった場合、それぞれのビット数の理論値は0.31 Bit,0.50 Bitとなりますが、実際にはどちらも1 Bitの符号に切り上げられてしまいます。
サンプルのソースコードをアップロードしておきます。ご自由にお使い下さい。
サンプルでは前回同様gtkを利用しています。動作確認はTurbolinux 7上で行いました。
make後、huffmanという実行ファイルが作成されます。引数なし実行すると簡単なヘルプが表示されるので、利用する場合はこれを参考にして下さい。
あくまでもサンプルですので、利用される方は充分に気をつけて下さい。
![[Go Back]](../images/back1.png) 前に戻る |
![[Back to HOME]](../images/home1.png) タイトルに戻る |
