【学术论文】基于手绘草图的图像检索技术研究进展

第10卷第2期 智能系统学报 Vol.10 No.2 2015年4月 CAAI Transactions on Intelligent Systems Apr.2015 D0:10.3969/j.issn.1673-4785.201401045 网s络出版地址：http:/www.cnki.net/kcms/detail/23.1538.TP.20150320.1036.001.html 基于手绘草图的图像检索技术研究进展 辛雨璇，闫子飞 (哈尔滨工业大学机电工程学院，黑龙江哈尔滨150001) 摘要：通过对现阶段基于草图的图像检索相关技术的研究，尝试构建了领域无关的基于手绘草图的图像检索系统 框架，并分别对手绘草图预处理、草图特征表示、草图匹配及图像反馈等系统阶段所涉及的相关技术及其发展进行 梳理，进而对基于手绘草图的图像检索系统的相关应用进行总结，展望了手绘草图检索系统在自然人机交互、普适 计算、大数据背景下的研究趋势。 关键词：手绘草图：特征表示：图像检索；人机交互；大数据 中图分类号：TP391.41文献标志码：A文章编号：1673-4785(2015)02-0167-11 中文引用格式：辛雨璇，闫子飞.基于手绘草图的图像检索技术研究进展[J].智能系统学报，2015,10(2)：167-177. 英文引用格式：XIN Yuxuan,YAN Zifei.Research progress of image retrieval based on hand-drawn sketches[J].CAAI Transac- tions on Intelligent Systems,2015,10(2):167-177. Research progress of image retrieval based on hand-drawn sketches XIN Yuxuan,YAN Zifei (School of Mechatronics Engineering,Harbin Institute of Technology,Harbin 150001,China) Abstract:This paper build a framework for the domain-independent image retrieval system based on hand-drawn sketches by researching the existing sketch-based image retrieval related technologies.The relevant technologies and their development of the involved system stages such as:hand-drawn sketch preprocessing,sketch feature interpre- tation,sketch matching,and image feedback were also outlined.Applications relating to sketch-based image re- trieval were summarized.Finally,the coming trends of the hand-drawn sketch-based image retrieval system under the background of natural user interface,pervasive computing and big data were forecasted. Keywords:hand-drawn sketches;feature interpretation;image retrieval;human-computer interaction;big data 互联网的发展和普及拓宽了人们获取信息的途 这种检索方式，由于人工标注的主观性)，导致检 径，也使得人们处于海量信息世界之中。这些信息 索效果并不理想。20世纪90年代初研究者们又提 不仅包括文字信息，也包括视觉信息。视觉感知是 出基于图像内容的检索方式，通过提取图像的底层 人类从客观世界获取信息的主要来源，也是人们认 特征)，如颜色、纹理等，增加了图像检索的有效 知的一种重要方式。如何从海量图像数据库中快速 性，而随着便捷化，小型化无线设备的发展和“数字 有效地进行信息检索，建立更为有效的图像描述，是 水墨”或电子纸的出现，笔式交互成为了新型人机 人们一直关心的问题。20世纪70年代提出了基于 交互方式之一。人机交互界面由桌面环境模拟了笔 图像文本标注的检索方式，即检索图像的文字表示。 纸的环境，促进了笔式交互的进程，也为利用手绘草 图进行图像检索奠定了基础。基于手绘草图的图像 收稿日期：2014-01-22.网络出版日期：2015-03-20. 检索也属于基于图像内容检索范畴。草图与图像不 基金项目：国家白然科学基金资助项目(61102037)：哈尔滨工业大学 科研创新基金资助项目(HT.NSRF.2015057). 同，草图是人依靠记忆和模仿来进行信息的表达，并 通信作者：闫子飞.E-mail:cszfyan@gmail.com 且勾勒草图是人与生俱来的能力，古代人就会画简

第 １０ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．２ ２０１５ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０１０４５ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０３２０．１０３６．００１．ｈｔｍｌ 基于手绘草图的图像检索技术研究进展 辛雨璇，闫子飞 （哈尔滨工业大学 机电工程学院，黑龙江 哈尔滨 １５０００１） 摘 要：通过对现阶段基于草图的图像检索相关技术的研究，尝试构建了领域无关的基于手绘草图的图像检索系统 框架，并分别对手绘草图预处理、草图特征表示、草图匹配及图像反馈等系统阶段所涉及的相关技术及其发展进行 梳理，进而对基于手绘草图的图像检索系统的相关应用进行总结，展望了手绘草图检索系统在自然人机交互、普适 计算、大数据背景下的研究趋势。 关键词：手绘草图；特征表示；图像检索；人机交互；大数据 中图分类号：ＴＰ３９１．４１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０２⁃０１６７⁃１１ 中文引用格式：辛雨璇，闫子飞． 基于手绘草图的图像检索技术研究进展［Ｊ］． 智能系统学报， ２０１５， １０（２）： １６７⁃１７７． 英文引用格式：ＸＩＮ Ｙｕｘｕａｎ， ＹＡＮ Ｚｉｆｅｉ． Ｒｅｓｅａｒｃｈ ｐｒｏｇｒｅｓｓ ｏｆ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｂａｓｅｄ ｏｎ ｈａｎｄ⁃ｄｒａｗｎ ｓｋｅｔｃｈｅｓ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（２）： １６７⁃１７７． Ｒｅｓｅａｒｃｈ ｐｒｏｇｒｅｓｓ ｏｆ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｂａｓｅｄ ｏｎ ｈａｎｄ⁃ｄｒａｗｎ ｓｋｅｔｃｈｅｓ ＸＩＮ Ｙｕｘｕａｎ， ＹＡＮ Ｚｉｆｅｉ （Ｓｃｈｏｏｌ ｏｆ Ｍｅｃｈａｔｒｏｎｉｃｓ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｈａｒｂｉｎ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｈａｒｂｉｎ １５０００１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｂｕｉｌｄ ａ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｔｈｅ ｄｏｍａｉｎ⁃ｉｎｄｅｐｅｎｄｅｎｔ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｈａｎｄ⁃ｄｒａｗｎ ｓｋｅｔｃｈｅｓ ｂｙ ｒｅｓｅａｒｃｈｉｎｇ ｔｈｅ ｅｘｉｓｔｉｎｇ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｒｅｌａｔｅｄ ｔｅｃｈｎｏｌｏｇｉｅｓ． Ｔｈｅ ｒｅｌｅｖａｎｔ ｔｅｃｈｎｏｌｏｇｉｅｓ ａｎｄ ｔｈｅｉｒ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｔｈｅ ｉｎｖｏｌｖｅｄ ｓｙｓｔｅｍ ｓｔａｇｅｓ ｓｕｃｈ ａｓ： ｈａｎｄ⁃ｄｒａｗｎ ｓｋｅｔｃｈ ｐｒｅｐｒｏｃｅｓｓｉｎｇ， ｓｋｅｔｃｈ ｆｅａｔｕｒｅ ｉｎｔｅｒｐｒｅ⁃ ｔａｔｉｏｎ， ｓｋｅｔｃｈ ｍａｔｃｈｉｎｇ， ａｎｄ ｉｍａｇｅ ｆｅｅｄｂａｃｋ ｗｅｒｅ ａｌｓｏ ｏｕｔｌｉｎｅｄ． Ａｐｐｌｉｃａｔｉｏｎｓ ｒｅｌａｔｉｎｇ ｔｏ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅ⁃ ｔｒｉｅｖａｌ ｗｅｒｅ ｓｕｍｍａｒｉｚｅｄ． Ｆｉｎａｌｌｙ， ｔｈｅ ｃｏｍｉｎｇ ｔｒｅｎｄｓ ｏｆ ｔｈｅ ｈａｎｄ⁃ｄｒａｗｎ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｓｙｓｔｅｍ ｕｎｄｅｒ ｔｈｅ ｂａｃｋｇｒｏｕｎｄ ｏｆ ｎａｔｕｒａｌ ｕｓｅｒ ｉｎｔｅｒｆａｃｅ， ｐｅｒｖａｓｉｖｅ ｃｏｍｐｕｔｉｎｇ ａｎｄ ｂｉｇ ｄａｔａ ｗｅｒｅ ｆｏｒｅｃａｓｔｅｄ． Ｋｅｙｗｏｒｄｓ：ｈａｎｄ⁃ｄｒａｗｎ ｓｋｅｔｃｈｅｓ； ｆｅａｔｕｒｅ ｉｎｔｅｒｐｒｅｔａｔｉｏｎ； ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ； ｈｕｍａｎ⁃ｃｏｍｐｕｔｅｒ ｉｎｔｅｒａｃｔｉｏｎ； ｂｉｇ ｄａｔａ 收稿日期：２０１４⁃０１⁃２２． 网络出版日期：２０１５⁃０３⁃２０． 基金项目：国家自然科学基金资助项目（６１１０２０３７）； 哈尔滨工业大学 科研创新基金资助项目（ＨＩＴ． ＮＳＲＩＦ． ２０１５０５７）． 通信作者：闫子飞． Ｅ⁃ｍａｉｌ：ｃｓｚｆｙａｎ＠ ｇｍａｉｌ．ｃｏｍ． 互联网的发展和普及拓宽了人们获取信息的途 径，也使得人们处于海量信息世界之中。 这些信息 不仅包括文字信息，也包括视觉信息。 视觉感知是 人类从客观世界获取信息的主要来源，也是人们认 知的一种重要方式。 如何从海量图像数据库中快速 有效地进行信息检索，建立更为有效的图像描述，是 人们一直关心的问题。 ２０ 世纪 ７０ 年代提出了基于 图像文本标注的检索方式，即检索图像的文字表示。 这种检索方式，由于人工标注的主观性［１］ ，导致检 索效果并不理想。 ２０ 世纪 ９０ 年代初研究者们又提 出基于图像内容的检索方式，通过提取图像的底层 特征［１］ ，如颜色、纹理等，增加了图像检索的有效 性，而随着便捷化，小型化无线设备的发展和“数字 水墨”或电子纸的出现，笔式交互成为了新型人机 交互方式之一。 人机交互界面由桌面环境模拟了笔 纸的环境，促进了笔式交互的进程，也为利用手绘草 图进行图像检索奠定了基础。 基于手绘草图的图像 检索也属于基于图像内容检索范畴。 草图与图像不 同，草图是人依靠记忆和模仿来进行信息的表达，并 且勾勒草图是人与生俱来的能力，古代人就会画简

·168. 智能系统学报 第10卷 图，因此利用手绘草图进行图像检索更接近自然的 无关即通用的图像检索框架：并对该框架所涉及的 人机交互方式。然而图像间的相似性不仅仅建立在 相关技术进行了较详细的归纳：对手绘草图检索系 颜色、纹理等特征)的基础上，Eakins[)]根据检索的 统现阶段的应用进行总结：并展望了手绘草图检索 复杂性将用户查询分成了3个层次，其中第1层次 系统在草图特征表示、多通道输入、检索机制和系统 为视觉相似检索，第2、3层为语义图像检索。视觉 评价的建立等方面在未来的研究趋势。 相似检索主要利用图像的形状信息检索，语义图像 1手绘草图检索系统概述 检索的目的则是使计算机在检索图像时拥有接近人 的理解水平。目前基于内容的图像检索结合相关领 在对大量基于手绘草图检索系统分析的基础 域语义知识已经取得大量的研究成果)，但都分别 上，本文提出了手绘草图检索系统框架图，基于手绘 针对某一特定领域（即领域相关）处理，典型的包 草图的图像检索系统框架一般可分为手绘输入模 括：IBM的QBIC4]系统、MT的PhotoBook)系统 块、手绘草图预处理模块、草图特征表示模块、草图 等。基于草图的图像检索也取得了很多进展。孙正 特征匹配模块、图像反馈模块、数据库模块等6个阶 兴6)对基于草图的人机交互技术早期的研究进展 段，如图1所示。现有手绘草图系统的草图特征表 进行了归纳和总结，并提出了基于草图的人机交互 示阶段根据特征提取单元不同一般可分为基于笔划 系统模型，此模型高度概括了当时绝大多数的基于 描述的草图特征表示、基于组合图形的草图特征表 草图的人机交互技术及应用，但这些应用大部分依 示和基于形状特征的草图特征表示。图像反馈模块 赖于领域知识，只能应用到特定的领域。而本文针 主要体现在对查询结果进行反馈、通过机器学习方 对基于草图的人机交互技术的图像检索领域，主要 法度量用户绘制意图等方面。 利用视觉信息，并结合语义知识检索，尝试建立领域 手绘输人模块 手绘草图预处理模块 草图特征表示模块 草图特征匹配模块 图像反馈模块 用 基于笔划描述 草图 交互界 预处理 基于组合图形 匹配 反馈 基于形状特征 面 数据库模块 在线 预处理 建立索引 草图数据库 离线 草图特征库 图1 基于手绘草图的图像检索系统框架图 Fig.I The system framework of hand-drawn sketch-based image retrieval 1.1手绘草图的预处理 添加了笔划合并以及多旋转检测。笔划合并和多旋 对手绘草图的预处理主要用于消除由用户绘图 转检测都考虑了多笔划输入的情况。汪文睿等[] 习惯不同以及草图固有的随意性而引发的噪声。噪 还提出了对草图笔划进行简化的思想，并将对带阴 声处理包括曲线闭合处理、冗余点去除、笔划合并 影区域的草图的处理称为草图简化，通过测量笔划 等。不同的手绘草图检索系统采用不同的草图预处 密度进行阴影区域的判断。 理方法，为草图特征表示阶段做准备。下面分别介 基于组合图形的草图特征表示，主要考虑图元 绍基于笔划描述的草图特征表示、基于组合图形的 间的位置关系，因此在预处理阶段，首先将图形分割 草图特征表示和基于形状特征的草图特征表示所对 为基本图元（圆形、三角形等），然后对基本图元进 应的预处理方法。 行噪声处理。孙正兴等)认为对基本图元的噪声 基于笔划描述的草图预处理阶段主要对草图笔 处理主要包括冗余点去除、聚点消除、端点校正和闭 划进行处理：采样、冗余点去除、平滑处理，并计算笔 包计算。冗余点通过设定某个结点到相邻结点的阈 划的特征值，比如方向等信息[7-)。李雪峰等[)还 值进行判断。而聚点是那些点密度较大的点，通过

