Quest-ce que la transformation de Walsh Hadamard? Comment pourrait-on lutiliser dans le traitement dimage?

La NASA utilisait la transformation dHadamard comme base pour compresser des photographies de sondes interplanétaires au cours des années 1960 et au début « Années 70. Hadamard est un substitut de calcul plus simple à la transformée de Fourier, car il ne nécessite aucune opération de multiplication ou de division (tous les facteurs sont plus ou moins un). Les opérations de multiplication et de division étaient extrêmement chronophages sur les petits ordinateurs utilisés à bord de ces vaisseaux spatiaux, donc les éviter était bénéfique à la fois en termes de temps de calcul et de consommation dénergie. Mais depuis le développement dordinateurs plus rapides incorporant des multiplicateurs à un cycle et la perfection dalgorithmes plus récents tels que la transformation de Fourier rapide, ainsi que le développement de JPEG, MPEG et dautres compressions dimages, je pense quHadamard est tombé en désuétude. Cependant, je crois comprendre quil sagit peut-être dun retour pour une utilisation dans linformatique quantique. (Lutilisation de la NASA provient dun ancien article de la NASA Tech Briefs; attribution exacte non disponible.)

Commentaires

• Fantastique récit historique M. Peters, merci pour il. Pouvez-vous nous expliquer ce que vous voulez dire / comment cela pourrait être un retour en informatique quantique? De quelle manière y faites-vous allusion dans votre article?
• Selon un article de Wikipédia, de nombreux algorithmes quantiques utilisent la transformée de Hadamard comme première étape, car elle mappe n qubits à une superposition de tous les 2n orthogonaux états dans la base quantique avec un poids égal.
• Eric, pouvez-vous fournir un lien vers larticle de wikipedia que vous citez? Si vous le faites, je peux accepter votre réponse.
• Sûrement. Cest en.wikipedia.org/wiki/Hadamard_transform
• Eric, je pensais que cétait une autre source à laquelle vous faisiez référence. Jamais à moi. 🙂

Les coefficients de la transformée dHadamard sont tous +1 ou -1. La transformée Fast Hadamard peut donc être réduite à des opérations daddition et de soustraction (pas de division ni de multiplication). Cela permet dutiliser un matériel plus simple pour calculer la transformation.

Le coût ou la vitesse du matériel peut donc être laspect souhaitable de la transformation Hadamard.

Commentaires

• Merci pour la réponse mais je voudrais comprendre la transformation sil vous plaît? Je ne me soucie pas pour le moment de la mise en œuvre rapide. Quelle est cette transformation? Pourquoi est-ce utile? Quel aperçu cela nous donne-t-il par rapport aux autres transformations par ondelettes?

Jetez un œil à cet article si vous avoir accès, jai « collé le résumé ici Pratt, WK; Kane, J .; Andrews, HC;, » Hadamard transform image coding, « Proceedings of the IEEE, vol.57, no.1, pp. 58-68, Janvier 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Résumé Lintroduction de lalgorithme de transformée de Fourier rapide a conduit au développement de la technique de codage dimage par transformée de Fourier dans laquelle la transformée de Fourier bidimensionnelle dune image est transmise sur un canal plutôt que sur limage elle-même. Ce développement a en outre conduit à une technique de codage dimage connexe dans laquelle une image est transformée par un opérateur de matrice de Hadamard. La matrice de Hadamard est un tableau carré de nombres plus et moins dont les lignes et les colonnes sont orthogonales les unes par rapport aux autres. Un algorithme de calcul à grande vitesse, similaire au Fourier rapide Un algorithme de transformation, qui effectue la transformation Hadamard, a été développé. Étant donné que seules des additions et des soustractions de nombres réels sont nécessaires avec la transformée de Hadamard, un avantage de vitesse dordre de grandeur est possible par rapport à la transformée de Fourier en nombre complexe. La transmission de la transformée de Hadamard dune image plutôt que la représentation spatiale de limage offre une tolérance potentielle aux erreurs de canal et la possibilité dune transmission à bande passante réduite.

Commentaires

• Merci pour ce lien, je vais certainement le lire, mais cela peut prendre un certain temps. Rien que de labstrait, il semble que la transformée dHadamard puisse être utilisée comme … substitut? … de la transformée de Fourier, en partie parce quelle est très efficace sur le plan du calcul, mais peut-être pour une autre raison également? Quelle a été votre opinion générale à ce sujet?
• En utilisant la transformation hadamard, nous pouvons transmettre une version codée de limage et la reconstruire au niveau du récepteur. Dans ce cas particulier, lauteur utilise la transformée afin de concentrer lénergie du signal dans une bande plus étroite que limage dorigine afin quelle soit moins affectée par le bruit et puisse être reconstruite en utilisant linverse hadamard au niveau du récepteur.
• Hmm, oui, je viens de finir de lire larticle – il semble que la transformation de Hadamard soit juste une alternative plus rapide à la transformation de Fourier, mais rien dautre ne se démarque vraiment. Il économise lénergie, lentropie, etc., mais semble plus ou moins être comme la FFT.
• La transformation Hadamard fait-elle assez bien (même si ce nest pas mieux) contre dautres transformées comme DFT ou même DCT. Être rapide, cest bien, mais peut-il vraiment faire une aussi bonne compression que le DCT est une vraie question. La plupart des normes conventionnelles JPEG, MPEGx ne ‘ ne lutilisent pas.

