O que é a transformação Walsh Hadamard? Como usá-lo no processamento de imagens?

A NASA costumava usar a transformada de Hadamard como base para compactar fotografias de sondas interplanetárias durante os anos 1960 e início “70s. Hadamard é um substituto computacionalmente mais simples para a transformada de Fourier, uma vez que não requer operações de multiplicação ou divisão (todos os fatores são mais ou menos um). As operações de multiplicação e divisão consumiam muito tempo nos pequenos computadores usados a bordo dessas espaçonaves, portanto evitá-las era benéfico tanto em termos de tempo de computação quanto de consumo de energia. Mas, desde o desenvolvimento de computadores mais rápidos que incorporam multiplicadores de ciclo único e o aperfeiçoamento de algoritmos mais novos, como a Fast Fourier Transform, bem como o desenvolvimento de JPEG, MPEG e outra compactação de imagem, acredito que o Hadamard está fora de uso. No entanto, eu entendo que pode estar preparando um retorno para uso em computação quântica. (O uso da NASA vem de um artigo antigo do NASA Tech Briefs; atribuição exata indisponível.)

Comentários

• Relato histórico fantástico Sr. Peters, obrigado por isto. Você pode expandir o que / como você quis dizer com isso, encenando uma volta na computação quântica? De que forma você alude a isso em sua postagem?
• De acordo com um artigo na Wikipedia, muitos algoritmos quânticos usam a transformada de Hadamard como uma etapa inicial, uma vez que mapeia n qubits para uma superposição de todos os 2n ortogonais estados na base quântica com peso igual.
• Eric, você pode fornecer um link para o artigo da wikipedia que você cita? Se você fizer isso, posso aceitar sua resposta.
• Certamente. É en.wikipedia.org/wiki/Hadamard_transform
• Eric, pensei que fosse outra fonte à qual você estava se referindo. Esquece. 🙂

Os coeficientes da transformação de Hadamard são todos +1 ou -1. A transformação rápida de Hadamard pode, portanto, ser reduzida a operações de adição e subtração (sem divisão ou multiplicação). Isso permite o uso de hardware mais simples para calcular a transformação.

Portanto, o custo ou a velocidade do hardware pode ser o aspecto desejável da transformação de Hadamard.

Comentários

• Obrigado pela resposta, mas gostaria de entender a transformação, por favor? Eu não me importo agora com a implementação rápida. O que é essa transformação? Por que isso é útil? Que insight isso nos dá VS outras transformações wavelet?

Dê uma olhada neste artigo se você tenha acesso, colei o resumo aqui Pratt, WK; Kane, J .; Andrews, HC;, “Hadamard transform image coding,” Proceedings of the IEEE, vol.57, no.1, pp. 58-68, Jan. 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Resumo A introdução do algoritmo de transformação rápida de Fourier levou ao desenvolvimento da técnica de codificação de imagem de transformação de Fourier, em que a transformação de Fourier bidimensional de uma imagem é transmitida por um canal em vez da própria imagem. Esse desenvolvimento levou ainda a uma técnica de codificação de imagem em que uma imagem é transformada por um operador de matriz de Hadamard. A matriz de Hadamard é uma matriz quadrada de mais e menos cujas linhas e colunas são ortogonais entre si. Um algoritmo computacional de alta velocidade, semelhante ao rápido Fourier O algoritmo de transformação, que realiza a transformação de Hadamard, foi desenvolvido. Uma vez que apenas adições e subtrações de números reais são necessárias com a transformada de Hadamard, uma vantagem de velocidade de ordem de magnitude é possível em comparação com a transformada de Fourier de número complexo. A transmissão da transformada Hadamard de uma imagem em vez da representação espacial da imagem fornece uma tolerância potencial para erros de canal e a possibilidade de transmissão de largura de banda reduzida.

Comentários

• Obrigado por este link, certamente irei lê-lo, mas pode demorar um pouco. Apenas de forma abstrata, parece que a transformada de Hadamard está sendo capaz de ser usada como um … substituto? … para a transformada de Fourier, em parte porque é computacionalmente muito eficiente, mas talvez por outro motivo também? Qual foi sua opinião geral sobre isso?
• Usando a transformação hadamard, somos capazes de transmitir uma versão codificada da imagem e depois reconstruí-la no receptor. Neste caso particular, o autor está usando a transformada para concentrar a energia do sinal em uma banda mais estreita do que a imagem original, de forma que seja menos afetada pelo ruído e possa ser reconstruída usando o hadamard inverso no receptor.
• Hmm, sim, acabei de ler o artigo – parece que a transformação de Hadamard é apenas uma alternativa mais rápida para a transformação de fourier, mas nada mais se destaca. Ele conserva energia e entropia, etc, mas mais ou menos parece ser igual ao FFT.
• A Hadamard Transform faz um bom trabalho (mesmo que não melhor) contra outras transformadas como DFT ou mesmo DCT. Ser rápido é bom, mas pode realmente fazer uma compressão tão boa quanto dizer que DCT é uma questão real. A maioria dos padrões convencionais JPEG, MPEGx não ‘ não costumam usá-lo.

Gostaria de adicionar que qualquer transformada m (matriz de Toeplitz gerada por uma sequência m) pode ser decomposta em

P1 * WHT * P2

onde WHT é a transformação de Walsh Hadamard, P1 e P2 são permutações (ref: http://dl.acm.org/citation.cfm?id=114749 ).

A transformada m é usada para uma série de coisas: (1) identificação do sistema quando o sistema é atormentado com ruído e (2) por virtual de (1) identificar atraso de fase em um sistema que é atormentado com ruído

para (1), a transformada m recupera o (s) kernel (s) do sistema quando o estímulo é uma sequência m, o que é útil em neurofisiologia (por exemplo, http://jn.physiology.org/content/99/1/367.full e outros) porque é de alta potência para um sinal de banda larga.

Para (2), o código Gold é construído a partir de sequências m (http://en.wikipedia.org/wiki/Gold_code).

Estou muito feliz em testemunhar um renascimento em torno das transformações de Walsh-Paley-Hadamard (ou às vezes chamadas de Waleymard), consulte Como nós pode usar a transformação Hadamard na extração de recursos de uma imagem?

Eles são instâncias particulares das funções do Rademacher. Eles formam transformações ortogonais que podem, omitindo normalizações de potência, ser implementadas apenas com adições e subtrações e, potencialmente, deslocamentos binários. Basicamente, eles não requerem multiplicação, permitindo cálculos rápidos e pequenas necessidades de pontos flutuantes.

Seus coeficientes de vetor são feitos de $ \ pm 1 $ , que imitam uma versão binarizada de bases de seno ou cosseno. A ordem dos vetores Walsh é em sequência (em vez de frequência) que conta o número de mudanças de sinal. Eles desfrutam de algoritmos de borboleta semelhantes para uma implementação ainda mais rápida.

Sequências de Walsh de comprimento $ 2 ^ n $ também podem ser interpretadas como instâncias de uma wavelet Haar pacote.

Como tal, eles podem ser usados em qualquer aplicação onde bases cosseno / seno ou wavelet são usadas, com uma implementação muito barata. Em dados inteiros, eles podem permanecer inteiros e permitir transformações e compactação verdadeiramente sem perdas (de forma semelhante ao DCT inteiro ou wavelets binários ou binlet). Portanto, é possível usá-los em códigos binários. Eles também são usados em sensores de compressão.

Seu desempenho é frequentemente considerado pior do que outras transformações harmônicas em sinais naturais e imagens, devido à sua natureza em blocos. No entanto, algumas variantes ainda estão em uso, como para transformações reversíveis de cores (RCT) ou transformações de codificação de vídeo de baixa complexidade ( Transformação de baixa complexidade e quantização em H.264 / AVC ).

Alguma literatura:

• Agaian, SS, Hadamard Matrices and their Applications, 1985
• Beauchamp, KG, Walsh functions and their aplicações, 1975
• Harmut, HF, Transmission of information by ortogonal functions, 1970
• Algoritmo de compressão de vídeo em tempo real para a transformação de Hadamard processamento (NASA, 196)
• Um compressor de vídeo de transformação Hadamard adaptável em tempo real (NASA, 196)

Alguns links: Página da web

Descrição geral

Para distribuição gaussiana

Relatório

Comentários

• É ‘ melhor se você puder explicar por que cada link é bom.Mesmo um título completo do documento com link seria melhor.
• Tentei, mas o software do fórum estava falhando, então você obtém uma versão resumida. Se você quiser deletar tudo no estilo wiki-policial, faça-o com certeza.
• Não ‘ não acho que seja tanto ” wiki-policing ” neste caso, como tentar manter um padrão no formato de Q & A neste borda. Seu objetivo não é funcionar como um fórum. Portanto, o feedback sobre a sua contribuição não é sobre excluí-la, mas sim sobre aceitá-la, mas também certificar-se de que ela está de acordo com o padrão. Isso é comum na rede de troca de pilha. Eu acho que vale a pena editar a postagem.