主观轮廓提取方法.docx

商标中主观轮廓提取方法*宋建国1,2； 吕肖庆1； 王剑明2 ；汤 帜1（1. 北京大学计算机科学技术研究所，北京，100080；2. 73630部队）摘要：在商标设计中常用多个连通分量之间空白区域形成主观轮廓，它与单连通分量形状一样可以很好地反映整个商标的主体特征。本文基于轮廓点Delaunay三角剖分，提出了一种多连通分量间的主观轮廓提取算法。重点分析了主观轮廓与多连通分量间空白区域内三角形边的关系，提出了一组关于种子三角形选取和三角形边的膨胀规则。实验结果表明，算法不仅能够有效地处理经典的主观轮廓图形，而且对于商标图形同样能够提取出符合人类视觉的主观轮廓。关键词：主观轮廓 Delaunay三角剖分 膨胀规则中图分类号：TP391A Subjective Contour Extraction Method for Trademark ImagesSong Jianguo1,2； Lu Xiaoqing1； Wang Jianming2； Tang Zhi1(1. Institute of Computer Science and Technology, Peking University, Beijing, 100871, China 2. 73630 Unit, )Abstract：A subjective contour in space among components is considered as the perceptual shape that exists in the space between real contours, the subjective shape information is useful for describing image content, and sometimes even more important than the shape of a single component. Based on the Delaunay triangulation, this paper proposes a method for the construction of subjective contours in the space among components. Through the analysis of the relation between the subjective contour and the edge of the triangle among components and put forward a set of seed selection and triangle dilating rules. Experimental results show that the proposed algorithm not only is able to deal effectively with classic subjective contour, and also can process trademark images.Key words：Subjective Contour Delaunay Triangulation Dilating Rules1 前言基金项目：国家重点基础研究发展计划（973）（2010CB735908）作者简介：宋建国（1981-），男，硕士研究生，研究方向：网络内容信息抽取与模式识别。E-mail:主观轮廓是一种重要的视觉心理现象，它是指在物理上并不存在却可被感知到的闭合轮廓，我们将商标图形连通分量本身称为正形，也称图；将其周围的“空白”称为负形，也称为底，负形的轮廓不同于孔洞，没有真实的闭合轮廓，但能被视觉感知到，因此在本文中也被视为主观轮廓。研究主观轮廓对于探讨人类视觉系统中物体识别的形成机制有着重要的意义，而在复杂图形中，比如商标，其包含的主观轮廓有时能够反映出整个图形的主体特征，当视觉在感知复杂图形时，由于视知觉的选择性，比如图1(a)(b)，主观轮廓的信息显然比原始的轮廓更具有主体性，再如图1(c)(d)，原始轮廓不相似，但主观轮廓的形状则具有明显的相似性，都近似“H”形。另外从商标设计的角度出发，设计师为了创作出传情达意的标志，经常采用图底反转方法，具体表现为正形和负形作为同样重要成分出现，共用边缘，相互关联，相互衬托，相互交织成一个有机的整体。因此复杂图形中的主观轮廓提取对理解和分析其内容有重要作用。关于主观轮廓的提取，近年来国内外学者提出了一些模型和算法，邵晓芳等1提出了一种基于视觉竞争合作机制的主观轮廓提取方法，通过用图像处理的方法代替复杂的细胞动力学方程模拟了生物视觉系统的竞争合作机制。Zhu Wei等 2提出了一种基于水平集的变分模型，Jung等3受到Zhu Wei等前人变分模型提取主观轮廓工作的启发，提出了一种简单的基于能量最小化的数学模型分析和模拟主观轮廓。另外，Soffer等4在多连通分量的形状相似性匹配中，结合了正形和负形特征，并在形状分类中取得了有效的结果，但其负形并不能直接刻画视觉感知出的形状特征，仍然是一种全局特征。(a)(b)(c)(d)图1 带有主观轮廓的复杂图形Fig.1 Multi-Component Shape with subjective contour从实验对象方面看，现有的研究主要集中于一些典型主观轮廓图形，比如Kanizsa三角形、主观圆和Ehrenstein中心光亮圆盘等，已有算法在针对特定图形的处理中能够得到较好的效果，但无论在提取效果和效率上都很少见到在大数据集中的测试结果，而且没有一种方法能够适用于所有类型的主观轮廓图形5，本文针对商标复杂图形，提取由连通分量部分轮廓段形成，能够被视觉感知的主观轮廓。本文后续结构如下：第二部分详细阐述主观轮廓提取算法；第三部分给出实验结果及分析；第四部分对全文进行总结并提出下一步的研究方向。2 主观轮廓提取算法2.1 原理商标中主观轮廓一般是以闭合的单轮廓形式存在，对于单轮廓形状，首先介绍一下如何通过轮廓点Delaunay三角剖分后所得的边获取原轮廓，由轮廓点的Delaunay三角剖分结果可以获得其骨架结构6，如图2所示，将轮廓内部三角形每条边的中点就近连接起来即可得到原轮廓的骨架，其中，边的两个端点不能是轮廓上的相邻点，根据Blum7对轮廓中轴骨架的定义，每个骨架点都对应原始轮廓上至少两个点，这些点与以该骨架点为圆心的最大圆盘相切，这些点被称为该骨架点的生成点，而且通过骨架点和轮廓点的这种对应关系，可以实现从骨架恢复轮廓的过程，这个过程同样可以用三角形的边去恢复原轮廓，边的端点可以认为是以该边中点为骨架点的生成点，如图2(b)所示，A和B即为边E的生成点，红色骨架所在边对应的黑色原始轮廓。接着我们再分析主观轮廓，如前文所述，主观轮廓是人类在视觉上基于多个连通分量的部分边缘知觉到的完整轮廓，如图1所示，其物理组成并不完整。我们利用上述方法能够通过连通分量空白区域内的边获取主观轮廓的部分轮廓段，再用Delaunay三角形边将不连续的轮廓段连接起来即可获得完整主观轮廓。本文是通过制定种子三角形选取和边的膨胀规则，采用迭代膨胀的算法去获取部分轮廓段并将其连接成完整轮廓。(a)(b)(c)ABE图2 (a)原始形状及轮廓点的三角剖分结果; (b)(a)中矩形区域内的局部轮廓的骨架; (c)原始形状的骨架结构.Fig.2 (a) Original shape and the result of DT; (b)The skeleton of the local shape in (a); (c) The skeleton of the Original shape.2.2 算法描述基于主观轮廓与三角形边的对应关系，通过对多连通之间的边进行分析，利用满足膨胀条件的边去恢复对应的原始轮廓，膨胀后闭合区域的边缘即为主观轮廓。PNNPNN(a)(b)(c)EEeEsPePsEEeEsPePs图3 (a)当前边E所在矩形区域; (b)E膨胀前; (c)E膨胀后.Fig.3 (a) Rectangular region where edge E is located; (b) Before dilating at edge E; (c) After dilating为了方便理解和描述，首先对符号及有关定义说明如下：集合S = OB1,OB2OBm表示所有连通分量的轮廓，m表示连通分量个数，OBi=pi1,pi2piNi，i=1,2m，表示第i个连通分量轮廓坐标点集，Ni表示第i个连通分量轮廓点个数，并且pi(j+1)是pij第i个连通分量轮廓顺时针方向相邻的点，这里1jNi 且pi(Ni+1)=p1，Delaunay三角剖分的点集为TP = OB1OB2OBm，如图3所示，Delaunay三角剖分后所得到的三角形边用E=(ps,pe)表示，ps为起点，pe为终点，位于边E的右侧的对应三角形顶点用pNN表示，它与两个端点ps，pe构成三角形，边E的右侧也称边E外侧，以ps为起点pNN为终点的邻边表示为Es=(ps,pNN)，以pNN为起点pe为终点的邻边表示为Ee=(pNN,pe)。当ps,pe属于不同轮廓时对边E的膨胀是指：用E右侧的两条邻边Es和Ee替换E的过程，当ps,pe属同一轮廓，并且从ps到pe的轮廓段与边E形成的闭合轮廓在E的右侧，所谓对E的膨胀就是用ps到pe的轮廓段替换E，这个轮廓段用CSE表示，用L(CSE)表示CSE所包含边的个数。2.3 算法流程如图4所示，提取主观轮廓算法主要步骤如下：(1) 初始化 选取种子三角形作为初始主观轮廓，Ssub=E1,E2,E3，Ei表示种子三角形的边，i1,2,3，且沿逆时针首尾相连，Nsub=3，Nsub表示当前主观轮廓边的个数。(2) 膨胀操作 从Ssub选择一条边Ei，利用膨胀判断函数If_dilate(Ei)决定是否膨胀，如果函数返回值为真，则Ei膨胀，当Ei的两个端点pis,pie属不同轮廓时，将Ei替换成两个邻边Eis和Eie，更新 Ssub=Ssub-Ei+Eis,Eie，Nsub=Nsub+1，当pis,pie属同一轮廓并且CSEi位于Ei的右侧时，Ssub=Ssub-Ei+CSEi，Nsub=Nsub+LCSEi-1。如果返回假则Ei不膨胀，Ssub不变，这时Ei就起到了修复不完整轮廓的作用。关于膨胀判断函数的定义将在2.4部分详细介绍。(3) 迭代执行步骤(2) 从当前主观轮廓Ssub中，选择与Ei的逆时针相邻下一条边Ei+1，以深度优先的顺序重复(2)的操作，直到Ssub中所有边都不满足膨胀条件。(4) 输出 输出最终主观轮廓Ssub=E1,E2ENsub。(a)(b)(c)(d)(e)图 4 算法流程. (a)原图; (b)三角剖分; (c)种子三角形（红色）,原始轮廓（蓝色）以及原图的凸包（绿色）; (d)膨胀; (e)主观轮廓结果（红色）.Fig.4 The workflow of the proposed algorithm. (a) Original image; (b) The result of DT; (c) Seed (red), Original contour (blue), Convex hull (green); (d)Dilating; (e) Result(red).2.4 种子选取与膨胀规则在本算法中，种子选取和膨胀条件的判定起着至关重要的作用，分述如下：（1）选择种子三角形要满足两个条件，第一，种子三角形要位于背景，以保证主观轮廓是完全从背景中提取的，这里说的背景是相对的，是指在二值图像中与前景相对颜色的区域；第二，要满足最小角最大的原则，因为最小角最大的三角形最有可能是骨架的分支点所在的三角形，可使得边膨胀后获得更多骨架分支对应的轮廓。（2）当前边E的膨胀规则，当前边如果膨胀需要同时满足三个规则，第一，当前边E的两个邻角PNNPsPe和PNNPePs不能过大，即最大值要小于阈值AT，否则轮廓膨胀过程会出现突变，产生不平滑的轮廓，继续膨胀的部分不再是主观轮廓的区域，即不符合人的视觉编组原则，此时要停止膨胀；第二，当前边大于指定阈值时，表示当前边还没有到达主观轮廓边缘应继续膨胀，也说明有更大的区域被膨胀作为主观轮廓区域的一部分，但当小于等于指定阈值时，表示当前边已经接近主观轮廓边缘，所以要求当前边的变化应该是递减的，直到不满足此条件停止膨胀。因此，当前边E要满足长度LELT或LELT且LEsLE,LEeLE，LT为长度阈值，实验中阈值LT选择为种子三角形内切圆半径的倍数，因为此半径在一定程度上可以反映出连通分量间缝隙空间的大小；第三，当前边E要满足位于凸包内部，即ECH，其中CH为凸包边的集合，否则停止膨胀，因为复杂图形中的主观轮廓是由凸包内部的部分真实轮廓边缘形成的，超出凸包就脱离了连通分量的物理边缘。综上分析，对于当前边E是否膨胀可总结为以下函数If_dilate(E)，如果返回真(1)，膨胀，否则返回假(0)，不膨胀。If_dilate(E)=1(maxPNNPsPe,PNNPePsLT)|LELT&LEsLE,LEeLE&ECH0其他3 实验结果实验数据选择了四种经典的主观轮廓图形5，包括Kanizsa三角形、Kanizsa四边形、主观圆和Ehrenstein中心光亮圆盘，结果如表1所示，对于复杂图形的实验，数据选自MPEG-7 CE-2商标库和英国专利商标局数据集中部分含有主观轮廓的复杂图形，结果如表2所示。参数AT = 120度，由于四种经典主观轮廓相对商标图形都是很规则的形状，结构简单，因此提取经典主观轮廓图形的参数LT要比复杂商标图形设置的大一些，LT越大获取到的轮廓距离种子三角形越近，输出的结果越简单，实验中，提取经典主观轮廓图形时LT设置为种子三角形内切圆的半径的6倍，相反，LT越小获取到的结果结构越复杂，表现形式越丰富，商标图形LT设置为种子三角形内切圆的半径。从实验结果看，无论是经典的主观轮廓图形还是商标这样的复杂图形，本文算法通过固定一组阈值都可以提取出符合人视觉感知的主观轮廓，但在相同阈值下，对于个别商标图形的提取效果不够理想，比如表2中第四行第四个商标出现了过度膨胀的情况，这种问题可通过增强阈值的自适应能力来解决。另外本算法从原始轮廓到输出结果时间复杂度为O(nlogn)，n为轮廓点个数。表1 经典主观轮廓图形提取效果Table 1 Extraction result for classic subjective contour原图主观轮廓原图主观轮廓原图主观轮廓原图主观轮廓表2 商标图形的主观轮廓提取效果Table 1 Subjective contour extraction result for trademark images原图主观轮廓原图主观轮廓原图主观轮廓原图主观轮廓 4 结论本文基于Delaunay三角剖分及其与主观轮廓的对应关系，提出了一种针对商标图形的主观轮廓提取算法，不仅能够有效地处理经典的主观轮廓图形，对于商标库中的复杂图形同样可以提取出符合人类视觉感知的主观轮廓，提取出的主观轮廓为进一步分析和理解其内容提供了重要依据。下一步的研究重点是如何使算法更具有更大的自适应性，并利用曲线连接修复主观轮廓不完整的部分。参 考 文 献1. 邵晓芳，姚伟，孙即祥. 基于视觉竞争合作机制的主观轮廓提取J. 中国图象图形学报，2005, 10(8): 1024-1028. Shao Xiaofang, Yao Wei, Sun Jixiang. A Method for Subjective Contour Based on Competition cooperation Mechanism of Visual ModelJ. Journal of Image and Graphics, 2005, 10(8): 1024-1028.2. Wei Zhu, Tony Chan. A Variational Model for Capturing Illusory Contours Using Curv