特征點(diǎn)提取器ORBextractor詳解

各成員函數(shù)/變量

構(gòu)造函數(shù): ORBextractor()

FAST特征點(diǎn)和ORB描述子本身不具有尺度信息,ORBextractor通過構(gòu)建圖像金字塔來得到特征點(diǎn)尺度信息.將輸入圖片逐級縮放得到圖像金字塔,金字塔層級越高,圖片分辨率越低,ORB特征點(diǎn)越大.

構(gòu)造函數(shù)ORBextractor(int nfeatures, float scaleFactor, int nlevels, int iniThFAST, int minThFAST)的流程:

1.初始化圖像金字塔相關(guān)變量:

下面成員變量從配置文件TUM1.yaml中讀入:

?

根據(jù)上述變量的值計(jì)算出下述成員變量:

2.初始化用于計(jì)算描述子的pattern變量,pattern是用于計(jì)算描述子的256對坐標(biāo),其值寫死在源碼文件ORBextractor.cc里,在構(gòu)造函數(shù)里做類型轉(zhuǎn)換將其轉(zhuǎn)換為const cv::Point*變量.

static int bit_pattern_31_[256*4] ={
    8,-3, 9,5/*mean (0), correlation (0)*/,
    4,2, 7,-12/*mean (1.12461e-05), correlation (0.0437584)*/,
    -11,9, -8,2/*mean (3.37382e-05), correlation (0.0617409)*/,
    7,-12, 12,-13/*mean (5.62303e-05), correlation (0.0636977)*/,
    2,-13, 2,12/*mean (0.000134953), correlation (0.085099)*/,
    // 共256行...
}


const Point* pattern0 = (const Point*)bit_pattern_31_;
std::copy(pattern0, pattern0 + npoints, std::back_inserter(pattern));

3.計(jì)算一個半徑為16的圓的近似坐標(biāo)

后面計(jì)算的是特征點(diǎn)主方向上的描述子,計(jì)算過程中要將特征點(diǎn)周圍像素旋轉(zhuǎn)到主方向上,因此計(jì)算一個半徑為16的圓的近似坐標(biāo),用于后面計(jì)算描述子時進(jìn)行旋轉(zhuǎn)操作.

成員變量std::vector umax里存儲的實(shí)際上是逼近圓的第一象限內(nèi)1/4圓周上每個v坐標(biāo)對應(yīng)的u坐標(biāo).為保證嚴(yán)格對稱性,先計(jì)算下45°圓周上點(diǎn)的坐標(biāo),再根據(jù)對稱性補(bǔ)全上45°圓周上點(diǎn)的坐標(biāo).

int vmax = cvFloor(HALF_PATCH_SIZE * sqrt(2.f) / 2 + 1); // 45°射線與圓周交點(diǎn)的縱坐標(biāo)
int vmin = cvCeil(HALF_PATCH_SIZE * sqrt(2.f) / 2);// 45°射線與圓周交點(diǎn)的縱坐標(biāo)
// 先計(jì)算下半45度的umax
for (int v = 0; v <= vmax; ++v) {
umax[v] = cvRound(sqrt(15 * 15 - v * v));
}
// 根據(jù)對稱性補(bǔ)出上半45度的umax
for (int v = HALF_PATCH_SIZE, v0 = 0; v >= vmin; --v) {
    while (umax[v0] == umax[v0 + 1])
        ++v0;
    umax[v] = v0;
    ++v0;
}

構(gòu)建圖像金字塔: ComputePyramid()

根據(jù)上述變量的值計(jì)算出下述成員變量:

函數(shù)void ORBextractor::Mat image)逐層計(jì)算圖像金字塔,對于每層圖像進(jìn)行以下兩步:

1）先進(jìn)行圖片縮放,縮放到mvInvScaleFactor對應(yīng)尺寸.

2）在圖像外補(bǔ)一圈厚度為19的padding(提取FAST特征點(diǎn)需要特征點(diǎn)周圍半徑為3的圓域,計(jì)算ORB描述子需要特征點(diǎn)周圍半徑為16的圓域).

下圖表示圖像金字塔每層結(jié)構(gòu):

1）深灰色為縮放后的原始圖像.

2）包含綠色邊界在內(nèi)的矩形用于提取FAST特征點(diǎn).

3）包含淺灰色邊界在內(nèi)的整個矩形用于計(jì)算ORB描述子.

void ORBextractor::Mat image) {
    for (int level = 0; level < nlevels; ++level) {
        // 計(jì)算縮放+補(bǔ)padding后該層圖像的尺寸
        float scale = mvInvScaleFactor[level];
        Size sz(cvRound((float)image.cols*scale), cvRound((float)image.rows*scale));
        Size wholeSize(sz.width + EDGE_THRESHOLD * 2, sz.height + EDGE_THRESHOLD * 2);
        Mat temp(wholeSize, image.type());
        
// 縮放圖像并復(fù)制到對應(yīng)圖層并補(bǔ)邊
        mvImagePyramid[level] = temp(Rect(EDGE_THRESHOLD, EDGE_THRESHOLD, sz.width, sz.height));
        if( level != 0 ) {
            resize(mvImagePyramid[level-1], mvImagePyramid[level], sz, 0, 0, cv::INTER_LINEAR);
            copyMakeBorder(mvImagePyramid[level], temp, EDGE_THRESHOLD, EDGE_THRESHOLD, EDGE_THRESHOLD, EDGE_THRESHOLD, 
                           BORDER_REFLECT_101+BORDER_ISOLATED);            
        } else {
            copyMakeBorder(image, temp, EDGE_THRESHOLD, EDGE_THRESHOLD, EDGE_THRESHOLD, EDGE_THRESHOLD, 
                           BORDER_REFLECT_101);            
        }
    }
}

copyMakeBorder函數(shù)實(shí)現(xiàn)了復(fù)制和padding填充,其參數(shù)BORDER_REFLECT_101參數(shù)指定對padding進(jìn)行鏡像填充.

提取特征點(diǎn)并進(jìn)行篩選: ComputeKeyPointsOctTree()

提取特征點(diǎn)最重要的就是力求特征點(diǎn)均勻地分布在圖像的所有部分,為實(shí)現(xiàn)這一目標(biāo),編程實(shí)現(xiàn)上使用了兩個技巧:

1）分CELL搜索特征點(diǎn),若某CELL內(nèi)特征點(diǎn)響應(yīng)值普遍較小的話就降低分?jǐn)?shù)線再搜索一遍.

2）對得到的所有特征點(diǎn)進(jìn)行八叉樹篩選,若某區(qū)域內(nèi)特征點(diǎn)數(shù)目過于密集,則只取其中響應(yīng)值最大的那個.

CELL搜索的示意圖如下,每個CELL的大小約為3030,搜索到邊上,剩余尺寸不夠大的時候,最后一個CELL有多大就用多大的區(qū)域.

需要注意的是相鄰的CELL之間會有6像素的重疊區(qū)域,因?yàn)樘崛AST特征點(diǎn)需要計(jì)算特征點(diǎn)周圍半徑為3的圓周上的像素點(diǎn)信息,實(shí)際上產(chǎn)生特征點(diǎn)的區(qū)域比傳入的搜索區(qū)域小3像素.

