JP3106036B2 - 3D information extraction method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for extracting three-dimensional information, and more particularly to a method for constructing a model of a feature point in a three-dimensional space in a computer by image processing. The present invention relates to a three-dimensional information extraction method used for visual recognition of an environment in a computer.

[0002]

2. Description of the Related Art Extracting three-dimensional information from a plurality of images
The best known method is stereo
Is the way. FIG. 9 is the Journal of the Institute of Television Engineers of Japan, Vol. 38,
No. 9 (1984) "3D visual information processing
Trends ". In FIG.
For simplicity, the position of the image is
On the other hand, it is drawn at a point symmetrical position with respect to the lens center. FIG.
, The distance between the lens centers is L,
When the distance to the image plane is f, the left and right optical axes are parallel.
Then, the depth d of the point P on the target is the position on the left and right images.
Mark each (X _L, Y_L), (X_R, Y_R)
If d = L · f / (X_L-X_R).

[0003] The above-mentioned method can determine the depth to an object by a very simple formula. However, when the number of feature points on an image increases, it is extremely difficult to determine a pair of corresponding points in the left and right images. There is a disadvantage that it becomes difficult, and it is known as a corresponding point problem in stereoscopic vision.

As a method of avoiding the corresponding point problem, a method using a larger number of images is disclosed in IEICE Technical Report Vol. 91, No. 478 pattern recognition
Understanding PRU 91-128, "A method for extracting three-dimensional information by voting cone-shaped eyes" (February 21, 1992) has been published.

FIG. 10 is a diagram for explaining the principle of the above-mentioned proposed method. In FIG. 10, I _i indicates the i-th image, F _j indicates the j-th feature point of the object, and f
_ji indicates the position of the feature point f _{j in} the i-th image, and W
Represents a target space in general, V represents a voxel space representing the same space as W in a small cubic mesh, and v _k represents a k-th element of the voxel space.

Next, the principle of the method shown in FIG. 10 will be described. The camera moves along the path Ω and sequentially
get _i . Next, feature points f _ji are extracted from the image, and a straight line connecting the projection center and the feature point when the image is obtained is calculated for each feature point. In FIG. 10, this straight line is indicated by a dotted line. Next, +1 voting is performed for each element in the voxel space where the straight line intersects. Assuming that n images are obtained and the feature points F _j are reflected in all the images, a voxel including F _j obtains a vote point n. Other voxels may also get some votes, but it is clear in principle that voxels containing F _j will get the highest votes. Therefore, the same voting process is performed even when there are many feature points, and voxels with high votes are extracted. Original information can be extracted.

[0007]

As described above, the new method that replaces stereoscopic vision is excellent in avoiding the problem of correspondence between images, but has the following problems.

FIG. 11 is a diagram for explaining a problem of the prior art, and FIG. 12 is a diagram showing an example of an image after extracting feature points of the image.

For example, as shown in FIG. 11, the target object is a cube, and the camera path Ω is set in a circular orbit centered on a cube obliquely looking down on the cube, and 36 images are taken each time the circular orbit is rotated by 10 °. An image shall be obtained. This means that images can be obtained from the entire circumference without deviation. It is assumed that feature points of the object are each ridge line, and all ridge lines are extracted from the image as feature points by an edge operator. FIG. 12 is an example of such an image.

As can be easily seen from FIGS. 11 and 12, four ridge lines belonging to the upper surface are observed in all 36 images. On the other hand, since the four ridge lines belonging to the lower surface may be hidden by the cube itself, only two are visible at the same time, and only 18 images are observed at most. In addition, the other four ridgelines that are always visible as vertical lines on the image are also hidden by the cube itself, and only three are visible at the same time, and are observed only in at most 27 images.

Therefore, when a voxel that has obtained 36 or more votes in the voting result as described above is extracted, only a voxel including four edges belonging to the upper surface is extracted. Therefore, in order to extract the voxels including the ridge lines belonging to the lower surface, if the voxels obtained with more than 18 votes are extracted, the voxels including all the ridge lines are extracted.
A voxel having a vote of 18 to 35 exists around a voxel having a vote point of 6, and the voxel is also extracted, so that the ridge line belonging to the upper surface is blurred. In addition, considering that a part of the target object may be hidden by the target object itself, it is difficult to determine how many voxels having more votes should be extracted from a general target object.

