[Insight-developers] itkScalarImageKmeansImageFilter3DTest timeouts

[Luis Ibanez]

Hi Bill, Hans,


I'm looking at this problem,
and here is what I have found so far:


A) The code is not going into an infinite loop,
    but it is certainly requiring a *very long* time to run.


      One image of   10 x 10 x 10  takes   0.05  seconds
      One image of   40 x 40 x 40  takes   4.37  seconds
      One image of   60 x 60 x 60  takes  38.05  seconds
      One image of   70 x 70 x 70  takes 115.44  seconds


    As you can see the process is of order larger than O(n3).


B) When going back to the versions of

         itkStatisticsAlgorithm.h     -r 1.9
         itkStatisticsAlgorithm.txx   -r 1.19

    The test runs a lot faster but the output of the KdTree
    generator is not correct. (e.g. the points are not in the
    correct bins).  :-/

    The KMeans that are reported seem to be numerically reasonable,
    but that seems to be rather a coincidence.

    Going back to these versions doesn't seem to be an option,
    given that the computation is not correct.



C) I'm now using gprof to trace the functions that are taking
    most of the time. It may still be that we are making many
    unnecessary calls...

    I'm also trying to separate whether the problem is originated
    in the ScalarImageToListAdaptor or in the KdTree itself.
    Initial runs of gprof on the KMeans image filter reports a high
    usage of SmartPointers, which in general is not a good sign...



      Luis


--------------------
Bill Lorensen wrote:
> Folks,
> 
> The subject test has been timing out since it was checked in. This is
> a known bug. Unfortunately, this failing test causes cdash e-mails to
> be sent every day and for every checkin. I'm concerned that all of
> these e-mails and test failures on the dashboard will hide new
> problems. I have modified the CMakeLists.txt file to only report this
> timeout on one dashboard: dash16.kitware. This way, the error will not
> be forgotten (or maybe it already has been) and the excess e-mails
> will be prevented.
> 
> Bill
>