JP2001307073A - Three-dimensional space reconstruction apparatus and three-dimensional space reconstruction method - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To provide a three-dimensional space reconstruction method capable of achieving both sufficient resolution and high-speed processing by dramatically reducing the amount of computation. SOLUTION: A maximum voxel in which a target object cannot be accommodated is determined. Initially, a plurality of voxels obtained by dividing the measurement target space by the maximum voxel are output as divided voxels, and a divided voxel obtained by dividing a given voxel into a fixed number is output from the beginning. It is determined whether or not each of the divided voxels and the target object overlap. Further, if the divided voxel determined to overlap with the target object does not satisfy the certain escape condition, the divided voxel is repeatedly divided. Only meaningful voxels are divided stepwise from large to small.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a three-dimensional space reconstructing apparatus and method for reconstructing a three-dimensional shape of a target object with minimum voxels using a volume intersection method.

[0002]

2. Description of the Related Art Volume Integer
As a conventional example of a three-dimensional spatial reconstruction method using the Rection method, a document “Virtual” by SAIED MOEZZI of the University of California, USA, et al.
View generation for 3D Di
digital video "(IEEE MULTIME
DIA Vol. 4 No. 1 pp. 18-26, 1
997).

In this method, a measurement target space into which a target object enters is divided into small cubes (voxels). That is, the measurement target space is treated as a space in which the voxels (corresponding to the “minimum voxel” of the present invention) are stacked without any gap in the XYZ directions. The length of one side of the voxel determines the resolution of the measurement.The smaller the length of one side, the higher the resolution of the measurement.The larger the length of one side, the higher the resolution of the measurement. descend.

Here, each length of the measurement object space in the XYZ directions is XL times the length of one side of the voxel, YL
And ZL times, the measurement target space is XL ×
This means that the space is filled with YL × ZL voxels.

[0005] In the visual volume intersection method, these XL ×
For all the YL × ZL voxels, it is determined whether the corresponding voxel is inside the target object or not (examination count: XL × YL × ZL times). As a result of the investigation, the three-dimensional shape of the target object is reconstructed so as to pile a block with so-called blocks of voxels inside the target object.

More specifically, as shown in FIG. 18, a plurality of cameras are set so as to have viewpoints 1 to n (usually n ≧ 3), and an object is photographed from different directions.

As a result, the silhouette of the target object is photographed on the image plane of each camera. The state of the voxel (whether the voxel and the target object overlap) can be determined based on whether or not the pixel corresponding to the voxel is included in the silhouette.

For example, a pixel corresponding to voxel A outside the target object is outside the silhouette in at least one camera image (in FIG. 18, outside the silhouette on image plane 1). Also, the pixel corresponding to voxel B inside the target object is inside the silhouette in all camera images.

That is, the pixel corresponding to a certain voxel is
In all camera images, if the voxel is included in the silhouette of the target object, the voxel is inside the target object. Conversely, in any camera image, if the pixel corresponding to the voxel is not included in the silhouette of the target object, the voxel is outside the target object.

If the camera calibration has been completed and camera parameters such as the camera position, posture, and focal length are known, the geometrical relationship is determined from the positional relationship between the lens center, the voxel position, and the image plane. In addition, the position where the voxel is projected on the image plane can be easily obtained.

FIG. 19 shows a configuration example for this purpose. FIG.
, A multi-directional image acquisition means 1 including a camera group and the like
, Simultaneously shoots a target object from a plurality of different viewpoints and directions, and outputs image data thereof.

The parameter holding means 2 holds information such as the positions and orientations of a plurality of cameras constituting the multi-directional image acquisition means 1 which have been input in advance.

The voxel state table holding means 3 holds the state of all voxels (whether voxels and target objects overlap).

The voxel generating means 4 of interest is XL × YL ×
The ZL voxels are sequentially selected one by one and output as the focused voxel.

The state determination means 5 of the target voxel outputs the voxel of interest output from the target voxel generation means 4 from the image data of the multi-directional image acquisition means 1 and the parameters of each camera held in the parameter holding means 2. The state of the voxel is determined in the manner described above, and the contents of the voxel state table holding means 3 are updated.

Next, a processing example will be described with reference to FIG. First, the target voxel state determination unit 5 accesses the voxel state table holding unit 3 to perform initialization, and sets all voxel states to “occupied” (meaning that the voxel and the target object overlap) ( Step S10
01).

