基于局部颜色直方图的SIFT 算法研究＊

任海林，程欣宇，李洪杰

(贵州大学 计算机科学与技术学院，贵州 贵阳 550025)

图像匹配是计算机视觉的基础，它是图像识别、图像拼接、图像恢复和目标跟踪等领域中的关键技术，大体可分为基于特征的图像匹配和基于区域的图像匹配两类［1］。当前，基于特征的图像匹配的相关理论快速发展，成为了图像匹配的主流方向，如SIFT 算法［2］。SIFT 算法是一种基于特征的图像匹配算子，它是一种对旋转、尺度缩放和光照保持良好不变性的局部特征描述算子。文献［3］通过实验证明了SIFT 算法对光照、几何变形、分辨率差异和旋转具有一定的不变性，是识别率最佳的算法之一。

大多数图像匹配算法是将彩色图像转化为灰度图像，利用灰度信息寻找图像中的几何不变量，进行图像的匹配。SIFT 算法也只使用图像的灰度信息，忽略颜色信息，导致对彩色目标匹配能力降低。

为了对彩色目标获得更高的识别率，研究者提出了各种彩色SIFT 描述子，特别是根据各种光照不变性模型提出的各种彩色SIFT 描述子，如HSVSIFT［4］，Hue-SIFT［5］，W-SIFT［6］、Opponent-SIFT，RGB-SIFT 和Transform Color SIFT 等等。文献［7］在不同的环境中对比了各种彩色描述算子的性能，不同描述算子的性能在不同的测试集中有所不同，Opponent-SIFT 在测试图像集和测试视频中都取得了较好的效果。但这些彩色SIFT 算法都是通过分别计算三个通道的128 维特征描述，然后组成一个128×3 维的特征描述，最终完成彩色目标匹配。显然，这些算法不仅在三个通道上计算特征描述，同时也大大增加了特征描述的维数，从而大大增加了匹配时间。文献［8］提出基于颜色量化矩阵的SIFT 算法(CQM-SIFT)，在HSV 空间中生成量化矩阵，然后根据量化矩阵生成128 维的SIFT 特征描述子，最后应用于彩色目标匹配，有效地提高了识别率和缩短了匹配时间。

颜色直方图为在给定的离散彩色空间(如HSV 空间)，分别计算颜色空间各通道中各颜色的概率。文献［9］通过实验证明图像进行旋转、缩放、模糊变换的直方图改变较小，即直方图具有对图像变换的不敏感性。但是，它是全局颜色统计特征，丢失了像素点的位置特征，相同的颜色直方图可能对应完全不同的图像，特别是对复杂场景它趋于无效。

结合SIFT 算法的问题和颜色直方图，以及人民币面值识别程序对时间的要求高的特点，本文提出一种基于局部颜色直方图的彩色SIFT 描述算子(CH-SIFT)。SIFT 算法的描述算子仅使用了关键点处的纹理信息，本文提出的方法不仅在关键点处使用纹理信息，而且使用颜色信息。本文通过对比SIFT 算法、Opponent-SIFT 算法和CH-SIFT 算法，实验证明CH-SIFT 算法的有效性。

1 SIFT 算法分析

SIFT 算法的实质是在不同的尺度空间上查找关键点，计算出关键点的方向和生成关键点特征描述。其关键点是一些十分突出，不会因光照，仿射变换和噪声等因素变化而变化的点，如角点、边缘点、亮区的暗点及暗区的亮点。实现SIFT 算法的关键在于关键点检测，生成关键点特征描述。Lowe［2］将SIFT 算法分解为四步:尺度空间极值检测、关键点的精确定位、关键点方向分配、关键点特征描述。

1.1 尺度空间极值检测

SIFT 算法首先通过降采样和不同尺度的高斯滤波建立高斯金字塔，然后使用高斯差分在各层高斯金字塔组内获取高斯差分图像，最后在每组高斯差分图像中检测出潜在的对尺度和旋转不变的极值点。

一幅图像的尺度空间L(x，y，σ)定义为一个变化尺度的高斯函数G(x，y，σ)与原图像I(x，y)的卷积:

其中，⊗表示卷积操作，σ为尺度因子。

为了获取局部极值点，利用高斯金字塔的各层组内相邻图相差建立高斯差分尺度空间(DoG):其中，k为相邻两个尺度空间的比例因子。

