Что такое вейвлет-преобразование?
UPD: 21 октября: добавлена новая инфа и пару картинок, исправлены ошибки.
Прежде чем рассказать, как я делал свой кодек, расскажу, что же такое вейвлет преобразование. Остановлюсь на его дискретном варианте. Все, у кого в институте была хоть какая-никакая математика, слышали про ряды Фурье. Это когда функцию можно разложить по базису в таком виде:
$f(x) = \sum_{k=0}^{\infty} \langle f(x), \psi_{k}(x) \rangle \psi_{k}(x)$
Обычно в виде $\psi_{k}(x)$ берутся всевозможные синусы и косинусы, это называется разложением по гармоническому базису. Я напишу это условно так:
$f(x) = \sum_{k=-\infty}^{\infty} \langle f(x), e^{ikx} \rangle e^{ikx}$
Как мы видим, $\psi_{k}(x) = \psi_{1}(kx)$, где $\psi_{1}(x) = e^{ix}$. В результате такого разложения мы получаем набор коэффициентов, где каждый коэффициент отвечает за "наличие" в функции гармонического колебания с частотой 1,2,3 итд. За это мы "забываем" информацию о времени, то есть когда же именно в функции были эти колебания. Решением проблемы стали оконные преобразования Фурье, когда функция предварительно домножалась на "плавающее" во времени окно.
Другим подходом к вопросу о сохранении информации о времени является (дискретное) вейвлет преобразование. Его можно записать в виде
$c_{m,n} = \langle f(x), \psi_{m,n}(x) \rangle = a^{-m/2}\langle f(x), \psi(a^{-m}x-nb) \rangle$
Здесь, как мы видим, смысл похож на ряд Фурье, за исключением того, что функция $\psi(x)$ не только меняет свой масштаб ("икс" домножается на множитель), но и сдвигается по времени. Таким образом, мы получаем и частотную составляющую, и временную. Однако тут есть простое правило, которое заключается в следующем: если мы точно знаем частоту сигнала, то никогда не узнаем, когда он произошел, и если точно знаем время — никогда не узнаем частоту. Возможны варианты посередине — например, частота сигнала почти 100Гц (с примесями), сигнал возник между таким-то временем и таким-то.
Существует множество вариантов функции $\psi(x)$, для которого существует обратное преобразование (т.е., по коэффициентам можно восстановить $f(x)$). Я остановлюсь на случае $a=2, b=1$:
$\psi_{m,n} = 2^{-m/2}\psi(2^{-m}x - n)$.
Также я покажу, как найти $\psi(x)$, для которых
$f(x) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} \langle f(x), \psi_{m,n}(x) \rangle \psi_{m,n}(x)$
Обычно в виде $\psi_{k}(x)$ берутся всевозможные синусы и косинусы, это называется разложением по гармоническому базису. Я напишу это условно так:
$f(x) = \sum_{k=-\infty}^{\infty} \langle f(x), e^{ikx} \rangle e^{ikx}$
Как мы видим, $\psi_{k}(x) = \psi_{1}(kx)$, где $\psi_{1}(x) = e^{ix}$. В результате такого разложения мы получаем набор коэффициентов, где каждый коэффициент отвечает за "наличие" в функции гармонического колебания с частотой 1,2,3 итд. За это мы "забываем" информацию о времени, то есть когда же именно в функции были эти колебания. Решением проблемы стали оконные преобразования Фурье, когда функция предварительно домножалась на "плавающее" во времени окно.
Другим подходом к вопросу о сохранении информации о времени является (дискретное) вейвлет преобразование. Его можно записать в виде
$c_{m,n} = \langle f(x), \psi_{m,n}(x) \rangle = a^{-m/2}\langle f(x), \psi(a^{-m}x-nb) \rangle$
Здесь, как мы видим, смысл похож на ряд Фурье, за исключением того, что функция $\psi(x)$ не только меняет свой масштаб ("икс" домножается на множитель), но и сдвигается по времени. Таким образом, мы получаем и частотную составляющую, и временную. Однако тут есть простое правило, которое заключается в следующем: если мы точно знаем частоту сигнала, то никогда не узнаем, когда он произошел, и если точно знаем время — никогда не узнаем частоту. Возможны варианты посередине — например, частота сигнала почти 100Гц (с примесями), сигнал возник между таким-то временем и таким-то.
Существует множество вариантов функции $\psi(x)$, для которого существует обратное преобразование (т.е., по коэффициентам можно восстановить $f(x)$). Я остановлюсь на случае $a=2, b=1$:
$\psi_{m,n} = 2^{-m/2}\psi(2^{-m}x - n)$.
Также я покажу, как найти $\psi(x)$, для которых
$f(x) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} \langle f(x), \psi_{m,n}(x) \rangle \psi_{m,n}(x)$
Multiresolution analysis.
Инфа здесь пойдет без пруфов, так как материал слишком большой. Предположим что мы знаем некое пространство $V_0$, которое является подпространством $L^2$. Допустим, мы знаем набор функций $\phi_{0,n}(x) = \phi (x-n)$, являющихся в нём ортнормированным базисом. Также мы знаем, что более "раздутая" версия $\phi(x)$ выражается через более "сжатые" версии себя самой так:
$\phi(x) = \sqrt{2} \sum_{n=-\infty}^{\infty} h_{n}\phi(2x-n)$
Тогда функция $\psi(x) = \sqrt{2} \sum_{n=-\infty}^{\infty} d_{n}\phi(2x-n)$, где $d_{n} = (-1)^{n-1}h_{-n-1}$ будет служить "основой" для функций $\psi_{m,n} = 2^{-m/2}\psi(2^{-m}x - n)$, которые будут ортнормированным базисом на всём пространстве $L^2$. $\psi(x)$ определяются уникально вплоть до сдвига. Например, для коэффициентов $d_n$ можно использовать уравнение $d_{n} = (-1)^{n-1}h_{2N-n-1}$, где $N$ — любое целое.
Любую функцию $f \in L^2$ можно представить в виде:
$f(x) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} \langle f(x), \psi_{m,n}(x) \rangle \psi_{m,n}(x)$ или $f(x) = \sum_{m=-\infty}^{M} \sum_{n=-\infty}^{\infty} \langle f(x), \psi_{m,n}(x) \rangle \psi_{m,n}(x) + \sum_{n=-\infty}^{\infty} \langle f(x), \phi_{M,n}(x) \rangle \phi_{M,n}(x)$.
Функция $\phi(x)$ называется scaling function, а $\psi(x)$ — mother wavelet.
Любую функцию $f \in L^2$ можно представить в виде:
$f(x) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} \langle f(x), \psi_{m,n}(x) \rangle \psi_{m,n}(x)$ или $f(x) = \sum_{m=-\infty}^{M} \sum_{n=-\infty}^{\infty} \langle f(x), \psi_{m,n}(x) \rangle \psi_{m,n}(x) + \sum_{n=-\infty}^{\infty} \langle f(x), \phi_{M,n}(x) \rangle \phi_{M,n}(x)$.
Обычно ценятся вейвлеты, где только конечное число $h_n$ не равны нулю. Тогда $\phi(x)$ и $\psi(x)$ будут иметь компактный носитель и хорошо оценивать время, когда произошел тот или иной сигнал.
Самый простой пример вейвлета, построенного таким образом — вейвлет Хаара. Возьмем $\phi(x) = \chi[0,1]$ Очевидно, что $\langle \phi(x-k), \phi(x-l) \rangle = \delta_{k,l}$. Видно, что $\phi(x) = \sqrt{2} (\frac{1}{\sqrt {2}} \phi(2x) + \frac{1}{\sqrt {2}} \phi(2x-1))$, тогда $\psi(x) = \sqrt{2} (-\frac{1}{\sqrt {2}} \phi(2x) + \frac{1}{\sqrt {2}} \phi(2x-1)) = \phi(2x-1) - \phi(2x) = \chi[\frac{1}{2},1] - \chi[0, \frac{1}{2}]$ будет основой для нашего базиса.
 |
