[Insight-users] fast marching behavior

[siqi chen]

To better illustrate my questions regarding fast marching, I put 2 example
code in the attachment.

In main1.cpp, I simply compute a distance map to point [50,50]. As you can
see from the output, the distances from the 4 neighbors of [50,50] to
[50,50] are correct, obviously the result is 1. However, the distance from
[51,51] to [50,50] is 1.707 instead of 1.414, which is obviously wrong. I
think this is due to the fast marching accuracy itself. If we switch to
higher order FMM, the result should be improved.

In main2.cpp, I perturb the target point a little bit. Instead, I want to
compute the distance map to point [49.7,49.8]. From my point of
understanding, I need to initialize the 4 neighbors of [49.7, 49.8] and put
them into the TrialPoints. As you can see, I compute the exact distance from
these 4 neighbors to [49.7,49.8] and put them into TrialPoints. However,
when I go back and check the result distance map, some thing is different.
The distances from these 4 neighbors to [49.7,49.8] are changed. As you can
see, the distance from [50,50] to [49.7,49.8] remains correct. This is
because this value is the smallest in the TrialPoints, therefore it is
pushed in to the AlivePoints heap first and the value is frozen since then.
I think there is something wrong here about whether to update trial points
value or not. If this trial point is user specified, then the value should
not be updated. I noticed a related discussion a couple of months ago in the
mailing list,
http://www.itk.org/pipermail/insight-users/2009-May/030282.html

http://www.rpi.edu/~chens/download/main1.cpp
http://www.rpi.edu/~chens/download/main2.cpp

Any input is appreciated.
Siqi


On Mon, Jan 4, 2010 at 3:32 PM, Dan Mueller <dan.muel at gmail.com> wrote:

> Hi Siqi,
>
> Indeed I am familiar with Fast Marching. I saw your question to the
> mailing list, but did not respond because I have not experienced what
> you describe: when I set the trial point value, that is the value in
> the arrival function.
>
> Perhaps you could post to the mailing list a minimal example
> (code+cmake+data) demonstrating your issue. That would make it really
> easy for me to help you!
>
> Cheers, Dan
>
> 2010/1/4 siqi chen <siqichensc at gmail.com>:
> > Hi, Dan,
> >
> > Sorry to bother you. From the ITK mailing list, I noticed you reported a
> bug
> > about FastMarchingImageFilter couple of months ago. So I guess you are a
> > fast marching expert : )
> >
> > I am trying to use FastMarchingImageFilter to calculate a distance map to
> a
> > set of points which have non-integer coordinates and I want the result to
> be
> > as accurate as possible. Here is what I did, but the result is not very
> > accurate.
> >
> > First I find the integer points which are the neighbors of the target
> points
> > and set these integer points as trial points. Then I use some
> interpolation
> > method to initialize the distance from these trial points to the target
> > points, which are assumed to be "exactly correct". The TrialPoints in the
> > FastMarchingImageFilter is defined as this set of trial points and their
> > corresponding distances to the target points. The AlivePoints is empty.
> When
> > I check the result distance map, I find that the distance value of these
> > trial points are changed, they are no longer what their initial states
> are.
> > Therefore, the iso curve deviate the original input a little bit. I am
> quite
> > confusing about this result.
> >
> > I noticed you mentioned on the mailing list about neighbor update, that
> is
> > to distinguish between user-specified trial points and
> algorithm-generated
> > trial points.  here is the discussion,
> > http://www.itk.org/pipermail/insight-users/2009-May/030282.html .  I
> wonder
> > if you have any suggestions about my problem.
> >
> > Any input is appreciated.
> >
> > Thanks
> > Siqi Chen
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20100104/56f634f7/attachment.htm>