JPH047805B2 - - Google Patents

Description

[Detailed Description of the Invention] (1) Description of the field to which the invention pertains The present invention relates to a stereo image matching processing method;
In particular, the present invention relates to a method for associating stereo images in which the depth (three-dimensional information) to an object in a scene is automatically determined by computer processing from images taken from a plurality of viewpoints by a camera.

(2) Description of conventional technology Many methods have been published to automatically obtain depth information using stereo methods, but none have achieved sufficient performance. Among these, the cross-correlation method, which finds corresponding points based on the cross-correlation value of the images in the window around each point in the left and right images, is used to If a viewpoint can be selected with a small ratio (ratio of depth to absolute value), it has the ability to withstand use, but in ground scenes and indoor scenes that are targeted by intelligent robots, the rate of change in depth is generally low. Large, step changes in depth often occur;
In such a case, there are many association errors and the performance is not sufficient.

Other typical methods include methods based on resolution hierarchy and depth continuity. This starts from a predetermined coarse resolution, gradually refines the resolution, stops processing at the predetermined resolution, and obtains the result. At each resolution, processing is performed based on the processing results of the previous stage. Specifically, line drawings corresponding to each resolution are obtained from the original image, and the intersection points of the left and right line drawings with a horizontal line at the same height (the camera's optical axis is parallel) are compared, and the right image corresponding to each point on the left image is calculated. The center of the search for the point is found from the previous processing result, and the corresponding point on the right image is found based on a search using a search width proportional to the resolution. However, although such a method has been improved by using hierarchy, it does not have sufficient matching performance.

In any case, this type of conventional method determines the corresponding points of the left and right images based only on the local information of the points, and is therefore unstable and prone to errors, and is not always suitable for wide-ranging scenes. also does not have sufficient performance.

(3) Purpose of the Invention In order to eliminate these drawbacks, the present invention aims to create a more stable connection that has more spatial extent and is less susceptible to noise, without directly linking images between points. Line components or segments that are part of them are associated with each other based on their overall characteristics, and based on the results, each point on the line is associated with each other, thereby determining the depth. Explain in detail.

(4) Description of structure and operation of the invention FIG. 1 is a diagram conceptually showing the arrangement of the stereo camera system considered in the present invention using a camera model. Here, the camera model grasps the image as an erect image. In the figure, 1 and 2 are the viewpoints of cameras 1 and 2 (the same applies hereafter), 3 and 4 are optical axes, 5 and 6 are image images, 7,
8 is the center of the image. However, the optical axis passes through the center of the image and is perpendicular to the image plane. 9 and 11 are the x-axes (x ₁ and x ₂ axes) of the image planes of camera systems 1 and 2;
12 is the y axis (y ₁ , y ₂ axis) of the image plane, 13 is a point on the target object, 14 and 15 are points on the image corresponding to object point 13 (image points), and 16 and 17 are image points 14 ,15
Epipolar line (Epipolar line or
Matching line). Here, the line segment connecting points 1 and 2 is called a base line, and the plane including the base line is called an epipolar plane, and the images of all points on the epipolar plane form one curve on each image plane. This is the above-mentioned epipolar line, and when the aberration of the lens is ignored, the epipolar line becomes a straight line. Epipolar lines 16 and 17 corresponding to the same epipolar plane are epipolar lines corresponding to each other. That is, the image point of camera 2 corresponding to the image point 14 of camera 1 is on the epipolar line 17. The present invention uses this property. Each epipolar line is a rotation angle of the corresponding epipolar plane (a signed plane angle with a plane that passes through the base line and is fixed relative to the camera system; for example, it may include one optical axis as the reference plane. ) is characterized by This rotation angle is named the "generalized height" of the image point.

Generalized height means that the optical axes of the left and right cameras are parallel, the focal length of both cameras is the same, the straight line connecting the optical centers of both cameras is perpendicular to both optical axes, and the imaging planes of both cameras are exactly rectangular. When the sizes are the same and both horizontal axes (x-axes) are parallel, it is defined as the y-coordinate of the imaging plane of each camera. It is equivalent that the points on the left and right images satisfy the epipolar constraint and that the generalized heights are equal. The fact that the left and right image points satisfy the epipolar constraint means that both image points lie on a single plane passing through the viewpoints of both cameras, which means that both image points originate from the same object point. This represents the necessary conditions for the point to be a point on the left and right images caused by the light. Even in the case of an image pair during convergence vision (a more general case where the optical axes are not parallel), if you convert it to an image of a virtual frame with parallel optical axes, the generalized height is equal to the y-coordinate of each frame. Become something.

The generalized height will now be explained with reference to FIG. 1b. Figure 1b is a projection view looking in the direction of point 1 from point 2 on a plane perpendicular to the base line (line segment passing through points 1 and 2), and point 18 is obtained by projecting the base line. point, and the straight lines 19 and 20 respectively correspond to the optical axis 3.
is a straight line obtained by projecting a plane passing through the optical axis 4 and the base line, the straight line 21' is a bisector of straight lines 19 and 20, and the straight line 22' is a plane passing through the object point 13 and the base line. This is a straight line obtained by projecting . At this time, the generalized height is defined as y _g =ftan using the (signed) angle of line segment 22' with respect to line segment 21'. However, f is the image focal length of the camera, and the generalized height is equal to the coordinate (height) of the point y on each image when the optical axes are parallel.

When the optical axes of both cameras are parallel and the x-axis of each image is parallel to the baseline, the corresponding image points 14 and 15 have the same height (y-axis value). Also between points 1 and 7 and between points 2 and 8
The distance between represents the focal length.

FIG. 2 is a block diagram showing the configuration of an embodiment of the present invention. One of two black and white images (two-dimensional pixel density array) taken by a camera (optical camera, television camera, etc.) to determine depth is named the left image and the other is named the right image. However, it is assumed that the optical axes of both cameras are parallel to each other, the left and right image planes are on the same plane, and the x-axes of both image planes are parallel to the base line. In the figure, 21 and 22 are a left original image input device, a right original image input device, 23 and 24 are a left line drawing extraction circuit, a right line drawing extraction circuit, 25 is a parallax offset detection circuit, and 2
Reference numerals 6 and 27 represent a left image segment extraction circuit, a right image segment extraction circuit, 28 a left and right segment correspondence circuit, 29 a left and right image feature point correspondence circuit, and 30 a depth calculation circuit.

Here, the original image input devices 21 and 22 are, for example,
A combination of a TV camera, AD converter, and frame memory, or a flying spot scanner or drum scanner that inputs prints, positive film, or negative film created from a camera, and AD.
It consists of a combination of a converter and a frame memory, etc. The left and right line drawing extraction circuits 23 and 24, for example, perform threshold processing on the result of applying a discrete Labrasian in units of 3×3 pixels to the original image, and then binarize the result.
The result was subjected to line thinning processing to fit the line into a line with a thickness of 1. Note that the above-mentioned discrete Laplacian may be considered to be processed as follows.

U _i,j =S _i+3,j +S _i-3,j +S _i,j+3 +S _i,j-3 −4S _i,j S _i,j ≡ _i+1 〓 ^k=i-1 _{j+ 1} 〓 ^l=j-1 Z _k,l Here, Z _K,l represents the density (brightness) at the pixel (k, l) (k, l are positive integers) of the image before applying the Laplacian operator, and U _{i ,j} represents the value at pixel (i, j) of the image after applying the Laplacian operator. In particular, here, when U _i,j < 0, it is corrected to U _i,j = 0 so that the Laplacian operator processing result is non-negative. That's how it is.

The "parallax offset" in the parallax offset detection circuit 25 represents the shift amount by which the images should match as a whole, and the difference between the left original image and the right original image (as a whole)
It is determined as the amount of shift that maximizes the cross-correlation.

A "segment" in the segment extraction circuits 26 and 27 for left and right drawings is defined as a portion between any of the following points among the line components of the line drawings with essentially a thickness of 1 obtained from the circuits 23 and 24. think. That is (1)
It is considered to be the part between the end point, (2) the branch point, and (3) the extreme point (the point where the height (y coordinate) on the screen is maximum or minimum when tracing the line). A conceptual diagram of the segment is shown in Figure 3. Figures 3a and 3b show how the left and right line drawings are decomposed into segments. In the figure, white circle 41
~56 represents an end point, a branch point, or a y-coordinate value extreme value point, and the part 57 between the white circles
~69 are segments. In the left and right image feature point correspondence circuit 29, any point on the line component (“feature point”)
), and the feature points on the single segment or composite segment of the matched left and right images that are at the same height are matched. The depth calculation circuit 30 determines the depth Z corresponding to the associated feature point, which is calculated by the formula Z=f·B/(x _l −x _r ). However, the Z axis that measures depth Z lies within the plane that includes the optical axes of both cameras, and the origin is the midpoint of the line segment that connects the viewpoints (object-side principal points) of both cameras, and the axis perpendicular to that line segment is It is. In other words, it is the depth seen from the intermediate position between both cameras. In the above formula, f
is the focal length of the camera, B is the base line length, the distance between the object-side principal points of both cameras, and x _l and x _r represent the x coordinates of the images of the corresponding feature points in the left and right images.

