JP3513219B2 - Corresponding point matching method and apparatus - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a corresponding point matching method and apparatus, for example, extracting a corresponding point between two images to obtain a parallax or depth, or a motion vector or speed from the image. It is suitable for use in the method and apparatus.

[0002]

2. Description of the Related Art Conventionally, different imaging arrangements (for example, two cameras having a predetermined base line length and a convergence angle) or different two imaging arrangements are used.
Determining corresponding points between two images obtained at time points or at different shooting positions (when using a single monocular camera), and obtaining depth (distance) information from the images based on their relative position vector or parallax. In addition, many methods for obtaining velocity vector (motion) information have been proposed.

Among them, the image is divided into blocks of a predetermined size, and the central pixel of the two blocks having the highest similarity based on the correlation between the blocks of the two images or the sum of squares of the brightness difference is the corresponding point. The method of extracting as is often applied.

Recently, among the proposed methods, the size of a divided block is set to be large at first and then gradually reduced to limit the corresponding point search range based on rough correspondence (Quam " Hierarchic
al Warp Stereo "Proc. of the
e DARPA Image Understandi
ng Workshop pp. 149-155 (19
84)).

Also, a correlation method (Kanade &
Okutomi "A stereo matchin
galgolithm with an adapti
ve window: Theory and expe
orientation, Proc. of International
onal Conference on Comput
er Vision, pp. 383-388, (199
0)) and so on.

[0006]

However, in the above-mentioned conventional example, the image in the divided blocks has a portion where the depth changes as seen from the camera or a portion where the velocity vector changes discontinuously in one image. However, there may be a part that is not shown in the other image. In such a case, there is a problem that a correct corresponding point cannot be obtained even if the corresponding point is estimated based on the correlation between these blocks.

In view of the above problems, it is an object of the present invention to enable block-based high-precision extraction of corresponding points between a plurality of images.

[0008]

According to the present invention, there is provided an extraction process for extracting respective edges or contour lines of a plurality of images, and a plurality of images for the respective images so as not to intersect the edges or contour lines extracted by the extraction process. Based on the degree of similarity between a block of one image and a block of the other image among the images divided into a plurality of pieces by the division processing of dividing into blocks, the corresponding points between the plurality of images are determined. Corresponding point determination processing is performed.

Another feature of the present invention is that
Extraction processing for extracting each edge or contour line of a plurality of images, division processing for dividing each image into a plurality of blocks so as not to intersect the edges or contour lines extracted by the extraction processing, and the division processing An estimation process of estimating a parallax or a motion vector of each point between the plurality of images based on a similarity between a block of one image and a block of the other image among the plurality of divided images, Subdivision processing for subdividing each image into a plurality of blocks based on the parallax or motion vector estimation value of each point, and corresponding points between the plurality of images based on the similarity between the subdivided blocks And the corresponding point determining process for determining.

[0010]

[0011]

Another feature of the present invention is that the extraction means for extracting the respective edges or contour lines of a plurality of images, and the extraction means for extracting each edge or contour line so as not to intersect with the edges or contour lines extracted by the extraction means. A dividing unit that divides an image into a plurality of blocks, and among the images divided into a plurality by the dividing unit, based on the similarity between a block of one image and a block of the other image, Corresponding point determining means for determining the corresponding points of.

Another feature of the present invention is that extraction means for extracting each edge or contour line of each of a plurality of images and each of the edges or contour lines so as not to intersect with the edge or contour line extracted by the extraction means. A dividing unit that divides an image into a plurality of blocks, and among the images divided into a plurality by the dividing unit, based on the similarity between a block of one image and a block of the other image, Of estimating the parallax or motion vector of each point, and a re-dividing means for sub-dividing each image into a plurality of blocks based on the parallax or motion vector estimation value of each point, and the sub-division And corresponding point determining means for determining corresponding points between the plurality of images based on the similarity between blocks.

[0014]

[0015]

[0016]

Since the present invention has the above technical means, each image is divided into a plurality of blocks centered on each pixel while not intersecting with an edge or a contour line extracted from each of the plurality of images. At the same time, the similarity of each block is detected, and the corresponding points are extracted from the detected similarities of each block. Therefore, the corresponding points can be extracted on a block basis.

[0017]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the corresponding point matching method and apparatus of the present invention will be described below with reference to the drawings. FIG. 1 is a flow chart for explaining a first embodiment of the corresponding point matching method of the present invention, and FIG. 5 is a block diagram showing a schematic configuration of an apparatus for carrying out the corresponding point matching method of the present embodiment. In the following embodiments, for convenience, a case will be described in which corresponding points between two images obtained by imaging with a camera arrangement having a predetermined convergence angle and a base line length are extracted.

