[Insight-users] fast marching behavior

[Luca Antiga]

Hi Dan,
  not at all, I was just referring to addressing the latest comments  
by Siqi.
I have the file on my desktop, waiting for me to handle it :-)

Luca


On Jan 8, 2010, at 5:18 PM, Dan Mueller wrote:

> 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