配列ディザリングのソースを表示

[[Image:Ordered 4x4 Bayer matrix dithering.png|frame|グレースケールのグラデーションに、白黒2値のカラーパレットと4x4のしきい値マップを使った配列ディザリングを適用した例。この時、使われるタイルパターンは全17通り。]]
'''配列ディザリング'''（はいれつでぃざりんぐ）とは、画像を[[ディザリング]]するアルゴリズムの一つである。

このアルゴリズムは通常、[[色深度]]が小さくて表示可能な色数が少ないディスプレイにおいて、なるべく滑らかな画像を表示するために使用される。たとえば、[[Microsoft Windows]]は「[[Video Graphics Array|VGA]]標準16色グラフィックモード」の時に配列ディザリング法を用いてグラフィックを表示する。画像にこのアルゴリズムを適用した場合、特徴的なクロスハッチング状のタイルパターンがハッキリと現れる。 

== しきい値マップ ==
このアルゴリズムは「'''しきい値マップ'''（{{math|'''M'''}}）」を使って色数を減らす。ディスプレイに表示される画像の各ピクセルの色の値と、対応する「しきい値マップ」のセルの値を比較し、画面に表示する色を決める。その過程で、元画像の色と、そのディスプレイで利用可能なカラーパレットの色との差分が切り捨てられる。

「しきい値マップ」の大きさは任意に決めて構わないが、普通は「2の累乗 かける 2の累乗」のマトリクスを使う。ちなみに、この「しきい値マップ」のことを「テーブル」という日本人がいるが、「マトリクス」が正しい（「テーブル」は「値」で構成された表、「マトリックス」は「行」と「列」で構成された表、つまり「[[行列]]」のこと）。

{|
|-
|

:<math>
\mathbf{M} = \frac{1}{4} \times
\begin{bmatrix}
0 & 2 \\
3 & 1 \\
\end{bmatrix}
</math>

:<math>
\mathbf{M} = \frac{1}{16} \times
\begin{bmatrix}
 0 &  8 &  2 & 10 \\
12 &  4 & 14 &  6 \\
 3 & 11 &  1 &  9 \\
15 &  7 & 13 &  5 \\
\end{bmatrix}
</math>

:<math>
\mathbf{M} = \frac{1}{64} \times
\begin{bmatrix}
0  & 48 & 12 & 60 &  3 & 51 & 15 & 63 \\
32 & 16 & 44 & 28 & 35 & 19 & 47 & 31 \\
8  & 56 &  4 & 52 & 11 & 59 &  7 & 55 \\
40 & 24 & 36 & 20 & 43 & 27 & 39 & 23 \\
2  & 50 & 14 & 62 &  1 & 49 & 13 & 61 \\
34 & 18 & 46 & 30 & 33 & 17 & 45 & 29 \\
10 & 58 &  6 & 54 &  9 & 57 &  5 & 53 \\
42 & 26 & 38 & 22 & 41 & 25 & 37 & 21 \\
\end{bmatrix}
</math>

|}

このマップは、回転や反転を行ったとしてもアルゴリズムの有効性に影響を与えない。両辺の長さがどちらも2の累乗になった、このようなしきい値マップは「'''インデックスマトリクス'''」または「'''ベイヤーマトリクス'''」とも呼ばれる<ref name=bayermatrix>
{{cite journal
 |url=http://white.stanford.edu/~brian/psy221/reader/Bayer.1973.pdf 
 |last=Bayer 
 |first=Bryce 
 |authorlink=Bryce Bayer 
 |title=An optimum method for two-level rendition of continuous-tone pictures 
 |journal=IEEE International Conference on Communications 
 |volume=1 
 |pages=11–15 
 |date=June 11–13, 1973 
 |url-status=dead 
 |archiveurl=https://web.archive.org/web/20130512190753/http://white.stanford.edu:80/~brian/psy221/reader/Bayer.1973.pdf 
 |archivedate=2013-05-12 
}} </ref>。白黒2値で写真を表現するためにコダック社の[[ブライス・ベイヤー]]が考案し、1973年に発表した。（ベイヤー以後にもディザリング用に独自のマトリクスを考案した者は存在するが、結局ベイヤーマトリクスが一番早くて奇麗なのでずっと使われている。ランダムな値のマトリクスを使う「ランダムディザリング法」も存在するが、綺麗にうまくいくシーンはそれほど多くない）

