劉 婉，徐望明，石漢路

（武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢 430081）

在如今信息化的時代，圖像資源日益豐富，如何從海量圖像資源里快速有效地獲取有價值的信息，是亟需解決的問題。傳統(tǒng)的基于文本的圖像檢索技術(shù)（TBIR）因其自身的局限性而無法從根本上解決這個問題。20世紀(jì)90年代，計算機(jī)視覺技術(shù)被應(yīng)用到圖像檢索中，由此產(chǎn)生了基于內(nèi)容的圖像檢索技術(shù)（CBIR），其關(guān)鍵在于：一是提取可靠的圖像特征來表征圖像的視覺內(nèi)容，二是根據(jù)圖像數(shù)據(jù)庫規(guī)模尋找有效的特征索引和相似性匹配算法。

描述圖像視覺內(nèi)容的全局特征如顏色 （Color）、形狀（Shape）、紋理（Texture）等雖被廣泛應(yīng)用于許多實際的圖像檢索系統(tǒng)中，但因其不能適應(yīng)圖像的局部變化而導(dǎo)致應(yīng)用上的局限，目前流行的方法是提取圖像的局部不變特征，從而用一組高維特征向量來表示圖像，這其中SIFT[1]特征的性能得到了普遍認(rèn)可。然而，高維局部特征在增強圖像信息的可分辨性的同時，也帶來了特征相似性搜索問題上的挑戰(zhàn)：每幅常規(guī)大小的圖像平均能提取成百上千的局部特征，這樣對大規(guī)模的圖像檢索系統(tǒng)而言，所生成的特征庫將是巨大的，一個高效的索引和匹配機(jī)制就成為特征相似性搜索迫切需要解決的難題。顯然，簡單的線性掃描搜索方法并不現(xiàn)實，而一般基于特征空間分割的索引方法如K-D Tree、R-Tree等隨著維數(shù)的增加其檢索性能急劇惡化。不過，LSH（Locality Sensitive Hashing）算法[2]為克服這種“維度災(zāi)難”問題提供了一條有效途徑，可用來解決主存儲器中高維特征的“近似近鄰”（ANN，Approximate Nearest Neighbor）搜索問題。

文中將圖像局部不變特征SIFT和高維特征索引算法LSH相結(jié)合應(yīng)用于基于內(nèi)容的圖像檢索，通過實驗驗證了即使在特征維數(shù)比較大時，仍能取得較好的檢索效果。

1 算法描述

1.1 SIFT算法

SIFT（Scale Invariant Feature Transform）算法是 David.G.Lowe在2004年在總結(jié)基于不變量技術(shù)的特征檢測方法的基礎(chǔ)上提出的一種基于尺度空間對圖像縮放、旋轉(zhuǎn)、光照變化甚至遮擋、裁剪等保持不變性的特征提取算法。以下是生成SIFT特征的幾個主要步驟[1-3]：

第1步：檢測尺度空間極值點。搜尋所有尺度和空間坐標(biāo)下的像素點，用層疊濾波的方式和高斯差分函數(shù)（DOG，Difference of Gauss）進(jìn)行運算，以便找出潛在的特征點，這些點是不同尺度和空間中的局部極大值和極小值。

第2步：精確定位特征點。所有在第1步找出來的候選特征點中低對比度的點和不穩(wěn)定的邊緣點被丟棄，并構(gòu)建了一個具體的模型以確定剩下的特征點的位置和尺度。

第3步：分配特征點方向。根據(jù)局部圖像特征點的梯度方向，一個或多個方向被分配給每個有意義的（在第2步中確定的）特征點。

第4步：生成特征向量。這一步通過在每個特征點周圍4×4共16個子區(qū)域采樣圖像像素的梯度幅度和8個方向形成一個覆蓋采樣區(qū)域的梯度方向直方圖來完成。梯度在特征點所在尺度計算，以確保尺度不變性。將坐標(biāo)軸旋轉(zhuǎn)為特征點的方向，以確保旋轉(zhuǎn)不變性。將梯度以加權(quán)的方式進(jìn)行累加得到的直方圖可轉(zhuǎn)換形成一個128維的向量，即為特征描述子，進(jìn)一步對其歸一化，從而去除光照條件變化的影響。

