1.FCN

1.1 CNN与FCN的比较

简单的说，FCN与CNN的区别在于FCN把CNN最后的全连接层换成卷积层，其输出的是一张已经标记好的图，而不是一个概率值。如下两图所示：
（1）在CNN中, 猫的图片输入到AlexNet, 得到一个长为1000的输出向量, 表示输入图像属于每一类的概率, 其中在“tabby cat”这一类统计概率最高, 用来做分类任务。
（2）FCN是对图像进行像素级的分类（也就是每个像素点都进行分类），从而解决了语义级别的图像分割问题。与上面介绍的经典CNN在卷积层使用全连接层得到固定长度的特征向量进行分类不同，FCN可以接受任意尺寸的输入图像，采用反卷积层对最后一个卷基层的特征图（feature map）进行上采样，使它恢复到输入图像相同的尺寸，从而可以对每一个像素都产生一个预测，同时保留了原始输入图像中的空间信息，最后奇偶在上采样的特征图进行像素的分类。如下图所示：
总结：
在传统的CNN结构中，前5层是卷积层，第6层和第7层分别是一个长度为4096的一维向量，第8层是长度为1000的一维向量，分别对应1000个类别的概率。FCN将这3层表示为卷积层，卷积核的大小(通道数，宽，高)分别为（4096,7,7）、（4096,1,1）、（1000,1,1）。所有的层都是卷积层，故称为全卷积网络。

1.2 三种上采样方法

经过全卷积化的网络后，我们会发现在整个过程中，原图象被进行了32倍的降采样。
但是FCN网络一般是用来对图像进行语义分割的，于是就需要对图像上的各个像素进行分类，这就需要一个上采样将降采样32倍的图像上采样到原图的大小。上采样对于低分辨率的特征图，常常采用上采样的方式将它还原高分辨率，这里陈述上采样的三种方法。

1.2.1 双线性插值上采样

简单来说，插值指利用已知的点来“猜”未知的点，一个分析帖。特点是不需要进行学习，运行速度快，操作简单。
单线性插值（一个方向上）就是知道两个点的值，并将两点连成一条直线，来确定中间的点的值，假设,现在有两点 （x1​,y1​）、（x2​,y2​）连成一条直线 [x1​,x2​]中的点就可以用线上的点表示。双线性插值（两个方向上）是一个三维的坐标系，因此，需要找到4个点来确定中心点坐标，如下图所示的例子：

已知的红色数据点和待插值的绿色数据点。咱们已知函数f在Q1,Q2,Q3,Q4四个点值，咱们想获得未知函数f在点P= (x,y) 的值。
第一步：X方向的线性插值，在Q12,Q22中插入蓝色点R2，Q11，Q21中插入蓝色点R1。

第二步 ：Y方向的线性插值 ,经过第一步计算出的R1与R2在y方向上插值计算出P点。

在x与y方向上，z值成单调性特性的应用中，此种方法能够作外插运算，便可以求解Q11~Q22所构成的正方形之外的点的值，计算正方形之外的点就是上采样的过程！！！

1.2.2 反卷积上采样

首先要记住把反卷积理解成逆卷积(Deconvolution)比较容易引起误会，把反卷积理解为转置卷积(Transposed Convolution)是一个更为合适的叫法.
(1)外围全补零（Full padding）反卷积

(2)插零分数步长反卷积
其实上面这种补0的方法事有问题的，你想一下，只在四周补0会导致最边上的信息不太好，那我们把这个信息平均下，在每个像素与像素之间补0,这就是插零分数步长反卷积

1.2.3 反池化上采样

反池化可以用下图来理解，
（1）在池化时需要记录下池化的位置，形成“池化索引”
（2）反池化时把池化的位置直接还原，其他位置填0。

注意：
反卷积与反池化之间最大的区别在于反卷积过程是有参数要进行学习的。
理论上反卷积可以实现反池化(UnPooling) ，只要卷积核的参数设置的合理。

1.3 FCN-跳层结构（Skip-layer）

首先为什么要做跳层呢？

我们看到5个卷积层之前已经有了32倍的降采样，而后面的6、7卷积层也是32倍的降采样，然后降采样之后直接通过双线性插值生成32倍，这个直接拿来做优化是有问题的，即直接使用32倍反卷积得到的分割结果粗糙。
这样的话就需要引入前面几个卷积层来做辅助，用以保证空间位置上的精确度，边缘区域分割的精确性。

如何实现跳层结构？
使用第4层和第3层输出的反卷积操作（分别需要16倍和8倍的上采样），再把这3个反卷积的结果图像融合，提升了结果的精确度：
• 跳层：Pool4和Pool3后会增加一个1x1卷积层做预测
• 较浅网络的结果精细，较深网络的结果鲁棒

