一種基于譜圖理論的Ｗｅｂ圖像搜索方法

摘要：在對(duì)當(dāng)前Web圖像搜索面臨的問(wèn)題進(jìn)行剖析的基礎(chǔ)上，根據(jù)譜圖理論的研究成果，提出了一種針對(duì)Web圖像搜索的新的解決方法。這種基于譜圖理論的方法極有可能是一種更有效的新型Web圖像信息分析方法，從而可以大幅提高現(xiàn)有基于鏈接的Web圖像搜索引擎的工作效率。

關(guān)鍵詞：譜圖理論；圖像搜索；信息處理

中圖分類(lèi)號(hào)：TP391．4文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)05-1598-03

0引言

隨著Web圖像信息的急劇膨脹，對(duì)這部分信息的搜索給傳統(tǒng)的搜索理論帶來(lái)了挑戰(zhàn)。圖像不同于文本，文本本身就可以說(shuō)明其內(nèi)容，而圖像則需要靠人們各自的理解來(lái)說(shuō)明其含義，因而圖像的搜索比起文本的搜索要困難得多，Web圖像搜索引擎的研究也成為互聯(lián)網(wǎng)搜索領(lǐng)域研究熱點(diǎn)。現(xiàn)有的Web圖像搜索引擎可分為兩大類(lèi)，即基于內(nèi)容的和基于鏈接的。除了都要利用相關(guān)的文本信息外，基于內(nèi)容的Web圖像搜索引擎主要根據(jù)圖像內(nèi)容（如顏色、紋理等）為圖像建立索引，而基于鏈接的Web圖像搜索引擎則主要根據(jù)頁(yè)面間的超鏈接來(lái)標(biāo)注圖像。基于鏈接的Web圖像搜索引擎使用文本搜索中普遍使用的HITS[1]或PAGERANK[2，3]等鏈接分析算法對(duì)圖像進(jìn)行分類(lèi)和標(biāo)注，在反映圖像的語(yǔ)義屬性方面具有一定的優(yōu)勢(shì)，而且由于這類(lèi)引擎不對(duì)圖像本身內(nèi)容進(jìn)行處理，系統(tǒng)開(kāi)銷(xiāo)也可以大大降低。對(duì)于基于鏈接的Web圖像搜索引擎的研究目前尚處于起步階段，針對(duì)如何將鏈接分析算法有效地應(yīng)用于Web圖像搜索有一些方案提出，并出現(xiàn)了一些對(duì)應(yīng)的Web圖像搜索引擎。然而，目前這些方案的效果均不夠理想，一方面是由于Web圖像搜索本身就是一個(gè)難度極大的工作；另一方面也可能是研究者尚未找到最適合Web圖像信息的數(shù)據(jù)分析方法。

1Web圖像搜索研究現(xiàn)狀

研究如何在圖像數(shù)據(jù)庫(kù)中檢索圖像由來(lái)已久，這方面比較成熟的技術(shù)是基于內(nèi)容的圖像檢索（CBIR），隨著互聯(lián)網(wǎng)上數(shù)字圖像的急劇增長(zhǎng)，如何對(duì)網(wǎng)頁(yè)上的圖像進(jìn)行檢索，即Web圖像搜索成為研究熱點(diǎn)。當(dāng)研究人員試圖將CBIR的技術(shù)直接運(yùn)用于Web圖像搜索時(shí)，卻遇到了一些難題。一方面，即使在離線(xiàn)檢索模式下（在線(xiàn)模式反應(yīng)時(shí)間過(guò)長(zhǎng)，一般不使用），圖像數(shù)據(jù)庫(kù)也是相當(dāng)龐大的，對(duì)圖像內(nèi)容的處理及分析開(kāi)銷(xiāo)將使系統(tǒng)難以承擔(dān)，同時(shí)在線(xiàn)等待的用戶(hù)不能容忍等得太久；另一方面，對(duì)于種類(lèi)繁多的Web圖像，用低層的圖像特征很難準(zhǔn)確表示圖像的語(yǔ)義屬性。因此，一些基于內(nèi)容的Web圖像搜索引擎，如WebSeer[4]、ImageRover[5]、WebSeek[6]等，在直接針對(duì)互聯(lián)網(wǎng)進(jìn)行Web圖像搜索時(shí)效果并不令人滿(mǎn)意。這類(lèi)搜索引擎采用了很多傳統(tǒng)圖像檢索系統(tǒng)（CBIR）中的技術(shù)，如特征提取、數(shù)據(jù)降維等，技術(shù)方法相對(duì)比較成熟，但由于上面提到的局限性，使其比較適合小范圍的Web圖像搜索（如特定網(wǎng)站內(nèi)的圖片搜索）。

與圖像數(shù)據(jù)庫(kù)中的圖像不同，Web圖像存在于網(wǎng)頁(yè)中，伴隨它的有許多附加信息，如圖像周?chē)奈淖帧D像的替換文本（alternate text，ALT）、圖像的URL等。這些信息對(duì)于表示圖像的語(yǔ)義屬性具有重要的作用。一些研究人員嘗試建立基于相關(guān)文本信息的Web圖像搜索引擎，如Lycos、Yahoo公司的Image Surfer等，但這種搜索方式面臨的一個(gè)問(wèn)題是用于判定的信息為極為有限的文本，檢索時(shí)將可能出現(xiàn)許多相關(guān)度相同的結(jié)果，對(duì)于結(jié)果的進(jìn)一步篩選就會(huì)遇到困難。為了解決這個(gè)問(wèn)題，一些研究人員將文本搜索中普遍使用的HITS或PAGERANK等鏈接分析算法引入到Web圖像搜索中，構(gòu)建出基于鏈接的Web圖像搜索引擎。HITS或PAGERANK等鏈接分析算法均基于兩個(gè)假設(shè)：a)頁(yè)面A如果有指向頁(yè)面B的鏈接則表明頁(yè)面A的作者認(rèn)為頁(yè)面B是有價(jià)值的，即頁(yè)面A的重要性可以通過(guò)它指向的頁(yè)面來(lái)衡量；b)被同一頁(yè)面指向的多個(gè)頁(yè)面可以被認(rèn)為屬于同一語(yǔ)義主題。在基于鏈接的Web圖像搜索引擎中，與Web圖像相關(guān)的鏈接（包括所在頁(yè)面間的鏈接、頁(yè)面區(qū)域間的鏈接等）分析將成為對(duì)其標(biāo)注和排序的關(guān)鍵信息。在此基礎(chǔ)上，再結(jié)合前面提到的相關(guān)文本信息，這些信息的綜合分析結(jié)果將表示圖像的語(yǔ)義屬性。鏈接分析算法用于文本搜索已經(jīng)被證明是有效的，但Web圖像的特點(diǎn)與文本相比差異較大，如何將鏈接分析算法有效地用于Web圖像搜索仍然有待進(jìn)一步研究。基于鏈接的Web圖像搜索引擎的研究尚處于起步階段，目前比較典型的例子是PicASHOW[7]。

2基于譜圖理論的學(xué)習(xí)算法簡(jiǎn)介

譜圖理論是微分幾何領(lǐng)域的一個(gè)分支理論，最早關(guān)于這方面的研究可以追溯到古希臘時(shí)期的等周問(wèn)題（isoperimetric problems），但它作為一個(gè)相對(duì)獨(dú)立的理論是1997年由Fan Chung提出的[8]。該理論通過(guò)研究根據(jù)圖定義的矩陣的譜，進(jìn)一步研究圖中包含的信息，最后通過(guò)微分幾何、矩陣分析及線(xiàn)性代數(shù)等方法在離散空間與連續(xù)空間之間建立聯(lián)系。基于該理論的一些學(xué)習(xí)算法最近在機(jī)器學(xué)習(xí)、數(shù)據(jù)降維、智能信息處理等領(lǐng)域得到了較多的關(guān)注。其中比較經(jīng)典的算法包括LLE、Isomap、Laplacian Eigenmap等。這些算法的主要思想均是首先將離散的數(shù)據(jù)集設(shè)法表示為圖的形式，然后用譜圖分析的方法處理這些圖的結(jié)構(gòu)，最后將數(shù)據(jù)轉(zhuǎn)換到連續(xù)空間從而完成數(shù)據(jù)的學(xué)習(xí)。通過(guò)進(jìn)一步的研究，發(fā)現(xiàn)這些算法在圖像檢索、文字識(shí)別、人臉識(shí)別、數(shù)據(jù)可視化等具體應(yīng)用上表現(xiàn)出了比傳統(tǒng)學(xué)習(xí)算法更佳的效果，國(guó)際上關(guān)于這方面的研究已經(jīng)成為機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)研究熱點(diǎn)，而國(guó)內(nèi)的周志華、王玨等學(xué)者也在這方面作了一些有益的研究[9，10]。作者近年來(lái)針對(duì)Laplacian Eigenmap算法的線(xiàn)性?xún)?yōu)化及在圖像檢索中的應(yīng)用作了一些有意義的研究，比較有代表性的成果是在結(jié)合相關(guān)反饋技術(shù)的基礎(chǔ)上，提出了用于圖像檢索的FLPP算法[11]。該算法在用于基于內(nèi)容的圖像檢索時(shí)能明顯提高檢索的準(zhǔn)確度。

基于譜圖理論的學(xué)習(xí)算法在某些應(yīng)用領(lǐng)域已經(jīng)表現(xiàn)出了優(yōu)異的性能，而基于鏈接的Web圖像搜索中最關(guān)鍵的工作就是根據(jù)鏈接、相關(guān)文本等信息對(duì)數(shù)量龐大的Web圖像數(shù)據(jù)進(jìn)行分類(lèi)和標(biāo)注，從本質(zhì)上可以說(shuō)是一個(gè)機(jī)器學(xué)習(xí)問(wèn)題，而且，一些權(quán)威研究[12]也表明Web從數(shù)學(xué)上更適合表示為圖的形式。因而，如果根據(jù)譜圖理論的研究成果，設(shè)計(jì)出適用于基于鏈接的Web圖像搜索的排序及聚類(lèi)算法，并在此基礎(chǔ)上構(gòu)建Web圖像搜索引擎將是一項(xiàng)具有較大理論意義和應(yīng)用前景的開(kāi)拓性工作。

3基于譜圖理論構(gòu)建Web圖像搜索引擎

基于譜圖理論的學(xué)習(xí)算法研究已經(jīng)取得了一些有意義的成果。基于這些研究成果，本文提出了一種基于基于譜圖理論構(gòu)建Web圖像搜索引擎的方案。該方案的要點(diǎn)如下：

a）在離線(xiàn)狀態(tài)根據(jù)包括頁(yè)面間鏈接、用戶(hù)日志等信息將海量的Web圖像構(gòu)建成一個(gè)Web圖像結(jié)構(gòu)圖；

b)設(shè)計(jì)基于譜圖理論可以分析海量數(shù)據(jù)的學(xué)習(xí)算法，有效地對(duì)Web圖像結(jié)構(gòu)圖進(jìn)行處理分類(lèi)；

c)設(shè)計(jì)基于譜圖理論的相關(guān)反饋算法，將用戶(hù)反饋用于調(diào)整Web圖像結(jié)構(gòu)圖的權(quán)重，從而在用戶(hù)搜索時(shí)返回最佳結(jié)果；

d)利用Web圖像結(jié)構(gòu)圖便于實(shí)現(xiàn)語(yǔ)義聚類(lèi)的優(yōu)勢(shì)，實(shí)現(xiàn)返回結(jié)果的聚類(lèi)顯示。

要真正實(shí)現(xiàn)上述方案具有較高的難度，盡管已經(jīng)有一些關(guān)于譜圖理論學(xué)習(xí)算法的研究作為基礎(chǔ)，但完全基于譜圖理論構(gòu)建Web圖像搜索引擎的研究尚處于探索階段，要取得實(shí)質(zhì)的進(jìn)展，筆者認(rèn)為尚有如下幾個(gè)關(guān)鍵問(wèn)題有待研究：

a）高維空間的最近鄰搜索問(wèn)題。到目前為止，這仍然是一個(gè)國(guó)際性的難題，但是這個(gè)問(wèn)題對(duì)于圖像搜索有著直接的關(guān)鍵性的影響。當(dāng)進(jìn)行基于譜圖的Web圖像搜索時(shí)，Web圖像將被表示為一個(gè)點(diǎn)，由于與Web 圖像相關(guān)的鏈接、用戶(hù)日志及文本等其他信息量很大，數(shù)據(jù)點(diǎn)的維度將可能達(dá)到好幾百，甚至上千。根據(jù)目前的研究現(xiàn)狀，最好的高維空間最近鄰搜索算法能處理的維度一般都是小于100的，因此，傳統(tǒng)的高維空間最近鄰搜索算法將不能直接應(yīng)用于Web圖像搜索。可以從兩個(gè)途徑嘗試解決這個(gè)問(wèn)題：（a）提出新的高維空間最近鄰搜索算法，使其能夠處理高達(dá)幾百維的數(shù)據(jù)；(b)直接應(yīng)用成熟的基于譜圖的數(shù)據(jù)分析算法，降低數(shù)據(jù)的維度，然后再進(jìn)行搜索。

國(guó)際上對(duì)于利用成熟譜圖分析算法進(jìn)行劇烈數(shù)據(jù)降維已經(jīng)有了一些有意義的研究，因此按上面提出的第二個(gè)途徑解決該問(wèn)題把握較大，但這種途徑的缺點(diǎn)是會(huì)產(chǎn)生一定的計(jì)算開(kāi)銷(xiāo)，雖然這些計(jì)算可以在離線(xiàn)狀態(tài)進(jìn)行，但對(duì)于任務(wù)繁重的Web圖像搜索系統(tǒng)仍有一定影響。如果按上面提出的第一個(gè)途徑解決該問(wèn)題，雖然國(guó)際上這方面的相關(guān)研究很少，但如果能取得進(jìn)展，將不會(huì)有額外計(jì)算開(kāi)銷(xiāo)的產(chǎn)生，從而將為Web圖像搜索中的高維數(shù)據(jù)搜索問(wèn)題找到更佳的方法。

b）如何構(gòu)建Web圖像結(jié)構(gòu)圖。目前基于鏈接的Web圖像搜索引擎（如PicASHOW[7]）一般都是直接利用Google等文本搜索引擎中得到成熟應(yīng)用的PageRank、HITS等鏈接分析算法來(lái)分析圖像所在頁(yè)面間的鏈接，再結(jié)合相關(guān)的文本信息，從而標(biāo)定圖像的語(yǔ)義屬性。該方法的缺陷：(a）PageRank、HITS等鏈接分析算法并不直接適用于Web圖像搜索，因?yàn)閳D像的含義本身就比較復(fù)雜，單純用文本或相關(guān)度評(píng)分過(guò)于簡(jiǎn)單，并不能準(zhǔn)確標(biāo)定Web圖像的語(yǔ)義屬性；（b）不適合檢索結(jié)果的聚類(lèi)處理。為了解決這些問(wèn)題，借鑒譜圖理論的一些研究成果，可以嘗試?yán)肳eb圖像的鏈接信息， Web圖像周?chē)奈淖中畔ⅲ╯urrounding text）以及用戶(hù)日志（user logs）等信息建立Web圖像結(jié)構(gòu)圖。根據(jù)譜圖理論，Web圖像結(jié)構(gòu)圖應(yīng)按權(quán)圖形式構(gòu)建，圖像作為圖中的節(jié)點(diǎn)，與圖像相關(guān)的頁(yè)面間鏈接以及文本信息均由節(jié)點(diǎn)間的權(quán)來(lái)體現(xiàn)。

雖然上面對(duì)于如何構(gòu)建Web圖像結(jié)構(gòu)圖有了初步的方案，但具體的權(quán)圖構(gòu)建方法，包括各種因素的比重如何確定等細(xì)節(jié)問(wèn)題將是本項(xiàng)目研究的關(guān)鍵問(wèn)題之一，尚有待于后續(xù)研究中通過(guò)大量的實(shí)驗(yàn)分析確定。當(dāng)Web圖像結(jié)構(gòu)圖建立后，就可以利用譜圖分析的方法來(lái)處理該結(jié)構(gòu)圖，從而最終標(biāo)定Web圖像的語(yǔ)義屬性。

