发布时间: 2017-11-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.170156
2017 | Volume 22 | Number 11

图像分析和识别

像对匹配的模板选择与匹配

贾迪, 杨宁华, 孙劲光

辽宁工程技术大学电子与信息工程学院, 葫芦岛 125105

收稿日期: 2017-05-03; 修回日期: 2017-08-05

基金项目: 国家自然科学基金项目（61601213）；第61批中国博士后面上基金项目（2017M611252）；辽宁省教育厅一般项目（LJYL017）

第一作者简介: 贾迪(1982-), 男, 副教授, 2011年于东北大学获计算机应用专业博士学位, 主要研究方向为图像的PDE处理、立体匹配、3维重建。E-mail:lntu_jiadi@163.com.

中图法分类号: TP391

文献标识码: A

文章编号: 1006-8961(2017)11-1512-09

摘要

目的图像模板匹配法常用于寻找像对间区域的对应关系，目前尚存的问题有：1）随着摄影基线的增加，待匹配区域在目标影像中有效信息逐渐降低；2）匹配区域的选择对匹配结果准确性影响较大。为了解决上述问题，提出一种基于分值图的图像模板选择与匹配方法。方法首先利用图像多通道特征，提出采用抽样矢量归一化相关算法SV-NCC（sampling vector-normalized cross correlation）度量两幅图像间区域一致性，增加多通道特征间的有效信息对比，以此降低噪声与光照对模板匹配的影响。其次，在矢量空间中对图像进行分块聚类，将模板区域根据颜色特征分为几类，统计匹配图像的每个区域类中心颜色在待匹配图像中相似数量的倒数作为度量值，其值越大则颜色或颜色组合在目标图像中相似的概率越小，以该位置为基础选取模板进行匹配的准确率越高。最后，给出依据分值图排序模板区域的方法，并选取高分值区域作为最终的模板选择区域。结果实验采用公共数据集从两个方面对本文方法进行客观评价：1）在摄影基线变换不大的情况下，SAD与SV-NCC方法的准确率均较高，达到90%以上。随着摄影基线的增大，采用SAD方法匹配准确率降低速率更快，在第6幅Graf图像的测试中匹配准确率低于20%，而SV-NCC方法匹配准确率高于40%；2）随着摄影基线的增大，落在高分值图区域匹配的正确率高于未落在高分值图区域匹配的正确率，由此可见高分值图区域的合理选择将提高模板匹配方法的准确率，验证了本文分值图与选择最佳模板匹配位置方法的有效性。结论该方法从定量和定性比较上都体现了较好的像对匹配能力，其匹配结果适用于影像融合、超分辨率重建及3维重建等技术中的先期处理步骤。

关键词

归一化互相关; 模板匹配; 分值图; 密度聚类; 摄影基线

Template selection and matching algorithm for image matching

Jia Di, Yang Ninghua, Sun Jinguang

School of Electronic and Information Engineering, Liaoning Technical University, Huludao 125105, China

Supported by: National Natural Science Foundation of China(61601213)

Abstract

