Qu'est-ce que la transformation de Walsh-Hadamard et à quoi sert-elle?

19

J'essaie de m'enseigner le WHT mais il ne semble pas y avoir beaucoup de bonnes explications en ligne n'importe où. Je pense avoir compris comment calculer le WHT, mais j'essaie vraiment de comprendre pourquoi il est considéré comme utile dans le domaine de la reconnaissance d'image.

Qu'est-ce qui est si spécial et quelles propriétés cela fait-il ressortir dans un signal qui n'apparaîtrait pas sur les transformées de Fourier classiques ou d'autres transformées en ondelettes? Pourquoi est-il utile pour la reconnaissance d'objets comme indiqué ici ?

Spacey
la source
Une application est les systèmes de mesure qui utilisent des séquences de longueur maximale (MLS) comme excitation (par exemple mlssa.com ). C'est censé être plus rapide car aucune multiplication n'est requise. En pratique, ce n'est pas vraiment un avantage et la MLS a d'autres problèmes
Hilmar
@DilipSarwate Pourquoi le WHT est-il utile et / ou unique?
Spacey

Réponses:

11

La NASA utilisait la transformée de Hadamard comme base pour compresser des photographies de sondes interplanétaires dans les années 60 et au début des années 70. Hadamard est un substitut de calcul plus simple pour 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 engins 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 d'ordinateurs plus rapides incorporant des multiplicateurs à cycle unique et la perfection d'algorithmes plus récents tels que la transformation de Fourier rapide, ainsi que le développement de JPEG, MPEG et d'autres compressions d'images, je crois que Hadamard est tombé en désuétude. cependant, Je comprends que cela pourrait être un retour pour une utilisation en informatique quantique. (L'utilisation de la NASA est tirée d'un ancien article des NASA Tech Briefs; l'attribution exacte n'est pas disponible.)

Eric Peters
la source
Fantastique récit historique M. Peters, merci pour cela. Pouvez-vous développer sur quoi / comment vous voulez dire qu'il pourrait être un retour en informatique quantique? De quelle manière y faites-vous allusion dans votre message?
Spacey
Selon un article de Wikipedia, de nombreux algorithmes quantiques utilisent la transformée de Hadamard comme étape initiale, car elle mappe n qubits à une superposition de tous les 2n états orthogonaux dans la base quantique avec un poids égal.
Eric Peters
Eric, pouvez-vous fournir un lien vers l'article wikipedia que vous citez? Si vous le faites, je peux accepter votre réponse.
Spacey
Sûrement. C'est en.wikipedia.org/wiki/Hadamard_transform
Eric Peters
Eric, je pensais que c'était une autre source à laquelle tu faisais référence. Jamais à moi. :-)
Spacey
7

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

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

Han
la source
1
Merci pour la réponse mais j'aimerais comprendre la transformation s'il vous plaît? Je ne me soucie pas pour l'instant de l'implémentation rapide. Quelle est cette transformation? Pourquoi est-ce utile? Quel aperçu cela nous donne-t-il VS d'autres transformées en ondelettes?
Spacey
5

Jetez un œil à cet article si vous y avez accès, j'ai collé le résumé ici Pratt, WK; Kane, J .; Andrews, HC; , "Hadamard transform image coding", Actes de l'IEEE, vol.57, n ° 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é L'introduction de l'algorithme de transformée de Fourier rapide a conduit au développement de la technique de codage d'image par transformée de Fourier par laquelle la transformée de Fourier bidimensionnelle d'une image est transmise sur un canal plutôt que sur l'image elle-même. Ce développement a en outre conduit à une technique de codage d'image similaire dans laquelle une image est transformée par un opérateur de matrice Hadamard. La matrice de Hadamard est un tableau carré de plus et moins ceux dont les lignes et les colonnes sont orthogonales les unes aux autres. Un algorithme de calcul à grande vitesse, similaire à l'algorithme de transformée de Fourier rapide, qui effectue la transformation de Hadamard a été développé. Étant donné que seuls des ajouts et des soustractions de nombres réels sont requis avec la transformée de Hadamard, un avantage de vitesse d'ordre de grandeur est possible par rapport à la transformée de Fourier en nombre complexe.