Therefore, a main object of the present invention is to provide a three-dimensional information extraction method capable of accurately extracting a voxel to which a feature point belongs even if the feature point is hidden by the object itself. is there.

[0013]

According to a first aspect of the present invention, there is provided an image pickup means, an image processing means, and a movement control means for processing a plurality of images of an object taken from different positions, and A three-dimensional information extraction method for extracting three-dimensional information, comprising the steps of: extracting a feature point from each image; calculating a straight line in a three-dimensional space connecting each feature point and a projection center of the image; Assuming a voxel that is a three-dimensional mesh in a three-dimensional space in which a voxel exists, a first voting process step of counting how many voxels intersect a straight line calculated from how many images in each voxel; A second voting process step for counting how many images have the largest value among the voxels intersecting the straight line of the calculation result in the number of images, and a first and a second voting process result Based comprises extracting voxels representing the three-dimensional position of the feature points.

According to a second aspect of the present invention, the plurality of images of the first aspect are provided with image numbers, and in the first voting processing step, the calculated straight lines are added to all the voxels intersecting the calculated straight lines. Voting is performed on the image numbers from which the feature points are extracted, and the vote value for each voxel is determined to be the number of different image numbers among the obtained votes. In the second voting step, all the voxels where the straight lines of the calculation result intersect are obtained. The image number from which the voxel with the largest vote value of each voxel in the first voting processing step is extracted, and the linear feature point of the calculation result is extracted only for the voxel located at the center among the maximum voxels To make the vote value for each voxel the number of different image numbers among the obtained votes.

[0015]

A three-dimensional information extracting method according to the present invention processes a plurality of images of an object taken from different positions, extracts feature points from each image, and connects each feature point to the projection center of the image. A straight line in the three-dimensional space is calculated, and in each voxel of the three-dimensional mesh assumed in the three-dimensional space where the object is present, the number of times that the voxel intersects the straight line calculated from how many images is counted. A second voting process for counting the number of images in which the first voting process result of each voxel has the maximum value among the voxels intersecting the straight line of the calculation result based on the result of the first voting process By extracting the voxels representing the feature points based on the results of the first and second voting processes, highly accurate and stable three-dimensional information can be extracted.

[0016]

FIG. 1 is a schematic block diagram of an embodiment of the present invention. In FIG. 1, a cube 1 as an example of an object
Is imaged by the television camera 2 as an imaging means. The image captured by the television camera 2 is stored in an image processing device 3
To be processed. The cube 1 is placed on a turntable 4 and its attitude with respect to the television camera 2 is changed.

The rotation position of the rotary table 4 is controlled by a rotary table controller 5. The image processing device 3 and the turntable controller 5 are controlled by a computer 6, and the computer 6 executes a process for extracting three-dimensional information of the cube 1.

FIGS. 2 to 5 are flow charts for explaining the operation of the embodiment of the present invention. In particular, FIG. 2 shows the overall flow, and FIG. 3 shows the steps shown in FIG. SP
FIG. 4 shows a specific flow of step SP2, and FIG. 5 shows a specific flow of step SP3.

Next, a specific operation of one embodiment of the present invention will be described with reference to FIGS. The television camera 2 shown in FIG. 1 captures an image of the cube 1 on the turntable 4, and supplies the captured output to the image processing device 3. The image processing device 3 processes the captured image and gives it to the computer 6.
The computer 6 outputs a command signal to the turntable controller 5 to rotate the turntable 4 by, for example, 10 °. By repeating this operation, the television camera 2 sequentially captures images of the cube 1 at different angles.

The computer 6 fetches each image signal from the image processing device 3 in step SP1 shown in FIG. 2 and extracts feature points. Then, a back projection line connecting the feature point and the projection center of the image is calculated, and in step SP2, for each voxel of the three-dimensional mesh assumed in the three-dimensional space where the cube 1 exists, the voxel is calculated from several images. The first voting process is performed by counting whether the line intersects the straight line. Further, in step SP3, based on the result of the first voting process, the number of images in which the first voting process result of each voxel has the maximum value among the voxels that intersect the straight line of the calculation result is determined. A second voting process for counting is performed. Further, in step SP4,
A voxel representing a feature point is extracted based on the first and second voting results.

