3.7.3. Практическое DCT

Уравнения (3.0) легко переводятся на любой язык программирования высокого уровня. Однако, имеется несколько возможностей для существенного ускорения вычисления этих величин. Эти формулы лежат в самом «сердце» метода JPEG, поэтому ускорение вычислений просто необходимо. Опишем несколько полезных приемов.

1. Независимо от размера изображения, используется только 32 значения функции косинус (см. следующий абзац). Их можно один раз вычислить и использовать много раз в операциях над единицами данных 8x8. Тогда вычисление выражения

будет состоять всего из двух операций умножения. Двойная сумма (3.9) потребует  умножений и 63 сложений.

(Аргументы функции косинус, используемые в DCT, имеют вид , где  и  - целые числа в интервале [0,7]. Их можно записать в виде , где  целое из интервала [0,15х7]. Поскольку косинус функция периодическая, для нее , , и так далее. В результате потребуется только 32 значения  при . Я признателен В.Сараванану (V.Saravanan), который указал мне на эту особенность DCT.)

2. Анализ двойной суммы (3.9) позволяет переписать ее в виде произведения матриц , где  - исходная 8x8 матрица пикселов, а матрица  определяется формулами

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

В итоге, вычисление одного элемента матрицы  требует восьми умножений и семи (ну пусть тоже восьми, для простоты) сложений. Умножение двух матриц  и  состоит из  умножений и столько же сложений. Умножение  на  потребует того же числа операций, значит одно DCT единицы данных состоит из 2х8 операций умножения (и сложения). Если исходное изображение состоит из  пикселов, причем , где  - число единиц данных, то для вычисления DCT всех этих единиц понадобиться  умножений (и столько же сложений). Для сравнения, вычисление одного DCT всего изображения потребует  операций. С помощью разделения изображения на единицы данных мы сократили общее число умножений (и сложений) в  раз. К сожалению, число  не может быть слишком большим, поскольку это уменьшает размер единицы данных.

Напомним, что цветное изображение состоит из трех компонент (обычно это RGB, которое преобразуется в YCbCr или в YPbPr). Каждая компонента преобразуется отдельно, что дает общее число операций равное . Для изображения с разрешением 512х512 пикселов потребуется сделать  умножений (и сложений).

3. Другой путь ускорения DCT состоит в выполнении арифметических вычислений над числами, представленными в форме с фиксированной точкой, а не в форме с плавающей точкой. Для многих компьютеров операции над числами с фиксированной точкой делаются существенно быстрее операций с плавающей точкой (некоторые высоко производительные компьютеры, вроде CDC 6400, CDC 7600 и различные системы CRAY являются заметными исключениями).

Бесспорно, лучший алгоритмом для DCT описан в [Feig, Linzеr 90]. Для него требуется всего 54 умножения и 468 сложений и сдвигов. На сегодняшний день имеются различные специализированные микросхемы, которые выполняют эти процедуры очень эффективно. Интересующийся читатель может познакомиться в [Loeffler et al. 89] с быстрым алгоритмом одномерного DCT, использующим всего 11 умножений и 29 сложений.