SYSTEM AND METHOD FOR COMPUTING MINIMUM DISTANCES BETWEEN TWO POINT CLOUDS

• US 20090063105A1
• Filed: 03/26/2008
• Published: 03/05/2009
• Est. Priority Date: 08/29/2007
• Status: Active Grant

• Current Assignee: Hong Fu Jin Precision Industry (Shenzhen) Co., Ltd. (Hon Hai Precision Industry Co., Ltd.), Hon Hai Precision Industry Co., Ltd.
• Original Assignee: Hong Fu Jin Precision Industry (Shenzhen) Co., Ltd. (Hon Hai Precision Industry Co., Ltd.), Hon Hai Precision Industry Co., Ltd.
• Inventors: HUANG, HUA, CHANG, CHIH-KUANG, WU, XIN-YUAN
• Granted Patent: US 7,933,749 B2
• Time in Patent Office: Days
• US Class Current: 703/1
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/30108 Industrial image inspection
• CPC Class Codes: G06T 7/001 using an image reference approach
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A method for computing minimum distances between two point clouds is provided. The method includes: (a) acquiring a first point cloud and a second point cloud; (b) establishing a topological structure for the second point cloud to make points of the second point cloud confined in a plurality of related cubical grids; (c) selecting a point from the first point cloud; (d) searching one or more cubical grids from the related cubical grids according to the topological structure and computing a distance between the selected point and each of points which belong to the second point cloud and in the searched cubical grids to obtain a closest point from the second point cloud, which has a shortest distance to the selected point; (e) repeating steps from (c) to (d) until all the points in the first point cloud have been selected. A related system is also provided.

Claims

1. A computer-enabled method for computing minimum distances between two point clouds, the method comprising steps of:

(a) acquiring a first point cloud and a second point cloud;

(b) establishing a topological structure for the second point cloud to make points of the second point cloud confined in a plurality of related cubical grids;

(c) selecting a maiden point from the first point cloud;

(d) searching one or more cubical grids from the related cubical grids according to the topological structure, and computing a distance between the selected point and each of points which belong to the second point cloud and in the searched cubical grids to obtain a closest point from the second point cloud, which has a shortest distance to the selected point, wherein the shortest distance is one of the minimum distances between the two point cloud;

(e) repeating steps from (c) to (d) until all the points in the first point cloud have been selected.

2. The method as described in claim 1, wherein the step (b) comprises steps of:

(b1) identifying an outermost point on each surface edge of the second point cloud by analyzing coordinates values of the points in the second point cloud;

(b2) creating a cubical figure that can confine the second point cloud according to the outmost points;

(b3) deriving a length, a width and a height of the cubical figure;

(b4) dividing the cubical figure into the plurality of cubical grids according to the length, the width, and the height of the cubical figure and an axes interval “

step”

preconfigured by a user; and

(b5) configuring serial numbers for the cubical grids to identify the cubical grids.

3. The method as described in claim 2, wherein the step (d) comprises:

(d1) computing a distance “

D”

from the selected point perpendicular to a plane of a closest side-surface of the cubical figure;

(d2) creating a measuring cube having a center of the selected point, and with a length of 2*(D+n*step), wherein n=n++, making the measuring cube cross with the cubical figure to form an intersection area, wherein cubical grids of the intersection area is the searched cubical grids;

(d3) computing distances between the selected point and points which belong to the second point cloud and in the searched cubical grids, to obtain a closest point which has a shortest distance “

d”

to the selected point;

(d4) judging that whether d>

(D+n*step) or not;

(d5) ascertaining that the distance “

d”

is the minimum distance if d≦

(D+n*Step); and

(d6) executing step (d2) to step (d5) if d>

(D+n*step).

4. A computerized method for computing minimum distances between a point cloud and a curved surface, the method comprising:

(a) acquiring a first point cloud and a curved surface;

(b) constructing a mesh of triangular facets based on the curved surface;

(c) gathering vertexes of triangles of the mesh of triangular facets to form a second point cloud;

(d) establishing a topological structure for the second point cloud to make points of the second point cloud confined in a plurality of related cubical grids;

(e) selecting a maiden point from the first point cloud;

(f) searching one or more cubical grids from the related cubical grids according to the topological structure, and computing a distance between the selected point and each of points which belong to the second point cloud and in the searched cubical grids to obtain a closest point “

p”

from the second point cloud, which has a shortest distance to the selected point;

(g) computing distances between the selected point and triangles whose vertex is the point “

p”

to obtain a shortest distance, wherein the shortest distance is one of the minimum distances between the point cloud and the curved surface; and

repeating step (e) to step (g) until all the points in the first point cloud have been selected.

5. The method as described in claim 4, wherein the step (d) comprises steps of:

(d1) identifying an outermost point on each surface edge of the second point cloud by analyzing coordinates values of the points in the second point cloud;

(d2) creating a cubical figure that can confine the second point cloud according to the outmost points;

(d3) deriving a length, a width and a height of the cubical figure; and

(d4) dividing the cubical figure into the plurality of cubical grids according to the length, the width, and the height of the cubical figure and an axes interval “

step”

preconfigured by a user

(d5) configuring serial numbers for the cubical grids to identify the cubical grids.

6. The method as described in claim 5, wherein the step (f) comprises:

(f1) computing a distance “

D”

from the selected point perpendicular to a plane of a closest side-surface of the cubical figure;

(f2) creating a measuring cube having a center of the selected point, and with a length of 2*(D+n*step), wherein n=n++, making the measuring cube cross with the cubical figure to form an intersection area, wherein cubical grids of the intersection is the searched cubical grids;

(f3) computing distances between the selected point and points which belong to the second point cloud and in the searched cubical grids, to obtain the closest point “

p”

which has a shortest distance “

d”

to the selected point;

(f4) judging that whether d>

(D+n*step) or not;

(f5) ascertaining that the distance “

d”

is the minimum distance if d≦

(D+n*Step); and

(f6) executing step (d2) to step (d5) if d>

(D+n*step).

7. A computerized method for computing a minimum distance between two curved surfaces, the method comprising:

(a) acquiring two curved surfaces;

(b) constructing two meshes of triangular facets based on the two curved surfaces respectively;

(c) gathering center points of triangles in one mesh of triangular facets to form a first point cloud, and gathering vertexes of triangles in other mesh of triangular facets to form a second point cloud;

(d) establishing a topological structure for the second point cloud to make points of the second point cloud confined in a plurality of related cubical grids;

(e) selecting a maiden point “

p₀”

from the first point cloud;

(f) searching one or more cubical grids from the related cubical grids according to the topological structure, and obtaining a point “

p”

from the second point cloud, which has the shortest distance to the point “

p₀”

by computing a distance between the point “

p₀” and

each of points which belong to the second point cloud and in the searched cubical grids;

(g) computing distances between the point “

p₀” and

triangles whose vertex is point “

p”

to obtain a triangle “

a”

which has a shortest distance to the point “

p₀”

;

(h) computing a distances “

d_n”

between the triangle “

a” and

the triangle whose center point is “

p₀”

;

repeating steps from (e) to (i) for computing a plurality of distances “

d_n”

until all the points in the first point cloud have been selected; and

(j) computing an average distance of the distances “

d_n”

, wherein the average distance is the minimum distance between the two curved surfaces.

8. The method as described in claim 7, wherein the step (d) comprises steps of:

(d1) identifying an outermost point on each surface edge of the second point cloud by analyzing coordinates values of the points in the second point cloud;

(d2) creating a cubical figure that can confine the second point cloud according to the outmost points;

(d3) deriving a length, a width and a height of the cubical figure; and

(d4) dividing the cubical figure into the plurality of cubical grids according to the length, the width, and the height of the cubical figure and an axes interval “

step”

preconfigured by a user

(d5) configuring serial numbers for the cubical grids to identify the cubical grids.

9. The method as described in claim 8, wherein the step (f) comprises:

(f1) computing a distance “

D”

from the selected point perpendicular to a plane of a closest side-surface of the cubical figure;

(f2) creating a measuring cube having a center of the selected point, and with a length of 2*(D+n*step), wherein n=n++, making the measuring cube cross with the cubical figure to form an intersection area, wherein cubical grids of the intersection area is the searched cubical grids;

(f3) computing distances between the selected point and points which belong to the second point cloud and in the searched cubical grids, to obtain the closest point “

p”

which has a shortest distance “

d”

to the selected point;

(f4) judging that whether d>

(D+n*step) or not;

(f5) ascertaining that the distance “

d”

is the minimum distance if d≦

(D+n*Step); and

(f6) executing step (d2) to step (d5) if d>

(D+n*step).