当前位置:首页 >> 哲学 >>

全自动金丝球焊机中芯片图像实时定位方法研究


中国科学院长春光学精密机械与物理研究所 硕士学位论文 全自动金丝球焊机中芯片图像实时定位方法研究 姓名:姜凯 申请学位级别:硕士 专业:机械电子工程 指导教师:汤建华 20031210

中Ⅲ科学院纠}究'.院砸}‘论立

摘篮





个n动金丝球蚪p【址集精鬻机械、h,山挖制、㈦像U{别、光。一、趟声波热n、 蝌接等领域r

体f阿现代化I:制使术微fix子封裂设备,l:要用J’笕成fU蹄制造盯

l+序,f r芯片站5搿1jt{'b4til梨fllJ引线的t10接。

木谍腿以外锭仑fI动金缝球蝌机㈥像iJ!别系统软仆乃li要训究内律.沦史-lI
埘课题期^U所做I 7门l:要I.作进行了介绍和总结。 尚‘儿,介绍了个f1 z以企鲐球焊机f门1.作味刖,分析了jL降I像U:*l系统a,以利

川的两种厅江..即图像讣竹帆处用!系统和软f,f:型『冬{像处理系统,外结介隈巡的实
际’ICier选择采IL|』后种疗法。

然后,对舰仃的数‘}嘲像预处辟技术进行了研究.纠埘小课题的特点着曛}J 沦了数宁图像坝处州c},荻度直疗图修整和巾值滤波两种矧像增强披术。试验刈比
了Robe,s算子、Sobel算子、Prewitt算子、Krisch算于及Laplacian弗子“种边

缘捻测罐子,通过对芯片图像边缘检测的刈比试验选择了适合本系统的Robe,s 边缘算子。

j£次.讨沧了H筒常用的儿种苍j荻度p‘配的快速剐像匹配算法,盔IFFT算
法、幅度排J芋十}|天鳟;2:、序贳相似检测算法(SSDA)、多辨率塔型结构茸}』.

(MPSA)、疆。J:遗传算法(GA)的快速搜索钟=法等.通过』i体试验t…--i‘t合其味
理分析了它们的优缺点,分析表叫这些算法部/f:能满足全17j动金蝗球_#-b'L罔像U{ 剐系统的安时性(<25ms/绂)要求,并¨时旧种锌泛、也小能满足』I育旋转化r芝 (一7”~+7。)的芯片劁像的l;l=_fifi精度要求。 再次.针对术课题实时tl:及精度的要求,提…了两种能够满足系统要求的算 法和…种f£育应刚价值的算泛:,即TS算法、TS.OA竹法和MPSA—GA算法。 Ts箨法足。种通过时:维芯片摸救罔像的边缘幅度图像抽样术进行阁像J嗄 眦f内快速钟=法。筇法通过设定搜索步K、提圾抽样序列,能够州时碱少挫索过frtl

和川火计算的上耋钾:量。算法采州两阶段搜索簸略,解决了芯片l鞫像存n:的旋转问
题,保ilF了lK眦精度。兑1 L剥削SSDA算法进行了优化,使得该算法运行时闽进

‘步减小。该3ItU_,运算简巾,特别通合硬件实现。诚验发I刿陔算法能够满足系统

的灾时陀和定位精度(±4pro)的要求.抗噪能力较强.jI仃fH强f门∞棒一盹。
TS-GA辣法除了干Jj瑚TS强法对芯片谈皈阳像进行坝处州外,lriTi rg还利删遗
化馆江的“=趟协搜索目【制,能够迅速收敛剑令局近似山量优钟,从10J迎‘步减少了 f圯刚过wf门iI"釜。,i{‘m此J,;fi;tl J:-』j八十^咖l哇舭川、*.找…H怀子l矧像的#f蛳伊 彬及旋转『f:!J业,试验表『列该竹法满足系统旧实时-比1 J*I膻_露求。‘丈阿l:IIf Jj耕蜘

熔铜炉

http://www.txjm-zj.com/

m[目科学院酬宄’{院坝l,|仑文

摘簦

J嘎托H:节}£}J0。较多.所以眩钟=“;要性J.TS竹浊,¨jE采_L}』”确座?陀搜索镶Ⅲ*. 使jon:以J心眦的情况r。口J以通过再次搜索找到H十,ji。返也址法竹法被逃州f一1.璎
原I*l,也就址晓町以mTS盼法火州的情况r门删嘎铮}上逊,亍.次{受索确定H怀

MPSA—GA竹泌足^:分"i了多分辨率塔形结构掉泄:(MPSA)和J。£』。遗化盯 浊|1{J㈥f941 st4f{『,'方法n勺.t,15+fill',{:.仃帆的绌合了这两利一力’;』i的优点提…n0种¥2i#J-队

速JJ【;州钎泄;,试验太叫小17法能仃效降低儿州时|1fJ。虽然浚卵:浊“刈个m曲金丝
球蚪目“门|冬Jf黎U!别系统设小小如前两种锥浊.们它为肝两种竹浊的"致提"!丁席 _i,”¨J}仃定n0 J衄川价位,H此找仃J也作了简要介绍。 破肝.通过埘}}通I村像的f几蚍定伊试验时一.种订池进行了检验.结粜&{y_|芎r
浊j L仃fM曲ifn通用州:和{,L噪声能/』,口』.以推』』越¨JJ’JL他炎似场介。

此外,为了验证以f:茆f』、.九:Windows98 f:利肘Visual C¨6 0措建了秤种 竹浊f门测试’卜台,沦文-}t也做了简要介绍。试验cf-州剑的,球片J刮像均为令fI动金
蝗j:}{烬机实际I.作时拍摄的刚像,

灭键词:个n动金丝球蚪{jJL直力阁均衡rf-位滤波边缘检测f錾4像jJi眦

巾;q,f:l-学院研Kt院顽I‘论之

ABSTRACT

ABSTRACT

"File

fnlb

atttomatic gold、、ire bonder is



nloderll micro—electronic wrapping
as

equipment that ntilizes interdisciplinary technologies such

title lnechanics.alllO
so 011

control,image recognition,optics,u Jtrasonic heat-pressing sealing and

It is

nlainly applied to bond the chip pad with the lead?-frame in rite post-wrapper process

of integrate circuit manufacture.

Works that should be done here is

to

develop file image recognition software tot

tile fillly atitoatatic gold wire bonder,and tile following researches and experiments
are

conducted、 First,the working principle of the fidly autolnatic gold wire bonder is introduced,

two schemes that

can

be nsed,that is.the image coinputer processing system and the
tile latter
one

softare
according

image processing system,are analyzed,attd
to

is adopted

the demands of

otlr

research
are

Second,some digital image pre-processing techniques

provided,and

n、O are

image enhancing techniques,the gray histogram trimming and tile median filter

discussed Contrast experiments

are

conducted

on

real chip images to check effects of

行~e usually nsed median filtel operator,that is Roberts operator.Sobel operator.

Prewitt operator,Krisch operator and Laplacian operator Experimental restilts sllo~x
that the Roberts operator is to
our

choice
on

Third,some commonly used fast image matching algorithm based
matching
are

gra3

discussed,including Si vnilarily

FFT algorithln,Mtfltitttde Detection

Sorting Relational Pagoda
pointed

algorithln,Sequential

algorithm,Multiresohition
are

Strttctnre algorithm and Genetic algorithm Their strong and weak points
out

by experiments and discipline analysis It is demonstrated that all those algorithms

do not satisfy the real time demand(<25ms/line)of the image recognition system tot the fully automatic gold wire bonder.and the first four algo打thins can’t meet the

matching precision demand of the chip image that has
too



rotating degree from-7。to

7‘1

Next,two algorithms that meet the real time demand of the system and algofitlun that ha、e application,,akie algorithm and MPSA—GA algorithm TS algorithm is


one

are

proposed.that is TS algorithm.TS—GA

fast algorillnn based

on I、、0

dilnensions template salnpling In

lhe algorithm tile search step and sanple sequence

ate set to

l-educe tile computational

熔铜炉

http://www.txjm-zj.com/

列科学院研究生院顾t|仑史

ABSTRAfT

complexity

Tile algorithm is broken into two search pans,which settles down the

problem of target subimage rotating and guarantee to find the matching positions precisely

1:urtbennore.SSDA algorithm

is utilized

to

reduce lhe compulaliona_l

complexity of tile algorithtn implementation

Tile simplicit2,of the algoritlnn thcilitates its harduare

Experiments show that tile real time demand(、-720ms)and precision
system
are

delnand(±49in)of tile
【o i101sc

mel well and tile algorithm i



robust and illlnl/lne

Besides tile preprocessing of the template image like TS,TS—GA exploits tile
global searching mechanism of the genetic algorithm to fasten tile convergence of the algorithm to tile sub—optimal solution to tile problem On this basis,a precisely

locating phase is introduced to fix the location and rotating degree of the optimal
target sub image in the
scene

image

Experiments show that the algorithm also

satisfies the demand of tile systeln

In fact,TS—GA is slower than TS due to tile

time-consuming precision matching step

However,the algorithm

carl

find the target due
to

f’or



second time

when

the first searching step missed tile target
As such,this algorithm

its

non-deterministic searching strategF

is chosen to be the

alternative to TS when it misses tile target

MPSA—GA is based algorithm
carl

On

MPSA and GA,experimental results demonstrate that tile
to some

re&me matching time
on

degree As tile first algorithm、 ̄e tllought
Here,、 ̄e also gl、7e


otlt,it has elucidating influence brief introduction
to

tile above two algorithms

it
are

At last,the generalization and the anti—noise ability of these three algorithms

tested

using

an

ordinary

image,and the experimental

resuhs show that
can

these
to

algorithms meet those demands well;therefore,those algorithms other application too All the experiments
are

be generalized

conducted

Oil

tile testing platfbrm we developed

on

Windows98

operating system using Visual C++6.0.which is also introdnced briefly.in

this paper,and the chip images used,iu exgedments瓠e taken fmm t1.xe扎lIy autom.atic gold wire bonder
011

line

Key lIords:drily automatic gold wire bonder

histogram equalization image matching

median filter

edge detection

中图科学院研究生院硕士论文

第一章引击

第一章
1.1课题研究背景

引言

全自动金丝球焊机是集精密机械、自动控制、图像识别、光学、超声波热胝

焊接等领域于啼K的现代化高技术微电子封筏设备。丰要JH于集成电路制造后T 序【|I芯片焊盘与外框架问引线的焊接。
所谓封装是指安装半导体集成电路芯片所f{i的外壳。它不仪起着安放、同定、

密封、保护芯片和增强电热性能的作用,而且还是沟通芯片内部世屏与外部电路

的桥梁一芯片上的焊盘用导线连接到封装外壳的引脚上,这些引脚又通过印制板
上的导线与其他器件建立连接。因此,封装对集成电路起着重要的作用。 封装设备的发展与芯片技术的发展是相辅相成的。新一代Ic的出现常常要 求有额的封装形式,而封装形式的进步又将反过来促成芯片技术向前发展。
自从1958年美国德克萨斯公司试制成功世界上第一块焦成电路起,40余年

来世界Ic产业经历了小规模、中规模、大规模、超大规模和特大规模集成电路 的发展阶段。单块半导体硅晶片上集成的元器件数日越来越多,集成电路的功能 和速度飞速提高,电子产品~直朝着便携式『,j、型化,网络化和多媒体方向发展,
这种市场需求对电路组装技术提出了两点主要要求:其一是单位体积内信息的提

高(高密度化):其二是单位时间内处理速度的提高(高速化)。为了进一步满足 这些要求,提高电路组装的功能密度便成为促进微电子封装技术发展的重要因
素。

与此对应,芯片的封装技术也经历了几代变迁,从DiP(Dual
QFP(Quad FlatPackage).PGA、BGA(Ball Package或Chip
Scale Grid Array
Chip

In.1ine Package)、

Package)到CSP(Chip

Size

Package),再到MCM(Multi

Model),技术指标’代比

…代先进,芯片面积与封装面积之比越来趣接近于1,适用频率越来越高,耐温 性能越来越好,引脚数越来越多,引脚间距越来越小,重量越来越小,可靠性越
来越高,使用更加方便等等。

集成电路后封装,一般是从对完成制芯王艺的晶圆片进行测试开始,经过减 薄、清洗、划片、粘片、键台、塑封、电镀、印字、切筋成型,到器件最终编带
包装入库的整个工艺过程,中间要经过十多道工序,涉及二十多种设备。随着芯

片引脚数的增多,引脚问距不断减小,芯片上焊盘到外框架的连接越来越硝难,
从而使集成电路的键台环节成为后封装设备自动化中的瓶颈。 要提高键合环节的精度和效率,必须从改进机械系统、电控系统以及提高自 动图像定位系统的精度和效率这三方面入手。本课题以研究图像识别定位算法为 n标,开发了全自动金丝球焊机r{t的图像识别定位系统软件,以提高键台环节的

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生疏硕£论文

鼐一章引高

精度和效率。

1.2课题研究的意义
近几年来,我国电子工业迅猛发展,但总体上我国的电子T业雉础设施和制
造能力还远远落后于世界发达国家。据推算,我国每增10亿块的lc上寸装能/J. 需要进口约500万美冗的设备。而我国在2000年的半导体器件产量就已经达到

218138亿块。
集成电路后封装设备在集成电路制造业是必不可少的。然而口前.像共晶粘 片机和全自动金丝球焊机等核心设备仍需依赖进口。因此发展我国自己的微电子 产业,扣‘破对发达国家的技术依赖,加快半导体封装设备的国产化进程势在必行。

我国已能自主生产金丝球焊机,但尚未实现自动焊接。采用手动焊接,对焊
接人员依赖较大,难以保证焊接精度,因而工艺水平不高,生产效率低,不能满 足现代化大生产线的需求。因此只有实现金丝球焊机的自动化焊接才能大规模提
高产能。

图像识别技术是实现自动化的关键技术之一。图像识别是一个把未知图像与

已知图像联系起来的过程。对一个复杂的识别系统来说,它的内部常同时存在着
多种输入和其它知识共存的表达形式。识别是把输入的未知图像与系统记忆的幽

像进行结合,发现其联系的过程。匹配算法就是用来建立这些联系的一利t技术。
目前,人们提出的图像匹配算法可以分为四大类型:关系结构匹配方法、神 经网络匹配方法、基于特征的匹配方法和基于灰度的匹配方法。但是现有的算法

并不能满足仝自动金丝球焊机中的实时处理要求,因此,必须给出一年叶嗵用于实
时处理的新方法。

1.3课题主要研究内容
全自动金丝球焊机主要由三大系统组成:机械分系统、控制分系统、图像识 别分系统。其中图像识别分系统(PRS)主要目的是片J来自动判识芯片上每个焊
盘(pad)的绝对位置。 全自动金丝球焊机对图像定位系统提出了以下要求: 1.精度要求。由于焊接的精度要求高达±4p.m,所以定位结果直接影响着
焊接的精度。

2.速度要求。定位的快慢很明显的影响设备的T作效率,闭此时算法要求 比较高,特别是在定位有旋转角度(一7。~+70)的芯片图像时更是如此。 3.适庶性要求。对十不同的材料表面、框架氧化程度和光照条佴都应有较

中圉科学院研究生院硕七论文

第一章引矗

高的识别率。

根据以上要求采用模板匹配的方法对芯片进行定位。论文从这三点要求出 发,对现有的图像匹配算法进行了比较研究,针对当前算法判识速度慢,难以满
足系统要求的缺点,进行了改进,设计了三种改进算法: MPSA.GA幽像匹配 算法、摹于模板抽样(TS)的图像匹配算法和基于TS.GA的图像匹配算法。其 -1一后两种算法在满足系统精度要求、适应性要求的同时,大大提高丁系统的T作
效率。

为了对各种算法进行统一‘的试验对比,从中筛选最优算法。我们构建了全自 动金丝球焊机图像定位软件开发测试平台。在算法实现以及试验平台的构建的过 程中,充分利心了面向对象的程序设计思想,增强了软件可重用和可维护性,为 以后的研究丁作奠定了基础,并且为软件的扩充提供了保障。

1.4论文总体结构
全文共分五章。以上引言部分介绍了本文的相关研究背景、国内外发展现状 以及面临的问题,概述了本文的主要研究内容。第二章首先简要介绍了全自动金 丝球焊机的工作原理,然后详细介绍了图像定位系统的基本原理,以及软、硬件 的组成。第三章针对第五章的图像匹配算法对芯片模板图像的处理要求介绍了几

种常用的图像处理技术,并进行了试验对比分析,选择了适合于本课题的算法。
第四章对现有的图像匹配算法的优缺点进行了对比试验分析,为算法改进提供了 重要的思路。第五章在上一章的基础上提出了三种改进算法,并时其进行了试验 比较,分析了每种算法的优缺点,并推广了其适用场合。在结束语【}f对所作的T 作进行了总结,并对今后的工作进行了展望。

熔铜炉

http://www.txjm-zj.com/

中陶科学院研究生院硕士论文

第二章垒自动金丝球焯机图像证ljjIl系统

第二章全自动金丝球焊机图像识别系统
本章主要内容:

I.介绍了仝自动金丝球焊机的丁作原理。

2.介绍了两种计算机图像处理系统,即图像计算机处理系统和软件型图像
处理系统,并讨论了两种方案对本系统的可行性。 3.介绍了图像识别系统的软硬件构成。
4.介绍了幽像识别软件试验平台的构成。

2.1全自动金丝球焊机概述
2.1.1工作原理 全自动金丝球焊机的工作过程是利用高压打火器将直径20~30jam的金丝
(Bond

wires)烧成球,然后通过超声波热压焊接方法将其焊接到芯片(Chip)

的电路引出端的焊盘(Pad)上,在系统XYZ三维运动控制下拉出设定的金丝线
形,并将金丝焊接到引脚框架上(Lead frame)上,拉断金丝完成一条电路引线 的焊接过程。如此往复,直到整个iC电路封装引脚全部焊接完毕,完成一只Ic 电路的焊接过程。图2.I所示的是lc电路连接示意图。

图2.I芯片焊接示意图

超声波热压焊接是一种嗣『f』超声波频率的机械震动能量连接同种或异种材

质的特殊焊接_T艺。在超声波焊接系统中,‘散由换能器、聚能器、耦台杆和J:
声栈构成声学系统。声学系统【}j各个组兀的自振频率设计成同个频率,”"iN卢 波发牛器的振荡电流频率与其。致时,系统即产生谐振。并向焊接体输出弹性篪

中国科学院研究生院硕士论文

第二章全自动仓丝球焊机删像母5别系统

动能,配合静压力将机械震动能转换为T件问的摩擦功、变形能和随之而产牛的 温升.实现焊接体在词态下的连接。 将机械震动能量转变为工件问的摩擦功、变形能以及随后有限的温升,是在 母材不发生熔化的情况下实现的,所阻超声波焊接是…种吲态焊接方法,不会对 半导体材料引起高温污染及损伤.非常适台于微电子器件的封装T艺。 2.I.2控制系统结构 全自动金丝球焊机的控制系统结构如图2-2所示,它是由丰控计算机、多轴

运动控制器、倒服电机、焊接头、摄像三L、无闪烁灯源、图像卡以及x.Y平台
等组成。摄像头取得的视频信号传到图像卡,经计算机处理,得到芯片焊盘的绝 对位置挫标,然后发信号给运动控制器,控制器再驱动伺服电机,调整X.Y平 台,将芯片上的某一焊盘对准z轴(焊接头)正下方.之后焊接头下落到预定高

度进行焊接.这样系统形成了一个闭环控制。可见,在整个控制系统小,图像处
理起着重要作用,所有的反馈量都是经图像处理后得出的。

I/0控制

/l———』 控制器\r—],.上位工控机

数字信号


驱动器


伺服电机

焊头

X-Y平台

工作平台

图2-2全自动金丝球焊机控制系统结构

2.2计算机图像处理系统
个汁算机幽像处理系统通常包括硬件环境和软件支持能力两方面。硬件 环境’般分为两大类型,第1种类型如图2-3(a)所示,在汁算机一lI插入个图像

熔铜炉

http://www.txjm-zj.com/

中国科学脘研究生疏硕上论文

第二一章全自动盒丝球焊机图缘站{州系统

采集卡,幽像采集卡畔,有利新图像存储器等专用硬件.而处理下作由计算机利jlj

相应的软件完成,这种类型简称为软件型图像处理系统.其处理速度完全取决一』:
计算机CPU的运算速度。另一种类型如图2-3(b)所示,系统利川专川硬件进行

图像处坪.向丰机仅发布命令或进行小部分处理,幽像硬件处婵可以脱机进行。
冈此这‘类可称为图像计算机型图像处理系统。以下分别就这两大类型系统针对
本课题的可行性进行分析介绍。

臣D
(b)图像计算机

图2.3两类计算机图像处理系统 (a)软件型系统

2.2.1图像计算机处理系统
在对图像处理系统的速度要求很高时,如处理跟踪军事同标或从卫星大量图 像的原始数据时,都要求实时处理或准实时处理。准实时处理就是要求处理速度 和电视显示速度一样快,大约20~40ms处理完一幅图像。虽然处理速度仍不能 满足真正实时跟踪的要求,但已能达到大多数应用的要求。为了解决实时处理问 题,常用专用硬件解决其最慢的处理环节。如我国进口韩国型号为TWB--540H

的全自动佥丝球焊机,采用一款低档的主机,CPU仅为80386,fEl其主要处理环
节则是由~块专用的图像处理硬件税构成的。并且采用了先进的高速DSP完成

了图像的预处理以及识别定位工作,主机只作为发布命令时使片j,发布命令后, 实际上硬件可以脱机处理,大大减轻了主机的负担。 此方案具有很强的处理速度优势。但也存在一定的缺点,开发图像计算机的
成本高,开发周期长,开发难度大,不利于产品快速投放市场。这对开发周期短 的项月也是一个致命的弱点。

2,2.2软件型图像处理系统
软件图像处理系统中图像存储体部分是设计的难点,从图2-3(a)可以看出, 图像存储体有三个接口,而且这三个接口时序都不一致。一般电视摄像机输入近 似100ns/像冗,这个速度要求存储芯片选用50ns的品种,而通』『JT控计‘算机的 存储嚣很难达到这样快的CPU控制存取速度。图像存储器输出刘显示器常J|!{!速 率也是100ns,而且是连续不断的传送数据显示。图像存储器的第三端与汁算机

中国科学院研究生院硕士论文

第二章仝自动仓丝球焊机酗像识别系统

相连,由CPU随机存取,一般来讲存取速度较慢。因此设计一个三端的图像存

储体是硬件环境的主要问题。幸运的是现在许多计算机厂商生产了配合Pc级计
算机的通用插件,通常称之为图像采集卡.它包括了AID,DtA,幽像存储器和

-些操作用的查找表。许多处理变换可朋查表的方式提高运算速皮。
由于图像L}i每个像元都由主机取出进行处理,所以对整幅图像的处理速度完

全依赖于计算机执行软件的速度。一般来讲,都希望处理速度快一些。那么可以 从两方面来提供处理速度。…是提高计算机本身的硬件指标,尽量选川处弹速度
快的计算机。一-是优化图像处理算法,开发实j{j性强的快速算法。 方面是可以获得较快的整幅图像的处理速度的。 ‘般通过这两

这种系统的建立只需赌买一块通用图像采集卡.便能迅速展开工作,大大
缩短了开发周期,节约了生产成本,开发的成功率也很高。但这种系统往往只对

静态图像或处理数量不多的图像的应用领域较适合。

2.3全自动金丝球焊机图像识别系统
图像计算机处理系统虽然能取得很好的处理速度,但图像计算机’般是针对

某一应用场合开发的,专用性较强。目前,市场上没有适合于全自动金丝球焊机
图像识别系统的专用图像计算机。这样开发周期势必拉长,不利于产品的快速上 市。另外专用图像计算机的开发难度很大,需要专业的图像处理软硬件开发人员。 所以,这个方案不可取。

虽然软件图像处理系统的实时性不高,但开发简单,成功率高。我们可以选
用高档主机和开发先进的快速算法来称补处理速度的不足。另外有鉴于该系统开 发周期短、资金少等特点。权衡利弊我们采用了软件图像处理系统方案。

2.3。I硬件组成 全自动金丝球焊机图像识别系统硬件构成如图2-4所示,主要由光学及照明 系统、图像采集系统、数据接口系统组成。
由于每批60只芯片按照10行6列分布在高温焊接平台上,每只芯片都需要

进行图像识别定位,因此无闪烁照明灯源、光路和CCD图像采集传感器都安装
在x.Y工作平台上,与焊头一起运动。工作时先根据芯片间距计算下‘‘芯片的 粗略位置,在到达预定位置后再进行图像抓取。

图像采集卡采用了Euresys公司的Pico]02,它的图象采集速度快。可以缩短
图像识别的整体时问。在软件识别出芯片焊盘的绝对位置后,要立即把数据传送

给运动控制器。由于运动控制器与主机是通过[SA总线连接的,数据传输速度比
较慢.为了加快传输速度,采用了高速的双口数据传输方式把数据迅速送给运动 控制器,以操纵焊头进行焊接。

熔铜炉

http://www.txjm-zj.com/

陶科学院研究生院硕七I仑文

莉.章仝闩动台蝗球弹帆削像0I)}J最筑

J15I:-4坎刊f4bkI斟

2.3.2软件分析
全ff动金缝球焊机蚓像订{别系统的{i曼r}的越测醚芯片I:符个焊融发外r』l

脚框架的精确似骨,提供给好接机构‘丈蚬焊接。软什n:系统t…I仃’译足辑重n0地
似+神i系统硬件确定的情况r,它决定臂U{别速度和U:别精瞍。
精度要求:¨{十芯”焊虢向糨约为90um×90 am,而金煌尾{夺绎岛胍烧球

Ji端阿ft达到50~60um,然肝通过焊接火的超声热爪焊,球端爪缩变j肜,吱g小 接触ffif积达剑厂70~80um。J州时T艺要求芯』l焊接肝,焊。^剑焊僦的边距人_F
5urn。通过以}:分析,堂求芯』f定似精度为±4pro。芯』{经过光学系统、CCD

处理肝转换为汁弹机q r的吲像.H像的每个像素对心的实际尺、r为29in,所以 nH像定位r|】要求误并为±2像素;, 述皮要求:焊接指标要求为4线/s,除去芯"传送刊焊头移动rt'j'fHJ,J尖际焊
接迷嫂为1 20ms/线。j:要时川分配为pU部分:焊艇U{别定能、焊船焊接、绒形

{t线、?川脚框架焊接。l川I^i-s,6i是…焊接丁岂决定的,苁约需95ms,圳此.
嘤水焊微U!别定位时|HJ,1i能超过25msi}£。

可见,为J7实现玳偷mi可靶的焊接,需要一个柑们moi速∥』H像U:别软rf是
j}

。共5,J:l‘焊烈‘十¨对十芯H术说比较小,成像磺‘拇女手,人叭也f}f}小埸辨泌,

对'十l=7:机求说)J{I』ljl难J!:{:业人。fil垃.对每平1-芯”lnj击焊涨十¨对.占H n0们芹足吲逆
n0,圳I阿可以H宅人丁?Ji甘删定…烬黼十¨对1‘芯¨O'tJ州对f■簧.然f^,fl川J|冬|傈以

c}二I司科举院研究生院母l{=论芷

第.簪个门动盒链球焊帆矧像识别系统

别软干1:确定.卷"的绝对付胃,进『nj汁剪…焊瑚‘的绝对似芹。这样,将对博黜的定 似疏化为对芯”的定位,一方m,可以fK证较r西的Ij{别准确半,另~方而.H爱
U{别…芯片眦可以定化芯¨卜所f『焊触的似簧,恻m提商r U{别效率。 嘤^『1定.卷¨的绝对似钭,需嘤I刽像旺配技术,我们将nj讹【JU—I}细介绍、.这

il【允介绍一卜软件的组成√【!也禽i人模块:模板训劫、模块、劁像U!别梭块f¨投

靠t:庠史¨模块。』川?,f斜像U!别模块(!土j;lH像的采架、颅处唧、模扳旺配等。幔
托乏训约;f墓块也十ll模扳的选扦、m处用、焊船m.出"rI,荆对fi背的测髓等。数捌J苹 模块ii爱(!土女}存储扦种芯JJ-的馍扳fj息、,』f线州表、焊稍干¨对十芯』{的毕畅i等数 j:ll:。再模块?rI成及数j];|:流}冬1如蚓2-5所示。

H 2-5图像口删系统软件构成示意圈

2.3.3识别软件试验平台
(t!-Ti:发全|,i动金缝球焊机H像U{别软什过程r}t,搭建一个合理的试验、Ii台是

f‘分必复的。它4i仪为各f"t一㈥像处婵U{别算法提供r一个统一的试验环境,使小 M的弹泫i!}行比较jI仃实际意义,In』几可以快速优化、筛选符利t算法组合,人幅 f!:{:提r4厂丌发速瞍,为开发新的快速算泓i奠定J,“物质”摧圳。卜所简曼介绍一
}?试验”t仃的类蚓。 亿试彰j、fi行的丌发过秤l J r创建的炎i‘茛仃:俐像阮I吲类、l冬{像聚集炎、}铡像

钟:上炎、蚓像炎、蚓像处胛钟江类、}{}|像眄配算浊类、GA—TS炎、MPSA—GA、 TS炎等。卜晰介绍一卜以』:件炎的JJJ能、川途;'2t1¨1'3之M的父系。 (1)旧像视H炎
i:复川十丝示j|IH像卜采集的场艟H像、横板剖像、肚

熔铜炉

http://www.txjm-zj.com/

t,旧利学院讲究牛院硕士i仑卫

幕.节争门动盒皑球鹊!机阿像0 5”lI最统

配结粜等。 (2)蚓像采集类封装r蚓像采集扣的驱动棵序,通过此类可拎制采馕k

的Tf'r:lX态完成图像的采集传输JD能。H仃H像朵促类传入㈦像数{ll:fljH像观H
楚_‘f:『皂4i断的姓示H像,即蚓像聚仉炎5』㈧像馄罔炎仃州1 nj的乍命州!f}j+所以蚓 像采集炎利H像视l蚓类我们采川J’组合天系。 (3)H像算法炎
父类。

{m象J’H像处卿、H像匹配算法的萸rl-作为这两个炎的

(4)蚓像类保存J’f刮像数{;I『:指针以^乏蚓像的l留瞍"赶fl:5:。,
(5)模板H像坝处婵搏法炎

{:爱究成对味始吲像的坝处理』J』能,提r码劁

像的质碾.像矧像的狄度校IR蚓像的滤波等算法部被封被n:本炎¨|t。 (6)吲像眄配算法炎
方法。

作为择种眄配算法的堆类为他们提供J’统一的接u

(7)MPSA.GA类、TS—GA类利TS类这i个炎是我们改进的i种1矧像匹 配算浊,le【}I历两种搏法皱终提1;_}c给全r1动金坦球焊继ii挖软件使ffJ的弹法,也 枕足奉课题所丌发的识别软什的核心部分。

中国科学疏研究生院硕士论文

第二章令自动金丝球焊帆图像Ul别系统

2.4小结

全自动金丝球焊机是种微电子专用设备,图像识别系统是其重要组成部
分,基于研制周期较短、资金少等特点.我们选择了软件型图像处理系统方案。 网此,开发快速有效的算法的任务显得尤为重要。为此我们利川了面向对象的思 想措建了软件试验平台,并对软件进行了模块化的规划和设计.为算法的设计改
进作好了准备T作。

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

第三章芯片图像预处理算泣试验与分析

第三章芯片图像预处理算法试验与分析
本章主要内容;

I.结合具体试验讨论了灰度直方图修整和I{l值滤波两种图像增强技术,并 通过试验选择了直方图均衡及5x 5-f‘字形窗口的『fI值滤波的方法对芯片图像进
行了预处理。

2.介绍了Roberts边缘算子、Sobel边缘算子、Prewitt边缘算子、Krisch边 缘算子及Laplacian边缘算子。并通过实际芯片图像的对比试验选择了Roberts 边缘算子作为本文的边缘提取方法。

3.1芯片图像增强
图像增强的目的是改善图像的视觉效果,但它不考虑图像降质的原因(追究 图像降质原因是属于图像复原的范畴,这里不作讨论),只将图像中感兴趣的区 域(ROI)有选择的突出.而衰减其次要信息.将其转换成更适合于人或机器进 行处理的形式。 图像增强基本上可以分为空间域和频域处理两大方法。空间域处理是在原图 像上直接进行数据运算。它又分为两类.一类是在与像素邻域有关空间域进行, 称为局部运算,如空间域卷积运算。另一类是对图像作逐点运算,称为点运算。 处理可以是线性或非线性的,如用指数、对数、比值、黑白到彩色的变化等。频 域处理是在图像的傅立叶变换域上进行修改,增强我们感兴趣的频率分量,然后 修改后的傅立叶变换值再作傅立叶反变换.便得到增强的图像。由于本课题采川 图像的灰度变换及平滑来增强图像,所以本章对频域处理方法不作介绍。 3.1.1灰度直方图修整 最常见的图像缺陷是全幅图像偏暗或偏亮,亮度范围不足或由非线性因素造 成的对比度不足,而修正这种不足的常用方法之一是修改图像的直方图。直方幽 具有一幅图像灰度分布的总体统计特性.是图像处理中最常用的统计图之‘一。 直方图是灰度值的函数.描述的是图像中具有该灰度值的像素的个数,其横 举标表示的是像素的灰度级别,纵坐标是该灰度出现的频数(像素的个数)。图 3.1给出了一幅图像及其直方图。 直方图还有另外一种方式的定义:假设有一幅由函数D(x,y)所定义的连续 幽像,它平滑的从中心的高灰度级变化到边缘的低灰度级。我们可以选择某‘灰

中国科学院研究生院硕士沦文

第三章芯片图像颊处理箨法试验与分析

皮级D,,然后定义一条轮廓线,该轮廓线联接了所有具有灰度级D.的点。所得 的轮廓线形成了包围灰度级大于等于D,的区域的封闭曲线。如蹦3-2所示,幽像 -|J有‘条灰度级为D,的轮廓线.在更高的灰度级D,处还有第二条轮廓线。设A, 是第。条轮廓线所包围的区域的面积,A2是第二条轮廓线所包围的面车J!。将?幅 连续图像砗l被具有灰度级D的所有轮廓线所包围的面积称为该图像的阈值面移{
函数A(D)。直方图可定义为:

删=l。ira盟型型一面d
、’A,】

DAD)D(A 扣、7

l、 (3.” r1

由式(3一I)可得出结论:一幅连续图像的直方图是其面秋函数的导数的负

数。负号的出现是由于随着D的增加一倒在减小。如果将图像看成?个二维随
机变量,则面积函数相当于其累积分布函数,而灰度直方圈相当于其概率密度函 数。 对于离散函数,我们固定AD为l,则(3,1)变为:
—H(D)=一(D)一爿(D+1)
‘3-2、

(8)图像

(b)直方图

图3-l图像及其直方图

直方图修整就是通过灰度映射函数s=rir],将原直方图尸,(r)变换成希望的 直疗图只(s)。s=丌r】必须满足以下四个条件:
f.在r∈【o’iJ内,5=玎叫单增; 2.J和,是一一对麻的:

3.对于r∈【03】,有s=7、…∈【03】:
l:

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院顾士论文

第三章芯片图像预处理算法试验与分析

4,反变换r=T。Is】满足条件1~3。 由概率论知

只(s):只(r)车 珊

(3-3)

图3-2图像直方图轮廓线示意图

下面我们介绍一下本课题中用到的灰度直方图修整技术一灰度直方图均衡。 灰度直方图均衡就是把给定的的图像直方图的分布改变成均匀分布。图3-3是实 际采集到的芯片图像经过直方图均衡处理的结果,直观的看,图像ff,j对比度得到 了增强。实际它上合并了~些灰度值,牺牲了一定的细节。要进行直方图均衡就 意味着只(s)=1,s∈【O,I】。由公式(3-2)可得:

幽2焉=竿州毋
从而
55

协。,

7’(7)2

jc(”)dw(3-5)

即T(r)为分布累积函数。

在数字图像处理中,宜方图均衡的离散公式为:

以‘7'c‘,。砉P c一,2妻;÷
其叶T
0≤‘sI,0≤s^≤l,k=0,1…,、L—I。

。,一。,

中国科学院研究生院硕士论文

第三章芯片图像预处理算法试骑与分析

由公式(3-6)计算出的受需要根据良好的间隔归入量化等级,即 ,t=h(L—1)] 其中【+1表示四舍五入取整。 需要注意的是灰度直方图均衡是灰度直方图修整的‘个特例,即修整后的灰 度概率密度均匀分布(只(一)=1)。但是由十灰度离散化,均衡化的直方图只是 近似均匀的直方图分布。均衡化的图像动态范围扩大了,但其本质是扩大了量化 层间隔,也就是说合并了~些灰度级.而非量化层的数日,这样均衡化后的级数 减少了.就有可能出现伪轮廓。


3-7、

(a)原始芯片图像

(b)苴方图均衡处理效果崮

(c)芯片图像直方倒

(d)处理后芯片图像盘方幽

图3-3芯片图像灰度直方图均衡效果示意圈

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕j:论文

第三章芯片圈像预处理算法试验与分析

3.1.2芯片图像中值滤波 l}j值滤波是一种非线性信号处理方法,与之对应的rlJ值滤波器■然也是’利r 非线性滤波器。它是1971年由J.W+Jukey首先提出的’种应川在‘维信号处理技 术(时问序列分析)中的滤波方法.后来被二维图像信号处理技术所引川。实际J. 也是‘’种图像的局部平均平滑技术。它对脉冲干扰和椒盐噪声的抑制效果较好, 更重要的是它在抑制噪声的同时保持了边缘的清晰,这正是我们所需要的,冈为 在对模板的预处理中我们要对模扳图像的边缘进行提取,在后面的章节I}l将会讲
到。

中值滤波的思想是以局部域中的巾位数(巾值)作为滤波器的输出灰度。对 于二维图像信号{Ⅳ.,『f,J∈Jv},,中值滤波器定义为 r,2MedianX,,2Median{X,+~+,I r,J∈爿} 其中,Ⅳ为自然数集.A为截取图像数据的窗口。 考虑到一般图像在二维方向上具有相关性,因此,活动窗口一般选为二维窗
口(如3x 3、5×5或7×7等)。窗口的形状常有的有方形、卜字形、圆形和x
f1一R)

形等。图3-4给出了常用的几种窗口形状和大小。

图314常用中值滤波窗口形状与大小

在进行滤波时需要注意的是具有丰富的尖、顶、角等几何特征的图像,最好 不用中值滤波做图像的平滑,如果不可避免则一般采用十字形窗E1,窗口的大小 最好不要超过图像中有效物体的尺寸。否则,滤波后会丢失大量细小的几何特征。 另外根据Tyan论述的中值滤波边缘保护特性的结论可知,滤波窗E1的点数要为
奇数。

中值滤波还具有良好的消噪声特性。设图像X,,的均值为一、方差为O-2、 独立同分布的随机变量』,,(』)和f(x)分别是X的概率分布函数和概率密度函
数,在大样本的情况下,由r{一心极限定理可知

I.J近似服从正态分布Ar(』f.盯2/月);

中国科学院研究生院硕士论文

第三章芯片图像预处理算法试验与分析

2,Media”(x.,吐…,x。)近似服从~(m’,口2+),其巾m+为理论。I?值,满足

F(Ⅲ+)=j1,而仃2|=而I。
当选取n等于滤波窗口叶1点数时,如果,(r)对一是对称的,则有
m’=E[Median(xl,X2…,x。)】_E(x,)=,f

由参数估计理论可知Median(x,,x:…J.)是均值∥的极大似然估计量,冈此 也是∥的最佳方差估计量(渐进意义下)。事实上成立着更‘般的结果:中值是

分布中心最小绝对偏差估计量,即Minn.)z.-allt生:a=Median(x。x,J。)时达到
最小。

上述结果得到的一般结论是:对抑制具有冗长拖尾分布的噪声,巾值滤波效 果比较好。经过大量的对比试验我们发现用5×5十字形窗口滤波效果最适合于 本课题的芯片图像的滤波。图(3.5)是芯片图像滤波的效果图。

(a)原始芯片图像

(b)中值滤波后芯片图像

图3-5十字形窗口中值滤波效果图

3.2芯片图像边缘检测
图像的边缘信息无论是对人或对机器视觉来说都是非常重要的,边缘具有能 勾画出区域的形状,能被局部定义以及能传递大部分幽像信息等许多优点。对它 的分析既可以为图像的恢复、增强和重构提供理沦与方法.又可为图像特征的提

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

第三章芯片图像预处理算法试验与分析

取提供依据。 图像的边缘有方向和幅度两种特性。通常沿水平方向边缘变化平缓,而沿垂
直方向走向的象素变化剧烈,这种变化可能呈现阶跃型和房顶型。如图3-6所示。



/\L
(b)房顶掣

(a),阶跃型

图3.6灰度变化类型

这些变化分别对应景物中不同的物理状态。如阶跃型变化常常对应景物的深
度和反射界面,而房顶型变化则表现为表面法线方向的不连续性。如果一个像素

落在图像中某一个物体的边界上,那么它的邻域将成为灰度级的变化带。对这种 变化最有用的两个特征是灰度的变化率和方向.他们分别是以梯度向量的幅度和
方向来表示的。

边缘检测算子的作用是检查每个像素的领域并对灰度变化率进行量化,当然
也包括方向的确定。边缘检测的方法众多,下面介绍几种常用的边缘检测算子:
3.2.1

Roberts边缘检测算子
Roberts边缘检测算于是一种利用局部差分寻找边缘的算子。它由式(3-9)

给出:

g(x,y)=“√而一√了ii;1而]2+【√而一√7i_i了丽r}1



(3.9)

其中f(x,y)是具有整数像素坐标的输入图像。

在式(3-9)中平h-根的运算使该处理类似于在人类视觉系统中发生的过程,
因此经过Roberts边缘检测算子处理得到的边缘图像在视觉效果上比较接近于人

3.2.2

Sobel边缘检测算子

Sobel边缘检测算子是由两个卷积核形成的,~个是检测水平边缘的

[j1享j’],另一个是检测垂直边缘的j:{i{}。我们对图像小的每个像素
都要HJ这两个核做卷积,通常第…个卷移{核对水平边缘响应最大,而第二个卷私5

中国科学院研究生院硕士论文

第三章芯片图像预处理算法试验与分析

rrew,tt边缘检测算子是由[’’’1’11和『i i:j1构成,与使川sobel
+5 一




5 3



3 3

+ ‘,



3 3 3






5 5 5





——3——3




3 3 3


¨o o o o¨







3 3
3 5.

P. . . .L





”o o o o¨

+ 一

5 3 r.、 . 、. .L








3 3

+5{

o 0




1● ● ● J



+5+5 +5—3}
0 —3


一 +



一3
十 +


十 +

+5


一 一

3 3




一 +

5 5

5 5



P. . .L

1,‘,5

P. ,. L







3.1● ,● J

—. 。.L— , .L



5-)3

——3——3

3.2.5

Laplacian边缘检测算子

Laplacian边缘检测算子是不依赖于边缘方向的二阶微分算子,他是一个标量 fo


ol


而不是向量,具有旋转不变性,即各项同性,其算子为』l一4

J,与一一阶微

10
一2 —4 —4 —4 0 8 0 —2 —4 —4 —4



0j

分相比,二阶Laplacian算子对噪声更敏感,它使得噪声成分加强.在实际应川 中通常先进行平滑处理。也可以采用Gauss?Laplacian(LOG)算子,常用的LOG
—4 0 8 0 8 24 8

的算子为

—4 —4

——2—.4

——4—.4——2

3.2.6各种算子对芯片图像边缘检测效果对比试验 图3—7a是图3—3a经过了直方图均衡以及中值滤波处理后的芯片图像,图 3-7bcdef是经过边缘算子处理后的边缘幅度图像,可以看出Robert边缘算子的效 果较好,它勾画了一幅清晰的边缘幅度图像。另外,根据我们设计的图像匹配算 法的特点,埘模板图像的预处理是离线进行的,所以对时问没有过多的要求,这 里不冉对各个算法的时间作比较分析。

熔铜炉

http://www.txjm-zj.com/

【lJ国科学院研究生院硕士论文

第三章芯片图像预处理算法试验与分析

(a)经直方图均衡及中值滤波处理的芯片图像

(b)Roberts算子处理的图像

(c)Sobel算子处理的图像

(d)Prewitt算子处理的图像

(e)Prewitt算子处理的图像

(f)Laphcian算子处理的图像

图3.7各种边缘检测算子处理后的芯片图像效果幽

中周科学院研究生院硕士论文

第三章芯片图像预处理算法试验与分析

3.3小结
图像增强的方法很多,针对全自动金丝球焊中芯片图像的特点,通过对比试 验选择了中值滤波和直方图均衡这两种方法并做了详细的分析。首先对图像进行 q一值滤波,在保持边缘的同时有效的滤除了噪声的干扰,然后通过直方图均衡提 高了图像的对比度忽略了一些特别具体的、不稳定的细节(对抽样点的提取具有 干扰)。从而为后面的边缘检测提供了基础。实际上我们获得边缘幅度图像的几 的是从模板图像中提取抽样点,达到匹配过程减少计算量的效果,所以不需要对 芯片图像的边缘进行拟合。 需要指出的是由于我们对图像的预处理是针对芯片模板图像的,也就是说是 离线处理的,所用时间因素并不很重要,而主要强调的是处理效果,所以本章只 针对各种算法的处理效果进行对比,并没有在处理时问上作比较分析。

熔铜炉

http://www.txjm-zj.com/

中周科学院研究生院硕士论_丈

第四章传统图像匹配算法对芯片圈像定位试验与分析

第四章传统图像匹配算法对芯片图像定位试验与分析
本章主要内容:

1.分别介绍了关系结构匹配方法、神经阀络匹配方法、基十特征的匹配方 法和摹于灰度的匹配方法四大图像匹配算法。 2.详细介绍了摹于灰度的匹配方法巾的模板匹配方法的基本原理。 3.介绍了目前常用的传统快速模板匹配方法的基本原理,如FFT、幅度排 序相关算法、序贯相似检测算法(SSDA)、多辨率塔型结构算法(MPSA)、基 于遗传算法(GA)的快速搜索算法等。并结合全自动金丝球焊机l+J芯片图像特 点试验分析了上述算法的优缺点。

4.1图像匹配方法
认知是一个把未知与已知联系起来的过程。对一个复杂的视觉系统来说,它 的内部经常同时存在着多种输入和其它知识共存的表达形式。感知是把视觉输入 与事前已有表达结合的过程,而识别也需要建立或发现各种内部表达式之间的联 系。匹配就是建立这些联系的技术和过程。建立联系的目的是为了用已知解释未
知。

在机器识别事物的过程中,常需要把不同的传感器或同~传感器在不同的时 问,不同的成像条件下对同一景物的两幅或多幅图像在空间上对准.或根据已知 模式到另一幅图中寻找相应的模式,这叫做匹配。目前.人们提出的图像匹配算

法可以分为四大类型:关系结构匹配方法、神经网络匹配方法、基于特征的匹配
方法和基于灰度的匹配方法。 4.1.1关系结构匹配方法

所谓关系结构主要是指语义网络。这种方法把计算机中的模型同外部世界叶1 的物体或现象建立起对应关系,也就是利用图像的结构特征或关系特征之间的关

系,把物体和物体问的关系表示成结构,通过沿图中的弧作关联搜索,建立卧}j
结点之问的关系.借助语义网络、框架理论和图论方法寻求匹配问题的解决。进 一步讲,这种方法是人_T智能技术在图像匹配领域的应用,在这个意义上,景物

可用知识和规则来描述,利用知识和规则实质上是给景物赋予了…种解释,所以 这种方法也称为纂于解释的匹配。这种方法在实现时,为了减少计算量而使结构
与点之间关系的描述常常是不完全的,并且缺乏一种有效的衡量点集之问是否柏 同的手段。所以这种疗法的研究至令尚未取得突破性进展。

中国科学院研究生院硕士论文

第四章传统图像匹配算法对芯片望堡皇位试墼墨兰!堑

4.1.2神经网络匹配方法 由于神经网络的并行分布处理等特点,神经网络匹配方法理所“’然地引起了 人们的重视.利用神经网络进行图像匹配的基本方法是:首先利用某种特征提取

算法(也可以是神经网络算法)对图像进行预处理,并按要求提取一‘定数量的特征
点。然后根据构造的某种神经网络算法的要求,选取并输入网络需要的’些初始 状态,同时也将选取的特征点作为基本输入参数。接着启动神经网络算法的迭代

过程,可能还要有学习过程。最后给出迭代结果,并对其进行分析评价。神经网
络匹配方法的这种匹配过程有咀下致命缺陷:

f1)特征点的选取还无法自动实现,日前的研究仪限于‘些边缘棱角突出的
工件等的匹配识别试验等。 f2)网络需要的初始状态的选择,对网络迭代过程影响较大,选择不当还会 造成不收敛或陷于某一极值而不能自拔。

(3)特征提取所需的预处理,神经网络的学习和迭代过程都是计算代价比较
昂贵的过程。 由此可见,虽然神经网络匹配方法取得了一些初步进展,但由于收敛性、通 用性不够理想,还无法用于灰度变化平缓、特征不突出的图像匹配,与实用性和 实时性要求相差甚远,所以研究神经网络匹配算法目前对实时图像匹配还不具有 实际应用意义。 4.1.3基于特征的匹配方法

基于特征的匹配是首先提取反映图像重要信息的特征,而后以这些特征为模 型进行匹配。局部特征有点、边缘、线条和小的区域.全局特征包括多边形和称 为结构的复杂的图像内容描述。特征提取的结果是一个含有特征的表和对图像的 描述,每一个特征由一组属性表示’对属性的进一步描述包括边缘的定向和弧度,
边与线的长度和曲率,区域的大小等。除了局部特征的属性外,还用这些局部特

征之间的关系描述全局特征,这些关系可以是几何关系.例如两个柏邻的三角彤
之间的边,或两个边之间的距离;可以是辐射度量关系,例如灰度值差别,或两

个相邻区域之间的灰度值方差;或拓扑关系,例如一个特征受限于另--个特征。
人们一般提到的基于特征的匹配绝大多数都是指基于点、线和边缘的局部特征匹

