Сжатие цветных ячеек - Color Cell Compression

Сжатие цветных ячеек это с потерями сжатие изображений алгоритм, разработанный Campbell et al.,^[1][2][3] в 1986 году, который можно считать ранним предшественником современных алгоритмов сжатия текстур, таких как Сжатие текстур S3 и Адаптивное масштабируемое сжатие текстур. Это тесно связано с Блочное усечение кодирования,^[4] другой алгоритм сжатия изображений с потерями, который предшествует сжатию цветных ячеек, поскольку он использует доминирующий яркость блока пиксели разделить указанные пиксели на два представительных цвета. Основное различие между кодированием с усечением блоков и сжатием цветных ячеек заключается в том, что первое было разработано для сжатия изображений в градациях серого, а второе - для сжатия цветных изображений. Кроме того, кодирование с усечением блоков требует, чтобы стандартное отклонение цветов пикселей в блоке вычисляются для сжатия изображения, тогда как при сжатии цветовых ячеек стандартное отклонение не используется. Однако оба алгоритма могут сжимать изображение до 2 бит на пиксель.

Исходное несжатое цветное изображение с разрешением 24 бита на пиксель

Сжатое изображение CCC, но с использованием только цветового квантования от 24 до 15 бит в сочетании с битовой картой яркости для 2,875 бит на пиксель (без палитры / справочной таблицы)

Палитра / справочная таблица с 256 входами, реализация алгоритма CCC при 2 битах на пиксель с палитрой, построенной с использованием кластеризации K-средних

Результат вывода стандартного тестового изображения Mandrill, сжатого с помощью алгоритма CCC со скоростью 2 бита на пиксель, с 256 входами палитры / справочной таблицы, созданной с использованием простого 15-битного алгоритма гистограммы

Алгоритм

Сжатие

Алгоритм сжатия цветных ячеек обрабатывает изображение за восемь шагов, хотя один из шагов (шаг №6) является необязательным. Здесь предполагается, что ввод - это изображение 24 бит / пиксель, как предполагалось в исходной статье журнала, хотя другие битовая глубина может быть использован.

1. Для каждой 8-битной тройки октетов RGB, содержащейся в каждом 24-битном значении цвета во входном изображении, NTSC яркость ${\textstyle y}$ вычисляется по следующей формуле:^[1][2][3]
   $${\displaystyle y=0.30\times red+0.59\times green+0.11\times blue}$$
