An automatic algorithm for line judgment based on tracing

Abstract

由于曲线通常可以用直线段逼近 ,直线判别在图象分析、识别及测量等很多涉及形状匹配的领域均有重要应用。由计算机视觉中直线判别的逆问题 ,即计算机图形学中直线生成的观点看 ,除水平、垂直、斜率为± 1的 4个基本方向的直线外 ,所有数字直线均由短的阶梯状的基本直线段构成。通过对数字直线特点进行理论分析 ,证明在其相互垂直方向象素长度分布不会同时超过 1个象素 ,并在此基础上 ,提出并设计了一种基于跟踪的全自动直线判别算法。和现有的一些代表性算法相比 ,实验结果验证了本文方法在减少关键点数和时空开销方面具有显著优势 As curves can be approached by polygons, line judgment is very important in image analysis, recognition, measurement, etc where shape matching is needed. Existing algorithms are not quite satisfactory for line judgment as they all lack theoretical analysis of the characteristics of digital lines. According to line generation in computer graphics, whose inverse problem in computer vision is line judgment, all digital lines consist of one or more of four basic lines: horizontal ( k =0), vertical ( k=∞ ), and ±45° lines ( k =±1) as shown in Fig. 1. In section 1, we propose what we call directional pixel length (DPL) and give two theorems on DPL. These two theorems enable us to propose an automatic algorithm for line judgment based on pixel tracing. Fig.2 shows the comparison of results obtained with Ansari Huang algorithm (Fig.2(b)), Zhu Chirlian algorithm (Fig.2(c)) and our algorithm (Fig.2(d)). This comparison shows that our algorithm appears to be better in that it can reduce the number of critical points and the expenditure of space and time.