Semi Causal Nonparametric Markov Random Field Texture Synthesis on a Gaussian Pyramid with K Nearest Search

<body bgcolor="#FFFFFF" text="#000000"> <FONT face="Verdana, Arial, Helvetica, sans-serif"> <h1 align="center">Semi Causal Nonparametric Markov Random Field Texture Synthesis on a Gaussian Pyramid with K Nearest Search</h1> <p><a href="index.htm" target="_top">My Home Page</a></p> <p><a href="nonparaMRFfast_Bar-Joseph.htm" target="_top">Fast Version</a></p> <p>This texture synthesis algorithm is basically a 2D implementation of <A href="http://research.microsoft.com/en-us/um/people/xtong/BTFSynthesis.pdf" target="_top">Synthesis of Bidirectional Texture Functions on Arbitrary</a> by Tong, Zhang, Liu, Wang and Guo. The algorithm still retains the underlying structure of the previous <a href="nonparaMRFfast.htm" target="_top">fast version</a>, however in this version the multiresolution is implemented via a <a href="http://www.cns.nyu.edu/heegerlab/content/publications/Heeger-siggraph95.pdf" target="_top">Gaussian pyramid</a> of the input image (instead of a decimated quadtree as in the fast version). The neighbourhood search algorithm has also been modified. In this version a <I>k</I> nearest neighbour lookup table is used, as in <A href="http://research.microsoft.com/en-us/um/people/xtong/BTFSynthesis.pdf" target="_top">Synthesis of Bidirectional Texture Functions on Arbitrary</a> by Tong, Zhang, Liu, Wang and Guo. There is one slight difference though in this implementation, when the <I>k</I> nearest neighbour lookup table is constructed, a smaller starting set is used from which the <I>k</I> nearest neighbours are found. This was done to save memory and computational time. Consult the code and their paper for more information. </p> <p>This version of the <a href="nonparaMRF.htm" target="_top">Semi Causal Nonparametric Markov Random Field Texture Synthesis</a> is not as fast as the <a href="nonparaMRFfast.htm" target="_top">fast version</a>, but it does offer some advantages. For one, there does appear to be a reduction in the speckle noise that was apparent in the images synthesised by the <a href="nonparaMRFfast.htm" target="_top">fast version</a>. Also, due to the nearest neighbour search algorithm, better blending is achieved between different phases of the synthetic texture. However, there is a loss in texture detail also due to the nearest neighbour search algorithm. One possible solution was presented by Hertzman etal. <a href="http://mrl.nyu.edu/projects/image-analogies/" target="_top">Image Analogies: A General Texture Transfer Framework</a>, in which the two nearest neighbour search techniques were used. Depending on a closeness of fit criteria, the result was taken from either one or the other search techniques. However the closeness of fit criteria depended on a slightly arbitrary input parameter. </p> <p>In summary, this version works well for general textures and does better on synthetic textures than the <a href="nonparaMRFfast.htm" target="_top">fast version</a>. However, for natural textures, I would recommend the <a href="nonparaMRFfast.htm" target="_top">fast version</a>, as it retains more detail in the synthetic texture. Or even the <a href="nonparaMRFgaussian.htm" target="_top">fast version on a Gaussian pyramid</a>, which is the <a href="nonparaMRFfast.htm" target="_top">fast version</a> implemented on a <a href="http://www.cns.nyu.edu/heegerlab/content/publications/Heeger-siggraph95.pdf" target="_top">Gaussian pyramid</a>, but with <A HREF="http://www.cs.utah.edu/~michael/ts/" target="_top">Ashikhmin's search</a> instead of <A href="http://research.microsoft.com/en-us/um/people/xtong/BTFSynthesis.pdf" target="_top">K nearest search</a>. For a list of other nonparametric texture synthesis techniques see <a href="links.htm" target="_top">the texture links page</a>. </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></UL> <UL><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> <h3>Source Code</h3> <table border=0 cellspacing=0 cellpadding=0><tr><td> <a href="MRFsynthesis_v1.2.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_gaussian_k [-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> <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>Min Run Time</th><th>Max Run Time</th><th>Mean Run Time</th><th>Stdev Run Time</th></tr> <tr><td>1 </td><td>165</td><td>0 0:04:05</td><td>0 0:12:24</td><td>0 0:04:42</td><td>0 0:01:06</td></tr> <tr><td>1 -c </td><td>165</td><td>0 0:04:05</td><td>0 0:12:21</td><td>0 0:04:38</td><td>0 0:01:09</td></tr> <tr><td>1 -s </td><td>165</td><td>0 0:04:30</td><td>0 0:13:48</td><td>0 0:05:11</td><td>0 0:01:17</td></tr> <tr><td>1 -s -c</td><td>165</td><td>0 0:04:33</td><td>0 0:14:19</td><td>0 0:05:11</td><td>0 0:01:24</td></tr> <tr><td>2 </td><td>165</td><td>0 0:05:18</td><td>0 0:16:28</td><td>0 0:06:17</td><td>0 0:01:25</td></tr> <tr><td>2 -c </td><td>165</td><td>0 0:05:28</td><td>0 0:09:50</td><td>0 0:06:22</td><td>0 0:01:10</td></tr> <tr><td>2 -s </td><td>165</td><td>0 0:11:00</td><td>0 0:21:10</td><td>0 0:13:17</td><td>0 0:02:05</td></tr> <tr><td>2 -s -c</td><td>165</td><td>0 0:11:21</td><td>0 0:23:09</td><td>0 0:13:54</td><td>0 0:02:39</td></tr> <tr><td>3 </td><td>165</td><td>0 0:06:30</td><td>0 0:20:28</td><td>0 0:07:36</td><td>0 0:01:32</td></tr> <tr><td>3 -c </td><td>165</td><td>0 0:06:36</td><td>0 0:21:23</td><td>0 0:08:03</td><td>0 0:02:08</td></tr> <tr><td>3 -s </td><td>165</td><td>0 0:34:25</td><td>0 1:56:03</td><td>0 0:44:45</td><td>0 0:09:46</td></tr> <tr><td>3 -s -c</td><td>165</td><td>0 0:36:11</td><td>0 1:56:12</td><td>0 0:46:51</td><td>0 0:09:41</td></tr> <tr><td>4 </td><td>165</td><td>0 0:07:30</td><td>0 0:15:11</td><td>0 0:08:52</td><td>0 0:01:33</td></tr> <tr><td>4 -c </td><td>165</td><td>0 0:07:36</td><td>0 0:26:03</td><td>0 0:09:21</td><td>0 0:02:24</td></tr> <tr><td>4 -s </td><td>165</td><td>0 1:34:30</td><td>0 5:37:25</td><td>0 2:08:30</td><td>0 0:32:01</td></tr> <tr><td>4 -s -c</td><td>165</td><td>0 1:43:16</td><td>0 5:48:46</td><td>0 2:17:23</td><td>0 0:30:42</td></tr> </table> <h3>Additional Information</h3> <p> <ul> <li>As in Greg Turk's algorithm <a href="http://www.cc.gatech.edu/~turk/texture_surfaces/texture.html" target="_top">Texture Synthesis on Surfaces</a>, every pixel in the Gaussian pyramid is visited twice. However better results maybe obtained by either increasing the neighbourhood size or modifying the probability update function <b>pUpdateFn()</b> so that each pixel is visited more than twice (as in this version). <li>To compare this algorithm with other algorithms, it is necessary to use the same neighbourhood for each. </ul> <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> <br> </FONT> <p> This site was proofread by<br> <a href="http://www.englishediting.ch">English Editing Experts</a>. </p> </body>