技事録係

IT中心にエンジニアに必要な技術情報・最新動向・働き方などを記録

AP 令和2年度秋期 午後 問3

 誤差拡散法による減色処理に関する次の記述を読んで,設問1〜4に答えよ。

 画像の情報量を落として画像ファイルのサイズを小さくしたり,モノクロの液晶画面に画像を表示させたりする際に,減色アルゴリズムを用いた画像変換を行うことがある。誤差拡散法は減色アルゴリズムの一つである。誤差拡散法を用いて,階調ありのモノクロ画像を,黒と白だけを使ったモノクロ2値の画像に画像変換した例を図1に示す。
 階調ありのモノクロ画像の場合は,各ピクセルが色の濃淡をもつことができる。濃淡は輝度で表す。輝度0のとき色は黒に,輝度が最大になると色は白になる。モノクロ2値の画像は,輝度が0か最大かの2値だけを使った画像である。

f:id:trhnmr:20201021182530p:plain

図1 画像変換の例

誤差拡散法のアルゴリズム

 画像を構成するピクセルの輝度は,1ピクセルの輝度を8ビットで表す場合,0〜255の値を取ることができる。0が黒で,255が白を表す。誤差拡散法では,次の二つの処理をピクセルごとに行うことで減色を行う。

① 変換前のピクセルについて,白に近い場合は輝度を255,黒に近い場合は輝度を0としてモノクロ2値化し,その際の輝度の差分を評価し,輝度の誤差Dとする。
例えば,変換前のピクセルの輝度が223の場合,変換後の輝度を255とし,輝度の誤差Dは,223-255から,-32である。

② 事前に定義した誤差拡散のパターンに従って,評価した誤差Dを周囲のピクセル(以下,拡散先という)に拡散させる。

 

 拡散先の数が4の場合の,誤差拡散のパターンの例を図2に,減色処理の手順を図3に示す。なお,拡散する誤差の値は整数とし,小数点以下は切り捨てる。

f:id:trhnmr:20201021182554p:plain

図2 拡散先の数が4の場合の,誤差拡散のパターンの例

1.変換前画像のピクセルの数と同じ要素数の整数の2次元配列を,変換処理後の輝度を格納するための配列(以下,変換後輝度配列という)として用意し,全ての要素を0で初期化する。

2.変換前画像の一番上の行から,各行について左から順に1ピクセル選び,輝度を得る。

3.変換前画像の輝度と,変換後輝度配列の同じ要素の値を加算し,これをFとする。

4.Fの値が128以上なら変換後輝度配列の輝度を255とし,誤差の値DをF-255とする。1Fの値が128未満なら変換後輝度配列の輝度を0とし,誤差の値DをPとする。

5.Dの値について,誤差拡散のパターンに定義された割合に従って配分し,拡散先の要素に加算する。ただし,画像の範囲を外れる場合は,その値を無視する。

6.処理していないピクセルが残っている場合は2.に戻って繰り返す。

7.変換後輝度配列で輝度が0を黒,輝度が255を白として,画像を出力する。

図3 減色処理の手順

 図2のパターンを使い,図3の手順に従って,1行目の左上から2ピクセル分の処理をした後,その右隣のピクセル(左上から3ピクセル目)について処理した例を図4に示す。変換前画像の輝度の値が128で,変換後輝度配列の同じ要素の値が-14なので,Fは128+(-14)=114となる。Fが128未満なので,輝度は0,誤差Dは114となる。誤差114に7/16を乗じて,小数点以下を切り捨てた値は49なので,変換後輝度配列の一つ右の要素に49を加算する。同様に,左下には21,下には35,右下には7を加算する。

f:id:trhnmr:20201021182634p:plain

図4 左上から3ピクセル目について処理した例

誤差拡散法を用いて減色するプログラム

 誤差拡散法を用いて減色するプログラムを作成した。プログラム中で使用する主な変数,定数及び配列を表1に,作成したプログラムを図5に示す。

表1 プログラム中で使用する主な変数,定数及び配列

名称 種別 説明
width 変数 画像の幅。1以上の整数が入る。
height 変数 画像の高さ。1以上の整数が入る。
bmpFrom[x,y] 配列 変換前画像の輝度の配列。輝度が0〜255の値で格納される。
x,yはそれぞれX座標とY座標で,画像の左上が[1,1],右下が[width,height]である。
bmpTo[x,y] 配列 変換後輝度配列。x,yはbmpFrom[x,y]と同様である。全ての要素は0で初期化されている。
ratioCount 定数 誤差拡散のパターンの拡散先の数。図2の場合は4が入る。
tdx 配列 拡散先の,ピクセル単位のX方向の相対位置。図2の場合は[1, -1, 0, 1]
tdy 配列 拡散先の,ピクセル単位のY方向の相対位置。図2の場合は[0, 1, 1, 1]が入る。
ratio[] 配列 拡散先のピクセルごとの割合の分子。図2の場合は[7, 3, 5, 1]が入る。
denominator 定数 拡散先のピクセルごとの割合の分母。図2の場合は16が入る。

f:id:trhnmr:20201021182713p:plain

図5 作成したプログラム

画質向上のための改修

 ピクセルを処理する順番を,Y座標ごとに逆向きにすることで,誤差拡散の方向の偏りを減らし,画質を改善することができる。
  Y座標が奇数の場合:ピクセルを左から順に処理する。
  Y座標が偶数の場合:ピクセルを右から順に処理する。
 なお,Y座標が偶数の場合は,誤差拡散のパターンを左右逆にして評価する。
 画質を向上させるために,図5の①と②の行の処理を書き換えた。書き換えた後の①の行の処理を図6に,書き換えた後の②の行の処理を図7に示す。なお,A mod Bは,AをBで割った余りである。

f:id:trhnmr:20201021182728p:plain

図6 書き換えた後の1の行の処理

f:id:trhnmr:20201021182741p:plain

図7 書き換えた後の2の行の処理

処理の高速化に関する検討

 図5中の③の箇所では,誤差を拡散させる先のピクセルが画像の範囲の外側にならないように制御している。このような処理をクリッピングという。
 ③のif文は,プログラムの終了までに  キ  回呼び出され,その度に,条件判定における比較演算と論理演算の評価が,あわせて最大で  ク  回行われる。ここでの計算量が少なくなるようにプログラムを改修することで,処理速度を向上させることができる可能性がある。

 

設問

設問1 図4の左上から3ピクセル目について処理した後の状態から処理を進め,太枠で示されたピクセルの一つ右隣のピクセルを処理した後の変換後輝度配列について,(1),(2)に答えよ。

(1)減色処理の結果のピクセル(上から1行目,左から4列目の要素)の色を,白か黒で答えよ。

 

(2)(1)のピクセルの処理後に,そのピクセルの下のピクセル(上から2行目,左から4列目の要素)に入る輝度の値を整数で答えよ。

 

 

設問2 図5中の  ア    ウ  に入れる適切な字句を答えよ。

 

 

設問3 図6,図7中の  エ    カ  に入れる適切な字句を答えよ。

 

 

設問4 本文中の  キ    ク  に入れる適切な字句を答えよ。

 

 

解答・解説

設問1 (1)
解答例

 

解説
準備中

 

 

設問1 (2)
解答例

 33

解説
準備中

 

 

設問2
解答例

 ア:bmpFrom[x,y] + bmpTo[x,y]
 イ:fが128以上
 ウ:bmpTo[px,py] + d * ratio[c] / denominator

解説
準備中

 

 

設問3
解答例

 エ:y
 オ:2
 カ:width - tx + 1

解説
準備中

 

 

設4
解答例

 キ:height * width * ratioCount
 ク:7

解説
準備中

 

 

 

IPA公開情報

出題趣旨
未発表
採点講評
未発表