[Insight-users] Kd-tree implementation in ITK is buggy and unreliable
Ali -
saveez at hotmail.com
Wed Apr 30 18:43:09 EDT 2008
Hi Luis,
Many thanks for the prompt fix, now other ITK classes using kd-tree search should work more accurately as well as my code.
-Ali
>
>
> 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
>>> 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
>>>>>
>>>>
>>>>
>>>> wrote:
>>>>
>>>>>
>>>>>> That looks good.
>>>>>>
>>>>>>
>>>>>> On Tue, Apr 29, 2008 at 1:39 PM, Luis Ibanez
>>>>
>>>>
>>>> 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
>>>>
>>>>
>>>>
>>>>
>>>>>>> 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
>>>>>>>>>>
>>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>>> 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
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>> 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
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>> 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(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
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>> 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]
>>>
>>>
>>>
>>
_________________________________________________________________
Play the Andrex Hello Softie Game & win great prizes
http://www.thehellosoftiegame.co.uk
More information about the Insight-users
mailing list