摘要：圖像矩圖像矩或稱幾何矩是由在年提出的。矩給出了對(duì)圖像形狀的一種度量。使用建議的第二種采樣方法即以圖像中心進(jìn)行高斯分布采樣，長度使用，然后在基礎(chǔ)上增加了旋轉(zhuǎn)的描述以及快速的計(jì)算方法，這種方法被稱為。

ORB（Oriented FAST and Rotated BRIEF）可用來替代SIFT（或SURF），它對(duì)圖像更具有抗噪特性，是一種特征檢測(cè)高效算法，其速度滿足實(shí)時(shí)要求，可用于增強(qiáng)圖像匹配應(yīng)用。
ORB的算法基于FAST角檢測(cè)（Features from accelerated segment test）和BRIEF(Binary Robust Independent Elementary Features)特征描述符，這也是它名字的由來。

FAST角檢測(cè)比之前我們介紹過的Harris角檢測(cè)、SIFT特征點(diǎn)檢測(cè)（使用高斯差）都要快，后兩者關(guān)注的是高質(zhì)量（精準(zhǔn)、穩(wěn)定性高）的特征檢測(cè)，但計(jì)算復(fù)雜，而FAST關(guān)注的是實(shí)時(shí)應(yīng)用，比如即時(shí)檢測(cè)定位（檢測(cè)視頻中的移動(dòng)物體），而且要在計(jì)算資源有限的智能手機(jī)上使用。

FAST檢測(cè)角點(diǎn)的過程真的很簡單：

以灰度圖像為例，從原圖像中選一個(gè)點(diǎn)（設(shè)為p），如上圖，放大顯示p點(diǎn)周圍的像素

給定一個(gè)閾值，比如設(shè)為p點(diǎn)灰度值的20%

以p為圓心，劃出半徑為3的圓，考慮落在圓周上的16個(gè)像素的值，若這16個(gè)像素連續(xù)N（N一般為12）個(gè)符合閾值，則認(rèn)為p為興趣點(diǎn)（角點(diǎn)）

為讓上面的判斷更快，可以先計(jì)算序號(hào)為1、5、9、13的4個(gè)像素（如圖），這4個(gè)像素至少要有3個(gè)符合閾值，才有可能存在連續(xù)12個(gè)像素滿足閾值，才有必要檢測(cè)其它像素。

對(duì)原圖像每一個(gè)像素，重復(fù)以上計(jì)算過程，最終得出所有興趣點(diǎn)。

FAST算法存在的問題：

N如果小于12，得出來的結(jié)果不是很理想，N建議值為12

只把圓周上的16個(gè)像素作為興趣點(diǎn)的信息貢獻(xiàn)（不一定適合大多數(shù)使用場(chǎng)景）

檢測(cè)出的興趣點(diǎn)，存在很多相鄰的興趣點(diǎn)（需要排除，選其一即可）

但現(xiàn)在這些問題可以通過機(jī)器學(xué)習(xí)的方法來解決。

skimage庫包含了FAST算法實(shí)現(xiàn)：

skimage.feature.corner_fast(image, n=12, threshold=0.15)

如果用一個(gè)二進(jìn)制串（binary strings）作為興趣點(diǎn)描述符（interest point descriptor，下很簡稱IPD），不僅存儲(chǔ)空間低，而且比較IPD，可以轉(zhuǎn)化為比較漢明距離（hamming distance），漢明距離為兩個(gè)二進(jìn)制串不同位的個(gè)數(shù)，用異或就可以簡單高效的完成計(jì)算。

BRIEF算法并不包含興趣點(diǎn)檢測(cè)（檢測(cè)可以用FAST或Harris等方法），它只是提出了一種二進(jìn)制串IPD，只需要256bit，甚至128bit就可以取得較好的匹配效果。在提取BRIEF二進(jìn)制串之前，需要先對(duì)圖像進(jìn)行高斯濾波（有關(guān)高斯濾波，前面筆記已詳細(xì)介紹，此不再述）以去除噪聲，然后使用其它方法檢測(cè)出興趣點(diǎn)，以其中一個(gè)興趣點(diǎn)為例：考慮以興趣點(diǎn)為中心的S×S大小的矩形圖像塊，以兩個(gè)像素值（設(shè)為p1和p2）為1對(duì)，隨機(jī)選N對(duì)（N為128或256或512），對(duì)每對(duì)（p1,p2）進(jìn)行測(cè)試，比較p1和p2，若p1二值測(cè)試（binary test）,將結(jié)果作為1bit存儲(chǔ)，N對(duì)的結(jié)果連在一起就組成了一個(gè)N bit的二進(jìn)制串。

如何選取N對(duì)像素？BRIEF給出了5種方法，并認(rèn)為第2種效果最好：

均勻采樣（uniformly sampled）

以圖像中心進(jìn)行高斯分布采樣，即越接近中心點(diǎn)的像素點(diǎn)將被優(yōu)先選擇

使用兩個(gè)不同sigma的高斯分布，設(shè)為G1和G2，所有p1用G1采樣，所有p2用G2采樣

使用粗極坐標(biāo)網(wǎng)格(coarse polar gird)的離散位置隨機(jī)采樣(原文：randomly sampled from discrete location of a coarse polar gird）

所有p1都固定為圖像塊的中心像素，所有p2用粗極坐標(biāo)網(wǎng)格采樣（每格采一像素）

對(duì)后兩種方法提到的粗極坐標(biāo)網(wǎng)格，看一下圖就不難理解了：

需要注意的是，BRIEF描述符沒有考慮多尺度，雖然對(duì)亮度、模糊、視角失真有一定的不變性，但它沒有考慮旋轉(zhuǎn)，容易受旋轉(zhuǎn)影響。

ORB其實(shí)綜合了FAST、Harris角測(cè)量、圖像矩、BRIEF等理論方法，并為實(shí)時(shí)計(jì)算提供解決方案。

ORB對(duì)FAST的補(bǔ)充

因FAST檢測(cè)出的鄰近興趣點(diǎn)通常會(huì)有很多，這些鄰近興趣點(diǎn)其實(shí)都位于同一個(gè)角點(diǎn)處。ORB的解決方法是：使用閾值過濾，并借助Harris角測(cè)量得到角點(diǎn)。

FAST沒有考慮圖像縮放，ORB構(gòu)造了不同縮放尺寸的圖像金字塔（詳細(xì)參考SIFT），對(duì)每一層圖像應(yīng)用上述方法檢測(cè)角點(diǎn)。

FAST檢測(cè)的角點(diǎn)沒有考慮方向，ORB借助圖像中心矩 計(jì)算方向。

圖像矩（image moment）
*圖像矩（或稱幾何矩）是由Hu(Visual pattern recognition by moment invariants)在1962年提出的。矩給出了對(duì)圖像形狀的一種度量。理解矩的概念有點(diǎn)困難，下面只是簡要說明ORB用到的中心矩，有興趣的讀者，可自行深入了解。

一個(gè)圖像塊I的p+q階矩的公式為：

其中，I(x,y)表示xy坐標(biāo)所在像素的亮度。
0階矩（記m00，用p=0, q=0代入上述公式）其實(shí)就是所有I(x,y)的和，即所有像素的亮度之和，也稱為圖像的總質(zhì)量(mass)。

用p=1,q=0代入公式，得到相對(duì)x的一階矩，記為m10，如果用m10除以m00，便可以得到x的平均值，也稱為中心值。同理，用p=0,q=1代入公式，得到相對(duì)y的一階矩，記為m01，用m01除以m00便得到y(tǒng)的中心值，x的中心值和y的中心值構(gòu)成了圖像亮度的 中心矩（centroid），記為C：

中心矩有時(shí)也稱為質(zhì)心，在二值圖像中，可用來代表形狀的中心。如果我們構(gòu)建一個(gè)從角點(diǎn)到中心矩的向量，那么此向量與X軸的角度為：

θ即為圖像塊的亮度方向，先旋轉(zhuǎn)到此方向再計(jì)算得出的興趣點(diǎn)描述符，便具有旋轉(zhuǎn)不變性。
測(cè)試表明，在圖像噪聲較大的情況下，此方法對(duì)旋轉(zhuǎn)相對(duì)SIFT更穩(wěn)定。

steered BRIEF
ORB使用BRIEF建議的第二種采樣方法（即以圖像中心進(jìn)行高斯分布采樣，IPD長度使用256bit），然后在BRIEF基礎(chǔ)上增加了旋轉(zhuǎn)的描述以及快速的計(jì)算方法，這種方法被稱為steered BRIEF。

BRIEF在選取點(diǎn)對(duì)（采樣）之前，需要對(duì)圖像應(yīng)用高斯濾波，而ORB則不用，取而代之的是使用以選取點(diǎn)為中心的5×5區(qū)域像素平均值，并用積分圖（integral image）來計(jì)算。積分圖，又稱總和面積表（summed area table，簡稱SAT），是一個(gè)快速且有效的對(duì)一個(gè)網(wǎng)格的矩形子區(qū)域中計(jì)算和的數(shù)據(jù)結(jié)構(gòu)和算法。

因引入了旋轉(zhuǎn)，采樣的點(diǎn)對(duì)坐標(biāo)也需要旋轉(zhuǎn)變換。將采樣點(diǎn)對(duì)坐標(biāo)組成矩陣S：

旋轉(zhuǎn)矩陣（Rotation matrix）設(shè)為Rθ：
Rθ =

則通過:
Sθ = S*Rθ
將S的每個(gè)列向量（x,y）關(guān)于原點(diǎn)逆時(shí)針旋轉(zhuǎn)θ，為加速計(jì)算，將360度以12度為單位離散為30份，事先計(jì)算好30個(gè)Sθ作為查找表，之后就可以節(jié)省坐標(biāo)變換這一步計(jì)算了。

看起來此方法不錯(cuò)，可惜的是，它的匹配效果比BRIEF差一截，通過大量樣本分析發(fā)現(xiàn)，BRIEF描述符有一個(gè)很好的特性，就是每一位bit對(duì)應(yīng)的點(diǎn)對(duì)之間表現(xiàn)出方差大、相關(guān)性小，而且同一位置bit的平均值接近0.5。但是steered BRIEF因進(jìn)行了坐標(biāo)旋轉(zhuǎn)，損失了這個(gè)特性，導(dǎo)致不同特征點(diǎn)描述符差別不大，相關(guān)性高，不利于匹配。所以O(shè)RB開發(fā)了另一種選取點(diǎn)對(duì)和計(jì)算IPD的方法——rBRIEF，此方法比steered BRIEF優(yōu)很多。

rBRIEF
這才是ORB最為關(guān)鍵的部分，一是因?yàn)橛悬c(diǎn)難懂（細(xì)節(jié)之處論文沒有講清楚），二是因?yàn)橛昧诉@個(gè)方法，使得ORB相較BRIEF和SURF表現(xiàn)突出。
rBRIEF是一種需要學(xué)習(xí)的算法，學(xué)習(xí)分兩步：

第一步，建立訓(xùn)練集，提取二值測(cè)試

論文例子使用的樣本數(shù)為30萬，即30萬個(gè)特征點(diǎn)及其對(duì)應(yīng)的（31×31）圖像塊，圖像數(shù)據(jù)來自PASCAL 2006 dataset

對(duì)每一個(gè)特征點(diǎn)， 其對(duì)應(yīng)的31×31圖像塊中，任選出兩個(gè)5×5的小塊組成一個(gè)二值測(cè)試，這種組合數(shù)目達(dá)到205590個(gè)，相當(dāng)于窮舉出了所有點(diǎn)對(duì)的可能組合

執(zhí)行所有二值測(cè)試，每個(gè)二值測(cè)試其實(shí)就是比較兩個(gè)5×5小塊的像素平均值（前文有述），結(jié)果為1或0，用1bit存儲(chǔ)，所以一個(gè)特征點(diǎn)得出一個(gè)向量[b1,b2,...,b205590]

循環(huán)上述計(jì)算步驟，直至完成30萬個(gè)特征點(diǎn)，將所有向量組成矩陣A，共30萬行：

[b1,b2,...,b205590]
[b1,b2,...,b205590]
...
[b1,b2,...,b205590]
[b1,b2,...,b205590]

第二步，排序，挑選

計(jì)算矩陣A的每一列的平均值，設(shè)為avg，那么該列與0.5的距離為：d = avg - 0.5

將矩陣A的列按d從小到大順序排列，結(jié)果設(shè)為T

將T中第一列放到結(jié)果矩陣R中

從T中拿出第一列，與R中所有列進(jìn)行比較，若它與R中任何一列的絕對(duì)相關(guān)度（absolute correlation）大于給定閾值，則丟棄，否則將它放入R中，循環(huán)執(zhí)行這一步，直到R中有256列

如果所有T的列都?xì)v遍了，R中的列數(shù)還不足256，則增大閾值，重復(fù)上述步驟，直至R中有256列

經(jīng)過第二步的計(jì)算，我們得到一個(gè)列向量之間相關(guān)性最小、每個(gè)列向量均值最接近0.5的結(jié)果集R（30萬行，256列），每一行即可以做為對(duì)應(yīng)特征點(diǎn)的IPD（256bit），此IPD對(duì)應(yīng)的點(diǎn)對(duì)組合是最優(yōu)的。

新的特征點(diǎn)的計(jì)算過程：

參考上述第一步，窮舉計(jì)算特征點(diǎn)所有可能的二值測(cè)試

將結(jié)果作為一行加入矩陣A中，按照上述第二步進(jìn)行計(jì)算，就可以得到此特征點(diǎn)對(duì)應(yīng)的IPD
因之前的樣本都計(jì)算過，所以對(duì)新的特征點(diǎn)來說，計(jì)算消耗就是上述第二步。

最后，還遺留有一個(gè)小問題沒有講清楚，就是二進(jìn)制向量間的絕對(duì)相關(guān)度（absolute correlation）如何計(jì)算？用漢明距離？

skimage庫包含了一個(gè)ORB類：

from skimage.feature import ORB

若import出錯(cuò)，查看scikit-image包版本：

pip show scikit-image
---
Name: scikit-image
Version: 0.11.3

如果低于此版本需要進(jìn)行升級(jí)：

sudo pip install -U scikit-image

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

class skimage.feature.ORB(downscale=1.2, n_scales=8, 
                        n_keypoints=500, fast_n=9, fast_threshold=0.08, harris_k=0.04)

downscale : 縮減因子，用于構(gòu)建圖像金字塔，默認(rèn)值1.2可以增強(qiáng)特征對(duì)圖像縮放尺度不變性
n_scales : 圖像金字塔的最大層數(shù)
n_keypoints : 指定最多檢測(cè)多少個(gè)關(guān)鍵點(diǎn)
fast_n : FAST算法的N值，即圓周上連續(xù)N個(gè)點(diǎn)符合閾值時(shí)，則中心點(diǎn)為關(guān)鍵點(diǎn)
fast_threshold : FAST算法閾值，設(shè)Ic為圓周上的像素值，Ip為中心像素值，若 Ic < Ip - fast_threshold 或 Ic > Ip + fast_threshold，表示符合閾值
harris_k : 為harris角檢測(cè)k方法中的k系數(shù)（詳見之前筆記），用于將角點(diǎn)從邊緣分離出來，典型取值區(qū)間[0, 0.2]，值越小表示檢測(cè)越銳利的邊緣

