16736-DBSCAN和K-Means混合聚类的牙齿特征自动识别

第2*卷第*期计算机辅助设计与图形学学报Vol.2*No.*201*年*月JournalofComputer-AidedDesign&ComputerGraphics***.201*收稿日期:20**-**-**;修回日期:20**-**-**.基金项目:国家自然科学基金(61472354,61672452);NSFC-广东省人民政府大数据科学研究中心项目(U1611263);褚玉伟(1993—),男,硕士研究生,主要研究方向为网格处理、医学图像处理;罗晓博(1994—),女,硕士研究生,主要研究方向为医学图像处理、数据可视化;屈珂(1994—),女,硕士研究生,主要研究方向为网格处理、医学图像处理;陶煜波(1980—),男,博士,副教授,硕士生导师,CCF,主要研究方向为数据可视化、可视分析、医学图像处理；林军(1967—),女,博士,副主任医师,硕士生导师,主要研究方向为口腔生物材料的生物相容性和口腔正畸方向；林海(1965—),男,博士,教授,博士生导师,论文通讯作者,主要研究方向为数据可视化、可视分析、医学图像处理.DBSCAN和K-Means混合聚类的牙齿特征自动识别褚玉伟1),罗晓博1),屈珂1),陶煜波1),林军2),林海1)*1)(浙江大学CAD&CG国家重点实验室杭州310058)2)(浙江大学附属第一医院正畸科杭州310006)([e-mail])摘要:根据牙齿网格数据表面的特点,提出一种密度聚类(Density-BasedSpatialClusteringofApplicationswithNoise,DBSCAN)和K-Means混合聚类的牙齿特征自动识别算法.首先利用平均曲率和高度值对数据进行预处理,加大区域间的距离;将牙齿点中高度值高的点投影到XOY平面做DBSCAN聚类,获取簇数和中心点作为下一步的输入;再使用K-Means算法对预处理的模型处理,用于牙齿区域的划分;最后基于每个划分区域,对特征点进行识别.实验结果表明,该算法能够精确地检测出牙齿的特征点,相比已有识别算法,操作简单,正确率高.关键词:特征识别;平均曲率;网格分割;DBSCAN;K-Means算法中图法分类号:TP391.41DBSCANandK-MeansHybridClusteringbasedAutomaticDentalFeatureDetec-tionChuYuwei1),LuoXiaobo1),QuKe1),TaoYubo1),LinJun2),andLinHai1)*1)(StateKeyLaboratoryofCAD&CG,ZhejiangUniversity,Hangzhou310058)2)(DepartmentofOrthodontics,theFirstAffiliatedHospital,ZhejiangUniversity,Hangzhou310006)Abstract:Accordingtothecharacteristicsofdentalmeshes,thispaperproposedanautomaticdentalfeaturedetectionalgorithmbasedonDBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)andK-Meanshybridclustering.First,averagecurvaturesandgeodesicdistanceswereusedtobetterrepresentthedistancesbetweenpartition.Second,DBSCANwasappliedtoprojectivepointswhichhavelargerZvaluesinordertoobtainthenumberofclustersandcenterpointsastheinputofnextstep.Next,weusedK-Meansalgorithmtogeneratepartitionsofthedentalmesh.Finally,thefeaturedetectionalgorithmwasemployedtoobtainfeaturepointsoneachpartition.Experimentsshowthatthisalgorithmcanaccuratelydetectdentalfeatures.Comparedtothepreviousautomaticalgorithm,theaccuracyissignificantlyimprovedandtheop-erationsarealsosimplified.Keywords:featuredetection;meancurvature;meshsegment;DBSCAN;K-Meansalgorithm自动识别牙齿的特征点,根据特征点计算相关特征值,对于临床正畸手术具有重要的价值,为牙2计算机辅助设计与图形学学报第2*卷齿正畸系统的加速配准、效果评估提供了可能.1相关工作近年来,技术性的进步使得治疗计划可以虚拟的(3d)模拟治疗方案并允许医生选择多种方案治疗[1].范然在2013年提出一整套计算机辅助牙齿隐形正畸系统[2],借助这个系统,可以完成隐形正畸矫治,隐形正畸矫治具有定位精准、美观、舒适、清洁等优点.在牙齿隐形正畸系统中,牙齿的特征点识别是非常重要的一块,隐形正畸系统需要许多牙齿表面的特征,原因在于这些特征可以提供一组定量数据判定牙齿是否对齐等标准(例如可以使用相邻边缘脊之间的高度差异定义牙齿是否对齐)[3].并且可以使用这些特征点来监视矫正的进度,为最佳的对准提供了用于评估的手段,同时由特征点经过计算可以获得系统所需要的其他特征值(比如通过特征点可以计算获得咬合面,这对于隐形正畸系统具有非常重要的意义).同时特征点存在可以加速匹配算法.隐形正畸系统的数据是患者的牙齿网格模型,如图1显示牙齿网格数据的结构图.在隐形正畸系统中,特征点的自动识别挑战在于,由于性别年龄等不同,牙齿的模型也是不同的,对这些不同的模型,算法是鲁棒的.尖点是特征点主要识别的点,尖点位于前磨牙和后磨牙上,如图1所示,每套牙齿一般有四个后磨牙和四个前磨牙,分别位于两侧,本文将靠近中间的牙齿标定为1号,远离中心的牙齿标定为2号.这些牙齿的表面有如同山峰一样的结构,尖点位于峰顶,图中红色的点表示尖点的位置.这些尖点可用于定义咬合面.一般来说前磨牙有两个尖点,后磨牙有四到五个尖点,有的可能会更多[3].Mokhtari等在1994年提出了一种基于牙印的特征点自动识别算法[5],通过对牙齿石膏模型进行漫射介质的差分吸收,获得牙齿模型的具有深度信息的牙印灰度图像,然后对灰度图像进行去除噪声点的处理,通过图像处理算法中的分水岭算法发现局部最低点作为二维图像的尖点,再对灰度图像进行重构,将灰度图像映射到三维模型,发现三维牙齿模型中对应的尖点,即可找到三维牙齿特征点.该算法率先实现了特征点的自动识别,但是算法需要通过硬件(需要灯光、照相机、染色剂和染色容器)设备将三维牙齿模型转换成二维灰度图像,过程比较复杂,并且转换过程会产生噪声,影响识别精度.2号后磨牙1号前磨牙2号前磨牙1号后磨牙图1牙齿结构图Mangan[6]在1999提出一种通过分水岭来对网格模型进行划分,这种方法可以很简单发现不同区域的局部点,Mangan提出了利用曲率作为高度函数.Kumar等利用Mangan提出的分水岭算法，在2013年提出了一种直接对牙齿三维模型使用分水岭算法进行特征识别的方法[1],其本质是利用高度函数发现汇水盆地,在汇水盆地中发现特征点,该算法改进了Mangan的高度函数，提出一种新的高度函数,充分利网格上每一个点的曲率和Z值两个参数,选取适当的参数,达到自动识别的目的.但是这种方法对噪声比较敏感,并且分水岭算法容易出现过划分和少划分的情况,造成特征点识别数目过多或者过少的现象.由于上述已有的特征自动识别算法存在着操作复杂、识别不准确和鲁棒性不强的不足等缺点,因此,本文提出了一种基于密度聚类(Density-BasedSpatialClusteringofApplicationswithNoise,DBSCAN)和K-Means混合聚类的特征自动识别方法对牙齿的尖点进行自动识别.本文算法流程图如图2所示,首先,对图像进行预处理操作,根据包围盒来确定局部坐标系(物坐标),从全局坐标转换局部坐标下;然后计算每个点平均曲率,然后更新Z轴的值获取新的位置.进行DBSCAN聚类,取Z值比较大的一部分点做投影和聚类,通过DBSCAN聚类方法得到簇的数目(特征点数目)和每个簇的中心点.然后将中心点作为K-Means的起始点,利用K-Means算法获得牙齿各个分割结果,最后在各个分割结果中找到最值点即可作为特征点.第*期褚玉伟,等:DBSCAN和K-Means混合聚类的牙齿特征自动识别3预处理DBSCANK-Means自动定轴平均曲率计算Z值替换剔除低值点映射DBSCAN聚类待处理模型结果图人工标定精度计算坐标转换中心点映射K-Means聚类特征点识别簇数及中心点图2特征自动识别架构图.2基于K-Means的特征点自动提取算法本文提出的基于DBSCAN和K-Means混合聚类的牙齿特征自动识别算法首先基于分水岭算法中的高度函数对网格数据进行处理,使牙齿的不同区域之间距离更大,区域之间的数据点的Z变小.然后使用DBSCAN聚类获得簇的数目和每个簇的中心点.K-Means算法[6]对数据进行分割,可以将每颗牙齿分成多块区域,最后找到每块区域的最值点作为特征点,实现了牙齿的特征点自动识别.本文算法相比之前的算法优点在于:时间复杂度比较低;操作简单;充分利用了曲率和高度值等信息;对于噪声比较鲁棒;对于所有的牙齿(牙齿表面比较复杂的数据)都有很好的识别效果.2.1基于高度函数的数据预处理算法初始牙齿网格数据往往存在着各种各样的噪声,同时牙齿的各个待分割区域比较接近,为了排除噪声的干扰,同时使得牙齿各个待分割区域之间比较分离,便于后期算法的效果,需要对原始模型进行预处理.首先,自动定轴,这是下一步坐标转换的输入值.通过获得牙齿模型的轴对齐包围盒可以近似的描述牙齿,可以将包围盒的中点作为局部坐标的原点,三条坐标轴分别平行与三个面.为了尽可能近似的描述牙齿,本文采用方向包围盒[8],方向包围盒与AABB[9]相比,拟合程度比较高,剔除效果好[10].图3表示某颗牙齿的包围盒,以及根据包围获得的局部坐标系,局部坐标原点位于包围盒中心,其中红色表示局部坐标的Z轴,绿色表示局部坐标的X轴,蓝色表示局部坐标的Y轴.图3某颗牙齿包围盒然后,坐标转换.为了在计算高度值的时候能够直接使用Z的值作为高度值,首先需要将网格模型从全局坐标转换到局部坐标下,这样可以减少很多计算量.牙齿网格数据由一系列的点(,,)iPxyz组成,根据文献[11]提出的转换公式,通过变换矩阵T可以将全局坐标的点ip转换到局部坐标系下的对应点(,,)''''ipxyz.通过以上变换可以将数据从世界坐标变换到局部坐标系.为了识别算法准确性更高,通过一定的预处理使数据集合之间距离更大,从图4可以发现数据集合之间的距离越大,划分效果越好.4计算机辅助设计与图形学学报第2*卷a.区域之间紧凑b.区域之间远离图4分割区域之间的位置关系图如果直接利用位置关系进行K-Means划分,发现有些牙齿的区域之间比较接近,如图5,容易造成不理想的划分,但是曲率可以使得数据之间特征更加明显.AB图5分割区域之间区分不明显模型文献[12]提出了平均曲率、高斯曲率、均方根(rootmeansquare,RMS)曲率和绝对(absolute,ABS)曲率.使用文献[12]中的曲率计算方式计算各种曲率,并且绘制热力图,如图6分别是根据四种曲率值绘制的热力图.从图中发现,平均曲率可以作为数据之间特征更加明显,各个区域之间的平均曲率相差比较大,