CV-2020-笔记:02 特征(Features) 上
文章目录
CV-2020-笔记:02 特征(Features)--上
计算机视觉课程学习笔记
“The question of whether computers can think is like the question of whether submarines can swin.”—— Edsger W. Dijkstra
1. 特征概览
特征点
-
特征的形式
- 特征点、局部关键点、感兴趣的点
- 整块区域
- 边缘图像
- 几何信息
-
图像局部特征
- 图像局部特征是基础,但并非全部
-
特征检测方法
-
两种技术路线
- 跟踪(track):局部搜索(适合画面变化不大,如视频连续画面)
- 独立考察,两两匹配(match)
-
四种独立步骤
- 特征检测(feature detection/extraction)
- 特征描述(feature description)
- 特征匹配(fearure match) / 特征跟踪(feature track)
-
自相关的方法 (Auto-Correlation)
- 问题:判断一个点是不是特征点(与周围其他点相差大)
-
建模
-
直观的建模
- 图像与其周边局部区域的相似性:
- $E_{WSSD}(u)=\sum_iw(x_i)[I_1(x_i+u)-I_0(x_i)]^2$
-
局部特征
- $E_{AC}({\Delta u})=\sum_iw(x_i)[I_0 (x_i+\Delta u)-I_0(x_i)]^2$
-
示例

-
泰勒级数展开
- $I_0(x_i+\Delta u)\approx \triangledown I_0(x_i)+\triangledown I_0(x_i)\cdot\Delta u$
$$ \begin{aligned} E_{AC}({\Delta u})&=\sum_iw(x_i)[I_0 (x_i+\Delta u)-I_0(x_i)]^2\\ &\approx \sum_iw(x_i)[I_0 (x_i)+\triangledown I_0(x_i)\cdot\Delta u-I_0(x_i)]^2\\ &=\sum_iw(x_i)[I_0 (x_i)\cdot\Delta u]^2\\ &=\Delta u^TA\Delta u\\ &\triangledown I_0(x_i)=(\frac{\partial I_0}{\partial x},\frac{\partial I_0}{\partial y})(x_i) \end{aligned} $$
- $A=w\times\begin{bmatrix}I_x^2\quad I_xI_y\\ I_xI_y\quad I_y^2\end{bmatrix}$
-
-
特征点的判断
- 设阈值,进行判断;
- 求矩阵的迹(trace);
-
基本特征提取的算法流程
- 将原始图像与高斯导数进行卷积,得到水平方向和垂直方向的导数$I_x$和$I_y$;
- 计算着图像对应这些梯度的外积;
- 用一个更大的高斯来对这些图像进行卷积;
- 用公式计算出标量度量;
- 找到某个阈值以上的局部极大值,并将其报告为检测到的特征点位置。
2. Harris Corner
基本观点
- 论文:C.Harris, M.Stephens, "A Combined Corner and Edge Detector". 1988
- 问题:寻找铰点
- 方法:通过滑窗寻找,在各个方向上梯度变化都很大的点
Moravec Corner Detector
- 图例
-
移动$[u,v]$的强度改变:$E(u,v)=\sum_{x,y}w(x,y)[I(x+u,y_v)-I(x,y)]^2$
- $w(x,y)$: 窗口函数,在窗内为1,反之为0(binary window function)
- $I(x+u,y+v)$:移动强度(shifted intensity)
- $I(x,y)$:原本强度
- $(u,v)=(1,0),(1,1),(0,1),(-1,1)$,在$\min\{E\}$寻找局部极值(local maxima)
-
Moravec的问题
- 四个方向的组合只能考虑45度的方向;
- 矩阵的差受像素的影响大 (Noisy due to a binary window function);
- 只有$E$的极小值被考虑到。
Harris Corner Detector
- Harris Corner detector在1988年被提出,来改进解决Moravec的问题。
-
解决方法:
-
使用高斯函数(Gaussian function)替代二分函数(binary function)
- $w(x,y)=\exp(-\frac{(x^2+y^2)}{2\sigma^2})$
-
把上下左右滑窗找极值转为用泰勒展式找梯度变换情况:
$$ \begin{aligned} E(u,v)&=\sum_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^2\\ &=\sum_{x,y}w(x,y)[I_xu+I_yv+O(u^2+v^2)]^2\\ E(u,v)&=Au^2+2Cuv+Bv^2\\ A&=\sum_{x,y}w(x,y)I_x^2(x,y)\\ B&=\sum_{x,y}w(x,y)I_y^2(x,y)\\ C&=\sum_{x,y}w(x,y)I_x(x,y)I_y(x,y)\\ E(u,v)&\approx[u,v]M\begin{bmatrix}u\\v\end{bmatrix}\\ M&=\sum_{x,y}w(x,y)\begin{bmatrix}I_x^2\quad I_xI_y\\I_xI_y\quad I_y^2\end{bmatrix} \end{aligned} $$
-
-
判断
- 边缘:$\lambda_2\gg\lambda_1$或$\lambda_1\gg\lambda_2$
- 铰点:$\lambda_1$和$\lambda_2$都很大,$E$在各个方向都增长
- 平滑:$\lambda_1$和$\lambda_2$都很小,$E$在各个方向都不变
- 度量方式:$R=\frac{\lambda_1\lambda_2}{\lambda_1+\lambda_2}=\frac{\det M}{Trace\ M}$
-
算法
- 寻找途中有较大边角相应函数值$R$的点($R>threshold$)
- 寻找$R$中的局部极值
-
示例

