A Disparity-prediction-based Hierarchical Accelerator For Tree-based Stereo Matching Algorithms

Stereo matching is one of the most important topic in computer vision. It extracts depth information, i.e., disparities, from two or more stereo images to generate accurate disparity map. Speed remains a significant challenge in stereo matching, especially for real-time applications. Among different categories of stereo matching algorithms, tree-based stereo matching has already reduced the complexity to O(N˙dmax) by employing the tree structure, where N is the number of pixels and dmax is the input maximum disparity. However, the previous tree-based algorithms, mostly hindered by the greediness of minimum spanning tree(MST), provide poorly adaptive support windows and have bad performance on curved and slanted surfaces. In this paper, we propose a hierarchical Disparity-Prediction-Based Accelerator(DPA) for tree-based stereo matching algorithms which is a general framework that dramatically speeds up the typical tree-based stereo matching methods and improve their accuracy at the same time. The DPA framework aims at reducing the complexity by doing cost computation,cost aggregation and disparity computation in a smaller possible interval of disparities.We carried out extensive results over Middlebury, KITTI as well as a Low Quality datasets demonstrated the effectiveness and efficiency of our DPA framework.Three contributions are presented in this paper:1. A novel concept of Disparity Intervals, i.e., the intervals of possible values for the true disparities(It’s highly probable for the true disparities to fall within the Disparity Intervals and nearly impossible for them to fall outside). Our core idea is to predict credible Disparity Intervals so that we can calculate and aggregatematching cost, find optimal disparities and refine the raw disparities within these small intervals only, rather than over the large full allowed disparity range and thus reduce the high computational efforts.2. A novel disparity prediction model(DPM) to predict the distribution of possible disparities, which can help construct Disparity Intervals of a larger-scale image based on the calculated disparities of a smaller-scale image.3. A hierarchical Disparity-Prediction-Based Accelerator(DPA), which is actually a general framework for tree-based stereo matching algorithms. With a little change in the original algorithm, an original tree-based algorithm can be fitted into our framework, and its accuracy and speed can both be dramatically improved. Specifically, for large-scale images, the speed is about 7-10 times faster than the tree-based algorithms after fitted into DPA framework.