Given a 3-D object (solid), it is possible to divide the exterior viewing space of the solid into maximally connected subspaces of vantage points such that the perspective views of the solid from all vantage points within a subspace have identical labeled line-junction graphs. We refer to such subspaces as the characteristic-view domains (CVDs) of the solid, and to a representative perspective view from within a domain, as a characteristic view (CV). The concept suggests a scheme for modeling 3-D objects in which the infinite number of possible views of a given solid are represented by a finite set of characteristic views (together with their respective projection-defining parameters). The concept was introduced more than 15 years ago as a modeling scheme to facilitate real-time recognition of 3-D objects. However, the difficulty of determining the CVs hindered its application. This article describes a technique for computing the characteristic views of general solids bounded by quadric surfaces (including polyhedra as a special case), and suggests how the technique can be used for 3-D object recognition.

Introduces the concept of the dominant views (DVs) of a solid object as those views that, in a sense to be defined, contain maximal visual information about the solid. The set of dominant views of a solid object is a minimal subset of the object's characteristic views (CVs) that represents all of the object's surfaces in the most general manner. The authors present a method for computing the dominant views of a solid object from its characteristic-view set and illustrate the method on some sample objects. By providing a basis for multi-level indexing of an object-model database, the DV concept should prove useful in object recognition and pose determination. A scheme for multi-level indexing is considered essential for solving the problem of inexact matching in multiview model-based recognition.>

An algorithm is presented for computing the characteristic views (CVs) of quadric-surfaced solids. The CVs are determined by analyzing the characteristic-view domains of the object by relating changes in the topology of the object's line structure to changes in the occlusion of 3D edges. The main task of the algorithm is to compute the envelope boundaries for viewpoint regions for which the object's visible-line projections have topologically equivalent line-junction graphs. By using the concepts of generalized edge, generalized face, and generalized vertex and using the techniques of order-of-visibility propagation and edge classification, the algorithm can efficiently compute both local and global visibility of edge segments, and therefrom compute the required envelope boundaries. This algorithm is shown to hold for quadric-surfaced solids in general and to treat a polyhedral object as a special case.>

A characteristic view (CV) class of a planar-faced solid (PFS) is a class of representative projection views of the solid such that all members of the class have isomorphic planar graph representation and can be related by a 3D geometric transformation. The viewing space of a PFS can be partitioned into regions called characteristic view domains (CVDs), such that a view of the PFS from any location within a region belongs to the same CV class and is different from all the CVs of the neighboring regions. The authors present a method of partitioning the viewing space into CVDs and finding the set of CV classes for a given PFS. Using the CV classes as the representation of the model object, they also present a method for model-based object recognition. Algorithms for representing, sorting, classifying, and graphically matching the CVs are given. All of these operations are needed in the object recognition method proposed.>

Polycurve codes is the name of a line-drawing model for describing object boundaries and contour lines. It belongs to chain-coding families such as chain codes and generalized chain codes. Polycurve codes make possible the direct extraction and labeling of predefined high-level line and arc segments from irregular object boundaries. Several algorithms for computing features of the objects from polycurve-encoded boundaries are presented. Some geometric calculation such as inverse and intersection points of two polycurves are also considered. The algorithms use look-up tables indexed by segment labels so that only elementary operations such as addition and subtraction may be required.>

The automatic placement of names on a geographic map, a seemingly straightforward computer task, is, in fact, remarkably complex. This paper describes the results of a research study which has led to the development of AUTONAP, an expert system for automatic name placement. The system attempts to emulate the manner in which an expert cartographer would place names. It utilizes heuristic knowledge about map placement and visual perception, embeds this in a set of explicit rules that form the knowledge base of the system, and draws on techniques from machine pattern analysis to achieve fully automatic placement of all the names in a map.

This paper examines a set of line-segment approximation codes for the representation of planar curves (the so-called generalized chain codes) and shows that the average quantization error (measure of code's precision) is directly proportional to the grid size and is independent of the form of the code. Thus, to achieve a desired level of precision for the representation of a line drawing, only the size of the grid need be determined; the form of the code can be chosen on the basis of other criteria, such as compactness, smoothness, or relative ease of encoding and processing.

An algorithm is presented for generating the optimum straight-line approximation for a plotter constrained to move a unit distance at a time in one of six equi-spaced directions. The algorithm facilitates the drawing of digital straight lines on a triangular grid.

This paper describes a computer program for constructing a description of solid bodies from a set of pictures taken from different vantage points. The bodies are assumed to be bounded by faces which are planar or quadric, and to have vertices formed by exactly three faces It is assumed that a preprocessor provides the program with line and junction information which it has extracted from the pictures. The preprocessor is expected to make mistakes, such as losing features or providing misinformation about their nature. A technique is presented for validating doubtful features as well as for matching corresponding features extracted from the different pictures. New grammar rules are developed for linedrawing projections of curved and planar bodies and are used as a tool in the scene analysis process. Each picture's data analysis is supported dynamically by the results obtained thus far in the other pictures' analysis. The analyzed data from all pictures are grouped into sets, each corresponding to a single face (flat or curved), whose nature is also determined. The sets are grouped again to correspond to the different bodies in the scene. The program written in PL/I has been tested successfully on several scenes.

A method for detecting sharp "corners" in a chain-coded plane curve is described. A measure for the prominence ("cornerity") of a corner is introduced. The effectiveness of the method is illustrated by means of a number of examples.

A cyclic-order property is defined for three-dimensional bodies with vertices formed by three faces. The property is useful in resolving ambiguities caused by the extraction of imperfect line data from photographs of such bodies. The property augments the grammatical rules-that govern the possibility or impossibility of the existence of three-dimensional bodies corresponding to particular two-dimensional line-structure projections.

Binary multiplication can be speeded up by taking two or more bits of the multiplier at a time. This note describes an exact method, based on the use of a discrete-time, finite-state system model, for calculating the gain in multiplication speed resulting from such a scheme. It is shown that the gain in speed is less than what had previously been obtained using an approximation formula.

The two-dimensional ``hidden-line'' problem is the problem of determining, by means of a computer algorithm, which edges or parts of edges of an arbitrary, nonintersecting polygon are visible from a specified vantage point in the plane of the polygon. The problem is an important one in the field of computer graphics, and is encountered, for example, in using a computer to determine the portion of an island's coastline visible from a ship offshore. Some propositions are introduced that facilitate the solution of this problem. A general algorithm for the solution is described, and illustrative examples are given of hidden-line problems solved with a digital computer.

This paper describes the development of a procedure that enables a digital computer to solve ``apictorial'' jigsaw puzzles, i.e., puzzles in which all pieces are uniformly gray and the only available information is the shape of the pieces. The problem was selected because it provided an excellent vehicle to develop computer techniques for manipulation of arbitrary geometric patterns, for pattern identification, and for game solving. The kinds of puzzles and their properties are discussed in detail. Methods are described for characterizing and classifying piece contours, for selecting and ordering pieces that are ``most likely'' to mate with a given piece, for determining likelihood of fit, for overcoming ambiguities, and for evaluation of the progressive puzzle assembly. An illustration of an actual computer solution of a puzzle is given.

A method is described which permits the encoding of arbitrary geometric configurations so as to facilitate their analysis and manipulation by means of a digital computer. It is shown that one can determine through the use of relatively simple numerical techniques whether a given arbitrary plane curve is open or closed, whether it is singly or multiply connected, and what area it encloses. Further, one can cause a given figure to be expanded, contracted, elongated, or rotated by an arbitrary amount. It is shown that there are a number of ways of encoding arbitrary geometric curves to facilitate such manipulations, each having its own particular advantages and disadvantages. One method, the so-called rectangular-array type of encoding, is discussed in detail. In this method the slope function is quantized into a set of eight standard slopes. This particular representation is one of the simplest and one that is most readily utilized with present-day computing and display equipment.

This article describes the design of a high speed electronic analog computing circuit which easily lends itself to time-sharing applications. By making use of a special high accuracy electronic switch and circuitry carefully designed to be independent of tube characteristics, it was possible to achieve a full-scale accuracy of better than 0.2 per cent over a wide range of input values. The unit described was built to carry out 400 complete multiplications and divisions in one second.