¿Qué es la transformación de Walsh-Hadamard y para qué sirve?

19

Estoy tratando de enseñarme sobre el WHT, pero no parece que haya muchas buenas explicaciones en línea en ningún lugar. Creo que he descubierto cómo calcular el WHT, pero realmente estoy tratando de entender por qué se considera útil dentro del dominio de reconocimiento de imágenes.

¿Qué tiene de especial y qué propiedades aporta en una señal que no se mostraría en las transformadas clásicas de Fourier u otras transformaciones wavelet? ¿Por qué es útil para el reconocimiento de objetos como se señala aquí ?

Spacey
fuente
Una aplicación son los sistemas de medición que utilizan secuencias de longitud máxima (MLS) como excitación (por ejemplo, mlssa.com ). Se supone que es más rápido ya que no se requieren multiplicaciones. En la práctica no es un gran beneficio y la MLS tiene otros problemas
Hilmar
@DilipSarwate ¿Por qué el WHT es útil y / o único?
Spacey

Respuestas:

11

La NASA solía usar la transformación Hadamard como base para comprimir fotografías de sondas interplanetarias durante la década de 1960 y principios de los 70. Hadamard es un sustituto computacionalmente más simple para la transformada de Fourier, ya que no requiere operaciones de multiplicación o división (todos los factores son más o menos uno). Las operaciones de multiplicar y dividir fueron extremadamente intensivas en tiempo en las pequeñas computadoras utilizadas a bordo de esas naves espaciales, por lo que evitarlas fue beneficioso tanto en términos de tiempo de cómputo como de consumo de energía. Pero desde el desarrollo de computadoras más rápidas que incorporan multiplicadores de ciclo único y la perfección de algoritmos más nuevos como la Transformada rápida de Fourier, así como el desarrollo de JPEG, MPEG y otras compresiones de imágenes, creo que Hadamard ha dejado de usarse. Sin embargo, Entiendo que puede estar organizando un regreso para su uso en la computación cuántica. (El uso de la NASA es de un artículo antiguo en NASA Tech Briefs; la atribución exacta no está disponible).

Eric Peters
fuente
Fantástico relato histórico Sr. Peters, gracias por ello. ¿Puede ampliar qué / cómo quiere decir que podría estar organizando un regreso en la computación cuántica? ¿De qué manera lo aludes en tu publicación?
Spacey
Según un artículo en Wikipedia, muchos algoritmos cuánticos usan la transformación de Hadamard como un paso inicial, ya que asigna n qubits a una superposición de todos los 2n estados ortogonales en la base cuántica con igual peso.
Eric Peters
Eric, ¿puedes proporcionar un enlace al artículo de Wikipedia que cites? Si lo haces, puedo aceptar tu respuesta.
Spacey
Seguramente. Es en.wikipedia.org/wiki/Hadamard_transform
Eric Peters
Eric, pensé que era otra fuente a la que te referías. Nunca mío. :-)
Spacey
7

Los coeficientes de la transformación de Hadamard son todos +1 o -1. La Transformación rápida de Hadamard puede por lo tanto reducirse a operaciones de suma y resta (sin división o multiplicación). Esto permite el uso de hardware más simple para calcular la transformación.

Por lo tanto, el costo o la velocidad del hardware pueden ser el aspecto deseable de la transformación de Hadamard.

Han
fuente
1
Gracias por la respuesta, pero me gustaría entender la transformación, ¿por favor? En este momento no me importa la implementación rápida. ¿Qué es esta transformación? ¿Por qué es útil? ¿Qué información nos da VS otras transformaciones wavelet?
Spacey
5

Eche un vistazo a este documento si tiene acceso. He pegado el resumen aquí Pratt, WK; Kane, J .; Andrews, HC; , "Hadamard transforma la codificación de imágenes", Actas del IEEE, vol.57, no.1, pp. 58-68, enero de 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp /stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Resumen La introducción del algoritmo de transformación rápida de Fourier ha llevado al desarrollo de la técnica de codificación de imagen de transformación de Fourier por la cual la transformación de Fourier bidimensional de una imagen se transmite a través de un canal en lugar de la imagen misma. Este desarrollo ha llevado a una técnica de codificación de imagen relacionada en la que una imagen es transformada por un operador de matriz Hadamard. La matriz de Hadamard es una matriz cuadrada de más y menos cuyas filas y columnas son ortogonales entre sí. Se ha desarrollado un algoritmo computacional de alta velocidad, similar al algoritmo de transformación rápida de Fourier, que realiza la transformación de Hadamard. Como solo se requieren sumas y restas de números reales con la transformación de Hadamard, es posible obtener una ventaja de velocidad de orden de magnitud en comparación con la transformación de Fourier de números complejos.

