第27卷第2期 2010年2月 机 电 工 程 Journal of Mechanical&Electrical Engineering V01．27 N0．2 Feb．20lO Image Quilting纹理合成算法的实现与改进 诸葛振荣，杨敏 (浙江大学电气工程学院，浙江杭州310027) 摘 要：针对Image Quilting算法在合成结构性较强的纹理图片时产生局部纹理不连续的问题，提出了 一种改进的方法。改进从以下两方面进行：通过图像变形增加样本图的采样空间以增大匹配的概率；改 变匹配块的选择策略以提高合成质量。实验结果表明，改进后的算法有效地改善了纹理不连续现象，生 成的纹理图像质量更高。 关键词：纹理合成；Image Quihing；图像变形；邻域匹配 中图分类号：TP391．4l 文献标识码：A 文章编号：1001—455I(2010)02—0043—03 Realization and improvement of image quilting texture synthesis algorithm ZHUGE Zhen．rong。YANG Min (College ofElectrical Engineering，Zhejiang University。Hangzhou 310027，China) Abstract：In order to solve the discontinuous problem when synthesizing structural texture pictures，an improved method of Image Quilting texture synthesis algorithm was presented．The proposed algorithm was improved in the following two aspects：increasing the sample space of structural information by image morphing to increase the matching probabitity，changing the policy of area matching tO improving synthesizing quality．Experimental results show that the proposed algorithm can improve discontinuous phe- nomenon and obtain a texture picture which has a better quality． Key words：texture synthesis；Image Quilting；image morphine；neighborhood matching 0引 言 纹理合成是当前计算机视觉和计算机图形学研究 的热点之一，它在i维真实感显示、纹理填充和图像修 复等领域有广泛的应用。纹理合成可以分为过程纹理 合成和基于样图的纹理合成。过程纹理合成通过对物 理生成过程的仿真直接在表面生成纹理，可以获得十 分逼真的纹理图像。但每一种纹理的相关参数选择十 分繁琐，需要反复测试…。基于样图的纹理合成是近 分辨率模型和矢量量化的方法加速了搜索过程旧1；国 内的徐晓刚等人提出了一种多种子纹理合成算法，能 有效提高合成的速度”1。 逐块合成法每次合成一块图像，由于以纹理块为 单位进行合成的方式提高了效率，而且能够更好地保 持纹理图像的结构特征，因此越来越多的纹理合成算 法以纹理块为单位进行合成。Efros提出一种Image Quilting纹理合成算法，通过计算纹理合成中重叠块的 累计误差和最小误差路径完成合成”1。Kwatra在Im— 几年发展起来的一种新的纹理合成技术，其基本思想 age Quilting算法的基础上，提出了基于Graph Cut的 是：基于给定的小样图的纹理特征，拼合生成大面积的 纹理图像。基于样图的纹理合成方法可以分成两类： 逐点合成法和逐块合成法。 逐点合成法以像素为单位，通过搜索与待合成点 改进方法∞1。Cohen等提出一种使用拼接Wang Tiles 的方法实时合成纹理07‘。Liang等人提出了一种实时 的基于块的纹理合成算法，由于算法采用了四又树金 字塔和KD树来加速纹理搜索过程，在效率上有所提 的邻域最匹配的区域来合成纹理。Efros等提出了一 高‘引。 种基于无参采样的合成算法忙1；Wei等提出了一种快 速纹理合成算法，该算法采用“L”型邻域，并且利用多 Image Quilting算法由于实现简单，并且能在较短 的时间内合成高质量的纹理图像，已成为应用最广泛 收稿日期：2009—09—30 作者简介：杨敏(1983一)，女，湖南常德人，主要从事纺织CAD方面的研究．E-mail：yangminzju@163．tom 通信联系人：诸葛振荣，男，副教授．E-mail：zdjw@263．com 万方数据 