| График mother wavelet для вейвлета Хаара (умноженный на -1) |
Это единственный пример, который находится так лекго, и функция $\psi(x)$ задаётся в явном виде.
Для построения других примеров введем полезные ограничения. Пусть $\int_{-\infty}^{-\infty} \phi(x) dx = 1$ и $\int_{-\infty}^{-\infty} x^k \psi(x) dx = 0$ для всех $k = 0, 1, \cdots, N$. Про последний интеграл говорят, что mother wavelet имеет $N+1$ нулевых моментов. В частности вейвлет Хаара имеет один нулевой момент. Нулевые моменты полезны тем, что они отчасти определяют скорость, с которой коэффициенты разложения стремятся к нулю. Представим функцию $f(x)$ в виде ряда Тейлора вблизи точки $a$: $f(x) = f(a) + f'(a)(x-a) + \frac{f''(a)}{2}(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n + \cdots$. Тогда $\langle f(x), \psi(x) \rangle = \frac {f^{(N+1)}(a)}{(N+1)!}\langle (x-a)^{N+1}, \psi(x) \rangle + \cdots$.
Это значит, что при малых масштабах (малом $m$), коэффициенты разложения будут ближе к $0$ при большем $N$, так как $\lim_{n->\infty} (x-a)^n = 0$ при $\left|x-a\right| < 1$.
Возьмем преобразование Фурье уравнения, написанного выше:
$\phi(x) = \sqrt{2} \sum_{n=-\infty}^{\infty} h_{n}\phi(2x-n)$
Получим следующее:
$\hat{\phi}(s) = \frac{1}{\sqrt{2}} \sum_{n=-\infty}^{\infty} h_{n}e^{-ins/2}\hat{\phi}(s/2)$
Можно определить функцию $\hat{m}(s) = \sum_{n=-\infty}^{\infty} h_{n}e^{-ins}$, называющуюся генерирующей функцией. Тогда
$\hat{\phi}(s) = \hat{m}(s/2)\hat{\phi}(s/2)$
Аналогично
$\hat{\psi}(s) = \hat{m_1}(s/2)\hat{\phi}(s/2)$, где $\hat{m_1}(s) = e^{is}\overline{\hat{m}(s+\pi)}$
Теперь легко доказать, что условию $\int_{-\infty}^{-\infty} \phi(x) dx = 1$ соответствует $\hat{m}(0) = 1$, а условию нулевых моментов — $\hat{m}^{(k)}(\pi) = 0$ для $k = 0, 1, \cdots, N$
Условие ортогональности $\langle \phi_{0,k}, \phi_{0,n} \rangle = \delta_{kn}$, оказывается, можно представить в виде $\left| \hat{m}(s) \right|^2 + \left| \hat{m}(s+\pi) \right|^2 = 1$.
Добираемся до второго примера. Найдем вейвлет, у которого $n$ исчезающих моментов. Будем искать $\hat{m}(s)$ в виде $\hat{m}(s) = (\frac{1+e^{-is}}{2})^n L(s)$ (видно, что все условия соблюдены, кроме, пока что, условия ортогональности), где $L(s)$ — тригонометрический многочлен. Находим $\left| \hat{m}(s) \right|^2 = [(\frac{1+e^{is}}{2})(\frac{1+e^{-is}}{2})]^n Q(\cos s) = \cos^{2n} (\frac{s}{2}) Q(\cos s)$, где $Q(\cos s)$ — многочлен от $\cos s$. Вводим переменную $x = \sin^2 (\frac{s}{2})$.
Тогда $\left| \hat{m}(s) \right|^2 = (1-x)^n Q(1-2x)$
$\left| \hat{m}(s+\pi) \right|^2 = \sin^{2n}(\frac{s}{2}) Q(-\cos s) = x^nQ(2x-1)$.
Обозначив $P(x) = Q(1-2x)$ получим уравнение
$(1-x)^nP(x) + x^nP(1-x) = 1$.
Это уравнение называется уравнением Безу (точнее, это его частный случай) и имеет решение
$P(x) = \sum_{k=0}^{n-1} C_{n+k-1}^{k} x^k + x^nR(2x-1)$, где $R(x)$ — нечетный многочлен или $0$. Для $n=2$ подойдет $P(x) = 1 + 2x$.
Затем мы находим $Q(1-2x)$:
$Q(1-2x) = 2 - (1 -2x) = 2 - \cos s$
Теперь находим $L(s)$ (нужно искать многочлен той же степени, что и $Q$).
$L(s) = a_0 + a_1 e^{-is}$
$L(s)L(-s) = (a_0 + a_1^{-is})(a_0 + a_1^{is}) = 2 - \frac{e^{is} + e^{-is}}{2}$
После этого находим $\hat{m}(s)$:
$\hat{m}(s) = \frac{1}{\sqrt{2}} (\frac{1+\sqrt{3} }{4\sqrt{2}}+ \frac{3+\sqrt{3}}{4\sqrt{2}}e^{-is} + \frac{3-\sqrt{3}}{4\sqrt{2}}e^{-2is} +\frac{1-\sqrt{3}}{4\sqrt{2}}e^{-3is})$
Или $\phi(x)$:
$\phi(x) = \sqrt{2} (\frac{1+\sqrt{3} }{4\sqrt{2}}\phi(2x)+ \frac{3+\sqrt{3}}{4\sqrt{2}}\phi(2x-1) + \frac{3-\sqrt{3}}{4\sqrt{2}}\phi(2x-2) +\frac{1-\sqrt{3}}{4\sqrt{2}}\phi(2x-3))$
Такие вейвлеты называются вейвлетами Добеши, значения коэффициентов $h_k$ для другого количества нулевых моментов есть в википедии.
Графики scaling function и mother wavelet для вейвлетов D4 (2 нулевых момента) и D6 (3 нулевых момента):
или
Для построения других примеров введем полезные ограничения. Пусть $\int_{-\infty}^{-\infty} \phi(x) dx = 1$ и $\int_{-\infty}^{-\infty} x^k \psi(x) dx = 0$ для всех $k = 0, 1, \cdots, N$. Про последний интеграл говорят, что mother wavelet имеет $N+1$ нулевых моментов. В частности вейвлет Хаара имеет один нулевой момент. Нулевые моменты полезны тем, что они отчасти определяют скорость, с которой коэффициенты разложения стремятся к нулю. Представим функцию $f(x)$ в виде ряда Тейлора вблизи точки $a$: $f(x) = f(a) + f'(a)(x-a) + \frac{f''(a)}{2}(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n + \cdots$. Тогда $\langle f(x), \psi(x) \rangle = \frac {f^{(N+1)}(a)}{(N+1)!}\langle (x-a)^{N+1}, \psi(x) \rangle + \cdots$.
Это значит, что при малых масштабах (малом $m$), коэффициенты разложения будут ближе к $0$ при большем $N$, так как $\lim_{n->\infty} (x-a)^n = 0$ при $\left|x-a\right| < 1$.
Возьмем преобразование Фурье уравнения, написанного выше:
$\phi(x) = \sqrt{2} \sum_{n=-\infty}^{\infty} h_{n}\phi(2x-n)$
Получим следующее:
$\hat{\phi}(s) = \frac{1}{\sqrt{2}} \sum_{n=-\infty}^{\infty} h_{n}e^{-ins/2}\hat{\phi}(s/2)$
Можно определить функцию $\hat{m}(s) = \sum_{n=-\infty}^{\infty} h_{n}e^{-ins}$, называющуюся генерирующей функцией. Тогда
$\hat{\phi}(s) = \hat{m}(s/2)\hat{\phi}(s/2)$
Аналогично
$\hat{\psi}(s) = \hat{m_1}(s/2)\hat{\phi}(s/2)$, где $\hat{m_1}(s) = e^{is}\overline{\hat{m}(s+\pi)}$
Теперь легко доказать, что условию $\int_{-\infty}^{-\infty} \phi(x) dx = 1$ соответствует $\hat{m}(0) = 1$, а условию нулевых моментов — $\hat{m}^{(k)}(\pi) = 0$ для $k = 0, 1, \cdots, N$
Условие ортогональности $\langle \phi_{0,k}, \phi_{0,n} \rangle = \delta_{kn}$, оказывается, можно представить в виде $\left| \hat{m}(s) \right|^2 + \left| \hat{m}(s+\pi) \right|^2 = 1$.
Добираемся до второго примера. Найдем вейвлет, у которого $n$ исчезающих моментов. Будем искать $\hat{m}(s)$ в виде $\hat{m}(s) = (\frac{1+e^{-is}}{2})^n L(s)$ (видно, что все условия соблюдены, кроме, пока что, условия ортогональности), где $L(s)$ — тригонометрический многочлен. Находим $\left| \hat{m}(s) \right|^2 = [(\frac{1+e^{is}}{2})(\frac{1+e^{-is}}{2})]^n Q(\cos s) = \cos^{2n} (\frac{s}{2}) Q(\cos s)$, где $Q(\cos s)$ — многочлен от $\cos s$. Вводим переменную $x = \sin^2 (\frac{s}{2})$.
Тогда $\left| \hat{m}(s) \right|^2 = (1-x)^n Q(1-2x)$
$\left| \hat{m}(s+\pi) \right|^2 = \sin^{2n}(\frac{s}{2}) Q(-\cos s) = x^nQ(2x-1)$.
Обозначив $P(x) = Q(1-2x)$ получим уравнение
$(1-x)^nP(x) + x^nP(1-x) = 1$.
Это уравнение называется уравнением Безу (точнее, это его частный случай) и имеет решение
$P(x) = \sum_{k=0}^{n-1} C_{n+k-1}^{k} x^k + x^nR(2x-1)$, где $R(x)$ — нечетный многочлен или $0$. Для $n=2$ подойдет $P(x) = 1 + 2x$.
Затем мы находим $Q(1-2x)$:
$Q(1-2x) = 2 - (1 -2x) = 2 - \cos s$
Теперь находим $L(s)$ (нужно искать многочлен той же степени, что и $Q$).
$L(s) = a_0 + a_1 e^{-is}$
$L(s)L(-s) = (a_0 + a_1^{-is})(a_0 + a_1^{is}) = 2 - \frac{e^{is} + e^{-is}}{2}$
После этого находим $\hat{m}(s)$:
$\hat{m}(s) = \frac{1}{\sqrt{2}} (\frac{1+\sqrt{3} }{4\sqrt{2}}+ \frac{3+\sqrt{3}}{4\sqrt{2}}e^{-is} + \frac{3-\sqrt{3}}{4\sqrt{2}}e^{-2is} +\frac{1-\sqrt{3}}{4\sqrt{2}}e^{-3is})$
Или $\phi(x)$:
$\phi(x) = \sqrt{2} (\frac{1+\sqrt{3} }{4\sqrt{2}}\phi(2x)+ \frac{3+\sqrt{3}}{4\sqrt{2}}\phi(2x-1) + \frac{3-\sqrt{3}}{4\sqrt{2}}\phi(2x-2) +\frac{1-\sqrt{3}}{4\sqrt{2}}\phi(2x-3))$
Такие вейвлеты называются вейвлетами Добеши, значения коэффициентов $h_k$ для другого количества нулевых моментов есть в википедии.
Графики scaling function и mother wavelet для вейвлетов D4 (2 нулевых момента) и D6 (3 нулевых момента):
 |
