第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·