Je voudrais ajouter que toute transformation m (matrice de Toeplitz générée par une séquence m) peut être décomposée en

P1 * WHT * P2

où WHT est la transformation de Walsh Hadamard, P1 et P2 sont des permutations (ref: http://dl.acm.org/citation.cfm?id=114749 ).

m-transform est utilisé pour un certain nombre de choses: (1) lidentification du système lorsque le système est en proie au bruit et (2) par virtuel de (1) identifier le retard de phase dans un système qui est en proie à bruit

pour (1), m-transform récupère le ou les noyaux du système lorsque le stimulus est une séquence m, ce qui est utile en neurophysiologie (par exemple http://jn.physiology.org/content/99/1/367.full et autres) car il sagit dune puissance élevée pour un signal large bande.

Pour (2), le code Gold est construit à partir de m-séquences (http://en.wikipedia.org/wiki/Gold_code).

Je suis assez heureux dassister à un renouveau autour des transformations Walsh-Paley-Hadamard (ou parfois appelées Waleymard), voir Comment nous peut utiliser la transformation Hadamard dans lextraction de caractéristiques à partir dune image?

Ce sont des instances particulières des fonctions Rademacher. Ils forment des transformations orthogonales qui peuvent, en omettant les normalisations de puissance, être implémentées avec seulement des ajouts et des soustraits, et potentiellement des décalages binaires. Fondamentalement, ils ne nécessitent aucune multiplication, permettant des calculs rapides et peu de besoins en virgule flottante.

Leurs coefficients vectoriels sont constitués de $ \ pm 1 $ , qui imitent une version binarisée des bases sinus ou cosinus. Lordre des vecteurs de Walsh est en séquence (au lieu de la fréquence) qui compte le nombre de changements de signe. Ils bénéficient dalgorithmes papillon similaires pour une mise en œuvre encore plus rapide.

Les séquences de Walsh de longueur $ 2 ^ n $ peuvent également être interprétées comme des instances dune ondelette de Haar paquet.

En tant que tels, ils peuvent être utilisés dans nimporte quelle application où des bases cosinus / sinusoïdales ou ondelettes sont utilisées, avec une implémentation très bon marché. Sur les données entières, ils peuvent rester entiers et permettre des transformations et une compression véritablement sans perte (de la même manière que les entiers DCT ou binaires ondelettes ou binlet). On peut donc les utiliser dans des codes binaires. Ils sont également utilisés dans la détection compressive.

Leurs performances sont souvent considérées comme moins bonnes que les autres transformations harmoniques sur les signaux naturels et les images, en raison de leur nature en bloc. Cependant, certaines variantes sont toujours utilisées, comme pour les transformations de couleur réversibles (RCT) ou les transformées de codage vidéo de faible complexité ( Transformée et quantification de faible complexité en H.264 / AVC ).

Quelques ouvrages:

• Les matrices Agaian, SS, Hadamard et leurs applications, 1985
• Fonctions de Beauchamp, KG, Walsh et leurs applications, 1975
• Harmut, HF, Transmission dinformations par fonctions orthogonales, 1970
• Algorithme de compression vidéo en temps réel pour la transformée dHadamard traitement (NASA, 196)
• Un compresseur vidéo de transformation Hadamard adaptatif en temps réel (NASA, 196)

Quelques liens: Page Web

Description générale

Pour la distribution gaussienne

Rapport

Commentaires

• Il ‘ est mieux si vous pouvez expliquer pourquoi chaque lien est bon.Même un titre complet du document lié serait mieux.
• Jai essayé mais le logiciel du forum était en train de seffondrer, donc vous obtenez une version résumée. Si vous voulez tout supprimer de style wiki-police, faites-le par tous les moyens.
• Je ne ‘ ne pense pas que cest tellement  » wiki-policing  » dans ce cas en essayant de maintenir une norme sur le format de Q & A sur ce tableau. Son objectif nest pas de fonctionner comme un forum. Ainsi, le retour sur votre contribution ne consiste pas à la supprimer, il sagit de la prendre en compte mais aussi de sassurer quelle est conforme à la norme. Ceci est courant sur le réseau déchange de pile. Je pense que cela vaut la peine de modifier le message.