Приложение Контрольные вопрос

Приложение 1. Вещественный интеграл Фурье. Сжатие изображений

Непериодическая вещественная функция $s(x) \,\!$ не может быть разложена в ряд Фурье. Однако ее всегда можно считать периодической с периодом $t_{x} \to \ \infty \,\!$ . Пусть она удовлетворяет условиям Дирихле, т. е. определена на всей числовой оси, имеет конечное число точек разрыва на каждом конечном промежутке и абсолютно интегрируема $\int\limits_{-\infty}^{\infty} |s(x)|\, dx <\ \infty \,\!$ , что всегда выполняется на практике. Тогда посредством предельного перехода $t_{x} \to \ \infty \,\!$ получается разложение $s(x) \,\!$ в так называемый вещественный (тригонометрический) интеграл Фурье

$s(x) = \int\limits_{0}^{\infty} \, d\nu_{x} \int\limits_{-\infty}^{\infty} s(u)\cos \big[2\pi \nu_{x}(x-u)\big] \, du = 2\int\limits_{0}^{\infty}\big[a_{\cos}(\nu_{x})\cos(2\pi x\nu_{x})+s_{\sin}(\nu_{x})\sin(2\pi x\nu_{x})\big] \, d\nu_{x} \to {\color{maroon}(1.1)}\,\!$

где $b_{\cos}(\nu_{x}) = \int\limits_{-\infty}^{\infty} s(u)\sin\big[ 2\pi\nu_{x}u\big] \, du = \int\limits_{-\infty}^{\infty} s(x)\cos\big[2\pi\nu_{x}\big] \, dx \to {\color{maroon}(1.2)} \,\!$

$a_{\sin}(\nu_{x}) = \int\limits_{-\infty}^{\infty} s(u)\cos\big[ 2\pi\nu_{x}u\big] \, du = \int\limits_{-\infty}^{\infty} s(x)\sin\big[2\pi\nu_{x}\big] \, dx \to {\color{maroon}(1.3)} \,\!$

$\nu_{x} \,\!$ – текущее значение пространственной (временной) частоты.

Интеграл Фурье $\color{maroon} (1.1) \,\!$ представляет вещественную функцию $s(x) \,\!$ в виде суммы бесконечного числа косинусоидальных гармоник с амплитудой $da = a_{cos}(\nu_{x})d\nu_{x} \,\!$ и синусоидальных гармоник с амплитудой $db = b_{sin}(\nu_{x})d\nu_{x} \,\!$ при непрерывно изменяющейся частоте $0 \le \nu_{x} <\ \infty \,\!$ . Функцию $a_{cos}(\nu_{x}) \,\!$ называют косинус-преобразованием Фурье, a $b_{sin}(\nu_{x}) \,\!$ – синус-преобразованием Фурье сигнала s(x). В зависимости от физического смысла переменной x говорят о непрерывном вещественном спектре амплитуд несмещенных по фазе косинусоидальных $a_{cos}(\nu_{x}) \,\!$ и синусоидальных $b_{sin}(\nu_{x}) \,\!$ гармоник или о непрерывном вещественном спектре амплитуд $a_{cos}(\nu_{t}), b_{sin}(\nu_{t}) \,\!$ которые также называют вещественной спектральной плотностью амплитуд соответственно косинусоидальных и синусоидальных гармоник.

Для углубления смысла вещественного интеграла Фурье выражение $\color{maroon} (1.1) \,\!$ можно преобразовать к виду

$s(x) = \int\limits_{0}^{\infty} d_{\cos}(nu_{x}) \cos \big[2\pi x \nu_{x} + \phi (nu_{x})\big] \, d\nu_{x} \to {\color{maroon}(1.4)} \,\!$

где $d_{\cos}(\nu_{x}) = \sqrt{a_{\cos}^2 (\nu_{x}) + b_{\sin}^2 (\nu_{x}) } \,\!$

