雙眼視差影像深度資訊生成演算法和架構設計

Algorithm and Architecture Design for Stereo video depth generation

賴彥傑(YEN-CHIEH LAI)

指導教授 ： 陳良基

國立臺灣大學/電機資訊學院/電子工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.02488

摘要

擁有雙眼視差的影片目前已成為立體影像的主流，若要將之利用在多視角的立體顯示器，仍需要有深度資訊的生成，以提供給後段生成多視角影像使用，相較於傳統平面影像，還原擁有雙眼視差的影像能提供較高品質的深度資訊，立體場景較能完整呈現，可帶給人們更深的立體感受。
本篇論文利用立體場景在兩個不同的相機擺設之下，會投影出不同的視差的原理，我們只要能找出視差大小，即可還原立體場景，找尋深度資訊。
我們並且使用了圖像模型中整體最佳化的方法，提供高品質的深度資訊。我們使用了信賴傳遞(Belief propagation)的方法，利用雙眼視差偵測的方式，完成對一個帶有雙眼視差的影片生成深度資訊。信賴傳遞演算法主要是考量每一節點與鄰近節點的相互關係，配合節點本身可能的機率分布，決定最佳的深度資訊。再利用節點之間的訊息傳遞，達成最後收斂的效果，找出一組最佳的深度資訊，進行深度修補步驟。我們根據之前原始信賴傳遞演算法，提出方格信賴傳遞演算法，相較於原始做法，我們的演算法能大幅節省記憶體的使用量，並能保有訊息交換的資訊。我們並針對複雜度的簡化提出了快速訊息計算方法，能大量降低運算複雜度。另外我們也針對大量的訊息儲存量，提出嶄新的信賴傳遞過程，亦能保有效能，又能在硬體架構上實行。我們亦針對雙眼視差模型上的限制，完成深度資訊內插的演算法，克服基本限制，完成最佳的效能。我們並在硬體架構上，提出多階段平行化計算流程，完成即時針對高畫質雙眼視差影片的深度資訊生成。

關鍵字

雙眼視差 ； 深度生成

並列摘要

Digital video technology has played an important role in our daily life. With the evolution of the display technologies, display system can provide higher visual quality to enrich human life. As 3D display technology matures, human aspires to experience more reality. The 3D video signal processing has become an active topic in the visual processing field. The depth generation from content is one of the important parts in 3D video processing. One typical way is the 2D-to-3D conversion focusing on extracting the depth information from the 2D image. The other topic focuses on the depth generation system from stereo-views sequence. Compared to the 2D-to-3D algorithms, the depth from stereo-view sequence can provide the better depth quality and is more suitable to reconstruct the virtual view. The depth generation from stereo-views system can be applied to the multi-view 3D displays and the free viewpoint display system.
In depth generation from stereo-views system is based on the stereo matching algorithm. Stereo matching can be formulated as an energy minimization problem on a 2D Markov Random Filed(MRF). Among many MRF global optimization method, belief propagation gives high quality and has highly potential to achieve real-time processing. However, because of costly iterative operations and high memory and bandwidth demand, the original belief propagation is computationally expensive for real-time system implementation.
In this thesis, we focus on the algorithm and hardware architecture design of stereo matching and depth generation from the stereo vision. In first, we analyze the hardware cost in the stereo matching and belief propagation system, and indicate the challenge and bottleneck in the memory and bandwidth resource requirement. Secondly, we propose tile-based belief propagation and message reduction algorithm to greatly reduce the memory and bandwidth cost and provide similar performance compared to the original belief propagation. Moreover, we design the fast message computation PE for belief propagation to reduce the complexity of message construction. Third, we propose the trilateral-filter-based depth post processing to correct the error in the occlusion region and overcome the matching constraint in the stereo vision. We Finally, an efficient VLSI architecture of real-time, high-performance stereo depth generation system is presented. The design combines the fast message computation method, the tile-based BP, message reduction ,with the trilateral-filter-based post processing to create a parallel and flexible architecture. These techniques include a 4-stage pipeline, fully-parallel processing elements for message update, and a data reuse scheme. When operating at 227 MHz, the architecture can generate HDTV720p disparity maps at 30 fps.

並列關鍵字

STEREO MATCHING ； BELIEF PROPOGATION

參考文獻

[13] S. Kimura, T. Shinbo, H. Yamaguchi, E. Kawamura, and K. Nakano, “A convolver-based real-time stereo machine (SAZAN),” in Proc. IEEE Comput. Soc. Conf. Comput. Vision Pattern Recognit., Fort Collins, CO, vol. 1. Jun. 1999, pp. 457-463.

[1] Redert, A.; de Beeck, M.O.; Fehn, C.; Ijsselsteijn, W.; Pollefeys, M.; Van Gool, L.; Ofek, E.; Sexton, I.; Surman, P.; , "Advanced three-dimensional television system technologies," 3D Data Processing Visualization and Transmission, 2002. Proceedings. First International Symposium on , vol., no., pp. 313- 319, 2002

[2] C.Fehn “A 3DTV system based on video plus information”, 37th Asilomar Conf. Signals. Syst. Comp., 2003

[3] H. Hirschmuller and D. Scharstein, “Evaluation of stereo matching costs on images with radiometric differences,” in IEEE Trans. PAMI, 2009.

[4] Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” in IEEE Trans. PAMI, vol. 23, no. 11, pp. 1222-1239, 2001.