Fast pattern matching using orthogonal Haar transform

Pattern matching is a widely used procedure in signal processing, computer vision, image and video processing. Recently, methods using Walsh Hadamard Transform (WHT) and Gray-Code kernels (GCK) are successfully applied for fast transform domain pattern matching. 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 × 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. Experimental results show the efficiency of pattern matching using OHT.