Estimation of surface geometry from relative range images

Claim 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.

Claim 2

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.

Claim 5

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.

Claim 6

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.