语义分割论文概览

这篇文章是顺着一篇语义分割的综述¹开始阅读相关论文。

介绍

早期的Object Detection多数采用尺度不变特征转换（SIFT）。深度学习应用到Object Detection，使得模型相较于传统算法能进行更复杂、精细地识别。这使得大家的研究方向着重于Generic Object Detection（而不是针对某个类别设计特殊的算法）。

目标

递进地来说，Object Detection的目标可以分为以下几种：

1. 图像级别的分类：将图片标记为一个或多个类别
2. 用边框围出事物并标类（边框有时会被叫做Axis-Aligned，因为它们是与坐标轴平齐的矩形）
3. 语义分割：将图片的每个像素标类
4. 事物实例分割：语义分割的基础上，对于同一类别的不同实例加以区分

挑战

• 准确度相关的挑战
  • 类别内变化大
    • 内在因素：比如各种各样的椅子
    • 图像条件：背景、光照等
  • 类别数目多
• 性能相关的挑战

SIFT²

⚠️警告: SIFT这个算法真的是复杂哭了。这里描述的是原论文里的方法。结合GitHub Repo rmislam/PythonSIFT的源码阅读可以极大地帮助理解原论文。当然这个源码似乎是原论文的改进版，里面用到了很多可怕的数学知识。 本文中的部分图片来源于这个Repo的教程。

该文提出了一种局部的图像特征，它不随缩放、平移、旋转的影响，并能部分地容忍光照、仿射、投影。它有生物学基础，即使是在杂乱、遮挡的情况下也能健壮地识别。

特征采用了分阶段过滤方案：首先寻找关键点。再对每个关键点会生成特征。然后匹配多张图的关键点，就可以寻找待识别的物体。

关键点定位

关键点定位：主要思想

（非人话版）通过高斯差分金字塔，从而尺度不变地选取关键点。其输入是一张图片，目标是选出图片中最有特点的点，类似下图（其中关键点用红点标出）：

高斯差分金字塔：高斯差是将一张图片通过两个标准差不同的高斯模糊后，相互作差得到的一张新的图片。这张新的图片会包含某一层次的细节。通过采用标准差不断递增的高斯模糊图片，而后紧挨着的两个图片作差，就可以得到一系列变化由细致到粗糙的图片。这一系列的差值图片我们成为高斯差分金字塔。类似下图：

极值点即关键点：差分金字塔某层上的极值点，通常是原图中某一尺度变化丰富的点。通过求解每层共享的极值点，就能得到在各个尺度下都变化显著的点，这些点就是我们想要寻找的关键点。

关键点定位：具体算法

我们用第$n$步指代算法的多个阶段，用第$n$步步骤$i$指代某个阶段的具体操作。

第一步：得到高斯差分金字塔。

1. 对输入图片扩大到2倍（面积就4倍哦）使用双线性差值
2. 选取$\sigma=\sqrt{2}$的高斯模糊处理先前的图片，得到图片A
3. 再次使用$\sigma=\sqrt{2}$的高斯模糊处理图片A，得到图片B（此时相当于对步骤2输入图片直接做$\sigma=2$的高斯模糊）
4. 产生一层高斯差分结果$A-B$
5. 将图片B的大小是缩小为原来的$1/1.5$倍，采用双线性插值。如果得到的图片太小或完成一定次数，算法完成。否则将该图片作为步骤2的输入，执行步骤2

第二步：找到关键点。

1. 从高斯差分金字的第1层开始，比较每个像素与其相邻的8个像素的大小，如果都大于或小于，则认为是极值点
2. 接着计算这些极值点对应下一层的像素点（考虑第一步步骤5中的缩放），判断他们是否还为极值点，如果不是则筛去它们
3. 重复第2步，直到遍历完所有层

由于极值点数目减少很快，所以第二步比第一步快很多。

