基于圖形剪切的圖像分割

點擊上方“小白學(xué)視覺”，選擇加"星標(biāo)"或“置頂”

重磅干貨，第一時間送達(dá)

圖像分割技術(shù)是計算機(jī)視覺領(lǐng)域的一個重要研究方向，也是圖像語義理解的重要組成部分。圖像分割是指將圖像分割為具有相似屬性的幾個區(qū)域的過程。從數(shù)學(xué)的角度來看，圖像分割是將圖像分割成不相交區(qū)域的過程。該區(qū)域可以是圖像的前景和背景，也可以是單個對象。可以使用顏色、邊緣或鄰域的相似性等要素構(gòu)造這些區(qū)域。

圖形切割算法是組合圖形理論的經(jīng)典算法之一。近年來，許多學(xué)者將之應(yīng)用于圖像和視頻分割，取得了良好的效果。本文簡要介紹了圖形切割算法和交互式圖像分割技術(shù)，以及圖形切割算法在交互式圖像分割中的應(yīng)用。

01.基本概念

運用圖形理論領(lǐng)域的理論和方法將圖像映射到加權(quán)無定向圖形中，將像素視為節(jié)點，將圖像分割問題視為圖形的頂點分割問題，利用最小的切割標(biāo)準(zhǔn)獲得圖像的最佳分割。

這種方法將圖像分割問題與MIN-CUT問題關(guān)聯(lián)在一起。通常的方法是將要分割的圖像映射到加權(quán)無方向圖形 G=（V，E），其中 ， V 是頂點集，E 是邊集。每個兩個相鄰頂點的連接形成的邊稱為 n 鏈接，每個普通頂點和兩個終端頂點之間的連接稱為 t 鏈接。每個節(jié)點對應(yīng)于圖像中的每個像素，每個邊 ∈ E 連接一對相鄰像素，并且邊緣的權(quán)重為 w（i，j）表示相鄰像素之間的灰色、顏色或紋理的非負(fù)相似性。

博伊科夫和喬利最初提議計算標(biāo)記像素的直方圖，以近似概率密度函數(shù)，并讓

例如，如果 fB 非常低，則 wi，F(xiàn) 將非常高，因此更有可能剪切 i 和 B 之間的邊緣。使用簡單的相似性度量計算節(jié)點間權(quán)重

Blake 等人演示了如何σ圖像樣本的局部對比度來估計參數(shù)。

我們以兩類除法為例，將G = （V，E） 分成兩個子集 A、B 。這兩個子集對應(yīng)于前景像素集和圖像的背景像素集，這相當(dāng)于完成圖像分割，其中：

圖像的分割 S 是圖像的剪切，分割的每個區(qū)域 C ∈ S 對應(yīng)于圖像中的子圖像。在組合優(yōu)化中，將切割成本定義為其切斷的邊緣成本之和是正常的。

切割的成本是邊集 C 中所有邊的重量的總和。

02.?Maxflow-Mincut 理論

圖形中的流

我們考慮一個定向圖（S，A），具有一組無限頂點S和一組弧線，連接其中一些頂點。

頂點中區(qū)分為源S，井P.與每個弧線關(guān)聯(lián)一個嚴(yán)格的正實數(shù)，稱為電容。

我們尋求通過液體的最大流量，從源頭到井——每個弧線中的流量不超過其容量。換句話說，我們正在尋找 R 中一組弧的函數(shù) f，以便：

• 對于任何弧 a，0≤f （a） ≤ c （a），其中 c （a） 是弧的容量。

• 對于源或井以外的任何頂點，傳入圓弧的流速之和等于傳出圓弧的流的總和。

我們談到這樣的應(yīng)用程序的流程。我們尋求確定最大流量，在意義上

• 離開源的弧的流速之和為最大值。

下面是一個流的示例。

然而，它不是最大值，例如，可以通過在S-a-b-d-e-P路徑上添加1的比特率來改進(jìn)。

有幾種算法可以實現(xiàn)最大流量，例如 Dinic 或 ISAP 算法。

最小切割

最大流量的值等于最小切入的值。

此外，如果 （A， B） 是最小切口，并且 a 是弧線，其起點為 A，結(jié)束為 B，則由任何最大流量飽和。

03.結(jié)論

本課介紹圖像處理的基本低級操作和工具，這些操作和工具是理解大多數(shù)常用的計算機(jī)視覺方法和工具所必需的。

04，參考文獻(xiàn)

1. Yuri Y. Boykov Marie-Pierre Jolly.Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images

2. A. Blake, C. Rother, M. Brown, P. Pérez, and P. Torr. Interactive image segmentation usingan adaptive GMMRF model. InEuropean Conference on Computer Vision (ECCV), 2004.

3. Yuri Boykov, Vladimir Kolmogorov: An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. IEEE Trans. Pattern Anal. Mach. Intell. 26(9): 1124–1137 (2004)

4. Adelson, Edward H., and James R. Bergen (1991), “The plenoptic function and the elements of early vision”, Computational models of visual processing 1.2 (1991).

5. Boykov, Y., Veksler, O., and Zabih, R. (2001), “approximate energy minimization via graph cuts,”?IEEE Transactions on Pattern Analysis and Machine Intelligence,?23(11): 1222–1239.

6. D.M. Greig, B.T. Porteous and A.H. Seheult (1989),?Exact maximum a posteriori estimation for binary images, Journal of the Royal Statistical Society, Series B,?51, 271–279.

7. D. Geman and S. Geman (1984),?Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell.,?6, 721–741.

8. J.E. Besag (1986),?On the statistical analysis of dirty pictures (with discussion),?Journal of the Royal Statistical Society?Series B,?48, 259–302.

交流群

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