基于改進(jìn)的K?means聚類算法水下圖像邊緣檢測

趙鳳嬌　賀月姣

摘 要： 邊緣檢測被廣泛用于圖像分析與處理中，由于水的吸收和散射效應(yīng)，傳統(tǒng)的邊緣檢測算法對(duì)于水下圖像得不到較好的效果。在此應(yīng)用一種新的方法來得到較準(zhǔn)確的水下圖像邊緣，首先，將原始圖像使用暗原色先驗(yàn)算法進(jìn)行處理得到較清晰的水下圖像；然后，使用梯度幅值邊緣檢測算法檢測出初始邊緣，在初始邊緣上檢測出端點(diǎn)，使用改進(jìn)的K?means聚類算法對(duì)端點(diǎn)進(jìn)行分類，從而確定背景和目標(biāo)灰度值接近的區(qū)域作為窗口；最后，在窗口內(nèi)使用梯度幅值檢測邊緣，通過多個(gè)窗口的并集得到最終邊緣。實(shí)驗(yàn)結(jié)果表明，邊緣檢測效果得到明顯的改善。

關(guān)鍵詞： 邊緣檢測； 暗原色先驗(yàn)； 圖像分析； K?means

中圖分類號(hào)： TN911.73?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）20?0089?03

Abstract： Edge detection is widely used in image analysis and processing. The traditional edge?detection algorithms are always ineffective to underwater images due to the absorption and scattering nature of seawater. A new approach is used in this paper to obtain the accurate edges of underwater images. Firstly， the original image is processed with the dark primary colour prior algorithm to get the clearer image. Then， the initial edge is calculated by the gradient magnitude edge detecting algorithm， the endpoints in the initial edge of the image are detected， and the modified K?means clustering algorithm is used to classify the endpoints to determine the region where the gray?scale of background and target is approximate as the window. Finally， the edge is detected in the window by the adaptive gradient magnitude， and then the final edge is got by union set of multiple windows. The edge detection result is significantly improved.

Keywords： edge detection； dark primary colour prior； image analysis； K?menas

圖像邊緣檢測是圖像處理與分析中最基礎(chǔ)的內(nèi)容之一，被廣泛用于特征描述、圖像分割、圖像增強(qiáng)、模式識(shí)別以及圖像壓縮等。因此，邊緣檢測在圖像處理與分析中成為一個(gè)研究熱點(diǎn)，新的理論和方法不斷地被提出。目前經(jīng)常使用的算法有Roberts，Sobel，Prewitt， LoG，Canny，Kirsch等，但這些經(jīng)典的邊緣檢測方法不能很好地用于水下圖像。本文使用一種改進(jìn)的邊緣檢測算法來得到較準(zhǔn)確的水下圖像邊緣。

1 圖像處理：暗原色先驗(yàn)

由于水體對(duì)光的吸收效應(yīng)和散射效應(yīng)使得水下圖像有嚴(yán)重的非均勻亮度和細(xì)節(jié)模糊、信噪比很低、對(duì)比度明顯變差，因而水下圖像極不理想。本文使用暗原色先驗(yàn)方法得到相對(duì)清晰地原始圖像。

1.1 水下光的物理特性

根據(jù) McCartney model[1]， 圖像模型如下：

[Ix=Jxtx+A[1-tx]] （1）

式中：I為輸入的場景圖像；J為場景輻射率；A為大氣光成分；t為光線透射率。

透射率t可表示為：

[tx=e-a+bdx] （2）

式中：a為吸收系數(shù)；b為散射系數(shù)；d（x）是景物深度。

1.2 暗原色先驗(yàn)

根據(jù)Hes research[2]，該理論認(rèn)為：在絕大多數(shù)戶外無霧圖像的局部區(qū)域里，至少存在一些像素，其一個(gè)顏色通道的強(qiáng)度值很低。He統(tǒng)計(jì)了5 000多幅圖像，暗原色通道的統(tǒng)計(jì)結(jié)果如圖1所示。大約75%的暗原色通道的像素值為0，90%的像素值低于0.25。

1.3 暗原色先驗(yàn)算法

