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

Аннотация


В данной статье читателю предлагается опыт разработки алгоритма сжатия изображения, хранящегося в формате 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 / Ссылка
Метки:
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 38
  • 0
    Прелесть формата png во многом в том, что он визуально (для глаз) не искажает сжатием картинку. На рисунке 3 я вижу разницу.
    • +4
      Зачем png ограничивать 256-ю цветами? PNG хранит графику в сжатом виде, сжатие производится без потерь для изображения. Это основное его преимущество как перед gif так и jpg ну и альфа-канал
      • +1
        Согласен, разница заметна, серый, белый и светло желтый смешались в один кластер.
        Однако что бы этого избежать в статье предлагается использовать «неприкасаемые цвета».
        Рисунок 3 сделан без «неприкасаемых цветов.
        Если поставить в качестве неприкасаемых цветов белый и серый — то будет просто замечательно.
        Я это намеренно не привел в статье чтобы пробудить интерес.
        Завтра обязательно приведу рисунок который обрабатывается данным алгоритмом без этого недостатка — замеченного вами.
        • +1
          Здесь не предлагается ограничить 256 цветами — речь о том что существует возможность внести потери, незаметные для глаза, на уровне цветов. 256 цветов — это крайность.
          Зачем? — чтобы снизить размер файла, даже если он мал, пользователи мобильных приложений будут благодарны, особенно при работе с картами.
          • –2
            Для сжатия с потерями есть другие форматы, специально для этого созданные. Суть PNG в беспотерьности, если я сохраняю изображение в пнг — я знаю, что восстановлю его до пикселя, а если программисты начнут внезапно реализовывать алгоритмы уменьшения цветов в энкодеры PNG, то эта уверенность улетучится и он станет ничем не лучше GIF или JPG.
            • +1
              Ну помимо отсутствия потерь — есть еще важная штука — альфа канал, который как мне известно полностью (все градации) поддерживается только этим форматом. В принципе из за его поддержки все и началось. И прошу заметить — здесь сжатие совсем другого уровня, оно, я бы сказал, очень нежное по отношению к картинке: без всяких квадратов, муаров, шума и прочего…
            • 0
              Я не спорю, оптимизация алгоритмов — это прекрасно, но уж очень зыбкая черта это ваше «незаметные для глаз». Для чьих глаз? При каком разрешении на каком расстоянии? :)
              • +3
                Делалось для мобильников, а вопросы ваши верные. Главный недостаток алгоритма — отсутствие контроля качества кластеризации — что получилось — то и получилось. И только для ограниченного класса изображений удается добиться качества.
                • 0
                  Андрей, вы большой молодец!
          • +3
            А я вообще не вижу рисунка 3.
            • 0
              Уточните — он что не грузится?
              • 0
                Форматирование не позволяет их увидеть. Разместите друг под другом.
                Вот прямые ссылки на все рисунки:
                Рисунок 1 — Тестовое изображение формата PNG для исследований, разрешение — 800x600
                habreffect.ru/files/e0c/6ce730c50/PNG_transparency_demonstration_2.png

                Рисунок 2 – Сжатое до 256 цветов изображение с использованием программы Color Quantizer
                habreffect.ru/files/7ca/ae107a6a2/256.png

                Рисунок 3 — Сжатое до 256 цветов изображение с использованием разработанного алгоритма
                habreffect.ru/files/9d6/f5fc67d86/256MY.png
                • 0
                  Спасибо, замечание учту. Все же, на будущее, мне неясно — почему не видно то?
                  Это из-за различных разрешений мониторов?
                  • 0
                    Мне вот тоже неясно, почему у вас видно, а у меня — нет :-)
                    • –1
                      Из-за различий расчета размеров страниц браузерами.
                      • –1
                        Я идиот, хотел же ссылку вставить.
                        • 0
                          Какой кошмар получился у меня, сейчас же поправлю!
                        • 0
                          Поправил, теперь должно быть нормально.
              • 0
                В наши дни практическая польза качественной квантизации палитры (да и то сомнительная) — чтобы гиф-анимации делать. Приведение к 256 цветам в PNG кажется натянутым. Но с теоретической точки зрения работа, безусловно, интересна :-)
                • 0
                  Гиф-анимация — точно, там это полезнее гораздо, надо попробовать эту тему.
                  Спасибо.
                • +1
                  Было бы не только уменьшение цветов, но и dithering — разницу было бы заметить очень сложно.
                  • 0
                    Я погуглил: «Дитеринг (Dithering) эффект при котором изображение строится из точек без их размывания, и чем меньше цветов при этом используется тем они более заметны.» Видимо вы имеете ввиду атиДитеринг, не знаком с этой темой, расскажите пожалуйста.
                    • +1
                      Я имею в виду именно dithering. Достаточно взять Photoshop или Gimp какой-нибудь и попробовать в них уменьшить количество цветов, чтобы посмотреть, какие возможности у них есть.

                      Вот, например, Photoshop, 256 цветов, стратегия уменьшения цветов Perceptual, no dithering, 46234 bytes:


                      Photoshop, 256 цветов, стратегия уменьшения цветов Perceptual, diffusion dithering, 58427 bytes:


                      Photoshop, 256 цветов, стратегия уменьшения цветов Perceptual, noise dithering, 125594 bytes:


                      Положим, noise dithering делает слишком большую картинку, если уж это и важно; но даже diffusion dithering при отличии в пять килобайт даёт видимо лучший результат, чем без dithering-а вообще.
                      • 0
                        Ага, понятно, надо бы почитать про эти алгоритмы.
                        • 0
                          Ищу про Дитеринг, возможно у вас есть ссылка?
                  • +1
                    Из двух картинок, на которых цвета сжаты до 256, выглядит лучше первая, конечно.
                    • +1
                      Рисунок 3 — получился такой потому-что смешались некоторые светлые цвета, этого можно избежать используя «неприкасаемые цвета» — завтра будет еще одна картинка, визуально неотличимая от рисунка 2.
                      • 0
                        Добавлен рисунок №4 и некоторые дополнения по результатам обсуждения.
                      • 0
                        Хороший обзор. Спасибо.
                        • +1
                          Программа CQ обладает существенным недостатком – крайне медленная скорость работы, что делает затруднительным ее использование в режиме реального времени, например, при передаче данных геоинформационных систем. Оказывается, что время, которое требуется для сжатия изображения, в разы превосходит время необходимое для передачи исходного – несжатого изображения.
                          Ваш алгоритм потратил 4.7 секунды, чтобы сэкономить около 130 кБ. То есть при скорости соединения выше 28 кБ/с было бы быстрее передать необработанную картинку.
                          И хотелось бы увидеть конкретные цифры при сравнении с другими методами (тем же CQ), потому что «крайне медленная скорость» — понятие крайне расплывчатое.
                          • +3
                            а кеширование пережатой картинки вы не учитываете?
                            а если раздать ее тысячам клиентов?
                            • 0
                              А использование авторского алгоритма для компрессии ресурсов (есть необходимость в альфе) standalone desktop приложения с большой аудиторией сэкономит. Верно? :)
                              • 0
                                Да. Для настольного приложения — я думаю это так же может быть актуально.
                              • +1
                                Я добавил в конце статьи сравнение по времени работы с программой CQ:
                                4.7 секунды против 34 у CQ.
                              • 0
                                Всегда использовал для этой цели Gimp с переводом цвета изображения в «Indexed». Там можно задать размер палитры.

                                Но такой ручной способ заметно влияет на размер только очень больших изображений, типа скриншотов.
                                • 0
                                  Я как-то писал свой беспотерьный компрессор полноцветных изображений.
                                  По большинству тестов он значительно выигрывает у PNG.
                                  В данном случае приведенную для тестов картинку размером 184 320 байт мой компрессор сжимает до 86 791 байт за 0,26 сек. Тут правда стоит учесть, что реализация на VisualBasic.
                                  И не стоит забывать, что у меня совсем без потерь. Т.е. изображение восстанавливается с точностью до бита.
                                  • 0
                                    Для меня очень интересная тема по сжатию изображений. Как только накоплю карму, обязательно напишу статью о своем компрессоре.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.