注意如下图所示：
（1）在最后预测过程中的反卷积层是不用学习的，如1，2，3
（2）但是在融合两层信息的过程中的反卷积是要学习的，如4，5

1.4 FCN架构

具体操作：
1、 迁移学习AlexNet卷积层参数
以经典的AlexNet分类网络为初始化进行迁移学习。
最后两级是全连接层（红色），参数弃去不用。

2.第2步建立（FCN-32s网络）
•把全连接层替换为两个同深度的卷积层（4096,1,1）到->16x16x4096
•追加一个预测卷积层（21,1,1）->16x16x21
•追加一个步长为32的双线性插值反卷积层->500x500x21
这个过程就是从特征小图预测分割小图，之后直接升采样为大图。

3.第3步建立（FCN-16s网络）
•对最终层Conv7结果2倍上采样->34x34x21
•提取Pool4输出，追加预测卷积层（21,1,1）->34x34x21
•相加融合->34x34x21
•追加一个步长为16的双线性插值反卷积层->500x500x21

这个过程就是把升采样分为两次完成（橙色×2）, 在第二次升采样前，把第4个pooling层（绿色）的预测结果（蓝色）融合进来。使用跳级结构提升精确性。

4.第4步建立（FCN-8s网络）
•对上次融合结果2倍上采样->70x70x21
•提取Pool3输出，追加预测卷积层（21,1,1）->70x70x21
•相加融合->70x70x21
•追加一个步长为8的双线性插值反卷积层->500x500x21

这个过程就是把升采样分为三次完成（橙色×3）, 进一步融合了第3个pooling层的预测结果。

1.5 FCN训练参数

2.DeepLab V1

当前使用FCN解决图像分割问题是：
(1)原始FCN网络的输出低分辨问题,即重复的最大池化和下采样造成分辨率下降。
(2)分类器获得以对象为中心的决策需要空间不变性，从而限制DCNN的空间定位精度
针对这两个问题，DeepLab提出以下两点改进：

(1) 使用带孔卷积解决下采样问题。
(2) 使用Dense CRF解决空间不变形问题。

2.1 孔（Hole）算法–空洞卷积

空洞卷积最初的提出是为了解决图像分割的问题而提出的,常见的图像分割算法通常使用池化层和卷积层来增加感受野(Receptive Filed),同时也缩小了特征图尺寸(resolution),然后再利用上采样还原图像尺寸,特征图缩小再放大的过程造成了精度上的损失,因此需要一种操作可以在增加感受野的同时保持特征图的尺寸不变,从而代替下采样和上采样操作,在这种需求下,空洞卷积就诞生了

其实更简单的说：
由于普通下采样（max pooling）方法导致分辨率下降、局部信息丢失。但是我们有不得不用max pooling（因为每个像素有较大receptive field，且减小图像尺寸）。于是想使用另一种方法，不进行max pooling，但也能使每个像素有较大receptive field，这就是空洞卷积。

与正常的卷积不同的是,空洞卷积引入了一个称为 “扩张率(dilation rate)”的超参数(hyper-parameter)，该参数定义了卷积核处理数据时各值的间距。扩张率中文也叫空洞数(Hole Size)。

以3x3卷积核为例子：

a是普通的卷积过程(dilation rate = 1),卷积后的感受野为3
b是dilation rate = 2的空洞卷积,卷积后的感受野为5
c是dilation rate = 3的空洞卷积,卷积后的感受野为8
实际上就是在原图上，插入rate-1个0。

那么为什么空洞卷积可以增大感受野,但是可以不改变图像输出特征图的尺寸(分辨率,resolution)?
为了更好地理解这一点,我们从一维去分析容易理解点
从a和b可以看到，普通池化会丢失输出的特征信息，即降低特征图尺寸和分辨率，但是用密集池化虽然可以完善这一点，但是感受野很小，特征信息不够。
从b和c就可以看出,有无空洞卷积,并不影响输出特征图的尺寸,也就是说输出特征图的尺和空洞数无关,因此可以利用空洞卷积增大感受野,而输出特征图的尺寸可以保持不变。

总结就是以下三点优势：
（1）参数数量不变
（2）计算量不变
（3）高分辨输出

简单的特征总结：

如果扩张率太大了会发生什么？
显然，扩张率过大也不合适。给小图设置大的扩张率的副作用：对于 14×14 的输入图像，使用扩张率为 15 的3×3 卷积，其结果和常规的 1×1 卷积类似。
如下图：左侧为扩张率为14的3x3卷积，右侧为1x1卷积

空洞卷积有什么效果，和正常的降采样再上采样比较？

反卷积和空洞卷积的区别？
反卷积注意用于增大图像尺寸，核心是在原来图像上插入空白数据
空洞卷积是为了增大感受野，是对卷积核进行空洞，就是在卷积核插入空白数据