图，因此利用手绘草图进行图像检索更接近自然的 人机交互方式。 然而图像间的相似性不仅仅建立在 颜色、纹理等特征［１］的基础上，Ｅａｋｉｎｓ ［２］根据检索的 复杂性将用户查询分成了 ３ 个层次，其中第 １ 层次 为视觉相似检索，第 ２、３ 层为语义图像检索。 视觉 相似检索主要利用图像的形状信息检索，语义图像 检索的目的则是使计算机在检索图像时拥有接近人 的理解水平。 目前基于内容的图像检索结合相关领 域语义知识已经取得大量的研究成果［３］ ，但都分别 针对某一特定领域（即领域相关） 处理，典型的包 括：ＩＢＭ 的 ＱＢＩＣ ［４］ 系统、ＭＩＴ 的 ＰｈｏｔｏＢｏｏｋ ［５］ 系统 等。 基于草图的图像检索也取得了很多进展。 孙正 兴［６］对基于草图的人机交互技术早期的研究进展 进行了归纳和总结，并提出了基于草图的人机交互 系统模型，此模型高度概括了当时绝大多数的基于 草图的人机交互技术及应用，但这些应用大部分依 赖于领域知识，只能应用到特定的领域。 而本文针 对基于草图的人机交互技术的图像检索领域，主要 利用视觉信息，并结合语义知识检索，尝试建立领域 无关即通用的图像检索框架；并对该框架所涉及的 相关技术进行了较详细的归纳；对手绘草图检索系 统现阶段的应用进行总结；并展望了手绘草图检索 系统在草图特征表示、多通道输入、检索机制和系统 评价的建立等方面在未来的研究趋势。 １ 手绘草图检索系统概述 在对大量基于手绘草图检索系统分析的基础 上，本文提出了手绘草图检索系统框架图，基于手绘 草图的图像检索系统框架一般可分为手绘输入模 块、手绘草图预处理模块、草图特征表示模块、草图 特征匹配模块、图像反馈模块、数据库模块等 ６ 个阶 段，如图 １ 所示。 现有手绘草图系统的草图特征表 示阶段根据特征提取单元不同一般可分为基于笔划 描述的草图特征表示、基于组合图形的草图特征表 示和基于形状特征的草图特征表示。 图像反馈模块 主要体现在对查询结果进行反馈、通过机器学习方 法度量用户绘制意图等方面。 图 １ 基于手绘草图的图像检索系统框架图 Ｆｉｇ．１ Ｔｈｅ ｓｙｓｔｅｍ ｆｒａｍｅｗｏｒｋ ｏｆ ｈａｎｄ⁃ｄｒａｗｎ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ １．１ 手绘草图的预处理 对手绘草图的预处理主要用于消除由用户绘图 习惯不同以及草图固有的随意性而引发的噪声。 噪 声处理包括曲线闭合处理、冗余点去除、笔划合并 等。 不同的手绘草图检索系统采用不同的草图预处 理方法，为草图特征表示阶段做准备。 下面分别介 绍基于笔划描述的草图特征表示、基于组合图形的 草图特征表示和基于形状特征的草图特征表示所对 应的预处理方法。 基于笔划描述的草图预处理阶段主要对草图笔 划进行处理：采样、冗余点去除、平滑处理，并计算笔 划的特征值，比如方向等信息［７－８］ 。 李雪峰等［９］ 还 添加了笔划合并以及多旋转检测。 笔划合并和多旋 转检测都考虑了多笔划输入的情况。 汪文睿等［１０］ 还提出了对草图笔划进行简化的思想，并将对带阴 影区域的草图的处理称为草图简化，通过测量笔划 密度进行阴影区域的判断。 基于组合图形的草图特征表示，主要考虑图元 间的位置关系，因此在预处理阶段，首先将图形分割 为基本图元（圆形、三角形等），然后对基本图元进 行噪声处理。 孙正兴等［１１］ 认为对基本图元的噪声 处理主要包括冗余点去除、聚点消除、端点校正和闭 包计算。 冗余点通过设定某个结点到相邻结点的阈 值进行判断。 而聚点是那些点密度较大的点，通过 ·１６８· 智 能 系 统 学 报 第 １０ 卷

第2期 辛雨璇，等：基于手绘草图的图像检索技术研究进展 ·169. 计算草图，点密度并设定密度的阈值进行聚点的判 关系进行笔划的自动成组。在草图特征表示方面， 断，并用重心代替消除。端点校正则是处理起点和 他采用朴素贝叶斯分类器，在离线情况下对草图和 终点难重合的情况。处理方法为：将顶点边反向延 样本分割，得到基本图元，然后计算一个六维度特征 长交叉，交叉部分比例小于阈值则删除。闭包计算， 向量，最后对用户草图得到的特征向量和样本特征 利用平面点集的闭包算法将凹多边形变为凸多边 向量分布进行比较，完成笔划集的特征表示。 形，为后期图元拟合做准备。 在线特征提取与用户的书写绘画过程同时 而基于形状特征的草图特征表示大部分以提取 开始、同时结束。用户可以及时了解计算机是否 轮廓特征为主，因此，在预处理阶段，常采用八连通 正确认识自己的意图。随着用户的输入，新像素 区域自适应追踪算法来获得草图边界轮廓[]。龚 点加入，特征也随之更新，计算机应找到与当前 健等[]在此基础上改进，提出基于四向连通种子 特征最匹配的图形。早期的研究，只能匹配几种 填充的封闭性判断算法进行封闭性判断。然后对于 几何图形[1]或算法复杂度高[20]。李俊峰等2) 封闭和非封闭的区域，分别用不同的算法提取轮廓。 提出增量式意图提取的草图识别算法采用增量 此外，Eiz等3]还提出应用Canny边缘检测，并设 式意图提取的方式理解用户的勾画意图。增量 定像素位置距离标准差去除不属于草图的线。然而 式意图提取通过不断收集用户的输入信息，并分 Canny算法仅利用了图像的亮度信息，而Berke- 析历史记录，然后对现有信息进行分析，进而根 ley边缘检测算法综合利用了图像的亮度、色度和 据当前信息修正以前生成的意图段落，是一个迭 纹理三方面的信息，计算出每个像素作为边界的概 代的问题求解过程。实验证明，增量式意图提取 率并用图中每个像素点的灰度值表示，得到概率图。 通过迭代的修正笔划，可以识别多种输入图形。 这种表示方式与人对图像轮廓的理解更相近。 近期，微软公开了一种基于手绘草图的在线图像 1.2草图的特征表示 检索引擎一MindFinder[22】,它将由笔划形成的 草图特征表示旨在描述预处理后草图的特征。 线条所包含的形状信息转化为一种由像素坐标 本文根据特征提取单元不同，将草图特征表示方法 与方向角共同表示的边缘像素词典，简化对形状 分为：基于笔划描述的草图特征表示、基于组合图形 特征的描述的同时保持了轮廓的空间信息。之 的草图特征表示和基于形状特征的草图特征表示。 后，上海交通大学[]在MinderFinder基础上做了 1.2.1基于笔划描述的草图特征表示 改进，它认为提取的笔划的方向角特征中包含冗 由于笔式交互以笔划为绘制基本单元，因此，可 余信息，不能准确地描述草图的轮廓信息。通过 以提取笔划的特征来表示草图。对笔划的特征提取 将方向图组合为轮廓显著性图，并分别对主要区 分为离线特征提取和在线特征提取。离线特征提取 域和感兴趣区域进行查找可以克服MinderFinder 即在用户抬笔后，特征提取才开始。早期基于笔划 不能找到位置、大小相差较大的场景图像的情 的特征表示，不仅是离线特征提取，还需要训练用户 况。然而基于笔划描述的特征表示方法，无论在 手势。手绘草图匹配的难易与用户草图绘制的自由 进行离线、在线特征提取后都难以找到图形的唯 度相关，对用户输入限制越多的草图，匹配越准确。 一表示，并且对于笔划复杂的图形，适应性较差， 如1991年Rubine等1s)提出手势特征提取工具 仍需进一步提高笔划特征的可分辨性。 GRANDMA,通过学习指定的单笔划手势，构造手势 1.2.2基于组合图元的草图特征表示 识别器来表示特征，该方法采用包围盒对角线的长 在用户的实际应用中，所要检索的图形有可能 度及倾斜度、起点与终点的距离等11个几何特征和 是种类繁多的一个或多个图元构成的复杂图形。而 笔划的最大速度值、起点到终点的时间值2个动态 多个图元构成的复杂草图可以利用组合图元来表示 特征来描述单笔划图形。Rubin的工作后来被 草图特征。 Long6延伸，他提出新的特征集合，但仍然需要严 基于组合图元的草图特征表示，在预处理阶段 格的训练，即用户要用同样的方式（逆时针画圆和 已经完成了图元分割、噪声的处理。特征表示阶段， 顺时针认为不同)绘图。为了减少对用户输入的限 对基本图元进行识别，最终利用图元间的空间关系 制，Hse等]提出用Zernike矩描述子来描述用户 进行检索。图元识别是寻找与输入草图最相近并接 输入的笔划，这种方法与笔划顺序、完成同一个图形 近用户输入的图形。对于图元的识别已经有很多研 的笔划数量和方向无关，同时满足平移、缩放和旋转 究。如Revankar等2提出用独立的几何模型去识 的不变性。此后孙正兴等[1]提出使用笔划的空间 别和修正手绘的几何草图，用图表示线的关系，并设

计算草图点密度并设定密度的阈值进行聚点的判 断，并用重心代替消除。 端点校正则是处理起点和 终点难重合的情况。 处理方法为：将顶点边反向延 长交叉，交叉部分比例小于阈值则删除。 闭包计算， 利用平面点集的闭包算法将凹多边形变为凸多边 形，为后期图元拟合做准备。 而基于形状特征的草图特征表示大部分以提取 轮廓特征为主，因此，在预处理阶段，常采用八连通 区域自适应追踪算法来获得草图边界轮廓［１２］ 。 龚 健 等［１２］在此基础上改进，提出基于四向连通种子 填充的封闭性判断算法进行封闭性判断。 然后对于 封闭和非封闭的区域，分别用不同的算法提取轮廓。 此外，Ｅｉｔｚ 等［１３］ 还提出应用 Ｃａｎｎｙ 边缘检测，并设 定像素位置距离标准差去除不属于草图的线。 然而 Ｃａｎｎｙ 算法仅利用了图像的亮度信息， 而 Ｂｅｒｋｅ⁃ ｌｅｙ ［１４］边缘检测算法综合利用了图像的亮度、色度和 纹理三方面的信息，计算出每个像素作为边界的概 率并用图中每个像素点的灰度值表示，得到概率图。 这种表示方式与人对图像轮廓的理解更相近。 １．２ 草图的特征表示 草图特征表示旨在描述预处理后草图的特征。 本文根据特征提取单元不同，将草图特征表示方法 分为：基于笔划描述的草图特征表示、基于组合图形 的草图特征表示和基于形状特征的草图特征表示。 １．２．１ 基于笔划描述的草图特征表示 由于笔式交互以笔划为绘制基本单元，因此，可 以提取笔划的特征来表示草图。 对笔划的特征提取 分为离线特征提取和在线特征提取。 离线特征提取 即在用户抬笔后，特征提取才开始。 早期基于笔划 的特征表示，不仅是离线特征提取，还需要训练用户 手势。 手绘草图匹配的难易与用户草图绘制的自由 度相关，对用户输入限制越多的草图，匹配越准确。 如 １９９１ 年 Ｒｕｂｉｎｅ 等［１５］ 提出手势特征提取工具 ＧＲＡＮＤＭＡ，通过学习指定的单笔划手势，构造手势 识别器来表示特征，该方法采用包围盒对角线的长 度及倾斜度、起点与终点的距离等 １１ 个几何特征和 笔划的最大速度值、起点到终点的时间值 ２ 个动态 特征 来 描 述 单 笔 划 图 形。 Ｒｕｂｉｎ 的 工 作 后 来 被 Ｌｏｎｇ ［１６］延伸，他提出新的特征集合，但仍然需要严 格的训练，即用户要用同样的方式（逆时针画圆和 顺时针认为不同）绘图。 为了减少对用户输入的限 制，Ｈｓｅ 等［１７］ 提出用 Ｚｅｒｎｉｋｅ 矩描述子来描述用户 输入的笔划，这种方法与笔划顺序、完成同一个图形 的笔划数量和方向无关，同时满足平移、缩放和旋转 的不变性。 此后孙正兴等［１８］ 提出使用笔划的空间 关系进行笔划的自动成组。 在草图特征表示方面， 他采用朴素贝叶斯分类器，在离线情况下对草图和 样本分割，得到基本图元，然后计算一个六维度特征 向量，最后对用户草图得到的特征向量和样本特征 向量分布进行比较，完成笔划集的特征表示。 在线特征提取与用户的书写绘画过程同时 开始、同时结束。 用户可以及时了解计算机是否 正确认识自己的意图。 随着用户的输入，新像素 点加入，特征也随之更新，计算机应找到与当前 特征最匹配的图形。 早期的研究，只能匹配几种 几何图形［ １９］ 或算法复杂度高［ ２０］ 。 李俊峰等［ ２１］ 提出增量式意图提取的草图识别算法采用增量 式意图提取的方式理解用户的勾画意图。 增量 式意图提取通过不断收集用户的输入信息，并分 析历史记录，然后对现有信息进行分析，进而根 据当前信息修正以前生成的意图段落，是一个迭 代的问题求解过程。 实验证明，增量式意图提取 通过迭代的修正笔划，可以识别多种输入图形。 近期，微软公开了一种基于手绘草图的在线图像 检索引擎———ＭｉｎｄＦｉｎｄｅｒ ［ ２２］ ，它将由笔划形成的 线条所包含的形状信息转化为一种由像素坐标 与方向角共同表示的边缘像素词典，简化对形状 特征的描述的同时保持了轮廓的空间信息。 之 后，上海交通大学［ ２３］ 在 ＭｉｎｄｅｒＦｉｎｄｅｒ 基础上做了 改进，它认为提取的笔划的方向角特征中包含冗 余信息，不能准确地描述草图的轮廓信息。 通过 将方向图组合为轮廓显著性图，并分别对主要区 域和感兴趣区域进行查找可以克服 ＭｉｎｄｅｒＦｉｎｄｅｒ 不能找到位置、大小相差较大的场 景 图 像 的 情 况。 然而基于笔划描述的特征表示方法，无论在 进行离线、在线特征提取后都难以找到图形的唯 一表示，并且对于笔划复杂的图形，适应性较差， 仍需进一步提高笔划特征的可分辨性。 １．２．２ 基于组合图元的草图特征表示 在用户的实际应用中，所要检索的图形有可能 是种类繁多的一个或多个图元构成的复杂图形。 而 多个图元构成的复杂草图可以利用组合图元来表示 草图特征。 基于组合图元的草图特征表示，在预处理阶段 已经完成了图元分割、噪声的处理。 特征表示阶段， 对基本图元进行识别，最终利用图元间的空间关系 进行检索。 图元识别是寻找与输入草图最相近并接 近用户输入的图形。 对于图元的识别已经有很多研 究。 如 Ｒｅｖａｎｋａｒ 等［２４］ 提出用独立的几何模型去识 别和修正手绘的几何草图，用图表示线的关系，并设 第 ２ 期 辛雨璇，等：基于手绘草图的图像检索技术研究进展 ·１６９·

