【機器視覺】9. 小結

05-20

【機器視覺】9. 小結

來自專欄 Let Machine See

機器視覺：小結

本專欄用了八篇文章，對機器視覺中常用的方法進行了介紹。

Calvin Shi：【機器視覺】1. 張正友平面標定法

Calvin Shi：【機器視覺】2. 特徵點檢測：Harris, SIFT, SURF, ORB

Calvin Shi：【機器視覺】3. 目標跟蹤：光流法

Calvin Shi：【機器視覺】4. 卡爾曼濾波

Calvin Shi：【機器視覺】 5. 立體視覺與三維重建

Calvin Shi：【機器視覺】6. 圖像處理的基礎知識

Calvin Shi：【機器視覺】7. 目標跟蹤：背景減除、粒子濾波、meanshift

Calvin Shi：【機器視覺】8. 特徵檢測及其應用

前面五篇文章基本上搭建起了機器視覺的脈絡，即：

攝像機標定並消除畸變
提取圖像中的特徵點
用光流法對目標點進行追蹤，並引入卡爾曼濾波，在包含雜訊的觀測序列中估計系統的狀態
在多幅圖像中建立對應點對，然後重構場景中的三維坐標
對攝像機進行校正，並獲取深度信息

接下來的三篇文章是對以上內容的擴展：

機器視覺涉及到大量的對數字圖像進行處理的操作，因而我們用一篇文章介紹了圖像處理中的基本演算法
目標跟蹤問題中，除了光流法外，還有背景減除和Meanshift等常用演算法；除了使用卡爾曼濾波的思路，還可以使用貝葉斯濾波和粒子濾波
我們有時不僅對「點」特徵感興趣，還對邊緣、邊界等特徵感興趣，這樣就要用到Canny邊緣檢測、邊界跟蹤、Hough變換等演算法

本文是對以上內容進行的梳理與總結。

張正友平面標定法

我們首先介紹了利用齊次坐標對空間中的點進行描述的方法，使用齊次坐標的目的，是為了利用矩陣變換，不僅能表示伸縮與旋轉，還能夠表示平移。齊次變換矩陣

${}{_B^A}{}T=egin{pmatrix}{}{_B^A}{}R & {}^A {P_{OB}}\ oldsymbol{0}^T & 1end{pmatrix}$

歐拉角適合用於表示兩個坐標系之間的旋轉。歐拉角方法根據一切旋轉都能分解為三次繞空間中不同軸的旋轉的原理，表明了一切坐標系的取向，都可以用三個歐拉角來表示。我們同時推導出了由歐拉角到旋轉矩陣的轉換關係。

接著，我們介紹了攝像機模型下的幾個坐標系，並通過幾何光學原理，推導出uv垂直和uv不垂直兩種情況下的攝像機內參數模型，並表示為矩陣K。然而，我們一般描述一個三維點，由於相機可能一直在運動，所以我們並不是基於攝像機坐標系下對其描述。我們通常是在世界坐標系下進行描述。攝像機外參數模型就是將物體在世界坐標系中的位置，變換到攝像機坐標系下。攝像機外參數矩陣是一個四階矩陣

${}{_w^c} M=egin{pmatrix}{}{_w^c}{}R & {}{^c}P_{Ow} \ 0^T & 1end{pmatrix}$

則攝像機參數矩陣（單應矩陣）

$M_{3 imes 4}=(K,oldsymbol{0})cdot {}{_w^c} M$

Note. 單應性變換（homography transform）就是一個平面到另一個平面的映射關係。在標定問題里，單應矩陣包括攝像機內外參數矩陣。

接著，我們首先介紹了直接線性變換（DLT）標定法求取攝像機的內外參數，介紹這一方法的目的在於讓大家熟悉對於在攝像機標定問題中常見的這類線性方程組的一般求解過程，也就是線性最小二乘的一般思路。

與DLT標定相比，張正友平面標定法放寬了對uv坐標的限制（認為u不一定垂直於v），並考慮了畸變的影響。總體思路是：先不考慮畸變，標定攝像機參數，得到參數的線性初值；然後利用線性初值，進行非線性標定，得到畸變參數。

