Was ist die Walsh Hadamard Transformation? Wie könnte man es in der Bildverarbeitung verwenden?

Die NASA verwendete die Hadamard-Transformation als Grundlage für die Komprimierung von Fotos von interplanetaren Sonden in den 1960er Jahren und früher „70er Jahre. Hadamard ist ein rechnerisch einfacherer Ersatz für die Fourier-Transformation, da keine Multiplikations- oder Divisionsoperationen erforderlich sind (alle Faktoren sind plus oder minus eins). Multiplikations- und Divisionsoperationen waren auf den kleinen Computern, die an Bord dieser Raumfahrzeuge verwendet wurden, äußerst zeitintensiv. Daher war ihre Vermeidung sowohl hinsichtlich der Rechenzeit als auch des Energieverbrauchs von Vorteil. Aber seit der Entwicklung schnellerer Computer mit Einzelzyklus-Multiplikatoren und der Perfektionierung neuerer Algorithmen wie der Fast Fourier Transform sowie der Entwicklung von JPEG, MPEG und anderer Bildkomprimierung glaube ich, dass Hadamard nicht mehr verwendet wird. Ich verstehe jedoch, dass es ein Comeback für die Verwendung im Quantencomputer geben könnte. (Die Verwendung durch die NASA stammt aus einem alten Artikel in den NASA Tech Briefs; genaue Zuordnung nicht verfügbar.)

Kommentare

• Fantastischer historischer Bericht Herr Peters, vielen Dank für es. Können Sie näher erläutern, was / wie Sie damit meinen, dass es sich um ein Comeback im Quantencomputer handelt? Inwiefern spielen Sie in Ihrem Beitrag darauf an?
• Laut einem Artikel in Wikipedia verwenden viele Quantenalgorithmen die Hadamard-Transformation als ersten Schritt, da sie n Qubits auf eine Überlagerung aller 2n orthogonalen abbildet Zustände in der Quantenbasis mit gleichem Gewicht.
• Eric, können Sie einen Link zu dem von Ihnen zitierten Wikipedia-Artikel bereitstellen? Wenn Sie dies tun, kann ich Ihre Antwort akzeptieren.
• Sicher. Es ist en.wikipedia.org/wiki/Hadamard_transform
• Eric, ich dachte, es wäre eine andere Quelle, auf die Sie sich bezogen haben. Nie meines. 🙂

Die Koeffizienten der Hadamard-Transformation sind alle +1 oder -1. Die schnelle Hadamard-Transformation kann daher auf Additions- und Subtraktionsoperationen (keine Division oder Multiplikation) reduziert werden. Dies ermöglicht die Verwendung einfacherer Hardware zur Berechnung der Transformation.

Hardwarekosten oder -geschwindigkeit können daher der wünschenswerte Aspekt der Hadamard-Transformation sein.

Kommentare

• Danke für die Antwort, aber ich möchte die Transformation bitte verstehen. Die schnelle Implementierung ist mir momentan egal. Was ist diese Transformation? Warum ist es nützlich? Welche Erkenntnisse gibt es uns gegenüber anderen Wavelet-Transformationen?

Schauen Sie sich dieses Dokument an, wenn Sie Zugriff haben, ich habe das Abstract hier eingefügt Pratt, WK; Kane, J.; Andrews, HC; „Hadamard Transform Image Coding“, Proceedings of the IEEE, Bd. 57, Nr. 1, S. 58-68, Jan. 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Zusammenfassung Die Einführung des schnellen Fourier-Transformationsalgorithmus hat zur Entwicklung der Fourier-Transformations-Bildcodierungstechnik geführt, bei der die zweidimensionale Fourier-Transformation eines Bildes über einen Kanal und nicht über das Bild selbst übertragen wird. Diese Entwicklung hat ferner zu einer verwandten Bildcodierungstechnik geführt in dem ein Bild von einem Hadamard-Matrixoperator transformiert wird. Die Hadamard-Matrix ist eine quadratische Anordnung von Plus- und Minus-Matrix, deren Zeilen und Spalten orthogonal zueinander sind. Ein Hochgeschwindigkeits-Berechnungsalgorithmus, ähnlich dem schnellen Fourier Der Transformationsalgorithmus, der die Hadamard-Transformation durchführt, wurde entwickelt. Da bei der Hadamard-Transformation nur reelle Additionen und Subtraktionen erforderlich sind, ist ein Geschwindigkeitsvorteil in der Größenordnung gegenüber der komplexen Zahl-Fourier-Transformation möglich. Das Übertragen der Hadamard-Transformation eines Bildes anstelle der räumlichen Darstellung des Bildes bietet eine potenzielle Toleranz gegenüber Kanalfehlern und die Möglichkeit einer Übertragung mit reduzierter Bandbreite.

Kommentare

