D0I:10.13374/1.issm100I103.2008.0L.02I 第30卷第1期 北京科技大学学报 Vol.30 No.1 2008年1月 Journal of University of Science and Technology Beijing Jan.2008 基于自构建多窗体结构的多目标匹配算法 郗安民朱欣昱谢飞 北京科技大学机械工程学院，北京100083 摘要针对大批量芯片生产中视觉检测难题，提出了一种基于多窗体结构的多目标匹配算法，实现了多窗体结构的自构 建.结合螺旋形特征链对最多近似点距离(MCD)进行了改进，提高了算法速度和鲁棒性·通过实验证实：该算法较好地完成 了大批量芯片识别任务：该算法除了具有高速度和高精确度的优点之外，还具有其他算法不具备的柔性， 关键词视觉检测：芯片生产；多窗体；最多近似点距离(MCD) 分类号TP391.4 Mass-target image matching algorithm based on self-constructed multi-window XI Anmin,ZHU Xinyu,XIE Fei School of Mechanical Engineering.University of Science and Technology Beijing.Beijing 100083.China ABSTRACT An algorithm of mass"target image matching for vision measurement in mass chip production was put forward to carry out multi-window self-construction.Spiral character chain was used to modify maximum close distance (MCD)for improving the speed and robustness.Experimental results confirm that the assignment of recognizing mass chips is achieved by the algorithm.Beside the advantages of high speed and precision,it is flexible compared with other algorithms. KEY WORDS vision measurement:chip production:multi-window:maximum close distance (MCD) 在电子器件的生产中，微细芯片检测分选的关 殊要求，随着芯片种类日趋增多，其图像特征千差 键技术之一，是对CCD摄像机所拍摄的芯片群进行 万别，对于不同的芯片，往往缺乏具共性的特征可 视觉定位，为后续分选工序提供位置参数，并对芯片 供提取识别，这就要求图像定位识别算法的判据不 的物理损伤情况进行初步检测，通常情况下，芯片 应是某些图形的某种特殊图像特征，而应该具有广 的排列是半有序性的，即有一定规律，但并不严格遵 泛的适应性，即柔性，目前，即使国外技术，尚不满 守.针对此类多目标识别的算法有如下难点及 足此类要求， 要求， 现有的图像识别算法均无法同时满足以上三个 ()算法的实时性，一张芯片盘上的芯片数量 要求，更缺少结合实际工业环境进行深入的研 通常为几千到几万不等，目前最快的处理速度为每 究].针对上述要求，相对而言采用基于像素的 秒2~3个芯片，除去机械运动及辅助工序的占用 模板匹配算法较为合适].由于模板图像可以由操 时间，对国外同类设备的测试结果表明，留给每个芯 作人员选取，因而在识别过程中，算法无需对特定的 片的平均识别时间最大不超过0.1s, 特征形状进行计算、判别和分类，只需比对两幅图像 (2)定位的精确性·芯片整体尺寸为百微米 的异同，满足了算法柔性的要求， 级，需为控制系统准确地提供其电极位置及质心位 国内有文献对此类情况下模板匹配的应用进行 置，国外同类设备中的识别算法，经位置换算后的 了研究，但大多局限于传统模板匹配，但传统模板 位置误差不超过10m, 匹配算法采取逐个像素遍历的方法，计算速度极慢. (③)算法的柔性，这是本文首次提出的一个特 因此，即使采用粗一精匹配策略，在目标密集、大图 收稿日期：2006-09-31修回日期：2007-03-16 幅、大模板的匹配任务中，不能保证检测的实时 基金项目：国家高技术研究发展计划资助项目(No,2004AA31g080) 性6] 作者简介：都安民(1958一)：男，教授，博士生导师 模板匹配算法还会导致另一问题，即相似度判
基于自构建多窗体结构的多目标匹配算法 郗安民 朱欣昱 谢 飞 北京科技大学机械工程学院北京100083 摘 要 针对大批量芯片生产中视觉检测难题提出了一种基于多窗体结构的多目标匹配算法实现了多窗体结构的自构 建．结合螺旋形特征链对最多近似点距离（MCD）进行了改进提高了算法速度和鲁棒性．通过实验证实：该算法较好地完成 了大批量芯片识别任务；该算法除了具有高速度和高精确度的优点之外还具有其他算法不具备的柔性． 关键词 视觉检测；芯片生产；多窗体；最多近似点距离（MCD） 分类号 TP391∙4 Mass-target image matching algorithm based on self-constructed mult-i window XI A nminZHU XinyuXIE Fei School of Mechanical EngineeringUniversity of Science and Technology BeijingBeijing100083China ABSTRACT An algorithm of mass-target image matching for vision measurement in mass chip production was put forward to carry out mult-i window self-construction．Spiral character chain was used to modify maximum close distance （MCD） for improving the speed and robustness．Experimental results confirm that the assignment of recognizing mass chips is achieved by the algorithm．Beside the advantages of high speed and precisionit is flexible compared with other algorithms． KEY WORDS vision measurement；chip production；mult-i window；maximum close distance （MCD） 收稿日期：2006-09-31 修回日期：2007-03-16 基金项目：国家高技术研究发展计划资助项目（No．2004AA31g080） 作者简介：郗安民（1958—）男教授博士生导师 在电子器件的生产中微细芯片检测分选的关 键技术之一是对 CCD 摄像机所拍摄的芯片群进行 视觉定位为后续分选工序提供位置参数并对芯片 的物理损伤情况进行初步检测．通常情况下芯片 的排列是半有序性的即有一定规律但并不严格遵 守．针对此类多目标识别的算法有如下难点及 要求． （1） 算法的实时性．一张芯片盘上的芯片数量 通常为几千到几万不等．目前最快的处理速度为每 秒2～3个芯片．除去机械运动及辅助工序的占用 时间对国外同类设备的测试结果表明留给每个芯 片的平均识别时间最大不超过0∙1s． （2） 定位的精确性．芯片整体尺寸为百微米 级需为控制系统准确地提供其电极位置及质心位 置．国外同类设备中的识别算法经位置换算后的 位置误差不超过10μm． （3） 算法的柔性．这是本文首次提出的一个特 殊要求．随着芯片种类日趋增多其图像特征千差 万别．对于不同的芯片往往缺乏具共性的特征可 供提取识别．这就要求图像定位识别算法的判据不 应是某些图形的某种特殊图像特征而应该具有广 泛的适应性即柔性．目前即使国外技术尚不满 足此类要求． 现有的图像识别算法均无法同时满足以上三个 要求更缺少结合实际工业环境进行深入的研 究［1—2］．针对上述要求相对而言采用基于像素的 模板匹配算法较为合适［3］．由于模板图像可以由操 作人员选取因而在识别过程中算法无需对特定的 特征形状进行计算、判别和分类只需比对两幅图像 的异同满足了算法柔性的要求． 国内有文献对此类情况下模板匹配的应用进行 了研究但大多局限于传统模板匹配．但传统模板 匹配算法采取逐个像素遍历的方法计算速度极慢． 因此即使采用粗—精匹配策略在目标密集、大图 幅、大模板的匹配任务中不能保证检测的实时 性［4—6］． 模板匹配算法还会导致另一问题即相似度判 第30卷 第1期 2008年 1月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．1 Jan．2008 DOI:10．13374／j．issn1001－053x．2008．01．021
第1期 郗安民等：基于自构建多窗体结构的多目标匹配算法 97 据单一，而单一判据很难无错判、无漏判、对复杂的 少图像处理工作量，降低图像处理难度.而且由于 目标特征与同样复杂的背景特征进行识别分类)]. 窗体的处理数据量相对较少，可以采用适应性强、鲁 因此需要对传统模板匹配算法进行较大改进，才有 棒性好的计算方法，提高目标识别系统的鲁棒性，以 可能满足要求.文献[8-11]采用的是通过二值化将 达到多目标检测的快速性和准确性要求。此外，由 目标同背景区分成黑白两块区域，消除目标的复杂 于窗体内的预定目标个数G∈[0,1]，因此可以采 特征，而后对二值化图进行匹配.这种方法较为简 用单一阈值和最大相似准则相结合的方法，有效地 便，但对实际情况中的光照情况估计不足，在光照 分辨匹配目标和背景干扰 较差的情况下，二值化处理无法区分目标与背景，反 但是，多窗体结构构建的参数完全来源于定位 而会损失有用信息，不利于识别本文提出了一种针 系统对系统状态的估计和传感器的感知机理的先验 对灰度图的基于自构建多窗体结构的多目标匹配算 知识来获得，限制了其适用范围，因此长期以来未得 法，成功地解决了以上问题 到重视和发展。而在实际芯片识别系统中，由于检 1 基于自构建多窗体结构的多目标匹配 测目标尺寸及分布并不确定，所以无法获得所需先 验知识，本文提出了一种新的多窗体结构的自构建 算法 方法，扩展了这一概念的适用范围 1.1多窗体结构 1.2多窗体结构的自构建 多窗体结构12]的概念最早在1983年由日本东 首先需要对芯片图像和模板图像分别进行二维 京大学提出，其实质是处理图像内包含许多预先估 投影.水平投影是将横坐标相等的图像点像素值进 计的可单独处理的矩形区域，每一个区域是一个“窗 行叠加，作为该行的水平投影结果；垂直投影是将纵 体”，每个窗体内预定目标个数G∈[0,1]，通过对 坐标相等的图像点像素值进行叠加，作为该列的垂 目标区域的图像处理，提取该区域存在的特征几何、 直投影结果，图1和图2分别是对一种芯片原图及 灰度等，进而完成目标的识别.多窗体结构可以减 其模板图像进行x向和y向投影的结果 (b) 图1原图水平(a)和垂直积分投影图(b) Fig.1 Horizontal (a)and vertical(b)projection of searching picture (b) 图2模板水平(a)和垂直积分投影(b) Fig.2 Horizontal (a)and vertical (b)projection of template
据单一．而单一判据很难无错判、无漏判、对复杂的 目标特征与同样复杂的背景特征进行识别分类［7］． 因此需要对传统模板匹配算法进行较大改进才有 可能满足要求．文献［8—11］采用的是通过二值化将 目标同背景区分成黑白两块区域消除目标的复杂 特征而后对二值化图进行匹配．这种方法较为简 便但对实际情况中的光照情况估计不足．在光照 较差的情况下二值化处理无法区分目标与背景反 而会损失有用信息不利于识别本文提出了一种针 对灰度图的基于自构建多窗体结构的多目标匹配算 法成功地解决了以上问题． 1 基于自构建多窗体结构的多目标匹配 算法 1∙1 多窗体结构 多窗体结构［12］的概念最早在1983年由日本东 京大学提出．其实质是处理图像内包含许多预先估 计的可单独处理的矩形区域每一个区域是一个“窗 体”每个窗体内预定目标个数 G∈［01］通过对 目标区域的图像处理提取该区域存在的特征几何、 灰度等进而完成目标的识别．多窗体结构可以减 少图像处理工作量降低图像处理难度．而且由于 窗体的处理数据量相对较少可以采用适应性强、鲁 棒性好的计算方法提高目标识别系统的鲁棒性以 达到多目标检测的快速性和准确性要求．此外由 于窗体内的预定目标个数 G∈［01］因此可以采 用单一阈值和最大相似准则相结合的方法有效地 分辨匹配目标和背景干扰． 但是多窗体结构构建的参数完全来源于定位 系统对系统状态的估计和传感器的感知机理的先验 知识来获得限制了其适用范围因此长期以来未得 到重视和发展．而在实际芯片识别系统中由于检 测目标尺寸及分布并不确定所以无法获得所需先 验知识．本文提出了一种新的多窗体结构的自构建 方法扩展了这一概念的适用范围． 1∙2 多窗体结构的自构建 首先需要对芯片图像和模板图像分别进行二维 投影．水平投影是将横坐标相等的图像点像素值进 行叠加作为该行的水平投影结果；垂直投影是将纵 坐标相等的图像点像素值进行叠加作为该列的垂 直投影结果．图1和图2分别是对一种芯片原图及 其模板图像进行 x 向和 y 向投影的结果． 图1 原图水平（a）和垂直积分投影图（b） Fig．1 Horizontal （a） and vertical （b） projection of searching picture 图2 模板水平（a）和垂直积分投影（b） Fig．2 Horizontal （a） and vertical （b） projection of template 第1期 郗安民等： 基于自构建多窗体结构的多目标匹配算法 ·97·
.98 北京科技大学学报 第30卷 设搜索图大小为M×N,模板图大小为m× 为多个窗体特征向量集，即使两两窗体之间有信息 .模板图像的二维投影信息分别组成水平向量Yh 重叠区域（这在大批量芯片识别中较为常见，可以大 和垂直投影向量Y,而搜索图的二维投影信息分别 幅提高鲁棒性)，对于计算速度也有很大优化效果 组成了水平投影向量集合以及垂直投影向量集合： 此外，在单个窗体内，仍可以采用传统的粗一精策略 n=(X,X6,X,…,X),=N-n十1； 来进一步优化计算速度，但无论多窗体结构，还是 Q=(X,x2,x3,…,),j=M-m十1. 粗一精匹配策略，都需要相似度量曲面的峰值越尖 由于搜索图投影信息的某些部分可以近似地看 锐越好，本文将螺旋式特征链结构同改进的最多近 作模板图投影信息的比例放大，按下式计算： 似点距离(MCD)相结合，创造了一种新的相似度度 Simh(Xh)= XY,0<≤N-n十1 量作为相似度判据，称之为有序最多近似点度量. h Yh 由于待识别目标的边缘图像干扰巨大，因此， (1) 在对模板的预处理中，使用特征链的结构·从图像 Y,三，0<≤M-m十1 特征最完好的中心开始螺旋式搜索，特征链结构如 sim(X)=Jx及JY.Y. 图3，依次将搜索到的特征点存入特征链，匹配时依 照特征链的顺序进行计算 (2) Sim(X)和Sim,(X)具有比例不变性.根据 式(l)和(2)解得Simh(X)和Sim,(X)的曲线 设图像空间存在点O(i0,jo),令 ioSim=max Simn(Xh) (3) joSimSim, (4) 点O(i0,j0)可以近似认为是在某一个芯片图 …□ 像的中心，这样就获取了分割图像特征向量集时的 参考起始点 图3螺旋式搜索后的特征链 再判断出Simh和Sim,局部极值，局部极值的 Fig.3 Character chain created by gyroidal searching 判别约束有两个， 设窗体特征向量集为{X1,X2,X3,,X:},= (1)门限约束.Simh(v)(Xho))>Ka,K,为相似 (M-W十1)X(N-H+1),模板向量为Y=(y1, 度门限，h(v)代表水平或垂直（下文同），本文中K。 y2,,yi),j=mx n. 取0.99（实验测定值）； 改进后的MCD距离为： (2)邻域极值约束.若大于K,的Simh(v)数据 间隔小于K(邻域间隔门限)，则认为它们属于同一 D(X:,Y)= R(》 (5) =1 邻域，取其中最大值作为局部极值，本文中K。取 R(xy)一0， 为yT (6) x一y≥T 而后计算两个相邻局部极值的间距d.和d, 其中，T为经实验测定的阈值；，为第j个特征点 取min(d.)和min(d,)作为子窗体在水平和垂直方 的优先性权值，取值为： 向上的参考间隔 1, n 至此，由于获得了参考起始点以及参考间隔，结 (7) 合搜索图像尺寸和模板图像尺寸，就可以完全实现 e,j≥n 多窗体结构的自构建，本文经过大量实验确定出的 式中，n为常数，可通过实验获得 求解窗体尺寸的经验公式为：子特征集宽度W= 对于单个窗体而言，由于第I类图像个数G∈ 2.1m,高度H=1.8n, [0,1],因此只需求得D(X:,Y)的局部极值点 多窗体结构的自构建可以看作是一种粗匹配， 要D(X,Y),则该点对应的子图向量X:即为初 由于多窗体结构的鲁棒性较好，因此位置参考点 步匹配点，再结合单一阈值法，使用Dthread(实验测 O(x,y)与参考间隔的精度无需很高 定)作为二次判决阈值，就能将巴要D(X:,Y)< 1.3有序最多近似点距离 Dtheread的误匹配点除去，这些误匹配点，可能是图 多窗体结构的实质是将搜索图特征向量集分解 像干扰，也可能是破损芯片
设搜索图大小为 M× N模板图大小为 m × n．模板图像的二维投影信息分别组成水平向量 Yh 和垂直投影向量 Yv而搜索图的二维投影信息分别 组成了水平投影向量集合以及垂直投影向量集合： Ωh＝（X 1 hX 2 hX 3 h…X i h）i＝ N— n＋1； Ωv＝（X 1 vX 2 vX 3 v…X j v）j＝ M— m＋1． 由于搜索图投影信息的某些部分可以近似地看 作模板图投影信息的比例放大．按下式计算： Simh（X i h）＝ X i h Yh X i h X i h Yh Yh 0＜ i≤ N— n＋1 （1） Simv（X j v）＝ X j v Yv X j v X j v Yv Yv 0＜ j≤ M— m＋1 （2） Simh（X i h）和 Simv （ X j v）具有比例不变性．根据 式（1）和（2）解得 Simh（X i h）和 Simv（X j v）的曲线． 设图像空间存在点 O（ i0j0）令 i0＝｛k｜Sim k h＝ max 0＜ i≤ N— n＋1 Simh（X i h）｝ （3） j0＝｛k｜Sim k v ＝ max 0＜ j≤ M— m＋1 Simv（X j v）｝ （4） 点 O（ i0j0）可以近似认为是在某一个芯片图 像的中心这样就获取了分割图像特征向量集时的 参考起始点． 再判断出 Simh 和 Simv 局部极值局部极值的 判别约束有两个． （1） 门限约束．Simh（v）（X i h（v））＞ KsKs 为相似 度门限h（v）代表水平或垂直（下文同）．本文中 Ks 取0∙99（实验测定值）； （2） 邻域极值约束．若大于 Ks 的Simh（v）数据 间隔小于 Kn（邻域间隔门限）则认为它们属于同一 邻域取其中最大值作为局部极值．本文中 Kn 取 5． 而后计算两个相邻局部极值的间距 dh 和 dv 取min（ dh）和min（ dv）作为子窗体在水平和垂直方 向上的参考间隔． 至此由于获得了参考起始点以及参考间隔结 合搜索图像尺寸和模板图像尺寸就可以完全实现 多窗体结构的自构建．本文经过大量实验确定出的 求解窗体尺寸的经验公式为：子特征集宽度 W ＝ 2∙1m高度 H＝1∙8n． 多窗体结构的自构建可以看作是一种粗匹配 由于多窗体结构的鲁棒性较好因此位置参考点 O（ xy）与参考间隔的精度无需很高． 1∙3 有序最多近似点距离 多窗体结构的实质是将搜索图特征向量集分解 为多个窗体特征向量集即使两两窗体之间有信息 重叠区域（这在大批量芯片识别中较为常见可以大 幅提高鲁棒性）对于计算速度也有很大优化效果． 此外在单个窗体内仍可以采用传统的粗—精策略 来进一步优化计算速度．但无论多窗体结构还是 粗—精匹配策略都需要相似度量曲面的峰值越尖 锐越好．本文将螺旋式特征链结构同改进的最多近 似点距离（MCD）相结合创造了一种新的相似度度 量作为相似度判据称之为有序最多近似点度量． 由于待识别目标的边缘图像干扰巨大．因此 在对模板的预处理中使用特征链的结构．从图像 特征最完好的中心开始螺旋式搜索特征链结构如 图3．依次将搜索到的特征点存入特征链匹配时依 照特征链的顺序进行计算． 图3 螺旋式搜索后的特征链 Fig．3 Character chain created by gyroidal searching 设窗体特征向量集为｛X1X2X3…Xi｝i＝ （ M— W＋1）×（ N— H＋1）模板向量为 Y＝（ y1 y2…yj）j＝ m× n． 改进后的 MCD 距离为： D（XiY）＝ ∑ m×n j＝1 R（ xjyj） （5） R（ xjyj）＝ ωj xj—yj＜ T 0 xj—yj≥ T （6） 其中T 为经实验测定的阈值；ωj 为第 j 个特征点 的优先性权值取值为： ω＝ 1 j＜ n e — j 1／4 j≥ n （7） 式中n 为常数可通过实验获得． 对于单个窗体而言由于第 I 类图像个数 G∈ ［01］．因此只需求得 D （ XiY） 的局部极值点 max 1＜ i＜ N D（XiY）则该点对应的子图向量 Xi 即为初 步匹配点．再结合单一阈值法使用 Dthread（实验测 定）作为二次判决阈值就能将 max 1＜ i＜ N D（ XiY）＜ Dtheread的误匹配点除去．这些误匹配点可能是图 像干扰也可能是破损芯片． ·98· 北 京 科 技 大 学 学 报 第30卷
第1期 郗安民等：基于自构建多窗体结构的多目标匹配算法 .99 使用有序最多近似点距离，对拥有四个识别目 度判据的相似曲面进行比较，结果如图4所示 标的图像进行计算，将获得的相似曲面与传统相似 可以看到，有序最多近似点距离的峰值更为突 1.00 600 0.95 400 0.90 N0.85 200 0.8 200150 00 00150 00 x/pixel 50650100150200250 ypixel xpixel 50 0050100150200250 wpixel 图4使用传统相似度判据(a)与有序最多近似点距离(b)获得的相似曲面比较 Fig.4 Comparison of curves obtained by traditional similarity measurement (a)and ordered maximum close distance (b) 出尖锐，与背景干扰的区别较大，利于后续的分辨， 初步匹配点，采用固定相似度门限判别，将低于门限 综上所述，基于自构建多窗体结构的模板匹配 的初步匹配点排除； 算法，其总体思路如下： (8)将最终匹配对象的图像坐标位置输出，供 (1)对搜索图（灰度图）和模板图像使用3×3 后续使用 高斯平滑预处理，消除微小的背景干扰，保留预处理 2实验 后的搜索图（灰度图）和模板（灰度图）； (2)对(1)中保存的模板图像进行螺旋式搜索， 分别使用本文算法针对三类共45幅不同位置 将所有特征信息依次存入特征链： 拍摄的图像进行识别.图像大小均为1280 pixelX (③)使用同一阈值对搜索图和模板图进行二值 1024 pixel.其中第1类图像拍摄状况接近生产正 化，对结果图分别进行水平和垂直投影； 常状态，光线良好，目标较为整齐，第2类图像拍摄 (4)根据(3)获得的投影结果，采用本文计算方 状况系生产中的极端状况，光线较差，目标凌乱、缺 法求得多窗体结构的主要参数： 失，第3类芯片图像目标结构复杂，边缘的反光干 (5)使用(4)中获得的参数，在(1)中保留的搜 扰严重，模板较大.三类图像每类15幅，共计45 索图上建立多窗体结构： 幅.图5(a)为第1类图像，(b)和(c)为第2类图像 (6)在每个窗体中使用特征链中存储特征，采 第3类图像的芯片尺寸较大，电极形状呈雪花状，极 用有序最多近似点距离进行特征匹配，每个窗体中 为复杂，图像的矩形外缘模糊不清。针对上述三类 的模板遍历采用粗一精匹配策略以提高速度（本文 图像进行识别，并与传统模板匹配法及国外同类设 实验中间隔为1pixel); 备所用的几何特征检测法识别结果进行对比·在对 (7)对每个窗体中求得的相似度极大值点作为 不同图像的识别中，算法未进行任何改动 (a) (b) 图5实验图像的局部图 Fig.5 Parts of testing images 表1为本文算法对三种图像的识别效果，表2 比较 为包括本文算法在内的三种不同算法在速度方面的
使用有序最多近似点距离对拥有四个识别目 标的图像进行计算将获得的相似曲面与传统相似 度判据的相似曲面进行比较结果如图4所示． 可以看到有序最多近似点距离的峰值更为突 图4 使用传统相似度判据（a）与有序最多近似点距离（b）获得的相似曲面比较 Fig．4 Comparison of curves obtained by traditional similarity measurement （a） and ordered maximum close distance （b） 出尖锐与背景干扰的区别较大利于后续的分辨． 综上所述基于自构建多窗体结构的模板匹配 算法其总体思路如下： （1） 对搜索图（灰度图）和模板图像使用3×3 高斯平滑预处理消除微小的背景干扰保留预处理 后的搜索图（灰度图） 和模板（灰度图）； （2） 对（1）中保存的模板图像进行螺旋式搜索 将所有特征信息依次存入特征链； （3） 使用同一阈值对搜索图和模板图进行二值 化对结果图分别进行水平和垂直投影； （4） 根据（3）获得的投影结果采用本文计算方 法求得多窗体结构的主要参数； （5） 使用（4）中获得的参数在（1）中保留的搜 索图上建立多窗体结构； （6） 在每个窗体中使用特征链中存储特征采 用有序最多近似点距离进行特征匹配每个窗体中 的模板遍历采用粗—精匹配策略以提高速度（本文 实验中间隔为1pixel）； （7） 对每个窗体中求得的相似度极大值点作为 初步匹配点采用固定相似度门限判别将低于门限 的初步匹配点排除； （8） 将最终匹配对象的图像坐标位置输出供 后续使用． 2 实验 分别使用本文算法针对三类共45幅不同位置 拍摄的图像进行识别．图像大小均为1280pixel× 1024pixel．其中第1类图像拍摄状况接近生产正 常状态光线良好目标较为整齐．第2类图像拍摄 状况系生产中的极端状况光线较差目标凌乱、缺 失．第3类芯片图像目标结构复杂边缘的反光干 扰严重模板较大．三类图像每类15幅共计45 幅．图5（a）为第1类图像（b）和（c）为第2类图像． 第3类图像的芯片尺寸较大电极形状呈雪花状极 为复杂图像的矩形外缘模糊不清．针对上述三类 图像进行识别并与传统模板匹配法及国外同类设 备所用的几何特征检测法识别结果进行对比．在对 不同图像的识别中算法未进行任何改动． 图5 实验图像的局部图 Fig．5 Parts of testing images 表1为本文算法对三种图像的识别效果表2 为包括本文算法在内的三种不同算法在速度方面的 比较． 第1期 郗安民等： 基于自构建多窗体结构的多目标匹配算法 ·99·
.100 北京科技大学学报 第30卷 表1算法识别效果 (2)特征链结构可与变模板技术相结合，在算法流 Table 1 Recognition results by the algorithm 程特定阶段根据识别结果，调整特征链结构，能够增 图像 目标 模板尺寸/ 漏识 误识 强算法在长时间工业生产中的稳定性 类型 数 (pixelXpixel) 率/% 率/% 1 99 77X78 0.36 0 参考文献 2 64 46×48 1.818 0.191 [1]Jin M H.Dong Z L.Zhu F,et al.Adaptive gray estimating 3 12 237×241 0.556 0 method for fast multitarget recognition.Compu Eng.2003.29 注：定位误差超出3pixl(约l0m)视为误识别，所有数据均为 (8):131 多次实验的平均值。 (金明华，董再励，朱枫，等。一种多目标快速识别的自适应灰 度量化方法研究.计算机工程，2003,29(8)：131) 表2算法速度比较 [2]Wang HX.Zhao W.Li Y X.et al.Multi-object recognition us- Table 2 Speed comparison of algorithms ms ing power spectrum optimized joint transform correlator.Opt 图像类型 本文算法 传统模板匹配 特征检测法 Tech,2006,32(2):190 1 8.04 3352.91 12.00 (王红霞，赵玮，李育新，等.多目标识别的联合变换相关器的 14.51 419.67 11.83 研究.光学技术，2006,32(2)：190) 75.23 255.00×103 无法识别 [3]Niu C.Liang W.Image correlation matching algorithm based on statistics of pixel eigenvalue.Control Autom,2005,21(11): 103 3实验结果 (牛刚，梁伟，基于特征像素统计的图像相关匹配算法·微计 算机信息，2005,21(11)：103) (1)第1类图像识别结果表明：对于拍摄效果 [4]Atallah M J.Fast image template matching in the sum of the ab- 较好的图像，即使不进行特殊的背景补偿，本算法的 solute value of differences measure.IEEE Trans Image Process. 漏识率仍然很低，无误识，漏识的原因是：个别芯片 2001,10(4):659 放置不平，导致反光异常；光照不均匀，个别区域明 [5]Wang L S.Template matching approach to edge detection of vol- 暗变化太大，如果能够在第1步预处理中加入背景 ume data.Workshop Med Imag Argument Reality.2001:286 补偿算法，漏识率能进一步降低， [6]Kwon O K,Sim D C.Park R H.Robust Hausdorff distance matching algorithms using pyramidal structures.Pattern Recog- (2)第2类图像识别结果表明：在干扰较大的 ni,2001,34(7):2005 情况下，漏识率上升，并出现误识情况，这是由于个 [7]Wang H M.Zhang K.Li Y J,et al.Research progress on image 别干扰特征与目标特征混淆造成的，但漏识率和误 matching.Comput Eng Appl,2004.19:42 识率仍维持在较低的水平.鉴于此类图像状况属极 (王红梅，张科，李彦俊，等。图像匹配研究进展、计算机工程 与应用，2004,19,42) 端状况，在正常生产中极少出现，该实验数据在生产 [8]Fang XS.Hu Y M.Gao H X.et al.High speed and high preci- 中也是可以接受的， sion vision detection and locating algorithm of BGA.Electron (3)第3类图像的识别结果验证了算法的柔 Process Technol.2006.27(5):262 性.首先，无需对算法进行任何改变，就能够处理完 (方晓胜，胡晓明，高红霞，等.BGA芯片的高速高精度视觉 全不同的目标图像；而国外同类设备所使用的几何 检测与定位算法.电子工艺技术，2006,27(5)：262) 特征检测算法，在不更改算法的情况下，完全无法进 [9]Guo QS,Jin W C.Zhou Q Y,et al.Vision inspection technolo- gy of IC die bonder.Semicond Ind,2006.2:59 行识别，其次，验证了改进MCD距离以及特征链对 (郭强生，新卫国，周庆亚，等。集成电路粘片机视觉检测技术 模板边缘噪声处理的有效性·再次，验证了本文算 半导体行业，2006,2.59) 法的运算速度对于模板大小并不敏感：随着模板的 [10]Zhong JS,Li Q C.Xia Y P.et al.Vision system of mounter 增大，传统模板匹配算法计算时间增加了约4min, and its visual location.Equip Electron Prod Manuf.2005, 131,26 本文算法时间仅增加67.19ms,因而本文算法在速 (钟江生，李泰川，夏毓鹏，等.贴片机视觉系统构成原理及其 度和柔性两个方面拥有极大的优势. 视觉定位.电子工业专用设备，2005,131：26) 4结语 [11]Wang JB.Hu H.Template matching approach to prober station system.Comput Inf Technol,2006(Z1):13 此算法目前已很好地应用于自行开发的二极管 (王建波，胡泓，图象模板匹配技术在探针台系统中的应用 计算机与信息技术，2006(Z1):13 芯片检测分选系统，实际应用和进一步研究中，如 [12]Barth M.An attentive sensing strategy for a multi window vi- 能够进行如下改进，预计会获得更好的效果：(1)结 sion architecture parallel architectures for image processing. 合背景预处理算法，进一步提高算法的识别正确率； SPIE,1990,1246:198
表1 算法识别效果 Table1 Recognition results by the algorithm 图像 类型 目标 数 模板尺寸／ （pixel×pixel） 漏识 率／％ 误识 率／％ 1 99 77×78 0∙36 0 2 64 46×48 1∙818 0∙191 3 12 237×241 0∙556 0 注：定位误差超出3pixel（约10μm）视为误识别所有数据均为 多次实验的平均值． 表2 算法速度比较 Table2 Speed comparison of algorithms ms 图像类型 本文算法 传统模板匹配 特征检测法 1 8∙04 3352∙91 12∙00 2 14∙51 419∙67 11∙83 3 75∙23 255∙00×103 无法识别 3 实验结果 （1） 第1类图像识别结果表明：对于拍摄效果 较好的图像即使不进行特殊的背景补偿本算法的 漏识率仍然很低无误识．漏识的原因是：个别芯片 放置不平导致反光异常；光照不均匀个别区域明 暗变化太大．如果能够在第1步预处理中加入背景 补偿算法漏识率能进一步降低． （2） 第2类图像识别结果表明：在干扰较大的 情况下漏识率上升并出现误识情况．这是由于个 别干扰特征与目标特征混淆造成的但漏识率和误 识率仍维持在较低的水平．鉴于此类图像状况属极 端状况在正常生产中极少出现该实验数据在生产 中也是可以接受的． （3） 第3类图像的识别结果验证了算法的柔 性．首先无需对算法进行任何改变就能够处理完 全不同的目标图像；而国外同类设备所使用的几何 特征检测算法在不更改算法的情况下完全无法进 行识别．其次验证了改进 MCD 距离以及特征链对 模板边缘噪声处理的有效性．再次验证了本文算 法的运算速度对于模板大小并不敏感；随着模板的 增大传统模板匹配算法计算时间增加了约4min 本文算法时间仅增加67∙19ms因而本文算法在速 度和柔性两个方面拥有极大的优势． 4 结语 此算法目前已很好地应用于自行开发的二极管 芯片检测分选系统．实际应用和进一步研究中如 能够进行如下改进预计会获得更好的效果：（1）结 合背景预处理算法进一步提高算法的识别正确率； （2）特征链结构可与变模板技术相结合．在算法流 程特定阶段根据识别结果调整特征链结构能够增 强算法在长时间工业生产中的稳定性． 参 考 文 献 ［1］ Jin M HDong Z LZhu Fet al．Adaptive gray estimating method for fast mult-i target recognition．Comput Eng200329 （8）：131 （金明华董再励朱枫等．一种多目标快速识别的自适应灰 度量化方法研究．计算机工程200329（8）：131） ［2］ Wang H XZhao WLi Y Xet al．Mult-i object recognition using power spectrum optimized joint transform correlator． Opt Tech200632（2）：190 （王红霞赵玮李育新等．多目标识别的联合变换相关器的 研究．光学技术200632（2）：190） ［3］ Niu GLiang W．Image correlation matching algorithm based on statistics of pixel eigenvalue．Control A utom200521（11）： 103 （牛刚梁伟．基于特征像素统计的图像相关匹配算法．微计 算机信息200521（11）：103） ［4］ Atallah M J．Fast image template matching in the sum of the absolute value of differences measure．IEEE T rans Image Process 200110（4）：659 ［5］ Wang L S．Template-matching approach to edge detection of volume data．Workshop Med Imag A rgument Reality2001：286 ［6］ Kwon O KSim D GPark R H．Robust Hausdorff distance matching algorithms using pyramidal structures．Pattern Recognit200134（7）：2005 ［7］ Wang H MZhang KLi Y Jet al．Research progress on image matching．Comput Eng Appl200419：42 （王红梅张科李彦俊等．图像匹配研究进展．计算机工程 与应用200419：42） ［8］ Fang X SHu Y MGao H Xet al．High-speed and high-precision vision detection and locating algorithm of BGA． Electron Process Technol200627（5）：262 （方晓胜胡晓明高红霞等．BGA 芯片的高速高精度视觉 检测与定位算法．电子工艺技术200627（5）：262） ［9］ Guo Q SJin W GZhou Q Yet al．Vision inspection technology of IC die bonder．Semicond Ind20062：59 （郭强生靳卫国周庆亚等．集成电路粘片机视觉检测技术． 半导体行业20062：59） ［10］ Zhong J SLi Q CXia Y Pet al．Vision system of mounter and its visual location． Equip Electron Prod Manuf2005 131：26 （钟江生李泰川夏毓鹏等．贴片机视觉系统构成原理及其 视觉定位．电子工业专用设备2005131：26） ［11］ Wang J BHu H．Template-matching approach to prober station system．Comput Inf Technol2006（Z1）：13 （王建波胡泓．图象模板匹配技术在探针台系统中的应用． 计算机与信息技术2006（Z1）：13 ［12］ Barth M．An attentive sensing strategy for a mult-i window vision architecture parallel architectures for image processing． SPIE19901246：198 ·100· 北 京 科 技 大 学 学 报 第30卷