[Insight-users] Kd-tree implementation in ITK is buggy and unreliable
Luis Ibanez
luis.ibanez at kitware.com
Wed Apr 30 15:48:21 EDT 2008
Hi Ali,
It seems that the behavior of the following classes:
* KdTree
* KdTreeGenerator
* WeightedCentroidKdTreeGenerator
has now been fixed.
The sources of the problem were spread in four
different locations:
1) KdTree was lacking to store the medial
point on each one of the non-terminal nodes
2) The Search method in the KdTree was therefore
not taking the separation (medial) point into
account properly when searching for the closest
point.
3) The implementation of the QuickSelect algorithm
in StatisticsAlgorithm was not functional for all
cases
4) The implementation of the Partition algorithm
in StatisticsAlgorithm was not functional for all
cases
The following changes were made in order to fix the
behavior:
1) The QuickSelect and Partition algorithms were
rewritten, based on the descriptions of these
algorithms found in the Wikipedia.
2) The creation of non-terminal nodes in the
KdTree generator(s) now stores the medial point
coordinates in the non-terminal node
3) The Search method now includes the medial point
in the list of closest point candidates.
The following features were added as a side effect:
4) The KdTree can now export its tree structure
to a text file in Graphviz-Dot format. With
this file you can generate diagrams of the
resulting KdTree.
5) A NthElement algorithm was added to the set
of algorithms in the StatisticsAlgoritms.txx
file. This algorithm was intended to provide
an alternative implementation to QuickSelect.
In order to put the code under control, a group of 25
test were added to the Nightly test suite.
http://www.itk.org/cgi-bin/viewcvs.cgi/Testing/Code/Numerics/Statistics/CMakeLists.txt?root=Insight&r1=1.44&r2=1.62
These new tests exercise the QuickSelect, Partition and
NthElement algoritms, as well as various scenarios of the
KdTree, and its generators.
The KdTree testing now includes the verification that
when searching for a closest point to a point P that
is already in the KdTree, the Search method return the
point P itself. An exahustive verification of closest
point correctness is also done with a second random
collection of points. These last tests are based on the
test contributed by Kevin Hobbs. Tests were also added
based on the search from an input file, contributed by
Tobias Heimann in his bug report
http://public.kitware.com/Bug/view.php?id=5082
If you have a chance, please update your CVS checkout
of ITK, and give it a try to the KdTree. We expect it
to behave properly at this point.
Please let us know if you find any problems.
Thanks
Luis
-------------------
Luis Ibanez wrote:
>
>
> Hi Bill,
>
> I just committed your fix to the QuickSelect main loop.
>
>
> Also restored the use of QuickSelect inside the KdTreeGenerators.
> (I had replaced its use with the NthElement algorithm this morning)
>
>
> Thanks a lot for fixing it.
> It was driving me crazy... :-/
>
>
>
> Luis
>
>
> ---------------------
> Bill Lorensen wrote:
>
>> I just submitted an experimental mingw with my changes. All tests pass.
>>
>> Bill
>>
>> On Tue, Apr 29, 2008 at 6:32 PM, Luis Ibanez <luis.ibanez at kitware.com>
>> wrote:
>>
>>> Hi Bill,
>>>
>>> I replaced the QuickSelect in StatisticsAlgorithms with
>>>
>>> the implementation of NthElement from STL.
>>>
>>> It does the trick as well.
>>>
>>> I'll incorporate your changes to have a working QuickSelect.
>>>
>>>
>>>
>>>
>>> Luis
>>>
>>>
>>> -------------------------
>>> Bill Lorensen wrote:
>>>
>>>> Luis,
>>>>
>>>> I think the current QuickSelect is not correct. I recoded it to match
>>>> the wikipedia article. All Statistics tests pass with these changes.
>>>> And NeuralNet tests. As I mentioned I don't have cvs access today.
>>>> here is the code for the while loop:
>>>>
>>>> while( true )
>>>> {
>>>> // Partition expects the end argument to be one past-the-end of the
>>>
>>>
>>> array.
>>>
>>>> // The index pivotNewIndex returned by Partition is in the range
>>>> [begin,end].
>>>> int pivotNewIndex =
>>>> Partition< TSubsample >(sample, activeDimension, begin, end+1,
>>>> tempMedian) ;
>>>> if( kthIndex == pivotNewIndex )
>>>> {
>>>> break;
>>>> }
>>>>
>>>> if( kthIndex < pivotNewIndex )
>>>> {
>>>> end = pivotNewIndex - 1;
>>>> }
>>>> else
>>>> {
>>>> begin = pivotNewIndex + 1;
>>>> }
>>>>
>>>> if( begin > end )
>>>> {
>>>> break;
>>>> }
>>>>
>>>>
>>>>
>>>>
>>>> On Tue, Apr 29, 2008 at 1:59 PM, Bill Lorensen
>>>> <bill.lorensen at gmail.com>
>>>
>>>
>>> wrote:
>>>
>>>>
>>>>> That looks good.
>>>>>
>>>>>
>>>>> On Tue, Apr 29, 2008 at 1:39 PM, Luis Ibanez <luis.ibanez at kitware.com>
>>>
>>>
>>> wrote:
>>>
>>>>>
>>>>>> 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,
>>>>>>
>>>>>>
>>>>>>
>>> ...
>>>
>>> [Message clipped]
>>
>>
>>
>
More information about the Insight-users
mailing list