File Exchange

image thumbnail

KD Tree Nearest Neighbor and Range Search

version 1.0 (212 KB) by

KD Tree range and nearest neighbor search.

4.10526
19 Ratings

15 Downloads

Updated

View License

This implements a KDTree for nearest neighbor and range searching.The KDTree stores a N-dimensional set of points. The tree can be queried for all points within a Euclidian range in order O(sqrt(p)+k) time, where p is the number of points and k is the number of reported points. A nearest neighbor search can be done in order O(log(p) time. The m-files are binary MATLAB functions written in C++. Source code is included as well as binaries for Linux on i386 and x86_64 systems and Windows (i386).

Comments and Ratings (28)

Jon

Jon (view profile)

Supplied mex files don't work and source code doesn't compile. I think it's missing the "void mexfunction" lines.

Francesco

I tried to run this work on Windows64 with MatlabR2012a, 64bit version without success. Is there anyone who can help me?

Maja Bitenc

Dear all,

First thanks to the Author for a nice submition I am using often to work with lidar point clouds.
But now I wish to use kdtree_range with multiple boxes & single call (making a loop takes for ages!). This is, I define the "range" as 3D array. An example what I did:

>> r = rand(5,2);
>> tree = kdtree(r);
>> boxm

boxm(:,:,1) =

         0 0
    0.5000 0.5000
    1.0000 1.0000

boxm(:,:,2) =

    0.5000 0.5000
    1.0000 1.0000
    1.5000 1.5000

>> kdtree_range(tree,boxm)
Multple range input must have size (N,ndim,2)

But the boxm HAS the size (N - number of boxes, ndim - which is two, 2)!?!
Any suggestios how to make it work?

Many thanks in advance!
Maja

Amir

Amir (view profile)

For one dimensional data I am searching, the range search gives some results which are outside the specified range by a tiny bit. e.g. 4-5 orders of magnitude relative to the search window size.

example for reproducing this : (takes a few minutes to complete run)

rng('default')
for i=1:1000
    x=rand(100000,1);
    tree=kdtree(x);
    r=[0.3331 1/3];
    idx=kdtree_range(tree,r);
    found=x(idx);
    if any(found<r(1))
        disp(i)
        disp(found(found<r(1))-r(1))
    end
    if any(found>r(2))
        disp(i)
        disp(found(found>r(2))-r(2))
    end
end

Rida Sadek

I had some troubles compiling this on MacOSX Snow Leopard.
In order to compile correctly this package I just added the following line to the CXXFLAGS
" -undefined dynamic_lookup -bundle "
and also removed the other options specifically:
" -mtune=pentium4 -msse -msse2 -fPIC"
However, I doubt that keeping them would harm the compilation.

It is a very nice and well implemented package.
Many thanks for sharing it.

Amir

Amir (view profile)

I just managed to compile mex files for this submission on windows 64.
It wasn't that easy, and I wasted a few good hours on that, but it works now.
I also admit I know almost nothing about compiling and so forth so there might be better ways to do it, but anyway these were my steps:

1. Installed MS Visual Studio 2010 (warning: it's not free, but luckily my helpdesk had a licensed copy)

2. Opened Matlab, typed
       >> mex -setup
and went through the setup process.

3. opened the options file:
    C:\Users\apaster\AppData\Roaming\MathWorks\MATLAB\R2011b\mexopts.bat
(find the right location by typing

and added the folder P:\Documents\MATLAB\kdtree\src that contained the source files of kdtree to the options file (lines 25-26):

set PATH=P:\Documents\MATLAB\kdtree\src;%VCINSTALLDIR%\bin\amd64;%VCINSTALLDIR%\bin;%VCINSTALLDIR%\VCPackages;%VSINSTALLDIR%\Common7\IDE;%VSINSTALLDIR%\Common7\Tools;%LINKERDIR%\bin\x64;%LINKERDIR%\bin;%MATLAB_BIN%;%PATH%
    
set INCLUDE=P:\Documents\MATLAB\kdtree\src;%VCINSTALLDIR%\INCLUDE;%VCINSTALLDIR%\ATLMFC\INCLUDE;%LINKERDIR%\include;%INCLUDE%
    
seems like if we don't do that, the compiler won't be able to find the kdtree.h file
    
4. from Matlab, typed:
     >> cd 'P:\Documents\MATLAB\kdtree\src'
     >> mex kdtree.cpp kdtree_create.cpp
     >> mex kdtree_range.cpp kdtree.cpp
     >> mex kdtree_closestpoint.cpp kdtree.cpp

5. That's it ! Now just copied the .mexw64 files to \kdtree\@kdtree folder.

Hope this works for you...

kennyou

@sun jin:
copy the directory @kdtree to current working directory, then the examples in README.txt can be performed

@all:
in matlab 2010b, KDTreeSearcher class work fine for me. here is a simple example:

>> X = rand( 10, 2 ) ; % 10 center vectors
>> tree = kdtreesearcher( X )
>> T = rand( 3, 2 ) ; % 3 test vectors
>> [ k, d ] = knnsearch( tree, T , 'k', 1 )

Srikrishna

The code is very well written. But the description is misleading. It says that "The tree can be queried for all points within a Euclidian range". But actually the range we specify is rectangular range in each dimensions.

Erez

Erez (view profile)

This is a windows 64 bit make file, which seemed to work for me:

#######################################################################
# Makefile for MatlabCPP
#
#######################################################################

# MATLAB directory -- this may need to change depending on where you have MATLAB installed
MATDIR = C:\\Program Files\\MATLAB\\R2010a

INCDIR = /I "." /I "../../src" -I "$(MATDIR)/extern/include" -I"../Libs/"
CPP = cl
CPPFLAGS = /c /Zp8 /GR /W3 /EHs /D_CRT_SECURE_NO_DEPRECATE /D_SCL_SECURE_NO_DEPRECATE \
/D_SECURE_SCL=0 /DMATLAB_MEX_FILE /nologo /DWIN64
#CPPFLAGS = /c /Zp8 /MD /GR /W3 /EHs /D_CRT_SECURE_NO_DEPRECATE /D_SCL_SECURE_NO_DEPRECATE \#
# #/D_SECURE_SCL=0 /DMATLAB_MEX_FILE /nologo /D "CPP_ACCEPT_EXPORTS" /D_USERDLL /D_WINDLL \
# /DUNICODE /D_UNICODE /DWIN32
LINK = link
LINKFLAGS = /dll /export:mexFunction /MAP /MACHINE:X64 \
/LIBPATH:"$(MATDIR)\extern\lib\win64\microsoft" \
/LIBPATH:"../Libs/$(OUTDIR)" \
libmex.lib libmx.lib libmat.lib

INSTDIR = ./../../@kdtree/
# DEBUGBUILD = 1

!IF DEFINED(DEBUGBUILD)
OUTDIR = Debug/
CPPFLAGS = $(CPPFLAGS) /Fo"$(OUTDIR)" /DDEBUG
LINKFLAGS = $(LINKFLAGS) /INCREMENTAL /DEBUG

!ELSE
OUTDIR = Release/
CPPFLAGS = $(CPPFLAGS) /O2 /Oy- /Fo"$(OUTDIR)" /DNDEBUG
!ENDIF

.SILENT :

# Rules for making the targets
TARGETS = $(OUTDIR)kdtree.mexw64 \
$(OUTDIR)kdtree_closestpoint.mexw64 \
$(OUTDIR)kdtree_range.mexw64

all: $(TARGETS)
@copy $(OUTDIR:/=\)*.mexw64 $(INSTDIR:/=\)
@echo Files Built Successfully

clean:
@echo Cleaning output filder
@del $(OUTDIR:/=\)*.mexw64
@del $(OUTDIR:/=\)*.lib
@del $(OUTDIR:/=\)*.exp
@del $(OUTDIR:/=\)*.obj
@del $(OUTDIR:/=\)*.manifest
@del $(OUTDIR:/=\)*.map
@del $(INSTDIR:/=\)*.mexw64

rebuild: clean all

.SUFFIXES : mexw64
.SILENT :

# The below two lines don't seem to work -- I'll do it manually
#{$(OUTDIR)}.mexw64{$(OUTDIR)}.obj:
# $(LINK) $(OUTDIR)$< $(LINKFLAGS) /OUT:$(OUTDIR)$<.mexw32

{./../../src/}.c{$(OUTDIR)}.obj:
    $(CPP) $(CPPFLAGS) $(INCDIR) $<

{./../../src/}.cpp{$(OUTDIR)}.obj:
    $(CPP) $(CPPFLAGS) $(INCDIR) $<

$(OUTDIR)kdtree.mexw64 : $(OUTDIR)kdtree.obj $(OUTDIR)kdtree_create.obj
$(LINK) $(OUTDIR)kdtree.obj $(OUTDIR)kdtree_create.obj \
$(LINKFLAGS) /PDB:"$(OUTDIR)kdtree.pdb" \
/OUT:"$(OUTDIR)kdtree.mexw64"

$(OUTDIR)kdtree_closestpoint.mexw64 : $(OUTDIR)kdtree.obj $(OUTDIR)kdtree_closestpoint.obj
$(LINK) $(OUTDIR)kdtree.obj $(OUTDIR)kdtree_closestpoint.obj \
$(LINKFLAGS) /PDB:"$(OUTDIR)kdtree_closestpoint.pdb" \
/OUT:"$(OUTDIR)kdtree_closestpoint.mexw64"

$(OUTDIR)kdtree_range.mexw64 : $(OUTDIR)kdtree.obj $(OUTDIR)kdtree_range.obj
$(LINK) $(OUTDIR)kdtree.obj $(OUTDIR)kdtree_range.obj \
$(LINKFLAGS) /PDB:"$(OUTDIR)kdtree_range.pdb" \
/OUT:"$(OUTDIR)kdtree_range.mexw64"

aarif

aarif (view profile)

sun jin

??? Error using ==> class
The CLASS function must be called from a class constructor.

xin chen

Hello, I am trying to do this:
>> r = rand(10,3);
>> tree = kdtree(r);

There is error
??? Error using ==> kdtree
Must have at least two input arrays.

How can I solve this?

Thank you

Andrea Tagliasacchi

I have been trying to use this utilities for OSX under Matlab2008a.

In the Makefile I changed the compiler to standard g++ (g++4.3.1):
CXX = g++
Also I had to remove some of the CXX options to compile successfully:
-mtune=pentium4 -msse -msse2 -fPIC

The make clean didn't remove the symbolic link so an error would be generated if you tried to recompile the source.

Also I had to change several inclusion directives to comply with the standard in almost all the *.cpp files:

#include <mex.h> ==> #include "mex.h"
#include <kdtree.h> ==> #include "kdtree.h"

With these changes I tried to compile under linux, which with these changes was finally successfully. However, when I try to run the script provided as an example in README.txt I get the following:

>> r = rand(1000,3);
>> tree = kdtree(r)
??? Attempt to execute SCRIPT kdtree.kdtree as a function:
/cs/grad1/ata2/temp/kdtree 3/@kdtree/kdtree.m

I also tried to compile under OSX and i686-apple-darwin9-g++-4.0.1 and I get the following:

>> !make
g++ -Wall -O3 -fomit-frame-pointer -Isrc -I/Applications/matlab/extern/include -c src/kdtree_create.cpp -o kdtree_create.o
g++ -Wall -O3 -fomit-frame-pointer -Isrc -I/Applications/matlab/extern/include -c src/kdtree.cpp -o kdtree.o
ln -s @kdtree kdtree
g++ -Wall -O3 -fomit-frame-pointer -shared kdtree_create.o kdtree.o -o kdtree/kdtree.mexglx
Undefined symbols:
  "_mxGetM", referenced from:
      _mexFunction in kdtree_create.o
.....(many more of similar errors)

I finally give up using this utility...
At least it should have worked in Linux properly

Paul Le

please Post it a gain! The zip file does not contain enough files as described.
Thanks,
Paul

Kim A

I think because I am using older Matlab version, 2006a, I cant run the program. I tried to use mex .cpp but still not successful. Anyone can help me for this?

Nils **********

David Doria

Would it be possible to include a "NearestNeighborExceptThisPoint" function? For example, I need to find the nearest neighbor to each point in a set. So I build the kdtree, then the "nearest neighbor" to each point is itself!

David Doria

I see some odd behavior when my data set has NaN members - it returns some random point as the best match rather than complaining. Other than that, this code was very helpful!

Yi Cao

Excellent work. Very efficient. Better than the kdtree provided in MATLAB Image Processing Toolbox. Would you like to upgrade the single nearest point search to a k-NN search?

saurabh agrawal

>> r = rand(1000,3);
>> tree = kdtree(r)
??? Error using ==> class
Class kdtree is not a valid class name.

Sam Dambreville

Stellar(as usual)

Thanks+++++++++

Liu Shuyong

It is a very good performance. But if I want to display the tree,how can I modify the programme. and if I want to count the searching times of this algorithm, how can I do.thank you.

J. Knight

Good, but supporting doubles would make it even better.

Zach Buckner

Absolutely perfect. Very well designed and packaged.

hu wenchao

could you give your algorithms and time complexity analysis

T M

Very good. Speeds up my program a lot

João Ferreira

As Alaa said, great AND fast. Thank you, Steven!

Alaa Halawani

Great and fast

Updates

Fix a memory error that sometimes causes incorrect results.

Fix an error that allocates too much memory when creating tree

1. Significantly speed up tree creation
2. Lower latency (removed tree "unserialization" for each function call)
3. fixed kdtree_closestpoint bug that returned incorrect points (but not indices) when querying closest point.

Update so that kdtree_range searches can be done on multiple volumes with a single call. Also, the tree creation switches from using a quicksort to a heapsort -- seems to be a little faster.

Update such that the tree is serialized instead of stored in an abstract pointer. This means that the tree can be saved in a MATLAB file (or to disk) and loaded again quickly. Also, the implementation is now done using MATLAB classes.

Fix memory leak in kdtree creation

A small but important change -- the border searching for the closest point function now compares |r|^2 instead of |r|. Removing the square root function siginificanly speeds up the closest point algorithm.

MATLAB Release
MATLAB 7.6 (R2008a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

kdtree/@kdtree/