机器视觉基础

参考视频：

机器视觉概念：计算机视觉（本科）北京邮电大学鲁鹏清晰完整合集_哔哩哔哩_bilibili（本校老师，强烈推荐！！！）
机器视觉实操（初级）机器视觉技术与应用_中国大学MOOC(慕课) (icourse163.org)
机器视觉实操（进阶）：强推！从零入门到超神机器视觉全套课程；机器视觉算法 | opencv | adaboost算法 | 人工智能 | aiot | 线性回归算法_哔哩哔哩_bilibili

参考博客：

2023/3/2 17:00 北京邮电大学的计算机视觉课程讲的非常好，看视频+适当的做笔记即可，教材暂时没有推荐（大部分教材都太老了，而且知识点很冗余），把视频中的知识点基本理解了就行；

2023/3/3 10:43 这门课程就不要花时间去找对应教材了，应该是找不到的，只需要看视频然后在网上找相应的博客总结即可，网上大多数博客总结的都零零散散的，建议学到哪里整理到哪里 – 实在找不到详细的整理资料就自己整理也不是不行（类似上学期操作系统）；

2023/4/20 21:58 从鲁鹏老师的机器视觉技术-recongnition章节开始其实就已经涉及到我们之前学习的一些交叉概念了，因为时间原因所以不再继续深入学习下去，机器视觉技术的学习告一段落；

2023/4/28 23:29 因为作业的原因我又回来了…在脑子比较清醒的时候看这后面的内容还是能看懂一部分的（前段时间看不懂一方面是因为没有笔记做参考比较慌，另一方面是因为老师在这后面难度比较大的部分讲的确实不是很好），所以可以听一部分学一部分，主要还是拓宽知识面构建知识框架；

1.卷积

PS：下面的内容中我们可能会将滤波器、卷积核、模板等当作相同的概念，不必过于计较；

1.1 卷积核

图像噪声点简单来说就是该点的像素值与该点周围的像素值差异过大，去除噪声点最直接的想法就是对噪声点和周围点进行加权平均，这就引出了卷积核的概念

卷积核：存储权值的模板

卷积核也称为滤波核，当我们使用卷积核对图像进行加权平均时我们称这样的卷积核为平均核

3*3大小的平均核

使用卷积核对图像进行卷积，在卷积之前一定要对其进行翻转（不翻转会导致相关），定义f是图像，g是卷积核，对图像进行卷积操作的表达式为

式子中，(m,n)表示正在进行卷积的图像f上的点坐标，(k,l)表示卷积核g上的相对坐标

PS：要保证卷积图像和原图一样大，则需要提前对原图进行填充，常用的方法是周围补0、边缘填充、镜像填充…无论如何，填充的结果都是为了保证输入和输出大小固定

1.2 卷积的特性

我们现在可以将卷积操作表示为数学公式filter(f)，卷积操作主要有以下特性

1.3 卷积的功能

前面我们通过平均核对图像进行平滑降噪引入了卷积核的概念，事实上不同的卷积核作用也不同

原图核左移核平滑核锐化核

1.3.1 高斯平滑核

使用平滑核进行图像处理会出现振铃效果 – 因为模板的每个点的值一样，卷积过程中引入了一些不属于原图的信息

我们希望模板的效果是这样，中心的点权值大，边缘的权值小（边缘对中心的影响太大肯定是不好的）

如何得到上述模板呢？这里引入二维高斯函数，我们称由高斯函数产生的模板为高斯核（其中(x,y)是模板的位置坐标，方差和模板大小由人为规定）

二维高斯函数

高斯核

PS：我们希望模板所有权重值求和为1，如果不是1会导致最终原图的颜色值被衰减 - 在使用高斯函数计算之后进行一个归一化处理可以保证最终的求和为1

因为方差和模板大小都由人为规定，所以其大小也对平滑操作有不同的影响：

模板大小不变改变高斯核的方差 – 方差越小表示数据越集中，表示滤波后中心（即自身）占的比重大，即平滑的效果没那么强
同理，固定方差调整模板的大小 – 因为涉及归一化处理，模板越小则归一化得到的中心值越大，导致滤波后被平滑的效果没那么强

总结：

无论是方差还是模板大小，越大导致图像越模糊，越小导致图像越清晰
关于窗宽和方差的经验 – 若给出方差的值，则窗宽设置为1+2*3方差，这样的窗宽好处是高斯分布几乎包含了所有值（高斯分部图像的特征），归一化的影响微乎其微

高斯核本身具备一些特性：

高斯核可以去除高频信号，保留低频信号
高斯卷积自身是另一个高斯 – 即连续使用两次方差为1的高斯核等同于使用一次方差为根号2的效果（勾股弦定理计算得到）
高斯核还能够分解为x方向和y方向的高斯核，连续使用两次这样的高斯核与使用一次高斯核的效果完全相同

第二点和第三点特性都表达了这样一个事情 – 一个大的高斯核可以拆分为两个小的高斯核，这意味着拆分后会大大减少图像运算的时间复杂度，这也是对图像进行卷积计算中常用的一种优化方式

1.3.2 锐化核

简单理解锐化核：

原图-平滑图=边缘图
原图+边缘图=锐化图
故 2脉冲核-平滑核=锐化核（分配律）

锐化核的推导过程

其中α是锐化因子，表示对图像进行锐化处理的程度，e是脉冲模板，g是平滑模板

1.4 噪声处理

前面介绍了可以使用卷积核来去除噪声，下面详细介绍一下对不同的噪声具体如何选择卷积核进行处理；

噪声一般分为三种，椒盐噪声（黑白），脉冲噪声（全白点），高斯噪声（每个点叠加符合独立正态分布的噪声变量产生）；

不同种类的噪声

高斯核主要用于去除高斯噪声（对于方差越小的高斯噪声去噪效果越好）

当噪声方差较小的时候使用方差较小的高斯核就可以滤波，反之就需要方差较大的模板才行
高斯滤波器的问题：去除噪声的同时边缘也被平滑了，且高斯模板的方差越大平滑效果越明显

对于椒盐噪声来说使用高斯模板的效果并不好，这里需要引入新的模板 – 中值滤波器

中值滤波器的核没有任何权值 – 过滤方式不是加权求和，而是选取模板中的中值作为最后的值

为什么使用中值滤波器去除椒盐噪声能够取得较好的效果呢？ – 因为使用中值滤波器不会给图像产生任何新的像素值，而如果使用平均值会导致图像出现从未有过的新的像素点

实际上，中值滤波对椒盐噪声和白噪声都非常有效
中值滤波的模板大小过大会也导致图像模糊（类似磨皮过头）

2.边缘

参考文章：(8条消息) 边缘检测(Edge Detection)_Wang Yuexin的博客-CSDN博客；

边缘的作用：图像的大部分语义信息和形状信息都可以编码在边缘上，通过边缘图可以了解图像的信息，即使用边可理解表达图像

不同的边的类型对不同问题的理解影响不同

边的分类

2.1 边缘提取

边缘的特征：边缘是图像强度函数中快速变化的地方

无论是什么类型的边，都需要先提取边缘；

边缘和图像其他部分的区别主要在于边缘部分的信号是突变的，那么数学中应该如何找信号突变？ – 这转化为导数操作，即对信号求导，找到导数的极值点

在二维空间中的偏导数计算公式如下

导数的数学公式

显然上述公式不容易计算，计算机视觉中对上述式子进行改进得到近似导数

针对上述公式，边缘提取的任务恰好可以用卷积来计算 – 对x方向的偏导数和y方向的偏导数分别用x方向的卷积核((-1,1)表示自身为负，右边为正)和y方向的卷积核表示

2.2 有限差分滤波器

事实上除了最简单的x方向和y方向的卷积核，还有如下不同算子定义的模板

2.2.1 Prewitt算子

对于单个区域的噪声点不太敏感，中间为0表示用左边和右边的差异来衡量本身是否是梯度，同时利用多个像素相减可以对单个噪声点的影响进行平均；

2.2.2 Sobel算子

这个核是可分离的，先高斯平滑再边缘提取，该算子对噪声的敏感程度更低；

Sobel 算子在 Prewitt 算子的基础上增加了权重的概念，认为相邻点的距离远近对当前像素点的影响是不同的，距离越近的像素点对应当前像素的影响越大，从而实现图像锐化并突出边缘轮廓；

2.2.3 Roberts算子

检测模板检测的信号和模板垂直，Mx检测135°的信号，My检测45°的信号；

2.3 图像梯度

在高数中我们知道梯度表示方向导数最大的向量，在图像中梯度指向强度增长最快（信号变化最大）的方向

梯度的方向与边缘垂直，梯度的模值代表了是边缘的可能性大小

梯度的方向

梯度的模值

2.4 高斯偏导核

如果对上述图像直接用边缘提取会得到下面的图像（因为每个点周围的信号浮动都较大），我们无法得到边缘的信息

出现上述情况的原因是原始信号有噪声，因此在对原始信号求偏导之前需要使用高斯平滑核进行平滑去噪，如果用g表示高斯平滑核，则需要对图像进行两次卷积d(f*g)/dx，能否转换为只对图像进行一次处理？

利用卷积的运算性质可以交换得到f*(dg/dx)，其中的dg/dx我们称为高斯偏导核

Q：为什么使用高斯偏导核更快？

A：dg/dx是高斯偏导模板，相比于f作卷积操作快得多，用算出来的高斯偏导模板与图像进行卷积，此时图像f就只会被操作一次；

高斯偏导核_三维

高斯偏导核是不可分离的，因为高斯g求偏导后的结果会多出一项（与高斯平滑核的区别之一）

高斯偏导核_二维

二维图像中，白色为正，黑色为负，值越大；颜色越深，卷积核的数值变化与其衡量的信号垂直；

高斯平滑核	高斯卷积核/偏导核
目标：去除高频噪声	目标：边缘检测，提取边缘信息
高斯平滑核没有负数	高斯偏导核可以有负数
高斯平滑核加权求和的结果为1（否则对图像信号放大或缩小）	高斯偏导核求和结果为0（否则对平坦的区域卷积后结果非0表示有边，矛盾）

通过增大高斯偏导核的标准差(标准差是方差的算术平方根)，可以使得图像呈现不同的结果，标准差越大滤波后的细节信息丢失的越多（对于不同的任务细节信息的重要性不同）；

2.5 Canny边缘提取算法

Canny边缘提取算法是一个经典的边缘提取算法，主要贡献是双门限和非最大化抑制思想；

问题1：使用简单的高斯偏导核往往会提取出一些无关紧要的噪声；

