robwhess/opensift

Open-Source SIFT Library

Update: This project is essentially unmaintained at this point, since I don't have time to work on it, and my focus has moved on to other things. Note that this very code was long ago incorporated directly into OpenCV and, as far as I know, still serves as the basis of OpenCV's SIFT implementation. Thus, if you have any issues with this project, I encourage you to use OpenCV's SIFT implementation directly.

Intro

This is a collection of code I've put together to detect SIFT features in images and to use SIFT (or other) features to compute image transforms with RANSAC. It includes a SIFT function library as well as some executables to detect, match, and display keypoints. For more information on SIFT, refer to the paper by Lowe:

Lowe, D. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60, 2 (2004), pp.91--110.

Or see Lowe's website: http://www.cs.ubc.ca/~lowe/keypoints/

Some of the code also works with affine-invariant features from the code by the VGG at oxford: http://www.robots.ox.ac.uk:5000/~vgg/research/affine/index.html

Check out match.c for an example of how to use the RANSAC function. Try match beaver.png beaver_xform.png to see it work.

Documentation is included in the docs/ directory. If it is not there, use make docs to build it (you need Doxygen).

Help is available for executables using the '-h' command line option.

Requirements

All code in this package requires the OpenCV library (known working version is 2.3): http://sourceforge.net/projects/opencvlibrary/

Some functions require GDK/GTK+2 (known working version is 2.18.4): http://www.gtk.org/

Building

To build everything, use make:

make

This should produce a few executables in bin/, a static library lib/libopensift.a, and some HTML documentation in docs/. You can use the -h argument to get help with any of the executables. libopensift.a can be compiled into your own code using the standard method:

gcc -I/path/to/opensift/include/ -L/path/to/opensift/lib/ yourcode.c -o yourexecutable -lopensift

The documentation in docs/ describes all of the functions available in libopensift.a as well as #defines, etc. Use the documentation to determine what header files from include/ to include in your code.

You can also individually build any of the executables or libopensift.a, e.g.

make libopensift.a

License

See the file LICENSE for more information on the legal terms of the use of this package.

opensift's Issues

License

Is this patent licensed or free ?

Missing link to libm

Linking in Ubuntu 13.10, gcc version 4.8.1:

gcc -I../include pkg-config --cflags opencv gtk+-2.0 siftfeat.c -o ../bin/siftfeat -L../lib -lopensift pkg-config --libs opencv gtk+-2.0
/usr/bin/ld: ../lib/libopensift.a(imgfeatures.o): undefined reference to symbol 'atan2@@GLIBC_2.0'
/lib/i386-linux-gnu/libm.so.6: error adding symbols: DSO missing from command line
collect2: error: ld returned 1 exit status

Adding -lm to the Makefile can fix the problem.

use cmake manage source and build

Should it be consistent when calculating dx and dy in the function static int calc_grad_ori ?

Hi! I am reading your code. In the file sift.c, in function static int calc_grad_mag_ori( IplImage* img, int r, int c, double* mag,double* ori ):
when calculating dx, dx = pixval32f( img, r, c+1 ) - pixval32f( img, r, c-1 );
when calculating dy, dy = pixval32f( img, r-1, c ) - pixval32f( img, r+1, c );
I am wondering why not dy=pixval32f( img, r+1, c ) - pixval32f( img, r-1, c )?
In the column direction, bigger index minus smaller index;
however, in the row direction, smaller index minus bigger index.
Is the calculating of dx and dy consistent?

I have one question about the code

