（计算机应用技术专业论文）基于多核处理器的景像织物cad设计.pdf

学位论文的主要创新点 l l l l r l f l r l l f l 删i i j 川f j f f y 18 7 r | | 1 8 l i i i i l 9 i i i i i 拶芗。 一通过对粒子群优化算法的研究，将粒子群优化算法成功地 应用于颜色量化算法之中，并运用0 p e n m p 多线程并行技术，设计了 并行粒子群颜色量化算法。该算法融合了粒子群优化算法的全局搜索 特点，克服了传统颜色量化算法的缺陷，充分发挥多核处理器的运算 能力，克服了粒子群颜色量化算法运算时间长的不足。 二 在并行粒子群颜色量化算法的基础上，结合相关的纺织知 识和技术设计并实现了基于多核处理器的景像织物c a d 软件，该软件 能够在充分发挥多核处理器的前提下，对真彩色景像图像进行并行粒 子群颜色量化，而后自动生成相对应的纺织物组织图，最后对织物组 织图的纺织效果进行模拟仿真。 摘要 基于多核处理器的景像织物c a d 软件已经成为纺织领域的一个重要研究方 向，基于多核处理器的景像织物c a d 软件运用粒子群颜色量化算法以及o p e n 多线程并行技术有效的解决了真彩色景像图像在机织织物上表现织物组织图的 设计问题，具有实际生产意义。 粒子群颜色量化技术融合了粒子群优化算法的优点，避免了传统颜色量化算 法的不足，能够在尽可能地接近原始图像的前提下，大幅度地减少了重建图像的 颜色数目，解决了真彩色图像颜色数目与机织设备经纬线颜色数目差距较大的问 题，在此基础上运用o p e n 多线程并行技术充分发挥多核处理器的数据处理 能力，快速设计出相对应的机织织物组织图并模拟仿真，提高了工艺设计人员的 工作效率。使用c + + 语言以及o p e n 多线程并行技术编程实现了基于多核处 理器的景像织物c a d 软件，通过对算法以及软件的实际测试，验证了基于多核 处理器的景像织物c a d 软件的可行性及有效性。 关键词：景像织物c a d ：并行粒子群颜色量化；o p e n a b s t r a c t s c e n ef a b r i cc a ds o f t w a r eb a s e do nm u l t i - c o r ep r o c e s s o r sh a sb e c o m ea l l i m p o r t a n tr e s e a r c hd i r e c t i o no f t h ef a b r i c t h i sc a d s o f t w a r eu s e st h ep a r t i c l es w a r m o p t i m i z a t i o n ( p s o ) c o l o rq u a n t i z a t i o na l g o r i t h ma n do p e n m pp a r a l l e lm u l t i t h r e a d e d t e c h n o l o g ye f f e c t i v e l ys o l v e st h et r u ec o l o rs c e n ei m a g e si n t h ep e r f o r m a n c eo f w o v e nf a b r i co nt h eo r g a n i z a t i o nc h a r to ft h ed e s i g np r o b l e m ，w i t ht h ea c t u a l p r o d u c t i o no fm e a n i n g t h ep a r t i c l es w a r mo p t i m i z a t i o nc o l o rq u a n t i z a t i o na l g o r i t h mt e c h n o l o g y c o m b i n e st h ea d v a n t a g e so fp s o ，t oa v o i dt h et r a d i t i o n a ll a c ko fc o l o rq u a n t i z a t i o n a l g o r i t h m ，c a nr e d u c es i g n i f i c a n t l yt h en u m b e ro fc o l o r si nt h ei m a g er e c o n s t r u c t i o n u n d e rt h ep r e m i s eo fr e s t o r i n gt h eo r i g i n a li m a g ea sm u c ha sp o s s i b l e ，r e s o l v et h e p r o b l e mb e t w e e nt h en u m b e ro fc o l o r si n t h et r u ec o l o ri m a g ea n dt h en u m b e ro f l a t i t u d ea n dl o n g i t u d el i n e sc o l o ro ft h ew e a v i n ge q u i p m e n t o nt h i sb a s i s ，w i t ht h e u s i n go fo p e n m pp a r a l l e lm u l t i t h r e a d e dt e c h n o l o g y , p l a yd a t ap r o c e s s i n gc a p a b i l i t i e s o fm u l t i - c o r ep r o c e s s o r s , r a p i dd e s i g no fw o v e nf a b r i c sc o r r e s p o n d i n go r g a n i z a t i o n c h a r ta n ds i m u l a t i o n ，i m p r o v et h ee f f i c i e n c yo fp r o c e s sd e s i g ns t a f f u s ec+ l a n g u a g ea n do p e n m pp a r a l l e lm u l t i - t h r e a d e dp r o g r a m m i n gt e c h n i q u e s f o rs c e n e f a b r i cc a ds o f t w a r eb a s e do nm u l t i - c o r ep r o c e s s o r s t h r o u g ht h ea c t u a lt e s t , t h i s c a ds o f t w a r et u r n so u tt ob ef e a s i b l ea n dv a l i d k e y w o r d s ：s c e n ef a b r i cc a d ；p p s oc o l o rq u a n t i z a t i o na l g o r i t h m ；o p e n m p 目录 第一章绪论l 1 1 机织c a d 发展现状1 1 2 课题的研究背景2 1 2 1 机织织物结构设计2 1 2 2 数字图像颜色量化一3 1 2 3 粒子群优化算法4 1 2 4 多核处理器并行处理4 1 3 课题的研究意义5 1 4 论文的组织结构5 第二章景像织物7 2 1 织物的概念及分类7 2 2 织物结构7 2 3 织物组织8 2 4 景像织物9 2 5 本章小结l l 第三章粒子群颜色量化1 3 3 1 粒子群算法1 3 3 1 1 粒子群算法的相关背景1 3 3 1 2 基本粒子群算法1 4 3 1 3 p s o 与其它进化算法比较1 6 3 2 粒子群颜色量化算法设计1 6 3 3 粒子群颜色量化算法具体实现1 8 3 3 1 粒子群颜色量化实现的整体架构1 8 3 3 2 粒子的初始化1 9 3 3 3 粒子速度与位置更新2 0 3 3 4 粒子的适应度值2 1 3 3 5 粒子个体最优及全局最优2 2 3 4 粒子群颜色量化与传统颜色量化的比较2 4 3 5 本章小结2 6 第四章并行粒子群颜色量化2 7 4 1 多核处理器2 7 4 1 1c m p 结构2 8 4 1 2 两种典型的c 卿2 9 4 2 0 p e n m p 并行编程技术3 1 4 2 1o p e n m p 运行原理3 2 4 2 2 0 p e n m p 与编译器结合3 3 4 2 3 0 p e n l 胛编译指导语句3 3 4 2 4 0 p e n m p 子句3 7 4 2 5 0 p e n m p 运行环境设置3 9 4 2 6 0 p e n m p 调度算法4 0 4 2 7 0 p e n m p 优化4 l 4 3 并行粒子群颜色量化算法4 2 4 3 1 并行粒子群颜色量化算法的基本思路4 2 4 3 2 并行粒子群颜色量化算法的具体实现4 4 4 4 实验对比4 5 4 5 本章小结4 7 第五章景像织物c a d 软件4 9 5 1 基于多核处理器的景像织物c a d 软件的总体设计4 9 5 2 软件设计5 0 5 2 1 软件功能设计5 0 5 2 2 图像处理模块5 l 5 2 3 织物组织图模块5 4 5 2 4 织物组织图模拟仿真模块5 6 5 3 软件运行5 7 5 3 1 图像部分5 7 5 3 2 组织图部分6 0 5 3 3 仿真部分6 2 5 4 本章小结6 3 第六章总结与展望6 5 参考文献6 7 研究生期间发表论文及参加科研情况说明7 1 致谢7 3 第一章绪论 1 1 机织c a d 发展现状 第一章绪论 随着计算机科学技术的迅猛发展以及人工智能技术的进步，计算机的使用已 经普遍渗透到社会、科学、生活、艺术等多个领域。计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，c a d ) 已为广大工程技术人员所熟悉，c a d 的应用水平不仅是衡 量企业产品开发、设计、制造能力和技术先进性的重要标志，更进一步影响着企 业在激烈的市场竞争中的生存空间和发展潜力。在2 0 0 1 年美国未来学杂志评 测报道中，c a d 技术则被列为2 1 世纪前2 0 年内对经济和社会发展最有影响的十 三项关键技术之一幅1 。 计算机技术发明之前的机织织物设计工艺主要是通过工艺技术人员手工完 成的，存在劳动强度大、生产效率低、工艺过程复杂、产品加工逆转性差等缺点， 因而一直成为机织织物设计与生产的瓶颈，在生活、生产节奏日益加快的今天已 经不能满足市场发展的需要口1 。 机织c a d 技术正是利用计算机强大的计算功能和高效的图形、图像处理能 力，改造传统的机织设计工艺，实现了机织设计的自动化，提高了工作效率，降 低了生产成本，缩短了产品的研发周期，提高了产品的市场竞争力。 国外机织c a d 系统的开发时间比较早，具有代表性的有德国g r o s s e 公司j a c 系统、英国b o n a s s 公司的c a p 系统、美国v i s i b l es y s t e m s 公司的系统、美国 的m e a v e y a k e 系统以及斯洛文尼亚的a r a h v e a v e 系统等。 国内从2 0 世纪7 0 年代开始也有一些科研生产机构开发了c a d 系统，如浙江 大学经纬自动化有限公司研制开发的j c a d 系统等。 在使用了机织c a d 系统后，机织织物已经能够在很短的设计周期内将简单色 彩的图像、图形通过织物结构、织物组织图十分便捷地呈现在人们的眼前。然而， 伴随着数字科学技术的进步以及计算机技术的快速发展，越来越多的图像采取数 字格式保存起来，这些数字图像细致的描绘了自然风景和人物肖像，但是，随之 而来的问题是：图像描绘的越细致，其颜色数量也极具增加，从最开始的几种颜 色增加到如今的1 6 0 0 多万色，怎样把这么色彩丰富的景像图像通过机织c a d 软 件进行快速设计，并用织物表现出来成为了一个有待解决的问题。 1 天津工业大学硕士学位论文 1 2 课题的研究背景 近年以来，计算机辅助景像织物设计( 景像织物c a d ) 已经成为织物设计专 业人员、相关学者以及相关企业所关注的研究课题。景像织物c a d 主要涉及的专 业技术包括：机织织物结构设计、数字图像颜色量化、粒子群优化算法、多核处 理器并行处理技术等方面。下面通过对各种技术进行简要介绍，阐述当今景像织 物c a d 这一领域的研究进展。 1 2 1 机织织物结构设计 景像织物c a d 最根本还是要对机织物进行设计。首先，我们要了解什么是“织 物”；将纤维纺制成纱线或丝线，再编织而成的产品，称为纺织产品，一般把纺 织产品统称为织物h 1 。其中，在织机上加工而成的织物称为机织织物，例如各类 棉织物、毛织物、丝织物和化纤织物等。 在纺织产品中，机织织物占得比重最大，本论文所研究的景像织物c a d 软件 就是针对机织织物产品设计。 机织物一般由经、纬两个方向的纱线或长丝交织而成。它的整体结构特点是： 外表呈平面型板状，经、纬两向结构重复交织，一般结构单一，但也可以是几层。 机织物的结构了解之后，还要进一步研究在机织物的结构中每根经线和每根纬线 具体的交织方法，研究并设计机织物的结构内每一根经纬纱线的具体交织方法是 决定机织物外观的重要基础。 机织物的经纬纱的交织规律一般用织物组织图来表示，大多采用方格表示法 哺1 。一般使用带有格子的意匠纸来绘制织物组织图，其纵行格子代表经纱，横行 格子代表纬纱。每个格子代表一个组织点，当组织点为经组织点时，将该格子填 黑，反之，纬组织点则空白该格子。传统的组织图绘制方法是采用人工一个格子 一个格子的绘制经纬组织点，即耗费人力资源，也容易造成错误，并且效率低下 严重影响生产进度。 然而，在绘制织物组织图之前，还有一部工作要做：标出经纬纱的排列顺序。 对于景像织物由于其颜色十分丰富，所以我们采用多经多纬织物结构，既三种或 三种以上的经线和三种或三种以上的纬线相互交织而成的色彩富丽的彩色织物 h 1 。可是，我们要织造的图像拥有1 6 0 0 多万种颜色，每一行或者每- - n 像素点 都拥有极多的不同的颜色，但是，目前用来织造机织物的剑杆织机一般只支持8 种不同颜色的纬线，在特定的要求下最多达到1 6 种颜色，远远少于图像中的颜 色数量，这时我们需要引进数字图像颜色量化技术来解决这个问题。 第一章绪论 1 2 2 数字图像颜色量化 要将1 6 0 0 多万种颜色的2 4 位真彩色图像，转变为用几种或十几种颜色来重 建图像，并做到尽可能的还原源图像，我们首先想到的就是运用颜色量化技术对 源图像进行数字图像处理。 颜色量化属于数字图像处理技术中的一种基础技术，是指由一个大颜色空间 集合到一个小颜色空间集合的映射过程，根据所选择的k 种最优颜色建立目标调 色板，并运用目标调色板重建图像，使所得到的重建图像尽可能贴近源图像，达 到失真度最小晗。 颜色量化是通过两部分来实现的：第一部分是根据相关的约束条件选择合适 的目标调色板：第二部分是颜色映射，用目标调色板的颜色代替源图像中像素点 的原有颜色，得到颜色量化后的重建图像。而其中目标调色板的选择是决定重建 图像质量的重点步骤u 引。 运用数字图像处理技术中的颜色量化技术将将1 6 0 0 多万种颜色的2 4 位真彩 色图像颜色量化为几种颜色，传统的颜色量化方法是将图像中的颜色出现的频率 排在前几十种的作为颜色量化后最终保留的颜色，而其他频率较低的颜色按色差 相近原则进行归并。该方法存在明显不足，颜色量化后图像的某些局部细节，由 于该色彩使用频度较少，而被其他颜色所代替，造成关键细节丢失，颜色量化后 的图像质量不够理想。 。传统的颜色量化算法包括以下几种： 1 ) 中位切割法：将颜色空间立方体平均分割成k 个小长方体，每个小长方 体内包含同等数量的像素，并且选择小长方体内的中心点颜色作为该小长方体内 所有颜色的代表值，最后汇总所有k 个小长方体的颜色代表值组成目标调色板。 尽管运用中位切割法得到的重构图像层次感较好，但是对局部细节的处理比较模 糊。 2 ) 中值裂分法：选取源图像像素点中rgb 三原色分量方差最大的分量中 值做为裂分标准，将源图像的颜色空间不断地分裂成较小的颜色空间，当达到约 束条件的k 个小颜色空间时，汇集各个较小颜色空间中心点的颜色做为目标调色 板。虽然，中值裂分法可以很好的将像素数量较多的颜色反映出来，但是却忽略 了像素数量较少的颜色，对细节的还原能力较差。 3 ) 八叉树算法：是由g e r v a u t z 和p u r g a t h o f e r 在1988 年提出。八叉树 算法将源图像的r g b 值分布到一棵深度可达九层八叉树中，即根节点层以及分别 代表8 位r 、g 、b 值的位。根据源图像中像素点颜色，将叶节点不断地创建与合 并，直到叶节点数等于或小于约束条件的颜色种类数目，并存储颜色及其频率； 最终遍历此八叉树，将叶节点的颜色汇总成为目标调色板。八叉树算法仍然改变 3 天津工业大学硕士学位论文 不了某些颜色由于出现频率少而造成的细节重建模糊的命运。 4 ) k 均值算法：是指随机初始化一个调色板，根据最小距离准则，将像素 点颜色映射至初始调色板：然后根据颜色空间的聚类结果，将调色板的颜色重新 聚类；如此反复直至收敛。k 均值算法能收敛到局部最优点，但是调色板的初始 值的选择对聚类结果有较大的影响。 考虑到传统颜色量化算法的缺点，本文提出运用基于粒子群优化智能算法的 颜色量化算法进行颜色量化工作，得到高质量的颜色量化结果，最大限度地还原 图像，减少失真度。 1 2 3 粒子群优化算法 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 算法是美国心理学家 k e n n e d y 和电气工程师e b e r h a r t 受鸟类觅食行为的启发而提出的一种基于群体 智能理论的新兴演化计算技术喳1 。p s o 算法模仿鸟类的觅食行为，将问题的搜索 空间类比于鸟类的飞行空间，将每只鸟抽象为一个无质量无体积的微粒，用以表 征问题的一个候选解，优化所需要寻找的最优解则等同于要寻找的食物 1 。 作为一种通过对自然界中生物捕食现象的模拟而提出的群体进化算法，p s o 算法具有记忆粒子最佳位置的能力和粒子间信息共享的机制，即通过种群间个体 的合作与竞争来实现优化问题的求解。 p s o 算法是一种全局优化进化算法，应用于颜色量化的基于微粒群颜色量化 算法能有效地找到合适的调色板如1 。然而，基于粒子群优化智能算法的颜色量化 算法也有其天生的缺陷：运算量大，运算时间长等。为了提高该算法的运算效率， 减少其运算时间，我们将目光聚焦到多核处理器及并行计算上。 1 2 4 多核处理器并行处理 多核处理器是指在一枚处理器中集成两个或多个完整的计算引擎( 内核) 。多 核处理器是单枚芯片( 也称为“硅核) ，能够直接插入单一的处理器插槽中，但 操作系统会利用所有相关的资源，将它的每个执行内核作为独立的逻辑处理器。 通过在两个执行内核之间划分任务，多核处理器可在特定的时钟周期内执行更多 任务。要想让多核完全发挥效力，需要硬件业和软件业更多革命性的更新。美国 卡内基梅隆大学计算机系教授朗道布赖恩特( r a n d a leb r y a n t ) 在接受财经 记者采访时就坦称，“这给软件业制造了巨大的问题”。 可见，软件程序并行化是充分利用多核处理器的当务之急的首要问题。 并行计算是提高计算机系统计算速度和处理能力的一种有效手段。一般来 讲，并行算法是指在各种并行计算机上求解问题和处理数据的算法，它的基本思 4 第一章绪论 想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分， 各部分均由一个独立的处理机来并行计算，使多核处理器的使用率尽可能的接近 1 0 0 ，充分发挥多核处理器的运算能力。 在粒子群颜色量化处理过程中，所处理的图像往往数据量相当大，计算量也 惊人，对于这类大规模数据的处理工作，如果采用多核处理器及相应的并行算法 是一个不错的想法。 在论文中，为了减少运算时间，提高运算速度，采用o p e n m p 来实现粒子群 颜色量化算法的多线程并行，o p e n l 岍是一种面向共享存储器的多处理器多线程 并行编程语言1 。在基于粒子群优化算法的颜色量化算法中，使用o p e n m p 并行 编程技术，在多核处理器平台上实现粒子群颜色量化算法的多线程并行，能够大 大减少运算时间、提高运行速度。 1 3 课题的研究意义 基于多核处理器的景像织物c a d 软件解决了目前景像图像颜色数目庞大与 机织织机纬线最大颜色数目较小的矛盾，在使用了基于p s o 算法的颜色量化技术 后，能够使得重建图像最大限度地接近于原始图像，改进了传统颜色量化算法的 不足。并且能够自动生成织物组织图，并保存为织物组织图文件，减轻了织物设 计人员的工作强度，避免了人为失误。 同时，在引入了o p e n m p 多线程并行技术以后，实现了对多核处理器的充分 使用，改善了传统p s o 算法运算数据量庞大、运行速度缓慢的问题，能够将设计 结果在最短的时间内用最直观的方式展现在设计人员面前，提高了工作效率、降 低了劳动强度。 因此，基于多核处理器的景像织物c a d 软件的研究与实现对于机织织物产品 的设计与生产具有十分重要的研究价值，同相关企业的实际生产有十分密切的联 系，具有重要的实际生产意义，拥有良好的发展前景。 1 4 论文的组织结构 在对相关知识和技术的研究之后，本文设计了基于多核处理器的景像织物 c a d 软件，并通过c + + 编程语言以及o p e r 岬多线程并行技术实现了基于多核处理 器的景像织物c a d 软件。通过对算法以及软件的实际测试，验证了基于多核处理 器的景像织物c a d 软件的可行性及有效性。 5 天津工业大学硕士学位论文 本论文共分六章，主要结构和内容如下： 第一章绪论介绍了机织c a d 的国内外发展现状，并简单说明了与基于多核 处理器的景像织物c a d 相关的知识与技术，以及基于多核处理器的景像织物c a d 的研究意义。 第二章景像织物介绍了景像织物c a d 软件所涉及的纺织专业的相关知识， 以及景像织物c a d 软件对实际纺织生产过程中的问题所具有的实际意义。 第三章粒子群颜色量化介绍了粒子群算法的相关知识，粒子群颜色量化算 法的设计思路，实验证明了粒子群颜色量化算法对比传统颜色量化算法的优势。 第四章并行粒子群颜色量化介绍了并行粒子群颜色量化算法以及相关的 多核处理器知识和o p e n m p 技术。实验对比了并行粒子群颜色量化算法在多处理 器平台上的加速效果。 第五章基于多核处理器的景像织物c a d 主要介绍了景像织物c a d 软件的整 体设计思路，功能模块的详细设计( 包括三部分：图像处理、组织图、模拟仿真) 以及软件运行的具体情况。 第六章结论与展望总结了本文所完成的工作及难点问题，提出了下一步的 工作展望。 6 第二章景像织物 第二章景像织物 景像织物是人像织物和风景织物的总称，是供装饰和欣赏用的纺织品扭1 。一 般是以人物、风景照片或名人字画、美术图案等作为纹样，织造时利用各种颜色 丝线通过组织变化构成明暗的影光层次，使织物表面显示出与彩色照片或图案 一致的人物或风景哺1 。它的核心部分是织物组织设计和意匠绘制。 2 1 织物的概念及分类 在介绍织物组织设计之前我们先要对织物的概念有所了解。 织物的现代定义是由纤维、纱线或者纤维与纱线按照一定的规律构成的片状 ( 或展开后也成片状) 集合物曲1 。机织物是最常见的织物种类之一。经典的机织 物是由经、纬两个系统纱线呈直角方向，按照各种织物组织结构相交织造的。所 以这种织物的织造也称两向织造。它广泛应用于人们生活的各个领域，如服用织 物、装饰织物、产业织物等。 机织物种类繁多，根据不同用途、不同使用领域、不同生产方式、不同工序 状态、不同的外观等，有不同的分类方法，其分类方法主要有以下两种： 1 按照原料种类可以分为：棉织物、毛织物、丝织物、麻织物、化纤织物 以及矿物纤维织物。 2 按原料组成成分可以分为：纯纺织物、混纺织物、交织物、交并织物、 混交织物、混并织物以及混并交织物。 景像织物的研究对象就是机织织物，不仅包括丝织物还包括各种其他种类的 机织织物。在了解了景像织物的研究对象后，我们还要对其织物结构作简要介绍。 2 2 织物结构 织物结构是指组成纺织品的框架结构。 织物是由纱线编织而成的，机织物都是有纵横两种纱线编织起来的。纵向纱 线称为经纱，横向纱线称为纬线。织物结构就是研究织成的织物使用的是几组经 线和几组纬线以及这些经线和纬线之间的关系和组成的方式。 我们常见的纺织产品的织物结构主要包括下列几种： 1 单经单纬织物：由一组经线和一组纬线交织而成的单层织物，是最简单 的织物结构，也是在纺织品中常见的织物结构。常用于轻薄型织物，多为素织物， 7 天津工业大学硕士学位论文 提花织物很少见到。 2 单经双纬织物：由一组经线和两组纬线交织而成的单层织物。其经线与 甲纬线交织成地组织，该纬线称为地纬或实织纬线；另一组乙纬线在地组织上起 花，该纬线称为起花纬线或绒纬。单经双纬织物是常见的提花织物。 3 单经多纬织物：由一组经线和三组以及三组以上的纬线交织而成的织物， 又称为纬三重织物或纬多重织物。均系一组纬线和经线交织成地组织或地纬，另 两组纬线或其他纬线在地组织上起花。 4 双经单纬织物：由两组经线和一组纬线交织而成的织物，又称经二重织 物。与单经双纬织物刚好相反，由一组经线和一组纬线交织成地组织，另一组经 线在地组织上起花。 5 双经双纬织物：由两组经线和两组纬线交织成上下两层织物。两组经线 称为表经线和里经线，两组纬线称为表纬线和里纬线，上下两层称为表层和里层。 6 多经多纬织物：由三种或三种以上的经线和三种或三种以上的纬线相互 线色彩的编织得 象的织物结构选 现景像真彩色图 度方向的纱称为 2 - 1 为织物交织 第二章景像织物 经纱和纬纱由于相互沉浮而重叠之处称为组织点( 浮点) 。凡经纱浮在纬纱 上，称经组点( 或经浮点) ；凡纬纱浮在经纱上，称纬组点( 或纬浮点) 。在织物 中，当经组织点和纬组织点沉浮规律达到循环时，称为一个组织循环( 或完全组 织) 嘲。 为了简单明了地表示织物的组织，对于简单的织物组织，经、纬纱的沉浮规 律一般用组织图来表示。把经纱和纬纱相互沉浮的规律绘制于一种专门用来表示 织物组织的方格纸上。这种用来描绘织物组织的、带有格子的方格纸称为意匠纸， 在意匠纸上其纵行格子代表经纱，横行格子代表纬纱。在简单组织中，每个格子 代表一个组织点( 浮点) 汹1 。当组织点位经组织点时，应在格子内填满颜色或标 以其他符号，常用黑色填满格子。当组织点为纬组织点时，则不填充标记，即为 空白格子。将一个织物组织中的所有经、纬组织点均按此种方法填绘于意匠纸上， 所形成的图称为织物组织图协副。 将某种组织在织机上织造，设计人员必须根据所设计的织物组织确定综框页 数、穿综方法、综框的提升顺序以及穿筘方法，并且将其以上机的方式下达到生 产车间，用以指导织物的上机织造工艺，根据组织图，织造工人将经线按照顺序 穿过综框、将纬线按照顺序排列起来，所以上机图是表示织物上机织造工艺条件 的图解。生产、仿造或创新织物是均需要确定上机图。其中织物组织图就是上机 图的重要组成部分。图2 - 2 就是一幅简单的织物组织图。 2 4 景像织物 图2 2织物组织图 景像织物以人物、风景照片或名人字画、美术图案等作为纹样，它利用经纬 线不同的色彩，不同的组织结构，配以彩色变化的荧光层次，达到与彩色照片或 彩色绘图相一致的人物或风景效果。由于彩色像景织物的色彩变化丰富、结构细 腻复杂，设计与生产的技术难度大怕1 。因此，彩色景像织物的设计转为利用c a d 系统进行辅助设计窿7 1 ，生产上则采用剑杆织机进行配套，其设计、生产过程如图 2 - 3 9 天津工业大学硕士学位论文 图2 - 3景像织物设计、生产流程图 a d 线 信 ) ， 出 特 第二章景像织物 传统的景像机织织物c a d 软件只能通过使用c a d 软件中的简单绘图功能手工 操作鼠标、电子绘图板等输入工具，绘制出简单的包含几种颜色的几何图案，或 者读取一些颜色数目很少的简单图像作为织造的源图像，生成电子组织图文件， 以满足生产环节中剑杆织机纬线颜色数目的参数限制。 但是，随着计算机技术地急速发展，大多数信息实现了数字化管理，并且多 数是以图像格式保存的。为了可以最大限度地保证图像信息的完整性以及图像色 彩的准确还原，大多数彩色图像采用2 4 位真彩色来存储图像，既1 6 0 0 多万种颜 色。图像中每一行像素所包含的颜色数目远远大于织造设备的极限参数，所以降 低原始图像中包含的不同颜色数目，使其符合织造设备的参数要求是我们要解决 的首要问题。颜色量化技术就是解决这一问题的最佳答案。 2 5 本章小结 本章主要介绍了景像织物的相关概念、织物的概念、织物结构及其分类、织 物组织的设计、景像织物的织造流程和制造设备以及传统景像织物c a d 软件的相 关情况。最后提出了景像织物c a d 软件在处理真彩色图像时所面临的问题。 1 1 天津工业大学硕士学位论文 第三章粒子群颜色量化 第三章粒子群颜色量化 我们都知道，颜色量化属于数字图像处理技术中的一种基础技术，是指由一 个大颜色空间集合到一个小颜色空间集合的映射过程，根据所选择的k 种最优颜 色建立目标调色板，并运用目标调色板重建图像，使所得到的重建图像尽可能贴 近源图像，达到失真度最小。 颜色量化是通过两部分来实现的：第一部分是根据相关的约束条件选择合适 的目标调色板；第二部分是颜色映射，用目标调色板的颜色代替源图像中像素点 的原有颜色，得到颜色量化后的重建图像。而其中目标调色板的选择是决定重建 图像质量的重点步骤。 在颜色量化之后，要想使得颜色量化的结果与拥有1 6 0 0 多万色的真彩色原 始图像尽可能的接近，我们必须选择合适的颜色量化算法。 目前，传统的颜色量化方法是选用在整幅图像中出现频率最高的几种颜色组 合生成调色板，使用此调色板进行图像重建。这种传统的颜色量化方法，对简单 和颜色分布比较均匀密集的图像能够取得较好的效果，但是很容易忽略局部的细 节。 本文研究的融合了粒子群优化算法的粒子群颜色量化算法是一种全局搜索 的算法，克服了忽略局部细节的缺点。首先我们要了解什么是粒子群算法。 3 1 粒子群算法 粒子群( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 算法，是基于群体智能理论 的一种新兴演化计算技术。p s o 算法通过群体中微粒间的合作与竞争而产生的群 体智能优化搜索，算法具有比较强的通用性，并且具有全局寻优的特点b 卵： 3 1 1 粒子群算法的相关背景 生物群体内部的个体间的竞争与合作等行为产生的群体智能，时常能给某些 特殊的问题提供有效的解决办法。鸟类在搜寻食物的过程时，鸟类个体之间能够 进行消息的共享与交流，其中每个成员都可以从其他成员个体的飞行经历和发现 中获得好处旧，。当食物源无法预测地零散分布时，这种相互协作带来的将是决定 性的优势，远远大于个体间对食物的竞争所带来的劣势。 美国的心理学家k e n n e d y 以及电气工程师e b e r h a r t 受到这种行为的启迪啪。， 1 3 天津工业大学硕士学位论文 在1 9 9 5 年提出了粒子群优化算法。粒子群优化算法是一种在群体智能理论基础 上提出的随机寻优算法，它模拟鸟类的觅食行为，将问题的搜索空间比作鸟类的 飞行空间，将每只觅食的鸟抽象为一个无体积无质量的微粒，用以表示问题的一 个候选解，优化所需要搜索的最优解则等价于鸟类要寻找的食物。p s o 算法为每 个微粒制定了相当于鸟类飞行运动的简单行为规则，由此使得整个粒子群的运动 表现出与鸟类觅食相类似的特性，进而可以应用于求解复杂的优化问题。 作为一种源自对自然界生物觅食现象的模仿而提出的群体进化算法，p s o 算 法具有微粒间信息共享的机制以及具有记忆微粒最佳位置的能力，也就是说通过 种群间个体的竞争与合作来求解复杂的优化问题。p s o 算法与人工生命有着极其 特殊的联系，尤其是进化算法。相比进化算法，p s o 算法保留了基于种群的全局 搜索策略，使用了更为简单的速度一位移模型，规避了复杂的遗传操作，与此同 时，p s o 算法可以动态跟踪当前的搜索状况来调整搜索策略。 3 1 2 基本粒子群算法 基于粒子群优化算法特有的搜索策略，p s o 算法首先对速度空问和可行解空 间随机初始化粒子群，也就是确定粒子的初始速度以及初始位置，其中问题的解 由粒子位置来表示。比如，n 维搜索空间内的第i 个粒子的位置以及速度可以分 别表示为x f = 【x i , i9 石f 2 ，x 抽】和k = 【v i 2 ，抽】。, i9 对于最小化问题，目标函数值越小，对应的适应值越好。设f ( x ，) 为最小化 的目标函数，粒子i 的当前最佳位置由下式确定： 只o + 1 ) ：j 只o ) 一( 置o + 1 ) ) 只( f ) ( 3 - 1 ) ”7 i z o + 1 ) 一- - f ( x , o + 1 ) ) 2 舻瓦i 而 i2 一伊一、，9 2 4 9i ( 3 - 5 ) ( 3 - 6 ) 其中，矿= c i + 乞并且矿 4 ，特别是，当c i ，c 2 都等于2 0 5 时，矿= 4 1 并且 z = 0 7 2 9 。 综上所述，粒子速度的更新公式( 3 3 ) 是由以下三部分组成的： 第一部分反映了粒子当前速度的影响，联系粒子当前的情况，起到了平衡全 局和局部搜索的作用u 引。 第二部分反映了粒子本身记忆的影响，也叫认知模式，如果基本粒子群算法 的速度更新公式仅包含认知模式部分，则其性能将变差。是因为不同的粒子间缺 乏信息交互，即没有社会信息共享，粒子间没有交流，使得一个规模为n 的群体 等价于运行了n 个单个个体，因此获得最优解的概率极小。 第三部分反映了群体信息的影响，体现了粒子间的信息共享。增强了粒子的 全局搜索能力，避免了陷入局部极小。 基本粒子群算法的流程如下： 第一步：对种群中每个粒子的速度和位置进行随机初始化，如果是n 维搜索 空间，则每个粒子中包含n 个变量。 第二步：计算每个粒子的适应值，并根据公式( 3 - 1 ) 求出每个粒子的个体 最佳位置。然后根据公式( 3 - 2 ) 求出整个种群的最佳位置。 第三步：按照公式( 3 - 3 ) 、( 3 - 4 ) 更新每个粒子的速度和位置。 第四步：计算每个粒子的适应值。 第五步：根据公式( 3 - 1 ) 更新每个粒子的个体最佳位置。 第六步：根据公式( 3 2 ) 更新整个种群的最佳位置。 第七步：如果满足终止条件，则停止算法，并将整个种群的最佳位置输出， 否则返回第三步。 天津工业大学硕士学位论文 3 1 3p s o 与其它进化算法比较 粒子群算法与其他智能进化算法( 如遗传算法和蚁群算法) 有许多相似之处： 粒子群算法和其他智能进化算法都基于“种群”概念，用于表示一组解空间 中的个体集合。它们都随机初始化种群，使用适应度值来评价个体，而且都根据 适应度值来进行一定的随机搜索u 。 种群进化过程是通过子代与父代竞争，若子代具有更好的适应度值，则子代 将替换父代，因此都具有一定的选择机制。 算法都具有并行性，搜索过程是从一个解集合开始的，而不是从每个个体开 始的，不容易陷入局部极小值，并且这种并行性能提高算法的性能和效率。 粒子群算法与其他智能进化算法也存在区别： 粒子群算法在进化过程中同时记忆粒子的位置和速度信息，而遗传算法和蚁 群算法通常只记忆位置信息。 粒子群算法的信息通信机制与其他进化算法不同。遗传算法中染色体互相通 过交叉等操作进行通信，蚁群算法中每只蚂蚁将蚁群全体构成的信息素轨迹作为 通信机制，因此整个种群比较均匀地向最优区域移动。在全局模式的粒子群算法 中，只有全局最优粒子提供信息给其他的粒子，整个搜索更新过程是跟随当前最 优解的过程，因此所有的粒子很可能更快地收敛于最优解。 3 2 粒子群颜色量化算法设计 我们设每个粒子= 【p u ，p ，2 ，p 啦】代表一个候选的调色板，包括了k 种 颜色，也就是颜色量化以后所剩的不同颜色总数。其中p j , k 代表调色板中的一种 颜色，包括红、绿、蓝三种颜色分量，即r g b 三原色分量；然后运用粒子群算法， 从候选的调色板方案中，选出最佳的调色板n 2 。 调色板粒子类定义如下： c l a s sp a r t i c l e p u b l i c ： i n ts i t e c o l o r s i z e 3 ； i n ts p e e d c o l o r s i z e 3 ； d o u b l ef i t n e s s ； i ms e l f b e s t s i t e c o l o r s i z e 3 ； d o u b l es e l f b e s t f i t n e s s ； ) ； 其中，c o l o r s i z e 表示每个调色板所含的颜色数目，s i t e c o l o r s i z e 3 表 1 6 第三章粒子群颜色量化 示粒子的当前位置，s p e e d c o l o r s i z e 3 表示粒子的当前速度， s e l f b e s t s i t e c o l o r s i z e 3 表示粒子的个体历史最优位置，f i t n e s s 表示粒子 的当前适应度值，s e l f b e s t f i t n e s s 表示粒子的个体历史最优适应度值。 为衡量粒子群颜色量化算法的量化效果，应设计评价粒子好坏的适应度函 数。以图像像素点颜色与调色板颜色的欧式距离作为适应度函数，如公式( 3 7 ) 所示： 材厅一厅一 ( 心 、7 ( 一黝2 ，、( 纰一) 2 ) ) 厂( z ) = 竺坐l j 生l j 生l 一 ( 3 - 7 ) ” m xn 式中，删分别表示图像像素点的行数和列数，m n 代表像素的总数；k 表 示粒子的维数，即代表调色板包含的颜色数；气表示粒子i 第k 种颜色的r g b 分量值之一；表示像素点编的r g b 分量值之一。 粒子群颜色量化算法步骤如下所示： ( 1 ) 通过在颜色空间随机选取k 个色彩初始化每个粒子 只= 【p f 1 ，p f 2 ，p “】中的k 个颜色，组成初始调色板，再通过在颜色空 间随机选取k 个色彩初始化每个粒子的速度向量。 ( 2 ) 从i t e r = l 到最大迭代次数i t e r = = ，进行如下循环。 a 利用位置和速度进化公式( 3 3 ) 、( 3 4 ) ，更新每个粒子 只= 【p u ，p 啦，p 啦】的位置和速度； b 利用调色板粒子适应度计算公式( 3 7 ) ，更新每个粒子 只= 【p f 1 ，以：，p 】的适应度； c 更新每个粒子的个体最优位置以及个体最优适应度值； d 更新整个粒子群的最优历史位置和最优历史适应度值； ( 3 ) 当到达最大迭代次数i t e r 一时，退出循环，输出最优调色板粒子。 ( 4 ) 利用最优调色板粒子对原始图像进行颜色量化。 粒子群颜色量化算法步骤如图3 - 1 所示： 1 7 天津工业大学硕士学位论文 第三章粒子群颜色量化 v o i dc a l l p