CN103177451A - Three-dimensional matching algorithm between adaptive window and weight based on picture edge - Google Patents

Abstract

The invention discloses a stereo matching algorithm based on image edge self-adaptive window and weight. The algorithm first uses the image edge information to quickly and dynamically select the size of the support window; Change characteristics, a weight model that conforms to the probability curve is proposed; finally, combined with the color similarity constraint, the weighted color distance accumulation sum is used as the similarity measure, and the disparity is calculated point by point to obtain a dense disparity map. The algorithm of the invention can effectively reduce the matching noise, improve the matching accuracy of the edge area and the low-texture area, and realize fast and efficient stereo matching.

Description

Based on the self-adapting window of image border and the Stereo Matching Algorithm of weight

Technical field

The invention belongs to computer vision field, particularly a kind of based on the self-adapting window of image border and the Stereo Matching Algorithm of weight.

Background technology

Binocular stereo vision is a kind of computer vision system that obtains the scene three-dimensional information by imitating mankind's binocular vision characteristic.Binocular camera obtains scene information from different perspectives, according to the distance of disparity computation corresponding point to imaging surface, obtains depth perception and three-dimensional reconstruction.Binocular Stereo Matching Algorithm is the hot issue of research always.

At present, the Stereo Matching Algorithm of broad research mainly is divided three classes: based on the matching algorithm of unique point, based on the matching algorithm in zone with based on the matching algorithm of the overall situation.

Be based on the matching algorithm of the features such as angle point, edge based on the matching algorithm of unique point, realization character point range finding fast can't be satisfied dense disparity map three-dimensional reconstruction demand but the method only can realize sparse coupling.

Matching algorithm based on the overall situation is the search strategy of a globally optimal solution, use can obtain matching result more accurately based on the Global Algorithm of heredity, neural network and dynamic programming etc., present most accuracy rate priority algorithm all adopts the global registration algorithm, but it is slow to ask for the large speed of globally optimal solution difficulty, is difficult to satisfy practical application request.Be that neighborhood take two width image respective pixel carries out the method for similarity coupling as the coupling primitive based on the matching algorithm in zone, Region Matching Algorithm can realize that dense matching can greatly dwindle the scope of finding the solution again.

The reliability of zone similarity matching algorithm is affected by the size of selected support window: window is larger, and information is abundanter, and is better to low texture region and repeat region matching effect, but mistake matching rate complicated to details, the parallax discontinuity zone is higher; Window is less, and is better to parallax discontinuity zone matching effect, but texture region information is more inadequate, the mistake matching rate is higher to hanging down.Adopt the self-adapting window algorithm based on region growing, can choose the window of definite shape and size for each pixel self-adaptation in degree of depth discontinuity zone, improved the accuracy rate of matching result, but the computing complicated and time consumption such as seed is chosen, growth.Color information is incorporated regional Stereo Matching Algorithm, and the method can more be given full play to the effect of each channel information of coloured image, has more advantage from computing velocity and the explanation of reliability aspect based on the matching algorithm in zone.The adaptive weighting matching algorithm in color-based and space, each pixel in two windows is distributed respectively a weighted value with self window center point color distance and geometric distance correlation of indices, take absolute error as the initial matching cost, the normalization weighted calculation zone degree of correlation, this arithmetic accuracy is higher, but algorithm is complicated, calculated amount is larger.

Summary of the invention

The object of the present invention is to provide a kind of based on image border self-adapting window size, distance weighted based on geometric distance adaptive weighting, color-based, can take into account accuracy and runtime, can effectively reduce the coupling noise, improve degree of depth discontinuity zone and low texture region matching precision based on the self-adapting window of image border and the Stereo Matching Algorithm of weight.

The technical solution that realizes the object of the invention is:

A kind of based on the self-adapting window of image border and the Stereo Matching Algorithm of weight, comprise the following steps:

Step 1: use the Canny operator to ask for the edge to benchmark image;

Step 2: step 2, pointwise detects, and according to whether being the difference of edge and edge power, distributes different neighborhood window sizes, chooses three kinds of neighborhood window size M, N, O(M〉N〉O); Then the detected image edge, as judgment basis, if window center arranges support window and is of a size of O on strong edge, be N if window center on weak edge, arranges window size, is M otherwise window size is set; Put the model that assigns weight to the geometric distance of window center according to neighborhood, shown in (1),

$\mathrm{fw}(i,j)={\mathrm{a\ω}}^{f^S}---\left(1\right)$

In formula, (i, j) be the coordinate in window for neighborhood point, be this to the geometric distance of window center, a, s and ω are that weight regulatory factor: a is the amplitude regulatory factor, ω is exponential damping speed regulatory factor, ω is larger, and characteristic curve is more level and smooth; S is the kurtosis regulatory factor, and s is larger, and characteristic curve is narrower, s and ω acting in conjunction, scope and the weight coefficient in control core district;

