引言

刚结束可能是我学生时代最后一场考试了，orz热乎着，记录一下。
这门课是学校新开的，叫《计算机图形图像》，没讲传统的图形学，是偏向计算机视觉去了。
网上复习资料太少了，这两周断断续续看的PPT、教材、提纲、博客都列举在“我的参考”里。
后面自己整理了几个以为会考的重要的简答题…

我的复习参考

• PPT来源：16-385 Computer Vision, Spring 2020
• 教材：
  • 英文版：SzeliskiBookDraft.pdf；
  • 中文版：计算机视觉-算法与应用中文版.pdf
• 整理得符合这课所学的中文期末笔记（简答题 流水线）计算机视觉期末笔记
• 复习提纲：ECS 174: Computer Vision, Final exam study-guide
• 简答题：山东大学软件学院计算机视觉（考试）——期末考试回忆版
• 试卷大题样例：CS 4495/7495 Computer Vision Final Exam
• 试卷大题样例-Cambridge：Past exam papers: Computer Vision

期末考试考题回忆

考了6个全跟农学相关背景的题，5个应用题（都是让你设计算法实现），1个计算题。

1. （识别、测距）无人机两个摄像头两个图片流，怎么智能采摘苹果吧。
2. （计算题）在离地面1万米高空的飞机上看到正下方有云，飞机以3600km/h飞（好像吧），10s后，看到云在左斜后方45°，求云离地高度。
3. 农药喷洒，得到俯视图，有杂草、作物、地面，只喷杂草。
4. 巨大的高清森林图（宽度、高度），某处的树冠图，怎么找到它？
5. （图像分割）大白菜和土壤背景。
6. 视频里给人头上戴个帽子，人动，帽子跟着动，用到了哪些AR（是这个缩写吗？）技术实现的？

PPT对应中文笔记整理

PPT来源：16-385 Computer Vision, Spring 2020
内容列表：

1. 色彩
2. 图像滤波
3. 图像金字塔
4. 霍夫变换
5. 特征与边角识别
6. 特征检测与描述
7. 图像分类
8. 2D变换
9. 图像单应性homographies
10. 立体
11. 神经网络
12. 卷积神经网络
13. 图像分割
    

参考的几篇博客的笔记

1、霍夫变换检测直线，圆，矩形，正方形？
说法1：

（1）量化参数空间(m,c)
（2）新建累加器矩阵A(m,c)
（3）初始化A(m,c)=0，对任意m,c
（4）对每个图像边缘(xi,yi)：对A(m,c)中的所有元素：如果(m,c)在线c=yi-mxi上：A(m,c)+=1
（5）找A(m,c)中的局部最大值

说法2：

在参数空间θ，ρ中
（1）初始化累加器H=0
（2）对图像中的每个边缘点(x,y):for θ=0 to 180:ρ=xcosθ+ysinθH(θ，ρ)+=1endend
（3）找H(θ，ρ)是局部最小值的（θ，ρ）值
（4）图中检测出的直线由ρ=xcosθ+ysinθ给出

说法3：

霍夫圆检测[了解]
方法：霍夫梯度法

2、基于RANSAC 随机样本一致性 的直线检测

内点：与主运动估计一致的点。
RANSAC的基本假设是：

（1）数据由“局内点（inliers）”组成，例如：数据的分布可以用一些模型参数来解释；
（2）“局外点（outliers）”是不能适应该模型的数据；
（3）除此之外的数据属于噪声。

RANSAC也做了以下假设：给定一组（通常很小的）局内点，存在一个可以估计模型参数的过程；而该模型能够解释或者适用于局内点。
RANSANC基本原理：
输入一组观测数据、参数化模型、可信的参数。
通过反复选择数据中的一组随机子集来达成目标。被选取的子集假设是局内点，并根据下述方法验证：

（1）模型适应于假设的局内点，（即所有未知参数都能由假设的局内点计算得出）
（2）用1中得到的模型去测试所有其他数据，如果某个点适用于估计的模型，则认为它也是局内点
（3）如果有足够多的点被归类为假设的局内点，则估计的模型足够合理
（4）then用所有假设的局内点重新估计模型，（因为它仅仅被初始的假设局内点估计过）
（5）last通过估计局内点与模型的错误率来评估模型
这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为有比现有模型更好而被选用。

RANSAC（直线检测算法，模型匹配算法） RANdom Sample Consistence

