تکراری برنامه ریزی و منطقه بندی فرعی درخت چهار گانه پویا برای تطبیق استریو سریع

The application of energy minimisation methods for stereo matching has been demonstrated to produce high quality disparity maps. However, the majority of these methods are known to be computationally expensive requiring minutes of computation. In this paper, we propose a fast minimisation scheme that produces high quality stereo reconstructions for significantly reduced running time, requiring only a few seconds of computation. The minimisation scheme is carried out using our iterated dynamic programming algorithm, which iterates over entire rows and columns for fast stereo matching. A quadtree subregioning process is also used for efficient computation of a matching cost volume where iterated dynamic programming operates on.

The study of computational stereo has undergone intensive research since its inception in the 1970s. Stereo matching is the main step for the recovery of the 3D structure of the scene given a pair of images. By matching primitives such as points, curves and regions between the stereo pair, such that the matched primitives are projections of the same 3D identity in the scene, a disparity map of the scene can be computed. While simple local correspondence methods have the advantage of low computational complexity they suffer from high sensitivity to matching ambiguity and the choice of matching metric. Reconstructions based on simple local correspondence can be improved by incorporating global constraints and structural information into the stereo matching process. One such class of global correspondence methods are those based on dynamic programming (DP). Since the dynamic programming framework allows efficient optimal solutions, it has been applied to locate the path of minimum matching cost for each scanline of the image [1], [2] and [3]. However, since DP is typically applied independently to each scanline, methods that employ this technique suffer from interscanline inconsistencies. Several studies have addressed this issue by applying postprocessing to iteratively improve the reconstruction, enforcing interscanline constraints. These techniques include minimising the number of horizontal and vertical discontinuities [4], estimating vertical slopes [5], and using edge maps [6]. These methods attempt to retain the computational benefits of a dynamic programming formulation while avoiding the problem of horizontal streaking. However, while these heuristics improve interscanline consistencies they do not entirely solve the problem. Another class of global correspondence techniques are those that formulate the stereo matching problem into a two-dimensional energy minimisation framework. By designing an energy functional whose minima will correspond to good stereo reconstructions, the aim is to compute a disparity function that minimises this energy. Geman and Geman [7] applied simulated annealing to minimise the energy function. Sun [8] proposed a two-stage dynamic programming technique to compute disparity surfaces of maximum total correlation. In recent years algorithms based on graph cuts and iterated graph cuts have been proposed to solve the optimisation problem [9], [10], [11], [12], [13] and [14]. Graph cut methods produce excellent results at the cost of orders of magnitude greater computation than dynamic programming techniques. In many stereo matching algorithms, there is a need to evaluate the similarity or other metric values for matching points. Metric values evaluated for all overlapping regions of interest between the stereo pair defined by the window size and disparity range can be constructed into a matching cost volume. For fast stereo matching, efficient computation of a matching cost volume is essential. Faugeras et al. [15] developed a recursive technique which is invariant to the size of the correlation window to calculate correlation coefficients. Sun [16] applied the box-filtering technique to achieve fast cross correlation computations. Efficient algorithms have previously been proposed to compute the full matching cost volume by processing the entire image simultaneously. Sun [8] proposed a rectangular subregioning algorithm in order to reduce the computation cost when constructing the matching cost volume. By subregioning the images into rectangular regions optimised for minimal computational load, the reevaluation of the banded cost volume at each finer scale can be computed efficiently and quickly. However, there are situations where the rectangular subregioning process is not optimal. In this paper, we present two new techniques for fast stereo matching. We propose an iterated dynamic programming (IDP) algorithm which minimises an energy function that incorporates both intrascanline and interscanline regularity. Although our energy minimisation method is also based on DP, the use of a multi-directional smoothing energy prevents streaking. This framework overcomes the interscanline inconsistency problem inherent to DP techniques and produces comparable results to existing energy minimisation algorithms. Hence, we propose IDP as a new alternative for minimising general energy functions of the form to be described in Section 2. We explain theoretically and demonstrate with results that the proposed algorithm is efficient and a competitive energy minimisation scheme. We also propose a quadtree subregioning (QSR) algorithm that segments stereo images into subregions for the fast computation of the matching cost volume in a multiscale framework. We improve on previous techniques and present a quadtree partitioning scheme that efficiently evaluates a banded cost volume. In Section 4, we present timings and results to demonstrate the quality and speed of the proposed techniques. Initial work by the same authors was presented in [17].

We have presented a new algorithm, iterated dynamic programming, for fast stereo reconstruction. Taking advantage of dynamic programming’s ability to compute the optimal multi-labelling of a one-dimensional energy function, we proposed an iterated dynamic programming scheme that can minimise a discontinuity-preserving energy function. We have also presented an algorithm for the fast computation of the cost volume by computing an optimal quadtree subregioning of the disparity image. Results have been presented and compared to existing stereo energy minimisation algorithms. These results demonstrate that iterated dynamic programming is strongly competitive in terms of quality with graph cut techniques while maintaining the computational advantages of dynamic programming techniques. Combined with quadtree subregioning, iterated dynamic programming computes high quality reconstructions in seconds rather than minutes. The quality and speed of our reconstructions establish iterated dynamic programming as a competitive energy minimisation scheme for stereo matching.