（光学专业论文）基于区域分割与熵匹配相结合的序列图像帧间预测编码方法的研究.pdf

摘要 摘要 预测编码是八十年代发展起来的一种图像压缩编码方法。由于兼顾了图像序 列之间的时空相关性，在采用运动补偿技术之后，帧间预测的准确度相当高，近 年来在运动图像编码中得到了广泛的应用。本文主要研究帧间预测编码中的一种 基于运动对象的图像运动估计算法。 图像分割是运动补偿技术的基础，通过图像分割可以将图像划分为各个特征 一致性的区域，作为图像匹配单元。如果划分不当，将增加匹配过程的复杂程度， 并将造成重构图像的失真，所以我们讨论了几种常用的不同的图像分割方法，并 在区域跟踪分割的理论基础上，根据生长点的提取及生长方法的不同对区域生长 法做了一定的改进和完善，实验表明，它在分割精度、区域连贯性和信息完整性 上都有优于其他几种分割方法之处，是后面做好图像匹配的关键。 对于分割后的图像，我们提取出其中的运动部分，得到要匹配的运动区域， 然后再用局部最小熵差匹配算法进行匹配，得到所需的重构图像。熵值反映的是 图像的统计特性，利用熵值来进行图像匹配是一种适应性强且非常有效的图像匹 配算法。它主要利用图像灰度的统计特性，求得各运动区域内的像素灰度分布， 再在搜索区间内对各个待匹配区域进行最小熵差的匹配。因为之前较为精确的提 取了图像中的运动部分，因此这里我们可以采用简化了的熵公式进行匹配计算， 从而提高匹配效率。同时由于该算法不存在门限选取、参数确定等人为因素的影 响，因此算法稳定性好，且能在一定程度上抵抗噪声和几何失真的影响。 区域生长法与局部最小熵差匹配的有力结合，充分利用了前后帧运动信息的 相关性，同时保证了匹配区域内运动矢量的一致性，提高了运动部分提取及运动 矢量估计的精确性，兼顾了图像的匹配效率，重构图像主观和客观效果都较好。 实验结果表明，基于区域生长与局部最小熵差匹配的帧间预测算法能够取得与 全域搜索法和三步法相当的正确匹配率和信噪比，重构图像质量较好，而匹配效 率却大大提高。同时，熵差匹配算法对具有一定噪声或旋转及形变的图像具有较 好的匹配效果，这些都是传统的块匹配法所做不到的。 关键词：序列图像；帧间预测编码：区域生长：局部熵差：图像匹配 i l l ： 兰堕里兰查堂望堂堡主兰堡笙苎 a b s tr a c t t h ep r e d i c t i v ec o d i n gi san e w t e c h n o l o g yo fi m a g ec o m p r e s s i o nd e v e l o p e di n 8 0 s b e c a u s eo f g i v i n ga t t e n t i o nt ob o t ho ft h et e m p o r a la n ds p a t i a lr e l a t i v i t i e so ft h e i m a g es e q u e n c e s ，t h ev e r a c i t yo f i n t e r f r a m ep r e d i c t i o ni sv e r y h i g ha f t e ra d o p t i n gt h e m o t i o nc o m p e n s a t i o na n dt h i s p r e d i c t i o nm e t h o dh a sb e e nw i d e l yu s e di nm o v i n g i m a g ec o d i n g i nt h i sd i s s e r t a t i o n ，an e wa l g o r i t h mo fi m a g em o t i o ne s t i m a t i o nb a s e d o nt h eo b j e c to ft h ei n t e r - f r a m ep r e d i c t i o ni ss t u d i e d i m a g es e g m e n t a t i o ni s t h eb a s eo ft h em o t i o nc o m p e n s a t i o na n dw i t hi tw ec a l l d i v i d et h ei m a g ei n t os e v e r a lr e g i o n sw i t ht h ec o n s i s t e n tc h a r a c t e rt ob et h eu n i t so f t h ei m a g em a t c h i n g ，i fn o t p r o p e r l ym a d e ，r e g i o nd i v i s i o nc a nc o m p l i c a t et h em a t c h i n g p r o c e d u r ea n dc a u s ed i s t o r t i o n i nt h er e c o n s t r u c t e di m a g e w es t u d ys e v e r a li m a g e s e g m e n t a t i o nm e t h o d sa n do p t i m i z et h em e t h o do fr e g i o ng r o w i n gt og e tb e t t e re f f e c t a c c o r d i n g t ot h es e l e c t i o no ft h ep o i n t sa n dt h ed i f f e r e n tg r o w i n gm e t h o d sb a s e d0 1 1t h e t h e o r yo ft h er e g i o nt r a c i n gs e g m e n t a t i o n o u rr e s e a r c hs h o w st h a t i ti sb e t t e rt h a n s e v e r a lo t h e rm e t h o d si nt h ea c c r d r a c y ，c o n t i n u i t ya n dc o m p l e t i o na n di st h ek e yo f t h e i m a g em a t c h i n gs u b s e q u e n t l y a f t e re x t r a c t i n gt h em o v i n gr e g i o n s ，w ec a nd ot h em a t c h i n gu s i n gt h el o c a l m i n i m a le n t r o p yd i f f e r e n c ea n dt h e ng e tt h er e c o n s t r u c t e di m a g et h a ti s n e e d e d e n t r o p y r e f l e c t st h es t a t i s t i c a lc h a r a c t e ro fi m a g ea n dt h em a t c h i n ga l g o r i t h mw i t hi ti s v e r yc o m p a t i b l ea n de f f i ：c t i v e i tc a ng e tt h ed i s t r i b u t i o no fp i x e lg r a y l e v e l i ne a c h m o v i n gr e g i o n a n dt h e nd o e n t r o p ym a t c h i n g w i t h e v e r ym a t c h i n gr e g i o n i nt h e s e a r c h i n gr a n g e b e c a u s eo ft h e a c c u r a t e s e g m e n t a t i o n ，w ec a n u s et h es i m p l i f i e d e n t r o p yf o r m u l at o e n h a n c et h em a t c h i n ge f f i c i e n c y t h i sa l g o r i t h mh a sv e r yg o o d s t a b i l i t ya n d c a nr e s i s tt h en o i s ea n dg e o m e t r yd i s t o r t i o nf o rn o ts e t t i n gt h ep a r a m e t e r s t h ec o m b i n a t i o no fr e g i o ng r o w i n gm e t h o da n dl o c a le n t r o p ym a t c h i n g u s e st h ei n t e r - f r a m em o v i n gi n f o r m a t i o na n dt h ec o n s i s t e n c yo fm o v i n g v e c t o rs u f f i c i e n t l yt oe n h a n c et h ee s t i m a t i o na c c u r a c ya n d t h em a t c h i n g e f f i c i e n c y o u ra l g o r i t h mh a sg o o do b j e c t i v e a n ds u b j e c t i v ep e r f o r m a n c e i n i m a g eq u a li t y t h er e s u l t so fe x p e r i m e n ts h o wt h a tt h ei n t e r f r a m ep r e d i c t i o nb a s e d o nr e g i o ng r o w i n ga n dl o c a le n t r o p ym a t c h i n gc a ng e tc o n s i d e r a b l ec o r r e c t m a t c h i n gr a t ea n dp s n rw i t hf sa n d3 s sa n dg o o dr e c o n s t r u c t e di m a g ew h i l e e n h a n c i n gt h em a t c h i n ge f f i c i e n c yg r e a t l y b e s i d e st h e s e ，e n t r o p ym a t c h i n g i v 摘要 c a n 荫tb e t t e re f f e c t t ot h ei m a g e sw i t hn o i s ea n dr o t a t i o nt h a nt h e t r a d i t i o n a lb l o c km a t c h i n gm e t h o d k e y w o r d s ：i m a g es e q u e n c e ：i n t e r f r a m ep r e d i c t i o n ：r e g i o ng r o w i n g ：l o c a l e n t r o p yd if f e r e n c e ：i m a g em a t c h i n g v 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进 行研究所取得的研究成果。除了文中特别加以标注引用的内容 外，本论文不包含任何其他个人或集体已经发表或撰写的成果作 品。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：王靓红岁秘) 彳。 日期：2 0 0 4 年2 月1 4 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权华南理工大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名： 王靓红多枷缸日期： 2 0 0 4 年2 月1 4 日 别雅辄揶孑 嗍僻堋蛐 j 第一章绪论 第一章绪论 1 1 图像的压缩编码 1 1 1 图像压缩编码概述 近年来，随着计算机与数字通信技术的迅速发展，特别是网络和多媒体技术 的兴起，图像压缩编码已受到了人们越来越多的关注 i 】。 图像编码与压缩从本质上来说就是对要处理的图像源数据按一定的规则进行 变换和组合，它是实现图像通信和存储的必要前提。图像数据的特点之一就是信 息量大。一幅5 1 2 5 1 2 、灰度等级为8 比特的图像，其数据量为2 5 6 k 字节。以四 通道卫星遥感探测器为例，以此视窗，一个时次即达1 m 字节。实际上，卫星遥 感探测时，视窗远大于此，通道远多于此，试想要保存这些图像数据，该需要多 大的存储空间。 在多媒体中，海量图像数据的存储和处理是难点之一。根据计算，一张6 0 0 m 字节的光盘，仅能存放2 0 秒左右的6 4 0 4 8 0 像索的图像画面信息。无疑，如不 进行编码压缩处理，那在多媒体信息保存工作中所遇到的困难和成本之高是可想 而知的。 现代通信中，图像传输已成为重要内容。工作中除要求设备可靠、图像保真 度高以外，实时性将是重要技术指标之。显然，在信道带宽、通信链路容量一 定的前提下，采用压缩编码技术，减少传输数据量，是提高通信速度的重要手段。 可以这样认为，没有压缩编码技术的发展，大容量图像信息的存储与传输是 难以实现的，多媒体等新技术在实际中的应用也会碰到困难。 图像信息压缩的可能性存在于图像本身之中。其中，明显可以利用的一点是 图像各像素之间的相关性。从统计观点出发，简单直观地讲，就是一个像素的灰 度值总是和其周围其他像素灰度值有某种关系，应用某种编码方法提取并减少这 些相关特性，便可实现图像信息的数据压缩。从信息论观点出发，就是减少图像 信息中无用的冗余信息，仍然保留有效信息，这样既减少了描述信息的数据量， 又保证了图像有效信息没有丢失，实现所谓信息保持编码。从图像信息的研究中 可以看到自然图像有很大冗余性，图像压缩编码的潜力是很大的。从另一个角度 出发，图像信息的信宿往往是人眼，而人的视觉系统接受信息的能力是有限的， 如灰度和空间分辨率都不是太高，即使是记录或显示设备，也往往受本身特性的 限制，只能接受某种程度量的信息，而并不能全部接受。所以可以根据图像信息 固有的统计特性和信宿接受能力，尽可能的去除无用信息，进行所谓的保真度编 码( 非信息保持编码) 。 华南理工大学理学硕士学位论文 1 1 2 图像压缩编码技术概述 图像压缩编码的研究始于4 0 年代，丽从7 0 年代开始到8 0 年代中后期，相关 学科的迅速发展和新兴学科的不断出现为图像压缩编码的发展注入了新的活力， 人们对图像信息需求的剧增也有力的促进了图像压缩编码技术的进步。冗余度压 缩编码、分形编码、小波编码【2 】，熵压缩编码等图像处理技术不断涌现，为图像 编码技术的发展提供了有力的条件。 1 1 2 1 冗余度压缩编码 减少或完全去除行内相邻像素间、帧内相邻像素行间以及帧间对应像素间的 相关性( 冗余) ，以减少存储、处理及传输的数据量，这一过程称之为冗余压缩。 冗余度压缩法的核心是基于统计模型，减少或完全去除源数据流中的冗余，同时 保持信息不变。如把图像数据中出现概率大的灰度级以短的代码表示，概率小的 灰度级用相对长的代码表示，处理的平均码长必然短于未压缩编码前的平均码长。 在解码过程中，可以根据相对应的规则或算法，将冗余量插入到图像数据中去， 严格恢复原图像实现编码与解码的互逆。因此，冗余压缩编码又称为无损压缩 或是无失真压缩。它包括哈夫曼编码、算术编码、游程编码、香农编码及轮廓编 码等几种常用的编码方法。 1 1 2 2 分形编码 分形图像编码是在m a n d e l b r o t 分形几何理论的基础上发展起来的一种编码方 法。分形理论是欧氏几何相关理论的扩展，是研究不规则图形和混沌运动的一门 新科学，它描述了自然异物体的自相似性，这种自相似可以是确定的，也可以是 统计意义上的。m b a r n s l e 引入迭代函数系统( i f s ) 来刻画这种自相似性，并将其 用于图像编码。该方法需要人工干预下进行，为此他的学生j a c q u i n 提出了基于迭 代压缩变换的自动分形图像编码方法，将分形在图像编码上的应用推进了一大步。 1 1 2 3 小波编码 1 9 8 9 年，s g m a l l e t 首先将小波变换用于多分辨率图像的描述。这个多分辨率 的图像描述叫做图像的小波分解。小波的图像分解方案实际上是属于子带分解的 一个特例，小波变换特别要求滤波器的正则性。小波分解是完备的、正交的、且 是多分辨率的分解。在空间域里，小波分解将信号分解为不同层次，每一层次的 分辨率不同。由于小波分解方法本身的正交性，分解后不同层次数据之间的相关 性完全由数据本身的相关性决定。由此排除了由于分解方法内在的相关性而造成 2 第一章绪论 数据之间呈现相关性的混淆。小波变换在空间域中进行多层次分解运算的同时形 成了频率域中的多层次分解。 1 1 2 4 熵压缩编码 熵压缩编码是一种以牺牲部分信息量为代价而换取缩短平均码长的压缩编码 方案。它利用人的视觉心理特性，在允许的失真度下，减少信息熵。熵压缩编码 后恢复的图像与原图像有一定的差别，因此属于有损编码。它包括以下几种基本 方法： 1 变换编码 从理论上来说，正交变换本身不能对图像数据进行有效的压缩。但正交变换 改变了图像数据的表现域或表现形式，为压缩编码提供了可能。变换编码也就是 经正交变换( d f t ，d c t ，碰礴) 获得图像的变换域，再对变换系数作抽样编码的一 种编码方法。它包括区域编码、阈值编码等两种常用的变换编码方法。 区域编码是选择能量集中的区域进行编码，舍弃能量为零和零星能量区域， 从而达到数据压缩的目的。而闽值编码方法则是按变换系数的幅度进行编码的方 法，它将变换系数与门限值相比较，大于门限的给予编码，否则舍弃。 2 预测编码 预测编码( p r e d i c t i v ec o d i n g ) 是统计冗余数据压缩理论的重要分支之一，其理 论基础是现代统计学和控制论，而其技术基础是信号的最佳预测和最佳量化。 预测编码主要是减少数据在时间和空间上的相关性，对图像信源而言，就是 减少图像帧内和帧间的相关性，分别称为帧内预测和帧间预测。它是根据某一模 型利用以往的样本值对新样本值进行预测，然后将样本的实际值与其预测值相减 得到一个误差。再对这个误差进行编码。如果模型足够好且样本序列在时间上的 相关性较强，则误差信号的幅度将远远小于原始信号，从而可以用较少的电平来 对差值进行量化，进而得到较大的数据压缩结果。如收发两端的预测器完全一样， 且发送端不经过量化，则在接收端完全可以实现无失真的恢复图像，即预测本身 并不引入误差，只是由于在实际使用过程中常常使用量化器以提高压缩比。因此， 在接收端经解码得到的预测误差值存在量化误差，导致最终恢复的图像也出现失 真。在预测编码方法中，既可以利用图像信号的统计特性，又可以利用人眼的视 觉特性，以降低编码率。 预测编码中最常用的就是线性预测法，也称为差分脉冲编码调制( d p c m ) 。 此方法较为简单且易于硬件实现。图像的一维预测或二维帧内预测中，一般都 采用此编码方法。 预测法在图像压缩编码中应用时，还普遍采用帧闻预测，也就是由前一帧或 前几帧图像来预测当前的图像，这样只需要对帧间误差进行量化编码即可。帧间 华南理工大学理学硕士学位论文 预测利用各帧图像之间的时空相关性，可以减少时间域上的冗余度。如果仅仅是 将上一帧相同空间位置上的像素值作为待编码的当前帧的预测值，则对图像中的 静止背景而言效果较好，而对图像中的运动部分效果则相对较差。如果知道待编 码的像素是上一帧哪个位置移过来的，那么在预测时以那个位置上的像素值作为 预测值，则预测的准确性将大大提高。换句话说就是通过运动补偿帧间预测可以 使预测误差的方差与原始图像相比大大减小，从而降低码率，提高压缩比。目前 运动补偿技术已被广泛应用于视频压缩的国际标准之中，如h 2 6 1 标准、m p e g i 标准、m p e g 一2 标准等。 运动补偿技术的内容主要包括图像分割、运动检测与估值、运动补偿和预测 信息编码几部分。图像分割即将图像分割成静止部分和运动部分：运动检测与估 值即检测运动的类型( 平移、旋转或缩放等) ，并估计物体运动的位移值；运动补 偿即用位移估值进行运动补偿预测；预测信息编码即对预测信息( 如预测误差、 运动矢量) 进行编码，并作为传送给接收端的信息。 图像分割是运动补偿技术的基础，但是，在实际使用过程中要把图像分割成 不同运动的物体是很困难的。通常采用两种简单的预测方法：一种是对每个像素 的位移进行递归估计，也称为像素递归法( 尸尺爿) ；另一种是把图像分为具有适当 大小的若干个矩形予块，把子块分为静止和运动两类，并估计运动子块的位移， 再进行预测编码，这就是所谓的块匹配法( b m a ) 。这两种方法各有特点，p r a 法 精度高，对多运动画面的适应能力强，但只能跟踪较小的位移( 2 像素帧3 像 素，帧) ，且实现复杂；b m a 法精度低于p r a 法，但其位移跟踪能力强( 不低于6 像素帧7 像素i 喷) ，且实现简单，因此获得了更广泛的应用。除了这两种方法 之外，还有许多其他运动估值方法，如二维运动估值的光流分析法、贝叶斯法和 三维运动估值的点对应法、直接法等。这些方法与p r a 法和b m a 法相比运算复杂， 因而目前它们的应用范围还不大。目讨，运动补偿技术正向着并行处理、神经网 络方法等方向发展。 3 混合编码 如前面所述，预测编码利用邻近像素的灰度相关性对某个时刻的某个像素进 行预测，并对其预测误差进行编码。而变换编码则是利用正交变换域中能量分布 比较集中这一特性，在约定规则下对部分变换系数进行编码。相比较而言，预测 编码实现起来较为简单，但其抗误码能力较差；而变换编码抗误码能力强i 但是 实现起来比较复杂。因此，为了适应图像信息千变万化这一实际情况和充分利用 不同编码方法的优点以进一步提高编码的可靠性及编码效率，哈比比( h a b i b i ) 在1 9 7 4 年提出了混合编码的问题，也就是集预测编码和变换编码于一个系统中。 如行内变换编码行间d p c m 、帧内余弦变换帧间d p c m 或是帧内傅立叶变换帧 r 司d p c m 等。 4 第一章绪论 1 2 研究背景与实践意义 图像变换编码方法以离散余弦变换为基础，通过去掉或分配少的比特数给能 量较小的分量而获得图像信息的压缩编码。而该算法复杂，使用的硬件也比较复 杂，成本较高。分形编码利用迭代函数系统恢复原始图像，但是如何较好的分割 图像以及如何构造迭代函数一直是其难点所在。小波变换编码利用完备的、正交 的且多分辨率的小波分解方法进行图像分解，在时域和频域上均有良好的局部性， 不过小波变换没有直流分量，对波形变化点特别敏感。 图像的预测编码方法主要是利用图像像素间的相关性，用己传送的像素的亮度 值对待传送像素的亮度值进行预测，并传送二者的差值，在量化器设计中考虑到 量化误差的统计特性以及人眼的视觉掩盖效应，即在图像亮度变化较大的地方允 许图像亮度值有较大的误差。预测编码的应用相当广泛，在一些国际标准中不仅 对像素值( 或像块值) 进行预测，还可将预测法推广应用到其他量的编码中，如 1 对运动矢量进行预测，即把左邻块的运动矢量作为本块运动矢量的预测 值，然后对运动矢量的预测误差进行编码传输。 2 在模型编码中对模型参数进行预测编码。 3 对各像素块的直流分量进行预测编码等。 ， 预测法在图像编码中应用时，并不局限于一维预测或二维的帧内预测，通常 都普遍采用帧间预测，即由前一帧或前几帧图像来预测当前图像，这样只需对帧 间误差进行量化编码即可。在采用运动补偿技术之后，帧间预测的准确度相当高， 其预测误差的方差与原始图像相比明显减少，压缩比明显提高。而且，从硬件制 作来说，预测法使用的硬件比较简单，成本也较低。 正是由于预测编码方法的上述优点，国内外很多专家对这种图像编码方法展 开了广泛的研究，硕果累累。本文就二维序列图像的帧问预测编码方法进行研究。 华南理工大学理学硕士学位论文 1 3 本文的研究内容 分割和匹配是序列图像帧间预测编码的基础。图像分割的好坏直接的影响着 匹配的效果。本文采用较为简单、直接的区域分割法，可以较为准确地提取出图 像中的运动部分，从而提高匹配区域的运动一致性，减小匹配的计算量。而不同 的匹配方法也决定着恢复图像的质量，我们在这里采用局部最小熵差的匹配方法， 可以在很大程度上提高编码的抗干扰能力和抗几何失真能力，提高复原图像质量。 我们的主要工作包括： 1 、通过区域合并或是区域生长的方法分割图像 2 、利用熵差最小准则，对参考图和实时图进行匹配 3 、用m a t l a b 对以上算法进行计算机仿真 4 、几种不同运动补偿方法的比较 本文运用的预测编码系统如图1 1 所示。 野野叵蛋一堕 图1 - 1 图像预测编码系统 r i g 1 - 1i m a g ep r e d i c t i o nc o d i n gs y s t e m 6 第二章图像分割 第二章图像分割 图像分割是计算机视觉领域中的一项关键技术，是实现自动图像分析时首先 需要完成的操作，也是运动补偿技术的基础。它是根据图像的某些特征或特征集 合的相似性准则，对图像进行分类，将图像平面划分成一系列“有意义”的区域。 这些区域具有特殊的涵义且互不相交，每一个区域都满足特定区域的一致性 3 1 。 计算机视觉中的图像理解包括目标检测、特征提取和目标识别等，都依赖于图像 分割的质量。尽管研究人员提出了许多分割方法，但到目前为止还不存在一种通 用的方法，也不存在一个判断分割是否成功的客观标准，因此被认为是计算机视 觉中的一个瓶颈【4 。在我们的算法中，分割结果的好坏直接影响到后面的运动检 测、运动补偿和图像匹配等算法的效率和准确性，因此分割的方法和精确程度是 至关重要的。 2 1 图像分割的数学描述 图像分割是将图像分成若干个区域，每一个区域内部有相同或者相似的特 性，而相邻区域的特性不同，下面给出图像分割的确切数学描述 5 | 。 设( x ，y ) 为数字图像像素的空间坐标，g = 0 , 1 ，k ) 为像素的灰度层次；一幅 数字化图像j 由盟x m 个像素组成，m = 1 ，2 ，竹) ，( 羔，y ) m x m ，于是图像函数 可以定义为一种映射厂：m 材斗g ，图像在点( x ，y ) 处的强度记为f ( x ，y ) 。由灰 度和纹理结构特征，可将图像中的区域b 定义为的相互连通的均匀子集。设f 为定义在b 区域上的一致性测量逻辑准则，有 吖鳓：j 豫吧 ( ( 占) 功 ( 2 1 ) 邢) 2 尉脚”：姜箍) 。 他1 定义h ：口斗6 是b 的一致性估计的函数，石是已经定义的d 的子区域。图 像分割就是将图像阵列j 分割成若干个邻近且互不交迭的菲空的子集 蜀、丑，、b 。，即日，应满足下面的条件： ( 1 ) t j b = i ( 2 ) e ( 3 ) b 的内部是连通的 ( 4 ) f ( b j ) = t r u e i = 1 ，2 ，m ( 5 ) b ，n b j = ( 1 s f ，m ，且f ，) ( 6 ) f ( b ，u q ) = f a l s e( 1 f ，s 埘，i ，且e 与毋相邻) 7 华南理工大学理学硕士学位论文 2 2 图像分割的一般方法 图像分割大致可分为基于边缘检测的方法和基于区域的方法。基于边缘检测 的方法使用局部窗口操作，检测出局部特性的不连续性，再将它们连成边界，这 些边界把图像分成不同的区域。基于区域的方法按某种准则人为的把图像分为若 干规则块，然后按属性致的原则，反复分开属性不致的图像块，合并具有 致属性的相邻图像块，从两形成一张区域图。在实际应用中，从不同的理论角度 提出了许多方法，主要可划分为三种类型：边缘检测型、阈值型和区域跟踪型。 2 2 ，1 边缘分割 图像的边缘对人类的视觉系统具有重要意义，它是人类判别物体的重要依 据，是图像的最基本特征。边缘中包含着景物有价值的边界信息，这些信息可以 用于图像分析、目标识别以及图像滤波，并且通过边缘检测可以极大的降低后继 图像分析处理的数据量。边缘存在于目标与背景、目标与目标、基元与基元之间。 边缘检测分割法是通过检测不同区域边界来进行分割的。边缘总是以强度突 变的形式出现，可以定义为图像局部特性的不连续性，如灰度的突变、纹理结构 的突变等。边缘常常意味着一个区域的终结和另一个区域的开始。图像的边缘包 含了物体形状的重要信息，它不仅在分析图像时大幅度的减少了要处理的信息 量，而且还保护了目标的边界结构。因此，边缘检测可以看作是处理许多复杂问 题的关键。这类方法首先通过检测图像中的局部不连续性得到图像的边缘，把边 界分解成一系列的局部边缘，再按照一些策略把这些边缘确定为一定的分割区 域。以边缘为对象的分割往往导致图像的不完全分割，即物体或者景物的边界有 间断或者附加有多余的边缘线，因此，基于边缘的分割方法一般还需要后继补偿 处理来得到图像的完全分割，这种补偿处理一般方法是轮廓跟踪、边缘消除和曲 线拟合等方法。对于边缘的检测常常借助予空域微分算子进行，通过将其模板与 图像卷积完成。两个具有不同灰度值的相邻区域之间总存在灰度边缘。灰度边缘 是灰度值不连续的结果，这种不连续常可利用求阶和二阶导数方便的检测到。 在现存的局部技术边缘检测方法中，主要有一次微分( s o b e l 算子、r o b e r t s 算 子等) 、二次微分( 拉普拉斯算子等) 和模板操作( p r e w i t t 算子、k i r s c h 算子、 r o b i n 5 口 算子等) 等。这些边缘监测器对边缘灰度值过渡比较尖锐且噪声较小等 不太复杂的图像，大多数提取算法均可以取得较好的效果a 但对于边缘复杂、采 光不均匀的图像来说，则效果不太理想。主要表现为边缘模糊、边缘非单像素宽、 弱边缘丢失和整体边缘的不连续等方面。在噪声较大的情况下常用的边缘检测算 法，如胁。算子，递归滤波器和c a n n y 算子等都是先对图像进行适当的平滑，“抑 8 第二章图像分割 制噪声，然后求导，或者先对图像进行局部拟合，然后再用拟合的光滑函数的导 数来代替直接的数值导数。c a n n y 算子较为简单，且考虑了梯度方向，效果较好。 无论是哪一种边缘检测算子，遗憾的是至今为止仍没有一个固定的评价其性 能优劣的准则。下面介绍一下c a n n y 给出的准则。c a n n y 准则认为一个优良的边 缘算子应具有一下特征：( 1 ) 好的检测性能。即具有低的把真实边缘点判为非边 缘点或把非边缘点误判断为边缘点的概率。( 2 ) 好的定位性能。即判断为边缘点 的点应尽可能靠近真实边缘的中心。( 3 ) 唯一性。即对于单个边缘点仅有一个响 应。因为第一准则可能对相同的边缘给出两个响应，所以必须认为其中有一个是 假的。第一准则不能给出单一响应，必须进行明晰化操作。一个好的边缘检测算 子应优化上面所有的准则。 2 22 灰度阈值分割法 灰度阈值分割法是一种广泛使用的基于空间域聚类分析的图像分割技术，这 种方法是先利用图像中要提取的目标和背景在灰度特性上的差异，确定一个处于 图像狄度取值范围之中的灰度闽值，然后将图像中各个像素的灰度值都与这个阚 值相比较，并根据比较结果将剥应的像素划分为两类：像素的灰度值大于闽值的 为类，像素的灰度值小于闽值的为另一类。这两类像素一般分属于图像中的两 类区域，所以对像素根据闽值分类达到了区域分割的目的，产生相应的二值图像。 这种方法对于在物体与背景之间存在明显差别的景物分割时十分有效。从以上步 骤中可知，确定闽值是分割的关键。闽值一般可写成如下形式： t = g x ，y ，p ( x ，y ) ，q ( x ，y ) ( 2 - 2 ) 其中p ( x ，y ) 代表像素点( x ，y ) 处的灰度值，q ( x ，y ) 代表该点邻域的局部特性。 如果p ( x ，) ，) t ，则点( x ，y ) 记做物体点，反之则记作背景点。根据对，的不同限 制，可得到三种不同类型的阈值，即： 全局闽值t = t p ( x ，y ) 1 ( 只与全图各像素的本身 生质有关)( 2 - 3 ) 局部阈值t = t p ( x ，y ) ，q ( x ，y ) ( 与区域内各像素的值，相邻像素值的关系 等有关)( 2 4 ) 动态闽值t = t x ，y ，p ( x ，y ) ，q ( x ，y ) ( 与像素空间坐标、该点像素性质、该点 的局部邻域特征有关) ( 2 5 ) 闽值的选择通常是利用直方图。给予直方图分析的门限分割法最直观，应用 最普遍。这种方法对于直方图具有明显双峰的图像，可获得很好的分割效果。一 般来说，对于目标与背景的灰度级有明显差别的图像，其灰度直方图分布呈双峰 状，两个波峰分别与图像中的目标和背景相对应，波谷与图像边缘相对应，当分 割域值立于谷底时，图像分割可取得最好的效果 6 | 。在图像内容不太复杂、灰度 9 华南理工大学理学硕士学位论文 分布较集中的情况下，往往采用最简单的全局阈值，并不考虑图像中点的位置和 其邻域性质。但现实生活中大多数自然景象的图像直方图变化丰富，很少表现为 明显的双峰。对于这类图像，一种方法是将图像分成若干块子图像，再对每个子 图像分别求出最优分割域值，用这种方法分割后的图像在不同子图像的边界处有 灰度的不连续分布，因此必须采用平滑技术来消除灰度的不连续性，c 。w 和 k a n e k o 采用了一个7 x7 的窗口来消除灰度的不连续性 7 ；另一种方法是根据空 间信息和灰度信息采用动态阈值。近年来，随着视觉特性、神经网络、模糊数学、 遗传算法、小波变换、信息论等工具在闽值分割算法中的应用，使得此类方法得 到了很大的发展。 2 2 3 区域跟踪分割法 闽值分割的方法只是孤立的考虑每个像素的灰度，没有考虑到图像区域的连 通性；边缘检测技术也只考虑了每个像素的一个小邻域内的灰度变化，且一般来 说物体的边界具有复杂的形状，从图像中灰度的变化直接找出物体的边界比较困 难 8 j 。而区域跟踪是以区域为处理对象，它考虑区域内部和区域之间的同异性， 寻找具有相似性的像素群，它们对应某种实体世界的平面或物体，它的方法是从 某一像素出发按照属性一致性原则( 这个一致性可以是灰度级、彩色、组织、梯 度或由图像的灰度值或色彩变换得到的特征的相似性等其他特性) 对同一灰度级 或是相同组织结构的像素进行逐步的累加，即区域增长，对由这些像素组成的区 域使用某种均匀测度函数测试其均匀性。若为真，则继续扩大区域，直到均匀测 度为假。常用的方法有区域分裂一合并法和区域生长法。 2 2 3 1 区域合并法 区域合并，就是首先用某种方法把图像分割成许多小区域，通过定义合并相 邻区域的准则，合并所有相邻的区域，如果没有能够再合并的块，则停止合并。 因此不同的初始分割方法和不同的合并准则将形成不同的区域合并方法，区域合 并的结果通常还依赖于区域合并的顺序。可见，区域合并的分割方法是一个迭代 过程，每一步都要重新计算被扩大的区域成员隶属关系，并消除弱边界。没有弱 边界可消除时，合并过程才结束。这样的一个过程看起来像一个物体内部区域不 断增长，直到到达边界为止的过程。 区域合并的方法计算量很大，但是它能够同时利用图像的多种性质，对自然 景物分割方面效果相对较好。 形成最初分割小区域的办法很多，最简单的起始方法就是把图像分成1 1 ， 2 x 2 ，4 x 4 或8 8 的区域的组合，并根据图像的灰度特性统计来定义合并准则。 1 0 第二卓幽像分割 区域合并的过程可通过下面的过程来实现。若比较相邻区域的灰度统计特性满足 合并要求，则把两个区域合并成更大的区域，并计算大区域的灰度统计特性：若 不满足合并要求，则把该区域标记为没有合并。不断重复上述过程，如果某个区 域不能与它周围的所有区域合并，则被标记成终结，当所有区域终结时，合并过 程结束。这里，合并的条件可定义为：当两相邻区域的绝大部分公共边界由弱边 缘组成时，可以合并两个区域，是否是弱边缘则需通过对区域边界处的梯度算子 作用后的幅值大小是否超过阈值，来判断，若边缘强度小于阈值丁则为弱边缘。 2 2 3 2 区域分裂法 区域分裂是与区域合并相反的一个过程，这是一种自顶向下的方法。首先假 定整幅图像是一致的。通过判别准则，如果发现与实际不一致，则将其分裂为四 个子图像，重复上面的过程，直到所有的子区域都满足一致性准则。区域分裂有 一些性质：如果原始图像是n x n ( 其中n = 2 ”，n n ) 大小的正方形，则分裂 后的所有区域都是正方形；因为如果区域不满足一致性准则的时候是要把该区域 分裂为四个不重叠的子区域，因此区域分裂生成的图像是可以用四叉树结构形式 来表示，这种表示形式给运算带来了方便。 一 2 2 3 3 区域分裂一合并法 区域的分裂方法存在一个缺陷，就是在最后可能出现分裂的两个区域足和r ， 是相邻的，而且两个区域满足均一性条件，但是却不能合成一个区域的现象。解 决这个问题的办法就是引入区域分裂一合并方法，它首先将图像分割为初始的区 域，然后分裂合并这些区域，逐步改善区域分割的性能，直到最后将图像分割为 最少的均匀区域为止。这种方法同样是种迭代的方法，只是在每次分裂后根据 均一性条件进行合并操作。具体的步骤可以归纳如下。 1 如果一个区域r 不满足均一性条件，即有e ( 墨) = f a l s e ，则把该区域分 裂成不重叠的四部分； 2 对相邻的两个区域月和r ，如果满足均一性条件，印e ( r u r ，) = t r u e ， 则把这两个区域合并起来； 3 当对于任一区域，既不能继续分裂也不能合并的时候，算法结束。 在这里，均一性准则可以是像素点的灰度值是否小于平均灰度，也可以采用 统计检验诸如均方误差最小、f 检验等方法。 2 2 3 4 区域生长法 区域生长法又叫区域扩张法，是图像分割常用的方法之一，它有许多不同的 方法 9 】。该方法从被称作“生长点”( 可以是单个像素，也可以是某个小区域) 华南理工大学理学硕士学位论文 的地方开始，搜索其邻域，把符合接收准则的点或子区域归并进来，形成新的“生 长点”，反复操作，直到当前区域不能再合并为止。 区域生长法在用来分割图像的时候，首先需要选定一些代表不同区域的起始 像素，即生长点。然后从这些生长点出发，按照一定的规则，一般是检查它与周 围像素( 或区域) 的一致性，把那些通过一致性测试的像素( 或区域) 合并进来， 直到这些区域覆盖整个图像区域为止。生长点的选取通常需要使用者指定，如果 需要划分图像为个区域，那么每一个区域r 必须要有一个生长点s ，其中 i = 1 , 2 ，。区域生长需要满足均一性准则，也即针对每个将要划入区域足的 像素x ，需要检查均一性准则e ( r u x ) ) = t r u e 是否成立，如果x 满足上式，即 满足均一性条件，就把x 点划入区域尺。这种准则在实际应用的时候可以有不同 的形式，比较简单的比如考虑灰度特性，选择一个没有被考察过的像素石点，考 虑其3 3 的邻域特性，来确定该点是否可以被划入区域足，而且要求其灰度接 近区域曩的灰度平均值，即有l 厂( x ) 一r3 0 ，则对幅m x n 大小的图像定义 mnm ， g f = 一p fl o g p f ，p 。= f ( i ，邝，u ，) ( 3 4 ) i f f i l j li = 1 i - i 称g f 为该图像的熵。如果只对图像的某一局部定义熵，则称其为局部熵。从信 息论的角度来看，灰度变化小的地方其信息量少，局部熵值大；灰度变化大的地 方，其信息量多，局部熵值小 1 5 j 。 由于上式定义的熵的计算涉及对数运算，计算量是比较大的，因此有时会利 用泰勒展开所得到的近似公式 m m g f = 一p f ( 既- i ) ，p f = f ( i ，川朋，) ( 3 5 ) j ；l j ；li = l - l 这是比较简单的代数运算，因此易于硬件实现。但是仿真实验结果表明，当基准 图像中各候选匹配图像熵的值分布接近时，近似计算引入的误差可能会导致错误 的匹配。因此我们必须针对不同的条件及需要采用相应的公式进行匹配计算。 可见，两幅图像之间灰度分布越相近，它们之间的熵差就越小。那么，在各 候选匹配图像中寻求与待匹配图像熵差最小者，便是我们要求的最佳匹配结果。 而匹配过程中可能会存在同时有多个候选匹配图像与待匹配图像熵差接近的情 况，但这是可以通过图像的空间相关性来解决的。当然，如果我们将待匹配图像 分块，求每一分块与相应候选匹配图像的熵差，这便是我们所说的局部熵差。选 取各局部熵差之和的最小值为我们的最后匹配结果，就是图像的局部最小熵差匹 配。它以灰度的空间分布为匹配标准，极大地克服了图像的噪声及几何形变的影 响，提高了恢复图像的质量。 华南理工大学理学硕士学位论文 3 4 本章小结 本章论述了图像匹配技术及其基本方法。首先阐述了图像匹配的基本概念和 基本原理，接着阐述了图像匹配的三个主要的技术难点，最后讲述了图像匹配的 几种常用方法，其中重点提及了熵匹配法，谈到了图