解决办法：某些区域的幅值较小可能是由于噪声引起的，设置一个门限将低于该门限的边缘去除；

问题2：边应当很细，但是往往提取出的边比较粗

原因：

解决办法：非最大化抑制，找到真正的边；

2.5.1 非最大化抑制

做法非常简单，对于粗边上的每一个像素点，与其梯度方向的前后点的梯度比较，保留值较大者

2.5.2 双门限法

门限设置过高会导致原本某些边会被去除，但是门限设置的过低又会导致某些假边存在（噪声边）；

双门限法的思想是：先用高门限将粗狂的边检测出来 – 这些边是噪声的可能性较低，接着降低门限使得较弱的边显现，只选择与粗狂边有连接的边保留

2.5.3 边缘提取算法

一个完整的边缘提取算法大致步骤如下（以Canny算法举例）

3.拟合

参考文章：(8条消息) 拟合(Fitting)_fitting拟合_Wang Yuexin的博客-CSDN博客；

问题引出：仅靠边缘提取不能对物体进行整体的描述，提取完边缘后如何使用数学模型来描述边缘？

边缘检测只能描述桌子上有钱币，而拟合可以描述钱币在桌子的什么地方、钱币的数学方程等

拟合的难点：

噪声：噪声的存在使拟合的模型偏离真实的线
外点：在目标图形以外的线，如上图中的目标图形为“车”，左边的“栅栏”就是外点
目标图形部分被遮挡，使部分图形消失

Overview

Fitting中常用的几种方法根据问题的难度分别如下：

假如我们已经知道了所有属于这条线上的像素点（噪声点也算原本属于线上的点，只是因为噪声的影响偏离了线） – 一般使用最小二乘法找出这条线
假如我们知道的像素点中有不属于这条线的（外点），按照外点的多少使用不同的方法 – 外点较少使用Robust fitting，外点较多使用RANSAC
假如存在很多线条，对于我们需要求解的线条来说都是外点 – RANSAC或Hough transform
甚至我们连这是否是一条线都不能确定（无法写出它的数学方程） – 使用Snake等虚拟建模

3.1 最小二乘法

最小二乘法的前提是所有的点都处于线上（都是有效点）

目标：找到一条线，使得这些点到线沿着纵轴方向的距离最短（注意不是垂直！！！），转化为使得优化函数E最小

经过上述变化可以直接求解B，使用最小二乘法求解得到的B是实际XB=Y方程的近似解

最小二乘法的问题：

假如要估计的直线是垂直的则无法使用最小二乘法；
假如摄像头旋转过后，原本可求解的直线可能就变得无法求解；

3.2 权最小二乘法

目标：找到一条线，使得这些点到线沿着纵轴方向的距离最短，此处的距离为点到直线的垂直距离，无论怎么旋转都不会影响点和直线之间的关系

使用上述的模型则优化函数E的表达式和待求解矩阵N的关系推导如下

权最小二乘法的几何解释：找到一条直线，使得所有点在法向量方向上的投影最小

权最小二乘法的问题：全最小二乘对外点来说不适用，拟合性很差

3.3 鲁棒性最小二乘

假如点到直线的距离过大（外点），那么认为其贡献有上限

使用鲁棒性最小二乘可以缓解外点带来的影响

鲁棒函数的参数选取需要合适：

参数过小会导致每个点都没有贡献
参数过大会导致出现与权最小二乘相同的问题

鲁棒性最小二乘只能用迭代方法求解（因为不是线性优化问题）

3.4 RANSAC

RANSAC也称为随机采样一致性，适用于外点较多的情况下，使用较少的点来拟合真实的模型；

RANSAC算法的主要步骤如下：

随机选择一个最小的集合s（对于拟合直线方程任务来说最小集合是两个点 – 两点确定一条直线）
拟合出一个模型（对于直线拟合来说就是利用集合中的两个点写出直线方程）
设置一个门限t（直线拟合任务中门限内的点我们认为是内点，门限外的点认为是外点）
用门限t内剩余的点给这个模型“投票”（最简单的投票方式就是有几个点投几票）
重复上述过程，取“得分”最高的模型，记录迭代次数N（这里的N就是得到最好模型一共进行的试验次数）
- 最后的输出结果有两种选择，一种是输出评分最高的模型，一种是输出大于一定门限值的一组模型（可用于存在外线的拟合）
- 最后输出的模型并不是评分最高确定的直线模型，而是会将该直线和内点再次使用权最小二乘方法进行拟合

RANSAC算法是一种框架，这意味着RANSAC算法不仅可用于拟合直线方程，也可以进行其他应用（如指纹匹配等）；

RANSAC算法主要有五个参数：

最小集合s
门限t
拟合准确率p
外点率e
迭代次数N

一般情况下已知s,t,p和e，我们可以直接根据下面的公式计算出迭代次数N

而实际任务过程中，外点率e通常是未知的（因为我们要拟合的线是什么都不知道，又怎么可能知道哪些点不属于这条线？），如何确定迭代次数N呢？

这里采用一种更普适的RANSAC方法 – 自适应参数提取RANSAC

3.5 Hough transform

基本思想：

霍夫变换同样是使用图像上的所有点为直线模型投票，选择票数最高的模型进行输出；
噪声点不会有一致性的答案；
即使中间的某些点被遮挡也能拟合一个好的模型；

霍夫变换首先需要引入原始图像空间和离散参数空间（将参数空间划离散化为一个个grid）

霍夫变换的原理是图像空间中的一个点对应参数空间的一条直线，那么图像空间中的两个点对应参数空间中的两条直线，参数空间中这两条直线的交点对应的参数实际就是图像空间中两点确定的直线的参数；

当图像空间中的点足够多的时候，参数空间中会存在多条直线，这些直线的交点（理解为得分最高的grid）就是图像空间中拟合的直线模型的参数

直角坐标的缺点：

对于m，b两个参数构成的参数空间本身是无范围的，这就给离散化带来困难（grid无穷）；
对于垂直直线m的范围为无穷，在参数空间中无法表示；

引入极坐标系解决问题，其中θ∈(0°,180°)，下面是如何将图像空间中的直线上的点转换为极坐标参数空间下的直线并进行投票的算法（也是真正常用的霍夫变换）

3.5.1 噪声影响

在霍夫变换中噪声的影响是非常大的

自身的噪声：峰值变得模糊且难以定位
外界的噪声：随机噪声会导致出现很多伪峰值

解决上述问题主要有如下三种方法：

选取合适大小的grid，即对参数空间进行适当的离散化；
投票的时候采取“软投票”策略：即不仅仅只对中心网格投票，也适当的按照一定比例给网格周围的grid投票；
Canny算子
- 只采用检测出的边上的点进行投票；
- 因为在Candy算子中得到点时就知道了梯度方向，相应的边缘方向的范围就大概确认了，故可以缩小θ的范围，从而解决了噪声的影响，也简化了计算；

于是改进霍夫变换如下

3.5.2 圆拟合

直线空间上的一个点如何推测圆心和半径？（即如何给参数空间投票）

给圆上一点和半径r，可以在参数空间对应两个点（圆心位置为圆周点加减半径，方向由梯度方向确定），圆心必定是投票数最高的地方，此时的(x,y,r)就是圆心坐标和圆半径

在实际的求解中并不知道圆周上每一点(x,y)以及半径，所以需要穷举所有的r（大于0小于图像长度），遍历圆上每一点进行投票；

3.5.3 小结

霍夫变化对参数空间非常敏感，如果空间维度高了霍夫变化的运算量会非常大

4.区域检测-角点

4.1 特征点

文章参考：(15条消息) 区域检测——Harris角点_Wang Yuexin的博客-CSDN博客；

图像处理过程中有一种任务是图像拼接，图像拼接即实现全景拍摄的一种手段，需要分析图片结构提取其特征点；

实现图像拼接具体步骤是什么？提取图像特征点采用的具体算法是什么？下面将介绍

图像拼接主要分为如下三个步骤：

提取特征点
匹配特征点
使用RANSAC方法将两张图片的对应的特征点转换的方式拟合出来，然后对图片采用相同的转换方式进行转换，最后进行拼接

本节主要讲解第一步如何提取特征点，首先要知道什么样的像素点能够充当特征点，主要需要满足如下四个特性：

可重复性：在一张图可以被观测到的，在其他同场景的图也可以被观测到
显著性：检测的特征点需要是在某一类图像中“独有的”，尽量剔除“普遍性”的点，目的是为了将不同类的图区分开
简洁和高效：尽可能的减少计算量，提高计算效率
局部性：特征计算的时候只与局部有关，与全局无关，这样两张图的同一个特征计算出来值才会接近

角点导数在两个及以上方向有变化的点满足上述四个条件，因此通常选择角点作为特征点；

下面介绍如何提取图像中的角点的算法；

4.2 特征提取

与平坦区域的点和边上的点不同的是，角点的导数在两个及以上方向有变化，因此最基本的想法为

使用一个较小的窗口在图像上沿各个方向滑动，该窗口可以包含图像的多个像素点
窗口移动前后不同的差异值显示了窗口内部像素点的信息
图像内部所在的窗口沿各个方向都没有变化（即内部的点的导数变化均为0，表现为窗口前后差异值为0）；边缘所在的窗口沿边缘方向无变化；角点所在窗口会在各个方向上都有显著的变化（即若窗口内含有角点，则该窗口无论沿任何方向移动其前后差异值都不为0）

将上述思想描述为数学公式如下

公式的意思是平移后的窗口与平移前的窗口的对应位置差的平方累加求和，E(u,v)就表示两个窗口内容的差异值的总和，其中

u和v是平移量；
考虑到每个点对窗口影响的不同程度，因此可以乘以窗口权重，赋予不同位置的点的差值对E(u,v)的影响程度；

如何直接建立u,v和E(u,v)之间的关系而不是如上面式子一样需要对应图像像素I(x,y)？这里使用泰勒展开式，在u=0,v=0的点二维泰勒展开

将上述泰勒展开计算并简化后得到

上述公式中Ix、Iy分别表示点在x方向和y方向的偏导，M是一个二阶矩矩阵加权求和；

从矩阵M的公式可以知道，给定一个像素区域即可将矩阵M计算出来，而矩阵M决定了u,v和E(u,v)方程之间的特性，因此将上述问题转换为分析矩阵M；

将上述E(u,v)与u,v的函数方程

绘制如下

该图像沿平行uOv平面截取得到的截面是一个椭圆，这个椭圆可以看作是M矩阵的几何形状：

