Strong Markov Random Field Texture Synthesis

<body bgcolor="#FFFFFF" text="#000000"> <h1 align="center">Strong Markov Random Field Texture Synthesis</h1> <p><a href="index.htm" target="_top">My Home Page</a></p> <p>This algorithm has been recently published in <A HREF="papers/Paget_PAMI_2004.pdf"><b>IEEE Transactions on Pattern Analysis and Machine Intelligence 2004</b></A>. The algorithm is based on the theory that an MRF with a much stronger conditional independence criteria, can be decomposed into its marginal distributions defined on its cliques. This stronger conditional independence criteria actually defines this strong-MRF on a triangulated graph. From graph theory [Judea Pearl "Probabilistic Reasoning in Intelligent Systems", 1988] and ANOVA log-linear construction [Bishop et al "Discrete Multivariate Analysis: Theory and Practice", 1975] it can be shown that this model can have its auto-model defined as combination of the marginal distributions defined on the pairwise cliques. I use this directly calculable auto-model to synthesis a variety of VisTex textures as presented on this webpage. </p> <p>In the presented paper, I advocate using a Parzen density estimation of the pairwise marginal distributions with only a box kernel and a smoothing parameter equal to 0. This is possible using Ashikhmin's argument as presented in <A HREF="http://www.cs.utah.edu/~michael/ts/" target="_top"><b>Synthesizing Natural Textures</b></A>. Although this dramatically reduces the stochastic nature inherent in the model, it does allow to show that quite a variety of textures can be modelled with just second order statistics. This gives credence for using second order models for classification. </p> <p>The model is not perfect. It is restrained by the assumptions made by the theory on the texture, and in the current implementation the Parzen density estimation of the pairwise marginal distributions does not take into account the stochastic nature of texture. The Parzen density estimation of the pairwise marginal distributions needs to be estimated with respect to entropy as in Zhu, Wu and Mumford's minimax entropy model ["FRAME: filters, random fields, and minimax entropy towards a unified theory for texture modeling", <i>Proceedings 1996 IEEE Computer Society Conference on Computer Vision and Pattern Recognition</i>]. </p> <p>In the synthesis results presented here, I have experimented with different Parzen smoothing (ie window) parameters. For an input parameter of <b>window</b>, I find a window size that equals the average distance to the first <b>k</b> nearest neighbours, where </p> <p><b>k = ImageSize^(4/7)*window/100</b> </p> <p>This value of <b>k</b> is from on Silverman ["Density estimation for statistics and data analysis", 1986] who says on page 99, that; "In the case of the generalized nearest neighour method .... the ideal <b>k</b> .... would be proportional to ImageSize^(4/(d+4)." As the data is of RGB pixels, I have used the value of <b>k</b> as given above. </p> <p>The synthesis algorithm employed is based on my earlier algorithm for <a href="nonparaMRF.htm" target="_top">nonparametric MRF texture synthesis</a>. It is a multiscale algorithm, meaning that <b>ImageSize</b> is dependent on scale. Calculating <b>k</b> at each scale gives a small window size at low resolution with increasing window size at each higher resolution. This fits neatly in with De Bonet's work ["Multiresolution sampling procedure for analysis and synthesis of texture images", <i>SIGGRAPH: Computer Graphics</i>, 1997] who employed a threshold that allowed the "variability" to increase with each higher resolution. </p> <h3>Source Code</h3> <table border=0 cellspacing=0 cellpadding=0><tr><td> <a href="strongMRFsynthesis_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_strong [-l levels] [-n neighOrder] [-s] [-t treeMax] [-i iterations] [-w window] [-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>iterations = <dd>number of iterations to be performed over the whole image. <dt>window = <dd>Parzen smoothing window parameter. The actual window size is calculated as given above. <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, iterations = 1, window = 0, 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 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>Iterations</th><th>Window</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>2</td><td> 0</td><td>165</td><td>0 00:20:36</td><td>0 02:23:26</td><td>0 00:49:51</td><td>0 00:52:52</td></tr> <tr><td>1 -s </td><td>2</td><td> 1</td><td>165</td><td>0 00:20:17</td><td>0 02:15:57</td><td>0 00:52:04</td><td>0 00:56:14</td></tr> <tr><td>1 -s </td><td>2</td><td> 2</td><td>165</td><td>0 00:20:40</td><td>0 02:05:29</td><td>0 00:54:30</td><td>0 00:57:33</td></tr> <tr><td>1 -s </td><td>2</td><td> 5</td><td>165</td><td>0 00:21:03</td><td>0 02:21:00</td><td>0 01:00:27</td><td>0 01:03:45</td></tr> <tr><td>1 -s </td><td>2</td><td>10</td><td>165</td><td>0 00:22:19</td><td>0 03:23:51</td><td>0 01:13:16</td><td>0 01:18:38</td></tr> <tr><td>1 -s </td><td>2</td><td>20</td><td>165</td><td>0 00:42:51</td><td>0 03:11:26</td><td>0 01:38:57</td><td>0 01:44:30</td></tr> <tr><td>2 -s </td><td>2</td><td> 0</td><td>165</td><td>0 00:42:04</td><td>0 03:33:01</td><td>0 01:47:50</td><td>0 01:53:34</td></tr> <tr><td>2 -s </td><td>2</td><td> 1</td><td>165</td><td>0 00:43:51</td><td>0 03:46:01</td><td>0 01:51:06</td><td>0 01:57:23</td></tr> <tr><td>2 -s </td><td>2</td><td> 2</td><td>165</td><td>0 00:44:22</td><td>0 03:56:17</td><td>0 01:54:03</td><td>0 02:00:32</td></tr> <tr><td>2 -s </td><td>2</td><td> 5</td><td>165</td><td>0 00:42:26</td><td>0 06:25:51</td><td>0 02:08:10</td><td>0 02:16:58</td></tr> <tr><td>2 -s </td><td>2</td><td>10</td><td>165</td><td>0 00:45:59</td><td>0 05:52:28</td><td>0 02:24:34</td><td>0 02:32:38</td></tr> <tr><td>2 -s </td><td>2</td><td>20</td><td>165</td><td>0 01:13:37</td><td>0 06:09:12</td><td>0 03:08:43</td><td>0 03:19:42</td></tr> <tr><td>3 -s </td><td>2</td><td> 0</td><td>165</td><td>0 01:15:27</td><td>0 09:23:11</td><td>0 03:21:46</td><td>0 03:37:40</td></tr> <tr><td>3 -s </td><td>2</td><td> 1</td><td>165</td><td>0 01:15:12</td><td>0 11:34:16</td><td>0 03:26:13</td><td>0 03:44:36</td></tr> <tr><td>3 -s </td><td>2</td><td> 2</td><td>165</td><td>0 01:15:46</td><td>0 10:24:21</td><td>0 03:34:17</td><td>0 03:48:51</td></tr> <tr><td>3 -s </td><td>2</td><td> 5</td><td>165</td><td>0 01:15:20</td><td>0 10:57:20</td><td>0 03:50:02</td><td>0 04:06:04</td></tr> <tr><td>3 -s </td><td>2</td><td>10</td><td>165</td><td>0 01:19:03</td><td>0 13:59:07</td><td>0 04:24:19</td><td>0 04:28:46</td></tr> <tr><td>3 -s </td><td>2</td><td>20</td><td>165</td><td>0 02:00:27</td><td>0 18:26:09</td><td>0 05:12:29</td><td>0 05:21:11</td></tr> <tr><td>4 -s </td><td>2</td><td> 0</td><td>165</td><td>0 01:54:34</td><td>0 12:39:00</td><td>0 05:14:56</td><td>0 05:35:18</td></tr> <tr><td>4 -s </td><td>2</td><td> 1</td><td>165</td><td>0 02:02:48</td><td>0 11:51:39</td><td>0 05:18:49</td><td>0 05:41:03</td></tr> <tr><td>4 -s </td><td>2</td><td> 2</td><td>165</td><td>0 01:53:47</td><td>0 15:37:25</td><td>0 05:33:14</td><td>0 05:36:28</td></tr> <tr><td>4 -s </td><td>2</td><td> 5</td><td>165</td><td>0 02:05:52</td><td>0 14:46:07</td><td>0 06:00:18</td><td>0 05:54:53</td></tr> <tr><td>4 -s </td><td>2</td><td>10</td><td>165</td><td>0 02:10:48</td><td>0 12:57:24</td><td>0 06:38:43</td><td>0 06:52:57</td></tr> <tr><td>4 -s </td><td>2</td><td>20</td><td>165</td><td>0 02:50:30</td><td>0 18:18:05</td><td>0 07:38:30</td><td>0 07:22:53</td></tr> </table> <h3>Limitations</h3> <p> <ul> <li>This algorithm works well for natural textures which have a pixelwise noise distribution. Generally, as the theory indicates, this model will only work for stationary homogeneous textures with limited long range correlations. However from the synthetic textures presented, it is clear that a surprising variety of textures can be modeled from just second order statistics. </ul> <br> <h3>Additional Information</h3> <p> <ul> <li>The advantage of the strong-MRF model is that it can be used to produce a nonparametric model of any statistical order directly from any stationary homogeneous random field. The nonparametric strong-MRF model is not constrained by the functionality of arbitrary predefined potential functions. These advantages make it an excellent candidate for the application of texture recognition in images that contain other textures of unknown origin [Paget and Longstaff, "Open-ended texture classification for terrain mapping", <i>International Conference on Image Processing</i>, 2000]. <li>It is hoped that this model will light the way to finding the optimal model that will give realistic realizations of a texture while at the same time being used for its classification. </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>