(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210524204.X (22)申请日 2022.05.14 (71)申请人 上海贝特威自动化科技有限公司 地址 201109 上海市嘉定区马陆镇横仓公 路2465号2幢301室 (72)发明人 肖振　陈红光　卢兴中　 (74)专利代理 机构 上海互顺专利代理事务所 (普通合伙) 31332 专利代理师 韦志刚　曹月明 (51)Int.Cl. G06V 10/762(2022.01) G06V 10/44(2022.01) G06F 7/24(2006.01) (54)发明名称 一种基于聚类的二维坐标行列排序方法及 装置 (57)摘要 本发明属于图像处理及机器视觉技术领域， 且公开了一种基于聚类的二维坐标行列排序方 法， 包括如下步骤： S1、 获取待排序的所有工件的 二维坐标； S2、 利用聚类的方法， 把属于同一列、 且紧密连接的二维坐标归为一类； S3、 分析类与 类之间的相对位置关系， 把属于同一列的类进行 合并； S4、 把S2中未能聚类的孤 立点， 根据其与其 它类之间的位置关系， 将其归为某一类。 本发明 提供了一种基于聚类的二维坐标行列排序方法 及装置， 能够实现如下效果： 将相对复杂的二维 坐标行列排序转化为两次简单的一维排序， 简化 了处理过程， 提高了生产效率； 能够对各种各样 排列不整齐、 分布不规则的工件进行正确的排 序， 而且不需要人工 干预、 易于操作、 效果可靠 。 权利要求书2页 说明书5页 附图5页 CN 114972828 A 2022.08.30 CN 114972828 A 1.一种基于聚类的二维坐标 行列排序方法， 其特 征在于， 包括如下步骤： S1、 获取待排序的所有工件的二维坐标； S2、 利用聚类的方法， 把属于同一列、 且紧密连接的二维坐标归为 一类； S3、 分析类与类之间的相对位置关系， 把属于同一列的类进行合并； S4、 把S2中未能 聚类的孤立 点， 根据其与其它类之间的位置关系， 将其归为某一类； S5、 把属于同一类的数据按照纵坐标进行一维排序； S6、 把所有的类按照横坐标进行一维排序。 2.根据权利要求1所述的一种基于聚类的二维坐标行列排序 方法， 其特征在于： 步骤S2 所述的聚类的方法是指基于密度的聚类方法。 3.根据权利要求2所述的一种基于聚类的二维坐标行列排序 方法， 其特征在于： 步骤S2 所述的聚类的方法， 采用的距离度量方式为： 假设两个二维坐标点P1(X1,Y1)和P2(X2,Y2)， 则二者的距离Distance＝X+Y， 其中， X＝∣ X1 –X2∣， 如果∣ Y1–Y2∣ 小于Th， 则Y＝0； 如果∣ Y1–Y2∣ 大于等于Th， 则Y＝∣ Y1 –Y2∣‑Th， 其中Th是一常量， 可以通过统计若干个数 据的平均值自动获得， 数据即指上 下相邻的两个二维坐标的纵向距离 。 4.根据权利要求1所述的一种基于聚类的二维坐标行列排序 方法， 其特征在于： 步骤S3 包括以下两种情况： S3.1、 如果类m和类n可以合并， 需要同时满足如下 条件： S3.11、 类m和类n的横向距离较小； S3.12、 类m中所有数据纵坐标的最小值大于类n中所有数据纵坐标的最大值， 或者， 类m 中所有数据纵坐标的最大值小于类n中所有数据纵坐标的最小值； S3.13、 类m位于类n的延长线上或者类n 位于类m的延长线上； S3.2、 如果类m和类n可以合并， 需要同时满足如下 条件： S3.21、 类m和类n的横向距离较小； S3.22、 类m中所有数据纵坐标的最小值大于类n中所有数据纵坐标的最大值， 或者， 类m 中所有数据纵坐标的最大值小于类n中所有数据纵坐标的最小值； S3.23、 存在类k、 且类m与类k的横向距离与类n与类k的横向距离 接近。 5.根据权利要求1所述的一种基于聚类的二维坐标行列排序 方法， 其特征在于： 步骤S4 包括以下步骤： S4.1、 遍历 S2中所有未能 聚类的孤立 点； S4.2、 如果孤立 点q可以归为类n， 需要满足如下 条件： S4.21、 点q和类n的横向距离较小； S4.22、 查找类n中距离点q最近的两个点 为p1、 p2， 点q到p1、 p2形成直线的距离较小。 6.根据权利要求1所述的一种基于聚类的二维坐标行列排序 方法， 其特征在于： 步骤S5 包括： 把属于同一类的数据按照纵坐标的升序或降序进行排列。 7.根据权利要求1所述的一种基于聚类的二维坐标行列排序 方法， 其特征在于： 步骤S6 包括： 求出每一类中所有数据横坐标的平均值， 然后按照这些平均值的升序或降序进行排 列。权　利　要　求　书 1/2 页 2 CN 114972828 A 28.一种基于聚类的二维坐标行列排序装置， 其特征在于： 包括二维坐标获取模块、 聚类 模块、 类类合并模块、 点类合并模块、 一维排序模块； 其中， 所述的二维坐标获取模块用于获取每 个工件的二维坐标点； 所述的聚类模块用于在所获得的坐标点中， 利用基于密度的聚类； 所述的类 类合并模块用于合并属于同一列的类； 所述的点类合并模块用于将孤立 点归为某一类； 所述的一维排序模块用于对类内数据按照纵坐标排序、 类间数据按照横坐标排序。权　利　要　求　书 2/2 页 3 CN 114972828 A 3