Многомерная дискретная свертка

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

• 1 Определение
  • 1.1 Постановка проблемы и основы
  • 1.2 Мотивация и приложения
• 2 Декомпозиция строки-столбца с разделяемыми сигналами
  • 2.1 Разделимые сигналы
  • 2.2 Декомпозиция строки-столбца
  • 2.3 Ускорение вычислений за счет декомпозиции строка-столбец
• 3 Круговая свертка дискретных многомерных сигналов
  • 3.1 Теорема о свертке в многомерном пространстве
  • 3.2 Подход круговой свертки
  • 3.3 Выбор размера ДПФ, чтобы избежать наложения спектров
  • 3.4 Краткое описание процедуры с использованием ДПФ
• 4 Перекрыть и добавить
  • 4.1 Разложение на более мелкие блоки свертки
  • 4.2 Разбивка процедуры
  • 4.3 Графический метод работы
• 5 Перекрытие и сохранение
  • 5.1 Сравнение для перекрытия и добавления
  • 5.2 Разбивка процедуры
• 6 Преобразование спирали
  • 6.1. Многомерная свертка методами одномерной свертки.
  • 6.2 Фильтрация по спирали
  • 6.3 Приложения
• 7 Гауссова свертка
  • 7.1 Аппроксимация КИХ-фильтром
  • 7.2 Аппроксимация коробчатым фильтром
  • 7.3 Приложения
• 8 См. Также
• 9 ссылки

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

Как и в одномерном случае, звездочка используется для обозначения операции свертки. Количество измерений в данной операции отображается в количестве звездочек. Например, M -мерная свертка будет записана с M звездочками. Следующее представляет собой M -мерную свертку дискретных сигналов:

${\ displaystyle y (n_ {1}, n_ {2},..., n_ {M}) = x (n_ {1}, n_ {2},..., n_ {M}) * {\ overset {M} {\ cdots}} * h (n_ {1}, n_ {2},..., n_ {M})}$

Для сигналов с дискретными значениями эту свертку можно напрямую вычислить с помощью следующего:

${\ displaystyle \ sum _ {k_ {1} = - \ infty} ^ {\ infty} \ sum _ {k_ {2} = - \ infty} ^ {\ infty}... \ sum _ {k_ {M} = - \ infty} ^ {\ infty} h (k_ ​​{1}, k_ {2},..., k_ {M}) x (n_ {1} -k_ {1}, n_ {2} -k_ { 2},..., n_ {M} -k_ {M})}$

Результирующая выходная область поддержки дискретной многомерной свертки будет определяться на основе размера и областей поддержки двух входных сигналов.

Визуализация свертки двух простых двумерных сигналов

Перечислены несколько свойств оператора двумерной свертки. Обратите внимание, что они также могут быть расширены для сигналов -измерений. ${\ displaystyle N}$

Коммутативная собственность:

${\ Displaystyle х ** ч = ч ** х}$

Сопутствующее имущество:

${\ Displaystyle (х ** ч) ** г = х ** (ч ** г)}$

Распределительное свойство:

${\ Displaystyle х ** (ч + г) = (х ** ч) + (х ** г)}$

Использование этих свойств показано на рисунке ниже. Учитывая некоторый входной сигнал, который поступает в фильтр с импульсной характеристикой, а затем в другой фильтр с импульсной характеристикой, на выходе получается. Предположим, что выходной сигнал первого фильтра равен, это означает, что: ${\ Displaystyle х (п_ {1}, п_ {2})}$${\ displaystyle h (n_ {1}, n_ {2})}$${\ displaystyle g (n_ {1}, n_ {2})}$${\ Displaystyle у (п_ {1}, п_ {2})}$${\ Displaystyle ш (п_ {1}, п_ {2})}$

${\ Displaystyle ш = х ** ч}$

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

${\ displaystyle y = w ** g = (x ** h) ** g}$

Используя свойство ассоциативности, это можно переписать следующим образом:

${\ Displaystyle у = х ** (ч ** г)}$

Это означает, что эквивалентная импульсная характеристика для каскадной системы определяется следующим образом:

${\ displaystyle h_ {eq} = h ** g}$

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

Аналогичный анализ можно провести на наборе параллельных систем, показанных ниже.

Система с набором параллельных фильтров.

В этом случае ясно, что:

${\ Displaystyle у = (х ** ч) + (х ** г)}$

Используя закон распределения, показано, что:

${\ Displaystyle у = х ** (ч + г)}$

Это означает, что в случае параллельной системы эквивалентная импульсная характеристика обеспечивается:

${\ displaystyle h_ {eq} = h + g}$

Эквивалентные импульсные характеристики как в каскадных системах, так и в параллельных системах можно обобщить на системы с числом фильтров. ${\ displaystyle N}$

Мотивация и приложения

Свертка в одном измерении была мощным открытием, которое позволило легко сравнивать входные и выходные данные линейной инвариантной к сдвигу (LSI) системы (см. Теорию систем LTI ) при условии, что импульсная характеристика системы фильтров была известна. Это понятие распространяется и на многомерную свертку, поскольку простое знание импульсной характеристики многомерного фильтра также позволяет проводить прямое сравнение между входом и выходом системы. Это очень важно, поскольку некоторые сигналы, которые передаются в современном цифровом мире, имеют множество измерений, включая изображения и видео. Подобно одномерной свертке, многомерная свертка позволяет вычислять выходные данные системы LSI для заданного входного сигнала.

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