As shown in FIG. 1, first, in the first step S1, the images from the left and right cameras (the left camera 1 _L and the right camera 1 _{R in} FIG. 5) are input to the image memory 2, respectively.
In step S2, edge extraction processing of each image is performed.

As the edge extraction method, a method of detecting the zero-cross point of the data obtained by performing the second derivative by the Laplacian operation after the convolution of a predetermined size of the Kaussian and the image is applied. Is not limited to a particular method.

In general, the edge extraction process causes unnecessary edges (due to noise in the image or factors specific to the method). In this embodiment, in order to remove such an unnecessary edge, the unnecessary edge removal processing is performed in step S3. The unnecessary edge removing process is a process for removing an unnecessary edge and removing or ignoring it when the length of the extracted edge is shorter than a predetermined value.

As another method relating to the above-mentioned unnecessary edge removal processing, the edge strength (for example, the sum of the absolute values of the stepwise space differential of the image after the low-pass filter | ∂I ^* / ∂x | + | I
^* / ∂y |, I ^* is the image after filtering) is below a predetermined level, it is considered as an unnecessary edge. Note that the above step S
The process of 3 may be omitted.

Next, in step S4, each pixel of the image is divided into blocks each having a fixed size. Then, in the next step S5, it is determined whether or not an edge exists in each of the blocks divided into a plurality of blocks, and if it is determined in step S6 that there is an intersection, the process proceeds to step S7, and the center image of the block and the edge are detected. The block size is reduced based on the distance between and so as not to intersect the edge, and then the process returns to step S5.

When it is determined that there is no intersection as a result of the determination in step S6, the process proceeds to step S8, and it is determined whether or not the process of dividing into blocks without intersection is completed. , And returns to step S4. Then, in step S4, the block size is reduced by a predetermined width to further determine the presence / absence of an edge, and the processing steps are repeated until there is no edge. In this way, all blocks centered on each pixel are redivided so that there is no edge intersection.

Then, when the process of dividing into blocks without crossing is completed, the process proceeds to step S9, and corresponding points are extracted by block correlation.

Next, a method of extracting corresponding points based on the similarity between blocks will be described. In the present embodiment, as a result of the above-described block division, the block size may differ depending on the pixel, but in order to cope with this, the similarity is calculated 2
The central pixels of the shapes of the two blocks extracted from one image are made to coincide with each other, and the overlapping portion in the state is performed. Now, let a block centering on a pixel (i, j) be “I ^k _{i, j} ” (k is an image number), and as a measure of similarity,

[0026]

[Equation 1]

[0027]

[Equation 2]

[0028]

[Equation 3]

[0029]

[Equation 4]

Etc. are used, but scales other than these are
You can use it, of course. However, C₁, C₂, C₃, C
_FourOf these, basically C₂, C_FourRepresents cross-correlation, and C
₁, C ₃Indicates between two blocks. Therefore, the correspondence
C to extract points₂, C _FourGive maximum value for
Eru Block I^R(I ', j') matches best
To do. Also, C₁, C₃For the
Rock I^R(I ', j') is the block I in the left image^L
Best match to (i, j).

Therefore, such a pixel combination ((i, j) and (i ', j')) is a corresponding point to be extracted.

As described above, FIG. 5 is a system configuration diagram of the stereoscopic information extraction system in which the processing unit of this embodiment is incorporated in the stereoscopic imaging system. In FIG. 5, 1 _L and 1 _R are left and right cameras, 2 is an image memory, 3 is a corresponding point extraction processing unit including the processing system shown in FIG. 1, 4 is a parallax or distance from the corresponding points, and an appropriate interpolation processing is performed. The shape restoration processing unit 5 that performs the process to restore the three-dimensional shape and the like is a monitor that displays the result.

FIG. 6 shows a block division process after step S3 when the process of this embodiment is applied to an actual image (cube). In the figure, the column of L is the image obtained by the left camera,
The R column shows the image obtained with the right camera.

In FIG. 6, (A) shows an edge image after the unnecessary edges are removed by the unnecessary edge removal processing in step S3 of the flowchart of FIG.

Further, (B) shows an image after being divided into blocks of a standard size in the standard block division of step S4 of the flowchart of FIG. 1, and the center of each block represents a representative point of the block. Actually, since blocks of the same size are set for each pixel, in general,
Although the blocks are overlapped with each other, for the sake of convenience, the blocks are shown so as not to overlap with each other.

