色の量子化のソースを表示

{{Stack|float=right|
[[ファイル:Dithering example undithered.png|frame|[[24ビット]]RGBの画像]]
[[ファイル:Dithering example undithered 16color.png|frame|同じ画像を、できるだけ元の画像に似るように選んだ16色で表示した画像。]]
}}
{{色}}
[[コンピュータグラフィックス]]において、'''色の量子化'''（いろのりょうしか、{{Lang-en|color quantization}}）または'''カラー画像の量子化'''（カラーがぞうのりょうしか、{{Lang-en|links=no|color image quantization}}）とは元の[[画像]]とできるだけ同じに見えるようにしつつ、画像内で使われる異なる色の数を減らす手法である。1970年代から[[ビットマップ画像]]上で色の量子化を行うコンピュータ[[アルゴリズム]]の研究が行われてきた。色の量子化は[[記憶装置|メモリー]]の制限のためにの限られた色しか表示できないデバイス上で、多くの色を使って画像を表示するのに重要であり、効率的に画像を[[データ圧縮|圧縮]]することができるようになっている。

''色の量子化''という言葉は当初はコンピュータグラフィックスの研究{{仮リンク|科学文献|en|Scientific literature|label=文献}}で用いられていた。[[アプリケーションソフトウェア|アプリケーション]]では、最大{{仮リンク|パレット (コンピュータ)|en|Palette (computing)|label=パレット}}生成（optimized palette generation）、最適パレット生成（optimal palette generation）、[[色深度]]減少（decreasing color depth）といった専門用語が用いられた。標準のアルゴリズムで生成されるパレットは必ずしも最適なものではないので、これらのうち一部は誤解を招く言葉である。

== アルゴリズム ==
多くの標準的な技術では色の量子化は[[三次元]]空間な点の集合（クラスター）として扱われる。この時、点が色、3つの軸が3つの色{{仮リンク|チャンネル (デジタル画像)|en|Channel (digital image)|label=チャンネル}}を表す。ほぼすべての3次元[[データ・クラスタリング|クラスタ・アルゴリズム]]が色の量子化に適用できるし、その逆も可能である。クラスターの位置が定まると、普通はクラスター内の点の色はならされ、そのクラスターの全ての点がそのクラスターの中で最も点の数が多かった色に統一される。3色のチャンネルの色は多くの場合[[RGB|赤、緑、青]]であるが、[[ユークリッド距離]]が色の認識の違いにより即している[[Lab色空間]]などの[[色空間]]もある。

これまでで最もよく知られている色の量子化のアルゴリズムは1979年にポール・ヘックバート（Paul Heckbert）によって開発された{{仮リンク|Median cut|en|Median cut}}である。この式に基づく多くの派生形が使われている。これが開発されるまで、色の量子化はほとんどが（population algorithm）や（population method）を用いて行われていた。これは、本質的には強さの範囲が同じである異なる色について[[ヒストグラム]]を描き、最も多くの点が含まれている範囲の色を割り当てるという方法である。より近代的で一般的な方法としては、ゲルヴァウツ（Gervautz） とプルガトファー（Purgathofer）が1988年に考案し、[[Xerox]][[パロアルト研究所]]の研究員ダン・ブルームバーグ（Dan Bloomberg）が改良した[[八分木]]を使うクラスタリングがある。
{|
|[[ファイル:Rosa Gold Glow 2 small noblue.png|frame|left|青（ブルー）のチャンネルを取り除いた画像。つまり、この画像の[[ピクセル]]はすべて二次元の色平面から成っているということである。]]
||[[ファイル:Rosa Gold Glow 2 small noblue color space.png|thumb|left|300px|左の画像の色平面。 [[Adobe Photoshop]]によって生成された16色の最適パレットに則っている。 各パレットにある色の[[ボロノイ図]]の区切りが示されている。]]
|}
[[オペレーティングシステム|OS]]内で働くときのように、リアルタイムで色が量子化されている時によく見られるようにパレットが固定されている場合、色の量子化は大抵''直線距離''（[[:en:As the crow flies|英語版]]）や''最も近い色''といったアルゴリズムを使って行われる。これは元の画像の色とパレットにある色を比較し、パレットにある色で最も元の画像に近い色を量子化した際の画像の色とすることである。ここで、色の「近さ」は「距離」を用いて定義できる。「距離」は次のように定義される。まずそれぞれの画像のRGBの値を測り、それぞれ<math>(r_1, g_1, b_1)</math>および<math>(r_2, g_2, b_2)</math>とする。このとき、以下の式で示されるユークリッド距離を最短にする色が「最も近い色」となる
:<math>\sqrt{(r_1-r_2)^2 + (g_1-g_2)^2 + (b_1-b_2)^2}.</math>
このようにして効率的に色の立方体を、パレットにある色が点として描かれているボロノイ図に圧縮することができる。またボロノイ図を計算し、どの場所に色がないか決めるために[[計算幾何学]]から生まれた効率的なアルゴリズムも存在する。しかし実際は、指定されるパレットはとても小さいため、多くの場合見逃されてしまう。
[[ファイル:Spatial color quantization - rainbow, 4 colors.png|thumb|256px|4色のみを使い、空間的色の量子化を使って表示した画像]]
色の量子化は[[グラデーション]]を量子化したときに色の帯が見える[[バンディング (色)|バンディング]]など不要な[[デジタルアーティファクト]]を取り除く[[ディザ]]と組み合わせられることが多い。最近の量子化プログラムの中には、パレットの色の選択とディザリングを同時に行うものもある。

