中央値カット

メディアンカットは、各データセットを最長次元に沿った中央点で再帰的にカットすることにより、任意の次元数のデータを一連のセットに分類するアルゴリズムです。メディアンカットは通常、色の量子化に使用されます。たとえば、64k色の画像を256色に減らすには、メディアンカットを使用して元のデータとよく一致する256色を見つけます。^[1]

任意の数のピクセルを含む画像があり、16 色の​​パレットを生成するとします。画像のすべてのピクセル (つまり、そのRGB 値) をバケットに入れます。バケット内のピクセルの中で、どのカラー チャネル (赤、緑、青) の範囲が最大であるかを調べ、そのチャネルの値に従ってピクセルをソートします。たとえば、青チャネルの範囲が最大である場合、RGB 値(32, 8, 16)のピクセルは、RGB 値(1, 2, 24)のピクセルよりも小さくなります。これは、 16 < 24であるためです。バケットがソートされたら、ピクセルの上半分を新しいバケットに移動します (このステップが、メディアン カット アルゴリズムの名前の由来です。バケットは、ピクセル リストの中央値で 2 つに分割されます)。このプロセスを繰り返して、ピクセル セットをさらに細分化できます。分割するバケット (たとえば、任意のカラー チャネルの範囲が最大であるバケット) を選択し、それを 2 つに分割します。必要な数のバケットが生成されたら、各バケットのピクセルを平均して最終的なカラーパレットを取得します。

• kdツリー

• 画像の量子化
• 中央カット + バリエーション
• Image::Pngslimmer CPAN の Perl モジュール
• フレームバッファ表示のためのカラー画像量子化