-
Harris Detector的特性
- $R$值具有旋转不变性
- $R$值具有部分的亮度变化不变性(平移不变,拉伸若超过阈值则会改变)
-
$R$值不具备尺度不变性(如弧线缩小,可能会被识别为铰点)
- 使用不同尺度多窗口检测?如何确认窗口大小?
3. 匹配(Matching)
特征匹配
-
特征点
- 鲁棒性、不变性 Invariant
- 独特性、唯一性 Distinctive
-
特征匹配
- 穷举搜索 Exhaustive Search
- 哈希映射 Hashing
- 最近邻技术 Nearest Neighbor Techniques:kd-树和其变体
-
应用
- 自动图像拼接
- 结果对应
- 物体识别
- 几何分析...
野点(outlier)
- 野点、异常点(outliers):未必是错的点,而是会对计算形成干扰的点
-
拒绝野点--NN
- 不比较全部的特征,而只比较那些有足够相似性的点
- $SSD(patch1, patch2)<threshold$
-
SSD
-
误差平方和算法(Sum of Squared Differences, SSD),也叫差方和算法
- $D(i,j)=\sum^M_{s=1}\sum^N_{t=1}[S(i+s-1,j+t-1)-T(s,t)]^2$
-
平均误差平方和算法(Mean Square Differences, MSD),也叫均方差算法
- $D(i,j)=\frac{1}{M\times N}\sum^M_{s=1}\sum^N_{t=1}[S(i+s-1,j+t-1)-T(s,t)]^2$
-
绝对误差和算法(Sum of Absolute Differences, SAD)
- $D(i,j)=\sum^M_{s=1}\sum^N_{t=1}|S(i+s-1,j+t-1)-T(s,t)|$
-
平均绝对差算法(Mean Absolute Differences, MAD)
- $D(i,j)=\frac{1}{M\times N}\sum^M_{s=1}\sum^N_{t=1}|S(i+s-1,j+t-1)-T(s,t)|$
-
归一化互相关算法(Normalized Cross Correlation, NCC)
- $R(i,j)=\frac{\sum^M_{s=1}\sum^N_{t=1}|S^{i,j}(s,t)-E(S^{i,j})|\cdot|T(s,t-E(T))|}{\sqrt{\sum^M_{s=1}\sum^N_{t=1}[S^{i,j}(s,t)-E(S^{i,j})]^2\cdot\sum^M_{s=1}\sum^N_{t=1}[T(s,t)-E(T)]^2}}$
- 序贯相似性检测算法(Sequential Similarity Detection Algorthim, SSDA)
- Hadamard变换算法(Sum of Absolute Transformed Difference, SATD)
- SSD(Single Shot Multi-Box Detector),深度学习的对象检测方法
-
-
拒绝野点更好的方法--NNDR[Lowe, 1999]
- 1-NN:寻找SSD最接近的匹配
- 2-NN:寻找第二近SSD的匹配
- 看1-NN比2-NN更接近多少:$1-NN/2-NN$
- NNDR(nearest neighbor distance ratio)$=\frac{d_1}{d_2}=\frac{|D_A-D_B|}{|D_A-D_C|}$
-
进一步排除点--ANMS
- 自适应非极大值抑制(Adaptive non-maximal suppression, ANMS)
- 特征点要比起半径r内的其他特征点强10%,而不是通过固定阈值。
随机采样一致性(RANSAC)
- 问题:匹配对中出现不一致的情况("bad" matches)
-
随机采样一致性(Random Sample Consensus)
- 选一对候选对假设正确,然后其他点也按此映射寻找匹配对
- 平均值映射,Least squares fit
-
RANSAC 循环
- 随机选择四对特征点;
- 计算单应性(homography) $H$;
- 计算内点(inliers)当$SSD(p_i,H_{p_i})<\epsilon$;
- 记录最大匹配集合;
- 重复计算,得到在最大匹配集上估计的最小$H$。
-
通用的RANSAC算法
运行$k$次:
- 随机选取$n$个采样;
- 对$n$个采样配合合适的参数$\Theta$;
- 对另外$N-n$个点,计算对应模型的适应度,得到匹配集合的点数$c$。
输出参数$\Theta $和最大适配集合$c$。
-
计算$k$
- $n$:每次迭代采样的数量
- $p$:真实适配集合的概率
- $P$:$k$次迭代后至少一次成功的概率
- $k=\frac{\log(1-P)}{\log(1-p^n)}$
关于图像特征部分的一半内容,包含提取、匹配。中间概念较多,但理解后还是蛮清晰的,只是计算、公式、实现部分需要多多思考。计算机视觉的魅力开始渐渐体现了...
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论