JPEG法では、DCT変換結果の符号化にハフマン圧縮を利用していたのに対し、JPEG2000はウェーブレット変換の結果を算術符号化(Arithmetic Coder)で符号化しています。この章では、算術符号化の原理について説明した後、算術符号化の一種であるRange CoderとQ-Coderを紹介します。
算術符号化の説明に入る前に、ハフマン符号化について復習しておきます。ハフマン符号化では、出現率の高いデータに短い符号、逆に出現率の低いデータに長い符号を割り当てることによって、データを圧縮していました。例えば、100個のデータのうち99個がa、残り1個がbだった場合、aに1ビットの符号'0'、bに1ビットの符号'1'を割り当てることで、全体のデータ長は100Bitで表すことができることになります。
ここで、ハフマン符号化の章で紹介した「エントロピー」と言う概念を使って、圧縮可能なBit数の理論限界値を求めてみます。データxが配列中で出現する確率をPxとしたとき、エントロピーの計算式は、
Σ ( -Px X log2Px )
なので、上記の例では -0.99 X log20.99 -0.01 X log20.01 = 0.0808となり、理論的には全体のデータ長を約8Bit程度にまで圧縮できることになります。しかし、ハフマン符号化では符号列のBit数が必ず整数値となるため、理論値とは程遠い結果となってしまいます。
ハフマン圧縮を使って、さらに理論値に近づけるための方法として、データのグルーピングというものがあります。上記の例で、例えばデータ列を2つずつペアにした場合、出現するデータはaaとab(またはba)のいずれかになります。これを符号化すると、全体のデータ長は50Bitとなり、データ一つずつを符号化する場合に比べて圧縮率を高めることができます。まとめるデータの数を増やせばそれだけ圧縮率は高くなりますが、その分処理量も大きくなってしまいます。
整数値の符号長しか使うことができないというハフマン符号化の問題をクリアする符号化として、算術符号化が登場しました。算術符号化は、先ほど説明したデータのグルーピングという考え方を発展させて、データ列全体を一つの符号列として置き換える方法で、1960年代にMassachusetts工科大学(MIT)のP.Eliasによって提唱されました。算術符号化ではデータ列を0と1の間の有理数で表し、符号化と復号化に算術演算を利用するため、この名称が付いたようですが、提唱者名からElias符号化とも呼ばれるようです。
算術符号化のアルゴリズムを、データ列の例として、abacabを使って説明したいと思います。このデータ列の出現率は
| a | 1/2 |
| b | 1/3 |
| c | 1/6 |
となるため、ハフマン符号化を使った場合は aを1Bit、bを2Bit、cを3Bitで表すことで、計10Bitに圧縮することができます。
算術符号化では、まず0から1までの数直線上に、各データを出現率の幅だけ空けて並べていきます。
ここで各データを、数直線上で割り当てた範囲の最小値で表すことにすると、aは0、bは0.5(=1/2)、cは0.833...(=5/6)になります。最初のデータは aになるので、これを数直線上の 0として表すことにします。
二番目のデータを加えると abになりますが、これを数直線上で表すために、上記数直線上の aの範囲(0〜1/2)に、前回同様各データを出現率の幅だけ空けて並べます。
bは数直線上で0.25(=1/4)で表されているため、データ列abは数直線上の0.25と表すことにします。さらにabの範囲(1/4〜5/12)に、各データを出現率の幅だけ空けて並べます。この操作を繰り替えしていきます。
上記の方法で六つのデータを順に符号化した結果、データ列abacabは、数直線上の93/288(=0.3229...)で表すことができることになります。また数直線を見ると、他のデータ列に関してもそれぞれ決められた数値を持つことが分かると思います(例えばabacaaは23/72になります)。このように、算術符号化によってデータ列は0から1の間の有理数に置換されることになるわけです。
さて、符号化された値は有理数なので、場合によっては割り切れない場合も発生します。また、割り切れたとしても桁数が大量になると圧縮率は低下してしまいます(下手すると元のデータ量より多くなってしまいます)。そこで問題になるのが、いったい何桁分まで保持すべきかということになりますが、符号化された数値が一意のデータ列を表している以上、他の符号と区別ができる分の桁数を保持すればいいことになります。例えば上記の例では、対象のデータ列であるabacabが93/288、次のデータ列abacacが281/864なので、その差は281/864 - 93/288 = 1/432となり、1/1000の精度まであれば区別ができます。このとき、小数点以下第4位以降を切り捨てて、abacabは0.322、abacacは0.325になります。
復号処理は、符号化のときと同様に0から1までの数直線を用意して、符号の値がどの範囲にあるかを調べます。上記の例では、0.322は0と1/2の間にあるので、最初のデータはaということになります。次にデータaが持つ範囲0-0.5に、出現率の幅分データを並べる操作も符号化と全く同じです。すると0.322は1/4と5/12の間になるので、二番目のデータはbとなります。これを繰りかえすと、データを復号することができます。
ここで問題となるのが、どこまで復号化を行えばいいかということです。上記方法で処理を行った場合、符号化された値は無限に復号化することができてしまいます。どこで処理を止めればいいか、なんらかの方法で持っておく必要がありますが、一番簡単な方法としては、データ数をあらかじめ持っておくやり方が考えられます。
もうひとつ、大きな問題があります。コンピュータは通常、浮動小数点数の演算をサポートしています。浮動小数点数は有効桁数に制限があるため、今回のようにデータ量によって大量の桁数が必要となるような場合には利用できません。通常の数値演算処理が使用できないため、新たに演算用のプログラムを用意する必要があります。しかし、まともに全桁に対して演算処理を行えば、桁数が増える毎に処理時間は増大してしまい、実用的なプログラムにはなりません。下位の桁に対してのみ演算を行い、オーバーフローしたら上位の桁の数を変更するような処理が必要となります。ところで、この方法で本当に圧縮ができるのか、不思議に思うかもしれません。圧縮率は、他の符号と識別可能な精度に依存します。上記の例では各符号との値の幅は1/432でしたが、これを二進数で表すと1/110110000になるため、9 Bitsの符号で表せることになります。元の符号は三種類のデータを持っているため、最低でも一つのデータに対して2 Bitsは必要になります。つまり元のデータは(なんらかの符号化をしていない限り)最低でも2 X 6 = 12 Bitsは必要になり、確かに圧縮されていることになります。
0と1が、等しい頻度で発生するデータ列があるとします。どちらのデータが出現しても、数直線の幅は常に1/2(二進数で1/10)ずつ小さくなるため、必要な精度は毎回1 Bitずつ増えていくことになります。つまりこのときは、全く圧縮がされないことになります。
しかし、例えば0の出現頻度が1/100、1のそれが99/100である場合、1が出現しても数直線の幅に大きな変化は表れません。つまり符号を識別するための精度も少なくすることができ、結果的に圧縮できることになります。
出現する確率がpであるデータを符号化したとき、他の符号と識別するために必要な精度を確保するために
log2( 1/p ) = -log2( p )
の量のビットを出力する必要があります。出現頻度が1/2ならば1 Bit出力しなければなりませんが、出現頻度が99/100ならば約0.0145 Bitを出力するだけで済みます。ハフマン符号化と同様に、出現率の高いデータは少ない情報量で表していることになるわけです。
前の章でも述べたように、符号を表す数直線上の値を算出するためには、通常の演算以外の方法を使う必要があります。算術圧縮時に利用する方法として、ある精度まで到達した時点で数値を定数倍(例えば10倍)して、オーバーフローした分だけ出力する処理がよく用いられます。このとき、数値を定数倍すると同時に数直線上の範囲の幅も同じ定数を掛ける必要があります。
Range Coderではさらに、符号化と復号化を高速に行うため、データの入出力をビット単位ではなくバイト単位にし、かつ整数演算処理のみを使います。基本的な処理方法は算術圧縮法と変わりませんが、算術圧縮法の特許が認可される前にこの方法が論文によって発表されていたため、特許フリーの算術圧縮法として注目されています。
Range Coderでは、数直線の幅(以下Rangeと略します)を1ではなく大きな整数で初期化します。データを一つ読み込んだ後、符号とRangeを計算する仕組み自体は算術符号化と変わりませんが、整数演算を用いて計算されるところが異なります。具体的には、データの大きさをSize、読み込んだデータの出現回数をCount、累積出現回数(前のデータの出現回数の総和)をAccumとしたとき、
新たな符号 = 現在の符号 + ( Range / Size ) * Accum Range = ( Range / Size ) * Count
として計算することができます。
処理を進めるうちに、Rangeの値は小さくなっていきます。よって、ある定数値より小さくなったら、符号とRangeを定数倍します。つまり、数直線を定数倍して大きくすることで精度を保つわけです。符号を定数倍するとオーバーフローしてしまうため、上位ビットは符号列として出力して切り捨てます。
Range Coderによる符号化の例を、算術符号化のときに使った例を利用して示します。
データ列abacab
| データ | 出現回数 | 累積出現回数 |
|---|---|---|
| a | 3 | 0 |
| b | 2 | 3 |
| c | 1 | 5 |
Range Coder符号化処理時の値の変化
| データ | 符号 | Range |
|---|---|---|
| 初期値 | 0 | 100 |
| a | 0 + (100/6) x 0 = 0 | (100/6) x 3 = 48 |
| b | 0 + (48/6) x 3 = 24 | (48/6) x 2 = 16 |
| a | 24 + (16/6) x 0 = 24 | (16/6) x 3 = 6 |
| Rangeを10倍 | 240 | 60 |
| 符号の3桁目(2)を出力 | 40 | 60 |
| c | 40 + (60/6) x 5 = 90 | (60/6) x 1 = 10 |
| a | 90 + (10/6) x 0 = 90 | (10/6) x 3 = 3 |
| Rangeを10倍 | 900 | 30 |
| 符号の3桁目(9)を出力 | 0 | 30 |
| b | 0 + (30/6) x 3 = 15 | (30/6) x 2 = 10 |
Range Coder符号化処理による数直線の変化は、以下のようになります。
上記の例では、Rangeの初期値を100としています。Rangeが10より小さくなったら符号とRangeを10倍し、符号の3桁目を符号列に出力しています。最後のデータまで符号化を行ったら、その時点での符号を符号列に出力して処理を完了します。この処理で、符号は'2915'になりました。
復号化処理でも、Rangeの初期値は符号化と同じ値を思います。また、符号化したデータの先頭の値を取得して、それを符号の初期値とします。符号をRange / Sizeで割り、その値を累積出現回数と比較して、範囲内にあったデータを復号化されたデータとして出力した後、符号とRangeを以下の式で再計算します。
新たな符号 = 現在の符号 - ( Range / Size ) * 復号したデータの累積出現回数 Range = ( Range / Size ) * 復号したデータの出現回数
「( Range / Size ) * 復号したデータの累積出現回数」は、それまでに復号化したデータを表す数直線上の値になるため、新たな符号はそれと現状の符号との誤差を示しています。この誤差を、次の復号のために使用するわけです。言葉では説明が難しいのですが、下記の例で示した図を見れば容易に理解できると思います。
符号化の場合と同様に、Rangeがある値より小さくなったら、符号とRangeを定数倍します。また、符号は定数倍した後、符号データから下位ビットを補うことで、必要な精度を保ちます。
Range Coder復号化処理時の値の変化
| 符号/(Range/Size) | 出力データ | 符号 | Range |
|---|---|---|---|
| 初期値 | 29 | 100 | |
| 29 / (100/6) = 1 | a | 29 - (100/6) x 0 = 29 | (100/6) x 3 = 48 |
| 29 / (48/6) = 3 | b | 29 - (48/6) x 3 = 5 | (48/6) x 2 = 16 |
| 5 / (16/6) = 2 | a | 5 - (16/6) x 0 = 5 | (16/6) x 3 = 6 |
| Rangeを10倍 | 50 | 60 | |
| 符号データから下位ビットを取得 | 51 | 60 | |
| 51 / (60/6) = 5 | c | 51 - (60/6) x 5 = 1 | (60/6) x 1 = 10 |
| 1 / (10/6) = 1 | a | 1 - (10/6) x 0 = 1 | (10/6) x 3 = 3 |
| Rangeを10倍 | 10 | 30 | |
| 符号データから下位ビットを取得 | 15 | 30 | |
| 15 / (30/6) = 3 | b | 15 - (30/6) x 3 = 0 | (30/6) x 2 = 10 |
Range Coder復号化処理による数直線の変化は、以下のようになります。
復号化の場合、数直線は常に0からRangeまでの範囲になります。符号が数直線上のどこに位置しているのかをチェックして、Rangeを復号化されたデータが持つ範囲に変換するところは、やはり算術符号化での処理と本質的に変わりありません。
処理方法は以上になりますが、ここでいくつかの問題を解決する必要があります。まず一つは、符号化と復号化での計算で使用している変数Range / Sizeが0になる可能性があるということで、このときはRangeを計算した結果が0になってしまうため、処理を続けることができなくなります。よってRangeの取り得る最小値は、データのサイズより大きくなければなりません。Range / Sizeが0になった場合、サンプル・プログラムでは単純にエラー終了しています。Rangeの最小値はサンプル・プログラム内の定数値RANGE_CODER_MIN_RANGEで定義され、その値は2の24乗(=4096 X 4096)になります。つまり、この大きさのデータまでは処理が可能であるということになります。
もう一つの問題は、符号化処理時に新たな符号を計算する際、オーバーフローが発生する可能性があると言うことです。処理の流れから見て、符号はRangeの最大値を越えることはできません。もし越えた場合、オーバーフローした場合のビットは捨てられてしまうことになります。サンプル・プログラムでは、符号の上位1ビットをキャリー・ビットとして、Rangeと符号を定数倍する前に、キャリー・ビットをチェックし、1が立ったらそのビットを前の符号に加算する処理を行っています。前の符号の全ビットが立っている状態である場合、さらにその前の符号に加算する処理を続ける必要があります。
以下に、サンプル・プログラムを示します。
#define UCHAR_MAX 255
#define CHAR_BIT_SIZE 8
/*
Range Coder用パラメータ
*/
enum RANGE_CODER_PARAM {
/* rangeのビット数 */
RANGE_CODER_RANGE_BIT_SIZE = 31,
/* 最大データサイズのビット数 */
RANGE_CODER_MAX_DATA_BIT_SIZE = 24,
/* rangeの初期値 */
RANGE_CODER_INIT_RANGE = 1 << RANGE_CODER_RANGE_BIT_SIZE,
/* rangeが取り得る最小値 */
RANGE_CODER_MIN_RANGE = 1 << RANGE_CODER_MAX_DATA_BIT_SIZE,
/* codeの最大値 */
RANGE_CODER_MAX_CODE = RANGE_CODER_INIT_RANGE,
/* range用のマスクパターン */
RANGE_CODER_RANGE_MASK = (unsigned int)RANGE_CODER_INIT_RANGE - 1,
};
typedef unsigned int UInt;
typedef unsigned char UChar;
/*
データの出現頻度をカウントする
UChar* data : データ列
UInt* count : 出現頻度を保持するデータ列
UInt size : dataのデータ長
*/
void count_data( UChar* data, UInt* count, UInt size )
{
int i;
/* 出現頻度の初期化 */
for ( i = 0 ; i < UCHAR_MAX + 1 ; i++ )
count[i] = 0;
for ( i = 0 ; i < size ; i++ )
count[ (UInt)( *data++ ) ]++;
}
/*
データの累積出現頻度を計算する
UInt* count : 出現頻度データ列
UInt* accum : 累積出現頻度を保持するデータ列
戻り値 : 出現頻度の総数
*/
UInt accum_count( UInt* count, UInt* accum )
{
int i;
accum[0] = 0;
for ( i = 1 ; i < UCHAR_MAX + 1 ; i++ )
accum[i] = accum[i-1] + count[i-1];
return( accum[UCHAR_MAX] + count[UCHAR_MAX] );
}
/*
符号のオーバーフロー分を、前の符号に加える
UChar* e : 現在の符号列へのポインタ
UChar* start : 符号列の先頭(番人)
UInt buffer_cnt : バッファ部分に登録されているビット数
戻り値 : 成功 = 1 , アンダーフロー = 0
*/
int add_overflow_data( UChar* e, UChar* start, UInt buffer_cnt )
{
UInt i;
/* 最初にバッファ部分に加算する */
i = *e + 1;
*e = i & ( ( 1 << buffer_cnt ) - 1 );
/* バッファもオーバーフローしている場合、その前の符号にも加算する */
if ( i >= ( 1 << buffer_cnt ) ) {
do {
if ( --e < start ) return( 0 );
i = *e + 1;
*e = i & UCHAR_MAX;
} while ( i > UCHAR_MAX );
}
return( 1 );
}
/*
バッファ位置をひとつ後ろにずらす
UChar** encode : 現在のバッファ位置
UChar* encode_end : 確保した符号列領域の末尾
UInt* buffer_cnt : バッファ内に登録されたビット数
戻り値 : 成功 = 1 , バッファが足りない = 0
*/
int flush_buffer( UChar** encode, UChar* encode_end, UInt* buffer_cnt )
{
if ( *encode >= encode_end ) {
return( 0 );
}
*( ++( *encode ) ) = 0;
*buffer_cnt = 0;
return( 1 );
}
/*
Range Coder符号化
UChar* data : データ列
UChar* data_end : データ列の末尾 + 1
UChar* encode : 符号データ列
UChar* encode_end : 符号データ列の末尾 + 1
UInt* count : データの出現頻度
UInt* accum : データの累積出現頻度
UInt size : データ列のサイズ
戻り値 : 符号化したデータの末尾 + 1
*/
char* range_encode( UChar* data, UChar* data_end, UChar* encode, UChar* encode_end, UInt* count, UInt* accum, UInt size )
{
/*
code = 0
+----------------------------------------+
<---- range = RANGE_CODER_INIT_RANGE ---->
*/
UInt range = RANGE_CODER_INIT_RANGE;
UInt code = 0;
UInt unit;
UInt buffer_cnt = 0;
UChar* c;
UChar* e = encode;
for ( c = data ; c < data_end ; c++ ) {
unit = range / size;
if ( unit == 0 ) return( NULL );
/*
code(c) code(c+1)
+----------------+------------------------------+
<- accum * unit ->
<---- range = count * unit ---->
( unit = range / size )
*/
code += unit * accum[(UInt)*c];
range = unit * count[(UInt)*c];
if ( code >= RANGE_CODER_MAX_CODE ) {
if ( ! add_overflow_data( e, encode, buffer_cnt ) ) {
return( NULL );
}
code -= RANGE_CODER_MAX_CODE;
}
while ( range < RANGE_CODER_MIN_RANGE ) {
if ( buffer_cnt >= CHAR_BIT_SIZE )
if ( ! flush_buffer( &e, encode_end, &buffer_cnt ) ) return( NULL );
*e = ( *e << 1 ) + ( ( code >> ( RANGE_CODER_RANGE_BIT_SIZE - 1 ) & 1 ) );
code = ( code << 1 ) & RANGE_CODER_RANGE_MASK;
range <<= 1;
buffer_cnt++;
}
}
int i;
for ( i = 0 ; i < RANGE_CODER_RANGE_BIT_SIZE ; i++ ) {
if ( buffer_cnt >= CHAR_BIT_SIZE )
if ( ! flush_buffer( &e, encode_end, &buffer_cnt ) ) return( NULL );
*e = ( *e << 1 ) + ( ( code >> ( RANGE_CODER_RANGE_BIT_SIZE - 1 ) & 1 ) );
code <<= 1;
buffer_cnt++;
}
if ( buffer_cnt > 0 )
*e++ <<= ( CHAR_BIT_SIZE - buffer_cnt );
return( e );
}
/*
復号データの検索
UInt64* code : 符号
UInt64* unit : range/データ総数
UInt* accum : データの累積出現頻度
戻り値 : 復号したデータ
*/
UChar find_decode_data( UInt code, UInt* accum )
{
UInt c;
for ( c = 0 ; c < UCHAR_MAX ; c++ )
if ( ( accum[c] <= code ) && ( code < accum[c + 1] ) )
break;
return( c );
}
/*
バッファに符号列の要素をひとつ読み込む
UChar** encode : 現在のバッファ位置
UChar* encode_end : 確保した符号列領域の末尾
UChar* buffer : 読み込んだ符号列を登録するバッファ
UInt* buffer_cnt : バッファ内に登録されたビット数
戻り値 : 成功 = 1 , バッファが足りない = 0
*/
int get_buffer( UChar** encode, UChar* encode_end, UChar* buffer, UInt* buffer_cnt )
{
if ( *encode >= encode_end ) {
return( 0 );
}
*buffer = **encode;
( *encode )++;
*buffer_cnt = 0;
return( 1 );
}
/*
Range Coder復号化
UChar* encode : 符号データ列
UChar* encode_end : 符号データ列の末尾 + 1
UChar* data : データ列
UChar* data_end : データ列の末尾 + 1
UInt* count : データの出現頻度
UInt* accum : データの累積出現頻度
UInt size : データ列のサイズ
戻り値 : 成功 = 1 , 失敗 = 0
*/
int range_decode( UChar* encode, UChar* encode_end, UChar* data, UChar* data_end, UInt* count, UInt* accum, UInt size )
{
int i;
UInt range = RANGE_CODER_INIT_RANGE;
UInt code = 0;
UInt unit;
UChar buffer = 0;
UInt buffer_cnt = 8;
UChar* data_start = data;
for ( i = 0 ; i < RANGE_CODER_RANGE_BIT_SIZE ; i++ ) {
if ( buffer_cnt >= CHAR_BIT_SIZE )
if ( ! get_buffer( &encode, encode_end, &buffer, &buffer_cnt ) ) return( 0 );
code = ( code << 1 ) + ( buffer >> ( CHAR_BIT_SIZE - 1 ) );
buffer <<= 1;
buffer_cnt++;
}
while ( ( data < data_end ) && ( encode < encode_end ) ) {
unit = range / size;
if ( unit == 0 ) return( 0 );
UChar c = find_decode_data( code / unit, accum );
*data++ = c;
code -= unit * accum[(UInt)c];
range = unit * count[(UInt)c];
while ( range < RANGE_CODER_MIN_RANGE ) {
if ( buffer_cnt >= CHAR_BIT_SIZE )
if ( ! get_buffer( &encode, encode_end, &buffer, &buffer_cnt ) ) return( 0 );
code = ( code << 1 ) + ( buffer >> ( CHAR_BIT_SIZE - 1 ) );
buffer <<= 1;
buffer_cnt++;
range <<= 1;
}
}
return( 1 );
}
/*
Range Coderテスト
戻り値 : 成功 = 1 , 失敗 = 0
*/
int range_coder_test()
{
UChar data[100];
UInt count[UCHAR_MAX + 1];
UInt accum[UCHAR_MAX + 1];
UChar encode[sizeof( data )];
int i;
for ( i = 0 ; i < sizeof( data ) - 1 ; i++ )
data[i] = (int)( (double)rand() / ( (double)RAND_MAX + 1 ) * (int)( 'z' - 'a' ) ) + 'a';
data[sizeof(data) + 1] = '\0';
printf( "%s\n", data );
count_data( data, count, sizeof( data ) );
accum_count( count, accum );
char* encode_end = range_encode( data, data + sizeof( data ),
encode, encode + sizeof( encode ),
count, accum, sizeof( data ) );
if ( encode_end == NULL ) return( 0 );
range_decode( encode, encode_end,
data, data + sizeof( data ),
count, accum, sizeof( data ) );
printf( "%s\n", data );
return( 1 );
}
|
Range Coderでは通常、符号の上位ビットをバイト単位で符号列へ出力するのですが、サンプル・プログラムでは1ビットずつ符号列に書き込んで、1バイト分書き込んだら符号列へのポインタを一つ進めるやり方にしています。
ハフマン符号化の章で使ったサンプルを使って、Range Coderによる符号化処理を評価した結果を以下に示します。
 |
 |
 |
 |
| テストパターン(1) | テストパターン(2) | テストパターン(3) | 自然画サンプル |
| 画像ファイル | 一成分あたりの 画像サイズ (Bits) | 色成分 | 平均ビット数 理論値 (Bits) | 圧縮率 理論値 (%) | Range Coder圧縮率 | |||||
|---|---|---|---|---|---|---|---|---|---|---|
| RANGEサイズ = 18 Bits | RANGEサイズ = 24 Bits | RANGEサイズ = 30 Bits | ||||||||
| 圧縮サイズ (Bits) | 圧縮率 (%) | 圧縮サイズ (Bits) | 圧縮率 (%) | 圧縮サイズ (Bits) | 圧縮率 (%) | |||||
| テストパターン(1) | 131072 | R | 1.837 | 22.963 | 30664 | 23.395 | 30136 | 22.992 | 30136 | 22.992 |
| G | 1.837 | 22.963 | 30664 | 23.395 | 30136 | 22.992 | 30136 | 22.992 | ||
| B | 1.837 | 22.963 | 30664 | 23.395 | 30136 | 22.992 | 30136 | 22.992 | ||
| テストパターン(2) | 80000 | R | 7.365 | 92.063 | 73872 | 92.340 | 73680 | 92.100 | 73688 | 92.110 |
| G | 0.000 | 0.000 | 32 | 0.040 | 32 | 0.040 | 32 | 0.040 | ||
| B | 0.000 | 0.000 | 32 | 0.040 | 32 | 0.040 | 32 | 0.040 | ||
| テストパターン(3) | 524288 | R | 7.875 | 98.438 | 516120 | 98.442 | 516120 | 98.442 | 516128 | 98.444 |
| G | 7.875 | 98.438 | 516120 | 98.442 | 516120 | 98.442 | 516128 | 98.444 | ||
| B | 7.875 | 98.438 | 516120 | 98.442 | 516120 | 98.442 | 516128 | 98.444 | ||
| 自然画サンプル | 687360 | R | 7.433 | 92.911 | 653064 | 95.010 | 638888 | 92.948 | 638672 | 92.917 |
| G | 7.401 | 92.507 | 651136 | 94.730 | 636112 | 92.544 | 635888 | 92.512 | ||
| B | 7.374 | 92.178 | 648648 | 94.368 | 633848 | 92.215 | 633632 | 92.183 | ||
| 256階調→8階調変換 + 誤差拡散法 | 687360 | R | 2.533 | 31.657 | 233080 | 33.909 | 217848 | 31.693 | 217632 | 31.662 |
| G | 2.522 | 31.528 | 230624 | 33.552 | 216968 | 31.565 | 216744 | 31.533 | ||
| B | 2.469 | 30.863 | 234704 | 34.146 | 212384 | 30.899 | 212176 | 30.868 | ||
| 256階調→4階調変換 + 誤差拡散法 | 687360 | R | 1.680 | 20.995 | 164496 | 23.932 | 144568 | 21.032 | 144352 | 21.001 |
| G | 1.660 | 20.753 | 156848 | 22.819 | 142904 | 20.790 | 142688 | 20.759 | ||
| B | 1.514 | 18.925 | 151856 | 22.093 | 130336 | 18.962 | 130120 | 18.930 | ||
ハフマン符号化のサンプル・プログラムと異なり、RGB各成分で独立して符号化を行ったため、ハフマン符号処理との完全な比較はできなかったのですが、特殊な画像を除けば算術符号化(Range Coder)の方が高い圧縮率を示していました。理論値と比較してもかなり値が近くなっています。
それでも理論値と等しくならないのは、Range Coderが符号とRangeの計算を整数演算で行っているため、精度が若干落ちるためです。Rangeの取り得る最小値を大きくすると、それだけ圧縮率は高くなり、理論値に近付いていることが上表からも分かると思いますが、これはRangeがある程度大きくなればそれだけ精度が高くなり、より理論値に近付くからです。
ハフマン符号化では、動的(適応型)ハフマン符号化というものがありました。これはハフマン木の作成と符号化処理を並列で行うやり方で、データを全て読み込んで出現頻度を調べてから符号化処理をする必要がないため、逐次データを読み込みながら符号化を行いたい場合に利用することができました。これは算術符号化でも利用できる手段であり、例えば出現頻度の初期値を全データに対して1としておいて、一つのデータを符号/復号化する度に更新することで簡単に対応できます。以下に、Range Coderで示した例と同じサンプル・データを利用して、実際に適応型の符号化・復号化を行った例を示します。
データ列abacab
| データ | 符号 | Range | 出現回数 | 累積出現回数 | ||||
|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | c | |||
| 初期値 | 0 | 100 | 1 | 1 | 1 | 0 | 1 | 2 |
| a | 0 + (100/3) x 0 = 0 | (100/3) x 1 = 33 | 2 | 1 | 1 | 0 | 2 | 3 |
| b | 0 + (33/4) x 2 = 16 | (33/4) x 1 = 8 | 2 | 2 | 1 | 0 | 2 | 4 |
| Rangeを10倍 | 160 | 80 | ||||||
| 符号の3桁目(1)を出力 | 60 | 80 | ||||||
| a | 60 + (80/5) x 0 = 60 | (80/5) x 2 = 32 | 3 | 2 | 1 | 0 | 3 | 5 |
| c | 60 + (32/6) x 5 = 85 | (32/6) x 1 = 5 | 3 | 2 | 2 | 0 | 3 | 5 |
| Rangeを10倍 | 850 | 50 | ||||||
| 符号の3桁目(8)を出力 | 50 | 50 | ||||||
| a | 50 + (50/7) x 0 = 50 | (50/7) x 3 = 21 | 4 | 2 | 2 | 0 | 4 | 6 |
| b | 50 + (21/8) x 4 = 58 | (21/8) x 2 = 4 | 4 | 3 | 2 | 0 | 4 | 7 |
符号列1858
| 符号/(Range/Size) | 出力データ | 符号 | Range | 出現回数 | 累積出現回数 | ||||
|---|---|---|---|---|---|---|---|---|---|
| a | b | c | a | b | c | ||||
| 初期値 | 18 | 100 | 1 | 1 | 1 | 0 | 1 | 2 | |
| 18 / (100/3) = 0 | a | 18 - (100/3) x 0 = 18 | (100/3) x 1 = 33 | 2 | 1 | 1 | 0 | 2 | 3 |
| 18 / (33/4) = 2 | b | 18 - (33/4) x 2 = 2 | (33/4) x 1 = 8 | 2 | 2 | 1 | 0 | 2 | 4 |
| Rangeを10倍 | 20 | 80 | |||||||
| 符号データから下位ビットを取得 | 25 | 80 | |||||||
| 25 / (80/5) = 1 | a | 25 - (80/5) x 0 = 25 | (80/5) x 2 = 32 | 3 | 2 | 1 | 0 | 3 | 5 |
| 25 / (32/6) = 5 | c | 25 - (32/6) x 5 = 0 | (32/6) x 1 = 5 | 3 | 2 | 2 | 0 | 3 | 5 |
| Rangeを10倍 | 0 | 50 | |||||||
| 符号データから下位ビットを取得 | 8 | 50 | |||||||
| 8 / (50/7) = 1 | a | 8 - (50/7) x 0 = 8 | (50/7) x 3 = 21 | 4 | 2 | 2 | 0 | 4 | 6 |
| 8 / (21/8) = 4 | b | 8 - (21/8) x 4 = 0 | (21/8) x 2 = 4 | 4 | 3 | 2 | 0 | 4 | 7 |
適応型の処理の場合、累積出現回数を毎回算出し直す必要があるため、初めから出現頻度を計算する場合に比べると処理時間は長くなります。また、最初は出現頻度の偏りがないことから、圧縮率も低下する傾向にあります。しかし、最初から全てのデータを読み込んでから処理することができない場合、例えばデータを他の変換処理で加工しながら、並行して算術符号化を行いたい場合は、この方法は有効な手段になります。
ところで、Range Coderのサンプル・プログラムでは0〜255までのデータを符号化処理しましたが、算術符号化の場合は、二進数に変換して0か1の二つのデータとして処理することが可能です。このような算術符号化は、二進算術符号化(binary arithmetic coding)と呼ばれています。数直線は0と1の二つのエリアに分割されるだけで済むため、その分処理も単純にすることが可能になります。
Q-Coderは、IBMが開発した適応型二進算術符号化(adaptive binary arithmetic coding)であり、JPEG2000ではこの発展形であるMQ-Coderが利用されています。Q-Coderの特徴として、符号化する値が実際の値(0か1)ではなく、MPS(More Probable Symbol)とLPS(Less Probable Symbol)という二つのシンボルであることが挙げられます。実際の値に関係なく、出現確率の高い側を前者、低い側を後者として表し、符号化を行います。数直線は二つのエリアに分かれ、0に近い側がLPS、遠い側がMPSとなります。
Range Coderと同じように、Rangeはある一定の幅を保つように正規化(renormalization)を行います。Q-CoderではRangeのことを確率区間幅Aとして表し、常に0.75〜1.5の範囲に保持します。このとき、Aの値は1に近似されることになります。
LPSの発生する確率をQeとしたとき、数直線上のMPSとLPSの幅は以下のように計算することができます。
LPSの幅 = Qe X A (4.1)' MPSの幅 = A - ( Qe X A ) (4.2)'
しかし、Aは1に近似できるため、上式は以下のように近似することができます。
LPSの幅 = Qe (4.1) MPSの幅 = A - Qe (4.2)
Q-Coderも算術符号化の一種なので、符号と確率区間幅Aを毎回更新することになります。入力データはLPSとMPSの二つなので、それぞれの符号化は次のように処理すればいいことになります。この処理においては加算以外の演算が不要になるため、実装を単純化することができ、特に処理回数の多い場所であることから高速な処理が期待できます。実装が単純な分、ハードウェアへの実装がしやすいという特徴もあります。
| LPS | MPS | |
|---|---|---|
| 符号 C | C | C + Qe |
| 確率区間幅 A | Qe | A - Qe |
前に述べたように、Q-CoderではRange Coder同様、確率区間幅Aがある一定の値より小さくなったときに符号とAを定数倍します。Q-Coderでは、Aが0.75より小さくなったらそれぞれを2倍して、Aが常に0.75〜1.5の範囲にあるように調整を行います。符号は常に大きくなるので、一定回数正規化処理を行ったら上位のビットを符号列として出力します。また、Range Coderと同様に桁上り(Carry Over)が発生する場合がありますが、Q-Coderではビット・スタフィング(Bit Stuffing)という方法を使って解決しています。この方法は、前の符号の全ビットが立っていた場合(=0xFF)、キャリー・ビットを冗長な1ビットとして出力するというもので、これにより桁上りによる再計算を回避することができます。
符号と確率区間幅Aの更新は近似式を用いているため、LPSの幅がMPSのそれよりも大きくなる場合が発生します。例えば、Qe = 0.48、A = 0.88のとき、正確に計算すれば
LPSの幅 = 0.48 X 0.88 = 0.42 MPSの幅 = 0.88 - ( 0.48 X 0.88 ) = 0.46
になりますが、近似式を使うと
LPSの幅 = 0.48 MPSの幅 = 0.88 - 0.48 = 0.40
となり、大きさが逆転してしまいます。このため、大小関係の逆転が発生した場合はLPSとMPSそれぞれを示す区間も逆転させる必要があります。これをMPSとLPSの状態交換(conditional exchange)と言います。
算術符号化処理でのもうひとつ重要な処理として、出現頻度の算出がありますが、Q-Coderではここでも処理を単純化するために、確率推定(Probability Estimate)という方法を使っています。文字通りきちんと出現頻度を計算する代わりに、推定した値を使って処理を行うというものですが、推定値を入力した値に応じて適正なものに保つために、正規表現でも紹介した有限オートマトン(Finite state Automaton : 有限状態機械)を利用しています。この有限オートマトンにはそれぞれ番号が振られ、一つのオートマトンに対してQe値、LPS/MPSそれぞれの符号化時に次の状態へ移るための番号、LPS/MPSの符号入れ換えを行うかどうかを示すフラグが定義されています。
MPS符号化時は、Qeは減少する傾向にあるため、状態もそのようになるよう遷移する番号が振られています。逆にLPS符号化時は、Qeが増加するように遷移します。また、常にMPS符号が発生した場合、Qeは最小値のまま常に同じ状態を遷移し続けることになります。
算術符号化処理の紹介は以上になります。JPEG2000では、エンベデッド符号化の一つであるEBCOTとQ-Coderの発展形であるMQ-Coderを組み合わせて使用しており、最初はこの内容まで一度に紹介しようと思っていましたが、そうなると量がかなり多くなってしまうため、次章にて紹介することにします。
Range Coderのサンプル・ソースをアップロードしておきます。御自由にお使い下さい。
![[Go Back]](../images/back1.png) 前に戻る |
![[Back to HOME]](../images/home1.png) タイトルに戻る |
