Code covered by the BSD License  

Highlights from
KD Tree Nearest Neighbor and Range Search

4.10526

4.1 | 19 ratings Rate this file 61 Downloads (last 30 days) File Size: 212 KB File ID: #7030

KD Tree Nearest Neighbor and Range Search

by

 

01 Mar 2005 (Updated )

KD Tree range and nearest neighbor search.

| Watch this File

File Information
Description

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).

Acknowledgements

This file inspired Efficient Kernel Smoothing Regression Using Kd Tree, Kdtree Implementation In Matlab, and Efficient K Nearest Neighbor Search Using Jit.

MATLAB release MATLAB 7.6 (R2008a)
Other requirements Source included; binaries for Linux (i386,x86_64) & Windows (i386) are included
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (28)
18 Aug 2014 Jon

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

20 Mar 2014 Francesco

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

06 Aug 2013 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

11 Jul 2012 Amir

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

27 Mar 2012 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.

23 Feb 2012 Amir

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...

23 May 2011 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 )

03 Nov 2010 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.

24 May 2010 Erez

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"

08 Apr 2010 aarif  
09 Sep 2009 sun jin

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

14 Jul 2009 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

12 Sep 2008 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

21 Aug 2008 Paul Le

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

01 Aug 2008 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?

23 Jul 2008 Nils **********  
10 Jul 2008 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!

06 Jul 2008 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!

25 Mar 2008 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?

04 Nov 2007 saurabh agrawal

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

12 Aug 2007 Sam Dambreville

Stellar(as usual)

Thanks+++++++++

08 Jul 2006 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.

31 Jan 2006 J. Knight

Good, but supporting doubles would make it even better.

11 Nov 2005 Zach Buckner

Absolutely perfect. Very well designed and packaged.

30 Aug 2005 hu wenchao

could you give your algorithms and time complexity analysis

08 Jun 2005 T M

Very good. Speeds up my program a lot

21 Apr 2005 João Ferreira

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

20 Apr 2005 Alaa Halawani

Great and fast

Updates
07 Apr 2005

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.

20 Apr 2005

Fix memory leak in kdtree creation

29 Jun 2005

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.

11 Nov 2005

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.

09 May 2006

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.

11 May 2006

Fix an error that allocates too much memory when creating tree

06 Jun 2006

Fix a memory error that sometimes causes incorrect results.

Contact us