黃超，齊英劍

(中國(guó)傳媒大學(xué)理學(xué)院，北京， 100024)

SIFT算法研究和應(yīng)用

黃超，齊英劍

(中國(guó)傳媒大學(xué)理學(xué)院，北京， 100024)

圖像匹配是計(jì)算機(jī)視覺(jué)中眾多問(wèn)題的一個(gè)基本方面，包括目標(biāo)和場(chǎng)景識(shí)別，從多圖片里解決三維結(jié)構(gòu)，立體相關(guān)性和動(dòng)作追蹤。本論文主要對(duì)SIFT算法的基本步驟進(jìn)行了簡(jiǎn)單闡述，并且闡述了其在場(chǎng)景分類(lèi)上的獨(dú)特應(yīng)用，以及一些重要改進(jìn)。實(shí)驗(yàn)結(jié)果表明該算法具有在場(chǎng)景識(shí)別和分類(lèi)上有較顯著的優(yōu)勢(shì)，可以進(jìn)行良好應(yīng)用。

特征描述符;尺度空間;詞包分類(lèi)算法;獨(dú)立成分分析;背影檢測(cè)

1 SIFT算法介紹

1.1 引言

1999年哥倫比亞大學(xué)的David G..Lowe教授提出了SIFT算法，一種基于提取局部特征的算法在尺度空間尋找極值點(diǎn)，提取位置，尺度，旋轉(zhuǎn)不變量。其具有局部性、特殊性、多量性和高效性等特性。他在2004年又把算法進(jìn)行了完善總結(jié)，后來(lái)Y.Ke將其描述子部分用PCA代替直方圖的方式，對(duì)其進(jìn)行改進(jìn)。該算法較好的解決了物體在發(fā)生旋轉(zhuǎn)縮放、視角、光度變化引起的圖像變形等問(wèn)題。

1.2 SIFT 算法原理

David G..Lowe在2004年總結(jié)了現(xiàn)有的基于不變量技術(shù)的特征檢測(cè)方法，提出了一種基于尺度空間的、對(duì)圖像縮放、旋轉(zhuǎn)和仿射變換具有不變性的圖像局部特征描述子——SIFT算子。該算法首先在特征空間進(jìn)行特征檢測(cè)，并確定關(guān)鍵點(diǎn)的位置和所處的尺度，然后使用關(guān)鍵點(diǎn)鄰域的梯度方向作為該點(diǎn)的方向，以實(shí)現(xiàn)算子對(duì)尺度和方向的無(wú)關(guān)性，從而得到了一種對(duì)尺度和方向無(wú)關(guān)的算子。

1.2.1 尺度空間極值點(diǎn)檢測(cè)

尺度空間理論最早出現(xiàn)于計(jì)算機(jī)視覺(jué)領(lǐng)域時(shí)其目的是模擬圖像數(shù)據(jù)的多尺度特征。Koendetink證明了高斯卷積核是實(shí)現(xiàn)尺度變換的唯一變換核，而Lindeburg等人則進(jìn)一步證明高斯核是唯一的線性核。一幅二維圖像在不同尺度下的尺度空間表示可由圖像與高斯卷積核得到:

因此，要提取穩(wěn)定的具有尺度無(wú)關(guān)性的特征點(diǎn)，就必須在圖像二維空間和DOG(Difference of Gaussian)尺度空間中同時(shí)檢測(cè)局部極值點(diǎn)。

在DOG空間檢測(cè)極值時(shí)，需要把關(guān)鍵點(diǎn)與同一尺度的周?chē)徲?個(gè)像素和相鄰2 6個(gè)像素進(jìn)行比較，以確保同時(shí)在尺度空間和二維圖像空間檢測(cè)局部極值。

DOG算子計(jì)算比較簡(jiǎn)單，是尺度歸一化的LOG算子的近似。

1.2.2 特征點(diǎn)過(guò)濾并進(jìn)行準(zhǔn)確定位

準(zhǔn)確確定關(guān)鍵點(diǎn)的位置和尺度，在該過(guò)程中，要同時(shí)去除低對(duì)比度的特征點(diǎn)和不穩(wěn)定的邊緣相應(yīng)點(diǎn)，以增強(qiáng)提取出來(lái)的描述符的有效性和實(shí)用性，提高抗噪能力。

