# A Line-Based Adaptive-Weight Matching Algorithm Using Loopy Belief Propagation

Authors: Hui Li; Xiao-Guang Zhang; Zheng Sun
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In traditional adaptive-weight stereo matching, the rectangular shaped support region requires excess memory consumption and time. We propose a novel line-based stereo matching algorithm for obtaining a more accurate disparity map with low computation complexity. This algorithm can be divided into two steps: disparity map initialization and disparity map refinement. In the initialization step, a new adaptive-weight model based on the linear support region is put forward for cost aggregation. In this model, the neural network is used to evaluate the spatial proximity, and the mean-shift segmentation method is used to improve the accuracy of color similarity; the Birchfield pixel dissimilarity function and the census transform are adopted to establish the dissimilarity measurement function. Then the initial disparity map is obtained by loopy belief propagation. In the refinement step, the disparity map is optimized by iterative left-right consistency checking method and segmentation voting method. The parameter values involved in this algorithm are determined with many simulation experiments to further improve the matching effect. Simulation results indicate that this new matching method performs well on standard stereo benchmarks and running time of our algorithm is remarkably lower than that of algorithm with rectangle-shaped support region.


---

## Body

## 1. Introduction

Stereo vision is a fundamental technique for extracting 3D information of a scene from two or more 2D images. It is widely applied in robot navigation, remote sensing, and industrial automation. One of the key technologies of stereo vision is stereo matching, which produces a disparity map. The stereo matching algorithm can be classified into two broad categories: global-based and local-based algorithms.Global-based matching algorithms follow the energy minimization principle. First, an energy function is established, consisting of a data term and a smoothness term. Next, this function is minimized with a global optimization method. Dynamic programming [1], loopy belief propagation (LBP) [2, 3], and graph cut [4, 5] are usually employed to identify the minimum energy required for a global-based algorithm. Comprehensive global constraint information can produce a more accurate disparity map in a global-based algorithm.A local-based matching algorithm is a simple and effective method for stereo matching that is commonly used. An important underlying principle of local-based matching is that pixels in a support region have an approximately equal disparity. To satisfy this principle, it is very important to determine the support region size. The support region must contain enough pixels for intensity variation, and the support region must include only those pixels with the same disparity. Thus, the traditional, local-based matching method is prone to false matching for pixels from the depth discontinuities region, since those pixels are from different depths. To ensure that a local-based matching algorithm performs well in practical applications, various approaches have been proposed. For example, adaptive windows have been used to improve matching results. These methods search an appropriate support region for each pixel, greatly improve the performance of matching results, and outperform standard local-based methods [6–10]. However, it is difficult to search a support region with an arbitrary shape and size, and most of these methods have a high computational complexity. Other researchers assign different support-weights to the pixels in a support region, keeping the size and shape of a support region constant [11–13].In recent years, several methods for acquiring satisfactory effect of stereo matching have been adopted. Yang et al. [17] presented a stereo matching algorithm which integrates color-weight, belief propagation, left-right checking, color segmentation, plane fitting, and depth enhancement. Mei et al. [18] integrated the AD-census cost measurement function, the cost aggregation method based cross-based region, the scanline optimize method, the multistep refinement method, and the accelerative algorithm based on CUDA into their algorithm.The algorithm presented in this paper is inspired from adaptive-weight matching algorithm. In this paper, the aim is to propose a low computation complexity and high accuracy stereo matching algorithm. So the rectangle-shaped support region is substituted for the line-shaped support region. Lacking of enough pixel information is a main weakness of the line-shaped support region, which is easy to cause error matching. Adaptive-weight can make full of limited pixel information, by analyzing the characteristic of the adaptive-weight model proposed in [13] on disparity accuracy, we use neural network (NN) to determine the spatial proximity and mean-shift based segmentation method to effectively describe the color similarity.In addition, several approaches are applied to complete the algorithm. We develop a new pixel dissimilarity measurement function which combines Birchfield pixel dissimilarity measurement function and census transform to compute the matching cost. The loopy belief propagation method proposed in [2] is employed to estimate the initial disparity map, which is optimized with min convolution and image pyramid. There are several measurable improvements for the initial disparity map. To further improve the accuracy of the initial disparity map, iterative left-right consistency (LRC) checking and segmentation voting are used to refine the disparity map by analyzing the features of the initial disparity map.


## 2. Algorithm Description

The algorithm presented in this paper can be divided into two steps: a disparity map initialization step and a refinement step. The framework of the algorithm is shown in Figure1. A detailed description of this algorithm is given  in the following sections.Figure 1
Block diagram of our algorithm.


### 2.1. Adaptive-Weight Based Cost Aggregation Method

Assuming the two pixelsp and q, the disparity of center pixel p wants to be computed. S(p) is the support region of pixel p, while q is a neighboring pixel of p in the support region. The support-weight of q is assigned by the following according to [12]: (1)wp,q=fcΔcpqfcΔgpq,where fc(Δgpq) represents the spatial proximity, fc(Δcpq) represents the color similarity, and w(p,q) is the support-weight. Our algorithm is designed on the basis of this framework. The list of variables used in this paper is shown in the end of the paper.


#### 2.1.1. The Model of Line-Based Adaptive-Weight

Wang et al. [13] noted that when the support region is large enough, color similarity plays a major role in computing the center pixel disparity within a certain range. As shown in Figure 2, red represents the support region S(p). We used the pixels in S(p) to compute the disparity of p. The effects of spatial proximity can be neglected in the pale blue region according to [13]. We call this region the transition area, represented by T(p). To satisfy this principle, the neural network can be applied in the design of this spatial proximity model.Figure 2
The assumption of segmentation-based stereo matching.Figure3 shows the spatial proximity model established by neural network. The position of a pixel is the input, the spatial proximity is the output, and the connect weights are shown as in the figure. In fact, the distance x-xp is the input of neural network. To simplify the notations, suppose that the center point p is at xp=0, the distance x-xp can be simplified into x which represents the position of a pixel. The concrete form of the spatial proximity is expressed by (2)IM1=x+β,IM2=-x+β,OMi=fIMi,IT=∑i=12OMi-1.5,fcΔgpq=fIT,where f(x)=1/(1+e-αx) is the sigmoid function. Figure 4 demonstrates the varied trend of the spatial proximity according to the position of a pixel.Figure 3
Spatial proximity described by neural network.Figure 4
Spatial proximity proposed in this paper whenα=1, β=8, and Ls=15.In Figure4, the space between the two blue lines is the transition area and the support region is represented by the whole x-axis. It can be seen from Figure 4 that (1) the spatial proximity of pixel in the transition area is significantly greater than that of pixel in other area, which accords with the spatial proximity model of traditional adaptive-weight theory; (2) there is not much difference between these pixels in the transition area for the spatial proximity, which means that the influence of spatial proximity can be neglected.According to the segmentation-based stereo matching principle [14, 19], a new model of color similarity is established by the following in [20]:(3)fcΔcpq=1ifsegq=segpexp⁡-Δ2cpqγcotherwise.Equation (3) shows that color similarity contributes enormously to measure the dissimilarity between center pixel p and its neighbor pixel q when p and q belong to the same segmentation.That color similarity model based on image segmentation can achieve good performance, as introduced in [13]. Mean-shift is a nonparametric estimation iterative technique, and its application domains include computer vision, clustering, and image processing [21]. In this work, we use mean-shift as the segmentation method.


#### 2.1.2. Cost Aggregation

The matching cost of pixelp with disparity d is represented by(4)Ep,d=∑q∈Lp,q-d∈Lp-dwp,qwp-d,q-deq,q-d∑q∈Lp,q-d∈Lp-dwp,qwp-d,q-d,where p-d and q-d are the corresponding pixels of p and q, respectively, when the disparity of the center pixel is d.The pixel dissimilarity measurement functione(q,q-d) in (4) is very important for cost aggregation. The absolute difference and Birchfield function [22] are widely used in cost aggregation. To improve the matching accuracy of the textureless and repetitive regions, the pixel dissimilarity measurement function is described by combing Birchfield function and census transform:(5)eq,q-d=min⁡CBirchq,q-d,IR,IL,TBirch+min⁡CCensusq,q-d,TCensus.To validate the effect of this cost aggregation method, simulation results on Teddy and Cones with Birchfield method and our method are shown in Figure5.Figure 5
(a) Part of the origin image. (b) Disparity results which are computed with our cost aggregation method. (c) Disparity results which are computed with Birchfield pixel dissimilarity measurement function.
(a)
(b)
(c)


### 2.2. Initial Disparity Determination

The winner-take-all (WTA) searching strategy is a common method for determining disparity, which can be expressed by(6)Dp=argmin⁡dEp,d.WTA tends to produce a low accuracy disparity map. Therefore, we adopt an efficient LBP algorithm proposed in [2] in this paper. In this LBP algorithm, FFT convolution and image pyramid are integrated into LBP, which can effectively decrease the complexity of LBP and increase the matching effect. The flowchart of the initial determination procedure is shown in Algorithm 1.Algorithm 1:The procedure of initial determination procedure.
(1) Computing matching cost E by (4)
Initializing pyramid levell and down sampling factor η=0.5
(2) Pyramid initialization
Pyramid(1).cost = E
(3) Establishing pyramid structure with l and η
(4) For each level i
(5)  For each iteration j
(6)   Updating left, right, up and down direction message for each pixel
(7)  End
(8) End
(9) Determining disparity for each pixel by max-product principle


### 2.3. Disparity Refinement

It is inevitable that initial disparity maps will contain many error-matched pixels. To refine the disparity map, a two-step postprocessing method is put forward in this section.


#### 2.3.1. Left-Right Consistency Check

The disparity mapDL for the left image is computed by previous steps. The disparity map DR for the right image is computed in a similar manner. In [15, 17], pixels are classified into several types according to DL, DR, and ER to remove outliers. Then different strategies are designed for different type of pixels to determine its disparity.In this work, we analyzed the property of initial disparity map. Figure6 shows the distribution of bad pixels after executing the disparity initialization step of our algorithm for Tsukuba. It can be seen from this figure that most of the bad pixels concentrate in the occluded region. According to this result, most of the pixels match correctly and the initial disparity in the nonocc region should be trusted. Therefore an iterative left-right consistency check is proposed for handling this.Figure 6
The distribution of bad pixels for initial disparity map of Tsukuba. Bad pixels are marked with red points.Pixels can be divided into two types: undependable pixels and dependable pixels. Pixelp is classified as dependable when it meets the following condition:(7)DLp=DRp-DLp.Pixelp is considered to be undependable if it fits the following condition: (8)DLp≠DRp-DLp.The new disparity of the undependable pixel can be computed as in Algorithm 2.Algorithm 2:The disparity map after execution of left-right consistency checking.
(1)   Establishing the table of pixel type Sti according to (7)-(8)
(2)   St←Sti
(3)    For each iteration k
(4)     For each undependable pixel pi which is determined by St
(5)      Searching the nearest dependable pixel piL and piR
(6)       dpi←min⁡dopiL,dopiR //where do· represents initial disparity of pixel
(7)      If dpi≠dopi
(8)        Set pi as dependable pixel in St
(9)      End
(10)    End
(11)   End
(12)  EndFigure7 shows the result after the execution of iterative left-right consistency checking. Table 1 shows the detailed data for the role of iterative left-right consistency checking.Table 1
The error percentages in different region for disparity refinement step.
Nonocc
All
Disc
Initial disparity map
1.21%
3.20%
6.42%
Left-right consistency
1.17%
2.40%
6.30%
Segmentation voting
0.95%
1.62%
5.07%Figure 7
The disparity map after execution of left-right consistency checking.


#### 2.3.2. Segmentation Voting

The pixelwise region shown in Figure8 is established according to color consistency. This region can be represented by U(p). Pixels in U(p) satisfy the following condition:(9)Iq-Ip<τ,q∈Up,xq-xp<Lsv,yq-yp<Lsv.Figure 8
Pixelwise region for segmentation voting.LetH(d) represent the frequency distribution of disparity d in U(p). The new disparity is updated by Algorithm 3.Algorithm 3:Disparity determination of segmentation voting.
(
1) Hd←0
(2) For each q∈Up
(3)  For each d∈dmin⁡,dmax⁡
(4)   If d==DLq
(5)    HDLq←HDLq+1
(6)   End
(7)  End
(8) End
(9) DLp=arg⁡maxd⁡H(d)The3×3 median filter is applied to the left disparity map. Figure 9 shows the effect of segmentation voting on the accuracy of the disparity map.Figure 9
The disparity map of Tsukuba obtained by segmentation voting.


## 2.1. Adaptive-Weight Based Cost Aggregation Method

Assuming the two pixelsp and q, the disparity of center pixel p wants to be computed. S(p) is the support region of pixel p, while q is a neighboring pixel of p in the support region. The support-weight of q is assigned by the following according to [12]: (1)wp,q=fcΔcpqfcΔgpq,where fc(Δgpq) represents the spatial proximity, fc(Δcpq) represents the color similarity, and w(p,q) is the support-weight. Our algorithm is designed on the basis of this framework. The list of variables used in this paper is shown in the end of the paper.


### 2.1.1. The Model of Line-Based Adaptive-Weight

Wang et al. [13] noted that when the support region is large enough, color similarity plays a major role in computing the center pixel disparity within a certain range. As shown in Figure 2, red represents the support region S(p). We used the pixels in S(p) to compute the disparity of p. The effects of spatial proximity can be neglected in the pale blue region according to [13]. We call this region the transition area, represented by T(p). To satisfy this principle, the neural network can be applied in the design of this spatial proximity model.Figure 2
The assumption of segmentation-based stereo matching.Figure3 shows the spatial proximity model established by neural network. The position of a pixel is the input, the spatial proximity is the output, and the connect weights are shown as in the figure. In fact, the distance x-xp is the input of neural network. To simplify the notations, suppose that the center point p is at xp=0, the distance x-xp can be simplified into x which represents the position of a pixel. The concrete form of the spatial proximity is expressed by (2)IM1=x+β,IM2=-x+β,OMi=fIMi,IT=∑i=12OMi-1.5,fcΔgpq=fIT,where f(x)=1/(1+e-αx) is the sigmoid function. Figure 4 demonstrates the varied trend of the spatial proximity according to the position of a pixel.Figure 3
Spatial proximity described by neural network.Figure 4
Spatial proximity proposed in this paper whenα=1, β=8, and Ls=15.In Figure4, the space between the two blue lines is the transition area and the support region is represented by the whole x-axis. It can be seen from Figure 4 that (1) the spatial proximity of pixel in the transition area is significantly greater than that of pixel in other area, which accords with the spatial proximity model of traditional adaptive-weight theory; (2) there is not much difference between these pixels in the transition area for the spatial proximity, which means that the influence of spatial proximity can be neglected.According to the segmentation-based stereo matching principle [14, 19], a new model of color similarity is established by the following in [20]:(3)fcΔcpq=1ifsegq=segpexp⁡-Δ2cpqγcotherwise.Equation (3) shows that color similarity contributes enormously to measure the dissimilarity between center pixel p and its neighbor pixel q when p and q belong to the same segmentation.That color similarity model based on image segmentation can achieve good performance, as introduced in [13]. Mean-shift is a nonparametric estimation iterative technique, and its application domains include computer vision, clustering, and image processing [21]. In this work, we use mean-shift as the segmentation method.


### 2.1.2. Cost Aggregation

The matching cost of pixelp with disparity d is represented by(4)Ep,d=∑q∈Lp,q-d∈Lp-dwp,qwp-d,q-deq,q-d∑q∈Lp,q-d∈Lp-dwp,qwp-d,q-d,where p-d and q-d are the corresponding pixels of p and q, respectively, when the disparity of the center pixel is d.The pixel dissimilarity measurement functione(q,q-d) in (4) is very important for cost aggregation. The absolute difference and Birchfield function [22] are widely used in cost aggregation. To improve the matching accuracy of the textureless and repetitive regions, the pixel dissimilarity measurement function is described by combing Birchfield function and census transform:(5)eq,q-d=min⁡CBirchq,q-d,IR,IL,TBirch+min⁡CCensusq,q-d,TCensus.To validate the effect of this cost aggregation method, simulation results on Teddy and Cones with Birchfield method and our method are shown in Figure5.Figure 5
(a) Part of the origin image. (b) Disparity results which are computed with our cost aggregation method. (c) Disparity results which are computed with Birchfield pixel dissimilarity measurement function.
(a)
(b)
(c)


## 2.1.1. The Model of Line-Based Adaptive-Weight

Wang et al. [13] noted that when the support region is large enough, color similarity plays a major role in computing the center pixel disparity within a certain range. As shown in Figure 2, red represents the support region S(p). We used the pixels in S(p) to compute the disparity of p. The effects of spatial proximity can be neglected in the pale blue region according to [13]. We call this region the transition area, represented by T(p). To satisfy this principle, the neural network can be applied in the design of this spatial proximity model.Figure 2
The assumption of segmentation-based stereo matching.Figure3 shows the spatial proximity model established by neural network. The position of a pixel is the input, the spatial proximity is the output, and the connect weights are shown as in the figure. In fact, the distance x-xp is the input of neural network. To simplify the notations, suppose that the center point p is at xp=0, the distance x-xp can be simplified into x which represents the position of a pixel. The concrete form of the spatial proximity is expressed by (2)IM1=x+β,IM2=-x+β,OMi=fIMi,IT=∑i=12OMi-1.5,fcΔgpq=fIT,where f(x)=1/(1+e-αx) is the sigmoid function. Figure 4 demonstrates the varied trend of the spatial proximity according to the position of a pixel.Figure 3
Spatial proximity described by neural network.Figure 4
Spatial proximity proposed in this paper whenα=1, β=8, and Ls=15.In Figure4, the space between the two blue lines is the transition area and the support region is represented by the whole x-axis. It can be seen from Figure 4 that (1) the spatial proximity of pixel in the transition area is significantly greater than that of pixel in other area, which accords with the spatial proximity model of traditional adaptive-weight theory; (2) there is not much difference between these pixels in the transition area for the spatial proximity, which means that the influence of spatial proximity can be neglected.According to the segmentation-based stereo matching principle [14, 19], a new model of color similarity is established by the following in [20]:(3)fcΔcpq=1ifsegq=segpexp⁡-Δ2cpqγcotherwise.Equation (3) shows that color similarity contributes enormously to measure the dissimilarity between center pixel p and its neighbor pixel q when p and q belong to the same segmentation.That color similarity model based on image segmentation can achieve good performance, as introduced in [13]. Mean-shift is a nonparametric estimation iterative technique, and its application domains include computer vision, clustering, and image processing [21]. In this work, we use mean-shift as the segmentation method.


## 2.1.2. Cost Aggregation

The matching cost of pixelp with disparity d is represented by(4)Ep,d=∑q∈Lp,q-d∈Lp-dwp,qwp-d,q-deq,q-d∑q∈Lp,q-d∈Lp-dwp,qwp-d,q-d,where p-d and q-d are the corresponding pixels of p and q, respectively, when the disparity of the center pixel is d.The pixel dissimilarity measurement functione(q,q-d) in (4) is very important for cost aggregation. The absolute difference and Birchfield function [22] are widely used in cost aggregation. To improve the matching accuracy of the textureless and repetitive regions, the pixel dissimilarity measurement function is described by combing Birchfield function and census transform:(5)eq,q-d=min⁡CBirchq,q-d,IR,IL,TBirch+min⁡CCensusq,q-d,TCensus.To validate the effect of this cost aggregation method, simulation results on Teddy and Cones with Birchfield method and our method are shown in Figure5.Figure 5
(a) Part of the origin image. (b) Disparity results which are computed with our cost aggregation method. (c) Disparity results which are computed with Birchfield pixel dissimilarity measurement function.
(a)
(b)
(c)


## 2.2. Initial Disparity Determination

The winner-take-all (WTA) searching strategy is a common method for determining disparity, which can be expressed by(6)Dp=argmin⁡dEp,d.WTA tends to produce a low accuracy disparity map. Therefore, we adopt an efficient LBP algorithm proposed in [2] in this paper. In this LBP algorithm, FFT convolution and image pyramid are integrated into LBP, which can effectively decrease the complexity of LBP and increase the matching effect. The flowchart of the initial determination procedure is shown in Algorithm 1.Algorithm 1:The procedure of initial determination procedure.
(1) Computing matching cost E by (4)
Initializing pyramid levell and down sampling factor η=0.5
(2) Pyramid initialization
Pyramid(1).cost = E
(3) Establishing pyramid structure with l and η
(4) For each level i
(5)  For each iteration j
(6)   Updating left, right, up and down direction message for each pixel
(7)  End
(8) End
(9) Determining disparity for each pixel by max-product principle


## 2.3. Disparity Refinement

It is inevitable that initial disparity maps will contain many error-matched pixels. To refine the disparity map, a two-step postprocessing method is put forward in this section.


### 2.3.1. Left-Right Consistency Check

The disparity mapDL for the left image is computed by previous steps. The disparity map DR for the right image is computed in a similar manner. In [15, 17], pixels are classified into several types according to DL, DR, and ER to remove outliers. Then different strategies are designed for different type of pixels to determine its disparity.In this work, we analyzed the property of initial disparity map. Figure6 shows the distribution of bad pixels after executing the disparity initialization step of our algorithm for Tsukuba. It can be seen from this figure that most of the bad pixels concentrate in the occluded region. According to this result, most of the pixels match correctly and the initial disparity in the nonocc region should be trusted. Therefore an iterative left-right consistency check is proposed for handling this.Figure 6
The distribution of bad pixels for initial disparity map of Tsukuba. Bad pixels are marked with red points.Pixels can be divided into two types: undependable pixels and dependable pixels. Pixelp is classified as dependable when it meets the following condition:(7)DLp=DRp-DLp.Pixelp is considered to be undependable if it fits the following condition: (8)DLp≠DRp-DLp.The new disparity of the undependable pixel can be computed as in Algorithm 2.Algorithm 2:The disparity map after execution of left-right consistency checking.
(1)   Establishing the table of pixel type Sti according to (7)-(8)
(2)   St←Sti
(3)    For each iteration k
(4)     For each undependable pixel pi which is determined by St
(5)      Searching the nearest dependable pixel piL and piR
(6)       dpi←min⁡dopiL,dopiR //where do· represents initial disparity of pixel
(7)      If dpi≠dopi
(8)        Set pi as dependable pixel in St
(9)      End
(10)    End
(11)   End
(12)  EndFigure7 shows the result after the execution of iterative left-right consistency checking. Table 1 shows the detailed data for the role of iterative left-right consistency checking.Table 1
The error percentages in different region for disparity refinement step.
Nonocc
All
Disc
Initial disparity map
1.21%
3.20%
6.42%
Left-right consistency
1.17%
2.40%
6.30%
Segmentation voting
0.95%
1.62%
5.07%Figure 7
The disparity map after execution of left-right consistency checking.


### 2.3.2. Segmentation Voting

The pixelwise region shown in Figure8 is established according to color consistency. This region can be represented by U(p). Pixels in U(p) satisfy the following condition:(9)Iq-Ip<τ,q∈Up,xq-xp<Lsv,yq-yp<Lsv.Figure 8
Pixelwise region for segmentation voting.LetH(d) represent the frequency distribution of disparity d in U(p). The new disparity is updated by Algorithm 3.Algorithm 3:Disparity determination of segmentation voting.
(
1) Hd←0
(2) For each q∈Up
(3)  For each d∈dmin⁡,dmax⁡
(4)   If d==DLq
(5)    HDLq←HDLq+1
(6)   End
(7)  End
(8) End
(9) DLp=arg⁡maxd⁡H(d)The3×3 median filter is applied to the left disparity map. Figure 9 shows the effect of segmentation voting on the accuracy of the disparity map.Figure 9
The disparity map of Tsukuba obtained by segmentation voting.


## 2.3.1. Left-Right Consistency Check

The disparity mapDL for the left image is computed by previous steps. The disparity map DR for the right image is computed in a similar manner. In [15, 17], pixels are classified into several types according to DL, DR, and ER to remove outliers. Then different strategies are designed for different type of pixels to determine its disparity.In this work, we analyzed the property of initial disparity map. Figure6 shows the distribution of bad pixels after executing the disparity initialization step of our algorithm for Tsukuba. It can be seen from this figure that most of the bad pixels concentrate in the occluded region. According to this result, most of the pixels match correctly and the initial disparity in the nonocc region should be trusted. Therefore an iterative left-right consistency check is proposed for handling this.Figure 6
The distribution of bad pixels for initial disparity map of Tsukuba. Bad pixels are marked with red points.Pixels can be divided into two types: undependable pixels and dependable pixels. Pixelp is classified as dependable when it meets the following condition:(7)DLp=DRp-DLp.Pixelp is considered to be undependable if it fits the following condition: (8)DLp≠DRp-DLp.The new disparity of the undependable pixel can be computed as in Algorithm 2.Algorithm 2:The disparity map after execution of left-right consistency checking.
(1)   Establishing the table of pixel type Sti according to (7)-(8)
(2)   St←Sti
(3)    For each iteration k
(4)     For each undependable pixel pi which is determined by St
(5)      Searching the nearest dependable pixel piL and piR
(6)       dpi←min⁡dopiL,dopiR //where do· represents initial disparity of pixel
(7)      If dpi≠dopi
(8)        Set pi as dependable pixel in St
(9)      End
(10)    End
(11)   End
(12)  EndFigure7 shows the result after the execution of iterative left-right consistency checking. Table 1 shows the detailed data for the role of iterative left-right consistency checking.Table 1
The error percentages in different region for disparity refinement step.
Nonocc
All
Disc
Initial disparity map
1.21%
3.20%
6.42%
Left-right consistency
1.17%
2.40%
6.30%
Segmentation voting
0.95%
1.62%
5.07%Figure 7
The disparity map after execution of left-right consistency checking.


## 2.3.2. Segmentation Voting

The pixelwise region shown in Figure8 is established according to color consistency. This region can be represented by U(p). Pixels in U(p) satisfy the following condition:(9)Iq-Ip<τ,q∈Up,xq-xp<Lsv,yq-yp<Lsv.Figure 8
Pixelwise region for segmentation voting.LetH(d) represent the frequency distribution of disparity d in U(p). The new disparity is updated by Algorithm 3.Algorithm 3:Disparity determination of segmentation voting.
(
1) Hd←0
(2) For each q∈Up
(3)  For each d∈dmin⁡,dmax⁡
(4)   If d==DLq
(5)    HDLq←HDLq+1
(6)   End
(7)  End
(8) End
(9) DLp=arg⁡maxd⁡H(d)The3×3 median filter is applied to the left disparity map. Figure 9 shows the effect of segmentation voting on the accuracy of the disparity map.Figure 9
The disparity map of Tsukuba obtained by segmentation voting.


## 3. Results and Discussion

### 3.1. Parameters Determining

The parameters involved in our algorithm greatly affect the performance of the algorithm. In this section, we present the parameter settings.We considered eight main parameters:Ls, α, β, γc, hS, hI, Lsv, and τ, which are kept constant for all benchmarks.Figure10 shows the influence of Ls on the accuracy of disparity map obtained by our algorithm. When Ls varies from 35 to 65, our algorithm is insensitive to Ls.Figure 10
(a) Performance evaluation of the proposed method when varyingLs (Tsukuba and Venus). (b) Performance evaluation of the proposed method when varying Ls (Teddy and Cones).
(a)
(b)Figure11 demonstrates that the performance of our algorithm varies with α and β. From these figures, it can be noted that (1) generally speaking when β is larger than 15, the influence of α over algorithm performance is small for Tsukuba, Venus, and Teddy. (2) Our algorithm shows good performance for Tsukuba and Teddy when β∈[0,45] and α∈[0.3,1]. (3) The error percentage tends to decrease with a decreasing α when β is smaller than 15. (4) In regard to Cones, the performances of this algorithm improve as α increases, and when β lies between 15 and 30.Figure 11
(a) Performance evaluation of the proposed method according toα and β for Tsukuba. (b) Performance evaluation of the proposed method according to α and β for Venus. (c) Performance evaluation of the proposed method according to α and β for Teddy. (d) Performance evaluation of the proposed method according to α and β for Cones.
(a)
(b)
(c)
(d)Figure12 shows the influence of γc on performance. The trend of the error percentage is U-shaped for Tsukuba when γc is smaller than 20. The error percentage bottom out when γc is between 7 and 13. The error percentage for Venus follows a downward trend. For Teddy and Cones, the error percentage is inversely proportional to γc. When γc is larger than 12, the error percentage is insensitive to γc.Figure 12
(a) Performance evaluation of the proposed method when varyingγc (Tsukuba and Venus). (b) Performance evaluation of the proposed method when varying γc (Teddy and Cones).
(a)
(b)Figure13 shows the performance of our algorithm according to hS and hI. From these figures, our algorithm has a good ability of robustness with different values of hS. When hI∈[3,8], the error percentage of the disparity map obtained by our algorithm is still fairly low.Figure 13
(a) Performance evaluation of the proposed method according tohS and hI for Tsukuba. (b) Performance evaluation of the proposed method according to hS and hI for Venus. (c) Performance evaluation of the proposed method according to hS and hI for Teddy. (d) Performance evaluation of the proposed method according to hS and hI for Cones.
(a)
(b)
(c)
(d)For the disparity map refinement step, two main parameters must be set.Lsv and τ are previously introduced. Figure 14 shows the influence of Lsv and τ on performance. When Lsv∈[5,20] and τ∈[7,10], all data sets show good performance.Figure 14
(a) Performance evaluation of the proposed method according toLsv and τ for Tsukuba. (b) Performance evaluation of the proposed method according to Lsv and τ for Venus. (c) Performance evaluation of the proposed method according to Lsv and τ for Teddy. (d) Performance evaluation of the proposed method according to Lsv and τ for Cones.
(a)
(b)
(c)
(d)


### 3.2. Experimental Results

We evaluate our algorithm on Middlebury benchmarks [23] with error threshold 1. The test platform hardware consists of T9600 CPU and 5 GB memory. Software consists of MATLAB 2014a and VS2012. Parameters are shown in Table 2.Table 2
Parameter setting for Middlebury benchmark.
L
s
α
β
γ
c
h
S
h
I
L
sv
τ
40
1
15
8
15
5
7
12Simulation results on Middlebury data sets are presented in Figure15. The quantitative performance of our algorithm is shown in Tables 3 and 4. Our algorithm ranks 5th in the Middlebury data set (July 1, 2014).Table 3
Quantitative evaluation results for Middlebury benchmark.
Algorithm
Tsukuba
Venus
Teddy
Cones
Nonocc
All
Disc
Nonocc
All
Disc
Nonocc
All
Disc
Nonocc
All
Disc
AdaptingBP
1.1122
1.379
5.7924
0.104
0.217
1.448
4.2217
7.0615
11.818
2.4822
7.9228
7.3227
CoopRegion [14]
0.875
1.162
4.614
0.115
0.215
1.5414
5.1630
8.3120
13.025
2.7939
7.1814
8.0147
Our algorithm
0.898
1.5923
4.789
0.115
0.3624
1.4911
4.3318
9.9332
11.217
2.8141
8.4645
7.8540
RDP [15]
0.9711
1.3911
5.0011
0.2139
0.3829
1.8924
4.8422
9.9433
12.622
2.5325
7.6920
7.3828
MultiRBF [16]
1.3347
1.5620
6.0232
0.1311
0.172
1.8421
5.0928
6.368
13.429
2.9048
6.768
7.1024Table 4
The results of whole performance evaluation for Middlebury benchmark.
Algorithm
Average rank
Average percent bad pixels
AdaptingBP
16.5
4.23
CoopRegion
12.2
4.41
Our algorithm
22.8
4.48
RDP
22.9
4.57
MultiRBF
23.2
4.39Figure 15
(a) The final disparity map obtained by our algorithm. (b) Error maps. (c) Ground truth.
(a)
(b)
(c)These results demonstrate our algorithm has a good performance. However, it is difficult to decrease the error percentages in the three regions (nonocc, all, and disc) at the same time. This is because many pixels with correct disparity are classified as undependable, according to (8). Tsukuba can be used as an example. Figure 16 represents the bad pixels detected by (7)-(8).Figure 16
Erroneous disparity distribution determined by (7)-(8) for the Tsukuba image.Figure6 shows the bad pixels obtained by comparing the initial disparity map and ground truth. Figure 6 indicates that true bad pixels are distributed in the occlusion region. However, it can be inferred from Figure 16 that many pixels in nonocc and disc regions are mistakenly classified as undependable. When standard LRC checking is used, misclassified pixels in the disc region may be assigned a wrong disparity, as shown in Figure 17. Table 5 shows quantitative comparison results for standard LRC checking and iterative LRC checking.Table 5
Comparison between standard LRC checking and iterative LRC checking presented in Section2.3.1.
Algorithm
Nonocc
All
Disc
Initial disparity
1.21%
3.20%
6.42%
Standard LRC checking
1.43%
2.10%
7.54%
Iterative LRC checking
1.17%
2.40%
6.30%Figure 17
Erroneous disparity distribution after executing standard LRC checking for Tsukuba.Thus, it can be seen that the error percentage in the disc region greatly increases after applying standard LRC checking. Because the disc region is part of the nonocc region, the error percentage in the nonocc region also increases. Our iterative LRC checking method can effectively improve the performance of our stereo matching algorithm.


### 3.3. Running Time of Our Algorithm

In this section, we investigate the computation running time of our algorithm. The running time directly reflects computational complexity. Without a loss of generality, our algorithm runs 50 times and average running time was calculated. Results are shown in Table6.Table 6
The average running time of each part of our algorithm for Tsukuba.
Mean-shift
Cost aggregation
LBP
Iterative LRC
Segmentation voting
7.37
19.23
0.78
0.24
0.30The new rectangle-based adaptive-weight method can be obtained by imposing they-direction constraint on the new weight model. Table 7 displays the running time of cost aggregation of our algorithm with the rectangle-shaped support region under different sizes of support region. The rectangle-based algorithm also runs 50 times under each size of support windows.Table 7
The variation of average running time of cost aggregation of our rectangle-based algorithm under different size of support region.
The size of support region
11
×
11
15
×
15
19
×
19
23
×
23
27
×
27
Running time
37.02
69.81
106.53
154.41
213.94Our algorithm with the rectangle-shaped support region performed best when the size of the support region is27×27; the error percentages of the initial disparity map in nonocc, all, and disc regions are 1.45%, 3.42%, and 7.08%, respectively. Tables 5–7 show that our algorithm produced notable results in decreasing computation complexity and improving performance.


## 3.1. Parameters Determining

The parameters involved in our algorithm greatly affect the performance of the algorithm. In this section, we present the parameter settings.We considered eight main parameters:Ls, α, β, γc, hS, hI, Lsv, and τ, which are kept constant for all benchmarks.Figure10 shows the influence of Ls on the accuracy of disparity map obtained by our algorithm. When Ls varies from 35 to 65, our algorithm is insensitive to Ls.Figure 10
(a) Performance evaluation of the proposed method when varyingLs (Tsukuba and Venus). (b) Performance evaluation of the proposed method when varying Ls (Teddy and Cones).
(a)
(b)Figure11 demonstrates that the performance of our algorithm varies with α and β. From these figures, it can be noted that (1) generally speaking when β is larger than 15, the influence of α over algorithm performance is small for Tsukuba, Venus, and Teddy. (2) Our algorithm shows good performance for Tsukuba and Teddy when β∈[0,45] and α∈[0.3,1]. (3) The error percentage tends to decrease with a decreasing α when β is smaller than 15. (4) In regard to Cones, the performances of this algorithm improve as α increases, and when β lies between 15 and 30.Figure 11
(a) Performance evaluation of the proposed method according toα and β for Tsukuba. (b) Performance evaluation of the proposed method according to α and β for Venus. (c) Performance evaluation of the proposed method according to α and β for Teddy. (d) Performance evaluation of the proposed method according to α and β for Cones.
(a)
(b)
(c)
(d)Figure12 shows the influence of γc on performance. The trend of the error percentage is U-shaped for Tsukuba when γc is smaller than 20. The error percentage bottom out when γc is between 7 and 13. The error percentage for Venus follows a downward trend. For Teddy and Cones, the error percentage is inversely proportional to γc. When γc is larger than 12, the error percentage is insensitive to γc.Figure 12
(a) Performance evaluation of the proposed method when varyingγc (Tsukuba and Venus). (b) Performance evaluation of the proposed method when varying γc (Teddy and Cones).
(a)
(b)Figure13 shows the performance of our algorithm according to hS and hI. From these figures, our algorithm has a good ability of robustness with different values of hS. When hI∈[3,8], the error percentage of the disparity map obtained by our algorithm is still fairly low.Figure 13
(a) Performance evaluation of the proposed method according tohS and hI for Tsukuba. (b) Performance evaluation of the proposed method according to hS and hI for Venus. (c) Performance evaluation of the proposed method according to hS and hI for Teddy. (d) Performance evaluation of the proposed method according to hS and hI for Cones.
(a)
(b)
(c)
(d)For the disparity map refinement step, two main parameters must be set.Lsv and τ are previously introduced. Figure 14 shows the influence of Lsv and τ on performance. When Lsv∈[5,20] and τ∈[7,10], all data sets show good performance.Figure 14
(a) Performance evaluation of the proposed method according toLsv and τ for Tsukuba. (b) Performance evaluation of the proposed method according to Lsv and τ for Venus. (c) Performance evaluation of the proposed method according to Lsv and τ for Teddy. (d) Performance evaluation of the proposed method according to Lsv and τ for Cones.
(a)
(b)
(c)
(d)


## 3.2. Experimental Results

We evaluate our algorithm on Middlebury benchmarks [23] with error threshold 1. The test platform hardware consists of T9600 CPU and 5 GB memory. Software consists of MATLAB 2014a and VS2012. Parameters are shown in Table 2.Table 2
Parameter setting for Middlebury benchmark.
L
s
α
β
γ
c
h
S
h
I
L
sv
τ
40
1
15
8
15
5
7
12Simulation results on Middlebury data sets are presented in Figure15. The quantitative performance of our algorithm is shown in Tables 3 and 4. Our algorithm ranks 5th in the Middlebury data set (July 1, 2014).Table 3
Quantitative evaluation results for Middlebury benchmark.
Algorithm
Tsukuba
Venus
Teddy
Cones
Nonocc
All
Disc
Nonocc
All
Disc
Nonocc
All
Disc
Nonocc
All
Disc
AdaptingBP
1.1122
1.379
5.7924
0.104
0.217
1.448
4.2217
7.0615
11.818
2.4822
7.9228
7.3227
CoopRegion [14]
0.875
1.162
4.614
0.115
0.215
1.5414
5.1630
8.3120
13.025
2.7939
7.1814
8.0147
Our algorithm
0.898
1.5923
4.789
0.115
0.3624
1.4911
4.3318
9.9332
11.217
2.8141
8.4645
7.8540
RDP [15]
0.9711
1.3911
5.0011
0.2139
0.3829
1.8924
4.8422
9.9433
12.622
2.5325
7.6920
7.3828
MultiRBF [16]
1.3347
1.5620
6.0232
0.1311
0.172
1.8421
5.0928
6.368
13.429
2.9048
6.768
7.1024Table 4
The results of whole performance evaluation for Middlebury benchmark.
Algorithm
Average rank
Average percent bad pixels
AdaptingBP
16.5
4.23
CoopRegion
12.2
4.41
Our algorithm
22.8
4.48
RDP
22.9
4.57
MultiRBF
23.2
4.39Figure 15
(a) The final disparity map obtained by our algorithm. (b) Error maps. (c) Ground truth.
(a)
(b)
(c)These results demonstrate our algorithm has a good performance. However, it is difficult to decrease the error percentages in the three regions (nonocc, all, and disc) at the same time. This is because many pixels with correct disparity are classified as undependable, according to (8). Tsukuba can be used as an example. Figure 16 represents the bad pixels detected by (7)-(8).Figure 16
Erroneous disparity distribution determined by (7)-(8) for the Tsukuba image.Figure6 shows the bad pixels obtained by comparing the initial disparity map and ground truth. Figure 6 indicates that true bad pixels are distributed in the occlusion region. However, it can be inferred from Figure 16 that many pixels in nonocc and disc regions are mistakenly classified as undependable. When standard LRC checking is used, misclassified pixels in the disc region may be assigned a wrong disparity, as shown in Figure 17. Table 5 shows quantitative comparison results for standard LRC checking and iterative LRC checking.Table 5
Comparison between standard LRC checking and iterative LRC checking presented in Section2.3.1.
Algorithm
Nonocc
All
Disc
Initial disparity
1.21%
3.20%
6.42%
Standard LRC checking
1.43%
2.10%
7.54%
Iterative LRC checking
1.17%
2.40%
6.30%Figure 17
Erroneous disparity distribution after executing standard LRC checking for Tsukuba.Thus, it can be seen that the error percentage in the disc region greatly increases after applying standard LRC checking. Because the disc region is part of the nonocc region, the error percentage in the nonocc region also increases. Our iterative LRC checking method can effectively improve the performance of our stereo matching algorithm.


## 3.3. Running Time of Our Algorithm

In this section, we investigate the computation running time of our algorithm. The running time directly reflects computational complexity. Without a loss of generality, our algorithm runs 50 times and average running time was calculated. Results are shown in Table6.Table 6
The average running time of each part of our algorithm for Tsukuba.
Mean-shift
Cost aggregation
LBP
Iterative LRC
Segmentation voting
7.37
19.23
0.78
0.24
0.30The new rectangle-based adaptive-weight method can be obtained by imposing they-direction constraint on the new weight model. Table 7 displays the running time of cost aggregation of our algorithm with the rectangle-shaped support region under different sizes of support region. The rectangle-based algorithm also runs 50 times under each size of support windows.Table 7
The variation of average running time of cost aggregation of our rectangle-based algorithm under different size of support region.
The size of support region
11
×
11
15
×
15
19
×
19
23
×
23
27
×
27
Running time
37.02
69.81
106.53
154.41
213.94Our algorithm with the rectangle-shaped support region performed best when the size of the support region is27×27; the error percentages of the initial disparity map in nonocc, all, and disc regions are 1.45%, 3.42%, and 7.08%, respectively. Tables 5–7 show that our algorithm produced notable results in decreasing computation complexity and improving performance.


## 4. Conclusions

In this work, we proposed a new line-based adaptive-weight stereo matching algorithm that integrates several methods. The main conclusions that can be drawn from our results are as follows.(1)
Cost aggregation is the most time-consuming part of stereo matching algorithm. Using a line-shaped support region can dramatically reduce the elapsed time of cost aggregation.(2)
The adaptive-weight model proposed in this paper can produce a rather satisfactory initial disparity map in the absence of enough pixel information.(3)
Experimental results show that the algorithm proposed in this paper can attain a better matching effect with less running time.Although our algorithm has a good performance on Middlebury data sets, there is still much room for improvement.(1)
There are too many parameters in our algorithm to accommodate different image pairs. In further research, we will analyze the intrinsic relationship among the parameters and reduce the number of parameters.(2)
Figure13 indicates that image characteristics have a significant impact on the optimum values of α and β. In future studies, we will explore how the optimum values of α and β vary according to the texture of image.



---

*Source: 297392-2015-04-19.xml*