热线电话：13121318867

登录
首页精彩阅读KD树的应用（1）SIFT+KD_BBF搜索算法
KD树的应用（1）SIFT+KD_BBF搜索算法
2014-12-03
收藏

KD树的应用（1）SIFT+KD_BBF搜索算法

3.1、SIFT特征匹配算法    

    之前本blog内阐述过图像特征匹配SIFT算法，写过五篇文章，这五篇文章分别为：

  • 九、图像特征提取与匹配之SIFT算法      (sift算法系列五篇文章)
  • 九（续）、sift算法的编译与实现
  • 九（再续）、教你一步一步用c语言实现sift算法、上
  • 九（再续）、教你一步一步用c语言实现sift算法、下
  • 九（三续）：SIFT算法的应用--目标识别之Bag-of-words模型

    不熟悉SIFT算法相关概念的可以看上述几篇文章，这里不再做赘述。与此同时，本文此部分也作为十五个经典算法研究系列里SIFT算法的九之四续。

    OK，我们知道，在sift算法中，给定两幅图片图片，若要做特征匹配，一般会先提取出图片中的下列相关属性作为特征点：

  1. /** 
  2. Structure to represent an affine invariant image feature.  The fields 
  3. x, y, a, b, c represent the affine region around the feature: 
  4.  
  5. a(x-u)(x-u) + 2b(x-u)(y-v) + c(y-v)(y-v) = 1 
  6. */  
  7. struct feature  
  8. {  
  9.     double x;                      /**< x coord */  
  10.     double y;                      /**< y coord */  
  11.     double a;                      /**< Oxford-type affine region parameter */  
  12.     double b;                      /**< Oxford-type affine region parameter */  
  13.     double c;                      /**< Oxford-type affine region parameter */  
  14.     double scl;                    /**< scale of a Lowe-style feature */  
  15.     double ori;                    /**< orientation of a Lowe-style feature */  
  16.     int d;                         /**< descriptor length */  
  17.     double descr[FEATURE_MAX_D];   /**< descriptor */  
  18.     int type;                      /**< feature type, OXFD or LOWE */  
  19.     int category;                  /**< all-purpose feature category */  
  20.     struct feature* fwd_match;     /**< matching feature from forward image */  
  21.     struct feature* bck_match;     /**< matching feature from backmward image */  
  22.     struct feature* mdl_match;     /**< matching feature from model */  
  23.     CvPoint2D64f img_pt;           /**< location in image */  
  24.     CvPoint2D64f mdl_pt;           /**< location in model */  
  25.     void* feature_data;            /**< user-definable data */  
  26.     char dense;                     /*表征特征点所处稠密程度*/  
  27. };  
    而后在sift.h文件中定义两个关键函数，这里，我们把它们称之为函数一，和函数二，如下所示：

函数一的声明：

  1. extern int sift_features( IplImage* img, struct feature** feat );  

函数一的实现：

  1. int sift_features( IplImage* img, struct feature** feat )  
  2. {  
  3.     return _sift_features( img, feat, SIFT_INTVLS, SIFT_SIGMA, SIFT_CONTR_THR,  
  4.                             SIFT_CURV_THR, SIFT_IMG_DBL, SIFT_DESCR_WIDTH,  
  5.                             SIFT_DESCR_HIST_BINS );  
  6. }  
从上述函数一的实现中，我们可以看到，它内部实际上调用的是这个函数：_sift_features(..)，也就是下面马上要分析的函数二。

函数二的声明：

  1. extern int _sift_features( IplImage* img, struct feature** feat, int intvls,  
  2.                           double sigma, double contr_thr, int curv_thr,  
  3.                           int img_dbl, int descr_width, int descr_hist_bins );  

函数二的实现：

  1. int _sift_features( IplImage* img, struct feature** feat, int intvls,  
  2.                    double sigma, double contr_thr, int curv_thr,  
  3.                    int img_dbl, int descr_width, int descr_hist_bins )  
  4. {  
  5.     IplImage* init_img;  
  6.     IplImage*** gauss_pyr, *** dog_pyr;  
  7.     CvMemStorage* storage;  
  8.     CvSeq* features;  
  9.     int octvs, i, n = 0,n0 = 0,n1 = 0,n2 = 0,n3 = 0,n4 = 0;  
  10.     int start;  
  11.   
  12.     /* check arguments */  
  13.     if( ! img )  
  14.         fatal_error( "NULL pointer error, %s, line %d",  __FILE__, __LINE__ );  
  15.   
  16.     if( ! feat )  
  17.         fatal_error( "NULL pointer error, %s, line %d",  __FILE__, __LINE__ );  
  18.   
  19.     /* build scale space pyramid; smallest dimension of top level is ~4 pixels */  
  20.     start=GetTickCount();  
  21.     init_img = create_init_img( img, img_dbl, sigma );  
  22.     octvs = log( (float)(MIN( init_img->width, init_img->height )) ) / log((float)(2.0)) -5;  
  23.     gauss_pyr = build_gauss_pyr( init_img, octvs, intvls, sigma );  
  24.     dog_pyr = build_dog_pyr( gauss_pyr, octvs, intvls );  
  25.     fprintf( stderr, " creat the pyramid use %d\n",GetTickCount()-start);  
  26.   
  27.     storage = cvCreateMemStorage( 0 );    //创建存储内存，0为默认64k  
  28.     start=GetTickCount();  
  29.     features = scale_space_extrema( dog_pyr, octvs, intvls, contr_thr,  
  30.         curv_thr, storage );  //在DOG空间寻找极值点，确定关键点位置  
  31.     fprintf( stderr, " find the extrum points in DOG use %d\n",GetTickCount()-start);  
  32.   
  33.     calc_feature_scales( features, sigma, intvls ); //计算关键点的尺度  
  34.   
  35.     if( img_dbl )  
  36.         adjust_for_img_dbl( features );  //如果原始空间图扩大，特征点坐标就缩小  
  37.     start=GetTickCount();  
  38.     calc_feature_oris( features, gauss_pyr );  //在gaussian空间计算关键点的主方向和幅值  
  39.     fprintf( stderr, " get the main oritation use %d\n",GetTickCount()-start);  
  40.   
  41.     start=GetTickCount();  
  42.     compute_descriptors( features, gauss_pyr, descr_width, descr_hist_bins ); //建立关键点描述器  
  43.     fprintf( stderr, " compute the descriptors use %d\n",GetTickCount()-start);  
  44.   
  45.     /* sort features by decreasing scale and move from CvSeq to array */  
  46.     //start=GetTickCount();  
  47.     //cvSeqSort( features, (CvCmpFunc)feature_cmp, NULL ); //?????  
  48.     n = features->total;  
  49.     *feat = (feature*)(calloc( n, sizeof(struct feature) ));  
  50.     *feat = (feature*)(cvCvtSeqToArray( features, *feat, CV_WHOLE_SEQ )); //整条链表放在feat指向的内存  
  51.   
  52.     for( i = 0; i < n; i++ )  
  53.     {  
  54.         free( (*feat)[i].feature_data );  
  55.         (*feat)[i].feature_data = NULL;  //释放ddata(r,c,octv,intvl,xi,scl_octv)  
  56.         if((*feat)[i].dense == 4) ++n4;  
  57.         else if((*feat)[i].dense == 3) ++n3;  
  58.         else if((*feat)[i].dense == 2) ++n2;  
  59.         else if((*feat)[i].dense == 1) ++n1;  
  60.         else                         ++n0;  
  61.     }  
  62.   
  63.     //fprintf( stderr, " move features from sequce to array use %d\n",GetTickCount()-start);  
  64.     //start=GetTickCount();  
  65.     fprintf( stderr, "In the total feature points the extent4 points is %d\n",n4);  
  66.     fprintf( stderr, "In the total feature points the extent3 points is %d\n",n3);  
  67.     fprintf( stderr, "In the total feature points the extent2 points is %d\n",n2);  
  68.     fprintf( stderr, "In the total feature points the extent1 points is %d\n",n1);  
  69.     fprintf( stderr, "In the total feature points the extent0 points is %d\n",n0);  
  70.     cvReleaseMemStorage( &storage );  
  71.     cvReleaseImage( &init_img );  
  72.     release_pyr( &gauss_pyr, octvs, intvls + 3 );  
  73.     release_pyr( &dog_pyr, octvs, intvls + 2 );  
  74.     //fprintf( stderr, " free the pyramid use %d\n",GetTickCount()-start);  
  75.     return n;  
  76. }  
    说明：上面的函数二，包含了SIFT算法中几乎所有函数，是SIFT算法的核心。本文不打算一一分析上面所有函数，只会抽取其中涉及到BBF查询机制相关的函数。


CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>>   “CDA报名” 了解CDA考试详情；

▷ 想加入CDA考试题库，点击>>> “CDA题库” 了解CDA考试详情；

▷ 想学习CDA考试教材，点击>>> “CDA教材” 了解CDA考试详情；

▷ 想查询CDA考试成绩，点击>>> “CDA成绩” 了解CDA考试详情；

▷ 想了解CDA考试含金量，点击>>> “CDA含金量” 了解CDA考试详情；

▷ 想获取CDA考试时间/费用/条件/大纲/通过率，点击 >>>“CDA考试官网” 了解CDA考试详情；

特征 特征提取

数据分析咨询请扫描二维码

上一篇成为CDA会员俱乐部志愿者你将获得！
下一篇图论在大数据分析中的作用！
CDA考试动态
CDA报考指南
热门栏目
最新资讯
更多
Copyright © 2015-present 北京国富如荷网络科技有限公司 All Rights Reserved.
京ICP备11001960号-9   京公网安备 11010802034615号   经营许可证编号：京B2-20210330
客服在线
立即咨询