# Linear Time Non-Local Cost Aggregation on Complementary Spatial Tree Structures
## 3 Implementation and Complexity  
Our method performs cost aggregation along two complementary spatial trees, namely _Tree 1_ and _Tree 2_ in Figure 1a,b. The spatial distance and the intensity difference between pixels in the eight-connected neighborhood are computed first to obtain the weights in recursive filtering procedures. The cost aggregation on each tree is implemented by filtering along eight sub-trees, and the final aggregated cost of our approach is the sum of outputs from these two trees.  
As the computational costs of performing cost aggregation on our two complementary spatial tree structures are the same, we elaborate on the computation required by perform  
\begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Method** & **Tree Building** & **Implementation** & **Spatial Distance** & **Eight Neighborhood** \\ \hline NL [27] & Yes & Recursive & Along MST & No \\ ST [17] & Yes & Recursive & Along segment-tree & No \\ DT [19] & No & Recursive & Row and column & No \\ Ours & No & Recursive & Row/Column and diagonal & Yes \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of typical non-local filtering methods. Tree building: if extra computation is needed to build a tree structure. Implementation: the way to implement the filtering procedure. Spatial distance: the way to evaluate spatial distance between two pixels. Eight neighborhood: if messages propagate along eight directions.  
Figure 2: Filtering results of different tree structures. (**a**) Input image. (**b**) Result of filtering along the MST. (**c**) Result of filtering along _Tree 1_. (**d**) Result of filtering along _Tree 2_. (**e**) Result of filtering along both _Tree 1_ and _Tree 2_. The blue arrows indicate the fake edges among sub-trees generated in the MST, and the red arrows indicate the streak artifacts when only filtering along one of our complementary spatial trees.  
ing cost aggregation on _Tree 1_, and the total computational cost of our method is twice that performing cost aggregation on _Tree 1_. From Equation (1), we can see that it needs four _multiplication_ operations and four _addition_ operations to obtain support from pixels located in the same row and column. Equation (2) needs four _multiplication_, four _subtraction_ operations, and another eight _addition_ operations to compute the support from pixels on sub-trees in diagonal directions. The fusion of the outputs from eight sub-trees in Equation (3) needs three _subtraction_ and seven _addition_ operations. Hence, seven _subtraction_, eight _multiplication_, and nineteen _addition_ operations are required to calculate the aggregated cost of each pixel at each disparity level on _Tree 1_. As the computational complexities of performing cost aggregation on _Tree 1_ and _Tree 2_ are the same, our method has linear time complexity. Supposing the resolution of the reference image and the candidate disparity space are \(N\) and \(L\), the computational cost of our approach is \(O(NL)\) time.  
Table 2 presents a running time comparison of typical edge-aware filtering approaches for one cost slice on a laptop with 2.0 GHz and 8 GB RAM. Both NL and ST extract tree structure from the reference image and recursively traverse the tree structure in two passes to aggregate informative messages across the whole image since they have the same computational complexity. The divergence of running time between NL and ST is due to different strategies adopted to implement the filtering procedure. GF needs to invert a three-by-three matrix when computing the filtering output for the color reference image. FCGF extends the support region of GF to the whole image to build complicated geometric structures of the input image. Although FCGF still has linear time complexity, the running time of FCGF is multiple times that of GF. Both spatial affinity and radiometric difference are utilized in BF to define the weights between neighboring pixels since the computational cost increases dramatically as the size of the support window rises.