Repo中的算法更加复杂，会对原图进行多次缩小，构成多个octave，然后对每个octave构建固定层的高斯差分金字塔。对于关键点选取，Repo是将某一像素所在的当前层连同前后层附近的点全挖去出来，形成了3x3x3的Cube，然后确保其中间点是其中最大的，从而粗略地定位斑点所在的位置和纵深（整数），作为下一步精确寻找的起始点。为了更精确地定位，Repo会用牛顿迭代法进一步寻找极值点的位置和纵深（实数），之后通过斑点的足够明/暗（响应的大小）和圆润与否进一步（Hessian矩阵特征值比值）筛选。

确认关键点的朝向

确认关键点的朝向：主要思想

（非人话版）通过寻找关键点的主要朝向，之后的特征提取可以在消去这个主要朝向后进行，从而使得特征提取不依赖于旋转方向。

像素$A_{ij}$梯度的模$M_{ij}$和朝向$R_{ij}$：对于第一步步骤2的图片A中的每个像素，我们定义其梯度的大小（模）和朝向：

$$M_{ij}=\sqrt{(A_{ij}-A_{i+1,j})^2+(A_{ij}-A_{i,j+1})^2}$$

$$R_{ij}=\mathrm{atan2}{(A_{ij}-A_{i+1,j},A_{i,j+1}-A_{ij})}$$

关键点的位置修正：之前得到关键点的位置是个整数，这里原论文没有细说怎么修正到sub-pixel，但可以想见是使用二次函数拟合局部点，然后找到极值位置。

对光照环境的健壮：设了个阈值，只考虑大于0.1倍最大可能光照的值。（嗯，我没看懂他在说啥）

关键点的主要朝向计算：挖取关键点周围的像素，计算它们的梯度方向，然后投放到36个桶里（每个桶宽度是$10^\circ$）。注意每个像素对桶的贡献是加权的，权重符合以关键点为中心，标准差为当前层$\sigma$ 3倍的高斯分布。之后，这个直方图会被平滑一下，然后选择最高点。关于“周围”的划分，由于是高斯分布，所以3倍标准差以外的点贡献很小，就可以不考虑算作“周围”。

确认关键点的朝向：具体算法

第三步：关键点的主要朝向计算。

1. 初始化36个桶，以及一个标准差为关键点所在层$\sigma$ 3倍的高斯核
2. 对于关键点所在层的图片$A$（而非$B$），挖取周围的像素（论文没说，我觉得再上面标准差基础上乘3倍就可以了，也就是所在层$\sigma$ 9倍），计算其梯度朝向，找到其对应的桶，往桶中加上该像素对应的高斯核值
3. 用一个平滑函数卷积一下36个桶（Repo里用的卷积核是$[1,4,6,4,1]/16$）
4. 找到数额最大的桶作为方向，这里当然也要使用包括最大桶及其左右的两个桶（共3个点），用二次函数插值找最大点

Repo中为了算法更稳定，它会寻找多个极值点，在极值点是最大值的0.8倍以上时，会创建多个位置相同，方向不同的关键点。

关键点特征提取

关键点特征提取：主要思想

文章扯了一大堆生物学。反正就是把关键点周围的像素，旋转一下，抵消掉主要朝向（这样图片旋转了，特征也不变）。然后统计不同位置（分成4x4个大致位置），不同朝向（分成8个大致方向）的像素点的梯度大小。

不过吧，论文里做的更加优雅点，有种双线性插值的感觉，然后有些数字对不太上，读得很困惑。

关键点特征提取：具体算法

第四步：

1. 创建4x4x8的特征张量，前两个维度表示坐标（这里的每个桶代表4倍关键点大小的像素间距），后一个维度表示方向（这里每个桶代表梯度向量$45^\circ$夹角）
2. 将关键点周围的点旋转抵消掉主要朝向，然后计算对应的特征张量的索引（这里索引是3个实数）即位置和方向，以及要存入的值即梯度大小
3. 将这个梯度大小按索引小数部分对应的权重分配到相邻的8个整数索引上
4. 特征张量归一（除以L2范数）

匹配图像

两幅图的关键点在特征的距离上彼此做个最近邻匹配，然后匹配的节点的坐标送进一个大的表示仿射变换的齐次线性方程组，最后来个最小二乘法。

深度学习模型分类

总的来说模型可以分为两类：

1. 两阶段模型：先预处理选出候选区域
2. 一阶段模型：无预处理阶段

两阶段模型

RCNN（Regions with CNN Features）³

1. 与类别无关的候选区域选取，方案为Selective Search⁴
2. 从图像中裁剪出相同大小的候选区域用于CNN模型预训练
3. 用SVM对CNN模型中提取的特征进行分类
4. 用边框对各类别的特征进行回归

SPPNet(Spatial Pyramid Pooling Net)

之前说到，在RCNN过程中，需要从一张图片中裁剪出的众多区域里提取CNN特征，导致RCNN的训练较慢。而SPP中可以输入不同大小的区域，将其应用于卷积层中，可以使RCNN显著提速。

Fast RCNN

Fast RCNN同时在softmax分类器和边框回归训练，还在CONV和FC layer之间添加了RoI(Region of Interest)池给每一个候选区域提取一个已修正长度的特征。相比RCNN和SPPNet，Fast RCNN更加高效。

Faster RCNN

Faster RCNN用更高效和精确的RPN(Region Proposal Network)来生成候选区域，RPN和Fast RCNN共享CONV特征，然后将其输入分类器或边框中训练，使得计算更高效。

RFCN(Region based Convolutional Network)

在RFCN中，没有隐藏的FC layer。RFCN和Faster RCNN的区别仅在于RoI，在Faster RCNN中，RoI之后的计算不能被分享；而在RFCN中，将一些特殊的CONV层作为FCN的输出来构造一套对位置敏感的地图，这些地图上的RoI不同于标准的，其精确度和Faster RCNN差不多，但速度更快。

Mask RCNN

Mask RCNN处理轴对象实例分割，分为两个阶段，第一个阶段是RPN，第二阶段则是在分类和边框训练的同时在CNN特征地图上进行FCN。

Light Head RCNN

为了提高RFCN的速度，尽可能减少RoI的计算，Li运用了一种大的核分裂卷积来产生更小的特征。

Selective Search

基于图（数据结构）的分割算法⁵

Selective Search的第一步是使用基于图（数据结构）的分割算法。具体来说，对于图像中的每个通道，我们将其看作由边和节点组成的带权无向图$G=(V,E)$，其中每个像素$p_i$对应于一个节点$v_i\in V$。而边，则是连接相邻的8个像素（论文指出可以采用其他的方法）。边的权重表示的是像素的不相似程度（越大越不相似），这里直接使用像素强度$I(p_i)$的差异作为权重：

$$w(v_i,v_j)=|I(p_i)-I(p_j)|$$

通常在进行这步之前，会使用$\sigma=0.8$的高斯模糊（模糊半径1.6）处理一下图片。

接下来，我们定义该图连通分量$C$的内部差异$Int(C)$。它被定义为其最小生成树$MSE$（Prim算法可以得到）最大的边权。

$$Int(C)=\max_{e\in MST(C)} w(e)$$

然后，我们定义两个连通分量$C_1,C_2$的最小内部差异$MInt(C_1,C_2)$：

$$MInt(C_1,C_2)=\min(Int(C_1)+\tau(C_1),Int(C_2)+\tau(C_2))$$

其中函数$\tau$可以调控差异，它越大象征着内部差异越大，相对地更能容忍连通区域之间的大差异，从而促使更大的连通区域形成。可能的设计包括使得细条形的$\tau$比较大，从而使得最终分割不太包含细条形的区域。这里我们使用：

$$\tau(C)=k/|C|$$

其中$|C|$表示连通分量节点的个数。这使得小的连通区域不太可能形成。$k$越大，算法更易形成越大的区域。对于128x128的图片，$k=150$是不错的选择；对于320x240及更大的图片，$k=300$是不错的选择。

