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

趙鳳嬌　賀月姣

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

關鍵詞： 邊緣檢測； 暗原色先驗； 圖像分析； K?means

中圖分類號： TN911.73?34 文獻標識碼： A 文章編號： 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

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

1 圖像處理：暗原色先驗

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

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 暗原色先驗

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

1.3 暗原色先驗算法

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

2 邊緣檢測

2.1 初始邊緣檢測

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

2.2 端點標記

端點標記算法：

（1） 取初始二值邊緣einit上的一個像素值為1的邊緣像素點Q；

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

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

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

2.3 確定窗口大小

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

[wui=miny1i，y2i，…yni；]

[wdi=maxy1i，y2i，…yni；]

[wli=minx1i，x2i，…xni；]

[wri=maxx1i，x2i，…xni；]

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 獲取最終邊緣

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

3 實驗結(jié)果

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

4 結(jié) 論

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

參考文獻

[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理論的自適應邊緣檢測方法[J].中國圖象圖形學報，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.