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

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

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

FAST檢測角點的過程真的很簡單：

以灰度圖像為例，從原圖像中選一個點（設為p），如上圖，放大顯示p點周圍的像素

給定一個閾值，比如設為p點灰度值的20%

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

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

對原圖像每一個像素，重復以上計算過程，最終得出所有興趣點。

FAST算法存在的問題：

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

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

檢測出的興趣點，存在很多相鄰的興趣點（需要排除，選其一即可）

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

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

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

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

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

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

均勻采樣（uniformly sampled）

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

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

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

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

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

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

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

ORB對FAST的補充

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

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

FAST檢測的角點沒有考慮方向，ORB借助圖像中心矩 計算方向。

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

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

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

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

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

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

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

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

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

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

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

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

rBRIEF
這才是ORB最為關鍵的部分，一是因為有點難懂（細節(jié)之處論文沒有講清楚），二是因為用了這個方法，使得ORB相較BRIEF和SURF表現(xiàn)突出。
rBRIEF是一種需要學習的算法，學習分兩步：

第一步，建立訓練集，提取二值測試

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

對每一個特征點， 其對應的31×31圖像塊中，任選出兩個5×5的小塊組成一個二值測試，這種組合數(shù)目達到205590個，相當于窮舉出了所有點對的可能組合

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

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

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

第二步，排序，挑選

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

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

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

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

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

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

新的特征點的計算過程：

參考上述第一步，窮舉計算特征點所有可能的二值測試

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

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

skimage庫包含了一個ORB類：

from skimage.feature import ORB

若import出錯，查看scikit-image包版本：

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

如果低于此版本需要進行升級：

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

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

對象屬性
keypoints: 關鍵點坐標數(shù)組
scales： 尺度數(shù)組
orientations： 方向（弧度）數(shù)組
responses： harris角檢測結(jié)果
descriptors：描述符數(shù)組

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

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

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

綜合以上函數(shù)，找出兩張圖像的若干對應關鍵點的代碼示例：

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)建一個ORB對象，只提取200個關鍵點
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()

效果圖：

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

FAST
BRIEF
Image moment
ORB