最後，由於結果可能存在高斯雜訊，所以使用最大似然估計進行優化。優化問題化為一個非線性最小二乘問題，我們介紹了求解這類問題的三種基本演算法：最速下降法、高斯-牛頓法和Levenburg-Marquardt演算法。

特徵點提取

我們介紹了四種特徵點，其中，Harris角點檢測、SIFT演算法和SURF演算法是計算機視覺中十分經典的特徵點演算法，其意義已經超越了演算法本身，成為計算機視覺研究中的一種範式（paradigm），而ORB演算法則因其處理速度而得到了廣泛應用。儘管隨著目前深度學習如火如荼地發展，SIFT、SURF這類特徵提取方法越來越多的被深度神經網路替代，但是，這些方法本身的研究思路，對於我們在計算機視覺和機器學習領域進行更深入的研究，和對現有演算法的改進，是非常有用的。可以參考：

目前火熱的Deep Learning會滅絕傳統的SIFT/ SURF的特徵提取的演算法嗎？?

www.zhihu.com

Harris角點檢測

角點特徵是最早被提出的特徵點。角點檢測的基本思想是最小化角點響應函數

$E(u,v)=sum_{(x,y)} w(x,y) [I(x+u,y+v)-I(x,y)]^2$

其中w為窗函數（window function），I為圖像梯度，那麼E就表示了灰度變化的劇烈程度，Harris角點檢測定義窗口函數為二維高斯函數，並通過泰勒展開考察微小移動

$E(u,v)=(u,v)Megin{pmatrix} u\ v end{pmatrix}\ ext{where }M=sum_{(x,y)}w(x,y)egin{pmatrix} I_X^2 & I_X I_Y \ I_X I_Y & I_Y^2 end{pmatrix}=egin{pmatrix} sum_W I_X^2 & sum_W I_X I_Y \ sum_W I_X I_Y & sum_W I_Y^2 end{pmatrix}$

自相關矩陣M描述了圖像局部區域的灰度變化趨勢，E可以看做一個橢圓，可以通過橢圓的形狀來判定角點。

1994年，Shi和Tomasi對Harris角點檢測進行了改進，即定義角點響應函數R=min? (λ1，λ2)，該改進是計算適合跟蹤的優質特徵（good features to track），使得特徵分布更均勻，其檢測精度是亞像素級別的。

SIFT

1999年Lowe提出了SIFT(Scale-invariant feature transform，尺度不變性特徵變換)特徵檢測演算法，並於2003年對其完善總結；2006年，Bay等人對SIFT演算法進行了改進，提升其效率，提出了SURF(Speeded Up Robust Features，加速魯棒性特徵)演算法。

SIFT特徵檢測的步驟：

檢測尺度空間的極值點
精確定位特徵點(Keypoint)
設定特徵點的方向參數
生成特徵點的描述子（128維向量）

首先利用高斯金字塔生成尺度空間，通過尺度空間理論模擬圖像數據的多尺度特徵，以高斯函數為實現尺度變換的唯一線性核，則二維圖像I(x, y)的尺度空間

$L(x,y,sigma)=I(x,y)*g(x,y,sigma)\ ext{where } g(x,y,sigma)=frac{1}{2pisigma^2 } exp? left(-frac{x^2+y^2}{2sigma^2 } ight)$

定義高斯差分（difference of Gaussian, DoG）運算元

$D(x,y,sigma,k)=L(x,y,ksigma)-L(x,y,sigma) approx (k-1) abla^2 h$

其中 $abla^2 h$ 表示高斯拉普拉斯運算元（LoG）。

檢測尺度空間的極值點，利用DoG函數在尺度空間的Taylor展開式(擬合函數)為：

$D(X)=D+frac{partial D^T}{partial X} X+frac{1}{2} X^T frac{partial^2 D}{partial X^2} X \ ext{where } X=[x,y,sigma,k]^T$

求導並讓方程等於零，可以得到極值點的偏移量為：

