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

薛怡寧　何明栩　徐川晴　劉潤萌

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

[關鍵詞]髓心定位 變換 K-medoids 聚類梯度Hough

木材髓心由一年生幼莖的初生木質部構成，位于木材中間，由于其位置的特殊性而被選為測量年輪參數的常用點。現今流行的年輪分析系統，如WinDENDRO等，通過定位年輪髓心，可進行年輪相關參數的檢測。例如，根據確定的髓心生成直線，通過記錄過中心的直線與年輪總體相交的次數得到年輪數目;通過計算同一;直線上相鄰灰度值為0的像素之，間的距離來確定年輪寬度。年輪髓心的定位既可通過人為手動指定，也可通過系統算法自動定位。但由于手動指定常常存在主觀性與測量誤差，年輪參數的測量會受到很大程度的影響。

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

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

1相關技術介紹

1.1基于圓檢測的Hough變換

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

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

綜合年輪的特性，本文選用梯度Hough變換作為本文算法的基礎。梯度Hough變換可理解為是一種基于梯度信息的改進的Hough變換算法，其應用也十分廣泛：利用梯度Hough算法進行油菜籽圖像的分割、使用基于梯度Hough變換的目標定位算法來定位自然環境中被遮擋的蘋果、以及識別和檢測機場道面地燈等。

1.2K-medoids聚類

K-medoids算法是一種經典的基于劃分的聚類算法，因強魯棒性、對噪聲數據及異常點處理能力強等優勢被廣泛應用，可認為是在另一經典算法K-Means的基礎上進行改進。K-Means算法選擇每個類簇所有樣本的均值作為聚類中心。與K-Means相比，K-medoids算法則以類簇的中位數為聚類中心，解決了K-Means易于陷入局部最優的缺陷，同時也排除孤立點帶來的負面影響。

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

2年輪髓心定位

2.1整體流程

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

（1）轉化彩色圖像為灰度圖像;

（2）使用雙邊濾波器進行濾波降噪;

（3）利用自適應閾值分割算法進行圖像分割以提取年輪輪廓。

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

2.2年輪圖像預處理

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

2.3梯度Hough變換髓心檢測

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

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

（2）因樹木生長環境的不同，會存在偏

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

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

圓心檢測結果如圖3所示，其中綠色的點表示檢測到的圓心，藍色的圓環表示圓心所在的圓環。因年輪形狀的不規則，檢測到的為近似結果。

2.4K-medoids聚類定位髓心

因上文是對半徑r在一個特定范圍內的圓進行圓心定位，會得到n個疑似髓心，因此還需對得到的結果進行聚類，取其聚類中心作為自動定位的髓心。因需要計算的數量較少，減小孤立數據點對結果的影響，本文采用K-medoids聚類求解髓心。

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

3實驗結果

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

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

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

4結論

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

參考文獻

[1]陳佶。圖像處理技術與統計學方法在自動化年輪分析系統中的應用[D].西安電子科技大學，2013.

[2]王燕鳳。樹木年輪圖像的邊緣檢測與樹齡測量方法研究[D].浙江農林大學，2017.

[3]趙娟娟，郭志成，蘇芳，趙亞明。基于數字圖像法樹木年輪寬度測量方法研究[J].工業儀表與自動化裝置，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]尚璐，李銳，宋信玉，改進的Hough變換圓檢測算法[J].電子設計工程，2011，19（14）：168-171.

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

[8]段黎明，汪威，張霞，改進的Hough變換實現圓檢測[J].計算機集成制造系統，2013，19（09）：2148-2152.

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

[10]楊東平。基于梯度改進Hough變換的油菜籽圖像分割方法[J].糧油食品科技，2016，24（04）：80-82.

[11]吳慶崗，張衛國，常化文，金保華，劉朝霞，基于梯度Hough變換的遮擋蘋果目標定位[J].浙江農業學報，2017，29（06）：1009-1016.

[12]陳柯宇，曹曉光，改進的基于梯度場Hough變換機場道面地燈檢測算法研究[J].電子設計工程，2015，23（05）：112-115+119.

[13]余冬華，郭茂祖，劉揚，任世軍，劉曉燕，劉國軍.基于距離不等式的K-medoids聚類算法[J].軟件學報，2017，28（12）：3115-3128.

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

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

[16]韓嘯;劉淑芬;徐天琦。基于遺傳模擬退火算法的改進K-medoids算法[J].吉林大學學報（工學報），2015，45（02）：619-623.

[17]瞿鈞，甘嵐，梯度Hough變換在圓檢測中的應用[J].華東交通大學學報，2007（01）：101-104.

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