基于改进MC算法的三维表面重建

2005年第22卷第 9期 微电子学与计算机 3 基于改进 MC算法的三维 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 面重建 王正山1 吕理伟 1 顾耀林 1 赵超尘2 (1江南大学信息工程学院，江苏 无锡 214036) (2南京医科大学，江苏 南京 210029) 摘 要：MC算法是面绘制中构造等值面的方法中最具代表性的方法之一，已经得到了许多完善及改进。介绍了 改进 MC算法的实现步骤，并介绍了用 Delphi7．0为开发平台，利用 OpenGL三维图形软件包开发基于改进 MC算 法的三维表面重建系统的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 过程。 关键词：MC算法，三维表面重建，Delphi，OpenGL 中图法分类号：TP391、42 文献标识码：A 文章编号：1000—7180(2005)09—003—03 3一D Surfaces Reconstruction Based on Improved MC Algorithm WANG Zheng—shan ，LV Li—wei ，GU Yao—lin ，ZHAO Chao—chen (1 School of Information Engineering，Southern Yangtze University，Wuxi 214036 China) (2 Nanjing Medical Unvercity，Nanjing 210029 China) Abstract： The Marching Cubes algorithm is one of the most representative methods of visualising isosurfaces．It has been improved greatly by the following authors．Th is paper analyses improved MC algorithm，and presents a system for 3-D surface reconstruction using Delphi7．0 and OpenGL． Key words：MC Algorithm，3-D Surfaces Reconstruction，Delphi，OpenGL 1 引言 三维空间数据场的重建方法分为两类 ：面绘制 (Surface Rendering)方法及体绘制(Volume Render— ing)方法 面绘制的方法从三维空间数据场构造中 间几何图元，即从数据场中提取曲线、边界曲线 、等 值面等信息、再利用原有的显示技术加以显示。在 面绘制 的方法中构造等值面的方法很多 ，其 中 Lorensen和 H．E。Cline提 出 的 MC算法 (Marching Cube Algorithm)[1]是最具代表性的方法之一。 该算法提出后作了许多改进 ：M．J。Durst提出 MC算 法存 在 着连 接方 式上 的二 义性 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 嘲； Matveyev讨论了内部二义性问题 ，利用用沿体单元 对角线的三重线性插值来解决圄：Adriano Lopes和 Ken Br0dlie改进了三重线性插值模型重建等值面 的正确性和精确性，提高了重建的效率[4】。 本文对现有的算法进行了 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，使用改进的 MC算法设计实现了三维空间数据场可视化系统。 系统的软件设计中，选择 Delphi与 OpenGL的混合 编程进行工作。 2 改进MC算法 传统移动立方体算法在拓扑结构上存在二义 收稿 日期：2005-01—10 性、我们首先介绍二义性的解决方法，以便在进行 等值面提取时可以生成拓扑一致且正确的三角片 逼近方式 我们采用方向无关的三重线性插值模型，每八 个相邻的采样点所定义的立方体区域就构成一个 体单元 、而这八个采样点称为该体单元的顶点，对 于体单元内的任一点．其值只能从体单元的八个顶 点的采样值来插值估算。插值结果为： ，y，z)=axyz+bxy+cyz+dzx+ex+fy+gz+h (1) 而等值面是空间中具有某个相同值的点的集 合。为一个三次曲面。 fplFO~)=C) (2) 2．1 二义性的消除 移动立方体算法中使用查询表进行立方体内 部表面的拼接。由于同样的构型进行拼接时方式不 止一种 。就造成了构型上的二义性 ，不能保证生成 结果拓扑结构上的一致性㈣。 假设待重建表面的原函数是 厂，则插值结果函 数 F在采样点上的值与厂是相等的，如果获得的逼 近结果的拓扑结构是正确的，那么它应该和 ( ) 是同构的。基于这个原理，Nielson和 Hamann中引 入表面测试法解决了表面上的二义性问题阁。但是 对二义性面采取相同的解决方式 ，仍然会有拓扑结 维普资讯 http://www.cqvip.com 4 微电子学与计算机 2005年第 22卷第 9期 构不同的三重线性插值方式。因为二义现象不仅仅 出现在立方体的表面．还可能出现在立方体的内 部．所以我们还必须解决内部二义性的问题。 f11面二义性 当立方体表面的一对对角顶点 为正 ．另一对对角顶点为负 ，这是就产生了面二义 性 如图 1所示。顶点 A、C为正顶点 ，而 、D为负 顶点，这时可根据 ) C)一 ) D)的正负来消除 C Ct C0 图1 面--SL~ 图2 内部二义性 面二义性【3l f21内部二义性 当立方体体对角线上的两个 顶点 A。、C 可以内部连接时就产生内部二义性 ，如 图2所示。对于同样连接生成的闭合多边形．如果 不考虑内点．将存在不同的剖分方式 ．从而重建出 拓扑结构不同的表面．如图3所示。 图3 内部--3L~ 假设A。、C。均为正顶点，可以内部连接，对于 X=A，B，C，D，令： X ：t X0+(1一 ) 1 (3) F是三线性函数 ．F沿面片方向上改变正负号 的次数不会超过 1次，所以存在平面尸= ， ，Cl， D1)，使得 A 。与 C0C。在正方形 A ， ，Cl，Dl内部连 接。对于每一种情形，我们需计算P的方向，计算 P 的高度 t来解决正方形A ， ，Cl，Dl内部的二义性。 我们先计算 ： ·_A 0)·(C·一co)一(B1一Bo)· ·一Do) 6=Co 。 " (A ，n I-A o)+ 、 A 一co)一D0‘ 1一 (4) 一 · 。一 一 c=A 0· Bo~D0 然后可构造二阶方程式： n·t +6·t+c (5) 其解即为高度 t，tE[0，1】。 2．2 表面法向量的估计 为了便于计算机硬件绘制三维重建形体．必须 给出每个等值面片地表面法向量．从而确定出该面 片的明暗(浓淡)程度。三角片自身的几何法向量不 能用于浓淡计算．因为这样计算的明暗度在三角片 的衔接处出现严重的不连续 ．得不到好的视觉效 果 ．而且直接计算三角片的法向量的代价很高。因 此采用中心差分法计算体素各顶点处的梯度 。体素 顶点 √，Jj})上的梯度 g= ， ， 由下式可得： fg [ √， )一F( √，k)]／2 { [ √ ，k)-F(i√ ，k)]／2 (6) 【＆=[ √，Jj} 一F(i√，Jj}— 】／2 这里6为沿法坐标立方体的步长。将计算得到 的 进行归一化。通过体素八个顶点上梯度的三线 性插值求出三角面片各个顶点的梯度．也就是各顶 点处的法向量．从而实现面的绘制。 为了获得更好的视觉效果．本系统采用 Gouraud 和 Ph0ng两种光照模型进行绘制，Gouraud光照模 型是对光强直接插值计算 ：而 Phong光照模型先插 值计算每一点的法向量 ．而后计算光强 ．比Gouraud 可以得到更好的高光效果 这样．我们给出MC算法的流程如下： (1)扫描读人内存的体数据 ，逐个构造体素，并 根据设定的阈值标记每个体素．创建响应的构型查 找表： f21判断体素是否属于边界体素，即该体素中是 否含有等值面片： (31对于边界体素，基于三线性插值计算等值面 片的顶点： f41基于中心差分法计算出体素的角点的法向 量．利用三线性插值计算出等值面片的各个顶点的 法向量 ： (5)根据使用的光照模型，绘制三维重建形体。 2．4 处理对象 CT数据分析 常规 CT成像系统用于结构成像．在少数场合 中用造影剂分布来作功能成像 CT图像的空间分辨 率在采集平面中为 0．1～1mm2．其层厚在 1～10mm。 采集的相邻图像数目要覆盖感兴趣结构的整个三 维空间．可从几个截面到 100个以上。通常三维扫 描是以变化的层厚来对整个结构进行的。在感兴趣 区以外扫描的层厚较大．在感兴趣区内用较小层 厚 、较高分辨串进行扫描 ．以减少获取整个三维结 构所需的X线曝光剂量 图像通常以512~512阵列重建．形成 512~512x 1到512x512x100的体图像 灰度分辨率在最大信号 差的0．5％之内．时间分辨率对于常规 CT系统大致 为 1—2s．这是X线系统旋转 360~所需的时间。大部 维普资讯 http://www.cqvip.com 维普资讯 http://www.cqvip.com 6 微电子学与计算机 2005年第 22卷第 9期 (上接第2页) 模型参数有效地计算出一给定词序列 ．．， 最 可能产生的词性标记序列t ⋯t 。计算过程如下： (1)给定：句子长度 11，标记集数目 ； (2)初始化 ： (3)61(∥)=P( 1Iti)·P(tJ)，1≤ ≤ ； (4)蛾(∥)=0 1≤ ≤T (5)循环： (6)for ：=1 to n一1 step 1 do (7)(对所有的标记)f0r all tags do (8)8i+1(∥)=m [6 (∥)×P( I 川)~P(tJlt )lP(tqwi)】 1≤ ≤ r (9) +1(tJ)=argmax1≤』≤r[8i(tJ)xP(∥1wi+1)×P (∥I )／P(∥1w )】 0 end 01)end 结束并读出数据 ： ⋯ 是根据词序列 ．．， 选择的标记序列 Xn=argmaxl~j<_r6 (_『) 0 forj：=n-1 to 1 step-1 do = +· +·) 0 end P(X ⋯Xn)=argmaxl_~_r n(_『) 4 实验结果 我们选取 1998年《人民日报》部分标注语料作 为测试和训练语料。语料使用 42种标记．其中测试 语料约有 244974 个记号．该语料有关特性如下： 42 tags 22345 types 244974 tokens 1 20048 89．72O％ 162246 66．230％ 2 1934 8．655％ 50243 20．5 1O％ 3 297 1．329％ 21419 8．743％ 4 5 1 0．228％ 9901 4．O42％ 表 1 模型 隐马尔可夫模型 马氏族模型 标注准确率 94．642％ 95．564％ 5 10 0．045％ 424 0．173％ 6 4 0．018％ 155 0．063％ 7 l 0．004％ 586 0．239％ 实验结果见表 1可以看出．在相同测试条件 下．基于马氏族模型的词性标注方法比常规的基于 隐马尔可夫模型词性标注方法大大提高了标注准 确率 参考文献 [1】 Eugene Chamiak，Curtis Hendricson，Neil Jacobson．Mike Perkowitz，Equations for Part-of-Speech Tagging，[C】Pro— ceedings of the Eleventh National Conference on Artificial intelligence，Menlo Park：AAAI Press／MIT Press(1993) 784—789． [2] Christopher D Manning，Hinrich Schume．Foudafions of Statistical Natural Language Processing．[M】London：，I'he MIrI1Press。1999． [3】 B Turish．Part-of-Speech Tagging with Finite-State Mor- phology．[C】Poster Presented at the Conference Colloca— tions and Idioms：Lingu istic，Computational，and Psy— cholingu istic perspectives．Berlin，2003：18-20． [4] T Brants．Tnt—a Statistical Part—of-Speech Tagger．[C】In Proceeding of the Sixth Applied Natural La ngu age Pro— cessing Conference．ANLP-2000，Seattle，WA，A 1-May 2000． [5]5 Rabiner L R．A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition，[C】Proceed— ings of the IEEE，1989，77(2)：257-285． 袁里驰 男，(1973一)，博士研究生。研究方向为自然语言处 理，网络安全 。 维普资讯 http://www.cqvip.com