$hat X= -frac{partial^2 D^{-1}}{partial X^2 } frac{partial D}{partial X}$

對於這樣得到的極值點，首先要捨去高斯差分運算元絕對值很小（一般指|D(hat X)|<0.03）的點，然後通過主曲率分析去除邊緣響應過大的極值點。

接下來對L(x,y,σ)進行差分，得到鄰域梯度方向直方圖（這裡常用Roberts運算元計算），進而確定特徵的方向參數。當圖像發生旋轉時，特徵點的主方向相對於像素的梯度方向不變；將多幅待匹配的圖像都旋轉到令特徵點方向為0的位置再匹配，使特徵具有旋轉不變性。

現在我們將坐標軸方向旋轉為特徵點的方向，以特徵點為中心取窗口，通過高斯加權增強特徵點附近像素梯度方向信息的貢獻，即在4 × 4的小塊上計算梯度方向直方圖（取8個方向），計算梯度方向累加值，形成種子點，構成4× 4 × 8= 128維特徵向量。SIFT特徵對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、雜訊也保持一定程度的穩定性。

SURF

SURF特徵(Speeded Up Robust Features，加速魯棒性特徵)是對SIFT特徵的進一步優化：

基於Hessian矩陣構造金字塔尺度空間，
利用箱式濾波器（box filter）簡化二維高斯濾波，不需要再進行降採樣；
通過Haar小波特徵設定特徵點主方向，這樣構建的特徵描述子就是64維的；
SURF構造的金字塔圖像與SIFT有很大不同，就是因為這些不同才加快了其檢測的速度。SIFT採用的是DOG圖像，而SURF採用的是Hessian矩陣行列式近似值圖像，也寫作DOH運算元。

在SIFT演算法中，每一組（octave）的圖像大小是不一樣的，下一組是上一組圖像的降採樣（1/4大小）；在每一組裡面的幾幅圖像中，他們的大小是一樣的，不同的是他們採用的尺度不同。而且在模糊的過程中，他們的高斯模板大小總是不變的，只是尺度改變。對於SURF演算法，圖像的大小總是不變的，改變的只是高斯模糊模板的尺寸，當然，尺度也是在改變的，但不需要降採樣過程，節省時間。

為了保證旋轉不變性，在SURF中，不統計其梯度直方圖，而是統計特徵點領域內的Harr小波特徵，並給這些響應值賦高斯權重係數，使得靠近特徵點的響應貢獻大，而遠離特徵點的響應貢獻小，然後60度範圍內的響應相加以形成新的矢量，遍歷整個圓形區域，選擇最長矢量的方向為該特徵點的主方向。

在特徵點周圍取正方形框，方框的方向為特徵點主方向，把方框分為16個子區域，在每個子區域統計水平方向和垂直方向的haar小波特徵，在每個子區域計算haar小波特徵的水平方向值之和，水平方向絕對值之和、垂直方向值之和、垂直方向絕對值之和，構成16× 4=64維特徵向量。

在完成採集後，還需要建立圖像的特徵點資料庫，每個特徵點的數據結構包括：位置坐標、尺度、方向、特徵向量（128或64維）；為新圖像的每個特徵點在資料庫中逐個匹配，即根據特徵向量的歐氏距離在資料庫中尋找其最近鄰和次近鄰特徵點，若最近鄰距離或次近鄰距離大於某一闕值，則特徵匹配成功。

ORB

ORB特徵是將FAST特徵點的檢測方法與BRIEF特徵描述子結合起來，並在它們原來的基礎上做了改進與優化。ORB演算法的速度大約是SIFT的100倍，是SURF的10倍。ORB（Oriented FAST and Rotated BRIEF）是一種快速特徵點提取和描述的演算法。包括：

Oriented FAST：

提取FAST特徵。
訓練一個決策樹，篩選出最優的FAST特徵點。
非極大值抑制去除局部較密集特徵點。
建立金字塔，來實現特徵點的多尺度不變性。
使用矩（moment）法來確定FAST特徵點的方向。

Rotated BRIEF:

在使用oFast演算法計算出的特徵點中包括了特徵點的方向角度。假設原始的BRIEF演算法在特徵點SxS（一般S取31）鄰域內選取n對點集。經過旋轉角度θ旋轉，得到新的點對，在新的點集位置上比較點對的大小形成二進位串的描述符。
為了解決描述子的可區分性和相關性的問題，ORB使用統計學習的方法來重新選擇點對集合。

光流法

跟蹤是在圖像序列或視頻里對其中的特徵點進行追蹤的過程，光流（optical flow）是目標、場景或攝像機在連續兩幀圖像間運動時造成的目標的運動。它是圖像在平移過程中的二維矢量場，是通過二維圖像來表示物體點三維運動的速度場，反映了微小時間間隔內由於運動形成的圖像變化，以確定圖像點上的運動方向和運動速率。

光流提供了恢復運動的線索。

光流法主要依賴於三個假設：

[亮度恆定] 圖像中目標的像素強度在連續幀之間不會發生變化。
[時間規律] 相鄰幀之間的時間足夠短，以至於在考慮運行變化時可以忽略它們之間的差異。
[空間一致性] 相鄰像素具有相似的運動。

我們介紹了兩種光流獲取方法：Lucas-Kanade演算法和Farneback演算法。

卡爾曼濾波

目標跟蹤需要在包含雜訊的觀測序列中估計時變系統的狀態，這種估計稱為濾波估計。濾波估計中最經典的演算法就是卡爾曼濾波，我們對基本的卡爾曼濾波進行了詳細的推導，並介紹了兩種「進階」的卡爾曼濾波方法，EKF演算法和UKF演算法。

立體視覺與三維重建

Structure from motion

立體視覺問題的基本步驟，就是在完成攝像機標定後，在多幅圖像中建立對應點對，然後重構場景中的三維坐標。這一過程也稱為Structure from motion(SFM)，即由一系列包含著視覺運動信息（motion signals）的多幅二維圖像序列(2D image sequences)估計三維結構(3D model)的技術。

我們首先根據對極幾何推出了基礎矩陣的關係式 $x^TFx=0$ ，並進而由基礎矩陣推出了本質矩陣，即 ${x}{}^TFx=0Rightarrow E={K}{}^TFK$ ，接著我們介紹了求取F矩陣和E矩陣的八點法，並引入RANSAC演算法對八點法進行改進。

八點法，五點法等可以求出閉式解的前提是已經知道確切的點對。但實際情況中往往存在大量的雜訊，點與點不是精確地對應甚至出現一些錯誤匹配。為了解決這個問題，需要使用光束平差法（Bundle Adjustment）。

圖像I1中點p1在圖像I2中的對應點p2在某條極線上，但確切位置不知。視差(stereo)定義為|p1-p2|，場景中接近點P和Q ，圖像中的對應點為p1和p2,q1和q2 ，若已知p1和p2對應，則視差差別的絕對值||p1?p2 |-|q1?q2 ||應較小。

空間點重建問題可以描述為，設攝像機已完成標定，參數矩陣分別為M1,M2，已知p1(u1,v1),p2(u2,v2)，求點在三維空間中的坐標。三維重建是相機成像過程的逆過程，即從像素坐標系中某一像素點反向映射成世界坐標系中的空間點。

先從圖片中提取特徵點並進行匹配，然後進行優化求解，這類方法稱為特徵法或間接法。由於提取、匹配的過程中耗時很大，因此有人提出是否能不計算關鍵點或描述子，直接根據圖像的像素信息來計算相機運動，這類方法稱為直接法。

立體視覺就是由兩幅或多幅二維圖像恢復物體三維幾何形狀的方法
用C1和C2兩個攝像機同時觀察P點，P點是兩條直線的交點，這就唯一確定了它的三維位置
投影矩陣為 $M_1=[M_{11},m_1]$ 和 $M_2=[M_{21},m_2]$ 的雙攝像機的基礎矩陣與投影矩陣為 $M_1H$ 和 $M_2H$ 的雙攝像機基礎矩陣只相差一個常數因子，認為它們相同，即可認為基礎矩陣與世界坐標系的選擇無關。重建步驟：

由雙攝像機所得圖像的對應點，計算基礎矩陣F
將基礎矩陣F分解為 $F=[m_2]_{ imes} M_{21}$
設雙攝像機的投影矩陣為 $M_1=[I,0],M_2=[M_{21},m_2]$ ，然後據此重建三維空間點

攝像機校正與深度映射

攝像機校正的目的

對兩個攝像機的圖像平面重投影，使得它們精確落在同一個平面上
使圖像平面共面且水平對準，極點位於無窮遠處

Bouguet演算法，是將旋轉和平移矩陣分解成左右相機各旋轉一半的旋轉和平移矩陣分解的原則是使得，左右圖像重投影造成的畸變最小，左右視圖的共同面積最大。

從2D到3D，需要通過三角測量獲取深度信息，其前提是：

攝像機前向平行排列
已標定、無畸變的立體成像系統，兩個攝像機焦距相同
兩個攝像機的像平面精確位於同一平面，光軸嚴格平行
兩幅圖像是行對準的

圖像處理的基礎知識

直方圖均衡化（histogram equlization），目標是創建一幅在整個亮度範圍內具有相同亮度分布的圖像。
距離變換（distance transform），給出圖像中的每個像素與某個圖像子集的距離。
圖像閾值化，將灰度圖像轉為二值圖像。
數學形態學（morphology），是以形態為基礎對二值圖像進行分析的數學工具，基本思想是用具有一定形態的結構元素去度量和提取圖像中的對應形狀，以達到圖像分析和識別的目的。
連通區域檢測，得到連通區域的標記。

接著，我們引入了圖像卷積的概念，這是一種在數字圖像處理中被廣泛使用的方法。利用傅里葉變換的卷積定理可以實現卷積與 FFT 的互相轉化。既然卷積與傅里葉變換可以互化，那麼將圖像與某些特定的卷積核（kernel）進行卷積（或將這些矩陣看做卷積掩膜， mask），就可以實現濾波的效果。我們把微分運算元（包括Roberts運算元、Prewitt運算元、Sobel運算元）和拉普拉斯運算元寫成了卷積核的形式。我們著重介紹了以下幾種濾波方法：

均值濾波：通過圖像的局部鄰域平均完成濾波
中值濾波：用像素點鄰域灰度值的中值來代替該像素點的灰度值
高斯濾波：基於高斯函數的形狀形成卷積掩模
箱式濾波：每個元素的值是該像素鄰域內的像素和

圖像金字塔就是為了以多解析度來解釋圖像而誕生的一種簡單有效的方法。一幅圖像的金字塔，是以一系列以金字塔形狀排列的解析度初步降低的圖像的集合。金字塔的底部是待處理圖像的高解析度的表示，而頂部是低解析度的表示。

區域的分裂過程對應於金字塔的降採樣（pyramid-down）過程，即自上而下（top-down）的採樣，可以使用差分高斯運算元（DoG）作為掩膜來實現，稱為高斯金字塔。
區域的歸併過程對應於金字塔的升採樣（pyramid-up）過程，即自下而上（bottom-up）的採樣，可以使用差分拉普拉斯運算元作為掩膜來實現，稱為拉普拉斯金字塔。拉普拉斯金字塔是高斯金字塔的逆過程，作用是重建高斯金字塔。
區域的降採樣對第i層圖像金字塔進行高斯內核卷積，將所有偶數行和列去除，得到的圖像即為第i+1層的圖像，顯而易見，結果圖像只有原圖的四分之一，向下取樣會逐漸丟失圖像的信息，縮小圖像。
區域的升採樣將圖像在每個方向擴大為原來的兩倍，新增的行和列以0填充，使用先前同樣的內核(乘以4)與放大後的圖像卷積，獲得「新增像素」的近似值，得到的圖像即為放大後的圖像，但是與原來的圖像相比會發覺比較模糊，因為在縮放的過程中已經丟失了一些信息，如果想在縮小和放大整個過程中減少信息的丟失，就需要與原圖進行比較。

