通用计算机的性价比在最近几年内已经达到了一个程度——如今可被轻松执行的图像分析算法在过去由于太大的计算量而不切实际。同时，传统的模式定位和检测工具例如blob（斑点）分析和NC(normalized correlation—正规化相关性)的局限性变得日益明显，包括一些机器视觉未能解决的潜在应用，以及来自对已经应用的很成熟的传统工具如何做进一步改进的瓶颈。

灵感来自于新的计算能力及其对上述局限性的反映，我们开发了一系列图像分析算法，为定位和检测目标提供了切合实际的通用工具。一般来说，新方法是一种几何图形对比的形式。避免了传统的用来描述和匹配模型的灰度值像素网格的方法，新技术能处理几乎所有的方位、尺寸、阴影的任意变化，得到更高的精确度而且不影响其鲁棒性，并且具有操作方便快速等优点。

如此陈述并不能帮助潜在用户理解此项新技术。传统方法的局限性是什么呢？建立模式匹配（图形对比）的确切目的是什么呢？如果不匹配摄像机获取的灰度值网格，那么又是如何工作的？如何评估几何图形对比工具，看它是否能得出所要求的结果？新技术能应用于什么样的实际场合？本文将一一回答这些问题。（上图为Bill Silver （Senior Vice President of Research & Development and Senior Fellow）

克服传统的局限性

为了了解这项新技术，有必要在各方面将它和传统方法做比较，因为大家对传统方法更熟悉。下面的概要将几何图形对比放置到适当的地方进行比较。

Blob分析

Blob分析是最早的广泛用于工业环境的目标定位和检测的视觉工具[1]。前提是将像素以某种方式简单地归类为目标或背景，使用领域连接准则将归类的像素作为离散目标，通过计算连接目标不同的矩来确定目标位置、尺寸和方位。Blob分析的优点在于速度快、精确度之高能达到亚像素级别（在图像未退化情况下）、易于训练、能够允许方向和尺寸的改变。缺点在于不能允许目标相互接触或重叠，对于存在的各种形式的退化图像的执行效果不好，不能确定某种特定形状物体的方位，作检测和识别时区分目标的能力不强。

然而最严重的问题可能是，在实际中将目标从背景分割出来的最为可靠的方法是将目标相对于背景设定为全白或全黑。这就严格地限制了潜在的应用范围，此后不久开发了目标定位和检测的其他方法。

模板匹配和正规化相关性（NC）

模板匹配方法起始于训练步骤，其中存储一幅待定位的目标图片（称为模板）。程序运行过程中将模板和类似的图像子集在一定范围内进行比较，最匹配的位置被认为是目标的位置。匹配程度（具体的数值）可被用于检测，就像在模板和位置最匹配的图像之间的单独像素的比较一样。

最早的模板匹配使用灰度阈值将模板和像素简化为两种状态，“白”或“黑”，因此比较操作能够在硬件上得到实时处理。不幸的是，要使阈值步骤达到亚像素级别的精确度是不切实际的，需要操作员人工选择阈值，这样的结果由于照明和目标反射率的变化而变得异常不稳定。

在1987年随着引入NC（规格化相关性）方法作为模板比较运算，上述局限性被克服。NC带来相当大的计算量一方面来自于复杂的搜索算法，另一方面来自于不做乘法而能计算相关性的一种简单设备的发明，这在当时是相当的复杂[3]。

NC模板匹配克服了很多blob分析的局限性，能够允许物体之间相互接触或重叠，即使存在各种形式的图像退化也能执行的很好，NC匹配值在一些检测应用中是非常有用的。最值得注意的是，目标不再需要根据灰度值从背景中划分出来，使应用变得更加广泛。几年之内NC便成为工业中模板匹配统治性的方法，特别是在半导体制造业和电子产品装配业。

不幸的是，NC放弃了blob分析的一些重要的优点，特别是放弃了在允许和测量方位和尺寸的变化方面的能力。NC能够允许小的变化，像很小的角度以及很少的百分比（根据特殊模板），但是甚至这么小范围的方位和尺寸的改变都将导致结果精确度的迅速下降。

通过旋转和缩放模板的比例，1991年出现的一种扩展的NC方法能部分地克服上述局限性，可用来测量方位和尺寸[4]。然而，原始方法及其扩展都很费事，并没有广泛地用于实际生产。此外，方位的精确度大约为一度，尺寸大约为几个百分数，位置精确度通常要比在没有旋转和尺寸变化的情况下低一些。

