（信号与信息处理专业论文）数字乐谱中乐符库系统研究和实现.pdf

摘要 摘要 数字乐谱中乐符库系统研究和实现 学生姓名：黄秋华导师姓名：赵力教授 东南大学信息科学与工程院系 数字化技术在当今世界无处不在，音乐数字化已经是非常流行的技术，乐谱数字化便是其中的 技术之一。在乐谱数字化系统中，一种存储数据量小、美观的乐符库是其中很重要的一个组成部分， 本论文正是基于此研究和实现数字乐谱中的乐符库系统。 本论文首先分析介绍了当前的点阵、向量、曲线字库三种字库技术，以及几种图像矢量化算法， 最后采用曲线字库和基丁：分割优先的图像欠量化算法作为数字乐谱中乐符库系统的字库和构造字 库方法。然后选取间接提取特征点算法作为本论文采用的特征点提取方法，实验结果验证该算法在 增人步长来优化特征点的同时，会错误地删除一些需要保留的一些特征点，本论文对此提出一种改 进：在不增加步长的条件下，利用特征点密集区相邻特征点之间的性质来优化特征点。最后分析了 由乐符点阵字库自动生成曲线字库流程中的轮廓提取、特征点提取、拟合线段类型判断、最小二乘 法求三次b e z i e r 曲线控制点等主要过程。 系统基于q tg u i 库开发出点阵乐符字库的生成器、参考中文字库存储格式存储乐符曲线字库 的数据、基于q tg u i 库设计和实现乐符显示接口，主要有乐符轮廓绘制、区域填充、乐符字形缩 放。在区域填充算法方面，提出一种参考上一扫描行并根据图像轮廓的特征来进行区域填充的方法。 本论文研究和实现的一整套从构造点阵乐符字库到自动生成乐符曲线字库和乐符显示接口。 关键词：曲线字库：图像矢量化；特征点；区域填充；三次b e z i e r 曲线；曲线拟合；q tg u i a b s t r a c t a bs t r a c t r e s e a r c ha n d i m p l e m e n t a t i o no fn o t ec u r v i l i n e a rf o n ts y s t e mi n d i g i t a lm u s i cb o o k b yh u a n gq i u h u a s u p e r v i s e db yp r o f e s s o rz h a o l i d e p a r t m e n to fr a d i oe n g i n e e r i n g s o u t h e a s tu n i v e r s i t y n o w a d a y s ，d i g i t a lt e c h n o l o g yc a nb es e e ni nm o s td o m a i n s ，a n dm u s i cd i g i t a l i z a t i o ni s v e r yp o p u l a r , i n c l u d i n gm u s i cb o o kd i g i t a l i z a t i o n h o wt oc r e a to n ek i n do fn o t ef o n tw h i c h s t o r a g ed a t ai ss m a l la n dc a nb ed i s p l a y e db e a u t i f u l l yi st h ek e yp o i n tt om u s i cb o o k d i g i t a l i z a t i o n s ot h i sp a p e ri st or e s e a r c ha n di m p l e m e n tt h i sk i n do fn o t ef o n t t h ep a p e ra n a l y s e st h r e ek i n d so fp o p u l a rf o n t , r a s t e rf o n t ，v e c t o rf o n ta n dc u r v i l i n e a r f o n t ，a n ds o m ek i n d so fi m a g ev e c t o r i z a t i o na l g o r i t h m a n ds e l e c tc u r v i l i n e a rf o n tt ob et h e f o n to fd i g i t a lm u s i cb o o k ，a n ds e l e c to n ek i n do fi m a g ev e c t o r i z a t i o na l g o r i t h mb a s e do n d i v i s i o nf i r s tt oe r e a tt h i sf o n t s e l e c to n ek i n do ff e a t u r ep o i n tf i n d i n ga l g o r i t h mt ou s e di n t h ep r o c e s s i n go fc r e a t i n gc u r v i l i n e a rf o n t ，a n dr a i s eb e t t e r m e n tt ot h i sa l g o r i t h m a n dt h e r e s u l ti sc o r r e c t a tl a s t ，a n a l y s em o s tp r o c e s si nc r e a t i n gn o t ec u r v i l i n e a rf o n t s u c h 晒g e t t i n g t h eo u t l i n eo fn o t e ，f e a t u r ep o t i n sf i n d i n g , j u d g eo n el i n eo ro n ec u b i cb e z i e rc u r v es h o u l db e u s e db e t w e e nf e a t u r ep o i n ta n di t sn e a rf e a t u r ep o i n t ，c o m p u t e rt w oc o n t r o lp o i n t so fc u b i c b e z i e rc u r v e i m p l e m e n t a t i o no fn o t er a s t e rf o n t e rc r e a t e rb a s e do nq tg u il i b r a r ya n dt h em e m o r y f o r m a to fn o t ec u r v i l i n e a rf o n t a n di m p l e m e n t a t i o no fn o t ed i s p l a yi n t e r f a c eb a s eo nq tg u i l i b r a r y , a n dr a i s eo n ek i n do fn e w a r e a - f i l l i n ga l g o r i t h m ：r e s u m p t i v e l y , t h i sp a p e r r e s e a r c h e sa n di m p l e m e n t st h e p r o c e s so fc r e a t i n gn t o e c u r v i l i n e a rf o n tf r o mr a s t e rf o n ta n dt h en o t ed i s p l a yi n t e r f a c e k e y w o r d s ：c u r v i l i n e a rf o n t ；i m a g ev e c t o r i z a t i o n ；f e a t u r ep o i n t ；a r e a f i l l i n g ；c u b i cb e z i e r c u r v e ；q tg u i i l 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签名：盔整日期： 丝! 军：三：1 2 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名；越导师签名： 1 的变化 次数； 条件3 ：s 【l 】【2 】xs 【2 】【l 】s 2 】【3 】= o 或t ( s 1 】 2 】) 1 ； 条件4 ：s 【l 】【2 】xs 【2 】 1 】s 3 】【2 】= o 或t ( s 2 】【l 】) 1 。 如果待判断的点同时满足上述4 个条件，则在目标像素集中将此点删除，否则保留此点。按照 上述法则遍历图像所有的点，一次遍历完成后再重复遍历图像所有点，直至遍历图像所有点时，没 有可被删除的点，则细化完成。 总的来说，基于细化的方法是采用各种手段逐层削去图形的外边界像素点，直至图形的像素宽 度减少剑一个像素，但同是保存能够表征图形的特征，然后使用像素跟踪的办法结合各个图形的判 别函数将图形转换为矢量格式。这个方法的优点是可以很好的保持图形几何属性质量；缺点是遍历 像素点比较费时，不能直接提取图形的线宽信息等。 2 2 2 基于轮廓线的矢量化算法 在基于非细化的矢量化算法中，基于轮廓线9 l 1 0 l ( c o n t o u rb a s e d ) 的方法在早期很流行，图像的轮 廓特征也可以表达图像的有用信息。轮廓匹配法就是利用图像轮廓进行识别处理的方法，它的基本 步骤是： ( 1 ) 抽取图像轮廓并进行矢量化； ( 2 ) 匹配轮廓对，提取骨架； ( 3 ) 搜索轮廓对，判别交叉点，确定骨架的拓扑关系，重建图形。 识别的过程如图2 - 4 所示： 9 东南大学硕士学位论文 图2 _ 4 轮廓匹配法示意图 轮廓匹配法处理的对象是单像素宽的轮廓，其矢量化也采用细化骨架的矢量化处理类似的方 法。相比之下，轮廓比细化后的骨架所包含的信息要更丰富些。但轮廓线上的噪声比骨架上的火， 其特征提取和分析相对困难些。 总的来说，基于轮廓线的方法是在提取出图形轮廓的基础上匹配各个轮廓对，用每个轮廓对的 中点来代替图形的中心线。这种方法的优点是处理速度快、可以保留图形的线宽信息；缺点是图形 容易分段、对噪声敏感、识别准确率不高。 2 2 0 基于h o u i g h 变换的矢量化算法 h o u g h 变换算法】是一种实现直线段特征求取的有效算法，其基本思路是，将直角坐标系中的 点( x ，y ) ，变换成极坐标系上的点( ，秒) 。然后利用“直角坐标系中同一条直线上的所有点( 即共线点) 在，- 一目平面上表现为同一个点”这一特征，来进行直线的判断。对于直角坐标系中的直线 y = ，舭+ b ，用离散的极坐标可表示为： = 五c o s q + 乃s i n 包 ( 2 1 ) 考虑x - y 平面的某特定的点( 五，y 。) ，通过该点的直线可以有很多条，它们都满足等式( 1 ) ，其中 玉，乃为常量，在，一p 平面上的表现为一条正弦型曲线墨，如图2 7 所示。对于一组x - y 平面上 的共线点，如图2 - 6 所示，因为它们共享一条直线的参数，所以其对应在厂一口平面上的正弦型曲线 族( 墨，是，墨，墨) 将交于同一个点( ，o o ) ，如图2 - 7 所示。 i ： 一 图2 - 5 过一点的若干直线 1 0 x 第- 二章图像矢量化 图2 - 6 直线的离散点表示 图2 7 共线点在，一目平面上交于一点 为了判断某一点集是否为直线段，可将r - 口平面量化成若干小格。根据每个已知的( x ，y ) 点代 入口后的量化值后算出r ，所得( r 秒) 值落在某一小格内，将该小格的计数器加l 。当全部( x ，y ) 点 变换后，对小格进行检查，计数值较大的小格对应共线点，这一点( r ，口) 即为所求的直线段的特征 量。 对于基于h o u g h 变换的矢量化算法，其基本步骤为： ( 1 ) 获得需要矢量化的图像； ( 2 ) 利用h o u g h 变换求得图像中直线段的点的特征； ( 3 ) 在点集中处，对具有直线段特征的点做标记； ( 4 ) 将点集中做标记的点，用直线段矢量化； ( 5 ) 将点集中未做标记的点，用曲线进行矢量化。 h o u g h 变换的实质是将图像空间的具有一定关系的像素进行聚类，寻找能把这些像素用某一解 析表达式联系起来的参数空间累积对应点。它的优点是抗噪声性能强，易于并行处理；缺点是运算 量大，计算十分耗时，有时会检测到虚假曲线。 2 2 4 正交方向搜索法( o z z ) d o f f 等人提出了正交方向搜索法( o z z ) 0 2 】，它根据水平线、垂直线和斜线等不同的线型设计了 不同的搜索路线和搜索条件，通过搜索步长的变换来判断是否经过了交叉区域。其基本思想是：沿 水平方向扫描图像，当遇到目标图形区域的边界时，扫描方向作正交变换，并记录下目标像素之间 的水平和垂直扫描线的中点，若扫描线长度大于阈值则扫描结束。利用所记录的中点就可以构成矢 量图形。正交方向搜索法( o z z ) 搜索过程如图2 8 所示： 厂 东南大学硕士学位论文 1 未遇到目标像素点，继续 f 一点 二、一一一一一 索长度超过 图2 8o z z 搜索法示意图 该算法首先对整张图进行搜索并提取出欠量段，然后分析提取出的矢量段，最后重建图形。该 算法的优点是不经细化和中间变换，将搜索范围集中于目标像素区域，从单像素的判别转为对区域 的搜索；因为搜索的频率降低了，从而有利于避开图线缺陷，且大大加快了图线提取速度。但此方 法不适合图形的细线和细微结构的识别处理，特别对线条交义区域的判断算法复杂，需频繁更改搜 索步长。在搜索过程中需要设定不容易确定的经验阈值，并且对图线轮廓质量要求较高。 2 2 5 基于游程编码的矢量化算法 基丁游程编码( r u nl e n g t he n c o d i n g ) 1 3 】【1 4 】的方法的过程是先对图像进行处理，形成域的表示及其 邻接图，再在后续矢量化处理过程中，以域结构作为处理的基本单元，提取图像所描述图形的拓扑 信息与几何信息，实现图像信息到矢量图形信息的转换。 此类算法由于是以域结构为基本处理单元，较之以像素为处理单元的算法减少了大量数据，抗 干扰性明显增强，而且具有整体性、关联性，为从宏观上把握整个图像的拓扑结构提供了便利。由 于该方法充分表达了图形的结构，因此可以更有效的进行线段提取、信息保存，同时也比较容易实 现。但是在游码图形显示的过程中，由于不能精确的对交叉点进行定位，所以容易产生噪音和引起 交叉区域的变形。同时，由于在光栅图的基础上构建游码图是十分费时的，并且游码方向的改变容 易造成不准确的交叉点，所以这种方法不适用含曲线太多的工程图纸的矢量化。 图2 - 9 基于游程编码算法流程图 2 2 6 图像矢量化算法小结 上面儿小节分析了几类基本的图像矢量化的算法，总结这些矢量化算法【5 】，它们都有一个共同 特点。即这些欠量化算法都是把从栅格图像剑矢量图像的转换分成了两个步骤。首先，输入的栅格 图像被转换为一种初步的矢量表示，例如细化算法中的骨架线，轮廓匹配的中轴线等，主要是以点 链的形式表示：第二个步骤，将初步的矢量格式分析和重构，得到图像的矢量对象，包括直线、圆 弧等。其过程如图2 1 l 所示。 这种类型的图像矢量化算法成功的将对像素的跟踪和图形对象的识别分于矢量化时使用了点 链的表达方式，并且其中一些算法矢量化时没有一个主这些造成了图像矢量化时在交叉点处的变形 以及对相交处点链的处理困难能处理相邻接的图形。针对这些不足，一种面向图形对象的直接矢量 1 2 第二章图像矢量化 化算法了出来，它以图形对象整体作为识别对象，根据图形整体特征进行跟踪。对于面积较大图形 识别较好，但对于面积较小、过于狭窄的图形无法识别。 从以上的分析我们可以看出，现有的矢量化算法均存在一定的局限性。化应用而言，仍需先分 析待矢量化图形的特征，然后再选取合适的矢量化矢量化。由于图像的复杂性，图像矢量化技术也 在不断发展，并且仍有广空间。 输入点阵图 j f 步骤1 ：提取骨架或中轴线 上 得到初步的矢量表示 上 i 步骤2 ：基于矢量的图形对象 上 得到矢量化图形 图2 1 0 图像矢量化的基本步骤 2 3 图像矢量化在由点阵字库生成曲线字库中的运用 在绪论中提到，点阵字库和曲线字库其实质就是对数据的表达形式的区别：点阵字库和点阵图 像一样存储各个像素值，曲线字库存储直线和曲线等几何图元。因此从点阵字库自动生成曲线字库 其实质也是图像的矢量化过程。本论文采用的是基于分割优先的图像矢量化，下面简单介绍下基于 分割优先的图像矢量化过程【l 引。 分割优先的方法先抽取基元之间的分界点，然后根据分界点确定拟合曲线的参数进行拟合。分 界点是人类认知形状的重要内容，可以用来描述、识别和匹配形状。经过多年的研究，已经提出多 种分界点检测算法： 1 曲率计算，根据曲率( 夹角) 大小来提取分界点，计算量相对较小，但抗噪性差。 2 小波变换，基于小波变换检测角点，抗干扰能力强，但计算较为复杂。 3 模糊推理，根据人对局部图形特征的认识，用模糊推理来检测角点。 4 优化方法，基于遗传算法来选择分界点进行曲线拟合，即根据拟合基元的特征确定一组最 佳分界点，使得拟合误差和点压缩率都满足一定的条件。这种方法的缺点是不适应用于长 的曲线且计算复杂。 一般情况下，单独使用以上的某一种方法很难达到很好的矢量化效果，因此通常都是把两种或 两种以上的方法结合起来使用，提出了一种基于预选关键点的遗传算法，即先利用曲率提取出一部分 点作为初始分界点，然后再利用遗传算法在这些初始点中进行最终分界点的选取。 分割优先的矢量化方法其过程可以用下图来表示： 1 3 东南大学硕士学位论文 _ 。 值边缘提取 位 图 图2 1 1 分割优先矢量化方法的流程 该方法也主要分三个步骤进行：首先对二值化后的光栅图像进行边缘跟踪得到图像轮廓的点序 列表示，然后提取出图像轮廓的分界点。最后利用分界点计算出拟合曲线的参数的剑矢量曲线。但 是目前该方法还存在的问题是： ( 1 ) 用作拟合基元的代数曲线形式比较复杂，给算法的设计带来难度，并且计算量很大。用直线 和圆弧进行迭代拟合，每次迭代计算误差时需要对圆弧和直线的拟合误差各进行一次计算，大人增 加了计算量。义如用三次b 样条曲线计算一个点的坐标需要进行一次立方运算、一次平方运算及三 次矩阵运算，在计算拟合误差时计算量非常大。 ( 2 ) 分界点的提取没有考虑到拟合的误差或计算量太大。在上面几种分界点提取算法中，前3 种 方法只考虑到轮廓某一方面的特征，因此通过这些分界点对整体曲线进行拟合时很难达到要求的精 度。只有优化算法把误差作为分界点选取的条件，因此能达到较高的精度。但该方法往往需要进行 多次迭代，且每次迭代需要对整体误差进行一次计算，冈此计算量太大，算法效率不高。 构造曲线字库的最大目地就是减少字库存储空间和提高字形缩放的美观度，冈此我们需要很好 的提取字形的轮廓，后进行矢量化。由于曲线字库最后片j 直线和曲线两种几何图元去拟合字形边缘， 为此我们得首先确定那些轮廓段用直线，哪些轮廓段用曲线，所以我们首先得对字形轮廓进行分段， 为此本论文中采用的是基于分割优先的矢量算法。对于上面提到的关于基于分割优先矢量算法的拟 合误筹大、计算量人、算法效率不高等缺点，对于曲线字库的生成本身就不需要实时处理，所以计 算量大、算法效率不高对于生成曲线字库来说不是大问题。对于拟合误差，其关键在于分段点的提 取，也即特征点提取的准确性以及曲线拟合的准确性。关于轮廓特征点的提取，现在有很多算法可 用，如经典的d o u g l a s - - p e u c k e r 法及其改进算法、基于曲率的特征点提取基于多边形的提取等。在 曲线拟合方面，现代计算机图形学的发展使得轮廓的曲线拟合精确度越米越高，基于数学方程的多 项式曲线、b e z i e r 曲线、b 样条曲线在轮廓拟合方面的运用已经非常广泛，并且对于b e z i e r 曲线、 直线的绘制算法都有先进的改进算法。因此，对于曲线字库的构造，运用多种算法的综合能够使得 拟合精确度足够高。 2 4 本章小结 本章首先讨论了图像与矢量图形的区别及各自优缺点，然后介绍了当今流行的几种图像矢量算 法，如基于细化的方法、基于轮廓线的方法、基于h o u g h 变换的方法、正交方向搜索法( o z z ) 、基 于网格模式的方法、基于游码的方法和基于稀疏像素的方法等，并分析了各自的优缺点。最后说明 了由点阵字库生成曲线字库的过程实质就是图像的矢量化过程，并采用基于分割优先的矢量化算法 来生成乐符曲线字库。 1 4 第三章轮廓特征点提取算法 3 1 引言 第三章轮廓特征点提取算法 本系统由点阵乐符字库自动生成曲线乐符字库的过程是基于分割优先的矢量化过程，因此分界 点的提取是重要的一个环节。轮廓的分界点也称之为轮廓特征点。图形轮廓的特征点提取是模式识 别及计算机视觉中的一个重要内容。轮廓的大量信息都集中在特征点上，所谓特征点是指能够代表 曲线特征的一些点，它们勾画出图形的人致轮廓，并且数量只占轮廓点序列的几十分之一，有利于 传输及后续的处理。因此，在对图形进行分析和描述以前，通常先进行特征点的检测。轮廓特征点 是对图形轮廓的分段，那么相邻两段的线段特征( 线段类型、走向) 不同，若相同，那么相邻两线段 可合并，用同一属性的线段拟合即可。轮廓特征点包括角点、切点、和拐点，其中角点是目标轮廓 线上曲率超过一定阈值的局部极大值点，切点是圆弧和直线的平滑过渡点，拐点是凹圆弧和凸圆弧 的平滑过渡点。由丁它们对目标形状起着决定作用，一r 口找到了目标的这些轮廓特征点也就大致掌 握了目标的形状。因此在形状表征、形状分析、图像匹配及目标识别中，角点、切点及拐点是最基 本的表征目标形状的特征基元。 常见的检测特征点的方法有多边形逼近法和角点检测测z z 】。多边形逼近法通常按照一定原则向 两个最初端点之间的曲线段中不断加入分割点以逼近原曲线，这些分割点就是特征点。每一步考察 曲线段中各点到当前两端点连成的弦的距离，选择距离最大且距离值大于阈值的点作为特征点，并 将该点作为新的端点，直到没有新的点产生。角点检测法通常计算轮廓上每一点的曲率并找出曲率 的局部最大值点作为特征点。对丁如何计算曲率，人们进行了很多研究，如利用某点的前后两点间 连线长度与该点到该连线的距离比作为近似曲率、利用b 样条曲线进行拟合获得曲率、利用某点前 后几点的几何中心与该点所构成的向量计算曲率角、以利用轮廓内面积与轮廓外面积在以轮廓点为 圆心的圆中所【与百分比估计曲率等等。还有d o u g l a s 等人1 9 7 3 年提出的d o u g l a s p e u c k e r 方法，简 称d p 方法，以及针对d o u g l a s - p e u c k e r 方法的几种改进方法。还有胡鹏等2 0 0 1 年提出的垂足法和 光栏法、l i z h i l i n 等1 9 9 2 年提出的基于自然规律的宏观综合法、v i s v a l i n g a m 等1 9 9 5 年提出的最小 面积重复删除法、黄培之1 9 9 5 年提出的顾及精度的较长距离边端点寻求法掣1 6 j 。 3 2d o u g l a s p e u c k e r 及其改进算法 1 9 7 3 年，d o u g l a s 和p e u c k e r 提出一种用于二维曲线形状化简的方法【1 7 】。该方法是对垂距限值 法的一种改进算法。道格拉斯算法被公认为线状要素化简的经典算法，并且3 0 多年来，道格拉斯 法己成为计算机制图及g i s 领域内对线状要素进行自动综合的最主要方法之一。它的特点是从形状 复杂的曲线点列中，通过相对简单的全局性递归运算，能选出那些反映曲线总体及局部形态的主要 特征点，它具有严格的保凹凸性，能保持曲线形状特征、减少线性位移量、保持分维值的优势。 d o u g l a s p e u c k e r 法对于简单的线状要素能很好的将其进行简化。 ( 1 ) d o u g l a s p e u c k e r 算法基本思想 d o u g l a s p e u c k e r 法的基本思想思想是由远到近，找出与矢量两端点连线的垂足最大的顶点判断 其是否满足要求。如下图所示 分裂 锚 漂浮点b 锚点 量大 漂浮点b ( a ) 第一步到第二步示意图c o ) 第四步回到第二步示意图，上次的c 现为b 1 5 东南大学硕士学位论文 寒 弋r | j 锚点a 二吴吣 ( c ) d o ，其大小为如图l 所示的阴影部分 的面积。 对于单边弧和双边弧的情况，分别作讨论。 ( 1 ) 单边弧最小误差逼近特征点 单边弧是指所有的点都在弦的一侧。设轮廓中的一个子轮廓的起点为p o ，终点为肌，用p o p 表示该子轮廓，p o p s 用来逼近子轮廓弧风肌的逼近误差，由其定义可表示为： = 彳= 靴n - i 而k ( 3 2 ) 式中红，而表示子轮廓肌任意点忍到风n 的有向距离( 按照弦的走向，在弦的左侧为正，在弦 的右侧为负) ，其值为： 1 8 多 一 第三章轮廓特征点提取算法 il：=pop：xpopi 凡朋 p o p i 为线段b 一。忍的长度，其值为： ：辰蒜 ( 3 3 ) ( 3 4 ) 如有下图所示情况，在风，肌中插入一点见，用折线段岛依，见n 重新去逼近肌 pk 、。 产、z 以，而赢、 - e p o h p f 1 9 ( 3 6 ) ( 3 7 ) 东南大学硕十学位论文 对于增加逼近点后的逼近误差分析： 踟= 一互1i 面一p o p kl = e p o p 一批而i f p - - - 赢i ( 3 8 ) 要使得 踟最小，而气 是固定的，则必须使得吾i 吸而i i p o p n 局t ，且i 瓦瓦i 为一固定 值，则只要l 吸。一p o p ni 最大，就可使得逼近误差最小。即我们要找的最佳逼近点n 为该点到弦的距离 最大： 魄一p o p n - - i 嬲( h i 赢i ) 为此，我们将提取见为特征点，p k 为p o p s 的最小逼近误差特征点。 ( 2 ) 双边弧最小误差逼近特征点 当轮廓曲线在弦的两侧时称为双边弧，此时存在分属丁弦的两边的最小逼近误筹特特征点见， 和p k 。f p kr h j 图3 5 双边弧情况 要使阴影面积也即逼近误差最小，必须满足以下条件： 仅，而2 爨( 五, v f f ) l = ln i , p o p t 。t ，7 ，助踟 。2 、 _ 而2 矧m 五l n ，( 勺，赢) ( 3 9 ) ( 3 1 0 ) 沿着弦的方向，n ，为后特征点，见。，为前特征点。因为2 个特征点位于弦的两侧，必然有轮廓弦 在一处或多处穿过弦，定义这些穿过点为弦上点。弧与弦的交点将弧分为两个两个单弧轮廓，我们 可按照匕述单弧情况，进行最小误差逼近特征点的提取。 通过以上对多边形逼近提取特征点算法的研究，用一组多边形去逼近一条曲线，其基本思想就 是在规定特征点提取数量的前提下，提取特征点后，该多边形能够最精确地去逼近该曲线，使得逼 近误差最小。 3 4 基于曲率的特征点提取算法 根据曲率的走势用图来表示下角点、切点和拐点。首先，定义在欧氏空间，一条直线的曲率为 零，圆弧的曲率是非零常数，凹圆弧和凸圆弧的曲率符号相反。设凸圆弧的曲率为止值，凹圆弧的 曲率为负值，用l 表示正曲率符号，1 表示负曲率符号，0 表示曲率为零。对于以下四种情况分析： 第三章轮廓特征点提取算法 l c c l r p ( a ) i l l - p l 2 c l c i r p c 2 c l p c 2 图3 _ 6 曲线的曲率符号 对于( a ) ，p 点是直线l 和圆弧c 的连接处，在曲率坐标上，点p 是0 ，l 阶跃函数，点p 为切 点；对于( b ) ，p 点是两凹凸圆弧c l 、c 2 的连接处，在曲率坐标上，点p 是1 ，l 阶跃函数，点p 为拐点；对于( c ) ，p 点是两直线l l 、l 2 的连接处，在曲率坐标上，除了点p 曲率为1 其余点的曲 率全为0 ，点p 为角点；对于( d ) ，p 点是两凸圆弧c l ，c 2 的连接处，在曲率坐标上，所有点的曲 率都为l ，点p 为普通点，不为特征点。 曲率表现轮廓的弯曲程度，曲率本身的计算量非常大，因此有很多近似的的方法来估算曲率， 这里介绍两种算法：基于曲率角的特征点提取算法和基于面积的特征点提取算法。 3 4 1 基于曲率角的特征点提取算法 基于曲率角的特征点提取算法【i9 】对于角点和拐点、切点的提取方法不一样，下面介绍该方法。 ( 1 ) 角点的提取 从上面的几种情况分析，是以角点附近的弯曲程度是附近点最大，也就是说角点的曲率是附近 点最大的。对于离散点序列中任意一点p ( i ) ，我们考察其前后半径为r 的个点构成的支撑区域： s ( f ) = p ( f ) = x ( _ ，) ，y ( j ) l j = i - r ，i - r + l ，i ，i + r - 1 ，f + 尺) ( 3 1 1 ) 定义点p ( i ) 前后两个区域中心点为p ，( f ) p 6 ( f ) ，其分别为： 一il p ( 泸【石) ，y ，( f ) 】= 【x ( j ) r ，y ( j ) r j = i ry = i r i + r i + r p b ( f ) = 【矿( 耽y 6 ( 例= 【x ( j ) r ，y ( j ) r 爿+ lj = l + l 两中心点p ，( 耽p 6 ( f ) 与点p ( f ) 构成的向量角分别为： 目，( f ) = a r c t a n ( y ( i ) 一y ，( f ) ) ( 石( f ) 一z ( f ) ) 】 2 l ( 3 1 2 ) ( 3 1 3 ) ( 3 1 4 ) 八 东南大学硕上学位论文 0 b ( f ) = a r c t a n ( y ( i ) 一y b ( f ) ) ( 工( f ) 一工6 ( f ) ) 】 则点p ( i ) 的曲率角秒“) 定义为： 如下图所示： o ( i ) = 秒，( f ) 一0 6 ( f ) p p ( i r 1 ( 3 1 5 ) ( 3 1 6 ) 图3 - 7 曲率角计算不慈图 可以看到点p ( f ) 的曲率角秒( f ) 越大，其曲率也越大，曲率角和曲率是成正比的。 为了确定一个点是否是角点，可以计算该点的曲率角的大小，得出点的曲率角后，需要和一参 考值比较以确定该店是否可以作为角点。设定一阈值t ，若ip ( f ) i t ，则选该点为候选角点。为了 防止过于密集的出现角点，通过非极小抑制可筛选出真正的角点，即只有当下式成立时，候选角点 p ( f ) 才能称为真正的角点，即： i o ( i ) | - m a x i p ( ) i i j = i - r ，f r + 1 ，f ，f + r 一1 ，f + 尺( 3 1 7 ) ( 2 ) 切点、拐点的提取 在欧氏空间，一条直线的曲率为零，圆弧的曲率是非零常数，凹圆弧和凸圆弧的曲率符号相反。 为确定轮廓点的曲率符号，可以假设按顺时针方向进行边缘跟踪来提取轮廓点，这样，根据曲率角 o ( i ) 的大小米确定该点曲率的符号。为此设一闽值互，该点的曲率符号孝( f ) 为： 1 0 i o ( i ) 阵石 f ( f ) = lp ( f ) 石 ( 3 1 8 ) 【一1 口( f ) 正时，才将作为候选角点，若将轮廓点近似看作是两直线段的交点， 则口即为这两直线段的夹角。 圆盘半径r 构成了测量角度的支撑区域，它的选取主要考虑数字化、噪声及测量角度的精度。 为了减小噪声的影响，通常的途径是将支撑区域取得较大，同时进行运算量较大的曲线( 直线) 拟合。 这样就导致了算法不仅对小尺寸不能适应而且运算量也较大。此算法是利用轮廓线在圆盘中所围成 的面积，求面积是积分运算，由此可以预见此方法抗噪能力比那些仅仅利用轮廓点的提取方法要好。 、，、， ，l，l t 疋 1 2 1 2 第三章轮廓特征点提取算法 须从由式( 3 2 4 ) 得到的一系列候选角点中筛选出真正的角点。 的角点，即只有当下式成立时，候选角点才成为角点： ( ) i l 焉艮( ，) 通过非极小抑制即可筛选出真正 ( 3 2 0 3 5 本论文采用的一种的特征点提取算法 在上一小节中提到的基于曲率的两种特征点提取算法，两种算法都是直接基于轮廓点关于x ， y 二元区域直接进行曲率的估算，冈此对于曲率角的计算和区域面积的计算量都较大，因此采用一 种间接提取特征点的算法【2 1 1 ，此方法首先将轮廓点分解为一元区域，从而使得曲率的估算简化。 一条轮廓上的所有轮廓点p ( i ) ：【x ( i ) ，y ( i ) 都是关于坐标x ，y 的二维函数，且x ，y 之间并不 是函数关系，因此函数中的曲率公式不能运用于此，因此有了上一节中的两种估算方法。间接提取 特征点算法是将p ( i ) 进行分解：x ( i ) 表示p ( i ) 在水平方向上的变化，y ( i ) 表示p ( i ) 在乖直方向上的变 化，冈此我们可以得到x ( i ) 和y ( i ) 两条关于i 的线段，现在需要各自分析这两条线段提取特征点， 并加以综合分析，从而提取p ( i ) 的特征点。x ( i ) 和y ( i ) 都是关丁i 的一元离散函数，因此求曲率的估 算较简单。 对于离散函数x _ x ( i ) ，i = 0 ，l ，n ，我们用二阶导数来近似代替曲率k ，则有： 1 k = 音 x q j 1 1 ) 一2 x ( i ) + x ( i + ) 】 ( 3 2 7 ) 厅 式中h 为考虑到数字化及噪声影响所取的步长。进一步简化我们去一数值q ： q = i k h 2 i = i x ( f j i l ) 一2 ( f ) + x ( f + ) i ( 3 2 8 ) 用q 来估算曲率k 。 求出x ( i ) 上每一个点的q 的值，选取一个闽值互。然后进行分区域分析： ( 1 ) 若在某一区间内，对所有的点都有g 巧，则该区间内不存在特征点。这时存在两种情况： 一是区间内大部分点的q 值都等于零，只有少量g 五的点可认为是噪声点，该区间对应一条存在 噪声的直线段；二是区间内大部分点的q 值不为零且小于正，该区间对应一条弯曲程度非常小的曲 线该曲线近似于直线。两种情况r 卜该区间内都不设特征点。 ( 2 ) 若在某一区间内，对所有的点都有q 正，则该区间对应一条变化程度较大的曲线。为更 好地逼近原始曲线，设定适当的步长，找出每个步长内q 值最大的点作为特征点。 在找出x ( i ) 的特征值后，按照同样的方法找出y ( i ) 的特征值，设定另外一个阈值乃，然后综合 分析以确定p ( i ) 的特征点： 在x ( i ) 和y ( i ) 都各自提取好特征点之后，可能会出现几种情况： ( 1 ) x ( j ) 为特征点、y ( j ) 也为特征点 ( 2 ) x ( j ) 为特征点、y 0 ) 不为特征点或x ( i ) 不为特征点、y ( j ) 为特征点 ( 3 ) x 0 ) 为特征点、y ( k ) 也为特征点，但是k 和j 不相等 为此需要依次分析x ( i ) 和y ( i ) 的特征点x ( j ) 和y ( k ) ： ( 1 ) 若v - k i t 2 ，x ( j ) 和y ( k ) 为p ( i ) 上的两个独立的特征点。 到此，p ( i ) 上的特征点已经提取完成。 在第四章中的实验结果表明，在参考文献 2 1 】给出的实验数据：h = 1 0 ，正- 2 ，互= 3 ，在步长选 取较小的情况下( 本论文采用的步长为8 ) 能够准确地提取额轮廓的特征点，但是在轮廓弯曲程度较 大的地方会产生较多的特征点，也即会出现特征点密集区。理论上对于轮廓弯曲程度大的区域，特 征点选取越多，用曲线拟合的时候，其拟合精度会更高。但是在拟合精度和数据压缩、曲线绘制之 间平衡还是需要对特征点密集区进行特征点优化。该算法提供了增加步长来优化特征点，在优化特 征点的时候会出现删除一些需要提取的特征点。下一章将对此算法经行室验证和分析，并且基于此 方法提出一种改进的间接提取特征点方法。 3 6 本章小结 本章介绍了特征点的概念以及特征点提取在生成乐符曲线字库中的重要性，然后分析了几种经 典的轮廓特征点提取算法，最后选取了一种间接提取特征点的算法作为本论文的方法。 2 6 第四章由乐符点阵字库自动生成曲线字库 第四章由乐符点阵字库自动生成曲线字库 4 1 乐符曲线字库自动生成的总体过程 鉴于需要开发完全自主知识产权的数字乐谱软件，我们将开发出自己的点阵字库，然后实现由 点阵字库自动生成曲线字库。首先需要有能够构造点阵乐符字库的工具，对此我们采用的o t 3 oc h 开发出能生成2 5 6 x2 5 6 点阵乐符字库的软件，将在第五章介绍。 乐符曲线字库的自动生成过程是基于分割优先的图像矢量化过程，因此首先我们得提取乐符字 形的轮廓并且进行分割。乐符轮廓的分割过程也是轮廓特征点提取的过成，特征点提取之后将乐符 字形轮廓分为各个子轮廓。而后我们需要根据一定的规则来判断分割后的各个子轮廓需要用什么类 型的几何图元米拟合，本系统中采用直线和三次b e z i e r 曲线两种几何图元。确定需要 j i 直线来拟合 后，只需要存储直线的两个端点即可。对于判断为需要用b e z i e r 曲线来拟合的子轮廓，我们不能把 两特征点中间的全部轮廓点都存储起来，也不能只存储两个端点。根据三次b e z i e r 曲线的性质，需 要四个控制点就能完全确定一条三次b e z i e r 曲线，所以除去已知的两个端点，我们需要根据已知的 轮廓点来反求出另外两个控制点。当所有的特征点利控制点都提取完之后，所生成的数据就是该乐 符能够表示该乐符轮廓的所有数据信息。 由乐符点阵字库自动生成曲线字库的主要步骤有： 第一步：构造点阵字库。这是曲线字库的数据来源。 第二步：提取点阵字库的边缘轮廓。本质上讲，乐符曲线字库就是存储乐符字形的轮廓信息， 这步已经提取了乐符字形的轮廓，但是针对轮廓中存在的特征，我们可以对该轮廓数据进行压缩， 减少乐符曲线字库的数据量。 第三步：提取边缘轮廓特征点，使边缘轮廓分段。最后表示乐符字形轮廓的图元只有直线和曲 线，所以一个完整的乐符字形可以用用一条直线或者曲线来表示。虽然一条复杂的多次b e z i e r 曲线 可以实现复杂的图形形状，但是多次的b e z i e r 曲线的复杂性，使得其在求控制点和绘制的过程中的 计算将会异常的复杂，所以一般在字形的曲线中我们只采用三次b e z i e r 曲线。特征点的提取是关系 到整个乐符曲线字库系统性能的关键。 第四步：确定相邻关键点之间拟合线段类型，确定需要用直线拟合还是片j 曲线拟合。 第五步：反求三次b e z i e r 曲线控制点。为了能使构造的曲线能够最大程度地逼近原轮廓点，就 必须找出最优的两个控制点，因为控制点完全决定着b e z i e r 曲线的形状。求控制点唯一依据就是原 轮廓点，利用最小二乘法可以由原轮廓点求出三次b e z i e r 曲线的两个控制点的最优解。 第六步：生成乐符曲线字库。 其流程图如下： 检 a 读 测 出 断 取 点 提 求 占阵 轮 一 胁 曲 线 控 点 雾蓁 征 点 阵 字 库 数 廓 点 影据 并 卜一 按 图4 - l 自动生成乐符曲线字库总流程 下面将就各个步骤经行分析研究。 东南大学硕七学位论文 4 2 点阵字库边缘轮廓提取 图像边缘是图像中灰度发生急剧变化的像素的集合，两个具有不同灰度值的相邻区域之间总存 在着边缘。图像边缘是图像最基本的特征之一，边缘检测是图像分割、目标区域识别、区域形状提 取等图像分析方法的基础，在工程应用中有着重要的地位。 图像边缘轮廓的提取主要流程如图所示： 边缘检测 轮廓跟踪 图4 - 2 图像轮廓提取流程 图像预处理主要包括对图像的去噪声处理、增强处理，本系统所采用的是自己构造的乐符点阵 图像，图像本身已经足够精确地表示乐符，所以不需要进行预处理直接进行边缘检测和轮廓提取。 4 2 1 图像边缘检测 本论文采用边缘检测算子来进行边缘检测 2 3 】【2 4 】。边缘检测算子是利用图像边缘的突变性质来检 测边缘的。主要分为两种类型：一种是以一阶导数为基础的边缘检测算子，通过计算图像的梯度值 来检测图像边缘，如：r o b e r t s 算子、s o b e l 算子、p r e w i t t 算子；一种是以二阶导数为基础的边缘检 测算子，通过寻求二阶导数中的过零点来检测边缘，如：l a p l a c i a n 算子、l o g 算子、c a n n y 算子。 4 2 1 1r o b e r t s 算子 r o b e r t s 边缘检测算子是一种利用局部差分运算来寻求检测边缘的算子。它采用两个2 x 2 模板， 如图4 3 所示。r