Сжатие цветовых ячеек

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

Крупный план мандрила с изображением разных цветов. — Исходное несжатое цветное изображение с глубиной цвета 24 бита на пиксель.

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

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

Алгоритм [ править ]

Сжатие [ править ]

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

Для каждой тройки 8-битных октетов RGB, содержащейся в каждом 24-битном значении цвета входного изображения, NTSC яркость ${\textstyle y}$ рассчитывается по следующей формуле: ^[1]^[2]^[3] $y=0.30\times red+0.59\times green+0.11\times blue$
Изображение теперь подразделяется на блоки размером 4 на 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 бит. Этот шаг не является обязательным, и при желании алгоритм может завершиться на этом этапе, поскольку общий размер сжатых блоков на этом этапе составляет ${\textstyle 16+2\times 15=46}$ бит, что при делении на 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-битному растровому изображению яркости. Это дает общий сжатый размер ${\textstyle 16+8+8=32}$ бит, которое при делении на 16 дает 2 бита на пиксель. ^[1]^[2]^[3]

Декомпрессия [ править ]

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

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

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

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

См. также [ править ]

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Кэмпбелл, Г.; Дефанти, штат Калифорния; Фредериксен, Дж.; Джойс, ЮАР; Леске, Луизиана (1986). «Двухбитное/пиксельное полноцветное кодирование». Материалы 13-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '86 . п. 215. дои : 10.1145/15922.15910 . ISBN 978-0-89791-196-2 . S2CID 18392630 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Пинс, Маркус (1991). «Расширения алгоритма сжатия цветовых ячеек». Компьютерная анимация '91 . стр. 241–251. дои : 10.1007/978-4-431-66890-9_17 . ISBN 978-4-431-66892-3 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Лампартер, Бернд Эффельсберг, Вольфганг (июнь 2005 г.). «Расширенное сжатие цветовых ячеек — эффективная схема сжатия программного видео». Мультимедиа: передовые телеуслуги и архитектуры высокоскоростной связи . Конспекты лекций по информатике. Том. 868. стр. 181–190. дои : 10.1007/3-540-58494-3_16 . ISBN 978-3-540-58494-0 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) ^{[ постоянная мертвая ссылка ]}
^ Веннерстен, П.; Стрём, Дж. (2009). «Альфа-сжатие на основе таблиц» (PDF) . Форум компьютерной графики . 28 (2): 687. doi : 10.1111/j.1467-8659.2009.01409.x . S2CID 7743813 .

[ccc-1] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Кэмпбелл, Г.; Дефанти, штат Калифорния; Фредериксен, Дж.; Джойс, ЮАР; Леске, Луизиана (1986). «Двухбитное/пиксельное полноцветное кодирование». Материалы 13-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '86 . п. 215. дои : 10.1145/15922.15910 . ISBN 978-0-89791-196-2 . S2CID 18392630 .

[ccc2-2] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Пинс, Маркус (1991). «Расширения алгоритма сжатия цветовых ячеек». Компьютерная анимация '91 . стр. 241–251. дои : 10.1007/978-4-431-66890-9_17 . ISBN 978-4-431-66892-3 .

[ccc3-3] Jump up to: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Лампартер, Бернд Эффельсберг, Вольфганг (июнь 2005 г.). «Расширенное сжатие цветовых ячеек — эффективная схема сжатия программного видео». Мультимедиа: передовые телеуслуги и архитектуры высокоскоростной связи . Конспекты лекций по информатике. Том. 868. стр. 181–190. дои : 10.1007/3-540-58494-3_16 . ISBN 978-3-540-58494-0 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) ^{[ постоянная мертвая ссылка ]}

[btc-4] Веннерстен, П.; Стрём, Дж. (2009). «Альфа-сжатие на основе таблиц» (PDF) . Форум компьютерной графики . 28 (2): 687. doi : 10.1111/j.1467-8659.2009.01409.x . S2CID 7743813 .

[1]

[2]

[3]

[4]