Масштабирование пространственной реализации

Масштабировать пространство
Аксиомы масштабного пространства
Масштабирование пространственной реализации
Обнаружение функций
Обнаружение края
Обнаружение больших двоичных объектов
Обнаружение углов
Обнаружение гребня
Обнаружение точек интереса
Выбор масштаба
Аффинная адаптация формы
Масштабно-пространственная сегментация

В областях компьютерного зрения , анализа изображений и обработки сигналов понятие представления в масштабном пространстве используется для обработки данных измерений в нескольких масштабах и, в частности, для улучшения или подавления характеристик изображения в разных диапазонах масштаба (см. статью о масштабном пространстве ). . Особый тип представления в масштабном пространстве обеспечивается гауссовским масштабным пространством, где данные изображения в N измерениях подвергаются сглаживанию с помощью гауссовой свертки . Большая часть теории пространства гауссовского масштаба связана с непрерывными изображениями, тогда как при реализации этой теории придется столкнуться с тем фактом, что большинство данных измерений дискретны. Следовательно, возникает теоретическая проблема относительно того, как дискретизировать непрерывную теорию, сохраняя или хорошо аппроксимируя желаемые теоретические свойства, которые приводят к выбору гауссова ядра (см. статью об аксиомах масштабного пространства ). В данной статье описаны основные подходы для этого, разработанные в литературе, см. также за углубленное рассмотрение темы аппроксимации операции гауссовского сглаживания и вычислений производной Гаусса в теории масштабного пространства.

Постановка задачи

гауссовском непрерывного сигнала в масштабе - мерного Представление N ,

$f_{C}\left(x_{1},\cdots ,x_{N},t\right),$

получается путем свертки f _C с N -мерным гауссовским ядром :

$g_{N}\left(x_{1},\cdots ,x_{N},t\right).$

Другими словами:

$L\left(x_{1},\cdots ,x_{N},t\right)=\int _{u_{1}=-\infty }^{\infty }\cdots \int _{u_{N}=-\infty }^{\infty }f_{C}\left(x_{1}-u_{1},\cdots ,x_{N}-u_{N},t\right)\cdot g_{N}\left(u_{1},\cdots ,u_{N},t\right)\,du_{1}\cdots du_{N}.$

Однако для реализации это определение непрактично, поскольку оно непрерывно. При применении концепции масштабного пространства к дискретному сигналу f _D можно использовать разные подходы. Эта статья представляет собой краткое изложение некоторых наиболее часто используемых методов.

Разделимость

Используя свойство отделимости ядра Гаусса

$g_{N}\left(x_{1},\dots ,x_{N},t\right)=G\left(x_{1},t\right)\cdots G\left(x_{N},t\right)$

N -мерную . операцию свертки можно разложить на набор разделимых шагов сглаживания с одномерным гауссовым ядром G вдоль каждого измерения

$L(x_{1},\cdots ,x_{N},t)=\int _{u_{1}=-\infty }^{\infty }\cdots \int _{u_{N}=-\infty }^{\infty }f_{C}(x_{1}-u_{1},\cdots ,x_{N}-u_{N},t)G(u_{1},t)\,du_{1}\cdots G(u_{N},t)\,du_{N},$

где

$G(x,t)={\frac {1}{\sqrt {2\pi t}}}e^{-{\frac {x^{2}}{2t}}}$

а стандартное отклонение гауссова σ связано с параметром масштаба t согласно t = σ ² .

Во всем дальнейшем будет предполагаться разделимость, даже если ядро ​​не совсем гауссово, поскольку разделение измерений является наиболее практичным способом реализации многомерного сглаживания, особенно в больших масштабах. Поэтому остальная часть статьи посвящена одномерному случаю.

Выборочное гауссово ядро

При реализации этапа одномерного сглаживания на практике, по-видимому, самым простым подходом является свертка дискретного сигнала f _D с дискретным гауссовским ядром :

$L(x,t)=\sum _{n=-\infty }^{\infty }f(x-n)\,G(n,t)$

где

$G(n,t)={\frac {1}{\sqrt {2\pi t}}}e^{-{\frac {n^{2}}{2t}}}$

(при t = σ ² ), который, в свою очередь, обрезается на концах, чтобы получить фильтр с конечной импульсной характеристикой.

$L(x,t)=\sum _{n=-M}^{M}f(x-n)\,G(n,t)$

для M выбрано достаточно большое (см. функцию ошибок ) такое, что

$2\int _{M}^{\infty }G(u,t)\,du=2\int _{\frac {M}{\sqrt {t}}}^{\infty }G(v,1)\,dv<\varepsilon .$

Распространенный выбор — установить M равным константе C , умноженной на стандартное отклонение ядра Гаусса.

$M=C\sigma +1=C{\sqrt {t}}+1$

где C часто выбирается где-то между 3 и 6.

Однако использование выборочного ядра Гаусса может привести к проблемам реализации, в частности, при вычислении производных более высокого порядка в более мелких масштабах с применением выборочных производных гауссовских ядер. Поэтому, когда точность и надежность являются основными критериями проектирования, следует рассмотреть альтернативные подходы к реализации.

Для малых значений ε (10 ⁻⁶ до 10 ⁻⁸ ) ошибки, вносимые усечением гауссиана, обычно незначительны. Однако для больших значений ε существует множество лучших альтернатив прямоугольной оконной функции . Например, для заданного количества точек окно Хэмминга , окно Блэкмана или окно Кайзера нанесет меньший ущерб спектральным и другим свойствам гауссианы, чем простое усечение. Несмотря на это, поскольку ядро ​​Гаусса быстро убывает на хвостах, основная рекомендация по-прежнему состоит в том, чтобы использовать достаточно малое значение ε, чтобы эффекты усечения больше не были важны.

Дискретное ядро ​​Гаусса

Идеальное дискретное гауссово ядро ​​(сплошное) в сравнении с выбранным обычным гауссовским ядром (пунктирное) для масштабов t = [0,5, 1, 2, 4]

Более усовершенствованный подход состоит в свертке исходного сигнала с дискретным ядром Гаусса T ( n , t )

$L(x,t)=\sum _{n=-\infty }^{\infty }f(x-n)\,T(n,t)$

где

$T(n,t)=e^{-t}I_{n}(t)$

и $I_{n}(t)$ обозначает модифицированные функции Бесселя целого порядка n . Это дискретный аналог непрерывного гауссиана в том смысле, что он является решением дискретного уравнения диффузии (дискретное пространство, непрерывное время), точно так же, как непрерывный гауссиан является решением непрерывного уравнения диффузии.

Этот фильтр может быть усечен в пространственной области, как и для выборочного гауссова

$L(x,t)=\sum _{n=-M}^{M}f(x-n)\,T(n,t)$

или может быть реализовано в области Фурье с использованием выражения в замкнутой форме для преобразования Фурье с дискретным временем :

${\widehat {T}}(\theta ,t)=\sum _{n=-\infty }^{\infty }T(n,t)\,e^{-i\theta n}=e^{t(\cos \theta -1)}.$

При таком подходе в частотной области свойства масштабного пространства передаются точно в дискретную область или с превосходной аппроксимацией с использованием периодического расширения и достаточно длинного дискретного преобразования Фурье для аппроксимации преобразования Фурье дискретного времени сглаживаемого сигнала. Более того, аппроксимации производной более высокого порядка могут быть вычислены простым способом (с сохранением свойств масштабного пространства), применяя малые опорные операторы центральной разности к представлению в дискретном масштабном пространстве .

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

Рекурсивные фильтры

Ядра масштабного пространства. Идеальный дискретный гауссиан, основанный на функциях Бесселя (красный) и двухполюсных парных рекурсивных сглаживающих фильтрах вперед/назад (синий) с полюсами, как описано в тексте. Вверху показаны отдельные ядра, а внизу — их совокупная свертка друг с другом; т = [0,5, 1, 2, 4].

Поскольку эффективность вычислений часто важна, рекурсивные фильтры для сглаживания в масштабном пространстве часто используются низкого порядка. Например, Янг и ван Влит. используйте рекурсивный фильтр третьего порядка с одним действительным полюсом и парой комплексных полюсов, применяемых вперед и назад, чтобы сделать симметричное приближение шестого порядка к гауссиане с низкой вычислительной сложностью для любого масштаба сглаживания.

Ослабляя некоторые аксиомы, Линдеберг пришел к выводу, что хорошими сглаживающими фильтрами будут «нормализованные последовательности частот Полиа », семейство дискретных ядер, включающее все фильтры с действительными полюсами при 0 < Z <1 и/или Z > 1, а также с действительными нулями при Z <0. Для симметрии, которая приводит к приблизительной направленной однородности, эти фильтры должны быть дополнительно ограничены парами полюсов и нулей, что приводит к фильтрам с нулевой фазой.

Чтобы согласовать кривизну передаточной функции на нулевой частоте дискретной гауссианы, что обеспечивает приближенное полугрупповое свойство добавки t , два полюса на

$Z=1+{\frac {2}{t}}-{\sqrt {\left(1+{\frac {2}{t}}\right)^{2}-1}}$

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

Передаточная функция H ₁ симметричного рекурсивного фильтра с парой полюсов тесно связана с преобразованием Фурье дискретного времени дискретного ядра Гаусса посредством аппроксимации экспоненты первого порядка:

${\widehat {T}}(\theta ,t)={\frac {1}{e^{t(1-\cos \theta )}}}\approx {\frac {1}{1+t(1-\cos \theta )}}=H_{1}(\theta ,t),$

где параметр t здесь связан со стабильным положением полюса Z = p посредством:

$t={\frac {2p}{(1-p)^{2}}}.$

Более того, такие фильтры с N парами полюсов, такие как две пары полюсов, показанные в этом разделе, являются еще лучшим приближением к экспоненте:

${\frac {1}{\left(1+{\frac {t}{N}}(1-\cos \theta )\right)^{N}}}=H_{N}(\theta ,t),$

где устойчивые поул-позиции корректируются путем решения:

${\frac {t}{N}}={\frac {2p}{(1-p)^{2}}}.$

Импульсные характеристики этих фильтров не очень близки к гауссовым, если не используется более двух пар полюсов. Однако даже при наличии только одной или двух пар полюсов на шкалу сигнал, последовательно сглаживаемый при увеличении масштаба, будет очень близок к сигналу, сглаженному по Гауссу. Свойство полугруппы плохо аппроксимируется, когда используется слишком мало пар полюсов.

Аксиомы масштабного пространства , которым по-прежнему удовлетворяют эти фильтры:

• линейность
• сдвиговая инвариантность (целочисленные сдвиги)
• отсутствие создания локальных экстремумов (переходов через нуль) в одном измерении
• отсутствие усиления локальных экстремумов в любом количестве измерений
• позитивность
• нормализация

Следующие условия выполняются лишь приблизительно, причем приближение лучше для большего числа пар полюсов:

• существование бесконечно малого генератора A (бесконечно малый генератор дискретной гауссианы или аппроксимирующий его фильтр приблизительно отображает отклик рекурсивного фильтра на один из бесконечно больших t )
• структура полугруппы с соответствующим свойством каскадного сглаживания (это свойство аппроксимируется, если ядра считаются эквивалентными, когда они имеют одинаковое значение t , даже если они не совсем равны)
• вращательная симметрия
• масштабная инвариантность

Этот метод рекурсивной фильтрации и его варианты для вычисления как гауссовского сглаживания, так и гауссовских производных были описаны несколькими авторами. Тан и др. проанализировали и сравнили некоторые из этих подходов и отметили, что фильтры Янга и Ван Влита представляют собой каскад (умножение) прямых и обратных фильтров, в то время как фильтры Дериша и Джина и др. фильтры представляют собой суммы прямых и обратных фильтров.

В мелких масштабах подход рекурсивной фильтрации, а также другие разделимые подходы не гарантируют наилучшего приближения к вращательной симметрии, поэтому неразделимые реализации для 2D-изображений могут рассматриваться как альтернатива.

При одновременном вычислении нескольких производных в N-струе дискретное сглаживание в масштабном пространстве с помощью дискретного аналога ядра Гаусса или с помощью аппроксимации рекурсивного фильтра, за которым следуют небольшие операторы разности опор, может быть быстрее и точнее, чем вычисление рекурсивных аппроксимаций. каждого производного оператора.

Сглаживатели с конечной импульсной характеристикой (FIR)

