1

同じサイズ（32px x 32px）のPNG画像（タイル）が約1000枚あります。それらはすべて異なって見えますが、いくつかは非常に似ています（それらは同じ色を使用します）。それぞれ約50タイルのPNG画像（ブロック）にまとめる必要があります。ブロックサイズは動的ですが、小さすぎないようにする必要があります。

私の目標は、結果のブロックのサイズを最小化することです。

ウィキペディアによると、PNGファイルのサイズはピクセルあたりの色深度に依存します。

私の考えは、各グループの色の量が最小になるようにタイルをグループ化することです。また、カラーインデックスを保存する必要があるため、各タイルをブロックとして保存することは最適なソリューションではありません。ブルートフォース攻撃を行うには非常に長い時間がかかるため、グループ化アルゴリズムの優れたスケッチを期待していました。

色の量が1、2、4、8、16、32などを超えると、ファイルサイズが「ジャンプ」すると思います。したがって、これらは注意すべきしきい値になる可能性があります。

次に、最適なソリューションを生成しないアルゴリズムをスケッチします

定義

グループタイルの距離を導入します。タイルAのグループからタイルBまでの距離は、Bにはあるが、グループAにはないさまざまな色の量です。

Color（G）は、タイルGのグループ内のさまざまな色の合計量です。

アルゴリズム

1）最初のタイルを選び、それをGroup1に入れます。

2）残りのすべてのタイルをループし、グループタイルの距離d_Tが最小のタイルTをGroup1に配置します（Colors（Group1）+ d_Tがしきい値よりも小さい場合、たとえば16）。そのようなタイルが見つからなくなるまでこの手順を繰り返します。 。

3）次に残っているタイルを選び、手順を繰り返します。

グループが多すぎるか少なすぎる場合は、しきい値を調整します。

残念ながら、これは必ずしも最良の結果をもたらすとは限りません（同じしきい値で可能なより大きなグループが存在する可能性があります）。

このアルゴリズムを変更して最適なソリューションを返すことはできますか、それとも別のアプローチを選択する必要がありますか？

PNGのサイズに影響を与える要因はありますか？私は考慮していませんでしたか？

4

1 に答える 1

1

これは2つの問題に分けることができます。

  1. 組み合わせる画像の選択（最小限のパレットを取得するため）

  2. それらが入っている順序を選択する（PNGフィルターを利用するため）

パレット

ヒストグラムを操作します。色をポスタライズ（最下位ビットを切り捨てる）して、異なる画像のヒストグラムを小さくし、ヒストグラム間のオーバーラップを大きくすることができます。

次に、それらをグループ化します。たとえば、最も類似性の低いヒストグラムのペアワイズグループ化を行うか、K-meansクラスタリングを使用します。

非類似度は、グループの合計ヒストグラムに追加される新しいヒストグラムエントリの数によって測定されます（たとえば、グループがすでに青とピンクの色を使用している場合、青の画像のコストは0、青と赤のコストは1、黄と緑のコストは2）。

また、特定の色（pngquantsqrt(num_pixels)で適切に機能）を使用してピクセル数で非類似度を評価し、グループのヒストグラムで使用可能な最も近い色からの距離を評価することもできます。

生の色の数だけでなく、それらの色がどれだけうまく選択されているかも重要です。平均二乗誤差が小さいパレットは、画像の重要度の低い領域で色が適切に「使用」されないため、ほとんどの場合、圧縮率（ビットあたりの視覚情報の量）が向上します。

フィルタ

最初の近似では、画像を滑らかさで並べ替えることができます。フィルタはグラデーションに役立ち、通常、ノイズの多い領域では役に立ちません。

次に、フィルタリングヒューリスティックが改善されたときに画像をランダムに交換することで、もう少しブルートフォース攻撃を行うことができます。

  1. 2つの画像を選択してください
  2. それらの画像の行の32行のピクセルのヒューリスティックを計算します
  3. スコアが向上する場合はスワップを維持し、向上しない場合はバックトラックします
  4. 一晩実行したままにします

フィルタは最適なパレットほど大きな節約にはならないため、＃1に注目してください。

于 2012-03-24T21:34:22.853 に答える