static IplImage*** build_gauss_pyr( IplImage* base, int octvs,
int intvls, double sigma )
{
IplImage*** gauss_pyr;
const int _intvls = intvls;
double sig[_intvls+3], sig_total, sig_prev, k;
int i, o;

gauss_pyr = calloc( octvs, sizeof( IplImage** ) );
for( i = 0; i < octvs; i++ )
gauss_pyr[i] = calloc( intvls + 3, sizeof( IplImage *) );

/*
precompute Gaussian sigmas using the following formula:
\sigma_{total}^2 = \sigma_{i}^2 + \sigma_{i-1}^2
sig[i] is the incremental sigma value needed to compute
the actual sigma of level i. Keeping track of incremental
sigmas vs. total sigmas keeps the gaussian kernel small.
/
k = pow( 2.0, 1.0 / intvls );
sig[0] = sigma;
sig[1] = sigma * sqrt( kk- 1 );
for (i = 2; i < intvls + 3; i++)
sig[i] = sig[i-1] * k;

for( o = 0; o < octvs; o++ )
for( i = 0; i < intvls + 3; i++ )
{
if( o == 0 && i == 0 )
gauss_pyr[o][i] = cvCloneImage(base);

/* base of new octvave is halved image from end of previous octave */
else if( i == 0 )
  gauss_pyr[o][i] = downsample( gauss_pyr[o-1][intvls] );
  
/* blur the current octave's last image to create the next one */
else
  {
    gauss_pyr[o][i] = cvCreateImage( cvGetSize(gauss_pyr[o][i-1]),
				     IPL_DEPTH_32F, 1 );
    cvSmooth( gauss_pyr[o][i-1], gauss_pyr[o][i],
	      CV_GAUSSIAN, 0, 0, sig[i], sig[i] );
  }
  }

return gauss_pyr;
}

Question about the code

Hello, your code is very elegant and I am now studying it.
I have one question:

	unsigned long* feature_mat;

	features = cvCreateSeq( 0, sizeof(CvSeq), sizeof(struct feature), storage );
	for( o = 0; o < octvs; o++ )
	{
		feature_mat = calloc( dog_pyr[o][0]->height * dog_pyr[o][0]->width, sizeof(unsigned long) );
		for( i = 1; i <= intvls; i++ )
			for(r = SIFT_IMG_BORDER; r < dog_pyr[o][0]->height-SIFT_IMG_BORDER; r++)
				for(c = SIFT_IMG_BORDER; c < dog_pyr[o][0]->width-SIFT_IMG_BORDER; c++)
					/* perform preliminary check on contrast */
					if( ABS( pixval32f( dog_pyr[o][i], r, c ) ) > prelim_contr_thr )
						if( is_extremum( dog_pyr, o, i, r, c ) ) 
							//is_extremum: Determines whether a pixel is a scale-space extremum by comparing it to it's
							//3x3x3 pixel neighborhood
						{
							feat = interp_extremum(dog_pyr, o, i, r, c, intvls, contr_thr);
							if( feat )
							{
								ddata = feat_detection_data( feat );
								// is_too_edge_like: is_too_edge_like: use the trace and det to determine
								if( ! is_too_edge_like( dog_pyr[ddata->octv][ddata->intvl],
														ddata->r, ddata->c, curv_thr ) )
								{
									if( ddata->intvl > sizeof(unsigned long) )
										cvSeqPush( features, feat );
									else if( (feature_mat[dog_pyr[o][0]->width * ddata->r + ddata->c] & (1 << ddata->intvl-1)) == 0 )
									{
										cvSeqPush( features, feat );
										feature_mat[dog_pyr[o][0]->width * ddata->r + ddata->c] += 1 << ddata->intvl-1;
									}
								}
								else
									free( ddata );
								free( feat );
							}
						}
		free( feature_mat );
	}

What's the purpose of feature_mat here?

Please document whether this is compatible with Lowe's sift tool

Hi!
The bundler program includes a shell script to invoke Lowe's sift tool in order to extract features from .pgm images. The original tool has some limitations (it's especially limited on the image size, so it won't work on larger images) and it would be interesting to know if the siftfeat program included in this project is compatible with it -- that is, whether it accepts the same input and delivers the output in the same format.
If it's not compatible, but you are able to document what the difference are, I could contribute a small shell script that wraps siftfeat in a way that makes it compatible with the original sift.

Create a seperate _sift_detect() function

Right now the only way to detect a SIFT feature is to also compute the descriptor. It would be helpful when comparing the your SIFT detector against others, if you could just call the detector without wasting CPU time computing descriptor also. This functionality is easily added. I would submit a patch, but it would probably take longer for you to inspect the code than to do it yourself.

