快速检索        
  武汉大学学报·信息科学版  2017, Vol. 42 Issue (7): 877-883

文章信息

王平, 魏征, 崔卫红, 林志勇
WANG Ping, WEI Zheng, CUI Weihong, LIN Zhiyong
一种基于统计学习理论的最小生成树图像分割准则
A Image Segmentation Method Based on Statistics Learning Theory and Minimum Spanning Tree
武汉大学学报·信息科学版, 2017, 42(7): 877-883
Geomatics and Information Science of Wuhan University, 2017, 42(7): 877-883
http://dx.doi.org/10.13203/j.whugis20150345

文章历史

收稿日期: 2015-09-12
一种基于统计学习理论的最小生成树图像分割准则
王平1, 魏征1, 崔卫红2, 林志勇2     
1. 国家海洋局南海规划与环境研究院, 广东 广州, 510300;
2. 武汉大学遥感信息工程学院, 湖北 武汉, 430079
摘要:根据基于区域增长的面向对象图像分割的本质特点,将统计学习理论与最小生成树算法相结合,提出了一种基于统计学习理论的最小生成树图像分割准则。将该图像分割准则应用于多种遥感影像数据进行分割实验,其结果表明基于统计学习理论的最小生成树图像分割准则能通过简便的参数设置,即可以较好地实现不同尺度目标的图像分割,同时又能对纹理区域进行有效分割,能获得良好的区域边界和较好的抗噪声性能,并在海岸带大比例尺无人机正射影像的图像分割实践中得到了较好验证。
关键词统计学习     最小生成树     图像分割准则    
A Image Segmentation Method Based on Statistics Learning Theory and Minimum Spanning Tree
WANG Ping1, WEI Zheng1, CUI Weihong2, LIN Zhiyong2     
1. South China Sea Institute of Planning and Environment Research, the State Oceanic Administration, Guangzhou 510300, China;
2. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China
First author: WANG Ping, senior engineer, specializes in marine remote sensing and GIS applications, marine resources development and protection. E-mail:1903125@qq.com
Corresponding author: WEI Zheng, PhD, engineer. E-mail: weizheng0628@foxmail.com
Foundation support: The Public Science and Technology Research Funds Projects of Ocean, No. 201305020-7; the Open Research Fund Program of Shenzhen Key Laboratory of Spatial Smart Sensing and Services(Shenzhen University), No. 201302; the Director Fundation of South China Sea Branch of the State Oceanic Administration; the National Natural Science Foundation of China, No. 41101410; the Natural Science Foundation of Hubei Province, No. 2011CDB273
Abstract: According to the essential feature of object-oriented image segmentation method, this paper explores a minimum span tree (MST) based image segmentation method. We define an edge weight based optimal criterion (merging predicate) which based on statistical learning theory (SLT), a scale control parameter is used to control the segmentation scale. Experiments based on the high resolution UAV images show that the proposed merging predicate can keep the integrity of the objects and do well on preventing over segmentation. It also proves its efficiency in segmenting the rich texture images while can get good boundary of the object.
Key words: statistical learning     minimum spanning tree (MST)     image segmentation rule    

图像分割的最终目的是使分割所得区域具有区域内相似性最大、区域间相似性最小,是典型的聚类、最优化问题。图论作为数学的一个分支,以由若干顶点和与顶点相连的边构成的图为研究对象,这样的图可以用来描述某些事物之间的关系,用顶点代表事物,用边表示顶点所对应两事物之间的关系。基于图论方法的图像分割算法已应用于医学图像的分割(运动分割、纹理分割、目标分割[1-6])等领域,并取得了很多成果。该类方法将图像映射为带权图,把像素或区域视作顶点,图的每一条边连接两个像素或区域,每条边被赋予权重,权重反映了像素或区域之间的相似性,然后利用图论最优化理论得到图像的最佳分割,其本质是将图像分割问题转化为图论的最优化问题,通过代价函数最小化实现图像分割。

1 基于最小生成树的图像分割

