期末复习

Image Filtering 1

集合, 映射/函数, 算子

定义 1 函数

$f=\{(x,y)|y=f(x)\}\subset \mathbb{R}\times \mathbb{R}$. 是定义在 $\mathbb{R}$ 上的函数.

定义 2 点算子

$f'=T[f]$, 点算子 $(x',y')=T(x,y)$, 也即 $y'=f'(x')=(Tf)(x')=T(f(x))$.

例 3

如果 $y=f(x)=\dfrac{1}{\sqrt{2\pi}\delta}e^{-\frac{x^2}{2\delta^2}}$, $\begin{bmatrix} x'\\ y' \end{bmatrix}=T(x,y)=\begin{bmatrix} \dfrac{x-a}{s}\\ ky+d \end{bmatrix}$ 求 $y'$ 用 $f, x'$ 表示.

$y'=ky+d=kf(x)+d=kf(sx'+a)+d$.

偏导 $$ \frac{\partial f'(x')}{\partial f(x)}=k $$

$$ \frac{\partial L}{\partial f(x)}=\frac{\partial L}{\partial f'(x')}\cdot\frac{\partial f'(x')}{\partial f(x)}=k\frac{\partial L}{\partial f'(x')}=k\frac{\partial L}{\partial f'(\frac{x-a}{s})} $$

定义 4 区域算子

$$ \begin{bmatrix}x'\y'\end{bmatrix}=Tf=\begin{bmatrix}x\ f*h(x')\end{bmatrix} $$

卷积和相关

定义 5

- 交叉相关 (cross correlation) $$ \begin{aligned} S[f]=w\otimes f\ Sf=\sum\limits_{i=-k}^k\sum\limits_{j=-k}^k w(i,j)f(m+i,n+j) \end{aligned}$$ - 卷积 (convolution)$$ \begin{aligned} S[f]=w*f\ Sf=\sum\limits_{i=-k}^k\sum\limits_{j=-k}^k w(i,j)f(m-i,n-j) \end{aligned}$$

性质 6

相关核 $g(x,y)$, 与卷积核 $g'(x,y)$ 满足中心对称关系 (二维情形), 即 $$ g(x,y)=g'(-x,-y) $$

锐化 (sharpening)

设 $f$ 为原始图像, $v$ 为滤波核 (均值滤波 / 高斯滤波), $w$ 为恒等映射.

则经过滤波的图像 $f_{blur} = v*f$, 由于滤波后各像素之间变平滑, 即特征变模糊, 所以考虑 $f-f_{blur}$ 其实就是图像的特征部分如下图所示.

那么想要锐化图像, 即增强其特征就考虑将这部分差值增加. 设权重为 $\alpha$, 锐化后的图像可表示为 $f_{sharp}=f+\alpha(f-f_{blur})=(1+\alpha)w*f-\alpha v*f=((1+\alpha)w-\alpha v)*f$. 该推导过程根据卷积的性质.

滤波

卷积方式: 三种

设图像大小为 $m*m$, 卷积核大小为 $k*k$. - 全卷积, 只要卷积核和原图像有重合就输出该点结果. 这会使得输出图像变大, 输出大小为 $(m+k-1)*(m+k-1)$. - 相同卷积, 输出卷积核中心与原图像重合结果. 输出大小与原图像大小一致, 为 $m*m$. - 有效卷积, 只输出卷积核完全与图像重合的点, 会使得输出图像变小, 输出大小为 $(m-k+1)*(m-k+1)$.

时间复杂度: 图像大小 $w*h$, 卷积核 $k*k$. 每次卷积复杂度 $O(k^2)$, 卷积次数 $O(wh)$, 总复杂度 $O(whk^2)$.

如果是可分离卷积, 那么单次卷积复杂度为 $O(k)$, 总复杂度 $O(whk)$.

边界情况: 四种处理方式 - Clip filter, 填充为 0, 即全黑 - Wrap around, 将原图片环绕一圈. - Copy edge, 直接复制边界点. - Reflect across edge, 关于四条边界做对称.

均值滤波: 取滤波核范围内所有点平均得到滤波结果. 滤波核 $w(p,q)=\frac{1}{|N_p|}$
高斯滤波: 依据高斯分布给滤波核赋权重, 求加权平均值. 滤波核 $w(p,q)=\frac{1}{S}\exp\left(-\frac{\Vert p-q \Vert^2}{2\sigma^2}\right)$, $S=\sum\limits_{r\in N_p}\exp\left(-\frac{\Vert p-r \Vert^2}{2\sigma^2}\right)$. 由于要采样整数点的高斯分布值, 故需要对全体做归一化.

一维: $G_{\sigma}=\frac{1}{\sqrt{2\pi\sigma^2}}e^{-\frac{x^2}{2\sigma^2}}$. 二维: $G_{\sigma}(x,y)=\frac{1}{2\pi\sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}}$.

$\sigma$ 越大越模糊, 因为权重越接近.

高斯滤波可分离: $G_{\sigma}(x,y)=G_{\sigma}(x)*G_{\sigma}(y)$.

$Dog$ 滤波核: 两个高斯滤波结果的差.

$\sigma$ 一般取图像对角线大小的 $2\%$.

双边滤波: 既考虑空间上距离的权重, 也考虑颜色值域差异的权重.

高斯滤波缺点: 只有空间距离不能检测出边界, 会将边界信息过度模糊.

双边优点: 综合考虑色彩差异的权重, 能更好的识别边界信息.

双边缺点: 滤波核与具体点周围情况有关, 每个点的核都不一样, 计算复杂度过大.

定义 13

综合考虑位置远近和灰度值差距.

$$ BF[I]_p\quad=\quad\frac {1}{W_p}\sum\limits_{q\in S}G_{\sigma_s}(\Vert p-q \Vert)G_{\sigma_r}(|I_[-I_q]|)I_q\quad $$

优势: - 易于理解. - 自适应. - 不用迭代.

缺点: 速度慢.

傅里叶变换

一维

连续:

空间域 $\to$ 频域: $F(\omega)=\mint[-\infty]^\infty f(x)e^{-\text{i}\omega x}\text{d}x$.

频域 $\to$ 空间域: $f(x)=\frac{1}{2\pi}\mint[-\infty]^\infty F(w)e^{\text{i}\omega x}\text{d} w$.

离散:

傅里叶基函数: $B_{k}(n)=e^{\text{i} 2 \pi k n /N}$. 信号可以表示位基函数的线性组合.

空间域 $\to$ 频域: $X(k)=\sum\limits_{n=0}^{N-1}x(n)e^{-\text{i} 2\pi k n/N}$.

频域 $\to$ 空间域: $x(n)=\frac1N \sum\limits_{k=0}^{N-1}X(k)e^{\text{i} 2 \pi k n /N}$.

特别的, 高斯函数 $f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{x^2}{2\sigma^2}}$. 经过傅里叶变换后仍为高斯函数, 且函数式为 $F(w)=e^{-\frac{\sigma^2 w^2}{2}}$.

