重磅干貨，第一時間送達

圖像分割（image segmentation）技術是計算機視覺領域的一個重要的研究方向，是圖像語義理解的重要一環(huán)。圖像分割是指將圖像分成若干具有相似性質的區(qū)域的過程，從數(shù)學角度來看，圖像分割是將圖像劃分成互不相交的區(qū)域的過程。近些年來隨著深度學習技術的逐步深入，圖像分割技術有了突飛猛進的發(fā)展，該技術相關的場景物體分割、人體前背景分割、人臉人體Parsing、三維重建等技術已經在無人駕駛、增強現(xiàn)實、安防監(jiān)控等行業(yè)都得到廣泛的應用。

圖像分割技術從算法演進歷程上，大體可劃分為基于圖論的方法、基于像素聚類的方法和基于深度語義的方法這三大類，在不同的時期涌現(xiàn)出了一批經典的分割算法。

此類方法基于圖論的方法利用圖論領域的理論和方法，將圖像映射為帶權無向圖，把像素視作節(jié)點，將圖像分割問題看作是圖的頂點劃分問題，利用最小剪切準則得到圖像的最佳分割。此類方法把圖像分割問題與圖的最小割（MIN-CUT）[1]問題相關聯(lián)，通常做法是將待分割的圖像映射為帶權無向圖G=(V，E)，其中，V={v1，…，vn}是頂點的集合，E為邊的集合。圖中每個節(jié)點N∈V對應于圖像中的每個像素，每條邊∈E連接著一對相鄰的像素，邊的權值w(vi,vj)，其中 (vi,vj)∈E，表示了相鄰像素之間在灰度、顏色或紋理方面的非負相似度。而對圖像的一個分割S就是對圖的一個剪切，被分割的每個區(qū)域C∈S對應著圖中的一個子圖。

分割的原則就是使劃分后的子圖在內部保持相似度最大，而子圖之間的相似度保持最小。我們以一個兩類的分割為例，把G = (V,E) 分成兩個子集A,B,另：A ∪ B = V, A ∩ B = ?，, 其中,  是權重(weight), 最小割就是讓上式的值最小的分割。

基于圖論的代表有NormalizedCut，GraphCut和GrabCut等方法

1.     NormalizedCut[2]

想要理解Normalized Cut 需要先理解什么是分割(CUT)與最小化分割（MIN-CUT)，我們拿下圖做例子，我們把圖一看成一個整體G，現(xiàn)在需要把它分成兩個部分。顯然中間的紅色虛線切割的邊就是最小化分割。

最小化分割解決了把權重圖G分成兩部分的任務，但是問題來了，如下圖所示，想要的結果是中間實線表示的分割，但是最小化切割卻切掉了最邊緣的角。這種情況很容易理解，因為最小化切割就是讓CUT(A,B)的值最小的情況，而邊緣處CUT值確實是最小，因此我們輸最小化切割時會有偏差的(bias)。如何去除這種偏差就要引入Normalized Cut算法了。

思路很簡單，將Cut normalize一下，除以表現(xiàn)頂點集大小的某種量度(如 vol A = 所有A中頂點集的度之和，含義是A中所有點到圖中所有點的權重的和)， 也就是NormalizeCut(A, B) = Cut(A, B) / volA + Cut(A, B) / volB，通過公式可以很清晰的看到NormalizeCut在追求不同子集間點的權重最小值的同時也追求同一子集間點的權重和最大值。 

2.     GraphCut[3]

Graph Cuts圖是在普通圖的基礎上多了2個頂點，這2個頂點分別用符號”S”和”T”表示，稱為終端頂點。其它所有的頂點都必須和這2個頂點相連形成邊集合中的一部分，所以Graph Cuts中有兩種頂點，也有兩種邊，第一種普通頂點對應于圖像中的每個像素。每兩個鄰域頂點的連接就是一條邊。這種邊也叫n-links。除圖像像素外，還有另外兩個終端頂點，叫S源點和T匯點。每個普通頂點和這2個終端頂點之間都有連接，組成第二種邊,這種邊也叫t-links，如下圖所示。

Graph Cuts中的Cuts是指這樣一個邊的集合，這些邊集合包括了上面定義的2種邊，該集合中所有邊的斷開會導致殘留“S”和“T”圖的分開，所以就稱為“割”。如果一個割，它的邊的所有權值之和最小，那么這個就稱為最小割，也就是圖割的結果。根據網絡中最大流和最小割等價的原理，將圖像的最優(yōu)分割問題轉化為求解對應圖的最小割問題。由Boykov和Kolmogorov發(fā)明的max-flow/min-cut算法[1，4]就可以用來獲得S-T圖的最小割，這個最小割把圖的頂點劃分為兩個不相交的子集S和T，其中s ∈S，t∈ T和S∪T=V 。這兩個子集就對應于圖像的前景像素集和背景像素集，那就相當于完成了圖像分割。

3.     GrabCut[5]