Charna
fuente
Gracias por este enlace, ciertamente lo leeré, pero puede llevar algún tiempo. Solo por el resumen, parece que la Transformada Hadamard se puede utilizar como ... ¿sustituto? ... para la transformada de Fourier, en parte porque es computacionalmente muy eficiente, pero ¿quizás por otra razón también? ¿Cuál fue su opinión general sobre esto?
Spacey
Usando la transformación hadamard podemos transmitir una versión codificada de la imagen y luego reconstruirla en el receptor. En este caso particular, el autor está utilizando la transformación para concentrar la energía de la señal en una banda más estrecha que la imagen original, de modo que el ruido la afecte menos y pueda reconstruirse utilizando el hadamard inverso en el receptor.
Charna
Hmm, sí, acabo de terminar de leer el periódico, parece que la transformación de Hadamard es solo una alternativa más rápida a la transformación de Fourier, pero nada más se destaca realmente. Conserva energía, y entropía, etc., pero más o menos parece ser como la FFT.
Spacey
¿Hadamard Transform realiza un trabajo lo suficientemente bueno (incluso si no mejor) contra otras transformaciones como DFT o incluso DCT. Ser rápido es bueno, pero ¿puede realmente hacer una compresión tan buena como decir que DCT es una pregunta real? La mayoría de los estándares convencionales JPEG, MPEGx no lo usan por cierto BTW.
Dipan Mehta
2

Me gustaría agregar que cualquier transformación m (matriz de Toeplitz generada por una secuencia m) puede descomponerse en

P1 * WHT * P2

donde WHT es la transformación de Walsh Hadamard, P1 y P2 son permutaciones (ref: http://dl.acm.org/citation.cfm?id=114749 ).

m-transform se usa para varias cosas: (1) identificación del sistema cuando el sistema está plagado de ruido y (2) por virtual de (1) identifica el retraso de fase en un sistema que está plagado de ruido

para (1), la transformación m recupera los núcleos del sistema cuando el estímulo es una secuencia m, lo cual es útil en neurofisiología (por ejemplo, http://jn.physiology.org/content/99/1/367. completo y otros) porque es de alta potencia para una señal de banda ancha.

Para (2), el código Gold se construye a partir de secuencias m (http://en.wikipedia.org/wiki/Gold_code).

thang
fuente
1

Estoy muy contento de presenciar un renacimiento en torno a las transformaciones de Walsh-Paley-Hadamard (o a veces llamado Waleymard), vea ¿Cómo podemos usar la transformación de Hadamard en la extracción de características de una imagen?

±1

2norte también se puede interpretar como instancias de un paquete wavelet de Haar.

Como tal, se pueden usar en cualquier aplicación donde se usen bases coseno / seno o wavelet, con una implementación muy barata. En los datos enteros, pueden permanecer enteros y permitir transformaciones y compresión verdaderamente sin pérdidas (de manera similar a DCT o wavelets o binlet binarios enteros). Entonces uno puede usarlos en códigos binarios.

Su rendimiento a menudo se considera más pobre que otras transformaciones armónicas en señales e imágenes naturales, debido a su naturaleza en bloque. Sin embargo, algunas variantes todavía están en uso, como las transformaciones de color reversibles (RCT) o las transformaciones de codificación de video de baja complejidad (Transformación de baja complejidad y cuantificación en H.264 / AVC ).

Alguna literatura:

Laurent Duval
fuente
-2

Algunos enlaces: página web

Descripción general

Para distribución gaussiana

Reporte

Sean O'Connor
fuente
Es mejor si puede dar una explicación de por qué cada enlace es bueno. Incluso un título completo del documento vinculado sería mejor.
Peter K.
Lo intenté pero el software del foro se estaba cayendo, por lo tanto, obtienes una versión resumida. Si desea eliminar el estilo wiki-police, elimínelo todo, hágalo.
Sean O'Connor
No creo que sea tanto "wiki-policing" en este caso como tratar de mantener un estándar sobre el formato de preguntas y respuestas en este foro. Su objetivo no es funcionar como un foro. Por lo tanto, la retroalimentación sobre su contribución no se trata de eliminarla, se trata de llevarla a bordo sino también de asegurarse de que cumpla con el estándar. Esto es común en la red de intercambio de pila. Creo que vale la pena editar la publicación.
A_A