Reading 1
Harris Corner Detector
Goal:學習並理解 Harris corner detector 的算法原理和演算步驟以及其特性。
Moravec corner detector
簡介與原理
這是最早使用來做角檢測的做法，他首先定義所謂的「角」就是那些自我相似程度低的點。這個演算法檢查所有圖像中的像素，並考慮以該像素為中心點的一片範圍，該範圍與他周圍覆蓋最大的另一個範圍的相似度做為參考，而相似度通常是將兩個範圍的對應點計算誤差的平方和(SSD: Sum of Squared differences) ，越小代表相似度越高。而角點則是計算SSD後與其周圍相似度都差距非常之大的點，是為局部最大值(最不相似)的點。
從左到右：
在平坦區域，子圖像（紅色）的微小變化不會引起任何變化。
在輪廓上，我們只觀察到一個方向的變化 。
在一個拐角處，各個方向都有明顯的變化。
數學表示
x,y 表示四個方向的偏移量(1,0),(1,1),(0,1),(-1,1)。
Wm,n是像素(m,n)周圍的矩形視窗。
f(u+x,v+y)-f(u,v)代表移動前後的差異。
流程與演算
選取一塊區域計算其SSD，接著將區域向偏移量移動，並再次計算SSD。
與先前計算出來之值做比較，對整張影像演算完成後，將SSD值相對較大的地方取出，該區域值為圖片角點。
Moravec detector 示意圖。
缺點
計算成本較高，因為它需要對每個像素進行8個方向的運算。
在存在圖像縮放或旋轉時，Maravec檢測器可能產生一些虛假的角點檢測，因為該算法使用的是基於圓周而不是高斯的kernel。
Harris corner detector
簡介與原理
該算法是由Chris Harris和Mike Stephens在1988年提出，是一種基於灰度強度變化的局部特徵檢測算法，是為Moravec corner detector的改良版本 。
主要思想是通過計算圖像的局部區域在不同方向上的灰度變化來判斷其是否是角點。首先計算圖像的梯度，在此基礎上計算出每個像素在不同方向上的梯度值，進而得到該像素的M矩陣，M矩陣可以描述該像素周圍的灰度變化情況，再根據M矩陣的特徵值大小判斷該像素是否為角點，具體判斷方式可以使用角點響應函數，該函數利用M矩陣的特徵值來計算該像素的角點響應值，從而進一步判斷是否為角點。
數學式
區域誤差平方值(SSD)計算。
Sum of Squared Difference（區域誤差平方值SSD）是一種影像相似度度量方法，通常用於影像比對和配準。在影像配準中，目標是找到兩個影像之間的平移、旋轉、縮放或透視變換，使它們在某種度量下最相似，通過計算兩個影像之間每個像素值的差的平方和，來衡量它們之間的相似度。
為了將Moravec檢測器擴展到所有方向，不局限於最初的四個方向，對移位後的子圖像進行泰勒級數展開。
展開後忽略極小值寫為此表達式。
所以可以將整體數學式表達為此。
原式通過矩陣整理後可改寫為矩陣形式。
M矩陣其實就是Harris矩陣，可以透過分析M的特徵值來辨識是否為角點。
M會擁有兩個特徵值 λ1和 λ2, 也就是橢圓的長短軸，所以:
當兩特徵值皆約為0，則代表像素位置只是一個普通的點。
當一特徵值約為0，而另一特徵值是一個大的正數，則代表像素位置在邊緣上。
當兩特徵值皆是大的正數，則代表像素位置是一個角點。
流程與演算法
1.計算 x 和 y 方向的梯度 Ix ,Iy。(Spatial derivative calculation)
2.使用計算出的梯度 Ix ,Iy 計算H矩陣。(Structure tensor setup)
3.計算Harris response。(Harris response calculation)
使用近似值算式來計算結構張量矩陣的最小特徵值。
使用經驗參數 k 帶入公式中處理，約在0.02到0.2之間 。
4.非最大值抑制 (Non-maximum suppression)
為了避免同一個角落檢測到多個重疊的角點，當在一個區域中檢測到多個候選角點時，只有擁有最大響應值的角點被保留，其它角點被抑制掉，這樣可以保證每個角落只有一個角點被檢測到，減少了冗餘和重複的角點檢測。
特性
尺度不變性 scale invariance
當圖片被放大縮小後，相對像素點的內容是完全不一樣的，同樣的一個曲線可能在放大後被辨識成邊緣，而縮小後被辨識成一個角點，因此 Harris corner Detector 是不符合尺度不變性的，理論上應能透過擴大局部包含範圍來解決尺度多樣性問題。
旋轉不變性 rotational invariance
Harris矩陣可以寫成橢圓的二次函式，而橢圓在旋轉時，其長軸和短軸是不變的，也就是說其特徵值不會因此改變，所以 Harris response 的值也不會改變，因此 Harris corner Detector 是符合旋轉不變性的。
仿射不變性 affine invariance
Harris 角點檢測算子對亮度和對比度的變化不太敏感，因為在進行 Harris 角點檢測時，使用了微分算子對圖像進行微分運算，而微分運算對圖像密度的拉升或收縮和對亮度的抬高或下降不太敏感。
但如圖的 I+b 以及 a*I 會導致最後結果不同，所以 Harris corner Detector 是只有部分符合仿射不變性的，這也跟閥值的設定有關。