随机选择一组种子点对模型进行初始的估计
根据初始的估计计算出局内点（到直线的距离小于阈值）
若局内点的个数大于阈值，则此次估计有效，利用最小二乘法对直线重新拟合
重复以上步骤，找出多条直线，选择其中局内点个数最多的一条作为最终的拟合结果

例子：从一组观测数据中找出合适的2维直线。假设观测数据中包含局内点和局外点，其中局内点近似地被直线所通过，而局外点远离于直线。

（1）假定模型（如直线方程），随机选nums（如nums=2）个样本点，对模型进行拟合
（2）数据波动容差范围sigma，找出距离拟合曲线容差范围内的点，统计点的个数
（3）重新选nums个点，重复（1）~（2）步，直到迭代结束
（4）每次拟合后，找出容差范围内统计点个数最多的情况，就是最终的拟合结果

来源：https://blog.csdn.net/xinxiangwangzhi_/article/details/89482018
3、图像扭曲（仿射变换）
博客：https://blog.csdn.net/qq_32642107/article/details/97614151

反向卷绕

4、从两幅图像重建三维场景结构
三维重建的算法流程：

（1）给定摄像机的内参K，用摄像机生成两幅同一场景不同角度的图像
（2）利用SIFT（尺度不变特征变换）方法对两幅图像进行特征检测，并对其特征匹配SIFT思想：寻找极值点，过滤，找出稳定的特征点，在每个稳定的特征点周围提取图像的局部特性，形成局部描述子，应用在以后的匹配中。SIFT步骤：检测尺度空间的极值点；抽取稳定的关键点；为每个关键点指定一个或多个方向；生成特征点描述子。特征匹配：一个特征在特征数据库中匹配，可使用的方法：①最近邻，即特征向量的欧氏距离②对最近邻的欧氏距离设一个全局阈值③用最近邻和次近邻的相对值
（3）利用匹配点，使用RANSANC的八点算法计算基本矩阵F博客：基本矩阵的基本解法之8点算法：①求线性解 ②奇异性约束
（4）利用内参K和基本矩阵F求出本质矩阵E
（5）对E进行SVD分解，从而恢复两个摄像机矩阵P和P’
（6）根据投影矩阵，用三角化法重建出三维点

来源：（知网）一种基于两幅图像的三维重建方法

5 词袋模型识别物体类别
词袋只依赖特征出现的频率。
计算在查询图像中找到的视觉词分布（直方图），比较这个分布与训练图像中的分布。

①在每个关键点抽取特征；
②量化，得到在学习来的视觉词（特征聚类中心）上的分布（直方图）；（把特征向量量化为视觉词）
③用分类算法，如SVM，在特征分布直方图上学习决策（分类）

笔记，BOW图像识别流水线：

（1）用聚类来学视觉词，构成学习字典
SIFT从图片中抽取特征
学习视觉字典，如用kmeans聚类；
（2）编码：成向量
（3）分类：用BOWs训练、测试数据

6、说明Harris角点检测的算法步骤

（1）计算x、y方向的图像梯度
（2）计算每个像素处的导数乘积
（3）计算每个像素处的导数乘积之和
（4）定义每个像素处的矩阵M(x,y)

（5）计算每个像素处检测器的响应值R=|M| -k(trace(M))2
（6）在R上应用阈值，计算非极大抑制找到变化最小的lenta，是点corner

将图像窗口平移[u,v]产生灰度变化E(u,v)，计算每个（blocksize大小）窗口的灰度值变化；计算响应函数R；把R值与（内置）阈值比较，判断该窗口下是否包含角点。
来源：博客：Harris角点检测数学计算过程与CornerHarris方法参数的一点说明

7、Canny边缘检测
是一个多阶段的算法，即由多个步骤构成：

1.图像降噪
2.计算图像梯度，得到可能边缘
3.非极大值抑制
4.双阈值筛选与连通性判断

分析：
首先，图像降噪。我们知道梯度算子可以用于增强图像，本质上是通过增强边缘轮廓来实现的，也就是说是可以检测到边缘的。但是，它们受噪声的影响都很大。那么，我们第一步就是想到要先去除噪声，因为噪声就是灰度变化很大的地方，所以容易被识别为伪边缘。

第二步，计算图像梯度，得到可能边缘。我们在前面的关于《图像梯度》文章中有所介绍，计算图像梯度能够得到图像的边缘，因为梯度是灰度变化明显的地方，而边缘也是灰度变化明显的地方。当然这一步只能得到可能的边缘。因为灰度变化的地方可能是边缘，也可能不是边缘。这一步就有了所有可能是边缘的集合。