基于图论的图像分割方法主要考虑到反映区域特征的代价函数、图的最优划分准则和有效的优化算法等3个方面的影响[1-12]

1.1 最小生成树图像分割思想

图论中的最小生成树问题就是寻找边权和最小的生成树,每个树都是一个连通图,因此,寻找差异最小的连通区域的图像分割问题就可以转化为最小生成树问题。基于最小生成树的图像分割主要有自顶向下分裂最小生成树与自底向上合并生成多个最小生成树两种策略。基于自顶向下的分割策略是在图像图模型构造完成的基础上首先按最小生成树算法得到一个连通整个图像的最小生成树,然后按一定准则分裂最小生成树,该过程对于图像分割来说,特别是大图像,将增大计算量,因此,本文采用自底向上(合并即区域增长)策略实现基于最小生成树的图像分割,称之为构造最小生成树方法。

1.2 基于构造最小生成树的图像分割

基于构造最小生成树的图像分割方法是在构建影像图模型的基础上,采用自底向上(合并)策略,用最小生成树算法按照一定准则来构造生成多个符合准则的最小生成树,每个最小生成树代表一个连通区域,如传统的固定阈值算法、单连接算法、完全连接算法等。该分割算法实现过程描述如下。

1) 以图像中每个像素为顶点,邻接的两个像素之间有一条边相连,通常为四邻域或八邻域,边权值按两顶点对应特征向量的不相似测度计算得到,构建图模型。图 1(b)图 1(a)按八邻域构建的图模型,每个黑点代表对应图像中的一个像素,线上的数字为像素灰度差绝对值得到的边权值。

图 1 基于图模型最小生成树的影像分割 Figure 1 Image Segmentation Based on Minimum Spanning Tree of Graph Model

2) 用最小生成树算法,如用Kruskal算法,将边按权值非递减顺序排列,从最小权边开始构造最小生成树。

3) 若当前边权值满足分割准则(如小于设置的全局阈值)时将其加入生成树,否则不加入。

4) 重复步骤3),直到当前边权值不满足准则(如大于所设阈值)。图 1(c)1(d)为选取不同全局阈值时得到的分割结果。其中,图 1(c)为阈值11时得到的分割结果,得到两个最小生成树;图 1(d)为选取10为阈值时得到的分割结果,得到3个最小生成树,即将图像分割成3个区域。

结果表明,基于简单阈值分割准则的结果对噪声敏感,特别是当阈值设置不合理时会产生很多孤立点。由图 1(d)可以看出,由于阈值减小会产生孤立点,随着阈值递减会产生更多孤立点。因此,要采取相应措施将这些孤立点合并到与其最相似的区域。一般可以按边权值非递减顺序将这些孤立点合并到与其邻接的差异最小的像素所在区域。

基于最小生成树的分割算法从差异最小的像素开始合并,避免了区域增长中的种子点选择问题,可以达到全局最优,但简单阈值准则对噪声敏感,容易产生孤立点;在合并过程中,仅根据边权值大小进行合并,与原始数据有关。当然,也可以考虑在算法实现和准则设置中将原始数据及其邻域关系考虑进来,但这样将会增加计算复杂度,因此,设计合理的边权构造函数和合并准则非常重要。

2 基于统计学习理论的合并准则

由于遥感影像具有内容复杂、纹理丰富的特点,因此在很多分割算法中都存在过分割现象,而实际上,大区域目标具有一定的统计特性,充分利用该特点进行分割将有利于减少过分割现象。影像分割过程是寻找同质区域的过程,可以认为是一个不断学习判断的过程。基于最小生成树算法的图像分割是树不断增长的过程,可以被看作是从少量相似样本开始不断寻找同类目标的过程,即依据少量样本学习的过程,而这正是统计学习理论中学习的强项。因此,应用统计学习理论来进行图像分割准则设置是可行的。本文将图像分割看作是一个回归估计问题,并将经验风险最小化问题转化为一个概率问题,研究并提出了一个基于经验风险最小化的β一致稳定学习算法的最小生成树分割准则,该准则只考虑边权特性,避免其他复杂运算。