In the embodiment, the left and right segment extraction circuits 26 and 27 perform a raster scan of a line drawing having a thickness of 1 to detect untracked segments. If an untracked segment is detected, that segment is tracked. In tracking a segment, at each current point, check its 8 neighboring points counterclockwise and use the untracked black point as the next tracking point (black points represent points on the feature line, white points represent other points). , if the number of sunspots NB among the 8 neighbors of the current point is 3,
In addition, if the number NWB of point pairs that change from white to black when going around the 8 neighborhoods counterclockwise is 2, then (1) the next tracking point P _A is a non-4 neighboring point, and when viewed from the current point; If 8 neighboring points P _B adjacent to the next tracking point in the counterclockwise direction are untracked points, the next tracking point is set to P _B
(2) If "point P _B is a tracked black point" or "point P _B is a white point, and the 8 neighboring points of P _A one block clockwise from the current point are black points" , the state is corrected to no next tracking point. Then, if there is no next tracking point or the current point is not the start point of the current segment and a branch point (NB = 4 or NB = 3 and
If the point NWB=3) or the current point is the extreme value point of the y-coordinate value, the current point is determined to be the end point of the current segment, returns to the segment start point, and raster scan is restarted. This process is repeated.

The left and right segment correlation circuit 28 sweeps all left image segments, detects all right image segments that are corresponding candidates for each left image segment, and registers them. Thereafter, for each left image segment, one right image segment is determined from among the corresponding candidates as a corresponding partner.

