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

Гексагональное быстрое преобразование Фурье (HFFT ) - это вариант быстрого преобразования Фурье (FFT), который разработан для использования преимуществ гексагональной выборки.

• 1 Предпосылки
• 2 Предварительные сведения
  • 2.1 Адресация набора массивов
  • 2.2 Гексагональное дискретное преобразование Фурье
• 3 Существующие подходы
• 4 Ссылки

Было доказано, что • гексагональная сетка служит оптимальной решеткой выборки для изотропно ограниченных по полосе двумерных сигналов и имеет эффективность выборки, которая на 13,4% больше по сравнению с эффективность выборки, полученная из прямоугольной выборки. Несколько других преимуществ гексагональной выборки включают согласованность соединений, более высокую симметрию, большее угловое разрешение и эквидистантные соседние пикселей.

Иногда более одного Эти преимущества объединяются, тем самым повышая эффективность вычислений и хранения на 50% по сравнению с прямоугольной выборкой. Несмотря на все эти преимущества гексагональной выборки по сравнению с прямоугольной выборкой, ее применение было ограничено из-за невозможности получить ортогональные строки и столбцы, которые можно преобразовать независимо, как это делается с прямоугольными выборками. По этой причине было разработано эффективное БПФ с разделяемым ядром Фурье с использованием так называемой схемы адресации набора массивов (ASA), которое называется гексагональным быстрым преобразованием Фурье.

Набором массивов адресация

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

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

$(a,\; r,\; c)\; \in \; \{0,\; 1\}\; \times \; Z\; \times \; Z\; \{\backslash \; displaystyle\; (a,\; r,\; c)\; \backslash \; in\; \backslash \; \{0,1\; \backslash \}\; \backslash \; times\; Z\; \backslash \; times\; Z\}$

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

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

Гексагональное дискретное преобразование Фурье (HDFT) было разработано Мерсеро и было преобразовано в представление ASA Раммелтом. Пусть $x\; (a,\; r,\; c)\; \{\backslash \; displaystyle\; x\; (a,\; r,\; c)\}$будет двумерным гексагонально дискретизированным сигналом, и пусть оба массива имеют размер $n\; X\; м\; \{\backslash \; displaystyle\; nXm\}$. Пусть $X\; (b,\; s,\; d)\; \{\backslash \; displaystyle\; X\; (b,\; s,\; d)\}$будет преобразованием Фурье x. Уравнение HDFT для прямого преобразования, как показано в, задается следующим образом:

$X\; (b,\; s,\; d)\; =\; \sum \; a\; \sum \; r\; \sum \; cx\; (a,\; r,\; c)\; E\; (.)\; \{\backslash \; Displaystyle\; X\; (b,\; s,\; d)\; =\; \backslash \; sum\; \_\; \{a\}\; \backslash \; sum\; \_\; \{r\}\; \backslash \; sum\; \_\; \{c\}\; x\; (a,\; r,\; c)\; E\; (.)\}$

где

$E\; (.)\; =\; exp\; [-\; j\; \pi \; ((a\; +\; 2\; c)\; (b\; +\; 2\; d)\; 2\; m\; +\; (a\; +\; 2\; r)\; (b\; +\; 2\; s)\; n)]\; \{\backslash \; displaystyle\; E\; (.)\; =\; exp\; [-j\; \backslash \; pi\; (\{\backslash \; frac\; \{(a\; +\; 2c)\; (b\; +\; 2d)\}\; \{2m\}\}\; +\; \{\backslash \; frac\; \{(a\; +\; 2r)\; (b\; +\; 2s)\}\; \{n\}\})]\}$

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

$Икс\; (b,\; s,\; d)\; =\; f\; 0\; (b,\; s,\; d)\; +\; W\; (.)\; f\; 1\; (b,\; s,\; d)\; \{\backslash \; displaystyle\; X\; (b,\; s,\; d)\; =\; f\_\; \{0\}\; (b,\; s,\; d)\; +\; W\; (.)\; f\_\; \{1\}\; (b,\; s,\; d)\}$

где

$W\; (.)\; =\; exp\; [-\; j\; \pi \; (b\; +\; 2\; d\; 2\; m\; +\; b\; +\; 2\; sn)]\; \{\backslash \; displaystyle\; W\; (.)\; =\; Exp\; [-j\; \backslash \; pi\; (\{\backslash \; frac\; \{b\; +\; 2d\}\; \{2m\}\}\; +\; \{\backslash \; frac\; \{b\; +\; 2s\}\; \{n\; \}\})]\}$

и

$ga\; (b,\; r,\; d)\; =\; \sum \; cx\; (a,\; r,\; c)\; exp\; (-\; j\; 2\; \pi \; (c)\; (b\; +\; 2\; d)\; 2\; m)\; \{\backslash \; displaystyle\; g\_\; \{a\}\; (b,\; r,\; d)\; =\; \backslash \; sum\; \_\; \{c\}\; x\; (a,\; r,\; c)\; exp\; (-j2\; \backslash \; pi\; \{\backslash \; frac\; \{(c)\; (b\; +\; 2d)\}\; \{2m\}\})\}$

$fa\; (b,\; s,\; d)\; =\; \sum \; rga\; (b,\; r,\; d)\; exp\; (-\; j\; 2\; \pi \; (r)\; (b\; +\; 2\; s)\; n)\; \{\backslash \; displaystyle\; f\; \_\; \{a\}\; (b,\; s,\; d)\; =\; \backslash \; sum\; \_\; \{r\}\; g\_\; \{a\}\; (b,\; r,\; d)\; exp\; (-j2\; \backslash \; pi\; \{\backslash \; frac\; \{(r)\; (b\; +\; 2s)\}\; \{n\; \}\})\}$

Линейные преобразования $ga\; \{\backslash \; displaystyle\; g\_\; \{a\}\}$и $fa\; \{\backslash \; displaystyle\; f\_\; \{a\}\}$аналогичны прямоугольному ядру Фурье, где линейное преобразование применяется по каждому измерению двумерных прямоугольных данных. Обратите внимание, что каждое из этих уравнений, обсужденных выше, представляет собой комбинацию четырех прямоугольных массивов, которые служат предшественниками HDFT. Два из этих четырех прямоугольных элементов $g\; a\; \{\backslash \; displaystyle\; g\_\; \{a\}\}$вносят вклад в подматрицу HFFT. Теперь, переключая двоичную координату, мы получаем четыре различных вида уравнений. На фиг.3 три из этих четырех выражений были вычислены с использованием нестандартных преобразований (NST), в то время как одно выражение вычислено с использованием любого правильного и применимого алгоритма БПФ.

$ga\; (0,\; r,\; d)\; =\; \sum \; сх\; (a,\; r,\; c)\; exp\; (-\; j\; 2\; \pi \; (c)\; (d)\; m)\; \{\backslash \; displaystyle\; g\_\; \{a\}\; (0,\; r,\; d)\; =\; \backslash \; sum\; \_\; \{c\}\; x\; (a,\; r,\; c)\; exp\; (-j2\; \backslash \; pi\; \{\backslash \; frac\; \{(c)\; (d)\}\; \{m\}\})\}$

$ga\; (1,\; r,\; d)\; =\; \sum \; сх\; (a,\; r,\; c)\; ехр\; (-\; j\; 2\; \pi \; (c)\; (2\; d\; +\; 1)\; 2\; m)\; \{\backslash \; displaystyle\; g\_\; \{a\}\; (1,\; r,\; d)\; =\; \backslash \; sum\; \_\; \{c\}\; x\; (a,\; r,\; c)\; exp\; (-j2\; \backslash \; pi\; \{\backslash \; frac\; \{(c)\; (2d\; +\; 1)\}\; \{2m\}\})\}$

$fa\; (0,\; s,\; d)\; =\; \sum \; rga\; (a,\; r,\; d)\; ехр\; (-\; J\; 2\; \pi \; (г)\; (2\; s)\; п)\; \{\backslash \; Displaystyle\; F\_\; \{а\}\; (0,\; s,\; d)\; =\; \backslash \; сумма\; \_\; \{г\}\; g\_\; \{а\}\; (а,\; г,\; d)\; ехр\; (\; -j2\; \backslash \; pi\; \{\backslash \; frac\; \{(r)\; (2s)\}\; \{n\}\})\}$

$fa\; (1,\; s,\; d)\; =\; \sum \; rga\; (a,\; r,\; d)\; exp\; (-\; j\; 2\; \pi \; (r)\; (2\; s\; +\; 1)\; n)\; \{\backslash \; displaystyle\; f\_\; \{a\}\; (1,\; s,\; d)\; =\; \backslash \; sum\; \_\; \{r\}\; g\_\; \{a\}\; (a,\; r,\; d)\; exp\; (-j2\; \backslash \; pi\; \{\backslash \; frac\; \{(r)\; (2s\; +\; 1)\}\; \{n\}\})\}$

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

