Algorithm and Architecture Design for Disparity Map Generation

In recent years, automobile electronics becomes a popular topic. The main reason is that we hope driving can be safer and more convenient for drivers. There are two parts of automobile electronics, including inside and outside parts. The inside part for example: fatigue detection and road information. On the other hand, outside part contains lane departure warning, collision avoidance and so on…. This thesis focuses on the front end of collision avoidance which estimates the distance between object and camera on the car. Our system is designed to avoid the collision against object which includes horizontal displacement. Therefore, the target of the front end of system is to find out the position and movement of these objects. First, we use SOBEL edge detection to find out the edges as our features because the collision occurs on these vertical edges. Another reason is the disparity of these vertical edges is more reliable when we generate disparity map. Then we use pyramid scale image to match the point from left view and right view. It can save a lot of computational time by reducing the window size and search range simultaneously. Finally, we check if the disparity map of left view and the disparity of right view are the same. After this step we can get a more reliable disparity map. When disparity map is done, we can directly get the distance between object and camera with the disparity value and the parameter of camera. However, there are some differences in real situation so that we must correct the formulation by an experiment. Because of the long processing time by software, we design VLSI architecture to perform block matching which takes the most time to compute disparity map. The search range and window size of the block matching is 64 and 13x13, respectively, so we design 64 processing units which can be divided into 5 groups. Therefore, hardware can perform block matching for full search at the same time. The spec for block matching circuit is 30 frames per second, 1080P resolution and operating frequency at 62.21MHz. And we implement the chip using TSMC 90nm.近年來車用電子不斷的受到重視，最主要的原因是希望能夠透過車用電子的輔助，讓駕駛人行車更加方便或安全，車用電子又分為車內與車外兩個部分,車內的如:疲勞偵測、道路訊息;車外部分則有車道偏離、防碰撞等等….此論文主要研究內容是屬於車外的防撞系統的前端的距離估測部分，影像式的車外防撞系統主要是抓取物體，並追蹤判斷是否造成危險並且提醒駕駛人。而我們的系統是針對水平移動的物體去預防碰撞適用於車速為50 km/hr以下的情況，在系統的前端部分是要計算物體的位置和運動情形。 首先，我們將物體先利用垂直邊緣法將垂直邊緣給找出，因為碰撞最先發生的地方是邊緣部分且視差也較為可靠，因此用物體的邊緣來取代整個物體，接著為了節省匹配造成的的龐大運算量，我們採取階層式的匹配將畫面先降取樣並且從較低解析度之影像開始做匹配，在同時降低視窗大小與搜尋範圍的情況下，省下的運算量大約為80%，是非常可觀的，經過匹配後再透過左眼影像視差與右眼影像視差做交叉比對將可靠的視差留下，最後可以得到一張基於邊緣部分的視差圖。 有了視差值理論上可以透過攝影機參數獲得該物體與攝影機之間的距離，但是理論值與實際值必定會有些誤差，因此透過實驗將真實的關係找出並且對誤差進行補償，如此一來便可以得到較為精確的結果，達到測距的目的。 因為軟體處理的時間過長，故本論文針對運算量最多的區塊做硬體化來加速運算，硬體架構設計方面，由於區域匹配需重複計算SAD值和搜尋範圍一樣多次(64)，且每次比對都必須計算視窗大小(13*13)次數的差值絕對值累加，因此我們設計64套的區塊匹配電路並分成5組，達到同時計算整個搜尋範圍的SAD值，且資料傳遞也可以達到重複使用的目的。我們提出規格為在一秒鐘就必須處理1920*1080*30點資料(寬度1920;高度1080;每秒30張畫面)，也就是說我們工作頻率為62.21MHz。實作上則採用TSMC 90nm 製程。目錄 第一章 引言 1 一、 車用防撞系統 2 二、 影像測距技術 4 三、 6D防撞系統 7 四、 論文組織 11 第二章 雙眼視差資訊相關理論與文獻 12 一、 視差圖的產生 12 二、 視差圖相關文獻介紹 13 (一) Edge-Directed Hardware Architecture for Real-Time Disparity Map Computation [1] 13 (二) Real-time Stereo Vision for Urban Traffic Scene Understanding [2] 15 第三章 應用於車用防撞系統之視差圖生成與及其模擬結果 16 一、 前言 16 二、 垂直邊緣偵測 17 三、 建立階層式的影像 26 四、 區域匹配 28 五、 將錯誤匹配之畫素排除 35 六、 距離估測 37 (一) 距離估測原理 37 (二) 實驗方法 38 (三) 距離估測結果 48 (四) 誤差檢討 53 (五) 結論 53 七、 模擬結果 54 (一) 模擬結果 54 第四章 硬體架構設計與實作 61 一、 前言 61 二、 硬體規格 61 三、 視差圖硬體架構設計(Disparity Map Architecture Design) 62 四、 各單元之硬體架構設計 63 (一) Edge Detection 63 (二) SAD Computation Unit 65 五、 實作結果比較 67 (一) 數位IC設計流程簡介 67 (二) 晶片規格 68 (三) Layout 圖 73 第五章 結論 75 一、 結論 75 參考文獻 7