Specifically, the correspondence candidate detection is performed as follows.
Sweep all left picture segments, and for each left picture segment, sweep all right picture segments. Take only the right image segment for which the absolute value of the difference between the disparity with the left image segment and the offset value of the disparity is within the tolerance, and calculate the starting point (upper end) and ending point (of the right image segment and left image segment, respectively). The y value is compared with the lower end), and if both the upper and lower ends match, it is registered as a rank 1 candidate. When only one of the top and bottom ends matches, a composite segment is considered in which the segment on the shorter side of the mismatched end is joined to the segment that was originally directly connected to it. However, as this composite segment, only those whose y values change monotonically will be considered. The y values of the upper and lower ends of this composite segment and the single segment of the other party are compared, and if both the upper and lower ends match, it is also registered as a rank 1 candidate. If a composite segment that matches both the top and bottom ends is not found, the original right single segment (the left single segment is also single) is ranked 2.
Register as a candidate.

The concept of correspondence candidate extraction is conceptually illustrated using FIG. 3, which has already been described. Left image segment 57,5
9, 61, 62, and 63 correspond to right image segments 64, 66, 67, 68, and 69 as single segments. However, as single segments, the left image segments 58 and 60 have no counterpart in the right image segment. However, segment 65 can be taken as a candidate for the composite segment that combines 58 and 60. Therefore, according to the present invention,
It is possible to overcome the influence of noise in the left and right images (the right image does not have a branch point corresponding to the branch point 42 in the left image).

In determining the correspondence, a correspondence partner is determined from among the right image segments registered as candidates for each left image segment. If there is a rank 1 candidate, the only right image segment is determined as the corresponding partner by maximizing or minimizing a certain feature amount (for example, minimizing the absolute value of the difference between the disparity and the disparity offset).

A simulation experiment in which the method of the embodiment described above was actually programmed and executed using a digital computer will be shown below. I pulled up a push-button telephone on a desk and photographed it from two different perspectives.
The above-mentioned Laplacian (negative values are corrected to 0) is applied to the original image input into the computer in units of 3 x 3 pixels, and the results are thinned and the results are shown in Figure 4 a and b.
Shown below. The shooting conditions are that the same camera is moved, the optical axes are parallel to each other in both shooting conditions, the image planes of both cameras are on the same plane, and one side of the rectangular image frame is a plane that includes both optical axes. is parallel to Thinning is by Hilditch for 8 connections. FIG. 4a shows the left viewpoint, and FIG. 4b shows the right viewpoint.

FIG. 5 shows the result of associating the left line drawing (FIG. 4a) with the right line drawing (FIG. 4b). However, in the case shown in Fig. 5, the three-dimensional points corresponding to the depths obtained from the corresponding feature points of the left line drawing and the right line drawing are calculated from the left viewpoint (corresponding to Fig. 4 a) and the right viewpoint (corresponding to It is drawn as a feature point image obtained when viewed from a third viewpoint (corresponding to Fig. 4b) (“synthesized third viewpoint image”), and in fact, the third viewpoint is the same as the left and right viewpoints above. This is exactly the middle point of view. The tolerance in determining the consistency of the upper and lower ends of a segment is ±3 pixels.

Since Figure 5 is similar to Figure 4 a and b, it can be understood that the correspondence is correct, but in order to more quantitatively evaluate the correspondence results shown in Figure 5. FIG. 6 shows a line drawing (third viewpoint drawing) obtained by applying Laplacian and thinning to the original image directly photographed from the above-mentioned third viewpoint. As can be seen by superimposing and looking through the image shown in Figure 5 and the image shown in Figure 6, the feature points in Figure 5 are almost completely located on the feature lines in Figure 6. I understand. However, in the composite third viewpoint drawing, only one point is drawn for the same y-coordinate (discrete value) on the same segment, so a long horizontal line also corresponds to one point, and the horizontal line in Figure 6 appears to be the same point. Although it appears to be missing in FIG. 5, the feature point in FIG. 5, which is almost on the horizontal line shown in FIG. 6, is the corresponding point. From the above, it can be seen that the correspondence shown in FIG. 5 is a good result, with most, but not all, of the main line parts being perfectly matched.

Furthermore, in order to check the correctness of the absolute value of the depth obtained as a result of the correspondence, the calculated depth Z _c (unit: cm) at each of three points of several representative segments is shown in FIG. 7a. The numbers in circles in the figure indicate serial numbers of representative segments. The figure also shows the actual measured value Z _d (unit: cm) of the average depth of the portion corresponding to each representative segment. The actual measurement value Z _d is either a value directly measured with a tape measure or a value obtained from the measurement value only by geometric calculation, and the measurement situation is shown in Figure 7b (the numbers in circles are (corresponding to Figure 7 a). FIG. 7c is a diagram specifically showing the measurement points shown in FIG. 7b on the target object. FIG. 7a is a matching image obtained by photographing this figure from the right side. In the figure, is the connection between the vertical panel and the number check stand, is the exit part of the cord, is the cord part, is the edge of the stand on the other side of the handset (the back of the left end when viewed from the viewpoint), and button □5 is the push button. It represents the "5" position.

By comparing Z _c and Z _d in FIG. 7a, it can be seen that the depth values Z _c obtained by this association method match within the range of measurement accuracy. The greater the pixel precision when inputting images into a computer, the better the degree of matching will be.

In the above example, it takes 3 steps to obtain a line drawing from an original drawing.
Although a discrete Laplacian with averaging of ×3 pixels is used, a discrete Laplacian with averaging of other n×n pixels (n is arbitrary) may be used. Furthermore, instead of the discrete Laplacian, a Gaussian Laplacian obtained by applying the Laplacian operator (∂ ² /∂x ² +∂ ² /∂y ² ) to a two-dimensional Gaussian may be used, or a general linear, quadratic, or cubic A discrete differential operator such as the following or an equivalent thereof may be used.
Also, to obtain a line drawing, instead of applying a differential operator to the original image and then binarizing and thinning it (or extracting the center line), you can apply a second-order differential operator and then extract zero-crossing lines (and then thin the line if necessary). You can also obtain a line drawing by using Characteristic line drawings other than line drawings representing edges such as those described above can be used as feature line drawings.
segm-entation) resultant boundary line or any differential geometric feature line of the density topography of the image, it may be any line drawing that represents the characteristics of the original image, and it does not necessarily have to be thinning or median line extraction (Medial).
It is sufficient if the line thickness of the characteristic line drawing obtained without using Axis Transformation is essentially 1.

Segment extraction is performed by extracting end points of connected line components,
the part between the bifurcation points or extreme points of height.”
Any algorithm may be used as long as it can extract the segment defined by or something close to it. This algorithm may generally rely on a previous stage of feature line drawing extraction, particularly a thinning algorithm. In defining a segment, instead of the height extremum point (the point at which the next tracking point returns one pixel in the height direction), a pseudo-extremum point (the point at which the next tracking point returns i pixels in the height direction) It is also possible to take i=2, 3...)).

