第15卷第1期 智能系统学报 Vol.15 No.1 2020年1月 CAAI Transactions on Intelligent Systems Jan.2020 D0:10.11992tis.201903037 快速的圆投影图像匹配算法 曹田，李勃，任福继3，董蓉4 (1.南京大学电子科学与工程学院，江苏南京210046；2.合肥工业大学计算机与信息学院，安徽合肥230009： 3.德岛大学智能信息工学部，日本德岛7708500,4.南通大学电子与信息学院，江苏南通226019) 摘要：针对现有圆投影匹配方法计算复杂度高、对同质区域无法识别的缺点，提出了一种新的图像匹配算 法。该算法基于混合圆投影向量，结合塔式分解和角度直方图估计，不仅可以识别出模板在待匹配图像中的准 确位置，还可以通过角度估计策略得到模板的旋转角度。通过图像金字塔策略，结合混合圆投影向量快速找到 候选点：然后在诸多候选点中精确定位，确定位置；最后通过角度直方图计算出准确的角度。实验结果证明该 算法识别率高，且匹配速度快。 关键词：圆投影：模板匹配：图像匹配；图像金字塔：角度直方图：混合圆投影；顶层局部聚类；非极大值抑制 中图分类号：TP391文献标志码：A文章编号：1673-4785(2020)01-0084-08 中文引用格式：曹田，李勃，任福继，等.快速的圆投影图像匹配算法.智能系统学报，2020,15(1)：84-91. 英文引用格式：CAO Tian,LIBo,REN Fuji,etal.Fast image matching algorithm based on circular projectionJ.CAAI transac-. tions on intelligent systems,2020,15(1):84-91. Fast image matching algorithm based on circular projection CAO Tian',LI Bo',REN Fuji2,DONG Rong' (1.School of Electronic Science and Engineering,Nanjing University,Nanjing 210046,China;2.School of Computer and Informa- tion Science,Hefei University of Technology,Hefei 230009,China:3.Department of Information Science and Intelligent Systems, Tokushima University,Tokushima 7708500,Japan;4.School of Electronics and Information,Nantong University,Nantong 226019, China) Abstract:In view of the high computational complexity and the incapability to recognize homogeneous regions of exist- ing circular projection matching algorithms,a new image matching algorithm is proposed in this study.On the basis of hybrid circular projection and combined with pyramid decomposition and angle histogram estimation,the proposed al- gorithm can not only identify the exact position of the template in the image to be matched but also obtain the rotation angle of the template through the angle estimation strategy.First,candidate points are identified by the image pyramid strategy combined with the hybrid circular projection vector.Then,the positions of the candidate points are precisely located and determined.Finally,the exact angle is calculated by the angle histogram algorithm.The experimental res- ults show the high recognition rate and fast matching speed of the proposed algorithm. Keywords:circular projection;template matching;image matching;image pyramid;angle histogram;hybrid circular projection;topmost local clustering,nonmaximal suppression 模板匹配是基于已知的模板在待匹配图中找 重要内容，已广泛应用于工业对位山、目标检测识 到最佳匹配位置的过程，是数字图像处理中一个 别)、跟踪等。近年来模板匹配研究已经有一 些有效的算法。但现有的模板匹配过程大多将 收稿日期：2019-03-26. 基金项目：国家自然科学基金深圳联合基金重点项目(U1613217). 模板与场景图像进行卷积，计算模板与场景图像 通信作者：曹田.E-mail:mgl623063@smail..nju.edu.cn 之间的相似度以确定位置。由于相关性的计算
DOI: 10.11992/tis.201903037 快速的圆投影图像匹配算法 曹田1 ，李勃1 ，任福继2,3，董蓉4 （1. 南京大学 电子科学与工程学院，江苏 南京 210046; 2. 合肥工业大学 计算机与信息学院，安徽 合肥 230009; 3. 德岛大学 智能信息工学部，日本 德岛 7708500; 4. 南通大学 电子与信息学院，江苏 南通 226019） 摘 要：针对现有圆投影匹配方法计算复杂度高、对同质区域无法识别的缺点，提出了一种新的图像匹配算 法。该算法基于混合圆投影向量，结合塔式分解和角度直方图估计，不仅可以识别出模板在待匹配图像中的准 确位置，还可以通过角度估计策略得到模板的旋转角度。通过图像金字塔策略，结合混合圆投影向量快速找到 候选点；然后在诸多候选点中精确定位，确定位置；最后通过角度直方图计算出准确的角度。实验结果证明该 算法识别率高，且匹配速度快。 关键词：圆投影；模板匹配；图像匹配；图像金字塔；角度直方图；混合圆投影；顶层局部聚类；非极大值抑制 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2020)01−0084−08 中文引用格式：曹田, 李勃, 任福继, 等. 快速的圆投影图像匹配算法 [J]. 智能系统学报, 2020, 15(1): 84–91. 英文引用格式：CAO Tian, LI Bo, REN Fuji, et al. Fast image matching algorithm based on circular projection[J]. CAAI transactions on intelligent systems, 2020, 15(1): 84–91. Fast image matching algorithm based on circular projection CAO Tian1 ，LI Bo1 ，REN Fuji2,3 ，DONG Rong4 (1. School of Electronic Science and Engineering, Nanjing University, Nanjing 210046, China; 2. School of Computer and Information Science, Hefei University of Technology, Hefei 230009, China; 3. Department of Information Science and Intelligent Systems, Tokushima University, Tokushima 7708500, Japan; 4. School of Electronics and Information, Nantong University, Nantong 226019, China) Abstract: In view of the high computational complexity and the incapability to recognize homogeneous regions of existing circular projection matching algorithms, a new image matching algorithm is proposed in this study. On the basis of hybrid circular projection and combined with pyramid decomposition and angle histogram estimation, the proposed algorithm can not only identify the exact position of the template in the image to be matched but also obtain the rotation angle of the template through the angle estimation strategy. First, candidate points are identified by the image pyramid strategy combined with the hybrid circular projection vector. Then, the positions of the candidate points are precisely located and determined. Finally, the exact angle is calculated by the angle histogram algorithm. The experimental results show the high recognition rate and fast matching speed of the proposed algorithm. Keywords: circular projection; template matching; image matching; image pyramid; angle histogram; hybrid circular projection; topmost local clustering; nonmaximal suppression 模板匹配是基于已知的模板在待匹配图中找 到最佳匹配位置的过程，是数字图像处理中一个 重要内容，已广泛应用于工业对位[1] 、目标检测识 别 [2-3] 、跟踪[4] 等。近年来模板匹配研究已经有一 些有效的算法[5]。但现有的模板匹配过程大多将 模板与场景图像进行卷积，计算模板与场景图像 之间的相似度以确定位置[6]。由于相关性的计算 收稿日期：2019−03−26. 基金项目：国家自然科学基金深圳联合基金重点项目 (U1613217). 通信作者：曹田. E-mail：mg1623063@smail.nju.edu.cn. 第 15 卷第 1 期 智 能 系 统 学 报 Vol.15 No.1 2020 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2020
第1期 曹田，等：快速的圆投影图像匹配算法 ·85· 量很大，因此需要低成本的相关性算法进行实时 意旋转的物体能精确地定位并估计角度，计算速 处理。文献[⑦)]提出了大量相关类型的算法。这 度也有了明显提升。 些方法大多分为两类：1)对模板和场景图像都使 用图像金字塔，并通过自顶向下搜索来执行匹 1标准圆投影匹配算法 配：2)采用两次搜索算法，在第1次搜索过程中 圆投影匹配以模板中心为圆心，模板图片最 使用亚模板在粗网格中搜索，第2次在先前发现 的候选点附近搜索更好的匹配。但是，当检测 大内切圆的半径R为半径创建圆型模板。如图1 目标发生旋转时，以上算法将不再有效。 所示，采用极坐标系表示图像T,以图像中心“O” 近年来国内外学者相继提出了一些可以任意 为圆心建立极坐标系，定义半径为r上的圆投影 旋转的方法。Loweltol提出了一种尺度不变特征 向量Pr)为 变换(SFT),它利用检测区域的梯度分布，具有缩 PT)=T,),0≤r≤R (1) 放和旋转不变性，但是当图像特征点过少或出现 0=0 重复结构时，基于SFT的匹配容易失败，且运算 式中R为图像最大的内切圆半径。 量大。文献[I1]提出一种将SIFT和旋转不变LBP 结合的图像匹配方法，提高了运算速度，但是当 图像细节纹理过多时，该算法匹配性能将显著降 低。基于圆投影的旋转不变性，Tang等提出了 用圆的各向同性和投影特征进行任何角度匹配， 图1圆投影模板示意图 但原始的圆投影匹配计算量较大。后续不断有学 Fig.1 Circular projection template 者对圆投影算法进行改进。Tsai等)使用环形投 当图像旋转时，图像上的像素会随着图像的 影技术表示多通道图像中的模板，通过计算彩色 旋转而旋转，P()为固定量，因此圆投影算法抗旋 环形投影信息之间的NCC来快速选择候选模板， 转。当半径不同时，所对应图像圆投影向量为 然后通过旋转模板来估计旋转。为了减少计算复 P=(p(0),p(1),…,p(R) (2) 杂度，文献[14]使用了一种快速检测到相似候选 项的消除策略。文献[15]将原始圆投影向量进行 为了方便计算，有时也定义圆投影向量P)为 改进，使得改进后的圆投影匹配算法对光照、噪 P(r)= 1 Tr,0,0≤r≤R (3) 声、对比度变化有更好的鲁棒性。文献[16]提出 了两阶段匹配方法，利用第1阶段环形投影的矢 式中n)为半径为r的圆周上的像素个数。 量和选择候选点，然后对第1阶段存留的候选点 然而，标准圆投影向量对于相近灰度值（同 质)的区域是无法识别的。如图2所示，图2(a)为 使用旋转不变属性进行Zernike矩模板匹配。文 半径为r的圆，圆上所有像素点灰度值都为100， 献[17]将圆投影和序贯相似性检测结合起来，通 图2(b)为等半径圆上，一半像素点值为50，另一 过跳跃大量匹配点，减少非匹配点的计算量。文 半为150，计算圆投影向量如图2(e)所示，可以看 献[l8]提出了一种扩展的圆投影算法(extended 到原始圆投影向量对于图2(a)、(b)这种同质区域 RPT,E-RPT),通过添加辅助点约束的方法来有效 是无法区别的。 提高匹配精度。但是上述算法忽略了圆投影向量 2改进的圆投影算法 本身对于同质区域无法识别的问题，同时具有计 算复杂度较高、识别率较低等缺点。 2.1圆投影向量的改进 针对上述应用中的问题，本文设计了一种新 圆投影变换得到图像特征，是为了降低计算 的改进的圆投影匹配算法，主要贡献为：)提出 复杂度，而且这些特征必须是稳定而且独特的。 了混合圆投影向量，提供稳定和独特的特征； 而原始圆投影向量对于图2(a)、(b)这种相近灰度 2)使用图像金字塔，结合顶层局部聚类和逐层金 值（同质）的区域无法区分，因此必须找到这些图 字塔筛选，提升运算速度；3)构建角度直方图，估 片的独特之处来加以区分。为解决这个问题，引 计精确的旋转角度。实验结果表明，本算法对任 入了对应半径r上的方差投影σ()，定义为：
量很大，因此需要低成本的相关性算法进行实时 处理。文献 [7] 提出了大量相关类型的算法。这 些方法大多分为两类：1) 对模板和场景图像都使 用图像金字塔，并通过自顶向下搜索来执行匹 配 [8] ；2) 采用两次搜索算法，在第 1 次搜索过程中 使用亚模板在粗网格中搜索，第 2 次在先前发现 的候选点附近搜索更好的匹配[9]。但是，当检测 目标发生旋转时，以上算法将不再有效。 近年来国内外学者相继提出了一些可以任意 旋转的方法。Lowe[10] 提出了一种尺度不变特征 变换 (SIFT)，它利用检测区域的梯度分布，具有缩 放和旋转不变性，但是当图像特征点过少或出现 重复结构时，基于 SIFT 的匹配容易失败，且运算 量大。文献 [11] 提出一种将 SIFT 和旋转不变 LBP 结合的图像匹配方法，提高了运算速度，但是当 图像细节纹理过多时，该算法匹配性能将显著降 低。基于圆投影的旋转不变性，Tang 等 [12] 提出了 用圆的各向同性和投影特征进行任何角度匹配， 但原始的圆投影匹配计算量较大。后续不断有学 者对圆投影算法进行改进。Tsai 等 [13] 使用环形投 影技术表示多通道图像中的模板，通过计算彩色 环形投影信息之间的 NCC 来快速选择候选模板， 然后通过旋转模板来估计旋转。为了减少计算复 杂度，文献 [14] 使用了一种快速检测到相似候选 项的消除策略。文献 [15] 将原始圆投影向量进行 改进，使得改进后的圆投影匹配算法对光照、噪 声、对比度变化有更好的鲁棒性。文献 [16] 提出 了两阶段匹配方法，利用第 1 阶段环形投影的矢 量和选择候选点，然后对第 1 阶段存留的候选点 使用旋转不变属性进行 Zernike 矩模板匹配。文 献 [17] 将圆投影和序贯相似性检测结合起来，通 过跳跃大量匹配点，减少非匹配点的计算量。文 献 [18] 提出了一种扩展的圆投影算法 (extended RPT，E-RPT)，通过添加辅助点约束的方法来有效 提高匹配精度。但是上述算法忽略了圆投影向量 本身对于同质区域无法识别的问题，同时具有计 算复杂度较高、识别率较低等缺点。 针对上述应用中的问题，本文设计了一种新 的改进的圆投影匹配算法，主要贡献为：1) 提出 了混合圆投影向量，提供稳定和独特的特征； 2) 使用图像金字塔，结合顶层局部聚类和逐层金 字塔筛选，提升运算速度；3) 构建角度直方图，估 计精确的旋转角度。实验结果表明，本算法对任 意旋转的物体能精确地定位并估计角度，计算速 度也有了明显提升。 1 标准圆投影匹配算法 圆投影匹配以模板中心为圆心，模板图片最 大内切圆的半径 R 为半径创建圆型模板。如图 1 所示，采用极坐标系表示图像 T，以图像中心“O” 为圆心建立极坐标系，定义半径为 r 上的圆投影 向量 P(r) 为 P(r) = ∑2π θ=0 T(r, θ), 0 ⩽ r ⩽ R (1) 式中 R 为图像最大的内切圆半径。 O θ r R 图 1 圆投影模板示意图 Fig. 1 Circular projection template 当图像旋转时，图像上的像素会随着图像的 旋转而旋转，P(r) 为固定量，因此圆投影算法抗旋 转。当半径 r 不同时，所对应图像圆投影向量为 P = (p(0), p(1),··· , p(R)) (2) 为了方便计算，有时也定义圆投影向量 P(r) 为 P(r) = 1 n(r) ∑2π θ=0 T(r, θ), 0 ⩽ r ⩽ R (3) 式中 n(r) 为半径为 r 的圆周上的像素个数。 然而，标准圆投影向量对于相近灰度值 (同 质) 的区域是无法识别的。如图 2 所示，图 2(a) 为 半径为 r 的圆，圆上所有像素点灰度值都为 100， 图 2(b) 为等半径圆上，一半像素点值为 50，另一 半为 150，计算圆投影向量如图 2(e) 所示，可以看 到原始圆投影向量对于图 2(a)、(b) 这种同质区域 是无法区别的。 2 改进的圆投影算法 2.1 圆投影向量的改进 σ(r) 圆投影变换得到图像特征，是为了降低计算 复杂度，而且这些特征必须是稳定而且独特的。 而原始圆投影向量对于图 2(a)、(b) 这种相近灰度 值 (同质) 的区域无法区分，因此必须找到这些图 片的独特之处来加以区分。为解决这个问题，引 入了对应半径 r 上的方差投影 ，定义为： 第 1 期 曹田，等：快速的圆投影图像匹配算法 ·85·
·86- 智能系统学报 第15卷 到，通过混合圆投影变换，4幅图片有较好的区 分度。 (a)灰圆b)半黑半白圆(c)内白外黑圆(d内黑外白圆 3.2 160 3.0 140 图2(a) 2.8 2.6 图2(a) -*-图2(b) -+图2(b) 120 -*-图2(c) 4 -图2c ◆图2(d) 023 ◆图2(d) 念100 2.0 80 1.8 1.6 1.4 *中* 特o特4特+++++++ 0 20 40 60 80100 0 20 40 60 80 100 r/pixel r/pixel (e)圆投影分布 图4混合投影向量 Fig.4 Hybrid projection vector 图2简单图和对应的圆投影向量 2.2 相似度函数 Fig.2 Simple graph and corresponding circular projec- 使用归一化互相关(normalized cross correla- tion vector tion,NCC)计算匹配的相似度，具体计算如下： 1 r(r)= [Tr,)-C(r)]2 (4) )xU.( (7) 式中：T(,为模板图上对应点的灰度值：C(r)= P(r)1 2 ，-x2- n=0 了T,)为半径为r的圆上灰度平均值： -R 得到的相似度∫在-1~1。待搜索子图和模板 (r)为半径为r的圆周上的像素个数。 完全匹配时，户1。 如图3所示，方差投影向量表明图2(b)和图 2.3图像金字塔加速 2(a)、(c)、(d)有显著区别。图2(a)、(c)、(d)这3类 为了提高匹配效率，这里使用了图像金字塔 图片无法用方差投影区分，但是可以用式(3)中 进行加速。这里分2个步骤：1)将图像降采样到 的圆投影向量区分出来，如图2(e)所示。 给定层，使用缩小后的图像和模板进行粗搜索， 得到若干候选点；2)逐层对候选点过滤，直到选 3000 出最匹配的点。假设取样层数为-1层，设置每 2500 一图2(a) 层的相似性阈值thresh[n={To,T,…,Tni,只有 2000 -+-图2(b) 1500 -*-图2(c) 大于阈值的匹配点才能够被保留下来。 ◆图2(d) 2.3.1顶层局部聚类 1000 在最顶层使用对应层数模板和待匹配子图的 500 圆投影向量匹配。为了提高效率，这里引人了局 0 0 20 40. 60 80100 部聚类算法，基本思想是将候选点按照位置分成 若干个团簇，每个团簇内的点拥有同一个簇编 图3方差投影向量 号，不同簇彼此不相邻。 Fig.3 Variance projection vector 如图5所示的流程图，算法流程表述如下： 为了兼顾稳定性和独特性，结合式(3)和式(4)， 1)构建一个和待匹配图相同大小的掩码图 得到了混合投影，用于模板图和待搜索子图的混 mask(里面存储候选点所在团簇编号)，以及团簇 合投影H(r)、H,(r)分别定义如下： 相关信息的hash_table(里面存储簇内最相似点位 Hn(r）=m X Pp(r)+woXg(r） (5) 置和相应的相似度)。 H,(r）=umXP(r）+wXo(r） (6) 2)计算某点P所在子图与模板的相似度T, 式中：wm、w。分别为均值投影和方差投影的权重 如果T大于相似度阈值T.,则计算该点上方和左 因子。 边点对应的mask值m_up和m_lefi。 如图4所示，为图2(a)(d)对应的混合投影 ①如果m_up和m_left不都为零，说明这是 向量分布图。此处使用wm=0.6,w=0.4.可以看 已经存在的某个簇的一部分，将P点加入到该簇
σ(r) = vt 1 n(r) ∑2π θ=0 [T(r, θ)−C(r)]2 (4) T(r, θ) C(r) = P(r) n(r) = 1 n(r) ∑2π θ=0 T(r, θ) 式中： 为模板图上对应点的灰度值； 为半径为 r 的圆上灰度平均值； n(r) 为半径为 r 的圆周上的像素个数。 如图 3 所示，方差投影向量表明图 2(b) 和图 2(a)、(c)、(d) 有显著区别。图 2(a)、(c)、(d) 这 3 类 图片无法用方差投影区分，但是可以用式 (3) 中 的圆投影向量区分出来，如图 2(e) 所示。 0 0 500 1 000 1 500 2 000 2 500 20 40 r/pixel sigma/r 60 3 000 80 100 图2(a) 图2(b) 图2(c) 图2(d) 图 3 方差投影向量 Fig. 3 Variance projection vector 为了兼顾稳定性和独特性，结合式 (3) 和式 (4)， 得到了混合投影，用于模板图和待搜索子图的混 合投影 Hp (r)、Hs (r) 分别定义如下： Hp(r) = ωm × Pp(r)+ωσ ×σp(r) (5) Hs(r) = ωm × Ps(r)+ωσ ×σs(r) (6) 式中：ωm 、ωσ 分别为均值投影和方差投影的权重 因子。 ωm = 0.6,ωσ = 0.4 如图 4 所示，为图 2(a)~(d) 对应的混合投影 向量分布图。此处使用 . 可以看 到，通过混合圆投影变换，4 幅图片有较好的区 分度。 0 1.6 2.0 2.4 2.8 3.0 20 40 r/pixel log H(r) 60 1.8 1.4 2.2 2.6 3.2 80 100 图2(a) 图2(b) 图2(c) 图2(d) 图 4 混合投影向量 Fig. 4 Hybrid projection vector 2.2 相似度函数 使用归一化互相关 (normalized cross correlation, NCC) 计算匹配的相似度，具体计算如下： f = ∑Rmax r=Rmin [Hp(r)− Hp]×[Hs(r)− Hs] ∑Rmax r=Rmin [Hp(r)− Hp] 2 × ∑Rmax r=Rmin [Hs(r)− Hs] 2 (7) 得到的相似度 f 在−1~1。待搜索子图和模板 完全匹配时，f=1。 2.3 图像金字塔加速 为了提高匹配效率，这里使用了图像金字塔 进行加速。这里分 2 个步骤：1) 将图像降采样到 给定层，使用缩小后的图像和模板进行粗搜索， 得到若干候选点；2) 逐层对候选点过滤，直到选 出最匹配的点。假设取样层数为 n−1 层，设置每 一层的相似性阈值 thresh[n]={T0 ,T1 ,···,Tn-1}，只有 大于阈值的匹配点才能够被保留下来。 2.3.1 顶层局部聚类 在最顶层使用对应层数模板和待匹配子图的 圆投影向量匹配。为了提高效率，这里引入了局 部聚类算法，基本思想是将候选点按照位置分成 若干个团簇，每个团簇内的点拥有同一个簇编 号，不同簇彼此不相邻。 如图 5 所示的流程图，算法流程表述如下： 1) 构建一个和待匹配图相同大小的掩码图 mask(里面存储候选点所在团簇编号)，以及团簇 相关信息的 hash_table(里面存储簇内最相似点位 置和相应的相似度)。 2) 计算某点 P 所在子图与模板的相似度 T， 如果 T 大于相似度阈值 Tn-1，则计算该点上方和左 边点对应的 mask 值 m_up 和 m_left。 ① 如果 m_up 和 m_left 不都为零，说明这是 已经存在的某个簇的一部分，将 P 点加入到该簇 (a) 灰圆 (b) 半黑半白圆 (c) 内白外黑圆 (e) 圆投影分布 (d) 内黑外白圆 0 60 80 100 P/r 120 140 160 20 40 r/pixel 60 80 100 图2(a) 图2(b) 图2(c) 图2(d) 图 2 简单图和对应的圆投影向量 Fig. 2 Simple graph and corresponding circular projection vector ·86· 智 能 系 统 学 报 第 15 卷
第1期 曹田，等：快速的圆投影图像匹配算法 ·87· 中，即将该点对应mask值设置为m_up和m_left ble中，将对应mask点的值设置为hash table,以 的较大值，如果P点对应相似度大于簇中最相似 此建立新的簇种子点。 点的相似度，则更新簇中最相似点的位置和相似 3)计算下一个点，重复步骤2)，直到所有的 度，否则不更新hash table; 点遍历完，计算结束。 ②反之，如果m_up和m_left都为零，说明 4)最终将hash table中的点位置保存下来。 P是新的点，将P对应位置和相似度放入hash ta- 初始化：mask为全 0,hash table为空 计算当前点P所在子 图与模板的相似度T N T>thresh Y 计算当前点上方和左边点对 将P点对应mask值设 应mask值：m_up、m_le 为max(m_up,m_left) N m up-0 m left=0 N T>hash table[m_p] Y Y table插入[P,T刀. 使用当前P和T更新 不更新 mask[P]=table.size hash table值 hash table 计算下一个点 所有点计算完毕一 Y 结束计算】 图5顶部层次聚类流程图 Fig.5 Top hierarchical clustering flowchart 以LENA图像为例，使用局部聚类之后的 suppression,NMS),选取本层最终候选点。 mask图像如图6所示。 NMS的基本思想是保留局部最大值、抑制非 极大值，计算流程如下：对于候选点列表B及其 对应的相似度S,结果候选点集合为D,采用下面 的计算方式： 1)将候选点集合B根据相似度得分进行降序 排列。 (a)匹配之后的效果 (b)模板 (c)mask图 2)选择具有最大得分的点P,将其从B集合 中移除并加入到最终的候选点集合D中。 图6局部聚类效果 Fig.6 Sketch of local clustering 3)计算B中剩余候选点中与P距离dis,将 dis小于阈值d(此处阈值一般选择为模板的内切 可以看到，使用局部聚类，可以在线性时间内 圆半径)的点从B中移除。 快速滤除干扰点，将相邻候选点聚集成簇，减少 4)重复这个过程，直到B为空或D中候选点 后续候选点数，减少了计算量。 数已超过一定数量。此时D中保留的候选点，作 2.3.2逐层金字塔筛选 为本层最终的候选点集。 上一层得到若干候选点之后，传入本层，对候 NMS流程示意图如图7所示。刚开始O~O, 选点相应位置进行扩大区域方法搜索，如果计算 计算得到的分值分别为0.9、0.7、0.6、0.8；通过选 相似度大于阈值，将其传入到本层候选点集合 择最大得分O,加入候选集D并在B中删除，删 中。但是在本层候选集合中有很多候选点，全都 除B中与O1距离在r以内的点(O2、O),在B中 传入下一层进行扩散搜索是非常耗时的。为了减 选择最大得分的点（仅有O),加入到D中，并将 少运算量，这里引入非极大值抑制(non-maximum 其从B中删除，得到D{O、O}
中，即将该点对应 mask 值设置为 m_up 和 m_left 的较大值，如果 P 点对应相似度大于簇中最相似 点的相似度，则更新簇中最相似点的位置和相似 度，否则不更新 hash_table； ② 反之，如果 m_up 和 m_left 都为零，说明 P 是新的点，将 P 对应位置和相似度放入 hash_table 中，将对应 mask 点的值设置为 hash_table，以 此建立新的簇种子点。 3) 计算下一个点，重复步骤 2)，直到所有的 点遍历完，计算结束。 4) 最终将 hash_table 中的点位置保存下来。 初始化：mask为全 0，hash table为空 计算当前点P所在子 图与模板的相似度T T>thresh 计算当前点上方和左边点对 应mask值：m_up、m_left m_up=0 & m_left=0 N N N N Y Y Y Y table插入[P,T], mask[P]=table.size 计算下一个点 将P点对应mask值设 为max(m_up, m_left) T>hash_table[m_p] 使用当前P和T更新 hash_table值 不更新 hash_table 所有点计算完毕 结束计算 图 5 顶部层次聚类流程图 Fig. 5 Top hierarchical clustering flowchart 以 LENA 图像为例，使用局部聚类之后的 mask 图像如图 6 所示。 (a) 匹配之后的效果 (b) 模板 (c) mask图 图 6 局部聚类效果 Fig. 6 Sketch of local clustering 可以看到，使用局部聚类，可以在线性时间内 快速滤除干扰点，将相邻候选点聚集成簇，减少 后续候选点数，减少了计算量。 2.3.2 逐层金字塔筛选 上一层得到若干候选点之后，传入本层，对候 选点相应位置进行扩大区域方法搜索，如果计算 相似度大于阈值，将其传入到本层候选点集合 中。但是在本层候选集合中有很多候选点，全都 传入下一层进行扩散搜索是非常耗时的。为了减 少运算量，这里引入非极大值抑制 (non-maximum suppression, NMS)，选取本层最终候选点。 NMS 的基本思想是保留局部最大值、抑制非 极大值，计算流程如下：对于候选点列表 B 及其 对应的相似度 S，结果候选点集合为 D，采用下面 的计算方式： 1) 将候选点集合 B 根据相似度得分进行降序 排列。 2) 选择具有最大得分的点 P，将其从 B 集合 中移除并加入到最终的候选点集合 D 中。 3) 计算 B 中剩余候选点中与 P 距离 dis，将 dis 小于阈值 d(此处阈值一般选择为模板的内切 圆半径) 的点从 B 中移除。 4) 重复这个过程，直到 B 为空或 D 中候选点 数已超过一定数量。此时 D 中保留的候选点，作 为本层最终的候选点集。 NMS 流程示意图如图 7 所示。刚开始 O1~O4 计算得到的分值分别为 0.9、0.7、0.6、0.8；通过选 择最大得分 O1 加入候选集 D 并在 B 中删除，删 除 B 中与 O1 距离在 r 以内的点 (O2、O3 )，在 B 中 选择最大得分的点 (仅有 O4 )，加入到 D 中，并将 其从 B 中删除，得到 D{O1、O4}。 第 1 期 曹田，等：快速的圆投影图像匹配算法 ·87·
88· 智能系统学报 第15卷 立n周-pXnA- 00.8] 00.8] 6,k)= (10) NMS -(,a<×[(u0d-(m) =0 0I0.9] 式中：p,(n)和p,'(m)分别为模板图和待搜索子图 对应半径圆上像素灰度值。 (a)刚开始候选点集合B (b)处理的结果D 采用式(8)(10)，就可以计算出半径为r处候 图7非极大值抑制示意图 选点的旋转角度。为了提升角度估计的准确性， Fig.7 Diagram of NMS 提出了一种用角度直方图(angle histogram estima- 使用NMS减少了相邻候选点的出现，避免结 tion,AHE)估计角度的方法。详细表述为 果的重叠，同时可以根据输入目标点数的要求， 1)构建一个维数为360的数组a360],存放 得到最终指定数量的匹配目标。 旋转角度对应的环的数量。 2.4角度估计 2)计算半径为r处的旋转角度0，四舍五人 由于保存了所在圆环上像素的灰度，就可以 后angle放入直方图，即alangle]加l。 比较容易地计算出旋转角度。图8为环上像素值 3)对所有半径进行步骤2)，最终构建角度分 布的直方图。 分布图(=100) 4)检查步骤3)得到的角度直方图中的众数， 即为最终角度。 图8(b)以图8(a)为模板，计算旋转角度之后 的角度统计图如图9。 150r 140 (a)原图 (b)旋转110图 130 250 盘120 200 110 175 100 125 90 0 100 102030,40.50607080 r/pixel 15 (a)环上的角度统计 50 40. (110,39) 02040 6080100120140160 35 n/pixel (C)原图(P)和旋转后(P)环上像素值分布 ←25 图8环上像素值分布 20 Fig.8 Pixel value distributions in rings 10 可以看到，旋转之后，环上所有像素的灰度值 发生了环形移位（简称环移）。由此，在半径为 0 050100150200250300350400 r的环上，旋转角度6，可以定义为 角度/) 0,=k,X9 (8) (b)角度对应的环数量分布直方图 式中：k,为偏移量；9，为步进角度，9，=360°/N,其 图9环上角度统计及分布直方图 中N,为半径为r的环上像素数量。 Fig.9 Angle statistics and distribution histogram 偏移量k,定义为 可以看到，通过AHE,计算得到最终角度，为 k=arg max(,(k)),kE[0.N.] (9) 直方图中的众数（即尖峰即110），和理论旋转角 N,为半径为r的环上像素数量。6，()为偏移 度相符合。使用AHE可以对角度有较好的估计， k像素之后和模板中环的归一化互相关系数，定 避免r过小时计算角度误差较大，另外，对于环上 义为 存在同质区域（灰度值分布一致）时角度计算不
(a) 刚开始候选点集合B (b) 处理的结果D O4 [0.8] O4 [0.8] O3 [0.6] O2 [0.7] O1 [0.9] O1 [0.9] NMS 图 7 非极大值抑制示意图 Fig. 7 Diagram of NMS 使用 NMS 减少了相邻候选点的出现，避免结 果的重叠，同时可以根据输入目标点数的要求， 得到最终指定数量的匹配目标。 2.4 角度估计 由于保存了所在圆环上像素的灰度，就可以 比较容易地计算出旋转角度。图 8 为环上像素值 分布图 (r=100)。 (a) 原图 (b) 旋转110°图 (c) 原图(Pr )和旋转后(Pr ′)环上像素值分布 0 75 125 150 200 225 20 40 n/pixel 灰度 60 50 100 175 250 80 100 120 140 160 Pr Pr ′ 图 8 环上像素值分布 Fig. 8 Pixel value distributions in rings θr 可以看到，旋转之后，环上所有像素的灰度值 发生了环形移位 (简称环移)。由此，在半径为 r 的环上，旋转角度 可以定义为 θr = kr ×φr (8) kr φr φr = 360◦ /Nr Nr 式中： 为偏移量； 为步进角度， ，其 中 为半径为 r 的环上像素数量。 偏移量 kr 定义为 kr = argmax(δr(k)), k ∈ [0,Nr] (9) Nr 为半径为 r 的环上像素数量。 δr(k) 为偏移 k 像素之后和模板中环的归一化互相关系数，定 义为 δr(k) = ∑Nr n=0 [pr(n)− pr(n)]×[pr ′ (n)− pr ′ (n)] ∑Nr n=0 [pr(n)− pr(n)] 2 × ∑Nr n=0 [pr ′ (n)− pr ′ (n)] 2 (10) pr(n) pr ′ 式中： 和 (n) 分别为模板图和待搜索子图 对应半径圆上像素灰度值。 采用式 (8)~(10)，就可以计算出半径为 r 处候 选点的旋转角度。为了提升角度估计的准确性， 提出了一种用角度直方图 (angle histogram estimation, AHE) 估计角度的方法。详细表述为 1) 构建一个维数为 360 的数组 a[360]，存放 旋转角度对应的环的数量。 2) 计算半径为 r 处的旋转角度 θr，四舍五入 后 angle 放入直方图，即 a[angle] 加 1。 3) 对所有半径进行步骤 2)，最终构建角度分 布的直方图。 4) 检查步骤 3) 得到的角度直方图中的众数， 即为最终角度。 图 8(b) 以图 8(a) 为模板，计算旋转角度之后 的角度统计图如图 9。 (a) 环上的角度统计 (b) 角度对应的环数量分布直方图 0 90 100 120 130 140 150 20 40 r/pixel 角度/(°) 60 110 10 30 50 70 80 0 0 10 20 30 40 50 150 角度/(°) (110, 39) 环数量/个 250 5 15 25 35 100 200 300 350 400 图 9 环上角度统计及分布直方图 Fig. 9 Angle statistics and distribution histogram 可以看到，通过 AHE，计算得到最终角度，为 直方图中的众数 (即尖峰即 110°)，和理论旋转角 度相符合。使用 AHE 可以对角度有较好的估计， 避免 r 过小时计算角度误差较大，另外，对于环上 存在同质区域 (灰度值分布一致) 时角度计算不 ·88· 智 能 系 统 学 报 第 15 卷
第1期 曹田，等：快速的圆投影图像匹配算法 ·89· 正确的情况，也具有一定的抗干扰能力，提高了 角度和真实旋转角度之差的绝对值。为了提供一 角度估计的鲁棒性。 个全面的精度评价，使用误差Er的3个性能指标 2.5计算复杂度分析 来定量地展示性能：误差的均值Erm、误差的标 假设模板图像T大小为m×m(伴径为空，搜 准差Er_std和最大误差Er max。.匹配结果如表1 索图像S大小为M×M。 所示。 原始圆投影匹配中，预先计算模板中的圆投 影向量，然后进行匹配。在匹配过程中，先计算 搜索图中每一个子图的圆投影向量，然后计算和 模板圆投影的相似度，最后取其相似度最大值为 最佳匹配位置。其中子图数量为(M-m)×(M-m, (a)低曝光1 (b)低曝光2 (c)中曝光1 每一个子图计算圆投影时间为O(m×m),计算相 似度时间为O(m×m,整个匹配过程的时间复杂 度为O(M-m)×m2。随着模板和搜索图尺寸的 增加，搜索时间将成倍增长。 本文算法使用金字塔策略，采用局部聚类和 (d)中曝光2 (e)高曝光1 ()高曝光2 逐层筛选策略优化搜索速度。假设降采样到L 图10不同光照下匹配情况 层，计算缩小后的模板混合圆投影向量，则缩小 Fig.10 Matching results under different illuminations 的模板大小为受×公搜索子图数量为(M-mr2 顶部聚类时间为O(M-m)2×m2/2+。只有少数 候选点进人后续筛选过程，假设只保留n个点进 入最后匹配，则后续匹配耗时为On×m2),整体匹 配过程时间复杂度为Om2× +保 守估计，当M仁400，m=100,L=2,n=3时，本文算法 相对原始圆投影算法提升了约8倍。 (a)基准图 (b)模板图 3实验结果 图11旋转测试图片 使用上述方法，本文试验了多组同一目标在 Fig.11 Rotation test pictures 发生不同变化下的匹配效果。为了验证本方法的 表1旋转角度匹配结果 有效性，将结果与文献[17刀和文献[19]中的方法 Table 1 Matching results for rotation test 进行了比较。所有实验均在一台使用VS2013、 角度误差 文献[17刀 文献[19] 本文 OpenCV3.0.0、Intel Core i51.6 Hz CPU和8GB内 Er m/() 58.333 0.098 存的电脑上进行。 Er std/() 76.811 0.184 3.1光照变化 Er_max/() 180 1.107 图10是不同光照下使用工业相机拍摄的槟 榔干图片，图10(a)为模板图片，图10(b)~(f) 从表1可以看出，本算法误差均值、标准差 为光照变化时匹配图片，圆圈内为匹配结果。可 最大值分别为0.0988、0.1836、1.107。文献[17] 以看到，本算法针对过曝、欠曝图片都可以很好 中使用序贯相似性检测对匹配进行加速，但只用 地识别出来，具有很强的光照不变性。 圆投影向量进行目标的定位，并没有计算旋转角 3.2角度估计结果 度，这里不便进行比较。在文献[19]中，角度精 图11是旋转测试图片，用于估计所提出算法 度严重依赖于预先建立的旋转模板和使用归一化 的角度精度，图11(a)为旋转基准图(1296×972)， 互相关系数NCC)估计出来的位置。如果没有精 图11(b)为模板(180×180)。将原始图像在0-360° 确定位将无法准确估算出角度，文献[19]使用 范围内每间隔10°做一次旋转，一共得到36张图 9个预先建立的旋转模板。可以看到，本文算法 片，然后使用本文的算法，对旋转后的36幅图片 能进行较好的角度估计，且适用于任意旋转的 和原始基准图进行匹配。角度误差为匹配出来的 物体
正确的情况，也具有一定的抗干扰能力，提高了 角度估计的鲁棒性。 2.5 计算复杂度分析 m×m m 2 M × M 假设模板图像 T 大小为 (半径为 )，搜 索图像 S 大小为 。 (M −m)×(M −m) O(m×m) O(m×m) O [ (M −m) 2 ×m 2 ] 原始圆投影匹配中，预先计算模板中的圆投 影向量，然后进行匹配。在匹配过程中，先计算 搜索图中每一个子图的圆投影向量，然后计算和 模板圆投影的相似度，最后取其相似度最大值为 最佳匹配位置。其中子图数量为 ， 每一个子图计算圆投影时间为 ，计算相 似度时间为 ，整个匹配过程的时间复杂 度为 。随着模板和搜索图尺寸的 增加，搜索时间将成倍増长。 m 2 L × m 2 L (M −m) 2 /2 L+1 O [ (M −m) 2 ×m 2 /2 (L+1)] O(n×m 2 ) O { m 2 × [ (M −m) 2 2 L+1 +n ]} 本文算法使用金字塔策略，采用局部聚类和 逐层筛选策略优化搜索速度。假设降采样到 L 层，计算缩小后的模板混合圆投影向量，则缩小 的模板大小为 ，搜索子图数量为 ， 顶部聚类时间为 。只有少数 候选点进入后续筛选过程，假设只保留 n 个点进 入最后匹配，则后续匹配耗时为 ，整体匹 配过程时间复杂度为 。保 守估计，当 M=400，m=100，L=2，n=3 时，本文算法 相对原始圆投影算法提升了约 8 倍。 3 实验结果 使用上述方法，本文试验了多组同一目标在 发生不同变化下的匹配效果。为了验证本方法的 有效性，将结果与文献 [17] 和文献 [19] 中的方法 进行了比较。所有实验均在一台使用 VS2013、 OpenCV3.0.0、Intel Core i5 1.6 Hz CPU 和 8 GB 内 存的电脑上进行。 3.1 光照变化 图 10 是不同光照下使用工业相机拍摄的槟 榔干图片，图 10(a) 为模板图片，图 10(b)~(f) 为光照变化时匹配图片，圆圈内为匹配结果。可 以看到，本算法针对过曝、欠曝图片都可以很好 地识别出来，具有很强的光照不变性。 3.2 角度估计结果 1 296×972 180×180 图 11 是旋转测试图片，用于估计所提出算法 的角度精度，图 11(a) 为旋转基准图 ( )， 图 11(b) 为模板 ( )。将原始图像在 0~360° 范围内每间隔 10°做一次旋转，一共得到 36 张图 片，然后使用本文的算法，对旋转后的 36 幅图片 和原始基准图进行匹配。角度误差为匹配出来的 角度和真实旋转角度之差的绝对值。为了提供一 个全面的精度评价，使用误差 Er 的 3 个性能指标 来定量地展示性能：误差的均值 Er_m、误差的标 准差 Er_std 和最大误差 Er_max。匹配结果如表 1 所示。 (a) 低曝光1 (b) 低曝光2 (c) 中曝光1 (d) 中曝光2 (e) 高曝光1 (f) 高曝光2 图 10 不同光照下匹配情况 Fig. 10 Matching results under different illuminations (a) 基准图 (b) 模板图 图 11 旋转测试图片 Fig. 11 Rotation test pictures 表 1 旋转角度匹配结果 Table 1 Matching results for rotation test 角度误差 文献[17] 文献[19] 本文 Er_m/(°) — 58.333 0.098 Er_std/(°) — 76.811 0.184 Er_max/(°) — 180 1.107 从表 1 可以看出，本算法误差均值、标准差、 最大值分别为 0.098 8、0.183 6、1.107。文献 [17] 中使用序贯相似性检测对匹配进行加速，但只用 圆投影向量进行目标的定位，并没有计算旋转角 度，这里不便进行比较。在文献 [19] 中，角度精 度严重依赖于预先建立的旋转模板和使用归一化 互相关系数 (NCC) 估计出来的位置。如果没有精 确定位将无法准确估算出角度，文献 [19] 使用 9 个预先建立的旋转模板。可以看到，本文算法 能进行较好的角度估计，且适用于任意旋转的 物体。 第 1 期 曹田，等：快速的圆投影图像匹配算法 ·89·
·90· 智能系统学报 第15卷 3.3运行速度测试 tems.2011,6(6):507-514 使用工业相机捕获的PCB图像进行了运行 [2]阮晓虎，李卫军，罩鸿，等.一种基于特征匹配的人脸配 速度的测试。所用测试和相应的模板图像如图12 准判断方法.智能系统学报，2015,10(1)：12-19. 所示。测试图像的大小为1920×1080，模板图像 RUAN Xiaohu,LI Weijun,QIN Hong,et al.An assess- 为283×283。本实验根据匹配结果对计算性能进 ment method for face alignment based on feature match- 行了评估。此外，为了保证比较的公平性，本文 ing[J].CAAI transactions on intelligent systems,2015, 还利用图像金字塔搜索框架对比较方法进行了优 10(1):12-19 化。效率和金字塔层数的统计结果如表2所示。 [3】李龙，尹辉，许宏丽，等.一种鲁棒的Multi-Egocentric视 频中的多目标检测及匹配算法.智能系统学报，2016 11(5):619-626 LI Long,YIN Hui,XU Hongli,et al.A robust multi-object detection and matching algorithm for multi-egocentric videos[J].CAAI transactions on intelligent systems,2016, 11(5):619-626 、85 (a)测试图 (b)模板图 [4]王杰，蒋明敏，花晓慧，等.基于投影直方图匹配的双目 视觉跟踪算法[.智能系统学报，2015,10(5)：775-782. 图12性能测试图片 Fig.12 Efficiency test pictures WANG Jie,JIANG Mingmin,HUA Xiaohui,et al.Bin- ocular object tracking method using projection histogram 表2运行时间 matching[J].CAAI transactions on intelligent systems, Table 2 Running time 2015,10(5):775-782 金字塔层数 文献[17刀 文献[19] 本文 [5]ZITOVA B,FLUSSER J.Image registration methods:a 1 10.78 94.28 0.61 survey[J].Image and vision computing,2003,21(11): 2 4.32 19.92 0.43 977-1000 3 1.02 3.23 0.32 [6]AGGARWAL J K,DAVIS L S,MARTIN W N.Corres- pondence processes in dynamic scene analysis[J].Proceed- 由表2可以看出，本方法相对其他方法在运 ings of the IEEE,1981,69(5):562-572 行效率上有明显的优势，另外金字塔搜索策略可 [7]SECILLA J P,GRACIA N,CARRASCOSA J L.Tem- 以显著提高匹配效率。 plate location in noisy pictures[J].Signal processing,1988, 4结束语 14(4):347-361 [8]TANIMOTO S L.Template matching in pyramids[J]. 本文提出了一种快速的基于旋转不变圆投影 Computer graphics and image processing,1981,16(4): 向量的模板匹配方法。结合混合圆投影向量和图 356-369】 像金字塔搜索策略，可以减少计算量，提升匹配 [9]ROSENFELD A,KAK A,Digital image processing[M] 效率。另外结合环移和角度直方图统计，可以精 2nd ed.Orlando:Academic Press,1982 确地估计出旋转角度。结果表明，该方法的旋转 [10]LOWE D G.Distinctive image features from scale-invari- 估计优于其他同类方法。此外，该算法可以在旋 ant keypoints[J].International journal of computer vision, 转、偏移、光照变化场景图像中获得准确、鲁棒的 2004,60(2:91-110. 结果。各种实验结果表明，该方法适用于工业场 [1]郑永斌，黄新生，丰松江.SIFT和旋转不变LBP相结合 景中的图像匹配。 的图像匹配算法[J】.计算机辅助设计与图形学学报！ 参考文献： 2010,22(2):286-292 ZHENG Yongbin,HUANG Xinsheng,FENG Songjiang. [1]周可，秦世引.SFT特征匹配的辐射畸变图像相对校正 An image matching algorithm based on combination of 新方法[).智能系统学报，2011,6(6)：507-514 SIFT and the rotation invariant LBP[J].Journal of com- ZHOU Ke,QIN Shiyin.A novel method for relative cor- puter-aided design&computer graphics,2010,22(2): rection of a radiometric distortion image based on SIFT 286-292. feature matching[J].CAAI transactions on intelligent sys- [12]TANG YY.CHENG H D,SUEN C Y.Transformation-
3.3 运行速度测试 1 920×1 080 283×283 使用工业相机捕获的 PCB 图像进行了运行 速度的测试。所用测试和相应的模板图像如图 12 所示。测试图像的大小为 ，模板图像 为 。本实验根据匹配结果对计算性能进 行了评估。此外，为了保证比较的公平性，本文 还利用图像金字塔搜索框架对比较方法进行了优 化。效率和金字塔层数的统计结果如表 2 所示。 (a) 测试图 (b) 模板图 图 12 性能测试图片 Fig. 12 Efficiency test pictures 表 2 运行时间 Table 2 Running time s 金字塔层数 文献[17] 文献[19] 本文 1 10.78 94.28 0.61 2 4.32 19.92 0.43 3 1.02 3.23 0.32 由表 2 可以看出，本方法相对其他方法在运 行效率上有明显的优势，另外金字塔搜索策略可 以显著提高匹配效率。 4 结束语 本文提出了一种快速的基于旋转不变圆投影 向量的模板匹配方法。结合混合圆投影向量和图 像金字塔搜索策略，可以减少计算量，提升匹配 效率。另外结合环移和角度直方图统计，可以精 确地估计出旋转角度。结果表明，该方法的旋转 估计优于其他同类方法。此外，该算法可以在旋 转、偏移、光照变化场景图像中获得准确、鲁棒的 结果。各种实验结果表明，该方法适用于工业场 景中的图像匹配。 参考文献： 周可, 秦世引. SIFT 特征匹配的辐射畸变图像相对校正 新方法 [J]. 智能系统学报, 2011, 6(6): 507–514. ZHOU Ke, QIN Shiyin. A novel method for relative correction of a radiometric distortion image based on SIFT feature matching[J]. CAAI transactions on intelligent sys- [1] tems, 2011, 6(6): 507–514. 阮晓虎, 李卫军, 覃鸿, 等. 一种基于特征匹配的人脸配 准判断方法 [J]. 智能系统学报, 2015, 10(1): 12–19. RUAN Xiaohu, LI Weijun, QIN Hong, et al. An assessment method for face alignment based on feature matching[J]. CAAI transactions on intelligent systems, 2015, 10(1): 12–19. [2] 李龙, 尹辉, 许宏丽, 等. 一种鲁棒的 Multi-Egocentric 视 频中的多目标检测及匹配算法 [J]. 智能系统学报, 2016, 11(5): 619–626. LI Long, YIN Hui, XU Hongli, et al. A robust multi-object detection and matching algorithm for multi-egocentric videos[J]. CAAI transactions on intelligent systems, 2016, 11(5): 619–626. [3] 王杰, 蒋明敏, 花晓慧, 等. 基于投影直方图匹配的双目 视觉跟踪算法 [J]. 智能系统学报, 2015, 10(5): 775–782. WANG Jie, JIANG Mingmin, HUA Xiaohui, et al. Binocular object tracking method using projection histogram matching[J]. CAAI transactions on intelligent systems, 2015, 10(5): 775–782. [4] ZITOVÁ B, FLUSSER J. Image registration methods: a survey[J]. Image and vision computing, 2003, 21(11): 977–1000. [5] AGGARWAL J K, DAVIS L S, MARTIN W N. Correspondence processes in dynamic scene analysis[J]. Proceedings of the IEEE, 1981, 69(5): 562–572. [6] SECILLA J P, GRACIA N, CARRASCOSA J L. Template location in noisy pictures[J]. Signal processing, 1988, 14(4): 347–361. [7] TANIMOTO S L. Template matching in pyramids[J]. Computer graphics and image processing, 1981, 16(4): 356–369. [8] ROSENFELD A, KAK A, Digital image processing[M]. 2nd ed. Orlando: Academic Press, 1982. [9] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision, 2004, 60(2): 91–110. [10] 郑永斌, 黄新生, 丰松江. SIFT 和旋转不变 LBP 相结合 的图像匹配算法 [J]. 计算机辅助设计与图形学学报, 2010, 22(2): 286–292. ZHENG Yongbin, HUANG Xinsheng, FENG Songjiang. An image matching algorithm based on combination of SIFT and the rotation invariant LBP[J]. Journal of computer-aided design & computer graphics, 2010, 22(2): 286–292. [11] [12] TANG Y Y, CHENG H D, SUEN C Y. Transformation- ·90· 智 能 系 统 学 报 第 15 卷
第1期 曹田，等：快速的圆投影图像匹配算法 ·91· ring-projection(TRP)algorithm and its VLSI implement- tion transformation algorithm for arbitrary rotation match- ation[.International journal of pattern recognition and ing[J].Computer engineering and applications,2011, artificial intelligence,1991,5(1/2):25-56. 47(5:172-174. [13]TSAI D M,TSAI Y H.Rotation-invariant pattern match- [19]SASSANAPITAK S.KAEWTRAKULPONG P.An effi- ing with color ring-projection[J].Pattern recognition, cient translation-rotation template matching using pre- 2002,35(1:131-141. computed scores of rotated templates[C]//Proceedings of [14]LEE W C,CHEN C H.A fast template matching method the 6th International Conference on Electrical Engineer- with rotation invariance by combining the circular projec- ing/Electronics,Computer,Telecommunications and In- tion transform process and bounded partial correlation[]. formation Technology.Pattaya,Chonburi,Thailand: IEEE signal processing letters,2012,19(11):737-740. IEEE,2009:1040-1043 [15]徐亦斌，王敬东，李鹏.基于圆投影向量的景象匹配 作者简介： 方法研究[].系统工程与电子技术，2005,27(10)： 曹田，硕土研究生，主要研究方向 1725-1728. 为图像处理和计算机视觉。 XU Yibin,WANG Jingdong,LI Peng.Research on scene matching method using circular projection[J].Systems en- gineering and electronics,2005,27(10):1725-1728. [16]CHOI M S,KIM W Y.A novel two stage template matching method for rotation and illumination 李勃.副教授，主要研究方向为宽 invariance[J].Pattern recognition,2002,35(1):119-129. 带网络通信、人工智能、图像识别。 [1刀贾晓芬，赵佰亭，周孟然，等.采用圆投影和序贯相似检 申请国家发明专利11项，授权3件。 测的图像匹配技术).哈尔滨商业大学学报（自然科学 申请PCT、国家发明专利14项，已授 版).2015,31(2)232-236.241. 权3项，获奖1项。发表学术论文20 JIA Xiafen,ZHAO Baiting,ZHOU Mengran,et al.Fast 余篇。 image matching algorithm based on circular projection and sequential similarity detection[J].Journal of Harbin 任福继，教授，日本工程院和欧盟 University of Commerce (Natural Sciences Edition), 科学院院士，中国人工智能学会名誉 2015,31(2:232-236,241. 副理事长，日本工学会、IEICE、CAAI Fellow,日本国际先进信息研究所主 [18]于辉，张忠秋，何周灿.用于任意旋转角度景象匹配的 席。主要研究方向为人工智能、情感 圆投影算法[】.计算机工程与应用，2011,47(5)： 计算、自然言语理解、模式识别。获吴 172-174 文俊人工智能科学技术奖创新一等奖 YU Hui,ZHANG Zhongqiu,HE Zhoucan.Ring projec- 等，发明专利10余项，发表学术论文500余篇
ring-projection (TRP) algorithm and its VLSI implementation[J]. International journal of pattern recognition and artificial intelligence, 1991, 5(1/2): 25–56. TSAI D M, TSAI Y H. Rotation-invariant pattern matching with color ring-projection[J]. Pattern recognition, 2002, 35(1): 131–141. [13] LEE W C, CHEN C H. A fast template matching method with rotation invariance by combining the circular projection transform process and bounded partial correlation[J]. IEEE signal processing letters, 2012, 19(11): 737–740. [14] 徐亦斌, 王敬东, 李鹏. 基于圆投影向量的景象匹配 方法研究 [J]. 系统工程与电子技术, 2005, 27(10): 1725–1728. XU Yibin, WANG Jingdong, LI Peng. Research on scene matching method using circular projection[J]. Systems engineering and electronics, 2005, 27(10): 1725–1728. [15] CHOI M S, KIM W Y. A novel two stage template matching method for rotation and illumination invariance[J]. Pattern recognition, 2002, 35(1): 119–129. [16] 贾晓芬, 赵佰亭, 周孟然, 等. 采用圆投影和序贯相似检 测的图像匹配技术 [J]. 哈尔滨商业大学学报 (自然科学 版), 2015, 31(2): 232–236, 241. JIA Xiafen, ZHAO Baiting, ZHOU Mengran, et al. Fast image matching algorithm based on circular projection and sequential similarity detection[J]. Journal of Harbin University of Commerce (Natural Sciences Edition), 2015, 31(2): 232–236, 241. [17] 于辉, 张忠秋, 何周灿. 用于任意旋转角度景象匹配的 圆投影算法 [J]. 计算机工程与应用, 2011, 47(5): 172–174. YU Hui, ZHANG Zhongqiu, HE Zhoucan. Ring projec- [18] tion transformation algorithm for arbitrary rotation matching[J]. Computer engineering and applications, 2011, 47(5): 172–174. SASSANAPITAK S, KAEWTRAKULPONG P. An efficient translation-rotation template matching using precomputed scores of rotated templates[C]//Proceedings of the 6th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology. Pattaya, Chonburi, Thailand: IEEE, 2009: 1040–1043. [19] 作者简介： 曹田，硕士研究生，主要研究方向 为图像处理和计算机视觉。 李勃，副教授，主要研究方向为宽 带网络通信、人工智能、图像识别。 申请国家发明专利 11 项，授权 3 件。 申请 PCT、国家发明专利 14 项，已授 权 3 项，获奖 1 项。发表学术论文 20 余篇。 任福继，教授，日本工程院和欧盟 科学院院士，中国人工智能学会名誉 副理事长，日本工学会、IEICE、CAAI Fellow，日本国际先进信息研究所主 席。主要研究方向为人工智能、情感 计算、自然言语理解、模式识别。获吴 文俊人工智能科学技术奖创新一等奖 等，发明专利 10 余项，发表学术论文 500 余篇。 第 1 期 曹田，等：快速的圆投影图像匹配算法 ·91·