| View Issue Details [ Jump to Notes ] | [ Print ] | ||||||||
| ID | Project | Category | View Status | Date Submitted | Last Update | ||||
| 0005082 | ITK | public | 2007-05-23 13:21 | 2008-05-01 14:36 | |||||
| Reporter | Tobias Heimann | ||||||||
| Assigned To | Luis Ibanez | ||||||||
| Priority | high | Severity | major | Reproducibility | always | ||||
| Status | closed | Resolution | fixed | ||||||
| Platform | OS | OS Version | |||||||
| Product Version | |||||||||
| Target Version | Fixed in Version | ||||||||
| Summary | 0005082: KdTree::Search does not return the true nearest neighbor | ||||||||
| Description | When searching the 1 nearest neighbor of an element that is included in the tree (i.e. should return a distance of zero), the search sometimes misses this element and returns another one with a distance > 0. Reproducible on Windows XP with MSVC 7.1, other platforms are not tested (but probably show the same behaviour). An example program with data that reproduces the bug is attached. | ||||||||
| Tags | No tags attached. | ||||||||
| Resolution Date | |||||||||
| Sprint | |||||||||
| Sprint Status | |||||||||
| Attached Files |  KdTreeBug.zip [^] (359,866 bytes) 1969-12-31 19:00 | ||||||||
| Relationships | |
| Relationships |
| Notes | |
|
(0011532) Luis Ibanez (manager) 2008-04-24 13:30 |
This example (illustrating the bug) has been added to the test suite: http://public.kitware.com/pipermail/insight-users/2008-April/025567.html [^] |
|
(0011544) Luis Ibanez (manager) 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 (manager) 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 (manager) 2008-04-28 08:15 |
Bugs 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 There are still side effects in the following (now failing) tests * BayesianClassifierInitializeTest * itkSampleMeanSjhiftClusteringFilterTest * RBFTest1 * ScalarImageKmeansClassifierTest They are currently timingout, (probably due to infinite-loops) we are now tracking those issues... |
|
(0011624) Luis Ibanez (manager) 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 (manager) 2008-05-01 14:36 |
The Dashboard is green today. |
| Notes |
| Issue History | |||
| Date Modified | Username | Field | Change |
| 2008-04-24 13:08 | Luis Ibanez | Assigned To | user677 => Luis Ibanez |
| 2008-04-24 13:30 | Luis Ibanez | Note Added: 0011532 | |
| 2008-04-24 22:02 | Luis Ibanez | Note Added: 0011544 | |
| 2008-04-25 19:46 | Luis Ibanez | Note Added: 0011557 | |
| 2008-04-28 08:15 | Luis Ibanez | Note Added: 0011565 | |
| 2008-04-30 15:52 | Luis Ibanez | Note Added: 0011624 | |
| 2008-05-01 14:36 | Luis Ibanez | Status | assigned => closed |
| 2008-05-01 14:36 | Luis Ibanez | Note Added: 0011650 | |
| 2008-05-01 14:36 | Luis Ibanez | Resolution | open => fixed |
| Issue History |
| Copyright © 2000 - 2018 MantisBT Team |