基于標(biāo)準(zhǔn)割(Normalized cut)算法圖像分割方法

安文波

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

1 圖像分割簡(jiǎn)介

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

圖1 圖像處理過程

2 圖論和閾值化分割方法

2.1 圖論分割的原理

(1)

圖論的圖像劃分領(lǐng)域應(yīng)用到圖像分割中來，形成了基于圖論的圖像分割方法該方法是將原圖二值化形成一個(gè)帶權(quán)值的映射圖，首先給定幾個(gè)基本定義如圖2所示[2]，圖中的點(diǎn)對(duì)應(yīng)著像素點(diǎn)或區(qū)域，權(quán)值數(shù)的大小表示著兩個(gè)點(diǎn)之間的相關(guān)性，通過權(quán)值的總和最小而形成的最小代價(jià)路線，這條線使得圖像分割得以實(shí)現(xiàn)。

圖2 圖論分割原理

通過圖2可以看出，圖論方法是應(yīng)用數(shù)學(xué)的一個(gè)計(jì)算方法，將待分割的圖片映射成為一幅無向加權(quán)圖，圖中的點(diǎn)對(duì)應(yīng)圖像的像素點(diǎn)，且像素點(diǎn)構(gòu)成圖中的頂點(diǎn)集，每個(gè)點(diǎn)對(duì)應(yīng)的數(shù)字表示圖像的灰度值，通過權(quán)值公式計(jì)算兩個(gè)像素的權(quán)值并尋找出一條權(quán)值和最小的路徑完成圖像分割。

圖3 圖像分割

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

2.2 閾值分割的原理

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

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

圖4 單個(gè)閾值分割方法

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

圖5 雙閾值圖像分割

如圖5就是使用兩個(gè)閾值將圖像分割為三個(gè)級(jí)別。

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

2.3 改進(jìn)的圖像分割算法

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

3 標(biāo)準(zhǔn)割(Normalized cut)算法

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

(4)

Shi和Malik為了獲得較好的分離效果，提出了提 Normalized Cut 標(biāo)準(zhǔn)割算法，其公式為：

(5)

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

圖6 真實(shí)圖像分割

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

4 結(jié)論

基于當(dāng)今時(shí)代的信息發(fā)展的迅速性和有效性，數(shù)字圖像在人們當(dāng)中越來越受到重視，它是人們獲取信息的主要方式和手段，數(shù)字圖像已經(jīng)滲透生活當(dāng)中各個(gè)領(lǐng)域、各個(gè)技術(shù)行業(yè)，有些時(shí)候人們?yōu)榱送怀鰣D像當(dāng)中比較重要的部分或者需要圖像當(dāng)中的某些信息，這就需要對(duì)數(shù)字圖像處理技術(shù)的要求也在不斷的提高，對(duì)于把圖像當(dāng)中感興趣的部分提取出來所需要的方法，各行業(yè)的人員都在進(jìn)行不斷的創(chuàng)新，對(duì)于其中的疑點(diǎn)和難點(diǎn)也一直在不斷的解決，因此對(duì)于新的理論、新的技術(shù)應(yīng)用在圖像分割領(lǐng)域是非常重要的，本文針介紹的圖像分割方法