利用多线程及改进SSDA算法加快拼接速度

谢永胜，余正生

（杭州电子科技大学图形图像研究所，浙江杭州310018）

0 引 言

图像配准和图像融合是图像拼接［1］的两个关键技术，图像配准是图像融合的基础，而且图像配准算法的计算量一般非常大，因此图像拼接技术的发展很大程度上取决于图像配准技术的创新。图像配准在数字图像领域已经有很多研究成果。这一问题涉及到点对点的匹配，特征的提取等等方面。概述了图像配准技术的基本理论以及主要方法如文献2，综述了随后10年的图像配准领域的相关方法如文献3。配准在图像处理里应该属于一种比较基础的技术，在某些特定的领域有着非常重要广泛的应用：比如计算机视觉处理［4］，医学图像处理［5］以及卫星遥感领域［6］等等。正因为如此重要，无论其配准速度或配准准确率都在不断地进行着改进。基于灰度的方法比较常用，但纯粹基于灰度的拼接方法适应性差，特别对于待配准图像的缺损方面要求很高。序列相似性检测算法目前已有多种改进，改进后的算法大大提高了运算速度，但由于速度的改进往往会带来准确性的降低，而本文的改进主要在于在淘汰非匹配点时对准确性要求方面效果更佳，主要目的还是针对算法在保证高配准精度条件下的对速度方面进行改进。

1 图像配准

基于图像灰度相关的常用匹配方法为模板匹配，即一种对待匹配的象元以一定大小窗口的灰度阵列按某种或几种相似性度量顺次进行搜索匹配的方法。见的相似性度量有以下几种：

1.1 基于两幅图像灰度的平方差之和

计算模板和搜索子图对应灰度值之差的平方公式和：

该方法称差和法，其中S，T分别代表图像各个象素的灰度值，m，n代表各个象素的坐标，其值最小者所对应的位置（i，j）为最佳匹配位置，记录其值。

1.2 序列相似度检测

其基本思想是：如果窗口内所有点被检验完之前该误差过早地达到预定的门限值，便认为该窗位置不是匹配点，无须继续检验窗内的剩余点，停止本次运算，而转向计算下一窗口位置，直到找到匹配点为止，记录其值，从而省去大量的在非匹配位置处的无用运算量。

1.3 互相关检测

互相关检测的思想是用到了概率和数理统计中相关系数的思想：

相关系数是0-1之间的一个数，其值越接近1说明量图像越相似，所以，值最大者为最佳匹配点，同样记录其值（即等于 1），R（i，j）越大，模板与子图 S（i，j）就越相似，（i，j）也就是要搜索的匹配点，同样记录其值。

2 图像拼接

确定匹配点后，要确定整幅象素的值，如图1所示。假设S点在矩形A中的坐标为（Asx，AT），图像左下角为坐标原点。在矩形B中的坐标为（Bsx，BT），AH、AWidth分别为矩形A的高度和宽度，BH、BWidth分别为矩形B的高度和宽度，则拼接后的图像的高度和宽度为CH、Cwidth。部分流程如图2所示。

图1 拼接实例图

图2 拼接流程图

3 算法改进

基于图像灰度方法虽然精确度较高，但是相应的计算量也很大，实时性不高，并且受灰度图像损伤程度影响较大，为了增加系统的实时性，适应性，减少运行时间，改进的基本思想有：（1）修改算法，提高运行速度；（2）多CPU线程并行编程技术；（3）引入仿射机制。

3.1 修改算法，提高程序运行速度

对序列相似性检测作进一步的改进，这本身是一种快速图像匹配算法，但由于其阀值的单一性，所以可针对其阀值进行算法修改。首先是定义误差，阀值增值为Add，阀值的取值空间设定为Value［Min-Num…MaxNum］，设置访问变量B［（M-N+1）（M-N+1）］为True，算法从W=Value［MinNum］开始循环，在子图中随即选取象素点，计算它同T中对应点的误差Error，然后把这点的差值同其他点对的差值累加起来，当累加P次直到误差超过Value［MinNum］则停止累加，并记下累加次数P。记下各累加次数点，找出W=Value［MinNum］这轮循环中累加次数最大点的值Max。淘汰W=Value［MinNum］这轮循环中累加次数点小于T的点，即将其B［］值设为False。通过对T的不同取值，分别进行50次配准（选取的两幅图像大小分别为256×56，35×44经过选取多幅图像进行测试也有类似的结论），来查看正确的配准次数，如表1所示：

表1 配准正确率比较

3.2 利用多CPU线程并行编程技术

提出了把多线程技术应用于图像配准，并且已经在平台下用VC++6.0加以实现，而硬件条件是采用英特尔酷睿2双核处理器，在一定程度上提高计算机资源的利用率，降低系统运行时间。在模板匹配的过程中，模板在待匹配图像上一个象素一个象素的进行遍历匹配，可以认为各象素间的匹配是没有任何关系的，基于此，提出将待匹配图像分为上下两个部分，创建两个线程，分别将两个部分在不同的线程中进行遍历匹配。主线程必须等待辅助线程都完成后，然后将各个辅助线程得出的误差进行相加，这样可以得这趟循环总的误差，然后用前述算法进行处理。最后综合两个线程的遍历结果，再通过主线程找出最佳匹配点。

3.3 引入仿射机制，用最小二乘法进行拟合

一旦将共同区域确定下来之后，那就需要通过仿射变换公式将映射参数计算出来。2D空间中，变换公式为：

引入最小二乘法，用多个配准点找出最优参数解。假设W为A，B两图中特征点组成的矩阵，X′，Y′分别为B图中特征点的X，Y坐标组成的矩阵。所以有：

那么就是所求的最优仿射参数解。由于式4中有逆矩阵的存在，这样计算结果会出现小数，所以对于结果图像的处理上的象素可能不在整数点上，就需要通过插值法进行弥补，而采用三次卷积法比较理想。

4 实验分析

因为本文中图像的拼接所耗费的时间主要花费在配准上面，用上述提出的改进算法，首先对大量图像进行配准实验，主要是针对已有的几种配准算法进行时间上的比较。拼接前的两幅图像如图3所示，拼接后的两幅图像如图4所示。各种算法拼接速度的比较如表2所示。

图3 拼接前的两幅图像

图4 拼接后的结果图像

表2 各种算法实现时间的比较

5 结束语

文中讨论的拼接算法具有实时响应速度快，特别是引入多CPU的线程同步技术，大大加快了拼接速度。但是由于要考虑到准确性方面，每次淘汰非匹配点的时候还是会有很多点需要在以后的循环当中进行重复的匹配，实验算法速度改进的空间还是很大的。

［1］ 王俊杰，刘家茂.图像拼接技术［J］.计算机科学，2003，30（6）：141-144.

［2］ Brown LG.A survey of image registration techniques［J］.ACM Computing Surveys，1992，24（4）：325-367.

［3］ Zitoa B，Flusser.I Image resist ration methods a Survey［J］.Image and Vision Computing，2003，21（11）：977-1 000.

［4］ Huang X，Paragios N，Metaxas D.Shape registration in implicit spaces using information theory and free form deformations［J］.IEEE Trans Pattern Anal Mach Intell，2006，28（8）：1 303-1 318.

［5］ 陈灵娜，盛利元，陈俊熹.CT图像配准算法的研究与实现［J］.医疗设备信息，2004，19（8）：4-5.

［6］ Bentoutou Y，Table N，kpalma K，et al.An automatic image registration for applications in remote sensing［J］.IEEE Trans Geosci Remote Sens，2005，43（9）：2 127-2 137.