JP2500654B2 - Three-dimensional shape relative position estimation device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention measures the shape of an object from multiple points of view by means of a range data measuring device and connects the partial shapes of the object (hereinafter referred to as partial shapes) obtained from the respective points of view. The present invention relates to an apparatus for reconstructing the shape of an object by estimating the relative position between partial shapes using texture.

[0002]

2. Description of the Related Art As a main range data measuring method, there are a method using a stereo method and a range finder (Ogami et al., "Image Processing Handbook", Shokoido (1987). Either method can be acquired at one time. It is only a part (partial shape) of the object, and in order to reconstruct the shape of the whole object, it is necessary to measure the shape of the object from various directions and integrate the results. Although it is necessary to find the relative position between the two, it is difficult to find the relative position of the stereo camera or range finder.
Methods have been developed for estimating relative position from shape data. In each of these, the relative position is estimated from the overlapping area on the assumption that adjacent partial shapes have an overlapping area (common area).

For example, a method of approximating a shape obtained by a range finder by triangular patches and estimating a relative combination of the triangular patches to estimate the relative position (Robert Bergevin et al .: Estim).
aating the 3D RigTrans
rmation Between Two Range
Views of a Complex Objec
t, ICPR'92), and also divide the range data,
A method of estimating relative position by matching between divided regions (Kawai et al .: 3 from multi-view range data)
Dimensional shape restoration ", IEICE Technical Report 91-19 (1991), Pattern Recognition and Understanding Research Society of the Institute of Electronics, Information and Communication Engineers, using the texture on the surface of an object as a clue to find the overlapping area between partial shapes and match the position and orientation of the overlapping area. There is a method of obtaining a relative position by doing so (Maruya, Nemoto, Takashima: partial shape connection method for three-dimensional shape reconstruction, 1992 IEICE Spring National Convention).

[0004]

However, it may be difficult to estimate the relative position based only on the information about the shape. For example, the overlap region has a sharp change in curvature,
Or unless it includes features such as the presence of discontinuities,
There is a high possibility that the overlapping area is not uniquely determined or even if it is, it is affected by the noise included in the range data.

On the other hand, in the method using the texture, the problem that the relative position is not uniquely determined is unlikely to occur. However, the method described above has a constraint that the optical axis of the stereo camera must always be in a certain horizontal plane.

An object of the present invention is to provide a relative position estimating device which can perform stable relative position estimation by using a texture and has no restriction on the position and orientation.

[0007]

In order to solve the above-mentioned problems, the three-dimensional shape relative position estimating device of the first invention is
Data input means for inputting range data and texture data, and an inclination angle of the range data measuring device, coordinate conversion means for converting a coordinate system expressing a partial shape to eliminate the influence of the inclination of the range data measuring device, and a horizontal plane. Set
An intersection line calculating means for obtaining an intersection line between a partial shape and a horizontal plane, a vertical deviation setting means for setting a vertical deviation between the partial shapes, and an overlapping width for estimating an overlap between the intersection lines obtained by the intersection line calculating means. An estimating means; a relative position estimating means for estimating a relative position between the partial shapes on a horizontal plane; a connection error calculating means for calculating a connection error; and a minimum connection error selecting means for selecting a vertical deviation that minimizes the connection error. , Are provided.

The three-dimensional shape relative position estimating apparatus of the second invention converts the range data and the texture data, the data input means for inputting the inclination angle of the range data measuring apparatus, and the coordinate system expressing the partial shape. Coordinate conversion means for eliminating the influence of the tilt of the range data measuring device, intersection line calculation means for setting a horizontal plane to find the intersection line between the partial shape and the horizontal plane, and vertical deviation setting means for setting the vertical deviation between the partial shapes. When,
Intersection line overlap width candidate extraction means for extracting overlap width candidates between intersection lines, overlap width selection means for collating upper and lower overlap width candidates and selecting an overlap width with high consistency, and a horizontal plane between partial shapes It comprises a relative position estimating means for estimating the above relative position, a connection error calculating means for calculating a connection error, and a minimum connection error selecting means for selecting a vertical deviation that minimizes the connection error.

[0009]

Next, the present invention will be described with reference to the drawings.

The first invention will be described with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of the first invention. Referring to FIG. 1, the first aspect of the invention is a data input unit 11, a partial shape generation unit 12, and a coordinate conversion unit 13.
The intersection line calculation means 14, the vertical deviation setting means 15, the overlap width estimation means 16, the relative position estimation means 17, the connection error calculation means 18, and the minimum connection error selection means 19.

Next, the operation of this embodiment will be described with reference to FIGS. 1 to 8. In the present embodiment, the input data is processed in the order of arrows shown in FIG.

The data input means 11 measures and inputs various range data and texture data of the object.
At that time, the tilt angle of the range data measuring device at the time of measuring the range data is also input. FIG. 3 shows an example in which a stereo camera 31 is used as the range data measuring device.
In FIG. 3, a stereo camera 31 as a range data measuring device includes an inclinometer 32 for measuring an angle β formed by the optical axis of the camera and a horizontal plane, and an inclinometer 33 for measuring a rotation angle α about the optical axis of the camera. Is attached. In addition,
Range data obtained using this camera is represented by a viewpoint coordinate system (x1, y1, z1) with the camera as the origin.

The partial shape generating means 12 generates a partial shape from the range data. Therefore, the range data in the background part is erased by using the discontinuous part of the range data as a clue. Then, a surface is generated from the remaining range data to form a partial shape.

In the coordinate conversion means 13, in order to eliminate the difference between the measurement points of the angle α and the angle β when measuring the range data,
The partial shape represented by the viewpoint coordinate system (x1, y1, z1) with the camera as the origin is the angle α at the time of range data measurement.
And the angle β is zero, the coordinate system (z2, y2, z
Convert to 2). In Fig. 3, the coordinate system (x1, y1, z1)
And (x2, y2, z2) are shown. This conversion is described next.

In FIG. 4, o is the origin. In the coordinate system (x1, y1, z1), the horizontal plane is observed as a plane (abco) inclined by α with respect to the x1 axis and β with respect to the z1 axis. To make the plane abco horizontal by coordinate transformation, first rotate the z1 axis by an angle −α and then rotate the x1 axis by an angle γ (counterclockwise rotation is positive). And). Therefore, the coordinate transformation is

