permutohedral lattice理解
[完結]saliency filters精讀之permutohedral lattice
2012年09月28日 22:40:08?工長山?閱讀數：12432 版權聲明：本文為博主原創文章，未經博主允許不得轉載。 https://blog.csdn.net/xuanwu_yan/article/details/7962508勘誤使于2017年3月19日
本文寫于2012年碩士生階段，有較多疏漏和誤解，于今日起開始勘誤，以最大限度的保留原始文章，同時更正其中錯誤。
一、背景碎碎念
之前的saliency filter引用了一篇Adams的Fast high-dimensional?filtering using the permutohedral lattice，2010（見引用4），看了很多遍，感覺由于篇幅受限略過去了很多東西，數學又是屬于基礎的問題，看起來很慢。不死心繼續搜，終于功夫不負有心人，找到了Adams在2011年寫的HIGH-DIMENSIONAL GAUSSIAN FILTERING FOR COMPUTATIONAL PHOTOGRAPHY（Pdf）博士畢業論文，全文133頁，詳細闡明了新提出的兩種高斯卷積加速方法：一個就是本篇中要詳細講的利用permutohedral lattice，第二種使用了Gaussian KD-Tree。 文章首先在開始處介紹了幾種Gaussian濾波的家族成員：雙邊濾波，joint-雙邊濾波，joint-雙邊濾波upsample，以及Non-local Means的主要函數形式，以及在圖片處理中的效果。下面是高維高斯濾波的函數形式： 左邊為位置i的新數值（一般為顏色），向量表示；pi表示當前點的特征值，pj為窗口空間中剩余點的特征值，， 對于此處為什么有個1，我的理解是為了保證窗口中權值之和為1需要除一個參數，新得到rgb值缺少這么一個參數，于是就有了這個1 我們分析不同濾波方式中特征值不同產生的影響： 1）在普通的高斯濾波中有 也就是說當前像素點周圍只是位置的遠近影響新的值； 2）而雙邊濾波中 導致顏色迥異的點時權值近似為零。（后來我才知道這里放的兩只黑狗照片是作者拍攝地，有錢淫，他的Stanford主頁上還有各種旅游風景照，口水ing）這里先做簡單介紹，實現代碼與此有關。此后又對以上幾種方法進行了圖片(Canon 400D?at ISO 1600.)處理的對比，發現對于非高斯噪點，joint-雙邊濾波對人眼表現最好，但Non-local Means處理后的照片最真實。 說了這么多，其實作者的意思就是高斯卷積在圖片處理中處于使用量巨大，但是同時速度很慢的一個技術，如何快速計算高斯卷積是一項灰常灰常重要的事。本文思想
下面輪到介紹本文的基本思想了，也許各位也看過了很多遍吧。。。 1）用新建坐標系，用pi表示特征值節點坐標而不是原始的(x, y)，vi保持不變 2）投影映射，就是坐標變換，降維的步驟在此處進行。一個坐標不是投影到一個點，而是類似于重心插值投影到一個單形(lattice)各個頂點處，保留各頂點的權值為以后的upsample保存。若兩個不同的點投影到相同的頂點坐標時，增大此點值。 3）對lattice的頂點計算高斯卷積 4）upsample得到原始的點。二、現有成果
由于我讀本文重點在于permutohedral lattice，所以那些濾波之類的就只做了一下簡單了解，joint-雙邊濾波-upsample和Non_local Means真心沒有搞懂，這里也不瞎做介紹。然后有一幅圖挺重要的，具體對比了Gaussian Filter這些年的進步。 1）Naive方法只是單純地將窗口中所有點進行卷積，時間復雜度O(mn^d)； 2）快速高斯卷積方法首先將格子中的每個點都放在了格子的重心上，時間復雜度O(mk^d)，由于格子的個數k小于point的個數n，所以提速； 3）雙邊方格卷積在上面的基礎上，不對每個點卷積，而是對格子的每個頂點卷積，最后使用插值方式恢復特征點，復雜度變為O(k^(d+1))，特征點的個數多于格子的個數，所以有加速，但此方法有個缺點就是對于維度仍然是指數復雜度，對高維特征的高斯濾波不合適(d>3 or d>5) 4）改進的快速高斯卷積，不局限于方格而是簇概念，每個簇可以是跨維度的形狀，雙邊濾波改進處就是在中心表示之后，直接對重心進行blur，然后在插值形成原來的點，時間復雜度O(mkd)； 5）本文在第一步采用了新的方法，通過提高維度的方法將格子原來的grid變成了文中的permutohedral lattice，時間復雜度也是O(nd^2)，但由于使用質心插值方法，能夠產生更加優秀的效果；高斯Kd-tree則在分類上做了改變，有時間再繼續讀。三、Permutohedral Lattice
本文貢獻
Permutohedral lattice相比之前工作的進步之處于，定義
一個d維的permutohedral lattice是d+1維空間子平面分割，此超平面法向量為，所以我們有。什么是分割？一般認為分割的格子（lattice）是同樣形狀，一個平面能夠被相同形狀的格子沒有縫隙，沒有重疊的布滿，那么格子就是空間的分割。 我們需要對此子平面進行分割，作者使用了單形進行分割。單形頂點在d+1維空間坐標我們不得而知，作者重新定義了基向量（并不完全準確，因為之間線性相關），于是此子平面上單形頂點的坐標直接滿足在平面上的要求，即。 當d=3時，單形頂點在原點，單形的邊長為1，格子如上圖所示。單形的頂點坐標為整數，并且一個點的坐標各項模d+1=3有相同余項k，我們稱這個頂點為余k點。這里對上面的基向量稍微做一下解釋，假設在三維空間中，有子空間，有 在xoy平面上，有三個點，這個點經過映射變換，就對應了上圖中的橙色區域，坐標為 也就是說，下圖右側x軸原點y軸夾的右上部分區域，是下圖左側分割空間坐標映射變換 下面的文章都是基于映射后的坐標。網格性質
子平面具有三個屬性：計算高斯卷積
下面介紹利用這個permutohedral lattice計算高斯卷積。生成特征值映射到子平面的點
首先將每個坐標點除了一個誤差，是由splat，blur以及slice中產生的。然后映射到子平面上，注意此時的映射矩陣與上面的不同，因為上面的基向量不是正交的，并且此映射可以用的時間計算出來。舉例bilateral filter，position由5-D向量組成， 計算方法如下：
Splat階段：
這個階段主要是把特征點的值使用質心插值的方法，累加到所在單形的所有頂點上。上文已經介紹了如何通過點找到所在單形的頂點。那么質心插值如何計算？ 還記得上面圖片的橙色三角區域嗎，假設其中有一個點y，s是單形的頂點，b是插值系數，那么我們有 作者證明了此階段時間復雜度是。 Blur階段：查找單形頂點的所有相鄰點對，即，使用核函數進行blur操作，此步驟復雜度為。
Slice階段：
同splat階段步驟，利用權重b計算插值。由于在splat階段建立了b的table，所以用時O(nd)。
本算法總計用時為O((n+l)d^2)。
此圖為速度比的等高線，為最快速度和第二快的算法結構用時之比。顏色越深相差越大。圖片左側標志維度，橫軸為filter size，右側為使用的算法。
可以看到5-20維度時候permutohedral lattice根據filter size情況最優。
?
完結。
?
?
https://www.codetd.com/article/2771587
?
直接看第三章，bilateral convolution layers。這個詞來自于文獻[22]和[25]：
[22]Learning Sparse High Dimensional Filters:Image Filtering, Dense CRFs and Bilateral Neural Networks?. CVPR2016
[25]Permutohedral Lattice CNNs.??ICLR 2015?
但是筆者去看了這兩篇文章，感覺這里其實叫Permutohedral Lattice CNNs更貼切。文獻[22]寫得亂七八糟得，提出了Bilateral Neural Networks這么個詞，其實根本就只是把文獻[25]里的Permutohedral Lattice CNNs換了換名字、換了個場合。
?
接著看文章，為了講解方便，我們就繼續用文中BCL這個名詞。
?
第三章比較重要，首先講了BCL的輸入。這里先區分兩個詞，input features?和lattice features ，前者是實打實的輸入特征，其維度為df，既可以是低階特征，也可以是神經網絡提取的高階特征，維度從幾到幾百均可；而后者是用來構造Permutohedral Lattice的特征，只用低階特征，如位置、顏色、法線，維度一般為個位數。例如第四章文中給的SPLATNet3D?的實現結構，lattice features是位置，維度就只有3。
接著，就是文章的核心了，介紹了BCL的三個基本操作：Splat、Convolve、Slice，這里文章介紹的不細致，而且容易誤導人，建議有時間的同學去看看文獻[25]以及文獻[1]“Fast High-Dimensional Filtering Using the Permutohedral Lattice”會有個更深入的理解。
Splat。
這個操作就是把歐式空間變換成另外一個空間，怎么變換？通過乘一個變換矩陣。變換矩陣一般是這樣
具體為什么定義成這樣就是數學問題了，在此就不贅述了。這里d表示Permutohedral Lattice空間的維度。
為了便于理解，給一個例子：歐式空間定義三個點，分別是（0,0,0）、（1,0,0）、（1,1,0）。令Permutohedral Lattice維度取d=2，則
用B2乘坐標，得到經過變換后新的三點坐標（0,0,0）、（2,-1,-1）、（1,1,-2）。這一過程如下圖所示：
右圖中，帶顏色的數字0，1，2都是余數（即文獻[1]中的remainder）。這個余數是怎么算的呢？舉例說明，如（2,-1,-1）這個點，2和-1兩個數對3進行取模運算，得到的余數都是2，所以這點就標成2；再比如（1,1,-2）對3取模，余數都是1，所以這點就標成1。在整個Permutohedral Lattice空間都遵循這種規則進行標注，后面做卷積運算時會根據這些余數進行相應操作。
如上圖所示的那樣，Permutohedral Lattice空間就是有多個單形不留縫隙地拼接而成，它不像歐式空間那樣坐標軸互相垂直，而是成一定角度，分布在平面上。它具有以下特點：
?
關于這兩點我的理解僅限于，這種空間對于稀疏無序的數據，能夠更加高效地進行組織，便于查找和各種運算的進行。
?
把歐式空間里的點變換到Permutohedral Lattice空間后，還要進行一步“炸裂”操作（這個名字是我杜撰的），如下圖：
也就是把單形里的某個點的信息炸開到周圍三個頂點上，當然了，這個點帶的信息也就是它的特征，不管64維也好128維也好，都要炸開到周圍三個頂點。這個所謂的“炸開”也是有一定依據的，會根據距離分配不同的權值，但是基本上炸開之后的特征維度是不變的。
至此，Splat操作完成。所以，現在大家應該能夠體會到Splat的作用了，就是把原本在歐式空間中又稀疏、又不均勻的點按照一種新的形式組織了一下，方便進行后續運算。下面就是Convolve。
Convolve說起來就簡單了，Splat操作之后，點的特征已經按照一定原則“分配”到各個單形的頂點上了，所以，位置也就很比較規整了，按照哈希表做索引，進行卷積操作就行了。
Slice。這是Splat的逆過程，把卷積運算后得到的Lattice頂點上的信息，“匯聚”到原來點的位置上。當然，如果“匯聚”到新的位置上也可以，新的點數也可以比原來的點數少，也可以分布在不同維度的歐式空間上。這就和卷積操作變換圖片尺寸的效果有點類似。
至此，就把Permutohedral Lattice CNN模塊講完了，這就是BCL的核心內容了。
第四章就簡單了，無非就是介紹網絡的超參是如何設定的、網絡結構如何設計的，都是比較容易理解了。
第五章介紹了2D-3D融合的實現版本，無非就是多加了幾個concate的操作，網絡更加復雜一些，根據語義分割的任務特點加了多層次信息融合等等，也都不難理解。
第六章是實驗，證明了本文所提網絡的有效性。
第七章總結。
附錄部分——附錄部分可以看看網絡的設計參數，例如BCL的輸出特征維度64-128-128-64-64-7等等，可以加深對網絡的認識。我最開始搞不清楚Splat投影是做什么的，受到文中一句話的誤導：
以為要把高維（如64，128）的特征映射到低維（如3，6），非常別扭。
直到看到附錄部分關于BCL輸出特征維度的介紹，維度還是很高的，就才恍然大悟，才知道Splat中的“炸開”是帶著厚厚的特征一塊“炸開”的。
?
直接看第三章，bilateral convolution layers。這個詞來自于文獻[22]和[25]：
[22]Learning Sparse High Dimensional Filters:Image Filtering, Dense CRFs and Bilateral Neural Networks?. CVPR2016
[25]Permutohedral Lattice CNNs.??ICLR 2015?
但是筆者去看了這兩篇文章，感覺這里其實叫Permutohedral Lattice CNNs更貼切。文獻[22]寫得亂七八糟得，提出了Bilateral Neural Networks這么個詞，其實根本就只是把文獻[25]里的Permutohedral Lattice CNNs換了換名字、換了個場合。
?
接著看文章，為了講解方便，我們就繼續用文中BCL這個名詞。
?
第三章比較重要，首先講了BCL的輸入。這里先區分兩個詞，input features?和lattice features ，前者是實打實的輸入特征，其維度為df，既可以是低階特征，也可以是神經網絡提取的高階特征，維度從幾到幾百均可；而后者是用來構造Permutohedral Lattice的特征，只用低階特征，如位置、顏色、法線，維度一般為個位數。例如第四章文中給的SPLATNet3D?的實現結構，lattice features是位置，維度就只有3。
接著，就是文章的核心了，介紹了BCL的三個基本操作：Splat、Convolve、Slice，這里文章介紹的不細致，而且容易誤導人，建議有時間的同學去看看文獻[25]以及文獻[1]“Fast High-Dimensional Filtering Using the Permutohedral Lattice”會有個更深入的理解。
Splat。
這個操作就是把歐式空間變換成另外一個空間，怎么變換？通過乘一個變換矩陣。變換矩陣一般是這樣
具體為什么定義成這樣就是數學問題了，在此就不贅述了。這里d表示Permutohedral Lattice空間的維度。
為了便于理解，給一個例子：歐式空間定義三個點，分別是（0,0,0）、（1,0,0）、（1,1,0）。令Permutohedral Lattice維度取d=2，則
用B2乘坐標，得到經過變換后新的三點坐標（0,0,0）、（2,-1,-1）、（1,1,-2）。這一過程如下圖所示：
右圖中，帶顏色的數字0，1，2都是余數（即文獻[1]中的remainder）。這個余數是怎么算的呢？舉例說明，如（2,-1,-1）這個點，2和-1兩個數對3進行取模運算，得到的余數都是2，所以這點就標成2；再比如（1,1,-2）對3取模，余數都是1，所以這點就標成1。在整個Permutohedral Lattice空間都遵循這種規則進行標注，后面做卷積運算時會根據這些余數進行相應操作。
如上圖所示的那樣，Permutohedral Lattice空間就是有多個單形不留縫隙地拼接而成，它不像歐式空間那樣坐標軸互相垂直，而是成一定角度，分布在平面上。它具有以下特點：
?
關于這兩點我的理解僅限于，這種空間對于稀疏無序的數據，能夠更加高效地進行組織，便于查找和各種運算的進行。
?
把歐式空間里的點變換到Permutohedral Lattice空間后，還要進行一步“炸裂”操作（這個名字是我杜撰的），如下圖：
也就是把單形里的某個點的信息炸開到周圍三個頂點上，當然了，這個點帶的信息也就是它的特征，不管64維也好128維也好，都要炸開到周圍三個頂點。這個所謂的“炸開”也是有一定依據的，會根據距離分配不同的權值，但是基本上炸開之后的特征維度是不變的。
至此，Splat操作完成。所以，現在大家應該能夠體會到Splat的作用了，就是把原本在歐式空間中又稀疏、又不均勻的點按照一種新的形式組織了一下，方便進行后續運算。下面就是Convolve。
Convolve說起來就簡單了，Splat操作之后，點的特征已經按照一定原則“分配”到各個單形的頂點上了，所以，位置也就很比較規整了，按照哈希表做索引，進行卷積操作就行了。
Slice。這是Splat的逆過程，把卷積運算后得到的Lattice頂點上的信息，“匯聚”到原來點的位置上。當然，如果“匯聚”到新的位置上也可以，新的點數也可以比原來的點數少，也可以分布在不同維度的歐式空間上。這就和卷積操作變換圖片尺寸的效果有點類似。
至此，就把Permutohedral Lattice CNN模塊講完了，這就是BCL的核心內容了。
第四章就簡單了，無非就是介紹網絡的超參是如何設定的、網絡結構如何設計的，都是比較容易理解了。
第五章介紹了2D-3D融合的實現版本，無非就是多加了幾個concate的操作，網絡更加復雜一些，根據語義分割的任務特點加了多層次信息融合等等，也都不難理解。
第六章是實驗，證明了本文所提網絡的有效性。
第七章總結。
附錄部分——附錄部分可以看看網絡的設計參數，例如BCL的輸出特征維度64-128-128-64-64-7等等，可以加深對網絡的認識。我最開始搞不清楚Splat投影是做什么的，受到文中一句話的誤導：
以為要把高維（如64，128）的特征映射到低維（如3，6），非常別扭。
直到看到附錄部分關于BCL輸出特征維度的介紹，維度還是很高的，就才恍然大悟，才知道Splat中的“炸開”是帶著厚厚的特征一塊“炸開”的。
?
轉載于:https://www.cnblogs.com/adong7639/p/10531140.html
總結
以上是生活随笔為你收集整理的permutohedral lattice理解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python range 小数_pyth
- 下一篇： SAP系统开发里程碑 2022 刘欣