• Vielen Dank für diesen Link, ich werde ihn sicherlich lesen, aber es kann einige Zeit dauern. Nur aus der Zusammenfassung geht hervor, dass die Hadamard-Transformation als … Ersatz für die Fourier-Transformation verwendet werden kann, teilweise weil sie rechnerisch sehr effizient ist, aber vielleicht auch aus einem anderen Grund? Wie haben Sie das allgemein gesehen?
• Mit der Hadamard-Transformation können wir eine codierte Version des Bildes übertragen und dann am Empfänger rekonstruieren. In diesem speziellen Fall verwendet der Autor die Transformation, um die Energie des Signals in einem schmaleren Band als das Originalbild zu konzentrieren, damit es weniger durch Rauschen beeinträchtigt wird und mithilfe des inversen Hadamards am Empfänger rekonstruiert werden kann.
• Hmm, ja, ich habe gerade die Zeitung gelesen – es scheint, dass die Hadamard-Transformation nur eine schnellere Alternative zur Fourier-Transformation ist, aber nichts anderes fällt wirklich auf. Es spart Energie, Entropie usw., scheint aber mehr oder weniger genau wie die FFT zu sein.
• Hat die Hadamard-Transformation gute (wenn auch nicht bessere) Arbeit gegen andere Transformationen wie DFT oder sogar DCT geleistet? Schnell zu sein ist gut, aber kann es wirklich so gut komprimieren, wie man sagt, DCT ist eine echte Frage. Die meisten herkömmlichen Standards JPEG, MPEGx ‚ verwenden es übrigens nicht ganz.

Ich freue mich sehr über eine Wiederbelebung der Walsh-Paley-Hadamard-Transformationen (oder manchmal auch Waleymard-Transformationen genannt), siehe Wie wir Kann die Hadamard-Transformation bei der Merkmalsextraktion aus einem Bild verwendet werden?

Sie sind eine besondere Instanz von Rademacher-Funktionen. Sie bilden orthogonale Transformationen, die unter Auslassung von Leistungsnormalisierungen nur mit Additionen und Subtraktionen und möglicherweise binären Verschiebungen implementiert werden können. Grundsätzlich erfordern sie keine Multiplikation, was schnelle Berechnungen und wenig ausgefallene Gleitkommaanforderungen ermöglicht.

Ihre Vektorkoeffizienten bestehen aus $ \ pm 1 $ , das ahmt eine binärisierte Version von Sinus- oder Cosinusbasen nach. Die Reihenfolge der Walsh-Vektoren erfolgt in Sequenz (anstelle der Frequenz), die die Anzahl der Vorzeichenwechsel zählt. Sie verfügen über ähnliche Butterfly-Algorithmen für eine noch schnellere Implementierung.

Walsh-Sequenzen der Länge $ 2 ^ n $ können auch als Instanzen eines Haar-Wavelets interpretiert werden Paket.

Als solche können sie in jeder Anwendung verwendet werden, in der Cosinus / Sinus- oder Wavelet-Basen verwendet werden, mit einer sehr billigen Implementierung. Bei ganzzahligen Daten können sie ganzzahlig bleiben und wirklich verlustfreie Transformationen und Komprimierungen ermöglichen (ähnlich wie bei ganzzahligen DCT- oder binären Wavelets oder Binlets). Man kann sie also in Binärcodes verwenden. Sie werden auch bei der Druckabtastung verwendet.

Ihre Leistung wird aufgrund ihrer Blockhaftigkeit häufig als schlechter angesehen als andere harmonische Transformationen auf natürlichen Signalen und Bildern. Einige Varianten werden jedoch noch verwendet, beispielsweise für reversible Farbtransformationen (RCT) oder Videokodierungstransformationen mit geringer Komplexität ( Transformation und Quantisierung mit geringer Komplexität in H.264 / AVC ).

Einige Literatur:

• Agaian, SS, Hadamard-Matrizen und ihre Anwendungen, 1985
• Beauchamp, KG, Walsh-Funktionen und ihre Anwendungen, 1975
• Harmut, HF, Übertragung von Informationen durch orthogonale Funktionen, 1970
• Echtzeit-Videokomprimierungsalgorithmus für die Hadamard-Transformation Verarbeitung (NASA, 196)
• Ein adaptiver Hadamard-Transformationsvideokompressor in Echtzeit (NASA, 196)

Einige Links: Webseite

Allgemeine Beschreibung

Für die Gaußsche Verteilung

Bericht

Kommentare

• ‚ ist besser, wenn Sie erklären können, warum jeder Link gut ist.Sogar ein vollständiger Titel des verlinkten Dokuments wäre besser.
• Ich habe es versucht, aber die Forensoftware ist ausgefallen, daher erhalten Sie eine zusammenfassende Version. Wenn Sie im Wiki-Polizei-Stil alles löschen möchten, tun Sie dies auf jeden Fall.
• Ich ‚ denke nicht, dass es so viel ist “ Wiki-Überwachung “ in diesem Fall als Versuch, einen Standard für das Format von Q & A beizubehalten Tafel. Ihr Ziel ist es nicht, als Forum zu fungieren. Beim Feedback zu Ihrem Beitrag geht es also nicht darum, ihn zu löschen, sondern ihn zu berücksichtigen, sondern auch sicherzustellen, dass er dem Standard entspricht. Dies ist im gesamten Stack Exchange-Netzwerk üblich. Ich würde denken, dass es sich lohnt, den Beitrag zu bearbeiten.