Semi‐real‐time algorithm for fast pattern matching. Issue 12 (1st December 2016)

• Record Type: Journal Article
• Authors: Dong, Jing; Liu, Haibo
• Is Part Of: IET image processing. Volume 10:Issue 12(2016)
• Page Start: 979
• Page End: 985
• Publication Date: 2016-12-01
• Subjects: image matching -- search problems; full search algorithm -- adaptive threshold -- base image candidate windows -- lower bounds -- orthogonal decomposition -- triangle inequality -- semireal‐time pattern‐matching algorithm -- semireal‐time algorithm; Image processing -- Periodicals; 621.36705
• DOI: 10.1049/iet-ipr.2016.0186
• Languages: English
• ISSNs: 1751-9659

Abstract

Abstract : A semi‐real‐time pattern‐matching algorithm consisting of an offline and online stage is proposed. The approach of the proposed algorithm is to perform a significant amount of the calculation required by pattern matching in the offline stage. This necessitates only a small amount of calculation in the online process to reject a great number of mismatched positions. The proposed algorithm first uses triangle inequality and orthogonal decomposition to derive the lower bounds of the distances between the pattern and the candidate windows of the base image. Then, mismatched candidate windows are rejected if their lower bounds exceed an adaptive threshold. The proposed method accelerates the online processing effectively while yielding the identical result as a full search algorithm. The proposed algorithm was compared with other state‐of‐the‐art algorithms and the result confirms that the proposed algorithm has a distinct speed advantage over the other algorithms for online processing.