Segmented Gray-Code Kernels for Fast Pattern Matching

Wanli Ouyang, Renqi Zhang and Wai-Kuen Cham

Abstract  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, which is the lowest among existing fast algorithms for Walsh Hadamard Transform on sliding windows.

This webpage introduces the fast Segmented Gray-Code Kernels and its fast algorithm in the following paper:

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

* 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

The Walsh Hadamard transform HN is a 2m x 2m matrix, the Hadamard matrix (scaled by a normalization factor), that transforms N=2m real numbers into 2m real numbers.

Fig. 1 WHT in natural order and sequency order.

It performs an orthogonal, symmetric, involutional, linear operation on 2m real numbers (or complex numbers, although the Hadamard matrices themselves are purely real).

 

The Gray-Code Kernels (GCK) is a generalization of WHT. Our proposed Segmented Gray-Code Kernels (SegGCK) is a special case of GCK. SegGCK is a lapped orthogonal transform(LOT). SegGCK can be computed very efficiently. To project input data onto u basis vectors, we only need O(u/k) operations, a sub-linear computational complexity.

 

In this paper, we also propose an algorithm that computes the sliding WHT by 3/4 additions per basis vector, which is faster than our previous work in [d].

 

 

ACKNOWLEDGMENTS

Many introductions 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 and Wai-Kuen Cham, "Fast algorithm for Walsh Hadamard transform on sliding windows", IEEE Trans. Pattern Anal. Mach. Intell., 32(1):165-171, Jan. 2010.

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

[f] 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

Source code

C code is available here. Please find the whole dataset from here to get the results on our paper. The code is in C using Visual studio 2008 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