计算机视觉-图像分割

计算机视觉——图像分割【本学期选修国科⼤⾼伟⽼师的计算机视觉课程，本⼈⽅向也是cv，因此想通过博客⽅式记录课程中⽐较重要的点，巩固并且进⾏⼀些扩展学习】【本章节内容针对图像分割进⾏讲解】接下来我们将主要针对以下内容进⾏介绍：早期的图像分割⽅法基于特定理论的⽅法：MeanShift、NormalizedCut、GraphCut基于深度神经⽹络的图像分割：FCN、SegNet、R-CNN⼀.早期图像分割⽅法：1.阈值法*2.区域⽣长法3.分裂合并法4.基于边缘的分割⽅法*5.等等这边重点介绍加粗变红部分。1.1阈值法基本原理：通过设定不同特的征阈值，把图像像素点分为若⼲类。常⽤的特征包括：灰度、彩⾊特征、由原始灰度或彩⾊值变换得到的特征。上图T值便是我们设置的阈值。但是如果遇到灰度级集中的情况，简单的设置阈值往往达不到很好的效果。如下图左边灰度级过于集中；或者右边应为光圈问题，在后期提取情况造成了很⼤的偏差。针对此，我们引⼊了1.2局部阈值法：基本原理：将图像分块，分别⽤全局阈值⽅法分割，最后再综合。1.3基于边缘的分割⽅法:基本步骤:1）检测边缘2）根据边缘将图像分割成不同的区域⽐如我们需要完成以下任务：在只有0-1灰度级的图中，我们想要捕捉-45度的线。解决⽅案：引⼊⼀个算⼦，表⽰-45度的斜线，在通过阈值来保存我们所需要的线。Hough⽅法图像中检测直线的⼀种⽅法，该⽅法也可以检测其他参数化的物体，⽐如圆或者椭圆等。该技术在1959年最早由PaulHough提出。)的直线可以表⽰为yi=a*xi+b,在不同的a、b的条件下，直线存在⽆数条。同样，若将a、b看成是变量，则可以表⽰为b=-xi*a+yi，对应a-b空间的⼀条线。若此时想要利⽤a-b空间找到左图同时过两个点的线，可以通过右图相加的点找到对应的a0和b0来确定该条直线。但是存在⼀个问题：若直线垂直于x轴，这意味着a值趋向于⽆穷⼤。因此针对该现象，我们引⼊了极坐标：其中相交的点便是我们寻找的条件。⼆.基于特定理论的⽅法：(Clustering聚类⽅法为主)2.1K-Means步骤如下：1.确定聚类（cluster，也称簇）中⼼的个数K，并为它们随机初始化⼀个各⾃的聚类质⼼点。2.根据每个数据点到质⼼的距离来进⾏分类，加⼊新的可加⼊的最近的数据点。3.针对加⼊的新数据点，重新计算每⼀聚类中所有向量的平均值，并确定出新的质⼼。4.重复2-3步骤，进⾏⼀定次数的迭代，直到质⼼的位置不再发⽣太⼤变化。优缺点：优点：速度快，时间复杂度O(n)。缺点：如何⼀开始就确定聚类个数K；⼀开始质⼼点的选取是随机的，质⼼点的位置不可重复且缺乏⼀致性。K-Means效果图2.2⾼斯混合模型（GMM）其是指多个⾼斯分布函数的线性组合，⽤两个参数来描述聚类的形状：均值和标准差。以⼆维分布为例，标准差的存在允许聚类的形状，相⽐如K-Means算法,更加灵活地对点进⾏分类。在图像上可表⽰为多类型的椭圆，⽽不再限制于圆形（K-Means）。如果数据点符合某个⾼斯分布，那它就会被归类为那个聚类。为了找到每个聚类的参数，EM算法【WuX,KumarV,QuinlanJR,etal.Top10algorithmsindatamining[J].Knowledgeandinformationsystems,2008,14(1):1-37.】在这⾥极为重要！EM算法是⼀种迭代优化策略，由于它的计算⽅法中每⼀次迭代都分两步，其中⼀个为期望步（E步），另⼀个为极⼤步（M步），所以算法被称为EM算法（Expectation-MaximizationAlgorithm）。基本思想：⾸先根据⼰经给出的观测数据，估计出模型参数的值；然后再依据上⼀步估计出的参数值估计缺失数据的值，再根据估计出的缺失数据加上之前⼰经观测到的数据重新再对参数值进⾏估计，然后反复迭代，直⾄最后收敛，迭代结束。缺点：与K-Means相⽐，GMM每⼀步迭代的计算量⽐较⼤。基于EM算法，有可能陷⼊局部极值，需要经过多次迭代。2.3Mean-Shift1975年，Fukunaga和Hostetle提出了⼀种基于⼀般核函数的⾮参数密度梯度的估计算法，并给出了保证估计值与真实值之间渐近⽆偏、⼀致和均匀连续时核函数应满⾜的条件。1999年，Comaniciu将均值移动应⽤于图像分析。核⼼思想:找到概率密度梯度为零的采样点，并以此作为特征空间聚类的模式点。【如上图绿⾊画圈范围中，红点所在区域密度更⼤，会使得该聚类点往红点迁移，⾄密度不变，也就是梯度为零情况。】优缺点：优点：与K-Means⽅法的最⼤优点是⽆需指定聚类数⽬K，聚类中⼼处于最⾼密度处，也符合直觉认知。缺点：如何正确选择窗⼝尺⼨h，不同的尺⼨会引⼊不同的计算结果。【如上图中间便是h过⼤，最右边是h过⼩的结果。】2.4图割基本思想：1.将图像⽤图的⽅式表⽰，顶点表⽰像素，边表⽰像素之间的关系。图像分割对应图的割集。2.确定图中边的权值，使图像分割⽬标（能量最⼩化）对应图的最⼩割。3.⽤最⼤流算法求解最⼩割问题。为了更好的学习相关内容，我们先针对图论相关知识进⾏系列学习。【⽆向图和有向图】S-T图1.有源节点（s）和终节点（t）2.每条边有⼀个⾮负的容量Cap(i,j)3.对于不存在的边，其容量为0【若s和t由线分割则为s-t割，反之为⾮s-t割】最⼩割：割线所经过权值最⼩图割在图像分割中的应⽤：1.Normalizedcut及其在图像分割中的应⽤2.graphcut算法求解计算机视觉中的能量极⼩化问题2.4.1Normalizedcut(归⼀化分割)⼀般的分类问题：给定⼀个点集V，按照⼀定的相似度量（距离）寻求⼀种划分，将点集V划分成不相交的若⼲⼦集合V1,V2…Vm。使得每⼀⼦集内部的相似度尽量⾼，⽽⼦集之间的相似度尽量低。在图论解决分类问题上，我们可以先使⽤⼀个⽆向赋权图来表⽰。考虑⼆分类问题：将点集V分成不相交的两部分A、B。则两类别之间的相似性我们可以⽤图割来度量。【cut取最⼩】需要注意的是：仅考虑⽤割集的权值之和来度量两个集合之间的相关性，会容易出现孤⽴分割的问题。如下图所⽰：这时候就引⼊了Normalizedcut，定义⼀个新的类间相似性度量。其中：【V为全部点】同理，新的类内相似性度量：简单推导可得：Ncut(A,B)=2-Nassoc(A,B)可见最⼩化类间相似性和最⼤化总类内相似性是等价的。这样就解决了划分准则的问题，即:最优划分对应于最⼩Ncut通过求最⼩Ncut，就可以得到最优划分。不幸的是求⼀个图的Ncut是⼀个。Normalizedcut在图像分割中应⽤具体过程：将⼀幅图像上所有像素点看作点集V，每两个点之间都建⽴⼀条边，得到边集E。为每条边按下⾯⽅法赋权。这样就建⽴⼀个赋权⽆向图G=(V,E)按照前述算法，我们就可以完成对该幅图像分割操作。2.4.2⽤graphcut求解能量极⼩化问题计算机视觉的很多问题可以看作⼀个最优标记（labeling）问题，如：我们构建如下能量函数来得到最优标记准则：f:P-L的映射。P是像素点集，L是标记集。Data项表⽰给每个像素点赋予标记（label）的代价Smooth项表⽰每两个相邻的像素分别赋予标记和的代价【Graphcut与能量函数的对应关系】两标记问题：对于两标记问题，最⼩能量对应于图的最⼩割。图论中已有经典的算法，可以求得⼀个图的最⼩割，从⽽得到极⼩能量。多标记问题：当标记数量⼤于2时，已经证明该问题是NP-hard问题。故很难求得