第24卷第2期通化师范学院学报V ol.24№2 2003年3月JOURNA L OF T ONG H UA TE ACHERSπC O LLEGE Mar.2003
曲面重构算法的发展现状述析Ξ
葛金辉
(通化师范学院数学系,吉林通化134002)
摘 要:在参阅和分析有关文献的基础上,对现有的曲面重构算法进行总结、比较和分类.
关键词:Delaunay法;Shepard方法;Multiquadric方法;有限元方法;层次B一样条方法
中图分类号:O242.21 文献标识码:A 文章编号:1008-7974(2003)02-0033-04
1 曲面重构在工程的重要作用
随着计算机技术的发展,以曲面重构为代表的逆向工程方法,无论在理论上还是在应用上取得了巨大的成功,成为发现和理解科学计算过程中各种现象的有力工具.
近几年来,随着计算机辅助设计与图形学的发展,曲面重构技术得到了更广泛的研究和应用,几乎涉及自然科学与工程技术的一切领域,如汽车、飞机、轮船等工业领域,基于地震勘探数据或测井数据的地质勘探领域,依据大量数据计算和计算结果分析的气象领域、分子模型构造领域,需要实现形体的网格划分及结果数据的显示、优化的有限元分析,根据测量数据建立人体以及骨骼和器官的计算机模型在医学、定制生产等许多方面都有重要意义和实用价值.
同时,随着科学技术的迅猛发展,来自各种科学计算、工程计算、测量等方面的数据日益增大,所要求的精度日益精确,待处理问题规模越来越大,因而,研究大规模散乱数据的曲面重构日益成为迫切需要解决的问题.
2 曲面重构的含义
曲面重构又称为逆向工程(Reverse engineering),是根据已有曲面去构造反映其形状的数学模型.
曲面重构要为已存在的曲面建立模型.曲面重构的目的是确定一个曲面逼近未知曲面.它有两方面的含义.第一意味着已有的曲面是曲面重构的根据;第二意味着已有的曲面是衡量重构所得曲面模型质量好坏的标准,要求建立的模型能忠实地恢复已有曲面的原状.
3 曲面重构的要求
曲面重构的基本要求是准确易行.
准确:要求建立起来的数学模型比较准确地反映原来曲面的形状,或者说较好地逼近原来的曲Ξ收稿日期:2002-05-15
作者简介:葛金辉(1968-),女,通化师范学院数学系讲师,硕士.
面.
易行:要求对所建立的数学模型易于进行各种操作,或者说较方便地适用于计算机进行曲面的存储、分析、计算和绘制等.
实现以上基本要求的方法是进行分而治之,化繁为简.分而治之是指把复杂曲面分割成一块块小曲面片;化繁为简是指把每块小曲面片的形状都用简化的方法来表示.
4 曲面重构算法的发展现状
散乱数据的曲面重构问题人们已经开始了一些研究.国外在这方面已有一系列研究成果.
(1)Delaunay法
散乱数据曲面重构最直接的方法是应用V orono图对散乱点集进行Delaunay三角化.1972年, laws on提出了三角化的最大角最小原则,符合这一原则三角形是局部最优的.这种方法简单、易行,但它仅仅能达到C°连续,而且,对大规模散乱数据进行三角划分时速度也是一个问题.
(2)Shepard法
这一方法首先由气象学及地质学工作者提出来的,后来由于D.Shepard的工作被称为Shepard 方法.其基本思想是将插值函数定义为各数据点函数值的加权平均,这是一种与距离成反比的加权方法,插值结果只能是C°连续.而且,当增加、删除或改变一个点时,权函数均需重新计算,因而该方法是一个全局插值算法.
为了克服Shepard方法的缺陷,Franke及Niels on[3]提出了MQS(M odified Quadratic Shepard)方法,它仍然是一个与距离成反比的加权方法.由于MQS方法消除了Shepard方法的一些缺陷,因此在散乱点插值中得到了广泛的应用,但由于多次求解线性方程组,计算量大,因此,一般只适用于中、小规模散乱点的插值运算.
(3)Multiquadric法
该方法由R.L.Hardy[4]在1971年提出来的.它是最早提出且应用得最为成功的一种径向基函数插值法.一般来说,这种方法不具有多项式精度,但只要稍加改进,即可获得具有多项式精度的插值公式.这一方法提出后的近20年间,在水文测量、大地测量、地质及采矿、地球物理等领域得到了广泛应用,效果良好.在数据点不太大的情况下,计算也较简单,但是,对其解的存在性等问题却一直没有数学上的证明,直到1986年,才由Micchelli[5]对这一方法为什么能工作得很好给出一些解释.
(4)有限元法
这是一种与前述方法完全不同的散乱点插值方法.由于其基本原理与求解偏微分方程的有限元方法相同,因而被称为散乱点插值的有限元方法.这种方法首先解决二维点集的三角剖分问题,之后讨论如何构造插值于各点函数的面片问题,这里只介绍三种插值方法.
①Clough-T ocher插值法
这种方法用一个三次曲面片对一个三角形的顶点进行插值,该三次面片可用一个双变量的三次多项式表示,进行处理中,关系式方程成为超定方程,无法求解,针对这一问题,R.W.Clough及J. L.T ocher[6]提出了一个方法,使其对其求解.
②Herron插值法
G.Herron[7]提出了一种在理论上有创新的方法,该方法定义了三角面片插值函数的性质,并将其表示为3类函数的线性组合,从而解决插值问题.
上述两种方法都需要知道各散乱点处的一阶偏导数,求解偏导数的方法很多,这里不一一介绍.
③最小模网络法(MNN法)
由G.M.Niels on[8]提出的最小模网络(Minimum N orm Netw ork)法是一种比较成功的基于三角面片的散乱点插值方法,有较为广泛的应用.该方法插值效果最好,但当增加、删除或改变一个点的位置或函数时,插值函数必须重新计算,故为基于全局插值的计算.
(5)层次B一样条法
1988年和1995年,F orsey和Burtels[10]提出了一种层次B一样条的方法来曲面拟合和曲面编辑.这种方法能提供很好的连续性,并且具有修改方便的优点.该算法使用一个层次结构的控制点网格,一步一步地从一个较粗糙的网格到一个较精细的网格来提高逼近的精度,但是它的应用仅限于规则网格.
1997年,Seungy ong lee[11]等人从图象变形技术出发,提出了散乱数据的多层次B-样条插值方法.该方法对给定的一组散乱数据,通过求解一个不定方程的伪逆矩阵来求解一组控制点,是通过最小二乘法来最终得到控制网格,它也是全局细化的过程.
国内在这一方面开展一些卓有成效的工作.
张伟强[15]在上述工作基础上,对层次化的过程作了限制,用一种自适应算法自动对某些需要细化的区域进行细化,提高了计算效率.
5 分类与比较
方法/性能光滑性时间复杂性数据量
Delaunay法C°全局细化小规模乱点
Shepard法C°全局细化小规模散乱点
M QS法C°局部细化小规模散乱点
Multiquadric法全局细化小规模散乱点
Clough-T ocher插值法
Herron插值法
M NN插值法
C1全局细化中、小规模散乱点
层次B-样法
多层次B-样条法
自适应层次B-样条法C2
全局细化
局部细化
中、小规模散乱点
大规模散乱点
总之,散乱数据的可视化,尤其是大规模散乱数据的可视化,需要进一步研究,以满足现代测量仪器、测量方法的不断进步,满足医药、工程学上对数据分析的需要,在算法的连续性、计算量、实现方法等方面的优化.
参考文献:
[1]Franke.R,Niels on G.1980.Sm ooth Interpolation of Large[J].Sets of Scattered Data International Journal for Numerical methods in Engi2 neering,15,1691-1704
[2]https://www.doczj.com/doc/ea2684899.html,attered Data Interpolation[J].T est of s ome M ethods.M ath C om p.,38,181-200
[3]Franke.R,Niels on.G M.Scattered Data Interpolation and Applications[J].A Tutorial and Survey.In hagen.H,R oller D.eds.G eometric M odelling:M ethod and Their Application,S pringer verlag,1991,131-160
[4]Hardy R L.1971.Multiquadric Equations of T opography and Other Irregular Surfaces[J].Journal of G eophysics Research,78,1905-1975
[5]M icchelli CA.1986.Interpolation of Scattered.Data:Distance M atrices and C onditionally P ositive Definite Functions C onstr[J].Approx.,
2,11-22
[6]Clough.R,T ocher J.1965.Finite E lement S tiffness M atrices for Analysis of Plats in Bending Proceedings of C on ference M atrix[J].M ethods in S tructural mechanics,515-545
[7]Herron.G.1985.A Char a cterization of Certain CI Discrete T riangular Interpolants[J].SIAMJournal on Numer.anal.,22(4),811-819
[8]Niels on G M.1983.A method for Interpolating Scattered Data Based Upon a M inimum N orm Netw ork[J].M athematics of C om putation,40 (161),253-271
[9]F orsey DR;Bartels RH.1988.Hierarchical B-S pline Refinement[J].C om puter G raphisics,22(4),205-212
[10]F orsey DR,Bartels RH.1995.Surface Fitting with Hierarchical S plines[J].AC M T ransactionos on G raphics.,14(2),134-161
[11]Lees,W olberg G,shin SY.1997.Scattered Data Interpolation with Multilevel B-S plines[J].IEEE T ransactions On visualization and
C om puter G raphics,3(3),228-244
[12]Lee DT,Scchschter B.J.1980,T w o Alg orithms for C onstructing a Delaunay T riangulation[J].International Journal of C om puter and In for2 mation sciences,9(3),219-242
[13]M eingue J.1984.Surface spline Interpolation[J]:Basic Theory and C om putational Aspects.
[14]M icchelli C.A.1986.Interpolation of Scattered.Data:Distance M atrices and C onditionally P ositive Definite Functions C onstr[J].Ap2 prox.,2,11-22
[15]Zhang W,T ang Z.1998.Adaptive Hierarchical B-S pline Surface Approximation of Large scale Scattered Data[J].Proceedings of Pacific
G raphics94,August,33-48
(责任编辑:景贸)
The Development Overview of Surface R econstruction Method
GE Jin-hui
(Department o f Mathematics,Tonghua Teacher s College,Tonghua,Jilin,134002)
Abstract:This paper,by com paring,analyzing and classifying the wide variety of surface reconstruction methods,provides a clear overall picture of all those methods.
K ey w ords:Delaunay method,Shepard method,multiquadric method,finite element method,hierarchical B-spline method
2017 年秋季学期研究生课程考核 （读书报告、研究报告） 考核科目:雷达系统导论 学生所在（系）:电子与信息工程学院 学生所在学科:电子与同学工程 学生姓名: 学号: 学生类别: 考核结果阅卷人 第 1 页（共页）
几种非线性滤波算法的介绍与性能分析 作者姓名：学号： 专业院系：电信学院电子工程系 电子邮件： 摘要—非线性滤波算法在雷达目标跟踪中有着重要的应用，对雷达的跟踪性能有着至关重要的影响。好的滤波算法有利于目标航迹的建立及保持，能够得到较精确的目标位置，为发现目标后的后续工作提供可靠的数据依据。本文重点介绍了雷达数据处理中的几种非线性滤波算法：扩展卡尔曼滤波（EKF）、不敏卡尔曼滤波（UKF）、粒子滤波（PF），并且给出了一个利用这三种算法进行数据处理的一个实例，通过这个实例对比分析了这三种算法的性能以及优劣。 关键字—非线性滤波算法；扩展卡尔曼滤波；不敏卡尔曼滤波；粒子滤波； I.概述（一级表题格式） 在雷达对目标进行跟踪前要先对目标进行检测。对于满足检测条件的目标就需要进行跟踪，在跟踪的过程中可以利用新获得的数据完成对目标的进一步检测比如去除虚假目标等，同时利用跟踪获得数据可以进一步完成对目标动态特性的检测和识别。因此对目标进行准确的跟踪是雷达性能的一个重要指标。在检测到满足条件的目标后，根据目标运动状态建立目标运动模型，然后对目标跟踪算法进行设计，这是雷达目标跟踪中的核心部分。 目前主要的跟踪算法包括线性自回归滤波，两点外推滤波、维纳滤波、- αβ滤波、加权最小二乘滤波、维纳滤波和卡尔曼滤波[1]。对于线性系统而言最优滤波的方法就是卡尔曼滤波，卡尔曼滤波是线性高斯模型下的最优状态估计算法。但是实际问题中目标的运动模型往往不是线性的，因此卡尔曼滤波具有很大的局限性。目前主要用的非线性滤波算法可以分为高斯滤波和粒子滤波[2]。不敏卡尔曼滤波和扩展卡尔曼滤波就是高斯滤波中的典型代表，也是应用相对较为广泛的。粒子滤波的应用范围比高斯滤波的适用范围要广，对于系统状态非线性，观测模型非高斯等问题都有很好的适用性。本文具体分析阐述了扩展卡尔曼滤波算法，不敏卡尔曼滤波算法，粒子滤波算法，并且通过一个实例利用仿真的方法分析了这三种算法在滤波性能上的优劣，最后对这三种算法做了一定的总结。 我本科毕业设计题目为《基于历史数据的路径生成算法研究》，由于我是跨专业保研到电信学院，该课题所研究内容不属于雷达系统研究范围，是一种城市路网最快路径生成算法。 II.几种非线性滤波算法 A.扩展卡尔曼滤波 扩展卡尔曼滤波是将非线性系统转换为近似的线性系统的一种方法，其核心思想是围绕滤波值将非线性函数展开成泰勒级数并略去二阶及以上的项，得到一个近似的线性化模型，然后应用卡尔曼滤波完成状态估计。 扩展卡尔曼滤波状态空间模型： k k k w x f+ = + ) ( x 1 状态方程 k k k v x h+ =) ( z观测方程 其中(.) f和(.) h为非线性函数 在扩展卡尔曼滤波中，状态的预测以及观测值的预测由非线性函数计算得出，线性卡尔曼滤波中的状态转移矩阵A阵和观测矩阵H阵由f和h函数的雅克比矩阵代替。 对 (.) f和(.) h Taylor展开，只保留一次项有： ) ? ( ) ?( ) ( k k k k k x x A x f x f- + ≈ ) ? ( ) ?( ) ( k k k k k x x H x h x h- + ≈ 其中： k k x x k k dx df A ?= =为f对 1- k x求导的雅克比矩阵 k k x x k k dx dh H ?= =为h对 1- k x求导的雅克比矩阵 ) ?( ? 1-k k x f x=，于是可以得出： k k k k k k k w x A x f x A x+ - + ≈ + ) ? ) ?( ( 1 k k k k k k k v x H x h x H z+ - + ≈ + ) ? ) ?( ( 1 通过以上变换，将非线性问题线性化。接下来EKF 滤波过程同线性卡尔曼滤波相同，公式如下: )) | (?( ) |1 ( X?k k X f k k= + ) ( ) ( ) | ( ) ( ) |1 (P k Q k k k P k k k+ Φ' Φ = + )1 ( )1 ( ) |1 ( )1 ( )1 (S+ + + ' + + = +k R k H k k P k H k )1 ( )1 ( ) |1 ( )1 ( K1+ + ' + = +-k S k H k k P k
三维曲面重构方法分析 摘要：曲面重构是逆向工程中CAD建模中的重要组成部分，三维曲面的重构方法决定了获得的曲面精度与光滑性，直接决定了逆向工程的效果，文章针对逆向工程中的关键技术三维曲面的重构方法进行了分析与讨论。 关键词：曲面重构；逆向工程；三维曲面 逆向工程是在吸收现有技术优点的基础上进行更优化的再创造技术，是针对现有设计方案的再设计过程。设计师使用逆向工程技术能够从实物上获取该物体的三维数据，并生成数据模型，这样可以将数据模型与实体进行比较，从而得到两者之间的异同点。使得在设计新产品过程中起点更高，设计周期更短，获得成效更快。 1 曲面重构算法的分类 三维曲面的重构，首先要进行点云的采集，然后进行曲面重构，并且结合正逆向工程的软件，重新设计比较复杂的三维曲面，得到光滑的无误的实体模型，并应用3D点云对齐的方式对重构模型进行误差分析，以达到最佳的重构效果。 在进行逆向工程的过程中，最重要的一步是重新对实体进行三维曲面重构。这是因为产品的再设计、模型分析、虚拟仿真、加工制造过程等应用都需要根据三维数据模型来进行。三维数据模型越准确这些过程得到的结果也会越准确。要获得精确的数据模型，一方面需要良好的硬件设备和操作软件，另一方面与操作人员的熟练程度有很大的关系。这是一个复杂、繁琐、技术性强的过程，国内外的众多学者都针对如何快速、准确地实现模型重构进行了大量的实验与总结，得到了很多曲面重构的算法，现在常用的曲面重构算法根据曲面类型、数据来源、造型方式能分为： ①按点云类型可分为规则排序的点与不规则排序的点。 ②按数据来源可分为三坐标测量、软件造型、光学测量等途径。 ③按造型的方式可分为根据曲线生成曲面与根据曲面拟合实体模型。 ④按曲面表现形式可分为曲面边界表示、曲面四边B-样条表示、三角面片和三角网格表示的模型重构。通常，采用NURBS、有理B-样条、Bezier曲面来表示长方形区域面重构的自由曲面，而采用NURBS和三角域的拓扑结构来进行散乱点的自由曲面重构。 2 曲面重构的精度 在进行曲面重构前，必须先对数据模型的基本信息与要求进行了解。基本信息包括了实体的几何特征、构造特点等；应用要求包括了数据分析、产品制造、
智能控制之蚁群算法 1引言 进入21世纪以来，随着信息技术的发展，许多新方法和技术进入工程化、产品化阶段，这对自动控制技术提出新的挑战，促进了智能理论在控制技术中的应用，以解决用传统的方法难以解决的复杂系统的控制问题。随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛。 智能控制技术的主要方法有模糊控制、基于知识的专家控制、神经网络控制和集成智能控制等,以及常用优化算法有:遗传算法、蚁群算法、免疫算法等。 蚁群算法是近些年来迅速发展起来的，并得到广泛应用的一种新型模拟进化优化算法。研究表明该算法具有并行性，鲁棒性等优良性质。它广泛应用于求解组合优化问题，所以本文着重介绍了这种智能计算方法，即蚁群算法，阐述了其工作原理和特点，同时对蚁群算法的前景进行了展望。 2 蚁群算法概述 1、起源 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 Deneubourg及其同事(Deneubourg et al.,1990; Goss et al.,1989)在可监控实验条件下研究了蚂蚁的觅食行为，实验结果显示这些蚂蚁可以通过使用一种称为信息素的化学物质来标记走过的路径，从而找出从蚁穴到食物源之间的最短路径。 在蚂蚁寻找食物的实验中发现，信息素的蒸发速度相对于蚁群收敛到最短路径所需的时间来说过于缓慢，因此在模型构建时，可以忽略信息素的蒸发。然而当考虑的对象是人工蚂蚁时，情况就不同了。实验结果显示，对于双桥模型和扩展双桥模型这些简单的连接图来说，同样不需要考虑信息素的蒸发。相反，在更复杂的连接图上，对于最小成本路径问题来说，信息素的蒸发可以提高算法找到好解的性能。 2、基于蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下假设： （1）蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的环境作出反应，也只对其周围的局部环境产生影响。 （2）蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的自适应表现，即蚂蚁是反应型适应性主体。 （3）在个体水平上，每只蚂蚁仅根据环境作出独立选择；在群体水平上，单
第十三章 卡尔曼滤波 在本章中，我们介绍一种被称为卡尔曼滤波的十分有用的工具。卡尔曼滤波的基本思想是将动态系统表示成为一种称为状态空间表示的特殊情形。卡尔曼滤波是对系统线性投影进行序列更新的算法。除了一般的优点以外，这种算法对计算确切的有限样本预测、计算Gauss ARMA 模型的确切似然函数、估计具有时变参数的自回归模型等，都提供了重要方法。 §13.1 动态系统的状态空间表示 我们已经介绍过一些随机过程的动态表示方法，下面我们在以前的假设基础上，继续分析动态系统的表示方法。 13.1.1 继续使用的假设 假设t y 表示时刻t 观测到的n 维随机向量，一类非常丰富的描述t y 动态性的模型可以利用一些可能无法观测的被称为状态向量(state vector)的r 维向量t ξ表示，因此表示t y 动态性的状态空间表示(state-space representation)由下列方程系统给出： 11+++=t t t v ξF ξ 状态方程(state model) (13.1) t t t w ξH x A y t +'+'= 量测方程(observation model) (13.2) 这里F ，A '和H '分别是阶数为r r ?，k n ?和r n ?的参数矩阵，t x 是1?k 的外生或者前定变量。方程(13.1)被称为状态方程(state model)，方程(13.2)被称为量测方程(observation model)，1?r 维向量t v 和1?n 维向量t w 都是向量白噪声，满足： ???≠=='τ ττ t t E t ,,)(0Q v v (13.3) ? ??≠=='τττt t E t ,,)(0R w w (13.4) 这里Q 和R 是r r ?和n n ?阶矩阵。假设扰动项t v 和t w 对于所有阶滞后都是不相关的，即对所有t 和τ，有： 0w v =')(τ t E (13.5) t x 是外生或者前定变量的假定意味着，在除了包含在121,,,y y y Λ--t t 内的信息以外，t x 没有为s t +ξ和s t +w (Λ,2,1,0=s )提供任何新的信息。例如，t x 可以包括t y 的滞后值，也可以包括与τξ和τw (任意τ)不相关的变量。 方程系统中方程(13.1)至方程(13.5)可以表示有限观测值的序列 },,,{21T y y y Λ，这时需要状态向量初始值1ξ。假设1ξ与t v 和t w 的任何实现都不
算法与算法描述教学设 计 公司内部档案编码：[OPPTR-OPPT28-OPPTL98-OPPNN08]
算法与算法描述教学设计 一、教学目标 （一）知识与技能 1．充分理解掌握算法的概念及其特点 2．学会用自然语言来准确地描述算法 3．认知流程图的六种基本符号，用流程图描述简单的算法 4．理解科学合理的选择和设计算法 （二）过程与方法 1．通过问题的解决，培养学生观察流程图问题、分析问题和解决问题的能力 （三）情感态度与价值观 激发学生学习算法设计的兴趣，使学生积极参与，发挥他们的主动性，激发他们的求知欲；认识计算机只是工具，合理的指挥和控制计算机来解决学习和生活中的问题。 二、内容分析
教学重点： 1. 充分理解掌握算法的概念及其特点 2. 学会用自然语言和流程图来准确地描述算法 教学难点： 学会用自然语言和流程图来准确地描述算法 三、学生分析 在必修模块“编制计算机程序解决问题”部分以及本章第一节的学习中，学生已经经历了用计算机解决问题的基本过程，对VB开发环境有所了解，这些都为本节课的学习提供了良好的基础。（学生对本节内容的学习具备一定的基础知识和学习经验） 本节课有关知识、问题与数学学科联系紧密，学生具有相关的数学基础，因此理解起来相对容易。教学中要关注全体学生，变学生的个体差异为资源，发挥同伴互助作用，共同提高教学效率。 四、教学策略 1、教学方法：讲授法、演示法、任务驱动、情境教学
2、学习方法：协作学习、自主学习 五、教学过程
六、教学反思： 本课充分发挥了学生的主观能动性，在教学中教师一般是提出问题让学生思考探究、注重实践、互动交流；另外举例生动形象，简单明了，学生学习起来兴趣浓厚，学生在轻松愉快的过程中较好的掌握了算法的概念，理解算法的设计和优劣的选择。学生初步接触编程，设计好这堂课的内容，能够激起学生学习编程的兴趣。
第一章算法与算法的描述 1．算法的定义 算法：就是解决问题的思想方法，对解题过程的精确描述。计算机解决问题的步骤为分析问题、设计算法、编写程序、调试程序。算法是程序设计的“灵魂”，最核心过程。 2．法的特征 一个算法应该具有以下五个重要的特征： 1、有穷性：一个算法必须保证执行有限步之后结束； 2、确定性：算法的每一步骤必须有确切的定义； 3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件； 4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性：算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成；（也称之为有效性） 3．算法的描述方法 算法的描述：可分多种表达方法，一般用自然语言、流程图和伪代码进行描述。 （1）自然语言描述法：指用人们日常生活中使用的语言（本国语言），用自然语言描述符合我们的习惯，且容易理解。 例1：求圆的周长和面积 算法如下：（自然语言描述法） （1）输入半径r ； (2) 计算周长c=2*π*r ； (3) 计算面积 s=π*r*r ； (4) 输出周长c，输出面积s ； (5) 结束 例2：工人每天工作8小时,每小时9元,超过8小时的每小时增加15%的加班费,计算工人每天的应发的日工资。（1）输入工作小时X （2）判断X值，分别计算 ●X小于8，工资=X*9 ●X大于8，工资=X*9＋(X-8)*9*0.15 （3）输出工资 （4）结束 练习：求三个数中的最大数。（用自然语言描述） （2）流程图描述：也称程序框图，它是算法的一种图形化表示方法。且描述算法形象、直观，更易理解。
用于运动识别的聚类特征融合方法和装置 提供了一种用于运动识别的聚类特征融合方法和装置，所述方法包括：将从被采集者的加速度信号 中提取的时频域特征集的子集内的时频域特征表示成以聚类中心为基向量的线性方程组；通过求解线性方程组来确定每组聚类中心基向量的系数；使用聚类中心基向量的系数计算聚类中心基向量对子集的方差贡献率；基于方差贡献率计算子集的聚类中心的融合权重；以及基于融合权重来获得融合后的时频域特征集。 加速度信号 →时频域特征 →以聚类中心为基向量的线性方程组 →基向量的系数 →方差贡献率 →融合权重 基于特征组合的步态行为识别方法 本发明公开了一种基于特征组合的步态行为识别方法，包括以下步骤：通过加速度传感器获取用户在行为状态下身体的运动加速度信息；从上述运动加速度信息中计算各轴的峰值、频率、步态周期和四分位差及不同轴之间的互相关系数；采用聚合法选取参数组成特征向量；以样本集和步态加速度信号的特征向量作为训练集，对分类器进行训练，使的分类器具有分类步态行为的能力；将待识别的步态加速度信号的所有特征向量输入到训练后的分类器中，并分别赋予所属类别，统计所有特征向量的所属类别，并将出现次数最多的类别赋予待识别的步态加速度信号。实现简化计算过程，降低特征向量的维数并具有良好的有效性的目的。 传感器 →样本及和步态加速度信号的特征向量作为训练集 →分类器具有分类步态行为的能力 基于贝叶斯网络的核心网故障诊断方法及系统 本发明公开了一种基于贝叶斯网络的核心网故障诊断方法及系统，该方法从核心网的故障受理中心采集包含有告警信息和故障类型的原始数据并生成样本数据，之后存储到后备训练数据集中进行积累，达到设定的阈值后放入训练数据集中；运用贝叶斯网络算法对训练数据集中的样本数据进行计算，构造贝叶斯网络分类器；从核心网的网络管理系统采集含有告警信息的原始数据，经贝叶斯网络分类器计算获得告警信息对应的故障类型。本发明，利用贝叶斯网络分类器构建故障诊断系统，实现了对错综复杂的核心网故障进行智能化的系统诊断功能，提高了诊断的准确性和灵活性，并且该系统构建于网络管理系统之上，易于实施，对核心网综合信息处理具有广泛的适应性。 告警信息和故障类型 →训练集 —>贝叶斯网络分类器
第31卷 第1期 吉首大学学报(自然科学版)Vol.31 No.1 2010年1月J ournal of J is ho u Uni ver s i t y (Nat ural Sci ence Editio n )J an.2010 文章编号:1007-2985(2010)01-0035-05 蚁群算法研究应用现状与展望 3 叶志伟,周 欣,夏 彬 (湖北工业大学计算机学院,湖北武汉 430068) 摘 要:蚁群算法是工程优化领域中新出现的一种仿生进化算法.首先介绍基本蚁群算法的原理和模型,然后评述近年来对蚁群算法的若干改进以及在许多新领域中的发展应用,最后对蚁群算法未来的发展和研究方向进行展望. 关键词:蚁群算法;优化;最优决策 中图分类号:TN911.73 文献标识码:A 实际工程问题常具有复杂性、非线性等特点,而它的解决通常也是一种寻求最优决策的过程,因此寻求一种适合大规模并行、具有智能特征的优化算法已经成为引人注目的研究方向.目前,除了业已得到公认的遗传算法、模拟退火算法、禁忌搜索算法等热门进化算法,蚁群优化算法[1-3](Ant Colony Optimization Algo rithm ,ACO ,也称蚂蚁系统)正在开始崭露头角,为复杂的系统优化问题提供了新的具有竞争力的求解算法.ACO 是由意大利学者M.D o rigo 等人于1991年首先提出来一种新兴模拟生物智能的算法,在短期内得到了迅速的发展,除了用于大批经典优化问题的求解,如二次分配问题(Qua d 2ra tic Assignme nt Problem ,QAP )、有序排列问题(Sequential Orde ring Problem ,SOP )[2-16]等,在实际工程领域也得到广泛的应用. 1 基本ACO 原理 为了说明ACO 模型,这里引入旅行商问题(TSP ),它是一类经典的组合优化问题,即在给定城市个数和各城市之间距离的条件下,要找到1条遍历所有城市当且仅当1次最短的线路. 为模拟真实蚂蚁的行为,首先引入如下标记:m 是蚁群的规模;b i (t )是t 时刻位于城市i 的蚂蚁数量,m = ∑n i =1 b i (t );d i j 是两城市i 和j 之间的距离;ηi j 是由城市i 转移到城市j 的可见度,反映城市i 转移到城市j 的启发信息,这个量在ACO 的 运行中保持不变;τi j 是边(i ,j )上的信息素轨迹强度;Δτi j 是蚂蚁k 在边(i ,j )上留下的信息素轨迹量;p k i j 是蚂蚁k 的转移概 率,j 是没有访问过的城市. 每只蚂蚁都是具有如下行为的个体:①由城市i 转移到城市j 的过程中或是在完成1次循环以后,蚂蚁在边(i ,j)上释放信息素;②蚂蚁随机的选择下一个将要访问的城市;③在完成一次循环以前,不允许选择已经访问过的城市. 基本ACO 在TSP 问题中实现的具体过程如下:假设将m 只蚂蚁放入到n 个随机选择的城市中;每只蚂蚁每步根据一定的概率,选择下一个它还没有访问过的城市,将所有城市遍历完以后回到出发的城市.蚂蚁选择目标城市的概率公式为 p k ij (t)= (τi j (t ))α(ηij )β/∑j ∈allowed (τi j (t ))α(ηi j )β j ∈allowed ,0 othe rwise.(1) 在得到每个候选城市的选择概率以后,蚂蚁运用随机选择的方式决定下一步要去的城市.(1)式中各参数意义如下:α表示信息素信息相对重要程度;β表示可见度信息相对重要程度.为了避免对同一个城市的重复访问,每只蚂蚁都保存一个列表tabu (k ),用于记录到目前为止蚂蚁已经访问过的城市集合.为了避免残留信息素过多引起残留信息淹没启发信息的现象发生,在每一只蚂蚁走完1步或者完成对所有n 个城市的访问后,对残留信息素进行更新处理.这样得到(t +n)时刻在(i , 3收稿日期:2009-04-10 基金项目:湖北省自然科学基金资助项目(2008CDZ003;2008CDB342);湖北省教育厅优秀中青年项目(Q20081409;Q20081402) 作者简介叶志伟(),男,湖北浠水人,湖北工业大学计算机学院副教授,博士,主要从图像处理领域和智能计算研究:1978-.
自适应卡尔曼滤波 卡尔曼滤波发散的原因 如果卡尔曼滤波是稳定的，随着滤波的推进，卡尔曼滤波估计的精度应该越来越高，滤波误差方差阵也应趋于稳定值或有界值。但在实际应用中，随着量测值数目的增加，由于估计误差的均值和估计误差协方差可能越来越大，使滤波逐渐失去准确估计的作用，这种现象称为卡尔曼滤波发散。 引起滤波器发散的主要原因有两点： （1）描述系统动力学特性的数学模型和噪声估计模型不准确，不能直接真实地反映物理过程，使得模型与获得的量测值不匹配而导致滤波发散。这种由于模型建立过于粗糙或失真所引起的发散称为滤波发散。 （2）由于卡尔曼滤波是递推过程，随着滤波步数的增加，舍入误差将逐渐积累。如果计算机字长不够长，这种积累误差很有可能使估计误差方差阵失去非负定性甚至失去对称性，使滤波增益矩阵逐渐失去合适的加权作用而导致发散。这种由于计算舍入误差所引起的发散称为计算发散。 针对上述卡尔曼滤波发散的原因，目前已经出现了几种有效抑制滤波发散的方法，常用的有衰减记忆滤波、限定记忆滤波、扩充状态滤波、有限下界滤波、平方根滤波、和自适应滤波等。这些方法本质上都是以牺牲滤波器的最优性为代价来抑制滤波发散，也就是说，多数都是次优滤波方法。 自适应滤波 在很多实际系统中，系统过程噪声方差矩阵Q和量测误差方差阵R事先是不知道的，有时甚至连状态转移矩阵 或量测矩阵H也不能确切建立。如果所建立的模型与实际模型不符可能回引起滤波发散。自适应滤波就是这样一种具有抑制滤波发散作用的滤波方法。在滤波过程中，自适应滤波一方面利用量测值修正预测值，同时也对未知的或不确切的系统模型参数和噪声统计参数进行估计修正。自适应滤波的方法很多，包括贝叶斯法、极大似然法、相关法与协方差匹配法，其中最基本也是最重要的是相关法，而相关法可分为输出相关法和新息相关法。 在这里只讨论系统模型参数已知，而噪声统计参数Q和R未知情况下的自适应滤波。由于Q和R等参数最终是通过增益矩阵K影响滤波值的，因此进行自适应滤波时，也可以不去估计Q和R等参数而直接根据量测数据调整K就可以了。
算法和算法的描述（教学案例） 教材分析： 这节课内容主要是一些概念和理论，而算法的概念和理论都太抽象，讲起来非常的枯燥乏味，那么就要把这些抽象的东西变得通俗易懂，使学生能轻松而又愉快的接受并理解。 学生分析： 学生基本上没有接触过编程，那么在高中阶段初步接触编程，学生首先会感到很深奥，看到书中的程序语句，尤其是看到后面的长一点的程序语句更是觉得可怕，那教师必须要考虑在授课中如何正确引导，以什么样的方式进行。学生有没有兴趣学，往往看这个课是不是有意思，难不难学，一看难学又乏味，就开始产生厌学的情绪。 教学目标： 引导学生对编程的兴趣，理解算法的概念和如何科学合理的选择和设计算法，为程序设计打好基础。 教学重点： 算法的概念、算法的设计和选择。 教学难点： 如何科学合理的选择和设计算法。 教学方法： 与学生进行互动探讨式教学,以趣味智力题激发学生探索解决问题的兴趣，以故事事例和具体的程序运行对比，引导学生一步步的思考，从而总结出算法的概念，以及如何设计和选择算法，充分调动学生的主观能动性和探究学习能力。 教学过程： 1、引导学生对编程的兴趣 （1）教师：同学们喜欢玩电脑游戏吗？ （2）学生：喜欢！（说到游戏学生总是表现出很浓的兴趣。） （3）教师：在上机练习课的时候，总发现有个别同学偷偷的玩游戏，其实你们喜欢，老师也很喜欢，那么同学们想不想自己编个游戏来玩呀？ （4）学生：会不会很麻烦！（学生表现出好奇，又对编程心里还没有底。） （5）教师：不用担心，编程并不像你们所想像的那样难，很快你们就会编一些小游戏程序了。其实编程是件非常有意思的事情，在以后的学习中你会发现自己越来越喜欢编程，甚至会着迷的。 2、算法的概念 (1)教师：幻灯片出示一个经典的趣味性例子, 有一个牧羊人带着一头羊,一只狼和一颗大白菜准备过河,他找到一只很小的船,每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，牧羊人应如何过河？ （2）教师：分组讨论，前后四个同学为一组,把你们的橡皮擦放到一块,分别写上狼、羊、白菜，你们自己是牧羊人，现在请同学们来设计一个方案,把3样东西安然无恙的带过河。我们来比一比看哪组同学最快完成。 课堂立即活跃起来，同学们把它当作一种游戏全都投入进去了，积极思考起来。 （3）很快就有学生举手回答。 过河的方案: 第一步：人和羊过河，人返回，留下羊； 第二步：人和狼过河，人和羊返回，留下狼； 第三步：人和菜过河，人返回，留下菜； 第四步：人和羊过河。 （4）教师：同学们这个方案行不行？ （5）学生：行。
科技信息 1、引言 在地震勘探中，野外作业的目的是收集原始数据，即进行地震数据的收集。这是地震勘探中获取地下地质信息的根本环节，所得数据是处理及解释等后续任务所依据的最根本的资料。因而，野外作业的质量直接影响到勘探的效果。野外收集数据作业中的差错可能会导致勘探的处理解释成果与地下实际情况全然不同。所以，有必要特别的重视地震数据采集。 地震勘探的最终目的是有效地处理地质难题。在一个工区能否使用地震勘探处理难题，很大程度上决定于该工区的地震地质条件。尤其是表层的地震地质条件，对采集数据的质量影响很大。近地表地层由于地质风化效果变得疏松，地震波在该地层传播的速度，通常比深部微风化的基岩中的速度要低得多。低速带的疏松性对地震波有很强的吸收效果。所以在地震勘探时，通常穿过低降速带在基岩中进行炸药震源的激发。这就要求有精细的近地表模型来指导井位和井深的确定。 野外采集的数据可以通过拟合算法来建立近地表模型，从而指导打井和静校正。薄板样条、三角剖分和B 样条是较常见的曲面插值拟合方法，本文通过实验对三种算法的优劣进行分析评价。 2、薄板样条法 薄板样条法的特点在于它是一种利用最小能量的函数来刻画不规则平面的插值方法。该方法的特点在于它的求解控制方程，用到的方程为： W (x )=∑i =1N αi |x -x i |2 log |x -x i | 2 其中W (x )指x 处的形变， αi 是待定系数。薄板样条法同样是无限平板样条方法，采用薄板样条法进行计算时，已知位移点的数目不受限制，但为了保证计算的精度，要求至少有三个已知位移点。 薄板样条在工程地质学上描绘如下：关于一阶问题，单元的三次样条能够被认为是处于平衡状态下的曲折变形梁；关于二阶问题，这种样条能够经过薄板的最小曲折变形来断定。它所确定的插值函数，不会受到被插值布局的转动和平移的影响，在对变化的曲面和弹性曲面进行插值时，显得更有用。 3、Delaunay 三角剖分 四面体是三维空间三角剖分的最小单元，它包含了许多其它单元没有的优势。而三角形是二维空间三角剖分的最小单元，它也包含了许多其它单元无法替代的优势；Delaunay 三角剖分算法是运用得最多的三角剖分算法。它具有“空外接圆”和“最小内角最大”两大特色，能够减少畸形三角单元的生成，从而保证了整个三角剖分质量达到最优。Delaunay 三角剖分算法是所有的三角剖分算法中一种比较常用、高效的三角剖分算法。 4、二次均匀B 样条曲线法 空间n+1个顶点的位置矢量P i （i=0，1，…，n ）定义n －1段二次（k ＝0,1,2，n=2）均匀B 样条曲线，每相邻三个点可构造一曲线段P i (u )（i=1，…，n －1），其定义表达为： P i (u )=12[] u 2u 1é?êêù?úú1-21-2201 10é?êêù?úúP i -1P i P i +1i =1,...,n -1; 0≤u ≤1=12!(1-2u +u 2)P i -1+12!(1+2u -2u 2)P i +12! u 2P i + 1图1二次B 样条曲线 如图1所示，端点位置矢量：P i (0)=0.5(P i -1+P i )，P i (1)= 0.5(P i +P i +1)， 即曲线起点和终点分别在控制多边形P i -1P i 和P i P i +1的中点。若P i -1、P i 、P i +1三个顶点位于同一条直线上，P i (u )蜕化成P i -1P i P i +1直线边上的一段直线。 端点一阶导数矢量：P i (0)=P i -P i -1，P i (1)=P i +1-P i ，P ′i (0)= P i +1-P i ，P ′i (1)=P i +2-P i +1， 即曲线的起点的切向量和终点的切向量分别和两个边重合，并且相邻的两曲线在节点处具有一阶导数连续。 二阶导数矢量：P ″ i (0)=P i -1-2P i +P i +1=P ″i (1)=P ″i (t )， 即曲线内的所有点处的二阶导数相等，并且临近的两条曲线在节点处的二阶导数不连续。 5、实例分析5.1速度比较 本文对一组理论生成的函数数据和两组某工区实测数据，按照控制点个数进行三种方法的插值拟合。计算速度见表1。 表1三种算法的耗时比较 数据函数数据1函数数据2函数数据3工区数据1工区数据2 控制点个数N 6252500100003525984 耗时/s 薄板样条 2493∞1∞ 三角剖分 1∞∞1∞ B 样条12214 从表1可以看出，随着控制点个数的增大，三种拟合算法对应的插 值速度变得越来越慢。其中薄板样条算法最慢，而且当数据量较大时会占用将近全部内存，导致不能计算出结果。B 样条插值速度最快，其次是三角剖分插值方法，薄板样条最慢。因此在稠密控制点和海量数据点的情况下，本文采用B 样条插值法重构近地表模型。 5.2精度比较 野外测量数据存在误差，而且小折射和微测井解释会受初至波拾取的影响，所以重构近地表模型时需要综合考虑到模型精度和光滑 度。插值法的精度可用平均相对误差ε来表示，ε=∑i =1N |v i -f (x i ,y i )f (x i ,y i )|/N ，其中N 为控制点个数，v i 为拟合值，f (x i ,y i )为真实值。 表2三种算法的误差比较 数据函数数据1函数数据2函数数据3工区数据1工区数据2 控制点个数N 6252500100003525984 误差ε 薄板样条0.2384122840.598707063 0.002943122三角剖分 0.893974868B 样条0.0874910230.1028944690.107028292 0.00380291 0.002070894 对三种算法拟合精度进行分析。首先对其中工区一拟合效果进行分析，其中三角剖分插值拟合算法精度很低，误差高达89%，从图2中可以看出，拟合效果图光滑性和连续性很差。在数据量较少且稀疏的情况下，三角剖分插值方法并不适用。薄板样条插值拟合效果最好，曲面平滑连续。误差小，精度高。B 样条拟合速度快，但是在图2中明显看出，B 样条插值拟合的效果有明显的样条痕迹，近地表地形曲面重构算法研究 中国地质大学（北京）地球物理与信息技术学院张雨飞 ［摘要］ 在地震资料的野外采集过程中，为了尽可能地消除近地表低速带、降速带对地震波的吸收衰减作用，要求穿过低降速带，将炸药放入高速层引爆。所以要求高精度的近地表模型来指导设计激发井深，然后确保高质量的单炮记录。地表曲面重构技术是近地表模型建立的首要关键环节，对于野外数据的采集和后续的处理解释工作有着重要的含义。本文重点研究薄板样条、三角剖分和B 样条的拟合方法，并通过具体工区实例分析其拟合效率。 ［关键词］ 曲面拟合薄板样条三角剖分B 样条近地表建模（下转第132页） — —137
第19卷哈尔滨师范大学自然科学学报 V ol.19,N o.52003 第5期 NAT URA L SCIE NCES JOURNA L OF H AR BI N NORM A L UNI VERSITY 几种三维重建方法的比较3 尚明姝 解 凯 (哈尔滨师范大学) 【摘要】 本文综述了三维重建的若干方法,并分析比较了各种方法的特点,同时 还给出了在欧氏几何下一种简单摄像机配置下的三维重建空间点的简单方法1此外给出了通过矩阵分解的办法来推导基本矩阵F 的方法1 关键词:三维重建;摄影重建;基本矩阵 收稿日期:2003-09-04 3本课题是黑龙江省教育厅科技资金(10531085)、哈师大校基金资助项目 1 三维重建的意义 客观世界在空间上是三维的,在工程技术界一般要对三维物体进行分析,以便获取有用的信息1目前,大多数图像采集装置所获取的图像本身是在二维平面上的,尽管其中可以含有三维物体的空间信息1因此,要从图像认识真实物体,就要从二维图像中恢复三维空间信息,这正是三维立体重建所要完成的任务1 2 三维重建的若干方法 211 欧氏几何意义下三维重建的一般方法 欧氏几何下三维重建的一般方法是在摄像机已定标情况下,从重建空间点开始,由三维顶点计算空间直线、空间二次曲线,由计算出的空间直线重组三维面、二次曲面,最后由计算出的三维平面、二次曲面重建三维实体121111 空间点的重建 空间物体表面是由三维点构成的,若能获得足够多的三维点,三维物体的形状与位置就可唯一确定1因此,用立体视觉的方法获得三维点的坐标是最基本的、最简单的,但也是十分重要的1 假定对应空间点的两个摄像机上的图像点已 从两幅图像中分别检测出来,两个摄像机已标定, 其投影矩阵已知1通过列出空间点在图像上投影 点坐标(u ,v )与世界坐标系(x ,y ,z )的关系,得出方程组,解出此空间点在世界坐标系下的坐标1 为了更清楚地了解点重建的物理意义,在文献[1]中给出了一种简单摄像机配置下空间点重建方法1以下作者将给出另一种简单摄像机配置下三维重建的简单方法1 如图1、2所示,原摄像机配置为:C 1与C 2摄像机的焦距相等,各内部参数也相等,且两个摄像机的光轴互相平行,X 轴互相重合,Y 轴互相平行,两个摄像机坐标系只差X 轴方向上的一个平移,平移距离记为b.现将左摄像机绕Y 轴顺时针转θ角,右摄像机逆时针转θ角,以左摄像机坐标系为世界坐标系1 在图2所示配置下,任一空间点在C 1坐标系下坐标为(x 1,y 1,z 1),在C 2坐标系下坐标为(x 2,y 2,z 2),其中,(x 1,y 1,z 1)与(x 2,y 2,z 2)关系如下 : 转换为方程:
卡尔曼滤波简介及其算法实现代码 卡尔曼滤波算法实现代码（C，C＋＋分别实现） 卡尔曼滤波器简介 近来发现有些问题很多人都很感兴趣。所以在这里希望能尽自己能力跟大家讨论一些力所能及的算法。现在先讨论一下卡尔曼滤波器，如果时间和能力允许，我还希望能够写写其他的算法，例如遗传算法，傅立叶变换，数字滤波，神经网络，图像处理等等。 因为这里不能写复杂的数学公式，所以也只能形象的描述。希望如果哪位是这方面的专家，欢迎讨论更正。 卡尔曼滤波器– Kalman Filter 1．什么是卡尔曼滤波器 （What is the Kalman Filter?） 在学习卡尔曼滤波器之前，首先看看为什么叫“卡尔曼”。跟其他著名的理论（例如傅立叶变换，泰勒级数等等）一样，卡尔曼也是一个人的名字，而跟他们不同的是，他是个现代人！ 卡尔曼全名Rudolf Emil Kalman，匈牙利数学家，1930年出生于匈牙利首都布达佩斯。1953，1954年于麻省理工学院分别获得电机工程学士及硕士学位。1957年于哥伦比亚大学获得博士学位。我们现在要学习的卡尔曼滤波器，正是源于他的博士论文和1960年发表的论文《A New Approach to Linear Filtering and Prediction Problems》（线性滤波与预测问题的新方法）。如果对这编论文有兴趣，可以到这里的地址下载： https://www.doczj.com/doc/ea2684899.html,/~welch/media/pdf/Kalman1960.pdf。 简单来说，卡尔曼滤波器是一个“optimal recursive data processing algorithm（最优化自回归数据处理算法）”。对于解决很大部分的问题，他是最优，效率最高甚至是最有用的。他的广泛应用已经超过30年，包括机器人导航，控制，传感器数据融合甚至在军事方面的雷达系统以及导弹追踪等等。近年来更被应用于计算机图像处理，例如头脸识别，图像分割，图像边缘检测等等。 2．卡尔曼滤波器的介绍 （Introduction to the Kalman Filter） 为了可以更加容易的理解卡尔曼滤波器，这里会应用形象的描述方法来讲解，而不是像大多数参考书那样罗列一大堆的数学公式和数学符号。但是，他的5条公式是其核心内容。结合现代的计算机，其实卡尔曼的程序相当的简单，只要你理解了他的那5条公式。 在介绍他的5条公式之前，先让我们来根据下面的例子一步一步的探索。 假设我们要研究的对象是一个房间的温度。根据你的经验判断，这个房间的温度是恒定的，也就
一第４２卷第１期２０１９年１月一一一一一一一一一一一一一一安徽师范大学学报(自然科学版)ＪｏｕｒｎａｌｏｆＡｎｈｕｉＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ(ＮａｔｕｒａｌＳｃｉｅｎｃｅ)一一一一一一一一一一一一Ｖｏｌ.４２Ｎｏ.１Ｊａｎ.２０１９一ＤＯＩ:１０.１４１８２/Ｊ.ｃｎｋｉ.１００１－２４４３.２０１９.０１.００８ 基于点云数据的曲面重建算法比较研究 吴一旭１?一卢凌雯２?３?４?一梁栋栋２?３?一汪晓楚２?３ (１.安徽师范大学计算机与信息学院?安徽芜湖一２４１００３?２.安徽师范大学地理与旅游学院?安徽芜湖一２４１００３?３.安徽师范大学地理大数据研究中心?安徽芜湖一２４１００３?４.苏州市测绘院有限责任公司?江苏苏州一２２１００８) 摘一要:针对现有的多种点云数据曲面重建算法?从曲面重建的网格曲面二隐式曲面二参数曲面三种 不同重建方式入手?比较了四种算法针对不同目标物重建的优劣?并给出相应的精度评价?实验结 果表明:基于ＮＵＲＢＳ参数曲面重建的方式最佳?基于贪婪投影三角化网格曲面重建的方式其次? 基于移动立方体与基于泊松方程隐式曲面重建方式的时间复杂度与空间复杂度较大?且重建后的 点云模型误差也较大? 关键词:贪婪三角化?移动立方体?泊松方程?ＮＵＲＢＳ?曲面重建 中图分类号:Ｏ１７５.１４一一一文献标志码:Ａ一一一文章编号:１００１－２４４３(２０１９)０１－００４６－０５ 在逆向工程二计算机视觉二ＣＡＤ制图二三维测量技术等众多领域?点云数据处理技术从八十年代起就被广泛应用?且发展至今[１]?随着计算机辅助设计与计算机图形学的发展?越来越多的学者对点云数据的曲面重建技术产生了浓厚的兴趣?从现有研究来看?曲面重构大致可以分为显式曲面重构和隐式曲面重构两类方法[２]?显式曲面重构方法提出较早?需要先将点云参数化?然后再进行曲面重构?它一般不能用单个曲面来直接拟合点云?比如ＮＵＲＢＳ算法需要先将点云分割成不同区域?然后分别拟合各自的曲面?最后将拟合的各曲面进行拼合得到完整曲面?隐式曲面重构方法利用隐式函数得到逼近点云的等值曲面?相比显式曲面重构方法?隐式曲面重构更适用于重构复杂拓扑形状的曲面?且重构的曲面具有很好的封闭性和完整性?除此之外?刘含波[３]等对曲面重建方法有两种分类方式:根据生成的表面是否经过原始采样点?分为基于插值的表面重建和基于逼近的表面重建?根据重建过程中所依赖的插值点的信息?分为基于全局准则的整体重建和基于局部准则的局部重建?宋大虎等[４]根据现有算法的特点?将曲面重建算法分为隐式曲面算法二参数曲面算法二基于学习的方式和Ｄｅｌａｕｎａｙ三角剖分算法? 本文从点云表面重建方式的角度?把曲面重建分成网格曲面二隐式曲面二参数曲面?其中贪婪投影三角化算法属于网格曲面重建?移动立方体算法以及泊松方程算法属于隐式曲面重建?ＮＵＲＢＳ算法属于参数曲面重建? 在实际工程中?采用多边形模型如网格方法作为输入输出?无论在数据处理方面?还是在计算机显示方面?都拥有一定的优势[５]?Ｄｅｌａｕｎａｙ三角网的逐点插入法与分治合并法两大方法在１９世纪７０年代相继被提出?２０世纪８０年代末?Ｃｈｅｗ提出了ＤｅｌａｕｎａｙＲｅｆｉｎｅｍｅｎｔ算法[６]?在９０年代初?Ｒｕｐｐｅｒｔ改进了ＤｅｌａｕｎａｙＲｅｆｉｎｅｍｅｎｔ算法?使该算法得到的三角形最小角大于２０.７度[７]?之后?Ｒｉｖａｒａ二Ｈｉｔｓｃｆｅｌｄ二Ｓｉｍｐｓｏｎ等人进一步扩展和优化?使得最小角的最小值达到３０度[８]?基于隐式函数的曲面重构方法可分为局部拟合方法和全局拟合方法?基于局部拟合的隐式函数重构方法出现较早?最早的代表性方法山由Ｈｏｐｐｅ等[９]人提出?先拟合局部点云的平面?再估算点云的一致性法矢?然后构建有向距离函数?最后提取其零等值面?其中代表性的是移动最小二乘曲面(ＭＬＳ)方法[１０]?和局部拟合方法不同?全局隐式拟合方法利用数学函数同时拟合所收稿日期:２０１８－０４－２６基金项目:安徽省智慧城市与地理国情监测重点实验室２０１６年度开放性基金重点课题. 作者简介:吴旭(１９７１ )?女?安徽阜阳市人?实验师?研究方向为地理计算和可视化?通讯作者:梁栋栋(１９７１ )?男?安徽亳州人?副教授?博 士?研究方向为地图可视化与三维建模. 引用格式:吴旭?卢凌雯?梁栋栋?等.基于点云数据的曲面重建算法比较研究[Ｊ].安徽师范大学学报(自然科学版)?２０１９?４２(１):４６－５０.
由点云重构CAD模型的基本步骤包括：点云分块、点云切片、曲面重构、CAD模型。 1.点云分块 由于工程实际中原型往往不是由一张简单曲面构成，而是由大量初等解析曲面(如平面、圆柱面、圆锥面、球面、圆环面等)及部分自由曲面组成，故三维实体重构的首要任务是将测量数据按实物原型的几何特征进行分割成不同的数据块，使得位于同一数据块内的数据点可以一张特定的曲面来表示，然后针对不同数据块采用不同的曲面建构方案(如初等解析曲面、B-spline 曲面、Bezier曲面、NURBS 曲面等)进行曲面重建，最后将这些曲面块拼接成实体，它包括点集分割与曲面重建两部分。 为了实现点云的分块功能，同时也为了后续曲线拟合中重要点的选取工作，我们建立了图元的拾取模块。它包括多边形拾取、矩形拾取、点选三个小的部分，运用此模块我们可以利用鼠标对空间点云进行任意的分割和提取。 多边形拾取与矩形拾取类似，都是在视图上确定一个选择区域，然后根据视图上的图形是否完全落在这个选择区域中来决定视图上的图形是否被选取。由于我们针对的对象是三维空间中的图元，因此在视图窗口中所确定的区域实际上是一个矩形体或者多面体，所拾取的图元是位于这个体中的对象。问题的关键在于如何确定图元是否位于矩形体或多面体中。 基于OpenGL的拾取机制很好的解决了这个问题。物体的实际坐标经模型视图变换、投影变换、视口变换后显示为屏幕上的一点，OpenGL的gluUnProject（）可以做该过程的逆变换，即根据已知屏幕上点的二维坐标以及经过的变换矩阵可求出该点变换前在三维空间的坐标位置，但需要事先给定二维屏幕坐标的深度坐标。考虑OpenGL的投影原理，将0.0和1.0作为前后裁剪面的深度坐标。因此两次调用gluUnProject()可得到视图体前后裁剪面上的两个点，也就是屏幕上点的两个三维坐标。 对于矩形拾取而言，判断点是否位于矩形体中比较简单，可以选取每个空间点，判断点的坐标是否位于矩形盒三个方向的极限范围内，如果满足条件，则可认为该点符合条件，被拾取到了，并高亮显示。对于多边形拾取而言，我们借助面的法矢进行判断，对于任意空间点p，首先计算出各个面的外法矢n，然后在每个面任选一点v与p构成向量pv,如果对于多边形的每个面恒有n*pv >0,则可认为该点位于多边形的内部，当然也可利用射线法进行判断，从该点出发,作任意方向的一根射线,考察此射线与三维物体各面的交点数,如果总数=0或其它偶数,则在三维物体之外,如果总数为奇,则在三维物体之内。点选相对比较简单，对鼠标点击点向各个方向各扩展一定距离，构成一个矩形，然后按照矩形拾取的原理进行判断。需要注意的是上述三种方法不可避免的会出现透视方向的重叠点，必须根据到前裁剪平面的距离进行取舍。下面分别给出一些简单的例子。 多变形拾取 在多边形拾取对话框中我们可以根据操作的类型选择是对网格还是点云进行拾取，同时所保留的区域（多边形内、外、或者同时）也可进行选择。基本操作步骤为：左键点击多边形按钮开始选择，在点云中左键单击作为多边形顶点，同时开始绘制，点击Apply结束多边形绘制，同时高亮显示拾取点云。