基于梯度 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.