Импульсные характеристики типичных многомерных фильтров нижних частот

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

Типичные импульсные характеристики для обнаружения фронта Исходное изображение (слева) и изображение после прохождения через фильтр обнаружения краев (справа)

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

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

Исходное изображение (слева) и размытое изображение (справа), выполненные с использованием гауссовой свертки

Разделимые сигналы

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

${\ displaystyle x (n_ {1}, n_ {2},..., n_ {M}) = x (n_ {1}) x (n_ {2})... x (n_ {M})}$

Некоторые легко распознаваемые разделяемые сигналы включают функцию единичного шага и импульсную функцию дирака-дельта.

${\ displaystyle u (n_ {1}, n_ {2},..., n_ {M}) = u (n_ {1}) u (n_ {2})... u (n_ {M})}$ (функция единичного шага)

${\ displaystyle \ delta (n_ {1}, n_ {2},..., n_ {M}) = \ delta (n_ {1}) \ delta (n_ {2})... \ delta (n_ { M})}$ (функция дирак-дельта-импульс)

Свертка - это линейная операция. Из этого следует, что многомерная свертка разделимых сигналов может быть выражена как произведение многих одномерных сверток. Например, рассмотрим случай, когда x и h обе разделяемые функции.

${\ displaystyle x (n_ {1}, n_ {2}) ** h (n_ {1}, n_ {2}) = \ sum _ {k_ {1} = - \ infty} ^ {\ infty} \ sum _ {k_ {2} = - \ infty} ^ {\ infty} h (k_ ​​{1}, k_ {2}) x (n_ {1} -k_ {1}, n_ {2} -k_ {2}) }$

Применяя свойства отделимости, это можно переписать следующим образом:

${\ displaystyle x (n_ {1}, n_ {2}) ** h (n_ {1}, n_ {2}) = {\ bigg (} \ sum _ {k_ {1} = - \ infty} ^ { \ infty} h (k_ ​​{1}) x (n_ {1} -k_ {1}) {\ bigg)} {\ bigg (} \ sum _ {k_ {2} = - \ infty} ^ {\ infty} h (k_ ​​{2}) x (n_ {2} -k_ {2}) {\ bigg)}}$

Легко видеть, что это сводится к произведению одномерных сверток:

${\ Displaystyle х (п_ {1}, п_ {2}) ** ч (п_ {1}, п_ {2}) = {\ bigg [} х (п_ {1}) * ч (п_ {1}) {\ bigg]} {\ bigg [} x (n_ {2}) * h (n_ {2}) {\ bigg]}}$

Этот вывод затем можно распространить на свертку двух разделимых M -мерных сигналов следующим образом:

${\ displaystyle x (n_ {1}, n_ {2},..., n_ {M}) * {\ overset {M} {\ cdots}} * h (n_ {1}, n_ {2},..., n_ {M}) = {\ bigg [} x (n_ {1}) * h (n_ {1}) {\ bigg]} {\ bigg [} x (n_ {2}) * h (n_ {2}) {\ bigg]}... {\ bigg [} x (n_ {M}) * h (n_ {M}) {\ bigg]}}$

Итак, когда два сигнала разделимы, многомерная свертка может быть вычислена путем вычисления одномерных сверток. ${\ displaystyle n_ {M}}$

Разложение по строкам и столбцам

Метод строка-столбец может применяться, когда один из сигналов в свертке разделяется. Этот метод использует свойства разделимости для достижения метода вычисления свертки двух многомерных сигналов, который является более эффективным с точки зрения вычислений, чем прямое вычисление каждой выборки (при условии, что один из сигналов является разделимым). Ниже показаны математические рассуждения, лежащие в основе подхода декомпозиции строки-столбца (обычно это разделяемый сигнал): ${\ displaystyle h (n_ {1}, n_ {2})}$

${\ displaystyle {\ begin {align} y (n_ {1}, n_ {2}) amp; = \ sum _ {k_ {1} = - \ infty} ^ {\ infty} \ sum _ {k_ {2} = - \ infty} ^ {\ infty} h (k_ ​​{1}, k_ {2}) x (n_ {1} -k_ {1}, n_ {2} -k_ {2}) \\ amp; = \ sum _ {k_ {1} = - \ infty} ^ {\ infty} \ sum _ {k_ {2} = - \ infty} ^ {\ infty} h_ {1} (k_ {1}) h_ {2} (k_ { 2}) x (n_ {1} -k_ {1}, n_ {2} -k_ {2}) \\ amp; = \ sum _ {k_ {1} = - \ infty} ^ {\ infty} h_ {1 } (k_ {1}) {\ Bigg [} \ sum _ {k_ {2} = - \ infty} ^ {\ infty} h_ {2} (k_ {2}) x (n_ {1} -k_ {1 }, n_ {2} -k_ {2}) {\ Bigg]} \ end {align}}}$

Значение теперь можно повторно использовать при оценке других значений с общим значением: ${\ displaystyle \ sum _ {k_ {2} = - \ infty} ^ {\ infty} h_ {2} (k_ {2}) x (n_ {1} -k_ {1}, n_ {2} -k_ { 2})}$${\ displaystyle y}$${\ displaystyle n_ {2}}$

