Embedded Files
目標：了解Harris corner detector
1. Harris corner detector的數學原理
2. Harris corner detector的演算法
3. 特性
Harris corner detector的數學原理
在介紹Harris corner detector之前，先了解一下corner detector。
Corner detector：
是電腦視覺中用來提取特徵以及推測圖像內容的一種方法。找到角點(corner point,兩條邊的交點形成一個角點)，是圖像中具有代表性以及穩健性的點，也就是角點能夠在有噪聲干擾的情況下也能穩定的被定位，並對圖像進行局部分析，所以不管圖像拍攝時採用了什麼視角、尺度和方位，理想情況下同一個場景或目標位置都要檢測到特徵點。Corner detect的應用很廣，常用在運動檢測、跟蹤、馬賽克（image mosaicing）、全景圖縫合（panorama stiching）、三維建模以及物體識別中。Corner detect在圖像上最簡單的做法是利用相關性，但這樣的作法需要耗費大量的運算資源以及得到的結果可能只是局部最大值，因此有個常見的作法是使用Harris和Stephens所提出的經由改善Moravec corner detector 的結果。
corner point
corner detection
由於Harris corner detector是改善Moravec corner detector，所以先了解Moravec corner detector。
Moravec corner detector：
是最早(1980)使用來做corner detection的做法，定義所謂的「角」就是那些自我相似程度低的點。演算法檢查圖像中所有的像素，觀察在所有方向上圍繞一個像素移動的子圖像是否發生顯著變化。如果是這種情況，則所考慮的像素是一個角。
(左)平坦區域，子圖像（紅色框）的變化微小不會引起任何變化。
(中)在輪廓上，子圖像（紅色框）只有一個方向的變化。
(右)在一個拐角處，子圖像（紅色框）各個方向都有明顯的變化。
從數學上來看，通常是將兩個範圍的對應點計算誤差的平方和(SSD: Sum of Squared differences) 。
變化的特徵在於每個像素(x,y)圖像的E(u,v)它表示偏移量的子圖像之間的差異(u,v)
u和v表示四個方向的偏移量：(u,v)∈{(1,0),(1,1),(0,1),(−1,1)}
w(x,y)是圍繞像素的矩形窗口
演算法找出整個圖像的局部最大值(局部最不相似的點)，這些局部最大值就很有可能是要偵測到的「角」。
Moravec corner detector有幾個局限性:
w是一個binary window，因此detector認為窗口中的所有像素具有相同的權重。當圖像中的噪聲很高時，可能會導致錯誤的角點檢測。
只考慮四個方向。
只考慮最小的E。
由於這些原因，Harris & Stephens 提出了一種detector來克服這些限制。
Harris corner detector：
廣泛運用在電腦視覺的演算法，主要用於從影像中找出代表邊角的特徵點。Harris & Stephens改善了Moravec corner detector(1988)，他們直接考慮每個像素沿著特定方向處的像素的SSD，而不是使用與周圍像素範圍的SSD。與Moravec corner detector相比，不是對局部小塊區域作45度角移動，而是考量了方向性值直接算出邊角的微分值，這個方法在當時已被證明可以更準確地去分辨出邊角。
從數學上來看，把window用高斯做計算，避免高雜訊的影響。
為了不局限於最初的四個方向，將Moravec corner detector擴展到所有方向，對移位後的子圖像進行二維泰勒展開。
因為higher order terms 很小，可以忽略不計因此可以得到：
將上式帶回E(u,v)，可以得到：
又可以將E(u,v)寫成：
M是結構張量，是從函數的梯度導出的矩陣。總結了一個點的指定鄰域中梯度的主要方向，以及這些方向連貫的程度。
通過求解 M 的特徵向量，可以獲得 SSD 最大和最小增量的方向。λ 1 和λ 2 (橢圓的長短軸)是M的特徵值，特徵值的大小決定一個區域是角、邊還是平面。
Harris response ：
Harris response ：
(k:由經驗所訂出來的常數，k∈[0.04,0.06])
當|R| 很小，在 λ1 和 λ2 很小時，該區域是平坦的(flat)。
當 R<0， λ1>>λ2 或λ1<<λ2，該區域是邊緣(edge)。
當 R 較大時， λ1 和 λ2 較大且 λ1∼λ2 時，該區域是角點(corner)。
Harris corner detector的演算法
1. 彩色影像轉換成灰階影像
如果輸入是一張彩色影像，第一步便是轉換成灰階影像，可以加快處理速度 。
2. 空間微分的計算
計算整張圖的梯度值，即每個像素的 x 、 y 梯度值(Ix、Iy)，可以用 Sobel。
3. 建構結構張量
計算結構張量，使用Ix與Iy計算M(在Harris corner detector的數學原理中有提到)。
4. 計算哈里斯響應
計算結構張量矩陣的最小的特徵值，在Harris corner detector的數學原理中有提到。
5. 非極大值抑制
由於只靠前面的步驟選出的特徵點很可能會在一小塊區域有很多個，希望能在局部區域選出值最大的，因此會設定各個擁有局部最大值的特徵點的距離不能太接近，如此便可以有效選出比較分散在整張圖的特徵點。
特性
Harris Corner Detector 基本上邊角的特性不會受到Scale、Rotational以及Affine的影響。
Scale invariance
如右圖所示，當原圖被縮小時，在檢測窗口尺寸不變的前提下，在窗口內所包含圖像的內容是完全不同的。原圖像可能被檢測為邊緣或曲線，而縮小圖像則可能被檢測為一個角點。
Harris corner detector有Scale invariance的特性，局部影像特徵的描述與偵測可以幫助辨識物體 。
Rotational invariance
Harris corner detector使用的是角點附近的區域灰度二階矩矩陣。而二階矩矩陣可以表示成一個橢圓，橢圓的長短軸正是二階矩矩陣特徵值平方根的倒數。當特徵橢圓轉動時，特徵值並不發生變化，所以判斷角點響應值 R 也不發生變化，因此 Harris corner detector具有Rotational invariance。
Affine invariance
給定一組多項式，設I是由這組多項式的係數所決定的函數，如果經過仿射變換G作用後函數值I不變，就稱I這組多項式在變換群G作用下affine invariance。整個圖像的像素值都進行仿射變換後，角點是affine invariance。且在 Harris corner dector 使用了微分運算，所以 Harris corner dector對於密度與亮度的改變不容易受影響。
(左圖)亮度改變(I=I+b)
(右圖)對比度改變(I=aI)
Reference
Computer Vision: Algorithms and Applications, 2nd ed,Richard Szeliski,2022
Microsoft PowerPoint - lec04_feature.ppt,Yung-Yu Chuang, Mar 20,2007,https://www.csie.ntu.edu.tw/~cyy/courses/vfx/07spring/lectures/handouts/lec04_feature_4up.pdf
Corner detection,Basics of Image Processing,Vincent Mazet (Université de Strasbourg), 2020-2023,https://vincmazet.github.io/bip/detection/corners.html
Moravec corner detection,Mahendra Singh Thapa,Feb 18, 2022,https://mahendrathapa.medium.com/moravec-corner-detector-5191f1c04b30
哈里斯邊角偵測,維基百科，自由的百科全書,Aug 21,2022,https://zh.wikipedia.org/zh-tw/%E5%93%88%E9%87%8C%E6%96%AF%E9%82%8A%E8%A7%92%E5%81%B5%E6%B8%AC
Introduction to Harris Corner Detector,Deepanshu Tyagi,Mar 16, 2019,https://medium.com/data-breach/introduction-to-harris-corner-detector-32a88850b3f6
角檢測,維基百科，自由的百科全書,Oct 30,2021,https://zh.wikipedia.org/wiki/%E8%A7%92%E6%A3%80%E6%B5%8B
【图像处理】（3）harris corner detection(角点检测),mjiansun,Aug 15,2022,https://blog.csdn.net/u013066730/article/details/126001684
仿射不變量,百度百科,Apr 2,2022,https://baike.baidu.hk/item/%E4%BB%BF%E5%B0%84%E4%B8%8D%E8%AE%8A%E9%87%8F/18878768?lang=zh_HK
Page updated
Google Sites
Report abuse