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