开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 中科大DIA复习内容 -> 正文阅读

[人工智能]中科大DIA复习内容

DIA复习

第2章图像数字化

可分离和正交图像变换
1. 图像变换
2. 成像过程：视觉过程、成像变换、成像亮度、视觉系统
采样和量化
1. 空间分辨率越低，区域边界出现方块
2. 图像幅度分辨率越低，图像出现虚假轮廓量化的比特数越多，灰度级越多
连通悖论(考点)
方盒量化和网格相交量化原理
1. 方盒量化：轮廓与方盒相交取方盒中心的点。
  定义：像素 $p_i=(x_i,y_i)$ , 数字化盒 $B_i=(x_i-1/2,x_i+1/2)\times(y_i-1/2,y_i+1/2)$ ，只要 $B_i\cap S\neq \empty$ ，则 $p_i$ 处在 $S$ 的数字化集合 $P$ 中。
2. 网格相交量化：相交的边缘按最近的点来替代。
数字弦，紧致弦(考点)
数字弦：像素 $p_i$ 和 $p_j$ 之间连线和它之间数字连接各段之间距离小于阈值。如果是基于8-数字弧，则在连续线段的任意一点 $\rho$ , 存在一点 $\rho_k\in P_{pq}$ 能使得 $d_8(\rho,\rho_k)<1$ ，该弦是数字弦。( $P_{pq}$ 为 $p$ 和 $q$ 两点的8-数字弧)

第3章图像变换

可分离和正交图像变换
1. 图像变换
$T(u,v)=\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}f(x,y)h(x,y,u,v)$

$f(x,y)=\sum_{u=0}^{N-1}\sum_{v=0}^{N-1}T(u,v)k(x,y,u,v)$

? $h (x, y, u, v)$ 为正向变换核， $k (x, y, u, v)$ 为反向变换核
2. 可分离： $h(x,y,u,v)=h_1(x,u)h_2(y,v)$ 1个2D变换分成2个1D变换

$T(x,v)=\sum_{y=0}^{N-1}f(x,y)h_2(y,v)\\ T(u,v)=\sum_{x=0}^{N-1}T(x,v)h_1(x,u)$

? 如果还是对称的， $h(x,y,u,v)=h_1(x,u)h_1(u,v)$

? 有正变换 $T = A F A$ ，反变换 $B T B = B A F A B$

? 若 $B=A^{-1}$ ， $F = B T B$ ，若 $B\neq A^{-1}$ ， $\hat{F}=BAFAB$ 。
3. 正交图像变换
$B=A^{-1}$ 且 $AA^{H}=I$

有2D的DFT变换

$F(u,v)=\sum_{x=0}^{N-1}\sum_{y=0}^{N-1}f(x,y)e^{-j2\pi\frac{ux+vy}{N}}\\ f(x,y)=\sum_{u=0}^{N-1}\sum_{v=0}^{N-1}F(u,v)e^{j2\pi\frac{ux+vy}{N}}$
2D DFT变换
如公式4
1. 图像空域变换对频谱的影响
  平移：改变频率域相位，幅度谱不变
  旋转：谱跟着旋转
  尺度变化：谱有分隔线，块状效应
哈达玛递推式
$H_2=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$

$H_{2N}=\frac{1}{\sqrt2}\begin{bmatrix}H_N&H_N\\H_N&-H_N\end{bmatrix}$
KL变换(PCA)

原理：通过对原始数据从N维变换到k维，使其在新的表达下各个维度上不存在相关性，即数据的不同维度的协方差为0。

找到个P
1. $Y = P X$
2. 要使得 $D_Y$ 是个对角阵，这样它的每一维度跟其他维度都是无关的
3. $D_X=U\Lambda U^T$ ，对 $D_X$ 对角化( $D_X$ 是对称矩阵)
4. 我们刚好希望 $D_Y=\Lambda$ ， $D_Y=\frac{1}{M}YY^{T}$ , $D_X=\frac{1}{M}XX^T$
5. $\frac{1}{M}XX^T=\frac{1}{M}UYY^TU^T\\ XX^T=UY(UY)^T$
  
  即 $Y=U^TX$ ， $P=U^T$
步骤：
1. 原始数据按列组成N行M列的矩阵X
2. 对X的每一行（每个维度）进行零均值化
3. 求出协方差矩阵 $D_X=\frac{1}{M}XX^T$ 。(对称矩阵一定能够特征值分解，正规阵)
4. 求出 $D_X$ 的特征值和特征向量
5. 将前k个特征向量按行排成矩阵P
6. Y=PX得到k维后的数据
2D DWT框架

第4章形态学

二值形态学
所有的操作都是将模板中心对上相应为1的位置。 $\hat{B}$ 为 $B$ 的映象，就是关于模板中心对称； $B)_x$ 表示 $B$ 的平移
1. 膨胀
2. 腐蚀
3. 开启和闭合
  
  开启运算可以把比结构元素小的突刺滤掉，起到分离的作用
  闭合运算可以把比结构元素小的缺口或孔填充上，起到连通的作用
  
  几何解释：
  1. 开启：让结构元素在被开启集合内滚动得到的外沿，即用结构元素B填充A得到结果
  2. 闭合：让结构元素在背景中滚动得到的外沿