当Ix和Iy均为0时（表现为窗口沿着任意方向移动前后差异值为0）截面为圆，表示此时窗口位于图像内部；
当窗口沿某一方向的导数为零时（表现为窗口沿着该方向移动前后差异值为0），截面为一个“正椭圆”，此时窗口位于边缘；
当窗口中含有角点（即窗口位于角上），截面椭圆的形状反映了当前窗口中角的特性；

具体对某一个椭圆进行分析，根据M矩阵的形式可以知道椭圆的半长轴反应的是沿该方向导数变化的快慢，半长轴越长则导数变化越快（正椭圆的情况下）

可以看到上述椭圆并不是正椭圆，即x方向的变化与y方向的变化并不能正交（无关），表现在M矩阵中即IxIy和IyIx都不为0，则不能使用前面三种判断方式，简单的，可以使用正交矩阵R对椭圆进行旋转使其成为正椭圆

PS：此处的λ1和λ2分别代表了Ix和Iy；

利用上面定义的λ1和λ2可以定义角点响应函数R

即将λ1和λ2特征转化给R，最终检测某个窗口内是否含有角点的问题就转化为判断R的问题

4.3 Harris检测器

Invariance:特征提取器对进行变换过后的图像（光照、角度）提取到的特征和没有变换之前的图像提取到的特征完全相同；

Covariance:特征提取器对进行变换过后的图像（光照、角度）提取到的特征需要经过一定的处理变换，处理后的特征等于没有变换之前的图像提取到的特征；

拥有了角点检测算法以后，就可以将其与其他方法结合得到特征点检测器，一个经典的特征点检测器为Harris检测器，其基本工作原理为

计算每个像素处的高斯导数
计算每个像素周围的高斯窗口中的二阶矩矩阵M
计算角点响应函数R
设置门限R
寻找响应函数的局部最大值(非最大抑制)

Harris检测器有如下特性：

当光线强度，明暗、像素改变时，只是改变了部分角点的值，还有大部分的点可以用于检测，可以进行检测(Partially invariance)；
当改变位置，角度时，没有改变相对位置，可以检测(Covariance)；
当改变窗口大小时，大窗口下是角点，而小窗口下是线或者边缘，无法检测，此时需要使用其他方法(Not invariance or covariance)；

5.区域检测-Blob检测

参考文章：(5条消息) 区域检测——Blob检测_Wang Yuexin的博客-CSDN博客；

上面说到Harris检测器无法拟合尺度问题，Blob检测的目标是独立检测同一个图像不同缩放版本的对应区域

5.1 拉普拉斯核

拉普拉斯核具备尺度不变性和旋转不变性，它作为工具与其他算法构成比如说Harris-Laplacian或SIFT算法，这些算法是具备检测尺度不变性特征点的；至于为什么使用拉普拉斯算子而不是高斯一阶偏导核，因为只有高斯二阶偏导才能做尺度选择；