[0016]

[Equation 1]

## EQU1 ##

Note that γ is obtained as follows. In FIG. 4, a ′ is a point (sinα · tanβ, cosα · tanβ, obtained by rotating α by −α around the z1 axis.
1), and b ′ is a point obtained by rotating b by −α around the z1 axis. Similarly, c ′ is a point obtained by rotating c by −α about the z1 axis. Furthermore, the plane a′b′c′o may be moved to the (x1, z1) plane by the rotation of γ around the x1 axis.
If the intersection of a'b 'and the (y1, z1) plane is d,
The position of d is (0, cos α · tan β, 1), the line segment od
Has a length of (1 + cos2α · tan2β) 1/2. Therefore, sinγ = cosα · tanβ / (1 + cos2α · t
an2β) 1/2 cosγ = 1 / (1 + cos2α · tan2β) 1/2.

When the difference between the angle α and the angle β at the time of range data measurement is eliminated by the above coordinate conversion, an unknown component among the relative positions between the partial shapes is related to the vertical relative position h and the horizontal direction. The relative position is p, q, and the rotation is θ about the vertical axis (FIG. 5).

The intersecting line calculating means 14 sets a plurality of horizontal planes at equal intervals and obtains an intersecting line between the partial shape and the horizontal plane (FIG. 6). Accurate results can be obtained with a large number of horizontal planes.

The vertical deviation setting means 15 sets one positional deviation h between the partial shapes in the vertical direction within a predetermined range. The unit of vertical deviation is the interval between horizontal planes.

The overlap width estimating means 16 estimates the overlap width between intersecting lines having the same height in the vertical deviation set by the vertical deviation setting means 15. Then, the relative position estimating means 1
At 7, the relative position is estimated such that the estimated overlap areas are spatially coincident. The overlapping width estimating means 16 and the relative position estimating means 17 are the above-mentioned methods (Maruya, Nemoto, Takashima: partial shape connection method for three-dimensional shape reconstruction, 199.
2 years IEICE Spring National Convention) can be used.

More specifically, first, sample points are set at equal intervals (δt) along the intersection line, and the shape data and texture data (luminance values) there are sampled. Next, the cross-correlation of the texture data of the overlapping portion is calculated while changing the overlapping width between the segments on the same horizontal plane by δt (FIG. 7). Then, the overlapping width that maximizes the cross-correlation is obtained, and this is performed for all intersection lines on the horizontal plane that associate the sample points with each other. FIG. 8 shows an example in which the overlapping width is 4 and there is only one horizontal plane. In the figure, a1 and b1, a2 and b2, a3 and b3, a4 and b
4 is associated.

Next, the relative position (p, q, θ) of the partial shape is calculated so that the mean square of the distance between the associated sample points becomes the smallest.

The connection error calculating means 18 calculates the clearance (referred to as connection error) in the region where the partial shapes overlap, for each horizontal plane. First, in accordance with (p, q, θ) estimated by the relative position estimation means 17, a parallel movement with respect to the partial shape,
Rotate. The mean square of the distance between the sample points at that time is the connection error in the vertical shift. Here, it is determined whether or not the connection error has been calculated for all the vertical deviations within the set range. If there is an uncalculated portion, the vertical shift h is changed by a constant value (the interval between horizontal planes), and the process returns to the vertical shift setting means 15. If all the connection error calculations have been completed, the process proceeds to the minimum connection error selection means 19.

The minimum connection error selection means 19 detects the vertical deviation that minimizes the connection error, and determines the vertical deviation h at that time and (p, q, θ) at that vertical deviation position as relative positions between the partial shapes. Presumed to be