检测极值点时，每一个像素点要和它同尺度的8 个相邻像素和上下相邻尺度的9×2 个点(共26个点)进行比较，以确保是在尺度空间和二维图像空间检测到的极值点。

1.2 关键点的精确定位

检测到的极值点不都是稳定的精确关键点，而且DoG 算子会产生较强的边缘响应，因此需要去除对比度低的极值点、不稳定的边缘响应和进行关键点精确定位，以增强匹配的稳定性和提高抗噪声能力，最后得到稳定和精确位置的关键点。

检测到的极值点为离散空间的极值点，为获取精确的极值点，需对尺度空间DoG 函数进行曲线拟合。利用DoG 函数在尺度空间的Taylor 展开式:

对于边缘的不稳定响应点，使用2×2 的Hessian 矩阵来判断是否去留。

1.3 关键点方向分配

为支持描述子对图像旋转具有不变性，通过计算关键点邻域像素的梯度方向为其分配一个或多个方向。关键点在(x，y)处的梯度的模和方向分别为:

完成关键点的梯度的模计算后，使用直方图统计邻域内各方向内的像素的梯度的模。梯度直方图中每10 度为一柱，共36 柱。以梯度方向为直方图的横轴，梯度的模为纵轴，将邻域内的每一个像素点按照梯度方向θ 归入对应的柱。为增强匹配的鲁棒性，选择直方图的主方向峰值作为关键点的方向，同时能量高于主方向峰值的80%作为关键点的辅助方向，即一个关键点有一个或多个方向。

1.4 关键点特征描述

关键点特征描述是为每一个关键点建立一个描述符，用一组向量将这个关键点信息描述出来，它不仅包括关键点，而且包括周围对关键点有贡献的像素点，使其具有各种不变性。

Lowe 建议以关键点为中心，在4×4 共16 个子窗口中计算8 个方向的梯度直方图统计信息，形成共4×4×8 共128 维梯度直方图特征描述，作为关键点的特征描述，其中每个子窗口的大小与尺度有关，为3σ_oct，σ_oct为组内图像尺度。

2 基于局部颜色直方图的SIFT 算法

SIFT 算法的关键点特征描述仅使用灰度信息，忽略颜色信息，导致纹理相似的彩色图像匹配率降低。为解决此问题，本文结合颜色直方图的特点，将关键点邻域内的颜色直方图的统计信息作为关键点的描述，分层次匹配，从而提高彩色图像的识别率。

2.1 颜色直方图原理

颜色直方图为在给定的离散彩色空间(如HSV 空间)，分别计算颜色空间各通道中各颜色的概率。其优点为它对图像的旋转、缩放、模糊保持良好的不变性;其缺点为它是全局颜色统计的结果，丢失了像素点的位置特征。本文算法是在每个关键点p(即位置信息)半径为σp邻域内计算颜色直方图，即局部颜色直方图，因而在一定程度上消除了直方图的无位置特征的缺点。

设输入24 位HSV 彩色空间图像I(x，y)，CHSIFT 算法的颜色直方图H(i)为:

式(5)中，Lc为彩色空间通道c 被划分的级数，hi为像素值Ixy到第i 级中心的距离，hi+1为像素值Ixy到第i+1 级中心的距离，如图1 所示。颜色直方图认为像素值Ixy与级别中心的距离有关系，离级别中心越近，δ 值越大。同时关键点邻域内的各个像素点具有不同的权重，离关键点越近，权重越大，实验采用高斯函数获得权重。图1 中的像素值Ixy分解为第1 级和第2 级，且离第一级中心较近，所以δ(1)值较大。

在实验中，将RGB 空间转换为HSV 空间，然后在HSV 空间计算各个关键点在邻域内的各个通道的等级为LH=32，LS=LV=16，然后在关键点邻域内生成颜色直方图特征描述。

2.2 颜色直方图匹配

直方图匹配就是衡量两个直方图的相似性，令Hp和Hq分别为目标图像中关键点p 和标准图像集中关键点q 的邻域的颜色直方图，则颜色直方图的欧式距离为:

图1 直方图的级数划分方法

其中，Lc与(1)式相同，kc为不同颜色通道的权重。当d(Hp，Hq)越小，说明两关键点邻域颜色相似度越大，当d(Hp，Hq)大于一定的阈值时，说明两颜色直方图不相似。