·170· 智能系统学报 第10卷 定连通性、相对方向、相等和平行性的阈值判断来确 图元的空间关系。而基于形状特征的特征表示，着 定线与线的关系去修正手绘笔划，使其更接近用户 眼于草图自身的外在形状特征。早期的研究采用闭 想画的图形。Sezgin等2)提出的系统用探测最高 包盒大小、最大内接三角形、或傅里叶描述子等作为 曲率和最低速度点的方式去识别图形。但是Sezgin 形状特征表示[93)，检索效率低，时间复杂度高。 的系统仅可以识别出简单的几何图元，包括直线、圆 之后很多研究主要在草图轮廓的基础上提取轮廓的 和由直线和曲线组成的简单合成图形。而Yu等[2 全局特征或局部特征作为草图的形状特征表示。全 提出的领域无关的草图识别系统，对图元的识别扩 局特征着眼于整幅图像，能更好地描述图像中物体 展到了折线、椭圆、弧和螺旋结构。他认为仅用曲率 的相对位置。如Chee等[]采用MPEG-7标准中提 判定，容易被噪音所误导，因此引入特征面积的概 出的边缘直方图(edge histogram descriptor,EHD), 念，并将方向、曲率和特征面积结合将用户所绘制草 具有描述图像像素变化方向的能力。它通过统计每 图近似为标准的图元。后来Paulson等2提出一个 个子图块含有垂直、水平、45°、135°及无方向5种边 精准的手绘草图识别系统PaleoSketch,他认为像 缘特征形式的个数，形成了五维特征向量，因此 Sezgin和Yu提出的那些简单图形的识别器在手绘 EHD利用5个方向的直方图提取特征，更注重图像 草图领域的通用性不强，很难识别由图表和草图构 的整体信息。但是EHD对于子图和方向的划分十 成的复杂符号。所以Paulson在Sezgin和Yu的基 分粗略，描述轮廓的能力有限。此外，李曼舞等3] 础上，又引入了2个新的特征值，NDDE(normalized 提出对草图预处理后，对质心距离形状描述子进行 distance between direction extremes)DCR(direction 傅里叶变换并除以直流成分生成傅里叶边界描述子 change ratio),NDDE是用总笔划长度除以最高方向 描述草图的形状特征。高竹红等34]在李曼舞的基 值和最低方向值之间的距离，得到方向相反线的百 础上，对生成的傅里叶描述子进行傅里叶反变换再 分比：DCR则是最大方向变化量占平均方向变化量 得到图像轮廓，将轮廓点到质心点进行连接得到轮 的百分比，用于更好地区分折线和曲线，在识别阶段 廓结构图，构造邻接矩阵并提取矩阵的特征向量进 获得较好的效果。此外，孙正兴等)和团队在其开 行检索。而吴明珠等35]提取轮廓成对几何直方图 发的Smart Sketchpad系统中提出用引力模型（认为 作为区域描述子，成对几何直方图是链码编码直方 点与点有相互吸引的趋势)，通过设定阈值将点合 图的一种扩展，是由角度和距离2个维度构成的二 并的方法，对基本图元分类。并提出图元内规整和 维直方图。钱晶等[36]提出使用一种仿射变换自适 图元外规整的方法。例如，判断三角形两边近似等 应骨架提取算法来提取对象骨架，构造骨架树描述 长则规整为等腰三角形的方法为内规整。利用图元 符进行图像表示。最后将图像的骨架特征与轮廓特 间相邻信息，将相近图元规整为相同大小的方法为 征结合进行检索。此后，钱晶等3小在之前只采用 外规整。该系统使用的是识别图元的基本方法。李 形状特征表示的基础上，又结合了颜色和纹理特征 雪峰等)则又对图元进行了扩充，支持直线、折线、 进行表示。为了加快检索速度，对每一个图像特征 圆弧、曲线、同心螺旋线、异心螺旋线、椭圆、圆等8 都使用了粗尺度和细尺度特征。先用粗尺度快速计 种基本图元以及多种图元组成的复杂图形。识别出 算区域相似度，丢弃不匹配的区域：再用细尺度特征 基本图元后，可以将不同复杂层次的图形元素抽象， 完成相似度的精确计算。 从而获得统一的表示。例如组合图形属性包括图形 特别地，Eitz等3]提出著名的特征袋(bag-of 元素类型、坐标、尺寸等。组合图形的空间关系包括 features)描述子，通过对形状内容描述子、星点描述 图形元素的相对位置关系、相对方位、相对旋转等。 子、改进的标准方向梯度直方图描述子分别进行实 张莉莎等[]则提出将复杂图形描述转化为不同信 验和评估发现，改进的标准方向梯度直方图描述子 息粒度的属性和空间关系表示。但草图本身具有模 表现最优。通过随机提取图像中的感兴趣点，以每 糊性和不确定性，加上线条数目繁多，难以对其施加 个感兴趣点的邻域为单元，计算梯度方向直方图并 判断和约束。此外，组合图形越复杂，空间关系的信 取其主方向作为该感兴趣点的边缘特征，最终形成 息维数越多，计算量越大。因此基于组合图元的草 了一个特征袋。Lukas等38]认为之前的系统都缺 图检索还需要依赖相关领域知识和上下文信息简化 少在互联网环境下检索图像的能力，他提出将方向 对复杂组合图形的表示过程。 梯度直方图和离散距离变换(discrete distance trans- 1.2.3基于形状特征的草图特征表示 formation,DDT)相结合的方法实现在线检索，通过 基于组合图形的草图特征表示，着眼于草图中 对小数据库和较大数据库进行实验都取得了良好的

定连通性、相对方向、相等和平行性的阈值判断来确 定线与线的关系去修正手绘笔划，使其更接近用户 想画的图形。 Ｓｅｚｇｉｎ 等［２５］ 提出的系统用探测最高 曲率和最低速度点的方式去识别图形。 但是 Ｓｅｚｇｉｎ 的系统仅可以识别出简单的几何图元，包括直线、圆 和由直线和曲线组成的简单合成图形。 而 Ｙｕ 等［２６］ 提出的领域无关的草图识别系统，对图元的识别扩 展到了折线、椭圆、弧和螺旋结构。 他认为仅用曲率 判定，容易被噪音所误导，因此引入特征面积的概 念，并将方向、曲率和特征面积结合将用户所绘制草 图近似为标准的图元。 后来 Ｐａｕｌｓｏｎ 等［２７］提出一个 精准的手绘草图识别系统 ＰａｌｅｏＳｋｅｔｃｈ，他认为像 Ｓｅｚｇｉｎ 和 Ｙｕ 提出的那些简单图形的识别器在手绘 草图领域的通用性不强，很难识别由图表和草图构 成的复杂符号。 所以 Ｐａｕｌｓｏｎ 在 Ｓｅｚｇｉｎ 和 Ｙｕ 的基 础上，又引入了 ２ 个新的特征值，ＮＤＤＥ （ ｎｏｒｍａｌｉｚｅｄ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｄｉｒｅｃｔｉｏｎ ｅｘｔｒｅｍｅｓ）和 ＤＣＲ（ｄｉｒｅｃｔｉｏｎ ｃｈａｎｇｅ ｒａｔｉｏ）， ＮＤＤＥ 是用总笔划长度除以最高方向 值和最低方向值之间的距离，得到方向相反线的百 分比；ＤＣＲ 则是最大方向变化量占平均方向变化量 的百分比，用于更好地区分折线和曲线，在识别阶段 获得较好的效果。 此外，孙正兴等［１１］ 和团队在其开 发的 Ｓｍａｒｔ Ｓｋｅｔｃｈｐａｄ 系统中提出用引力模型（认为 点与点有相互吸引的趋势），通过设定阈值将点合 并的方法，对基本图元分类。 并提出图元内规整和 图元外规整的方法。 例如，判断三角形两边近似等 长则规整为等腰三角形的方法为内规整。 利用图元 间相邻信息，将相近图元规整为相同大小的方法为 外规整。 该系统使用的是识别图元的基本方法。 李 雪峰等［９］则又对图元进行了扩充，支持直线、折线、 圆弧、曲线、同心螺旋线、异心螺旋线、椭圆、圆等 ８ 种基本图元以及多种图元组成的复杂图形。 识别出 基本图元后，可以将不同复杂层次的图形元素抽象， 从而获得统一的表示。 例如组合图形属性包括图形 元素类型、坐标、尺寸等。 组合图形的空间关系包括 图形元素的相对位置关系、相对方位、相对旋转等。 张莉莎等［２８］则提出将复杂图形描述转化为不同信 息粒度的属性和空间关系表示。 但草图本身具有模 糊性和不确定性，加上线条数目繁多，难以对其施加 判断和约束。 此外，组合图形越复杂，空间关系的信 息维数越多，计算量越大。 因此基于组合图元的草 图检索还需要依赖相关领域知识和上下文信息简化 对复杂组合图形的表示过程。 １．２．３ 基于形状特征的草图特征表示 基于组合图形的草图特征表示，着眼于草图中 图元的空间关系。 而基于形状特征的特征表示，着 眼于草图自身的外在形状特征。 早期的研究采用闭 包盒大小、最大内接三角形、或傅里叶描述子等作为 形状特征表示［２９⁃３１］ ，检索效率低，时间复杂度高。 之后很多研究主要在草图轮廓的基础上提取轮廓的 全局特征或局部特征作为草图的形状特征表示。 全 局特征着眼于整幅图像，能更好地描述图像中物体 的相对位置。 如 Ｃｈｅｅ 等［３２］采用 ＭＰＥＧ⁃７ 标准中提 出的边缘直方图（ｅｄｇｅ ｈｉｓｔｏｇｒａｍ ｄｅｓｃｒｉｐｔｏｒ， ＥＨＤ） ， 具有描述图像像素变化方向的能力。 它通过统计每 个子图块含有垂直、水平、４５°、１３５°及无方向 ５ 种边 缘特征形式的个数， 形成了五维特征向量， 因此 ＥＨＤ 利用 ５ 个方向的直方图提取特征，更注重图像 的整体信息。 但是 ＥＨＤ 对于子图和方向的划分十 分粗略，描述轮廓的能力有限。 此外，李曼舞等［３ ３ ］ 提出对草图预处理后，对质心距离形状描述子进行 傅里叶变换并除以直流成分生成傅里叶边界描述子 描述草图的形状特征。 高竹红等［３ ４ ］ 在李曼舞的基 础上，对生成的傅里叶描述子进行傅里叶反变换再 得到图像轮廓，将轮廓点到质心点进行连接得到轮 廓结构图，构造邻接矩阵并提取矩阵的特征向量进 行检索。 而吴明珠等［３ ５ ］ 提取轮廓成对几何直方图 作为区域描述子，成对几何直方图是链码编码直方 图的一种扩展，是由角度和距离 ２ 个维度构成的二 维直方图。 钱晶等［３ ６ ］ 提出使用一种仿射变换自适 应骨架提取算法来提取对象骨架，构造骨架树描述 符进行图像表示。 最后将图像的骨架特征与轮廓特 征结合进行检索。 此后，钱晶等［３ ７ ］ 在之前只采用 形状特征表示的基础上，又结合了颜色和纹理特征 进行表示。 为了加快检索速度，对每一个图像特征 都使用了粗尺度和细尺度特征。 先用粗尺度快速计 算区域相似度，丢弃不匹配的区域；再用细尺度特征 完成相似度的精确计算。 特别地，Ｅｉｔｚ 等［１３］ 提出著名的特征袋（ ｂａｇ⁃ｏｆ⁃ ｆｅａｔｕｒｅｓ）描述子，通过对形状内容描述子、星点描述 子、改进的标准方向梯度直方图描述子分别进行实 验和评估发现， 改进的标准方向梯度直方图描述子 表现最优。 通过随机提取图像中的感兴趣点，以每 个感兴趣点的邻域为单元，计算梯度方向直方图并 取其主方向作为该感兴趣点的边缘特征，最终形成 了一个特征袋。 Ｌｕｋａｓ 等［３ ８ ］ 认为之前的系统都缺 少在互联网环境下检索图像的能力，他提出将方向 梯度直方图和离散距离变换（ｄｉｓｃｒｅｔｅ ｄｉｓｔａｎｃｅ ｔｒａｎｓ⁃ ｆｏｒｍａｔｉｏｎ，ＤＤＴ）相结合的方法实现在线检索，通过 对小数据库和较大数据库进行实验都取得了良好的 ·１７０· 智 能 系 统 学 报 第 １０ 卷

