Line Drawing Interpretation

ISBN-13: 9781848002289 / Angielski / Twarda / 2008 / 262 str.

Martin Cooper

Opis

The computer interpretation of line drawings is a classic problem in arti?cial intelligence (AI) which has inspired the development of some fundamental AI tools, including constraint propagation, probabilistic relaxation, the characte- zation of tractable constraint classes and, most recently, the propagationof soft constraintsin?nite-domainoptimizationproblems. Line drawinginterpretation has many distinct applications on the borderline of computer vision and c- puter graphics, including sketch interpretation, the input of 3D object models 1 and the creation of 2 D illustrations in electronic documents. 2 I hope I have made this fascinating topic accessible not only to computer scientistsbutalsotomathematicians, psychologistsandcognitivescientistsand, indeed, to anyone who is intrigued by optical illusions and impossible or - biguous ?gures. This book could not have been written without the support of the CNRS, theFrenchCentreNational deRecherche Scienti?que, who?nancedmyone-year break from teaching at the University of Toulouse III. The UK Engineering and Physical Sciences Research Council also ?nanced several extended visits to the Oxford University Computing Laboratory. Section 9.1 is just a brief summary of the results on tractable constraints that have come out of this very productive joint research programme with David Cohen, Peter Jeavons and Andrei Krokhin. The various soft arc consistency techniques described in Chapter 8 were developed in collaboration with Thomas Schiex and Simon de Givry at INRA, Toulouse. I am also grateful to Ralph Martin and Peter Varley for their comments on the line-labelling constraints presented in Chapter 3.

Spis treści

Impossible Pictures.- Labeling Line Drawings of Polyhedra.- Discrete In°ation Using Cubic Corners.- A Rich Labeling Scheme for Curved Objects.- Depth Recovery Through Linear Algebra.- Wireframe Projections.- Simplification of Combinatorial Problems.- Tractability of Drawing Interpretation.- 3D Reconstruction of Ambiguous Pictures.

Blurb

The computer interpretation of line drawings is a classic problem in artificial intelligence and has inspired the development of some fundamental AI tools, including constraint propagation, probabilistic relaxation, tractable constraints, and (most recently) local simplification of optimisation problems.

Based on the author’s considerable research experience, this book looks at line drawing interpretation and constraint satisfaction, covering several landmark results in the field. It contains state-of-the-art reviews of work in both drawing interpretation and discrete optimisation, and is not just restricted to drawings of polyhedral objects, but also covers complex curved objects. Its novel approach to drawing interpretation combines new constraints with recent advances in soft constraint programming.

The book will become a standard reference in the field with its coverage of many theoretical results with formal proofs, particularly concerning necessary-and-sufficient conditions for realizability, simplification operations for combinatorial problems and tractability of drawing interpretation.

Martin Cooper makes this fascinating topic accessible not only to computer scientists, but also to mathematicians, psychologists and cognitive scientists – indeed to anyone intrigued by optical illusions and impossible or ambiguous figures.