·44· 机 电 工 程 第27卷 的纹理合成算法之一。但Image Quilting算法在合成 这两条路径就是纹理块的缝合路径。Efros提出的这 某些结构性强的纹理图片时，会产生局部纹理不连续 种最小误差路径算法原理简单、计算量小，合成质量也 的现象。 很高。 本研究提出一种改进的算法，能很好地解决这个 问题，提高合成图片的质量。 1 Image Quilting算法 Efros在2001年的SIGGRAPH会议上提出了一种 基于块拼接的纹理合成算法：Image Quilting。与以往 算法相比，该算法在合成质量和合成速度等方面有了 图2利用公式12)计算出的重叠区域最小误差路径 很大的提高。Image Quilting算法的基本思想是：按照 Image Quilting算法的实现步骤如下： 扫描线顺序，每次依照一定的匹配规则，从输入纹理选 (1)从输入纹理中选择一个纹理块，拷贝至目标 取固定大小的纹理块拷贝至输出纹理，直到达到输出 纹理的左上角； 纹理图像的大小要求。其示意图如图1所示。 已合成Ⅸ域7旷 未合成区域 (2)按照扫描线顺序，每次从输入纹理中选择满 足相似度限制的纹理块集合，从该集合中随机地选择 一块，拷贝至目标纹理； (3)计算重叠部分的最小误差路径作为拼接路 径，按照该路径对两个纹理块进行缝合； (4)重复步骤(2)，(3)，直到达到目标图像的大 圈1 Image Quilting算法示意图 小限制。 在纹理块的选择上，首先随机选取指定数量的纹 理块，作为样本块序列。然后从样本块序列中，选择和 Image Quilting算法原理简单，计算量小，合成质 量也较高，适合大多数纹理图像的合成。 已合成纹理块的重叠区域的累计误差(Sum of Squared 2算法的改进 Differences，SSD)满足输入参数error tolerance限制的 块。从上述块中，随机选择一块拷贝至目标图像的待 合成位置。累计误差采用以下公式计算： d(N，，No)=∑[I R(p)一尺(g))2+(G(p)一 pE“f，q EⅣ。 尽管Image Quilting算法 能胜任大多数纹理图像的合 成，但对于一些结构性很强的 纹理图片，Image Quilting算 G(q))2+(B(p)一曰(q))2]¨2 (I) 法的结果却不太理想。合成图3 式中J7、r。，Ⅳ。一已合成纹理块和待合成纹理块重叠的 图片如图3所示，局部纹理的 区域；尺()，G()，曰()一像素的3原色红、绿、蓝通道。 不连续现象比较明显。 Imag。Quilting算 法合成的局部纹 理不连续的图像 为了使块与块之间的过渡更加平滑，Efros使用了 从图中可以看出，算法在拼接某些块时，出现了比 最小误差路径对重叠区域进行缝合。设B。和B：为沿 较明显的错误。出现这些不连续现象的原因：一方面 垂直边重叠的两相连块，重叠部分为BO。和BO：，误差 是因为输人纹理都是比较小的图片，整个纹理块的采 曲面定义为e=(口?…一曰：)2。通过下式寻找重叠部分 样空间不够大，在搜索邻域匹配块的时候找不到合适 的最小误差路径： 的块；另一方面是因为在待合成块与已合成块的重叠 E‘』2 ef．』+min(El-1，卜l，E‘．卜l，E…j-1) (2) 区域没有足够好的拼接路径。 式中 i，J．-当前的行列号；ei一重叠区域在行_『列,j 的误差值；E；，一对应位置的拼接代价。 i 本研究分别从上述两个方面对Image Quilting算 法进行了改进： 计算最后一行各点的拼接代价，取其中值最小的 改进一：通过图像变形来增加样本图的采样空间。 一点E。¨指定该点为最小误差路径的终点，反向跟踪 在Image Quilting和其他大多数的纹理合成算法中，所 获得整条路径，E。；。称为整个重叠区域的最小拼接代 有的样本都取自面积较小的输入纹理图像，因此采样 价。在合成时，在水平方向和垂直方向各有一条最小 空间比较单一，在搜索邻域时可能找不到合适的匹配 误差路径，两条路径会在中间某点重合，如图2所示， 块。为了丰富采样空间。可以对特定的图像进行一定 万方数据 

