Faster Semi Causal Nonparametric Markov Random Field Texture Synthesis

<body bgcolor="#FFFFFF" text="#000000"> <h1 align="center">Faster Semi Causal Nonparametric Markov Random Field Texture Synthesis</h1> <p><a href="index.htm" target="_top">My Home Page</a></p> <p><a href="nonparaMRFfast.htm" target="_top">Fast Version</a></p> <p>This algorithm is a cut down version of the algorithm published in <A HREF="papers/Paget_IP_1998.pdf"><b>IEEE Transactions on Image Processing 1998</b></A>. In this version, it has been rewritten for a single cpu machine. To maintain speed of synthesis, the update function <b>pUpdateFn()</b> has been set to return the maximum value. If this was modified to return a portion of the maximum value, then the synthesis would take longer, but there would be a gain in quality. If you do decide to modify the code, be careful, as I have not put in any safeguard checks. Best to fully understand the whole code, before modifying it.</p> <p> This faster version implements a modification based on Ashikhmin's <A HREF="http://www.cs.utah.edu/~michael/ts/" target="_top"><b>Synthesizing Natural Textures</b></A>. As noted in his work, the L2 norm may not be the best measure to test for perceptual similarity between two neighbourhoods. Instead, we may note that if we are only taking pixels from the input image (and not sampling from a larger distribution), then when we iterate a respective pixel, we can be assured that each of its defined neighbours occur within the input image. Speed can be gained if, instead of doing a exhaustive search, we only sample from those pixels which have the same neighbour. In this algorithm I have modified Ashikhmin's approach by using my previous algorithm, and sampling from <b>all</b> pixels which have at least one of its neighbours the same colour as its respective neighbour of the pixel being iterated. </p> <p> Recently there has been quite an influx of nonparametric sampling techniques for texture synthesis (,<a href="links.htm" target="_top"><b>here is a brief list</b></a>). This is because it has been the nonparametric models that have had the greatest success at synthesising arbitrary textures. This technique uses a multiscale approach, which has the advantage that only a small neighbourhood is required. </p> <p><UL><LI>R. Paget and I. D. Longstaff, ``Texture synthesis via a noncausal nonparametric multiscale Markov random field,'' <I>IEEE Transactions on Image Processing</I>, vol. 7, n 6, pp. 925-931, June 1998. - <A HREF="papers/Paget_IP_1998.pdf">Paget_IP_1998.pdf</A> - <A HREF="papers/Paget_IP_1998.ps.gz">Paget_IP_1998.ps.gz</A> - <A HREF="papers/Paget_IP_1998.ppt">Paget_IP_1998.ppt</A> </LI></UL> <p>However the basis of the algorithm first appeared in:</p> <p><UL><LI>R. Paget and I. D. Longstaff, ``A nonparametric multiscale Markov random field model for synthesising natural textures,'' in <I>Fourth International Symposium on Signal Processing and its Applications</I>, vol. 2, (Gold Coast, Australia), pp. 744-747, ISSPA 96, August 1996. - <A HREF="papers/Paget_ISSPA_1996.pdf">Paget_ISSPA_1996.pdf</A> - <A HREF="papers/Paget_ISSPA_1996.ps.gz">Paget_ISSPA_1996.ps.gz</A> </LI> <LI>R. Paget and I. D. Longstaff, ``Texture synthesis via a nonparametric Markov random field,'' in <I>Proceedings of DICTA-95, Digital Image Computing: Techniques and Applications </I>(A. Maeder and B. Lovell, eds.), vol. 1, (Brisbane, Australia), pp. 547-552, Australian Pattern Recognition Society, December 1995. - <A HREF="papers/Paget_DICTA_1995.pdf">Paget_DICTA_1995.pdf</A> - <A HREF="papers/Paget_DICTA_1995.ps.gz">Paget_DICTA_1995.ps.gz</A> </LI></UL> <br> <h3>Source Code</h3> <table border=0 cellspacing=0 cellpadding=0><tr><td> <a href="fasterMRFsynthesis_v1.0.tar.gz">Download Source Code</a> </td><td width=20></td><td> <i>Copyright (C) 2002, by Rupert Paget, all rights reserved.</i> </td></tr></table> <p>The source code requires <a href="http://www.imagemagick.org">ImageMagick</a> to be preinstalled. To compile the code, run gmake in the parent directory. There are two makefiles, one in parent directory, and in the src directory. If the code does not compile, both makefiles will need to be edited. I have written one for a sun (default) and one for an sgi machine, but I give no guarantees that they will work. </p> <h3>The program is executed with the following command</h3> <p> nonparaMRF_faster [-l levels] [-n neighOrder] [-s] [-t treeMax] [-c] [-x cols] [-y rows] [-m maskfile] [-h] texturefile </p> <p>where</p> <p> <dl compact> <dt>levels = <dd>number of gray levels the image will be compacted to. Reducing the number from 255, will probably not improve the synthesis, and will most likely increase the run time. <dt>neighOrder = <dd>number to signify neighbourhood size. See <a href="nonparaMRFSynthesisTemplate.htm" target="Synthesis">neighbourhoods</a> for schematics of the neighbourhoods used in the texture synthesis algorithm. <dt>s = <dd>if set, the neighbourhood becomes a square neighbourhood. <dt>treeMax = <dd>maximum quadtree height. The algorithm will not allow the quadtree height to be set to a value that will allow either the input image or output image to be reduced to less than a 2x2 pixel image. <dt>c = <dd>if set, the output image is defined to be toroidal (ie cyclic) where each border matches with its opposite border. <dt>cols = <dd>number of columns in the output image. If undefined, number columns in the output image will equal number columns in the input image. <dt>rows = <dd>number of rows in the output image. If undefined, number rows in the output image will equal number rows in the input image. <dt>maskfile = <dd>is a mask image that must be the same size as the input texture image. Only where the mask image is non zero is the input image used. <dt>h = <dd>if set, will mean that just usage and default values will be displayed. This will also occur if no input values are given. <dt>texturefile = <dd>is the input texture image that is to be synthesised. </dl> <p> Default values are : levels = 256, neighOrder = 1, square = false, treeMax = 6, cyclic = false </p> <p> <h3><a href="nonparaMRFSynthesisTemplate.htm" target="Synthesis">Schematic of the neighbourhoods used in the texture synthesis algorithm<img src="nonparaMRFimages/n2_64x64.gif" width=64 height=64 border=0 alt="Schematic of the neighbourhoods used in the texture synthesis algorithm"></a></h3> <br> <h3>Synthesis run times for various input parameters</h3> <p> These times were compiled on a distributed system of mainly <b>SunBlades 100</b>: 500 MHz, 256 MBytes RAM. The input textures were 128x128 pixel images, and the output synthesised textures were 256x256 pixel images. The run times are basically dependent on output image size and the type of input texture. This is due to the nearest neighbour search algorithm used in the code. If the input texture is fairly uniform in colour, then the search algorithm will be more of an exhaustive search, and therefore more dependent on input image size. Time stamps are in "Days Hours:Minutes:Seconds". </p> <table cellspacing=5 border> <tr><th>Neighbourhood</th><th># of Tests</th><th>Fastest Run Time</th><th>Slowest Run Time</th><th>Mean Run Time</th><th>Stdev Run Time</th></tr> <tr><td>1 -s </td><td>165</td><td>0 0:02:12</td><td>0 0:06:28</td><td>0 0:02:48</td><td>0 0:00:31</td></tr> <tr><td>1 -s -c</td><td>165</td><td>0 0:02:12</td><td>0 0:05:54</td><td>0 0:02:53</td><td>0 0:00:34</td></tr> <tr><td>2 -s </td><td>165</td><td>0 0:02:12</td><td>0 0:05:56</td><td>0 0:02:50</td><td>0 0:00:28</td></tr> <tr><td>2 -s -c</td><td>165</td><td>0 0:02:15</td><td>0 0:07:55</td><td>0 0:02:55</td><td>0 0:00:35</td></tr> <tr><td>3 -s </td><td>165</td><td>0 0:02:16</td><td>0 0:06:48</td><td>0 0:02:55</td><td>0 0:00:35</td></tr> <tr><td>3 -s -c</td><td>165</td><td>0 0:02:23</td><td>0 0:08:14</td><td>0 0:03:02</td><td>0 0:00:37</td></tr> <tr><td>4 -s </td><td>165</td><td>0 0:02:19</td><td>0 0:06:01</td><td>0 0:03:01</td><td>0 0:00:32</td></tr> <tr><td>4 -s -c</td><td>165</td><td>0 0:02:11</td><td>0 0:05:42</td><td>0 0:02:47</td><td>0 0:00:23</td></tr> </table> <h3>Limitations</h3> <p> <ul> <li>This algorithm works well for natural textures which have a pixelwise noise distribution. However unwanted noise appears in textures that don't have a substantial pixel noise distribution (like artificial textures). The noise seems to appear at pixel points that have been synthesised at the higher grid levels (lower resolution). There are various reasons for this, but it results from modifying the update function <b>pUpdateFn()</b> in order to speed up the algorithm. </ul> <br> <h3>Additional Information</h3> <p> <ul> <li>In this version, the Manhatten distance is used to find the nearest neighbourhood. From personal observation, the Manhatten distance produced more detail in the synthetic texture compared to using the Euclidean norm. <li>This faster version uses a combination of 3 different sampling methods. The methods are used in a consecutive order until a sample is found. They are as follows: <ul> <li> Ashikhmin's sampling method. <li> My modified version of Ashikhmin's sampling method. <li> Exhaustive search. </ul> <li>To compare this algorithm with other algorithms, it is necessary to use the same neighbourhood for each. </ul> <br> <h3>For More Information</h3> <p> Email Rupert Paget at: <a href="mailto:dr@rupertpaget.com">dr@rupertpaget.com</a></p>  <script type="text/javascript" language="JavaScript">var site="s13rupert"</script> <script type="text/javascript" language="JavaScript1.2" src="http://s13.sitemeter.com/js/counter.js?site=s13rupert"> </script> <noscript> <a href="http://s13.sitemeter.com/stats.asp?site=s13rupert" target="_top"> <img src="http://s13.sitemeter.com/meter.asp?site=s13rupert" alt="Site Meter" border=0></a> </noscript>   <p> <a href="http://validator.w3.org/check/referer"><img border="0" src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" height="31" width="88"></a> </p> <p> This site was proofread by<br> <a href="http://www.englishediting.ch">English Editing Experts</a>. </p> </body>