KD Tree Nearest Neighbor and Range Search

KD Tree range and nearest neighbor search.

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 submission has inspired the following:; Efficient Kernel Smoothing Regression using KD-Tree, Kdtree implementation in matlab , 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

[Alaa Halawani]

Great and fast

[João Ferreira]

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

[T M]

Very good. Speeds up my program a lot

[hu wenchao]

could you give your algorithms and time complexity analysis

[Zach Buckner]

Absolutely perfect. Very well designed and packaged.

[J. Knight]

Good, but supporting doubles would make it even better.

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

[Sam Dambreville]

Stellar(as usual)

Thanks+++++++++

[saurabh agrawal]

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

[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?

[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!

[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!

[Nils **********]

 

[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?

[Paul Le]

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

[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

[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

[sun jin]

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

[aarif]

 

[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"

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

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