Computer Vision

1. Introduction

What is

Make a computer understand images and “tell a story” like human beings.
To bridge the gap between pixels and “meaning”.
Vision as a source of semantic information.

Philosophy in human vision system

等级制的—->多尺度融合
中心偏置的—->正则化
显著性—->显著性检测

Covers

compute 3D structure (shape and motion capture)
recognition (对象检测、语义分割、图像描述、行为识别)
Image enhancement (背景模糊、超分辨率重建、去噪、阴影去除、去模糊)
Image editing (风格迁移、图像生成、图像修复、图像填补)

Application

OCR (Optical Character Recognition)
Face detection and analysis (smile detection…)
Fingerprint/ face unlock
recreation(例如，张嘴吐口红)
Google maps: Annotate all houses and streets
Amazon Go (supermarket)
tracking 追踪
autonomous vehicles
robotics
medical diagnosis
vision-based interaction and games (运动手环)
Augmented Reality (AR 增强现实)
Virtual Reality

Challenges

view variance
weak lighting
scale discrepancy
Intra-class variance
motion
cluttered background
occlusion
blur

2. Image filtering

Image formation

图像数字化：离散化连续图像，包括采样和量化

sampling：将连续图像空间划分为M*N个网格
quantization：将连续的亮度变化转换为单个数字
- gray scale: 表示像素位置的亮度和暗度的整数 0-255

Image representation

二维矩阵表示图像像素的二维排列

Image resolution (分辨率)：采样点的数量。采样间隔越大，采样点越少，分辨率越低

binary image：0和1，0：black，1：white。
gray scale image: 0-255表示灰度
color image：
$f(x,y)=\begin{bmatrix}r(x,y)\\g(x,y)\\b(x,y)\end{bmatrix} R=\begin{bmatrix}255&240&240\\255&0&80\\255&0&0 \end{bmatrix}...$

description of an image

grayscale
contrast
RGB

Color

RGB(red, green and blue)

CMYK(Cyan青, Magenta洋红, Yellow, Black)

$\begin{bmatrix}C\\Y\\M\end{bmatrix} = \begin{bmatrix}1\\1\\1\end{bmatrix} - \begin{bmatrix}R\\G\\B\end{bmatrix}$

neignborhood: 四领域：上下左右；八领域：一圈

attributes: 色调、饱和度、亮度

Image filtering

应用目标：图像去噪（噪声：和领域差别大的点）

filter kernel
- moving average 移动平均：将每个像素替换为领域的加权平均值，以保证信息量不变，且卷积后的数据不会溢出
卷积定义

将卷积核先水平再竖直翻转后再对应位相乘。
卷积性质：
- linearity (线性)
- shift invariance (平移不变性) —->任意线性平移不变运算可以表示为卷积
- commutative：滤波器和信号之间在概念上没有差异
- associative：逐个应用滤波器相当于应用一个滤波器
- distribution over addition
- scalars factor out
卷积输出
- full / same / valid (f+g / f / <f)
- extrapolate image: 在外圈补黑色、边缘像素复制、边缘像素延展
linear filter
- original
  $\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}$
- shifted left
  $\begin{bmatrix}0&0&0\\0&0&1\\0&0&0\end{bmatrix}$
- blur with box filter
  $\frac{1}{9}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}$
- sharpening
  $\begin{bmatrix}0&0&0\\0&2&0\\0&0&0\end{bmatrix}-\frac{1}{9}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}$
  说明模糊会减少边缘信息
  
  original - smoothed = detail
  
  original + detail = sharpened
- disadvantage
  
  出现振铃现象（输出图像的灰度剧烈变化处产生的震荡）
  
  出现原因：未考虑图像的景深，损失图像高频信息
Gaussian Kernel

指定领域大小，e.g. 5*5，表示在给定σ的Gaussian图像上取25个格子；σ指平均值周围变化程度，σ越大，变化越缓慢，图片越糊

Gaussian filters
- 从图像中删除”高频“部分（低通滤波器）
- 自我卷积是另一种高斯函数
  - 可以用small-σ kernel，进行多次运算，以达到large-σ的效果（更糊）
  - 对一幅图像进行连续两次σ=1的高斯卷积相当于进行一次卷积核为√2σ的卷积。满足勾股定理，比如连续的两次高斯卷积核大小为 √2σ,√3σ 可以使用 √13σ高斯卷积核代替。
- separable 可分解性
  $G_\sigma=\frac{1}{2\pi\sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}}=(\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{x^2}{2\sigma^2}})(\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{y^2}{2\sigma^2}})$
  二维高斯可以转化为一维高斯的乘积。
- 复杂度
  - n×n image with m×m kernel: O(n^2m^2)
  - n×n image with m×m separable kernel: O(n^2m)——-?
median filtering 中值滤波
- 将窗口内所有像素值排序，选择中位数作为中心位置像素。
- 非线性
- 对异常值具有鲁棒性
noise
- 椒盐噪声：有随机出现的黑白像素，一般用中值滤波
- 脉冲噪声：有随机出现的白像素，一般用中值滤波
- 高斯噪声：图像是由真实图像+高斯噪声，我们假设噪声的产生是相互独立的，且服从均值为0的正态分布。一般用高斯滤波
  
  | | 高斯滤波 | 中值滤波 |
  | —— | ———————————————————— | —————————————————————— |
  | 优点 | 简单、效率高 | 保护图像的边缘特性、新的值是图片中已存在的值 |
  | 缺点 | 将边缘模糊、丢失了原有特征（产生新的值） | 非线性、计算慢 |
  | 处理 | 高斯噪声 | 椒盐噪声、脉冲噪声 |

3. Edge Detection

Edge

图像局部特性的不连续性（求导找最值）

origin：

表面法相不连续（弯曲）
深度不连续
表面颜色不连续
光亮不连续（影子）

Criteria:

good detection：减少假阳性和假阴性出现的概率
good localization：检测到的边缘尽可能接近真实边缘
single response：最小化真实边缘周围点出现的概率

Image gradient

[纵向边缘，横向边缘]

$\nabla f=[\frac{\partial f(x,y)}{\partial x},\frac{\partial f(x,y)}{\partial y}]\\ gradient \; direction:\theta=tan^{-1}(\frac{\partial f}{\partial y}/\frac{\partial f}{\partial y}) \\ gradient \; magnitude: \|\nabla f\|=\sqrt{(\frac{\partial f}{\partial x})^2+(\frac{\partial f}{\partial y})^2}$

边缘检测算子
- Roberts
  
  感觉x方向和y方向没差
  $G_x=\begin{bmatrix}0&1\\-1&0\end{bmatrix} \quad G_y=\begin{bmatrix}1&0\\0&-1\end{bmatrix}$
- Prewitt
  $G_x=\begin{bmatrix}-1&0&1\\-1&0&1\\-1&0&1 \end{bmatrix} \quad G_y=\begin{bmatrix}1&1&1\\0&0&0\\-1&-1&-1 \end{bmatrix}$
- Sobel（偏向于竖直和水平边缘）
  $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}$
others
- 有噪声使得求导之后找不到边缘，因此，在求导之前需要进行去噪
  $\frac{d}{dx}(f*g)=f*\frac{dg}{dx}$
  由上式可知，我们可以先对滤波器进行求导，再与图片卷积，高斯滤波器求导后不再是可分的。
- 高斯导数滤波器
  
  可以找到多尺度的边缘，但去除噪声的时候会将边缘变模糊
  
  | | smoothing 平滑 | derivative filters 导数滤波器 |
  | ——- | ——————— | ——————————————- |
  | 类型 | 高斯函数 | 高斯函数的导数 |
  | value | 全为正 | 可存在负值 |
  | sum | 1 | 0 |
- Canny edge detector
  1. 将图片作用于高斯导数滤波器，σ越大，检测到的细节信息越少，更偏向大规模边缘。
  2. 计算梯度的大小和方向
  3. 使用非极大值抑制将厚边界变为线条：检查像素是否是沿梯度方向的局部最大值，选择边宽度上的最大值。
  4. 使用滞后阈值法将边界相连：首先定义low-high thresholds,高于high的边界直接要，低于Low的舍去，两者之间的部分如果可以用高阈值边界作为起点和终点将他们连接起来，那就保留。

Bilateral Filter

对图像分小块多次使用高斯导数滤波器，同时设置与中心位置数值相近的邻域权重大（引入亮度值），将高斯导数滤波器与权重分配叠加，形成最终的滤波器。

优点：1. 保留边缘信息。 2. 简单直观。 3. 非迭代

缺点： 复杂度：O(r^2) 非线性

Deep learning-based solutions for low-level vision tasks ？

low-quality images’ procession：

低质量：噪声、雾气、模糊

解决一：多尺度融合 CNN+transformer

解决二：多尺度生成器

解决三：特定任务约束

edge detection:

逐片分类

多尺度连接策略

4. Local Feature

Corners

应用：全景拼接

基本步骤：特征提取——特征匹配——图像对齐

好的特征点：

Repeatability 可重复性，在不同图片多次出现
Sailency 显著性，每个特征点不具有歧义
Compactness and efficiency 紧凑性，特征点远小于图像像素个数
Locality 局部性，特征值只占据图像较小区域

应用： 图像对齐、3D重建、运动追踪、物体识别

finding corner：

★ 角点在至少两个方向上都有显著的梯度，因此向任何方向移动窗口都会有很大的强度变化

★ 角点具有可重复性和可分辨性

Change：

$E(u,v)=\sum_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^2$

(u,v)是平移量，w(x,y)是窗口函数，窗内为1，外面为0。I(x,y)指图像某个像素点的强度，可以理解为高斯导数。

利用二阶泰勒展开：

$E(u,v)\approx \begin{bmatrix}u&v\end{bmatrix}M\begin{bmatrix}u\\v\end{bmatrix}\\ M=\sum_{x,y}w(x,y)\begin{bmatrix}I^2_x&I_xI_y\\I_xI_y&I^2_y\end{bmatrix}=\begin{bmatrix}\lambda_1&0\\0&\lambda_2\end{bmatrix}$

角点检测

$R=det(M)-\alpha trace(M)^2=\lambda_1\lambda_2-\alpha (\lambda_1+\lambda_2)^2\\ \alpha \in[0.04,0.06]\ constant$

Harris detector

计算每个像素的高斯导数
计算每个像素周围高斯窗口中的二阶矩矩阵M
计算角点响应函数R
找到 R>threshold 的
找响应函数函数的局部极大值（非极大值抑制）

invariance：图像被变换但角点位置不改变。
covariance：如果我们有一张图片的两个变换版本，特征会在相应的区域被发现。e.g. 平移、旋转

但尺度不具有协变性。

Scale Invariant Detection

有一个关于尺度的单峰函数，在尺度最合适时函数取得最大值。

Blob detection

Edge = ripple

Blob = 两个ripples的叠加

当唯一极大值出现时，对应的scale就是最合适的。我们希望通过将图像与拉普拉斯算子在几个尺度上卷积并寻找最大相应。

然而，随着σ的增大，拉普拉斯响应变弱，这会造成边界信息的大量丢失，因此，需要normalization。

用σ乘高斯导数，用σ^2乘高斯二阶导。

2D:

$\nabla^2_{norm}g=\sigma^2(\frac{\partial^2g}{\partial x^2}+\frac{\partial^2g}{\partial y^2})$

scale selection: 令上式为零，可得

$\sigma =r/ \sqrt 2$

Scale-space blob detector:

用多个σ对图片进行正则化后的拉普拉斯卷积。
在尺度空间（同层和上下层）找平方拉普拉斯相应的最大值

SIFT

Difference of Gaussians. 用高斯差逼近拉普拉斯算子。