The operation of each of the above steps will be described in more detail. The specific processing of step SP1 shown in FIG. 2 is shown in FIG. Step SP11 shown in FIG.
, The index variable i is initialized to 0. In step SP12, the image signal is read from the television camera 2 into the image processing device 3, and the image data image-
i. In step SP <b> 13, the image processing device 3 causes an edge operator for extracting an edge on the image, such as a zero-cross operator, to act on image-i, extracts the edge, that is, the coordinates of the feature point, and provides the same to the computer 6. This feature point coordinate data is stored in feature-
points-i.

In step SP14, the computer 6 sets f
A straight line connecting the position corresponding to the feature point coordinates obtained on the feature-points-i on the imaging surface and the lens center of the TV camera 2 is calculated, and the feature-lines-i is calculated.
And There are as many straight lines as the number of feature points extracted in step SP13, and it can be said that the feature points on the object 1 are somewhere on this straight line. Step SP15 is a process for imaging the object 1 from an angle different by 10 °,
The computer 6 issues a command to the rotary table controller 5,
The turntable 4 is rotated by 10 °. Accordingly, in step SP16, the index variable i is incremented. In step SP17, it is determined whether or not the index variable i has become 36. If the index variable i is not 36, the process returns to step SP12, and repeats the processing of steps SP12 to SP16, and the index variable i becomes 0 to 35. Repeat the process until
The operation of step SP1 ends.

Next, the first voting process in step SP2 will be described in more detail with reference to FIG. First, in step SP21, all first counters (existing by the number of voxels) associated with each voxel in the voxel space assumed on the turntable 4 are cleared, and the first voting process is initialized. Perform processing. The result of the first voting process is counted by the first counter.
In step SP22, the index variable i is initialized to 0. In step SP23, the feature-lines-i obtained in step SP14 described above.
The intersection of each straight line with each voxel is checked, and a voxel that intersects even one straight line is marked with a passage. In step SP24, the first counter of the voxel with the passing mark is incremented by +1 to clear the passing mark.

In step 23, a pass mark is added without directly incrementing the first counter, and the first counter is incremented in step SP24. This is because there is a possibility that there is a voxel where a plurality of straight lines intersect. Even if a plurality of straight lines intersect, the number of votes under one image data, that is, under one i is increased only by one. That's why.

Step SP25 is processing for rotating the voxel space by 10 ° in calculation, and is preparation for processing data picked up from different angles by 10 °. This is a process only in the computer 6, and does not actually move. In step SP26, the index variable i is incremented. In step SP27,
It is determined whether or not the index variable i has become 36, and if not, the process returns to step SP23, and repeats the processing of steps SP23 to SP26 described above. If the index variable i has been processed from 0 to 35, step S
The operation of P2 ends.

Next, the second voting process in step SP3 will be described in detail with reference to FIG. In step SP31, all the second counters (existing by the number of voxels) associated with each voxel in the voxel space assumed on the rotation table 4 are cleared, and the initialization process of the second voting process is performed. . The result of the second voting process is counted by a second counter. At the start of this process, the first counter holds the result of the first voting process.

In step SP32, the index variable i is initialized to 0. In step SP33,
Feature-l obtained in step SP14 described above.
For each straight line of ines-i, the maximum value mark is given to the voxel having the largest value of the first counter among all the voxels intersecting it. In step SP34, the second counter of the voxel with the maximum value mark is incremented by +1 to clear the maximum value mark. Note that the maximum value mark is added without incrementing the second counter in step SP33, and then the second counter is incremented in step SP34 because the first voxel of the same voxel in a plurality of straight lines is used. This is because there is a possibility that there is a voxel in which the counter of the maximum becomes a maximum value.
This is because the number of votes under one image data, that is, one index variable i is increased by only one.

Step SP35 is processing for rotating the voxel space by 10 ° in calculation, and is preparation for processing data picked up from 10 ° different angles. This is a process only in the computer 6, and does not actually move. In step SP36, the index variable i is incremented, and in step SP37, it is determined whether or not the index variable i has become 36. If the index variable i is not 36, the above-mentioned step SP3
3 and repeat the processing of steps SP33 to SP36. If the index variable i has been processed from 0 to 35, the processing of step SP3 ends.

