2020年 秋期 応用情報技術者試験 問3
誤差拡散法による減色処理
画像の情報量を落として画像ファイルのサイズを小さくしたり，モノクロ液晶画面に画像を表示させたりする際に，減色アルゴリズムを用いた画像変換を行うことがある。誤差拡散法は減色アルゴリズムの一つである。誤差拡散法を用いて，階調ありのモノクロ画像を，黒と白だけを使ったモノクロ2値の画像に画像変換した例を図1に示す。
階調ありのモノクロ画像の場合は，各ピクセルが色の濃淡をもつことができる。濃淡は輝度で表す。輝度0のとき色は黒に，輝度が最大になると色は白になる。モノクロ2値の画像は，輝度が0か最大かの2値だけを使った画像である。
【誤差拡散法のアルゴリズム】
画像を構成するピクセルの輝度は，1ピクセルの輝度を8ビットで表す場合，0～255の値を取ることができる。0が黒で，255が白を表す。誤差拡散法では，次の二つの処理をピクセルごとに行うことで減色を行う。
① 変換前のピクセルについて，白に近い場合は輝度を255，黒に近い場合は輝度を0としてモノクロ2値化し，その際の輝度の差分を評価し，輝度の誤差Dとする。
例えば，変換前のピクセルの輝度が223の場合，変換後の輝度を255とし，輝度の誤差Dは，223－255から，－32である。
② 事前に定義した誤差拡散のパターンに従って，評価した誤差Dを周囲のピクセル（以下，拡散先という）に拡散させる。
拡散先の数が4の場合の，誤差拡散のパターンの例を図2に，減色処理の手順を図3に示す。なお，拡散する誤差の値は整数とし，小数点以下は切り捨てる。
1. 変換前画像のピクセルの数と同じ要素数の数数の2次元配列を，変換処理後の輝度を格納するための配列（以下，変換後輝度配列という）として用意し，全ての要素を0で初期化する。
2. 変換前画像の一番上の左から，各行について左から1ピクセル選び，輝度を得る。
3. 変換前画像の輝度と，変換後輝度配列の同じ要素の値を加算し，これをFとする。
4. Fの値が128以上なら変換後輝度配列の輝度を255とし，誤差の値DをF－255とする。Fが128未満なら変換後輝度配列の輝度を0とし，誤差の値DをFとする。
5. Dの値について，誤差拡散のパターンに定義された割合に従って配分し，拡散先の要素に加算する。ただし，画像の範囲を外れる場合は，その値を無視する。
6. 処理していないピクセルが残っている場合は2に戻って繰り返す。
7. 変換後輝度配列で輝度が0を黒，輝度が255を白として，画像を出力する。
図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を加算する。
【誤差拡散法を用いて減色するプログラム】
誤差拡散法を用いて減色するプログラムを作成した。プログラム中で使用する主
| 名称 | 種別 | 説明 |
|---|---|---|
| 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が入る。 |
for ( y を 1 から height まで繰り返す )
for ( x を 1 から width まで繰り返す )
f ← ア
if ( イ )
d ← f - 255
bmpTo[x, y] ← 255
else
d ← f
bmpTo[x, y] ← 0
endif
for ( c を 1 から ratioCount まで繰り返す )
px ← x + tdx[c]
py ← y + tdy[c]
if ( (px が 1 以上) かつ (px が width 以下)
かつ (py が 1 以上) かつ (py が height 以下) )
bmpTo[px , py] ← ウ
endif
endfor
endfor
endfor
【画質向上のための改修】
ピクセルを処理する順番を，Y座標ごとに逆向きにすることで，誤差拡散の方向の偏りを減らし，画質を改善することができる。
Y座標が奇数の場合：ピクセルを左から順に処理する。 Y座標が偶数の場合：ピクセルを右から順に処理する。
なお，Y座標が偶数の場合は，誤差拡散のパターンを左右逆にして評価する。
画質を向上させるために，図5の①と②の行の処理を書き換えた。書き換えた後の①の行の処理を図6に，書き換えた後の②の行の処理を図7に示す。なお，A mod Bは，AをBで割った余りである。
for ( tx を 1 から width まで繰り返す )
x ← tx
if ( ( エ mod オ ) が 0 に等しい )
x ← カ
endif
px ← x - tdx[c] + ( 2 * tdx[c] * ( エ mod オ ) )
【処理の高速化に関する検討】
図5中の③の箇所では，誤差を拡散させる先のピクセルが画像の範囲の外側にならないように制御している。このような処理をクリッピングという。
③のif文は，プログラムの終了までにキ回呼び出され，その度に，条件判定における比較演算と論理演算の評価が，あわせて最大でク回行われる。
ここでの計算量が少なくなるようにプログラムを改修することで，処理速度を向上させることができる可能性がある。