《计算机视觉》

简介

这学期上《计算机视觉》,感觉很多不懂,记录一下。

综合转载以下文章:

现实中平行的直线在照片中,尽管还是直的,但很多时候都不会平行,将它们延伸至相交,交点称为“消失点“。两个消失点相连,称为”消失线“。

在欧几里得几何空间里,两条平行线永远都不会相交。但是在投影空间中,如右图中的两条铁轨在地平线处却是会相交的,因为在无限远处它们看起来相交于一点。

在欧几里得(或称笛卡尔)空间里描述2D/3D 几何物体是很理想的,但在投影空间里面却并不见得。 我们用 (x, y) 表示笛卡尔空间中的一个 2D 点,而处于无限远处的点 (∞,∞) 在笛卡尔空间里是没有意义的。投影空间里的两条平行线会在无限远处相交于一点,但笛卡尔空间里面无法搞定这个问题(因为无限远处的点在笛卡尔空间里是没有意义的),因此数学家想出齐次坐标这个点子来了。

齐次坐标

由 August Ferdinand Möbius 提出的齐次坐标(Homogeneous coordinates)让我们能够在投影空间里进行图像和几何处理,齐次坐标用 $N + 1$个分量来描述 $N$ 维坐标。比如,2D 齐次坐标是在笛卡尔坐标$(X, Y)$的基础上增加一个新分量 $w$,变成$(x, y, w)$,其中笛卡尔坐标系中的大$X$,$Y$ 与齐次坐标中的小$x$,$y$有如下对应关系:

笛卡尔坐标中的点 $(1, 2) $在齐次坐标中就是$ (1, 2, 1)$ 。如果这点移动到无限远$(∞,∞)$处,在齐次坐标中就是 $(1, 2, 0)$ ,这样我们就避免了用没意义的”$∞$” 来描述无限远处的点。

为什么叫齐次坐标?

前面提到,我们分别用齐次坐标中的 $x$ 和 $y$ 除以 $w$ 就得到笛卡尔坐标中的 $x$ 和 $y$,如图所示:

仔细观察下面的转换例子,可以发现些有趣的东西:

上图中,点 $(1, 2, 3)$,$(2, 4, 6)$ 和 $(4, 8, 12)$ 对应笛卡尔坐标中的同一点 $(\frac{1}{3}, \frac{2}{3})$。 任意数量积的$(1a, 2a, 3a)$ 始终对应于笛卡尔坐标中的同一点 $(\frac{1}{3}, \frac{2}{3})$。因此这些点是“齐次”的,因为他们始终对应于笛卡尔坐标中的同一点。换句话说,齐次坐标描述缩放不变性(scale invariant)。

证明: 两平行线可以相交

笛卡尔坐标系中,对于如下两个直线方程:

如果 $C ≠ D$,以上方程组无解;如果 $C = D$,那这两条线就是同一条线了。
下面我们用 $\frac{x}{w}$,$\frac{y}{w}$ 代替 $x$, $y$ 放到投影空间里来求解:

现在我们就可以在 $C ≠ D$ 的情况得到一组解 $(x, y, 0)$,代入得 $(C - D)w = 0$,因为 $C ≠ D$,所以 $w = 0$。因而,两条平行线相交于投影空间中无限远处的一点 $(x, y, 0)$。

齐次坐标在计算机图形学中是有用的,将 3D 场景投影到 2D 平面的过程中就用到它了。

三坐标系

图像坐标系

如图所示,以图像左上角为原点建立以像素为单位的直接坐标系$u-v$。像素的横坐标$u$与纵坐标$v$分别是在其图像数组中所在的列数与所在行数。

由于$(u,v)$只代表像素的列数与行数,而像素在图像中的位置并没有用物理单位表示出来,所以,我们还要建立以物理单位(如毫米)表示的图像坐标系$x-y$。将相机光轴与图像平面的交点(一般位于图像平面的中心处,也称为图像的主点(principal point)定义为该坐标系的原点$O_1$,且$x$轴与$u$轴平行,$y$轴与$v$轴平行,假设$(u_0,v_0)$代表$O_1$在$u-v$坐标系下的坐标,$dx$与$dy$分别表示每个像素在横轴$x$和纵轴$y$上的物理尺寸,则图像中的每个像素在$u-v$坐标系中的坐标和在$x-y$坐标系中的坐标之间都存在如下的关系:

(上述公式中我们假设物理坐标系中的单位为毫米,那么$dx$的的单位为:毫米/像素。那么$x/dx$的单位就是像素了,即和$u$的单位一样都是像素)

为了使用方便,可将上式用齐次坐标与矩阵形式表示为:

其逆关系可表示为:

相机坐标系

相机成像的几何关系可由图表示。其中$O$点为摄像机光心(投影中心),$X_c$轴和$Y_c$轴与成像平面坐标系的$x$轴和$y$轴平行,$Z_c$轴为摄像机的光轴,和图像平面垂直。光轴与图像平面的交点为图像的主点$O_1$,由点$O$与$X_c$,$Y_c$,$Z_c$轴组成的直角坐标系称为摄像机的坐标系。$OO_1$为摄像机的焦距。

世界坐标系

世界坐标系是为了描述相机的位置而被引入的,如图中坐标系$O_wX_wY_wZ_w$即为世界坐标系。平移向量$t$和旋转矩阵$R$可以用来表示相机坐标系与世界坐标系的关系。所以,假设空间点$P$在世界坐标系下的齐次坐标是$(X_w,Y_w,Z_w,1)^T$,(这里$T$是上标转置),在相机坐标下的齐次坐标是$(X_c,Y_c,Z_c,1)^T$,则存在如下的关系:

上式中$R$是$3×3$的正交单位矩阵(也成为旋转矩阵),$t$是三维的平移向量。矢量$0=(0,0,0)$。

投影矩阵

结合以上三种坐标系的转换,得到下图。

内部矩阵$K$

1.焦距$f$

2. 光中心$(u_0,v_0)$

3.单元的长宽比,非方形$\alpha$,$\beta$

4.倾斜程度$s$

旋转矩阵$R$

逆时针旋转。

1.绕$x$轴

2.绕$y$轴

3.绕$z$轴

平移向量$T$

自由度

$K$有5个自由度,$R$有3个自由度,$xyz$三轴的旋转角度,$T$有3个自由度,总共有11个自由度。

常见2D变换/仿射变换

景深

景深(DOF),是指在摄影机镜头或其他成像器前沿能够取得清晰图像的成像所测定的被摄物体前后距离范围。而光圈、镜头、及拍摄物的距离是影响景深的重要因素。

在聚焦完成后,焦点前后的范围内所呈现的清晰图像,这一前一后的距离范围,便叫做景深。在镜头前方(调焦点的前、后)有一段一定长度的空间,当被摄物体位于这段空间内时,其在底片上的成像恰位于焦点前后这两个弥散圆之间。被摄体所在的这段空间的长度,就叫景深。换言之,在这段空间内的被摄体,其呈现在底片面的影象模糊度,都在容许弥散圆的限定范围内,这段空间的长度就是景深。

光子

吸收

漫射

反射

透射

折射

荧光

子面散射

磷光

相互反射

图片显示的两种方式

  • Global shutter是通过整幅场景在同一时间曝光实现的。
  • Rolling shutter与Global shutter不同, 它是通过Sensor逐行曝光的方式实现的。

人眼

视锥细胞

视细胞的一种,位于视网膜内。因为它能接受光刺激,并将光能转换为神经冲动,故亦称光感受器。由外节、内节、胞体和终足四部分组成。其外节为圆锥状,故名视锥细胞。内含有感光物质(视紫蓝质)。在光刺激下,感光物质可发生一系列的光化学变化和电位改变,使视锥细胞发放神经冲动。

视锥细胞是感受强光和颜色的细胞,对弱光和明暗的感知不如视杆细胞敏感;而对强光和颜色,具有高度的分辨能力。在视网膜的黄斑中央凹处,只有视锥细胞,光线可直接到达视锥细胞,故此处感光和辨色最敏锐。而以视杆细胞为主的视网膜周缘部,则光的分辨率低,色觉不完善,但对暗光敏感。家鸡等动物视网膜中视锥细胞较多,故黄昏以后视觉减弱。人的视网膜中约有600万~800万个视锥细胞。

  • 锥形
  • 不敏感
  • 在高光下操作
  • 彩色视觉

视杆细胞

视细胞的一种,位于视网膜内。因为它能接受光刺激,并将光能转换为电能,发放神经冲动,故亦称光感受器。

由外节、内节、胞体和终足四部分组成。其外节呈细杆状,故名视杆细胞。内含有感光物质,在光刺激下,感光物质可发生一系列的光化学变化和电位改变,使视细胞发放神经冲动。视杆细胞是感受弱光刺激的细胞,对光线的强弱反应非常敏感,对不同颜色光波反应不敏感。它所含的感光物质为视紫红质。

猫头鹰等动物视网膜中视杆细胞较多,故夜间活动视觉灵敏。人的视网膜中约有12000万个视杆细胞。

  • 杆状
  • 高度敏感的
  • 在晚上工作
  • 灰度视觉

中央凹没有杆体细胞,只有锥体细胞,其密度高达每平方毫米150,000。

离开中央凹,锥体细胞急剧减少,而杆体细胞急剧增多,在离开中央凹20度的地方,杆体细胞最多.中央凹的锥体细胞密度很高,是产生最清晰视觉的地方.杆体细胞主要是在黑暗的条件下起作用,同时还负责察觉物体的运动。

感受野

直接或间接影响某一特定神经细胞的光感受器细胞的全体。

感受野分两大类:

  • On型感受野:由中心的兴奋区域和周边的抑制区域构成的同心圆结构
  • Off型感受野:由中心抑制和周边兴奋区域构成的同心圆结构

图像滤波

三种滤波方式:

  • 空间域的图像滤波器:一种数字网格的数学运算,包括平滑,锐化,测量纹理
  • 频域的图像滤波器:一种修改图像频率的方法,包括去噪,采样,图像压缩
  • 模板和图像金字塔:一种将模板匹配到图像的方法,包括检测,粗到细的配准

空间域的图像滤波器

盒滤波器

作用:实现平滑效果,删除锐利的特征

锐化滤波器

作用:突出与局部平均水平的差异

垂直边缘滤波器

水平边缘滤波器

滤波与卷积的区别

  • 线性:
    filter(f1 + f2) = filter(f1) + filter(f2)

  • 位移不变性:
    filter(shift(f)) = shift(filter(f))

任何线性、位移不变算子都可以表示为卷积。

滤波的可分离性

滤波器的大小

中值滤波器

中值滤波器通过选择窗口中的中值强度来进行,对于离群值有很高的鲁棒性。

其他非线性滤波器

  • 加权中值滤波器(离中心计数远一点的像素)
  • 修剪均值滤波器(均值,但忽略一些最亮和最暗的像素)
  • 双边滤波滤波器(按空间距离和强度差加权)

三外:卷积

一维卷积

定义:

将函数$g$反折,向右移动距离$t$,计算$x$和反折后的$g$在各点的积,积分得到在$t$处的输出值。






离散一维卷积

两个长度分别为$m$和$n$的序列$f(i)$,$g(i)$的卷积为:

$h(i)$给出了一个长度为$N=m+n-1$的输出序列。
$f(i)$是一个周期至少为$N$的无限长周期序列的一部分,由于$f(i)$的长度小于$N$,其空余部分必须补$0$。

$g(i)$,$h(i)$有相同的操作


矩阵$G$叫做环矩阵。

二维卷积

$g(-u,-v)$是$g(u,v)$绕其原点旋转$180$度,$g(x-u,y-v)$将旋转后的$g$移至点$(x,y)$。随后这两个函数逐点相乘,将得到的积函数做二维积分。例:


离散二维卷积

定义:

由于$F$和$G$仅在有限范围内非$0$,因此求和计算只在非$0$部分重叠的区域上进行。$G$叫做卷积核,若$G$较大,卷积将耗费相当长的时间。

假设数组$F$和$G$在$x$方向上是周期的,周期长度至少等于这两个数组水平长度之和,$y$方向也做如此假设。扩展后的新矩阵为$F_p$,$G_p$按行堆叠的方法从$F_p$构造一个$N^2×1$维列向量$f_p$:将$F_p$的第一行转置,使之成为$F_p$的最上面$N$个元素,然后将其他行转置依此放在它下面。将矩阵$G_p$的第一行先生成一个$N×N$循环矩阵,总共生成$N$个这样的矩阵$G_i$。按如下方式生成一个$N^2×N^2$的块矩阵$G_b$:

二维卷积写成简单的矩阵形式:

首先,贴一下傅里叶变换的介绍,傅里叶分析之掐死教程(完整版)更新于2014.06.06

连续:

离散:

图像傅里叶变换的物理意义

图像的频率是表征图像中灰度变化剧烈程度的指标,是灰度在平面空间上的梯度。如:大面积的沙漠在图像中是一片灰度变化缓慢的区域,对应的频率值很低;而对于地表属性变换剧烈的边缘区域在图像中是一片灰度变化剧烈的区域,对应的频率值较高。傅里叶变换在实际中有非常明显的物理意义,设f是一个能量有限的模拟信号,则其傅里叶变换就表示f的频谱。从纯粹的数学意义上看,傅里叶变换是将一个函数转换为一系列周期函数来处理的。从物理效果看,傅里叶变换是将图像从空间域转换到频率域,其逆变换是将图像从频率域转换到空间域。换句话说,傅里叶变换的物理意义是将图像的灰度分布函数变换为图像的频率分布函数。

傅里叶逆变换是将图像的频率分布函数变换为灰度分布函数傅里叶变换以前,图像(未压缩的位图)是由对在连续空间(现实空间)上的采样得到一系列点的集合,通常用一个二维矩阵表示空间上各点,记为z=f(x,y)。又因空间是三维的,图像是二维的,因此空间中物体在另一个维度上的关系就必须由梯度来表示,这样我们才能通过观察图像得知物体在三维空间中的对应关系。

傅里叶频谱图上我们看到的明暗不一的亮点,其意义是指图像上某一点与邻域点差异的强弱,即梯度的大小,也即该点的频率的大小(可以这么理解,图像中的低频部分指低梯度的点,高频部分相反)。一般来讲,梯度大则该点的亮度强,否则该点亮度弱。这样通过观察傅里叶变换后的频谱图,也叫功率图,我们就可以直观地看出图像的能量分布:如果频谱图中暗的点数更多,那么实际图像是比较柔和的(因为各点与邻域差异都不大,梯度相对较小);反之,如果频谱图中亮的点数多,那么实际图像一定是尖锐的、边界分明且边界两边像素差异较大的。

对频谱移频到原点以后,可以看出图像的频率分布是以原点为圆心,对称分布的。将频谱移频到圆心除了可以清晰地看出图像频率分布以外,还有一个好处,它可以分离出有周期性规律的干扰信号,比如正弦干扰。一幅频谱图如果带有正弦干扰,移频到原点上就可以看出,除了中心以外还存在以另一点为中心、对称分布的亮点集合,这个集合就是干扰噪音产生的。这时可以很直观的通过在该位置放置带阻滤波器消除干扰。

示例

性质

  1. 两个函数卷积的傅里叶变换是它们的傅里叶变换的乘积

  1. 空间域的卷积等于频域的乘法

  1. 线性

  1. 实信号的傅里叶变换关于原点是对称的

  2. 信号的能量等于它的傅里叶变换的能量

频域滤波

将图像和滤波器先转换成频域图,相乘之后,再用逆傅里叶变换转换成时域图像。

高斯滤波

盒滤波

采样

混叠问题

在统计、信号处理和相关领域中,混叠是指取样信号被还原成连续信号时产生彼此交叠而失真的现象。当混叠发生时,原始信号无法从取样信号还原。而混叠可能发生在时域上,称做时间混叠,或是发生在频域上,被称作空间混叠。

奈奎斯特准则

所定的取样频率若取样的频率太低,就会产生取样的结果和原来的样本不同的状况。若一样本的频谱是带限频谱,也就是在某一频率$|w_n|$之外都为0的频谱,那么取样频率$w_s$就必须要大于两倍的$w_n$,才不至于使频谱产生交叠,也因此产生失真。

数学式表示为:$w_s>2w_n$。

消除混叠

采样定理的一个重要指导意义是给出了消除混叠的最低条件,混叠本身是采样的必然效应,只不过如果混叠到原信号带宽范围内的频率成分为零的话,信号不会被破坏,也就能“完全重构”了。消除频率混叠的途径有两种:

  1. 提高采样频率$f_s$,即缩小采样时间间隔。然而实际的信号处理系统不可能达到很大的采样频率。另外,许多信号本身可能含有$0\sim \infty$范围内的频率,不可能将采样频率提高到$\infty$。所以,通过提高采样频率避免混叠的方法是有限制的。
  2. 采用抗混滤波器。在采样频率fs一定的前提下,通过低通滤波器滤掉高于fs/2的频率成分,通过低通滤波的信号则可避免出现频率混叠。

人类感知线索

人类的早期处理过滤各种方向和频率范围。

中高频的感知线索主导着感知。

当我们看到远处的图像时,我们实际上是对它进行子采样。

离散傅利叶变换

逆变换:

快速傅里叶变换(FFT)在串行机器上最优地实现,DFT在并行机器上更快。

模板匹配

滤波器匹配

用眼睛对图像进行滤波。

零均值滤波器匹配

用零均值的眼睛对图像进行滤波。

SSD

潜在缺点

归一化互相关

方法比对

视情况而定:

  • SSD:更快,对整体强度敏感;
  • 归一化互相关:较慢,对局部平均强度和对比度不变

但实际上,这些方法已经过时。

图像金字塔

用于不同尺度的匹配。

流程:

1
2
3
4
5
1.输入:图像,模板
2.按当前比例匹配模板
3.下采样图像
4.重复1-2直到图像很小
5.在某些阈值以上采取响应,可能带有非最大值抑制

二维边缘检测滤波器

拉普拉斯滤波器

计算高斯/拉普拉斯的金字塔

图像表示总结

  • 像素:非常适合空间域,对频率不适用;
  • 傅里叶变换:非常适合频率,而不适用于空间信息;
  • 金字塔/滤波器组:空间和频率信息之间的平衡。

应用:纹理表示

纹理:由凸起、凹槽和/或标记引起的规则或随机模式。

纹理表示:计算在不同方向和尺度上的斑点和边缘的响应。

过完备表示:滤波器组(filter banks)

纹理特征表示

测量斑点和边缘在不同方向和尺度上的响应。

idea1:记录完全过滤器响应的简单统计信息(如均值、标准差)

用完全响应表示纹理,

idea2:取每个像素的滤波器响应向量并将它们聚类,然后取直方图

图像压缩

离散余弦变换(DCT)

有损图像压缩(JPEG)

块状离散余弦变换

  • 第一个系数$B(0,0)$是DC分量,即平均强度
  • 左上角的系数表示低频,右下角表示高频

将DCT用于图像压缩

  • 量化:
    • 高频更粗略(也往往具有更小的值)
    • 许多量化的高频值将为零
  • 编码:
    • 可以用逆DCT解码

JPEG压缩的总结

  1. 将图像转换为$YC_rC_b$颜色空间

  2. 子样本颜色的因子2

    人们对颜色的分辨能力很差

  3. 分成块(通常是8x8),减去128

  4. 对于每个块,

    1. 计算DCT系数

    2. 粗量化

      许多高频部分将变为零

    3. 编码(例如,用霍夫曼编码)

无损压缩(PNG)

  1. 根据左上角的邻域预测像素值
  2. 存储预测值和实际值的差值
  3. Pkzip它(DEFLATE算法)

降噪

减少高斯噪声

用较大的标准差进行平滑可以抑制噪声,但也会模糊图像。

通过高斯平滑减少椒盐噪声

中值滤波器

对离群值有鲁棒性

六:边缘/边界检测

目标:识别图像中的突然变化(不连续)

  • 直观上,图像的大部分语义和形状信息都在边缘上进行编码表示
  • 比像素更紧凑

理想情况:生成像艺术家的线条画(虽然艺术家也使用对象级知识)

边缘是由多种因素造成的:

  • 表面正常的不连续
  • 深度不连续
  • 表面颜色不连续
  • 光照不连续

描述边缘

  • 边缘是图像强度函数快速变化的地方

噪声的影响

差分滤波器对噪声有很强的响应能力:

  • 图像噪声产生的像素看起来与它们的相邻非常不同
  • 一般来说,噪音越大,响应越强

解决方案

  1. 平滑

在$\frac{d}{dx}(f\ast g)$的山峰寻找边缘。

卷积导数定理

微分是卷积,卷积是联合的。

平滑和定位之间的权衡:

实施问题

  • 沿着一条厚厚的“轨迹”或“山脊”,梯度大小很大,那么我们如何识别实际的边缘点呢?
  • 我们如何将边缘点连接起来形成曲线?

设计边缘检测器

好的边缘检测器的标准:

  • 好的检测:最优检测器应找到所有真实边缘,忽略噪声或其他人为因素
  • 好的定位:
    • 检测到的边缘必须尽可能接近真实的边缘
    • 探测器必须仅为每一个真正的边缘点返回一个点

边缘检测线索:

  • 颜色、强度或纹理的差异
  • 连续性和闭合性
  • 高层次的知识

Canny边缘检测器

这可能是计算机视觉中应用最广泛的边缘检测器。

理论模型:加性高斯噪声破坏的阶梯边缘。

Canny已经证明高斯的一阶导数非常接近于优化信噪比和定位的乘积的算子。

Matlab中的Canny边缘检测器

实现中的小错误:

  • 高斯函数没有很好地归一化
  • 首先用高斯滤波器,然后是高斯差分。(相当于用更大的高斯函数进行滤波并取差)
样例

  1. 高斯滤波器的导数

  1. 计算梯度(DoG)

  1. 获得每个像素的方向

  1. 每个方向的非最大值抑制

在$q$处,如果值大于$p$处和$r$处的值,就会得到最大值。

  1. 边缘连接

假设标记点是一个边缘点。然后我们构造一条与边缘曲线相切的曲线(这条曲线与该点的梯度是垂直的),然后用它来预测下一个点(这里不是$r$就是$s$)。

  1. 其他工具:双线性插值

  1. 双阈值
  • 阈值在低/高水平得到弱/强边缘像素
  • 连接组件,从强边缘像素开始

  • 检查梯度值的最大值是否足够大
  • 使用高阈值构建边缘曲线,使用低阈值延伸它们

总结
  1. 用高斯函数的$x$, $y$导数对图像进行滤波

  2. 求梯度的大小和方向

  3. 非极大值抑制

    宽薄的多像素“脊”变为单像素宽度

  4. 阈值化与连接(双阈值)

    • 定义两个阈值:低阈值和高阈值
    • 使用高阈值构建边缘曲线和低阈值延伸它们

pB边缘探测器

七:兴趣点和角点

跨越视角的对应

对应:图像之间的匹配点、小块、边缘或区域。

应用

特征点用于:

  • 图像对齐
  • 三维重建
  • 运动跟踪
  • 机器人导航
  • 索引和数据库检索
  • 对象识别

关键点匹配概述

  1. 找到一组有鉴别力的关键点
  2. 围绕每个关键点定义一个区域
  3. 提取和正则化区域内容
  4. 从正则化区域计算局部描述符
  5. 匹配局部描述符

不变局部特征

图像内容被转换成局部特征坐标,这些坐标对平移、旋转、缩放和其他成像参数不变。

  1. 检测:识别感兴趣的点
  2. 描述:提取每个兴趣点周围的向量特征描述符。
  3. 匹配:确定两个视图中描述符之间的对应关系

好的特征的特点

  • 可重复性

    同样的特征可以在一些图像中发现,尽管存在着几何变换和光度变换

  • 鉴别性

    每个特征都有鉴别性的

  • 紧致性和效率性

    比图像像素更少的特征

  • 局域性

    一个特征占据图像相对较小的区域;抗杂乱和抗遮挡

可重复性

我们希望在这两幅图像中检测到(至少部分)相同的点。然而,我们必须能够独立地根据图像运行检测程序。

鉴别性

我们希望能够可靠地确定哪一点与哪一点相匹配。必须为两个视图之间的几何和光度差异提供一定的不变性。

角点检测

透过小窗口可以使人很容易地认出它。向任何方向移动一个窗口都会使强度发生很大的变化。

关键性质:在角点区域,图像梯度有两个或两个以上的主导方向;而且角点是可重复的和鉴别性的。

数学推导

窗口坐标函数$w(x,y)$,偏移量$[u,v]$,强度$I(x,y)$,偏移强度$I(x,y)$:

窗口坐标函数$w(x,y)$为,

$E(u,v)$在$(0,0)$附近的局部二次逼近由二阶泰勒展开式给出:

所以,

其中$M$为图像导数计算的二阶矩矩阵:

解释二次矩阵

表面$E(u,v)$局部近似为二次形式。

首先,考虑轴对齐的情况(渐变是水平的或垂直的),如果$λ$接近0,那么这不是一个角点,所以寻找两者都很大的位置。

之后,考虑水平切片的情况,$M$的对角化,

椭圆的轴长度由特征值$\lambda$确定,方向由$R$确定。

二次矩阵的可视化:

解释特征值

使用$M$的特征值对图像点进行分类:

角点响应方程:

其中$\alpha$为$(0.04,0.06)$的定值。

Harris角点检测

  1. 计算每个图像窗口的$M$矩阵来获得其角度得分
  2. 找到周围窗口给出大角点响应的点($f>threshold$)
  3. 取局部最大值的点,即执行非最大值抑制

例子

Hessian角点检测

Hessian&Harris

Hessian检测:

Harris检测:

不变性和齐变换性

我们希望角点位置对光度变换是不变的,并且对几何变换是一起变换的,

  • 不变性:图像被转换,角点位置不会改变
  • 齐变换性:如果同一幅图像经过了两次变换,特征应该能在相应的位置被检测到

仿射强度变化

八:局部图像特征

自动选择尺度

如何自动选择:增加尺度的函数响应(尺度签名)

有用的签名函数

高斯差分=“斑点”检测器

DoG过程参考:SIFT特征详详解

结果:

Harris-Laplace

最大稳定极值区域(MSER)

基于分水岭分割算法,选择在大参数范围内保持稳定的区域。

  • 极值区域:$\forall p \in Q,q\in \delta Q$
  • 有序区域:$I(p)>I(q)$或$I(p)<I(q)$,$Q_1 \subset … \subset Q_i \subset Q_{i+1} \subset … \subset Q_n$
  • MSER:$q(i)=|Q_{i+\Delta}\backslash Q_{i-\Delta}|/Q_i$

步骤

  1. 聚类(Clustering)

    对于目标图像在每一个灰度级做二值化处理,例如对于灰度级$i$,将原图中灰度大于等于$i$的像素的灰度级置为$1$,将灰度小于$i$的像素置为$0$。于是在此二值图像中必有若干个像素值为$1$的连通区。那么对于每一个灰度级都可以形成相应的连通区域。于是纵向观察这些区域,不同灰度级的连通区域之间必然存在嵌套关系(即嵌套树结构)。

  2. 探测最大稳定极值区域(MSER detection)

    $Q_1,Q_2,…,Q_i$为相互嵌套的区域(Region)且(属于$Q_i$灰度级$i$的连通区域)定义函数:

    其中$\Delta$为人为选定的参数,$|Q_i|$为$Q_i$连通区域的势(即包含的点的个数),对每个$Q_i$计算其$q(i)$,若$q(i)$为局部极小值,则$Q_i$为MSER。

  3. 结果显示

    将一幅灰度图像按照上述步骤进行处理得到MSER+特征区域,再将该图象反转,重复上述步骤得到MSER-特征区域。于是取这些区域的重心,并且以1.5倍该区域的尺度做椭圆形区域。

图像表示:直方图

直方图:每个bin中数据的概率或计数。

距离计算

  1. 直方图交集(假设已归一化)
  1. 卡方距离

量化

  • 网格:快速但只适用于很少的维数
  • 聚类:速度较慢,但可以量化高维数据

匹配

  • 直方图交集或欧几里德可能更快。
  • 卡方距离经常表现更好。
  • 当附近的bin代表相似的值时,EMD距离(Earth mover’s distance)会表现得更好。

局部描述符:形状上下文

计算每个bin里的点数,如上图。使用对数极坐标系的原因:对附近的点更精确,对更远的点更灵活。

局部描述符:几何模糊

自相似性描述符

学习局部图像描述符

局部描述符:总结

  • 形状:场景比例,物体比例,细节比例,2D形式,阴影,阴影,纹理,线性透视
  • 材料特性:反射率,手感,硬度,颜色,质地
  • 运动:光流,跟踪点
  • 距离:立体,位置,遮挡,场景形状,大小,其他对象

大多数特征可以看作是模板、直方图(计数)或组合。应该是鲁棒性的、判别性的、紧凑的、高效的。

大多数可用的描述符集中在边缘/梯度信息上,捕获纹理信息,颜色特征很少使用。

局部描述符:匹配

寻找欧式距离下最接近的描述符,与第二接近的描述符之间到达一个阈值即为成功匹配。

SURF

参照SURF特征详解

九:拟合

拟合:找到最适合数据的模型参数。

设计挑战:

  • 设计合适的拟合度量
    • 相似性应反映应用目标
    • 编码对异常值和噪声的鲁棒性
  • 设计优化方法
    • 避免局部最优值
    • 快速找到最佳参数

方法

  • 全局优化/参数搜索
    • 最小二乘法拟合
    • 鲁棒最小二乘法拟合
    • 最近点迭代(ICP)
  • 假设与测试
    • 广义Hough变换
    • RANSAC

简单例子:拟合一条直线

“垂直”最小二乘法

“垂直”最小二乘法的问题:

  • 不具有旋转不变性
  • 完全失败的垂直线

总体最小二乘法

如果$a^2+b^2=1$,那么点$(x_i,y_i)$到单位法线的距离为$|ax_i+by_i+c|$。

找到$(a,b,c)$以最小化垂直距离的平方和,$E=\sum_{i=1}^n(ax_i+by_i+c)^2$。

解是对应于$A^TA$最小特征值的特征向量。

概述:两个优化问题

最小二乘法(全局)优化:

  • 优点:

    • 有明确的目标函数
    • 优化是很容易的
  • 缺点:

    • 可能不是按照预期所优化的

    • 对异常值敏感

      不好的匹配,额外的点

    • 不允许得到多个好的拟合

      检测多个对象和线等

鲁棒最小二乘法(用于处理异常值)

其中,$u_i(x_i,\theta)$为关于模型参数 $\theta$ 的第 $i$ 个点的残差,$\rho$ 是具有尺度参数 $\sigma$ 的鲁棒函数。

鲁棒函数 $\rho$

  • 支持具有较小残差
  • 对于较大的残差,惩罚不变

鲁棒估计

  1. 初始化:通过最小二乘拟合选择 $θ$,$\sigma=1.5·\text{median}(error)$。
  2. 选择参数最小化:$\sum_i=\frac{error(\theta,data_i)^2}{\sigma^2+error(\theta,data_i)^2}$,例如数值优化。
  3. 计算新的$\sigma=1.5·\text{median}(error)$。
  4. 重复第2步和第3步直至收敛。

搜索参数的方法(当不存在闭式解时)

  • 线性搜索/一维搜索
    1. 对于每个参数,逐步检查值并选择最适合的值
    2. 重复第1步直到没有参数发生变化
  • 网格搜索/二维搜索
    1. 提出几组参数,在联合集中均匀采样
    2. 选择最佳(或前几个)并围绕当前最佳样本联合参数,重复
  • 梯度下降法
    1. 生成初始化位置(例如随机化)
    2. 根据梯度在局部搜索更好的参数

假设与测试

  1. 提出参数
    • 尝试所有可能
    • 每个点都为所有一致性参数投票
    • 重复采样足够的点来求解参数
  2. 对给定参数进行评分

    • 一致点的数目,可以由距离加权
  3. 从一组参数中进行选择

    • 全局/局部最优值得分
  4. 可以通过内点来优化参数

Hough变换

  1. 创建参数值网格
  2. 每个点投票给一组参数,在网格中增加这些值
  3. 在网格中找到最大值或局部最大值

给定一组点,找出最能解释数据点的曲线或直线。

问题:参数空间 $[m,b]$ 是无界的。

解决方法:对参数空间使用极坐标表示。

一些实验结果

问题:由于均匀的噪声产生的伪峰值。

利用Hough变换求解直线

  • 使用 $m$,$b$ 参数化
  • 使用 $r$,$\theta$ 参数化

    • 使用有方向的梯度
  • 实际考虑

    • bin大小
    • 平滑化
    • 求解多条线
    • 求解线段

优点

  • 对异常值的健壮性:每个点单独投票
  • 十分高效(比尝试所有参数快得多)
  • 生成多个好的拟合

缺点

  • 对噪音的敏感性

  • bin的大小在噪音容限、精度和速度/内存之间进行权衡

  • 不适合多个参数

    网格大小呈指数增长

应用

  • 直线拟合(圆、椭圆等)
  • 对象实例识别(参数为仿射变换)
  • 对象类别识别(参数为位置/尺度)

RANSAC

随机抽样一致性算法。

步骤:

  1. (随机)抽样所需的点数,以适应模型

  2. 使用样本求解模型参数

  3. 根据模型预设阈值内的离群值的百分比进行评分

  4. 重复第1步至第3步,直到找到最适合的模型

怎样选择参数

  • 样本个数 $N$

    选择 $N$,使得在概率为 $p$ 的情况下,至少有一个随机样本不存在离群值,如$p=0.99$(离群比:e)。

  • 采样点个数 $s$

    符合模型所需的最小数量。

  • 距离阈值 $\delta$

    • 选择 $\delta$ 以便在阈值内可能存在具有噪声的好点,例如 $prob = 0.95$。
    • 零均值,标准差为 $t^2=3.84\sigma^2$ 的高斯噪声。

优点

  • 对异常点/离群点鲁棒
  • 适用于比Hough变换更多的目标函数参数
  • 优化参数的选择比Hough变换简单

缺点

  • 计算时间随着异常值的占比和参数的数量快速增长
  • 不适合生成多个拟合

应用

  • 计算单应性,例如图像拼接
  • 估计基本矩阵(关联两个视图)

十:对齐

对齐:搜索将一组点映射到另一组的模型参数。通常希望得到有最多真实对应关系占比的全局转换。

难点:

  • 噪声(一般为1-3像素)
  • 离群值(通常是50%)
  • 多对一匹配或多个对象

参数(全局)变化

变换 $T$ 用于坐标变换,

$T$ 是全局的,意味着对于任何点 $p$ 都是一样的,可以只用几个参数来描述。对于线性变换,我们可以将 $T$ 表示为矩阵,

基础变换

仿射变换

仿射变换的性质:

  • 直线映射到直线
  • 平行线保持平行
  • 保留比率
  • 仍然保持闭合

投影变换

投影变换是仿射变换和投影变形的组合。有以下性质:

  • 直线映射到直线
  • 平行线不一定保持平行
  • 不保持原本的比率
  • 仍然闭合
  • 基础模型发生改变
  • 8个自由度

例子:解决变换问题

给定 $\{A\}$ 和 $\{B\}$ 中的匹配点,估计对象的平移量

最小二乘法

  1. 确定目标函数
  2. 利用导数
    1. 计算导数
    2. 计算结果
  3. 计算结果
    1. 写成 $Ax=b$ 的形式
    2. 利用伪逆或特征值分解求解

RANSAC

  1. 样本一组(一对)匹配点
  2. 求解变换参数
  3. 具有异常值数量的得分参数
  4. 重复第1步至第3步,$N$ 次

Hough变换

  1. 初始化参数值网格
  2. 每个匹配对都对一致性值进行投票
  3. 找到得票最多的参数
  4. 使用最小二乘法对内点求解

如果没有初始的匹配对,那么RANSAC和Hough变换就不适用。

迭代最近点法(ICP)

目标:估计两组密集点之间的变换。

  1. 初始化变换,例如计算均值和尺度的偏差
  2. 分配$\{Set 1\}$中的每个点到$\{Set 2\}$中最近邻
  3. 估计变换参数,即最小二乘法/鲁棒最小二乘法
  4. 变换使用估计参数转换 $\{Set 1\}$ 中的点
  5. 重复第2步至第4步,直至变化非常小

例子:边界对齐

  1. 提取边缘像素 $p_1..p_n$ 和 $q_1..q_m$

  2. 计算初始变换(例如,根据质心和方差计算平移和缩放)

  3. 得到每个点 $p$ 的最近邻,对应匹配

  1. 根据匹配计算变换 $T$
  2. 根据 $T$ 变换点 $p$
  3. 重复第3步至第5步,直至收敛

总结

  • 最小二乘法
    • 闭式解
    • 对噪声鲁棒
    • 对异常点不鲁棒
  • 鲁棒最小二乘法
    • 提高对噪声的鲁棒性
    • 需要迭代优化
  • Hough变换
    • 对噪声和异常点鲁棒
    • 能够拟合多个模型
    • 只适用于少数参数(一般1至4)
  • RANSAC
    • 对噪声和异常点鲁棒
    • 能够适用于较多的参数(一般1至8)
  • 迭代最近点法(ICP)
    • 仅用于局部对齐:不需要初始对应

对象实例识别

  1. 将关键点与对象模型匹配
  2. 求解仿射变换参数
  3. 按内点评分排序并选择分数高于阈值的内点

特征点匹配

  1. 找到一组独特的关键点
  2. 描述每个关键点周围的区域
  3. 提取并正则化区域内容
  4. 从正则化区域计算局部描述符
  5. 匹配局部描述符

基于特征点的实例识别

给出两个图像及其关键点(位置,比例,方向,描述符)。
目标:验证它们是否属于一致的。

对象搜索

  1. 匹配从输入图像到数据库图像的特征点
  2. 匹配点投票选择粗略的位置、方向、对象比例
  3. 找到至少有三票的位置、方向、对象比例
  4. 使用具有异常值检查的迭代最小二乘法计算仿射定位和匹配
  5. 如果至少有 $T$ 个匹配点,则报告对象
一分一毛,也是心意。