Problems of computational and information complexity in machine vision and learning
Sanjeev R. Kulkarni, Sanjoy K. Mitter · 1991
In this thesis, we consider a number of problems in the areas of machine vision and learning. Our results take steps towards understanding the computational and information complexity of problems in areas such as machine vision and signal processing. In the first part of the thesis, we study problems concerning computational requirements/limitations in machine vision. We first consider relationships between variational methods and discrete Markov random field formulations for the problem of image restoration and segmentation. Several discrete formulations are presented which correctly approximate the continuous segmentation problem. The results for the segmentation problem lead us to consider a question concerning the computation of the length of a digitized contour. It is shown that for a particular model of parallel computation, length cannot be computed locally with a rectangular digitization, but can be computed locally using a random tesselation and an appropriate deterministic one. Finally, we study the complexity of model based recognition and show that certain formulations of model based recognition are NP-complete. In the second part of the thesis, we study a number of extensions to models in machine learning with a view towards obtaining information complexity results applicable to areas such as machine vision and signal processing. We first consider extensions to the Probably Approximately Correct (PAC) learning model, including learning over a class of distributions, active learning, and learning with generalized samples. We study a particular application of learning with generalized samples to a problem of reconstructing a curve by counting intersections with straight lines. Our results refine a classical result from stochastic geometry. Finally, we consider a problem concerning the classification of an unknown probability measure from empirical data. Using large deviations techniques, we simplify and extend previous results on classifying the mean of a random variable. We also study the much more general case of classifying the measure itself, and consider applications to density estimation and the problem of order determination of a Markov chain. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)