✋🏾 🍤 👃🏼 PNGパレットのクラスタリングと圧縮 🚦 🏯 💼

注釈

この記事では、読者がPNG形式で保存された画像を圧縮するアルゴリズムの開発を体験するように招待されています。圧縮は、分類器K –グループ内平均を使用してパレットを量子化することにより実行されます。 Javaで記述されたアルゴリズムのソースコードが提供されます。アルゴリズムを改善するための問題とさらなる方法が示されています。

はじめに

PNG形式（「ping」と発音）は、ビットマップイメージの保存と送信を目的としています。この形式は、画像データの段階的な表示、ガンマインデックスに関する情報の保存、各ピクセルの透明度、およびテキスト情報を提供します。この形式は、効率的なロスレス圧縮方法を使用します[1]。

PNGファイル（またはデータストリーム）は、識別署名と少なくとも3つのデータで構成されます。 PNGは、クリティカル部分と呼ばれる4つの標準部分を定義します。これは、すべてのリーダーとライターによってサポートされる必要があります[1]：

サービングヘッダー（IHDR）。
部分パレット（PLTE）-画像データに関連付けられたカラーテーブルデータを格納します。この部分は、画像データがカラーパレット（カラーインデックス）を使用している場合にのみファイルに存在します。
画像データの一部（IDAT）。
最後の部分（IEND）。

PNG形式の説明と機能の詳細については、[2]を参照してください。また、フォーマットで使用される圧縮アルゴリズムについて説明し、範囲を示します。

PNG形式で保存される画像のサイズを縮小する主な目的は、画像に表示されるさまざまな色の数を減らすことです。さらに、元の数の色が失われることは、人間の目にはまったく見えません。著者によると、今日（2011年2月）の最高品質のプログラムの1つはColor Quantizer（CQ）です[3]。このプログラムの主な機能は次のとおりです。

任意の数の色に変換し、
パレットの便利な編集、
バッチ最適化。

さらなる調査のためのテスト図面として、下の図1に示す[4]から画像を選択します。図1にはアルファチャネルが含まれておらず、チェスの背景は単なる模造品であることに注意してください。元の画像には43,500の一意の色が含まれています。 CQプログラムを使用して、画像に残っている色の数と出力ファイルのサイズに関するデータを含む表1をコンパイルしました。 CQで圧縮する場合、25％のエラーレベルが設定されました。

表1-CQプログラムを使用した画像圧縮率

色数	サイズ、ディスク上のバイト
43,500（ソース）	184 320
4096	147 456
1024	106 496
256	53,248

表1のデータからわかるように、色の数を256に減らすと、結果のファイルのサイズは53,248バイトになり、元のファイルのほぼ3.5倍になります。

図1-研究用のテスト画像フォーマットPNG、解像度-800x600

QEを使用した圧縮画像、256色

図2-Color Quantizerを使用した最大256色の圧縮画像

開発したアルゴリズム、256色を使用した圧縮画像

図3-開発されたアルゴリズムを使用して256色に圧縮された画像

当然のことながら、このような深刻な色の喪失は画像の痕跡なしでは通じませんが、この場合、著者の意見では重要ではありません。図2は、最大256色の圧縮画像を示しています。したがって、Webで画像を使用する場合に特に重要な色の数を減らすだけで、PNG画像のボリュームを大幅に減らすことができます。ただし、これはそれほど単純ではなく、CQプログラムには重大な欠点があります-操作が極端に遅いため、たとえば、地理情報システムからデータを送信するときにリアルタイムで使用するのが難しくなります。画像を圧縮するのにかかる時間は、元の圧縮されていない画像を送信するのにかかる時間よりも数倍長いことがわかります。

次の章では、画像のパレット（ここではPLTEの部分については説明していません）を量子化（クラスタリング）することにより、画像の色数をリアルタイムで削減できる非常にシンプルでかなり高速なアルゴリズムについて説明します。

イメージパレットクラスタリングアルゴリズム

画像パレットは、画像で使用される色のセットです。画像がRGB形式で保存されている場合、このセットの各ポイントには、赤、緑、青の3つの座標があります。 ARGB形式の場合は、アルファチャネルまたは透明度という非常に重要なコンポーネントがもう1つ追加されます。

パレットは、RGBの場合は3次元、ARGB空間の場合は4次元の点のセットとして表すことができます。画像に滑らかな移行と色のハーフトーンが存在するため、ポイントは「クラウド」、いわゆるクラスターを形成します。このクラスターでは、同じクラスターのすべてのポイントが互いに近い色を持ちます。したがって、同じクラスターに含まれるポイントに対して、1つの平均化された（オプションの1つ）色を割り当てて、セットの寸法（パレット）を減らすことができます。

ただし、最初に色間の近接性の測定値を決定する必要があります。多くのオプションがあり、それらはすべて視覚的に均一な色空間の構築に基づいています[5]。この記事では、著者は最も単純なアプローチを使用しています-加重ユークリッドメトリックが選択されています。この場合、ARGB形式の色間の距離は、式

ここで、 xおよびyは、成分{x _A 、x _R 、x _G 、x _B }、{y _A 、y _R 、y _G 、y _B }の色であり、 α、β、γ、εは、おそらく視覚的な均一性を提供するパラメーターです。実験的に選択されます。

多くのデータクラスタリングアルゴリズムが開発されました[6]。最も単純なアルゴリズムの1つはK –グループ内平均です。このアルゴリズムは、次の手順で表すことができます。

0.必要なN個のクラスターの場合、セットのN個のポイントが取得されます（例：最初の番号）。
1.見つかったクラスターごとに、中心、つまりクラスターに含まれるすべてのオブジェクトの平均値（重心）を計算します。
2.セットの各オブジェクトについて、N個のクラスターそれぞれへの距離のセットを計算します。
3.セットの各オブジェクトは、そのクラスターに起因し、距離は最小になります。
4.クラスタリングの品質に関する特定の正式な基準が満たされるまで、ステップ1に進みます。

