【正文】 ..... 43 圖表 12 建索引流程圖 ............................................................................................... 46 圖表 13 內(nèi)容相同圖片的拉鏈結(jié)構(gòu) .............................................................................. 47 圖表 14 查詢過程 ...................................................................................................... 47 圖表 15 查詢線程流程圖 ............................................................................................ 49 學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 1 第 1章 引言 背景 目前的 Inter 應(yīng)用已經(jīng)取得了長足的發(fā)展，隨著網(wǎng)絡(luò)帶寬和終端計算能力的不斷增強，圖片被越來越多的應(yīng)用于內(nèi)容的表達(dá)和信息的承載，特別是在 Web的應(yīng)用上更是不可或缺。圖片的信息是指圖片的內(nèi)容所表征的意義，這種的信息承載方式與傳統(tǒng)的文本的信息是不一樣的。基于內(nèi)容的技術(shù)是對圖片的內(nèi)容本身（像素）進(jìn)行分析和檢索，而基于文本的技術(shù)利用圖片的相關(guān)文字信息作為分析對象，并提供類似于傳統(tǒng)文本檢索的工作方式。這就為提供一個通用的信息提取框架提供了可能。 根據(jù) CNNIC 的《 2020 中國互聯(lián)網(wǎng)絡(luò)信息資源數(shù)量調(diào)查報告 》 [1]顯示（截至到 2020 年 12 月 31 日）： 網(wǎng)頁數(shù) 全國網(wǎng)頁總數(shù) 311,864,590 個 其中：靜態(tài)網(wǎng)頁數(shù) 226,725,557 個 動態(tài)網(wǎng)頁數(shù) 85,139,033 個 學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 2 靜動態(tài)網(wǎng)頁數(shù)比例 :1 平均每個網(wǎng)站的網(wǎng)頁數(shù) 網(wǎng)頁字節(jié)數(shù) 全國網(wǎng)頁總 字節(jié)數(shù) 6,059,431,526KB 每個網(wǎng)頁平均 字節(jié)數(shù) 平均每個網(wǎng)站的網(wǎng)頁 字節(jié)數(shù) 10, 圖表 1 網(wǎng)頁數(shù)及網(wǎng)頁 字節(jié)數(shù) 情況 近三年中國網(wǎng)頁數(shù)對比159460056 1570912203118645901 .5 %9 8 .5 %0500000001000000001500000002020000002500000003000000003500000002020 年 2020 年 2020 年2 0 %10%40%70%100%130%網(wǎng)頁數(shù) 增長比率 圖表 2 近三年中國網(wǎng)頁數(shù)對比 圖像 % 音頻 % 視頻 % 圖表 3 網(wǎng)頁的內(nèi)容分類情況 （按 多媒體 形式） 從以上統(tǒng)計數(shù)字可以看到，目前國內(nèi)的 Web 信息資源數(shù)量已經(jīng)相當(dāng)可觀，并且隨著 IT 業(yè)在 2020 年的逐漸復(fù)蘇，網(wǎng)頁數(shù)量比 2020 年增長了一倍。因此，本文的切入點就是如何有效的利用這些 HTML 網(wǎng)頁來構(gòu)建 Web 圖片搜索引擎。許多的醫(yī)學(xué)和健康相關(guān)的專業(yè)需要使用例如 X 光、掃描影像之類的一些可視信息資料，用 于診斷和檢測疾病。對于已有的設(shè)計的重用，可以為該領(lǐng)域的工作者提供大量的素材和靈感，圖片檢索系統(tǒng)可以為這些工作提供大量幫助，同時，對于用戶尋找特定要求的作品也提供了很大的便利。 其它的一些領(lǐng)域還包括建筑設(shè)計、天文學(xué)、地理學(xué)、歷史研究、犯罪取證等。因此，圖片通常具有多種檢索方式，從用戶檢索的角度看，可以分為如下幾類： ? 目錄式檢索： yahoo 的圖片搜索集成了其網(wǎng)頁搜 索的特點，將圖片進(jìn)行分類，用戶按照分類結(jié)構(gòu)逐漸細(xì)化查詢范圍。關(guān)鍵字檢索方式最顯著的優(yōu)點是其檢索速度非?？欤⑶一谖谋镜乃饕夹g(shù)已經(jīng)很成熟。二是人工標(biāo)引的信息主觀性比較強，有時候不能恰當(dāng)?shù)姆从硤D片的真實信息或者反映的信息不完全（后者幾乎總是存在）。 ? 實例式檢索： 目前的基于內(nèi)容的圖片搜索引擎大多是這一類。 ? 屬性式檢索： 這種檢索方式多用于小規(guī)模的專門的圖片數(shù)據(jù)庫，比如攝影圖片庫，用戶可以根據(jù)作者，拍攝日期等一些圖片的外在特征來進(jìn)行檢索。假設(shè)對于特定的查詢， D+為整個文檔集合中相關(guān)文檔的數(shù)量， R 為查詢結(jié)果文檔集合， R+為結(jié)果文檔中相關(guān)文檔集合，則查準(zhǔn)率和查全率可以形式化的定義為： 查準(zhǔn)率： RRecisio n ??Pr 查全率： ??? DRcallRe 在圖片檢索系統(tǒng)中，對于這兩項指標(biāo)的度量 比較困難，因為對于圖片與文本的相關(guān)性評價是相當(dāng)主觀的，基本上只能得到一個很粗略的統(tǒng)計結(jié)果。 研究現(xiàn)狀 基于文本的圖片檢索最早可以追溯到 20 世紀(jì) 70 年代早期，當(dāng)時的檢索系統(tǒng)使用人工對圖片的內(nèi)容進(jìn)行文字信息標(biāo)引，利用 DBMS 存儲文字信息，并利用文本檢索技術(shù)提供查詢。該技術(shù)不需要進(jìn)行文字標(biāo)引，而是通過圖片本身的可視化內(nèi)容來進(jìn)行索引，例如顏色、紋理、形狀等。 鑒于此，有學(xué)者提出了基于語義的圖像檢索 [43]，該技術(shù)試圖建立一種高層次的語義到低層次的可視特征之間的映射關(guān)系，實際上是試圖將可視特征識別為語義概念，使之類似于人類識別事物的方式。 在所有的圖像檢索技術(shù)中，無疑基于文本的檢索是效率最高的一種，很多的圖片搜索引擎都全部或部分的運用了基于文本的檢索機制。其學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 6 中比較重要的幾個商業(yè)圖片搜索引擎包括國外的 google、 yahoo 等，國內(nèi)的有baidu、 Tom、 sina 等。采用一定的基于內(nèi)容的分析手段，提供基于色彩類型（黑白，灰階和全彩）的過濾。其采用了圖片內(nèi)容和文本信息結(jié)合的 方式進(jìn)行處理，分別計算出兩種特征向量，結(jié)合起來提供查詢。特征的提取包括顏色柱狀圖（ color histogram），主方向柱狀圖（ dominant orientation histogram）以及紋理（ texture），并 利用了 PCA（ Principal ponent analysis）在盡可能少丟失信息的情況下降低向量的維數(shù)。 WebSeer 并不對整個網(wǎng)頁的信息建立索引，而是從多個可能的來源提取文 ① 的數(shù)字 學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 7 字，同時對不同的來源確定不同的權(quán)值。 WebSeek WebSeek[10]由哥倫比亞大學(xué)（ Columbia University） Image and Advanced Television Lab 開發(fā)。系統(tǒng)提供關(guān)鍵字檢索方式，輸入關(guān)鍵字得到一個初始的結(jié)果集，之后可以通過文字或者內(nèi)容的提純。并將這些可視化特征利用 kd 樹來索引，可以達(dá)到近似 log(n)級的檢索性能。系統(tǒng)沒有提供相關(guān)反饋功能。之后對文字信息建立索引，建索引過程中使用了死鏈檢查工具，及時將死鏈從索引中去除，并使用了圖片內(nèi)容消重算法。而研究性的圖片搜索引擎大多使用到基于內(nèi)容檢索的方法，或者是兩種方法的結(jié)合，主要是為了提高檢索的精度。 鑒于此，本文 將主要工作放在基于文本的檢索方式上。 本文也簡單的介紹了主要的基于內(nèi)容的信息提取方法，并提出與基于文本的方法結(jié)合的手段，并通過 LSI 方法來提高圖片的高低層語義之間的相關(guān)性，并演示分析了效果。 學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 10 第 2章 相關(guān) 技術(shù) 基于文本的 Web 圖片搜索引擎是一個復(fù)雜的系統(tǒng)，需要多個工作部件之間的協(xié)調(diào)工作，比如純文本網(wǎng)頁和二進(jìn)制圖片的抓取，圖片的文字信息提取，對文字信息建立索引，提供高性能的查詢手段等。 簡單的 Spider 的網(wǎng)頁抓取的路徑是按照超鏈接的拓?fù)漤樞蜻M(jìn)行的。 小型的 Spider 的設(shè)計是很簡單的，但是當(dāng) Spider 的規(guī)模增大以后，甚至到了需要遍歷 Inter 上的大部分資源的時候，性能、健壯性等等方面的一些因素就必須仔細(xì)的考慮，下面提出一些問題，進(jìn)行簡單的分析。任務(wù)分配的策略有 很多種，可以分為動態(tài)分配和靜態(tài)分配。目前通過采用 HTTP/ 重用連接， DNS 緩存和預(yù)取等技術(shù)，可以加快處理速度。 ? 對于動態(tài)網(wǎng)頁的處理 由于眾所周知的 Spider Trap 問題，很多 Spider 的做法是不抓取動態(tài)網(wǎng)頁，有的 Spider 只抓取第一層的動態(tài)網(wǎng)頁，這樣可以避免很多問題，但是以放棄部分信息為代價，特別是某些最新的重要信息（比如最新報道）可能放在動態(tài)網(wǎng)頁中，這樣對于新信息的搜索將得不到滿意的結(jié)果。 3）基于位置，分析網(wǎng)頁的位置，比如域名，目錄深度等，可以優(yōu)先抓取“ .”域名下網(wǎng)頁，并優(yōu)先抓取目錄深度淺的網(wǎng)頁。隨著圖片數(shù)量的急劇增長，用戶每次查詢返回的結(jié)果數(shù)也相應(yīng)的迅速增大。 學(xué)位論文 基于文本的 Web 圖片搜索引擎的研究 12 下面介紹兩種比較常用的相關(guān)性排序技術(shù)： VSM 和 LSI。 形式化的定義為： ??? TnTT WWWD ,.. ., 21 其中， D 代表文檔，其是一個 n 維的向量。 文檔被形式化的表示成向量以后，我們可以通過將查詢也表 示成向量形式，而通過計算兩個向量在向量空間中的夾角來評估文檔與查詢之間的相似度。 但是 VSM 的重要意義在于，它提供了一種通用的方法來比較特征之間的相似性。一方面，同一個詞表達(dá)的意思在不同的上下文中是不一樣的，這種情況下，查到的結(jié)果往往并不是想要的，影響查準(zhǔn)率；另一方面，相同的意思可以使用多種不同的詞來表達(dá)，這種情況下，只有包含查詢詞 的文檔才會被檢索到，而其他的相關(guān)的文檔將不能查到，影響查全率。圖片檢索系統(tǒng)中，這個問題更加嚴(yán)重，多了一次映射，即從圖片到詞語。 傳統(tǒng)的檢索系統(tǒng)中通常是引入一個知識庫來試圖解決上述問題。該模型不試圖利用任何外部知識，而是從挖掘文檔集本身的潛在信息入手，利用統(tǒng)計分析方法來構(gòu)造語義空間結(jié)構(gòu)，自動發(fā)現(xiàn)文檔之間的潛在語義關(guān)系。 LSI 通過統(tǒng)計方法，對大規(guī)模的文檔集合構(gòu)造對應(yīng)的矩陣，并通過 SVD（ Singular Value Deposition，奇異值分解）和降維處理，來將文檔和詞的關(guān)系映射到相似的低維的語義空間中。該權(quán)值的計算有很多種方法，最簡單的就是詞在文檔中出現(xiàn)的頻率。選定一個 K 值，保留 S0矩陣的對角線上的前K 個最大的 σ，而將其余的替換為 0。 K 值的選取是很重要的，太大會導(dǎo)致結(jié)果趨近于原始矩陣而失去挖掘潛在語義的能力，太小則會使得語義信息丟失太多，以至于對于文檔和詞的分辨能力不足。 在圖片搜索引擎中，圖片本身能夠提取到的信息是有限的，主要是由于兩點原因： 1）本身可供提取的信息比較少； 2）即使是可以提取大量的信息，考慮到相關(guān)性低的問題，往往也只保留很少的一部分。相關(guān)的內(nèi)容將在 節(jié)中進(jìn)一步闡述。獲得文字信息之后， 可以利用傳統(tǒng)的文本信息檢索的相關(guān)技術(shù)來提供信息的組織和查詢。 可視化特征提取是基于內(nèi)容的圖片檢索的基礎(chǔ)，按照應(yīng)用范圍可以分為特定領(lǐng)域的特征提取和通用特征提取。所以，在進(jìn)行特征提取的時候，通常也是從多個不同的角度去考慮，從而形成了多種可視化特征對象。 顏色直方圖是最常被用于顏色特征表達(dá)的方法，它從統(tǒng)計意義上表示了三種顏色通道的強度的關(guān)聯(lián)概率。另外的一些顏色系統(tǒng)，比如 U*V*W、 L*a*b、L*u*v 等，充分考慮了人眼對于顏色感知上的特點，因此適合用于圖片檢索這類需要滿足人眼視覺要求的系統(tǒng)中 [25]。 基于邊界的描述方式中使用最多的是傅立葉描述子（ Fourier Descriptor）。 Hu 提出了 7 種不同的矩 [20]，后來有人提出來改進(jìn)的計算方法 [20]，有效的提高了計算的效率。結(jié)構(gòu)方法主要針對有規(guī)律的紋理結(jié)構(gòu)，利用句法分析方法來進(jìn)行識別。目前有很多的圖片，文字被嵌入到了其中，通過圖片的像素表現(xiàn)出來。該方法的難度在于圖片中的文字可以 是任意的顏色，并且有些圖片的文字背景圖案由各種不同顏色的對象構(gòu)成，難于將其識別為獨立的成分。 另一個潛在的優(yōu)勢是，分析圖片內(nèi)容本身來探究其包含的意義符合固有的人類理解圖片的方式，隨著計算機視覺 和人工智能等技術(shù)的不斷發(fā)展，圖片分析技術(shù)將會不斷接近于人類的視覺認(rèn)知水平。在這里，啟發(fā)式規(guī)則的選擇是相當(dāng)重要的，它將直接影響到系統(tǒng)的查準(zhǔn)率，同時也在很大程度上影響著系統(tǒng)的查全率。這種方案實現(xiàn)簡單，順序掃描信息進(jìn)行字符串匹配即可。以下簡單的介紹兩種技術(shù)的基本原理。 當(dāng)進(jìn)行查詢時，將查詢 詞利用相同的 Hash 函數(shù)進(jìn)行簽名，利用簽名產(chǎn)生的位串在簽名文件中進(jìn)行遍歷查詢，可以得到一個匹配的結(jié)果文檔列表。 由于簽名文 件本質(zhì)上還是掃描文檔，所以盡管其在很多方面不斷進(jìn)行改進(jìn)，但對于海量數(shù)據(jù)的應(yīng)用，表現(xiàn)依然不夠理