What is the purpose of feature_mat?

Hello, I am now reading the code. It's so elegant. And I have one question,

`
unsigned long* feature_mat;

features = cvCreateSeq( 0, sizeof(CvSeq), sizeof(struct feature), storage );
for( o = 0; o < octvs; o++ )
{
feature_mat = calloc( dog_pyr[o][0]->height * dog_pyr[o][0]->width, sizeof(unsigned long) );
for( i = 1; i <= intvls; i++ )
for(r = SIFT_IMG_BORDER; r < dog_pyr[o][0]->height-SIFT_IMG_BORDER; r++)
for(c = SIFT_IMG_BORDER; c < dog_pyr[o][0]->width-SIFT_IMG_BORDER; c++)
/* perform preliminary check on contrast */
if( ABS( pixval32f( dog_pyr[o][i], r, c ) ) > prelim_contr_thr )
if( is_extremum( dog_pyr, o, i, r, c ) )
{
feat = interp_extremum(dog_pyr, o, i, r, c, intvls, contr_thr);
if( feat )
{
ddata = feat_detection_data( feat );
if( ! is_too_edge_like( dog_pyr[ddata->octv][ddata->intvl],
ddata->r, ddata->c, curv_thr ) )
{
if( ddata->intvl > sizeof(unsigned long) )
cvSeqPush( features, feat );
else if( (feature_mat[dog_pyr[o][0]->width * ddata->r + ddata->c] & (1 << ddata->intvl-1)) == 0 )
{
cvSeqPush( features, feat );
feature_mat[dog_pyr[o][0]->width * ddata->r + ddata->c] += 1 << ddata->intvl-1;
}
}
else
free( ddata );
free( feat );
}
}
free( feature_mat );
}
`

What's feature_mat used for?
Thank you so much.

linking to libopensift from C++

Hello,
I'm attempting to call libopensift from C++ and running into linker
errors:

clang++ -g -I/opt/OpenSIFT/include -I/usr/local/include/opencv
-I/usr/local/include -I/usr/local/include -I/usr/local/include/glib-2.0
-I/usr/local/lib/glib-2.0/include -I/usr/local/include/libxml2
-I/usr/local/include/libgsf-1 -I/usr/local/include/GraphicsMagick
-I/usr/local/include/orc-0.4 -I/usr/local/include/OpenEXR
-I/usr/local/include/poppler/glib -I/usr/local/include/cairo
-I/usr/local/include/pixman-1 -I/usr/local/include/freetype2
-I/usr/local/include/libdrm -pthread -D_THREAD_SAFE
-I/usr/local/include/libpng16 -I/usr/local/include/poppler
-I/usr/local/include/librsvg-2.0 -I/usr/local/include/gdk-pixbuf-2.0
-pthread -I/usr/local/include/pango-1.0 -I/usr/local/include/harfbuzz
-c Mosaic.cxx -o mosaic.o

clang++ -L/usr/local/lib -lvips-cpp -lvips -lgobject-2.0 -lglib-2.0
-lintl -L/usr/local/lib -lopencv_calib3d -lopencv_contrib -lopencv_core
-lopencv_features2d -lopencv_flann -lopencv_gpu -lopencv_highgui
-lopencv_imgproc -lopencv_legacy -lopencv_ml -lopencv_nonfree
-lopencv_objdetect -lopencv_ocl -lopencv_photo -lopencv_stitching
-lopencv_superres -lopencv_ts -lopencv_video -lopencv_videostab -ltbb
-lpthread -lm -L/opt/OpenSIFT/lib -lopensift -o mosaic mosaic.o

mosaic.o: In function dem(std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >)': /home/rmason/Programming/C/VipsMosaic2/Mosaic.cxx:383: undefined reference to sift_features(_IplImage*, feature**)'
/home/rmason/Programming/C/VipsMosaic2/Mosaic.cxx:384: undefined reference to sift_features(_IplImage*, feature**)' /home/rmason/Programming/C/VipsMosaic2/Mosaic.cxx:389: undefined reference to kdtree_bbf_knn(kd_node*, feature*, int, feature***, int)'
/home/rmason/Programming/C/VipsMosaic2/Mosaic.cxx:392: undefined reference to descr_dist_sq(feature*, feature*)' /home/rmason/Programming/C/VipsMosaic2/Mosaic.cxx:393: undefined reference to descr_dist_sq(feature*, feature*)'
clang++: error: linker command failed with exit code 1 (use -v to see invocation)

