Реализация масштабного пространства - Scale space implementation

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

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

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

${displaystyle f_ {C} left (x_ {1}, cdots, x_ {N}, tight),}$

получается свертывание ж_C с N-размерный Гауссово ядро:

${displaystyle g_ {N} left (x_ {1}, cdots, x_ {N}, tight).}$

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

${displaystyle Lleft (x_ {1}, cdots, x_ {N}, tight) = int _ {u_ {1} = - infty} ^ {infty} cdots int _ {u_ {N} = - infty} ^ {infty} f_ {C} влево (x_ {1} -u_ {1}, cdots, x_ {N} -u_ {N}, плотно) cdot g_ {N} left (u_ {1}, cdots, u_ {N}, плотно ), du_ {1} cdots du_ {N}.}$

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

Отделимость

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

${displaystyle g_ {N} left (x_ {1}, dots, x_ {N}, tight) = Gleft (x_ {1}, tight) cdots Gleft (x_ {N}, плотно)}$

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

${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 {2pi t}}} e ^ {- {frac {x ^ {2}} {2t}}}}$

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

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

Выбранное ядро ​​Гаусса

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

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

куда

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

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

${displaystyle L (x, t) = сумма _ {n = -M} ^ {M} f (x-n), G (n, t)}$

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

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

Обычный выбор - установить M к постоянному C умноженное на стандартное отклонение гауссова ядра

${displaystyle M = Csigma + 1 = C {sqrt {t}} + 1}$

куда C часто выбирают между 3 и 6.

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

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

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

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

Более совершенный подход состоит в свертке исходного сигнала с дискретное гауссово ядро Т(п, т)^[1][2][3]

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

куда

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

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

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

${displaystyle L (x, t) = сумма _ {n = -M} ^ {M} f (x-n), T (n, t)}$

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle {widehat {T}} (heta, t) = {frac {1} {e ^ {t (1-cos heta)}}} приблизительно {frac {1} {1 + t (1-cos heta)} } = H_ {1} (heta, t),}$

где т здесь параметр относится к стабильному полюсу Z = п через:

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

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

${displaystyle {frac {1} {left (1+ {frac {t} {N}} (1-cos heta) ight) ^ {N}}} = H_ {N} (heta, t),}$

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

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

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

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

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

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

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

Этот метод рекурсивного фильтра и его варианты для вычисления как гауссовского сглаживания, так и гауссовских производных были описаны несколькими авторами.^[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расположение четырех полюсов (X) и четырех нулей (кружков) на плоскости для сглаживающего фильтра, использующего прямой / обратный биквадрат для сглаживания в масштабе т = 2, с половиной сглаживания от полюсов и половиной от нулей. Все нули на Z = –1; полюса на Z = 0,172 и Z = 5,83. Полюса за пределами единичного круга реализуются путем фильтрации в обратном направлении с помощью устойчивых полюсов.

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

${displaystyle {widehat {T}} (heta, t) = e ^ {- t (1-cos heta)} приблизительно {1-t (1-cos heta)} = F_ {1} (heta, t),}$

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

${displaystyle t = - {гидроразрыв {2z} {(1-z) ^ {2}}},}$

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

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

${displaystyle left (1- {frac {t} {N}} (1-cos heta) ight) ^ {N} = F_ {N} (heta, t),}$

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

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

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

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

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

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

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

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

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

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

Рекомендации