JP2002366934A - Method and apparatus for generating three-dimensional shape data and computer program - Google Patents

Abstract

(57) [Summary] [Problem] Even if there is a concave area or a part with low reflectance,
To accurately restore a three-dimensional shape with as little memory capacity as possible and in a short calculation time. A method of generating three-dimensional shape data of an object, wherein the first volume data is generated by converting a plurality of images of the object from different viewpoints into volume data using a silhouette method. 1
A second step of generating second volume data by converting three-dimensional data obtained by three-dimensional measurement on the object into volume data;
The method includes a third step of integrating the first volume data and the second volume data into one volume data.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a method and an apparatus for generating three-dimensional shape data, and a computer program.

[0002]

2. Description of the Related Art Conventionally, as one of methods for generating three-dimensional shape data of an object, a silhouette method (Shape From S
Ilhouette) is known.

In the silhouette method, a three-dimensional shape of an object is restored from a plurality of images obtained by photographing (or photographing) the object from different viewpoints. That is, in the silhouette method, based on images obtained by photographing the object from a plurality of line-of-sight methods, an object existence region reflecting the shape of the object as viewed from each line-of-sight direction is described as a set of voxels in a three-dimensional image space. Then, a set of voxels in the object existing area viewed from all directions is obtained as an object in the three-dimensional space.

[0004]

However, in the silhouette method, since the depressed portion or the depressed portion of the object does not appear as a silhouette image, the shape of such a depressed region cannot be restored.

On the other hand, as another method for restoring the three-dimensional shape of an object, there is a method using a range sensor (three-dimensional measuring device) for measuring an object in a non-contact manner by a light cutting method or the like.
However, when the range sensor is used, data is lost when the reflectance of the surface of the object is extremely low, and there is a problem that the three-dimensional shape of that part cannot be restored.

SUMMARY OF THE INVENTION The present invention has been made in view of the above-mentioned problem, and even when there is a concave area or a part having a low reflectance, a three-dimensional shape can be accurately restored with as little memory capacity as possible and in a short calculation time. The purpose is to:

[0007]

According to one aspect of the present invention, there is provided a method for generating three-dimensional shape data of an object, the method comprising using a silhouette method from a plurality of images of the object with different viewpoints. A first step of generating first volume data by converting to volume data, and a second step of generating second volume data by converting three-dimensional data obtained by three-dimensional measurement of the object to volume data. And a third step of integrating the first volume data and the second volume data into one volume data.

Preferably, in the first step, when converting into volume data using the silhouette method, (a) at each discrete coordinate position in the coordinate system expressing the volume, the contour of the image of the object is Obtaining a value corresponding to a distance to a boundary of a viewing volume determined by a viewpoint of the image; and (b) for each coordinate position, a distance from an object surface based on a plurality of values obtained for a plurality of images of the object. Is determined, and a step of holding the value in association with each coordinate position is executed.

In the second step, when the three-dimensional data is converted into volume data, (a) at each discrete coordinate position in the coordinate system expressing the volume, it is represented by the three-dimensional data of the object. (B) obtaining a value corresponding to the distance to the object surface, and (b) storing the obtained value in association with each coordinate position.

The three-dimensional shape of the object is restored by inversely transforming the generated volume data. According to the present invention, a high-precision three-dimensional model with no omissions is generated by compensating for each disadvantage caused by the difference in the method of generating three-dimensional shape data.

[0011]

FIG. 1 is a block diagram of a three-dimensional data generating apparatus 1 according to the present embodiment. In FIG. 1, 3
The dimensional data generation device 1 includes a device main body 10, a magnetic disk device 11, a medium drive device 12, and a display device 1.
3, a keyboard 14, a mouse 15, and the like.

The apparatus main body 10 includes a CPU, a RAM, and an RO.
M, a video RAM, an input / output port, and various controllers. Various functions described below are realized by the CPU executing programs stored in the RAM, the ROM, and the like.

