??? 摘? 要: 給出幾種簡單的預篩選方法,并詳細介紹基于壓縮比例和借助顏色統計的算法及其特點,借助這些算法對網上獲取的GIF格式圖片進行了篩選試驗,取得了滿意的結果。?
??? 關鍵詞: 網絡? 搜索引擎? GIF格式? 圖像圖片? 圖形圖片
?
1問題的提出?
??? 圖像技術的發展和網絡的廣泛應用使網上的圖像搜索引擎成為當今研究的熱點[1]。為構建圖像搜索引擎及基于內容的圖像檢索網站,開發了其信息收集部分——網上爬蟲(Spider)。利用網上爬蟲可以在網上獲取大量的圖片,其中多數是GIF格式[2]。在GIF格式的圖片中,有一些是屬于,自然風景等的圖像圖片,但也有許多屬于圖標圖片。廣告和按鈕等類型的圖形圖片,它們在圖像檢索中意義不大,需要在入庫前濾除掉,這對搜索引擎的下一步工作是非常必要的。?
??? 由于需要建立至少是萬的數量級大小的圖片庫,有大量的圖片需要處理,這就限制了不能采用過于復雜的算法。下面首先介紹幾種簡單的預篩選方法,然后介紹筆者提出的基于壓縮比例和借助顏色統計的算法,最后對算法的效果利用網上GIF圖片進行試驗、考察。?
2 圖片的預篩選?
??? 在獲得GIF文件時,從其文件頭可以得到一些有用的信息,可用來進行預篩選:?
??? (1) 利用圖片文件長度:一般來說,文件長度很短的GIF圖片大多是圖標圖片,可先篩除掉。兩個典型的例子如圖1,兩圖的文件長度分別為346byte和511byte。?
?
?
??? (2) 利用圖片寬高尺度:有些圖片的文件長度不是很短,但其寬度或高度之一很小,這樣的圖片大多是按鈕、圖標或裝飾顏色條。典型的例子如圖2,文件長度為3126byte,但圖片高度只有43個象素(圖片寬度為228象素)。?
?
?
??? (3)利用圖片顏色深度:顏色深度是指每個象素顏色的bit位數。GIF圖片深度不大于8,對應256色。顏色深度太小的圖片由于色彩的限制,大多是圖形圖片。兩個典型的例子如圖3,兩圖的顏色深度均為5bit。?
?
?
3基于壓縮比例的篩選算法?
??? 這種算法借助了GIF格式中所采用的LZW壓縮算法的特點。LZW算法屬于字典壓縮算法[2],其基本壓縮原理是將每一個字節的值都與下一個字節的值配成一個字符對,并為每一個字符設置一個代碼。當同樣的字符對再度出現時,就用代碼代替這一字符對,然后再以這個代碼與下一個字符配對。這里代碼長度為固定的12位,即最大值為4095,這些代碼用盡后,需要重新配對并添表。當圖片顏色深度D<8位時,壓縮的數據單位取為D比特,每個數據單位表示一個象素的顏色值,然后對這樣的基于象素的數據流進行壓縮。?
??? 由上述可見,LZW算法的壓縮比例在很大程度上取決于圖片的“圖案化”程度。如果可以在圖片中查找到圖案模型(如許多圖形圖片那樣),并利用比較短的代碼取代它,則壓縮比就會比較高。而如果原始圖像數據值中帶有相當的隨機變化(如許多圖像圖片那樣),則很難利用LZW算法進行有效的壓縮。這個特點為利用壓縮比例來區分圖像和圖形圖片提供了理論依據。?
??? 定義如下壓縮比例R:?
????
?
??? 其中W為圖片寬度,H為圖片高度,D為圖片的顏色深度,對于GIF圖片,它的取值為1～8。這些數據都可以通過讀取GIF文件頭快速得到。式(1)中的L為GIF文件數據區的長度(對經過預篩選的GIF圖片,其文件中非數據區部分的長度已經微不足道,可用GIF文件的總長度代替數據區的長度進行計算以降低算法的復雜度)。由式(1)的定義可知,這樣計算出來的壓縮比例值R消除了圖片大小和顏色深度對壓縮效果計算的影響。?
??? 根據壓縮比例值R選取合適的閾值TR就可區分圖形和圖像。筆者曾從15個有代表性的綜合站點(包括263,Chinabyte,yesky等)隨機抽取了3071幅GIF格式圖片,經預篩選后剩余358幅圖片(這也可看出預篩選的作用),其中D=8的圖片有179幅,它們的R值分布情況如表1。?
?
?
??? 這里對圖像圖形的區分采用了人工標定的方法。標定的原則是:如果圖片2/3以上的部分是由自然景物或者美術作品構成的,則認為它是圖像圖片,否則就認為它是圖形圖片。從表1的統計數據可以看出如果選擇閾值TR為0.07就可在保證不篩除圖像的條件下篩除2/3的圖形圖片。?
4 基于顏色統計的篩選算法?
??? 這種算法的基本原理是統計圖片中出現的顏色數。一般由于圖像圖片包含顏色過渡,所以色彩數比較多。但因為圖形中也常有微小的過渡區域,有時使得直觀上看起來色彩很簡單的圖形圖片其顏色統計的結果往往并不少。為此規定只有某種顏色出現的次數大于N才被計入顏色總數,這里定義:?
????
?
??? 上式的統計意義就是出現次數小于顏色平均次數1/40的顏色不計入顏色總數。這種改進可以使對圖形圖片顏色的統計比較正確。而圖像圖片由于過渡區域往往面積比較大,這種改進對其顏色數量的影響比較小。?
??? 對表1的179幅圖片根據其顏色統計值劃分的結果見表2。?
?
?
??? 由表2可見,如果取閾值于TS為36,則通過保留顏色統計值大于TS的圖片可以保留所有的圖像圖片,并且去掉77.4%的圖形圖片。?
5 兩種算法的綜合與比較?
??? 上述兩種算法可結合使用,為衡量它們的性能,可以使用查全率和查準率,它們分別定義為:?
????
?
??? 對上述兩種算法結合使用與單獨使用的效果做比較,其結果見表3。?
?
?
??? 由表3可見:?
??? (1)取閾值為0.07的壓縮比例法和取閾值為36的顏色統計法可以保證較高的查全率;?
??? (2)取閾值為0.09的壓縮比例法可以獲得較高的查準率,如果與取閾值為36的顏色統計法配合使用可進一步提高查準率。?
??? 兩種算法從計算復雜度來考慮,壓縮比例法的計算時間可以忽略不計,而顏色統計法平均每幅圖片處理的時間在50ms左右(奔騰II-300)。如果精確地計算GIF文件數據壓縮區的長度可以進一步提高分類的準確性,但需要對GIF碼流做分解,對算法速度有影響。?
??? 本文討論了對網上GIF格式圖片劃分圖像和圖形圖片的一些方法。先介紹了幾種簡單的預篩選方法,然后介紹了兩種比較有效的篩選算法,一種基于壓縮比例,一種借助顏色統計。分析和實驗表明,它們均具有較好的準確性和較快的運算速度,可結合實際應用領域綜合使用這些方法以取得需要的劃分圖像和圖形的效果。?
參考文獻?
1 Cho J, Garcia-Molina H, Page L. Efficient crawling?through URL ordering. Proc. 7th International World?ide Web Conference, 1998:161～172?
2 凱依(美)著,柏東譯. 圖形圖像文件格式大全.北京:學苑出版社, 1994