Objective Template matching algorithms consider all possible transformations, such as rotation, scaling, and affine transformations.Template matching algorithms are commonly used to find the corresponding image regions between image pairs.However, the two following issues negatively affect its accuracy.1) When the photography baseline increases, the effective information of the area to be matched in the target image decreases and the matching accuracy gradually decreases.2) The choice of matching areas significantly influences the matching accuracy; thus, the matching results may differ considerably by selecting different regions as matching templates.We propose a template selection and matching algorithm for image matching to resolve these problems. Method First, sampling vector normalized cross-correlation (SV-NCC) is proposed to measure the regional consistency between two images by multichannel features.The proposed method discards two parameters, i.e., Δ$s$ and $r$, which play an important role in suppressing the interference of light and noise in the CSAD method but reduce matching accuracy.The NCC method is introduced using the "mean" and "cross-correlation" to inhibit the effect of light and noise to solve this problem.Template matching is conducted in Lab color space to better reduce the influence of the change in illumination.When computing the color similarity of two images, if the Euclidean distance of two color components < a, b > falls in a rectangle with width $w$ and height $h$, then they are considered similar colors.Coefficient proportionality $λ$ is used to adjust the proportion of brightness similarity; thus, distinction between similar colors is obtained by controlling $λL$.Second, we divide the image into many blocks and use the clustering method to derive several categories in accordance with the color feature.The reciprocal of the similar number of each area is used to measure similarity.The larger this value, the smaller the probability that the color or color combination is similar to the target image.Thus, the accuracy of template matching based on this location can be high.Although density-based spatial clustering of applications with noise (DBSCAN) is used in the previously presented process, the image is divided into many blocks.Thus, no matter how large the image size is, the processing time of pixel clustering cannot substantially increase.In addition, the clustering results can exhibit a mosaic appearance but cannot affect the calculation of subsequent statistical scores.Finally, on the basis of the score map, a method for sorting the template area is proposed.These areas with high scores are selected as the final template areas.The parallel DBSCAN algorithm is also used in this research to fully utilize a multi-core CPU and reduce the computation time.For example, with an eight-core CPU, an 800×600 image with 100×100 blocks takes 2.8 s to process.Then, the computational complexity is reduced because of the fact that introducing the integral image to compute blocks can significantly reduce the processing time and can make this algorithm practical in real-life usage. Result The experiments use a 3.3 GHz, 8 GB RAM, four-core CPU and are coded in MATLAB.Data from Oxford Graf, which contain six different views of the same target, and data of Pascal VOC 2010 are selected for the experiment to test the effectiveness of the proposed algorithm.The size of the template is set as 100×100, $Tr$=2, $δ$=0.25, and $ℓ$=0.15.Given that two important parameters that affect the experimental results should be set on the basis of experience in using the CSAD, it is unsuitable to compare with the SV-NCC, which automatically computes the similarity between the blocks.Therefore, we compare the proposed method with the SAD method directly.We evaluate the proposed method in the two following aspects.1) When the baseline of photographic changes is low, the accuracy of the SAD and SV-NCC methods are all more than 90%.However, when the baseline of photographic changes increases, the matching accuracy of SAD is reduced rapidly.In the test of the sixth Graf image, the matching accuracy is less than 20% and the accuracy of SV-NCC matching is more than 40%.2) When the baseline of photographic changes increases, the matching accuracy is higher in the regions with high scores than that in the regions with low scores.Thus, the reasonable selection of regions with high scores can improve the accuracy of template matching, and the proposed method, which selects the best template positions, is verified. Conclusion The SV-NCC method is proposed to compute the similarity between regions by use of the multichannel features of colored images to resolve the previously mentioned issues when matching wide baseline colored images.On the basis of the assumption that, the lesser the color or color combination in the images to be matched, the higher the matching accuracy, a new algorithm based on the score map is proposed to optimize the template selection and improve the matching accuracy.The experiments show that this algorithm presents a significantly high image matching accuracy for wide baseline colored images.The algorithm is also robust, making it practical, particularly in areas where colored images need to be matched with high accuracy.The algorithm can also be combined with random sample consensus to eliminate mismatched regions.Quantitative and qualitative analyses of the proposed method show that it exhibits a good performance and that its matching results are suitable for image fusion, super-resolution reconstruction, and 3D reconstruction in the advanced steps.

Key words

normalized cross correlation; template matching; score map; density clustering; photographic baseline

0 引言

