1 ランレングス法による符号化

情報実習第 5 回
1
October 24, 2011
[p.1/4]
ランレングス法による符号化
画像データの符号化に関する次の記述を読んで、設問 1∼3 に答えよ。
図 1 は、8 × 8 の画素の白と黒だけで色分けされた 2 値画像の例である。画素を 1 番上の行から右
へ、次に 2 番目の行の左から右へと順に 1 画素を 1 ビットで、白を 0、黒を 1 で表すと、図 2 のよう
に 64 ビットのビット列で表現することができる。
1. 図 2 のビット列を、同じ値が連続している部分 (ラン) ごとに区切り、各ランをその連続する個
数 (ランレングス) で表すことによって、少ないビット数でのビット列表現に書き換えることが
できる。図 2 では、左上から数えて 0 が 27 個、1 が 27 個、0 が 10 個の順に連続しているので、
27,27,10 という情報を使った表現に書き換える。これを「ランレングス符号化」という。
2. 1 番上の行の左端の画素は白で始まるものとする。ただし、その画素が黒の場合は、先頭に 0
個の白があるものとして符号化を行う。
3. ランレングス符号化の方法は、次のとおりである。
(a) ランレングスを n とし、n を 2 進数で表現した時のけた数を m とする。ただし、常に m ≥ 2
となるように、n = 0 の 2 進数表現を 00、n = 1 の 2 進数表現を 01 とする。
(b) n ビットのランを図 3 のビット列に書き換える。
4. 図 2 の例では、最初は 0 が 27 個連続しているので、n = 27 である。27 を 2 進数で表現すると
11011 となり、5 桁なので m = 5 である。m − 2 = 3 なので、けた数情報は 111 である。した
がって、この部分の符号化後のビット列表現は 111011011 となり、9 ビットで表現できる。
5. 表に n,m 及び符号化のビット列を示す。
情報実習第 5 回
October 24, 2011
学籍番号
[p.2/4]
氏名
表中の a には何が入るか。
表中の b には何が入るか。
設問 2
図 2 の 64 ビットのビット列をランレングス符号化すると、何ビットで表現できるか？
設問 3
ランレングス符号化後のビット列が次の通りであったとする。このビット列を復号した 2 値画像とし
て正しい答えを解答群の中から選べ。
000111011111111011111010
解答群
情報実習第 5 回
2
October 24, 2011
[p.3/4]
ビット操作と論理演算
水平方向及び垂直方向がそれぞれ 128 画素からなる画面がある。水平方向を x 座標、垂直方向を y 座
標とする。この画面の 1 画素の状態を 1 ビットで記憶する配列 MAP(添え字は 0 から始まる) がある。
配列 MAP の各要素の大きさは 16 ビットであり、各ビットの値が 1 の時には対応する画素が点灯し、
0 の時には消灯する。画面上の画素の座標と、配列 MAP の要素中のビット位置との関係を図に示す。
情報実習第 5 回
October 24, 2011
学籍番号
[p.4/4]
氏名
座標 (x, y) が与えられたときに、対応する画素を点灯または消灯するアルゴリズムを作成する。
このアルゴリズムを説明した次の記述中の dummy に入る正しい答えを答えよ。c,d に関しては解
答群の中から選べ。ここで X, Y, V, Q, S はすべて 16 ビットの符号なし整数とする。
1. 座標 (x, y) の画素に対応するビットが含まれる配列要素 M AP (V ) の番号 V を求める。
(a) x を X に代入し、y を Y に代入する。
(b) 画面の水平方向 1 行に対応する配列要素の個数は 8 である。Y を 8 倍するため、Y を右・左
に dummy ビットだけ算術シフトした値を Y に代入する。
(c) X を右・左に
dummy ビットだけ算術シフトした値を S に代入する。
(d) Y + S を V に代入する。
2. 座標 (x, y) の画素に対応する配列要素 MAP(V ) の該当ビットだけが 1 となっているデータ Q を
求める。このため表に示す配列 BIT を参照する。
Q を求める処理の手順は次のとおりである。
(a) X と 15 の
c
を求めて X に代入する。
(b) BIT(X) の値を Q に代入する。
3. 配列 MAP の内容を変更して、座標 (x, y) の画素を点灯または消灯する。
(a) MAP(V ) の値を W に代入する。
(b) 点灯する場合には、W と Q の
d
を求めて MAP(X) に代入する。
(c) 消灯する場合には、Q のすべてのビットを反転し、W と Q のビット単位の論理積を求め
て MAP(V ) に代入する。
c,d に関する解答群
ア、2 の補数イ、ビット単位の排他的論理和ウ、ビット単位の論理積エ、ビット単位の論理和
オ、ビットの反転
カ、加算結果
キ、減算結果
ク、乗算結果

Download Report