（计算机应用技术专业论文）高精度曲线轮廓甲骨文字形生成系统的研究与实现.pdfVIP

苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文口 论文作者签名：j 研 日 导师签名：日 期：型! 坐 期：趁应磁 高精度曲线轮廓甲骨文字形生成系统的研究与实现中文摘要 高精度曲线轮廓甲骨文字形生成系统的研究与实现 中文摘要 甲骨文是我国最珍贵的文化遗产之一，具有极其重要的文化遗产保护和历史研究 价值。随着现代科技的迅速发展，将甲骨文数字化处理可以更好的保护和继承这一传 统文化。本文根据国内外现有的相关技术，研究并实现了从甲骨文原始图片中提取出 字体，并拟合生成高精度曲线轮廓甲骨文字形，设计并实现了甲骨文字形自动生成系 统。论文的主要研究内容如下： 1 结合k 均值聚类分析和八邻域法，提出了一种基于改进的k 均值聚类图像处 理方法。该方法可以更有效地将甲骨文字体目标从原始甲骨文图片中分割出来。在甲 骨文文字目标分割出来后，根据图像平滑等处理对甲骨文文字目标进行优化，然后提 取出甲骨文原始轮廓线以及特征点信息，为下一步拟合生成曲线轮廓甲骨文字形做准 备。 2 提出了一种带自适应形状参数的三次b 样条曲线拟合方法，并将其应用于生 成曲线轮廓甲骨文字形。该方法根据带局部形状参数三次b 样条曲线的性质，首先 反求出过特征点的b 样条曲线的控制点，然后利用最小二乘法求解与离散点距离总 偏差最小的局部形状参数，最后根据控制点和形状参数进行曲线拟合生成曲线轮廓甲 骨文字形。该方法使拟合曲线精确的经过特征点，自动获取并调节形状参数，达到了 比较好的曲线拟合效果。 3 设计并实现了高精度曲线轮廓甲骨文字形自动生成系统，该系统不仅验证了 上述算法的正确性，而且大大提高了生成甲骨文字形的效率，减少了保存甲骨文字体 所占的存储空间。 关键词：甲骨文；曲线轮廓字形；图像分割：k 均值；b 样条曲线；自适应形状参数 作者：王晓丽 指导教师：马小虎 本文的研究工作受到江苏省自然科学基金项目( 项目编号：b k 2 0 0 7 0 5 0 ) 的资助。 一a b s t r a c t r e s e a r c ha n di m p l e m e n t a t i o no fh i i g h p r e c i s i o nc u r v e - o u t l i n eg e n e r a t i o ns y s t e mf o rj i a g u w e n r e s e a r c ha n d i m p l e m e n t a t i o no fh i g h - p r e c i s i o n c u r v e - o u t li n eg e n e r a t i o ns y s t e mf o rj i a g u w e n a b s t r a c t j i a g u w e ni so n eo ft h er a r e s tc u l t u r eh e r i t a g e si nc h i n a , a n di tp o s s e s s e so fm o s t i m p o r t a n t v a l u eo fc u l t u r e h e r i t a g ep r o t e c t i o n a n d h i s t o r yr e s e a r c h w i t hr a p i d d e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , i ti sm o r ea d v a n t a g e o u st op r o t e c ta n di n h e r i tt h e r a r ej i a g u w e nt h r o u g hd i g i t a lp r o c e s s i n g a c c o r d i n gt ot h er e l a t e dt e c h n o l o g ya th o m ea n d a b r o a d ，ah i g h - p r e c i s i o nc u r v e o u t l i n eg e n e r a t i o ns y s t e mf o rj i a g u w e ni sd e s i g n e da n d i m p l e m e n t e di nt h i sp a p e r t h ei m p l e m e n t e ds y s t e mc a nb eu s e dt oe x t r a c tj i a g u w e nf r o m t h es o u r c ej i a g u w e ni m a g e sa n dg e n e r a t et h eh i g h - p r e c i s i o nc u r v e - o u t l i n eo fj i a g u w e nf o n t n e m a j o rr e s e a r c hc o n t e n ti nt h i sp a p e ri sa sf o l l o w s ： 1 c o m b i n e dw i t hk - m e a n sc l u s t e ra n a l y s i sm e t h o da n dt h e e i g h tn e i g h b o r h o o d t e c h n o l o g y , am e t h o df o rj i a g u w e ni m a g ep r o c e s s i n gb a s e do nm o d i f i e dk - m e a n s c l u s t e r i n ga l g o r i t h mi sp r o p o s e d am o r ee f f e c t i v ei m a g es e g m e n tr e s u l ti so b t a i n e db yt h e m e t h o d ，a f t e ri m a g es e g m e n t ，s o m em e t h o do fi m a g ep r o c e s s i n gw i l lb eu s e df o r m o d i f y i n ga n di m p r o v i n gt h er e s u l to fi m a g es e g m e n ta n dt h eo u t l i n e so fj i a g u w e na r e o b t a i n e d a tl a s t ，t h ef e a t u r ep o i n t so nt h eo u t l i n e so fj i a g u w e nf o n t sa r ec a l c u l a t e df o r n e x tr e s e a r c hw o r k 2 am e t h o do fu n i f o r n lc u b i cb s p l i n ec u r v ef i t t i n gw i t ha d a p t i v es h a p ep a r a m e t e r si s p r o p o s e da n da p p l i e dt og e n e r a t et h ec u r v eo u t l i n eo fj i a g u w e na u t o m a t i c a l l y c o m b i n e d 、航t hc u b i cb s p l i n ew i t hl o c a ls h a p ep a r a m e t e r , t h ec o n t r o lp o i n t so f b s p l i n ew h i c ht r a n s i t t h ep r e - c a l c u l a t e df e a t u r ep o i n t si sg o tb ym a t h e m a t i c a lm e t h o d a n dt h e nt h el o c a ls h a p e p a r a m e t e r si so b t a i n e db yu s i n gt h el e a s ts q u a r em e t h o d ，w h i c hr e s u l ti nt h es m a l l e s t d i s t a n c eb e t w e e nt h eo b t a i n e df i t t i n gc u r v ea n ds o u r c eo u t l i n eo fj i a g u w e n , f i n a l l yt h e c u b i cb - s p l i n ec u r v ef i t t i n gi sp e r f o r m e db yt h ec o n t r o lp o i n t sa n ds h a p ep a r a m e t e r 1 1 1 e f i t t i n gc u r v ei si m p r o v e da u t o m a t i c a l l yb ya d j u s t i n gt h ea d a p t i v es h a p ep a r a m e t e r s ，a n d t r a n s i t st h ef e a t u r ep o i n t sa c c u r a t e l y 3 t h e1 1 i g h p r e c i s i o nc u r v e o u t l i n eg e n e r a t i o ns y s t e mf o rj i a g u w e ni s d e s i g n e da n d i m p l e m e n t e di nt h i st h e s i s t h i ss y s t e mn o to n l yv a l i d a t e st h em e t h o d sw h i c ha r ep r o p o s e d i nt h ep a p e r ，b u ta l s oe n h a n c e st h ee f f i c i e n c yo fg e n e r a t i n gc u r v e - o u t l i n eo fj i a g u w e nf o n t a u t o m a t i c a l l ya n dr e d u c i n gt h es t o r a g eo fj i a g u w e n k e yw o r d s ：j i a g n w e n ；c u r v eo u t l i n ef o n t ；i m a g es e g m e n t ；k - - m e a n s ；b s p l i n e ； a d a p t i v es h a p ep a r a m e t e r w r i t t e nb yw a n gx i a o l i s u p e r v i s e db ym ax i a o h u t h er e s e a r c ho ft h i st h e s i sh a sb e e ns p o n s o r e db yn a t u r a ls c i e n c ef o u n d a t i o no fj i a n g s u p r o v i n c eu n d e rg r a n tb k 2 0 0 7 0 5 0 1 1 目录 第一章绪论l 1 1 研究背景1 1 2 研究内容及意义2 1 2 1 本文研究内容2 1 2 2 本文研究意义4 1 3 本文组织结构4 第二章相关技术6 2 1 数字图像处理技术6 2 1 1 概述6 2 1 2 图像分割7 2 2 聚类分析方法8 2 3b 样条曲线造型技术8 2 3 1b 样条曲线的定义9 2 3 2b 样条曲线性质l0 2 4 本章小结1 1 第三章基于k 均值聚类的甲骨文图像预处理方法1 3 3 1 引言1 3 3 2 基本原理1 4 3 2 1k 均值聚类方法1 4 3 2 2 邻域法。1 4 3 2 3 膨胀。1 5 3 3 图像分割1 6 3 3 1 改进k 均值聚类图像分割算法1 6 3 3 2 图像分割结果分析。1 7 3 4 边界提取1 8 3 5 后续处理1 9 3 5 1 轮廓跟踪2 0 3 5 2 提取特征点信息。2 l 3 6 本章小结2 5 第四章基于b 样条的甲骨文曲线轮廓字形生成方法2 6 4 1 引言2 6 4 2 三次b 样条2 6 4 2 1 三次b 样条定义2 6 4 2 2 三次b 样条曲线段性质2 7 4 3 带形状参数的三次均匀b 样条2 8 4 3 1 基函数的构造与性质。2 9 4 3 2 构造带形状参数的三次b 样条曲线。3 0 4 4 反求b 样条的控制点3 0 4 5 带自适应形状参数的三次b 样条曲线拟合31 4 5 1 最d 、- - - - 乘法31 4 5 2 求解三次b 样条曲线的形状参数3l 4 5 3 曲线拟合生成字形具体算法步骤3 2 4 6 实验结果分析3 3 4 7 本章小结3 4 第五章系统设计与实现。3 5 5 1 系统功能概述3 5 5 2 系统设计3 5 5 2 1 系统模块设计3 5 5 2 2 测试流程设计3 6 5 3 系统实现3 7 5 3 1 界面模块3 7 5 3 2 预处理模块3 8 5 3 3 拟合处理模块。3 9 5 3 4 高级功能模块。3 9 5 4 实例演示4 l 5 4 1 基本功能演示。4 1 5 4 2 高级功能演示4 4 5 5 本章小结4 6 第六章总结与展望4 7 6 1 总结4 7 6 2 工作展望4 8 参考文献4 9 攻读学位期间公开发表的论文与科研项目成果5 4 致谢5 6 高精度曲线轮廓甲骨文字形生成系统的研究与实现 第一章绪论 1 1 研究背景 第一章绪论 甲骨文是我国现存最早的成系统的文字材料，也是迄今发现的最古老的象形文字 之一。它产生的时期尚属于绘画阶段，所体现的语法规则是汉语语法可追溯的最早源 头【l l 。1 9 世纪末年，甲骨文在殷代都城遗址( 河南安阳小屯) 被发现，甲骨文主要指 殷墟甲骨文，又称为“殷墟文字”、“殷契”，是中国商代后期王室用于占b 记事而刻在 龟甲和兽骨上的文字，如图1 1 、图1 2 所示。殷商灭亡周朝兴起之后，甲骨文还延 绵使用了一段时期。安阳殷墟甲骨文的发现，在海内外学术界引起了轰动。从1 9 2 8 年1 0 月起，到1 9 3 5 年6 月抗战爆发止，当时的国民政府中央研究院组织对殷墟进行 了十五次考古发掘，共出土有字的甲骨近两万五千片，可谓成绩卓著；新中国建立后， 人民政府对殷墟又组织过多次发掘，共得有字甲骨六千多片t 2 1 。 图1 - 1 刻辞卜骨图1 2 刻辞龟甲 甲骨文是中国已发现的古代文字中时代最早且体系最为完整的文字系统【3 1 。甲骨 文被学术界称为清末“四大发现”之一，同古代埃及的圣书字、西亚的丁头字一样， 以出现早、发育成熟而闻名于世：且以三千年一贯沿用至今，举世无二而饮誉全球。 甲骨文是中国文化的载体，记录了中国古代文明的痕迹，蕴藏着先人的思维思想。甲 l 第一章绪论高精度曲线轮廓甲骨文字形生成系统的研究与实现 骨文是中国古代社会生活、历史事件的真实记录，是打开中国上古时代文化宝库的钥 匙，是探索文字源流、研究文字发展规律的宝贵资料。人们对甲骨文的研究已经取得 了一定的成果，文字的考释也对其意义做出了解释。正如甲骨学史学家王宇信所说： “甲骨学研究的发展，使得这些暴睛鼓眼，洁曲警牙的商代甲骨文所记载的古代社会 奥秘逐一被人们所窥破。我们可以毫不夸大地说，谁要是想认识和了解中国古代社会 的历史和文化，谁就必须对甲骨学有一定的知识和研究。”【l 4 】但是随着时代的变迁， 这种文字符号系统已经很少被使用，如何更好的继承、保护和发展这些珍贵的文化遗 产已经成为现在对于古代文字研究的课题之一。 在甲骨文资料和研究成果的交流方面，现在很多研究学者仍然使用原始骨片或图 片上直接取字的方式进行，最常用的人工取字方法是：首先扫描或用相机获取甲骨文 原始图片；然后利用图像处理软件对甲骨文文字图像进行手工预处理操作，并获取甲 骨文轮廓字形；最后利用字体编辑工具将图形文字做矢量化处理，编码后加入甲骨文 字库。这种手工处理甲骨文的方法工作量非常大，效率低并且字形轮廓的精确度也得 不到保障。 随着现代科技的不断发展，运用计算机技术将甲骨文数字化处理可以更好的保护 处 特习。文如前将甲来 高精度曲线轮廓甲骨文字形生成系统的研究与实现 第一章绪论 描述的甲骨文字形等方面进行研究。本文着重介绍生成高精度曲线轮廓甲骨文字形过 程中的关键技术。生成甲骨文字形的研究工作主要分为两大部分，本文将前期对甲骨 文图片进行图像处理的部分称为“甲骨文图像预处理”，后期拟合生成甲骨文字形部 分称为“曲线拟合生成甲骨文字形”。 本文研究的重点内容有以下几点： ( 1 ) 研究用于对甲骨文原始图片进行图像处理的方法，提取出能够表现甲骨文原 始字形特征的信息。这个部分过程即为甲骨文图像预处理部分。 ( 2 ) 结合甲骨文图像预处理得到的数据，设计一种用b 样条曲线来描述甲骨文曲 线轮廓字形的方法。这部分内容即为曲线拟合生成甲骨文字形部分。 ( 3 ) 在以上算法研究的基础上，根据面向对象和模块化设计方法，实现甲骨文字 形自动生成系统。 本文主要研究内容的层次结构如图1 3 所示。 图1 3 主要内容的层次结构图 甲骨文图像预处理的主要方法是：首先利用中值滤波去除甲骨文图像中的部分噪 声点；然后利用改进的k 均值聚类方法对甲骨文原始图像分割，提取出原始文字目 标；最后对文字进行优化，提取出甲骨文原始字形轮廓，获取能够表现甲骨文字形轮 廓特征的信息。本文结合了邻域法和k 均值聚类方法对传统的k 均值聚类方法加以 改进。在甲骨文图像分割中，这种方法达到了比较好的实验效果。 第一章绪论高精度曲线轮廓甲骨文字形生成系统的研究与实 拟合生成甲骨文曲线轮廓字形的主要方法是：首先反求出过甲骨文原始字形轮 特征点的三次均匀b 样条曲线的控制点；然后利用最小二乘法求解与原始字形轮 上的离散点距离总偏差最小的局部形状参数；最后根据所求的控制点和形状参数进 三次b 样条曲线拟合，生成用b 样条曲线描述的高精度甲骨文字形曲线轮廓。这 过程中通过数学运算自动获取最逼近原始曲线段的形状参数，即三次b 样条拟合 参数是自适应的，同时保证了新生成甲骨文字形曲线轮廓的精确度。 1 2 2 本文研究意义 殷墟甲骨文在1 8 9 9 年被发现，此后不久，学术界就开始了对甲骨文语言学的研 究，到目前为止，甲骨文语言学的研究已取得了辉煌的成蒯引。 随着信息技术的发展，人们不再局限于仅仅研究甲骨文这门语言，如何将现代化 的科学技术运用到甲骨文上已经成为甲骨文数字化研究的热点。甲骨文数字化使得专 家们对甲骨文的研究更加方便，对甲骨文的保护更加容易，使甲骨文的应用和传播更 加广泛【5 】。甲骨文数字化是指利用计算机对其进行处理、存储和使用，将原始的甲骨 文转化成数字材料。目前对甲骨文进行计算机处理的研究还不能满足实际需型6 。 本文研究的内容就是甲骨文数字化工作之一，甲骨文数字化使得甲骨文不再只属 于研究甲骨文的专家学者们。数字化的甲骨文可以在电脑上方便的显示、使用和处理， 利用现代网络技术可以快捷地进行甲骨文文化传播与学术交流，普通大众可以更加方 便的接触和学习甲骨文【6 1 。因此，应用现代科学技术手段将甲骨文数字化处理使得甲 骨文的传播更加快捷和广泛。因此，将现代科学技术应用于甲骨文更加有利于保护和 继承这一珍贵的文化遗产。 1 3 本文组织结构 第一章简介了本文的研究背景、内容及意义，并说明了本文的组织结构。 第二章介绍相关技术，主要包括图像处理技术、聚类分析以及曲线造型技术。 第三章介绍了甲骨文图像处理技术。主要包括图像去噪和图像分割等，提取甲骨 文原始字形轮廓并获取轮廓上特征点的信息。提出一种结合邻域法和k 均值聚类分 4 高精度曲线轮廓甲骨文字形生成系统的研究与实现 第一章绪论 析的图像分割方法，有效的将甲骨文文字目标从原始甲骨文图像中分割出来。 第四章介绍了三次均匀b 样条的原理和性质，提出一种带自适应形状参数的三 次b 样条曲线拟合方法。该方法根据甲骨文原始字形轮廓的特征点信息，计算并获 取三次b 样条曲线拟合的控制点：结合最f l , - 乘法和带形状参数的三次b 样条，实 现了参数自适应的b 样条曲线拟合方法，生成了高精度曲线轮廓甲骨文字形。 第五章设计并实现了甲骨文字形自动生成系统，介绍了该系统的各个功能模块， 并演示系统的部分功能。 第六章对本文所做的工作进行了概括总结，并指出不足之处和下一步的研究方 向。 第二章相关技术高精度曲线轮廓甲骨文字形生成系统的研究与实现 2 1 数字图像处理技术 2 1 1 概述 第二章相关技术 数字图像处理起源于2 0 世纪2 0 年代，当时第一幅数字照片采用数字压缩技术通 过海底电缆从英国伦敦传输到美国纽约。此后，随着遥感等领域中的数字图像处理技 术的应用，使得图像处理技术逐渐发展起来。第三代计算机问世后，数字图像处理技 术便开始迅速发展并得到普遍应用【9 】。数字图像是现代社会中不可缺少的信息元素之 一，是信息科学、工程学、医学、生理学、遥感技术、地质学甚至社会科学等学科的 重要基础。数字图像处理技术广泛应用于人类生活和工作的各个方面，是一门具有经 济和社会效益的实用技术。随着未来计算机和信息技术的发展，可以预见数字图像处 理技术必将更加深入到生产和科研活动当中。 数字图像处理又称为计算机图像处理，它是指将图像信号转换成数字信号并利用 计算机对其进行处理的过程，数字图像处理技术主要包括图像的转换和存储、图像视 觉优化和图像理解三个层冽1 0 l 。具体技术内容构成如图2 1 所示。 图2 1 数字图像处理技术 6 高精度曲线轮廓甲骨文字形生成系统的研究与实现第二章相关技术 在对甲骨文图片的处理过程中，使用到的数字图像处理技术主要包含图像数字 化、去噪、分割、平滑以及图像特征提取等。 2 1 2 图像分割 为了有效的进行图像描述和分析，往往先把图像分成若干个不同意义的区域，称 为图像分割1 1 】。图像分割是图像处理、模式识别和人工智能等许多研究领域的重要课 题之一，它的应用范围非常广泛，例如：工业自动化、文档图像处理、遥感和生物医 学图像分析、农业工程等方面。图像分割一直是图像处理领域中的一个比较活跃的分 支【12 1 。 图像分割的基本概念就是把图像中具有特殊涵义的不同区域( 例如依据图像的灰 度、颜色、纹理和边缘等特征的不同区域) 区分开来，把图像分成各自满足某种相似 性准则或具有某种同质特征的连通区域的集合的过程。这些区域是互不相交的，每一 个区域都满足特定区域的一致性f 1 3 - 15 1 。 假设集合r 代表整个图像区域，按一致性属性准则p 将图像r 分割分成n 个非 空子集 r i , r ：r 。) ，且这些子集必须满足以下几个条件： ( 1 ) u r ，= r l f f i l ( 2 ) r 。nr ，= 矽，v i j ( 3 ) p ( r 。) = t r u e ，v i ( 4 ) p ( a jnr = f a l s e ) ，v i ，r ，与r j 相邻 图像分割也是计算机视觉研究中的一个经典难题。到目前为止，还没有哪种图像 分割方法能满足全部图像的分割需要。 图像分割方法的种类很多，例如：基于最大一维熵的图像分割法【16 。1 引、基于聚类 图像分割法【1 蛆4 1 、基于边缘检测的图像分割法f 2 5 1 、基于阈值的图像分割法【2 3 1 、基于 小波分析的图像分割法1 3 4 , 3 5 】、基于神经网络的图像分割法等【3 6 ，3 7 1 。 在本文中，图像分割的主要目的就是让计算机能够自动判断哪些区域是属于文字 区域，哪些区域属于背景区域，将文字目标从甲骨文图片中提取出来，为下一步的工 7 第二章相关技术高精度曲线轮廓甲骨文字形生成系统的研究与实现 作做准备，图像分割效果的好坏直接影响着后续实验工作。 2 2 聚类分析方法 聚类分析指将物理或抽象对象的集合分成为由类似的对象组成的多个类的分析 过程。聚类分析是由若干模式组成的，是研究分类的一种多元统计方法。通常，模式 是一个度量的向量，或者是多维空间中的一个点。聚类分析以相似性为基础，在一个 聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性 3 8 , 3 9 1 。 聚类源于很多领域，包括数学、经济学、生物学、计算机科学和统计学等，并且 在各个应用领域也都得到广泛的应用，例如：图像分割、文本划分、数据挖掘、网络 传感技术、图像处理、神经网络等数据分析的各个方面。 聚类分析是通过对数据进行建模并简化数据的一种方法。传统的统计聚类分析方 法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类法、有重叠聚类法 和模糊聚类法等【3 8 小】。并且这些方法已经广泛应用于社会的各个方面，例如：网络、 电子商务、地理、保险业和生物分析等。 本文在图像处理过程中主要使用的是k 均值聚类分析方法。k 均值聚类算法主 要思想是接受输入量k ；然后将n 个数据对象划分为k 个聚类以便使得所获得的聚类 满足：同一聚类中的对象相似度较高，而不同聚类中的对象相似度较小。聚类相似度 是利用各聚类中对象的均值所获得一个中心对象 来进行计算的【4 0 舶】。 k 均值聚类算法的工作过程说明如下：首先从聆个数据对象中任意选择k 个对象 作为初始聚类中心；而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度， 分别将它们分配给与其最相似的聚类；然后再计算每个新聚类的聚类中心( 该聚类中 所有对象的均值) ；不断重复这一过程直到标准测度函数收敛为止，一般都采用均方 差作为标准测度函数4 3 , 4 4 】。 2 3b 样条曲线造型技术 随着计算机科学技术和工业制造等行业的发展，计算机辅助设计也迅速发展起 来，并且很快应用到社会的各个领域，例如：地形地貌描述、铁路勘察设计与坏境工 8 高精度曲线轮廓甲骨文字形生成系统的研究与实现 第二章相关技术 程、服装设计、虚拟场景设计等，这一切都离不开不规则曲线曲面的拟合和生成技术。 所谓的曲线拟合是指在图像处理、工程设计等应用中常常需要用曲线按照一定要求逼 近一系列实测的有序数据点【4 5 , 4 6 1 。 在2 0 世纪4 0 年代中期，s c h o e n b e r g 4 7 】提出了b 样条这个概念，现在b 样条的 概念已经得到了很大的发展，并且在当前的计算机辅助设计系统中，b 样条曲线曲面 已经成为几何造型的核心部分。b 样条曲线曲面造型方法的理论基础就是b 样条，在 本文中，均匀周期b 样条是拟合生成甲骨文字形的重要理论基础之一。 2 3 1b 样条曲线的定义 设给定刀+ 1 个控制点p 。( 待0 , 1 ，刀) ，也称之为特征多边形的顶点，k 次( k + 1 阶) b 样条曲线的表达式是【4 8 】： b ( r ) = p n ( f ) ( 2 1 ) 公式( 2 1 ) 中n i j ( f ) 是调和函数，也称之为基函数，定义如下： 哪) = 亿鬟g + l m 乒c ，) = 警+ 墅垒生掣c ，乙“) 。2 2 ， 其中t 。是节点值，丁= i t o ，t l ，t l + 2 k + l 】构成了k 次b 样条函数的节点矢量，其中 节点是非递减序列，且三= 刀一k 。当节点沿参数轴均匀等距分布，即t i i - t i = c ，c 为常数，则表示均匀b 样条函数，否则表示非均匀b 样条函数。 当，f - f ( o f ”+ k + 1 ) ，节点向量丁= o ，l ，以+ k + 1 】时，均匀b 样条称为均匀周 期b 样条，即基函数n f ，1 ( f ) 的形状都是相同的，n i ，1 ( f ) 可以由n i 一1 ，l ( f ) 向右移一个单 位得到。由此可知所有的f ，| | ( f ) 的形状也相同，即n i ，惫( f ) 由n i 一1 ，| | ( f ) 向右移位得到。 此时有：n i ，k ( t ) = n i 一1 ，七( ，) = n “1 ，七( f ) ，u e t f + f ，t k + i + l 】，均匀周期b 样条基函数如图2 - 2 9 第二章相关技术高精度曲线轮廓甲骨文字形生成系统的研究与实现 所示。 图2 - 2 均匀周期b 样条基函数 对于七次均匀周期b 样条，基函数 r f | ( f ) 具有下列几个特性： ( 1 ) nm 七( f ) ：1 ； i = 0 ( 2 ) n i 七( f ) 0 ，t k f t n + l ； ( 3 ) n f 七( ，) 具有c 七一7 连续性，其中，为重节点。 由此可知，b 样条曲线段以b 样条函数的各段为基函数。公式( 2 1 ) 表明刀次b 样条曲线段上的点b ( t ) 是由数据点p f 各与刀次b 样条基函数积的总和形成，b 样条函 数的某一段。上( r ) 反映了相应的数据点p ，对b 样条曲线段上点b ( ，) 的影响，即每段b 珂) 中若干个顺序排列的点所控制。 图2 - 3 中，通过改变曲线( a ) 的控制点忍生成了 了曲线的局部形状，并没有影响到由e 4 、b 和圪 1 0 高精度曲线轮廓甲骨文字形生成系统的研究与实现 第二章相关技术 p 1 一 p l 图2 - 3b 样条曲线的局部调整 b 样条除了具有局部控制特征之外，还可以通过改变控制点的个数来设计或者控 制曲线，而不需要改变多项式的次数。类似地，b 样条还可以通过增加节点向量的值 从而辅助设计曲线。 k 次b 样条具有下列性质【4 9 】： ( 1 ) 在f 的取值范围内，多项式曲线的次数为k 一1 ，并且具有c 扣2 的连续性； ( 2 ) 对于, + 1 个控制点，曲线由刀+ 1 个混合函数进行描述； ( 3 ) 每个混合函数( f ) 定义在f 取值范围的k 子区间上，以节点向量r ，为起点； ( 4 ) 参数t 的取值范围由刀+ k + 1 个节点向量中指定的值分成 + k 个子区间； ( 5 ) 每个样条曲线段( 在两个相邻节点值间) 受k 个控制点影响； ( 6 ) 任意一个控制点可以影响最多k 个曲线段的形状。 另外b 样条曲线位于至多k + 1 个控制点所形成的凸壳内，因此b 样条与控制点 位置密切关联。对于节点到r 川区间上的任意值r ，所有的基函数之和为1 ： 2 4 本章小结 j ，t ( f ) = 1 ( 2 3 ) 本章主要对数字图像处理、聚类分析以及b 样条曲线造型等相关技术进行了描 述。这些理论和技术是本文研究甲骨文字形生成过程的理论基础和技术依据。 数字图像处理技术和聚类分析主要应用在甲骨文原始图像的分割上，即将甲骨文 的文字目标从背景中分离出来，并提取出甲骨文字体的轮廓信息，获取原始字形特征 第二章相关技术高精度曲线轮廓甲骨文字形生成系统的研究与实现 点。利用三次b 样条曲线来拟合生成甲骨文曲线轮廓字形。 在实际应用过程中，直接利用传统的基本算法对甲骨文进行处理并不能得到令人 满意的效果。为了提高甲骨文图像处理的效果和曲线拟合字形的精确度，下面章节将 在这些技术和理论基础上对传统的方法进行改进以满足实际应用的需要。 1 2 高精度曲线轮廓甲骨文字形生成系统的研究与实现第三章基于k - 均值聚类的甲骨文图像预处理方法 第三章基于k 均值聚类的甲骨文图像预处理方法 3 1 引言 几千年来，甲骨文一直深埋地下，很多甲骨被腐蚀，加之后来出土时的损坏，造 成许多甲骨残缺不全，大多数的甲骨都有明显的裂痕，以此为原型的甲骨文图片往往 残缺不全，字形模糊，含有很多噪声点【5 】。因此需要对甲骨文图片进行图像处理，目 的就是为了去除背景和噪声，分割出甲骨文字体目标区域，对其进行边界提取和轮廓 跟踪等操作，获取甲骨文原始字形轮廓线上的特征点，为下一步的工作做准备。 聚类算法是根据某种距离将对象划分成一组数据对象的集合，其中k 均值方法 是聚类分析最常用的方法之一，根据数据的内在性质将其划分为若干个聚类区，尽可 能使区内元素距离小，区间元素距离大 5 0 , 5 1 】。因为k 均值聚类的这一特性，现在已 有很多研究结合k 均值聚类方法以及其它方法做出各种各样的尝试，将其应用到数 据挖掘、网络传感技术、图像处理、神经网络等数据分析的各个方面【5 2 侧。 本章根据甲骨文原始图片的特点，结合k 均值聚类分析方法和八邻域法，提出 一种基于改进的k 均值聚类图像处理方法。该方法可以更好的将文字目标中的噪声 和背景区域去除，将甲骨文字体目标分割出来。在图像分割后，可以根据数学形态学 中的膨胀、图像平滑等原理对甲骨文文字目标进行优化。最后进行边界提取、轮廓跟 踪，获取甲骨文原始字形轮廓线上的特征点信息，为下一步工作做准备。甲骨文图像 预处理的具体步骤如图3 1 所示。 甲骨文原始陋嘲 中值滤波 图像l，j 去噪 提取特征点 改进的k 一均值聚 类进行图像分割 黼艮踪同膨胀；差茎提取 图3 1 甲骨文图像预处理过程 第三章基于k 均值聚类的甲骨文图像预处理方法高精度曲线轮廓甲骨文字形生成系统的研究与实现 3 2 基本原理 3 2 1k 均值聚类方法 k 均值聚类算法m a cq u e e n 于1 9 6 7 年提出，因算法简单且收敛速度快得到了非 常广泛的应用。其基本思想是选取k 个数据对象作为初始聚类中心，通过迭代把数据 对象划分到不同的簇中，使簇内部对象之间的相似度很大，而簇之间对象的相似度很 小【5 羽。k 均值聚类分析的算法基本过程如下【5 3 , 6 1 】： 设s = x l , x 2 ，x n ) 代表n 个对象构成的集合，而c l ，c 2 ，c k 是足个不同的划分 集合，则须满足： c f c i , f = 1 ，2 ，k ； qnc ，= 矽，汪l ，2 ，七；j = 1 ，2 ，k ；且 ( 1 ) 从s 中随机选出k 个聚类中心( c l ，c t ) 作为初始聚类中心。 ( 2 ) 对每个数据对象一按某种距离模式分配给最邻近的聚类中心q ，f = 1 , 2 k 。 ( 3 ) 对每一类中的所有对象取平均值作为新的聚类中心，表达式为： 矿= 吉奢乩2 ，七 ( 4 ) c ，不再变化或者聚类的成员不再变化则终止，否则转到第( 2 ) 步。 3 - 2 - 2 邻域法 ( 3 1 ) 对灰度图像而言，仅通过对某个像素点灰度值的分析所获得的信息比较有限，而 且并不可靠，因为图像所包含的信息是由许多像素点共同组成，因此对图像进行处理 过程中常常会结合邻域点来进行分析，这样分析的好处是能够适当的保持和增强图像 的信息。 邻域运算是指输出图像中的每个像素是由对应的输入像素以及其邻域内的像素 点共同决定的图像运算，主要用于对图像进行空域滤波，比如平滑、中值滤波、细化 等。 1 4 os = c 七u脚 z 高精度曲线轮廓甲骨文字形生成系统的研究与实现 第三章基于k 一均值聚类的甲骨文图像预处理方法 假设丁为像素点p o1 拘3 x 3 的八邻域集合( 包含异) ，如图3 - 2 所示。表示丁的 元素，( e ) 表示点e 的灰度值，q 表示各点的权重，则r 点的灰度值可表示为： 3 2 3 膨胀 觚，2 嘉渺弓) p |p 2p 3 # ? p 3 p 5 貔幺 p 6 p ， p 8 图3 2 八邻域图 ( 3 2 ) 膨胀是数学形态学中最基本的运算之一，它的作用是把图像周围的背景点合并到 目标物体中，如果两个物体之间的距离比较近，那么膨胀运算可能会使这两个物体连 通在一起，膨胀对填补图像分割后物体中的空间很有作用。简而言之，膨胀就是图像 中“加长 或“变粗 的操作，这种特殊的方式和变粗的程度由一个称为结构元素的 集合控制。 数学上，膨胀定义为集合运算。彳被b 膨胀，记为彳ob ，定义如下【6 2 】： 4o b = zl ( b ) ：na ( 3 3 ) 其中矽为空集，召为结构元素。总之，彳被b 膨胀是所有结构元素原点位置组成 的集合，其中映射并平移后的b 至少与彳的某些部分重叠。膨胀满足交换定律，即 彳ob = b0a 。在图像处理中，习惯于令第一个操作数为图像，第二个操作数为结 构元素，结构元素往往比图像小的多。 基本算法为：结构元素b 的原点平移过整个图像a 区域，覆盖a 中任何1 值的像 素，并且核对哪些地方与值为1 的像素重叠。如图3 3 所示。 第三章基于k 均值聚类的甲骨文图像预处理方法高精度曲线轮廓甲骨文字形生成系统的研究与实现 o o 0 o o o 00x =o0o oo，- | 0 0o o 00 鼍 00 0 o 000o o 00o o 0 图3 - 3 膨胀方法示意图 3 3 图像分割 3 3 1 改进k 均值聚类图像分割算法 0 0 o o 0 0 o o o o 0 o 0 o o o o 1 o 0 么0b o 0 0 0 0 o o o 0 o 0 甲骨文是刻在龟甲或兽骨上的文字，在其灰度图像中文字笔画具有比背景更深的 痕迹，且文字目标与背景的像素点都分别具有像素值一致性，如图3 - 4 ( a ) 、 图3 5 高精度曲线轮廓甲骨文字形生成系统的研究与实现 第三章基于k - 均值聚类的