控制网

引言

    图象匹配是在计算机视觉和自动目标识别领域中广泛应用的识别定位技术，主要是在给定初始目标信息的情况下，能在后续图象中自动找到目标区域。目标位置通常用相对于视场左上角的偏移、旋转角度和放大比例等几个参数来描述。

    当前，图象匹配主要方法有特征匹配方法、基于平移模型的相关匹配方法等。特征匹配方法一般应用于待匹配图象目标有较明显的几何特征，例如亮度特征、区域特征、边缘特征、点特征等请情况。首先按照相同的特征提取准则在输入图象和模板图象中提取特征，再根据两者特征的对应性得到一个超方程组，然后可以通过一些诸如最小二乘法、最小错误方程法等优化解法得到位置参数。定位将相对容易一些。但是，当目标处于复杂背景中，或者没有明显几何特征时，这种方法的应用受到很大的限制。此外，当出现新的特征或者部分特征丢失等情况下，特征之间的对应性将难以确立。本文论述的基于区域的仿射模型定位方法能够在复杂背景中获得较高的匹配精度，可以作为互相关算法的改进型。

1 仿射变换定义及其性质

    仿射变换是射影几何中的一种基本变换，其定义是：若变换 ， ， 是非奇异线性变换，  ,则变换 称为仿射变换。
二维欧氏空间上的仿射变换为：
                            (1)
其中，
 ， ， 
式中的 都是实数。

    仿射变换具有平行线转换成平行线和有限点映射到有限点的一般特性。平移，旋转，缩放，及错位等都是二维仿射变换的特例。

2 误差评价方法

    传统的误差评价方式往往容易受到极个别大误差点的影响，而不能够有效考虑整体的情况。降低个别较大误差点的影响，必须考虑在映射函数上对其进行抑制。考察函数误差映射函数：                                (2)

    函数曲线表示为：
 
图1   曲线

    实线表示 对应的曲线，虚线表示 对应的曲线， 值控制该函数对误差的抑制范围， 值越小对误差值抑制的程度就越大。再采用 函数计算上面图1的例子得到，(b)相对于(a)的 值为0.988，而(c)相对于(a)的 值为1.241，大于真正的目标图象的误差，这种评价方式是合理的。

3 迭代求解算法

    这种方法的突出优点是在目标真实位置附近能够快速收敛，并且可以获取非常高的定位精度。缺点是该方法是局部收敛的，必须要有目标的先验位置知识。

    以模板图象中心为坐标原点建立坐标系，那么模板图象表示为 。模板图象中的点 经仿射变换后，变为输入图象中的点 ，其中位置 和 之间存在仿射关系： 。 为 和仿射系数 的函数。 和 是相对于模板图象中心的水平和垂直坐标， 和 表示仿射变换后的图象在水平和垂直方向的变化量。

    若用 来表示模板图象 经过仿射变换后在输入图象中的对应区域，则在灰度不变性前提下有公式成立：
                         (3)

    至此，模板目标图象和输入图象之间的仿射关系就建立起来了。

    基于梯度下降的算法是一种局部收敛的算法，计算时需要一个参数的初始估计 。采用迭代递归方法来求解最优的仿射参数 ：

    设 ，参数 为仿射参数 的两次估计值之间的差，称为仿射增量：
                         (4)     参数 仍然采用迭代过程来计算。采用公式(3.11)所示的误差评价函数：
  
                         (5)

    对误差评价函数表达式中 的各分量分别求偏导可得：
   (6)

    令  ，得到含有未知变量 的方程，

    再采用高斯牛顿迭代法求解 ：
                          (7) 其中 ， 的调整增量 ， 
  

    (8)其中 部分计算较繁琐，可以用 来代替。

    总结上面各计算分项，得到总的计算公式：
 
      (9) 

    参数 的迭代计算收敛之后，就得到了第 次仿射参数 。继续计算 ， ，……，直到 ，得到参数 的最优值。

4 迭代求解算法分析

    本节的目的是在分析算法的基础上，尽快提高算法的执行速度。下面首先来具体分析迭代求解参数 公式中的各个部分，以及详细求解方法。 

    1）   表示第 次计算得到的目标图象，是按照第 次仿射参数到输入图象中截取的目标区域。根据已知仿射参数，模板图象中任意点在输入图象中对应点的坐标可以由下式求出：
       （10）

    假设模板图象中水平相邻两个象素点 和 ，则经仿射变换之后在输入图象中有对应的两点 和 。不难推导，有如下关系式成立：  。同理假设模板图象中竖直相邻两个象素点 和 ，则经仿射变换之后在输入图象中有对应的两点 和 ，有如下关系式成立：  。因此，可以得到结论：输入图象中经变换后的两点坐标差只与模板中对应点的坐标差有关系，而与对应点所处位置无关。也就是说，只要计算一次仿射变换，得到目标左上角象素点的在输入图象中的位置，其它象素点的精确位置就可以采用增量法来求出。因此，除了第一个点以外，只需要计算两个浮点加法就可以完成一个仿射变换点的精确位置。
仅仅获得了精确的位置还是不够的，还需要利用双线性差值法来获取相对精确的灰度值。
 
图2  双线性插值示例图
 
  (11)
 ， ， ， 分别表示图2中1，2，3，4点的灰度值。

    因此，对一个目标象素点，只需要计算3次乘法运算和6次加法运算就可以获得基于双线性插值的结果灰度值。试验发现，算法对目标图象灰度值的精度要求较小，只取整数部分就可以基本上满足算法的需要。

    利用双线性插值来求解精确图象，是整个算法中最耗时间的部分。究竟是采取双线性插值法还是采用相对简单的最近邻法来计算，需要根据具体情况来分析。根据实验情况来看，当模板图象较大时（3000个象素点以上），采用双线性插值法来求解目标图象有较大的时延。双线性插值法在对比度较低、图象纹理不丰富、目标变化幅度较剧烈的时候表现比较突出，比最近邻法收敛要快得多，总的计算时间也要略少。但是采用大模板时，双线性插值法耗费的时间将它所带来的便利抵消掉了，整体上就比采用最近邻法略慢。

    2）差分图象 ，包括水平差分和竖直差分两部分，即 ，为两个列向量，分别表示水平和竖直方向差分图象。利用下面水平和竖直算子来求解差分图象：
  
(a)水平差分算子       (b)竖直差分算子
图3 差分算子

    实验发现这部分对于精度要求虽然要比上面求解目标图象时要高一些，如果去掉小数部分也基本上没有太大的影响。注意，差分图象的求解是在输入图象中求得的，而不是对目标图象施算子。也可以在目标图象上求差分图象，但是需要做个适当的变换。

    3） 函数的求解。

    可以采用查找表的方式来完成。如果目标图象和模板图象均采用了整数形式，那么可以得到两个图象的象素差的存在范围： 。又因为 函数具有关于原点对称的性质，所以只需要建立 的查找表就可以了。

    4） 求解。 ，表示仿射参数对 各分量的偏导数，反映了 各分量对整体的影响。当 分别取0到5不同的值时，可以求得 的结果向量。因此可以通过不同的 值而直接表现为一些确定的向量。如下所示：
 
    5） 项： 在算法实现时，可以考虑只使用一个固定的 经验值，在以前的试验中，采用了112.8，也就是65 ，效果较好。

    6）向量 为已知模板图象。

5 迭代算法实验分析：

    首先给出输入图象，如图4(a)所示，再将输入图象中的矩形框标志的区域截取出来，作为模板图象，如图4(b)所示。
           
(a)输入图象                                  (b)选取模板图象
图4 输入图象及模板图象

    以图5中的虚线框为初始估计值，按照上面给出的迭代算法求解，收敛之后得到仿射变化参数，再将其以矩形框的形式显示出来，得到下面结果：
          
(a)匹配结果图象                        (b)定位区域的目标图象
图5 匹配结果图象和定位结果目标图象

    从匹配的结果来看，最终的匹配框相比初始估计发生了旋转、位移和比例放大变化，与图4(a)中的模板图象截取框完全吻合。将框中的图象截取出来，得到的目标图象（如图5(b)所示）与模板图象完全一致，效果理想。从运算时间上来看，在迭代收敛区间内，对于30 30大小的模板，算法从开始状态到收敛仅需要8毫秒的时间（PⅢ730处理器，256M内存，VC6.0编译），验证了该算法的可实时性能。

6 总结

    在本文中，首先对传统的误差评价方式进行了改进，减小了少数大误差点对误差评价造成的过大影响，更全面的考虑整个误差的总体分布情况。随后论述了仿射变换的定义和性质，然后给出了基于区域仿射模型的快速定位方法，迭代求解算法。对迭代求解方法，本文详细讨论了它的实现原理，细节，并对算法进行了详细的分析，同时给出了算法流程图，以及试验部分。总体来说，具有较强的实际意义。

参考文献：

[1] Q. Zheng, R.R. Chellappa. Automatic feature point extraction and tracking in image sequences for
arbitrary camera motion. Computer Visionm, 1995, Vol.15: pages 31-76

[2] G. Jacob, A. Noble, and A. Blake. Robust contour tracking in echographic sequences. In Proceedings of
6th International Conference on Computer Vision, Bombay (India), January 1998: pages 408-413

[3] Min C. Shin, Dmitry Goldgof, and Kevin W. Bowyer. Comparison of edge detectors using an object recognition task. Proceedings of the IEEE CVPR Conference, 1999: pages 360-365

[4] John C. McEachen and James S. Duncan. Shape-based tracking of naturally occurring annuli in image sequences. In Computer Vision and Pattern Recognition, IEEE Computer Society, New York City, June 1993:
pages 613-614

[5] R.J. Feriez and D.C. Lang. Gear-tooth fault detection and tracking using the wavelet transform. Proc. Prognosis of Residual Life of Machinery and Structures, MFPT, 1998

[6] 毛澎芬, 沈世明. 射影几何.上海：上海科学技术文献出版社, 1985

[7] Song-Ha Choi and Seong_whan Lee. Region tracking using perspective motion model. Pattern Recognition 33(2000) 2095-2098.

[8] Michael J.Black and Allan D.Jepson, Eigentracking: robust matching and tracking of articulated objects using a view-based representation, [A], International Journal of Computer Vision, 1998: 26(1) pages 63-84.

[9] Klbl O, Bach U, Gasior D and de Laporte K. Multi-template-matching for the automation of photogrammetric measurements. Archives of the 17 th Congress ISPPS, Washington 1992; 29(B3): 540-548