Return to search

Fast pattern matching and its applications. / CUHK electronic theses & dissertations collection

After that, strip sum and orthogonal Haar transform are proposed. The sum of pixels in a rectangle can be computed by one addition using the strip sum. Then this thesis proposes to use the orthogonal Haar transform (OHT) for pattern matching. Applied for pattern matching, the fast OHT algorithm using strip sum requires O(log u) additions per pixel to project input data of size N1 x N2 onto u 2-D OHT bases. Experimental results show the efficiency of pattern matching using OHT. / Firstly, this thesis proposes a fast algorithm for Walsh Hadamard Transform (WHT) on sliding windows which can be used to implement pattern matching efficiently. / Support vector machine (SVM) is a widely used classification approach. Direct computation of SVM is not desirable in applications requiring computationally efficient classification. To relieve the burden of high computational time required for computing SVM, this thesis proposes a transform domain SVM (TDSVM) using pruning that computes SVM much faster. Experimental results show the efficiency in applying the proposed method for human detection. / Then this thesis analyzes and compares state-of-the-art algorithms for full search equivalent pattern matching. Inspired by the analysis, this thesis develops a new family of transforms called the Kronecker-Hadamard Transform (KHT) of which the GCK family is a subset and WHT is a member. Thus, KHT provides more choices of transforms for representing images. Then this thesis proposes a new fast algorithm that is more efficient than the GCK algorithm. All KHTs can be computed efficiently using the fast KHT algorithm. Based on the KHT, this thesis then proposes the segmented KHT (SegKHT). By segmenting input data into Ls parts, the SegKHT requires 1/Ls the computation required by the KHT algorithm in computing basis vectors. Experimental results show that the proposed algorithm can significantly accelerate the pattern matching process and outperforms state-of-the-art methods. / This thesis aims at improving the computational efficiency in pattern matching. / Ouyang, Wanli. / Adviser: Wai Kuen Cham. / Source: Dissertation Abstracts International, Volume: 73-04, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 143-147). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_344754
Date January 2011
ContributorsOuyang, Wanli., Chinese University of Hong Kong Graduate School. Division of Electronic Engineering.
Source SetsThe Chinese University of Hong Kong
LanguageEnglish, Chinese
Detected LanguageEnglish
TypeText, theses
Formatelectronic resource, microform, microfiche, 1 online resource (xxii, 147 leaves : ill.)
RightsUse of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/)

Page generated in 0.0018 seconds