Apa itu Walsh-Hadamard Transform dan apa gunanya?

Saya mencoba untuk belajar sendiri tentang WHT tetapi sepertinya tidak ada banyak penjelasan yang baik tentang itu secara online di mana saja. Saya pikir saya sudah menemukan cara menghitung WHT, tapi saya benar-benar mencoba memahami mengapa itu dianggap berguna dalam domain pengenalan gambar.

Apa yang istimewa dari itu, dan sifat apa yang dihasilkannya dalam sinyal yang tidak akan muncul pada transformasi Fourier klasik, atau transformasi wavelet lainnya? Mengapa ini berguna untuk pengenalan objek seperti yang ditunjukkan di sini ?

NASA dulu menggunakan transformasi Hadamard sebagai dasar untuk mengompresi foto dari penyelidikan antarplanet selama 1960-an dan awal 70-an. Hadamard adalah pengganti yang lebih sederhana secara komputasi untuk transformasi Fourier, karena tidak memerlukan operasi perkalian atau pembagian (semua faktor plus atau minus satu). Operasi penggandaan dan pembagian sangat intensif waktu pada komputer kecil yang digunakan di pesawat ruang angkasa itu, sehingga menghindarinya akan bermanfaat baik dalam hal waktu komputasi dan konsumsi energi. Tetapi sejak pengembangan komputer yang lebih cepat dengan pengganda satu siklus, dan kesempurnaan algoritma yang lebih baru seperti Fast Fourier Transform, serta pengembangan JPEG, MPEG, dan kompresi gambar lainnya, saya percaya Hadamard tidak lagi digunakan. Namun, Saya mengerti ini mungkin akan menjadi comeback untuk digunakan dalam komputasi kuantum. (Penggunaan NASA berasal dari artikel lama di NASA Tech Briefs; atribusi tepat tidak tersedia.)

Koefisien transformasi Hadamard semuanya +1 atau -1. Fast Hadamard Transform karenanya dapat dikurangi menjadi operasi penjumlahan dan pengurangan (tidak ada pembagian atau penggandaan). Ini memungkinkan penggunaan perangkat keras yang lebih sederhana untuk menghitung transformasi.

Jadi biaya atau kecepatan perangkat keras mungkin merupakan aspek yang diinginkan dari transformasi Hadamard.

Lihatlah makalah ini jika Anda memiliki akses, saya telah menempelkan abstrak di sini Pratt, WK; Kane, J .; Andrews, HC; , "Hadamard mentransformasikan pengkodean gambar," Prosiding IEEE, vol.57, no.1, hlm. 58-68, Januari 1969 doi: 10.1109 / PROC.1969.6869 URL: http://ieeexplore.ieee.org/stamp /stamp.jsp?tp=&arnumber=1448799&isnumber=31116

Abstrak Pengenalan algoritma transformasi Fourier yang cepat telah mengarah pada pengembangan teknik pengkodean transformasi gambar Fourier dimana transformasi Fourier dua dimensi dari suatu gambar ditransmisikan melalui saluran daripada gambar itu sendiri. Devlopement ini selanjutnya mengarah pada teknik pengkodean gambar terkait di mana gambar diubah oleh operator matriks Hadamard. Matriks Hadamard adalah array kuadrat dari plus dan minus yang baris dan kolomnya ortogonal satu sama lain. Algoritma komputasi berkecepatan tinggi, mirip dengan algoritma transformasi Fourier cepat, yang melakukan transformasi Hadamard telah dikembangkan. Karena hanya penambahan dan pengurangan bilangan real diperlukan dengan transformasi Hadamard, urutan keunggulan kecepatan mungkin dimungkinkan dibandingkan dengan transformasi kompleks Fourier.

Ingin menambahkan bahwa m-transform (matriks Toeplitz yang dihasilkan oleh m-sequence) dapat didekomposisi menjadi

P1 * WHT * P2

di mana WHT adalah Transform Walsh Hadamard, P1 dan P2 adalah permutasi (ref: http://dl.acm.org/citation.cfm?id=114749 ).

m-transform digunakan untuk sejumlah hal: (1) identifikasi sistem ketika sistem terganggu dengan noise dan (2) secara virtual dari (1) mengidentifikasi fase lag dalam sistem yang terganggu dengan noise

untuk (1), m-transform memulihkan kernel sistem ketika rangsangannya adalah urutan-m, yang berguna dalam neurofisiologi (misalnya http://jn.physiology.org/content/99/1/367. penuh dan lain-lain) karena ini adalah daya tinggi untuk sinyal pita lebar.

Untuk (2), Kode emas dibuat dari m-sequence (http://en.wikipedia.org/wiki/Gold_code).

Saya cukup senang menyaksikan kebangkitan di sekitar transformasi Walsh-Paley-Hadamard (atau kadang-kadang disebut Waleymard), lihat Bagaimana kita dapat menggunakan transformasi Hadamard dalam ekstraksi fitur dari gambar?

$\pm 1$

$2^n$

Dengan demikian, mereka dapat digunakan dalam aplikasi apa pun di mana basis cosinus / sinus atau wavelet digunakan, dengan implementasi yang sangat murah. Pada data integer, mereka dapat tetap integer, dan memungkinkan transformasi dan kompresi yang benar-benar lossless (mirip dengan integer DCT atau wavelet atau binlet biner). Jadi seseorang dapat menggunakannya dalam kode biner.

Kinerja mereka sering dianggap lebih buruk daripada transformasi harmonik lainnya pada sinyal dan gambar alami, karena sifatnya yang kuning. Namun, beberapa varian masih digunakan seperti untuk transformasi warna reversibel (RCT) atau transformasi pengkodean video dengan kompleksitas rendah ( Transformasi kompleksitas rendah dan kuantisasi dalam H.264 / AVC ).

Beberapa literatur:

• Agaian, SS, Hadamard Matriks dan Aplikasi Mereka, 1985
• Beauchamp, KG, fungsi Walsh dan aplikasi mereka, 1975
• Harmut, HF, Transmisi informasi oleh fungsi ortogonal, 1970
• Algoritma kompresi video waktu-nyata untuk pemrosesan transformasi Hadamard (NASA, 196)
• Kompresor video transformasi Hadamard adaptif real-time (NASA, 196)

Beberapa tautan: Halaman Web

Gambaran umum

Untuk distribusi Gaussian

Melaporkan