In the example of extracting correspondence candidates, candidates are extracted by dividing them into ranks 1 and 2, and the hierarchical nature of ranks 1 and 2 is taken into consideration in determining the correspondence.
You can change the rank structure to something other than this, or rank 1.
It is also conceivable to extract only the candidates of , and make correspondence decisions within that range. In addition, we are considering a single segment and a composite segment consisting of two segments as objects of correspondence, but it can be expanded to include a single segment and a composite segment consisting of up to n (n≧3) or any number of segments. It is also possible to target segments (however, the composite segment is such that the height changes almost monotonically). Furthermore, in general, it is also conceivable to associate the connected line components based on the structural features of the connected line components including the heights of the end points, branch points, and extreme points (with respect to height) of the connected line components.

In the correspondence determination of the embodiment, when there are multiple candidates (of rank 1 or rank 2), the one with the smallest difference between the disparity and the disparity offset is selected. (large) is fine. For example, it may be the maximum ratio between the width of the common height (y value) range where the left and right segments exist and the average width of the height range where each segment exists. Furthermore, at the stage of extracting correspondence candidates, it is conceivable to set the number of candidates to one as much as possible based on the structural information of the connected components and other characteristics, and to reject the determination when a plurality of candidates remain.

In the example, the optical axes of the cameras that photographed the images to be correlated are parallel to each other, the image planes of the cameras are on the same plane, and one side of the rectangular frame of the image (x
axis) is parallel to the plane containing both optical axes, but if the relative positions and orientations of both cameras are known, and the common part of the scene is sufficiently large, this condition is not necessarily met. There is no need to satisfy. In this case, the "height" used in the example when the optical axes are parallel (the height direction position of the image,
Use the above-mentioned "generalized height" instead of "height extreme point", "height of end point, branch point, height extreme point", etc. (same as y coordinate value) There is a need.

Although there may be two or more cameras with substantially the same characteristics, the method of the present invention can be applied to the correspondence between images from any two of them. Furthermore, a left image and a right image may be obtained by using one camera and photographing from different viewpoints.

It is contemplated that the method of the present invention may be applied not only to black-and-white grayscale images but also to color gradation images. In addition, the method of the present invention eliminates the possibility that characteristic lines of images such as edges, which are caused mainly through light reflection reflecting the shape and surface material of an object, are distorted due to grainy noise in photographs, electronic noise from television cameras, etc. It resists deformations such as bending, hitting, and branching, and correctly associates points on the feature line (named feature points). It utilizes the property that the direction of a point relative to the camera and its position on the image plane have a one-to-one correspondence based on the law of refraction of light.

Further, in FIG. 2 of the embodiment, only one direction of signal transmission is shown between the blocks in the figure, but it is also possible for signals to be fed back by lines in other directions. The results of step 28 may be fed back to the left and right line drawing extraction circuits to change their processing parameters, such as the binarization threshold.

(5) Explanation of Effects As explained above, according to the present invention, the correspondence between points on the feature line is reliably performed, and thereby depth information can be reliably obtained on the feature line. Unlike depth measurement methods using light projection such as the slit light irradiation method, this method does not have the limitation that it is difficult to use in a bright room, and there is no danger to humans due to light irradiation, which may cause discomfort or annoyance to the human subject. It has the advantage of being versatile and can be used in coexistence spaces with humans. Therefore, in vision for general-purpose intelligent robots, the distance to the object's main feature points can be obtained, the average distance to the object can be found, and the object can be identified and understood using the distance to the main feature points and top-down knowledge. Furthermore, by interpolating the depth at the main feature points of an object to the entire object plane, it can also be used for more advanced understanding by reproducing the shape.

[Brief explanation of drawings]

Fig. 1 is a conceptual diagram of a stereo camera system, Fig. 2 is a flow chart showing the configuration of the present invention, Fig. 3 is a conceptual diagram illustrating the decomposition of a line drawing into segments and the correspondence between segments, and Fig. 4 a The left line drawing of the telephone scene in the simulation experiment, and FIG. 4b also shows the right line drawing. Figure 5 shows the third composite result of mapping the line drawings in Figure 4 using the mapping method of this example.
Figure 6 shows the feature points obtained directly from the original image at the third viewpoint, and Figure 7a shows the calculated value and direct measurement of the depth at the sample point based on the matching result. Figures 7b and 7c are explanatory diagrams showing values based on direct measurements. 1, 2...Viewpoints of camera No. 1 and 2, 3, 4...
Optical axis, 5, 6... image plane, 7, 8... center of image plane,
9, 11... x axis (x ₁ , x ₂ ), 10, 12... y
Axis (y ₁ , y ₂ ), 13... Point on target object, 14,
15... Image points (or image points) of cameras No. 1 and 2 corresponding to object point 13, 16, 17... Epipolar line, 21, 22... Left and right original image input devices, 2
3, 24... Left and right line drawing extraction circuit, 25... Parallax offset, 26, 27... Left and right image segment extraction circuit, 28... Left and right segment correspondence circuit, 29... Left and right image feature point correspondence attached circuit, 30
... Depth calculation circuit, 41-56 ... Any point among end points, branch points, and height extreme points, 57-69 ...
segment.

Claims (1)

[Claims] 1. Among a plurality of images of the same scene taken from different viewpoints using an image input optical device,
For two images, characteristic line drawings are extracted from both images, and in each connected line component in the characteristic line drawings, it is assumed that the end points, branch points, and optical axes of the above-mentioned different viewpoints are parallel. Extract segments separated by the maximum value point or minimum value point for the generalized height corresponding to the y-coordinate on each image, and extract the upper and lower end points of the segment in the left and right images for the two images. The correspondence between the segments of the left and right images is performed based on the information on whether the generalized heights of Based on the depth Z corresponding to the point on each segment, Z = f・B/(x _L − x _r ), where f is the focal length of the image input optical device, and B is the baseline length x _L and x _r correspond to each other. A stereo image mapping method characterized in that the x-coordinate of a point image is determined. 2. As a method for associating segments, a composite segment consisting of one or more segments, which does not include any branching, and whose generalized height changes almost monotonically, is compared between the left and right images. Claim 1, characterized in that the correspondence between the segments of both images is determined based on whether the generalized heights of the upper and lower ends of the single segment or composite segment of both images match. The described stereo image mapping processing method.