7.2.3. Преобразование DCT/IDCT

Дискретное косинус-преобразование DCT широко применяется в алгоритмах сжатия цифровых изображений и видео для декорреляции изображений или остаточных данных перед выполнением квантования и энтропийного сжатия (см. гл. 3). Если попытаться выполнить прямую реализацию преобразований FDCT и IDCT по формулам (3.4) и (3.5), то это потребует большого числа сложений и умножений. Однако возможно значительно сократить объем операций, используя особую структуру матрицы преобразования . В этом заключается причина чрезвычайной популярности DCT.

7.2.3.1. DCT 8x8

Вычисление прямого DCT по формулам (3.4) для блоков 8x8 (N = 8) потребует 64 х 64 = 4096 умножений и сохранений данных. Из матричной формы (см. (3.1)) видно, что двухмерное преобразование можно выполнить в два этапа (т.е. сначала найти произведение , а потом результат умножить на  или наоборот). Одномерное FDCT задается уравнением (7.4), где  — это N входных данных, а результатом служат N выходных коэффициентов . Преобразовав уравнение (3.4), можно показать, что двухмерное FDCT представимо в виде композиции двух одномерных преобразований (7.5). Для этого нужно сначала вычислить одномерное FDCT для каждого столбца входной матрицы (внутреннее преобразование), а затем совершить одномерное FDCT для каждой строки полученного результата (внешнее преобразование). Обратное двухмерное преобразование IDCT можно выполнить аналогичным образом (см. уравнение (7.5)). Каждое одномерное преобразование восьми компонент занимает 64 операции умножения/сохранения, что дает общее число из 64х8х2=1024 операций умножения/сохранения для двухмерного FDCT или ГОСТ блока 8x8.

                (7.4)

   (7.5)

    (7.6)

На первый взгляд может показаться, что выполнение одномерного FDCT размерности 8 по формуле (7.4) требует вычисления восьми различных косинусных множителей (т.е. значений  для восьми разных ) для каждого из восьми индексов (). Однако свойство симметрии функции  позволяет выполнить эти вычисления за меньшее число шагов. Например, рассмотрим вычисление  по формуле (7.4):

                   (7.7)

В формуле (7.4) имеется 8 умножений и 7 сложений (плюс деление на 2). Однако, используя свойство симметрии функции косинус, эту формулу можно упростить следующим образом:

      (7.8)

Аналогично формулу для вычисления   можно привести к виду

          (7.9)

Видно, что сложения и вычитания одинаковы в обеих формулах, и их достаточно выполнить только один раз, поэтому  и  можно вычислить, используя всего 8 сложений и 4 умножения (плюс деление на 2). Распространение этого приема на полное преобразование FDCT приводит к альтернативной «быстрой» реализации, близкой к известному алгоритму Чена, Смита и Фралика [14]. Поток данных в этом одномерном алгоритме можно представить в виде граф-схемы, приведенной на рис. 7.11. На этой схеме кружками обозначены сложения двух входов, квадратики обозначают умножения на константы, причем  обозначает c. Этот алгоритм использует только 26 сложений и вычитаний и 20 умножений (для сравнения, прямое вычисление по формуле (7.4) использует 64 сложения и 64 умножения).

Рисунок 7.11 представляет собой одно простое упрощение одномерного алгоритма DCT. За несколько лет было разработано много граф-схем алгоритмов, оптимизированных по различным требованиям (по минимуму умножений, минимуму вычитаний и т.п.). Дальнейшего улучшения можно добиться при прямой оптимизации двухмерного DCT (обычно при этом приходится платить увеличением сложности реализации алгоритма).

Рис. 7.11. Граф-схема FDCT.

Граф-схемные алгоритмы очень популярны при разработке программных кодеков, где (во многих случаях) лучшая производительность достигается путем минимизации числа вычислительно дорогих операций умножения. Для аппаратной реализации регулярность потока данных может быть важнее, чем число операций, что приводит к иным требованиям, применяемым к алгоритмам. Популярные аппаратные архитектуры для FDCT/IDCT основаны на применении параллельных мультипликаторов массивов и распределенной арифметики [15 - 18].