二维

连续:

空间域 $\to$ 频域: $F(u,v)=\displaystyle\iint_{-\infty}^\infty f(x,y)e^{-\text{i} (ux+vy)}\text{d}x\text{d} y$.

频域 $\to$ 空间域: $f(x,y)=\displaystyle\iint_{-\infty}^\infty F(u,v)e^{\text{i} (ux+vy)}\text{d}x\text{d} y$.

离散:

傅里叶基函数: $B_{k,l}(x,y)=e^{\text{i}(\frac{2\pi k x}{N}+\frac{2\pi l y}{N})}=\cos(\frac{2\pi k x}{N}+\frac{2\pi l y}{N})+\text{i} \sin(\frac{2\pi kx}{N}+\frac{2\pi l y}{N})$.

空间域 $\to$ 频域: $F(u,v)=\sum\limits_{x=0}^{M-1}\sum\limits_{y=0}^{N-1}f(x,y)e^{-\ti2\pi\left(\frac{ux}{M}+\frac{vy}{N}\right)}$.

频域 $\to$ 空间域: $f(x,y)=\frac{1}{MN}\sum\limits_{u=0}^{M-1}\sum\limits_{v=0}^{N-1}F(u,v)e^{\text{i} 2\pi\left(\frac{ux}{M}+\frac{vy}{N}\right)}$.

称模长 $|F(u,v)|$ 为幅度谱 (AM), 相角 $\arg F(u,v)$ 为相位谱 (Phase).

dual domains

空间域的卷积等于频域的点乘.

$$\begin{aligned} h=f*g\\ H=FG \end{aligned}$$

对称的, 空间域的点乘等于频域的卷积 $$\begin{aligned} H=F*G\\ h=f\cdot g \end{aligned}$$

