（信号与信息处理专业论文）基于图论的图像分割及其嵌入式应用研究.pdf

基于图论的图像分割及其嵌入式应用研究 摘要 图像分割是一种底层的图像处理技术，它根据特定的特征将图像分离为连通的 有意义区域，可以广泛应用在图像及视频的高级处理任务中。图像分割技术经过几 十年的发展，形成了众多的方法、繁杂的类别和海量的文献，但是与人眼视觉特征 相一致的全局分割问题一直得不到解决。在这些方法中，基于图论最小生成树的方 法利用区域比较准则和最小生成树算法分割图像，具有获取全局特征的能力，计算 速度快，是一种可以作为应用研究的分割方法之一。本文的工作主要基于此算法。 为了提高此算法应用的可能性，我们需要更改算法及优化程序，提高其全局分 割效果和计算速度。本文在分析基于最小生成树分割算法概念、原理、数据结构和 实现方式的基础上，发现其运算瓶颈为边的数目，也就是图中实际计算的节点数日。 因此本文利用图像局部特征相似的特性，使用n xn ，n = 1 , 2 ，3 大小的自适应像素块 映射为单个计算肖点，大大降低了实际计算的1 了点和边的数目，从而降低了核心算 法的计算复杂度。 为了适应块结构，本文更改了邻域系统，提出了基本连接和超连接的层次。基 本连接保证了相邻区域的邻近性，而超连接提供了区域之间的连续性。这种两层的 连接方式提高了算法获取全局特征的能力，获得了既不过分割也不欠分割的效果， 接近图像对象的数目，减少了原算法分割区域的数目。另外，为了分析基于最小生 成树算法的结构，本文将其分为三个阶段：前处理、核心算法和后处理。原算法大 部分的计算负担集中在核心算法上，算法结构极不均衡。因此，本文在保证三个阶 段接口不变的基础上，将构造图的过程从核心算法阶段转移到前处理阶段，均衡了 计算量，增加了算法并行处理的能力。 图像进行分层分析和表达由来已久，具有在不同分辨牢下表现图像内容的优势。 金字塔图像分割方法是一种分层的分析方法，其突出优点是可以累积局部特征，从 而表现全局特征。金宁塔分为规则金宁塔和非规则金字塔，后者可以克服前者的刚 性特点，与图像内容相适应，成为金字塔图像分割算法的主要实现形式。人们提出 了不同的非规则金字塔数据结构和缩减方法，但足大多数比较复杂。本文利用基于 最小生成树分割算法计算速度快、结构简单、有效进行区域比较的优势，将其作为 缩减核应用到非规则金字塔结构中，形成一种快速有效的块嵌入非规则金字塔分割 算法。为了将金字塔高度控制在合理范围内，提高缩减因子，本文在第零层使用块 结构加快其收敛速度，并提出了一种快速的邻近区域搜索方法以有效地构造高一层 的边。试验结果表明，新的算法具有良好的分割效果和计算速度。 块嵌入非规则金字塔分割算法使用区域的特征平均值代替父节点的特征值，降 低了噪声对算法的影响，从而无需额外的去噪方法，消除了原算法的高斯滤波参数。 本文使用权重的最大最小差值代替原算法抑制小区域的参数，可以在每层上自动适 应图像的特征。另外，在构造块结构的过程中，本文使用图像的标准差作为比较准 则，从而无需输入块构造参数。金字塔累积局部特征的本质可以去除合并小区域的 步骤，从而消除了最小区域参数。本文的这些工作使块嵌入非规则金字塔分割算法 成为一个参数独立的自动分割算法，有利于实际应用。 良好的分割效果与快速计算速度使分割算法进行实时应用成为可能。本文在高 清数字电视解码器片上系统平台软硬件工作的基础上，分析了基于m i p s 处理器的 嵌入式平台在时间和空间上的运算资源优化，尝试将基于最小生成树的图像分割算 法进行嵌入式移植。在回顾算法改进的基础上，本文对程序代码进行运行时问和空 间上的优化，包括运行时问剖析、缓存优化、调用关系优化和动态内存分析等，以 软件i p 的形式移植到基于m i p s 开发平台m a l t a 板上。分割程序建立在一个嵌入式 软件系统上，包括启动程序、l i n u x 操作系统、a p i 和库等，以主机控制目标板的方 式运行，通过网络远程读写图像文件。 关键词：图像分割，图论，最小生成树，金字塔分割，非规则金字塔，缩减核， 优化，嵌入式平台，软件i p r e s e a r c ho ng r a p h t h e o r yb a s e di m a g es e g m e n t a t i o na n d i t se m b e d d e d a p p l i c a t i o n a b s t r a c t i m a g es e g m e n t a t i o ni sal o w l e v e lt e c h n i q u eo fi m a g ep r o c e s s i n g i tp a r t i t i o n s i m a g e si n t om e a n i n g f u lc o n n e c t e dr e g i o n sb ys o m es p e c i f i c i m a g ef e a t u r e s t h e h i g h l e v e la p p l i c a t i o n so fi ti n c l u d ei m a g e & v i d e op r o c e s s i n gt a s k s ，c o v e t i n gf i e l d so f b r o a d c a s t ，c o m p u t e rn e t w o r k ，p a t t e r nr e c o g n i t i o n ，a n dm a c h i n ev i s i o n ，e t c r e s e a r c ho n i m a g es e g m e n t a t i o nt e c h ni q u e sh a sd u r a t i o no fs e v e r a ld e c a d e so f y e a r s a l t h o u g ht h e r e e x i s tm a n ym e t h o d s ，m u l t i p l ec l a s s e s ，a n dah u g el i t e r a t u r ei nt h i s f i e l d ，t h ep r o b l e mo f g l o b a ls e g m e n t a t i o nh a v i n gv i s i o nc o n s i s t e n c yw i t hh u m a ne y e si sn o ts o l v e dw e l l a m o n ga l l o ft h e s ei m a g es e g m e n t a t i o nm e t h o d s ，t h eo n eb a s e do nm i n i m u m s p a n n i n gt r e e ( m s t ) a n dr e g i o nc o m p a r i s o np r e d i c a t e sh a st h ec a p a b i l i t yo fc a p t u r i n g g l o b a lf e a t u r e s i ta l s or u n sq u i c k l y , h a v i n gc o m p u t a t i o n a lc o m p l e x i t yn e a r l yl i n e a rt ot h e p i x e in u m b e r t h et w od o m i n a n ta d v a n t a g e sg i v ei tt h ep o s s i b i l i t yt oa p p l i c a t i o n o u r w o r km a i n l yb a s e so nt h em s t - b a s e da l g o r i t h m i no r d e rt o i m p r o v et h es e g m e n t a t i o nr e s u l t sa n dc o m p u t a t i o n a l s p e e d ，w e c o n c e n t r a t et h em o d i f i c a t i o ne f f o r t so nt w os i d e s ：a l g o r i t h ma n dp r o g r a m t h e a l g o r i t h m d e t a i l so ft h ec o n c e p t s ，t h e o r i e s ，d a t as t r u c t u r e s ，a n di m p l e m e n t a t i o nw a y sa r es t u d i e d w ef i n dt h a tt h eb o t t l en e c ko ft h ea l g o r i t h md u e st ot h en u m b e ro fg r a p he d g e s ，i e ，t h e a c t u a ln u m b e ro f c o m p u t e dv e r t i c e si nt h em a p p e dg r a p h i n s t e a do f m a p p i n gt h ei m a g e p i x e lb yp i x e l ，o u rw o r kr e p r e s e n t sw i t ho n ev e r t e xas q u a r eb l o c ko fi m a g ep i x e l sw i t h f i x e ds i z eo fnxn ，n = 1 , 2 ，3 t h i st r i c ku t i l i z e st h es i m i l a r i t yo f l o c a li m a g ef e a t u r e s a m o n gn e i g h b o r i n gp i x e i s ，s i g n i f i c a n t l yd e c r e a s i n gt h en u m b e ro f g r a p he d g e s t h ef i x e d s q u a r eb l o c k ss i m p l i f yt h ew o r ko fd e c i d i n gw h e t h e ro n ep i x e lb e l o n g st os o m eb l o c k w e c h a n g et h en e l g h b o r i n gs y s t e mt oa d a p tw i t ht h es q u a r eb l o c k s i tc o n s i s t so ft w o l a y e r s ：t h eb a s i ca n ds u p e rc o n n e c t i o n t h eb a s i cc o n n e c t i o nk e e p st h ep r o x i m i t yo f r e g i o n s , a n dt h es u p e rc o n n e c t i o nk e e p st h ec o n t i n u i t yo fr e g i o n s t h e yi m p r o v et h e c a p a b i l i t y o f c a p t u r i n gg l o b a lf e a t u r e s t h es e g m e n t a t i o n p r o d u c e s n e i t h e r i i i 0 v e r - s e g m e n t e dn o ru n d e r - s e g m e n t e dr e g i o n s w ec l a s s i f yt h ea l g o r i t h mi n t ot h r e es 协g e s ： p r e p r o c e s s o r ，k e r n e l ，a n dp o s t p r o c e s s o r t h e s t r u c t u r ef a c i l i t a t e s t h eb a l a n c eo f c o m p u t a t i o n a ll o a d s 。t h eo r i g i n a la l g o r i t h mh a s ab i gp o r t i o no fc o m p u t a t l o nmt n e k e m e l t h e r e f o r ew em o v et h ep r o c e d u r e o fg r a p hb u i l d i n gf r o mk e r n e l i n t ot h e p 陀p r o c e s s o rb yk e e p i n gt h ei n t e r f a c e su n c h a n g e d t h em o d i f i c a t i o ni m p r 0 v e s t h ea b l l 埘 o fp a r a l l e lp r o c e s s i n g a n a l y z i n ga n dr e p r e s e n t i n gi m a g e si na h i e r a r c h i c a lw a yh a sal o n gh i s t o 阱i th 硒 a d v a n t a g e so fs h o w i n gi m a g ec o n t e n t si nd i f f e r e n td e f i n i t i o n s g r a p hp y r 锄l d sm 1 m a g e s e g l n e n t a t i o nc 锄a g ：c u m u l a t em e a lf e a t u r e s ，r e p r e s e n t i n gi na c o a e s ed e f i n i t i o nt h eg l o b a l f e 咖佗s p y r a m i d sh a v et w oc l a s s e s ：r e g u l a ra n di r r e g u l a rp y r a m i d i r r e g u l a rp y 咖i d 1 s a i s oc a l i e da d a p t i v ep y r a m i d ，w h i c ho v e r c o m e st h er i g i d i t yo fr e g u l a rp y 舢1 d 舳d 1 s a d a p t i v et o t h ec o n t e n t so fi m a g e s t h ei r r e g u l a rp y r a m i d s t r u c t u r e1 st h em 猢 i m p i e m e n t a t i o ni ns e g m e n t a t i o nm e t h o d s m a n yd a t as t r u c t u r ea n d d e c i m a t l o ns c h e m e s a b o u ti 仃e g u l a rp y r a m i d sh a v eb e e np r e s e n t e d ，b u tm o s to f t h e m a r et o oc o m p i e x o u rw o r ku s et h em s t - b a s e ds e g m e n t a t i o na l g o r i t h ma sa ni r r e g u l a rc o n t r a c t l o n k e m e lb e e a u o fi t sa d v a n t a g e so fg l o b a ls e g m e n t a t i o n ，h i g hr u n n i n gs p e e d ，a n ds l m p i e a l g o r i t h ms t r u c t u r e t h eb l o c k sa r eu s e di nl e v e l0 t oi m p r o v ec o n v e r g e n c es p e e d an e w f a s tn e i g h b o rr e g i o ns e a r c h i n gm e t h o di sg i v e n t oe f f i c i e n t l yc o n s t r u c tt h ee d g e sm h l g h e 。 l e v e l t h e s ee 肋r t sl i m i tt h ec o n t r a c t i o nf a c t o ra n dp y r a m i dh e i g h t ，a n d s h o wan e w i r r e g u l a rp y r a m i ds e g m e n t a t i o n a l g o r i t h mw i t h e m b e d d e db l o c k s m o r e e f f i c i e n t s e g m e n t a t i o na i l dh i g h e rr u n n i n gs p e e d a r ev e r i f i e db yt h ee x p e r i m e n t a lr e s u l t s w eu s es o m em o d i f i c a t i o n st of o r map a r a m e t e ri n d e p e n d e n ts e g m e n t a t i o na l g o r i t h m f i r s t l v t h ef e a t u r eo fp a r e n tv e r t e xi sr e p l a c e db yt h em e a nv a l u eo f i t sr e 9 1 0 n1 no u r i r r e g u l a rp y r a m i d i tr e d u c e s t h ea f f e c to fn o i s ew i t h o u to t h e rm e t h o d s ，t h e r e f o 。e r e m o v i n gt h eg a u s s i a nf i l t e rp a r a m e t e ri nt h eo r i g i n a la l g o r i t h m s e c o n d l y ，t h ep a r a m e t e r o fl i m i t i n gs m a l lr e g i o n si sr e p l a c e db yt h ee d g ew e i g h td i f f e r e n c eb 咖e e nm 觚1 m u m 觚dm i n i m u mv a l u e t h em o d i f i c a t i o na d a p t st h ea l g o r i t h mt oe a c hl e v e lo f t h e1 r r e g u l a r p v m m i d t h i r d l y , t h ed e v i a t i o no ft h ei m a g ef e a t u r ei sc o m p u t e d t or e p i a c eat h 。e s h o l d p a r a m e t e ri nc o n s t r u c t i n gt h eb l o c k s f o u r t h l y , t h ei n t r i n s i cc o n t r a c t l o n o ft h ep y r a m l d 嘶sr i do ft h ep r o c e d u r eo fm e r g i n gs m a l lc o m p o n e n t s t h e r e f o r e i tr e m o v e st h e c o r r e s p o n d i n gp a r a m e t e r i v g o o ds e g m e n t a t i o nr e s u l t sa n df a s ts o l u t i o nm a k eo u ra l g o r i t h mh a v eap o s s i b i l i t yt o r e a l - t i m ea p p l i c a t i o n s b a s e do nt h ew o r ko fs o f t w a r e h a r d w a r ed e s i g n so nt h ed e c o d e ro f h i g hd e f i n i t i o nt e l e v i s i o ns y s t e m - o n a - c h i pp l a t f o r m ，w ea n a l y z et h eo p t i m i z a t i o n so f t e m p o r a la n ds p a t i a l r e s o u r c e so ne m b e d d e dp l a t f o r mw i t hm i p sp r o c e s s o r t h e o p t i m i z a t i o no ft h em s t - b a s e ds e g m e n t a t i o na l g o r i t h m i s f i r s t l yr e c a l l e d t h e nw e c o n e e n 打a t et h eo p t i m i z a t i o nw o r ko np r o g r a mc o d e s , i n c l u d i n gr u n n i n gt i m ep r o f i l i n g , c a c h eu s i n g , f u n c t i o nc a l l ，a n dd y n a m i cm e m o r y , e t c f i n a l l yo u rs e g m e n t a t i o na l g o r i t h m i sp o r t e dt om i p sd e v e l o p m e n tp l a t f o r mm a l t aa ss o f t w a r ei p i tr u n si nah o g - t a r g e tw a y o na l le m b e d d e ds o f t w a r es y s t e m ，w i t hc o m p o n e n t si n c l u d i n gb o o tl o a d e r , l i n u xk e r n e l ， a p ia n dl i b t h es e g m e n t a t i o np r o g r a mr e a d s w r i t e si m a g ed a t af i l e sv i an e t w o r k i naw o r d ，w es t u d yt h em s t - b a s e di m a g es e g m e n t a t i o nm e t h o da n dp y r a m i d s t r u c t u r e s a tt h es a m et i m e , as e r i e so fe f f o r t sa r eg i v e nt oi m p r o v et h es e g m e n t a t i o n r e s u l t sa n dr u n n i n gs p e e d w ea l s oo p t i m i z et h ep r o g r a mi nr u n n i n gt i m ea n ds p a c e a s p e c t s ，a n dp r e s e n tap o r t i n gt oe m b e d d e dp l a t f o r m t h ee x p e r i m e n t a lr e s u l t ss h o wg o o d v a l u e so f o u rw o r ko nt h e o r ya n da p p l i c a t i o n k e yw o r d s ：i m a g es e g m e n t a t i o n ，g r a p ht h e o r y , m i n i m u ms p a n n i n gt r e e ，p y r a m i d s e g m e n t a t i o n ，i r r e g u l a rp y r a m i d ，c o n t r a c t i o nk e r n e l ，o p t i m i z a t i o n ，e m b e d d e dp l a t f o r m ， s o f t w a r ei p v a 术语中英文对照表 按级合并( u n i o nb yr a n k ) 按点合并( u n i o nb yv e r t e x ) b 比例切割( r a t i oc u t ) 边( e d g e ) 边图( e d g eg r a p h ) 标签( l a b e l i n g ) 保持结构的收缩( s t r u c t u r e p r e s e r v i n gc o n t r a c t i o n ) 包含关系( i n c l u s i o nr e l a t i o n s h i p ) 饱和度( s a t u r a t i o n ) 保留节点( s u r v i v i n gv e r t i c e s ) 比较谓词( c o m p a r i s o np r e d i c a t e ) 不用人为干预的( u n s u p e r v i s e d ) c 彩色图像( c o l o ri m a g e ) 采样率( s a m p l i n gr a t e ) 残差图( r e s i d u a lg r a p h ) 差别( d i f f e r e n c e ) 超连接( s u p e rc o n n e c t i o n ) 垂直关系( v e r t i c a lr e l a t i o n s h i p ) 存储系统( m e m o r ys y s t e m ) d 底层( l o w - l e v e l ) i x 独立的连续区域( d i s j o i n t e dc o n s t i t u e n tr e g i o n ) 独立节点( i s o l a t e dv e r t i c e s ) 端点( t e r m i n a l s ) 对偶边收缩( d u a l - e d g ec o n t r a c t i o n ) 对偶对( d u a lp a i r ) 对偶面缩减( d u a l f a c ec o n t r a c t i o n ) 对偶图( d u a lg r a p h ) 对偶图收缩( d u a l - g r a p hc o n t r a c t i o n ) 多重边( m u l t i p l ee d g e ) 多项式时间( p o l y n o m i a lt i m e ) e f 方向线( d a r t ) 非保留( n o n s u r v i v i n g ) 非规则金字塔( i r r e g u l a rp y r a m i d ) 非连续性( d i s c o n t i n u i t y ) 分层图( h i e r a r c h i c a lg r a p h ) g 感兴趣目标( o b j e c to f i n t e r e s t ，o o i ) 感知组合( p e r c e p t u a lg r o u p i n g ) 高级( h i g h - l e v e l ) 高清晰度电视( h i i g hd e f i n i t i o nt e l e v i s i o n ，h d t v ) 格式塔心理学( g e s t a l tp s y c h o l o g y ) 工作层( w o r k i n gl e v e l ) 关联矩阵( i n c i d e n c em a t r i x ) 固件( f i r m w a r e ) 归一化( n o r m a l i z e d ) 归一化切割( n o r m a l i z e dc u t ) x 规则金字塔( r e g u l a rp y r a m i d ) h 函数头( f u n c t i o np r o l o g u e ) 函数尾( f u n c t i o ne p i l o g u e ) 合并一寻找( u n i o n f i n d ) 缓存( c a c h e ) 灰度图像( g r a yi m a g e ) 汇集( s i n ks e t ) 汇节点( s i n kv e r t e x ) i j 加权链接金字塔( w e i g h t e dl i n k e dp y r a m i d ) 加权图( w e i g h t e dg r a p h ) 简单图( s i m p l eg r a p h ) 交互位势( i n t e r a c t i o np o t e n t i a l ) 基本连接( b a s i cc o n n e c t i o n ) 继承排列( s u c c e s s o rp e r m u t a t i o n ) 级间边( i n t e r - l e v e le d g e ) 级内边( i n t r a - l e v e le d g e ) 计算机视觉( c o m p u t e rv i s i o n ) 基于特征空间( f e a t u r e s p a c eb a s e d ) 基于图论的图像分割( g r a p ht h e o r yb a s e di m a g es e g m e n t a t i o n ) 基于图像空间( i m a g e - d o m a i nb a s e d ) 基于物理特征( p h y s i c sb a s e d ) 节点( v e r t e x ) 金字塔链接方法( p y r a m i dl i n k i n ga p p r o a c h ) 聚类( c l u s t e r i n g ) 剧烈变化( h i g h t - v a r i a b i l i t y ) x i k 空间的一致性( s p a t i a lc o n s i s t e n c y ) 扩充路径( a u g m e n t i n g p a t h ) l 拉普拉斯矩阵( l a p l a c i a nm a t r i x ) 分离集森林( d i s j o i n - s e t f o r e s t ) 立体视觉( s t e r e o ) 连接密度( c o n n e c t i o nd e n s i t y ) 连通路径( c o n n e c t i n gp a t h ) 连通区域( c o n n e c t e dr e g i o n ) 连续性( c o n t i n u a t i o n ) 亮度( b r i g h t n e s s ) 邻接矩阵( a d j a c e n c ym a t r i x ) 邻接性( p r o x i m i t y ) 邻域系统( n e i g h b o rs y s t e m ) 流量守恒条件( c o n s e r v a t i o nc o n s t r a i n t s ) 路径压缩( p a t hc o m p r e s s i o n ) 滤波器幅度( f i l t e rs c a l e ) m 马尔科夫随机场( m a r k o vr a n d o mf i e l d ，m r f ) 紧致性( c o m p a c t ) 模糊集理论( f u z z ys e tt h e o r y ) 模式识别( p a t t e r nr e c o g n i t i o n ) n 内部属性( i n t e r n a lp r o p e r t y ) 逆排列( r e v e r s ep e n n u t a t i o n ) o p 片上系统( s y s t e m o n - a - c h i p ，s o c ) x 平均切割( a v e r a g ec u t ) 平面图( p l a n a rg r a p h ) 剖析( p r o f i l e ) 谱图( s p e c t r a lg r a p h ) q 前景切割( f o r g r o u n dc u t ) 嵌入式平台( e m b e d d e dp l a t f o r m ) 嵌入式系统( e m b e d d e ds y s t e m ) 嵌套切割( n e s t e dc u t ) 区域分离和合并( r e g i o ns p l i t t i n ga n dm e r g i n g ) 区域邻接图( r e g i o na d j a c e n c yg r a p h ，r a g ) 区域增长( r e g i o ng r o w i n g ) 区域组合( r e g i o ng r o u p ) r 容差( t o l e r a n c e ) 容量( c a p a c i t y ) 容量限制条件( c a p a c i t yc o n s t r a i n t s ) 容纳区域( r e c e p t i v ef i e l d ) 瑞利商( r a y l e i g hq u o t i e n t ) s 色调( h u e ) 生成森林( s p a n ni n gf o r e s t ) 生成树( s p a n n i n g t r e e ) 生成子图( s p a n n i n gs u b g r a p h ) 试探法( h e u r i s t i c s ) 收缩率( c o n t r a c t i o nr a t i o ) 数据惩罚函数( d a t ap e n a l t yf u n c t i o n ) 数据结构合并( d a t as t r u c t u r em e r g i n g ) 数字图像分割( d i g i t a li m a g es e g m e n t a t i o n ) 水平关系( h o r i z o n t a lr e l a t i o n s h i p ) 缩变性( s c a l e v a r i a n t ) 缩减参数( d e c i m a t i o np a r a m e t e r ) 缩减窗( r e d u c t i o nw i n d o w ) 缩减方法( d e c i m a t i o ns c h e m e ) 缩减过程( d e c i m a t i o np r o c e d u r e ) 缩减函数( r e d u c t i o nf u n c t i o n ) 缩减核( c o n t r a c t i o nk e r n e l ) 缩减因子( r e d u c t i o nf a c t o r ) t 特征分析( e i g e na n a l y s i s ) 同质特性( h o m o g e n o u sf e a t u r e ) 同质性谓词( h o m o g e n e i t yp r e d i c a t e ) 图边( g r a p he d g e ) 图节点( g r a p hv e r t e x ) 图谱( g r a p hs p e c t r u m ) 图切割( g r a p hc u t ) 图像标签( i m a g el a b e l i n g ) 图像复原( i m a g er e s t o r a t i o n ) 图像检索( i m a g ei n d e x i n g ) 图像挖掘( i m a g em i n i n g ) 图像压缩( i m a g ec o m p r e s s i o n ) 退化面( d e g e n e r a t e df a c e ) 推进重标签( p u s h - r e l a b e l ) u v w v 外部属性( e x t e r n a lp r o p e r t y ) 纹理合成( t e x t u r es y n t h e s i s ) 无内锁流水线微处理器( m i c r o p r o c e s s o r w i t h o u ti n t e r l o c k i n gp i p e l i n es t a g e ，m i p s ) x 相邻( n e i g h b o r h o o d ) 相似度矩阵( a f f i n i t ym a t r i x ) 相似性( s i m i l a r i t y ) 像素格( p i x e lg r i d ) 形状重构( s h a p er e c o n s t r u c t i o n ) 旋变性( r o t a t i o n v a r i a n t ) 循环合并( l o o pf u s i o n ) 循环交换( l o o pi n t e r c h a n g e ) 寻找路径( f i n dp a t h ) y 颜色空间( c o l o rs p a c e ，又称c o l o rm o d e l 或者c o l o rs y s t e m ) 移变问题( s h i f tv a r i a n tp r o b l e m ，s vp r o b l e m ) 移变性( s h i f t - v a r i a n t ) 应用程序接口( a p p l i c a t i o np r o g r a mi n t e r f a c e ，a p i ) 有根树( r o o t e dt r e e ) 阈值化( t h r e s h o l d i n g ) 源集( s o u r c es e t ) 源节点( s o u r c ev e r t e x ) 源汇的切割( s o u r c e s i n kc u t ) z 直方图阈值( h i s t o g r a mt h r e s h o l d i n g ) 知识产权( i n t e l l e c t u a lp r o p e r t y ，i p ) 种子规则( s e e d i n gr u l e ) 自身环( s e l f l o o p ) 自适应金字塔( a d a p t i v ep y r a m i d ) 子图( s u b g r a p h ) 自相似性( s e l f - s i m il a r r y ) 组合地图( c o m b i n a t o r i a lm a p ) 最人独立边集( m a x i m a li n d e p e n d e n te d g es e t ，m i e s ) 最大独立集( m a x i m a li n d e p e n d e n ts e t ，m i s ) 最大匹配( m a x i m a lm a t c h i n g ) 最近相邻( n e a r e s tn e i g h b o r ) 最小割最大流( m i n i m u mc u t m a x i m u mf l o w ) 最小生成树( m i n i m u ms p a n n i n gt r e e ，m s t ) 最小最大切割( m i n m a xc u t ) x 上海交通大学上海父逋大字 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究 做