这是 2025 春 计算机视觉导论的笔记

Todo:

• 内容杂乱无章，十分愚蠢，或许未来会润色语言使它便于阅读

Review

1. 目标：Lane Detection
2. 完成的部分：Edge Detection
3. 现在的目标：从散点到直线，得到更好的 Line Fitting

Least Square Method

1. Least Square Method：L2 norm - Find (m, b) to minimize \displaystyle E = \sum_{i=1}^n (y_i - mx_i -b)^2

   1. let \displaystyle Y = \left[\begin{matrix}y_{1} \\ \vdots \\ y_{n} \end{matrix}\right] , \displaystyle X = \left[\begin{matrix}x_{1} & 1 \\ \vdots & \vdots \\ x_{n} & 1 \end{matrix}\right], B = \left[\begin{matrix}m\\b\end{matrix}\right], \displaystyle E = ||Y-XB||^2, finally gives \displaystyle B = (X^TX)^{-1}X^TY，必要数学参见 matrix cookbook

   2. 一个凸优化问题，且具有唯一全局最小值

   3. Limitation: For outlier, it's not robust, 离群点会把线全部带偏; fails for vertical line

   4. Improvement: Use \displaystyle ax+by=d, to maxmize E, data \displaystyle A = \begin{bmatrix}x_{1} & y_{1} & 1 \\ \vdots & \vdots & \vdots \\ x_{n} & y_{n} & 1\end{bmatrix}, \displaystyle \boldsymbol{h} = \begin{bmatrix}a \\ b \\ d\end{bmatrix}. 此时得到的最小二乘回归方程 \displaystyle \boldsymbol{Ah} = 0，并满足 \displaystyle E=||\boldsymbol{Ah}||^2 最小；它有一个平凡解 (0, 0, 0)；指定 \displaystyle a^{2}+b^{2}+d^{2}=1 可以让解唯一化，失去平凡解

2. Solve：Find \displaystyle \boldsymbol{h}, minimize \displaystyle ||\boldsymbol{Ah}||, subject to \displaystyle ||\boldsymbol{h}||=1
   1. 问题转化：找到单位球面上的一个点使得这个点和A的点积最小
   2. 方阵矩阵的特征值分解：实对称方阵一定可以对角化 => 解 \displaystyle Bx=\lambda x 得到 n 个特征值 \displaystyle \lambda 和 \displaystyle x_{i} => 凡是可以对角化的矩阵 n 个特征向量构成正交基 => 取最小的 \displaystyle \lambda 时 \displaystyle ||\boldsymbol{Bh}|| 最小 (把对应的维度压缩到最小)
   3. 非方阵矩阵不能做特征值分解/对角化 => 提出了一种从方阵到非方阵的extension：Singular Value Decomposition (SVD)
3. Analysis：Robustness Absolutely still sensitive to outliers; 这来自 L2 Norm 越离群 gradient 就越大的特性; 如果用 L1 Norm？收敛就很困难

RANSAC

Random Sample Consensus: 解决离群点的问题

1. 自动丢掉离群点的方法：如果已经知道了答案，离群点就会离它significantly地远；那么就随机取出一个Sample，求这个Sample构成的hyperplane(如果Sample数大于维度就要最小二乘或SVD了，等于维度就可以直接求解线性方程组)，再衡量Consensus，让支持它的dataset里尽可能没有outlier
2. RANSAC Loop
   1. Initialize: 随机取 2 个点 (期望不包含Outlier，所以是最少的可以形成hyperplane的seed group)
   2. Compute: transformation from seed group
   3. Inliers: 计数合群点的数目，更新最大Inliers => 找到Inliners最多的那个Sample

We should implement a parallel version: Use Tensor, No For Loop

3. Hyperparameters
   1. Hypothesis: 取出多少个点做Sample
   2. Theoshold: 算作Inlier的阈值 (例如 \displaystyle 3\sigma)
4. Post-process：如果多个seed group给出了相同的Inlier number？朴素的优化 => 把这些Inlier选出来，用最小二乘或SVD给出最后的结果的那个方程
5. 为什么要选最小数目的hypothesis？包含n个点的hypothesis全都正确的概率是 \displaystyle \omega^{n}，所有的k个sample全部fail的概率是 \displaystyle (1-\omega^{n})^{k}，所以需要尽量减小n，增大k
6. Pros and Cons
   1. Pros: general, easy
   2. Cons: only moderate percentage of outliers => Voting Strategy, Hough Transform

Summary

gradient -> edge -> line

这个是 module-based system，缺点是一步出错就会影响很多，需要很强的robustness；自动驾驶从几十万行的rule到End2End的system也是这样的；
Lecturer: 某司唯一的不端到端的是提取出红绿灯🚥结果识别，再丢进网络里；
这部分总之只是对经典视觉方法的管中窥豹；

Corner Detection

1. 图片的 keypoints 也是很重要的东西，应用例：从关键点检测keypoints localization，到corri-bonding到image matching到相机的rotation/transform的识别
2. Requirements
   1. Saliency: Interesting points
   2. Repeatability: same result, same object, different images
      1. 对亮度的不变性 Illumination invariance
      2. Image scale invariance
      3. Viewpoint invariance
         1. implant rotation: 关于相机主轴的旋转
         2. affine: 产生仿射变换 (?)
   3. Accurate localization
   4. Quantity: number sufficient
3. Corner
   1. 基本满足上面的requirements
   2. key property: in the region around the corner, image gradient has two or more dominant directions
   3. Harris Corner: Use a Sliding Window
      留意我们没有再进行edge detection，这里衡量gradient的方法是滑动窗口内的intensity
4. Implement
   1. Move
   2. Square diff
   3. Window function
   4. Let Square intensity difference \displaystyle D(x, y)=[I(x+u, y+v)-I(x, y)]^{2}
      Window Function \displaystyle w(x,y) which has a param \displaystyle b
      => 成为一个卷积操作\begin{align}\displaystyle E_{x_{0},y_{0}}(u,v) & =\sum_{x,y}w^{\prime}_{x_{0},y_{0}}(x,y)[I(x+u, y+v)-I(x, y)]^{2} \\ & =\sum_{x,y}w(x_{0}-x,y_{0}-y)D_{u,v}(x,y) \\ & =w*D_{u,v}\end{align}
      1. 在 \displaystyle (x_{0},y_{0}) 周围关于 \displaystyle (u,v) 做一阶 Taylor 展开，进而把 \displaystyle D 写成二次型
         注意每个I都是一个大的image
      2. Result
      3. Analysis
      4. Corner/Edge/Flat?
      5. 问题：多大算大？可能需要多个超参，但我们只关心corner，可以定义
      6. let window rotation-invariant => Gaussian window
5. Whole Process

这一部分推导

Properties

Definitions
If \displaystyle X\in V, and \displaystyle f:V\to V is a function, \displaystyle T:V\to V is a transformation operation like translation or rotation, then

• \displaystyle f to be equivariant under \displaystyle T if \displaystyle T(f(x))=f(T(x))
• \displaystyle f to be invariant under \displaystyle T if \displaystyle f(x) = f(T(x))

1. Scale
   1. Harris Detection 对 translation 和 rotation (?) 都是 equivariant 都是等变的
   2. To be realistic, 旋转后对网格进行了双线性差值，自然都不可能是rotation-variant的
   3. 对 scale 不是 invariant 的 (自然也没有equivariance)，但问题不大
2. Scale-invariant methods: Harris Laplacian 和 LIFT