An improved method of processing two- and three-dimensional image data to locate known shapes called "geometric primitives" involves (1) extraction of edges and other relevant image features and (2) performing a hierarchical search, in a space of parameters of equations that describe the shapes of the features, for those parameters that represent the geometric primitives. This method is inspired by prior object-recognition methods in which parameter spaces are recursively divided and pruned. The most closely related prior methods of this type are based on variations of the Hough transform. Whereas the prior methods have generally offered robustness or computational efficiency but not both, this method offers both, along with other advantages: It enables the efficient and robust extraction of geometric primitives from noisy and incomplete data that include many distracting data, without need for initial estimates of the locations of the geometric primitives.
In this method, one extracts geometric primitives from image data in the following way: One searches for parameters that satisfy a quantitative acceptance criterion based on the number of data features that approximate geometric primitives within a specified error measure. The search involves the subdivision of the parameter space into rectilinear cells, possibly starting from one or a few large cell(s). Each point in the parameter space represents a candidate position of a geometric primitive in the data. The cells are volumes of the parameter space and thus represent continuous ranges of locations of geometric primitives in the parameter space.
Each cell in the parameter space is tested to determine whether it can contain the parameters of a primitive that satisfies the acceptance criterion. If the acceptance criterion is not satisfied, the cell is pruned. If the acceptance criterion is satisfied, then the cell is split into two subcells and the subcells are examined recursively. When the smallest specified cell size is reached, the primitive at the center of the cell is tested to determine whether it meets the acceptance criterion.
At each state in this recursive process of division and pruning, the test is performed by an efficient algorithm that is conservative in that it never rules out a cell that contains a good primitive. Although this test can sometimes fail to rule out a cell that does not contain any good primitive, this failure does not result in false positives in the end because false positives are ruled out in the subsequent tests performed at subsequent finer subdivisions.
An interesting facet of this method is that a hierarchy is constructed not only in the parameter space, but also in the image feature space. This makes it possible for many image features to be pruned at each step with little computation, in addition to the pruning in the parameter space. Empirical evidence suggests that this hierarchical pruning reduces the complexity of the extraction process. In cases in which the number of data greatly exceed that needed for extraction of geometric primitives, robust random sampling can also be used to increase speed.
In some initial test cases, the geometric primitives were relatively simple shapes (circles and cylinders). The test cases were representative of three different image-recognition problems: identifying craters in digital images of planetary bodies, detecting the predominantly cylindrical bodies of unexploded bombs in images of a military test range, and detecting circles in an engineering drawing (see figure). Examples of other potential applications include locating parts for robotic assembly and detecting symbols in engineering drawings for transcription by computer.
This work was done by Clark F. Olson of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp under the Information Sciences category.
NPO-20941