Next, the focused voxel generating means 4 determines the first focused voxel (step S1002), and the focused voxel state determining means 5 determines the center position of the voxel,
A pixel p at a point where a straight line connecting the lens center of the first camera intersects the image plane is determined (step S100).
4).

In step S1005, the state determination means 5 for the voxel of interest determines whether or not the pixel p is included in the silhouette on the image plane. If the pixel p is not included in the silhouette, the state of the voxel is determined. It is set to “empty”, and the process proceeds to the next voxel (step S1006). If it is included, the process from step S1003 is repeated for the next camera.

If the state is included in all the cameras, the state remains "occupied"; otherwise, the state becomes "empty".

The above processing is repeated for all voxels (step S1002).

When these series of processes are completed, the state of all voxels is determined, and the three-dimensional space is reconstructed.

[0022]

At present, it is assumed that the measurement accuracy is insufficient with the current resolution, and in order to improve the resolution, the length of one side of the voxel is assumed to be １ ／ times as long as before. . Then, the measurement target space is (4 × XL)
× (4 × YL) × (4 × ZL) = 64 (XL × YL × Z
L) voxels will be filled, and the number of surveys will be 64 times larger than before.

As is apparent from this example, in the prior art, when trying to obtain a practical resolution, the amount of calculation becomes enormous, and it becomes very difficult to perform real-time processing. was there.

An object of the present invention is to provide a three-dimensional space reconstructing apparatus and a method thereof which can achieve both sufficient resolution and high-speed processing while dramatically reducing the amount of calculation.

[0025]

According to the present invention, an object in a measurement object space is imaged from different directions, and
A target object is reconstructed by a mass of a number of minimum voxels. A voxel dividing unit that outputs a divided voxel obtained by dividing a given voxel into a fixed number while outputting as a divided voxel, and whether each of the divided voxels output by the voxel dividing unit and the target object overlap with each other. Voxel state determining means for determining the voxel state, and control means for giving the divided voxel to the voxel dividing means when the divided voxel determined to overlap with the target object does not satisfy a certain escape condition, and repeatedly dividing the voxel. .

With this configuration, the amount of calculation in the three-dimensional space reconstruction is dramatically reduced, and both a sufficient resolution and high-speed processing can be achieved.

[0027]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS In a three-dimensional space reconstruction apparatus according to the present invention, a target object in a measurement target space is imaged from different directions, and a large number of minimum voxel clusters are used.
Maximum voxel determination means for reconstructing the target object, determining the maximum voxel that the target object can not fit,
Initially, a plurality of voxels obtained by dividing the measurement target space by the maximum voxel are output as divided voxels, and voxel dividing means for outputting a divided voxel obtained by dividing a given voxel into a fixed number, and voxel dividing means, Voxel state determining means for determining whether or not each divided voxel and the target object overlap with each other, and the divided voxel determined to overlap with the target object does not satisfy a certain escape condition. And a control unit for giving the voxel dividing unit a repetitive division.

In this configuration, by repeating the voxel division starting from the above-described maximum voxel, the search for empty voxels can be reduced, and the calculation amount can be greatly reduced.
As a result, even if one side of the minimum voxel is reduced in order to obtain a sufficient resolution, the three-dimensional space of the target object can be reconstructed in a practical processing time.

In the three-dimensional space reconstruction apparatus according to the second aspect, the constant escape condition is that the size of the divided voxel and the size of the minimum voxel are the same.

With this configuration, when the repetitive processing is completed, the three-dimensional shape of the target object can be reconstructed with the minimum voxel block without any special processing.

In the three-dimensional space reconstruction apparatus according to the third aspect, the fixed number is eight.

According to this configuration, it is possible to easily divide each half in the XYZ directions.

In the three-dimensional space reconstruction apparatus according to the fourth aspect, the voxel state determining means examines only the vicinity of the surface of a given voxel, and when a target object can be detected near any of the surfaces, the voxel state is determined. It is determined that the target object and the target object overlap.

With this configuration, the amount of calculation can be further reduced by omitting the investigation inside the divided voxels.

In the three-dimensional space reconstruction apparatus according to the fifth aspect, the voxel state determining means has a sample voxel generating unit for generating a sample voxel by sampling a part near the surface of the voxel, and based on the sample voxel. Then, the target object is detected.