著者は、反復クラスタリングアルゴリズムを停止するために次の基準を使用しました。現在のステップでクラスターを変更したオブジェクトの数が前のステップでの同じオブジェクトの数と等しい場合、反復は終了します。

このアルゴリズムの実装は、大きな困難を引き起こしません。記事に添付されているファイルには、アルゴリズムのソースコードが含まれています。 PNG画像を操作するには、PNGEncoderモジュール[7]が使用されます。

ソーステキストを含むアーカイブをダウンロードするためのリンク

関数を呼び出して色の数を減らす例

 String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; //  PNG  PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); //   CPNGCompression.Compression(bufImage, true , ColorCounts); //  encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); //    encoder.setCompression(encoder.BEST_COMPRESSION); //   PNG //   ( PLTE) -       255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); //    FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; // PNG PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); // CPNGCompression.Compression(bufImage, true , ColorCounts); // encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); // encoder.setCompression(encoder.BEST_COMPRESSION); // PNG // ( PLTE) - 255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); // FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

 String imageFileName = "D:/Projects/PNG/big.png" ; String outImageFileName = "D:/Projects/PNG/bigout" ; int ColorCounts = 255; //  PNG  PngImage image = new PngImage(); BufferedImage bufImage = image.read( new File (imageFileName)); //   CPNGCompression.Compression(bufImage, true , ColorCounts); //  encoder.setColorType(encoder.COLOR_INDEXED_ALPHA); //    encoder.setCompression(encoder.BEST_COMPRESSION); //   PNG //   ( PLTE) -       255 encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO); //    FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png" ); encoder.encode(bufImage, outfile); outfile.flush(); outfile.close(); * This source code was highlighted with Source Code Highlighter .

関数シグネチャ

 public static void Compression ( BufferedImage aImage, //    boolean aUseFixedColorList, //       int aColorCount //      ) * This source code was highlighted with Source Code Highlighter .

public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .

public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .

public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .

public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .

public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .

public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .

public static void Compression ( BufferedImage aImage, // boolean aUseFixedColorList, // int aColorCount // ) * This source code was highlighted with Source Code Highlighter .

 public static void Compression ( BufferedImage aImage, //    boolean aUseFixedColorList, //       int aColorCount //      ) * This source code was highlighted with Source Code Highlighter .

圧縮関数は、CPNGCompressionクラスに対して静的です。 aUseFixedColorListパラメーターがtrueに設定されている場合、画像の一部の色は「タッチ不可」になります。そのような色のリストは、CPNGCompressionクラスの静的配列で構成されます。タッチできない色が導入されているため、たとえば、グレーの形成と白と黒の混合（クラスターの中心を計算する場合）がありません。

分類の視覚的品質は、式（1）の係数に強く依存すると仮定するのが論理的です。式（1）は、限られたクラスの画像に対して決定できます。たとえば、著者は特別な地図作成データに次の値を選択しました： α= 100、β= 30、γ= 59、ε= 11 。

図3は、開発したアルゴリズムを使用して、元の画像を256色に圧縮した結果を示しています。開封、圧縮、保持の合計時間は4700ミリ秒でした。出力ファイルサイズは53,248バイトで、CQプログラムの場合も同様です（表1）。ご覧のとおり、図3は図2と比較して背景色が変更されており、 視覚的には灰色よりも黄色に近くなっています。背景を構成する「タッチ不可」な白とグレーの色を指定すると、この欠陥は簡単に解消されます。

おわりに

この記事では、画像の色数を減らすタスクで使用される最も単純なクラスタリングアルゴリズムの1つを検討します。このアルゴリズムは、よく知られているソリューションであるCQプログラムと比較されます。アルゴリズムのさらなる改善は、

反復を完了するための基準の変更、
色間の距離関数の変更、
クラスタリング中に別の色空間に移行します。

記事への追加-コメントに基づく

主な記事では、このアルゴリズムによって「タッチ不可な色」を使用して圧縮された画像は提供していません。タッチできない色を次のように設定します。

 //    CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; //  CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

// CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; // CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

 //    CPNGCompression.m_fixedColors = new int [2]; CPNGCompression.m_fixedColors[0] = 0xFF969696; CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF; //  CPNGCompression.Compression(bufImage, true , 256); * This source code was highlighted with Source Code Highlighter .

この場合、ここで検討したアルゴリズムによる圧縮の結果は画像になります。

図4- タッチできない2色を使用した圧縮画像

このイメージのサイズは、ディスク上でも53,243バイトです。

CQプログラムの動作時間と、私が知らない所望の精度とを比較する方法。

システムクロックを+ -2秒の精度で使用すると、CQは34秒で256色に圧縮されます。これは、提案されたアルゴリズムの結果よりも1桁劣っています。

使用したソース

D.マレー、W。ヴァンリパー。グラフィックファイル形式の百科事典。
Greg Roelofs、Ivan Zenkov、Dimok Busheff。 PNG：フォーマット/ リンク機能の簡単な紹介
Color Quantizer：ウェブ/ リンク用に画像を簡単に最適化できるプログラム
ウィキペディアの資料、テスト画像、GNU Free Documentation License / リンク
A.I. T.E.クリコフオヴチンニコフ。 CIE Luv Space、現代のコンピュータグラフィックス/ リンクのアルゴリズムの基礎
データクラスタリングアルゴリズム/ リンクの概要
PNG画像を操作するためのPNGEncoderパッケージ、Java / リンク

PNGパレットのクラスタリングと圧縮

注釈