基本情報技術者 2009年 春期 午後 問01
画像データの符号化に関する次の記述を読んで、設問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) ランレングス符号化の方法は、次のとおりである。
① ランレングスをnとし、nを2進数で表現したときのけた数をmとする。ただし、常にm≧2となるように、n=0の2進数表現を00、n=1の2進数表現を01とする。
② nビットのランを図3のビット列に書き換える。
(4) 図2の例では、最初は0が27個連続しているので、n=27である。27を2進数で表現すると11011（5けた）となり、m=5である。m−2=3なので、けた数情報は111である。したがって、この部分の符号化後のビット列表現は111011011となり、9ビットで表現できる。
(5) 表にn、m及び符号化後のビット列を示す。
設問1：
問題文を見る 表中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：100
イ：0100
ウ：10100
エ：110100
bに関する解答群
ア：14
イ：15
ウ：16
エ：17
模範解答
a：ウ、b：イ
解説
解答の導き方
この問題では、ランレングスを図3のルールで符号化したビット列から、ランレングス を求めます。
図3の符号は、次の3つの部分でできています。
- 個の連続する1（けた数情報）
- 1個の0（区切り）
- ランレングス を表す、ちょうど ビットの2進数
ここで、 は を2進数で表したときのけた数です。つまり、符号の先頭からけた数情報と区切りを読んだ後、残った ビットを2進数として読み取ります。
aを求める
表のこの行は です。まず、 を2進数で表すと で、けた数は3けたです。したがって、 です。
けた数情報は 個の1なので、1です。そこに区切りの0と、ランレングスの2進数表現である100を続けます。
となり、つなげると10100です。したがって、aは解答群のウです。
bを求める
表では、 の行の符号化後のビット列が1101111です。
なので、けた数情報は 個の1です。先頭の11がけた数情報、その次の0が区切りです。残った4ビットの1111が、ランレングス の2進数表現です。
1111を10進数に直すと、 です。したがって、bは解答群のイです。
誤りやすいポイント
- けた数情報は、 個の1ではなく、 個の1です。たとえば、 なら先頭は11です。
- 区切りの0も符号の一部です。けた数情報の後にあるこの0を飛ばして、残りを読む必要があります。
- ランレングスの2進数部分は、 ビットです。 の場合は、区切りの後から4ビットを取り出します。
- が1けたまたは2けたの2進数で表される場合も、問題文のルールに従って は2以上になります。
FAQ
Q: けた数情報は、何のために付いているのですか？
A: 後ろに続くランレングスの2進数が何ビットあるかを、先に伝えるためです。けた数が分かれば、どこまでをランレングスとして読めばよいか判断できます。
A: 後ろに続くランレングスの2進数が何ビットあるかを、先に伝えるためです。けた数が分かれば、どこまでをランレングスとして読めばよいか判断できます。
Q: のとき、けた数情報はどうなりますか？
A: なので、けた数情報はありません。符号は区切りの0から始まり、その後にランレングスを表す2ビットが続きます。
A: なので、けた数情報はありません。符号は区切りの0から始まり、その後にランレングスを表す2ビットが続きます。
Q: や も符号化できますか？
A: できます。問題文では、 を00、 を01とし、どちらも として符号化しています。
A: できます。問題文では、 を00、 を01とし、どちらも として符号化しています。
関連キーワード: ランレングス符号化、2値画像、2進数、データ圧縮
設問2：
問題文を見る 図2の64ビットのビット列をランレングス符号化すると、何ビットで表現できるか。正しい答えを、解答群の中から選べ。
解答群
ア：22
イ：23
ウ：24
エ：25
模範解答
エ
解説
解答の導き方
図2のビット列は、問題文にあるとおり、同じ値が続く部分（ラン）に分けると、左から「0が27個、1が27個、0が10個」です。各ランの長さをランレングス（同じ値が続く個数）として符号化します。
問題文の符号化方法では、ランレングスを 、その2進数表現の桁数を とすると、次の3つを順に並べます。
- けた数情報：1を 個
- 区切り：0を1個
- ランレングス情報： の2進数表現を ビット
それぞれのランについて、必要なビット数を計算します。
最後に、3つのランの符号化に必要なビット数を足します。
したがって、図2のビット列は25ビットで表現でき、解答群ではエです。
誤りやすいポイント
- 64画素を表す元のビット数と、符号化後のビット数を混同しないようにします。ここで求めるのは、各ランを符号化した後の合計です。
- ランレングスの値だけを2進数にして終わりではありません。けた数情報と区切りのビットも加えます。
- の2進数表現は1010で、 です。けた数情報は 個の1なので、符号化後は1101010となり、7ビットです。
- 1つ目と2つ目のランは、どちらも27ですが、符号化はそれぞれ必要です。
FAQ
Q: けた数情報は、なぜランレングスの値そのものではなく、桁数を表すのですか？
A: 区切りの位置から、後ろに続くランレングス情報が何ビットなのかを分かるようにするためです。桁数が分かれば、ランレングスの2進数表現を読み取れます。
A: 区切りの位置から、後ろに続くランレングス情報が何ビットなのかを分かるようにするためです。桁数が分かれば、ランレングスの2進数表現を読み取れます。
Q: 27の符号化に9ビット必要なのはなぜですか？
A: 27の2進数表現は11011で、 です。けた数情報に ビット、区切りに1ビット、ランレングス情報に5ビットを使うため、合計は ビットです。
A: 27の2進数表現は11011で、 です。けた数情報に ビット、区切りに1ビット、ランレングス情報に5ビットを使うため、合計は ビットです。
Q: 0が連続するランと1が連続するランを、毎回区別するビットは必要ですか？
A: この問題では、先頭は白、つまり0から始めると決めています。その後はランごとに0と1が交互に現れるため、各ランの値を別に記録しなくても区別できます。
A: この問題では、先頭は白、つまり0から始めると決めています。その後はランごとに0と1が交互に現れるため、各ランの値を別に記録しなくても区別できます。
関連キーワード: ランレングス符号化、2値画像、2進数、ビット列
設問3：
問題文を見る ランレングス符号化後のビット列が、次のとおりであったとする。このビット列を復号した2値画像として正しい答えを、解答群の中から選べ。
000111011111111011111010
解答群
模範解答
エ
解説
解答の導き方
本文では、1番上の行の左端は白で始める決まりです。また、左端が黒なら「白が0個続く」として符号化します。したがって、符号を復号したときは、最初に白の画素が0個、その次に黒の画素が続く場合があります。
符号化されたビット列を、ランレングス（同じ色が連続する画素の個数）に戻します。図3の方法では、先頭から連続する1の個数でランレングスの2進数のけた数を読み取り、続く0を区切りとして、その後のビットからランレングスを読み取ります。
「000111011111111011111010」を、次のように区切って読みます。
たとえば、2つ目の「111011111」は、先頭の1が3個なので、ランレングスの2進数は5けたです。区切りの0の後にある5ビット「11111」は、2進数で31を表します。
このように復号すると、白が0画素、黒が31画素、白が31画素、黒が2画素の順に続きます。白が0画素なので、画像の最初から黒が31画素並びます。画素を左から右、上から下へ並べた順に位置を分けると、次のようになります。
これは、選択肢エの配列と一致します。
誤りやすいポイント
-
最初の「000」を、白が3画素続くと読まないこと。
先頭の1が0個なので、けた数は2です。最初の0が区切り、その後の2ビット「00」がランレングスを表し、白は0画素です。 -
ランレングスの色は、符号の中に直接書かれているわけではありません。
白、黒、白、黒の順に交互に切り替わります。最初の白が0画素なら、次のランは黒です。 -
画素の合計が64画素になることも確認します。
0＋31＋31＋2＝64です。さらに、復号した画素は8×8画素の画像に並べる必要があります。
FAQ
Q: 最初のランレングスが0になるのは、なぜですか？
A: 画像の左上が黒で始まる場合も表せるようにするためです。最初は白と決めているので、白が1画素もなければ、白のランレングスを0としてから黒のランを読みます。
A: 画像の左上が黒で始まる場合も表せるようにするためです。最初は白と決めているので、白が1画素もなければ、白のランレングスを0としてから黒のランを読みます。
Q: 先頭に続く1の個数は、何を表していますか？
A: ランレングスを2進数で表したときのけた数を決める情報です。先頭の1が3個なら、けた数は3＋2＝5けたです。その後の区切りの0に続く5ビットが、ランレングスを表します。
A: ランレングスを2進数で表したときのけた数を決める情報です。先頭の1が3個なら、けた数は3＋2＝5けたです。その後の区切りの0に続く5ビットが、ランレングスを表します。
Q: ランレングスを読んだ後、色はどのように決まりますか？
A: 最初を白として、ランごとに白と黒を交互に切り替えます。最初のランが0画素でも、その次は黒のランになります。
A: 最初を白として、ランごとに白と黒を交互に切り替えます。最初のランが0画素でも、その次は黒のランになります。
関連キーワード: ランレングス符号化、2進数、2値画像、ビット列、画像の走査順
