形状描述与识别

1、形状描述与识别描述形状特征参数的方法主要有两类：基于区域的特征参数和基于边界的特征参数。8.1区域描述参数区域特征参数主要是通过区域内的所有像素点的集合来获得对形状特征参数的描述。这些参数可以是几何参数，也可以是密度参数，还可以是区域的二维变换(如傅立叶变换和小波变换)系数或能量谱 等。对于形状特征的描述，人们已提出了许多方法，比较典型的有不变矩法、傅立叶描述子、边缘直方 图法、小波重要系数法、小波轮廓表示法、几何参数法等。1.基于区域的不变矩对于二维连续函数f (x, y )，其(p + q阶矩定义为mpq = copyqf (x，y)dxdy p,q = 0,1,2，川用(8-3)根据唯一

2、性定理说明，如果f (x, y融段连续，且只在xy平面的有限部分有非0值，则所有各阶矩皆存在，并且矩序列mpq唯一地由f(x, y)所确定。反之，mpq也唯一地确定了 f(x,y )。f (x, y )的中心矩可表示如下:% =. (x-x)p(y-y)q f (x, y)dxdy-3d式中m_ moix = 一， y = moomoo对于数字图像，用求和代替积分：q 八-(x-x)p(y-y)qf(x,y) x ympq二二 xpyqf (x, y)x y零阶矩m。= f (x, y)为f (x, y )的均值，对于二值图像即为区域的面积。 x y(8-4)(8-5)(8-6)mio=ez

3、xf(x,y), moi = e z yf(x,y)除以零阶矩 moo后得: x yx y mio x = moo一 moiy =是图像的重 moo心坐标。中心矩是反映图像相对于重心分布的度量。例如，20和n 02分别表示图像围绕通过重心的垂直和水平轴线的惯性矩；卜30和no3可以度量图像对于垂直和水平轴线的对称性等。利用不变矩可以计算出物体的圆形度(物体形状和圆的接近程度)、物体的矩形度(物体形状和矩形的接近程度)、物体的水平和垂直对称性、物体的主轴方向、扁度等。hu.m.k118利用二阶和三阶规格化中心矩导出了7个不随平移、旋转、等比缩放变化的矩组，称7个不变矩：j1 - 20 02- 2

4、22 - ( 20 -，：02)4 113 = ( 30 一3 12)2( 03 3 21)23= (30. j(03- 21)2中5=(30一3 12)(30一12)( 30.12)2一3(03.21)2(3 21 - 03)(21- 03)3( 30-12)2-(0321)23=(20一 02)(30.12)2一(03.21)24n(30 . 12)( 03 . 21)中 7= (3 21 - 03)(30.12)( 30.12)2-3(03.j(3 12 - 30 )(2103)3( 30-12)2 -(0321 )2其中“pq是p+q阶规格化中心矩： pqpq = r1 pq =2,3

5、,111111002这组矩反映了物体的形状特征，可以用于形状识别。2 .区域的面积区域的面积是区域的一个基本特征，它描述了区域的大小。对于数字图像，区域的面积定义为区域中的像素点数。特别地，对于二值图像，面积 s=叫0。3 .矩形度(rectangularity)矩形度定义为物体的面积a。与物体的最小外接矩形(mer)的面积ar之比，即r= a0/ar。矩形度反映了物体在最小外界矩形中的填充程度，矩形的矩形度为1,圆的矩形度为 n/4,三角形的矩形度为0.5。对于其它形状，矩形度的取值范围为(0, 1)。利用矩形度可以区分矩形、圆形和不规则形状。4 .主轴方向物体的主轴方向定义为物体的具有最大

6、长宽比的最小外接矩形的长轴方向，可以利用矩计算，即：1 42 %日=一 tan (8-7)24 20025 .扁度(eccentricity)扁度或称狭长度(elongatedness),本文采用归一化定义： 彳be = 1 (8-8)式中a为物体长轴，b为物体的短轴。物体的长轴和短轴有一种简单的定义是具有最小外接矩形的 长边和短边，但这种定义受边界的毛刺影响很大。利用惯量矩37计算物体的惯量长短轴可以有效地抑制噪声(边界毛刺、缝隙等)。假设坐标原点在物体的重心上。图像f(x,y )相对直线y = xtan日的惯性力矩 me为：22.2.mb = (j cosei sine) f(i, j)

7、=r02 cos 日十 r20 sin en11sin2日 (8-9)i 4 j=0求m6的最大值m emax和最小值m/in,扁度定义为：(8-10)e =1 - m 5n m max扁度也可以由矩直接求出119,即:2 .(m2。- mb)2 4m112e =j22(8-11)m2。- mo2 , (mb。-mo2)2 , 4；扁度反映了物体形状的狭长程度。例如，线的扁度为1,矩形的扁度是其长宽差与长边比，圆和正方形的狭长度为0。6 .圆形度(circularity )圆形度反映了物体接近圆形的程度，也称作区域的紧凑性( compactness),定义为4兀倍的区域面积a与周长p的平方之比

8、(有的文献定义为周长的平方与4兀倍的区域面积之比)，即：p2(8-12)c =1 ,正方形的圆形度c =4(实际为边界上到重心的最短距离与在相同面积的情况下，具有光滑边界的形状边界较短，圆形度较大，表明形状较密集。随着边界凹凸变化程度的增加，周长p相应增加，圆形度随之减小。圆的圆形度7 .球形度(sphericity)球形度定义为圆心都在区域重心的内切圆与外接圆的半径之比最长距离之比)，即s = n / rc其中，ri为内切圆半径，rc为外接圆半径。圆的球形度为1,正方形的球形度为 y2,其它形状的球2形度取值范围为0, 1)。8 .拓扑描绘子一一欧拉数拓扑学是研究图形性质的重要理论，图形的拓

9、扑特性也是形状的重要特征。本文利用拓扑描绘子一一欧拉数作为识别环形、轮形等形状的关键参数。欧拉数定义为e =c-h,其中h为图形的孔洞数，c为图形中连通的区域数。对于只有 1个连通区域的图形， c =1。环形的欧拉数为 0, “8的欧拉数为-1。8.2边界描述参数区域的边界包括外边界(轮廓)和内边界，这里只考虑区域的外边界。边界的表示方法有链码 (chain codes)、边界段(boundary segments)、逼近多边形( approximating polygon )、标记(signature)等， 边界的描述参数有边长、边界曲率、形状数、边界矩、主分量、傅立叶描述子、逼近多边形的参

10、数等。本文使用傅立叶描述子和基于逼近多边形的参数识别形状。1 .边界的长度和直径边界的直径是边界上相隔最远的2点之间的距离，即这2点之间的直连线段长度。有时这条直线也称为边界的主轴或长轴(与此垂直且最长的与边界的2个交点间的线段也叫边界的短轴)。边界b的直径dia d (b)可由下式计算：bib, bjbe2 .斜率、曲率和角点斜率(slope )能表示轮廓上各点的指向，曲率(点沿轮廓方向变化的情况。在1个给定的轮廓点，curvature )是斜率的改变率，它描述了轮廓上各曲率的符号描述了轮廓在该点的凹凸性。如果曲率大于零，则曲线凹向朝着该点法线的正向。如果曲率小于零，则曲线凹向是朝着该点法线

11、的负方向。曲率 的局部极值点称为角点。3 .傅立叶描述子对边界的离散傅里叶变换可以作为定量描述形状边界的特征参数。设 表不成：xy平面上的封闭轮廓线可以s(k)=x(k)+jy(k)k=0,1,s(k)的离散傅里叶变换为：,n(8-13)1 nd2 二 wks w = v s k exp -j n yw=0,1j|,n -1(8-14)s(w)是边界的傅里叶描述子，完全决定了封闭边界的形状。考虑边界长度随形状尺度变化，将其变 为等长边界m (例如m=100)的轮廓线sil：int i 1s k i =0,2/i|,m -1(8-15)然后，利用等长边界的模归一化傅里叶描述子作为形状特征参数识别

12、形状。对轮廓的离散傅里叶变换表达可以作为定量描述轮廓形状的基础。将轮廓所在的平面uv重合，其中实部 u轴与x轴重合，虚部 v轴与y轴重合。这样就可用复数xy平面与一个复 u + jv的形式来表示给定轮廓上的每个点(x, y)而将xy平面中的曲线段转化为复平面上的1个序列，见下图。4 y,v .(七 , y。uk + j vkdiad (b) =maxdd(bi,bj)i,j其中dd ()可以是任一种距离量度，如de(), d4()和d8()距离(参见1.3节和4.5节)。例边界直径的计算下图给出用3种不同的距离量度来计算同1个目标边界得到的3个直径值。x,u考虑1个由n点组成的封闭边界，从任

13、1点开始绕边界1周就得到1个复数序列:s(k)=u(k) jv(k) k =0,1, , n -1s(k)的离散傅里叶变换是：1 n js(w)s(k)exp_j2 二wk/nn kz0s(w)可称为边界的傅里叶描述，它的傅里叶反变换是：n 1s(k) = s(w)expj2wk/nw回如果我们只利用 s(w)的前m个系数，这样可得到m 1s(k)s(w)expj2 二 wk/nw =0,1, ,n -1k = 0,1, , n -1s(k)的1个近似:k =0,1，n -1wq0例借助傅里叶描述近似表达边界下图给出1个由n = 64个点组成的正方形轮廓以及取不同的m值重建这个边界得到的一些结

14、果。n =64m =2m =4m =8m =16m =24m =32m =40m =48m =56m =61m =624 .逼近多边形用尽量少的线段表示边界的基本形状，然后计算多逼近多边形是用直线拟合逼近任意弯曲的边界,边形的参数，从而使边界描述变得简单。产生逼近多边形的常用方法有三种：基于收缩的最小周长多边形法、基于聚合(merge)的最小均方误差线段逼近法和基于分裂( split)的最小误差线段逼近法。如下左图。第1种方法将原边界看成是有弹性的线， 将组成边界的象素序列的内外边各看成一堵墙, 如果将线拉紧则可得到如下右图所示的最小周长多边形。先选1个边界点为起点,第2种方法是沿边界依次连接

15、象素。用直线依次连接该点与相邻的边界点。1条边并将分别计算各直线与边界的(逼近)拟合误差，把误差超过某个限度前的线段确定为多边形的误差置零。然后以线段另 1端点为起点继续连接边界点，直至绕边界1周，如下图。第3种方法是先连接边界上相距最远的2个象素(即把边界分成 2部分)，然后根据一定准则进步分解边界，构成多边形逼近边界，直到拟合误差满足一定限度，如下图。5 .基于多边形的特征参数多边形的特征参数主要有顶点数、凹点数、内角分布等。(1)多边形的顶点数、凹点数和凸点数多边形的顶点数表明了多边形的复杂程度，而且凹点增加，多边形变得复杂。多边形的凹凸点比例反映了物体边界的齿状情况。(2)多边形的内角

16、直方图多边形的内角可以用余弦公式计算。多边形的内角分布反映了多边形的许多性质。例如，分布在(00, 1800)中的内角对应凸顶点，分布在 (1800, 3600)中的内角对应凹顶点，分布在1800左右的内角对应平滑线或弧线等。图 8-7示出凹边形、凸边形和弧边形的内角直方图。10654320 90 180 270 3600内角数量43212108内角数量(a)凹形100 90 180 270 360 q20640 90 180 270 3600图6-7(b)凸形(c)月牙形多边形及其内角直方图(3)内角方差如等边多边形、矩形、圆的内角方差为0。内角方差的多边形的内角方差反映了形状的规则程度,

17、计算公式如下：(8-16)n -2 180其中，& even = n 是内角均值，n是多边形的顶点数。(4)最小外接凸多边形、最大内接凸多边形、凹凸度最小外接凸多边形指连接部分凸点形成的包含原图的凸多边形，最大内接凸多边形指连接部分凸点和凹点形成的包含在原图中的最大凸多边形。图8-8示出一个凹边形的最小外接凸多边形和最大内接凸多边形的例子。(a)原图(b)最小外接凸多边(c)最大内接凸多边图8-8多边形的最小外接凸多边形和最大内接凸多边形示例凹凸度(concavo-convex)是反映物体形状凹凸程度的一个重要度量定义如下:(8-17)concavo-convex /sc其中，&是多边形白面积

18、，sc是最小外接凸多边形的面积，sr是最大内接凸多边形的面积。显然,凸形的凸度、凹凸度为 1,而星形的凹度较大，凹凸度较小。利用凹凸度，可以识别物体的姿态，如飞 禽类的飞、栖，走兽类的卧、站、奔跑等。图8-9示出鸟飞与栖的姿态及其凹凸度。(a)凹凸度为0.16(b)凹凸度为0.47图6-9鸟的姿态与凹凸度8.3形状识别8.3.1形状分类在人们对图像或图形的长期感知中,对物体的形状产生了相对明确和稳定的概念，中文中就有许多描述物体形状的名词和形容词。本文收集这些形状描述词，进行归并，将描述相同或相似(计算机难以区分)形状的词归并为同义词，如矩形/长方形、椭圆形/扁圆形、环形/轮形、扇形/锥形、拱

19、形/马蹄形等。图8-10是根据这些常用的形状描述词对图形和图像中常见的简单形状进行的分类，即基于概念的 简单形状分类。有些图像中较少出现的形状词（如桶形、柱形、管形、弓形、罐形、马鞍形、工字形等）和计算机 难以识别的抽象形状描述词（如扁平形、尖角形、薄片形、锯齿形、麻花形、螺旋形等）以及多目标形 状描述词（如品字形）等，在此暂不讨论。表8-1示出16种典型的多边形，表 8-2示出9种常见的弧边形。圆平菱梯多矩正四 五六 丁 十五北形方角行边边边 字字角极图8-10基于概念的常见形状分类表8-1 : 16种典型的多边形图例条形矩形止方形凸多边形凹多边形四边形五边形六边形1a|三角形平行四边形菱形

20、梯形丁字形十字形五角星形北极星形 4 t ，表8-2: 9种常见的弧边形示例圆形环形椭圆形扇形拱形月牙形蘑菇形葫卢形心形io13a8.3.2形状识别物体形状的识别对物体的识别非常重要，对基于语义或基于对象的图像检索具有重要意义。自然 界中物体的形状变化万千，加之图像分割的困难性，完全准确地描述和识别物体的形状目前还做不到。 下面就简单的常见形状识别进行讨论。1 .形状识别策略根据前面的形状描述参数，按照形状概念进行识别和分类。分类的原则是采用层次化多种方法分类： 对形状参数有明显区别的形状（如条形的扁度、圆形的圆形度、矩形的矩形度、多边形的凹凸度等），采用形状参数直接识别；对单个形状参数难以区

21、分的形状，采用bp神经网络模糊分类。采用形状参数直接识别的优点是提高了识别效率，减少了模糊分类的数目，提高利用神经网络进行模糊分类的准确率。 形状分类和识别时，首先计算图形的欧拉数，然后填充区域内的所有空，计算形状特征参数，再按下列 步骤进行形状分类：根据形状的扁度将其分为条形（扁度 0.8）和块形；根据内角在135, 2250 内的比率分为弧边形（比率80%）和直边形（多边形）；在弧边形中，根据圆形度识别圆（圆形度0.9）, 再根据欧拉数（环形的欧拉数为0）识别环形；对其它弧边形，利用bp神经网络识别椭圆、扇形、拱形、月牙形、葫芦形和蘑菇形；余者视为任意弧边形，简称弧边形；在多边形中，根据形

22、状的凹凸度 将其分为凸多边形和凹多边形（凹凸度0.8）识别正方形和矩形，再根据扁度区分正方形和矩形（扁度0.2）;对其它凸多边形，利用 bp神经网络识别三角形、梯形、平行四边形、菱形；在余下的凸多边形中，利用顶点数识别四边形、五边形和六边形，其它 作为任意凸多边形；在凹多边形中，利用bp神经网络识别丁字形、十字形、五角星形、北极星形，余者作为任意凹多边形。任意凸多边形和任意凹多边形都简称多边形。2 .利用bp神经网络识别形状bp神经网络目前广泛应用于模糊*ii式识别中。利用三层bp神经网络识别形状，选取32个形状参数（包括 20个等边长模归一化傅里叶描述子、7个不变距、圆形度、凹凸度、扁度、球

23、形度、矩形度）作为描述图像主体形状的特征向量。为了便于神经网络学习，对32个参数归一化，取值范围限制在0,1内。对于条形、圆形、环形、矩形、正方形、四边形、五边形、六边形各取60个实验样本，对于椭圆形、扇形、拱形、月牙形、蘑菇形、葫芦形、心形、三角形、平行四边形、菱形、梯形、丁字形、十字 形、五角星形、北极星形，训练样本取40个，测试样本取20个，另外选取任意弧边形、任意凸边形、任意凹边形各60个作为干扰项。根据图8-10所示的形状分类，利用单个形状参数分类，实验结果如表8-3。表8-3:利用单个形状参数对14种简单形状分类的正确率和准确率形状条形块形弧边形多边形凸多边形凹多边形accurac

24、y ( %)929681869492precision (%)959488839295形状圆形环行矩形止方形四边形五边形六边形accuracy ( %)92929496989794precision (%)90909594989895利用三层bp神经网络（隐含层采用对数sigmoid传递函数，节点数分别为14、8、8,输出层采用线性传递函数），对弧边形、凸多边形、凹多边形进行模糊分类，实验结果如表8-4, 8-5, 8-6。表8-4 :利用bp网络对7种弧边形分类的正确率和准确率形状椭圆形扇形拱形月牙形蘑菇形葫卢形心形accuracy (%)80798885848586precision (%

25、)80808785828284种凹多边形分类的表8-5:利用bp网络对4种凸多边形分类的正确率和准确率形状三角形平行四边形菱形梯形accuracy (%)80878481precision (%)79888085用bp网络对4表8-6:利正确率和准确率形状丁字形十字形五角星形北极星形accuracy (%)84818681precision (%)80839078从实验结果单个形状参数直接 高。对于难以用简上看，采用简单的 识别，准确性比较 单的形状参数识别，采用bp神经网络模糊分类，在分类数较多时，分类的准确性明显下降。考虑物体形状的复杂性和多样性，要提高形状识别的准确性，还需选取更多的训练

26、样本，并寻求新的分类方法，如采用svm进行形状多类分类等。8.3.3主体识别图象的主体识别就是根据图象中的主体的视觉特征和先验知识（知识库）以及有关图象的主题和 内容将其识别出来，用概念（主体名）表示，如下图。图像中主体的识别对理解图像的内容和语义具有重要意义，但由于物体在图像中投影的复杂性， 加之图像分割的困难性，图象中主体识别一直是困难而又重要的工作。目前，利用物体在图像中投影的视觉特征和先验知识识别物体的效果还不理想2 ,还需要借助其它信息提高识别率，如web图像的相关文本、图象的分类目录等。 从图像的相关文本中提取图像中可能包含的物体名词、视觉特征名词或形容词可以作为图象中主体识别的重

27、要参考依据。下面阐述基于图像主体知识库，利用图像的相关文本和视觉特征识别图像主体的一种方法。 1.图像主体的特征表示与文本提取图像的主体指图像中突出表现的物体，在图像中占据较大的面积或特定的位置，并与背景存在较大的反差。图像主体的视觉特征主要包括颜色、形状、姿态、纹理、位置、大小、方向等，如图2。图像主体知识库即在一定的知识领域内根据人们对图像主体的认识，列出图像主体必须具有和可能具有的视觉特征和特征值，主要是颜色、纹理和形状特征。表示形式为：attribute = ai, a2 , a3,。其中a=?或特征值，？表示不确定或未知值（缺省时即为此值）。特征值可以用数值或文字表示，如颜色可以用颜

28、色名或颜色的 rgb值表示。ai, a2 , a3,表示a的“a （与）”、“ v（或）”逻辑范式， 其中表示 “同时具有，“v”表示“可以具有其中若干项（单选时只能具有其中一项）”。例如，图像主体“虎”的属性表示为：图像主体=虎，颜色（color尸（土黄八黑）v （白人黑），形状（shape尸？ v长，姿态（attitude尸？ v站v卧v奔跑v跳跃，纹理（texture尸条纹。表示图像中虎”的颜色必须是土黄和黑或白和黑（白虎），形状是长或不确定，姿态是站、卧、奔跑、跳跃或不确定，主体形状图主体姿态主体纹理主体位置主体大小主体颜色主体方向图1图像内容的层次结构纹理必须是条纹。图2图像主体的视

29、觉属性在ww陶页中，与图像有关的文本主要有图像文件名、图像周围的说明文字、图像的标签、图像所在网页的标题、图像链接白网页标题、图像的 url图像所在网页的 url和图像链接的url等3。在这 些文本中可能包括描述图像主体名称和视觉特征的关键词。为了提取这些关键词， 需要根据应用领域建立图像主体名词典和主体视觉特征词典。图像主体名词典列出图像的主体名称（名词），本文实验中建立了面向自然风景和动物的240个主体名词典。主体视觉特征词典列出描述图像主体视觉特征的中文用词(名词或形容词)，包括262个颜色词(对应 rgb直)、82个形状词、18个纹理词、15个姿态词、11 个位置词和8个方向词。将图像

30、文件名中包含的主体名、相关文本中至少两中文本包含的主体名以及图像周围的说明文字中出现频率最高的3个主体名提取出来。将主体名中包含的视觉特征词和主体名前有“的”字，而“的” 字前的视觉特征词以及在包含图像主体名的句子中由图像主体知识库列出的图像主体可能具有的视觉 特征词提取出来。2 .图像分割与图象主体提取从图象中提取面积最大的区域作为图像的主体区域。3 .图像主体的视觉特征识别(1)颜色提取提取主体区域的5个主色调，用rgb直表示。(2)形状识别将主体区域的形状识别出来。(3)纹理识别将主体区域的纹理识别出来。4 .基于知识的图像主体识别利用图像分割得到白图像主体与从 ww忡提取的图像主体名没

31、有直接的对应关系，需要根据图像主体知识库和两者的视觉特征对图像主体进行识别。将图像分割得到的图像主体、ww忡提取的图像主体和图像主体知识库中的图像主体分别记为i、ii、出，然后按如下方法操作：(1)根据ng,在图像主体知识库中找到出，将两者整合，用n的确定的特征值取代出的与 或逻辑形式的特征值，记为iv。(2)计算i与w的每个特征的相似度。在图像主体知识库中，特征值一般用与或逻辑式表示。首先定义两个与或逻辑式之间的相似度。设一个特征的与或逻辑式为in ,另一个为a?。若im ,0用42a2ev2j士之则两者的相似度定义为s(q甸书axm吟v2j)下若为小，则两者的相似度定义为sa叼品平vi，v

32、2j)卜j 土s(v 1i, v2j)为两个特征值之间的相似度。？与任何特征值的相似度为定义0.5。对于形状和纹理特征值，相似度定义为两个特征值中相同词的比例数。对于颜色特征，首先利用颜色词典将iv的颜色词转换成rgb直，然后利用(3)式计算两种颜色之间的距离d,再利用下式将其转换成相似度s。(4)当d=c0时s=0.5。d可作为相似与否的判断阈值。i , w) s t( i ,w),其中sc( i ,iv)、.3s( i ,iv)小于0.5 ,则认为i与iv无(3)计算i与iv的总相似度s( i , w ) = s c( i ,w) s s(ss( i ,iv)、st( i ,iv)分别为颜

33、色、形状、纹理的相似度。若关，为i取名？1、？2、(表示未知主体名)，否则在iv中寻找 s(iv)的最大值，用最相似的iv 的名称为i命名，表示识别出图像主体i。(4)计算图像主体的识别率和识别正确率。假设xi为i的集合，xn为n的集合。图像主体的识别率s =|x i,xn |/|x i| ,图像主体的识别正确率入=#(xi,bn )/|x irxn | ,其中|x i |表示xi中i的数量(本文中取 5), |xi.-xn |表示xi中能够识别的i的数量，#(xirxn )表示xi中正确识别的i的数量。5 .实验结果与分析借助google的图像搜索功能，用关键词“自然风光”搜索并下载了1200幅中文网页中的图片。利用2中的方法，提取每幅图像中可能的主体名和主体特征词。提取的主体名中约28%与图像中的主体相关，并能够提取12%勺视觉特征词。结合图像分析，利用5中的方法识别图像主体，在“自然风光”类图像中，山、水、花、草、树、天空等重要主体的识别率和识别正确率如下表：图像主体山水花草树天空图像数566756586545识别率42%38%43%44%24%45%正确率72%51%71%75%67%68%图像主体识别率比较低的主要原因是文本中缺少对应的主体名。在文本中含有图像包含的主体名时，即使文本中对应的视觉特征词很少，利用图像主体知识库仍能达到较高的识