英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
图像分割：图割方法综述
Faliu Yi 朝鲜大学计算机工程系
Inkyu Moon* 朝鲜大学计算机工程系
摘要：作为预处理步骤，图像分割可以将图像分割成不同的区域，在计算机视觉、物体识别、跟踪和图像分析中起着重要的作用。直到今天，有大量的方法能够从背景中提取所需的前景。然而，这些方法大多是基于边界或区域信息，在很大程度上限制了分割结果。由于graph cut基于图割的分割方法，因为该方法利用了边界信息和区域信息，所以得到了广泛的关注。此外，graph cut基于图割法的能量函数可以达到全局最优的结果，是一种有效的、被广泛接受的方法。它不仅对已知图像的特定图像有希望，而且对于没有任何已知信息的自然图像也是有效的。对于N维图像的分割，基于图割的方法也是适用的。由于图形切割的优点,人们已经提出了各种方法。本文的主要目的是帮助研究人员更容易理解基于图形分割的分割方法。我们还将此方法分为三类。它们是基于图形切割、基于交互的图形切割和基于形状先验的图形切割。本文将有助于那些想要将图形切割方法应用到他们的研究中的人。
关键词：图像分割，N维图像，能量函数，图割，测量。
- 简单介绍
图像分割是将图像分割成不同的区域，这些区域可能具有相似的颜色、强度或纹理[1-2]。分割作为一个预处理步骤在计算机视觉、目标识别、跟踪和图像分析中起着重要的作用。传统上，分割可以分为五类。第一种是基于阈值的分割方法[2, 3]。该方法通常将图像分为前景和背景两部分。当像素的强度大于（小于）预定阈值时，这些像素被分类为前景。否则，它们将被视为背景。在现有的分割方法中，基于阈值的方法是最直接、最简单、最快速的方法。困难的是，不容易找到合适的阈值，可以直接将图像分成两组。该方法还要求图像中的前景和背景具有明显不同的强度值。Otsu算法[1]是寻找合适阈值的最常用方法。Otsu的算法可以找到一个阈值，使部分（前景和背景之间）方差最大且内部（前景或背景内）方差最小。第二类是基于边缘的分割方案[1-3]。该方法假设前景和背景的像素值是不同的。这些不连续性通常通过梯度或拉普拉斯[2-4]的一阶或二阶导数方法来检测。Sobel、Roberts和Rewitt边缘检测器[1, 4, 5]是基于梯度概念的，易于实现，并且可以大致检测轮廓轮廓，但它们对图像噪声敏感。拉普拉斯算法[2-5]使用二阶导数来检测边缘，该算法可以沿着边缘定位像素的方向，但是它也对噪声敏感。引入高斯的拉普拉斯算子，利用高斯滤波器平滑图像，然后再利用拉普拉斯算子。Canny边缘检测器与以前的相比具有更好的检测结果，因为该方法结合了滤波、增强和检测的操作[4-5]。尽管物体的边界可以通过这些方法来检测，但仍然会包含许多假边缘。因此，基于边缘的分割通常需要后处理操作。第三类是基于区域的分割[2, 3, 6 ]。典型的算法是区域生长和区域分裂合并[1 ]。对于区域生长方案，首先需要确定一组种子。然后，通过类似的强度、颜色或纹理，通过预定义的标准将相邻像素分组到这些种子。因此，当已知先验信息时，种子点的选择技巧对于区域生长是非常重要的。对于区域分裂合并方法，首先将图像分割成一系列小区域。然后通过一个先决条件合并或分割这些较小的区域。这个过程简单点讲就是将图像分割成许多未重叠的区域，直到它不能被分割为止。然后，合并满足预定义条件的相邻区域。基于区域的分割强烈依赖于对象和背景的强度值，并且总是对提取的对象产生非光滑边界。第四类是基于分水岭的分割[1, 2, 3，7]。该方法将图像视为拓扑曲面，将强度值视为高度。图像中的区域极小值被解释为汇水盆地，每两个相邻流域之间的最大值被视为脊线。基于分水岭的分割是在图像中寻找被称为分水岭的脊线。因此，为了提取目标，通常将分水岭变换算法应用到梯度图像中，其中目标对应汇水盆地，而边界对应分水岭。然而，直接应用的分水岭算法将因为噪声和其他局部不规则的梯度而造成过分割问题[1 ]。为了减少过分割，提出了标记控制的分水岭分割方法。在该方法中，区域极小值只发生在标记的位置。因此，关键的过程是识别包括内部和外部标记的标记物。内部标记表示对象，外部标记表示背景，这些外部标记必须连接在一起。当适当地识别标记物时，基于分水岭的分割可以得到合理的结果。第五类是基于能量的分割。这种方法需要建立一个目标（能量）函数，当图像被分割成期望的结果时，它将达到最小值。Live wire [8], active contour [9], level sets [10-11] and graph cut [12-13]都属于这一类。对于Live wire，种子需要由用户识别，这些种子必须位于目标边界。然后通过最小化构造能量函数对边界位置进行优化。对于active contour和level sets，需要给出初始边界。当边界以预定义规则演化时，提取合理的边界，使能量函数具有最小值。然而，active contour和level sets仅利用边界信息，并且对初始边界非常敏感。此外，它们不能保证获得全局最优结果，因为它们将收敛于局部最小值。对于graph cut，基于区域和边界信息构造能量函数，实现全局最优的结果。图切割分割首先由Boykov和Julle[12]在2001提出。自那时以来，许多基于图形切割的方法被开发出来，这些方法被广泛应用于医学图像、视频和自然图像分割[12—22]。在本次调查中，我们将首先关注图形分割的概念。然后，我们将介绍几种常用的方法，即加快图形切割的计算、交互式分割和结合形状先验信息的图形分割。
论文的其余部分按如下方式组织。在第2节中，我们描述了基于图形分割的概念。在第3节中，我们提出了基于图割算法的分类。在第4节中，我们总结了本文。
二．图形分割
在这一节中，我们将介绍图割的概念，以及如何用给定的图像来建立图，该图将被图割分割。
- 图割
无向图可以表示为：G=lt;V,Egt;，这里的V表示顶点，E表示为图中相邻两个顶点的边。顶点V由两种不同的节点（顶点）组成。第一类顶点是对应于像素的邻域节点，而另一类顶点称为由s（源）和t（汇）组成的终端节点。这种图也称为s-t图，其中图像s节点通常表示对象，而t节点表示背景。在这种图中，也有两种类型的边。第一类边称为n-links，是图中相邻顶点(相邻图像像素)连接形成的边；第二类边称为t-links，是终端顶点(s，t)与相邻顶点连接形成的边。在图中，每个边都附一个非负权值(也可以表示为cost)，表示为:。一个割可以看做是边集E的子集，表示为C。一个割的代价表示为：
（1）
最小割是具有最小代价的割，它可以通过找到最大流来实现，这在[12, 13, 23]中被验证，最小割相当于最大流。Boykov和Kolmogorov[23]开发的最大流/最小割算法可用于得到s-t图的最小割集。因此，该图由这个割分开，并且节点被分离成两个不相交的子集S和T，其中,且。这两个子集对应于图像分割中的前景和背景。这种图形可以在图1中描述。
|
|
|
图1.s-t图的说明,图像像素对应于图中的相邻节点（除s和t节点之外）。图中的实线是n-link，虚线是t-link。 |
- 图割分割
图像分割可视为像素标记问题。对象（S节点）的标签被设置为1，而背景（T节点）的标签被赋予为0，并且这个过程可以通过最小化图切割的能量函数来实现。为了使分割合理，应该在对象和背景之间的边界处进行切割。也就是说，在物体边界处，割的能量应该被最小化。设，其中p是图像中的像素数且。因此，集合L被划分为2个部分，标记为1的像素属于对象，而其他被分组为背景。能量函数定义为以下方程，该方程可通过s-t图中的最小割来最小化[12-13]。
(2)
其中，R（L）被称为区域项，它将区域信息融入到分割中，而B（L）称为边界项，将边界约束融入到分割中，alpha;是区域和边界项之间的相对重要因素。当alpha;被设为0时，意味着忽略了区域信息，只考虑了边界信息。在式（2）中的能量函数中，区域项定义为以下方程。
(3)
其中，是将标签分配给像素P的惩罚。通过比较像素p的强度与对象和背景的给定直方图（强度模型），可以得到的权重。t-link的权重定义为以下方程[12-13]。
(4)
(5)
从等式（4）和（5），我们可以看到，当大于时，将小于。这意味着当像素更可能成为对象时，将像素分组成对象的惩罚应该更小，这可以减少等式(2)中的能量。因此，当所有的像素被正确地分离成两个子集时，区域项将被最小化。等式（2）中的是边界项，其定义为以下方程[12-13]。
(6)
其中p，q是相邻像素，定义为：
(7)
对于区域约束，它可以被解释为将标签分配给相邻像素。当相邻像素具有相同的标签时，惩罚为0，这意味着区域项仅在分割边界处加和惩罚。对于，定义为的非递增函数如下〔24〕：
(8)
其中，可以将sigma;视为摄像机噪声。当两个相邻像素的强度非常相似时，惩罚非常高。否则，它是低的。因此，当能量函数获得最小值时，更可能发生在对象边界处。在〔12, 13〕中，Boykov和Jolly表明最小能量可以通过最大流最小割来计算。因此，最小能量问题被转换成图切割问题。为了得到一个合理的分割结果，在s-t图中赋权是非常重要的。在Boykov和Jolly方法中，给出了s-t图的权重如下：
（9）
式（9）也可以解释为，在s-t图中，当像素的强度倾斜为对象时，该像素和S节点之间的权重将大于像素和T节点之间的权重，这意味着在更小的权重的边缘处更容易发生切割。对于相邻像素，当它们的强度非常相似时，权重非常大，不可能被切割分开。因此，当在s-t图实现最小切割时，切口的位置接近对象边界。图切割的实现可以通过在[12, 13, 23 ]中描述的最大流/min切割来实现。在图2中，我们说明了3times;3图像分割的图割。边的宽度表示权重的大小。
|
|
|
图2.图解图割用于图像分割。切割对应于式(2)的最小能量。 |
三．基于图割算法的分类
在本节中，我们将基于图割的技术分类为三类。第一种是基于加速的图割，其目的是提高基于图割的方法的速度。第二种是基于交互的图割，将用户的交互融入到分割中，从而提高分割结果。最后一种是基于形状先验的图形切割，它考虑了对象的形状先验，使得分割更加合理。接下来，我们逐一介绍这些技术。
A.基于加速的图割算法
为了加快图形切割算法的计算，在文献[25 ]中提出了一种基于GPU的CUDA码的实现方法。这种方法是通过并行计算来实现加速，与顺序计算相比具有良好的性能。然而，用于减少图割相关算法的计算时间的最常用的方法是基于图重建过程中的图形节点的减少[14-16，26-228 ]。传统上，图像中的每个像素将被视为图中的一个节点。因此，随着图像分辨率的提高，图将非常大，使得图形的计算速度变慢。由于大多数情况下，对象只占据整个图像中的一个小区域，所以可以只考虑覆盖目标的相对较小的部分来分割对象[26-28]。在这种情况下，由于图像尺寸在一定程度上减小，因此减小了图的大小。较小的区域可以通过用户的输入或一些匹配算法来选择[26-28 ]。此外，对于图像，当两个相邻像素的强度值非常相似时，图中相应的权重将非常重，这意味着它们不会被图割分开。换句话说，当两个相邻像素的强度值非常相似时，它们可以被视为一个像素。这种思想产生了聚类方法在图割中的应用。图割中最常用的方法是分水岭算法[14, 16, 26]。通常将分水岭算法应用于梯度图像。在分水岭算法中，梯度图像被视为拓扑表面，梯度值被视为高度。当在拓扑表面的每个区域极小值上钻孔并将其放入水中时，水将从每个孔喷出。可以保留水的地方称为集水盆地。当两个相邻的集水盆地的水趋于合并时，在它们之间建造了一个水坝。在整个表面浸入水中后，左边的水坝是分水岭。因此，具有相似强度值的较小区域可以通过分水岭分组为一个簇，并且在图割的图形重构中将这些簇作为节点。在分水岭的预分割后，将每个簇的平均强度视为原始图像中由许多相似像素组成的新点（超点）的像素值。因此，可以通过将超点的值与所建立的对象和背景相似的直方图与等式（4）和（5）进行比较来设置t-link的权重。在文献〔26〕中，n-link的权重由下列方程给出。
（9）
其中，梯度J（I）是簇I的平均梯度幅度，而J是它的相邻簇。由于分水岭算法可以产生许多小的聚类，并且这些簇之间的边界总是能够保持原始图像中的原
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[22164]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
