Performance Evaluation of Pattern Matching Algorithms
Wanli Ouyang



 Federico Tombari



 Stefano Mattoccia

 Luigi Di Stefano



 Wai-Kuen Cham

กก

List of the datasets used for comparison:

Dataset Image size Pattern size
S1-1 160x120 16x16
S2-1 320x240 16x16
S2-2 320x240 32x32
S3-1 640x480 16x16
S3-2 640x480 32x32
S3-3 640x480 64x64
S4-1 1280x960 16x16
S4-2 1280x960 32x32
S4-3 1280x960 64x64
S4-4 1280x960 128x128
S5-1 2560x1920 16x16
S5-2 2560x1920 32x32
S5-3 2560x1920 64x64
S5-4 2560x1920 128x128

List of algorithms:

Denotation Paper
LRPsld
(Our new implementation)		 M. G. Alkhansari. A fast globally optimal algorithm for template matching using low-resolution pruning. TIP, 10(4):526-533, Apr 2001.
LRPcan
 (Our new implementation)
LRPhier
 (Our new implementation)
IDA

F. Tombari,S. Mattoccia, and Luigi Di Stefano, Full search-equivalent pattern matching with incremental dissimilarity approximations. TPAMI., vol. 31, no. 1, pp. 129-141, Jan. 2009.
PWHT

Y. Hel-Or and H. Hel-Or. Real time pattern matching using projection kernels. TPAMI, 27(9):1430-1445, Sept. 2005.
PGCK

G. Ben-Artz, H. Hel-Or, and Y. Hel-Or. The Gray-code filter kernels. TPAMI, 29(3):382-393, Mar. 2007.
FWHT

Wanli Ouyang and Wai-Kuen Cham. Fast algorithm for Walsh Hadamard transform on sliding windows. TPAMI, 32(1):165-171, Jan. 2010. [Full text *] [Powerpoint]

FFT

J.P. Lewis, Fast template matching. in Vision Interface 95, Quebec City, Canada, May 15-19 1995, pp. 120-123. [Source code on OpenCV]

Selected experimental results:

The experimental results are measured as speed-ups over the FS algorithm in terms of execution time. As an example, the speed-up of IDA over FS in execution time is measured as the execution time required by FS divided by that required by IDA. The larger the speed-up, the faster the algorithm.

A demo image showing an image under different levels of distortions

Speed-ups in execution time for images with Gaussian noise when SSD is used.
``I: 160x120-T: 16x16'' corresponds to image size 160x120 and pattern size 16x16.
G(1) => G(4) larger noise

Speed-ups in execution time for blurred images when SSD is used.
``I: 160x120-T: 16x16'' corresponds to image size 160x120 and pattern size 16x16.
B(1) => B(5) more blur

Speed-ups in execution time for JPEG compressed images when SSD is used.
``I: 160x120-T: 16x16'' corresponds to image size 160x120 and pattern size 16x16.

J(1) => J(5) more artifacts caused by compression

Speed-ups in execution time for images with Gaussian noise when SAD is used.
``I: 160x120-T: 16x16'' corresponds to image size 160x120 and pattern size 16x16.

Speed-ups in execution time for blurred images when SAD is used.
``I: 160x120-T: 16x16'' corresponds to image size 160x120 and pattern size 16x16.

Speed-ups in execution time for JPEG compressed images when SAD is used.
``I: 160x120-T: 16x16'' corresponds to image size 160x120 and pattern size 16x16.

กก

กก