As described above, the first voting process result and the second voting process result are held in the first counter and the second counter of each voxel, respectively. In the first voting process, all the voxels that intersect with the straight line connecting the feature point detected on the image and the projection center of the image are equally voted, and based on the result, the second voting process intersects with the same straight line. Voting is performed only for the most likely voxel among all voxels, that is, the voxel having the largest first voting result. In summary, from how many images the first voting process result shows how many feature points of the voxel were determined to be possible, and from how many images the second voting result appeared in the image The source of the feature point indicates whether or not it was determined to be that voxel. The vote value of the result of the first voting process is 36 at the maximum, and the result of the second voting process is equal to or less than the result of the first voting process of each voxel. The vote value of the first voting process result varies greatly depending on whether or not the feature point is hidden depending on the imaging direction of the object, but the vote value of the second voting process result is In the voxel representing a point, the value is close to or equal to the first vote value, and in other voxels, the value is zero or a value close to zero.

Then, returning to FIG. 2, voxels representing feature points are extracted in step SP4. That is, in each voxel, the result of the second voting process is divided by the result of the first voting process. If the value is, for example, 0.8 or more, it is assumed that the voxel is a voxel representing a feature point.

However, in the embodiment shown in FIGS. 2 to 5, extracting the voxel representing the feature point by back-projecting the target object from all directions is based on the vote of the first and second voting processing results. Although it is possible from the values, as shown in FIG. 8, when the target object is back-projected from a limited direction, voxels representing the feature points and voxels in the vicinity thereof are also extracted.

FIG. 8 (a) shows back projection straight lines L1 to L by using images in which one voxel space is replaced by a two-dimensional plane and one feature point P on the target object is picked up from different angles by 10 degrees.
8 is a state diagram obtained by subtracting 5, FIG. 8 (b) is a diagram showing the vote value of the first voting processing result from the state of FIG. 8 (a), and FIG. It is the figure which showed the vote value of the 2nd voting process result from the state of b). Note that the meshes shown in FIGS. 8A to 8C correspond to one of the voxel spaces.
One voxel is shown, and the position of each voxel is designated using alphabets from 1 to 9 vertically and a to g horizontally.

A pass point mark is given to a voxel passing through each of the back-projected straight lines L1 to L5 drawn in FIG. 8A, so that the result of the first vote processing as shown in FIG. 8B is obtained. The vote value is shown. For example, the vote value is 2 because two back projection straight lines L4 and L5 pass through the voxel 8c. Next, among the voxels through which each of the backprojected straight lines L1 to L5 passes, a voxel having the maximum vote value of the first vote processing result is voted for the maximum value mark, and the second mark as shown in FIG. Of the voting process result of the voting process. The voxels containing the vote value 5 are shown to be 4d, 5d, and 6d voxels, but the voxels containing the actual feature points P are only the 5d voxels. That is, even if the target object is back-projected from a limited direction and the second voting processing result is obtained, it is only possible to specify that voxels representing feature points exist in voxels distributed in a predetermined range. .

Another embodiment of the present invention for solving the above problems will be described. 6 and 7 are flow charts for explaining the operation of another embodiment of the present invention. In particular, FIG. 6 shows the overall flow, and FIG. 7 shows the specifics of step SP3 'shown in FIG. A simple flow is shown.

Hereinafter, the description of the same parts as those of the embodiment shown in FIGS. 1 to 5 will be omitted, and different parts will be described. 6, steps SP3 and SP4 in the flowchart shown in FIG. 2 are replaced with steps SP3 'and SP4', respectively.
In FIG. 7, steps SP33 and SP34 in the flowchart shown in FIG.
And SPA4.

Referring to FIG. 7, step S shown in FIG.
The second voting process in P3 'will be described.

From step SP31 to step SP32, all the second counters associated with each voxel in the voxel space assumed on the rotary table are cleared, and the index variable i is initialized to zero. . At the time when the process of step SP31 is started, the result of the first voting process is held in the first counter.

In step SPA3, the feature-lines-i obtained in step SP14 is obtained.
For each line, find all the voxels in which the value of the first counter is the largest among all the voxels intersecting with each other, and put the maximum center mark on the voxel located at the center of the largest voxel. . Step SPA4
At the second of the voxels with the largest center mark
Is incremented by one, and the maximum center mark is cleared.

After the maximum center mark is set without incrementing the second counter in step SPA3,
The reason why the second counter is incremented in step SPA4 is that when a plurality of backprojected straight lines from the same image are close to each other, a voxel whose first voxel counter has the maximum median value is determined. This is because there is a possibility that the number of votes under one image data, that is, one index variable i increases only in such a case.

