（机械设计及理论专业论文）印花图案中细茎图样自动重描方法研究.pdf

浙江大学硕十学位论文 摘要 印染c a d c a m 系统采用先进的计算机处理技术、自动控制技术、机电 体化技术改造传统的印花图案设计和生产制造工艺，实现印花设计和生产过程的 自动化。 印花c a d 软件提供了强大的印花图样处理功能，但随用户需求的不断提高， 软件功能及性能的逐步完善一直为企业技术改进的目标。印花c a d 软件利用扫 描仪或数码相机等将花样图案输入电脑，进行分色处理和印前处理，以指导生产， 在此过程中因多种原因将噪声引入图像，如：布纹的干扰、布匹的褶皱、数码相 机的成像、图像的数字化等，使得图案多毛刺、边界模糊，无法直接用于生产。 因此用户需要根据因噪声腐蚀的花样图案，印花c a d 软件的处理工具，恢复理 想图案。对于印花图案中的复杂图样如细茎、撇丝、云纹、泥点等，由于其特征 较复杂，至今无成熟的自动处理算法，因此操作人员必须耗费大量的时间和精力 反复对照原图通过人机交互方式采用绘图工具手工重描生成符合生产要求的图 案，这对于大幅复杂图案往往会耗费一周甚至更长的时间。因此，该类软件迫切 希望增加复杂图样的自动重描功能，以提高效率。本论文主要研究基于角点特征 提取的方法，解决印花图案中细茎图样的自动重描问题。 本文的工作与印染c a d 企业杭州开源电脑技术有限公司合作进行，以开源 公司印花c a d 软件变色龙为开发平台，利用该软件的分色工具和边界跟踪工具 获取细茎边界，结合细茎图案的特征分析，突破传统的直接消除噪声生成新边界 的算法思想，利用多种算法检测出对于细茎图案特征最为关键的角点特征，并得 到平滑边界，同时得到部分对于边界信息相对重要的交点特征，然后利用角点和 交点及平滑的边界拟合生成新的细茎边界，并填充得到新的细茎图案。 论文对多种印花图案进行了细茎自动提取和处理方法的研究试验，修正了算 法，得到了较好的处理效果，可以用该功能来自动完成细茎重描，从而大大提高 了印花c a d 系统的自动化水平和处理效率。同时，这种处理思想和方法对其它 复杂图样特征自动重描功能的实现也提供了一定的借鉴作用。 关键词：印染业印花c a d 自动重描细茎角点模拟退火算法 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t t oi m p r o v et h et e c h n i q u eo fd e s i g np r i n t i n go nf a b r i ca n dt h ea u t o m a t i cd e g r e e o fi m a g ed e s i g na n dm a n u f a c t u r i n gp r o c e s s ，t e c h n i q u e so fa d v a n c e dc o m p u t e r p r o c e s s i n g , a u t o m a t i cc o n t r o l l i n ga n dm e c h a t r o n i ch a v eb e e ni n t r o d u c e dt o t h e a u t o m a t i cd e s i g na n dm a n u f a c t u r ei np r i n t i n ga n dd y i n gs y s t e m , a n da sar e s u l tw h i c h h i g l l l yi m p r o v e dt h ee f f i c i e n c ya sc o m p a r e dt ot h et r a d i t i o n a lw a yo fm a n u a li m a g e d e s i g na n dm a n u f a c t u r i n gp r o c e s s a m o n gt h ea u t o m a t i cp r i n t i n ga n dd y i n gt o o l s ，t h ec o m p u t e ra i d e dd e s i g n s o f t w a r eo f f e r e ds t r o n gf u n c t i o n s b u to w i n gt ot h ei n c r e a s i n gd e m a n df r o mt h eu s e r , t h ep e r f o r m a n c eo ft h es o f t w a r eh a sa l w a y sb e e nt h ei m p r o v i n gt a r g e t b yf a r , h o w e v e r , t h e r ea r en om a t u r er e c i p e sf o rt h ea u t o g e n e r a t i o no fc o m p l e xc h a r a c t e rs u c h a st h i n s t e m , o r c h i do rm u d p o i n t t h e r e f o r et h es o f t w a r ed e v e l o p e rh o p e st oa c h i e v e t h ea u t o g e n e r a t i v ef u n c t i o nt oi m p r o v et h ep r o d u c t i v i t y i nt h i sp a p e r , w em a i n l yt r y t ow o r ko u tt h ea u t o g e n e r a t i o no ft h i n s t e mt h r o u g hs t u d y i n gt h er e c i p eo fc o m e r d e t e c t i o n t h e w o r ki nt h i sp a p e ri sc a r r i e do u tb yc o o p e r a t i o nw i t hk a i y u a nc o ，l t d w i t h k a i y u a n sc a ds o f t w a r e 一- a n s c r i e sa st h ed e v e l o p i n gp l a t f o r m ，w eg e tt h et h i n s t e m c h a r a c t e ru s i n gt h ec o l o r - p a r t i t i o nt o o l s ，a n dt h e nw o r ko u tr e c i p e st og e tb o u n d a r i e s c o n s i d e r i n gt h ec h a r a c t e r i s t i co ft h i n s t e m , w eb r e a ko u tt h et r a d i t i o n a lt h o u g h t so f c r e a t i n gn e wb o u n d a r yb ys m o o t h i n gn o i s e ，a n dg e tt h em o s ti m p o r t a n tc o m e r c h a r a c t e ra n dp a r to fc r o s sp o i n tb yi n t e g r a t i o no fs e v e r a lc o r n e rd e t e c t i o nr e c i p e s , a n d s i m u l t a n e o u s l yg e tt h es m o o t hb o u n d a r y t h e nw e r e b u i l dt h en e wb o u n d a r yb yu s i n g t h ei n f o r m a t i o no fc o m e rp o i n t , c r o s sp o h na n dt h es m o o t hb o u n d a r y i nt h ee n d ，w e f i l lt h ea r e a se n c l o s e db yt h en e wb o u n d a r ya n dg e tt h en e wt h i n s t e mi m a g e t h i sp a p e rh a st e s t e do u rr e c i p ew i t ht h et y p i c a la n dc o m p l i c a t e dp r i n t i n gi m a g e s ， r e c t i f i e dt h ep a r a m e t e r s , a n da n a l y z e dt h et h i n s t e mp r o c e s sr e s u l t s t h em e t h o dc o u l d b eu s e dt oc o m p l e t et h ea u t o g e n e r a t i o no ft h i n s t e ma n dh e n c ei m p r o v et h ea u t o m a t i o n d e g r e ea n dp r o c e s s i n gp r o f i c i e n c yo fp r i n t i n ga n dd y i n gc a d s o f t w a r e a tt h es a m e t i m e ，t h ei d e a sa n dp r a c t i c e si nt h i sp a p e rm i g h tg i v es o m ei n s p i r a t i o n st ot h er e s e a r c h o fs i m i l a rc o m p l e xc h a r a c t e rp r o c e s s i n gt e c h n i q u e s k e yw o r d s ：p r i n t i n ga n dd y i n g , a u t o g e n e r a t i o n , t h i n s t e m , c o r n e r , s i m u l a t e d a n n e a l i n g 学号2 q 3 q 曼! 垒兰 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得迸江盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：嚣承葩 签字日期： 石年，月7 日 学位论文版权使用授权书 本学位论文作者完全了解逝江盘鲎有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权澎鎏盘鲎可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：菏秘芎：导师签名： 签字日期： 。占年 ；月7 日 签字日期： 6 6 年，月1 日 学位论文作者毕业后去向： 工作单位：西门子迈迪特 通讯地址： 电话： 邮编： 浙江大学硕十学位论文 1 1 引言 第一章绪论 提起计算机辅助设计与制造( c a d c a i i ) ，许多人立刻想到了汽车制造，建筑 设计，零件加工以及复杂的电路板设计等等，c a 9 c a m ( c o m p u t e ra i d e d d e s i g n c o m p u t e ra i d e dm a n u f a c t u r e ) 是2 0 世纪全球最杰出的工程技术成果之 一，是跨世纪的国家关键技术。c a d c a m 技术的发展与应用水平已成为衡量一个 国家工业现代化的重要标志，在一定程度上反映出一个国家的综合实力。推广 c a d c a l i 技术是提高产品和工程设计技术水平的一项重大措施，企业在激烈的市 场竞争中要想立于不败之地，就必须以新产品为龙头，以c a d c a l l 技术应用为手 段，使其转化为生产力，推动企业快速发展。计算机数字化设计的引入，极大的 提高了我国的社会生产效率，缩短了与世界加工制造业的差距，为社会带来了可 观的经济效益。近年来，随着计算机技术的高速发展，以电子计算机为主体的现 代控制技术已慢慢的渗透到纺织、印染加工的各个领域，可以说它将给纺织印刷 行业带来了一次新的技术革命。 纺织印染业是我国的主要传统产业，也是我国出口创汇的重要组成部分。印 染行业是纺织品深加工、精加工以及提高附加值的关键行业，是纺织行业发展和 技术水平的综合体现“1 。但由于我国纺织品的工艺水平技术落后，造成了产品质 量档次不高，附加值较低的现状，在国际市场上一直扮演着初级商品供应商角色， 成为制约出口的重要因素。中国加入世贸组织两年多来，中国印染行业出现了前 所未有的持续快速发展局面。多元化投资大量涌入，先进装备相继投产，新产品、 新技术纷纷亮相，在全球的产能份额持续上升，已成为世界印染布产量最大的国 家。受传统工艺的影响，我国印染c a m 相对落后于国际水平，但是我国在印花行 业c a d 设计方面我国起步较早，至今处于国际领先地位。”1 1 2 课题来源及背景 印花c a d 软件提供了强大的印花图样处理功能，但随用户需求的不断提高， 软件功能及性能的逐步完善一直为企业技术改进的目标。本论文主要研究基于角 点特征提取的方法，解决印花图案中细茎图样的自动重描问题。 数码喷射印花系统的实现，使得从客户提供的花样扫描到大样生产只需几个 小时，完全能够适应小批量、多品种的快速生产的需要嘲印花c a d 软件利用 扫描仪或数码相机等将花样图案输入电脑，进行分色处理和印前处理，以指导生 1 0 浙江大学硕七学位论文 产，但实际生产时，在此过程中因多种原因将噪声引入图像，如：靠纹的干扰、 布匹的褶皱、数码相机的成像，图像的数字化等，使得图案多毛刺、边界模糊， 无法直接用于生产。因此用户需要根据因噪声腐蚀的花样图案，印花c a d 软件 的处理工具，恢复理想图案。对于印花图案中的复杂图样如细茎、撇丝、云纹、 泥点等。由于其特征较复杂，至今无成熟的自动处理算法，因此操作人员必须耗 费大量的时间和精力反复对照原图通过人机交互方式采用绘图工具手工重描生 成符合生产要求的图案，这对于大幅复杂图案往往会耗费一周甚至更长的时间。 因此，该类软件迫切希望增加复杂图样的自动重描功能，以提高效率。这在近年 来一直是该行业的难点，至今仍然没有公司解决该类问题，因此本论文的研究有 重要意义。该项目是与开源公司合作开发细茎特征的自动提取功能。 1 2 印花c a d 1 2 1 印花c a d 发展现状 印花指在用染料或颜料处理后的织物上饰印花纹的工艺过程。在数码印花技 术中，首先通过扫描仪或数码相机等输入手段，把所需图案扫描输入计算机，经 该系统( c a d ) 编辑处理，或由计算机直接生成图案，利用印花分色软件对图案 处理，调配色彩，产生出满意的图案。因此，印花分色软件的使用使得图案修改 极为方便，且计算机屏幕显示出的彩色花样，就是面料图案效果，为印花图案的 设计提供了极大的便利。至今，国内外主要印花分色软件系统有国内的开源公司 a n s e r i e s 变色龙分色软件、新创公司的新创v 2 0 0 3 智能印花分色系统、金吕印 花( e x 9 0 0 0 ) 分色系统，宏华a t s l 印染分色设计系统，德国w i r t h 爱德艺印花分 色图像处理系统及比利时s o p h i s ，法国电脑分色设计制版系统等产品。嘲由于印 花c a d 设计系统不受传统工艺的局限，其发展较早，目前该类软件已经相对成熟。 我国由于在印花c a d 软件行业起步较早，至今仍然居于国际先进水平。该类软 件功能具有相似性，因此我们以本论文使用的印花分色软件a n s e r i e s 为例，简 要介绍该类软件的功能。 1 2 2 印花软件a n s e r i e s 的功能 n s e r i e s 印花分色软件是运行在w i n d o w s 操作系统上成功的分色c a d 软件 之一，它与传统手工描稿制版相比具有十分明显的优势。该系统自1 9 9 5 年投放 市场以来，已经进行了l o 次版本升级，使系统始终处于国内外同类产品的先进 水平，在印花行业占据了重要的位置，对印染行业的发展起到了很大的推动作用。 系统主要特点如下 1 、强大的多层操作、丰富的工具、高效的功能 浙江大学硕士学位论文 绪论 2 、有效的内存压缩 3 、兼有图像和图形矢量功能 4 、枯笔集 5 、单、多层、云纹配色，色库、色卡功能 6 、立体贴面 7 、套装软件包括分色、设计、发排等 该软件具有三大块功能：分色部分，设计部分，打印部分。 1 2 2 1 分色功能 其分色部分实现了针对印染行业图案特征的图样处理功能，包括拼接、区域、 花样多层管理与操作。撇丝、泥点、特殊花样、云纹、细茎、颜色保护、层问色 保护、矢量图形的应用，内存的压缩，使大图处理起来更快捷。 其中撇丝、泥点、云纹、细茎是印染行业典型的复杂特征，下面将依次简要 介绍这些特征。 细茎：是由一种等宽的细长边界组成的图案。 图1 1 具有细茎特征的图案 撇丝：花样上至少有一个端点又尖又长的色块，按其类型可分为云纹撇丝、 泥点撇丝以及成组撇丝。 浙江大学硕士学位论文绪论 图1 2具有撇丝特征的图案 图1 3撇丝特征 泥点：不同大小、层次、密度、性状的点子组成的图案，按其类型可分为云纹泥 点、大小泥点以及随机泥点、模式泥点、自创建泥点等。 浙江大学硕七学位论文 图1 4 具有泥点特征的图案 云纹：由前景色一背景色渐变的图案，多层的应用方便混合云纹的操作“ 图1 5 云纹特征 1 2 2 2 设计功能 现在随着人们的生活水平提高，人们对服饰、室内布艺装饰的要求也越来越 高。花样的新颖、色彩的调配，逼真的效果，需要没计者能快捷的表现出来。而 手工设计者在设计时，必需先打底稿，然后用水彩、水粉等绘画颜料，用毛笔勾 浙江大学硕七学位论文 线填色，或是喷枪刻模喷制。碰到系列花型、不同配色方案，则更需在复印的底 稿上用不同的套色再重现画出，麻烦而费时。用变色龙设计软件则轻而易举。可 借助压力笔，利用变色龙自带的工具，任意的表现不同风格的花样效果。而且可 以自由地配出多种色位，直至获得自己所满意的效果为止。更突出的功能是，可 将设计好的花样直接贴到服装模特、床罩、窗帘织物上，达到一种逼真的效果， 让客户直截了当看到其真实的立体效果，从而大大提高了速度和效率。 设计软件包含了分色部分的所有功能，同时增加了许多全新的功能，使设计 师能够完全脱离手工操作，甚至还可以做出手工难以达到的效果，并且设计好的 花样可以直接出片，不用分色，使整体工作效率提高5 0 以上。设计新花样也由 原来的2 - 4 张月提高到5 - 1 0 张月。 1 2 2 3 打印功能 变色龙打印部分已经实现激光照排打印、圆网喷蜡打印、平网喷蜡打印。嘲 1 2 3 a n s e r i e s 功能遗留问题 该类软件已经实现了分色和设计功能和打印功能，以便于用户直接由计算机 生成图案进行设计，从而缩短了生产周期。但是该软件也没有解决图案的自动重 描功能。其中该公司尝试了撇丝的自动重描功能，其实现效果如图1 6 、1 7 ， 需要进步完善才可以用来指导生产。另外该公司在去年尝试开发泥点的自动重 描功能，但是由于得到的效果与原图相差较大，无法用于生产而对于细茎特征， 由于该特征更为复杂，该公司也一直未能实现自动重描的功能，因此我们与该公 司合作，开发研究细茎的重描功能。 撇丝的实现效果： 图1 6 撇丝特征图1 7 撇丝重描效果 浙江大学硕士学位论文 1 3 细茎图案特征 如图1 8 、1 9 所示为典型的细茎图案，细茎为等宽细长曲线，利用细茎可以 任意勾勒出多种形状的图案。 图1 8 细茎的图样 图1 9 细茎的图样 图1 1 是存在细茎特征的实际应用图案，图中花瓣或叶片的边缘都是由细茎 特征构成的，如局部放大图1 1 0 。 浙江大学硕+ 学位论文 图1 1 0 花瓣特征 1 3 1 角点的特征 角点( s l i g h t l yr o u n d e dc o r n e r ) 可以认为是理想的光滑边界上不应存在 的点，表现为曲率较大，且过渡不圆滑如下图1 1 l 。 图1 1 1 角点 在细茎的形状信息中，角点包含着最重要的信息。在角点处两边细茎的接头 形状对细茎重描效果有决定性的作用，且在细茎的图样中，其角点特征具有规律 性，即角点的接头方式为尖头、圆头、方头三种形式。如图1 1 2 中有多个角点， 由于设计的需要，细茎中往往包含多个角点。 图1 1 2 细茎的角点特征 1 3 2 交点的特征 实际细茎的图案由于信息量较大，且较复杂，在多处存在多条细茎相交的情 况，如图1 1 3 所示。交点的曲率特征与角点相似，即曲率值较大，但交点形状 随意，过渡随意，而角点则特殊设计为一定的形状。根据细茎的图案特征，我们 浙江大学硕十学位论文 可以认为在交点存在的地方不存在角点，而对于以单条边界考虑，则交点的特征 对角点的辨认构成了一定的干扰。 图1 1 3 细茎相交的地方 1 t t 噪声的特征 1 3 3 1 图像的噪声类型 图像噪声使图像产生退化，一般图像的噪声是不可预测的随机信号，我们只 能用统计学的方法去认识。从统计学观点看，凡是统计特征不随时间变化的噪声 称为平稳噪声，凡是统计特征随时间变化的噪声称为非平稳噪声。从噪声的幅度 分布的统计来看，其噪声密度函数有高斯型、瑞利型，分别称为高斯噪声和瑞利 噪声。我们又将频谱均匀分布噪声称为白噪声蜘。 1 3 3 2 图像的噪声特征 噪声是随机性的，因而需要用随机过程来描述，即要求知道其分布函数和密 度函数。但在许多情况下，这些函数很难测出或描述，所以常用统计特征来描述 噪声，如均值、方差、相关函数等。设灰度图象信号是按二维分布f ( x ，y ) 的， 则噪声可以看作对其亮度的干扰。用n ( x ，y ) 来表示。 均值，描述噪声的总功率： e n ( x ，y ) ( 1 1 ) 方差，描述噪声的交流功率： e ( ( n ( x ，y ) - ee n ( x ，y ) ) 2 ( 1 2 ) 均值的平方，表示噪声的直流功率： e n ( x ，y ) 2( 1 3 ) 1 3 3 3 噪声的模型 在图像处理中，退化是由噪声引起。按噪声对信号的影响可分为加法噪声和 乘法噪声模型两大类。设f ( x ，y ) 为信号，n ( x ，y ) 为噪声，信号处理后( 即退化) 的输出为g ( x ，y ) 。 浙江大学硕士学位论文 加法性噪声 g ( x ，y ) = f ( x ，y ) + n ( x ，y ) 输出的信号是噪声和信号的叠加，其特点是n ( x ，y ) 和信号无关，无论输入 信号大小，其输出总是与噪声相叠加。 乘法性噪声 g ( x ，y ) = f ( x ，y ) 1 + n ( x ，y ) = f ( x ，y ) + f ( x ，y ) n ( x ，y ) 其输出是两部分叠加，噪声项信号受f ( x ，y ) 的影响，f ( x ，y ) 越大，则第二 项越大，即噪声项受信号的调制。 1 3 3 3 细茎图案中噪声特征 图1 1 4 噪声 印染分色c a d 系统中噪声的引入是多原因的。首先，通过各种数字化手段， 如扫描仪、数码相机等将所需图像输入到计算机，并经采样、量化、编码等一系 列步骤处理图像。该系列步骤中，扫描仪或数码相机等成像设备引入设备噪声， 量化引入量化噪声，另外如布纹的对图案的干扰，或布料或布匹褶皱对图案的干 扰、或由于同色等其他因素的影响，都有可能引入噪声，造成图像失真。我们所 得到的细茎图案中的噪声，并非简单或有一定规律的量化噪声和高斯噪声等，而 是随机、不均匀的可加性噪声。另外，在变色龙软件得到的图案，一般会由于腐 蚀的原因，造成边界信息的损失，但较少因某种原因而在边界上生成突变的噪声， 如图1 1 4 ，噪声生成的原因是认为边界被腐蚀了，即余下的凸出部分都应该是原 细茎上应该有的。 由以上图中可以看出，细茎由具有一定宽度的曲线构成，形状复杂，其角点 及在角点处的接头形状是决定细茎意境效果的重要特征，且实际的细茎图案中， 一般有多条细茎相交，且具有大量的随机噪声，增加了图案处理的复杂性。 其中图i 8 、1 9 为印染行业典型的细茎图样，该图样包含有细茎全部特征， 在实际应用中，便是利用这些细茎的特征构成任意形式的图案，因此论文中以其 浙江大学硕士学位论文 中一幅图1 8 为基础，研究印花图案中细茎图样自动重描方法。 1 4 论文解决的思路 综上所述，细茎自动重描所面临的问题：扫描得到的细茎图案，由于存在大 量噪声，造成图像的退化及失真，需要在此基础上恢复原始的细茎图案。 我们根据细茎的特征和图像的知识，制定以下解决方案： ( 1 ) 将细茎特征取出生成新的图层，在新层上处理细茎图案； ( 2 ) 取得细茎的边界点链； ( 3 ) 滤掉边界的噪声、得到新的边界，取得边界的角点和交点特 征； 一 ( 4 ) 拟合细茎边界； ( 5 ) 填充边界，得到新的细茎图案。 即处理流程为： i 得到图案l ll l i 得到新l l 的细茎层1 滤噪声，得新边界i 链，取角点和交点i i ? j 拟合边界k ! 填充边界 得细茎图案 图1 1 5 解决方案 - 1 1 - 浙江大学硕 学位论文 绪论 1 5 论文研究的内容 按照如上的解决方案，我们要研究每个步骤用到的算法。 由上可知我们首先利用软件中的并色功能，将判断为细茎的特征，合并为一 种颜色，并将其生成为新的层，在新层上进行处理，需研究的算法如下： 第一步：取得细茎的边界。 得到图像上感兴趣的具有细茎特征图案的区域，在该区域内提取轮廓，跟踪 该轮廓得到边界链。 第二步：处理细茎的边界。 该部分是本论文研究的核心内容。有多种经典算法可以用于恢复被噪声腐蚀 的边界，通过滤掉噪声得到平滑的边界，但是对噪声进行平滑必然会平滑掉边界 的某些特征，而细茎的特征中，角点特征尤为关键，其次，交点的形状和位置、 边界的形状和位置等也传递了细茎的重要信息。因此，如何在平滑边界的同时最 大程度的保留边界的特征，尤其是角点特征，是我们必须考虑的问题。 论文引入基于角点检测的算法，并分别以两种算法进行考虑：首先优化边界， 以降低噪声的影响，对该优化边界计算曲率以检测角点；对原粗糙的边界计算曲 率函数以检测角点。对于优化边界的算法中，考虑该类算法中在优化边界的同时 保留边界特征的程度，选取利用模拟退火算法优化边界，初检测边界角点。但是 由于算法中因边界的平滑而选出角点较少，论文中另外选用一种抗噪的算法对原 粗糙边界计算选取角点，以辅助判断，该算法选取的角点往往多于实际角点。然 后利用细茎的图案特征以筛选或补偿角点，从而最终较为准确地选取角点，并另 外选取对于边界特征影响较大的交点。 第三步：生成细茎图案。 该步骤拟合边界，并填充边界得到细茎图案。新的优化边界较为平滑且较大 程度的保留了细茎的特征，但是细茎的角点和交点位置对于细茎的形状非常重 要，而在优化的边界中，对该部分特征进行了平滑，因此对于角点和交点位置处 的边界，我们选取原边界上的点以三次b 样条曲线进行拟合，且由于角点和交点 的特征不同，因此我们在拟合时区别处理，而对于其他位置的边界点，我们选取 优化的边界点链以三次b 样条曲线进行拟合。则在新边界点和原边界点处断开的 位置利用插值算法，连接为光滑边界，从而取得平滑边界。对于得到的光滑边界 进行填充，得到细茎图案。 如下流程图，显示本论文中研究的算法。 绪论 塑翌查兰堡兰垡丝塞一 - 1 3 一 浙江大学硕士学位论文 绪论 1 6 论文的难点 由图像的知识我们可以知道，上述取得角点为本论文的难点。由于我们取得 的边界为离散的像素点，而非连续的边界曲线描述，曲线点的离散特性增加了曲 率计算的复杂性和扩大了噪声的影响，且由于噪声、角点和交点特征具有相似性， 即：其曲率值较大，因此难以准确的将该三类特征区分。对边界进行平滑滤除噪 声的同时，无法避免会将边界的角点和交点特征平滑，这样也为得到角点和交点 增加了困难。因此，论文重点研究角点检测的算法。 角点检测的算法在两大领域里发展：( 一) 对边界进行优化，检澳0 优化边界 的角点；( 二) 对原粗糙边界进行角点检测。两种算法各有其优缺点，对边界进 行优化可以减少噪声的影响，但无法避免对角点特征的平滑，从而漏选部分角点。 对原边粗糙界进行处理避免漏选角点，但无法避免噪声引起的伪角点。因此本论 文基于两类算法的各优缺性，分别设计选用两个领域里的最为适用的算法以选取 细茎的角点，互为补充。 对含有噪声的边界点位置进行优化，使其既保留角点的特征又除掉噪声，这 是对点位置的组合优化问题。我们在考虑该类算法各优缺性的基础上，最终选定 利用模拟退火算法的理论对边界进行优化。模拟退火算法是近年来提出的一种适 合解大规模组合优化问题的通用有效近似算法，我们利用模拟退火算法优化边界 点的位置，对优化的边界，在曲率函数空间计算其角点尖锐度，设定阀值选取角 点。 对原粗糙边界直接进行角点获取的算法，我们在考虑该类算法各优缺性的基 础上，最终选定自适应曲率函数的曲率计算方法以获取角点。 对上述两种算法选取的角点，我们根据细茎图案的特征以进一步筛选或补 偿，最终较为准确的获取角点。 下一章我们将针对边界优化介绍模拟退火算法的理论。 浙江大学顾十学位论文 第二章模拟退火算法 第二章模拟退火算法 【主要内容l 本章着重讨论了模拟退火算法。首先，介绍了其| i 身局部搜索 算法的特性和弊端。再通过对固体退火的物理图象和统计性质等背景的描述引入 模拟退火算法，阐述了该算法的总特性，详细介绍了算法应用关键冷却进度 表各项参数的一般选取原则，并介绍了对模拟退火算法的一般应用要求。然后， 针对模拟退火算法存在的不足提出了一种智能化的有记忆的模拟退火算法，以解 决边界平滑问题。 2 1 前言 论文的核心为边界角点的选取，一个好的角点搜索算法，应在精度和速度上 经受考验，只有精确度高且拐点冗余度小，提取出来的拐点才能准确反映曲线形 状。但是从原始图像中提取的对象边界常会受到背景因素和噪声的影响而使原本 平滑的边界出现“毛刺”，且数字化边界本身具有离散特性，也即点位置的不适 当放置，这样无疑会引起曲线上某些点的局部弯曲度突然增大而成为“伪角点”， 计算所得的曲率函数非常粗糙，而且，曲率的计算必须得到一阶、二阶导函数， 微分离散和噪声数据增加了噪声。论文中所得的边界为离散边界，我们在离散域 搜索边界的角点。离散域可以直接采用k - 曲率的思想来计算曲率函数，也可以先对 边界上的点的位置进行优化，从而减少数字边界的离散特性和噪声的影响，以接 近于连续边界，从而计算曲率函数。 对边界进行优化的算法，可以看成是边界上点的位置的优化配置问题，对含 有噪声的原边界点的位置进行优化，使其既保留角点的特征又去掉噪声，这是对 点位置的组合优化问题。 模拟退火算法是近年来提出的一种适合解大规模组合优化问题的通用有效 近似算法。它与以往的近似算法相比，具有描述简单、使用灵活、运用广泛、运 行效率高和较少受仞始条件限制等特点，因此具有很高的实用价值。嘲 论文中选取基于模拟退火算法平滑边界，对边界点位置进行优化以平滑边 界，并以该平滑边界为基础选取角点，因此在本章首先详细介绍模拟退火算法。 组合优化问题是在给定的约束条件下，求目标函数最优值( 最大值或最小值) 的问题。 优化问题包含三个基本要素： 浙江大学硕士学位论文 第二章模拟退火算法 ( 1 ) 变量求解过程中选定的基本参数； ( 2 ) 约束对变量t 取值的种种限制； ( 3 ) 目标函数表示可行方案衡量标准的函数。 组合优化问题的一个实例可以表示为一个对偶( s ，f ) ，其中解空间s 为可行解集， 目标函数f 是一个映射，定义为： f s 一 r 求目标函数最小值的问题称为最小化问题，记为： r a i n f ( i ) ，i s 求目标函数最大值的问题称为最大化问题，记为： m a x f ( o i s 显然，只要改变目标函数的符号，最小化问题与最大化问题就可以等价转换。 1 9 8 2 年，k i r k p a t d c k 等将退火思想引入组合优化领域，提出了一种求解大规 模组合优化问题的有效近似算法模拟退火算法。它源于对固体退火过程的模 拟；采用m e t r o p o l i s 接受准则；并用一组称为冷却进度表的参数控制算法进程， 使算法在多项式时间里给出一个近似最优解。 下面将首先介绍一些关于组合优化的基本概念，接着说明模拟退火算法的前 身局部搜索算法及其特点和弊端，然后介绍模拟退火算法的数学背景、理论 基础和实现形式，最后提出一种基于模拟退火算法的改进算法- 有记忆的模拟 退火法，该算法不改变传统模拟退火算法进程，但能在一定程度上有效的提高优 化解质量。 2 2 整体最优解、邻域结构与局部最优解 定义2 1 设( s ，d 是组合优化问题的一个实例，i 叩t s ，称i 0 p i 为最小化问题 r a i nf ( i ) ，i s ； 的整体最优解，若 f ( i 。曲f ( i ) ，对所有i e s 成立。 定义2 2 设( s ，d 是组合优化问题的一个实例，则一个邻域结构是一个映射 n ：s 一2 s 浙江大学硕t 学位论文第二章模拟退火算法 其中，2 s 表示s 的所有子集组成的集合。其涵义是，对每一个解i s ，有一个解 的集合s ie s ，这些解在某种意义上是“邻近”i 的。集合s j 称为i 的邻域，每 个j s i 称为i 的一个邻近解。 定义2 3 设( s ，f ) 是组合优化问题的一个实例，而n 是一个邻域结构，f s i 。 称i 为最小化问题 m i n f ( i ) i s 的局部最优解，若 f ( i ) 耋f t j ) ，对所有j e s i 成立。 2 3 局部搜索算法 局部搜索算法是一种通用的近似算法，其基本法则是在邻近解中迭代，使目 标函数逐步优化，直至不能再优为止。局部搜索法灵活、简便，能求解多种组合 优化问题，并能给出较好的近似解。 2 3 1 局部搜索算法的算法描述 局部搜索算法从一个初始解i s 开始，然后运用一个产生器，持续的在解i ( 称 为当前解1 的邻域s i 中搜索比i 更优的解。若找到比i 更优的解，就用这个解取 代i ，成为当前解，再对当前解继续算法；否则算法终止，当前解就是算法的最 终解。 下面给出伪c 语言描述的求解最小化问题的局部搜索算法。 算法2 1 最小化问题的局部搜索算法 l o c a l s e a r c h 0 l m r a l l z e ( i o ) ； i = i o ； d o f o r 0 = d j s i i f ( 绚) f 【i ) ) i - - j ； 浙江丈学硕七学位论文第二章模拟退火算法 w h i l e ( s i 内还有解未被搜索到) ； 2 3 2 局部搜索算法的特性 由算法描述可知，局部算法具有以下特性： ( d 通用性。只要给定组合优化问题的实例“s ，d ) ，产生器和邻域结构，就能实现 算法； ( 2 ) 灵活性。可以选用不同机制的产生器，设定不同复杂程度的邻域结构； ( 3 ) 最终解是某个局部最优解。由于在大多数情况下，无法设定恰当的邻域结构， 因此，一般不能保证最终解的质量； ( 4 ) 最终解的质量还依赖于初始解的选择。而对大多数组合优化问题来说，不存 在选择初始的准则，算法执行时的初始解往往是随机选取的，它可能导致低质的 最终解。 2 3 3 改善局部搜索算法性能的途径 在保持局部搜索算法通用性和灵活性的前提下，以下方案有利于提高最终解 的质量： ( 1 ) 对大量初始解执行算法，再从中优选； ( 2 ) 引入更复杂的邻域结构，使算法能对解空间的更大范围进行搜索； ( 3 ) 改变局部搜索算法只能接受优化解迭代的准则，在一定限度内接受恶化 解。 第一种方案由于受到运行时间的限制，不可能对所有解施行，因而最终解仍 然是某个局部最优解；第二种方案需要对求解问题的透彻了解，而专注于某类问 题又将使局部搜索算法失去通用性而成为一种专用算法；第三种方案需要确定新 的接受准则，这使得局部搜索算法演变为一种新的算法一模拟退火算法。这是 本章后续重点讨论的内容。 2 4 模拟退火算法的背景 模拟退火算法是局部搜索算法的扩展，从理论上说是一个全局最优算法。模 拟退火算法源于对固体退火过程的研究，算法思想由m e t r o p o l i s 在1 9 5 3 年提出， 由k i r k p a t r i c k 在1 9 8 2 年成功应用在组合优化问题中。固体退火过程的物理性质 是模拟退火算法的物理背景，m e t r o p o l i s 接受准则使算法跳离局部最优自勺陷阱”。 浙江大学硕十学位论文第二章模拟退火算法 2 4 1 固体退火过程 2 4 1 1 固体退火过程的物理图象 在加热固体时，固体粒子的热运动不断增强，系统能量随温度升高而增大。 当温度升至熔解温度时，固体的规则性被彻底破坏，固体熔解为液体，粒子排列 从较有序的结晶态转变为无序的液态，这个过程称为熔解。其目的是消除系统中 原先可能存在的非均匀状态，使随后进行的冷却过程以某一平衡态为始点冷却 时，随着温度的徐徐降低，系统能量也渐渐减小，粒子运动渐趋于有序。当温度 降至结晶温度后，粒子运动变为围绕晶体格点的微小振动，液体凝固成固体的晶 态，这个过程称为退火。退火过程之所以必须“徐徐”进行，是为了使系统在每 一个温度下都达到了平衡态，最终达到固体能量最小的基态。 2 4 1 2 固体退火过程的统计性质 从统计力学的角度看，固体退火过程的统计性质服从如下的正则分布 2 2 1 ： p e e 卜而1e x “寺 ( 2 - 1 ) 麟p ( 二争) 称为b o l t 锄a n n 因子，e i 为能量，t 是绝对温度，k 是：b o l t z m a n n 常数o z ( t ) 为概率分布的标准化因子z 阶罩e x p ( 鲁) 这种分布给出温度t 时固体处于能量为e i 的微观态的几率。显然，固体处 于能量较低的微观态的几率较大。在温度降低时，那些能量相比最低的微观态最 有可能出现。当温度趋于零时，固体只能处于能量为最小值的基态上。 2 4 2m e t r o p o l i s 准则 1 9 5 3 年，m e t r o p o l i s 等提出重要性采样法，用下述方法产生固体的状态序列： 先给定以粒子相对位置表征的初始状态i ，作为固体的当前状态，该状态的能量 为e i ，然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小变化，得 到一个新的状态j ，新状态的能量是b i ，如果e i e i ，则该新状态就作为“重要” 状态反之，则考虑到热运动的影响，该新状态是否“重要”要依据固体处于 该状态的几率来判断。由式( 2 1 ) 可知，固体处于状态i 和状态j 的几率的比值等 于相应的b o l t z m a n n 因子的比值，即 p ( e j - e j 】 ( 2 2 ) 浙江大学硕士学位论文第二章模拟退火算法 f 是一个小于1 的数。用随机数发生器产生一个【o ，l 】区间的均匀分布的随 机数亭，若，宇，则新状态j 作为重要状态，否则舍去。 若新状态j 是重要状态，就以j 取代i 成为当前状态，否则仍以i 为当前状 态再重复以上新状态的产生过程。在大量迁移( 固体状态的变换称为迁移) 后， 系统趋于能量较低的平衡状态。 由式( 2 2 ) 可知，高温下可接受与当i ； 状态能差较大( 新状态能量较大于当前 状态) 的新状态为重要状态，而在低温下只能接受与当前解能差较小的新状态为 重要状态。这与不同温度下的热运动的影响完全一致。 上述接受新状态的准则称为m e t r o p o l i s 准则，相应的算法称为m e t r o p o l i s 算 法。 2 5 模拟退火算法 2 5 1 模拟退火算法的提出 设组合优化问题的一个解i 及其目标函数f ( i ) 分别与固体的一个微观状态及 其能量等价，令随算法进程递减其值的控制参数t 担当固体退火过程中的温度t 的角色，对于控制参数t 的每一取值，算法持续进行“产生新解一判断接 受舍弃”的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程，也就 是执行了一次m e t r o p o l i s 算法。这样就由固体的退火过程推演到组合优化问题 了，如表2 1 所示。 表2 - 1 组合优化问题与固体退火过程 t a b 2 1c o m b i n a t o r i a lo p t i m i z a t i o na n da n n e a l i n gp r o c e s so fs o l i d 组合优化问题固体退火过程 解 微观状态 目标函数 能量 控制参数t温度 迭代过程( m e t r o p o l i s 算法) 热平衡 m e t r o p o l i s 算法从某一初始状态出发，通过计算系统的时间演化过程，求出 浙江大学硕十学位论文第二章模拟退火算法 系统最终达到的相似状态，模拟退火算法从某个初始