<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2800.1491" name=GENERATOR></HEAD>
<BODY>
<DIV><SPAN class=899565514-16032005><FONT face=Arial color=#0000ff
size=2>Stefan, I started a thread on this a while ago relating to
non-deterministic behavior across platforms. If the ITK design committee
approves the move, it would be great to standardize the random number generator
to be sufficiently random, fast and generate the same sequences (from a given
seed) across platforms. The discussion culminated with Brad's post: <A
href="http://www.itk.org/mailman/private/insight-developers/2005-January/006220.html">http://www.itk.org/mailman/private/insight-developers/2005-January/006220.html</A>
I'm not sure any action happened on the suggestions.</FONT></SPAN></DIV>
<DIV><SPAN class=899565514-16032005></SPAN><SPAN class=899565514-16032005><FONT
face=Arial color=#0000ff size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=899565514-16032005><FONT face=Arial color=#0000ff size=2>As you
point out, many registration algorithms depend on random sampling, exactly where
I came across the problem.</FONT></SPAN></DIV>
<DIV><SPAN class=899565514-16032005><FONT face=Arial color=#0000ff
size=2></FONT></SPAN> </DIV>
<DIV><SPAN class=899565514-16032005><FONT face=Arial color=#0000ff
size=2>Cheers,</FONT></SPAN></DIV>
<DIV><SPAN class=899565514-16032005><FONT face=Arial color=#0000ff
size=2>-dan</FONT></SPAN></DIV>
<BLOCKQUOTE>
<DIV class=OutlookMessageHeader dir=ltr align=left><FONT face=Tahoma
size=2>-----Original Message-----<BR><B>From:</B>
insight-users-bounces@itk.org [mailto:insight-users-bounces@itk.org]<B>On
Behalf Of </B>Stefan Klein<BR><B>Sent:</B> Wednesday, March 16, 2005 9:16
AM<BR><B>To:</B> Insight-users@itk.org<BR><B>Subject:</B> [Insight-users]
random number generator<BR><BR></FONT></DIV><FONT size=3><BR>Dear
itk-users,<BR><BR>I did some tests with the underlying random generator of the
itkImageRandomIteratorWithIndex and it seems that, in Windows, it is 'not very
random'. <BR><BR>The itkImageRandomIterator uses the following
random-generator:<BR><ITKSOURCE>\Utilities\vxl\core\vnl\vnl_sample.<h/cxx><BR><BR>In
Linux the drand48 random-generator is used, which is a good choice.<BR>In
Windows however a "simple congruential random number generator" is
implemented, since drand48 is not available in Windows. This gives inferior
results, in my experience.<BR><BR>To get a feel for the result look at the
image1.<mhd/raw>, which is in the file: randomtestresults.zip, which you
can download from: <A href="http://www.isi.uu.nl/People/Stefan/"
eudora="autourl">http://www.isi.uu.nl/People/Stefan/<BR></A>The gray-values in
this image show how many times a pixel was sampled. The sampling<BR>process
works was defined as follows:<BR> "An ImageRegionIterator walks
N=200 times through the image and tests<BR> at each voxel whether
to sample it or not. The test is performed by <BR> drawing a
number between 0 and 1 using the random generator defined in<BR>
vnl_sample.h; a value >=0.5 means that the voxel is sampled"<BR>As you can
see in the image the pixels are not really selected at random...<BR><BR>If we
use the itkImageRandomIteratorWithIndex to sample the image, the result
(image3.<mhd,raw>) may look better at first sight, but the histogram
looks terrible.<BR><BR>On the internet I found the following link:<BR><A
href="http://paine.wiau.man.ac.uk/pub/doc_vxl/core/vnl/html/classvnl__random.html"
eudora="autourl">http://paine.wiau.man.ac.uk/pub/doc_vxl/core/vnl/html/classvnl__random.html</A><BR>It
describes the files vnl_random.<h,cxx>; those files are not included in
the vxl-version that comes with ITK. I tried to use these as a random
generator. The results are now much better. Image2, which is generated in the
same was as image1, but with the random generator defined in vnl_random, does
not show any structure anymore. Image4, which is generated using an
ImageRandomIterator that uses the vnl_random as its underlying random number
generator, has the histogram that you would expect.<BR><BR>For more details
please look at the source of the test program, which you can also download
from <A href="http://www.isi.uu.nl/People/Stefan/"
eudora="autourl">http://www.isi.uu.nl/People/Stefan/</A> :
itkrandomtestsource.zip. You may reproduce the results with this program. Note
that only in Windows bad results will be obtained. In Linux there is no
problem.<BR><BR>Algorithms that rely on a good random generator may fail if
you use the itkRandomImageIteratorWithIndex under Windows. For example, in my
research on nonrigid registration I tried to use a stochastic gradient descent
optimisation method for minimising the MattesMutualInformation in combination
with a B-spline transform (it may speed up your registration algorithms; if
you are interested: <BR><A
href="http://www.isi.uu.nl/Research/Publications/publicationview.php?id=1011"
eudora="autourl">http://www.isi.uu.nl/Research/Publications/publicationview.php?id=1011</A>
). When I used the itkImageRandomConstIteratorWithIndex for selecting spatial
samples the registration results got significantly worse than when I used the
itkImageMoreRandomConstIteratorWithIndex (which uses the vnl_random as
underlying random number generator).<BR><BR>Any comments on this would be
appreciated!<BR><BR>Stefan<BR><BR><BR><BR><BR><BR></FONT><BR></BLOCKQUOTE></BODY></HTML>