Skip to content

Fix KD Tree kNN Implementation#18061

Merged
alalek merged 2 commits intoopencv:3.4from
danielenricocahall:fix-kd-tree
Sep 4, 2020
Merged

Fix KD Tree kNN Implementation#18061
alalek merged 2 commits intoopencv:3.4from
danielenricocahall:fix-kd-tree

Conversation

@danielenricocahall
Copy link
Copy Markdown
Contributor

@danielenricocahall danielenricocahall commented Aug 9, 2020

Several issues about the implementation of the KDTree for kNN have been brought up over the years:

I believe this PR should address the issues described:

  • Add an additional clause in the median split algorithm to ensure no infinite loop in the case of identical values
  • Ensure the computations for the nearest neighbor are correctly returned
  • Enable original tests with some updates to reflect the implementation of the KD Tree
  • Add a new test based on issues to verify

Pull Request Readiness Checklist

See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request

  • I agree to contribute to the project under OpenCV (BSD) License.
  • To the best of my knowledge, the proposed patch is not based on a code under GPL or other license that is incompatible with OpenCV
  • The PR is proposed to proper branch
  • There is reference to original bug report and related work
  • There is accuracy test, performance test and test data in opencv_extra repository, if applicable
    Patch to opencv_extra has the same branch name.
  • The feature is well documented and sample code can be built with the project CMake

@danielenricocahall danielenricocahall force-pushed the fix-kd-tree branch 5 times, most recently from 31a6514 to fe843a3 Compare August 9, 2020 22:00
@asmorkalov asmorkalov requested a review from vpisarev August 10, 2020 08:29
@asmorkalov
Copy link
Copy Markdown
Contributor

@vpisarev please take a look on the patch.


TEST(ML_KNearest, bug_11877) {
Mat trainData = (Mat_<float>(5,2) << 3, 3, 3, 3, 4, 4, 4, 4, 4, 4);
Mat trainLabels = (Mat_<float>(5,1) << 0, 0, 1, 1, 1);
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please remove tabs. Use 4 spaces for indentation

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

fixed!

if( _results.needed() )
{
_results.create(testcount, 1, CV_32F);
res = _results.getMat();
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This doesn't look valid.

OpenCV API can reuse output buffers (if they are not zero). However it is not tested widely.

res.push_back(_res.t());

will keep garbage in the beginning from the passed buffer for output.

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I believe I saw some similar behavior with what you're describing when I left these lines in here - in the example of the test case with two samples, res would contain four values - the first two of which were garbage, and the latter two contained valid/reasonable values.

Copy link
Copy Markdown
Member

@alalek alalek left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good to me! Thank you 👍


EXPECT_EQ(int(result.at<int>(0, 0)), 1);
EXPECT_EQ(int(result.at<int>(1, 0)), 2);
EXPECT_EQ(trainLabels.at<int>(result.at<int>(0, 0), 0), 0);
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please swap arguments for EXPECT_EQ() macro:

  • EXPECT_EQ(expected, actual)

danielenricocahall and others added 2 commits September 4, 2020 14:30
remove docs and revert change

Make KDTree mode in kNN functional

spacing

Make KDTree mode in kNN functional

fix window compilations warnings

Make KDTree mode in kNN functional

fix window compilations warnings

Make KDTree mode in kNN functional

casting

Make KDTree mode in kNN functional

formatting

Make KDTree mode in kNN functional
@alalek alalek merged commit 20b23da into opencv:3.4 Sep 4, 2020
@alalek alalek mentioned this pull request Sep 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants