ObstacleDetection Using Stereo Matching

一、摘要

Stereo Matching 是利用左右兩台攝影機模擬雙眼，由左右兩張影像的disparity來算出物體深度。關於這次專題的內容，主要是希望提高計算 disparity 的速度，參考了幾篇 paper 的方法，試著將它們結合。

算disparity可以視為解Markov Random Field的問題，專題中是用Belief Propergation(BP)來估計disparity。在 ”Implementation of BP for Early Vision” [1] 中提供了一個降低 BP 複雜度的演算法，在 “Bilayer Stereo Matching”[2] 中則是運用了 bitwise 的概念，把 label 換成二進位，一個一個 bit 算，同時為了提高準確度，提出了 bilayer 的方式，把 label 值分為前景和背景兩個範圍，分別對全圖的每個點算出最適合的值，再算出各個點是前景還是背景。這次就是結合這兩個方法。

二、方法概述

1. Belief Propagation

計算 disparity field 可以視為找出 Markov random field (MRF) model 裡最適合的 label 值使得 energy function 為最小。

上面為 energy function的式子，N是所有把相鄰兩點連接起來的 edge， P 是圖上的所有點, f 是 label 值 f_p 和 f_q 分別為 p, q 兩個 node (這裡代表兩個相鄰的點) 的 label 值， D_p(f_p)為點 p 的 label 值為 f_p 的 cost, ) , V(f_p, f_q) 則是相鄰的兩點 p, q 的 label 值為 f_p, f_q 時的 cost。

這邊我們是用 belief propagation 來解 MRF model，BP 的式子主要如下:

m^t_pq 為點 p 傳給點 q 的 message，前一次的結果都會影響下一次的結果，是遞迴的計算，經過Ｔ次後，每一點都會決定一 p f 使得 p b 的值收斂為一最小值，這樣的方式在有 n 點，k 個可能的 label 值時，所需的時間為O(nk²T)

2.Efficient Belief Propagation

這是[1]中提出的方法，這裡我稱之為 Hierachical BP，主要有下列幾點改進：

(a)computing message

原來的BP每一次都要花O(k²)才能決定一m_pq，由於V(f_p, f_q)是建立在f_p, f的差異上我們使用下列式子：

再加入truncated linear model:

依照以上的式子，使用下列演算法：

Time Complexity 變為O(k)

(b)multiscale BP

miltiscale 方法是把原來的圖分層很多層，上層的一個node代表著下層的許多node，計算結果從粗略到精準，方法如下圖 level 1 的一個 node 代表了 level 0 的四個 node。上層計算的初始值就是下層收歛的結果，這樣的方式可以加快原本 BP 傳遞 message 所需的收斂時間，也就是降低 T。

3. Bitwise Algorithm

這方法是[2]裡面提出的，一次決定 label 的一個 bit，若label有k個可能的值，原本要 O(k)，現在就只要 O(logk)，以下是[2]中的演算法，我把裡面graph cut的方法改成用 HBP：

4. Bilayer Stereo Matching

最後我們再利用 bilayer 方式，改善得到的結果，主要的方式是把 disparity 分成前景和背景的範圍，分別找出在每點機率最大的值，再用前背景得出的值決定每一點是前景還是背景記錄在 intermediate layer 的 label 當中，在專題的作法中，每次都是用 BP 去決定 label 值，所以總共是做了三次的 BP ，而整個流程如下：

而能改善的原因，主要是因為當沒有分前背景時，傳遞 message 時，在物體邊界的部分（前背景的交界）屬於背景範圍的 disparity 值，會影響到前景的部份，反之亦然，把前背景分開處理後，問題就減少了。另外，在我們做障礙物偵測時，我們正好可利用 intermediate layer 的資訊，把前景的部分視為障礙物。

三、結果比較

1. bitwise

以下是 bitwise 的結果

2. 結果比較

以下是 HBP，bilayer，單純Bitwise HBP，還有intermediate layer 的結果

3. 時間比較

下表為三種方法的所花時間(s)

可以發現當 label 數越大時， bitwise 加速的效果就越明顯，加了 bilayer 後，Teddy 和 Cones 的時間還是比沒用 bitwise 來的短。

4. 結果評測

下表是在 middlebury 網站[3]上所做的評測

可以發現，加了 bilayer 後，的確改善了 bitwise 的結果，但還是比 Hierarchical BP 差了一點。

四、結論

利用 BP 來解 MRF model 所需的時間受到 label 數和 node 數( 圖片大小 ) 的影響最大，而在 label 數的部份，使用 bitwise 的方法，降低了 complexity，圖片大小方面，則是利用 multiscale 使得所須計算的次數減少，根據實驗結果可以發現，當圖片越大，label 範圍越廣時，我們結合了兩個演算法，確實加速了不少。而另一方面，利用 bilayer 的技巧，不僅可以提高我們結果的準確度，同時前背景的分離，正好可以作為障礙物偵測的一個依據。

五、參考資料

[1] Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Efficient Belief Propagation for Early Vision. 2004
[2] Dengfeng Chai and Qunsheng Peng. Bilayer Stereo Matching. 2007
[3] http://vision.middlebury.edu/stereo/