Charna
la source
Merci pour ce lien, je vais certainement le lire, mais cela peut prendre un certain temps. Juste à partir de l'abstrait, il semble que la transformée de Hadamard puisse être utilisée comme ... substitut? ... pour la transformée de Fourier, en partie parce qu'elle est très efficace sur le plan informatique, mais peut-être pour une autre raison également? Quelle était votre opinion générale à ce sujet?
Spacey
La transformée de hadamard nous permet de transmettre une version codée de l'image puis de la reconstruire au niveau du récepteur. Dans ce cas particulier, l'auteur utilise la transformation afin de concentrer l'énergie du signal dans une bande plus étroite que l'image d'origine, de sorte qu'elle est moins affectée par le bruit et peut être reconstruite en utilisant le hadamard inverse sur le récepteur.
Charna
Hmm, oui, je viens de terminer la lecture du document - il semble que la transformation de Hadamard soit juste une alternative plus rapide à la transformation de Fourier, mais rien d'autre ne se démarque vraiment. Il conserve l'énergie, l'entropie, etc., mais semble plus ou moins comme la FFT.
Spacey
Hadamard Transform fait-il un travail assez bon (même s'il n'est pas meilleur) contre d'autres transformations comme DFT ou même DCT. Être rapide, c'est bien, mais peut-il vraiment faire une bonne compression comme le DCT est une vraie question? La plupart des normes JPEG conventionnelles, MPEGx ne l'utilisent pas tout à fait BTW.
Dipan Mehta
2

J'aimerais ajouter que toute m-transform (matrice de Toeplitz générée par une m-séquence) peut être décomposée en

P1 * WHT * P2

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

m-transform est utilisé pour un certain nombre de choses: (1) identification du système lorsque le système est en proie à du bruit et (2) par virtuel de (1) identifier le retard de phase dans un système qui est en proie à du 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. pleine et autres) car il s'agit d'une puissance élevée pour un signal large bande.

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

merci
la source
1

Je suis très heureux d'assister à un renouveau autour des transformations de Walsh-Paley-Hadamard (ou parfois appelées Waleymard), voir Comment pouvons-nous utiliser la transformation de Hadamard dans l'extraction de fonctionnalités à partir d'une image?

±1

2n

En tant que tels, ils peuvent être utilisés dans n'importe quelle application où des bases cosinus / sinus ou ondelettes sont utilisées, avec une mise en œuvre très bon marché. Sur les données entières, elles peuvent rester entières et permettre des transformations et une compression véritablement sans perte (de la même manière que les DCT entiers ou les ondelettes binaires ou binlet). On peut donc les utiliser dans des codes binaires.

Leur performance est souvent considérée comme plus mauvaise que d'autres transformations harmoniques sur des signaux et des images naturels, en raison de leur nature en blocs. Cependant, certaines variantes sont encore utilisées, comme pour les transformations de couleurs réversibles (RCT) ou les transformations de codage vidéo à faible complexité (transformation et quantification à faible complexité en H.264 / AVC ).

Quelques publications:

Laurent Duval
la source
-2

Quelques liens: page Web

Description générale

Pour la distribution gaussienne

rapport

Sean O'Connor
la source
C'est mieux si vous pouvez expliquer pourquoi chaque lien est bon. Même un titre complet du document lié serait préférable.
Peter K.
J'ai essayé mais le logiciel du forum était en train de s'écailler, donc vous obtenez une version résumée. Si vous voulez supprimer tout de style wiki-police, faites-le par tous les moyens.
Sean O'Connor
Je ne pense pas qu'il s'agisse tant de «wiki-police» dans ce cas que d'essayer de maintenir une norme sur le format des questions et réponses sur ce forum. Son objectif n'est pas de fonctionner comme un forum. Donc, le retour sur votre contribution ne consiste pas à le supprimer, il s'agit de l'intégrer mais également de vous assurer qu'il est conforme à la norme. Ceci est courant sur le réseau d'échange de pile. Je pense que cela vaut la peine d'éditer le message.
A_A