sift match

#include <cv.h> #include <cxcore.h> #include <highgui.h> #include <stdio.h> #include <time.h> #include "windows.h" const double PI2 = 2.0 * CV_PI; /******************************** Structures *********************************/ // Structure to represent an affine invariant image feature. // The fields x, y, a, b, c represent the affine region around the feature: // a(x-u)(x-u) + 2b(x-u)(y-v) + c(y-v)(y-v) = 1 //+++++++++++++++++++ struct feature { double x; /**< x coord */ double y; /**< y coord */ double a; /**< Oxford-type affine region parameter */ double b; /**< Oxford-type affine region parameter */ double c; /**< Oxford-type affine region parameter */ double scl; /**< scale of a Lowe-style feature */ double ori; /**< orientation of a Lowe-style feature */ int d; /**< descriptor length */ double descr[128]; /**< descriptor */ int type; /**< feature type, OXFD or LOWE */ int category; /**< all-purpose feature category */ struct feature* fwd_match; /**< matching feature from forward image */ struct feature* bck_match; /**< matching feature from backmward image */ struct feature* mdl_match; /**< matching feature from model */ CvPoint2D64f img_pt; /**< location in image */ CvPoint2D64f mdl_pt; /**< location in model */ void* feature_data; /**< user-definable data */ }; struct feature; //+++++++++++++++++++ /** a node in a k-d tree */ struct kd_node { int ki; /**< partition key index */ double kv; /**< partition key value */ int leaf; /**< 1 if node is a leaf, 0 otherwise */ struct feature* features; /**< features at this node */ int n; /**< number of features */ struct kd_node* kd_left; /**< left child */ struct kd_node* kd_right; /**< right child */ }; //+++++++++++++++++++ /** holds feature data relevant to detection */ struct detection_data { int r; int c; int octv; int intvl; double subintvl; double scl_octv; }; /** FEATURE_OXFD <BR> FEATURE_LOWE */ enum feature_type { FEATURE_OXFD, FEATURE_LOWE, }; /** FEATURE_FWD_MATCH <BR> FEATURE_BCK_MATCH <BR> FEATURE_MDL_MATCH */ enum feature_match_type { FEATURE_FWD_MATCH, FEATURE_BCK_MATCH, FEATURE_MDL_MATCH, }; /** Structure to represent an affine invariant image feature. The fields x, y, a, b, c represent the affine region around the feature: a(x-u)(x-u) + 2b(x-u)(y-v) + c(y-v)(y-v) = 1 */ struct bbf_data { double d; void* old_data; }; /** holds feature data relevant to ransac */ struct ransac_data { void* orig_feat_data; int sampled; }; /* initial # of priority queue elements for which to allocate space */ #define MINPQ_INIT_NALLOCD 512 /********************************** Structures *******************************/ /** an element in a minimizing priority queue */ struct pq_node { void* data; int key; }; /** a minimizing priority queue */ struct min_pq { struct pq_node* pq_array; /* array containing priority queue */ int nallocd; /* number of elements allocated */ int n; /**< number of elements in pq */ }; /*************************** Function Prototypes *****************************/ /** Creates a new minimizing priority queue. */ extern struct min_pq* minpq_init(); /** Inserts an element into a minimizing priority queue. @param min_pq a minimizing priority queue @param data the data to be inserted @param key the key to be associated with \a data @return Returns 0 on success or 1 on failure. */ extern int minpq_insert( struct min_pq* min_pq, void* data, int key ); /** Returns the element of a minimizing priority queue with the smallest key without removing it from the queue. @param min_pq a minimizing priority queue @return Returns the element of \a min_pq with the smallest key or NULL if \a min_pq is empty */ extern void* minpq_get_min( struct min_pq* min_pq ); /** Removes and returns the element of a minimizing priority queue with the smallest key. @param min_pq a minimizing priority queue @return Returns the element of \a min_pq with the smallest key of NULL if \a min_pq is empty */ extern void* minpq_extract_min( struct min_pq* min_pq ); /** De-allocates the memory held by a minimizing priorioty queue @param min_pq pointer to a minimizing priority queue */ extern void minpq_release( struct min_pq** min_pq ); /******************************* Defs and macros *****************************/ /* RANSAC error tolerance in pixels */ #define RANSAC_ERR_TOL 3 /** pessimistic estimate of fraction of inlers for RANSAC */ #define RANSAC_INLIER_FRAC_EST 0.25 /** estimate of the probability that a correspondence supports a bad model */ #define RANSAC_PROB_BAD_SUPP 0.10 /* extracts a feature's RANSAC data */ #define feat_ransac_data( feat ) ( (struct ransac_data*) (feat)->feature_data ) /******************************* Defs and macros *****************************/ /* colors in which to display different feature types */ #define FEATURE_OXFD_COLOR CV_RGB(255,255,0) #define FEATURE_LOWE_COLOR CV_RGB(255,0,255) /** max feature descriptor length */ #define FEATURE_MAX_D 64 /** default number of sampled intervals per octave */ #define SIFT_INTVLS 3 /** default sigma for initial gaussian smoothing */ #define SIFT_SIGMA 2.6 //1.6->0.6 /** default threshold on keypoint contrast |D(x)| */ #define SIFT_CONTR_THR 0.04 /** default threshold on keypoint ratio of principle curvatures */ #define SIFT_CURV_THR 10 /** double image size before pyramid construction? */ #define SIFT_IMG_DBL 1 /** default width of descriptor histogram array */ #define SIFT_DESCR_WIDTH 4 /** default number of bins per histogram in descriptor array */ #define SIFT_DESCR_HIST_BINS 8 /* assumed gaussian blur for input image */ #define SIFT_INIT_SIGMA 0.5 /* width of border in which to ignore keypoints */ #define SIFT_IMG_BORDER 5 /* maximum steps of keypoint interpolation before failure */ #define SIFT_MAX_INTERP_STEPS 5 /* default number of bins in histogram for orientation assignment */ #define SIFT_ORI_HIST_BINS 36 /* determines gaussian sigma for orientation assignment */ #define SIFT_ORI_SIG_FCTR 1.5 /* determines the radius of the region used in orientation assignment */ #define SIFT_ORI_RADIUS 3.0 * SIFT_ORI_SIG_FCTR /* number of passes of orientation histogram smoothing */ #define SIFT_ORI_SMOOTH_PASSES 2 /* orientation magnitude relative to max that results in new feature */ #define SIFT_ORI_PEAK_RATIO 0.8 /* determines the size of a single descriptor orientation histogram */ #define SIFT_DESCR_SCL_FCTR 3.0 /* threshold on magnitude of elements of descriptor vector */ #define SIFT_DESCR_MAG_THR 0.2 /* factor used to convert floating-point descriptor to unsigned char */ #define SIFT_INT_DESCR_FCTR 512.0 /* returns a feature's detection data */ #define feat_detection_data(f) ( (struct detection_data*)(f->feature_data) ) /* the maximum number of keypoint NN candidates to check during BBF search */ #define KDTREE_BBF_MAX_NN_CHKS 200 /* threshold on squared ratio of distances between NN and 2nd NN */ #define NN_SQ_DIST_RATIO_THR 0.49 #define ABS(x) ( ( x < 0 )? -x : x ) typedef CvMat* (*ransac_xform_fn)( CvPoint2D64f* pts, CvPoint2D64f* mpts, int n ); /** Prototype for error functions passed to ransac_xform(). For a given point, its correspondence, and a transform, functions of this type should compute a measure of error between the correspo