ACM SERIES FORWARD -- Henry S. Baird

Series Forward, by Charles L. Bradshaw, Chairman, Awards Committee, ACM.

This book is being published by The MIT Press as an outgrowth of the annual contest for the best doctoral dissertation in computer-related science and engineering. The contest was initiated in 1982 and is co-sponsored by ACM and The MIT Press.

The Distinguished Doctoral Dissertation Series has been created to recognize that some of the theses considered in the final round of selecting a contest winner also deserve publication. In the judgment of the ACM selection committee and The MIT Press, this thesis is of such high quality that it deserves special recognition in this new series.

Dr. Henry S. Baird wrote his thesis on "Model-Based Image Matching Using Location" at Princeton University. The thesis work was supervised by Professor Kenneth Steiglitz and was submitted to the 1984 competition. The Doctoral Dissertation Award Committee of the ACM recommended the publication of this thesis because it presents an elegant solution to the problem of matching a known "model" shape with an observed image of it. The assumption is that by translating, rotating, and scaling, one can match features found in the image with features of the model. Each feature is observed with some location error whose worst-case bounds are known. The thesis shows that this problem can be recast as the solution of a series of sets of linear inequalities, and so can be attacked using the Simplex and Soviet ellipsoid algorithms, among others. Surprisingly, the ellipsoid method runs substantially faster than Simplex for this problem. In addition, the method is shown to run in time linearly proportional to the number of features (for objects of reasonable complexity).

The committee found the statement and solution of the problem to be both elegant and relevant. The thesis is an excellent example of the interplay of theory and practice.