汪 松，王俊平，万国挺，王 乐

(西安电子科技大学通信工程学院，西安710071)

近年来，随着匹配技术的迅猛发展，图像匹配在全景图合成、物体3D重建、航空摄影测量、三维地图制作等领域具有广泛应用［1］。因此针对图像匹配技术的研究从未停止。

目前图像匹配方法分为基于灰度的图像匹配方法［2］、基于特征的图像匹配方法［3］和基于解释的图像匹配算法［4］。文献［2－5］详细介绍了基于灰度的匹配方法，但这种方法对图像变形、光照、尺度变化等情况有一定的敏感性。因此不具有适用性。由于基于解释的图像匹配算法应用较少，并且该方法需要建立在图像自动判读的专家系统上，目前还没有取得突破性的进展。基于特征的图像匹配方法，如 CCH算法［6］、Harris算法［7］、SIFT算法［8］等都能够较好的适应图像变形、光照变化等情况，而且技术比较成熟。Mikolajczyk等［9］对以上算法做了系统的比较，结果表明SIFT算法检测效果最好。但SIFT算法存在匹配点数量有限、算法效率低、精度差、并且在特征点分布均匀的情况下正确匹配率低。人们提出了很多的匹配方法以解决上述问题带来的匹配困难。根据Brown［10］理论，各种匹配方法都是特征空间、相似性度量、搜索空间和搜索策略4个关键要素的不同选择组合。因此，笔者依据Brown理论，在设计匹配方法时，首先在特征点提取前对待匹配图像进行匹配预处理，然后基于简化SIFT算法在搜索策略方面进行了改进，采用KD树双向匹配方法，在匹配点数量、匹配点的精度和匹配重复点方面都有所提高。笔者通过对有共同缺陷的版图进行图像匹配实验，并验证得到了较好的效果，最后将该方法应用于优化版图的线网自动检测方面，进一步验证了该方法的适用性。试验证明该方法不仅满足图像拼接等相关领域对匹配技术高精度、高准确率的要求，而且在集成电路版图优化线网检测领域也有较好的适用性。

1 图像匹配预处理

图像在成像过程中易受到随机噪声、成像传感器变化以及在不同时间受到不同环境的影响，使所得到的原始图像都不是理想的待配准图像，这些图像间的差异可能会使后面的配准产生错误的结果或无法配准。所以在进行图像匹配之前，对原始图像进行预处理是非常必要的，图像预处理也是图像配准整个过程必不可少的环节。为减少噪声，增强图像边缘特征信息，提高匹配点的精度和数量，经实验笔者对图像进行高斯和Wallis滤波处理，这样特征提取效果较好。

1.1 高斯滤波

高斯滤波的实现方法比较常见，这里不再累述，把处理前后的图像列出，如图1是一幅480× 421像素的缺陷版图。高斯滤波后的图像如图2所示。直观上看，图2的噪声已被滤除，但边缘有些模糊，这是后续进行Wallis滤波所需步骤，实验结果表明这样的预处理效果提高了图像匹配点数量和精度，并不影响原始图像的边缘信息和匹配点在原始图像上的显示。

图1 高斯滤波前缺陷版图Fig.1 The former defects territory of the Gaussian filter

图2 高斯滤波后版图图像Fig.2 The Gaussian filtered territory image

1.2 W allis滤波

高斯滤波后的图像存在一定程度的边缘模糊等问题。考虑到Wallis滤波是一种局部的影像变换，它可增强影像的纹理模式和影像反差同时压制噪声，提高了影像的信噪比。因此笔者采用Wallis滤波器处理图像2。Wallis滤波器的一般形式为［11］:

其中g(x，y)为原始图像的灰度值;f(x，y)为Wallis滤波后图像的灰度值;mg为原始图像的局部灰度均值;sg为原始图像的局部灰度方差值;mf为结果图像局部灰度均值的目标值;sf为结果图像局部灰度方差值的目标值;c∈［0，1］为图像反差的扩展常数;b∈［0，1］为图像的亮度系数。

图3为Wallis滤波后图像。可发现图2模糊的边缘信息经过滤波后边缘更加突出、版图缺陷更加明显、纹理更加清晰，这为特征点的提取提供了更多的点、边缘等特征信息。

图3 W allis滤波后版图效果图Fig.3 W allis filtered territory effect diagram

2 特征点提取与匹配

SIFT算法分为构造尺度空间、极值点检测、精确确定极值点位置、特征点方向分配、生成特征点描述子［8］5个步骤。

从文献［12］中可知尺度空间的构造大约占总时间的30%～55%，优化空间较大。为提高提取特征点的效率，笔者根据文献［12］采用简化尺度空间的SIFT算法提取特征点，即取高斯金字塔的组数为2，每组3层的固定金字塔进行尺度空间的构造。表1列出了传统 SIFT算法和简化SIFT算法完成匹配的时间。

表1 一般SIFT和简化SIFT耗时对比Table 1 run time of SIFT and simplified SIF

从表1可看出简化SIFT的耗时为一般方法的1/2，在算法效率方面有所提高。实验验证简化后的SIFT算法提高了效率，而且特征点的数量并不比一般SIFT算法少很多。