第三步，非极大值抑制。通常灰度变化的地方都比较集中，将局部范围内的梯度方向上，灰度变化最大的保留下来，其它的不保留，这样可以剔除掉一大部分的点。将有多个像素宽的边缘变成一个单像素宽的边缘。即“胖边缘”变成“瘦边缘”。

第四步，双阈值筛选。通过非极大值抑制后，仍然有很多的可能边缘点，进一步的设置一个双阈值，即低阈值（low），高阈值（high）。灰度变化大于high的，设置为强边缘像素，低于low的，剔除。在low和high之间的设置为弱边缘。进一步判断，如果其领域内有强边缘像素，保留，如果没有，剔除。

这样做的目的是只保留强边缘轮廓的话，有些边缘可能不闭合，需要从满足low和high之间的点进行补充，使得边缘尽可能的闭合。

————————————————
原文链接：博客：Canny边缘检测

8、Harris角点检测：
角点：在以角点为中心的邻域中，梯度有多个主要的方向，可被重复检测，包含丰富的信息且具有可区分性

角点检测：

计算图像x，y方向上的梯度Ix，Iy
使用高斯函数作为窗口函数
计算 sei ta
非极大值抑制

其他的关键点检测算法：

Harris-拉普拉斯
DOG高斯差分算法（具有尺度不变性）:利用不同尺度的高斯差分算子与图像卷积，获得尺度空间，寻找极大值点

9、模板匹配
就是在给定的图片中查找和模板最相似的区域，输入包括模板和图片，
整个任务的思路：就是按照滑窗的思路，不断的移动模板图片，计算其与图像中对应区域的匹配度，最终将匹配度最高的区域选择为最终的结果
流程：

准备两幅图像：
1.原图像(I)：在这幅图中，找到与模板相匹配的区域
2.模板(T)：与原图像进行比对的图像块 滑动模板图像和原图像进行比对： 将模板块每次移动一个像素 (从左往右，从上往下)，在每一个位置，都计算与模板图像的相似程度。
对于每一个位置将计算的相似结果保存在结果矩阵（R）中。如果输入图像的大小（WxH）且模板图像的大小(wxh)，则输出矩阵R的大小为（W-w

• 1,H-h + 1）将R显示为图像 获得上述图像后，查找最大值所在的位置，该位置对应的区域就被认为是最匹配的。对应的区域就是以该点为顶点，长宽和模板图像一样大小的矩阵。

拓展：模板匹配不适用于尺度变换，
视角变换后的图像，这时我们就要使用关键点匹配算法，比较经典的关键点检测算法包括SIFT和SURF等，主要的思路是首先通过关键点检测算法获取模板和测试图片中的关键点；然后使用关键点匹配算法处理即可，这些关键点可以很好的处理尺度变化、视角变换、旋转变化、光照变化等，具有很好的不变性。

10、图像匹配：

找到一组关键点（Harris角点检测）
对每个关键点定义一个邻域
对此邻域进行提取和归一化
提取归一化后的邻域的局部特征
根据提取的局部特征进行匹配

HOG（方向梯度直方图）

提取的是全局特征，归一化时是对若干个cell（block）将图像分为若干个小的图像块cell（用图像或圆表示）对每一个cell计算梯度的方向和幅值并构造直方图
直方图：180°划分为9个部分，0°，20°，…，180°

11、SIFT特征提取：局部特征

将关键点邻域平分为4*4个图像块
对每一个图像块构建方向梯度
将子图像块中的每个像素点的梯度方向旋转 x°，梯度幅值投影到方向上
根据距离进行加权

每个关键点提取到的是128维特征，具有旋转不变性与尺度不变性（关键点检测使用的是高斯差分算法，对于每一个关键点都有对应的尺度信息）

HOG与SIFT的差别

HOG提取的是全局特征，SIFT提取的是局部特征
HOG归一化时是对若干个cell，SIFT归一化时是对128维向量
使用SIFT提取特征时找出最重要的梯度方向进行旋转，HOG不用
SIFT用变化的尺度计算

12、全景拼接

对两幅图像的关键点进行检测（高斯差分算法DOG）
找到两幅图中对应的关键点对用SIFT提取关键点的局部特征（128维）用SIFT局部特征进行匹配计算点对之间的欧式距离是否小于阈值来判断是否是对应的关键点对
用关键点对实现变换达到拼接的目的计算出变换矩阵使用RANSAC估计变换矩阵

13、图像缩放
接缝剪裁技术
动态编程技术

接缝剪裁：移除不重要的像素点（能量最少的像素点）

能量：像素点在x，y方向的梯度的幅值

接缝：像素从上到下（从左到右）的连接路径

最优接缝：使能量方程最小的接缝

进行接缝剪裁后图像整体的平均能量值上升（去除了能量小的像素点）

缺点：无法识别平坦区域上的物体

图像分割：聚类任务（将图像中相似的像素点分为一组）非监督学习

层次聚类将每个点视为一组找到距离最近的两组合并重复2，3，直到剩余一个组K-means（K均值）随机的选择k个聚类中心将每个点归类到距离它最近的聚类中心计算每一组平均值作为新的聚类中心重复，直到聚类中心不再改变
优点：找到使条件方差最小化的聚类中心简单易实现
缺点：需要选择k对局外点（噪声点）敏感局部最优所有的聚类使用相同的参数mans-shift随机选择一个种子点，创建一个窗口W计算窗口内的均值作为新的窗口中心重复，直到窗口中心不再改变
优：应用范围很广对数据集的形状没有特定要求只有一个参数（窗口大小）可找到不同数量的聚类对噪声具有鲁棒性（不会随着某物的变化而变化的性质，可以理解为稳定性）
缺：算法结果表现依赖于窗口尺度窗口尺度不易选择计算复杂不能根据特征空间的维度缩放K-NN(物体识别，分类算法) 无训练过程，只有测试过程选择一个k值计算距离测试点最近的k个点将测试点归入k个点中最多的那一类优点：简单有灵活的决策边界1-NN错误率是贝叶斯的两倍k值的选择用交叉验证的方法
k越小，对于噪声点越敏感
k越大，包含其他样本，影响判断，决策边界平滑欠拟合：模型过于简单 ，高偏差，低方差，训练集测试集错误率高
过拟合：模型过于复杂 ，低偏差，高方差，训练集测试集错误率低

降低方差的方法：
选择一个简单的算法
调整参数
使用更多的训练数据

物体识别
图像分类
对图像中物体的检测和定位
对图像中物体的语义和几何信息的提取
对人的活动和事件的分类

物体识别框架：

训练图像–>特征提取–>训练（训练标签）–>分类器
测试图像–>特征提取–>预测（分类器）

数据降维

PCA零均值化求协方差矩阵的特征值与特征向量（协方差用来统计两个随机变量关系的统计量）将特征向量按照特征值从大到小的顺序排列成矩阵，取出前k行为矩阵PY = P X 即为降维之后的数据
SVD（奇异值分解）特征值分解与奇异值分解都是给一个矩阵（线性变换）找一组特殊的基，特征值分解找到了特征向量这组基，在这组基下线性变换只有缩放的效果奇异值分解则是找到另一组基，这组基下线性变换的旋转、缩放、投影三种功能能独立地展示出来了压缩比p = n²/k（2n+1）> 1
LDALDA：线性判别分析，分类算法同时也是一种降维方法PCA:保持差异最大化（无监督学习）LDA:保持区分度（监督学习）

Bag of words

利用Bag of words模型将一幅图像表示为数值向量SIFT提取：利用SIFT算法从不同类别地图像中提取视觉词汇向量，这些向量代表的是图像中的局部不变的特征点K-means合并，构造词汇表：将所有的特征向量合到一块，利用K-means算法合并词义相近的视觉词汇，构造一个包含k个词汇的词汇表统计单词表中每个单词在图像中出现的次数，从而将图像表示成一个数值向量

准确率 = TP / TP + FP (在预测为真的样本中，真实正例的概率)
召回率 = TP / TP + FN（在真实正例中，预测为真的样本的概率）

对象检测

找到一个HOG模板并用作过滤器滑动窗口+HOG特征窗口大小做多尺度滑动窗口创造特征金字塔
视觉词汇表将对象表示为可变性零件集合，每个零件代表局部特征检测得分定义为全局和部分（零件）的得分之和减去每个零件变形成本之和
滑动窗口+全局和部分滤波器
累计整体和零件评分，并对变形零件进行惩罚

DPM

方法:手动选择一组零件,为每个零件训练的特定检测器
优：零件具有直观的含义标准检测方法可用于每个零件适用于特定类别
缺：需要手动选择零件语义驱动的部分有时没有简单的外观分布不能保证某些重要的部分没有被遗漏
当切换到另一个类别时，必须从头开始重建模型

————————————————
来源：博客：计算机视觉期末笔记