模板匹配算法通常考虑所有可能的变换，包括旋转、尺度及仿射变换。Alexe等人^[1]提供了一种高效的计算方式处理两幅图像匹配窗口中的高维矢量，该方法提取两个窗口重叠部分的边界，并使用它去限制与匹配多窗口。Tsai等人^[2]提出使用波分解与环形投影提高匹配准确率，并重点考虑了旋转变换。Kim等人^[3]给出一种灰度模板匹配方法，该方法具备较好地抗旋转与尺度变换。Yao等人^[4]提出一种搜索颜色纹理的方法，该方法同样考虑了旋转与尺度变换。在宽基线条件下，后3种方法存在匹配质量不高的问题。另一项相关研究为Tian等人^[5]的工作，该方法对密度形变场进行参数估计，是一种从目标变换参数空间中获得最小变换距离的方法。FAST-Match^[6]由Korman等人于2013年提出，该方法通过抽样计算匹配区域像素间最小化SAD(sum of absolute differences)判定匹配结果，并使用全局模板匹配^[7]实现加速搜索，但对彩色图像匹配前需要预先转化为灰度图像。文献[8]以该方法为基础，实现了一种由粗到精的区域选择与匹配。CFAST-Match由Jia等人^[9]提出，通过计算模板区域中不同颜色所占比例提高彩色图像模板匹配的准确性，但该方法需要对部分参数依据经验进行设置，此外该方法使用了密度聚类(DBSCAN^[10])，在处理大尺寸图像时执行时间长，降低了该方法的实用性。

在实际同物方影像的采集过程中，随着摄影基线的增大，待匹配区域在目标影像中有效信息逐渐降低，这种情况下利用图像中的多种信息、选择合适的待匹配位置成为提高匹配准确性的有效手段，为此本文提出一种基于分值图的图像模板选择与匹配方法。主要贡献点为：1) 提出抽样矢量归一化方法(SV-NCC)，提高彩色图像块间匹配的实用性；2) 依据选取的模板中所包含的颜色或颜色组合在待匹配图像中越少，则匹配正确性概率越高这一规律，提出一种分值图的计算方法，利用分值图排序模板区域，并选取高分值区域作为最终的模板选择区域，通过实验验证了本文方法的有效性。

1 SV-NCC度量彩色图像块间相似性

彩色图像灰度化的过程中将损失部分重要信息。如图 1(a)所示，该图由3种颜色构成，其RGB的值分别为(69，0，0)、(0，35，0)、(0，0，182)。图 1(b)是由图 1(a)灰度化后获得的结果。可见，红、绿、蓝区域转化后的灰度相同，其值均为21。因此当使用模板匹配算法时，损失了原有图像中的颜色信息，可能导致匹配错误率升高。

图 1 彩色图像转灰度图像的信息损失

Fig. 1 Information loss of converting RGB to grey

((a)color image; (b)gray image)

令图像I₁与I₂间的区域相似性$ {{\Delta }_{T}}$(I₁，I₂)由SAD计算得到，令I为I₁中的像素$p $到I₂中像素间的仿射变换矩阵，则有

$ {{\Delta }_{T}}\left( {{\mathit{\boldsymbol{I}}}_{1}}, {{\mathit{\boldsymbol{I}}}_{2}} \right)=\frac{1}{n_{1}^{2}}\sum\limits_{p\in {{I}_{1}}}{\left| {{I}_{1}}\left( p \right)-{{I}_{2}}\left( T\left( p \right) \right) \right|} $

(1)

式中，$ n_1 $为随机选取的像素点个数。文献[6]的创新点主要有以下两个方面：1) 尺度、旋转、切变的变换步长通过经验参数δ进行控制，即如何获得式(1) 中的$ T $变换；2) 通过参数$ ℓ $控制抽样点，以此计算$ {{I}_{1}}\left( p \right) $与$ {{I}_{2}}\left( p \right) $的相似性。采用式(1) 处理图 1(a)，需要先将图 1(a)转化为图 1(b)，然而图 1(b)中区别不同区域的信息已经消失。因此为了避免这个问题，文献[9]采用CSAD度量区域间的相似性

$ {{d}_{T}}\left( {{\mathit{\boldsymbol{I}}}_{1}}, {{\mathit{\boldsymbol{I}}}_{2}} \right)=\frac{1}{n_{1}^{2}}\sum\limits_{p\in {{\mathit{\boldsymbol{I}}}_{1}}}{F\left( {{I}_{1}}\left( p \right), {{I}_{2}}\left( T\left( p \right) \right) \right)} $

(2)

$ \begin{array}{l} F\left( {{I_1}\left( p \right), {I_2}\left( {T\left( p \right)} \right)} \right) = \\ \left\{ \begin{array}{l} |(I_1^R(p)-I_2^R(T(p))| + |I_1^G(p)-I_2^G(T(p))| + \\ \;\;\;\;\;\;|I_1^B(p)-I_2^B(T(p))|) * \Delta s\left( p \right)\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;D(C({I_1}(p)), {I_2}(T(p))) \le r\\ 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;D(C({I_1}(p)), {I_2}(T(p))) > r \end{array} \right. \end{array} $

式中，R、G、B为彩色图像中RGB通道的颜色值，D(*)用来计算两个输入参数间的相似性，$ C\left( {{I_1}\left( p \right)} \right) $为I₁中$p $点所属类中心的RGB值，$ \Delta s\left( p \right) $为$p $所在区域的分值系数，$ r $为距离阈值半径。采用式(2) 方法则存在以下问题：1) $ r $与$ \Delta s\left( p \right) $需要根据经验预先设置；2) 采用DBSCAN密度聚类算法对整幅图像进行处理，当图像尺寸较大时处理时间过长。

为了解决上述问题，考虑摒弃Δ$ s $与$ r $这2个参数，然而这种处理方式降低了匹配的准确性，其根本原因在于Δ$ s $与$ r $对光照与噪声干扰起到了抑制作用。为了解决这一问题，引入NCC方法，由于该方法使用了“均值”与“互相关”计算，因此对噪声与光照都有一定的抑制作用，提出抽样矢量归一化相关算法SV-NCC，即

$ \begin{align} & {{\Delta }_{T}}\left( {{\mathit{\boldsymbol{I}}}_{1}}, {{\mathit{\boldsymbol{I}}}_{2}} \right)= \\ & \frac{\sum\limits_{p\in {{I}_{1}}}{\sum\limits_{m\in K}{\left[\begin{matrix} |I_{1}^{V\left( m \right)}\left( p \right)-E\left( I_{1}^{V\left( m \right)}\left( p \right) \right)|\cdot \\ \left| I_{2}^{V\left( m \right)}\left( T\left( p \right) \right)-E\left( I_{2}^{V\left( m \right)}\left( T\left( p \right) \right) \right) \right| \\ \end{matrix} \right]}}}{\sqrt{\begin{align} & \sum\limits_{p\in {{I}_{1}}}{\sum\limits_{m\in K}{{{\left[I_{1}^{V\left( m \right)}\left( p \right)-E\left( I_{1}^{V\left( m \right)}\left( p \right) \right) \right]}^{2}}\cdot }} \\ & \sum\limits_{p\in {{I}_{1}}}{\sum\limits_{m\in K}{{{\left[I_{2}^{V\left( m \right)}\left( T\left( p \right) \right)-E\left( I_{2}^{V\left( m \right)}\left( T\left( p \right) \right) \right) \right]}^{2}}}} \\ \end{align}}} \\ \end{align} $

(3)

式中，M与N为模板的长和宽，$ T $(*)为仿射变换函数，$ T(p) $用于求取$p $点仿射变换后的坐标，$ E $(*)用于求取*位置上子图均值，$ V(m) $为$m $通道的矢量值，K为通道数。为了更好地完成匹配，将彩色图像由RGB空间转为Lab空间，其好处在于可以更好地控制亮度的相似性，即在对L通道按式(3) 进行计算时，可以加入比例系数$ λ $，调节亮度相似性所占比例。如图 2中的立方体区域中均偏红色，通过控制$ λ $的高度获得相似颜色的区分。例如，当计算两幅彩色图象的相似性时，通过计算$ < a, b > $的SV-NCC是否落在长为$ w $、宽为$ h $的立方体内，以此判断模板与匹配区域的相似度。因此仿射变换相似性估计$ {{\Delta }_{T}}$(I₁，I₂)可以通过以下抽样方法获得：