${\ displaystyle {\ begin {align} y (n_ {1} + \ delta, n_ {2}) amp; = \ sum _ {k_ {1} = - \ infty} ^ {\ infty} h_ {1} (k_ {1}) {\ Bigg [} \ sum _ {k_ {2} = - \ infty} ^ {\ infty} h_ {2} (k_ {2}) x (n_ {1} - [k_ {1} - \ delta], n_ {2} -k_ {2}) {\ Bigg]} \\ amp; = \ sum _ {k_ {1} = - \ infty} ^ {\ infty} h_ {1} (k_ {1} + \ delta) {\ Bigg [} \ sum _ {k_ {2} = - \ infty} ^ {\ infty} h_ {2} (k_ {2}) x (n_ {1} -k_ {1}, n_ {2} -k_ {2}) {\ Bigg]} \ конец {выровнено}}}$

Таким образом, результирующую свертку можно эффективно вычислить, сначала выполнив операцию свертки для всех строк, а затем для всех ее столбцов. Этот подход можно дополнительно оптимизировать, приняв во внимание способ доступа к памяти в процессоре компьютера. ${\ Displaystyle х (п_ {1}, п_ {2})}$

Процессор загрузит данные сигнала, необходимые для данной операции. Для современных процессоров данные будут загружаться из памяти в кэш процессора, который имеет более быстрое время доступа, чем память. Сам кеш разбит на строки. Когда строка кэша загружается из памяти, одновременно загружается несколько операндов данных. Рассмотрим оптимизированный случай, когда строка данных сигнала может полностью уместиться в кэш-памяти процессора. Этот конкретный процессор сможет эффективно обращаться к данным по строкам, но не по столбцам, поскольку разные операнды данных в одном столбце будут находиться в разных строках кэша. Чтобы воспользоваться преимуществами способа доступа к памяти, более эффективно транспонировать набор данных, а затем ось его по строкам, а не пытаться получить доступ к нему по столбцам. Затем алгоритм становится:

1. Разделите разделяемый двумерный сигнал на два одномерных сигнала и${\ displaystyle h (n_ {1}, n_ {2})}$${\ displaystyle h_ {1} (n_ {1})}$${\ displaystyle h_ {2} (n_ {2})}$
2. Выполните построчную свертку горизонтальных компонентов сигнала, используя для получения${\ Displaystyle х (п_ {1}, п_ {2})}$${\ displaystyle h_ {1} (n_ {1})}$${\ displaystyle g (n_ {1}, n_ {2})}$
3. Транспонируйте вертикальные компоненты сигнала, полученного на шаге 2.${\ displaystyle g (n_ {1}, n_ {2})}$
4. Выполните построчную свертку транспонированных вертикальных компонентов, чтобы получить желаемый результат.${\ displaystyle g (n_ {1}, n_ {2})}$${\ Displaystyle у (п_ {1}, п_ {2})}$

Ускорение вычислений за счет разложения строки на столбец

Рассмотрим случай, когда изображение большого размера проходит через разделяемый фильтр размера. Само изображение не отделимо. Если результат вычисляется с использованием подхода прямой свертки без использования разделимости фильтра, это потребует приблизительного умножения и сложения. Если учесть разделимость фильтра, фильтрацию можно провести в два этапа. На первом шаге будет умножение и сложение, а на втором - умножение и сложение в сумме или. Сравнение вычислительной сложности между прямой и разделяемой сверткой дается на следующем изображении: ${\ Displaystyle X \ раз Y}$${\ displaystyle J \ times K}$${\ displaystyle XYJK}$${\ displaystyle XYJ}$${\ displaystyle XYK}$${\ displaystyle XYJ + XYK}$${\ Displaystyle XY (J + K)}$

Количество вычислений, пропускающих изображение размером 10 x 10 через фильтр размера J x K, где J = K изменяется в размере от 1 до 10.

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

Теорема свертки в нескольких измерениях

Для одномерных сигналов теорема свертки утверждает, что преобразование Фурье свертки между двумя сигналами равно произведению преобразований Фурье этих двух сигналов. Таким образом, свертка во временной области равна умножению в частотной области. Математически этот принцип выражается следующим образом:

$${\ Displaystyle у (п) = час (п) * Икс (п) \ longleftrightarrow Y (\ omega) = H (\ omega) X (\ omega)}$$ Этот принцип можно напрямую распространить на сигналы многих измерений. $${\ displaystyle y (n_ {1}, n_ {2},..., n_ {M}) = h (n_ {1}, n_ {2},..., n_ {M}) * {\ overset {M} {\ cdots}} * x (n_ {1}, n_ {2},..., n_ {M}) \ longleftrightarrow Y (\ omega _ {1}, \ omega _ {2},..., \ omega _ {M}) = H (\ omega _ {1}, \ omega _ {2},..., \ omega _ {M}) X (\ omega _ {1}, \ omega _ { 2},..., \ omega _ {M})}$$ Это свойство легко распространяется на использование с дискретным преобразованием Фурье (ДПФ) следующим образом (обратите внимание, что линейная свертка заменена круговой сверткой, где используется для обозначения операции круговой свертки размера): ${\ displaystyle \ otimes}$${\ displaystyle N}$

${\ Displaystyle Y (N) = H (N) \ otimes x (n) \ longleftrightarrow Y (k) = H (k) X (k)}$

При работе с многомерными сигналами:

$${\ displaystyle y (n_ {1}, n_ {2},..., n_ {M}) = h (n_ {1}, n_ {2},..., n_ {M}) \ otimes {\ overset {M} {\ cdots}} \ otimes x (n_ {1}, n_ {2},..., n_ {M}) \ longleftrightarrow Y (k_ {1}, k_ {2},..., k_ {M}) = H (k_ {1}, k_ {2},..., k_ {M}) X (k_ {1}, k_ {2},..., k_ {M})}$$ Круговые извилины здесь будут иметь размер. ${\ displaystyle N_ {1}, N_ {2},..., N_ {M}}$

Подход круговой свертки

Мотивация использования подхода круговой свертки заключается в том, что он основан на ДПФ. Предпосылка круговой свертки состоит в том, чтобы взять ДПФ входных сигналов, умножить их вместе, а затем взять обратное ДПФ. Необходимо соблюдать осторожность, чтобы использовать достаточно большое ДПФ, чтобы не возникало наложения спектров. ДПФ вычислимо численно при работе с сигналами конечной протяженности. Одним из преимуществ этого подхода является то, что, поскольку он требует использования ДПФ и обратного ДПФ, можно использовать эффективные алгоритмы, такие как быстрое преобразование Фурье (БПФ). Круговая свертка также может быть вычислена во временной / пространственной области, а не только в частотной области.

Блок-схема круговой свертки с 2 M -мерными сигналами

Выбор размера ДПФ, чтобы избежать сглаживания

Рассмотрим следующий случай, когда принимаются два сигнала конечной протяженности x и h. Для обоих сигналов существует соответствующее ДПФ:

${\ displaystyle x (n_ {1}, n_ {2}) \ longleftrightarrow X (k_ {1}, k_ {2})}$ и ${\ displaystyle h (n_ {1}, n_ {2}) \ longleftrightarrow H (k_ {1}, k_ {2})}$

Регион поддержки есть и регион поддержки есть и. ${\ Displaystyle х (п_ {1}, п_ {2})}$${\ Displaystyle 0 \ Leq N_ {1} \ Leq P_ {1} -1}$${\ Displaystyle 0 \ Leq N_ {2} \ Leq P_ {2} -1}$${\ displaystyle h (n_ {1}, n_ {2})}$${\ Displaystyle 0 \ Leq N_ {1} \ Leq Q_ {1} -1}$${\ Displaystyle 0 \ Leq N_ {2} \ Leq Q_ {2} -1}$

Линейная свертка этих двух сигналов будет дана как:

$${\ displaystyle y_ {linear} (n_ {1}, n_ {2}) = \ sum _ {m_ {1}} \ sum _ {m_ {2}} h (m_ {1}, m_ {2}) x (n_ {1} -m_ {1}, n_ {2} -m_ {2})}$$ Учитывая регионы поддержки и, тогда регион поддержки будет представлен следующим образом: ${\ Displaystyle х (п_ {1}, п_ {2})}$${\ displaystyle h (n_ {1}, n_ {2})}$${\ displaystyle y_ {linear} (n_ {1}, n_ {2})}$ $${\ displaystyle 0 \ leq n_ {1} \ leq P_ {1} + Q_ {1} -1}$$ $${\ displaystyle 0 \ leq n_ {2} \ leq P_ {2} + Q_ {2} -1}$$ Основываясь на областях поддержки двух сигналов, необходимо использовать ДПФ такого размера, где и поскольку для обоих сигналов необходимо использовать ДПФ одинакового размера. В случае, когда требуется размер ДПФ, превышающий размер сигнала, сигнал дополняется нулями до тех пор, пока не достигнет требуемой длины. После умножения ДПФ и взятия обратного ДПФ на результат результирующая круговая свертка определяется следующим образом: ${\ displaystyle N_ {1} \ times N_ {2}}$${\ Displaystyle N_ {1} \ geq \ max (P_ {1}, Q_ {1})}$${\ Displaystyle N_ {2} \ geq \ max (P_ {2}, Q_ {2})}$

${\ displaystyle y_ {круговой} (n_ {1}, n_ {2}) = \ sum _ {r_ {1}} \ sum _ {r_ {2}} {\ Bigg [} \ sum _ {m_ {1} = 0} ^ {Q_ {1} -1} \ sum _ {m_ {2} = 0} ^ {Q_ {2} -1} h (m_ {1}, m_ {2}) x (n_ {1} -m_ {1} -r_ {1} N_ {1}, n_ {2} -m_ {2} -r_ {2} N_ {2}) {\ Bigg]}}$ для ${\ displaystyle (n_ {1}, n_ {2}) \ in R_ {N_ {1} N_ {2}}}$

${\ Displaystyle R_ {N_ {1} N_ {2}} \ треугольник \ {(n_ {1}, n_ {2}): 0 \ leq n_ {1} \ leq N_ {1} -1,0 \ leq n_ {2} \ leq N_ {2} -1 \}}$

Результатом будет версия результата линейной свертки с пространственным псевдонимом. Это можно выразить следующим образом: ${\ displaystyle y_ {круговой} (n_ {1}, n_ {2})}$${\ displaystyle y_ {linear} (n_ {1}, n_ {2})}$

${\ displaystyle y_ {круговой} (n_ {1}, n_ {2}) = \ sum _ {r_ {1}} \ sum _ {r_ {2}} y_ {linear} (n_ {1} -r_ {1 } N_ {1}, n_ {2} -r_ {2} N_ {2}) {\ mathrm {\, \, \, для \, \, \,}} (n_ {1}, n_ {2}) \ in R_ {N_ {1} N_ {2}}}$

