4ビット及び8ビットのBMPファイルで利用可能な圧縮方式であるRLEの解説。 #contents *概要 [#about] **RLEとは [#about-rle] @dfn{RLE};とは、Run Length Encodingの略で、データの可逆圧縮方式の1つである。~ 同一の値が連続するようなデータの圧縮に効果を発揮する。 例えば、次の図のようなデータの並びを考える。 #ref(非圧縮データ例1.png,left,nolink,|1|1|1|1|2|3|3|3|3|3|3|4|4|4|) このデータを口で説明すると、「最初に @code{1}; が4個、次に @code{2}; が1個、次に @code{3}; が6個、最後に @code{4}; が3個」となる。~ そして、この説明文を形にしたものがRLEである。~ 即ち、上の図のデータは次の図のように圧縮される。 #ref(例1のRLEデータ.png,left,nolink,|4|1|1|2|6|3|3|4|) このようにRLEでは、連続するデータ値を [値の連続数][値] という形式で表す。~ 上の2つの図からもわかる通り、この例では14バイトの元データが8バイトに圧縮されている。 上の例において、データ値 @code{2}; については @code{1 2}; とエンコードされており、1バイトから2バイトに増えてしまっている。~ 一般に、あるN個の値が羅列されたデータにRLEを施した場合、最も圧縮効率が良いのは全ての値が同一だった場合であり、エンコード後のデータは最小で2個になる。~ 反対に、最も圧縮効率が悪いのは全ての値が連続していない場合であり、エンコード後のデータはN×2個、即ち元の2倍の量になってしまう。 **絶対モード [#about-absolute] BMPにおけるRLEでは、上述のようなデータの膨張を軽減するために、@dfn{絶対モード};というものが存在する。~ 絶対モード内のデータはエンコードされずにそのままの形で格納される。 例えば、次の図のようなデータの並びを考える。 #ref(非圧縮データ例2.png,left,nolink,|1|1|1|2|3|4|5|6|7|8|8|8|8|) このデータに通常のRLEを施すと、次の図のようになる。 #ref(例2の絶対モード無しRLEデータ.png,left,nolink,|3|1|1|2|1|3|1|4|1|5|1|6|1|7|4|8|) 上の2つの図からもわかる通り、13バイトの元データが16バイトに膨張してしまっている。 ここで、 [エスケープコード][値の連続数][値][値]… という形式の絶対モードを導入する。~ エスケープコードは絶対モードの開始位置を示すためのもので、ここでは @code{0}; とする。~ 膨張の原因となっている箇所に対して絶対モードを適用した場合のデータを次の図に示す。 #ref(例2の絶対モード有りRLEデータ.png,left,nolink,|3|1|0|6|2|3|4|5|6|7|4|8|) 絶対モードを導入することで、13バイトの元データが12バイトに圧縮されており、膨張が抑えられたといえる。~ 絶対モードは、3個以上の同一でない値の羅列に対して膨張抑止効果を持つ。 *RLEデータの構造 [#struct] BMPにおけるRLEは、[[イメージデータ>../バイナリ構造#image-data]]の[[行データ>../バイナリ構造#image-data-line]]単位で施される。~ RLEを施す対象となる[[イメージデータ>../バイナリ構造#image-data]]での[[行データ>../バイナリ構造#image-data-line]]の格納順は、イメージ表示時に下に来る行ほど最初に格納されるボトムアップ形式でなければならず、トップダウン形式は認められない。 BMPにおけるRLEを施されたデータは、以下の5種類の構成要素の集合となる。 -[[エンコードデータ>#struct-encoded]] -[[絶対モードデータ>#struct-absolute]] -[[行データの終わり>#struct-eol]] -[[イメージデータの終わり>#struct-eob]] -[[位置移動情報>#struct-delta]] これら各構成要素は、必ず2バイトの整数倍のサイズ(ワードアラインメント)でなければならない。~ [[絶対モードデータ>#struct-absolute]]はピクセル数によっては2バイトの整数倍のサイズにならない場合があるが、その場合は2バイトの整数倍のサイズになるように @code{0}; で埋める。 [[概要>#about]]においては値の連続数はバイト単位として解説したが、実際のBMPにおけるRLEでは、値の連続数はピクセル単位である。~ 8ビットBMPでは1ピクセルが1バイトであるため問題ないが、4ビットBMPでは2ピクセルで1バイトなので注意すること。~ ただし、値の連続、不連続の判定はBMPの形式に関係なくバイト単位で行う。 以下に各構成要素の詳細を述べる。 **エンコードデータ [#struct-encoded] @dfn{エンコードデータ};とは、RLEそのものが施されたデータのことで、以下の構成要素を持つ。 |~要素|~バイト数|h |LEFT:|RIGHT:|c |ピクセルの連続数|1| |連続している値|1| @dfn{ピクセルの連続数};は符号無し整数値で、@dfn{連続している値};のピクセル単位での連続数を示す。 8ビットBMPにおいては、エンコードデータは[[概要>#about]]で述べたRLEそのものである。~ ピクセルの連続数は最大で @code{255}; となり、それ以上連続している場合は2つ以上のエンコードデータに分割する。 4ビットBMPにおいて、例えば、次の図のような8ピクセルの連続したデータを考える。 #ref(4ビットBMPの非圧縮データ例.png,left,nolink,|1;1|1;1|1;1|1;1| (|=バイト区切り ;=ピクセル区切り)) このデータに対してRLEを施すと、次の図のようになる。 #ref(4ビットBMPのRLEデータ.png,left,nolink,|8|1;1| (|=バイト区切り ;=ピクセル区切り)) このように、4ビットBMPにおいては、連続判定はバイト単位で行い、連続数はピクセル単位で書き出す。~ 必然的にピクセルの連続数は偶数となり、最大で @code{254}; となる。 **絶対モードデータ [#struct-absolute] @dfn{絶対モードデータ};とは、文字通り[[絶対モード>#about-absolute]]が適用されたデータのことで、以下の構成要素を持つ。 |~要素|~バイト数|h |LEFT:|RIGHT:|c |エスケープコード|1| |ピクセル数|1| |非圧縮データ|2N| @dfn{エスケープコード};は、エンコーダが特殊データ([[エンコードデータ>#struct-encoded]]以外のデータ)の開始を知るためのもので、必ず @code{0}; となる。 @dfn{ピクセル数};は続く非圧縮データのピクセル数を示す符号無し整数値で、8ビットBMPでは @code{3}; から @code{255}; 、4ビットBMPでは @code{4}; から @code{254}; の値を取る。~ @code{2}; 以下の値を取ってはならない。 @dfn{非圧縮データ};は、非圧縮の[[ピクセルデータ>../バイナリ構造#image-data-pixel]]のピクセル数分の羅列である。~ これは2バイトの整数倍のサイズでなければならず、足りない場合は @code{0}; で埋める必要がある。 **行データの終わり [#struct-eol] @dfn{行データの終わり};は@dfn{EOL};と呼ばれ、文字通り行の終わりを示す。~ 以下の構成要素を持つ。 |~要素|~バイト数|h |LEFT:|RIGHT:|c |エスケープコード|1| |EOL識別コード|1| @dfn{エスケープコード};は、エンコーダが特殊データの開始を知るためのもので、必ず @code{0}; となる。 @dfn{EOL識別コード};は、このデータがEOLであることを示すためのもので、必ず @code{0}; となる。 BMPにおけるRLEは[[行データ>../バイナリ構造#image-data-line]]単位で施される。~ よって、あるEOLから次のEOLまでのデータが1行分のデータとなる。~ 非圧縮BMPにおける[[行データ>../バイナリ構造#image-data-line]]は4バイトの整数倍のサイズに揃えなければならなかったが、RLEにおいてはそのような制約はなく、エンコーダは有効なピクセル数分だけ圧縮すればよい。 なお、展開中の行の全ピクセルの取得が終わる前にEOLが現れる場合がある。~ その場合、デコーダによるその行の残りのピクセルの扱いは定義されていないが、通常は @code{0}; で埋める。~ エンコーダは、このようなEOLの扱い方をするべきではない。 **イメージデータの終わり [#struct-eob] @dfn{イメージデータの終わり};は@dfn{EOB};と呼ばれ、全データの終わりを示す。以下の構成要素を持つ。 |~要素|~バイト数|h |LEFT:|RIGHT:|c |エスケープコード|1| |EOB識別コード|1| @dfn{エスケープコード};は、エンコーダが特殊データの開始を知るためのもので、必ず @code{0}; となる。 @dfn{EOB識別コード};は、このデータがEOBであることを示すためのもので、必ず @code{1}; となる。 EOBは、その役割上、全データの一番最後に一度だけ必ず現れる必要がある。~ デコーダは、EOBが出現した時点でデータの伸張を完了する。 なお、展開中の全行全ピクセルの取得が終わる前にEOBが現れる場合がある。~ その場合、デコーダによる残りのピクセルの扱いは定義されていないが、通常は @code{0}; で埋める。~ エンコーダは、このようなEOBの扱い方をするべきではない。 **位置移動情報 [#struct-delta] @dfn{位置移動情報};は、現在のデコード位置からの移動を示すデータで、以下の構成要素を持つ。 |~要素|~バイト数|h |LEFT:|RIGHT:|c |エスケープコード|1| |位置移動情報識別コード|1| |移動ピクセル数|1| |移動行数|1| @dfn{エスケープコード};は、エンコーダが特殊データの開始を知るためのもので、必ず @code{0}; となる。 @dfn{位置移動情報識別コード};は、このデータが位置移動情報であることを示すためのもので、必ず @code{2}; となる。 @dfn{移動ピクセル数};及び@dfn{移動行数};は、現在のデコード位置からの移動量を示す符号無し整数値である。 例えば、現在のデコード位置が3番目の[[行データ>../バイナリ構造#image-data-line]]の5ピクセル目で、移動ピクセル数が @code{4}; 、移動行数が @code{2}; だった場合、その次のデータを5番目の[[行データ>../バイナリ構造#image-data-line]]の9ピクセル目としてデコードを再開する。~ 位置移動情報によって飛ばされたピクセルの扱いは定義されていないが、通常は @code{0}; で埋める。 意図する場合を除き、エンコーダは位置移動情報を利用するべきではない。 *RLEによる圧縮処理 [#compress] 4ビットまたは8ビットの非圧縮BMPの[[行データ>../バイナリ構造#image-data-line]]に対して、[[絶対モード>#about-absolute]]を考慮したRLEを施す処理のC++言語でのコーディング例を以下に示す。 #code(c){{ // static 関数のプロトタイプ宣言 static unsigned long store_encoded( void* dest, unsigned char data, long data_num, int bitcount); static unsigned long store_absolute( void* dest, const void* src, long src_size, int bitcount); /** * @brief * 非圧縮の行データに画像の幅及びビット数を基にしてRLEを施す。 * * @param[out] dest * RLEを施した行データの格納先。 * src の倍のサイズを確保しておく必要がある。 * @param[in] src * RLEを施す対象となる行データ。 * @param[in] width * 元画像の幅。 * @param[in] bitcount * 元画像のビット数(4 または 8)。 * * @return * dest に格納されたデータのバイト単位でのサイズ。 * 引数が不正な場合は 0 。 */ unsigned long rle_compress_line( void* dest, const void* src, long width, int bitcount = 8) { // 引数チェック if (dest == NULL || src == NULL || width <= 0) { return 0; } // 行データのバイト幅及び最大連続バイト数設定 long bytelen, maxbyte; switch (bitcount) { case 8: bytelen = width; maxbyte = 255; break; case 4: bytelen = (width + 1) / 2; maxbyte = 127; break; default: return 0; } // ポインタ設定 unsigned char* pdest = (unsigned char*)dest; const unsigned char* psrc = (const unsigned char*)src; // 絶対モード開始位置ポインタ const unsigned char* pabs = psrc; // 前回バイト値保持変数(最初のバイト値と異なる値で初期化) unsigned char prev = (*psrc == 0) ? 1 : 0; // 連続回数及び絶対モードカウンタ long cont = 1; long abso = -1; // データ分だけループ for (long i = 0; i < bytelen; i++) { // 現在位置のバイト値取得 unsigned char cur = *(psrc + i); // 前のバイト値と等しいかどうかで処理分け if (cur == prev) { cont++; if (abso >= 1) { // 今までの不連続値があれば書き出し pdest += store_absolute(pdest, pabs, abso, bitcount); abso = -1; } else if (cont == maxbyte) { // 最大バイト数になったならエンコードデータ書き出し pdest += store_encoded(pdest, prev, maxbyte, bitcount); cont = 1; // 次のバイト値とは異なる値にする prev = (*(psrc + i + 1) == 0) ? 1 : 0; } } else { abso++; if (cont >= 2) { // 今までの連続データがあればエンコードデータ書き出し pdest += store_encoded(pdest, prev, cont, bitcount); cont = 1; } else if (abso == maxbyte) { // 最大バイト数になったなら絶対モードデータ書き出し pdest += store_absolute(pdest, pabs, maxbyte, bitcount); abso = 0; } // 絶対モード開始位置移動 if (abso == 0) { pabs = psrc + i; } // 前のバイト値置き換え prev = cur; } } // 残りのデータを書き出し if (abso >= 0) { pdest += store_absolute(pdest, pabs, abso + 1, bitcount); } else if (cont >= 2) { pdest += store_encoded(pdest, prev, cont, bitcount); } return (unsigned long)(pdest - dest); } /** * @brief * 指定した数の連続した値をエンコードデータとして書き出す。 * * @param[out] dest * 書き出し先のアドレス。 * @param[in] data * 書き出す値。 * @param[in] data_num * data のバイト単位での連続数。 * @param[in] bitcount * 元画像のビット数。 * * @return * dest に格納されたデータのバイト単位でのサイズ。 */ static unsigned long store_encoded( void* dest, unsigned char data, long data_num, int bitcount) { unsigned char* pdest = (unsigned char*)dest; // エンコードデータ書き出し if (data_num >= 1) { *pdest++ = (unsigned char)(data_num * 8 / bitcount); *pdest++ = data; } return (unsigned long)(pdest - dest); } /** * @brief * 指定したサイズの不連続な値にRLEを施して書き出す。 * * @param[out] dest * 書き出し先のアドレス。 * @param[in] src * 書き出し元のアドレス。 * @param[in] src_size * src のバイト単位でのサイズ。 * @param[in] bitcount * 元画像のビット数。 * * @return * dest に格納されたデータのバイト単位でのサイズ。 */ static unsigned long store_absolute( void* dest, const void* src, long src_size, int bitcount) { unsigned char* pdest = (unsigned char*)dest; const unsigned char* psrc = (const unsigned char*)src; if (src_size >= 3) { // サイズが 3 以上ならば絶対モードデータとして書き出し *pdest++ = 0x00; *pdest++ = (unsigned char)(src_size * 8 / bitcount); for (long i = 0; i < src_size; i++) { *pdest++ = *(psrc + i); } // バイト数が奇数(2の倍数でない)なら 0 で埋める if ((src_size & 1) != 0) { *pdest++ = 0x00; } } else { // サイズが 2 以下ならばエンコードデータとして書き出し for (long i = 0; i < src_size; i++) { pdest += store_encoded(pdest, *(psrc + i), 1, bitcount); } } return (unsigned long)(pdest - dest); } }} この処理を全ての[[行データ>../バイナリ構造#image-data-line]]に対して行うことで非圧縮の[[イメージデータ>../バイナリ構造#image-data]]にRLEを施すことができる。~ 上述のコーディング例で記述した @code{rle_compress_line}; 関数を用いたC++言語でのコーディング例を以下に示す。 #code(c){{ /** * @brief * 非圧縮のイメージデータに、画像の幅、高さ、及びビット数を * 基にしてRLEを施す。 * * @param[out] dest * RLEを施したイメージデータの格納先。 * src の倍のサイズを確保しておく必要がある。 * @param[in] src * RLEを施す対象となるイメージデータ。 * @param[in] width * 元画像の幅。 * @param[in] height * 元画像の高さ。 * @param[in] bitcount * 元画像のビット数(4 または 8)。 * * @return * dest に格納されたデータのバイト単位でのサイズ。 * 引数が不正な場合は 0 。 */ unsigned long rle_compress_image( void* dest, const void* src, long width, long height, int bitcount = 8) { // 引数チェック if ( dest == NULL || src == NULL || width <= 0 || height <= 0 || (bitcount != 4 && bitcount != 8)) { return 0; } // ポインタ設定 unsigned char* pdest = (unsigned char*)dest; // 1行あたりのバイト数を算出 long linelen = (width * bitcount + 31) / 32 * 4; // 行データの数だけループ for (long i = 0; i < height; i++) { // 行データ位置のポインタ設定 const unsigned char* psrc = (const unsigned char*)src + linelen * i; // 行データにRLEを施して書き出す pdest += rle_compress_line(pdest, psrc, width, bitcount); // EOLを書き出す *pdest++ = 0x00; *pdest++ = 0x00; } // EOBを書き出す *pdest++ = 0x00; *pdest++ = 0x01; return (unsigned long)(pdest - dest); } }} このコーディング例で記述した @code{rle_compress_image}; 関数の戻り値分のサイズだけ実際のファイルに書き出すようにする。~ *RLEの伸張処理 [#decompress] 8ビットのRLEが施された[[イメージデータ>../バイナリ構造#image-data]]を非圧縮の[[イメージデータ>../バイナリ構造#image-data]]に伸張する処理のC++言語でのコーディング例を以下に示す。 #code(c){{ #include <memory.h> /** * @brief * 8ビットのRLEが施されたイメージデータを伸張する。 * * @param[out] dest * 伸張したイメージデータの格納先。 * サイズは (width*8+31)/32*4*height 以上でなければならない。 * @param[in] src * 8ビットのRLEが施されたイメージデータ。 * @param[in] width * 元画像の幅。 * @param[in] height * 元画像の高さ。 * * @return * dest に格納されたデータのバイト単位でのサイズ。 * 引数が不正な場合は 0 。 */ unsigned long rle8_decompress_image( void* dest, const void* src, long width, long height) { // 引数チェック if (dest == NULL || src == NULL || width <= 0 || height <= 0) { return 0; } // ポインタ設定 const unsigned char* psrc = (const unsigned char*)src; // 1行あたりのバイト数及び出力先サイズを算出 long linelen = (width * 8 + 31) / 32 * 4; long datasize = linelen * height; // 出力先を 0 で埋める memset(dest, 0, datasize); // 行数分だけループ for (long y = 0; y < height; y++) { // ポインタ設定 unsigned char* pdest = (unsigned char*)dest + linelen * y; // EOB出現フラグ bool eob = false; // 行の終端(EOL)に達するまでループ for (long x = 0; ; ) { // 2バイト取得 unsigned char code[2]; code[0] = *psrc++; code[1] = *psrc++; // 1バイト目が 0 ならエンコードデータ以外 if (code[0] == 0) { // EOL出現フラグ bool eol = false; // 識別コードによる処理分け switch (code[1]) { case 0x00: // EOL eol = true; break; case 0x01: // EOB eob = true; break; case 0x02: // 位置移動情報 code[0] = *psrc++; code[1] = *psrc++; x += code[0]; y += code[1]; pdest += code[0] + linelen * code[1]; break; default: // 絶対モードデータ x += code[1]; for (long i = 0; i < (long)code[1]; i++) { *pdest++ = *psrc++; } // 奇数個ならバイト埋めの 0 を飛ばす if ((code[1] & 1) != 0) { psrc++; } break; } if (eol || eob) { break; } } else if (x < width) { // エンコードデータ x += code[0]; for (long i = 0; i < (long)code[0]; i++) { *pdest++ = code[1]; } } else // if (x >= width) { // 横幅を超えてもEOLが現れないのでエラー return 0; } } if (eob) { break; } } return datasize; } }} また、4ビットのRLEが施された[[イメージデータ>../バイナリ構造#image-data]]を非圧縮の[[イメージデータ>../バイナリ構造#image-data]]に伸張する処理のC++言語でのコーディング例を以下に示す。 #code(c){{ #include <memory.h> /** * @brief * 4ビットのRLEが施されたイメージデータを伸張する。 * * @param[out] dest * 伸張したイメージデータの格納先。 * サイズは (width*4+31)/32*4*height 以上でなければならない。 * @param[in] src * 4ビットのRLEが施されたイメージデータ。 * @param[in] width * 元画像の幅。 * @param[in] height * 元画像の高さ。 * * @return * dest に格納されたデータのバイト単位でのサイズ。 * 引数が不正な場合は 0 。 */ unsigned long rle4_decompress_image( void* dest, const void* src, long width, long height) { // 引数チェック if (dest == NULL || src == NULL || width <= 0 || height <= 0) { return 0; } // ポインタ設定 const unsigned char* psrc = (const unsigned char*)src; // 1行あたりのバイト数及び出力先サイズを算出 long linelen = (width * 4 + 31) / 32 * 4; long datasize = linelen * height; // 出力先を 0 で埋める memset(dest, 0, datasize); // 行数分だけループ for (long y = 0; y < height; y++) { // ポインタ設定 unsigned char* pdest = (unsigned char*)dest + linelen * y; // 次の書き出し位置が上位4ビットなら true bool is_hi = true; // EOB出現フラグ bool eob = false; // 行の終端(EOL)に達するまでループ for (long x = 0; ; ) { // 2バイト取得 unsigned char code[2]; code[0] = *psrc++; code[1] = *psrc++; // 1バイト目が 0 ならエンコードデータ以外 if (code[0] == 0) { // EOLフラグ bool eol = false; // 識別コードによる処理分け switch (code[1]) { case 0x00: // EOL eol = true; break; case 0x01: // EOB eob = true; break; case 0x02: // 位置移動情報 code[0] = *psrc++; code[1] = *psrc++; x += code[0]; y += code[1]; pdest += (long)code[0] / 2 + linelen * code[1]; // 奇数ピクセルなら半バイト位置を進める if ((code[0] & 1) != 0) { is_hi = !is_hi; if (is_hi) { pdest++; } } break; default: // 絶対モードデータ { x += code[1]; long dbyte = ((long)code[1] + 1) / 2; if (is_hi) { for (long i = 0; i < dbyte; i++) { *pdest++ = *psrc++; } // 奇数ピクセルなら半バイト戻る if ((code[1] & 1) != 0) { *(--pdest) &= 0xF0; is_hi = false; } } else { for (long i = 0; i < dbyte; i++) { *pdest++ |= (*psrc >> 4) & 0x0F; *pdest |= (*psrc++ << 4) & 0xF0; } // 奇数ピクセルなら半バイト戻る if ((code[1] & 1) != 0) { *pdest = 0x00; is_hi = true; } } // 奇数個ならバイト埋めの 0 を飛ばす if ((dbyte & 1) != 0) { psrc++; } } break; } if (eol || eob) { break; } } else if (x < width) { // エンコードデータ x += code[0]; // 次の書き出し位置が上位4ビットでない場合の処理 if (!is_hi) { *pdest++ = (code[1] >> 4) & 0x0F; code[1] = ((code[1] >> 4) & 0x0F) | ((code[1] << 4) & 0xF0); code[0]--; is_hi = true; } // 書き出し long dbyte = ((long)code[0] + 1) / 2; for (long i = 0; i < dbyte; i++) { *pdest++ = code[1]; } // 奇数ピクセルなら半バイト戻る if ((code[0] & 1) != 0) { *(--pdest) &= 0xF0; is_hi = false; } } else // if (x >= width) { // 横幅を超えてもEOLが現れないのでエラー return 0; } } if (eob) { break; } } return datasize; } }} これらの例では、飛ばされたピクセルについては @code{0}; で埋めている。