[Insight-users] Problem with Fast marching minimal path extraction

[Dan Mueller]

Hi Maria,

I have located the issue. It is a problem with the Fast Marching
Minimal Path source code.

The speed functions I used when developing Fast Marching Minimal Path
where for vascular segmentation. These functions were basically white
(1.0) near the vessel centerline and black (0.0) outside the vessels.
Hence the arrival function were relatively smooth and continuous i.e.
there were no sharp changes in intensity (low first derivatives).

The speed function you are trying to use has a dark spot in which you
place a seed point. However, within this dark spot the arrival
function has large changes in intensity (high first derivatives)
because the front is moving slowing through the dark region.

In the file itkSingleImageCostFunction.txx, in the function
GetDerivative(), there is code at the bottom which sets the derivative
to 0.0 if it is above some constant threshold (currently set at 15.0
arrival time units). The derivatives in your image are much bigger
than 15.0 -- in the order of 50.0. By removing this code, or
significantly increasing the constant, I can get your image to work as
expected.

In short, change the following lines in
itk::SingleImageCostFunction::GetDerivative from

  // Convert the image function output to the cost function derivative
  const typename DerivativeType::ValueType DerivativeThreshold = 15.0;
  for (int i=0; i<ImageDimension; i++)
    {
    derivative[i] = static_cast<typename DerivativeType::ValueType>(
output[i] );

    // NOTE: The cost function may undefined / unreachable areas
    //		 (indicated by very large values) which may skew the gradient.
    //		 To avoid this skewing effect, we reset gradient values larger
    //		 than a given threshold.
    if ( vnl_math_abs(derivative[i]) > DerivativeThreshold )
      {
      derivative[i] = 0.0;
      }
    }

to

  // Convert the image function output to the cost function derivative
 for (int i=0; i<ImageDimension; i++)
    {
    derivative[i] = static_cast<typename DerivativeType::ValueType>(
output[i] );
    }

The proper way of solving this is to make the DerivativeThreshold a
user-specified parameter, which depends on the application.

HTH

Cheers, Dan

On 6 July 2011 17:35, Dan Mueller <dan.muel at gmail.com> wrote:
> Hi Maria,
>
> Can you please upload the exact speed image and start/end points you
> are trying to use?
>
> I suspect the issue is because the Fast Marching front (in ITK) does
> not expand into regions which have 0.0 speed values. One possibility
> is to scale your speed image to ensure no values are 0.0 (i.e. using
> RescaleIntensityImageFilter with max=1.0 and min=0.01).
>
> To quote the Insight Journal article:
>    pg 4. "Choosing an appropriate speed function is the most
> difficult part of the entire process"
>
> Cheers, Dan
>
> On 6 July 2011 17:13, Maria Alejandra Zuluaga Valencia
> <mariazulv at yahoo.es> wrote:
>> Hi Dan,
>> In order to provide you more information I did a small modification to the
>> SpeedFunctionToPathFilter. I have added an image writer so that I can save
>> what you call the current arrival function. At the same time, I compare the
>> result with a well-known toolbox in matlab that performs the fast marching
>> (btw, this is my final purpose; using itk instead of matlab). What I found
>> is that the arrival functions differ significantly (might the problem be on
>> the Fastmarching itself?). Moreover, I do obtain a path in matlab, no matter
>> the end point.
>> To illustrate you the situation I provide you screenshots of the matlab
>> results (example_D_one_.jpg and example_path_one.jpg files) and the arrival
>> function with itk (example_D_two.jpg), since no path is obtained. For this
>> example, I have used an image of mine. I was using your Synthetic-04-Speed
>> to evaluate  the filter, but I can't not read zraw in matlab, so that is why
>> I send you this other example. However, I will try to solve the zraw problem
>> so that I can run the matlab code in Synthetic-04-Speed.
>> Regarding your saying about the path, perhaps on an image as
>> Synthetic-04-Speed there should be no path when a point is badly placed (due
>> to the completely dark background) but, in the image as the one I am using I
>> think it should get something (as in matlab). I am not an expert but I
>> believe that one of the advantage/disadvantage of minimal paths approaches
>> is the fact that it will always find a path given two points. But, as I said
>> before, according to the results I am sending you, I believe the problem
>> seems to come from the arrival function and not from the path search. What
>> do you think?
>> Since my firewall does not allow me to attach files to emails, you can
>> obtain the screenshots here:
>> http://www.creatis.insa-lyon.fr/~zuluaga/fm_issues/
>> regards,
>> Maria
>> ps. If you want I can also send you the image of my examples, while I solve
>> the zraw problem. It is very small (184x184x23). I could place it on my
>> server.
>>  let me know if that sounds ok.
>>
>> ________________________________
>> De: Dan Mueller <dan.muel at gmail.com>
>> Para: Maria Alejandra Zuluaga Valencia <mariazulv at yahoo.es>
>> CC: "insight-users at itk.org" <insight-users at itk.org>
>> Enviado: miércoles 6 de julio de 2011 14:43
>> Asunto: Re: [Insight-users] Problem with Fast marching minimal path
>> extraction
>>
>> Hi Maria,
>>
>> Can you please provide some more information?
>>
>> Which synthetic image are you using? Where are you placing the seed point?
>>
>> I would not expect that every seed point will work -- the seed point
>> needs to be in a region which is reachable by the Fast Marching
>> expanding front. For example, placing the seed point in a region with
>> low speed (near 0.0) will not work.
>>
>> Attached are a few examples using different seed points.
>>
>> Regards, Dan
>>
>> On 5 July 2011 17:23, Maria Alejandra Zuluaga Valencia
>> <mariazulv at yahoo.es> wrote:
>>> Hi,
>>> I am trying to use the minimal path extraction algorithm reported in:
>>> http://hdl.handle.net/1926/1332
>>> After some minor compilation errors I managed to make it work. However, I
>>> found the behavior is a bit weird. As an example:
>>> if I test with one of the Synthetic images provided and the path points
>>> given, everything works fine. But, as soon as I change one of the path end
>>> points it stops working. By stop working I mean that the extracted path
>>> contains no points. I've tried with several examples and it is always the
>>> case.
>>>
>>> As far as I know, no matter how bad I place my end point, I should get a
>>> minimal path connecting the end and start points. Has any one had the same
>>> kind of problem? did you managed to fix it?
>>> thanks,
>>> Maria