【導(dǎo)讀】搜索引擎為目標(biāo)，提出基于文本檢索方式的Web圖片搜索引擎設(shè)計(jì)方案。提出的系統(tǒng)設(shè)計(jì)方案中。在對(duì)真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)和分析的基礎(chǔ)上，提出了若干關(guān)鍵技術(shù)，圖片相關(guān)的信息，以保證提取到的信息相關(guān)性程度較高。2)提出了過(guò)濾無(wú)用圖片的方法，提高了系統(tǒng)中圖片的可用度。引用次數(shù)高的圖片需要經(jīng)過(guò)過(guò)濾才能保證重要性較高。使用效果和性能進(jìn)行了簡(jiǎn)單評(píng)測(cè)。

　　

【正文】 同義性問(wèn)題，但多義性問(wèn)題依然無(wú)法得到較好的解決。更糟糕的是，對(duì)于通用搜索引擎這樣的領(lǐng)域無(wú)關(guān)系統(tǒng)，根本無(wú)法建立知識(shí)庫(kù)。 針對(duì)以上問(wèn)題， Deerwester 等人提出了 LSI 模型（ Latent Semantic Indexing，潛在語(yǔ)義索引） [12][13]。該模型不試圖利用任何外部知識(shí)，而是從挖掘文檔集本身的潛在信息入手，利用統(tǒng)計(jì)分析方法來(lái)構(gòu)造語(yǔ)義空間結(jié)構(gòu)，自動(dòng)發(fā)現(xiàn)文檔之間的潛在語(yǔ)義關(guān)系。 LSI 模型是對(duì)于 VSM 模型的一種改良，已經(jīng)被證明在很多應(yīng)用中具有顯著的改進(jìn)效果，能夠 在很大程度上彌補(bǔ) VSM 的不足。 LSI 模型基于一點(diǎn)假設(shè)：在文檔集中協(xié)同出現(xiàn)（ Cooccurrence）的詞之間具學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 14 有相關(guān)性，協(xié)同出現(xiàn)的頻率越高則相關(guān)性越強(qiáng)。例如，如果在大量的文檔中同時(shí)出現(xiàn)“ Linux”和“ GNU”，則可以認(rèn)為這兩個(gè)詞之間具有較強(qiáng)的相關(guān)性。 LSI 通過(guò)統(tǒng)計(jì)方法，對(duì)大規(guī)模的文檔集合構(gòu)造對(duì)應(yīng)的矩陣，并通過(guò) SVD（ Singular Value Deposition，奇異值分解）和降維處理，來(lái)將文檔和詞的關(guān)系映射到相似的低維的語(yǔ)義空間中。此時(shí)的語(yǔ)義空間揭示了詞與詞之間，文檔與文檔之間，文檔與詞 之間的潛在相似度關(guān)系，提供相當(dāng)豐富的信息。 下面簡(jiǎn)要的介紹 LSI 模型的計(jì)算方法。 首先需要建立矩陣 X=T D，矩陣的行代表詞，列代表文檔，矩陣的單元代表詞在文檔中的權(quán)值。該權(quán)值的計(jì)算有很多種方法，最簡(jiǎn)單的就是詞在文檔中出現(xiàn)的頻率。另外的一些計(jì)算方法有絕對(duì)詞頻加權(quán)法、平均詞頻加權(quán)法、相對(duì)頻率加權(quán)法、逆文檔頻率加權(quán)法以及多種加權(quán)法的綜合運(yùn)用。 然后是對(duì)詞頻矩陣 X 進(jìn)行奇異值分解（ SVD），得到如下形式的三個(gè)矩陣的乘積： 000 DSTX ???? 其中， ),( 210 nd i a gS ??? ?? 為奇異值的對(duì)角矩陣，并且有n??? ??? ?21 ， T0和 D0ˊ 是正交矩陣，即： EDDTT ???? 0000 數(shù)學(xué)上可以證明，任意的矩陣總是能夠進(jìn)行這樣的分解。 接下來(lái)是對(duì) S0矩陣進(jìn)行降維。選定一個(gè) K 值，保留 S0矩陣的對(duì)角線上的前K 個(gè)最大的 σ，而將其余的替換為 0。 用降維以后的 S0ˊ 代替原來(lái)的 S0，重新計(jì)算得到新的 Xˊ 矩陣的值。 此時(shí)的 Xˊ矩陣是原來(lái)的 X 的一個(gè)近似，重要的是語(yǔ)義結(jié)構(gòu)已經(jīng)被映射到低維空間中，并且消除了語(yǔ)義上的細(xì)微差別而保留了重要的潛在語(yǔ)義關(guān)系。此時(shí)文檔和詞之間的相關(guān)性度量被直觀的表示為 Xˊ 矩陣中文檔與詞對(duì)應(yīng)的單元上的值。 K 值的選取是很重要的，太大會(huì)導(dǎo)致結(jié)果趨近于原始矩陣而失去挖掘潛在語(yǔ)義的能力，太小則會(huì)使得語(yǔ)義信息丟失太多，以至于對(duì)于文檔和詞的分辨能力不足。 實(shí)際上， LSI 的應(yīng)用遠(yuǎn)不止于相關(guān)性排序。在不同的應(yīng)用環(huán)境當(dāng)中，對(duì)矩陣的構(gòu)造方法進(jìn)行一些變化，能夠衍生出很多 LSI 的用途。由于能夠通過(guò)統(tǒng)計(jì)來(lái)挖掘大量的相關(guān)性這一特點(diǎn)， LSI 被廣泛的應(yīng)用到了包括文本檢索、文本分類(lèi)、信息過(guò)濾、文本摘要、雙語(yǔ)交叉過(guò)濾、垃圾郵件過(guò)濾、個(gè)性化服務(wù)、智能檢索等在內(nèi)的廣闊的領(lǐng) 域中。 在圖片搜索引擎中，圖片本身能夠提取到的信息是有限的，主要是由于兩點(diǎn)原因： 1）本身可供提取的信息比較少； 2）即使是可以提取大量的信息，考慮到相關(guān)性低的問(wèn)題，往往也只保留很少的一部分。 學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 15 因?yàn)樵~對(duì)于文檔的權(quán)值是反映詞對(duì)于文檔的重要性，對(duì)于不同的應(yīng)用，應(yīng)該判斷哪些詞對(duì)于文檔意義的貢獻(xiàn)更大，從而賦予更高的權(quán)值。所以，在圖片搜索中構(gòu)造 LSI 初始矩陣的方法也需要一些變化，不應(yīng)該單純使用詞頻方法作為詞在文檔中權(quán)值的計(jì)算準(zhǔn)則，可以通過(guò)綜合考慮詞的來(lái)源等信息加以確定。 圖片本身除了可以有文字信息之外，還有自身固有的可視 化特征，通過(guò)建立一個(gè)統(tǒng)一的關(guān)于特征的向量表示以后，可以利用 LSI 方法在多種特征之間建立起語(yǔ)義關(guān)系，比如文字和可視化特征的關(guān)系，從而能夠獲得更直觀意義上的圖片、文字和可視化特征之間的相互關(guān)系。相關(guān)的內(nèi)容將在 節(jié)中進(jìn)一步闡述。 信息提取技術(shù) 上文提到， Web 圖片搜索引擎中圖片的信息提取有兩種主要方式：基于內(nèi)容的提取和基于文本的提取。 基于內(nèi)容的提取通過(guò)分析圖片本身的二進(jìn)制內(nèi)容（像素），提取出其中的一些可視化特征，并對(duì)這些特征建立索引，在提供檢索時(shí)，通過(guò) 與檢索示例圖片的同類(lèi)特征進(jìn)行比較來(lái)度量圖片之間的相似性，并返回相似度最高的圖片。 基于文本的信息提取并不試圖分析圖片本身的內(nèi)容，而是盡力提取與圖片相關(guān)的文字信息，以這些文字作為圖片內(nèi)容的表征。獲得文字信息之后， 可以利用傳統(tǒng)的文本信息檢索的相關(guān)技術(shù)來(lái)提供信息的組織和查詢(xún)。 下面簡(jiǎn)要介紹一些基于內(nèi)容和基于文本的信息提取技術(shù)，并進(jìn)行簡(jiǎn)要的分析。 基于內(nèi)容的提取技術(shù) 基于內(nèi)容的圖片檢索技術(shù)分析的對(duì)象是圖片本身的二進(jìn)制數(shù)據(jù)，該技術(shù)試圖通過(guò)分析數(shù)據(jù)，從中發(fā)現(xiàn)可視化信息，并利用匹配技術(shù)得到相似的圖片。 和文本檢索一樣， 基于效率上的考慮，不可能在檢索的時(shí)候才去分析圖片的內(nèi)容，而必須對(duì)待檢索的圖片集進(jìn)行預(yù)處理，主要是提取其中的可視化信息，利用多維索引技術(shù)建立索引，從而使得檢索的時(shí)候只需要利用某種匹配算法在索引中查找即可。 可視化特征提取是基于內(nèi)容的圖片檢索的基礎(chǔ)，按照應(yīng)用范圍可以分為特定領(lǐng)域的特征提取和通用特征提取。前者是應(yīng)用相關(guān)的，涉及到知識(shí)庫(kù)，比如對(duì)于人臉的識(shí)別，這方面的技術(shù)在模式識(shí)別領(lǐng)域中討論的比較多；后者是獨(dú)立于應(yīng)用的，所以適用范圍要廣得多，他僅僅提取一些很基本（但重要）的可視特征，并不要求對(duì)這些特征進(jìn)行識(shí)別，這一點(diǎn) 對(duì)于基于內(nèi)容相似匹配的圖片檢索已經(jīng)足夠了。這里重點(diǎn)介紹通用特征提取方式。 由于人們對(duì)于圖片的觀察是很主觀的過(guò)程，往往存在不同的視角，并沒(méi)有一學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 16 個(gè)唯一的標(biāo)準(zhǔn)來(lái)定義什么是最佳（最精確）的可視化特征。所以，在進(jìn)行特征提取的時(shí)候，通常也是從多個(gè)不同的角度去考慮，從而形成了多種可視化特征對(duì)象。經(jīng)常被用于分析的特征有顏色（ color）、紋理（ texture）和形狀（ shape）。 ? 顏色 顏色是最常被用于基于內(nèi)容的圖片檢索的可視化特征之一。顏色提取的優(yōu)點(diǎn)在于對(duì)圖片的大小和方向不敏感，并且對(duì)于處理各種背景復(fù)雜的圖片時(shí)效果比 較穩(wěn)定，同時(shí)，顏色是也描述圖片的最簡(jiǎn)單的特征。 顏色直方圖是最常被用于顏色特征表達(dá)的方法，它從統(tǒng)計(jì)意義上表示了三種顏色通道的強(qiáng)度的關(guān)聯(lián)概率。 Swain 等人提出了顏色索引方法，利用顏色直方圖的交和反投影來(lái)度量圖片之間的相似性 [20][40]。 在進(jìn)行顏色直方圖生成時(shí)，顏色系統(tǒng)（ color system）的選取是一個(gè)很重要的問(wèn)題。 RGB 是使用最廣泛的顏色系統(tǒng)，它表現(xiàn)了本原的顏色屬性，但是沒(méi)有考慮人眼視 覺(jué)觀察的一些特點(diǎn)（比如人眼對(duì)于不同顏色差別的敏感程度是不一樣的），對(duì)于某些應(yīng)用并不是最佳選擇。另外的一些顏色系統(tǒng)，比如 U*V*W、 L*a*b、L*u*v 等，充分考慮了人眼對(duì)于顏色感知上的特點(diǎn)，因此適合用于圖片檢索這類(lèi)需要滿(mǎn)足人眼視覺(jué)要求的系統(tǒng)中 [25]。為了克服顏色空間信息丟失的缺點(diǎn)，之后的很多改進(jìn)模型被提出來(lái) [41]。 ? 形狀 形狀也是圖片中的一個(gè)重要的可視化特征，是人類(lèi)認(rèn)知自然對(duì)象的最基本特征。 形狀特征的描述通常有兩種常用的方式：基于邊界的描述和基于區(qū)域的描述。 基于邊界的描述方式中使用最多的是傅立葉描述子（ Fourier Descriptor）。該方法只考慮圖片中對(duì)象的外層邊界，并對(duì)邊界進(jìn)行傅立葉變換，作為對(duì)象的形狀特征。為了消除數(shù)字化噪音的影響， Rui 提出了改進(jìn)的傅立葉描述子方法 [20]，該方法同時(shí)對(duì)于形狀的幾何變換具有很好的魯棒性。基于區(qū)域的描述方法中常用的方法是不變矩（ Moment Invariant），其對(duì)于形狀的變換來(lái)說(shuō)是恒定的。 Hu 提出了 7 種不同的矩 [20]，后來(lái)有人提出來(lái)改進(jìn)的計(jì)算方法 [20]，有效的提高了計(jì)算的效率。 在實(shí)際應(yīng)用中需要考慮時(shí)間和空間效率的因素，往往采用更簡(jiǎn)單的形狀描述和檢索方法，比如形狀參數(shù)（ Shape Factor） [40]，考察面積，周長(zhǎng)等參數(shù)，在實(shí)際中得到較好的應(yīng)用。 ? 紋理 紋理也是圖像的一個(gè)重要特征，其描述了對(duì)象表面的像素分布規(guī)律。描述紋理的主要的方法有結(jié)構(gòu)方法，統(tǒng)計(jì)方法和頻譜分析方法 [40]。結(jié)構(gòu)方法主要針對(duì)有規(guī)律的紋理結(jié)構(gòu)，利用句法分析方法來(lái)進(jìn)行識(shí)別。統(tǒng)計(jì)方法通過(guò)對(duì)像素的分布進(jìn)行統(tǒng)計(jì)，發(fā)現(xiàn)其中的分布規(guī)律。頻譜分析方法主要是利用小波變換來(lái)生成紋理特征，實(shí)踐證明是效果比較好的紋理識(shí)別方法 [41]。 學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 17 基于內(nèi)容的圖片分析中還有一種比較特殊的應(yīng)用，用于發(fā)現(xiàn)圖片中包含的文本。目前有很多的圖片，文字被嵌入到了其中，通過(guò)圖片的像素表現(xiàn)出來(lái)。這 種信息對(duì)于人們理解來(lái)說(shuō)輕而易舉，但是由于其丟失了文字本身的信息，對(duì)于機(jī)器理解還有很大的難度。 目前在模式識(shí)別領(lǐng)域有很多的關(guān)于識(shí)別圖片中文本的研究。 Zhou[32]等提出了一種文本識(shí)別算法，利用 color clustering 和 connected ponent analysis 方法將輸入圖片的顏色空間經(jīng)過(guò)預(yù)處理量化為一系列的顏色類(lèi)，然后標(biāo)示出每一個(gè)顏色類(lèi)中類(lèi)似文本的連接成分，最后將這些連接成分通過(guò)后繼處理轉(zhuǎn)化為文本。該方法的難度在于圖片中的文字可以 是任意的顏色，并且有些圖片的文字背景圖案由各種不同顏色的對(duì)象構(gòu)成，難于將其識(shí)別為獨(dú)立的成分。 .基于內(nèi)容的檢索技術(shù)有基于文本所不具有的特點(diǎn)，其一大優(yōu)勢(shì)在于它分析圖片文件本身包含的信息，可以不依賴(lài)于圖片的來(lái)源。這樣帶來(lái)的一個(gè)非常顯著的好處是，我們收集的可用于檢索的圖片的領(lǐng)域?qū)?huì)變得廣闊得多。我們不僅可以利用 Web 中無(wú)法提取文字信息的圖片，還可以到 ftp 等其他形式的并不包含有充分的文字信息的網(wǎng)絡(luò)資源中去獲取圖片。 另一個(gè)潛在的優(yōu)勢(shì)是，分析圖片內(nèi)容本身來(lái)探究其包含的意義符合固有的人類(lèi)理解圖片的方式，隨著計(jì)算機(jī)視覺(jué) 和人工智能等技術(shù)的不斷發(fā)展，圖片分析技術(shù)將會(huì)不斷接近于人類(lèi)的視覺(jué)認(rèn)知水平。 基于文本的提取技術(shù) 基于文本的提取技術(shù)通過(guò)分析 Web 上的資源，來(lái)獲取圖片的相關(guān)文字信息。HTML 文檔能夠?qū)⑽淖趾蛨D片組織在一起，提供了非常豐富的信息，因此成為我們提取信息的主要資源。通過(guò)分析 HTML 中的標(biāo)記，可以利用一系列啟發(fā)式規(guī)則來(lái)獲得相關(guān)的圖片和文字。在這里，啟發(fā)式規(guī)則的選擇是相當(dāng)重要的，它將直接影響到系統(tǒng)的查準(zhǔn)率，同時(shí)也在很大程度上影響著系統(tǒng)的查全率。 其它類(lèi)型的資源，比如 FTP，從中基本上只能得到路徑和文件名信息，而且這些信 息常常是無(wú)關(guān)的，因此基本上無(wú)法用于圖片的文字信息提取。 本文中，我們提出了利用 HTML來(lái)獲得圖片信息的一些方法以及對(duì)于 HTML的一些潛在意義的分析，詳細(xì)的內(nèi)容在 第 3 章 闡述。 信息索引技術(shù) 當(dāng)信息量較小時(shí)，往往可以通過(guò)遍歷所有的信息來(lái)查找到相關(guān)的信息，類(lèi)似于 SQL 語(yǔ)言中的 LIKE 檢索方式。這種方案實(shí)現(xiàn)簡(jiǎn)單，順序掃描信息進(jìn)行字符串匹配即可。但是當(dāng)信息量增加到一定程度以后，利用這種遍歷所有數(shù)據(jù)的方式是相當(dāng)?shù)托У?。這時(shí)，需要使用某種索引技術(shù)來(lái)改變這種檢索方式。 學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 18 用于海量文本數(shù)據(jù)庫(kù)（ Text Database）建立索引的方式主要有簽名文件和倒排文件 [18]。以下簡(jiǎn)單的介紹兩種技術(shù)的基本原理。 索引方式 簽名文件 簽名文件的本質(zhì)是將文檔利用簽名來(lái)表示，以此來(lái)減少查詢(xún)時(shí)需要訪問(wèn)的數(shù)據(jù)，查詢(xún)的本質(zhì)還是遍歷和匹配。最簡(jiǎn)單的簽名文件是對(duì)文檔中每個(gè)出現(xiàn)的詞項(xiàng)利用特定的 Hash 函數(shù)進(jìn)行簽名，得到固定長(zhǎng)度的位串（通常為了減小簽名文件的大小，位串的長(zhǎng)度比較?。?。將各個(gè)位串順序的存儲(chǔ)在一起，用來(lái)表示該文檔。 當(dāng)進(jìn)行查詢(xún)時(shí)，將查詢(xún) 詞利用相同的 Hash 函數(shù)進(jìn)行簽名，利用簽名產(chǎn)生的位串在簽名文件中進(jìn)行遍歷查詢(xún)，可以得到一個(gè)匹配的結(jié)果文檔列表。需要注意的是：由于位串長(zhǎng)度選取的比較小，可能會(huì)出現(xiàn)兩個(gè)詞項(xiàng)的簽名相同的情況（實(shí)際上經(jīng)常如此），因此并非所有簽名匹配的文檔都是符合結(jié)果的文檔（包含查詢(xún)?cè)~）。所以需要對(duì)結(jié)果文檔進(jìn)行驗(yàn)證是否實(shí)際包含了檢索詞。 通常直接儲(chǔ)存每個(gè)詞項(xiàng)的簽名的文件尺寸還是比較大，所以很多種壓縮技術(shù)被應(yīng)用到其中，比如： Logic Blocked 壓縮方法 [18]。 由于簽名文 件本質(zhì)上還是掃描文檔，所以盡管其在很多方面不斷進(jìn)行改進(jìn)，但對(duì)于海量數(shù)據(jù)的應(yīng)用，表現(xiàn)依然不夠理想。 倒排文件 搜索引擎中使用最廣泛的索引技術(shù)就是倒排文件。倒排文件包含一個(gè)查詢(xún)項(xiàng)到查詢(xún)主體的映射結(jié)構(gòu)，其優(yōu)勢(shì)在于映射結(jié)構(gòu)可以預(yù)先建立并存儲(chǔ)，而在查詢(xún)時(shí)可以通過(guò)映射結(jié)構(gòu)直接獲得查詢(xún)項(xiàng)對(duì)應(yīng)的查詢(xún)主體，并作為查詢(xún)結(jié)果，避免了整個(gè)文檔集的掃描。通常，對(duì)于文本檢索而言，查詢(xún)項(xiàng)為詞，而查詢(xún)主體