基于標準割(Normalized cut)算法圖像分割方法

安文波

(中國刑事警察學院，遼寧 沈陽 110854)

1 圖像分割簡介

圖像分割是圖像處理中的一項至關重要的技術。自20世紀70年代開始，圖像分割技術一直備受人們的高度重視，到目前為止已經有很多的分割方法，從圖像分割的依據出發，分割方法分為非連續性分割和相似性分割[1]。近年來有很多不同領域的學者們提出的新理論、新方法與圖像分割相結合而形成多種新型分割技術，如聚類分析、圖理論、小波變換、人工神經網絡等分割方法，這些多領域、多類型的分割方法的提出對于圖像分割技術的完善有著重要的作用。圖1是一般的圖像處理過程，從圖中可以看出圖像分割是介于圖像預處理和圖像識別之間，在圖像處理當中起著承上啟下的作用，一方面它是準確提取目標物的處理手段，使人們能夠得到有意義的感興趣對象，另一方面它能夠做到目標準確的識別，特征準確的提取，參數準確的測量等使圖像變得更為簡明、抽象的形式展現在觀察者面前，更容易進行視覺分析和模式識別，并且對后續的圖像識別、分析和理解能夠達到跟高的層次。

圖1 圖像處理過程

2 圖論和閾值化分割方法

2.1 圖論分割的原理

(1)

圖論的圖像劃分領域應用到圖像分割中來，形成了基于圖論的圖像分割方法該方法是將原圖二值化形成一個帶權值的映射圖，首先給定幾個基本定義如圖2所示[2]，圖中的點對應著像素點或區域，權值數的大小表示著兩個點之間的相關性，通過權值的總和最小而形成的最小代價路線，這條線使得圖像分割得以實現。

圖2 圖論分割原理

通過圖2可以看出，圖論方法是應用數學的一個計算方法，將待分割的圖片映射成為一幅無向加權圖，圖中的點對應圖像的像素點，且像素點構成圖中的頂點集，每個點對應的數字表示圖像的灰度值，通過權值公式計算兩個像素的權值并尋找出一條權值和最小的路徑完成圖像分割。

圖3 圖像分割

圖3在使用MATLAB軟件進行的圖論分割方法分割出來的圖像，在MATLAB中通過計算灰度級強度差找到權值求和最小也就是代價最小的路徑完成分割。

2.2 閾值分割的原理

閾值分割方法是圖像分割的一項悠久而又關鍵的技術，所謂閾值就是事先設定一個值，閾值分割就是對圖像的灰度分成不同的等級，然后設定一個閾值與圖像中不同的灰度等級進行比較，根據比較將圖像灰度像素分成兩個區域，分別是目標區域和背景區域，從而達到分割的目的。假定圖像的設定的閾值為n，那么圖像中的像素等級也就被閾值分成兩部分，輸入圖像f(x,y)，輸出圖像f′(x,y)，則：

這就是閾值化分割方法。圖4是使用單個閾值方法將圖像分割為目標物和背景圖兩部分

圖4 單個閾值分割方法

由于實際需要的圖像目標與背景圖之間存在許多灰度等級，那么就需要兩個或兩個以上閾值對圖像進行分割提取目標物。如(n1,n2)作為圖像分割的閾值，那么就需要兩個公式對圖像進行二值化處理。

圖5 雙閾值圖像分割

如圖5就是使用兩個閾值將圖像分割為三個級別。

目前，由于圖像中往往有各種噪聲，最佳閾值的選擇仍然是一項難題，在尋找最短路徑是非常耗費時間的，如果提高速度那么就會使得精度會降低，如果提高選擇精度那么又會很耗費時間，急需找到以一種合適的算法處理最佳閾值的選擇問題。到目前為止，閾值分割方法有很多，較為經典的方法有：基于直方圖的Ramesh閾值分割方法；基于空間信息的Pal閾值圖像分割方法；基于屬性相似度Pikaz閾值圖像分割方法；基于熵的Kapur閾值圖像分割方法；基于聚類分割的Kittler閾值圖像分割方法；以及基于局部信息的Yanowitz閾值圖像分割方法；這些方法有自己獨特的優點，也有解決不了的缺點，仍然有很多學者在這個方面進行深刻的研究，嘗試者解決這一難題。

2.3 改進的圖像分割算法

雖然基于圖論的分割方法在圖像處理上有很好的發展空間和應用效果，但是單純的使用這種方法仍然存在一些不足和缺陷，在區間數據很接近的情況下使用這種方法的弊端體現的很明顯。因此，針對其不足的地方進行改進，使這種方法在圖像分割領域能有更好的應用前景。閾值化圖像分割是一種區域分割技術，通過設置一個合理的閾值，然后將圖像中所有的灰度值與之進行比較，大于或等于閾值的像素被劃分為分離出的物體，小于閾值的部分就是物體之外的。因此，只要能夠選擇到最佳閾值圖像的分割就很容易實現。這種簡單易行的方法和基于圖論的圖像分割方法相結合，能夠很好的彌補圖論方法在圖像分割當中的不足之處。針對以上問題，采用 標準割Normalized Cut 割集方法[3]與閾值結合來實現目標和背景的精確分離，一種典型的分割圖像分割方法。

3 標準割(Normalized cut)算法

如前文中所提到的，將一幅圖表示成空間點集的無向加權圖G=(A,B)其中V是定點集合，E是兩點連接的邊集合，w(u,v)是對兩個節點連接成的邊賦予權值 ，將圖像分割成A和B兩個部分的點集，其中V是A和B的集合V=A+B，A和B之間的差異程度可表示為移去兩區間所有節點連接的邊的權值之和所付出的代價，稱為割cut，表示為：

(4)

Shi和Malik為了獲得較好的分離效果，提出了提 Normalized Cut 標準割算法，其公式為：

(5)

近些年來，圖像分割方法中譜聚類方法一直是大家研究的熱門，諸如此類方法有很多種，如標準分割(Normalized cut，Ncut)算法、比例分割(Ratio cut，Rcut)方法[4]、以及最小最大割(Min-max cut，Mcut)算法[5]等。該類方法是將圖構造一個帶帶頂點集的加權圖，然后通過求矩陣的特征值和特征向量來獲得譜聚類的結果。本文針對標準割算法進行了進一步的研究，該方法可以很好的克服被劃分出來的圖像中的孤立點，但是由于計算量較大且類間重疊較大時易出現彎斜劃分。 圖6是采用核磁拍攝的PDWI圖(質子密度加權圖)，并通過MATLAB進行了圖像分割。采用改進后的標準割算法對圖像進行分割，能夠有效的克服前文中所產生的圖像孤立點問題。

圖6 真實圖像分割

圖中邊緣部分為腦袋顱骨，中間部分為腦組織，從可以看出才用此方法可以很容易的對顱骨和腦組織進行圖像分割。

4 結論

基于當今時代的信息發展的迅速性和有效性，數字圖像在人們當中越來越受到重視，它是人們獲取信息的主要方式和手段，數字圖像已經滲透生活當中各個領域、各個技術行業，有些時候人們為了突出圖像當中比較重要的部分或者需要圖像當中的某些信息，這就需要對數字圖像處理技術的要求也在不斷的提高，對于把圖像當中感興趣的部分提取出來所需要的方法，各行業的人員都在進行不斷的創新，對于其中的疑點和難點也一直在不斷的解決，因此對于新的理論、新的技術應用在圖像分割領域是非常重要的，本文針介紹的圖像分割方法