Pull to refresh

Кластеризация палитры изображения и сжатие в формате PNG

Algorithms *
Sandbox

Аннотация


В данной статье читателю предлагается опыт разработки алгоритма сжатия изображения, хранящегося в формате PNG. Сжатие осуществляется за счет квантования палитры с использованием классификатора К–внутригрупповых средних. Приводится исходный код алгоритма, написанный на языке Java. Указываются проблемы и дальнейшие пути улучшения алгоритма.

Введение


Формат PNG (произносится как «пинг») предназначен для хранения и передачи растровых изображений. Формат обеспечивает поэтапное отображение данных изображения, хранение информации о показателе гамма, о прозрачности каждого пикселя, а так же текстовой информации. Формат использует эффективный метод сжатия без потерь [1].
Файл (или поток данных) в формате PNG состоит из идентификационной подписи и не менее чем трех порций данных. В PNG определены четыре стандартные порции, называемые критическими порциями, которые должны поддерживаться всеми программами чтения и записи [1]:
  1. Порция заголовка (IHDR).
  2. Порция палитры (PLTE) – хранит данные цветовой таблицы, связанные с данными изображения. Эта порция присутствует в файле только в том случае, когда данные изображения используют цветовую палитру (индексацию цвета).
  3. Порция данных изображения (IDAT).
  4. Завершающая порция (IEND).

Подробнее про описание и особенности формата PNG приведено в [2]. Там же описываются алгоритмы сжатия, используемые форматом и указываются области применения.
Основная идея уменьшения размера картинки, хранящейся в PNG формате, состоит в уменьшении количества различных цветов представленных на изображении. При этом потеря исходного количества цветов может быть совершенно незаметна для глаза человека. По мнению автора одна из самых качественных на сегодняшний (02.2011) момент программ – Color Quantizer (CQ) [3]. К основным возможностям этой программы относится:
  • конвертирование в произвольное количество цветов,
  • удобное редактирование палитры,
  • пакетная оптимизация.

В качестве тестового рисунка для дальнейших исследований выберем изображение из [4], представленное на рисунке 1 ниже. Отметим, что рисунок 1 не содержит альфа канала и шахматный фон — лишь имитация. Исходное изображение содержит 43500 уникальных цветов. С использованием программы 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 – Сжатое до 256 цветов изображение с использованием программы Color Quantizer

Сжатое изображение с использованием разработанного алгоритма, 256 цветов
Рисунок 3 — Сжатое до 256 цветов изображение с использованием разработанного алгоритма

Естественно такая серьезная потеря цвета не может пройти бесследно для изображения, однако в данном случае она на взгляд автора несущественна. На рисунке 2 представлено сжатое до 256 цветов изображение. Таким образом, можно существенно уменьшить объем PNG картинки простым уменьшением количества цветов, что особенно важно при использовании изображений в web. Однако сделать это не так просто, программа CQ обладает существенным недостатком – крайне медленная скорость работы, что делает затруднительным ее использование в режиме реального времени, например, при передаче данных геоинформационных систем. Оказывается, что время, которое требуется для сжатия изображения, в разы превосходит время необходимое для передачи исходного – несжатого изображения.
В следующей главе будет описан очень простой и достаточно быстрый алгоритм, позволяющий в режиме реального времени уменьшать количество цветов на изображении путем квантования (кластеризации) палитры (здесь речь не о PLTE порции) изображения.

Алгоритм кластеризации палитры изображения


Палитра изображение представляет собой множество цветов, используемых на изображении. Если изображение хранится в формате RGB, то каждая точка этого множества имеет три координаты – Red, Green, Blue; а если в формате ARGB, то добавляется еще одна, очень важная компонента – альфа канал или прозрачность.
Палитру можно представить набором точек в трехмерном для RGB или четырехмерном для ARGB пространствах. За счет присутствия на изображении плавных переходов и полутонов цвета, точки будут образовывать «облака» — так называемые кластеры, где все точки одного кластера имеют близкий друг другу цвет. Поэтому, для точек, которые попали в один кластер, можно назначить один усредненный (один из вариантов) цвет, и уменьшить за счет этого размерность множества – палитры.
Однако вначале необходимо определить меру близости между цветами. Существует множество вариантов, все они основаны на построении пространства цветов которое визуально равномерно [5]. В данной статье автор применяет наиболее простой подход – выбирается взвешенная Евклидова метрика. В этом случае расстояние между цветами в формате ARGB определяется формулой
image
где x и y — цвета с компонентами {xA, xR, xG, xB}, {yA, yR, yG, yB} а α, β, γ, ε — параметры, возможно обеспечивающие визуальную равномерность, которые подбираются экспериментально.
Разработано множество алгоритмов кластеризации данных [6], один из самых простых алгоритмов – К–внутригрупповых средних, который используется, если известно количество кластеров, на которые разбивается множество объектов (в нашем случае – множество цветов). Алгоритм может быть представлен следующими шагами:
  • 0. За N искомых кластеров принимаются любые N точек множества, например первые по номеру.
  • 1. Для каждого найденного кластера рассчитываем центр – среднее значение (центр масс) среди всех объектов, включенных в него.
  • 2. Для каждого объекта из множества рассчитываем набор расстояний до каждого из N кластеров.
  • 3. Каждый объект множества относим в тот кластер, расстояние до которого минимально.
  • 4. Переходим к шагу 1, до тех пор, пока не удовлетворен некоторый формальный критерий качества кластеризации.

Автор использовал следующий критерий останова итерационного алгоритма кластеризации: итерации прекращаются, если количество объектов изменивших свой кластер на текущем шаге равно количеству таких же объектов на предыдущем шаге.
Реализация данного алгоритма не вызывает существенных сложностей. В файле, прикрепленном к статье приведен исходный код алгоритма. Для работы с PNG изображением используется модуль PNGEncoder [7].
Ссылка для скачивания архива с исходным текстом

Пример вызова функции уменьшения количества цветов


  1. String imageFileName = "D:/Projects/PNG/big.png";
  2. String outImageFileName = "D:/Projects/PNG/bigout";  
  3. int ColorCounts = 255;
  4. // Чтение PNG картинки
  5. PngImage image = new PngImage();
  6. BufferedImage bufImage = image.read(new File(imageFileName));
  7. // Сжатие картинки
  8. CPNGCompression.Compression(bufImage, true, ColorCounts);
  9. // Сохранение
  10. encoder.setColorType(encoder.COLOR_INDEXED_ALPHA);// Поддержка альфа канала
  11. encoder.setCompression(encoder.BEST_COMPRESSION); // Уровень сжатия PNG
  12. // Индексированная палитра (блок PLTE) - поддерживается если количество цветов не превышает 255
  13. encoder.setIndexedColorMode(encoder.INDEXED_COLORS_AUTO);
  14. // Запись в поток
  15. FileOutputStream outfile = new FileOutputStream(outImageFileName + ".png");
  16. encoder.encode(bufImage, outfile);    
  17. outfile.flush();
  18. outfile.close();
* This source code was highlighted with Source Code Highlighter.


Сигнатура функции
  1. public static void Compression
  2. (
  3.  BufferedImage aImage, // Изображение для сжатия
  4.  boolean aUseFixedColorList, // Настроены ли цвета которые нельзя изменять
  5.  int aColorCount // Количество требуемых цветов на выходе
  6. )
* This source code was highlighted with Source Code Highlighter.


Функция Compression — статическая для класса CPNGCompression. Если параметр aUseFixedColorList установлен в true, то некоторые цвета на изображении становятся «неприкасаемыми» — список таких цветов настраивается в статическом массиве класса CPNGCompression. Неприкасаемые цвета введены для того, чтобы, например, не происходило смешение (при вычислении центра кластера) белого и черного с образованием серого.
Логично предположить, что визуальное качество классификации сильно зависит от коэффициентов в формуле (1), которые могут быть определены для ограниченного класса изображений, например для специальных картографических данных автором подобраны следующие значения: α=100, β=30, γ=59, ε=11.
На рисунке 3 представлен результат сжатия до 256 цветов исходной картинки с использованием разработанного алгоритма. Суммарное время открытия, сжатия и сохранения составило 4700 мсек. Размер выходного файла составляет 53 248 байт, так же как и для программы CQ (таблица 1). Как мы видим, рисунок 3 по сравнению с рисунком 2, имеет измененный цвет фона – визуально он стал ближе к желтому цвету, чем к серому. Этот дефект легко устраняется, если указать в качестве «неприкасаемых» белый и серый цвета – которые составляют фон.

Заключение


В статье рассмотрен один из простейших алгоритмов кластеризации используемый в задаче уменьшения количества цветов на изображении. Алгоритм сравнивается с известным решением – программой CQ. Дальнейшие улучшения алгоритма могут быть связаны с
  • изменением критерия завершения итераций,
  • модификацией функции расстояния между цветами,
  • переходом в другое цветовое пространство при кластеризации.


Дополнения к статье — по мотивам комментариев


В основной статье не приводится изображения, сжатого данным алгоритмом, с использованием «неприкасаемых цветов». Настроем неприкасаемые цвета следующим образом:
  1. // Настраиваем неприкасаемые цвета
  2. CPNGCompression.m_fixedColors = new int [2];
  3. CPNGCompression.m_fixedColors[0] = 0xFF969696;
  4. CPNGCompression.m_fixedColors[1] = 0xFFFFFFFF;
  5. // Сжимаем
  6. CPNGCompression.Compression(bufImage, true, 256);
* This source code was highlighted with Source Code Highlighter.


Тогда результатом сжатия рассматриваемым здесь алгоритмом будет изображение:
image
Рисунок 4 — Сжатое изображение с использованием двух неприкасаемых цветов

Размер данной картинки так же составляет 53 243 байт на диске.

Как сделать сравнение времени работы программы CQ с нужной точность я не знаю.
С использованием системных часов, с точностью +-2 секунды, сжатие до 256 цветов программой CQ выполняется за 34 секунды, что на порядок хуже, чем результат предлагаемого алгоритма.

Используемые источники


  1. Д. Мюррей, У. ван Райпер. Энциклопедия форматов графических файлов.
  2. Greg Roelofs, Иван Зенков, Dimok Busheff. PNG: Простое введение в особенности формата / Ссылка
  3. Color Quantizer: Программа позволяющая легко оптимизировать изображения для web / Ссылка
  4. Материал из википедии, тестовое изображение, GNU Free Documentation License / Ссылка
  5. А.И. Куликов, Т.Э. Овчинникова. Пространство CIE Luv, Алгоритмические основы современной компьютерной графики / Ссылка
  6. Обзор алгоритмов кластеризации данных / Ссылка
  7. Пакет PNGEncoder для работы с изображениями в формате PNG, Java / Ссылка
Tags:
Hubs:
Total votes 47: ↑46 and ↓1 +45
Views 13K
Comments Comments 38