With this configuration, it is possible to further reduce the amount of calculation by thinning out the calculation target by sampling.

In the three-dimensional space reconstruction apparatus according to the sixth aspect, the sample voxel is any one of a plurality of voxels obtained by equally dividing a given voxel by a minimum voxel size.

With this configuration, the state of the sample voxel and the state of the minimum voxel become the same, and the state determination processing can be omitted for the minimum voxel that matches the sample voxel at a stage where the sample voxel is later divided. The amount of calculation can be reduced accordingly.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.

In FIG. 1, a control means 10 controls each means described later. In particular, when the divided voxel determined to overlap with the target object does not satisfy the certain escape condition, the divided voxel is provided to the voxel dividing unit 18 to be repeatedly divided.

The input means 11 receives an input from an operator.

The multi-directional image obtaining means 12 captures a target object in the measurement target space from different directions and viewpoints, and outputs a plurality of image data.

The storage means 13 includes a program executed by the control means 10, an area for temporarily storing information as necessary, and a voxel state table for holding the state of each voxel for each repetition level described later. It has 14. Of course, other well-known data structures, such as lists, may be adopted as long as reading and writing are free without using such a table.

The parameter holding means 15 holds parameters such as the positions and postures of all the cameras.

The maximum voxel determining means 16 determines the maximum voxel that cannot be covered by the target object.

The escape condition judging means 17 is a constant escape condition referred to when the control means 10 re-divides the divided voxel using the repeated voxel dividing means 18 (in this example, the divided voxel has the same size as the smallest voxel). Is determined to be satisfied. Note that the escape condition may be changed such that the divided voxel is several times the minimum voxel.

The voxel dividing means 18 initially outputs a plurality of voxels obtained by dividing the measurement target space by the maximum voxels as divided voxels, and outputs divided voxels obtained by dividing a given voxel into a fixed number thereafter.

The voxel state determining means 19 determines whether or not each of the divided voxels output by the voxel dividing means 18 and the target object overlap. In this example,
The voxel state determination means 19 examines only the vicinity of the surface of the given voxel, and when a target object can be detected near any surface, determines that the voxel and the target object overlap.

The voxel state determining means 19 has a sample voxel generator 20 which samples a part of the voxel near the surface to generate a sample voxel, and detects a target object based on the sample voxel.

Then, the sample voxel state determination unit 21
Only the sample voxel generated by the sample voxel generator 20 is examined. If at least one of the sample voxels overlaps with the target object, the corresponding divided voxel (regardless of size) overlaps with the target object. Otherwise, it is determined that the divided voxel and the target object do not overlap.

More specifically, the result is as shown in FIG. That is, when the target object O (here, it is assumed to be a human) exists in the measurement target space S, the target object O is imaged from different directions by the multidirectional image acquisition means 12. That is, the target object O is imaged by a plurality of cameras 22 to 26 (preferably four or more in order to prevent occlusion) having different viewpoints and directions.
The image data is taken into the information processing device by a group of capture boards 27 connected to the information processing device 6.

The information processing apparatus includes a keyboard 28 serving as input means, a bus 28 for mediating data communication between elements, a CPU 29, a memory 30, and an external storage device 31. Here, each of the means 10 and 15 to 19 described above includes:
This is realized by the CPU 29 reading and writing from and to the memory 30 and the external storage device 31 as the storage unit 13 and executing a program according to a flowchart described later.

Next, an outline of the processing of the present invention will be described. In the present invention, as described above, the concept of “maximum voxel” in which the target object cannot be accommodated is introduced. Here, the name such as “maximum” is a point at which this “maximum voxel” is the starting point of repetitive division of a voxel, which will be described later. Because it goes.

On the other hand, the voxel for determining the resolution is called "minimum voxel". In other words, the voxel division repeated in the present invention starts with the size of the maximum voxel, and then becomes smaller as the number of stages (expressed as levels in the following description) increases, and reaches the minimum voxel. Go through the process.

Here, in order to realize the processing of the present invention in the most ideal state, it is desirable that the target object satisfies the following conditions. (1) Although the target object can be deformed, the size of the smallest cube (minimum circumscribed cube) among the cubes spatially circumscribed in all the deformation patterns is known. (2) Assuming that a cross section obtained by cutting each part of the target object by an arbitrary surface is a circumscribed square on the cut surface, the size of the smallest square (minimum circumscribed square) is known.

