Fast pattern matching using Black Sheep algorithm

Pattern matching has found wide application in signal processing, computer vision, image and video processing. Recently, the Incremental Dissimilarity Approximations (IDA) algorithm is successfully applied for pattern matching. This paper proposes a method, called Black Sheep algorithm, which utilizes unmatched sub-block to eliminate all blocks that contain this sub-block. Then Black Sheep rejection condition and Black Sheep threshold are proposed to further relieve the burden of computation. Experiment results show the high efficiency of the proposed algorithm.