第12卷第8期2000年8月
计算机辅助设计与图形学学报
JOU R NA L O F CO M PU T ER A IDED D ESI GN A N D COM P U T ER GR AP HICS
V o l.12,N o.8A ug.,2000
谈 正 王利生
(西安交通大学电子与信息工程学院 西安 710049)
摘要 曲面网格数据是有限元计算与实际测量中经常得到的一类重要的离散数据，由于其采样不规则，采样点
分布在曲面上，因而已有的图像分析方法不再适用.文中讨论了该类数据的特征分析方法，给出了曲面网格数据中特征区域边缘的自动提取与显示方法.
关键词 曲面网格数据，边缘检测，边缘曲线，邻域中图法分类号 T P 391
Detection of Edge of Surface Mesh Data
T AN Zheng W ANG Li-Sheng
(S chool of E le ctronic and I nf or mation E ng ineering ,X i ′an Jiaotong Univ ersity ,X i ′an 710049)
Abstract Surface m esh data is a kind of im po rtant discrete data obtained in finite element com-putation and m easurement.In the paper ,an algorithm is developed fo r detecting and displaying
featur e edge from the surface m esh data.
Key words surface mesh data ,edge detection ,edg e curv e ,neighborhood
原稿收到日期:1999-05-24；修改稿收到日期:2000-01-13.本课题得到国家自然科学基金(69773003)资助.谈 正，男,1939年生，教授，博
士生导师，主要研究方向为图像处理与分析、图形与可视化、图像图形融合.王利生，男，博士研究生.
1 引 言
曲面网格数据是在曲面网格的网格顶点进行数值采样(计算或测量)得到的离散数据，如地球表面的温度数据、数值计算得到的飞机机翼表面的压力数据、地球表面的地形学数据等.在有限元计算和实际测量中，通常得到这类数据，它们在科学计算及工程中应用范围很广.曲面网格数据是三维网格数据，数据分布在曲面上，由数值数据与几何数据两部分
组成[1]
.几何数据即曲面网格，它决定数据分布的曲面形状及数据采样形式；数值数据决定曲面上属性值的分布特点，二者缺一不可.地球表面的地形学数据与飞机机翼表面的压力数据是典型的曲面网格数据，见图1与图2.图1为美国地球物理数据中心公布的地球表面的地形学数据，图1(a)为数值数据按地球经纬度坐标表示的结果，图1(b )为数值数据采样时所对应的曲面网格(几何数据).图2(b)为机翼表面压力分布数据(经处理后按灰度显示)，图2(a)为机翼表面数据采样时对应的曲面网格(几何数
据).在曲面网格数据中，只有将数值数据与几何数据结合后进行分析，才能得到曲面上属性的真实分布特点.图1(c)为地形学数据的可视化结果，它描述了地球表面的陆地与海洋分布的真实状况.
曲面网格事实上是数据采样曲面的离散剖分结果.在实际应用中，连续曲面一般被剖分为四边形网格，因此曲面采样数据多为曲面四边形网格数据.由于曲面网格数据分布在曲面上，在X -Y -Z 坐标空间不规则分布，而且数据采样空间较大，因此，图像处理中大多数特征分析方法无法在曲面网格数据分析中应用.曲面网格数据分析的目的是从数据中获取需要的特征.抽取等值线是曲面网格数据分析的一类方法.而在测量及数值计算得到的曲面网格数据中，人们更关心曲面上的数据是否发生变化(指数值数据在取值上发生的较大跳跃)，以及数据在何处发生变化.一般来说，数值的变化可以反映许多重要的信息.例如，在地球表面的地形学数据中，数值的变化反映了海洋与陆地的分界线；在机翼表面流体力学数
据中，流速及压力分布数据的变化反映了机翼表面设计的结构特性.显然，该类问题可以归结为曲面上网格数据的边缘曲线检测问题.边缘曲线是指曲面上其两边的数据发生较大变化的曲线.一般情况下，曲面网格数据中的边缘曲线是分布在曲面上的三维曲线.由于曲面网格的每一个网格单元在空间有不同的法向量，因此曲面网格数据中特征的显示必须与计算机图形学相结合，才能显示出三维真实效果.边缘曲线检测是实现曲面网格数据自动特征分析的重要一步，它在理论分析与工程应用中都是非常重要且有实用价值的研究问题[2].本文研究曲面网格数据中特征区域边缘曲线的提取和显示的算法.
2 曲面网格数据中边缘曲线的
检测算法与显示
分析图像处理中图像锐化及图像边缘提取等数据处理可知，这些数据处理都是在象素的局部邻域
内进行.为此，我们首先在网格数据中引入邻域结构
的定义.由于曲面网格数据分布在曲面上，而且采样不规则，本文将网格点的邻域定义如下.
定义.如果离散网格中的两个网格点的连接线段为某一网格单元的边或对角线，则称这两个网格点为邻接点.一网格点的所有邻接点构成该网格点的邻域.以一网格点为顶点的网格单元称为该网格
点的邻接网格单元.
曲面四边形网格中的每一网格点有8个邻接点,4个邻接四边形，邻域为八邻域，邻域结构是一致的.网格点之间的联结关系可通过增加或减少数据域中的索引来显式描述，但结构网格需显式保存每个网格点的坐标.为了应用方便，本文将曲面网格中网格点邻域内的邻接点按顺(逆)时针方向顺序存储，见图3(a ).应该注意，网格点邻域内的邻接点不一定分布在一个平面上，而且网格点周围的邻接点分布不均匀.由于曲面网格数据中邻域结构的这些特点，图像分析中以象素的八邻域结构为基础的、通过求梯度判断边缘的分析方法无法应用.
曲面上的连续场中许多特征具有这样的特点：其所在的曲面区域的场值明显不同于周围曲面区域的场值，即相邻区域间存在明显的边缘.只要检测出边缘，边缘内部即为特征区域.特征的这一特点即使在离散的曲面网格数据中一般仍会保持.只要得到连通的边缘网格点集合，则其内部所围曲面区域即为特征区域.
离散的曲面网格数据所对应的连续场为一个分布于曲面上的三维函数，边缘线为连续场中的一条两侧函数值变化很大的连续曲线.考察连续场中边缘线穿过的一个小的邻域窗口，该窗口为一小曲面区域，边缘线将该小窗口分为目标特征及背景两部分，二者的取值有较大的差别，见图3(b).因为曲面网格数据的采样间隔大，所以边缘线穿行在曲面上，但不一定经过网格点，更多的情形是从两个曲面网格点之间通过.
由于在离散情形只能用网格多边形逼近曲面,581
8期谈 正等：曲面网格数据的边缘提取与显示
因此，在近似的情况下，穿行在曲面上的边缘线可近似地看作穿行在曲面网格单元集合中，这些网格单元是边缘网格单元.这一近似会在曲线的精确表示上引起一点误差，但不影响问题的实质.这里所讨论的曲面网格单元都为四边形，所以当边缘线穿过这些网格单元时，一般情形是：边缘线从一条边进去，从另一条边出去.如果将边缘线穿过的网格单元集合到，而且在这些网格单元中到边缘线穿过的两条边，就可以确定边缘线位置及分布方向.
如果边缘网格单元的一条边被边缘线穿过，则该边的两个端点的函数值相差很大.而且这两个端点的邻域内的网格点集也被边缘线分为函数值相差很大的两部分网格点.因此，在网格数据中，通过判定网格点的邻域是否具有这一特点，可以将被边缘线穿过的边的端点到.这些端点都是边缘网格点.分析可知，
边缘网格点作为边缘线穿过边的端点，将成双出现.这是曲面网格数据中边缘网格点的双反映现象.若网格点邻域中所有网格点的值相近，则其中必然没有边缘线穿过.
设(x ,y ,z )为曲面上一边缘网格点，则在(x ,y ,z )的邻域内包含了一边缘线，边缘线将邻域分割为取值相差较大的两部分网格点，它们分别是邻域内的两个连通点集.可以通过计算网格点周围的这两组邻接点的场值变化来检测边缘网格点，即先求两组邻接点的场值的和，再求这两个和之间的差，然后进行判定.基于这一分析，下面构造一个边缘算子检测边缘网格点.
首先给出曲面网格点的邻域结构的表示方式，可用数据结构neighbor 描述:
struct neighbor {float p oint [3];int num ;
float p ointset [N ][3];};
其中，数组p oint [3]存储给定网格点的x ,y ,z 坐标，二维数组p ointset [N ][3]按顺(逆)时针方向顺序存储所有邻接点的x ,y ,z 坐标,num 存储邻接点个数,N =num .
设(x ,y ,z )网格点的邻接点个数为num .令i =0,1,…,num -1，并设K 为常数(一般地，四边形网格取为3)，记
S i =∑K -1
m =0f (p ointset [i +
m ]),
M i =
∑
n um -K -1
j =0
f (p ointset [i +K +j ]).
这里,f 为求该点灰度值的函数,S i 为K 个(2个或
3个)相邻邻接点的和,M i 为剩下num -K 个相邻邻接点的和.用网格点邻域中K 个相邻邻接点的加权和减去剩下的num -K 个邻接点的加权和，令邻接点环绕(x ,y ,z )不断移位(旋转)，则得到num 个差值:
(num -K )õS i -K õM i ,i =0,1,…,num -1.取num 差值中的最大者作为边缘检测算子的值，则边缘检测算子值定义为W (x ,y ,z )=
max {(num -k )õS i -k õM i :i =0,1,…,num -1}
(1)
我们取门限值T H 做如下判断：如果W (x ,y ,z )>TH ，则(x ,y ,z )为边缘网格点.
可以采用与图像处理中门限选取类似的方法选取门限值TH .
式(1)实质上是求网格点邻域中一部分邻接点场值的和与另一部分邻接点场值和之间的差.由于式(1)环绕(x ,y ,z )不断旋转，因此，利用该算子可以检测到网格数据在曲面上各个方向场值的阶跃变化.本质上，式(1)是基于场值的梯度变化检测边缘网格点.式(1)可以看作Kir sch 算子的一种推广形式[3]
.
由于边缘网格点的双反映特征，位于真实的特征边缘线两侧的两个网格点会同时响应.因此，利用式(1)检测网格数据时，在真实边界线的两侧分别有一连通边缘网格点列，见图4(b).已知，若一边界线穿过一网格单元，则该单元至少有3个顶点作为边缘网格点响应.经分析可知，用式(1)检测到的双响应边缘网格点集合恰好是被边界线穿过的网格单元的顶点集合.利用式(1)检测到边缘网格点集合后，根据3个顶点是否为边缘网格点，可以将边界线穿过的网格单元集合全部检测出，见图4(c).其中，将3个顶点为边缘网格点、但所有顶点场值相近的伪边缘网格单元去掉.
得到包含特征边界线的网格单元集合后，对每一边缘网格单元，计算各边两顶点的差值，差值较大的两边判定为真实边界穿入及穿出的边.为了计算简单，可取网格单元中被边界线穿过的两条边的中点连接线段，来近似网格单元中的真实边缘曲线段.结构网格单元被边缘线穿过的情形有3种.边缘线在边缘网格单元中的穿行情况，由边缘网格单元中所有边的两端点的场值之差决定.
边缘网格单元集合中的边缘线段自然地构成了一条连续的边缘曲线.见图4(d).
582
计算机辅助设计与图形学学报2000年
曲面网格数据中边缘提取可以用并行算法实现，步骤如下:
第1步.采用梯度检测算子从网格点集合中检测边缘网格点.
第2步.从边缘网格点集合中出边缘网格单元.
第3步.在每一边缘网格单元中，出边缘线穿进及穿出的两条边.
第4步.以边缘网格单元中边缘线穿过的两条边的中点连接线段近似边缘曲线段.
由于边缘网格点、边缘网格、边缘曲线分布在曲面上，因此它们的显示一般需要与曲面的显示相结合，见图4.图5为曲面网格数据中边缘网格点、
边
缘网格、边缘曲线在空间的直接显示，当边缘曲线的分布复杂时，该显示方法易产生视觉上的混淆.
3 曲面网格数据中边缘提取算法的应用
下面给出从曲面网格数据中检测边缘曲线的具体例子.考察图1中地球表面的地形学数据，容易观察到，陆地数据与海洋数据在取值上存在很大不同，即陆地区域与海洋区域之间存在边缘.利用本文的边缘检测方法可以将陆地轮廓检测出来，检测结果见图6.从图6中可以看到边缘网格点、边缘网格集合及边缘曲线恰好分布在陆地与海洋的分界线处.为了方便观测，也可以只在地球表面上显示网格点、边缘网格集合及边缘曲线的分布，而不显示地球表面的地形分布，结果见图7.从图7中可以看到，检测出的边缘曲线很清晰地刻画了东西两个半球上陆地的轮廓
.
583
8期谈 正等：曲面网格数据的边缘提取与显示
曲面网格数据中边缘曲线的显示比较复杂.首先，要根据曲面的几何数据生成数据的采样曲面；其次，显示每一个边缘网格单元中的边缘曲线段.如果不显示数据采样曲面，只显示检测得到的边缘曲线，则在视觉上容易造成混淆，很难判断边缘线是否分布
于一曲面上，见图8(a )和图8(b ).图8(a )—图8(c )为东半球上检测到的边缘网格点、边缘网格集合及边缘曲线，图8(d)为西半球上检测到的边缘线.数据采样曲面的显示离不开计算机图形学，只有利用图形学中光照模型生成的曲面才会有三维真实感
.
在飞机机翼表面的流体力学计算中，人们非常关心机翼表面气流速度及压力的分布状况，尤其关心流速及压力分布的变化情况.利用本文的边缘检测算法可以从机翼表面的压力分布数据中检测出边缘曲线，即检测出机翼表面上压力发生跳跃之处，结果见图9.从边缘线的分布位置可知,
压力在机翼的
上下表面交界处发生跳跃.显然，这与实际相符.飞机之所以能在空中飞行，一个重要的原因便是由于机翼的上下表面的压力之差而产生的向上的推力.
参
考文献
1Hagen H ,M uller H .Focu s on Scientific Vis ualization .New York:S pringer-Verlag,1993.73-91
2M oorh ead R J,Zhu Z F.Sign al proces sing aspects of s cientific vis ualization.IEEE SP M agazine,1995,(9):20-41
3该边
Kirs ch K .Com puter determin ation of the constituent structure of biological images .Computer and Biomedical Research ,1971,4(3):315-328
584
计算机辅助设计与图形学学报2000年
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议