2.1 β一致稳定学习算法

统计学习理论是研究小样本情况下的机器学习理论,把学习问题看作是利用有限数量的观测来寻找待求的依赖关系的问题,从而对未知数据进行预测或对其性质进行判断。学习的目的就是从给定的函数集f(x, α), αΛ(Λ是参数集合,即任意函数集)中选择出能最好地逼近训练器响应的函数。这种选择是基于训练集S的,训练集S是根据联合分布抽取出的l个来自独立同分布的X×Y的样本(观测值):(x1, y1), …,(xl, yl)。

联合分布为:

$ P\left( {x,y} \right) = P\left( {y|x} \right) \times P\left( x \right) $ (1)

式中,P(y|x)为yx的条件概率;P(x, y)为一个确定但未知的量。若从训练集S学习得到一个函数fS,则对于一个新的xxnew,它可以预测出相应的y值:

$ {y_{{\rm{pred}}}} = {f_S}\left( {{x_{{\rm{new}}}}} \right) $ (2)

为了清楚地阐述推导过程,首先给出与其相关的几个概念与定理。

1) 损失函数。利用L(f(x), y*)表示付出的代价,称为损失函数。回归常用的损失函数为平方损失或称为L2损失:

$ c\left( {f,z} \right) = L\left( {f\left( x \right),{y^ * }} \right) = {\left( {f\left( x \right) - {y^ * }} \right)^2} $ (3)

其中,z=(x, y)。

2) 泛化误差。D[fS]=I[fS]-IS[fS]为泛化误差,其中IS[fS]为经验风险,I[fS]为期望风险,即n→∞时的损失。当l→∞时,D[fS]→0。

本文采用算法的稳定性来获得泛化误差界,这种方法只是关心算法产生的那一个泛化误差界大于某值的概率,即有:

$ {P_S}\left( {\left| {{I_S}\left[ {{f_S}} \right] - I\left[ {{f_S}} \right]} \right| > \varepsilon } \right) < \delta $ (4)

3)β一致稳定性算法[1]。给定一个训练集S,定义Si, z是一个新的训练集,其中S中的点i被新的点zZ替换,称算法A具有β一致稳定性(即β-稳定)。

Bousquet和Elisseeff[1, 2]通过McDiarmid[11]不等式证明得到如下泛化误差界的概率:

$ \begin{array}{*{20}{c}} {\Pr \left( {\left| {{I_S}\left[ {{f_S}} \right] - I\left[ {{f_S}} \right]} \right| > \beta + \varepsilon } \right) \le }\\ {2\exp \left( { - \frac{{l{\varepsilon ^2}}}{{2{{\left( {l\beta + M} \right)}^2}}}} \right)} \end{array} $ (5)

式中,l为样本数;M为损失上界。

对于一致稳定性算法,β=k/l(k为常数)是“足够好的”,利用β=0,并以概率1-δ,有:

$ I\left[ {{f_S}} \right] \le {I_S}\left[ {{f_S}} \right] + M\sqrt {\frac{{2\ln \left( {2/\delta } \right)}}{l}} $ (6)

至此,得到了泛化误差的界与损失界、样本数以及概率1-δ的关系式。

2.2 合并准则设计

本文将影像分割看作是一个预测学习过程,预测一个像素或区域是否应该被合并到另一个区域,并将其看作是一个回归问题。寻找一个算法fS使得对每一个输入xi都有一个输出yi。这里假设一个同质区所有像素灰度值都是属于某一概率分布P的独立随机变量(x1, y1), …, (xl, yl)序列对来自于Pxi是观测到的灰度值,即影像像素灰度值。yixi对应的真实值,y*是同质区的真实灰度值。可以设想所有被合并到同一区域的像素具有fS(xi)=xi=yi=yi*=y*,这意味着该区域的IS[fS]=0,可以将基于最小生成树的影像分割问题转化为式(6) 所描述的概率问题。