However, the above conditions are not essential, and setting the maximum voxel relatively small is often sufficient for practical use.

FIG. 4 shows how to determine the maximum voxel V0 when a human is used as the target object. That is, a human has many joints and can take various postures. However, there is a posture in which even if the body is folded as small as possible, it cannot be further reduced. At this time, a cube that is slightly smaller than a cube circumscribing a human is determined, and is set as the maximum voxel (length of one side: L).

The maximum voxel V thus determined
Looking closely at the relationship between 0 and humans, the following can be seen. That is, since a human cannot fully enter the maximum voxel V0, a certain part of the human (in the example of FIG. 4, the head and the toe) must protrude from the maximum voxel V0.

Here, the maximum voxel V0 has six surfaces, and any part of these surfaces will cut off the protruding human part. More specifically, focusing on the surface of the maximum voxel V0, if a human part exists on any surface, the maximum voxel V0 can be obtained without looking inside the maximum voxel V0 (even if the investigation is omitted).
0 (that is, the maximum voxel V
0 and human beings overlap).

Conversely, if no human part exists on all surfaces of the maximum voxel V0, the maximum voxel V0
In, there is no human being (it does not overlap).

According to the present invention, based on the above findings, a process is used in which the maximum voxel V0 is used as a starting point and this is repeatedly subdivided. Further, when examining one maximum voxel, only the vicinity of the surface is examined, and the number of surveys can be reduced by omitting the internal survey.

Further, when it is determined that the maximum voxel V0 or the large divided voxel does not overlap the target object, the subsequent division (that is, more detailed investigation) is not performed.

If the maximum voxel V0 is composed of 1000 minimum voxels, and if it is determined that the maximum voxel V0 does not overlap the target object in one investigation, the subsequent investigation is omitted. On the other hand, in the prior art, since all of the minimum 1000 voxels were exhaustively investigated, the method of the present invention is much more advantageous than the prior art, and the amount of computation is dramatically reduced. It will be easily understood that it can be reduced.

FIG. 5 schematically illustrates the processing steps according to the present invention. Initially, as shown in FIG. 5A, the measurement target space S is divided into divided voxels having the same size as the maximum voxel V0. At this time, as shown in FIG. 5E, only the vicinity of the surface of each divided voxel is examined, and whether or not each divided voxel and the target object overlap is determined based on the above-described knowledge.

Further, in this example, instead of examining all of these surfaces, preferable thinning is performed by grid-like sampling, and only a part near the surface is examined.

Next, as shown in FIG. 5B, only the object overlapping with the target object is handled, and the division and the investigation of the divided voxels are repeated (from the level of FIG. 5B to the level of FIG. 5C). From the level in FIG. 5 (c) to the level in FIG. 5 (d)...), The process ends when the image is finally divided into the minimum voxels.

Hereinafter, a more specific description will be given. First, the voxel state table 14 is configured as shown in FIG. In other words, the voxel state table 14 stores a plurality of levels (FIG. 8A shows the maximum voxel size at level 0, FIG. 8A).
(D) is a state table of the voxel space of level Ls and the size of the smallest voxel).

In each table, voxels constituting each voxel space are associated with voxel numbers, which are identification numbers uniquely assigned within the same level, and their states.

Next, how to determine the size of the maximum voxel, the level of the minimum voxel, the interval between sample voxels, and the like will be specifically described. These parameters are determined when the required spatial resolution, the size of the measurement target space S, and the target object O are determined.

The length of one side of the minimum voxel is the same value as the required spatial resolution, and is set to Amin. In addition, the length A of one side of the minimum circumscribed cube described above is assumed.

The level Ls is obtained by the following equation.

[0072]

(Equation 1)

The maximum voxel size is obtained by the following equation.

[0074]

(Equation 2)

The sample voxel is the same size as the smallest voxel. The interval S between sample voxels is obtained by the following procedure. As shown in FIG. 9A, the length As of one side of the minimum circumscribed square is As, and as shown in FIG. 9B, the length At of one side of a square having a diagonal line of As is obtained by the following equation. .

[0076]

(Equation 3)

In order to set the interval S between sample voxels (interval for the minimum number of voxels S) to the power of 2, an index S1 satisfying the following equation is determined.

[0078]

(Equation 4)

In the following equation, the smaller value of the index S1 and Ls-L is defined as the index SS.

[0080]

(Equation 5)

The interval S between the sample voxels is obtained using the index SS according to the following equation.

[0082]

(Equation 6)

Next, a divided voxel of interest (hereinafter, simply referred to as a “vox of interest” in the following description and drawings)
The relationship between the surface and the sample voxel will be described.

First, the length of one side of the target voxel at the division level L and the interval S between the sample voxels are selected so as to be a power of two. In this case, FIGS. 10 (a) and 10 (b)
As shown in (1), sample voxels are arranged in a grid at intervals S on each surface of the voxel of interest.

Note that, strictly speaking, the center of the sample voxel is
Although it is not on the surface of the voxel of interest and is spatially shifted by about half the size of the sample voxel, it is located near the surface of the voxel of interest. This is because the sample voxel and the voxel of interest are in the above-described division relationship, and by doing so, the algorithm can be simplified and the processing speed can be improved.

Next, a more specific calculation example will be described. Here, the target object O is a single person, and a specific method for determining each parameter will be described.

The length of one side of the minimum voxel (that is, the required spatial resolution) is set to Amin = 6.25 mm.
The number of cameras is n = 4 (units).

Now, a human can take many postures. However, assuming a posture in which his back is round and his knees bent with both arms are bent, a cube circumscribing this posture is defined as a minimum circumscribed cube. The length of one side is A = 850 mm.

The level Ls that satisfies (Equation 1) is 7.

The size of the maximum voxel is given by
max = 800 mm.

Assuming that the measurement target space S is a cubic region having a side of 2400 mm, the maximum voxel is M = 3 × 3 × 3.
= 27 combined spaces.

Next, an interval S between sample voxels is obtained. Here, the thinnest part of the human body is the wrist (in this example, the finger of the limb thinner than the wrist is not measured). If the minimum cross section of the wrist is a circle having a diameter of 75 mm, the length of one side of the minimum circumscribed square is As = 75 mm.

(Equation 3) gives At = 53 mm, (Equation 4) gives an index S1 = 3, and (Equation 5) gives an index SS = 3 or SS = 7-L depending on the magnitude relationship between S1 and 7-L. From (Equation 6), the sample voxel interval S is similarly S1
S = 8 or S = 2 ＾ (7
-L).

Next, the operation of the three-dimensional space reconstruction apparatus of the present invention will be described with reference to the flowcharts of FIGS.

First, in step S0 in FIG. 11, the n cameras 22 to 26 use the measurement target space S including the target object O.
To shoot the image at the same time. In addition, a silhouette of the target object O is extracted as image data based on a background difference from an image of only the background without the target object O which has been captured in advance.

Next, the elements of the state table of the voxel space of all levels are set to "undecided" (step S).
1).

Next, the processing of steps S2 to S6 is repeated for levels L = 0 to Ls. Here, the counter L indicating the level defines an escape condition, and when exiting the loop, the voxel of interest has the same size as the minimum voxel. In step 2, an interval S between sample voxels matching the level L is determined from (Equation 3) to (Equation 6). Further, the coarse voxels are divided into level L voxels, each of which is set as a target voxel Vi (step S3).

That is, here, as shown in FIG. 12, the level L is evaluated (step S31). If L = 0 (initial), the measurement target space S is divided into M level 0 voxels (maximum). (The same size as the voxel), and set as M focused voxels Vi (step S33). Also, L
If ≠ 0 (other than at the beginning), one coarse level (L-
1) With reference to the state table of the voxel space, only the voxels in the “occupied” state are divided into level L voxels and set as the voxel of interest Vi (step S32).

After step S3 in FIG. 11, the processing of steps S4 to S6 is repeated for each voxel of interest Vi. That is, the sample voxel on the surface of the target voxel Vi is set to SVj (step S4), and all the sample voxels S
The state of Vj is determined (step S5).

Here, as shown in FIG. 13, the processing of steps S51 and S52 is repeated for all the sample voxels SVj.

That is, the state of the sample voxel SVj is evaluated, and if "undecided", the state is determined by the visual volume intersection method (steps S51 and S52).

In this volume intersection method, as shown in FIG. 14, a straight line connecting the center of the sample voxel SVj and the center of the lens of the camera C is defined by a pixel Pc at a position where the pixel Pc intersects the image plane of the camera C. (C = 1 to n) is obtained (step S521).

