交互式圖像分割

交互式圖像分割指用戶以某種交互手段指定圖像的部分前景與部分背景，然后算法以用戶的輸入作為分割的約束條件自動地計算出滿足約束條件下的最佳分割移宅。典型的交互手段包括用一把畫刷在前景和背景處各畫幾筆以及在前景的周圍畫一個方框等洋闽。

基于圖割算法的圖像分割技術(shù)是近年來國際上圖像分割領(lǐng)域的一個新的研究熱點(diǎn)。該類方法將圖像映射為賦權(quán)無向圖，把像素視作節(jié)點(diǎn)微渠，利用最小切割得到圖像的最佳分割。

Graph Cut

Graph Cut圖割算法用于解決低級計算機(jī)視覺問題咧擂，該類方法將圖像分割問題與圖的最小割（min cut）問題相關(guān)聯(lián)逞盆，采用最小割最大流方法進(jìn)行圖像分割，將圖像分割為前景和背景松申。使用時在前景和背景處各話幾筆作為輸入云芦，算法將建立各個像素點(diǎn)與前景背景相似度的賦權(quán)圖，并通過求解最小切割區(qū)分前景和背景贸桶。

最小割算法（Minimum Cut）

最小割算法（Minimum Cut）是圖像分割的經(jīng)典算法之一舅逸，在"Graph Cut"、"Grab Cut"等算法中都有被使用過皇筛。

提出該分割算法的論文：
Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images

image.png

最小割

圖論中的最小割
在圖論中琉历，圖的最小切割是其在某種意義上是最小的切割（圖形的頂點(diǎn)劃分為由至少一個邊連接的兩個不相交的子集）。圖的最小割可以分很多情況進(jìn)行討論水醋，例如有向圖旗笔、無向圖，邊的權(quán)重等拄踪。下圖是一張無向無權(quán)重圖和它的兩個割蝇恶，紅色的線格割掉了三條邊，而綠色的線割掉了兩條邊惶桐，很明顯綠色的線為該圖的最小割撮弧。

image

Graph Cut（圖割）

Graph cuts是一種十分有用和流行的能量優(yōu)化算法，在計算機(jī)視覺領(lǐng)域普遍應(yīng)用于前背景分割（Image segmentation）姚糊、立體視覺（stereo vision）贿衍、摳圖（Image matting）等。

此類方法把圖像分割問題與圖的最小割（min cut）問題相關(guān)聯(lián)叛拷。首先用一個無向圖G=<V舌厨，E>表示要分割的圖像，V和E分別是頂點(diǎn)（vertex）和邊（edge）的集合忿薇。此處的Graph和普通的Graph稍有不同裙椭。普通的圖由頂點(diǎn)和邊構(gòu)成躏哩，如果邊的有方向的，這樣的圖被則稱為有向圖揉燃，否則為無向圖扫尺，且邊是有權(quán)值的，不同的邊可以有不同的權(quán)值炊汤，分別代表不同的物理意義正驻。而Graph Cuts圖是在普通圖的基礎(chǔ)上多了2個頂點(diǎn)，這2個頂點(diǎn)分別用符號”S”和”T”表示抢腐，統(tǒng)稱為終端頂點(diǎn)姑曙。其它所有的頂點(diǎn)都必須和這2個頂點(diǎn)相連形成邊集合中的一部分。所以Graph Cuts中有兩種頂點(diǎn)迈倍，也有兩種邊伤靠。

第一種頂點(diǎn)和邊是：第一種普通頂點(diǎn)對應(yīng)于圖像中的每個像素。每兩個鄰域頂點(diǎn)（對應(yīng)于圖像中每兩個鄰域像素）的連接就是一條邊啼染。這種邊也叫n-links宴合。

第二種頂點(diǎn)和邊是：除圖像像素外，還有另外兩個終端頂點(diǎn)迹鹅，叫S（source：源點(diǎn)卦洽，取源頭之意）和T（sink：匯點(diǎn)，取匯聚之意）斜棚。每個普通頂點(diǎn)和這2個終端頂點(diǎn)之間都有連接阀蒂，組成第二種邊。這種邊也叫t-links打肝。

image.png

相關(guān)論文及python實(shí)現(xiàn)代碼：

PAPER:
1.Fast approximate energy minimization via graph cuts
2.Graph based algorithms for scene reconstruction from two or more views
3.What energy functions can be minimized via graph cuts?
4.Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images
CODE
https://github.com/cm-jsw/GraphCut
參考項(xiàng)目：https://github.com/NathanZabriskie/GraphCut

GrabCut和GraphCut的不同點(diǎn)

（1）GraphCut的目標(biāo)和背景的模型是灰度直方圖脂新，GrabCut取代為RGB三通道的混合高斯模型GMM挪捕；
（2）GraphCut的能量最小化（分割）是一次達(dá)到的粗梭，而GrabCut取代為一個不斷進(jìn)行分割估計和模型參數(shù)學(xué)習(xí)的交互迭代過程；
（3）GraphCut需要用戶指定目標(biāo)和背景的一些種子點(diǎn)级零，但是GrabCut只需要提供背景區(qū)域的像素集就可以了断医。也就是說你只需要框選目標(biāo)，那么在方框外的像素全部當(dāng)成背景奏纪，這時候就可以對GMM進(jìn)行建模和完成良好的分割了鉴嗤。即GrabCut允許不完全的標(biāo)注（incomplete labelling）。

效果：

image

GitHub代碼：

1. https://github.com/downingstreet/GrabCut
2. https://github.com/Orcuslc/GrabCuthttps://github.com/Orcuslc/GrabCut

Grab Cut論文：
“GrabCut”: interactive foreground extraction using iterated graph cuts

參考博客

https://blog.csdn.net/mmm_jsw/article/details/83866624
https://blog.csdn.net/mmm_jsw/article/details/83787395
https://github.com/NathanZabriskie/GraphCut/tree/master/graph_cut
https://blog.csdn.net/zouxy09/article/details/8534954
https://blog.csdn.net/zouxy09/article/details/8532111
https://blog.csdn.net/zouxy09/article/details/8535087