DOG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng)，因此要通過(guò)擬合三維二次函數(shù)以準(zhǔn)確確定關(guān)鍵點(diǎn)的位置和尺度。

1.2.3 關(guān)鍵點(diǎn)方向分配

利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具有旋轉(zhuǎn)不變性。

至此，圖像的關(guān)鍵點(diǎn)已檢測(cè)完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息:位置、所處尺度、方向。這樣就可以一個(gè)SIFT特征區(qū)域。

1.2.4 生成描述特征點(diǎn)的特征向量

首區(qū)域計(jì)算8個(gè)方向的梯度直方圖，繪制每個(gè)梯度方向的累計(jì)值，即可形成一個(gè)種子點(diǎn)，這樣對(duì)于每個(gè)關(guān)鍵點(diǎn)就可以形成一個(gè)128維的SIFT特征向量。此時(shí)SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何變形因素的影響，然后將特征向量的長(zhǎng)度歸一化，就可以進(jìn)一步去除光照條件的影響。這種鄰域方向性信息聯(lián)合的思想增強(qiáng)了算法的抗噪聲能力，同時(shí)對(duì)于含有定位誤差的特征匹配也提供了較好的容錯(cuò)能力。特征向量生成示意圖如下(圖1):

圖1 特征向量生成示意圖

1.2.5 SIFT描述符在圖像匹配方面的表現(xiàn)

當(dāng)兩幅圖像的SIFT特征向量生成以后，采用關(guān)鍵點(diǎn)特征向量的歐氏距離作為兩幅圖中關(guān)鍵點(diǎn)相似性的判定度量。取其中一幅圖片的某個(gè)關(guān)鍵點(diǎn)，并找出另一幅圖片中歐式距離最近的的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近鄰的距離小于某一個(gè)預(yù)先設(shè)定的比例閾值，則接受這一匹配點(diǎn)。

2 SIFT描述符的應(yīng)用

SIFT描述符最早用于圖像匹配，在隨后的研究中，不斷有新的算法提出并應(yīng)用到不同領(lǐng)域。比如使用SIFT特征完成目標(biāo)識(shí)別，包括最近鄰搜索，對(duì)象位姿的霍夫聚類(lèi)，最小二乘位姿計(jì)算，最后完成驗(yàn)證，其它應(yīng)用還有3D重建，運(yùn)動(dòng)跟蹤、分割、機(jī)器定位、攝影機(jī)標(biāo)定等。未來(lái)的研究還包括建立光照不變的顏色描述符(目前是單色的灰度圖像)局部紋理的測(cè)量，這方面的研究已經(jīng)在人類(lèi)視覺(jué)中扮演了越來(lái)越重要的角色，可以整合到特征描述符中，可以多特征結(jié)合進(jìn)行對(duì)象識(shí)別;另一個(gè)方向是特定對(duì)象類(lèi)別的識(shí)別。

2.1 SIFT描述符應(yīng)用于圖像匹配中

當(dāng)兩幅圖像的SIFT特征向量生成以后，采用關(guān)鍵點(diǎn)特征向量的歐氏距離作為兩幅圖中關(guān)鍵點(diǎn)相似性的判定定量。取其中一幅圖片的某個(gè)關(guān)鍵點(diǎn)，并找到另一幅圖片中的歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近鄰的距離小于某一個(gè)預(yù)先設(shè)定的比例閾值，則接受這一匹配點(diǎn)。

結(jié)果(對(duì)lena圖像提取特征點(diǎn)圖2)如下:

結(jié)果如下:

以上看出提取出來(lái)的SIFT描述符在圖像匹配上有很好的應(yīng)用。因?yàn)樵搱D像是對(duì)原圖像進(jìn)行順時(shí)針90°然后在另一幅圖片上進(jìn)行了一個(gè)小貼圖，結(jié)果比較理想。證明了SIFT描述符的旋轉(zhuǎn)不變性。

2.2 SIFT描述符在場(chǎng)景分類(lèi)中的應(yīng)用