3 实验步骤

本文所提CH-SIFT 算法与SIFT 算法有两点不同，一是生成关键点描述中不仅对所有的检测关键点生成梯度直方图特征描述，而且生成颜色直方图特征描述;二是特征描述匹配过程中，首先使用梯度直方图特征描述匹配，然后串联使用颜色直方图特征描述匹配，所提方法的流程图如图2 所示。除灰色背景的颜色直方图特征描述和颜色直方图特征描述匹配两项外，其他项和SIFT［3］算法完全相同，因此不做介绍。

图2 CH-SIFT 算法流程图

3.1 颜色直方图特征描述

为提取每一个关键点的颜色直方图特征描述，首先需构建彩色空间各通道的高斯尺度空间，其参数与SIFT 算法构建高斯尺度空间完全一样;然后根据关键点的位置在每个通道的高斯尺度空间中计算关键点邻域的颜色直方图，并归一化以保证尺度不变性;最后根据每个通道的颜色信息的重要性，加权合并为一个关键点的颜色直方图特征描述，为下一步的匹配做准备。在实验中，为消除光照强度整体变化的影响，在建立高斯尺度空间之前需对各通道的图像归一化。

3.2 梯度直方图特征描述匹配

匹配就是在一个关键点集合中搜索出与当前关键点最相似的点，如果两点相似度小于等于阈值THRESHOLD，则添加此匹配对，否则去除。实验中采用欧式距离计算梯度直方图特征描述的相似度。假设当前点所在集合的基数为M，搜索集合的基数为N，特征描述为D=128 维，则时间复杂度为T(m，n)=O(M× N× D)。实际上，当前关键点没必要和搜索集合中的每一个关键点都计算D 维，因为前面d(d ≤D)维的计算结果如果大于THRESHOLD，则此匹配对应删除。

实验中首先初始化当前关键点与搜索集合关键点的最小阈值为minThreshold=THRESHOLD，然后计算每维特征描述后，判断欧式距离和dist 是否大于minThreshold，如果是，则提前结束计算;当D 维欧式距离和dist ＜ minThreshold 时，更 新minThreshold=dist，并更新当前搜索关键点为最佳匹配关键点。经过N 次循环后，如果minThreshold≤THRESHOLD，则当前关键点与最佳匹配关键点组合为有效匹配对，否则去除。实验表明，此方法平均提高1～5 倍速度。

3.3 颜色直方图特征描述匹配

在匹配时，通过颜色直方图特征描述对梯度直方图特征描述匹配的结果进行筛选，以达到提高彩色目标识别率的目的。实验中采用欧式距离计算颜色直方图特征描述的相似度。为提高速度，采用和3.2 类似的剪枝算法。

4 实验与对比分析

人民币面值识别软件是为特殊人群开发的一款能够识别不同人民币面值的软件，它应用计算机视觉技术，能够在不同的场景中识别出不同的人民币面值。本实验以人民币识别为基础，使用计算机视觉库Open CV 实现人民币面值识别算法，算法分为离线训练和在线检测两过程。

离线训练过程中，首先收集不同人民币面值的标准图像，分别是1、5、10、20、50、100 元的正反两面共12 张图像，然后利用SIFT 算法、Opponent-SIFT 算法和本文所提的CH-SIFT 算法离线提取关键点和特征描述;在线检测过程中，首先建立使用相机拍摄的不同光照、背景、缩放、局部区域人民币和不同旋转角度等复杂场景中的原图，大小为1200×1600(或1600×1200)，经重采样为400×533(或533×400)的50×12 张人民币测试图像集，并标记人民币面值类标签，如图3 所示。然后分别检测每一张测试图像在标准图像集的相似度。为了使匹配结果具有稳定性，在匹配结果中，当次好匹配率小于最好匹配率的80%时(因1 元正面和50 元正面的颜色较为相似，阈值设为85%)，且最好匹配的结果和标记的类标签相同时，匹配正确，否则匹配错误。

图3 不同场景100 元正面实验图像集

实验将50×12 张图像集分为三个图像集测试，分别为人民币正面图像集、人民币反面图像集、人民币正反面图像集，表1为在不同图像集中检测的结果。不同算法对人民币反面图像集识别率均很高，而对人民币正面图像集识别率偏低，其原因是不同人民币的反面图案存在较大差异，而不同人民币的正面存在很多纹理相同而颜色不同的图案，如国徽，毛主席头像等，在复杂环境中获得的图像的亮度信息可能很相似，从而导致SIFT 算法误匹配增加，识别率降低。表1为SIFT、Opponent-SIFT和CH-SIFT 三种算法的识别率和时间对比，在人民币正面图像集中，Opponent-SIFT 的识别率最高，但时间最多，CH-SIFT 算法识别率和时间居中，比SIFT 算法的识别率提高了6.7%;在人民币正反面图像集中，CH-SIFT 算法识别率和Opponent-SIFT相近，但后者识别时间是前者的1.71 倍。

表1 不同算法的正确率和时间比较

图4为10 元人民币正面通过SIFT、Opponent-SIFT 和CH-SIFT 算法的匹配结果。图4(a)为错误匹配，图4(b)和图4(c)为正确匹配。错误匹配的原因是测试图像为人民币局部区域，关键点较少，主要集中在毛主席图案上，且受光照不均、模糊和缩放等因素的影响，导致亮度信息与50 元人民币正面更相似，从而出现误匹配;正确匹配的原因是Opponent-SIFT 将图像变换到Opponent 空间，不同颜色的图像的每个通道区分较大，使不同颜色的图像易于区分;CH-SIFT 算法利用梯度直方图统计关键点邻域的纹理信息和使用颜色直方图统计关键点邻域的颜色信息，在纹理和颜色上均限制匹配对的相似性。

表2为图4 左边10 元人民币正面在SIFT、Opponent-SIFT 和CH-SIFT 算法中的不同关键步骤运行30 次平均花费的时间。实验结果表明，通过剪枝算法，关键点匹配阶段节约1～5 倍时间。Opponent-SIFT 算法在关键点检测与描述阶段的时间为SIFT 算法的2.6 倍;在关键点匹配阶段，因特征描述长度是SIFT 算法的3 倍，所以花费时间为SIFT算法的3 倍，加上剪枝算法节约时间不同，最终花费的时间是SIFT 算法的6.7 倍。在剪枝的情况下，CH-SIFT 算法花费的总时间是SIFT 算法的1.7倍，远低于Opponent-SIFT 算法花费的时间;在非剪枝的情况下，CH-SIFT 算法花费的总时间接近SIFT算法的时间。根据正确匹配对数量比较，CH-SIFT算法效果最好。

图4 不同算法对10 元人民币正面图像的匹配结果

表2 不同算法的关键步骤时间比较 ms

5 结语

本文根据SIFT 算法对彩色目标识别率较低的原因，结合颜色直方图的特点，提出了CH-SIFT 算法。实验表明，在纹理不同且颜色不同的人民币反面图像集中，CH-SIFT 算法和SIFT 算法保持相近的识别率;而在大量纹理相同而颜色不同的人民币正面图像集中，CH-SIFT 算法的识别率比SIFT 算法高。实验中对比Opponent-SIFT 算法的识别率和时间，CH-SIFT 算法的识别率与Opponent-SIFT 算法相近，但是所花时间少，证明了本文方法是有效的。

［1］王娟，师军，吴宪祥.图像拼接技术综述［J］.计算机应用研究，2008，25(7):1940－1943.

［2］Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91－110.

［3］Mikolajczyk K，Schmid C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1615－1630.

［4］BoschA，Zisserman A，Muoz X.Scene classification using a hybrid generative/discriminative approach［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30(4):712－727.

［5］Weijer J，Gevers T，Bagdanov A.Boosting color saliency in image feature detection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(1):150－156.

［6］Geusebroek J M，Boomgaard R，Smeulders A W M，et al.Color invariance［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23(12):1338－1350.

［7］Van de sande K E A，Snoek C G M.Evaluation of color descriptors for object and scene recognition［C］//Proceedings of the Computer Vision and Pattern Recognition Conference.New York:Institute of Electrical and Electronics Engineers Computer Society，2008:542－560.

［8］汤伯超，蔡念，程昱.基于颜色量化矩阵的SIFT 特征描述方法［J］.山东大学学报:工学版，2011，41(2):46－50.

［9］M J Swain，D H Ballard.Color indexing［J］.International Journal of Computer Vision，1991，7(1):11－32.