三角形网格数据的边缘提取及网格自适应细分

三角形网格数据的边缘提取及网格自适应细分 () () V o l. 4 A , N o. 8 第 4 卷 A 版8 期中国图象图形学报第 A ug. 1999 1999 年 8 月Jo u rn a l o f Im age an d G rap h ic s 3 三角形网格数据的边缘提取及网格自适应细分 王利生谈正 ( ) 西安交通大学电信学院信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 研究所, 西安 710049 摘 要 三角形网格数据是数值计算及实际测量中获得的一类主要的不规则网格数据, 数据量比较庞大, 结构复 ( 杂, 因而数据的可视化和分析存在许多困难。如果只将人们有兴趣的数据特征区域提取出来并单独处理 可视化、 ) 存储、后处理, 不仅可以减少可视化中的计算及存储需求, 而且可以为数据场中特征的高级 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示、分析提供基础。 因此本文讨论三角形网格数据中特征区域边缘的提取算法。 我们在三角形网格中引入了邻域的定义, 并基于此定 义给出网格数据中边缘网格点的检测算法。该算法被用于三角形网格的局部自适应加细。 关键词 三角形网格数据 特征区域 邻域 边缘提取 有许多重要应用, 例如: ? 单独处理特征区域可以 较大地减少数据量, 从而减少计算与存储需求; ? 0 引言 数据场中特征区域边缘的有效提取, 可以为数据场 中特征的高级表示、分析提供基础; ? 数据场中特 网格数据是与图象不同的一类离散数据, 通过 () 在给定的网格上采样 数值计算或测量得到。 在实 征区域边缘的提取算法可应用于数值计算中的网格 际应用中, 许多数值仿真计算或测量得到的数据都 局部自适应加细。这里, 网格自适应加细指网格点的 一种优化分布: 在数据变化小的区域, 生成较少的网 是网格数据。例如, 气象数据及有限元数据等。对这 些抽象数据的理解和解释是一件非常困难的事情。 格点; 在数据变化大的区域, 生成较多的网格点。 数据可视化是这方面的强有力工具, 但通常可视化 在数值计算及测量中, 可以得到各种类型的网 处理的数据量非常庞大, 所以在数据的交互可视化、 格数据。 简单的网格数据, 如笛卡儿网格数据、规整 ( 存储及后处理等许多方面存在不少困难。 注意到人 网格数据等, 它们的邻域结构整齐一致 4 邻域或 8 2, 4 ) 们有兴趣的只是数据中所包含的特征, 而且对应于 邻域, 其特征区域提取算法的讨论相对简单。而 特征的数据在许多情况下只是庞大数据中的一部 在实际应用中, 复杂区域的数值计算大多生成不规 分, 因此从庞大数据中只将人们有兴趣的数据特征 则网格数据, 这些数据的结构非常复杂。 其中, 三角 () 区域提取出来并单独处理可视化、存储、后处理成 形网格数据是二维不规则网格数据中最为重要的一 1, 2 类。通常, 有限元剖分、散乱数据的剖分得 为人们的一个研究重点。D e lau n ay ( ) 抽取等值线 面是数据可视化的主要手段, 但 到这类数据, 而且许多二维网格数据可转化为三角 在实际应用中, 有许多重要特征无法用抽取等值线 形网格数据处理。 三角形网格数据中的特征区域提 () 面的方法提取。例如, 有许多特征区域的特点是其 取算法的研究结果知之甚少, 因此本文将讨论三角 ( 内部的数据相对于周围区域的数据有较大变化 存 形网格数据中特征区域边缘的提取方法。 边缘提取 ) 在较大的梯度, 区域的分布存在明显的边缘。显然, () 是一种局部运算, 为此, 我们首先在三角形网格中引 用抽取等值线面的方法有时无法从数据场中提取 这类特征, 而必须通过边缘检测。 这里, 边缘指两边 入邻域的定义, 并基于该定义给出三角形网格数据 的数据发生较大变化的曲线或曲面。 中 特征区域边缘网格点的检测算法。 该算法是 从数据场中自动抽取特征区域边缘的处理方法 算法在网格数据中的推广。 作为应用, 我们 K ir sch 将本文结果用于三角形网格的局部自适应加细。 ()3 本文研究受华中理工大学图象信息处理与智能控制国家教委开放实验室资金资助9709 T KL J 收稿日期: 1998208227; 收到修改稿: 1998211224 = 。 任意三个邻接点 [ ]、[ + n um p oin t se t i p oin t se t i 1 、构成一邻接三角形, 共有 个。 p oin t n um 1 三角形网格数据的基本特性分析 在有限元剖分生成的三角形网格中, 所有网格 点的坐标都显式保存, 而且网格中每一三角形的顶 1. 1 三角形网格数据的邻域结构分析点构成也被保存。 利用下面算法可从中抽取所有网 格点的邻域结构:三角形网格将连续空间剖分为互不相交的三角 ( ) 形集合, 数据采样 有限元计算或数据测量等在所 () 1遍历三角形网格集合, 可以得到所有网格 ()有三角形的顶点进行, 见图 1 。显然, 三角形网格 a 点的邻接三角形集合及邻接点集合。 数据的采样频率很低, 而且采样方式不规则, 在每一 () ( ) 2按逆 顺时针方向排列所有网格点的邻接 网格点周围的网格点数可以不同, 而且分布不均匀。 点。 由于三角形网格不存在规则结构网格所具有的整齐 ( ) 及任一整数, 并令 = 0。 ? 任取一网格点 一致的邻域结构 4 邻域或 8 邻域, 为了对三角形 p oin t i 网格数据进行局部分析与处理, 首先引入三角形网 ? 取 的一邻接三角形, 记一项点为 p oin t p oin t 格点的邻接点及邻域的定义, 以及连通的定义。 [ , 另一顶点为 [ + 1 。se t i p oin t se t i ? 遍历 的邻接三角形集合, 必存在邻接p oin t 三角形, 两个顶点中, 一个等于 [ + 1 , 而p oin t se t i 另一个不等于 [ , 记后一顶点为 p oin t se t i p oin t se t [ + 2 。i ? 如果 [ + 2 不等于 0 , 令p oin t se t ip oin t se t = + 1, 并转向?; 否则, 令 = + 1, 并转向?。 iin um i 得到网格点的邻域结构后, 可以在三角形网格 () () 三角形网格 三角形网格邻域结构 ab 数据中进行中值滤波、边缘点检测等局部处理。 图 1 1. 2 三角形网格数据的孤立点噪声分析 定义 1 如果三角形网格中 2 个网格点的连接 三角形网格数据的可视化本质上是将离散的网 , 连续 格数据重构生成连续场后进行显示。因为连续线段构成某一三角形的边, 则称这 2 点为邻接点。一 场中每一网格点的值与其周围插值点的值将非常接 个网格点的所有邻接点构成该点的邻域。 以网格点 近, 因此三角形网格数据中的孤立点噪声在连续场 为顶点的三角形称为该网格点的邻接三角形。中将在周围扩散, 形成一小的区域。引入网格点邻域 个网格点 , 称为是连通的, 如果 2 2x 0 x n 定义 的定义后, 可以利用中值滤波消除三角形网格数据 0, 1, 2, , 在三角形网格中存在网格点列{}, = x i i 中的孤立点噪声, 即在每一网格点的邻域内以所求 中值代替网格点数据本身。 实验结果表明在三角形 , 使得 与 为邻接点。 n x i x i+ 1 连通的网格点可用三 角形的边连接起来。 三角 网格数据中中值滤波也可以较好地抑制随机噪声。形网格中, 任 2 个网格点都连通的数据子集称为连 ( 应注意, 网格点邻域内的邻接点数可以为偶数例如通集。显然, 如果特征在连续场中表现为场值分布于 ) 2, 这时, 将从大到小排序后的第 + 1 个值称为n n 一定范围内的连通区域, 则在三角形网格数据中, 其 中值。仍表现为场值分布于一定范围内的连通集。 为了应用方便, 我们将网格点邻域内的邻接点 () () 按逆 顺时针方向顺序存储。例如, 在图 1 中, 网 b 2 三角形网格数据的边缘检测算法及 格 点“”有“、、、、、”6 个 邻 接 点, 并 有 O A B CD EF 其应用、、等 6 个邻接三角形。二维网格点的 A B O B CO CD O 邻 域 结 构 可 以 用 数 据 结 构 描 述: st ru c t n e ig h bor 三角形网格数据是对连续场的一种离散采 样。已知, 当连续场中特征所在区域的场值明显不同 {f lo a t p oin t 2 ; in t n um ; f lo a t p oin t se t [N 2 }; 于周围区域的场值时, 该特征与相邻区域间存在明 其中, 数组 2 存储给定网格点的 , 坐标, 二 p oin t x y 显的边缘, 只要检测出边缘, 边缘内部即为特征区 ( ) 维 数组 [2 按逆 顺时针方向顺序存 p oin t se t N域。 连续场中特征的这一特点在离散采样数据中依 储所有邻接点的 , 坐标, 存储邻接点个数, x y n um N 709 第 8 期王利生等: 三角形网格数据的边缘提取及网格自适应细分 ( () () , = { - 2×- 2: ||然存在, 表现在三角形网格数据中为: 只要把边缘网W x 1 y 1 m ax n um S i M j ()1 格点找到, 则边缘网格点集合所围的区域便为特征 = 0, 1,- 1}i n um () 区域。 本节给出三角形网格数据中边缘网格点的检 取门限值 做如下判断: 如果, 〉, 则 T H W x 1 y 1 T H () 测算法。 特征边缘的检测是网格数据中特征的高级 , 为阶跃边缘点。 x 1 y 1 上述边缘网格点检测算子表示及自动提取与分析不可缺少的一步。 与方向无关, 利用该 算子, 可以检测到场值在各个方向的阶跃变化, 而且 2. 1 三角形网格数据的边缘检测算法检测到的边缘网格点为连通集合, 其所围的区域即 () ) (设 , 为连续场, , 为一阶跃边缘点。 数据中的特征区域。 f x y x 1 y 1 5 () () () 算子 1是图象处理中的 算子在网格 取 , 的球形窗口 邻域, 则窗口内包含了一边 K ir sch x 1 y 1 缘线。边缘线将窗口分为目标特征及背景两部分, 二 数据中的推广, 由于其基于场值的梯度变化检测边 缘网格点, 因此与二维图象处理类似, 位于特征边缘 者的取值有较大的跳跃。离散采样后, 在三角形网格 ( ) 中考察 , 的邻接点, 则必然一部分位于背景 线两侧的 2 个网格点会同时响应, 边缘网格点成双 x 1 y 1 () 存在。 见图 2 , 边缘检测结果表现为在真实的边 中, 另一部分位于目标特征中, 而且这二部分邻接点 b ( 场值依然相差较大。显然, 通过考察网格点周围邻接 缘线两侧分别形成一条连通的边缘网格点曲线 点 )点的灰度变化, 可以判断阶跃边缘点。 列。与图象不同, 三角形网格数据的采样频率低, 真 ( ) 实的特征边缘线不一定通过网格点, 更多的是从两 设网格点 , 的邻接点数为 个, 邻域x 1 y 1 n um 结构为 。 令 = 0, 1, - 1, 并设 = 个邻接边缘网格点中间通过, 因此, 真实的边缘线穿n e ig h borin um S i f num - 3 行在邻接的三角形网格集合中。已知, 若一边缘线穿 ) (( ) , = [ ]+ [ + 1 M i 6 f p oin t se t i f p oin t se t i j = 0 过一网格三角形, 则三角形的 3 个顶点均作为边缘 ()[ + 2+ ]。这里, [ ]与 p oin t se t ij p oin t se t k p oin t se t() 网格点响应。 分析可知, 算子 1检测到的双响应边 [ ? ] 为同一点, ? 表示取余数。为二个相邻 k n um S i 缘网格点恰恰是被边缘线穿过的网格三角形的顶 邻接点的场值的和, 为剩下的 - 2 个邻接点M i n um () 点。 因此利用公式 1检测到边缘网格点后, 根据 3 的场值的和。 以网格点邻域中二个相邻邻接点的场顶点是否为边缘网格点, 可以将边缘线穿过的网格 值的加权和 减去剩下的邻接点的场值的加权和S i () ()三角形集合 边缘网格检测出, 见图 2 。 需要指 c( ) , 而且令邻接点环绕 , 不断移位, 则得到M i x 1 y 1 出, 当边缘线局部弯曲很大时, 尽管弯曲处一些三角 () 个差值: - 2×- 2, = 0, 1, n um n um S i M i i- n um 形网格中无边缘穿过, 但其 3 个顶点仍可能是边缘 1。 取 个差值中的最大者作为边界检测算子的 n um网格点。 可以根据三角形 3 个顶点值是否相近排除 值, 则边界检测算子值定义为:这一情形。 () () () () 数据可视化图 边缘网格点 边缘穿过的三角形 边缘线 ab cd 图 2 ()检测出包含特征边缘线的所有三角形网格单元2 条边的中点连线近似真实边缘线, 见图 2 。 的 d () 边缘网格集合后, 对每一三角形, 计算其中包含的 我们利用本文算法处理关于某海湾相对涡量分布的 (() ) 小段边缘曲线, 所有的小段边缘曲线最终构成完整 网格数据 见图 4 , 所检测到的边缘网格集合及a ()() 的边缘。在边缘三角形中, 计算各边 2 个顶点的场值 边缘线见图 3 和。易知, 边缘检测可以通过并 a b 差, 差值较大的 2 边判定为真实边缘穿入及穿出的 行运算实现。 2 边。为了计算简单, 可取网格单元中被边缘线穿过 2. 2 三角形网格的自适应细分 网格数据的一个主要来源是数值仿真计算, 如 流体力学计算, 有限元分析等。数值仿真计算时, 首 先要将连续区域进行网格剖分, 分割为互不相交的 网格集合, 然后数值计算在所有网格的顶点进行。因 此, 网格剖分生成的网格集合决定了网格数据的采 () () 边缘网格集合 边缘线 ab样方式。 因为人们一般只对网格数据中的一部分特 图 3征区域有兴趣, 所以将所有网格较细的剖分后进行 () () 三角形原始网格及数据 自适应细分后的三角形网格 ab 图 4 () 计算, 不仅增加了计算量, 而且是一种浪费。 一种可三边的中点相连, 分为 4 个三角形。本文采2 () 用后一种细分方法, 实验结果见图 4 。行的改进方法是: 先在剖分较粗的网格中提取特征 b 区域, 然后单独将特征区域的网格加细, 其他区域的 致 谢 审稿人提出了许多重要的修改意见, 表示衷心(网格保持不变。 这样, 既提高了特征区域的采样计 的感谢。 ) 算分辨率, 计算量也不会增加很多。 上述方法是网格的一类自适应加细方法, 也是 参 考 文 献 网格数据的一种优化采样方法, 关键是如何从已有 1 M oo rh ead R J , Zh u Z F. S igna l p ro ce ssing a sp ec t s o f sc ien t if ic 3 的网格数据中抽取特征。在许多应用领域中, 人们 . , 1995, 20, 41.v isua liza t io nIE E E SP M agazineSep tem be r 主要关心数据有较大变化之处, 即梯度较大之处。数 . 2Sam taney R et a lV isua lizing fea tu re s and t rack ing th e ir evo lu 2 , 27.. , 1994, 20t io nCom p u te rJ u ly 据变化较大的区域我们前面定义为特征边缘线 , . , 2H agen H M u lle r HFo cu s o n sc ien t if ic v isua liza t io n Sp r inge r ()( ) 面。 边缘线 面分布在边缘网格集合中, 可通过 3 , 1993.V e r lag 网格数据的边缘检测得到。 对这些边缘网格分别细 梁训东, 刘慎权. 基于特征的时间序列数据场的可视化方法. 软 4 ( ) 件学报, 1996, 7 9: 547, 552. 分, 则实现了网格的自适应加细。三角形的细分主要 . K ir sch RCom p u te r de te rm ina t io n o f th e co n st ituen t st ruc tu re 有两种方法:5 . , 1971,o f b io lo g ica l im age sCom p u te r and B iom ed ica l R e sea rch () 1某一顶点与对边的中点相连, 分为 2 个三 ( ) 4 3: 315, 328. 角形; 711 第 8 期王利生等: 三角形网格数据的边缘提取及网格自适应细分 西安交通大学电信学院信 王利生谈 正 西安交通大学电信学院教 授。主要研究方向为图象分析, 计算机图 息工程研究所博士, 工程师。主要研究方 形学。 向为数据可视化中的特征提取, 几何建 模, 神经网络。 Edge D e tec t ion an d A da p t ive Subd iv is ion of Tr ian gula r M e sh D a ta W an g L ish en g, T an Zh en g ()S ch ool of E lectr ics and I nf orm a tion E ng ineer ing , X i’an J iaotong U n iv ersity , X i’an 710049 . A bstrac t T r iangu la r m e sh st ruc tu re is an im po r tan t ir regu la r m e sh in da ta v isua liza t io nA n effec t ive w ay fo r reduc ing com 2 (, , , p u ta t io n and m em o ry requ irem en t s is to ex t rac t fea tu re reg io n s f rom m a ssive da ta se tand o n ly p ro ce ss v isua lizesto re ) , . . , t ran sm ite tcth e da ta in th e se reg io n sFo r th is rea so nw e g ive an a lgo r ithm fo r de tec t ing edge po in t s f rom t r iangu la r . .m e sh da taT h e a lgo r ithm can be app lied to adap t ive subd iv isio n o f t r iangu la r m e sh e s , , Keywords T r iangu la r m e sh da taE dge de tec t io nA dap t ive subd iv isio n o f m e sh 新书推介 () 图象工程 上册 三年级上册必备古诗语文八年级上册教案下载人教社三年级上册数学 pdf四年级上册口算下载三年级数学教材上册pdf ——图象处理和分析 清华大学出版社出版章毓晋 编著 本书主要介绍了图象处理和分析的基本原理、典型方法和实用技术。考虑到图象技术的飞速发展和广泛应用, 本书在讲解基本理论的同时还介绍了许多近年来国际上有关的最新研究成果和应用实例。 本书主要 () 包括三大部分。 第一部分 包含第 1, 2, 3 章是图象基础, 论述了图象工程的定义, 图象技术整 体概况和分类以及有关视觉和图象模型, 数字图象采集、表达和象素关系, 图象的各种基本变换技术等。第二 () 部分 包含第 4, 5, 6 章论述了图象处理的各重要分支, 如图象增加, 图象恢复, 由投影重建图象和图象压缩 () 编码等基础理论、技术和方法。 第三部分 包含第 7, 8 章和附录介绍了图象分析的基本原理和技术, 如图 A 象分割、目标表达和描述、特征测量、形态学方法等。 书中还提供了大量例题与习题。 本书可作为信息和信号处理、通信与电子系统、模式识别、生物医学工程等学科大学本科和研究生专业 基础课教材, 也可供上述学科及信息工程、电子工程、计算机科学与技术、机器人自动化、遥感和军事侦察等 领域的科技工作者和高等院校的师生参考。