1 CvMat* ransac_xform( struct feature* features, int n, int mtype,2              ransac_xform_fn xform_fn, int m, double p_badxform,3              ransac_err_fn err_fn, double err_tol,4              struct feature*** inliers, int* n_in )

  1 CvMat* ransac_xform( struct feature* features, int n, int mtype,  2                     ransac_xform_fn xform_fn, int m, double p_badxform,  3                     ransac_err_fn err_fn, double err_tol,  4 struct feature*** inliers, int* n_in )  5 {  6     //matched：所有具有mtype类型匹配点的特征点的数组，也就是样本集  7     //sample：单个样本，即4个特征点的数组  8     //consensus：当前一致集；  9     //consensus_max：当前最大一致集(即当前的最好结果的一致集) 10     struct feature** matched, ** sample, ** consensus, ** consensus_max = NULL; 11     struct ransac_data* rdata;//每个特征点的feature_data域的ransac数据指针 12     CvPoint2D64f* pts, * mpts;//每个样本对应的两个坐标数组：特征点坐标数组pts和匹配点坐标数组mpts 13     CvMat* M = NULL;//当前变换矩阵 14     //p：当前计算出的模型的错误概率，当p小于p_badxform时迭代停止 15     //in_frac：内点数目占样本总数目的百分比 16     double p, in_frac = RANSAC_INLIER_FRAC_EST; 17     //nm：输入的特征点数组中具有mtype类型匹配点的特征点个数 18     //in：当前一致集中元素个数 19     //in_min：一致集中元素个数允许的最小值，保证RANSAC最终计算出的转换矩阵错误的概率小于p_badxform所需的最小内点数目 20     //in_max：当前最优一致集(最大一致集)中元素的个数 21     //k：迭代次数，与计算当前模型的错误概率有关 22     int i, nm, in, in_min, in_max = 0, k = 0; 23  24     //找到特征点数组features中所有具有mtype类型匹配点的特征点，放到matched数组(样本集)中，返回值nm是matched数组的元素个数 25     nm = get_matched_features( features, n, mtype, &matched ); 26     //若找到的具有匹配点的特征点个数小于计算变换矩阵需要的最小特征点对个数，出错 27     if( nm < m ) 28     {   //出错处理，特征点对个数不足 29         fprintf( stderr, "Warning: not enough matches to compute xform, %s"  30             " line %d\n", __FILE__, __LINE__ ); 31         goto end; 32     } 33  34     /* initialize random number generator */ 35     srand( time(NULL) );//初始化随机数生成器 36  37     //计算保证RANSAC最终计算出的转换矩阵错误的概率小于p_badxform所需的最小内点数目 38     in_min = calc_min_inliers( nm, m, RANSAC_PROB_BAD_SUPP, p_badxform ); 39     //当前计算出的模型的错误概率,内点所占比例in_frac越大，错误概率越小；迭代次数k越大，错误概率越小 40     p = pow( 1.0 - pow( in_frac, m ), k ); 41     i = 0; 42  43     //当前错误概率大于输入的允许错误概率p_badxform，继续迭代 44     while( p > p_badxform ) 45     { 46         //从样本集matched中随机抽选一个RANSAC样本(即一个4个特征点的数组)，放到样本变量sample中 47         sample = draw_ransac_sample( matched, nm, m ); 48         //从样本中获取特征点和其对应匹配点的二维坐标，分别放到输出参数pts和mpts中 49         extract_corresp_pts( sample, m, mtype, &pts, &mpts ); 50         //调用参数中传入的函数xform_fn，计算将m个点的数组pts变换为mpts的矩阵，返回变换矩阵给M 51         M = xform_fn( pts, mpts, m );//一般传入lsq_homog()函数 52         if( ! M )//出错判断 53             goto iteration_end; 54         //给定特征点集，变换矩阵，误差函数，计算出当前一致集consensus，返回一致集中元素个数给in 55         in = find_consensus( matched, nm, mtype, M, err_fn, err_tol, &consensus); 56  57         //若当前一致集大于历史最优一致集，即当前一致集为最优，则更新最优一致集consensus_max 58         if( in > in_max ) 59         { 60             if( consensus_max )//若之前有最优值，释放其空间 61                 free( consensus_max ); 62             consensus_max = consensus;//更新最优一致集 63             in_max = in;//更新最优一致集中元素个数 64             in_frac = (double)in_max / nm;//最优一致集中元素个数占样本总个数的百分比 65         } 66         else//若当前一致集小于历史最优一致集，释放当前一致集 67             free( consensus ); 68         cvReleaseMat( &M ); 69  70 iteration_end: 71         release_mem( pts, mpts, sample ); 72         p = pow( 1.0 - pow( in_frac, m ), ++k ); 73     } 74  75     //根据最优一致集计算最终的变换矩阵 76     /* calculate final transform based on best consensus set */ 77     //若最优一致集中元素个数大于最低标准，即符合要求 78     if( in_max >= in_min ) 79     { 80         //从最优一致集中获取特征点和其对应匹配点的二维坐标，分别放到输出参数pts和mpts中 81         extract_corresp_pts( consensus_max, in_max, mtype, &pts, &mpts ); 82         //调用参数中传入的函数xform_fn，计算将in_max个点的数组pts变换为mpts的矩阵，返回变换矩阵给M 83         M = xform_fn( pts, mpts, in_max ); 84         /***********下面会再进行一次迭代**********/ 85         //根据变换矩阵M从样本集matched中计算出一致集consensus，返回一致集中元素个数给in 86         in = find_consensus( matched, nm, mtype, M, err_fn, err_tol, &consensus); 87         cvReleaseMat( &M ); 88         release_mem( pts, mpts, consensus_max ); 89         //从一致集中获取特征点和其对应匹配点的二维坐标，分别放到输出参数pts和mpts中 90         extract_corresp_pts( consensus, in, mtype, &pts, &mpts ); 91         //调用参数中传入的函数xform_fn，计算将in个点的数组pts变换为mpts的矩阵，返回变换矩阵给M 92         M = xform_fn( pts, mpts, in ); 93         if( inliers ) 94         { 95             *inliers = consensus;//将最优一致集赋值给输出参数：inliers，即内点集合 96             consensus = NULL; 97         } 98         if( n_in ) 99             *n_in = in;//将最优一致集中元素个数赋值给输出参数：n_in，即内点个数100         release_mem( pts, mpts, consensus );101     }102     else if( consensus_max )103     {   //没有计算出符合要求的一致集104         if( inliers )105             *inliers = NULL;106         if( n_in )107             *n_in = 0;108         free( consensus_max );109     }110 111     //RANSAC算法结束：恢复特征点中被更改的数据域feature_data，并返回变换矩阵M112 end:113     for( i = 0; i < nm; i++ )114     {115         //利用宏feat_ransac_data来提取matched[i]中的feature_data成员并转换为ransac_data格式的指针116         rdata =http://www.mamicode.com/ feat_ransac_data( matched[i] );117         //恢复feature_data成员的以前的值118         matched[i]->feature_data = http://www.mamicode.com/rdata->orig_feat_data;119         free( rdata );//释放内存120     }121     free( matched );122 123     return M;//返回求出的变换矩阵M124 }

 1 //特征提取和匹配 2 void match(IplImage *img1,IplImage *img2) 3 { 4     IplImage *img1_Feat = cvCloneImage(img1);//复制图1，深拷贝，用来画特征点 5     IplImage *img2_Feat = cvCloneImage(img2);//复制图2，深拷贝，用来画特征点 6      7     struct feature *feat1, *feat2;//feat1：图1的特征点数组，feat2：图2的特征点数组 8     int n1, n2;//n1:图1中的特征点个数，n2：图2中的特征点个数 9     struct feature *feat;//每个特征点10     struct kd_node *kd_root;//k-d树的树根11     struct feature **nbrs;//当前特征点的最近邻点数组12     int matchNum;//经距离比值法筛选后的匹配点对的个数13     struct feature **inliers;//精RANSAC筛选后的内点数组14     int n_inliers;//经RANSAC算法筛选后的内点个数,即feat1中具有符合要求的特征点的个数15     16     //默认提取的是LOWE格式的SIFT特征点17     //提取并显示第1幅图片上的特征点18     n1 = sift_features( img1, &feat1 );//检测图1中的SIFT特征点,n1是图1的特征点个数19     export_features("feature1.txt",feat1,n1);//将特征向量数据写入到文件20     draw_features( img1_Feat, feat1, n1 );//画出特征点21     cvShowImage("img1_Feat",img1_Feat);//显示22 23     //提取并显示第2幅图片上的特征点24     n2 = sift_features( img2, &feat2 );//检测图2中的SIFT特征点，n2是图2的特征点个数25     export_features("feature2.txt",feat2,n2);//将特征向量数据写入到文件26     draw_features( img2_Feat, feat2, n2 );//画出特征点27     cvShowImage("img2_Feat",img2_Feat);//显示28     29     Point pt1,pt2;//连线的两个端点30     double d0,d1;//feat1中每个特征点到最近邻和次近邻的距离31     matchNum = 0;//经距离比值法筛选后的匹配点对的个数32 33     //将2幅图片合成1幅图片,上下排列34     stacked = stack_imgs( img1, img2 );//合成图像，显示经距离比值法筛选后的匹配结果35     stacked_ransac = stack_imgs( img1, img2 );//合成图像，显示经RANSAC算法筛选后的匹配结果36 37     //根据图2的特征点集feat2建立k-d树，返回k-d树根给kd_root38     kd_root = kdtree_build( feat2, n2 );39 40     //遍历特征点集feat1，针对feat1中每个特征点feat，选取符合距离比值条件的匹配点，放到feat的fwd_match域中41     for(int i = 0; i < n1; i++ )42     {43         feat = feat1+i;//第i个特征点的指针44         //在kd_root中搜索目标点feat的2个最近邻点，存放在nbrs中，返回实际找到的近邻点个数45         int k = kdtree_bbf_knn( kd_root, feat, 2, &nbrs, KDTREE_BBF_MAX_NN_CHKS );46         if( k == 2 )47         {48             d0 = descr_dist_sq( feat, nbrs[0] );//feat与最近邻点的距离的平方49             d1 = descr_dist_sq( feat, nbrs[1] );//feat与次近邻点的距离的平方50             //若d0和d1的比值小于阈值NN_SQ_DIST_RATIO_THR，则接受此匹配，否则剔除51             if( d0 < d1 * NN_SQ_DIST_RATIO_THR )52             {   //将目标点feat和最近邻点作为匹配点对53                 pt1 = Point( cvRound( feat->x ), cvRound( feat->y ) );//图1中点的坐标54                 pt2 = Point( cvRound( nbrs[0]->x ), cvRound( nbrs[0]->y ) );//图2中点的坐标(feat的最近邻点)55                 pt2.y += img1->height;//由于两幅图是上下排列的，pt2的纵坐标加上图1的高度，作为连线的终点56                 cvLine( stacked, pt1, pt2, CV_RGB(255,0,255), 1, 8, 0 );//画出连线57                 matchNum++;//统计匹配点对的个数58                 feat1[i].fwd_match = nbrs[0];//使点feat的fwd_match域指向其对应的匹配点59             }60         }61         free( nbrs );//释放近邻数组62     }63     qDebug()<<tr("经距离比值法筛选后的匹配点对个数：")<<matchNum<<endl;64     //显示并保存经距离比值法筛选后的匹配图65     cvNamedWindow(IMG_MATCH1);//创建窗口66     cvShowImage(IMG_MATCH1,stacked);//显示67 68     //利用RANSAC算法筛选匹配点,计算变换矩阵H69     CvMat * H = ransac_xform(feat1,n1,FEATURE_FWD_MATCH,lsq_homog,4,0.01,homog_xfer_err,3.0,&inliers,&n_inliers);70     qDebug()<<tr("经RANSAC算法筛选后的匹配点对个数：")<<n_inliers<<endl;71     //遍历经RANSAC算法筛选后的特征点集合inliers，找到每个特征点的匹配点，画出连线72     for(int i=0; i<n_inliers; i++)73     {74         feat = inliers[i];//第i个特征点75         pt1 = Point(cvRound(feat->x), cvRound(feat->y));//图1中点的坐标76         pt2 = Point(cvRound(feat->fwd_match->x), cvRound(feat->fwd_match->y));//图2中点的坐标(feat的匹配点)77         qDebug()<<"("<<pt1.x<<","<<pt1.y<<")--->("<<pt2.x<<","<<pt2.y<<")"<<endl;78         pt2.y += img1->height;//由于两幅图是上下排列的，pt2的纵坐标加上图1的高度，作为连线的终点79         cvLine(stacked_ransac,pt1,pt2,CV_RGB(255,0,255),1,8,0);//画出连线80     }81     cvNamedWindow(IMG_MATCH2);//创建窗口82     cvShowImage(IMG_MATCH2,stacked_ransac);//显示83 }