WO2009124663A1

WO2009124663A1 - Semi-global correspondence search in stereo images

Info

Publication number: WO2009124663A1
Application number: PCT/EP2009/002228
Authority: WO
Inventors: Stefan Hahn
Original assignee: Daimler Ag
Priority date: 2008-04-08
Filing date: 2009-03-26
Publication date: 2009-10-15
Also published as: DE102008017834A1

Abstract

The invention relates to a method for determining correspondence of image points (p, p') in at least two stereoscopically produced images (1, 1'), wherein a calculation is performed for each pixel (p) of one of the images (1) of the costs (C(p,d)) of a dissimilarity in the intensities of the pixel (p) and of a potentially corresponding pixel (p') of the other image (1'), wherein the costs (C(p,d)) are accumulated along a number of one-dimensional paths (L) opening on the pixel (p), where that pixel is selected for producing a disparity map (D(p)) from the pixels (p') of the other image (1') considered to be potentially corresponding that has a minimal global energy comprising at least the costs (C(p,d)) of the dissimilarity, wherein the image (1) is divided into image segment of size (n+1)x(n+1) for determining the correspondences, wherein the costs (S(p,d)) accumulated in each of the one-dimensional paths (L) are stored for each nth line and each mth column, wherein one each of the image segments is loaded, wherein the accumulated costs (S(p,d)) stored for an edge of the image segment is loaded, wherein the costs (S(p,d)) accumulated in each of the one-dimensional paths (L) for an internal of the image segment are newly calculated.

Description

SEMI GLOBAL CORRESPONDENSE SEARCH IN STEREO IMPORTERS

The invention relates to a method for determining correspondences of pixels in at least two stereoscopically recorded images according to the preamble of claim 1.

The determination of correspondences of pixels, also called pixels, in stereoscopically recorded images is a standard problem of image processing. Numerous algorithms have already become known for solving this problem. To solve often restrictive assumptions are made, for. Epipolar Constraint, Ordering Constraint, Smoothness Assumption, Uniqueness Constraint. A common problem is the different brightness, also called intensity, of corresponding pixels in the stereoscopically recorded images. A

Correspondence formation in this case is made more difficult by the fact that global stereo methods usually use a pixel-based similarity criterion that reacts sensitively to different brightnesses. In (H. Hirschmuller, Accurate and Efficient Stereo Processing by Semi-Global Matching and Mutual Information, 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR ¹ 05) - Volume 2, pp. 807-814), transinformation (mutual Information) as a similarity criterion that compensates for global brightness variations. For depth calculation of input images in embedded real-time systems, the algorithm must be in programmable hardware or other specialized hardware, and external memory is added to this hardware. To keep the performance of the process high and the electrical power consumption low, the memory bandwidth must be minimized.

The invention is therefore based on the object to provide an improved method for determining correspondences of pixels in stereoscopically recorded images, in which a memory requirement is reduced.

The object is achieved by a method having the features of claim 1.

Advantageous developments of the invention are the subject of the dependent claims.

In the method for determining correspondences of pixels in at least two stereoscopically recorded images, a calculation of costs of dissimilarity is performed for each pixel of one of the images based on intensities of the pixel and a pixel of the other image regarded as potentially corresponding. Along a number of one-dimensional paths that flow into the pixel, the costs are accumulated. From the pixels of the other image considered as potentially corresponding, the one to create a disparity map is selected in which a global energy is at least minimizing the cost of dissimilarity. In the process, the image for determining the correspondences is subdivided into image sections of size (n + 1) x (m + 1) in an inventive manner. For further calculation, not all accumulated costs are stored, as is conventional in the art, but only the costs accumulated in each of the one-dimensional paths for every nth row and every mth column of the picture. The storage takes place for example in an external memory, while the calculation for example, in an FPGA. Subsequently, one of the image sections is loaded in each case. In this case, the stored accumulated costs which relate to an edge of the image section are loaded. The costs accumulated in each of the one-dimensional paths for an interior of the image section are recalculated.

Compared with the storage of all accumulated costs known from the prior art, the computation outlay increases by about a factor of 2, but the external memory bandwidth can be reduced by at least the factor m / 2 to factor m, so that less memory is required. With less memory installed, both the cost of the memory itself and the power consumption of the memory are reduced. The prerequisite is that an internal memory of a microprocessor or an FPGA, in which the calculation is performed, is sufficiently large for the calculation of all one-dimensional paths for the selected size of the image section. If necessary, adjust the size of the image section.

Embodiments of the invention are explained in more detail below with reference to drawings.

Showing:

Fig. 1 is a schematic representation of an image with a pixel and eight one-dimensional paths that open in the pixel, and