证明: $$\begin{aligned} H(w)=\int_{-\infty}^\infty h(t)e^{-\text{i} wt}\text{d} t\\ =\int_{-\infty}^\infty f*g(t)e^{-\text{i} wt}\text{d} t\\ =\int_{-\infty}^\infty \int_{-\infty}^\infty f(\tau)g(t-\tau)\text{d} \tau e^{-\text{i} wt}\text{d} t\\ =\int_{-\infty}^\infty f(\tau)\int_{-\infty}^\infty g(t-\tau)e^{-\text{i} w (t-\tau)}\text{d} t e^{-\text{i} w\tau}\text{d} \tau\\ =\int_{-\infty}^\infty f(\tau)G(w)e^{-\text{i} w\tau}\text{d} \tau\\ =G(w)\cdot F(w) \end{aligned}$$

图像变换

将像素点看作三维 $(x,y,1)^T$. 因为平移等变换二维矩阵无法表示.

\begin{tabular}{|l|c|c|c|c|}

        **变换** & **变换矩阵 $T$** & **逆变换 $T^{-1}$** & **自由度数** & **保持**  \\

        平移变换 &
        $\begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix}$ &
        $\begin{bmatrix} 1 & 0 & -t_x \\ 0 & 1 & -t_y \\ 0 & 0 & 1 \end{bmatrix}$ &
        2 & 方向  \\

        尺度变换 &
        $\begin{bmatrix} c_x & 0 & 0 \\ 0 & c_y & 0 \\ 0 & 0 & 1 \end{bmatrix}$ &
        $\begin{bmatrix} 1/c_x & 0 & 0 \\ 0 & 1/c_y & 0 \\ 0 & 0 & 1 \end{bmatrix}$ &
        2 & 平行性  \\

        旋转变换 &
        $\begin{bmatrix} \cos\theta & -\sin\theta & 0 \\ \sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}$ &
        $\begin{bmatrix} \cos\theta & \sin\theta & 0 \\ -\sin\theta & \cos\theta & 0 \\ 0 & 0 & 1 \end{bmatrix}$ &
        1 & 长度  \\

        欧氏变换 &
        $\begin{bmatrix} \cos\theta & -\sin\theta & t_x \\ \sin\theta & \cos\theta & t_y \\ 0 & 0 & 1 \end{bmatrix}$ &
        --- & % 逆变换未填写, 留空或可计算
        3 & 长度  \\

        相似变换 &
        $\begin{bmatrix} s\cdot\cos\theta & -s\cdot\sin\theta & t_x \\ s\cdot\sin\theta & s\cdot\cos\theta & t_y \\ 0 & 0 & 1 \end{bmatrix}$ &
        --- & % 逆变换未填写, 留空或可计算
        4 & 夹角  \\

        仿射变换 &
        $\begin{bmatrix} a & b & c \\ d & e & f \\ 0 & 0 & 1 \end{bmatrix}$ &
        --- & % 逆变换未填写, 留空或可计算
        6 & 平行性  \\

    \end{tabular}

前向变换与逆向变换

设变换 $T$, 原图像 $f(x,y)$, 变换后图像 $g(x,y)$.

前向变换: 从原图像坐标出发计算变换后的坐标, 即 $g(T(x,y))=f(x,y)$.

缺点: $T(x,y)$ 不一定是整数, 且 $g$ 中每个点不一定有对应的坐标从而产生空洞.

逆向变换: 从新图像坐标根据逆变换求原图像对应坐标, 即 $g(x,y)=f(T^{-1}(x,y))$.

存在问题, 逆变换的结果也不一定是整数值, 解决方案通过 $f$ 邻域内整点的值进行插值.

有如下插值方式: - (1) 近邻插值: 即寻找逆变换坐标最近的原图像整点. - (2) : 双线性插值: 根据逆变换坐标到临近的四个整点的面积算比例加权平均得到该点的值.

下采样与上采样

下采样: 每隔 $P$ 像素取一个点, 采样后图像大小为 $N/P$.

缺点: 容易出现 Aliasing 混叠现象.

上采样: 在像素之间填 0, 一般填一个, 这样使图像大小翻倍. 但填 0 会出现很多空洞, 考虑做高斯滤波来填充空白, 但滤波后会使得整个图像偏暗, 因为填了很多 0 (黑像素点). 所以整体乘一个倍率以提高亮度, 一般乘 4.

高斯金字塔与拉普拉斯金字塔

