基于圖論的圖像分割軟件設(shè)計

姬治華++曹金香++楊發(fā)順

摘要：本文設(shè)計了一款基于圖論的圖像分割軟件，并對交互方式進(jìn)行了改進(jìn)。該軟件基于VS2010軟件平臺和OpenCV庫，使用C++作為開發(fā)語言，運(yùn)用MFC進(jìn)行軟件界面和對話框的設(shè)計，為圖像分割提供了一個良好的界面交互環(huán)境和可視化平臺。

關(guān)鍵詞：圖像分割；圖論；最小割；MFC

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）20-0183-02

1 概述

圖像分割是計算機(jī)視覺中最基本最重要的研究內(nèi)容之一，對圖像處理、圖像分析和圖像理解起著關(guān)鍵性的作用。所謂圖像分割是指根據(jù)圖像的某個特定屬性將圖像劃分為若干個互不交疊的區(qū)域，并從中提取目標(biāo)的過程[1]。

圖像分割的定義[2]：

2算法原理

2.1圖論的基本概述

圖論（Graph Theory）是數(shù)學(xué)的一個分支，它以圖為研究對象。圖論中的圖是由點(diǎn)和連接兩點(diǎn)的線所構(gòu)成，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)的兩個事物之間具有的某種關(guān)系[3]。

基于圖論的圖像分析指將待處理的圖像映射為帶權(quán)的無向連通圖G=（V，E，W），節(jié)點(diǎn)集V是圖I中所有像素點(diǎn)的集合，邊集E表示連接兩個鄰接頂點(diǎn)的邊的集合，W表示每條邊權(quán)值的集合，邊的權(quán)值反映了該邊的兩個頂點(diǎn)的差異或相似度。

權(quán)值集合W的構(gòu)建是圖像分割成功的關(guān)鍵，好的相似度度量函數(shù)需要體現(xiàn)出兩個節(jié)點(diǎn)在顏色、亮度、距離等方面的相似程度。常用的相似度度量函數(shù)有特征空間的歐氏距離：

作為相似度的度量函數(shù)，前者的優(yōu)點(diǎn)是直觀且計算簡單，后者的優(yōu)點(diǎn)是與實(shí)際情況更加接近，但是運(yùn)算量較大[4]。

2.2最小割/最大流方法

基于圖論的分割方法是將整幅圖像映射為圖，圖的頂點(diǎn)和圖中像素一一對應(yīng)，根據(jù)一定的割集準(zhǔn)則將圖劃分為兩個子圖，使得子圖之間的相似性最小，而子圖內(nèi)的相似性最大[5]。圖割示意圖如圖1所示：

使得代價函數(shù)最小的劃分即為圖像的最佳分割，也即圖的最小割。

最小割/最大流方法主要包括兩大類[6]：推進(jìn)重標(biāo)記（Push relabel）方法和增廣路徑（Augmenting paths）方法。推進(jìn)重標(biāo)記法易于并行實(shí)現(xiàn)，通常采用GPU加速實(shí)現(xiàn)來提高效率?；谠鰪V路徑的方法通過標(biāo)號不斷生長一棵樹，直到找不到關(guān)于可行流的增廣路徑為止。該類方法的計算復(fù)雜性和網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和邊數(shù)無關(guān)，而與邊上的權(quán)值有關(guān)。

3軟件系統(tǒng)設(shè)計

3.1設(shè)計思路

3.2軟件測試及結(jié)果

單擊選擇圖像按鈕讀入待分割圖像，根據(jù)圖像中目標(biāo)的形狀選擇交互方式，單擊分割按鈕運(yùn)行分割程序，矩形交互和圓形交互分割結(jié)果分別如圖3和圖4所示：

從上圖可以看出，分割結(jié)果圖像邊緣比較光滑，所設(shè)計軟件操作簡便且具有較好的分割效果。

4 結(jié)論

基于圖論的分割方法可以將圖像的全局分割與局部信息處理相結(jié)合，可減少由于圖像離散化造成的誤差，從而可獲得良好的分割結(jié)果。本系統(tǒng)具有如下技術(shù)特點(diǎn)：（1）將原始圖像，交互圖像和分割后圖像顯示在同一界面上，運(yùn)算結(jié)果形象直觀，便于用戶觀察；（2）界面簡潔，操作簡單，運(yùn)行效率和分割精度較高。

參考文獻(xiàn)：

[1] 章毓晉. 圖像分割[M].北京：科學(xué)出版社， 2000.

[2] 羅希平， 田捷， 諸葛嬰，等. 圖像分割方法綜述[J]. 模式識別與人工智能， 1999（3）：300-312.

[3] 張建梅， 孫志田， 余秀萍. 基于圖論的圖像分割算法仿真研究[J]. 計算機(jī)仿真， 2011， 28（12）： 268-271.

[4] 楊帆，廖慶敏. 基于圖論的圖像分割算法的分析與研究[J]. 電視技術(shù)， 2006 （7）： 80-83.

[5] Sarkar S， Soundararajan P. Supervised learning of large perceptual organization： Graph spectral partitioning and learning automata[J]. Pattern Analysis and Machine Intelligence， IEEE Transactions on， 2000， 22（5）： 504-525.

[6] Boykov Y， Veksler O. Graph cuts in vision and graphics： Theories and applications[M]. Handbook of mathematical models in computer vision. Springer US， 2006： 79-96.