配列ディザリング法を使う場合は、上記のマトリクスをそのまま使うのが一般的だが、もし任意のサイズのしきい値マップを自力で作りたい場合は、簡単な法則を使って制作できる。まず、各スロットを連続した整数で埋める。次に、マップ内の2つの連続した数同士の平均距離ができるだけ大きくなるように並べ替え、テーブルが端で「折り返される」ようにする{{Citation needed|date=February 2008}}。

次元が2の累乗であるしきい値マップの場合、マップは以下の定式で再帰的に生成できる。 

:<math>
\mathbf M_{2 n} = \frac{1}{(2n)^2} \times \begin{bmatrix}
4 \times \mathbf M_n & 4 \times \mathbf M_n + 2 \\
4 \times \mathbf M_n + 3 & 4 \times \mathbf M_n + 1
\end{bmatrix}
</math>

再帰式は、ビット演算のみを使用して明示的に計算できる<ref>Joel Yliluoma. “[http://bisqwit.iki.fi/story/howto/dither/jy/ Arbitrary-palette positional dithering algorithm]”</ref>。

 M(i, j) = bit_reverse(bit_interleave(bitwise_xor(i, j), i)) / n ^ 2

== 前処理したしきい値マップ ==
ディザリングが実行されるハードウェアの精度にもよるが、しきい値マップを、 0 から<math>n^2</math>までの整数を<math>n</math> x <math>n</math>のマトリクスとして保持しておくという伝統的な方式よりも、[[前処理]]で浮動小数点の形式にしたものを保持していた方が便利な場合がある。

その場合、以下の式が使われる。

 Mpre(i,j) = (Mint(i,j)+1) / n^2

これにより、「[[標準化]]（[[正規化]]）しきい値マトリクス」が生成される。

例えば2×2のしきい値マップは、

{|
|-
|
:<math>
\frac{1}{4} \times
\begin{bmatrix}
0 & 2 \\
3 & 1 \\
\end{bmatrix}
</math>
|}

であるが、これをベースとして「しきい値マップ」に前処理をかけると、

{|
|-
|
:<math>
\begin{bmatrix}
0.25 & 0.75 \\
1.0 & 0.5 \\
\end{bmatrix}
</math>
|}

となる。加えて言うと、前処理によって各値を正規化して合計を0に平均化するようなマップを作ることもできる。この場合、しきい値マップの全ての値から0.5を減算すればよい。

 Mpre(i,j) = (Mint(i,j)+1) / n^2 - 0.5

これにより、次のような前処理済ディザマップが生成される。

{|
|-
|
:<math>
\begin{bmatrix}
-0.25 & 0.25 \\
0.5 & 0 \\
\end{bmatrix}
</math>
|}

== アルゴリズム ==
[[ファイル:Game-Boy-Camera.jpg|thumb|right|120px|任天堂 [[ポケットカメラ]]（1998年発売）。配列ディザリング法は軽くて十分きれいなので、Z80カスタム（4MHz）を搭載した携帯型ゲーム機でも動画（縦112ドット×横128ドット、モノクロ4階調）のリアルタイム処理が可能]]
配列ディザリングのアルゴリズムは画像を自然に表現できるが、しかし画像のピクセルの各々においては、そのピクセルの色の値がしきい値マップの対応するセルの値で置き換えられることになるので、ピクセルの色の値のしきい値を超えた部分がカットされ、元の色とは異なる色に[[量子化]]されることになる。

配列ディザリング法のアルゴリズムを組むに際して、ほとんどの場合、すべてのピクセルにしきい値を追加して、ピクセルの値をしきい値と比較するだけで充分ディザリングの実用を満たすので、わざわざ0.5を減算して「しきい値マップ」を正規化する必要まではない。元画像のピクセルの輝度の値がベイヤーマトリクスの対応するセルの値よりも小さかった場合は、そのピクセルを「黒」で描写し、そうじゃなかった場合は「白」で描写する、みたいなアルゴリズムで充分である。ただ、正規化しなかった場合、画像の平均輝度がわずかに増加し、「ほとんど白に近いグレー」のピクセルがディザリングされずにそのまま白になる、という欠点がある。もっともこれは、グレースケールパレット（もしくは色同士の相対的な距離が（ほぼ）一定なカラーパレット）を使用する場合は問題とはならない。人間の目は明色の階調差よりも暗色の階調差の方をより正確に認識するため、「ほとんど白に近いグレー」を白飛びさせて暗色の階調差に割り振るのは、むしろ望ましいディザリング結果になるとすら言える。一方で、色数の特に少ないカラーパレットや任意の色で構成されたカラーパレットを使用してディザリングを行った場合は、元画像と全然違った見た目の画像が生成されることになるため、アルゴリズムを組む人は面倒がらずに適切な正規化を行った方が良い。

[[Image:Scale ordered dither.png|frame|配列ディザリング法で、64色のカラーパレット（左）を使って、140 x 140 = 19600色のカラースケールを表現したもの（右）]]

逆の目線で言うと、アルゴリズムは、すべてのピクセルの各カラーチャンネル「{{math|''c''}}」に対して次の変換を実行する。

:<math>
c' = \mathrm{nearest\_palette\_color}\mathopen{}\left(c + r \times \left(M(x \bmod n, y \bmod n) - \frac{1}{2}\right)\mathclose{}\right)
</math>

ここで、「{{math|''M''(''i'', ''j'')}}」は{{math|''i''}}番目の行と{{math|''j''}}番目の列のしきい値マップ、「{{math|''c''′}}」は変換された色、「{{math|''r''}}」は色空間における広がりの量である。RGBの各色が0から255までの[[オクテット (コンピュータ)|オクテット]]で表された、全「{{math|2<sup>3''N''</sup>}}」色の等間隔な色で構成されるカラーパレットを想定すると、一つの色は通常はこのような形で選択される。

:<math>r \approx \frac{255}{N}</math>

このアルゴリズムは1つ１つのピクセルのみを操作するもので、条件分岐もないため、非常に高速で、リアルタイム変換に適している。さらに、ディザパターンは表示フレームに対して常に同じ位置にあるため、[[誤差拡散法]]よりも[[ジッター]]（いわゆる「カクツキ」「チラツキ」、現代のゲームエンジンのレトロゲーム機風シェーダーでも問題になる）が発生しにくく、アニメーションに適している。誤差拡散法のディザパターンよりも反復的なタイリングであるため、配列ディザリングを使用した画像の圧縮率は高くなる。配列ディザリングは、直線が真っ直ぐに変換され、揺らぎが少ないため、イラストなど線画系の画像に適している（写真などは誤差拡散法の方が奇麗に出る）。

カラーパレットに合わせてしきい値マップを自作する場合、しきい値マップの値同士の差は、カラーパレットの色同士の最小の差と同じ範囲になるようにスケーリングすることが望ましい。

== 注釈 ==
<references />

== 参照 ==
* [http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/ordered_dithering.html Ordered Dithering] (Graphics course project, Visgraf lab, Brazil)
* [https://web.archive.org/web/20190316064436/http://www.efg2.com/Lab/Library/ImageProcessing/DHALF.TXT Dithering algorithms] (Lee Daniel Crocker, Paul Boulay and Mike Morra)

== 関連項目 ==
* [[誤差拡散法]]
* [[ドット絵]] - 配列ディザリングはタイルパターンが奇麗に出るので、画像のドット絵化（デジタイズ）に適している。

== 外部リンク ==
* [https://web.archive.org/web/20131022220241/http://michal.is:80/projects/image-dithering-in-matlab/ Matlab implementation of various dithering methods]
{{デフォルトソート:はいれつていさりんく}}
[[Category:画像処理]]