Сжатие цветных ячеек - это алгоритм сжатия изображений с потерями , разработанный Кэмпбеллом и др. [1] [2] [3] в 1986 году, который можно считать ранним предшественником современных алгоритмов сжатия текстур, таких как S3 Texture Compression и Adaptive Scalable Texture. Сжатие . Это тесно связанно с блоком кодирования Усечения , [4] другой алгоритм сжатия с потерями изображения, который предшествует цвет ячейки сжатия, в том , что он использует доминирующие яркости из блока пикселейразделить указанные пиксели на два представительных цвета. Основное различие между блочным кодированием усечения и сжатием цветных ячеек состоит в том, что первое было разработано для сжатия изображений в градациях серого, а второе - для сжатия цветных изображений. Кроме того, кодирование с усечением блоков требует, чтобы стандартное отклонение цветов пикселей в блоке было вычислено для сжатия изображения, тогда как сжатие цветовых ячеек не использует стандартное отклонение. Однако оба алгоритма могут сжимать изображение до 2 бит на пиксель.
Алгоритм
Сжатие
Алгоритм сжатия цветных ячеек обрабатывает изображение за восемь шагов, хотя один из шагов (шаг №6) является необязательным. Здесь предполагается, что входными данными является изображение 24 бит / пиксель, как предполагалось в исходной статье журнала, хотя могут использоваться другие значения битовой глубины .
- Для каждой 8-битной тройки октетов RGB, содержащейся в каждом 24-битном значении цвета во входном изображении, яркость NTSCвычисляется по следующей формуле: [1] [2] [3]
- Изображение теперь разделено на блоки по 4 пикселя, и среднее арифметическое значение яркости каждого пикселя в блоке используется для выбора репрезентативного значения яркости. [1] [2] [3]
- Затем каждый блок пикселей делится на две группы. Одна группа состоит из пикселей в текущем блоке, где яркость каждого пикселя больше или равна репрезентативной яркости для текущего блока. Вторая группа пикселей состоит из пикселей в текущем блоке, где яркость каждого пикселя меньше репрезентативной яркости для текущего блока. Принадлежит ли пиксель в текущем блоке определенной группе, определяется двоичным значением «0» или «1» в другом отдельном битовом массиве с 16 элементами . [1] [2] [3]
- Теперь для каждого блока пикселей выбираются два репрезентативных 24-битных цвета с помощью двух арифметических средств. Первое среднее арифметическое - это среднее арифметическое всех пикселей, принадлежащих первой группе пикселей, где яркость каждого пикселя равна «1» в битовой карте яркости. Второй 24-битный репрезентативный цвет выбирается аналогичным образом путем взятия среднего арифметического всех 24-битных цветовых пикселей во второй группе, где каждый пиксель соответствует «0» в битовой карте яркости. [1] [2] [3]
- Битовая карта яркости сохраняется во временном месте, а затем два 24-битных репрезентативных цвета для текущего блока добавляются к битовой карте. На этом этапе изображение было сжато в битовую карту с 16 элементами и двумя добавленными 24-битными двоичными значениями. Общий размер сжатого блока теперь составляет 16 бит для битовой карты яркости и две 24-битные двоичные величины для каждого репрезентативного цвета, что дает общий размер 64 бита, который при делении на 16 (количество пикселей в блоке ), дает 4, т. е. 4 бита на пиксель. [1] [2] [3]
- Каждый сжатый блок пикселей модифицируется путем усечения каждого из двух 24-битных репрезентативных цветов до 15 бит. Этот шаг является необязательным, и при желании алгоритм может завершиться на этом этапе, поскольку сжатые блоки на этом этапе имеют общий размербит, который при делении на 16 дает 2,875 бит на пиксель. Если этот шаг выполняется, то 15-битные усеченные значения цвета можно использовать на следующем шаге для создания гистограммы меньшего размера. Кроме того, поскольку каждый 15-битный двоичный вектор цвета предположительно хранится в 16-битном слове, то 16-й бит можно использовать для улучшения качества изображения, указав, какую из двух таблиц поиска следует использовать. [1] [2] [3]
- Создается гистограмма всех 24-битных цветов в исходном 24-битном цветном изображении или усеченных 15-битных цветовых векторов. В наивной реализации гистограмма используется для выбора 256 из наиболее часто используемых цветов, которые затем помещаются в массив из 256 записей, где каждая запись состоит из трех октетов значения цвета 24 бита на пиксель. Метод гистограммы для выбора наиболее подходящих цветов для исходного цветного изображения с разрешением 24 бита на пиксель может быть заменен алгоритмом класса векторного квантования, таким как алгоритм медианного отсечения или кластеризация K-средних [ необходима ссылка ], что обычно дает лучшие результаты. [1] [2] [3]
- Последний шаг состоит в том, чтобы взять текущий блок пикселей и определить, какой цвет 24 бита на пиксель в таблице поиска с 256 элементами наиболее точно соответствует двум репрезентативным цветам для каждого блока. Два 8-битных индекса, указывающих на цвета в поисковой таблице, теперь добавляются к 16-битной битовой карте яркости. Это дает общий сжатый размербит, который при делении на 16 дает 2 бита на пиксель. [1] [2] [3]
- Для каждой 8-битной тройки октетов RGB, содержащейся в каждом 24-битном значении цвета во входном изображении, яркость NTSCвычисляется по следующей формуле: [1] [2] [3]
Декомпрессия
Декомпрессия очень проста и понятна. Чтобы восстановить каждый сжатый 4-пиксельный блок на 4-пиксельный блок, для каждого блока обращаются к 16-битной битовой карте яркости. В зависимости от того, является ли элемент растрового изображения 1 или 0, выбирается один из двух 8-битных индексов в поисковой таблице, затем разыменовывается и извлекается соответствующее значение цвета 24 бита на пиксель. [1] [2] [3]
Производительность и качество изображения
Несмотря на очень простой механизм, алгоритм дает удивительно хорошие результаты на фотографических изображениях, [1] [2] [3], и его преимущество состоит в том, что он очень быстро декодируется с ограниченным оборудованием. Хотя он намного превосходит по степени сжатия более поздние методы кодирования с блочным преобразованием, такие как JPEG , он имеет преимущество очень простой декомпрессии и быстрого произвольного доступа к сжатому изображению.
Смотрите также
- Индексированный цвет
- Адаптивное масштабируемое сжатие текстур
- Сжатие текстур S3
Рекомендации
- ^ a b c d e f g h i j k Кэмпбелл, G .; Defanti, TA; Frederiksen, J .; Joyce, SA; Леске, Л.А. (1986). «Двухпиксельное полноцветное кодирование». Материалы 13-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '86 . п. 215. DOI : 10,1145 / 15922,15910 . ISBN 978-0-89791-196-2.
- ^ Б с д е е г ч я J K Булавки, Маркус (1991). Расширения алгоритма сжатия цветных ячеек . Компьютерная анимация 91 года . С. 241–251. DOI : 10.1007 / 978-4-431-66890-9_17 . ISBN 978-4-431-66892-3.
- ^ Б с д е е г ч я J K Лампартер, Бернд Эффельсберг, Вольфганг (июнь 2005 г.). Расширенное сжатие цветных ячеек: эффективная схема сжатия для программного видео . Мультимедиа: передовые телесервисы и архитектуры высокоскоростной связи . Конспект лекций по информатике. 868 . С. 181–190. DOI : 10.1007 / 3-540-58494-3_16 . ISBN 978-3-540-58494-0.CS1 maint: несколько имен: список авторов ( ссылка )[ постоянная мертвая ссылка ]
- ^ Wennersten, P .; Стрем, Дж. (2009). «Табличное альфа-сжатие» ( PDF ) . Форум компьютерной графики . 28 (2): 687. DOI : 10.1111 / j.1467-8659.2009.01409.x .