第2期 辛雨璇，等：基于手绘草图的图像检索技术研究进展 ·171· 效果。然而，基于形状特征的草图特征表示难以区 向的倒角匹配(indexable oriented chamfer matc- 分形状相似的不同物体，因此.，还需要结合语义对图 hing)22】,节约了物理花销并具有局部形状不变性。 形分类或者利用草图识别提高检索精度。 1.4图像反馈 1.3草图的特征匹配 利用视觉信息检索，能够增加检索的有效性，却 为了加快检索速度，需要对图像库也进行预处 造成视觉信息和高层语义之间的鸿沟。为了架起高 理，形成图像特征库。将草图的特征和图像特征库 层语义和底层特征的桥梁，需要对草图检索结果进 进行匹配，即特征匹配阶段。对图像库预处理首先 行语义提取。反馈是语义提取的一个重要方面，主 缩小图像库中图像大小，然后一般采用与输入草图 要包括对查询结果进行反馈、通过机器学习方法度 同样的处理方法对库中的图像进行预处理和特征提 量用户的绘制意图等方面。早期的反馈多采用查询 取。匹配时，需要根据不同的草图特征表示方法找 点移动策略[45]或权值再计算。通过重新排列检索 到合适的相似度计算方法。基于笔划描述的草图检 结果来改善检索效率，虽然这种反馈对系统而言无 索方法，大部分采用转换为计算特征向量之间相似 本质的提高，但是用户在搜索结果上的行为数据是 性度量的方法，其中欧式距离由于计算简单、效果 分析用户心理的重要数据来源，如何基于这些数据 好，被许多系统采用2.36-3]。也可以表示为点的序 提高排序质量，也是一个值得研究的问题。 列，计算2个序列中相对位置相同项占所有项的比 后来的反馈系统引入机器学习方法。例如引入 例，即相关系数法【，9-40)。基于组合图元的特征 SVM学习方法[146]，一些检索系统采用经典的二 表示，在识别基本图元后，首先要进行图元成组。然 值SVM或单类SVM分类器。然而二值SVM忽略 后进行部分结构相似性计算和整体相似性计算。部 正反例数量不对称的情况，而单类SVM则对反例信 分结构相似性计算包括图形构成相似性计算和图形 息不适用。因此应用这2种经典的SVM得到的检 骨架间的相似性计算山。实质上就是把图元构成 索效果都不理想。梁爽等[46]在此基础上提出了有 和骨架结点都转换为多维向量或结点数组的计算。 偏SVM,通过学习用户对草图的理解和主观评价， 还可以基于空间关系计算组合图元的相似度，将空 并实时捕捉用户的查询兴趣，使搜索的结果更加接 近用户的意图。袁贞明等[47]通过计算草图结构中 间关系转化为空间拓扑图和层次结构图，用拉普拉 斯图谱转换为特征向量41-42】。最后利用欧式距离 贝叶斯网络拓扑结构的最大后验概率，根据用户输 进行相似度计算4)。对于复杂的组合图形的检索 入的笔划信息对笔划进行动态最优分组，保证了笔 方法，可以在匹配阶段，找到源空间关系图和目标空 划输入的连续性，提高了分组效率。裴继红等4) 提出带反馈机制的闭环隐马尔可夫模型，采用带压 间关系图的映射关系，但是匹配复杂度很高。也可 缩率调整因子的特征压缩算法，在计算各个后验概 以采取约束的部分枚举算法[28】，满足顶点匹配约 率后进行满意度判断，以确定是否调整压缩因子。 束或边匹配约束的序列可以从当前状态略去无效序 裴继红将这种方法应用于手绘图形的识别，通过实 列直接到达后继状态，节省了大量的计算。此外，基 验证明带反馈机制的闭环隐马尔可夫比开环隐马尔 于形状特征的草图特征表示除了转化为向量特征表 可夫有更高的识别率。然而目前机器学习的方法并 示，还包括直方图特征表示和骨架特征表示。基于 没有人工标注图像的方法发展的成熟，因此可以采 直方图特征的草图匹配可以采用复杂度很低的直方 用人工标注的方法辅助检索，缩小检索范用，例如 图相交算法来计算直方图的距离35]，数值越小，相 Sketch2 Photo[s2]首先用关键字查找，然后再提取草 似度越高。基于骨架特征的草图匹配，对骨架树的 图特征进一步查找。总之，利用人工标注图像语义 分支分别计算相似度，对于子节点需要由分支相似 的方法极大地缩小了视觉信息和语义的鸿沟，仍然 距离计算节点相似距离，最后由上述结果根据各自 被广泛采用。 权重相加计算骨架树相似距离[36-37]。MindFind- er22]中，提出倒角匹配(chamfer matching)a3]和定 2手绘草图检索系统现阶段的应用 向的倒角匹配(oriented chamfer matching)方法[)， 现有基于手绘草图的检索技术的相关文章大多 但前者时间复杂度高，后者内存花销大。因此，该文 可归为于本文所总结系统框架的某个或某几个模块 将利用定向的倒角匹配生成的草图线条距离图转变 的研究范畴。通过对之前研究的分析，提出手绘草 为有N个方向通道的击中映射图(hit map),并验证 图的手绘草图检索系统框架，旨在建立领域无关的 待匹配图像中是否有某个边缘像素(edg©l)与草图 手绘草图检索系统，从而将草图检索系统应用于更 线条映射图中的点相似。这种方法称为可索引的定 广阔的领域。本文现将基于手绘草图的检索系统现

效果。 然而，基于形状特征的草图特征表示难以区 分形状相似的不同物体，因此，还需要结合语义对图 形分类或者利用草图识别提高检索精度。 １．３ 草图的特征匹配 为了加快检索速度，需要对图像库也进行预处 理，形成图像特征库。 将草图的特征和图像特征库 进行匹配，即特征匹配阶段。 对图像库预处理首先 缩小图像库中图像大小，然后一般采用与输入草图 同样的处理方法对库中的图像进行预处理和特征提 取。 匹配时，需要根据不同的草图特征表示方法找 到合适的相似度计算方法。 基于笔划描述的草图检 索方法，大部分采用转换为计算特征向量之间相似 性度量的方法，其中欧式距离由于计算简单、效果 好，被许多系统采用［１２，３ ６ －３ ７ ］ 。 也可以表示为点的序 列，计算 ２ 个序列中相对位置相同项占所有项的比 例，即相关系数法 ［１３， ３９ － ４ ０ ］ 。 基于组合图元的特征 表示，在识别基本图元后，首先要进行图元成组。 然 后进行部分结构相似性计算和整体相似性计算。 部 分结构相似性计算包括图形构成相似性计算和图形 骨架间的相似性计算［１１］ 。 实质上就是把图元构成 和骨架结点都转换为多维向量或结点数组的计算。 还可以基于空间关系计算组合图元的相似度，将空 间关系转化为空间拓扑图和层次结构图，用拉普拉 斯图谱转换为特征向量［４ １ －４ ２ ］ 。 最后利用欧式距离 进行相似度计算［４ １ ］ 。 对于复杂的组合图形的检索 方法，可以在匹配阶段，找到源空间关系图和目标空 间关系图的映射关系，但是匹配复杂度很高。 也可 以采取约束的部分枚举算法［２ ８ ］ ，满足顶点匹配约 束或边匹配约束的序列可以从当前状态略去无效序 列直接到达后继状态，节省了大量的计算。 此外，基 于形状特征的草图特征表示除了转化为向量特征表 示，还包括直方图特征表示和骨架特征表示。 基于 直方图特征的草图匹配可以采用复杂度很低的直方 图相交算法来计算直方图的距离［３ ５ ］ ，数值越小，相 似度越高。 基于骨架特征的草图匹配，对骨架树的 分支分别计算相似度，对于子节点需要由分支相似 距离计算节点相似距离，最后由上述结果根据各自 权重相加计算骨架树相似距离［３ ６ －３ ７ ］ 。 ＭｉｎｄＦｉｎｄ⁃ ｅｒ ［２ ２ ］中，提出倒角匹配（ｃｈａｍｆｅｒ ｍａｔｃｈｉｎｇ） ［４ ３ ］和定 向的倒角匹配（ｏｒｉｅｎｔｅｄ ｃｈａｍｆｅｒ ｍａｔｃｈｉｎｇ）方法［４ ４ ］ ， 但前者时间复杂度高，后者内存花销大。 因此，该文 将利用定向的倒角匹配生成的草图线条距离图转变 为有 Ｎ 个方向通道的击中映射图（ｈｉｔ ｍａｐ），并验证 待匹配图像中是否有某个边缘像素（ ｅｄｇｅｌ） 与草图 线条映射图中的点相似。 这种方法称为可索引的定 向的 倒 角 匹 配 （ ｉｎｄｅｘａｂｌｅ ｏｒｉｅｎｔｅｄ ｃｈａｍｆｅｒ ｍａｔｃ⁃ ｈｉｎｇ） ［２ ２ ］ ，节约了物理花销并具有局部形状不变性。 １．４ 图像反馈 利用视觉信息检索，能够增加检索的有效性，却 造成视觉信息和高层语义之间的鸿沟。 为了架起高 层语义和底层特征的桥梁，需要对草图检索结果进 行语义提取。 反馈是语义提取的一个重要方面，主 要包括对查询结果进行反馈、通过机器学习方法度 量用户的绘制意图等方面。 早期的反馈多采用查询 点移动策略［４ ５ ］或权值再计算。 通过重新排列检索 结果来改善检索效率，虽然这种反馈对系统而言无 本质的提高，但是用户在搜索结果上的行为数据是 分析用户心理的重要数据来源，如何基于这些数据 提高排序质量，也是一个值得研究的问题。 后来的反馈系统引入机器学习方法。 例如引入 ＳＶＭ 学习方法［１１，４ ６ ］ ，一些检索系统采用经典的二 值 ＳＶＭ 或单类 ＳＶＭ 分类器。 然而二值 ＳＶＭ 忽略 正反例数量不对称的情况，而单类 ＳＶＭ 则对反例信 息不适用。 因此应用这 ２ 种经典的 ＳＶＭ 得到的检 索效果都不理想。 梁爽等［４ ６ ］ 在此基础上提出了有 偏 ＳＶＭ，通过学习用户对草图的理解和主观评价， 并实时捕捉用户的查询兴趣，使搜索的结果更加接 近用户的意图。 袁贞明等［ ４ ７ ］ 通过计算草图结构中 贝叶斯网络拓扑结构的最大后验概率，根据用户输 入的笔划信息对笔划进行动态最优分组，保证了笔 划输入的连续性，提高了分组效率。 裴继红等［４ ８ ］ 提出带反馈机制的闭环隐马尔可夫模型，采用带压 缩率调整因子的特征压缩算法，在计算各个后验概 率后进行满意度判断，以确定是否调整压缩因子。 裴继红将这种方法应用于手绘图形的识别，通过实 验证明带反馈机制的闭环隐马尔可夫比开环隐马尔 可夫有更高的识别率。 然而目前机器学习的方法并 没有人工标注图像的方法发展的成熟，因此可以采 用人工标注的方法辅助检索，缩小检索范围，例如 Ｓｋｅｔｃｈ２Ｐｈｏｔｏ ［５ ２ ］首先用关键字查找，然后再提取草 图特征进一步查找。 总之，利用人工标注图像语义 的方法极大地缩小了视觉信息和语义的鸿沟，仍然 被广泛采用。 ２ 手绘草图检索系统现阶段的应用 现有基于手绘草图的检索技术的相关文章大多 可归为于本文所总结系统框架的某个或某几个模块 的研究范畴。 通过对之前研究的分析，提出手绘草 图的手绘草图检索系统框架，旨在建立领域无关的 手绘草图检索系统，从而将草图检索系统应用于更 广阔的领域。 本文现将基于手绘草图的检索系统现 第 ２ 期 辛雨璇，等：基于手绘草图的图像检索技术研究进展 ·１７１·

172 智能系统学报 第10卷 阶段的应用总结为五方面内容。 1)只利用检索功能，检索出用户需要的图像。目 前草图检索已经实现从2-D图像到3D图像，从小数 据库到百万数据库的检索。如Mindfindert9]系统已 经实现利用手绘草图从在线的百万数据图片中进行 快速检索，并用三维检索结构去减少检索时间，如图 2。而MagicBrusht0]系统还考虑了颜色信息，实现利 用带颜色的草图在百万数据库中的实时检索，如图3 所示。离线情况也可以将搜索完成的图像利用系统 进行合成，用于照片的制作s12】,如图4所示。还可 图5基于人脸位置和属性的图像搜索 以通过简单的图形表示人脸位置和人脸属性，例如指 Fig.5 Image retrieval based on human face location 定是否戴帽子或指定肤色[s3],实现对人脸图像的检 and property 索，如图5所示。此外，i等54]已经实现利用手绘 草图对三维模型的检索，如图6。 syney apera 司 图2利用Mindfinder查找悉尼歌剧院 图6利用草图进行三维模型的检索 Fig.2 Find the Sydney Opera house with Mindfinder Fig.6 Three-dimensional model retrieval by sketches 2)扩展检索功能，用草图检索系统管理图像数 据。例如肖秦琨等55】等用手绘图作为查询条件运 用Zernike矩函数提取图像特征，完成对商标的管理 和检索，用于新商标的设计和检验。周良等[56]提 出利用图匹配方法对工程图纸检索，便于工程图纸 的查找和管理。Tencer等[s7]提出利用草图对文档 中的插图进行检索，如图7所示，对于图文相混合的 大量文档，更便于感兴趣区域的快速定位。 问题 结果 图3 MagicBrush:利用带颜色草图进行检索 7 Fig.3 MagicBrush:sketch retrieval by color sketches 图7利用草图对文档中插图进行检索 Fig.7 Using sketches to retrieve the illustrations in a document 3)利用草图模糊性和不明确性的特点开发特 定应用。可以根据现场目击者和受害者的回忆，手 图4利用草图在数据库中查询并合成图片 绘犯罪嫌疑人的头像，然后通过手绘草图检索系统 Fig.4 Retrieve in the database and synthesis of a pic- 和人脸识别技术，在犯罪嫌疑人的图像库中进行搜 ture by sketches 索从而缩小嫌疑人的范围，以便协助公安机关破案

阶段的应用总结为五方面内容。 １）只利用检索功能，检索出用户需要的图像。 目 前草图检索已经实现从 ２⁃Ｄ 图像到 ３⁃Ｄ 图像，从小数 据库到百万数据库的检索。 如 Ｍｉｎｄｆｉｎｄｅｒ ［ ４９ ］ 系统已 经实现利用手绘草图从在线的百万数据图片中进行 快速检索，并用三维检索结构去减少检索时间，如图 ２。 而 ＭａｇｉｃＢｒｕｓｈ ［ ５０ ］系统还考虑了颜色信息，实现利 用带颜色的草图在百万数据库中的实时检索，如图 ３ 所示。 离线情况也可以将搜索完成的图像利用系统 进行合成，用于照片的制作［５ １ ⁃５ ２ ］ ，如图 ４ 所示。 还可 以通过简单的图形表示人脸位置和人脸属性，例如指 定是否戴帽子或指定肤色［ ５ ３ ］ ，实现对人脸图像的检 索，如图 ５ 所示。 此外，Ｅｉｔｚ 等［５ ４ ］已经实现利用手绘 草图对三维模型的检索，如图 ６。 图 ２ 利用 Ｍｉｎｄｆｉｎｄｅｒ 查找悉尼歌剧院 Ｆｉｇ．２ Ｆｉｎｄ ｔｈｅ Ｓｙｄｎｅｙ Ｏｐｅｒａ ｈｏｕｓｅ ｗｉｔｈ Ｍｉｎｄｆｉｎｄｅｒ 图 ３ ＭａｇｉｃＢｒｕｓｈ：利用带颜色草图进行检索 Ｆｉｇ．３ ＭａｇｉｃＢｒｕｓｈ： ｓｋｅｔｃｈ ｒｅｔｒｉｅｖａｌ ｂｙ ｃｏｌｏｒ ｓｋｅｔｃｈｅｓ 图 ４ 利用草图在数据库中查询并合成图片 Ｆｉｇ．４ Ｒｅｔｒｉｅｖｅ ｉｎ ｔｈｅ ｄａｔａｂａｓｅ ａｎｄ ｓｙｎｔｈｅｓｉｓ ｏｆ ａ ｐｉｃ⁃ ｔｕｒｅ ｂｙ ｓｋｅｔｃｈｅｓ 图 ５ 基于人脸位置和属性的图像搜索 Ｆｉｇ．５ Ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｂａｓｅｄ ｏｎ ｈｕｍａｎ ｆａｃｅ ｌｏｃａｔｉｏｎ ａｎｄ ｐｒｏｐｅｒｔｙ 图 ６ 利用草图进行三维模型的检索 Ｆｉｇ．６ Ｔｈｒｅｅ⁃ｄｉｍｅｎｓｉｏｎａｌ ｍｏｄｅｌ ｒｅｔｒｉｅｖａｌ ｂｙ ｓｋｅｔｃｈｅｓ ２）扩展检索功能，用草图检索系统管理图像数 据。 例如肖秦琨等［５ ５ ］ 等用手绘图作为查询条件运 用 Ｚｅｒｎｉｋｅ 矩函数提取图像特征，完成对商标的管理 和检索，用于新商标的设计和检验。 周良等［５ ６ ］ 提 出利用图匹配方法对工程图纸检索，便于工程图纸 的查找和管理。 Ｔｅｎｃｅｒ 等［５ ７ ］ 提出利用草图对文档 中的插图进行检索，如图 ７ 所示，对于图文相混合的 大量文档，更便于感兴趣区域的快速定位。 图 ７ 利用草图对文档中插图进行检索 Ｆｉｇ．７ Ｕｓｉｎｇ ｓｋｅｔｃｈｅｓ ｔｏ ｒｅｔｒｉｅｖｅ ｔｈｅ ｉｌｌｕｓｔｒａｔｉｏｎｓ ｉｎ ａ ｄｏｃｕｍｅｎｔ ３）利用草图模糊性和不明确性的特点开发特 定应用。 可以根据现场目击者和受害者的回忆，手 绘犯罪嫌疑人的头像，然后通过手绘草图检索系统 和人脸识别技术，在犯罪嫌疑人的图像库中进行搜 索从而缩小嫌疑人的范围，以便协助公安机关破案 ·１７２· 智 能 系 统 学 报 第 １０ 卷

第2期 辛雨璇，等：基于手绘草图的图像检索技术研究进展 ·173· 和法院诉讼[s8] 4)用于开发面向儿童的认知训练系统。 Sketch2 Cartoon系统[s9]提出新颖的剪贴画搜索引擎 ClipartFinder,.能够实时检索互联网上一百万幅剪贴 画的卡通图像，并将寻找到的矢量图进一步编辑从 而构成自己的图画，如图8所示。2012年上市的基 于iOS平台的社交游戏“你画我猜”(Draw some- thing),通过画线条图进行猜词，进一步拓展了面向 儿童的应用，如图9所示。 (a) b 图11利用草图进行三维人脸重建 Fig.11 3-D face reconstruction by sketches 3展望 本文通过对基于手绘草图的图像检索的系统框 架进行梳理发现，以下3个方面可能成为未来手绘 图8利用草图构建儿童画 草图检索技术的研究趋势。 Fig.8 The construction of children's drawing by sket- 3.1多通道的交互方式 ches 笔纸交互是自然的交互方式，然而在手绘草图 5)利用手绘草图进行三维建模。陈雪锦[60]用 领域，最自然的交互方式是不妨碍甚至推进用户进 二维设计草图生成具有真实感的三维几何模型，如 行创作的过程，并非只采用鼠标模拟笔进行绘图。 建筑模型或树模型，帮助用户方便地捕捉构思，进行 因此，在未来的手绘草图系统中，可以引入触摸交 抽象的思考和形象的描述。如图10所示。刘凯 互、语音交互、手势交互与笔纸交互相融合，实现多 等[61]利用草图进行三维人脸的建模，可快速生成 通道的交互环境。在触摸交互方面，随着平板电脑 特定的人脸模型。如图11所示。 的出现，可以利用多点触摸技术在触摸屏上精准地 绘图。在语音交互方面，可以运用声音改变笔的颜 色、绘图的场景等。例如，王丹力等〔62]设计了儿童 交互式智能讲故事系统，儿童可以使用笔和语音的 多通道交互技术，完成故事的创作。在手势交互方 面，可以利用摄像头、数据手套进行空中涂鸦。也可 以借鉴体感游戏的设计理念，利用Kinect开发基于 手势识别的“手绘”系统。由于基于多通道交互的 DRAW WITH YOUR FRIENDS 手绘草图系统，丰富了创作方法，减小了交互障碍， 极大释放了用户创作的本能，必将成为普适计算时 图9你画我猜游戏界面 Fig.9 The interface of drawing something 代人机交互的一个重要研究方向。 3.2大数据背景下的草图检索 3.2.1更合理的特征表示方法 利用手绘草图进行检索的难点在于草图本身的 模糊性和不准确性，因此，手绘草图系统研究的关键 在于对草图的理解与表征。本文将现有特征表示方 图10利用草图生成树木和房屋的真实感模型 法归纳为基于笔划描述的草图特征表示、基于形状 Fig.10 Realistic models of trees and houses generated 特征的草图特征表示和基于组合图元的草图特征表 by sketches 示。但是对于构图复杂的草图，现有方法仍难以全

和法院诉讼［５ ８ ］ 。 ４） 用 于 开 发 面 向 儿 童 的 认 知 训 练 系 统。 Ｓｋｅｔｃｈ２Ｃａｒｔｏｏｎ 系统［ ５９ ］提出新颖的剪贴画搜索引擎 ＣｌｉｐａｒｔＦｉｎｄｅｒ，能够实时检索互联网上一百万幅剪贴 画的卡通图像，并将寻找到的矢量图进一步编辑从 而构成自己的图画，如图 ８ 所示。 ２０１２ 年上市的基 于 ｉＯＳ 平台的社交游戏“你画我猜” （Ｄｒａｗ ｓｏｍｅ⁃ ｔｈｉｎｇ） ，通过画线条图进行猜词，进一步拓展了面向 儿童的应用，如图 ９ 所示。 图 ８ 利用草图构建儿童画 Ｆｉｇ．８ Ｔｈｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｃｈｉｌｄｒｅｎ＇ｓ ｄｒａｗｉｎｇ ｂｙ ｓｋｅｔ⁃ ｃｈｅｓ ５）利用手绘草图进行三维建模。 陈雪锦［ ６ ０ ］用 二维设计草图生成具有真实感的三维几何模型，如 建筑模型或树模型，帮助用户方便地捕捉构思，进行 抽象的思考和形象的描述。 如图 １０ 所示。 刘凯 等［ ６ １ ］ 利用草图进行三维人脸的建模，可快速生成 特定的人脸模型。 如图 １１ 所示。 图 ９ 你画我猜游戏界面 Ｆｉｇ．９ Ｔｈｅ ｉｎｔｅｒｆａｃｅ ｏｆ ｄｒａｗｉｎｇ ｓｏｍｅｔｈｉｎｇ 图 １０ 利用草图生成树木和房屋的真实感模型 Ｆｉｇ．１０ Ｒｅａｌｉｓｔｉｃ ｍｏｄｅｌｓ ｏｆ ｔｒｅｅｓ ａｎｄ ｈｏｕｓｅｓ ｇｅｎｅｒａｔｅｄ ｂｙ ｓｋｅｔｃｈｅｓ 图 １１ 利用草图进行三维人脸重建 Ｆｉｇ．１１ ３⁃Ｄ ｆａｃｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｂｙ ｓｋｅｔｃｈｅｓ ３ 展望 本文通过对基于手绘草图的图像检索的系统框 架进行梳理发现，以下 ３ 个方面可能成为未来手绘 草图检索技术的研究趋势。 ３．１ 多通道的交互方式 笔纸交互是自然的交互方式，然而在手绘草图 领域，最自然的交互方式是不妨碍甚至推进用户进 行创作的过程，并非只采用鼠标模拟笔进行绘图。 因此，在未来的手绘草图系统中，可以引入触摸交 互、语音交互、手势交互与笔纸交互相融合，实现多 通道的交互环境。 在触摸交互方面，随着平板电脑 的出现，可以利用多点触摸技术在触摸屏上精准地 绘图。 在语音交互方面，可以运用声音改变笔的颜 色、绘图的场景等。 例如，王丹力等［ ６ ２ ］ 设计了儿童 交互式智能讲故事系统，儿童可以使用笔和语音的 多通道交互技术，完成故事的创作。 在手势交互方 面，可以利用摄像头、数据手套进行空中涂鸦。 也可 以借鉴体感游戏的设计理念，利用 Ｋｉｎｅｃｔ 开发基于 手势识别的“手绘”系统。 由于基于多通道交互的 手绘草图系统，丰富了创作方法，减小了交互障碍， 极大释放了用户创作的本能，必将成为普适计算时 代人机交互的一个重要研究方向。 ３．２ 大数据背景下的草图检索 ３．２．１ 更合理的特征表示方法 利用手绘草图进行检索的难点在于草图本身的 模糊性和不准确性，因此，手绘草图系统研究的关键 在于对草图的理解与表征。 本文将现有特征表示方 法归纳为基于笔划描述的草图特征表示、基于形状 特征的草图特征表示和基于组合图元的草图特征表 示。 但是对于构图复杂的草图，现有方法仍难以全 第 ２ 期 辛雨璇，等：基于手绘草图的图像检索技术研究进展 ·１７３·

·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

面合理地描述其特征。 因此，找到更合理有效的草 图特征描述方法仍需进一步研究。 有些学者已经开 始了新的尝试，如 Ｗａｎｇ 等［６ ３ ］等人认为目前大部分 研究只关注对图像特征的描述，而忽略了人的视觉 注意机制，从而提出利用角径向分区的分割方法，根 据用户手绘细致程度的不同求得空间权值分配图， 并将权值分配图与图像特征相结合，提取分割后各 块的特征与权值组成多维特征向量进行相似度计 算。 通过实验表明，将权值图应用于图像特征对实 验效果有明显改善。 可见，更合理的特征描述不能 只关注草图本身的构成，还要结合人的视觉机制、人 对图形的认知，以及其他反应人的输入意图的主观 因素，形成共同描述草图的特征表示方法。 ３．２．２ 基于大数据的索引结构 早期的草图检索系统均建立在小型数据库的基 础上，采用线性的索引结构。 而随着互联网数据的 海量激增，信息检索技术需要满足人们在大数据背 景下的检索需求。 目前已经提出一些索引方法来加 速检索。 例如将用于文本检索的倒排索引运用到草 图检索系统［１３，２３，５ １ ］中来，满足基于较大数据库快速 检索的要求。 Ｌｕｋａｓ 等［３ ８ ］ 利用最近邻算法加速检 索。 ＭｉｎｄｅｒＦｉｎｄｅｒ ［２２］提出 Ｅｄｇｅｌ Ｉｎｄｅｘ 的索引结构， 配合上文提到的可索引的定向倒角匹配算法，实现 了在 两百万幅图片上检索仅需几百毫秒的检索效 率。 ＭａｇｉｃＢｒｕｓｈ ［５ ０ ］提出类似于倒排索引的方法实 现六百四十万幅图片上的实时检索。 然而对于十亿 级数据库（ ｂｉｌｌｉｏｎ⁃ｌｅｖｅｌ）， ＭｉｎｄｅｒＦｉｎｄｅｒ 需要几分钟 的时间和 ５ＴＢ 的内存空间。 因此微软亚洲研究院 的 Ｓｕｎ Ｘｉｎｇｈａｉ 等［６ ４ ］提出了采用 ＫＬＳＨ，即采用中心 点算法（Ｋ⁃Ｍｅｄｏｉｄｓ）代替 Ｋ⁃ｍｅａｎｓ 算法的局部敏感 哈希（Ｌｏｃａｌｉｔｙ ｓｅｎｓｉｔｉｖｅ ｈａｓｈｉｎｇ， ＬＳＨ） 的检索结构， 实现了二十亿数据库的实时检索。 然而对于更大规 模（ｂｉｇ ｄａｔａ）的数据库，如何实现快速检索的需求， 仍在探索阶段。 ３．２．３ 利用草图语义改进草图检索 传统基于草图的图像检索方法，虽然已经不再 限制笔划方向等绘画要求，但也需要所绘制的草图 接近用户意图。 而对于那些在几何形状上离用户意 图很远的草图，传统基于草图的图像检索方法则不 具有适应性。 Ｅｉｔｚ 等［６ ５ ］针对此种情况，提出语义草 图检索的方法，采用将用户所绘制草图分类，然后将 类别作为关键字进行检索。 然后在此基础上可以选 择继续利用形状特征等传统图像检索方法进行图像 检索。 Ｓｕｎ 等［６ ６ ］ 也提出将草图识别用于加强草图 检索。 可见，将草图的语义用于草图检索可以放宽 用户绘图的相似性要求、增加检索的准确性，也为未 来基于草图的图像检索系统的开发开拓了思路。 ３．２．４ 统一的搜索评价标准 随着手绘草图检索系统的增多，如何判定检索 系统的优劣成为人们关心的问题。 对检索系统的评 价分为检索性能评价和检索效果评价，检索性能包 括检索速度、所需内存空间大小及是否满足平移、旋 转、缩放不变性等。 好的检索系统占用最低的内存 空间，实现海量数据库的实时响应。 检索效果则为 检索出的图片与所画草图的相似程度，一般通过绘 制“查准率⁃查全率曲线” 进行评价，如［３ ３ ⁃３ ５，６ ７ ］ 等。 然而查准率是实验者对检索结果的主观判断，因此 Ｍａｔｈｉａｓ Ｅｉｔｚ ［１３］提出把检索算法对图像的排序与人 的主观感受进行比较的评价标准，用二者之间的相 关性作为检索效果的评价标准。 然而检索系统的优 劣，应该从特征描述的有效性、系统的稳定性和可移 植性、检索性能和效果以及人的主观需求综合考虑， 因此如何形成统一的针对基于手绘草图检索系统的 评价标准仍是一个值得深入研究的问题。 参考文献： ［１］ ＲＵＩ Ｙ， ＴＨＯＭＡＳ Ｓ， ＣＨＡＮＧ Ｓ． Ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ： ｐａｓｔ， ｐｒｅｓｅｎｔ ａｎｄ ｆｕｔｕｒｅ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｖｉｓｕａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ Ｉｍａｇｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ， １９９９， １０（１）： ３９⁃６２． ［２］ ＥＡＫＩＮＳ Ｊ． Ａｕｔｏｍａｔｉｃ ｉｍａｇｅ ｃｏｎｔｅｎｔ ｒｅｔｒｉｅｖａｌ－Ａｒｅ ｗｅ ｇｅｔ⁃ ｔｉｎｇ ａｎｙｗｈｅｒｅ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ３ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ ｏｎ Ｅｌｅｃｔｒｏｎｉｃ Ｌｉｂｒａｒｙ ａｎｄ Ｖｉｓｕａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｒｅ⁃ ｓｅａｒｃｈ． Ｎｅｗｃａｓｔｌｅ， Ｕｎｉｔｅｄ Ｋｉｎｇｄｏｍ， １９９６： １２３⁃１３５． ［３］ ＶＥＬＴＫＡＭＰ Ｒ Ｃ， ＴＡＮＡＳＥ Ｍ． Ｃｏｎｔｅｎｔ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅ⁃ ｔｒｉｅｖａｌ ｓｙｓｔｅｍｓ： ａ ｓｕｒｖｅｙ． ＵＵ⁃ＣＳ⁃２０００⁃３４ ［ Ｒ］． Ｄｅｐｔ ｏｆ Ｃｏｍｐｕｔｉｎｇ Ｓｃｉｅｎｃｅ， Ｕｔｒｅｃｈｔ Ｕｎｉｖｅｒｓｉｔｙ， ２０００． ［４］ ＮＩＢＬＡＣＫ Ｃ， ＢＡＲＢＥＲ Ｒ， ＥＱＵＩＴＺ Ｗ， ｅｔ ａｌ． Ｔｈｅ ＱＢＩＣ ｐｒｏｊｅｃｔ： ｑｕｅｒｙｉｎｇ ｉｍａｇｅｓ ｂｙ ｃｏｎｔｅｎｔ ｕｓｉｎｇ ｃｏｌｏｒ， ｔｅｘｔｕｒｅ， ａｎｄ ｓｈａｐｅ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＳＰＩＥ Ｅｌｅｃｔｒｏｎｉｃ Ｉｍａｇｉｎｇ： Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ． Ｓａｎ Ｊｏｓｅ， Ｃａｎａｄａ， １９９３： １７３⁃ １８７． ［５］ＰＥＮＴＬＡＮＤ Ａ， ＰＩＣＡＲＤ Ｒ Ｗ， ＳＣＬＡＲＯＦＦ Ｓ． Ｐｈｏｔｏｂｏｏｋ： ｃｏｎｔｅｎｔ⁃ｂａｓｅｄ ｍａｎｉｐｕｌａｔｉｏｎ ｏｆ ｉｍａｇｅ ｄａｔａｂａｓｅｓ［ Ｊ］． Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ， １９９６， １８（３）： ２３３⁃２５４． ［６］孙正兴，冯桂焕 ，周若鸿．基于草图的人机交互技术研究 进展［Ｊ］． 计算机辅助设计与图形学学报， ２００５， ９（１７）： １８８９⁃１８９９． ＳＵＮ Ｚｈｅｎｇｘｉｎｇ， ＦＥＮＧ Ｇｕｉｈｕａｎ， ＺＨＯＵ Ｒｕｏｈｏｎｇ． Ｔｅｃｈ⁃ ｎｉｑｕｅｓ ｆｏｒ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｕｓｅｒ ｉｎｔｅｒｆａｃｅ： ｒｅｖｉｅｗ ａｎｄ ｒｅｓｅａｒｃｈ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２００５， ９（１７）： １８８９⁃１８９９． ［７］尹婷婷，王丹力，戴国忠． 基于多笔划的草图绘制工具 ［Ｃ］ ／ ／ 第 ５ 届全国普适计算学术会议论文集．北京，中 国， ２００９： ３０８⁃３１２． ＹＩＮ Ｔｉｎｇｔｉｎｇ， ＷＡＮＧ Ｄａｎｌｉ， ＤＡＩ Ｇｕｏｚｈｏｎｇ． Ａ ｓｋｅｔｃｈ ·１７４· 智 能 系 统 学 报 第 １０ 卷

第2期 辛雨璇，等：基于手绘草图的图像检索技术研究进展 ·175. drawing tool based on multiple strokes recognition [C]// Zernike moments[C]//Proceedings of the 17th Interna- Proceedings of the 5th National Conference on Pervasive tional Conference on Pattern Recognition.S.I.,2004: Computing.Beijing,China,2009:308-312. 367-370. [8]SEZGIN T,STAHOVICH T,DAVIS R.Sketch based inter- [18]谢强，冯桂焕，孙正兴.基于上下文的在线草图识别方 faces:early processing for sketch understanding[C]//Pro- 法[J刀.计算机科学，2007,34(3)：216-220. ceedings of 2001 Workshop Perceptive User interface.New XIE Qiang,FENG Guihuan,SUN Zhengxing.Online York,USA,2001:1-8. sketch recognition using contexts[J].Computer Science, [9]李雪峰，周良.基于自适应顶点探测的手绘草图识别 2007,34(3):216-220. [C]/2008年中国高校通信类院系学术研讨会论文集. [19]TANDLER P,PRANTE T.Using incremental gesture rec- 南京，中国.2009：315-320 ognition to provide immediate feedback while drawing pen LI Xuefeng,ZHOU Liang.Sketch recognition based on a- gestures[C]//Proceedings of ACM Symposium on User In- daptive vertex detection[C]//2008 Proceedings of the Sym- terface Software and Technology.New York,USA,2001: posium on Communication Colleges and Universities in Chi- 18-25. na.Nanjing,China,2009:315-320. [20]ARVO J,NOVINS K.Fluid sketches:continuous recogni- [10]汪文睿，周良.基于层次的草图检索框架[J刀].中国制造 tion and morphing of simple hand-drawn shapes[C]//Pro- 信息化，2006,35(19)：78-81. ceedings of the ACM Symposium on User Interface Software WANG Wenrui,ZHOU Liang.The framework for sketch and Technology.New York,USA,2000:73-80. searching based on hierarchy[J].Manufacture Information [21]李俊峰，张习文，敖翔，等.具有实时反馈的草图交互 Engineering of China,2006,35(19):78-81. 识别方法[J].计算机辅助设计与图形学学报，2005， [11]孙正兴，徐晓刚，孙建勇，等.支持方案设计的手绘图形 17(11):2453-2458. 输入工具[J].计算机辅助设计与图形学学报，2003， LI Junfeng,ZHANG Xiwen,AO Xiang,et al.An interac- 15(9):1145-1152. tive sketch recognition approach with real time feedback SUN Zhengxing,XU Xiaogang,SUN Jianyong,et al. [J].Journal of Computer Aided Design and Computer Sketch-based graphic input tool for conceptual design[J]. Graphics,2005,17(11):2453-2458. Journal of Computer Aided Design and Computer Graphics, [22]CAO Y,WANG C,ZHANG L,et al.Edgel index for 2003.15(9):1145-1152. large-scale sketch-based image search[C]//Proceedings [12]龚健，费广正，石民勇，等.基于手绘草图轮廓检索的简 of IEEE Conference on Computer Vision and Pattern Rec- 笔绘图系统[C]/2008系统仿真技术及其应用学术会 ognition.[S.1.],2011:761-768. 议论文集.北京，中国，2008：761-764. [23]ZHOU R,CHEN L,ZHANG L.Guess what you draw:in- GONG Jian,FEI Guangzheng,SHI Minyong,et al.A teractive contour-based image retrieval on a million-scale painting system based on freehand sketch contour retrieval database[C]//Proceedings of the 20th International Con- [C]//Proceedings of 2008 Symposium on System Simula- ference on Multimedia.New York,USA,2012:1343- tion Technology and Its Applications.Beijing,China, 1344. 2008:761-764. [24]REVANKAR S,YEGNANARAYANA B.Machine recogni- [13 EITZ M,HILDEBRAND K,BOUBEKEUR T,et al. tion and correction of freehand geometric line sketches Sketch-based image retrieval:benchmark and bag-of-fea- [C]//Proceedings of IEEE International Conference on tures descriptors[].IEEE Transactions on Visualization Systems,Man,and Cybernetics.New York,USA,1991: and Computer Graphics,2011,17(11):1624-1634. 87-92. [14]MARTIN D R,FOWLKES CC,MALIK J.Learning to de- [25]SEZGIN T.Feature point detection and curve approxima- tect natural image boundaries using local brightness,color, tion for early processing of free-hand sketches[D].Cam- and textureJ.IEEE Transactions on Pattern Analysis and bridge,USA:Massachusetts Institute of Technology, Machine,.2004,26(5):530-549. 2001:3-74. [15]RUBINE D.Specifying gestures by example[C]//Proceed- [26]YU B,CAIN S.A domain-independent system for sketch ings of the 18th Annual Conference on Computer Graphics recognition C//Proceedings of the 1st International Con- and Interactive Techniques.New York,USA,1991:329- ference on Computer Graphics and Interactive Techniques 337. New York,USA,2003:141-146. [16]LONG A C,JAMES J,LANDAY A,et al.Visual similari- [27]PAULSON B,HAMMOND T.Accurate primitive sketch ty of pen gestures[C]//Proceedings of the SIGCHI Confer- recognition and beautification[C]//Proceedings of Intelli- ence on Human Factors in Computing Systems.New York, gent User Interfaces.New York,USA,2008:1-10. USA,2001:360-367. [28]张莉莎，孙正兴，周若鸿，等。一种基于图匹配的复杂草 [17]HSE H,NEWTON A.Sketched symbol recognition using 图识别方法[J].计算机科学，2004,31(4)：147-150

