基于中層特征的精細(xì)圖像分類-論文

1、基于中層特征的精細(xì)圖像分類摘 要現(xiàn)如今，圖像處理中目標(biāo)分類與檢測(cè)越來(lái)越多的得到了人們的關(guān)注與研究。目標(biāo)分類一般分為兩種，一種是基礎(chǔ)圖像分類，另一種是越來(lái)越受到人們關(guān)注的精細(xì)圖像分類。基礎(chǔ)圖像分類是為了區(qū)分具有不同形狀以及視覺(jué)特征的物體（例如給出一個(gè)鳥(niǎo)的圖片，基礎(chǔ)圖像分類就是為了要區(qū)分出這張圖片是鳥(niǎo)的圖片還是狗的圖片）。精細(xì)圖像分類則是要區(qū)分具有相似形狀以及外貌特征的物體（例如給出一副鳥(niǎo)的圖片，精細(xì)分類就是要判斷出這只鳥(niǎo)究竟屬于哪一類鳥(niǎo)）。在這篇文章中，我們主要研究了圖像的精細(xì)分類問(wèn)題，在現(xiàn)實(shí)生活中它比圖像的基礎(chǔ)分類更加具有實(shí)用性。我們所使用的數(shù)據(jù)庫(kù)是目前比較有挑戰(zhàn)性的CUB-200以及Stan

2、ford_Dogs數(shù)據(jù)庫(kù)。我們結(jié)合了高效匹配核函數(shù)（EMK）與帶有權(quán)重的空間金字塔以達(dá)到最優(yōu)的分類表現(xiàn)。實(shí)驗(yàn)用EMK與詞包（BoW）作對(duì)比，其中，BoW也可以看做是一種核函數(shù)匹配方法，EMK是找出詞表主要成分的相互關(guān)系，并且在核函數(shù)的框架中找到一種新的映射。EMK是通過(guò)映射，將局部特征映射到一個(gè)低維的特征空間并且將結(jié)果向量平均化以形成一個(gè)特征層集合。實(shí)驗(yàn)結(jié)果表明，這可以很好的改進(jìn)系統(tǒng)的性能。關(guān)鍵詞：高效匹配核函數(shù)（EMK）；詞包（BoW）；細(xì)粒度圖像分類ABSTRACTIn recent days, object classification and detection in image pr

3、ocessing are getting more and more attention and research. Object classification include two sides, one is basic classification, another is fine-grained classification which attract more and more people to study. basic classification is to classify the object which have the different shapes and visu

4、al appearance(e.g.: for a picture of bird,the basic classification is to identify the object in the picture is a bird or dog ). Fine-grained classification is to classification the object with the similar shapes and visual appearance(e.g.: for a picture of bird,the fine-grained classification is to

5、identify which kind of birds it belongs to). In this paper, we study the problem of fine-grained image categorization, which is much more useful in real applications than basic image classification. Based on the most challenge dataset, CUB-200, Stanford_Dogs_Dataset.We combine Efficient match kernel

6、 (EMK) with the weighted spatial pyramid to achieve state-of-art performance. Comparison with BoW, which can also be viewed as kernel matching approach, EMK digs the relations among vocabulary bases and finds a new mapping in kernel framework. By it, local features are mapped to a low dimensional fe

7、ature space and average the resulting vectors to form a set level feature in EMK. It is proved that it is helpful to improve the system performance.第1章 緒論1.1精細(xì)圖像分類的研究背景及意義伴隨著網(wǎng)絡(luò)和多媒體技術(shù)的飛速發(fā)展，越來(lái)越多的聲音、圖形、圖像、視頻和動(dòng)畫(huà)等數(shù)字信息越來(lái)越多的出現(xiàn)在人們的工作、學(xué)習(xí)和生活當(dāng)中。而圖像作為一種內(nèi)容豐富、表現(xiàn)生動(dòng)的媒體信息，也越來(lái)越受到了人們的關(guān)注。在現(xiàn)實(shí)生活中，時(shí)時(shí)刻刻都會(huì)有大量的圖像產(chǎn)生，對(duì)于如何從這些給定

8、的圖像信息中找出符合人們所需求的圖像就是研究者們需要解決的問(wèn)題。圖像分類其實(shí)就是模式識(shí)別的過(guò)程，它是利用計(jì)算機(jī)來(lái)對(duì)圖像進(jìn)行定量分析，把圖像中的每個(gè)像素元或區(qū)域轉(zhuǎn)化成一種計(jì)算機(jī)識(shí)別的特征類別，用來(lái)代替人的視覺(jué)判讀?，F(xiàn)如今百度、google等網(wǎng)絡(luò)公司使用的都是傳統(tǒng)的圖像分類方法，為了能夠?qū)崿F(xiàn)圖像更精確的分類也都有做圖像精細(xì)分類方面的研究，如果可以實(shí)現(xiàn)圖像的精細(xì)分類，那么在網(wǎng)絡(luò)搜索中，我們可以快速的實(shí)現(xiàn)圖像的匹配，以此來(lái)實(shí)現(xiàn)精確圖像的搜索。而不會(huì)像在傳統(tǒng)的圖像分類中那樣，在圖像匹配方面只能實(shí)現(xiàn)粗略的匹配而使得圖像搜索結(jié)果多而不精。隨著智能機(jī)器的不斷發(fā)展進(jìn)步，人們對(duì)于圖像分類的要求越來(lái)越高，它要求我們

9、對(duì)于圖像能夠?qū)崿F(xiàn)越來(lái)越精細(xì)的分類。而傳統(tǒng)的圖像分類只能進(jìn)行粗略的圖像分類，它一般都是利用圖像的紋理、灰度、形狀位置等底層特征對(duì)圖像進(jìn)行分類，而在圖像的搜索查找方面一般都是選用關(guān)鍵詞來(lái)進(jìn)行查找。而在本文中，我們所要實(shí)現(xiàn)的是圖像分類能夠根據(jù)圖像的底層特征以及利用中層特征思想的方法來(lái)實(shí)現(xiàn)圖像的精細(xì)分類，并且可以根據(jù)未知圖片來(lái)搜索相關(guān)信息。1.2國(guó)內(nèi)外研究現(xiàn)狀基于精細(xì)圖像分類的研究是從11年以后才開(kāi)始有相關(guān)研究的，且只有斯坦福大學(xué)、加利福尼亞大學(xué)等少數(shù)的學(xué)校在做。其中以斯坦福大學(xué)Li Fei-Fei等人在2011年、2012年在CVPR上發(fā)表的Combining Randomization and D

10、iscrimination for Fine-Grained Image Categorization以及A Codebook-Free and Annotation-Free Approach for Fine-Grained Image Categorization最為突出。下面我們介紹幾種圖像分類的方法。1、基于編碼簿（code book）的編碼方法現(xiàn)如今大多數(shù)的最優(yōu)的圖像分類系統(tǒng)是基于局部圖像塊編碼的視覺(jué)代碼，但是這種視覺(jué)代碼是經(jīng)常導(dǎo)致圖像塊詳細(xì)信息丟失的粗糙編碼?，F(xiàn)如今，一些最新的研究開(kāi)始使用稀疏編碼SC（Sparce Code）來(lái)獲得更準(zhǔn)確的圖像塊編碼，并且這種方法已被證明在許多的

11、圖像分類的任務(wù)中使得分類性能得到了改進(jìn)。但是在這種方法中，圖像信息的丟失也是沒(méi)有辦法避免的。2、基于注釋的方法圖像分類中，為了在細(xì)粒度分類問(wèn)題中說(shuō)明重要目標(biāo)的特性以及與其它的相似目標(biāo)的細(xì)微區(qū)別，越來(lái)越多的工作都試圖從人類方面來(lái)吸收更多的輸入信息，包括要求人們點(diǎn)擊目標(biāo)區(qū)域、回答關(guān)于目標(biāo)特性問(wèn)題的人類循環(huán)方法。它是一個(gè)關(guān)于鳥(niǎo)類識(shí)別的改進(jìn)的postlet-like算法，并且在Caltech-UCSD鳥(niǎo)類數(shù)據(jù)庫(kù)中獲得了良好的性能。但是這種方法需要人們對(duì)于目標(biāo)特性或者關(guān)鍵點(diǎn)位置的冗長(zhǎng)的注釋，這對(duì)那些需要全自動(dòng)學(xué)習(xí)來(lái)進(jìn)行區(qū)分圖像信息的情況構(gòu)成了嚴(yán)峻的考驗(yàn)。而且將這種方法使用到新的細(xì)粒度目標(biāo)層中所需要付出的

12、代價(jià)是很昂貴的，因?yàn)樘卣鞑樵兒湍繕?biāo)關(guān)鍵點(diǎn)通常需要由領(lǐng)域的專家仔細(xì)設(shè)計(jì)，尤其是那些沒(méi)有明顯關(guān)鍵區(qū)域或者直接特性的目標(biāo)，例如樹(shù)、水、食物等等。3、基于模板的方法基于模板的算法是一個(gè)需要獲得帶有大量隨機(jī)生成的映像模板來(lái)匹配圖像特征響應(yīng)的映射。這種方法在思想上類似于最近大量使用的各種預(yù)定義濾波器來(lái)生成圖像響應(yīng)特征的研究，例如目標(biāo)檢測(cè)，人體部分探測(cè)器以及圖像區(qū)域的聚類中心。雖然這些方法在基礎(chǔ)層目標(biāo)和場(chǎng)景分類任務(wù)中已經(jīng)展現(xiàn)了很好的結(jié)果，但是它們?nèi)匀幻媾R著粗糙編碼或者冗長(zhǎng)的人類注釋的問(wèn)題，而且這些代表方法目前還沒(méi)有一個(gè)用在細(xì)粒度圖像分類上。4、細(xì)粒度圖像分類方法細(xì)粒度圖像分類方法是用各種數(shù)據(jù)庫(kù)來(lái)進(jìn)行細(xì)粒度圖

13、像分類，它是最近研究比較多的。這種方法可以識(shí)別數(shù)據(jù)中的具有相似外表的圖像。這也是我們這次設(shè)計(jì)的主要思想，具體詳見(jiàn)下文。5、其它圖像分類方法這些超出了我們這篇文章的討論大型目標(biāo)分類工作的范疇，例如一些基于局部模型工作在最小范圍的分類目標(biāo)或從背景中局部化目標(biāo)可以完成的很好。然而，在怎樣使用這些方法來(lái)區(qū)分那些有相似視覺(jué)外表的細(xì)粒度目標(biāo)并且展示這些目標(biāo)的的重要部分還不清楚。1.3文章框架精細(xì)圖像分類是解決限制人類視覺(jué)效能以達(dá)到區(qū)分相似目標(biāo)的有效方法。例如當(dāng)人看到一種自己并不認(rèn)識(shí)的花或鳥(niǎo)時(shí)，很想知道這種花或鳥(niǎo)的具體名稱以及其相關(guān)信息，但是人的視覺(jué)以及學(xué)識(shí)可能會(huì)不能幫助人們區(qū)分這種花或鳥(niǎo)，這時(shí)，細(xì)粒度圖像

14、分類就會(huì)幫助人們來(lái)解決這個(gè)問(wèn)題。而在文章中，我們主要想做的也是細(xì)粒度圖像分類，這種方法亦可以廣泛擴(kuò)展到其它領(lǐng)域中，并且其分類范圍也可以廣泛運(yùn)用到任何的數(shù)據(jù)庫(kù)中。在文章中，為了實(shí)現(xiàn)圖像的細(xì)粒度圖像分類，整個(gè)實(shí)驗(yàn)步驟如圖1-1：BoWSVM空間金字塔特征提取使用包圍盒截取圖片圖片RFEMK圖1-1 細(xì)粒度圖像分類實(shí)驗(yàn)過(guò)程文章我們采用了以下框架：1、特征提取在文章的第二章中我們介紹了整個(gè)程序中的特征提取，而在特征提取的過(guò)程中，我們采用了兩種特征描述子來(lái)提取圖片的特征信息以作后續(xù)分類結(jié)果的對(duì)比。而這兩個(gè)特征我們采取了尺度不變特征轉(zhuǎn)換（SIFT）特征以及方向梯度直方圖（HOG）特征。對(duì)全文的精細(xì)圖像分類

15、起到基礎(chǔ)作用。2、使用中層特征在文章的第三章中，我們介紹了將第二章中所提取的特征進(jìn)一步處理以達(dá)到我們的精細(xì)圖像分類要求。在這一章中，我們介紹了我們?cè)趯?shí)驗(yàn)過(guò)程中所用到過(guò)的詞包（BoW，Bag of Word），高效匹配核函數(shù)（EMK，Efficient Match Kernel）以及空間金字塔（SP，Spatial Pyramid）。對(duì)比了相互之間的關(guān)系以及差別，對(duì)全文的精細(xì)圖像分類起到很重要的作用。3、分類器介紹在文章的第四章中，我們介紹了本實(shí)驗(yàn)的最后一步匹配環(huán)節(jié)，在這一環(huán)節(jié)中，我們使用了支持向量機(jī)（SVM，Support Vector Machine）以及隨機(jī)森林（RF，Random For

16、est）這兩種方法。在第四章中，我們重點(diǎn)介紹了每種分類器的特點(diǎn)、結(jié)構(gòu)以及優(yōu)缺點(diǎn)。4、實(shí)驗(yàn)環(huán)節(jié)在文章的第五章中，我們介紹了整個(gè)文章的實(shí)驗(yàn)環(huán)節(jié)。首先介紹了我們實(shí)驗(yàn)中所使用的數(shù)據(jù)庫(kù)，之后介紹了實(shí)驗(yàn)結(jié)果以及實(shí)驗(yàn)結(jié)果分析。第2章 底層特征文章中對(duì)于底層特征的描述，我們采用了局部描述子SIFT特征以及HOG特征，對(duì)于這兩種基本特征的詳細(xì)描述如下。2.1 SIFT算法介紹尺度不變特征轉(zhuǎn)換(Scale-invariant feature transform或SIFT)是David Lowe在1999年提出的一種局部特征描述子算法，并且在2004年進(jìn)行了更深入的發(fā)展和完善。SIFT算法是一種

17、電腦視覺(jué)的算法，它可以用來(lái)檢測(cè)與描述圖像中的局部性特征。該算法通過(guò)求一幅圖片中的特征點(diǎn)（interest points,or corner points），包括這些特征點(diǎn)的尺度（scale）以及方向（orientation）的描述子來(lái)得到特征描述子，并進(jìn)行圖像特征點(diǎn)匹配，這種方法獲得了良好效果。SIFT特征不僅僅具有尺度不變性，即使改變其圖像亮度、旋轉(zhuǎn)角度或拍攝視角，仍然能夠得到好的檢測(cè)效果。而且對(duì)視角變化、噪聲也能夠保持一定的穩(wěn)定性。整個(gè)SIFT算法分為以下幾個(gè)部分：1、 尺度空間的極值檢測(cè)：第一階段的計(jì)算搜索了所有的尺度和圖片位置信息。通過(guò)使用差分高斯（difference-of-Gaus

18、sian或DoG）函數(shù)來(lái)有效的區(qū)分具有潛在的尺度以及方向不變的興趣點(diǎn)；2、 關(guān)鍵點(diǎn)定位：在每一個(gè)可能的位置，找出具有決定性的位置和尺度所匹配的詳細(xì)模型，然后基于它們的穩(wěn)定性來(lái)選擇關(guān)鍵點(diǎn)；3、 分配方向：基于局部圖像的梯度方向，每一個(gè)關(guān)鍵點(diǎn)位置都被分配了一個(gè)活多個(gè)方向。對(duì)于圖像數(shù)據(jù)都會(huì)轉(zhuǎn)換成相應(yīng)的特征點(diǎn)，而每個(gè)特征點(diǎn)都會(huì)分配尺度、方向以及位置信息，這些是以后我們圖像分類操作的基礎(chǔ)，因此，我們應(yīng)提供這些轉(zhuǎn)換過(guò)程一個(gè)不變性；4、 關(guān)鍵點(diǎn)描述子：局部圖像的梯度是由我們所選擇的在每個(gè)關(guān)鍵點(diǎn)周圍區(qū)域的尺度得出來(lái)的，這些使得在光照改變以及發(fā)生局部形變時(shí)這些特征點(diǎn)仍具有代表性。2.1.1SIFT算法的具體步驟

19、： 1、 構(gòu)建尺度空間首先，要構(gòu)建一個(gè)尺度空間，這是一個(gè)初始化的操作，該尺度空間理論的目的在于模擬圖像數(shù)據(jù)的多尺度特征。Koenderink (1984) and Lindeberg (1994)已經(jīng)證明，在各種合理的假設(shè)下，高斯函數(shù)是唯一可能的尺度空間函數(shù)。由于高斯卷積核是實(shí)現(xiàn)尺度變換的唯一線性核，因此，我們可以將一副圖像的尺度空間定義為： (2-1)其中，*代表卷積運(yùn)算，是尺度可變高斯函數(shù)， 在公式（2-1）中（x，y）是空間坐標(biāo)，同時(shí)也是尺度坐標(biāo)。值的大小決定圖像的平滑程度，大尺度對(duì)應(yīng)圖像的概貌特征，小尺度則對(duì)應(yīng)圖像的細(xì)節(jié)特征。大的值對(duì)應(yīng)粗糙尺度（低分辨率），反之，則對(duì)應(yīng)精細(xì)尺度（高分辨

20、率）。不同所對(duì)應(yīng)的尺度空間如下圖：圖2-1 不同所對(duì)應(yīng)的尺度空間為了能夠有效的在尺度空間檢測(cè)穩(wěn)定的關(guān)鍵點(diǎn)坐標(biāo)，Lowe于1999年提出了使用高斯差分尺度空間（DOG scale-space）來(lái)計(jì)算尺度空間的極值。它是利用不同尺度的高斯差分核函數(shù)來(lái)卷積圖像I生成?？梢杂蓛蓚€(gè)被一常量因子所分開(kāi)的相鄰尺度間的差別來(lái)計(jì)算。即(2-2)對(duì)于選擇這個(gè)函數(shù)的方法有很多種。首先，這個(gè)函數(shù)要是一個(gè)能計(jì)算出來(lái)的有效函數(shù)，例如給出一副平滑圖像，我們需要在任意尺度空間特征描述子情況下都能計(jì)算出L,而D能由簡(jiǎn)單的圖像差分來(lái)計(jì)算。除此之外，由Lindeberg (1994).的研究我們可以得到，高斯差分函數(shù)可以近似的看做

21、一種高斯函數(shù)的拉普拉斯標(biāo)準(zhǔn)尺度變換，。Lindeberg研究表明，帶有因子的拉普拉斯變換的標(biāo)準(zhǔn)化需要尺度不變性。在詳細(xì)的實(shí)驗(yàn)對(duì)比中，Mikolajczyk (2002)發(fā)現(xiàn)，的最大值和最小值相比于其它的如梯度或者Harris角函數(shù)這些可能的圖片函數(shù)所得到的圖片特征更加穩(wěn)定。和之間的關(guān)系就參數(shù)而言可以從熱擴(kuò)散方程方面理解。即（2-3）從公式（2-3）可以看到，可以由有限差分逼近來(lái)計(jì)算，這就利用了在以及這兩個(gè)相鄰出度空間的的不同處，即（2-4）因此有：（2-5）公式2-5表明，當(dāng)差分高斯函數(shù)具有尺度而不同于一個(gè)常量時(shí)，它就已經(jīng)包含了標(biāo)準(zhǔn)化所需的拉普拉斯尺度不變性。方程中的在所有的尺度中都是一個(gè)常數(shù)

22、，因此不會(huì)影響到極值的定位。近似誤差也會(huì)由0到1，但是在實(shí)際實(shí)驗(yàn)中，近似誤差對(duì)極值檢測(cè)的穩(wěn)定性或在尺度中顯著差異的定位幾乎沒(méi)有影響。在SIFT算法過(guò)程中，一般要建立圖像金字塔：如何建立圖像金字塔如下：對(duì)于一幅圖像I，需要建立其在不同尺度（scale）的圖像，也稱為塔或子八度（octave），這是為了圖像能夠具有尺度不變性（scale-invariant），也就是在任何尺度都能有對(duì)應(yīng)的特征點(diǎn)，第一層子八度的尺度為原圖大小，后面的每一層子八度都為其上一層子八度降采樣的結(jié)果，即為原圖的1/4（長(zhǎng)寬分別減半），構(gòu)成了下一個(gè)子八度（高一層的金字塔）。例如1塔的第0層可以由0塔的第3層down sampl

23、e得到，然后進(jìn)行與0塔類似的高斯卷積操作。如何建立一個(gè)有效的可以由圖2-2得到：圖2-2：圖像的左側(cè)表示對(duì)于每一個(gè)尺度空間的子八度，初始化后的圖片就會(huì)由高斯函數(shù)不停的卷積以生成圖像尺度空間的集合。圖的右側(cè)表示，相鄰的高斯圖像依次相減以生成差分高斯圖像。在每一個(gè)八度后，高斯圖像進(jìn)行降采樣。之后過(guò)程重復(fù)。首先，最初的圖像逐漸由高斯函數(shù)進(jìn)行卷積，生成被常數(shù)在尺度空間內(nèi)分割的圖像，即圖2-2的左邊部分。我們選擇將尺度空間中的每一個(gè)子八度分成s層，所以就有，而對(duì)于每一個(gè)子八度中的大量模糊圖片，我們必須生成幅圖片，這樣最后的極值檢測(cè)才能覆蓋整個(gè)的子八度。相鄰的圖像尺度相減后得到圖2-2中右面的差分高斯圖像

24、。在完成該尺度空間的處理后，我們就會(huì)以重新采樣高斯圖像。關(guān)于的采樣準(zhǔn)確率和之前子八度的采樣準(zhǔn)確率是沒(méi)有差別的。但是計(jì)算卻簡(jiǎn)單了很多。一般來(lái)說(shuō)，我們由圖片的大小來(lái)決定建幾個(gè)子八度，每層子八度幾層圖像(S一般為3-5層)。0層子八度的第0層是原始圖像(或是我們?nèi)‰p精度（double）后的圖像)，往上每一層是對(duì)其下一層進(jìn)行差分高斯卷積變換（其中值是越來(lái)越大的，例如可以是, , 等等），從直觀上看，越往上圖片就越模糊。2、 局部極值點(diǎn)檢測(cè)為了檢測(cè)局部的極大值與極小值，每一個(gè)樣本點(diǎn)都要和它周圍所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)的大或者小。即每個(gè)樣本點(diǎn)都要和它周圍同尺度的八個(gè)點(diǎn)以及上下

25、相鄰兩層的個(gè)點(diǎn)，共26個(gè)點(diǎn)進(jìn)行比較，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。 一個(gè)點(diǎn)如果在DOG尺度空間本層以及上下兩層的26個(gè)領(lǐng)域中是最大或最小值時(shí)，就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)特征點(diǎn),如圖所示。圖2-3：差分高斯圖像的極大值與極小值的檢測(cè)，是通過(guò)比較一個(gè)像素點(diǎn)在的區(qū)域內(nèi)與其相鄰的26個(gè)相鄰像素點(diǎn)的比較得來(lái)的在極值比較的過(guò)程中，同一組中的相鄰尺度（由于k的取值關(guān)系）肯定是上下層之間進(jìn)行尋找，每一組圖像的首末兩層是無(wú)法進(jìn)行極值比較的，為了滿足尺度變化的連續(xù)性，我們?cè)诿恳唤M圖像的頂層繼續(xù)用高斯模糊生成了3幅圖像，高斯金字塔有每組S+3層圖像。DOG金字塔每組有S+2層圖像。3、 關(guān)鍵點(diǎn)

26、定位一個(gè)可能的關(guān)鍵點(diǎn)已經(jīng)經(jīng)由對(duì)比像素周圍的值得到，第二步就是要形成一個(gè)詳細(xì)的適合位置、尺度和主曲率的數(shù)據(jù)。這就允許我們放棄一些具有低對(duì)比度（對(duì)噪聲比較敏感）的點(diǎn)，或者在圖像邊緣的邊緣響應(yīng)點(diǎn)。這種方法的初步實(shí)現(xiàn)僅僅是定位在某一位置、尺度的中央采樣點(diǎn)處確定關(guān)鍵點(diǎn)。然而，最近Brown提出了一個(gè)新的方法來(lái)確定關(guān)鍵點(diǎn)。它通過(guò)擬和三維的二次函數(shù)到局部采樣點(diǎn)，以檢測(cè)最大值的曲線位置。實(shí)驗(yàn)證明，這個(gè)方法對(duì)圖像的匹配和穩(wěn)定性具有實(shí)質(zhì)性的改進(jìn)。（1）去除低對(duì)比度的點(diǎn)這個(gè)方法使用了尺度空間函數(shù)泰勒展開(kāi)式（展開(kāi)到二次項(xiàng)），所以在采樣點(diǎn)處，公式（2-2）可以轉(zhuǎn)換成：（2-6）其中D和它的一維及二維導(dǎo)數(shù)在采樣點(diǎn)處均可求

27、，是采樣點(diǎn)處的補(bǔ)償。將公式（2-6）對(duì)x求導(dǎo)，并令導(dǎo)數(shù)為0，得到的即可得到精確位置，即：（2-7）正如Brown 提出的那樣，Hessian 和D的導(dǎo)數(shù)在通過(guò)使用不同的相鄰的采樣點(diǎn)是近似的。的線性系統(tǒng)可以以最小的消耗來(lái)得到解決。如果在任一維度的值大于0.5，這就說(shuō)明極值點(diǎn)考進(jìn)來(lái)一個(gè)不同的采樣點(diǎn)，這種情況下，采樣點(diǎn)就會(huì)由插入的采樣點(diǎn)代替。最后的代入采樣點(diǎn)的位置以獲得插值的極值點(diǎn)。將公式（2-7）代入公式（2-6）中即可得到極值，它可以有效的去除低對(duì)比度的關(guān)鍵點(diǎn)和不穩(wěn)定的點(diǎn)。為：（2-8）若，該特征點(diǎn)就保留下來(lái)，否則就舍去。（2） 去除邊緣響應(yīng)點(diǎn)為了特征點(diǎn)的穩(wěn)定，光去除低對(duì)比度的點(diǎn)是不夠的，邊緣點(diǎn)

28、對(duì)于高斯差分函數(shù)有強(qiáng)烈的影響。因?yàn)檫吘夗憫?yīng)點(diǎn)是不容易確定的，因此，即使一點(diǎn)點(diǎn)的噪聲也會(huì)對(duì)邊緣點(diǎn)殘生很大的干擾。一個(gè)定義不好的高斯差分函數(shù)的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率可以通過(guò)一個(gè)的Hessian矩陣H求出:（2-9）D的主曲率和H的特征值成正比，借用Harris and Stephens (1988)的方法，我們可以避免明確的結(jié)算特征值，因?yàn)槲覀冎恍枰紤]它們的比例問(wèn)題。令為較大特征值，為較小的特征值，我們可以從H以及行列式中計(jì)算出特征值的和： （2-10）（2-11）令r為最大特征值與最小特征值之間的比率，即令，有；（2-12）由此可見(jiàn)，這個(gè)公

29、式僅取決于特征最大值與最小值的比例r，的值在兩個(gè)特征值相等的時(shí)候最小，隨著r的增大而增大，因此，為了檢測(cè)主曲率是否在某域值r下，只需檢測(cè)（2-13）如果則舍掉，對(duì)于本文章來(lái)說(shuō)，我們通常按Lowe文章中的經(jīng)驗(yàn)值取。4、 方向分配上一步中我們確定了每幅圖中的特征點(diǎn)，接下來(lái)要為每個(gè)特征點(diǎn)計(jì)算一個(gè)方向，對(duì)于每一個(gè)基于局部圖像特性的關(guān)鍵點(diǎn)分配一個(gè)一直的方向，則關(guān)鍵點(diǎn)描述子就會(huì)由它的方向表示，這個(gè)方法和Schmid andMohr (1997)的方向不變描述子具有相似性。在這里，每一幅圖片的特性都是由旋轉(zhuǎn)不變性測(cè)量來(lái)的。關(guān)鍵點(diǎn)的尺度用來(lái)尋找高斯平滑圖像L，依照這個(gè)方向做進(jìn)一步的計(jì)算，對(duì)每一幅圖像在某一尺度

30、進(jìn)行采樣得，梯度幅值為和方向。利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個(gè)關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。（2-14）公式（2-14）為(x,y)處梯度的模值和方向公式。其中L所用的尺度為每個(gè)關(guān)鍵點(diǎn)各自所在的尺度。至此，圖像的關(guān)鍵點(diǎn)已經(jīng)檢測(cè)完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置，所處尺度、方向，由此可以確定一個(gè)SIFT特征區(qū)域。由關(guān)鍵點(diǎn)區(qū)域內(nèi)的梯度方向的采樣點(diǎn)可以形成梯度直方圖。梯度直方圖的范圍是0360度，其中每10度一個(gè)柱，總共36個(gè)柱。隨著距離中心點(diǎn)越遠(yuǎn)的領(lǐng)域其對(duì)直方圖的貢獻(xiàn)也響應(yīng)減小.在實(shí)際計(jì)算時(shí)，我們?cè)谝躁P(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計(jì)鄰域像素的梯度方向。梯度直方圖的范

31、圍是0360度，其中每45度一個(gè)柱，總共8個(gè)柱, 或者每10度一個(gè)柱，總共36個(gè)柱。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。圖2-4直方圖中的峰值就是主方向，其它的達(dá)到最大值80%的方向可作為輔助方向圖2-5由梯度方向直方圖確定主梯度方向圖2-6通過(guò)對(duì)關(guān)鍵點(diǎn)周圍圖像區(qū)域分塊，計(jì)算塊內(nèi)梯度直方圖，生成具有獨(dú)特性的向量，這個(gè)向量是該區(qū)域圖像信息的一種抽象，具有唯一性。5、 局部圖像描述子首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性。以關(guān)鍵點(diǎn)為中心取8×8的窗口。圖2-7：16*16的圖中其中1/4的特征點(diǎn)梯度方向及scale，右圖為其加權(quán)到8個(gè)主方向后的

32、效果。圖中的左部分的中央為當(dāng)前關(guān)鍵點(diǎn)的位置，每個(gè)小格代表關(guān)鍵點(diǎn)鄰域所在尺度空間的一個(gè)像素，利用公式求得每個(gè)像素的梯度幅值與梯度方向，箭頭方向代表該像素的梯度方向，箭頭長(zhǎng)度代表梯度模值，然后用高斯窗口對(duì)其進(jìn)行加權(quán)運(yùn)算。圖中藍(lán)色的圈代表高斯加權(quán)的范圍（越靠近關(guān)鍵點(diǎn)的像素梯度方向信息貢獻(xiàn)越大）。然后在每4×4的小塊上計(jì)算8個(gè)方向的梯度方向直方圖，繪制每個(gè)梯度方向的累加值，即可形成一個(gè)種子點(diǎn)，如圖右部分示。此圖中一個(gè)關(guān)鍵點(diǎn)由2×2共4個(gè)種子點(diǎn)組成，每個(gè)種子點(diǎn)有8個(gè)方向向量信息。這種鄰域方向性信息聯(lián)合的思想增強(qiáng)了算法抗噪聲的效能，同時(shí)對(duì)于含有定位誤差的特征匹配也提供了較好的容錯(cuò)性。計(jì)

33、算關(guān)鍵點(diǎn)周圍的16*16的窗口中每一個(gè)像素的梯度，而且使用高斯下降函數(shù)降低遠(yuǎn)離中心的權(quán)重。圖2-8：在每個(gè)4*4的1/16象限中，通過(guò)加權(quán)梯度值加到直方圖8個(gè)方向區(qū)間中的一個(gè)，計(jì)算出一個(gè)梯度方向直方圖。這樣每個(gè)特征就可以形成一個(gè)維的描述子，每一維都可以表示個(gè)格子中一個(gè)的尺度或方向。將這個(gè)向量歸一化之后，就進(jìn)一步去除了光照的影響。最后經(jīng)過(guò)SIFT運(yùn)算后得到的圖像特征點(diǎn)如圖所示： 圖2-9 狗和鳥(niǎo)類的特征點(diǎn)提取2.1.2 SIFT算法的特點(diǎn)：SIFT特征作為局部特征，它是基于物體上的一些局部外觀的興趣點(diǎn)形成的，與影像的大小和旋轉(zhuǎn)無(wú)關(guān)。對(duì)于光線、噪聲、些微視角改變的容忍度也相當(dāng)高。它的信息量大，適合

34、在大亮點(diǎn)數(shù)據(jù)庫(kù)中做快速準(zhǔn)確匹配。SIFT算法的優(yōu)缺點(diǎn)：1. SIFT特征是圖像的局部特征，其對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性；2. 獨(dú)特性（Distinctiveness）好，信息量豐富，適用于在海量特征數(shù)據(jù)庫(kù)中進(jìn)行快速、準(zhǔn)確的匹配；3. 多量性，即使少數(shù)的幾個(gè)物體也可以產(chǎn)生大量的SIFT特征向量；4. 高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達(dá)到實(shí)時(shí)的要求；5. 可擴(kuò)展性，可以很方便的與其它形式的特征向量進(jìn)行聯(lián)合；6、缺點(diǎn)是SIFT特征為128維，維數(shù)高、且是不完全的仿射不變。2.2 HO

35、G特征 方向梯度直方圖（Histogram of Oriented Gradient, HOG）特征是一種在計(jì)算機(jī)視覺(jué)和圖像處理中用來(lái)進(jìn)行物體檢測(cè)的特征描述子。它通過(guò)計(jì)算和統(tǒng)計(jì)圖像局部區(qū)域的梯度方向直方圖來(lái)構(gòu)成特征。 HOG特征是一種局部區(qū)域描述符,它通過(guò)計(jì)算局部區(qū)域上的梯度方向直方圖來(lái)構(gòu)成人體特征,能夠很好地描述人體的邊緣。而且它對(duì)光照變化和小量的偏移不敏感。2.2.1 36維HOG特征提取算法的實(shí)現(xiàn)HOG特征提取步驟如下：（1）顏色空間灰度化 在HOG算法中由于顏色信息的作用不大，所以我們通常將所要檢測(cè)的圖像先轉(zhuǎn)化為灰度圖像（即將要檢測(cè)的圖像看作一個(gè)灰度的三維圖像）在進(jìn)行HOG特

36、征提取。（2）標(biāo)準(zhǔn)化gamma空間為了減少光照因素的影響，首先需要將整個(gè)圖像進(jìn)行規(guī)范化（歸一化）。在圖像的紋理強(qiáng)度中，局部的表層曝光貢獻(xiàn)的比重較大，所以，這種壓縮處理能夠有效地降低圖像局部的陰影和光照變化。在文中采用Gamma校正法對(duì)輸入圖像進(jìn)行顏色空間的標(biāo)準(zhǔn)化（歸一化）；目的是調(diào)節(jié)圖像的對(duì)比度，降低圖像局部的陰影和光照變化所造成的影響，同時(shí)可以抑制噪音的干擾；壓縮圖像的方法是將院圖像進(jìn)行（gamma）冪指數(shù)處理。即Gamma壓縮公式為：（2-15）一般可以取Gamma=1/2。（3）梯度計(jì)算檢測(cè)器的性能對(duì)梯度的計(jì)算方法是非常敏感的，但是最簡(jiǎn)單的方法被證明也是最好的方法。我們?cè)谝粋€(gè)離散導(dǎo)數(shù)后使

37、用高斯平滑計(jì)算圖像橫坐標(biāo)和縱坐標(biāo)方向的梯度，并據(jù)此計(jì)算每個(gè)像素位置的梯度方向值。求導(dǎo)操作不僅能夠捕獲圖像的輪廓，人影和一些紋理信息，還能進(jìn)一步減弱光照對(duì)此的影響。在一幅圖像中像素點(diǎn)(x,y)的水平以及垂直梯度為：（2-16）式中分別表示輸入圖像中像素點(diǎn)處的水平方向梯度、垂直方向梯度和像素值。像素點(diǎn)處的梯度幅值和梯度方向分別為：（2-17）一般來(lái)說(shuō)，最常用的求梯度的方法是：首先用-1,0,1梯度算子對(duì)原圖像做卷積運(yùn)算，得到x軸方向（水平方向，以向右為正方向）的梯度分量的梯度，然后用1,0,-1T梯度算子對(duì)原圖像做卷積運(yùn)算，得到y(tǒng)軸方向（豎直方向，以向上為正方向）的梯度分量的梯度y。然后再利用公式

38、（2-17）計(jì)算該像素點(diǎn)的梯度大小和方向。（4）為每個(gè)細(xì)胞單元構(gòu)建梯度方向直方圖我們將圖像分成若干個(gè)“單元格（cell）”，例如一個(gè)單元格為6*6個(gè)像素。假設(shè)我們采用9個(gè)通道的直方圖來(lái)統(tǒng)計(jì)這6*6個(gè)像素的梯度信息。那么也就是將單元格的梯度方向360度分成9個(gè)方向塊。起初令方向塊的每一個(gè)的值都為0，當(dāng)單元格內(nèi)的像素的梯度方向在某一方向塊內(nèi)，則這一方塊的值加1。例如，如果這個(gè)像素的梯度方向是20-40度，符合直方圖的第二個(gè)方向塊，則直方圖的第2個(gè)方向塊內(nèi)的計(jì)數(shù)就加一。這樣，對(duì)單元格內(nèi)每個(gè)像素用梯度方向在直方圖中進(jìn)行加權(quán)投影（映射到固定的角度范圍），就可以得到這個(gè)單元格的梯度方向直方圖了，就是該單元

39、格對(duì)應(yīng)的9維特征向量（因?yàn)橛?個(gè)方向塊）。如圖所示：圖2-10將360度分成9個(gè)方向塊        梯度大小就是作為投影的權(quán)值的。例如：某一像素的梯度方向是20-40度，假設(shè)它的梯度大小是2，那么直方圖第2個(gè)方向塊的計(jì)數(shù)就是加2。（5）合并細(xì)胞單元，歸一化梯度直方圖由于局部光照的變化以及前景-背景對(duì)比度的變化，使得梯度強(qiáng)度的變化范圍非常大。這就需要對(duì)梯度強(qiáng)度做歸一化。歸一化能夠進(jìn)一步地對(duì)光照、陰影和邊緣進(jìn)行壓縮。我們所采取的辦法是：將各個(gè)細(xì)胞單元組合成一個(gè)大的、空間上連通的區(qū)域塊（blocks）。在我們的實(shí)驗(yàn)中，

40、一般采用Dalal提出的Hog特征提取，也就是每相鄰的4個(gè)細(xì)胞單元構(gòu)成一個(gè)區(qū)域塊（block）。通常情況下，我們所使用HOG特征中一般都采用9個(gè)方向塊，即每個(gè)細(xì)胞單元有9個(gè)特征。所以每個(gè)區(qū)域塊內(nèi)就有個(gè)特征向量。這樣由于每個(gè)細(xì)胞單元這樣，一個(gè)塊內(nèi)所有單元格的特征向量串聯(lián)起來(lái)便能得到這個(gè)塊內(nèi)的HOG特征。但是這些區(qū)域塊有些是相互重疊的，這也就意味著：每一個(gè)單元格的特征會(huì)以不同的結(jié)果，重復(fù)出現(xiàn)在最后的特征向量中。我們將歸一化之后的塊描述子（向量）就稱之為HOG描述子。（6）合并HOG特征將各個(gè)區(qū)域塊中的特征描述子串聯(lián)起來(lái)就可以得到該圖像的HOG特征描述子，即最后的HOG特征向量。例如一副64*128

41、維的圖像，以8個(gè)像素點(diǎn)為步長(zhǎng)，那么在該圖像的水平方向?qū)?huì)有8個(gè)掃描窗口，垂直方向?qū)?huì)有16個(gè)掃描窗口，則該圖像所能得到的HOG特征向量為8*16*36，共有8*16*36=4608個(gè)特征。圖像36維HOG特征示意圖如下： 圖2-11 狗和鳥(niǎo)的36維HOG特征2.2.2 HOG特征的降維在本實(shí)驗(yàn)中，我們采用的是31維的HOG特征。這一特征是從大量各種分辨率的圖片中收集了很多36維的HOG特征，并在這些特征向量上進(jìn)行主成分分析（PCA）分析得來(lái)的。圖2-12展示了分析出的主成分，從中我們發(fā)現(xiàn)了很多有趣的現(xiàn)象。圖2-12HOG特征的PCA分析。由圖2-12可以看到，每個(gè)特征向量(eigenvecto

42、r)都顯示為的矩陣，所以每一特征向量的一行對(duì)應(yīng)一個(gè)歸一化因子，每一列對(duì)應(yīng)一個(gè)方向塊。每個(gè)特征向量所對(duì)應(yīng)的特征值在特征向量上方。由前11個(gè)主特征向量所定義的線性子空間基本上包含了HOG特征的所有信息。注意到，所有主特征向量沿著其矩陣表達(dá)的行或列是定值。由前11個(gè)主特征向量(eigenvector)所定義的線性子空間基本上間包含了HOG特征的所有信息 。實(shí)際上，我們用起初的36維特征以及向主特征向量投影所得到的11維特征在目標(biāo)分類上所得到的結(jié)果都差不多。而且使用低維特征可以產(chǎn)生參數(shù)較少的模型，并且能夠加速學(xué)習(xí)和檢測(cè)算法。但是由于在計(jì)算特征金字塔的時(shí)候需要相對(duì)比較耗時(shí)的投影步驟，這就減少了獲得的加速

43、優(yōu)勢(shì)。36維的HOG特征向量是來(lái)自4個(gè)不同的歸一化的9維方向直方圖，所以36維的HOG特征向量也可以很自然地看做一個(gè)的矩陣。而在圖2-12中的主特征向量中，有一個(gè)非常特殊的結(jié)構(gòu)：它們沿其矩陣表達(dá)的行或列(近似)是定值。所以主特征向量所依賴的線性子空間可由沿其矩陣表達(dá)的某一行或列為定值的稀疏向量定義。令，其中和都是36維向量，其的矩陣表達(dá)式滿足下列條件：（2-18）（2-19），例如，定義一個(gè)13維向量，其中的元素是36維HOG特征與每個(gè)和的點(diǎn)積。HOG特征向每個(gè)的投影并通過(guò)計(jì)算對(duì)應(yīng)方向的4個(gè)歸一化值的和(即矩陣表達(dá)的某列的和)來(lái)獲得，HOG特征向每個(gè)的投影通過(guò)計(jì)算對(duì)應(yīng)歸一化方法的9個(gè)方向值的和

44、(即矩陣表達(dá)的某行的和)來(lái)獲得。(注：13維特征并不是36維特征向量V的線性投影，因?yàn)楹筒皇钦坏?。事?shí)上，由V定義的線性子空間的維數(shù)是12)使用11維PCA特征和使用36維HOG特征或由V定義的13維特征進(jìn)行圖像分類可以獲得同樣的性能表現(xiàn)。然而，由于和是稀疏向量 ，所以計(jì)算由V定義的13維特征比計(jì)算向PCA主特征向量的投影要簡(jiǎn)單的多。此外，13維特征有還可以看做是9個(gè)方向特征和反應(yīng)單元格周圍區(qū)域的梯度能量的4個(gè)特征。我們也可以定義對(duì)比度敏感的低維特征。我們發(fā)現(xiàn)有些目標(biāo)類別適合使用對(duì)比度敏感特征，有些目標(biāo)類別又適合用對(duì)比度不敏感特征。所以在實(shí)際中我們既使用對(duì)比度敏感特征又使用對(duì)比度不敏感特征。