图 2 Lab颜色空间图示

Fig. 2 Color space diagram of Lab

1) 令输入彩色图像为I₁与I₂，精度参数$ ℓ $^[6]及仿射变换矩阵T；

2) 根据$ m = \Theta \left( {1{/ℓ^2}} \right) $^[6]采样$ {p_1}, \cdots, {p_{\rm{m}}} \in {I_1} $的$ < a, b > $通道值，其中Θ用于求取弧长，利用式(3) 计算SV-NCC作为$ {{\Delta }_{T}}$(I₁，I₂)的估计值。

2 分值图与选择最佳模板匹配位置

采用模板匹配算法匹配两幅图像时，匹配模板位置的选择对匹配准确率影响很大。图 3(a)由4种色块构成，图 3(b)为图 3(a)经过仿射变换得到。图 3(a)中的A—D区域为模板选择区域，在与图 3(b)进行匹配时，由于模板A—C均存在多相似性区域，导致很难获得准确的匹配结果，而模板D中存在的颜色组合唯一，在图 3(b)中仅位于图像中心处，因此容易准确匹配。由此可见，选择颜色或颜色组合在目标图像中出现尽可能少的区域作为模板容易提高匹配的准确率。

图 3 模板匹配存在的问题

Fig. 3 Template matching problem

((a)template; (b)affine transformation)

尽管如此，由于图 3(a)中每个区域在图 3(b)中进行比较是一件非常耗时的事，因此采用如下方法解决该问题：在矢量空间中对图像进行聚类，将模板区域根据颜色分为几类，统计匹配图像的每个区域类中心颜色在待匹配图像中相似数量的倒数作为度量值，为每个区域打分，分数越高则颜色或颜色组合在目标图像中相似的概率越小, 即

$ {S_{{\rm{Map}}}}\left( {i, j} \right) = \frac{1}{{{C_{{\rm{Sim}}}}\left( {{I_1}\left( {i, j} \right), {\mathit{\boldsymbol{I}}_2}} \right) + o}} $

(4)

式中，I₁与I₂分别为待匹配与匹配图像，$ \left( {i, j} \right) $为当前像素点坐标，$ {{C_{{\rm{Sim}}}}\left( {{I_1}\left( {i, j} \right), {\mathit{\boldsymbol{I}}_2}} \right)} $用于计算I₁中$ \left( {i, j} \right) $位置像素在I₂中的相似数量，$ o $用于确保分母不为0，S_Map即为分值表。在聚类后的图像上滑动匹配窗口，计算不同类别的数量，以此作为选择区域的颜色组合数，结合分值图ScoreMap计算每个位置的选择优先度，具体过程如下：

1) 将图像I₁与I₂根据块大小的设定进行分块，分别获得N₁、N₂个分块，构成集合B₁、B₂；

2) 分别对于每个分块的 < R G B > 3维数据进行密度聚类(DBSCAN)处理，获得集合DB₁、DB₂；

3) 分别求取DB₁、DB₂中每个分块内部同类标号(标号为DBSCAN密度聚类算法的输出结果，标号相同的位置代表同一类)的相同通道均值，记为$ \bar R、\bar G、\bar B $，建立结构$ \mathit{\boldsymbol{s = }}\left[{\bar R\;\bar G\;\bar B\;BN\; < {x_1}, {y_1} > \; \cdots \; < {x_n}, {y_n} > } \right] $，获得结构集S₁与S₂；(BN为分块号，$ { < {x_1}, {y_1} > \; \cdots \; < {x_n}, {y_n} > } $为当前同类标号的坐标)；

4) 将S₁与S₂中前3项$ \bar R、\bar G、\bar B $转为L、$ a $、$ b $，即令每个结构单元为$ \mathit{\boldsymbol{s = }}\left[{L\;a\;b\;BN\; < {x_1}, {y_1} > \; \cdots \; < {x_n}, {y_n} > } \right] $；

5) 计算S₁到S₂的每个s单元间$ < L\;a\;b > $的欧代距离，累计小于阈值$ Tr $的数量N，并将$ \frac{1}{N} $替换S₁中结构单元首字节，即$ \mathit{\boldsymbol{s = }}\left[{\frac{1}{N}\;a\;b\;BN\; < {x_1}, {y_1} > \cdots < {x_n}, {y_n} > } \right] $；

6) 构造行列分别为$ m $及$ n $的零矩阵SM，遍历S₁中所有的s，对于每个s，将[$ \frac{1}{N} $]根据$ \left[{BN\; < x1, y1 > \cdots < xn, yn > } \right] $填入矩阵SM (BN为分块编号，$ { < {x_{1, }}{y_1} > .. < {x_n}, {y_n} > } $为当前同类标号的坐标)；

7) 输出分值图SM(ScoreMap)。

需要说明的是，上述过程中虽然用到了DBSCAN算法，但由于对图像进行了分块处理，因此无论图像尺寸有多大，均不会极大增加像素聚类的处理时间。另外，分块聚类尽管会出现“马赛克”的现象，但不会影响后续分值的计算。利用上述分值图，通过积分图的方式排序每个模板区域，将前$n $个分值最高区域作为最后的选择结果，计算过程如下：

1) 计算分值图SM的积分图^[9]，记为SMSAT；

2) 设定待匹配模板大小为W×H；

3) 遍历SMSAT中的每个点$ \left( {i, j} \right) $，通过以下公式计算以$ \left( {i, j} \right) $为左上角，$ \left( {i + W, j + H} \right) $为右下角的矩形区域分值累计值

$ \begin{array}{c} BS = SAT\left( {i + W, j + H} \right) + SAT\left( {i, j} \right)-\\ SAT\left( {i + W, j} \right)-SAT\left( {i, j + H} \right) \end{array} $

构造$ m \times n $个单元$ < BS\;i\;j > $，获得集合S；

4) 依据BS的值由大到小排序集合中的单元$ < BS\;i\;j > $，获得排序好的集合S；

5) 从S[0]开始，通过S中的$ < i\;j > $抽取不相邻$n $个区域，获得集合R；

6) 返回R作为最后的模板选择结果。

3 实验分析

选用4核主频为3.3 GHz的CPU，内存8 GB的计算机作为实验环境，Matlab编码。采用牛津大学数据Graf^[11]，其中包含6张不同视角拍摄的同目标影像，以及建筑影像数据Pascal VOC 2010^[12]，模板大小设置为100×100、$Tr=2$、$δ=0.25$、$ℓ=0.15$。本文采用SV-NCC的方法省去文献[9]中CSAD的Δ$ s $与$ r $这2个参数设置，提高了匹配算法的实用性，其匹配结果与CSAD中依据经验选择这两个参数得到的匹配结果不具有可比性，因为依据经验调整Δ$ s $与$ r $这两个参数可以获得全局最优值，因此未做比较分析。

