§ Одномерное преобразование

Элементы матрицы представлены формулой DCT-2n (число 2 - это версия ДКП, n - размерность):
DCT(i,j) = c(i) cos \frac{ i (j + 0.5) \pi }{n}
Коэффициент перед косинусом вычисляется так:
  • c(i) = \sqrt{\frac{2}{n}} если i > 0
  • c(i) = \frac{1}{\sqrt{n}} если i = 0
Это - прямое преобразование. Обратное преобразование точно такое же, необходимо всего лишь транспонировать матрицу.

§ Прямое преобразование

Допустим, есть вектор на 8 элементов. Нужно умножить его на матрицу 8x8
v0   m00 m01 ... m07
v1   m10 m11 ... m17
.. x ..............
v6   m60 m61 ... m67
v7   m70 m71 ... m77
По правилу умножения матриц, каждый элемент вектора (столбец) умножается на строку в матрице:
v'_i = \sum_{j=0}^{n-1} v_{j} m_{ij}
Другими словами, например, рассчитаем:
v'_3 = v_0 m_{30} + v_1 m_{31} + v_2 m_{32} + v_3 m_{33} + v_4 m_{34} + v_5 m_{35} + v_6 m_{36} + v_7 m_{37}
И так для каждого нового элемента столбца.

§ Обратное преобразование

Здесь все будет так же, кроме одного: матрица транспонируется. То есть, она как будто переворачивается на 90 градусов и значения следующие:
v0   m00 m10 ... m70
v1   m01 m11 ... m11
.. x ..............
v6   m06 m16 ... m76
v7   m07 m17 ... m77
Потому рассчитываются теперь значения иначе:
v'_i = \sum_{j=0}^{n-1} v_{j} m_{ji}
Здесь от предыдущей формулы поменялся только порядок m_{ji}

§ Небольшой вывод преобразования

Умножим вектор на матрицу
v0   m00 m01 m02
v1 x m10 m11 m12
v2   m20 m21 m22
Получим
f0 = v0*m00 + v1*m01 + v2*m02
f1 = v0*m10 + v1*m11 + v2*m12
f2 = v0*m20 + v1*m21 + v2*m22
Умножим снова вектор на транспонированную матрицу
f0   m00 m10 m20
f1 x m01 m11 m21
f2   m02 m12 m22
Получим
n0 = f0*m00 + f1*m10 + f2*m20
n1 = f0*m01 + f1*m11 + f2*m21
n2 = f0*m02 + f1*m12 + f2*m22
А теперь вместо f0,f1,f2 подставим их выражения
n0 = (v0*m00 + v1*m01 + v2*m02)*m00 + (v0*m10 + v1*m11 + v2*m12)*m10 + (v0*m20 + v1*m21 + v2*m22)*m20
n1 = (v0*m00 + v1*m01 + v2*m02)*m01 + (v0*m10 + v1*m11 + v2*m12)*m11 + (v0*m20 + v1*m21 + v2*m22)*m21
n2 = (v0*m00 + v1*m01 + v2*m02)*m02 + (v0*m10 + v1*m11 + v2*m12)*m12 + (v0*m20 + v1*m21 + v2*m22)*m22
Внесем общие множители из скобок:
n0 = (v0*m00*m00 + v1*m01*m00 + v2*m02*m00) + (v0*m10*m10 + v1*m11*m10 + v2*m12*m10) + (v0*m20*m20 + v1*m21*m20 + v2*m22*m20)
n1 = (v0*m00*m01 + v1*m01*m01 + v2*m02*m01) + (v0*m10*m11 + v1*m11*m11 + v2*m12*m11) + (v0*m20*m21 + v1*m21*m21 + v2*m22*m21)
n2 = (v0*m00*m02 + v1*m01*m02 + v2*m02*m02) + (v0*m10*m12 + v1*m11*m12 + v2*m12*m12) + (v0*m20*m22 + v1*m21*m22 + v2*m22*m22)
Перегруппировка v0,v1,v2:
n0 = v0*(m00*m00 + m10*m10 + m20*m20) + v1*(m01*m00 + m11*m10 + m21*m20) + v2*(m02*m00 + m12*m10 + m22*m20)
n1 = v0*(m00*m01 + m10*m11 + m20*m21) + v1*(m01*m01 + m11*m11 + m21*m21) + v2*(m02*m01 + m12*m11 + m22*m21)
n2 = v0*(m00*m02 + m10*m12 + m20*m22) + v1*(m01*m02 + m11*m12 + m21*m22) + v2*(m02*m02 + m12*m12 + m22*m22)
Итак, что в итоге получилось? Сейчас я обращу внимание на то, что у коэффициентов v0, v1, v2 — находится сумма квадратов. А что такое m_{ij} ? Это косинусы ведь.
Дело в том, что сумма этих косинусов по дискретным отсчета это значение интеграла:
\sum_{x=0}^{n-1} cos^2 ax = \int_{0}^{n} cos^2 (ax) dx
Поскольку значение a - это константа, поскольку она не меняется при суммировании, то видно, что функция то может быть ортонормирована! Просто необходимо домножить константу a в косинусе на \frac{\pi}{n} .
\sum_{x=0}^{n-1} cos^2 \frac{\pi ax}{n}
И выходит, что результат получается равным \frac{n}{2} для любого a . В данном случае в качестве a выступает номер i вектора, который вычисляем.
Еще одна особенность, что при a = 0 интеграл будет равен n .
Теперь рассмотрим два других компонента:
  • v1*(m01*m00 + m11*m10 + m21*m20)
  • v2*(m02*m00 + m12*m10 + m22*m20)
Как видно, они подчиняются правилу:
v_i \sum_{j=0}^{n-1} m_{ji} m_{ik}
Где k - это номер элемента вектора, который считаем (здесь константа), и i - номер компонента, тоже константа. И получается что:
v_i \sum_{x=0}^{n-1} cos (ax) cos (bx)
Где a \neq b . Аналогично, если привести в тот же ортонормированный вид, то получится 0, всегда 0, из-за свойства ортонормированности. Это означает, что при перемножении на такую матрицу и умножении ее снова на ту же, получим одно и то же одинаковое значение входящего вектора.
Естественно, это все доказано так себе, но хотя бы общее представление теперь у меня имеется, почему именно оно так работает.
Поскольку, если применять формулу вычисления, которая получилась выше, то для новых коэффициентов получатся значения v'_0 = n v_0 (выше показано, что интеграл при a = 0 равен n), и также v'_i = \frac{n}{2} v_i
Чтобы этого избежать, коэффициенты как раз и домножаются на \sqrt{\frac{1}{n}} для нулевого i , и \sqrt{\frac{2}{n}} для всех остальных.
15 фев, 2022
© 2007-2022 Все кони весьма получены