ｄｒａｗｉｎｇ ｔｏｏｌ ｂａｓｅｄ ｏｎ ｍｕｌｔｉｐｌｅ ｓｔｒｏｋｅｓ ｒｅｃｏｇｎｉｔｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｅｒｖａｓｉｖｅ Ｃｏｍｐｕｔｉｎｇ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２００９： ３０８⁃３１２． ［８］ＳＥＺＧＩＮ Ｔ， ＳＴＡＨＯＶＩＣＨ Ｔ， ＤＡＶＩＳ Ｒ． Ｓｋｅｔｃｈ ｂａｓｅｄ ｉｎｔｅｒ⁃ ｆａｃｅｓ：ｅａｒｌｙ ｐｒｏｃｅｓｓｉｎｇ ｆｏｒ ｓｋｅｔｃｈ ｕｎｄｅｒｓｔａｎｄｉｎｇ ［ Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ２００１ Ｗｏｒｋｓｈｏｐ Ｐｅｒｃｅｐｔｉｖｅ Ｕｓｅｒ ｉｎｔｅｒｆａｃｅ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００１： １⁃８． ［９］李雪峰，周良． 基于自适应顶点探测的手绘草图识别 ［Ｃ］ ／ ／ ２００８ 年中国高校通信类院系学术研讨会论文集． 南京， 中国， ２００９：３１５⁃３２０． ＬＩ Ｘｕｅｆｅｎｇ， ＺＨＯＵ Ｌｉａｎｇ． Ｓｋｅｔｃｈ ｒｅｃｏｇｎｉｔｉｏｎ ｂａｓｅｄ ｏｎ ａ⁃ ｄａｐｔｉｖｅ ｖｅｒｔｅｘ ｄｅｔｅｃｔｉｏｎ［Ｃ］ ／ ／ ２００８ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｓｙｍ⁃ ｐｏｓｉｕｍ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｃｏｌｌｅｇｅｓ ａｎｄ Ｕｎｉｖｅｒｓｉｔｉｅｓ ｉｎ Ｃｈｉ⁃ ｎａ． Ｎａｎｊｉｎｇ， Ｃｈｉｎａ， ２００９： ３１５⁃３２０． ［１０］汪文睿，周良． 基于层次的草图检索框架［Ｊ］． 中国制造 信息化， ２００６， ３５（１９）：７８⁃８１． ＷＡＮＧ Ｗｅｎｒｕｉ， ＺＨＯＵ Ｌｉａｎｇ． Ｔｈｅ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｓｋｅｔｃｈ ｓｅａｒｃｈｉｎｇ ｂａｓｅｄ ｏｎ ｈｉｅｒａｒｃｈｙ［ Ｊ］． Ｍａｎｕｆａｃｔｕｒｅ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ ｏｆ Ｃｈｉｎａ， ２００６， ３５（１９）： ７８⁃８１． ［１１］孙正兴，徐晓刚，孙建勇，等． 支持方案设计的手绘图形 输入工具［ Ｊ］． 计算机辅助设计与图形学学报， ２００３， １５（９）： １１４５⁃１１５２． ＳＵＮ Ｚｈｅｎｇｘｉｎｇ， ＸＵ Ｘｉａｏｇａｎｇ， ＳＵＮ Ｊｉａｎｙｏｎｇ， ｅｔ ａｌ． Ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｇｒａｐｈｉｃ ｉｎｐｕｔ ｔｏｏｌ ｆｏｒ ｃｏｎｃｅｐｔｕａｌ ｄｅｓｉｇｎ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２００３， １５（９）： １１４５⁃１１５２． ［１２］龚健，费广正，石民勇，等． 基于手绘草图轮廓检索的简 笔绘图系统［Ｃ］ ／ ／ ２００８ 系统仿真技术及其应用学术会 议论文集． 北京， 中国， ２００８： ７６１⁃７６４． ＧＯＮＧ Ｊｉａｎ， ＦＥＩ Ｇｕａｎｇｚｈｅｎｇ， ＳＨＩ Ｍｉｎｙｏｎｇ， ｅｔ ａｌ． Ａ ｐａｉｎｔｉｎｇ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｆｒｅｅｈａｎｄ ｓｋｅｔｃｈ ｃｏｎｔｏｕｒ ｒｅｔｒｉｅｖａｌ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２００８ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｓｙｓｔｅｍ Ｓｉｍｕｌａ⁃ ｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｉｔｓ Ａｐｐｌｉｃａｔｉｏｎｓ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２００８： ７６１⁃７６４． ［１３］ ＥＩＴＺ Ｍ， ＨＩＬＤＥＢＲＡＮＤ Ｋ， ＢＯＵＢＥＫＥＵＲ Ｔ， ｅｔ ａｌ． Ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ： ｂｅｎｃｈｍａｒｋ ａｎｄ ｂａｇ⁃ｏｆ⁃ｆｅａ⁃ ｔｕｒｅｓ ｄｅｓｃｒｉｐｔｏｒｓ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２０１１， １７（１１）： １６２４⁃１６３４． ［１４］ＭＡＲＴＩＮ Ｄ Ｒ， ＦＯＷＬＫＥＳ Ｃ Ｃ， ＭＡＬＩＫ Ｊ． Ｌｅａｒｎｉｎｇ ｔｏ ｄｅ⁃ ｔｅｃｔ ｎａｔｕｒａｌ ｉｍａｇｅ ｂｏｕｎｄａｒｉｅｓ ｕｓｉｎｇ ｌｏｃａｌ ｂｒｉｇｈｔｎｅｓｓ， ｃｏｌｏｒ， ａｎｄ ｔｅｘｔｕｒｅ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ， ２００４， ２６（５）： ５３０⁃５４９． ［１５］ＲＵＢＩＮＥ Ｄ． Ｓｐｅｃｉｆｙｉｎｇ ｇｅｓｔｕｒｅｓ ｂｙ ｅｘａｍｐｌｅ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄ⁃ ｉｎｇｓ ｏｆ ｔｈｅ １８ｔｈ Ａｎｎｕａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｎｔｅｒａｃｔｉｖｅ Ｔｅｃｈｎｉｑｕｅｓ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， １９９１： ３２９⁃ ３３７． ［１６］ＬＯＮＧ Ａ Ｃ， ＪＡＭＥＳ Ｊ， ＬＡＮＤＡＹ Ａ， ｅｔ ａｌ． Ｖｉｓｕａｌ ｓｉｍｉｌａｒｉ⁃ ｔｙ ｏｆ ｐｅｎ ｇｅｓｔｕｒｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＳＩＧＣＨＩ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ ｏｎ Ｈｕｍａｎ Ｆａｃｔｏｒｓ ｉｎ Ｃｏｍｐｕｔｉｎｇ Ｓｙｓｔｅｍｓ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００１： ３６０⁃３６７． ［１７］ ＨＳＥ Ｈ， ＮＥＷＴＯＮ Ａ． Ｓｋｅｔｃｈｅｄ ｓｙｍｂｏｌ ｒｅｃｏｇｎｉｔｉｏｎ ｕｓｉｎｇ Ｚｅｒｎｉｋｅ ｍｏｍｅｎｔｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １７ｔｈ Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． ［ Ｓ． ｌ．］， ２００４： ３６７⁃３７０． ［１８］谢强， 冯桂焕， 孙正兴． 基于上下文的在线草图识别方 法［Ｊ］． 计算机科学， ２００７， ３４（３）： ２１６⁃２２０． ＸＩＥ Ｑｉａｎｇ， ＦＥＮＧ Ｇｕｉｈｕａｎ， ＳＵＮ Ｚｈｅｎｇｘｉｎｇ． Ｏｎｌｉｎｅ ｓｋｅｔｃｈ ｒｅｃｏｇｎｉｔｉｏｎ ｕｓｉｎｇ ｃｏｎｔｅｘｔｓ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００７， ３４（３）： ２１６⁃２２０． ［１９］ＴＡＮＤＬＥＲ Ｐ， ＰＲＡＮＴＥ Ｔ． Ｕｓｉｎｇ ｉｎｃｒｅｍｅｎｔａｌ ｇｅｓｔｕｒｅ ｒｅｃ⁃ ｏｇｎｉｔｉｏｎ ｔｏ ｐｒｏｖｉｄｅ ｉｍｍｅｄｉａｔｅ ｆｅｅｄｂａｃｋ ｗｈｉｌｅ ｄｒａｗｉｎｇ ｐｅｎ ｇｅｓｔｕｒｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｕｓｅｒ Ｉｎ⁃ ｔｅｒｆａｃｅ Ｓｏｆｔｗａｒｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００１： １８⁃２５． ［２０］ＡＲＶＯ Ｊ， ＮＯＶＩＮＳ Ｋ． Ｆｌｕｉｄ ｓｋｅｔｃｈｅｓ： ｃｏｎｔｉｎｕｏｕｓ ｒｅｃｏｇｎｉ⁃ ｔｉｏｎ ａｎｄ ｍｏｒｐｈｉｎｇ ｏｆ ｓｉｍｐｌｅ ｈａｎｄ⁃ｄｒａｗｎ ｓｈａｐｅｓ［Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｕｓｅｒ Ｉｎｔｅｒｆａｃｅ Ｓｏｆｔｗａｒｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２０００： ７３⁃８０． ［２１］李俊峰， 张习文， 敖翔，等． 具有实时反馈的草图交互 识别方法［ Ｊ］． 计算机辅助设计与图形学学报， ２００５， １７（１１）： ２４５３⁃２４５８． ＬＩ Ｊｕｎｆｅｎｇ， ＺＨＡＮＧ Ｘｉｗｅｎ， ＡＯ Ｘｉａｎｇ， ｅｔ ａｌ． Ａｎ ｉｎｔｅｒａｃ⁃ ｔｉｖｅ ｓｋｅｔｃｈ ｒｅｃｏｇｎｉｔｉｏｎ ａｐｐｒｏａｃｈ ｗｉｔｈ ｒｅａｌ ｔｉｍｅ ｆｅｅｄｂａｃｋ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２００５， １７（１１）： ２４５３⁃２４５８． ［２２］ ＣＡＯ Ｙ， ＷＡＮＧ Ｃ， ＺＨＡＮＧ Ｌ， ｅｔ ａｌ． Ｅｄｇｅｌ ｉｎｄｅｘ ｆｏｒ ｌａｒｇｅ⁃ｓｃａｌｅ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｉｍａｇｅ ｓｅａｒｃｈ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃ⁃ ｏｇｎｉｔｉｏｎ． ［Ｓ．ｌ．］， ２０１１： ７６１⁃７６８． ［２３］ＺＨＯＵ Ｒ， ＣＨＥＮ Ｌ， ＺＨＡＮＧ Ｌ． Ｇｕｅｓｓ ｗｈａｔ ｙｏｕ ｄｒａｗ： ｉｎ⁃ ｔｅｒａｃｔｉｖｅ ｃｏｎｔｏｕｒ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｏｎ ａ ｍｉｌｌｉｏｎ⁃ｓｃａｌｅ ｄａｔａｂａｓｅ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ ｏｎ Ｍｕｌｔｉｍｅｄｉａ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２０１２： １３４３⁃ １３４４． ［２４］ＲＥＶＡＮＫＡＲ Ｓ， ＹＥＧＮＡＮＡＲＡＹＡＮＡ Ｂ． Ｍａｃｈｉｎｅ ｒｅｃｏｇｎｉ⁃ ｔｉｏｎ ａｎｄ ｃｏｒｒｅｃｔｉｏｎ ｏｆ ｆｒｅｅｈａｎｄ ｇｅｏｍｅｔｒｉｃ ｌｉｎｅ ｓｋｅｔｃｈｅｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｙｓｔｅｍｓ， Ｍａｎ， ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， １９９１： ８７⁃９２． ［２５］ ＳＥＺＧＩＮ Ｔ． Ｆｅａｔｕｒｅ ｐｏｉｎｔ ｄｅｔｅｃｔｉｏｎ ａｎｄ ｃｕｒｖｅ ａｐｐｒｏｘｉｍａ⁃ ｔｉｏｎ ｆｏｒ ｅａｒｌｙ ｐｒｏｃｅｓｓｉｎｇ ｏｆ ｆｒｅｅ⁃ｈａｎｄ ｓｋｅｔｃｈｅｓ［Ｄ］． Ｃａｍ⁃ ｂｒｉｄｇｅ， ＵＳＡ： Ｍａｓｓａｃｈｕｓｅｔｔｓ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， ２００１： ３⁃７４． ［２６］ＹＵ Ｂ， ＣＡＩＮ Ｓ． Ａ ｄｏｍａｉｎ⁃ｉｎｄｅｐｅｎｄｅｎｔ ｓｙｓｔｅｍ ｆｏｒ ｓｋｅｔｃｈ ｒｅｃｏｇｎｉｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ ａｎｄ Ｉｎｔｅｒａｃｔｉｖｅ Ｔｅｃｈｎｉｑｕｅｓ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００３： １４１⁃１４６． ［２７］ ＰＡＵＬＳＯＮ Ｂ， ＨＡＭＭＯＮＤ Ｔ． Ａｃｃｕｒａｔｅ ｐｒｉｍｉｔｉｖｅ ｓｋｅｔｃｈ ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ ｂｅａｕｔｉｆｉｃａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｉｎｔｅｌｌｉ⁃ ｇｅｎｔ Ｕｓｅｒ Ｉｎｔｅｒｆａｃｅｓ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２００８： １⁃１０． ［２８］张莉莎，孙正兴，周若鸿，等． 一种基于图匹配的复杂草 图识别方法［Ｊ］． 计算机科学， ２００４， ３１（４）： １４７⁃１５０． 第 ２ 期 辛雨璇，等：基于手绘草图的图像检索技术研究进展 ·１７５·

·176· 智能系统学报 第10卷 ZHANG Lisha,SUN Zhengxing,ZHOU Ruohong,et al.A M ]London:Griffin,1948:1-160. method of graph-based composite sketchy graphics recogni- [41]李彬，梁爽，孙正兴.基于空间关系的手绘草图检索 tion[J].Computer Science,2004,31(4):147-150. [J].计算机科学，2005,32(12)：227-231. [29]GROSS M.The electronic cocktail napkin:a computational LI Bin,LIANG Shuang,SUN Zhengxing.Sketch retrieval environment for working with design diagram[J].Design based on topological relations [J].Computer Science, Studies,1996,17(1):53-69. 2005,32(12):227-231. [30]CHEN C,XIE S.Freehand drawing system using a fuzzy [42]SOUSA P,FONSECA M.Sketch-based retrieval of draw- logic concept[J].Computer-Aided Design,1996,28(2): ings using topological proximity [C]//Proceedings of the 77-89. 14th International Conference on Distributed Multimedia [31]SCIASIO E,MONGIELLO M.Query by sketch and rele- Systems.Lisboa,Portugal,2008:276-281. vance feedback for content-based image retrieval over the [43]BORGEFORS G.Hierarchical chamfer matching:a para- web[J].Journal of Visual Languages and Computing, metric edge matching algorithm[J].IEEE Transactions on 1999,10(6):565-584. Pattern Analysis and Machine Intelligence,1988,10(6): [32]CHEE S,PARK K,PARK S.Efficient use of MPEG-7 849-865. edge histogram descriptor[J].ETRI Journal,2002,24 [44]STENGER B,THAYANANTHAN A,TORR P,et al. (1):35-42. Model-based hand tracking using a hierarchical Bayesian [33]李曼舞，孙正兴，顾庆东.基于轮廓的手绘草图检索研 filter[J].IEEE Transactions on Pattern Analysis and Ma- 究[J].计算机应用，2005,25(2)：344-347. chine Intelligence,2006,28(9):1372-1384. LI Manwu,SUN Zhengxing,GU Qingdong.Study on con- [45]ROCCHIO J.Relevance feedback in information retrieval tour-based freehand sketch retrieval[J].Computer Appli- [M].[S.I.]Prentice Hall,1971:313-323. cations,2005,25(2):344-347. [46]梁爽，孙正兴.面向草图检索的相关反馈方法[J刀.计算 [34]高竹红，汤进，罗斌.基于结构图的手绘草图检索[J] 机辅助设计与图形学学报，2006,18(11)：1753-1757. 计算机技术与发展，2008,18(3)：33-35. LIANG Shuang,SUN Zhengxing.BSVM-based relevance GAO Zhuhong,TANG Jin,LUO Bin.Sketch retrieval feedback for sketch retrieval[J].Journal of Computer Ai- based on structural graph[J].Computer Technology and ded Design and Computer Graphics,2006,18(11): Development,2008,18(3):33-35. 1753-1757. [35]吴明珠.利用成对几何直方图改进基于轮廓的图像检 [47]袁贞明，金贵朝，张佳.基于贝叶斯网络的在线草图识 索[J].电脑知识与技术，2007,16(1)：1140-1147. 别算法[J].计算机工程，2010,36(5)：32-34. WU Mingzhu.Improvement of contour-based image retriev- YUAN Zhenming,JIN Guichao,ZHANG Jia.Online al using pair wise geometric histogram [J].Computer sketch recognition algorithm based on Bavesian network Knowledge and Technology,2007,16(1):1140-1147. [J].Computer Engineering,2010,36(5):32-34. [36]钱晶.按例和按绘的图像检索研究[D].合肥：中国科学 [48]裴继红，李翠芸，龚忻.一种新的隐马尔可夫模型及其 技术大学，2009：69-100. 在手绘图形识别中的应用[J].计算机学报，2005,28 QIAN Jing.Research on example and sketch based image (10):1745-1752 retrieval[D].Hefei:University of Science and Technology PEI Jihong,LI Cuiyun,GONG Xin.A novel hidden Mark- of China.2009:69-100. ov model and its application to recognize hand-drawn [37]钱晶，汪增福.一种基于规范化形状的手绘草图检索算 graphic symbol[J].Chinese Journal of Computers,2005, 法[J].中国科学技术大学学报，2010,10(40)：1043. 28(10):1745-1752. 1053. [49]CAO Y,WANG H,WANG C,et al.MindFinder:interac- QIAN Jing,WANG Zengfu.A method for freehand sketch tive sketch-based image search on millions of images[C]/ retrieval based on affine adaptive skeleton[J.Journal of Proceedings of the 18th International Conference on Multi- University of Science and Technology of China,2010,10 media.Santiago,USA,2010:1605-1608. (40):1043-1053. [50]SUN X,WANG C,SUD A,et al.MagicBrush:image [38 ]LUKAS T.A new framework for online sketch-based image search by color sketch C//Proceedings of the 21st ACM retrieval in web environment[C]//Proceedings of the 11th International Conference on Multimedia.New York,USA, International Conference on Information Sciences,Signal 2013:475-476. Processing and their Applications.Montreal,Canada, [51]EITZ M,HILDEBRAND K,BOUBEKEUR T,et al.Pho- 2012:1430-1431. toSketch:a sketch based image query and compositing sys- [39]KENDALL M.A new measure of rank correlation J].Bi- tem[C]//ACM SIGGRAPH Talk Program.New Orleans, ometrika,1938,6(30):81-93. USA,2009:60. 40]KENDALL M,GIBBONS J.Rank correlation methods [52]CHEN T,CHENG M.TAN P,et al.Sketch2Photo:inter-

