Издательство MIT Press, 1986, -236 pp.
This book presents a computational mechanism for the interpretation of line drawings by means of which a machine can extract three-dimensional object structures from their pictures drawn on a two-dimensional plane. It is easy for a human being to understand what is represented by line drawings, so that they are frequently used in many stages of human communication, such as illustrations in books and engineering drawings in factories. For a machine, on the other hand, line drawings are simple collections of twodimensional line segments; some intelligent mechanism is required to extract three-dimensional information from them. How the machine can possess such intelligence is the main problem attacked throughout this book.
From a theoretical point of view this book provides a typical example of making humanlike intelligence by a simple computational mechanism. We are apt to think that the human ability to interpret line drawings is based on various kinds of human experiences, and hence a mechanism that mimics this ability should be supported by extensive and complicated knowledge about the outside world. However, it tus out that this ability can be realized by a simple mathematical procedure at least when the objects are restricted to planar faced solids. The computational mechanism presented here is not accompanied by a large database, but is composed of several simple procedures based on linear algebra and combinatorial theory; it can still mimic human flexible intelligence in picture perception.
From a practical point of view the results in this book can be applied to man-machine communication and robot vision. One of the main problems in a computer-aided system for geometric design is how to input data about object structures that are bo in a designer’s mind. The computational mechanism in this book makes the communication flexible in the sense that the system can extract object structures automatically from pictures drawn by the designer. In a robot vision system for recognizing the outside world, the present results can be used as an intermediate stage, which receives line drawings from an image processing stage and offers the descriptions of three-dimensional object structures to an object recognition stage. This book is mainly based on the author’s work during the past ten years, the first half of which was spent at the Electrotechnicai Laboratory and the other half at Nagoya University, on understanding line drawings. Among many others the author would like to express his thanks to Prof. Noboru Sugie of Nagoya University and Dr. Yoshiaki Shirai of the Electrotechnical Laboratory for guiding him to this interesting field of research; Prof. Masao Iri of Tokyo University for suggesting the importance of the combinatorial aspect of line drawings; Prof. Jun-ichiro Toriwaki of Nagoya University, Dr. Hiroshi Imai of Tokyo University, Prof. Henry Crapo of INRIA, Prof. Walter Whiteley of McGill University, Dr. Masaki Oshima of the Electrotechnical Laboratory, and Prof. Ken-ichi Kanatani of Gumma University for valuable communications; and Mr. Hiroki Iguchi of NEC Co. Ltd, for help in writing computer programs when he was a student at Nagoya University. Many of these people, in particular Profs. Iri, Sugie, and Kanatani, gave the author valuable comments on earlier versions of the manuscript. The author also wants to thank his wife Keiko Sugihara for helping him not only mentally but also physically by keeping their daughters from his room and thus giving him time for writing this book. The text was generated by ATF (Advanced Text Formatter for science) at the Nagoya University Computation Center.
Introduction
Candidates for Spatial Interpretations
Discrimination between Correct and Incorrect Pictures
Correctness of Hidden-Part-Drawn Pictures
Algebraic Structures of Line Drawings
Combinatorial Structures of Line Drawings
Overcoming the Superstrictness
Algorithmic Aspects of Generic Reconstructibility
Specification of Unique Shape
Recovery of Shape from Surface Information
Polyhedrons and Rigidity
This book presents a computational mechanism for the interpretation of line drawings by means of which a machine can extract three-dimensional object structures from their pictures drawn on a two-dimensional plane. It is easy for a human being to understand what is represented by line drawings, so that they are frequently used in many stages of human communication, such as illustrations in books and engineering drawings in factories. For a machine, on the other hand, line drawings are simple collections of twodimensional line segments; some intelligent mechanism is required to extract three-dimensional information from them. How the machine can possess such intelligence is the main problem attacked throughout this book.
From a theoretical point of view this book provides a typical example of making humanlike intelligence by a simple computational mechanism. We are apt to think that the human ability to interpret line drawings is based on various kinds of human experiences, and hence a mechanism that mimics this ability should be supported by extensive and complicated knowledge about the outside world. However, it tus out that this ability can be realized by a simple mathematical procedure at least when the objects are restricted to planar faced solids. The computational mechanism presented here is not accompanied by a large database, but is composed of several simple procedures based on linear algebra and combinatorial theory; it can still mimic human flexible intelligence in picture perception.
From a practical point of view the results in this book can be applied to man-machine communication and robot vision. One of the main problems in a computer-aided system for geometric design is how to input data about object structures that are bo in a designer’s mind. The computational mechanism in this book makes the communication flexible in the sense that the system can extract object structures automatically from pictures drawn by the designer. In a robot vision system for recognizing the outside world, the present results can be used as an intermediate stage, which receives line drawings from an image processing stage and offers the descriptions of three-dimensional object structures to an object recognition stage. This book is mainly based on the author’s work during the past ten years, the first half of which was spent at the Electrotechnicai Laboratory and the other half at Nagoya University, on understanding line drawings. Among many others the author would like to express his thanks to Prof. Noboru Sugie of Nagoya University and Dr. Yoshiaki Shirai of the Electrotechnical Laboratory for guiding him to this interesting field of research; Prof. Masao Iri of Tokyo University for suggesting the importance of the combinatorial aspect of line drawings; Prof. Jun-ichiro Toriwaki of Nagoya University, Dr. Hiroshi Imai of Tokyo University, Prof. Henry Crapo of INRIA, Prof. Walter Whiteley of McGill University, Dr. Masaki Oshima of the Electrotechnical Laboratory, and Prof. Ken-ichi Kanatani of Gumma University for valuable communications; and Mr. Hiroki Iguchi of NEC Co. Ltd, for help in writing computer programs when he was a student at Nagoya University. Many of these people, in particular Profs. Iri, Sugie, and Kanatani, gave the author valuable comments on earlier versions of the manuscript. The author also wants to thank his wife Keiko Sugihara for helping him not only mentally but also physically by keeping their daughters from his room and thus giving him time for writing this book. The text was generated by ATF (Advanced Text Formatter for science) at the Nagoya University Computation Center.
Introduction
Candidates for Spatial Interpretations
Discrimination between Correct and Incorrect Pictures
Correctness of Hidden-Part-Drawn Pictures
Algebraic Structures of Line Drawings
Combinatorial Structures of Line Drawings
Overcoming the Superstrictness
Algorithmic Aspects of Generic Reconstructibility
Specification of Unique Shape
Recovery of Shape from Surface Information
Polyhedrons and Rigidity