一、ORB算法原理

	全名Oriented FAST and Rotated BRIEF算法，是指它基于FAST算法提取特征點，并基于BRIEF算法構建特征點的描述子，在他們原有的基礎上進行修正，實現(xiàn)特征點的尺度不變性與旋轉(zhuǎn)不變性，即經(jīng)過了縮放與旋轉(zhuǎn)后的特征點仍能產(chǎn)生與原來相近的描述符。

算法步驟：

1.特征點提取

FAST進行特征點提取是根據(jù)當前點領域內(nèi)的點的差值作為特征點的篩選標準

2.特征點編碼

	BRIEF是一種對已經(jīng)檢測到的特征點進行描述的算法，該算法生成一種二進制描述子來描述已知的特征點。這些描述子可以用來進行特征點匹配等操作。BRIEF摒棄了利用區(qū)域直方圖描述特征點的傳統(tǒng)方法，采用二進制、位異或運算處理，大大的加快了特征點描述符建立的速度，同時也極大的降低了特征點匹配的時間，是一種非常快速的特征點描述子算法。

BRIEF的目標是得到一個二進制串，該串描述了特征點的特性。描述子生成的方式：
( 1 ) 為了減少噪聲干擾，首先對圖像進行高斯濾波（方差為 2 ，高斯窗口為 9 × 9 ）； ( 2 ) 然后以特征點為中心，取 S ? S 大小的鄰域窗口，在窗口內(nèi)以一定方式選取一對點 p , q ，比較兩個像素點的大?。? a ) . 如果 I p > I q ，則當前位二進制值為 1 ； b ) . 否則為 0 ； c ) . 重復這一步驟，產(chǎn)生指定長度的特征描述符；選取點的采樣方式可以為： ? ? p , q 都符合 [ ? S 2 , S 2 ] 的均勻采樣； ? ? p , q 都符合各向同性的高斯分布 [ 0 , 1 25 S 2 ] 采樣； ? ? p 符合高斯分布 [ 0 , 1 25 S 2 ] 采樣， q 符合 [ 0 , 1 100 S 2 ] 采樣，采樣方式是首先在原點處為 p 采樣，然后以 p 為中心為 q 采樣； ? ? p , q 在空間量化極坐標下的離散位置處進行隨機采樣； ? ? p = ( 0 , 0 ) T , q 在空間量化極坐標下的離散位置處進行隨機采樣； \begin{aligned} &(1)為了減少噪聲干擾，首先對圖像進行高斯濾波（方差為2，高斯窗口為9 × 9）；\\ &(2)然后以特征點為中心，取S * S大小的鄰域窗口，在窗口內(nèi)以一定方式選取一對點 p,q，比較兩個像素點的大小：\\ &\quad a).如果 I_p > I_q，則當前位二進制值為1；\\ &\quad b). 否則為0；\\ &\quad c). 重復這一步驟，產(chǎn)生指定長度的特征描述符；選取點的采樣方式可以為：\\ &\qquad \qquad * \ p,q都符合[-\frac{S}{2},\frac{S}{2}]的均勻采樣；\\ &\qquad \qquad * \ p,q都符合各向同性的高斯分布[0, \frac{1}{25}S^2]采樣；\\ &\qquad \qquad * \ p符合高斯分布[0, \frac{1}{25}S^2]采樣，q符合[0, \frac{1}{100}S^2]采樣，采樣方式是首先在原點處為p采樣，然后以p為中心為q采樣；\\ &\qquad \qquad * \ p,q在空間量化極坐標下的離散位置處進行隨機采樣；\\ &\qquad \qquad * \ p=(0,0)^T,q在空間量化極坐標下的離散位置處進行隨機采樣； \end{aligned} ?(1)為了減少噪聲干擾，首先對圖像進行高斯濾波（方差為2，高斯窗口為9×9）；(2)然后以特征點為中心，取S?S大小的鄰域窗口，在窗口內(nèi)以一定方式選取一對點p,q，比較兩個像素點的大?。?/span>a).如果Ip?>Iq?，則當前位二進制值為1；b).否則為0；c).重復這一步驟，產(chǎn)生指定長度的特征描述符；選取點的采樣方式可以為：??p,q都符合[?2S?,2S?]的均勻采樣；??p,q都符合各向同性的高斯分布[0,251?S2]采樣；??p符合高斯分布[0,251?S2]采樣，q符合[0,1001?S2]采樣，采樣方式是首先在原點處為p采樣，然后以p為中心為q采樣；??p,q在空間量化極坐標下的離散位置處進行隨機采樣；??p=(0,0)T,q在空間量化極坐標下的離散位置處進行隨機采樣；?

以采樣（3）為例子：綠色點為原點，藍色點為采樣p，黃色點為采樣q

?
BRIEF存在不具備旋轉(zhuǎn)不變性，不具備尺度不變性。

改進后的BRIEF：rBRIEF

（1）縮放不變性
????為使特征滿足縮放不變性，構建圖像金字塔。圖像金字塔是單個圖像的多尺度表示法，由一系列原始圖像的不同分辨率版本組成（比如每個圖像以1/2比例向下采樣）。

????ORB 創(chuàng)建好圖像金字塔后，會使用 FAST 算法從每個級別不同大小的圖像中快速找到關鍵點。因為金字塔的每個級別由原始圖像的更小版本組成，因此原始圖像中的任何對象在金字塔的每個級別也會降低大小。

（2）旋轉(zhuǎn)不變性
????為滿足特征的旋轉(zhuǎn)不變性，ORB 為每個關鍵點分配一個方向，該方向取決于該關鍵點周圍的灰度是如何變化的。ORB 首先選擇金字塔Level 0 中的圖像，計算該圖像關鍵點的方向。首先計算以關鍵點為中心的指定大小方框中的強度形心（灰度強度的形心）。強度形心可以看做給定區(qū)域中的平均像素灰度的位置。計算強度形心后，通過畫一條從關鍵點到強度形心的向量，獲得該關鍵點的方向。
????為金字塔級別 0 的圖像中的每個關鍵點分配方向后，ORB 現(xiàn)在為所有其他金字塔級別的圖像重復相同流程。

3.opencv實現(xiàn)

// nfeatures		期望檢測到的特征點數(shù)
// scaleFactor		多尺度金字塔的尺度
// nlevels			金字塔層數(shù)
// edgeThreshold	邊界閾值，靠近邊緣edgeThreshold以內(nèi)的像素是不檢測特征點的
// firstLevel		金字塔層的起始層
// wat_k			產(chǎn)生rBRIEF描述子點對的個數(shù)
// scoreType		角點響應函數(shù)，默認使用HARRIS對角點特征進行排序
// patchSize		鄰域大小
// fastThreshold
Ptr<ORB> ORB::create(int nfeatures, float scaleFactor, int nlevels, int edgeThreshold, int firstLevel, int wta_k, int scoreType, int patchSize, int fastThreshold){
    CV_Assert(firstLevel >= 0);
    return makePtr<ORB_Impl>(nfeatures, scaleFactor, nlevels, edgeThreshold, firstLevel, wta_k, scoreType, patchSize, fastThreshold);
}

// _image			計算特征和描述子的輸入圖像
// _mask			掩模
// keypoints		輸出關鍵點的集合
// _descriptors		描述子
// useProvidedKeypoints 使用提供的關鍵點

void ORB_Impl::detectAndCompute( InputArray _image, InputArray _mask, std::vector<KeyPoint>& keypoints,
                                 OutputArray _descriptors, bool useProvidedKeypoints ) {
    CV_Assert(patchSize >= 2);
    bool do_keypoints = !useProvidedKeypoints;
    bool do_descriptors = _descriptors.needed();
    if( (!do_keypoints && !do_descriptors) || _image.empty() )
        return;

    //ROI handling
    const int HARRIS_BLOCK_SIZE = 9;
    int halfPatchSize = patchSize / 2;
    // sqrt(2.0) is for handling patch rotation
    int descPatchSize = cvCeil(halfPatchSize*sqrt(2.0));
    int border = std::max(edgeThreshold, std::max(descPatchSize, HARRIS_BLOCK_SIZE/2))+1;

    Mat image = _image.getMat(), mask = _mask.getMat();
    if( image.type() != CV_8UC1 )
        cvtColor(_image, image, COLOR_BGR2GRAY);			//ORB采用點鄰域半徑內(nèi)的像素和當前像素的灰度差來表征特征點，顏色信息對于特征描述意義不大

    int i, level, nLevels = this->nlevels, nkeypoints = (int)keypoints.size();
    bool sortedByLevel = true;

    std::vector<Rect> layerInfo(nLevels);			//當前層圖像的rect相對于firstLevel層的位置，如果當前層的圖像比firstLevel層大則采用當前圖源尺寸
    std::vector<int> layerOfs(nLevels);				//當前層的數(shù)據(jù)index，用于OpenCL優(yōu)化
    std::vector<float> layerScale(nLevels);			//保存從第0層到第nLevels層縮放的尺度
    Mat imagePyramid, maskPyramid;
    float level0_inv_scale = 1.0f / getScale(0, firstLevel, scaleFactor);	//第一層的縮放尺度
    size_t level0_width = (size_t)cvRound(image.cols * level0_inv_scale);	//第一層圖像的寬度
    size_t level0_height = (size_t)cvRound(image.rows * level0_inv_scale);	//第一層圖像的高度
    Size bufSize((int)alignSize(level0_width + border*2, 16), 0);  			//第一層圖像對齊后的rowbyteperrow,+2border是為方便做HARRIS做的padding

    int level_dy = (int)level0_height + border*2;
    Point level_ofs(0, 0);
	//這里只計算每一層的尺寸并不進行實際的金字塔層的構造工作，下面的一系列計算都是為了防止越界，以及金字塔特征層是在一張Mat上而不是一個vector<Mat>
    for( level = 0; level < nLevels; level++ )
    {
		//getScale->(float)std::pow(scaleFactor, (double)(level - firstLevel))金字塔層第0層就是原圖，層數(shù)越高，圖像的尺度多樣性越豐富，圖像越小
        float scale = getScale(level, firstLevel, scaleFactor);
        layerScale[level] = scale;
        float inv_scale = 1.0f / scale;				//從這里能夠看出第一層圖像是最大的然后逐層減小
        Size sz(cvRound(image.cols * inv_scale), cvRound(image.rows * inv_scale));	//當前層圖像的尺寸
        Size wholeSize(sz.width + border*2, sz.height + border*2);		//padding邊界尺寸之后的實際尺寸
        if( level_ofs.x + wholeSize.width > bufSize.width )
        {//如果當前行存在足夠的空間則優(yōu)先放在當前行，由于圖像是從大到小生成的y方向始終是足夠的
            level_ofs = Point(0, level_ofs.y + level_dy);
            level_dy = wholeSize.height;
        }

        Rect linfo(level_ofs.x + border, level_ofs.y + border, sz.width, sz.height);
        layerInfo[level] = linfo;
        layerOfs[level] = linfo.y*bufSize.width + linfo.x;
        level_ofs.x += wholeSize.width;
    }
	
    bufSize.height = level_ofs.y + level_dy;
    imagePyramid.create(bufSize, CV_8U);
    if( !mask.empty() )
        maskPyramid.create(bufSize, CV_8U);

    Mat prevImg = image, prevMask = mask;
    // Pre-compute the scale pyramids 構造金字塔層，下
    for (level = 0; level < nLevels; ++level)
    {//從上面計算的尺寸中取出相應的尺寸縮放圖像生成對應的金字塔
        Rect linfo = layerInfo[level];
        Size sz(linfo.width, linfo.height);
        Size wholeSize(sz.width + border*2, sz.height + border*2);
        Rect wholeLinfo = Rect(linfo.x - border, linfo.y - border, wholeSize.width, wholeSize.height);
        Mat extImg = imagePyramid(wholeLinfo), extMask;
        Mat currImg = extImg(Rect(border, border, sz.width, sz.height)), currMask;

        if( !mask.empty() )
        {
            extMask = maskPyramid(wholeLinfo);
            currMask = extMask(Rect(border, border, sz.width, sz.height));
        }

        // Compute the resized image 這里生成的圖像邊界padding的并不是一個固定的像素值而是原圖像的鏡像，這樣能夠最大程度的保留圖像的信息避免額外引入的噪聲的干擾
        if( level != firstLevel )
        {
            resize(prevImg, currImg, sz, 0, 0, INTER_LINEAR_EXACT);
            if( !mask.empty() )
            {
                resize(prevMask, currMask, sz, 0, 0, INTER_LINEAR_EXACT);
                if( level > firstLevel )
                    threshold(currMask, currMask, 254, 0, THRESH_TOZERO);
            }

            copyMakeBorder(currImg, extImg, border, border, border, border,
                           BORDER_REFLECT_101+BORDER_ISOLATED);
            if (!mask.empty())
                copyMakeBorder(currMask, extMask, border, border, border, border,
                               BORDER_CONSTANT+BORDER_ISOLATED);
        }
        else
        {
            copyMakeBorder(image, extImg, border, border, border, border,
                           BORDER_REFLECT_101);
            if( !mask.empty() )
                copyMakeBorder(mask, extMask, border, border, border, border,
                               BORDER_CONSTANT+BORDER_ISOLATED);
        }
        if (level > firstLevel)
        {
            prevImg = currImg;
            prevMask = currMask;
        }
    }

	// Get keypoints, those will be far enough from the border that no check will be required for the descriptor
	computeKeyPoints(imagePyramid, uimagePyramid, maskPyramid,
					 layerInfo, ulayerInfo, layerScale, keypoints,
					 nfeatures, scaleFactor, edgeThreshold, patchSize, scoreType, useOCL, fastThreshold);

    if( do_descriptors )
    {
        int dsize = descriptorSize();	//固定dsize=32byte就是特征的256位的二進制位描述
        nkeypoints = (int)keypoints.size();
        if( nkeypoints == 0 )
        {
            _descriptors.release();
            return;
        }

        _descriptors.create(nkeypoints, dsize, CV_8U);	//這里創(chuàng)建的是一個nxndesc大小的矩陣表示n個特征點的特征描述
        std::vector<Point> pattern;

        const int npoints = 512;						//256對點
        Point patternbuf[npoints];
        const Point* pattern0 = (const Point*)bit_pattern_31_;	//bit_pattern_32_是通過PASCAL 2006數(shù)據(jù)集訓練好的pattern，這部分數(shù)據(jù)是硬編碼。是patchSize為31時，在其鄰域內(nèi)選取的256個點對
        if( patchSize != 31 )
        {
            pattern0 = patternbuf;
            makeRandomPattern(patchSize, patternbuf, npoints);		//如果patchSize不為31的話會隨機生成篩選的點對，而且隨機數(shù)的種子是固定的保證篩選的位置都是固定的，不然同一張圖不同時刻輸入得到特征點不一樣
        }

        CV_Assert( wta_k == 2 || wta_k == 3 || wta_k == 4 );
        if( wta_k == 2 )
            std::copy(pattern0, pattern0 + npoints, std::back_inserter(pattern));
        else
        {
            int ntuples = descriptorSize()*4;
            initializeOrbPattern(pattern0, pattern, ntuples, wta_k, npoints);
        }

        for( level = 0; level < nLevels; level++ )
        {
            // preprocess the resized image
            Mat workingMat = imagePyramid(layerInfo[level]);
			//對每一層的圖像進行高斯模糊
            //boxFilter(working_mat, working_mat, working_mat.depth(), Size(5,5), Point(-1,-1), true, BORDER_REFLECT_101);
            GaussianBlur(workingMat, workingMat, Size(7, 7), 2, 2, BORDER_REFLECT_101);
        }
		
        {
            Mat descriptors = _descriptors.getMat();
            computeOrbDescriptors(imagePyramid, layerInfo, layerScale,
                                  keypoints, descriptors, pattern, dsize, wta_k);
        }
    }
}

static void computeKeyPoints(const Mat& imagePyramid, const UMat& uimagePyramid, const Mat& maskPyramid, const std::vector<Rect>& layerInfo, const UMat& ulayerInfo, const std::vector<float>& layerScale, std::vector<KeyPoint>& allKeypoints, int nfeatures, double scaleFactor, int edgeThreshold, int patchSize, int scoreType, bool useOCL, int fastThreshold  ) {
    int i, nkeypoints, level, nlevels = (int)layerInfo.size();
    std::vector<int> nfeaturesPerLevel(nlevels);

    // fill the extractors and descriptors for the corresponding scales
    float factor = (float)(1.0 / scaleFactor);
    float ndesiredFeaturesPerScale = nfeatures*(1 - factor)/(1 - (float)std::pow((double)factor, (double)nlevels));

    int sumFeatures = 0;
	//從這里能夠看出檢測出的n個特征點是按比例分配在多層金字塔上的，其總數(shù)為nfeatures
    for( level = 0; level < nlevels-1; level++ ) {
        nfeaturesPerLevel[level] = cvRound(ndesiredFeaturesPerScale);
        sumFeatures += nfeaturesPerLevel[level];
        ndesiredFeaturesPerScale *= factor;		//第一層的特征點數(shù)最多，越往上越少
    }
	
    nfeaturesPerLevel[nlevels-1] = std::max(nfeatures - sumFeatures, 0);
    // Make sure we forget about what is too close to the boundary
    //edge_threshold_ = std::max(edge_threshold_, patch_size_/2 + kKernelWidth / 2 + 2);

    // pre-compute the end of a row in a circular patch
    int halfPatchSize = patchSize / 2;
    std::vector<int> umax(halfPatchSize + 2);

    int v, v0, vmax = cvFloor(halfPatchSize * std::sqrt(2.f) / 2 + 1);
    int vmin = cvCeil(halfPatchSize * std::sqrt(2.f) / 2);
    for (v = 0; v <= vmax; ++v)
        umax[v] = cvRound(std::sqrt((double)halfPatchSize * halfPatchSize - v * v));

    // Make sure we are symmetric
    for (v = halfPatchSize, v0 = 0; v >= vmin; --v){
        while (umax[v0] == umax[v0 + 1])
            ++v0;
        umax[v] = v0;
        ++v0;
    }

    allKeypoints.clear();
    std::vector<KeyPoint> keypoints;
    std::vector<int> counters(nlevels);
    keypoints.reserve(nfeaturesPerLevel[0]*2);

    for( level = 0; level < nlevels; level++ )
    {
        int featuresNum = nfeaturesPerLevel[level];
        Mat img = imagePyramid(layerInfo[level]);
        Mat mask = maskPyramid.empty() ? Mat() : maskPyramid(layerInfo[level]);

        // Detect FAST features, 20 is a good threshold
        {使用fast進行角點檢測
			Ptr<FastFeatureDetector> fd = FastFeatureDetector::create(fastThreshold, true);
			fd->detect(img, keypoints, mask);
        }

        // 移除邊界附近的角點特征
        KeyPointsFilter::runByImageBorder(keypoints, img.size(), edgeThreshold);
        // Keep more points than necessary as FAST does not give amazing corners
        KeyPointsFilter::retainBest(keypoints, scoreType == ORB_Impl::HARRIS_SCORE ? 2 * featuresNum : featuresNum);

        nkeypoints = (int)keypoints.size();
        counters[level] = nkeypoints;

        float sf = layerScale[level];
        for( i = 0; i < nkeypoints; i++ ){
            keypoints[i].octave = level;
            keypoints[i].size = patchSize*sf;
        }

        std::copy(keypoints.begin(), keypoints.end(), std::back_inserter(allKeypoints));
    }

    std::vector<Vec3i> ukeypoints_buf;
    nkeypoints = (int)allKeypoints.size();
    if(nkeypoints == 0){
        return;
    }
	
    Mat responses;
    // 使用Harris篩選FAST檢測到的特征點
    if( scoreType == ORB_Impl::HARRIS_SCORE ) {
        HarrisResponses(imagePyramid, layerInfo, allKeypoints, 7, HARRIS_K);

        std::vector<KeyPoint> newAllKeypoints;
        newAllKeypoints.reserve(nfeaturesPerLevel[0]*nlevels);
        int offset = 0;
        for( level = 0; level < nlevels; level++ ) {
            int featuresNum = nfeaturesPerLevel[level];
            nkeypoints = counters[level];
            keypoints.resize(nkeypoints);
            std::copy(allKeypoints.begin() + offset,
                      allKeypoints.begin() + offset + nkeypoints,
                      keypoints.begin());
            offset += nkeypoints;

            //cull to the final desired level, using the new Harris scores.
            KeyPointsFilter::retainBest(keypoints, featuresNum);

            std::copy(keypoints.begin(), keypoints.end(), std::back_inserter(newAllKeypoints));
        }
        std::swap(allKeypoints, newAllKeypoints);
    }

    nkeypoints = (int)allKeypoints.size();
    {	//通過質(zhì)心計算當前特征點的角度fastAtan2((float)m_01, (float)m_10);
        ICAngles(imagePyramid, layerInfo, allKeypoints, umax, halfPatchSize);
    }

    for( i = 0; i < nkeypoints; i++ ) {			//將每一層經(jīng)過縮放過的角點還原到原圖上
        float scale = layerScale[allKeypoints[i].octave];
        allKeypoints[i].pt *= scale;
    }
}

計算特征點的描述子：

static void
computeOrbDescriptors( const Mat& imagePyramid, const std::vector<Rect>& layerInfo,
                       const std::vector<float>& layerScale, std::vector<KeyPoint>& keypoints,
                       Mat& descriptors, const std::vector<Point>& _pattern, int dsize, int wta_k )
{
    int step = (int)imagePyramid.step;
    int j, i, nkeypoints = (int)keypoints.size();
    for( j = 0; j < nkeypoints; j++ ){
        const KeyPoint& kpt = keypoints[j];
        const Rect& layer = layerInfo[kpt.octave];
        float scale = 1.f/layerScale[kpt.octave];
        float angle = kpt.angle;
        angle *= (float)(CV_PI/180.f);
        float a = (float)cos(angle), b = (float)sin(angle);
        const uchar* center = &imagePyramid.at<uchar>(cvRound(kpt.pt.y*scale) + layer.y, cvRound(kpt.pt.x*scale) + layer.x);
        float x, y;
        int ix, iy;
        const Point* pattern = &_pattern[0];
        uchar* desc = descriptors.ptr<uchar>(j);

    #if 1//這個宏就是將點根據(jù)pattern旋轉(zhuǎn)對應的角度得到新的xy
        #define GET_VALUE(idx) \
               (x = pattern[idx].x*a - pattern[idx].y*b, \
                y = pattern[idx].x*b + pattern[idx].y*a, \
                ix = cvRound(x), \
                iy = cvRound(y), \
                *(center + iy*step + ix) )
    #else
	//省略
    #endif

        if( wta_k == 2 ){
            for (i = 0; i < dsize; ++i, pattern += 16){
                int t0, t1, val;
                t0 = GET_VALUE(0); t1 = GET_VALUE(1);
                val = t0 < t1;	//這里比較明顯就是比較一個點對的大小關系來作為當前二進制位的具體值
                t0 = GET_VALUE(2); t1 = GET_VALUE(3);
                val |= (t0 < t1) << 1;
                t0 = GET_VALUE(4); t1 = GET_VALUE(5);
                val |= (t0 < t1) << 2;
                t0 = GET_VALUE(6); t1 = GET_VALUE(7);
                val |= (t0 < t1) << 3;
                t0 = GET_VALUE(8); t1 = GET_VALUE(9);
                val |= (t0 < t1) << 4;
                t0 = GET_VALUE(10); t1 = GET_VALUE(11);
                val |= (t0 < t1) << 5;
                t0 = GET_VALUE(12); t1 = GET_VALUE(13);
                val |= (t0 < t1) << 6;
                t0 = GET_VALUE(14); t1 = GET_VALUE(15);
                val |= (t0 < t1) << 7;

                desc[i] = (uchar)val;
            }
        }
        else if( wta_k == 3 ){//下面wta_k=3和4同理
            for (i = 0; i < dsize; ++i, pattern += 12){
                int t0, t1, t2, val;
                t0 = GET_VALUE(0); t1 = GET_VALUE(1); t2 = GET_VALUE(2);
                val = t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0);

                t0 = GET_VALUE(3); t1 = GET_VALUE(4); t2 = GET_VALUE(5);
                val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 2;

                t0 = GET_VALUE(6); t1 = GET_VALUE(7); t2 = GET_VALUE(8);
                val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 4;

                t0 = GET_VALUE(9); t1 = GET_VALUE(10); t2 = GET_VALUE(11);
                val |= (t2 > t1 ? (t2 > t0 ? 2 : 0) : (t1 > t0)) << 6;

                desc[i] = (uchar)val;
            }
        }
        else if( wta_k == 4 ){
            for (i = 0; i < dsize; ++i, pattern += 16){
                int t0, t1, t2, t3, u, v, k, val;
                t0 = GET_VALUE(0); t1 = GET_VALUE(1);
                t2 = GET_VALUE(2); t3 = GET_VALUE(3);
                u = 0, v = 2;
                if( t1 > t0 ) t0 = t1, u = 1;
                if( t3 > t2 ) t2 = t3, v = 3;
                k = t0 > t2 ? u : v;
                val = k;

                t0 = GET_VALUE(4); t1 = GET_VALUE(5);
                t2 = GET_VALUE(6); t3 = GET_VALUE(7);
                u = 0, v = 2;
                if( t1 > t0 ) t0 = t1, u = 1;
                if( t3 > t2 ) t2 = t3, v = 3;
                k = t0 > t2 ? u : v;
                val |= k << 2;

                t0 = GET_VALUE(8); t1 = GET_VALUE(9);
                t2 = GET_VALUE(10); t3 = GET_VALUE(11);
                u = 0, v = 2;
                if( t1 > t0 ) t0 = t1, u = 1;
                if( t3 > t2 ) t2 = t3, v = 3;
                k = t0 > t2 ? u : v;
                val |= k << 4;

                t0 = GET_VALUE(12); t1 = GET_VALUE(13);
                t2 = GET_VALUE(14); t3 = GET_VALUE(15);
                u = 0, v = 2;
                if( t1 > t0 ) t0 = t1, u = 1;
                if( t3 > t2 ) t2 = t3, v = 3;
                k = t0 > t2 ? u : v;
                val |= k << 6;

                desc[i] = (uchar)val;
            }
        }
        else
            CV_Error( Error::StsBadSize, "Wrong wta_k. It can be only 2, 3 or 4." );
        #undef GET_VALUE
    }
}

4.算法優(yōu)缺點

優(yōu)點：計算速度很快，比SIFT、SURF快

缺點：對噪聲敏感，對光照變化敏感

二、SIFT算法原理

	SIFT，全稱是Scale-Invariant Feature Transform，是與縮放無關的特征檢測，也就是具有尺度不變性。SIFT算法可以說是傳統(tǒng)CV領域中達到巔峰的一個算法，這個算法強大到即使對圖片進行放縮、變形、模糊、明暗變化、光照變化、添加噪聲，甚至是使用不同的相機拍攝不同角度的照片的情況下，SIFT都能檢測到穩(wěn)定的特征點，并建立對應關系。

1.特征點提取

• 高斯函數(shù)尺度處理
  ? 所謂尺度可以理解為圖像模糊程度，使用不同的sigma值（$\sigma$?）的高斯核對圖像進行卷積，達到對圖像的尺度處理。
  ? $G(x,y,\sigma )$是高斯核函數(shù)，$L(x,y,\sigma )$是對應$\sigma$值尺度處理下的尺度圖像，$I(x,y)$?為原圖像。以下公式可求出尺度圖像：
  ? $$G(x,y,\sigma )=(\frac{1}{2\pi {\sigma }^2}{)}^{e^{\frac{?(x^2+y^2)}{2{\sigma }^2}}}$$ $$L(x,y,\sigma )=G(x,y,\sigma )?I(x,y)$$
  ? 所求的尺度圖中，$\sigma$ 越大圖像越模糊

