基于词汇树的图片搜索

—189— 基于词汇树的图片搜索 陈 赟，沈一帆 (复旦大学计算机科学与技术学院，上海 200433) 摘 要：针对基于内容的图片搜索存在召回率低及匹配速度较慢的问题，在词汇树的基础上，利用模糊量化加以解决。把从图像中抽取到 的 SIFT 特征利用词汇树模糊量化到单词中，从而将图片转为用向量表示，同时用向量间的比较测量图片相似度。实验结果表明，该方法 可以有效缩短响应时间，提高搜索结果的召回率。 关键词：图片搜索；词汇树；模糊量化 Image Search Based on Vocabulary Tree CHEN Yun, SHEN Yi-fan (School of Computer Science and Technology, Fudan University, Shanghai 200433) 【Abstract】Regarding the inadequacy in recall rate and match speed in content-based image search, an effective method based on vocabulary tree is presented, using fuzzy quantification. The SIFT(Scale Invariant Feature Transform) descriptors are extracted from the query image, which fuzzily quantifies these features to words using vocabulary tree. In this way, the query image can be represented as a weight vector. The query vector is compared with database vectors to measure the image similarity. Experimental results show this method can greatly shorten the response time, and improve the recall rate significantly. 【Key words】image search; vocabulary tree; fuzzy quantification 计 算 机 工 程 Computer Engineering 第 36卷 第 6期 Vol.36 No.6 2010年 3月 March 2010 ·人工智能及识别技术· 文章编号：1000—3428(2010)06—0189—03 文献标识码：A 中图分类号：TP311.52 1 概述 从本质上说，基于内容的图片搜索是图像匹配技术的应 用。图片中不规则物体的形变、背景的干扰、视角或尺度的 差异以及光照的变化等，都会给图片匹配带来很大困难。而 在基于特征的匹配技术中，首要任务是提取稳定的特征，本 文采取 SIFT 特征[1]作为图像的描述子。SIFT 特征是图像的 局部特征，它对旋转、尺度缩放、亮度变化保持不变性，对 视角变化、仿射变换、噪声也保持一定的稳定性。利用 SIFT 特征匹配算法实现图片搜索，最基本的做法是把每幅图片用 一个特征集合来表示，当输入查询图片时，把查询图片的特 征集合与库中每张图片的特征集合进行比较，找到特征匹配 数目最多的几张图片作为查询结果返回。实验结果表明，当 库中的图片数量不多时，这种方法返回的查询结果具有较高 的精度，但是当库中的图片成倍的增加时，花在特征匹配上 的时间则急剧增加，无法满足实际应用要求。文献[2]借鉴文 本信息检索中的方法，把从训练集中提取到的特征进行 K-Means 聚类，生成的每个簇集定义为一个单词，每个单词 再关联一个倒排文件，然后把从查询图片中提取到的特征量 化到这些单词当中，利用 TF-IDF模型[3]对查询图片与库中图 片的相似度进行评测。文献[4]在文献[2]的基础上提出分层聚 类的做法，利用生成的词汇树，使特征量化时不必遍历所有 单词，极大缩短了量化所需时间。本文方法在文献[3]的基础 上，引入模糊分类理论对特征进行模糊量化，使查询结果具 有更高的返回率。实验表明，该方法在有遮挡发生或有背景 干扰时仍然具有很好的鲁棒性。本文方法采用 Matlab7.0加以 实现。图 1为系统流程。 图 1 系统流程 2 词汇树构造 训练集中的每张图片用一个唯一标识的 ID(自然数)进行 关联。对每张图片都提取 SIFT 特征，得到一个特征集合 { }iF f= 以及相应的图片 ID集合 imgId= { }iid ，它表示提取到 的第 i 个特征出现在 ID 为 iid 的图片中。然后对特征集合 F 进行分层聚类，这里采用 K-Means聚类方法，它的优点是具 有较快的聚类速度、较好的可伸缩性，可以满足缩短响应时 间的要求。初始时，在树的第 1 层上对特征集合 F 进行 K-Means 聚类，把特征集合 F 分成 k 份 { |1 }iF i k≤ ≤ ，计算 出每个簇集 iF 的中心向量 iC 。类似地，对新产生的簇集利用 K-Means 再分成 k 个簇集，不断地重复上述操作直到树的深 度达到预先设定的 L 值。若树中某个簇集内的向量个数小于 k，则这个节点就不再分裂。该过程如图 2所示。 { }iF f= 1F (1 )iF i k< < kF 1i F (1 )iF kθ θ< < kiF " " "" " " " " " 图 2 词汇树 作者简介：陈 赟(1985－)，男，硕士，主研方向：计算机视觉，行 人检测；沈一帆，教授 收稿日期：2009-10-10 E-mail：chenyun_08290@hotmail.com —190— 树中节点的数目为 1 1 1 L lL l k kk k + = −=∑ − ，它们都是对特征聚 类而产生的簇集 1 (1 )lLliF i k=∑≤ ≤ ，定义为单词，而把每张图 片看作是文档，这里是借鉴了文本检索当中的概念。每个单 词都关联一个倒排文件，它统计了单词在每篇文档中出现的 频率。在具体实现中这个倒排文件是一个由图片 ID组成的向 量，所以，可以利用图片内的特征在单词中的分布来表示一 幅图片。接下来将介绍如何把一幅图片转换为用一个权值向 量来表示。建立词汇树过程实际上是一个无监督的训练过程， 它为特征的量化提前做好准备。 3 训练集中的图片转换为向量表示 3.1 图片的表示方法 在文本信息检索当中，可以为文献中的标引词定义一个 权值(weight)来描述标引词与文献的相关程度。假设用 iF 表示 标引词， jd 表示文献， , 0i jw ≥ 为二元组 ( , )i jF d 的权值，该 权值可以用来衡量描述文献语义内容的标引词的重要性。用 t 表示文献中标引词的数目，那么 1 2{ , , , }tF F F F= " 是所有标 引词的集合， ,i jw 是文献 jd 中标引词 iF 的权值，对于没有出 现在文献 jd 中的标引词，其权值 ,i jw =0。所以，文献 jd 可以 用权值向量来表示： 1, 2, ,[ , , , ]j j j t jw w w=d " (1) 将这个原理应用到基于内容的图片检索中，仍然可以使 用式(1)表示图片，这时 iF 表示分层聚类所形成的簇集，即前 面说到的单词，而用 jd 来表示图片，此时单词的数目 1 lL lt k== ∑ 。 类似地， ,i jw 表示用来描述第 j 张图片的第 i 个单词 ( 1 i t≤ ≤ )的重要性，换言之就是单词 iF 与图片 jd 的相关程 度。这样训练集中的所有图片可以用如下矩阵表示： 1,1 2,1 ,1 1,2 2,2 ,2 1, 2, , t t N N t N w w w w w w w w w ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ " " # # # " 下面将介绍权值 ,i jw 是如何计算的。 3.2 权值的计算 在文本信息检索中，tf-idf[3]是有效的语词加权 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。仿 照 tf-idf的原理来定义权值，它的定义分成 2个部分： (1)假设 ,i jm 表示单词 iF 在图片 jd 当中出现的次数，它可 用于衡量单词描述图片的好坏程度。假设与单词 iF 关联的倒 排文件为 [1, ,1,2, ,2,3, ,3, ]" " " " ， ,1im 表示单词 iF 在第 1 张 图片 1d 中出现的次数(也就是 1 的个数)，类似地，单词 iF 在 第 2张图片 2d 中出现的次数则表示为 ,2im 。如果单词 iF 不出 现在图片 jd 中，则 ,i jm =0。 (2)假设 N表示训练集中的图片总数， in 表示包含单词 iF 的图片数目。类似于文本检索当中的逆文献频率 iidf ，定义 lgi i Nidf n = ，它阐明了在许多图片当中出现的单词对于区分相 似图片和不相似图片是没有什么作用的。把它固化到词汇树 的节点上表示为该节点的信息熵，在训练阶段完成信息熵的 求解，这就减少了查询时计算权值时所花的时间。 所以，单词 iF 与图片 jd 的相关程度 ,i jw 可以定义为 , , lgi j i j i Nw m n = × (2) 4 查询图片的向量表示 4.1 查询特征的量化 本文目标是把查询图片 q也转化为关于单词的权值向量 1 2[ , , , ]tw w w=q " 表示。把提取特征后得到的集合 { }j=FQ fq 量化到词汇树中的簇集中。在树的第 1层上，文献[3]把每个 特征 jfq ，与该层上的 k个簇集 (1 )iF i k≤ ≤ 分别进行比较， 其实就是与 k 个簇集的中心向量 (1 )i i kC ≤ ≤ 分别做点积运 算。因为 jfq 和 (1 )i i kC ≤ ≤ 都是单位向量，所以点积的结果 越大，代表 2 个向量越相近。假设中心向量 (1 )ii ii kC ≤ ≤ 与 jfq 最接近，就把 jfq 归入到 iiC 代表的簇集 iiF 中。 接下来在词汇树的下一层，再把特征 jfq 与簇集 iiF 的 k 个子节点(簇集)进行比较，如此反复直到达到树的叶子节 点，这样就完成了对集合中的特征 jfq 的量化过程。 树的深度为 L，对于一个特征而言，基于词汇树的量化 总共需要的计算成本为 kL次点积，当 k不是很大时，量化过 程是非常迅速的。 本文对量化的过程进行改进。K-Means 由于自身存在的 弱点，可能会把一组内在非常相近的向量强行分成 2 个或更 多部分，这就造成了在词汇树的每一层上确定查询特征 jfq 的归属时有可能会发生偏差。基于这样的考虑，引入模糊分 类来增强量化的鲁棒性。 4.2 改进的量化过程——模糊分类 假设从查询图片中得到的特征集合为 1 2{ , , ,fq fq=FQ " , , }j Mfq fq" 其中，共有 M个 SIFT特征向量。 在词汇树的第 1层上有 k个簇集 (1 )iF i k≤ ≤ ，定义 ,i jχ 代表特征 jfq 在簇集 iF 中的隶属度，它反映的是特征 jfq 在多 大程度上可以归入到簇集 iF 中，这与文献[4]中特征 jfq 被严 格量化到某个簇集 iF 是不同的，它可以弥补 K-Means聚类时 可能产生的误差，增强了量化的鲁棒性。隶属度 ,i jχ 需满足 的条件为 , 1 1, (1 ) k i j i j Mχ = =∑ ≤ ≤ (3) , 1 0 , (1 ) M i j j M i kχ = < <∑ ≤ ≤ (4) 接下来讨论如何计算隶属度 ,i jχ 。已知簇集 iF 的中心向 量为 iC ，首先定义 ,i jdis 代表特征 jfq 与中心向量 iC 之间的欧 氏距离： , , 1 ,1i j idis i k j M= −jfq C ≤ ≤ ≤ ≤ (5) 接着定义特征 jfq 相对于以 iC 为中心向量的簇集 iF 的隶 属度 ,i jχ ： 12 /( 1) , , 1 , 1 , 1 k i j i j j dis i k j M dis β δ δ χ −− = ⎡ ⎤⎛ ⎞⎢ ⎥= ⎜ ⎟∑ ⎜ ⎟⎢ ⎥⎝ ⎠⎣ ⎦ ≤ ≤ ≤ ≤ (6) 其中， β 是个调节因子，它控制着模糊分类的模糊程度。如 果对某些 i或者 j来说， , 0i jdis = ，那么规定 , ,1; 0,i j jδχ χ= = iδ ≠ ，这实际上就表示特征 jfq 被完全地归入到簇集 iF 中， 所以，可以说引入模糊分类是对文献[3]方法的一个扩展。从 —191— k个隶属度 ,i jχ 中选择最大值所对应的簇集，接下来的过程与 文献[4]相同。 4.3 图片的向量表示 对于词汇树中的每一个单词 (1 )iF i t≤ ≤ ，累计查询图片 中的特征在该单词当中出现的频率 im 。由于在训练阶段已得 到该节点(单词)处的信息熵，即 lg i N n ，同样借用 tf-idf的原理， 计算出单词 iF 与查询图片的相关程度： lg ,1i i i Nw m i t n = × ≤ ≤ 所以，查询图片可以转换为关于单词的权值向量表示： [ ]1 2, , , tw w w=q " 5 图片间的相似度测量 训练集中图片 1, 2, ,[ , , , ]j j j t jw w w=d " ，而查询图片也转换 为向量 [ ]1 2, , , tw w w=q " 表示。 定 义 训 练 图 片 与 查 询 图 片 之 间 的 差 异 程 度 ： ( , )j j pS = −d q d q ，这里采用的是 2-范数。比较查询图片与 训练图片之间的差异程度 ( , ) , jS d q (1 )j N≤ ≤ ，选取差异程 度最小的前 λ 个作为查询结果返回。 6 实验与分析 本文采用的训练图片一部分来源于 C a l t e c h 2 5 6 , Caltech101，另一部分为手工拍摄，共有 18 组图片，各有 4组分别来自于 Caltech101, Caltech256的 4个不同种类图片， 每组中包含属于该种类的 4张图片，最后 10组为笔者拍摄， 每组中包含相同物体在不同拍摄条件下的 4张图片。 图 3为训练图片的一部分，前 2行是从 Caltech256中的 bl imp 和 elephant 2 个物体类别中抽取的 4 张图片。 从第 1 行中的 4 幅图片当中可以看到，图片中的相同的 物体处于不同的场景当中，且视角和尺度都有较大的不同； 而第 2行 4幅图片则是 4只不同的大象，外观和姿态都不同， 且处于差异很大的背景中，但它们同属于一个物体类别 (elephant)；第 3 行则为笔者拍摄的图片；最后 2 行是从 Caltech101 中的 mandolin 和 pigeon 2 个物体类别中抽取的 4张图片。 图 3 部分训练集图片 图 4 为程序的一个界面。先从训练集中选择一幅《模式 分类》书的图片输入到程序中，分辨率为 640 480× ，提交查 询请求，系统则会从 72 张训练集图片(每组中有 4 张图片， 总共有 18 组)中找出 4 张与输入图片最相似的图片作为查询 结果返回。如图 4 所示，系统成功地把训练集中的 4 张《模 式分类》书的图片都找出来，并作为查询结果返回，返回率 为 100%。 图 4 系统演示图 实验的机器配置为 Pentium M 1.5 GHz, 896 MB内存。从 该图片当中提取 757 个 SIFT 特征，花费 2.824 s；词汇树的 深度 L设定为 4，而 K-Means的 k设定为 6(比较合理的参数 选择)，查询特征的量化花费了 74.577 s；查询图片转化为权 值向量表示则是非常迅速的，只需 0.12 s。表 1、表 2列出了 不同图片种类的实验数据。 表 1 实验的时间数据 序号 图片类别 提取特征个数 提取特征/s 特征量化/s 1 Java 书 1 099 3.646 95.137 2 音箱 448 2.574 45.596 3 模式分类书 757 2.824 74.577 4 茶壶 878 2.974 86.374 5 椅子 751 2.925 73.405 6 打印机 1 010 3.074 98.983 7 运动鞋 435 2.604 42.561 8 旱冰鞋 795 2.934 77.071 9 电脑屏幕 736 2.925 73.405 10 饮水机 533 2.794 52.546 11 elephant 1 577 3.055 153.711 12 blimp 415 1.462 40.268 13 Mountain-bike 159 0.591 16.103 14 t-shirt 68 1.312 6.580 15 mandolin 123 0.590 12.058 16 saxophone 330 0.791 32.226 17 faces 212 0.981 20.389 18 pigeon 351 0.951 34.960 表 2 返回率数据 序号 图片类别 严格量化/(%) 模糊量化/(%) 1 Java 书 75 100 2 音箱 75 100 3 模式分类书 100 100 4 茶壶 100 100 5 椅子 75 100 6 打印机 75 75 7 运动鞋 25 75 8 旱冰鞋 75 75 9 电脑屏幕 25 75 10 饮水机 25 50 11 elephant 25 50 12 blimp 25 75 13 Mountain-bike 25 50 14 t-shirt 100 75 15 mandolin 25 75 16 saxophone 25 100 17 faces 25 50 18 pigeon 25 50 表 1、表 2 中从第 1 行~第 10 行为笔者拍摄的图片，由 于拍摄对象为相同物体，且处于较为单一的场景当中，尽管 (下转第 195页)