[Insight-users] fast marching algorithm very time consuming?

Tue Aug 14 06:07:10 EDT 2007

Hi Michal,

Running the Fast Marching method on your data produced the results you
described.

Having a closer look, I think this is due to the spacing of the image.
What unit is the spacing of your image? If it is mm, then [98.0, 98.0,
106.0] seems somewhat strange...

I temporarily changed the spacing (WARNING: be VERY careful doing
this) by dividing each component by 100 to be [0.98, 0.98, 1.06].
Using this, the method works fine for me. When solving the underlying
quadratic equation, the Fast Marching method takes into the account
the spacing. The large spacing in your image is causing the front to
move very slowly. Perhaps you can convert the spacing to a different
unit or if the spacing is wrong (as I suspect) replace it with the
correct values and/or units.

Hope this helps,

Cheers, Dan

On 14/08/07, Michal Plotkowiak <michal.plotkowiak at bnc.ox.ac.uk> wrote:
> Hi,
>
> Thank you Dan and Luis for your help. My server is temporary down so I had to
> use 'YouSendIt' service, hope that's ok and you got the link.
>
> the first file FastMarchingOutput3 contains 6 slices, data is stored locally
> in .mha
>
> the second file single slice contains values for one slice saved in .dat file
>
> the max for my speed is about 0.77 and the min is 0.07e-012
>
> Should I rescale it?
>
> many thanks
> michal
>
>
>
>
> In message <46C0DAF8.4020200 at kitware.com> Luis Ibanez <luis.ibanez at kitware.com>
> writes:
> >
> > Hi Michal,
> >
> >
> >      I think Dan is in the right track here.
> >
> >
> > The fact that you need such a large stopping time in order to
> > fill up the objects in your image, raises doubts about the
> > scale of intensities in your speed image.
> >
> > As Dan describes, we usually assume that the speed image
> > has been scaled to a range of 0.0 to 1.0.
> >
> > E.g. if your image is of size 256x256, we could expect that
> > with an stopping time of about 300 you could fill in any
> > object in the image. This assumption is based on guessing
> > that your speed image has pixel values close to 1.0 inside
> > the objects that you are trying to segment. Therefore it
> > takes 1 unit of time for the FastMarching front to advance
> > a distance of 1 pixel.
> >
> >
> > You may want to take a look at the ITK Software Guide
> >
> >         http://www.itk.org/ItkSoftwareGuide.pdf
> >
> > in particular to the section on LevelSet segmentation,
> > where you will find advice on how to prepare the speed
> > (or feature) image that is passed as input to most
> > level set methods.
> >
> >
> >
> > As Dan suggested: it will help a lot if you post
> >       your speed image (slices of the original, not
> >       screen shots) to some public web site.
> >
> >
> >
> >     Regards,
> >
> >
> >         Luis
> >
> >
> > -----------------
> > Dan Mueller wrote:
> > > Hi Michal,
> > >
> > > I too use the Fast Marching method for segmenting the heart (from CTA
> > > images). I can process 512x512x512 datasets with Fast Marching in
> > > under 60 sec on an Intel Xeon, 2.66 GHz, 8 MB RAM, Windows XP.
> > >
> > > Are you compiling your program in Debug or Release mode? Sometimes
> > > debug mode can be very slow...
> > >
> > > Also, your speed function can alter the stopping value: for example,
> > > if the speed function has many small values (near say 0.0001), larger
> > > arrival times will be produced (requiring more time to reach your
> > > stopping value). Are you rescaling your speed function to fill the
> > > entire range between [0, 1]? Perhaps you could upload your speed image
> > > (or a few slices of it) to a public datastore and post the link on
> > > this list?
> > >
> > > Cheers, Dan
> > >
> > > On 14/08/07, Michal Plotkowiak <michal.plotkowiak at bnc.ox.ac.uk> wrote:
> > >
> > >>In message <46C06E15.7050200 at kitware.com> Luis Ibanez
> <luis.ibanez at kitware.com>
> > >>writes:
> > >>
> > >>as far as I see, the fact that I increased the treshold value allowed me to
> > >>store the result in the final output. Previously I was reading results from
> the
> > >>intermediate output 4. But still to get a complite segmentation i need to
> set
> > >>my values to around 2000 (this value is also suggested by my output map).
> > >>Again, it takes very long to get any results.
> > >>
> > >>michal
> > >>
> > >>
> > >>>Hi Michael,
> > >>>
> > >>>FastMarching should take only seconds in that size of data set.
> > >>>
> > >>>You are requesting a stopping time of 2000 and thresholding at 100,
> > >>>that means that all the times from 101 to 2000 are going to waste.
> > >>>
> > >>>If you are going to threshold at 100, you can just set the stopping
> > >>>time to a value slightly above the threshold. For example, you could
> > >>>stop at 110.
> > >>>
> > >>>The heuristic for choosing the stopping time relates to the size of
> > >>>the object that you want to segment and to the average value of the
> > >>>speed image in the region that goes from the seed points to the
> > >>>boundaries of the object that you want to segment.
> > >>>
> > >>>
> > >>>
> > >>>BTW: What is the profile of your computer ?
> > >>>      OS, Processor, Memory ?
> > >>>
> > >>>
> > >>>
> > >>>    Regards,
> > >>>
> > >>>
> > >>>       Luis
> > >>>
> > >>>-------------------------
> > >>>Michal Plotkowiak wrote:
> > >>>
> > >>>>Hi,
> > >>>>
> > >>>>I'm segmenting 3D data of a heart using FastMarchingImageFilter program.
> > >>
> > >>The
> > >>
> > >>>>data size is 256x256x362. Every 5th slice I generate seed points
> > >>
> > >>(approximately
> > >>
> > >>>>300 on a slice). My threshold time is 100 and stoping time 2000. When I
> ran
> > >>
> > >>the
> > >>
> > >>>>simulation only for 6 slices I get good results but after about an hour.
> > >>
> > >>When I
> > >>
> > >>>>tried to run the sumulation for all the slices (362) two days wasn't
> > >>
> > >>enough...
> > >>
> > >>>>Has anyone some experience with FastMarching algorithm? The time needed
> for
> > >>
> > >>the
> > >>
> > >>>>simulation seems to be far too long. Should I somehow change my approach
> to
> > >>
> > >>the
> > >>
> > >>>>problem?
> > >>>>
> > >>>>many thanks
> > >>>>michal
> > >>>
> > >>--
> > >>Michal Plotkowiak
> > >>Doctoral Researcher
> > >>Oxford University LSI DTC
> > >
> > > _______________________________________________
> > > Insight-users mailing list
> > > Insight-users at itk.org
> > > http://www.itk.org/mailman/listinfo/insight-users
> > >
> >
>
> --
> Michal Plotkowiak
> Doctoral Researcher
> Oxford University LSI DTC