圖像目標(biāo)的分類(lèi)、識(shí)別是計(jì)算機(jī)視覺(jué)和模式識(shí)別領(lǐng)域的一個(gè)重要的研究問(wèn)題。由于圖像目標(biāo)存在視角變化、亮度變化、尺度、目標(biāo)變形、遮擋、復(fù)雜背景以及目標(biāo)類(lèi)內(nèi)差別等影響，使得圖片目標(biāo)的分類(lèi)非常困難。針對(duì)這些問(wèn)題，lowe提出的SIFT描述算子，這種具有尺度不變、旋轉(zhuǎn)不變的局部特征為了使用這些局部特征提出了許多基于特征包(Bags of Features)的方法對(duì)圖像進(jìn)行分類(lèi)，并取得了良好的性能，但是這些方法沒(méi)有利用局部特征在圖像空間的位置關(guān)系，只利用了局部特征在特征空間的關(guān)系，最近Lazebnik借鑒Grauman的金字塔匹配思想，在Discriminative Classification with Sets of Image Features中提出空間金字塔匹配核(Spacial Pyramid Matching Kernel)，首先對(duì)局部特征量化，并在二維圖像空間建立金字塔，然后計(jì)算兩幅圖像的子圖像區(qū)域局部特征直方圖交叉，該方法要求圖像中的目標(biāo)比較規(guī)范，且要求目標(biāo)在圖像中的位置比較一致，這也是其缺陷，時(shí)間效率不會(huì)很高。

2.3 結(jié)合金字塔匹配方法對(duì)圖片庫(kù)分類(lèi)

金字塔匹配是一種以特征為基礎(chǔ)的匹配，即指通過(guò)分別提取兩個(gè)或多個(gè)圖像的特征(點(diǎn)、線、面等特征)，對(duì)特征進(jìn)行參數(shù)描述，然后運(yùn)用所描述的參數(shù)來(lái)進(jìn)行匹配的一種算法?；谔卣鞯钠ヅ渌幚淼膱D像一般包含的特征有顏色特征、紋理特征、形狀特征、空間位置特征等。要進(jìn)行圖像匹配首先要進(jìn)行特征提取與描述，通常我們將此類(lèi)問(wèn)題看做是識(shí)別圖像的語(yǔ)義種類(lèi)。

建立金字塔首先要用一個(gè)規(guī)則的晶格在每一幅圖片上提取SIFT描述符，然后通過(guò)K-均值建立詞典，每一個(gè)SIFT描述符給定了一個(gè)紋理標(biāo)簽，該標(biāo)簽是與最近的詞典碼字相對(duì)應(yīng)的。最后，金字塔從這些標(biāo)簽中產(chǎn)生出來(lái)。所以該算法主要分以下步驟:

1)生成SIFT描述符(GenerateSiftDescriptors)

2)計(jì)算詞典(CalculateDictionary)

3)建立直方圖(BuildHistograms)

4)構(gòu)建金字塔(CompilePyramid)(該步較重要現(xiàn)將流程表達(dá)如下)

基本流程如下:

2.4 結(jié)合SIFT描述符的性別識(shí)別

性別識(shí)別(gender recognition)結(jié)合面部表情的密集SIFT描述符和形狀內(nèi)容，性別分類(lèi)很重要，因?yàn)樗梢蕴嵘渌恍?yīng)用，比如人體識(shí)別和人機(jī)交互。

應(yīng)用SIFT描述符對(duì)面部的的性別識(shí)別有四個(gè)問(wèn)題:

(1)由于丟失的紋理信息或者因?yàn)楣庹赵虻膱D片只能提取一部分的關(guān)鍵點(diǎn)。

(2)在關(guān)鍵點(diǎn)上的SIFT描述符是獨(dú)特的，但是在非關(guān)鍵點(diǎn)(如晶格)可能對(duì)準(zhǔn)確性有負(fù)面影響。

(3)對(duì)于相對(duì)較大尺寸的的圖片則需要獲取足夠的關(guān)鍵點(diǎn)來(lái)支持圖像匹配。

(4)匹配算法假設(shè)人臉是被合適的記錄下來(lái)。

處理以上問(wèn)題主要是通過(guò)將SIFT描述符和形狀特征，而不是僅僅提取興趣點(diǎn)周?chē)拿枋龇?，在?guī)則圖片晶格點(diǎn)上提取局部特征描述符，這就需要對(duì)面部圖片進(jìn)行密集特征提取。另外面部圖片的全局形狀融合在這些密集特征中來(lái)提高準(zhǔn)確性。

2.5 結(jié)合SIFT特征匹配的的陰影檢測(cè)

