基于局部顏色直方圖的SIFT 算法研究＊

任海林，程欣宇，李洪杰

(貴州大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025)

圖像匹配是計算機(jī)視覺的基礎(chǔ)，它是圖像識別、圖像拼接、圖像恢復(fù)和目標(biāo)跟蹤等領(lǐng)域中的關(guān)鍵技術(shù)，大體可分為基于特征的圖像匹配和基于區(qū)域的圖像匹配兩類［1］。當(dāng)前，基于特征的圖像匹配的相關(guān)理論快速發(fā)展，成為了圖像匹配的主流方向，如SIFT 算法［2］。SIFT 算法是一種基于特征的圖像匹配算子，它是一種對旋轉(zhuǎn)、尺度縮放和光照保持良好不變性的局部特征描述算子。文獻(xiàn)［3］通過實驗證明了SIFT 算法對光照、幾何變形、分辨率差異和旋轉(zhuǎn)具有一定的不變性，是識別率最佳的算法之一。

大多數(shù)圖像匹配算法是將彩色圖像轉(zhuǎn)化為灰度圖像，利用灰度信息尋找圖像中的幾何不變量，進(jìn)行圖像的匹配。SIFT 算法也只使用圖像的灰度信息，忽略顏色信息，導(dǎo)致對彩色目標(biāo)匹配能力降低。

為了對彩色目標(biāo)獲得更高的識別率，研究者提出了各種彩色SIFT 描述子，特別是根據(jù)各種光照不變性模型提出的各種彩色SIFT 描述子，如HSVSIFT［4］，Hue-SIFT［5］，W-SIFT［6］、Opponent-SIFT，RGB-SIFT 和Transform Color SIFT 等等。文獻(xiàn)［7］在不同的環(huán)境中對比了各種彩色描述算子的性能，不同描述算子的性能在不同的測試集中有所不同，Opponent-SIFT 在測試圖像集和測試視頻中都取得了較好的效果。但這些彩色SIFT 算法都是通過分別計算三個通道的128 維特征描述，然后組成一個128×3 維的特征描述，最終完成彩色目標(biāo)匹配。顯然，這些算法不僅在三個通道上計算特征描述，同時也大大增加了特征描述的維數(shù)，從而大大增加了匹配時間。文獻(xiàn)［8］提出基于顏色量化矩陣的SIFT 算法(CQM-SIFT)，在HSV 空間中生成量化矩陣，然后根據(jù)量化矩陣生成128 維的SIFT 特征描述子，最后應(yīng)用于彩色目標(biāo)匹配，有效地提高了識別率和縮短了匹配時間。

顏色直方圖為在給定的離散彩色空間(如HSV 空間)，分別計算顏色空間各通道中各顏色的概率。文獻(xiàn)［9］通過實驗證明圖像進(jìn)行旋轉(zhuǎn)、縮放、模糊變換的直方圖改變較小，即直方圖具有對圖像變換的不敏感性。但是，它是全局顏色統(tǒng)計特征，丟失了像素點的位置特征，相同的顏色直方圖可能對應(yīng)完全不同的圖像，特別是對復(fù)雜場景它趨于無效。

結(jié)合SIFT 算法的問題和顏色直方圖，以及人民幣面值識別程序?qū)r間的要求高的特點，本文提出一種基于局部顏色直方圖的彩色SIFT 描述算子(CH-SIFT)。SIFT 算法的描述算子僅使用了關(guān)鍵點處的紋理信息，本文提出的方法不僅在關(guān)鍵點處使用紋理信息，而且使用顏色信息。本文通過對比SIFT 算法、Opponent-SIFT 算法和CH-SIFT 算法，實驗證明CH-SIFT 算法的有效性。

1 SIFT 算法分析

