Bag of Features (BOF)图像检索算法
FROM：http://blog.csdn.net/loadstar_kun/article/details/39450137
?1.首先，我們用surf算法生成圖像庫(kù)中每幅圖的特征點(diǎn)及描述符。
2.再用k-means算法對(duì)圖像庫(kù)中的特征點(diǎn)進(jìn)行訓(xùn)練，生成類(lèi)心。
3.生成每幅圖像的BOF，具體方法為：判斷圖像的每個(gè)特征點(diǎn)與哪個(gè)類(lèi)心最近，最近則放入該類(lèi)心，最后將生成一列頻數(shù)表，即初步的無(wú)權(quán)BOF。
4.通過(guò)tf-idf對(duì)頻數(shù)表加上權(quán)重，生成最終的bof。（因?yàn)槊總€(gè)類(lèi)心對(duì)圖像的影響不同。比如超市里條形碼中的第一位總是6，它對(duì)辨別產(chǎn)品毫無(wú)作用，因此權(quán)重要減小）。
5.對(duì)query進(jìn)來(lái)的圖像也進(jìn)行3.4步操作，生成一列query圖的BOF。
6.將query的Bof向量與圖像庫(kù)中每幅圖的Bof向量求夾角，夾角最小的即為匹配對(duì)象。
圖像檢索中應(yīng)用LSH實(shí)現(xiàn)快速搜索，其在一定概率的保證下解決了高維特征查詢(xún)的問(wèn)題，但筆者在應(yīng)用LSH結(jié)合SIFT特征實(shí)踐圖像檢索實(shí)驗(yàn)時(shí)，由于每張圖像涉及上百個(gè)特征，那么在查詢(xún)一張圖片時(shí)，需要進(jìn)行上而次的特征查詢(xún)，即便是將查詢(xún)圖片的特征點(diǎn)數(shù)篩選至50%的量，一次圖片查詢(xún)需要進(jìn)行的特征查詢(xún)次數(shù)亦不容小窺。那么有沒(méi)有方法可以將任意圖片的所有特征向量用一個(gè)固定維數(shù)的向量表出，且這個(gè)維數(shù)并不因圖片特征點(diǎn)數(shù)不同而變化？本篇要講到的方法可以解決這個(gè)問(wèn)題，盡管它并不是因這個(gè)問(wèn)題而生的。
Bag-of-Words模型源于文本分類(lèi)技術(shù)，在信息檢索中，它假定對(duì)于一個(gè)文本，忽略其詞序和語(yǔ)法、句法。將其僅僅看作是一個(gè)詞集合，或者說(shuō)是詞的一個(gè)組合，文本中每個(gè)詞的出現(xiàn)都是獨(dú)立的，不依賴(lài)于其他詞是否出現(xiàn)，或者說(shuō)這篇文章的作者在任意一個(gè)位置選擇詞匯都不受前面句子的影響而獨(dú)立選擇的。
圖像可以視為一種文檔對(duì)象，圖像中不同的局部區(qū)域或其特征可看做構(gòu)成圖像的詞匯，其中相近的區(qū)域或其特征可以視作為一個(gè)詞。這樣，就能夠把文本檢索及分類(lèi)的方法用到圖像分類(lèi)及檢索中去。
?????????????????????? Accelerating?Bag-of-Features?SIFT?Algorithm??for?3D?Model?Retrieval
Bag-of-Features模型仿照文本檢索領(lǐng)域的Bag-of-Words方法，把每幅圖像描述為一個(gè)局部區(qū)域/關(guān)鍵點(diǎn)(Patches/Key?Points)特征的無(wú)序集合。使用某種聚類(lèi)算法(如K-means)將局部特征進(jìn)行聚類(lèi)，每個(gè)聚類(lèi)中心被看作是詞典中的一個(gè)視覺(jué)詞匯(Visual?Word)，相當(dāng)于文本檢索中的詞，視覺(jué)詞匯由聚類(lèi)中心對(duì)應(yīng)特征形成的碼字(code?word)來(lái)表示（可看當(dāng)為一種特征量化過(guò)程）。所有視覺(jué)詞匯形成一個(gè)視覺(jué)詞典(Visual?Vocabulary)，對(duì)應(yīng)一個(gè)碼書(shū)(code?book)，即碼字的集合，詞典中所含詞的個(gè)數(shù)反映了詞典的大小。圖像中的每個(gè)特征都將被映射到視覺(jué)詞典的某個(gè)詞上，這種映射可以通過(guò)計(jì)算特征間的距離去實(shí)現(xiàn)，然后統(tǒng)計(jì)每個(gè)視覺(jué)詞的出現(xiàn)與否或次數(shù)，圖像可描述為一個(gè)維數(shù)相同的直方圖向量，即Bag-of-Features。
???????????????????????????????????????????
??????????????????????????Bag?of?Features?Codebook?Generation?by?Self-Organisation
?Bag-of-Features更多地是用于圖像分類(lèi)或?qū)ο笞R(shí)別。在上述思路下對(duì)訓(xùn)練集提取Bag-of-Features特征，在某種監(jiān)督學(xué)習(xí)（如:SVM）的策略下，對(duì)訓(xùn)練集的Bag-of-Features特征向量進(jìn)行訓(xùn)練，獲得對(duì)象或場(chǎng)景的分類(lèi)模型；對(duì)于待測(cè)圖像，提取局部特征，計(jì)算局部特征與詞典中每個(gè)碼字的特征距離，選取最近距離的碼字代表該特征，建立一個(gè)統(tǒng)計(jì)直方圖，統(tǒng)計(jì)屬于每個(gè)碼字的特征個(gè)數(shù)，即為待測(cè)圖像之Bag-of-Features特征；在分類(lèi)模型下，對(duì)該特征進(jìn)行預(yù)測(cè)從實(shí)現(xiàn)對(duì)待測(cè)圖像的分類(lèi)。
Classification?Process
1、局部特征提取：通過(guò)分割、密集或隨機(jī)采集、關(guān)鍵點(diǎn)或穩(wěn)定區(qū)域、顯著區(qū)域等方式使圖像形成不同的patches，并獲得各patches處的特征。
????????????????????????????????????????????????????????????????????????????????????
其中，SIFT特征較為流行。
2、構(gòu)建視覺(jué)詞典：
由聚類(lèi)中心代表的視覺(jué)詞匯形成視覺(jué)詞典：
3、生成碼書(shū)，即構(gòu)造Bag-of-Features特征，也即局部特征投影過(guò)程：
4、SVM訓(xùn)練BOF特征得分類(lèi)模型，對(duì)待測(cè)圖像BOF特征預(yù)測(cè)：
Retrieval?Process
Bag-of-words在CV中的應(yīng)用首先出現(xiàn)在Andrew?Zisserman[6]中為解決對(duì)視頻場(chǎng)景的搜索，其提出了使用Bag-of-words關(guān)鍵點(diǎn)投影的方法來(lái)表示圖像信息。后續(xù)更多的研究者歸結(jié)此方法為Bag-of-Features，并用于圖像分類(lèi)、目標(biāo)識(shí)別和圖像檢索。在Bag-of-Features方法的基礎(chǔ)上，Andrew?Zisserman進(jìn)一步借鑒文本檢索中TF-IDF模型(Term?Frequency一Inverse?Document?Frequency)來(lái)計(jì)算Bag-of-Features特征向量。接下來(lái)便可以使用文本搜索引擎中的反向索引技術(shù)對(duì)圖像建立索引，高效的進(jìn)行圖像檢索。
Hamming?embedding?and?weak?geometric?consistency?for?large?scale?image?search
實(shí)現(xiàn)檢索的過(guò)程同分類(lèi)的過(guò)程無(wú)本質(zhì)的差異，更多的是細(xì)節(jié)處理上的差異：
1、局部特征提取；
2、構(gòu)建視覺(jué)詞典；
3、生成原始BOF特征；
4、引入TF-IDF權(quán)值：
TF-IDF是一種用于信息檢索的常用加權(quán)技術(shù)，在文本檢索中，用以評(píng)估詞語(yǔ)對(duì)于一個(gè)文件數(shù)據(jù)庫(kù)中的其中一份文件的重要程度。詞語(yǔ)的重要性隨著它在文件中出現(xiàn)的頻率成正比增加，但同時(shí)會(huì)隨著它在文件數(shù)據(jù)庫(kù)中出現(xiàn)的頻率成反比下降。TF的主要思想是:如果某個(gè)關(guān)鍵詞在一篇文章中出現(xiàn)的頻率高，說(shuō)明該詞語(yǔ)能夠表征文章的內(nèi)容，該關(guān)鍵詞在其它文章中很少出現(xiàn)，則認(rèn)為此詞語(yǔ)具有很好的類(lèi)別區(qū)分度，對(duì)分類(lèi)有很大的貢獻(xiàn)。IDF的主要思想是:如果文件數(shù)據(jù)庫(kù)中包含詞語(yǔ)A的文件越少，則IDF越大，則說(shuō)明詞語(yǔ)A具有很好的類(lèi)別區(qū)分能力。
詞頻(Term?Frequency，TF)指的是一個(gè)給定的詞語(yǔ)在該文件中出現(xiàn)的次數(shù)。如：tf?=?0.030?(?3/100?)表示在包括100個(gè)詞語(yǔ)的文檔中,?詞語(yǔ)'A'出現(xiàn)了3次。
逆文檔頻率(Inverse?Document?Frequency，IDF)是描述了某一個(gè)特定詞語(yǔ)的普遍重要性，如果某詞語(yǔ)在許多文檔中都出現(xiàn)過(guò)，表明它對(duì)文檔的區(qū)分力不強(qiáng)，則賦予較小的權(quán)重;反之亦然。如:idf?=?13.287?(?log?(10,000,000/1,000)?)表示在總的10,000,000個(gè)文檔中，有1,000個(gè)包含詞語(yǔ)'A'。
最終的TF-IDF權(quán)值為詞頻與逆文檔頻率的乘積。
5、對(duì)查詢(xún)圖像生成同樣的帶權(quán)BOF特征；
6、查詢(xún)：初步是通過(guò)余弦距離衡量，至于建立索引的方法還未學(xué)習(xí)到，望看客指點(diǎn)。
Issues
1、使用k-means聚類(lèi)，除了其K和初始聚類(lèi)中心選擇的問(wèn)題外，對(duì)于海量數(shù)據(jù)，輸入矩陣的巨大將使得內(nèi)存溢出及效率低下。有方法是在海量圖片中抽取部分訓(xùn)練集分類(lèi)，使用樸素貝葉斯分類(lèi)的方法對(duì)圖庫(kù)中其余圖片進(jìn)行自動(dòng)分類(lèi)。另外，由于圖片爬蟲(chóng)在不斷更新后臺(tái)圖像集，重新聚類(lèi)的代價(jià)顯而易見(jiàn)。
2、字典大小的選擇也是問(wèn)題，字典過(guò)大，單詞缺乏一般性，對(duì)噪聲敏感，計(jì)算量大，關(guān)鍵是圖象投影后的維數(shù)高；字典太小，單詞區(qū)分性能差，對(duì)相似的目標(biāo)特征無(wú)法表示。
3、相似性測(cè)度函數(shù)用來(lái)將圖象特征分類(lèi)到單詞本的對(duì)應(yīng)單詞上，其涉及線型核，塌方距離測(cè)度核，直方圖交叉核等的選擇。
4、將圖像表示成一個(gè)無(wú)序局部特征集的特征包方法，丟掉了所有的關(guān)于空間特征布局的信息，在描述性上具有一定的有限性。為此，?Schmid[2]提出了基于空間金字塔的Bag-of-Features。
5、Jégou[7]提出VLAD(vector?of?locally?aggregated?descriptors)，其方法是如同BOF先建立出含有k個(gè)visual?word的codebook，而不同于BOF將一個(gè)local?descriptor用NN分類(lèi)到最近的visual?word中，VLAD所采用的是計(jì)算出local?descriptor和每個(gè)visual?word(c-i)在每個(gè)分量上的差距，將每個(gè)分量的差距形成一個(gè)新的向量來(lái)代表圖片。
Resources
Two?bag-of-words?classifiers(Matlab)
Code?for?Vocabulary?tree?based?image?search(C++)
matlab+VC?實(shí)現(xiàn)Bag?of?features?
Bag?of?Words/Bag?of?Features的Matlab源碼
一個(gè)用BoW|Pyramid?BoW+SVM進(jìn)行圖像分類(lèi)的Matlab?Demo
Bag-Of-Words中K-Means聚類(lèi)的效率優(yōu)化
aMMAI?BLOG
Visual?Wordsを用いた類(lèi)似畫(huà)像検索
bayonを使って畫(huà)像からbag-of-keypointsを求める
Paper
1.Bag?of?words?models(.ppt?)??byLi?Fei-Fei(Stanford)
2.??Spatial?Pyramid?Matching:
-
Beyond?Bags?of?Features:?Spatial?Pyramid?Matching?for?Recognizing?Natural?Scene?Categories
S.?Lazebnik,?C.?Schmid,?and?J.?Ponce,?CVPR?2006
?Slides,?MATLAB?code,?scene?category?dataset
3.?Improving?bag-of-features?for?large?scale?image?search
-
Improving?bag-of-features?for?large?scale?image?search.
Hervé?Jégou,?Matthijs?Douze,?Cordelia?Schmid.International?Journal?of?Computer?Vision,?Volume?87,?Number?3?-?feb?2010.[pdf]
Demo:bigimbaz?image?search?engine?
4.?Hamming?embedding?and?weak?geometric?consistency?for?large?scale?image?search.?Hervé?Jégou,?Matthijs?Douze,?Cordelia?Schmid
European?Conference?on?Computer?Vision?-?oct?2008.[pdf][slides]
5.?Bag-of-colors?for?improved?image?search.?Christian?Wengert,?Matthijs?Douze,?Hervé?Jégou,ACM?Multimedia?(2011).[pdf]
6.?Video?Google:?A?Text?Retrieval?Approach?to?Object?Matching?in?Videos??.??J.?Sivic,?A.?Zisserman.??IEEE?International?Conference?on?Computer?Vision,?Volume?2,?page?1470--1477,?2003.[PDF?]
7.Aggregating?local?descriptors?into?a?compact?image?representation.?Hervé?Jégou,?Matthijs?Douze,?Cordelia?Schmid,?Patrick?Pérez.?IEEE?Conference?on?Computer?Vision?&?Pattern?Recognition?-?jun?2010.?[pdf][sildes]
?
轉(zhuǎn)自：http://hi.baidu.com/hj11yc/item/1c08ac29db90480242634ace
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結(jié)
以上是生活随笔為你收集整理的Bag of Features (BOF)图像检索算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 运动目标检测与跟踪
- 下一篇： Kmeans、Kmeans++和KNN算