Затем, чтобы избежать наложения спектров между репликами с пространственным псевдонимом, и должен быть выбран так, чтобы он удовлетворял следующим условиям: ${\ displaystyle N_ {1}}$${\ displaystyle N_ {2}}$

${\ Displaystyle N_ {1} \ geq P_ {1} + Q_ {1} -1}$

${\ Displaystyle N_ {2} \ geq P_ {2} + Q_ {2} -1}$

Если эти условия выполнены, то результаты круговой свертки будут равны результатам линейной свертки (принимая основной период круговой свертки в качестве области опоры). Это:

${\ displaystyle y_ {круговой} (n_ {1}, n_ {2}) = y_ {linear} (n_ {1}, n_ {2})}$ для ${\ displaystyle (n_ {1}, n_ {2}) \ in R_ {N_ {1} N_ {2}}}$

Краткое описание процедуры с использованием ДПФ

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

1. Выбирай и удовлетворяй и${\ displaystyle N_ {1}}$${\ displaystyle N_ {2}}$${\ Displaystyle N_ {1} \ geq P_ {1} + Q_ {1} -1}$${\ Displaystyle N_ {2} \ geq P_ {2} + Q_ {2} -1}$
2. Обнулить сигналы и так, чтобы они были одинакового размера.${\ displaystyle h (n_ {1}, n_ {2})}$${\ Displaystyle х (п_ {1}, п_ {2})}$${\ displaystyle N_ {1} \ times N_ {2}}$
3. Вычислить ДПФ обоих и${\ displaystyle h (n_ {1}, n_ {2})}$${\ Displaystyle х (п_ {1}, п_ {2})}$
4. Умножьте результаты ДПФ, чтобы получить ${\ Displaystyle Y (k_ {1}, k_ {2}) = H (k_ {1}, k_ {2}) X (k_ {1}, k_ {2})}$
5. Тогда результат IDFT будет равен результату выполнения линейной свертки двух сигналов.${\ displaystyle Y (k_ {1}, k_ {2})}$

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

Рассмотрим двумерную свертку с помощью прямого вычисления:

${\ displaystyle y (n_ {1}, n_ {2}) = \ sum _ {k_ {1} = - \ infty} ^ {\ infty} \ sum _ {k_ {2} = - \ infty} ^ {\ infty} x (n_ {1} -k_ {1}, n_ {2} -k_ {2}) h (k_ ​​{1}, k_ {2})}$

Предполагая, что выходной сигнал имеет N ненулевых коэффициентов, а импульсный отклик имеет M ненулевых отсчетов, это прямое вычисление потребует умножения MN и сложения MN - 1 для вычисления. Вместо этого при использовании БПФ частотная характеристика фильтра и преобразование Фурье входного сигнала должны быть сохранены в памяти. Огромные объемы вычислений и чрезмерное использование памяти для хранения создают проблемную проблему по мере добавления дополнительных измерений. Здесь на помощь приходит метод перекрытия и добавления свертки. ${\ Displaystyle у (п_ {1}, п_ {2})}$

Разложение на более мелкие блоки свертки

Вместо того, чтобы выполнять свертку для блоков информации в целом, информация может быть разбита на более мелкие блоки размером x, что приводит к меньшим БПФ, меньшей вычислительной сложности и меньшему объему необходимого хранилища. Математически это можно выразить следующим образом: ${\ displaystyle L_ {1}}$${\ displaystyle L_ {2}}$

${\ displaystyle x (n_ {1}, n_ {2}) = \ sum _ {i = 1} ^ {P_ {1}} \ sum _ {j = 1} ^ {P_ {2}} x_ {ij} (n_ {1}, n_ {2})}$

где представляет собой входной сигнал x, который представляет собой сумму сегментов блока, с и. ${\ Displaystyle х (п_ {1}, п_ {2})}$${\ displaystyle N_ {1}}$${\ displaystyle N_ {2}}$${\ Displaystyle P_ {1} P_ {2}}$${\ Displaystyle P_ {1} = N_ {1} / L_ {1}}$${\ Displaystyle P_ {2} = N_ {2} / L_ {2}}$

Для получения выходного сигнала выполняется двумерная свертка:

${\ displaystyle y (n_ {1}, n_ {2}) = x (n_ {1}, n_ {2}) ** h (n_ {1}, n_ {2})}$

Подстановка результатов в следующем: ${\ Displaystyle х (п_ {1}, п_ {2})}$

${\ displaystyle y (n_ {1}, n_ {2}) = \ sum _ {i = 1} ^ {P_ {1}} \ sum _ {j = 1} ^ {P_ {2}} x_ {ij} (n_ {1}, n_ {2}) ** h (n_ {1}, n_ {2})}$

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

Разбивка процедуры

Пусть будет размером: ${\ displaystyle h (n_ {1}, n_ {2})}$${\ displaystyle M_ {1} \ times M_ {2}}$