图 4为描述分值图生成过程的示例图。图 4(a)为两幅包含相同场景的宽基线影像。采用分块密度聚类方法，获得如图 4(b)所示的结果。以该结果作为输入，采用本文第2节给出的分值图计算方法，得到如图 4(c)所示的结果。由图 4(c)可见，分值最高(灰度值)的区域为对应原图中的黄色区域，而该区域在目标图像中存在的部分最少；灰色区域的分值最低，而该类区域在目标图像中存在的部分最多，因此可以直观地反映分值图计算方法的正确性。利用第2节方法(分值图)确定分块位置，并分别采用文献[6]和本文方法进行实验获得如图 5的实验结果。图 5(a)为采用本文第2节给出方法标记模板位置的图像，图 5(b)为采用本文第1节给出方法获得的匹配结果，图 5(c)为采用文献[6]获得的匹配结果。图 5(d)与(e)分别为图 5(b)与(c)中每个匹配位置的区域放大图。由图 5(d)可见，Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ、Ⅸ、Ⅹ、Ⅺ、Ⅻ为正确的匹配区域，因此其匹配准确率为9/12=75 %，而图 5(e)中，仅有Ⅱ、Ⅲ、Ⅴ为正确匹配区域，因此其准确率为25 %，验证了本文第2节给出方法的有效性。

图 4 分值图的获取过程

Fig. 4 Acquisition process of score map((a)images to bematched; (b)desity clustering results; (c)score map)

图 5 本文方法与文献[6]的匹配结果对比

Fig. 5 Contrast between the results of this paper and the reference[6] ((a) image to be matched and location of the templates; (b) ours; (c) matching result of reference[6]; (d) local enlarged corresponding regions of (a) and (b); (e) local enlarged corresponding regions of (a) and (c))

图 6(a)为采用随机方法确定的模板位置(模板间不重叠，尽可能使模板分布均匀)，图 6(b)为采用本文第1节方法获得的匹配结果，相应的局部放大区域如图 6(c)所示。由图 6(c)可见，正确的匹配区域为Ⅱ、Ⅵ、Ⅸ、Ⅻ，因此其匹配准确率为33 %，低于75 %。对比图 5(d)与图 6(c)明显可见，依据分值表选择的模板匹配准确性更高，验证了本文第1节给出方法的有效性。图 7选择的实验影像为另一组宽基线影像，图 7(a)标记的模板区域由图 7(b)的分值图获得，图 7(c)与图 7(d)分别为采用本文方法和文献[6]的方法获得的匹配结果，尽管两幅图像中存在着多相似性区域，但从实验结果上同样验证了本文方法优于文献[6]给出的方法。图 8为一组采用牛津大学数据Graf^[11]获得的法性能评估图，由图 8(a)可见随着图像编号的增加，摄影基线在逐渐增大。图 8(b)为采用第1节给出的方法与文献[6]方法的对比结果。由图可见，在摄影基线变换不大的情况下，两种方法的准确率较高，均达到90 %以上。随着摄影基线的增加，文献[6]所采用的SAD方法匹配准确率降低速率更快，如在编号为6的图像中，本文所采用的SV-NCC方法匹配准确率高于40 %，文献[6]的方法匹配准确率低于20 %。图 8(c)为采用本文第1节给出的方法匹配所有位置的实验结果，粉色曲线为落在高分值图区域(分值高于平均值)且匹配正确的比率，蓝色曲线为未落在高分值图区域且匹配正确的比率。由图可见，高分值图区域的合理选择将提高模板匹配方法的准确率，同样验证了本文第2节给出方法的有效性。为了缩短算法的处理时间，采用多核CPU通过并行DBSCAN算法处理对每个分块进行密度聚类。例如，采用一颗8核的CPU处理的800×600像素的图像，当分块大小为100×100时，平均耗时2.8 s。其次，排序分值图利用了积分图SAT，同样降低了计算复杂度，提高了本文方法的执行效率。

图 6 随机选择模板匹配结果

Fig. 6 Matching results of randomly selected templates((a) image to be matched and randomly selected templates; (b) ours; (c) local enlarged corresponding regions of (a) and (b))

图 7 建筑影像匹配结果对比

Fig. 7 Contrast of the architectural image matching results((a) image to be matched and location of the templates; (b) score map; (c) ours; (d) matching result of reference[6])

