Fast algorithm for Walsh Hadamard transform on sliding windows

Wanli Ouyang and Wai-Kuen Cham

AbstractThis paper proposes a fast algorithm for Walsh Hadamard Transform on sliding windows which can be used to implement pattern matching most efficiently. The computational requirement of the proposed algorithm is about 1.5 additions per projection vector per sample, which is the lowest among existing fast algorithms for Walsh Hadamard Transform on sliding windows.

This webpage introduces the fast Walsh Hadamard transform algorithm of the following paper:

Wanli Ouyang and Wai-Kuen Cham, "Fast algorithm for Walsh Hadamard transform on sliding windows", IEEE Trans. Pattern Analysis and machine Intelligence, 32(1):165-171, Jan. 2010. [Full text *] [Powerpoint

]

* Personal use of these materials is  permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from IEEE.

Introduction (from Wikipedia)

Fig. 1 WHT in natural order and sequency order.

Application of WHT

In computer vision, it is used in pattern matching, road/path tracking , mouth tracking , wide baseline image matching, scene labeling, texture synthesis and augmented reality.

WHT is also used in data encryption, as well as many signal processing and data compression algorithms, such as HD Photo and MPEG-4 AVC. In video compression applications, it is usually used in the form of the sum of absolute transformed differences.

WHT is used in Quantum computation. As pointed out in Wikipedia, many quantum algorithms use the Hadamard transform as an initial step.

The Nlog(N) fast WHT algorithm

Naive implementation of the WHT would have a computational complexity of O(N2). The fast WHT algorithm as show in Fig. 2 requires only NlogN additions or subtractions. One of these algorithms is in [a].

Fig. 2 The fast Walsh Hadamard transform applied to a vector of length 8 (From Wikipedia).

The 1.5N-1 fast WHT algorithm -- This paper

This paper proposes a fast algorithm for Walsh Hadamard Transform on sliding windows which can be used to implement pattern matching most efficiently. The computational requirement of the proposed algorithm is about 1.5 additions per projection vector per sample. The proposed algorithm requires 1.5N-1 additions for transforming N numbers into N real numbers. A comparison of our proposed algorithm and the algorithm in [a] is shown in Fig. 3.

Other famous WHT algorithms on sliding windows are in [b][c]. In [d], we propose a new transform and its fast algorithm.

Fig. 3 The number of operations as a function of the WHT transform size N for the algorithm in [a] and our algorithm.

New paper is here [f], about 1.33N additions for WHT.

Experimental results (where is my cup?)

The proposed fast WHT algorithm is utilized for pattern matching. The algorithm finds out the same result as Full search (exhaustive search) and significantly saves the computation required.

In the following video (enable ActiveX control to see the video), pattern matching the proposed algorithm requires lees than 0.1 second to locate the cup using pattern matching. The experiment considers image without noise and image with Gassian noise, Image blur and JPEG compression disturbances.  This algorithm guarantees to find the global optimum in pattern matching application.

 

ACKNOWLEDGMENTS

Many introduction of WHT and fast WHT algorithm in this webpage are directly copied from Wikipedia. To avoid annoyance, we did not provide reference to Wikipedia for all places.

 

Reference

[a] Fino, B.J., and Algazi, V.R., 1976, "Unified Matrix Treatment of the Fast Walsh-Hadamard Transform," IEEE Transactions on Computers 25: 1142-1146.

[b] Y. Hel-Or and H. Hel-Or, "Real Time Pattern Matching Using Projection Kernels," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 9, pp. 1430-1445, Sept. 2005.

[c] G. Ben-Artzi, H. Hel-Or, and Y. Hel-Or, "The Gray-Code Filter Kernels," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 29, no. 3, pp. 382-393, Mar. 2007.

[d] Wanli Ouyang, Renqi Zhang and Wai-Kuen Cham, "Fast pattern matching using orthogonal Haar transform ", In Proc. IEEE CVPR 2010, Webpage and source code.

[e] Wanli Ouyang, Federico Tombari, Stefano Mattoccia, Luigi Di Stefano, and Wai- Kuen Cham, "Performance Evaluation of Full Search Equivalent Pattern Matching Algorithms, " IEEE Trans. Pattern Anal. Mach. Intell., 34(1):127-143, Jan. 2012. Webpage and source code

 

[f] Wanli Ouyang and Wai-Kuen Cham, "Segmented Gray-Code Kernels for Fast Pattern Matching", IEEE Trans. Image Processing, 22(4):1512-1525, Apr. 2013. Webpage and source code

Source code

Matlab code is available here. The code is in C using Visual studio 6.0 as the compiling environment.

Please note the "Conditions of Use and Disclaimer" below for this code.

 Conditions of Use and Disclaimer:

You are only granted a limited right to use this software for your
personal non-commercial use.

This software is provided as SHAREWARE for testing and evaluating
purposes and cannot be sold or used in any commercial way, or
distributed, with or without consideration and whether on its own or
bundled with any commercial package, or by accompanying books, magazines
or any publication in any media without express written permission from
the owner.

The owner of this software accepts no responsibility for any damages
resulting from any use relating to this software and makes no warranty
or representation, either express or implied, including but not limited
to, any implied warranty of merchantability or fitness for a particular
purpose. This software is provided "AS IS", and you, as a limited right
user, assume all risks when using it.

This software is intended for personal non-commercial use only.

For any other use of the code, whether commercial or otherwise, please make
enquiries by writing to:

Technology Licensing Office
The Chinese University of Hong Kong
Shatin, N.T., Hong Kong

Email: tech_license@cuhk.edu.hk