Тема 10. Методы кодирования физических сигналов в компьютерных сетях

.097887 -.278653.416700 -.490862.489771 -.413593.274008 -.092414

.191618 -.462282.461366 -.189409 -.193822.463187 -.460440.187195

.277992 -.490246.096324.416700 -.414486 -.100228.491013 -.274673

.353694 -.353131 -.354256.352567.354819 -.352001 -.355378.351435

.414818 -.097106 -.490246 -.278653.276667.490710.099448 -.414486

.461978.191618 -.190882 -.461673 -.462282 -.192353.190145.461366

.490393.415818.277992.097887 -.097106 -.277329 -.415375 -.490246

.353553.353553.353553.353553.353553.353553.353553.353553

Или же, в матричной форме,

RES = DCT ^T*IMG * DCT,

где DCT - матрица базисных (косинусных) коэффициентов для преобразования размером 8х8, имеет конкретный вид:

Обратное восстановление матрицы пикселей исходного изображения IMG по его преобразованию DCT в матричной форме имеет очевидный вид:

IMG = DCT*RES * DCT ^T

Итак, в результате применения к блоку изображения размером 8х8 пикселов дискретного косинусного преобразования получим двумерный спектр, также имеющий размер 8х8 отсчетов. Иными словами, 64 числа, представляющие отсчеты изображения, превратятся в 64 числа, представляющие отсчеты его DCT -спектра.

А теперь напомним, что такое спектр сигнала. Это – величины коэффициентов, с которыми соответствующие спектральные составляющие входят в сумму, которая в результате и дает этот сигнал. Отдельные спектральные составляющие, на которые раскладывается сигнал, часто называют базисными функциями. Для преобразования Фурье базисными функциями являются синусы и косинусы разных частот.

Для 8х8 DCT система базисных функций задается формулой

,

Сами базисные функции выглядят подобно приведенным на рис. 15.2. для одномерного DCT преобразования для n=4, 8, 16. Рисунок дает нам понятие о качественных характеристиках преобразования или разложения входного сигнала на спектральные составляющие. По характеру поведения базисных функций видно, что фунции с наименьшими номерами выделяют из спектра сигнала низкочастотные составляющие, а с ростом номера функции она выделяет все более высокочастотные компоненты сигнала.

(ii) Рис. 15.2

На рис. 15.3 показано поведение базисных функций двумерного DCT для n=4. Нетрудно заметить, что сечение каждого квадратика по горизонтали совпадает с поведением одномерной DCT для n=4 для ситуации рис.15.2

(iii) Рис. 15.3

Самая низкочастотная базисная функция, соответствующая индексам (0,0), изображена в левом верхнем углу рисунка, самая высокочастотная – в нижнем правом. Базисная функция для (0,1) представляет собой половину периода косинусоиды по одной координате и константу - по другой, базисная функция с индексами (1,0) – то же самое, но повернута на 90⁰.

Дискретное косинусное преобразование вычисляется путем поэлементного перемножения и суммирования блоков изображения 8х8 пикселов с каждой из этих базисных функций. В результате, к примеру, компонента DCT -спектра с индексами (0,0) будет представлять собой просто сумму всех элементов блока изображения, то есть среднюю для блока яркость. В компоненту с индексом (0,1) усредняются с одинаковыми весами все горизонтальные детали изображения, а по вертикали наибольший вес присваивается элементам верхней части изображения и т.д. Можно заметить, что чем ниже и правее в матрице DCT его компонента, тем более высокочастотным деталям изображения она соответствует.

Для того, чтобы получить исходное изображение по его DCT- спектру (выполнить обратное преобразование), нужно теперь базисную функцию с индексами (0,0) умножить на спектральную компоненту с координатами (0,0), прибавить к результату произведение базисной функции (1,0) на спектральную компоненту (1,0) и т.д.

В приведенной ниже табл. 15.1 приведены числовые значения одного из блоков изображения и его DCT -спектра:

Таблица 15.1

Исходные данные
Результат DCT
235,6	-1	-12,1	-5,2	2,1	-1,7	-2,7	1,3
-22,6	-17,5	-6,2	-3,2	-2,9	-0,1	0,4	-1,2
-10,9	-9,3	-1,6	1,5	0,2	-0,9	-0,6	-0,1
-7,1	-1,9	0,2	1,5	0,9	-0,1		0,3
-0,6	-0,8	1,5	1,6	-0,1	-0,7	0,6	1,3
1,8	-0,2	1,6	-0,3	-0,8	1,5		-1
-1,3	-0,4	-0,3	-1,5	-0,5	1,7	1,1	-0,8
-2,6	1,6	-3,8	-1,8	1,9	1,2	-0,6	-0,4

Отметим очень интересную особенность полученного DCT -спектра: наибольшие его значения сосредоточены в левом верхнем углу табл. 15.1 (низкочастотные составляющие), правая же нижняя его часть (высокочастотные составляющие) заполнена относительно небольшими числами. Чисел этих, правда, столько же, как и в блоке изображения: 8х8 = 64, то есть пока никакого сжатия не произошло, и, если выполнить обратное преобразование, получим тот же самый блок изображения.

Следующим этапом работы алгоритма JPEG является квантование (табл. 15.2).

Если внимательно посмотреть на полученные в результате DCT коэффициенты, то будет видно, что добрая их половина - нулевые или имеет очень небольшие значения (1 - 2). Это высокие частоты, которые (обычно) могут быть безболезненно отброшены или, по крайней мере, округлены до ближайшего целого значения.

Квантование заключается в делении каждого коэффициента DCT на некоторое число в соответствии с матрицей квантования. Эта матрица может быть фиксированной либо, для более качественного и эффективного сжатия, получена в результате анализа характера исходной картинки. Чем больше числа, на которые происходит деление, тем больше в результате деления будет нулевых значений, а значит, сильнее сжатие и заметнее потери.

Таблица 15.2

Ранее полученный результат DCT
235,6	-1	-12,1	-5,2	2,1	-1,7	-2,7	1,3
-22,6	-17,5	-6,2	-3,2	-2,9	-0,1	0,4	-1,2
-10,9	-9,3	-1,6	1,5	0,2	-0,9	-0,6	-0,1
-7,1	-1,9	0,2	1,5	0,9	-0,1		0,3
-0,6	-0,8	1,5	1,6	-0,1	-0,7	0,6	1,3
1,8	-0,2	1,6	-0,3	-0,8	1,5		-1
-1,3	-0,4	-0,3	-1,5	-0,5	1,7	1,1	-0,8
-2,6	1,6	-3,8	-1,8	1,9	1,2	-0,6	-0,4
Таблица квантования
Результат квантования
		-1
-2	-1
-1	-1

Совершенно очевидно, что от выбора таблицы квантования будет в значительной степени зависеть как эффективность сжатия – число нулей в квантованном (округленном) спектре,– так и качество восстановленной картинки.

Таким образом, мы округлили результат DCT и получили в большей или меньшей степени искаженный поблочный спектр изображения.

Следующим этапом работы алгоритма JPEG является преобразование 8х8 матрицы DCT -спектра в линейную последовательность. Но делается это таким образом, чтобы сгруппировать по возможности вместе вначале все большие значения и потом все нулевые значения спектра. Совершенно очевидно, что для этого нужно прочесть элементы матрицы коэффициентов DCT в порядке, изображенном на рис. 15.4, то есть зигзагообразно - из левого верхнего угла к правому нижнему.

i) Рис. 15.4

Эта процедура называется зигзаг-сканированием.

В результате такого преобразования квадратная матрица 8х8 квантованных коэффициентов DCT превратится в линейную последовательность из 64 чисел, большая часть из которых – это идущие подряд нули. Известно, что такие потоки можно очень эффективно сжимать путем кодирования длин повторений. Именно так это и делается.

На следующем, пятом этапе JPEG -коди-рования получившиеся цепочки нулей подвергаются кодированию длин повторений.

ii) И, наконец, последним этапом работы алгоритма JPEG является кодирование получившейся последовательности каким-либо статистическим алгоритмом или алгоритам из серии LZW. Обычно используется кодирование по методу Шеннона-Фано или или по алгоритму Хаффмена. В результате получается новая последовательность, размер которой существенно меньше размера массива исходных данных.

Последние два этапа кодирования обычно называют вторичным сжатием, и именно здесь происходит статистическое кодирование без потерь, и с учетом характерной структуры данных - существенное уменьшение их объема.

Декодирование данных сжатых согласно алгоритму JPEG производится точно так же, как и кодирование, но все операции следуют в обратном порядке.

После распаковки методом Хаффмена (или LZW) и расстановки линейной последовательности в блоки размером 8х8 чисел спектральные компоненты деквантуются с помощью сохраненных при кодировании таблиц квантования. Для этого распакованные 64 значения DCT умножаются на соответствующие числа из таблицы. После этого каждый блок подвергается обратному косинусному преобразованию, процедура которого совпадает с прямым и различается только знаками в матрице преобразования. Последовательность действий при декодировании и полученный результат иллюстрируются приведенной ниже табл. 16.3.

Таблица 15.3

Квантованные данные
		-1
-2	-1
-1	-1
Деквантованные данные
		-10
-24	-12
-14	-13
Результат обратного DCT
Для сравнения - исходные данные

Очевидно, что восстановленные данные несколько отличаются от исходных. Это естественно, потому что JPEG и разрабатывался, как сжатие с потерями.

На представленном ниже рис. 15.5 приведено исходное изображение (слева), а также изображение, сжатое с использованием алгоритма JPEG в 10 раз (в центре) и в 45 раз (справа). Потеря качества в последнем случае вполне заметна, но и выигрыш по объему тоже очевиден.

Рис. 15.5

Итак, JPEG -сжатие состоит из следующих этапов:

1. Разбиение изображения на блоки размером 8х8 пикселов.

2. Применение к каждому из блоков дискретного косинусного преобразования.

3. Округление коэффициентов DCT в соответствии с заданной матрицей весовых коэффициентов.

4. Преобразование матрицы округленных коэффициентов DCT в линейную последовательность путем их зигзагообразного чтения.

5. Кодирование повторений для сокращения числа нулевых компнент.

6. Статистическое кодирование результата кодом Хаффмена или арифметическим кодом.

Декодирование производится точно так же, но в обратном порядке.

Существенными положительными сторонами алгоритма сжатия JPEG являются:

- возможность задания в широких пределах (от 2 до 200) степени сжатия;

- возможность работы с изображениями любой разрядности;

- симметричность процедур сжатия – распаковки.

К недостаткам можно отнести наличие ореола на резких переходах цветов - эффект Гиббса, а также распадение изображения на отдельные квадратики 8х8 при высокой степени сжатия.

Дата добавления: 2014-01-04