（信息与通信工程专业论文）基于对称性的目标描述和识别技术.pdf

国防科学技术大学研究生院学位论文 摘要 目标的表示和识别技术是模式识别和图象理解领域的核心环节之一。现有的目 标表示方法往往是基于目标的图象特性和几何特性的。本文重点讨论了从大量人造目 标和自然目标中广泛存在的对称性出发而导出的目标表示和识别技术。 论文主要研究了基本对称和广义对称两大类对称性及其应用问题，它涉及如下 的研究工作。 首先，论文系统地总结了基本对称和扭对称的基本理论和检测技术。为了克服 直接从灰度图象中检测目标的基本反射对称轴时的困难，论文提出了一种基于分布式 主动智能体的新方法。该方法通过模拟智能体的感知、通信和行为能力来实现图象中 局部对称轴的检测、生长和编组功能。 其次，论文研究了基于骨架的目标表示和识别的基本理论和关键技术，具体涉 及：骨架的提取、骨架的分解、基于骨架的目标表示和匹配等技术。 在骨架提取方面，论文提出了一种通过模拟水流冲刷地形表面的过程来直接从 灰度图象中提取目标的骨架的高效算法，它可以得到连通的、保持目标的拓扑属性的、 处在目标的中线上的、近似单象素宽度的骨架。 在骨架分解和表示方面，论文提出了一种高效的骨架层次分解以及矢量化算法。 该算法首先将骨架分解为它的有意义分量( 如分支和环) 集，然后将各分量矢量化为 简单的结构基元( 如直线段和圆) ，最后将它们组织到个属性关系图之中。为了构 造属性关系图，论文提出了一种基于距离变换的确定平面子集的k 一近邻的实时算法。 该算法适用于任何类型的平面子集，并且可以推广到高维空间子集的k 一近邻计算中。 在骨架匹配方面，论文提出了一种基于加权最优二分图匹配技术的骨架匹配技 术。该算法通过测量属性关系图之间的最大公子图来计算骨架之间的距离。 最后，在基于对称性的目标描述和识别理论的基础上，建立了一个基于骨架的 图象数据库检索的实验系统，取得了预期的效果。 关键字：对称；扭对称：骨架；属性关系圈；图匹配；距离变换； 第1 页 国防科学技术大学研究生院学位论文 a b s t r c t o b j e c tr e p r e s e n t a t i o na n dr e c o g n i t i o nt e c h n i q u e sa r eo n eo ft h ek e yi s s u e si np a t t e r n r e c o g n i t i o na n di m a g eu n d e r s t a n d i n ga r e a s t h ec u r r e n to b j e c tr e p r e s e n t a t i o nm e t h o d sa r e u s u a l l yb a s e do nt h ei m a g ea t t r i b u t e sa n dt h eg e o m e t r i ca t t r i b u t e so ft h eo b j e c t s t h et h e s i s i s e m p h a s i z e do nt h et e c h n i q u e sc o n d u c t e df r o mt h eu b i q u i t o u si n h e r e n ts y m m e t r i c p r o p e r t i e so f t h em a n m a d ea n d n a t u r a lo b j e c t s t h eb a s i cs y m m e t r ya n dt h eg e n e r a l i z e ds y m m e t r ya n dt h e i ra p p l i c a t i o n sa r et h em a i n r e s e a r c hc o n t e n to f t h i st h e s i s i ti n c l u d e st h ef o l l o w i n gr e s e a r c hw o r k s f i r s t , t h eb a s i ct h e o r i e sa n dd e t e c t i o nt e c h n i q u e sf o r t h eb a s i cs y m m e t r i e sa n dt h e s k e w e ds y m m e t r i e sa r es y s t e m a t i c a l l ys u m m a r i z e d i no r d e rt oo v e r c o m et h ed i m c u l t i e st o d e t e c tt h eb a s i cr e f l e c t i o n a la x e so ft h eo b j e c t sd i r e c t l yf r o mag r a yi m a g e ，an e w a p p r o a c h b a s e do nt h ed i s t r i b u t e da c t i v ea g e n t si sp r e s e n t e di nt h i s 血e s i s t h i sm e t h o de n a b l e st o d e t e c t i o nt h el o c a ls y m m e t r yf i x e s ，g r o w i n ga n dg r o u p i n gt h e mb ys i m u l a t i n gt h e p e r c e p t i o n ，c o m m u n i c a t i o na n da c t i o nb e h a v i o r so f t h ea g e n t s n e x t ，t h eb a s i c t h e o r i e sa n dt h e k e yt e c h n i q u e s o ft h e s k e l e t o n b a s e d o b j e c t r e p r e s e n t a t i o na n dr e c o g n i t i o na r es t u d i e di n t h i st h e s i s ，w h i c hi n c l u d et h es k e l e t o n e x t r a c t i o n ，s k e l e t o nd e c o m p o s i t i o n ，s k e l e t o nb a s e do b j e c tr e p r e s e n t a t i o na n dm a t c h i n g t e c h n i q u e sa n ds oo n i nt h es k e l e t o ne x t r a c t i o n ，a nn o v e la p p r o a c hf o re x t r a c t i n gt h es k e l e t o n sd i r e c t l yf r o m t h eg r a yi m a g e si sd e v e l o p e db ys i m u l a t i n gt h ep r o c e d u r eo fw a t e re r o d i n gt h et o p o g r a p h y s u r f a c e t h er e s u l t a n ts k e l e t o n sa r es i n g l e - p i x e lw i d t ha n dc o n n e c t e d i ta l s ol i e si nt h e m i d d l el i n eo ft h e o b j e c ta n dk e e p st h et o p o l o g i c a lp r o p e r t i e so ft h eo r i g i n a li m a g e u n c h a n g e d i nt h es k e l e t o nd e c o m p o s i t i o na n dr e p r e s e n t a t i o n a ne 蚯c i e n ts k e l e t o nd e c o m p o s i t i o n a n dv e c t o r i z a t i o nm e t h o di sp r e s e n t e d t l l i sm e t h o df i r s td e c o m p o s e st h es k e l e t o ni u t oi t s m e a n i n g f u lc o m p o n e n t ( s u c ha sb r a n c ha n d1 0 0 p ) s e t ，t h e nv e c t o r i z e se a c hc o m p o n e n t st o s i m p l es t r u c t u r ee l e m e n t s ( s u c ha ss t r a i g h tl i n es e g m e n t sa n dc i r c l e s ) a n df i n a l l ya r r a n g e t h e mi n t oa l la t t r i b u t e dr e l a t i o ng r a p h i no r d e rt oc o n s t r u c tt h ea t t r i b u t e dr e l a t i o ng r a p h ，a n e wr e a lt i m em e t h o di sd e v e l o p e d w h i c hc o m p u t e st h ek - n no ft h ea r b i t r a r yp l a n a rs e t s u s i n gt h ed i s t a n c et r a n s f o r m a t i o nt e c h n i q u e t h i si d e ac a l la l s ob ea p p l i e dt ot h eh i g h e r d i m e n s i o n a ln o i n ts e t s i nt h es k e l e t o nm a t c h i n g ，a l ln o v e la p p r o a c hb a s e do nw e i g h t e do p t i m a lb i p a r t i t eg r a p h m a t c h i n gt h e o r yi sa l s op r e s e n t e d t h i sm e t h o dm e a s u r et h ed i s t a n c eo ft h es k e l e t o n s b a s e do nt h em a x i m a lc o m m o ns u b - g r a p ho f t h e i rc o r r e s p o n d i n ga t t r i b u t e dr e l a t i o ng r a p h s l a s t l y , as k e l e t o n - b a s e de x p e r i m e n ts y s t e mf o ri m a g ed a t a b a s er e t r i e v a li sd e s i g n e d 第1 i 页 国防科学技术大学研究生院学位论文 a n di m p l e m e n t e do nt h eb a s i so ft h es y m m e t r yb a s e do b j e c tr e p r e s e n t a t i o na n dr e c o g n k i o n t h e o r i e s n l ep r o s p e c t i v er e s u l ti ss h o w n k e y w o r d s ：s y m m e t r y ；s k e w e ds y m m e t r y ；s k e l e t o n ；a t t r i b u t e dr e l a t i o ng r a p h ； g r a p hm a t c h i n g ；d i s t a n c et r a n s f o r m a t i o n ； 第l i l 页 国防科学技术大学研究生院学位论文 第一章绪论 目标的表示和识别技术是模式识别和图像理解领域的核心环节之一。现有 的目标表示方法往往是基于目标的图像特性和几何特性的。本论文重点讨论了从 大量人造目标和自然目标中广泛存在的对称性出发而导出的目标表示和识别技 术。 我们将首先介绍课题的背景和研究意义，其后表述论文的主要研究内容， 接着总结论文的主要研究成果，最后说明论文的内容安排。 1 1 课题的背景与研究意义 计算机视觉和图像理解领域的主要目标是赋予机器以视觉功能，使机器能够 主动地观察周围环境、智能地分离和表示目标，并最终自动地识别目标。m a r t 所创立的视觉计算理论为实现这个目标奠定了理论基础3 。为了完整地理解视 觉，他认为必须在三个不同的层次上对它进行解释，这三个层次是计算理论( 计 算的目的是什么? 为什么这一计算是合适 的? 进行计算的策略是什么? ) 、算法( 如 输入图像或视频 何实现计算理论? 输入输出的表示形式是 什么? 如何实现这些表示形式的变换? ) 以 及硬件实现( 在物理上如何实现这种表示和 算法? ) 。从计算理论的层次来看，视觉信 息处理必须用三级内部表示来加以描述，它 们是要素图( 图像的表象) 、2 5 维图( 可见 表面的表象) 和3 d 模型表示( 用于识别3 d 目标的形状的表象) 。 在上述理论的基础之上，通常的机器视 觉系统包括低层处理、中层处理和高层处理 三个过程。7 1 ( 如图卜l 所示) 。 低层处理过程的主要任务是从输入图 像中检测感兴趣目标的符号表示( 如区域和 轮廓等) 。图像分割是这个过程中的关键技 知识 识别结果 图l0 1 计算机视觉的结构流图 术。图像分割是将图像划分为若干个有意义的目标的过程，它所利用的图像信息 可以是色彩信息、纹理信息、体视信息、图像序列中的运动信息以及阴影信息等。 它是构造图像理解系统的关键环节。 中层处理过程的主要任务是通过对目标符号的处理来获得目标的可以用于 第1 页 国防科学技术大学研究生院学位论文 分类识别的数值的或非数值的表示阻耵。目标的形状分析是这个过程的主要技术， 它主要包括形状表示和形状描述两个方面。形状表示方法的目标是获得能保持原 始目标的重要的特性的非数值的表示，其中“重要性”根据具体的应用的不同而 有所不同：形状描述方法的目标是获得给定形状的数值的描述矢量( 又称为特征 矢量) ，通常要求这些矢量对于图像的变换( 如平移、旋转和伸缩等) 具有不变 性质。基于区域符号的形状分析方法被称为内空间法，而基于轮廓符号的方法被 称为外空间法。 高层处理过程的任务是通过综合目标的表示以及用于理解的先验知识来识 别目标。形状匹配或分类是其主要技术，它通过比较目标与模型之间差异的大小 来实现。在这个过程中通常要涉及到最优分类器的设计和训练，分类器的噪声稳 健性分析等相关问题。 从目前的研究状况来看，低层处理往往与具体的应用密切相关，在短时间内 设计统一的、普适的、稳健有效的图像分割算法仍然非常困难。1 。它不是本文的 重点，在后面的叙述中，我们假定已经获得了目标的符号表示。 在中层处理和高层处理方面，研究者们提出了许多形状表示和识别的框架， 例如基于不变矩的方法、基于f o u r i e r 描述子的方法、基于形状矩阵的方法、基 于弯曲能量的方法、基于随机过程模型的方法、基于多边形近似的方法以及基于 形态学算子的方法等o ”。这些方法描述了形状的不同侧面，并成为许多成功的系 统的重要组成部份。但是值得指出的是，在许多情况下它们是不充分的，例如它 们无法描述诸如形状中有几个洞、形状是否对称、形状存在几个组成部分以及各 部分的连接关系如何等问题。随着目标形状的复杂性和变化性的增加，进而导致 目标的类内差异增大和类间差异减小的情况下，这些方法的局限更加明显，必须 研究新的形状表示及相应的分类识别算法。 有鉴于此，人们希望新的目标的表示方法能同时满足下面几个准则： ( 1 ) 可以在基于图像数据的底层处理和基于语义信息的高层处理之 间建立联接的桥梁，从而方便识别系统的构建； ( 2 ) 可以研究目标的整体和部分之间以及部分与部分之间的关系，从 而便于实现目标之间基于共同部分的比较过程： ( 3 ) 可以很好地模型化人类视觉感知的某些特性( 如对称特性) ，从 而加快识别过程； 为了获得具有这些能力的目标表示技术，本文将从目标的对称特征出发，通过研 究它们与目标的内在关系以及它们在目标表示方面的优势，从而最终发展出基于 对称结构的目标表示和识别技术。 第2 页 国防科学技术大学研究生院学位论文 1 2 论文的主要研究内容 对称性是大量人造目标和自然目标的共同属性，它提供了人类视觉感知目 标形状的关键线索。基于对称特征的目标表示和识别技术是从6 0 年代兴起并一 直活跃到现在的研究领域口拽2 3 珈】。它是模式识别、人工智能、感知科学、图像 处理以及计算几何等的交叉学科。它主要研究两个方面的问题：( 1 ) 人类视觉如 何感知目标中的对称特征：( 2 ) 利用计算机如何检测、量化和描述目标的对称特 征。 作为目标的本质特征，对称具有许多重要的应用，包括目标分割、视觉检 查、形状表示、注意力引导、自动字符识别、自动指纹识别、文档图像分析、医 厂基本对称 对称 l 。义对称 僵霾瓣 l 基本旋转对称 d r d 一 其中p 为非负整数，q 为正整数。 性质2 4 - 1 标准的基本反射对称图像的广义复矩为实数，即它的相位为肋。 若将标准的基本反射对称图像旋转角度卢，则其广义复矩g q ，的相位为砟，。= q p - k x ， 即有p ：垒l 坚，其中k ：0 , 1 ，g 一1 。对于任意图像，若其广义复矩g q 。不为零，则 q 它的反射对称轴必然包含在上述g 个轴组成的集合中，此时，反射对称轴的检测问题 就变为检测多个非零广义复矩的轴集合的交集的问题。设有 ? 巳，v o ：q = q ，q 2 ，) ，其 中q ，的轴集为4 ： 屏：生也：女：o ，l 丹 ( 扛l ，2 ，) ，则目标的基本反射对称轴集 l 坼 j 为肚，：怠4 。 性质2 - 4 2 若图像是一个足一r s l ，当q 不是k 的整数倍时有g q ，；o 。若 第1 2 页 国防科学技术大学研究生院学位论文 p c ，。，i = 1 ，2 ，j 为检测到的非零广义复矩集，则瓣的个数足等于集合h ：扛1 ，2 ，j ) 中 整数的最大公约数( 其中i ，为预先设定的常数) 。另外，存在整数集k ，：= 1 , 2 ，j 使 得k = 圭x ，q ，取下列线性规划问题的解集中绝对值较小的数作为这个整数集中的元 尸l 素： m i n z ，q j 5 t e x q g 1 h t 。m a ，x ，q 则目标的基本旋转对称轴是从坐标原点出发，角度为 壹x ，九。，+ o 一1 ) x 2 z 只= 丝_ 一 田 户l 的直线( 其中，i = 1 , 2 ，k ) 。 在利用广义复矩检测对称轴之前，必须解决的一个重要问题是如何检测非零的 广义复矩，它包括两个方面的内容：( 1 ) 确定恰当的p ；( 2 ) 在保持p 不变的情况下 确定q 。 用图像的f o u r i e r 谱的转换能来选择p ：对于卜d 函数h p p ) 和它的f o u r i e r 变 换： b p ) ；r “，p p 9 胁 h 翰= 去毫h p 悱蝌拍 显然有能量等价关系f ”k ，p 1 2 d 目；2 z 妻忙，圳2 成立。注意到g c p , q = h p 。) ，则比例 旷l 一篇 可用来度量卜d 函数h p p ) 的周期性的强度，a p 越大则说明函数 。p ) 的周期性越强。实 际上，一旦a ，0 0 5 成立，则选择此时的p 作为广义复矩的固定量。 利用剩余能量来选择口：总能量中剩余的转换能的比例为 第1 3 页 国防科学技术大学研究生院学位论文 ：畦尘垫蚓 1 。 m p 籼 若b 。越小则说明剩余的转换能越少。实际上，一旦b 。t0 0 1 成立，则取此时的q 为广义 复矩的阶数。 根据性质2 4 1 和性质2 4 2 以及确定p 和q 的技术，基本反射对称轴和旋转对 称轴的检测算法包含下面的步骤： ( i ) 计算图像的质心b 。加。，m 。，m 。) ，使图像中心化； ( 2 ) 为该图像选择恰当的p ； ( 3 ) 在6 。，o 0 1 且q o 时取正号，当c ，0 或c ：0 且日t 0 时取负号。 另一种方法是用a 和口来直接表达目，具体方法是：如图2 6 ，首先考虑三角形 a , i d e ， b a d = z 一妇+ 卢) ，再考虑三角形a , 4 d b ，z a b d ：z b a d f ，2 = z ，2 一缸+ 卢) ，再考虑三 角形a o b c ，0 ：z 1 2 一z a b d ：a + 芦，则扭对称轴的直线方程为： p = x c o s 缸+ 卢) + ys i l i 缸+ 卢) ( 2 5 ) 三、扭对称的表示 下面介绍检测扭对称轴的主要方法，这些方法用到了上述的基本约束，且适用 第2 2 页 d一 旦虬 拈 。 暑| 音吗咭c 矿 一 舻 国防科学技术大学研究生院学位论文 于不同的目标数据。它们包括基于不变特征的方法、基于h o u g h 变换的方法以及基于 规则化的方法。 1 、适用于完整轮廓数据的检测方法 当己知扭对称目标的完整边界曲线r 时，b r u c k s t e i n 等。”提出一种利用不变特 征进行扭对称轴检测的新方法。他们主要回答了下面这个一般性问题：给定一个形状 s 和一个平面变换的连续群：异z r ：( 其中。为这个变换群的参数) ，如何根据一个 被变换扭曲的形状珞啦) 来推断原始形状是否存在基本反射对称轴? 他们利用“广义曲率”一“不变弧长”函数来取代原先的“曲率”一“弧长” 函数来描述形状从而使这种描述对于给定的变换群具有不变性质。他们的主要思路 是：首先获得关于边界曲线的，一不变测度r 和r 一不变特征p ，且这个测度和特征可以 通过曲线局部的微分特征或几何特征来计算，则函数p ( f ) 对于变换群具有不变性； 由于恒等变换也属于这个变换群，故形状s 与扭曲的形状巧0 ) 具有相同的函数p o ) ( 除 了由于初始化位置的不同而产生的偏移外) ，若s 是基本反射对称的，则v e ( s ) 的函数同 s 的函数具有相同的对称结构。 对于以近似多边形表示的目标，在仿射变换群和透视变换群意义下，他们给出 了上述不变测度和不变特征的具体形式，并给出了扭对称检测算法。设近似多边形的 顶点序列是把，岛，以 ，他们注意到多边形中顶点的序号l ，2 ，n 对于仿射变换和透视 图2 7 近似多边形在顶点只处的几何关系 变换都是不变的，故以这个序号作为 r 一不变测度。又由于单个不变特征列 不能唯一地重构原始形状，他们采用两 个不变特征列来唯一地表征目标。 由于面积比是仿射变换的不变 量( 即原始多边形中任意两个三角形的 面积比等于仿射变换后对应的三角形 竺型：型 沪e ! 刚) = 黝= 表鹄 第2 3 页 国防科学技术大学研究生院学位论文 任意共线且不重台的4 个点为 ，巴，马和只的交比定义为 。 c r ( e , 眦，= 躲糍捌 由于交比是透视变换的不变量，即若任意透 视变换将共线且不重合的4 点焉，b ，弓和 变换为同样共线且不重合的4 点岛，9 2 ，岛和 q 4 ，则有c r ( p , ，b ，b ，只) = c r ( q 。，。2 ，q 3 ，凸) 。所以 他们利用线段的交比来定义透视不变特征c 和一。图2 8 显示了多边形在顶点b 处的几 何关系，其中可是直线异一：墨。与只+ 。毋的交点， 4 为直线4 + ：与直线只的交点，4 j 为直线 图2 - 8 多边形在顶点只处的几何关系 4 只+ ：与直线鼻一，毋。的交点，同样可以确定盯，皿和彤，则有： o ) = c r ( a ；，a j , _ ? ，b + 2j 。o ) = c r ( b ：，b i ，计，只一：j 在获得了多边形在仿射变换群和透视变换群下的不变特征列营似f 8o ) 后( 其中f = p 或 f ：) ，就可以用来检测两类对称： 顶点对称：若不变特征在顶点p 处出现了回文结构，即 f 8 0 一曲= f o + 七lf o 一砷= f 8 d + t ) ； 边对称：若不变特征在边e 一，只处出现了回文结构， 即 f 8 0 k 1 ) = f o + t lf o t 一1 ) = - r 0 + ) ； 若出现了两个对称顶点，则过这两个顶点的直线就是多边形的一个扭对称轴；若出现 了两个对称边，则过这两个边的中点的直线就是多边形的一个扭对称轴。 该方法为扭对称检测提供了一个统一的理论框架，具有重要的理论意义。但是， 由于多边形近似算法的精度和对于噪声的稳健性有限，且仿射变换和透视变换会产生 一些畸变的情形( 如本来不同的直线经过变换在图像中会重合等) ，使得在具体应用 中困难较大，从而基于上述思想设计稳健的检测算法仍需要进一步研究。 2 、适用于边缘数据的检测方法 当已知目标以边缘表示的不连续边界时，研究者们提出了基于h o u g h 变换的检 测技术来检测目标的扭对称轴。根据扭对称轴的直线方程( 式2 4 和式2 5 ) 的不 同，这类算法的具体操作也不相同。下面介绍利用式2 - - 4 的检测技术( y i p 1 ) ，利 第2 4 页 国防科学技术大学研究生院学位论文 = = = = = = = = = = = = = = = = = = = i = = = = = = 皇= = = = = = = = = = = = = = = = = = = 暑= = 皇= = = = = = = = = = = = = = = = = = = = = 用式2 5 的检测技术见l e i 等“”的工作。这个方法包括三个步骤。 利用h o u g h 变换测扭对称轴 对于每个边缘点对b o y ) 和0 0 ，y 小计算它们的中点m = 仁+ p j ) 2 ，以及连接只和 p ，的直线与横轴正向的夹角( 即图2 - 6 中的扭角) 卢：。一f 上丑 l t j ， 并把扭角相同的中点收集起来。 在h o u g h 空间初始化d ，o ) 的一个累加器，对于每个扭角进行后面的操作：对于 具有当前扭角的任意两个中点m 。g 。乩) 和m 。k ，儿) ，实际上，它们就是图2 6 中某个 梯形的上下底的中点，故利用式2 4 可以获得当前扭对称轴的参数，o ) ，并使h o u g h 空间中对应的单元的累加器的值加1 。 当上述投票过程结束后，检测h o u g h 空间中的所有可能峰( 每个峰对应一个扭 对称轴) 。 计算扭对称轴为。，以) 的扭角成 首先初始化卢的一个累加器，然后对于每个扭角卢进行后面的操作：对于具有 当前扭角的每个中点g ，y ) ，计算它到当前扭对称轴( 以) 的距离 d = l p ，一jc o s o , 一ys i n 以i ( 2 7 ) 当这个距离小于某个预设门限r 时，使卢对应的累加器的值加1 。最后当投票过程结 束后，累加器中值最大的扭角即为，。 确定与扭对称轴，以) 相关联的目标的边界点 对于每个边缘点对b g ，) 和弓g ，y a 若它们的扭角声与成相同，则利用式2 7 计算它们的中点到扭对称轴；，以) 的距离d ，若这个距离小于某个预设的门限r 时， 则认为异和，是与扭对称轴d ；，铂相关联的目标的边界点。 上述方法的特点是可以同时检测目标的全局扭对称轴和局部扭对称轴，并且可以 得到与扭对称轴关联的目标的不连续边界，缺点是计算复杂性较高。克服上述问题的 有效途径是利用随机h o u g h 变换、层次h o u g h 变换、模糊h o u g h 变换啪3 或u p w r i t e n 9 1 来检测扭对称性。这些技术有的可以加快计算效率，有的可以较好处理精度一不确定 性对偶问题，即使在h o u g h 空间的量化较粗的情况下也可以获得精确可靠的解。 3 、基于灰度数据的形状表示 第2 5 页 国防科学技术大学研究生院学位论文 本章的第二节介绍了s h e n g 等8 1 利用非零广义复矩检测基本对称轴的方法，对 于由于仿射变换而导致的扭对称形状，他们又提出了一种基于3 阶常规矩的规格化方 法。 设，“，v ) 为由原始图像，g ，y ) - 经 射变换而得到的变形图像，则有： 几小瓜卅4 i 其中，为仿射变换的齐次矩阵表示。可以证明，它们的常规矩之间存在着下 面的关系( 这是本节中公式n ：d r m d 在3 d 上的扩展) ： 其中：m ，。为原始图像，k ，) 的埘一阶矩，m k 为原始图像，( 1 ，v ) 的p q 一阶矩，即 枷】= 端 小枷】。谢 现在的问题是：已知变形图像，0 ，v ) 以及它的矩，如何得到一个新图像几7 。y ) 使它对于 任何仿射变换均保持不变( 意即无论对原始图像，b ，y ) 进行哪种仿射变换，用变换后的 版本巾，v ) 均可求得相同的几，y ) ) ，这个图像被称为紧致( c o m p a c t ) 图像，获得紧致 图像的算法被称为紧致化算法。可以证明，满足下面条件的图像就是紧致图像： 生 雕) _ ，) 训压怫：鬻 l札j 其中， 和如是矩阵ur 的特征值， 也m o 叫- - m t “z l o ，乏1 叠o 吨i l 研：l 一埘：o 埘函 m ；2 一m “ j 且e = ke ：】，其中e 和e ：是矩阵u r 关于 和如的特征矢量，d 是预先指定的限制图像 尺寸的参数。 他们首先获得扭对称图像的紧致图像，然后检测紧致图像的基本对称轴，然后 利用上述过程的逆过程将它们变换到扭对称图像表面，从而最终完成扭对称检测。 第2 6 页 铷 o m一 = d 叫 埘舵 堍而 ，i ， 肿 肿 肿 。【 1 | 1，j o 啦吒k q q “ vjijio且 m胛， 嘞 m 坍 小 坍 = i i i i i j 坩 h 也o 旧旧旧 国防科学技术大学研究生院学位论文 1 1 2 3 基于分布式主动智能体的基本反射对称检测技术 在本章第二节中我们定义了图像的局部的基本反射对称度，它是通过中心像素 的位置、邻域半径以及与横轴的夹角来刻画的。对称度越高则说明相应的对称轴的显 著性也越高。我们注意到下面两个事实： 在显著性较高的局部对称轴方向上存在同方向的显著性较高的对称轴的可 能性很大； 对称轴的邻域半径越大，则它的显著越大，全局性越强； 近来，智能体( a g e n t ) 作为一种具有感知能力、问题求解能力和通讯能力的抽 象实体，已经成为人工智能和计算机科学的热点研究对象。“”3 。l i u 等“”设计了一类 可以随机搜索并检测一致区域的智能体，并利用它们来分割文档图像和c t 图像。我 们注意到，通过恰当地重新定义该智能体的行为模式，可以使它们非常适于基本反射 对称轴检测问题。 基于上述考虑，我们提出一种基于分布式主动智能体的对称轴检测的新技术。我 们设计了一种可以感知邻域环境并且具有定居、发展、迁徙和死亡等行为模式的问题 求解型智能体。该智能体首先通过计算其邻域环境的对称度来判断是否存在显著的对 称轴，若存在，它就定居在这个邻域环境中，否则它就通过迁徙行为改变其在图像中 的位景，同时逐渐增大年龄直到死亡。已定居的智能体通过扩大邻域半径和在对称轴 方向上繁殖后代来继续随机搜索更为显著的对称轴。最后，我们将那些位置相近、方 向相同的局部对称轴编组并连接为全局性更强的对称轴。这种技术的优点是适用于任 意灰度图像，可以检测出所有的局部基本反射对称轴，而且每个智能体独立工作，适 于并行实现。 1 、智能体的行为描述 本文设计了一种分布式主动智能体，它直接附着在图像的单个像素上，具有可 变的邻域半径和年龄，它主动地计算其邻域环境的图像特征和反射对称度，并通过定 居、发展、迁徙和死亡这四类行为不断地寻找更好的对称轴。当智能体附着在象素 0 。，y o ) 处，且其邻域半径为，时，它的邻域环境就是，而，关于轴岛的对称度s o ( f ) 可 通过本章第二节中的方法来计算。下面介绍智能体的主要行为模式。 定居 智能体具有感知其邻域环境并且判断该环境是否适合生存的能力，当邻域环境适 于生存，它就在这个环境中定居下来。若智能体一的邻域环境满足下面两个准则就让 它定居：( 1 ) 具有特定的图像特征：( 2 ) 具有显著性足够高的轴。 第2 7 页 国防科学技术大学研究生院学位论文 准则1 允许我们加入具体应用中关于邻域环境的先验知识( 如对邻域环境的灰度 水平、变化程度以及纹理属性等的限制) ，用来保证智能体定居在有意义的图像上下 文中，从而避免平凡的情形并加快计算的速度。本文采用的图像特征是平均灰度和方 差，设邻域环境的平均灰度为五，方差为v ：，若厶c 五t 厶。和v ：。c 嵋cv 同时成立， 则称这个邻域环境满足准则1 ，其中厶。，嗍，v 二和v 均为预定的门限。 准则2 要求邻域环境对于某些轴具有较高的对称度，其测试方法如下：为计算方 便，我们等分区间【0 ，z ) 获得 个轴，它们与横轴正向的夹角分别为b ；卅 ( f = o ，n 一1 ) ，计算其邻域环境关于每个轴i 的反射对称度品，若黾，t ，则称 邻域环境满足准则2 ，其中r 为预定的门限。此时，称只为成功定居方向，称它们中 具有最大局部对称度的方向为主定居方向。 当智能体同时满足准则1 和准则2 时，它就定居在这个邻域环境中。 发展 为获得更大的生存空间，定居在某个邻域环境中的智能体a 具有扩大自己的感知 范围( 即邻域半径) 以及繁殖后代的行为趋向。 扩大感知范围可以使它捕获图像中更全局、更显著的对称轴，具体方法是：首先 获得它的主定居方向及其相应的轴，然后在逐渐增大智能体的感知半径r 的过程中， 计算此时的邻域环境关于该轴的对称度，直到不满足上述的准则2 为止。 注意到在己定居的智能体的成功方向上出现可定居的邻域环境的可能性很大，若 在该方向上产生新的智能体，则可更容易地检测到显著的局部对称轴。智能体通过繁 殖子代来实现上述目标，具体的方法是：设智能体a 的儿子的个数为 ，成功方向的 个数为d 。，当前的感知半径为。以各成功方向的对称度在它们的总和中所占的比例 为概率随机生成繁殖方向d ，同时生成均匀分布于区间( - ，) 的随机数r ，则在a 的 成功方向d 上距离为，的像素上生成它的一个儿子：继续上述过程直到产生了m 个儿 子。 迁徙 那些没有定居成功的智能体，为了获得生存和发展的机会，它们必须在图像中不 断移动，以便捕获适于生存的邻域环境，这个过程称为迁徙。在迁徙的过程中，智能 体的年龄逐渐增大，当其年龄大于生命周期时就死亡。智能体的这种随机搜索行为是 至关重要的，它可以保证智能体不断发现新的显著性较高的轴。 迁徙过程的具体方法是：对于第g + i 代的未定居智能体a ，寻找它的父亲，若父 亲不存在，则随机地选择一个迁徙方向e ；若它的父亲。缸) 存在，再通过父亲找到它在 第2 8 页 国防科学技术大学研究生院学位论文 第g + 1 代的堂兄弟们- ) ；然后统计它们中通过迁徙行为而成功定居的那些智能体的 迁徙方向的直方图，最后以每个迁徙方向在直方图中的值在它们的总和中的比例为概 率，随机产成一个迁徙方向e 。另外再生成一个均匀分布于区间( _ r ，r ) 的随机数，其 中r 为事先给定的最大迁徙距离，则数对( p ，) 就确定了a 的新位置。这个机制在总结 了家族成功迁徙的经验的前提下可以在概率意义下保证智能体快速定居。 2 、编组和连接智能体 当上述随机搜索过程结束后，每个定居成功的智能体就确定了一个局部对称轴， 所有这些智能体就形成一个对称轴图。为了从这个图中获得图像的主要对称轴，本文 采用一个先入先出的队列( f i f 0 ) 并执行了下列步骤：在圭定居方向为i 的智能体中 找到s d s 最大者，将它加入到队列的尾部：当队列不空时开始循环，获得其中第一个 智能体，然后在它的邻域内寻找处于它的主定居方向上且主定居方向也为i 的智能体， 并将它们加入队列的尾部，如此继续；上述过程结束后，曾经存在于该f i f 0 中的智 能体就形成了图像的一个主要的对称轴，其s d s 为其中所有智能体的s d s 之和。然后， 我们从图中删除这些智能体及其邻域中的同方向智能体，重新执行上述步骤，即可得 到其它的主要对称轴。 3 、利用智能体检测灰度图像中的对称轴的主要步骤 ( 1 ) 初始化过程：生成一组智能体缸雀，随机产生它们的中心位置，使它们的 感知半径为r 。( 预先给定的参数) ，年龄为o ：同时将它们加入到活动智 能体队列中： ( 2 ) 执行下列步骤直到队列为空或图像像素已全部被标记： ( 3 ) 对于中的每个智能体a ，执行如下步骤： 检查该智能体是否可定居，可则转，否则转； 使a 扩大感知范围且繁殖后代，同时将这些后代加入到中；记录n 的 信息并将它从l 中剔除，标记a 的中心像素的某个小邻域； 标记a 的中心像素的某个小邻域，然后迁徙a ，若。的年龄超过生命周 期，则将。从中剔除使它死亡： ( 4 ) 编组并连接上述过程得到的智能体，获得最终的主要对称轴。 4 、实验结果 为了验证该方法的效果，我们对若干自然图像进行了实验。实验的参数设置为： 初始智能体的个数为1 0 0 ，它们的年龄周期为1 0 ，子代个数m 为1 0 ，最小感知半径月曲 第2 9 页 国防科学技术大学研究生院学位论文 为3 0 ，最大迁徙半径r 为3 0 ，平均灰度的上限f m 。和下限，m ，。分别为2 0 0 和i 0 0 ，方 差的上限v 。2 。和下限2 。分别为2 0 0 和3 0 ，最小对称度门限r 为0 ，9 。 从图2 - 9 到图2 1 2 显示了4 幅自然图像，分别为花、树丛中的房子、路标和树 图2 - 9 花的灰度图像及其局部基本反射 对称轴 图2 1 1 路标幽像及其局部的基本反射 对称轴 图2 1 0 树丛中的房屋及其局部的基本反射对称 轴 图2 1 2 树木图像及其局部的基本反射对 称轴 水图像。由于模糊、噪声以及遮挡的影响，难于提取其中的对称结构的轮廓。显然， 这些图像中存在着大量的局部对称轴，这里我们只给出其巾s d s 最大的几个局部对称 轴。对称轴可通过一个五元组( 训，r ，口s d s ) 来描述，其中( x ，) 为轴的中心，r 为邻域半 径，口为轴的方向，s d s 为轴的尺度相关对称度。经过计算我们得到图2 9 中的两个 轴分别为( 1 0 9 ，15 013 t 口4 16 3 0 29 5 )和( 1 0 9 15 0 ，9 9 ，如4 ，9 2 129 4 ) ，图2l o 中的轴为 第3 0 页 国防科学技衣太学研究生院学位论文 ( 1 0 8 ，1 0 4 ，5 2 ，f 2 ，2 5 1 47 2 ) ，图2 1 1 中的轴为( 1 2 7 ，1 2 1 ，1 1 6 ，口2 ，1 2 6 4 86 4 ) ，图2 1 2 中的两个轴分 别为( 1 8 4 ，1 0 9 ，8 0 ， 2 ，5 8 8 8 ) 和0 1 0 ，1 2 4 ，7 0 , 3 n ，4 ，4 4 1 0 ) 。在图像中我们以白色直线段表示该对称 轴，以白色的圆表示对称轴的邻域环境。从实验结果中可以看到，这些对称轴捕获了 图像中的主要对称结构，获得了与人类视觉感知一致的结果。 本算法的串行程序在奔腾2 - 3 0 0 微机上执行大约5 分钟后即可结束迭代过程，并 得到最终的主要对称轴。从初始智能体集开始，在先前的若干次迭代中将产生大量的 智能体，然后它们逐渐变为静态或死亡，并最终完全标记图像中的每个象素，从而结 束迭代。显然串行算法的计算复杂性仍然较高，但是注意到智能体一经产生就完全独 立运行，所以适宜于采用特定的并行结构来实现。 2 4 小结 本章系统地总结了基本对称和扭对称的基本概念和有关理论，并根据目标的不 同图像表现以及有关对称轴的显著性的要求实现了对检测算法的分类，从而为我们在 各种成像条件下构造检测系统提供了出发点。 我们特别强调了基本对称和扭对称的内在联系。对于每种检测算法，我们分析 了它的主要思路和步骤，并研究了它的优点和不足。在这些方法中，基于不变特征的 方法、基于广义复矩的方法以及基于局部对称度的方法尤其要引起足够的重视。它们 从一致理论方面和具体应用方面各有千秋，最有发展潜力。 为了克服直接从任意灰度图像中提取目标的基本对称轴的困难性，我们提出一 种通过模拟分布式主动智能体的行为模式的对称轴检测新算法。该算法将人工智能中 的研究热点和图像对称性分析问题有机地结合在一起。该技术模拟了生物适应环境并 逐渐发展的过程。算法的计算复杂性较高，但适合于并行实现，具有一定的发展前途。 第3 l 页 国防科学技术大学研究生院学位论文 第三章数字图像的距离变换 3 1 概述 距离变换是计算一个点集中所有点到另一个点集( 一般称为