快速的基于小波的图像检索方法

摘要：该文描述一种基于小波的图像检索方法。该方法使用小波分解提取图像“签名”，然后使用该文构建的检索方法进行检索。该方法已应用于某纪念币检索系统中，具有查询速度快、存储空间小和实现简单等优点。

关键词：小波；Haar；小波分解；基于内容的图像检索；图像数据库

中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)35-2218-02

Fast Wavelet-based Image Retrieval

CHEN Kang, SU Xiao-long, WANG Xiang-ting

(China University of Mining and Technology, School of Computer Science and Technology, Xuzhou 221008, China)

Abstract: The paper presents a method for wavelet-based image retrieval. It extracts image "signature" by wavelet decomposition, then searching by using the method of the paper. The method has been applied in the Commemorative Coins Retrieval System. The method is very fast and needs a little storage and is implemented easily.

Key words: wavelet; haar; wavelet decomposition; content-based image retrieval; image database

1 引言

图像检索系统[1]是一种计算机系统，用于在大型的数字图像数据库中进行图像的浏览与检索。传统的图像检索方法主要是通过人工向图像中添加关键字等元数据对图像进行索引。这种方法存在以下两个问题。首先，这是一个非常耗时的工作，随着图像数量的急剧增长，人工处理的方法将很难满足要求。其次，由于视觉方面的差异，不同的人对同一图像可能存在不同的描述，这将导致查询结果很不可靠。目前使用的方法主要是基于内容的图像检索方法[1]。

本文描述的方法是：首先对数据库中的图像进行Haar小波分解[2]提取图像特征，称之为“签名”，然后对输入的图像进行相同的Haar小波分解，最后使用本文构建的检索方法在图像数据库中进行检索，并返回最相似的若干图像。该方法允许多尺度查询[3]，运行时间和存储空间都独立于图像数据库[4]的图像的尺度，并且图像的签名信息可以从图像的小波压缩版本中直接抽取。最后，该方法非常容易实现和使用。

2 检索方法的构建

我们的目标是构建一种图像检索方法，该方法可以快速计算并且仅需要少量的存储空间。因此，我们猜测图像的二维小波分解对于构建这种方法可能提供一种比较好的途径，原因如下：

1） 小波分解可以使用较少的系数较好的描述图像。这种特性已经被应用于图像的有陨压缩[5]中。

2） 小波分解可以用于抽取和编码图像边缘信息。这种特性对于图像检索具有非常重要的意义。

3） 小波分解的系数提供的信息独立于原始图像的尺度。因此，基于小波的检索方法允许查询图像与目标图像的具有不同的尺度。

4） 小波分解非常快速并且容易计算，线性时间复杂度，编码实现也非常简单。

2.1 相关问题

下面是本文检索方法的一些相关问题：

1） 颜色空间：我们需要选择一个颜色空间来表示图像，实现分解。我们实验了以下三种颜色空间：RGB，HSV和YIQ。最终，通过实验得出YIQ在这三种颜色空间中最为有效。

2） 小波类型：我们选择Haar小波，因为它计算非常快速并且易于实现。

3） 截断：对于128×128的图像每个颜色通道共有1282=16,384种不同的小波系数，而本文方法只使用最大的小波系数。这种截断不仅加速搜索并且减少存储空间。通过实验发现存储40个最大系数效果最佳。

4） 量化：像截断一样，对于每个小波系数进行量化主要为了加速搜索和减少存储空间。我们将系数量化为二个级别：+1（代表正系数）和-1（代表负系数）。

2.2 相似度计算

图像检索的过程就是比较查询图像与目标图像的相似度。下面介绍本文如何计算图像相似度。首先，Q和T分别代表查询图像和目标图像单个颜色通道的小波分解。Q[0,0]和T[0,0]代表相应颜色通道的颜色平均值。更进一步Q[i,j]和T[i,j]代表第[i,j]个截断的、量化的小波系数，这些值可能为：-1，0和+1。Q与T的相似度计算等式如下：

（1）

上式中bin(i,j)是由索引[i,j]选择权重的函数。上式中(Q[i,j]==T[i,j])的计算方法为：当Q[i,j]等于T[i,j]时为1，否则为0。注意：上式的值越小代表Q与T越相似。

3 算法

本文的检索算法的复杂度是线性的。算法描述为：在预处理阶段，我们对图像数据库中的每个图像进行标准的二维小波分解，存储颜色平均值和m个最大的小波系数的索引和符号。然后，对每个查询图像，执行相同的小波分解，获取颜色平均值和m个最大量级的小波系数。然后利用式(1)对目标图像T进行评分（相似度计算）。