4. 击中-击不中变换
  
  先将A用E去腐蚀找出匹配点，然后A的补集用F去腐蚀找出匹配点，通过交集来找出符合两者的位置区域。
5. 对偶性：一个运算对图像目标的操作相当于另一个运算对图像背景操作
  
  腐蚀和开启
  $\oplus B)^c = A^c\ominus \hat{B}\\ (A\ominus B)^c=A^c\oplus \hat{B}$
  开启和闭合
$(A\circ B)^c=A^c\cdot \hat{B}\\ (A\cdot B)^c=A^c\circ\hat{B}$
1. 组合运算
  1. 区域凸包：从四个方向迭代优化到收敛
    
    ? 例子：
  2. 细化求骨架
    
    ? 例子
  3. 粗化:
2. 实用算法
  1. 噪声滤除(考点)
    先开启后闭合
  2. 目标检测
  3. 边界提取(考点)
  4. 区域填充
  5. 连通组元提取
  6. 区域骨架提取
    
    k表示做了k次，S(A)可能不连通，K表示使A腐蚀至空集的最大K值。若要求要连通，可用细化操作。
灰度形态学
1. 平坦结构元：随定义域不变的灰度级；非平坦结构元：随定义域变化的灰度级
2. 平坦结构元
  1. 腐蚀
  2. 膨胀
    非平坦结构元
  3. 腐蚀
  4. 膨胀
3. 开操作和闭操作：
  
  开操作消除与结构元素相比尺寸较小的亮细节，保持图像整体灰度值和大的亮区域基本不受影响；闭操作消除与结构元素相比尺寸较小的暗细节，保持图像整体灰度值和大的暗区域基本不受影响
4. 实用算法
  1. 形态学平滑
  2. 形态学梯度
  3. 顶帽变换和底帽变换
    顶帽变换：增强暗区细节
    底帽变换：增强亮区细节
    
    $f\circ b$ 和 $f\cdot b$ 是背景估计， $h=f-(f\circ b)$ 和 $(f\cdot b)-f$ 都用来背景消除
  4. 粒度测定：根据差值阵列曲线峰值来区分两个物体
  5. 纹理分割：开启或闭合找出目标区域；开启或闭合提高亮度/暗度；阈值分割找出分界

第5章图像增强

图像增强和图像恢复的区别
1. 相同点：两者都是改善图像的质量
2. 不同点：增强一般仅借助人类视觉系统的特性以取得看起来较好的视觉结果；恢复则要根据相应退化模型和知识重建或恢复原始的图像，以保真原则为前提。
空域灰度变换
$g (x, y) = T (f (x, y))$ ，其中T在点(x,y)的邻域上定义的算子
1. 基本的灰度变换 $s = T (r)$ 邻域为1x1
  1. 图像求反 $s = L ? 1 ? r$
  2. 对数变换 $s=c\cdot log(1+r)$
  3. 指数变换 $s=c\cdot r^\gamma$ 伽马校正(用于缓解显示设备的非线性亮度映射)
  4. 分段线性变换函数对比度拉伸；灰度级切分；比特面分割(突出特定比特对整幅图像的贡献)
2. 直方图处理
  1. 灰度直方图
  2. 直方图均衡
  3. 直方图匹配
    1. $s = T (r)$
    2. $G (z) = s$
    3. $z=G^{-1}(s)=G^{-1}(T(r))$
  4. 局部直方图：局部领域直方图均衡化
  5. 基于直方图统计的图像增强
空域滤波
1. 相关和卷积：相关无需对卷积核做反转，而卷积需要
2. 空域平滑作用：降噪
  1. 局部平均滤波器
  2. 中值滤波保留边缘
    用局部邻域(窗口)里的中值来代替上述局部平均法中的局部平均值。即将以该点为中心的某个窗口框住的各象素的中间值作为处理后图象中该点象素的值。
  3. 保边滤波器
    
    代表：双边滤波器
3. 空域锐化（突出灰度过渡部分，使边缘清晰）
  1. 中心差分
  2. 梯度算子
    由于微分算子可突出高频成分，因此容易受突变的噪声影响，所以先做平滑降低对突变对梯度的影响，才有了Sobel和Prewitt算子，由于Prewitt算子并没有考虑像素间的位置关系，Sobel算子引入了像素间的位置关系，通过将中间的权重进行增大。
  3. 二阶算子
4. 频域增强
  1. 频域滤波步骤
    
    为了有效和快速地对图象进行处理，常常需要将原定义在图象空间的图象以某种形式转换到另外一些空间(频率域空间)并加工，最后再转换回图象空间以得到所需的效果。
    1. $1)^{(x+y)}$
    2. $F (u, v)$
    3. $H(u,v)\times F(u,v)$
    4. IDFT
    5. 取实部
    6. $1)^{(x+y)}$
  2. 频率域平滑（低通滤波）
    
    理想低通滤波器：振铃效应(长尾效应)：空域sinc函数有长尾，范围大
    
    解决方法：布特沃斯低通滤波器或者高斯低通滤波器
  3. 频率域锐化（高通滤波）
  4. 同态滤波
    一幅图像𝑓(𝑥, 𝑦)可以表示为照射分量和反射分量的乘积
    $f(x,y)=i(x,y)\cdot r(x,y)$
    由于傅立叶变换对两个函数的乘积是不可分的，因此采用对数，将两个分量分离。
    $z(x,y)=ln(f(x,y))=ln(i(x,y))+ln(r(x,y))\\ F\{ln(f(x,y))\}=F\{ln(i(x,y))\}+F\{ln(r(x,y))\}$
    步骤

