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

Color Cell Compression — это алгоритм сжатия изображений с потерями , разработанный Кэмпбеллом и др. [1] [2] [3] в 1986 году, который можно считать ранним предшественником современных алгоритмов сжатия текстур, таких как S3 Texture Compression и Adaptive Scalable Texture Compression . Он тесно связан с Block Truncation Coding , [4] другим алгоритмом сжатия изображений с потерями, который предшествовал Color Cell Compression, в том смысле, что он использует доминирующую яркость блока пикселей для разделения указанных пикселей на два репрезентативных цвета. Основное различие между Block Truncation Coding и Color Cell Compression заключается в том, что первый был разработан для сжатия изображений в оттенках серого, а второй — для сжатия цветных изображений. Кроме того, Block Truncation Coding требует, чтобы для сжатия изображения вычислялось стандартное отклонение цветов пикселей в блоке, тогда как Color Cell Compression не использует стандартное отклонение. Однако оба алгоритма могут сжимать изображение до эффективных 2 бит на пиксель.

Крупный план мандрила, изображенного в разных цветах.
Исходное несжатое цветное изображение с глубиной цвета 24 бита на пиксель
Сжатое изображение стандартного тестового изображения Mandrill выше
Изображение, сжатое по алгоритму CCC, но использующее только 24-битное или 15-битное квантование цвета в сочетании с растровой картой яркости для 2,875 бит на пиксель (без палитры/таблицы поиска)
См. подпись
Реализация 256-элементной палитры/таблицы поиска алгоритма CCC с 2 битами на пиксель с палитрой, построенной с использованием кластеризации K-средних
См. подпись
Результат вывода стандартного тестового изображения Mandrill, сжатого с помощью алгоритма CCC со скоростью 2 бита на пиксель и палитрой из 256 элементов/таблицей поиска, сгенерированной с помощью простого алгоритма 15-битной цветовой гистограммы

Алгоритм

Сжатие

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

  1. Для каждой 8-битной тройки октетов RGB, содержащейся в каждом 24-битном цветовом значении входного изображения, яркость NTSC вычисляется по следующей формуле: [1] [2] [3] у {\textstyle у} у = 0.30 × г е г + 0,59 × г г е е н + 0.11 × б л ты е {\displaystyle y=0,30\times красный+0,59\times зеленый+0,11\times синий}
  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 бит. Этот шаг необязателен, и алгоритм может завершиться на этом этапе, если это необходимо, так как сжатые блоки на этом этапе имеют общий размер бит, который при делении на 16 дает 2,875 бит на пиксель. Если этот шаг выполняется, то 15-битные усеченные значения цвета могут быть использованы на следующем шаге для создания меньшей гистограммы. Кроме того, поскольку каждый 15-битный двоичный цветовой вектор предположительно хранится в 16-битном слове, то 16-й бит может быть использован для улучшения качества изображения путем указания того, какую из двух таблиц поиска следует использовать. [1] [2] [3] 16 + 2 × 15 = 46 {\textstyle 16+2\умножить на 15=46}
  7. Создается гистограмма всех 24-битных цветов в исходном 24-битном цветном изображении или усеченных 15-битных цветовых векторах. В наивной реализации гистограмма используется для выбора 256 наиболее часто используемых цветов, которые затем помещаются в массив из 256 записей, где каждая запись состоит из трех октетов 24-битного значения цвета на пиксель. Метод гистограммы выбора наиболее подходящих цветов для исходного 24-битного цветного изображения можно заменить алгоритмом класса векторного квантования, таким как алгоритм медианного разреза или кластеризация K-средних [ требуется ссылка ], что обычно дает лучшие результаты. [1] [2] [3]
  8. Последний шаг состоит из взятия текущего блока пикселей и определения того, какой цвет 24 бита на пиксель в таблице поиска с 256 записями наиболее точно соответствует двум репрезентативным цветам для каждого блока. Два 8-битных индекса, указывающие на цвета в таблице поиска, теперь добавляются к 16-битной битовой карте яркости. Это дает общий сжатый размер битов, который при делении на 16 дает 2 бита на пиксель. [1] [2] [3] 16 + 8 + 8 = 32 {\textstyle 16+8+8=32}

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

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


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

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

Apple Video (RPZA) и S3 Texture Compression используют тот же принцип кодирования блоков размером 4×4 пикселя на основе двух репрезентативных цветов. Они улучшают CCC, расширяя каждую запись в битовой карте яркости до двух битов, где два дополнительных значения представляют собой средневзвешенное значение: одну треть одного цвета и две трети другого. Чтобы обойти патент S3, была создана библиотека Super Simple Texture Compression ( S2TC ) для кодирования данных CCC в формате, совместимом с декодерами S3TC, и для повторной интерпретации S3TC как CCC с незначительной потерей качества.

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

Ссылки

  1. ^ abcdefghijk Кэмпбелл, Г.; Дефанти, ТА; Фредериксен, Дж.; Джойс, С.А.; Леске, Л.А. (1986). "Двухбитовое/пиксельное полноцветное кодирование". Труды 13-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '86 . стр. 215. doi :10.1145/15922.15910. ISBN 978-0-89791-196-2. S2CID  18392630.
  2. ^ abcdefghijk Pins, Markus (1991). "Расширения алгоритма сжатия цветных ячеек". Computer Animation '91 . pp.  241– 251. doi :10.1007/978-4-431-66890-9_17. ISBN 978-4-431-66892-3.
  3. ^ abcdefghijk Lamparter, Bernd Effelsberg, Wolfgang (июнь 2005 г.). "Расширенное сжатие цветных ячеек — эффективная схема сжатия программного видео". Мультимедиа: передовые телесервисы и архитектуры высокоскоростной связи. Конспект лекций по информатике. Том 868. С.  181– 190. doi :10.1007/3-540-58494-3_16. ISBN 978-3-540-58494-0.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )[ постоянная мертвая ссылка ‍ ]
  4. ^ Wennersten, P.; Ström, J. (2009). "Табличная альфа-компрессия" (PDF) . Computer Graphics Forum . 28 (2): 687. doi :10.1111/j.1467-8659.2009.01409.x. S2CID  7743813.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Color_Cell_Compression&oldid=1172314760"