| Вейвлет D6 (scaling function — фиолетовый, mother wavelet — зеленый график) |
 |
| Вейвлет D4 |
Я использую один из биортогональных вейвлетов. Это когда $f(x) = \sum_{m=-\infty}^{\infty} \sum_{n=-\infty}^{\infty} \langle f(x), \psi_{m,n}(x) \rangle \tilde{\psi}_{m,n}(x)$
Принцип их построения очень прост. Вводятся две функции $\hat{m}(s)$ и $\tilde{\hat{m}}(s)$ и условие ортогональности заменяется на $\hat{m}(s)\overline{\tilde{\hat{m}}(s)} + \hat{m}(s+\pi)\overline{\tilde{\hat{m}}(s+\pi)} = 1$. Для коэффициентов $d_n$ и $\hat{d}_n$ используются формулы:
$d_n = (-1)^{n+1}\tilde{h}_{-n+1}$
$\tilde{d}_n = (-1)^{n+1}h_{-n+1}$
Пример построения, когда обе функции $\psi(x)$ и $\tilde{\psi}(x)$ имеют 2 исчезающих момента:
Возьмем $\hat{m}(s) = (\frac{1+e^{-is}}{2})^2$ и $\tilde{\hat{m}}(s) = (\frac{1+e^{-is}}{2})^2Q(\cos s)$
Заметим, что $\cos^2 (\frac{s}{2}) = \frac{(e^{is/2} + e^{-is/2})^2}{4} = \frac{1}{4}(e^{is} + 2 + e^{-is}) = e^{is}(\frac{1+e^{-is}}{2})^2$
Тогда
$\hat{m}(s) = e^{-is}(\cos^2 \frac{s}{2})^2$ и $\tilde{\hat{m}}(s) = e^{-is}(\cos^2 \frac{s}{2})^2Q(\cos s)$
Относительно переменной $x = \sin^2 \frac{s}{2}$ снова получаем уравнение
$(1-x)^nP(x) + x^nP(1-x) = 1$, где $P(x) = Q(1-2x)$.
Решив его получим:
$\hat{m}(s) = \frac{1}{\sqrt 2} (\frac{1}{2\sqrt{2}}e^{-is} + \frac{1}{\sqrt{2}} + \frac{1}{2\sqrt{2}}e^{is})$
$\tilde{\hat{m}}(s) = \frac{1}{\sqrt 2} (-\frac{1}{4\sqrt{2}}(e^{-2is} + e^{2is}) + \frac{1}{2\sqrt{2}}(e^{-is} + e^{is}) + \frac{3}{2\sqrt{2}})$$d_n = (-1)^{n+1}\tilde{h}_{-n+1}$
$\tilde{d}_n = (-1)^{n+1}h_{-n+1}$
Пример построения, когда обе функции $\psi(x)$ и $\tilde{\psi}(x)$ имеют 2 исчезающих момента:
Возьмем $\hat{m}(s) = (\frac{1+e^{-is}}{2})^2$ и $\tilde{\hat{m}}(s) = (\frac{1+e^{-is}}{2})^2Q(\cos s)$
Заметим, что $\cos^2 (\frac{s}{2}) = \frac{(e^{is/2} + e^{-is/2})^2}{4} = \frac{1}{4}(e^{is} + 2 + e^{-is}) = e^{is}(\frac{1+e^{-is}}{2})^2$
Тогда
$\hat{m}(s) = e^{-is}(\cos^2 \frac{s}{2})^2$ и $\tilde{\hat{m}}(s) = e^{-is}(\cos^2 \frac{s}{2})^2Q(\cos s)$
Относительно переменной $x = \sin^2 \frac{s}{2}$ снова получаем уравнение
$(1-x)^nP(x) + x^nP(1-x) = 1$, где $P(x) = Q(1-2x)$.
Решив его получим:
$\hat{m}(s) = \frac{1}{\sqrt 2} (\frac{1}{2\sqrt{2}}e^{-is} + \frac{1}{\sqrt{2}} + \frac{1}{2\sqrt{2}}e^{is})$
или
$\phi(x) = \sqrt 2 (\frac{1}{2\sqrt{2}}(\phi(2x-1) + \phi(2x+1)) + \frac{1}{\sqrt{2}}\phi(2x))$
$\tilde{\phi}(x) = \sqrt 2 (-\frac{1}{4\sqrt{2}}(\tilde{\phi} (2x-2) + \tilde{\phi}(2x+2)) + \frac{1}{2\sqrt{2}}(\tilde{\phi} (2x-1) + \tilde{\phi}(2x+1)) + \frac{3}{2\sqrt{2}}\tilde{\phi}(2x))$ |
| График функции $\tilde{\phi}(x)$ (взято из википедии). |
Что делать с коэффициентами?
На данном этапе мы имеем набор коэффициентов $h_n$ и $d_n$ для функций $\phi(x)$ и $\psi(x)$ соответственно. Мы можем построить их на компьютере и считать скалярные произведения (чисто в целях визуализации можно использовать этот мой пакет для построения вейвлетов). Но лучше сделать иначе. Допустим, только $K$ коэффициентов $h_n$ отличны от нуля (для вейвлетов Добеши с $N$ исчезающими моментами, $2N$ коэффициентов отличны от нуля).
Чисто интуитивно предположим, что на самом-самом мелком масштабе, скажем, при $m=0$ значения нашей функции будут равны константе на некотором малом отрезке. Тогда $\langle f(x), \phi_{1,n}(x) \rangle = \sum_{k=0}^{K-1} h_k \langle f(x), \phi(2(x-n)-k) \rangle = \sum_{k=0}^{K-1} h_k f_{2n+k}\langle 1, \phi(2(x-n)-k) \rangle = \sum_{k=0}^{K-1} h_k f_{2n+k}$. Эта формула обозначает свертку (дискретную) функции $f(z)$ с фильтром $h(z) = \sum_{k=0}^{K-1} h_k z^{-k}$ и выбрасыванием каждого второго (нечетного) семпла. Такая же операция проводится с фильтром $d(z) = \sum_{k=0}^{K-1} d_k z^{-k}$. Итого scaling function можно рассматривать как низкочастотный (low pass) фильтр, а mother wavelet — как высокочастотный (high pass) фильтр. Из $N$ семплов функции получаем $N/2$ коэффициентов $a_n$ от low pass фильтра и $b_n$ от high pass. Далее повторяем процесс для коэффициентов $a_n$, получая результат для более "крупного" масштаба пока не остается один коэффициент $a_n$.
Реконструкция сигнала происходит добавлением нулей через каждый второй семпл и пропусканием через те же фильтры в обратном порядке
Ещё одна схема применения — через составление прямой и обратной матриц преобразования. Подробности здесь.
И наконец есть так называемая lifting scheme. Этот механизм я использую в своём кодеке. Подробности можно узнать в статье "Factoring wavelet transforms into lifting steps" (Daubechies, 1996).
Для биортогональных вейвлетов получаются два набора фильтров: $h(z)$, $d(z)$ и $\tilde{h}(z)$, $\tilde{d}(z)$. Один используется для прямого преобразования, другой — для обратного. К слову, только биортогональные вейвлеты могут быть симметричными (за исключением вейвлета Хаара). Симметричные вейвлеты имеют линейную фазу, а значит все частотные составляющие исходного сигнала получают одинаковую задержку после прохождения через фильтры.
Мой кодек.
Мой кодек работает выполняя вейвлет преобразование (я использую (4,2) биортогональный B-сплайн вейвлет). Так как любая (би)ортогональная последовательность функций слабо сходится к нулю, коэффициенты преобразования на малых масштабах весьма малы. Я использую этот факт, чтобы кодировать коэффициенты вейвлет преобразования кодом Райса, выбирая свой параметр для каждого масштаба. Результат сжатия — 50-70% от исходного размера. Реализяция на языке Common Lisp тут.
Comments
Post a Comment