第6章图像恢复

降质模型
空域滤波，频域滤波
1. 空域滤波针对加性噪声
  1. 均值滤波器
  2. 次序统计滤波器
  3. 自适应滤波器
2. 频域滤波针对周期噪声
  1. 带阻滤波器
  2. 带通滤波器
  3. 槽口滤波器
运动恢复建模估计
1. 降质函数估计
2. 逆滤波（难以精确重建）限制频谱范围
  
  维纳滤波：均方误差最小 $e^2=E\{(f-\hat{f})^2\}$ ， $f$ 是未污染的图像， $\hat{f}$ 是图像的估计
  
  约束最小二乘滤波（仅需知道噪声的均值和方差） $\rVert g-H\hat{f}\rVert$ ， $g$ 是降质函数的输出
几何校正
1. 坐标的几何校正(空间变换)
2. 像素灰度值的估计(灰度插值)
  1. 最近邻插值零阶插值用最靠近的点赋予该点
  2. 双线性插值一阶插值克服导数不连续 $f(x,y)=a\cdot x+ b\cdot y+c\cdot x\cdot y+d $
  3. 高阶插值克服不连续
  4. 薄板样条插值 Thin plate spline(TPS)
    
    原理：假设空间中有一片薄钢板，我们希望将这块钢板进行弯折，让它通过每一个观测点。同时，我们希望弯折这块板子所需要的能量最小。

第7章边缘检测

边缘模型
边缘参数
边缘检测算子
1. 正交梯度算子
2. 方向微分算子 Kirsch算子
3. 二阶导数算子
  1. 拉普拉斯算子
    
    影响：对图象中的噪声相当敏感；产生双象素宽的边缘；不能提供边缘方向的信息
  2. Marr算子
4. Canny算子（最优边缘检测算子）
  1. 原理：将像素的梯度大小与该梯度方向相邻的两个像素梯度大小比较，如果相邻点梯度幅值比像素的幅值小，则认定该点为边缘。
  2. 步骤
5. SUSAN 算子
  1. 原理：当核处在边缘处的时候，USAN面积约为最大值的一半。当核处在角点处，USAN面积则为最大值的1/4.
  2. 步骤：
    1. 利用圆形模板遍历图像，计算每点处的USAN值。
    2. 设置一阈值g，一般取值为1/2(Max(n)，也即取值为USAN最大值的一半，进行阈值化，得到角点响应。
    3. 使用非极大值抑制来寻找角点
边缘拟合
1. 灰度阶跃拟合
  
  原理构造原图象(或子图、小区域) 的拟合曲面，再在拟合曲面上利用曲面的参数检测出边缘
2. 基于斜面模型的边缘检测
  
  原理：根据相邻的可靠的斜面参数进行比较，如果三个参数相等的话，则没有边缘，如果相差比较大，则有边缘。
  
  拟合误差 $e^2 = \sum_R\sum_C[ax+\beta y+\gamma - f(x,y)]^2$
  
  步骤：

第8章图像分割

图像分割定义
传统分割方法
1. 阈值分割
  阈值法是以图像直方图为依据，选定阈值，再逐个对像素作判决。一维的直方图有灰度直方图，多维的直方图有两个波段组成的二维直方图。
  $T = T [x, y, f (x, y), p (x, y)]$
  1. 依赖像素的阈值方法 (全局法) 仅根据 $f (x, y)$ 来选取阈值
    1. 直方图方法
    如果分布近似正态分布，方差相等的情况下， $T=\frac{\mu_1+\mu_2}{2}+\frac{\sigma^2}{\mu_1-\mu_2}ln(\frac{P_2}{P_1})$
    2. Otsu’s 方法
  2. 依赖区域的阈值选取
    1. 直方图变换
    2. 灰度-梯度散射图通过聚类的方法找到最佳阈值将二者分开
  3. 依赖坐标的阈值选取
    1. 变化阈值法
2. 区域生长法
  1. 基本思想：将相似像素结合起来构成区域
  2. 基本步骤：
    1. 选择区域的种子像素
    2. 确定将相邻像素包括进来的准则
    3. 制定生长停止的规则
  3. 例子
3. 分裂合并法
  1. 步骤
    1. 先把图像分成任意大小且不重叠的区域
    2. 然后再(根据准则)合并或分裂这些区域
    3. 迭代进行直到实现分割
  2. 数据结构：四叉树
  3. 例子
4. 分水岭分割算法
  1. 基本思想：建立不同目标间的分水岭（过分割的话采用标记的方法）易受噪声影响
  2. 步骤
5. 聚类分割算法
  1. K-means 聚类算法(考点)
    1. 基本步骤
    2. 计算复杂度 O(NKD)
  2. AP聚类算法解决K-means需要指定聚类数目
    1. 基本思想：假设类中心来自某些样本点，将全部样本看作一个网络的节点，然后通过网络中各条边的消息传递计算出各样本的聚类中心。
    2. 聚类步骤
水平集分割的基本思想和优势(考点)
1. 基本思想：通过演化三维曲面，然后根据演化后的三维曲面的零水平集来得到轮廓。
2. 曲线演化到水平集演化的推导
  1. 曲线演化方程 $\frac{\partial C}{\partial t}=FN$ ，其中 $F$ 为速度函数， $N$ 为曲线 $C$ 的法向量
  2. 将动态闭合的曲线 $C(\rho,t)$ (描述的是曲线的)作为水平集，嵌入到随时间变化的函数 $\phi(x,t)$ 中，使得 $\phi(C(\rho,t),t)=0$
  3. 两边对t求微分 $\frac{\partial \phi}{\partial t}+\nabla \phi\cdot\frac{\partial C}{\partial t}=0$
  4. 水平集演化方程
    $\frac{\partial \phi}{\partial t}=-\nabla\phi\cdot\frac{\partial C}{\partial t}=-\nabla \phi\cdot FN=-\nabla\phi\cdot F (-\frac{\nabla\phi}{|\nabla\phi|})=F|\nabla\phi|$
3. 利用变分法和梯度下降推导演化方程
  
  定义变分的能量函数：重新初始化写成能量函数:
  $E(\phi)=\int_{\Omega}\frac{1}{2}(|\nabla\phi|-1)^2dxdy\\=\int_{\Omega}\frac{1}{2}(|\nabla\phi|^2-2|\nabla\phi|+1)dxdy$
  让 $F(\phi)=\frac{1}{2}(|\nabla\phi|^2-2|\nabla\phi|+1)=\frac{1}{2}((\phi_x^2+\phi_y^2)-2\sqrt{\phi_x^2+\phi_y^2}+1)$
  
  通过一个微小的扰动 $\delta$ 和任意函数 $h$ ， $h$ 满足 $h|_{\partial \Omega}=0$ (在线两端扰动值为0)。有如下方程
  $F(\phi+\delta h)=\frac{1}{2}(((\phi+\delta h)_x^2+(\phi+\delta h)_y^2)-2\sqrt{(\phi+\delta h)_x^2+(\phi+\delta h)_y^2}+1)$
  
  $\frac{\partial F(\phi+\delta h)}{\partial \delta}=h_x(\phi+\delta h)_x +h_y(\phi+\delta h)_y-\frac{h_x(\phi+\delta h)_x +h_y(\phi+\delta h)_y}{\sqrt{(\phi+\delta h)_x^2+(\phi+\delta h)_y^2}}\\ =\nabla h\cdot \nabla(\phi+\delta h)-\frac{\nabla h\cdot \nabla(\phi+\delta h)}{\sqrt{(\phi_x^2+\phi_y^2)+\delta^2(h_x^2+h_y^2)+2\delta\nabla h\cdot\nabla\phi}}$
  
  令 $\frac{\partial F(\phi+\delta h)}{\partial \delta}|_{\delta\rightarrow0}=\nabla h\cdot\nabla\phi-\frac{\nabla h\cdot\nabla\phi}{\sqrt{\phi_x^2+\phi_y^2}}$
  
  则
  $\frac{\partial E(\phi+\delta h)}{\partial \delta}|_{\delta\rightarrow0}=\int_{\Omega}(\nabla h\cdot\nabla\phi-\frac{\nabla h\cdot\nabla\phi}{\sqrt{(\phi_x^2+\phi_y^2)}})dxdy\\=\int_{\Omega}(h_x\phi_x+h_y\phi_y)dxdy-\int_\Omega\frac{h_x\phi_x+h_y\phi_y}{\sqrt{\phi_x^2+\phi_y^2}}dxdy$
  因为 $KaTeX parse error: Undefined control sequence: \part at position 17: …frac{\partial}{\?p?a?r?t? ?x}(h\phi_x)=h_x…$ ， $KaTeX parse error: Undefined control sequence: \part at position 17: …frac{\partial}{\?p?a?r?t? ?y}(h\phi_y)=h_y…$
  
  则
  $\frac{\partial E(\phi+\delta h)}{\partial \delta}|_{\delta\rightarrow0}=\int_{\Omega}(\frac{\partial}{\partial x}(h\phi_x)+\frac{\partial}{\partial y}(h\phi_y))dxdy-\int_\Omega (h\phi_{xx}+h\phi_{yy})dxdy\\-\int_\Omega(\frac{\partial}{\partial x}(\frac{h\phi_x}{|\nabla\phi|})+\frac{\partial}{\partial y}(\frac{h\phi_y}{|\nabla\phi|}))dxdy+\int_\Omega (h\frac{\partial}{\partial x}(\frac{\phi_x}{|\nabla\phi|})+h\frac{\partial}{\partial y}(\frac{\phi_y}{|\nabla\phi|}))dxdy$
  根据格林公式 $\iint_D(\frac{\partial Q}{\partial x}-\frac{\partial P}{\partial y})dxdy=\oint_L(Pdx+Qdy)$ 和 $h|_{\partial \Omega}=0$ 得到
  $\int_\Omega(\frac{\partial}{\partial x}(h\phi_{x})+\frac{\partial}{\partial y}(h\phi_y))dxdy = \oint_{\partial \Omega}h(-\phi_ydx+\phi_xdy)=0\\ \int_\Omega(\frac{\partial}{\partial x}(\frac{h\phi_{x}}{|\nabla\phi|})+\frac{\partial}{\partial y}(\frac{h\phi_{y}}{|\nabla\phi|}))dxdy = \oint_{\partial \Omega}h(-\frac{\phi_y}{|\nabla\phi|}dx+\frac{\phi_x}{|\nabla\phi|}dy)=0$
  则
  $\frac{\partial E(\phi+\delta h)}{\partial \delta}|_{\delta\rightarrow0}=-\int_\Omega (h\phi_{xx}+h\phi_{yy})dxdy+\int_\Omega (h\frac{\partial}{\partial x}(\frac{\phi_x}{|\nabla\phi|})+h\frac{\partial}{\partial y}(\frac{\phi_y}{|\nabla\phi|}))dxdy\\ =-\int_\Omega h\Delta \phi dxdy+\int_\Omega h\nabla\cdot(\frac{\nabla\phi}{|\nabla\phi|})dxdy\\=-\int_\Omega h(\Delta\phi-\nabla\cdot(\frac{\nabla\phi}{|\nabla\phi|}))dxdy=0$
  因为 $h$ 是任意函数，因此
  $\Delta\phi-\nabla\cdot(\frac{\nabla\phi}{|\nabla\phi|})=0$
  则 $E(\phi)$ 的梯度为 $-(\Delta\phi-\nabla\cdot(\frac{\nabla\phi}{|\nabla\phi|}))$
  
  我们可以得到水平集 $\phi$ 对时间的更新梯度(负梯度)应该是
  $\phi_t =\Delta\phi-\nabla\cdot(\frac{\nabla\phi}{|\nabla\phi|})$
Graph Cut 分割的基本思想

? 通过人为的标注一部分肯定属于前景或背景的像素点，作为先验信息，构建源点和汇点，将源点，汇点分别与像素连接以及像素之间也进行连接构建图，根据最小割的方法将前景和背景分开。

第9章图像表达与描述

基于全局特征的图像表达
1. 灰度直方图
  根据直方图的形态可以大致推断图像质量的好坏
2. Color Name 用color name来做表征
3. GIST
  1. Gabor函数是一个用于边缘提取的线性滤波器，该滤波器的频率和方向表达同人类视觉系统类似，十分适合纹理表达和分离
  2. 流程：
基于局部特征的图像表达
1. 简单局部视觉特征
  1. 局部二值模式 LBP(考点)
    1. 原理：在不同光照条件下，同一场景的图像像素亮度变化显著，但局部区域的像素亮度相对大小关系是稳定的，LBP在3x3的窗口区域内，将中心像素作为阈值，相邻8个像素与中心像素比较来得到局部特征模式。
    2. LBP直方图：将LBP特征与图像的空间信息结合。
      
      步骤：
      1. 首先将LBP特征图像分成m个局部块，并提取每个局部块的直方图
      2. 然后将这些直方图依次连接在一起形成LBP特征的统计直方图，构成LBP特征向量。
    3. 特性：具有灰度不变性，本身不具备旋转不变性（旋转不变性可通过牺牲了LBP特征对不同模式的区分性），二进制模式比较多，可以通过等价模式对LBP算子的模式种类进行降维。
  2. 梯度方向直方图 HOG特征 (考点)
    1. 原理：在一副图像中，局部目标的外观和形状能够被梯度或边缘的方向密度分布很好地描述。
    2. 步骤：
      1. 梯度计算
      2. 直方图统计 cell：8x8
      3. 块(block)描述子 block归一化用来降低光照的影响(大小: 16x16)
    3. 特性：对灰度的线性变换具有不变性
  3. 形状上下文(shape context)
    1. 原理：提取二值图像中的物体轮廓，比较轮廓点的相似性，以及匹配关系
    2. 步骤：
      1. 以某一个轮廓点为参考原点，统计其他轮廓点的分布
      2. 极坐标空间划分涉及两个变量𝑟和𝜃，轮廓点分布的直方图可以用二维矩阵表示
      3. 计算两组图像的轮廓的匹配代价
    3. 性质：
      1. 平移变换具有不变性
      2. 选择合适半径后具有缩放不变性
      3. 通过选择局部切向作为bin编号的参考方向，可对旋转具有不变性
      4. 可容忍小的仿射畸变
2. 基于关键点检测的局部特征
  1. 基本框架：输入图片->局部特征提取->特征编码->局部特征聚合
  2. 局部关键点检测
    1. Harris角点检测
      1. 推导首先对 $I (x + u, y + v)$ 进行一阶泰勒展开，然后将平方项内括号展开，对中间矩阵做特征值分解，就可以分清楚哪些情况
      2. 三种比较
      3. 性质：有旋转不变性；没有尺度不变性
    2. 块检测
      1. 高斯差分检测子 DOG SIFT检测子(考点)
        步骤：1. 构建高斯金字塔 2.关键点检测
        性质：尺度不变性
      2. 最大稳定极值区域检测子 MSER
        原理：在一个比较大的阈值范围内，可被独立分割出来的、面积稳定的图像区域。因为区域内部和区域边界上的像素的灰度有显著差异。
        步骤
        
        性质：对仿射畸变有较好的鲁棒性
  3. 局部区域描述 SIFT描述子(考点)
    1. 基本流程
    2. 主方向估计流程
    3. SIFT描述子生成流程
    4. 性质:
      1. 通过DOG检测子进行多尺度检测来实现尺度不变性
      2. 通过缩放到相同大小来实现缩放不变性
      3. 通过分块处理来实现平移不变性
      4. 通过主方向估计和旋转对齐来实现旋转不变性
      5. 通过对直方图的归一化实现亮度不变性（灰度不变性）
    5. SIFT反色变换后，SIFT特征变化
      1. SIFT的特征数量不变
      2. 每个SIFT特真的关键点位置、特征尺度不变
      3. 每个SIFT特征的主方向相差180度
      4. 每个SIFT特征的128D描述子，它们的16个格子中每个格子对应的8维梯度方向直方图不变，但是16个格子的排列顺序颠倒了
特征编码与聚合
1. BOW 步骤稀疏采用倒排索引
  1. 利用SIFT算法从不同类别的图像中提取视觉词汇向量，这些向量代表代表的是图像中局部不变的特征点
  2. 将所有特征点向量集合到一块，利用K-means算法合并词义相近的视觉词汇，构造一个包括K个词汇的单词表
  3. 统计单词表中每个单词在图像中出现的次数，从而将图像表示为一个K维数值向量
2. VLAD 步骤稠密不适用倒排索引
3. 将图像分成若干块，分别对每一块进行统计特征
4. 采用一种多尺度的分块算法，分块的粒度越大越细，呈现出一种层次金字塔的结构
5. 乘积量化原理 PQ 通过对空间的极度精细划分来使得数据距离可通过它们所属类的距离来替换。

第10章图像识别

形状识别
1. Hough变换(考点)
  1. 思想：基于投票的机制
  2. Hough 参数空间：图像空间与参数空间之间的一种变换
    1. 直线检测
      1. 问题： $p_{max}$ / $q_{max}$ 可能为无穷大，难以对其进行离散化
      2. 解决方案
    2. 圆周检测先Sobel算子然后取阈值之后进行Hough变换得到了累计图，累计最多点的坐标作为圆周的坐标，该点在其圆上的出现最多的r作为圆周的半径。
      
      利用梯度来降维
    3. 椭圆检测利用梯度信息检测椭圆
  3. 广义Hough变换
    1. 原理：在所需检测的曲线或目标轮廓没有或不易用解析式表达时，可以利用表格来建立曲线或轮廓点与参考点间的关系，从而可继续利用Hough变换进行检测
2. 距离变换(考点) 倒角距离变换
  1. 基本思路：将模板去放置每个位置 $x$ 处，然后计算模板与测试图像边缘匹配的距离，将最小距离的位置作为匹配的位置
  2. 计算复杂度: O(MNP) M边缘点数量，P为像素点数量，N为模板中边缘点数量
  3. 将计算复杂度减少为O(NP)，通过提前把每个点的距离计算出来，通过累加相应的值就可以得到距离，从而减少冗余。离最接近灰色的距离计算，按照棋盘距离，也就是4邻域进行计算
人脸检测与识别方法
1. 基本思想：通过一系列基学习器，使得后者分类器关注前面分类器容易出错的部分，最后将这些基分类器结合起来得到强的分类器。
一般目标检测
1. 基本思想：通过滑窗然后得到与模板响应，根据模板的响应来得到目标的位置。
图像分类
1. 空间金字塔匹配 (Spatial Pyramid Matching) SPM
2. KNN
3. SVM
图像检索
1. 倒排索引：将KxM的矩阵变为MxK的矩阵，由于矩阵的稀疏性，通过链表来实现计算和索引
2. 几何校验
  1. RANSAC
    1. 思想：通过正确匹配点对估计仿射模型来排除错误匹配点对
    2. 步骤：
      1. 迭代的随机选取匹配点对当作假设的inliers
      2. 根据假设的inliers计算一个仿射模型
      3. 其他数据点根据上述的仿射模型判断是否是inliers
      4. 通过所有的inliers重新估计仿射模型
      5. 通过所有的匹配点对与模型的拟合程度计算误差
    3. 缺点：计算量大 $O(N^3)$
  2. 空间编码 (考点)
    1. 原理：根据空间中点的相对关系建立空间编码矩阵，对空间编码矩阵进行异或运算来得到不符合空间位置分布的点，然后将其剔除。
    2. 步骤：
      1. 建立空间编码矩阵Xmap, Ymap。
      2. 对两幅图片的对应的空间编码矩阵进行异或运算并求和
      3. 迭代地查找和删除最不一致的匹配对
3. 二值哈希基本思想：将图像的高维特征向量映射到高维立方体的顶点(二值表达)上来减小存储开销，通过汉明距离来达到加快检索速度。

第11章概率图模型可在李航统计学习的书上找到

概率无向图
1. 定义：概率无向图的点为随机变量，边为概率，随机变量之间存在成对马尔可夫性；局部马尔可夫性；全局马尔可夫性。
  1. 成对马尔可夫性 u,v之间通过O连接
  2. 局部马尔可夫性
  3. 全局马尔可夫性
2. 因子分解
  1. 最大团
  2. 定义：
  3. 例子
条件随机场
1. 线性条件随机场一般用于标注
  1. 定义：
  2. 线性条件随机场的模样
  3. 参数化形式
    $P(y|x)=\frac{1}{Z(x)}exp(\sum_{i,k}\lambda_kt_k(y_i,y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x_i,i))\\Z(x)=\sum_yexp(\sum_{i,k}\lambda_kt_k(y_i,y_i,x,i)+\sum_{i,l}\mu_ls_l(y_i,x_i,i))$
    $Z (x)$ ：规范化因子
    
    $t_k$ ：定义在边上的特征函数，转移特征，依赖于前一个和当前位置
    
    $s_l$ ：定义在结点上的特征函数，状态特征，依赖于当前位置
    
    $\lambda_k$ 和 $\mu_l$ 是 $t_k$ 和 $s_l$ 对应的权值
  4. 简化形式
    
    ? 其中
  5. 矩阵形式
    
    原理：
  6. 例子
  7. 例子
    
    答案：根据 $M_1(x),M_2(x),M_3(x),M_4(x)$ 可画出如下的条件随机场
    所有路径的非规范化概率：
    $a_{01}b_{11}c_{11}$ , $a_{01}b_{11}c_{12}$ , $a_{01}b_{12}c_{21}$ , $a_{01}b_{12}c_{22}$ ,
```
$a_{02}b_{21}c_{11}$,$a_{02}b_{21}c_{12}$,$a_{02}b_{22}c_{21}$,$a_{02}b_{22}c_{22}$

规范化因子计算
计算$M=M_1(x)M_2(x)M_3(x)M_4(x)\\=\begin{bmatrix}a_{01}b_{11}c_{11}+a_{02}b_{21}c_{11}+a_{01}b_{12}c_{21}+a_{02}b_{22}c_{21}+a_{01}b_{11}c_{12}+a_{02}b_{21}c_{12}+a_{01}b_{12}c_{22}+a_{02}b_{22}c_{22}&0\\0&0\end{bmatrix}$

$Z(x)=M[start,stop]=M[1,1]\\=a_{01}b_{11}c_{11}+a_{02}b_{21}c_{11}+a_{01}b_{12}c_{21}+a_{02}b_{22}c_{21}+a_{01}b_{11}c_{12}+a_{02}b_{21}c_{12}+a_{01}b_{12}c_{22}+a_{02}b_{22}c_{22}$
```
2. 概率计算推导看书
  前向-后向算法，考的概率低
3. 预测算法给定条件随机场 $P (Y ∣ X)$ 以及输入序列，求条件概率最大的输出序列
4. 维特比算法
5. 例题
  
  答案:
  
  所有路径的概率：
  
  0.5x0.3x0.5=0.075, 0.5x0.3x0.5=0.075, 0.5x0.7x0.6=0.21, 0.5x0.7x0.4=0.14,
  
  0.5x0.7x0.5=0.175, 0.5x0.7x0.5=0.175, 0.5x0.3x0.6=0.09, 0.5x0.3x0.4=0.06
  
  所有路径中概率最大的序列为21212，概率为0.21. 其实每次都选取概率最大的路径。

第12章运动分析

相机运动建模
光流方程 (考点)
1. 光流定义：基于图片模式的变化“感知”二维运动，也依赖于光照和目标表面纹理
2. 光流方程推导
  恒定光流假设 $\psi(x+d_x,y+d_y,t+d_t)=\psi(x,y,t)$
  
  一阶泰勒展开 $\psi(x+d_x,y+d_y,t+d_t)=\psi(x,y,t)+\frac{\partial\psi}{\partial x}d_x+\frac{\partial\psi}{\partial y}d_y+\frac{\partial\psi}{\partial t}d_t$
  
  则有 $\frac{\partial\psi}{\partial x}d_x+\frac{\partial\psi}{\partial y}d_y+\frac{\partial\psi}{\partial t}d_t=0$
  
  对时间求导，有 $\frac{\partial\psi}{\partial x}v_x+\frac{\partial\psi}{\partial y}v_y+\frac{\partial\psi}{\partial t}=0$
  
  写成向量形式 $\nabla\psi^Tv+\frac{\partial \psi}{\partial t}=0$
3. 二义性：光流方程仅包含梯度 $v_n$ 方向的流向量，切线方向 $v_t$ 的流向量是未定义的，在恒定亮度区域 $\nabla\psi=0$ ，光流是不确定的。即红色框的量无法知道。所以在平坦纹理区域，运动估计是不可靠的，更可靠的是靠近边缘的区域。
运动表达方法
1. 准则：
  1. 基于位移帧差准则 (DFD criterion)
  2. 基于光流方程准则 (OF criterion)
  3. 正则化准则：利用额外的平滑项约束(smoothness)，保证 $x$ 的邻域的像素 $y$ 要尽可能和 $x$ 的偏移量尽可能一致。
  4. 贝叶斯准则：一般简化为具有适当平滑约束的基于DFD的估计。
  运动较小时用OF准则，运动较大时用DFD准则
2. 优化方法：
  1. 穷举搜索（DFD准则）
  2. 梯度搜索（DFD准则下p=2和OF准则）
  3. 多分辨率搜索（从粗到细地搜索）
3. 基于像素的运动估计
  1. 运动平滑约束正则化方法(OF+smoothless)
    目标函数: $min\;E(V(X))=\sum_{X\in\Delta}(\frac{\partial\psi}{\partial x}v_x+\frac{\partial\psi}{\partial y}v_y+\frac{\partial\psi}{\partial t})^2+w_s(\rVert\nabla v_x\rvert^2+\rVert\nabla v_y\rVert^2)$
  2. 多点邻域方法：最小化像素的邻域像素的DFD误差，独立地估计每个像素的运动向量。
    
    目标函数： $min\;E_{DFD}(d_n)=\sum_{x\in B(x_n)}w(x)|\psi_2(x+d_n)-\psi_1(x)|^2$
4. 基于块的运动估计
  1. 块匹配
    1. 原理：假设块中所有像素仅有同一个平移运动，用一个运动向量即可表示。通过最小化块中的DFD误差，估计运动向量。
    2. 目标函数： $min\;E_{DFD}(d_m)=\sum_{x\in B_m}|\psi_2(x+d_m)-\psi_1(x)|^p$
    3. 穷举块匹配法：通过选定候选区域，然后用块进行滑动搜索来估计块的运动。
      
      半像素精度：首先进行双线性插值，然后步长不是整像素点，是一半像素点，提高精度
    4. 层级块匹配算法：首先经过下采样得到低分辨率的图片，然后根据低分辨率的图片进行运动估计，然后映射到下一层高分辨率图像，利用该运动估计向量的2倍进行位置搜索，对该运动向量进行修正，继续往下一层高分辨图像做同样的映射，直到达到原来的分辨率的图像。
5. 相位相关法：通过计算在频域的相关性得到它们之间相位关系，从而进行反变换的到它们的运动关系。
运动参数估计
1. 全局运动
  1. 直接估计优化DFD准则来得到参数
  2. 间接估计使用基于像素或基于块的方法找到深度运动场，然后通过最小二乘拟合，利用运动模型对得到的运动场进行参数化
2. 局部估计
  1. 稳健估计: **迭代删除离群点(outlier)像素 ** 细节: 硬阈值与软阈值
    1. 将区域设置为帧中的所有像素
    2. 将直接或间接方法应用于区域内的所有像素
    3. 评估区域内所有像素的误差(EDFD or Efit)
    4. 删除有较大错误的离群像素
    5. 对区域中的其余像素重复步骤2-4

第13章目标跟踪

单目标跟踪
1. 贝叶斯跟踪框架
2. 粒子滤波
  1. 基本思想：利用状态空间的一组带权值的随机样本逼近状态变量的概率密度函数，其显著优点是多假设性，不受先验分布及状态转移模型的限制，方便地对目标状态进行表达。
  2. 实质：根据一定规则(采样函数)采样一些随机粒子 (样本)，观测粒子的相似度(似然)来确定粒子的权重，并利用粒子和权值来近似地表示后验概率。
  3. 方法：蒙特卡洛方法
  4. 步骤：
3. 均值漂移跟踪 MeanShift 算法
  1. 基本思想：利用概率密度的梯度爬升来寻找局部最优。
  2. 原理：每一次计算区域内样本点的数目，求质心，作为新的区域中心，不断迭代直到区域中心不再变化。
4. 相关滤波跟踪(判别式跟踪算法)
  1. 基本思想：通过对感兴趣区域的水平和垂直方向圆周移位，可以获取大量的训练样本。通过训练这些样本获取滤波器用于跟踪。
  2. 优化
5. 多目标跟踪vs单目标跟踪
  1. 单目标跟踪的初始目标在第一帧给定(通常矩形框表示)，单目标跟踪要求可以处理任意类别物
  2. 多目标跟踪没有初始标注，由目标检测算法生成目标框。多目标跟踪算法主要负责每个目标的数字标识(ID)的帧间关联。跟踪过程中，原目标可能消失，新目标可能加入
6. 主动目标跟踪

第14章基于深度学习的图像分析

卷积层作用：平移不变性，局部感受野，权值共享
pooling作用：降低空间分辨率，去噪。
1. invariance(不变性)，这种不变性包括translation(平移)，rotation(旋转)，scale(尺度)
2. 保留主要的特征同时减少参数(降维，效果类似PCA)和计算量，防止过拟合，提高模型泛化能力
max pooling是无穷范数

可以用可学习的p范数代替（定义了一个在非欧几何空间的超球体），多个可学习的p范数组合能够对输入空间有重要的分离边界，但是会增加计算量
减少过拟合方法：BN; dropout; 正则化
参数规模计算
1. 卷积： $K^2\times C_i\times C_o+C_o$
2. 全连接： $T_i\times T_o+T_o$
计算复杂度 FLOPS
1. 卷积
2. 全连接: