下的一个圆,在参数的三维空间中得到一个圆锥。最后找出参数空间中的峰值点,即得到待识别的圆的圆心和半径。由于霍夫变换具有良好的抗噪声性能和对部分遮盖的不敏感等特性,又不受图像旋转的影响,在很多领域都有广泛的应用,有关霍夫变换的研究和改进也很多。例如广义霍夫变换、随机霍夫变换、快速霍夫变换等等,就是针对直线的霍夫变换也有很多改进算法。由于时间的原因,在本软件中,只是使用了标准的霍夫变换算法。简单几何图形的识别和编辑- 10- 2. 基于单义域的直线及圆识别算法霍夫变换为几何图形的识别的一个重要算法,但是由于该标准算法的时间复杂度和空间复杂度都是( ) m O N , 其中 m 是参数坐标的维数, 虽然有不少针对具体问题(例如直线识别)的改进算法,其在实际使用中也存在计算量大的问题。针对本论文的工作的实际情况,参考文献【 1 】,并进行了适当的简化, 完成了论文的识别部分。下面就对这个基于单义域的识别算法进行简单的介绍。 2.1 多义域的获得单义域是指对待识别的图形进行分割得到的具有单一的几何意义(线段或圆弧)点的集合。对图片进行从上往下、从左往右的扫描,根据交点进行分割得到多义域,多义域中的点构成一个连通区域。对多义域进行识别并分割得到单义域。多义域由链表实现。算法描述如下: 1. 对图形进行从上往下、从左往右的扫描; 2. 对每一个前景点,判断其是否为交点; 3. 将该点与现有的多义域的头(如果其头节点不是交点)、尾(如果其尾节点不是交点)节点进行比较,如果与头节点相邻,将其插入到该多义域的头节点之前;如果与尾节点相邻,将其插入到该多义域的尾节点之后。 4. 如果该前景点不属于任何现有多义域,则以该点为头节点生成新的多义域。 5. 直到图形扫描完毕。注:交点的判断。由此得到的多义域将是一个线段、一个圆弧或者线段和圆弧的组合。在后续的识别过程中将把不是单义域的进行分裂。
全文预览
