(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210247307.6 (22)申请日 2022.03.14 (71)申请人 北京信息科技大 学 地址 100088 北京市西城区北三环中路甲 29号华龙大厦B座802室 (72)发明人 胡宇　孟臻　 (74)专利代理 机构 哈尔滨市阳光惠远知识产权 代理有限公司 2321 1 专利代理师 孙莉莉 (51)Int.Cl. G06V 10/762(2022.01) G06V 10/74(2022.01) G06V 10/82(2022.01) G06K 9/62(2022.01) G06N 3/04(2006.01)G06T 5/00(2006.01) G06T 5/20(2006.01) G06T 7/13(2017.01) G06V 10/46(2022.01) (54)发明名称 一种基于小波形状描述子的聚类算法有效 性评价方法、 设备及 介质 (57)摘要 本发明提出一种基于小波形状描述子的聚 类算法有效性评价方法、 设备及介质， 该方法从 聚类簇中随机抽取或加入任意元素， 形成原始簇 与簇； 将原始簇与测试簇分别转化为二维图像； 检测原始簇与测试簇二维图像的轮廓边界； 计算 原始簇与测试簇二维图像的轮廓的小波形状描 述子， 得到轮廓上每个像素的特征向量； 分别计 算原始簇与测试簇二维图像的相似性； 构建聚类 算法有效性评价模型， 基于原始簇与测试簇二维 图像的相似性即可计算作为聚类算法有效性评 价模型的参数， 即可评价聚类算法的有效性。 该 方法适用于所有聚类算法的有效性评价， 使用前 不需要预了解聚类算法相关信息， 速度快、 准确 性高， 实现了聚类算法有效性的盲评估。 权利要求书4页 说明书16页 附图5页 CN 114677530 A 2022.06.28 CN 114677530 A 1.一种基于小波形状描述子的聚类算法有效性评价方法， 其特征在于， 所述方法具体 包括： 随机生成多个服从正态分布的数据构成数据集； 在构建的数据集上采用任一聚类算法进行聚类， 将聚类结果的任一簇作为原始簇， 添 加或移除任意个元 素作为测试簇； 采用德劳内三角函数将聚类簇中二维空间点映射 为二维映射图； 利用高斯滤波器及梯度函数， 检测原始簇与测试簇二维映射图的边缘轮廓， 利用小波 形状描述子分别计算 二者的边缘轮廓特 征； 采用图像相似度的方法计算原始簇与测试簇的二维映射图的边缘轮廓的形状相似度 实现聚类结果的质量评估， 即聚类算法的有效性评估。 2.根据权利要求1所述的方法， 其特征在于， 利用R语言 的rnorm()函数 随机生成10000 个服从正态分布的数据构成数据集。 3.根据权利要求2所述的方法， 其特征在于， 假设数据集被分为N个类， 分别记为原始簇 Ⅰ、 原始簇Ⅱ、……、 原始簇N； 从中随机挑选一个簇作为实验对象， 即原始簇 Ⅰ， 向其随机添加 或移除n个元 素， 生成测试簇 Ⅰ。 4.根据权利要求3所述的方法， 其特征在于， 所述原始簇 Ⅰ进行图形化过程， 所述图形化 过程是以原始簇 Ⅰ中任一点作为三角形的顶点， 将与它欧氏距离最近的两个点与其连接， 经 过N次迭代得到德劳内三角网络； 记录共用各点的三角形， 求出三角形的外接圆圆心， 再按 顺时针方向连接圆心即为该点对应的泰 森多边形。 5.根据权利要求4所述的方法， 其特征在于， 所述采用德劳内三角函数将聚类簇 中二维 空间点映射 为二维映射图， 具体为： 设(X,Y)＝{(x1,y1),(x2,y2),…,(xn,yn)}表示原 始簇Ⅰ上N个不重复的点组成的点 集P； ①将所述N个点以x坐标为主， 以y坐标为辅进行排序； ②构造过程： ⅰ如果N＝2， 则直接返回； ⅱ如果N＝3， 则连接三个点构成三角网， 返回； ⅲ将N个点平均或者按最近原则分成两份子点 集Pl和Pr； ⅳ分别构建点 集Pl和点集Pr的德劳内三角网络DT(Pl)与DT(Pr)； ⅴ合并DT(Pl)与DT(Pr)为DT(P)； ③合并过程： ⅰ对于给定的DT(Pl)与DT(Pr)， 计算点集Pl和Pr的凸包； ⅱ得到顶端切线 UCT与底端切线BCT， 两切线在最终合并的三角网中是 可见的； ⅲ从凸包的底端切线开始， 利用切线的左端点、 右端点以及它们的相邻点进行局部更 新以完成DT(Pl)与DT(Pr)， 直到遇到顶端切线 UCT为止。 6.根据权利要求5所述的方法， 其特征在于， 所述检测原始簇与测试簇二维映射图的边 缘轮廓， 具体为： 步骤(1)图像与高斯平 滑滤波器卷积： 采用大小为(2K+1) ×(2K+1)高斯滤波器核式对图像进行高斯滤波：权　利　要　求　书 1/4 页 2 CN 114677530 A 2其中， K为 正整数， Hij表示第i行第j列的像素值， σ 标准差； 若映射图像中一个3 ×3的窗口为A， 要滤波 的像素点为e， 则经过高斯滤波后， 像素点e 的亮度值e ′为： 其中*为卷积体符号， sum表示矩阵中所有元 素相加求和； 步骤(2)计算滤波后的原始 簇Ⅰ二维映射图的水平、 垂直和对角边缘， 返回水平Gx和垂直 方向Gy方向的一阶导数， 确定像素点的梯度强度G和方向梯度 θ； 已用高斯滤波器平滑的二维映射图记为 g(x,y)， 其梯度使用2 ×2一阶有限差分近似来 计算x和y偏导数的两个阵列fx'(x,y)与fy'(x,y)： f’x(x,y)≈Gx＝[f(x+1,y) ‑f(x,y)+f(x+1,y+1) ‑f(x,y+1)]/2    (3) f’y(x,y)≈Gy＝[f(x+1,y) ‑f(x,y)+f(x+1,y+1) ‑f(x,y+1)]/2    (4) 在2×2正方形内求有限差分的均值， 以便在图像中的同一点计算x和y的偏导数梯度； 梯度强度G和方向梯度 θ用直角坐标到极坐标转 化公式来计算： 步骤(3)对梯度幅值进行非极大值仰制： 利用梯度的方向将梯度角离散为圆周的四个 方向之一， 以便用3 ×3的窗口作为抑制运算； 四个扇区的标号为0～3， 对应3*3邻域的四种 可能组合； 在每一点上， 邻域的中心像素G(x,y)与沿着梯度线的两个像素相比， 如果G(x,y) 的梯度值小于沿梯度线的两个 像素梯度值， 则令G(x,y)＝0； 步骤(4)二维映射图轮廓边缘的检测与连接： 对非极大值抑制图像作用两个阈值th1和 th2， 且th1＝0.4th2； 把梯度值小于th1的像素的灰度值设为0， 得到图像1； 把梯度值小于 th2的像素的灰度值设为0， 得到图像2； 图像2以高阈值为基数得到， 在 去除噪声的同时也造 成了有用边缘信息的损失； 而图像1以低阈值为基数取得， 虽然噪音多， 但也保留了多的信 息； 因此， 采用图像1与图像2相结合的方法完成图像 轮廓边缘的连接； 所述采用图像1与图像2相结合的方法完成图像 轮廓边缘的连接， 具体为： 第一步： 当在图像2上遇到一个非零灰度的像素p(x,y)时， 按照一定方向跟踪以p(x,y) 为起点的轮廓线， 直到轮廓线的终点q(x,y)； 第二步： 找到图像1中与q(x,y)点位置相对应 的点s(x,y)的8邻近区域； 第三步： 如果在s(x,y)点的8邻近区域中有非零像素存在， 则将其 包括在图像2中， 记作r(x,y)点； 第四步： 从r(x,y)开始， 重复第一步， 直到在图像1与图像2权　利　要　求　书 2/4 页 3 CN 114677530 A 3