When all the pixels Pc (C = 1 to n) are on the silhouette of the target object O, the state of the sample voxel SVj is set to “occupied”, and at least one of the pixels Pc is not on the silhouette. At this time, it is set to “empty” and the state table of the minimum voxel space is updated (step S52).
2-524). As described above, the state of the sample voxel SVj can be determined.

Next, in step S6 in FIG. 11, the state of the target voxel Vi is determined from the state of the sample voxel SVj. Here, if the state of all the sample voxels SVj on the surface of the target voxel Vi is “empty”, the target voxel V
The state of i is set to “empty”, and if at least one of the sample voxels Vi is in the state of “occupied”, the state of the voxel Vi of interest is set to “occupied”. Thus, the level L voxel space can be determined, and the three-dimensional space reconstruction of the measurement target space 121 has been completed in the level L voxel space.

For the voxels not divided into levels L in step S3, the contents of the state table remain "undecided". This is the level before division (L-1)
At the voxel stage, it has been found that the object does not overlap with the target object, so the “undecided” state may be regarded as an “empty” state. These voxels will not be discussed in further detail hereafter.

The above processing is repeated from level L = 0 to LS-1, and the three-dimensional space reconstruction of the measurement target space 121 is completed in all level L voxel spaces.

Further, in step S7 in FIG. 11, the three-dimensional space is reconstructed using the minimum voxel. Here, as shown in FIG. 16, referring to the state table in the level (Ls-1) voxel space, only the voxels in the “occupied” state
The image is divided into voxels Vi of interest (step S71).

Then, the processing of steps S72 and S52 is repeated for all the voxels Vi of interest. That is,
The state of the voxel Vi of interest is evaluated, and if "undecided", the state is determined by the visual volume intersection method (step S52).

Here, at the level Ls, the voxel of interest and the minimum voxel are the same, and the result of determining the sample voxel by the processing so far is recorded in the state table of the minimum voxel space. No additional processing is required.

With the above processing, reconstruction of the three-dimensional space of the measurement target space S in the minimum voxel space is completed, and the position and shape of the target object O inside the measurement target space S can be determined.

Assuming that the measurement target space S is a room or the like, the volume occupancy of the person (volume occupancy of the target object in the measurement target space) is several percent to 10% or less at most. That is, most of the measurement target space is in an “empty” state where no people are present. In such a situation with a low volume occupation ratio, the fact that coarse voxels can be deleted from the calculation target greatly contributes to a reduction in the amount of calculation. Incidentally, when the measurement is actually performed, the volume occupancy is often about this level, which is practically effective.

According to the estimation of the present inventors, a space (measurement target space) of 2400 mm 3 is imaged by four cameras and 1
When measuring the movement of a person (height 1700 mm)
Volume occupancy of the person in the measurement target space (space occupancy)
Is about 1.38%, and as shown in FIG. 17, the amount of calculation is drastically reduced to about 1/50 to 1/60 as compared with the related art.

[0113]

According to the present invention, the maximum voxel is used by paying attention to the properties of the target object, and furthermore, only the significant portion is repeatedly subjected to voxel division.
The amount of computation can be dramatically reduced, and while having sufficient resolution,
Processing can be completed at high speed.

[Brief description of the drawings]

FIG. 1 is a functional block diagram of a three-dimensional space reconstruction apparatus according to an embodiment of the present invention.

FIG. 2 is a functional block diagram of the same.

FIG. 3 is a block diagram of the same.

FIG. 4 is an explanatory diagram of the maximum voxel.

FIG. 5A is a schematic diagram of the flow of the same process; FIG. 5B is a schematic diagram of a flow of the same process; FIG. 5C is a schematic diagram of a flow of the same process; Outline diagram of flow

FIG. 6A is an explanatory diagram of the measurement target space. FIG. 6B is an explanatory diagram of the maximum voxel.

FIG. 7A is an explanatory view of dividing the same voxel. FIG. 7B is an explanatory view of dividing the same voxel. FIG. 7C is an explanatory view of dividing the same voxel.

FIG. 8A is a view showing an example of the voxel state table. FIG. 8B is a view showing an example of the voxel state table. FIG. 8C is a view showing an example of the voxel state table.

