Classic Vision II

Line Fitting#

很多特点都以线的形式存在，比如道路边界，建筑物边缘，物体轮廓等，因此我们需要一种方法来拟合这些线条

最小二乘法#

数据：$(x_1,y_1), (x_2,y_2), ..., (x_n,y_n)$

目标：找到一条线$y = ax + b$，使得所有点到这条线的垂直距离的平方和最小，即minimize $E=\sum_{i=1}^n (y_i - ax_i - b)^2$

设$Y = [y_i], X=[x_i,1], B=[a,b]^T$

写成矩阵形式就是

$$E = |Y-XB|^2 = (Y-XB)^T(Y-XB) = Y^TY-2(XB)^TY+(XB)^T(XB)$$

对$B$求导，令其为$0$，得到

$$\frac{\mathrm{d} E}{\mathrm{d} B} = -2X^TY + 2X^TXB = 0$$

解出$B = (X^TX)^{-1} X^TY$

这种方法有一个问题，就是不能拟合垂直的线条（当$a$趋近于无穷大时），因此我们需要一种更一般的方法来拟合线条

General case

我们可以把线条表示$ax + by + c = 0$，这样就可以拟合任意方向的线条了，此时

$$E = \sum_{i=1}^n (ax_i + by_i + c)^2$$

设$A = [x_i,y_i,1], h=[a,b,c]^T$，则写成矩阵形式就是$E = |Ah|^2$

我们想要最小化$|Ah|$，但是为了避免平凡解$h=0$，我们需要加上一个约束条件$|h|=1$

对$A$进行SVD分解，得到

$$A_{n\times 3} = U_{n\times n}\Sigma_{n\times 3} V^T_{3\times 3}$$

其中$\Sigma$是一个对角矩阵，三个奇异值设为$\lambda_1 \geq \lambda_2 \geq \lambda_3$，$U$和$V$是正交矩阵

设$V = [c_1, c_2, c_3]$，其中$c_i$是$V$的第$i$列，这三列构成了一个正交基，因此我们可以把$h$表示成$c_1, c_2, c_3$的线性组合，即

$$h = \alpha_1 c_1 + \alpha_2 c_2 + \alpha_3 c_3,\quad\alpha_1^2+\alpha_2^2+\alpha_3^2 = 1$$

那么$Ah = U_{n\times n}[\lambda_1\alpha_1, \lambda_2\alpha_2, \lambda_3\alpha_3, O]^T$

因此$|Ah|^2 = (\lambda_1\alpha_1)^2 + (\lambda_2\alpha_2)^2 + (\lambda_3\alpha_3)^2\geq \lambda_3^2$，此时$h = c_3$，也就是说我们需要选择$V$的最后一列作为我们的解

RANSAC#

在实际应用中，数据中往往会存在一些离群点（outliers），这些离群点可能会对我们的拟合结果产生很大的影响，因此我们需要一种方法来处理这些离群点，RANSAC就是一种常用的方法

具体步骤：

• 选择所需样本量最小的随机样本进行模型拟合
• 从取样的点中拟合模型
• 计算所有点到拟合模型的距离，判断哪些点是inliers，哪些点是outliers
• 迭代多次，保留inliers数量最多的模型

那么我们应该选取多少个样本点进行拟合，以及该迭代多少次？

设下面几个参数：

• $n$:确定模型所需的最少点数（最小样本数）
• $\epsilon$:内点比例，$0<\epsilon<1$
• $k$:迭代次数
• $p$:期望的成功概率，即以概率$p$保证至少有一次采样全是内点

从数据中随机选取$n$个点，全部是内点的概率为$\epsilon^n$，单次采样至少包含一个离群点的概率为$1-\epsilon^n$，迭代$k$次至少有一次采样全是内点的概率为$1-(1-\epsilon^n)^k$，而我们希望这个概率大于$p$，因此有

$$1-(1-\epsilon^n)^k \geq p \Rightarrow k \geq \frac{\log(1-p)}{\log(1-\epsilon^n)}$$

观察上面的公式，我们可以看到，固定$p$和$\epsilon$，当$n$增加时，迭代次数$k$会急剧增加，因此我们应该尽量选择较小的$n$，比如拟合一条线时$n=2$，拟合一个平面时$n=3$

一些超参数：

• threshold：如果一个点到拟合模型的距离小于这个threshold，那么这个点就被认为是inlier
• $k$:迭代次数，因为实际上我们不知道$\epsilon$的值，因此无法计算出$k$

Corner Detection#

除了edge，keypoint也是图像中的重要特征。keypoint一般有以下特点：

• 可重复性：在两幅图像中独立地检测出相同的点
• 显著性：在图像中具有明显的特征
• 算法可以精确定位
• 有足够的数量
• 在不同光照、视角、尺度下具有鲁棒性

corner就是一种keypoint，下面我们介绍用于检测corner的一些算法

Harris Corner Detector#

在corner处，图像的梯度在两个方向上都有显著的变化，可以利用这一点来检测corner

我们设$I(x,y)$为图像的灰度值，$(u,v)$为一个小的位移，我们定义Intensity difference为

$$D_{u,v}(x,y) = [I(x+u,y+v) - I(x,y)]^2$$

用一个窗函数$w(x,y)$来描述范围

$$w(x,y) = \begin{cases}1, & \text{if } -b\leq x,y \leq b \\0, & \text{otherwise}\end{cases}$$

如下图，我们计算某个点$(x_0,y_0)$处移动一个小位移$(u,v)$后窗口内的Intensity difference的变化$E_{x_0,y_0}(u,v)$

图中$E_{x_0,y_0}(u,v)$本质上是$D_{u,v}(x,y)$与$w(x,y)$的卷积，即

$$E_{x_0,y_0}(u,v) = (D_{u,v} * w)(x_0, y_0)$$

对$D_{u,v}(x,y)$进行泰勒展开，得到

$$D_{u,v}(x,y) \approx (I_x u + I_y v)^2 = [u, v] \begin{bmatrix}I_x^2 & I_x I_y \\ I_x I_y & I_y^2\end{bmatrix} \begin{bmatrix}u \\ v\end{bmatrix}$$

那么$E_{x_0,y_0}(u,v)$就可以写成

$$E_{x_0,y_0}(u,v) = [u, v] M(x_0,y_0) \begin{bmatrix}u \\ v\end{bmatrix}$$

其中$M$是一个2x2的对称、半正定矩阵

$$M(x,y) = \begin{bmatrix}I_x^2 * w & I_x I_y * w \\ I_x I_y *w & I_y^2 * w\end{bmatrix}$$

$M$可以对角化为$Q\ diag\{\lambda_1,\lambda_2\}\ Q^T$，其中$\lambda_1\geq \lambda_2\geq 0$

因为$Q$为正交矩阵，可以将$[u,v]$变换为另一组正交基，即$[u',v'] = [u,v]Q$，此时

$$E_{x_0,y_0}(u,v) = [u', v'] \begin{bmatrix}\lambda_1 & 0 \\ 0 & \lambda_2\end{bmatrix} \begin{bmatrix}u' \\ v'\end{bmatrix} = \lambda_1 u'^2 + \lambda_2 v'^2$$

由此我们可以进行直观上的分类：

• $\lambda_1 \approx 0, \lambda_2 \approx 0$:平坦区域 （不管怎么移动，Intensity difference都不变）
• $\lambda_1 \gg 0, \lambda_2 \approx 0$: 边缘 （在某个方向上Intensity difference有显著变化，在另一个方向不变）
• $\lambda_1 \gg 0, \lambda_2 \gg 0$:角点 （在两个方向上Intensity difference都有显著变化）

• 角点也可以按照图中分类，要求$\lambda_1$和$\lambda_2$都大于某个threshold，并且$\lambda_1/\lambda_2$也不能太大

对于上面的条件，进行一些数学上的转换：

$$\lambda_1,\lambda_2 > b \Rightarrow \lambda_1\lambda_2 - 2t > 0,\quad t = \frac{b^2}{2}$$ $$\frac{1}{k}<\frac{\lambda_1}{\lambda_2} < k \Rightarrow \lambda_1\lambda_2 - 2\alpha(\lambda_1+\lambda_2)^2 > 0,\quad \alpha = \frac{1}{2(k + \frac{1}{k})^{2}}$$

因此我们可以定义一个corner response function $\theta$

$$\begin{aligned} \theta & = \frac{1}{2}(\lambda_1\lambda_2 - 2t) + \frac{1}{2}(\lambda_1\lambda_2 - 2\alpha(\lambda_1+\lambda_2)^2) \\ & = \lambda_1\lambda_2 - \alpha(\lambda_1+\lambda_2)^2 - t \\ & = \det(M) - \alpha \cdot \mathrm{trace}(M)^2 - t \end{aligned}$$

当$\theta > 0$或某个threshold时，我们认为这个点是一个corner

Harris Detector Process#

1. 计算图像的梯度$I_x$和$I_y$
2. 计算$I_x^2, I_y^2, I_x I_y$
3. 用窗函数对$I_x^2, I_y^2, I_x I_y$进行卷积
4. 计算corner response function $\theta$，找到所有$\theta$大于某个threshold的点
5. 对于所有$\theta$大于threshold的点，进行NMS计算，保留局部最大的点

Harris 算子的特点#

关于不变性（invariant）和等变性（equivariant）：

• 不变性：对于某个变换$T$，如果算法的输出不受$T$的影响，即$f(T(I)) = f(I)$，则称算法具有不变性
• 等变性：对于某个变换$T$，如果算法的输出也发生相同的变换，即$f(T(I)) = T(f(I))$，则称算法具有等变性

Harris算子具有平移等变性，显然求导数和卷积操作都是平移等变的

对于使用具有各向同性（isotropic）的窗函数（即窗函数具有旋转不变性），比如高斯窗或矩形窗，Harris算子还具有旋转等变性

但不具有尺度不变性