類方法
detect(image)： 檢測(cè)圖像關(guān)鍵點(diǎn)
extract(image, keypoints, scales, orientations)： 為給定關(guān)鍵點(diǎn)提取rBRIEF描述符
detect_and_extract(image)： 檢測(cè)圖像關(guān)鍵點(diǎn)并提取rBRIEF描述符，此方法比用上面兩步要快

對(duì)象屬性
keypoints: 關(guān)鍵點(diǎn)坐標(biāo)數(shù)組
scales： 尺度數(shù)組
orientations： 方向（弧度）數(shù)組
responses： harris角檢測(cè)結(jié)果
descriptors：描述符數(shù)組

ORB論文中沒有描述如何比較兩個(gè)IPD的相關(guān)性和如何匹配，但BRIEF是有指出用漢明距離比較IPD。下面的例子，我使用是skimage庫中的一個(gè)匹配函數(shù)：

skimage.feature.match_descriptors(descriptors1, descriptors2, metric=None, 
                                            p=2, max_distance=inf, cross_check=True)

metric: 指定匹配算法： {‘euclidean’, ‘cityblock’, ‘minkowski’, ‘hamming’, ...}，默認(rèn)使用hamming(漢明距離)
max_distance： 兩個(gè)IPD之間的最大距離，小于此距離才認(rèn)為是匹配的，經(jīng)測(cè)試，它的取值范圍為[0.0,1.0]
cross_check: 為True時(shí)，表示使用兩向匹配，即兩個(gè)IPD相互認(rèn)為對(duì)方是最佳匹配時(shí)，才確定對(duì)應(yīng)關(guān)系

綜合以上函數(shù)，找出兩張圖像的若干對(duì)應(yīng)關(guān)鍵點(diǎn)的代碼示例：

from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
from skimage.feature import (match_descriptors, ORB, plot_matches)
                             
im1 = Image.open("y1.jpg")
im2 = Image.open("y2.jpg")
img1 = np.array(im1.convert("L"))
img2 = np.array(im2.convert("L"))

o = ORB(n_keypoints=200)     #創(chuàng)建一個(gè)ORB對(duì)象，只提取200個(gè)關(guān)鍵點(diǎn)
o.detect_and_extract(img1)   #提取第一幅圖像                    
k1 = o.keypoints
d1 = o.descriptors

o.detect_and_extract(img2)   #提取第二幅圖像                       
k2 = o.keypoints
d2 = o.descriptors

matches12 = match_descriptors(d1, d2, cross_check=True, max_distance=0.5)

plot_matches(plt, im1, im2, k1, k2, matches12)
plt.axis("off")
plt.show()

效果圖：

從整個(gè)ORB的設(shè)計(jì)思想可以看出，它重在快速計(jì)算，目的就是為了滿足在實(shí)時(shí)計(jì)算情景下使用，而且通過大量的樣本分析得出，ORB并不遜于SIFT和SURF，反而在圖像受噪聲影響的情況下，ORB表示出更穩(wěn)定的特性。
另外，ORB的rBRIEF描述符需要事先訓(xùn)練學(xué)習(xí)，但我覺得這不是問題，第一，今時(shí)今日非常容易收集和獲取到更具有代表性的數(shù)據(jù)樣本；第二，訓(xùn)練這一步計(jì)算可以由后臺(tái)服務(wù)器來實(shí)現(xiàn)，所以O(shè)RB非常適合在移動(dòng)設(shè)備上使用。
目前，關(guān)于ORB可參考的中文資料缺乏，加上論文原文有一些關(guān)鍵細(xì)節(jié)沒有表達(dá)出來，所以在學(xué)習(xí)ORB上花了較多的時(shí)間。但本文包含的所介紹的方法，其思想讓人視野開闊。
本文所述內(nèi)容，可能存在理解偏差，歡迎指正。

FAST
BRIEF
Image moment
ORB