Estoy tratando de aprender sobre el WHT pero no parece haber 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 del reconocimiento de imágenes.
¿Qué tiene de especial y qué propiedades presenta en una señal que no se mostraría en las transformadas clásicas de Fourier u otras transformadas wavelet? ¿Por qué es útil para el reconocimiento de objetos como se señala aquí ?
Comentarios
- 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 el MLS tiene otros problemas
- @DilipSarwate ¿Por qué el WHT es útil y / o único?
Respuesta
La NASA solía usar la transformada de Hadamard como base para comprimir fotografías de sondas interplanetarias durante la década de 1960 y principios «70. Hadamard es un sustituto computacionalmente más simple de 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 multiplicación y división requerían mucho 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 regresando para su uso en computación cuántica. (El uso de la NASA proviene de un artículo antiguo en NASA Tech Briefs; la atribución exacta no está disponible).
Comentarios
- Fantástico relato histórico Sr. Peters, gracias por eso. ¿Puede explicar qué / cómo quiere decir que podría estar protagonizando un regreso en la computación cuántica? ¿De qué manera lo alude en su publicación?
- Según un artículo en Wikipedia, muchos algoritmos cuánticos usan la transformada de Hadamard como paso inicial, ya que mapea n qubits a una superposición de todos los 2n ortogonales estados en la base cuántica con el mismo peso.
- Eric, ¿puede proporcionar un enlace al artículo de wikipedia que cita? Si lo hace, puedo aceptar su respuesta.
- Seguramente. Es en.wikipedia.org/wiki/Hadamard_transform
- Eric, pensé que era otra fuente a la que te referías. Nunca mío. 🙂
Respuesta
Los coeficientes de la transformada de Hadamard son todos +1 o -1. Por lo tanto, la Transformada Rápida de Hadamard puede reducirse a operaciones de suma y resta (sin división ni 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.
Comentarios
- 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 frente a otras transformaciones wavelet?
Respuesta
Eche un vistazo a este documento si tienen acceso, he pegado el resumen aquí Pratt, WK; Kane, J .; Andrews, HC;, «Hadamard transform image coding,» Proceedings of the 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 transformada rápida de Fourier ha llevado al desarrollo de la técnica de codificación de imágenes por transformada de Fourier, mediante la cual la transformada bidimensional de Fourier de una imagen se transmite a través de un canal en lugar de la imagen en sí. Este desarrollo también ha llevado a una técnica de codificación de imágenes relacionada en el que una imagen es transformada por un operador de matriz de Hadamard. La matriz de Hadamard es una matriz cuadrada de más y menos cuyas filas y columnas son ortogonales entre sí. Un algoritmo computacional de alta velocidad, similar al rápido Fourier Se ha desarrollado el algoritmo de transformación, que realiza la transformación de Hadamard. Dado que solo se requieren sumas y restas de números reales con la transformada de Hadamard, es posible una ventaja de velocidad de orden de magnitud en comparación con la transformada de Fourier de números complejos. La transmisión de la transformada de Hadamard de una imagen en lugar de la representación espacial de la imagen proporciona una tolerancia potencial a los errores de canal y la posibilidad de transmisión de ancho de banda reducido.
Comentarios
- Gracias por este enlace, sin duda lo leeré, pero puede llevar algún tiempo. Solo desde el punto de vista abstracto, parece que la Transformada de Hadamard se puede usar como … ¿sustituto? … de 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?
- 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á usando la transformada para concentrar la energía de la señal en una banda más estrecha que la imagen original, por lo que se ve menos afectada por el ruido y se puede reconstruir usando la inversa hadamard en el receptor.
- Hmm, sí, acabo de terminar de leer el artículo; parece que la transformación de Hadamard es una alternativa más rápida a la transformada de Fourier, pero nada más destaca realmente. Conserva energía, entropía, etc., pero más o menos parece ser como la FFT.
- ¿Hadamard Transform hace un trabajo suficientemente bueno (aunque no mejor) contra otras transformadas como DFT o incluso DCT? Ser rápido es bueno, pero ¿realmente puede hacer una compresión tan buena como, por ejemplo, DCT? La mayoría de los estándares convencionales JPEG, MPEGx no ‘ no los usan por cierto.
Respuesta
Me gustaría agregar que cualquier transformación m (matriz de Toeplitz generada por una secuencia m) se puede descomponer en
P1 * WHT * P2
donde WHT es la Transformada de Walsh Hadamard, P1 y P2 son permutaciones (ref: http://dl.acm.org/citation.cfm?id=114749 ).
La transformada m se usa para varias cosas: (1) identificación del sistema cuando el sistema está plagado de ruido y (2) por virtual de (1) identificar desfase en un sistema que está plagado de ruido
para (1), la transformada m recupera el núcleo 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.full 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).
Respuesta
Estoy muy contento de presenciar un avivamiento en torno a las transformaciones de Walsh-Paley-Hadamard (o, a veces, llamadas Waleymard), consulte Cómo ¿Se puede usar la transformación de Hadamard en la extracción de características de una imagen?
Son una instancia particular de las funciones de Rademacher. Forman transformaciones ortogonales que pueden, omitiendo las normalizaciones de potencia, implementarse solo con sumas y restas, y potencialmente con cambios binarios. Básicamente, no requieren multiplicar, lo que permite cálculos rápidos y pequeñas necesidades de coma flotante sofisticadas.
Sus coeficientes vectoriales están hechos de $ \ pm 1 $ , que imitan una versión binarizada de bases de seno o coseno. El orden de los vectores de Walsh es en secuencia (en lugar de frecuencia) que cuenta el número de cambios de signo. Disfrutan de algoritmos de mariposa similares para una implementación aún más rápida.
Las secuencias de Walsh de longitud $ 2 ^ n $ también se pueden interpretar como instancias de una wavelet de Haar paquete.
Como tales, se pueden usar en cualquier aplicación donde se usen bases coseno / seno o wavelet, con una implementación muy económica. En datos enteros, pueden permanecer enteros y permitir transformaciones y compresión verdaderamente sin pérdidas (de manera similar a DCT de enteros o wavelets o binlet binarios). Entonces uno puede usarlos en códigos binarios. También se utilizan en la detección por compresión.
Su rendimiento a menudo se considera más pobre que el de otras transformaciones armónicas en señales e imágenes naturales, debido a su naturaleza en bloque. Sin embargo, todavía se utilizan algunas variantes, como las transformaciones de color reversibles (RCT) o las transformaciones de codificación de video de baja complejidad ( Transformada de baja complejidad y cuantificación en H.264 / AVC ).
Alguna literatura:
- Agaian, SS, Matrices de Hadamard y sus aplicaciones, 1985
- Funciones de Beauchamp, KG, Walsh y sus aplicaciones, 1975
- Harmut, HF, Transmisión de información por funciones ortogonales, 1970
- Algoritmo de compresión de video en tiempo real para la transformada de Hadamard procesamiento (NASA, 196)
- Un compresor de video de transformación de Hadamard adaptable en tiempo real (NASA, 196)
Respuesta
Algunos enlaces: Página web
Comentarios
- 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.
- Lo intenté, pero el software del foro se estaba estropeando, por lo que obtienes una versión resumida. Si quieres borrar todo al estilo wiki-police, hazlo.
- No ‘ creo que sea demasiado » wiki-policing » en este caso tratando de mantener un estándar en el formato de Q & A en este Junta. Su objetivo no es funcionar como foro. Por lo tanto, la retroalimentación sobre su contribución no se trata de eliminarla, se trata de incorporarla, pero también de asegurarse de que cumpla con el estándar. Esto es común en toda la red de intercambio de pila. Creo que vale la pena editar la publicación.