45、設(shè)C是聚合有9個(gè)對(duì)比度不敏感方向的像素級(jí)特征映射而獲得的基于單元格的特征映射，D是聚合有18個(gè)對(duì)比度敏感方向的像素級(jí)特征而獲得的基于單元格的特征映射。定義C和D的4種歸一化因子。可以獲得一個(gè)4*(9+18)=108維的特征向量F(i,j)。實(shí)際中我們使用的是此108維向量的一個(gè)解析投影，此投影由下面幾個(gè)統(tǒng)計(jì)量定義：27個(gè)在不同歸一化因子上的累加和(即列的和)，F(xiàn)中的每個(gè)方向通道對(duì)應(yīng)一個(gè)；以及4個(gè)在不同方向(9維對(duì)比度不敏感方向)上的累加和(即行的和)，每個(gè)歸一化因子對(duì)應(yīng)一個(gè)。最終的特征映射是31維向量 G(i,j)，其中27維對(duì)應(yīng)不同的方向通道(9個(gè)對(duì)比度不敏感方向和18個(gè)對(duì)比度敏感方向)，其

46、中4維捕獲(i,j)周圍4個(gè)單元格組成的block的梯度能量。形成31維特征向量的解釋圖如圖：圖2-13 31維特征向量解釋圖下圖為利用31維HOG特征所提取的狗和鳥(niǎo)的圖像特征示意圖： 圖2-14 狗和鳥(niǎo)的31維HOG特征2.2.3 HOG特征優(yōu)缺點(diǎn)：與其它的特征描述方法相比，HOG有很多優(yōu)點(diǎn)。1、 HOG表示的是邊緣梯度的結(jié)構(gòu)特征，因此可以用來(lái)描述局部形狀信息；2、 HOG特征在位置和方向空間的量化，在一定程度上可以抑制圖像旋轉(zhuǎn)和平移所帶來(lái)的影響；3、 HOG特征將局部區(qū)域也歸一化成直方圖，這樣可以減弱光照變化所帶來(lái)的影響；4、 由于在HOG特征中可以忽略光照對(duì)圖像的影響，使得圖像所需要表示

47、特征的數(shù)據(jù)位數(shù)降低；5、 由于HOG特征有將數(shù)據(jù)進(jìn)行分塊和分單元格的處理方式，使得圖像的局部像素點(diǎn)之間的關(guān)系得到很好的表達(dá)。HOG的缺點(diǎn)：1、 HOG的特征描述子生成過(guò)程比較長(zhǎng)，這樣就使得提取特征的速度較慢，實(shí)時(shí)性差；2、 HOG特征很難處理遮擋的圖像；3、 由于梯度自身的性質(zhì)，HOG特征對(duì)噪聲比較敏感。2.3 小結(jié)HOG及SIFT算法都是局部特征，其中Hog沒(méi)有旋轉(zhuǎn)和尺度不變性，因此計(jì)算量??；而SIFT中每個(gè)特征需要用128維的向量來(lái)描述，因此計(jì)算量相對(duì)很大。對(duì)于兩種不同的底層特征，各有其自身優(yōu)勢(shì)。所以我們選用這兩個(gè)特征作為本實(shí)驗(yàn)的底層特征。3、 中層特征目前，基于局部特征的模型在視覺(jué)目標(biāo)分

48、類中都取得了較好的結(jié)果。而中層特征就是利用這些原始的圖像的特征向量將其進(jìn)行整理，以使原始圖像的局部特征向量更具有代表性，能更好的實(shí)現(xiàn)目標(biāo)分類。在這一章中，我們重點(diǎn)介紹了我們所使用的中層特征有：詞包（BoW）模型以及高效匹配核函數(shù)（EMK）模型。具體介紹見(jiàn)下文。3.1 BoW（Bag of Word）模型BoW模型的全稱為Bag of Words，早先是為了處理文本數(shù)據(jù)而在文本處理領(lǐng)域提出的一種簡(jiǎn)單有效的分類方法。由于其簡(jiǎn)單易行的原理，圖像分類領(lǐng)域中也開(kāi)始使用這種分類模型。本節(jié)我們將對(duì)BoW這一經(jīng)典模型的概念以及具體實(shí)現(xiàn)進(jìn)行詳細(xì)的闡述。由于圖像可以類比為文檔(document), 圖像中的單詞(

49、words)可以定義為一個(gè)圖像塊(image patch)的特征向量. 那么圖像的BoW模型即是 “圖像中所有圖像塊的特征向量得到的直方圖”。將圖像表達(dá)為BoW模型的類似于圖像3-1：圖3-1 對(duì)于圖像的BoW模型表示示意圖BoW的關(guān)鍵之處在于將局部特征描述子映射到一個(gè)新的特征空間空間中去，而這個(gè)特征空間的基礎(chǔ)就是視覺(jué)單詞所組成的向量。在新的映射空間中，一副圖片中的局部特征向量被轉(zhuǎn)換成了一組新的向量。而在做圖像匹配時(shí)，可以由歐幾里德距離等來(lái)計(jì)算。BoW模型在圖像分類中的具體實(shí)現(xiàn)的流程示意圖如圖：圖3-2：BoW模型在圖像分類中的具體實(shí)現(xiàn)的流程示意圖建立BoW模型主要分為如下幾個(gè)步驟:1. 特征

50、提取假設(shè)共有N張圖像, 第i張圖像圖像由n(i)個(gè)圖像塊組成, 即可以用n(i)個(gè)特征向量來(lái)表達(dá)這張圖像。則所有圖像的的特征向量的總和就是BoW的單詞。特征向量可以根據(jù)特征問(wèn)題自行設(shè)計(jì), 常用特征有Color histogram, SIFT, LBP等.在第二章中，我們已經(jīng)講述了我們所用來(lái)提取特征的算法為SIFT特征算法以及HOG特征算法。這里不再敘述。2. 生成字典/碼本(codebook)在提取完圖像的特征向量后，我們接下來(lái)的任務(wù)就是要將這些特征向量轉(zhuǎn)換成能夠表示為圖像的“關(guān)鍵詞”，并將全部關(guān)鍵詞結(jié)合起來(lái)完成碼本的構(gòu)建。為了能夠得到碼本，我們將第一步中所得到的特征向量進(jìn)行聚類。在文章中，我

51、們使用的聚類方法是K-means聚類方法。K-means聚類算法是最簡(jiǎn)單的一種聚類算法。由于簡(jiǎn)潔和效率，K-means聚類算法成為人們最廣泛使用的聚類算法。它在一個(gè)給定數(shù)據(jù)點(diǎn)集合和需要的聚類中心數(shù)目k（k由用戶指定）的情況下，根據(jù)某一個(gè)距離函數(shù)，反復(fù)的把數(shù)據(jù)分入到k個(gè)聚類中心中去。K-means聚類算法的一般步驟是：（1）在給定對(duì)象集合的情況下，隨機(jī)選取k個(gè)值作為起始的聚類中心。注：這個(gè)過(guò)程大多數(shù)情況都是采用隨機(jī)選取的辦法，或者針對(duì)不同的聚類情況選取特定的聚類中心；（2）計(jì)算每個(gè)聚類對(duì)象到各個(gè)聚類中心的距離，將每一個(gè)對(duì)象歸類到離它最近的那個(gè)聚類中心。聚類中心及所分配給它的對(duì)象就表示一個(gè)聚類；（