圖像分割，常用的方法是分水嶺演算法（watershed）。

目標跟蹤：背景減除、粒子濾波、meanshift

背景減除（background subscription）目的在於區分場景背景和場景運動，從而進行運動檢測。基於混合高斯模型的背景建模將圖像中的每個像素看成是從混合高斯分布樣本中採樣得到的隨機變數。

在卡爾曼濾波中，我們建立的模型

$egin{cases} X_t=A_{t,t-1}X_{t-1}+W_t\ Z_t=C_tX_t+V_t end{cases}$

具有這樣兩條性質

[狀態量的馬爾可夫性] k時刻狀態量只與k-1時刻的狀態量有關
[觀測量的條件獨立性] k時刻觀測值只與k時刻狀態值有關

如果我們把位置和觀測建模為概率分布，即

$egin{cases} x_k sim p(x_k|x_{1:k-1},y_{1:k-1})\ y_k sim p(y_k|x_{1:k},y_{1:k-1}) end{cases}$

根據貝葉斯定理

$p(x_{k}|y_{1:k})=frac{p(y_{1:k}|x_{k})p(x_{k})}{p(y_{1:k})}$

這種方法也就是所謂的批處理貝葉斯方法。但是這種方法每次都要拿所有的測量值來重新計算概率分布，對於計算機是個沉重的負擔。因此，有了改進的基於遞歸的貝葉斯濾波方法

$p(x_k|y_{1:k-1})=int{p(x_k|x_{k-1})p(x_{k-1}|y_{1:k-1})} dx_{k-1}$

其中 $p(x_k|x_{k-1})$ 代表了狀態由k-1時刻到k時刻的轉移概率。利用觀測值進行更新

$p(x_k|y_{1:k})=frac{p(y_k|x_k)p(x_k|y_{1:k-1})}{int{p(y_k|x_k)p(x_k|y_{1:k-1})} dx_k}$

這個後驗分布，將作為估計k+1時刻位置的先驗分布，從而開始下一輪的遞歸解算。

粒子濾波的結構實際上就是加入蒙特卡羅方法（Monte Carlo method，即以某時間出現的頻率來指代該事件的概率）的卡爾曼濾波，該方法的基本思想是用一組樣本（或稱粒子）來近似表示系統的後驗概率分布，然後使用這一近似的表示來估計非線性系統的狀態。採用此思想，在濾波過程中粒子濾波可以處理任意形式的概率，而不像卡爾曼濾波只能處理線性高斯分布的概率問題。粒子濾波的一大優勢也在於此。

粒子濾波的三個重要步驟為

[粒子採樣] 從建議分布中抽取一組粒子
[粒子加權] 根據觀測概率分布，重要性分布以及貝葉斯公式計算每個粒子的權值
[估計輸出] 估計輸出系統狀態的均值協方差等

此外，為了應對粒子退化現象，還採用了重採樣等策略。

Mean shift演算法中，特徵空間中數據最密集的地方，對應於概率密度最大的地方，且概率密度的質心就可以被視為是概率密度函數的局部最優值，也就是要求的聚類中心。

對於每一個樣本點，計算以它為中心的某個範圍內所有樣本點的均值，作為新的中心（這就是shift，即圓心的漂移），移動直至收斂。這樣每一輪迭代，中心都會向數據更密集的地方移動，直到最後穩定收斂到樣本的「質心」。

將meanshift演算法擴展到連續圖像序列，就是camshift演算法。它將視頻的所有幀做meanshift運算，並將上一幀的結果，即搜索窗的大小和中心，作為下一幀meanshift演算法搜索窗的初始值；如此迭代下去，就可以實現對目標的跟蹤。

特徵檢測及其應用

Canny的邊緣最優化準則

