【小林的OpenCV基礎課 22】BRIEF/ORB/故事未結束

來自專欄 小林的CV視覺工坊

【非自然死亡】想看??，同學們有木有看完的？

關於【超能力女兒】（B站給的分類標籤是：搞笑/裝逼/日常/漫改）有同學留言說「杏子小天使」，小林表示高票贊同。杏子與雛的環境不同，世界觀也不同，但她倆都漸漸融入到大人的生活中，變得越來越懂事了。

導覽

上一話我們講到了FAST演算法，原理簡潔，速度快。其實從SIFT開始，我們一直在對特徵檢測演算法進行優化，從SIFT到SURF是對細節運算的優化，而FAST則直接對演算法流程進行改進。這一優化的過程使運算速度大為提升。

但有個問題一直沒有解決，就是SIFT和SURF的描述需要佔據很多存儲空間，對於嵌入式應用非常不利。

於是又有人提出了BRIEF描述，這種描述採用二進位位，佔用空間小，而且在特徵匹配時運算更快（使用異或運算）。

那如何將BRIEF描述與檢測演算法結合呢？ORB演算法應運而生。

關於BRIEF描述

全稱Binary Robust Independent Elementary Features，提出的背景是SIFT描述是128維度，佔用512 bytes，SURF描述是64維度，佔用256 bytes，這兩種描述佔用空間過大，而並不是所有維度信息都是有用的。

BRIEF描述的思想就是，在關鍵點周圍做像素值比較，得到的結果是二進位串。

在使用BRIEF之前我們要先做關鍵點檢測，論文中推薦使用CenSurE演算法，當然也可以用SIFT或SURF。

首先對圖像平滑，然後在關鍵點周圍選取一個圖像塊，在圖像塊中按一定規則選取一系列像素點對，同時生成一個nd向量，大小為選取的像素的對數。假設選取了像素點p和q，對應的像素值為Ip和Iq。

若Ip<Iq，則對應的nd向量元素的值為1，否則為0。

注意，nd向量存儲的是二進位位，它可以為128位或256位或512位，在OpenCV中默認為256位，又因為OpenCV用位元組數表示，所以256位又可以用32位元組表示。

對於如何選取像素點對，論文中有詳細的解釋，這裡不展開講。

那如何用BRIEF描述進行特徵匹配呢？前面提到了Hamming距離，我們要用它來計算匹配度。

Hamming距離是對兩個二進位串做異或運算，而異或運算對CPU來說是非常快的。

何為Hamming距離？其實就是比較兩個二進位串對應位置的不同數值的個數，換句話說，它就是將一個字元串變換成另外一個字元串所需要替換的字元個數。實質上是做了異或運算。

小林來做下總結：

• BRIEF描述是基於二進位串的運算，速度快，存儲空間少
• 圖像發生微小旋轉時依然能保持較大的識別率，但旋轉過大時識別率會大大降低

ORB演算法淺析

ORB=(FAST pro)+(BRIEF pro)，沒錯，強強聯手。往細里講，ORB=(Oriented FAST)+(Rotated BRIEF)。

然後，SURF和SIFT都有專利保護，而ORB並沒有。(此處應該有開源支持者的掌聲)

現在來看下ORB演算法幹了個啥事。

ORB=(Oriented FAST)+(Rotated BRIEF)，很明顯，ORB要解決兩個痛點：

• FAST不會計算關鍵點主方向
• BRIEF對旋轉肥腸敏感

ORB首先用FAST找到關鍵點，然後用Harri角點演算法篩選出Top N個關鍵點。

• 為了解決尺度不變，ORB也使用了金字塔構建尺度空間

現在我們來解決上面的兩個痛點

• FAST pro：要使FAST計算主方向。使用矩(moment)來計算主方向，公式如下

• BRIEF pro：要使BRIEF能應對大幅度旋轉，首先採用暴力窮舉的方式找到像素點對，然後讓BRIEF二進位串與旋轉矩陣相乘，得到旋轉後的BRIEF二進位串。

BRIEF描述在OpenCV中的實現

上面小林講到，要使用BRIEF描述，得先做特徵檢測。這裡既可以用SIFT也可以用SURF，但論文中建議用一個叫CenSurE的演算法，在OpenCV中這種演算法對應的檢測器叫做Star。

API：

首先創建Star檢測器

retval=cv2.xfeatures2d.StarDetector_create([, maxSize[, responseThreshold[, lineThresholdProjected[, lineThresholdBinarized[, suppressNonmaxSize]]]]])

由於Star檢測器繼承自Feature2D類，因此可以使用：

keypoints=cv2.Feature2D.detect(image[, mask])

但不能使用以下的函數，因為Star只是一個檢測器：

keypoints, descriptors=cv2.Feature2D.compute(image, keypoints[, descriptors])keypoints, descriptors=cv2.Feature2D.detectAndCompute(image, mask[, descriptors[, useProvidedKeypoints]])

再創建BIREF描述對象：

retval=cv2.xfeatures2d.BriefDescriptorExtractor_create([, bytes[, use_orientation]])

• bytes：BRIEF描述的尺寸，默認值32位元組
• use_orientation：是否使用旋轉計算，默認值False

同樣，因為繼承自Feature2D類，可以使用：

keypoints, descriptors=cv2.Feature2D.compute(image, keypoints[, descriptors])

下面是完整Demo

import numpy as npimport cv2img = cv2.imread(Mavic Air Fly.jpeg)grayImg = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)# 創建一個CenSurE檢測器 這是論文中推薦的檢測器star = cv2.xfeatures2d.StarDetector_create()# 創建一個brief描述brief = cv2.xfeatures2d.BriefDescriptorExtractor_create()# 檢測關鍵點並生成描述kp = star.detect(img, None)kp, des = brief.compute(img, kp)print(des)print(des.shape)

將顯示如下信息

[[183 185 123 ..., 151 161 8] [ 17 17 78 ..., 221 194 119] [183 177 122 ..., 199 84 12] ..., [ 27 5 240 ..., 108 64 251] [ 48 85 103 ..., 212 65 107] [ 57 150 70 ..., 40 194 197]](199, 32)

ORB演算法在OpenCV中的實現

小林要講兩個事：

• 用ORB做特徵點檢測
• 用ORB做特徵點匹配

先看檢測

構造方法如下：

retval=cv.ORB_create([,nfeatures[,scaleFactor[,nlevels[,edgeThreshold[,firstLevel[,WTA_K[,scoreType[,patchSize[,fastThreshold]]]]]]]]])

• nfeatures：我們要獲取的特徵點的最大數量
• fastThreshold：FAST演算法使用的閾值t
• 其他參數都有默認值，特殊需要時我們再考慮他們

檢測和計算描述的方法如下：

keypoints=cv2.Feature2D.detect(image[, mask])keypoints, descriptors=cv2.Feature2D.compute(image, keypoints[, descriptors])keypoints, descriptors=cv2.Feature2D.detectAndCompute(image, mask[, descriptors[, useProvidedKeypoints]])

檢測的Demo如下：

import numpy as npimport cv2img = cv2.imread(Mavic Air Fly.jpeg)grayImg = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)# 創建一個CenSurE檢測器orb = cv2.ORB_create(nfeatures=200)kp, des = orb.detectAndCompute(grayImg, None)img2 = cv2.drawKeypoints(img, kp, None, (0, 255, 0), 0)cv2.imshow(KP, img2)cv2.waitKey()cv2.destroyAllWindows()

再看匹配

大致流程依然是：

• 分布計算兩幅圖的特徵和描述
• 使用BFMatcher匹配，要將距離參數設置為Hamming距離

Demo如下：

import numpy as npimport cv2img1 = cv2.imread(Mavic Air Fly.jpeg)img2 = cv2.imread(Mavic Air Fly yuntai Erected.jpeg)grayImg1 = cv2.cvtColor(img1, cv2.COLOR_BGR2GRAY)grayImg2 = cv2.cvtColor(img2, cv2.COLOR_BGR2GRAY)matchImg = np.zeros_like(img1)orb = cv2.ORB_create(nfeatures=50)kp1, des1 = orb.detectAndCompute(grayImg1, None)kp2, des2 = orb.detectAndCompute(grayImg2, None)# 創建BF匹配對象 使用Hamming距離bf = cv2.BFMatcher_create(cv2.NORM_HAMMING, crossCheck=True)matches = bf.match(des1, des2)matches = sorted(matches, key=lambda x: x.distance)matchImg = cv2.drawMatches(img1, kp1, img2, kp2, matches, matchImg, flags=cv2.DRAW_MATCHES_FLAGS_NOT_DRAW_SINGLE_POINTS)cv2.imshow(match, matchImg)cv2.waitKey()cv2.destroyAllWindows()

這一話的代碼已經同步到Github上了，在Class 5 Feature Detection and Description文件夾下，對應C5 brief.py、C5 ORBDetect.py和C5 ORBMatch.py。