基于灰度分類的圖像搜索引擎

魏正曦，邱玲，趙攀

（四川理工學院計算機學院，四川自貢643000）

基于灰度分類的圖像搜索引擎

魏正曦，邱玲，趙攀

（四川理工學院計算機學院，四川自貢643000）

圖像搜索是下一代搜索引擎迫切需要解決的課題，在對圖像搜索引擎的主要功能和關(guān)鍵技術(shù)進行了分析和討論的基礎(chǔ)上，詳細剖析了圖像搜索引擎設(shè)計中任務分析、解決方案、感受哈希算法、實現(xiàn)等關(guān)鍵過程，并實現(xiàn)了一個基于灰度值分類的圖像搜索引擎。實際試驗表明，本圖像搜索引擎的搜索速度較快、性能穩(wěn)定，具有較好的搜索效果。

圖像搜索引擎；網(wǎng)絡(luò)爬蟲；圖像識別；感知哈希算法

隨著網(wǎng)絡(luò)進入Web2.0時代，人們已不滿足于僅對文本信息的搜索，還希望能夠從已知圖像中找到更多的相關(guān)圖像，圖像搜索引擎今后將成為用戶檢索網(wǎng)絡(luò)圖像的主要工具［1］。以圖像分析與圖像識別技術(shù)為支撐的圖像搜索技術(shù)正在成為人們關(guān)注和研究的熱點。

谷歌、百度、搜狗作為用戶搜索信息時最常用的三個綜合性搜索引擎，已經(jīng)推出了用關(guān)鍵詞進行圖像搜索的服務，但使用圖像搜索圖像的功能仍處在測試階段［2］。目前國內(nèi)外還沒有形成一個成熟的圖像搜索引擎產(chǎn)品，主要原因在于圖像比起文本其內(nèi)容更加的豐富、復雜，所包含的信息量是文本無法比擬的。另外，數(shù)字圖像處理技術(shù)還有很多難點沒有解決，文本本身能夠表達一定的語義含義，而圖像只能通過本身的內(nèi)容特征來表達。因此，基于內(nèi)容的圖像檢索比起基于文本的檢索難度要大的多。

1 設(shè)計任務

1.1 解決方案

與文本搜索引擎相對比，圖像搜索引擎需要完成以下四項工作∶自動收集網(wǎng)絡(luò)圖像、建立和維護圖像索引數(shù)據(jù)庫、計算圖像相似性返回檢索結(jié)果、設(shè)計友好的人機交互界面［3］。相應地，圖像搜索引擎的開發(fā)涉及以下四項基本內(nèi)容∶

（1）網(wǎng)絡(luò)圖像的獲取。在完成網(wǎng)絡(luò)圖像搜索任務之前，搜索引擎所在主機要儲備大量的圖片以備圖像比對?？梢允褂镁W(wǎng)絡(luò)爬蟲程序來搜索和下載Internet圖像，該程序從某個網(wǎng)站的頂層開始，按照廣度或深度優(yōu)先的遍歷策略下載網(wǎng)站圖片，并按照一定的格式存儲到本地文件系統(tǒng)中［4］。

（2）圖像特征提取算法。搜索引擎對下載的圖像文件首先進行統(tǒng)一格式化處理，然后提取圖像特征、建立特征庫。使用圖像處理算法為每張圖片生成索引，它可以用來比較、計算不同圖片的相似度。將大量的圖像索引都存入到一個數(shù)據(jù)庫，即圖像特征庫。在建立圖像特征庫時，需要保存源圖像在Internet中的URL地址以及其他屬性以備用戶將來查詢，幫助用戶獲取該圖像所在的原始頁面。

（3）圖像搜索策略。用戶在瀏覽器端上傳想要搜索的示例圖片，示例圖片經(jīng)過上載和格式化轉(zhuǎn)換后送至搜索引擎軟件的圖像處理模塊，根據(jù)圖像比對算法，本地主機為上載圖片生成圖像索引，然后以索引為范本在圖像特征庫中檢索相似圖片；然后將匹配度超過某個臨界值的一組圖片按一定的順序排列［5］、以縮略圖的形式返回至用戶瀏覽器界面，從而完成圖像搜索任務。

（4）編碼實現(xiàn)。按照上述解決方案合理劃分軟件功能模塊，選取相應的開發(fā)環(huán)境、數(shù)據(jù)庫、軟件工具包，逐一完成軟件的編碼和測試工作。

1.2 工作流程設(shè)計

圖像搜索引擎的工作流程如下∶用戶在客戶端上載待檢索的圖片，圖片經(jīng)過預處理后發(fā)送至服務器端，服務器端自動識別圖像特征，在圖像特征庫中檢索相似圖片，最后在頁面顯示圖像檢索結(jié)果［6］。整個步驟如圖1所示。

2 圖像處理算法

本設(shè)計的核心內(nèi)容是圖像匹配算法，即由已知的模板圖中搜索相匹配的子圖像。一般地，圖像匹配算法有基于灰度值的方法如感知哈希算法、序列相似性檢測算法等等，另一種是基于特征提取的方法，如基于顏色特征、紋理特征、形狀特征、空間位置等特征的匹配。本文選用基于灰度值的算法用于建立圖像特征索引。

基于灰度值的圖像處理算法［7］的基本思想是將圖像看成是二維信號，采用統(tǒng)計相關(guān)的方法尋找信號間的相關(guān)匹配。利用兩個信號的相關(guān)函數(shù)，評價它們的相似性以確定相同點。

灰度匹配可以利用某種相似性度量，如相關(guān)函數(shù)、協(xié)方差函數(shù)、差平方和、差絕對值和等測度極值，判定兩幅圖像中的對應關(guān)系。感知哈希算法［8］是其中最具有代表性的算法之一。

2.1 感知哈希算法

感知哈希函數(shù)能在多媒體數(shù)據(jù)集與多媒體感知摘要集之間建立起單向映射關(guān)系，也即，它能將具有相同感知內(nèi)容的多媒體數(shù)字映射表示為一段唯一的數(shù)字摘要。

感知哈希函數(shù)被引入到圖像識別領(lǐng)域是因其有如下的一系列優(yōu)良特性∶

（1）唯一性∶不可逆的提取原始數(shù)據(jù)的數(shù)字摘要，內(nèi)容映射具有單向性。

（2）區(qū)分性∶感知內(nèi)容不同的數(shù)字圖像表示不會映射為相同的感知哈希值。

（3）魯棒性∶感知內(nèi)容相同的不同多媒體數(shù)字表示仍映射為同一哈希值。

（4）摘要性∶在滿足以上基本性質(zhì)的情況下，感知哈希算法處理所得的數(shù)據(jù)量所占的數(shù)據(jù)容量較小。

本設(shè)計即是根據(jù)感知哈希算法的上述特性，將其用于圖像內(nèi)容識別。

2.2 圖像處理過程

利用感知哈希算法處理圖像的工作過程如下∶

（1）圖像格式化∶將圖片縮小到n×n的分辨率（n≤8），總共n2個像素。這樣可以去除圖片的細節(jié)，只保留結(jié)構(gòu)、明暗等基本信息，從而排除圖像因為分辨率、亮度等屬性帶來的差異。

（2）灰度降階∶將圖像統(tǒng)一降階為T級灰度，也就是，把所有像素點簡化成總共只有T種顏色，T≤64級。這樣處理旨在排除圖像顏色數(shù)的差異，將其灰度值放在同一個范圍內(nèi)進行計算。

（3）計算圖像的灰度平均值［9］∶用公式（1）計算圖片中所有n2個像素的灰度平均值u。式中xi表示某一個像素的灰度值，pi表示它在圖像中出現(xiàn)的概率值。

（4）像素的二進制映射∶按公式（2）把像素映射成一個二進制數(shù)。將每個像素的灰度與平均值進行比較，大于或等于平均值，記為1；小于等于平均值，記為0。

（5）構(gòu)造哈希序列值∶將上一步的比較結(jié)果組合在一起，構(gòu)成一個n2位的二進制整數(shù)序列，例如｛1，0，0，1，…，0，1｝，它就是每張圖片的圖像指紋。

（6）圖像比對∶比對算法就是看不同圖像的n2位二進制整數(shù)中有多少位不相同，這相當于計算圖像間的漢明距。一般而言，如果不相同的數(shù)據(jù)位不超過5，就說明兩張圖片很相似；如果大于10，就說明這是兩張不同的圖片。