$\phi (\nu_{x} = \arctan \big[-b_{\sin}(\nu_{x})/a_{\cos}(\nu_{x})\big] \,\!$

$\cos{\phi}(\nu_{x} = a_{\cos}(\nu_{x})/d(\nu_{t}) \,\!$

$\sin{\phi}(\nu_{x} = -b_{\sin}(\nu_{x})/\phi(\nu_{t}) \,\!$

Тогда говорят о непрерывных вещественных спектрах амплитуд $d_{\cos}(\nu_{x}) \,\!$ и фаз $\phi(\nu_{x}) \,\!$ или о непрерывных вещественных ЧВС амплитуд $d_{\cos}(\nu_{t}) \,\!$ и фаз $\phi(\nu_{t}) \,\!$ , смещенных по фазе косинусоидальных гармоник. Эти спектры часто называют вещественной спектральной плотностью амплитуд и фаз. При этом частоты непрерывно заполняют действительную полуось $0 \le \nu_{x}, \nu_{t} <\ \infty \,\!$ , а функции $d_{\cos} \,\!$ и $\phi \,\!$ задают закон распределения амплитуд и начальных фаз в зависимости от частоты. В результате интеграл Фурье $\color{maroon} (3.4) \,\!$ представляет вещественную функцию $s(x) \,\!$ в виде суммы бесконечного числа смещенных по фазе косинусоидальных гармоник с амплитудой $dd = d_{\cos}(\nu_{x})d\nu_{x} \,\!$ при непрерывно изменяющейся частоте.

Тригонометрический интеграл Фурье $\color{maroon} (1.1) \,\!$ обычно применяют для разложения в вещественный спектр непериодических многомерных и электрических сигналов, описываемых четными или нечетными функциями. Для четной функции $\color{maroon} (1.1) \,\!$ имеет вид косинус-интеграла Фурье из несмещенных по фазе косинусоидальных гармоник:

$s^{chot}(x) = 2 \int\limits_{0}^{\infty} a_{\cos}^{chot}(\nu_{x})\cos(2\pi x\nu_{x})\, d\nu_{x} \to {\color{maroon}(1.6)} \,\!$

где косинус-преобразование Фурье $\color{maroon} (1.2) \,\!$

$a_{\cos}^{chot}(\nu_{x}) = 2 \int\limits_{0}^{\infty} s^{chot}(x)\cos(2\pi x\nu_{x})\, dx \to {\color{maroon}(1.7)}\,\!$

В случае нечетной функции имеем синус-интеграл Фурье, задающий непрерывное разложение по не смещенным по фазе синусоидальным гармоникам:

$s^{nechot}(x) = 2 \int\limits_{0}^{\infty} b_{\sin}^{chot}(\nu_{x})\sin(2\pi x\nu_{x})\, d\nu_{x} \to {\color{maroon}(1.8)} \,\!$

где синус-преобразование Фурье ${\color{maroon}(1.3)} \,\!$

$b_{\sin}^{nechot}(\nu_{x}) = 2 \int\limits_{0}^{\infty} s^{nechot}(x)\sin(2\pi x\nu_{x})\, dx \color{maroon} (1.9)\,\!$

Формулы $\color{maroon} (1.6) \,\!$ – $\color{maroon} (4.6) \,\!$ обычно используют вместо $\color{maroon} (1.1) \,\!$ – $\color{maroon} (1.3) \,\!$ для временных сигналов $s(t) \,\!$ , так как последние заданы для $t \ge 0 \,\!$ и могут быть продолжены на всю действительную ось четным или нечетным образом.

Приложение 2. Математическое определение прямого ДКП [DCT (FDCT)] и обратного ДКП [DCT (IDCT)] применительно к использованию в формате хранения растровых изображений JPEG

Процесс сжатия изображения JPEG из следующих этапов:

1) Преобразование цветового пространства: [R G B] -> [Y Cb Cr] (R,G,B - 8-битовые величины без знака)

$\begin{vmatrix} y \\c_b \\c_r \end{vmatrix} = \begin{vmatrix} 0.299 & 0.587 & 0.114 \\ - 0.1687 & - 0.3313 & 0.5 \\ 0.5 & - 0.4187 & -0.0813 \end{vmatrix} \cdot \begin{vmatrix} r \\ g \\ b \end{vmatrix} + \begin{vmatrix} 0 \\ 128 \\ 128 \end{vmatrix} \,\!$

Новая величина названа яркостью. Это величина, используемая монохромными мониторами, чтобы представить цвет RGB. Физиологически, передает интенсивность цвета RGB воспринятого глазом.

Формула для Y, подобно средневзвешенному значению с разным весом для каждого спектрального компонента: глаз наиболее чувствителен на Зеленый цвет, затем следует Красный компонент и в последнюю очередь - Синий.

Величины $c_b = -0.1687\cdot r - 0.3313\cdot g + 0.5\cdot b + 128 \,\!$ и $cr = 0.5\cdot r - 0.4187\cdot g - 0.0813\cdot b + 128 \,\!$ названы цветовыми величинами и представляют 2 координаты в системе, которая измеряет оттенок и насыщение цвета (эти величины указывают количество синего и красного в этом цвете). Эти 2 координаты кратко названы цветоразностью.

2) Дискретизация и JPEG Стандарт

JPEG Стандарт принимает во внимание то, что глаз более чувствителен к яркости цвета, чем к оттенку этого цвета. (Черно-белые ячейки вида имеют больше влияния, чем ячейки дневного видения).

Так, для большинства JPG, яркость взята для каждого пикселя, тогда как цветоразность – как средняя величина для блока 2x2 пикселей. Имейте в виду, что это не обязательно, но при этом можно достичь хороших результатов сжатия, с незначительным убытком в визуальном восприятии нового обработанного изображения.

Примечание: JPEG стандарт определяет, что для каждого компонента образа (подобно, например Y) должно быть определено 2 коэффициента дискретизации: один для горизонтальной дискретизации и один для вертикальной дискретизации. Эти коэффициенты дискретизации определяются в файле JPG как относительно максимального коэффициента дискретизации (дополнительно об этом позже).

3) Сдвиг Уровня

