time:2015年10月09日 星期五 23時11分58秒
# opencv筆記6：角點檢測
update：從角點檢測，學習圖像的特征，這是后續圖像跟蹤、圖像匹配的基礎。
角點檢測是什么鬼？前面一篇學習筆記是各種模板操作，是圖像增強技術。
那么我節寫來應該繼續找下有沒有別的圖像增強技術。
但是，我對增強還不是特別理解。
圖像增強：劃定ROI區域，然后想方設法將感興趣的特征有選擇的突出。注意，這可是不去考慮圖像質量下降的原因的。
圖像恢復：針對圖像降質的原因，設法去補償降質因素，從而使改善后的圖像盡可能的逼近原始圖像。
好吧，圖像恢復目前所了解的，就是09年CVPR的best paper那篇，講圖像去霧的。先不管，我先看看圖像增強的其他方法。
頻域增強：上一篇筆記中提到的什么高頻分量、低頻分量，說的就是：圖像經過傅立葉變換后的頻譜的高低。高頻譜對應著圖像中灰度值變化大的地方，比如圖像邊緣、噪聲點；低頻譜對應著圖像中灰度值穩定、變化很小的地方。是哪些地方？不是邊緣、噪聲點的地方。
正題，開始看角點檢測了。因為opencv的文檔中有這部分的內容，現在自己也不了解它具體是怎么玩的，所以要看看。
什么是角點(what)
百度百科：角點就是極值點，即在某方面屬性特別突出的點。
淺墨博主：要了解角點，先看興趣點。興趣點包括：邊緣、角點、斑點(blobs,即感興趣區域)。角點位于兩條邊緣的交點處，代表了兩個邊緣變化的方向上的點，所以它們是可以精確定位的二維特征，其圖像梯度有很高的變化。
opencv官方文檔：計算機視覺中，我們常常需要再不同環境框架下找到匹配點。我們說的匹配點，通常是指能夠容易識別到的特征點(characteristics)，也叫features。那么一個feature應該包含哪些characteristic呢？一定是能被獨一無二地識別的那些。（PS 翻譯一下：feature就是獨一無二的屬性。我們要找尋feature）。
圖像特征包括：邊緣(edges) 角點（corners，也叫interest points） blobs（淺墨翻譯成斑點，也有人翻譯成粒子。反正，這東西就是比corners更大一些的東西。也叫regions of interests，感興趣區域）。角點是兩個edge交界的地方，表示兩條edge變化的方向。
角點的特點？應用？(why)
角點是特征點，可以理解為正張圖片中的“精英分子”，雖然本身數量不多，但是帶有圖像的大量信息。（當然，除了角點，邊緣、粒子也都是“精英分子”）顯然，若干圖像之間的操作，比如匹配、運動檢測、視頻跟蹤、三維建模中會被用到。
opencv中cornerHarris()函數用于角點檢測。
角點檢測的方法(how)
百度搜到的一篇文章：小魏的修行路【OpenCV】角點檢測：Harris角點及Shi-Tomasi角點檢測，內容還算豐富，不過人家是原創的。如果是我去寫一篇原創性的呢？因為總有要自己去寫原創性blog的時候，不如現在就去做，先不看這篇文章的內容，自行搜索一篇好的綜述類文章然后消化吸收整理出結果，再和她的文章對比下。
A comprehensive review of current local features for computer vision
最早是Moravec的角點檢測，后來被Harris和Stephens的Harris算法改進，再后是Lowe的SIFT算法，以及一系列的保持放射不變性的方法，比如MSER。
Moravec角點檢測
最早的角點檢測法，認為角點是“局部區域中'最小灰度變化'最大的點”。
步驟：（1）每個點，右邊、右下、下方、左下四個方向的patch（比如3x3模板框）分別和本像素點對應的patch，做SSD（對應點做差，再求平方和，還要乘以權重函數w），最小的SSD值就是“興趣值”S。SSD值代表了灰度變化，SSD越小，當前patch和鄰近patch越相似；每個點的SSD都拿出來比較，SSD是極大值的，說明它在自己鄰域內灰度變化最大，角點、邊緣處的灰度變化才應當大，所以這樣的點是興趣點。
設需要計算的點為I(i,j)
用(x,y)遍歷其鄰域（比如3x3）內的點
(u,v)屬于{(1,0),(1,1),(0,1),(-1,1)}，表示四個方向
對每個(u,v)計算：SSD(u,v)=sigma(x,y){w(x,y)*[I(x+u,y+v)-I(x,y)]^2}
其中w(x,y)表示權重，若(x+u,y+v)落在原有像素點的patch內，則w(x,y)=1，否則為0
興趣值S=min{SSD}（2）每個點都算出了興趣值后，尋找興趣值的極大指點。這些點就是“興趣點”。
缺點
只考慮了相隔45度的四個方向，其他方向沒有考慮，明顯不公平嘛，其他方向的興趣點不太容易檢測到。
權值w(x,y)明顯可以換成高斯函數什么的
注意：檢測到邊緣點，不能說是缺點。因為此算法本身定義的“興趣點”就是角點和邊緣點。
Harris角點檢測
由Harris和Stephens提出，是Moravec算法的改進。
步驟
1）每個點計算Harris矩陣A
S(x,y)=sigma(u,v)[w(u,v) (I(u+x,v+y)-I(u,v))^2]
由泰勒展開有近似等式：I(u+x,v+y)=I(u,v)+I_x(u,v)x + I_y(u,v)y
帶入S(x,y)有S(x,y)=sigma(u,v)[w(u,v)(I_x(u,v)x+I_y(u,v)^2]
這里權值w(u,v)使用了圓形的模板，類似于高斯低通濾波使用的模板，而不是原來類似于理想低通濾波的0-1函數模板
整理為S(x,y)=(x y)A(x y)^T的形式
其中A=[(I_x)^2*w (I_x·I_y)*w]
[(I_x·I_y)*w (I_y)^2*w], *表示卷積2）計算A矩陣的特征值l1、l2
3）用l1、l2判斷
l1約等于0，l2約等于0：則當前點處于平穩區(uniform intensity region)
l1約等于0，l2遠大于0：則當前點處于邊緣上
l1,l2都遠大于0：當前點是角點改進
實際計算特征值時，涉及平方根計算，比較耗時，有人提出簡化算法
M = l1·l2-k(l1+l2)^2
= |A|-k·tr^2(A)
k是經驗值，和圖像尺寸(scale)相關對應的判斷為：
M約等于0（可正可負）：當前點處于平穩區
M小于0：當前點處于邊緣
M大于0：當前點處于角落，為角點評價
此法檢測到的角點，具有旋轉不變性
缺點是，不具備尺度不變性，只能在預設尺度上找到各方向大梯度值的區域
代碼
還是到opencv中試一試吧。注意載入的圖像應當是灰度圖像。
#include <iostream>
#include <opencv2/opencv.hpp>
using namespace std;
using namespace cv;
int main(){
//【1】載入原圖像
//【2】調用harris角點檢測
//【3】閾值操作，得到二值圖像
//【4】顯示結果
//【1】載入原圖像
Mat srcImage = imread("/home/chris/workspace/clion/luca.png", 0);
Mat cornerStrength, dstImage;
//【2】調用harris角點檢測
cornerHarris(srcImage, cornerStrength, 2, 3, 0.01);
//【3】閾值操作，得到二值圖像
threshold(cornerStrength, dstImage, 0.00001, 255, THRESH_BINARY);
//【4】顯示結果
imshow("原圖", srcImage);
imshow("harris角點檢測后的二值效果", dstImage);
waitKey(0);
destroyAllWindows();
return 0;
}SUSAN/FAST角點檢測
SUSAN算法->FAST算法
SUSAN(Smallest UnivalueSegment AssimilatingNucleus)算法認為：與每一圖像點相關的局部區域具有相同的亮度。如果某一窗口區域內的每一像元亮度值與該窗口中心的像元亮度值相同或相似，這一窗口區域將被稱之為“USAN”。計算圖像每一像元的“USAN”，為我們提供了是否有邊緣的方法。位于邊緣上的像元的“USAN”較小，位于角點上的像元的“USAN”更小。因此，我們僅需尋找最小的“USAN”，就可確定角點。該方法由于不需要計算圖像灰度差，因此，具有很強的抗噪聲的能力。
FAST（Features from Accelerated Segment Test）算法由Edward Rosten 和 Tom Drummond在他們2006年的論文“Machine learning for high-speed corner detection”（在2010年再次被修訂）中被提出。
看看opencv是怎么實現的：
若某像素點圓形鄰域圓周上有3/4的點和該像素點不同（編程時不超過某閾值th），則認為該點就是候選角點。opencv更極端，選用半徑為3的圓周上（上下左右）四個點，若超過三個點和該像素點不同，則該點為候選角點。
和Harris算法類似，該算法需要非極大值抑制。
代碼：
#include <iostream>
#include <vector>
#include <opencv2/opencv.hpp>
using namespace std;
using namespace cv;
int main(){
//【1】載入原圖像
//【2】調用快速特征檢測
//【3】描繪角點
//【4】顯示結果
//【1】載入原圖像
Mat srcImage = imread("/home/chris/workspace/clion/luca.png", 0);
Mat cornerStrength, dstImage=srcImage.clone();
//【2】調用快速特征檢測
FastFeatureDetector fast(30, true);//30表示閾值,true表示抑制非極大值
vector<KeyPoint> keypoints;
fast.detect(srcImage, keypoints);
//【3】描繪角點
drawKeypoints(srcImage, keypoints, dstImage, Scalar::all(255), DrawMatchesFlags::DRAW_OVER_OUTIMG);
//【4】顯示結果
imshow("原圖", srcImage);
imshow("harris角點檢測后的二值效果", dstImage);
waitKey(0);
destroyAllWindows();
return 0;
}下一步
角點只是特征中的一種，邊緣也是很好用的特征。準備看下SIFT和SURF的原理。
提到SIFT就要考慮尺度(Scale)的問題，不同scale的圖像，怎樣使同一個算法得到基本相同的效果？差別肯定是有的，但要盡量小，就涉及到兩個步驟：
1）首先在粗尺度上進行特征（結構）檢測
2）然后再在細尺度上進行精確定位
需要看一下圖像金字塔
其他坑
還有些邊邊角角的東西沒有串起來，比如DoG角點檢測算法，LoG算法。
ref
墨色光暈的專欄角點檢測的幾種基本方法
文章列表
留言列表
