基于梯度 Hough 變換和 K-medoids 聚類的年輪髓心定位

薛怡寧　何明栩　徐川晴　劉潤(rùn)萌

摘要：為實(shí)現(xiàn)不同條件下年輪髓心的自動(dòng)定位，本文提出一種基于梯度Hough變換和K-medoids算法的年輪髓心定位算法。首先應(yīng)對(duì)年輪圖片進(jìn)行預(yù)處理，將彩色圖片灰度化，并進(jìn)行降噪、圖像分割。然后通過(guò)Sobel算子提取邊緣，利用基于梯度變換的Hough變換計(jì)算得到若干疑似髓心。最后利用K-medoids算法對(duì)疑似髓心進(jìn)行聚類，得到最終的髓心。實(shí)驗(yàn)結(jié)果表明，該算法定位的髓心與人工標(biāo)定的髓心重合度較高，具有一定的實(shí)用性。

[關(guān)鍵詞]髓心定位 變換 K-medoids 聚類梯度Hough

木材髓心由一年生幼莖的初生木質(zhì)部構(gòu)成，位于木材中間，由于其位置的特殊性而被選為測(cè)量年輪參數(shù)的常用點(diǎn)?，F(xiàn)今流行的年輪分析系統(tǒng)，如WinDENDRO等，通過(guò)定位年輪髓心，可進(jìn)行年輪相關(guān)參數(shù)的檢測(cè)。例如，根據(jù)確定的髓心生成直線，通過(guò)記錄過(guò)中心的直線與年輪總體相交的次數(shù)得到年輪數(shù)目;通過(guò)計(jì)算同一;直線上相鄰灰度值為0的像素之，間的距離來(lái)確定年輪寬度。年輪髓心的定位既可通過(guò)人為手動(dòng)指定，也可通過(guò)系統(tǒng)算法自動(dòng)定位。但由于手動(dòng)指定常常存在主觀性與測(cè)量誤差，年輪參數(shù)的測(cè)量會(huì)受到很大程度的影響。

年輪髓心定位對(duì)于測(cè)量樹(shù)木年輪寬度以及年齡具有重要意義，許多學(xué)者在其研究中使用不同的方法定位髓心，以進(jìn)一步計(jì)算年輪寬度、樹(shù)齡等重要參數(shù)。陳佶在其自動(dòng)化年輪分析系統(tǒng)中將年輪圖像進(jìn)行水平垂直掃描，年輪數(shù)目最大的直線用于進(jìn)行定位髓心;王燕鳳提出一種多角度半徑追蹤統(tǒng)計(jì)的樹(shù)齡測(cè)量方法，在該方法中需手動(dòng)定位髓心;趙娟娟等在其年輪寬度測(cè)量方法中使用AutoCAD添加輔助線來(lái)定位髓心。

本文提出一種基于梯度Hough變換和K-medoids聚類的年輪髓心定位算法，利用Hough變換獲得一定半徑范圍內(nèi)的多個(gè)年輪髓心，使用K-medoids聚類得到整體年輪的髓心，實(shí)現(xiàn)年輪樣本圖像的批量處理。實(shí)驗(yàn)證明該算法對(duì)年輪髓心的定位快速準(zhǔn)確，具有較高實(shí)用性。

1相關(guān)技術(shù)介紹

1.1基于圓檢測(cè)的Hough變換

在圖像處理中，Hough變換常用來(lái)進(jìn)行物體識(shí)別與特征檢測(cè)。最初由PaulHough于1962年提出并應(yīng)用于直線檢測(cè)中，但使用時(shí)存在一定缺陷。RichardDuda和PeterHart于1972年對(duì)其進(jìn)行改進(jìn)，提出廣義Hough變換，自此Hough變換不僅可以用于檢測(cè)直線，還可用于檢測(cè)任何形狀，常見(jiàn)的有圓形、橢圓形。

但Hough變換存在著一定缺陷，如計(jì)算量大、占用內(nèi)存大等。因此許多改進(jìn)算法也被相繼提出，如：利用圓的中心對(duì)稱特征計(jì)算圓心，將傳統(tǒng)Hough變換檢測(cè)圓的三維空間轉(zhuǎn)為一維空間并對(duì)一維Hough變換進(jìn)行半徑累加，得到圓半徑;分析圓周點(diǎn)與鄰域內(nèi)其他點(diǎn)的位置關(guān)系從而判斷出圓心方向和圓周邊緣的凹凸性，以圓弧中心線的累加結(jié)果確定圓心;通過(guò)對(duì)圖像提取邊緣后的輪廓進(jìn)行二次篩選，并對(duì)候選邊緣點(diǎn)組進(jìn)行快速點(diǎn)Hough變換圓檢測(cè)以計(jì)算圓心坐標(biāo)和圓直徑;采用一維霍夫變換方法累積待檢測(cè)圓直徑，與設(shè)定閾值比較來(lái)確定圓心和半徑。

綜合年輪的特性，本文選用梯度Hough變換作為本文算法的基礎(chǔ)。梯度Hough變換可理解為是一種基于梯度信息的改進(jìn)的Hough變換算法，其應(yīng)用也十分廣泛：利用梯度Hough算法進(jìn)行油菜籽圖像的分割、使用基于梯度Hough變換的目標(biāo)定位算法來(lái)定位自然環(huán)境中被遮擋的蘋果、以及識(shí)別和檢測(cè)機(jī)場(chǎng)道面地?zé)舻取?/p>

1.2K-medoids聚類

K-medoids算法是一種經(jīng)典的基于劃分的聚類算法，因強(qiáng)魯棒性、對(duì)噪聲數(shù)據(jù)及異常點(diǎn)處理能力強(qiáng)等優(yōu)勢(shì)被廣泛應(yīng)用，可認(rèn)為是在另一經(jīng)典算法K-Means的基礎(chǔ)上進(jìn)行改進(jìn)。K-Means算法選擇每個(gè)類簇所有樣本的均值作為聚類中心。與K-Means相比，K-medoids算法則以類簇的中位數(shù)為聚類中心，解決了K-Means易于陷入局部最優(yōu)的缺陷，同時(shí)也排除孤立點(diǎn)帶來(lái)的負(fù)面影響。

許多學(xué)者致力于改進(jìn)K-medoids算法，并將其應(yīng)用于不同的學(xué)科領(lǐng)域中。一種改進(jìn)的K-medoids算法引入粒度概念，克服了傳統(tǒng)算法中聚類結(jié)果隨初始中心變動(dòng)以及計(jì)算雜度較高的缺陷;基于MapReduce編程模型的K-medoids并行算法解決了傳統(tǒng)K-medoids在處理海量數(shù)據(jù)時(shí)帶來(lái)的內(nèi)存容量和CPU處理速度的瓶頸;將K-medoids算法與遺傳算法和模擬退火算法相結(jié)合，增強(qiáng)了傳統(tǒng)K-medoids算法在聚類時(shí)的全局搜索能力并加快其收斂能力。

2年輪髓心定位

2.1整體流程

年輪的形狀為若干同心圓輪紋，且髓心位于年輪中心，因此髓心定位的本質(zhì)是尋找樹(shù)木橫切面上若干年輪線的近似圓心，并計(jì)算這些近似圓心的中心。于是，對(duì)于髓心定位，首先應(yīng)對(duì)年輪圖片進(jìn)行預(yù)處理。具體分為三個(gè)小步驟：

（1）轉(zhuǎn)化彩色圖像為灰度圖像;

（2）使用雙邊濾波器進(jìn)行濾波降噪;

（3）利用自適應(yīng)閾值分割算法進(jìn)行圖像分割以提取年輪輪廓。

預(yù)處理完成后，利用基于梯度變換的Hough圓檢測(cè)，得到若干近似圓心。最后利用K-medoids算法對(duì)近似圓心進(jìn)行聚類，得到最終結(jié)果。算法流程如圖1所示。

2.2年輪圖像預(yù)處理

一般得到的樹(shù)木橫截面圖片多為各種格式的三通道彩色圖像。彩色圖像雖較好的保留了原年輪圖像的特征，但因其較為復(fù)雜，進(jìn)行后續(xù)處理會(huì)造成一定的系統(tǒng)負(fù)載，因此需將彩色圖像轉(zhuǎn)換為灰度圖像。將年輪圖片灰度化后，利用雙邊濾波對(duì)圖像進(jìn)行處理，達(dá)到保持邊緣、降噪平滑的效果。對(duì)于年輪輪廓提取選取自適應(yīng)閾值算法，該算法不僅考慮周邊鄰域的情況進(jìn)行圖像分割處理而且處理速度較快，提取結(jié)果如圖2所示。

2.3梯度Hough變換髓心檢測(cè)

傳統(tǒng)Hough圓檢測(cè)的基本思想在于證據(jù)積累，通常圓檢測(cè)的參數(shù)空間是三維的，在三維空間上進(jìn)行證據(jù)累加會(huì)導(dǎo)致計(jì)算量大，占用內(nèi)存大，不適用于大批量處理年輪采集樣本圖像。因此，本文提出一種基于梯度Hough變換的髓心檢測(cè)算法，算法描述如下：

（1）掃描原圖像，利用Sobel算子對(duì)原圖像求梯度，并且對(duì)求得的梯度圖像進(jìn)行閾值變換。利用公式（1）求其梯度方向角θ（其中Gx和G，表示圖像在每個(gè)像素位置上的偏導(dǎo)數(shù)

（2）因樹(shù)木生長(zhǎng)環(huán)境的不同，會(huì)存在偏

心年輪的情況，即年輪輪紋線呈橢圓形。通過(guò)觀察，發(fā)現(xiàn)靠近年輪髓心位置的年輪線更接近于正圓形，因此為增加髓心定位的準(zhǔn)確性，減少迭代的次數(shù)，須將r限制在一"定的范圍內(nèi)。假設(shè)年輪最外層輪廓線的形狀近似橢圓，長(zhǎng)半軸為m，短半軸為n，參數(shù)r的最小值為rmim，in'最大值為rmx，則

較為明顯，rmx的取值應(yīng)盡量接近于下限;若髓心附近年輪較為稀疏，rmim的取值應(yīng)盡量接近于上限。在一個(gè)對(duì)半徑r的循環(huán)中按公式（2）求得圓心坐標(biāo)a、b的值（其中x和y為當(dāng)前像素點(diǎn)的坐標(biāo);r為半徑;θ為求得的梯度方向角），累加數(shù)組同步進(jìn)行累加操作。最終，累加數(shù)組中最大值所對(duì)應(yīng)元素的a和b就是被檢測(cè)圓的圓心坐標(biāo)。

圓心檢測(cè)結(jié)果如圖3所示，其中綠色的點(diǎn)表示檢測(cè)到的圓心，藍(lán)色的圓環(huán)表示圓心所在的圓環(huán)。因年輪形狀的不規(guī)則，檢測(cè)到的為近似結(jié)果。

2.4K-medoids聚類定位髓心

因上文是對(duì)半徑r在一個(gè)特定范圍內(nèi)的圓進(jìn)行圓心定位，會(huì)得到n個(gè)疑似髓心，因此還需對(duì)得到的結(jié)果進(jìn)行聚類，取其聚類中心作為自動(dòng)定位的髓心。因需要計(jì)算的數(shù)量較少，減小孤立數(shù)據(jù)點(diǎn)對(duì)結(jié)果的影響，本文采用K-medoids聚類求解髓心。

已檢測(cè)到的n個(gè)疑似髓心多集中分布于一個(gè)近似圓形的范圍內(nèi)，因此對(duì)傳統(tǒng)K-medoids算法進(jìn)行改進(jìn)，計(jì)算已有的n個(gè)疑似髓心在x和y方向的均值（x，），加入疑似髓心數(shù)據(jù)集，并作為初始聚類中心O，。分析所有可能的對(duì)象對(duì)，每對(duì)中的一個(gè)對(duì)象看作是代表對(duì)象O，而另一個(gè)是非代表對(duì)象O，。對(duì)于每對(duì)代表對(duì)象與非代表對(duì)象，計(jì)算聚類結(jié)果。對(duì)象O;被那個(gè)可以使誤差值減少最多的對(duì)象O，所取代，最終集合中的代表對(duì)象O;便是年輪的髓心。上文中疑似髓心的聚類中心的坐標(biāo)為（603，394）。通過(guò)人工測(cè)定，該年輪實(shí)際髓心的坐標(biāo)為（603，392），與檢測(cè)結(jié)果相差2px，檢測(cè)年輪的平均半徑為302.5px，檢測(cè)偏差占平均半徑的0.66%，可見(jiàn)誤差較小。

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

為驗(yàn)證年輪髓心定位算法的有效性，選取不同樹(shù)種在不同環(huán)境下的年輪圖片進(jìn)行髓心檢測(cè)。圖4給出了4幅具有代表性的年輪隨心測(cè)量結(jié)果，第一列為小紅松年輪圖片，第二三列為落葉松年輪圖片，第四列為小紅橡年輪圖片。第一行為年輪原圖，第二行為年輪髓心檢測(cè)結(jié)果（藍(lán)線表示檢測(cè)到的圓環(huán)，綠點(diǎn)表示檢測(cè)到的疑似髓心，黃點(diǎn)表示人工定位的髓心，紅點(diǎn)表示最終聚類結(jié)果）。由實(shí)驗(yàn)結(jié)果可知，對(duì)于第一列，因其年輪清晰，噪聲較少，年輪輪廓線接近正圓，可較為精準(zhǔn)的定位，人工定位的髓心與檢測(cè)到的髓心相重合。對(duì)于第二列，雖然其橫截面不平整，心材部分早材晚材顏色較為相近，但輪廓線清晰且接近正圓，也可較好的檢測(cè)年輪髓心，檢測(cè)結(jié)果與人工識(shí)別結(jié)果一致。但當(dāng)年輪橫截面上有疤痕時(shí)，會(huì)使年輪形狀發(fā)生扭曲變形，例如第三列，此種情況不利于髓心檢測(cè)，可通過(guò)調(diào)整檢測(cè)半徑避開(kāi)疤痕影響的范圍進(jìn)行檢測(cè)，結(jié)果雖略有偏差但基本重合。對(duì)于第四列，因樹(shù)木生長(zhǎng)環(huán)境的差異導(dǎo)致年輪存在偏心現(xiàn)象，同時(shí)年輪心材部分早材顏色較深，圖像處理提取年輪輪廓線時(shí)會(huì)有一定難度，但年輪髓心定位偏差較小。同時(shí)經(jīng)檢測(cè)，若輪盤因干裂年輪線存在斷裂，本算法仍可較為準(zhǔn)確定位髓心。

為進(jìn)一步檢驗(yàn)算法定位年輪髓心的準(zhǔn)確度，對(duì)定位髓心的偏差進(jìn)行定量分析。選取50張年輪圖片，測(cè)量年輪在東、南、西、北四個(gè)方向的年輪半徑，取其平均值記為r;測(cè)量人工定位年輪與本文算法定位年輪的偏差計(jì)算偏差

由表1可見(jiàn)測(cè)量偏差在1%以內(nèi)占比為90%，但若年輪圖片噪聲較大或年輪線扭曲變形較大則易造成測(cè)量誤差。

4結(jié)論

結(jié)合年輪自身特征，本文提出一種基于梯度Hough變換和K-medoids算法的年輪髓心定位算法。為提高髓心定位的準(zhǔn)確性，首先應(yīng)對(duì)年輪圖片進(jìn)行預(yù)處理，將彩色圖片灰度化，使用雙邊濾波器進(jìn)行濾波降噪，利用自適應(yīng)閾值分割算法進(jìn)行圖像分割。然后利用Sobel算子提取邊緣，利用基于梯度變換的Hough變換，計(jì)算得到若干疑似圓心。最后利用K-medoids算法對(duì)疑似圓心進(jìn)行聚類，得到最終結(jié)果。通過(guò)對(duì)不同樹(shù)種，不同明暗，及存在偏心、裂紋、疤痕等特殊情況的年輪進(jìn)行檢測(cè)，測(cè)量結(jié)果與人工標(biāo)記髓心有較高的重合度，由此可見(jiàn)本算法具有一定的實(shí)用性。

