<br>It definitely should be committed. I also have several suggestions about fastmarching implementation in ITK. <br><br>1. I think it&#39;s quite misleading to say that &quot;In order for the filter to evolve, at least some trial points must be specified.&quot; I think it should be &quot;at least some alive points must be specified&quot;. 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.<br>
<br>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.<br>
<br>3. Possible improvements. Current implementation is based on Prof. Sethian&#39; 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:<br>
<a href="http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=841">http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=841</a> .  <br><br>Thanks<br>Siqi<br><br><br><div class="gmail_quote">On Thu, Jan 7, 2010 at 4:56 PM, Luca Antiga <span dir="ltr">&lt;<a href="mailto:luca.antiga@gmail.com">luca.antiga@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div style="word-wrap: break-word;"><div>Dan, Siqi,</div><div> the patch should be committed. I remember the original discussion, we never followed up</div>
<div>committing the patch. It&#39;s time to do it.</div><div>However, since the fast marching method is probably used by a lot of people, how about</div><div>adding a cmake flag to revert to the &quot;wrong&quot; implementation to ensure backward compatibility?</div>
<div><br></div><font color="#888888"><div><br></div><div>Luca</div></font><div><div></div><div class="h5"><div><br></div><br><div><div>On Jan 7, 2010, at 10:42 PM, siqi chen wrote:</div><br><blockquote type="cite"><br>I think the patch correctly implements the FMM method described by Sethian. <br>
<br>Thanks<br>Siqi<br><br><br><div class="gmail_quote">On Thu, Jan 7, 2010 at 1:54 PM, Dan Mueller <span dir="ltr">&lt;<a href="mailto:dan.muel@gmail.com" target="_blank">dan.muel@gmail.com</a>&gt;</span> wrote:<br> <blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi Siqi,<br> <br> I managed to find some time to take a look at the issue you reported.<br> <br> I think the following patch will help:<br>    <a href="http://public.kitware.com/Bug/view.php?id=8990" target="_blank">http://public.kitware.com/Bug/view.php?id=8990</a><br>
 <br> Here is the results I get with the patch applied:<br> <br> The distance from [50,50] to [49.7,49.8] is: 0.36<br> The distance from [49,49] to [49.7,49.8] is: 1.06<br> The distance from [49,50] to [49.7,49.8] is: 0.73<br>
 The distance from [50,49] to [49.7,49.8] is: 0.85<br> The distance from [48,49] to [49.7,49.8] is: 2.06<br> The distance from [48,50] to [49.7,49.8] is: 1.73<br> The distance from [49,48] to [49.7,49.8] is: 2.06<br> The distance from [49,51] to [49.7,49.8] is: 1.73<br>
 The distance from [50,48] to [49.7,49.8] is: 1.85<br> The distance from [50,51] to [49.7,49.8] is: 1.36<br> The distance from [51,49] to [49.7,49.8] is: 1.85<br> The distance from [51,50] to [49.7,49.8] is: 1.36<br> <br>
 Is that what you expected?<br> <br> Hope this helps.<br> <br> Cheers, Dan<br> <br> 2010/1/5 siqi chen &lt;<a href="mailto:siqichensc@gmail.com" target="_blank">siqichensc@gmail.com</a>&gt;:<br> <div><div></div><div>&gt;<br>
 &gt; I read a few more papers and  thought about the question number 2 again. I<br> &gt; think there is misinterpretation on my part. The 4 neighbors of [49.7,49.8]<br> &gt; along their exact distance value should be set as Alive Points instead of<br>
 &gt; Trial Points. Then the neighbors of the 4 neighbors (another layer around<br> &gt; the 4 neighbors) are set as trial points, their initial tentative values are<br> &gt; calculated using upwind difference method. When I check the result distance<br>
 &gt; map, a few things to notice:<br> &gt; 1. The distance value of the 4 neighbors of [49.7, 49.8] are correct. This<br> &gt; is obvious since I set them as Known instead of Trial.<br> &gt; 2. The distance value of the neighbors of the 4 neighbors (the input trial<br>
 &gt; points) still changed. I think this is due to the inherent FMM accuracy and<br> &gt; update method.<br> &gt;<br> &gt; You can try this with the following code.<br> &gt; <a href="http://www.rpi.edu/%7Echens/download/main3.cpp" target="_blank">http://www.rpi.edu/~chens/download/main3.cpp</a><br>
 &gt;<br> &gt; Thanks<br> &gt; Siqi<br> &gt;<br> &gt; On Mon, Jan 4, 2010 at 6:03 PM, siqi chen &lt;<a href="mailto:siqichensc@gmail.com" target="_blank">siqichensc@gmail.com</a>&gt; wrote:<br> &gt;&gt;<br> &gt;&gt; To better illustrate my questions regarding fast marching, I put 2 example<br>
 &gt;&gt; code in the attachment.<br> &gt;&gt;<br> &gt;&gt; In main1.cpp, I simply compute a distance map to point [50,50]. As you can<br> &gt;&gt; see from the output, the distances from the 4 neighbors of [50,50] to<br>
 &gt;&gt; [50,50] are correct, obviously the result is 1. However, the distance from<br> &gt;&gt; [51,51] to [50,50] is 1.707 instead of 1.414, which is obviously wrong. I<br> &gt;&gt; think this is due to the fast marching accuracy itself. If we switch to<br>
 &gt;&gt; higher order FMM, the result should be improved.<br> &gt;&gt;<br> &gt;&gt; In main2.cpp, I perturb the target point a little bit. Instead, I want to<br> &gt;&gt; compute the distance map to point [49.7,49.8]. From my point of<br>
 &gt;&gt; understanding, I need to initialize the 4 neighbors of [49.7, 49.8] and put<br> &gt;&gt; them into the TrialPoints. As you can see, I compute the exact distance from<br> &gt;&gt; these 4 neighbors to [49.7,49.8] and put them into TrialPoints. However,<br>
 &gt;&gt; when I go back and check the result distance map, some thing is different.<br> &gt;&gt; The distances from these 4 neighbors to [49.7,49.8] are changed. As you can<br> &gt;&gt; see, the distance from [50,50] to [49.7,49.8] remains correct. This is<br>
 &gt;&gt; because this value is the smallest in the TrialPoints, therefore it is<br> &gt;&gt; pushed in to the AlivePoints heap first and the value is frozen since then.<br> &gt;&gt; I think there is something wrong here about whether to update trial points<br>
 &gt;&gt; value or not. If this trial point is user specified, then the value should<br> &gt;&gt; not be updated. I noticed a related discussion a couple of months ago in the<br> &gt;&gt; mailing list,<br> &gt;&gt; <a href="http://www.itk.org/pipermail/insight-users/2009-May/030282.html" target="_blank">http://www.itk.org/pipermail/insight-users/2009-May/030282.html</a><br>
 &gt;&gt;<br> &gt;&gt; <a href="http://www.rpi.edu/%7Echens/download/main1.cpp" target="_blank">http://www.rpi.edu/~chens/download/main1.cpp</a><br> &gt;&gt; <a href="http://www.rpi.edu/%7Echens/download/main2.cpp" target="_blank">http://www.rpi.edu/~chens/download/main2.cpp</a><br>
 &gt;&gt;<br> &gt;&gt; Any input is appreciated.<br> &gt;&gt; Siqi<br> &gt;&gt;<br> &gt;&gt;<br> &gt;&gt; On Mon, Jan 4, 2010 at 3:32 PM, Dan Mueller &lt;<a href="mailto:dan.muel@gmail.com" target="_blank">dan.muel@gmail.com</a>&gt; wrote:<br>
 &gt;&gt;&gt;<br> &gt;&gt;&gt; Hi Siqi,<br> &gt;&gt;&gt;<br> &gt;&gt;&gt; Indeed I am familiar with Fast Marching. I saw your question to the<br> &gt;&gt;&gt; mailing list, but did not respond because I have not experienced what<br>
 &gt;&gt;&gt; you describe: when I set the trial point value, that is the value in<br> &gt;&gt;&gt; the arrival function.<br> &gt;&gt;&gt;<br> &gt;&gt;&gt; Perhaps you could post to the mailing list a minimal example<br> &gt;&gt;&gt; (code+cmake+data) demonstrating your issue. That would make it really<br>
 &gt;&gt;&gt; easy for me to help you!<br> &gt;&gt;&gt;<br> &gt;&gt;&gt; Cheers, Dan<br> &gt;&gt;&gt;<br> &gt;&gt;&gt; 2010/1/4 siqi chen &lt;<a href="mailto:siqichensc@gmail.com" target="_blank">siqichensc@gmail.com</a>&gt;:<br>
 &gt;&gt;&gt; &gt; Hi, Dan,<br> &gt;&gt;&gt; &gt;<br> &gt;&gt;&gt; &gt; Sorry to bother you. From the ITK mailing list, I noticed you reported<br> &gt;&gt;&gt; &gt; a bug<br> &gt;&gt;&gt; &gt; about FastMarchingImageFilter couple of months ago. So I guess you are<br>
 &gt;&gt;&gt; &gt; a<br> &gt;&gt;&gt; &gt; fast marching expert : )<br> &gt;&gt;&gt; &gt;<br> &gt;&gt;&gt; &gt; I am trying to use FastMarchingImageFilter to calculate a distance map<br> &gt;&gt;&gt; &gt; to a<br> &gt;&gt;&gt; &gt; set of points which have non-integer coordinates and I want the result<br>
 &gt;&gt;&gt; &gt; to be<br> &gt;&gt;&gt; &gt; as accurate as possible. Here is what I did, but the result is not very<br> &gt;&gt;&gt; &gt; accurate.<br> &gt;&gt;&gt; &gt;<br> &gt;&gt;&gt; &gt; First I find the integer points which are the neighbors of the target<br>
 &gt;&gt;&gt; &gt; points<br> &gt;&gt;&gt; &gt; and set these integer points as trial points. Then I use some<br> &gt;&gt;&gt; &gt; interpolation<br> &gt;&gt;&gt; &gt; method to initialize the distance from these trial points to the target<br>
 &gt;&gt;&gt; &gt; points, which are assumed to be &quot;exactly correct&quot;. The TrialPoints in<br> &gt;&gt;&gt; &gt; the<br> &gt;&gt;&gt; &gt; FastMarchingImageFilter is defined as this set of trial points and<br> &gt;&gt;&gt; &gt; their<br>
 &gt;&gt;&gt; &gt; corresponding distances to the target points. The AlivePoints is empty.<br> &gt;&gt;&gt; &gt; When<br> &gt;&gt;&gt; &gt; I check the result distance map, I find that the distance value of<br> &gt;&gt;&gt; &gt; these<br>
 &gt;&gt;&gt; &gt; trial points are changed, they are no longer what their initial states<br> &gt;&gt;&gt; &gt; are.<br> &gt;&gt;&gt; &gt; Therefore, the iso curve deviate the original input a little bit. I am<br> &gt;&gt;&gt; &gt; quite<br>
 &gt;&gt;&gt; &gt; confusing about this result.<br> &gt;&gt;&gt; &gt;<br> &gt;&gt;&gt; &gt; I noticed you mentioned on the mailing list about neighbor update, that<br> &gt;&gt;&gt; &gt; is<br> &gt;&gt;&gt; &gt; to distinguish between user-specified trial points and<br>
 &gt;&gt;&gt; &gt; algorithm-generated<br> &gt;&gt;&gt; &gt; trial points.  here is the discussion,<br> &gt;&gt;&gt; &gt; <a href="http://www.itk.org/pipermail/insight-users/2009-May/030282.html" target="_blank">http://www.itk.org/pipermail/insight-users/2009-May/030282.html</a> .  I<br>
 &gt;&gt;&gt; &gt; wonder<br> &gt;&gt;&gt; &gt; if you have any suggestions about my problem.<br> &gt;&gt;&gt; &gt;<br> &gt;&gt;&gt; &gt; Any input is appreciated.<br> &gt;&gt;&gt; &gt;<br> &gt;&gt;&gt; &gt; Thanks<br> &gt;&gt;&gt; &gt; Siqi Chen<br>
 &gt;&gt;&gt; &gt;<br> &gt;&gt;<br> &gt;<br> &gt;<br> </div></div>&gt; _____________________________________<br> &gt; Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br> &gt;<br> &gt; Visit other Kitware open-source projects at<br>
 &gt; <a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br> &gt;<br> &gt; Kitware offers ITK Training Courses, for more information visit:<br>
 &gt; <a href="http://www.kitware.com/products/protraining.html" target="_blank">http://www.kitware.com/products/protraining.html</a><br> &gt;<br> &gt; Please keep messages on-topic and check the ITK FAQ at:<br> &gt; <a href="http://www.itk.org/Wiki/ITK_FAQ" target="_blank">http://www.itk.org/Wiki/ITK_FAQ</a><br>
 &gt;<br> &gt; Follow this link to subscribe/unsubscribe:<br> &gt; <a href="http://www.itk.org/mailman/listinfo/insight-users" target="_blank">http://www.itk.org/mailman/listinfo/insight-users</a><br> &gt;<br> &gt;<br> </blockquote>
</div><br> _____________________________________<br>Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br><br>Visit other Kitware open-source projects at<br><a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>Kitware offers ITK Training Courses, for more information visit:<br><a href="http://www.kitware.com/products/protraining.html" target="_blank">http://www.kitware.com/products/protraining.html</a><br><br>Please keep messages on-topic and check the ITK FAQ at:<br>
<a href="http://www.itk.org/Wiki/ITK_FAQ" target="_blank">http://www.itk.org/Wiki/ITK_FAQ</a><br><br>Follow this link to subscribe/unsubscribe:<br><a href="http://www.itk.org/mailman/listinfo/insight-users" target="_blank">http://www.itk.org/mailman/listinfo/insight-users</a><br>
</blockquote></div><br></div></div></div></blockquote></div><br>