執(zhí)行算法的前5步可以從原始圖片中計算圖片的指紋值，并將圖片指紋、原始圖片路徑、圖片URL等相關(guān)信息寫入到數(shù)據(jù)庫。

在寫入數(shù)據(jù)庫的時候，需要存入一個關(guān)鍵字所對應的多個屬性記錄，這是因為同樣的一張圖片可能來自不同的網(wǎng)站鏈接。后續(xù)的工作可以通過對比不同圖片的指紋，從而算出圖片之間的相似度。

3 設(shè)計與實現(xiàn)

3.1 開發(fā)工具

Heritrix是一個專門為互聯(lián)網(wǎng)上的網(wǎng)頁進行存檔而開發(fā)的網(wǎng)頁檢索器［10］］。它由Java編寫而成并且完全開源，并支持多線程，現(xiàn)在已經(jīng)成為一個成熟的開源爬蟲，并被廣泛使用。圖像搜索引擎采用Heritrix自動獲取網(wǎng)絡(luò)圖像。

Berkeley DB是一個高性能的嵌入式數(shù)據(jù)庫，它為應用程序提供可伸縮的、高性能的數(shù)據(jù)庫管理服務，支持數(shù)千的并發(fā)線程同時訪問操作數(shù)據(jù)庫，數(shù)據(jù)流量可達TB級別。它不需要對某種查詢語言進行解析，也不用生成執(zhí)行計劃，這就大大提高了運行效率?；谶@些特點，搜索引擎的圖像特征數(shù)據(jù)庫采用Berkeley DB。

軟件選用MyEclipse作為開發(fā)編譯環(huán)境。該工具包的功能非常強大，支持的編程語言類型十分廣泛，尤其是對各種開源產(chǎn)品的開發(fā)提供了多種便利。利用它可以在數(shù)據(jù)庫和Java應用程序服務器的整合方面極大地提高工作效率。

3.2 功能模塊

圖像搜索引擎軟件主要由兩大功能模塊組成，如圖2所示。

圖像處理模塊對客戶端上傳的圖片進行預處理，包括安全檢查、格式轉(zhuǎn)換、尺寸處理等，其中格式轉(zhuǎn)換、尺寸處理將根據(jù)實際需求進行調(diào)整；圖片上傳后存放于服務器的臨時目錄下；通過圖像處理算法自動對圖片內(nèi)容

當相似圖像作為搜索結(jié)果返回到頁面時，圖像搜索結(jié)果按匹配度大小降序排列呈現(xiàn)給用戶。

3.3 測試結(jié)果

測試選取一臺主機作為服務器，搭建和配置運行搜索引擎所需的硬件和軟件環(huán)境，連接圖像特征數(shù)據(jù)庫，保證程序?qū)D像特征庫的有效訪問。

圖像搜索引擎的用戶界面如圖3所示。用戶點擊“瀏覽文件”按鈕選擇圖像搜索的源圖片。如果上傳的圖片符合要求，經(jīng)過客戶端的預處理，瀏覽器上面會出現(xiàn)一個進度條，上面有上傳圖片的名稱以及圖片容量。此時，“開始上傳”按鈕從最初的灰色變?yōu)榭捎?；點擊該按鈕，圖像搜索引擎便自動為用戶搜索相似的圖像。進行分析、識別，得到此圖片的相關(guān)特性信息，生成圖像索引，待下一步調(diào)用圖像搜索模塊進行檢索。

圖像搜索模塊在用戶檢索之前，搜集并存儲大量的圖片，將圖片按顏色、形狀、直方圖等特征進行分類，建立圖像特征索引庫；把經(jīng)過內(nèi)容識別的上傳圖片在圖像特征庫中進行檢索、比對并將一組相似圖片及其來源的URL返回至用戶搜索頁面。

本圖像搜索引擎還提供了不同圖像之間的匹配度，如公式（3）所示。算法首先找出不同圖像的哈希序列值（n2位二進制整數(shù)序列）中有多少相同的二進制位m，然后計算m與n2的比值λ，λ能反映不同圖像的相似程度，比值越大表明圖像也就越相近，如果兩幅圖像完全相同，則匹配度為100%。