Fig. 2 is a diagram of a disparity of a pixel in dependence on a direction of the one-dimensional path.

The figure shows a picture 1 and a pixel p. The other image 1 'and the pixel p' regarded as potentially corresponding are not shown. By way of illustration can be Compare the method with the superimposition of the images 1 and 1 'and the shifting of the images 1, 1' relative to each other to determine a match in a pixel p, p ¹ .

The method is used to determine correspondences of pixels (pixels p, p ') in at least two stereoscopically recorded images 1, 1'. In this case, for each pixel p of one of the images 1, a calculation of the costs of the dissimilarity C (p, d) (= cost of disparity) to a pixel p 'of the other image I ¹ regarded as potentially corresponding is carried out. This occurs, for example, on the basis of intensities of the pixel p and of the pixel p 'of the other image I ¹ considered as potentially corresponding. In other words, the cost of disparity is the cost of matching p to d.

Along a number of one-dimensional paths L, which result from different directions r in the pixel p, an accumulation of the costs C (p, d) takes place. Here, the lowest cost C (p, d) is propagated along the one-dimensional path L, similar to dynamic programming (without traceability).

In FIG. 1, eight one-dimensional paths L are used. But it is also conceivable another number, for example, sixteen. The accumulated costs S (p, d) are determined according to the following formula:

S {p, d) = ΣL _r {p, d) [1] r

From the pixels p ^{1 of} the other image 1 'regarded as potentially corresponding, the one for creating a disparity map D (p) is selected in which a global energy is at least comprising the cost C (p, d) of dissimilarity. The global energy can too Strafterme Pl, P2 are included, which take into account the changes of adjacent disparities to each other, as is clear from Figure 2 and as shown in the following formula:

For example, a small penalty term pl in the determination of global energy is taken into account when the disparity d between adjacent pixels p, p 'varies slightly and a large penalty term p2, when an abrupt change of the disparity d between adjacent pixels p, p ¹ is present. This is also called a smoothness constraint.

The image 1 is subdivided into image sections of size (n + l) x (m + l) in order to determine the correspondences. For further calculation, only the costs S (p, d) accumulated in each of the one-dimensional paths L for every nth row and every mth column of the picture 1 are stored in an accumulated cost matrix, the complexity of the algorithm relating to the Time 0 (WHD) is (WHD - width, height, disparity rank, width, height, disparity range).

The storage takes place, for example, in an external memory, while the calculation takes place, for example, in an FPGA or a microcontroller. Subsequently, one of the image sections is loaded in each case. In this case, the stored accumulated costs S (p, d) which relate to an edge of the image section are loaded. The costs S (p, d) accumulated in each of the one-dimensional paths L for an interior of the image section are recalculated.

Reference sign list

1, 1 'image

C (p, d) Cost of dissimilarity d Disparity in aligned images, otherwise line parameters

D (p) disparity image, map

L one-dimensional path

P, p 'pixels

Pl Strafterm 1

P2 Strafterm 2 r direction

S (p, d) accumulated cost for a pixel

Claims

claims

1. Method for determining correspondences of

Pixels (p, p ') in at least two stereoscopically recorded images (1, 1'), wherein for each pixel (p) of one of the images (1) a calculation of costs (C (p, d)) of a dissimilarity based on Intensities of the pixel (p) and a pixel (p ^? ) Of the other image (I ¹ ) regarded as potentially corresponding, wherein along a number of one-dimensional paths (L) that terminate in the pixel (p), an accumulation of the costs (C (p, d)), wherein from the pixels (p ^? ) Of the other image (I ¹ ) regarded as potentially corresponding, the one for creating a disparity map (D (p)) is selected in which a global energy is minimal comprising at least the cost (C (p, d)) of the dissimilarity, characterized in that the image (1) for determining the correspondences is subdivided into image sections of size (n + l) x (n + l), the in each of the one-dimensional paths (L) accumulated costs (S (p, d)) for every nth row u and each mth column, each loading one of the image sections, loading the accumulated costs (S (p, d)) stored for one edge of the image section, the costs accumulated in each of the one-dimensional paths (L) (S (p, d)) are recalculated for an interior of the image section.

2. Method according to claim 1, characterized in that in the determination of the global energy a small penalty (Pl) is taken into account when the disparity (d) between adjacent pixels (p, p ¹ ) changes slightly and a large penalty term (P2 ) is considered if there is a sudden change in disparity (d) between adjacent pixels (p, p ¹ ).

3. The method according to any one of claims 1 or 2, characterized in that the costs (C (p, d)) along eight one-dimensional paths (L) are accumulated.