Fast Exhaustive Pattern Matching and Block Matching

Introduction

Pattern Matching

Given an image I and a pattern P, pattern matching aims at determining all the candidate subwindows on I which are similar enough to P. In order to accomplish this task, a matching measure is computed between P and all possible candidate subwindows on I, then a threshold is used to discriminate between matching and mismatching patterns. A particular case of pattern matching is when only the best matching candidate on I with respect to P has to be found. Many different matching measures have been proposed: the most popular are those derived from the Lp norm (e.g. SAD, SSD) and those based on the cross-correlation (e.g. NCC, ZNCC).

Block Matching

Similarly to pattern matching, block matching, a widely used approach to perform motion estimation (e.g. for lossy video compression) computes a matching measure (typically the SAD) in order to find the most similar block pairs between two consecutive frames. For this reason, pattern matching, block matching and other tasks such as vector quantization can be all seen as particular instances of a common problem, known as Nearest-Neighbor Search (NNS).

Our approach

Since typically NNS is computationally expensive, an important research topic deals with developing novel approaches aimed at reducing the computational burden. These fall into two categories: exhaustive and non-exhaustive methods. Unlike non-exhaustive ones, exhaustive methods are able to speed-up the whole process without any loss in accuracy. In particular, indicating with FS (Full Search) the basic algorithm which evaluates all possible candidates, exhaustive approaches guarantee that their results are always the same as those yielded by FS.

We have been developing exhaustive approaches for different commonly used measures (NCC, ZNCC, SAD, SSD) and for different NNS problems. The common idea to all approaches is that, at each candidate, instead of computing the actual matching function, a pruning condition based on a rapidly-computable bounding function is tested. If this condition is verified, then the current candidate can be safely pruned without computing theh matching measure on it.

Results

Preliminary results are presented here, that deal with pattern matching based on dissimilarity measures (i.e. SAD, SSD) [2]. Results are shown in terms of speed-ups (i.e. ratios of measured execution times) yielded by our approach against the FS. In the SSD case we also compare our approach with the FFT, a commonly adopted method to speed-up exhaustively pattern matching tasks. The dataset used for the comparison is also shown, and is available upon request.

The overall result is that our approaches can dramatically speed-up pattern matching and block matching tasks based on NCC, ZNCC, SSD, SAD, the computational benefits being in most cases much higher than those yielded by state-of-the-art methods.

Dataset

paint 1,2,3	pcb3
plants	Ringo 1,2
Board 1,2,3	Wafer 1,2,3

References