New techniques for the analysis of two and three dimensional objects

Abstract

The results of an investigation carried out on certain pattern recognition aspects of a class of two-dimensional line drawings and three-dimensional objects are reported in this thesis. The motivation for the proposed schemes for coding and recognizing two- and three-dimensional objects originates from neurophysiological evidence on pattern and contour coding and edge feature extraction in the visual system of mammalian species. The thesis is divided into six chapters. A brief bibliographic survey of research activity in related areas and an introduction to the problem under consideration are given in the first chapter.

Chapter 2 This chapter deals with the study of a hypothetical model for visual recognition of alphanumerals. The model incorporates the concept of a short-line extractor neuron, the known structural organization (neurophysiological) of the mammalian visual cortex, and the concept of lateral inhibition. Based on the findings of Hubel and Wiesel that there are cortical cells with different orientations of their field axes, four basic types of short-line extractors are proposed to extract four types of short-line features. This follows the usual practice in pattern recognition studies of using a 3-bit quantization of the slopes of line segments in a given pattern. Alphanumerals are taken as the test patterns for the recognition task. It is found that correct recognition of the letters H and T requires the extraction of the largest number of features.

Chapter 3 The above ideas lead to the investigation of machine algorithms that duplicate the performance of short-line extractor neurons. To this end, given a pattern in digitized binary form, four different pairs of operators are proposed for extracting short-line features-namely, the medial lines of vertical, horizontal, right-inclined, and left-inclined line segments. This is made possible by introducing two new concepts: turning points and end points, which indicate the presence of a junction and an open end, respectively, in the pattern. The algorithm extracts these points during the first stage and, during the second stage, develops the medial line or skeleton of the given pattern using a simple search procedure. The proposed method and the results obtained are discussed in Chapter 5.

Chapter 4 The concepts of turning and end points introduced in Chapter 3 facilitate easy encoding of the class of two-dimensional line drawings considered. The code for a given line drawing is a sequence of turning and end points and is based on how these points are connected in the pattern. Using these informationally rich points from a topological perspective, a scheme for recognizing alphanumerals of a particular font is evolved using simple decision rules. From the code sequence developed for a pattern, it is shown that information about characteristics such as the number of independent loops, the number of junctions/nodes, the number of limbs in the pattern, and their topological arrangement can be extracted.

Chapter 5 The above concepts of coding two-dimensional line drawings are extended to address perceptual problems of three-dimensional objects by machine. Trihedral objects composed of long, thin, and narrow rectangular prisms connected at their ends are considered for this purpose. The specific tasks administered to the machine are as follows:

Given two object views, determine whether they portray objects of identical shape, mirror-image objects, partially identical objects, or partially mirror-image objects. Given one view of an object, visualize its other views resulting from known rotations.

The input format to the program is the two-dimensional line drawing (portraying a given three-dimensional object) in digitized binary form. From the set of all nodes (picture points where two lines meet at angles other than 180°) and the set of all junctions (picture points where more than two lines meet), a process of redundancy removal defines a set of cardinal nodes and cardinal junctions. These points indicate bends and open ends in the object and are the three-dimensional counterparts of turning and end points in the two-dimensional case. The skeleton of the three-dimensional object is obtained as an ordered and connected path passing through the cardinal points. The skeleton is represented as a sequence of slope-code numbers (numbers representing the different slopes of line segments in the given drawing). To solve the first task, the two sequences representing the skeletons of the two given views are tested for skeletal, mirror, partial skeletal, and partial mirror matches. A particular match reflects a corresponding shape relation between the objects portrayed by the two views. Such a study enables finer analysis leading to detection of shape relations and their correlation. Some results of computer simulation of the proposed model are also presented. To solve the second task, appropriate transformations are defined on the sequence representing the skeleton of the given view corresponding to the specified amount and sense of rotation. From the transformed sequence, the skeleton for the new view is obtained. The faces are constructed around this skeleton using knowledge of the transformed cardinal nodes and junctions.

Final Chapter The final chapter summarizes the results of the investigation carried out on the problems posed in the thesis. The scope for future research in this area is also indicated.