從GraphCut到GrabCut的OpenCV實現：圖像分割

05-31

圖像分割一直是圖像處理中一項棘手的問題。圖像分割演算法從大的方面講可以分為兩類：

1 全自動圖像分割：一般採用聚類演算法來最大化前景與背景的差。

2 用戶互動式圖像分割：用戶提供前景和背景的種子，然後對前景背景建立概率分布模型。

而GraphCut和GrabCut就是屬於第二類圖像分割演算法。首先來說GraphCut。

GraphCut：

將圖像中的每一個像素看成Graph中的一個Node，然後在Graph中增加兩個Node，分別為F和B，F代表Foreground前景，而B代表Background背景，具體圖如下：

然後每兩個相鄰像素點用一條邊連起來，每一個像素點和F點用一條邊連起來，每一個像素點和B點也用一條邊連起來。然後一個切割就是將圖像分成兩部分，第一部分的像素點和F相連為前景，第二部分的像素點和B相連為背景。這樣一個切割是通過優化以下的能量函數來實現的：

其中g(X)為Data項，由像素v屬於前景和屬於背景的概率決定。而h(v,u)為Smoothness項，由像素v和其鄰接像素u的相似程度決定。最簡單的前景背景概率計算就是基於圖像的直方圖，而衡量兩個相鄰像素點相似度的方法最簡單的則用其灰度值的差來表示。通過上式可以看到，能量的最優化其實是將最有可能是前景的列為一組，最有可能是背景的列為一組，然後將灰度差最大的相鄰像素切割開來，這樣的分割為全局最優分割。

下圖為一個具體例子，其中紅線和綠線為用戶提供的背景和前景的種子。

GrabCut：

GraphCut需要用戶提供精確的前景背景的種子，而且當提供的種子無法覆蓋所有分布時，必然會影響分割的準確度。為了解決這個問題，微軟研究室提出了更加快捷高效的GrabCut分割演算法。GrabCut需要用戶提供一個長方形，長方形包含前景，而長方形外是背景。GrabCut具體步驟如下：

1：長方形外的Pixels作為背景Pixel，長方形內的Pixels作為前景Pixel，用著兩組去Train背景GMM和前景，GMM(這裡GMM指高斯混合模型)。

2：用訓練好的兩個GMM來計算每一個像素屬於背景和屬於前景的概率，進而計算出能量函數E中的Data項，能量函數中的Smoothness項的計算方法大致與GraphCut相同。

3：通過最優化能量函數得到圖像的一個分割。

4：用3中的分割結果中的前景Pixels和背景Pixels去訓練前景GMM和背景GMM.

5：重複2，3，4，直到分割結果收斂(不再有大的變化)。

由以上步驟可以看出，GrabCut是一個循環執行的演算法，其循環的目的是為了EM（Expectation Maximization）。因為用戶提供的長方形內也有部分背景像素，所以這樣的種子是不完全正確的。好在GMM模型並不要求所有的訓練數據正確，即使有一部分分類不正確，也可以通過EM步驟使得最終結果正確。而GrabCut正是利用了GMM的這一特性。值得注意的是，GMM有陷入局部最優的問題無法解決，所以GrabCut也有此問題。下面用圖說明GrabCut分割結果，相比其他的分割演算法，GrabCut的效果還是很不錯的。

以下是GrabCut的OpenCV代碼，有興趣的可以試著運行一下：

#include "highgui.h"

#include "cv.h"

#include "features2d/features2d.hpp"

#include "opencv/cxcore.hpp"

#include "cvaux.h"

using namespace std;

using namespace cv;

void main()

{

cv::Mat bgModel, fgModel, mask;

//按照需要修改以下的長方形位置

cv::Rect rect;

rect.x = 20;

rect.y = 30;

rect.width = 100;

rect.height = 200;

//讀入圖像

Mat Img= imread(「C：//1.jpg」);

//循環執行3次，這個可以自己設置

cv::grabCut(Img, mask, rect, bgModel, fgModel, 3, cv::GC_INIT_WITH_RECT);

cv::compare(mask, cv::GC_PR_FGD, mask, cv::CMP_EQ);

imshow("mask", mask);

cvWaitKey(0);

}