第2期 诸葛振荣，等：Image Quilting纹理合成算法的实现与改进 ·45· 的变换操作，如旋转、镜像、缩放、仿射变换等操作。这 骤，改进后的算法速度没有原算法高，下一步工作是提 样就能扩大图像采样的范围，增大匹配的概率，提高合 高算法的运行速度，使其适用于实时的交互式应用任 成图像的质量【9】。而且，采样空问转化以后，合成的 务场景中。 图像将更加地丰富和多样化。 改进二：改变匹配块的选择策略。Image Quilting 算法的核心部分是利用最小误差路径对待合成块和已 合成块进行拼接。利用这种方法，可以最大限度地减 少块与块之间的不连续。用公式(2)计算最小误差路 径时，得到重叠区域的最小拼接代价层。¨它的大小决 定了块拼接质量的好坏。E。i。越大，表示按照对应路 径进行拼接的误差越大，拼接质量越差，反之，则拼接 质量较好。原算法在选择匹配块时，只是单一地从重 叠区域的累积误差去考虑。累计误差小仅代表待合成 块和已合成块的边界误差小，相似度较高，并不代表重 叠区域的最小拼接代价小。若将最小拼接代价较大的 块拷贝到目标图像，则拼接的质量不会很高。因此，在 改进的算法中，将重叠区域的累计误差和最小拼接代 价综合考虑。在搜索邻域匹配块时选择具有最小 Dist。…¨的块合成到目标图像中，块与块之间的匹配 程度采用下式衡量： 跳‰und．。=a_SSDovo,lap+(1一a)箸(3) ‘‘overlap ’。path 式中 SSD…山。一重叠区域的累计误差；T／'overlap一重叠 区域的像素个数；E。；。一重叠区域的最小拼接代价； T／"path一最小误差路径的像素个数。 在公式(3)中，本研究引入了权值a∈(0，1)，用 来调整累计误差和最小拼接代价各自的比重。经过多 次的实验得知，当Ot取0．8时能够得到比较好的效果。 3实验结果 图4合成结果对比 参考文献(References)： [1]徐晓刚，鲍虎军，马利庄．基于相关性原理的多样图纹理 合成方法[J]．自然科学进展。2002，12(6)：665—668． [2] EFROS A，LEUNG T K．Texture Synthesis by Non-paramet- ric Sampling[C]／／International Conference Computer Vi- sion．Greece：ACM Press，1999：1033—1038． [3] WEI Li-yi，LEVOY M．Fast Texture Synthesis using Tree— structured Vector Quantization[C]／／Proceedings of S1G— GRAPH，2000：479—488． [4] 徐晓刚，于金辉，马利庄．多种子快速纹理合成[J]．中国 图像图形学报：A辑，2002，7(10)：994—999． [5] EFROS A A，FREEMAN W T．Image Quilting for Texture 利用本研究所述的算法改进思想笔者做了大量的 Synthesis and Transfer[C]／／Proceedings of SIGGRAPH． 实验，并将实验结果和原算法进行了对比。设置纹理 块大小为30 pixels×30 pixels，重叠区域大小为10 pix． els x30 pixels。error tolerance设为0．1，a设为0．8，实 验结果的对比图如图4所示。可以看出，相比Image Quilting算法，改进后的算法合成的图像质蟹更好，纹 理的不连续现象有了比较大的改善。 4结束语 在Image Quilting算法的基础上，采取通过图像变 形增加采样空间和改进匹配块的选择策略。对算法进 Los Angeles：[S．n．]，2001：341—347． [6] KWATRA V，SCHOODL A，ESSA I，et a1．Graph cut tex· tures：image and video synthesis using graph cuts[J]． ACM Transactions on Graphics，2003，22(3)：277—286． [7]COHEN M F，SHADE J，HILLER S，et a1．Wang tiles for image and texture generation[J]．ACM Transactions on Graphics，2003，22(3)：287—294． [8]LIANG L，LIU C．Real—time Texture Synthesis by Patch— based Sampling[R]．Proceedings of SIGGRAPH，2001． [9]SHEN Jian-bing，J1N Xiao—gang，MAO Xiao·yang，et a1． Completion based texture design using deformation[J]．The 行改进。改进后的算法改善了原算法在合成结构性较 Visual Computer，2006，22(9—11)：936—945． 强的纹理图片时产生的纹理不连续的问题，适用于大 多数纹理图片的合成。但是由于增加了图像变形等步 [编辑：李辉] 万方数据 

