Быстрые алгоритмы для многомерных сигналов

Аналогично одномерной цифровой обработке сигналов в случае многомерной обработки сигналов. ^{[ 1 ]} у нас есть эффективные алгоритмы. Эффективность алгоритма можно оценить по количеству вычислительных ресурсов, необходимых для расчета выходных данных, или по интересующему количеству. На этой странице объясняются два очень эффективных алгоритма для многомерных сигналов. Для простоты описания это объясняется для 2-D сигналов. Однако та же теория справедлива и для сигналов МД. Также упоминается точная экономия вычислений для каждого алгоритма.

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

В случае цифровых систем для описания взаимосвязи ввода-вывода можно использовать математические выражения, а для реализации этой взаимосвязи можно использовать алгоритм. Аналогичным образом могут быть разработаны алгоритмы для реализации различных преобразований, таких как цифровой фильтр , преобразование Фурье , гистограмма , улучшение изображения и т. д. Прямая реализация ^{[ 2 ]} из этих отношений ввода-вывода и преобразований не обязательно является наиболее эффективным способом их реализации.

Когда люди начали вычислять такие результаты на основе входных данных путем прямой реализации, они начали искать более эффективные способы. Цель этой вики-страницы — продемонстрировать такие эффективные и быстрые алгоритмы для многомерных сигналов и систем. Многомерный (MD) сигнал можно смоделировать как функцию M независимых переменных, где M больше или равно 2. Эти сигналы можно разделить на непрерывные, дискретные или смешанные. Непрерывный сигнал можно смоделировать как функцию независимых переменных, которые варьируются в пределах континуума значений, например: звуковая волна, распространяющаяся в пространстве, трехмерные космические волны, измеренные в разное время. С другой стороны, дискретный сигнал можно смоделировать как функцию, определенную только для набора точек, например набора целых чисел. Изображение — это простейший пример двумерного сигнала дискретной области, который является пространственным по своей природе.

В контексте быстрых алгоритмов рассмотрим пример ниже:

Нам нужно вычислить A, которое определяется выражением

A = αγ + αδ + βγ + βδ, где α,β,γ и δ — комплексные переменные.

Чтобы вычислить А, нам нужно 4 комплексных умножения и 3 комплексных сложения. Приведенное выше уравнение можно записать в упрощенной форме как

А = (а + б)(с + г)

Эта форма требует всего 1 комплексного умножения и 2 комплексных сложений.

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

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

Самая простая форма представления системы с инвариантом линейного сдвига (LSI) — это ее импульсный отклик. Выходной сигнал такой дискретной системы LSI определяется сверткой ее входного сигнала и импульсной характеристики системы. Математически это представляется следующим образом:

$y\left(n_{1},n_{2}\right)=\sum _{l_{1}=-\infty }^{+\infty }\sum _{l_{2}=\infty }^{+\infty }x(l_{1},l_{2})h(n_{1}-l_{1},n_{2}-l_{2})$

где $h(n_{1},n_{2})$ это импульсный отклик системы.

Согласно приведенному выше уравнению, чтобы получить выходное значение в определенной точке (скажем, $y(0,0)$ ) нам нужно умножить несколько значений входных данных $x(l_{1},l_{2})$ и импульсный отклик $h(-l_{1},-l_{2})$ . Конечно, это зависит от региона поддержки входа, а также от импульсной характеристики. Здесь следует отметить ключевой момент: нам нужно выполнить очень много сложных умножений и сложений, чтобы получить одно выходное значение.

Предполагая, что двумерный входной сигнал имеет длину $M\times M$ а импульсная характеристика системы имеет длину $N\times N$ нам нужно выполнить $M^{2}N^{2}$ количество умножений для получения всех выходных значений. Выходные данные могут быть вычислены эффективно, если можно использовать некоторые характеристики системы.

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

Прямой расчет двумерного ДПФ — это просто оценка двойной суммы. ^{[ 3 ]}

$X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{1}}^{n_{1}k_{1}}W_{N_{2}}^{n_{2}k_{2}}$ ${\text{ for }}0\leq k_{1}\leq N_{1}-1{\text{ and }}0\leq k_{2}\leq N_{2}-1$

${\text{ where }}W_{N}\equiv {\text{exp}}\left(-j{\frac {2\pi }{N}}\right)$

Общее количество комплексных умножений и комплексных сложений, необходимых для оценки этого двумерного ДПФ путем прямого расчета, равно $N_{1}^{2}N_{2}^{2}$ . Это наивный подход, однако мы уже знаем, что N-точечное 1D ДПФ можно вычислить с гораздо меньшими затратами, чем $N^{2}$ умножения с использованием алгоритма быстрого преобразования Фурье (БПФ). Как описано в следующем разделе, мы также можем разработать быстрые преобразования Фурье для расчета двумерных или многомерных ДПФ. ^{[ 3 ]}

Быстрые алгоритмы для многомерных сигналов

Подход декомпозиции строк и столбцов для оценки ДПФ

Источник: ^{[ 3 ]}

Сумма ДПФ $X\left(k_{1},k_{2}\right)$ в предыдущем уравнении можно также записать в следующем виде

$X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}\left[\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}}\right]W_{N_{1}}^{n_{1}k_{1}}$

Позволять $G\left(n_{1},k_{2}\right)$ обозначают количество внутри скобок и выражаются по формуле:

$G\left(n_{1},k_{2}\right)=\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}}$

$X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}G\left(n_{1},k_{2}\right)W_{N_{1}}^{n_{1}k_{2}}$

Используя этот метод, ДПФ $X$ может быть вычислено как несколько одномерных ДПФ. То есть каждый столбец $G$ можно рассматривать как одномерное ДПФ соответствующего столбца $x$ ( $n_{1}$ = константа). И каждый ряд $X$ является 1-ДПФ соответствующей строки $G$ ( $n_{2}$ = константа). Следовательно, мы вычисляем двумерное ДПФ, разлагая его на ДПФ по строкам и столбцам.

Тот же принцип используется для оценки MD DFT M-мерного сигнала.

Теперь давайте поговорим об экономии вычислительных ресурсов, которую мы получаем при использовании этого подхода. Замечено, что нам требуется $N_{1}N_{2}(N_{1}+N_{2})$ сложные сложения и умножения. Кроме того, если каждое из этих одномерных ДПФ вычисляется с использованием одномерного БПФ, количество комплексных умножений можно дополнительно сократить до $N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}$

Быстрое преобразование Фурье векторного основания

Источник: ^{[ 3 ]}

Как и в случае с 1-D БПФ, в случае 2-D сигналов может быть достигнуто прореживание во времени. 1-D ДПФ сигнала, длина которого равна степени 2, может быть выражена через два ДПФ половинной длины, каждый из которых снова может быть выражен как комбинация ДПФ четверти длины и так далее.

В случае двумерных сигналов мы можем выразить $(N_{1}{\text{ x }}N_{2})$ ДПФ с точки зрения четырех ${\frac {N_{1}}{2}}{\text{ x }}{\frac {N_{2}}{2}}$ ДПФ (при условии, что $N_{1}$ и $N_{2}$ являются степенями 2). Для простоты предположим, что $N_{1}=N_{2}=N$ . Двойную сумму ДПФ можно разложить на четыре отдельных суммирования, одно по этим выборкам. $x$ для чего оба $n_{1}$ и $n_{2}$ четные, такие, для которых $n_{1}$ четный и $n_{2}$ нечетный, тот, для которого $n_{1}$ это странно и $n_{2}$ четный и последний, для которого $n_{1}$ и $n_{2}$ странные.

Это написано как:

 $X\left(k_{1},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$

где

$S_{00}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1},2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}$

$S_{01}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1},2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}$

$S_{10}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1}+1,2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}$

$S_{11}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1}+1,2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}$

Все массивы $S_{00}S_{01}S_{10}$ и $S_{11}$ являются периодическими по $(k_{1},k_{2})$ с горизонтальным и вертикальным периодами ${\frac {N}{2}}$ . Используя этот факт, а также то, что $W_{N}^{N/2}=-1,$ мы можем получить следующие тождества:

$X\left(k_{1},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$

$X\left(k_{1}+{\frac {N}{2}},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$

$X\left(k_{1},k_{2}+{\frac {N}{2}}\right)=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$

$X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}$

Приведенное выше уравнение говорит нам, как вычислить четыре точки ДПФ. $X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)$ за определенную стоимость $(k_{1},k_{2})$ из четырех точек $S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ . $S_{00}(k_{1},k_{2})$ можно получить, оценив $\left({\frac {N}{2}}\times {\frac {N}{2}}\right)$ -точечное ДПФ (аналогично другим $S_{ij}$ можно получить).

Таким образом, мы видим, что $N\times N$ ДПФ можно выразить через четыре ${\frac {N}{2}}\times {\frac {N}{2}}$ ДПФ.

По аналогии с одномерным случаем, вычисление, изображенное на рисунке ниже, называется ${\text{butterfly}}$ или точнее $radix-(2\times 2){\text{ butterfly}}$ .

Каждая бабочка требует трех комплексных умножений и восьми сложных сложений для расчета выходных данных на основе входных данных. И чтобы вычислить все выборки $X$ от $S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})$ это требует расчетов ${\frac {N^{2}}{4}}$ бабочки.

Эта процедура децимации выполняется $\log _{2}N$ времена, когда $N$ представляет собой степень двойки. Каждый этап децимации состоит из ${\frac {N^{2}}{4}}$ бабочки, а каждая бабочка включает в себя три комплексных умножения и восемь комплексных сложений и, следовательно, количество комплексных умножений, которое необходимо выполнить при вычислении $(N\times N)$ -точечная система счисления $(2\times 2)$ БПФ определяется выражением

$C_{vectorRadix(2\times 2)}={\frac {3N^{2}}{4}}\log _{2}N$

См. также

Ссылки

^ Бозе, НК, изд. (1985). Теория многомерных систем, прогресс, направления и открытые проблемы в многомерных системах . Дордрехт, Голландия: Издательство Д. Рейделя.
^ Быстрые алгоритмы обработки сигналов Ричарда Э. Блахута, Cambridge University Press, 2010 г.
^ Jump up to: ^а ^б ^с ^д Дэн Э. Даджен, Рассел М. Мерсеро, «Многомерная цифровая обработка сигналов», Серия Prentice-Hall Signal Processing, ISBN 0136049591 , 1983.

[1] Бозе, НК, изд. (1985). Теория многомерных систем, прогресс, направления и открытые проблемы в многомерных системах . Дордрехт, Голландия: Издательство Д. Рейделя.

[fa-2] Быстрые алгоритмы обработки сигналов Ричарда Э. Блахута, Cambridge University Press, 2010 г.

[dm-3] Jump up to: ^а ^б ^с ^д Дэн Э. Даджен, Рассел М. Мерсеро, «Многомерная цифровая обработка сигналов», Серия Prentice-Hall Signal Processing, ISBN 0136049591 , 1983.

[ 1 ]

[ 2 ]

[ 3 ]