• 圖像金字塔
  ? 相鄰不同層級的 $\sigma$? 值之間的高斯圖像做差分（圖像大小相同，模糊程度不同），此過程達到保留原圖像重要信息的目的
  

• 構造DoG空間
  ? 然后進行圖像進行縮放，每一個縮放的高斯模糊金字塔差分結果稱為DoG

• 極值檢測
  關鍵點由DoG空間的極值點組成，極值點從正數(shù)第二層到倒數(shù)第二層中尋找，某個點跟上一層、本層、下一層周圍的26個點進行比較，符合極大值或極小值，此點便為極值點。
  
• 對離散空間進行插值，找到精確特征點
  ? 在離散空間中尋找到的極值點并不一定是真正的極值點。我們用離散值插值的方式，將離散空間轉(zhuǎn)換為連續(xù)空間，得到更加準確的極值點。同時去除低對比度的關鍵點和不穩(wěn)定的邊緣響應點。
  

2.特征點描述

• 關鍵點梯度求解
• 利用關鍵點領域所有點的梯度方向，當作極值點方向

• 對關鍵點周圍像素進行方向統(tǒng)計、高斯加權
  取特征點周圍8*8的像素進行梯度方向統(tǒng)計和高斯加權（藍色圓圈代表高斯加權范圍）。每4 * 4窗口生成8個方向，這樣就生成了2 * 2 * 8的向量作為特征點的數(shù)學描述。
  SIFT算法采用4 * 4 * 8共128維向量作為特征點的描述子。最后通過描述子的歐式距離進行特征點匹配。

3.算法優(yōu)缺點

優(yōu)點：特征穩(wěn)定，對旋轉(zhuǎn)、尺度變換、亮度保持不變性，對視角變換、噪聲也有一定程度的穩(wěn)定性；

缺點：實時性不高，對于邊緣光滑目標的特征點提取能力較弱

三、SURF算法原理

	SURF全稱 Speeded Up Robust Features（加速穩(wěn)健特征），是對SIFT算法的一種改進。

1.特征點提取

• 使用方型濾波器取代SIFT算法中的高斯濾波器，借此提高運算

2.特征點描述

• 使用哈爾小波轉(zhuǎn)換的概念，利用積分圖簡化描述子的計算

3.算法優(yōu)缺點

優(yōu)點：相較SIFT算法快幾倍，比SIFT更加穩(wěn)健文章來源地址http://www.zghlxwxcb.cn/news/detail-777584.html

到了這里，關于opencv特征匹配算法原理的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！