8 февраля 2011 в 20:42

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

Аннотация

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

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

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.

Тогда результатом сжатия рассматриваемым здесь алгоритмом будет изображение:

Рисунок 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 / Ссылка