计算机学报chin 8页

____________________________________________________________________________www.paper.edu.cn第22卷　第7期计　　算　　机　　学　　报Vol.22No.71999年7月CHINESEJ1COMPUTERSJuly1999曲线曲面的形态算法及应用刘文予　万　菲　朱光喜(华中理工大学电信系图像信息处理与智能控制开放实验室　武汉430074)摘　要　从积分几何中的概念出发,证明了凸体形态和运算的一个重要性质:F(S,u)=F(A,u)ÝF(B,u),从而将两物体的形态和归结为法矢相同的点集的形态和,并提出法矢球的概念,将物体表面各点的法矢顺序对应至球,即得到该物体的唯一法矢球表示,通过对法矢球的合并,则得到两物体的形态运算结果,在理论上统一了二维、三维实体的形态运算,并给出二维、三维曲线、曲面的具体形态算法.此外还给出曲线、曲面形态算法的具体应用,如扫成曲面造型、字型合成、非刚体运动的广义内插等.关键词　形态学,法矢球,法矢圆,凸分析.分类号:TP391CURVEANDSURFACE'SMORPHOLOGYALGORITHMANDITSAPPLICATIONSLIUWen2YuWANFeiZHUGuang2Xi(OpenLaboratoryofImageInformationProcessingandIntelligentControl,DepartmentofElectronicsandInformationEngineering,HuazhongUniversityofScienceandTechnology,Wuhan430074)AbstractInthispaper,theimportantpropertyofconvexobjectmorphologyadditionisprovedthatF(S,u)=F(A,u)ÝF(B,u)basedonintegralgeometry,thenthetwoobjects'morphologyoperatorcanbecalculatedbythroughthetwopointsets'Minkowskyadditionwhichhavesamenormalvector.Theconceptofvectorsphereisprovided,everypointonaspherehasanonlynor2malvectordirection.ForanyvectorinEuclidspacethereexistsauniquecorrespondentpointinthesphere,thatmeansthepoint'snormalvectorhasthesamedirectionasinEuclid.Correspondeverypoint'snormalvectoronanobject'ssurfacetoaspherewhichkeeptheirrelativepositionnotchanged,themorphologyadditionoftwoobjectscanbesimplifiedasthecombinationoftwovectorsphere,acomputationalmodelispresented,whichunifiesthemorphologyaddition,sub2tractionof3Dobjectsintheory.Themorphologyadditionalgorithmof2D,3Dcurvesandsurfacesisalsoprovidedandtheapplicationofthe2D,3Dcurvesandsurfacesmorphologyoperatorsisgivensuchassweepsurfacemodeling,fontcompositionandnon2rigidbodymotioninterpolation.KeywordsMorphology,normalvectorsphere,normalvectorcircle,convexanalysis.获取图像的形态参数和结构参数来描述图像对应的1　引　言物理量,随后发现形态运算具有强的几何选择特性和通过积分几何理论可间接获取图像的几何参数的数学形态学最初用于二值图像的形态变换,以能力,数学形态学已成为图像处理领域的一个重要本文1998208201收到,修改文1999202223收到.本课题得到国家自然科学基金(编号69672014)资助.刘文予,男,1963年生,副教授,主要研究方向为计算机图形学、计算机视觉、多媒体信息处理.万　菲,女,1976年生,获硕士学位,现在美国攻读博士学位,主要研究领域为多媒体通信.朱光喜,男,1945年生,教授,博士生导师,主要研究领域为多媒体通信、计算机图像图形处理、CSCW、数字电视.©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.\n____________________________________________________________________________中国科技论文在线www.paper.edu.cn7期刘文予等:曲线曲面的形态算法及应用709分支.形态运算作为欧氏空间中的集合运算,并没有2　形态算子的基本原理区分离散集或连续集,理论上而言,它应也适用于二(n)维、三维空间中连续物体的处理,Lozano2Perez提定义1.设E中的集合X,结构元素B为[1](n)(m)出了实现两凸多面体形态差的算法,当两凸多面E或其子空间E上的一个集合,则集合X关于2结构元素B的形态和、形态差分别定义为如下集合:体的顶点数均为O(n)时,算法复杂度为O(nlogn).∨∨[2]XÝB={x:BGhosh提出了二维、三维物体形态算子的算法.在xQX}={x:Bx∩X≠Á},∨[3]随后的论文中他描述了一个算法,实现了以闭合XßB={x:Bx0,称该点为椭圆点;若K<0,称该点为双曲则有F(S,u)=F(A,u)ÝF(B,u).点;若K=0,称该点为抛物点.证明.∵F(A,u)=∪{aû〈a,u〉=H(A,3.1　二维法矢圆a∈A2u)},F(B,u)=∪{bû〈b,u〉=H(B,u)},则F(A,定义6.设A为E中简单闭合曲线#及其围b∈B成的平面区域,#上每一点a,当存在唯一法矢nau)ÝF(B,u)=(∪{aû〈a,u〉=H(A,u)})Ýa∈A时,有单位圆C上的一点P与之对应,na=np;当法(∪{bû〈b,u〉=H(B,u)})=∪{a+bû〈a,u〉b∈Ba∈A,b∈B矢不唯一时,在na1到na2区间中单调增(单调减)变=H(A,u),〈b,u〉=H(B,u)}.化,有单位圆C上的一段弧R与之对应,R上各点的令r=a+b,则〈r,u〉=〈a+b,u〉=〈a,u〉+法矢也在na1到na2区间中单调增(单调减)变化.由〈b,u〉,F(A,u)ÝF(B,u)=∪{rû〈r,u〉=r∈AÝB此得到的单位圆称为A的法矢圆.H(A,u)+H(B,u}=∪{rû〈r,u〉=H(S,u)}=设曲线#有分段连续的一阶导数,将曲线#分r∈SF(S,u).证毕.段,使得每一段曲线#i上或者只含有逗留点,或者3不含逗留点.若#推论1.若A,B为E中的凸体,S=AÝB,i上只含逗留点,则#i为直线段,各则有5S=5AÝ5B.点的相对曲率均为零,即#i上法矢保持不变,对应C该推论表明,凸体的形态和可化为边界的形态上一点;若#i上无逗留点,则各点的相对曲率同号和,即两凸体的形态和的边界等于两凸体的边界的且不等于零,即#i上法矢在区间内单调变化,对应C形态和.上一段单向圆弧.若#i的一阶导数不连续,则一阶3导数不连续处的点法矢不定,在一区间内连续可变,推论2.若A,B为E中的非凸体,S=AÝB,则有F(S,u)E取值于单位球面S={(X,Y,Z)的任一曲线a(t)=X(u(t),v(t)).3222∈E;X+Y+Z=1}得到的映射N:∑->S在a(t)上一点P,有aP=Xuu′+Xvv′,称为曲面∑的Gauss映射.dN(a′)=N′(u(t),v(t))=Nuu′+Nvv′因为Gauss映射是定义在正则曲面上的,而形若a(t)是∑的边界曲线,则a(t)=X(t,0)或态运算的曲面一般不是正则的,但可以分解为若干a(t)=X(t,1)或a(t)=X(0,t)或a(t)=X(1,t).正则曲面之并.因此首先将Gauss映射扩展到非正当a(t)=X(t,0)时,dN(a′)=Nu.则曲面,得到法矢球定义,然后在形态运算时再将曲因为∑上不含抛物点,故其上任意点N≠0.面分解为正则曲面之并.N=Nu×NvöK=>Nu≠0,即a(t)=X(t,0)3定义8.设A为E中简单闭合曲面∑及其围上无逗留点.成的空间区域,∑上每一点a,当存在唯一法矢na同理可证其它3条边界曲线上也无逗留点.时,有单位球S上的一点与P之对应,na=np;当法矢证毕.不唯一时,在(na1,na2,⋯,nak)区间中变化,kE3,有因此,围成曲面片的边界曲线的球面像曲线可单位球S上的k段曲线C1,C2,⋯,Ck围成的曲面片与用(H,U,$H,$U)表示.H,U为球面像曲线的起点的球©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.\n____________________________________________________________________________中国科技论文在线www.paper.edu.cn712计　　算　　机　　学　　报　1999年坐标,$H,$U为球面像曲线从起点到终点的法矢的运动的曲线所包围的区域,即两曲线包含区域形态变化范围.和的曲线.图4为一个二阶偏导函数连续的曲面的法矢第2步中的法矢相同点对应的点集的形态和计球.其中S1,S3两个半球面的法矢球像也是两个半算的方法因点集的形式不同而不同.球面,柱面S2的法矢球像是单位球上经过球心与x定理4.平面上相对曲率为kr1和kr2的两个圆轴垂直的圆弧.C1,C2包围的区域作形态和,求得的结果是一个相1对曲率为的圆包围的区域.11+kr1kr2证明.设P,Q分别为C1和C2上法矢相同的两个点,它们的矢量表示分别为r1和r2,如图5所示,$r1$r2它们的切矢也相等,即=,这两点的形态û$r1ûû$r2û和就是它们的矢量相加结果,为R=r1+r2.图4　二阶偏导函数连续的曲面的法矢球多面体是一种特殊的闭合曲面,它只有法矢不确定的顶点和法矢不确定的边以及只含平点的曲面片组成.多面体上边的球面像是一以原点为圆心的单位圆弧,它的法矢的球面像圆弧是以原点为圆心,图5　两法矢相同点的形态和半径为1,两端点分别为相邻两面球面像点的一段当$r1→0,$r2→0时,r1+$r1点和r2+$r2圆弧.点法矢相同,因此这两点也可进行形态和,结果为r1+r2+$r1+$r2.4基于法矢圆、法矢球的形态i¨$Hû$rû因为r=lim,并且当$H→0时$H=,所以,算法模型$r→0$rûrûi¨$H3($r1+$r2)ö(r1+r2)R=lim=lim$r1+$r2→0$r1+$r2$r1+$r2→0$r1+$r24.1　基于法矢圆的形态和算法1=,即根据F(S,n)