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

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

Постановка проблемы

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

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

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

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

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

${\displaystyle 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 можно использовать различные подходы. В этой статье кратко изложены некоторые из наиболее часто используемых методов.

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

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

${\displaystyle 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 вдоль каждого измерения

${\displaystyle 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},}$

где

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

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

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

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

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

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

где

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

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

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

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

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

Обычным выбором является установка M на константу C, умноженную на стандартное отклонение гауссовского ядра.

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

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

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

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

Дискретное гауссовское ядро

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

Более совершенный подход заключается в свертке исходного сигнала с дискретным гауссовым ядром T ( n , t ) ^{[2] [3] [4]}

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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 через:

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

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

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

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

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

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

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

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

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

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

Этот метод рекурсивной фильтрации и его вариации для вычисления как гауссовского сглаживания, так и гауссовых производных были описаны несколькими авторами. ^{[7] [8] [9] [10]} Тан и др. проанализировали и сравнили некоторые из этих подходов и указали, что фильтры Юнга и Ван Влита представляют собой каскад (умножение) прямых и обратных фильтров, в то время как фильтры Дериша и Джина и др. представляют собой суммы прямых и обратных фильтров. ^[11]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что касается темы автоматического выбора масштаба на основе нормализованных производных, то для получения производительности в реальном времени часто используются пирамидальные аппроксимации . ^{[12] [13] [14]} Уместность аппроксимации операций масштабного пространства в пирамиде проистекает из того факта, что повторное каскадное сглаживание с обобщенными биномиальными ядрами приводит к эквивалентным сглаживающим ядрам, которые при разумных условиях приближаются к гауссовским. Более того, можно показать, что биномиальные ядра (или, в более общем смысле, класс обобщенных биномиальных ядер) составляют уникальный класс ядер с конечным носителем, которые гарантируют отсутствие создания локальных экстремумов или нулевых пересечений с увеличением масштаба (подробнее см. статью о многомасштабных подходах ). Однако может потребоваться особая осторожность, чтобы избежать артефактов дискретизации.

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

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

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

Смотрите также

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

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

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

Ссылки

1. Линдеберг, Т., «Дискретные аппроксимации гауссовского сглаживания и гауссовских производных», Журнал математической визуализации и зрения, 66(5): 759–800, 2024.
2. Линдеберг, Т., «Масштабное пространство для дискретных сигналов», PAMI(12), № 3, март 1990 г., стр. 234-254.
3. Lindeberg, T., Теория масштабного пространства в компьютерном зрении, Kluwer Academic Publishers, 1994, ISBN  0-7923-9418-6
4. RA Haddad и AN Akansu, «Класс быстрых гауссовых биномиальных фильтров для обработки речи и изображений», IEEE Transactions on Acoustics, Speech, and Signal Processing, т. 39, стр. 723-727, март 1991 г.
5. Кэмпбелл, Дж., 2007, Модель SMM как граничная задача с использованием дискретного уравнения диффузии , Theor Popul Biol. 2007 Декабрь;72(4):539-46.
6. Линдеберг, Т. Дискретные производные аппроксимации со свойствами масштабного пространства: основа для извлечения низкоуровневых признаков, J. of Mathematical Imaging and Vision, 3(4), стр. 349--376, 1993.
7. Ian T. Young & Lucas J. van Vliet (1995). "Рекурсивная реализация фильтра Гаусса". Обработка сигналов . 44 (2): 139–151. Bibcode :1995SigPr..44..139Y. CiteSeerX 10.1.1.12.2826 . doi :10.1016/0165-1684(95)00020-E. 
8. Дериш, Р.: Рекурсивная реализация гауссианы и ее производных, Исследовательский отчет INRIA 1893, 1993.
9. Ричард Ф. Лион. «Распознавание речи в масштабном пространстве», Труды ICASSP 1987 г. Сан-Диего, март, стр. 29.3.14, 1987 г.
10. Jin, JS, Gao Y. «Рекурсивная реализация фильтрации LoG». Real-Time Imaging 1997;3:59–65.
11. . Совира Тан; Джейсон Л. Дейл и Алан Джонстон (2003). «Производительность трех рекурсивных алгоритмов для быстрой пространственно-вариантной гауссовой фильтрации». Real-Time Imaging . Том 9, № 3. С. 215–228. doi :10.1016/S1077-2014(03)00040-8.
12. Линдеберг, Тони и Бретцнер, Ларс (2003). «Выбор масштаба в реальном времени в гибридных многомасштабных представлениях». Методы масштабного пространства в компьютерном зрении. Конспект лекций по информатике. Том 2695. Proc. Scale-Space'03, Springer Lecture Notes по информатике. С. 148–163. doi :10.1007/3-540-44935-3_11. ISBN 978-3-540-40368-5.
13. Кроули, Дж., Рифф О.: Быстрое вычисление масштабно-нормализованных гауссовых рецептивных полей, Proc. Scale-Space'03, остров Скай, Шотландия, Springer Lecture Notes in Computer Science, том 2695, 2003.
14. Лоу, Д.Г., «Отличительные особенности изображения по масштабно-инвариантным ключевым точкам», Международный журнал компьютерного зрения, 60, 2, стр. 91-110, 2004.