ORB 算法學(xué)習(xí)筆記

本博客內(nèi)容來源于網(wǎng)絡(luò)以及其他書籍，結(jié)合自己學(xué)習(xí)的心得進(jìn)行重編輯，因?yàn)榭戳撕芏辔恼虏槐阋灰粯?biāo)注引用，如圖片文字等侵權(quán)，請告知?jiǎng)h除。

傳統(tǒng)2D計(jì)算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門
傳統(tǒng)3D計(jì)算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門

前言

休息了一天，雨天去了一次頤和園，不幸，我感冒了。所以，如果本文有任何常識(shí)性問題，請不要懷疑作者的知識(shí)水平，而是腦子有點(diǎn)燒糊涂了。前面我們描述完了sift以及surf算法，本片我們描述一下orb特征檢測算法。

今天一看，竟然已經(jīng)寫了15篇文章了，也為自己的堅(jiān)持點(diǎn)個(gè)贊 ~ (≧▽≦)/ ~ 。的的確確這段時(shí)間，對一些算法的理解也有了更深的層次，再接再厲，今晚獎(jiǎng)勵(lì)給我家貓獎(jiǎng)勵(lì)一罐小魚干。

ORB簡介

ORB 全稱：Oriented FAST and Rotated BRIEF，是一種快速特征點(diǎn)提取和描述的算法，發(fā)布于“ORB：An Efficient Alternative to SIFT or SURF” 論文中。從名字中，我們可以看出是由兩部分構(gòu)成，Oriented FAST 和 Rotated BRIEF，這也以最簡單的語言描述了ORB算法。ORB算法分為兩部分，分別是特征點(diǎn)提取和特征點(diǎn)描述。特征提取是由FAST算法（前面已經(jīng)學(xué)過）發(fā)展來的，特征點(diǎn)描述是根據(jù)BRIEF特征描述算法改進(jìn)的。

ORB算法最大的特點(diǎn)就是計(jì)算速度快，計(jì)算時(shí)間大概只有SIFT的1%，SURF的10%，這主要是因?yàn)槭褂昧薋AST來加速了特征點(diǎn)的提取。再次是使用BRIEF算法計(jì)算描述子，該描述子特有的2進(jìn)制串的表現(xiàn)形式不僅節(jié)約了存儲(chǔ)空間，而且大大縮短了匹配的時(shí)間。

當(dāng)然ORB算法也有一些缺點(diǎn)，比如尺度變換的應(yīng)對能力比較低。接下來我們來看ORB的流程，來分析一下ORB特征提取的優(yōu)缺點(diǎn)。

ORB 算法流程

1. 關(guān)鍵點(diǎn)提取

有關(guān)FAST算法，可以跳轉(zhuǎn)去看另一篇來詳細(xì)描述FAST特征點(diǎn)的筆記：FAST角點(diǎn)學(xué)習(xí)筆記中查看。本節(jié)主要描述ORB算法中對FAST算法的改進(jìn)。

ORB對FAST的改進(jìn)或者拓展，主要是為其增加了其尺度不變性以及旋轉(zhuǎn)不變性。接下里來看一看怎么實(shí)現(xiàn)的。

1. 提取FAST特征點(diǎn)

通過FAST算法提取出FAST特征點(diǎn)，過程不在詳細(xì)描述，這樣我們就找到了一張圖片的基本的關(guān)鍵點(diǎn)。

2. 建立金字塔

ORB實(shí)現(xiàn)尺度不變性，也是通過圖像金字塔來實(shí)現(xiàn)的。ORB論文本身并沒有解決尺度不變性，而是在opencv實(shí)現(xiàn)中添加了這部分，具體做法為設(shè)置一個(gè)比例因子scale（opencv默認(rèn)取1.2）和金字塔的層數(shù)n（通常取8）。將原圖像按比例因子縮小成n幅圖像?？s放后的圖像為：I’= I / scale^k (k=1,2,…, n)。n幅不同比例的圖像提取特征點(diǎn)總和作為這幅圖像的FAST特征點(diǎn)。

當(dāng)然可以通過采用不同的高斯核進(jìn)行高斯模糊來建立金字塔，但是時(shí)間成本就很高了。

3. 定義特征點(diǎn)方向

ORB實(shí)現(xiàn)旋轉(zhuǎn)不變性，也是通過確定一個(gè)特征點(diǎn)的方向來實(shí)現(xiàn)的，我們來看看ORB是怎么來確定特征點(diǎn)的方向的？

ORB的論文中提出了一種利用灰度質(zhì)心法來解決這個(gè)問題，通過計(jì)算一個(gè)矩來計(jì)算特征點(diǎn)以r為半徑范圍內(nèi)的質(zhì)心，特征點(diǎn)坐標(biāo)到質(zhì)心形成一個(gè)向量作為該特征點(diǎn)的方向。我們來看看具體怎么實(shí)現(xiàn)灰度質(zhì)心法。

一個(gè)圖像塊（比如5x5的圖像塊中），對應(yīng)的2x2的矩的元素表達(dá)為：

x，y分別為坐標(biāo)值，I（x，y）為像素值

而該圖像窗口的質(zhì)心就是：

其實(shí)灰度的質(zhì)心就是對所有的位置進(jìn)行加權(quán)，權(quán)重就是像素值在整個(gè)圖像中像素值之和的比例。

那么特征點(diǎn)與質(zhì)心的夾角定義為FAST特征點(diǎn)的方向：

也就有了特征點(diǎn)的方向，繼而實(shí)現(xiàn)旋轉(zhuǎn)不變性。

通過上述步驟我們找到了所有的特征點(diǎn)，并計(jì)算出了特征點(diǎn)的方向，下面就看一下怎么描述這些特征點(diǎn)。

2. 關(guān)鍵點(diǎn)描述

ORB選擇了BRIEF作為特征描述方法，并對其進(jìn)行改進(jìn)使其加上旋轉(zhuǎn)不變性并增加其可區(qū)分性，首先我們先看看BRIEF描述子。

  • BRIEF描述子

BRIEF算法計(jì)算出來的是一個(gè)二進(jìn)制串的特征描述符。它是在每一個(gè)特征點(diǎn)的鄰域內(nèi)，選擇n對像素點(diǎn)pi、qi（i=1,2,…,n）。然后比較每個(gè)點(diǎn)對的灰度值的大小。如果I(pi)> I(qi)，則生成二進(jìn)制串中的1，否則為0。所有的點(diǎn)對都進(jìn)行比較，則生成長度為n的二進(jìn)制串。一般n取128、256或512，通常取256。

為了增強(qiáng)抗噪性，一般會(huì)先對圖像進(jìn)行高斯平滑。ORB算子采用5x5的子窗口進(jìn)行平滑。

那么這n個(gè)點(diǎn)對如何選取呢?
在點(diǎn)周圍選取點(diǎn)對(p,q)的方法有以下5種：

  1. 在圖像塊內(nèi)平均采樣；
  2. p和q都符合(0,S2/25)的高斯分布；
  3. p符合(0,S2/25)的高斯分布，而q符合(0,S2/100)的高斯分布；
  4. 在空間量化極坐標(biāo)下的離散位置隨機(jī)采樣；
  5. 把p固定為(0,0)，q在周圍平均采樣。

BRIEF作者采用的是第二種。而ORB作者沒有選擇以上任意方式，而是一種新的方式，我們在下面再說。

BRIEF流程簡單實(shí)時(shí)性較好，論文中生成512個(gè)描述子用時(shí)8.18ms，并且其描述子是二進(jìn)制碼，其匹配也比較快。但是，當(dāng)BRIEF對于旋轉(zhuǎn)過大時(shí)，比如超過30度時(shí)，匹配正確率迅速下降直到45度時(shí)為0。所以需要增加其描述子的旋轉(zhuǎn)不變性。

  • BRIEF算法改進(jìn)

在描述基礎(chǔ)BRIEF算法時(shí)，我們提出了兩個(gè)問題，一個(gè)是增加其旋轉(zhuǎn)不變性，一個(gè)是選點(diǎn)方式。

  • steered BRIEF 增加其旋轉(zhuǎn)不變性

