Wanli Ouyang, Renqi Zhang and Wai-Kuen Cham

Wanli Ouyang, Renqi Zhang and Wai-Kuen Cham,
"Fast pattern matching using orthogonal Haar
transform ", CVPR2010 [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.

**Feature extraction from images**

Many image processing and computer
vision applications require extracting information from images. In many such
applications, however, extracting a large amount of features from data is
prohibited due to time limitations. This limitation is even more severe when
dealing with video data in which features are extracted from a large amount of
images. For example, the summation of pixels in a *N*_{1}x*N*_{2}
rectangular region, called rectangle sum here, is a basic operation. Haar like features,
which are built on on rectangle sum, are also widely
used in computer vision applications.

**The proposed strip sum**

Without fast algorithm, the summation of
pixels in a *N*_{1}x*N*_{2}
rectangular region requires *N*_{1}*N*_{2}-1
additions. In the paper, we introduce a data structure (strip
sum) as shown in Fig. 1 that computes sum of pixels in a rectangle by 1 addition.

Fig. 1 Use strip sum to compute sum of pixels in a rectangle.

**The proposed Orthogonal Haar
Transform (OHT)**

Fig. 2 The 4x4 orthogonal Haar transform (OHT).

We
also introduce a transform that requires *O*(log* u*)
additions per pixel to project *N*_{1}x*N*_{2} input window onto *u* basis vectors. An example for
the proposed OHT is shown in Fig. 2.

Among the fast WHT algorithms on sliding windows in [a][b][c], our proposed algorithm in [a] is the fastest.

Comparison of the proposed OHT using the proposed algorithm and WHT using the algorithm in [a] is shown in Fig. 3 and Fig. 4.

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

Fig. 4 The percentage of energy extracted from data as a function of the number of basis vectors (a) and number of operations required (b). With the same number of bases, the energy extracted by OHT is very similar to WHT. However, OHT requires much fewer operations in extracting energy.

The transform and the data structure can be applied for pattern matching as shown in the Fig.3. When applied for pattern matching, the algorithm finds out the same result as Full search (exhaustive search) and significantly saves the computation required.

**Experimental
results **

**Where
is my cup?**

In
the following video (enable ActiveX control to see the video), pattern matching
the proposed algorithm requires 0.015 second to locate the cup using pattern
matching. In the video, a 64x64 pattern is sought in a given 640x480 image. 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.

[a] **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. Webpage and source code

[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**, 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

[e] **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**

Source 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 OHT, 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