<!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.1476" name=GENERATOR></HEAD>
<BODY>
<DIV><SPAN class=470011515-16032005><FONT face=Arial color=#0000ff size=2>Maybe
we should add a proposal on the itk Wiki.</FONT></SPAN></DIV>
<DIV><SPAN class=470011515-16032005><FONT face=Arial color=#0000ff size=2><A
href="http://www.itk.org/Wiki/ITK_Oversight_Committee">http://www.itk.org/Wiki/ITK_Oversight_Committee</A></FONT></SPAN></DIV>
<DIV><SPAN class=470011515-16032005></SPAN> </DIV>
<BLOCKQUOTE dir=ltr style="MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader dir=ltr align=left><FONT face=Tahoma
size=2>-----Original Message-----<BR><B>From:</B>
insight-developers-bounces@itk.org
[mailto:insight-developers-bounces@itk.org]<B>On Behalf Of </B>Blezek, Daniel
J (Research)<BR><B>Sent:</B> Wednesday, March 16, 2005 10:05 AM<BR><B>To:</B>
Stefan Klein; Insight-users@itk.org;
insight-developers@itk.org<BR><B>Subject:</B> [Insight-developers] RE:
[Insight-users] random number generator<BR><BR></FONT></DIV>
<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></BLOCKQUOTE></BODY></HTML>