The image analysis community has put much effort into developing systems for the automatic reading of various types of documents containing text, graphic information, and pictures. A closely related but much more problematic task is the reading and interpretation of line drawings such as maps, engineering drawings, and diagrams. This book considers the problem in detail, analyzes its theoretical foundations, and analyzes existing approaches and systems.
The rapid growth of computer facilities and their peripheral devices has led to their wide influence on all spheres of human activity. Although originally developed for mathematical calculations in the 1960s and 70s, they began to be used for more complex tasks such as OCR, voice recognition, and graphical document interpretation. The ever-increasing amount of paper records precipitated research into electronic storage and organization of graphical information. With the fast development of inputoutput devices such as digitizers, scanners, and plotters, this task became more realistic, and by the end of the 1970s, the first systems for text recognition were being developed. Attention then turned to graphical information input devices. Although they were at first too expensive to be practical, further progress in hardware design led to less costly peripheral devices and computers, and now nearly every small company and an increasing number of individuals have them. From the mathematical point of view, that period of the late 1970s and onward has been characterized by increasing attention to image processing and pattern recognition algorithms that has led to increased software development. Along with theoretical developments, particular attention has been paid to development of task-oriented systems in each specific field. The image analysis community has put much effort into developing systems for the automatic reading of various types of documents containing text, graphical information, and pictures. A closely related but much more problematic task is the reading and interpretation of line drawings such as maps, engineering drawings, and diagrams. This book considers the problem in detail, analyzes its theoretical foundations, and examines existing approaches and systems. The volume is organized in the sequence in which line drawings are usually analyzed. The first chapter considers the problem of line-drawing interpretation. A comparison is made between manual and automatic line-drawing input, and between vector and raster types of information representation; line-drawing specifics are analyzed in detail. A brief overview of the existing research systems is given as well as commercial systems existing in the Russian market. The second chapter is devoted to a general methodology of the line-drawing interpretation process. First, the main requirements for an interpretation technology are given. We then consider the basic technology stages and show how an initial image is transformed to a final representation. All intermediate image models are classified and described in detail. Finally, possible output image representations for maps and engineering drawings are considered. The third chapter addresses image scanning and binarization. The main characteristics of existing scanners are shown along with how they can be used to input line drawings. An analysis of existing image file formats is given, leading to a discussion of the binarization of gray-scale images. Finally, the two principal theoretical tools for binary image processingCthe distance transform and mathematical morphologyCare introduced. The binary image preprocessing stage is analyzed in Chapter 4. First, the general principles of raster-to-vector transform of binary images are introduced. Then, noise reduction algorithms for binary images are presented, as well as classification of thinning algorithms and a developed thinning algorithm. The medial axis transform operation, to obtain object middle lines, and image contouring are also discussed. Chapter 5 addresses the main techniques for image vectorization. Feature extraction and thinned image vectorization stages are described, polygonal approximation algorithms are classified, and an example of a data structure to represent the vectorized images is given. Since the vectorized image usually has defects (structural noise), algorithms to reduce object defects are considered. The sixth chapter is devoted to recognition of cartographic objects. A general methodology of map recognition is proposed that incorporates the three main object classes: line objects, area and texture objects, and symbols. Its classification is given and algorithms to recognize these object classes are described. Note that recognition algorithms for line objects and symbols are based on vector object representation, while recognition of texture objects is based on raster representation. Chapter 7 examines the problem of engineering drawing (ED) entities recognition. Specifics of ED image vectorization are introduced that take into account as much information about the initial drawing as possible. Algorithms to recognize all main ED entitiesCarcs, circles, line types, dimensions, cross-hatching areas, and blocksCare proposed. Recognition examples are given. The final chapter explores output image representation. Because automatic recognition alone cannot produce the required output, interactive techniques for map interpretation are described. Control of the digitized data is considered and its main notions are introduced. Existing devices for drafting the vectorized image models are investigated. Practical applications of map and engineering drawing interpretation, as well as recommendations for design of such systems, are given. Finally, topics for further development of this problem are discussed. We have attempted to examine all problems of line-drawing interpretation and hope this book will be useful for the understanding and creation of these systems.