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

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

Определение

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

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

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

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

$\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})$

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

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

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

Коммутативное свойство:

$x**h=h**x$

Ассоциированная недвижимость:

$(x**h)**g=x**(h**g)$

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

$x**(h+g)=(x**h)+(x**g)$

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

$w=x**h$

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

$y=w**g=(x**h)**g$

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

$y=x**(h**g)$

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

$h_{eq}=h**g$

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

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

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

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

$y=(x**h)+(x**g)$

С помощью распределительного закона показано, что:

$y=x**(h+g)$

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

$h_{eq}=h+g$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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})$

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

$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 )}$

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

$x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}$

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

$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 ]}$

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

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

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

${\begin{aligned}y(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})\\&=\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})\\&=\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{aligned}}$

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

${\begin{aligned}y(n_{1}+\delta ,n_{2})&=\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 ]}\\&=\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 ]}\end{aligned}}$

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

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

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

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

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

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

Круговая свертка дискретнозначных многомерных сигналов

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

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

Для одномерных сигналов Теорема о свертке утверждает, что преобразование Фурье свертки между двумя сигналами равно произведению преобразований Фурье этих двух сигналов. Таким образом, свертка во временной области равна умножению в частотной области. Математически этот принцип выражается следующим образом: $$y(n)=h(n)*x(n)\longleftrightarrow Y(\omega )=H(\omega )X(\omega )$$Этот принцип напрямую распространяется на работу с сигналами многих измерений. $$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})$$ Это свойство легко расширяется до использования с дискретным преобразованием Фурье (ДПФ) следующим образом (обратите внимание, что линейная свертка заменяется круговой сверткой, где $\otimes$ используется для обозначения операции круговой свертки размером $N$):

$y(n)=h(n)\otimes x(n)\longleftrightarrow Y(k)=H(k)X(k)$

При работе с сигналами нескольких измерений: $$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})$$Круговые извилины здесь будут размером $N_{1},N_{2},...,N_{M}$.

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

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

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

Выбор размера DFT, чтобы избежать наложения

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

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

Регион поддержки $x(n_{1},n_{2})$ является $0\leq n_{1}\leq P_{1}-1$ и $0\leq n_{2}\leq P_{2}-1$ и регион поддержки $h(n_{1},n_{2})$ является $0\leq n_{1}\leq Q_{1}-1$ и $0\leq n_{2}\leq Q_{2}-1$.

Линейная свертка этих двух сигналов будет иметь вид: $$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})$$Учитывая регионы поддержки $x(n_{1},n_{2})$ и $h(n_{1},n_{2})$, регион поддержки $y_{linear}(n_{1},n_{2})$ тогда будет дано следующее:

$$0\leq n_{1}\leq P_{1}+Q_{1}-1$$$$0\leq n_{2}\leq P_{2}+Q_{2}-1$$На основе областей поддержки двух сигналов, ДПФ размера $N_{1}\times N_{2}$ необходимо использовать там, где $N_{1}\geq \max(P_{1},Q_{1})$ и $N_{2}\geq \max(P_{2},Q_{2})$ поскольку для обоих сигналов необходимо использовать ДПФ одинакового размера. Если требуется размер ДПФ, превышающий размер сигнала, сигнал дополняется нулями до тех пор, пока не достигнет требуемой длины. После умножения ДПФ и получения обратного ДПФ результата результирующая круговая свертка определяется следующим образом:

$y_{circular}(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 ]}$ для $(n_{1},n_{2})\in R_{N_{1}N_{2}}$

$R_{N_{1}N_{2}}\triangleq \{(n_{1},n_{2}):0\leq n_{1}\leq N_{1}-1,0\leq n_{2}\leq N_{2}-1\}$

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

$y_{circular}(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 {\,\,\,for\,\,\,} }(n_{1},n_{2})\in R_{N_{1}N_{2}}$

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

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

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

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

$y_{circular}(n_{1},n_{2})=y_{linear}(n_{1},n_{2})$ для $(n_{1},n_{2})\in R_{N_{1}N_{2}}$

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

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

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

Перекрыть и добавить

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

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

$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})$

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

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

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

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

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

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

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

Подставляя вместо $x(n_{1},n_{2})$ приводит к следующему:

$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})$

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

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

Позволять $h(n_{1},n_{2})$ быть большого размера $M_{1}\times M_{2}$:

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

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

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

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

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

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

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

Свертка каждого компонента с выделенными перекрывающимися частями

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

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

$(N/2)$ $+$$(N/8)$ $-$$1$ = $(5/8)N-1$

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

Перекрыть и сохранить

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

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

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

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

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

Позволять $h(n_{1},n_{2})$ быть большого размера $M_{1}\times M_{2}$:

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

Спиралевидное преобразование

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

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

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

$Z(i,j)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}X(m,n)Y(i-m,j-n)$

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

$\mathbf {X'} ={\begin{bmatrix}X&0\\0&0\\\end{bmatrix}}$ и $\mathbf {Y'} ={\begin{bmatrix}Y&0\\0&0\\\end{bmatrix}}$

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

$l_{X''}=$ $(M+K-1)$$\times$$(N-1)$ + $M$

$l_{Y''}=$$(M+K-1)$$\times$$(L-1)$ + $K$

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

$l_{Z''}=$ $l_{Y''}+$$l_{X''}$ $=(M+K-1)$$\times$$(N+L-1)$

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

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

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

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

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

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

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

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

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

$h(n)=-1,0,...,0,-1,4,-1,0,...,0,-1,0,...$

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

Приложения

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

Гауссова свертка

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

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

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

$y(n)=x(n)*G(n)$

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

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

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

$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}}$

где

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

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

Приближение коробчатым фильтром

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

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

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

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

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

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

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

$\vdots$

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

Приложения

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

См. также

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