В областях компьютерного зрения , анализа изображений и обработки сигналов понятие масштабно-пространственного представления используется для обработки данных измерений в нескольких масштабах и, в частности, для улучшения или подавления функций изображения в разных диапазонах масштабов (см. Статью о масштабном пространстве ) . Особый тип представления масштабного пространства обеспечивается гауссовым масштабным пространством, где данные изображения в N измерениях подвергаются сглаживанию с помощью гауссовой свертки.. Большая часть теории для пространства с гауссовым масштабом имеет дело с непрерывными изображениями, тогда как при реализации этой теории придется столкнуться с тем фактом, что большинство данных измерений являются дискретными. Следовательно, возникает теоретическая проблема относительно того, как дискретизировать непрерывную теорию, сохраняя или хорошо аппроксимируя желаемые теоретические свойства, которые приводят к выбору гауссова ядра (см. Статью об аксиомах масштабного пространства ). В этой статье описаны основные подходы для этого, которые были разработаны в литературе.
Масштабировать пространство | |
---|---|
Аксиомы масштабного пространства | |
Реализация масштабного пространства | |
Обнаружение функции | |
Обнаружение края | |
Обнаружение BLOB-объектов | |
Обнаружение углов | |
Обнаружение гребня | |
Обнаружение точки интереса | |
Выбор шкалы | |
Адаптация аффинной формы | |
Сегментация масштабного пространства | |
Постановка задачи
Гауссово масштаб пространство представление из двух величин N непрерывного сигнала n - мерных,
получается сверткой f C с N -мерным гауссовским ядром :
Другими словами:
Однако для реализации это определение непрактично, поскольку оно непрерывно. При применении концепции масштабного пространства к дискретному сигналу f D можно использовать разные подходы. Эта статья представляет собой краткое изложение некоторых из наиболее часто используемых методов.
Отделимость
Используя свойство отделимости гауссова ядра
N - мерный сверток операцию можно разложить на множество разъемных шагов сглаживания с одномерным гауссово ядром G вдоль каждой размерности
где
и стандартное отклонение гауссова σ связано с параметром масштаба t согласно t = σ 2 .
Во всем дальнейшем будет предполагаться разделимость, даже если ядро не совсем гауссово, поскольку разделение измерений является наиболее практичным способом реализации многомерного сглаживания, особенно в больших масштабах. Поэтому остальная часть статьи посвящена одномерному случаю.
Выбранное ядро Гаусса
При реализации шага одномерного сглаживания на практике, предположительно, самый простой подход состоит в свертке дискретного сигнала f D с дискретизированным гауссовым ядром :
где
(с t = σ 2 ), который, в свою очередь, обрезается на концах, чтобы получить фильтр с конечной импульсной характеристикой
для M, выбранного достаточно большим (см. функцию ошибок ), таким, что
Обычный выбор - установить M равным C, умноженному на стандартное отклонение гауссова ядра.
где C часто выбирают между 3 и 6.
Однако использование дискретизированного гауссовского ядра может привести к проблемам реализации, в частности, при вычислении производных более высокого порядка в более мелких масштабах путем применения дискретизированных производных гауссовых ядер. Когда точность и надежность являются основными критериями проектирования, следует рассмотреть альтернативные подходы к реализации.
Для малых значений ε (от 10 −6 до 10 −8 ) ошибки, вносимые усечением гауссиана, обычно незначительны. Однако для больших значений ε есть много лучших альтернатив прямоугольной оконной функции . Например, для заданного числа точек в окне Хэмминга , Blackman окна или окна Кайзера будет делать меньше повреждений спектральных и других свойств гауссовой , чем простое усечение будет. Несмотря на это, поскольку гауссово ядро быстро уменьшается на хвостах, основная рекомендация по-прежнему состоит в том, чтобы использовать достаточно малое значение ε, чтобы эффекты усечения больше не были важны.
Дискретное гауссово ядро
Более точный подход состоит в свертке исходного сигнала с дискретным гауссовым ядром T ( n , t ) [1] [2] [3]
где
а также обозначает модифицированные функции Бесселя целого порядка n . Это дискретный аналог непрерывного гауссиана в том смысле, что он является решением дискретного уравнения диффузии (дискретное пространство, непрерывное время), точно так же, как непрерывный гауссиан является решением уравнения непрерывной диффузии. [1] [2] [4]
Этот фильтр может быть усечен в пространственной области, как для дискретизированного гауссовского
или может быть реализован в области Фурье с использованием выражения в замкнутой форме для дискретного преобразования Фурье :
При таком подходе частотной области свойства масштабного пространства передаются точно в дискретную область или с отличным приближением с использованием периодического расширения и подходящего длинного дискретного преобразования Фурье для аппроксимации дискретного преобразования Фурье сглаживаемого сигнала. Более того, приближения производных высшего порядка могут быть вычислены прямым способом (и с сохранением свойств масштабного пространства) путем применения операторов центральной разности с малой опорой к представлению дискретного масштабного пространства . [5]
Как и в случае с дискретизированным гауссианом, простое усечение бесконечной импульсной характеристики в большинстве случаев будет достаточным приближением для малых значений ε, в то время как для больших значений ε лучше использовать либо разложение дискретного гауссиана на каскад обобщенные биномиальные фильтры или, альтернативно, построить конечное приближенное ядро путем умножения на оконную функцию . Если ε было выбрано слишком большим, так что эффекты ошибки усечения начинают проявляться (например, как ложные экстремумы или ложные ответы на операторы производной более высокого порядка), то можно уменьшить значение ε так, чтобы большее конечное ядро используется с вырезом там, где опора очень мала, или для использования сужающегося окна.
Рекурсивные фильтры
Поскольку вычислительная эффективность часто важна, рекурсивные фильтры низкого порядка часто используются для сглаживания масштабного пространства. Например, Янг и ван Влит [6] используют рекурсивный фильтр третьего порядка с одним действительным полюсом и парой комплексных полюсов, применяемый в прямом и обратном направлении, чтобы сделать симметричное приближение шестого порядка к гауссиану с низкой вычислительной сложностью для любого сглаживания. шкала.
Ослабив некоторые аксиомы, Линдеберг [1] пришел к выводу, что хорошими сглаживающими фильтрами будут «нормализованные частотные последовательности Полиа », семейство дискретных ядер, которое включает все фильтры с действительными полюсами в 0 < Z <1 и / или Z > 1. , а также с действительными нулями при Z <0. Для симметрии, которая приводит к приблизительной однородности направления, эти фильтры должны быть дополнительно ограничены парами полюсов и нулей, которые приводят к фильтрам с нулевой фазой.
Чтобы согласовать кривизну передаточной функции на нулевой частоте дискретного гауссиана, что обеспечивает приближенное полугрупповое свойство аддитивного t , два полюса на
может применяться вперед и назад для симметрии и устойчивости. Этот фильтр является простейшей реализацией ядра нормализованной частотной последовательности Полиа, которое работает для любого масштаба сглаживания, но он не является таким превосходным приближением к гауссову, как фильтр Янга и Ван Влиета, который не является нормализованной частотной последовательностью Полиа из-за своей сложной полюса.
Передаточная функция H 1 рекурсивного фильтра симметричной пары полюсов тесно связана с дискретным преобразованием Фурье дискретного гауссовского ядра через аппроксимацию первого порядка экспоненты:
где параметр t здесь связан с устойчивым положением полюса Z = p через:
Кроме того, такие фильтры с N парами полюсов, такие как две пары полюсов, показанные в этом разделе, являются еще лучшим приближением к экспоненте:
где стабильные положения полюсов регулируются путем решения:
Импульсные характеристики этих фильтров не очень близки к гауссовым, если не используется более двух пар полюсов. Однако даже с одной или двумя парами полюсов на шкалу сигнал, последовательно сглаженный с увеличением масштабов, будет очень близок к сглаженному по Гауссу сигналу. Если используется слишком мало пар полюсов, свойство полугруппы аппроксимируется плохо.
Эти фильтры по-прежнему удовлетворяют следующие аксиомы масштабного пространства :
- линейность
- инвариантность сдвига (целочисленные сдвиги)
- отсутствие локальных экстремумов (нулевых переходов) в одном измерении
- отсутствие усиления локальных экстремумов в любом количестве измерений
- позитивность
- нормализация
Следующие условия выполняются лишь приблизительно, причем приближение лучше для большего числа пар полюсов:
- существование инфинитезимального генератора A (бесконечно малый генератор дискретного гауссиана или приближающий его фильтр, приблизительно отображает рекурсивный отклик фильтра на один из бесконечно больших t )
- структура полугруппы с соответствующим свойством каскадного сглаживания (это свойство аппроксимируется рассмотрением ядер как эквивалентных, когда они имеют одинаковое значение t , даже если они не совсем равны)
- вращательная симметрия
- масштабная инвариантность
Этот метод рекурсивного фильтра и его варианты для вычисления как гауссовского сглаживания, так и гауссовских производных были описаны несколькими авторами. [6] [7] [8] [9] Тан и др. проанализировали и сравнили некоторые из этих подходов и указали, что фильтры Янга и Ван Влита представляют собой каскад (умножение) прямых и обратных фильтров, в то время как Deriche и Jin et al. фильтры - это сумма прямых и обратных фильтров. [10]
При малых масштабах подход рекурсивной фильтрации, а также другие подходы с разделением не гарантируют наилучшего приближения к вращательной симметрии, поэтому в качестве альтернативы можно рассматривать неразделимые реализации для 2D-изображений.
При одновременном вычислении нескольких производных в N-струе дискретное сглаживание в масштабном пространстве с дискретным аналогом гауссова ядра или с приближением рекурсивного фильтра, за которым следуют операторы малых опорных разностей, может быть как быстрее, так и точнее, чем вычисление рекурсивных приближений. каждого производного оператора.
Сглаживание с конечной импульсной характеристикой (FIR)
Для небольших масштабов КИХ-фильтр низкого порядка может быть лучшим сглаживающим фильтром, чем рекурсивный фильтр. Симметричное 3-ядро [ t / 2, 1- t , t / 2] для t ≤ 0,5 сглаживается до масштаба t, используя пару действительных нулей при Z <0, и приближается к дискретному гауссову в пределе малых т . Фактически, при бесконечно малом t либо этот фильтр с двумя нулями, либо двухполюсный фильтр с полюсами при Z = t / 2 и Z = 2 / t может использоваться в качестве бесконечно малого генератора для дискретных гауссовских ядер, описанных выше.
Нули КИХ-фильтра могут быть объединены с полюсами рекурсивного фильтра для создания общего высококачественного сглаживающего фильтра. Например, если процесс сглаживания заключается в том, чтобы всегда применять биквадратный (двухполюсный, два нуля) фильтр вперед, а затем назад к каждой строке данных (и к каждому столбцу в 2D случае), полюса и нули могут выполнять часть сглаживания. Нули ограничиваются t = 0,5 на пару (нули при Z = –1), поэтому для больших масштабов полюса делают большую часть работы. В более мелких масштабах комбинация дает отличное приближение к дискретному гауссову, если полюса и нули каждый делают примерно половину сглаживания. Значения t для каждой части сглаживания (полюса, нули, множественные приложения вперед и назад и т. Д.) Являются аддитивными в соответствии с приблизительным свойством полугруппы.
Передаточная функция КИХ-фильтра тесно связана с дискретным гауссовским ДВПФ, как и рекурсивный фильтр. Для одной пары нулей передаточная функция равна
где параметр t здесь связан с нулевыми положениями Z = z через:
и нам требуется t ≤ 0,5, чтобы передаточная функция оставалась неотрицательной.
Кроме того, такие фильтры с N парами нулей являются еще лучшим приближением к экспоненте и распространяются на более высокие значения t :
где стабильные нулевые положения настраиваются путем решения:
Эти КИХ-фильтры и фильтры с нулевым полюсом являются действительными ядрами масштабного пространства, удовлетворяющими тем же аксиомам, что и все полюсные рекурсивные фильтры.
Реализация в реальном времени в пирамидах и дискретная аппроксимация масштабно-нормированных производных
Что касается автоматического выбора масштаба на основе нормализованных производных, аппроксимации пирамиды часто используются для получения производительности в реальном времени. [11] [12] [13] Уместность аппроксимации операций масштабного пространства внутри пирамиды проистекает из того факта, что повторное каскадное сглаживание с обобщенными биномиальными ядрами приводит к эквивалентным ядрам сглаживания, которые при разумных условиях приближаются к гауссову. Кроме того, биномиальное ядро (или в более общем случае класс обобщенных биномиальных ядер) можно показать , представляет собой уникальный класс конечно-поддержки ядер , которые гарантируют Невозникновение локальных экстремумов или нулевых пересечений с увеличением масштаба (см статьи на несколько -масштабно подходит к деталям). Однако может потребоваться особая осторожность, чтобы избежать артефактов дискретизации.
Другие многомасштабные подходы
Для одномерных ядер существует хорошо разработанная теория многомасштабных подходов , касающихся фильтров, которые не создают новых локальных экстремумов или новых переходов через ноль с увеличением масштабов. Для непрерывных сигналов фильтры с действительными полюсами на s- плоскости относятся к этому классу, в то время как для дискретных сигналов вышеописанные рекурсивные и КИХ-фильтры удовлетворяют этим критериям. В сочетании со строгим требованием непрерывной полугрупповой структуры, непрерывный гауссовский и дискретный гауссовский представляют собой уникальный выбор для непрерывных и дискретных сигналов.
Существует множество других методов многомасштабной обработки сигналов, обработки изображений и сжатия данных с использованием вейвлетов и множества других ядер, которые не используют или не требуют тех же требований, что и описания масштабного пространства ; то есть они не зависят от более грубого масштаба, не генерируя новый экстремум, который не присутствовал в более мелком масштабе (в 1D), или от отсутствия усиления локальных экстремумов между соседними масштабными уровнями (в любом количестве измерений).
Смотрите также
- Масштабировать пространство
- Пирамида (обработка изображений)
- Многомасштабные подходы
- Гауссов фильтр
Рекомендации
- ^ a b c Линдеберг, Т., "Масштабное пространство для дискретных сигналов", ПАМИ (12), № 3, март 1990 г., стр. 234–254.
- ^ a b Линдеберг, Т., Теория масштабного пространства в компьютерном зрении, Kluwer Academic Publishers, 1994 , ISBN 0-7923-9418-6
- ^ Р. А. Хаддад и А. Н. Акансу, " Класс быстрых гауссовских биномиальных фильтров для обработки речи и изображений" , "Транзакции IEEE по акустике, речи и обработке сигналов", вып. 39, стр. 723-727, март 1991 г.
- ^ Кэмпбелл, Дж., 2007, Модель SMM как краевая задача с использованием уравнения дискретной диффузии , Theor Popul Biol. 2007 декабрь; 72 (4): 539-46.
- ^ Линдеберг, Т. Аппроксимации дискретной производной со свойствами масштабного пространства: основа для выделения признаков низкого уровня, J. of Mathematical Imaging and Vision, 3 (4), стр. 349--376, 1993.
- ^ а б Ян Т. Янг и Лукас Дж. Ван Влит (1995). «Рекурсивная реализация фильтра Гаусса» . Обработка сигналов . 44 (2): 139–151. CiteSeerX 10.1.1.12.2826 . DOI : 10.1016 / 0165-1684 (95) 00020-E .
- ^ Deriche, R: Рекурсивная реализация гауссианы и ее производных, Отчет об исследовании INRIA 1893, 1993.
- ^ Ричард Ф. Лайон. «Распознавание речи в масштабном пространстве», Тр. 1987 ICASSP. Сан-Диего, март, стр. 29.3.14, 1987.
- ^ Jin, JS, Gao Y. "Рекурсивная реализация фильтрации LoG". Визуализация в реальном времени 1997; 3: 59–65.
- ^ .Совира Тан; Джейсон Л. Дейл и Алан Джонстон (2003). «Выполнение трех рекурсивных алгоритмов быстрой пространственно-вариативной гауссовой фильтрации». Визуализация в реальном времени . Vol. 9 нет. 3. С. 215–228. DOI : 10.1016 / S1077-2014 (03) 00040-8 .
- ^ Линдеберг, Тони и Бретцнер, Ларс (2003). Выбор масштаба в реальном времени в гибридных многомасштабных представлениях . Proc. Scale-Space'03, Конспект лекций по информатике . Конспект лекций по информатике. 2695 . С. 148–163. DOI : 10.1007 / 3-540-44935-3_11 . ISBN 978-3-540-40368-5.
- ^ Кроули, J, Рифф O: Быстрое вычисление масштабно нормализованных гауссовских рецептивных полей, Proc. Scale-Space'03, Остров Скай, Шотландия, Springer Lecture Notes in Computer Science, volume 2695, 2003.
- ^ Лоу, Д.Г., «Отличительные особенности изображения от масштабно-инвариантных ключевых точек», Международный журнал компьютерного зрения, 60, 2, стр. 91-110, 2004.