本文介紹的文章就是CVPR2013的《Segment-Tree based Cost Aggregation for Stereo Matching》一文，介紹它原因有以下幾點：
1.它是NLCA的變種。
2.它是CVPR的文章。
本文還是從Segment-Tree的算法思想，算法核心，算法效果三方面進行分析，這篇文章的源代碼連結是:https://github.com/kc4271/STCostAggregation
1. 算法思想
Stereo Match是前段時間一直研究的問題，我将主要的精力都集中在了半全局算法上，或者帶有全局性質的局部算法，如上一篇部落格介紹的NLCA（non-local cost aggregation），本文介紹一下NLCA的衍生品，這樣說沒有冒犯作者的意思哈！但是ST（segment tree）确實是基于NLCA的改進版本，本文的算法思想是：基于圖像分割，采用核NLCA同樣的方法對每個分割求取子樹，然後根據貪心算法，将各個分割對應的子樹進行合并，算法核心是其複雜的合并流程。 但是這個分割不是簡單的圖像分割，其還是利用了最小生成樹（MST）的思想，對圖像進行處理，在分割完畢的同時，每個分割的MST樹結構也就出來了。然後将每個子樹視為一個個節點，在節點的基礎上繼續做一個MST，是以作者号稱ST是分層MST，還是比較貼切的！ 算法是基于NLCA的，那麼ST和NLCA比較起來好在哪裡？作者給出的解釋是，NLCA隻在一張圖上面做一個MST，并且edge的權重隻是簡單的灰階差的衍生值，這點不夠科學，比如說，當遇到紋理豐富的區域時，這種區域會導緻MST的構造出現錯誤，其實想想看的确是這樣，如果MST構造的不好，自然會導緻視內插補點估計不準确。而ST考慮了一個分層的MST，有點“由粗到精”的意思在裡面。有圖說明：
a指的是原圖，b指的是局部放大圖，c指的是ST的權重圖，d指的是NLCA的權重圖，這個權重圖指的是， 周圍點對紅色點的貢獻度，越亮代表權重越大。可以明顯看到，在對細節的處理上，ST明顯強于NLCA，例如ST中p1點，其位于低紋理區域，對高紋理區域的貢獻很低很低，這更符合理想狀态。但是MST卻有瑕疵，p1點對其它點的貢獻不具有區域性，綠色三角指向的地方就是瑕疵所在。 産生上述現象的原因是：ST在生成整幅圖MST的同時，事實上也對各個區域生成了MST，便使得單點對其它點的權值，在所位于區域内比較大， 而在不同的區域上往往很小。至于ST是如何做到的，請看下一小節中的解釋。
2. 算法核心
本文的核心部分就是其中的流程圖，最讓人費解的也是這個算法流程，是以本小節重點說一下我對這塊的了解。它将流程分為三個部分，初始化->聚合->連接配接
其實，該算法流行直接采用了文獻《Efficient graph based image segmentation》中提到的全局分割方法，文獻在這裡并沒有進行過多的解釋，隻是一再強調可以去文獻中查閱這篇文章。下面說一下各個步驟的含義。 1. 初始化很簡單，邊先暫且不考慮，将每個像素點形成一個集合T，集合内隻有一個像素點。 2. 聚合比較複雜，需要将邊根據權值由小到大排序，然後對所有的邊進行周遊，與邊相伴随的兩個點要麼合并，要麼不合并，判斷的準則就是邊權值是否滿足下述條件：
如果合并，那麼就要将邊不斷的添加到集合E‘中，最終，E’中存放的都是小樹中的邊，由于後續還需将每個小樹視作一個個節點，重新将小樹連接配接成為一棵大樹，是以需要将E‘從E中删除。 3.剩下的就是連接配接，正如上面所說，連接配接就是将每個小樹視作節點，進一步形成一顆大樹。采用的方法和上面的步驟很相似，對E中的邊進行周遊，這個時候沒有條件的限制，如果兩個小樹不同就得合并，直至E’中邊的個數隻比點的個數少1， 因為樹的邊數就比節點數少1個，是以這裡意味着全圖對應的還是隻有一顆MST，注意，這個E‘沒有重新被清空。
流程就是上面說的這樣，下面提幾個問題： 1）流程圖中合并的集合一直都是Vp，Vq，那麼Vp,q是怎麼處理的？ 2）為什麼聚合之後，就相當于對圖像進行了分割？ 3）終止條件有什麼意義在裡面？ 4）邊權值滿足的門檻值有什麼意義？
以下部分是我的回答： 1). 要回答這個問題，我們不妨思考一下MST的建立過程，你就會發現，原來這個流程圖和MST的差別隻有一處，那就是 “選擇edge的時候，多了一個判斷條件”，其餘的真的是一模一樣，作者故意将流程圖分為三部分，使其看的複雜，其實完全可以說 “我們的算法流程就是普通的基于克魯斯卡爾建立MST + edge判斷條件”，這很滑稽，也是各國論文中無處不在的存在某種問題或陰謀。回到正題，Vp,q變成了一個連通，僅此而已，在代碼上隻要寫parent(Vp) = parent(Vq)即可。說白了，作者忘了多提一句Vp = Vp,q
2). MST建立的時候，隻要發現一個edge兩個端點所屬的連通不一樣，就要将兩個連通合并為一個連通，這裡面的連通就可以了解為這裡的子樹，而ST會考慮edge兩個端點所在連通的差別大小，差別不大就合并，差別大就不合并，你懂了吧？這樣就會将圖像自然的分成一個個區域，因為你有的區域不合并嘛！ 但是，說句心裡話，我覺得作者雖然一直強調ST有這麼優秀的性質，但是并沒有給出嚴格意義上的證明啥的，隻是根據直覺，這有點不靠譜，至少我在做視差圖的時候，發現視差圖并沒有展現出 區域分割的優勢。是以我覺得在此處有過度包裝的嫌疑。
3). 終止條件中的Int(Tp)其實是一種 區域内間距的定義，而k/|Tp|就是一種調節因子。這直接借鑒了圖像分割中一類方法（基于圖表示的圖像分割），它定義了 區域間間距和 區域内間距兩種距離度量，如果區域間間距大于區域内間距，那麼兩個區域就不能合并，反之就可以合并，公式中的邊權值w，由于是從小到大排列的，剛好就是區域間間距的意思。 （關于基于圖表示的圖像分割方面的内容，網上部落格也有很多，，大家可以去科普一下這方面的知識。我就找到了《Efficient Graph-Based Image Segmentation論文思路》一文，介紹的就不錯。）
4). 如果是不同的圖像區域，MST的做法對區域沒有任何辨識能力，有的區域之間差距很明顯，有的區域之間差距不明顯，但是MST一視同仁，而ST卻不是，它提出了一個判斷條件，滿足這個條件的不同區域，我可以合并，不滿足就不合并！門檻值就是幹這個的。
3. 算法效果
論文中給出了算法的視差圖對比，當然對比的對象就是NLCA，以及雙邊濾波方向的方法Guided Filter，從标準資料集上看，其實ST和NLCA真的差距不是很大，并且标準資料集上的比較并沒有很強的實際意義，往往在middlebery上好的評測算法，在實際應用場景上，效果就是個渣渣。。。但是ST是一種代價聚合方法，很多全局算法之是以求得精确，就在于它們在視差求精階段做足了文章，其實它們的代價聚合步驟得到的視差往往不咋地，那麼完全可以基于ST進行視差求精，這才是ST最大的意義啊！
4. 副産品
ST有個副産品，就是圖像分割，雖然作者沒有明确地強調這塊内容，隻是将其視作視差圖的求精部分， 但是分割的效果其實真心不錯，如圖所示：
大家看看效果還可以吧？至于作者怎麼做到的，過程真的很簡單，作者隻是基于深度圖和原圖重新構造了像素點之間的距離（或權重），然後重新走了一遍分割樹流程，再将圖像根據連通區域标定标簽，就得到了第三幅圖像的分割效果，中間那副圖像是隻考慮原圖的分割樹分割效果圖，很挫。引入的新公式如下所示：
作者在文獻中對這塊的說明一筆帶過，根據提供的源碼，色彩之間的距離其實是RBG三個通道內插補點的最大值，并且隻在穩定點上進行計算（關于穩定點，請參考其他幾篇部落格），折中參數設定的是0.5，這和文獻中的0.4不大一緻，不知道是出于何種原因。我在自己的資料集上也測試了這部分的分割效果，真的還不錯，看來也算是一種實用的圖像分割算法了（一定是基于雙目相機），雖然作者隻是想用其進行視差求精。
5. 結論
之是以研究ST，主要還是因為它是NLCA的擴充，是一種非傳統的全局算法，與NLCA唯一的差別就在于ST在建立MST的時候，引入了一個判斷條件，使其可以考慮到圖像的區域資訊。這點很新穎，說明作者閱讀了大量的文章，并且組合能力驚人，組合了MST和基于圖表示的圖像分割方法。它的運作時間雖然比NLCA要大一些，但是相比較全局算法，速度已經很可以了。 但是ST也有一些缺陷，首先，算法對圖像區域資訊的考慮并不是很嚴謹，對整幅圖像用一個相同的判斷條件進行分割，分割效果不會好到哪裡去，并且基于實際資料實測，會發現視差圖總是出現“白洞”，說明該處的視內插補點取最大，這也是區域資訊引入的不好導緻的。雖然在細節上略勝于NLCA，但是算法耗時也有所增加。上述原因也是本文引用率不佳的原因。