In steps SP35 to SP37, the voxel space is rotated by 10 degrees, the index variable i is incremented, and the index variable i becomes 3
6 is determined. If the index variable i is 36, the process returns to step SPA3, and the processing from step SPA3 to step SPA36 is repeated. Thus, the process of step SP3 'shown in FIG. 6 ends when the index variable i is processed from 0 to 35.

Next, referring to FIG. 6, step SP4 '
Extracts a voxel representing a feature point. That is, in each voxel, if the number of votes obtained by the second vote processing is, for example, half or more of the number of images, the voxel is a voxel representing a feature point. Note that, instead of the feature point extraction method in step SP4 ', the feature point extraction method in step SP4 shown in FIG. 2 may be used.

[0042]

As described above, according to the present invention, a plurality of images of an object taken from different positions are processed to extract feature points from each image, and each feature point and the projection center of the image are extracted. Is calculated, and in each voxel of the three-dimensional mesh assumed in the three-dimensional space where the object exists, counts how many images the voxel intersects with the straight line calculated from how many images Second voting for counting the number of images in which the first count result of each voxel becomes the maximum value among voxels intersecting each straight line of the calculation result based on the result of the first voting process Since the processing is performed and voxels representing feature points are extracted based on the first and second voting processing results, accurate three-dimensional information with high accuracy can be extracted.

[Brief description of the drawings]

FIG. 1 is a schematic block diagram of one embodiment of the present invention.

FIG. 2 is an overall flowchart showing a three-dimensional information extraction method according to an embodiment of the present invention.

FIG. 3 is a step SP1 of the overall flow chart shown in FIG. 2;
It is a flowchart which shows the detail of.

FIG. 4 is a step SP2 in the overall flow chart shown in FIG. 2;
It is a flowchart which shows the detail of.

FIG. 5 is a step SP3 in the overall flow chart shown in FIG. 2;
It is a flowchart which shows the detail of.

FIG. 6 is an overall flowchart showing a three-dimensional information extracting method according to another embodiment of the present invention.

FIG. 7 is a step SP in the overall flow chart shown in FIG. 6;
It is a flowchart which shows the detail of 3 '.

FIG. 8 is a diagram for explaining a problem of one embodiment of the present invention.

FIG. 9 is a diagram for explaining a conventional three-dimensional information extraction method.

FIG. 10 is a diagram for explaining another conventional three-dimensional information extraction method.

FIG. 11 is a diagram for explaining a problem of the related art.

FIG. 12 is a diagram illustrating an example of an image after extracting feature points of the image, for explaining a problem of the related art.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Target object 2 TV camera 3 Image processing device 4 Rotary table 5 Rotary table controller 6 Computer

──────────────────────────────────────────────────続 き Continuation of the front page (58) Field surveyed (Int. Cl. ⁷ , DB name) G01B 11/24 G06T 1/00 G06T 7/00

Claims (2)

(57) [Claims] 1. An object comprising: an imaging unit for obtaining an image of an object; an image processing unit for processing the obtained image; and a movement control unit for controlling a relative positional relationship between the object and the imaging unit. A three-dimensional information extraction method for processing a plurality of images by imaging an object from different positions and extracting three-dimensional information of the object, wherein a feature point is extracted from each of the images, Calculating a straight line in a three-dimensional space connecting the projection center of the image and the projection center of the image.Assuming a voxel that is a three-dimensional mesh in the three-dimensional space where the object is present, the voxel is calculated from several images in each voxel. A first voting processing step of counting whether or not the line intersects the straight line, wherein the first voting processing result of each voxel has the maximum value among the voxels that intersect the straight line of the calculation result in a number of images. Second voting process steps, and the first and on the basis of the second voting process result, the step of extracting a voxel representing a three-dimensional position of the feature point, three-dimensional information extracting method of counting how. 2. The plurality of images are provided with image numbers, and the first voting step includes extracting feature points on the calculated straight line in all voxels where the calculated straight lines intersect. Voting the selected image numbers to make the vote value for each voxel the number of different image numbers among the obtained voting. The second voting processing step includes the steps of: The voxel having the largest vote value of each voxel in the first voting processing step is extracted, and the characteristic point on the straight line of the calculation result is extracted only in the voxel located at the center among the maximum voxels. Voting the image numbers that have been made, to make the vote value for each voxel the number of different image numbers among the obtained votes.
The method for extracting three-dimensional information according to claim 1.