Graph Cuts 算法利用了圖像的像素灰度信息和區(qū)域邊界信息，代價函數(shù)構建在全局最優(yōu)的框架下，保證了分割效果。但Graph Cuts 是NP 難問題，且分割結果更傾向于具有相同的類內相似度。Rother 等人提出了基于迭代的圖割方法，稱為Grab Cut 算法。該算法使用高斯混合模型對目標和背景建模，利用了圖像的RGB 色彩信息和邊界信息，通過少量的用戶交互操作得到非常好的分割效果。

機器學習中的聚類方法也可以用于解決圖像分割問題，其一般步驟是:

基于像素聚類的代表方法有K-means（K均值），譜聚類，Meanshift和SLIC等。

1、K-means

K-means算法是輸入聚類個數(shù)k，以及包含 n個數(shù)據對象的數(shù)據庫，輸出滿足方差最小標準k個聚類的一種算法。K-means 算法接受輸入量 k，然后將N個數(shù)據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。

算法過程如下：

2、譜聚類

譜聚類(Spectral Clustering, SC)是一種基于圖論的聚類方法——將帶權無向圖劃分為兩個或兩個以上的最優(yōu)子圖，使子圖內部盡量相似，而子圖間距離盡量距離較遠，以達到常見的聚類的目的。與 K-means 算法相比不容易陷入局部最優(yōu)解，能夠對高維度、非常規(guī)分布的數(shù)據進行聚類。與傳統(tǒng)的聚類算法相比具有明顯的優(yōu)勢，該算法能在任意形狀的樣本空間上執(zhí)行并且收斂于全局最優(yōu)，這個特點使得它對數(shù)據的適應性非常廣泛。為了進行聚類，需要利用高斯核計算任意兩點間的相似度以此構成相似度矩陣。

譜聚類方法缺點：

a)譜聚類對參數(shù)非常敏感；

b)時間復雜度和空間復雜度大。

對于 k-way 譜聚類算法，一般分為以下步驟：

3、Meanshift[6]

Meanshift 算法的原理是在d 維空間中,任選一點作為圓心,以h為半徑做圓.圓心和圓內的每個點都構成一個向量。將這些向量進行矢量加法操作，得到的結果就是Meanshift 向量。繼續(xù)以Meanshift 向量的終點為圓心做圓，得到下一個Meanshift 向量.通過有限次迭代計算，Meanshift 算法一定可以收斂到圖中概率密度最大的位置,即數(shù)據分布的穩(wěn)定點，稱為模點。利用Meanshift做圖像分割，就是把具有相同模點的像素聚類到同一區(qū)域的過程,其形式化定義為：

其中，xi表示待聚類的樣本點，yk代表點的當前位置，yk+1代表點的下一個位置，h表示帶寬。Meanshift 算法的穩(wěn)定性、魯棒性較好，有著廣泛的應用。但是分割時所包含的語義信息較少，分割效果不夠理想，無法有效地控制超像素的數(shù)量，且運行速度較慢，不適用于實時處理任務。

4、SLIC[7]

SLIC（simple linear iterativeclustering），是Achanta 等人2010年提出的一種思想簡單、實現(xiàn)方便的算法，將彩色圖像轉化為CIELAB顏色空間和XY坐標下的5維特征向量，然后對5維特征向量構造距離度量標準，對圖像像素進行局部聚類的過程。SLIC算法能生成緊湊、近似均勻的超像素，在運算速度，物體輪廓保持、超像素形狀方面具有較高的綜合評價，比較符合人們期望的分割效果。

SLIC 算法的實質是將K-means 算法用于超像素聚類,眾所周知，K-means 算法的時間復雜度為O(NKI),其中, N 是圖像的像素數(shù),K 是聚類數(shù), I 是迭代次數(shù).

SLIC具體實現(xiàn)的步驟：

聚類方法可以將圖像分割成大小均勻、緊湊度合適的超像素塊,為后續(xù)的處理任務提供基礎，但在實際場景的圖片中，一些物體的結構比較復雜,內部差異性較大，僅利用像素點的顏色、亮度、紋理等較低層次的內容信息不足以生成好的分割效果，容易產生錯誤的分割。因此需要更多地結合圖像提供的中高層內容信息輔助圖像分割，稱為圖像語義分割。

深度學習技術出現(xiàn)以后，在圖像分類任務取得了很大的成功，尤其是其對高級語義信息的model能力很大程度上解決了傳統(tǒng)圖像分割方法中語義信息缺失的問題。

2013年，LeCun的學生Farabet等人使用有監(jiān)督的方法訓練了一個多尺度的深度卷積分類網絡[9]。該網絡以某個分類的像素為中心進行多尺度采樣，將多尺度的局部圖像patch送到CNN分類器中逐一進行分類，最終得到每個像素所屬的語義類別。在實際操作中，作者首先對圖片進行了超像素聚類，進而對每個超像素進行分類得到最后的分割結果，一定程度上提高了分割的速度。這種做法雖然取得了不錯的效果，但是由于逐像素的進行窗口采樣得到的始終是局部信息，整體的語義還是不夠豐富，于是就有了后面一系列的改進方案，本文中選擇了幾種代表性的網絡進行逐一分析。

