問題プレビューID: 17d233cd応用情報技術者試験 2020年(令和2年度)10月 午後

問 3
応用情報技術者試験 2020年(令和2年度)10月 午後

誤差拡散法による減色処理に関する次の記述を読んで,設問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 の場合の,誤差拡散のパターンの例

輝度の誤差 D→ D×7/16
D×3/16↓ D×5/16D×1/16

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

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

変換前画像(太枠は左上から 3 ピクセル目)

022312835220
30221855197
3512225010515
3815325112018

左上から 2 ピクセル分の処理後(変換後輝度配列)

0255−1400
−6−10−200
00000
00000

左上から 3 ピクセル目の処理後

02550490
−6113370
00000
00000

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

誤差拡散法を用いて減色するプログラムを作成した。プログラム中で使用する主な変数,定数及び配列を表 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 が入る。

図 5 作成したプログラム

for ( y を 1 から height まで繰り返す )
  for ( x を 1 から width まで繰り返す )                                    ← ①
    f ← [ア]
    if ( [イ] )
      d ← f - 255
      bmpTo[x, y] ← 255
    else
      d ← f
      bmpTo[x, y] ← 0
    end if
    for ( c を 1 から ratioCount まで繰り返す )
      px ← x + tdx[c]                                                      ← ②
      py ← y + tdy[c]
      if ( (px が 1 以上) かつ (px が width 以下)
           かつ (py が 1 以上) かつ (py が height 以下) )                  ← ③
        bmpTo[px , py] ← [ウ]
      end if
    end for
  end for
end for

〔画質向上のための改修〕

ピクセルを処理する順番を,Y 座標ごとに逆向きにすることで,誤差拡散の方向の偏りを減らし,画質を改善することができる。

Y 座標が奇数の場合:ピクセルを左から順に処理する。

Y 座標が偶数の場合:ピクセルを右から順に処理する。

なお,Y 座標が偶数の場合は,誤差拡散のパターンを左右逆にして評価する。

画質を向上させるために,図 5 の①と②の行の処理を書き換えた。書き換えた後の①の行の処理を図 6 に,書き換えた後の②の行の処理を図 7 に示す。なお,A mod B は,A を B で割った余りである。

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

for ( tx を 1 から width まで繰り返す )
  x ← tx
  if ( ( [エ] mod [オ] ) が 0 に等しい )
    x ← [カ]
  end if
end for

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

px ← x - tdx[c] + ( 2 * tdx[c] * ( [エ] mod [オ] ) )

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

図 5 中の③の箇所では,誤差を拡散させる先のピクセルが画像の範囲の外側にならないように制御している。このような処理をクリッピングという。

③の if 文は,プログラムの終了までに [キ] 回呼び出され,その度に,条件判定における比較演算と論理演算の評価が,あわせて最大で [ク] 回行われる。ここでの計算量が少なくなるようにプログラムを改修することで,処理速度を向上させることができる可能性がある。

設問1

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

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

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

設問2

図 5 中の [ア]〜[ウ]に入れる適切な字句を答えよ。

設問3

図 6,図 7 中の [エ]〜[カ]に入れる適切な字句を答えよ。

設問4

本文中の [キ],[ク]に入れる適切な字句を答えよ。

模範解答

設問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

解説

設問1 (1) 図 4 の左上から 3 ピクセル目を処理した後の変換後輝度配列の 1 行目は 0,255,0,49,0 である。次に処理するのは太枠のピクセルの一つ右隣,すなわち 1 行目 4 列目のピクセルである。変換前画像の 4 列目の輝度は 35,変換後輝度配列の同じ要素の値は 49 なので,F は 35+49=84 となる。F が 128 未満なので,変換後の輝度は 0,すなわち黒となる。(2) 誤差 D は 84 である。図 2 のパターンに従うと,下(2 行目 4 列目)には 84×5/16=26.25 を小数点以下切り捨てた 26 を加算する。2 行目 4 列目の値は処理前 7 なので,7+26=33 となる。

設問2 ア:F は変換前画像の輝度 bmpFrom[x, y] と変換後輝度配列の同じ要素の値 bmpTo[x, y] の和なので,bmpFrom[x, y] + bmpTo[x, y] となる。イ:F が 128 以上なら輝度を 255(白),128 未満なら輝度を 0(黒)とするので,条件は「f が 128 以上」である。ウ:拡散先の要素に,誤差 D の配分(d * ratio[c] / denominator)を加算するので,bmpTo[px, py] + (d * ratio[c] / denominator) となる。

設問3 Y 座標が偶数のときはピクセルを右から順に処理し,誤差拡散のパターンを左右逆にして評価する。エ,オ:Y 座標が偶数かどうかは y mod 2 が 0 に等しいかで判定するので,エは y,オは 2 である。カ:右から順に処理するときの X 座標は width − tx + 1 で求まる。図 7 は拡散先の X 方向の位置を左右反転する処理であり,同じく y mod 2 を用いている。

設問4 キ:③の if 文は,各ピクセルについて拡散先の数 ratioCount 回呼び出されるので,全体では height×width×ratioCount 回呼び出される。ク:③の条件は「px が 1 以上」「px が width 以下」「py が 1 以上」「py が height 以下」の 4 つの比較演算と,それらを結ぶ 3 つの論理演算から成り,最大で 4+3=7 回の評価が行われる。

関連問題

本文が同じ・似ている問題を表示しています