[檢測標準（最大信噪比準則）] 要有好的檢測結果，不丟失，也不應有虛假的邊緣；
[定位標準（最優過零點準則）] 實際邊緣位置與檢測到的邊緣位置間的偏差最小；
[單響應標準（多峰值響應準則）] 對實際上的同一邊緣要有低的響應次數。

Canny以一維形式為例，給出了三條準則的數學表達式，將尋找最優濾波器的問題轉換為泛函的約束優化問題。Canny邊緣檢測通過閾值化確定突出的邊緣，若濾波結果超出或低於閾值，則雜訊引起的單邊緣虛假響應會使檢測出的邊緣不連續，Canny通過滯後閾值化處理解決該問題：

圖像的響應大於高閾值，它一定是邊緣
圖像的響應小於低閾值，它一定不是邊緣
圖像的響應在高低閾值之間，如果它與大於高閾值的像素相連，它也可能是邊緣
高、低閾值可根據對信噪比的估計確定

此外，我們還介紹了邊緣圖像閾值化方法、有方向邊緣數據的非最大抑制、邊緣檢測運算元輸出的滯後過濾、邊緣鬆弛等操作；並介紹了內邊界、外邊界和擴展邊界跟蹤演算法。

Hough變換的基本原理是基於點-線的對偶性質，如果我們設直線的法向量模值為ρ，相角為θ，那麼直線上的任一點(x,y)滿足ρ=x cosθ+y sinθ，如果以任意x,y為參數，θ為自變數，ρ為因變數，那麼上式就是周期為2π的正弦曲線簇。

曲線簇有且只有唯一交點，其對應的ρ, θ值即為直線的ρ, θ參數。由於三角函數的周期性，我們對θ進行細分，將參數空間細分為m×n個累加單元，初始化累加器矩陣Q，例如考慮ρ ∈[-20,20]且為整數，則m=41；以10°為步長，則n=36；對每一組ρ, θ值，遍歷圖像上的點並進行「投票」，就能將直線檢測出來。

此外，我們還討論了Hough變換檢測多條直線、檢測圓、檢測圓錐曲線，以及基於概率的Hough變換等多種推廣形式。

參考文獻

主要參考書目

Hartley,R. Zisserman,A. Multiple View Geometry in Computer Vision. Cambridge University Press.2002

（中文版：Hartley,R. Zisserman,A. 計算機視覺中的多視圖幾何[M]. 安徽大學出版社, 2002.）

Forsyth,D. Ponce,J. Computer Vision: A Modern Approach. (Second Version)2011

（中文版：Forsyth,D. Ponce,J. 計算機視覺:一種現代方法[M]. 電子工業出版社, 2012.）

A.Mordvintsev, K.Abid: OpenCV Python Tutorial, opencv.org, 2017, HTML版見 http://docs.opencv.org/3.0-beta/doc/py_tutorials/py_tutorials.html

Solem J.E.: Programming Computer Vision with Python, OReilly, 2012

（中文版：Solem J.E. Python計算機視覺編程[M]. 人民郵電出版社, 2014.）

高翔，張濤等.視覺SLAM十四講：從理論到實踐[M].電子工業出版社.2017

參考論文

以下列出了我們上面提到的一些經典演算法的相關論文。

張正友平面標定法 Zhang, Zhengyou. "A flexible new technique for camera calibration." Tpami 22.11(2000):1330-1334.

Levenburg-Marquardt演算法 Marquardt, Donald W. "An Algorithm for Least Square Estimation of Non-Linear Parameters." Journal of the Society for Industrial & Applied Mathematics 11.2(1963):431-441.

Moravec角點檢測 H. P. Moravec, Towards Automatic Visual Obstacle Avoidance, International Joint Conference on Artificial Intelligence, 1977, p. 584

Harris角點檢測 Harris, C. J. "A combined corner and edge detector." Proc Alvey Vision Conf 1988.3(1988):147-151.

亞像素級角點檢測 Shi, Jianbo. "Good Feature to Track." IEEE Conference on Computer Vision and Pattern Recognition 1994.

SIFT特徵 Lowe, David G. "Distinctive Image Features from Scale-Invariant Keypoints." International Journal of Computer Vision 60.2(2004):91-110.