精确度和代价问题根据用来表示模板像素网格的类型决定。网格能被平移、旋转、仅作近似的比例缩放（除了整体平移和缩放因数外）。这样的操作不仅会引入畸变而且相当费事。

NC模板匹配基于物体的阴影定位物体（例如，灰度模板）。对于理想的2D物体像打印纸或硅晶片，阴影通常由照明强度和表面反射率决定并且依不同的情形而改变，这样NC便能处理的非常好。对于3D物体通常像机器人的拾起和放置以及装配应用，阴影取决于更多的因数，包括照明方向，表面方向，阴影以及相互照明等。在这些应用当中，物体的阴影变得相当的不可靠，即使物体的阴影是一致的，但也不适合NC。

特殊图形查找

通过使用Hough变换[5]，某种指定的形状如线形和弧形能克服blob和NC的一些局限性。能被这种基本形状描述的目标通常在任何方向都能被定位，此方法已经成功地应用于某些机器人系统中。然而，这种方法也有其局限性，例如缺乏一般性、训练复杂、图像退化时处理变得困难以及对速度的要求。

需要一种通用的方法

上述的每种方法都有其局限性而无法应用于许多需要使用视觉的场合。在机器人应用中，例如，NC不能处理阴影变化，在处理方位和尺寸变化时存在着成本和精确度的局限性，这些都完全地妨碍了它们的应用。在一些使用背光的场合下能够使用blob分析，特定模型查找方法在一些场合下已经得到成功的应用，但对于大多数机器人制造商来说，还是得采用机械固定和推算定位。

甚至在NC应用得极为成功的半导体行业中，仍然存在严重的局限性。一些处理过程例如CMP，导致阴影变化率超过了NC所能允许的范围。几乎所有的应用都存在一些方位上的变化，因此必需接受以充分地降低精确度和复杂度以及时间消耗过程为代价来测量方位。尽管当今工厂的仪器都相互联网了，在一台机器上训练的模板下载到其他机器上的需求会受到光学放大倍率带来的不可避免的精确度降低的阻碍。

几何图形对比

就像我们所看到的那样，NC具有许多优秀的性质而且应用的非常成功。但是受到其基于的灰度值的像素网格算法的限制。阴影是目标最不可靠的属性之一，尽管目标的形状是一样的但阴影却是多变的，并且网格不能非整数平移。

几何模板匹配通过以几何形状、独立的阴影以及不依赖离散网格描述物体的方式来避免上述的限制。几何模板匹配重新拥有了blob和NC所没有的允许和测量在方位和尺寸上存在变化的能力，保留了速度、鲁棒性、易于训练和NC的通用性，而特定目的模板查找器不存在通用性；增加了允许阴影任意变化的能力；当方向和尺寸变化时能得到相当高的精确度；提供检测的详细缺陷数据，使方向、尺寸和阴影变化不受约束。

经过4年所面临的挑战和发展，开发了通用目标的定位和检测。移除了传统应用发展的屏障，开创了机器视觉应用的新领域。

工作方式

全新的几何图形对比技术包含了5个新的图像处理算法：特征检测、训练、仿射搜索、位置精化和检测。这些模块对其操作及其属性和行为的定义很关键，下面做些必要的解释。

特征检测

特征检测是PatMax几何图形对比的架构，定义了系统的所见，如果你不能看到那么你什么也不能发现。特征检测对物体的边缘提出了一种几何描述——轮廓边缘点的序列表分割图像的不同区域。不同于传统的边缘检测，只是简单的标记某些像素为边缘，特征检测中每个边缘点都指定了位置和方向为其实际坐标值（在适当精度范围内）。

依靠图像检测时像素的粒度来判定边缘的存在和定位。例如，图2显示的QFP（四方扁平封装quad flat pack）的引线端，QFP是一种用于电子装配应用的器件。在图2a中，以某种粗糙粒度（coarse granularity）为阈值进行特征检测操作，一组引线被检测为一条边缘。在图2b中（放大两倍看），以精确粒度（fine granularity）为阈值进行特征操作，每条单独的引线都被检测为一个边缘。两种结果都是正确的，对于给定的检测图像PatMax将给出一个粒度范围阈值。

粒度（granularity）的重要性在图3中更明显，图中显示的是一个复杂纹理的金属零件局部的例子。此处边缘点可以被认为是显示其位置和方向的小的片断。目标的几何描述仅仅对粗糙粒度——精确尺寸而言有意义。唯一可见的是随机纹理。而传统的边缘检测则不能检测出来。

训练

训练的目的是选择合适的粒度范围使检测出的目标有意义，选择不同的粒度表示物体特征。这也是几何图形对比最具挑战性的任务，因为需要做大量的判断而不是简单的测量。当然你也可以人工地选择粒度范围，但是根据NC模板匹配的经验显示，机器操作员进行的模式训练不能比在目标上画框更复杂。因此，训练选择必需完全的自动化，遇到特殊情况时才求助于人工解决。

精确搜索

特征检测得出几何描述—一是一系列概念上的位置和方向的实际值，能够被平移、旋转、缩放、伸展以及其他一些不失保真度的任何变化。实际上我们使用6自由度的仿射变换，包括2自由度的平移和1自由度的旋转、缩放、特征比和形变。而形变是很少使用的，为了方便起见我们用水平和垂直缩放比作为单独的自由度替代特征比。

每个非平移自由度或者指定为固定值或者为某个范围的值进行搜索。固定自由度的值能带来不需要时间补偿和额外训练模式的训练模型的平移方案。例如，通过为自由度缩放设定适当的固定值，简单的方形模式被训练后可用来查找已知尺寸和形状变化的矩形目标。

如果物体的方位、尺寸和/或者特征比可以被调整，可以为适当的自由度指定搜索范围。搜索时间通常和搜索空间大小成比例，当然空间可以根据具体应用在2维到6维之间变化。通常只对其中3维和4维感兴趣，例如(512 像素) × (512 像素) × (360度),和(512像素) × (512 像素) ×(360度) ×(2:1 比例)。

很明显面对如此巨大的搜索空间主要的挑战是速度，我们很谨慎的选择了MMX汇编程序语言进行编程。我们放弃定制硅片，不仅因为昂贵，还包括其不能跟上Intel无情的性能进步，也不能满足PatMax的第四代run－time图像分析算法复杂的需要。

位姿精化

一般的算法能够迅速地覆盖大量搜索空间但不能得到精确的结果。为了避免这种折中性，我们设计的仿射搜索能够以尽可能快的速度运行，建立全新的几何匹配算法，位姿精化——其唯一目的是为了获得高精确度。使刚性变换下的几何描述的保真度达到了极限。

当然，精确性主要还取决于例如模型尺寸和图像退化度等实际应用条件。硅晶片模型的实验显示我们能够达到绝对的3S精确度，例如0.025的像素平移、0.02°的方位和0.05％的尺寸精确度。实验中，我们特意测试了来自训练模型的不同方位和尺寸（方位和尺寸同步）的实时图像的平移精确度。精确度并不因方位和尺寸的变化而受影响，同样地满足几何匹配。在同样的条件下任何技术都不能达到如此完美的结果。

检测

检测算法在实时图像和训练模型图像的边界点建立相关性，再利用相关性评估每个边界点。不同于基于网格模板比较算法，检测算法在方位和尺寸变化下不失保真度，不损失边界保真度以及不受阴影变化的影响。

如何评价几何匹配

随着几何匹配的概念被接受并在工业领域内普及，潜在用户能够评估这类生产商主张的系统。下面是评价或比较几何匹配技术需要关注的一些方面。

测量方位和尺寸

性能优秀的几何图形对比工具应该允许360度的方位变化，而不应该附加任何限制条件。尺寸变化会受限于相机视场和分辨率，也可能还有其它的限制条件，但不应该覆盖过宽的范围。同样也不应该不支持特征比的变化，尽管你的检测物体并没有这么多的变化。简化训练是为了能够使用标准的合成模型并且在运行时自动地调整几何结构。

精确度不受方位和尺寸影响

当方位和尺寸固定不变时很多工具都能得到很高的精确度，几何图形对比的一个重要性能是精确度在这些条件改变的情况下仍不受影响。这个性能非常重要因为在大部分实际应用中方位和尺寸等条件都会或多或少的改变，如果方位和尺寸的精确度（例如NC算法）低于一定程度时，几何匹配的意义将不复存在。改变光学放大倍数和相机角度可能会使模板分散，因此精确的几何匹配对网络化的工厂生产更加重要。

速度

如果速度太慢，测量方位和尺寸的能力显得不那么重要。现代的PC机处理2自由度变化不成问题（仅做搜索处理），因此能做3或4自由度的搜索才显得意义重大。

阴影变化尺度

几何图形对比应该允许阴影存在大范围的变化，例如可能发生在金属零件位置不固定时，或由于晶片处理的CMP步骤时。对于限制尺度改变允许和额外特征，物体接触和重叠，例如NC模板匹配方法擅长于处理此类情况。进行几何匹配转换时也应该保留这些优势。

允许图像退化

噪声，严重散焦和过低的对比度都强调了特征检测的重要性。尽管你的应用中可能不存在这些问题，但将其作为鲁棒性测试也是个不错的注意。不清楚边缘的容限模型，不清楚边缘的模型，如图3所显示的特征检测的最终强度测试。尽管物体边缘质量可能很差或改进后也不明显，这就是很好的测试例子。能够操作粒度范围的特征检测器（查找器）也应该能够处理这种情况。

显示训练

NC模板匹配的一个好处是只要在图像上画一个简单的方框，模型就能够被训练。训练一个几何图形对比就应该这么简单。注意到向导和模型编辑工具，尽管在特定环境下非常有用，但不应该处处都使用。对大多数机器视觉工作人员而言已经存在很多挑战，没有必要再花时间去学习使用这些训练工具。

生成检测的缺陷数据

在方位、尺寸和阴影变化的情况下查找缺陷的能力对多数实际检测应用是有必要的。在PC上运行。如果模板匹配工具在一台普通的没有特殊硬件的PC上运行，必须确保你能够跟上Intel的高速发展步伐。从不能跟上Intel步伐的小公司制定加速器时要谨慎。

市场认同

最后，市场才是品质的最好审判官。确保调查几何图形对比的实际安装情况。

实际应用

几何图形对比已经得到全世界几百个应用实例的证明，包括半导体、电子、汽车和食品包装行业。这只是其中一些例子。更多的信息可以咨询参考指示。

KLA/Tencor将晶片模型定位到薄片测量机器上，薄片经过处理过程后从根本上改变了模板的形状，使NC模板匹配变得不再适合。

Ganton Technologies（Sturtevant市,WI州）将任意方向的发动机零件定位到机器人的自动控制单元[7]。由于零件的阴影和方向的改变使传统的视觉技术不能胜任此项任务，因此单元最初是由12个单独的机械夹具构成，既昂贵又不灵活。

Modgal公司（以色列的Golan Heights）经营金属波导管接头的机器人拾起—放置项目[8]。原来的视觉系统被PatMax所替换，因为原来的系统不能处理由于阳光变化而带来的零件阴影变化问题，以及零件角度变化问题。

IBM Microelectronics（Burlington，VT）检验半导体电路芯片焊接到导线架上的准线。实际应用中的芯片模型和导线架模型层叠，但每个模型必需以高精确度来单独定位。芯片和导线架单独地训练，然后再将两者模型定位到实时的同一幅图像中。

ABB（瑞典的Vasteras市）引进了新的FlexPickerä机器人作为简单的任意方向的食品包装和药物的应用[9]，[10]。产品观念需要机器视觉指导，但传统的模型查找方法并不适合。

福特发动机公司（加拿大的Windsor铝厂）引导机器人装载27kg非固定箱子的铝发动机模块到固定的传送带[11]，[12]。该应用需要使用自动化机器人来达到降低成本、提高质量和人员安全等目的。机器人需要机器视觉导航。传统的机器视觉工具由于受到阴影和方位变化的影响而不适合此实际应用。

参考文献 [1] Horn, B.K.P. Robot Vision. MIT Press, 1986, chapter 4. [2] Silver, W.M. "Normalized Correlation Search in Alignment, Gauging, and Inspection". Proceedings of SPIE, Volume 755, January 1987, pp. 23-34. [3] Silver, W.M., R.A. Wolff, and R.E. Dynneson. "Digital Image Processing System". U.S. Patent #4,972,359, November 20, 1990. [4] McGarry, J. News Release, Acumen 900 series, October 22, 1991. [5] Hough, P.V.C. "Method and means for recognizing complex patterns." U.S. Patent #3,069,654, 1962. [6] Ballard, D.H. and Brown, C.M. Computer Vision. Prentice-Hall, 1982. pp. 75-81. [7] Robotics World, March/April 1999, pp. 20-25. [8] Manufacturing Engineering, March 1999, pp. 154-156. [9] Machine Design, March 11, 1999, p. 176. [10] ABB Flexible Automation, FlexPicker IRB 340 Industrial Robot product brochure, 1998. [11] Automotive Engineering International, February 1999. [12] Quality, April 1999, pp. 120-121.