I've tried various versions of the link line, modified sift.h to declare
sift_features extern "C", but to no avail.

If you have suggestions on how to link C++ against libsift I would be
most grateful to hear them.

Thanks,
Roger
FreeBSD 10.3

fails @ make

Different feature detector

Is it possible to use a different feature detector (like MSER or STAR)?

memory leak issue in the match (bin)

Hi,
I'm using match.c for matching two frames. I ran the executable with valgrind tool. I found 6 blocks are still reachable.
And the print is as follows:

==17724== Memcheck, a memory error detector
==17724== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==17724== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==17724== Command: ./bin/match /home/gaian/test_png_folder/thumb5.png /home/gaian/test_png_folder/thumb6.png
==17724==
==17724== Conditional jump or move depends on uninitialised value(s)
==17724== at 0x5B04DD8: inflateReset2 (in /lib/i386-linux-gnu/libz.so.1.2.3.4)
==17724== by 0x5B04EC7: inflateInit2_ (in /lib/i386-linux-gnu/libz.so.1.2.3.4)
==17724==
Finding features in /home/image1.png...
Finding features in /home/image2.png...
Building kd tree...
Found 2710 total matches
==17724==
==17724== HEAP SUMMARY:
==17724== in use at exit: 9,276 bytes in 6 blocks
==17724== total heap usage: 807,627 allocs, 807,621 frees, 282,519,676 bytes allocated
==17724==
==17724== 1,036 bytes in 1 blocks are still reachable in loss record 1 of 6
==17724== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==17724== by 0x6FA0979: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F9F2FB: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6FA1064: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F62B03: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x400EEAA: call_init (dl-init.c:85)
==17724== by 0x400EF93: _dl_init (dl-init.c:134)
==17724== by 0x400120E: ??? (in /lib/i386-linux-gnu/ld-2.15.so)
==17724==
==17724== 1,036 bytes in 1 blocks are still reachable in loss record 2 of 6
==17724== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==17724== by 0x6FA0979: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F9DDC4: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6FA1080: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F62B03: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x400EEAA: call_init (dl-init.c:85)
==17724== by 0x400EF93: _dl_init (dl-init.c:134)
==17724== by 0x400120E: ??? (in /lib/i386-linux-gnu/ld-2.15.so)
==17724==
==17724== 1,036 bytes in 1 blocks are still reachable in loss record 3 of 6
==17724== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==17724== by 0x6FA0979: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6FBCC34: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F8EF5A: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6FA108A: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F62B03: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x400EEAA: call_init (dl-init.c:85)
==17724== by 0x400EF93: _dl_init (dl-init.c:134)
==17724== by 0x400120E: ??? (in /lib/i386-linux-gnu/ld-2.15.so)
==17724==
==17724== 1,036 bytes in 1 blocks are still reachable in loss record 4 of 6
==17724== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==17724== by 0x6FA0979: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6FE1749: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F8EF32: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6FA108A: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F62B03: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x400EEAA: call_init (dl-init.c:85)
==17724== by 0x400EF93: _dl_init (dl-init.c:134)
==17724== by 0x400120E: ??? (in /lib/i386-linux-gnu/ld-2.15.so)
==17724==
==17724== 1,036 bytes in 1 blocks are still reachable in loss record 5 of 6
==17724== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==17724== by 0x6FA0979: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6FA4DA4: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6FA10AA: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x6F62B03: ??? (in /usr/lib/i386-linux-gnu/libpixman-1.so.0.30.2)
==17724== by 0x400EEAA: call_init (dl-init.c:85)
==17724== by 0x400EF93: _dl_init (dl-init.c:134)
==17724== by 0x400120E: ??? (in /lib/i386-linux-gnu/ld-2.15.so)
==17724==
==17724== 4,096 bytes in 1 blocks are still reachable in loss record 6 of 6
==17724== at 0x402BE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==17724== by 0x5C21AB7: libjpeg_general_init (in /usr/lib/i386-linux-gnu/libjpeg.so.8.0.2)
==17724== by 0x400EEAA: call_init (dl-init.c:85)
==17724== by 0x400EF93: _dl_init (dl-init.c:134)
==17724== by 0x400120E: ??? (in /lib/i386-linux-gnu/ld-2.15.so)
==17724==
==17724== LEAK SUMMARY:
==17724== definitely lost: 0 bytes in 0 blocks
==17724== indirectly lost: 0 bytes in 0 blocks
==17724== possibly lost: 0 bytes in 0 blocks
==17724== still reachable: 9,276 bytes in 6 blocks
==17724== suppressed: 0 bytes in 0 blocks
==17724==
==17724== For counts of detected and suppressed errors, rerun with: -v
==17724== Use --track-origins=yes to see where uninitialised values come from
==17724== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 0 from 0)