Further, (C) shows the division without edge crossing obtained by performing each processing such as step S5 → step S6 → step S5 of the flowchart of FIG. 1 in a loop in the same manner as (B) described above. It is a figure. In this case, the block shape is rectangular or triangular (right triangle)
Becomes In particular, triangular blocks result from block division along the contour (edge) of a cube. Generally, a block having a shape including a part of the contour of the object is generated.

Next, a second embodiment of the present invention will be described with reference to FIG. FIG. 2 is a flow chart showing the processing procedure of the second embodiment of the present invention. Each step from step S1 to step S9 in FIG. 2 is the same as that of the first embodiment.

However, in this embodiment, in step S10, the parallax or motion vector estimation value between the blocks adjacent to the edge, that is, the difference (deviation) between the corresponding points is calculated.

In the next step S11, it is judged whether or not the difference (deviation) in the detected distances between corresponding points is larger than the reference value, and the edge is regarded as a shielding contour (or parallax edge, velocity edge). , The block division that sandwiches this is not changed. If it is larger than the reference value, the process proceeds to step S12, it is determined whether or not all corresponding points have been calculated, and if all are completed, the process ends.

On the other hand, if the result of determination in step S11 is less than the reference value, the edge is considered to be an intensity edge caused by a smooth pattern on the object surface, illumination distribution, etc., and the process returns to step S3. In this case, the block division that does not intersect the edge as described in the first embodiment is unnecessary, and the feature of the present embodiment is that the corresponding points are obtained by performing the block division including the pixels on the edge. . In step S10, the difference in the parallax gradient and the difference in the motion vector gradient at each point may be obtained as the deviation.

Next, a third embodiment of the present invention will be described with reference to FIG. FIG. 3 is a flowchart showing the processing procedure of the third embodiment of the present invention. As shown in FIG. 3, in the third embodiment, edge extraction processing (step S
2) and unnecessary edge removal (step S3), corresponding points are extracted based on edges or edge segments in step S4.

In step S4, corresponding points (including presence or absence of corresponding points) in the left and right images of points on the edge are obtained, and the distance (or parallax or motion vector) is calculated in step S5.

In the next step S6, step S of FIG.
If the distance obtained in 9 is larger than the reference value or if there is no corresponding point, the edge crosses the block when dividing the image into blocks, or a flag for prohibiting inclusion in the flag, or Perform the process to set the label.

Specifically, each pixel (i, j) has a label e (i, j), and is initialized to e (i, j) = 0 first, and a pixel for which a prohibition flag is set is e. (I, j)
= 1.

In the processes after step S6, the process is divided into blocks so as not to intersect the edges with the prohibition flag (steps S7, S8 and S1).
0) and, after that, extraction of corresponding points based on the similarity between blocks (step S12) follows. In particular, in this embodiment, the intersection determination in step S8 is made based on the value of the prohibition flag.

Next, a fourth embodiment will be described with reference to the flowchart of FIG. In this embodiment, in step S2, each pixel is divided into blocks with a predetermined size.
Next, in step S3, corresponding points are estimated based on the degree of similarity between blocks obtained by a predetermined scale as in the first embodiment described above.

Next, in step S4, the gradient of the distance between the corresponding points is calculated from the estimation in the neighboring pixels. In the next step S5, if the gradient value calculated in the previous step S4 is outside the reference range, it is considered that the parallax (or motion vector) in the pixel between the two images changes discontinuously, and The continuous label (prohibition flag) e (i, j) is set to 1 (e (i, j) is assumed to be initialized to 0 in advance).

Next, in step S6, the discontinuity in the block is judged. If the discontinuity of e (i, j) = 1 exists in the block with a predetermined size (length) or more, the discontinuity is determined. It is determined that there is a continuous portion, and the process proceeds to step S7.

In step S7, a process of reducing the block size by a predetermined method is performed, and thereafter, the process returns to step S3 and the process of discontinuity determination from the corresponding point estimation is performed again. Such processing is repeated.

Next, in step S8, it is determined whether or not there is a discontinuous portion in all the blocks. If there is a discontinuous portion, the process returns to step S2, the above-described processing is repeated, and finally the corresponding points are determined. obtain.

In the above embodiments, the block shape is basically a rectangle or square having m pixels vertically and n pixels horizontally. However, in the case of the present invention, the shape is not necessarily limited to these shapes, and may be an arbitrary polygon according to the shape of the discontinuous portion. However, in that case, it goes without saying that the center of the block (or the geometric center of gravity) is a pixel that represents that block.

Next, an example of the corresponding point matching device of the present invention will be described with reference to FIG. In FIG. 7, is an image memory, is a dividing means, is a divided image storage means,
Is an estimation means, is a determination means, is a re-division means, is a re-divided image storage means, is a corresponding point determination means, and is a monitor.