52、3）當(dāng)對(duì)象集合中的所有對(duì)象都被分配給某一個(gè)聚類中心時(shí)，每個(gè)聚類的聚類中心就會(huì)根據(jù)它所被分配的對(duì)象被重新計(jì)算；（4）由于K-means聚類的結(jié)果過(guò)度依賴于初值的選取。我們不能保證在每一次的聚類中都會(huì)取得收斂到全局的最優(yōu)解的。因此是用新的聚類中心，重復(fù)第二步，一直到迭代到聚類中心基本不在變化為止。3. 根據(jù)碼本生成直方圖將K-means聚類中每個(gè)聚類中心及被分配給該聚類中心的對(duì)象轉(zhuǎn)化成直方圖，這樣就可以得到該圖片對(duì)應(yīng)于該碼本的BoW表示。聚類過(guò)程的示意圖如下：圖3-3：聚類過(guò)程示意圖3.2 EMK（Efficient match kernel）高效匹配核函數(shù)（EMK）方法是一種特殊的核函數(shù)方法，所

53、以在介紹EMK之前，我們要先知道什么是核函數(shù)方法，核函數(shù)方法可以用來(lái)解決不同維數(shù)集合的匹配問(wèn)題。它可以用來(lái)解決在將低維線性不可分空間通過(guò)非線性映射到高維特征空間中實(shí)現(xiàn)線性可分的時(shí)候所帶來(lái)的在高維空間中位數(shù)過(guò)高問(wèn)題的一種方法。核函數(shù)方法使得高維空間的特征位數(shù)減少，大大的減少了計(jì)算量。它是除了BoW之外另一種計(jì)算局部無(wú)序特征相似性的方法。核函數(shù)方法可以和不同的算法相結(jié)合，形成多種不同的基于核函數(shù)技術(shù)的方法。而論文6也證明了BoW也可以看做是一個(gè)特殊視覺(jué)核函數(shù)。通常情況下，核函數(shù)方法都需要明確的求出所有核函數(shù)的矩陣，因此它們需要的空間以及時(shí)間復(fù)雜度是圖片數(shù)量的二次方。而高效匹配核函數(shù)（EMK）這一結(jié)

54、合了BoW和核函數(shù)集合的方法就被提了出來(lái)。我們將圖像的局部特征映射到低維度的特征空間中去并且通過(guò)平均這個(gè)結(jié)果特征向量構(gòu)建一個(gè)特征層集合。所以EMK不需要計(jì)算全部的核函數(shù)矩陣，這就使得在有大量的圖片進(jìn)行處理時(shí)，它的時(shí)間以及空間復(fù)雜度都是線性的。3.2.1 核函數(shù)框架目前，基于局部特征的模型方法在許多視覺(jué)目標(biāo)識(shí)別實(shí)驗(yàn)中都取得了很好的結(jié)果。對(duì)于一幅圖片，它可以由其塊中所提取的局部特征集合來(lái)表示。由于不同圖像所提取的局部特征集合不一定相同，因此在匹配過(guò)程中，如何將這寫(xiě)局部特征集合所有的技術(shù)不同的圖片進(jìn)行匹配就成了一個(gè)需要重點(diǎn)決定的問(wèn)題。核函數(shù)方法是就用來(lái)解決不同維數(shù)集合圖像的匹配問(wèn)題的。對(duì)于具有不同模

55、的圖像集合X和集合Y，我們可以使用公式(3-1)來(lái)進(jìn)行集合的匹配過(guò)程：(3-1)基于數(shù)學(xué)中的封閉屬性，我們可以確定只要是正定的，則就是一個(gè)正定的核函數(shù)。為了方便起見(jiàn)，我們將看做是一個(gè)局部核函數(shù)，我們可以看到這個(gè)核函數(shù)在計(jì)算的過(guò)程中，需要計(jì)算所有的匹配函數(shù)的和，也就是說(shuō)，對(duì)于一個(gè)由向量定義的單獨(dú)的核函數(shù)的來(lái)說(shuō)，它的計(jì)算復(fù)雜度是而不是O(1)這就使得這個(gè)核分別花費(fèi)和度來(lái)存儲(chǔ)和計(jì)算所有的核函數(shù)矩陣。其中n為訓(xùn)練集中的圖像數(shù)目，d是描述子的維數(shù)，m是所有集合的平均基數(shù)。對(duì)于圖片分類來(lái)說(shuō)，m可以是成千上萬(wàn)個(gè)單元，因此，它的計(jì)算花費(fèi)能夠以n的四次方的形式快速增長(zhǎng)。核函數(shù)方法除了在訓(xùn)練時(shí)需要花費(fèi)很高的代價(jià)外

56、，它在測(cè)試方面所花費(fèi)的代價(jià)也是非常高的。對(duì)于一些稀疏的核函數(shù)分類方法，它在各個(gè)方面所花費(fèi)的代價(jià)在一定程度上能夠得到降低，但是由于稀疏的層數(shù)往往都會(huì)隨著n線性增長(zhǎng)，所以還是不會(huì)改變其其復(fù)雜度。3.2.2 用核函數(shù)的方法重新審視BoW在監(jiān)督類圖像分類中，我們給出了圖片的訓(xùn)練集合以及這些圖片所對(duì)應(yīng)的標(biāo)簽。我們的目的就是為了訓(xùn)練一個(gè)分類器，使得我們能夠標(biāo)注出那些看不到的圖像。我們就采用了特征包的方法。令，分別為圖片、的局部特征集合。為詞表，即視覺(jué)單詞的集合，其中為詞表大小。是基于詞典的的編碼系數(shù)向量。在BoW中，每一個(gè)特征向量都被量化到D維的二進(jìn)制向量中去，在通常情況下采用硬性分配，令，則有當(dāng)時(shí)的值即

57、為1，否則為0。即如下公式：（3-2） 由公式（3-2）我們可以知道，很明顯是一個(gè)正定函數(shù)。而且會(huì)被分配到此表中與其最近的詞匯。在稀疏編碼中，匹配的整個(gè)過(guò)程都是與公式（3-2）相似，除了它不僅僅是屬于稀疏編碼中的一個(gè)基礎(chǔ)，也就是說(shuō)在中，不僅僅只有一個(gè)元素是非零的。對(duì)于圖片的直方圖，我們可以將其看成在公式（3-2）中，稀疏編碼中的對(duì)于的一種合并求和的方法。即為：（3-3）在實(shí)際的許多應(yīng)用中，一幅圖片的表示并不是我們所要求的最終結(jié)果，而是為了得到在圖像匹配的過(guò)程中所需要圖片之間的相似性。為了比較圖片之間的相似性，我們一般會(huì)采用計(jì)算直方圖之間距離的方法。假設(shè)圖片以及它們的直方圖，一般來(lái)說(shuō)，最常見(jiàn)的匹配方法就是計(jì)算的直方圖之間的歐幾里德距離。那么和之間的距離表示如下：（3-4）在公式（3-4）中，如果我們采用內(nèi)積的方法來(lái)代替歐幾里德距離，則公式（3-4）會(huì)轉(zhuǎn)化為如下形式：（3-5）也可以將公式（3-5）寫(xiě)成（3-6）其中，并且。這就將BoW看成核函數(shù)方法的過(guò)程。3.2.3 EMK的實(shí)現(xiàn)過(guò)程在核函數(shù)方法的實(shí)際應(yīng)用當(dāng)中，我們?cè)?.2.1節(jié)中已經(jīng)知道，公式（3-1）對(duì)于核函數(shù)矩陣的計(jì)算復(fù)雜度是，其中n是訓(xùn)練集中圖片的張數(shù)，d是描述子的維數(shù)，m是所有集合的平均基數(shù)。它的昂貴的計(jì)算代價(jià)阻礙了核函數(shù)方法在一些大數(shù)據(jù)集中的應(yīng)用。由于受到公式（3-6）的啟發(fā)，如果在公式（3-1）中我們使，那么公式（3