·174. 智能系统学报 第10卷 面合理地描述其特征。因此，找到更合理有效的草 来基于草图的图像检索系统的开发开拓了思路。 图特征描述方法仍需进一步研究。有些学者已经开 3.2.4统一的搜索评价标准 始了新的尝试，如Wang等[63]等人认为目前大部分 随着手绘草图检索系统的增多，如何判定检索 研究只关注对图像特征的描述，而忽略了人的视觉 系统的优劣成为人们关心的问题。对检索系统的评 注意机制，从而提出利用角径向分区的分割方法，根 价分为检索性能评价和检索效果评价，检索性能包 据用户手绘细致程度的不同求得空间权值分配图， 括检索速度、所需内存空间大小及是否满足平移、旋 并将权值分配图与图像特征相结合，提取分割后各 转、缩放不变性等。好的检索系统占用最低的内存 块的特征与权值组成多维特征向量进行相似度计 空间，实现海量数据库的实时响应。检索效果则为 算。通过实验表明，将权值图应用于图像特征对实 检索出的图片与所画草图的相似程度，一般通过绘 验效果有明显改善。可见，更合理的特征描述不能 制“查准率-查全率曲线”进行评价，如3335,671等。 只关注草图本身的构成，还要结合人的视觉机制、人 然而查准率是实验者对检索结果的主观判断，因此 对图形的认知，以及其他反应人的输入意图的主观 Mathias Eitz1s)提出把检索算法对图像的排序与人 因素，形成共同描述草图的特征表示方法。 的主观感受进行比较的评价标准，用二者之间的相 3.2.2基于大数据的索引结构 关性作为检索效果的评价标准。然而检索系统的优 早期的草图检索系统均建立在小型数据库的基 劣，应该从特征描述的有效性、系统的稳定性和可移 础上，采用线性的索引结构。而随着互联网数据的 植性、检索性能和效果以及人的主观需求综合考虑， 海量激增，信息检索技术需要满足人们在大数据背 因此如何形成统一的针对基于手绘草图检索系统的 景下的检索需求。目前已经提出一些索引方法来加 评价标准仍是一个值得深入研究的问题。 速检索。例如将用于文本检索的倒排索引运用到草 图检索系统3,3,31门中来，满足基于较大数据库快速 参考文献： 检索的要求。Lkas等38]利用最近邻算法加速检 [1]RUI Y,THOMAS S,CHANG S.Image retrieval:past, 索。MinderFinder[a)提出Edgel Index的索引结构， present and future[J].Journal of Visual Communication 配合上文提到的可索引的定向倒角匹配算法，实现 and Image Representation,1999,10(1):39-62. 了在两百万幅图片上检索仅需几百毫秒的检索效 [2]EAKINS J.Automatic image content retrieval-Are we get- 率。MagicBrush[so]提出类似于倒排索引的方法实 ting anywhere[C]//Proceedings of 3rd International Con- ference on Electronic Library and Visual Information Re- 现六百四十万幅图片上的实时检索。然而对于十亿 search.Newcastle,United Kingdom,1996:123-135. 级数据库(billion-level),MinderFinder需要几分钟 [3]VELTKAMP R C,TANASE M.Content-based image re- 的时间和5TB的内存空间。因此微软亚洲研究院 trieval systems:a survey.UU-CS-2000-34[R].Dept of 的Sun Xinghai等[64提出了采用KLSH,即采用中心 Computing Science,Utrecht University,2000. 点算法(K-Medoids)代替K-means算法的局部敏感 [4]NIBLACK C,BARBER R,EQUITZ W,et al.The QBIC 哈希(Locality sensitive hashing,LSH)的检索结构， project:querying images by content using color,texture, 实现了二十亿数据库的实时检索。然而对于更大规 and shape[C]//Proceedings of SPIE Electronic Imaging: Science and Technology.San Jose,Canada,1993:173- 模(big data)的数据库，如何实现快速检索的需求， 187. 仍在探索阶段。 [5]PENTLAND A,PICARD R W,SCLAROFF S.Photobook: 3.2.3利用草图语义改进草图检索 content-based manipulation of image databases[J].Interna- 传统基于草图的图像检索方法，虽然已经不再 tional Journal of Computer Vision,1996,18(3):233-254. 限制笔划方向等绘画要求，但也需要所绘制的草图 「61孙正兴，冯桂焕，周若鸿.基于草图的人机交互技术研究 接近用户意图。而对于那些在几何形状上离用户意 进展[J].计算机辅助设计与图形学学报，2005,9(17)： 图很远的草图，传统基于草图的图像检索方法则不 1889-1899 具有适应性。Ez等[6s)针对此种情况，提出语义草 SUN Zhengxing,FENG Guihuan,ZHOU Ruohong.Tech- 图检索的方法，采用将用户所绘制草图分类，然后将 niques for sketch-based user interface:review and research J.Journal of Computer Aided Design and Computer 类别作为关键字进行检索。然后在此基础上可以选 Graphics,2005,9(17):1889-1899. 择继续利用形状特征等传统图像检索方法进行图像 [7]尹婷婷，王丹力，戴国忠.基于多笔划的草图绘制工具 检索。Sum等[6]也提出将草图识别用于加强草图 [C]/第5届全国普适计算学术会议论文集.北京，中 检索。可见，将草图的语义用于草图检索可以放宽 国，2009：308-312. 用户绘图的相似性要求、增加检索的准确性，也为未 YIN Tingting,WANG Danli,DAI Guozhong.A sketch面合理地描述其特征。 因此，找到更合理有效的草 图特征描述方法仍需进一步研究。 有些学者已经开 始了新的尝试，如 Ｗａｎｇ 等［６ ３ ］等人认为目前大部分 研究只关注对图像特征的描述，而忽略了人的视觉 注意机制，从而提出利用角径向分区的分割方法，根 据用户手绘细致程度的不同求得空间权值分配图， 并将权值分配图与图像特征相结合，提取分割后各 块的特征与权值组成多维特征向量进行相似度计 算。 通过实验表明，将权值图应用于图像特征对实 验效果有明显改善。 可见，更合理的特征描述不能 只关注草图本身的构成，还要结合人的视觉机制、人 对图形的认知，以及其他反应人的输入意图的主观 因素，形成共同描述草图的特征表示方法。 ３．２．２ 基于大数据的索引结构 早期的草图检索系统均建立在小型数据库的基 础上，采用线性的索引结构。 而随着互联网数据的 海量激增，信息检索技术需要满足人们在大数据背 景下的检索需求。 目前已经提出一些索引方法来加 速检索。 例如将用于文本检索的倒排索引运用到草 图检索系统［１３，２３，５ １ ］中来，满足基于较大数据库快速 检索的要求。 Ｌｕｋａｓ 等［３ ８ ］ 利用最近邻算法加速检 索。 ＭｉｎｄｅｒＦｉｎｄｅｒ ［２２］提出 Ｅｄｇｅｌ Ｉｎｄｅｘ 的索引结构， 配合上文提到的可索引的定向倒角匹配算法，实现 了在 两百万幅图片上检索仅需几百毫秒的检索效 率。 ＭａｇｉｃＢｒｕｓｈ ［５ ０ ］提出类似于倒排索引的方法实 现六百四十万幅图片上的实时检索。 然而对于十亿 级数据库（ ｂｉｌｌｉｏｎ⁃ｌｅｖｅｌ）， ＭｉｎｄｅｒＦｉｎｄｅｒ 需要几分钟 的时间和 ５ＴＢ 的内存空间。 因此微软亚洲研究院 的 Ｓｕｎ Ｘｉｎｇｈａｉ 等［６ ４ ］提出了采用 ＫＬＳＨ，即采用中心 点算法（Ｋ⁃Ｍｅｄｏｉｄｓ）代替 Ｋ⁃ｍｅａｎｓ 算法的局部敏感 哈希（Ｌｏｃａｌｉｔｙ ｓｅｎｓｉｔｉｖｅ ｈａｓｈｉｎｇ， ＬＳＨ） 的检索结构， 实现了二十亿数据库的实时检索。 然而对于更大规 模（ｂｉｇ ｄａｔａ）的数据库，如何实现快速检索的需求， 仍在探索阶段。 ３．２．３ 利用草图语义改进草图检索 传统基于草图的图像检索方法，虽然已经不再 限制笔划方向等绘画要求，但也需要所绘制的草图 接近用户意图。 而对于那些在几何形状上离用户意 图很远的草图，传统基于草图的图像检索方法则不 具有适应性。 Ｅｉｔｚ 等［６ ５ ］针对此种情况，提出语义草 图检索的方法，采用将用户所绘制草图分类，然后将 类别作为关键字进行检索。 然后在此基础上可以选 择继续利用形状特征等传统图像检索方法进行图像 检索。 Ｓｕｎ 等［６ ６ ］ 也提出将草图识别用于加强草图 检索。 可见，将草图的语义用于草图检索可以放宽 用户绘图的相似性要求、增加检索的准确性，也为未 来基于草图的图像检索系统的开发开拓了思路。 ３．２．４ 统一的搜索评价标准 随着手绘草图检索系统的增多，如何判定检索 系统的优劣成为人们关心的问题。 对检索系统的评 价分为检索性能评价和检索效果评价，检索性能包 括检索速度、所需内存空间大小及是否满足平移、旋 转、缩放不变性等。 好的检索系统占用最低的内存 空间，实现海量数据库的实时响应。 检索效果则为 检索出的图片与所画草图的相似程度，一般通过绘 制“查准率⁃查全率曲线” 进行评价，如［３ ３ ⁃３ ５，６ ７ ］ 等。 然而查准率是实验者对检索结果的主观判断，因此 Ｍａｔｈｉａｓ Ｅｉｔｚ ［１３］提出把检索算法对图像的排序与人 的主观感受进行比较的评价标准，用二者之间的相 关性作为检索效果的评价标准。 然而检索系统的优 劣，应该从特征描述的有效性、系统的稳定性和可移 植性、检索性能和效果以及人的主观需求综合考虑， 因此如何形成统一的针对基于手绘草图检索系统的 评价标准仍是一个值得深入研究的问题。 参考文献： ［１］ ＲＵＩ Ｙ， ＴＨＯＭＡＳ Ｓ， ＣＨＡＮＧ Ｓ． Ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ： ｐａｓｔ， ｐｒｅｓｅｎｔ ａｎｄ ｆｕｔｕｒｅ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｖｉｓｕａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｉｍａｇｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ， １９９９， １０（１）： ３９⁃６２． ［２］ ＥＡＫＩＮＳ Ｊ． Ａｕｔｏｍａｔｉｃ ｉｍａｇｅ ｃｏｎｔｅｎｔ ｒｅｔｒｉｅｖａｌ－Ａｒｅ ｗｅ ｇｅｔ⁃ ｔｉｎｇ ａｎｙｗｈｅｒｅ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｏｎｉｃ Ｌｉｂｒａｒｙ ａｎｄ Ｖｉｓｕａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅ⁃ ｓｅａｒｃｈ． Ｎｅｗｃａｓｔｌｅ， Ｕｎｉｔｅｄ Ｋｉｎｇｄｏｍ， １９９６： １２３⁃１３５． ［３］ ＶＥＬＴＫＡＭＰ Ｒ Ｃ， ＴＡＮＡＳＥ Ｍ． Ｃｏｎｔｅｎｔ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅ⁃ ｔｒｉｅｖａｌ ｓｙｓｔｅｍｓ： ａ ｓｕｒｖｅｙ． ＵＵ⁃ＣＳ⁃２０００⁃３４ ［ Ｒ］． Ｄｅｐｔ ｏｆ Ｃｏｍｐｕｔｉｎｇ Ｓｃｉｅｎｃｅ， Ｕｔｒｅｃｈｔ Ｕｎｉｖｅｒｓｉｔｙ， ２０００． ［４］ ＮＩＢＬＡＣＫ Ｃ， ＢＡＲＢＥＲ Ｒ， ＥＱＵＩＴＺ Ｗ， ｅｔ ａｌ． Ｔｈｅ ＱＢＩＣ ｐｒｏｊｅｃｔ： ｑｕｅｒｙｉｎｇ ｉｍａｇｅｓ ｂｙ ｃｏｎｔｅｎｔ ｕｓｉｎｇ ｃｏｌｏｒ， ｔｅｘｔｕｒｅ， ａｎｄ ｓｈａｐｅ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＳＰＩＥ Ｅｌｅｃｔｒｏｎｉｃ Ｉｍａｇｉｎｇ： Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ． Ｓａｎ Ｊｏｓｅ， Ｃａｎａｄａ， １９９３： １７３⁃ １８７． ［５］ＰＥＮＴＬＡＮＤ Ａ， ＰＩＣＡＲＤ Ｒ Ｗ， ＳＣＬＡＲＯＦＦ Ｓ． Ｐｈｏｔｏｂｏｏｋ： ｃｏｎｔｅｎｔ⁃ｂａｓｅｄ ｍａｎｉｐｕｌａｔｉｏｎ ｏｆ ｉｍａｇｅ ｄａｔａｂａｓｅｓ［ Ｊ］． Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， １９９６， １８（３）： ２３３⁃２５４． ［６］孙正兴，冯桂焕 ，周若鸿．基于草图的人机交互技术研究 进展［Ｊ］． 计算机辅助设计与图形学学报， ２００５， ９（１７）： １８８９⁃１８９９． ＳＵＮ Ｚｈｅｎｇｘｉｎｇ， ＦＥＮＧ Ｇｕｉｈｕａｎ， ＺＨＯＵ Ｒｕｏｈｏｎｇ． Ｔｅｃｈ⁃ ｎｉｑｕｅｓ ｆｏｒ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｕｓｅｒ ｉｎｔｅｒｆａｃｅ： ｒｅｖｉｅｗ ａｎｄ ｒｅｓｅａｒｃｈ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２００５， ９（１７）： １８８９⁃１８９９． ［７］尹婷婷，王丹力，戴国忠． 基于多笔划的草图绘制工具 ［Ｃ］ ／ ／ 第 ５ 届全国普适计算学术会议论文集．北京，中 国， ２００９： ３０８⁃３１２． ＹＩＮ Ｔｉｎｇｔｉｎｇ， ＷＡＮＧ Ｄａｎｌｉ， ＤＡＩ Ｇｕｏｚｈｏｎｇ． Ａ ｓｋｅｔｃｈ ·１７４· 智 能 系 统 学 报 第 １０ 卷