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
This Brief includes a Technical Support Package (TSP).
Finding Known Shapes in an Image by Pruning Parameter Space
(reference NPO-20941) is currently available for download from the TSP library.
Don't have an account?
Overview
This document presents a novel method for extracting geometric primitives from two-dimensional (2D) and three-dimensional (3D) image data, developed by the Jet Propulsion Laboratory (JPL) under a NASA contract. The primary focus is on efficiently locating geometric shapes, such as circles and cylinders, which have applications in various fields, including planetary science and engineering.
The extraction process is based on parametric equations that describe the geometric primitives in the image space. A key feature of this method is the use of an explicit error model, which enhances the robustness of the extraction against noise, missing data, and distracters. This is particularly important in real-world applications where image data can be imperfect.
The search strategy employed is hierarchical, allowing for a systematic exploration of the parameter space. This approach not only reduces the complexity of the extraction process but also enables effective pruning of irrelevant image features at each step. By constructing a hierarchy in both the parameter space and the image feature space, the method can efficiently narrow down potential candidates for geometric primitives without extensive computation.
The document highlights the advantages of this technique over traditional methods, such as the Hough transform, which typically require an initial estimate of the positions of the geometric primitives. The new algorithm does not necessitate such estimates, making it more versatile and applicable to a wider range of scenarios.
Applications of this method include detecting craters on planetary bodies and identifying unexploded ordnance in test ranges. The empirical evidence presented suggests that the proposed technique significantly improves the accuracy and efficiency of geometric primitive extraction compared to previous approaches.
In summary, this document outlines a robust and efficient algorithm for geometric primitive extraction from image data, emphasizing its practical applications and advantages over existing methods. The combination of a hierarchical search strategy and an explicit error model positions this technique as a valuable tool for various image analysis tasks, paving the way for advancements in fields that rely on accurate geometric shape detection.