Document the Patent

SIFT is patent protected and naming this library "Open" may mislead people into believing that it is "free as in beer".

http://en.wikipedia.org/wiki/Scale-invariant_feature_transform

Please document this on your homepage... your code may be open source but anyone wanting to actually use it in the US needs to seek a commercial arrangement with UBC.

In the UK, it is not possible to patent an algorithm (although it is possible to patent one for a particular application, just not the mathematics of it).

dvips: DVI file can't be opened: _formulas.dvi: No such file or directory error: Problems running dvips. Check your installation!

No file _formulas.aux.

what is this? i am not understanding the problem.i don't able to fix it.plz help what to do

Strange piece of code (bug or small optim)

I found a strange piece of code in sift.c (line 251 to 263) : https://github.com/robwhess/opensift/blob/master/src/sift.c#L251

/*
precompute Gaussian sigmas using the following formula:

\sigma_{total}^2 = \sigma_{i}^2 + \sigma_{i-1}^2
*/
sig[0] = sigma;
k = pow( 2.0, 1.0 / intvls );
for( i = 1; i < intvls + 3; i++ )
{
  sig_prev = pow( k, i - 1 ) * sigma;
  sig_total = sig_prev * k;
  sig[i] = sqrt( sig_total * sig_total - sig_prev * sig_prev );
}

We can see that :

sig[0] = sigma
sig[i] = sqrt(sig_total * sig_total - sig_prev * sig_prev )
       = sqrt(sig_prev * sig_prev * k * k - sig_prev * sig_prev )
       = sig_prev * sqrt(  k * k -  1 )
       = k^(i-1) * sigma * sqrt(  k * k -  1 )

then

sig[0] = sigma
sig[1] = sigma * sqrt(  k * k -  1 )
sig[2] = k * sigma * sqrt(  k * k -  1 ) = k* sig[1] 
sig[3] = k^2 * sigma * sqrt(  k * k -  1 ) = k* sig[2] 
...

This lines can then we rewrite with less calculation :

k = pow( 2.0, 1.0 / intvls );
double sk2m1 = sqrt( k*k- 1 );
sig[0] = sigma;
sig[1] = sigma * sk2m1;
for (int i = 2; i < intvls + 3; i++)
    sig[i] = sig[i-1] * k;

In the first code it seems sig_prev != sig[i-1], but sig_prev is used instead of sig[i-1] in the formula sqrt(sig_total * sig_total - sig_prev * sig_prev ).

Insufficient memory

I use the siftfeat function of OpenSIFT, but I get an Insufficient memory Exception.
Is this a known Issue?

The Picture I use is 5,6 MB (5647400 Bytes) and 7110x5427 pixel in size.
Try it with this, for example:
http://eoimages.gsfc.nasa.gov/images/imagerecords/80000/80258/kilauea_wv2_2011135_lrg.jpg
The RAM is 8GB (Exception when 4GB are used).
The OS is mint Linux 64bit.