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

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

關鍵詞：圖像分割；圖論；最小割；MFC

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2016）20-0183-02

1 概述

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

圖像分割的定義[2]：

2算法原理

2.1圖論的基本概述

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

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

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

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

2.2最小割/最大流方法

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

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

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

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

3.1設計思路

3.2軟件測試及結果

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

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

4 結論

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

參考文獻：

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

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

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

[4] 楊帆，廖慶敏. 基于圖論的圖像分割算法的分析與研究[J]. 電視技術， 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.