Fast Full-Search-Equivalent Pattern Matching Using Asymmetric Haar Wavelet Packets
Wanli Ouyang, Tianle Zhao, Wai-Kuen Cham, Liying Wei · IEEE Transactions on Circuits and Systems for Video Technology · 2016
Pattern matching is widely used in signal processing, computer vision, and image and video processing. One efficient approach is to perform pattern matching in a transform domain that has good energy packing ability and so allows early rejection of most mismatched candidates. Calculating the transforms of pixels in sliding windows requires much computation, and so fast algorithms are employed. Existing methods require O(u) additions per pixel for projecting input pixels onto u 2D basis vectors. In this paper, we propose a new 2D transform, called asymmetric 2D Haar transform, and extend it to wavelet packets that contain exponentially large number of bases. A basis selection algorithm is then proposed to search for the optimal basis in the wavelet packets. A fast algorithm is also developed, which can compute u projection coefficients with only O(log u) additions per pixel. The results of experiments show that the proposed fast algorithm and the proposed transform can significantly accelerate the full-search-equivalent pattern matching process and outperform state-of-the-art methods.