The image memory is a memory for fetching and storing a video signal inputted from the outside, and the image stored therein is divided into a predetermined number by the dividing means. Then, the image divided by the dividing unit is stored in the divided image storage unit.

For the divided images stored in the divided image storage means, the estimation means estimates the parallax or motion vector of each point between the plurality of images. This estimation is performed based on the similarity between the block of one image and the block of the other image, and is performed based on the parallax or motion vector of each point between the plurality of images.

The estimated value obtained by the estimating means is given to the determining means provided in the next stage. The determination means determines whether or not the gradient of the given estimated value falls within the reference range, and supplies the determination result to the subdivision means.

The subdivision means subdivides the divisional image stored in the divisional image storage means based on the determination result given from the determination means, and stores it in the redivided image storage means.

Corresponding points are determined by the corresponding point determining means in the re-divided image stored in the re-divided image storage means. The above-mentioned decision is made based on the similarity between the blocks, and the result is displayed on the monitor.

[0058]

As described above, the present invention divides each image into a plurality of blocks centered on each pixel while not intersecting with an edge or a contour line extracted from each of the plurality of images. At the same time, the similarity of each block is detected, and the corresponding points are extracted from the detected similarity of each block. Therefore, highly accurate corresponding point extraction can be performed on a block basis.

[Brief description of drawings]

FIG. 1 is a flowchart showing a processing procedure of a first embodiment of the present invention.

FIG. 2 is a flowchart showing a processing procedure of a second embodiment of the present invention.

FIG. 3 is a flowchart showing a processing procedure of a third embodiment of the present invention.

FIG. 4 is a flowchart showing a processing procedure of a fourth embodiment of the present invention.

FIG. 5 is a configuration diagram of a stereoscopic information extraction system to which the present invention is applied.

FIG. 6 is an explanatory diagram of a block division process (beginning and end).

FIG. 7 is a functional configuration diagram showing an outline of a corresponding point matching device of the present invention.

[Explanation of symbols]   Image memory   Dividing means   Divided image storage means   Estimating means   Judgment means   Subdivision means   Redivided image storage means   Corresponding point determination means   monitor

─────────────────────────────────────────────────── --Continued from the front page (56) Reference JP-A-3-291766 (JP, A) JP-A-5-174149 (JP, A) JP-A-2-238580 (JP, A) JP-A-7- 160664 (JP, A) (58) Fields surveyed (Int.Cl. ⁷ , DB name) G01B 11/00-11/30 G06T 7/00

Claims (4)

(57) [Claims] 1. An extraction process for extracting each edge or contour line of a plurality of images, and a division process for dividing each image into a plurality of blocks so as not to intersect the edges or contour lines extracted by the extraction process. , Among the images divided into a plurality by the above division processing,
A corresponding point matching method characterized by performing corresponding point determination processing for determining corresponding points between the plurality of images based on the degree of similarity between a block of one image and a block of the other image. 2. An extraction process for extracting each edge or contour line of each of a plurality of images, and a division process for dividing each image into a plurality of blocks so as not to intersect with the edges or contour lines extracted by the extraction process. , Among the images divided into a plurality by the above division processing,
An estimation process of estimating the parallax or motion vector of each point between the plurality of images based on the similarity between the block of one image and the block of the other image, and the estimated value of the parallax or motion vector of each point. Based on
It is characterized by performing a subdivision process for subdividing each of the images into a plurality of blocks, and a corresponding point determination process for determining corresponding points between the plurality of images based on the similarity between the redivided blocks. Corresponding point matching method. 3. Extraction means for extracting each edge or contour line of each of the plurality of images, and division means for dividing each image into a plurality of blocks so as not to intersect with the edges or contour lines extracted by the extraction means. , Of the images divided into a plurality by the dividing means,
A corresponding point matching device comprising: corresponding point determining means for determining corresponding points between the plurality of images based on a similarity between a block of one image and a block of the other image. 4. Extraction means for extracting the respective edges or contour lines of a plurality of images, and dividing means for dividing each image into a plurality of blocks so as not to intersect the edges or contour lines extracted by the extraction means. , Of the images divided into a plurality by the dividing means,
Estimating means for estimating the parallax or motion vector of each point between the plurality of images based on the similarity between the block of one image and the block of the other image, and the estimated value of the parallax or motion vector of each point. Based on
A re-dividing unit that sub-divides each image into a plurality of blocks, and a corresponding point determining unit that determines a corresponding point between the plurality of images based on the similarity between the re-divided blocks. A corresponding point matching device characterized by being provided.