卡通图像线条提取算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇卡通图像线条提取算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：卡通图像中，线条是最主要的构成其感知信息的元素，仅凭借线条，卡通图像即可表达自身的绝大部分信息。卡通图像中的线条的提取是计算机理解卡通图像的关键步骤。首先探讨了卡通图像中线条的分类，随后基于装饰线与边缘的剖面对高斯一阶导数及二阶导数的响应的差异，提出了基于一阶方向导数过零点与二阶导数极值点共同提取装饰线的方法；随后将提取到的装饰线与边缘融合最终生成卡通图像的线条。
关键词：卡通图像，线条提取，Hessian矩阵
中图分类号：TP391.41 文献识别号：A 文章编号：2095-2163（2013）04-
Decorative Line and Edge Extraction in Cartoon Images
ZHANG Tiejun， Ahmed A. Abd El-Latif， NIU Xiamu
（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150080， China）
Abstract： Decorative Lines and edges in a cartoon image are the most important elements to convey its semantic information. This paper proposes a method to extract both decorative lines and edges of the cartoon image at the same time. Firstly， the paper uses the Hessian matrix to compute the direction perpendicular to the decorative lines in the image. Then， non-maximum suppression is applied to the image’s second derivative of Gaussian to locate the possible decorative line’s center. Secondly， it also uses directional zero-crossing （the zero-crossing of the first Gaussian derivative on the pre-computed direction） to verify the existence of the decorative lines. Finally， decorative lines and the edges detected by non-maximum suppression on the first Gaussian derivative are fused together. The experimental results show that the proposed method is more effective than other existed methods in literature for complicated cartoon images.
Keywords： Cartoon Image； Curve Extraction； Hessian Matrix
0 引言
卡通（Cartoon）是指以漫画绘制稿为基础的2-D视觉媒体。作为一种特殊的艺术形式，卡通一般通过归纳、夸张、变形的手法来塑造各种形象，将复杂的对象进行简单化表现，颜色明快生动，人物结构简单、夸张，深受少年儿童的喜爱。历史上，涌现过大量的经典卡通漫画、动画。动画公司希望能够快速开发经典卡通潜在的商业价值，并同时保证期版权安全；运营商希望能够有效利用卡通而提供相应的检索、检测服务。以上问题的解决均有赖于对卡通内容的识别提取，也就是卡通图像中线条的最佳提取。
Zhang[1]提出卡通图像中的线条主要分为两种：其一是有区域和区域之间的间断性构成的边缘；其二是卡通创作者用来分割区域或者勾勒图案使用的实线。这两种线条都能够向用户传达卡通图像的语义信息，所以需要提取卡通图像的这些基本语义元素来帮助计算机理解卡通图像的内容。一些研究者已经开始关注卡通图像中线条信息的提取。Steger[2] 提出了一种提取实线结构的方法用于道路检测、经脉检测等，但没有考虑边缘；Sykora[3，4]假定卡通图像中的装饰线都是颜色较深的实线，采用高斯拉普拉斯算子（LoG）提取闭合轮廓的方法定位线条实线卡通图像矢量化。但因其对卡通线条的假设前提过于严格，使得该方法无法区分边缘与装饰线，在应用于现代卡通动画时，将直接导致两个问题：对卡通图像中线条的漏检和误检。Zhang 提出了另一个对大多数现代卡通都有效的矢量化方法，可独立提取卡通动画的边缘与装饰线。但是由于在部分情况下无法区分装饰线与边缘，所以尽管该方法对卡通图像的矢量化较为有效，但对线条的检测却常常出现误检，如图1（c）中，边界的检测明显存在着位置偏差。
Ping 提出了基于Delaunay三角剖分的方法来检测装饰线[5]，但是如果在预处理阶段对边界检测的不连续点不加以限制，该方法会陷入局部混乱状态。Huang等人提出的方法是采用各向异性滤波器来计算实线，但却无法有效提取边缘[6]。
本文提出一种分别提取装饰线与边缘的方法，提出了采用一阶导数零交叉点验证装饰线的存在，可以精确区分装饰线与边缘，从而更加清晰勾勒图像中的线条信息。
1 装饰线滤波响应特性
一般而言，为了更清晰地对区域进行划分或表现形状，装饰颜色都较深，是亮度较低的一个细条形结构。如图2 （a）所示，方形为一个典型的装饰线剖面图；图2（b）是一个在卡通中边缘的典型的边缘剖面。单独使用二阶导数滤波可以在装饰线中心的位置获得极值响应，如图2（e）中的极值响应，但同时也可能产生误检，如图2 （f）中的极值点也常被误检为装饰线。而由图2 （c）、（d）可见，装饰线在二阶导数滤波时产生峰值，同时伴随一阶滤波的零交叉点出现；边缘在二阶导数极值的位置不会出现一阶导数零交叉值。
（a） 典型装饰剖面；（b）典型边缘剖面；（c）装饰线剖面对一阶高斯滤波的响应；（d）边缘剖面对对一阶高斯滤波的响应；（e） 装饰线剖面对二阶高斯滤波的响应；（f） 边缘剖面对二阶高斯滤波的响应；
（b） 图2 装饰线与边缘剖面一阶、二阶滤波特性
（a） profile of classic decorative line，（b） profile of classic edge，（c） decorative line’s response to the first order Gaussian derivative， （d） edge’s response to the first order Gaussian derivative， （e） decorative line’s response to the second order Gaussian derivative， （f） edge’s response to the second order Gaussian derivative.
Fig.2 Characteristic of edge and decorative line when convolved by the first and second order Gaussian derivative
总结以上特性，可以得出以下结论：装饰线（深色实线）的存在一般伴随着两个必要条件：
（1）垂直于线条方向的一阶高斯导数在该位置存在过零点；
（2）二阶高斯导数在该位置存在极值点。
2 卡通图像线条提取算法
本文的卡通线条检测可以用如图3描述。
由图3可知，首先采用Hessian矩阵获得卡通图像中线条方向，在该方向上计算二阶方向导数极值点以及一阶导数过零点，二者的交集即为装饰线；随后由一阶导数极值获得卡通图像的边缘，将边缘与装饰线利用图像形态学方法整合，即得到了卡通图像中的所有线条。
2.1 基于Hessian矩阵装饰线方向计算
Hessian矩阵常用来判断一个临界点是鞍点还是极值点，本文利用此性质计算装饰线的方向。
将一幅卡通图像经过二阶高斯导数卷积生成的结果表示为，表示像素点位置。Hessian矩阵可以如下定义：
其中，，和表示二阶偏导数。Hessian矩阵最大的特征值对应的特征向量决定了二阶导数的方向。
（a） 一阶零交叉点；（b） 二阶高斯方向极值点；（c） 一阶零交叉点与二阶极值点的叠加；（d） 装饰线检测结果；（e） Hessian矩阵计算的方向
（a） Zero-crossing on the first order Gaussian derivation， （b） Directional maxima of second order Gaussian derivation， （c） Superposition of the zero-crossing on the first order Gaussian derivation and the directional maxima of second order Gaussian derivation， （d） The detected results of decorative lines， （e） Direction computed by the Hessian matrix.
Fig.4 The intervening results of decorative line detection
图4中，（a）表示一阶高斯导数零交叉点的检测结果，（b）表示二阶高斯导数极值点的检测结果，（c）为（a）和（b）中检测结果的叠加。采用（a）的检测结果对（b）进行验证，获得装饰检测结果（d）；（e）图显示了Hessian对线条方向的预测。
设Hessian最大特征值对应特征向量用表示，那么图4 （e）中所示箭头即为矩阵的特征向量的方向，箭头长度为；采用下面方程将方向归一化可得为：
2.2 一阶方向高斯微分零交叉点监测
表示卡通图像上点由一阶高斯方向导数滤波所得结果。沿着方向的分量可以用下式计算：
（3）
用表示在矩阵上的零交叉点。零交叉监测目的是寻找在矩阵中，由正到负或由负到正穿越零点的位置，也就是符号发生变化的位置。零交叉监测公式可以如下表示：
（4）
检测结果如图4（a）所示。在实际应用中，常常发生零交叉点出现在两个像素点之间的情况，此时本文选择绝对值较小的点的位置作为零交叉点。
2. 3 二阶高斯导数非极大值抑制
由Hessian矩阵的特征值可知装饰线的方向，可以采用非极大值抑制的方法在上定位高斯二阶导数的方向极大值。由其极大值可以定位装饰线的中心位置。在非极大值抑制的过程中，本文并未将方向量化为圆周上的4或者8个方向，而是使用了方向的原值。具体计算公式如下：
（5）
其中，是的8连通邻域，并且角度便宜不超过；。非最大化抑制输出的结果显示在图4 （b）中。
2. 4 装饰线脊线提取
在4（b）中，非最大化抑制不仅将装饰线定位出来，还在边缘位置附近产生了极值点。可对进行验证来获取更准确的装饰线定位。根据前述原理，本文采用一阶零交叉与二阶极值点共同作用生成装饰线：
（6）
在检测过程中，如果与之间偏移不超过1个像素，这种误差是可以接受的。
2.5 装饰线与边缘融合
卡通图像中存在两种线条：装饰线与边缘。卡通图像中的边缘由Canny边缘检测算法[7]可以很容易获取。装饰线一般临近于两条平行的边缘，基于此项准则，采用洪水填充（flood filling）即可填补边界与装饰线中心的空白区域。当边缘不连续时，可以采用距离装饰线中心距离等于平均距离的点实现链接，平均距离则为平行于装饰的边缘心的点到装饰线的距离均值。这样即获得了卡通图像中的线条图线，如图5所示。
在图5中，宽度较大的线条为装饰线，而单像素线条为检测到的边缘。
3 实验结果及评价
本文以几类著名的卡通图像为例对本文所提出的算法进行了测试，包括辛普森一家（the Simpsons）、喜羊羊与灰太狼以及圣斗士星矢（Saint Seiya），并将所提出的方法与该领域最具代表性的Sykora 和Zhang的算法进行了对比，如图6所示。
在本试验中，假定装饰线不应该超过12个像素宽；装饰线及邻近区域均标记为黑色；在求解导数阶段，。经过对比发现，Sykora的方法经常丢失对比度较低的边缘，并将所有的边缘都检测为带有一定位置偏移的装饰线；Zhang的方法效果比 Sykora的方法略好，但是当装饰线宽度较小时，经常将其检测为边缘。本文所提出的方法将装饰线与边缘清晰地区分开，在三个算法中效果最优。
4 结束语
本文研究了卡通图像中线条的分类，讨论了装饰线与边缘在一阶、二阶高斯导数滤波响应的不同特性，提出了新的针对卡通图像的线条提取算法，并对几种有代表性的线条提取算法在经典卡通图像上进行了测试。测试结果表明，本文所提出算法具有更佳的视觉效果与更清晰区分轮廓线与边缘的能力。
[1] ZHANG Songhai， CHEN Tao， ZHANG Yifei， et al. Vectorizing Cartoon animations[J]. IEEE Transactions on Visualization and Computer Graphics， 2009 15（4）.
[2] STEGER C. An unbiased detector of curvilinear structures[J]. IEEE Trans. Pattern Analysis and Machine Intelligence， 1998， 20（2）：113-125.
[3] SYKORA S， BURI？NEK J， Z？RA J. Segmentation of black-and-white Cartoons[C]//Proceedings of the 19th Spring Conference on Computer Graphics， 2003： 223-230
[4] SYKORA D， BURI？NEK J， Z？RA J. Sketching Cartoons by example[C]//Proc. Second Eurographics Workshop Sketch-Based Interfaces and Modeling， 2005：27-34.
[5] YANG Ping， WANG GuoZhao. Unbiased curvilinear structure extraction for cartoon images[C]//Eighth International Symposium on Voronoi Diagrams in Science and Engineering， 2011：220-227.
[6] HUANG Mengcheng， YANG Meng， LIU Fang， et al. Stroke extraction in cartoon images using edge-enhanced isotropic nonlinear filter[C]// Proceedings of the 9th ACM SIGGRAPH Conference on Virtual-Reality Continuum and its Applications in Industry， 2010.
[7] CANNY J. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1986，8（6）： 679-698.
参考文献：
[1]ZHANG Songhai， CHEN Tao， ZHANG Yifei， et al. Vectorizing Cartoon animations[J]. IEEE Transactions on Visualization and Computer Graphics， 2009，15（4）.
[2]STEGER C. An unbiased detector of curvilinear structures[J]. IEEE Trans. Pattern Analysis and Machine Intelligence， 1998， 20（2）：113-125.
[3]SYKORA D， BURINEK J， ZRA J. Segmentation of black-and-white Cartoons[C]//Proceedings of the 19th Spring Conference on Computer Graphics， 2003： 223-230.
[4]SYKORA D， BURINEK J， ZRA J. Sketching Cartoons by example[C]//Proc. Second Eurographics Workshop Sketch-Based Interfaces and Modeling， 2005：27-34.
[5]YANG Ping， WANG Guozhao. Unbiased curvilinear structure extraction for cartoon images[C]//Eighth International Symposium on Voronoi Diagrams in Science and Engineering， 2011：220-227.
[6]HUANG Mengcheng， YANG Meng， LIU Fang， et al. Stroke extraction in cartoon images using edge-enhanced isotropic nonlinear filter[C]// Proceedings of the 9th ACM SIGGRAPH Conference on Virtual-Reality Continuum and its Applications in Industry， 2010.
[7]CANNY J. A computational approach to edge detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1986，8（6）： 679-698.