Дискретно-косинусное пробразование

Дискретное косинусное преобразование представляет собой разновидность преобразования Фурье и, так же как и оно, имеет обратное преобразование. Графическое изображение можно рассматривать как совокупность пространственных волн, причем оси X и Y совпадают с шириной и высотой картинки, а по оси Z откладывается значение цвета соответствующего пикселя изображения. Дискретное косинусное преобразование позволяет переходить от пространственного представления картинки к ее спектральному представлению и обратно. Воздействуя на спектральное представление картинки, состоящее из “гармоник”, то есть, отбрасывая наименее значимые из них, можно балансировать между качеством воспроизведения и степенью сжатия.

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

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


Формула дискретного косинусного преобразования:



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






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

Реализация ДКП.

Время, необходимое для вычисления каждого элемента матрицы дискретного косинусного преобразования, сильно зависит от ее размера. Так как используются два вложенных цикла, время вычислений составляет О (NxN). Одной из особенностей является то, что практически невозможно выполнить дискретное косинусное преобразование для всего изображения сразу. В качестве решения этой проблемы группа разработчиков JPEG предложила разбивать изображение на блоки размером 8x8 точек.

Увеличивая размеры блока дискретного косинусного преобразования, можно добиться некоторого увеличения результатов сжатия. Ограничения в коэффициенте сжатия объясняются малой вероятностью того, что удаленные на значительное расстояние точки изображения имеют одинаковые атрибуты.

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

При таком подходе формула дискретного косинусного преобразования может быть записана в следующем виде:

ДКП = КП * Точки * КПт

Где:

- ДКП - дискретное косинусное преобразование;

- КП - матрица косинусного преобразования размером NxN, элементы которой определяются по формуле

Точки - матрица размером NxN, состоящая из пикселов изображения;

Кпт - транспонированная матрица КП.

При перемножении матриц “цена” вычисления одного элемента результирующей матрицы составляют N умножений и N сложений, при вычислении матрицы дискретного косинусного преобразования - 2xN соответственно. По сравнению с O(NxN) это заметное повышение производительности. Так как дискретное косинусное преобразование является разновидностью преобразования Фурье, то все методы ускорения преобразования Фурье могут быть применены и в данном случае.

Comments