參考文獻(xiàn)

[1]陳佶。圖像處理技術(shù)與統(tǒng)計(jì)學(xué)方法在自動(dòng)化年輪分析系統(tǒng)中的應(yīng)用[D].西安電子科技大學(xué)，2013.

[2]王燕鳳。樹(shù)木年輪圖像的邊緣檢測(cè)與樹(shù)齡測(cè)量方法研究[D].浙江農(nóng)林大學(xué)，2017.

[3]趙娟娟，郭志成，蘇芳，趙亞明?；跀?shù)字圖像法樹(shù)木年輪寬度測(cè)量方法研究[J].工業(yè)儀表與自動(dòng)化裝置，2017（06）：75-77+96.

[4]Hough V， PaulC. Methods and Means for Recognizing Complex Patterns.US： Patent 3069654， 1962.

[5]Duda R 0， Hart P E.Use of the Houghtransformation to detect lines andcurves in pictures [J]. Communicationsof the ACM， 1972， 15（01）： 11-15.

[6]尚璐，李銳，宋信玉，改進(jìn)的Hough變換圓檢測(cè)算法[J].電子設(shè)計(jì)工程，2011，19（14）：168-171.

[7]焦圣喜，肖德軍，闞一凡，霍夫變換算法在圓心視覺(jué)定位中的應(yīng)用研究[J].科學(xué)技術(shù)與工程，2013，13（14）：4089-4093.

[8]段黎明，汪威，張霞，改進(jìn)的Hough變換實(shí)現(xiàn)圓檢測(cè)[J].計(jì)算機(jī)集成制造系統(tǒng)，2013，19（09）：2148-2152.

[9]屈漢章，王洋，吳成茂。基于直徑累積的霍夫變換檢測(cè)圓算法[J].西安郵電大學(xué)學(xué)報(bào)，2017，22（05）：89-93.

[10]楊東平?；谔荻雀倪M(jìn)Hough變換的油菜籽圖像分割方法[J].糧油食品科技，2016，24（04）：80-82.

[11]吳慶崗，張衛(wèi)國(guó)，?；模鸨ＨA，劉朝霞，基于梯度Hough變換的遮擋蘋果目標(biāo)定位[J].浙江農(nóng)業(yè)學(xué)報(bào)，2017，29（06）：1009-1016.

[12]陳柯宇，曹曉光，改進(jìn)的基于梯度場(chǎng)Hough變換機(jī)場(chǎng)道面地?zé)魴z測(cè)算法研究[J].電子設(shè)計(jì)工程，2015，23（05）：112-115+119.

[13]余冬華，郭茂祖，劉揚(yáng)，任世軍，劉曉燕，劉國(guó)軍.基于距離不等式的K-medoids聚類算法[J].軟件學(xué)報(bào)，2017，28（12）：3115-3128.

[14]馬菁，謝娟英.基于粒計(jì)算的K-medoids聚類算法[J].計(jì)算機(jī)應(yīng)用，2012（07）：1973-1977.

[15]張雪萍，龔康莉，趙廣才，基于MapReduce的K一Medoids并行算法[J].計(jì)算機(jī)應(yīng)用，2013（04）：1023-1025+1035.

[16]韓嘯;劉淑芬;徐天琦?；谶z傳模擬退火算法的改進(jìn)K-medoids算法[J].吉林大學(xué)學(xué)報(bào)（工學(xué)報(bào)），2015，45（02）：619-623.

[17]瞿鈞，甘嵐，梯度Hough變換在圓檢測(cè)中的應(yīng)用[J].華東交通大學(xué)學(xué)報(bào)，2007（01）：101-104.

[18]吳文亮。聚類分析中K-均值與K-中心點(diǎn)算法的研究[D].華南理工大學(xué)，2011.