Šestihranná rychlá Fourierova transformace - Hexagonal fast Fourier transform

Rychlá Fourierova transformace (FFT) je důležitým nástrojem v oblasti obrazu a zpracování signálu. Šestihranný rychlá Fourierova transformace ( HFFT ) využívá stávající FFT rutiny spočítat diskrétní Fourierova transformace (DFT) obrazů, které byly zachyceny s šestibokou vzorkování . Hexagonální mřížky slouží jako optimální vzorkovací mřížky pro izotropicky pásmu omezené dvourozměrné signály a má účinnost vzorkování, které je o 13,4% vyšší než účinnost odběru vzorků získaných z obdélníkového vzorku . Několik dalších výhod hexagonálního vzorkování zahrnuje konzistentní připojení, vyšší symetrii , větší úhlové rozlišení a ekvidistantní sousední pixely . Někdy se spojuje více než jedna z těchto výhod, čímž se ve srovnání s obdélníkovým vzorkováním zvyšuje účinnost o 50%, pokud jde o výpočet a skladování. Přes všechny tyto výhody hexagonálního vzorkování oproti obdélníkovému vzorkování byla jeho aplikace omezena z důvodu nedostatku efektivního souřadnicového systému. Toto omezení však bylo odstraněno nedávným vývojem hexagonálního efektivního souřadnicového systému (HECS, dříve známého jako adresování sady polí nebo ASA), který zahrnuje výhodu oddělitelného Fourierova jádra. Existence oddělitelného Fourierova jádra pro šestihranně vzorkovaný obraz umožňuje použití existujících FFT rutin k efektivnímu výpočtu DFT takového obrazu.

Předkola

Hexagonal Efficient Coordinate System (HECS)

Reprezentace hexagonálně vzorkovaných dat jako dvojice obdélníkových polí pomocí souřadnicového systému HECS

Hexagonal efficient coordinate system (formerly known as array set addressing (ASA)) was developed based on the fact that a hexagonal grid can be represented as a combination of two interleaved rectangular arrays. Je snadné adresovat každé jednotlivé pole pomocí známých celočíselných indexů řádků a sloupců a jednotlivá pole se odlišují jedinou binární souřadnicí. Proto může být úplná adresa libovolného bodu v hexagonální mřížce jedinečně reprezentována třemi souřadnicemi.

${\ displaystyle (a, r, c) \ v \ {0,1 \} \ krát \ mathbb {Z} \ krát \ mathbb {Z}}$

kde souřadnice , r a c představují pole, řádků a sloupců, resp. Obrázek ukazuje, jak je hexagonální mřížka reprezentována dvěma prokládanými obdélníkovými poli v souřadnicích HECS.

Hexagonální diskrétní Fourierova transformace

Šestiúhelníková diskrétní Fourierova transformace (HDFT) byla vyvinuta společností Mersereau a byla převedena na reprezentaci HECS společností Rummelt. Dovolit být dvourozměrný hexagonálně vzorkovaný signál a nechat obě pole mít velikost . Nechť je Fourierova transformace of  x. Rovnice HDFT pro dopřednou transformaci, jak je znázorněna, je dána vztahem ${\ displaystyle x (a, r, c)}$${\ displaystyle n \ krát m}$${\ displaystyle X (b, s, d)}$

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

kde

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

Všimněte si, že výše uvedená rovnice je oddělitelná, a proto ji lze vyjádřit jako

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

kde

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

a

${\ displaystyle g_ {a} (b, r, d) = \ součet _ {c} x (a, r, c) \ exp \ left (-j2 \ pi {\ frac {(c) (b + 2d) } {2m}} \ vpravo)}$

${\ displaystyle f_ {a} (b, s, d) = \ součet _ {r} g_ {a} (b, r, d) \ exp \ left (-j2 \ pi {\ frac {(r) (b + 2 s)}} {n}} \ vpravo)}$

Šestihranná rychlá Fourierova transformace (HFFT)

Lineární transformace a jsou podobné obdélníkovému Fourierovu jádru, kde je lineární transformace aplikována podél každé dimenze 2-D obdélníkových dat. Všimněte si, že každá z těchto rovnic, diskutovaná výše, je kombinací čtyř obdélníkových polí, která slouží jako předchůdci HDFT. Dva z těchto čtyř pravoúhlých výrazů přispívají k dílčímu poli HFFT. Nyní přepnutím binární souřadnice máme čtyři různé formy rovnic. V roce byly tři z těchto čtyř výrazů hodnoceny pomocí toho, co autor nazval „nestandardní transformace (NST)“ (viz níže), zatímco jeden výraz je vypočítán pomocí jakéhokoli správného a použitelného algoritmu FFT. ${\ displaystyle g_ {a}}$${\ displaystyle f_ {a}}$${\ displaystyle g_ {a}}$

${\ displaystyle g_ {a} (0, r, d) = \ součet _ {c} x (a, r, c) \ exp \ left (-j2 \ pi {\ frac {(c) (d)} { m}} \ vpravo)}$

${\ displaystyle g_ {a} (1, r, d) = \ součet _ {c} x (a, r, c) \ exp \ left (-j2 \ pi {\ frac {(c) (2d + 1) } {2m}} \ vpravo)}$

${\ displaystyle f_ {a} (0, s, d) = \ součet _ {r} g_ {a} (a, r, d) \ exp \ left (-j2 \ pi {\ frac {(r) (2 s )} {n}} \ vpravo)}$

${\ displaystyle f_ {a} (1, s, d) = \ součet _ {r} g_ {a} (a, r, d) \ exp \ left (-j2 \ pi {\ frac {(r) (2 s +1)} {n}} \ vpravo)}$

Při pohledu na druhý výraz vidíme, že to není nic jiného než standardní diskrétní Fourierova transformace (DFT) s konstantním posunem podél řad obdélníkových dílčích polí hexagonálně vzorkovaného obrazu . Tento výraz není nic jiného než kruhová rotace DFT. Všimněte si, že k posunu musí dojít v celočíselném počtu vzorků, aby byla vlastnost držena. Tímto způsobem lze funkci vypočítat pomocí standardního DFT, ve stejném počtu operací, bez zavedení NST. ${\ displaystyle g_ {a} (1, r, d)}$${\ displaystyle x (a, r, c)}$${\ displaystyle g_ {a}}$

Pokud se podíváme na pole 0 , bude výraz vždy symetrický přibližně v polovině jeho prostorové periody . Z tohoto důvodu stačí vypočítat pouze polovinu z toho. Zjistili jsme, že tento výraz je standardní DFT sloupců , který je zdecimován faktorem 2 a poté je duplikován, aby překlenul prostor r pro stejnou druhou periodu komplexního exponenciálu. Matematicky, ${\ displaystyle f_ {a}}$${\ displaystyle g_ {a}}$

Analýza se nezdařila (MathML s využitím SVG nebo PNG (doporučeno pro moderní prohlížeče a nástroje přístupnosti)): Neplatná odpověď („Matematické rozšíření se nemůže připojit k Restbase.“) Ze serveru „/ mathoid / local / v1 /“ :): {\ 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 {zarovnat}}

Výraz pro pole 1 je ekvivalentní výrazu pole 0 s posunem o jeden vzorek. Proto může být výraz 1-pole vyjádřen jako sloupce DFT decimovaný faktorem dva, počínaje druhým vzorkem poskytujícím konstantní posun potřebný pro 1-pole, a poté zdvojnásoben v prostoru, aby se rozprostřel rozsah s . Metoda vyvinutá Jamesem B. Birdsongem a Nicholasem I. Rummeltem je tedy schopna úspěšně vypočítat HFFT pomocí standardních FFT rutin na rozdíl od předchozí práce v. ${\ displaystyle f_ {a}}$${\ displaystyle g_ {a}}$

Reference