Image Quilting纹理合成算法的实现与改进 作者： 诸葛振荣， 杨敏， ZHUGE Zhen-rong， YANG Min 作者单位： 刊名： 浙江大学电气工程学院,浙江,杭州,310027 机电工程 英文刊名： MECHANICAL & ELECTRICAL ENGINEERING MAGAZINE 年，卷(期)： 2010，27(2) 0次 被引用次数： 参考文献(9条) 1.徐晓刚.鲍虎军.马利庄 基于相关性原理的多样图纹理合成方法[期刊论文]-自然科学进展 2002(6) 2.EFROS A.LEUNG T K Texture Synthesis by Non-parametric Sampling 1999 3.WEI Li-yi.LEVOY M Fast Texture Synthesis using Treestructured Vector Quantization 2000 4.徐晓刚.于金辉.马利庄 多种子快速纹理合成 2002(10) 5.EFROS A A.FREEMAN W T Image Quilting for Texture Synthesis and Transfer 2001 6.KWATRA V.SCHOODL A.ESSA I Graph cut textures:image and video synthesis using graph cuts 2003(3) 7.COHEN M F.SHADE J.HILLER S Wang tiles for image and texture generation 2003(3) 8.LIANG L.LIU C Real-time Texture Synthesis by Patchbased Sampling 2001 9.SHEN Jian-bing.JIN Xiao-gang.MAO Xiao-yang Completion based texture design using deformation 2006(9-11) 相似文献(6条) 1.会议论文 林定.陈崇成.唐丽玉.王钦敏 基于Image Quilting算法的纹理合成 2008 基于样图的纹理合成方法是继纹理映射、过程纹理合成方法后发展起来的纹理拼接技术,用于解决传统方法中出现的缝隙、扭曲、变形和参数调整等 问题.Image Quilting算法是简单易行的接缝消除方法,采用Image Quilting算法合成纹理并生成Wang Tile集,继而拼接大图像.实验表明,Image Quilting算法能够较好地保持纹理特征的连续性,但在接缝处可能破坏纹元特征. 2.学位论文 杨敏 织物纹理合成算法研究 2010 纹织CAD系统对于推进纺织品行业的发展有十分积极的作用，纹理合成技术是纹织CAD系统中非常重要的组成部分。目前的主流纹理合成算法都以普 通纹理图像作为处理对象，没有专门面向织物纹理图像的纹理合成算法。因此设计一种专用于处理织物纹理图像的纹理合成算法具有十分重要的意义。
　　 本文首先介绍了纹理合成的基本概念以及用于描述纹理的模型，并选择了几种典型的纹理合成算法进行介绍，接着分析和比较了这些算法各自的特点以 及适用的场合。然后文章分析了织物纹理图像的基本特点。在此基础上，本文提出了一种基于Image Quilting算法的织物纹理图像的纹理合成算法。算 法在Image Quilting算法的基础之上改进而成。改进一是通过将织物纹理图像的颜色空间转换至CIELAB，使输出纹理更符合人眼视觉特点。改进二是通 过比较合成纹理块和输入纹理块的直方图相似性，得到最佳合成纹理块大小。改进算法还对原算法中的纹理块选择策略进行了调整，使得输出的织物纹 理图像能更好地保持原有纹理的结构特征。最后对改进的算法进行了系统实现，实验结果表明，改进后的算法在处理织物纹理图像时具有很好的效果。 3.期刊论文 沈剑伟.王朔中.SHEN Jian-wei.WANG Shuo-zhong 拼接法纹理合成中的结构特征匹配 -上海大学学报 (自然科学版)2010,16(1) 提出一种新的纹理合成技术,该方法对样本纹理图像进行采样,逐块合成纹理图像.在寻找最优候选匹配块时改变以往算法中仅匹配颜色相似度的做法 ,加入结构信息,提高了块边界结构的相似度.用该算法选择的最优匹配块更符合人的视觉特性,合成图像接缝区域的过渡更为流畅,结构单元的完整性明显 优于原有方法.实验结果表明,该算法对结构性强的纹理具有良好的合成效果. 4.期刊论文 薛峰.成诚.江巨浪.XUE Feng.CHENG Cheng.JIANG Ju-lang 基于Wang Tile的改进纹理合成算法 -计算 机应用2010,30(8) Wang Tiles由4个纹理块构建而成,并为Tiles拼接做准备.因为Wang Tiles是事先制作的,所以它是一种实时纹理合成方法.然而,在Tiles内部和相邻 Tiles拐角处存在着匹配问题,因此,提出了一种改进Wang Tile的新方法,该方法使用一个新的样图来替换边界匹配样图的中心,并采用Image Quilting算 法查找替换路径,从而生成Tile集合,继而合成大块纹理.实验结果表明,所绘制的纹理不仅成功克服了匹配问题,而且在某种程度上增强了纹理多样性. 5.期刊论文 丁博.孙立镌.李峰.DING Bo.SUN Li-quan.LI Feng 结构性信息纹理合成新方法 -哈尔滨理工大学学报 2008,13(2) 针对当前基于结构性信息的纹理合成技术上存在的缺陷,提出了一种基于结构性信息的纹理合成新方法.该方法在基于Image Quilting方法的基础上 ,不仅考虑了两个匹配块之间的颜色相似性, 还充分考虑了结构的差别, 从而获得了比较理想的合成结果. 6.学位论文 闫钰锟 基于LBP的二维图像纹理合成技术 2009 近年来纹理合成技术广泛地应用于真实感和非真实感绘制、数据压缩、计算机动画、图像修复和编辑等领域，已经成为计算机图形学、机器视觉和 数字图像处理领域的一个重要的研究课题。本文在分析与探讨纹理合成技术的基础上，结合纹理合成技术的应用背景，确定以二维纹理图像为研究对象 ，以基于块的纹理合成技术作为本文工作重点，相关工作及主要贡献如下： 1.分析了基于样图的二维纹理合成技术的研究现状，分类总结了二维纹理图像的合成算法。 

