? ? 關(guān)于算法原理請參考《基于SURF特征的圖像與視頻拼接技術(shù)的研究》。一、問題提出? ??? ? RANSAC的算法原理并不復(fù)雜，比較復(fù)雜的地方在于“建立模型”和“評價(jià)模型”。我們經(jīng)常看到的是采用“直線”或者“圓”作為基本模型進(jìn)行“建立”，而采用所有點(diǎn)到該“直線”或“圓”的歐拉距離作為標(biāo)準(zhǔn)來“評價(jià)”（當(dāng)然是越小越好）。在經(jīng)典的圖像拼接算法中，需要對特征點(diǎn)進(jìn)行配對。采用的模型簡單來說為“根據(jù)4對特征點(diǎn)計(jì)算出單應(yīng)矩陣，而后計(jì)算圖1上所有對應(yīng)的特征點(diǎn)經(jīng)過這個‘單應(yīng)矩陣’變化后得到的圖片和圖2上的距離之和“（當(dāng)然也是越小越好）。? ? ? ? 為了提高識別的效率，前輩對算法進(jìn)行了不懈的研究和提升，目前看來，用于圖像拼接的RANSAC算法應(yīng)該如下：? ??
及其改進(jìn)算法：二、算法實(shí)現(xiàn)? ? ? ?a)數(shù)據(jù)準(zhǔn)備某大學(xué)圖片，很明顯的有視場變化? ? ? ?b)算法分析，參考《基于SURF特征的圖像與視頻拼接技術(shù)的研究和實(shí)現(xiàn)一 和 二》? ? ? ?現(xiàn)在思考，RANSAC算法其實(shí)是”基于統(tǒng)計(jì)的配對算法“，在進(jìn)入RANSAC算法流程之前，已經(jīng)計(jì)算出來圖1和圖2上的特征點(diǎn)值了。我們不僅需要根據(jù)這些點(diǎn)值去預(yù)測模型，而且需要去檢測模型。這個模型也不是憑空隨便找的，而是以”透視變換“作為基礎(chǔ)的（關(guān)于透視變化請參考我前面的博文）。? ? ? ? 尋找的方法是首先找到符合某一模型的”內(nèi)點(diǎn)集“，而后根據(jù)這一”內(nèi)點(diǎn)集“，創(chuàng)建變換模型。? ? ? ? 尋找”內(nèi)點(diǎn)集“的方法就是直接從現(xiàn)有的數(shù)據(jù)中找出一部分?jǐn)?shù)據(jù)計(jì)算出一個模型，而后根據(jù)這個模型計(jì)算所有點(diǎn)的誤差，迭代多次，得到最小誤差的情況（和對應(yīng)的點(diǎn)集），這個時候的模型就是接近正確的模型。? ? ? ? 這個誤差的計(jì)算方法也是設(shè)計(jì)出來的（很可能還是統(tǒng)計(jì)值）。? ? ? ? 所以RANSAC很像是基于統(tǒng)計(jì)的一種計(jì)算可行解的模式。很多時候你不是需要從很多的數(shù)據(jù)中找出一個模型來嗎？比如馬爾薩斯模型？這個模型可能有函數(shù)，還有參數(shù)。你猜測的是函數(shù)，但是參數(shù)就可以通過這種模式來進(jìn)行計(jì)算。? ? ? ? 如果有比較好的評價(jià)函數(shù)，最后你還可以比較幾種函數(shù)的選擇。所以RANSAC就是一種單模型下基于離散數(shù)據(jù)計(jì)算模型的方法。（其實(shí)也是直觀的、基礎(chǔ)的、簡潔的、有效的）? ? ? ?這樣我想起之前研究過的一種叫做”交叉檢驗(yàn)“(cross check /cross validation)的東西。? ? ? ?定義：在給定的建模樣本中，拿出大部分樣本進(jìn)行模型建立，留小部分對建立的模型進(jìn)行預(yù)報(bào)，并將這小部分進(jìn)行誤差預(yù)報(bào)，計(jì)算平方加和。（然后當(dāng)然是選取誤差最小的模型和）? ? ? ?相比較RANSAC和CROSS VALIDATION，有兩點(diǎn)不同。一個是模型的建立，RANSAC是選擇很少量的數(shù)據(jù)建立模型（比如圓、線、透視變換），而后大量數(shù)據(jù)做驗(yàn)證；而CROSS需要較多的數(shù)據(jù)建立模型（比如MLP，神網(wǎng)），較少的數(shù)據(jù)進(jìn)行驗(yàn)證（它也只有較少的數(shù)據(jù)了）? ? ? ?c)解析OPENCV中的實(shí)現(xiàn)? ? ? ?為了實(shí)現(xiàn)圖像的特征點(diǎn)的匹配，并且最后實(shí)現(xiàn)圖像拼接，在OPENCV中實(shí)現(xiàn)了RANSAC算法及其改進(jìn)算法? ? ? ?c.1 調(diào)用方法? ? ??????//--?Step?3:?匹配????FlannBasedMatcher?matcher;//BFMatcher為強(qiáng)制匹配????std::vector<?DMatch?>?matches;????matcher.match(?descriptors_1,?descriptors_2,?matches?);????//取最大最小距離????double?max_dist?=?0;?double?min_dist?=?100;????for(?int?i?=?0;?i?<?descriptors_1.rows;?i++?)????{?????????double?dist?=?matches[i].distance;????????if(?dist?<?min_dist?)?min_dist?=?dist;????????if(?dist?>?max_dist?)?max_dist?=?dist;????}????std::vector<?DMatch?>?good_matches;????for(?int?i?=?0;?i?<?descriptors_1.rows;?i++?)????{?????????if(?matches[i].distance?<=?3*min_dist?)//這里的閾值選擇了3倍的min_dist????????{?????????????good_matches.push_back(?matches[i]);?????????}????}????//畫出"good?match"????Mat?img_matches;????drawMatches(?img_1,?keypoints_1,?img_2,?keypoints_2,????????good_matches,?img_matches,?Scalar::all(-1),?Scalar::all(-1),????????vector<char>(),?DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS?);????//--?Localize?the?object?from?img_1?in?img_2????std::vector<Point2f>?obj;????std::vector<Point2f>?scene;????for(?int?i?=?0;?i?<?(int)good_matches.size();?i++?)????{????????????obj.push_back(?keypoints_1[?good_matches[i].queryIdx?].pt?);????????scene.push_back(?keypoints_2[?good_matches[i].trainIdx?].pt?);????}????//直接調(diào)用ransac,計(jì)算單應(yīng)矩陣????Mat?H?=?findHomography(?obj,?scene,?CV_RANSAC?);? ? ? ?c.2 原理分析? ? ? ?opencv中已經(jīng)封裝的很好了，注意的是在實(shí)際使用中還可以對識別出來的結(jié)果做進(jìn)一步的處理。? ? ??findHomography的定義參數(shù)分為points1和points2,參數(shù)3是method,然后是threshold(一般為3),最后為maskcv::Mat cv::findHomography( InputArray _points1, InputArray _points2,
? ? ? ? ? ? ? ? ? ? ? ? ? ? int method, double ransacReprojThreshold, OutputArray _mask )
{
? ? const double confidence = 0.995;
? ? const int maxIters = 2000;
? ? const double defaultRANSACReprojThreshold = 3;
? ? bool result = false;

? ? Mat points1 = _points1.getMat(), points2 = _points2.getMat();
? ? Mat src, dst, H, tempMask;
? ? int npoints = -1;

? ? for( int i = 1; i <= 2; i++ )
? ? {
? ? ? ? Mat& p = i == 1 ? points1 : points2;
? ? ? ? Mat& m = i == 1 ? src : dst;
? ? ? ? npoints = p.checkVector(2, -1, false);
? ? ? ? if( npoints < 0 )
? ? ? ? {
? ? ? ? ? ? npoints = p.checkVector(3, -1, false);
? ? ? ? ? ? if( npoints < 0 )
? ? ? ? ? ? ? ? CV_Error(Error::StsBadArg, "The input arrays should be 2D or 3D point sets");
? ? ? ? ? ? if( npoints == 0 )
? ? ? ? ? ? ? ? return Mat();
? ? ? ? ? ? convertPointsFromHomogeneous(p, p);
? ? ? ? }
? ? ? ? p.reshape(2, npoints).convertTo(m, CV_32F);
? ? }

? ? CV_Assert( src.checkVector(2) == dst.checkVector(2) );

? ? if( ransacReprojThreshold <= 0 )
? ? ? ? ransacReprojThreshold = defaultRANSACReprojThreshold;

? ? Ptr<PointSetRegistrator::Callback> cb = makePtr<HomographyEstimatorCallback>();

? ? if( method == 0 || npoints == 4 )
? ? {
? ? ? ? tempMask = Mat::ones(npoints, 1, CV_8U);
? ? ? ? result = cb->runKernel(src, dst, H) > 0;
? ? }
? ? else if( method == RANSAC )
? ? ? ? result = createRANSACPointSetRegistrator(cb, 4, ransacReprojThreshold, confidence, maxIters)->run(src, dst, H, tempMask);
? ? else if( method == LMEDS )
? ? ? ? result = createLMeDSPointSetRegistrator(cb, 4, confidence, maxIters)->run(src, dst, H, tempMask);
? ? else
? ? ? ? CV_Error(Error::StsBadArg, "Unknown estimation method");

? ? if( result && npoints > 4 )
? ? {
? ? ? ? compressPoints( src.ptr<Point2f>(), tempMask.ptr<uchar>(), 1, npoints );
? ? ? ? npoints = compressPoints( dst.ptr<Point2f>(), tempMask.ptr<uchar>(), 1, npoints );
? ? ? ? if( npoints > 0 )
? ? ? ? {
? ? ? ? ? ? Mat src1 = src.rowRange(0, npoints);
? ? ? ? ? ? Mat dst1 = dst.rowRange(0, npoints);
? ? ? ? ? ? src = src1;
? ? ? ? ? ? dst = dst1;
? ? ? ? ? ? if( method == RANSAC || method == LMEDS )
? ? ? ? ? ? ? ? cb->runKernel( src, dst, H );
? ? ? ? ? ? Mat H8(8, 1, CV_64F, H.ptr<double>());
? ? ? ? ? ? createLMSolver(makePtr<HomographyRefineCallback>(src, dst), 10)->run(H8);
? ? ? ? }
? ? }

? ? if( result )
? ? {
? ? ? ? if( _mask.needed() )
? ? ? ? ? ? tempMask.copyTo(_mask);
? ? }
? ? else
? ? ? ? H.release();

? ? return H;
}? ? ? ?和RANSAC相關(guān)的是Ptr<PointSetRegistrator> createRANSACPointSetRegistrator(const Ptr<PointSetRegistrator::Callback>& _cb,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int _modelPoints, double _threshold,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?double _confidence, int _maxIters)
{
? ? CV_Assert( !RANSACPointSetRegistrator_info_auto.name().empty() );
? ? return Ptr<PointSetRegistrator>(
? ? ? ? new RANSACPointSetRegistrator(_cb, _modelPoints, _threshold, _confidence, _maxIters));
}??? ??class RANSACPointSetRegistrator : public PointSetRegistrator{
public:
? ? RANSACPointSetRegistrator(const Ptr<PointSetRegistrator::Callback>& _cb=Ptr<PointSetRegistrator::Callback>(),
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? int _modelPoints=0, double _threshold=0, double _confidence=0.99, int _maxIters=1000)
? ? : cb(_cb), modelPoints(_modelPoints), threshold(_threshold), confidence(_confidence), maxIters(_maxIters)
? ? {
? ? ? ? checkPartialSubsets = true;
? ? }

? ? int findInliers( const Mat& m1, const Mat& m2, const Mat& model, Mat& err, Mat& mask, double thresh ) const
? ? {
? ? ? ? cb->computeError( m1, m2, model, err );
? ? ? ? mask.create(err.size(), CV_8U);

? ? ? ? CV_Assert( err.isContinuous() && err.type() == CV_32F && mask.isContinuous() && mask.type() == CV_8U);
? ? ? ? const float* errptr = err.ptr<float>();
? ? ? ? uchar* maskptr = mask.ptr<uchar>();
? ? ? ? float t = (float)(thresh*thresh);
? ? ? ? int i, n = (int)err.total(), nz = 0;
? ? ? ? for( i = 0; i < n; i++ )
? ? ? ? {
? ? ? ? ? ? int f = errptr[i] <= t;
? ? ? ? ? ? maskptr[i] = (uchar)f;
? ? ? ? ? ? nz += f;
? ? ? ? }
? ? ? ? return nz;
? ? }

? ? bool getSubset( const Mat& m1, const Mat& m2,
? ? ? ? ? ? ? ? ? ? Mat& ms1, Mat& ms2, RNG& rng,
? ? ? ? ? ? ? ? ? ? int maxAttempts=1000 ) const
? ? {
? ? ? ? cv::AutoBuffer<int> _idx(modelPoints);
? ? ? ? int* idx = _idx;
? ? ? ? int i = 0, j, k, iters = 0;
? ? ? ? int esz1 = (int)m1.elemSize(), esz2 = (int)m2.elemSize();
? ? ? ? int d1 = m1.channels() > 1 ? m1.channels() : m1.cols;
? ? ? ? int d2 = m2.channels() > 1 ? m2.channels() : m2.cols;
? ? ? ? int count = m1.checkVector(d1), count2 = m2.checkVector(d2);
? ? ? ? const int *m1ptr = m1.ptr<int>(), *m2ptr = m2.ptr<int>();

? ? ? ? ms1.create(modelPoints, 1, CV_MAKETYPE(m1.depth(), d1));
? ? ? ? ms2.create(modelPoints, 1, CV_MAKETYPE(m2.depth(), d2));

? ? ? ? int *ms1ptr = ms1.ptr<int>(), *ms2ptr = ms2.ptr<int>();

? ? ? ? CV_Assert( count >= modelPoints && count == count2 );
? ? ? ? CV_Assert( (esz1 % sizeof(int)) == 0 && (esz2 % sizeof(int)) == 0 );
? ? ? ? esz1 /= sizeof(int);
? ? ? ? esz2 /= sizeof(int);

? ? ? ? for(; iters < maxAttempts; iters++)
? ? ? ? {
? ? ? ? ? ? for( i = 0; i < modelPoints && iters < maxAttempts; )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int idx_i = 0;
? ? ? ? ? ? ? ? for(;;)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? idx_i = idx[i] = rng.uniform(0, count);
? ? ? ? ? ? ? ? ? ? for( j = 0; j < i; j++ )
? ? ? ? ? ? ? ? ? ? ? ? if( idx_i == idx[j] )
? ? ? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? if( j == i )
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? for( k = 0; k < esz1; k++ )
? ? ? ? ? ? ? ? ? ? ms1ptr[i*esz1 + k] = m1ptr[idx_i*esz1 + k];
? ? ? ? ? ? ? ? for( k = 0; k < esz2; k++ )
? ? ? ? ? ? ? ? ? ? ms2ptr[i*esz2 + k] = m2ptr[idx_i*esz2 + k];
? ? ? ? ? ? ? ? if( checkPartialSubsets && !cb->checkSubset( ms1, ms2, i+1 ))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? iters++;
? ? ? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? ? ? if( !checkPartialSubsets && i == modelPoints && !cb->checkSubset(ms1, ms2, i))
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? break;
? ? ? ? }

? ? ? ? return i == modelPoints && iters < maxAttempts;
? ? }

? ? bool run(InputArray _m1, InputArray _m2, OutputArray _model, OutputArray _mask) const
? ? {
? ? ? ? bool result = false;
? ? ? ? Mat m1 = _m1.getMat(), m2 = _m2.getMat();
? ? ? ? Mat err, mask, model, bestModel, ms1, ms2;

? ? ? ? int iter, niters = MAX(maxIters, 1);
? ? ? ? int d1 = m1.channels() > 1 ? m1.channels() : m1.cols;
? ? ? ? int d2 = m2.channels() > 1 ? m2.channels() : m2.cols;
? ? ? ? int count = m1.checkVector(d1), count2 = m2.checkVector(d2), maxGoodCount = 0;

? ? ? ? RNG rng((uint64)-1);

? ? ? ? CV_Assert( cb );
? ? ? ? CV_Assert( confidence > 0 && confidence < 1 );

? ? ? ? CV_Assert( count >= 0 && count2 == count );
? ? ? ? if( count < modelPoints )
? ? ? ? ? ? return false;

? ? ? ? Mat bestMask0, bestMask;

? ? ? ? if( _mask.needed() )
? ? ? ? {
? ? ? ? ? ? _mask.create(count, 1, CV_8U, -1, true);
? ? ? ? ? ? bestMask0 = bestMask = _mask.getMat();
? ? ? ? ? ? CV_Assert( (bestMask.cols == 1 || bestMask.rows == 1) && (int)bestMask.total() == count );
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? bestMask.create(count, 1, CV_8U);
? ? ? ? ? ? bestMask0 = bestMask;
? ? ? ? }

? ? ? ? if( count == modelPoints )
? ? ? ? {
? ? ? ? ? ? if( cb->runKernel(m1, m2, bestModel) <= 0 )
? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? bestModel.copyTo(_model);
? ? ? ? ? ? bestMask.setTo(Scalar::all(1));
? ? ? ? ? ? return true;
? ? ? ? }

? ? ? ? for( iter = 0; iter < niters; iter++ )
? ? ? ? {
? ? ? ? ? ? int i, goodCount, nmodels;
? ? ? ? ? ? if( count > modelPoints )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? bool found = getSubset( m1, m2, ms1, ms2, rng );
? ? ? ? ? ? ? ? if( !found )
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if( iter == 0 )
? ? ? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }

? ? ? ? ? ? nmodels = cb->runKernel( ms1, ms2, model );
? ? ? ? ? ? if( nmodels <= 0 )
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? CV_Assert( model.rows % nmodels == 0 );
? ? ? ? ? ? Size modelSize(model.cols, model.rows/nmodels);

? ? ? ? ? ? for( i = 0; i < nmodels; i++ )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Mat model_i = model.rowRange( i*modelSize.height, (i+1)*modelSize.height );
? ? ? ? ? ? ? ? goodCount = findInliers( m1, m2, model_i, err, mask, threshold );

? ? ? ? ? ? ? ? if( goodCount > MAX(maxGoodCount, modelPoints-1) )
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? std::swap(mask, bestMask);
? ? ? ? ? ? ? ? ? ? model_i.copyTo(bestModel);
? ? ? ? ? ? ? ? ? ? maxGoodCount = goodCount;
? ? ? ? ? ? ? ? ? ? niters = RANSACUpdateNumIters( confidence, (double)(count - goodCount)/count, modelPoints, niters );
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? if( maxGoodCount > 0 )
? ? ? ? {
? ? ? ? ? ? if( bestMask.data != bestMask0.data )
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if( bestMask.size() == bestMask0.size() )
? ? ? ? ? ? ? ? ? ? bestMask.copyTo(bestMask0);
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? transpose(bestMask, bestMask0);
? ? ? ? ? ? }
? ? ? ? ? ? bestModel.copyTo(_model);
? ? ? ? ? ? result = true;
? ? ? ? }
? ? ? ? else
? ? ? ? ? ? _model.release();

? ? ? ? return result;
? ? }

? ? void setCallback(const Ptr<PointSetRegistrator::Callback>& _cb) { cb = _cb; }

? ? AlgorithmInfo* info() const;

? ? Ptr<PointSetRegistrator::Callback> cb;
? ? int modelPoints;
? ? bool checkPartialSubsets;
? ? double threshold;
? ? double confidence;
? ? int maxIters;
};? ? ? ?d)如何復(fù)用OPENCV中的實(shí)現(xiàn)于數(shù)據(jù)的統(tǒng)計(jì)研究? ? ? ?opencv中的封裝是專門用于特征點(diǎn)的，如果需要使用在其它地方還需要修改。但是我更關(guān)心的是RANSAC的算法應(yīng)該用在哪里？四、反思小結(jié)? ? ? ?即使是這樣一個原理來說比較清楚的算法，如果想從零開始進(jìn)行實(shí)現(xiàn)，還是很不容易的。所以積累算法資源、提高算法實(shí)現(xiàn)能力，可能都是很重要的事情。? ? ? ?和cross validation算法比較，和lmeds 最小平方中值估計(jì)法

來自為知筆記(Wiz)

轉(zhuǎn)載于:https://www.cnblogs.com/jsxyhelu/p/6873309.html

總結(jié)

以上是生活随笔為你收集整理的RANSAC算法在图像拼接上的应用的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。