一般特征点匹配采用单向匹配方法，匹配方法简便，但容易产生误匹配，而且由于一个特征点可能具有多个方向，在匹配时可能产生重复的匹配点。笔者为提高图像匹配的准确率，采取双向匹配方法，即基于单向匹配结果，反过来求第2个特征集中已被匹配的特征点在第1个特征点集中匹配点，距离比小于某个阈值的特征点为正确匹配点［13］。双向匹配方法既去除了重复匹配点，又提高了匹配准确率。图4为一般SIFT算法对缺陷版图提取特征点的图像效果，共得到802对匹配点，经过RANSAC剔除后有665对正确匹配点。图5为笔者方法提取特征点的图像效果，共得到2659对匹配点，无错匹配点。

图4 一般SIFT方法缺陷版图匹配效果Fig.4 The general SIFT method defects territory matching effect

图5 笔者方法缺陷版图匹配效果Fig.5 The author method defects territorymatching effect

3 笔者算法在优化线网检测的应用

随着集成电路复杂度与芯片面积的增加和亚波长光刻技术的广泛应用，导致集成电路(IC)成品率降低，进一步影响了半导体产品市场竞争和质量［14］。版图优化的目标是在不改变电路性能的情况下，调整版图上的布线使关键面积降低，从而提高其成品率，因此，版图优化对提高IC成品率具有重要的研究意义［15］。

版图优化主要是通过对版图结构和线网位置的改变来达到减小面积、延迟和功耗的目的。对于优化后的版图进行移动线网的检测也是版图优化中不可缺少的步骤。笔者通过该方法对优化前和优化后的版图进行图像匹配，然后以匹配点对的位置关系检测移动的线网。如图6为优化前的版图，图6中绿色线框内是需要优化的线网，图7为线网移动后的优化版图。同图6相比图7中的线网进行了简单的平移，先通过该方法对图6和图7进行匹配，然后根据线网上的一对匹配点R-1、L-1的坐标关系可以检测出线网在x，y方向的平移量。如表2所示，列出了x，y的坐标和平移量，以像素为单位。

图6 优化前的线网Fig.6 Line network before optim ization

图7 优化后的线网Fig.7 Optim ized reticle

表2 匹配点对x，y坐标与平移量Table2 the coordinates and shift ofmatched points

4 实验结果与结论

匹配方法的性能评价指标有匹配正确率、匹配时间和匹配精度3方面。为验证笔者方法，针对有缺陷的版图图像从这3个方面进行检验。实验结果表明，该方法提取的匹配点在数量、准确率等方面都优于一般SIFT算法。该方法是一种有效的图像匹配方法，具有精度高、鲁棒性强、稳定性高、适用性强等优点，并在优化线网检测的应用得到较好效果。同时，该方法为图像拼接等相关领域后续产品的生成提供了精确的匹配点。在匹配时间方面由于该方法的特征点数量较多，所以匹配耗时较多，对该方法的实时性还需要进一步的研究。

［1］苏宇.基于特征点的图像拼接技术研究［D］.西安:西安电子科技大学，2008.

SU Yu.Research on image mosaic based on feature points［D］.Xi’an:Xidian University，2008.

［2］Mortani M，Sationh F.Image template matching based on ratio ofmean and cent－ral pixel in local area［J］. Proceedings of the SPIE－The International Society for Optical Engineering，2007，67(94):1－6.

［3］Barbara Zitova，Jan Flusser.Image registr－ation methods:a survery［J］.Image and Vis－ion Computing，2003，21(11):977－100.

［4］王宏力，贾万波.图像匹配算法研究综述［J］.计算机技术与应用，2008(6):17－19.

Wang Hong－Li，Jia Wan－bo.Study on image matching algorithm［J］.Progress of comp－uter technology and Application，2008(6):17－19.

［5］Shimizu Masao，Okutomi Masatoshi.Multi－Parameter simultaneous estimationg on area－based matching［J］. International Journal of Computer Vision，2006，67 (3):327－342.

［6］C R Huang，C SChen，PC Chung.Contrast context histogram－A discriminating local descriptor for imagematching［J］.International Conference on Pattern Recognition，2006(4):53－56.

［7］Marco Loog，Francois Lauze.The improbability of harris interest points［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(6):1141－1147.

［8］Lowe D G.Distinctive image features from scale－invariant keypoints［J］.Inter－national Journal of Computer Vision，2004，60(2):91－110.

［9］Mikolajczyk K，Schmid C.A performance evaluation of local descriptor［J］.IEEE Transactions on Pattern A－nalysis and Ma－chine Intelligenee，2005，27(10):1615－1630.

［10］Brown LG.A survey of image registrati－on technique［J］. ACM Computing Surverys，1992，24(4):325－376.

［11］Han X，Wu QS，Feng N.Fastwallis image enhancement algorithm with CUDA［J］.Journal of Shenyang Shenyang University of Technoloy，2011，33(3):293－298.

［12］曹世翔，江洁.一种简化SIFT的图像配准算法［J］.红外与激光工程，2010(4):35－39.

Cao SX，Jiang J.A simplified SIFT algorithm for image registration［J］.Infra－red and Laser Engineering，2010 (4):35－39.

［13］Iftikhar Hussain，Muhammad Zubair，Jamil Ahmed.Bidirectional exact pattern matching algorithm［C］//Modern Problems of Radio Engineering，Telecommunicaions and Computer science.Ukraine，2010:293－296.

［14］Wang Jun－ping，Hao Yue.Short critical area computationalmethod usingmath－ematicalmorphology［J］.CIS，2005，38(2):796－803.

［15］Barnt T S，Bickford J，Weger a J.Product yield prediction system and critical area database［C］//Advanced emiconductor Man－uacturing Conference，2007:351－355.