IRIS-96-345

Inference of Multiple Curves and Surfaces from Sparse Data

Gideon Guy

February 1996

We address the problem of acquiring high-level descriptions from sparse and noisy input data in 2-D and in 3-D. We claim that a local process cannot always capture meaningful structure among input data points, and more global constraints need to be imposed. Our system employs a global voting scheme that makes use of perceptual grouping constraints. These constraints encode properties such as smoothness, co-curvilinearity, proximity, and curvature optimization. The voting phase generates a dense space which lends itself to easy extraction of high-level primitives. These include junctions and edges in 2-D, and 3-D junctions, space curves and surfaces in 3-D.The scheme is non-iterative, parameter-free, can handle multiple objects, each with any size genus, and does not require an initial guess. Moreover, it can handle large amounts of noise. The result is in the form of dense saliency maps for curves nad junctions (in 2-D), and surfaces, intersections between surfaces, and 3-D junctions (in 3-D). These saliency maps are then used to guide a `marching' process to generate a high-level description. In the 2-D case, the description is in terms of connected curves, and junctions, while in the 3-D case it consists of polygonal meshes, polygonal space curves, and 3-D junctions. The scheme is non-iterative, parameter-free, can handle multiple objects, each with any size genus, and does not require an initial guess. Moreover, it can handle large amounts of noise, both in the from of erroneous input primitives, and in the localization accuracy of valid input samples. \\ \\