[Insight-users] fast marching behavior
Luca Antiga
luca.antiga at gmail.com
Thu Jan 7 16:56:10 EST 2010
Dan, Siqi,
the patch should be committed. I remember the original discussion,
we never followed up
committing the patch. It's time to do it.
However, since the fast marching method is probably used by a lot of
people, how about
adding a cmake flag to revert to the "wrong" implementation to ensure
backward compatibility?
Luca
On Jan 7, 2010, at 10:42 PM, siqi chen wrote:
>
> I think the patch correctly implements the FMM method described by
> Sethian.
>
> Thanks
> Siqi
>
>
> On Thu, Jan 7, 2010 at 1:54 PM, Dan Mueller <dan.muel at gmail.com>
> wrote:
> Hi Siqi,
>
> I managed to find some time to take a look at the issue you reported.
>
> I think the following patch will help:
> http://public.kitware.com/Bug/view.php?id=8990
>
> Here is the results I get with the patch applied:
>
> The distance from [50,50] to [49.7,49.8] is: 0.36
> The distance from [49,49] to [49.7,49.8] is: 1.06
> The distance from [49,50] to [49.7,49.8] is: 0.73
> The distance from [50,49] to [49.7,49.8] is: 0.85
> The distance from [48,49] to [49.7,49.8] is: 2.06
> The distance from [48,50] to [49.7,49.8] is: 1.73
> The distance from [49,48] to [49.7,49.8] is: 2.06
> The distance from [49,51] to [49.7,49.8] is: 1.73
> The distance from [50,48] to [49.7,49.8] is: 1.85
> The distance from [50,51] to [49.7,49.8] is: 1.36
> The distance from [51,49] to [49.7,49.8] is: 1.85
> The distance from [51,50] to [49.7,49.8] is: 1.36
>
> Is that what you expected?
>
> Hope this helps.
>
> Cheers, Dan
>
> 2010/1/5 siqi chen <siqichensc at gmail.com>:
> >
> > I read a few more papers and thought about the question number 2
> again. I
> > think there is misinterpretation on my part. The 4 neighbors of
> [49.7,49.8]
> > along their exact distance value should be set as Alive Points
> instead of
> > Trial Points. Then the neighbors of the 4 neighbors (another layer
> around
> > the 4 neighbors) are set as trial points, their initial tentative
> values are
> > calculated using upwind difference method. When I check the result
> distance
> > map, a few things to notice:
> > 1. The distance value of the 4 neighbors of [49.7, 49.8] are
> correct. This
> > is obvious since I set them as Known instead of Trial.
> > 2. The distance value of the neighbors of the 4 neighbors (the
> input trial
> > points) still changed. I think this is due to the inherent FMM
> accuracy and
> > update method.
> >
> > You can try this with the following code.
> > http://www.rpi.edu/~chens/download/main3.cpp
> >
> > Thanks
> > Siqi
> >
> > On Mon, Jan 4, 2010 at 6:03 PM, siqi chen <siqichensc at gmail.com>
> wrote:
> >>
> >> 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
> >>> >
> >>
> >
> >
> > _____________________________________
> > Powered by www.kitware.com
> >
> > Visit other Kitware open-source projects at
> > http://www.kitware.com/opensource/opensource.html
> >
> > Kitware offers ITK Training Courses, for more information visit:
> > http://www.kitware.com/products/protraining.html
> >
> > Please keep messages on-topic and check the ITK FAQ at:
> > http://www.itk.org/Wiki/ITK_FAQ
> >
> > Follow this link to subscribe/unsubscribe:
> > http://www.itk.org/mailman/listinfo/insight-users
> >
> >
>
> _____________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Kitware offers ITK Training Courses, for more information visit:
> http://www.kitware.com/products/protraining.html
>
> Please keep messages on-topic and check the ITK FAQ at:
> http://www.itk.org/Wiki/ITK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://www.itk.org/mailman/listinfo/insight-users
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20100107/92c82f53/attachment.htm>
More information about the Insight-users
mailing list