拉普拉斯核实际就是边缘检测中提到的[高斯一阶偏导核](#2.4 高斯偏导核)的二阶偏导版本

对不同的图像使用同一个拉普拉斯核(方差为1)进行卷积，得到如下的波纹图

波纹图中二阶偏导为0的点表示信号边缘，即波纹表示边缘信息，当波纹重叠并出现极值（最后一幅图），表示此时的信号和拉普拉斯核对应（尺度选择特性）；

利用上述特性，在实际使用过程中利用拉普拉斯模板去匹配信号，即不断改变Laplacian的参数σ，取处理后的结果达到峰值时的σ，然而简单的增大σ会导致信号卷积后特征消失（因为高斯偏导的面积公式中的σ在分母）

为了防止这种情况需要乘以σ^2^（拉普拉斯核是二阶高斯导数），称为尺度标准化，将标准化后的拉普拉斯核用于卷积信号图像得到如下波纹图

5.2 二维Blob检测

这里我们假设讨论的二维信号都是圆信号（之后会讨论非圆信号，由简到难），用于二维信号的拉普拉斯核的表达式及其图像如下（标准化需要乘以σ^2^）

要使用上述拉普拉斯核对二维圆信号进行检测，拉普拉斯核的方差σ与圆信号的半径有什么关系呢？换句话说，当拉普拉斯核与圆信号匹配得到最大相应的时候，拉普拉斯核与圆信号有什么联系？

为了得到最大相应（即拉普拉斯核与圆信号卷积后的结果最大），拉普拉斯核的零点需要与圆信号对齐 <=> 卷积后响应最大，此时拉普拉斯核的零点与圆信号的边缘是对齐的；

这点比较难以理解，不妨用一维的拉普拉斯核与一维信号解释，只有形式如下的拉普拉斯核与一维信号做卷积得到的结果最大（拉普拉斯核零点与信号边缘对齐），也就是出现波纹重叠的极值，否则正向面积均会被抵消一部分；

这也解释了为什么原始信号与不匹配的拉普拉斯模板进行卷积后不会得到最大响应值；

二维平面中拉普拉斯核的零点方程表示为

化简后得到

即圆半径r与拉普拉斯核的方差之间的关系为

多尺度理论：拉普拉斯核的方差越大则检测的圆信号越大，即大σ检测大信号，小σ检测小信号；

有了上述定义后，将图像的特征尺度r定义为拉普拉斯峰值对应的尺度的根号2倍；

下面举个例子表示拉普拉斯核的具体应用，特征尺度选择过程中将逐步增加参数σ，每个σ 逐像素计算最大响应，每相邻取九个像素取响应值最大的像素，再与上下两层不同尺度的最大相应取最大（即在一个3x3x3共27个的响应值中取最大的响应值对应的像素点和尺度值，这是一种非最大化抑制的思想） – 同一个像素点很可能画出多个圆信号，因为方差越大圆半径越大；

不变性：拉普拉斯核也就是拉普拉斯特征点具备尺度不变性和旋转不变性，因此是invariant的(拉普拉斯特征点无论是缩放还是旋转都是特征点)；但Blob圆的大小会因为缩放和图像旋转改变，因此是covariant的；

5.3 SIFT算法

这个算法的理论难度非常大，所以额外参考了其他教程：

在实际运用过程中，使用Laplacian核可以很好的处理尺度变换的问题，但是需要大量的计算，有两种主流的解决方法：

一种是将Harris与拉普拉斯核结合，只需要在Harris角点周围是否存在尺度空间；
另一种是SIFT尺度不变特征；

SIFT全称为Scale Invariant Feature Transform尺度不变特征变换，SIFT特征对于旋转、尺度缩放、亮度变化等保持不变性，是一种非常稳定的局部特征；

SIFT特征检测的步骤主要分为如下四个步骤：

尺度空间的极值检测：搜索所有尺度空间上的图像，通过高斯微分函数来识别潜在的对尺度和选择不变的兴趣点；
特征点定位：在每个候选的位置上，通过一个拟合精细模型来确定位置尺度，关键点的选取依据他们的稳定程度；
特征方向赋值：基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向，后续的所有操作都是对于关键点的方向、尺度和位置进行变换，从而提供这些特征的不变性；
特征点描述：在每个特征点周围的邻域内，在选定的尺度上测量图像的局部梯度，这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变换；

在介绍SIFT算法之前先介绍DoG模板，一种拉普拉斯模板的替换版本；DoG的函数图像与Laplacian核很相似，具有相似的性质，但使用的是两个高斯差分来定义，大的高斯核可以使用小的高斯核来计算，大大减少了计算量

DoG主要从以下几方面提升拉普拉斯核的效率（后面还会详细解释，这里仅给出结论）：

高斯空间中的模板利用DoG算法直接在前一层的基础上计算，这样就形成一个DoG空间，得到的模板与高斯空间相差一个常数项(k-1)；
计算大尺度的模板时不改变参数值，而改变图像大小，例如：将图像缩小一倍时不改变模板尺度得到效果和不改变图像大小时增大模板尺度的效果相同，那么计算四倍尺度的值就可以直接将图像缩小四倍；
k=2^1/s^，其中s表示要输出的尺度数量，即可利用s来确定k；
模板尺度通常取2的等比数列；

5.3.1 尺度空间

在未知场景中计算机视觉并不能提供物体的尺度大小，其中一种方法是将物体不同尺度下的图像都提供给机器，让机器能够对物体在不同的尺度下有一个统一的认知，因此需要考虑图像在不同尺度下都存在的特征点；

(1)图像金字塔

多分辨率图像金字塔

早期图像的多尺度通常用图像金字塔表示，图像金字塔是同一图像在不同分辨率下得到的一组结果，其生成步骤主要分为两步：

对原始图像进行平滑操作；
对处理后的图像进行降采样（一般是水平、垂直方向的1/2像素）

(2)高斯金字塔

降采样后得到一系列不断尺寸缩小的图像，因为使用的是降采样方案，故图像的局部特征难以保持，也就是无法保持特征的尺度不变性；

因此提出了另一种尺度空间的表现形式 – 高斯尺度空间，在分辨率不变的条件下使用不同的参数来模糊图像；

图像和高斯函数进行卷积可以对图像进行模糊，因此使用不同的高斯核可以得到不同模糊程度的图像，一幅图像的高斯尺度空间可以由该图像和不同的高斯卷积得到

其中的G(x,y,σ)是高斯核函数

称方差σ为尺度空间因子，因为它能够反应图像被模糊的程度，σ值越大图像越模糊，对应的尺度L也就越大，由不同尺度L构成的L(x,y,σ)就是图像的高斯尺度空间；

构建尺度空间是为了能够检测出在不同尺度下都存在的特征点，检测特征点使用的算子就是前面介绍过的拉普拉斯核

因为拉普拉斯核LoG的运算量过大，所以引入了DoG差分高斯来近似计算LoG

其中k是相邻两个高斯尺度空间的比例因子，L(x,y,σ)是图像的高斯尺度空间；

DoG的计算公式表明将相邻的两个高斯空间的图像相减就可以得到DoG的响应图像，因此要得到DoG图像（因为得到DoG图像实际就得到了LoG），首先需要构建高斯尺度空间：高斯尺度空间可以在图像金字塔降采样的基础上加上高斯滤波得到，也就是对图像金字塔的每层图像使用不同的参数σ进行高斯模糊，使每层金字塔有多张高斯模糊过的图像；

PS：降采样的过程中，金字塔上面一组的图像的第一张由其下面一组图像的倒数第三张降采样得到（简单理解就是因为上一组图像的最底层图像由下一组中尺度为2σ的图像进行因子为2的降采样得到）

高斯尺度空间

从上面的高斯金字塔可以看出，高斯金字塔有多组，每组有多层，一组中的多个层之间的尺度是不一样的（即使用的高斯参数σ是不同的），相邻两层之间的尺度相差一个比例因子k；

假如高斯金字塔的每组有S层，则

高斯金字塔的组数一般为

其中o表示高斯金字塔的组数，m，n分别是图像的行和列，系数a可以是0-log2min(m,n)中的任意值，与具体需要的金字塔的顶层图像的大小有关，一般取值为3；

高斯模糊参数σ由下面的关系式得到

其中o为所在的组，s为所在的层，σ0为初始的尺度，S为每组的层数；

同一组内相邻层之间的图像尺度关系为

相邻组之间的尺度关系为

5.3.2 DoG空间极值检测

为了寻找尺度空间的极值点，每个像素点要和其图像域（同一尺度空间）和尺度域（相邻的尺度空间）的所有相邻点进行比较，当其大于（或者小于）所有相邻点时，这个点就是极值点。如图所示，中间的检测点要和其所在图像的3×3邻域8个像素点，以及其相邻的上下两层的3×3领域18个像素点，共26个像素点进行比较（非最大化抑制）；

因为每组图像的第一层和最后一层无法进行比较取得极值，为了满足尺度变换的连续性，需要在每一组图像的顶层继续使用高斯模糊生成3幅图像，因此高斯金字塔每组有S+3层图像，DoG金字塔每组有S+2层图像；

尺度变换连续性：

5.3.3 过滤特征点

通过比较检测得到的DoG局部极值点是在离散空间搜索得到，由于离散空间是对连续空间采样得到的结果，因此离散空间上得到的极值点不一定是真正意义上的极值点，需要将不满足条件的极值点剔除；要剔除掉的不符合要求的点主要有两种：

低对比度的特征点
不稳定的边缘响应点

一般通过尺度空间DoG函数进行曲线拟合寻找极值点，这一步的本质是去掉DoG局部曲率非常不对称的点；

剔除低对比度的特征点

候选特征点x，其偏移量定义为Δx，其对比度为D(x)的绝对值∣D(x)∣，对D(x)应用泰勒展开式

由于x是D(x)的极值点，所以对上式求导并令其为0，得到

然后再把求得的Δx代入到D(x)的泰勒展开式中

设对比度的阈值为T，若∣D(x^)∣≥T，则该特征点保留，否则剔除该特征点；

删除不稳定的边缘响应点

在边缘梯度的方向上主曲率值比较大，而沿着边缘方向则主曲率值较小。候选特征点的DoG函数D(x)的主曲率与2×2Hessian矩阵H的特征值成正比

其中，Dxx,Dxy,Dyy是候选点邻域对应位置的差分求得的。为了避免求具体的值，可以使用H特征值得比例。设α=λmax为H的最大特征值，β=λmin为H的最小特征值，则

其中，Tr(H)为矩阵H的迹，Det(H)为矩阵H的行列式。

设γ=α/β表示最大特征值和最小特征值的比值，则

上式的结果与两个特征值的比例有关，和具体的大小无关，当两个特征值想等时其值最小，并且随着γ的增大而增大。因此为了检测主曲率是否在某个阈值Tγ下，只需检测

如果上式成立，则剔除该特征点，否则保留特征点；

过滤特征点之后SIFI算法还有求取特征点的主方向、生成特征点描述等步骤，但是因为难度较大暂时先放一放，感兴趣参考[转]SIFT特征原理详解及实现 - 简书 (jianshu.com)自学；

5.4 SIFI延展

经过前面的介绍可以知道，经过SIFI算法可以利用DoG将图像中的特征点提取出来，解决了尺度的问题，接下来还存在方向、光照和视角的问题，本节介绍SIFI算法如何解决这些问题；

5.4.1 视角变化

当视角改变时，即使是同一个圆，其中的内容也有很大的差异，因此需要对其进行处理；

具体做法就是借助M矩阵：

先确定一个圆
将圆内的所有像素拿出来计算M矩阵
比较计算出来的λ1、λ2
将较小的λ的方向进行缩小
再将上一步缩小后的区域（椭圆）内的像素拿出来计算M矩阵
重复上述步骤，逐步迭代。直至λ1和λ2 近似相等，说明区域边缘的梯度变化近似一致
将椭圆转换到一样大小的圆中

5.4.2 方向变化

通过仿射自适应变换后，内容基本一致，但方向不同，对应的像素差异较大，无法识别；

使用梯度方向法对圆的方向进行调整：

计算圆内每个像素的梯度强度和方向
将梯度方向量化成八份，给对应的直方图投票，票数就是梯度的大小
统计完之后选择票数最高的方向作为圆内像素整体的梯度方向，将方向转换到0°，将整个圆进行相同的旋转

5.4.3 光照变换

将圆均分成16格，每个格代表一个区域，统计每个区域的方向量化梯度（两化成八个角度，长度代表梯度大小），每个区域中由一个“8位”向量表示，将16个区域的向量拉直就得到一个8*16=128的向量来描述这个圆内的内容，最后比较每个圆的128个数来判断两个圆内容的相似程度

6.纹理表示

参考链接：纹理表示(Texture)_使用高斯偏导核,对图像_Wang Yuexin的博客-CSDN博客；

纹理是指一些基元以某种方式组合起来的，看起来很乱但存在一定内部规律的，物体上的花纹或线条，纹理主要分为规则的纹理和不规则的纹理

6.1 纹理描述

因为纹理是由某些重复的局部模块组成的，所以纹理描述主要分为两个部分：

找到纹理的局部模块
描述每个局部模块的统计信息

对纹理模块的提取主要使用的是前面介绍的高斯核，这里拓展一下多元高斯的概念，不同的协方差矩阵Σ对应了不同高斯核形状

经过不同的变化得到的filter模板如下，形成了filter bank

filter bank中需要添加的filter主要包括检测edges、bars、spots这几类纹理模块的功能，同时这些filter可以检测满足不同比例和方向的纹理模块的要求；

拥有filter bank之后，就可以按照如下步骤对图像进行纹理提取和分类：

使用高斯偏导核，对图像进行卷积，x方向的偏导得到的是竖直纹理，y方向的偏导得到的是水平纹理（其他方向的偏导得到对应的纹理）；
统计各个方向的纹理数量，在图中表示出来，不同的区域映射的是不同的纹理特性；
对统计结果进行K均值聚类即可对图像的纹理类别进行区分；
不同窗口内的点的距离显示了窗口之间的纹理的区别；

6.2 纹理匹配

将对应的卷积核的响应结果求均值，将所得结果组成一个7维度向量，每个向量对应一个纹理，可以将响应结果与纹理进行匹配

实际运用中将采取的纹理与数据库中的纹理进行对比，实现纹理检索与分类

7.图像分割

参考链接：(11条消息) 图像分割(Segmentation)——K-Means, 最小割, 归一化图割_原始 k-means 分割_Wang Yuexin的博客-CSDN博客；

图像分割指的是将图片相似的部分分割成相同的块，也就是将图像中相似的像素组合在一起

图像分割的结果可能有过分割（分割的过于细致）和欠分割（分割的不够细致），这两种情况都不是我们想要的，因此需要有一个适当的图像分割算法；

7.1 Gestalt理论

分割的依据 – Gestalt理论，相似性、连通、平行…

Gestalt理论是解释图像分割的底层理论，即将同一个群组中的图像汇聚在一起的时候，这些图像根据相互之间的关系可以产生新的属性

Gestalt一些常见的分组情况如下，代表了在什么样的情况下群组可以自动汇聚，什么样的情况下群组无法自动汇聚（即能够一眼辨别出的群组类型/高效群组类型）

一个低效的群组可能导致识别的困难，而一个高效的群组可以很轻易的识别，区分一个群组是否高效主要就是看其是否符合上述几类Gestalt分组

Gestalt理论作为图像分割任务的指导理论，以下介绍的几种图像分割算法都是基于该理论；

7.2 K-Means聚类

主要思想：将分割的任务转换为聚类的任务 – 相似的像素属于同一个事物

像素表达：每个像素使用一个多维向量表示，如三维向量(R,G,B)或五维向量(R,G,B,X,Y)。不同的像素表达方式会导致分割的结果不同，三维向量对应语义分割，五维向量对应实例分割

K-Means聚类算法：

首先输入k的值，即希望将数据集经过聚类得到的k个分组；
从数据集中随机选择k个数据点作为初始大哥（质心，Centroid）；
对集合中每一个小弟，计算与每一个大哥的距离（一般选择欧氏距离），离哪个大哥距离近，就跟定哪个大哥；
这时每一个大哥手下都聚集了一票小弟，这时候召开代表大会，每一群选出新的大哥（其实是通过算法选出新的质心）；
- 如果新大哥和老大哥之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），可以认为我们进行的聚类已经达到期望的结果，算法终止；
- 如果新大哥和老大哥距离变化很大，需要迭代3~5步骤；

优点：

非常简单直观的方法；
可能收敛到局部最优值；

缺点：

内存需求较大；
需要指定合理的超参数k；
对初始化的结果非常敏感；
对外点很敏感；
只能检测圆/球形群组；

7.3 Mean-shift聚类

主要思想：可以认为就是寻找密度中心的问题，Mean Shift算法将像素的密度峰值作为初始值，在特征空间中寻找密度的模态或局部最大值；

密度中心：随机选取像素点，向密度较大的区域漂移，迭代直到search window不再漂移

为什么密度中心可以分割图像呢？因为像素点的所有轨迹都会通向具有相同模态的区域

优点：

不只是可以检测圆/球形cluster；
只需要指定一个参数，即检测窗口的大小（检测窗口过小可能卡在局部最优值，太大了导致最终只会出现一个类）；
对外点有鲁棒性；

缺点：

分割结果及其依赖窗口大小；
计算较复杂（一个一个像素的聚类），解决方法是在路径上window中的点一起进入一个类；
对于高维特征表现不是很好（漂移的方向不确定）；

7.4 Images as graphs

主要思想：

节点代表像素；
边代表每对像素之间的联系；
每条边都根据两个节点的亲和力或相似性进行加权；
找到一条边删除，将像素之间的联系切断 – 对切断的边的权值求和使其最小；

边上的权值的定义如下：

拥有了带权图之后，只需要选择一个合适的边切割方法即可；

最小割的思想是将权值最小的边去掉

但是最小割倾向于将像素点单独切割出来，这将导致分割出很多“小块”，因此一般不选择最小割，而是选择归一化图割，归一化图割的核心思想如下

如何具体的实现归一化图割呢？主要流程如下

优点：

可以定义任何的方式来表示像素点；

缺点：

运算量非常大；
归一化图割更倾向于将图像分割成大小相等的部分，不适用于某些分割任务；

8.图像识别

8.1 概述

8.1.1 图像识别的分类

图像识别任务Recognition主要分为图像分类和图像检测：

图像分类：为图像指定标签或类别的任务。例如，猫的图像可以被归类为“猫”，或者汽车的图像可以归类为“汽车”；
图像检测：识别和定位图像中的对象。这通常涉及在感兴趣的对象周围绘制边界框。例如，可以分析街道场景的图像，以检测和定位场景中的所有汽车；

刚好我的项目中有这两个项目，感兴趣可以参考：图像分类，目标检测；

对于图像检测来说，包括以下子任务：

对象检测：对象检测包括识别图像中对象的位置和类别。它通常包括围绕对象绘制边界框，并为其指定标签或类别；
语义分割：语义分割包括根据图像中的每个像素所属对象的类别对其进行分类。换句话说，语义分割根据图像中每个像素所代表的对象为其分配标签。
实例分割：实例分割更进一步，识别和描绘图像中的单个对象，并为每个实例分配单独的标签或标识符。换句话说，实例分割不仅涉及检测图像中的对象，还涉及区分同一对象类的不同实例。实例分割是图像检测的一种更细粒度的版本，它通过识别和分离对象的单个实例来超越简单的对象检测；

除了图像分类和图像检测这两个基本的任务以外，图像识别领域也有更高级的任务，比如事件识别和行为识别。

事件识别和行为识别不仅仅识别图像中的对象，还包括分析对象或个人之间的时间关系和交互。事件识别涉及识别视频或图像序列中发生的特定动作或事件，而行为识别侧重于识别和表征一段时间内的行为模式。

虽然事件识别和行为识别与图像分类和图像检测有关，但它们涉及对视觉数据进行更复杂和细致的分析。它们通常需要使用机器学习算法，这些算法可以随着时间的推移处理和分析视频或图像序列，而不仅仅是单个图像。因此，事件识别和行为识别被认为是视觉识别领域中更高级的任务。

因此，根据不同的目标和使用的方法，图像识别算法最终可分为如下四种：

图像或视频的分类；
物体检测和定位；
估计语义和几何属性；
分析人类行为事件；

8.1.2 图像识别面临的问题

图像识别面临很多问题：需要识别的种类太多、视角变化影响、光照影响、尺寸变化影响、形变影响（如蹲着的猫和站立的猫，解决方法就是喂大量数据）、遮挡（解决方法是提取局部特征进行识别）、背景杂波、intra-class variationin 等。

8.1.3 图像识别的步骤

图像识别一般包含三个环节，其中第一步又包含图像表达和选择分类策略。第二步学习就是机器学习课程讲解的知识点，涉及学习批量、泛化、监督级别等，这里不再赘述。

(1)图像表达和分类策略

（1）图像表达的方式有很多，但无论使用哪种，应当实现的基本目标为图像表达对视角、光照、尺寸、遮挡、杂波、形变有Invariance的特性。

（2）常用的分类策略可分为产生式和判别式。举例说明两者之间的区别，比如当前有任务“识别张三”：

产生式的目标是画出张三，画的越像识别率越高（不需要李四的存在） – 了解内部规律并建模
判别式不需要知道张三和李四长什么样，只需要知道张三和李四之间的差异即可 – 找到内外部的差异并建模

产生式模型

用更加官方的话来说，“判别式建模的是后验概率，产生式建模的是先验概率和似然概率”，什么是先验概率，什么又是后验概率和似然概率呢？（实际上就是贝叶斯公式里的各部分）

常见的判别式模型有SVM、神经网络、Boosting等，常见的生成式模型有朴素贝叶斯、层次贝叶斯等。

(2)Recognition

在确定了图像表达方式、分类策略以及学习方式后，最后就是Recognition，前面也说过识别主要分为分类和检测，分类非常的简单只需要对整图进行类别判断即可；检测稍难，不仅要从整图检测(detection)出物体，还需要识别(recognition)窗口中物体的类别。

检测任务具有滑动窗口问题。检测任务的本质就是判断图像中的每个窗口是否是待检测目标（检测任务实际上也是一个分类任务，只是在一个窗口内的分类）这就要求评判每个窗口的速度尽量快，进而实现实时检测。

滑动窗口的另一个问题是，可能有多个检测窗口都输出真值，需要使用非最大化抑制得到一个检测框。

8.2 图像分类

随着计算机与互联网技术以及数字图像获取技术的快速发展,海量的数字图像出现在互联网上及人们周边的生活中。依靠传统的人工方式对图像进行分类、组织和管理非常耗时耗力，所以希望能够通过计算机对图像中的目标内容进行自动地分析处理，从而将图像数据快速、规范、自动地进行组织、归类和管理。

早期的图像分类主要依赖于文本特征，采用人工方式为图像标注文本，使用的是基于文本的图像分类模式。由于图像标注需要人为地辨识并为其选定关键字，故其分类的效果不是非常理想，且耗时严重。随着计算机技术和数字化图像技术的发展，图像库的规模越来越大，人工标注的方式对图像进行分类已不可能，人们开始逐渐将研究的重点转移到基于图像内容分析的自动分类研究上。

基于内容的图像分类技术不需要进行人工标注的语义信息，而是直接对图像所包含的信息进行处理和分析，利用图像底层视觉特征来进行图像分类。图像分类技术研究是一个集中了机器学习、模式识别、计算机视觉和图像处理等多个研究领域的交叉研究方向。

图像分类任务的常用方法包括：

传统机器学习方法：如分类器、决策树、随机森林等。
- 逻辑回归：用于二分类问题，可以使用sigmoid等激活函数进行参数学习。
- 支持向量机：用于多分类问题，需要正则化，并可以使用核等技巧进行超参数优化。
深度学习模型：其中最常用的是卷积神经网络，如卷积神经网络（CNN）、循环神经网络（RNN）等。

本次实验要求使用支持向量机对图像进行分类，下面是使用支持向量机实现图像分类的一般步骤：

数据预处理：将图像转换为二维数组，并对每个像素进行标准化处理，以消除像素之间的尺度差异。
构建SVM分类器：使用支持向量机算法构建SVM分类器，通常使用径向基函数（RBF）或多项式核（Polynomial Kernel）等核函数。
训练SVM分类器：使用训练数据训练SVM分类器，通常使用交叉验证等方法进行模型选择和参数优化。
使用SVM分类器进行预测：使用训练好的SVM分类器对新的图像进行分类预测。

图像分类常用的是深度学习的模型（毕竟诸如CNN这种能够自动提取图像的局部特征）。但是，这并不妨碍SVM是一个优秀的算法，大量的实践都证明它对于小批量数据集的分类、预测都能够得到较好的效果。

8.2.1 词袋模型概述

参考链接（这一节看文本很难形成直观上的理解，推荐搭配视频）：

视频：09.识别&词袋模型.1080P_哔哩哔哩_bilibili（这个视频只能作为最基本的入门来看，很多描述不准确）；
视觉单词模型、词袋模型BoW - ostartech - 博客园 (cnblogs.com)；
(6条消息) 计算机视觉课程作业基于词袋模型的图像分类算法_蒋_X_X的博客-CSDN博客；

词袋模型BoW在NL和CV领域都有提到，这里我们主要介绍词袋模型在CV领域的使用即BoVW。

词袋模型最初用于文本分类中，然后逐步引入到了图像分类任务中。在文本分类中，文本被视为一些不考虑先后顺序的单词集合。而在图像分类中，图像被视为是一些与位置无关的局部区域的集合（一袋拼图），因此这些图像中的局部区域就等同于文本中的单词。在不同的图像中，局部区域的分布是不同的（一袋“马”的拼图肯定和一袋“牛”的拼图不同）。因此，可以利用提取的局部区域的分布对图像进行识别。

注意这里的“局部区域”，一般指的是具有代表性的图像区域，也就是图像特征，一般使用SIFT提取器提取（当然直接将图像均分为局部区域也可以，但这种做法得到的拼图过多影响后续处理）

图像分类和文本分类的不同点在于，在文本分类的词袋模型算法中，字典是已存在的，不需要通过学习获得；而在图像分类中，词袋模型算法需要通过监督或非监督的学习来获得视觉词典。造成这种差异的原因是，图像中的视觉特征不像自然语言中的单词那样定义明确和被理解。因此，有必要学习一种能够有效地表示图像中特征的视觉词典。

视觉词袋（BoVW，Bag of Visual Words）模型，是“词袋”（BoW，Bag of Words）模型从自然语言处理与分析领域向图像处理与分析领域的一次自然推广。对于任意一幅图像，BoVW模型提取该图像中的基本元素，并统计该图像中这些基本元素出现的频率，用直方图的形式来表示。通常使用“图像局部特征”来类比BoW模型中的单词，如SIFT、SURF、HOG等特征，所以也被称之为视觉单词模型。

图像BoVW模型表示的直观示意图如图所示

利用BoVW模型表示图像，获得图像的全局直方图表示，主要有四个关键步骤：

Step 1：图像局部特征提取（Image Local Features Extrication）。根据具体应用考虑，综合考虑特征的独特性、提取算法复杂性、效果好坏等选择特征。利用局部特征提取算法，从图像中提取局部特征。 – SIFT特征提取器

Step 2：视觉词典构造（Visual Dictionary Construction）。利用上一步得到的特征向量集，抽取其中有代表性的向量，作为单词，形成视觉词典。一般是从图像库中选取一部分来自不同场景或类别的图像来组成训练图像集，并提取其局部特征，然后对训练图像的所有局部特征向量通过适当的去冗余处理得到一些有代表性的特征向量，将其定义为视觉单词。通常所采用的处理方法是对训练图像的所有局部特征向量进行聚类分析，将聚类中心定义为视觉单词。所有视觉单词组成视觉词典，用于图像的直方图表示。 – K-means聚类

Step 3：特征向量量化(Feature Vector Quantization)。BoVW模型采用向量量化技术实现，向量量化结果是将图像的局部特征向量量化为视觉单词中与其距离最相似的视觉单词。向量量化过程实际上是一个搜索过程，通常采用最近邻搜索算法，搜索出与图像局部特征向量最为匹配的视觉单词。 – KNN最近邻聚类

Step 4：用视觉单词直方图表示图像，也称为量化编码集成(Pooling)。一幅图像的所有局部特征向量被量化后，可统计出视觉词典中每个视觉单词在该图像中出现的频数，得到一个关于视觉单词的直方图，其本质是上一步所得量化编码的全局统计结果，是按视觉单词索引顺序组成的一个数值向量（各个元素的值还可以根据一定的规则进行加权）。该向量即为图像的最终表示形式。

上述步骤很抽象，下面举一个例子来帮助理解：

现在我们有如下三张原始图像

原始图像

第一步是做局部特征提取，假设使用SIFT特征提取器提取到了如下这些特征（可以认为是拼图，我们将三张原始图像的拼图都放在一个袋子中，这就是我们的“词袋”）

第二步是视觉词典构造，也就是从上述那么多特征中选取k个单词来构成视觉词典，这里的k由人为规定（一般需要先验知识）。使用K-means聚类算法将词袋中的拼图聚为k个类，k个类别中心的拼图就是k个单词（假设我们令k=4）

视觉词典

第三步和第四步通常合并进行，即对词袋中的每个拼图都使用最近邻算法，寻找与其最近的在视觉词典中的单词（我们认为这两张图像属于同一个单词），找到之后对直方图中该单词的频数+1。因为我们有三张原始图像，所以对应有三个直方图，每个直方图的横轴为视觉词典中的单词，纵轴为该单词出现的频数，因此对原始三张图像的直方图表示如下

直方图表示

Q：K-means聚类和KNN最近邻有什么区别？

A：回答参考KNN和K-mean有什么不同？ - 知乎 (zhihu.com)；

KNN
- 分类算法
- 监督学习
- 数据集是带Label的数据
- 没有明显的训练过程，基于Memory-based learning
- K值含义 - 对于一个样本X，要给它分类，首先从数据集中，在X附近找离它最近的K个数据点，将它划分为归属于类别最多的一类
K-means
- 聚类算法
- 非监督学习
- 数据集是无Label，杂乱无章的数据
- 有明显的训练过程
- K值含义- K是事先设定的数字，将数据集分为K个簇，需要依靠人的先验知识

8.2.2 词袋模型+SVM图像分类

词袋模型的概念介绍完毕，下面通过“词袋模型+SVM图像分类”任务来介绍其中涉及的知识点（这是一个最基本的词袋模型的运用），即SIFT特征提取器、K-means算法、KNN算法以及最终进行图像分类需要使用的SVM模型（以下知识点都是之前学习过程中自己总结的，如果有看不懂的也可以自行Google）

完整的项目链接在图像分类，涉及的知识点链接都在下面：

[SIFT特征提取器](# 5.3 SIFT算法)；
K-means聚类；
KNN算法；
SVM支持向量机；

要实现基于词袋模型的图像分类，大致分为如下四步：

特征提取与描述子生成：一般选择SIFT特征提取器，SIFT特征具有放缩、旋转、光照不变性，同时兼有对几何畸变，图像几何变形的一定程度的鲁棒性；
词袋生成：词袋生成基于描述子数据的基础上，生成一系列的向量数据，最常见就是首先通过K-Means实现对描述子数据的聚类分析，一般会分成K个聚类、得到每个聚类的中心数据，就生成了K单词，根据每个描述子到这些聚类中心的距离，决定了它属于哪个聚类，这样就生成了图像的直方图表示数据。
SVM分类训练与模型生成：使用SVM进行数据的分类训练，得到输出模型；
模型使用预测：加载预训练好的模型，使用模型在测试集上进行数据分类预测；

8.3 图像检测

参考资料：

(7条消息) 机器学习: Viola-Jones 人脸检测算法解析(一)_vio-jones算法_Matrix_11的博客-CSDN博客；
[(7条消息) 机器学习: Viola-Jones 人脸检测算法解析(二)_violajones算法_Matrix_11的博客-CSDN博客](https://blog.csdn.net/matrix_space/article/details/53892765?ops_request_misc=&request_id=&biz_id=102&utm_term=Viola-Jones 人脸检测算法解析&utm_medium=distribute.pc_search_result.none-task-blog-2~~all~~sobaiduweb~default-1-53892765.142^v88^insert_down38v5,239^v2^insert_chatgpt&spm=1018.2226.3001.4187)；
HOG特征详解与行人检测-腾讯云开发者社区-腾讯云 (tencent.com)；

8.3.1 人脸检测

在人脸检测邻域，Viola-Jones算法非常经典。Viola-Jones算法在2001年的CVPR上提出，因为其高效而快速的检测即使到现在也依然被广泛使用。VJ算法包含以下几个重要的部分：

利用 Haar 特征描述人脸的共有属性；
建立了一种称为积分图像的特征，并且基于积分图像，可以快速获取几种不同的矩形特征；
利用 Adaboost 算法进行训练；
建立层级分类器；

(1)Harr特征

一般来说，人脸会有一些基本的共性，比如眼睛区域会比脸颊区域要暗很多、鼻子一般属于脸部的高光区域因而鼻子会比周围的脸颊要亮很多、一张正脸图像，眼睛，眉毛，鼻子，嘴巴等的相对位置是有规律可循的。Haar特征考虑的是某一特定像素点相邻的矩形区域的特征，这需要将整个矩形区域内的像素相加然后再做减法运算。一般的，有以下几种Harr特征算子

普通的特征都是针对单一像素，Harr特征是针对矩形区域，因此计算时需要先将每个矩形区域的像素进行求和，然后再使用上面的算子进行计算

(2)积分图像

为了计算Harr特征，需要先对矩形区域内的所有像素求和。而一张图像中的像素形成的矩形区域形状、大小不定，因此如果使用常规的对每个矩形区域内的像素进行遍历求和的方法会导致很大的运算量。下面引入这样一种数据结构，称为积分图像。积分图像的原理非常简单，即对积分图像中的任何一点，该点的积分图像值等于该点在原图中的点左上角的所有像素值之和，表达式如下

积分图像与原图之间满足如下关系

其中I表示积分图像，f表示原图，x,y表示像素点的坐标。因此，一张图像的积分图像记录了这张图像上每一个像素点其左上角所有像素的和。如果把一张图像的左上角看做坐标原点，那么上面的表达式就是原点到该像素点之间的所有像素点的离散求和，这可以看成是一种积分，所以这也是积分图像名称的由来。利用积分图像，可以非常快速的计算一张图像上任意一个矩形区域内的像素和

这意味着，原图中任意一个矩形区域的像素和，都可以由上述运算法则求解。

在VJ人脸检测中，主要使用了三种不同的矩形特征（Harr特征中的其中三个），分别是二邻接，三邻接，四邻接矩形，矩形的Value计算公式为

因为一个矩阵需要使用四个点来计算/表示，进而二邻接矩形需要六个点表示，三邻接矩形需要八个点，而四邻接矩形需要九个点表示。

下面来计算给定一张图像，能够得到多少个矩形特征。

VJ算法中使用的图像大小都是24*24的图像大小。考虑水平方向和垂直方向二邻接矩形有两种情况1×2和2×1，三邻接矩形也有两种情况1×3和3×1，而四邻接矩形只有一种情况2×2。

下面列出每种矩阵可能的size：

二邻接矩阵：
三邻接矩阵：
四邻接矩阵：

根据卷积定理，一个大小为W*H的图像与大小为m*n的filter做卷积，新生成的图像大小为(W-m+1)*(H-n+1)，这意味着新图像有多少个像素，则对应原图有多少个m*n大小的矩形。

计算过程省略，最终一个24*24大小的图像会产生162336个矩形特征，这个维度远远高于图像本身的维度，因此不可能将这些特征全部使用，需要使用Boost来做特征选择与训练。

(3)Boost训练

前面已经说过，VJ人脸检测算法使用的特征就是基于积分图像的矩形特征，也称为Harr特征。一张图像生成的Harr特征集远高于图像维度，下面介绍使用Boost做特征选择和分类器训练。

Boost可以同时进行特征选择与分类器训练，简单来说，Boost就是将一系列的”弱”分类器通过线性组合，构成一个”强”分类器

其中h(x)就是一个强分类器

而hj(x)就是“弱”分类器，hj(x)本质上是一个简单的阈值函数

规定：给定N个训练样本(x^i^,y^i^)，其中含有m个正样本，l个负样本。如果x^i^是人脸图像则y^i^=1，否则y^i^=0。

基于Boost的训练算法具体流程如下：

θj门限是在第1步确定的，简单理解就是选择什么样的θ能够使得该弱分类器效果最好（正确率最高）；
β是一个小于1的数，权重更新会导致权重越来越小，这意味着搞不定的样本的权值不变，搞定的权值的样本减小（变相增大搞不定的样本的权值）；
α权重决定了最终该弱分类器在整个Boosting组合中的重要程度，与β成反比，与分类错误率ε成正比；
上述步骤2，3，4会一直循环，直到生成的强分类器的性能达到要求，此时选择的弱分类器就是前面162336个矩形特征中被选中的特征（即此处的特征和弱分类器是等价的）；

(4)层级分类器

在一张正常的图像中，包含人脸的区域只占整张图像中很小的一部分，如果所有的局部区域都要遍历所有特征的话，这个运算量非常巨大，也非常耗时，所以为了节省运算时间，应该把更多的检测放在潜在的正样本区域上。所以有了层级分类器的概念，层级分类器就是为了将任务简化，一开始用少量的特征将大部分的negative 区域剔除，后面再利用复杂的特征将 false positive 区域剔除。

在层级分类器架构中，每一层级含有一个“强”分类器（也就是上一步中Boosting学习得到的强分类器），同时所有的矩形特征被分成几组，每一组都包含部分矩形特征，这些矩形特征用在层级分类器的不同阶段。层级分类器的每一阶段都会判别输入的区域是不是人脸，如果肯定不是，那么这个区域会被立即舍弃掉，只有那些被判别为可能是人脸的区域才会被传入下一阶段用更为复杂的分类器进一步的判别。其流程图如下所示:

处于cascade层级分类器前端的分类器分类速度较快，可以拒绝大部分负样本并且检测出几乎所有的正样本（正样本一定要通过，负样本在可接受范围内可通过一定数量）；
处于cascade层级分类器后端的分类器分类速度较慢，但是大多数区域样本几乎无法到达；

每个层级的矩形特征都比较简单。下面的两种特征可以达到100%的检测率，但是也会产生很多的 false positive，一般来说是 50%的FP rate。但是这两种特征对 negative 区域的识别非常高效，所以层级分类器的第一层基本都是用这两种特征加上一个”强”分类器先将大量的negative 区域剔除。对于 false positive 的处理，有赖于后面阶段更多的特征及分类器。

层级分类器总的识别率D或false positive F是每一层的分类器的识别率d和false positive f的乘积

一个层级分类器，应该综合考虑以下几个因素：

层级分类器的层次，即需要多少个分类器；
每一层分类器需要测试的特征数ni；
每一层分类器的阈值；

8.3.2 行人检测

(1)HOG概述

HOG特征全称方向梯度直方图特征，在对象检测与模式匹配中是一种常见的特征提取算法，是一种基于本地像素块进行特征直方图提取的一种算法，对象局部的变形与光照影响有很好的稳定性，最初是用HOG特征来来识别人像，通过HOG特征提取+SVM训练，可以得到很好的效果。HOG特征提取的大致流程如下

1.灰度化：对HOG特征提取来说第一步是对输入的彩色图像转换为灰度图像，图像灰度化的方法有很多，不同灰度化方法之间有一些微小的差异，从彩色到灰度的图像转换可以表示如下

2.计算图像梯度：计算图像的X方向梯度dx与Y方向梯度dy，根据梯度计算mag与角度，计算梯度时候可以先高斯模糊一下(可选)，然后使用sobel或者其它一阶导数算子计算梯度值dx、dy、mag、angle

3.Cell分割与Block对于图像来说，分成8x8像素块，每个块称为一个Cell，每个2x2大小的Cell称为一个Block，每个Cell根据角度与权重建立直方图，每20度为一个BIN，每个Cell得到9个值、每个Block得到36个值(4x9)，图像如下

每个Block为单位进行L2数据归一化，作用是抵消光照/迁移影响，L2的归一化的公式如下

4.生成描述子：对于窗口64x128范围大小的像素块，可以得到8x16个Cell，使用Block在窗口移动，得到输出的向量总数为7x15x36=3780特征向量，每次Block移动步长是八个像素单位，一个Cell大小

(2)HOG+SVM行人检测

基于HOG特征和SVM分类器的行人检测的基本流程如下

训练过程中正样本为图片中包含有目标区域(行人)的boundingbox，尺寸统一为检测窗口的大小即64×12864×128，负样本不需要统一尺寸，只需比检测窗口大，且图片中不包含检测目标，可任意截取图片中64×12864×128大小的区域提取HOG特征作为负样本的特征向量，并与正样本图片中boundingbox区域提取出的HOG特征向量一起训练，得到SVM的分类模型。

检测过程中采用滑动窗口法，检测窗口尺寸固定不变，对待检测图片进行尺度缩放，在每一层的图像上，用固定大小的滑动窗口提取HOG特征，并根据训练好的分类模型判断检测窗口是否为目标(行人)。因此HOG + SVM进行行人检测的过程实际上就是对图像的检测窗口提取HOG特征进行分类判决的过程。

8.4 物体追踪

因为时间原因可能不能学到这部分知识点，但是相对来说这个知识点网上的参考资料挺多的，之后有时间了可以结合资料自学

9.三维重建

（这一章开始其实视频就讲的不是很好了，一方面课程难度增大，另一方面可能老师备课不是特别充足，推荐先看一遍文本知识熟悉概念再看视频）

9.1 摄像机几何

参考资料：

摄像机几何全称为摄像机几何成像模型，其意义在于使用数学公式描述了三维空间中一点与二维图像中一点的关系。摄像机几何主要涉及四个坐标系，这也是整个三维重建部分最基础、最核心的部分。

9.1.1 四大坐标系

四大坐标系包括世界坐标系、相机坐标系、图像坐标系和像素坐标系，通过建立它们之间的位置关系可以实现二维平面上一点与三维空间中一点的坐标的互相转换。

坐标系	描述
世界坐标系	世界坐标系是建立在真实世界中的坐标系，单位为米。
摄像机坐标系	以相机设备的光心Oc作为摄像机坐标的原点位置，单位为米。其横、纵坐标分别与图像坐标系的横、纵坐标平行，但是摄像机坐标系的Z轴为摄像机的光轴。
图像物理坐标系	图像物理坐标系以图像中心（或像平面与摄像机光轴的交点）作为原点位置，单位为毫米。横坐标与纵坐标分别平行于摄像机坐标系的横坐标与纵坐标，描述了像素的实际位置。
图像像素坐标系	图像像素坐标系以图像左上角的像素点Oo作为原点，单位为像素，其横纵坐标与图像物理坐标系的横纵坐标分别平行。

(1)摄像机坐标系&图像物理坐标系

这是最简单的以“小孔成像”为原理的针孔摄像机的的原理

从3D到2D的转换过程中会遗失角度以及距离的信息。

假设P的三维坐标为[x,y,z]，其在物理坐标系中对应的坐标为[x’,y’]，则两个坐标之间有如下关系（相似三角形）

等价于

将上述欧式坐标关系式转换为齐次坐标关系式如下

上述等式的右边常常写作如下形式

看起来仅仅只是将常数z提取出来，实际上表达的意思多了一层：对二维图像物理坐标系中的一个点坐标，其对应的三维坐标有无数种可能，只要保证在投影线上即可（这也是引入齐次坐标的一个意义）

(2)摄像机坐标系&像素坐标系

一般来说在摄像机中存储的都是数字图像，因此需要将像平面（图像物理坐标系）转换到像素坐标系，也就是三维空间中的物体直接通过小孔投影到像素坐标系中（此处的像素坐标系的原点取的是图像左下角）。从像平面到像素平面的转换需要既需要考虑原点之间的偏置，也需要考虑单位之间的变换以及摄像机偏斜（摄像机内置参数，主要为α、β、θ、cx、cy）。为了保证变换的线性性质，引入齐次坐标（简单理解就是在欧式坐标的基础上增加一个维度，齐次坐标变为欧式坐标直接减少最后一个维度同时其他维度除以该维度的值），在下面的介绍中，没有特殊说明以外，默认使用的都是齐次坐标。

(3)世界坐标系&像素坐标系

不同摄像机坐标系对于真实世界中三维物体的描述都不同，因此更好的方式是在真实世界中选定一个世界坐标系来描述真实物体。摄像机坐标系和世界坐标系的变换关系为旋转R(绕x,y,z轴旋转)和平移T(绕x,y,z轴移动)（R和T称为摄像机外参数）

9.1.2 坐标系转换

若已知摄像机的内参数和外参数（实际情况是这些参数一般都未知，这就是之后相机标定解决的问题），将空间内任意一点P从世界坐标下的描述变为像素坐标下的描述，一共需要经过三次坐标变换，坐标系之间的转换关系如下所示

(1)世界坐标系->摄像机坐标系

刚体变换是指在变换过程中物体不会出现形变，只进行旋转变换和平移变换。坐标转换关系如下

其中(XW,YW,ZW)为P点在世界坐标系中的坐标，(XC,YC,ZC)是P点在摄像机坐标系中的坐标，R是3*3的旋转矩阵，T是3*1的平移矩阵。上述式子转换为矩阵形式如下

(2)摄像机坐标系->物理坐标系

摄像机坐标系与图像坐标系之间的转换关系使用透视投影来描述。一般规定图像坐标系的原点是成像平面与摄像机光轴之间的交点，且其x,y轴与摄像机坐标系的X,Y轴平行。由理想的针孔成像原理可以得到如下坐标转换关系式（相似三角形）

上述式子中的f是摄像机的焦距，是一个固定的参数，由摄像机自身决定。上述式子写为矩阵的形式如下

(3)物理坐标系->像素坐标系

假设在像素坐标系中有一个点p，其在x轴和y轴方向上的尺寸分别为dx和dy，则图像物理坐标系和图像像素坐标系之间的转换关系式如下

上述式子中的dx和dy分别表示一个像素在x方向和y方向表示多少毫米。上述式子写为矩阵形式如下

(4)世界坐标系->像素坐标系

联立上述三个转换式子中的三个矩阵表达式，可以将世界坐标系中任意一点P转换到像素坐标系中，转换关系式如下

其中M1为摄像机的内参数矩阵(也称为标定矩阵)，M2为摄像机的外参数矩阵，由旋转矩阵R和平移矩阵T构成。M1和M2组成的矩阵统称为投影矩阵，通过投影矩阵，可以直接将一个齐次的世界坐标系坐标投影到二维齐次像素坐标系坐标。

9.1.3 畸变

畸变是指对直线投影的一种偏移，简单理解就是一条三维空间中的直线投影到二维平面上发生了弯曲，这就称为畸变（更准确的说应该是光学畸变，是由于摄像机的镜头导致）

畸变一般分为径向畸变和切向畸变：

径向畸变来自于摄像机使用的透镜；
切向畸变来自整个摄像机的组装；

无论是哪种畸变，都属于相机本身的固有特性，与摄像机的内部参数一样，在进行摄像机标定之后即可正常使用。当然还存在其他畸变，但是效果没有径向畸变和切向畸变显著，因此很少被关注。

(1)径向畸变

径向畸变包括枕形畸变和桶形畸变，实际的透镜总是会在成像仪的边缘产生显著的畸变。

其中桶形畸变一般发生在使用广角镜头或使用变焦镜头的广角端时，枕形畸变则是使用长焦镜头或使用变焦镜头的长焦端时发生。

如下图，光线在原理透镜中心的地方比靠近中心的地方更加弯曲。对于常用的普通透镜来说，这种现象更加严重。筒形畸变在便宜的网络摄像机中非常厉害，但在高端摄像机中不明显，因为这些透镜系统做了很多消除径向畸变的工作。

对于径向畸变，成像仪中心（光学中心）的畸变为0，随着向边缘移动，畸变越来越严重。

使用数学形式表示径向畸变，首先假定归一化平面上有一点p，其坐标为[x,y]^T^，对应的极坐标形式为[r,θ]^T^，其中r表示该点与坐标原点的距离，θ表示与水平轴的夹角。径向畸变就是r发生了变化，畸变后的坐标表示为

此处的k1,k2和k3就是径向畸变参数。

(2)切向畸变

切向畸变是由于透镜制造上的缺陷或摄像机组装上的问题使得透镜本身与图像平面不平行而产生

切向畸变可分为薄透镜畸变和离心畸变

其中的p1,p2就是切向畸变参数。

综合径向畸变和切向畸变的公式，最终可以得到5个畸变参数

9.2 摄像机标定

参考链接：

相机标定就是根据某些方法确定出相机的内参数和畸变参数（实际上在这个标定的过程中是可以获取到摄像机的外部参数的如相机的位置和姿态）

摄像机标定的过程可以描述为通过标定板，得到n对世界坐标三维点Xi和图像坐标二维点xi，这些三维点到二维点的转换都可以通过相机内参、相机外参以及畸变参数经过一系列的矩阵变换得到。

摄像机标定的意义在于，因为每个镜头的畸变程度不同，通过相机标定可以求解相机的内部参数和畸变参数以此来矫正这种镜头畸变

摄像机标定的步骤主要如下：

1、打印一张棋盘格，把它贴在一个平面上，作为标定物。
2、通过调整标定物或摄像机的方向，为标定物拍摄一些不同方向的照片。
3、从照片中提取棋盘格角点。
4、估算理想无畸变的情况下，五个内参和六个外参。
5、应用最小二乘法估算实际存在径向畸变下的畸变系数。
6、极大似然法，优化估计，提升估计精度。

摄像机标定的过程实际上就是使用线性方法求解方程式，主要分为不考虑畸变和考虑畸变两种情况考虑

9.2.1 不考虑畸变

假设现有三维坐标点Xi以及其对应的二维图像物理坐标点xi，两种坐标的表达形式都是使用齐次坐标表示的。目标是估计投影矩阵P=M1M2，由于三维坐标点和二维坐标点的共线性，有如下关系成立

写作矩阵形式即

此处的p^T^j表示矩阵P的第j行，共线使用叉积表示即

写作矩阵乘积的形式为

投影矩阵实际的参数是12个，但是因为尺度任意，因此只需要求解11个自由度。1对3D-2D的对应点可以提供2个线性等式（因为矩阵形式的秩为2），为了求解投影矩阵，需要至少6对3D-2D的对应点。如果数据点多于6对，可以增强结果的鲁棒性。

假设现在我们已经拥有多个数据对，根据上述方法可以写作如下形式

将上述式子简单记作

很明显，p=0是方程的一个解，但是该解不是我们想要的，因此需要增加约束||p||=1，因此上述式子的完整约束形式为（齐次最小二乘形式）

要求解上述式子，基本的解法步骤如下

上面最后一步意思是要求解的p就是A^T^A最小特征值对应的特征向量，而要找A^T^A的最小特征值，就需要计算A的最右边的奇异向量（具体原因参考相机模型与标定 | SuperZLW’s Blog）

相机标定只要求内参，而求解出的投影矩阵既包含内参又包括外参，因此求解出投影矩阵P之后还需要继续向下求解，也就是通过投影矩阵求解标定矩阵

求解出的投影矩阵P是一个3*4的矩阵，将它按照如下方式分解：

此处的矩阵M是一个3*3的矩阵，m是一个3*1的矩阵。进一步的将M进行QR分解为一个上三角矩阵K和一个正交矩阵R，此处的K就是要求的标定矩阵，R是外参旋转矩阵。

最后，只需要通过SVD找到c作为P的零空间，即完成不考虑畸变的标定。

9.2.2 考虑畸变

不考虑畸变的情况只是特殊情况，一般现实中是不能忽略畸变参数的。

考虑前面介绍的径向畸变和切向畸变，一个畸变后的坐标应该是如下形式

畸变无法直接求解，可以考虑使用优化的思想，目标函数使用最小化重投影误差，也就是将空间坐标点按照估计的投影方程投影到图像上，得到像素估计值，使该值与实际观测值之间的误差最小。

其中变量初始值设置为：畸变参数为0，其余参数参考无畸变情况下的标定结果。

需要优化的变量不只是畸变参数，还有其他内参。

9.3 三维重建基础

参考资料：

三维重建既可以使用单视图也可以使用多视图，但是使用单视图需要有场景的先验信息如点的对应关系、线面几何以及深度等。因此一般情况下，基于多视图的三维重建的适用范围优于单视图，下面主要介绍的是基于两视图的情况以及其包含的几何关系。

三维重建的几个关键问题：

摄像机几何：从一张或多张图像中求解摄像机的内、外参数（摄像机标定）
场景几何：通过二张或多幅图寻找3D场景坐标（三角测量或多几何视图）
对应关系：已知一个图像中的p点，如何在另外一个图像中找到p’点（极几何约束）

9.3.1 三角测量

三维重建的基础可以看作是一个三角化问题（当然也可以看作是一个多几何视图问题）

三角测量的目标在于，给定一个三维点在两个或多个投影矩阵M已知的图像中的投影，期望通过投影找到该点的坐标。

以两张图像的投影为例，如下图（其中x1和x2分别为X在两个投影面上的投影点）

因为投影矩阵M已知，因此O1x1和O2x2都可以求解出来，进而很容易求解出该空间三维点（两个直线的交点）。然而这种情况的前提是两条直线能够相交，而实际上由于噪音和数值误差，这个条件一般都无法满足，既更一般的情况如下

基于上述情况，一个基本的思想是找到连接两条直线的最短线段，该线段的中点就是三维点X。具体操作为：

寻找线段的方向(即同时垂直于两条射线)；
构造两个平面，每个平面都包含该线段以及一条射线；
将该平面与其它射线相交以产生线段的端点；
找到中点；

现在已知的条件是x1,x2和内参数矩阵K1,K2和旋转平移矩阵R,T。利用上述思想求解点X主要有两种方法，线性法和非线性法。

(1)线性法

线性法的精度不高但是容易求解，只需要求解一个齐次线性方程组，使用SVD分解即可解出

对于多余两个视图的情况，只需要多列几个方程并求解即可

(2)非线性法

非线性法的基本思想是希望能够找到一个X以最小化如下式子（其中P1和P2分别是两个摄像机的投影矩阵）

也就是说找到的三维点投影到图像上的点，要与真实观测点的投影点的距离最小，即最小化

如果将世界坐标系的原点设置在O1处，则两个投影矩阵可以表示为

只需要通过迭代求解即可，一般使用高斯牛顿法或L-M法求解，此处不过多介绍，感兴趣可自行Google。

9.3.2 极几何约束

极几何描述了同一场景或物体的两个视点图像间的几何关系

(1)极几何概念

在介绍极几何约束之前先介绍几个基本的极几何概念

极平面(Epipolar plane)：三点确定一个平面，这三点分别是三维点P和两个相机的中心点O1,O2；
基线(baseline)：O1与O2的连线；
极线(epipolar lines)：极平面和像平面的交线，即p1e1和p2e2；
极点(Epipole)：基线O1O2与像平面的交点，即e1,e2（可以在可见区域以外）

关于极几何有几个比较重要的性质

极平面相较于基线O1O2；
极线相交于极点e和e’；

这两个性质显而易见，比较简单

p1对应的点落在极线p2e2上；
p2对应的点落在极线p1e1上；

这两个性质表明，寻找像点在另一个平面的对应点，不需要整图寻找，只需要在极线上找即可

这里有几个极几何的特例

（1）平行视图

两个图像平行；
基线平行于图像平面，两极点位于无穷远处；
极线平行于图像坐标轴的其中一条轴；

（2）前后平移

两幅图极点位置相同，极点称为展开焦点；

现在的问题是，需要知道一个图中的点与另一幅图中的点的对应关系，也就是极几何约束的目的

从上图可以得到以下关系（如下三个关系都是等价的，只是表示方式不同）

主要分为两种情况考虑：本质矩阵情况和基础矩阵情况

极几何约束本质上可以归纳为两个矩阵，也就是本质矩阵和基础矩阵 – 本质矩阵和基础矩阵是cv领域中用于描述两个摄像机之间的几何关系的矩阵：

基础矩阵是在单目视觉中描述两个图像之间的几何关系的矩阵。它表示了在一个图像中的点与另一个图像中的点之间的对应关系。基础矩阵可以通过至少七对对应点的坐标计算得到。

本质矩阵是在双目视觉中描述两个摄像机之间的几何关系的矩阵。它包含了相机的内部参数和相对运动的信息。本质矩阵可以通过基础矩阵和相机的内部参数来计算得到。

(2)本质矩阵

本质矩阵对规范化相机拍摄的两个视点图像间的极几何关系进行代数描述。下面首先对本质矩阵进行推导，原文链接：(10条消息) 【三维重建】三维重建学习笔记（4）—— 三维重建基础与极几何_Quentin_HIT的博客-CSDN博客。

关于本质矩阵有如下性质

(3)基础矩阵

一般情况下我们的相机都不是规范化的相机，而是普通的一般化相机，不适用于上面的情况，这时候就引出了与本质矩阵相对的“基础矩阵”。基础矩阵对一般的透视摄像机拍摄的两个视点的图像间的极几何关系进行代数描述。基础矩阵的推导思想是将透视摄像机变换到规范摄像机

基础矩阵有与本质矩阵类似的如下性质

基础矩阵只和内参数相关，本质矩阵不仅和外参数相关，和内参数也相关

9.3.3 基础矩阵估计

原文链接：(10条消息) 【三维重建】三维重建学习笔记（4）—— 三维重建基础与极几何_Quentin_HIT的博客-CSDN博客；

基础矩阵可以通过本质矩阵和相机内部参数来计算得到，因此此处仅介绍基础矩阵的估计方法。

(1)八点算法

基础矩阵有7个自由度，理论上只需要7个点就可以求解，但是这样求解非常负责且得到的解是非线性解，因此一般使用8个点求解，俗称“八点估算法”

(2)归一化八点法

9.4 运动结构恢复

参考链接：(12条消息) 【三维重建】三维重建学习笔记（5）—— 双目立体视觉系统_三维重建三角化_Quentin_HIT的博客-CSDN博客（这哥们总结的公式特别到位）；

Q：运动恢复结构和摄像机标定的关系？

A：

摄像机标定是指通过对相机的内部和外部参数进行估计，以及确定图像中的特定点在现实世界中的位置，从而建立图像坐标与物理坐标之间的关系。相机的内部参数包括焦距、主点坐标等，而外部参数则包括相机的位置和姿态。通过标定，可以将图像中的像素坐标转换为三维物理坐标，从而实现图像测量、物体重建等应用。

运动结构恢复是指从一系列图像中恢复相机和场景的三维运动和结构信息。通过对图像序列中的像素点的运动进行分析，可以估计相机的运动轨迹，并且根据这些信息还原出场景中的三维结构。常用的运动结构恢复方法包括多视图几何和[三角测量](# 9.3.1 三角测量)等（简单理解运动结构恢复就是将三角测量应用在实际的三维重建任务中，三角测量是运动恢复结构的基础，与其他方式结合形成有效的方法）。

这两个问题之间存在密切的关系。在进行运动结构恢复之前，通常需要进行摄像机标定，以获得准确的相机内部和外部参数。标定结果对于恢复准确的相机运动和场景结构至关重要。另外，标定和运动结构恢复的过程中所使用的数学模型和算法也有一定的重叠，比如使用相似的投影模型、优化方法等。

总之，摄像机标定提供了相机的内部和外部参数，为运动结构恢复提供了必要的输入信息；而运动结构恢复则利用标定结果，从图像序列中恢复相机和场景的三维运动和结构信息。