Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

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

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

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

f(2y + l)jv\ /(2ж + 1)1тг\ pxycos ( 16) cos ( 16)

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

(Аргументы функции косинус, используемые в DCT, имеют вид (2х + 1)г'7г/16, где х и г - целые числа в интервале [0,7]. Их можно записать в виде П7г/16, где п - целое из интервала [0,15 х 7]. Поскольку косинус-функция периодическая, для нее cos(327r/16) = = cos(07r/16), cos(337r/16) = cos(l7r/16), и так далее. В результате потребуется только 32 значения cos(n7r/16) при п = 0,1,... ,31. Я признателен В.Сараванану (V.Saravanan), который указал мне на эту особенность DCT.)

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

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

Напомним, что цветное изображение состоит из трех компонент (обычно это RGB, которое преобразуется в YCbCr или в YPbPr). Каждая компонента преобразуется отдельно, что дает общее число операций равное 3 • 2д283 = 3072д2. Для изображения с разрешением 512 х 512 пикселов потребуется сделать 3072 х 642 = 12 582 912 умножений (и сложений).

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

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