Lowe, David G. "Object Recognition from Local Scale-Invariant Features." iccv IEEE Computer Society, 1999:1150.

SURF特徵 Bay, Herbert, T. Tuytelaars, and L. V. Gool. "SURF: speeded up robust features." European Conference on Computer Vision Springer-Verlag, 2006:404-417.

FAST特徵 Rosten, Edward, and T. Drummond. "Machine learning for high-speed corner detection." European Conference on Computer Vision Springer-Verlag, 2006:430-443.

BRIEF特徵 Calonder, Michael, et al. "BRIEF: binary robust independent elementary features." European Conference on Computer Vision 2010:778-792.

ORB特徵 Rublee, Ethan, et al. "ORB: An efficient alternative to SIFT or SURF." IEEE International Conference on Computer Vision IEEE, 2012:2564-2571.

Lucas-Kanade演算法 Lucas, Bruce D., and T. Kanade. "An iterative image registration technique with an application to stereo vision." International Joint Conference on Artificial Intelligence Morgan Kaufmann Publishers Inc. 1981:674-679.

Farneback演算法 Farneback, Gunnar. "Two-frame motion estimation based on polynomial expansion." Scandinavian Conference on Image Analysis Springer-Verlag, 2003:363-370.

Kalman濾波（原論文） Kalman, R. E. "A New Approach to Linear Filtering and Prediction Problems." Journal of Basic Engineering Transactions 82(1960):35-45.

Kalman濾波（綜述，包括對EKF的介紹） Welch, G. "An introduction to the Kalman filter." Course Notes of Acm Siggraph 8.7(1995):127-132.

UKF（無跡Kalman濾波） Merwe, R. Van Der, and E. A. Wan. "The square-root unscented Kalman filter for state and parameter-estimation." IEEE International Conference on Acoustics, Speech, and Signal Processing, 2001. Proceedings IEEE, 2002:3461-3464 vol.6.

對極幾何（綜述） Zhang, Zhengyou. "Determining the Epipolar Geometry and its Uncertainty: A Review." International Journal of Computer Vision 27.2(1998):161-195.

八點法 Hartley, Richard I. "In Defense of the Eight-Point Algorithm." IEEE Pami 19.6(1997):580-593.

RANSAC演算法 Fischler, Martin A., and R. C. Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. ACM, 1981.

光束平差法 Triggs, Bill, et al. "Bundle Adjustment — A Modern Synthesis." International Workshop on Vision Algorithms: Theory and Practice Springer-Verlag, 1999:298-372.

ROF降噪 Rudin, Leonid I., S. Osher, and E. Fatemi. "Nonlinear total variation based noise removal algorithms." Eleventh International Conference of the Center for Nonlinear Studies on Experimental Mathematics : Computational Issues in Nonlinear Science: Computational Issues in Nonlinear Science Elsevier North-Holland, Inc. 1992:259-268.

Meanshift演算法 Comaniciu, D., and P. Meer. "Mean Shift: A Robust Approach Toward Feature Space Analysis." IEEE Transactions on Pattern Analysis and Machine Intelligence 2002:603--619.

Cheng, Yizong. "Mean Shift, Mode Seeking, and Clustering." IEEE Trans.pattern.anal.mach.intell 17.8(1995):790-799.

Camshift演算法 Allen, John G, R. Y. D. Xu, and J. S. Jin. "Object tracking using CamShift algorithm and multiple quantized feature spaces." The Workshop on Visual Information Processing Australian Computer Society, Inc. 2004:3-7.

Canny邊緣檢測 Canny, J. A Computational Approach to Edge Detection. IEEE Computer Society, 1986.

Hough變換 Duda, R., and P. Hart. "Using the Hough transforms to detect lines and curves in pictures." Commun. ACM 1972:11-15.

HOG特徵 Dalal, N., and B. Triggs. "Histograms of oriented gradients for human detection." IEEE Computer Society Conference on Computer Vision & Pattern Recognition IEEE Computer Society, 2005:886-893.