配,而具有全局特征的匹配实质上是我们上面提到的关系结构匹配方法。 特征是图像内容最抽象的描述.与将要介绍的基于灰度的匹配方法相比,特 征相对于凡何图像和辐射度影响来说更不易变化,但特征提取方法的计算代价通
常较大,并且需要…些自由参数和事先按照经验选取的门槛值,因而不便于文时

应川。同时,在纹理较少的图像【基域提取的特征的密度通常比较稀少,使局部特 征的提取比较困难。另外,基于特征的匹配方法的相似性度量也比较复杂,往彳牛
要以特征属性、肩发式方法及门槛方法的结合来确定度量方法。尽管基于特征的

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

第四章传统圈像匹配算法对芯片倒像定位试验与分析

匹配方法有其自身的不足,但由于该方法业已取得了比较好的匹配效果,所以许 多人正在从事这方面的研究T作。

4.1.4基于灰度的匹配方法
基于灰度的匹配就是逐像素地把~个一定大小的实时场景酗像窗口的灰度

矩阵与先前选择的参考图像的所有可能的窗口灰度阵列按某种相似性度量方法
进行搜索比较的匹配方法.从理论上说就是采用图像相关技术。

图像相关技术近二十年来得到了迅猛发展,并形成了?门新的学科,由于它 与其它方法相比具有计算量小,易于硬件实现等优点,是当前应』}j研究ffl的丰流
方法。目前,这种方法已经取得了突破性进展。

围绕减少搜索空间和减少匹配时问的问题,人们相继提出了序贯辛Ij似性检测 算法(SSDA)、两级模板匹配算法、多辨率塔型结构算法(MPSA)、多子区域相 关匹配算法、基于局部熵差的图像匹配算法等各种快速匹配方法。嗣绕抗噪声干
扰和抗几何失真问题,人们相继提出了随机符号变化准则、不变矩等算法。同时.

人们对与提高匹配精度和匹配速度有关的各种问题,比如定位精度、噪声、灰度
电平偏差、量化误差等误差因素对匹配性能的影响,各种预处理技术等都进行了

比较系统的研究,有力地推进了图像相关技术的应用。

4.2模板匹配方法
模板匹配方法是一种基于灰度的匹配方法,它的原理简单,易于软硬件实现.
并且实时性较好,是当前研究最成熟应用最广泛的方法之一。

模板就是人工引导选择的一幅小图像,也就是所要识别的目标。模板匹配就
是在一幅大图像中搜寻目标,已知该图中有要找的目标,且该目标同模板有柑同 的尺寸、方向和图像,通过一定的算法可以在图中找到目标,确定其坐标位置。 如图4-J所示,图中有若干个目标,现在需要寻找…下有无十字形的图像。

若在被搜索图中有待寻找的目标,且模板有…样的尺寸和方向,他的基本原则就 是通过相关函数的计算来找到目标的坐标位置。


ral
f h1

尉4-I

模板匹配示意图

(a)场景图,(b)模扳

中¨科学皖坍究生皖硒十论文

记州午f{控州惮匹配钾“、刈占J;H像,En烈靴Ij讣fI.

设模扳7替放北场景罔豫~J.、}7f;,模扳筱羔H由那块场景罔f蒙叫做H h、J7
斟N。,I.,为这块H},Ji了I剖|_|勺芹1.『fJ像采许I纠NIItf『勺举},J、、¨LI参与.一jh从I叫4-二 几』以石…,i,,的l驶缸范川为:1<i./<A 7一^,十l。

^,

●}————————÷

十i飞
斟斗:场景斟像【a)与横扳(b

观在口T以比较71和s。,的内容』’。栩珥荇一敛,则7和㈧..之美.为零。所以口j
以川卜列婀种测度之’来衡南i ir利N,,的-十}I似程度

,地/)=∑∑【^
或者

(4.】)

D(,√)=∑∑限小w)
如果展丌自卜一个式二』,,则自
l,

(4—2)

’,

,J(,,J)=∑丑一,(帆,7)】二 ∑∑¨

一亿”)x

7(Ⅲ川】+∑∑m771,7)】二
,H=1,辟1

(4.3)

钉边筘.i项_=&示枚扳的总能越,是

1\常数,.Lj(,-,)_九父,第上砸足杉!扳趟

蒿ii的那块l刮像了f矧的能毓,它随(『_/)缸’岸的变化『山缓慢改变,筑:琐艟了I蚓

