Transformada hexagonal rápida de Fourier

La transformada rápida de Fourier (FFT) es una herramienta importante en los campos del procesamiento de imágenes y señales. La transformada hexagonal rápida de Fourier ( HFFT ) utiliza rutinas FFT existentes para calcular la transformada discreta de Fourier (DFT) de imágenes que se han capturado con muestreo hexagonal . ^[1] La cuadrícula hexagonal sirve como red de muestreo óptima para señales bidimensionales de banda isotrópica limitada y tiene una eficiencia de muestreo que es un 13,4% mayor que la eficiencia de muestreo obtenida del muestreo rectangular . ^{[2] [3]} Varias otras ventajas del muestreo hexagonal incluyen conectividad consistente, mayor simetría , mayor resolución angular y píxeles vecinos equidistantes . ^{[4] [5]} A veces, más de una de estas ventajas se combinan, aumentando así la eficiencia en un 50% en términos de cálculo y almacenamiento en comparación con el muestreo rectangular. ^[3] A pesar de todas estas ventajas del muestreo hexagonal sobre el muestreo rectangular, su aplicación ha sido limitada debido a la falta de un sistema de coordenadas eficiente. ^[6] Sin embargo, esa limitación se ha eliminado con el reciente desarrollo del sistema de coordenadas eficiente hexagonal (HECS, anteriormente conocido como direccionamiento de conjunto de matrices o ASA), que incluye el beneficio de un núcleo de Fourier separable. La existencia de un núcleo de Fourier separable para una imagen muestreada hexagonalmente permite el uso de rutinas FFT existentes para calcular eficientemente la DFT de dicha imagen.

Preliminares

Sistema de coordenadas eficiente hexagonal (HECS)

Representación de datos muestreados hexagonalmente como un par de matrices rectangulares utilizando el sistema de coordenadas HECS

El sistema de coordenadas eficiente hexagonal (anteriormente conocido como direccionamiento de conjuntos de matrices (ASA)) se desarrolló basándose en el hecho de que una cuadrícula hexagonal se puede representar como una combinación de dos matrices rectangulares entrelazadas. ^[7] Es fácil abordar cada matriz individual utilizando índices familiares de filas y columnas con valores enteros y las matrices individuales se distinguen por una única coordenada binaria. Por lo tanto, una dirección completa para cualquier punto de la cuadrícula hexagonal se puede representar de forma única mediante tres coordenadas.

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

donde las coordenadas a , r y c representan la matriz, fila y columna respectivamente. La figura muestra cómo la cuadrícula hexagonal está representada por dos matrices rectangulares entrelazadas en coordenadas HECS.

Transformada de Fourier discreta hexagonal

La transformada hexagonal discreta de Fourier (HDFT) ha sido desarrollada por Mersereau ^[3] y Rummelt la ha convertido a una representación HECS. ^[7] Sea una señal muestreada hexagonalmente bidimensional y ambas matrices sean de tamaño . Sea, la transformada de Fourier de  x. La ecuación HDFT para la transformada directa como se muestra en ^[7] viene dada por ${\displaystyle x(a,r,c)}$ ${\displaystyle n\times m}$ ${\displaystyle X(b,s,d)}$

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

dónde

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

Tenga en cuenta que la ecuación anterior es separable y, por lo tanto, se puede expresar como

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

dónde

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

y

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

Transformada hexagonal rápida de Fourier (HFFT)

Las transformaciones lineales son similares al núcleo de Fourier rectangular donde se aplica una transformación lineal a lo largo de cada dimensión de los datos rectangulares 2-D. ^[1] Tenga en cuenta que cada una de estas ecuaciones, analizadas anteriormente, es una combinación de cuatro matrices rectangulares que sirven como precursoras de la HDFT. Dos de esos cuatro términos rectangulares contribuyen al subconjunto de HFFT. Ahora, al cambiar la coordenada binaria, tenemos cuatro formas diferentes de ecuaciones. En ^[7] , tres de esas cuatro expresiones se evaluaron utilizando lo que el autor llamó "transformaciones no estándar (NST)" (que se muestran a continuación), mientras que una expresión se calcula utilizando cualquier algoritmo FFT correcto y aplicable. ${\displaystyle g_{a}}$ ${\displaystyle f_{a}}$ ${\displaystyle g_{a}}$

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

