Сжатие изображений без потери качества методом квантования цветов

Алгоритмы построения палитры и распределение погрешности

Центральная теоретическая часть работы посвящена методам кластеризации трехмерного цветового пространства RGB. Тебе нужно разобрать устройство классических алгоритмов, распределяющих миллионы исходных оттенков по ограниченной таблице из 256 или менее записей.

• Метод медианного сечения (Median Cut) Пола Хекберта 1982 года, где цветовой куб последовательно делится плоскостями по медиане наибольшего цветового диапазона на равные подкубы.
• Алгоритм октодерева (Octree), в котором пиксели встраиваются в восьмеричное дерево глубиной до восьми уровней, а затем нижние листовые узлы сворачиваются для получения целевого числа кластеров.
• Метод квантования Сяолиня Ву (Xiaolin Wu), оптимизирующий дисперсию цвета внутри каждого выделенного прямоугольного параллелепипеда.
• Алгоритмы диффузии ошибки, в первую очередь фильтр Флойда — Стейнберга, передающий накопленную цветовую погрешность соседним необработанным пикселям для устранения видимых ступенчатых переходов (бандинга).

Механизм индексации и энтропийного сжатия в формате PNG

Полноцветный PNG-24 хранит по три байта на каждый пиксел без учета альфа-канала. После квантования изображение переходит в индексированный формат PNG-8, где каждый пиксел кодируется одним байтом — указателем на индекс в палитре (PLTE chunk). Для теоретического обоснования тебе нужно подробно описать конвейер сжатия PNG, состоящий из двух независимых шагов.

Сначала применяется построчная дельта-фильтрация (типы Sub, Up, Average, Paeth), которая трансформирует байты соседних пикселей в разностные значения. Затем поток байтов сжимается алгоритмом Deflate, объединяющим поиск повторяющихся подстрок через LZ77 и статистическое кодирование Хаффмана. Важно показать математическую взаимосвязь. Уменьшение разнообразия байтовых последовательностей после квантования резко увеличивает длину совпадений в скользящем окне LZ77, что дает многократный выигрыш в размере итогового файла.

Метрики визуального сходства и экспериментальный стенд

Курсовая требует экспериментальной главы с замерами на реальных файлах. Оценивать результат только «на глаз» нельзя. Для объективного доказательства сохранения качества необходимо рассчитать численные метрики искажений между исходным 24-битным оригиналом и квантованным 8-битным снимком.

• Пиковое отношение сигнала к шуму (PSNR), вычисляемое через среднеквадратичную ошибку (MSE) по всем цветовым каналам.
• Индекс структурного сходства (SSIM), который сопоставляет локальные контрасты, яркости и структуры фрагментов картинки, точнее отражая восприятие человеческого глаза.
• Цветовое различие по формуле Delta E 2000 в перцептивно равномерном пространстве CIELAB, показывающее, видит ли средний наблюдатель подмену оттенка.
• Коэффициент сжатия в процентах и абсолютных байтах по сравнению со стандартным сжатием PNG-24 с максимальным уровнем компрессии Deflate.

Что проверяет преподаватель в этой теме

Комиссия смотрит на строгую алгоритмическую грамотность и аккуратность эксперимента. Преподаватель обратит внимание на следующие детали:

• Понимание границы между сжатием с потерями и без потерь применительно к этапам обработки растра.
• Корректность программного кода квантования, отсутствие готовых внешних компрессоров там, где требовалось написать или разобрать алгоритм самостоятельно.
• Обоснованность тестовой выборки, в которую должны войти иллюстрации с разной энтропией — пейзажи с плавными градиентами, скриншоты интерфейсов с резкими границами и синтетические текстуры.
• Наличие графиков зависимости метрик PSNR и SSIM от размера результирующей палитры (например, при 16, 32, 64, 128 и 256 цветах).

Где брать тестовые данные и литературу

Случайные картинки из поисковика обесценивают научную сторону работы. Используй признанные в академической среде датасеты для тестирования алгоритмов компьютерного зрения:

• Набор Kodak Lossless True Color Image Suite (24 несжатых изображения формата PNG/TIFF с богатой палитрой и мелкой детализацией).
• Архив тестовых изображений USC-SIPI Image Database Университета Южной Калифорнии (классические снимки Mandrill, Peppers, Lena).
• Официальная спецификация W3C Portable Network Graphics (PNG) Specification (Second Edition) и стандарт RFC 2083 для точного описания структуры чанков и фильтров.
• Статьи Paul Heckbert «Color Image Quantization for Frame Buffer Display» (1982) и Xiaolin Wu «Color Quantization by Dynamic Programming and Principal Analysis» (1991).