Abstract This paper presents a novel tree-based cost aggregation method for dense stereo matching. Instead of employing the minimum spanning tree (MST) and its variants, a new tree structure, ”Segment-Tree”, is proposed for non-local matching cost aggregation. Conceptually, the segment-tree is constructed in a three-step process: fifirst, the pixels are grouped into a set of segments with the reference color or intensity image; second, a tree graph is created for each segment; and in the fifinal step, these independent segment graphs are linked to form the segment-tree structure. In practice, this tree can be effificiently built in time nearly linear to the number of the image pixels. Compared to MST where the graph connectivity is determined with local edge weights, our method introduces some ’non-local’ decision rules: the pixels in one perceptually consistent segment are more likely to share similar disparities, and therefore their connectivity within the segment should be fifirst enforced in the tree construction process. The matching costs are then aggregated over the tree within two passes. Performance evaluation on 19 Middlebury data sets shows that the proposed method is comparable to previous state-of-the-art aggregation methods in disparity accuracy and processing speed. Furthermore, the tree structure can be refifined with the estimated disparities, which leads to consistent scene segmentation and signifificantly better aggregation results.