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
墨色光晕的专栏角点检测的几种基本方法