c）設(shè)計(jì)有效的基于譜圖理論的Web圖像排序算法。傳統(tǒng)的文本搜索引擎和現(xiàn)有的基于鏈接的Web圖像搜索引擎均用相似性度量來(lái)標(biāo)定頁(yè)面屬性后再實(shí)現(xiàn)搜索結(jié)果的排序。應(yīng)用譜圖理論進(jìn)行排序與傳統(tǒng)方法中直接用相似性度量的最大區(qū)別是：基于譜圖的排序是在整個(gè)圖（graph）上同時(shí)進(jìn)行的，而相似性度量則可以分別對(duì)每一個(gè)對(duì)象處理。用相似性度量進(jìn)行排序的最大優(yōu)點(diǎn)是排序的計(jì)算開(kāi)銷(xiāo)極小，缺點(diǎn)是用于圖像排序時(shí)過(guò)于簡(jiǎn)單，難以表示圖像間復(fù)雜的語(yǔ)義關(guān)系；而基于譜圖進(jìn)行排序的最大優(yōu)點(diǎn)是按譜圖理論構(gòu)建的Web圖像結(jié)構(gòu)圖可以較好地表示圖像間復(fù)雜的語(yǔ)義關(guān)系，但缺點(diǎn)是通過(guò)譜圖進(jìn)行排序?qū)a(chǎn)生一定的時(shí)間（計(jì)算）及空間（數(shù)據(jù)存儲(chǔ)）開(kāi)銷(xiāo)。因此，設(shè)計(jì)基于譜圖的排序算法時(shí)的關(guān)鍵是如何降低算法的時(shí)間和空間復(fù)雜度，以適應(yīng)Web環(huán)境中的大規(guī)模計(jì)算，這也是本方案需要解決的關(guān)鍵問(wèn)題之一。目前國(guó)際上對(duì)于譜圖排序的一些研究已經(jīng)表明，基于譜圖進(jìn)行排序在某些應(yīng)用領(lǐng)域具有更佳的效果，這方面比較有代表性的成果參見(jiàn)文獻(xiàn)[13]。本方案也以此為基礎(chǔ)，再結(jié)合作者研究基于譜圖理論的傳統(tǒng)圖像檢索系統(tǒng)時(shí)一些成果[11]，從而設(shè)計(jì)出適合Web圖像搜索的排序算法。

d）如何實(shí)現(xiàn)Web圖像搜索結(jié)果的聚類(lèi)。基于相似性度量的搜索方法很難直接實(shí)現(xiàn)返回結(jié)果的聚類(lèi)顯示，但基于譜圖的搜索方法在這方面卻很容易實(shí)現(xiàn)，這是因?yàn)楦鶕?jù)譜圖中數(shù)據(jù)點(diǎn)的幾何分布很容易直接進(jìn)行相對(duì)準(zhǔn)確的聚類(lèi)劃分。目前基于譜圖的聚類(lèi)算法很多，比較有代表的算法是斯坦福大學(xué)A. Ng等人提出的譜圖聚類(lèi)算法[14]和賓夕發(fā)尼亞大學(xué)J. Shi等人提出的Normalized Cut算法[15]。在對(duì)現(xiàn)有譜圖聚類(lèi)算法進(jìn)行深入分析的基礎(chǔ)上，針對(duì)Web圖像搜索結(jié)果返回的一些特點(diǎn)（如聚類(lèi)區(qū)別非常明顯、用戶(hù)反饋可以提供指導(dǎo)作用、系統(tǒng)計(jì)算負(fù)荷大等），找到一種適合Web圖像搜索的譜圖聚類(lèi)算法也將是本方案需要解決的一個(gè)關(guān)鍵問(wèn)題。對(duì)于該問(wèn)題，筆者注意到基于譜圖的排序和聚類(lèi)在數(shù)學(xué)原理上是一致的。如果通過(guò)使用一些數(shù)學(xué)技巧同時(shí)得到排序和聚類(lèi)結(jié)果，就使得聚類(lèi)算法與前面提到的譜圖排序算法在某種程度上結(jié)合起來(lái)，從而大大降低系統(tǒng)的計(jì)算開(kāi)銷(xiāo)。

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

