使用於立體視差估算之快速圖形切割演算法

Abstract

視差估算在3D視頻處理系統中是其中一個關鍵的因素。許多技術已經被提出來計算視差圖，圖形切割演算法是一種公認較好的視差估算計畫。然而，圖形切割演算法具有很高的計算複雜度。 在這篇論文中，我們提出了一個用於視差估算的快速圖形切割演算法，有兩個加速的技巧被提出：一個是提前終止規則，另一個是排出α-β交換對的搜索的優先順序。我們的模擬結果表現，當我們跟原始方法比較，該演算法可以加速68%的平均運算時間。同時，視差圖的品質可以保持在幾乎跟原始方法一樣。 另一個加速技術，我們是採用多解析度的方法。一開始我們先對原始影像降頻取樣，並針對低解析度的影像作視差估算，產生低解析度的視差圖。接著，我們再對低解析度的視差圖做升頻取樣，並以此視差圖作為初始值去做原始解析度的視差估測，我們去測試幾種降頻取樣及升頻取樣的方式，並找到最佳的組合。我們的模擬顯示，多解析度的圖形切割演算法只使用原始計算時間的的16%，而壞像素的升幅只有1%。我們研究的最後一個主題是使用多相機拍照的視差估測，初步觀察顯示了一些有趣的結果，我們需要進一步的實驗才能發揮這主題的優勢。

Disparity estimation is one of the critical elements in a 3D video processing system. Many techniques have been proposed to calculate the disparity map from a pair of images and the graph cut (GC) algorithm is one of the recognized better disparity estimation schemes. However, GC has a very high computational complexity. In this thesis, we propose a fast GC algorithm for disparity estimation purpose. Two accelerating techniques are suggested: one is the early termination rule and the other is prioritizing the α-β swap pair search order. Our simulations show that the proposed fast GC algorithm can reduce 68% computing time on the average, when compared with the original GC scheme. Meanwhile, its disparity estimation performance is about the same as that of the original GC. Another speed-up technique we adopt is the multi-resolution approach. The original images are down-sampled and a low-resolution disparity map is first estimated. Then, the low-resolution disparity map is up-sampled as the initial values for estimating the disparity map of the original images. Several down-sampling and up-sampling filters are tested to find the best combination. Our simulation shows that the multi-resolution GC (MRGC) algorithm uses only 16% of the original computing time and the bad pixel probability increases only by 1%. The last topic we investigate is disparity estimation using multi-camera pictures. The initial exploration shows some interesting results. Further investigation is needed to fully take the advantage of multiple images recoded by a camera array.