|
Notes |
|
|
(0011532)
|
|
Luis Ibanez
|
|
2008-04-24 13:30
|
|
|
|
|
(0011544)
|
|
Luis Ibanez
|
|
2008-04-24 22:02
|
|
Increasing the bucket size to 30 (from its current value of 16) solves the problem.
This doesn't seems to be a bug, but a misunderstanding on how the class should be used properly. |
|
|
|
(0011557)
|
|
Luis Ibanez
|
|
2008-04-25 19:46
|
|
Bucket size turned out not to be the reason for the failures.
This class (and the KdTreeGenerator) should work regardless of the bucket size value. |
|
|
|
(0011565)
|
|
Luis Ibanez
|
|
2008-04-28 08:15
|
|
|
|
|
(0011624)
|
|
Luis Ibanez
|
|
2008-04-30 15:52
|
|
From:
http://www.itk.org/pipermail/insight-users/2008-April/025641.html [^]
We believe that this bug 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 this bug report. |
|
|
|
(0011650)
|
|
Luis Ibanez
|
|
2008-05-01 14:36
|
|
|
The Dashboard is green today. |
|
KdTreeBug.zip (359,866) 1969-12-31 19:00