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

Блочное кодирование усечения ( 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, имел (приблизительно) то же среднее значение и стандартное отклонение, что и соответствующий блок исходного изображения. Двухуровневое квантование блока — это то, где мы получаем сжатие, и оно выполняется следующим образом:

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

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

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

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

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

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

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

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

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

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

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

Внешние ссылки [ править ]

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

[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] Группа фрактального кодирования и анализа Ватерлоо

[1]

[2]

[3]

[4]

[5]

[6]

[7]