1、 FCN（Fully Convolutional Networks for Semantic Segmentation）[10]

Long 等人于2014 年提出了FCN方法，這是深度學習在圖像分割領域的開山之作，作者針對圖像分割問題設計了一種針對任意大小的輸入圖像，訓練端到端的全卷積網絡的框架，實現(xiàn)逐像素分類，奠定了使用深度網絡解決圖像語義分割問題的基礎框架。為了克服卷積網絡最后輸出層缺少空間位置信息這一不足，通過雙線性插值上采樣和組合中間層輸出的特征圖，將粗糙(coarse)分割結果轉換為密集(dense)分割結果。FCN由于采用的下采樣技術會丟失很多細節(jié)信息，后續(xù)的一系列方法也都做了相應的改進策略。

2、DeepLab系列

DeepLab-v1 [11]在FCN 框架的末端增加可fully connected CRFs，使得分割更精確。DeepLab 模型，首先使用雙線性插值法對FCN的輸出結果上采樣得到粗糙分割結果，以該結果圖中每個像素為一個節(jié)點構造CRF 模型 (DenseCRF)提高模型捕獲細節(jié)的能力。該系列的網絡中采用了Dilated/Atrous Convolution的方式擴展感受野，獲取更多的上下文信息，避免了DCNN中重復最大池化和下采樣帶來的分辨率下降問題，分辨率的下降會丟失細節(jié)。

DeepLab-v2 [12]提出了一個類似的結構，在給定的輸入上以不同采樣率的空洞卷積并行采樣，相當于以多個比例捕捉圖像的上下文，稱為ASPP(atrous spatial pyramid pooling)模塊，同時采用了深度殘差網絡替換掉了VGG16增加了模型的擬合能力。DeepLab-v3 [13]重點探討了空洞卷積的使用，同時改進了ASPP模塊，便于更好的捕捉多尺度上下文，在實際應用中獲得了非常好的效果。

使用不同采樣率的空洞卷積并行采樣

3、PSPNet（Pyramid Scene Parsing Network）[14]

作者提出的金字塔池化模塊( pyramid pooling module)能夠聚合不同區(qū)域的上下文信息,從而提高獲取全局信息的能力，通過金字塔結構將多尺度的信息，將全局特征和局部特征嵌入基于FCN預測框架中，針對上下文復雜的場景和小目標的做了提升。為了提高收斂的速度，作者在主干網絡中增加了額外的監(jiān)督損失函數(shù)。

4、U-Net [15]

U-Net由菲茲保大學的Olaf Ronneberger等人在2015年提出，相較于FCN多尺度信息更加豐富，最初是用在醫(yī)療圖像分割上。在生物圖像分割中，最為突出了兩個挑戰(zhàn)是：可獲得的訓練數(shù)據很少；對于同一類的連接的目標分割。作者解決第一個問題的方法是通過數(shù)據擴大（data augmentation）。他們通過使用在粗糙的3*3點陣上的隨機取代向量來生成平緩的變形。解決第二個問題是通過使用加權損失（weighted loss），這是基于相鄰細胞的分界的背景標簽在損耗函數(shù)中有很高的權值。

編碼部分，每經過一個池化層就構造一個新的尺度，包括原圖尺度一共有5個尺度。解碼部分，每上采樣一次，就和特征提取部分對應的通道數(shù)相同尺度融合。這樣就獲得了更豐富的上下文信息，在Decode的過程中通過多尺度的融合豐富了細節(jié)信息，提高分割的精度。 

5、SegNet [16]

SegNet和FCN思路十分相似，只是Encoder中Pooling和Decoder的Upsampling使用的技術不一致。此外SegNet的編碼器部分使用的是VGG16的前13層卷積網絡，每個編碼器層都對應一個解碼器層。

在SegNet中的pooling與FCN的Pooling相比多了一個記錄位置index的功能，也就是每次pooling，都會保存通過max op選出的權值在filter中的相對位置，Unpooling就是Pooling的逆過程，Unpooling使得圖片變大2倍。max-pooling之后，每個filter會丟失的權重是無法復原的，但是在Unpooling層中可以得到在pooling中相對pooling filter的位置，所以Unpooling中先對輸入的特征圖放大兩倍，然后把輸入特征圖的數(shù)據根據pooling indices放入，總體計算效率也比FCN略高。

隨著深度學習在計算機視覺領域的巨大成功,以卷積神經網絡為基礎的圖像語義分割方法取得了突破性的進展，將圖像分割帶到了一個新的高度。筆者認為如何繼續(xù)提高分割算法的精度，以及降低分割算法的復雜度是值得繼續(xù)研究的問題。

交流群

歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學影像、GAN、算法競賽等微信群（以后會逐漸細分），請掃描下面微信號加群，備注：”昵稱+學校/公司+研究方向“，例如：”張三 + 上海交大 + 視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據研究方向邀請進入相關微信群。請勿在群內發(fā)送廣告，否則會請出群，謝謝理解~