基于鏈接的Web圖像搜索引擎使用文本搜索中普遍使用的HITS或PAGERANK等鏈接分析算法對(duì)圖像進(jìn)行分類(lèi)和標(biāo)注，在表達(dá)圖像的語(yǔ)義屬性方面具有一定的優(yōu)勢(shì)。對(duì)于基于鏈接的Web圖像搜索引擎的研究目前尚處于起步階段，針對(duì)如何將鏈接分析算法有效地應(yīng)用于Web圖像搜索有一些方案提出，并出現(xiàn)了一些對(duì)應(yīng)的Web圖像搜索引擎。然而，目前這些方案的效果均不夠理想。

本文在對(duì)當(dāng)前Web圖像搜索面臨的問(wèn)題進(jìn)行剖析的基礎(chǔ)上，根據(jù)譜圖理論的研究成果，提出了一種針對(duì)Web圖像搜索的新的解決方案，這種基于譜圖理論的方法極有可能是一種更有效的新型Web圖像信息分析方法，從而可以大幅提高現(xiàn)有基于鏈接的Web圖像搜索引擎的工作效率。

參考文獻(xiàn)：

［1］KLEINBERG J.Authoritative sources in a hyperlinked environment[C]//Proc of the 9th ACM－SIAM Symposium on Discrete Algorithms.1998.

[2]BRIN S，PAGE L.The anatomy of a large－scale hypertextual (Web) search engine[C]//Proc of the 7th International World Wide Web Conference.1998.

[3]HAVELIWALA T H.Topic－sensitive pagerank[C]//Proc of the 11th International World Wide Web Conference.Hawaii:[s.n.]，2002.

[4]FRANKEL C，SWAIN M，ATHITSOS V.WebSeer:an image search engine for the World Wide Web[R].Chicago:Department of Compu-ter Science， University of Chicago，1996.

[5]SCLAROFF S，TAYCHER L，CASCIA M L.ImageRover: a content－based image browser for the World Wide Web[C]//Proc of IEEE Workshop on Content－based Access of Image and Video Libraries.San Juan， Puerto Rico:[s.n.]，1994.

[6]SMITH J，CHANG S F.Visually searching the Web for content[J].IEEE Multimedia Magazine，1997，4(3):12-20.

[7]LEMPEL R，SOFFER A.PicASHOW:Pictorial authority search by hyperlinks on the Web[C]//Proc of the 10th Int World Wide Web Conference.San Juan， Puerto Rico:[s.n.]，1994:2－9.

[8]CHUNG F.Spectral graph theory[M].Providence:American Mathematical Society，1997.

[9]何力，張軍平，周志華.基于放大因子和延伸方向研究流形學(xué)習(xí)算法[J].計(jì)算機(jī)學(xué)報(bào)，2005，28(12):2000-2009.

[10]楊劍，李伏欣，王玨.一種改進(jìn)的局部切空間排列算法[J].軟件學(xué)報(bào)， 2005，16(9):1584－1590.

[11]LU K，HE X.Image retrieval based on incremental subspace learning[J].Pattern Recognition，2005，38(11): 2047-2054.

[12]KLEINBERG J，LAWRENCE S.The structure of the Web[J].Scien－ce，2001，294:1849－1850.

[13]ZHOU Deng－yong，WESTON J，GRETTON A，et al. Ranking on data manifolds[C]//Proc of Advances in Neural Information Processing Systems.[S.l.]:MIT Press， 2003.

[14]NG A，JORDAN M，WEISS Y.On spectral clustering:analysis and an algorithm[C]//Proc of Advances in Neural Information Processing Systems.2001.

[15]SHI J，MALIK J.Normalized cuts and image segmentation[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2000，22(8):888-905.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”