滤波

高斯核的性质：

使用小方差的高斯核卷积多次和一个大的方差的高斯核卷积效果一样，比如使用方差为$\sigma$ 的高斯核卷积两次，和使用方差为$\sqrt 2\sigma$ 的高斯核卷积一次效果一样。上述关系类似勾股定理，第一次使用 $m\sigma$卷积，第二次使用$n\sigma$卷积，结果相当于使用$\sqrt{m^2+n^2}\sigma$卷积

m*m卷积核卷积n*n的图像，复杂度从$O(n^2m^2)$变为$O(n^2m)$
高斯卷积核可以分解为x和y方向，分解为两个方向分别卷积
选择卷积核大小：中心左右各3sigma，filter size：$2\cdot3\sigma +1$

中值滤波：

使用卷积核中的中间值作为输出（可以类比max pooling，看作median pooling），可以去除椒盐噪声或白噪声

边缘

Sobel算子：相当于先高斯后梯度
\[ \begin{bmatrix} -1 & 0 & 1\\ -2 & 0 & 2\\ -1 & 0 & 1\\ \end{bmatrix} = \begin{bmatrix} 1\\ 2\\ 1\\ \end{bmatrix} \begin{bmatrix} -1 & 0 & 1 \end{bmatrix} \]
Riberts算子：Mx检测135°的My检测45°
\[ M_x = \begin{bmatrix} 0 & 1\\ -1 & 0 \end{bmatrix} \qquad M_y = \begin{bmatrix} 1 & 0\\ 0 & -1 \end{bmatrix} \]
实际使用为了去除噪声，需要先高斯平滑，再提取边缘，这需要两次卷积：

为了合并成一次卷积，利用结合率 $\frac{d}{dx} (f * g) = f *\frac{d}{dx}g$ （求导也是卷积因此满足结合律，先对高斯求导，使用求导出的东西卷积），出来一个高斯偏导模板，类似高斯核，不过是使用高斯函数的导数去填充，即x方向上使用$\frac{\partial}{\partial x} \frac{1}{2\pi\sigma^2} \exp(-\frac{x^2+y^2}{2\sigma^2})$ 函数填充，y方向类似：

x-direction水平梯度，竖直边缘，y-direction垂直梯度，水平边缘

拟合

最小二乘，检测线，只在垂直方向：对于$XB=Y$的方程（$B=[m\ b]^T$）最优解满足
\[ X^T XB = X^T Y \]

无法应对垂直的线，那么使用到直线的距离和最小

上述的解：对于矩阵乘法：$AX=0$，那么使矩阵$A$特征值为0的特征向量就是解。

还可以从最大似然估计的角度看待

鲁棒的最小二乘：相当于阈值化距离，当距离过长时对error的贡献和较近的点类似，如下图，可以认为距离10和距离4最终error一样都是1，原本总损失由点到直线距离构成，现在改为这个函数，由于是非线性最优化，通常使用迭代的方法求解，以最小二乘算出来的为初始值迭代

参数选择：$\sigma$ 选择最小二乘后的平均残差的1.5倍

sigma太小：点对误差贡献基本一样，无法拟合

sigma太大：和不鲁棒的一样了

RANSAC

最小二乘当外点（不属于直线的点）比较多的时候不适用，此时ransac比较好，全名随机采样一致性（random sample consensus）.

基本思想：对于直线，两个点可以确定，那么随机采样两个点确定一条直线，其余点给这条直线投票（计算距离，距离小于门限的认为在直线上，投票），重复最终选择得分最高的直线

重复N次：

均匀地随机画出s个点
对这s个点拟合直线
在余下的点中找到该线的离群点（即与线的距离小于t的点其与直线的距离小于t)
如果有d个或更多的离群点，则接受该线，并使用所有的离群点重新拟合。异常点

关键的：我们需要迭代多少次才能拿到希望的结果。假设外点率$e$，我们希望直线的置信度$p$，那么需要迭代次数有如下关系：
\[ (1-(1-e)^s)^N = 1-p\\ N = \log(1-p) / \log(1-(1-e^s)) \]
其中s时估计曲线需要的点的个数，对于直线就是2，e为外点率，不属于直线的点

有关输出：可能输出最大的，也可以指定门限，投票大于门限的都输出，检测多条直线

真实的情况外点率不确定，自适应ransac

N=∞，sample_count=0
当N>sample_count
1. 选择两个点估计直线
2. 计算当前直线的外点率：$e = 1-(inliers / total\_num)$
3. 根据这个外点率计算$N = \log(1-p) / \log(1-(1-e^s))$
4. 给sample_count+1

RANSAC算出一条线后还会将所有内点最小二乘算出最终的线。

不止拟合直线，还可以指纹匹配

假设上面的形状是指纹上不同类型的模式，那么如果两个匹配，肯定会有一个变换矩阵使这些模式经过变换能够一一对应

变换矩阵6个参数，那么需要3对点构建上述方程。

那么我们可以：

选择三对点（3个不同类的，每类一对）
计算出变换矩阵T
其余的点给T打分

不停迭代，最后有一个最高得分的

霍夫变换

一种投票算法

首先需要将参数空间离散化，变成一个个能够投票的bins

以直线为例，图像中的一个线，参数空间中就是唯一对应的点，同时图像中一个点，经过它的所有线的参数在参数空间为一条线

那么图像中两个点分别在参数空间的线，相交，就是两点确定的直线的参数

求直线：直接用$y = ax+b$也可以做，但是参数没有边界，同时无法表达垂直的线

因此换成极坐标表示：
\[ x\cos \theta+y\sin\theta=\rho \]
$\theta$可以在0-180穷举，步骤表示如下：

还可改进，因为直线的点上梯度的方向垂直于线，可以通过梯度进一步缩小theta的搜索范围，考虑到梯度确定的直线方向可能有误差吗，可以在确定的theta左右取十几二十度为范围投票

