Шестиугольное быстрое преобразование Фурье

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

Предварительные сведения

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

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

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

(a,r,c)\in \{0,1\}\times \mathbb {Z} \times \mathbb {Z}

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

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

Шестиугольное дискретное преобразование Фурье (HDFT) было разработано Мерсеро. ^[3] и оно было преобразовано в представление HECS компанией Rummelt. ^[7] Позволять $x(a,r,c)$ быть двумерным сигналом с шестиугольной выборкой, и пусть оба массива имеют размер $n\times m$ . Позволять, $X(b,s,d)$ быть Фурье преобразованием x. Уравнение HDFT для прямого преобразования, как показано на рисунке. ^[7] дается

X(b,s,d)=\sum _{a}\sum _{r}\sum _{c}x(a,r,c)E(\cdot )

где

E(\cdot )=\exp \left[-j\pi \left({\frac {(a+2c)(b+2d)}{2m}}+{\frac {(a+2r)(b+2s)}{n}}\right)\right]

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

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

где

W(\cdot )=\exp \left[-j\pi \left({\frac {b+2d}{2m}}+{\frac {b+2s}{n}}\right)\right]

и

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

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

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

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

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

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

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

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

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

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

{\begin{aligned}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{aligned}}

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Джеймс Б. Бердсонг, Николас И. Раммельт, «Гексагональное быстрое преобразование Фурье», Международная конференция IEEE по обработке изображений (ICIP), 2016 г., стр. 1809–1812, два : 10.1109/ICIP.2016.7532670
^ Д. П. Петерсен и Д. Миддлтон, декабрь 1962 г., «Выборка и реконструкция функций с ограниченным волновым числом в n-мерных евклидовых пространствах», Inf. Контроль, том. 5, нет. 4, стр. 279–323.
^ Jump up to: ^а ^б ^с Р. М. Мерсеро, июнь 1979 г., «Обработка двумерных сигналов с гексагональной выборкой», Proceedings of IEEE, vol. 67, нет. 6, стр. 930–949.
^ X. Он и В. Цзя, 2005, «Шестиугольная структура для интеллектуального зрения», в Proc. 1-й Межд. Конф. Информационные и коммуникационные технологии, стр. 52–64.
^ WE 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
^ Jump up to: ^а ^б ^с ^д ^и Николас И. Раммельт, 2010, Адресация набора массивов: обеспечение эффективной обработки изображений с гексагональной выборкой, доктор философии. диссертация, Университет Флориды

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

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

[:0-3] Jump up to: ^а ^б ^с Р. М. Мерсеро, июнь 1979 г., «Обработка двумерных сигналов с гексагональной выборкой», Proceedings of IEEE, vol. 67, нет. 6, стр. 930–949.

[4] X. Он и В. Цзя, 2005, «Шестиугольная структура для интеллектуального зрения», в Proc. 1-й Межд. Конф. Информационные и коммуникационные технологии, стр. 52–64.

[5] WE 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] Jump up to: ^а ^б ^с ^д ^и Николас И. Раммельт, 2010, Адресация набора массивов: обеспечение эффективной обработки изображений с гексагональной выборкой, доктор философии. диссертация, Университет Флориды

[1]

[2]

[3]

[4]

[5]

[6]

[7]