基于Modular积图和最大团的草图形状匹配技术研究

With the development of touch-based interfaces, sketch-based applications and interaction become more and more popular in both professional activities and general tasks. Sketch matching plays a significant and fundamental role in various sketch-based applications, such as sketch recognition, sketch retrieval, etc. Actually, the ultimate goal of the research of sketch matching is to design certain computational models that can measure the similarity between two shapes automatically and effectively, in consistency with subjective visual perceptions. Currently, however, the matching ability of the state-of-the-art sketch matching methods, especially partially matching ability, cannot highly correlate with subjective perceptions. To this end, we will lay our focus on devising novel high performance sketch matching methods in this project. Specifically, the newly proposed sketch matching method will be based on graph-based representation and product graph and maximal clique theory, for which there are several justifications. On one hand, graph-based representation is effective in dealing with the characteristics of uncertainty of sketches. On the other hand, the product graph and maximal clique theory is a flexbile and effective way of supporting partial matching in graph matching problems. Thus, in this project, we will attempt to integrate these two theories together appropriately and to introduce them into the sketch matching community. And accordingly, based on them, we will propose some novel high performance sketch matching techniques. The anticipated output of this project will benefit greatly the whole sketch-based interaction community both in theory and in application.

近年来，随着触摸屏的普及，草图交互技术及其应用已渗透到国民经济的各个行业和国人的日常生活中。在草图识别/检索等很多草图交互系统中，草图形状匹配技术都扮演着基石的角色。草图形状匹配研究的最终目的是希望提出某些度量算法，进而有效、自动地计算两个形状之间的相似度，并希望计算的结果能够和人的视觉感知高度一致。目前的方法对草图形状的匹配能力（尤其是部分匹配能力）还达不到和人的视觉感知高度一致的程度。鉴于此，在本项目中，我们将致力于提出新的高精度的草图形状匹配方法。拟提出的新方法将建立在图模型表示和积图与最大团两个理论基础之上。这是因为：一方面，图模型表示可以有效地处理草图的不确定问题；另一方面，积图与最大团可以灵活地支持部分匹配。我们将尝试把这两个理论有机结合，并有效地引入到草图形状匹配领域中，来构建全新的高精度的草图形状匹配方法。本项目的预期成果将在理论和应用两个方面极大地促进草图交互领域的发展。

随着近年来高精度触摸屏和虚拟现实等技术的快速发展，自然智能的人机交互界面成为下一轮科技浪潮中的热点。其中，基于手绘草图的交互方式由于其灵活、直观、高效的优点成为了输入图形数据的重要手段，在基于草图的内容（草图，图像，三维模型等）检索，图形构思与协调合作、编辑等任务中具有广泛的应用。. 本课题重点研究高精度的草图形状匹配问题，致力于提出新的高精度的草图形状匹配方法，并希望其计算结果能够和人的视觉感知高度一致。项目执行期间进展顺利，在项目组的努力下超额完成了原定目标，发表了多篇高质量学术论文，申请发明专利3项。. 草图形状匹配问题是所有基于手绘草图输入的应用的核心问题。由于手绘草图数据所固有的模糊性、不规则性和不完整性等难点，现有方法均难以取得满意精度。本课题提出了基于积图的匹配方法，创造性地将拓扑特征提取，拓扑图模型表示和积图中的最大团搜索问题结合起来，大幅度地提高了匹配精度，较之前方法提高21%。值得一提的是，我们的方法首次有效的支持基于不完整草图的部分匹配，而之前并无实际有效的解决方案，从而极大地提高了用户的输入效率。相关代表性成果发表于国际顶级期刊TPAMI。. 本课题同时研究如何有效抽取图像数据的高层语义信息，使之符合人的高层视觉感知，从而适用于基于草图的图像检索。我们通过全局优化的方法将图像前景和背景的信息结合起来计算图像中的显著区域，进而实现草图与图像内容的匹配。所提出的图像显著区域提取算法达到了国际领先水平，在2015年的综合评比中（含40种最新的算法）获得第二。论文发表于计算机视觉顶级会议CVPR 2014，迄今被引用238次，获得学术界的广泛认可。. 综合而言，本项目提出的高精度的草图匹配技术和检索系统具有重大的理论突破和实际价值，在图像检索，三维建模，智能家居，虚拟现实等多个领域将发挥显著作用。