[Insight-users] Kd-tree implementation in ITK is buggy and unreliable
Luis Ibanez
luis.ibanez at kitware.com
Tue Apr 29 13:39:39 EDT 2008
Well,
So how about the following:
if( NumericTraits< MeasurementType >::is_signed )
{
lowerBound[d] = -vcl_sqrt(NumericTraits< MeasurementType >::max())/2.0;
upperBound[d] = vcl_sqrt(NumericTraits< MeasurementType >::max())/2.0;
}
else
{
lowerBound[d] = NumericTraits< MeasurementType >::Zero;
upperBound[d] = vcl_sqrt(NumericTraits< MeasurementType >::max())/2.0;
}
I guess this would do the trick, isn't it ?
Luis
---------------------------
Bill Lorensen wrote:
> I believe that -0 is OK.
>
> BTW, it is vcl_sqrt(), not vcl_sqr()
>
> On Tue, Apr 29, 2008 at 1:08 PM, Luis Ibanez <luis.ibanez at kitware.com> wrote:
>
>>What will be the right way of doing this when
>>the MeasurementType is "unsigned char" ?
>>
>>Should we do something like checking if the
>>type is signed before we use -vcl_sqr() ?
>>
>>
>> Luis
>>
>>
>>---------------------
>>
>>
>>Bill Lorensen wrote:
>>
>>>No, you need the sqrt.
>>>
>>>On Tue, Apr 29, 2008 at 12:27 PM, Luis Ibanez <luis.ibanez at kitware.com>
>>
>>wrote:
>>
>>>
>>>>Hi Bill,
>>>>
>>>>
>>>>I undid part of those changes this
>>>>morining when fixing compiler warnings :-(
>>>>
>>>>...
>>>>
>>>>Here is the problem,
>>>>
>>>>In the effort to reduce the bounds
>>>>
>>
>>http://public.kitware.com/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkKdTree.txx?root=Insight&r1=1.23&r2=1.24
>>
>>>>the code used:
>>>>
>>>>lowerBound[d] = -vcl_sqrt(NumericTraits< MeasurementType >::max())/2.0;
>>>>
>>>>but some of the examples use MeasurementTypes that are unsinged,
>>>>and the negative value is misinterpreted in that context. In
>>>>general we cannot assume that the vector use signed components.
>>>>
>>>>The code above was replaced with
>>>>
>>
>>http://public.kitware.com/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkKdTree.txx?root=Insight&r1=1.23&r2=1.26
>>
>>>>
>>>>lowerBound[d] =
>>>> NumericTraits< MeasurementType >::NonpositiveMin() / 2.0;
>>>>
>>>>
>>>>It is missing the sqrt() part of your fix...
>>>>
>>>>Do you think that the 1/2.0 factor may be enough for
>>>>dealing with the numerical overflow ?
>>>>
>>>>
>>>>----
>>>>
>>>>BTW: Somewere in the MeanShift class there is a mislead
>>>> typedef for MeasurementType.
>>>>
>>>> I had to add the declaration:
>>>>typedef typename TSample::MeasurementType MeasurementType;
>>>>
>>>> in order to avoid conversion warnings with gcc.
>>>>
>>>>
>>>>
>>>>
>>>> Luis
>>>>
>>>>
>>>>
>>>>---------------------
>>>>
>>>>
>>>>Bill Lorensen wrote:
>>>>
>>>>
>>>>
>>>>>I committed last night. You should see the results on tomorrow's
>>>>>
>>>>
>>>>dashboard.
>>>>
>>>>
>>>>
>>>>>Bill
>>>>>
>>>>>On Tue, Apr 29, 2008 at 11:43 AM, Luis Ibanez
>>
>><luis.ibanez at kitware.com>
>>
>>>>wrote:
>>>>
>>>>
>>>>
>>>>>
>>>>>>Hi Bill,
>>>>>>
>>>>>> Great !
>>>>>>
>>>>>>
>>>>>>Have you committed the fix ?
>>>>>>Or, could you post the patch
>>>>>>
>>>>>>
>>>>>>On a parallel note,
>>>>>>I'm tracking the problem with the time out
>>>>>>of about 6 test. The new version of QuickSelect
>>>>>>fails for cases where there are many repeated
>>>>>>values in the collection. I'm looking at
>>>>>>replacing it with the implementation of
>>>>>>NthElement from STL.
>>>>>>
>>>>>>
>>>>>>
>>>>>>Thanks
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> Luis
>>>>>>
>>>>>>
>>>>>>-------------------
>>>>>>Bill Lorensen wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>Luis,
>>>>>>>
>>>>>>>I fixed the floating point overflow problem in KdTree.
>>>>>>>
>>>>>>>Bill
>>>>>>>
>>>>>>>On Mon, Apr 28, 2008 at 8:21 AM, Luis Ibanez
>>
>><luis.ibanez at kitware.com>
>>
>>>>>>>
>>>>>>wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>>>Hi Ali,
>>>>>>>>
>>>>>>>>
>>>>>>>>A quick update on the status of this problem:
>>>>>>>>
>>>>>>>>
>>>>>>>>Bugs were identified and fixed at the level of the
>>>>>>>>StatisticsAlgorithms:
>>>>>>>>
>>>>>>>>* Partition
>>>>>>>>* QuickSelect
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkStatisticsAlgorithm.txx?root=Insight&r1=1.19&r2=1.21&sortby=date
>>
>>>>
>>>>>>
>>http://www.itk.org/cgi-bin/viewcvs.cgi/Code/Numerics/Statistics/itkKdTreeGenerator.txx?root=Insight&r1=1.14&r2=1.18&sortby=date
>>
>>>>
>>>>>>
>>>>>>>>Explicit tests were added for
>>>>>>>>
>>>>>>>>* QuickSelect
>>>>>>>>* KdTree
>>>>>>>>* KdTreeGenerator
>>>>>>>>
>>>>>>>>(about 12 new tests).
>>>>>>>>
>>>>>>>>These new tests are passing.
>>>>>>>>
>>>>>>>>
>>>>>>>>There are still side effects in the following (now failing)
>>
>>tests
>>
>>>>>>>>* BayesianClassifierInitializeTest
>>>>>>>>* itkSampleMeanSjhiftClusteringFilterTest
>>>>>>>>* RBFTest1
>>>>>>>>* ScalarImageKmeansClassifierTest
>>>>>>>>
>>>>>>>>They are currently timing-out, (probably due to infinite-loops)
>>>>>>>>We suspect that they are related to the
>>>>>>>>
>>>>>>>
>>>>WeightedCentroidKdTreeGenerator
>>>>
>>>>
>>>>
>>>>>>>>(but that is only early speculation).
>>>>>>>>
>>>>>>>>
>>>>>>>>We are now tracking those issues...
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>Luis
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>--------------------
>>>>>>>>Luis Ibanez wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>Hi Bill,
>>>>>>>>>
>>>>>>>>>Yeap, the problem was in the combination of QuickSelect and
>>>>>>>>>
>>>>>>>>
>>>>Partition.
>>>>
>>>>
>>>>
>>>>>>>>>Both of them are defined in
>>>>>>>>>
>>>>>>>>>Insight/Code/Numerics/Statistics/itkStatisticsAlgorithms.txx
>>>>>>>>>
>>>>>>>>>Sorting the list before QuickSelect would only work when the
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>measurement
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>vector has a single dimension. Otherwise, a single sort can
>>
>>not
>>
>>>>>>>>>
>>>>>>>>
>>>>>>possibly
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>organize the list in all dimensions. We could call sort just
>>>>>>>>>
>>>>>>>>
>>>>before
>>>>
>>>>
>>>>
>>>>>>>>>Partition, to sort the activeDimension, but this is an
>>
>>overkill,
>>
>>>>since
>>>>
>>>>
>>>>
>>>>>>>>>Partition is indeed intended for parforming a partial sorting.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>I have replaced both the QuickSelect and Partition functions
>>
>>with
>>
>>>>>>>>>implementations based on the description of the Partition and
>>>>>>>>>QuickSelect algorithms in the Wikipedia:
>>>>>>>>>
>>>>>>>>>http://en.wikipedia.org/wiki/Quickselect
>>>>>>>>>
>>>>>>>>>This works fine for KdTreeTest1 and KdTreeTest2.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>However, the test for the StatisticsAlgorithms itself fails
>>>>>>>>>
>>>>>>>>
>>>>(timesout)
>>>>
>>>>
>>>>
>>>>>>>>>due to the fact that its list contains multiple entries with
>>>>>>>>>values equal to the partition value. A case that is not
>>
>>considered
>>
>>>>>>>>>in the current algorithm. The current algorithm enters into an
>>>>>>>>>infinite loop in this case.
>>>>>>>>>
>>>>>>>>>I'm modifying the implementation for covering that case.
>>>>>>>>>
>>>>>>>>>--
>>>>>>>>>
>>>>>>>>>BTW, about 10 test more were added, for exercising the KdTree
>>>>>>>>>at different bucket sizes.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>To be revisited: The tests in Borland are producing
>>
>>floating-point
>>
>>>>>>>>> overflows... not a good sign. There are possible
>>>>>>>>> other issues in the computation.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>Luis
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>---------------------
>>>>>>>>>Bill Lorensen wrote:
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>Luis,
>>>>>>>>>>
>>>>>>>>>>I think the main problem is that the samples need to be
>>
>>sorted.
>>
>>>>I
>>>>
>>>>
>>>>
>>>>>>added:
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>HeapSort<SubsampleType>(m_Subsample, partitionDimension,
>>>>>>>>>>
>>>>>>>>>
>>>>beginIndex,
>>>>
>>>>
>>>>
>>>>>>>>>>endIndex);
>>>>>>>>>>just before the QuickSelect call and itkKdTreeTest1 passes
>>>>>>>>>>consistently.
>>>>>>>>>>
>>>>>>>>>>However, this is not a good fix. I think the QuickSelect
>>
>>code
>>
>>>>should
>>>>
>>>>
>>>>
>>>>>>>>>>work. Probably the error is in Partition. It should group a
>>
>>list
>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>into
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>two parts, one less than the partition value and another
>>
>>greater
>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>than
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>or equal the value. Currently it looks like Partition
>>
>>assumes
>>
>>>>the
>>>>
>>>>
>>>>
>>>>>>list
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>is sorted.
>>>>>>>>>>
>>>>>>>>>>BTW, itkKdTreeTest2 produces a tree different from the one
>>
>>in
>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>wikipedia.
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>HTH,
>>>>>>>>>>Bill
>>>>>>>>>>
>>>>>>>>>>On Fri, Apr 25, 2008 at 12:59 PM, Luis Ibanez
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>><luis.ibanez at kitware.com>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>Hi Ali,
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>An update on the KdTree segmentation fault
>>>>>>>>>>>(that may or may not be related to the problem that you
>>>>>>>>>>>
>>>>>>>>>>
>>>>observe).
>>>>
>>>>
>>>>
>>>>>>>>>>>This test is running the example tree provided in the
>>>>>>>>>>>
>>>>>>>>>>
>>>>Wikipedia
>>>>
>>>>
>>>>
>>>>>>>>>>>http://en.wikipedia.org/wiki/Kdtree
>>>>>>>>>>>http://en.wikipedia.org/wiki/Kdtree#Constructing_a_kd-tree
>>>>>>>>>>>
>>>>>>>>>>>We are feeding the set of points:
>>>>>>>>>>>
>>>>>>>>>>> (2,3), (5,4), (9,6), (4,7), (8,1), (7,2)
>>>>>>>>>>>
>>>>>>>>>>>and expecting to get the tree:
>>>>>>>>>>>http://upload.wikimedia.org/wikipedia/en/f/f1/Kd_tree.png
>>>>>>>>>>>
>>>>>>>>>>> (7,2)
>>>>>>>>>>> /\
>>>>>>>>>>> / \
>>>>>>>>>>> / \
>>>>>>>>>>> (5,4) (9,6)
>>>>>>>>>>> /\ \
>>>>>>>>>>> / \ \
>>>>>>>>>>> / \ \
>>>>>>>>>>> (2,3) (4,7) (8,1)
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>Here is what we currently observe as output for different
>>>>>>>>>>>bucket sizes:
>>>>>>>>>>>
>>>>>>>>>>>-----
>>>>>>>>>>>
>>>>>>>>>>>Case BucketSize == 1:
>>>>>>>>>>>
>>>>>>>>>>>The segmentation fault of itkKdTreeTest2 with
>>
>>BucketSize==1
>>
>>>>>>>>>>>happens because the recursive function:
>>>>>>>>>>>
>>>>>>>>>>>KdTreeGenerator::GenerateTreeLoop() (line 179)
>>>>>>>>>>>
>>>>>>>>>>>ends up calling itself indifinitely, until it overflows
>>
>>the
>>
>>>>stack.
>>>>
>>>>
>>>>
>>>>>>>>>>>It enter in an infinite (recursive) loop calling:
>>>>>>>>>>>
>>>>>>>>>>>GenerateTreeLoop( 0, 0, level++)
>>>>>>>>>>>GenerateTreeLoop( 0, 2, level++)
>>>>>>>>>>>GenerateTreeLoop( 0, 0, level++)
>>>>>>>>>>>GenerateTreeLoop( 0, 2, level++)
>>>>>>>>>>>GenerateTreeLoop( 0, 0, level++)
>>>>>>>>>>>GenerateTreeLoop( 0, 2, level++)
>>>>>>>>>>>....
>>>>>>>>>>>
>>>>>>>>>>>where "0" and "2" here are the indexes of the points in
>>
>>the
>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>sample.
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>>-----
>>>>>>>>>>>
>>>>>>>>>>>Case BucketSize == 2:
>>>>>>>>>>>
>>>>>>>>>>>The segmentation fault of itkKdTreeTest2 with
>>
>>BucketSize==2
>>
>>>>>>>>>>>happens also because the recursive function:
>>>>>>>>>>>
>>>>>>>>>>>KdTreeGenerator::GenerateTreeLoop() (line 179)
>>>>>>>>>>>
>>>>>>>>>>>ends up calling itself indifinitely, until it overflows
>>
>>the
>>
>>>>stack.
>>>>
>>>>
>>>>
>>>>>>>>>>>It enter in an infinite (recursive) loop calling:
>>>>>>>>>>>
>>>>>>>>>>>GenerateTreeLoop( 3, 3, level++)
>>>>>>>>>>>GenerateTreeLoop( 3, 6, level++)
>>>>>>>>>>>GenerateTreeLoop( 3, 3, level++)
>>>>>>>>>>>GenerateTreeLoop( 3, 6, level++)
>>>>>>>>>>>GenerateTreeLoop( 3, 3, level++)
>>>>>>>>>>>GenerateTreeLoop( 3, 6, level++)
>>>>>>>>>>>....
>>>>>>>>>>>
>>>>>>>>>>>where "3" and "6" here are the indexes of the points in
>>
>>the
>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>sample.
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>>-----
>>>>>>>>>>>
>>>>>>>>>>>Case BucketSize == 3:
>>>>>>>>>>>
>>>>>>>>>>>When using a bucket size of 3, the function
>>
>>GenerateTreeLoop()
>>
>>>>>>>>>>>is being called only once, but it generates the following
>>
>>tree
>>
>>>>>>>>>>> NTN
>>>>>>>>>>> /\
>>>>>>>>>>> / \
>>>>>>>>>>> / \
>>>>>>>>>>>[(2,3),(4,7)] NTN
>>>>>>>>>>> /\
>>>>>>>>>>> / \
>>>>>>>>>>> / \
>>>>>>>>>>> [(8,1)] [ (7,2) (5,4) (9,6)]
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>Where "NTN" stands for "non-terminal node".
>>>>>>>>>>>and the groups with parenthesis "[ ]" represent buckets.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>That is a first plane dividing the space at X=4.5
>>>>>>>>>>>One bucket on the left for points with X values < 4.5
>>>>>>>>>>>and on the right, a second plane dividing the space
>>>>>>>>>>>at Y = 1.5, to create on bucket on the left with (8,1)
>>>>>>>>>>>and on the right another bucket with points with Y values
>>>>>>>>>>>larger than 1.5, namely: [ (7,2) (5,4) (9,6)]
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>-----
>>>>>>>>>>>
>>>>>>>>>>>Case BucketSize == 4:
>>>>>>>>>>>
>>>>>>>>>>>When using a bucket size of 4 , the function
>>>>>>>>>>>
>>>>>>>>>>
>>>>GenerateTreeLoop()
>>>>
>>>>
>>>>
>>>>>>>>>>>is being called three times, and it generates the
>>
>>following
>>
>>>>tree
>>>>
>>>>
>>>>
>>>>>>>>>>> NTN
>>>>>>>>>>> /\
>>>>>>>>>>> / \
>>>>>>>>>>> / \
>>>>>>>>>>>[(2,3),(4,7)] [(8,1) (7,2) (5,4) (9,6)]
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>That is a single plane dividing the space at X=4.5
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>----------
>>>>>>>>>>>
>>>>>>>>>>>In either case,
>>>>>>>>>>>the partition is not what we could expect from a KdTree...
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>Just to clarify, the real problem seems to be in the
>>>>>>>>>>>implementation of the algorithm in the KdTreeGenerator,
>>>>>>>>>>>not in the KdTree class itself...
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>Luis
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>-------------------
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>Luis Ibanez wrote:
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>Hi Ali,
>>>>>>>>>>>>
>>>>>>>>>>>>Thanks for the additinonal information.
>>>>>>>>>>>>
>>>>>>>>>>>>Yeap, the algorithm should work regardless
>>>>>>>>>>>>of the bucket size. That one was a false alarm.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>I'm tracking now the cases where itkKdTreeTest2
>>
>>segfaults
>>
>>>>>>>>>>>>with a bucket size == 2. Hopefully this will illuminate
>>>>>>>>>>>>at least part of the problem.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>Thanks
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>Luis
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>---------------
>>>>>>>>>>>>Ali - wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>Luis,
>>>>>>>>>>>>>
>>>>>>>>>>>>>I used a bucket size of 16 with about 100 particles.
>>
>>Like
>>
>>>>you
>>>>
>>>>
>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>mentioned,
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>>the algorithm must work fine independent of these
>>
>>parameters.
>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>>-Ali
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>Hi Ali,
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>Could you please report
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>1) How many points (measurement vectors) are you
>>>>>>>>>>>>>>currently feeding into the KdTreeGenerator ?
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>and
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>2) What value of "BucketSize" did you use ?
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>The problem reported in the bug
>>>>>>>>>>>>>>http://public.kitware.com/Bug/view.php?id=5082
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>Seems to be simply the result of a poor choice
>>>>>>>>>>>>>>on the value of the bucket size parameter.
>>>>>>>>>>>>>>For the test case reported in that bug, increasing
>>>>>>>>>>>>>>the value from 16 to 30 solves the problem.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>We are wondering if the problem that you are
>>>>>>>>>>>>>>experiencing is also the result of poor parameter
>>>>>>>>>>>>>>setting.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>Please let us know,
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>Thanks
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Luis
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>------------
>>>>>>>>>>>>>>Ali - wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>Hi,
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>A quick search in the mailing list shows that,
>>
>>during
>>
>>>>the
>>>>
>>>>
>>>>
>>>>>>past
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>half
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>>a decade, it has been reported many times that the kd-tree
>>>>>>>>>>>
>>>>>>>>>>
>>>>classes
>>>>
>>>>
>>>>
>>>>>>in
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>ITK
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>>are buggy. Writing some library based on ITK, it took me a
>>
>>few
>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>days to
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>find
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>>out that the bug in my library is actually introduced by
>>
>>the
>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>kd-tree
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>>implementation in ITK which FINDS THE WRONG NEAREST
>>
>>NEIGHBOUR.
>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>>>>I have no idea, against many warnings from the
>>
>>users,
>>
>>>>why
>>>>
>>>>
>>>>
>>>>>>the
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>bug
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>>has not been resolved yet. In the case it is difficult to
>>>>>>>>>>>
>>>>>>>>>>
>>>>address
>>>>
>>>>
>>>>
>>>>>>the
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>bug,
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>>one option is to wrap many other existing implementations,
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>personally
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>I
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>>switched to libkdtree++.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>_________________________________________________________________
>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>>>>>>>100's of prizes to be won at BigSnapSearch.com
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>http://www.bigsnapsearch.com
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>>>>_______________________________________________
>>>>>>>>>>>>>>>Insight-users mailing list
>>>>>>>>>>>>>>>Insight-users at itk.org
>>>>>>>>>>>>>>>http://www.itk.org/mailman/listinfo/insight-users
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>_________________________________________________________________
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>>>>>>>>100's of prizes to be won at BigSnapSearch.com
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>http://www.bigsnapsearch.com
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>_______________________________________________
>>>>>>>>>>>Insight-users mailing list
>>>>>>>>>>>Insight-users at itk.org
>>>>>>>>>>>http://www.itk.org/mailman/listinfo/insight-users
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>
>>>>>
>>>
>
More information about the Insight-users
mailing list