Diskrete Hartley-Transformation - Discrete Hartley transform

Eine diskrete Hartley-Transformation (DHT) ist eine Fourier-bezogene Transformation von diskreten, periodischen Daten ähnlich der diskreten Fourier-Transformation (DFT), mit analogen Anwendungen in der Signalverarbeitung und verwandten Gebieten. Der Hauptunterschied zur DFT besteht darin, dass sie reelle Eingaben in reelle Ausgaben umwandelt, ohne dass komplexe Zahlen intrinsisch beteiligt sind . So wie die DFT das diskrete Analogon der kontinuierlichen Fourier-Transformation (FT) ist, ist die DHT das diskrete Analogon der kontinuierlichen Hartley-Transformation (HT), die 1942 von Ralph VL Hartley eingeführt wurde.

Da es analoge schnelle Algorithmen für die DHT gibt, analog zur schnellen Fourier-Transformation (FFT), wurde die DHT ursprünglich 1983 von Ronald N. Bracewell als effizienteres Rechenwerkzeug für den allgemeinen Fall vorgeschlagen, in dem die Daten rein real sind. Später wurde jedoch argumentiert, dass spezialisierte FFT-Algorithmen für reale Eingaben oder Ausgaben normalerweise mit etwas weniger Operationen gefunden werden können als jeder entsprechende Algorithmus für die DHT.

Definition

Formal ist die diskrete Hartley-Transformation eine lineare, invertierbare Funktion H : R ⁿ → R ⁿ (wobei R die Menge der reellen Zahlen bezeichnet ). Die N reellen Zahlen x ₀ , ..., x _{N −1} werden nach der Formel in die N reellen Zahlen H ₀ , ..., H _{N −1 umgewandelt}

${\displaystyle H_{k}=\sum _{n=0}^{N-1}x_{n}\operatorname {cas} \left({\frac {2\pi }{N}}nk\right) =\sum _{n=0}^{N-1}x_{n}\left[\cos\left({\frac {2\pi }{N}}nk\right)+\sin\left({ \frac{2\pi}{N}}nk\right)\right]\quad \quad k=0,\dots,N-1.}$

Die Kombination wird manchmal als cas( z ) bezeichnet und sollte nicht mit cis( z ) = e ^iz = cos( z ) + i  sin( z ) oder e ^{− iz} = cis(− z ) verwechselt werden, die in der DFT vorkommt Definition (wobei i die imaginäre Einheit ist ). ${\displaystyle \cos(z)+\sin(z)}$ ${\displaystyle ={\sqrt {2}}\cos \left(z-{\frac {\pi}{4}}\right)}$

Wie bei der DFT sind der Gesamtskalenfaktor vor der Transformation und das Vorzeichen des Sinusterms Konventionssache. Obwohl diese Konventionen gelegentlich von Autor zu Autor variieren, haben sie keinen Einfluss auf die wesentlichen Eigenschaften der Transformation.

Eigenschaften

Die Transformation kann als Multiplikation des Vektors ( x ₀ , ...., x _{N −1} ) mit einer N- mal- N- Matrix interpretiert werden ; daher ist die diskrete Hartley-Transformation ein linearer Operator . Die Matrix ist invertierbar; die inverse Transformation, die es ermöglicht, x _n aus H _{k zurückzugewinnen} , ist einfach die DHT von H _k multipliziert mit 1/ N . Das heißt, das DHT ist bis auf einen Gesamtskalierungsfaktor seine eigene Umkehrung ( involutorisch ).

Die DHT kann verwendet werden, um die DFT zu berechnen und umgekehrt. Für reelle Eingaben x _n hat die DFT-Ausgabe X _k einen Realteil ( H _k + H _{N – k} )/2 und einen Imaginärteil ( H _{N – k} – H _k )/2. Umgekehrt entspricht die DHT der Berechnung der DFT von x _n multipliziert mit 1 +  i , wobei dann der Realteil des Ergebnisses genommen wird.

Wie bei der DFT wird eine zyklische Faltung z = x ∗ y zweier Vektoren x = ( x _n ) und y = ( y _n ), um einen Vektor z = ( z _n ) der Länge N zu erzeugen , zu einer einfachen Operation nach die DHT. Nehmen wir insbesondere an, dass die Vektoren X , Y und Z die DHT von x , y bzw. z bezeichnen. Dann sind die Elemente von Z gegeben durch:

${\displaystyle {\begin{matrix}Z_{k}&=&\left[X_{k}\left(Y_{k}+Y_{Nk}\right)+X_{Nk}\left(Y_{k} -Y_{Nk}\right)\right]/2\\Z_{Nk}&=&\left[X_{Nk}\left(Y_{k}+Y_{Nk}\right)-X_{k}\ left(Y_{k}-Y_{Nk}\right)\right]/2\end{matrix}}}$

wobei wir alle Vektoren als periodisch in N annehmen ( X _N = X ₀ , usw.). So wie die DFT eine Faltung in eine punktweise Multiplikation komplexer Zahlen ( Paare von Real- und Imaginärteilen) umwandelt, transformiert die DHT eine Faltung in eine einfache Kombination von Paaren reeller Frequenzkomponenten. Die inverse DHT liefert dann den gewünschten Vektor z . Auf diese Weise ergibt ein schneller Algorithmus für das DHT (siehe unten) einen schnellen Algorithmus für die Faltung. (Dies ist etwas teurer als das entsprechende Verfahren für die DFT, ohne die Kosten der nachfolgenden Transformationen, da die obige paarweise Operation 8 reelle arithmetische Operationen im Vergleich zu den 6 einer komplexen Multiplikation erfordert. Diese Zählung beinhaltet nicht die Division durch 2, die zB in die 1/ N- Normalisierung des inversen DHT aufgenommen werden kann.)

Schnelle Algorithmen

Ebenso wie für die DFT, direkt die DHT Definition Auswertung erfordern würde O ( N ² ) arithmetische Operationen (siehe Big O - Notation ). Es gibt jedoch schnelle Algorithmen ähnlich der FFT, die das gleiche Ergebnis nur in O( N log N ) Operationen berechnen . Fast jeder FFT-Algorithmus, von Cooley-Tukey über Primfaktor bis Winograd (1985) bis Bruuns (1993), hat ein direktes Analogon für die diskrete Hartley-Transformation. (Allerdings wurden einige der exotischeren FFT-Algorithmen, wie die QFT, noch nicht im Zusammenhang mit der DHT untersucht.)

Insbesondere wird der DHT - Analogon des Cooley-Tukey - Algorithmus , wie die allgemein bekannte schnelle Hartley - Transformation (FHT) Algorithmus und wurde zuerst von Bracewell in 1984. Diesen FHT - Algorithmus beschrieben wird , zumindest , wenn sie angewandt Potenz von zwei Größen N , ist Gegenstand des US- Patents Nr. 4,646,256, das 1987 an die Stanford University erteilt wurde . Stanford hat dieses Patent 1994 gemeinfrei gemacht (Bracewell, 1995).

Wie oben erwähnt, sind DHT-Algorithmen typischerweise etwas weniger effizient (in Bezug auf die Anzahl von Gleitkommaoperationen ) als der entsprechende DFT-Algorithmus (FFT), der auf reale Eingaben (oder Ausgaben) spezialisiert ist. Dies wurde erstmals von Sorensen et al. (1987) und Duhamel & Vetterli (1987). Die letztgenannten Autoren erhielten die scheinbar niedrigste veröffentlichte Operationszahl für die DHT mit Zweierpotenzgrößen, indem sie einen Split-Radix-Algorithmus (ähnlich der Split-Radix-FFT ) verwendeten, der eine DHT der Länge N in eine DHT von . zerlegt Länge N /2 und zwei Real-Input-DFTs ( keine DHTs) der Länge N /4. Auf diese Weise argumentierten sie, dass eine DHT mit einer Zweierpotenz-Länge bestenfalls mit 2 Additionen mehr berechnet werden kann als die entsprechende Anzahl von arithmetischen Operationen für die Real-Input-DFT.