考虑到Kruskal最小生成树算法的第一步是将边按权值非递减顺序排序,也就是说它从连接两个最相似像素的最小权边(权值可能为0,表示两个像素具有相同灰度值)开始构造MST,因此,我们将该像素点的灰度值看作是同质区域的真实值,随着MST的增长,加入MST的边权值在增加,最后被加入的边的权值反映了观测区域的最大损失,对于MST,有:

$ n\left( {{\rm{MST}}} \right) = e\left( {{\rm{MST}}} \right) + 1 $

式中,n(MST)表示MST包含的顶点数;e(MST)表示MST的边数。

根据损失函数式(3) 可以发现,边权函数实际就是损失函数,在预测过程中,I[fS]是n→∞时的损失:

$ I\left[ {{f_S}} \right] = \mathop {\lim }\limits_{n \to \infty } \frac{1}{n}\sum\limits_{i = 1}^n {L\left( {f\left( {{x_i}} \right),y_i^ * } \right)} = \mathop {\lim }\limits_{n \to \infty } \frac{1}{n}\sum\limits_{i = 1}^{n - 1} {{w_i}} $

式中,n是区域像素数,即MST的顶点数。

根据式(5) 和式(6),将式(5) 重写为:

$ \Pr \left( {\frac{1}{n}\sum\limits_i^{n - 1} {{w_i}} \le M\sqrt {\frac{{2\ln \left( {2/\delta } \right)}}{n}} } \right) \ge 1 - \delta $ (7)

S1S2代表两个区域(MSTs),n1n2表示区域S1S2中的像素数(顶点数),w1i(i=1, 2, …, n1)和w2i(i=1, 2, …, n2)是S1S2的边权值,wc是当前连接区域S1S2边权,用它来判断区域S1S2是否应该合并。用IS1IS2分别表示区域S1S2的经验风险:

$ {{I'}_{{S_1}}} = \frac{1}{{{n_1}}}\left( {{w_c} + \sum\nolimits_{i = 1}^{{n_1} - 1} {{w_{1i}}} } \right) $ (8)
$ {{I'}_{{S_2}}} = \frac{1}{{{n_2}}}\left( {{w_c} + \sum\nolimits_{i = 1}^{{n_2} - 1} {{w_{2i}}} } \right) $ (9)

根据式(7) 可以定义如下合并判决准则1:

$ P\left( {{S_1},{S_2}} \right) = \left\{ \begin{array}{l} {\rm{True,}}\;{{I'}_{{S_1}}} \le M\sqrt {\frac{{2\ln \left( {2/\delta } \right)}}{{{n_1}}}} ;{{I'}_{{S_2}}} \le M\sqrt {\frac{{2\ln \left( {2/\delta } \right)}}{{{n_2}}}} \\ {\rm{False,其他}} \end{array} \right. $ (10)

该准则说明,如果当前边连接的两个区域合并后的经验风险均不超过其各自的泛化误差界,则返回TRUE,可以合并,否则不能合并。

从式(8) 和式(9) 可以看出,经验风险是区域中边权和的均值,在合并过程中需要累加边权,增加了计算量。为此,可以将准则1进行改进,并得到合并准则2。

准则2的基本思想是假设每个损失值都是最坏情况,即损失最大值,它对应最后被加入MST的边权值,而这个边也正是我们想预测是否应该将其加入MST的边。因此,可以得到:

$ \begin{array}{*{20}{c}} {I\left[ {{f_S}} \right] = \mathop {\lim }\limits_{n \to \infty } \frac{1}{n}\sum\limits_{i = 1}^n {L\left( {f\left( {{x_i}} \right),y_i^ * } \right)} \le }\\ {\mathop {\lim }\limits_{n \to \infty } \frac{1}{n}\left[ {n \times L\left( {f\left( {{x_n}} \right),y_n^ * } \right)} \right] = }\\ {\mathop {\lim }\limits_{n \to \infty } L\left( {f\left( {{x_n}} \right),{y_n}} \right) = {w_{n - 1}}} \end{array} $ (11)

式中,n是顶点数,wn-1是最后要加入MST的边权。根据式(5) 和上面的解释,可以得到概率表达式:

$ \Pr \left( {{w_{n - 1}} \le M\sqrt {\frac{{2\ln \left( {2/\delta } \right)}}{n}} } \right) \ge 1 - \delta $ (12)

那么,合并判决准则1可以改写得到合并准则2:

$ P\left( {{S_1},{S_2}} \right) = \left\{ \begin{array}{l} {\rm{True,}}\;{w_{{n_1} - 1}} \le M\sqrt {\frac{{2\ln \left( {2/\delta } \right)}}{{{n_1}}}} ;{w_{{n_2} - 1}} \le M\sqrt {\frac{{2\ln \left( {2/\delta } \right)}}{{{n_2}}}} \\ {\rm{False,其他}} \end{array} \right. $ (13)

可以看出,合并准则2(式13) 只需比较当前边的权值是否同时小于它所连接的两个区域所允许的泛化误差界,并且减少了数据存储量和计算量。

3 合并准则分析与实验结果比较 3.1 合并准则分析

两个准则都由3个参数(ni,δ,M)来控制阈值,而且正好是控制分割尺度的参数,其中,ni是区域i的像素数,其值随合并过程动态变化。概率δ是在0和1之间的一个小值,它的变化对阈值影响不大,具有微调作用。根据概率理论和前面的分析,我们通常设其值为0.1。M是损失上界,它对应于边权的上确界,可以根据可能的最大边权值(区域内最大差异)来选择它的值。

$ \begin{array}{*{20}{c}} {w\left( {u,v} \right) = \sum\limits_{i = 1}^l {{w_i}d\left( {{u_i},{v_i}} \right)} = }\\ {\sqrt {\sum\limits_{i = 1}^l {{w_i}{{\left| {{u_i} - {v_i}} \right|}^2}} } } \end{array} $ (14)

式中,w(u, v)表示连接两相邻顶点(像素)uv的边的权值;l为波段数;wi为波段i的距离权重;$\sum\limits_{i = 1}^l {{w_i} = 1} $ui为顶点u在波段i的灰度值。一般灰度影像的M最大为255。图 2给出了δ=0.1,M取值分别为30、40、50、80、100、120时,阈值随区域像素数从1~100的变化曲线,可以发现,其他两个参数不变的情况下,M值较大时得到的阈值较大,允许的泛化误差大,即允许区域内部变化大,从而得到大尺度的分割结果。对于判决准则1,I′i是MST的边权期望(均值),因此,要得到好的分割结果,应该设置M为期望的边权均值,对于判决准则2,M应该设置为希望得到的区域的最大边权。

图 2 M取不同值时阈值随面积的变化规律 Figure 2 Relationship Between the Threshold and the Area with Different M

给定一个小的δ和损失上界M,合并阈值随着区域的增大而减小。这意味着在合并过程中,区域面积较小时允许区域内部具有较大差异,而随着区域面积的增大,它所允许的区域内差异较小,保证了区域的一致性,这使得该准则具有较高的抗噪声能力,避免产生太小区域(过分割)。在准则1中,使用MST的边权均值来判断和预测两个区域是否允许合并,削弱了大边权值的影响,因此,它允许区域内存在大的不均匀性。而准则2用最大边权来进行判断预测,因此,能较好地保持区域内部一致性和边界信息。

从计算量考虑,使用准则1时,在合并算法实现过程中需要存储区域中每个边权值并且计算它们的和与均值,而在准则2的实现过程中,只需使用当前访问边,因此,对于准则1来说所需计算量和存储量都大于准则2。另外,在构造影像图模型的过程中,很容易得到最大边权值,即损失上界M,这样就可以根据其大小和允许内部差异大小给出一个推荐M值,从而实现不同尺度参数下的分割。

综上所述,准则2在算法的准确度和效率上都优于准则1。

3.2 分割实验结果与分析

本文以我国阳江海域无人机遥感影像数据(由DM150型号飞机于2014-11-28,在飞行高度为800 m获取的0.18 m分辨率影像生成的1:2 000比例尺DOM影像)作为实验对象,通过两组图像分割实验比较分析两种分割准则支持下的最小生成树分割结果,并将其与其他分割方法进行比较。

1) 第一组实验对本文提出的两个准则的分割结果比较。

图 3图 4分别给出了以δ=0.1,M=10和M=15情况下,采用准则1和准则2得到的分割结果(红色曲线为区域边界)。从图中可以看出,同样的参数,准则1分割得到的区域更大,区域内部差异也更大,这是因为准则1采用了区域边权平均,而准则2采用的是区域内最大边权值,更保证了区域内部的一致性。另一方面,两个准则都随着参数M值的增大,分割所得区域面积也在不断增大,因此,通过选择合适的参数M的值,将得到不同细节的分割区域。同时,由于算法相同,参数控制总的思想相同,因此,采用准则2同样可以得到准则1的分割结果。从图中可以发现,这两个准则都随着分割尺度参数的增大,区域内部的细节被忽略,具有保证分割结果整个区域完整性的特点,即避免产生过分割。

图 3 采用准则1分割所得结果 Figure 3 Segmentation Results by the First Criterion
图 4 采用准则2分割所得结果 Figure 4 Segmentation Results by the Second Criterion

通过实验可知,准则2能较好地得到区域边界,且不会出现重边等过细的不必要的分割边界。

2) 第二组实验将本文提出的准则2与Felzenszwalb等[7]提出的分割准则比较。

图 5(a)为采用准则2取M=20时得到的分割结果,图 5(c)为采用Felzenszwalb准则取k=255时所得分割结果。从图 5中可以发现,采用Felzenszwalb准则得到的分割结果存在很多双边区域,如图 5(b)5(d)中黄色框内局部显示,这些双边小区域对于区域划分和目标识别来说过于琐碎,并且容易在整体内部出现小对象,如图中的围塘,采用Felzenszwalb准则会出现很多过分割,不利于整体分析;另外,从图中可以看出,本文方法也可以将轮船边界分割的较好,而Felzenszwalb准则会在船只周边出现很多小对象,但该准则可以较好地将每个小船只分割出来。

图 5 本文准则与Felzenszwalb准则分割结果比较 Figure 5 Segmentation Result Comparison Between the Proposed Second Criterion and the Criterion Proposed by Felzenszwalb

通过以上两组实验比较分析可以发现,本文提出的基于统计学习理论的最小生成树图像分割准则能通过尺度参数控制实现不同尺度目标的分割,具有较好的抗噪声性能,对纹理区域也能得到较好的分割效果,同时能获得良好的区域边界。

本文提出的分割准则只考虑了边权特性,由于基于自底向上的最小生成树分割思想与区域增长本质上的一致性,只是种子点选取是区域增长分割方法中关键步骤之一,而最小生成树方法从最相似像素开始增长,保证了全局最优,为基于区域增长的分割方法的种子点选择提供了思路,因此,将基于最小生成树的分割方法与区域增长方法相结合将对有效提高分割效果。如何在分割过程中考虑除了边权值外的其他因素,还可以将原始影像中其他信息加入分割准则,这将是下一步研究的问题。

4 结语

大多数面向对象的图像分割方法本质上都是一个区域增长的过程,区域增长种子点的选择和分割准则设计的合理性对分割结果具有重要影响,也是区域增长分割方法的关键和难点。本文采用图论中的最小生成树最优化理论及算法实现区域增长式的面向对象影像分割,使得邻接的最相似像素优先合并,避免了传统区域增长分割算法中选择增长点的难题;同时将最小生成树算法思想与统计学习理论相结合来设置合并准则,详细阐述了设计该分割准则的理论依据,并对分割参数与分割结果之间的关系进行分析,结果表明,该准则具有较好的抗噪声性能,对纹理区域也能得到较好的分割效果,同时能获得良好的区域边界,并在海岸带大比例尺无人机正射影像的图像分割实践中得到了较好验证。

由于分割参数的选择是影响分割效果的重要因素,不同地物类型所需要的分割尺度参数有所不同,因此,需要针对不同影像、不同地物研究和确定一套分割尺度参数选择机制,这也是本文进一步开展的研究方向。

参考文献
[1] Bousquet O, Elisseeff A. Algorithmic Stability and Generalization Performance[J]. Advances in Neural Information Processing Systems, 2001, 13: 499–526
[2] Bousquet O, Elisseeff A. Stability and Generalization[J]. Journal of Machine Learning Research, 2002, 2: 499–526
[3] Boykov Y Y, Jolly M P. Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images[C]. International Conference on Computer Vision, Vancouver, Canada, 2001
[4] Boykov Y, Kolmogorov V. An Experimental Comparison of Min-cut/max-flow Algorithms for Energy Minimization in Vision[J]. IEEE Transactions on PAMI, 2004, 26(9): 1124–1137 DOI:10.1109/TPAMI.2004.60
[5] Cour T, Benezit F, Shi J. Spectral Segmentation with Multiscale Graph Decomposition[J]. IEEE Computer Vision and Pattern Recognition, 2005, 2: 1124–1131
[6] Falcão A X, Udupa J K, Samarasekera S, et al. User-Steered Image Segmentation Paradigms:Live Wire and Live Lane[J]. Graphical Models and Image Processing, 1998, 60(4): 233–260 DOI:10.1006/gmip.1998.0475
[7] Felzenszwalb P F, Huttenlocher D P. Efficient Graph-Based Image Segmentation[J]. International Journal of Computer Vision, 2004, 59(2): 167–181 DOI:10.1023/B:VISI.0000022288.19776.77
[8] Grady L, Schwartz E L. Isoperimetric Graph Partitioning for Image Segmentation[J]. IEEE Trans Pattern Anal Mach Intell, 2006, 28(3): 469–475 DOI:10.1109/TPAMI.2006.57
[9] Hickson S, Birchfield S, Essa I, et al. Efficient Hierarchical Graph-based Segmentation of RGBD Videos[J]. Computer Vision and Pattern Recognition (CVPR), 2014, 12(4): 344–351
[10] Kropatsch W G, Haxhimusa Y, Ion A. Multiresolution Image Segmentations in Graph Pyramids[J]. Studies in Computational Intelligence(SCI), 2007, 52: 3–41
[11] Habib M, McDiarmid C, Ramirez-Alfonsin J, et al. Concentration in Probabilistic Methods for Algorithmic Discrete Mathematics[M]. NY: Spring, 1998: 195–248
[12] Mortensen E N, Barrett W A. Interactive Segmentation with Intelligent Scissors[J]. Graphical Models and Image Processing, 1998, 60(5): 349–384 DOI:10.1006/gmip.1998.0480
[13] Santle C K, Govindan V K. A Review on Graph Based Segmentation[J]. International Journal of Image, Graphics and Signal Processing (IJIGSP), 2012, 4(5): 1–13 DOI:10.5815/ijigsp
[14] Shi J, Malik J. Normalized Cuts and Image Segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2000, 22(8): 888–905 DOI:10.1109/34.868688
[15] Wei Y C, Cheng C K. Ratio Cut Partitioning for Hierarchical Designs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991, 10(7): 911–921 DOI:10.1109/43.87601
[16] Xu N, Bansal R, Ahuja N. Object Segmentation Using Graph Cuts Based Active Contours[J]. IEEE Computer Vision and Pattern Recognition, 2003, 2: 46–53
[17] Xu Y, Uberbacher E C. 2D Image Segmentation Using Minimum Spanning Trees[J]. Image and Vision Computing, 1997, 15(1): 47–57 DOI:10.1016/S0262-8856(96)01105-5
[18] Zheng Chen, Wang Leiguang, Hu Yijun, et al. Texture Segmentation Based on Multiscale Fuzzy Markov Random Field Model in Wavelet Domain[J]. Geomatics and Information Science of Wuhan University, 2010, 35(9): 1074–1078 ( 郑晨, 王雷光, 胡亦钧, 等. 利用小波域多尺度模糊MRF模型进行纹理分割[J]. 武汉大学学报·信息科学版, 2010, 35(9): 1074–1078. )