像和和校扳H像的:f_J{荧,鼬(,l川|1儿_嵌、当7和N肚州时叫r劁缘为H杯JiH

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕十论文—舅四章传统型堡堕堡里望翌一堡丛鬯堡塞垡堕些兰坌塑

像时此项取得最大值,因此可以用下列相关函数做相似性测度:
^,^,

R(i,/)=篓#}矿————一 ∑∑is。(m,”)】:
m=I

∑∑is。㈨n)xT(m,”)】
(4_4 j
n=l

或者归?化为:

∑∑p
R(i,J)=
f^,^,

(Ⅲ,")×T(m,”)】 …^o
(4—5)

17∑∑h(m,n)】!JZ2[T(m,n)r l…“=‘
Y_f=I目=I

掣为常数时取极大值(等于1)。式(4.5)可写成更简洁的内积形式,令
,I厅7,行J

根据旋瓦兹不等式可以知道,式(4-5)中0<R(i√)<I,并且仅在比值

Si(f√,表示予图,f表示模板,则有:

踟∽2耐淼

㈨。,

当矢量t和S(f,』)之间的夹角为零时,即S.(f√)=kt时,这里的^为标量常
数,有月<^,)=J,否则R(i,J)<I。

4.3传统快速模板匹配算法
相关匹配的计算量是很大的t模板T与子图像S。在(M—N+1)个参考位置 上做相关计算,其时间复杂度为D((Ⅳ一M+I)2×M 2),但其中除一点以外都是

在菲匹配点做无用功(单目标场景图像)。因此人们希望设计…些快速计算方法
来满足工业需求。

通过分析我们发现主要有两种途径可以减少算法的计算量:一种是减小模板

T与子图像S,的相关计算;一种是减小模扳7’在场景图像S上的搜索空间。几 前,较为常用的方法有:FFT相关算法、序贯相似检测算法(SSDA)、幅度排序 相关算法.多辨率塔型结构算法(MPSA)和基于遗传算法(GA)的快速搜索
算法等。下面我们分别详细介绍上述算法。

中国科学院研究生疏硕士论文

第四章传统&|像匹配算法对芯片I生|像定位试驰与分析

4.3.1

F兀相关算法
由傅立叶分析中的相关定理可知,两个函数在定义域中的卷秘等于他们住频

域【1I的乘积,而相关则是卷积的一种特定形式。因此,存在着另‘。种计算相关函 数的方法。但这样做在时间上并没有可取之处,而快速傅立叶变换技术的出现比 川直接方法提高了一‘个数量级.为此用FFT进行频域的相关计算也是一种减少
计算量的方法。

首先把模板图像丁和场景图像S进行二维离散傅立叶变换(DFI’),对十71,
有:

T(“v)=古∑∑T(i,j)w…W…
Jw

(4.7)

』_0忙0

其中“和v分别表示i和,方向上的频率变量,且 W^,=ex.p(j22r/M) 对于场景图像的二维离散傅立叶变换用同样的计算方法可以得到S(u.v)。然 后由相关定理可以写出离散傅立叶变换m(“,v)为:
孵(“,v)=T(u,v)S‘似,v)
(4—8)

接下来对吼(“,v)求傅立叶反变换,就可以得到空域中的相关函数g(i,J)为

R(i,/)=∑∑(彳(叫)一S(¨)】雌w嚣
u=O v-o

(4.9)

其中?为共扼运算符。
由此可见,相关函数可以通过DFT的方法计算出来,而计算DFT最有效的

方法是FFT算法(FFT算法这里不作讨论,可参考有关教科书)。 最后,根据以上的关系式可以画出FFT相关算法的流程图,如图4-3所示。

图4-3 FFT相关算法

如果模扳幽像71和场景图像S很大,那么这种算法将节省很多时问。需要注

熔铜炉

http://www.txjm-zj.com/

毓肼辛.传统斟撵IJc配算法肿.群"蝌僳定位试验‘j臼"i

意晌^!=,Ih J。DFT足个J纠珊l"L/幕l数,蚓此性雕点会J剖19…0…州,J77【_Dttl!殳际J域

川时心采取必霹的{丹施。 4,3.2幅度排序相关算法
返种并浊IlI两步纰成。第‘步址把场景『刮像,『-的芹个耿J亟位扳幅膻人小排成 刊的形式.然肝刈它进{f.进制(或一进制)编码,址所袱士|}::迸捌排17:的渚刈.

把场景㈧像变{讯成.逃制阶列的‘个仃序集合{(1。"=1.!… ̄r】,返过”称为 柚度排序的顺处雕。第.步,{lllj{J亍;l’内将这Ⅱ~.进制阼剁。I楼板矧像进行…粑剑刑

的4<1I天运竹.盥到确定川嘎配点为“.。为了醣{UJ这种锋法的原鄄.以卜举侧观}叭
第‘步:坝处剧

肖。先把场景罔像(3×3)?…门扦个灰膻(11[按人小次序排成列.并算…器个
荻度值仡原蚓中的位置(,,女)。f(【j劁4-4(a)所1÷。

位置
(1?k)

幅度
17 15 14
11

二i挂制摧序
(11(2)《3)
I : 1 1
×

(1,2) (2,3) (3,1)




1 0



×

l 0


(1,1) (3,3)
(2,1)

10


0 0

1 l 0 C

1 0

(2,2) (二.2)

q 1








a)3×3场景阿像
陌4-4

Q,j)

(h)颅处坪步骤(排Fr) 3×3场馈阿像觚处婵

然历把排序后的灰度幅度值分成数H捌等的两纰,l L幅度人f一‘组赋值为1,

幅度小的毗值为0。荇蛳度数为奇数.帅ft问耶个巾f.钆芝浦规定为X。如俐4-5 Jpi

_j。把每‘鲍【分为两、}!.刑t-刊样的畎『,I和0位,这个过甜‘直进行剁择组划分
为‘个巾儿为I【:,7F;成一:避制排』争。
J‘足,根斟,}”:进制}*序的次f手(1)(2)(3)和符个:进制及je位置,便町

构成(。I,(’2.“等j进制融’硎。如矧4-5所1;。I-jFi.对r‘般情况口,得
{f’.,,,?=1,2…

,、r;(A7为.进蔫:J{|}J亨f内分垃:数。)

中嘲利学院研究生院硕卜论文

第pq豪传统罔艨旺眦算法对芯片罔像定任试验2』分_i





O 1




i 0



0 i
×

『o




0 0











1 j

1 I



第.步:}}溻!剑细的引l父过H。 尚光,川“雕列-』帧饭酣:刊作川天返钾:.得

妒MV)= ∑尺,“+、一 ∑尺,。。
,‘ /^

(4.10)

('|I J☆l:I

(。ll,^悼(1

这意u术着.:j(’l酣j列放九模扳f一个{蜓索何岢(虬r)…t,’j“。fI的l值所
对应f阿模扳吲像的灰度值之和减去’j(1l小的0值所对,越的模板矧像荻度位之和
(【^J1j(’I巾×所对应的模扳蚓像的荻度值|J!fJ被忽略)。所以n(圯~?)吱际卜址1比

特量化场景图像。j模扳图像的j;f{荆『关两数.它反映丁土勿景罔像tl r最籼糙f门H像结
掬侪息1j.|:;l板l划像的秆|火。以(zt.r)称为缺奉}|J天ff!f二

仵模扳蚓像的全区域艘蒙过种-h荇i5}定一个I到值m,,』f:禽办耶此
锻(以v)<th。的艘索点,【l|l』口J_以人人碱少卜I

轮搜索州的挫索位置数。作

矿:(ff.v)>th.的搜索位置J:.再进行细的十¨火远竹,拢口J’以_L}j卜式米计并。 妒二(z,.’‘)=矿I(玑1’)+(
}k

∑舟川“。.~ ∑异,叫‘叫)/2
}k (:【/.k】;。’

(4.fI)

f:‘,^户】

州鲤!,为了a成少fr争议f|0 pj削点的数卜I.世闽值m?,』j:仡驴,(¨1-)>1/7、『|0搜

索谚置卜.以(j为堰础进行更细的干¨父运筛;

矿;(Ⅳ,’’)=妒:(Ⅳ,V)+(∑尺。“。一∑只一¨。)/2
,j ,i ({(,^)=1



(4一12)

f“,tk¨

再设糊值珐.;等,依次类推,nJ。得"个榭天i卜mf为:

硝玑11)=%1(玑V)+(∑R…¨,,一∑尺H“。)/2”1
,^ 』女

f4—13)

(,¨^l=I

<,f,^Ffl

与设置心位th,,埘’,若纸fff‘,’’‘)>,☆。帕伊置l:仃‘个,则咳侮冒使为肛州H 杯的伊营。¨然捧个闯值的天采如F:
7。>一一l>

>7j>7l

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院颈士论文

茉四荜传统图像匹配算法对芯片图像定位试验与分析

因此,逐次细化相关的搜索位置越来越少,直到找到匹配位置为止。此方法 减少了计算量.提高了处理速度。

4.3.3序贯相似检测算法(SSDA)
Bamea等人的序贯相似性检测算法(SSBA)的基本思想是这样的:往每次匹
配过程r{,并不等到模板与场景图象中的某‘子图象完全匹配结束后才决定该子 图象是否为一日标子图像.而是在该次匹配过程【+j检测已处理的郜分与模板的相 似程度,
新的匹配。

‘旦发现子图象与模板育较大差别则放弃该次匹配,重新选择参数进行

虽然这…算法针对的是简单模板匹配方法,但埘其它匹配方法有指导作川。
SSDA算法的基本要点如下:

(1)定义绝对误差值为:

s(f,,.mt仇)=Js。(m。,"^)一互、,(f.j)-T(m。,心)+于f
其中


(4.14)

^,盯

文‘加素萎酗加,哪
T(i,,)=—击T(m,n) 』W…月。I
取‘不变闽值腩 (2)子图像S,(m,71)中随机选取像点,计算它同模板图像7’I卜对应点的误 差值s,然后把这差值累加起来,当累加r次误差超过th,则停止累加,并记下次

数r。定义该算法的检测曲面为:
f(f√)={rI rain[g(i,,,%心)≥f棚)
(4.15)

(3)把,(,,_,)值大的(,,/)点作为匹配点,在这点上需要很多次蒙加才使总误
差超过抽。

对SSDA算法还可以采取一定的方法加以改进,比如: (1)搜索时采取隔点搜索,不逐点搜索。即,模板不…定对每一?点都平移。
例如可以用粗一细结合的方法搜索,即先每隔r/个点搜索一下好坏,然后在有极 大匹配值周围的局部范围内对各个参考点持确匹配。这样fIi,D的单峰性和平滑 性将影响匹配的正确性。

(2)改嘲定闽值,^为单调增加的阈值序列,这样使非匹配点,}j更少的计算就 达到阈值而被舍弃。

坷科学院研究生院硕h仑Z

鹅pq簪传统【≈豫J眶配尊法埘一出片矧像定他试验。,分H÷

SSDA鲐法足~种坝受重视的方浊,我们m p一学的墒卡模饭抽样(TS)的 方法巾川这种方法作r优化,取印¨’胛思的设裂。 4.3.4多辨率塔型结构算法(MPSA) MPSA钟引、的壤水思想址源十人们光栅Jli钏∞、¨knf,】;的方}』、,例如,f1… 抖地|冬|t J?找北京的似芹时,人们一舭咒找剑l㈨4这个人卜<域.我们称为¥n牛¨X过 柙,然J.j亿这个Jx:城内fr自II确定北京的何胃,这叫.fill斗1f天过秤。很IUJ姓.这种方 i』i可以很快找剑我们所希塑的r『丰,』” MPSA算法采川j,企’一嵴式的数抓?,I拗,也就芷将㈥像迸行J’分层处坪。它 通过从粗糙蚓像(叩低分辨率图像)丌始进行模扳匹配,逐步找,0原始蚓像(叩 垃岛分辨率蚓像)c},的旺配点,』e步骤如卜: (1)对待旺配的场等亡H像和模板l冬|像tf 2×2邻域内的镍素扶皮倩取、}j均. 甜刨分辨率低一线的㈥像。 (2)对分辨率低一级的矧像叶J 2×2邻域内的象素狄度侑m取“I均,f:}剑分 辨率更低一级的图像。依次类推,可衔到一纽昼金1,塔,℃的矧像,削^表示级数, K为最高级,k=O级幽像为原蚓像。 (3)从待匹配的场景刚像和摸板H像的筇K级(即最低分辨j昝劁像)丌始 匹配搜索,找到粗肛配位置肝,冉n:笫尽1级图像I:粗压配化置附近进行搜索, 依此类推,A到女=0的那一级(即原H像)为I}:。Fh于从第肛I级丌始仪限十 仵一个域儿个粗匹配点的附近进行搜索,所以汁算节并小人。

假定场景第女级为9,模板图像筇女缎为^从l二述舒.法可以行…,筇一次
搜索(即她Ⅳ级图像)足遍历搜索。搜索何置的个数为((Ⅳ一A门12。十1)2,每玖 压配’十算的象素^ii数为"2/4。,汁尊艟已绎人为减少。: 7Ⅳ”1指…,对于』nJ样的分层技术,若采Ⅲ/i;J吲的滤波预处胛和彳iM的十lj关算 法,就可以形成4i同的分层吒配方法。另外,该方法还可以川SSDA方法术优化 搜索时M。 4.3.5基于遗传算法(GA)的快速搜索算法 一般『^f击,场景蚓像以及模板小身郧难以川衙单几精确的数学模型水表示。 爱从阳乍刚像?f?找刨对心模板的最传眄配了-蚓像很难利川先验知l泌=然lni遗传解: 法却能ni对象捕述/fiIU J确的情况Fn:仝』而范…内找剑次坡优解乃全蜮优斛。J爿此 就可阱…崖传算法t虻化搜索过f7。

遗传舒弘足近年求发“≤琏采的一神新的岬论,它仿效J。}:物从低级剑t岛级的
进化过柙,j£仃简单、通川、田椽?El:-强利适十jf:行处辉等优,t,它乐川仃指导的 非迹7/j随机搜索机制,可以快述收敛剑全硒近似蛙优斛乃至最优解.所需的汁钎

熔铜炉

http://www.txjm-zj.com/

中翻科学院研究生皖硕上论文

第1/It章-传统图像匹配算法对芯片图像定位试验与分析

量较之遍历搜索要少的多。因此,遗传算法非常适于图像匹配问题的求解。其基 本步骤如下: (1)对所需优化的参数进行编码,确定解的适应度函数、群体规模、最大 世代数,复制概率、杂交概率和变异概率,并随机产生初始群体。 (2)计算当前群体中个体的适应度。 (3)将选择、杂交和变异算子作用于当前群体产生新一代群体。 (4)迭代执行第(2)步与第(3)步.直到满足终止条件为止。把适虑度 最好的个体指定为最终结果,解码该结果得到本问题的解。 将遗传算法用于图象匹配遇到的首要斟难是编码形式的确定。如果将二进制 形式的坐标位置作为编码,那么将无法保证杂交过程中产生的新个体包含父代的 优良特性。为此需设计一种有效的编码方式或对遗传算法作必要的改动,例如将 匹配进行的方向编码并在此基础上使用遗传算法求解。

4.4传统快速图像匹配算法对芯片图像定位试验比较
我们在主频为1G的工控机上利用Visual c+十6.0实现了上述的快速算法,在 试验中选择了大小为640×480实拍芯片图像作为场景图像,模板尺寸为234× 234,如图4-6所示,试验结果如表4.1所示。匹配效果图如图4.7、4—8所示。 由于FFT、幅度排序相关算法、SSDA和MPSA四种匹配算法匹配位置相差不大, 所以并未全部给出匹配效果图,仅给出了MPSA匹配算法的匹配效果图,而GA 匹配算法可以搜索旋转角度,具有较高的匹配精度,因此也给出了匹配的效果图。

图4-6模扳图像

中国科学院研究生院硕士论文

第四章传统图像匹配算_;圭对芯片图像定位试驼与分射i

(a)

(b)

图4_7

MPSA匹配结果

(a)

(b)

图4_8GA匹配结果

表4-I算法比较结果 原始位置(中心)
b FPr

算法

匹配位置(中心)


匹配时间
(ms) 17854 6543 804 lOl6 1278

r297,204) (290,206) (286,203,0.50)

(294,209) (293,212) (29I’2】I) (291014) (296,219.7189%

幅度排序
SSDA MPSA
GA

(299,228,6.80)

(290210) (294208)

(290,204,10)89%

需要说明的是对于GA的方法,由于其每次匹配的时间和位置并不完全敛, 所以在匹配位置这一项中我们标注了匹配成功的概率,并且匹配时问也只是个 平均值。另外SSDA算法随着目标位置的不同,每幅图像所需的时问也并不柏同,

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

第四章传统图像匹配算法对芯片图像定位试验与分析

这里也只是取平均值。 可以看出FFT、幅度排序相关算法、SSDA和MPSA四种匹配算法对芯片图 像存在较小偏转角度时(图4-7a>,匹配精度基本能达到要求,而“’旋转角度较

大时(如图4-7b),匹配精度变得很差。GA算法能搜索芯片的旋转角度,这样 匹配精度较前四种算法要高.但也不能满足精度要求,而且其失配率很高,这是
不允许的。更重要的是是这五种算法都不能满足系统的实时性要求(<25ms/线)。 冈此,在下‘章中我们将针对芯片图像的特点有效的组合改进上述的快速算法. 来满足系统对速度和精度的要求。

4.5小结
目前.图像匹配技术大致可以分为四大类方法,即基于解释的匹配、神经网

络匹配、基于特征的匹配和基于灰度的匹配。由于前两种方法还未成熟,而基十 特征的匹配方法在特征提取上耗时颇多,也就是在实时场景图像的预处理上消耗 时间太多,很难满足系统对实时性的要求,所以只有基于灰度的匹配方法最适合
本课题。

模板匹配是一种基于灰度匹配的方法.目前主要有FFT相关算法、序贯相似
检测算法、幅度排序相关算法、多辨率塔型结构算法和基于遗传算法的快速搜索

算法。实际上全自动金丝球焊机的前~种设各(共晶粘片机)在粘片时,难免粘 歪,也就是说送到球焊机的芯片存在着旋转,这样前四种算法无法搜索角度.使
得精度难以保证.并且也满足不了系统的实对性要求:GA匹配算法虽然可以搜 索角度但是也不能保证精度,而且在实时性上也不满足系统要求。

在实际工程应用中可以改进或者组合几种算法的来满足我们的要求。例如, 可以用序贯相似检测算法来优化多辨率塔型结构算法等。在下一章我们将详细介
绍本课题所改进的快速图像匹配算法。

中国科学院研究生院硕士论文

第五章芯片图像实时定位算注设计与实现

第五章芯片图像实时定位算法设计与实现
本章主要内容:

1.详细讨论了Ts匹配算法及TS—GA匹配算法,简要的介绍丁MPSA—GA 匹配算法。 2.通过实际芯片图像试验比较分析了三种匹配算法的优缺点并给出了详细 的试验数据。 3.通过试验验证了三种改进的匹配算法具有~定的通用性,可以应j{J在类 似的其它环境中。

5.1问题的提出
我们知道对模扳匹配来说有两种途径可以减少图像匹配算法的计算量:一种 是减小模板71与子图像S,的相关计算:…种是减小模板T在场景图像S上的搜索 空问。由于上一章所提到的各种快速算法并不能满足全自动金丝球焊机的应用环 境,它要求目标芯片图像在具有旋转的情况下,以25ms/线的速度精确(±49in) 识别定位。所以必须对现有图像匹配算法加以改进才能满足我们的需要。例如, 可以用SSDA算法来优化MPSA算法,也可以用GA来优化MPSA算法。但是这两 种方法仍不能满足全自动金丝球焊机的实时性及精度要求,因此我们设计了满足 系统要求的两种快速算法,即基于模板抽样(TS)匹配算法和Ts与GA有机结合 的匹配算法(TS—GA)。 假设给定场景图像&大小为NXN, 模板图像7’,大小为MXM,记S,为S

中欲与旭配的子图像,(,,)为量,的左上角在s中的坐标。对计算机而言,加减
运算速度比较快,因此,我们采用点与点之间的灰度差作为两点之间的距离。定 义图像A中点aN图像B中点b的距离d(一(Ⅱ),B(6))为:
d(爿(口),8(6))=I A(a)一B(b)l。
(5.1)

5.2TS匹配算法
由于芯片图像自相关性很强,所以可以选择适当的搜索步长进行第。阶段粗 匹配,加快搜索速度。然后在此基础上进行第二阶段精确匹配,找出n标图像的

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

第五_棼芯片图像实时定位算法设计与贫土蛇

旋转和精确平移。 5,2.I芯片模板图像预处理 ’幅芯片图像是一个复杂模式,包含了丰富的信息,其rt,许多信息是冗余的, 闭此,不必要对芯片的模板图像与目标子图像进行逐点比对。在确保匹配精度的 前提下对二维芯片模板的灰度边缘图像以归一化后的灰度值作为概率密度进行 抽样。这是_’种在统计意义上对图像上有代表性的点的提取,从而减少了匹配过 程【{1图像数据的运算量,提高了匹配速度,同时也提高了抗噪声能力。 为了对芯片模板图像进行抽样得到抽样点序列跚(,),需要对其进行如下预
处理:

一、芯片模板图像的增强
(1)直方图均衡

在获取的芯片图像中.存在着由于光线的变化、芯片材质及材质的氧化程度 不同等因索造成全幅图像偏暗或偏亮或亮度范围不足造成的对比度不足等问题。 所以首先要对图像进行直方图均衡,提高图像的对比度.以便于后续的边缘检测。 芯片图像的直方图的均衡处理效果如图(5.1 b)所示。 (2)中值滤波 大多数滤波器在降低噪声的同时也导致了边缘强度的损失,因此在增强边缘 和降低噪声之间需要折中,为此选用既具有明显边缘保护特性又具有较强去噪能 力的中值滤波器。一般中值滤波窗口越大,去噪能力也就越强,但过大的窗口会 增加计算复杂性。在第三章中通过试验选择了5×5的十字形窗口进行中值滤波. 以便在滤除噪声的同时尽量保持芯片图像边缘的清晰度,其滤波效果如图(5.I c)
所示。

(a)原始芯片图像

(b)直方图均衡处理后图像

(c)中值滤波处理后图像

图5?1芯片图像经直方图均衡及中值滤波处理后效果圈

±望型兰壁翌窒竺垦望主堡奎
二、边缘提取

墨墨!蔓苎璺堡塞堕塞堡翌鎏堡生兰!!丛

边缘提取有多种算法,在这里采用Roberts边缘检测算子得到芯片模板的灰 度边缘幅度图像,边缘提取的结果0ngfl(s?2)所示,定义其概率分布为:

P{X:f'y:/)_j;l业(5-2)
∑∑G(t,,)
其I|】G(i.』)表示灰度边缘图像在(,√)点的灰度值。 可见,芯片模板图像经过Roberts边缘检测算子处理后,得到的边缘部分被 勾画出来了,边缘部分要亮一些,也就是灰度值大,然后以(5—2)式进行抽样,这 样边缘部分被选择的概率要大,如此芯片模板图像的主要特征被突出了。

图5-2 Roberts算子处理效果

三、提取抽样点序列 得到芯片模板的灰度边缘图像后,以(5-2)式确定的概率P对其进行抽样 得到抽样点序列Sq(,)。,的大小由下式确定:

,=f㈨川G(Lj)>m}l
其中m为阚值。 在具体实现中我们采用的是轮盘赌的方法到抽样点序列国(,)。

(5-3)

考虑到目标芯片图像存在旋转,因此需要对芯片模板图像T以qt心为对称点 进行间隔为l o的离散化旋转处理,L表示模板图像以角度0”旋转后得到的图像。 需要注意的是经过旋转处理后图像的大小会改变,我们截去对匹配有影响的 点,如图(5.3)所示。由于对芯片模板图像的预处理可以提前进行(对实时拍摄的 芯片场景图像不作预处理),并不占用匹配时间,保证了匹配的实时性。

熔铜炉

http://www.txjm-zj.com/

中翻科学院研究生院硕t论文

第五靶芯片图像实时定位算法设汁与殳观

图5-3模板图像、旋转后图像及旋转后截取图像
(阴影部分为截取图像)。

5.2.2第一阶段搜索
在第一阶段的粗匹配中.需要从全部匹配子图像集S中获得候选子图像集台 C.为了保证算法的正确性,必须满足 (I)c包含真正的匹配点。 (2)}cI尽可能地小,以降低第二阶段的搜索空间。 (3)C能快速获得。 在第一阶段以搜索步长h进行粗匹配以确定集合c中包含的元素。

定义予图像与模板图像之间的距离D rS,.r,为:


D(S。.r)=∑d(S¨(勋(f),丁(Sq(f)))
tll

(5—4)

候选子图像集f满足:
C={S。fD(一,,T)≤0}
(5-5)

其中,0为阈值。

候选子图像集的大小fCl影响匹配的正确性,旧过小,就有可能产乍失配,
特别是在场景图像中存在多个目标子图像时;而Jq过大,又会增大匹配时问。

}{j户可以根据实际需要选择适当的阑值以确定1c1。
5.2.3第二阶段搜索 由于金丝球焊机中的芯片图像总会发生~定范围内的旋转,因此,准确定位 也应将芯片的旋转角度找出来。试验表明,偏转角度.70<a<70对粗匹配的影
响不是很大,因此,在第一阶段的设计中可以不对其进行考虑,在第二阶段的精 确匹配中增加多模板匹配这一环节。 在第二阶段中,需要为第。阶段搜索得到的c中的每’个候选子图像确定搜

索区域.区域大小(2rX2r)的确定弓搜索步长h有直接关系,理论上廊选取r= h/2。具体做法是:以每…个候选子图像S,的定上角丝标(id)为rI-心,建立大

中周科学院研究生院硕士论文

第五章芯片母像实时定位算法设计与实现

小为2r x打的搜索区域,如图5-4所示。在每一点遍历匹配每‘个旋转处理后的

模板图象L.取
(,o,^,%)=

{(_弘0。l她∥五)=Hra口nin,(魍w-瓦,))^i一,<z<i+r^/~r<y<J-kf'A-7“<口<7“} ,“I’(J+r
一7姐。(r

为最佳匹配位置。
fegL0ntobe

se础ed

图5-4搜索区域的确定

5.2.4

TS算法优化策略

为了进一步降低芯片图像匹配计算量对该算法进行了优化,在每次匹配过程 中并不等到芯片模板图像与匹配子图像完全匹配结束后才判断是否是目标芯片,

而是在匹配过程中动态生成阐值序列砌,该序列形成了实际检测曲面,如图5-5
所示。一旦发现距离D(s。,r)的计算结果超过检测曲面,则终止该次匹配,进
行下一次匹配。 检测曲面动态生成算法可描述如下:

1.令thI=o(s。r):
2.对于第n次匹配,若有,满足

Zd(S,(勋(七)),r(勋肚)))>巩∥,<,
I=I

(5.6)

则Th。=Th。,并放弃本次匹配。否则

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

第五章芯片图像实时定位算法设计与实观

Th。=O(S。,T)
5.2.5

Ts算法分析

该算法意义清晰直观,设计简单,易于实现。匹配算法中仅涉及加法运算. 只在对芯片模板图像的预处理中涉及到乘法运算,保证了算法的快速实现。

传统的灰度匹配算法时问复杂度为o((Ⅳ一M十1)2×M 2,采』fj上述算法第 阶段时间复杂度为0【(Ⅳ一M+1)2×,/h 2),第二阶段为o(5 cj
xt×4r 2×,)即

()(fCl×f×h 2×,),因此总的时问复杂度为D(((Ⅳ一M+1)2/h 2+lC J

xt

xh!×,。

算法复杂度大大低于传统算法。

∑d





10

15

20

2S

n(times)

圈5-5检测曲面示意图,其中实线代表动态生成的检测曲面.虚线为距离曲面。

搜索步长^的确定是保证算法正确性的关键。当搜索步长较大而模板较小时 有可能漏检真正的匹配子图像。图5-6显示了搜索步长与时间的关系,可知,搜 索步长h在6~12之间,算法所用时间较少,在全自动金丝球焊的图像识别系统
软件中,采用h=10。

需要说明的是,算法中搜索步长h,候选图像子集大小J



l以及抽样大小

,均为变量,可以通过试验,针对具体应用场合在时间和精度之间做出取舍。

中Iq利学院研究’I院顽}。|仑史

第l:尊苎¨罔僳寅H『定俺弹法蹬汁0寓观

160.J

一㈨J1 翟
量40

籀00 川5
,=300

苜80 1


Sea

rching steps(PixeI)

I《5-6时M‘_搜索步K的父最

5.3

TS.GA匹配算法
逮f々竹法足近年束发J良起来晌1种新的优化蜉浊.jl仃简巾、jl立川、停棒蜊:

强和通』’外行处理等优点。它采刚f1‘指导的m遍J』J随机搜索机制.ar以快速收敛

j:9个局次优角犁乃每最优解,所篙j的计算鼙较之传统的遍历搜索耍少的多。 现仃的基于遗传筇法的匹配剪法虽然能够解决H标子l纠像I’向旋转M题,fI!适 应皮怕订算或足计铮量夫或迅需要对场景图像进行复杂九勺预处削,小能满足系统 f门实时+Pli要求,,j外.对旋转,fj度的旺眦精度也满足小了要求。㈥此.投们肘观 仃的旗_r遗传馆法的旺配算法逆行改进结合了TS锌法的思想对::维模板图像的 荻度边缘罔像进行抽样处理,汗n最后刈J几盹结粜进行了精确的们』耍及微小何移
铰『F。

I:靴经验表I_!JJ遗传算法件件。r以fH队收敛到仑局近似敲优解.如裂要收敛剑
破优解则i^j要较K的时问。刖此分两步时㈨像进行jJL=M。河先.以第+步的机JK

雕?{-利用遗传算法得到灭’r H标于J纠像的近似鲑优解,然后九:此旗础j:x,j-H杯子 矧像的微小胜转角度及微小位移进行p;配,以便找…H标子图像的精确俺置及旋 ¥t讯熳。 s.3.1芯片模板图像预处理
fjf J:TS算法’j TS—GA好法的j:璎区别^:J‘搜索策略的玎iH.

利,足采川确
样的.nJ

定。Pl:搜索策略,
以参J硪5
2 1。

’种足采州随机搜索策略.m他仃j肘校扳的顶处删址

5,3.2对芯片图像进行粗匹配
m靴lJi眦一h 1^i要从个闸:IK眦f罔像集合一}-快速扶搿H杯子1刘像旧近似群.

…此.造化竹法适合小问题f门求自¥。m府州遗f0铮法求解蚓像l儿州刚地时,1:嘤

熔铜炉

http://www.txjm-zj.com/

q,r斟车!f学院研究{.院颈i’论吏

第t搴芯片舟像蛮对《侮悼法没汁’j实脱

解决以F两个刚巡: (1)染也体编码

染色体的编码策略刈J?遗化搽作.尤i0足时j‘交义搽作的助能仃张人影响。
采州吱数编码无蒿进行问题守州‘j GA穿问的敦制转化,能直接反n灾…所求刚题

小身的结{=f:j十0{ll!,¨口,能,”卜无效编码,所以心?』f入编码的f『效。r{:榆聆机带’j.总
f10术泌,文数编码f门引卯:芷璎小J

.进m』编码,从Ⅲn,以电仃效n0小队收敛,…

此逃Ⅲ了实数编码。考虑剑芯H l到像仃’17移、娩#‘特‘Pf:,将这u叫j。+阡编剑染包体
IfI.自。:

('hn*m=k,,口

f5-71

le中(,,,)投u÷待I嘎刚子㈥像s。t}rl均(,,,),目太小S。十llX,J-j‘校扳降J像的偏 转ffJ度(精确纠1 o)。【大】此, (2)适应度嘲数的构造 }if j:遗传算旺i柏j求解问题时,琏本4i删外部信息.仪以通戍眨嘲数为胀捌.

’个染色体对应。对(S。7:,)。

所以适随度诼】数设计的好坏直接影响遗传舒法淌?睢能好坏。 定义适应度函数t:ilnit~(,、/,占)为:

Fztne,'Ys(i,J,臼)=

.1)喊j,T—j1
f,xt

(5-8)

JLmI,^为『冬f像荻度级。当7:,’jS。完个j,E刚时,,)( ̄、。,7],)=0,l,7tni、^(,‘,,d)

取得坡人位I;,)(N。,7j)越人,适应_r!L峨数t:ttnixs(i,,,8)越小;当,)(N…7:,)耿
得最夫值L×,u,f,透应度萌数}7铆,“(,,j,秽)墩得最小值0.5:这样藏订了刈劁像
『,i雕秘度的确1效判据。

确定了编码策略与适膨度甬数,卜咖对jE他Hl天问避进行训沦。
(1)初始群体I’由,“牛以及群体设定

…J:要求打:线迸f于阁像f心州.『大I此难J:捩取行天H标子阁像卉:场景罔像的何 置1iffj度的先验知U{,jI能f9Ii机乍成仞始群体。为了避免术成熟收敛埘缘.心采 Hj较人旧群体规栈,以保证群体的多样性,f}1考虑剑计算散盔,群体姚卡5:}1i1门:过

人。通过试验,选用群体娥校为60。
(2)造f‘操作设计
复制操作。n:f辱 代进化。h尚‘丸陋"L决定小次进化淘汰的个体数量,然盯

采川轮龠:嵴的/。’浊随口【决定沏汰和复制旧个体,以饵:持肝体nq多样一阽,迹免m入

叶?『司利学脘研究卡院硼{:论文

第t章芯H斟像实时定他弹;j.畦计与蛮毗

局部最优。为了加怏收敛速J亟.时轮甜蜡,J’法进行丁&i垃.叫n:选定要淘汰和耍

复制的个体质.严椿以&f个体盼换0i良个体.fi}:将通『№度土i圭&f的个体直接复制进 入r代,m淘汰迂庸膻址斧的个体苻发观子代【1叫、包禽j前株存旧通心嫂坡
☆J:f|,J个体,就:瞄+占燃删f采衙.进入_ 代..

jj交操作。采圳j进制编码时.执f『杂交h5P)j:’’’乍f门新个体1j父代蜉别小人.
¨物川意义小f9 J蜘,l阿采州十进制浮点数编码时,{嘻个十进制敬做石作 个J r;…

坚体,㈥为个体小身虢址斜夺M n0点,lL物州意义锹lUJ确。为使尔交^i肝新IH个
体仃更人f一斧异,找fil J构造丁‘种。盘进I’门"术尔交17于.jW『『述“『h:

∥卸1。I+hzxz
1引r h=0

(5-91

Ix2’=^2xl+^lJ:
5+h,h2=O

5一^,h=O.95fl,∥为[O.I”杓随机城a

为了避免刁i ar行个体解的,‘。,j-,采取n!J。7l二子代后逐个判断足fr越界,荇越

界则更换成下面的混合杂交辣子求产生新个体,以利j:个体的多样‘H:,I—J时陔竹
子可傈砥子代玎i会越界。

㈠2e1+‘,2k(5-10) 【X2'=肛二+(1一声)』1


je—h∥为[O,1】的随机数=

变异操作。每个十进制数的受异郜吼点制订:动力学筷型的参数允许响变动范…
内,可消除1i合耻变异,以提l:刊欠敛速度。采用’{|=均匀变异法。捕述::[|rF:

对j:给定的父代个体、t.荇它的/曲薛r:被随机选米变异.删,j:成衍代?,’,¨f}
JⅣ的兀索随机地按如卜两种nJ能f向机会变化:

』t。=』t+△(f,一:一』々)或工£=f^一△(,、』‘一工:)

(5-11)

这.甲,x:和x:分别魁扎f|勺J:卜界。蛹数△(,,J’)给…【0,J,】问的’个位,
使得△(,,y)随柠f的增jf|11撕趋+J:0(,怂代数)。町耿△(,,J。)为:
△(,,J?)=∥×r×(I一,/7)’或△(,.J-)=J×(I一,‘卜。1 9)
(5-12)

返哩,,‘为[O,l】的随机数;7’为艟人代数:h为确定+”均匀艘的参数。’j外, 为了科:仃限次的这f℃巾琳。r能获得参数的嫩优解.心陔:I苷{岳代群体c1 r迂戍膻最 好的个体r以保存,n:完成进化肝进行愉j的筛选。

5.3.3芯片模板图像的精确匹配
通过遗f0竹汪彳导到fn,‘,,疗小能满足个rI动金丝球“'4"lLI冬I像Ul别系统I’门特』生

熔铜炉

http://www.txjm-zj.com/

c{?』叫引。#院6阡究’卜臃M,卜论立

讯K尊已H l封隙盛时定似弹iJ、设引2 J史J世

璎求,㈥此必颈进行芯片矧像的精确I心雌。
当伊穆<7,^及旋转f『j度P}雎小叫.1II泰讪绂数腱Jl:,一’j 7,,之M满址F J℃:

N。㈠j)
=7。(』cos∥~J’sin∥十c,,.Ys“1∥十。、COS卢+^)
CA"

;7),(.。,J.)+旦掣(一、∥+II)+皇掣(.卢+^)
f—j

(5一13)

J:S,,(x,J,)一7:,(工,y):至掣(-yp+。)+旦掣(。∥+^)15114)
dx d17

J’址仃:

为求婀.f.』℃【f『的c,.^以成∥,jw“r取j个水M的点求何一n‘绑叩t『J,俐为

了确f铽精度-我们采J}I了最小:乘法利IlJ序列№(…},的点睢‘的fj『n定【“,h,芦1。
将第

步得到的L厶口川“,扫,∥j』【jr修正。U』j川锝到最终的匹州结果:

(i+“.J+^、口+∥)。

5.4

MPSA—GA匹配算法
实助-J:这种算法是先十前阳种算法”发…来n々,口】址并没彳『最后川存个||动

缸够球焊机的冈像识别软什小,卞要是它4 1芯“Ikl像II'JI;t;[~iL,㈠』1】U两种掉法相比

没订优辨t小满足系统n勺实叫陛要求,1R红特定的削像I几配中它也jI订较高的’戈 用价位。并儿它也是为开发^j阳种箅.法起刘丁肩发的件用,Ⅲ此_白。必要扛此作简
单的介绍,

遗{‘萌法的优势妊!.搜索速&}尖,能解决H标jf矧像的放獭问题。MPSA珏
法的优钟存于IJ‘配过程训剪茸.小并[L从菊Ⅳ一1级到染0级搜索,;,M小。
IvlPSA?GA鳟鞋;fJ.丰Jl的整合了这两frI r箅衽:n勺优势,』t设训思想是:

(1)对模板陶像7’进竹分层及旋转处理得到瓒(聪表力:7’。按0旋转盯nj
到j10新模板幽像,0精确到1”)。对场景}型像s进行分层得到St。

(2)对7Z殷N。利川遗f‘翁:浊迅速{£Il卜一个或儿个羊Ⅱ队配协置及Il协。rj刽像
旧旋{0角艘臼,缸然较MPSA郎法的第次搜索的迎_fc!:螫快了许多。 L3)年,Lrfl MPSA钟i上赴』0它J蠢『:依次搜索n刘赴J职ffff幽像l『一}蔓剑辅确匹州
ft置,

中国科学院研究生院硕士论文

第五章芯片图像实时定位算法设计与文现

需要说明的是,在利用MPSA算法进行第K层匹配时为了进一步降低图像 匹配的计算量可以引入SSDA。另外.该算法不宜分层过多(+般分3层即可), 否则将导致失配的概率较大或者得到的候选子图像过多;并且分层过多也使对场 景幽像的分层处理消耗时间过多。

5.5试验结果比较分析
利用Visual c++6.0实现了上述三种改进算法,并在在主频为lG的T控机上

进行了实际芯片定位的试验。试验芯片场景图像大小为640X480,芯片模板图 像见图5.7,大小为228×228,抽样大小I=280,f=1 5。对于Ts匹配算法l
C1

一I,搜索步长^=lO;对于TS—GA算法,GA的初始种群为60,他们被均匀的 分布于模板图像中,进化代数为50代;对于MPSA.GA算法分层数K-----3;试验 效果见图5-8,由于图像匹配结果类似,人眼很难区分效果,本章中只给出了Ts 算法的匹配效果图,在下一节的算法通用性分析中亦是如此,这也说明这三种算 法在匹配精度上差异较小,主要的区别在于匹配时间。试验结果表5.【、表5-2 和表5-3,可以看出Ts算法速度最快,TS—GA算法较慢.MPSA.GA算法最慢。 通过大量的试验统计(试验次数大于2000次),我们发现三种算法都有失配 的现象,其中TS算法的失配率为0.8%,TS.GA算法的失配率为10,7%, MPSA.GA算法的失配率为I I.3%。虽然TS—GA算法失配的概率比Ts算法高, 但是由于它采用的是随机搜索策略,也就是说对于同一幅场景图像进行多次搜索 可能搜索结果不完全一致,这样只要我们牺牲~定的时间就有可能正确找到目 标。 Ts算法通过引入候选子图像集合c,有效降低了失配的概率,使该算法能 快速精确的在场景图像中定位目标子图像。试验表明该方法对待识别图像依赖性 较弱,具有很强的抗噪声能力。但是该方法是基于确定性搜索策略的.一旦产生 失配,将不可能通过再次搜索正确找到目标。 MPSA—GA算法对模板及场景图像进行了分层处理,有效的降低了遗传算法 适应度的计算量,当然,它也可以引入候选子图像集合c来达到降低失配率的 目的,即在最低分辨率层上用GA匹配时保留多个候选目标子图像.但是,这样 又增加了计算量,这个矛盾需要权衡处理。另外,由于分层处理平滑掉了…些高 频信息,使该算法具有一定的抗噪声能力;但也使其不适于具有较多点、线、尖 预等细节的图像。 TS—GA算法通过引入了精确匹配环节.使得该算法能匹配精度得到了提高, 实际上该方法在匹配较小的场景图像中并不能完全发挥出其优势,在匹配较大的 场景图像,比如航片时.GA的非遍历随机搜索机制将会得到更好的体现,也就

熔铜炉

http://www.txjm-zj.com/

中国科学脘研究生院硕士论文

第五章芯片图像实时定位算法设训与立现

是说较之确定性搜索策略要节省很多计算成本。并且,若在算法个体中加入缩放 园子S,即令Chrom={,,J,0,S)就可以搜索具有尺度变换的图像。 需要说明的是,这三种算法对于目标或背景都特别单调的图像是不适合的。
将导致很高的失配率。

图5-7模板图像

(a)

(c)

(d) 图5-8 TS图像匹配算法定位结果

中国科学院研究生院硕士论文

第五章芯片图像实时定位算法设计与实现

表5,1 TS算法定位结果 序号 原始位置 匹^B位置


匹配时问(his)
l8 3 18.9
18 5

a(28 l 207、一2.9’



(280,2071-30) (296227,n
(306235,一30)
(3 14,24020)

(296227,7 03 (306,234,-3.2‘1 (314,240,1.80】



‰蚍哪言;哪 ,蛳‰跏‰

184

衷5-2 TS-GA算法定位结果 序号


原始位置 (28t,207,-2.93
(296,227,7.00) 006234,.3.20)

匹配位置 (281,207,-2 50) (296,227,7 l o) 006,234-3 51



匹配时间(ms)
42,4
45 l




46.7



(314240,I.83

(314,240,I.93

呱螂哪眦螂 ,娥‰%m

4l 8

表5.3 MPSA-GA算法定位结果

序号

原始位置

匹配位置
(28I,206,-30) (2%,227,70)



匹配时间(ms)
824 84.4
87.7

a(28120z-2,明



(296翌7,7∞
(306,234,-3.20)

(306235,-30)
(315240,2。)



(314,240,1.确

‰哪哪哪哪 ,铂%鼢麟

800

由于全自动金丝球焊机要求图像识别系统的识别率很高,否则将会造成极高 的废品率。因此,在实际的图像系统中我们使用了两种算法即Ts算法和TS.GA 算法。 系统首先使用TS算法搜索芯片的位置,如果匹配度低于设定值,则认为是 产生了失配,没有找到芯片,那么将启动TS.GA算法进行二次搜索,直到找到

芯片目标为止(实际上我们设定了TS—GA算法的运行次数舫止在无芯片目标时
陷入死循环)。

在完成了对各种算法的测试后,我们将所有算法包括图像的预处理分别封装 成类的形式提供给主控程序,供其调用。

5.6算法的抗噪声及通用性试验验证与分析
为了验证三种改进匹配算法的通用性及其抗噪声能力,我们分别刷三种算法 对同一幅普通图像进行定位,并对原始图像分别加入噪音、模糊,原始图像大小 为256)<256,模板大小为1 00×100,,=100,对于Ts匹配算法!C l=I,搜索步

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

第五章芯片图像实时定位算挂设计与实现

长h=6:对于TS—GA算法,GA的初始种群为60,他们被均匀的分布于模板图 像rfl,进化代数为50代;对于MPSA—GA算法分层数K=3;试验结果见图5.10、 袁5-4、5-5及5-6。可以看出,三种算法对噪声具有很强的抵抗力,对模糊图像
有’定的适应能力,具有一定的通用性.因而具有一定的推广应用价值。

图5-9原始图象与模扳

(a)加入卷积模糊

(b)加入随机噪声

(c)加入椒盐噪声

(d)加入椒盐噪声与随机噪声 图5?10

(e)加入卷集模糊与噪音

TS算法定位结果(图像加入噪声)

。固科学院研究生院硕士论史

前j上母,奋j}同像炎时定他锋法设计。o嵌班

太5_4Ts算法定似纳粜


D::始f■带

旺配≯1烈
{142.1431 《14I,14i)

R t、。,,7 92 6。。 -52 3% 92 70
9l









41.14

(14I.14I) (141.141) (】42,143)




870

92二‰

采5-5 is—GA铭法定f?i结粜

,,

鸠 搿 i ,、 岢

匹配 71崔
f|42, 42) f141. 41)

R(~.7)
93 8% 93 6。自 93 3% 92 8% 923%






¨训 j4 ”

(141, 41) (14】, 4I) (】43, 42)




表5-6 MPSA-GA算法定位结_粜
f,

J'2始啦胃

旺配弦置
42, 43
4l,

R 1、S,.j 92 I% 924% 92 8% 9l铲,; 92 60,;



一产一a b


4l

f14】.14

4I, 41
4I. 41




42. 43

需要指…的是,|}1十全f{动金坦球焊机f史JrJ的足周定照H』J,所以光源比较稳 定,4:会对场景图像与模板矧像的距离汁算造成’r.扰。对于光源4i是很稳定的情 况,可以存公式f{i加入’r硝像荻发、f,均硕即可褥到改辫,令:

D(S。,7’)=芝I S。(Sv(^))-D-,一r(sq(^))+厂I
^#I

(5—15)

如㈦,=;套乩(勋(纠,厂={-妇洲))。

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

第五章芯片图像实时定位算法设计与宴现

5.7小结
对模板图像进行抽样实际上抽取了能反应图像本质特征的点,这些点可以 代表模板图像。如此我们在进行相关运算时只需要比较这些抽样点,使可以找到

目标图像,有效的减少了相关运算量。值得一提的是TS匹配算法所j}j运算全部
是加减运算,可以部分甚至全部用硬件芯片来实现。这样我们未来也可以将全自 动金丝球焊机的图像处理系统改为图像计算机处理系统,定位速度将会迸?步提
高。

TS-GA匹配算法和MPSA-GA匹配算法实际上不仅仅是在Ts匹配算法和
M F'SA匹配算法的基础上用GA来进行了算法的优化,GA还可以很好的解决旋

转及尺度变换,并且这两种算法在解决大图像问题上更具有优势。 需要进一步说明的是如果Ts匹配算法采用均匀抽样,比如对模板图像每隔 8个像素点进行抽样。可以不必对模板进行预处理而取得较好的匹配效果,这样
就可以用动态模板来跟踪动态目标物体。即,每识别出目标物体后便将其作为新

的模板匹配下一个目标。均匀采样的实质是降低了图像的分辨率,保留了其基本
特征而忽略了部分细节,同时也起到滤除部分高频噪声的作用,提高了抗噪能力。

中国科学院研究生院硕士论文

第六章结束语

第六章结束语
全自动金丝球焊机是一种芯片后封装设备,由于其焊接速度高达I 20ms/线. 必然要求其图像识别定位系统提供很高的速度及精度。经分析其速度及精度要求 分别为25ms/线及±49in。同时全自动金丝球焊机中芯片存在着许多复杂情况,
如存在芯片旋转、材质以及亮度不同等问题。因此.必须针对这些特殊要求,设 计特定的匹配算法,以期满足上述要求。 本课题在查阅大量文献的基础上,选择了基于灰度的图像匹配技术作为解决

本问题的方法。为了完成全自动金丝球焊机中的芯片图像识别任务,对现有的多 种图像预处理及图像匹配算法进行了研究。在图像预处理方面,主要对图像增强、 边缘检测等多种算法针对芯片图像这个特定环境进行了大量试验,并根据试验结
果对各个预处理环节选择了合适的算法:在图像匹配方面,实现并比较了目前常

用的快速图像匹配算法,包括FFT、幅度排序、SSDA、MPSA和GA匹配算法,
试验表明他们都不能满足系统的设计要求。

对图像匹配原理进行分析研究,发现可以通过两种途径减少模板图像匹配算 法的计算量,即通过减小模板与子图像的相关计算以及通过减小模板在场景图像 上搜索空间的大小来减少匹配过程总的计算量。在此基础上开发了三种改进的图 像匹配算法,Ts算法、TS.GA算法和MPSA.GA算法。通过对实际拍摄的芯片
图像的匹配定位试验,结果表明TS算法能在约为I 8ms找到日标芯片,TS—GA

算法能在约为45ms找到目标芯片。对于二极管的芯片而言,因为只有一个焊盘
所以"FS—GA算法不能满足速度要求,除此之外两种算法无论在实时性还是在定 位精度上都能很好的满足全自动金丝球焊机中图像识别系统的速度和精度要求。

最后,对~幅分别加入了随机噪声、椒盐噪声及卷积模糊普通图像利用三种 算法进行了通用性试验分析,验证了算法有较强的抗噪声能力.很好的适应性,
以及较高的鲁棒性,具有较高的推广应用价值。

由于时间较短,本课题尚有许多问题有待深入研究。例如算法在判断目标有 无的问题上需要进一步改善,也就是说算法的匹配度(相似度)的衡量函数需要
做相应的完善。这是一个很重要的问题,因为如果对匹配度的阈值设置不合理,

那么,不但会导致频繁启动TS.GA算法,浪费较多时问.更重要的是可能造成 误匹配,使得次品率升高。所以下一步的研究重点是改进相似度的衡量手段以及
设计具有自适应性的匹配度阐值。

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院硕士论文

参考文献

参考文献
一、论文部分
【I】赵立初,施鹏飞,余勇.模板图像匹配中的亚象元定位新方法IJ J红外与毫米波学 报、1999,(5).

f2】朱红,赵亦工基于遗传算法的快速图像相关匹配【J】.红外与毫米波学报,1999,
18(2):145一I SO

【3】王延风,何惠阳.孙宝玉等全自动金丝球焊机的CAD/CAE设计研究….光学精密-丁 鞋,2002,10(5):466—470

【4】刘立峰,汤建华全自动金丝球焊机焊接定位系统设计研究[J】光学精密工程,2002,
1 0r6):70-74

【5】Barnea [61 Kashef

D l,Silverman H F A Class Algorithms for Fast Digital Image

Registration[J],IEEE Mapping[J],SPIE,

Trans.On

Comput.,1972,C-21(2):179-186.

B G.A.Survey of New Techniques for Image Registration and

1983,443:222—239.

17J Sung—Hyuk Cha.Efficient Algorithms for Image Template and Dictionary Matching,Jouma J
ofMathematical Imaging and

Vision[J]2000,12:8l一90 Processing[M],Englewood
Cloffs:Prentice—Hall,1996.

【8】K

R Castleman.Digital Image

【9J刘健庄,谢继信,高新波基于Hausdorff距离和遗传算法的物体匹配方法【J1.电子学报,
1996,24(4):1.6.

【10]韩瑞峰,张永奎一种改进的实数编码遗传算法【J】.计算机工程与应用,2002,I 3:78,80 【II】廖美英,郭荷清,张勇军一种整数编码的改进遗产算法【JJ计算机工程与应用,
2003,01:103-106

[I 2J Shill Umeyama.Parameterized Point PaRem Matching and Its Application

to

Recognition

ofObject Families01
136.i44.

IEEEtrans.On PaRernAnalysis andMachineIntelligence,1993,l 5(2)

【13】毛德柱,周凯,张伯鹏基于遗传算法的工件位姿求取研究【J】制造技术与机床,
200I.I:10?I I.

【14】藏铁飞,沈庭芝,陈建军等改进德HausdorfF距离和遗传算法在图像匹配中的应用Ij】北
京理工大学学报,2000,20(6):733.737

[15J罗成平,龚沛曾图像匹配技术【J】.微型电脑应用2000,16(3):26.28,I 1. 【16】李俊山,沈绪榜图像匹配技术研究【J】礅电子学与计算机,2000,2:10.I 3 【17】舒付祥,孙继银一种基于灰度特征的图像匹配算法设计与研究【J】计算机工程与应用
2002.9:10l—102.

f18】胡均安,刘革辨,张道德等实时图像识别技术在片式元件编带机中的应用【J】武汉汽车工 业大学学报,2000,22(6):59—62.
【19】刘道海,孙作龙,黄樟灿图像匹配问题的新算法【J】.武汉理工大学学报.2002,24(1):25—27 f20】Paumard
l J

Robust comparison of binary

images[J].PaRem
to

Recognition Letters,1997,

8(12):1057一1063


【2 l】ROOKS

W.Vision helping the automotive industry

bener

customer

choice[J】Industrial

Robot,f997,24(I):48.5I

尘璺型兰垦塑塞竺堕堡圭篓苎
二、书籍部分 …周春光,粱艳春.计算智能【M】.长春:吉林大学出版社,2001

羔苎兰坠

『21王小平,曹立明遗传算法.理论、应用与软件实现【Ml馥安:西安交通人学出版利
2002

【3】Christian H,et a1.Overview ofImage Matching Technique fMl wwW—DGR?PHTO.1998,10

『4】【日l谷口庆治编束红等译数字图像处理.应用篇[M/北京:科学出版社,2002 Keiji Taniguchi.Digital
Image

Processing【MI.Bering:Science Press,2002(in Chinese)

【5]5李介谷,施鹏飞,刘重庆周像处理技术【M】上海:上海交通大学出版社,1988
【6】马颂德,张正友.计算机视觉【M】,北京:科学出版社,1998.

[7】何斌,马天予,王云坚等擞字图像处理【M J北京:人民邮电出版社,200I.
18】容观澳.计算机图像处理IM】_jE京:清华大学出版杜,2000 【91刘榴娣,刘明奇,党长民.实用数字图像处lltMI.北京:北京理工大学出舨社,200I.
【10】苏光大微机图像处理系统【M】北京:清华大学出版社,2000.
[I I】贾永红,计算机图像处理与分析【M】.武汉:武汉大学出版社,200I.

53

熔铜炉

http://www.txjm-zj.com/

±里型堂堕堕窒生堕堡主堡苎

堕壁

附录部分源代码
图像类;
typedef
struct

taglMAGE{

LPSTR m—pDlBBits; LONG LONG

m—IWidth;
m—IHeight;

}IMAGE;

图像匹配类:
class CMatch


protected:

CMatch(int MaxDegree); virtual-CMatch();
public:
CPoint GetCenterPt()const

{retum m—ptCenter;j
int

GetDegreeoconst (return m—iDegree;};

double

GetFitness()const

{return 111』Fit;};
void

SetSampDest(int

iDestX,int iDeStY)

{m—iSampteDistX=iDestX;
m—iSampleDistY=iDestY;

);
void Leam(LPSTR IpDIBBits,LONG
virtual void

IWidth,LONG 1Height);

Match(LPSTR

IpDIBBits。LONG

IWidth,LONG IHeight)

protected: void

RotateDIB(LPSTR

m—BufferSor,LONG WidthSor,LONG HeightSor

LPSTR m—BufferDst,LONG&WidthDst,LONG& HeightDst,int BYTE

iRotateAngle);

Interpolation(LPSTR IpDlBBits,LONG IWidth,
LONG lHeight,FLOAT x,FLOAT

y):

!=里型兰堕塑塞生堕堡主堡苎
protected:

堕塞

IMAGE+m—ipRotateTemp; im
inI int

m—iMaxDegree;
m iSampleDistX; m iSampleDistY;

IMAGE LONG
LONG

m—iTemp,m—ilmg; m—J Widthl。ine;

m—iHalfWidth,m—iHalfHeight;

CPoint int

m_.ptCenter: m—iDegree; m—dFit;

double

HGLOBAL+m—hDIB; LONG+

m—IRotateTempWidthLine;

);

TS算法类:
class CTSMatch:public CMatch


public:

CTSMatch(int MaxDegree=7); virtual-CTSMatch0;
private:

int
public: void

m—iHop;

SetHop(int iHop) {m—iHop=iHop;};

virtual void Match(LPSTR IpDIBBits,LONG

IWidth,LONG IHeight);

};

TS.GA算法类:
typedefstruct tagCHROM


int

xOff§et: yOffset;

int

double fitness;

55

熔铜炉

http://www.txjm-zj.com/

±里型兰垦竺塞皇堕堡主堡奎——一堕墨
)CHROM

class CTS GAMatch:public CMatch


public:

CTS—GAMatch(int MaxDegree27)
virtual-CTS
private:

GAMatchO;

void

Statistics(CHROM+pop,int

m iGen,double4

BestFit,double+

AveFit);
void void

Sort(double+Data,int DataSize); SelectPop(CHROM+m_pOldPop.CHROM’m pNewPop);

void void
void void

GACreate0; Mutation(CHROM Child); CrossOver(CHROM ParI,CHROM Par2,CHROM+Child); SelectPopKeepMax(CHROM+m_pOldPop.CHROM‘m pNewPop):
FindBestChrom(CHgOM+Pop,CHROM&bestChrom);
EvalueFunctionfCHROM chrom);

void
double

CHROM

SelectPar(CHROM+pop):

CHROM。m_.pOldPop; CHROM
int

m_bestChrom; m_iGen;

double+mJpBestFitperGen;
double+i1-1JpAvemgeFitness;
double
in【

m—dBestFitness;

rrl—iMaxGen;
m—iConstGen;

int

CHROM+m pNewPop;
int public:
viaual m jSearchRnX,m iSearchRn Y;

void

Matcb(LPSTR

IpDIBBits,LONG

IWidth,LONG IHeight);

}:

中国科学院研究生院硕士论文

攻读硕士朝删发袁的论文

攻读硕士期间发表的论文
【1】姜凯,陈海霞,汤建华,。种快速图像匹配算法的设计与实现计算机丁:=程与应用,
2004.8

【2】姜凯,陈海霞,黄波,汤建华.全自动金丝球焊机中芯片图像快速定位算法光电
子?激光,2004l

【3]姜凯’陈海霞,刘立峰,汤建华.基于模板抽样的快速图像匹配算法光学精密T牲、
2004 3

57

熔铜炉

http://www.txjm-zj.com/

中国科学院研究生院颈士论文

致谢

致谢
在论文的撰写和整个研究生学习期间,始终得到我的导师汤建华研究员的悉

心指导和关心。从他那里除了学到了专业知识以外,更重要的是学到了从事科研 工作所具备的严谨的科学态度和实事求是的科研作风,在此致以衷心的感谢。 在光华微电子公司作课题期间,得到了许多同事的支持和帮助,在与黄波、 刘立峰、孙继风、刘轩及王忠生等人的讨论中受益匪浅,使我开拓了视野,能够 系统掌握该方向的专业知识,此外研究生部的老师在我的求学期间也给予了很大
的帮助,在此一并致谢。

在图像识别软件的编写过程中一直得到了吉林大学计算机科学与技术学院 陈海霞同学的帮助,在此表示感谢,同时也感谢我的父母多年来对我无私的关心
和支持。

全自动金丝球焊机中芯片图像实时定位方法研究
作者: 学位授予单位: 姜凯 中国科学院长春光学精密机械与物理研究所

引证文献(4条) 1.钟雪灵.鲍苏苏 芯片焊接中焊点自动定位技术的研究[期刊论文]-计算机工程与设计 2009(11) 2.钟雪灵.鲍苏苏 半导体生产后工序设备的自动化改造方案[期刊论文]-计算机技术与发展 2006(6) 3.钟雪灵.鲍苏苏 自动焊机中芯片识别技术的研究[期刊论文]-计算机科学 2006(11) 4.钟雪灵 自动焊机中定位技术的研究[学位论文]硕士 2005

本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y685689.aspx 授权使用:吕先竟(wfxhdx),授权号:06b708d5-2c3f-4b5c-80a0-9e49014b8467 下载时间:2010年12月11日

熔铜炉

http://www.txjm-zj.com/


赞助商链接
相关文章:
数字图像叠加技术研究
图像目标位置的标定,运用了数字图像 叠加技术标定图片...比如,在视频监控系统中,监控设备不仅能实时的显示...论文中涉及到的关于这款芯片的使用方法,CMOS 图像...
基因芯片相关图像技术的简单介绍
人工难以识别和处理,因此多采用自动化手段进行处理,包括图像技术 和计算机技术。 ...通过对芯片图像中荧光的位置,颜色、强弱 进行分析可以推测基因芯片上探针发生反应...
HKD-2320TS型超声波金丝球焊机-说明书
系列超声波金丝球焊机主要应用于发光二极管、 中小型...在 第一焊点瞄准位置分步与自动可以互相切换。具有...2. 劈刀安装 劈刀安装方法(见 16) :劈刀上端面...
超声波金丝球焊线机
超声波金丝球焊线机 超声波金丝球焊线机的组成与使用 基本原理 超声波金丝焊...位置连接紧密并破坏焊接面表面的污染物,使之适 合焊线,压是指瓷嘴对芯片的...
基于FPGA的图像处理现状分析
关键字:FPGA,图像处理,实时,硬件设计. 1 引言 随着数字多媒体技术的不断发展,数字图像处理技术被广泛应用于航空航天、通信、医 学及工业生产等领域中,新开发的...
全自动键合机工艺调试方法
先进后封装技术,如多芯片封装和系 统级封装(SIP)都对引线键合技术、工艺等...本文中进行调试的全自动金线键合机是以热超声球焊 为工艺基础的金丝球焊机。 ...
球焊
球焊_经管营销_专业资料。3303A型 03A型 超声金丝球焊机 使用说明书 深圳市亿洋...5 焊接动作程序:焊接动作如下顺序进行,如下图所示。 6 5.1 初始位置 每次第...
基于MATLAB的图像处理及跟踪算法
图像进行阈值处理(图像分割) ,再对分 割后的图像求取形心,以对目标图像进行定位,并最后找到各幅帧图像的目标位 置方法,从而实现对 100 帧视频图像实时...
基于MATLAB的图像区域特征检测
图像中区域特征检测与提取技术研究摘要: 数字图像处理...在航天应用中:军事侦察、定位、导航、指挥;多光谱...逐渐向多维成像的方向发展;在硬件芯片上 的应用将...
基于机器视觉的工件识别和定位文献综述_图文
伴随着工业机器人研究技术的成熟和现代制造业对自动...实时性要好,所以更适合工件的在线检测、识别、定位...年代, 60 Roberts 通过计算机程序从数字图像中提取出...
更多相关标签: