# Linear Time Non-Local Cost Aggregation on Complementary Spatial Tree Structures
## 4 Results and Discussions
### Stereo Matching
#### 4.1.2 KITTI Dataset  
Both KITTI 2012 [25] and KITTI 2015 [26] datasets are real-world street views of both highways and rural areas captured by a driving car under natural conditions since there is a large portion of textureless regions in these stereo pairs. We adopt both the _Census Transform_ and the correlation of deep features extracted by CNNs to compute matching costs and then evaluate the performance of these two cost functions under different cost aggregation methods. The main idea of _Census Transform_ is to use a string of bits to characterize the pixels in the local window. We suppose the size of the local window is \((2m+1)\times(2n+1)\); thus, the _Census Transform_ of pixel \((i,j)\) can be defined as  
\[CT(i,j)=\mathop{\otimes}\limits_{l=-m}^{m}\mathop{\otimes}\limits_{k=-n}^{n} \xi(I(i,j),I(i+l,j+k)),\quad\text{where}\quad\xi(I_{p},I_{q})=\left\{ \begin{array} []{ll}1,&ifI_{p}\leq I_{q}\\ 0,&ifI_{p}>I_{q}\end{array} \right., \tag{10}\]  
where \(CT(i,j)\) is the string of bits for pixel \((i,j)\) after _Census Transform_ and \(\otimes\) is the bit-wise concatenation operation. The Hamming distance of two strings of bits is utilized to measure the similarity of pixels. The matching cost of pixel \((i,j)\) at disparity \(l\) is  
\[C_{i,j}^{h}(l)=\sum H(CT\_(i,j),CT^{{}^{\prime}}\_(i+l,j)), \tag{11}\]  
where \(CT\) and \(CT^{{}^{\prime}}\) are the two strings of bits for matching pixels in the left and right images, \(H(\_)\) is the operation to calculate Hamming distance, and \(C^{h}\) indicates the matching cost of the handcrafted feature. As for features extracted by CNNs, we directly use the correlation of left and right features to evaluate the similarity of matching pixels. The PSMNet [24] combines spatial pyramid pooling and dilated convolution to enlarge the receptive field. The resultant local and global features aggregate context information at different scales and locations and are widely used in many state-of-the-art methods [23; 30; 31]. We also use the PSMNet to extract deep features in our experiments. We denote the learned features as \(\Psi\), so the matching cost of pixel \((i,j)\) at disparity \(l\) can be expressed as  
\[C_{i,j}^{l}(l)=\frac{\sum_{k=1}^{M}\Psi_{ij}(k)*\Psi_{i+l,j}^{\prime}(k)}{\| \Psi_{ij}\|_{2}\|\Psi_{i+l,j}^{\prime}\|_{2}}, \tag{12}\]  
where \(C^{l}\) is the matching cost of features extracted by CNNs, \(\Psi\) and \(\Psi^{{}^{\prime}}\) represent the deep features of left and right images, \(\|.\|_{2}\) is the \(L2\) norm. Typical cost aggregation methods are utilized to improve the robustness of matching costs. In the refinement step, the left-right  
Figure 3: Results of typical cost aggregation methods on the Middlebury dataset [8]. Mismatched pixels in occluded and non-occluded regions are indicated by red and green, respectively. (**a**) Input image. (**b**) Bilateral filter [29]. (**c**) Guided filter [13]. (**d**) Non-local filter [16]. (**e**) Fully connected guided filter [18]. (**f**) Our method. consistency check is used to identify mismatched pixels, and those mismatched pixels are assigned to the lowest disparity value of the spatially closest matched pixels on the same scanline. Finally, we adopt the weighted median filter to remove streak artifacts. The error threshold in our evaluation is 3. Qualitative evaluation: Figures 4 and 5 present a comparison of GF and our method using two kinds of features to compute the matching costs on the KITTI 2012 and KITTI 2015 datasets. GF can effectively filter out noise in textured regions by taking advantage of local structure in the guidance image but fails to preserve fine-scale details in real-world stereo pairs. The reason is that the intensity difference between foreground and background is indistinctive in many cases since the local linear regression model used in GF cannot accurately distinguish fine-scale details from background. Moreover, GF fails to filter out the noise in large homogeneous regions, such as the sky.