所謂steered BRIEF　就是對挑選出的點(diǎn)對加上一個(gè)旋轉(zhuǎn)角度θ。對于任何一個(gè)特征點(diǎn)來說，它的BRIEF描述子是一個(gè)長度為??的二值碼串，這個(gè)二值碼串是由特征點(diǎn)鄰域??個(gè)點(diǎn)對生成的，我們現(xiàn)在講這2??個(gè)點(diǎn)(????,????),??=1,2,.....,2??組成一個(gè)矩陣??:

使用鄰域方向??和對應(yīng)的旋轉(zhuǎn)矩陣????，構(gòu)建??的一個(gè)校正版本????:

其中

即我們把坐標(biāo)軸旋轉(zhuǎn)]?????????，計(jì)算以主方向?yàn)樽鴺?biāo)系的匹配點(diǎn)對，如下圖：

steered BRIEF加入了旋轉(zhuǎn)不變性，但同時(shí)特征描述量的可區(qū)分行就下降了,所以就有了ORB作者提出的rBRIEF。

  • rBRIEF 增加其可區(qū)分性

我們在上邊說過ORB沒有使用BRIEF 5種選取點(diǎn)對方法中的任意一種，那么ORB用的是什么方式？
ORB使用統(tǒng)計(jì)學(xué)習(xí)的方法來重新選擇點(diǎn)對集合，目的是增大其特征描述量的可區(qū)分行。這里我們先不解釋其具體的實(shí)驗(yàn)流程（主要是我還沒有完全理解），但是通過其實(shí)驗(yàn)，選出來的點(diǎn)對對特征點(diǎn)描述的區(qū)分度變高了。

至此ORB算法計(jì)算完畢。

OpenCV ORB特征效果展示[代碼]

#include <opencv2/opencv.hpp>
#include <iostream>
#include <opencv2/xfeatures2d.hpp>
#include <opencv2/features2d/features2d.hpp>
void extracte_orb(cv::Mat input,std::vector<cv::KeyPoint> &keypoint,cv::Mat &descriptor){
    cv::Ptr<cv::ORB> f2d = cv::ORB::create(500);
    f2d->detect(input,keypoint);
    cv::Mat image_with_kp;
    f2d->compute(input,keypoint,descriptor);
    cv::drawKeypoints(input, keypoint, image_with_kp, cv::Scalar::all(-1),cv::DrawMatchesFlags::DRAW_RICH_KEYPOINTS);
    cv::imwrite("orb"+std::to_string(random())+".png",image_with_kp);
}

void match_two_image(cv::Mat image1,cv::Mat image2, std::vector<cv::KeyPoint> keypoint1,std::vector<cv::KeyPoint> keypoint2,cv::Mat descriptor1,cv::Mat descriptor2){
    cv::BFMatcher matcher(cv::NORM_HAMMING);
    std::vector<cv::DMatch> matches;
    matcher.match(descriptor1,descriptor2, matches);
    cv::Mat good_matches_image;
    cv::drawMatches(image1, keypoint1, image2, keypoint2,
                    matches, good_matches_image, cv::Scalar::all(-1), cv::Scalar::all(-1),
                    std::vector<char>(), cv::DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS);
    cv::imwrite("good_matches_image.png",good_matches_image);
    {
        std::vector <cv::KeyPoint> RAN_KP1, RAN_KP2;
        std::vector<cv::Point2f> keypoints1, keypoints2;
        for (int i = 0; i < matches.size(); i++) {
            keypoints1.push_back(keypoint1[matches[i].queryIdx].pt);
            keypoints2.push_back(keypoint2[matches[i].trainIdx].pt);
            RAN_KP1.push_back(keypoint1[matches[i].queryIdx]);
            RAN_KP2.push_back(keypoint2[matches[i].trainIdx]);
        }

        std::vector<uchar> RansacStatus;
        cv::findFundamentalMat(keypoints1, keypoints2, RansacStatus, cv::FM_RANSAC);
        std::vector <cv::KeyPoint> ransac_keypoints1, ransac_keypoints2;
        std::vector <cv::DMatch> ransac_matches;
        int index = 0;
        for (size_t i = 0; i < matches.size(); i++)
        {
            if (RansacStatus[i] != 0)
            {
                ransac_keypoints1.push_back(RAN_KP1[i]);
                ransac_keypoints2.push_back(RAN_KP2[i]);
                matches[i].queryIdx = index;
                matches[i].trainIdx = index;
                ransac_matches.push_back(matches[i]);
                index++;
            }
        }
        cv::Mat after_ransac_sift_match;
        cv::drawMatches(image1, ransac_keypoints1, image2, ransac_keypoints2,
                        ransac_matches, after_ransac_sift_match, cv::Scalar::all(-1), cv::Scalar::all(-1),
                        std::vector<char>(), cv::DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS);
        cv::imwrite("after_ransac_orb_match.png",after_ransac_sift_match);
    }
}

