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