Блочное усечение кодирования - Block Truncation Coding

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

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

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

Алгоритм BTC использовался для сжатия Марс-следопыт изображения ровера.^[5]

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

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

${displaystyle y(i,j)={egin{cases}1,&x(i,j)>{ar {x}}�,&x(i,j)leq {ar {x}}end{cases}}}$

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

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

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

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

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

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

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

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

Пример

Кодировщик

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

${displaystyle {egin{matrix}245&239&249&239245&245&239&235245&245&245&245245&235&235&239end{matrix}}}$

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

${displaystyle {egin{matrix}1&0&1&01&1&0&01&1&1&11&0&0&0end{matrix}}}$

Декодер

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

${displaystyle {egin{matrix}245&236&245&236245&245&236&236245&245&245&245245&236&236&236end{matrix}}}$

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

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

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

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

1. Liou, D. -M .; Huang, Y .; Рейнольдс, Н. (1990). «Новая система визуализации на базе микрокомпьютера с техникой C / sup 3 /». IEEE TENCON'90: 1990 IEEE Region 10 Conference on Computer and Communication Systems. Материалы конференций. п. 555. Дои:10.1109 / TENCON.1990.152671. ISBN  0-87942-556-3.
2. Healy, D .; Митчелл, О. (1981). «Сжатие полосы пропускания цифрового видео с использованием блочного кодирования с усечением». Транзакции IEEE по коммуникациям. 29 (12): 1809. Bibcode:1981ITCom..29.1809H. Дои:10.1109 / TCOM.1981.1094938.
3. Delp, E .; Митчелл, О. (1979). «Сжатие изображений с использованием блочного кодирования с усечением». Транзакции IEEE по коммуникациям. 27 (9): 1335. Bibcode:1979STIA ... 8011525D. Дои:10.1109 / TCOM.1979.1094560.
4. Лема, М .; Митчелл, О. (1984). «Абсолютное кодирование усечения блока моментов и его применение к цветным изображениям». Транзакции IEEE по коммуникациям. 32 (10): 1148. Дои:10.1109 / TCOM.1984.1095973.
5. "Описание инструмента камеры Rover". НАСА. Получено 2011-11-09.
6. Leis, J, 2008, ELE4607 Advanced Digital Communications, Module 3: Image & Video Coding. Слайды лекций, Университет Южного Квинсленда, 2008 г.
7. Группа фрактального кодирования и анализа Ватерлоо

внешняя ссылка

• СМИ, связанные с Блочное усечение кодирования в Wikimedia Commons