色の量子化

コンピュータグラフィックスにおいて、色の量子化（いろのりょうしか、英語: color quantization）またはカラー画像の量子化（カラーがぞうのりょうしか、英語: color image quantization）とは元の画像とできるだけ同じに見えるようにしつつ、画像内で使われる異なる色の数を減らす手法である。1970年代からビットマップ画像上で色の量子化を行うコンピュータアルゴリズムの研究が行われてきた。色の量子化はメモリーの制限のためにの限られた色しか表示できないデバイス上で、多くの色を使って画像を表示するのに重要であり、効率的に画像を圧縮することができるようになっている。

24ビットRGBの画像

同じ画像を、できるだけ元の画像に似るように選んだ16色で表示した画像。

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

アルゴリズム

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

これまでで最もよく知られている色の量子化のアルゴリズムは1979年にポール・ヘックバート（Paul Heckbert）によって開発されたMedian cutである。この式に基づく多くの派生形が使われている。これが開発されるまで、色の量子化はほとんどが（population algorithm）や（population method）を用いて行われていた。これは、本質的には強さの範囲が同じである異なる色についてヒストグラムを描き、最も多くの点が含まれている範囲の色を割り当てるという方法である。より近代的で一般的な方法としては、ゲルヴァウツ（Gervautz） とプルガトファー（Purgathofer）が1988年に考案し、Xeroxパロアルト研究所の研究員ダン・ブルームバーグ（Dan Bloomberg）が改良した八分木を使うクラスタリングがある。

青（ブルー）のチャンネルを取り除いた画像。つまり、この画像のピクセルはすべて二次元の色平面から成っているということである。

左の画像の色平面。 Adobe Photoshopによって生成された16色の最適パレットに則っている。 各パレットにある色のボロノイ図の区切りが示されている。

OS内で働くときのように、リアルタイムで色が量子化されている時によく見られるようにパレットが固定されている場合、色の量子化は大抵直線距離（英語版）や最も近い色といったアルゴリズムを使って行われる。これは元の画像の色とパレットにある色を比較し、パレットにある色で最も元の画像に近い色を量子化した際の画像の色とすることである。ここで、色の「近さ」は「距離」を用いて定義できる。「距離」は次のように定義される。まずそれぞれの画像のRGBの値を測り、それぞれ$(r_{1},g_{1},b_{1})$および$(r_{2},g_{2},b_{2})$とする。このとき、以下の式で示されるユークリッド距離を最短にする色が「最も近い色」となる

${\sqrt {(r_{1}-r_{2})^{2}+(g_{1}-g_{2})^{2}+(b_{1}-b_{2})^{2}}}.$

このようにして効率的に色の立方体を、パレットにある色が点として描かれているボロノイ図に圧縮することができる。またボロノイ図を計算し、どの場所に色がないか決めるために計算幾何学から生まれた効率的なアルゴリズムも存在する。しかし実際は、指定されるパレットはとても小さいため、多くの場合見逃されてしまう。

4色のみを使い、空間的色の量子化を使って表示した画像

色の量子化はグラデーションを量子化したときに色の帯が見えるカラーバンディングなど不要なデジタルアーティファクトを取り除くディザと組み合わせられることが多い。最近の量子化プログラムの中には、パレットの色の選択とディザリングを同時に行うものもある。

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

画質が高いが動作が遅いNeuQuantというアルゴリズムは、テウボ・コホネンの自己組織化写像を使って入力された画像の色を256色に減らす。それぞれの「ニューロン」をとってRGB色空間中での位置に持っていき、質の高いカラーマップを与えてその位置の色に似た色を出させるというものである。これは特にグラデーション画像について利点が大きい。

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

歴史と応用

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

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

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

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

エディターのサポート

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

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

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

関連項目

• インデックスカラー
• ディザ

外部リンク・参考文献

• Paul S. Heckbert. Color Image Quantization for Frame Buffer Display. ACM SIGGRAPH '82 Proceedings. First publication of the median cut algorithm.
• Dan Bloomberg. Color quantization using octrees. Leptonica.
• Oleg Verevka. 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. On Spatial Quantization of Color Images. (full text .ps.gz) Technical Report IAI-TR-98-1、ボン大学、1998年.
• A. Schrader. Evolutionäre Algorithmen zur Farbquantisierung und asymmetrischen Codierung digitaler Farbbilder、WVB Verlag、ベルリン、1999年、Comprehensive Overview and Comparison of Color Quantization Algorithms.