Dissertation/Thesis Abstract

Grammatical methods in computer vision
by Purdy, Eric, Ph.D., The University of Chicago, 2013, 212; 3557428
Abstract (Summary)

In computer vision, grammatical models are models that represent objects hierarchically as compositions of sub-objects. This allows us to specify rich object models in a standard Bayesian probabilistic framework. In this thesis, we formulate shape grammars, a probabilistic model of curve formation that allows for both continuous variation and structural variation. We derive an EM-based training algorithm for shape grammars. We demonstrate the effectiveness of shape grammars for modeling human silhouettes, and also demonstrate their effectiveness in classifying curves by shape. We also give a general method for heuristically speeding up a large class of dynamic programming algorithms. We provide a general framework for discussing coarse-to-fine search strategies, and provide proofs of correctness. Our method can also be used with inadmissible heuristics.

Finally, we give an algorithm for doing approximate context-free parsing of long strings in linear time. We define a notion of approximate parsing in terms of restricted families of decompositions, and construct small families which can approximate arbitrary parses.

Indexing (document details)
Advisor: Felzenszwalb, Pedro
Commitee: Amit, Yali, Goldsmith, John
School: The University of Chicago
Department: Computer Science
School Location: United States -- Illinois
Source: DAI-B 74/07(E), Dissertation Abstracts International
Subjects: Artificial intelligence, Computer science
Keywords: Computer vision, Context-free, Curve formation, Grammars, Shape grammars, Silhouettes
Publication Number: 3557428
ISBN: 978-1-303-00544-2
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy