1. INTRODUCTION

Stereo matching plays an important role in many applications, including 3D reconstruction, 3D scanning, and medical imaging. According to [1], stereo-matching algorithms can be mainly classified into local and global methods. Global stereo methods skip the cost aggregation step. They use belief propagation [2] or graph cut [3] to minimize an energy function and constrain the disparity smoothness between two neighbor pixels. Global methods achieve higher accuracy, but the execution time is long. Local methods use local features to determine each pixel’s disparity. The matching accuracy of the local method is lower than that of the global method, but it benefits from a fast running time, so it has attracted a lot of attention. In recent years, the semi-global method (SGM) and the data-driven method (deep learning) have also been widely used to solve the stereo-matching problem. Compared with these, the local method is simpler in principle and implementation. Therefore, in our work, we focus on computing an accurate disparity map with the local stereo-matching strategy.

Most local stereo-matching methods consist of four steps: cost computation, cost aggregation, disparity computation, and disparity refinement. Most stereo-matching algorithms use intensity-based initial cost measurements, for instance, the sum of absolute differences (SAD) and the sum of squared differences (SSD). But these methods are sensitive to noise and radiometric distortions [4]. Fortunately, the normalized cross correlations (NCC) [5], gradient, rank [6], census transforms [7], and convolutional neural networks (CNN) [8] have been widely used. Certainly, in order to obtain more robust cost, some methods combine different costs [9–11].

The cost-aggregation procedure is another significant procedure for stereo matching, because cost aggregation can restrain the noise interference in the cost volume. Many aggregation methods have been proposed and evaluated [12]. Yoon and Kweon [13] proposed an adaptive support weight (ASW) method based on color and distance information at the cost aggregation step, and the weight assigned to each pixel is variable. The edge effect is much better than the SAD algorithm, and ASW achieved results comparable to those of global methods. After the ASW, many edge-aware filters were introduced to smooth the cost volume. Yang [14] used improved bilateral filtering to filter the cost volume. Rhemann et al. [15] used a very fast edge-preserving filter (guided filter [16]) to smooth the cost volume. It used the mean and variance information to calculate the filtering weight, which introduced the structure information of the image. The matching result is more accurate, and the noise point is less than that of the ASW algorithm. After Rhemann, many methods used the guided filter or its variant to proceed with the cost aggregation [17–19]. Besides the support weight, some scholars pay more attention to the support region shape [20–22]. Veksler [20] presented a variable window method by choosing a useful range of window shapes/sizes for evaluation. Zhang et al. [21] constructed a cross-skeleton support region for every pixel. Shi et al. [22] calculated the adaptive support window according to each segmentation region based on the color correlation between adjacent pixels. In order to consider more global information, some segment tree methods were proposed [23,24]. Yang [23] proposed a non-local cost aggregation method, which extended the kernel size to the entire image. By computing a minimum spanning tree (MST) over the image graph, the non-local cost aggregation method can perform extremely fast. Mei et al. [24] followed the non-local cost aggregation idea and enforced the disparity consistency by using a segment tree instead of MST. Zhang et al. [25] proposed a cross-scale cost aggregation (CSCA) stereo-matching method. Compared with the single-scale cost aggregation, this multiscale constraint strengthened the consistency of inter-scale cost volume and behaved well in textureless regions.

Disparity refinement is designed to improve the matching accuracy in occluded regions and low-texture regions. The left-right consistency check (LRC) and the left-right filling strategy [26] are commonly used to detect and refine outliers. Huang and Zhang [27] used belief aggregation for outlier detection and belief propagation for disparity filling. Mei et al. [10] detected and classified pixels into occlusions and mismatches and then used an iterative region voting strategy to interpolate these outliers. Bilateral filtering and weighted median filtering [28] were also employed for disparity refinement.

Though many methods have been proposed to improve the matching accuracy, the low-accuracy problem in texture-free regions has not been solved very well. To improve the matching accuracy in texture-free regions, we propose a local stereo-matching method based on multi-scale fusion and multi-type support regions. There are some contributions for our method.

Figure 1 shows the flowchart of our algorithm. The red lines denote the cost computation step, the green lines denote the cost aggregation step, the blue lines denote the disparity computation step, and the black lines denote the disparity refinement step. The purple lines denote the proposed pixel category step.

 

Fig. 1. Overview of the proposed method.

Download Full Size | PDF

The paper is organized as follows: Section 1 is the introduction. The proposed method is described in Section 2. Corresponding to the four steps of stereo matching, Section 2.A is the cost computation procedure, Section 2.B is the cost aggregation procedure, Section 2.C is the disparity computation procedure, and Section 2.D is the disparity refinement procedure. Experiments and comparison results are presented in Section 3. Finally, we come to the conclusion in Section 4.

2. PROPOSED METHOD

A. Cost Computation Using Color and Gradient Differences

The common cost measurements include absolute difference (AD), gradient amplitude, and non-parametric transformations such as rank and census. They all have their own strengths and weaknesses and apply to different backgrounds. In order to synthesize the advantages of different algorithms, the matching cost combination method is widely used. Zhu and Li [9] proposed an improved gradient cost function that incorporates the gradient phase because the gradient vector and phase have different invariance properties with respect to the radiometric distortion. Mei et al. [10] proposed a new cost measure by combining AD and census to achieve an impressive performance. Zhan et al. [11] proposed a novel double-RGB gradient model using the guidance image. In our method, we use the color and gradient differences to compute the matching cost.

Given a pixel $p=(x,y)$ in the left image with a disparity d, the corresponding pixel in the right image is $p_d=(x-d,y)$. First, we compute the color and gradient cost values $C_{AD}(p,d)$ and $C_{GD}(p,d)$ as follows:

B. Cost Aggregation by Cost Volume Fusion

After obtaining the color and gradient cost volumes, many cost computation methods use the fixed proportion [Eq. (5)] to merge these different cost volumes [15,19,29–31]. The fixed proportion merging method is simple, but it is difficult to obtain the optimal merging parameter $\alpha$. Different from these methods, we use the guided filter to merge these two cost volumes as follows:

 

Fig. 2. Disparity maps under different cost volumes. (a), (c) Disparity maps under single color cost volume; (b), (d) disparity maps under single gradient cost volume.

Download Full Size | PDF

Based on these characteristics, we assume that the aggregated cost volume has relationships with the color cost volume $C_{AD}$ and the gradient cost volume $C_{GD}$ as shown in Eqs. (6) and (7). To minimize the energy function [Eq. (8)], we can solve the guided filter parameters in Eqs. (9) and (10) and compute the fused cost volume as follows:

Figure 3 contains the disparity maps under the fixed proportion cost merging method of [15] and our cost fusion method. The disparity maps obtained by our cost volume are more correct, especially in texture-free regions (the red rectangle areas).

 

Fig. 3. Disparity maps under different cost volume merging algorithms. (a), (c) Disparity maps under the fixed proportion merging method of [15]; (b), (d) disparity maps under our fused cost volume. All results are obtained under the guided filter cost aggregation method.

Download Full Size | PDF

C. Primary Disparity Computation Based on Multi-Scale Disparity Merging

1. Multi-Scale Disparity Map Computation

CSCA [25] proved that cross-scale cost aggregation behaved well in textureless regions. Inspired by that, we use multi-scale images in our method. We use the original and the half-scale images to compute the cost volume and obtain the disparity maps corresponding to each scale. We record the zoom parameter as scale. The block sizes [$\mathrm{\Omega }(x)$ in Eq. (6)] of the cost volume fusion process under two scales are $r_1\times r_1$ and $r_2\times r_2$. Figure 4(b) shows the disparity maps obtained under the half-scale image (the disparity map has been resized to the same size as the original image). In red rectangle regions on the plastic image, the error disparities of the half-scale image are less than the original scale. But, in the red rectangle regions on the Tsukuba image, the fine structural information under the half scale is not better than that of the original scale image. To get a primary disparity map that has less incorrect values in large texture-free regions and retains fine structural information, we propose our disparity merging method based on the pixel category.

 

Fig. 4. Disparity maps under different scales. (a) Disparity maps obtained under the original scale, (b) disparity maps obtained under the half-scale, and (c) disparity maps obtained under our disparity merging method.

Download Full Size | PDF

2. Multi-Scale Disparity Maps Merging Based on Pixel Category

In our merging method, we define three pixel categories: segmentation category, texture category, and left-right consistency (LRC) category. We use the mean-shift segmentation method [32] to obtain the segmentation category image [as shown in Fig. 5(b)]. Pixels in the same segmentation region have the same label.

 

Fig. 5. Pixel category images. (a) Original left image, (b) segmentation category image by mean shift, (c) texture category image, and (d) the LRC category image.

Download Full Size | PDF

We use Eq. (11) on the segmentation image to produce the texture category image. In the texture category image, pixels with a value of 1 [white pixels in Fig. 5(c)] lie in the texture-free regions, and pixels with a value smaller than 1 lie in the texture regions;

Besides the previous two categories, we also use the LRC check to classify the pixels into stable and unstable points. Figure 5(d) is the LRC category image. Pixels with a value of 1 (white pixels in LRC category image) fail the LRC check, and pixels with a value of 0 (black pixels in LRC category image) pass the LRC check.

In the end, for pixels whose texture category values equal 1 and fail the LRC check simultaneously, we choose the small scale disparity values as the primary disparity values. For other pixels, we choose the original scale disparity values as the primary disparity values. Figure 4(c) shows the primary disparity maps by our disparity map merging method. Compared with Figs. 4(a) and 4(b), our primary disparity maps retain fine structural information and have less incorrect values in texture-free regions.

D. Disparity Refinement

1. Edge Disparity Optimization Based on Multi-Information Weights

The disparity map usually suffers from the edge foreground expansion problem. To solve this problem, we first use the Canny edge detection method on the first filled disparity map to find the disparity edge [Fig. 6(b)]. Then we use the dilate operation to expand the edge lines into edge regions. In Fig. 6(d), the green lines are the ground truth disparity edges, and the black regions are the disparity edge regions extracted by us. The green lines are surrounded by our disparity edge regions. Therefore, operating the cost aggregation on the detected disparity edge regions can once again obtain more accurate edge disparity values.

 

Fig. 6. Edge regions detection. (a) First filled disparity map, (b) canny edge of left image, (c) ground-truth disparity map, and (d) the location relationship of the expanded edge region and the true edge.

Download Full Size | PDF

In order to limit the time consumed, for the disparity edge pixels we do not proceed with the second cost aggregation on the whole cost volume. As shown in Fig. 7, for an edge point (the blue pixel), the effective disparity values in its support region (the red rectangle) are 5 and 8 on the first filled disparity map, so we prefer to proceed with the aggregation operation on the cost volume only from disparity of 5 to disparity of 8 instead of the whole cost volume from disparity 1 to 25 (the disparity level).

 

Fig. 7. Disparity limitation on edge region cost aggregation.

Download Full Size | PDF

The cost aggregation methods can be regarded as a filter operation in Eq. (13). Color weight in Eq. (14) and spatial distance weight in Eq. (15) are always used to assign the filter weights. In our method, we introduce another disparity weight in Eq. (16) into the weight assignment procedure. The three image categories (obtained in Section 2.C.2) are also used in the weight calculation procedure, written as follows:

For edge pixels the lie in the texture-free regions, the weight calculation method is Eq. (18). The disparity values in texture-free regions are usually low error values, and the parameter ${\lambda }_3$ can assign low weight for the pixels with incorrect low disparity values as follows:

 

Fig. 8. Disparity map under different weight computation algorithms. (a) Disparity map before edge optimization, (b) disparity maps under the color and distance weights and without the disparity limitation, and (c) disparity maps under our weight assignment method.

Download Full Size | PDF

2. Disparity Map Filling Based on Multi-Type Support Regions

The ordinary left-right consistency check (LRC) is important for disparity refinement, but there are some disadvantages for the LRC check and filling strategy.

First, the LRC check is always not correct enough: pixels that have passed the LRC check may not have the correct disparity, and pixels that have failed the LRC check may have the correct disparity.

Second, the ordinary LRC only pays attention to the horizontal direction and ignores other surrounding pixels’ disparity information.

Third, the perceptual range of the ordinary LRC is limited; it cannot collect enough global information to deal with the texture-free regions.

To overcome all these disadvantages, we define four types of support regions based on the three pixel categories defined in Section 2.C.2. Figure 9 shows the four types of support regions. The horizontal support region is the ordinary LRC check region; the eight scan lines support region and the rectangle support region pay more attentio to the local information. The cross-support region pays more attention to the global information.

 

Fig. 9. Support region setting for disparity filling. (a) Horizontal support region, (b) rectangle support region, (c) eight scan lines support region, (d) cross-support region. Pixels with red edges form the support regions.

Download Full Size | PDF

In the horizontal support region, we find two pixels that have passed the LRC check first in the left side and the right side, and then we calculate the minimum and maximum disparity value of these two pixels and record them as ${\text{horizon}}_{\min }$ and ${\text{horizon}}_{\max }$.

In the eight scan lines support region, we find eight pixels that have passed the LRC check first in eight directions. Then, among these eight pixels, we find the pixel that is the most similar to the pixel that failed the center LRC check and record the disparity of it as ${\text{eight}}_{\mathrm{most}}$. The similarity is calculated by Eq. (19) as follows

In the rectangle support region, we compute the median disparity value for the pixels that lie in the same segmentation region as the center pixel and record it as ${\text{rect}}_{\mathrm{med}}$. We also compute the median disparity value for the pixels that have passed the LRC check and simultaneously lie in the same segmentation region as the center pixel, and we record it as ${\text{rect}}_{\text{med\_lrc}}$.

The half-arm length of the cross-support region is $r_7$. In this support region, we compute the median disparity value for the pixels that lie in the same segmentation region as the center pixel and record it as ${\text{cross}}_{\mathrm{med}}$. After that, we further compute the median disparity value and the largest disparity value for the pixels that have passed the LRC check and simultaneously lie in the same segmentation region as the center pixel. Then we record them as ${\text{cross}}_{\text{med\_lrc}}$ and ${\text{cross}}_{\mathrm{most}}$.

Our disparity refinement contains two disparity filling steps. The first filling step mainly pays attention to the local disparity information, so the horizontal support region, the eight scan lines support region, and the rectangle support region are used. The concrete procedure for the first disparity filling is shown in Table 1.

Table 1. First Disparity Filling Process

View Table | View all tables in this article

In Table 1, $x_1$ is one of the candidate pixels in the rectangle support region $\mathrm{\Omega }(x)$. $T(x)\ne 1$ means that pixel $x$ does not lie in the texture-free region. $S(x_1)=S(x)$ means that pixel $x_1$ lies in the same segmentation region as pixel $x$. $\mathrm{LRC}(x_1)\ne 1$ means that pixel $x_1$ has passed the LRC check. The $\mathrm{num}()$ operation counts the pixel number, satisfying the conditions in the brackets. If the amount of pixels that lie in the same region as the center pixel and have also passed the LRC check is not larger than the threshold ${\lambda }_4$, the ${\text{rect}}_{\text{med\_lrc}}$ is less likely to be the correct disparity value. Considering this, we set the operations from line 9 to line 13.

The second filling step mainly pays attention to the global disparity information, so the horizontal support region and the cross-support region are used. In order to deal with texture-free regions, we divide pixels into four categories: pixels that have failed the LRC check and also lie in the texture-free region, pixels that have failed the LRC check and also lie in the texture region, pixels that have passed the LRC check and also lie in the texture-free region, and pixels that have passed the LRC check and also lie in the texture region. For these four pixel categories, we use different the filling strategies listed in Table 2.

Table 2. Second Disparity Filling Process

View Table | View all tables in this article

In Table 2, the settings of $\text{numDisp}/2$ in line 5 and line 19 are to restrain low incorrect values in foreground areas and high incorrect values in background areas. In the cross-support region, if the amount of pixels that lie in the same region as the center pixel and have also passed the LRC check is not larger than the threshold ${\lambda }_4$, the ${\text{cross}}_{\text{med\_lrc}}$ value is less likely to be the correct disparity value. Considering this, we set the operations from line 11 to line 15. In line 24, for the pixels that pass the LRC check, the setting of ${\lambda }_5$ can avoid the unnecessary change.

Figure 10 shows the results of each refinement step in our method. For the first and second filling steps in Figs. 10(b) and 10(d), the filled disparity maps have less error disparities than the previous non-filled disparity maps in Figs. 10(a) and 10(c).

 

Fig. 10. Results of every procedure under the proposed method. (a) Primary disparity maps, (b) first filled disparity maps, (c) edge-optimized disparity maps, (d) second filled disparity maps.

Download Full Size | PDF

3. EXPERIMENT AND ANALYSIS

A. Experimental Environment and Parameter Setting

In order to evaluate the performance of the proposed method, we carry out our experiments with an Intel i5-7300HQ 2.5 GHz CPU and 8 GB RAM environment, and the development tool is MATLAB 2016a. There are some parameters in our experiments, and they are listed in Table 3. In Table 3, wid and hei are image width and height, respectively. The scale of 0.5 means that we use two scale images: the original scale image and the half-scale image. The win is the basic block size in our method, and many other block sizes are based on it. The ${\tau }_{AD}$ and ${\tau }_{GD}$ are the same as in [19,30]. Figure 11 shows the results by our method.

Table 3. Parameters Set in our Experiments

View Table | View all tables in this article

 

Fig. 11. Results of the proposed method: (a), (c), and (e) original images; (b), (d), and (f) the final results of our method (red pixels are error pixels). The original images from left to right are Adirondack, Midd1, and Dolls.

Download Full Size | PDF

The complexity of the cost fusion procedure is similar to that of the CostFilter [15] method, because we all use the guided filter for cost aggregation. The complexity of the disparity refinement is mainly decided by the disparity edge-optimization procedure, which proceeds the second cost aggregation procedure on the disparity edge pixels. Table 4 shows the corresponding time consumption of the images in Fig. 11. In Table 4, the time of the small image Midd1 is close to the time of the large image Adirondack; this is because the edge-optimization procedure will find and optimize more disparity edge pixels in the texture-free regions. The whole matching time for the Midd1 image is 258 s: the disparity edge-optimization procedure takes 151 s, and the cost fusion procedure is 4 s.

Table 4. Computation Time in Seconds

View Table | View all tables in this article

B. Comparison Experiments

As a method based on the guided filter, our method can be regarded as an improvement on the CostFilter method [15], so we first compare our method with CostFilter. Table 5 is the final error results of our method and the CostFilter method. We do the comparison experiments on the four Middlebury 2.0 test images. Compared with the CostFilter method, our method obtains a lower error rate in three images, and our method’s average error rate is also lower than that of the CostFilter method.

Table 5. Comparison Result between CostFilter and the Proposed Algorithms

View Table | View all tables in this article

Our method is a multi-scale method that is inspired by the CSCA method. But different from the CSCA method, instead of merging costs under different scales, we merge disparity maps under different scales. Figure 12 shows the comparison result between CSCA and our method. All disparity maps in Fig. 12 do not have disparity refinement. We can see in the texture-free regions (the red rectangle regions) that our disparity maps have more correct disparity values than CSCA. This proves that our multi-scale disparity map merging method is more suitable for texture-free regions than the CSCA method.

 

Fig. 12. Comparison results between CSCA and the proposed method. (a) Left images, (b) disparity maps under CSCA, and (c) disparity maps under the proposed method.

Download Full Size | PDF

The PatchMatch-based methods have attracted the attention of many scholars, and this kind of method currently achieves the best result in the non-deep-learning methods. Therefore, we also compare our method with some PatchMatch-based methods and other classical methods: PatchMatch Belief Propagation (PMBP) [33], Speed-up PatchMatch Belief Propagation (SPM-BP) [29], Graph Cut based continuous stereo matching using Locally Shared Labels (GCLSL) [34], Segment Tree (ST) [24], Local Expansion (LocalExp) [35], PatchMatch (PM) [36], and PatchMatch-based Superpixel Cut (PMSC) [37]. Since most of the methods are designed for low-resolution images, we run the corresponding experiments on the Middlebury 2006 data set, which consists of 21 low-resolution image pairs. Figures 13 and 14 are part of the image results.

 

Fig. 13. Comparison of disparity maps generated from different algorithms. Error pixels are marked in red. (a) Left image, (b) PMBP, (c) SPM-BP, (d) GCLCL, (e) PMSC, and (f) our proposed method. Best viewed with zoom-in on a digital display.

Download Full Size | PDF

 

Fig. 14. Comparison of disparity maps generated from different algorithms. Error pixels are marked in red. (a) Left image, (b) PatchMatch, (c) PMF, (d) LocalExp, (e) our proposed. Best viewed with zoom-in on a digital display.

Download Full Size | PDF

As shown in Figs. 13 and 14, the PM, PatchMatch Filter (PMF), PMBP, SPM-BP, and GCLSL methods are not good at dealing with texture-free regions: they have many error disparities (the red points in these two figures) in the texture-free regions. Table 6 shows the eight methods’ error rates on the 21 image pairs of Middlebury 2006, with 1 pixel error threshold. Error rates are evaluated on non-occluded regions. Our method reaches the best accuracy in 11 out of the 21 image pairs, and the average error rate is also the lowest. The PMSC and LocalExp methods used the pixel-matching cost from Matching Cost with a Convolutional Neural Network (MC-CNN) [8], but their average error rates are also not superior to ours, especially for images containing large texture-free regions like Midd1, Midd2, Monopoly, and Plastic in Table 6.

Table 6. Comparison Result under Middlebury 2006 Data Set on Non-occluded Regions^a

View Table | View all tables in this article

The Middlebury 2006 data sets contain low-resolution images, so we also evaluate our method on the Middlebury 2014 data sets, which have high-resolution images. There are many state-of-the-art methods on the Middlebury website, including the local method, global method, semi-global method, and data-driven (deep learning) method. Because our method is not a data-driven method, we compare our method with the newest non-data-driven methods: Confidence Map based 3D cost aggregation with multiple Minimum Spanning Trees (3DMST-CM) [38], Coalesced Bidirectional Matching Volume Robost vision challenge (CBMV-ROB) [39], Dense and robust image registration by shift Adapted Weighted Aggregation (DAWA-F) [40], Fusing Adaptive Support Weights (FASW) [41], Improvement of Stereo Matching (ISM) [42], PieceWise Cost Aggregation Semi-Global Matching (PWCA-SGM) [43], Segment-based Disparity Refinement (SDR) [44], Adaptive Weighted bilateral filter Processing on Stereo Matching (SM-AWP) [45], Sparse Representation for Suitable and selective Stereo Matching (SMSSR) [46], Two-branch Convolutional Sparse Coding Stereo Matching (TCSCSM) [47], and Ref. [48]. All these methods were proposed after the year 2018. The qualitative and quantitative comparison results are shown in Fig. 15 and Table 7. During our experiments, we used 1p perfect images (Adirondack, Jade Plant, Motorcycle, Piano, Pipes, Playroom, PlaytableP, Recycle, Shelves, and Teddy) without any interfering factors. In Table 7, our method achieved the fourth-lowest error rate among all twelve methods. This proves that our method is not inferior to the mainstream methods on large images.

 

Fig. 15. Comparison of disparity maps generated from different algorithms on Middlebury 2014. Error pixels are marked in red. From top to bottom are the results of 3DMST-CM [38], CBMV-ROB [39], DAWA-F [40], FASW [41], ISM [42], PWCA-SGM [43], SDR [44], SM-AWP [45], SMSSR [46], TCSCSM [47], Ref. [48], and our proposed method. Images from left to right are Adirondack, Jade Plant, Motorcycle, Piano, Pipes, Playroom, PlaytableP, Recycle, Shelves, and Teddy. Best viewed with zoom-in on a digital display.

Download Full Size | PDF

Table 7. Average Error Rates of the 10 Images on Middlebury 2014 Data Sets in Non-occluded Regions^a

View Table | View all tables in this article

4. CONCLUSION

In this paper, we present a novel accurate stereo-matching approach with multi-scale fusion and multi-type support region. We propose a fusion-based cost aggregation method and a multi-scale disparity map merging strategy. Under this method, we can obtain as many correct disparity values as possible in texture-free regions for the primary disparity map. During the disparity refinement procedure, we define three types of support regions that can consider both the local and global information to refine the disparity map. Furthermore, we also define a new weight assignment strategy to refine the disparity values in edge regions. Evaluation shows that the proposed method obtains highly accurate disparity maps, and it is currently superior to many state-of-the-art methods on the Middlebury 2006 data set. There are certainly still some disadvantages to our method; as a type of local method, our method does not obtain the highest score on high-resolution Middlebury 2014 stereo images, and the error disparities always lie in the slant regions with obvious depth discontinuity. In the future, we would like to solve these problems.