一种新的基于发散度函数的地形模型简化方法  

A New Simplification Method for Terrain Model Based on Divergence Function

作　　者：张慧杰[1,2] 孙吉贵[2] 吕英华[1] 吕楠[2] 王远志[3] 

机构地区：[1]东北师范大学计算机学院,长春130117 [2]吉林大学计算机科学与技术学院,长春130012 [3]安庆师范学院计算机系,安徽安庆246011

出　　处：《计算机学报》2009年第5期962-973,共12页Chinese Journal of Computers

基　　金：国家自然科学基金(60773097);国家自然科学青年基金(60603030);东北师范大学自然科学青年基金(20081003);安徽省高校省级自然科学重点项目基金(KJ2008A18ZC)资助~~

摘　　要：提出了一种新的地形模型简化方法,该方法是在隐式四叉树层次结构基础上,结合离散粒子群思想建立地形的简化模型.文中重新定义粒子为具有层次信息的特征点的集合,从而每个粒子与简化模型的一个候选解相对应.为了实现多个粒子的空间压缩和快速检索,给出了隐式四叉树层次结构的快速索引方法.此外提出了基于法向矢量夹角的发散度函数的误差计算方法,重新定义了既满足地形模型误差要求同时兼顾模型简化比例的粒子评价函数,使地形简化模型在保持细节特征和轮廓特征的同时获得了更优的简化比率和模型精度.最后采用最优粒子作为启发信息引导简化过程,因此多个粒子迅速收敛于最优简化模型,从而模型的简化效率大大提高.文中方法均在多个基准数据上进行实验研究,结果表明与经典层次简化方法相比,算法效率和模型精度均显著提高.This paper presents a fast simplification method for the terrain model using the discrete particle swarm algorithm based on the quad-tree hierarchical structure. What is new in this paper is that the particle has been redefined as a set of feature points. And then each particle presents a candidate solution of the approximation model. In order to compress those particles, a connotative quad-tree hierarchical structure and its index technology are proposed in this paper. Usually, an error measure is very important to an approximation. Therefore, this paper proposes a new divergence function, which is better to measure the surface of an approximation. Based on it, the evaluation function of particle is defined. Since both the detailed feature and the simplification ratio are also taken into account, the approximation is higher quality. Finally, the optimal particle is taken as the heuristic information to accelerate the simplification, so that these particles can converge rapidly to the optimal approximation. As a result, the method is of higher efficiency. By the experiments on many benchmark terrain models, the efficiency of the proposed method and the quality of approximations are improved greatly, compared with the typical hierarchical simplification algorithms.

关 键 词：四叉树层次结构 简化模型 评价函数 离散粒子群算法 地形特征 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]