Step 3 is calculated the color distance of every pair of corresponding element in neighborhood window matrix, and is used restraint with interceptive value, and color distance cw expression formula is suc as formula shown in (2),

$\mathrm{cw}((x_1,y_1),(x_2,y_2))=\sqrt{{(r_1-r_2)}^2+{(g_1-g_2)}^2+{(b_1-b_2)}^2}---\left(2\right)$

In formula, (r ₁, g ₁, b ₁) (r ₂, g ₂, b ₂) be respectively the RGB triple channel brightness value for 2, (x ₁, y ₁), (x ₂, y ₂) be the coordinate of corresponding element;

Step 4 multiplies each other color distance and distance weighting corresponding in neighborhood window matrix and add up, take limit add up in disparity range with hour as optimum solution, namely this parallax, skip to step 2, descends some coupling, until complete the entire image coupling, draw disparity map.

The present invention compared with prior art, its remarkable advantage:

Support window consistent size, the uniform regional Stereo Matching Algorithm of reference value, larger support window has more brightness to change to carry out reliable matching at low texture region, but has more error message in occlusion areas; Less window has better effect to the coupling of degree of depth discontinuity zone, but low texture region is not suitable for; And in window, each pixel has different reference values; Algorithm of the present invention is on the basis of the size of dynamically choosing support window according to the marginal information of image, cumulative and as similarity with color distance, this similarity introducing is met the weight model of probability curve characteristic, thereby rationally utilize match information, obtain dense disparity map.

Below in conjunction with accompanying drawing, the present invention is described in further detail.

Description of drawings

Fig. 1 is the variation characteristic schematic diagram of geometric distance weight fw of the present invention.

Fig. 2 is algorithm flow chart of the present invention.

Fig. 3 is SAD algorithm window size and error rate schematic diagram.

Fig. 4 is that algorithm parameter of the present invention is chosen and the error rate schematic diagram.

Fig. 5 is result of implementation and the invention process result contrast schematic diagram of Tsukuba image; (a) be the left figure of former figure, (b) be the standard disparity map, (c) be 9 * 9SAD arithmetic result schematic diagram, (d) be 15 * 15SAD arithmetic result schematic diagram, (e) be Yoon arithmetic result schematic diagram, (f) being arithmetic result schematic diagram of the present invention, is (g) 15 * 15SAD Mismatching point schematic diagram, is (h) algorithm Mismatching point schematic diagram of the present invention.

Fig. 6 is Middlebury database images result of implementation and the invention process result contrast schematic diagram; (a) being the left figure of Cones, is (b) Cones standard disparity map, be (c) algorithm of the present invention for the Cones result schematic diagram, (d) be the left figure of Venus, be (e) Venus standard disparity map, be (f) that algorithm of the present invention is for the Venus result schematic diagram.

Fig. 7 is that algorithm of the present invention is to the effect schematic diagram of embodiment image; (a) being the left figure of the embodiment of the present invention, is (b) the right figure of the embodiment of the present invention, (c) is the disparity map of the embodiment of the present invention.

Embodiment

As shown in Figure 2: the present invention is a kind of based on the self-adapting window of image border and the Stereo Matching Algorithm of weight, comprises the following steps:

Step 1: use the Canny operator to ask for the edge to benchmark image;

Step 2: step 2, pointwise detects, and according to whether being the difference of edge and edge power, distributes different neighborhood window sizes, chooses three kinds of neighborhood window size M, N, O(M〉N〉O); Then the detected image edge, as judgment basis, if window center arranges support window and is of a size of O on strong edge, be N if window center on weak edge, arranges window size, is M otherwise window size is set; Put the model that assigns weight to the geometric distance of window center according to neighborhood, shown in (1),

$\mathrm{fw}(i,j)={\mathrm{a\ω}}^{f^S}---\left(1\right)$

In formula, (i, j) be the coordinate in window for neighborhood point, be this to the geometric distance of window center, a, s and ω are that weight regulatory factor: a is the amplitude regulatory factor, ω is exponential damping speed regulatory factor, ω is larger, and characteristic curve is more level and smooth; S is the kurtosis regulatory factor, and s is larger, and characteristic curve is narrower, s and ω acting in conjunction, and scope and the weight coefficient in control core district, the probability curve feature is satisfied in the variation of geometric distance weight fw, as shown in Figure 1;

Step 3 is calculated the color distance of every pair of corresponding element in neighborhood window matrix, and is used restraint with interceptive value, and color distance cw expression formula is suc as formula shown in (2),

$\mathrm{cw}((x_1,y_1),(x_2,y_2))=\sqrt{{(r_1-r_2)}^2+{(g_1-g_2)}^2+{(b_1-b_2)}^2}---\left(2\right)$

In formula, (r ₁, g ₁, b ₁) (r ₂, g ₂, b ₂) be respectively the RGB triple channel brightness value for 2, (x ₁, y ₁), (x ₂, y ₂) be the coordinate of corresponding element;

Step 4 multiplies each other color distance and distance weighting corresponding in neighborhood window matrix and add up, take limit add up in disparity range with hour as optimum solution, namely this parallax, skip to step 2, descends some coupling, until complete the entire image coupling, draw disparity map.

Wherein, the concrete grammar that in step 3, interceptive value uses restraint is: propose to introduce upper limit interceptive value ctw, make up the deficiency of simple use similarity, shown in (3), select upper limit interceptive value, in formula, T is the intercept threshold value,

ctw＝min{cw,T} (3)

Wherein, step 4 is specially: on the basis of the size of dynamically choosing support window according to the marginal information of image, cumulative and as similarity with color distance, this similarity is introduced the weight model that meets the probability curve characteristic, at first the weighting color distance of calculation window element adds up and is SDC, as similarity, shown in (4).

SDC(x,y,d)＝sum{fw(i,j)×ctw[(x+i,y+j),(x+i+d,y+j)]} (4)

Then introduce the self-adapting window algorithm based on the edge, namely EAW, in the EAW+SDC mode, realize the regional Stereo matching of accuracy and runtime compatibility.

The effect of this patent can further illustrate by following result:

In order to test this patent Algorithm Performance and selected with reference to coefficient, this patent has carried out a large amount of embodiment analytical algorithms.The embodiment environment is notebook computer, and dominant frequency is Intel Core2Duo T81002.10GHz, and internal memory 2G, programming language are Matlab R2009a.

Use respectively SAD algorithm, Yoon algorithm and this patent algorithm to carry out Stereo matching to Middlebury database Stereo Matching Algorithm test pattern.Test pattern Tsukuba picture size is 384 * 288, and disparity range is 0～15, as shown in Fig. 5 (a).The standard disparity map contains 8 parallax grades as shown in Fig. 5 (b), it has ignored the parallax grade in the background.

Find out the optimum window size of SAD algorithm by embodiment, data as shown in Figure 3, data are from embodiment and Middlebury evaluating system, draw the SAD algorithm relatively hour window size be 15 * 15.This patent algorithm desired parameters is got by the embodiment test and appraisal, as shown in Figure 4.

(1) use the SAD algorithm, window size is selected 9 * 9 and 15 * 15, calculates parallax and auto adapted filtering gets disparity map as Fig. 5 (c) and (d);

(2) use the Yoon algorithm, the embodiment parameter is set according to its data-oriented fully, gets disparity map as shown in Fig. 5 (e);

(3) use this patent algorithm, selected strong edge window size is 7 * 7, and weak edge window size is 9 * 9, non-edge window size is 15 * 15, each factor a=10 in distance weighting, s=2, ω=0.94, interceptive value T=5, result of calculation is as shown in Fig. 5 (f).The statistical graph of Mismatching point is as shown in Fig. 5 (g) and Fig. 5 (h), and in figure, black color dots is Mismatching point, and gray area is that occlusion area does not include erroneous point, and white portion is correct coupling.

Qualitative analysis:

(1) through filtering, Fig. 5 (c) still has a lot of noises and mistake coupling, and Fig. 5 (f) has eliminated major part wherein, and the area of residual fraction also obviously dwindles, and this is that this patent self-adapting window method has made up the not obvious loss of learning that causes of texture;

(2) Fig. 5 (e) outline effect is best, Fig. 5 (c) and Fig. 5 (d) are very not neat, Fig. 5 (e) has the fat situation in border, but existing obviously improvement, profile is the intersection of parallax discontinuity zone and occlusion areas, illustrates that this patent algorithm has lifting to this regional matching effect;

(3) Fig. 5 (f) details keeps better, illustrates that this patent algorithm has reduced the loss of detail that causes because of the window amplification.

Quantitative test:

The accuracy rate aspect, through the system testing of Middlebury Online Judge, SAD algorithmic match error rate is about 20%, and this patent algorithm is reduced to 6.7%, at each regional matching effect, obvious lifting is arranged.Evaluation result is as shown in table 1, ratio with mistake matched pixel number and the regional total pixel number of the type represents the matching error rate, in table, n-occ represents the matching error rate of non-occlusion areas (non-occluded regions), all represents the error rate of global area, disc represents the error rate of degree of depth locus of discontinuity near zone (regions near depth discontinuities), and bad pixels represents the overall matching error rate.

Time aspect: SAD algorithm 6.6s consuming time, Yoon adaptive weighting algorithm (Yoon ' s Adaptive Weight, write a Chinese character in simplified form Yoon AW) time loss up to 1152.5s, this patent algorithm 7.5s consuming time, the method that self-adapting window method and weighting color distance are cumulative and replacement SAD estimates has been offset the calculated amount that part increases because of the weighted sum hyperchannel.

Table 1 embodiment interpretation of result

This patent algorithm is when promoting accuracy rate, and computing velocity is near initial matching cost function SAD, and is very competitive aspect taking into account in speed and accuracy.Other images in the Middlebury database are tested, also obtained matching effect preferably, as shown in Figure 6.

Result shows, this patent algorithm can effectively reduce the coupling noise, improves the matching precision of fringe region and low texture region, and matching speed is fast.

In order to check this patent Algorithm Performance, this patent has built the required hardware platform of Binocular Stereo Vision System experiment.Use this patent algorithm to carry out Stereo matching to the image that gathers.

Binocular Stereo Vision System that utilization is built gathers stereo-picture pair, and as shown in Fig. 7 (a) Fig. 7 (b), image resolution ratio is 2048*1536, and disparity range is about 150～220 pixels.Use this patent algorithm to carry out Stereo matching.The selected algorithm parameter: window size is 31 * 31,23 * 23,19 * 19, T=100, w=0.94, s=1.3.Obtain disparity map as shown in Fig. 7 (c).

Analyze above disparity map, this patent algorithm can effectively be realized the division of degree of depth level, and noise is few, and profile is more obvious.

Result shows, this patent algorithm can effectively be applied to the image that the embodiment system gathers, and the matching result noise is little, speed is fast.

Compare by theoretical analysis with to Middlebury database data, embodiment data, prove that the method has higher matching efficiency than conventional stereo matching algorithm (SAD, SSD, NCC) and self-adapting window method (Yoon AW).

Claims (3)

1. a stereo matching algorithm based on adaptive window of image edge and weight, is characterized in that, comprises the following steps: Step 1: Use the Canny operator to find the edge of the reference image; Step 2: Step 2, point-by-point detection, according to whether it is an edge and the strength of the edge, assign different neighborhood window sizes, and select three neighborhood window sizes M, N, O (M>N>O); then Detect the edge of the image, based on this, if the center of the window is on the strong edge, then set the size of the support window to O, if the center of the window is on the weak edge, then set the size of the window to N, otherwise set the size of the window to M; The model for assigning weights to the geometric distance from the domain point to the center of the window, as shown in formula (1),

In the formula, (i, j) is the coordinate of the neighborhood point in the window, which is the geometric distance from the point to the center of the window, a, s and ω are the weight adjustment factors: a is the amplitude adjustment factor, and ω is the exponential decay speed Adjustment factor, the larger the ω, the smoother the characteristic curve; s is the kurtosis adjustment factor, the larger the s, the narrower the characteristic curve, s and ω work together to control the range and weight coefficient of the core area; Step 3: Calculate the color distance of each pair of corresponding elements in the neighborhood window matrix, and constrain it with a truncation threshold. The expression of the color distance cw is shown in formula (2),

In the formula, (r ₁ , g ₁ , b ₁ )(r ₂ , g ₂ , b ₂ ) are RGB three-channel luminance values of two points respectively, (x ₁ , y ₁ ), (x ₂ , y ₂ ) is the coordinate of the corresponding element; Step 4: Multiply and accumulate the corresponding color distance in the neighborhood window matrix with the distance weight, and the optimal solution is when the accumulated sum within the limited parallax range is the smallest, that is, the parallax at this point. Skip to step 2 and perform the next point matching. Draw a disparity map until the entire image matching is completed. the 2. the stereo matching algorithm based on the self-adaptive window of image edge and weight according to claim 1, it is characterized in that, in described step 3, the concrete method that truncation threshold is restricted is: propose to introduce upper limit truncation threshold ctw, make up for simple Using the lack of similarity, as shown in formula (3), select the upper limit truncation threshold, where T is the truncation threshold, ctw=min{cw,T} (3) . 3. the stereo matching algorithm based on the adaptive window of image edge and weight according to claim 1, is characterized in that: described step 4 is specifically: on the basis of dynamically selecting the size of support window according to the edge information of image , taking the cumulative sum of color distances as the similarity, and introducing a weight model that conforms to the characteristics of the probability curve to the similarity, first calculate the weighted cumulative sum of color distances of the window elements, namely SDC, as the similarity, as shown in formula (4). the SDC(x,y,d)=sum{fw(i,j)×ctw[(x+i,y+j),(x+i+d,y+j)]} (4) Then, an edge-based adaptive window algorithm, namely EAW, is introduced to achieve regional stereo matching with speed and precision in the form of EAW+SDC. the

Images