WikiDer > Реализация масштабного пространства
В областях компьютерное зрение, анализ изображений и обработка сигналовпонятие масштабно-пространственного представления используется для обработки данных измерений в нескольких масштабах и, в частности, для улучшения или подавления функций изображения в разных диапазонах масштабов (см. статью о масштабное пространство). Особый тип представления масштабного пространства обеспечивается масштабным пространством Гаусса, где данные изображения в N размеров подвергается сглаживанию по Гауссу свертка. Большая часть теории для пространства с гауссовым масштабом имеет дело с непрерывными изображениями, тогда как при реализации этой теории придется столкнуться с тем фактом, что большинство данных измерений являются дискретными. Следовательно, возникает теоретическая проблема относительно того, как дискретизировать непрерывную теорию при сохранении или хорошей аппроксимации желаемых теоретических свойств, которые приводят к выбору гауссова ядра (см. Статью о аксиомы масштабного пространства). В этой статье описаны основные подходы для этого, разработанные в литературе.
Постановка задачи
В Гауссовский представление в масштабном пространстве из N-размерный непрерывный сигнал,
получается свертывание жC с N-размерный Гауссово ядро:
Другими словами:
Однако для выполнение, это определение непрактично, поскольку оно непрерывно. При применении концепции масштабного пространства к дискретному сигналу жDможно использовать разные подходы. Эта статья представляет собой краткое изложение некоторых из наиболее часто используемых методов.
Отделимость
С использованием свойство отделимости гауссова ядра
то N-размерный свертка операция может быть разложена на набор разделимых шагов сглаживания с одномерным гауссовым ядром грамм по каждому измерению
куда
а стандартное отклонение гауссовой σ связано с параметром масштаба т в соответствии с т = σ2.
Во всем дальнейшем будет предполагаться разделимость, даже если ядро не совсем гауссово, поскольку разделение измерений является наиболее практичным способом реализации многомерного сглаживания, особенно в больших масштабах. Следовательно, остальная часть статьи посвящена одномерному случаю.
Выбранное ядро Гаусса
При реализации шага одномерного сглаживания на практике, предположительно, самый простой подход состоит в том, чтобы свернуть дискретный сигнал жD с выбранное ядро Гаусса:
куда
(с т = σ2), который, в свою очередь, обрезается на концах, чтобы получить фильтр с конечной импульсной характеристикой
за M выбран достаточно большим (см. функция ошибки) такие, что
Обычный выбор - установить M к постоянному C умноженное на стандартное отклонение гауссова ядра
куда C часто выбирают между 3 и 6.
Однако использование дискретизированного гауссовского ядра может привести к проблемам реализации, в частности, при вычислении производных более высокого порядка в более мелких масштабах путем применения дискретизированных производных гауссовских ядер. Когда точность и надежность являются основными критериями проектирования, следует рассмотреть альтернативные подходы к реализации.
При малых значениях ε (10−6 до 10−8) ошибки, вносимые усечением гауссиана, обычно незначительны. Однако для больших значений ε есть много лучших альтернатив прямоугольному оконная функция. Например, для заданного количества точек Окно Хэмминга, Окно Блэкмана, или же Окно Кайзера нанесет меньший ущерб спектральным и другим свойствам гауссианы, чем простое усечение. Несмотря на это, поскольку гауссово ядро быстро уменьшается на хвостах, основная рекомендация по-прежнему состоит в том, чтобы использовать достаточно малое значение ε, чтобы эффекты усечения больше не были важны.
Дискретное гауссово ядро
Более совершенный подход состоит в свертке исходного сигнала с дискретное гауссово ядро Т(п, т)[1][2][3]
куда
и обозначает модифицированные функции Бесселя целочисленного порядка, п. Это дискретный аналог непрерывного гауссиана в том смысле, что он является решением дискретной уравнение диффузии (дискретное пространство, непрерывное время), точно так же, как непрерывный гауссиан является решением уравнения непрерывной диффузии.[1][2][4]
Этот фильтр может быть усечен в пространственной области, как для дискретизированного гауссова
или может быть реализован в области Фурье с использованием выражения в закрытой форме для его преобразование Фурье с дискретным временем:
При таком подходе в частотной области свойства масштабного пространства передаются точно к дискретной области или с отличным приближением с использованием периодического расширения и подходящей длины дискретное преобразование Фурье приблизить преобразование Фурье с дискретным временем сглаживаемого сигнала. Более того, приближения производных высшего порядка могут быть вычислены прямым способом (и с сохранением свойств масштабного пространства) путем применения операторов центральной разности с малой опорой к дискретным представление масштабного пространства.[5]
Как и в случае с дискретизированным гауссианом, простое усечение бесконечной импульсной характеристики в большинстве случаев будет достаточным приближением для малых значений ε, в то время как для больших значений ε лучше использовать либо разложение дискретного гауссиана на каскад обобщенные биномиальные фильтры или, альтернативно, построить конечное приближенное ядро путем умножения на оконная функция. Если ε было выбрано слишком большим, так что эффекты ошибки усечения начинают проявляться (например, как ложные экстремумы или ложные ответы на операторы производной более высокого порядка), то можно уменьшить значение ε так, чтобы конечное ядро большего размера используется с вырезом там, где опора очень мала, или для использования конического окна.
Рекурсивные фильтры
Поскольку часто важна эффективность вычислений, рекурсивные фильтры часто используются для сглаживания масштабного пространства. Например, Янг и ван Влит[6] используйте рекурсивный фильтр третьего порядка с одним действительным полюсом и парой комплексных полюсов, применяемый в прямом и обратном направлении, чтобы сделать симметричное приближение шестого порядка к гауссиану с низкой вычислительной сложностью для любого масштаба сглаживания.
Ослабив некоторые аксиомы, Линдеберг[1] пришел к выводу, что хорошие сглаживающие фильтры будут "нормализованы Pólya частотные последовательности ", семейство дискретных ядер, которое включает в себя все фильтры с действительными полюсами в 0 < Z <1 и / или Z > 1, а также с действительными нулями при Z <0. Для симметрии, которая приводит к приблизительной однородности направления, эти фильтры должны быть дополнительно ограничены парами полюсов и нулей, которые приводят к фильтрам с нулевой фазой.
Чтобы согласовать кривизну передаточной функции на нулевой частоте дискретного гауссиана, что обеспечивает приближенное полугруппа свойство добавки т, два полюса на
может применяться вперед и назад для симметрии и устойчивости. Этот фильтр является простейшей реализацией ядра нормализованной частотной последовательности Полиа, которое работает для любого масштаба сглаживания, но не является таким превосходным приближением к гауссову, как фильтр Юнга и Ван Влита, который является нет нормализованная частотная последовательность Полиа из-за ее сложных полюсов.
Передаточная функция, ЧАС1рекурсивного фильтра симметричных пар полюсов тесно связана с преобразование Фурье с дискретным временем дискретного гауссовского ядра через аппроксимацию первого порядка экспоненты:
где т здесь параметр относится к стабильному полюсу Z = п через:
Кроме того, такие фильтры с N пары полюсов, такие как две пары полюсов, показанные в этом разделе, являются еще лучшим приближением к экспоненте:
где стабильные положения полюсов регулируются путем решения:
Импульсные характеристики этих фильтров не очень близки к гауссовым, если не используется более двух пар полюсов. Однако даже при наличии только одной или двух пар полюсов на шкалу сигнал, последовательно сглаженный с увеличением масштабов, будет очень близок к сглаженному по Гауссу сигналу. Если используется слишком мало пар полюсов, свойство полугруппы аппроксимируется плохо.
Аксиомы масштабного пространства которые по-прежнему удовлетворяются этими фильтрами:
- линейность
- инвариантность сдвига (целочисленные сдвиги)
- отсутствие локальных экстремумов (нулевые переходы) в одном измерении
- отсутствие усиления локальных экстремумов в любом количестве измерений
- позитивность
- нормализация
Следующие условия выполняются лишь приблизительно, причем приближение лучше для большего числа пар полюсов:
- наличие бесконечно малый генератор А (бесконечно малый генератор дискретного гауссовского сигнала или приближающий его фильтр приблизительно отображает рекурсивный отклик фильтра на один из бесконечно больших т)
- то полугрупповая структура с ассоциированным свойство каскадного сглаживания (это свойство аппроксимируется рассмотрением ядер как эквивалентных, если они имеют одинаковые т стоимость, даже если они не совсем равны)
- вращательная симметрия
- масштабная инвариантность
Этот метод рекурсивного фильтра и его варианты для вычисления как гауссовского сглаживания, так и гауссовских производных были описаны несколькими авторами.[6][7][8][9] Загар и другие. проанализировали и сравнили некоторые из этих подходов и отметили, что фильтры Янга и Ван Влита представляют собой каскад (умножение) прямых и обратных фильтров, в то время как фильтры Дериша и Джина и другие. фильтры - это сумма прямых и обратных фильтров.[10]
В точных масштабах подход рекурсивной фильтрации, а также другие подходы с разделением не гарантируют наилучшего приближения к вращательной симметрии, поэтому в качестве альтернативы можно рассматривать неразделимые реализации для 2D-изображений.
При вычислении нескольких производных в N-струя одновременно, дискретное пространство масштаба сглаживание с дискретным аналогом гауссового ядра, или с помощью рекурсивного фильтра аппроксимации, а затем разностных операторы поддержки малой, может быть и более быстрым и точным, чем вычисления рекурсивных аппроксимаций каждого оператора производной.
Сглаживание с конечной импульсной характеристикой (FIR)
Для небольших масштабов КИХ-фильтр низкого порядка может быть лучшим сглаживающим фильтром, чем рекурсивный фильтр. Симметричное 3-ядро [т/2, 1-т, т/2], за т ≤ 0,5 сглаживается по шкале т используя пару действительных нулей на Z <0, и приближается к дискретному гауссову в пределе малых т. Фактически, с бесконечно малым т, либо этот фильтр с двумя нулями, либо двухполюсный фильтр с полюсами на Z = т/ 2 и Z = 2/т может использоваться как бесконечно малый генератор для дискретных гауссовских ядер, описанных выше.
Нули КИХ-фильтра могут быть объединены с полюсами рекурсивного фильтра для создания общего высококачественного сглаживающего фильтра. Например, если процесс сглаживания заключается в том, чтобы всегда применять биквадратный (двухполюсный, два нуля) фильтр вперед, а затем назад к каждой строке данных (и к каждому столбцу в 2D-случае), полюса и нули могут выполнять часть сглаживания. Предел нулей на т = 0,5 на пару (нули в Z = –1), поэтому для больших масштабов полюса делают большую часть работы. В более мелких масштабах комбинация дает отличное приближение к дискретному гауссову, если полюса и нули каждый делают примерно половину сглаживания. В т значения для каждой части сглаживания (полюса, нули, множественные приложения вперед и назад и т. д.) являются аддитивными в соответствии с приблизительным свойством полугруппы.
Передаточная функция КИХ-фильтра тесно связана с дискретным гауссовским ДВПФ, как и рекурсивный фильтр. Для одной пары нулей передаточная функция равна
где т здесь параметр относится к нулевым позициям Z = z через:
и мы требуем т ≤ 0,5, чтобы передаточная функция оставалась неотрицательной.
Кроме того, такие фильтры с N пары нулей, являются еще лучшим приближением к экспоненте и распространяются на более высокие значения т :
где стабильные нулевые положения настраиваются путем решения:
Эти КИХ-фильтры и фильтры с нулевым полюсом являются действительными ядрами масштабного пространства, удовлетворяющими тем же аксиомам, что и все полюсные рекурсивные фильтры.
Реализация в реальном времени в пирамидах и дискретная аппроксимация нормированных по масштабу производных
Что касается темы автоматического выбора шкалы на основе нормализованных производных, приближения пирамиды часто используются для получения производительности в реальном времени.[11][12][13] Приемлемость аппроксимации операций масштабного пространства внутри пирамиды проистекает из того факта, что повторное каскадное сглаживание с помощью обобщенных биномиальных ядер приводит к эквивалентным ядрам сглаживания, которые при разумных условиях приближаются к гауссову. Кроме того, можно показать, что биномиальные ядра (или, в более общем смысле, класс обобщенных биномиальных ядер) составляют уникальный класс ядер с конечной опорой, которые гарантируют отсутствие локальных экстремумов или нулевых переходов с увеличением масштаба (см. Статью о многомасштабные подходы подробнее). Однако может потребоваться особое внимание, чтобы избежать артефактов дискретизации.
Другие многомасштабные подходы
Для одномерных ядер существует хорошо развитая теория многомасштабные подходы, относительно фильтров, которые не создают новых локальных экстремумов или новых нулевых пересечений с увеличивающимся масштабом. Для непрерывных сигналов фильтры с действительными полюсами в s-plane входят в этот класс, тогда как для дискретных сигналов описанные выше рекурсивные и FIR-фильтры удовлетворяют этим критериям. В сочетании со строгим требованием непрерывной полугрупповой структуры, непрерывный гауссовский и дискретный гауссовский представляют собой уникальный выбор для непрерывных и дискретных сигналов.
Существует множество других методов многомасштабной обработки сигналов, обработки изображений и сжатия данных, использующих вейвлеты и множество других ядер, которые не используют и не требуют те же требования в качестве масштабное пространство описания делать; то есть они не зависят от более грубого масштаба, не генерируя новый экстремум, который не присутствовал в более мелком масштабе (в 1D), или от отсутствия усиления локальных экстремумов между соседними масштабными уровнями (в любом количестве измерений).
Смотрите также
Рекомендации
- ^ а б c Линдеберг, Т., "Масштабное пространство для дискретных сигналов", ПАМИ (12), № 3, март 1990 г., стр. 234-254.
- ^ а б Линдеберг, Т., Теория масштабного пространства в компьютерном зрении, Kluwer Academic Publishers, 1994., ISBN 0-7923-9418-6
- ^ Р.А. Хаддад и А. Акансу, "Класс быстрых гауссовских биномиальных фильтров для обработки речи и изображений, "IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 39, pp 723-727, March 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. Дои:10.1016 / 0165-1684 (95) 00020-E.
- ^ Дериш, Р.: Рекурсивная реализация гауссианы и ее производных, Отчет об исследовании INRIA 1893, 1993.
- ^ Ричард Ф. Лайон. «Распознавание речи в масштабном пространстве», Тр. 1987 ICASSP. Сан-Диего, март, стр. 29.3.14, 1987.
- ^ Цзинь, Дж. С., Гао Ю. "Рекурсивная реализация фильтрации LoG". Визуализация в реальном времени 1997;3:59–65.
- ^ . Совира Тан; Джейсон Л. Дейл и Алан Джонстон (2003). «Выполнение трех рекурсивных алгоритмов быстрой пространственно-вариативной гауссовой фильтрации». Визуализация в реальном времени. Vol. 9 нет. 3. С. 215–228. Дои:10.1016 / S1077-2014 (03) 00040-8.
- ^ Линдеберг, Тони и Бретцнер, Ларс (2003). Выбор масштаба в реальном времени в гибридных многомасштабных представлениях. Proc. Scale-Space'03, Конспект лекций по информатике. Конспект лекций по информатике. 2695. С. 148–163. Дои:10.1007/3-540-44935-3_11. ISBN 978-3-540-40368-5.
- ^ Кроули, Дж., Рифф О: Быстрое вычисление масштабно нормализованных гауссовских рецептивных полей, Proc. Scale-Space'03, Остров Скай, Шотландия, Springer Lecture Notes in Computer Science, volume 2695, 2003.
- ^ Лоу, Д. Г., «Отличительные особенности изображения от масштабно-инвариантных ключевых точек», Международный журнал компьютерного зрения, 60, 2, стр. 91-110, 2004.