level set （水平集）演算法是什麼？
一年前看到師兄弄 level set，當時沒有看懂。
前幾天，在看一本書時，偶然又看到這個，就打算來仔細了解一下了。
所以，下面的這些點子新鮮出爐的，沒有太多的實戰經驗，若有錯誤，應該也是很正常的，請見諒。
這篇答案，最大的啟發來自youtube的這兩個視頻：
https://www.youtube.com/watch?v=B9soiDHr9bo
https://www.youtube.com/watch?v=1ZJ88JyLPZI
--------------------------------------------------------------
1.
我第一次看到 level-set 的時候，我認為它是一種圖像分割的方法。
當然，大家也都這麼說。
不過，從這幾天的了解來看，如果在內心一直帶著「它是一種圖像分割方法」這個想法，反而是帶著一些框框，很多概念變得不那麼好理解了。
所以，第一步： 請忘掉這件事情，暫時我們不說它是一種圖像分割的方法。
2.
在說 level set 之前，我們先談 曲線的演變。
我們已經有一條曲線了。
現在，假如我們要演變它。
這裡的意思是，我們要讓一條曲線變化，慢慢地變成另一條曲線。
那麼我們很容易想到的一個點子是：我只需要指定曲線上的每一個點的運動方向和速度就可以了。
可以參考下面這個圖：
這個圖裡面只考察了一個點的運動方向和速度。
3.
到這裡可能會很讓你驚訝。
我們還沒有提及到任何 和 「level -set」 有關的東西，圖像分割的點子已經來了。
圖像分割的結果是，在我們要分割的圖像上，我們繪製了一條曲線。
曲線包住了一些東西，那被我們說成是分割出來了的東西。
所以，圖像分割，如果用曲線演變的方法，大約就是在要分割的圖片上，先隨便繪製一條曲線，然後讓這條曲線演變成我們想要的曲線，分割就搞定了。
回看一下上面，曲線的演變的話，我們其實只需要控制的是每一個點在每一個時刻的速度而已。
圖像分割，僅僅是，針對曲線上的每一個點，考察其蓋住的圖像，通過此來決定在曲線上的這個的點的運動速度而已。
為了說明，我打算舉個例子：
上面圖裡，那個紅色小圈就是我的初始曲線。
現在，我要演變這個曲線。
那麼也就是要控制每一個時刻這個曲線上的每一個點的運動速度和方向。
方向嘛，我就朝外（arc length 法線方向），而大小呢，我就根據這條曲線蓋住的圖像來確定。
（把圖像和曲線看成在兩個不同的圖層，曲線在上一層，圖像在它下面）
這個大小的確定有很多不同的方法，但是很基本的要滿足的條件是：我希望到快接近邊緣的時候，速度就慢了，甚至停了下來，而如果曲線上的那個點不靠近邊緣，那麼速度就得比較快。
比如說，大小確定的方法，我根據曲線上的每一個點，當前蓋住的圖像的點處的梯度來決定速度的大小。
如果梯度比較小，那說明這個時候，曲線還在肚子裡面，我的速度就可以大一點。
如果梯度比較大，那麼說明這個時候，已經接近了邊緣了，那麼我的運動速度就要小一點了。
因此，曲線上每一個點運動的速度，和其蓋住的圖像的點的梯度大約成反比：
比如上圖，綠色的點的運動速度就很大。
而黃色的那個點啊，就得運動得很慢了，甚至幾乎不怎麼運動。
慢慢地，這個曲線就貼近圖像的輪廓了。
至少從我目前的理解來看，核心在於如何通過要分割的圖像，去確定曲線運動的速度。
4.
圖像分割的故事其實已經說完了。
到目前為止，都還沒有說到 level - set。
小結一下： level set 準確地說來，不是圖像分割的方法。
真正的圖像分割的方法，是 曲線的演變。
我們通過把每一個點的演變速度和圖像扯上關係，曲線就慢慢演變成了輪廓。
那 level-set 是什麼？它是 曲線演變的 實現方法。
5.
上面的曲線演變，在真的實現的時候，會很頭疼。
所以，才需要 level set 幫忙。
在這個部分，我打算談一下是怎麼頭疼的：
（1）綠色曲線的兩個鄰近的點，根據當前的速度演變，到了下一刻，成了紅色曲線上的兩個點。注意到，這裡曲線「變長」了，多出了藍色的點，這個點還需要插值出來得到。
（2）
對於左邊的圖，如果是從紅色曲線演變成黃色的曲線，其實好比較容易想通。
但是，從黃色曲線演變成紅色曲線就有點費解了。
因為有的地方，兩個點重合了之後，不知道該如何描述下一個時刻。
是兩個點和成了一個呢？還是每一個點都還有自己的運動。
再看右邊，紅色曲線很光滑，慢慢朝著裡面運動，變得越來越尖了。這個時候又不好描述點的運動了。
所以，真的去跟蹤每一個點的運動是很頭疼的。
6.
終於要說到 level set了。
先來看這個詞，set 的意思是集合。
我們要描述直線上的兩個點，那麼可以直接就寫出兩個點的坐標：
你也可以繞一下，寫成集合的形式，也就是所謂的 level set：
這裡的 y 的取值就是 level，那麼和上面相比，直接是X 軸上的兩個點。
在這裡的話，表達方式就成了，level 為1 的所有x取值的集合。
所以對於曲線來說是一樣的。
一個曲線是二維的。
我們可以直接用一個參數方程在二維平面上表示一條曲線：
或者，也是表示集合的形式，那麼就會是一個曲面（二元函數）上，某個level下的（一般選擇的是level=0，也就是 f(x,y)=0），所有點的（x，y）坐標的集合（圖中紅色的為曲線，這些點的z坐標均為零）：
7.
於是，上面的曲線的演變，可以變成了這個 f(x,y)隨著時間演變，整個曲面發生了變化，它的level 0 的集合（即曲線），也發生了變化。
說是這麼說，到底能不能實現，就需要回到我們上面曲線演變的問題：
上圖中的第一個公式，其實就是對於我們上面曲線演變的描述。
C表示的曲線（這裡省略了具體細節，用這個比較模糊的式子，實際上為 C(p) = (x(p),y(p))），下標t表示，C對t求導。那麼這個實際上，得到的是曲線上的每一個點的運動速度（向量）。
所有右邊的V是速度的大小，而N是指的曲線的法線方向。
這裡是我不太懂的地方，視頻的作者不斷談到，改變曲線形狀的速度方向是法線方向的，而切線方向的速度是不改變曲線的形狀的，所以，在曲線的演變中，所有的點都只考慮了其發現方向的速度。
然後下面一個公式，f是一個二元函數，以x和y自變數的函數，它的取值為零時，所有的
x和y的坐標點的集合就是我們的曲線，它是第一個式子通過推導（其中需要引入的條件就是，level = 0 時的集合為曲線）得來的。意思是說，你的曲面只要按照這個式子去演變，那麼其level 0，總是我們想要的曲線。
所以，來回顧一下：
我們要實現的是第一個公式，曲線的演變，其中的V怎麼來選擇，我們暫時不管，V選擇的方式才決定了我們要乾的事情是不是圖像分割。
而第二個公式，是曲面的演變，曲面的演變，如果遵循這個式子，即是曲面上的點，z=f(x,y)的取值，隨著時間的變化滿足這個式子的右邊。那麼每一次，取這個曲面的 level 0，那些點就一定是上面我們想要的當前狀態下的曲線。
再來看下第二個式子要怎麼實現？
很簡單。
一開始，隨便選取一個曲面，只要其 level 0 為我們要的初始曲線。
然後，下一刻時刻，僅僅根據V，還有當前曲面的梯度，就能得到 f_t.
然後，把所有的z的取值，都加上對應的 del*f_t 即可。
非常容易。
首先必須要贊一波水平集的鼻祖們，這個方法確實牛，用形象的數學工具表達目標，還可以方便的在能量泛函中加入先驗知識，確實高明。
其實維基百科說的也差不多了。水平集演算法是一種隱式的表示曲線的方法。就是把低維目標用比他高一維的水平集函數的零水平集來表示。零水平集可以有很多個曲線來表示目標，這就得看你的目標是什麼樣子了。說完水平集函數，就要說你構造的能量泛函了，這個函數一般都有一個內部力量項，外部力量項和一個正則項。怎麼構建的？具體看各個文章了，大多都是差不多的，手機也不好搞公式…（主要是懶）這又牽扯到泛函。我們一般說的函數是關於變數的，而泛函通俗講就是關於函數的函數， 水平集方法構建的能量泛函就是關於水平集函數的。當極小化這個泛函時，水平集函數的零水平集也就收縮到目標邊界。這是因為零水平集受到內力和外力作用，當和目標重合時，內外力平衡，能量極小化。
……………………分割線………………………
水平集常用在活動輪廓active contour 方法中表示曲線，而活動輪廓又分為基於區域的和基於邊緣的方法。安利一個大牛，李純明，現在回國了，之前就是看他的水平集文章，有兩篇都是best paper。其中基於區域的方法可以看李純明教授的RSF，寫的很好，不依賴於初始化，還有相關代碼也公開了。基於邊緣的方法可以看他的DRLSE，對初始化敏感，但是對簡單圖效果很好。這兩篇看完如果還很迷糊，當然我也迷糊。。。你可以再去看看蛇模型和CV，看看區別，總結一下，感覺就可以了，有些東西說是說不粗來的。
記得有個老師講課時候說，我們搞圖像的，經常被別人說我們的演算法都沒有普適性，都是需要靠人品的，人品好了，參數調對了，結果就有了，沒人品，對不起。。。
前面的知友已經解釋的很好了，這裡補充一個個人認為很好的材料，可做補充：Level Set Method: an Explanation
其實 Level Set 就是地形圖上常見的等高線：
而 Level Set Method 就是通過連續上下移動等高平面（下圖中的藍色平面），得到連續變化的輪廓，從而模擬曲線或曲面的連續變形。
圖片來自維基百科：
Level set
Level set method
廣義地講，level set是一種界面追蹤的數值方法，由著名的應用數學家Osher於1988年提出。這一類方法最早用於計算物理中對界面的捕捉（比如水面相對於空氣）。由於界面的低維特性（比如兩維世界裡的界面是沒有面積的曲線，三維世界裡的界面是沒有體積的曲面），和複雜的拓撲結構，之前沒有很好的辦法來計算界面的變化。Level set方法通過把界面定義為某個虛擬函數取某一特定值的集合，將描述界面的變化轉換成描述這一虛擬函數的變化，而後者有許多現成的數值方法可用。
曲線的運動方向由法線方向決定，而不是曲線的切線方向決定，是因為曲線點的運動速度方向與切線方向平行，所以無法改變其運動方向
我所知道的level set method是運用在two-phase flow的計算中的。。。沒想到還能用在圖像處理上
簡單來說就是一個沿著他的法向演化的曲線。因為最簡單的level set函數就是
frac{partial{Phi}}{partial t} = |
abla Phi|，
我覺得這個問題， @楊樹下的狐狸已經說的很好了。我想補充的一點是，其實水平集的level選幾都無所謂，怎麼都能轉化成level=0的形式。還有 @zlion 說的，李純明老師的文章，我都拜讀過了，依然迷糊。水平集真是太博大精深了，一時半會真都很難理解到真諦啊。
我恰好是研究這個方向的，水平集應該說是主動輪廓方法（Active Contour Model，ACM）的一種具體解法，之前（現在仍然有人研究）人們也使用過質點標註法一些列方法來解ACM。
詳細的地方過幾天再來補充……最近被水平集法在實景上的極差表現折磨中……
李純明老師的paper怎麼搜索啊？
推薦閱讀：
※誰能圖文並茂地區分一下 Chroma 和 Saturation 這兩個色彩術語？
※如何在photoshop中把字體顏色處理成下面鏈接圖片的樣子？
※如何補救清晰度低的照片？
※在圖像處理中，散度 div 具體的作用是什麼？
※有哪些辦法將圖形轉化為聲音？
TAG:圖像處理 | 機器視覺 | 數字信號處理 | 圖像信號處理器ISPImageSignalProcessor |