Performance Evaluation of Pattern Matching Algorithms
Wanli Ouyang



 Federico Tombari



 Stefano Mattoccia

 Luigi Di Stefano

 Wai-Kuen Cham

 

INTRODUCTION

This page presents a performance evaluation of Full-Search (FS) - equivalent pattern matching algorithm. The results presented on this webpage are relative to the following paper:

          [1] 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 Analysis and machine Intelligence(TPAMI), Minor revision.

Pattern matching relates to the problem of matching a given pattern within a given image. Full search-equivalent pattern matching algorithms accelerate the pattern matching process and, at the same time, yield exactly the same result as the full search/exhaustive search.

A pattern matching DEMO is available here.

The algorithms included in our evaluation are the following ones:

  • LRP:  [2] M. G. Alkhansari. A fast globally optimal algorithm for template matching using low-resolution pruning. TIP, 10(4):526-533, Apr 2001.
  • PWHT: [3]  Y. Hel-Or and H. Hel-Or. Real time pattern matching using projection kernels. TPAMI, 27(9): 1430-1445, Sept. 2005.
  • PGCK: [4] G. Ben-Artz, H. Hel-Or, and Y. Hel-Or. The Gray-code filter kernels. TPAMI, 29(3):382-393. Mar. 2007. 
  • IDA: [5] Federico Tombari,Stefano Mattoccia, and Luigi Di Stefano. Full search equivalent pattern matching with incremental dissimilarity approximatinos. TPAMI, 31(1): 129-141. Jan. 2009.
  • FFT: [7] J.P. Lewis, Fast template matching. in Vision Interface 95, Quebec City, Canada, May 15-19 1995, pp. 120-123. [Source code on OpenCV]

* 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.

 

DATASET

A demo image showing an image under different levels of distortions

Datasets are from:
 http://people.csail.mit.edu/torralba/images
http://zulu.ssc.nasa.gov/mrsid
www.data-compression.info/corpora/lukascorpus

Details about the dataset 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

Please cite appropriately this webpage and [1] if you use this dataset for research or scientific purposes.


SELECTED EXP. RESULTS

 


SOFTWARE

It is possible to download the source code used for our evaluation. The code is in C. We used Visual studio 6.0 for compilation and linking. Once compiled, this code can be directly run on the dataset provided. The source code can be downloaded from here: 

             Source code in C

DISCLAIMER:

The code provided for our evaluation includes parts of code written by the authors who developed the original algorithms being evaluated. The distributed code and materials are protected by proprietary rights and, in particular, by copyright.

For research purposes: these proprietary rights are freely licensed for use and copy. Please cite their papers [2-7] and [1] appropriately if you use the provided code.

For commercial purposes: please refer directly to the authors who developed the algorithms and papers.

กก