2.2CRF 条件随机场（可以对比一下graph cut）

2.2.1什么是条件随机场

1. 一例说明条件随机场是什么

假设你有贾斯丁·比伯一天生活的照片，你想要给每一张照片贴上一个标签，比如吃饭，舞蹈，睡觉，唱歌，驾驶等，该如何做？

一种方法是忽视照片的时间顺序特性，照片之间是相互独立的，训练数据有大量的照片和对应的标签，构建分类模型。比如训练数据包含近一个月的标签照片，你的分类模型可能会认为早上6点拍摄的黑色的照片是与睡眠相关的，有明亮色彩的照片往往与舞蹈相关，有汽车的照片与驾驶相关等等。

这种忽视时间顺序特性的方法会损失很多信息，比如，如果你看到一张嘴的特写照片，标签是唱歌还是吃饭？如果你考虑时间的顺序特性，假设前一张照片是吃饭或烹饪，那么这张照片的标签很可能是吃饭；若前一张照片是唱歌或舞蹈，那么这张照片的标签很可能是也唱歌。

因此，为了提高标签的准确性，我们应该考虑邻近照片的标签，这种方法就是条件随机场。

条件随机场的定义:
如上图所示，实际上条件随机场的应用场景是给定输入的随机变量X，预测随机变量Y。那么如何实现这个预测呢就要考虑两点（1）邻近 （2）MRF-马尔科夫随机场
(1)什么是邻近
如下为一个概率无向图模型：

变量y1的邻近点是y2,y3,y4,y5，变量y4的邻近点是y1,y6，变量y6的邻近点是y4。
所以其实邻近点的含义就是用无向边相连，存在相关的两个随机变量。

（2）什么是马尔科夫随机场？
马尔科夫随机场的本质是概率无向图，之所以叫马尔科夫随机场的原因是随机变量间满足成对马尔科夫性、局部马尔科夫性和全局马尔科夫性，马尔科夫性是关于条件独立的一种方法。
从本质上来说 马尔科夫随机场（MRF）对应一个无向图。此无向图上的每一个节点对应一个随机变量，节点之间的边表示节点对应的随机变量之间有概率依赖关系，即马尔科夫随机场是随机场的特例，假设某一个位置的赋值只与和它相邻的位置相关。

有以上两点知识以后：

我们可以认为条件随机场其实是马尔科夫随机场的特例，假设马尔可夫随机场只有X和Y两个随机变量，一般情况下，X是给定的，Y是输出。
形式化定义：设X和Y是随机变量，P(Y∣X)是给定X时Y的条件概率分布，若Y构成一个马尔科夫随机场，则 P(Y∣X)是条件随机场。
而在深度学习中：
对于每个像素i具有类别标签xi还有对应的观测值yi，这样每个像素点作为节点，像素与像素间的关系作为边，即构成了一个条件随机场。

2.2.2全连接条件随机场(FC-CRF)

那么什么是全连接随机场呢？
全连接条件随机场也叫做 Dense CRF，简单的说即图像中每个像素都与其他所有像素相关，为每个像素对都建立关系，但是问题在于，连接数量是像素数量的平方级别，这就导致了即使是很小的一幅图像，计算复杂度都会非常大，从而实用性不高。
以下这个帖子对该类进行了形象介绍：Dense CRF

2.2.3 FC-CRF在Deeplab的体现

作用：通过迭代精化分割结果（恢复精确边界）

CNN是一个逐步提取特征的部分，原始位置信息会随着网络深度的增加而减少或消失。CRF在传统图像处理上的应用是做一个平滑。CRF简单说，是在决定一个位置的标签（像素点的值）时，会考虑周围标签（像素点的值）。但是通过CNN得到的概率图在一定程度上已经足够平滑，所以短程的CRF没有太大的意义。于是考虑使用Fully connected CRF，这样就会综合考虑全局信息，恢复详细的局部结构，如精确图形的轮廓。CRF几乎可以用于所有的分割任务中图像精度的提高。
效果如下图所示，边界越来越精确：
第一行：飞机类别的分值（softmax之前）
第二行：飞机类别的概率值（softmax之后）
具体操作：
CRF是后处理，是不参与训练的，
（1）在测试时对特征提取后得到的得分图进行双线性插值，恢复到原图尺寸，（2）进行CRF处理，因为缩小8倍的，所以直接放大到原图是可以接受的。如果是32倍，则需要上采样（反卷积）。
如下图所示：

3.DeepLab v2

实际上针对 图像语义分割我们可以归结到以下三个挑战

Q1：传统分类DCNNs中连续的池化和下采样将导致空间分辨率明显下降，不利于图像分割

Q2：对象多尺度检测问题

