誤差拡散法による減色処理に関する次の記述を読んで，設問1〜4に答えよ。
画像の情報量を落として画像ファイルのサイズを小さくしたり，モノクロの液晶画面に画像を表示させたりする際に，減色アルゴリズムを用いた画像変換を行うことがある。誤差拡散法は減色アルゴリズムの一つである。誤差拡散法を用いて，階調ありのモノクロ画像を，黒と白だけを使ったモノクロ2値の画像に画像変換した例を図1に示す。
階調ありのモノクロ画像の場合は，各ピクセルが色の濃淡をもつことができる。濃淡は輝度で表す。輝度0のとき色は黒に，輝度が最大になると色は白になる。モノクロ2値の画像は，輝度が0か最大かの2値だけを使った画像である。
図1 画像変換の例
画像を構成するピクセルの輝度は，1ピクセルの輝度を8ビットで表す場合，0〜255の値を取ることができる。0が黒で，255が白を表す。誤差拡散法では，次の二つの処理をピクセルごとに行うことで減色を行う。
① 変換前のピクセルについて，白に近い場合は輝度を255，黒に近い場合は輝度を0としてモノクロ2値化し，その際の輝度の差分を評価し，輝度の誤差Dとする。
例えば，変換前のピクセルの輝度が223の場合，変換後の輝度を255とし，輝度の誤差Dは，223-255から，-32である。
② 事前に定義した誤差拡散のパターンに従って，評価した誤差Dを周囲のピクセル（以下，拡散先という）に拡散させる。
拡散先の数が4の場合の，誤差拡散のパターンの例を図2に，減色処理の手順を図3に示す。なお，拡散する誤差の値は整数とし，小数点以下は切り捨てる。
図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を加算する。
図4 左上から3ピクセル目について処理した例
誤差拡散法を用いて減色するプログラムを作成した。プログラム中で使用する主な変数，定数及び配列を表1に，作成したプログラムを図5に示す。
| 名称 | 種別 | 説明 |
| 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が入る。 |
図5 作成したプログラム
ピクセルを処理する順番を，Y座標ごとに逆向きにすることで，誤差拡散の方向の偏りを減らし，画質を改善することができる。
Y座標が奇数の場合：ピクセルを左から順に処理する。
Y座標が偶数の場合：ピクセルを右から順に処理する。
なお，Y座標が偶数の場合は，誤差拡散のパターンを左右逆にして評価する。
画質を向上させるために，図5の①と②の行の処理を書き換えた。書き換えた後の①の行の処理を図6に，書き換えた後の②の行の処理を図7に示す。なお，A mod Bは，AをBで割った余りである。
図6 書き換えた後の1の行の処理
図7 書き換えた後の2の行の処理
図5中の③の箇所では，誤差を拡散させる先のピクセルが画像の範囲の外側にならないように制御している。このような処理をクリッピングという。
③のif文は，プログラムの終了までに キ 回呼び出され，その度に，条件判定における比較演算と論理演算の評価が，あわせて最大で ク 回行われる。ここでの計算量が少なくなるようにプログラムを改修することで，処理速度を向上させることができる可能性がある。
出典：令和2年度秋期 問3
設問1 図4の左上から3ピクセル目について処理した後の状態から処理を進め，太枠で示されたピクセルの一つ右隣のピクセルを処理した後の変換後輝度配列について，（1），（2）に答えよ。
（1）減色処理の結果のピクセル（上から1行目，左から4列目の要素）の色を，白か黒で答えよ。
解答・解説
解答例
黒
解説
（2）（1）のピクセルの処理後に，そのピクセルの下のピクセル（上から2行目，左から4列目の要素）に入る輝度の値を整数で答えよ。
解答・解説
解答例
33
解説
設問2 図5中の ア 〜 ウ に入れる適切な字句を答えよ。
解答・解説
解答例
ア：bmpFrom[x, y] + bmpTo[x, y]
イ：fが128以上
ウ：bmpTo[px, py] + (d * ratio[c] / denominator)
解説
設問3 図6，図7中の エ 〜 カ に入れる適切な字句を答えよ。
解答・解説
解答例
エ：y
オ：2
カ：width - tx + 1
解説
設問4 本文中の キ ， ク に入れる適切な字句を答えよ。
解答・解説
解答例
キ：height * width * ratioCount
ク：7
解説
IPA公開情報
出題趣旨
近年，コンピュータの処理能力は向上しているとはいえ，大量のデータを扱う際には，処理対象のデータを 事前に加工処理しておく必要がある場合がある。
本問では，誤差拡散法による画像のモノクロ 2 値化を題材に，アルゴリズムの理解と応用力について問う。
採点講評
問 3 では，誤差拡散法による画像のモノクロ 2 値化を題材に，そのアルゴリズムに関する理解と応用力につ いて出題した。全体として正答率は平均的であった。
設問 1(2)は，正答率がやや低かった。手順が進むごとに，データの値がどのように変化していくかを正しく 把握することは，手順（アルゴリズム）を理解するだけでなく，その手順をプログラムとして実装する上でも 非常に重要である。
設問 2 のウは，正答率が低かった。拡散された誤差の値を，ピクセルごとに加算し蓄積する処理について問 うたが，d*ratio[c]/denominator だけを答えた解答が目立った。ピクセルの元の値に拡散された誤差を足し込 む処理であるということを理解した上で解答してほしかった。
設問 4 のクは，正答率が低かった。プログラム中に実行回数が多い処理がある場合，その回数を正しく把握 することは，パフォーマンスを改善する上で非常に重要なので，理解を深めてほしい。