最大的优势可以得到多个点（多个极大值）

但如果有噪声，投票到目标会减少，同时如果随机点多，还会出现伪峰值

噪声处理

选择更好网格或者离散化，如果噪声多可以网格大一点，但是会不够准确
提高邻居格子的评分（软门限），很有效，比如投票到某一格子，给该各自周边的bin也根据距离投票，比如中心投票加0.1，距离为1的加0.05，距离为2的加0.01，总分为1
减少外点数：只统计边缘的点和更确定的投票，比如对于直线，只投票梯度theta方向或theta附近方向投票

霍夫变换求圆：

在梯度方向投票，投在不同的半径区间内，如果梯度方向上没有正好对应的像素，以线性插值的方式给周围的两个像素按比例投票

Harris角点

好的特征的特性：

可靠性，在不同的角度、不同的图片中都能有这个特征
显著性：不能太平庸，得有代表性，不能和别的长得太像
计算高效
只和局部相关

角点检测，通过移动窗口并对前后的窗口相减就可以看出变化
\[ E(u,v) = \sum_{x,y} w(x,y) [I(x+u, y+v)-I(x,y)]^2 \]
x,y为窗口内坐标，u,v为窗口移动的距离

将上式用泰勒展开，最后只会留下二阶项（0，1阶为0）
\[ E(u,v)=[u\quad v]\begin{bmatrix}E_{uu}(0,0) & E_{uv}(0,0)\\ E_{uv}(0,0) & E_{vv}(0,0)\end{bmatrix} [u\quad v]^T \]
由于$E_{uu}(0,0) = \sum_{x,y}2w(x,y)I_x(x,y)I_x(x,y)$ 其他也可表示为类似的，最终可以表示为
\[ E(u,v)=[u\quad v]M [u\quad v]^T\\ M = \sum_{x,y}w(x,y) \begin{bmatrix}I_x^2 & I_x I_y\\ I_x I_y & I_y^2\end{bmatrix} \]
如果我们的角的两边分别和图片的长宽平行，那么M是一个对角矩阵，对应着一个垂直坐标轴的椭圆（因为上述是一个二次项，可以表示为一个椭圆），否则M四个元素都不为0，对应一个旋转的椭圆。我们可以进行对角化将其转化
\[ M = R^{-1}\begin{bmatrix}\lambda_1 & 0\\ 0 & \lambda_2\end{bmatrix} R \]
那么最终可以表示为
\[ \begin{aligned} E(u,v)&=[u\quad v] R^{-1} M' R[u\quad v]^T\\ &= (R[u\quad v])^T M'(R[u\quad v]^T) \end{aligned} \]
注：因为R正交所以转置和逆相等

这样就相当于把角旋转正。上面的lambda1，2是和椭圆的轴有关，$\sqrt{1/\lambda}$ 是轴的长度，lambda越大，轴越短，那么lambda越大那么梯度变化越快

最终可以分为如下情况：

lambda1，2都很小，变化都不强烈，所以是平坦区域
lamdba1>>lambda2或反过来，只在一个方向变化大，是边
都很大，是角点

最终判断通过公式：
\[ R = \det(M) - \alpha \text{trace}(M)^2 = \lambda_1\lambda_2 - \alpha (\lambda_1+\lambda_2)^2 \]
alpha经验值，取0.04到0.06，用M的行列式，减去M的迹（对角元素和），这样不用求特征值，对于$M=\begin{bmatrix}a&c\\c&b\end{bmatrix}$ 直接用$(ab-c^2)-\alpha(a+b)^2$

最终$R>0$是角点，$R<0$是边，$R\approx 0$ 是平坦区域

总体流程：

计算每个点的梯度（x和y方向的）
计算每个像素的二阶矩矩阵（需要每个像素画个小框计算M，并且用高斯加权，中心权重大，周围权重低）
计算R
根据R的阈值保留可能的角点
非极大抑制（在窗口内取最大的值）

观察代码实现：一半提取梯度和高斯统一使用Sobel完成（因为Sobel可以看作高斯核与梯度核的结合）

特点：

光照或亮度的变换$I \to aI+b$，如果整体亮度变化，$I \to I+b$，因为只用了导数方向，影响不大但如果$I \to aI$ 可能导致部分R可能小于或大于门限，对最终结果产生影响 invariance
shift平移，比如角在0，0和在5，5，点都会检测出来，但位置会不同，需要经过一个平移变换，因此是covariance（经过一些变换能够对应上）
旋转：同样是covariance
尺度：图像放大缩小：可以考虑极端的，如果一个角放大足够大，也会变得平滑而不是角点，因此不是尺度不变的

SIFT(Blob检测)

出发点：希望找到一种尺度不变的特征（针对角点的缺点），希望这个特征针对尺度是covariance的

可视化：希望找到一个特征选择器，给一个点向周围画圆，到合适大小时这个圆半径得分最高，之前之后都小

回忆之前：找边缘的时候，使用高斯偏导模板对信号卷积，相当于先高斯后偏导，在边缘处得到最大的响应，那么我们如果对高斯求二阶偏导呢？结果如下图：

边缘就是过零点的地方，二阶导也叫做拉普拉斯核

高斯核、一阶导、拉普拉斯核都遵循经验公式：filter size=$2\cdot3\sigma +1$，因此只用指定一个参数$\sigma$

当我们用固定参数的拉普拉斯核卷积不同大小的信号时，边缘可以看作是一个涟漪，而当信号和核的参数尺度匹配时，两个涟漪叠加形成一个极大值：

上图可以看出卷积核参数与信号的匹配性，那么我们如果使用不同的模板参数卷积，找出最大的模板参数就能得到尺度信息。但是使用拉普拉斯卷积，当方差过大时($\sigma$)，信号会被衰减，无法比较。

因为高斯偏导模板积分出来面积为 $\frac{1}{\sigma \sqrt{2\pi}}$ 为了使不受sigma影响，因此应当补偿乘一个sigma，而拉普拉斯是二阶导，因此补偿一个 $\sigma^2$，补偿前后效果：

将上述卷积结果的中心连在一起看就可以看出本章第一张图的效果，即圆的半径和得分的关系。

需要在x、y方向上分别应用这个核：
\[ \nabla^2g = \frac{\partial^2g}{\partial x^2}+\frac{\partial^2g}{\partial y^2}\\ \nabla_{\text{norm}}^2g =\sigma^2\left( \frac{\partial^2g}{\partial x^2}+\frac{\partial^2g}{\partial y^2}\right) \]
拉普拉斯核方差和图像上半径的关系：$\sigma=r/\sqrt 2$，结论：最大响应时信号的宽度正好和拉普拉斯核的0平面部分宽度一样

使用时使用多个尺度去卷积，得到一系列的尺度表达：

每三个相邻尺度为一组，看中间的的尺度是否是极大的，如果是，那么认为该尺度得到了匹配。（因为是三个相邻尺度比较，所以总体上一个点可能有多次被匹配，一个点画好几个圆）；因为一个点不仅有上下的不同尺度，还有同尺度的不同空间位置，因此在这里非极大抑制，只有中心点比周围26个点都大，才胜出

拉普拉斯如果全图搜索的话，需要做很多不同尺度的卷积，运算量很大，那么有两个个改进：

Harris-Laplacian：在角点附近搜索特征点
SIFT：Scale-Invariant Feature Transform

SIFT

提出了laplacian的改进：高斯差分DoG，结果和拉普拉斯很像：$G(x,y,k\sigma)-G(x,y,\sigma) \approx (k-1)\sigma^2\nabla^2G$

因为高斯核有个性质，大高斯核的卷积结果能够用多次小高斯核的结果得到，减少了卷积运算量（大卷积核运算量更大）

与拉普拉斯的对应关系：$\sigma \to \sigma_{lap}\quad k\sigma \to k\sigma_{lap}$ ，最终结果只相差一个常数$k-1$，相差一个常数无所谓，因为最终只对比相对大小，都差一个常数相当于都不差，依次类推

后者：相当于$G(x,y,k^2\sigma)-G(x,y,k\sigma) = (k-1)(k\sigma)^2\nabla^2G$ 是$k\sigma$尺度下的拉普拉斯响应的常数缩放(k-1)

同时，利用高斯核的特性：$k\sigma$的结果只需要在$\sigma$上再用$\sqrt{(k\sigma)^2-\sigma^2}$ 卷积就好，这个卷积核比$k\sigma$的卷积核小，提高了效率。

SIFT还把图像缩小到1/2，1/4等等不同大小，这样同样的核卷积出来的结果尺度大多个倍数，也不用更大的卷积核来做，减小了运算量同时检测到了更大尺度的特征。比如使用sigma=1检测到了特征，如果是原图上，这个特征对应的区域半径是$\sqrt2$，那么在缩小的图像检测出的，对应到原图上就是半径$2\sqrt2$的区域。

因此SIFT不同尺度区域的sigma是通过缩放图像不同倍数得到的，比如1-2的尺度在原图上卷积得到，2-4的尺度在缩小1/2的图上，4-8的尺度在缩小到1/4的图上得到。

k如何设置？$k=2^{1/s}$，其中s代表最终能输出多少个尺度，上图为例，一共得到了四个高斯差分，每相邻三个高斯差分的中间能得到一个最终的尺度表达，那么四个最终能输出$k\sigma$和$k^2$2个尺度的表达，因此$s=2$

这样能够形成连续的尺度空间，因此最初的高斯的层数取决于选择的s。

并且对于上图的情况，我们通常把倒数第三层直接下采样，就变成了上一级octave的第一层

有关不变性

拉普拉斯的响应：旋转和尺度不变invariant

Blob的位置和尺度是旋转和尺度的协变covariant

SIFT对于视角不是不变的，因为视角改变，圆可能变成椭圆

如果想对视角变化有一定鲁棒性：给出圆，然后计算圆内所有像素的M矩阵（Harris角点），看两个特征值，如果两个特征值相差多，把最初的圆在小特征值方向压扁成一个椭圆，再计算椭圆区域的M，重复上述步骤，直到区域内两个特征值差不多。仿射自适应。

我们依据仿射自适应把两个区域变化到一样的大小，可以发现内容基本一致，但是方向不同

为了处理角度不同：基于梯度方向。求出整个SIFT区域每个点的梯度强度和方向，画出梯度方向直方图（0-360分为8份），落到哪个方向范围就在对应的方向范围加上梯度的强度，以此得到信号变化最大的方向，根据这个方向将图旋转使方向归0

为了处理亮度的不同，最终使用梯度描述区域特征：最后把区域分为4*4=16份，同时每个小格分别统计梯度方向直方图，量化为8份（同上），将这8个数作为该小区域的一个描述，一共16个区域形成一个128维的向量作为区域的描述符

SIFT描述符不局限于SIFT算法：Harris+Laplacian也可以得到区域，也可以使用sift描述符表示。

拆分成小格：在局部上做直方图上统计，能够保留一些空间特征（patch顺序保留了一些空间信息）

SIFT特征匹配

两张对同一物品的图片如何匹配SIFT特征，两两计算特征距离，但是如何定义门限？

对于一个特征，看与他匹配的另一张图的特征的第一近邻和第二近邻的距离，如果差异较大，说明匹配成功；如果差异不大说明匹配模糊，可能错误丢弃

纹理

用处：

从纹理中恢复形状（从纹理的变化）
分割或分类：不同物体的纹理特性不同，识别不同的材质，识别水果，区分动物。
合成：给定纹理合成更多的纹理，下图给出了纹理的分类和合成区别

希望找到一种特征比边缘更高级，表示纹理。

纹理由重复的一些模式构成，那么我们需要发现模式，描述区域里模式的关系。

纹理表示：分成小窗口，计算水平和垂直梯度，表示到二维平面上，可以看出能够分为几类，可以使用kmeans聚类

这种表示方法有尺度问题：窗口大小的选择，可以选择不同大小的窗口，某一段尺度窗口大小纹理信息不怎么变化代表尺度合适。

只用边缘信息可能不够，那么我们可以使用更多的滤波器获得更多的特征，d个滤波器获得d维的特征，比如下图，考虑了尺度、方向，检测了边、条、点

上述斜着的高斯核协方差矩阵中x，y相关

获得到这些特征后，每个像素都对应一个48维的向量，我们可以做global avg pooling，最终用一个48维的向量表示图片做分类，或者直接拼接。（操作和卷积神经网络最后的分类头一模一样）

分割

过分割：把大物体中间分开

欠分割：小目标没分开

superpixel：把粒度提高了，相似的像素变成一个个小区块，图块比像素数量小

自顶向下：从整体的语义出发，通过语义的相似性去分割

自底向上：从底层像素的相似性出发来分割，聚类（无监督）

人的感受：哥斯达理论，群组感受，同样的线和箭头，不同的组合有不同的感受，会按照先验的知识去理解整体的语义

分割依据：距离近、相似（形状、颜色等）、共同的命运（运动方向）、共同的区域、平行的、对称的、连续性、封闭的几何形状

电梯按错：没有群组不好判断哪个数字对应哪个按钮

分割方法：聚类

将相似的像素聚类，比如使用RGB三个维度表示一个像素，三维空间中kmeans聚类；还可以基于灰度聚类（只有一维）

分割：语义分割、实例分割

为了可能实现实例分割、分割同类不同的物品，可以在像素特征中加入位置信息（但可能过分割，比如一个大的物体因为物体内像素位置差别大被分为多个类）

kmeans：对外点敏感；同时有一个假设，球形的聚类（非球型用高斯混合模型）

Mean Shift 均值漂移

不仅可以用于分割。

在寻找特征空间或模式中最大密度的中心

基本思想：对于一组点，随机选一个初始，画一个区域，之后计算区域的重心，将计算出的重心变成新区域的中心，重新计算新区域，重复该过程就能找到密度最大的中心。

如何分割：对于图像上点的特征，如果最终找到的中心是中心1，那么就分类为1，中心是2分割为2，如下图最终特征流向了多个中心

这样不需要指定中心，最后流向几个中心，就有几个类

优点：没有假定是球型的聚类；只有一个参数（窗口大小，决定了能不能跨域局部的密度中心，得到更大的分割）；可以得到不确定数量的类（受窗口大小影响）；不受噪声影响

缺点：特别依赖窗口大小；计算量大（可以改进，shift过程的路径上的点也可以直接当成一类）；对高维特征不好用（维度高的时候，可能点会很稀疏，窗口范围内就没几个点，导致无法准确找到重心进一步更新）。

图像看成图(graph)

每个像素都是一个图中的节点，每个边的权重是像素间的相似度。分割就是删除graph中的边，那么目标可以看作在图中找一个切分图的方法，使切掉的边权重最小。相似的像素都在一起。

相似性函数：假设定义好了特征向量和距离函数，通过下式控制相似性
\[ \exp\left(-\frac{1}{2\sigma^2}\text{dist}(x_i, x_j)^2\right) \]
通过$\sigma^2$ 控制相似，当 $\sigma^2$ 小，那么距离变化很小的时候，相似性衰减快

Minimun cut

最小割问题，图论中有方法，不叙述了。

但直接用可能出现切除很多独立的小块

normalize cut归一化图割：

\[ \frac{w(A,B)}{w(A,V)} + \frac{w(A,B)}{w(B,V)} \]

$w(A,B)$ 意为A部分，B部分之间的所有有连接关系的点的连接边的求和，原本倾向于直接让w(A,B)最小，一边是A，一边是B，现在归一化的是除以分割后和所有点的的联系$w(A,V)$ 中V是所有点，这样不鼓励只有一条边被割（假设A是单独的一个点，那么w(A,V)肯定不大，因此整体值就增大）

如何计算：

前置步骤：首先选定图像像素的特征表示，RGB也好，RGB+XY也好；之后选择向量距离，L1，L2，cosine都行；选择相似度中的$\sigma$ ，之后步骤如下：

定义一个W叫做邻接关系矩阵，记录相似度，$w_{i,j}$ 为第i个和第j个像素的相似度，特别的自己和自己的相似度定义成0。w是对称矩阵
定义D为一个对角矩阵，第$d_{i,i}$是W中第i行所有结果相加的结果 $D(i,i) = \sum_j W(i,j)$
理想中求出向量y，向量维度是像素个数，y内元素只有0和1，将像素分为两类，即将图割开。每次割出来两类
那么我们需要最小化的cost形如：
\[ \frac{y^T(D-W)y}{y^TDy} \]
拉格朗日法求最小化，上面分数形式最小化，例如$A/B$最小化，通常写成最小化$L=A+\lambda B$其中λ是拉格朗日乘子对于上式就是$L=y^T(D-W)y+\lambda y^TDy$
求最小值，求导，由于$\lambda$可正可负，所以后项的正负号不影响，可以写成负号，求导等于0后可以得到
\[ (D-W)y=\lambda Dy \]
结论：解为$(D-W)$第二小的特征值的特征向量，因为第一小对应的是0，标准解，不需要。
求出来的y不是0和1，那么需要设定一个门限，大于门限为1，小于门限为0得到$\hat y$，确定门限可以带回到cost，哪个门限最小选择哪个门限
使用$\hat y$将图分割
循环的分割割出来的子图，或者对于上面$(D-W)$分解出的所有特征向量聚类，可以这样理解：每个特征值对应一个分割方法，那么将分割方法聚类，聚类出k个类别，将相似的分割方法看成同一种分割方法，聚类中心作为分割方法的代表

如何表示像素特征：RGB固然是可以的，也可以使用纹理表示的方法（上节内容，用多个滤波核的结果表示成向量）纹理效果很好：

但是用纹理也有问题，可能会把边缘单独分为一个类（因为边缘的纹理特征和内部不一样）消除影响：分析中间轮廓，如果和外边轮廓相似认为是一个类

优点：一个总体的框架，可以选择很多种的特征

缺点：很高的计算和存储要求（pixel和pixel之间，高分辨率图像带来很高的特征数量）；有把物体平均分割的偏差（bias）

识别&分类

分类的级别：

整图的分类：猫、狗
目标检测：框出来哪里是物体，区域级的分割
分割：像素级的分类

识别任务有两种：

单实例识别：认出来确定的某一个物品，比如天安门、北邮西门
类别识别：识别某一类的，比如猫、狗、所有的大门

识别面临的问题：

类别多，人类可以识别10000-30000种物品
视角变化
光照：对颜色等信息造成影响
尺度：物品占图像的比例不同，希望能够对抗尺度变化
形变：猫可能有很多变化，站着、坐着、躺着
遮挡：
背景杂波：
类内变化：同一种物品不一样，比如不同的椅子

识别系统：

表达：如何表达一个物体的类别
学习：如何从训练数据中学习一个分类器
识别：如何应用分类器到新的数据上

表达

一般用区域表达图像：比如SIFT、其他检测器、直接将图像均分为块、随机采样一些区域

可以直接将区域当成特征表示（词袋），也可以考虑区域的相对位置关系。

表达图像：词袋、纹理

我们想达到invariance，主要针对视角、光照、遮挡和尺度

词袋

将图像打散成块，装进“袋子”，对遮挡、视角的小变化、平移等不太敏感

起源：纹理表示，通过纹理基元的统计特征表示为直方图

提取特征
构建视觉词典
把图像表示成词典

词典大小：一般取总特征数的1/10-1/100

空间金字塔表示

词袋缺少位置信息，使用空间金字塔表示，整图表达为一个词袋，图切成4份，每个区域也能表达成一个词袋；同理还能分成16份，把这些词袋全部拼接，作为整个图的表示，代表了一些空间上的含义

学习

产生式、判别式

判别：区分不同的分布

产生：建模事物的规律，直接学习分布

判别模型建模的是后验概率，生成模型建模的是似然和先验概率

先验描述整体上是斑马和不是斑马的概率，似然描述是斑马和不是斑马的图像的分布，后验描述给定图像是斑马和不是斑马的概率。根据上式，生成模型也能判别：建模出了似然和先验，那么对于给定的图片（相当于一个随机变量的值）可以计算出对应的似然和先验，那么就得到了后验概率比值。

学习就是去调整模型参数使某个指标最大。

标签等级：noise label 弱监督，可能标签是错的

标签是整个给的还是增量的：可能一次给出所有样本，还可能是增量学习，一天增加几个

先验：先验如何获取，从领域或行业知识获取

检测任务最终目标：从图像中的一堆窗口中判断窗口是否是目标（包含窗口的位置，角度，大小，类别）

目标检测

希望得到目标的位置：建立一个检测的模板，在图像中搜索哪一部分可以和模板匹配到。

难点：

光照、物体的姿态、杂波、遮挡、类内的外貌不同、视角；
不能和背景混在一起，那么如何建模背景，特征容易混淆的物体
如何高效搜索：不同尺度、不同位置的框很多
如何设计特征建模物体
如何解决不同视角：12年之前使用不同的模型训练不同的视角

人脸检测

检测和识别：检测拿出人脸，识别认识是哪个脸

单张图人脸较少，那么在背景处少检测，脸部分多检测

使用Adaboost

Boosting算法

集成多个弱分类器：给定n个二分类的弱分类器，首先分类，选出分类精度最高的（大于50%），把他的权重加大

最后分类器：
\[ h(x) = \alpha_1h_1(x) + \alpha_2h_2(x) + \alpha_2h_2(x)+\cdots \]
单个分类器：
\[ h_j(x) = \left\{ \begin{aligned} &1 \quad f_j(x)>\theta_j\\ &0 \end{aligned} \right. \]
总的分类器：
\[ h_j(x) = \left\{ \begin{aligned} &1 \quad \sum_{t=1}^T \alpha_t h_t(x)>\frac{1}{2}\sum_{t=1}^T\alpha_t\\ &0 \end{aligned} \right. \]

Boost在人脸检测

训练很慢但推理很快

主要思想

积分图，建立多个有分类能力的弱分类器
特征选择上应用boosting，使用上述弱分类器组合强分类器
使用级联块拒绝非人脸的区域

每个弱分类器有以下属性：

4个type，通过卷积核拿到，白区域减黑区域
pos：区域的位置x,y
size：区域的面积w,h

最终每个分类器只负责自己pos和size区域的type特征，结果大于门限投1分否则0分作为分类结果

计算所有的卷积比较慢：加速使用积分图

积分图

图中$i,j$位置的值是他左上方所有像素的求和

\[ I_\sum(x,y) = \sum_{x'\leq x; y' \leq y}i(x', y') \]
有了积分图后，可以很方便的计算面积（区域内的像素求和）：

\[ S_{ABCD} = A-B-C+D \]
三次加法就能得到任何区域的求和。

算法详细可以参考人脸检测算法之Haar-Adaboost分类器原理 - 简书 (jianshu.com)，下面简述步骤

步骤：

对于每个弱分类器（type、pos、size）：输入所有的训练图片（可能有几万张）根据分类的结果，选择最优的门限，在可能的范围内枚举，选择最好的。
选择分类器的最优的权重
1. 所有样本权重归一化，如果是第一次，所有权重一样
2. 对于每一个特征 $\epsilon_j = \sum_i w_i |h_j(x_i) - y_i|$其中的$w_i$是样本的权重，训练的时候使用的，用来给不同样本不同特征，从而筛选出不同的分类器
3. 选择最低错误率的分类器
更新权重（把分正确的样本权重缩小，相对的错误的权重就增大，能选出下一个分类出这些错误样本的分类器）
\[ w_{t+1, i} \gets w_{t,i}\beta_t^{1-|h_t(x_i) - y_i|} \qquad \beta_t =\frac{\epsilon_t}{1-\epsilon_t} \]
最终分类器：
\[ h(x) = \left\{ \begin{aligned} &1 \quad \sum_{t=1}^T \alpha_t h_t(x)>\frac{1}{2}\sum_{t=1}^T\alpha_t\\ &0 \end{aligned} \right. \qquad \alpha_t = \log \frac{1}{\beta_t} \]

需要强调的是：训练的时候数据只有单独的人脸，每个24*24；推理的时候把图像割成不同大小的区域，reshape到24*24，送到分类器中判断区域是不是人脸。

对快速检测的级联：

因为上面的检测虽然精度高，但是每张图有极大数量的特征，如果都送到上面的强分类器中需要很大的运算量和时间

将强分类器级联，每个强分类器不需要很高的精度（Precision），假阳率高没问题，但要尽可能的将正样本判断正确（高召回率）。比如只需要50%正确率，输出100个预测的正样本，只要其中50个是真正的正样本即可。
在前一个分类器的基础上，只分类被第一个分类器过滤的区域（每层只考虑前一层没有解决的问题）

分清楚：

漏检率，如果每个召回率99%，漏检1%，那么如果叠10层，那么最终只检测出$0.99^{10}\approx0.9$
误检率：如果每个误检率0.3，那么最终误检$0.3^{10} \approx 6*10^{-6}$

针对级联的，每个强分类器都需要学习，一个个训练，训练完挂在级联串后面，指定强分类器的指标，比如召回率0.99，查准率50%

级联的训练：

正样本：5000张脸24*24，负样本：9500张非人脸图片中抽取出的300m负样本

每轮训练5000正，5000负

对于stage1：5000正样本，从9500张负样本中随机（大小、位置）扣出来5000张负样本，变为24*24的

对于stage2：5000正样本不变，再从9500张负样本采样负样本，送给stage1，stage1分错的（负分类成正），送给stage2当作负样本，也这样采样出5000个负样本

后面的stage同理

检测出人脸后还可以做人脸识别：

找出人脸
定位眼睛嘴巴鼻子
将上述五官缩放定位到标准模板
最终分类

行人检测

对于每个行人的样本，计算梯度直方图

步骤：

图像必须是64*128的，将图像分成16*16的block，block分成4块，每块8*8，在这个8*8的区域内提取梯度方向直方图（9个方向，每40°分一次，因此是9维），那么一个block就是4*9=36维。

对于第二个block，在第一个block的基础上步长为8，相当于重叠一半，继续这样计算。

这种方式可以得到105个区域，每个区域36维，最终得到3780维的HoG特征。

拿这个向量训练SVM。

之后对于给定的图像可以选取一个64*128的区域，按上述方法提取特征，拿线性SVM分类，最终非极大抑制

本质就是通过SVM选择出了一个模板，测试的时候将特征和模板进行比较。

本身就是滑动窗口的方法：

非常时候人脸检测
车和行人检测也不错
对狗、猫等检测效果不好，因为他们会形变

摄像机模型

摄像机内参

一般我们分析的是虚拟像平面，正着的，和真正的像平面对称。

通过如下相似三角形建立真实的三维点和像平面坐标点的关系：

对于透镜摄像机，依然可以建立以上关系，只用关心$z'$即可：

但是透镜相对于小孔，在景深外的物品会模糊，同时还会出现径向畸变，做后续任务的时候需要将摄像机的图像校正消除畸变

由于我们的图像由像素构成，那么我们更希望建立三维坐标和像素的关系，需要将像平面上的坐标转化为像素坐标

由于二维坐标通常使用中心作为原点，而像素平面使用左下角，所以需要加上偏置，同时还有像素对应的长度的缩放系数

这样建立以后，以x为例，可以写成
\[ x' = \alpha\frac{x}{z} + c_x \]
由于x下还有一个变量z，x和x'不是线性变化的，因此引入齐次坐标

换成齐次坐标表示，就可以写成如下形式：

前面的矩阵可以写成$M$，那么可以表示为
\[ P' = MP \\ M = \begin{bmatrix} \alpha & 0 & c_x & 0\\ 0 & \beta & c_y & 0\\ 0 & 0 & 1 & 0\\ \end{bmatrix} \]
此时两个坐标之间就是线性变换，只不过换成了齐次坐标（P': 3*1，P：4*）

如果考虑到摄像机成像像素不是垂直的，而是有一定夹角，不是矩形，那么M表示为：

此时，我们称M为投影矩阵，M左侧的方阵称为摄像机内参矩阵

将二者分开可以写做如下形式，其中$I$为3x3的单位阵

当K为单位矩阵时，称对应的M为规范化投影，对应的相机是规范化相机

相机可以规范化：我们令$\bar P = MP$ ，此时$\bar P$ 维度为3*1，此时在最后一位拼接一个常数得到最终的$\bar P$，这是想要把$\bar P$ 转化为P就只需要一次规范化投影。

摄像机外参

选取一个世界坐标系独立于摄像机之外，摄像机在世界坐标系中有独立的位置，我们最终的目标是从世界坐标系中转化为像素坐标，那么就需要建立世界坐标系到摄像机坐标系的转化，解决三维物体描述方便性问题。

世界坐标系的点经过旋转平移之后得到摄像机坐标系（R表示旋转矩阵，T表示平移，由于R是正交矩阵，因此转置和逆相等）：
\[ P = RP_w+T\\ P_w = R^\top(P-T) \]
那么写成齐次坐标如下：
\[ P = \begin{bmatrix} R & T\\ 0 & 1 \end{bmatrix} P_w \qquad P_w = \begin{bmatrix} x\\y\\z\\1 \end{bmatrix} \]
整体的转化就如下式：

形状：R 3*3, T 3*1, K 3*3, M 3*4

此时投影矩阵M完成了世界坐标到像素坐标的转化（齐次坐标）

特别的，摄像机的光心（摄像机坐标的原点）在世界坐标系的坐标为$O = -R^\top T$（根据上面的转化公式）

M的自由度：K有5个，R有3个（三个旋转方向），T有3个，一共11个自由度

我们还可以将M写为
\[ M = \begin{bmatrix} m_1\\m_2\\m_3 \end{bmatrix} \]
其中每行是一个1*4的向量，那么$MP_w$就是$[m_1P_w\quad m_2P_w\quad m_3P_w]^\top$，那么 $m_1P_w$等都是标量，最终可以直接将欧式坐标写出来
\[ P = \begin{bmatrix} \frac{m_1P_w}{m_3P_w} \\ \frac{m_2P_w}{m_3P_w} \\ \end{bmatrix} \]
M还可以得到很多信息：

0倾斜：摄像机像素两个边垂直

最后一个：像素是正方形

其他摄像机

弱透视：当相对场景深度小于其与相机的距离时，物体到相机的距离$z_0$看作一个固定值，假设物体都来自一个空间上的平面上

与透视关系：相当于m3变为[0 0 0 1]

正交投影 - 更多应用在建筑设计(AUTOCAD）或者工业设计行业

弱透视投影在数学方面更简单 –当物体较小且较远时准确，常用于图像识别任务

透视投影对于3D到2D映射的建模更为准确 –用于运动恢复结构或SLAM

摄像机标定

求解摄像机的内外参数

标定问题：世界坐标系中点$P_1\cdots P_n$位置已知，同时相机图像中$p_1\cdots p_n$也知道，求解相机内参

整理出表达式：

给出一对点，可以建立两个方程，前一章M有11个自由度，因此需要6对点就可以求出M的参数。通常我们选择多于6对点来获得更加鲁棒的结果。

11个未知量12个方程：超定，n对点方程表示如下

对于超定方程：

下面文字是$\min_m \Vert P m\Vert \quad s.t. \Vert m\Vert=1$ 后面的约束是因为不加约束m可以成比例的一直缩小到0

结论：对$P$进行奇异值分解：$U_{2n\times 12} D_{12\times12}V^\top_{12\times12}$

m为最小奇异值对应的右奇异向量（V）且$|m|=1$

拿到m之后就可以求摄像机的内参数，结论如下，其中A为M左边3*3的方阵，b为列向量

需要注意的是，选择的用于标定的点不能位于同一平面

三维重建与极几何

单单从一张图片很难重建关系，无法正确感应深度，单视图2D到3D有多义性。

三角化

已知摄像机坐标和内参，以及三维点在两个图像上的位置，求出三维点的坐标。通过两条线的交点得到P的坐标，实际上对于有参数abc的直线$l=[a\quad b\quad c]^\top$，两条直线叉乘就是交点坐标。

但由于噪声和误差，两条线一般是不相交的。

一般两种解法：线性和非线性解法，线性就是列方程，不详述，下面主要叙述非线性。

将目标转化为，在空间中找到一个最优点$P^*$使其在两个成像平面的坐标和实际坐标相差最小

通常我们使用牛顿法和L-M方法求解（可以理解为使用了二阶导数的更精确的梯度下降）

我们通常使用$O_1$作为世界坐标系那么$M=K[I\quad 0]$其实就是摄像机的内参数，同时又已知第二个摄像机关于第一个摄像机的R和T，那么$M'=K'[R\quad T]$以上求解就是可行的，最终$P^*$求出来的就是$O_1$坐标系下的

通过以上分析我们知道：需要两个摄像机的内参数，摄像机之间的R和T。

关键问题：

摄像机几何：从一张或者多张图像中求解摄像机的内、外参数

场景几何：通过二至多幅图寻找 3D 场景坐标

对应关系：已知一个图像中的$p$点，如何在另外一个图像中找到$p'$点

极几何

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

极几何的几个关键概念：

极平面：灰色平面；基线：橙色线；极线：蓝色线；极点：两个e点

极线相交于极点：不同点在同一成像平面上，有很多极线，都相交于极点

后两点：将搜索范围缩小到对应的极线上。

特例：

本质矩阵

本质矩阵对规范化摄像机拍摄的两个视点图像间的极几何关系进行代数描述，$M=[I\quad0]$，

摄像机坐标系下三维点的欧式（非齐次）坐标 = 图像点的其次坐标

最后一行：空间点 p在 01 坐标系下的非齐次坐标为(u,v,1)，空间点 p'在O2坐标系下的非齐次坐标为（u',v',1)可能最终差一个系数（可以这样理解，在pP和p'P线上的都可表示为两种形式）

那么p'在O1坐标的坐标是什么？二者满足什么关系？

上面最终的结果通过O1p'和O1O2叉乘得到，这两条线叉乘垂直于极平面，那么点乘p向量（O1p）肯定等于0

向量叉乘矩阵可以写成上述叉乘的矩阵表示，将向量写成一个矩阵和后面的东西进行矩阵乘法，那么最终可以表示如下：

上面的$E=[T_\times]R$被称为本质矩阵

上式可以得到如下结论：

第一二点：可以这么理解，以第一点为例，因为p点对应的p‘一定在极线上，根据上面E的定义描述的约束，p’一定在极平面上（因为叉乘结果和O1p点乘为0）p‘又在成像平面上，那么描述的约束就是极线，因为点p在直线l上的充分必要条件就是直线l 的系数与p的齐次坐标p’的内积为0（可以参考这个对极约束、本质矩阵(E)、基础矩阵(F) - 静精进境 - 博客园 (cnblogs.com)）

基础矩阵

本质矩阵在规范化，那么基础矩阵推广到一般的透视摄像机

思路：变换到规范化摄像机！

同时乘以$K^{-1}$最终得到$p_c = K^{-1}p$那么$p_c$和P之间是一个规范化摄像机的关系

根据以上带入到之前的本质矩阵的约束

性质如下图所示：

已知 𝐹 ,无需场景信息以及摄像机内、外参数，即可建立左右图像对应关系

基础矩阵估计

对应点已知，如何估计基础矩阵

F有7个自由度，理论上 7个点即可求解F，但计算方法比较复杂。所以我们使用八点法

使用SIFT特征，在两张图中选择8组对应的点，列方程

同样和之前一样，选择最小奇异值的右奇异向量。

基础矩阵秩为2，而求出来的$\hat F$通常是满秩的，那么我们找到如下的F

对$\hat F$进行奇异值分解，之后直接让$s_3=0$再乘起来。

总体步骤：

但是有问题，精度比较低，原因是 W 中各个元素的数值差异过大，因为包含坐标乘积，可能有几千乘几千，也可能有个位数相乘，相差过大导致SVD分解有数值计算问题

更常用归一化八点法：对每幅图像施加变换T(平移与缩放)，让其满足如下条件：原点 = 图像上点的重心；各个像点到坐标原点的均方根距离等于$\sqrt 2$ (或者均方距离等于2)。（可能是距离平方求平均再开方？$\sqrt{\sum_i d_i^2/n}$）

那么，步骤为：

双目立体视觉

使用平行视图进行深度估计

对于普通情况下的基础矩阵：
\[ F=K'^\top[T_\times]RK^{-1}\\ e' = K'[R\quad T] [0\ 0\ 0\ 1]^\top = K'T \]
上面的$e'$，因为e‘可以看作O1在第二个摄像机的平面上的投影，那么$[0\ 0\ \ 0\ 1]$就是O1在O1坐标系的齐次坐标，乘以旋转和平移矩阵变换到O2下，最终通过K'变到O2的平面上。

利用叉乘的性质和一些推导，可以得到$F$有关$e$的表达形式：

相差一个尺度：等式左右可能差一个倍数，我们不关心这个倍数

此处$e'$为平面上的齐次坐标

有关平行视图的性质：

两摄像机一般选择相同的$K=K'$，没有旋转$R=I$，只有x的平移$T=[T\ 0\ 0]^\top$，e'在无穷远点，那么齐次坐标为$e' = [1\ 0\ 0]^\top$，那么最终可以得到$F$的表达：

据此，我们可以得到如下结论：

p和p'都在一条线上，称为扫描线：p'点沿着扫描线寻找即可！！！

平行视图三角化

俯视整个系统

过O1做O2P的平行线，与扫描线相交，那么$O_1p_up_2$和$p_up_u'P$构成相似三角形，同时$p_up_u'P$又和$O_1O_2P$相似，那么$p_2p_u$和f的比值等于$O_1O_2$和z的比值，得到上述结论，因此有视差和相机位置，就能得到深度
\[ z= \frac{B\cdot f}{p_u-p_u'} \]

构建双目立体视觉系统

双自立体视觉系统构建的两个核心问题：

如何获得平行视图？
如何建立点对应关系？

图像校正

需要两个图像被校正后满足之前的平行视图的性质：

极线是水平的平行于u轴
极点位于无穷远
p和p'的v坐标一样！

前两点需要$e'=[1\ 0\ 0]^\top$

那么校正步骤：

在两幅图像I和I'找到一组匹配点$p_i\leftrightarrow p_i'$；，不少于8个
计算基础矩阵F，求解两幅图像中的极点e和e
选择透视变换H将e'映射到无穷远点（f，0,0)。
\[ H' = T^{-1}GRT \]
寻找对应的透视变换矩阵H使得下式最小
\[ \sum d(Hp_i, H'p_i') \]
分别用矩阵H和H，对左右两幅图像I和I进行重采样

第二步求e和e'，所有极线交与极点，那么可以求解(第一个图)，超定的，用最小二乘解：

第三步上右图，首先将中心移动到图像中心[0, 0, 1]（原来一般在左上），使用平移变换。接着使用第一步得到的$e_1'$和$e_2'$构造旋转矩阵，旋转矩阵乘以原来的图像，得到新的e'坐标(f, 0, 1)；最后构造G矩阵，和G相乘，e'最终变为(f, 0, 0)，上述变换可以用$H' = T^{-1}GRT$描述

第四步：找到了H’变换右图，那么左图的变换可以通过最小化函数$\sum d(Hp_i, H'p_i')$ 得到$H$，就是变换之后的对应点距离最小。（可能使用L-M算法？）

最后使用H和H'校正图像

对应点搜索

沿着扫描点找对应点：相关法，四步完成

说白了就是找两个向量最小的类似余弦相似度的东西

如果亮度剧烈变化，那么使用归一化相关匹配
\[ \frac{(w-\bar w)(w'-\bar w')}{\Vert w-\bar w\Vert\cdot\Vert w'-\bar w'\Vert} \]
$\bar w$和$\bar w'$是窗口内的灰度均值，相当于将均值归0后求余弦相似度

窗口大小会影响：

更好的匹配方法就是图割的方法

计算机视觉

滤波

边缘

拟合