第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 且勾勒草图是人与生俱来的能力,古代人就会画简
第 10 卷第 2 期 智 能 系 统 学 报 Vol.10 №.2 2015 年 4 月 CAAI Transactions on Intelligent Systems Apr. 2015 DOI:10.3969 / j.issn.1673⁃4785.201401045 网络出版地址: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 收稿日期:2014⁃01⁃22. 网络出版日期:2015⁃03⁃20. 基金项目:国家自然科学基金资助项目(61102037); 哈尔滨工业大学 科研创新基金资助项目(HIT. NSRIF. 2015057). 通信作者:闫子飞. E⁃mail:cszfyan@ gmail.com. 互联网的发展和普及拓宽了人们获取信息的途 径,也使得人们处于海量信息世界之中。 这些信息 不仅包括文字信息,也包括视觉信息。 视觉感知是 人类从客观世界获取信息的主要来源,也是人们认 知的一种重要方式。 如何从海量图像数据库中快速 有效地进行信息检索,建立更为有效的图像描述,是 人们一直关心的问题。 20 世纪 70 年代提出了基于 图像文本标注的检索方式,即检索图像的文字表示。 这种检索方式,由于人工标注的主观性[1] ,导致检 索效果并不理想。 20 世纪 90 年代初研究者们又提 出基于图像内容的检索方式,通过提取图像的底层 特征[1] ,如颜色、纹理等,增加了图像检索的有效 性,而随着便捷化,小型化无线设备的发展和“数字 水墨”或电子纸的出现,笔式交互成为了新型人机 交互方式之一。 人机交互界面由桌面环境模拟了笔 纸的环境,促进了笔式交互的进程,也为利用手绘草 图进行图像检索奠定了基础。 基于手绘草图的图像 检索也属于基于图像内容检索范畴。 草图与图像不 同,草图是人依靠记忆和模仿来进行信息的表达,并 且勾勒草图是人与生俱来的能力,古代人就会画简
·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-)。李雪峰等[)还 值进行判断。而聚点是那些点密度较大的点,通过
图,因此利用手绘草图进行图像检索更接近自然的 人机交互方式。 然而图像间的相似性不仅仅建立在 颜色、纹理等特征[1]的基础上,Eakins [2]根据检索的 复杂性将用户查询分成了 3 个层次,其中第 1 层次 为视觉相似检索,第 2、3 层为语义图像检索。 视觉 相似检索主要利用图像的形状信息检索,语义图像 检索的目的则是使计算机在检索图像时拥有接近人 的理解水平。 目前基于内容的图像检索结合相关领 域语义知识已经取得大量的研究成果[3] ,但都分别 针对某一特定领域(即领域相关) 处理,典型的包 括:IBM 的 QBIC [4] 系统、MIT 的 PhotoBook [5] 系统 等。 基于草图的图像检索也取得了很多进展。 孙正 兴[6]对基于草图的人机交互技术早期的研究进展 进行了归纳和总结,并提出了基于草图的人机交互 系统模型,此模型高度概括了当时绝大多数的基于 草图的人机交互技术及应用,但这些应用大部分依 赖于领域知识,只能应用到特定的领域。 而本文针 对基于草图的人机交互技术的图像检索领域,主要 利用视觉信息,并结合语义知识检索,尝试建立领域 无关即通用的图像检索框架;并对该框架所涉及的 相关技术进行了较详细的归纳;对手绘草图检索系 统现阶段的应用进行总结;并展望了手绘草图检索 系统在草图特征表示、多通道输入、检索机制和系统 评价的建立等方面在未来的研究趋势。 1 手绘草图检索系统概述 在对大量基于手绘草图检索系统分析的基础 上,本文提出了手绘草图检索系统框架图,基于手绘 草图的图像检索系统框架一般可分为手绘输入模 块、手绘草图预处理模块、草图特征表示模块、草图 特征匹配模块、图像反馈模块、数据库模块等 6 个阶 段,如图 1 所示。 现有手绘草图系统的草图特征表 示阶段根据特征提取单元不同一般可分为基于笔划 描述的草图特征表示、基于组合图形的草图特征表 示和基于形状特征的草图特征表示。 图像反馈模块 主要体现在对查询结果进行反馈、通过机器学习方 法度量用户绘制意图等方面。 图 1 基于手绘草图的图像检索系统框架图 Fig.1 The system framework of hand⁃drawn sketch⁃based image retrieval 1.1 手绘草图的预处理 对手绘草图的预处理主要用于消除由用户绘图 习惯不同以及草图固有的随意性而引发的噪声。 噪 声处理包括曲线闭合处理、冗余点去除、笔划合并 等。 不同的手绘草图检索系统采用不同的草图预处 理方法,为草图特征表示阶段做准备。 下面分别介 绍基于笔划描述的草图特征表示、基于组合图形的 草图特征表示和基于形状特征的草图特征表示所对 应的预处理方法。 基于笔划描述的草图预处理阶段主要对草图笔 划进行处理:采样、冗余点去除、平滑处理,并计算笔 划的特征值,比如方向等信息[7-8] 。 李雪峰等[9] 还 添加了笔划合并以及多旋转检测。 笔划合并和多旋 转检测都考虑了多笔划输入的情况。 汪文睿等[10] 还提出了对草图笔划进行简化的思想,并将对带阴 影区域的草图的处理称为草图简化,通过测量笔划 密度进行阴影区域的判断。 基于组合图形的草图特征表示,主要考虑图元 间的位置关系,因此在预处理阶段,首先将图形分割 为基本图元(圆形、三角形等),然后对基本图元进 行噪声处理。 孙正兴等[11] 认为对基本图元的噪声 处理主要包括冗余点去除、聚点消除、端点校正和闭 包计算。 冗余点通过设定某个结点到相邻结点的阈 值进行判断。 而聚点是那些点密度较大的点,通过 ·168· 智 能 系 统 学 报 第 10 卷
第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]提出使用笔划的空间 别和修正手绘的几何草图,用图表示线的关系,并设
计算草图点密度并设定密度的阈值进行聚点的判 断,并用重心代替消除。 端点校正则是处理起点和 终点难重合的情况。 处理方法为:将顶点边反向延 长交叉,交叉部分比例小于阈值则删除。 闭包计算, 利用平面点集的闭包算法将凹多边形变为凸多边 形,为后期图元拟合做准备。 而基于形状特征的草图特征表示大部分以提取 轮廓特征为主,因此,在预处理阶段,常采用八连通 区域自适应追踪算法来获得草图边界轮廓[12] 。 龚 健 等[12]在此基础上改进,提出基于四向连通种子 填充的封闭性判断算法进行封闭性判断。 然后对于 封闭和非封闭的区域,分别用不同的算法提取轮廓。 此外,Eitz 等[13] 还提出应用 Canny 边缘检测,并设 定像素位置距离标准差去除不属于草图的线。 然而 Canny 算法仅利用了图像的亮度信息, 而 Berke⁃ ley [14]边缘检测算法综合利用了图像的亮度、色度和 纹理三方面的信息,计算出每个像素作为边界的概 率并用图中每个像素点的灰度值表示,得到概率图。 这种表示方式与人对图像轮廓的理解更相近。 1.2 草图的特征表示 草图特征表示旨在描述预处理后草图的特征。 本文根据特征提取单元不同,将草图特征表示方法 分为:基于笔划描述的草图特征表示、基于组合图形 的草图特征表示和基于形状特征的草图特征表示。 1.2.1 基于笔划描述的草图特征表示 由于笔式交互以笔划为绘制基本单元,因此,可 以提取笔划的特征来表示草图。 对笔划的特征提取 分为离线特征提取和在线特征提取。 离线特征提取 即在用户抬笔后,特征提取才开始。 早期基于笔划 的特征表示,不仅是离线特征提取,还需要训练用户 手势。 手绘草图匹配的难易与用户草图绘制的自由 度相关,对用户输入限制越多的草图,匹配越准确。 如 1991 年 Rubine 等[15] 提出手势特征提取工具 GRANDMA,通过学习指定的单笔划手势,构造手势 识别器来表示特征,该方法采用包围盒对角线的长 度及倾斜度、起点与终点的距离等 11 个几何特征和 笔划的最大速度值、起点到终点的时间值 2 个动态 特征 来 描 述 单 笔 划 图 形。 Rubin 的 工 作 后 来 被 Long [16]延伸,他提出新的特征集合,但仍然需要严 格的训练,即用户要用同样的方式(逆时针画圆和 顺时针认为不同)绘图。 为了减少对用户输入的限 制,Hse 等[17] 提出用 Zernike 矩描述子来描述用户 输入的笔划,这种方法与笔划顺序、完成同一个图形 的笔划数量和方向无关,同时满足平移、缩放和旋转 的不变性。 此后孙正兴等[18] 提出使用笔划的空间 关系进行笔划的自动成组。 在草图特征表示方面, 他采用朴素贝叶斯分类器,在离线情况下对草图和 样本分割,得到基本图元,然后计算一个六维度特征 向量,最后对用户草图得到的特征向量和样本特征 向量分布进行比较,完成笔划集的特征表示。 在线特征提取与用户的书写绘画过程同时 开始、同时结束。 用户可以及时了解计算机是否 正确认识自己的意图。 随着用户的输入,新像素 点加入,特征也随之更新,计算机应找到与当前 特征最匹配的图形。 早期的研究,只能匹配几种 几何图形[ 19] 或算法复杂度高[ 20] 。 李俊峰等[ 21] 提出增量式意图提取的草图识别算法采用增量 式意图提取的方式理解用户的勾画意图。 增量 式意图提取通过不断收集用户的输入信息,并分 析历史记录,然后对现有信息进行分析,进而根 据当前信息修正以前生成的意图段落,是一个迭 代的问题求解过程。 实验证明,增量式意图提取 通过迭代的修正笔划,可以识别多种输入图形。 近期,微软公开了一种基于手绘草图的在线图像 检索引擎———MindFinder [ 22] ,它将由笔划形成的 线条所包含的形状信息转化为一种由像素坐标 与方向角共同表示的边缘像素词典,简化对形状 特征的描述的同时保持了轮廓的空间信息。 之 后,上海交通大学[ 23] 在 MinderFinder 基础上做了 改进,它认为提取的笔划的方向角特征中包含冗 余信息,不能准确地描述草图的轮廓信息。 通过 将方向图组合为轮廓显著性图,并分别对主要区 域和感兴趣区域进行查找可以克服 MinderFinder 不能找到位置、大小相差较大的场 景 图 像 的 情 况。 然而基于笔划描述的特征表示方法,无论在 进行离线、在线特征提取后都难以找到图形的唯 一表示,并且对于笔划复杂的图形,适应性较差, 仍需进一步提高笔划特征的可分辨性。 1.2.2 基于组合图元的草图特征表示 在用户的实际应用中,所要检索的图形有可能 是种类繁多的一个或多个图元构成的复杂图形。 而 多个图元构成的复杂草图可以利用组合图元来表示 草图特征。 基于组合图元的草图特征表示,在预处理阶段 已经完成了图元分割、噪声的处理。 特征表示阶段, 对基本图元进行识别,最终利用图元间的空间关系 进行检索。 图元识别是寻找与输入草图最相近并接 近用户输入的图形。 对于图元的识别已经有很多研 究。 如 Revankar 等[24] 提出用独立的几何模型去识 别和修正手绘的几何草图,用图表示线的关系,并设 第 2 期 辛雨璇,等:基于手绘草图的图像检索技术研究进展 ·169·
·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)相结合的方法实现在线检索,通过 基于组合图形的草图特征表示,着眼于草图中 对小数据库和较大数据库进行实验都取得了良好的
定连通性、相对方向、相等和平行性的阈值判断来确 定线与线的关系去修正手绘笔划,使其更接近用户 想画的图形。 Sezgin 等[25] 提出的系统用探测最高 曲率和最低速度点的方式去识别图形。 但是 Sezgin 的系统仅可以识别出简单的几何图元,包括直线、圆 和由直线和曲线组成的简单合成图形。 而 Yu 等[26] 提出的领域无关的草图识别系统,对图元的识别扩 展到了折线、椭圆、弧和螺旋结构。 他认为仅用曲率 判定,容易被噪音所误导,因此引入特征面积的概 念,并将方向、曲率和特征面积结合将用户所绘制草 图近似为标准的图元。 后来 Paulson 等[27]提出一个 精准的手绘草图识别系统 PaleoSketch,他认为像 Sezgin 和 Yu 提出的那些简单图形的识别器在手绘 草图领域的通用性不强,很难识别由图表和草图构 成的复杂符号。 所以 Paulson 在 Sezgin 和 Yu 的基 础上,又引入了 2 个新的特征值,NDDE ( normalized distance between direction extremes)和 DCR(direction change ratio), NDDE 是用总笔划长度除以最高方向 值和最低方向值之间的距离,得到方向相反线的百 分比;DCR 则是最大方向变化量占平均方向变化量 的百分比,用于更好地区分折线和曲线,在识别阶段 获得较好的效果。 此外,孙正兴等[11] 和团队在其开 发的 Smart Sketchpad 系统中提出用引力模型(认为 点与点有相互吸引的趋势),通过设定阈值将点合 并的方法,对基本图元分类。 并提出图元内规整和 图元外规整的方法。 例如,判断三角形两边近似等 长则规整为等腰三角形的方法为内规整。 利用图元 间相邻信息,将相近图元规整为相同大小的方法为 外规整。 该系统使用的是识别图元的基本方法。 李 雪峰等[9]则又对图元进行了扩充,支持直线、折线、 圆弧、曲线、同心螺旋线、异心螺旋线、椭圆、圆等 8 种基本图元以及多种图元组成的复杂图形。 识别出 基本图元后,可以将不同复杂层次的图形元素抽象, 从而获得统一的表示。 例如组合图形属性包括图形 元素类型、坐标、尺寸等。 组合图形的空间关系包括 图形元素的相对位置关系、相对方位、相对旋转等。 张莉莎等[28]则提出将复杂图形描述转化为不同信 息粒度的属性和空间关系表示。 但草图本身具有模 糊性和不确定性,加上线条数目繁多,难以对其施加 判断和约束。 此外,组合图形越复杂,空间关系的信 息维数越多,计算量越大。 因此基于组合图元的草 图检索还需要依赖相关领域知识和上下文信息简化 对复杂组合图形的表示过程。 1.2.3 基于形状特征的草图特征表示 基于组合图形的草图特征表示,着眼于草图中 图元的空间关系。 而基于形状特征的特征表示,着 眼于草图自身的外在形状特征。 早期的研究采用闭 包盒大小、最大内接三角形、或傅里叶描述子等作为 形状特征表示[29⁃31] ,检索效率低,时间复杂度高。 之后很多研究主要在草图轮廓的基础上提取轮廓的 全局特征或局部特征作为草图的形状特征表示。 全 局特征着眼于整幅图像,能更好地描述图像中物体 的相对位置。 如 Chee 等[32]采用 MPEG⁃7 标准中提 出的边缘直方图(edge histogram descriptor, EHD) , 具有描述图像像素变化方向的能力。 它通过统计每 个子图块含有垂直、水平、45°、135°及无方向 5 种边 缘特征形式的个数, 形成了五维特征向量, 因此 EHD 利用 5 个方向的直方图提取特征,更注重图像 的整体信息。 但是 EHD 对于子图和方向的划分十 分粗略,描述轮廓的能力有限。 此外,李曼舞等[3 3 ] 提出对草图预处理后,对质心距离形状描述子进行 傅里叶变换并除以直流成分生成傅里叶边界描述子 描述草图的形状特征。 高竹红等[3 4 ] 在李曼舞的基 础上,对生成的傅里叶描述子进行傅里叶反变换再 得到图像轮廓,将轮廓点到质心点进行连接得到轮 廓结构图,构造邻接矩阵并提取矩阵的特征向量进 行检索。 而吴明珠等[3 5 ] 提取轮廓成对几何直方图 作为区域描述子,成对几何直方图是链码编码直方 图的一种扩展,是由角度和距离 2 个维度构成的二 维直方图。 钱晶等[3 6 ] 提出使用一种仿射变换自适 应骨架提取算法来提取对象骨架,构造骨架树描述 符进行图像表示。 最后将图像的骨架特征与轮廓特 征结合进行检索。 此后,钱晶等[3 7 ] 在之前只采用 形状特征表示的基础上,又结合了颜色和纹理特征 进行表示。 为了加快检索速度,对每一个图像特征 都使用了粗尺度和细尺度特征。 先用粗尺度快速计 算区域相似度,丢弃不匹配的区域;再用细尺度特征 完成相似度的精确计算。 特别地,Eitz 等[13] 提出著名的特征袋( bag⁃of⁃ features)描述子,通过对形状内容描述子、星点描述 子、改进的标准方向梯度直方图描述子分别进行实 验和评估发现, 改进的标准方向梯度直方图描述子 表现最优。 通过随机提取图像中的感兴趣点,以每 个感兴趣点的邻域为单元,计算梯度方向直方图并 取其主方向作为该感兴趣点的边缘特征,最终形成 了一个特征袋。 Lukas 等[3 8 ] 认为之前的系统都缺 少在互联网环境下检索图像的能力,他提出将方向 梯度直方图和离散距离变换(discrete distance trans⁃ formation,DDT)相结合的方法实现在线检索,通过 对小数据库和较大数据库进行实验都取得了良好的 ·170· 智 能 系 统 学 报 第 10 卷
第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)与草图 手绘草图检索系统,从而将草图检索系统应用于更 线条映射图中的点相似。这种方法称为可索引的定 广阔的领域。本文现将基于手绘草图的检索系统现
效果。 然而,基于形状特征的草图特征表示难以区 分形状相似的不同物体,因此,还需要结合语义对图 形分类或者利用草图识别提高检索精度。 1.3 草图的特征匹配 为了加快检索速度,需要对图像库也进行预处 理,形成图像特征库。 将草图的特征和图像特征库 进行匹配,即特征匹配阶段。 对图像库预处理首先 缩小图像库中图像大小,然后一般采用与输入草图 同样的处理方法对库中的图像进行预处理和特征提 取。 匹配时,需要根据不同的草图特征表示方法找 到合适的相似度计算方法。 基于笔划描述的草图检 索方法,大部分采用转换为计算特征向量之间相似 性度量的方法,其中欧式距离由于计算简单、效果 好,被许多系统采用[12,3 6 -3 7 ] 。 也可以表示为点的序 列,计算 2 个序列中相对位置相同项占所有项的比 例,即相关系数法 [13, 39 - 4 0 ] 。 基于组合图元的特征 表示,在识别基本图元后,首先要进行图元成组。 然 后进行部分结构相似性计算和整体相似性计算。 部 分结构相似性计算包括图形构成相似性计算和图形 骨架间的相似性计算[11] 。 实质上就是把图元构成 和骨架结点都转换为多维向量或结点数组的计算。 还可以基于空间关系计算组合图元的相似度,将空 间关系转化为空间拓扑图和层次结构图,用拉普拉 斯图谱转换为特征向量[4 1 -4 2 ] 。 最后利用欧式距离 进行相似度计算[4 1 ] 。 对于复杂的组合图形的检索 方法,可以在匹配阶段,找到源空间关系图和目标空 间关系图的映射关系,但是匹配复杂度很高。 也可 以采取约束的部分枚举算法[2 8 ] ,满足顶点匹配约 束或边匹配约束的序列可以从当前状态略去无效序 列直接到达后继状态,节省了大量的计算。 此外,基 于形状特征的草图特征表示除了转化为向量特征表 示,还包括直方图特征表示和骨架特征表示。 基于 直方图特征的草图匹配可以采用复杂度很低的直方 图相交算法来计算直方图的距离[3 5 ] ,数值越小,相 似度越高。 基于骨架特征的草图匹配,对骨架树的 分支分别计算相似度,对于子节点需要由分支相似 距离计算节点相似距离,最后由上述结果根据各自 权重相加计算骨架树相似距离[3 6 -3 7 ] 。 MindFind⁃ er [2 2 ]中,提出倒角匹配(chamfer matching) [4 3 ]和定 向的倒角匹配(oriented chamfer matching)方法[4 4 ] , 但前者时间复杂度高,后者内存花销大。 因此,该文 将利用定向的倒角匹配生成的草图线条距离图转变 为有 N 个方向通道的击中映射图(hit map),并验证 待匹配图像中是否有某个边缘像素( edgel) 与草图 线条映射图中的点相似。 这种方法称为可索引的定 向的 倒 角 匹 配 ( indexable oriented chamfer matc⁃ hing) [2 2 ] ,节约了物理花销并具有局部形状不变性。 1.4 图像反馈 利用视觉信息检索,能够增加检索的有效性,却 造成视觉信息和高层语义之间的鸿沟。 为了架起高 层语义和底层特征的桥梁,需要对草图检索结果进 行语义提取。 反馈是语义提取的一个重要方面,主 要包括对查询结果进行反馈、通过机器学习方法度 量用户的绘制意图等方面。 早期的反馈多采用查询 点移动策略[4 5 ]或权值再计算。 通过重新排列检索 结果来改善检索效率,虽然这种反馈对系统而言无 本质的提高,但是用户在搜索结果上的行为数据是 分析用户心理的重要数据来源,如何基于这些数据 提高排序质量,也是一个值得研究的问题。 后来的反馈系统引入机器学习方法。 例如引入 SVM 学习方法[11,4 6 ] ,一些检索系统采用经典的二 值 SVM 或单类 SVM 分类器。 然而二值 SVM 忽略 正反例数量不对称的情况,而单类 SVM 则对反例信 息不适用。 因此应用这 2 种经典的 SVM 得到的检 索效果都不理想。 梁爽等[4 6 ] 在此基础上提出了有 偏 SVM,通过学习用户对草图的理解和主观评价, 并实时捕捉用户的查询兴趣,使搜索的结果更加接 近用户的意图。 袁贞明等[ 4 7 ] 通过计算草图结构中 贝叶斯网络拓扑结构的最大后验概率,根据用户输 入的笔划信息对笔划进行动态最优分组,保证了笔 划输入的连续性,提高了分组效率。 裴继红等[4 8 ] 提出带反馈机制的闭环隐马尔可夫模型,采用带压 缩率调整因子的特征压缩算法,在计算各个后验概 率后进行满意度判断,以确定是否调整压缩因子。 裴继红将这种方法应用于手绘图形的识别,通过实 验证明带反馈机制的闭环隐马尔可夫比开环隐马尔 可夫有更高的识别率。 然而目前机器学习的方法并 没有人工标注图像的方法发展的成熟,因此可以采 用人工标注的方法辅助检索,缩小检索范围,例如 Sketch2Photo [5 2 ]首先用关键字查找,然后再提取草 图特征进一步查找。 总之,利用人工标注图像语义 的方法极大地缩小了视觉信息和语义的鸿沟,仍然 被广泛采用。 2 手绘草图检索系统现阶段的应用 现有基于手绘草图的检索技术的相关文章大多 可归为于本文所总结系统框架的某个或某几个模块 的研究范畴。 通过对之前研究的分析,提出手绘草 图的手绘草图检索系统框架,旨在建立领域无关的 手绘草图检索系统,从而将草图检索系统应用于更 广阔的领域。 本文现将基于手绘草图的检索系统现 第 2 期 辛雨璇,等:基于手绘草图的图像检索技术研究进展 ·171·