FIG. 9A is an explanatory diagram of the parameter; FIG. 9B is an explanatory diagram of the parameter;

FIG. 10A is an explanatory diagram of the sample voxel. FIG. 10B is an explanatory diagram of the sample voxel.

FIG. 11 is the same flowchart.

FIG. 12 is the same flowchart.

FIG. 13 is the same flowchart.

FIG. 14 is the same flowchart.

FIG. 15 is the same flowchart.

FIG. 16 is the same flowchart.

FIG. 17 is a graph showing the relationship between the calculation amount and the volume occupancy.

FIG. 18 is a diagram illustrating the principle of conventional three-dimensional space reconstruction.

FIG. 19 is a functional block diagram of the three-dimensional space reconstruction apparatus.

FIG. 20 is a flowchart of the three-dimensional space reconstruction apparatus.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 10 Control means 12 Multi-directional image acquisition means 14 Voxel state table 16 Maximum voxel determination means 18 Voxel division means 19 Voxel state determination means

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Hiroyuki Yoshida 1006 Kazuma Kadoma, Kadoma City, Osaka Prefecture F-term in Matsushita Electric Industrial Co., Ltd. 5B047 AA07 BB06 CA14 CB22 5B057 BA02 CB13 CD20 CE10 CH07 DA06

Claims (12)

[Claims] 1. A three-dimensional space reconstruction apparatus for imaging a target object in a measurement target space from directions different from each other and reconstructing the target object by a mass of a number of minimum voxels. Maximum voxel determining means for determining the maximum voxel that cannot be cut off, and initially outputting a plurality of voxels obtained by dividing the measurement target space by the maximum voxel as a divided voxel, and dividing a given voxel into a fixed number from the beginning. Voxel dividing means for outputting voxels, voxel state determining means for determining whether or not each of the divided voxels output by the voxel dividing means and the target object overlap with each other, and a divided voxel determined to overlap with the target object. But,
A three-dimensional space reconstructing apparatus, comprising: a controller that supplies the divided voxel to the voxel dividing unit when the predetermined escape condition is not satisfied, and performs repeated division. 2. The three-dimensional space reconstruction apparatus according to claim 1, wherein said constant escape condition is that the size of the divided voxel and the size of the smallest voxel are the same. 3. The three-dimensional space reconstruction apparatus according to claim 1, wherein the predetermined number is eight. 4. The voxel state determining means examines only the vicinity of the surface of a given voxel, and when a target object can be detected near any of the surfaces, determines that the voxel and the target object overlap. The three-dimensional space reconstruction apparatus according to claim 1, wherein 5. The voxel state determining means includes a sample voxel generating unit that samples a part of the voxel near its surface to generate a sample voxel, and detects a target object based on the sample voxel. The three-dimensional space reconstruction apparatus according to claim 4, wherein 6. The three-dimensional space reconstruction apparatus according to claim 5, wherein the sample voxel is one of a plurality of voxels obtained by equally dividing a given voxel by a minimum voxel size. 7. A three-dimensional space reconstruction method for imaging a target object in a measurement target space from directions different from each other, and reconstructing the target object by a large number of minimum voxel clusters. Determining a maximum voxel that cannot be cut, and initially outputting a plurality of voxels obtained by dividing the measurement target space by the maximum voxel as a divided voxel, and outputting a divided voxel obtained by dividing a given voxel into a fixed number from the beginning. Determining whether each of the divided voxels and the target object overlap with each other, and determining whether or not the divided voxel and the target object overlap with each other.
And a step of repeatedly dividing the divided voxels when the fixed escape condition is not satisfied. 8. The three-dimensional space reconstruction method according to claim 7, wherein the constant escape condition is that the size of the divided voxel and the size of the smallest voxel are the same. 9. The three-dimensional space reconstruction method according to claim 7, wherein the predetermined number is eight. 10. Examining only the vicinity of a given voxel surface and detecting an object near any of the surfaces,
10. The three-dimensional space reconstruction method according to claim 7, wherein it is determined that the voxel and the target object overlap. 11. The three-dimensional space reconstruction method according to claim 10, wherein a sample voxel is generated by sampling a part of the voxel near the surface, and a target object is detected based on the sample voxel. . 12. The three-dimensional space reconstruction method according to claim 11, wherein the sample voxel is any one of a plurality of voxels obtained by equally dividing a given voxel by a minimum voxel size.