圖像搜索結(jié)果如圖4所示。在搜索結(jié)果頁面中，點擊圖片或者圖片下方的超鏈接地址則可查看圖片在源網(wǎng)址頁面。在URL下面，引擎還給出了相似圖像的匹配相似度。

本測試中，圖片庫中的圖片數(shù)量約為5萬張。搜索損耗時間數(shù)據(jù)表明，即使圖片量較大的情況下，本圖像搜索引擎也能在1秒鐘以內(nèi)返回圖像的搜索結(jié)果，并且給出相似圖像的匹配度。這說明本搜索引擎的檢索速度較快，采用的算法執(zhí)行效率高。

4 結(jié)束語

基于內(nèi)容的圖像搜索是下一代搜索引擎迫切需要解決的問題，本文對其主要功能和關(guān)鍵技術(shù)進行了分析和討論，設(shè)計并實現(xiàn)了一個基于灰度值分類的圖像搜索引擎。測試表明本圖像搜索引擎的總體性能穩(wěn)定，基本達到了預期的設(shè)計要求。

需要指出的是，搜索結(jié)果中有時會出現(xiàn)匹配度適中而內(nèi)容與上載圖片不一致的圖像。原因在于圖像匹配度是按照整幅圖像內(nèi)容而非僅僅是對圖像局部（如臉部）進行計算，這樣處理有時會造成圖像的語義誤差。因此，本搜索引擎在圖像識別算法方面還有待于進一步地研究和改進。

［1］何海地.互聯(lián)網(wǎng)搜索引擎變革給圖書館服務的啟示［J］.圖書館雜志'2013'32(10）:29-34.

［2］高瑞.百度、Google、Sogou三種圖像搜索引擎功能的比較［J］.中國科技信息'2010'41(18）:91-92.

［3］高云輝'劉春雙.搜索引擎技術(shù)在圖像檢索中的應用研究［J］.計算機光盤軟件與應用'2013(4）:123-125.

［4］呂志花.網(wǎng)絡(luò)信息挖掘及其在搜索引擎方面的應用［J］.微計算機信息'2008'2(3）:173-174.

［5］謝輝'陸月明.搜索引擎中基于內(nèi)容的圖像重排序［J］.計算機應用'2012'33(2）:460-462.

［6］吳文超'汪彥'舒會'等.有關(guān)內(nèi)容圖像搜索引擎技術(shù)的探索與實踐［J］.計算機與數(shù)字工程'2009'37 (10）:124-127.

［7］魏正曦.圖像閾值自動選取算法的C++實現(xiàn)［J］.四川理工學院學報:自然科學版'2010'23(4）:420-422.

［8］孫銳'閆曉星'丁志中.基于圖像正則化的抗幾何變換的感知哈希算法［J］.工程圖學學報'2010'31(2）: 116-122.

［9］梁金明'魏正曦.Ostu算法的改進研究［J］.四川理工學院學報:自然科學版'2010'23(5）:543-545.

［10］張敏'孫敏.基于Heritrix限定爬蟲的設(shè)計與實現(xiàn)［J］.計算機應用與軟件'2013'30(4）:33-35.

Image Search Engine Based on Grey-Classification

WEIZhengxi，QIU Ling，ZHAO Pan
（School of Computer Science，Sichuan University of Science&Engineering，Zigong 643000，China）

The image search is an urgent problem of the next generation of search engines.Themain functions and key technologies of the image search engine are analyzed and discussed in the article.Next，the main contents including task analysis，solutions，perception hash algorithm，aswell as implementationmethods and so on，are discussed.As a result，an image search engine based on gray-classification is designed.The tests show that the image search engine has very fast speed and stable performance，and basically achieves the desired design requirements.

image search engine；web crawler；image recognition；perception hash algorithm

TP391

A

1673-1549（2014）01-0037-04

10.11863/j.suse.2014.01.10

2013-06-07

人工智能四川省重點實驗室項目（2011RYY03）

魏正曦（1976-），男，四川自貢人，副教授，碩士，主要從事計算機應用方面的研究，（E-mail）413789256@qq.com