由于每幅圖像的內(nèi)容不同，它們的特征向量數(shù)量也會不同，但通常每幅常規(guī)大小的圖像平均都能提取成百上千個SIFT特征，并且每個特征向量都有128維。在圖像數(shù)據(jù)庫規(guī)模較大時就需要有高效的特征索引和特征相似性匹配機(jī)制來有效完成圖像檢索任務(wù)。

1.2 LSH算法

傳統(tǒng)的近鄰查詢指出，數(shù)據(jù)點與查詢點之間的距離應(yīng)滿足小于某個特定距離的條件，而在實際應(yīng)用中，為了提高檢索速度，可以以降低檢索的準(zhǔn)確度為代價。由此，基于“近鄰查詢”的概念提出了“近似近鄰查詢”的概念。近似近鄰查詢要求數(shù)據(jù)點與查詢點之間的距離小于某個特定距離的概率應(yīng)大于給定的概率值[4]。通過近似近鄰的方法可以快速獲取大致符合相似要求的點集，一種解決近似近鄰問題的重要方法就是LSH算法。

LSH算法的基本思想[4]是對數(shù)據(jù)點集，利用一組具有一定約束條件的哈希函數(shù)來建立多個哈希表，使得在某種相似度量條件下，相似的點發(fā)生沖突的概率較大，而不相似的點發(fā)生沖突的概率相對較小。

引入LSH函數(shù)的定義[2]：

對任意的p，q∈S（S為查詢高維矢量空間），定義哈希函數(shù)族H={hi:S→U}對距離函數(shù)D（·）應(yīng)該滿足如下條件：

1）若 D（p，q）p1]；

2）若 D（p，q）>r2，則 P[hi（q）=hi（p）

其中，P（·）是概率函數(shù)，i是隨機(jī)數(shù)，i∈{1，…，k}。

LSH算法處理近似近鄰搜索問題的高效性體現(xiàn)在如下的處理過程[2-5]：

對于給定參數(shù)（r1，r2，p1，p2）的哈希函數(shù)族 H 和常數(shù) k，定義一個新的哈希函數(shù)族 Ω={g:S→Uk}， 滿足 g （p）={h1（p），h2（p），…，hk（p）}，其中 hi∈H，p∈S 為特征向量。 從 Ω 中隨機(jī)選擇 L 個函數(shù)（g1，g2，…，gL）。 當(dāng)建立特征索引時，將每一個 p 通過哈希映射后存儲在哈希表項 gj（p）中，其中 j=0，…，L，由于這些表項的總數(shù)可能會很大，需要通過使用散列保留非空表項。當(dāng)查詢一個特征向量q時，通過搜索所有的哈希表項g1（q），g2（q），gL（q）得到屬于 q 的相似域的所有特征向量。 如果p與q的距離在q的相似域閾值范圍內(nèi)，則返回p作為q的近似近鄰。

2 CBIR系統(tǒng)構(gòu)建

文中將SIFT特征提取算法和LSH索引算法應(yīng)用到基于內(nèi)容的圖像檢索系統(tǒng)（CBIR）中，構(gòu)造實驗系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 提出的基于內(nèi)容的圖像檢索系統(tǒng)Fig.1 The proposed CBIR system

首先，利用程序讀取圖像庫中的每一幅圖像，并采用SIFT算法提取其特征向量，然后依次存入特征數(shù)據(jù)庫。特征數(shù)據(jù)庫中應(yīng)包含圖像每個SIFT特征128維的向量信息以及每個特征向量所屬原圖像的ID（ID即圖像編號）信息。然后，根據(jù)LSH算法建立圖像特征索引。

對于用戶給定的查詢圖像，系統(tǒng)首先提取其SIFT特征向量，通過LSH索引的近似近鄰查詢方法可以獲得與給定圖像的特征向量集相似的所有特征向量以及所屬庫圖像的ID，對將得到的庫圖像ID進(jìn)行投票統(tǒng)計，如果要求只找出與給定查詢圖像最相似的N幅圖像，那就選出出現(xiàn)頻數(shù)最多的前N個ID（即為與查詢圖像最相似的N幅庫圖像的ID），利用程序在圖像庫里找到對應(yīng)ID的N幅圖像，按照ID出現(xiàn)頻數(shù)由大到小的順序 （即與目標(biāo)圖像相似程度由高到低的順序）顯示檢索得到的N幅圖像。

3 圖像檢索實驗及性能分析

1）實驗設(shè)置

圖像庫采用Caltech Buildings圖像庫[6]中的圖像，其中包含250幅建筑物的圖片，圖像尺寸為300×300，取自50處不同的建筑物，其中每一處建筑物圖像存在不同程度的縮放、旋轉(zhuǎn)、視角偏差和亮度變化等。另外，從Caltech Buildings提供的250幅圖片中隨機(jī)選取15幅圖片作為查詢圖像對系統(tǒng)進(jìn)行測試。文中采用Matlab實現(xiàn)整個實驗過程。實驗中，對圖像庫中250幅圖像提取的SIFT特征總數(shù)為168 790，實驗要求在圖像庫中檢索出與目標(biāo)圖像具有相同建筑物的前5幅圖像。

2）實驗結(jié)果及性能評價

圖2是對查詢庫中的任意兩幅圖像進(jìn)行查詢后所得實驗結(jié)果的示例。從中可以看出，系統(tǒng)分別為兩幅查詢圖像檢索出5幅與之相似的圖像。圖2中5-NN（5-Nearest-Neighbor）檢索結(jié)果即5幅近鄰檢索圖像。對第一幅查詢圖像而言，系統(tǒng)準(zhǔn)確地返回了圖像庫中與之相關(guān)圖像的5幅圖像的全部；對第二幅查詢圖像而言，系統(tǒng)返回了圖像庫中與之相關(guān)圖像的5幅圖像中的4幅，且排序比較靠前，最后1幅圖像是錯誤的返回結(jié)果。

圖2 兩幅查詢圖像及實驗結(jié)果示例Fig.2 Examples of two query images and the experimental results

對于該系統(tǒng)的性能評價，采用信息檢索中標(biāo)準(zhǔn)的評價方法：查全率與查準(zhǔn)率。

查全率是在一次查詢過程中系統(tǒng)返回的查詢結(jié)果中的相關(guān)圖像的數(shù)目r在圖像庫中所有相關(guān)圖像數(shù)目R中占有的比例，用公式表示為：

查準(zhǔn)率是指在一次查詢系統(tǒng)過程中系統(tǒng)返回的查詢結(jié)果中的相關(guān)圖像的數(shù)目r在所有返回圖像數(shù)目N中占有的比例，用公式表示為：

由于實驗中Caltech Buildings圖像庫中每幅查詢圖像只有5幅相關(guān)圖像，系統(tǒng)指定返回5幅圖像作為檢索結(jié)果，R=N，從而查全率與查準(zhǔn)率值相等。表1統(tǒng)計了查詢庫中15幅圖像的檢索結(jié)果。

表1 15幅查詢圖像的檢索結(jié)果Tab.1 Retrieval results of 15 query images

由此，可初步估算出系統(tǒng)的平均查全率（或查準(zhǔn)率）=每幅查詢圖像的查全率之和/查詢圖像的總數(shù)目=86.67%。更準(zhǔn)確的平均查準(zhǔn)率（或查準(zhǔn)率）可使用更多的查詢圖像或使用不同的圖像庫重做實驗加以統(tǒng)計。

4 結(jié)束語

文中將目前流行的圖像局部不變特征提取算法SIFT和高維特征索引算法LSH應(yīng)用到基于內(nèi)容的圖像檢索系統(tǒng)（CBIR）中，在Caltech Buildings圖像庫上進(jìn)行了圖像檢索實驗，驗證了該方法的有效性。

[1]David G L.Distinctive image features from scale-invariant keypoints[J].InternationalJournalofComputerVision，2004，60（2）：91-110.

[2]Indyk P，Motwani R.Approximate nearest neighbors：Towards removing the curse of dimensionality[C]//Proc.of the 30th ACM Symposium on Theory of Computing，New York:ACM Press，1998：604-613.

[3]David G L.Object recognition from local scale-invariant features[C]//International Conference on Computer Vision，Washimgtoin，DC，USA：IEEE Computer Society，1999：1150-1157.

[4]唐俊華，閻保平.基于LSH索引的快速圖像檢索[J].計算機(jī)工程與應(yīng)用，2002，38（24）：20-21，63.TANG Jun-hua，YAN Bao-pin.Fast image retrieval based on LSH indexing[J].Computer Engineering and Applications，2002，38（24）：20-21，63.

[5]Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing[C]//Proc.International Conference on Very Large Data Bases，USA:Morgan Kaufmann Publisher Lnc.，1999：518-529.

[6]Caltech-building data set[EB/OL][2011-08-02].http://www.vision.caltech.edu/malaa/datasets/caltech-buildings/caltechbuildings.zip.