Fast pattern matching using orthogonal Haar transform

Wanli Ouyang, Renqi Zhang and Wai-Kuen Cham

Abstract: This paper introduces strip sum on the image. The sum of pixels in a rectangle can be computed by one addition using the strip sum. Then we propose to use the orthogonal Haar transform (OHT) for pattern matching. Applied for pattern matching, the algorithm using strip sum requires O(log u) additions per pixel to project input data of size N by N onto u 2-D OHT basis while existing fast algorithms require O(u) additions per pixel to project the same data onto u 2-D WHT or GCK basis.

This webpage introduces the transform and algorithm of the following paper:

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 N1xN2 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 N1xN2 rectangular region requires N1N2-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 N1xN2 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