陰影檢測(cè)(shadow detection)對(duì)視覺(jué)監(jiān)督系統(tǒng)的健壯性和可靠性是至關(guān)重要的，當(dāng)目標(biāo)部分和真正的陰影部分比例相似的時(shí)候，基于灰度水平和顏色信息的陰影檢測(cè)就會(huì)失效，但是當(dāng)利用SIFT特征檢測(cè)時(shí)就可以解決這一問(wèn)題。在2010年國(guó)際信息工程大會(huì)上 ZhangLiang和 HeXiaomei的Fake Shodow Detection Based on SIFT Features Matching提出的利用RGB顏色模型候選陰影檢測(cè)出來(lái)之后，然后利用SIFT算法將局部特征描述出來(lái)(在兩個(gè)連續(xù)的框架內(nèi))對(duì)于移動(dòng)目標(biāo)和陰影的SIFT特征的位置信息就會(huì)得到，從而將陰影檢測(cè)出來(lái)。

2.6 結(jié)合SIFT描述符和自適應(yīng)顏色獨(dú)立成分分析對(duì)圖像的分類(lèi)

一般對(duì)圖像分類(lèi)或者匹配都是在灰度圖像上，對(duì)于在顏色圖像上進(jìn)行分類(lèi)就顯得比較難。所以如何能找到一種自適應(yīng)強(qiáng)且效果好的顏色空間來(lái)提取SIFT特征就成了一個(gè)重要的課題。在2010年國(guó)際模式識(shí)別大會(huì)上Danni Ai等在Adaptive Color Independent Components based SIFT Descriptors for Image Classification中提出的，此方法不僅可以加強(qiáng)目標(biāo)和背景之間的對(duì)比度，和傳統(tǒng)的目標(biāo)和場(chǎng)景分類(lèi)相比效果也是很好的。主要從以下兩方面進(jìn)行處理:

(1)基于獨(dú)立成分分析，一種自適應(yīng)能力好且效果好的顏色空間用來(lái)表示顏色圖像。

(2)在此基于顏色空間中的獨(dú)立成分分析中，一種有區(qū)別性的CIC-SIFT描述符計(jì)算了出來(lái)用于圖片分類(lèi)。

3 SIFT算法的改進(jìn)

3.1 提高旋轉(zhuǎn)不變性

不同圖像之間的匹配在一算計(jì)視覺(jué)中一直是一個(gè)很有挑戰(zhàn)性的課題。圖像匹配也是中國(guó)計(jì)算機(jī)視覺(jué)應(yīng)用中的幾個(gè)必須步驟，如三維重建，鑲嵌和目標(biāo)識(shí)別。圖像點(diǎn)需要通過(guò)特征向量提取出來(lái)，或者整幅圖片應(yīng)用密集匹配(算法效率不高，硬件要求較高)。提取的圖像點(diǎn)然后通過(guò)一個(gè)特征描述符的算法轉(zhuǎn)化成一個(gè)特征向量，這個(gè)向量最終來(lái)對(duì)比建立匹配。

由于不能保證每幅圖像都能很規(guī)則的表示，所以難免會(huì)有圖片有旋轉(zhuǎn)，那么在遇到這種情況下，SIFT描述符就顯示了其優(yōu)勢(shì)。圖像描述符在匹配圖像特征中已廣泛得到一種應(yīng)用結(jié)構(gòu)?；赟IFT方法的描述符是通過(guò)計(jì)算不同特征區(qū)域的梯度方向直方圖，一般都是通過(guò)一種規(guī)則的笛卡爾晶格或者log-polar晶格來(lái)劃分區(qū)域。為了得到旋轉(zhuǎn)不變性，特征點(diǎn)一般需要在主梯度方向上進(jìn)行旋轉(zhuǎn)。在Fabio Bellavia等的Improving SIFT-based descriptors stability to rotations中提到了一種改進(jìn)是基于某種晶格進(jìn)行的SIFT特征提取，這樣可能就會(huì)避免在計(jì)算描述符之前旋轉(zhuǎn)特征點(diǎn)，因?yàn)樘崆岸x的離散方向可以很容易的通過(guò)改變描述符向量來(lái)得到。

3.2 利用灰關(guān)聯(lián)提高計(jì)算率

在上面應(yīng)用中介紹了在性別識(shí)別中用到是密集SIFT描述符，通常這需要很大的計(jì)算量和較高配置的硬件，這樣要求怎樣能更好的準(zhǔn)確定位關(guān)鍵點(diǎn)可以加快計(jì)算的速度從而提高效率。因?yàn)榈龅奶卣鼽c(diǎn)提取容易不夠用，而稠密采樣又計(jì)算量大，可以使用灰關(guān)聯(lián)的方法較合理的獲得特征點(diǎn)，也兼顧平滑特點(diǎn)。灰色關(guān)聯(lián)分析的基本思想是根據(jù)序列曲線幾個(gè)形狀的相似程度來(lái)判斷其聯(lián)系是否緊密。曲線越接近，相應(yīng)序列之間關(guān)聯(lián)度越大，反之就越小。就是利用灰關(guān)聯(lián)的這種性質(zhì)，在進(jìn)行SIFT描述符提取的過(guò)程中可以利用該理論進(jìn)行關(guān)聯(lián)度判斷，從而判斷其關(guān)聯(lián)度的大小來(lái)決定是否是其達(dá)到要求的興趣點(diǎn)。這種方法就可以更好更快的解決效率問(wèn)題。

在以后的工作中，如何更快更好的算法找到特征點(diǎn)，是研究的重點(diǎn)。

4 結(jié)束語(yǔ)

本文主要研究了SIFT算法，介紹了SIFT算法的原理和將算法應(yīng)用到圖像匹配和圖片分類(lèi)和算法的改進(jìn)，并結(jié)合其他算法應(yīng)用到圖像分類(lèi)中的應(yīng)用，說(shuō)明SIFT描述符和算法確實(shí)具有很強(qiáng)的應(yīng)用價(jià)值，具有較強(qiáng)的健壯性，而且結(jié)合其他算法可以實(shí)現(xiàn)更多的重要功能，這些都需要有待進(jìn)一步的研究。

［1］David G Love.Distinctive Image Featurea from Scale-Invarient Keypoints.International Journal of Computer Vision，2004.

［2］Sv etlana Lazebnik，Cordelia Schmid，Jean Ponce.Beyond Bags of Features:Spatial Pyramid Matching for Recognizing Natural Scene Categories.IEEE，2006.

［3］Kristen Grauman，Trevor Darrell.The Pyramid Match Kernel:Discriminative Classification with Sets of Image Features.IEEE，2005.

［4］K Mikolajczyk and C Schmid.A performance evaluation of local descriptors.IEEE Transaction on PAMI 2005

［5］Jian-Gang，Jun Li，Wei-Yun Yau.Boosting Dense SIFT Descriptors and Shape Contents of Face Images for Gender Recognition.IEEE，2010.

［6］Liang Zhang，Xiaomei He.Fake Shadow Detection Based on SIFT Features Matching.IEEE，2010.

［7］Danni Ai，Xianhua Han，Xiang Ruan，Yen-Wei Chen.Adaptive Color Independent Components based SIFT Descriptors for Image Classification.IEEE，2010.

［8］楊淑瑩.模式識(shí)別與智能計(jì)算——Matlab技術(shù)實(shí)現(xiàn)［M］.電子工業(yè)出版社，2009.

［9］于成波.數(shù)字圖像處理及MATLAB實(shí)現(xiàn).重慶大學(xué)出版社，2003.

［10］劉思峰，謝乃明等.灰色系統(tǒng)理論及其應(yīng)用［M］.科學(xué)出版社，2008.

SIFT Algorithm Research and Application

HUANG Chao，Qi Ying-jian
(School of Science Communication University of China Beijing 100024)

Image matching is a fundamental aspect of many problems in Compter Vision，including object and scene recognition，solving 3D structure in more images，3D correlation and motion tracking.The paper is mainly about SIFT alorithm and the its application in scenes classification and some of its improvement.The experiments results shows that it has significant advantages in scene recognition and classification，it also can be improved and adopted in other computer vision.

feature descriptor;scale space;BOF，ICA-SIFT;shadow detection

TP391

A

1673-4793(2012)01-0068-05

2011-1-5

黃超(1987-)，男，山東臨沂市人，中國(guó)傳媒大學(xué)研究生。

(責(zé)任編輯

:龍學(xué)鋒)