Auf modernen Computern wird die Leistung mehr durch Überlegungen zum Cache und zur CPU-Pipeline bestimmt als durch strikte Betriebszählungen, und ein geringfügiger Unterschied bei den arithmetischen Kosten ist unwahrscheinlich. Da FHT- und Real-Input-FFT-Algorithmen ähnliche Rechenstrukturen aufweisen, scheint keiner von beiden einen wesentlichen Geschwindigkeitsvorteil a priori zu haben ( Popović  [ sr ] und Šević, 1994). Aus praktischen Gründen sind hochoptimierte Real-Input-FFT-Bibliotheken von vielen Quellen erhältlich (zB von CPU-Herstellern wie Intel ), während hochoptimierte DHT-Bibliotheken weniger verbreitet sind.

Andererseits sind die redundanten Berechnungen in FFTs aufgrund von reellen Eingaben für große Primzahlen N schwieriger zu eliminieren , trotz der Existenz von O( N log N ) komplexen Datenalgorithmen für solche Fälle, da die Redundanzen hinter komplizierten Permutationen verborgen sind und/oder Phasendrehungen in diesen Algorithmen. Im Gegensatz dazu kann ein Standard-Prime-Size-FFT-Algorithmus, der Rader-Algorithmus , direkt auf die DHT von realen Daten angewendet werden, was ungefähr einen Faktor von zwei weniger Rechenaufwand erfordert als der der äquivalenten komplexen FFT (Frigo und Johnson, 2005). Andererseits ist auch eine nicht-DHT-basierte Anpassung des Rader-Algorithmus für Real-Input-DFTs möglich (Chu & Burrus , 1982).

Mehrdimensionale diskrete Hartley-Transformation (MD-DHT)

Der rD-DHT (MD-DHT mit "r"-Abmessungen) ist gegeben durch

${\displaystyle X(k_{1},k_{2},...,k_{r})=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_ {2}=0}^{N_{2}-1}\dots \sum_{n_{r}=0}^{N_{r}-1}x(n_{1},n_{2},. ..,n_{r}){\rm {cas}}({\frac {2\pi n_{1}k_{1}}{N_{1}}}+\dots +{\frac {2\pi n_{r}k_{r}}{N_{r}}}),}$

mit und wo${\displaystyle k_{i}=0,1,\ldots ,N_{i}-1}$${\displaystyle {\rm {cas}}(x)=\cos(x)+\sin(x).}$

Ähnlich dem 1-D-Fall ist die MD-DHT als reelle und symmetrische Transformation einfacher als die MD-DFT. Zum einen ist die inverse DHT identisch mit der Vorwärtstransformation, mit der Hinzufügung eines Skalierungsfaktors;

und zweitens vermeidet er, da der Kernel reell ist, die Rechenkomplexität komplexer Zahlen . Außerdem ist die DFT durch eine einfache additive Operation direkt aus der DHT erhältlich (Bracewell, 1983).

Der MD-DHT wird häufig in Bereichen wie der Bild- und optischen Signalverarbeitung eingesetzt. Spezifische Anwendungen umfassen Computer Vision, hochauflösendes Fernsehen und Telekonferenzen, Bereiche, die bewegte Bilder verarbeiten oder analysieren (Zeng, 2000).

Schnelle Algorithmen für das MD-DHT

Da die Rechengeschwindigkeit weiter zunimmt, werden größere mehrdimensionale Probleme rechnerisch durchführbar, was die Notwendigkeit schneller mehrdimensionaler Algorithmen erfordert. Es folgen drei solcher Algorithmen.

Im Streben nach Trennbarkeit für Effizienz betrachten wir die folgende Transformation (Bracewell, 1983):

