[Insight-users] fast marching behavior

[Dan Mueller]

Hi Luca,

Is there anything wrong with the "FastMarching.patch" file attached to
the bug entry?
    http://public.kitware.com/Bug/view.php?id=8990

2010/1/8 Luca Antiga <luca.antiga at gmail.com>:
> Hi Siqi,
>  I understand your points. We have to find a solution that guarantees
> backwards compatibility, we cannot switch to setting Alive points
> altogether.
> My proposal is to use the distinction between Trial points and InitialTrial
> points in Dan's patch, and to add a flag that will decide whether
> InitialTrial points should be updated or not. This will solve the problem
> maintaining backwards compatibility. With no updating allowed, InitialTrial
> points will behave just like you wish, and we won't have to write extra code
> for computing the initial layer around Alive points.
> Let me know if you agree with this.
> Dan, I appreciate the lack of time, and I must say we're pretty much on the
> same boat. However, this issue carries some weight. As soon as we devise an
> acceptable solution, I'm willing to put in some time to commit the patch and
> take care of the rest.
> Best regards
> Luca
>
>
>
> On Jan 8, 2010, at 4:06 PM, siqi chen wrote:
>
> The reason I suggest to let the algorithm compute the initial trial is the
> following:
>
> If we want to compute a distance map to a perfect circle. The first thing we
> do is to discretize the circle, of course, most of the points will be
> non-integer coordinates. To initialize the algorithm, we need to find the 4
> neighbor lattice of the discretized circle points and calculate the exact
> distance from these lattice to the circle. In my humble opinion, in the
> current ITK implementation, the algorithm accepts these lattice points as
> "TrialPoints". As I illustrated before, since the FMM method will update the
> values of trial points if the new value is smaller, it is very likely that
> after the FMM sweeping, the value of the these lattice (the immediate 4
> neighbors of the circle) will change. This will introduce large errors if we
> compare the zero iso curve of the result distance to the initial circle.
>
> To fix this problem, there are two options:
> 1. Distinguish between the user input trial and the algorithm generated
> trial as you guys mentioned before. If it's a user input trial, then don't
> update the value at all.
> 2. Set these immediate 4 neighbors as KnownPoints, and let the user compute
> another layer outside these knownpoints and set them as trial points. This
> is quite tedious for the user, since they need to figure out the "upwind"
> themselves. Again, according to the FMM algorithm itself, this initial trial
> computation should be done by the algorithm, not the user. That's why I
> think we should let the algorithm to compute the initial trial.
>
> Thanks
> Siqi
>
> On Thu, Jan 7, 2010 at 6:07 PM, Luca Antiga <luca.antiga at gmail.com> wrote:
>>
>> Hi Siqi,
>>  this sounds like a perfect contribution for the Insight Journal.
>> I suggest to write a new class for the second-order implementation.
>> As for the minheap, I agree with you, it would save some memory.
>> As for setting trial points: in the current implementation, if you don't
>> set trial points you won't have anything to process in the TrialHeap.
>> I understand your point, but I am kind of in favor of the current way of
>> working. Setting alive points doesn't necessarily mean that you want
>> the solution to propagate automatically starting from their boundary
>> with far points.
>> This could indeed be an option, but it's not
>> necessarily always practically
>> convenient. Is there any particular reason why you wouldn't want to set
>> your
>> initial points as trial?
>>
>> Luca
>>
>> On Jan 7, 2010, at 11:47 PM, siqi chen wrote:
>>
>> It definitely should be committed. I also have several suggestions about
>> fastmarching implementation in ITK.
>>
>> 1. I think it's quite misleading to say that "In order for the filter to
>> evolve, at least some trial points must be specified." I think it should be
>> "at least some alive points must be specified". The initial trial points
>> should be calculated by the algorithm itself, not by the user. For example,
>> when I start with FastMarchingImageFilter, I want to try a simple example of
>> calculating a distance map to [50,50], Mr. Kevin Hobbs told me the right way
>> is to set [50,50] as trial point. However, I think it is not right
>> description. The right way is to set [50,50] as alive points, and the
>> algorithm computes the initial trial points and start the iteration.
>>
>> 2. Another thing is about heap implementation. Currently,
>> std::priority_queue is used, and there is some issue as Doxygen described.
>> I think we can use a minheap as the basic data structure. I wrote a VTK fast
>> maching filter yesterday and I used this min heap data structure.
>>
>> 3. Possible improvements. Current implementation is based on Prof.
>> Sethian' s work, which is actually a first order approximation of distance
>> map. This implementation will introduce large errors in the diagonal
>> direction. With a little bit change of code, we can implement a higher order
>> accuracy FMM method. The detail can be found here:
>> http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=841 .
>>
>> Thanks
>> Siqi