Estimation of surface geometry from relative range images

• US 5,617,491 A
• Filed: 05/16/1995
• Issued: 04/01/1997
• Est. Priority Date: 11/09/1993
• Status: Expired due to Fees

• Current Assignee: National Research Council Canada
• Original Assignee: National Research Council Canada
• Inventors: Roth, Gerhard
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/442,356
• Time in Patent Office: 686 Days
• Field of Search: 382/100, 382/108, 382/173, 382/203, 382/206, 382/285, 382/286, 364/578, 395/120, 395/121, 395/125, 395/141, 395/142
• US Class Current: 382/285
• CPC Class Codes: G06T 17/30 Polynomial surface description
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

A semi-automatic method is provided for finding an equation for a geometric surface patch that closely approximates a geometric surface within a digitized scene. By finding equations for patches within a scene, equations representing the entire scene can be found by stepwise sequential processing or alternatively by a system capable of parallel processing. Initially an operator using a mouse or pointing device selects a region from the digitized scene, and then selects one of a plurality of geometric surface types to represent a predominant geometric surface covered by the region. The process is based on randomly choosing the minimal number of data points from the selected region. Based on this information an equation of a surface on which the randomly selected points lie is determined. The process is repeated a predetermined number of times and the equation of the surface with the maximum number of associated data points is selected.

Claims

1. A method of finding a geometric surface patch represented by an equation, the surface patch closely approximating a geometric surface within a digitized scene, the scene comprising a plurality of surface patches represented by a plurality of data points, the method comprising the steps of:

a) digitizing the scene by sensing relative range information about a plurality of points observed in a scene using a rangefinding sensor;

b) inputting the sensed relative range information into a computer having a random access memory;

c) storing the digitized scene in the random access memory, the digitized scene comprising a plurality of data points;

d) using the computer to select a region from the digitized scene consisting of a set of points in three dimensions stored in the random access memory;

e) selecting one of a plurality of geometric surface types from a library of geometric surface types to represent a predominant geometric surface covered by the region;

f) determining a minimal number of data points required to define the selected surface type;

g) selecting the minimal number of data points by randomly choosing the data points from the selected region;

h) using the computer to compute from the surface type and the selected randomly chosen minimal number of data points, an equation of a surface patch on which the randomly selected points lie;

i) counting the number of data points in the selected region that are within a predetermined distance from the geometric surface patch defined by the equation; and

,

j) repeating steps (g) to (i) a predetermined number of times, and selecting the surface patch with the maximum number of counted data points.

2. A method as defined in claim 1, wherein the selected region is larger than and at least completely covers the surface patch it approximates.

3. A method as defined in claim 2, wherein the predetermined distance is a tolerance in the form of a fixed band around the geometric surface being approximated.

4. A method of finding a plurality of geometric surface patches closely approximating a geometric surface within a digitized scene, the scene comprising a plurality of surface patches represented by a plurality of data points stored within a random access memory, each surface patch represented by an equation, the method comprising the steps of:

a) digitizing the scene using a rangefinding sensor by sensing relative range information about a plurality of points observed in a scene;

b) storing the digitized scene in the random access memory, the digitized scene comprising a plurality of data points;

c) using a computer pointing device to select a region from the digitized scene consisting of a set of points in three dimensions stored in the random access memory;

d) having an operator choose one of a plurality of geometric surface types from a library of geometric surface types to represent a predominant geometric surface covered by the region;

e) determining a minimal number of data points required to define the selected surface type;

f) selecting the minimal number of data points by randomly choosing the data points from the selected region;

g) computing from the surface type and the selected randomly chosen minimal number of data points, an equation of a surface patch on which the randomly selected points lie;

h) counting the number of data points in the selected region that are within a predetermined distance from the geometric surface patch defined by the equation;

i) repeating steps (f) to (h) a predetermined number of times, and selecting the surface patch with the maximum number of counted data points; and

,

j) repeating steps (c) to (i) a plurality of times to acquire a plurality of selected surface patches.

5. A method as defined in claim 4, further comprising the step of providing the selected surface patches in the form of their defining equations to a modeling system for building a model of the geometric surface.