高斯金字塔: 高斯滤波后做下采样, 每轮操作后得到的一些列图像称为高斯金字塔.

利用高斯滤波避免下采样混叠 Aliasing.

记图像为 $g_k$, 高斯滤波和下采样操作为 $G_k$.

拉普拉斯金字塔: 将高斯金字塔下一层结果做上采样并和当前层结果做差.

记图像为 $l_k$, 上采样为 $F_k$.

$l_k=g_k-F_kg_{k+1}=(I-F_kG_k g_k)$.

边缘检测

认为梯度变化大的就是边缘, 但求梯度会放大高频信息, 因为 $(\sin \omega x)'=\omega\cos\omega x$. 所以在求梯度前先做滤波减少噪音, 使梯度平滑.

根据行纵两个维度梯度大小确定总梯度方向.

由于求导和卷积可以换序, 即 $\frac{\text{d}}{\text{d} x} (f*h)=f*\frac{\text{d} h}{\text{d} x}$ 故如果使用高斯滤波可以将滤波核与求导结合乘一个滤波核.

Sobel Filter 在离散图像中采用相邻点差值来近似梯度. 固定检测水平方向或垂直方向的边缘. $$G_x= \begin{bmatrix} -1 & 0 & 1 \ -2 & 0 & 2 \ -1 & 0 & 1 \end{bmatrix} ,\quad G_y= \begin{bmatrix} -1 & -2 & -1 \ 0 & 0 & 0 \ 1 & 2 & 1 \end{bmatrix} $$

NMS 非极大值抑制

认为真实边缘是单像素宽, 但仅根据梯度大小可能会出现粗的边缘.

根据每个点梯度方向确定该点和哪个点比较, 如果幅值比另一个点小则认为该点不是边界, 直接设置成 0.

Hysteresis 阈值

双阈值连接.

先设置高的阈值, 认为高于这个阈值的梯度很可能是边界点不是噪声, 称为强边界. 再设置低阈值, 低于该阈值的认为肯定是噪声, 高于这个阈值并和强边界连通的点也认为是边界.

避免单阈值问题: 阈值高会边缘断裂, 阈值低会出现大量噪声.

Canny 边缘检测

(1) 对图像高斯滤波降噪;
(2) 求梯度 (幅值+方向) Sobel ;
(3) NMS 细化边界;
(4) Hysteresis 双阈值连接;

如何评价边缘检测器

(1) Good detection 最小化 false positives (将噪声识别为边界) 和 false negatives (错失真实边界);
(2) Good localization 检测出的边缘位置接近真实边缘;
(3) Single Response 每条真实边缘只检测出一条结果.

角点检测

角点定义: 窗口在任意方向平移, 都发生明显变化.

用 SSD (平方误差和) 刻画 $$ E(u,v)=\sum\limits_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^2 $$ $(u,v)$ 窗口平移量, $w(x,y)$ 窗口函数.

当 $u,v$ 很小时, 用梯度一阶近似 $I(x+u,y+v)\approx I(x,y)+I_x u+ I_y v$.

展开平方项后可以表示为 $$E(u,v)= \sum w(x,y) \begin{bmatrix}u&v\end{bmatrix} \begin{bmatrix} I_x^2 & I_xI_y\\ I_xI_y & I_y^2 \end{bmatrix} \begin{bmatrix}u\\ v\end{bmatrix}$$

那么设 $M=\sum w(x,y)\begin{bmatrix} I_x^2 & I_xI_y\\ I_xI_y & I_y^2 \end{bmatrix}$ 就有 $E(u,v)=[u v]M\begin{bmatrix} u\\v \end{bmatrix}$

考虑 $M$ 的特征值, $\lambda_{max}$ 对应特征向量 $x_{max}$, 表示 $E$ 变化最大的方向. $\lambda_{min}$ 及其特征向量表示变化最小的方向.

因为 $E(x)=x^TMx=\lambda \Vert x \Vert^2=\lambda$.

所以当特征值 $\lambda_{max}\approx\lambda_{min}\approx 0$ 时意味着任意方向移动都不变认为是平坦区域.

当 $\lambda_{max}\gg \lambda_{min}\approx 0$ 意味着某个方向上变化很小, 认为是边界.

当 $\lambda_{max}\approx \lambda_{min}\gg 0$ 则是角点.

Harris 角点检测

