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

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

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

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

1 概述

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

圖像分割的定義[2]：

2算法原理

2.1圖論的基本概述

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

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

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

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

2.2最小割/最大流方法

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

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

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

3軟件系統設計

3.1設計思路

3.2軟件測試及結果

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

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

4 結論

基于圖論的分割方法可以將圖像的全局分割與局部信息處理相結合，可減少由于圖像離散化造成的誤差，從而可獲得良好的分割結果。本系統具有如下技術特點：（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.