第07回 ランレングス符号 課題解答例

課題1

以下に示す図4のような画像を表1の方法でランレングス符号にしたときの平均符号長を求めよ。
図4

「Bが4個」「Wが4個」の並びがひとかたまりとしてそれぞれ4ビットの符号語に置き換えられる。
これをシンボル1つあたりに換算すれば、ちょうどその1/4なので平均符号長は 1ビット になる。

課題2

以下に示す図5のような画像を表1の方法でランレングス符号にしたときの平均符号長を求めよ。ただし、結果は四捨五入して小数第三位までにすること。
図5

画像のうち最後の4つのピクセルを除く部分は「Bが5個」か「Wが5個」のいずれかで、その数は \((1024-4)/5=204\) 組である。最後の「Bが4個」の1つを加えて全部で205組の並びがあり、 いずれも4ビットの符号語に置き換えられるので、全体のデータ量は \(205\times4=820\) ビットある。
一方シンボルは全部で1024個あるので、平均符号長は \(820/1024=0.8007...≒0.801\) より 0.801ビット になる。

課題3

表1の方法で \(p_{b1}=p_{w1}=0.43\) で、 \(p_{b2}\)~\(p_{b8}\) と \(p_{w2}\)~\(p_{w8}\) がすべて \(0.01\) のときの平均符号長 \(L\) を求めよ。

白と黒のピクセルの同じ数の並び対応する確率が同じなので、符号の並びの数の平均は
\( \begin{eqnarray} L_s&&=\sum_i^8 \left(ip_{bi}+ip_{wi}\right)\\ &&=2\sum_i^8 ip_{bi}\\ &&=2\left(0.43+0.01(2+3+4+5+6+7+8)\right)\\ &&=2\times0.78\\ &&=1.56 \end{eqnarray} \)

となるので、並びに対する符号長をこれで割って \(L=4/L_s=4/1.56=2.564...≒2.56\) より \(L=2.56\) ビット となる (問題文で特に小数第何位までという指定がないので、\(L=2.564\) ビット でも正解)。
なにも工夫せずにそれぞれのピクセルを1ビットに置き換えた場合は \(L=1\) ビットで、このケースではそれに比べてデータが2倍以上にふくらんでしまうことを意味する。

課題4

表1の方法で \(p_{b1}\)~\(p_{b7}\) と \(p_{w1}\)~\(p_{w7}\) がすべて\(0.01\)、\(p_{b8}=p_{w8}=0.43\) のときの平均符号長 \(L\) を求めよ。

白と黒のピクセルの同じ数の並び対応する確率が同じなので、符号の並びの数の平均は
\( \begin{eqnarray} L_s&&=\sum_i^8 \left(ip_{bi}+ip_{wi}\right)\\ &&=2\sum_i^8 ip_{bi}\\ &&=2\left(0.43\times8+0.01(1+2+3+4+5+6+7)\right)\\ &&=2\times3.72\\ &&=7.44 \end{eqnarray} \)

となるので、並びに対する符号長をこれで割って \(L=4/L_s=4/7.44=0.537...≒0.54\) より \(L=0.54\) ビット となる (問題文で特に小数第何位までという指定がないので、\(L=0.538\) ビット でも正解)。
この結果は、なにも工夫せずにそれぞれのピクセルを1ビットに置き換えた場合よりも効率が良く、データが半分近くに減らせていることを意味する。

書き方の全般的な注意

等しくないものをイコールでつながない
課題1で
\( \begin{eqnarray} &&204\times4+4\\ =&&820\\ =&&\frac{820}{1024}\\ =&&\cdots \end{eqnarray} \)

のように書いた人が複数いた。2行目までがデータ総量の計算、3行目からが平均符号長の計算のつもりと思われるが、3行目の先頭の「=」は明らかに誤り。

課題3, 4に多かった書き方
\( \begin{eqnarray} L_s&=&\cdots\\ &=&1.56\\ &=&\frac{4}{1.56}\\ &=&\cdots \end{eqnarray} \)

の3行目の先頭の「=」も同様に誤り。
inserted by FC2 system