void ORBextractor::ComputeKeyPointsOctTree(vector >& allKeypoints){
    for (int level = 0; level < nlevels; ++level)
        // 計(jì)算圖像邊界
        const int minBorderX = EDGE_THRESHOLD-3;
        const int minBorderY = minBorderX;
        const int maxBorderX = mvImagePyramid[level].cols-EDGE_THRESHOLD+3;
        const int maxBorderY = mvImagePyramid[level].rows-EDGE_THRESHOLD+3;
        const float width = (maxBorderX-minBorderX);
        const float height = (maxBorderY-minBorderY);
        const int nCols = width/W;// 每一列有多少cell
        const int nRows = height/W;// 每一行有多少cell
        const int wCell = ceil(width/nCols);// 每個cell的寬度
        const int hCell = ceil(height/nRows);// 每個cell的高度




        // 存儲需要進(jìn)行平均分配的特征點(diǎn)
        vector vToDistributeKeys;




    // step1. 遍歷每行和每列,依次分別用高低閾值搜索FAST特征點(diǎn)
        for(int i=0; i vKeysCell;




                // 先用高閾值搜索FAST特征點(diǎn)
                FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell, iniThFAST, true);
                // 高閾值搜索不到的話,就用低閾值搜索FAST特征點(diǎn)
                if(vKeysCell.empty()) {
                    FAST(mvImagePyramid[level].rowRange(iniY,maxY).colRange(iniX,maxX),vKeysCell, minThFAST, true);
                }
// 把 vKeysCell 中提取到的特征點(diǎn)全添加到 容器vToDistributeKeys 中
                for(KeyPoint point :vKeysCell) {
                    point.pt.x+=j*wCell;
                    point.pt.y+=i*hCell;
                    vToDistributeKeys.push_back(point);
                }
            }
        }




    // step2. 對提取到的特征點(diǎn)進(jìn)行八叉樹篩選,見 DistributeOctTree() 函數(shù)
        keypoints = DistributeOctTree(vToDistributeKeys, minBorderX, maxBorderX, minBorderY, maxBorderY, mnFeaturesPerLevel[level], level);
    }
// 計(jì)算每個特征點(diǎn)的方向
    for (int level = 0; level < nlevels; ++level)
        computeOrientation(mvImagePyramid[level], allKeypoints[level], umax);
}
}

八叉樹篩選特征點(diǎn): DistributeOctTree()

函數(shù)DistributeOctTree()進(jìn)行八叉樹篩選(非極大值抑制),不斷將存在特征點(diǎn)的圖像區(qū)域進(jìn)行4等分,直到分出了足夠多的分區(qū),每個分區(qū)內(nèi)只保留響應(yīng)值最大的特征點(diǎn). 其代碼實(shí)現(xiàn)比較瑣碎,程序里還定義了一個ExtractorNode類用于進(jìn)行八叉樹分配,知道原理就行,不看代碼.

計(jì)算特征點(diǎn)方向computeOrientation()

函數(shù)computeOrientation()計(jì)算每個特征點(diǎn)的方向: 使用特征點(diǎn)周圍半徑19大小的圓的重心方向作為特征點(diǎn)方向.

static void computeOrientation(const Mat& image, vector& keypoints, const vector& umax)
{
for (vector::iterator keypoint : keypoints) {
// 調(diào)用IC_Angle 函數(shù)計(jì)算這個特征點(diǎn)的方向
        keypoint->angle = IC_Angle(image, keypoint->pt, umax);
    }
}




static float IC_Angle(const Mat& image, Point2f pt,  const vector & u_max)
{
int m_01 = 0, m_10 = 0;// 重心方向
    const uchar* center = &image.at (cvRound(pt.y), cvRound(pt.x));
    for (int u = -HALF_PATCH_SIZE; u <= HALF_PATCH_SIZE; ++u)
    m_10 += u * center[u];
    int step = (int)image.step1();
for (int v = 1; v <= HALF_PATCH_SIZE; ++v) {
        int v_sum = 0;
  int d = u_max[v];
    for (int u = -d; u <= d; ++u) {
            int val_plus = center[u + v*step], val_minus = center[u - v*step];
            v_sum += (val_plus - val_minus);
            m_10 += u * (val_plus + val_minus);
        }
        m_01 += v * v_sum;
    }




    // 為了加快速度使用了fastAtan2()函數(shù)，輸出為[0,360)角度，精度為0.3°
    return fastAtan2((float)m_01, (float)m_10);
}

計(jì)算特征點(diǎn)描述子computeOrbDescriptor()

計(jì)算BRIEF描述子的核心步驟是在特征點(diǎn)周圍半徑為16的圓域內(nèi)選取256對點(diǎn)對,每個點(diǎn)對內(nèi)比較得到1位,共得到256位的描述子,為保計(jì)算的一致性,工程上使用特定設(shè)計(jì)的點(diǎn)對pattern,在程序里被硬編碼為成員變量了.

在computeOrientation()中我們求出了每個特征點(diǎn)的主方向,在計(jì)算描述子時,應(yīng)該將特征點(diǎn)周圍像素旋轉(zhuǎn)到主方向上來計(jì)算;為了編程方便,實(shí)踐上對pattern進(jìn)行旋轉(zhuǎn).

static void computeOrbDescriptor(const KeyPoint& kpt, const Mat& img, const Point* pattern, uchar* desc) {




    float angle = (float)kpt.angle*factorPI;
float a = (float)cos(angle), b = (float)sin(angle);




const uchar* center = &img.at(cvRound(kpt.pt.y), cvRound(kpt.pt.x));
const int step = (int)img.step;




    // 旋轉(zhuǎn)公式
// x'= xcos(θ) - ysin(θ)
    // y'= xsin(θ) + ycos(θ)
    #define GET_VALUE(idx) 
    center[cvRound(pattern[idx].x*b + pattern[idx].y*a)*step + cvRound(pattern[idx].x*a - pattern[idx].y*b)]        
    for (int i = 0; i < 32; ++i, pattern += 16) {
        int t0, t1, val;
        t0 = GET_VALUE(0); t1 = GET_VALUE(1);
        val = t0 < t1;// 描述子本字節(jié)的bit0
        t0 = GET_VALUE(2); t1 = GET_VALUE(3);
        val |= (t0 < t1) << 1;// 描述子本字節(jié)的bit1
        t0 = GET_VALUE(4); t1 = GET_VALUE(5);
        val |= (t0 < t1) << 2;// 描述子本字節(jié)的bit2
        t0 = GET_VALUE(6); t1 = GET_VALUE(7);
        val |= (t0 < t1) << 3;// 描述子本字節(jié)的bit3
        t0 = GET_VALUE(8); t1 = GET_VALUE(9);
        val |= (t0 < t1) << 4;// 描述子本字節(jié)的bit4
        t0 = GET_VALUE(10); t1 = GET_VALUE(11);
        val |= (t0 < t1) << 5;// 描述子本字節(jié)的bit5
        t0 = GET_VALUE(12); t1 = GET_VALUE(13);
        val |= (t0 < t1) << 6;// 描述子本字節(jié)的bit6
        t0 = GET_VALUE(14); t1 = GET_VALUE(15);
        val |= (t0 < t1) << 7;// 描述子本字節(jié)的bit7




        //保存當(dāng)前比較的出來的描述子的這個字節(jié)
        desc[i] = (uchar)val;
    }
}

ORBextractor類的用途

ORBextractor被用于Tracking線程對輸入圖像預(yù)處理的第一步. ORBextractor類提取特征點(diǎn)的主函數(shù)void operator()() 這個函數(shù)重載了()運(yùn)算符,使得其他類可以將ORBextractor類型變量當(dāng)作函數(shù)來使用. 該函數(shù)是ORBextractor的主函數(shù),內(nèi)部依次調(diào)用了上面提到的各過程.

void ORBextractor::operator()(InputArray _image, InputArray _mask, vector& _keypoints, OutputArray _descriptors) { 
// step1. 檢查圖像有效性
    if(_image.empty())
        return;
Mat image = _image.getMat();
assert(image.type() == CV_8UC1 );




    // step2. 構(gòu)建圖像金字塔
    ComputePyramid(image);




    // step3. 計(jì)算特征點(diǎn)并進(jìn)行八叉樹篩選
    vector > allKeypoints; 
    ComputeKeyPointsOctTree(allKeypoints);




    // step4. 遍歷每一層圖像,計(jì)算描述子
    int offset = 0;
for (int level = 0; level < nlevels; ++level) {
        Mat workingMat = mvImagePyramid[level].clone();
        // 計(jì)算描述子之前先進(jìn)行一次高斯模糊
        GaussianBlur(workingMat, workingMat, Size(7, 7), 2, 2, BORDER_REFLECT_101);
        computeDescriptors(workingMat, allKeypoints[level], descriptors.rowRange(offset, offset + allKeypoints[level].size());, pattern);
        offset += allKeypoints[level].size();
    }
}

這個重載()運(yùn)算符的用法被用在Frame類的ExtractORB()函數(shù)中了,這也是ORBextractor類在整個項(xiàng)目中唯一被調(diào)用的地方.

// 函數(shù)中`mpORBextractorLeft`和`mpORBextractorRight`都是`ORBextractor`對象
void Frame::ExtractORB(int flag, const cv::Mat &im) {
    if(flag==0)
        (*mpORBextractorLeft)(im, cv::Mat(), mvKeys, mDescriptors);
    else
        (*mpORBextractorRight)(im,cv::Mat(),mvKeysRight,mDescriptorsRight);
}

ORBextractor類與其它類間的關(guān)系

Frame類中與ORBextractor有關(guān)的成員變量和成員函數(shù)

// Frame類的兩個ORBextractor是在調(diào)用構(gòu)造函數(shù)時傳入的,構(gòu)造函數(shù)中調(diào)用ExtractORB()提取特征點(diǎn)
Frame::Frame(ORBextractor *extractorLeft, ORBextractor *extractorRight) 
    : mpORBextractorLeft(extractorLeft), mpORBextractorRight(extractorRight) {




        // ...




        // 提取ORB特征點(diǎn)
        thread threadLeft(&Frame::ExtractORB, this, 0, imLeft);
        thread threadRight(&Frame::ExtractORB, this, 1, imRight);
        threadLeft.join();
        threadRight.join();




        // ...       
    }




// 提取特征點(diǎn)
void Frame::ExtractORB(int flag, const cv::Mat &im) {
    if (flag == 0)
        (*mpORBextractorLeft)(im, cv::Mat(), mvKeys, mDescriptors);
    else
        (*mpORBextractorRight)(im, cv::Mat(), mvKeysRight, mDescriptorsRight);
}

Frame類的兩個ORBextractor指針指向的變量是Tracking類的構(gòu)造函數(shù)中創(chuàng)建的

// Tracking構(gòu)造函數(shù)
Tracking::Tracking() {
    // ...
    
    // 創(chuàng)建兩個ORB特征點(diǎn)提取器
    mpORBextractorLeft = new ORBextractor(nFeatures, fScaleFactor, nLevels, fIniThFAST, fMinThFAST);
    if (sensor == System::STEREO)
        mpORBextractorRight = new ORBextractor(nFeatures, fScaleFactor, nLevels, fIniThFAST, fMinThFAST);




  // ...
}




// Tracking線程每收到一幀輸入圖片,就創(chuàng)建一個Frame對象,創(chuàng)建Frame對象時將提取器mpORBextractorLeft和mpORBextractorRight給構(gòu)造函數(shù)
cv::Mat Tracking::GrabImageStereo(const cv::Mat &imRectLeft, const cv::Mat &imRectRight, const double &timestamp) {
    // ...
    
    // 創(chuàng)建Frame對象
    mCurrentFrame = Frame(mImGray, imGrayRight, timestamp, mpORBextractorLeft, mpORBextractorRight);




    // ...
}

由上述代碼分析可知,每次完成ORB特征點(diǎn)提取之后,圖像金字塔信息就作廢了,下一幀圖像到來時調(diào)用ComputePyramid()函數(shù)會覆蓋掉本幀圖像的圖像金字塔信息;但從金字塔中提取的圖像特征點(diǎn)的信息會被保存在Frame對象中.所以O(shè)RB-SLAM2是稀疏重建,對每幀圖像只保留最多nfeatures個特征點(diǎn)(及其對應(yīng)的地圖點(diǎn)).

審核編輯：劉清