Если мы посмотрим на 0-массив $fa\; \{\backslash \; displaystyle\; f\_\; \{a\}\}$, выражение всегда будет симметричным примерно на половине своего пространственного периода. Из-за этого достаточно вычислить только половину. Мы обнаружили, что это выражение является стандартным ДПФ столбцов $ga\; \{\backslash \; displaystyle\; g\_\; \{a\}\}$, которое прореживается с коэффициентом 2, а затем дублируется, чтобы охватить пространство r для идентичного второго периода комплексной экспоненты. Математически

$X\; даже\; [k]\; =\; \sum \; N\; =\; 0\; N\; -\; 1\; x\; [n]\; e\; -\; 2\; j\; \pi \; N\; 2\; kn\; \{\backslash \; displaystyle\; X\_\; \{even\}\; [k]\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\; [n]\; e\; ^\; \{-\; \{\backslash \; tfrac\; \{2j\; \backslash \; pi\}\; \{N\}\}\; 2kn\}\}$

$=\; \sum \; n\; =\; 0\; N\; 2\; -\; 1\; x\; [n]\; e\; -\; 2\; j\; \pi \; N\; /\; 2\; кн\; +\; \sum \; N\; знак\; равно\; N\; 2\; N\; -\; 1\; Икс\; [N]\; е\; -\; 2\; J\; \pi \; N\; /\; 2\; кн\; \{\backslash \; displaystyle\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\{\backslash \; tfrac\; \{N\}\; \{2\}\}\; -\; 1\}\; x\; [n]\; e\; ^\; \{-\; \{\backslash \; tfrac\; \{2j\; \backslash \; pi\}\; \{N\; /\; 2\}\}\; kn\}\; +\; \backslash \; sum\; \_\; \{n\; =\; \{\backslash \; tfrac\; \{N\}\; \{2\}\}\}\; ^\; \{N-1\}\; x\; [n]\; e\; ^\; \{-\; \{\backslash \; tfrac\; \{2j\; \backslash \; pi\}\; \{N\; /\; 2\}\}\; kn\}\}$

$=\; \sum \; n\; =\; 0\; N\; 2\; -\; 1\; x\; [n]\; e\; -\; 2\; j\; \pi \; N\; /\; 2\; kn\; +\; \sum \; N\; знак\; равно\; 0\; N\; 2\; -\; 1\; Икс\; [N\; +\; N\; 2]\; е\; -\; 2\; J\; \pi \; N\; /\; 2\; Kn\; \{\backslash \; Displaystyle\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\{\backslash \; tfrac\; \{N\}\; \{2\}\}\; -\; 1\}\; x\; [n]\; e\; ^\; \{-\; \{\backslash \; tfrac\; \{2j\; \backslash \; pi\}\; \{N\; /\; 2\}\}\; kn\}\; +\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\{\backslash \; tfrac\; \{N\}\; \{2\}\}\; -\; 1\}\; x\; [n\; +\; \{\backslash \; frac\; \{N\}\; \{2\}\}]\; e\; ^\; \{-\; \{\backslash \; tfrac\; \{2j\; \backslash \; pi\}\; \{N\; /\; 2\}\}\; kn\}\}$

$=\; \sum \; n\; =\; 0\; N\; 2\; -\; 1\; (x\; [\; n]\; +\; x\; [n\; +\; N\; 2])\; е\; -\; 2\; j\; \pi \; N\; /\; 2\; kn\; \{\backslash \; displaystyle\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\{\backslash \; tfrac\; \{N\}\; \{2\}\}\; -\; 1\}\; (x\; [\; n]\; +\; x\; [n\; +\; \{\backslash \; tfrac\; \{N\}\; \{2\}\}])\; e\; ^\; \{-\; \{\backslash \; tfrac\; \{2j\; \backslash \; pi\}\; \{N\; /\; 2\}\}\; kn\}\}$

Выражение для 1-массива $fa\; \{\backslash \; displaystyle\; f\_\; \{a\}\}$эквивалентно 0-массивному выражению со сдвигом на одну выборку. Следовательно, выражение с 1 массивом может быть выражено как столбцы ДПФ $ga\; \{\backslash \; displaystyle\; g\_\; \{a\}\}$, прореженные в два раза, начиная со второй выборки, обеспечивающей необходимое постоянное смещение. на 1-массив, а затем удвоился в пространстве, чтобы охватить диапазон s. Таким образом, метод, разработанный Джеймсом Б. Бердсонгом и Николасом И. Раммелтом, позволяет успешно вычислять HFFT с использованием стандартных процедур FFT, в отличие от предыдущей работы в.