2.基于LBP图像的纹理合成 分析了Image Quilting纹理合成算法的分块思想，提出了基于局部二进模板(LocalBinary Pattern，LBP)的合成算法，该算法将LBP图像作为纹理合 成的中间图像，用于纹理合成过程中差值平方和(Sum-of-Squared Differences，SSD)的计算；同时结合ImageQuilting算法计算最小误差边界切割 (Minimum Error Boundary Cut，MEBC)过程，采用块拼贴的思想进行纹理合成。该算法过程简单，容易实现；可以处理多种纹理，达到了合成质量与合 成速度上的平衡。对于规则纹理合成，提出了取消MEBC计算过程的简化算法。 3.基于LBP积分直方图的纹理合成 ①基于LBP直方图的相似性度量 针对块拼贴思想的纹理合成，在对纹理样图进行LBP图像计算的基础上，采用直方图间的相似性度量作为纹理合成中的匹配准则，将直方图用于纹理 合成，解决了LBP图像合成算法无法有效合成自然纹理的问题。实验表明，对于包含较多纹理细节的自然图像合成，本算法取得了很好的合成结果；但是 ，与基于LBP图像的合成算法相比，本算法比较费时。 ②基于积分直方图技术的快速直方图计算 为了提高LBP直方图合成算法的速度，将积分直方图(Integral Histogram)技术用于LBP图像中各种规则区域直方图的快速计算，从而提出了基于 LBP积分直方图的纹理合成算法。积分直方图的使用，大大减少了合成过程中局部规则区域直方图的计算时间，明显改善了纹理合成的效率。实验表明 ，基于积分直方图的纹理合成算法适用于自然纹理的合成，其合成结果保证了视觉上的相似性，合成速度满足用户的需要。 本文链接：http://d.g.wanfangdata.com.cn/Periodical_jdgc201002013.aspx 授权使用：华南理工大学(hnlgdx)，授权号：69b0791d-cf12-4f09-a742-9e9b00b12ada 下载时间：2011年3月3日