Q3：以物体为中心的分类器，需要保证空间转换不变性 ，导致细节信息丢失

DeepLab v2 是在Deeplab v1 的基础上针对多尺度问题进行改进。具体如下：

(1)用空洞卷积（Atrous Convolution ）代替原来上采样的方法，比之前得到更高像素的score map，在不增加参数数量或计算量的情况下，有效地扩大感受野，以获得更多的上下文信息；和V1是一样的就是引入了空洞卷积。

(2) 全连接的CRF，利用低层的细节信息对分类的局部特征(边缘)进行优化。和V1是一样的

(3) ASPP(atrous spatial pyramid pooling) ：基于空间空洞金字塔池化的多尺度分割方法，即多尺度特征提取，在多个尺度上捕获对象和图像特征和语境；

如上所述真正改进的其实是第三点ASPP！！！！！

3.1 ASPP(atrous spatial pyramid pooling)-- Atrous空间金字塔池化

原理：我们知道“多尺度”技术对性能提升很大，如果有多个感受野，就相当于一种“多尺度”。

具体结构如图所示：

实际上就是通过不同的rate构建不同感受野的卷积核，用来获取不同尺度上的特征
如上图所示就是在Conv6层引入4个并行空洞卷积，分别Rate为6, 12, 18, 24
这样就会获取到4个不同的感受野：13x13, 25x25, 37x37, 49x49，然后得到四个尺度不同的特征信息

具体步骤是：
（1）特征经过pooling5以后到Conv6后，引入4个并行3x3空洞卷积进行多尺度特征融合
（2）后两层都用11卷积，最后进行融合（融合方式就是概率相加），如下图所示：

3.2 架构变化

主要关注上采样过程，原来的用传统深度网络即DCNN（FCN）的话，会把特征卷得很小很小（32倍），如图一圈中所示，所以要变成大特征即使用双线性插值的过程中，特征会损失很多！！所以我们对此进行进行优化，最后特征卷的不那么小，双线性插值后损失特征没那么多。

4. DeepLab V3 && DeepLab V3+

4.1 DeepLab V3 改进点

提出的串行和并行（atrous spatial pyramid pooling，ASPP）网络模块中包含了不同rates的atrous convolution处理与batch normalization layers，对于网络训练非常重要.
（1）无空洞卷积：
（2）串行空洞卷积：
（3）并行空洞卷积（相比V2加了BN层）
一个1×1卷积和3个3×3的空洞卷积(采样率为(6,12,18))，每个卷积核都有256个且都有BN层
包含图像级特征(即全局平均池化)

4.1 DeepLab V3+ 改进点

相比DeepLabv3，v3+引入了Decoder模块，其将底层特征与高层特征进一步融合，提升分割边界准确度。从某种意义上看，DeepLabv3+在DilatedFCN基础上引入了Ecoder-Decoder的思路，进一步保护物体的边缘细节信息。

可以看一下这个帖子总结一下语义分割的一些内容

4.补充知识：

4.1什么是正则化

首先：正则化要是理解成 规则化就更好理解了，为了避免过度拟合，所以才要加入了正则化
作用：就是向你的模型加入某些规则，加入先验，缩小解空间，减小求出错误解的可能性
一些介绍贴：
（1） 正则化为什么能防止过拟合（重点地方标红了） - alexanderkun - 博客园
[机器学习]正规化_for justice-CSDN博客_正规化
机器学习中正则化项L1和L2的直观理解_小平子的专栏-CSDN博客_l1和l2正则化

Leetcode

695. 岛屿的最大面积

继承一个图像渲染的方法，就是用队列实现广度搜索

class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) -> int:lenx=len(grid)leny=len(grid[0])#先遍历下来，找到一个1就开始渲染成0，直到渲染不到为止，然后比较面积大小direct=[(0,1),(0,-1),(1,0),(-1,0)]queue=[]maxarea=0for rx in range(lenx):for ry in range(leny):if grid[rx][ry] == 1:grid[rx][ry]=0queue.append((rx,ry))#渲染并且淹没陆地area=0while len(queue)>0:# print(queue)point=queue.pop()area+=1for i in range(4):nx=point[0]+direct[i][0]ny=point[1]+direct[i][1]if 0<= nx < lenx and 0<= ny < leny and grid[nx][ny]==1:grid[nx][ny]=0queue.append((nx,ny))print(area)if area>maxarea:maxarea=areareturn maxarea

617. 合并二叉树

很简单就是用递归实现检索二叉树，这里应该是是深度遍历

class Solution:def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:if not root1:return root2if not root2:return root1mergeRoot=TreeNode(root1.val+root2.val)mergeRoot.left=self.mergeTrees(root1.left,root2.left)mergeRoot.right=self.mergeTrees(root1.right,root2.right)return mergeRoot