${\displaystyle {\hat{X}}(k_{1},k_{2},...,k_{r})=\sum_{n_{1}=0}^{N_{1}-1 }\sum_{n_{2}=0}^{N_{2}-1}\dots \sum_{n_{r}=0}^{N_{r}-1}x(n_{1}, n_{2},...,n_{r}){\rm {cas}}({\frac {2\pi n_{1}k_{1}}{N_{1}}})\dots {\ rm {cas}}({\frac {2\pi n_{r}k_{r}}{N_{r}}}).}$

In Bortfeld (1995) wurde gezeigt, dass die beiden durch einige Ergänzungen in Beziehung gesetzt werden können. Zum Beispiel in 3D,

${\displaystyle X(k_{1},k_{2},k_{3})={\frac {1}{2}}[{\hat {X}}(k_{1},k_{2}, -k_{3})+{\hat{X}}(k_{1},-k_{2},k_{3})+{\hat{X}}(-k_{1},k_{2} ,k_{3})-{\hat{X}}(-k_{1},-k_{2},-k_{3})].}$

Für können dann Zeilen-Spalten-Algorithmen implementiert werden. Diese Technik wird aufgrund der Einfachheit solcher RC-Algorithmen häufig verwendet, aber sie sind nicht für allgemeine MD-Räume optimiert. ${\displaystyle {\hat {X}}}$

Andere schnelle Algorithmen wurden entwickelt, wie Radix-2, Radix-4 und Split-Radix. Boussakta (2000) entwickelte beispielsweise die 3D-Vektor-Radix,

${\displaystyle X(k_{1},k_{2},...,k_{r})=\sum_{n_{1}=0}^{N-1}\sum _{n_{2} =0}^{N-1}\sum _{n_{r}=0}^{N-1}x(n_{1},n_{2},n_{3}){\rm {cas}} ({\frac {2\pi }{N}}(n_{1}k_{1}+n_{2}k_{2}+n_{3}k_{3}))}$

${\displaystyle =\sum _{n_{1}:gerade}\sum _{n_{2}:gerade}\sum _{n_{3}:gerade}+\sum _{n_{1}:gerade}\ Summe _{n_{2}:gerade}\sum _{n_{3}:ungerade}+\sum _{n_{1}:gerade}\sum _{n_{2}:ungerade}\sum _{n_{ 3}: gerade}}$

${\displaystyle +\sum _{n_{1}:gerade}\sum _{n_{2}:ungerade}\sum _{n_{3}:ungerade}+\sum _{n_{1}:ungerade}\ Summe _{n_{2}:gerade}\sum _{n_{3}:gerade}+\sum _{n_{1}:ungerade}\sum _{n_{2}:gerade}\sum _{n_{ 3}: ungerade}}$

${\displaystyle +\sum _{n_{1}:ungerade}\sum _{n_{2}:ungerade}\sum _{n_{3}:gerade}+\sum _{n_{1}:ungerade}\ Summe _{n_{2}:ungerade}\sum _{n_{3}:ungerade}.}$

In Boussakta (2000) wurde auch präsentiert, dass dieser 3D-Vektor-Radix-Algorithmus Multiplikationen und Additionen im Vergleich zu Multiplikationen und Additionen aus dem Zeilen-Spalten-Ansatz nimmt. Der Nachteil besteht darin, dass die Implementierung dieser Algorithmen vom Radix-Typ für Signale beliebiger Dimensionen schwer zu verallgemeinern ist. ${\displaystyle ({\frac {7}{4}})N^{3}\log_{2}N}$${\displaystyle ({\frac {31}{8}})N^{3}\log_{2}N}$${\displaystyle 3N^{3}\log_{2}N}$${\displaystyle ({\frac {9}{2}})N^{3}\log_{2}N+3N^{2}}$

Zahlentheoretische Transformationen wurden auch zum Lösen des MD-DHT verwendet, da sie extrem schnelle Faltungen durchführen. In Boussakta (1988) wurde gezeigt, wie man die MD-DHT-Transformation in eine aus Faltungen bestehende Form zerlegt:

Für den 2-D-Fall (der 3-D-Fall wird auch in der angegebenen Referenz behandelt),

${\displaystyle X(k,l)=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x(n,m){\rm {cas} }({\frac {2\pi nk}{N}}+{\frac {2\pi ml}{M}}),\;}$ ${\displaystyle k=0,1,\ldots,N-1}$ , ${\displaystyle l=0,1,\ldots,M-1}$

lässt sich wie folgt in 1-D- und 2-D-Kreisfaltungen zerlegen:

${\displaystyle X(k,l)={\begin{cases}X_{1}(k,0)\\X_{2}(0,l)\\X_{3}(k,l)\end{ Fälle}}}$

wo

${\displaystyle X_{1}(k,0)=\sum_{n=0}^{N-1}(\sum_{m=0}^{M-1}x(n,m)){ \rm{cas}}({\frac{2\pi nk}{N}}),\;}$ ${\displaystyle k=0,1,\ldots,N-1}$

${\displaystyle X_{2}(0,l)=\sum_{m=0}^{M-1}(\sum_{n=0}^{N-1}x(n,m)){ \rm {cas}}({\frac {2\pi ml}{M}}),\;}$ ${\displaystyle l=1,2,\dots,M-1}$

${\displaystyle X_{3}(k,l)=\sum_{n=0}^{N-1}\sum_{m=0}^{M-1}x(n,m){\rm {cas}}({\frac {2\pi nk}{N}}+{\frac {2\pi ml}{M}})\;,}$

${\displaystyle k=1,2,\ldots,N-1}$

${\displaystyle l=1,2,\ldots,M-1.}$

Die Entwicklung weiterer, ${\displaystyle X_{3}}$

${\displaystyle X_{3}(k,l)=\sum_{n=0}^{N-1}x(n,0){\rm {cas}}({\frac {2\pi nk} {N}})+\sum_{m=1}^{M-1}x(0,m){\rm {cas}}({\frac {2\pi ml}{M}})}$

${\displaystyle +\sum _{n=1}^{N-1}\sum _{m=1}^{M-1}x(n,m){\rm {cas}}({\frac { 2\pi nk}{N}}+{\frac {2\pi ml}{M}}).}$

An dieser Stelle stellen wir die Fermat-Zahlentransformation (FNT) vor. Die t- ^te Fermat-Zahl ist gegeben durch , mit . Die bekannten Fermat-Zahlen sind für ( ist eine Primzahl für ), (Boussakta, 1988). Die Fermat-Zahlentransformation ist gegeben durch ${\displaystyle F_{t}=2^{b}+1}$${\displaystyle b=2^{t}}$${\displaystyle t=0,1,2,3,4,5,6}$${\displaystyle F_{t}}$${\displaystyle 0\leq t\leq 4}$

${\displaystyle X(k,l)=\sum _{n=0}^{N-1}\sum _{m=0}^{M-1}x(n,m)\alpha _{1} ^{nk}\alpha_{2}^{ml}\mod F_{t}}$

mit . und sind Wurzeln der Einheit der Ordnung und jeweils . ${\displaystyle k=0,\ldots,N-1,l=0,\ldots,M-1}$${\displaystyle \alpha_{1}}$${\displaystyle \alpha_{2}}$${\displaystyle N}$${\displaystyle M}$${\displaystyle (\alpha_{1}^{N}=\alpha_{2}^{M}=1\mod F_{t})}$

Zurück zur Zerlegung, der letzte Term für wird als bezeichnet , dann ${\displaystyle X_{3}(k,l)}$${\displaystyle X_{4}(k,l)}$

${\displaystyle X_{4}(k,l)=\sum_{n=1}^{N-1}\sum_{m=1}^{M-1}x(n,m){\rm {cas}}({\frac {2\pi nk}{N}}+{\frac {2\pi ml}{M}}),}$