Все 8-битовые величины без знака (Y,Cb,Cr) в изображении - "смещенные по уровню": они преобразовываются в 8-битовое знаковое представление вычитанием 128 из их величины.

4) 8x8 Дискретное Косинусное Преобразование (DCT)

Изображение делится на блоки 8x8 пикселей, затем для каждого блока 8x8 применяется DCT-трансформация. Заметьте, что если размер X исходного образа не делится на 8, шифратор должен сделать его делимым, дополняя остальные правые столбцы (пока X не станет кратным 8). Аналогично, если размер Y не делимо на 8, шифратор должен дополнить строки.

Блоки 8x8 обрабатываются слева направо и сверху вниз.

Поскольку каждый пиксель в блоке 8x8 имеет 3 компонента (Y,Cb,Cr), DCT приложен отдельно в трех блоках 8x8:

Первый блок 8x8 является блоком, который содержит яркость пикселей в исходном блоке 8x8;
Второй блок 8x8 является блоком, который содержит величины Cb;
И, аналогично, третий блок 8x8 содержит величины Cr.

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

DCT-трансформация очень похожа на 2-мерное преобразование Фурье, которое получает из временного интервала (исходный блок 8x8) частотный интервал (новые коэффициенты 8x8=64, которые представляют амплитуды проанализированного частотного пространства)

Математическое определение прямого DCT (FDCT) и обратного DCT (IDCT).

FDCT:

$f(u, v) = {c(u,v) \over 4} \cdot \sum_{x=0}^7\sum_{y=0}^7 f(x,y) \cdot \cos({2x+1 \over 16}\cdot u\pi) \cos ({2y+1 \over 16}\cdot v\pi)$

где $u,v = 0, ..., 7; c(u,v) = 1/2 \,\!$ , когда $u=v=0; c(u,v)=1 \,\!$ - в остальных случаях.

IDCT:

$f(x,y) = {1 \over 4} \cdot \sum_{x=0}^7\sum_{y=0}^7 c(u,v) \cdot f(u,v) \cdot \cos({2x+1 \over 16}\cdot u\pi) \cos ({2y+1 \over 16}\cdot v\pi)$

где $x,y = 0, ..., 7 \,\!$

Применение этих формул непосредственно в вычислительном отношении дорого, особенно, когда имеются разработанные более быстрые алгоритмы для прямого или обратного DCT. Один, названный AA&N, имеет только 5 операций умножения и 29 операций сложения. Больше информации и реализацию этого можно найти в свободном программном обеспечении для JPEG кодировщиков от Независимой JPEG Группы (IJG), их C-источники могут быть найдены на www.ijg.org.

Зигзагообразная перестановка 64 DCT коэффициентов

Так, после того, как мы выполнили DCT-преобразование над блоком величин 8x8, у нас есть новый блок 8x8. Затем, этот блок 8x8 просматривается по зигзагу подобно этому (числа в блоке 8x8 указывают порядок, в котором мы просматриваем 2-мерную матрицу 8x8). После того, как прошли по зигзагу матрицу 8x8, мы имеем теперь вектор с 64 коэффициентами (0..63) Смысл этого зигзагообразного вектора – в том, что мы просматриваем коэффициенты 8x8 DCT в порядке повышения пространственных частот. Так, мы получаем вектор, отсортированный критериями пространственной частоты: первая величина на векторе (индекс 0) соответствует самой низкой частоте в изображении – она обозначается термином DC. С увеличением индекса на векторе, мы получаем величины соответствующие высшим частотам (величина с индексом 63 соответствует амплитуде гармоники самой высокой частоты в блоке 8x8). Остальная часть коэффициентов DCT обозначается AC.