Three-dimensional shape data recording/display method and device, and three-dimensional shape measuring method and device

• US 8,300,048 B2
• Filed: 12/15/2006
• Issued: 10/30/2012
• Est. Priority Date: 12/16/2005
• Status: Active Grant

• Current Assignee: IHI Corporation
• Original Assignee: IHI Corporation
• Inventors: Hayashi, Toshihiro, Kawano, Yukihiro, Terada, Hideo
• Primary Examiner(s): Chauhan, Ulka
• Assistant Examiner(s): NGUYEN, ANH TUAN V
• Application Number:
  US12/096,871
• Publication Number:
  US 20090184961A1
• Time in Patent Office: 2,146 Days
• Field of Search: 345/419, 345/653, 345/664, 345/679
• US Class Current: 345/424
• CPC Class Codes: G01B 11/24 for measuring contours or curvatures
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 5/50 using two or more images, e.g. averaging or subtraction

Abstract

A three-dimensional shape data recording/display method including: a data inputting step S1 for inputting into a computer coordinate values on a three-dimensional shape; a model structuring step S3 for structuring an environment model for partitioning a spatial region into a plurality of voxels made from rectangular solids, of which the boundary surfaces are mutually perpendicular, and stores the positions of the individual voxels; a matching step S4 for setting and recording a representative point and an error distribution within the voxel corresponding to the coordinate value; a model updating step S5 for updating the environment model; and an outputting step S6 for outputting, to an outputting device, at least one of the voxel position, representative point, and error distribution.

Claims

1. A three-dimensional shape data recording/displaying method for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape, the method comprising the steps of:

(a) inputting, into a computer, coordinate values on a three-dimensional shape in a data inputting step;

(b) structuring, in a model structuring step, an environment model that partitions a spatial region, in which the three-dimensional shape exists into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and storing positions of individual voxels;

(c) setting and recording, in a matching step, a representative point and an error distribution within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the representative point corresponds to a measured point obtained by using a range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction, wherein the matching step further includes setting and recording a plurality of representative points in the plurality of voxels, respectively, and a plurality of error distributions of the plurality of representative points are set and recorded in the plurality of voxels, respectively, wherein the plurality of representative points include the representative point, and the plurality of voxels include the first voxel, and the plurality of error distributions include the error distribution; and

(d) outputting, to an outputting device, a voxel position, the representative point, and the error distribution in an outputting step.

2. The three-dimensional shape data recording/displaying method as set forth in claim 1, further comprising, in the model structuring step, the steps of

setting a second voxel to a size corresponding to a minimum required resolution;

and

when a plurality of measured points exist within a single voxel, further partitioning hierarchically the second voxel into a plurality of third voxels so that only a single measured point exists within a single voxel.

3. The three-dimensional shape data recording/displaying method as set forth in claim 1, further comprising the steps of:

(e) updating, in a model updating step, the environment model after the matching step;

wherein the model updating step further comprises the steps of

i. retrieving a second voxel corresponding to a second coordinate value of a newly inputted measured point; and

ii. deciding that no object exists between an origin and a measuring point, and resetting or eliminating representative points and error distributions within those voxels positioned therebetween.

4. The three-dimensional shape data recording/displaying method as set forth in claim 1, further comprising the step of:

(e) updating, in a model updating step, the environment model after the matching step, wherein the model updating step further comprises the steps of

i. retrieving a second voxel corresponding to a second coordinate value of a newly inputted measured point; and

ii. when there is no representative point within the second voxel, setting the second coordinate value and the error distribution as a third coordinate value and error distribution of the representative point.

5. The three-dimensional shape data recording/displaying method as set forth in claim 1, further comprising the step of:

(e) updating, in a model updating step, the environment model after the matching step, wherein the model updating step further comprises the steps of

i. retrieving a second voxel corresponding to a second coordinate value of a newly inputted measured point;

ii. when there is a representative point that has already been set within the second voxel, comparing a newly obtained error distribution and an error distribution already set within the second voxel;

when the error distributions are mutually overlapping, resetting a new error distribution and a new representative point from both error distributions; and

when error distributions are not mutually overlapping, further partitioning hierarchically the second voxel into a plurality of third voxels so that only a single representative point exists within a single voxel.

6. The three-dimensional shape data recording/displaying method as set forth in claim 5, further comprising the steps of:

comparing, in the model updating step, the newly obtained error distribution and the error distribution that has already been set within the second voxel;

when the error distributions are mutually overlapping, and a new representative point has moved into another voxel as the result of resetting a new error distribution and a new representative point from both of the error distributions, in the case where there is no representative point in the another voxel, setting the new error distribution and the new representative point into the another voxel;

when there is a representative point that has already been set in the another voxel, then comparing the new error distribution and the error distribution that has already been set into the another voxel;

when the error distributions are mutually overlapping, then resetting a new error distribution and a new representative point from either both error distributions or from both error distributions and the representative point that has already been set within the second voxel and a newly entered measured point coordinate value; and

when the error distributions are not mutually overlapping, further partitioning a voxel hierarchically into a plurality of fourth voxels so that only a single representative point exists within a single voxel.

7. The three-dimensional shape data recording/displaying method as set forth in claim 1, wherein the first voxel holds a probability value in addition to the representative point and error distribution.

8. The three-dimensional shape data recording/displaying method as set forth in claim 1, further comprising, in the data inputting step, the steps of

i. sequentially obtaining coordinate values on the three-dimensional shape as range data with an arbitrary measuring position being an origin;

and

ii. using the range sensor while moving the origin.

9. The three-dimensional shape data recording/displaying method as set forth in claim 8, further comprising the step of:

when a position and an error distribution of the position are obtained for the range sensor, combining the error distribution of the position of the range sensor with an error distribution of measured data.

10. The three-dimensional shape data recording/displaying method as set forth in claim 1, further comprising, after the matching step, the step of

updating the environment model in a model updating step, wherein the model updating step comprises the steps of

i. obtaining and resetting a new representative point and error distribution through a Kalman filter from a second coordinate value and error distribution of a newly inputted measured point, and from the representative point and the error distribution that have already been set in the first voxel.

11. A three-dimensional shape data recording/displaying device for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape, wherein the three-dimensional shape data recording/displaying device comprises:

(a) a data inputting device operably connected to input, into a computer, coordinate values on a three-dimensional shape, wherein the data inputting device comprises a range sensor;

(b) a model structuring device operable to structure an environment model that partitions a spatial region, in which the three-dimensional shape exists, into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and the model structuring device stores positions of individual voxels;

(c) a matching device operable to set, and record, a representative point and an error distribution of the representative point, within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the matching device is operable to set and record a plurality of representative points in the plurality of voxels, respectively, and to set and record a plurality of error distributions of the plurality of representative points in the plurality of voxels, respectively, wherein the plurality of representative points include the representative point, and the plurality of voxels include the first voxel, and the plurality of error distributions include the error distribution; and

(d) a data transferring device operably connected to output, to an outputting device, a voxel position, the representative point, and the error distribution,

wherein the representative point corresponds to a measured point obtained by the range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction.

12. A three-dimensional shape measuring method for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape and for outputting three-dimensional shape data, wherein the method comprises the steps of:

(a) inputting, into a computer, coordinate values on a three-dimensional shape in a data inputting step;

(b) structuring, in a model structuring step, an environment model that partitions a spatial region, in which the three-dimensional shape exists, into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and storing positions of individual voxels;

(c) setting and recording, in a matching step, a representative point and an error distribution of the representative point, within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the representative point corresponds to a measured point obtained by using a range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction, wherein the matching step further includes setting and recording a plurality of representative points in the plurality of voxels, respectively, and a plurality of error distributions of the plurality of representative points are set and recorded in the plurality of voxels, respectively, wherein the plurality of representative points include the representative point, and the plurality of voxels include the first voxel, and the plurality of error distributions include the error distribution; and

(d) outputting, in an outputting step, to an outputting device at least one of the representative point, a voxel position, and the error distribution.

13. The three-dimensional shape measuring method as set forth in claim 12, further comprising, in the outputting step, the steps of outputting a position of the representative point of the first voxel to the outputting device as a three-dimensional shape measurement value;

and outputting an index indicating a reliability or accuracy of the three-dimensional shape measurement value to the outputting device based on a magnitude of the error distribution within the first voxel.

14. The three-dimensional shape measuring method as set forth in claim 12, wherein, in the outputting step, when a position of the representative point of the first voxel is outputted to the outputting device as a three-dimensional shape measurement value, when a magnitude of the error distribution within the first voxel is larger than a specific reference value, then a reliability or accuracy of the measurement value is regarded to be less than a specific reference, and the three-dimensional shape measurement value for the first voxel is not outputted to the outputting device.

15. The three-dimensional shape measuring method as set forth in claim 12, further comprising, in the data inputting step, the steps of sequentially obtaining coordinate values on the three-dimensional shape as range data with an arbitrary measuring position that is an origin, and using the range sensor while moving the origin.

16. The three-dimensional shape measuring method as set forth in claim 12, further comprising after the matching step, the steps of:

(e) updating the environment model in a model updating step, wherein the model updating step comprises retrieving a second voxel corresponding to a coordinate value of a newly inputted measured point; and

(f) when there is no representative point within the second voxel, setting the coordinate value and the error distribution as the representative point coordinate value and error distribution.

17. The three-dimensional shape measuring method as set forth in claim 12, further comprising, after the matching step, the steps of:

(e) updating the environment model in a model updating step, wherein the model updating step comprises retrieving a second voxel corresponding to a coordinate value of a newly inputted measured point;

(f) when there is a representative point that has already been set within the second voxel, comparing a newly obtained error distribution and the error distribution already set within the second voxel;

(g) when error distributions are mutually overlapping, resetting a new error distribution and a new representative point from both of the error distributions, or from both of the error distributions and the representative point already set within the second voxel and the coordinate values of the measured point newly inputted; and

(h) when error distributions are not mutually overlapping, further partitioning hierarchically the second voxel into a plurality of third voxels so that only a single representative point exists within a single voxel.

18. The three-dimensional shape measuring method as set forth in claim 12, further comprising, after the matching step, the steps of:

(e) updating the environment model in a model updating step, wherein the model updating step comprises the steps of

i. retrieving a second voxel corresponding to a coordinate value of a newly inputted measured point; and

ii. when at least one of the representative point and the error distribution within that second voxel is newly set, or reset, or the second voxel is further partitioned hierarchically into a plurality of third voxels, then, in the outputting step, outputting a position of a representative point of that second voxel to the outputting device as a three-dimensional shape measurement value.

19. The three-dimensional shape measuring method as set forth in claim 12, further comprising, in the outputting step, outputting, to the outputting device, as a three-dimensional shape measurement value, a position of a representative point for a second voxel in the environment model in a scope for which the position can be measured from a position of the range sensor.

20. A three-dimensional shape measuring device for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape and for outputting three-dimensional shape data, wherein the three-dimensional shape measuring device comprises:

(a) a data inputting device operably connected to input, into a computer, coordinate values on a three-dimensional shape, wherein the data inputting device comprises a range sensor;

(b) a model structuring device operable to structure an environment model that partitions a spatial region, in which the three-dimensional shape exists, into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and the model structuring device stores positions of individual voxels;

(c) a matching device operable to set and record a representative point and an error distribution of the representative point, within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the matching device is operable to set and record a plurality of representative points in the plurality of voxels, respectively and to set and record a plurality of error distributions of the plurality of representative points in the plurality of voxels, respectively, wherein the plurality of representative points include the representative point, and the plurality of voxels include the first voxel, and the plurality of error distributions include the error distribution; and

(d) a data transferring device operably connected to output, to an outputting device, at least one of the representative point, a voxel position, and the error distribution,

wherein the representative point corresponds to a measured point obtained by the range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction.

21. A three-dimensional shape data recording/displaying method for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape, wherein the method comprises the steps of:

(a) inputting, into a computer, coordinate values on a three-dimensional shape in a data inputting step;

(b) structuring, in a model structuring step, an environment model that partitions a spatial region, in which the three-dimensional shape exists, into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and storing positions of individual voxels;

(c) setting and recording, in a matching step, a representative point, and an error distribution of the representative point, within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the representative point corresponds to a measured point obtained by using a range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction, wherein the matching step further includes setting and recording a plurality of representative points in the plurality of voxels, respectively, and a plurality of error distributions of the plurality of representative points are set and recorded in the plurality of voxels, respectively, wherein the plurality of representative points include the representative point, and the plurality of voxels include the first voxel, and the plurality of error distributions include the error distribution; and

(d) outputting, in an outputting step, to an outputting device at least one of the representative point, a voxel position, and the error distribution.

22. A three-dimensional shape data recording/displaying method for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape, the method comprising the steps of:

(a) inputting, into a computer, coordinate values on a three-dimensional shape in a data inputting step;

(b) structuring, in a model structuring step, an environment model that partitions a spatial region, in which the three-dimensional shape exists into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and storing positions of individual voxels;

(c) setting and recording, in a matching step, a representative point and an error distribution within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the representative point corresponds to a measured point obtained by using a range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction;

(d) outputting, to an outputting device, a voxel position, the representative point, and the error distribution in an outputting step; and

(e) updating, in a model updating step, the environment model after the matching step;

wherein the model updating step further comprises the steps of

i. retrieving a second voxel corresponding to a second coordinate value of a newly inputted measured point; and

ii. deciding that no object exists between an origin and a measuring point, and resetting or eliminating representative points and error distributions within those voxels positioned therebetween.

23. A three-dimensional shape data recording/displaying method for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape, the method comprising the steps of:

(a) inputting, into a computer, coordinate values on a three-dimensional shape in a data inputting step;

(b) structuring, in a model structuring step, an environment model that partitions a spatial region, in which the three-dimensional shape exists into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and storing positions of individual voxels;

(c) setting and recording, in a matching step, a representative point and an error distribution within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the representative point corresponds to a measured point obtained by using a range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction;

(d) outputting, to an outputting device, a voxel position, the representative point, and the error distribution in an outputting step; and

(e) updating, in a model updating step, the environment model after the matching step, wherein the model updating step further comprises the steps of

i. retrieving a second voxel corresponding to a second coordinate value of a newly inputted measured point; and

ii. when there is no representative point within the second voxel, setting the second coordinate value and the error distribution as a third coordinate value and error distribution of the representative point.

24. A three-dimensional shape measuring method for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape and for outputting three-dimensional shape data, wherein the method comprises the steps of:

(a) inputting, into a computer, coordinate values on a three-dimensional shape in a data inputting step;

(b) structuring, in a model structuring step, an environment model that partitions a spatial region, in which the three-dimensional shape exists, into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and storing positions of individual voxels;

(c) setting and recording, in a matching step, a representative point and an error distribution of the representative point, within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the representative point corresponds to a measured point obtained by using a range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction; and

(d) outputting, in an outputting step, to an outputting device at least one of the representative point, a voxel position, and the error distribution;

(e) updating the environment model in a model updating step, wherein the model updating step comprises retrieving a second voxel corresponding to a coordinate value of a newly inputted measured point; and

(f) when there is no representative point within the second voxel, setting the coordinate value and the error distribution as the representative point coordinate value and error distribution,

wherein steps (e) and (f) occur after the matching step.

25. A three-dimensional shape measuring method for reproducing a three-dimensional shape from coordinate values of measured points on a three-dimensional shape and for outputting three-dimensional shape data, wherein the method comprises the steps of:

(a) inputting, into a computer, coordinate values on a three-dimensional shape in a data inputting step;

(b) structuring, in a model structuring step, an environment model that partitions a spatial region, in which the three-dimensional shape exists, into a plurality of voxels formed from rectangular solids, of which boundary surfaces are mutually perpendicular, and storing positions of individual voxels;

(c) setting and recording, in a matching step, a representative point and an error distribution of the representative point, within a first voxel corresponding to a first coordinate value, wherein the error distribution is an existence probability of the representative point, and the error distribution extends three dimensionally in the environment model, wherein the representative point corresponds to a measured point obtained by using a range sensor, and the error distribution is longer in a measuring direction of the range sensor than in a direction perpendicular to the measuring direction; and

(d) outputting, in an outputting step, to an outputting device at least one of the representative point, a voxel position, and the error distribution, and, in the outputting step, outputting to the outputting device, as a three-dimensional shape measurement value, a position of a representative point for a second voxel in the environment model in a scope for which the position can be measured from a position of the range sensor.