ＺＨＡＮＧ Ｌｉｓｈａ， ＳＵＮ Ｚｈｅｎｇｘｉｎｇ， ＺＨＯＵ Ｒｕｏｈｏｎｇ， ｅｔ ａｌ． Ａ ｍｅｔｈｏｄ ｏｆ ｇｒａｐｈ⁃ｂａｓｅｄ ｃｏｍｐｏｓｉｔｅ ｓｋｅｔｃｈｙ ｇｒａｐｈｉｃｓ ｒｅｃｏｇｎｉ⁃ ｔｉｏｎ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００４， ３１（４）：１４７⁃１５０． ［２９］ＧＲＯＳＳ Ｍ． Ｔｈｅ ｅｌｅｃｔｒｏｎｉｃ ｃｏｃｋｔａｉｌ ｎａｐｋｉｎ： ａ ｃｏｍｐｕｔａｔｉｏｎａｌ ｅｎｖｉｒｏｎｍｅｎｔ ｆｏｒ ｗｏｒｋｉｎｇ ｗｉｔｈ ｄｅｓｉｇｎ ｄｉａｇｒａｍ［ Ｊ］． Ｄｅｓｉｇｎ Ｓｔｕｄｉｅｓ， １９９６， １７（１）： ５３⁃６９． ［３０］ＣＨＥＮ Ｃ， ＸＩＥ Ｓ． Ｆｒｅｅｈａｎｄ ｄｒａｗｉｎｇ ｓｙｓｔｅｍ ｕｓｉｎｇ ａ ｆｕｚｚｙ ｌｏｇｉｃ ｃｏｎｃｅｐｔ［Ｊ］． Ｃｏｍｐｕｔｅｒ⁃Ａｉｄｅｄ Ｄｅｓｉｇｎ， １９９６， ２８（２）： ７７⁃８９． ［３１］ＳＣＩＡＳＩＯ Ｅ， ＭＯＮＧＩＥＬＬＯ Ｍ． Ｑｕｅｒｙ ｂｙ ｓｋｅｔｃｈ ａｎｄ ｒｅｌｅ⁃ ｖａｎｃｅ ｆｅｅｄｂａｃｋ ｆｏｒ ｃｏｎｔｅｎｔ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｏｖｅｒ ｔｈｅ ｗｅｂ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｖｉｓｕａｌ Ｌａｎｇｕａｇｅｓ ａｎｄ Ｃｏｍｐｕｔｉｎｇ， １９９９， １０（６）： ５６５⁃５８４． ［３２］ ＣＨＥＥ Ｓ， ＰＡＲＫ Ｋ， ＰＡＲＫ Ｓ． Ｅｆｆｉｃｉｅｎｔ ｕｓｅ ｏｆ ＭＰＥＧ⁃７ ｅｄｇｅ ｈｉｓｔｏｇｒａｍ ｄｅｓｃｒｉｐｔｏｒ ［ Ｊ］． ＥＴＲＩ Ｊｏｕｒｎａｌ， ２００２， ２４ （１）： ３５⁃４２． ［３３］李曼舞，孙正兴，顾庆东． 基于轮廓的手绘草图检索研 究［Ｊ］． 计算机应用， ２００５， ２５（２）： ３４４⁃３４７． ＬＩ Ｍａｎｗｕ， ＳＵＮ Ｚｈｅｎｇｘｉｎｇ， ＧＵ Ｑｉｎｇｄｏｎｇ． Ｓｔｕｄｙ ｏｎ ｃｏｎ⁃ ｔｏｕｒ⁃ｂａｓｅｄ ｆｒｅｅｈａｎｄ ｓｋｅｔｃｈ ｒｅｔｒｉｅｖａｌ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉ⁃ ｃａｔｉｏｎｓ， ２００５， ２５（２）： ３４４⁃３４７． ［３４］高竹红， 汤进， 罗斌． 基于结构图的手绘草图检索［ Ｊ］． 计算机技术与发展， ２００８， １８（３）： ３３⁃３５． ＧＡＯ Ｚｈｕｈｏｎｇ， ＴＡＮＧ Ｊｉｎ， ＬＵＯ Ｂｉｎ． Ｓｋｅｔｃｈ ｒｅｔｒｉｅｖａｌ ｂａｓｅｄ ｏｎ ｓｔｒｕｃｔｕｒａｌ ｇｒａｐｈ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２００８， １８（３）： ３３⁃３５． ［３５］吴明珠． 利用成对几何直方图改进基于轮廓的图像检 索［Ｊ］．电脑知识与技术， ２００７， １６（１）： １１４０⁃１１４７． ＷＵ Ｍｉｎｇｚｈｕ． Ｉｍｐｒｏｖｅｍｅｎｔ ｏｆ ｃｏｎｔｏｕｒ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖ⁃ ａｌ ｕｓｉｎｇ ｐａｉｒ ｗｉｓｅ ｇｅｏｍｅｔｒｉｃ ｈｉｓｔｏｇｒａｍ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２００７， １６（１）： １１４０⁃１１４７． ［３６］钱晶． 按例和按绘的图像检索研究［Ｄ］．合肥：中国科学 技术大学， ２００９： ６９⁃１００． ＱＩＡＮ Ｊｉｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ｅｘａｍｐｌｅ ａｎｄ ｓｋｅｔｃｈ ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ［Ｄ］． Ｈｅｆｅｉ： Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉｎａ， ２００９： ６９⁃１００． ［３７］钱晶， 汪增福． 一种基于规范化形状的手绘草图检索算 法［Ｊ］．中国科学技术大学学报， ２０１０， １０（４０）： １０４３⁃ １０５３． ＱＩＡＮ Ｊｉｎｇ， ＷＡＮＧ Ｚｅｎｇｆｕ． Ａ ｍｅｔｈｏｄ ｆｏｒ ｆｒｅｅｈａｎｄ ｓｋｅｔｃｈ ｒｅｔｒｉｅｖａｌ ｂａｓｅｄ ｏｎ ａｆｆｉｎｅ ａｄａｐｔｉｖｅ ｓｋｅｌｅｔｏｎ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉｎａ， ２０１０， １０ （４０）： １０４３⁃１０５３． ［３８］ＬＵＫＡＳ Ｔ． Ａ ｎｅｗ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｏｎｌｉｎｅ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ ｉｎ ｗｅｂ ｅｎｖｉｒｏｎｍｅｎｔ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １１ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ， Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ ａｎｄ ｔｈｅｉｒ Ａｐｐｌｉｃａｔｉｏｎｓ． Ｍｏｎｔｒｅａｌ， Ｃａｎａｄａ， ２０１２： １４３０⁃１４３１． ［３９］ＫＥＮＤＡＬＬ Ｍ． Ａ ｎｅｗ ｍｅａｓｕｒｅ ｏｆ ｒａｎｋ ｃｏｒｒｅｌａｔｉｏｎ［ Ｊ］． Ｂｉ⁃ ｏｍｅｔｒｉｋａ， １９３８， ６（３０）： ８１⁃９３． ［４０］ ＫＥＮＤＡＬＬ Ｍ， ＧＩＢＢＯＮＳ Ｊ． Ｒａｎｋ ｃｏｒｒｅｌａｔｉｏｎ ｍｅｔｈｏｄｓ ［Ｍ］． Ｌｏｎｄｏｎ： Ｇｒｉｆｆｉｎ， １９４８： １⁃１６０． ［４１］李彬，梁爽，孙正兴． 基于空间关系的手绘草图检索 ［Ｊ］． 计算机科学， ２００５， ３２（１２）： ２２７⁃２３１． ＬＩ Ｂｉｎ， ＬＩＡＮＧ Ｓｈｕａｎｇ， ＳＵＮ Ｚｈｅｎｇｘｉｎｇ． Ｓｋｅｔｃｈ ｒｅｔｒｉｅｖａｌ ｂａｓｅｄ ｏｎ ｔｏｐｏｌｏｇｉｃａｌ ｒｅｌａｔｉｏｎｓ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００５， ３２（１２）： ２２７⁃２３１． ［４２］ＳＯＵＳＡ Ｐ， ＦＯＮＳＥＣＡ Ｍ． Ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｒｅｔｒｉｅｖａｌ ｏｆ ｄｒａｗ⁃ ｉｎｇｓ ｕｓｉｎｇ ｔｏｐｏｌｏｇｉｃａｌ ｐｒｏｘｉｍｉｔｙ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄｉｓｔｒｉｂｕｔｅｄ Ｍｕｌｔｉｍｅｄｉａ Ｓｙｓｔｅｍｓ． Ｌｉｓｂｏａ， Ｐｏｒｔｕｇａｌ， ２００８： ２７６⁃２８１． ［４３］ ＢＯＲＧＥＦＯＲＳ Ｇ． Ｈｉｅｒａｒｃｈｉｃａｌ ｃｈａｍｆｅｒ ｍａｔｃｈｉｎｇ： ａ ｐａｒａ⁃ ｍｅｔｒｉｃ ｅｄｇｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， １９８８， １０（６）： ８４９⁃８６５． ［４４］ ＳＴＥＮＧＥＲ Ｂ， ＴＨＡＹＡＮＡＮＴＨＡＮ Ａ， ＴＯＲＲ Ｐ， ｅｔ ａｌ． Ｍｏｄｅｌ⁃ｂａｓｅｄ ｈａｎｄ ｔｒａｃｋｉｎｇ ｕｓｉｎｇ ａ ｈｉｅｒａｒｃｈｉｃａｌ Ｂａｙｅｓｉａｎ ｆｉｌｔｅｒ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａ⁃ ｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００６， ２８（９）：１３７２⁃１３８４． ［４５］ ＲＯＣＣＨＩＯ Ｊ． Ｒｅｌｅｖａｎｃｅ ｆｅｅｄｂａｃｋ ｉｎ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｔｒｉｅｖａｌ ［Ｍ］． ［Ｓ．ｌ．］： Ｐｒｅｎｔｉｃｅ Ｈａｌｌ， １９７１： ３１３⁃３２３． ［４６］梁爽，孙正兴． 面向草图检索的相关反馈方法［Ｊ］． 计算 机辅助设计与图形学学报， ２００６， １８（１１）：１７５３⁃１７５７． ＬＩＡＮＧ Ｓｈｕａｎｇ， ＳＵＮ Ｚｈｅｎｇｘｉｎｇ． ＢＳＶＭ⁃ｂａｓｅｄ ｒｅｌｅｖａｎｃｅ ｆｅｅｄｂａｃｋ ｆｏｒ ｓｋｅｔｃｈ ｒｅｔｒｉｅｖａｌ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ａｉ⁃ ｄｅｄ Ｄｅｓｉｇｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ， ２００６， １８ （ １１ ）： １７５３⁃１７５７． ［４７］袁贞明，金贵朝，张佳． 基于贝叶斯网络的在线草图识 别算法［Ｊ］． 计算机工程， ２０１０， ３６（５）：３２⁃３４． ＹＵＡＮ Ｚｈｅｎｍｉｎｇ， ＪＩＮ Ｇｕｉｃｈａｏ， ＺＨＡＮＧ Ｊｉａ． Ｏｎｌｉｎｅ ｓｋｅｔｃｈ ｒｅｃｏｇｎｉｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｂａｙｅｓｉａｎ ｎｅｔｗｏｒｋ ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１０， ３６（５）： ３２⁃３４． ［４８］裴继红，李翠芸，龚忻． 一种新的隐马尔可夫模型及其 在手绘图形识别中的应用［ Ｊ］． 计算机学报， ２００５， ２８ （１０）： １７４５⁃１７５２． ＰＥＩ Ｊｉｈｏｎｇ， ＬＩ Ｃｕｉｙｕｎ， ＧＯＮＧ Ｘｉｎ． Ａ ｎｏｖｅｌ ｈｉｄｄｅｎ Ｍａｒｋ⁃ ｏｖ ｍｏｄｅｌ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｒｅｃｏｇｎｉｚｅ ｈａｎｄ⁃ｄｒａｗｎ ｇｒａｐｈｉｃ ｓｙｍｂｏｌ［Ｊ］． Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ， ２００５， ２８（１０）： １７４５⁃１７５２． ［４９］ＣＡＯ Ｙ， ＷＡＮＧ Ｈ， ＷＡＮＧ Ｃ， ｅｔ ａｌ． ＭｉｎｄＦｉｎｄｅｒ： ｉｎｔｅｒａｃ⁃ ｔｉｖｅ ｓｋｅｔｃｈ⁃ｂａｓｅｄ ｉｍａｇｅ ｓｅａｒｃｈ ｏｎ ｍｉｌｌｉｏｎｓ ｏｆ ｉｍａｇｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｕｌｔｉ⁃ ｍｅｄｉａ． Ｓａｎｔｉａｇｏ， ＵＳＡ， ２０１０： １６０５⁃１６０８． ［５０］ ＳＵＮ Ｘ， ＷＡＮＧ Ｃ， ＳＵＤ Ａ， ｅｔ ａｌ． ＭａｇｉｃＢｒｕｓｈ： ｉｍａｇｅ ｓｅａｒｃｈ ｂｙ ｃｏｌｏｒ ｓｋｅｔｃｈ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｕｌｔｉｍｅｄｉａ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２０１３： ４７５⁃４７６． ［５１］ＥＩＴＺ Ｍ， ＨＩＬＤＥＢＲＡＮＤ Ｋ， ＢＯＵＢＥＫＥＵＲ Ｔ， ｅｔ ａｌ． Ｐｈｏ⁃ ｔｏＳｋｅｔｃｈ： ａ ｓｋｅｔｃｈ ｂａｓｅｄ ｉｍａｇｅ ｑｕｅｒｙ ａｎｄ ｃｏｍｐｏｓｉｔｉｎｇ ｓｙｓ⁃ ｔｅｍ［Ｃ］ ／ ／ ＡＣＭ ＳＩＧＧＲＡＰＨ Ｔａｌｋ Ｐｒｏｇｒａｍ． Ｎｅｗ Ｏｒｌｅａｎｓ， ＵＳＡ， ２００９： ６０． ［５２］ＣＨＥＮ Ｔ， ＣＨＥＮＧ Ｍ， ＴＡＮ Ｐ， ｅｔ ａｌ． Ｓｋｅｔｃｈ２Ｐｈｏｔｏ： ｉｎｔｅｒ⁃ ·１７６· 智 能 系 统 学 报 第 １０ 卷