3.1 预处理

图像的标准的二维Haar小波分解非常容易编码实现。首先对图像的每一行进行一维小波分解，然后对分解结果的每一列进行一维小波分解。

下面的伪代码对数组A[h]执行一维的小波分解，h必须是2的幂：

proc DecomposeArray(A : array[0..h-1] of color) :

A A/?h

while h > 1 do :

h h/2

for i 0 to h-1 do :

A`[i] (A[2i]+A[2i+1])/

A`[h+i] (A[2i]-A[2i+1])/ ?2

end for

A A`

end while

end proc

上面的伪代码，假设数组A中每个元素代表的颜色具有三个通道，范围为[0,1]。各种操作分别对每个颜色通道进行。

一个r×r的图片T可以进行如下分解：

proc DecomposeImage(T : array[0..r-1, 0..r-1] of color) :

for row 1 to r do :

DecomposeArray(T[row, 0..r-1])

end for

for col 1 to r do :

DecomposeArray(T[0..r-1, col])

end for

end proc

在分解过程之后，T[0,0]代表整幅图像的颜色平均值，而其它的值为小波系数。

最终，我们存储T[0,0]和最大的m个小波系数的索引和符号。为了优化搜索过程，保留的m个小波系数被组织成六个数组，称为搜索数组，每个数组代表符号（+/-）和颜色通道（如YIQ）的每种组合。

检索是非常直接的。对于特定的查询图像Q，我们执行上一节描述的小波分解。然后，保留图片的颜色平均值和每个颜色通道的最大的m个小波系数的索引和符号。然后根据查询图像Q分别对图像数据库中每个目标图像T进行评分，计算过程如下：

func ScoreQuery(Q : array[0..r-1, 0..r-1] of color; m : int) :

DecomposeImage(Q)

Initialize scores[i] 0 for all i

for each color channel c do :

for each database image T do :

score[index(T)] += Wc[0]×|Qc[0,0]-Tc[0,0]|

end for

Q TruncateCoefficients(Q, m)

for each non-zero cefficient Qc[i,j] do :

if Qc[i,j] > 0 then

list Tc+[i,j]

else

list Tc-[i,j]

end if

for each element l of list do :

scores[index(l)] -= wc[bin(i,j)]

end for

end for

end for

return scores

end func

函数bin(i,j)提供了一种将不同的小波系数分组的方法，每一组使用不同的权重w[b]。在我们的实现中，使用的函数为：bin(i,j) = min{max{i, j}, 5}。

对于我们的图像数据库，一个比较好的使用YIQ颜色空间和标准Haar小波分解的权重集，如下：

wY[b] wI[b]wQ[b]

0 5.00 19.21 24.37

1 0.83 1.26 0.36

2 1.01 0.44 0.45

3 0.52 0.53 0.14

4 0.47 0.28 0.18

5 0.30 0.14 0.27

最后，我们的算法检查分数列表，这些得分可能为正也可能为负。最小的（通常是负的）得分被认为是最接近的。我们使用堆排序算法查找前20幅最匹配的图像。

4 应用

本文描述的图像检索方法被应用到某纪念币网站的纪念币检索系统中。该系统要求用户输入查询纪念币的图像（正面或背面），系统会输出与其最匹配的前20个纪念币的图像及其资料。在实际的应用中，本文描述的检索方法具有检索速度快、准确性高和占用存储空间小等优点，完全满足了该检索系统的要求。

5 小结

本文描述的检索方法具有检索速度快，准确性高，存储空间小和实现简单等优点，具有一定的实用价值。但本文的检索方法仍然存在着不足，比如不具有旋转不变性，权重调整速度慢等缺点，需要进一步完善，这也是下一步的工作内容与研究方向。

参考文献：

[1] 周明全.基于内容图像检索技术[M].北京:清华大学出版社,2007.

[2] 孙延奎.小波分析及应用[M].北京:机械工业出版社,2005.

[3] Lowe D. Object recognition from local scale-invariant features[M]. In Proc. ICCV,1999:1150-1157.

[4] Squire D M, Muller W, Muller H, et al. Content-based query of image database: inspiration from text retrieval[C]. Pattern Recognition Letters,2000(21):1193-1198.

[5] 曾文曲,文有为,孙炜,等.分形小波与图像压缩[M].辽宁:东北大学出版社,2002.