[Insight-developers] RE: [Insight-users] random number generator

[Simon Warfield]

I would vote for using the Mersenne Twister.  I have been using that on 
and off for a couple of years, with good experiences.


Lorensen, William E (Research) wrote:

> Maybe we should add a proposal on the itk Wiki.
> http://www.itk.org/Wiki/ITK_Oversight_Committee
>  
>
>     -----Original Message-----
>     *From:* insight-developers-bounces at itk.org
>     [mailto:insight-developers-bounces at itk.org]*On Behalf Of *Blezek,
>     Daniel J (Research)
>     *Sent:* Wednesday, March 16, 2005 10:05 AM
>     *To:* Stefan Klein; Insight-users at itk.org; insight-developers at itk.org
>     *Subject:* [Insight-developers] RE: [Insight-users] random number
>     generator
>
>     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:
>     http://www.itk.org/mailman/private/insight-developers/2005-January/006220.html 
>     I'm not sure any action happened on the suggestions.
>      
>     As you point out, many registration algorithms depend on random
>     sampling, exactly where I came across the problem.
>      
>     Cheers,
>     -dan
>
>         -----Original Message-----
>         *From:* insight-users-bounces at itk.org
>         [mailto:insight-users-bounces at itk.org]*On Behalf Of *Stefan Klein
>         *Sent:* Wednesday, March 16, 2005 9:16 AM
>         *To:* Insight-users at itk.org
>         *Subject:* [Insight-users] random number generator
>
>
>         Dear itk-users,
>
>         I did some tests with the underlying random generator of the
>         itkImageRandomIteratorWithIndex and it seems that, in Windows,
>         it is 'not very random'.
>
>         The itkImageRandomIterator uses the following random-generator:
>         <ITKSOURCE>\Utilities\vxl\core\vnl\vnl_sample.<h/cxx>
>
>         In Linux the drand48 random-generator is used, which is a good
>         choice.
>         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.
>
>         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: http://www.isi.uu.nl/People/Stefan/
>         The gray-values in this image show how many times a pixel was
>         sampled. The sampling
>         process works was defined as follows:
>            "An ImageRegionIterator walks N=200 times through the image
>         and tests
>            at each voxel whether to sample it or not. The test is
>         performed by
>            drawing a number between 0 and 1 using the random generator
>         defined in
>            vnl_sample.h; a value >=0.5 means that the voxel is sampled"
>         As you can see in the image the pixels are not really selected
>         at random...
>
>         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.
>
>         On the internet I found the following link:
>         http://paine.wiau.man.ac.uk/pub/doc_vxl/core/vnl/html/classvnl__random.html
>         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.
>
>         For more details please look at the source of the test
>         program, which you can also download from
>         http://www.isi.uu.nl/People/Stefan/ : 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.
>
>         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:
>         http://www.isi.uu.nl/Research/Publications/publicationview.php?id=1011
>         ). 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).
>
>         Any comments on this would be appreciated!
>
>         Stefan
>
>
>
>
>
>
>------------------------------------------------------------------------
>
>_______________________________________________
>Insight-users mailing list
>Insight-users at itk.org
>http://www.itk.org/mailman/listinfo/insight-users
>  
>


-- 
Simon K. Warfield, Ph.D. warfield at bwh.harvard.edu Phone:617-732-7090
http://www.spl.harvard.edu/~warfield           FAX:  617-582-6033
Associate Professor of Radiology,          Harvard Medical School
Director, Computational Radiology Laboratory
Thorn 329, Dept Radiology,  Brigham and Women's Hospital 
75 Francis St, Boston, MA, 02115