Кодирование с усечением блока

Кодирование с блочным усечением ( BTC ) — это тип метода сжатия изображений с потерями для изображений в оттенках серого . Он делит исходные изображения на блоки, а затем использует квантизатор для уменьшения количества уровней серого в каждом блоке, сохраняя при этом то же среднее значение и стандартное отклонение . Это ранний предшественник популярной аппаратной техники DXTC , хотя метод сжатия BTC был впервые адаптирован для цвета задолго до DXTC с использованием очень похожего подхода, называемого Color Cell Compression . ^[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 имел (приблизительно) то же среднее значение и стандартное отклонение, что и соответствующий блок исходного изображения. Двухуровневое квантование на блоке — это то, где мы получаем сжатие, и выполняется следующим образом:

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

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

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

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

$b={\bar {x}}+\sigma {\sqrt {\cfrac {mq}{q}}}$

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

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

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

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

Пример

Кодировщик

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

${\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 соответственно. Последнее вычисление, которое необходимо выполнить на стороне кодирования, — это настроить матрицу на передачу единиц и нулей, чтобы каждый пиксель мог передаваться как один бит.

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

Декодер

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

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

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

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

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

Ссылки

^ Liou, D. -M.; Huang, Y.; Reynolds, N. (1990). "Новая система визуализации на основе микрокомпьютера с технологией C/sup 3/". IEEE TENCON'90: 1990 IEEE Region 10 Conference on Computer and Communication Systems. Труды конференции . стр. 555. doi :10.1109/TENCON.1990.152671. ISBN 0-87942-556-3. S2CID 62015990.
^ Хили, Д.; Митчелл, О. (1981). «Сжатие полосы пропускания цифрового видео с использованием кодирования с усечением блоков». Труды IEEE по коммуникациям . 29 (12): 1809. Bibcode : 1981ITCom..29.1809H. doi : 10.1109/TCOM.1981.1094938.
^ Delp, E.; Mitchell, O. (1979). «Сжатие изображений с использованием блочного усечения кодирования». IEEE Transactions on Communications . 27 (9): 1335. Bibcode : 1979STIA...8011525D. doi : 10.1109/TCOM.1979.1094560.
^ Лема, М.; Митчелл, О. (1984). «Кодирование с блочным усечением абсолютного момента и его применение к цветным изображениям». Труды IEEE по коммуникациям . 32 (10): 1148. doi :10.1109/TCOM.1984.1095973.
^ "Описание инструмента камеры марсохода". NASA . Получено 2021-05-18 .
^ Leis, J 2008, ELE4607 Advance Digital Communications, Модуль 3: Кодирование изображений и видео. Слайды лекций, Университет Южного Квинсленда, 2008.
^ Группа фрактального кодирования и анализа Ватерлоо

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

Медиафайлы, связанные с кодированием блочного усечения на Wikimedia Commons

[1] Liou, D. -M.; Huang, Y.; Reynolds, N. (1990). "Новая система визуализации на основе микрокомпьютера с технологией C/sup 3/". IEEE TENCON'90: 1990 IEEE Region 10 Conference on Computer and Communication Systems. Труды конференции . стр. 555. doi :10.1109/TENCON.1990.152671. ISBN 0-87942-556-3. S2CID 62015990.

[2] Хили, Д.; Митчелл, О. (1981). «Сжатие полосы пропускания цифрового видео с использованием кодирования с усечением блоков». Труды IEEE по коммуникациям . 29 (12): 1809. Bibcode : 1981ITCom..29.1809H. doi : 10.1109/TCOM.1981.1094938.

[3] Delp, E.; Mitchell, O. (1979). «Сжатие изображений с использованием блочного усечения кодирования». IEEE Transactions on Communications . 27 (9): 1335. Bibcode : 1979STIA...8011525D. doi : 10.1109/TCOM.1979.1094560.

[4] Лема, М.; Митчелл, О. (1984). «Кодирование с блочным усечением абсолютного момента и его применение к цветным изображениям». Труды IEEE по коммуникациям . 32 (10): 1148. doi :10.1109/TCOM.1984.1095973.

[5] "Описание инструмента камеры марсохода". NASA . Получено 2021-05-18 .

[6] Leis, J 2008, ELE4607 Advance Digital Communications, Модуль 3: Кодирование изображений и видео. Слайды лекций, Университет Южного Квинсленда, 2008.

[7] Группа фрактального кодирования и анализа Ватерлоо