图 8 算法性能评估

Fig. 8 Algorithm performance evaluation((a) Graf images sequence; (b) contrast of this paper and reference[6]; (c) location validity of templates selection)

4 结论

为了提高模板图像匹配的准确率，引入彩色图像的多通道特征，提出抽样矢量归一化互相关方法SV-NCC计算区域间的相似性。通过选择两幅图像中越少的颜色或颜色组合区域，在进行区域随机抽样匹配时准确率越高这一规律，给出一种基于分值图的模板选择方法，提高了模板匹配的准确率。实验结果表明，本文方法对彩色图像匹配有着较高的适用性，在需要更高匹配准确率的应用环境下，可结合RANSAC剔除误匹配区域，从而为后续图像融合、3维重建等高级图像处理提供更好的支持。与基于点特征匹配方法相比，模板类匹配方法由于需要比较所有的变换区域，因此执行速度较慢。下一步将以本文方法中的分值图为基础，研究模板匹配空间搜索方法，提高模板匹配的运行速度。

参考文献

[1] Alexe B, Petrescu V, Ferrari V.Exploiting spatial overlap to efficiently compute appearance distances between image windows[C]//Advances in Neural Information Processing Systems 24:25th Annual Conference on Neural Information Processing Systems.Spain, Curran Associates Inc, 2011, 24:2735-2743.

[2] Tsai D M, Chen C H. Rotation-invariant pattern matching using wavelet decomposition[J]. Pattern Recognition Letters, 2002, 23(1-3): 191–201. [DOI:10.1016/S0167-8655(01)00099-X]

[3] Kim H Y, de Araújo S A.Grayscale template-matching invariant to rotation, scale, translation, brightness and contrast[C]//Advances in Image and Video Technology.Santiago de Chile, Chile:Springer, 2007:100-113.[DOI:10.1007/978-3-540-77129-6_13]

[4] Yao C H, Chen S Y. Retrieval of translated, rotated and scaled color textures[J]. Pattern Recognition, 2003, 36(4): 913–929. [DOI:10.1016/S0031-3203(02)00124-3]

[5] Tian Y, Narasimhan S G. Globally optimal estimation of nonrigid image distortion[J]. International Journal of Computer Vision, 2012, 98(3): 279–302. [DOI:10.1007/s11263-011-0509-0]

[6] Korman S, Reichman D, Tsur G, et al.FAsT-match:fast affine template matching[C]//Proceedings of 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland, OR:IEEE, 2013:2331-2338.[DOI:10.1109/CVPR.2013.302]

[7] Penate-Sanchez A, Porzi L, Moreno-Noguer F.Matchability prediction for full-search template matching algorithms[C]//Proceedings of 2015 International Conference on 3D Vision.Lyon, France:IEEE, 2015:353-361.[DOI:10.1109/3DV.2015.47]

[8] Yang Y C, Lu Z J, Sundaramoorthi G.Coarse-to-fine region selection and matching[C]//Proceedings of 2015 IEEE Conference on Computer Vision and Pattern Recognition.Boston, MA:IEEE, 2015:5051-5059.[DOI:10.1109/CVPR.2015.7299140]

[9] Jia D, Cao J, Song W D, et al. Colour FAST (CFAST) match:fast affine template matching for colour images[J]. Electronics Letters, 2016, 52(14): 1220–1221. [DOI:10.1049/el.2016.133]

[10] Han J W, Kamber M. Data Mining:Concepts and Techniques[M]. San Francisco: Morgan Kaufmann Publishers, 2001.

[11] Mikolajczyk K, Schmid C. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615–1630. [DOI:10.1109/TPAMI.2005.188]

[12] Everingham M, Van Gool L, Williams C K I, et al. The Pascal visual object classes (VOC) challenge[J]. International Journal of Computer Vision, 2010, 88(2): 303–338. [DOI:10.1007/s11263-009-0275-4]