(1) 高斯滤波;
(2) 求梯度;
(3) 计算 $I_x^2, I_xI_y, I_y^2$;
(4) 高斯加权求 M 矩阵;
(5) 计算 $R=\det (M)-\alpha \text{trace}^2(M)$ $\alpha\in[0.04,0.06]$.
(6) 阈值筛选;
(7) 非极大值抑制;

不变性分析

\begin{tabular}{|c|c|}

        **变换** & **结果** \\

        平移 & $\checkmark$~角点响应不变，位置等变 \\

        旋转 & $\checkmark$~响应不变（特征值不变） \\

        亮度平移 & $\checkmark$~不变 \\

        亮度缩放 & $\times$~不完全不变 \\

        尺度 & $\times$~不尺度不变 \\

    \end{tabular}

分析: 对于平移变换, 由于卷积是平移不变的, 所以 M 矩阵只会平移, 值不改变.

对于旋转变换, 相当于是给每个点乘了一个可逆矩阵, 根据矩阵的性质, 对于 M 矩阵来说是一个相似变换, 从而特征值不变.

而对于尺度变换, 设 $I'(x)=I(x/s)$, 那么 $M'=\frac1{s^2}M$. 从而 Harris 角点检测不是尺度不变的. 直观理解, 可以尺度将某一维度的边长度缩成 $0$, 从而变成边缘.

特征描述与匹配

特征描述子

定义 14

Feature descriptor 是对局部图像区域的数值化表示, 用于在不同图像中进行匹配与识别.

希望描述子具有不变性和判别性, 即在图像经过变换后仍可以用同一个描述子匹配特征. 不同特征的描述子应该有所区分.

SIFT

128 维向量描述.

构建过程:

匹配过程: 在所有描述子中找到 $L_2$ 距离下最近的两个特征, 计算 $R=\frac{\Vert f-g_1 \Vert}{\Vert f-g_2 \Vert}$, 当 $R$ 较小的时候认为匹配效果好, $R$ 接近 1 意味着两个特征相似.

不变性: 平移不变性, 尺度不变性, 旋转不变性, 光照不变性.

图像对齐

对于所有关键点的匹配对 $(p,p')$, 寻找变换 $T^*=\text{arg}\min\limits_{T}\sum\limits_{p\in\Omega}\Vert p'-T(p) \Vert^2$.

由于在二维图像变换中, 一组 $(p,p')$ 可以提供两个等式关系, 所以对于变换 $T$ 只需要自由度一半的点数量理论上就能确定该变换.

最小二乘法: 普通最小二乘法行不通, 因为 SIFT 匹配结果正确比例不高错误匹配会严重影响最小二乘的结果.

RANSAC

(1) 随机选取理论最小需求数量的匹配点 (自由度除以 2).
(2) 用最小点集精确求解模型 $T$.
(3) 计算各匹配点在该模型下的误差, 设定阈值划分内点/外点.
(4) 选取内点最多的模型.
(5) 基于该内点集合用最小二乘法重新计算 H.

设 $w$ 是正确内点比例, 最小点集需要选取 $n$ 个点, 那么在一次随机中正确的概率为 $w^n$, 那么反复选取 $k$ 次仍找不到正确解的概率是 $(1-w^n)^k$. 从而为了满足正确率 $p$ 只要 $k\geqslant \frac{\log(1-p)}{\log(1-w^n)}$

成像几何

线段比例

如何寻找 $T_1$ 在 $b_2t_2$ 上的对应点: 由于 $T_1\widetilde{T_1}\mathop{//} B_1B_2$ 所以在 2D 中的交点也在消失线上, 故取 $b_1b_2$ 与消失线 $l$ 的交点, 再连接 $t_1$ 得到对应点.

设 $b_2\widetilde{t_1}=a, b_2t_2=b, b_2v=c$.

利用射影几何保持交比不变 $CR(B_2,\widetilde{T_1},T_2,\infty)=CR(b_2,\widetilde{t_1},t_2,v)$ 从而 $$ \frac{l_2}{l_2-l_1}:1=\frac{b}{b-a}:\frac{c}{c-a} $$ 解得 $\dfrac{l_1}{l_2}=\dfrac{a(c-b)}{b(c-a)}$.

4 个坐标系变换

(1) 世界坐标系: 描述真实 3D 世界, 记为 $\bm X_w=(X_w,Y_w,Z_w,1)$.
(2) 相机坐标系: 原点为相机的针孔, $Z_c$ 为光轴, 记为 $\bm X_c=(X_c,Y_c,Z_c)$.
(3) 透视投影, 归一化平面: $x_n=\frac{X_c}{Z_c}, y_n=\frac{Y_c}{Z_c}$, $\bm x_n=(x_n,y_n,1)$.
(4) 像素坐标系: $\bm x_{img}=(u,v,1)=K \bm x_n$.

外参: 与相机在世界中的位姿有关, 受世界和移动影响 $\begin{bmatrix} R & t \\ 0 & 1 \end{bmatrix}$ 从 3D 坐标系变为相机坐标系. 当相机原点及方向与世界坐标一致时 $R=I$.

相机坐标系到投影做归一化.

内参: 只和相机硬件参数有关 $K=\begin{bmatrix} s_x & \alpha & t_u\\ 0 & s_y & t_v\\ 0 & 0 & 1 \end{bmatrix}$ 投影坐标变为像素坐标. - $s_x$ 焦距, 像素单位, 把米转为像素 $s_x=f/\Delta x$. $\Delta x$ 表示一个像素在真实世界的物理长度. - $s_y$ 焦距, $s_y=f/\Delta y$. - $\alpha$ 斜切, 描述像素坐标轴是否正交. - $t_u,t_v$ 主点坐标.

立体视觉

理想双目相机

两个相机光轴平行, 只沿 x 轴平移, 成像平面共面, 内参已知, 无旋转 $R=I$.

性质: 对应点满足 $y_L=y_R$, 即只在 x 方向位移, 故匹配变为 1D 搜索.

视差与深度

$x_1=[I|0]X_w, x_2=[I|t]X_w$, $t=\begin{bmatrix} t_x\\ 0\\ 0 \end{bmatrix}$

从而推出 $Z=\frac{t_x}{x_2-x_1}$.

NCC

NCC: 先减均值再归一化, 最后做内积获得余弦相似度. 对亮度平移及缩放具有不变性.

假设图像大小 $M\times N$, 视差范围 $D$.

对每个像素遍历可能的视差 $d=0,1,\ldots, D-1$.

左图以 $(x,y)$ 为中心的窗口, 右图以 $(x+d,y)$ 为中心的窗口.

计算 $C(x,y,d)=NCC(W_L(x,y),W_R(x+d,y))$.

选 $d^*=\text{arg}\max\limits_{d}C(x,y,d)$.

注意不同点的最优视差不同, 因为有深度差异.

对极几何

对图 1 中任意点 $x$, 其在图二中对应的极线为 $l'=Fx$, 而所有极线交于一点称为极点. 记作 $e'$.

有关系式 $[t]_\times = \begin{bmatrix} 0 & -t_z & t_y\\ t_z & 0 & -t_x\\ -t_y & t_x & 0 \end{bmatrix}$ $[t]_\times a=t\times a$.

$0=x_{img}^{(2)^T} E x_{img}^{(1)}$, $E=[t]_\times R$.

$0=x_{img}^{(2)^T} F x_{img}^{(1)}$, $F=K_2^{-T}[t]_{\times}RK_1^{-1}$.

$F^T e'=0$.

区别: $E$ 作用对象是归一化之后的坐标, $F$ 作用对象是像素坐标. 所以二者的转化之间差了内参矩阵.

图像分类

k近邻

取最近的 k 个点投票, 以最多的类别当作类别.

贝叶斯分类

神经网络

激活函数

\small

    \begin{tabular}{|c|c|c|c|c|}

        **激活函数** & **函数表达式** & **导数** & **值域** & **特点与使用** \\

        Sigmoid &
        $\displaystyle \sigma(x)=\frac{1}{1+e^{-x}}$ &
        $\displaystyle \sigma'(x)=\sigma(x)(1-\sigma(x))$ &
        $(0,1)$ &
        非线性平滑；\\
        & & & &
         易梯度消失；\\
        & & & &
         输出非零均值；\\
        & & & &
         多用于输出层（二分类） \
$$
10pt]

        Tanh &
        $\displaystyle \tanh(x)=\frac{e^x-e^{-x}}{e^x+e^{-x}}$ &
        $\displaystyle 1-\tanh^2(x)$ &
        $(-1,1)$ &
        零均值；\\
        & & & &
         仍存在梯度消失；\\
        & & & &
         早期常用于隐藏层 \\

        ReLU &
        $\displaystyle f(x)=\max(0,x)$ &
        $\displaystyle
        f'(x)=
        \begin{cases}
            1, & x>0 \\
            0, & x\le 0
        \end{cases}$ &
        $[0,+\infty)$ &
        计算简单；\\
        & & & &
         缓解梯度消失；\\
        & & & &
         可能产生“死ReLU”；\\
        & & & &
         **默认首选** \
$$
10pt]

        Leaky ReLU &
        $\displaystyle f(x)=\max(\alpha x,x)$ &
        $\displaystyle
        f'(x)=
        \begin{cases}
            1, & x>0 \\
            \alpha, & x\le 0
        \end{cases}$ &
        $(-\infty,+\infty)$ &
        缓解死ReLU；\\
        & & & &
         $\alpha\!\approx\!0.01$；\\
        & & & &
         实践中有效 \
$$
10pt]

        ELU &
        $
        f(x)=
        \begin{cases}
            x, & x>0 \\
            \alpha(e^x-1), & x\le 0
        \end{cases}$ &
        $
        f'(x)=
        \begin{cases}
            1, & x>0 \\
            f(x)+\alpha, & x\le 0
        \end{cases}$ &
        $(-\alpha,+\infty)$ &
        输出接近零均值；\\
        & & & &
         收敛快；\\
        & & & &
         计算略复杂 \\

        Softmax &
        $\displaystyle
        f_i(x)=\frac{e^{x_i}}{\sum_j e^{x_j}}$ &
        $\displaystyle
        \frac{\partial f_i}{\partial x_j}
        =
        f_i(\delta_{ij}-f_j)$ &
        $(0,1)$ &
        多分类输出层；\\
        & & & &
         概率解释；\\
        & & & &
         常与交叉熵联合使用 \\

    \end{tabular}

简单反向传播### 梯度消失/梯度爆炸

梯度消失: 连乘 <1 的梯度, 导致梯度传递多层后趋于 0, 比如激活函数 $sigmoid/tanh$. 后果就是前面的层学不到东西. 可以换用 ReLu 等激活函数.

梯度爆炸: 连乘 >1 的梯度, 导致梯度趋于无穷, 权重大的激活函数, 后果是训练不稳定, 可以手动剪裁过大梯度.

优化器

Adam

同时维护 Momentum 和 RMSProp 的信息, 即同时维护一阶矩和二阶矩.

$$ g_t=\nabla_W L(W_t) $$

分为四步:

一阶动量 $m_t=\beta_1 m_{t-1}+(1-\beta_1)g_t$.

二阶动量 $v_t=\beta_2 v_{t-1}+(1-\beta_2)g_t^2$. 控制不同参数学习率大小.

偏差修正: 由于初始化时 $m_0=0, v_0=0$ 早期会偏向 0, 所以要修正: $$ \hat m_t=\frac{m_t}{1-\beta_1^t}, \hat v_t=\frac{v_t}{1-\beta_2^t} $$

最终 $$ W_{t+1}=W_t-lr*\frac{\hat{m}_t}{\sqrt{\hat{v}_t}+\varepsilon}. $$

CNN

ImageNet

GoogleNet

注重效率提升. - Inception: 把一个局部单元设计成多分支并行 (不同大小的卷积核, 池化) 最后再 Concat 起来. 效率提升关键: 在对多通道数据卷积前使用 1*1 的卷积核 (bottleneck) 进行通道数的降维, 以此减少计算量. - GAP (global average pooling): 用 GAP 代替 VGG 最后参数巨大的 FC 层. 过程: 直接对最终 $C\times H\times W$ 的数据按通道求平均值, 即操作后变为 $C\times 1\times 1$, 再接线性层到分类结果. - Auxiliary Classifiers: 辅助分类器, 即在网络中间部分也加入分类器计算 loss 并回传, 以此避免网络层数过多时梯度传不到前层的状况.

ResNet

残差网络.

层数加深问题: 理论上增加层数不会使得效果变差, 但实际中优化器很难学到这样的恒等映射.

残差学习就是直接考虑学习残差, 即传统网络学习 $H(x)$, Resnet 提出 $F(x)=H(x)-x$, 于是输出就变为 $y=F(x)+x$. 那么只需学习 $F(x)=0$ 就等于学到了恒等映射 $H(x)=x$.

而权重趋于 0 相对来说更好学习.

在实际实现中就是在卷积, 激活函数等神经网络层操作后将原始输入与输出结果叠加作为最终输出, 由此哪怕 $\frac{\partial F}{\partial x}$ 学成 0 了也能正常的梯度传播. 称输入结果叠加为 shortcut.