${\displaystyle k=1,2,\ldots,N-1}$

${\displaystyle l=1,2,\ldots,M-1.}$

Wenn und sind primitive Wurzeln von und (die garantiert werden , bestehen , wenn und sind prime ) dann und Karte zu So, Kartierung und zu und erhält man die folgende, ${\displaystyle g_{1}}$${\displaystyle g_{2}}$${\displaystyle N}$${\displaystyle M}$${\displaystyle M}$${\displaystyle N}$${\displaystyle g_{1}}$${\displaystyle g_{2}}$${\displaystyle (n,m)}$${\displaystyle (g_{1}^{n}\mod N,g_{2}^{m}\mod M).}$${\displaystyle n,m,k}$${\displaystyle l}$${\displaystyle g_{1}^{-n},g_{2}^{-m},g_{1}^{k}}$${\displaystyle g_{2}^{l}}$

${\displaystyle X_{4}(g_{1}^{k},g_{2}^{l})=\sum _{n=0}^{N-2}\sum _{m=0}^ {M-2}x(g_{1}^{-n},g_{2}^{-m}){\rm {cas}}({\frac {2\pi g_{1}^{(- n+k)}}{N}}+{\frac {2\pi g_{2}^{(-m+l)}}{M}}),}$

${\displaystyle k=0,1,\ldots,N-2}$

${\displaystyle l=0,1,\ldots,M-2}$.

Was jetzt eine kreisförmige Faltung ist . Mit , , und hat man ${\displaystyle Y(k,l)=X_{4}(g_{1}^{k},g_{2}^{l})}$${\displaystyle y(n,m)=x(g_{1}^{-n},g_{2}^{-m})}$${\displaystyle h(n,m)={\rm {cas}}({\frac {2\pi g_{1}^{n}}{N}}+{\frac {2\pi g_{2} ^{m}}{M}})}$

${\displaystyle Y(k,l)=\sum _{n=0}^{N-2}\sum _{m=0}^{M-2}y(n,m)h(<kn>_ {N},<lm>_{M})}$

${\displaystyle Y(k,l)=FNT^{-1}\{FNT[y(n,m)]\otimes FNT[h(n,m)]}$

wobei bezeichnet Term-für-Term-Multiplikation. In (Boussakta, 1988) wurde auch festgestellt, dass dieser Algorithmus die Anzahl der Multiplikationen gegenüber anderen DHT-Algorithmen um den Faktor 8–20 reduziert, auf Kosten einer leichten Erhöhung der Anzahl der Verschiebungs- und Additionsoperationen, von denen angenommen wird, dass sie einfacher als Multiplikationen. Der Nachteil dieses Algorithmus ist die Einschränkung, dass jede Dimension der Transformation eine primitive Wurzel hat . ${\displaystyle \otimes}$

Verweise

Weiterlesen

• Bracewell, Ronald N. (1986). Die Hartley-Transformation (1 Hrsg.). Oxford University Press . ISBN 978-0-19503969-6.
• Boussakta, Said; Holt, Alan GJ (1988). „Schnelle mehrdimensionale diskrete Hartley-Transformation mit Fermat-Zahlentransformation“. IEE Proceedings G - Elektronische Schaltungen und Systeme . 135 (6): 235–237. doi : 10.1049/ip-g-1.1988.0036 .
• Hong, Jonathan; Vetterli, Martin ; Duhamel, Pierre (1994). "Basisfeld transformiert mit der Faltungseigenschaft" (PDF) . Verfahren der IEEE . 82 (3): 400–412. doi : 10.1109/5.272145 .
• O'Neill, Mark A. (1988). "Schneller als Fast Fourier". BYTE . 13 (4): 293–300.
• Olnejniczak, Kraig J.; Heydt, Gerald T. (März 1994). „Scannen des speziellen Abschnitts über die Hartley-Transformation“. Verfahren der IEEE . 82 : 372–380. (NB. Enthält umfangreiche Bibliographie.)