Блокирование кодирования усечения

Блочное кодирование усечения ( BTC ) — это метод сжатия изображений с потерями для изображений в оттенках серого . Он делит исходные изображения на блоки, а затем использует квантователь, чтобы уменьшить количество уровней серого в каждом блоке, сохраняя при этом то же среднее значение и стандартное отклонение . Это ранний предшественник популярной аппаратной технологии DXTC , хотя метод сжатия BTC был впервые адаптирован для цвета задолго до DXTC с использованием очень похожего подхода, называемого сжатием цветовых ячеек . ^[1] BTC также адаптирован для сжатия видео. ^[2]

BTC был впервые предложен профессорами Митчеллом и Делпом из Университета Пердью. ^[3] Другой вариант BTC — это блочное кодирование абсолютного момента или AMBTC , в котором вместо использования стандартного отклонения сохраняется первый абсолютный момент вместе со средним значением. AMBTC вычислительно проще, чем BTC, а также обычно приводит к более низкой среднеквадратической ошибке (MSE). AMBTC был предложен Максимо Лемой и Робертом Митчеллом. ^[4]

Использование подблоков размером 4×4 пикселя дает степень сжатия 4:1 при условии, что во время передачи или хранения используются 8-битные целочисленные значения. Блоки большего размера обеспечивают большее сжатие (значения a и b распространяются на большее количество пикселей), однако качество также снижается с увеличением размера блока из-за особенностей алгоритма.

Алгоритм BTC использовался для сжатия изображений марсохода Mars Pathfinder . ^[5]

Процедура сжатия

Пиксельное изображение делится на блоки размером обычно 4×4 пикселя. Для каждого блока рассчитываются среднее и стандартное отклонение значений пикселей; эта статистика обычно меняется от блока к блоку. Значения пикселей, выбранные для каждого реконструированного или нового блока, выбираются таким образом, чтобы каждый блок изображения, сжатого BTC, имел (приблизительно) то же среднее значение и стандартное отклонение, что и соответствующий блок исходного изображения. Двухуровневое квантование блока — это то, где мы получаем сжатие, и оно выполняется следующим образом:

${\displaystyle y(i,j)={\begin{cases}1,&x(i,j)>{\bar {x}}\\0,&x(i,j)\leq {\bar {x}}\end{cases}}}$

Здесь представлены пиксельные элементы исходного блока и элементы сжатого блока. На словах это можно объяснить так: если значение пикселя больше среднего, ему присваивается значение «1», в противном случае — «0». Значения, равные среднему значению, могут иметь либо «1», либо «0» в зависимости от предпочтений человека или организации, реализующей алгоритм. ${\displaystyle x(i,j)}$ ${\displaystyle y(i,j)}$

Этот 16-битный блок сохраняется или передается вместе со значениями среднего и стандартного отклонения. Реконструкция выполняется с двумя значениями «a» и «b», которые сохраняют среднее значение и стандартное отклонение. Значения «a» и «b» можно вычислить следующим образом:

${\displaystyle a={\bar {x}}-\sigma {\sqrt {\cfrac {q}{m-q}}}}$

${\displaystyle b={\bar {x}}+\sigma {\sqrt {\cfrac {m-q}{q}}}}$

Где стандартное отклонение, m — общее количество пикселей в блоке, а q — количество пикселей, превышающее среднее значение ( ) ${\displaystyle \sigma }$ ${\displaystyle {\bar {x}}}$

Чтобы восстановить изображение или создать его аппроксимацию, элементы, которым присвоено значение 0, заменяются значением «a», а элементы, которым присвоено значение 1, заменяются значением «b».

${\displaystyle x(i,j)={\begin{cases}a,&y(i,j)=0\\b,&y(i,j)=1\end{cases}}}$

Это демонстрирует, что алгоритм асимметричен, поскольку кодировщику приходится выполнять гораздо больше работы, чем декодеру. Это связано с тем, что декодер просто заменяет 1 и 0 расчетным значением, тогда как кодеру также необходимо вычислить среднее значение, стандартное отклонение и два значения, которые будут использоваться. ^[6]

Пример

Кодер

Возьмите блок 4×4 из изображения, в данном случае из изображения горного теста: ^[7]

${\displaystyle {\begin{matrix}245&239&249&239\\245&245&239&235\\245&245&245&245\\245&235&235&239\end{matrix}}}$

Как и с любым небольшим блоком изображения, с ним довольно скучно работать, поскольку все числа очень похожи. Такова природа сжатия с потерями и то, как оно может так хорошо работать для изображений. Теперь нам нужно вычислить два значения на основе этих данных: среднее и стандартное отклонение. Среднее значение можно вычислить как 241,875. Это простой расчет, который не требует дополнительных объяснений. Стандартное отклонение легко вычисляется и составляет 4,36. Отсюда значения «a» и «b» можно рассчитать с использованием предыдущих уравнений. Они получаются 236,935 и 245,718 соответственно. Последний расчет, который необходимо выполнить на стороне кодирования, — это установить матрицу для передачи в 1 и 0, чтобы каждый пиксель мог передаваться как один бит.

${\displaystyle {\begin{matrix}1&0&1&0\\1&1&0&0\\1&1&1&1\\1&0&0&0\end{matrix}}}$

Декодер

Теперь на стороне декодера все, что нам нужно сделать, это переназначить значения «a» и «b» пикселям 1 и 0. Это даст нам следующий блок:

${\displaystyle {\begin{matrix}245&236&245&236\\245&245&236&236\\245&245&245&245\\245&236&236&236\end{matrix}}}$

Как можно видеть, блок был реконструирован с двумя значениями «a» и «b» как целыми числами (поскольку изображения не определены для хранения чисел с плавающей запятой). При проработке теории это хороший момент для расчета среднего и стандартного отклонения реконструированного блока. Они должны равняться исходному среднему значению и стандартному отклонению. Не забывайте использовать целые числа, иначе возникнет большая ошибка квантования, поскольку ранее мы квантовали все до целых чисел в кодировщике.

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

• Сжатие цветовых ячеек (новая производная от блочного усечения кодирования)

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

1. Лиу, Д.-М.; Хуанг, Ю.; Рейнольдс, Н. (1990). «Новая система визуализации на базе микрокомпьютера с технологией C / Sup 3 /». IEEE TENCON'90: 1990 г. Конференция IEEE региона 10 по компьютерным и коммуникационным системам. Материалы конференций . п. 555. дои :10.1109/TENCON.1990.152671. ISBN 0-87942-556-3. S2CID  62015990.
2. Хили, Д.; Митчелл, О. (1981). «Сжатие полосы пропускания цифрового видео с использованием блочного усечения кодирования». Транзакции IEEE в области коммуникаций . 29 (12): 1809. Бибкод : 1981ITCom..29.1809H. дои : 10.1109/TCOM.1981.1094938.
3. Дельп, Э.; Митчелл, О. (1979). «Сжатие изображения с использованием блочного кодирования». Транзакции IEEE в области коммуникаций . 27 (9): 1335. Бибкод : 1979STIA...8011525D. дои : 10.1109/TCOM.1979.1094560.
4. Лема, М.; Митчелл, О. (1984). «Кодирование усечения блока абсолютного момента и его применение к цветным изображениям». Транзакции IEEE в области коммуникаций . 32 (10): 1148. doi :10.1109/TCOM.1984.1095973.
5. «Описание прибора камеры вездехода» . НАСА . Проверено 18 мая 2021 г.
6. Лейс, Дж. 2008, ELE4607 Advanced Digital Communications, Модуль 3: Кодирование изображений и видео. Слайды лекций, Университет Южного Квинсленда, 2008 г.
7. Группа фрактального кодирования и анализа Ватерлоо

Внешние ссылки

• СМИ, связанные с кодированием усечения блоков, на Викискладе?