Architecture Design of Belief Propagation for Disparity Estimation

科技改變生活，這是當下一句廣告，同時也反映了我們真實的生活狀態。從蘋果公司開創個人電腦時代開始，再到以Cisco為代表的網路設備公司打開了互聯網的大門，隨後又進入到以Qualcomm為代表的移動通訊時代。最近的5年，智能手機呈現井噴式成長，在移動互聯網的大背景下，以智能手機為代表的個人便攜式計算終端逐漸趨於成長末端。而以VR或AR為技術背景的計算體驗平台仿佛預告了下一個計算終端的爆發點，在這些視覺體驗應用中，對於3D效果的要求是非常直觀和迫切的。而視差預測便是其中的一部分。 視差預測可以在數學上轉化為一種基於二維馬爾科夫隨機場的能量最小化問題。目前有眾多演算法可以解決視差預測問題，例如：動態規劃算法、圖割算法、置信度傳遞算法等等。其中置信度傳遞算法在提供了較高的景深圖像品質的基礎上之外，其演算法本身具有規整運算的特性，從而使置信度傳遞算法從眾多方法中脫穎而出，很適合使其ASIC化。就置信度傳遞演算法而言，它的核心思想是假設每個像素的深度值與除去自身外，周圍所有的像素深度值呈現關聯，透過像素之間的置信度傳遞以及迭代，從而決定出本像素的深度值。 在此論文中，我們首先介紹了一些基於視差預測的應用，例如：VR和AR；以及目前市面上移動終端平台。隨後我們會介紹在視差預測中的一些基礎問題，包括立體視覺問題、關於深度和視差的定義以及關於二維馬爾科夫隨機場的簡介；其次我們探討了關於多種用於視差預測的演算法，簡要提及動態規劃算法、圖割算法與信度傳遞算法的對比，然後詳細地描述并分析了信度傳遞算法其中多個參數對結果的影響。再其次我們通過軟體上對信度傳遞算法的分析，對其進行子系統劃分使其方便的進行ASIC架構設計。隨後基於信度傳遞算法整體的架構劃分，對其中的幾個系統子架構進行了詳細的描述，並與最後對ASIC化之後的結果進行分析。 總結而言，我們在信度傳遞算法的基礎上，針對算法中的關鍵部分進行了實驗分析，以此為準設計出一套與此對應的硬體架構；使得此硬體系統架構能快速地處理視差預測問題。Technology changes life, and this is a sentence form advertisement, it reflects the real lief of ours. From Apple to create the personal computer era, and then to the Cisco network equipment company, represented by opening the door of the Internet, then entered into with Qualcomm as the representative of the era of mobile communications. Last five years, smartphone blowout type growth in the context of mobile Internet, smart phones as the representative of the personal portable computing devices tend to grow gradually end. And in VR or AR for the technical background of the computing experience platform seems to notice the flash point of the next computing terminal, 3D effecte requirements in these applications are very intuitive and urgent. The disparity estimation is a part of the problem. For abovementioned applications, disparity estimation is the key technology to obtain 3D information. Stereo vision approach is more power efficient which is more suitable for mobile devices than structure lighted and Time-of-Flight (ToF). Among existing global optimization algorithms, Field is widely discussed because of its promising performance. Disparity estimation can be transformed into a prediction based on 2D field with energy minimization problem in mathematics. There are many algorithms which can solve the disparity estimation problems, such as: dynamic programming algorithm, graph cut algorithm, belief propagation algorithm, and so on. Belief propagation algorithm provides a good quality depth map of the image, the algorithm its computation is regular, so that the belief propagation algorithms different to other algorithms, making it very suitable for implementation as ASIC. The belief propagation algorithm, it assumed that the depth value for each pixel related to itself and all of the values of surrounding pixel, passed through the belief value and iteration between pixels to determine the present depth values of the pixels. In this thesis, the character of Belief Propagation is reanalyzed. A disparity estimation engine supports full-HD 60 fps is proposed. According to the software experiment, the proposed disparity range is set to 64, and so is other parameter setting. In order to support the full-HD 60 fps specification, in some parts of architecture design insert 2-Pipeline. As the result, the proposed architecture improves operation frequency in almost 300%