Подведение итогов, оптимизация размеров - PullRequest
Новая
       35

Подведение итогов, оптимизация размеров

1 голос
/ 12 февраля 2012

У меня есть около 1000 изображений PNG (плиток) одинакового размера (32px x 32px).Все они выглядят по-разному, но некоторые очень похожи (они используют одинаковые цвета).Я должен суммировать их в PNG изображениях (блоки) с около 50 плиток каждый.Размер блока является динамическим, но не должен быть слишком маленьким.

Моя цель - минимизировать размер получаемых блоков.

Википедия говорит мне, что размер файла PNG зависит от глубины цвета на пиксель.

Моя идея состоит в том, чтобы сгруппировать плитки так, чтобы у каждой группы было наименьшее количество цветов.Также необходимо сохранить индекс цвета, поэтому сохранение каждой плитки в виде блока не будет оптимальным решением.Выполнение полного перебора потребовало бы очень много времени, поэтому я надеялся на хороший эскиз алгоритма группировки.

Я бы предположил, что размер файла «перепрыгивает», когда количество цветоввыходит за 1,2,4,8,16,32 и так далее.Так что это могут быть пороговые значения, на которые нужно обратить внимание.

Сейчас я набросаю алгоритм, который не дает оптимального решения

Определить

Введите расстояние для групповой плитки.Расстояние, которое группа мозаичных элементов A имеет до мозаичного элемента B, представляет собой количество различных цветов, находящихся в B, но не в группе A.

Color (G) - это общее количество различных цветов вгруппа плиток G.

Алгоритм

1) Выберите первую плитку и поместите ее в группу 1.

2) Зафиксируйте все оставшиеся плитки ипоместите плитку T с наименьшим расстоянием для групповой плитки d_T в Group1, если Colors (Group1) + d_T меньше или равно некоторому порогу, например 16. Повторяйте этот шаг, пока такая плитка не будет найдена.

3) Выберите следующую оставшуюся плитку и повторите процедуру.

Настройте порог, если слишком много или слишком мало групп.

К сожалению, это не обязательно приведет к наилучшему возможному результату.(возможно, может быть большая группа с тем же порогом).

Можно ли изменить этот алгоритм, чтобы получить оптимальное решение, или я должен выбрать другой подход?

Возможнолюбые факторы, которые влияютct размер PNG, который я не учел?

1 Ответ

1 голос
/ 25 марта 2012

Это можно разбить на две задачи:

  1. выбор изображений для объединения (чтобы получить минимальную палитру)

  2. выбор порядка ихВы находитесь (чтобы воспользоваться преимуществами фильтров PNG)

Палитра

Работа с гистограммами.Вы можете постеризовать цвета (обрезать младшие значащие биты), чтобы получить меньшие гистограммы и большее перекрытие между гистограммами разных изображений.

Затем сгруппируйте их, например, выполните попарную группировку наименьших разнородных гистограмм или используйте кластеризацию K-средних.

Различие будет измеряться количеством новых записей гистограммы, которые будут добавлены к общей гистограмме группы (например, если группа уже использует синий и розовый цвета, тогда синее изображение стоит 0, синий + красный стоит 1, желтый + зеленый стоит2).

Вы также можете взвешивать различия по количеству пикселей, используя данный цвет (sqrt(num_pixels) хорошо работает для pngquant ) и, возможно, расстояние от ближайшего доступного цвета в гистограмме группы.

Учитывается не только количество цветов, но и то, насколько хорошо они выбраны.Палитра с меньшей среднеквадратичной ошибкой почти всегда дает лучшее сжатие (количество визуальной информации на бит), потому что цвета не будут "расходоваться" плохо на менее важные области изображения.

Фильтры

Для первого приближения вы можете отсортировать изображения по их гладкости.Фильтры полезны для градиентов и, как правило, не помогают в шумных областях.

Тогда вы можете немного больше грубой силы путем случайного обмена изображениями, когда улучшается фильтрация эвристика , то есть:

  1. Выберите два изображения
  2. Рассчитайте эвристику для 32 строк пикселей в строках этих изображений
  3. Сохраняйте своп, если это улучшает оценку, откат назад, если это не так
  4. Оставьте это включенным на ночь

Сосредоточьтесь на # 1, поскольку фильтры не дают такой большой экономии, как оптимальная палитра.

...