（计算机系统结构专业论文）基于综合推理的绣花智能花稿设计的研究.pdf

摘要 在传统的绣花c a d 中，花稿设计需要花费大量的专业人员，使得设计周期 - ，_ _ _ - _ _ ，一_ - - - 。- 。一 长，效率低，跟不上市场和生产的需要。针对这些缺点，本文对利用计算机进 行花稿的智能设计做了一些研究。通过对花稿图案的分解、描述，生成特征图 元、图构件工程数据库，然后根据绣花图稿生成规则进行元素的替换、综合， 以生成各种新的花稿图案，并运用适当的人工智能模型对这些图案进行自动针 法生成。 a b s t r a c t i nt r a d i t i o n a le m b r o i d e r yc a d s y s t e m s , t h e 口r o f b s s i o n a l ss h a l ls p e n dam a s so f t i m eo ne m b r o i d e r yd r a f t sd e s i g n i n g ，s ot h a ti th a sl o w e f f i c i e n c ya n dc a r l ta d a p t t o p r o d u c t i o n i na l l u s i o n t ot h e s e s h o r t c o m i n g t h i sp a p e rs t u d i e s h o wt o d e s i g n e m b m i d e w d r a f t sa u t o m a t i c a l l yb yc o m p u t e r t h r o u g ha n a l y z i n ga n dd e s c r i b i n gt h e p a t t e m o fe m b r o i d e r y d _ r a n s ，c h a r a c t e r i s t i cm e t aa n de n g i n e e r i n gd a t a b a s ea r e c r e a t e d t h e nw e d i s p l a c ea n ds y n t h e s i z et h ee l e m e n t sa c c o r d i n g t og e n e r a t i o nr u l e st o b u i l dn e wp a t t e r n s a tl a s tt h es t i t c h e sm g e n e r a t e da u t o m a t i c a l l yb ye x e r t i n g c o r r e s p o n d m ga r t i f i c i a li n t e l l i g e n c em o d e l s 一、前言 花边工艺是一种国内外倍受青睐的工艺。近年来，计算机技术飞速发展， 尤其是c a d 技术的发展，使花边的设计如虎添翼。国内外花边c a d 的产品也 层出不穷。然而，传统的绣花c a d 产品中都存在着一些缺憾，例如花稿输入速 度不尽如人意，花稿的设计需要大量专业人员的参与，花稿图案的创新也是一 个困扰厂家的问题，既费时费工，又不易精确作业，不能适应国际市场的竞争 需要，特别不能适应外贸小批量，多品种，交货快等方面的要求。 为了解决这些问题，本文提出了基于综合推理的绣花c a d 智能花稿设计及 针法自动生成系统，希望对绣花c a d 的智能化作出一些有益的研究。 二、综合推理【5 】 知识获取一直是专家系统建造过程中的一个主要“瓶颈问题”。如何总结抽 取领域专家的经验，将其有效地表达为知识，并使相应知识库具有自学习能力， 对于提高系统的智能性至关重要。智能图案设计是一个充分体现人类形象思维 的c a d 领域，设计师的作图经验很难用普通的形式化方法表达。但也正是因为 其蕴涵着人类思维的跳跃性和不定性，无论从几何布局、色彩定格、元素选择 上都无定量的约束，也就是说新构图知识的生成本身就是一个约束很少的过程， 这就给新知识的生成提供了很大余地，使得由机器根据知识库中已有构图知识、 通过一定的推理机制来完成部分知识的学习和生成成为可能。综合推理是一种 新型的推理方式。综合推理模型非常适用于模拟基于形象信息的思维过程，这 一特点使得综合推理可以在图形图像领域得到广泛的应用。 推理是人工智能的一块基石。推理和搜索、约束满足一起被称为人工智能 问题求解的三大方法。推理的源头是演绎三段论，它利用两个正确命题之间的 关系推出第三个正确的命题。从这个源头出发研究出了各种推理方法。这些方 法的发展趋势可以分成如下几个方面加以观察。 逻辑学派在发展推理方法的过程中始终围绕着如何保持推理结论的正确性 这个核心。他们发展了非单调逻辑、可信度逻辑、时序逻辑、模糊逻辑、开放 逻辑等等。从而使得推理可以在部分事实错误、或暂时错误的情况下也能进行。 知识学派研究如何表达领域知识的同时也发展推理方法。他们发展了规则 基推理、语义网络推理、c a s e 基推理、模型基推理等等。随着知识表达和获取 研究的深化，以及问题求解范围的扩大，推理范畴从演绎扩大到归纳，以致于 类比。 基于图形图像的研究工作的深入也逐步参与发展推理方法的过程。这方面 的工作围绕着如何基于形象信息进行推理这一核心，并发展了空间推理、几何 推理、视觉推理等等。从而使推理能够在地图、三维形体和二维图像等信息上 进行。 分析推理的上述发展可以看出这样一种趋势：从严格的演绎逻辑出发，到 开放逻辑，到c a s e 推理，到类比推理，到视觉推理，推理呈现明显的松绑趋 势。为了适应越来越广阔的环境，处理越来越丰富的媒介，解决越来越复杂的 问题，推理技术不断挣脱束缚，向四面渗透、改造与拓展自己。推理的松绑趋 2 势使得推理逐步走向对思维的广泛模拟。 人类在设计过程中的思维方式，是比这些推理方式更加宽松的一种方式。 它完全可能同时考虑各方面情况，在质、量不相同的情况下，综合各个成分， 产生出新的想法，它可以利用旧的经验，也可能采纳仅仅是设想的成分，在头 脑中加工形成设计结果。因此，要更准确、更广泛地模拟思维，必须研究人的 思维过程中的综合能力。h a 。s i m o n 早在1 9 7 5 年就指出设计是一种以综合为特 征的问题求解，钱学森也认为从定性到定量的综合集成是思维科学的一个主要 方面。综合推理是对推理范畴的又一次松绑。 2 1 综合推理模型 综合推理的辅入是二个或二个以上表达，以及综合要求，输出是综合结果。 我们将输入的表达称为综合源，记为s ；将综合要求称为综合约束，记为c ；将 综合结果记为r ，并有定义如下： 定义1综合源( 简称源，记为s ) ，一个综合源s 是一个具有如下结构的信息表 达： s = p ，m ，f 其中：p 是部件的集合，p = p l ，p 2 ，p 。，它表示一个源由n 个部件构成。 m 是结构，它是一种描述n 个部件如何构成一个整体的方法。 在综合时，每个源都有一个影响场。源影响场f 的定义如下： 定义2 源影响场( 简称源场。记为f ) ，f 描述了源参加综合时，其影响力强度 的分布情况，f 由两部组成：f = f p ，f m 。 f p 是一个部件的场强函数的集合，f p 的每一个元素表达一个对应部件在综 合时的影响力大小的分布。f p = f p l ，f p 。f m 是一种结构的场强函数，它 描述源的结构在综合时的影响力大小分布情况。 按源场强度函数的不同，源场可以分为连续场和离散场。图1 示出一种离 散场，它只含0 ，l 两值。它表示该部件在综合时要么被保留，要么被删除。 综合推理的源数必须大于等于2 。这些源构成一个综合空间。 图1 定义3 综合空间( 简称空间，记为s s ) ，综合空间由参加综合的源叠加构成。综 合空间中的每一位置都是一个潜在的综合结果，记为s s ( x ，y ，曲。m 个源构成 的空间定义为： s s ( x ，y ，z ) = ( f p 0 ( x ，y ，z ) p 0 ，f m j 玛) j - i l - 】 构成一个空间的前提是所有的源都有相同个数( n 个) 的可对应部件。源的实 际部件数目与可对应部件数目可以不同。在这种情况下，可以用合并对应或重 复对应的方法来达到所要求的可对应部件数目。 基于上述概念之上，综合推理定义为： 定义4 综合推理( 记为s r ) ：是一种通过构造综合空间并在其中定位而获得结果 的推理方法。 定义4 描述综合推理的两个主要步骤：首先根据多个源构造一个综合空间； 然后根据综合要求在综合空间中定位。其中源与综合要求正是综合推理的两个 输入，综合空间的定位点正是推理结果，或者说是综合推理的输出。下面，我 们来研究综合推理的分类。 我们可以将综合推理分为正域推理和逆域椎理并定义逆域推理为： 定义5 源a 的逆( 正) 域综合推理：如果综合推理s r 的结果定位在源的逆( 正) 域，则称s r 为源a 的逆( 正) 域综合推理，否则称s r 为源a 的正( 逆) 域综合推理。 其中源a 的逆( 正) 域定义为： 定义6 源a 的逆( 正) 域：源a 的源场中场强度为负( 正) 值的部分称为源a 的逆( 正) 域，源场的其余部分称为源a 的i e ( 逆) 域。 4 源a 的逆域还可以被划分为“源8 关于源b t 的逆域”，“源f l 关于源b 2 的逆 域”，等等。逆域推理也可依同样细节。 综合推理又可以以场强函数的连续变化和离散变化的不同而划分为连续场 综合推理和离散场综合推理，并定义如下： 定义7 如果参加综合推理的全部源的场强函数都是离散的，则称这种综合推理 为离散场综合推理。否则，称为连续场综合推理。特殊地，如果全部源的场强 函数都是两值函数，则称这种推理为两值场综合推理。 两值场综合推理是一种以替换部件的方式进行综合的过程。以语言为综合 对象时，如诗人炼句、选韵就是一种两值的综合推理。两值场综合推理是一般 综合推理的一种极端特殊的情况。 2 2 综合推理特点 仔细分析上述综合推理的模型，可以发现它含许多与传统演绎和归纳推理 不同的特点。 综合推理的核心机制是集成各个源场，建立综合空间，而传统推理核心机制 则是蕴含、匹配和替换。传统推理机制的一个特征是在若干推理步骤之间形成 一条推理链，而综合推理由于可以在一个由各种场集成的空间中两维运动因 而可以形成一个推理面。如果说，传统的推理链呈现的是一种线型的推理形式 的话，那么综合推理面则呈现的是一种面型的推理形式。 和传统推理方式的离散性不同，综合推理可以呈现连续性。这种连续性既可 以体现在推理空间的连续上、又可以体现在推理对象的连续上。综合推理的这 种连续性和我们在想象中所体会到的思维的连续性十分吻合。 综合推理是一种生成性推理，而不是如演绎推理那样的判断性推理。构成综 合推理机理的核心不是对象值的真假，而是对象的结构。虽然归纳推理也是一 种生成性推理，但它不仅要求参加归纳的对象具有完全相同的结构，而且要求 各对象所含的部件具有兄弟关系。而综合推理则灵活得多，它只要求参加综合 的源具有可比的结构，和各源所含部件之间具有对应关系。综合推理的这种宽 松要求意义的重大，它使得各种范例和形状能够方便地进入推理，使得人工智 能学者爱不释手而又难以运用c a s e 推理得以方便地实现，使得推理从字符介质 进入形象介质，并在多媒体的领域中得到一种新发展。 综合推理是形象思维的重要操作之一。形象思维对综合与分析的依靠更重于 对演绎与归纳的依靠。这也是为什么在演绎与归纳的这条根上，形象思维难以 发展的原因。由此可知，综合推理之不同于演绎推理的一系列特点、也部分地 揭示了形象思维之不同于抽象思维的特点。 研究指出记忆中的极大多数常识都是以形象的形式存在，综合推理的模型进 一步指出了这些常识是如何参加推理的。和演绎推理相比，参加综合推理的源 只需要较少的形式化，我们不妨称之为弱形式化。对比之下，逻辑则是一种强 形式化。在弱形式化推理领域，表达的核心作用将削弱表达将根据目标与存 在的差异而自动生成。从强形式化走向弱形式化，将会成为人工智能发展的一 大趋势。 综合推理是一种多源推理，和归纳推理对各源的同一要求不一样，综合推 理不仅允许许多源变化多端，不仅能综合集成各源的特点。不仅能既在每一个 源的正域又在负域中推理，而且它的每个源场允许是连续的。因此综合推理含 有一个变化丰富、数目无穷的结果空间。这使它而且，综合推理也不同于类比 生成，它是类比生成的更高级形式。类比生成通常是面对一组具有一致性表达 的对象，对类比源的一些共同侧面进行生成性类比，而在综合过程中，综合本 身的含义就是指能在综合源的不同性质、观点之间进行斡旋、平衡，生成最佳 结果，举例来说，如果要求对红基调具有庄重感生成一种色彩，此时，一个源 是r 、g 、b 的符号性综合源，另一个是依赖感觉的主观评价，这对类比生成就 超出了其表达、推理的能力，因为类比生成的基础是类比源有共同的一致的表 达，从而保证生成结果也具有这样一种宏观规模，而现在提供的源横跨两个领 域的知识就必须使用综合的技术了。可以注意到，类比生成的( 7 1 1 ) 式的结果 是以部件的集合形成表达的，类比生成是在部件上进行的，部件的总装没有进 行生成性表达。当部件的总装也进行生成性表达时类比推理就上升为综合推 理。应该注意到，综合推理对应着分解推理，从一个完整要求分解到的各个知 识片段和前提约束虽有一致的表达，经过修改，根据具体情况而进行的生成性 过程，各个部件、约束、知识片段形成了不再统一的形式。它们可能是符号性 的，也可能是形象性的，可能是离散的，也可能是连续的，可能是空间性的内 容，也可能只是抽象性的描述。因此，综合推理在其生成性的任务完成之后， 更艰巨也更有意义的工作是将这种形式多样、内容丰富的部件再还原为一个整 体对象，给出综合的生成结果。因此，在综合性推理的模型中包含结构，类比 6 生成只是综合推理的一个特例，综合推理是一个更加广泛的范畴。自然也就更 加复杂。 2 3 基于综合推理的花稿图案设计 2 3 1 思想的提出 智能c a d 是a i 技术与c a d 技术相结合的产物。在智能c a d 系统中，最 基本的要素是知识，它直接影响到系统的性能以及功能的强弱。绝大多数智能 c a d 系统都有自己的一套知识表达、获取及学习系统。经过了十多年的发展， 目前已形成了几种较为成熟的智能c a d 方法：如基于规则的设计方法、基于框 架的设计方法、基于问题求解的搜索方法、约束满足的方法、基于c a s e 推理 的设计方法以及将设计师的设计经验提炼出来表达为知识的知识工程的方法等 等。 在上述方法的指导下，智能c a d 领域不乏成功的实用的系统。在一些系统 中，计算机确实可以模拟设计师的智能、来代替设计师的一部分工作，甚至可 以在某些方面大大超越设计师的设计能力，得到一些令人满意的结果。但是， 在智能c a d 领域研究至今，仍然存在着一大缺陷，那就是大量的设计工作过程 伴随的联想、灵感、直觉等形象思维活动过程，用至今的a i 技术都不能有效地 来刻划这种过程。而这些过程正是真正的智能和创造性体现的关键。因此，为 弥补这一缺陷，毫无疑问需要加强在认知科学方面对形象思维的深入研究，需 要深入探讨“智能”这一概念。美国的h o w a r dg a r d e n d e r 在其( f r a m e so f m i n d ) ) 一书中提出智能分为多种智能，其中包括逻辑一数学智能和其他各种智能。不 难看出，传统的a j 技术侧重于逻辑一数学智能，侧重于对抽象思维的研究，而 对其他方面的智能和思维模式则显得束手无策。 综合推理是一种全新的推理，它揭示了一种人们经常使用的形象思维过程 模型，在打破传统a j 推理的抽象思维模式的束缚方面作了一步重大尝试。也正 是由于基于形象信息，综合推理在图形、图像领域可以得到广泛应用，并将打 开智能c a d 的新局面。 2 3 2 图案的四要素 撇开图案的领域性，首先分析一下任意几张图案本身，看看它们在组成上 有没有什么共性? 不难发现：一幅图案首先可以被分为两个部分：背景图案及前 景图案。 背景图案是指一种布满整个图案的有规律的背景色、背景纹样等。例如从 上而下由红色渐变到白色的一种连续变化的色调和如图2 所示的某种纹样。 图2 某种纹样 前景图案是指除背景图案外的其余图案。它往往可以看成是由若干具有某种 色彩风格的于图案按照某种布局方法组合而成。 将一幅已知的图案划分为背景图案与前景图案的方法不是唯一的。同样，将 前景图案划分为若干子图案的方法也不是唯一的，这取决于划分人的艺术思维 方法。 尽管划分的方法并不唯一，但任意一幅图案总可以作如上划分。因此，可 以得到如下定义： 定义8 一个图案原型( p a t t e r np r o t o t y p e ) 为一四元组：p p = ( e 、b 、c 、w ) 。其中， e 为子图案集，即p p 的前景图案的某种划分，我们将子图案称为图元；b 为布 局，即各个图案( 或图元) 构成前景图案的方法；c 为图案的色彩风格；w 为图案 的纹理风格，包括背景图案及图元的各种特殊效果，也就是说，图案具有四要 素：图元、布局、色彩和纹理。 显然，一个p p 的c ，w 是唯一的，但可以有多组e 、b 的组合，但只要确 定了e ，那么b 也就确定了。但是，反过来，给出一四元组( e ，b 、c 、w ) 就能 够产生唯一一幅图案。即从( e 、b ，c 、w ) 一p p 是唯一的。那么，就可以从这条 路径考虑图案设计问题。 图案的这种定义方法更具有形象性，更适合于利用综合推理的模型进行图 8 案创作。 由综合推理模型可知，综合推理是一种通过构造综合空间并在其中定位而 获得结果的推理方法，而综合空间由参加综合的源叠加构成。 针对图案设计的特点，我们将参加综合的源进行分类，得到如下三个定义： 定义9 单要素综合：指参加综合的源属于同一种图案要素。 由于图案共有四要素，显然我们在图案设计中有4 类单要素综合：图元的 综合、色彩的综合，纹理的综合以及布局的综合。 定义1 0 双要素综合：指参加综合的源属于两种不同的图案要素。 从理论上说，根据排列组合规则，在图案设计中应该有c 净6 种双要素综 合，但其他要素与布局的双要素综合并无实际意义。 双要素综合一般在两个源之间进行。其中一个源提供一种要素，另一个源 提供另种要素。 定义1 1多要素结合：指参加综合的源多于两种不同的图案要素。 在图案设计中，多要素综合主要指图元、色彩和纹理的综合，但还未在本 实验系统中实施。 2 3 3 单要素综合模型 2 3 3 1 图元形状的综合 一、图形图元与图像图元 图元是图案创作的基本素材。图元可以分为两类：图形图元和图像图元。 图形图元和图像图元的区别如同图形( g r a p h i c ) 和图像( i m a g e ) 的区别。前者是矢 量结构，由几种基本笔划( 如多边形、圆、矩形、折线等) 组成，在数据结构上多 边形的折线用顶点坐标存储，圆用圆心坐标和半径数值存储，矩形用左上角和 右下角坐标存储；后者是点阵结构，无具体的笔划，在数据结构上用象素点坐 标和色彩值存储。 图形图元的输入一般来自某一个辅助软件，由设计人员借助输入设备( 数字 化仪、m o u s e 、键盘等) 描入；图像图元的输入一般则是将现成的照片或资料通过 扫描仪扫入，然后再借助辅助软件进行勾勒、去背景、色彩合并等处理。 图形图元的特点是构图简单、色彩变化小、存储量小；图像图元的特点则 9 正好相反，构图复杂、色彩丰富、存储量大。 在图案设计中，这两类图元相辅相成，缺一不可。在绣花c a d 中，图形图 元，如直线段、矩形、圆等，可以由鼠标、键盘输入，作为一种辅助；而图象 图元是主要的，它通过扫描仪将照片、图片、已有花稿实物扫入，再通过一定 的算法将其分割而成，并按一定规律存入工程数据库以供选用。 二、图元的获取 对于图形图元，我们已有现成的算法来得到；对于一般的图象图元，我们 可以采用阈值进行分割。 而对于绣花产品，由于其具有特殊的纹理特征，因此我们采用文献1 3 所介 绍的算法来分割花稿图案以得到图象图元。 1 、花边图像的特征【1 3 j 花边图像是花边实样通过扫描仪扫描产生的图像，由于花边工艺本身的，点， 花边图稿有以下特征：花边图像基本为单色二值图像；图像由许多相互邻接的 针法区域组成；各针法区域的排列无规律；各针法区域相接处无明显的边界； 针法区域内部均由有规律的针法组成有其独特的纹理特征。这些特征是我们采 用图像纹理分区技术进行研究的主要依据。 2 、纹理分区技术 2 1 图像分割与纹理分区 图像纹理分区属图像分割的范畴。图像分割是把一个图像分割成多个小区域， 使得每个小区域内部都是单一的。而且，这些区域又具有以下特点：不存在许 多小孔；相邻区域之间具有明显的特征值灰度和纹理形状；区域的边界不粗糙； 区域在空间位置上是精确的。 2 2 纹理分析和自相关函数 纹理是指在图像中反复出现的局部模式和它们的排列规则，很多图像纹理可 分解成众多纹理基元( 也称局部模式) ，这些基元n y , j 有一定规则，且反复出现。 纹理分析可以基于最小基元一像素灰度进行，建立纹理模型，这类纹理分析 方法叫作纹理的模型分析。另一种方法是将复杂的纹理图像通过特征抽取和分 割，得到诸局部模式( 基元，例如边缘) 和它们的属性( 例如边缘的方向) ，分析诸 基元间的关系，然后对纹理图像作出解释。这一类方法叫做纹理的结构分析。 本章中我们进行花边图像纹理分析所采用的是结构分析的方法。 l o 定义图像 f ( x i ，y i ) ；i ，j = o ，1 ，2 ，n 1 ) 的自相关函数。 n l 一1 ，( x 。，乃) 厂( t + x ，y ，+ j ，) p ( x ，y ) = = o j - o 这里o x l l ( ，0 y l l y 若x l l 【或y 1 b ，则f ( x l ，y 1 ) = 0 显然，当x = 0 ，y = 0 时，p ( x ，y ) 取最大值，记 d = ( x 2 + y 2 、1 陀 利用自相关函数p ( x ，y ) 随x ，y 大小变化的规律，我们就可以描述图像的纹 理特征。 若图像纹理较粗，p ( x ，y ) 随d 增加而下降的速度较慢；若图像纹理较细，p ( x ， y ) 随d 增加而下降的速度较快。随着d 的增加，p ( x ，y ) 会呈现某种周期性的变 化，这种变化反映了局部模式排列规则的稀疏或稠密程度。 2 3 灰度分布统计特征分析 任何复杂的图像我们总可以看成三维空间的一个曲面。局部模式的不同形式 和它们的种种排列规则反映在曲面上就是一个方向。相邻某间隔长度的一对像 素，它们各属于什么灰度范围，从我们感兴趣的某一图像区域来说，要求知道 具有这类属性的点对个数的分布规律，从这一观点出发，提出了灰度共生矩阵 的纹理分析方法。 一幅图像的灰度共生矩阵反映了图像灰度关于方向、相邻门限和变化幅度等 的综合信息，是分析图像局部模型和它们排列规则的基础，由它也可进一步提 取描述图像纹理的一系列特征。 假设一幅图像f 的x 方向像素总数为n 。，y 方向像素总数为_ n ，。将图像灰度 作归并，其最高灰度级是第n 。级， 记： l x = 1 ，2 ，n 。) b 2 1 ，2 ，n y g 5 l ，2 ，n g 我们把待纹理分析的图像f 理解为从l 【l v 到g 的一个变换，也就是说对 l 。k 中的每一个点，对应一个属于g 的灰度。 定义方向为t ，间隔为d 的灰度共生矩阵为( p ( i ，j ，d ，t ) p ( i ，j ，d ，t ) 表示矩阵第i 行第j 列元素，其中( i ，j ) g g 间。，4 5 。，9 0 。，1 3 5 。，角度为o x 轴为起始，逆时针方向计算，对不同的 t 矩阵元素的定义为： p ( i , j ，d ，0 。) 群 代1 ) ，( m ，n ) ( l y + ix ) + ( l y + l x ) ) | k - m = o ；j 1 - n l = d ；f ( k ，1 ) - - i , f ( m , n ) j p ( i j ，d ，4 5 。) 爿 ( k ，1 ) ，( m ，n ) ( t , y + l x ) + ( l y + l x ) i ( k i t i = d ，1 - n = d ) o r ( k - m = 一d ，l - n = - d ) f 【k 1 ) = i ，f ( m , n ) - - - j p ( i j ，d ，9 0 。) 爿 ( k ，1 ) ，( m ，n ) ( l y + l x ) + ( l y + l x ) i i k m f d ，l n = o ；f ( k ，1 ) = i ，f ( m ，n ) - - j p ( i , j ，d , 1 3 5 。) 刊 ( k 1 ) ，( m ，n ) ( l y + l x ) + ( l y + l x ) i ( k - m = d ，1 - n = 一d ) o r ( k - m = 一d ，1 - n = d ) f ( k ，1 ) = i ，f ( m ，n ) - - j ) 记号群 x 表示集合x 的元素数。矩阵( p ( i ，j ，d ，t ) ) 的第i 行第j 列元素表 示所有t 方向，相邻间隔为d 的像素中有一个取i 值，另一个取j 值的相邻对点 数。 3 、花边图像的分割 花边图像有其独有特点。我们分析了花边图像的特点，发现此类图像由各种 已知的针法有规律的组合而成；整个图像由多个局部区域组成，而每个区域仅 由一种确定针法组成。因此，花边图像的纹理分区就是要找出有机组成图像的 局部区域来。我们系统中的纹理分区算法采用了四叉树结构，而把以往的分区 步骤：“分解一合并”改为“分解一初合并一再合并及连通”。经过这一改进， 我们的算法对以黑白二值为主的花边稿图像的纹理分区取得了满意的效果。 3 1 花边图像的分解 花边稿图像的分解就是建立一颗四叉树的过程。为了防止计算量过大和四叉 树生成过多的结点，我们先按一定大小平均分解图像。平均分解大小一般人为 给定1 0 0 2 0 0 个象素单位。这样，一幅图像就被均分为大小相等的小方形。当不 能整除时，便产生长宽比均等的小矩形，这些小方形和小矩形统称为“局部区 域”。为了尽可能快速分解局部区域，我们引入了“重心”这个能充分体现灰度 分布的概念。当局部区域的面积大于最小可分面积( 人为给定) ，且内部象素非全 0 或全“1 ”时，就须计算重心的位置，以进一步分解。重心的位置计算公 式如下： 1 2 邝，胪if ( i ，) + ， g a r _ x ：= 号等一g a r _ y = 号艺一 ，( f ，)厂( f ，) j = lj - 1i - 1j la 其中币0 ) 代表二维局部区域第( i j ) 坐标的像素 值，g r a v x ，g r a v - y 分别为重心的x ，y 方向的坐标，n ，m 是局 部区域的宽度和高度。d f 厂同 删7 83 f 雨 1 j 【j _ j b c 局部区域均分为3 37 的9 个区域，如图3 ：图3 比较重心落在局部区域的哪个编号内。如果落在0 号区内，说明区域内图像 内容集中在0 号区附近。这时，分解点在区域内距a 点( 2 + g r a v x ，2 * g r a v y ) 处。 余者类推。当重心落在8 号区内时，说明局部区域内图像内容基本均匀分布。 这时要作出是否分解的判断。考虑到实际中花边稿的灰度不是零散分布的，而 是连续分布的。所以，重心离局部区域四个边的间距中，只要存在一个大于给定 阈值，就须再分割。否则，结束分割。 3 2 分解区域的初合并 经过分解之后生成了一颗四叉树。树的叶子包含了花边稿图像的分解结果， 包含图像的平均灰度及所属区号。分解后的区域号全为0 ，表示所有区域均不属 于任何一个纹理分区。若有叶子区域号不为0 ，表示该叶子属某一纹理分区。初 合并的过程：从树中找一个叶子，它的区域号为0 ，平均灰度值不为0 ，给它 赋一个唯一的标号。以该叶子为起点找与其相邻四周( 上下左右) 是否有满足初 合并条件的区域。若有，则将该块亦赋同一标号，并把该叶子结点推入一个队 列的尾部，直到这个起点叶子的四周找完。从前面的队列头部取一个叶子结 点，对它重复2 的操作。反复做直至队列为空。这表明找完一个纹理分区。 重复操作，直至所有的叶子结点均经历过初合并。 初合并的条件是两个相邻块问的平均灰度值差的绝对值，小于某一阈值。这 个阈值设置得越小，初合并就越严格，获得的纹理分区就越多，但需以速度为 代价。因此，纹理分区好坏与闽值设置有直接关系。 初合并后生成一个纹理分区链表，表中每个表日包括该区的平均灰度值，面 积和区号。 此处给出一个寻找邻域可并块的算法，以递归式简化表达，实际程序中应该 以非递归的方法实现。因为从花边图像生成的四叉树往往层次较多，递归实现 占用，空间大，速度慢。递归算法如下： n o d e + f m g - n e i g h b o r ( p , d ) 产寻找结点p 在垂直或水平方向的同等大小的邻域，d 代表方向+ n o d e+ p ： d i r e c t o r d ： r e t u r n ( s o n ( i fa d j ( d ，s o n t y p e ( p ) ) t h e n f i n d n e i g h b o r ( f a t h e r ( p ) ，d ) e l s e f a t h e r ( p ) r e f l e c t ( d ，s o n t y p e ( p ) ) ) ) ； 其中函数s o n ( p , 1 ) 表示p 的四个子结点，1 表示子结点所在的象限( 上下左右) 。 f a t h e r ( p ) 表示p 的父结点。 s o n t y p e ( p ) 表示p 所在的象限。 a 由( d ，1 ) ，在方向d 和象限1 是否有邻域。 r e f l e c t ( d ，1 ) 产生一个结点，在象限1 。 3 3 再合并及连通算法 再合并是将初合并之后生成的纹理分区小区域合并成为大区域。这里我们依 据多次实践，也设一个m i n a r e a = 1 1 0 0 个象素单位的阈值，以判断是否属小区 域。 再合并的过程是：从分区链表中找出一个面积小于等于m i n a r e a 的结 点，获得其区号。从四叉树中找出与该片区域相邻的区域，把其中的p r i o r i t y 值最大的区域合并图1 到该区域中去，面积相加。重复直至链表中所有 结点的面积均大于m i n a r e a 。 p r i o r i t y = 0 7 + 区域平均灰度+ 0 3 + 区域面积 至此，我们的纹理分区已经完成。以下给出一个连通算法，使散布在四叉树 各叶子结点上的相同纹理分区连成一个闭环的区域。 以两个矩形连通的情况为例。如图4 ： 图4 2 1 4 把b 矩形连入a 矩形中去。a 链表为： 一巨丑巨丑臣三日 至卫 b 以有序顶点数组表示：( ) 【5 ，y 5 ) ，( x 6 ，y 6 ) ，( x 7 ，y 7 ) ，( x 8 ，y 8 ) ； 算法思想如下： 找出b 矩形的哪一条边与a 相交 根据相交边号，调整b 数组顶点次序 检查b 矩形中顶点是否与a 中顶点重合，若有则去掉b 中顶点。 若经过以上3 步之后，b 数组非空，按数组次序生成结点连入a 链表。 其中b 数组经调整后，从相交边结束点开始到相交边起始点结束。即得： ( ) ( 7 ，y 7 ) ，( x 8 ，v 8 ) ，( x 5 ，y 5 ) ，( x 6 ，y 6 ) 。 算法从略。 连通结果如图5 所示： 5 e 2 3 + 卧卧日吁 日卧日圃 图5 现在，获得了以矢量表示的针法区域。就可以以这些封闭区域为单位，对区 域内针法进行识别最终实现针法自动填充。 4 、实例 以上的思想和算法以程序实现，即得到以下结果，其效果基本令人满意见图 6 、7 、8 、9 。 图5倒9 三、图元的综合 综合推理的两个主要步骤为：( 1 ) 根据多个源构造一个综合空间；( 2 ) 根据综 合要求在综合空间中定位。其中源与综合要求是综合推理的两个输入，综合空 间的定位点正是推理结果，或者说是综合推理的输出。 进行综合推理的必要条件是必须有两个以上的源，且所有源都有相同个数m 个) 的可对应部件。当然，源的实际部件数目与可对应部件数目可以不同。在这 种情况下，可以用合并对应或重复对应的方法来达到所要求的可对应部件数目。 因此，根据综合推理模型，要进行图元形状的综合，首先必须确定参加综合 1 6 的每个图元的部件，并为它们建立相互的一一对应关系。 在实验系统中，我们采用交互的方法完成部件的分解与对应。从而建立一 个综合空间，完成综合推理的第一步骤。 综合要求则可以由用户输入，一般是一些权值，对应每个源的每个部件都 有一个权值，说明每个源的每个部件参加综合时的影响力( 1 i p 场强) 。 设有m 个图元参加综合，每个图元有n 个部件，分别记为f p i l ，p 1 2 ， p l 。) ， p 2 1 ，p 2 2 ，p 2 。) ， p m l ，p 帕，p 。) ，它们对应的权值分别记 为： w t l ，w 1 2 ，w l n ) ， w 2 1 ，w 2 2 ，w 2 n ) ， w m l ，w l i l 2 ， w 。 ，则权值满足： rw l l + w 1 2 + + w l n = l iw 2 1 + w 2 2 + + w 2 = 1 卜 。j 手形啦扣”+ w m = l 也可以不规定综合要求，由系统自动在综合空间中寻找一定位点，得到一种 结果，然后由用户对结果进行评价，好的保留，差的删去。因此，同样的源参 加综合，由于无明确的综合要求，可以得到许多解，这些解无论好坏，都是一 种综合结构，当然，系统中可以设定若干评价条件，以防止解的无限性。 例如，我们让一朵玫瑰和一朵牡丹进行综合，将玫瑰和牡丹都按花的结构 分解为 花瓣、花芯、花枝、花叶) ，可以得到许多既像玫瑰又像牡丹的花朵。 显然，通过综合推理，我们可以以有限的几个图元为基础，滋生出许多新 的图元，大大丰富图案创作的素材。 2 3 3 2 色彩的综合 一、图像颜色分割【l 2 j c a d 系统首先通过图像扫描仪将小样稿转换为数字图像，然后经过编辑、 修改及相应工艺处理，最后输出纹板、胶片及图纸。这些c a d 系统的小样稿一 般都由包含几种或几十种彩色或灰度的颜色( 称为样稿颜色，简称样色) 块组成。但 由于通常使用的图像扫描仪其颜色分辨率高达2 2 4 种，设备本身还会产生热噪 声，因此，经过图像扫描仪数字化输入计算机的小样稿图像，会出现许多样色 以外的颜色。如何对包含大量杂乱颜色的小样稿图像进行颜色分割以提取样色， 获得小样稿的样色图像，就成为c a d 系统要解决的关键问题，它类似于全真彩色 图像的颜色量化( 或颜色压缩) 。目前，已有方法可分为两大类：一类是均匀量化， 即对应的调色板颜色均匀分布，这种量化方法对颜色分布不均匀的彩色图像就 无能为力了；另一类是统计法，它通过对彩色图像中颜色出现频数的统计，取 得使用频率最高的样本颜色，以此作为图像的调色板，这种方法使用较多。在统 计法基础上，又出现了几种变形方法，包括面向图像的调色板技术、面向视觉 的调色板技术及基于磨光技术的图像颜色分割算法等。这些方法都是在一维颜 色直方图的基础上，统计选取使用频率最高的颜色作为样色。当在小样稿图像 中不出现样色以外的杂色或噪声时，这些方法可以使用，但在实际的小样稿图 像中常包含有大量样色以外的杂色或噪声，处理结果会使在小样稿图像中包含 较少像素点的样色块被量化掉，而占像素点数量较多、随机分布在图像中的杂 色被保留下来。这种现象出现的原因是，由于传统统计法仅考虑了颜色出现频 数的分布，而未考虑颜色的空间分布，所以其结果杂色取代了样色。为解决这 个问题，文献1 2 引入二维直方图，即在考虑一维颜色直方图的同时，也利用颜 色的空间分布信息，采用模糊聚类方法，滤掉了孤立噪声点颜色和随机分布的杂 色，聚类分割出了样色。实验结果及实际应用都证明了新方法的有效性。 1 、基于二维直方图的颜色模糊聚类 小样稿图像颜色分割的过程包括中心色的确定和颜色归并。由于图像扫描仪 及其噪声干扰的作用，所以基于一维直方图的传统统计法不能获得满意的颜色 分割结果，往往还会失去某些样色而保留一些杂色。为解决此问题，首先建立 颜色的二维直方图，然后再利用模糊c 均值( f c m ) 聚类算法获到小样稿图像各像 素点的隶属度，据此得到中心色和分割限，实现颜色的分割与归并。 1 1 二维直方图的建立 若小样稿图像j ( m ，甩) 的颜色数及大小分别为l 和n n ，由其采用3 x3 或5 x 5 点阵平均得到的平滑图像为h ( m ， ) ，其大小和颜色数与原图像相同。设s ( 切 为原图像中颜色为邓专攻m ，n ) 】及平滑图像的颜色为，【嘲( m ，蝴的像素点个数，则 由此获得的二维直方图为 p ( i d ) 。器 ( 1 ) 这样就建立了既反映图像中各颜色出现的频数分布，又体现图像的空间信息 的颜色一平滑颜色频数分布的二维直方图。 1 2 f c m 聚类算法 设j ，- 缸l 尥， ) 艘为任一有限数据集合，”为数据项数。整数c 为类别 数，2 c 胛。隶属度矩阵u 兰 蝴。满足u j k 0 ，1 和e 。1 ，vk 。v = v l ，v 2 ， 艘为c 个聚类中心集合。f c m 聚类准则函数为 厶( 以功= n l 靠，1 历 一 = li ；l ( 2 ) 式中d ：= l l x , 一v , 1 1 2 ，靠为欧氏距离。为了获得数据集合x 的c 类最佳划分， 可通过如下迭代优化算法求得使厶( u v ) 一m i n 的u 和阮 ( 1 ) 确定聚类类别数c ( 2 c ”) 和加权指数珊( 1 矾 + ( x i 2 。一x 0 2 ) + + i n m 一x o m ) 在线段l 2 中依次插入点x 1 1 ，x 2 1 ，x i l 1 ，l ，x 1 2 ，x 2 2 ，x i 2 2 ，2 ， x i n ，x 2 n ，x i n _ l n ，满足： ! 二丝业：墨2 1 二墨! ! 一一丝生1 二些! ：墨1 2 二墨丝：墨丝二墨丝一一 x l l _ x 0 lx 2 ，一x 。，x 帆。一x “z ：一x 。：x ：一x 。2 坚! 二墨型! 一一墨! ! 二墨业：丝盐二丝! ! x 。：一x 。：x 。一x 。x ：。一x 。 一x 。一x 。一厶 x m , n - - x 厶 增加色彩值c l l ，c 2 1 ，c i l 1 ，l ，c 1 2 ，c 2 2 ，c n 1 ，2 ，c i n ，c 2 n ， c i 。山，满足 c l l = c 2 1 一c i , 11 = c o l ； c 1 2 2 c 2 2 = 一c u 。1 , 2 0 2 ； c i n = c 2 n s ：o oo = c i n 1 n o i i 分别将线段集l l 和k 作为两个综合源，即l i = p l ，m 1 ，f l ，f i = f l p i ， f l m l ) ，p 1 = x 0 1 ，c o l ，x n ，c i ，x i ，1 ，x 0 2 ，c 0 2 ，x 1 2 ，c 1 2 ，x ， x o n ，c 0 n ，x l n ，c i n ，x i n ，n ) ，l 2 = p 2 ，m 2 ，f 2 ) ，f 2 = f 2 p 2 ，f 2 m 2 ，p 2 = x o l ， c o l ，x n ，c n t t ) ( i l 1 - ) ( 0 2 ，c 0 2 ，x 1 2 ，c i 2 ，x i 2 2 ，x o n ，c 0 n ， x i n 。 ，分别指定f i p l ，f 2 p 2 和f l m l ，f 2 m 2 ，就可以得到一种综合结果。 我们知道，图像图元实际上是一系列水平方向线的组合，而图形图元也可以 用几何方法来求得它的每一水平方向线的线段端点坐标。这样只要找到一个两 者的水平方向线之间的对应关系，就可以反复使用上述模型来实现色彩和形状 的综合了。这个对应关系可以利用两者的水平方向线数的比例关系来实现。设 s l 水平方向线数为n l ，而s 2 的水平方向线数为n 2 ，则s 2 的第i 条线对应的是 s 1 的第i * n i n 2 条线。 根据上述讨论，我们实际上已经在最简单情形的模型基础上建立了一个整 体上的综合图像图元色彩和图形图元形状的模型。这个模型经过推广，可以适 用于图像图元的色彩和形状的综合、图形图元的色彩和形状的综合及图形图元 的色彩和图像图元的形状的综