2. Изображение теперь разделено на блоки 4 на 4 пикселя, и среднее арифметическое яркости каждого пикселя в блоке используется для выбора репрезентативного значения яркости.^[1][2][3]
3. Затем каждый блок пикселей делится на две группы. Одна группа состоит из пикселей в текущем блоке, где яркость каждого пикселя больше или равна репрезентативной яркости для текущего блока. Вторая группа пикселей состоит из пикселей в текущем блоке, где яркость каждого пикселя меньше репрезентативной яркости для текущего блока. Принадлежность пикселя в текущем блоке к определенной группе определяется двоичным значением «0» или «1» в другом, отдельном, 16-значном значении. битовая карта.^[1][2][3]
4. Теперь для каждого блока пикселей выбираются два репрезентативных 24-битных цвета с помощью двух арифметических средств. Первое среднее арифметическое - это среднее арифметическое всех пикселей, принадлежащих к первой группе пикселей, где яркость каждого пикселя равна «1» в битовой карте яркости. Второй 24-битный репрезентативный цвет выбирается аналогичным образом, путем взятия среднего арифметического всех 24-битных цветовых пикселей во второй группе, где каждый пиксель соответствует «0» в битовой карте яркости.^[1][2][3]
5. Битовая карта яркости сохраняется во временном местоположении, а затем два 24-битных репрезентативных цвета для текущего блока добавляются к битовой карте. На этом этапе изображение было сжато в битовую карту с 16 элементами и двумя добавленными 24-битными двоичными значениями. Общий размер сжатого блока теперь составляет 16 бит для битовой карты яркости и две 24-битные двоичные величины для каждого репрезентативного цвета, что дает общий размер 64 бита, который при делении на 16 (количество пикселей в блоке ), дает 4, т.е. 4 бита на пиксель.^[1][2][3]
6. Каждый сжатый блок пикселей модифицируется усечение каждый из двух 24-битных представительных цветов до 15 бит. Этот шаг является необязательным, и при желании алгоритм может завершиться на этом этапе, поскольку сжатые блоки на этом этапе имеют общий размер ${\textstyle 16+2\times 15=46}$ бит, который при делении на 16 дает 2,875 бит на пиксель. Если этот шаг выполняется, то 15-битные усеченные значения цвета можно использовать на следующем шаге для создания гистограммы меньшего размера. Кроме того, поскольку каждый 15-битный двоичный вектор цвета предположительно хранится в 16-битном слове, то 16-й бит можно использовать для улучшения качества изображения, указав, какую из двух таблиц поиска следует использовать.^[1][2][3]
7. Создается гистограмма всех 24-битных цветов в исходном 24-битном цветном изображении или усеченных 15-битных цветовых векторов. В наивной реализации гистограмма используется для выбора 256 из наиболее часто используемых цветов, которые затем помещаются в массив из 256 записей, где каждая запись состоит из трех октетов значения цвета 24 бита на пиксель. Метод гистограммы для выбора наиболее подходящих цветов для исходного цветного изображения с разрешением 24 бита на пиксель можно вместо этого заменить на средний разрез алгоритм, который обычно дает лучшие результаты.^[1][2][3]
8. Последний шаг состоит в том, чтобы взять текущий блок пикселей и определить, какой 24-битный цвет на пиксель в 256-записи Справочная таблица наиболее точно соответствуют двум представительным цветам для каждого блока. Два 8-битных индекса, указывающие на цвета в поисковой таблице, теперь добавляются к 16-битной битовой карте яркости. Это дает общий сжатый размер ${\textstyle 16+8+8=32}$ бит, который при делении на 16 дает 2 бита на пиксель.^[1][2][3]

Декомпрессия

Декомпрессия очень проста и понятна. Чтобы восстановить каждый сжатый 4-пиксельный блок на 4-пиксельный блок, для каждого блока обращаются к 16-битной битовой карте яркости. В зависимости от того, является ли элемент битовой карты 1 или 0, выбирается один из двух 8-битных индексов в таблице поиска, а затем разыменованный и извлекается соответствующее 24-битное значение цвета на пиксель.^[1][2][3]

Производительность и качество изображения

Несмотря на очень простой механизм, алгоритм дает удивительно хорошие результаты на фотографических изображениях.^[1][2][3] и его преимущество в том, что он очень быстро декодируется при ограниченном оборудовании. Хотя намного превзошел коэффициент сжатия более поздними методами кодирования с блочным преобразованием, такими как JPEG, он имеет преимущество очень простой распаковки и быстрого произвольного доступа к сжатому изображению.

Смотрите также

• Индексированный цвет
• Адаптивное масштабируемое сжатие текстур
• Сжатие текстур S3

Рекомендации

1. Кэмпбелл, G .; Defanti, T. A .; Frederiksen, J .; Joyce, S.A .; Леске, Л. А. (1986). «Двухпиксельное полноцветное кодирование». Материалы 13-й ежегодной конференции по компьютерной графике и интерактивным техникам - SIGGRAPH '86. п. 215. Дои:10.1145/15922.15910. ISBN  978-0-89791-196-2.
2. Булавки, Маркус (1991). Расширения алгоритма сжатия цветных ячеек. Компьютерная анимация '91. С. 241–251. Дои:10.1007/978-4-431-66890-9_17. ISBN  978-4-431-66892-3.
3. Лампартер, Бернд Эффельсберг, Вольфганг (июнь 2005 г.). Расширенное сжатие цветных ячеек: эффективная схема сжатия для программного видео. Мультимедиа: передовые телесервисы и архитектуры высокоскоростной связи. Конспект лекций по информатике. 868. С. 181–190. Дои:10.1007/3-540-58494-3_16. ISBN  978-3-540-58494-0.^{[постоянная мертвая ссылка ]}
4. Wennersten, P .; Стрем, Дж. (2009). "Альфа-сжатие на основе таблиц" (PDF ). Форум компьютерной графики. 28 (2): 687. Дои:10.1111 / j.1467-8659.2009.01409.x.