The second invention will be described with reference to the drawings. FIG. 2 is a block diagram showing an embodiment of the second invention. Referring to FIG. 2, the second aspect of the invention is a data input unit 11, a partial shape generation unit 12, and a coordinate conversion unit 13.
, Intersection line calculation means 14, vertical deviation setting means 15, overlap candidate extraction means 21, overlap width selection means 22, relative position estimation means 17, connection error calculation means 18, and minimum connection error selection means 19. Composed of. The input data is processed in the order of arrows shown in FIG. The difference from the first invention lies in the overlap candidate extracting means 21 and the overlap width selecting means 22, so these two will be explained.

The overlapping candidate extracting means 21 of the second invention is
For each line of intersection, all overlapping widths at which the cross-correlation of texture data is maximized are extracted as overlapping width candidates. Then, the overlapping width selecting means 22 compares the overlapping widths between the upper and lower intersecting lines, and selects the overlapping width having the highest consistency. The processing in the overlapping width selection means 22 will be described in detail.
First, the sample points on the line of intersection that are vertically adjacent to each other are associated with each other. The sample points closest to each other are associated with each other in a one-to-one manner, but the lengths of the intersecting lines are usually different, so that there are sample points with no corresponding points at the ends of the intersecting lines. In FIG. 9, the intersection line 91
An example of the correspondence between the intersection line 92 and the intersection line 92 immediately below and the correspondence line 93 and the intersection line 94 immediately below the intersection line 93 is shown. Here, w1 is an overlapping width candidate at the intersecting lines 91 and 93, and w2 is an overlapping width candidate at the intersecting lines 92 and 94. Also, S1 is
It is the number of sample points at the left end of the intersection line 93 with no partner,
S2 is the number of sample points at the right end of the intersecting line 92 with no other party. In this case, w1 + S1 = w2-S
If the relationship of 2 holds, the overlapping width candidates w1 and w2
Are determined to be highly consistent. This consistency check is performed on intersection lines on all horizontal planes, and the overlapping width determined to be consistent on more horizontal planes is selected.

[0029]

According to the shape relative position estimating apparatus of the first invention, the texture of the partial shapes is used to detect the overlapping of the partial shapes, and the common portion of the two partial shapes is detected. The relative positions of the two partial shapes are estimated by matching the shapes of the common parts.

Therefore, the relative position can be determined even if there is no characteristic such as a rapid change in curvature or the presence of discontinuity. Further, since there is no restriction on the position and orientation of the range data measuring device, the blind spot and time and effort for measuring the range data are significantly reduced.

In the shape relative position estimating device of the second invention,
Since the consistency is checked in the overlap width estimation,
More accurate estimation can be performed.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of a first invention.

FIG. 2 is a block diagram showing an embodiment of the second invention.

FIG. 3 is a diagram showing a stereo camera and how to attach an inclinometer to the stereo camera.

FIG. 4 is a diagram showing a relationship between coordinate systems.

FIG. 5 is a diagram showing parameters representing relative positions between partial shapes.

FIG. 6 is a diagram showing a relationship between a partial shape and a horizontal plane.

FIG. 7 is a diagram showing overlap width estimation.

FIG. 8 is a diagram showing parameters representing relative positions between segments.

FIG. 9 is a diagram showing upper and lower correspondences between sample points.

[Explanation of symbols]

 11 data input means 12 partial shape generation means 13 coordinate conversion means 14 intersection line calculation means 15 vertical deviation setting means 16 overlap width estimation means 17 relative position estimation means 18 connection error calculation means 19 minimum connection error selection means 21 overlap width candidate extraction means 22 Overlap width selection means 91 Intersection line 92 Intersection line 93 Intersection line 94 Intersection line

Claims (2)

(57) [Claims] 1. A three-dimensional shape relative position estimation device for inputting range data and texture data of an object from a plurality of viewpoints by a range data measuring device and estimating relative positions between partial shapes of the object obtained therefrom. Data input means for inputting the range data and texture data, and the inclination angle of the range data measuring device, and coordinate conversion means for converting the coordinate system expressing the partial shape to eliminate the influence of the inclination of the range data measuring device, An intersection line calculation means for setting a horizontal plane and obtaining an intersection line between the partial shape and the horizontal plane, a vertical deviation setting means for setting a vertical deviation between the partial shapes, and an overlap between the intersection lines obtained by the intersection line calculation means. Of the overlap width, a relative position estimating means for estimating the relative position between the partial shapes on the horizontal plane, a connection error calculating means for calculating the connection error, and a minimum connection error. And a minimum connection error selecting means for selecting the vertical deviation. 2. An intersection line overlap width candidate extraction unit that extracts candidates for an overlap width between intersection lines instead of the overlap width estimation unit, and an overlap width candidate between upper and lower intersection lines are collated to check consistency. 3. The three-dimensional shape relative position estimating device according to claim 1, further comprising an overlapping width selecting unit that selects a high overlapping width.