3.5.3. Дискретное косинус-преобразованиеПрежде всего мы рассмотрим одномерное (векторное) преобразование DCT (в приложениях используется двумерное (матричное) косинус-преобразование, но векторное DCT проще понять, и оно основано на тех же принципах). На рис. 3.20 показано восемь волн косинуса,
которые формируют базисный вектор Программа для вычисления рис. 3.20 (Matematica). Можно показать, что все векторы Одномерное DCT имеет также другую интерпретацию. Можно рассмотреть векторное пространство, базисом которого служат векторы Рис. 3.20. Вычисление одномерного DCT. Например, выберем 8 (коррелированных) чисел
Вес
Табл. 3.21. Вычисление одномерного DCT. Рис. 3.22 иллюстрирует эту линейную комбинацию графически. Все восемь векторов На практике одномерное DCT проще всего вычислять по формуле
где Здесь исходными данными (пикселами, фрагментами звука или другими элементами) являются величины
Рис. 3.22. Графическое представление одномерного DCT. Следующий пример демонстрирует достоинства метода DCT. Рассмотрим множество, состоящее из 8 величин (исходных данных) 28.6375, 0.571202, 0.46194, 1.757, 3.18198, - 1.72956, 0.191342, -0.308709. Эти числа можно использовать для точного восстановления исходных данных (с маленькой ошибкой, вызванной ограничением на точность компьютерных вычислений). Наша цель, однако, улучшить сжатие с помощью подходящего квантования коэффициентов. Округляем (квантуем) их до 28.6, 0.6, 0.5, 1.8, 3.2, -1.8, 0.2, -0.3, применяем IDTC и получаем 12.0254, 10.0233, 7.96054, 9.93097, 12.0164, 9.99321, 7.94354, 10.9989. Еще раз квантуем коэффициенты: 28, 1, 1, 2, 3, –2, 0, 0 и опять получаем с помощью IDCT следующий результат: 12.1883, 10.2315, 7.74931, 9.20863, 11.7876, 9.54549, 7.82865, 10.6557. Наконец, квантуем коэффициенты до 28, 0, 0, 2, 3, –2, 0, 0 и получаем с помощью IDCT последовательность 11.236, 9.62443, 7.66286, 9.57302, 12.3471, 10.0146, 8.05304, 10.6842, в которой наибольшая разность между исходным значением (12) и реконструированным (11.236) равна 0.764 (или 6.4% от 12). Программа вычисления для системы Matematica приведена на рис. 3.23. Рис. 3.23. Эксперименты с одномерным DCT. Эти простые примеры показывают достоинства метода DCT. Множество 28, 0, 0, 2, 3, –2, 0, 0 грубо квантованных коэффициентов DCT обладает четырьмя свойствами, которые делают его идеальным для сжатия, причем с замечательной декомпрессией при малой потери данных. Вот эти четыре свойства: (1) множество состоит только из целых чисел, (2) только четыре из них не равны нулю, (3) нулевые коэффициенты образуют серии, (4) среди ненулевых коэффициентов только первый имеет большую величину; остальные меньше исходных чисел. Эти свойства можно использовать при реализации схемы RLE, метода Хаффмана или любой другой техники (см. § 3.7.4 и 3.7.5) для дальнейшего сжатия этого множества. Пример: Одномерное DCT (уравнение (3.7)) восьми коррелированных величин 11, 22, 33, 44, 55, 66, 77 и 88 произведет восемь коэффициентов 140, –71, 0, –7, 0, –2, 0, 0. После квантования получаем множество 140, –71, 0, 0, 0, 0, 0, 0 и применяем IDCT. В результате: 15, 20, 30, 43, 56, 69, 79 и 84. Эти числа весьма близки к исходным; наибольшее расхождение равно 4. На рис. 3.24 дана программа для этого примера. Рис. 3.24. Пример одномерного DCT (Matematica). Дойдя до этого места, воодушевленный читатель может воскликнуть: «Удивительно! Восемь исходных данных восстанавливаются всего с помощью двух чисел. Чудеса какие-то!»» Однако, те, кто поняли свойства преобразований, могут дать простое объяснение. Восстановление данные происходит не только по двум числам 140 и –71, но также по их положению в последовательности из 8 коэффициентов. Кроме того, исходные величины восстанавливаются с высокой точностью благодаря присутствию избыточности. Предельным случаем избыточных данных служит последовательность одинаковых величин. Они, конечно, имеют совершенную корреляцию, и мы чувствуем интуитивно, что одного числа будет достаточно для полного их восстановления. Реконструкция последовательности высоко коррелированных данных, такой, как 20, 31, 42, 53, ... потребует всего двух чисел. Ими могут быть начальное значение (20) и шаг (11) (разность этой арифметической прогрессии), но могут быть и другие числа. В общем случае, чем меньше коррелированы данные, тем больше чисел потребуется для их восстановления. Двумерное (матричное) DCT: Из опыта хорошо известно, что пикселы изображения имеют корреляцию по двум направлениям, а не только по одному (пикселы коррелируют со своими соседями слева, справа, а также сверху и снизу). Поэтому методы сжатия изображений используют двумерное DCT, которое задается формулой
при
где Двумерное DCT можно интерпретировать двумя способами: с помощью вращения (на самом деле, композиции двух вращений), и с помощью базиса в из уравнения (3.9). Результатом этого вращения служит блок
Здесь ужу столбцы матрицы Рис. 3.25. Двумерное DCT и двойное вращение. Вторая интерпретация (при На рис. 3.26 показано графическое представление 64 базисных образов двумерного DCT при Используя подходящее программное обеспечение, легко выполнить вычисление DCT и отобразить результаты графически. На рис. 3.29а приведена случайная матрица 8х8 из нулей и единиц. Эта матрица изображена на рис. 3.29b с помощью белых и черных квадратиков, обозначающих 1 и 0, соответственно. На рис. 3.29с показаны численные значения весов, на которые следует умножить каждый из 64 коэффициентов DCT для того, чтобы восстановить исходную матрицу. Рис. 3.26. 64 базисных изображения двумерного DCT. На этом рисунке нуль показан нейтрально-серым цветом, положительные числа светло-серым, а отрицательные темным. На рис. 3.29d даны численные значения этих весов. Приведена также программа для построения всех этих графиков. На рис. 3.30 сделаны те же самые построения, но применительно к более регулярным исходным данным. Теперь продемонстрируем достоинства двумерного DCT применительно к двум блокам чисел. Первый блок (табл. 3.27, слева) состоит из сильно коррелированных целых чисел в интервале [8,12], а второй (табл. 3.28, слева) образован случайными числами из того же интервала. Первый блок порождает один большой коэффициент DC, за которым следуют маленькие (включая 20 нулевых) коэффициентов АС. А среди коэффициентов DCT второго, случайного, блока имеется всего один нуль. Программа для рис. 3.26 (Matematica) Альтернативная программа для рис. 3.26 (Видно, почему пикселы в табл. 3.27 коррелированы. Все восемь чисел верхней строки таблицы близки друг к другу (расстояния между ними равны 2 или 3). Все остальные строки получаются циклическим сдвигом вправо предыдущей строки.)
Табл. 3.27. Двумерное DCT блока коррелированных величин.
Табл. 3.28. Двумерное DCT блока случайных величин. Рис. 3.29. Пример двумерного DCT (Mathematica). Сжатие любого изображения с помощью DCT можно теперь сделать следующим образом. 1. Разделить его на 2. Применить DCT к каждому блоку 3. Все 4. Сделать квантование каждого вектора коэффициентов Рис. 3.30. Пример двумерного DCT (Matematica). Декодер читает 64 квантованных вектора коэффициентов использует их для построения
|