int main(int argc, char *argv[])
{
    cv::Mat image1 = cv::imread(argv[1]);
    cv::Mat image2 = cv::imread(argv[2]);
    std::vector<cv::KeyPoint> keypoint1,keypoint2;
    cv::Mat descriptor1, descriptor2;
    extracte_orb(image1,keypoint1,descriptor1);
    extracte_orb(image2,keypoint2,descriptor2);
    match_two_image(image1,image2,keypoint1,keypoint2,descriptor1,descriptor2);
    return 0;
}

因?yàn)閛rb難以應(yīng)對我們類似SIFT或surf那么大的仿射變換，所以不得不換了仿射變換小的照片

原圖1 orb識(shí)別效果 原圖2 orb識(shí)別效果
初步匹配效果 ransac后匹配效果

總結(jié)

總體來說ORB在上述實(shí)驗(yàn)實(shí)例中的效果還是很好的。我們已經(jīng)講完SIFT，SURF還有ORB，我們來對比一下這三個(gè)算法。
計(jì)算速度： ORB>>SURF>>SIFT（各差一個(gè)量級(jí)）
旋轉(zhuǎn)魯棒性： SURF>ORB~SIFT（～表示差不多）
模糊魯棒性： SURF>ORB~SIFT
尺度變換魯棒性： SURF>SIFT>ORB（ORB尺度變換性很弱）
在日常應(yīng)用中，有SURF基本就不用考慮SIFT，SURF基本就是SIFT的全面升級(jí)版，當(dāng)然也有其他SIFT的改進(jìn)版比如Affine SIFT的效果就要比SUFR要好更多，但是計(jì)算時(shí)間也有延長，而ORB的強(qiáng)點(diǎn)在于計(jì)算時(shí)間。ORB主要還是在VSLAM中應(yīng)用較多，場景變化不明顯，但是需要高速的計(jì)算時(shí)間，這正好符合ORB。

特征點(diǎn)到此結(jié)束，繼續(xù)加油

重要的事情說三遍：

如果我的文章對您有所幫助，那就點(diǎn)贊加個(gè)關(guān)注唄 ( * ^ __ ^ * )

如果我的文章對您有所幫助，那就點(diǎn)贊加個(gè)關(guān)注唄 ( * ^ __ ^ * )

如果我的文章對您有所幫助，那就點(diǎn)贊加個(gè)關(guān)注唄 ( * ^ __ ^ * )

傳統(tǒng)2D計(jì)算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門
傳統(tǒng)3D計(jì)算機(jī)視覺學(xué)習(xí)筆記目錄------->傳送門

任何人或團(tuán)體、機(jī)構(gòu)全部轉(zhuǎn)載或者部分轉(zhuǎn)載、摘錄，請保留本博客鏈接或標(biāo)注來源。博客地址：開飛機(jī)的喬巴

作者簡介：開飛機(jī)的喬巴（WeChat：zhangzheng-thu），現(xiàn)主要從事機(jī)器人抓取視覺系統(tǒng)以及三維重建等3D視覺相關(guān)方面，另外對slam以及深度學(xué)習(xí)技術(shù)也頗感興趣，歡迎加我微信或留言交流相關(guān)工作。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容