The magnetic disk drive 11 has an OS (Operat
Modeling program PR for generating the 3D model ML, other programs, input 3D data (3D shape data) DT, image (2D image data) FT, volume data DV, 3D model ML, other data, and the like. These programs and data are loaded into the RAM of the apparatus body 10 at appropriate times.

The modeling program PR includes programs for initialization processing, attribute value setting processing, attribute value determination processing, boundary determination processing, division processing, integration processing, inverse transformation processing, mapping processing, and other processing. Is included.

The medium drive device 12 is a CD-ROM
(CD), floppy disk FD, magneto-optical disk,
It accesses the semiconductor memory HM such as CompactFlash (registered trademark) and other recording media to read and write data or programs. An appropriate drive device is used depending on the type of the recording medium. The above-described modeling program PR can be installed from these recording media. 3D data DT and image FT
Can be input via a recording medium.

The display surface HG of the display device 13 includes:
Various data described above, three-dimensional data DT, image F
T, the image of the processing process by the modeling program PR,
The generated three-dimensional model ML and other data or images are displayed.

The keyboard 14 and the mouse 15 are used by the user to make various designations for the image FT and the three-dimensional data DT displayed on the display device 13 and input various data to the device body 10. Or to give instructions.

Although not shown, the apparatus main body 10 can be connected to a digital camera for photographing an object as an object from various viewpoints or photographing from various viewpoints and inputting an image FT. is there. By extracting the outline of the object from the image FT, the silhouette image F
S is generated. It is possible to generate three-dimensional data DT by the silhouette method based on the silhouette image FS.

Further, based on two images having parallax, 3
It is also possible to generate three-dimensional data DT by performing dimensional reconstruction. Further, a three-dimensional input device (three-dimensional measuring device) for photographing an object and inputting three-dimensional data DT thereof can also be connected to the device main body 10. Such a three-dimensional input device measures non-contact three-dimensional data DT of an object by, for example, a light section method. Alternatively, instead of the three-dimensional data DT, data serving as a source for generating the three-dimensional data DT may be output from the three-dimensional input device, and the three-dimensional data DT may be obtained by calculation by the device body 10.

The three-dimensional data D obtained as described above
T or the data in the process of generating the three-dimensional data DT expresses the three-dimensional shape of the object in a boundary expression format. In the present embodiment, volume data (Volume Data) D in which each voxel (Voxel) has a multi-valued attribute value d is obtained by converting the three-dimensional shape of the object represented in the boundary representation format into a voxel (Voxel).
Convert to V A voxel is a small cube composed of a unit cell by decomposing a three-dimensional space into a small unit cell.

Also, a plurality of volume data DV converted from a plurality of three-dimensional shapes having different generation methods are integrated into one volume data DV. The final volume data DV is again converted back to the shape expression in the boundary expression format. At that time, for example, a known zero isosurface extraction method or the like can be used. That is, a point corresponding to a zero isosurface on a side connecting adjacent vertices (lattice points) is calculated, and a triangular polygon in which those points are connected is generated, whereby the polygon mesh can be converted.

A texture image is also pasted on the three-dimensional shape obtained by the inverse transformation. Thus, the three-dimensional model ML is generated. The three-dimensional data generation device 1 can be configured using a personal computer, a workstation, or the like. The programs and data described above can be received and acquired via the network NW.

FIG. 2 is a flowchart showing the flow of the process of generating the three-dimensional model ML by the three-dimensional data generating device 1. In FIG. 2, a volume (volume data DV) of an appropriate size is prepared and initialized (#
1). For example, a volume having a size of about 50 × 50 × 50 voxels or about 100 × 100 × 100 voxels is used. The volume need not be a cube. Also, the coordinates and orientation of the center of the voxel in the coordinate system are set.

The volume can store two types of multivalued data as attribute values d at each vertex of the voxel. That is, for each vertex, two attribute values ds, dr
Is provided. This may be that there are two volumes that can store multivalued data as attribute values at each vertex of the voxel. In this case, one can be described as a first volume and the other as a second volume.

In this specification, "volume"
May be described as “volume data”.
In this case, the “volume data” is a three-dimensional area that is configured to have a predetermined shape by voxels and that can store data at each vertex of the voxel.

The vertices of voxels are common to adjacent voxels. Therefore, the vertices not at the peripheral edge are the vertices of eight voxels. The vertices coincide with the grid points of the volume data. Therefore, the “vertex” may be described as a “lattice point”.

Now, returning to FIG. 2, a conversion process is performed using the silhouette image to generate first volume data DV (# 2). The conversion processing is performed using the range data, and the second volume data DV is generated (#
3). Note that the range data is three-dimensional shape data obtained by measuring an object using a three-dimensional measuring device called a range finder or the like. In addition, three-dimensional shape data reconstructed from a plurality of images having parallax by a stereo method is also included in the range data referred to herein.

The first and second volume data DV are integrated (# 4). The integrated volume data DV is inversely converted into a boundary representation format shape representation (# 5). Texture mapping is performed as needed (# 6).

In the following, the process of converting to volume data DV and the process of integrating a plurality of volume data DV will be described in detail. First, the conversion process will be described. [Conversion Processing According to First Embodiment] FIG. 3 is a flowchart showing the conversion processing by the three-dimensional data generating apparatus 1, and FIG.
9 is a flowchart showing a modification of the conversion process. The conversion processing shown in these flowcharts includes range data,
It is applied to conversion processing using other three-dimensional shape data and a silhouette image.

In FIG. 3, first, three-dimensional data DT representing a three-dimensional shape of an object is prepared. Alternatively, instead of the three-dimensional data DT, a plurality of images FT from which the three-dimensional data DT is generated are prepared. And three-dimensional data D
T and volume data DV are aligned (# 11). Normally, the size and position of the three-dimensional data DT are determined so that the three-dimensional data DT just fits in the volume data DV.

For each vertex of the voxel constituting the volume, a value corresponding to the distance from each vertex to the boundary expressing the three-dimensional shape, that is, the distance to the surface of the object is obtained (# 12). The obtained value is held as the attribute value of each vertex (# 13).

In this manner, the vertices of each voxel, that is, the grid points, store the multi-valued attribute values, and the volume data D composed of the grid point group having the multi-valued attribute values.
V is generated.

In FIG. 4, voxels crossing the surface of the object are extracted (# 22). Such a voxel may be described as a “boundary voxel”. A value corresponding to the distance from the vertex to the surface of the object is obtained for the boundary voxel (# 23). The obtained value is held as the attribute value of each vertex in the same manner as above (# 24).

When a certain vertex is a common vertex of a boundary voxel and another voxel, the vertex is treated as a vertex of the boundary voxel. [Conversion Processing According to Second Embodiment] The conversion processing will be described in more detail based on the second embodiment. The second and third embodiments are mainly applied to conversion processing using a silhouette image.

FIG. 5 is a flowchart showing a conversion process according to the second embodiment, FIG. 6 is a flowchart showing a subroutine of an attribute value setting process in step # 34 of FIG. 5, and FIG. 7 shows a process of converting a silhouette image FS into volume data DV. FIG. 8 is a view for explaining a projected state, FIG. 8 is an enlarged view of a part of the silhouette image FS shown in FIG. 7, FIG. 9 is a view showing a state where the volume data DV is cut along a horizontal plane, and FIG. FIG. 11 is an enlarged view of a voxel, and FIG. 11 is a diagram showing an example of a volume table TLs storing volume data DV.

In FIG. 5, first, for the set volume data DV, initial values are set to all grid points TP. Thus, the volume data DV is initialized (# 31). As an initial value of the lattice point TP, for example, “plus infinity” meaning inside the object is set. In this case, “plus infinity” is the first in the present invention.
Is a specific value of. When initialization is completed, FIG.
All the volume data DV indicated by 0 are initial values.

Next, one image FT is inputted (# 3).
2). At this time, the camera parameters at the time of capturing the image FT are also input. Camera parameters include a camera internal matrix such as a focal length and an external matrix such as a viewpoint position. A projection matrix including these may be input. The viewpoint position and the projection direction when projecting the image FT on the volume data DV are determined based on the camera parameters.

When the image FT is input in step # 32, the image FT is stored in the magnetic disk device 11.
The image FT stored in the magnetic disk device 11 is automatically read into the RAM by a program, and the subsequent processing is added. However, the input of the image in step # 32 is performed by setting the image FT stored in the magnetic disk device 11 to R
It may be used to mean reading on AM. In that case, a large number of images FT may be stored in the magnetic disk device 11 in advance, and one image FT designated in step # 32 may be read into the RAM. Further, the input of an image can be used to mean that one image FT to be processed is designated from among a large number of images FT stored in the magnetic disk device 11.

The outline of the object, which is the subject, is cut out from the input image FT, so that the silhouette image F
S is generated (# 33). Since the outline of the silhouette image FS only needs to be known, a monochrome image is sufficient.
The generation of the silhouette image can be performed automatically or manually by a known method.

Volume data DV, that is, voxel V
The attribute value of each vertex (grid point) TP of X is obtained and set (# 34). The attribute value is obtained as a signed distance between each vertex TP and the surface of the object. That is, for example, as shown in FIGS. 7 and 8, the distance Ls from the boundary SF of the view volume VV determined by the contour (obstructed contour) by the silhouette image FS and the viewpoint VP to the vertex TP is set to the inside of the view volume VV. The direction toward is determined as + (plus). Details will be described later.

If there is an image FT that needs to be processed, the next one image is input (Yes in # 35, # 3)
2). This is repeated until the processing for all necessary images FT is completed (# 35). Even when the processing for all the scheduled images FT has been completed, the processing of steps # 32 to # 34 can be performed by adding the image FT as necessary.

It is also possible to input a silhouette image FS instead of inputting the image FT in step # 32. In that case, step # 33 is unnecessary.
In FIG. 6, when setting the attribute value, first, attention is paid to one grid point TP constituting the volume (# 41). Check the attribute value of the grid point TP of interest (# 4
2). If the attribute value is "minus infinity", the process proceeds to step # 45. That is, that the attribute value is “minus infinity” means that the lattice point TP is outside the object. Since the grid points TP outside the object are cut off, there is no need to calculate any more attribute values. In this case, "minus infinity" is the second specific value in the present invention.

When the first image is processed, since "plus infinity" is set as an initial value for all the grid points, the process proceeds to step # 43. When processing the second and subsequent images, processing of the previous image
One of “plus infinity”, “minus infinity”, or “signed distance ds” described later is set as an attribute value, and is other than “minus infinity”, that is, “plus infinity” or “signed In the case of "distance ds", the flow proceeds to step # 43.

If the attribute value is not "minus infinity",
In step # 43, a signed distance ds is calculated. There are various methods for calculating the signed distance. Next, the first to third methods will be described. (First method) A grid point TP of interest and a grid point adjacent to the grid point TP (that is, a vertex of the same voxel VX) are projected onto the image FT toward the viewpoint VP. . When the projected points are connected to each other on the image FT and the side formed thereby intersects the contour (shielding contour), the signed distance is calculated.

That is, as shown in FIG. 7, when a certain voxel VX is on the boundary SF of the visual volume VV, the voxel VX is the boundary voxel VXs. A signed distance is calculated for the vertex TP of the boundary voxel VXs.

In FIG. 9, the voxel VX that intersects the boundary SF of the visual volume VV is shown as a boundary voxel VXs at an intermediate density. In FIG. 10, the boundary voxel V
The distance from each vertex TP of Xs to the boundary SF of the visual volume VV is obtained. The calculated distance, or the numerical value corresponding to it,
It is shown as the attribute value of each vertex TP.

The unit or scale of the distance may be set appropriately. The maximum value of the distance is the length of the diagonal line of the voxel VX. Therefore, the distance may be normalized based on the length of the diagonal line. Further, for the vertex TP inside the visual volume VV, the sign of the distance is set to a positive value as it is, and for the vertex TP outside, the distance is set to a negative value by adding minus.

For example, when 8-bit data is used as the attribute value, the most significant bit is a sign bit, and the lower 7 bits indicate the distance. Thereby, -127 to +1
Since the value of 28 can be expressed, -127 is made to correspond to "minus infinity" indicating the outside, and +128 is made
Corresponding to "plus infinity" indicating the interior, -126 to +
127 correspond to the signed distance. 1 as the attribute value
Data of 2 bits, 16 bits, and other bits can be used.

Therefore, when the lattice point TP is on the boundary SF of the visual volume VV, the attribute value is zero. The attribute value increases as the lattice point TP goes inside the viewing volume VV, and the attribute value decreases as it goes outside.

If the side does not intersect with the shielding contour, that is, if it is not the boundary voxel VXs, the grid point TP
Exists inside or outside the visual volume VV. If it is outside, the grid point TP is a point to be cut out, and the attribute value is set to “minus infinity”. If it is inside, the attribute value is left as “plus infinity”. (Second method) The grid point TP of interest is projected on the image FT toward the viewpoint VP. It is checked whether or not there is an occluded contour in an area inside a circle having a fixed radius from the center with the projected point as the center. If there is an occluded contour, the signed distance is calculated. If no shielding contour exists in the area and the grid point TP is outside the viewing volume VV, the attribute value is set to “minus infinity”. . (Third method) Sampling contours are sampled at regular intervals,
A straight line connecting the sampling point and the viewpoint VP is obtained. These straight lines are lines of sight passing through the shielding contour. Using the line of sight instead of the boundary SF of the visual volume VV, a signed distance is calculated three-dimensionally. That is, for the vertex TP of the boundary voxel VXs, the distance from the vertex TP to the line of sight is calculated. When the grid point TP of interest is outside the visual volume VV, the attribute value is set to “minus infinity”.

Then, in step # 44, an attribute value is set to the grid point TP. When setting an attribute value, only a value smaller than the already set attribute value is set. If a new value larger than the already set attribute value is obtained, the new attribute value is ignored.

That is, assuming that "minus infinity" is newly obtained as an attribute value, the attribute value becomes "minus infinity" whatever the attribute value set previously.
In this way, the outside of the object is cut out.

When the attribute value is a signed distance for both the new and old attributes, an average value thereof may be obtained and used as a new attribute value d. It is checked whether the processing has been performed for all the grid points TP (# 45). If there is a lattice point TP that has not been processed yet, step # 4
Repeat from 1 onwards. When the processing for all the lattice points TP is completed, the process returns. As a result, FIG.
The volume table TLs as shown in FIG.

According to the second embodiment, one image FT
Since the processing is performed every time, when the processing of the image is completed, the image can be deleted, and the memory capacity to be used can be reduced accordingly. [Conversion Processing According to Third Embodiment] In the conversion processing according to the second embodiment, the conversion processing is advanced by adding images FT. First, a plurality of images FT are collectively input (read). ), It is also possible to perform processing. Next, an example thereof will be described as a third embodiment.

FIG. 12 is a flowchart showing the conversion processing of the third embodiment, and FIG. 13 is a flowchart showing a subroutine of the attribute value setting processing in step # 54 of FIG.

In FIG. 12, step # 51 is the same as step # 31 in FIG. In step # 52, all the images FT taken of the object are input at one time. At this time, camera parameters at the time of capturing each image FT are input. For each image FT, a silhouette image FS is generated as in step # 33 (# 53). Then, attribute values are set (# 5).
4).

In FIG. 13, when setting an attribute value, first, as in step # 41, attention is paid to one grid point TP (# 61). The grid point TP of interest is the viewing volume V
It is checked at what position with respect to V (# 62).

That is, when the lattice point TP is present near the boundary SF of the visual volume VV, the attribute value is temporarily set to “BORDER”.
The attribute value is set to “INSIDE” when it exists inside the visual volume VV, and the attribute value is set to “OUTSIDE” when it exists outside the subject. Attribute value "INSIDE""OUTSIDE
"Are the first specific value and the second specific value in the present invention. Next, two check methods will be described. (First method) A grid point TP of interest and a grid point adjacent thereto are projected on all the images FT. On each projected image FT, when two projected points are connected on each image FT, it is determined whether or not a side formed thereby intersects a contour (shielding contour). 1
If at least one intersecting image FT exists, it is determined that the grid point TP exists near the boundary SF of the visual volume VV, and the attribute value is temporarily set to “BORDER”. If there is no intersecting image FT and there is at least one image in which the projection point of the grid point TP exists outside the shielding contour, it is determined that the grid point TP exists outside the subject, and the attribute value is temporarily set. "OUTSIDE".
In other cases, it is determined that the grid point TP exists inside the subject, and the attribute value is temporarily set to “INSIDE”. (Second method) The grid point TP of interest is projected on all the images FT. With each projected point as the center, it is checked whether or not there is an occluded contour in an area inside a circle having a constant radius from the center. The image determined to include the occlusion outline is 1
If any one exists, it is determined that it exists near the boundary SF of the visual volume VV. When there is no image determined to include the occlusion outline, and if there is at least one image in which the projection point of the grid point TP exists outside the occlusion outline, it is determined that the image exists outside the subject. Otherwise, it is determined that it exists inside the subject.

In this way, for one grid point TP, provisional attribute values are determined in consideration of all the images FT. If the temporary attribute value is “OUTSIDE” or “INSIDE”, the attribute value is, for example, “minus infinity” or “plus infinity”, respectively. If the provisional attribute value is “BORDER”, a signed distance is calculated (# 63).

The calculation method of the signed distance is basically the same as that described in the description of step # 43. However, here, for one grid point TP, all the images FT
At the same time to determine the signed distance.

That is, for example, the signed distance is calculated as follows. (First method) A grid point TP of interest is projected on all the images FT. From all the projected images FT, the one with the shortest distance from the projection point to the shielding contour is selected. For the selected image FT, a line of sight passing through a point on the shielding contour is determined. The distance from the grid point TP to the line of sight is determined. The obtained distance is assigned an attribute value by adding a plus or minus sign. (Second method) With respect to all the images FT, the shielding contours are sampled at regular intervals, and similarly to the third method in step # 34, the signed distance is three-dimensionally determined using the line of sight passing through the shielding contour. calculate.

Next, in step # 64, step # 4
An attribute value is set to the grid point TP in the same manner as in step 4. However, here, a final attribute value is set for each grid point TP.

In step # 65, similarly to step # 45, it is checked whether the processing has been performed for all the grid points TP. According to the third embodiment, since the signed distance is calculated only for the lattice point TP whose temporary attribute value is “BORDER”, the calculation amount of the signed distance is significantly reduced. Therefore, the processing speed is high. [Conversion Processing According to Fourth Embodiment] Next, a conversion processing using an octree expression will be described as a fourth embodiment.

FIG. 14 is a flowchart showing the conversion processing of the fourth embodiment. FIG. 15 is a flowchart showing a subroutine of the intersection determination processing in step # 75 of FIG.
6 and 17 are diagrams for explaining the principle of octree representation.

As shown in FIGS. 16 and 17, in the octree representation, a cube larger than the target object is defined, and this is defined as a root cube (Root-Cube) RC. When the root cube is bisected along each of the x, y, and z directions, eight cubes having a volume of 1/8 are generated. By repeating such division recursively to an arbitrary level, data of an octree is generated. The octree representation is itself known.

In FIG. 14, first, a root cube is set (# 71). When setting the root cube, input the coordinates and size of the center. Also, “CO” meaning inside the object is set as an initial value for all vertices of the root cube. Also, the attribute of the root cube is set to “GRAY” indicating that it intersects with the shielding contour, and the level is set to “0”. Attribute is "GRAY"
Is equivalent to the boundary cube in the present invention.

Next, an image F obtained by photographing an object which is a subject
Input all necessary images for T (# 7)
2). At this time, camera parameters at the time of capturing each image FT are input.

In step # 73, in step # 33
, A silhouette image FS is generated. Step #
At 74, a cube (root cube) is split. The division here is performed only for the cube whose attribute is "GRAY". The division is divided into eight. Then raise the level by one.

At step # 75, the intersection of the cubes is determined. Here, each of the divided cubes is projected on the image FT to determine whether or not there is an intersection with the shielding contour. Based on the result of the determination, the attributes of the cube are determined.

Then, the processes of steps # 74 and # 75 are repeated until the predetermined level is reached (# 76). Or, if there are no more cubes with the attribute "GRAY", the process ends there. In that case, in the subsequent processing, a cube on the boundary or a cube with vertices on the boundary is used as a cube whose attribute is “GRAY”.

When the processing is completed, the attribute value of each vertex is obtained and set for the cube whose attribute is “GRAY” (#
77). As a method of obtaining an attribute value for each vertex, the method described in the second embodiment can be used.

In FIG. 15, attention is paid to one of the divided cubes (# 81). The cube is projected on all the images FT, and it is determined whether or not each of the cubes intersects with the shielding contour (# 82).

If it is determined that at least one image FT intersects the occluded contour, the attribute of the cube is set to “GRAY”. In all the images, if the projected cube exists in the occluded contour, the attribute of the cube is set to “WHITE” representing the inside of the object. In all images, if the projected cube exists outside the occluded contour, it is set to “BLACK” representing the outside of the object (#
83).

Here, "GRAY", "WHITE" and "BLACK"
Are "BORDER", "INSIDE", and "OUTS"
IDE ”. When the processing has been performed for all of the eight divided cubes (Yes in # 84), the process returns.

Also in the fourth embodiment, the attribute is “GRA
Since the signed distance is calculated only for the lattice point TP of the cube “Y”, the calculation amount of the signed distance is greatly reduced, and the processing speed is high.

As described above, according to the conversion processing of the first to fourth embodiments, multi-valued data can be provided at the grid point TP, and a high-precision three-dimensional shape is represented by a small number of voxels VX. can do. Therefore, the three-dimensional shape of the object can be represented with high accuracy with a small memory capacity.

The conversion processing of the second to fourth embodiments described above is mainly applied to a silhouette image. Next, a conversion process mainly applied to range data will be described in detail. [Conversion Processing According to Fifth Embodiment] FIG. 18 is a flowchart showing the conversion processing of the fifth embodiment, FIG. 19 is a view for explaining space carving, and FIG. 20 shows a state in which the volume data DV is cut along a horizontal plane. FIG. 21 is an enlarged view of a boundary voxel, and FIGS. 22 to 25 are diagrams for explaining a method of obtaining a nearest point MD.

Here, conversion processing is performed on a plurality of range data DR. Such multiple range data is
For example, it can be obtained by measuring the object from different positions around the object in a plurality of times. It is assumed that the positioning of the range data with respect to the volume data DV has been completed.

In FIG. 18, space carving (sp
ace carving) (# 91). Space carving is a process of cutting out unnecessary portions that are not objects from the volume data DV.

That is, as shown in FIG. 19, of the voxels VX of the volume data DV, the range data DR
Is set to “minus infinity” as the attribute value of the vertex TP of the voxel VX outside of. At this time, a line of sight including the range data DR is imagined from the viewpoint VP to the range data DR, and the voxel VX inside the line of sight and outside the range data DR.
Is the voxel VX to be clipped. However, as in the case of the above embodiment, the vertex TP near the range data DR is excluded. In FIG. 19, white voxels are displayed as external voxels VX.

Attention is paid to one grid point TPx (# 9)
2). The attribute value of the grid point TPx of interest is checked (# 93). If the attribute value is not "minus infinity", the process proceeds to step # 94.

With respect to the lattice point TPx, the nearest point MD is obtained (# 94). The nearest point MD in the i-th range data DR is set as the nearest point ri. The method of obtaining the nearest point MD is as follows.

As shown in FIG. 22, for each of the plurality of range data DR, a perpendicular line is drawn from the grid point TPx. When a plurality of perpendicular lines can be drawn for one range data DR, the shortest perpendicular line is selected. The drop point is the closest point MD1,2. However, the perpendicular length LM
Condition 1 and 2 are shorter than a predetermined length α. That is, when both the lengths LM1 and LM2 of the perpendicular are larger than the predetermined length α, it is assumed that the nearest point MD does not exist.

If the nearest point MD does not exist (# 95)
No), the attribute value of the grid point TPx is set to “plus infinity” (# 96). If there is one or more nearest points MD (Yes in # 95), the nearest point MD closest to the lattice point TPx among the nearest points MD is referred to as the nearest point rmin.
(# 97).

Here, the closest point MD is selected from the three-dimensional polygon data DP constituting the range data DR. That is, in FIGS. 23 and 25, the nearest point MD1 on the range data DR with respect to the grid point TPx
Coincides with a three-dimensional point existing as the polygon data DP of the range data DR. Therefore, the coordinates of the closest point MD1 match the coordinates of the polygon data DP. Since the coordinates of the polygon data DP are known, the coordinates of the nearest point MD1 can be obtained very easily. However, recently MD1
Is not the point that is truly closest to the range data DR. Therefore, when obtaining the signed distance later, the correction is performed by multiplying the cosine of the angle formed by the normal.

On the other hand, as shown in FIG. 24, when an arbitrary point PMT on the polygon mesh PM is set as the nearest point MD, a true nearest point with respect to the range data DR can be obtained. However, in this case, since the coordinates of the nearest point MD1 need to be obtained by calculation from the coordinates of the surrounding polygon data DP, it takes time to obtain the coordinates.

Returning to FIG. 18, in step # 98, the signed distance from the grid point TPx to the range data DR is calculated by calculating one or more nearest points M from the grid point TPx.
It is determined by a weighted average of the distance to D. The method for obtaining the signed distance is as follows.

That is, in the nearest point MD, the nearest point rmi
Only the closest point MD within a certain distance from n is extracted.
It also includes the nearest point rmin. In other words, the most recent rmi
Exclude the closest point MD that is more than a certain distance from n. The distance from the lattice point TPx is determined for the extracted nearest point MD. It is obtained by a weighted average of all the distances obtained.

That is, the signed distance of the lattice point TPx is dr (x): dr (x) = Σwi · [ni · (ri−TPx)] / Σwi (1) where ri is the i-th range The nearest point ni in the data is the normal vector of the nearest point ri wi is the weight of the nearest point ri

[0090]

(Equation 1)

Is obtained. That is, the lattice point TP
The distance between x and the nearest point ri is given by the length of the line connecting the grid point TPx and the nearest point ri (that is, the distance between them),
It is obtained as a value obtained by multiplying the cosine of the angle between the line and the normal at the nearest point ri. That is, the distance in the normal direction to the lattice point TPx at the closest point MD is obtained.
The sign of the distance is minus in the normal direction. Weight (weight) according to the reliability of each nearest point ri for the obtained distance
And average. This gives the signed distance.

The weight wi is the cosine of the angle formed by the normal vector ni at the nearest point ri and the vector starting at the lattice point TPx and ending at the nearest point ri. That is, since it is considered that the larger the angle is, the lower the reliability is, the weight wi is reduced.

The obtained signed distance is converted to the lattice point TPx
Stored as attribute value of It is checked whether the processing has been performed for all the grid points TP (# 99). If there is a lattice point TP that has not been processed yet, step # 92 and subsequent steps are repeated. When the processing for all the lattice points TP has been completed, the processing ends. Thus, a volume table TLr similar to the volume table TLs of FIG. 11 corresponding to the range data DR is completed. [Integration of Volume Data] In steps # 2 and # 3, volume data DV using the silhouette image FS and volume data DV using the range data DR are generated. In step # 4, these volume data DV are integrated. Volume data DV
In the integration of the voxel VX, the integrated attribute value of the voxel VX is obtained based on the two attribute values of the voxel VX corresponding to each other in each volume data DV. Note that the attribute value of the volume data DV based on the silhouette image FS is
The attribute value of the volume data DV based on the silhouette attribute value ds and the range data DR may be described as a range attribute value dr, and the attribute value of the integrated volume data DV may be described as an integrated attribute value dt.

FIG. 26 is a diagram showing the positional relationship between the attribute value of the grid point TP and the surface HM of the object, and FIG. 27 is a diagram showing a method of integrating the two attribute values. As shown in FIG. 26, the surface HM of the object is classified into four (outside (far), outside (near), inside (near), and inside (far) according to the value of the attribute value.

In other words, when the attribute value is “minus infinity”, it is outside (far), when the attribute value is “plus infinity”, it is inside (far), and the attribute value is negative and not “minus infinity”. If the attribute value is positive and is not “plus infinity”, it is internal (near). This is applied to the volume data DV using any of the silhouette image FS and the range data DR.

As shown in FIG. 27, the silhouette attribute value d
When s is outside (far), the integrated attribute value dt is “minus infinity” indicating the outside (far) regardless of the contents of the range attribute value dr. When both the silhouette attribute value ds and the range attribute value dr are inside (far), the integrated attribute value dt is “plus infinity” indicating the inside (far). Silhouette attribute value ds is inside (far) and range attribute value d
If r is external (far), this is not really possible, but the integrated attribute value dt is "minus infinity" indicating external (far).

Otherwise, if one is outside (far) or inside (far) and the other is outside (near) or inside (near), the outside (near) or inside (near) Attribute value is used. If both are external (near) or internal (near), both attribute values are mixed. By the mixing, the integrated attribute value dt is calculated by the following equation (3).

Dt = wxdr + (1-wx) ds (3) where wx represents the weight of the range attribute value dr at the grid point TPx. That is, the range attribute value dr and the silhouette attribute value ds are mixed at a ratio according to the weight wx of the range attribute value dr. The value of the load wx is determined according to the shape of the object and the like. In this way, by adding at an appropriate ratio according to the weight, the boundary between the volume data DV based on the silhouette image FS and the volume data DV based on the range data DR is smoothly connected. The obtained integrated attribute value dt is stored as the attribute value of the grid point TP. In this way, attribute values are obtained for all grid points TP. This completes the integration process.

As described above, by integrating the volume data DV based on the silhouette image FS and the volume data DV based on the range data DR, it is possible to generate a highly accurate three-dimensional model ML that compensates for each of the drawbacks and has no loss. it can.

Therefore, even when the object has a concave area or a part with a low reflectance, the three-dimensional shape can be accurately restored with a memory capacity as small as possible and in a short calculation time.

In the embodiment described above, the attribute value is set at the vertex of the voxel. However, the attribute value need not always be set at the vertex of the voxel. For example,
The center of gravity of the voxel may be used.

Although the distance value between the vertex and the boundary is set only for the voxel that intersects the boundary, it may be set for all the voxels. However, the operation time is shortened when the operation is performed only on the intersecting voxels as in the embodiment. Although the inside of the object is expressed as positive and the outside is expressed as negative, the opposite may be used.

In the fourth embodiment, an example in which the cube is divided into eight parts has been described. However, the invention is not limited to eight parts, and the cube may be divided into three parts in each of the xyz directions, that is, the cube may be divided into 27 parts. It may be divided.

In the embodiment described above, the configuration of the whole or each part of the three-dimensional data generating device 1, the content and order of processing, the number of voxels VX, the number of digits of attribute values, etc. are in line with the gist of the present invention. It can be changed as appropriate.

[0105]

According to the present invention, a three-dimensional shape can be accurately restored with a memory capacity as small as possible and with a small calculation time even when there is a concave area or a part with a low reflectance.

[Brief description of the drawings]

FIG. 1 is a block diagram of a three-dimensional data generation device according to an embodiment.

FIG. 2 is a flowchart illustrating a flow of a three-dimensional model generation process performed by the three-dimensional data generation device.

FIG. 3 is a flowchart illustrating a conversion process performed by the three-dimensional data generation device.

FIG. 4 is a flowchart illustrating a modification of the conversion process.

FIG. 5 is a flowchart illustrating a conversion process according to the second embodiment.

FIG. 6 is a flowchart illustrating a subroutine of an attribute value setting process in step # 34 of FIG. 5;

FIG. 7 is a diagram for explaining a state in which a silhouette image is projected on volume data.

8 is an enlarged view showing a part of the silhouette image shown in FIG. 7;

FIG. 9 is a diagram showing a state where volume data is cut along a horizontal plane.

FIG. 10 is an enlarged view of a boundary voxel.

FIG. 11 is a diagram illustrating an example of a volume table storing volume data.

FIG. 12 is a flowchart illustrating a conversion process according to the third embodiment.

FIG. 13 is a flowchart showing a subroutine of an attribute value setting process in step # 54 of FIG.

FIG. 14 is a flowchart illustrating a conversion process according to the fourth embodiment.

FIG. 15 is a flowchart showing a subroutine of intersection determination processing in step # 75 of FIG. 14;

FIG. 16 is a diagram for explaining the principle of octree expression.

FIG. 17 is a diagram for explaining the principle of octree expression.

FIG. 18 is a flowchart illustrating a conversion process according to the fifth embodiment.

FIG. 19 is a diagram for explaining space carving.

FIG. 20 is a diagram showing a state where volume data is cut along a horizontal plane.

FIG. 21 is an enlarged view showing a boundary voxel.

FIG. 22 is a diagram for explaining a method for obtaining a nearest point.

FIG. 23 is a diagram for explaining a method for obtaining a nearest point.

FIG. 24 is a diagram for explaining a method for obtaining a nearest point.

FIG. 25 is a diagram for explaining a method for obtaining a nearest point.

FIG. 26 is a diagram illustrating a positional relationship between attribute values of grid points and the surface of an object.

FIG. 27 is a diagram illustrating a method of integrating two attribute values.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 3D data generation apparatus 10 Device main body (1st conversion means, 2nd conversion means, integration means) 11 Magnetic disk drive DV Volume data VX Voxel FT image FS Silhouette image CD CD-ROM (recording medium) FD Floppy disk (Recording medium) TL Volume table (Volume data) PR Modeling program (Computer program)

 ──────────────────────────────────────────────────続 き Continued on the front page F term (reference) 5B057 CA13 CA16 CB13 CB16 CE08 CH09 DB03 DC01 DC16 5B080 AA00 AA17 GA22

Claims (8)

[Claims] 1. A method for generating three-dimensional shape data of an object, wherein the first volume data is generated by converting a plurality of images of the object from different viewpoints into volume data using a silhouette method. A first step of generating the second volume data by converting three-dimensional data obtained by three-dimensional measurement of the object into volume data; and a second step of generating the second volume data and the second volume data. A third step of integrating volume data into one volume data; and a method for generating three-dimensional shape data. 2. The volume data according to claim 1, wherein at each discrete coordinate position in a coordinate system expressing the volume, a value corresponding to a distance from the surface of the object is held. How to generate dimensional shape data. 3. In the first step, when converting into volume data using the silhouette method, (a) at each discrete coordinate position in the coordinate system expressing the volume, the outline of the image of the object and the Obtaining a value corresponding to the distance to the boundary of the viewing volume determined by the viewpoint of the image; and (b) calculating, for each coordinate position, a distance from the object surface based on a plurality of values obtained for a plurality of images of the object. 3. The method according to claim 2, further comprising: deciding a value corresponding to the coordinate value and holding the value in association with each coordinate position. 4. In the second step, when converting three-dimensional data into volume data, (a) at each discrete coordinate position in a coordinate system expressing a volume,
3. The method according to claim 2, further comprising: a step of obtaining a value corresponding to a distance to an object surface represented by the three-dimensional data of the object; and (b) a step of storing the obtained value in association with each coordinate position. How to generate dimensional shape data. 5. The method according to claim 2, wherein in the third step, a value of the first volume data and a value of the second volume data are added at a predetermined ratio to each coordinate position. How to generate dimensional shape data. 6. An apparatus for generating three-dimensional shape data of an object, wherein the first volume data is generated by converting a plurality of images of the object from different viewpoints into volume data using a silhouette method. First converting means for converting the three-dimensional data obtained by three-dimensional measurement of the object into volume data to generate second volume data; and the first volume data. An integrating means for integrating the first volume data with the second volume data to form one volume data. 7. A computer program for generating three-dimensional shape data of an object, comprising converting a plurality of images of the object from different viewpoints into volume data by using a silhouette method. A first step of generating data, a second step of generating second volume data by converting three-dimensional data obtained by three-dimensional measurement of the object into volume data, A third step of integrating the second volume data into one volume data, and causing the computer to execute the third step. 8. A computer-readable recording medium on which the computer program according to claim 7 is recorded.