任海林,程欣宇,李洪杰
(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴州 貴陽(yáng) 550025)
圖像匹配是計(jì)算機(jī)視覺(jué)的基礎(chǔ),它是圖像識(shí)別、圖像拼接、圖像恢復(fù)和目標(biāo)跟蹤等領(lǐng)域中的關(guān)鍵技術(shù),大體可分為基于特征的圖像匹配和基于區(qū)域的圖像匹配兩類[1]。當(dāng)前,基于特征的圖像匹配的相關(guān)理論快速發(fā)展,成為了圖像匹配的主流方向,如SIFT 算法[2]。SIFT 算法是一種基于特征的圖像匹配算子,它是一種對(duì)旋轉(zhuǎn)、尺度縮放和光照保持良好不變性的局部特征描述算子。文獻(xiàn)[3]通過(guò)實(shí)驗(yàn)證明了SIFT 算法對(duì)光照、幾何變形、分辨率差異和旋轉(zhuǎn)具有一定的不變性,是識(shí)別率最佳的算法之一。
大多數(shù)圖像匹配算法是將彩色圖像轉(zhuǎn)化為灰度圖像,利用灰度信息尋找圖像中的幾何不變量,進(jìn)行圖像的匹配。SIFT 算法也只使用圖像的灰度信息,忽略顏色信息,導(dǎo)致對(duì)彩色目標(biāo)匹配能力降低。
為了對(duì)彩色目標(biāo)獲得更高的識(shí)別率,研究者提出了各種彩色SIFT 描述子,特別是根據(jù)各種光照不變性模型提出的各種彩色SIFT 描述子,如HSVSIFT[4],Hue-SIFT[5],W-SIFT[6]、Opponent-SIFT,RGB-SIFT 和Transform Color SIFT 等等。文獻(xiàn)[7]在不同的環(huán)境中對(duì)比了各種彩色描述算子的性能,不同描述算子的性能在不同的測(cè)試集中有所不同,Opponent-SIFT 在測(cè)試圖像集和測(cè)試視頻中都取得了較好的效果。但這些彩色SIFT 算法都是通過(guò)分別計(jì)算三個(gè)通道的128 維特征描述,然后組成一個(gè)128×3 維的特征描述,最終完成彩色目標(biāo)匹配。顯然,這些算法不僅在三個(gè)通道上計(jì)算特征描述,同時(shí)也大大增加了特征描述的維數(shù),從而大大增加了匹配時(shí)間。文獻(xiàn)[8]提出基于顏色量化矩陣的SIFT 算法(CQM-SIFT),在HSV 空間中生成量化矩陣,然后根據(jù)量化矩陣生成128 維的SIFT 特征描述子,最后應(yīng)用于彩色目標(biāo)匹配,有效地提高了識(shí)別率和縮短了匹配時(shí)間。
顏色直方圖為在給定的離散彩色空間(如HSV 空間),分別計(jì)算顏色空間各通道中各顏色的概率。文獻(xiàn)[9]通過(guò)實(shí)驗(yàn)證明圖像進(jìn)行旋轉(zhuǎn)、縮放、模糊變換的直方圖改變較小,即直方圖具有對(duì)圖像變換的不敏感性。但是,它是全局顏色統(tǒng)計(jì)特征,丟失了像素點(diǎn)的位置特征,相同的顏色直方圖可能對(duì)應(yīng)完全不同的圖像,特別是對(duì)復(fù)雜場(chǎng)景它趨于無(wú)效。
結(jié)合SIFT 算法的問(wèn)題和顏色直方圖,以及人民幣面值識(shí)別程序?qū)r(shí)間的要求高的特點(diǎn),本文提出一種基于局部顏色直方圖的彩色SIFT 描述算子(CH-SIFT)。SIFT 算法的描述算子僅使用了關(guān)鍵點(diǎn)處的紋理信息,本文提出的方法不僅在關(guān)鍵點(diǎn)處使用紋理信息,而且使用顏色信息。本文通過(guò)對(duì)比SIFT 算法、Opponent-SIFT 算法和CH-SIFT 算法,實(shí)驗(yàn)證明CH-SIFT 算法的有效性。
SIFT 算法的實(shí)質(zhì)是在不同的尺度空間上查找關(guān)鍵點(diǎn),計(jì)算出關(guān)鍵點(diǎn)的方向和生成關(guān)鍵點(diǎn)特征描述。其關(guān)鍵點(diǎn)是一些十分突出,不會(huì)因光照,仿射變換和噪聲等因素變化而變化的點(diǎn),如角點(diǎn)、邊緣點(diǎn)、亮區(qū)的暗點(diǎn)及暗區(qū)的亮點(diǎn)。實(shí)現(xiàn)SIFT 算法的關(guān)鍵在于關(guān)鍵點(diǎn)檢測(cè),生成關(guān)鍵點(diǎn)特征描述。Lowe[2]將SIFT 算法分解為四步:尺度空間極值檢測(cè)、關(guān)鍵點(diǎn)的精確定位、關(guān)鍵點(diǎn)方向分配、關(guān)鍵點(diǎn)特征描述。
SIFT 算法首先通過(guò)降采樣和不同尺度的高斯濾波建立高斯金字塔,然后使用高斯差分在各層高斯金字塔組內(nèi)獲取高斯差分圖像,最后在每組高斯差分圖像中檢測(cè)出潛在的對(duì)尺度和旋轉(zhuǎn)不變的極值點(diǎn)。
一幅圖像的尺度空間L(x,y,σ)定義為一個(gè)變化尺度的高斯函數(shù)G(x,y,σ)與原圖像I(x,y)的卷積:
其中,?表示卷積操作,σ為尺度因子。
為了獲取局部極值點(diǎn),利用高斯金字塔的各層組內(nèi)相鄰圖相差建立高斯差分尺度空間(DoG):其中,k為相鄰兩個(gè)尺度空間的比例因子。
檢測(cè)極值點(diǎn)時(shí),每一個(gè)像素點(diǎn)要和它同尺度的8 個(gè)相鄰像素和上下相鄰尺度的9×2 個(gè)點(diǎn)(共26個(gè)點(diǎn))進(jìn)行比較,以確保是在尺度空間和二維圖像空間檢測(cè)到的極值點(diǎn)。
檢測(cè)到的極值點(diǎn)不都是穩(wěn)定的精確關(guān)鍵點(diǎn),而且DoG 算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng),因此需要去除對(duì)比度低的極值點(diǎn)、不穩(wěn)定的邊緣響應(yīng)和進(jìn)行關(guān)鍵點(diǎn)精確定位,以增強(qiáng)匹配的穩(wěn)定性和提高抗噪聲能力,最后得到穩(wěn)定和精確位置的關(guān)鍵點(diǎn)。
檢測(cè)到的極值點(diǎn)為離散空間的極值點(diǎn),為獲取精確的極值點(diǎn),需對(duì)尺度空間DoG 函數(shù)進(jìn)行曲線擬合。利用DoG 函數(shù)在尺度空間的Taylor 展開(kāi)式:
對(duì)于邊緣的不穩(wěn)定響應(yīng)點(diǎn),使用2×2 的Hessian 矩陣來(lái)判斷是否去留。
為支持描述子對(duì)圖像旋轉(zhuǎn)具有不變性,通過(guò)計(jì)算關(guān)鍵點(diǎn)鄰域像素的梯度方向?yàn)槠浞峙湟粋€(gè)或多個(gè)方向。關(guān)鍵點(diǎn)在(x,y)處的梯度的模和方向分別為:
完成關(guān)鍵點(diǎn)的梯度的模計(jì)算后,使用直方圖統(tǒng)計(jì)鄰域內(nèi)各方向內(nèi)的像素的梯度的模。梯度直方圖中每10 度為一柱,共36 柱。以梯度方向?yàn)橹狈綀D的橫軸,梯度的模為縱軸,將鄰域內(nèi)的每一個(gè)像素點(diǎn)按照梯度方向θ 歸入對(duì)應(yīng)的柱。為增強(qiáng)匹配的魯棒性,選擇直方圖的主方向峰值作為關(guān)鍵點(diǎn)的方向,同時(shí)能量高于主方向峰值的80%作為關(guān)鍵點(diǎn)的輔助方向,即一個(gè)關(guān)鍵點(diǎn)有一個(gè)或多個(gè)方向。
關(guān)鍵點(diǎn)特征描述是為每一個(gè)關(guān)鍵點(diǎn)建立一個(gè)描述符,用一組向量將這個(gè)關(guān)鍵點(diǎn)信息描述出來(lái),它不僅包括關(guān)鍵點(diǎn),而且包括周圍對(duì)關(guān)鍵點(diǎn)有貢獻(xiàn)的像素點(diǎn),使其具有各種不變性。
Lowe 建議以關(guān)鍵點(diǎn)為中心,在4×4 共16 個(gè)子窗口中計(jì)算8 個(gè)方向的梯度直方圖統(tǒng)計(jì)信息,形成共4×4×8 共128 維梯度直方圖特征描述,作為關(guān)鍵點(diǎn)的特征描述,其中每個(gè)子窗口的大小與尺度有關(guān),為3σ_oct,σ_oct為組內(nèi)圖像尺度。
SIFT 算法的關(guān)鍵點(diǎn)特征描述僅使用灰度信息,忽略顏色信息,導(dǎo)致紋理相似的彩色圖像匹配率降低。為解決此問(wèn)題,本文結(jié)合顏色直方圖的特點(diǎn),將關(guān)鍵點(diǎn)鄰域內(nèi)的顏色直方圖的統(tǒng)計(jì)信息作為關(guān)鍵點(diǎn)的描述,分層次匹配,從而提高彩色圖像的識(shí)別率。
顏色直方圖為在給定的離散彩色空間(如HSV 空間),分別計(jì)算顏色空間各通道中各顏色的概率。其優(yōu)點(diǎn)為它對(duì)圖像的旋轉(zhuǎn)、縮放、模糊保持良好的不變性;其缺點(diǎn)為它是全局顏色統(tǒng)計(jì)的結(jié)果,丟失了像素點(diǎn)的位置特征。本文算法是在每個(gè)關(guān)鍵點(diǎn)p(即位置信息)半徑為σp鄰域內(nèi)計(jì)算顏色直方圖,即局部顏色直方圖,因而在一定程度上消除了直方圖的無(wú)位置特征的缺點(diǎn)。
設(shè)輸入24 位HSV 彩色空間圖像I(x,y),CHSIFT 算法的顏色直方圖H(i)為:
式(5)中,Lc為彩色空間通道c 被劃分的級(jí)數(shù),hi為像素值Ixy到第i 級(jí)中心的距離,hi+1為像素值Ixy到第i+1 級(jí)中心的距離,如圖1 所示。顏色直方圖認(rèn)為像素值Ixy與級(jí)別中心的距離有關(guān)系,離級(jí)別中心越近,δ 值越大。同時(shí)關(guān)鍵點(diǎn)鄰域內(nèi)的各個(gè)像素點(diǎn)具有不同的權(quán)重,離關(guān)鍵點(diǎn)越近,權(quán)重越大,實(shí)驗(yàn)采用高斯函數(shù)獲得權(quán)重。圖1 中的像素值Ixy分解為第1 級(jí)和第2 級(jí),且離第一級(jí)中心較近,所以δ(1)值較大。
在實(shí)驗(yàn)中,將RGB 空間轉(zhuǎn)換為HSV 空間,然后在HSV 空間計(jì)算各個(gè)關(guān)鍵點(diǎn)在鄰域內(nèi)的各個(gè)通道的等級(jí)為L(zhǎng)H=32,LS=LV=16,然后在關(guān)鍵點(diǎn)鄰域內(nèi)生成顏色直方圖特征描述。
直方圖匹配就是衡量?jī)蓚€(gè)直方圖的相似性,令Hp和Hq分別為目標(biāo)圖像中關(guān)鍵點(diǎn)p 和標(biāo)準(zhǔn)圖像集中關(guān)鍵點(diǎn)q 的鄰域的顏色直方圖,則顏色直方圖的歐式距離為:
圖1 直方圖的級(jí)數(shù)劃分方法
其中,Lc與(1)式相同,kc為不同顏色通道的權(quán)重。當(dāng)d(Hp,Hq)越小,說(shuō)明兩關(guān)鍵點(diǎn)鄰域顏色相似度越大,當(dāng)d(Hp,Hq)大于一定的閾值時(shí),說(shuō)明兩顏色直方圖不相似。
本文所提CH-SIFT 算法與SIFT 算法有兩點(diǎn)不同,一是生成關(guān)鍵點(diǎn)描述中不僅對(duì)所有的檢測(cè)關(guān)鍵點(diǎn)生成梯度直方圖特征描述,而且生成顏色直方圖特征描述;二是特征描述匹配過(guò)程中,首先使用梯度直方圖特征描述匹配,然后串聯(lián)使用顏色直方圖特征描述匹配,所提方法的流程圖如圖2 所示。除灰色背景的顏色直方圖特征描述和顏色直方圖特征描述匹配兩項(xiàng)外,其他項(xiàng)和SIFT[3]算法完全相同,因此不做介紹。
圖2 CH-SIFT 算法流程圖
為提取每一個(gè)關(guān)鍵點(diǎn)的顏色直方圖特征描述,首先需構(gòu)建彩色空間各通道的高斯尺度空間,其參數(shù)與SIFT 算法構(gòu)建高斯尺度空間完全一樣;然后根據(jù)關(guān)鍵點(diǎn)的位置在每個(gè)通道的高斯尺度空間中計(jì)算關(guān)鍵點(diǎn)鄰域的顏色直方圖,并歸一化以保證尺度不變性;最后根據(jù)每個(gè)通道的顏色信息的重要性,加權(quán)合并為一個(gè)關(guān)鍵點(diǎn)的顏色直方圖特征描述,為下一步的匹配做準(zhǔn)備。在實(shí)驗(yàn)中,為消除光照強(qiáng)度整體變化的影響,在建立高斯尺度空間之前需對(duì)各通道的圖像歸一化。
匹配就是在一個(gè)關(guān)鍵點(diǎn)集合中搜索出與當(dāng)前關(guān)鍵點(diǎn)最相似的點(diǎn),如果兩點(diǎn)相似度小于等于閾值THRESHOLD,則添加此匹配對(duì),否則去除。實(shí)驗(yàn)中采用歐式距離計(jì)算梯度直方圖特征描述的相似度。假設(shè)當(dāng)前點(diǎn)所在集合的基數(shù)為M,搜索集合的基數(shù)為N,特征描述為D=128 維,則時(shí)間復(fù)雜度為T(m,n)=O(M× N× D)。實(shí)際上,當(dāng)前關(guān)鍵點(diǎn)沒(méi)必要和搜索集合中的每一個(gè)關(guān)鍵點(diǎn)都計(jì)算D 維,因?yàn)榍懊鎑(d ≤D)維的計(jì)算結(jié)果如果大于THRESHOLD,則此匹配對(duì)應(yīng)刪除。
實(shí)驗(yàn)中首先初始化當(dāng)前關(guān)鍵點(diǎn)與搜索集合關(guān)鍵點(diǎn)的最小閾值為minThreshold=THRESHOLD,然后計(jì)算每維特征描述后,判斷歐式距離和dist 是否大于minThreshold,如果是,則提前結(jié)束計(jì)算;當(dāng)D 維歐式距離和dist < minThreshold 時(shí),更 新minThreshold=dist,并更新當(dāng)前搜索關(guān)鍵點(diǎn)為最佳匹配關(guān)鍵點(diǎn)。經(jīng)過(guò)N 次循環(huán)后,如果minThreshold≤THRESHOLD,則當(dāng)前關(guān)鍵點(diǎn)與最佳匹配關(guān)鍵點(diǎn)組合為有效匹配對(duì),否則去除。實(shí)驗(yàn)表明,此方法平均提高1~5 倍速度。
在匹配時(shí),通過(guò)顏色直方圖特征描述對(duì)梯度直方圖特征描述匹配的結(jié)果進(jìn)行篩選,以達(dá)到提高彩色目標(biāo)識(shí)別率的目的。實(shí)驗(yàn)中采用歐式距離計(jì)算顏色直方圖特征描述的相似度。為提高速度,采用和3.2 類似的剪枝算法。
人民幣面值識(shí)別軟件是為特殊人群開(kāi)發(fā)的一款能夠識(shí)別不同人民幣面值的軟件,它應(yīng)用計(jì)算機(jī)視覺(jué)技術(shù),能夠在不同的場(chǎng)景中識(shí)別出不同的人民幣面值。本實(shí)驗(yàn)以人民幣識(shí)別為基礎(chǔ),使用計(jì)算機(jī)視覺(jué)庫(kù)Open CV 實(shí)現(xiàn)人民幣面值識(shí)別算法,算法分為離線訓(xùn)練和在線檢測(cè)兩過(guò)程。
離線訓(xùn)練過(guò)程中,首先收集不同人民幣面值的標(biāo)準(zhǔn)圖像,分別是1、5、10、20、50、100 元的正反兩面共12 張圖像,然后利用SIFT 算法、Opponent-SIFT 算法和本文所提的CH-SIFT 算法離線提取關(guān)鍵點(diǎn)和特征描述;在線檢測(cè)過(guò)程中,首先建立使用相機(jī)拍攝的不同光照、背景、縮放、局部區(qū)域人民幣和不同旋轉(zhuǎn)角度等復(fù)雜場(chǎng)景中的原圖,大小為1200×1600(或1600×1200),經(jīng)重采樣為400×533(或533×400)的50×12 張人民幣測(cè)試圖像集,并標(biāo)記人民幣面值類標(biāo)簽,如圖3 所示。然后分別檢測(cè)每一張測(cè)試圖像在標(biāo)準(zhǔn)圖像集的相似度。為了使匹配結(jié)果具有穩(wěn)定性,在匹配結(jié)果中,當(dāng)次好匹配率小于最好匹配率的80%時(shí)(因1 元正面和50 元正面的顏色較為相似,閾值設(shè)為85%),且最好匹配的結(jié)果和標(biāo)記的類標(biāo)簽相同時(shí),匹配正確,否則匹配錯(cuò)誤。
圖3 不同場(chǎng)景100 元正面實(shí)驗(yàn)圖像集
實(shí)驗(yàn)將50×12 張圖像集分為三個(gè)圖像集測(cè)試,分別為人民幣正面圖像集、人民幣反面圖像集、人民幣正反面圖像集,表1為在不同圖像集中檢測(cè)的結(jié)果。不同算法對(duì)人民幣反面圖像集識(shí)別率均很高,而對(duì)人民幣正面圖像集識(shí)別率偏低,其原因是不同人民幣的反面圖案存在較大差異,而不同人民幣的正面存在很多紋理相同而顏色不同的圖案,如國(guó)徽,毛主席頭像等,在復(fù)雜環(huán)境中獲得的圖像的亮度信息可能很相似,從而導(dǎo)致SIFT 算法誤匹配增加,識(shí)別率降低。表1為SIFT、Opponent-SIFT和CH-SIFT 三種算法的識(shí)別率和時(shí)間對(duì)比,在人民幣正面圖像集中,Opponent-SIFT 的識(shí)別率最高,但時(shí)間最多,CH-SIFT 算法識(shí)別率和時(shí)間居中,比SIFT 算法的識(shí)別率提高了6.7%;在人民幣正反面圖像集中,CH-SIFT 算法識(shí)別率和Opponent-SIFT相近,但后者識(shí)別時(shí)間是前者的1.71 倍。
表1 不同算法的正確率和時(shí)間比較
圖4為10 元人民幣正面通過(guò)SIFT、Opponent-SIFT 和CH-SIFT 算法的匹配結(jié)果。圖4(a)為錯(cuò)誤匹配,圖4(b)和圖4(c)為正確匹配。錯(cuò)誤匹配的原因是測(cè)試圖像為人民幣局部區(qū)域,關(guān)鍵點(diǎn)較少,主要集中在毛主席圖案上,且受光照不均、模糊和縮放等因素的影響,導(dǎo)致亮度信息與50 元人民幣正面更相似,從而出現(xiàn)誤匹配;正確匹配的原因是Opponent-SIFT 將圖像變換到Opponent 空間,不同顏色的圖像的每個(gè)通道區(qū)分較大,使不同顏色的圖像易于區(qū)分;CH-SIFT 算法利用梯度直方圖統(tǒng)計(jì)關(guān)鍵點(diǎn)鄰域的紋理信息和使用顏色直方圖統(tǒng)計(jì)關(guān)鍵點(diǎn)鄰域的顏色信息,在紋理和顏色上均限制匹配對(duì)的相似性。
表2為圖4 左邊10 元人民幣正面在SIFT、Opponent-SIFT 和CH-SIFT 算法中的不同關(guān)鍵步驟運(yùn)行30 次平均花費(fèi)的時(shí)間。實(shí)驗(yàn)結(jié)果表明,通過(guò)剪枝算法,關(guān)鍵點(diǎn)匹配階段節(jié)約1~5 倍時(shí)間。Opponent-SIFT 算法在關(guān)鍵點(diǎn)檢測(cè)與描述階段的時(shí)間為SIFT 算法的2.6 倍;在關(guān)鍵點(diǎn)匹配階段,因特征描述長(zhǎng)度是SIFT 算法的3 倍,所以花費(fèi)時(shí)間為SIFT算法的3 倍,加上剪枝算法節(jié)約時(shí)間不同,最終花費(fèi)的時(shí)間是SIFT 算法的6.7 倍。在剪枝的情況下,CH-SIFT 算法花費(fèi)的總時(shí)間是SIFT 算法的1.7倍,遠(yuǎn)低于Opponent-SIFT 算法花費(fèi)的時(shí)間;在非剪枝的情況下,CH-SIFT 算法花費(fèi)的總時(shí)間接近SIFT算法的時(shí)間。根據(jù)正確匹配對(duì)數(shù)量比較,CH-SIFT算法效果最好。
圖4 不同算法對(duì)10 元人民幣正面圖像的匹配結(jié)果
表2 不同算法的關(guān)鍵步驟時(shí)間比較 ms
本文根據(jù)SIFT 算法對(duì)彩色目標(biāo)識(shí)別率較低的原因,結(jié)合顏色直方圖的特點(diǎn),提出了CH-SIFT 算法。實(shí)驗(yàn)表明,在紋理不同且顏色不同的人民幣反面圖像集中,CH-SIFT 算法和SIFT 算法保持相近的識(shí)別率;而在大量紋理相同而顏色不同的人民幣正面圖像集中,CH-SIFT 算法的識(shí)別率比SIFT 算法高。實(shí)驗(yàn)中對(duì)比Opponent-SIFT 算法的識(shí)別率和時(shí)間,CH-SIFT 算法的識(shí)別率與Opponent-SIFT 算法相近,但是所花時(shí)間少,證明了本文方法是有效的。
[1]王娟,師軍,吳憲祥.圖像拼接技術(shù)綜述[J].計(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é)報(bào):工學(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.