Al observar la segunda expresión, vemos que no es más que una transformada de Fourier discreta (DFT) estándar con un desplazamiento constante a lo largo de las filas de subconjuntos rectangulares de una imagen muestreada hexagonalmente . ^[1] Esta expresión no es más que una rotación circular del DFT. Tenga en cuenta que el cambio debe ocurrir en el número entero de muestras para que se mantenga la propiedad. De esta forma, la función se puede calcular utilizando el DFT estándar, en el mismo número de operaciones, sin introducir un NST. ${\displaystyle g_{a}(1,r,d)}$ ${\displaystyle x(a,r,c)}$ ${\displaystyle g_{a}}$

Si echamos un vistazo a la matriz 0 , la expresión siempre será simétrica aproximadamente la mitad de su período espacial . Por esta razón, basta con calcular sólo la mitad. Encontramos que esta expresión es la DFT estándar de las columnas de , que se diezma por un factor de 2 y luego se duplica para abarcar el espacio de r para el segundo período idéntico del exponencial complejo. ^[1] Matemáticamente, ${\displaystyle f_{a}}$ ${\displaystyle g_{a}}$

${\displaystyle {\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}}}$

La expresión para la matriz 1 es equivalente a la expresión de la matriz 0 con un desplazamiento de una muestra. Por lo tanto, la expresión de 1 matriz se puede expresar como columnas de la DFT diezmadas por un factor de dos, comenzando con la segunda muestra que proporciona un desplazamiento constante necesario para 1 matriz, y luego duplicada en el espacio para abarcar el rango de s . Por lo tanto, el método desarrollado por James B. Birdsong y Nicholas I. Rummelt en ^[1] es capaz de calcular con éxito la HFFT utilizando las rutinas FFT estándar a diferencia del trabajo anterior en ^{[7] .} ${\displaystyle f_{a}}$ ${\displaystyle g_{a}}$

Referencias

1. James B. Birdsong, Nicholas I. Rummelt, "La transformada rápida hexagonal de Fourier", Conferencia internacional IEEE sobre procesamiento de imágenes (ICIP) de 2016, págs. 1809-1812, doi :10.1109/ICIP.2016.7532670
2. DP Petersen y D. Middleton, diciembre de 1962, "Muestreo y reconstrucción de funciones limitadas por número de onda en espacios euclidianos de n dimensiones", Inf. Controlar, vol. 5, núm. 4, págs. 279–323
3. RM Mersereau, junio de 1979, "El procesamiento de señales bidimensionales muestreadas hexagonalmente", Actas del IEEE, vol. 67, núm. 6, págs. 930–949
4. X. He y W. Jia, 2005, "Estructura hexagonal para una visión inteligente", en Proc. 1º Int. Conf. Tecnologías de la información y las comunicaciones, págs. 52–64
5. WE Snyder, 1999, H. Qi y W. Sander, "Un sistema de coordenadas para píxeles hexagonales", en Proc. SPIE Medical Imaging: Procesamiento de imágenes, vol. 3661, págs. 716–727
6. Nicholas I. Rummelt y Joseph N. Wilson "Direccionamiento de conjuntos de matrices: tecnología habilitadora para el procesamiento eficiente de imágenes muestreadas hexagonalmente", Journal of Electronic Imaging 20 (2), 023012 (1 de abril de 2011). https://doi.org/10.1117/1.3589306
7. Nicholas I. Rummelt, 2010, Direccionamiento de conjuntos de matrices: habilitación de un procesamiento eficiente de imágenes muestreadas hexagonalmente, Ph.D. tesis, Universidad de Florida