応用情報技術者 2020年 秋期 午後 問03

　 　画像の情報量を落として画像ファイルのサイズを小さくしたり、モノクロの液晶画面に画像を表示させたりする際に、減色アルゴリズムを用いた画像変換を行うことがある。誤差拡散法は減色アルゴリズムの一つである。誤差拡散法を用いて、階調ありのモノクロ画像を、黒と白だけを使ったモノクロ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に示す。なお、拡散する誤差の値は整数とし、小数点以下は切り捨てる。

　図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を加算する。

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

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

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