PCB板图形元素的解析与求并算法研究

作     者：李梦珂 

作者单位：杭州电子科技大学 

学位级别：硕士

导师姓名：包健

授予年度：2022年

学科分类：080903[工学-微电子学与固体电子学] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

主      题：布尔并运算 PCB板 光栅化 奇异问题 缺陷检测 

摘      要：在工业4.0与电子制造业自动化时代下,印刷电路板(Printed Circuit Board,PCB)制造行业朝着超薄型、细间距、低缺陷、高密度等方向快速发展,因此,自动光学检测(Automated Optical Inspection,AOI)技术作为PCB板缺陷检测的主流技术变得越来越关键。然而,该技术长期被国外垄断,是我国的“卡脖子技术之一。目前国内针对AOI技术的研究大都基于图像模板来实现,这种方式虽方便与采集图像作比对,但图像模板的精度、形变等问题会直接影响缺陷检测的效果。而图形模板能够保留PCB板图形元素的矢量信息,不易受形变的影响。因此,本文针对基于图形模板的PCB板缺陷检测技术中PCB板图形元素的解析与求并算法进行了深入的研究,主要如下:(1)在计算机图形学布尔运算的基础上,针对AOI技术中PCB板图形元素的解析与求并问题,提出了一种基于方向向量旋转角度的二维图形布尔并运算方法。首先,算法采用链表结构存储图形的基本信息,并定义点的“入边和“出边属性。其次,求解出所有交点,并利用改进后的射线法识别内点和外点,进而判别出有效点和无效点。然后,遍历连通域内的有效点并根据边的方向向量的旋转角度大小选择轮廓边。最后,连接所有轮廓边得到连通域布尔并图形轮廓。该算法解决了布尔并运算中常见的特殊奇异问题(例如重合点、重合边、圆弧相切、带有孔洞),适用于由直线段和圆弧段构成的具有正负极属性的二维图形布尔并运算,能够正确求解出PCB板图形元素的布尔并轮廓,生成图形模板。(2)针对上述算法的精度误差和时间复杂度问题进行了进一步的优化研究,提出了一种基于图像点阵的优化方法。首先,建立矢量图形数据与栅格化像素点之间的映射关系,利用图形光栅化技术来控制二维图形栅格化的精度,避免了工程容差和计算机浮点数计算误差带来的精度影响,提高了算法稳定性。然后,用链表结构存储同一像素点上重合的二维图形序号,通过图形序号定位到其矢量数据,进而计算图形交点,有效降低了二维图形交点计算的时间复杂度。最后,利用光栅化生成的填充图像快速识别内点和外点,避免了冗余的计算过程,提高了算法的整体执行效率。(3)将优化后的二维图形布尔并算法应用在AOI系统中图形模板生成模块。首先,针对基本图形元素及常见特殊奇异情况的求解进行了实验验证。然后,随机选取100块PCB板进行实板实验,算法平均执行时间为1分钟左右,错误率为0.005%左右。结果表明,该算法不仅准确率高、速度快,而且有效地解决了精度误差带来的问题,在实际工程中具有良好的应用价值,为AOI缺陷检测技术的发展提供了良好的技术和思路。