算法流程圖[3]如圖2所示。在水下圖像中，限定的局部區(qū)域內(nèi)存在至少一個(gè)顏色通道的強(qiáng)度值很低，假設(shè)這個(gè)區(qū)域?yàn)棣福▁），則水下圖像J的暗原色可表示為：

2 邊緣檢測

2.1 初始邊緣檢測

首先使用Sobel[4]算法檢測出初始邊緣，將邊緣細(xì)化[5]為一個(gè)像素。將細(xì)化后的邊緣作為初始邊緣并記為einit。

2.2 端點(diǎn)標(biāo)記

端點(diǎn)標(biāo)記算法：

（1） 取初始二值邊緣einit上的一個(gè)像素值為1的邊緣像素點(diǎn)Q；

（2） 將該像素點(diǎn)的8鄰域內(nèi)的像素值按照順序展開成一維數(shù)組，并在該一維數(shù)組中尋找模式“01”個(gè)數(shù)C；

（3） 將當(dāng)前像素點(diǎn)的值Q和C做“與”運(yùn)算，若計(jì)算結(jié)果為1，則說明該點(diǎn)是端點(diǎn)，否則不是；

（4） 取下一個(gè)沒有檢測過的的邊緣點(diǎn)，循環(huán)執(zhí)行步驟（2）與步驟（3），直到所有邊緣點(diǎn)被檢測完。

2.3 確定窗口大小

使用K?means聚類算法[6]對(duì)檢測出的N個(gè)端點(diǎn)進(jìn)行分類，假設(shè)初始邊緣端點(diǎn)為{（x1，y1），（x2，y2），…，（xN，yN）}，使用改進(jìn)的K?means聚類算法將N個(gè)邊緣端點(diǎn)分成k類，若第i（i=1，2，…，k）個(gè)分類的集合為[Ci=（x1i，y1i），（x2i，y2i），…，（xni，yni）]，則第i個(gè)窗口上下左右邊界分別為：

[wui=miny1i，y2i，…yni；]

[wdi=maxy1i，y2i，…yni；]

[wli=minx1i，x2i，…xni；]

[wri=maxx1i，x2i，…xni；]

因此[wi=wli：wri，wui：wdi]。

K?means算法的基本思想是初始隨機(jī)給定k個(gè)聚類中心，按照最鄰近原則把待分類樣本點(diǎn)分到各個(gè)聚類中。然后按平均法重新計(jì)算各個(gè)聚類的質(zhì)心，從而確定新的聚類中心。一直迭代，直到類心的移動(dòng)距離小于某個(gè)給定的值。

根據(jù)Tou and Gonzalez[7]傳統(tǒng)K?means算法步驟如下：

（1） 選取k個(gè)初始聚類中心z1（1），z2（1），…，zk（1）。

（2） 計(jì)算每個(gè)點(diǎn)到聚類中心的距離，將每個(gè)點(diǎn)聚類到離該點(diǎn)最近的聚類中去，即若[||x-zj（k）||<||x-zi（k）||]，則[x∈Cjk， j=1，2， …，k；i≠j；]Cj（k）表示聚類中心為zj（k）的樣本集。

（3） 重新計(jì)算聚類中心zj（k+1）：

[zjk+1=1Njx∈Cjkx， j=1，2， …，k]

式中：Nj表示樣本集Cj（k）的樣本個(gè)數(shù)。

（4） 如果[zjk+1=zjk， j=1，2， …，k]，停止迭代；否則轉(zhuǎn)到步驟（2）。

改進(jìn)的聚類算法[8]：傳統(tǒng)的K?means聚類算法要求必須先給出分類個(gè)數(shù)k，然后隨機(jī)選取k個(gè)對(duì)象作為初始聚類中心，并且算法對(duì)初始值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同的聚類結(jié)果。本文對(duì)傳統(tǒng)的K?means算法進(jìn)行改進(jìn)，通過計(jì)算得出較好的聚類個(gè)數(shù)與聚類中心，改進(jìn)步驟如下：

（1） 將分類端點(diǎn)轉(zhuǎn)換為7個(gè)不同維數(shù)的二維矩陣；

（2） 計(jì)算每一維數(shù)矩陣的平均值，平均值相同的舍去其中一個(gè)，然后將平均值升序排序；

（3） 平均值個(gè)數(shù)與平均值分別作為聚類個(gè)數(shù)與聚類中心。

2.4 獲取最終邊緣

將初始邊緣基礎(chǔ)上找到的聚類區(qū)域映射到原始圖像，然后對(duì)原始圖像中的相應(yīng)區(qū)域使用梯度幅值邊緣檢測算法監(jiān)測區(qū)域內(nèi)的邊緣，可得到區(qū)域內(nèi)較好的邊緣效果；若要得到整幅圖像的邊緣，則只需要將每個(gè)區(qū)域的邊緣和初始邊緣求并集即可。假設(shè)第i個(gè)窗口內(nèi)檢測到的邊緣為eωi，則將初始邊緣和每個(gè)窗口區(qū)域內(nèi)的邊緣求并集即可得到最終的邊緣e，即[e=i=1keinit∪eωi]。

3 實(shí)驗(yàn)結(jié)果

在海洋實(shí)驗(yàn)中，獲得圖片如圖3（a）所示，經(jīng)過暗原色先驗(yàn)算法進(jìn)行處理過的圖像如圖3（b）所示。經(jīng)過Sobel，Canny[9]，Prewitt[10]和改進(jìn)算法所得到的邊緣圖像如圖3（c）～（f）所示。實(shí)驗(yàn)結(jié)果顯示，Sobel和Prewitt算法均不能獲得相對(duì)較完整的圖像邊緣，Canny算法可以得到完整的邊緣，可是存在太多的冗余邊緣，細(xì)節(jié)較多。本文算法相比于傳統(tǒng)算法有較大改善，不但去除了很多不必要的冗余，而且可檢測到相對(duì)完整的邊緣。

4 結(jié) 論

本文提出了一種新方法用于處理水下不清晰圖像，并獲得相對(duì)較完整的邊緣。實(shí)驗(yàn)結(jié)果顯示暗原色先驗(yàn)算法可以有效的去除后向散射噪聲，增強(qiáng)圖像的分辨率和對(duì)比度。傳統(tǒng)的邊緣檢測方法對(duì)于檢測水下圖像邊緣效果不理想，改進(jìn)的算法可以檢測出相對(duì)完整的邊緣。

參考文獻(xiàn)

[1] MATTIS M P， PESKIN M E. Systematics of πN scattering in chiral soliton models [J]. Physical Review D， 1985， 32（1）： 58?62.

[2] HE K， SUN J， TANG X. Single image haze removal using dark channel prior [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（12）： 2341?2353.

[3] WANG Z， ZHENG B， TIAN W. New approach for underwater image denoise combining inhomogeneous illumination and dark channel prior [C]// Proceedings of Oceans?St. [S.l.]： IEEE， 2013：111?116.

[4] ZHAO Jingdong， ZHAO Jingxiu. An improved self?adaptable algorithm of edge?detection based on the gradient magnitude[J]. Optoelectronic Technology， 2009， 2： 5?10.

[5] ZHANG T Y， SUEN C Y. A fast parallel algorithm for thinning digital patterns [J]. Communications of the ACM， 1984， 27（3）： 236?239.

[6] VASSILVITSKII S. K?Means： algorithms， analyses， experiments[M]. Stanford， CA USA： Stanford University，2007.

[7] TOU J T， GONZALEZ R C. Pattern recognition principles [M]. [S.l.]： Addison?Wesley Publishing Company， 1974.

[8] SAMMA A S B， SALAM R A. Adaptation of K?means algorithm for image segmentation [J]. World Academy of Science， Engineering and Technology， 2009， 50： 58?62.

[9] 王植，賀賽先.一種基于Canny理論的自適應(yīng)邊緣檢測方法[J].中國圖象圖形學(xué)報(bào)，2005，9（8）：957?962.

[10] GONZALEZ R C， WOODS R E， EDDINS S L. Digital image processing using Matlab [M]. India： Pearson Education， 2004.