SIFT 算法的實質(zhì)是在不同的尺度空間上查找關(guān)鍵點，計算出關(guān)鍵點的方向和生成關(guān)鍵點特征描述。其關(guān)鍵點是一些十分突出，不會因光照，仿射變換和噪聲等因素變化而變化的點，如角點、邊緣點、亮區(qū)的暗點及暗區(qū)的亮點。實現(xiàn)SIFT 算法的關(guān)鍵在于關(guān)鍵點檢測，生成關(guān)鍵點特征描述。Lowe［2］將SIFT 算法分解為四步:尺度空間極值檢測、關(guān)鍵點的精確定位、關(guān)鍵點方向分配、關(guān)鍵點特征描述。

1.1 尺度空間極值檢測

SIFT 算法首先通過降采樣和不同尺度的高斯濾波建立高斯金字塔，然后使用高斯差分在各層高斯金字塔組內(nèi)獲取高斯差分圖像，最后在每組高斯差分圖像中檢測出潛在的對尺度和旋轉(zhuǎn)不變的極值點。

一幅圖像的尺度空間L(x，y，σ)定義為一個變化尺度的高斯函數(shù)G(x，y，σ)與原圖像I(x，y)的卷積:

其中，?表示卷積操作，σ為尺度因子。

為了獲取局部極值點，利用高斯金字塔的各層組內(nèi)相鄰圖相差建立高斯差分尺度空間(DoG):其中，k為相鄰兩個尺度空間的比例因子。

檢測極值點時，每一個像素點要和它同尺度的8 個相鄰像素和上下相鄰尺度的9×2 個點(共26個點)進(jìn)行比較，以確保是在尺度空間和二維圖像空間檢測到的極值點。

1.2 關(guān)鍵點的精確定位

檢測到的極值點不都是穩(wěn)定的精確關(guān)鍵點，而且DoG 算子會產(chǎn)生較強(qiáng)的邊緣響應(yīng)，因此需要去除對比度低的極值點、不穩(wěn)定的邊緣響應(yīng)和進(jìn)行關(guān)鍵點精確定位，以增強(qiáng)匹配的穩(wěn)定性和提高抗噪聲能力，最后得到穩(wěn)定和精確位置的關(guān)鍵點。

檢測到的極值點為離散空間的極值點，為獲取精確的極值點，需對尺度空間DoG 函數(shù)進(jìn)行曲線擬合。利用DoG 函數(shù)在尺度空間的Taylor 展開式:

對于邊緣的不穩(wěn)定響應(yīng)點，使用2×2 的Hessian 矩陣來判斷是否去留。

1.3 關(guān)鍵點方向分配

為支持描述子對圖像旋轉(zhuǎn)具有不變性，通過計算關(guān)鍵點鄰域像素的梯度方向為其分配一個或多個方向。關(guān)鍵點在(x，y)處的梯度的模和方向分別為:

完成關(guān)鍵點的梯度的模計算后，使用直方圖統(tǒng)計鄰域內(nèi)各方向內(nèi)的像素的梯度的模。梯度直方圖中每10 度為一柱，共36 柱。以梯度方向為直方圖的橫軸，梯度的模為縱軸，將鄰域內(nèi)的每一個像素點按照梯度方向θ 歸入對應(yīng)的柱。為增強(qiáng)匹配的魯棒性，選擇直方圖的主方向峰值作為關(guān)鍵點的方向，同時能量高于主方向峰值的80%作為關(guān)鍵點的輔助方向，即一個關(guān)鍵點有一個或多個方向。

1.4 關(guān)鍵點特征描述

關(guān)鍵點特征描述是為每一個關(guān)鍵點建立一個描述符，用一組向量將這個關(guān)鍵點信息描述出來，它不僅包括關(guān)鍵點，而且包括周圍對關(guān)鍵點有貢獻(xiàn)的像素點，使其具有各種不變性。

Lowe 建議以關(guān)鍵點為中心，在4×4 共16 個子窗口中計算8 個方向的梯度直方圖統(tǒng)計信息，形成共4×4×8 共128 維梯度直方圖特征描述，作為關(guān)鍵點的特征描述，其中每個子窗口的大小與尺度有關(guān)，為3σ_oct，σ_oct為組內(nèi)圖像尺度。

2 基于局部顏色直方圖的SIFT 算法

SIFT 算法的關(guān)鍵點特征描述僅使用灰度信息，忽略顏色信息，導(dǎo)致紋理相似的彩色圖像匹配率降低。為解決此問題，本文結(jié)合顏色直方圖的特點，將關(guān)鍵點鄰域內(nèi)的顏色直方圖的統(tǒng)計信息作為關(guān)鍵點的描述，分層次匹配，從而提高彩色圖像的識別率。

2.1 顏色直方圖原理

顏色直方圖為在給定的離散彩色空間(如HSV 空間)，分別計算顏色空間各通道中各顏色的概率。其優(yōu)點為它對圖像的旋轉(zhuǎn)、縮放、模糊保持良好的不變性;其缺點為它是全局顏色統(tǒng)計的結(jié)果，丟失了像素點的位置特征。本文算法是在每個關(guān)鍵點p(即位置信息)半徑為σp鄰域內(nèi)計算顏色直方圖，即局部顏色直方圖，因而在一定程度上消除了直方圖的無位置特征的缺點。

設(shè)輸入24 位HSV 彩色空間圖像I(x，y)，CHSIFT 算法的顏色直方圖H(i)為:

式(5)中，Lc為彩色空間通道c 被劃分的級數(shù)，hi為像素值Ixy到第i 級中心的距離，hi+1為像素值Ixy到第i+1 級中心的距離，如圖1 所示。顏色直方圖認(rèn)為像素值Ixy與級別中心的距離有關(guān)系，離級別中心越近，δ 值越大。同時關(guān)鍵點鄰域內(nèi)的各個像素點具有不同的權(quán)重，離關(guān)鍵點越近，權(quán)重越大，實驗采用高斯函數(shù)獲得權(quán)重。圖1 中的像素值Ixy分解為第1 級和第2 級，且離第一級中心較近，所以δ(1)值較大。

在實驗中，將RGB 空間轉(zhuǎn)換為HSV 空間，然后在HSV 空間計算各個關(guān)鍵點在鄰域內(nèi)的各個通道的等級為LH=32，LS=LV=16，然后在關(guān)鍵點鄰域內(nèi)生成顏色直方圖特征描述。

2.2 顏色直方圖匹配

直方圖匹配就是衡量兩個直方圖的相似性，令Hp和Hq分別為目標(biāo)圖像中關(guān)鍵點p 和標(biāo)準(zhǔn)圖像集中關(guān)鍵點q 的鄰域的顏色直方圖，則顏色直方圖的歐式距離為:

圖1 直方圖的級數(shù)劃分方法

其中，Lc與(1)式相同，kc為不同顏色通道的權(quán)重。當(dāng)d(Hp，Hq)越小，說明兩關(guān)鍵點鄰域顏色相似度越大，當(dāng)d(Hp，Hq)大于一定的閾值時，說明兩顏色直方圖不相似。

3 實驗步驟

本文所提CH-SIFT 算法與SIFT 算法有兩點不同，一是生成關(guān)鍵點描述中不僅對所有的檢測關(guān)鍵點生成梯度直方圖特征描述，而且生成顏色直方圖特征描述;二是特征描述匹配過程中，首先使用梯度直方圖特征描述匹配，然后串聯(lián)使用顏色直方圖特征描述匹配，所提方法的流程圖如圖2 所示。除灰色背景的顏色直方圖特征描述和顏色直方圖特征描述匹配兩項外，其他項和SIFT［3］算法完全相同，因此不做介紹。

圖2 CH-SIFT 算法流程圖

3.1 顏色直方圖特征描述

為提取每一個關(guān)鍵點的顏色直方圖特征描述，首先需構(gòu)建彩色空間各通道的高斯尺度空間，其參數(shù)與SIFT 算法構(gòu)建高斯尺度空間完全一樣;然后根據(jù)關(guān)鍵點的位置在每個通道的高斯尺度空間中計算關(guān)鍵點鄰域的顏色直方圖，并歸一化以保證尺度不變性;最后根據(jù)每個通道的顏色信息的重要性，加權(quán)合并為一個關(guān)鍵點的顏色直方圖特征描述，為下一步的匹配做準(zhǔn)備。在實驗中，為消除光照強(qiáng)度整體變化的影響，在建立高斯尺度空間之前需對各通道的圖像歸一化。

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

匹配就是在一個關(guān)鍵點集合中搜索出與當(dāng)前關(guān)鍵點最相似的點，如果兩點相似度小于等于閾值THRESHOLD，則添加此匹配對，否則去除。實驗中采用歐式距離計算梯度直方圖特征描述的相似度。假設(shè)當(dāng)前點所在集合的基數(shù)為M，搜索集合的基數(shù)為N，特征描述為D=128 維，則時間復(fù)雜度為T(m，n)=O(M× N× D)。實際上，當(dāng)前關(guān)鍵點沒必要和搜索集合中的每一個關(guān)鍵點都計算D 維，因為前面d(d ≤D)維的計算結(jié)果如果大于THRESHOLD，則此匹配對應(yīng)刪除。

實驗中首先初始化當(dāng)前關(guān)鍵點與搜索集合關(guān)鍵點的最小閾值為minThreshold=THRESHOLD，然后計算每維特征描述后，判斷歐式距離和dist 是否大于minThreshold，如果是，則提前結(jié)束計算;當(dāng)D 維歐式距離和dist ＜ minThreshold 時，更 新minThreshold=dist，并更新當(dāng)前搜索關(guān)鍵點為最佳匹配關(guān)鍵點。經(jīng)過N 次循環(huán)后，如果minThreshold≤THRESHOLD，則當(dāng)前關(guān)鍵點與最佳匹配關(guān)鍵點組合為有效匹配對，否則去除。實驗表明，此方法平均提高1～5 倍速度。

3.3 顏色直方圖特征描述匹配

在匹配時，通過顏色直方圖特征描述對梯度直方圖特征描述匹配的結(jié)果進(jìn)行篩選，以達(dá)到提高彩色目標(biāo)識別率的目的。實驗中采用歐式距離計算顏色直方圖特征描述的相似度。為提高速度，采用和3.2 類似的剪枝算法。

4 實驗與對比分析

人民幣面值識別軟件是為特殊人群開發(fā)的一款能夠識別不同人民幣面值的軟件，它應(yīng)用計算機(jī)視覺技術(shù)，能夠在不同的場景中識別出不同的人民幣面值。本實驗以人民幣識別為基礎(chǔ)，使用計算機(jī)視覺庫Open CV 實現(xiàn)人民幣面值識別算法，算法分為離線訓(xùn)練和在線檢測兩過程。

離線訓(xùn)練過程中，首先收集不同人民幣面值的標(biāo)準(zhǔn)圖像，分別是1、5、10、20、50、100 元的正反兩面共12 張圖像，然后利用SIFT 算法、Opponent-SIFT 算法和本文所提的CH-SIFT 算法離線提取關(guān)鍵點和特征描述;在線檢測過程中，首先建立使用相機(jī)拍攝的不同光照、背景、縮放、局部區(qū)域人民幣和不同旋轉(zhuǎn)角度等復(fù)雜場景中的原圖，大小為1200×1600(或1600×1200)，經(jīng)重采樣為400×533(或533×400)的50×12 張人民幣測試圖像集，并標(biāo)記人民幣面值類標(biāo)簽，如圖3 所示。然后分別檢測每一張測試圖像在標(biāo)準(zhǔn)圖像集的相似度。為了使匹配結(jié)果具有穩(wěn)定性，在匹配結(jié)果中，當(dāng)次好匹配率小于最好匹配率的80%時(因1 元正面和50 元正面的顏色較為相似，閾值設(shè)為85%)，且最好匹配的結(jié)果和標(biāo)記的類標(biāo)簽相同時，匹配正確，否則匹配錯誤。

圖3 不同場景100 元正面實驗圖像集

實驗將50×12 張圖像集分為三個圖像集測試，分別為人民幣正面圖像集、人民幣反面圖像集、人民幣正反面圖像集，表1為在不同圖像集中檢測的結(jié)果。不同算法對人民幣反面圖像集識別率均很高，而對人民幣正面圖像集識別率偏低，其原因是不同人民幣的反面圖案存在較大差異，而不同人民幣的正面存在很多紋理相同而顏色不同的圖案，如國徽，毛主席頭像等，在復(fù)雜環(huán)境中獲得的圖像的亮度信息可能很相似，從而導(dǎo)致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 算法的匹配結(jié)果。圖4(a)為錯誤匹配，圖4(b)和圖4(c)為正確匹配。錯誤匹配的原因是測試圖像為人民幣局部區(qū)域，關(guān)鍵點較少，主要集中在毛主席圖案上，且受光照不均、模糊和縮放等因素的影響，導(dǎo)致亮度信息與50 元人民幣正面更相似，從而出現(xiàn)誤匹配;正確匹配的原因是Opponent-SIFT 將圖像變換到Opponent 空間，不同顏色的圖像的每個通道區(qū)分較大，使不同顏色的圖像易于區(qū)分;CH-SIFT 算法利用梯度直方圖統(tǒng)計關(guān)鍵點鄰域的紋理信息和使用顏色直方圖統(tǒng)計關(guān)鍵點鄰域的顏色信息，在紋理和顏色上均限制匹配對的相似性。

表2為圖4 左邊10 元人民幣正面在SIFT、Opponent-SIFT 和CH-SIFT 算法中的不同關(guān)鍵步驟運行30 次平均花費的時間。實驗結(jié)果表明，通過剪枝算法，關(guān)鍵點匹配階段節(jié)約1～5 倍時間。Opponent-SIFT 算法在關(guān)鍵點檢測與描述階段的時間為SIFT 算法的2.6 倍;在關(guān)鍵點匹配階段，因特征描述長度是SIFT 算法的3 倍，所以花費時間為SIFT算法的3 倍，加上剪枝算法節(jié)約時間不同，最終花費的時間是SIFT 算法的6.7 倍。在剪枝的情況下，CH-SIFT 算法花費的總時間是SIFT 算法的1.7倍，遠(yuǎn)低于Opponent-SIFT 算法花費的時間;在非剪枝的情況下，CH-SIFT 算法花費的總時間接近SIFT算法的時間。根據(jù)正確匹配對數(shù)量比較，CH-SIFT算法效果最好。

圖4 不同算法對10 元人民幣正面圖像的匹配結(jié)果

表2 不同算法的關(guān)鍵步驟時間比較 ms

5 結(jié)語

本文根據(jù)SIFT 算法對彩色目標(biāo)識別率較低的原因，結(jié)合顏色直方圖的特點，提出了CH-SIFT 算法。實驗表明，在紋理不同且顏色不同的人民幣反面圖像集中，CH-SIFT 算法和SIFT 算法保持相近的識別率;而在大量紋理相同而顏色不同的人民幣正面圖像集中，CH-SIFT 算法的識別率比SIFT 算法高。實驗中對比Opponent-SIFT 算法的識別率和時間，CH-SIFT 算法的識別率與Opponent-SIFT 算法相近，但是所花時間少，證明了本文方法是有效的。

［1］王娟，師軍，吳憲祥.圖像拼接技術(shù)綜述［J］.計算機(jī)應(yīng)用研究，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］.山東大學(xué)學(xué)報:工學(xué)版，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.