摘  要: 给出几种简单的预筛选方法,并详细介绍基于压缩比例和借助颜色统计的算法及其特点,借助这些算法对网上获取的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的统计数据可以看出如果选择阈值T_R为0.07就可在保证不筛除图像的条件下筛除2/3的图形图片。 

4 基于颜色统计的筛选算法 

    这种算法的基本原理是统计图片中出现的颜色数。一般由于图像图片包含颜色过渡,所以色彩数比较多。但因为图形中也常有微小的过渡区域,有时使得直观上看起来色彩很简单的图形图片其颜色统计的结果往往并不少。为此规定只有某种颜色出现的次数大于N才被计入颜色总数,这里定义: 

    上式的统计意义就是出现次数小于颜色平均次数1/40的颜色不计入颜色总数。这种改进可以使对图形图片颜色的统计比较正确。而图像图片由于过渡区域往往面积比较大,这种改进对其颜色数量的影响比较小。 

    对表1的179幅图片根据其颜色统计值划分的结果见表2。 

    由表2可见,如果取阈值于T_S为36,则通过保留颜色统计值大于T_S的图片可以保留所有的图像图片,并且去掉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