2025-02-27
图片可以看作 \(R^2\to R^M\) 的函数. 对于灰度（Grayscale）图，则为 \(f:[a,b]\times [c,d]\to [0,255]\)，其中后者为 Intensity，有一个 channel. 而对于彩色图片，则可以看作 \([r(x,y),g(x,y),b(x,y)]\) 的向量，有三个 channel.
计算机图片一个很大的特点是空间是离散的（像素点），而颜色也是离散的，形成一个网格状（Grid-like）的数据. 灰度图片可以看作一个 \(H\times W\) 的矩阵，而彩色图片则形成了 \(H\times W\times 3\) 的 tensor.
既然图片是函数，那么我们可以求这个函数的梯度. 但由于是离散的，所以用有限的差分去替代这个梯度. 例如 \(f\) 在 \(x_0\) 的梯度直接用 \(\frac{f(x_0+1,y_0)-f(x_0-1,y_0)}{2}\) 计算. 梯度的方向由黑向白.
先在 \(x\) 上求导，再在 \(y\) 上求导，然后可以得到 Gradient Magnitude \(||\nabla f||=\sqrt{(\frac{df}{dx})^2+(\frac{df}{dx})^2}\). 当且仅当一个地方有一个剧烈的颜色变化，即 Edge，才会有很大的 Gradient Magnitude. Gradient 的方向垂直于 Edge. 于是仅用求梯度的方法，我们可以获取图片的边缘相关信息.
Filtering：通过原来的 \(f\)，进行一系列算子的操作，得到一个新的图片. Filtering 是信号处理的术语，而图片可以视作一个二维的信号.
一个一维离散信号的 Filter 的例子：Moving Average.
取 \(h_n\) 为 \(f_{[n-k,n+k]}\) 的均值. 想法是噪声独立随机的话，取一个均值就可以把噪声给消去. 这个 Filter 由于是对原信号进行线性组合，所以是一个 Linear Filter.
这个东西可以扩展到一维离散卷积. 取一个数组 \(g[n]\)，定义 \(h[n]=(f*g)[n]=\sum f[m]g[n-m]\). 相当于对 \(g\) 做翻转后，从左到右做一个邻域的带权相加. 称 \(g\) 为卷积核.
考虑离散傅里叶变换 \(\mathcal F\)，根据我们所熟知的 FFT 那套理论，有卷积定理：\(\mathcal F(f*g)=\mathcal F(f)\cdot \mathcal F(f)\)，于是我们将实域的卷积变成了频域的点乘. 理解一个 Filter 干了什么，可以考虑看它做傅里叶变换后的频谱. 而从频域的角度看，Moving Average 的频谱集中在了 \(0\) 附近，高频处值很小，所以其实就是一个 Low-pass Filter. 但其实我什么也不懂. FFT，谁会？
对于任何 Linear Filter \(\cal G\)，一定能够通过卷积的形式来描述.
考虑扩展到二维的图片上. 定义二维的卷积核（Convolution Kernel）\(g\)，那么可以定义卷积 \((f*g)[m,n]=\sum_{k,l} f[k,l]g[m-k,n-l]\).
对二维图片做 Moving Average 会让边界变模糊.
一个非线性的例子：二值化 Binarization（via Threshold），即设立一个阈值，并令 \(h[m,n]=[f[n,m]>\tau]\).
下面可以通过上述两个很简单的操作实现 Edge Detection. 这个方法也是至今使用的方法.
Edge 的定义：沿着一个方向有剧烈的 Intensity 的变化，并且沿着正交方向变化较小的区域. 注意 Gradient Magnitude 大不等于是 Edge. 比如 Corner 就是沿着多个方向变化都大.
Edge Detection 的 Criteria：Precision = \(\frac{TP}{TP+FP}\)，Recall = \(\frac{TP}{TP+FN}\). Localization & Response.
考虑之前做的求梯度. 如果图片有高频的噪声，那么就会变得很搞笑，因为哪里都有巨大的梯度. 所以就要抑制噪声，对整个图片做一个 Low Pass Filter.
Gaussian Filter：取 \(g=\frac{1}{\sqrt{2\pi\sigma^2}}\exp(-\frac{x^2}{2\sigma^2})\) 做卷积. 做傅里叶变换后有 \(\cal F(g)=\exp(-\frac{\sigma^2\omega^2}{2})\).
首先这个 Filter 满足 \(0\) 处很高，且积分为 \(1\)（不然会导致整张图片能量产生变化）. 并且这个 Filter 受到 \(\sigma\) 控制. \(\sigma\) 越大，高频抑制作用越大. \(\sigma \to 0\) 时相当于啥都不做. 而这个 Filter 好就好在不管在哪个域，都是一个高斯函数.
运用 Gaussian Filter 之后，影响 Edge Detection 的高频噪音就被去除了. 我们的步骤就是先卷积，再求导.
卷积求导定律：\(\frac{d}{dx}(f*g)=f*\frac{d}{dx}g\). 于是可以从两步变成一步. 这本质其实就是因为求导本身也是卷积. 但是由于要求 Magnitude 所以要对 \(x\) 和 \(y\) 两个维度分开求. 然后再做一个二值化.
但是就算这样，一个 edge 的宽度太大了. 于是我们需要做一个去冗余的操作.
Non-Maximal Suppression：对于留下来的点 \(q\) 和 gradient magnitude \(g(q)\)，沿着 \(g(q)\) 找两个邻居 \(r=q+g(q)\) 和 \(p=q-g(q)\). \(r,p\) 未必是整点，所以需要插值计算 \(g(r)\)，\(g(p)\). 如果 \(g(q)\) 为三者中最大值，那么保留，否则抛弃.
插值采用 Bilinear Interpolation. 对于 \((x,y)\) 邻域的四个形成正方形的格点，能分割成四个长方形。按照对角的长方形的面积作为权值，进行带权平均. 也相当于先算两个关于 \(x\) 轴的投影的点的值通过线性插值算出来的值，在用这两个点对于目标点做一个线性插值.
一个另一个简化的 NMS：先看 Gradient 的方向按照上下左右以及斜上下左右去分类，然后直接比较两个 pixel 的 \(g\) 值.
现在我们已经获得了 Pixel 的信息，现在问题是如何将这些 Pixel 给穿起来，形成 Edges. 即 Edge Linking.
Hysteresis Thresholding：从高可信的地方开始画线，然后串线的时候可以容忍低可信度. 对于所有通过 NMS 的点，求得平均 magnitude，然后据此设置 maxVal 和 minVal. 具体的原则就是起笔的条件是 >maxVal，断掉的条件是 <minVal.
这个 Edge Detector 的名字是 Canny Edge Detector. 其中有若干超参：Gaussian Filter 的 \(\sigma\)，NMS 的步长，Linking 的 minVal maxVal. 其中 \(\sigma\) 越大，细的 edge 就更可能会被 blur 掉.