Курвлет

Кривые — это неадаптивный метод представления многомасштабных объектов . Являясь расширением концепции вейвлетов , они становятся популярными в аналогичных областях, а именно в обработке изображений и научных вычислениях .

Вейвлеты обобщают преобразование Фурье , используя основу, которая представляет как местоположение, так и пространственную частоту. Для 2D- или 3D-сигналов направленные вейвлет-преобразования идут дальше, используя базисные функции, которые также локализованы по ориентации . Кривллет-преобразование отличается от других направленных вейвлет-преобразований тем, что степень локализации ориентации меняется в зависимости от масштаба. В частности, мелкомасштабные базисные функции представляют собой длинные гребни; форма базисных функций в масштабе j равна $2^{-j}$ к $2^{-j/2}$ поэтому мелкомасштабные основания представляют собой тонкие гребни с точно определенной ориентацией.

Кривые являются подходящей основой для представления изображений (или других функций), которые являются гладкими, за исключением особенностей вдоль гладких кривых, где кривые имеют ограниченную кривизну , т.е. где объекты на изображении имеют минимальный масштаб длины. Это свойство справедливо для мультфильмов, геометрических диаграмм и текста. По мере увеличения таких изображений края, которые они содержат, кажутся все более прямыми. Кривые используют это свойство, определяя кривые с более высоким разрешением более вытянутыми, чем кривые с более низким разрешением. Однако естественные изображения (фотографии) этим свойством не обладают; у них есть детали в каждом масштабе. Поэтому для естественных изображений предпочтительнее использовать какое-либо направленное вейвлет-преобразование, вейвлеты которого имеют одинаковое соотношение сторон в каждом масштабе.

Когда изображение правильного типа, кривые обеспечивают представление, которое значительно более разрежено, чем другие вейвлет-преобразования. Это можно оценить количественно, рассмотрев наилучшее приближение геометрического тестового изображения, которое можно представить, используя только $n$ вейвлеты и анализ ошибки аппроксимации как функции $n$. Для преобразования Фурье квадрат ошибки уменьшается только как $O(1/{\sqrt {n}})$. Для широкого спектра вейвлет-преобразований, включая как направленные, так и ненаправленные варианты, квадрат ошибки уменьшается как $O(1/n)$. Дополнительное предположение, лежащее в основе преобразования кривой, позволяет достичь $O({(\log n)}^{3}/{n^{2}})$.

Существуют эффективные численные алгоритмы для вычисления кривллета-преобразования дискретных данных. Вычислительные затраты на дискретные кривые преобразования, предложенные Candès et al. (Дискретное кривленое преобразование, основанное на неравномерно распределенных быстрых преобразованиях Фурье и на основе обертывания специально выбранных выборок Фурье) примерно в 6–10 раз больше, чем БПФ, и имеет ту же зависимость $O(n^{2}\log n)$ для изображения размера $n\times n$.

Конструкция кривеллета

Чтобы построить базовую кривую $\phi$ и обеспечить мозаику двумерного частотного пространства, следует руководствоваться двумя основными идеями:

1. Рассмотрим полярные координаты в частотной области
2. Постройте элементы кривой, локально поддерживаемые рядом с клиньями.

Количество клиньев $N_{j}=4\cdot 2^{\left\lceil {\frac {j}{2}}\right\rceil }$ в масштабе $2^{-j}$, т. е. удваивается в каждом втором круговом кольце.

Позволять ${\boldsymbol {\xi }}=\left(\xi _{1},\xi _{2}\right)^{T}$быть переменной в частотной области, и $r={\sqrt {\xi _{1}^{2}+\xi _{2}^{2}}},\omega =\arctan {\frac {\xi _{1}}{\xi _{2}}}$ быть полярными координатами в частотной области.

Мы используем анзац для расширенных основных кривых в полярных координатах:
${\hat {\phi }}_{j,0,0}:=2^{\frac {-3j}{4}}W(2^{-j}r){\tilde {V}}_{N_{j}}(\omega ),r\geq 0,\omega \in [0,2\pi ),j\in N_{0}$

Чтобы построить базовую кривую с компактной опорой вблизи «базового клина», два окна $W$ и ${\tilde {V}}_{N_{j}}$необходимо иметь компактную поддержку.Здесь мы можем просто взять $W(r)$ покрыть $(0,\infty )$с расширенными кривыми и ${\tilde {V}}_{N_{j}}$ такие, что каждое круговое кольцо покрыто трансляциями ${\tilde {V}}_{N_{j}}$ .

Тогда допустимость дает
$\sum _{j=-\infty }^{\infty }\left|W(2^{-j}r)\right|^{2}=1,r\in (0,\infty ).$ _{см. в разделе «Оконные функции». дополнительную информацию}

Для укладки круглого кольца в $N$ клинья, где $N$ — произвольное положительное целое число, нам нужно $2\pi$-периодическое неотрицательное окно ${\tilde {V}}_{N}$ с поддержкой внутри $\left[{\frac {-2\pi }{N}},{\frac {2\pi }{N}}\right]$ такой, что
$\sum _{l=0}^{N-1}{\tilde {V}}_{N}^{2}\left(\omega -{\frac {2\pi l}{N}}\right)=1$,
для всех $\omega \in \left[0,2\pi \right)$, ${\tilde {V}}_{N}$ можно просто построить как $2\pi$-периодизации масштабированного окна $V\left({\frac {N\omega }{2\pi }}\right)$.

Тогда следует, что
$\sum _{l=0}^{N_{j}-1}\left|2^{\frac {3j}{4}}{\hat {\phi }}_{j,0,0}\left(r,\omega -{\frac {2\pi l}{N_{j}}}\right)\right|^{2}=\left|W(2^{-j}r)\right|^{2}\sum _{l=0}^{N_{j}-1}{\tilde {V}}_{N_{j}}^{2}\left(\omega -{\frac {2\pi l}{N}}\right)=\left|W(2^{-j}r)\right|^{2}$

Для полного покрытия частотной плоскости, включая область вокруг нуля, нам необходимо определить элемент нижних частот.
${\hat {\phi }}_{-1}:=W_{0}(\left|\xi \right|)$ с
$W_{0}^{2}(r)^{2}:=1-\sum _{j=0}^{\infty }W(2^{-j}r)^{2}$
который поддерживается на единичной окружности и где мы не рассматриваем вращение.

Приложения

• Обработка изображений
• Сейсморазведка
• Гидравлическая механика
• PDE решение
• Сжатое зондирование

См. также

• Преобразование Банделе
• Преобразование чирплета
• Контурное преобразование
• Преобразование Френеле
• Шумовое преобразование
• Масштабировать пространство
• Преобразование Шерлета

Ссылки

• Э. Кандес и Д. Донохо, «Кривелики – удивительно эффективное неадаптивное представление объектов с краями». В: А. Коэн, К. Рабут и Л. Шумейкер, Редакторы, Кривые и подгонка поверхности : Сен-Мало, 1999, Издательство Университета Вандербильта, Нэшвилл (2000), стр. 105–120.
• Маджумдар Ангшул Бангла Базовое распознавание символов с использованием цифрового преобразования кривых. Журнал исследований в области распознавания образов ( JPRR ), Том 2. (1) 2007 стр. 17-26
• Эммануэль Кандес, Лоран Демане, Дэвид Донохо и Лексинг Инь. Быстрые дискретные кривые преобразования.
• Цзянвэй Ма, Герлинд Плонка , Преобразование кривой : журнал обработки сигналов IEEE, 2010, 27 (2), 118-133.
• Жан-Люк Старк, Эммануэль Дж. Кандес и Дэвид Л. Донохо, Преобразование кривой для шумоподавления изображений,: Транзакции IEEE по обработке изображений, Vol. 11, № 6, июнь 2002 г.

Внешние ссылки

• Домашняя страница Curvelet.org