Fast exhaustive-search equivalent pattern matching through norm ordering

• We propose a fast exhaustive-search equivalent block matching algorithm.
• We combine our algorithm with other algorithms to provide faster algorithms.
• We tested on 14 datasets, each algorithm was tested more than 15 million times.
• Our results are up-to two orders of magnitude faster than state-of-art.
• We provide detailed analysis on performance of proposed algorithms.

Pattern matching is a fundamental problem in computer vision, and image and video processing. Exhaustive-search equivalent algorithms yield the same results as exhaustively searching all patterns in the image but significantly faster. In this paper, we propose a novel exhaustive-search equivalent algorithm that is combined with a number of state-of-art algorithms to provide a significantly faster alternative in the problem of finding nearest pattern according to a predefined distance measure. Our technique also shows high resilience to both blurring and JPEG compression types of noise. This is demonstrated in the paper with results from over 15 million runs for each compared algorithm.