(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210749976.3 (22)申请日 2022.06.29 (71)申请人 中国测绘科 学研究院 地址 100036 北京市海淀区莲 花池西路28 号 (72)发明人 陈颂　赵习枝　刘晓东　张福浩　 仇阿根　李栋　鲍帅　郑佳荣　 (74)专利代理 机构 北京睿派知识产权代理事务 所(普通合伙) 11597 专利代理师 刘锋 (51)Int.Cl. G06V 20/13(2022.01) G06V 20/10(2022.01) G06V 10/762(2022.01) G06V 10/80(2022.01) (54)发明名称 一种基于CFSFDP改进算法的地图图斑聚类 融合处理方法 (57)摘要 一种基于CFSFDP改进算法的地图图斑聚类 融合处理方法， 利用CFSFDP算法的基本思路， 将 密度计算方法改进为图斑聚集程度计算， 通过各 图斑之间的距离获得密集聚集程度值与图斑关 系， 结合聚类中心或距离方案对n叉树进行剪枝， 生成聚类结果， 以此辨别图斑的分布与归属。 本 发明对CFSFDP算法进行了部分改进， 保有原算法 的优点， 还简化了算法的数据组织结构， 将图斑 密度计算替换为图斑聚集程度计算， 使之适应图 斑聚类处理， 并采取划定距离阈值或聚类中心方 案对n叉树进行剪枝， 可调节的得到聚类结果， 减 少原有数据定量分析的工作量， 可用于对建筑、 农田等具有明显聚集特征的地图图斑的聚类， 进 一步完善对此类信息的处 理。 权利要求书3页 说明书9页 附图3页 CN 115205699 A 2022.10.18 CN 115205699 A 1.一种基于 CFSFDP改进算法的图斑聚类融合处 理方法， 其特 征在于， 包括如下步骤： 图斑距离矩阵计算 步骤S110： 基于已有的遥感影像解译结果， 获取需要处理的海量地类图斑， 基于地图图斑的形状 与分布， 计算各图斑间的距离， 对所有图斑进行两 两计算， 生成地图 图斑距离矩阵； 地图图斑聚集度计算 步骤S120： 基于地图图斑距离矩阵， 各图斑选取k个最邻 近图斑， 计算反距离平均值作为图斑聚集 度值， 其中k个数由用户依据最小图斑聚类 个数设定； 构建地图 图斑归属n叉树S140： 依据地图图斑聚集度值的计算结果， 对各个图斑 𝑖建立归属关系 ， 各图斑𝑖只对比自 身聚集值大的图斑 𝑗进行距离计算， 即 ， 在获得与所有符合条件的图斑的计算距 离， 取其中的最小值 的 𝑗作为𝑖保留的 归属关系， 记为 ， 针对聚集度值最大 的图斑𝑖,采用其余所有图斑的最小连接距离值中的最大值 来代表自身 上级要素的距离值， 自身作为上级连接图斑 ， 通过上述处理， 从而生成基于图斑距离生 成的n叉树； n叉树剪枝聚类步骤S15 0： 将地图图斑要素关系结构n叉树进行梳理， 识别分析树枝关系与关键分支点， 依据聚类 需求， 选择聚类剪枝 方案， 在n叉树上， 根据相应剪枝 方案剪掉相应的树枝 联系， 生成多个要 素集， 并统一编号处 理。 2.根据权利要求1所述的图斑聚类融合处 理方法， 其特 征在于： 在步骤S120和S140之间还 包括地图图斑聚集度排序步骤S13 0： 在已有的地图图斑聚集度数值的基础上， 对地图图斑聚集度数值进行排序， 获得各要 素的重要性 排名， 为构建地图 图斑归属n叉树 提供数值依据。 3.根据权利要求1所述的图斑聚类融合处 理方法， 其特 征在于： 构建地图 图斑归属n叉树S140具体为： 1） 单向遍历地图 图斑： 根据地图图斑 𝑖的图斑聚集程度 大小， 自大到小获取地图图斑 𝑖所需计算 的地图图 斑  𝑗的存储ID； 2） 与上级图斑建立连接： 依据图斑聚集程度进行上级图斑的连接， 即在序列中的要素 𝑖向密度较高的要素  𝑗建 立连接， 由此从所有密度较高的要素中选取距离自身最近的图斑， 建立依附关系， 其中，𝑖是图斑的ID， 只有当 ， 即图斑 𝑗聚集度比图斑 𝑖大， 获取图斑 𝑖距离最小 的图斑 𝑗并保留图斑j的ID与 距离 ,作为图斑 𝑖字段“上级要素”与“上级距离 ”的属性； 若 𝑖 为聚集度值最大时， 即 ，“上级要素 ”属性设为自身ID， 距离采用后续其他 中的权　利　要　求　书 1/3 页 2 CN 115205699 A 2最大值； 3） n叉树结构生成： 根据各图斑计算所得到的 “上级要素 ”与“上级距离 ”获取要素的关系， 生成的带有上级 要素信息的序列表， 形成n叉树结构的图斑要素关系。 4.根据权利要求1所述的图斑聚类融合处 理方法， 其特 征在于： 图斑距离矩阵计算 步骤S110中， 采用多边形中心 距离或边界最近距离度量进行距离计算， 具体为： （1） 多边形中心距离： 采用地图图斑的几何中心作为距离计算的依据， 计算各图斑之间 中心的距离， 得到最后结果； （2） 边界最近距离： 最短距离是采用图斑外边界计算相互之间的距离， 根据边界的关键 点或边进行检索解 算， 发现最短的距离， 当多边形 出现叠置与接触时， 最近距离为0 。 5.根据权利要求1所述的图斑聚类融合处 理方法， 其特 征在于： 在地图图斑聚集度计算 步骤S120中， 所述计算反距离平均值作为图斑聚集度值具体包括： 1)获取k个最邻近图斑： 首先对地图图斑建立空间索引， 减小邻近要素的搜索范围， 在当前选中要素的搜索范 围内获取需参与计算的潜在邻近图斑要素， 并从中计算得出k个最邻近图斑， 建立连接关 系； 2） 聚集程度反距离加权计算： 基于地图图斑距离矩阵， 获取每个要素 𝑖的k个邻近图斑距离 ,其中𝑖为当前计算要素 ID, t 为k个邻近图斑的ID,利用 的反距离加权来实现图斑聚集 程度 的计算； 其中k取值 为3‑10。 6.根据权利要求3所述的图斑聚类融合处 理方法， 其特 征在于： 利用公式 （1） 进行图斑聚集 程度 的计算：         公式 （1） 其中， 代表图斑聚集 程度值， 𝑘为k个邻近图斑总数。 7.根据权利要求3所述的图斑聚类融合处 理方法， 其特 征在于： 在进行图斑聚集 程度 的计算时， 加入图斑面积 进行二次计算， 具体参见公式 （2） ， 其中， 为邻近图斑的面积， 为权值， 𝑘为k个邻近图斑总数。 8.根据权利要求2所述的图斑聚类融合处 理方法， 其特 征在于： n叉树剪枝聚类步骤S15 0中， 所选择的聚类剪枝方案， 采取以下两个方案; (1)依据中心图斑进行剪枝聚类： 将各图斑的上级距离与聚集度值生成二维点图， 并找 出上级距离与聚集度值乘积最大的x个点， x为用户输入的最终类别个数， 采用线性二维划权　利　要　求　书 2/3 页 3 CN 115205699 A 3