算法的结果是一个分割$S$，它被定义为互不交且之间无空隙的连通分量的集合。

最后算法如下：

1. 对边集$E$按权重递增排序$\pi=(o_1,\dots,o_m)$（$m=|E|$）
2. 初始化分割$S$，其中每个节点各自成一个连通分量。
3. 对于$\pi$中的每个边$o_q=(v_i,v_j)$:
   1. 如果$v_i$和$v_j$分属于$S$中不同的两个连通分量$C_i$和$C_j$，且$w(o_q)\leq MInt(C_i,C_j)$：
      1. 合并$S$中的连通分量$C_i$和$C_j$

对于彩色的图片，这个算法在每个通道上运行，最终两个像素在同一个连通分量里当且仅当它们在各个通道上都在同一个连通分量里。

Selective Search剩余算法

一阶段模型

DetectorNet

DetectorNet将边框作为分类问题，给定一个图片，他们用一个网络预测一个大致的格子，然后用四个其余的网络预测出对象的上、下、左、右。Detector必须对每张图片采取重要的样本，然后用网络对每个样本的各部分训练。

OverFeat

OverFeat产生一组特征向量，每个都代表一个输入的图片中的位置以及可以预测物体的出现。一旦一个物体被识别，相同的特征就会被用来预测一个边框分类器。除此以外，OverFeat能通过处理原始图片六倍大小得到多规模的特征来提高整体表现，并将其整合到一起，得到一个最后的特征向量。OverFeat比RCNN速度更快，但精确度不足。

YOLO(You Only Look Once)

不同于其他基于区域的方法，YOLO从图片整体获得特征。YOLO将一张图片分为SS个格子，每个格子预测C类概率，B个边框和置信分数，这些预测都被编译成SS*(5B+C)张量。

YOLO容易忽略一些小的对象，因为格子分割是很粗糙的，而每一个格子又只能包含一个对象。

YOLOv2 and YOLO9000

YOLOv2是YOLO的增强版，用DarkNet19取代了GoogLeNet，优化了现有工作。

YOLO9000用联合优化的方法同时训练了ImageNet和带WordTree的COCO，可以观测9000多个对象类别。

SSD(Single Shot Detector)

SSD比YOLO更快，并与基于区域检测的检测器，如Faster RCNN有差不多的精确度。SSD高效地结合了Faster RCNN中的RPN、YOLO以及多规模CONV特征实现了更快更精确的检测。和YOLO类似，SSD检测一些修正过的边框，然后从中给对象打分，最后由NMS产生最后的检测结果。

基本子问题

基于DCNN的对象表示

特征表示已经转移成为了架构的设计问题。

提高对象表示的方法

检测对象通常需要处理大量数据，一个经典的策略是运行能处理大量图片的检测器，但是会受制于时间和内存；另一种是CNN可以一层一层地计算特征层次，子抽样的层会得到一个如金字塔般固定的规模。

三种多规模对象检测：

1. 检测多CNN层的联合特征
2. 检测多CNN层
3. 上面两种方法的结合

上下文建模

上下文可以分为三类：

1. 语义上下文：不同场景中对象被发现的可能性不一样
2. 空间上下文：在不同位置发现对象的可能性不同
3. 尺度上下文：对象有一部分限制的大小和其他场景中的规模相关

Global context

根据图片或场景，global context可以作为检测对象的线索。

Local context

Local context考虑到了对象和其周围的区域。一般来说，在对一些对象之间的关系建模时要求不同类、位置、规模的边框是有逻辑的。在深度学习领域，相关模型的研究很有限，具有代表性的有SMN(Spatial Memory Network)、Object Relation Network、SIN(Structure Inference Network)。

检测方法

一个好的检测建议应该有以下几种特点：

1. 高召回，即只需一点建议就可以实现
2. 建议尽可能精确地匹配对象
3. 高效

边框建议法

对象分割建议法