[Insight-users] Kd-tree implementation in ITK is buggy and unreliable
Bill Lorensen
bill.lorensen at gmail.com
Tue Apr 29 13:13:01 EDT 2008
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