Гексагональное быстрое преобразование Фурье - Hexagonal fast Fourier transform

В быстрое преобразование Фурье (БПФ) - важный инструмент в области обработки изображений и сигналов. В гексагональное быстрое преобразование Фурье (HFFT) использует существующие процедуры БПФ для вычисления дискретное преобразование Фурье (DFT) изображений, снятых с помощью шестиугольная выборка.^[1] В шестиугольная сетка служит оптимальной выборкой решетка для изотропно ограниченный диапазон двумерных сигналов и имеет эффективность выборки, которая на 13,4% больше, чем эффективность выборки, полученная из прямоугольных отбор проб.^[2]^[3] Несколько других преимуществ гексагональной выборки включают последовательную связь, более высокую симметрия, больше угловое разрешение, и равноудаленный соседний пиксели.^[4]^[5] Иногда несколько из этих преимуществ сочетаются вместе, тем самым повышая эффективность на 50% с точки зрения вычислений и хранения по сравнению с прямоугольной выборкой.^[3] Несмотря на все эти преимущества гексагональной выборки по сравнению с прямоугольной выборкой, ее применение было ограничено из-за отсутствия эффективной системы координат.^[6] Однако это ограничение было снято с недавней разработкой гексагональной эффективной системы координат (HECS, ранее известной как адресация набора массивов или ASA), которая включает в себя преимущество разделяемого ядра Фурье. Существование разделяемого ядра Фурье для изображения с шестигранной выборкой позволяет использовать существующие процедуры БПФ для эффективного вычисления ДПФ такого изображения.

Предварительные мероприятия

Гексагональная эффективная система координат (HECS)

Представление данных с гексагональной выборкой в виде пары прямоугольных массивов с использованием системы координат HECS

Гексагональная эффективная система координат (ранее известная как адресация набора массивов (ASA)) была разработана на основе того факта, что гексагональная сетка может быть представлена как комбинация двух чередующихся прямоугольных массивов.^[7] К каждому отдельному массиву легко обращаться, используя знакомые целочисленные индексы строк и столбцов, а отдельные массивы различаются одной двоичной координатой. Следовательно, полный адрес любой точки гексагональной сетки можно однозначно представить тремя координатами.

{ Displaystyle (а, г, с) в {0,1 } раз mathbb {Z} раз mathbb {Z}}

где координаты а, р и c представляют массив, строку и столбец соответственно. На рисунке показано, как гексагональная сетка представлена двумя чередующимися прямоугольными массивами в координатах HECS.

Гексагональное дискретное преобразование Фурье

Гексагональное дискретное преобразование Фурье (HDFT) было разработано Mersereau.^[3] и он был преобразован в представление HECS Раммельтом.^[7] Позволять ${ Displaystyle х (а, г, с)}$ быть двумерным гексагонально дискретизированным сигналом, и пусть оба массива имеют размер ${ Displaystyle п раз м}$ . Позволять, ${ Displaystyle X (b, s, d)}$ быть преобразование Фурье изИкс. Уравнение HDFT для прямого преобразования, как показано на ^[7] дан кем-то

{ Displaystyle Икс (Ь, s, d) = сумма _ {а} сумма _ {г} сумма _ {с} х (а, г, с) Е ( cdot)}

где

{ Displaystyle Е ( cdot) = ехр влево [-j пи влево ({ гидроразрыва {(a + 2c) (b + 2d)} {2m}} + { frac {(a + 2r) (b + 2s)} {n}} right) right]}

Обратите внимание, что приведенное выше уравнение разделимо и, следовательно, может быть выражено как

{ Displaystyle X (b, s, d) = f_ {0} (b, s, d) + W ( cdot) f_ {1} (b, s, d)}

где

{ Displaystyle W ( cdot) = exp left [-j pi left ({ frac {b + 2d} {2m}} + { frac {b + 2s} {n}} right) правильно]}

и

{ displaystyle g_ {a} (b, r, d) = sum _ {c} x (a, r, c) exp left (-j2 pi { frac {(c) (b + 2d) } {2m}} right)}

{ displaystyle f_ {a} (b, s, d) = sum _ {r} g_ {a} (b, r, d) exp left (-j2 pi { frac {(r) (b + 2s)} {n}} right)}

Гексагональное быстрое преобразование Фурье (HFFT)

Линейные преобразования ${ displaystyle g_ {a}}$ и ${ displaystyle f_ {a}}$ похожи на прямоугольное ядро Фурье, в котором линейное преобразование применяется по каждому измерению двумерных прямоугольных данных.^[1] Обратите внимание, что каждое из этих уравнений, обсужденных выше, представляет собой комбинацию четырех прямоугольных массивов, которые служат предшественниками HDFT. Два из этих четырех прямоугольных ${ displaystyle g_ {a}}$ термины вносят вклад в подмассив HFFT. Теперь, переключая двоичную координату, мы получаем четыре различных вида уравнений. В,^[7] три из этих четырех выражений были вычислены с использованием того, что автор назвал «нестандартными преобразованиями (NST)» (показано ниже), в то время как одно выражение вычисляется с использованием любого правильного и применимого алгоритма БПФ.

{ displaystyle g_ {a} (0, r, d) = sum _ {c} x (a, r, c) exp left (-j2 pi { frac {(c) (d)} { m}} right)}

{ displaystyle g_ {a} (1, r, d) = sum _ {c} x (a, r, c) exp left (-j2 pi { frac {(c) (2d + 1) } {2m}} right)}

{ displaystyle f_ {a} (0, s, d) = sum _ {r} g_ {a} (a, r, d) exp left (-j2 pi { frac {(r) (2s )} {n}} right)}

{ displaystyle f_ {a} (1, s, d) = sum _ {r} g_ {a} (a, r, d) exp left (-j2 pi { frac {(r) (2s +1)} {n}} right)}

Глядя на второе выражение, ${ displaystyle g_ {a} (1, r, d)}$ , мы видим, что это не более чем стандарт дискретное преобразование Фурье (ДПФ) с постоянным смещением по строкам прямоугольных подматриц шестигранно-дискретизированного изображения ${ Displaystyle х (а, г, с)}$ .^[1] Это выражение - не что иное, как круговое вращение ДПФ. Обратите внимание, что сдвиг должен происходить в целое число образцов в собственность для хранения. Таким образом, функция ${ displaystyle g_ {a}}$ может быть вычислен с использованием стандартного ДПФ за то же количество операций без введения NST.

Если мы посмотрим на 0-массив ${ displaystyle f_ {a}}$ , выражение всегда будет симметричным примерно на половине своего пространственный период. Из-за этого достаточно вычислить только половину. Мы находим, что это выражение является стандартным ДПФ столбцов ${ displaystyle g_ {a}}$ , который прореживается в 2 раза, а затем дублируется, чтобы охватить пространство р для идентичного второго периода комплексной экспоненты.^[1] Математически,

{ displaystyle { begin {align} X _ { text {even}} [k] & = sum _ {n = 0} ^ {N-1} x [n] e ^ {- { tfrac {2j pi} {N}} 2kn} [5pt] & = sum _ {n = 0} ^ {{ tfrac {N} {2}} - 1} x [n] e ^ {- { tfrac { 2j pi} {N / 2}} kn} + sum _ {n = { tfrac {N} {2}}} ^ {N-1} x [n] e ^ {- { tfrac {2j pi} {N / 2}} kn} [5pt] & = sum _ {n = 0} ^ {{ tfrac {N} {2}} - 1} x [n] e ^ {- { tfrac {2j pi} {N / 2}} kn} + sum _ {n = 0} ^ {{ tfrac {N} {2}} - 1} x left [n + { tfrac {N} { 2}} right] e ^ {- { tfrac {2j pi} {N / 2}} kn} [5pt] & = sum _ {n = 0} ^ {{ tfrac {N} { 2}} - 1} left (x [n] + x left [n + { tfrac {N} {2}} right] right) e ^ {- { tfrac {2j pi} {N / 2}} kn} end {выровнен}}}

Выражение для 1-массива ${ displaystyle f_ {a}}$ эквивалентно выражению 0-массива со сдвигом на одну выборку. Следовательно, выражение 1-массива может быть выражено как столбцы ДПФ ${ displaystyle g_ {a}}$ прореживается в два раза, начиная со второй выборки, обеспечивая постоянное смещение, необходимое для 1-массива, а затем удваивается в пространстве, чтобы охватить диапазон s. Так, метод, разработанный Джеймсом Б. Бердсонгом и Николасом Раммельтом в ^[1] способен успешно вычислять HFFT, используя стандартные процедуры FFT, в отличие от предыдущей работы в.^[7]

использованная литература

^ ^а ^б ^c ^d ^е Джеймс Б. Бердсонг, Николас И. Раммельт, «Гексагональное быстрое преобразование Фурье», Международная конференция IEEE по обработке изображений (ICIP), 2016 г., стр. 1809–1812, Дои:10.1109 / ICIP.2016.7532670
^ Д. П. Петерсен и Д. Миддлтон, декабрь 1962 г., "Выборка и реконструкция функций с ограниченным волновым числом в n-мерных евклидовых пространствах", Inf. Контроль, т. 5, вып. 4. С. 279–323.
^ ^а ^б ^c Р. М. Мерсеро, июнь 1979 г., "Обработка гексагонально дискретизированных двумерных сигналов", Proceedings of the IEEE, vol. 67, нет. 6. С. 930–949.
^ X. He и W. Jia, 2005, «Гексагональная структура для интеллектуального зрения», в Proc. 1-й Int. Конф. Информационные и коммуникационные технологии, стр. 52–64.
^ W. E. Snyder, 1999, H. Qi и W. Sander, «Система координат для гексагональных пикселей», в Proc. SPIE Medical Imaging: обработка изображений, т. 3661, стр. 716–727
^ Николас И. Раммельт и Джозеф Н. Уилсон «Адресация набора массивов: технология, обеспечивающая эффективную обработку изображений с шестигранной выборкой», Journal of Electronic Imaging 20 (2), 023012 (1 апреля 2011 г.). https://doi.org/10.1117/1.3589306
^ ^а ^б ^c ^d ^е Николас I. Раммельт, 2010, Адресация набора массивов: обеспечение эффективной обработки изображений с шестигранной выборкой, доктор философии. диссертация, Университет Флориды

[:2-1] а ^б ^c ^d ^е Джеймс Б. Бердсонг, Николас И. Раммельт, «Гексагональное быстрое преобразование Фурье», Международная конференция IEEE по обработке изображений (ICIP), 2016 г., стр. 1809–1812, Дои:10.1109 / ICIP.2016.7532670

[2] Д. П. Петерсен и Д. Миддлтон, декабрь 1962 г., "Выборка и реконструкция функций с ограниченным волновым числом в n-мерных евклидовых пространствах", Inf. Контроль, т. 5, вып. 4. С. 279–323.

[:0-3] а ^б ^c Р. М. Мерсеро, июнь 1979 г., "Обработка гексагонально дискретизированных двумерных сигналов", Proceedings of the IEEE, vol. 67, нет. 6. С. 930–949.

[4] X. He и W. Jia, 2005, «Гексагональная структура для интеллектуального зрения», в Proc. 1-й Int. Конф. Информационные и коммуникационные технологии, стр. 52–64.

[5] W. E. Snyder, 1999, H. Qi и W. Sander, «Система координат для гексагональных пикселей», в Proc. SPIE Medical Imaging: обработка изображений, т. 3661, стр. 716–727

[:9-6] Николас И. Раммельт и Джозеф Н. Уилсон «Адресация набора массивов: технология, обеспечивающая эффективную обработку изображений с шестигранной выборкой», Journal of Electronic Imaging 20 (2), 023012 (1 апреля 2011 г.). https://doi.org/10.1117/1.3589306

[:1-7] а ^б ^c ^d ^е Николас I. Раммельт, 2010, Адресация набора массивов: обеспечение эффективной обработки изображений с шестигранной выборкой, доктор философии. диссертация, Университет Флориды

[1]

[2]

[3]

[4]

[5]

[6]

[7]