他にも、ここまで挙げてきたものほど使われていないものの全く異なるアプローチをとる方法がたくさん開発されてきた。1995年にオレッグ・ヴェルフカ（Oleg Verevka）によって考案された[[K平均法|K平均アルゴリズム]]は、画面上に異なる[[配色]]の多くの画像が同時に表示され、また受け入れられる色が決まっている[[ウィンドウシステム]]のために設計された。それはパレットを根本から考え直し、繰り返し磨きをかけたクラスタリングの上を行く方法である。

[[画質]]が高いが動作が遅い''NeuQuant''というアルゴリズムは、{{仮リンク|テウボ・コホネン|en|Teuvo Kohonen}}の[[自己組織化写像]]を使って入力された画像の色を256色に減らす。それぞれの「[[神経細胞|ニューロン]]」をとってRGB色空間中での位置に持っていき、質の高い{{仮リンク|カラーマッピング|en|Color mapping|label=カラーマップ}}を与えてその位置の色に似た色を出させるというものである<ref>[http://members.ozemail.com.au/~dekker/NEUQUANT.HTML NeuQuant: Fast High-Quality Image Quantization]</ref>。これは特にグラデーション画像について利点が大きい。

最後に、[[ボン大学]]のプッチーチャ（Puzicha）、ヘルト（Held）、ケットラー（Ketterer）、ブーマン（Buhmann）とフェルナー（Fellner）が考案した空間的色の量子化（spatial color quantization）を紹介する。これはパレットの生成を含むディザリングと、色の数が少なくても印象に残るようにモデル化した人間の知覚を組み合わせたものである。これはクラスタリングとしてのパレットの色選びをあまり厳密には行わず、元の画像での近くの[[ピクセル]]の色の影響も量子化された画像のピクセルへの影響に含まれている。[http://www.cs.berkeley.edu/~dcoetzee/downloads/scolorq/#sampleimages サンプル画像はこちら]。

== 歴史と応用 ==
初期の[[パーソナルコンピュータ|PC]]では、メモリー制限の関係でビデオのアダプターは2色、4色、16色か、どんなに多くても256色しかサポートしていなかった。ビデオは、映像の色を増やすよりも映像の[[解像度]]を上げることにメモリーを割いていたからである。色の量子化は、少ない色で多くの色を表現できるようにすることで、この傾向を正当化することとなった。多くのOSが、色の多い画像を256色のビデオモードで見ている時には自動的に量子化とディザリングを実行している。これは、かつてはほとんどの映像デバイスが256色に制限されていたからである。最近のコンピューターは一度に数百万色を表示できる。これは人間の眼がそれら全てを識別するのは不可能な値である。よってこのアプリケーションはモバイルのデバイスと旧式の[[ハードウェア]]に残るのみとなった。

現在、色の量子化は[[Graphics Interchange Format|GIF]]や[[Portable Network Graphics|PNG]]画像に主に使われている。長い間[[World Wide Web|WWW]]のビットマップ[[ファイルフォーマット|フォーマット]]であるGIFは256色までしかサポートしていないので、多くの画像で量子化が必要だった。初期の[[ウェブブラウザ]]の中には画像を[[ウェブカラー]]と呼ばれる特定のパレットを使って見なければならないものがあり、最適化パレットに比べ画質の低下が激しかった。PNG画像は[[24ビット]]カラーをサポートしているが、画質をあまり低下させずに[[ファイルサイズ]]を圧縮するため、色の量子化のアプリケーションを使うことも多い。なぜならPNGファイルはパレットの色を使った画像に対しては1ピクセルあたりの使用[[ビット数]]が少ないからである。

[[カメラ]]の[[レンズ]]を通して得た無限色の画像をコンピューターの[[スクリーン]]にそのまま映し出すのは不可能である。したがって、どんな写真も必ず[[デジタイズ|デジタル化]]しなければならない。これには量子化が関わってくる。

表示できる色が少ない初期のコンピューターで量子化アルゴリズムを実行すると、異なる量子化アルゴリズムを使えば同じ画像でもまったく違う画像が出力される。結果として、元の画像にそっくりな画像を出力できるアルゴリズムを作るのに長い時間がかかった。

=== エディターのサポート ===
多くの[[ペイントソフト|ビットマップ描画ソフト]]では色の量子化がサポートされており、多色の画像を少ない色にしか対応していない画像フォーマットに変換するときには自動的に実行される。この処理のおかけでユーザーは欲しい色の数をきっちり決めることができる。

また、色の量子化は{{仮リンク|色調分離|en|Posterization}}効果を生み出すのにも使われている。ただし、色調分離は同じ色空間内で色の数を減らすことを目標とするのとほとんど変わらない。よって、普通はパレットが固定されているときに用いられる。

[[ベクター画像]]の[[ドローソフト|描画ソフト]]中にも色の量子化を使うものがある。特に縁を見つけてビットマップ画像のトレースを作り、ラスターを[[ベクトル化]]する技術に応用されている。


== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[インデックスカラー]]
* [[ディザ]]

== 外部リンク・参考文献 ==
* Paul S. Heckbert. [https://web.archive.org/web/20050606233131/http://citeseer.ist.psu.edu/heckbert80color.html Color Image Quantization for Frame Buffer Display]. {{仮リンク|ACM SIGGRAPH|en|ACM SIGGRAPH}} '82 Proceedings. First publication of the median cut algorithm.
* Dan Bloomberg. [http://www.leptonica.com/papers/colorquant.pdf Color quantization using octrees]. Leptonica.
* Oleg Verevka. [http://citeseer.ist.psu.edu/100440.html Color Image Quantization in Windows Systems with Local K-means Algorithm]. ''Proceedings of the Western Computer Graphics Symposium '95.''
* J. Puzicha, M. Held, J. Ketterer, J. M. Buhmann, and D. Fellner. [http://www.iai.uni-bonn.de/III/forschung/publikationen/tr/abstracts/IAI-TR-98-1.abstract-en.html On Spatial Quantization of Color Images]. ([http://www.informatik.uni-bonn.de/III/forschung/publikationen/tr/reports/IAI-TR-98-1.ps.gz full text .ps.gz]) Technical Report IAI-TR-98-1、[[ボン大学]]、1998年.
* A. Schrader. [http://www.andreas-schrader.de/publications.html Evolutionäre Algorithmen zur Farbquantisierung und asymmetrischen Codierung digitaler Farbbilder]、WVB Verlag、[[ベルリン]]、1999年、Comprehensive Overview and Comparison of Color Quantization Algorithms. 

{{デフォルトソート:いろのりようしか}}
[[Category:画像処理]]