1. Разбейте ввод на неперекрывающиеся блоки размеров.${\ Displaystyle х (п_ {1}, п_ {2})}$${\ Displaystyle L_ {1} \ раз L_ {2}}$
2. Обнулить площадку, чтобы она имела размеры () ().${\ displaystyle h (n_ {1}, n_ {2})}$${\ displaystyle L_ {1} + M_ {1} -1}$${\ displaystyle \ times}$${\ displaystyle L_ {2} + M_ {2} -1}$
3. Используйте DFT, чтобы получить.${\ Displaystyle Н (к_ {1}, к_ {2})}$
4. Для каждого входного блока:
   1. Нулевая площадка должна иметь размеры () ().${\ displaystyle x_ {ij} (n_ {1}, n_ {2})}$${\ displaystyle L_ {1} + M_ {1} -1}$${\ displaystyle \ times}$${\ displaystyle L_ {2} + M_ {2} -1}$
   2. Возьмите дискретное преобразование Фурье каждого блока, чтобы дать.${\ displaystyle X_ {ij} (k_ {1}, k_ {2})}$
   3. Умножьте, чтобы получить.${\ Displaystyle Y_ {ij} (k_ {1}, k_ {2}) = X_ {ij} (k_ {1}, k_ {2}) H (k_ {1}, k_ {2})}$
   4. Возьмите обратное дискретное преобразование Фурье, чтобы получить.${\ displaystyle Y_ {ij} (k_ {1}, k_ {2})}$${\ displaystyle y_ {ij} (n_ {1}, n_ {2})}$
5. Найдите путем наложения и сложения последних выборок с первыми выборками, чтобы получить результат.${\ Displaystyle у (п_ {1}, п_ {2})}$${\ displaystyle (M_ {1} -1)}$${\ displaystyle \ times}$ ${\ displaystyle (M_ {2} -1)}$${\ displaystyle y_ {ij} (n_ {1}, n_ {2})}$${\ displaystyle (M_ {1} -1)}$ ${\ displaystyle \ times}$${\ displaystyle (M_ {2} -1)}$${\ displaystyle y_ {я + 1, j + 1} (n_ {1}, n_ {2})}$

Графический метод работы

Чтобы нагляднее представить метод сложения с перекрытием, на следующих иллюстрациях этот метод рассматривается графически. Предположим, что вход имеет опору квадратной области длиной N как в вертикальном, так и в горизонтальном направлениях, как показано на рисунке ниже. Затем он разбивается на четыре меньших сегмента таким образом, что теперь он состоит из четырех меньших квадратов. Каждый блок совокупного сигнала имеет размеры.${\ Displaystyle х (п_ {1}, п_ {2})}$${\ Displaystyle (N / 2)}$ ${\ displaystyle \ times}$ ${\ Displaystyle (N / 2)}$

Разложенный входной сигнал

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

На рисунке ниже первый график слева представляет свертку, соответствующую компоненту входа с соответствующей импульсной характеристикой. Справа от этого вход затем свертывается с импульсной характеристикой. ${\ displaystyle x_ {0,0}}$${\ displaystyle h (n_ {1}, n_ {2})}$${\ displaystyle x_ {1,0}}$${\ displaystyle h (n_ {1}, n_ {2})}$

Свертка отдельных компонентов с импульсной характеристикой Свертка каждого компонента с выделенными частями перекрытия

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

Предположим, что импульсная характеристика фильтра имеет область поддержки в обоих измерениях. Это влечет за собой, что каждый из свертки свертывает сигналы с размерами в обоих и направлениях, что приводит к перекрытию (выделено синий цвет), так как длина каждой отдельной свертки эквивалентны: ${\ displaystyle h (n_ {1}, n_ {2})}$${\ Displaystyle (N / 8)}$${\ Displaystyle (N / 2)}$ ${\ displaystyle \ times}$ ${\ Displaystyle (N / 8)}$${\ displaystyle n_ {1}}$${\ displaystyle n_ {2}}$

${\ Displaystyle (N / 2)}$ ${\ displaystyle +}$${\ Displaystyle (N / 8)}$ ${\ displaystyle -}$${\ displaystyle 1}$ знак равно ${\ displaystyle (5/8) N-1}$

в обоих направлениях. Светло-синяя часть коррелирует с перекрытием между двумя соседними свертками, тогда как более темная синяя часть коррелирует с перекрытием между всеми четырьмя свертками. Все эти перекрывающиеся части складываются вместе в дополнение к сверткам, чтобы сформировать комбинированную свертку. ${\ Displaystyle у (п_ {1}, п_ {2})}$

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

Сравнение с перекрытием и добавлением

Метод перекрытия и сохранения очень похож на методы перекрытия и добавления с некоторыми заметными исключениями. Метод сложения с перекрытием включает в себя линейную свертку сигналов с дискретным временем, тогда как метод с сохранением перекрытия использует принцип круговой свертки. Кроме того, метод перекрытия и сохранения использует только одноразовое нулевое заполнение импульсной характеристики, тогда как метод перекрытия-добавления включает заполнение нулями для каждой свертки на каждом входном компоненте. Вместо использования нулевого заполнения для предотвращения сглаживания во временной области, как его аналог с перекрытием-добавлением, overlap-save просто отбрасывает все точки сглаживания и сохраняет предыдущие данные в одном блоке для копирования в свертку для следующего блока.

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

Разбивка процедуры

Пусть будет размером: ${\ displaystyle h (n_ {1}, n_ {2})}$${\ displaystyle M_ {1} \ times M_ {2}}$

1. Вставьте столбцы и строки нулей в начало входного сигнала в обоих измерениях.${\ displaystyle (M_ {1} -1)}$${\ displaystyle (M_ {2} -1)}$${\ Displaystyle х (п_ {1}, п_ {2})}$
2. Разделите соответствующий сигнал на перекрывающиеся сегменты размеров () (), в которых каждый двумерный блок будет перекрываться.${\ displaystyle L_ {1} + M_ {1} -1}$${\ displaystyle \ times}$${\ displaystyle L_ {2} + M_ {2} -1}$${\ displaystyle (M_ {1} -1)}$ ${\ displaystyle \ times}$ ${\ displaystyle (M_ {2} -1)}$
3. Обнулить площадку, чтобы она имела размеры () ().${\ displaystyle h (n_ {1}, n_ {2})}$${\ displaystyle L_ {1} + M_ {1} -1}$${\ displaystyle \ times}$${\ displaystyle L_ {2} + M_ {2} -1}$
4. Используйте DFT, чтобы получить.${\ Displaystyle Н (к_ {1}, к_ {2})}$
5. Для каждого входного блока:
   1. Возьмите дискретное преобразование Фурье каждого блока, чтобы дать.${\ displaystyle X_ {ij} (k_ {1}, k_ {2})}$
   2. Умножьте, чтобы получить.${\ Displaystyle Y_ {ij} (k_ {1}, k_ {2}) = X_ {ij} (k_ {1}, k_ {2}) H (k_ {1}, k_ {2})}$
   3. Возьмите обратное дискретное преобразование Фурье, чтобы получить.${\ displaystyle Y_ {ij} (k_ {1}, k_ {2})}$${\ displaystyle y_ {ij} (n_ {1}, n_ {2})}$
   4. Избавьтесь от первого для каждого выходного блока.${\ displaystyle (M_ {1} -1)}$${\ displaystyle \ times}$${\ displaystyle (M_ {2} -1)}$${\ displaystyle y_ {ij} (n_ {1}, n_ {2})}$
6. Найдите, прикрепив последние образцы для каждого выходного блока.${\ Displaystyle у (п_ {1}, п_ {2})}$${\ Displaystyle (L_ {1} \ раз L_ {2})}$${\ displaystyle y_ {ij} (n_ {1}, n_ {2})}$

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

Многомерная свертка методами одномерной свертки

Чтобы понять преобразование спирали, полезно сначала понять, как многомерная свертка может быть разбита на одномерную свертку. Предположим, что два сигнала, которые должны быть свёрнуты, - это и, что приводит к выходу. Это выражается следующим образом: ${\ displaystyle X_ {M \ times N}}$${\ displaystyle Y_ {K \ times L}}$${\ Displaystyle Z _ {(М-К + 1) \ раз (N-L + 1)}}$

${\ Displaystyle Z (я, j) ​​= \ сумма _ {м = 0} ^ {M-1} \ sum _ {n = 0} ^ {N-1} X (m, n) Y (im, jn) }$

Затем создаются две матрицы, которые заполняют каждый вход нулями в обоих измерениях, так что каждый вход имеет эквивалентные размеры, т. Е.

${\ displaystyle \ mathbf {X '} = {\ begin {bmatrix} X amp; 0 \\ 0 amp; 0 \\\ end {bmatrix}}}$ и ${\ displaystyle \ mathbf {Y '} = {\ begin {bmatrix} Y amp; 0 \\ 0 amp; 0 \\\ end {bmatrix}}}$

где каждая из входных матриц теперь имеет размерность. Затем можно реализовать лексикографическое упорядочение по столбцам, чтобы преобразовать модифицированные матрицы в векторы, и. Чтобы минимизировать количество несущественных выборок в каждом векторе, каждый вектор усекается после последней выборки в исходных матрицах и соответственно. Учитывая это, длина вектора и определяется выражением: ${\ Displaystyle (М + К-1)}$${\ displaystyle \ times}$${\ Displaystyle (N + L-1)}$${\ displaystyle X ''}$${\ displaystyle Y ''}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle X ''}$${\ displaystyle Y ''}$

${\ displaystyle l_ {X ''} =}$ ${\ Displaystyle (М + К-1)}$${\ displaystyle \ times}$${\ Displaystyle (N-1)}$ + ${\ displaystyle M}$

${\ displaystyle l_ {Y ''} =}$${\ Displaystyle (М + К-1)}$${\ displaystyle \ times}$${\ Displaystyle (L-1)}$ + ${\ displaystyle K}$

Длина свертки этих двух векторов может быть получена и показана как: ${\ displaystyle Z ''}$

${\ displaystyle l_ {Z ''} =}$ ${\ displaystyle l_ {Y ''} +}$${\ displaystyle l_ {X ''}}$ ${\ Displaystyle = (М + К-1)}$${\ displaystyle \ times}$${\ Displaystyle (N + L-1)}$

Эта длина вектора эквивалентна размерам исходной матрицы, что делает преобразование обратно в матрицу прямым преобразованием. Таким образом, вектор преобразуется обратно в матричную форму, которая дает результат двумерной дискретной свертки. ${\ displaystyle Z}$${\ displaystyle Z ''}$

Фильтрация по спирали

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

Преобразование из двумерной декартовой плоскости фильтрации в спиральный фильтр.

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

Одномерная фильтрующая полоса после разматывания.

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

0	-1	0
-1	4	-1
0	-1	0

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

${\ displaystyle h (n) = - 1,0,..., 0, -1,4, -1,0,..., 0, -1,0,...}$

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

Приложения

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

Одно из применений многомерной свертки, которое используется при обработке сигналов и изображений, - это свертка по Гауссу. Это относится к свертке входного сигнала с функцией распределения Гаусса.