низкого порядка Для небольших масштабов КИХ-фильтр может быть лучшим сглаживающим фильтром, чем рекурсивный фильтр. Симметричное 3-ядро [ t /2, 1- t , t /2] для t ≤ 0,5 сглаживается до масштаба t с использованием пары действительных нулей при Z < 0 и приближается к дискретному гауссову в пределе малых т . Фактически, при бесконечно малом t либо этот двухнулевой фильтр, либо двухполюсный фильтр с полюсами при Z = t /2 и Z = 2/ t можно использовать в качестве бесконечно малого генератора для дискретных гауссовских ядер, описанных выше.

Нули КИХ-фильтра можно объединить с полюсами рекурсивного фильтра, чтобы получить общий высококачественный сглаживающий фильтр. Например, если процесс сглаживания всегда применяет биквадратичный (двухполюсный, два нуля) фильтр вперед, а затем назад к каждой строке данных (и к каждому столбцу в двумерном случае), каждый полюс и нули могут выполнять часть сглаживания. Нули ограничиваются при t = 0,5 на пару (нули при Z = –1), поэтому в больших масштабах большую часть работы выполняют полюса. В более мелких масштабах эта комбинация дает превосходное приближение к дискретной гауссиане, если каждый из полюсов и нулей выполняет примерно половину сглаживания. Значения t для каждой части сглаживания (полюсы, нули, множественные применения вперед и назад и т. д.) являются аддитивными в соответствии со свойством аппроксимированной полугруппы.

Расположение на плоскости Z четырех полюсов (X) и четырех нулей (кругов) для сглаживающего фильтра, использующего прямой/обратный биквадрат для сглаживания до масштаба t = 2, с половиной сглаживания от полюсов и половиной от нулей. Все нули находятся в точке Z = –1; полюса находятся при Z = 0,172 и Z = 5,83. Полюса за пределами единичного круга реализуются путем обратной фильтрации с помощью стабильных полюсов.

Передаточная функция КИХ-фильтра тесно связана с дискретным гауссовым DTFT, так же, как и рекурсивный фильтр. Для одной пары нулей передаточная функция равна

${\widehat {T}}(\theta ,t)=e^{-t(1-\cos \theta )}\approx {1-t(1-\cos \theta )}=F_{1}(\theta ,t),$

где параметр t здесь связан с нулевыми положениями Z = z посредством:

$t=-{\frac {2z}{(1-z)^{2}}},$

и нам требуется t ≤ 0,5, чтобы передаточная функция оставалась неотрицательной.

Более того, такие фильтры с N парами нулей являются еще лучшим приближением к экспоненте и распространяются на более высокие значения t :

$\left(1-{\frac {t}{N}}(1-\cos \theta )\right)^{N}=F_{N}(\theta ,t),$

где устойчивые нулевые положения корректируются путем решения:

${\frac {t}{N}}=-{\frac {2z}{(1-z)^{2}}}.$

Эти КИХ-фильтры и фильтры с нулевым полюсом являются действительными ядрами масштабного пространства, удовлетворяющими тем же аксиомам, что и всеполюсные рекурсивные фильтры.

Реализация в реальном времени в рамках пирамид и дискретная аппроксимация нормализованных по масштабу производных

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

Другие многомасштабные подходы

Для одномерных ядер существует хорошо разработанная теория многомасштабных подходов , касающаяся фильтров, которые не создают новых локальных экстремумов или новых пересечений нуля с возрастающими масштабами. Для непрерывных сигналов к этому классу относятся фильтры с действительными полюсами в s -плоскости, тогда как для дискретных сигналов этим критериям удовлетворяют описанные выше рекурсивные и КИХ-фильтры. В сочетании со строгим требованием непрерывной полугрупповой структуры непрерывный гауссиан и дискретный гауссиан представляют собой уникальный выбор для непрерывных и дискретных сигналов.

Существует множество других методов многомасштабной обработки сигналов, обработки изображений и сжатия данных с использованием вейвлетов и множества других ядер, которые не используют и не требуют тех же требований , что и масштабного пространства описания ; то есть они не зависят от более грубого масштаба, не создавая нового экстремума, которого не было в более мелком масштабе (в 1D), или от отсутствия усиления локальных экстремумов между соседними уровнями масштаба (в любом количестве измерений).

См. также

• Масштабировать пространство
• Пирамида (обработка изображений)
• Многомасштабные подходы
• Гауссов фильтр

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

• pyscsp: набор инструментов масштабного пространства для Python на GitHub (включая реализации различных методов аппроксимации гауссовского сглаживания для дискретных данных).