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

Tue Aug 14 08:15:43 EDT 2007

Dan, thank you for your suggestion.

I thought that spacing is not important as long as I keep the right ratio. I've 
changed the values to .98 .98 and 1.06. Now it's enough when I set the treshold 
and stopping values to around 100. However, it still takes a long time to 
deliver any results.

cheers,
michal

In message <2b8d077d0708140307u63bb92acsecb8d3e4667aff3c at mail.gmail.com> "Dan 
Mueller" <dan.muel at gmail.com> writes:
> 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
> 

-- 
Michal Plotkowiak
Doctoral Researcher
Oxford University LSI DTC