2D гауссовская визуализация, где и${\ Displaystyle \ му _ {1} = \ му _ {2} = 0}$${\ Displaystyle \ sigma _ {1} = \ sigma _ {2} = 1}$

Распределение Гаусса, полученное с дискретными значениями в одном измерении, определяется следующим образом (при условии):${\ displaystyle \ mu = 0}$

$${\ displaystyle G (n) = {\ frac {1} {\ sqrt {2 \ pi \ sigma ^ {2}}}} e ^ {- {\ frac {n ^ {2}} {2 \ sigma ^ { 2}}}}}$$ Это легко распространяется на сигнал размера M (при условии, что он остается постоянным для всех измерений и):${\ displaystyle \ sigma}$${\ displaystyle \ mu _ {1} = \ mu _ {2} =... = \ mu _ {M} = 0}$ $${\ displaystyle G (n_ {1}, n_ {2},..., n_ {M}) = {\ frac {1} {(2 \ pi) ^ {M / 2} \ sigma ^ {M}} } e ^ {- {\ frac {({n_ {1}} ^ {2} + {n_ {2}} ^ {2} +... + {n_ {M}} ^ {2})} {2 \ sigma ^ {2}}}}}$$ Одно важное свойство, которое следует признать, заключается в том, что сигнал размерности M отделим, так что: $${\ Displaystyle G (n_ {1}, n_ {2},..., n_ {M}) = G (n_ {1}) G (n_ {2})... G (n_ {M})}$$ Тогда свертка Гаусса с дискретными сигналами может быть выражена следующим образом:

${\ Displaystyle у (п) = х (п) * г (п)}$

${\ displaystyle y (n_ {1}, n_ {2},..., n_ {M}) = x (n_ {1}, n_ {2},..., n_ {M}) *... * G (n_ {1}, n_ {2},..., n_ {M})}$

Аппроксимация КИХ-фильтром

Гауссова свертка может быть эффективно аппроксимирована с помощью фильтра с конечной импульсной характеристикой (FIR). Фильтр будет разработан с усеченными версиями Гаусса. Для двумерного фильтра передаточная функция такого фильтра будет определяться следующим образом:

${\ displaystyle H (z_ {1}, z_ {2}) = {\ frac {1} {s (r_ {1}, r_ {2})}} \ sum _ {n_ {1} = - r_ {1 }} ^ {r_ {1}} \ sum _ {n_ {2} = - r_ {2}} ^ {r_ {2}} G (n_ {1}, n_ {2}) {z_ {1}} ^ {-n_ {1}} {z_ {2}} ^ {- n_ {2}}}$

куда

${\ displaystyle s (r_ {1}, r_ {2}) = \ sum _ {n_ {1} = - r_ {1}} ^ {r_ {1}} \ sum _ {n_ {2} = - r_ { 2}} ^ {r_ {2}} G (n_ {1}, n_ {2})}$

Выбор более низких значений для и приведет к выполнению меньшего количества вычислений, но даст менее точное приближение, тогда как выбор более высоких значений даст более точное приближение, но потребует большего количества вычислений. ${\ displaystyle r_ {1}}$${\ displaystyle r_ {2}}$

Аппроксимация коробчатым фильтром

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

${\ Displaystyle H (z) = {\ frac {1} {2r + 1}} {\ frac {z ^ {r} -z ^ {- r-1}} {1-z ^ {-} 1}} }$

Обычно рекурсивные проходы выполняются 3, 4 или 5 раз, чтобы получить точное приближение. Предлагаемый метод вычисления r будет выглядеть следующим образом:

${\ displaystyle \ sigma ^ {2} = {\ frac {1} {12}} K ((2r + 1) ^ {2} -1)}$ где K - количество рекурсивных проходов через фильтр.

Затем, поскольку распределение Гаусса разделяется по разным измерениям, из этого следует, что рекурсивное прохождение через одномерные фильтры (изолируя каждое измерение отдельно), таким образом, даст приближение многомерной свертки Гаусса. То есть M- мерная гауссова свертка может быть аппроксимирована рекурсивными проходами через следующие одномерные фильтры:

${\ Displaystyle H (z_ {1}) = {\ frac {1} {2r_ {1} +1}} {\ frac {{z_ {1}} ^ {r_ {1}} - {z_ {1}} ^ {- r_ {1} -1}} {1- {z_ {1}} ^ {-} 1}}}$

${\ displaystyle H (z_ {2}) = {\ frac {1} {2r_ {2} +1}} {\ frac {{z_ {2}} ^ {r_ {2}} - {z_ {2}} ^ {- r_ {2} -1}} {1- {z_ {2}} ^ {-} 1}}}$

${\ displaystyle \ vdots}$

${\ displaystyle H (z_ {M}) = {\ frac {1} {2r_ {M} +1}} {\ frac {{z_ {M}} ^ {r_ {M}} - {z_ {M}} ^ {- r_ {M} -1}} {1- {z_ {M}} ^ {-} 1}}}$

Приложения

Гауссовы свертки широко используются при обработке сигналов и изображений. Например, размытие изображения может быть выполнено с помощью свертки по Гауссу, где параметр будет управлять силой размытия. Таким образом, более высокие значения будут соответствовать более размытому конечному результату. Он также обычно используется в приложениях компьютерного зрения, таких как масштабно-инвариантное преобразование признаков (SIFT). ${\ displaystyle \ sigma}$

• Свертка
• Ядро (обработка изображений)
• Обработка сигнала