由此残差网络就改善了学习过程中的优化问题.

图像分割

分割策略

Bottom-up: 自底向上, 依据亮度, 颜色, 纹理, 位置等信息, 像素"看起来像"就分为一组. 特点: 无监督, 不理解"语义".
Top-Down: 自顶向下. 依据语义, 先验模型等信息, 像素来源于同一个物体. 特点: 有监督, 偏深度学习.

K-means

目标函数: $$ \min\sum\limits_{i=1}^K\sum\limits{x\in C_i}\Vert x-c_i \Vert^2 $$ 其中 $C_i$ 表示被归为 $i$ 类的向量, $c_i$ 是第 $i$ 类的聚类中心.

算法流程: - (1) 随机化 $K$ 个聚类中心. - (2) Assignment step, 根据每个点到聚类中心的距离, 取最近的中心作为类别. - (3) Update step, 重新根据每个类别的点计算均值得到新的中心. - (4) 如果中心变化则重复 2,3 步.

优点: 算法简单, 容易实现; 计算效率高, 适合大规模数据; 收敛速度快.

缺点: 需人为指定聚类数 $K$; 对初始化敏感 (容易陷入局部最优); 假设族在空间中是球形/凸的; 对噪声和离群点敏感.

Mean-Shift

思想: 不断向密度最大方向移动, 找到聚类中心.

算法流程: - (1) 选择核函数与带宽, 常用高斯核, 带宽参数 $h$. - (2) 计算 Mean-shift 向量, 对当前点 $x$ $$ m(x)=\frac{\sum_i K(\frac{x_i-x}{h})x_i}{\sum_i K(\frac {x_i-x}{h})}-x $$ 即加权均值减去当前值. - (3) 更新位置 $x\leftarrow x+m(x)$. - (4) 重复 2,3 直到 $m(x)$ 接近零, 此时就停留在密度峰值. - (5) 收敛到同一峰值的点就认为是同一族.

优点: 不需要指定聚类数; 能发现任意形状的族; 对噪声相对鲁棒; 分割结果边界自然, 连续.

缺点: 计算复杂度高; 对带宽参数 $h$ 非常敏感; 不适合高维特征空间.

语义分割

可学习的上采样: 转置卷积

假设卷积步长 2.

全卷积

整个神经网络只有卷积层, 最后用 1*1 的卷积核将通道数变为分类数 C, 每个通道的值即为该类别分数. 用逐元素交叉熵作为损失函数.

目标检测

Viola-Jones

使用大量 Haar 特征保证判别能力, 弱分类器.
利用积分图实现 O(1) 计算任意矩阵的和以实现特征的快速计算.
采用 AdaBoost 自动选择有效特征并构建强分类器.
快速分类产生级联分类器. 能够将 99\% 的非人脸窗口筛去, 避免每个窗口都使用复杂的分类器.

RCNN

R-CNN

引入 CNN 提高检测精度, 但计算量巨大, 训练复杂. 分为 2000 个候选框独立训练 CNN.

fast RCNN

解决 RCNN 重复计算问题, 只用进行一次 CNN 得到共享的图像特征, 并在共享特征上裁剪, 但候选框仍依赖 Selective Search, 速度受限.

faster RCNN

用 RPN 代替 Selective Search, 利用 CNN 来计算候选区域.

期末复习

期末复习

Image Filtering 1

集合, 映射/函数, 算子

卷积和相关

锐化 (sharpening)

滤波

傅里叶变换

一维

二维

dual domains

图像变换

前向变换与逆向变换

下采样与上采样

高斯金字塔与拉普拉斯金字塔

边缘检测

NMS 非极大值抑制

Hysteresis 阈值

Canny 边缘检测

如何评价边缘检测器

角点检测

Harris 角点检测

不变性分析

特征描述与匹配

特征描述子

SIFT

图像对齐

RANSAC

成像几何

线段比例

4 个坐标系变换

立体视觉

理想双目相机

视差与深度

NCC

对极几何

图像分类

最近邻

k近邻

贝叶斯分类

神经网络

激活函数

简单反向传播### 梯度消失/梯度爆炸

优化器

Adam

CNN

ImageNet

GoogleNet

ResNet

图像分割

分割策略

K-means

Mean-Shift

语义分割

可学习的上采样: 转置卷积

全卷积

目标检测

Viola-Jones

RCNN

R-CNN

fast RCNN

faster RCNN

transformer