Что такое вейвлет-преобразование?
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