4ビット及び8ビットのBMPファイルで利用可能な圧縮方式であるRLEの解説。
RLEとは、Run Length Encodingの略で、データの可逆圧縮方式の1つである。
同一の値が連続するようなデータの圧縮に効果を発揮する。
例えば、次の図のようなデータの並びを考える。
このデータを口で説明すると、「最初に 1
が4個、次に 2
が1個、次に 3
が6個、最後に 4
が3個」となる。
そして、この説明文を形にしたものがRLEである。
即ち、上の図のデータは次の図のように圧縮される。
このようにRLEでは、連続するデータ値を [値の連続数][値] という形式で表す。
上の2つの図からもわかる通り、この例では14バイトの元データが8バイトに圧縮されている。
上の例において、データ値 2
については 1 2
とエンコードされており、1バイトから2バイトに増えてしまっている。
一般に、あるN個の値が羅列されたデータにRLEを施した場合、最も圧縮効率が良いのは全ての値が同一だった場合であり、エンコード後のデータは最小で2個になる。
反対に、最も圧縮効率が悪いのは全ての値が連続していない場合であり、エンコード後のデータはN×2個、即ち元の2倍の量になってしまう。
BMPにおけるRLEでは、上述のようなデータの膨張を軽減するために、絶対モードというものが存在する。
絶対モード内のデータはエンコードされずにそのままの形で格納される。
例えば、次の図のようなデータの並びを考える。
このデータに通常のRLEを施すと、次の図のようになる。
上の2つの図からもわかる通り、13バイトの元データが16バイトに膨張してしまっている。
ここで、 [エスケープコード][値の連続数][値][値]… という形式の絶対モードを導入する。
エスケープコードは絶対モードの開始位置を示すためのもので、ここでは 0
とする。
膨張の原因となっている箇所に対して絶対モードを適用した場合のデータを次の図に示す。
絶対モードを導入することで、13バイトの元データが12バイトに圧縮されており、膨張が抑えられたといえる。
絶対モードは、3個以上の同一でない値の羅列に対して膨張抑止効果を持つ。
BMPにおけるRLEは、イメージデータの行データ単位で施される。
RLEを施す対象となるイメージデータでの行データの格納順は、イメージ表示時に下に来る行ほど最初に格納されるボトムアップ形式でなければならず、トップダウン形式は認められない。
BMPにおけるRLEを施されたデータは、以下の5種類の構成要素の集合となる。
これら各構成要素は、必ず2バイトの整数倍のサイズ(ワードアラインメント)でなければならない。
絶対モードデータはピクセル数によっては2バイトの整数倍のサイズにならない場合があるが、その場合は2バイトの整数倍のサイズになるように 0
で埋める。
概要においては値の連続数はバイト単位として解説したが、実際のBMPにおけるRLEでは、値の連続数はピクセル単位である。
8ビットBMPでは1ピクセルが1バイトであるため問題ないが、4ビットBMPでは2ピクセルで1バイトなので注意すること。
ただし、値の連続、不連続の判定はBMPの形式に関係なくバイト単位で行う。
以下に各構成要素の詳細を述べる。
エンコードデータとは、RLEそのものが施されたデータのことで、以下の構成要素を持つ。
要素 | バイト数 |
---|---|
ピクセルの連続数 | 1 |
連続している値 | 1 |
ピクセルの連続数は符号無し整数値で、連続している値のピクセル単位での連続数を示す。
8ビットBMPにおいては、エンコードデータは概要で述べたRLEそのものである。
ピクセルの連続数は最大で 255
となり、それ以上連続している場合は2つ以上のエンコードデータに分割する。
4ビットBMPにおいて、例えば、次の図のような8ピクセルの連続したデータを考える。
このデータに対してRLEを施すと、次の図のようになる。
このように、4ビットBMPにおいては、連続判定はバイト単位で行い、連続数はピクセル単位で書き出す。
必然的にピクセルの連続数は偶数となり、最大で 254
となる。
絶対モードデータとは、文字通り絶対モードが適用されたデータのことで、以下の構成要素を持つ。
要素 | バイト数 |
---|---|
エスケープコード | 1 |
ピクセル数 | 1 |
非圧縮データ | 2N |
エスケープコードは、エンコーダが特殊データ(エンコードデータ以外のデータ)の開始を知るためのもので、必ず 0
となる。
ピクセル数は続く非圧縮データのピクセル数を示す符号無し整数値で、8ビットBMPでは 3
から 255
、4ビットBMPでは 4
から 254
の値を取る。
2
以下の値を取ってはならない。
非圧縮データは、非圧縮のピクセルデータのピクセル数分の羅列である。
これは2バイトの整数倍のサイズでなければならず、足りない場合は 0
で埋める必要がある。
行データの終わりはEOLと呼ばれ、文字通り行の終わりを示す。
以下の構成要素を持つ。
要素 | バイト数 |
---|---|
エスケープコード | 1 |
EOL識別コード | 1 |
エスケープコードは、エンコーダが特殊データの開始を知るためのもので、必ず 0
となる。
EOL識別コードは、このデータがEOLであることを示すためのもので、必ず 0
となる。
BMPにおけるRLEは行データ単位で施される。
よって、あるEOLから次のEOLまでのデータが1行分のデータとなる。
非圧縮BMPにおける行データは4バイトの整数倍のサイズに揃えなければならなかったが、RLEにおいてはそのような制約はなく、エンコーダは有効なピクセル数分だけ圧縮すればよい。
なお、展開中の行の全ピクセルの取得が終わる前にEOLが現れる場合がある。
その場合、デコーダによるその行の残りのピクセルの扱いは定義されていないが、通常は 0
で埋める。
エンコーダは、このようなEOLの扱い方をするべきではない。
イメージデータの終わりはEOBと呼ばれ、全データの終わりを示す。以下の構成要素を持つ。
要素 | バイト数 |
---|---|
エスケープコード | 1 |
EOB識別コード | 1 |
エスケープコードは、エンコーダが特殊データの開始を知るためのもので、必ず 0
となる。
EOB識別コードは、このデータがEOBであることを示すためのもので、必ず 1
となる。
EOBは、その役割上、全データの一番最後に一度だけ必ず現れる必要がある。
デコーダは、EOBが出現した時点でデータの伸張を完了する。
なお、展開中の全行全ピクセルの取得が終わる前にEOBが現れる場合がある。
その場合、デコーダによる残りのピクセルの扱いは定義されていないが、通常は 0
で埋める。
エンコーダは、このようなEOBの扱い方をするべきではない。
位置移動情報は、現在のデコード位置からの移動を示すデータで、以下の構成要素を持つ。
要素 | バイト数 |
---|---|
エスケープコード | 1 |
位置移動情報識別コード | 1 |
移動ピクセル数 | 1 |
移動行数 | 1 |
エスケープコードは、エンコーダが特殊データの開始を知るためのもので、必ず 0
となる。
位置移動情報識別コードは、このデータが位置移動情報であることを示すためのもので、必ず 2
となる。
移動ピクセル数及び移動行数は、現在のデコード位置からの移動量を示す符号無し整数値である。
例えば、現在のデコード位置が3番目の行データの5ピクセル目で、移動ピクセル数が 4
、移動行数が 2
だった場合、その次のデータを5番目の行データの9ピクセル目としてデコードを再開する。
位置移動情報によって飛ばされたピクセルの扱いは定義されていないが、通常は 0
で埋める。
意図する場合を除き、エンコーダは位置移動情報を利用するべきではない。
4ビットまたは8ビットの非圧縮BMPの行データに対して、絶対モードを考慮したRLEを施す処理のC++言語でのコーディング例を以下に示す。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 | - ! - | | | | | | | | | | | | | | | | ! - - ! | - ! | - | | | | | | | | | | | | ! | - ! | | - ! | - ! | - ! | | - ! - - ! | - ! - - ! | | - - ! ! | - - ! | | - ! ! | - ! ! | - - | ! | | - - ! ! | - - ! | ! | - ! | - ! | - ! ! ! | - ! - | ! | - | ! | | ! - | | | | | | | | | | | | | | ! - | | - ! - | | ! | | ! - | | | | | | | | | | | | | | ! - | | | | - - ! | | - | ! | - ! ! | - - ! - | ! ! | | ! |
|
この処理を全ての行データに対して行うことで非圧縮のイメージデータにRLEを施すことができる。
上述のコーディング例で記述した rle_compress_line
関数を用いたC++言語でのコーディング例を以下に示す。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | - | | | | | | | | | | | | | | | | | | | ! - - ! | | - | ! | - ! | - ! | - ! - - ! | | - ! | - ! | ! | - ! | | | ! |
|
このコーディング例で記述した rle_compress_image
関数の戻り値分のサイズだけ実際のファイルに書き出すようにする。
8ビットのRLEが施されたイメージデータを非圧縮のイメージデータに伸張する処理のC++言語でのコーディング例を以下に示す。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | - | | | | | | | | | | | | | | | | ! - - ! - | ! | - ! | - ! | | - ! | - ! - - ! | - ! | - ! - - ! | | | - ! - - ! | - ! - | - ! | | | - ! | | | - ! | | | | | | | - ! | - | ! | - ! | | ! | | ! | - - ! | - | ! ! | - - ! ! ! | | ! | | ! |
|
また、4ビットのRLEが施されたイメージデータを非圧縮のイメージデータに伸張する処理のC++言語でのコーディング例を以下に示す。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 | - | | | | | | | | | | | | | | | | ! - - ! - | ! | - ! | - ! | | - ! | - ! - - ! | - ! | - ! | - ! - - ! | | | - ! - - ! | - ! - | - ! | | | - ! | | | - ! | | | | | - ! - | | ! | | | | - ! | | | | - | - | ! | - ! - | | ! ! | - | - | | ! | - ! - | | ! ! | - ! ! | ! | | ! | - - ! | - ! - | | | | | | ! | - ! | - | ! | - ! - | | ! ! | - - ! ! ! | | ! ! |
|
これらの例では、飛ばされたピクセルについては 0
で埋めている。