计算机视觉与模式识别

发表于 2022-06-17 更新于 2022-07-02 Waline：阅读次数：

前言（考试前）

开始复习 CVPR 的时候 CVPR 大佬，你交校友孙剑博士去世了，RIP。以后无论水平高低出身贵贱，都得先养好身体。

这门课的老师是苏远歧老师，由于之前在 UPenn 带同一门课所以基本可以算高端课程的减负版（但是相比之下还是作业很多笑死），想要上课学本事的非常建议选！

前言（考试后）

快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑快跑vvvvvv

前言（出分了）

竟然意外地不错。

看来老师 Norm 了（笑）。

符号版式说明

考虑到排版规范和编写便利性、可读性，后文的符号版式说明如下

矩阵是斜体大写字母 $A,B,C,R,H_{3\times 3},P,I_3,\cdots$
集合也是斜体大写字母，但是用的不多，上下文判断吧
向量是粗体小写字母 $\boldsymbol {x},\boldsymbol {v},\boldsymbol {d},\cdots$
标量是斜体小写字母 $a,b,c,x,y,z,u,v,w,\cdots$
向量展开可以写成如 $(x,y,z,1)^T$ 的元组形式，也可以写成矩阵形式 $\begin{bmatrix}x &y & z\end{bmatrix}^T$
矩阵乘法写成 $AB$、$A\boldsymbol x$、$\boldsymbol{y}^T\boldsymbol{x}$ 等，向量点乘写作 $\boldsymbol{y}\cdot \boldsymbol{x}$
$A^{-T}=(A^{-1})^T$，即逆的转置

数学知识

三维向量的叉积 $\boldsymbol v=\boldsymbol {v_1}\times \boldsymbol {v_2}$ 垂直（点乘为零）于两个向量，长度为正弦，方向符合右手法则；设 $\boldsymbol{\hat\imath},\boldsymbol{\hat\jmath},\boldsymbol{\hat k}$ 为正交基、计算如下： \[ \begin{aligned} \boldsymbol v=\boldsymbol {v_1}\times \boldsymbol {v_2} & = (x,y,z)^T\times(u,v,w)^T \\ & = \begin{vmatrix} \boldsymbol{\hat\imath} & \boldsymbol{\hat\jmath} &\boldsymbol{\hat k} \\ x & y & z \\ u & v & w \end{vmatrix} \\ & = [v_\times]\boldsymbol{v_2}\\ & = \begin{bmatrix} 0 & -z & y \\ z & 0 & -x \\ -y & x & 0 \end{bmatrix} \boldsymbol {v_2} \end{aligned} \] 其中 $[v_\times]$ 为 $\boldsymbol {v_1}$ 的叉积矩阵，是反对称矩阵，它把叉积运算转换为矩阵乘法运算方便推导

QR 分解即 $A=QR$，将矩阵 $A$ 分解为上三角矩阵 $R$ 和正交矩阵 $Q$（$Q^T=Q^{-1}$）

矩阵导数参照表（$\boldsymbol x$ 为列向量，且其导数与其同形状）：

$L$	$\dfrac{\partial L}{\partial \boldsymbol x}$
$\boldsymbol x^T A \boldsymbol x$	$\boldsymbol x^T(A+A^T)$
$\boldsymbol a^T\boldsymbol x$	$\boldsymbol a$
$\boldsymbol x^T \boldsymbol a$	$\boldsymbol a^T$

SVD 分解（奇异值分解）即 $A=USV^T$，设 $A_{m\times n}$ 的秩为 $r$，有 $U_{m\times m}$ 为正交矩阵，$S_{m\times n}$ 为有 $r$ 个非零值（奇异值 $\sigma_i$）的对角矩阵，$V_{n\times n}$ 为正交矩阵

最小二乘问题 $\|A\boldsymbol x\|^2$

伪逆解法：$\boldsymbol x=(A^TA)^{-1}A^T\boldsymbol b$
SVD 解法：设 $A$ 的 SVD 分解 $A=USV^T$，则 $V$ 的最后一列“最可能”是一个零解

基础知识

由于考试不考默写，所以懂就行了，比如图像是正则化网格点上的离散函数 $I(x,y)$ 啦，分辨率、位深、图像种类啦，认识就行。

相机模型和应用

小孔成像模型和摄像机内参

光心（摄像机中心）是小孔，作为原点；投影平面（成像平面）在原点的 $Z$ 轴正方向（主方向）处，垂直于 $Z$ 轴（主轴）；主平面过光心平行于投影平面，主点是是主轴和投影平面的交点

摄像机坐标到像平面坐标 $(x,y,z)\to(u_{CCD},v_{CCD})=(x\cdot f_m/z, y\cdot f_m/z)$
像平面坐标到像素坐标 $(u_{CCD},v_{CCD})\to(u_{img}, v_{img})=(x\cdot f_x/z+p_x, y\cdot f_y/z+p_y)$

对于像素坐标中像素计量的焦距 $f_x$，有 $f_x=f_m\cdot w_{img}/w_{CCD}$；$f_y$ 同理

齐次坐标 $\lambda(x,y,1),\lambda>0$：投影方向的射线，透视空间中的点

摄像机坐标（测度空间）到像素齐次坐标（透视空间）的透视投影变换 \[ \lambda \begin{bmatrix} u_{img} \\ v_{img} \\ 1 \end{bmatrix} = \begin{bmatrix} f_x & & p_x \\ & f_y & p_y \\ & & 1 \end{bmatrix} \begin{bmatrix}x \\ y \\ z\end{bmatrix} \triangleq K\boldsymbol x \] 其中 $K$ 为内参矩阵

径向畸变模型：假设归一化的像平面坐标 $\boldsymbol{\bar u_{undistorted}}=K^{-1} u$（即测度空间坐标）到主点到距离 $\rho=\|\boldsymbol {\bar u_{undistorted}}\|$，那么畸变后的对应坐标满足 \[ \begin{cases} \boldsymbol{\bar u_{distorted}} = L(\rho) \boldsymbol{\bar u_{undistorted}} \\ L(\rho) = 1 + k_1 \rho^2 + k_2 \rho^4 + \cdots \end{cases} \]

世界坐标和摄像机外参

世界坐标 $\boldsymbol {x_W}=(x,y,z)^T$ 到摄像机坐标 $\boldsymbol{x_C}=(u,v,w)^T$ 的旋转矩阵 ${^CR_W}$ 定义如下 \[ \boldsymbol{x_C}=\begin{bmatrix} {r_x}_1 & {r_x}_2 & {r_x}_3 \\ {r_y}_1 & {r_y}_2 & {r_y}_3 \\ {r_z}_1 & {r_z}_2 & {r_z}_3 \\ \end{bmatrix} \boldsymbol {x_W} =\begin{bmatrix} \boldsymbol{r_x} \\ \boldsymbol{r_y} \\ \boldsymbol{r_z} \\ \end{bmatrix} \boldsymbol {x_W} \triangleq {^CR_W}\boldsymbol {x_W} \] 旋转矩阵只有三个自由度 ${^CR_W}\in SO(3)$；旋转矩阵是正交矩阵，${^CR_W}^T{^CR_W}=I_3$；旋转矩阵的每一行是世界坐标看摄像机坐标的坐标轴方向，每一列是摄像机坐标看世界坐标的坐标轴方向

摄像机在世界坐标内的平移 $\boldsymbol{^Ct}$：摄像机坐标看世界坐标原点到摄像坐标原点的位移 \[ \boldsymbol{x_C}= {^CR_W}\boldsymbol {x_W}+\boldsymbol{^Ct}= \begin{bmatrix} {r_x}_1 & {r_x}_2 & {r_x}_3 & t_x \\ {r_y}_1 & {r_y}_2 & {r_y}_3 & t_y \\ {r_z}_1 & {r_z}_2 & {r_z}_3 & t_z \\ \end{bmatrix} \begin{bmatrix} \boldsymbol {x_W} \\ 1 \end{bmatrix} = \begin{bmatrix} {^CR_W} & \boldsymbol{^Ct} \end{bmatrix} \begin{bmatrix} \boldsymbol {x_W} \\ 1 \end{bmatrix} \] 透视投影矩阵 $P=K\begin{bmatrix}{^CR_W} & \boldsymbol{^Ct}\end{bmatrix}$

摄像机标定

摄像机标定的任务是通过图像，获得摄像机的内参和对应各图像的外参

齐次几何

二维空间中，齐次坐标点表示为 $\boldsymbol p = (u,v,1)^T$

二维空间中的直线齐次坐标表示 $\boldsymbol l^T\boldsymbol p=0$，其中 $\boldsymbol l = (a,b,c)^T$，$\boldsymbol l \in SO(2)$ 是齐次的
过两点 $\boldsymbol {p_1}$，$\boldsymbol {p_2}$ 的直线有 $\boldsymbol l=\boldsymbol {p_1}\times \boldsymbol {p_2}$（因为 $\boldsymbol {p_1}\times \boldsymbol {p_2}\perp \boldsymbol {p_1}\wedge \boldsymbol {p_1}\times \boldsymbol {p_2}\perp \boldsymbol {p_2}$）
两直线 $\boldsymbol {l_1}$，$\boldsymbol {l_2}$ 的交点是 $\boldsymbol l=\boldsymbol {l_1}\times \boldsymbol {l_2}$

三维空间中，齐次坐标点表示为 $\boldsymbol p = \lambda(x,y,z,1)^T=(x',y',z',w)^T$

三维空间的线 $\boldsymbol p=\boldsymbol {p_1}+k(\boldsymbol {p_2}-\boldsymbol {p_1})$
三维空间的平面 $\boldsymbol\pi \cdot \boldsymbol p=0$，其中 $\boldsymbol\pi=(a,b,c,d)^T$，法向量为 $(a,b,c)^T$
三维齐次坐标无穷远点表示为 $x'\neq0 \vee y'\neq 0 \vee z'\neq 0$ 且 $w=0$，相当于平行线交点

消失点解旋转矩阵

对世界坐标系中三个特殊无穷远点（三个轴方向的无穷远点），可以列三个方程解出旋转矩阵

设透视投影矩阵 \[ P=K\begin{bmatrix}{^CR_W} & \boldsymbol{^Ct}\end{bmatrix}=\begin{bmatrix} p_{11} & p_{12} & p_{13} & p_{14} \\ p_{21} & p_{22} & p_{23} & p_{24} \\ p_{31} & p_{32} & p_{33} & p_{34} \\ \end{bmatrix} \]

假设三个特殊无穷远点经透视投影后的透视空间坐标为 $\boldsymbol{p_{X\infty}}$，$\boldsymbol{p_{Y\infty}}$，$\boldsymbol{p_{Z\infty}}$ \[ \begin{aligned} \boldsymbol{p_{X\infty}}&= \lambda\begin{bmatrix}{u_x}\\{v_x}\\1\end{bmatrix} = \begin{bmatrix} p_{11} & p_{12} & p_{13} & p_{14} \\ p_{21} & p_{22} & p_{23} & p_{24} \\ p_{31} & p_{32} & p_{33} & p_{34} \\ \end{bmatrix} \begin{bmatrix} \infty\\ 0\\ 0\\ 1 \end{bmatrix} \\ &\Longrightarrow \begin{cases} u_x=\displaystyle\lim_{X\to\infty}\dfrac{p_{11}X+p_{14}}{p_{31}X+p_{34}}=\dfrac{p_{11}} {p_{31}}\\ v_x=\displaystyle\lim_{X\to\infty}\dfrac{p_{21}X+p_{24}}{p_{31}X+p_{34}}=\dfrac{p_{21}} {p_{31}}\\ \end{cases} \\ &\Longrightarrow \lambda\begin{bmatrix}{u_x}\\{v_x}\\1\end{bmatrix}=\begin{bmatrix}p_{11}\\p_{21}\\p_{31}\end{bmatrix} \end{aligned} \] 则通过三个消失点解得 $p_{11},p_{21},p_{31},p_{12},p_{22},p_{32},p_{13},p_{23},p_{33}$，再结合已知的内参矩阵解得旋转矩阵

单应矩阵

世界坐标的一个平面，可表示为平面上的点满足 \[ \boldsymbol v=v_1\boldsymbol b_1+v_2\boldsymbol b_2+\boldsymbol c=\begin{bmatrix}\boldsymbol b_1 &\boldsymbol b_2 &\boldsymbol c\end{bmatrix} \begin{bmatrix} v_1\\ v_2\\ 1 \end{bmatrix} \] 假设在世界坐标系里 $\boldsymbol {b_1}=\boldsymbol {\hat\imath}$，$\boldsymbol {b_1}=\boldsymbol {\hat\jmath}$，$\boldsymbol c=\boldsymbol 0$ 那么上述式子可以表示世界坐标的 XY 平面

将世界坐标平面投影到像素空间的单应矩阵 $H\in SO(8)$，$(u_x,u_y,1)^T=H(v_x,v_y,1)^T$ \[ H= K\begin{bmatrix}R\boldsymbol b_1 & R\boldsymbol b_2 & R\boldsymbol c+\boldsymbol{t}\end{bmatrix} = \begin{bmatrix} h_{11} & h_{12} & h_{13} \\ h_{21} & h_{22} & h_{23} \\ h_{31} & h_{32} & h_{33} \\ \end{bmatrix} \] 对于一张图像，有图像上的像素点 $u_x,u_y$，设定的平面点 $v_x,v_y$ 可列出 \[ \begin{aligned} &\begin{cases} u_x = \dfrac{h_{11}v_x+h_{12}v_y+h_{13}}{h_{31}v_x+h_{32}v_y+h_{33}}\\ u_y = \dfrac{h_{21}v_x+h_{22}v_y+h_{23}}{h_{31}v_x+h_{32}v_y+h_{33}}\\ \end{cases} \\ &\Longrightarrow \\ &\begin{bmatrix} v_x & v_y & 1 & & & -v_xu_x & -v_yu_x & -u_x\\ & & & v_x v_y & 1 & -v_xu_y & -v_yu_y & -u_y\\ \end{bmatrix} \begin{bmatrix} h_{11} \\ h_{12} \\ h_{13} \\ h_{21} \\ h_{22} \\ h_{23} \\ h_{31} \\ h_{32} \\ h_{33} \\ \end{bmatrix} =0 \end{aligned} \] 四个点即可解出 Homography（假设其中一个值为一即可），且若 $\boldsymbol v$ 位于 XY 平面（Z 分量为零），有 \[ H=K\begin{bmatrix} {r_x}_1 & {r_x}_2 & t_x \\ {r_y}_1 & {r_y}_2 & t_y \\ {r_z}_1 & {r_z}_2 & t_z \\ \end{bmatrix} \] 对 $H$ 进行 Givens 分解可得到一个上三角矩阵 $K$ 和正交旋转矩阵 $R$ 的估计

张正友标定

此节的 $h_1,h_2,h_3,r_1,r_2,t$ 都是向量，忽略了粗体

以标定版为世界坐标，已知单应矩阵 $H=\begin{bmatrix}h_1 & h_2 & h_3\end{bmatrix}$，且有 $H=K\begin{bmatrix}r_1 &r_2 & t\end{bmatrix}$，有 \[ K^{-1}\begin{bmatrix}h_1 & h_2 & h_3\end{bmatrix}=\begin{bmatrix}r_1 & r_2 & t\end{bmatrix} \Longrightarrow \begin{cases} r_1=K^{-1} h_1\\ r_2=K^{-1}h_2\\ t=K^{-1}h_3 \end{cases} \] 由于 $r_1,r_2$ 是旋转矩，有 $r_1^Tr_2=0$，$\|r_1\|=\|r_2\|$，得 \[ \begin{cases} h_1^TK^{-T}K^{-1}h_2=0\\ h_1^TK^{-T}K^{-1}h_1=h_1^TK^{-T}K^{-1}h_1 \end{cases} \] $K^{-T}K^{-1}$ 未知，记为 \[ B= \begin{bmatrix} b_1 & & b_2 \\ & b_1 & b_3 \\ b_2 & b_3 & b_4 \end{bmatrix} =K^{-T}K^{-1} = \begin{bmatrix} 1/f & & \\ & 1/f & \\ -p_x/f & -p_y/f & 1 \end{bmatrix} \begin{bmatrix} 1/f & & -p_x/f\\ & 1/f & -p_y/f \\ & & 1 \end{bmatrix} \] 将满足的条件 $h_1^TBh_2=0$ 展开并区分未知量，可以列出 \[ \begin{bmatrix} h_{11}h_{12}+h_{21}h_{22} & h_{11}h_{32}+ h_{31}h_{12} & h_{21}h_{32}+h_{31}h_{22} & h_{31}h_{32}\\ \end{bmatrix} \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{bmatrix}=0 \] 将满足的条件 $h_1^TBh_1=h_2^TBh_2$ 展开并区分未知量，可以列出 \[ \begin{bmatrix} h_{11}^2-h_{12}^2+h_{21}^2-h_{22}^2 & 2(h_{11}h_{31}-h_{12}h_{32}) & 2(h_{21}h_{31}-h_{22}h_{32}) & h_{31}^2-h_{32}^2 \end{bmatrix} \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{bmatrix}=0 \] 每幅图像可以得到上述两个方程，两幅图像即可求得 $B$，进而得到内参矩阵 $K$；获得内参后可求得 $r_1,r_2,t$，用 $\|K^{-1}h_1\|$ 除，归一化得旋转矩阵和平移向量

三角化

三角化点任务是通过两个或多个已经标定的摄像机，求三维空间中一个点的坐标

给定透视投影矩阵 $P_{Alice}$，$P_{Bob}$，给定世界坐标中一点 $\boldsymbol x$，给定该点的两个投影 $\boldsymbol u$，$\boldsymbol v$，有 $$ \[\begin{bmatrix} u_x \\ u_y \\ 1 \end{bmatrix}\] =P_{Bob} \[\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}\] = \[\begin{bmatrix} \boldsymbol p_{Bob}^{1T} \\ \boldsymbol p_{Bob}^{2T} \\ \boldsymbol p_{Bob}^{3T} \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} \Longrightarrow\] \[\begin{bmatrix} \boldsymbol p_{Bob}^{1T} - u_x \boldsymbol p_{Bob}^{3T} \\ \boldsymbol p_{Bob}^{2T} - u_y \boldsymbol p_{Bob}^{3T} \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}\]

= $$ 再用 Alice 的透视投影矩阵即可获得点的世界坐标

单视测量

单视测量的任务是通过一张图片和先验知识，获得图像中的线段对应的实际距离

交比是透视投影前后不变的性质：对一条线段上的四个顺序点 $A,B,C,D$，有 \[ \frac{\overline{AC}}{\overline{BC}}\cdot \frac{\overline{BD}}{\overline{AD}} \] 在透视投影变换后不变

单视测量的基本流程是：找参照长度，找消失点，连平行线，找另一个消失点，连线得到四个点，用无穷远和参照长度代入计算

双视几何

双视几何的任务是获得两个拍摄者的相对位置（又叫对极几何）

Bob 的光心 $\boldsymbol {c_{Bob}}$ 在 Alice 图像平面的投影 $\boldsymbol {e_{Alice}}$ 称为 Alice 的极点（Epipole）。给定世界坐标的一个点 $\boldsymbol x$，对应 Bob 图像中的一个点 $\boldsymbol u$，在 Alice 的图像中对应一条线称为极线 $\boldsymbol {l_u}$；同理有 Alice 图像中的点 $\boldsymbol v$ 和 Bob 的极线 $\boldsymbol{l_{v}}$

设世界坐标和 Bob 的相机坐标相同，Bob 的透视投影矩阵 $P_B=K\begin{bmatrix}I_{3\times3} & \boldsymbol 0\end{bmatrix}$，Alice 的透视投影矩阵 $P_A=K\begin{bmatrix}R & \boldsymbol t\end{bmatrix}$，则

Bob 的光心世界坐标 $\boldsymbol {c_{Bob}}=\boldsymbol 0$
Alice 的光心世界坐标 $\boldsymbol {c_{Alice}}=-R^T\boldsymbol t$
Alice 的极点 $\boldsymbol {e_{Alice}}=KP_A\begin{bmatrix}\boldsymbol{c_{Bob}} \\ 1\end{bmatrix}=\boldsymbol Kt$（在 Alice 相机坐标）
Bob 的极点 $\boldsymbol {e_{Bob}}=KP_B\begin{bmatrix}\boldsymbol{c_{Alice}} \\ 1\end{bmatrix}=-KR^T\boldsymbol t$（在 Bob 相机坐标）

基础矩阵 $F$ 满足 $\boldsymbol v^TF\boldsymbol u=0$；下面推导基础矩阵如何用上述未知外参表示

世界坐标上，Bob 的极点方向射线 $\lambda K^{-1}\boldsymbol {e_{Bob}}=\lambda_1R^T \boldsymbol t$
在世界坐标上，Alice 的 $\boldsymbol v$ 方向射线 $-R^T\boldsymbol t+\lambda_2R^TK^{-1}\boldsymbol v$

上述的两条射线位于同一个平面极平面，那么极平面的法线 $\boldsymbol n$ 满足 \[ \begin{aligned} \boldsymbol n &= (R^T \boldsymbol t)\times(-R^T\boldsymbol t+\lambda_2R^TK^{-1}\boldsymbol v) \\ &= \lambda_2 (R^T \boldsymbol t)\times( R^TK^{-1}\boldsymbol v) \\ &\equiv (R^T \boldsymbol t)\times (R^TK^{-1}\boldsymbol v) \\&= R^T (\boldsymbol t\times K^{-1}\boldsymbol v) \\&= R^T [t_\times] K^{-1}\boldsymbol v \end{aligned} \] Bob 的极线 $\boldsymbol{l_v}=K^{-T}\boldsymbol n=K^{-T}R^T [t_\times] K^{-1}\boldsymbol v$

由于对极几何约束，$\boldsymbol u$ 在 Bob 的极线上，那么 \[ \begin{aligned} &\boldsymbol u^T\boldsymbol {l_v}=0 \\&\Longrightarrow \boldsymbol u^TK^{-T}(R^T [t_\times] )K^{-1}\boldsymbol v = 0 \\&\Longrightarrow \boldsymbol v^TK^{-T}(-[t_\times]R)K^{-1}\boldsymbol u = 0 \\&\Longrightarrow \boldsymbol v^TK^{-T}[t_\times]RK^{-1}\boldsymbol u = 0 \\&\Longrightarrow F=K^{-T}[t_\times]RK^{-1} \end{aligned} \] 由于 $\boldsymbol v^TF\boldsymbol u=0$，则在两个图像中找出八个点对，即可列出关于 $F$ 的八个方程，求解得基础矩阵的值

基础矩阵的性质：

基础矩阵的转置对应了 Alice，Bob 互换
极线方程 $\boldsymbol {l_u}=F\boldsymbol u$，$\boldsymbol {l_v}=F^T\boldsymbol v$
极点方程 $F\boldsymbol {e_{Bob}}=0$，$F^T\boldsymbol {e_{Alice}}=0$

本质矩阵即世界坐标上两个投影点的关系矩阵，$E=[t_\times]R=K^TFK$

下面通过本质矩阵求 $R,t$。对反对称矩阵分解可得 \[ [t_{\times}]=U\begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}U^T \] 其中 $U$ 是正交矩阵，定义 $R=UWV^T$ 那么 \[ E=U\begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}U^TUWV^T = U\begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}WV^T \] 又有 $E$ 的 SVD 分解（因为 $R\in SO(3)$，$\mathrm {rank}(R)=2$，且易证线性变换尺度不变） \[ E=U\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}V^T \] 那么 $W$ 有两种可能取值 \[ W= \begin{cases} \begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \\ \begin{bmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \end{cases} \] 终于，因为可以对 $E$ 使用 SVD 分解获得 $U$ 和 $V$，那么将 $W$ 的两种值代入即可获得 $R$ 的两种可能值

设 $U=\begin{bmatrix}\boldsymbol {u_1} &\boldsymbol {u_2} &\boldsymbol {u_3}\end{bmatrix}$，有 $\boldsymbol t=\pm \boldsymbol {u_{3}}$（证明似乎很复杂）

那么，$R$ 和 $\boldsymbol t$ 均有两个取值，共四个取值都需要被验证一下，其中三个都无法使图像内包含同一个点的投影

数字图像处理

几何变换

给定输入图像 $I$ 上的点 $(x,y)$，输出图像 $O$ 的对应点 $(x',y')$，有 $I(x,y)=O(x',y')$，几何变换 $G:R^2\to R^2$ 是它们之间的映射 $G(x,y)=(x',y')$

原图像绕 $(x_0,y_0)$ 逆时针旋转 $\theta$ 角度 \[ \begin{bmatrix} x'\\y' \end{bmatrix} =\begin{bmatrix} \cos \theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \left( \begin{bmatrix} x\\y \end{bmatrix} -\begin{bmatrix} x_0\\y_0 \end{bmatrix} \right) +\begin{bmatrix} x_0\\y_0 \end{bmatrix} \] 离散点上实施变换的方法：

前向变换（不好）：遍历输入图像的点，应用映射，绘制对应输出图像的点
后向变换（好）：遍历输出图像的点，应用逆映射，得到原图像中的像素值

后向变换的插值：最近邻、双线性、双三次

双线性插值：找四个近邻点画框，分为四个方形，每个角落的权值为对面方形的面积

通过对应点对求解仿射变换 $\boldsymbol u=A_{2\times 2}\boldsymbol v+\boldsymbol b$：共六个参数，三个点对最小二乘即可

灰度变换

$O(x,y)=T(I(x,y))$，其中 $T$ 为灰度变换，和位置无关；常用查找表实现

给定连续的灰度变换函数 $t=T(s)$，针对灰度区间 $[s_1,s_2]$

如果 $|T(s_2)-T(s_1)|>|s_2-s_2|$，则该区间的灰度等级被扩展
如果 $|T(s_2)-T(s_1)|<|s_2-s_2|$，则该区间的灰度等级被压缩

幂律变换 $t=s^{\gamma}$（$s\in[0,1]$），$\gamma$ 大于一时变暗，小于一时类似对数变换；CRT 显示器自带一个 $\gamma\approx 2.2$ 的幂律变换，所以要应用一个 $\gamma=1/2.2$ 的伽马校正

灰度直方图 $p_s=\dfrac{n_s}{\sum_s n_s}$，其中 $n_s$ 是值为 $s$ 的像素出现的频次

直方图均衡：

求 CDF $c_s=\sum_{i=0}^{s} p_i$
灰度变换函数 $t=T(s)=Round((\max -\min)\times c_s+\min)$

空间滤波

模版运算：给定输入图像 $I(x,y)$ 定义在 $X\times Y$ 大小的空间，$f(x,y)$ 定义在 $(2m+1)\times (2n+1)$ 大小的空间 \[ O(x,y)=\sum_{a=-m} ^{m}\sum_{b=-n}^n I(x+a,y+b)f(a,b) \] 输出尺寸：

全尺寸 $(X+2m)\times(Y+2n)$
同等尺寸 $X\times Y$
有效尺寸 $(X-2m)\times(Y-2n)$

常用 Padding：0、拷贝、反射、循环

数学上的二维卷积即模版上下左右翻转

模版运算的性质

可加性 $f\otimes (h_1+h_2)=f\otimes h_1 + f\otimes h_2$
线性 $f\otimes (kh)=k(f\otimes h)$
可交换性 $f\otimes h = h\otimes f$，注意输出尺寸

高斯模板 $\exp\left(-\dfrac{x^2+y^2}{2\sigma^2}\right)$

Sobel 算子 $\begin{bmatrix}-1&0&1\end{bmatrix}$ 和 $\begin{bmatrix}-1&0&1\end{bmatrix}^T$

频域变换

DFT

离散傅里叶变换 DFT 的形式 \[ F(x,y)=\sum_{u=1}^X\sum_{v=1}^Y I(u,v) \exp\left(-2\pi \jmath \frac{(u-1)(x-1)}{X}\right) \exp\left(-2\pi \jmath \frac{(v-1)(y-1)}{Y}\right) \] 逆变换的形式 \[ I(u,v)= \frac{1}{XY} \sum_{x=1}^X\sum_{y=1}^Y F(x,y) \exp\left(-2\pi \jmath \frac{(u-1)(x-1)}{X}\right) \exp\left(-2\pi \jmath \frac{(v-1)(y-1)}{Y}\right) \] DFT 一般把变换完的图像，四个象限各自内外反转，来把低频放在中间

DCT

离散余弦变换 DCT 的形式 \[ F(u,v)= \alpha_u\alpha_v \sum_{x=1}^{X-1}\sum_{y=1}^{Y-1} I(x,y) \cos\left(\frac{\pi(2x+1)u}{2X}\right) \cos\left(\frac{\pi(2y+1)v}{2Y}\right) \] 逆变换的形式 \[ I(u,v)= \sum_{x=1}^{X-1}\sum_{y=1}^{Y-1} \alpha_u\alpha_v F(x,y) \cos\left(-\frac{\pi(2x+1)u}{2X}\right) \cos\left(-\frac{\pi(2y+1)v}{2Y}\right) \] 其中 \[ \begin{aligned} \alpha_u&=\begin{cases} 1/\sqrt{X}, &u=0 \\ \sqrt{2}/\sqrt{X}, & 1\le u\le X-1 \end{cases} \\ \alpha_v&=\begin{cases} 1/\sqrt{Y}, &v=0 \\ \sqrt{2}/\sqrt{Y}, & 1\le v\le Y-1 \end{cases} \end{aligned} \] DCT 的解释：每个像素是一个权重图像逐点乘整个图像

DCT 计算分离：可以先对 Y 轴 DCT 再对 X 轴 DCT

矩阵计算 DCT：

构造矩阵 $A$ 满足 $A_{ij}=\alpha_i\cos(\pi(2j+1)i/(2Y))$
构造矩阵 $A'$ 满足 $A_{ij}=\alpha_j\cos(\pi(2i+1)j/(2X))$
那么有 $F=AIA'$（当 $X=Y$ 时有 $A'=A^T$）

Morphing

即分块线性变换加交叉溶解

重心坐标（Barycentric Coordinates）：$X=\alpha A+\beta B+\gamma C$，且 $\alpha + \beta + \gamma =1$

Seam Carving

即切掉较为同质的一行或一列，做到保持物体比例的图像大小变换

能量矩阵即对原图像作两个方向的梯度模板运算，再求 L2 范数

在能量矩阵上建图，上一行的点到下一行的三个点的边权为能量矩阵值的差，DP 求最短路

梯度融合

即将一部分图像粘贴到另一张图像，并且保持边缘梯度一致的方法

光流法

对于两张图片，它们间进行了尺度不大的几何变换，想要求对应点

给定两张图片 $I$ 和 $J$，设点 $\boldsymbol x$ 在 $I$ 的定义域内，求 $J$ 中 $\boldsymbol x$ 的对应点 $\boldsymbol x+\boldsymbol d$ 使 $I(\boldsymbol x)\sim J(\boldsymbol x + \boldsymbol d)$

设 $E(\boldsymbol d)=\|J(\boldsymbol x + \boldsymbol d)-I(\boldsymbol x)\|^2$，求 $\arg\min E(\boldsymbol d)$；泰勒展开得 \[ E(\boldsymbol d)\approx\left\| J(\boldsymbol x) + \frac{\partial J(\boldsymbol x) }{\partial \boldsymbol x}\boldsymbol d -I(\boldsymbol x) \right\| \] 这里梯度向量是行向量；设右部为零以列方程，移项得 \[ \frac{\partial J(\boldsymbol x) }{\partial \boldsymbol x}\boldsymbol d = I(\boldsymbol x) -J(\boldsymbol x) \] 左右同乘 $\boldsymbol x$ 处梯度向量的转置得 \[ \left({\frac{\partial J(\boldsymbol x) }{\partial \boldsymbol x}}^T \frac{\partial J(\boldsymbol x) }{\partial \boldsymbol x}\right) \boldsymbol d = {\frac{\partial J(\boldsymbol x) }{\partial \boldsymbol x}}^T (I(\boldsymbol x) -J(\boldsymbol x)) \] 虽然可以求解，但是极易尺度过小导致左右均为零，所以要在一个窗口（点集合 $W$）上列方程求解，注意到 $\boldsymbol d$ 在窗口内共享 \[ \sum_{\boldsymbol x\in W} \left({\frac{\partial J(\boldsymbol x) }{\partial \boldsymbol x}}^T \frac{\partial J(\boldsymbol x) }{\partial \boldsymbol x}\right) \boldsymbol d = \sum_{\boldsymbol x\in W} {\frac{\partial J(\boldsymbol x) }{\partial \boldsymbol x}}^T (I(\boldsymbol x) -J(\boldsymbol x)) \] 求得偏移量 $\boldsymbol d$ 后，对图像做变换，然后继续迭代，累加所有的偏移量直到两图像差异小于阈值

机器学习

和别的课程重复的部分就不整理了，包括：感知机；梯度下降；BP；CNN 的概念；YOLO/SSD 等。

CNN

这一小节不符合符号规范，但是在深度学习的上下文中可以理解

假设输入特征张量 $x$ 的尺寸 $(N,C_{in},W_{in},H_{in})$，输出张量 $y$ 的尺寸 $(N,C_{out},W_{out},H_{out})$，卷积核 $h$ 的尺寸 $(C_{in}, C_{out},W_{k},H_{k})$

假设卷积操作的 Padding 为 Same，Stride 为 1，卷积 $y=x\otimes h$ 的运算如下（卷积核以偏移量作索引） \[ y_{c_o,x,y}= \sum_{c_i=0}^{C_{in}} \sum_{w=-\lfloor W/2\rfloor}^{\lfloor W/2\rfloor} \sum_{h=-\lfloor H/2\rfloor}^{\lfloor H/2\rfloor} x_{c_i,x+w,y+h}h_{c_i,c_o,w,h} \] 假设损失函数 $L$ 对 $y$ 对导数为 $\delta_y$，那么反向传播 \[ \begin{cases} \delta_x=\delta_y\otimes ROT_{180\degree}(h) \\ \dfrac{\partial L}{\partial h} = \delta_y\otimes ROT_{180\degree}(x) \end{cases} \] 注意到，$ROT_{180\degree}$ 表示将二维图像旋转 180 度，也是索引取反。并且若正向的 Padding 是 Full，反向的 Padding 为 None，反之亦然。

特征提取

Canny 边缘检测

将图像转换为图像的方式，生成的图像中的亮点说明原图像的对应点属于边缘

高斯滤波；
计算边缘强度（两个方向梯度的 L2 范数）；
计算边缘方向（两个方向的梯度）；
极大值抑制；
连接边缘（Hystersis）：确定两个边缘强度的阈值，从强点开始沿着切线方向搜索加入所有的中强点。

Harris 角点检测

量化当前矩形框与周边的差异，并通过特征值判断是角点还是边

对于矩形框中一个点 $(x+m,y+n)$ 和加一个任意偏置 $(u,v)$ 得到的新点 $(x+m+u,y+n+v)$，它们的差异是 $[I(x+m+u,y+n+v)-I(x+m,y+n)]^2$；对其加权求和可得这个矩形框的任意方向差异度量 \[ \sum_{m,n}w(m,n)[I(x+m+u,y+n+v)-I(x+m,y+n)]^2 \] 其中 $w(m,n)$ 可以是一个高斯函数来强调矩形框中心的权重。接下来提出一种不用再对 $u,v$ 求和的方法。首先关于 $u,v$ 进行一阶 Taylor 近似 \[ \begin{aligned} &\sum_{m,n}w(m,n)\left[\frac{\partial I(x+m,y+n)}{\partial x}u+\frac{\partial I(x+m,y+n)}{\partial y}v\right]^2 \\\triangleq & \sum_{m,n}w(m,n)\left[I_x(x+m,y+n)u+I_y(x+m,y+n)v\right]^2 \\= & \sum_{m,n}w(m,n) \begin{bmatrix}u & v\end{bmatrix} \begin{bmatrix} I_x^2(x+m,y+n) & I_xI_y(x+m,y+n) \\ I_xI_y(x+m,y+n) & I_y^2(x+m,y+n) \end{bmatrix} \begin{bmatrix}u \\ v\end{bmatrix} \\\triangleq & \sum_{m,n}w(m,n) \begin{bmatrix}u & v\end{bmatrix} H(x+m,y+n) \begin{bmatrix}u \\ v\end{bmatrix} \end{aligned} \] Hessian 矩阵 $H$ 是一个二次型矩阵，可以求其两个实特征值 $\lambda_1$，$\lambda_2$；我们关注两个特征值的大小，如果两个都很大，说明两个方向都有很大的变化系数，那么是角点；如果其中一个大，那么是边缘；如果都不大，说明不是角点也不是边缘。

实际上操作的时候可以先滤波，就不用考虑矩形框里求和了，直接对每个点求特征值就行。

SIFT 特征

Scale-invariant feature detection

基础概念

LoG（Laplacian of Gaussian）即高斯核的拉普拉斯函数 \[ LoG(x,y)= \Delta G = \frac{\partial G^2}{\partial x^2}+\frac{\partial G^2}{\partial y^2}= \frac{1}{\pi\sigma^4} \left(\frac{x^2+y^2}{2\sigma^2}-1\right) \exp\left(-\frac{x^2+y^2}{2\sigma^2}\right) \] 归一化的 LoG $\tilde \Delta G=\sigma LoG$

DoG（Diffierence of Gaussian）是不同方差（$\sigma$ 和 $k\sigma$）的高斯核的差，是 LoG 的高效替代 \[ \begin{aligned} \sigma\Delta G=\frac{\partial G}{\partial \sigma} &\approx \frac{G(x,y,k\sigma)-G(x,y,\sigma)}{(k-1)\sigma} \\ &\Longrightarrow \\ DoG(x,y)&=G(x,y,k\sigma)-G(x,y,\sigma) = (k-1)\sigma^2 \Delta G \end{aligned} \] ##### 步骤

第一步：求尺度空间的极大值

给定输入图像 $I$，先分别使用六个方差（$\sigma,k\sigma,\cdots,k^5\sigma$）的高斯函数对其滤波得到六张图像（等价于用 $k^n\sqrt{k^n-1}\sigma$ 做五次），对其作差得到五张 DoG图像。对 $I$ 两倍下采样一次作同样的一组 DoG，还可以下采样更多次，得到高斯金字塔。

若一个点在其 DoG 的八邻域以及相邻尺度的 DoG 的八邻域这 27 个点中是极大值，那么它是一个关键点。

第二步：关键点筛选和插值

首先对 DoG 插值，来更精细地定位关键点，然后类似 Harris 作 Hessian 矩阵过滤边缘，最后做阈值筛选出特征点。

第三步：确定方向

在特征点的邻域内求所有的梯度幅值和方向进行投票，投票出 36 个离散方向中的前几个作为特征的方向。

第四步：求描述子

依据特征点的方向，取 $16\times 16$ 邻域分为 $4\times 4$ 的块，对于每块做 8 个离散方向的梯度方向直方图，则最后得到一个 128 维的描述子。

HOG 特征

Histogram of Oriented Gradient

给定一个图像，拆成 $8\times8$ 的格子（Cell），每个格子统计一个九个离散方向的梯度直方图

对于每四个邻近格子，称为一块（Block），块内做归一化

对于一个 $64\times 128$ 大小的图像，滑动提取块后，将会有 $7\times 15$ 个块。每个块贡献各自的梯度直方图，形成一个维数 $36×7\times 15=3780$ 的描述子

特征差异度量

当使用 Harris 或 SIFT 等方法得到两个特征点 $(x,y)$，$(x',y')$ 对应的图像块时，可以度量这两个图像块的差异

SAD（Sum of Absolute Difference） \[ SAD=\sum_{n=-N}^N\sum_{m=-M}^M|I_1(x+m,y+n)-I_2(x'+m,y'+n)| \] MSE（Mean Squared Error） \[ MSE=\frac{\sum_{n=-N}^N\sum_{m=-M}^M[I_1(x+m,y+n)-I_2(x'+m,y'+n)]^2} {(2N+1)(2M+1)} \] NCC（Normalized Cross Correlation） \[ NCC=\frac{\sum_{n=-N}^N\sum_{m=-M}^M[I_1(x+m,y+n)-\mu_1][I_2(x'+m,y'+n)-\mu_2]} {[(2N+1)(2M+1)-1]\sigma_1\sigma_2} \]

Hough 投票

对栅格图像中直线、圆等简单几何体（参数不多）进行矢量化的一种方法

以直线为例：对于每个点，穷举一些通过它的直线，计算这些直线通过的别的点，进行投票

RANSAC

Random Sample Consensus，是一种通过数据点拟合模型的方法

步骤

随机采样：取一些足够计算出模型参数的样本
构建模型：计算模型参数
过滤：使用构建的模型和阈值，筛选出符合模型的样本
内点计数：统计各模型符合的样本数，找出最好的模型

\(L\)	\(\dfrac{\partial L}{\partial \boldsymbol x}\)
\(\boldsymbol x^T A \boldsymbol x\)	\(\boldsymbol x^T(A+A^T)\)
\(\boldsymbol a^T\boldsymbol x\)	\(\boldsymbol a\)
\(\boldsymbol x^T \boldsymbol a\)	\(\boldsymbol a^T\)