第３４卷第２期 ２０１４年３月 海洋测 绘 ＶＯ１．３４．Ｎｏ．２ Ｍａｒ．，２０１４ ＨＹＤＲＯＧＲＡＰＨＩＣ ＳＵＲＶＥＹＩＮＧ ＡＮＤ ＣＨＡＲＴＩＮＧ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７１—３０４４．２０１４．０２．００５ 机载ＬｉＤＡＲ点云的Ｄｅｌａｕｎａｙ三角网快速生成算法 罗 胜 ，王 鑫 ，孙￣－－？－ （１．解放军信息工程大学地理空间信息学院，河南郑州４５００５２；２．６１３６３部队，陕西西安７１００５４） 摘要：为了提高机载激光点云的Ｄｅｌａｕｎａｙ三角网生成效率及稳定性，基于分块算法的思想，改进了点云数据 的分块方式，利用点云的凸包及重心点进行数据分块，并结合子块中激光点个数阈值进行三角形子块的细分，从而 避免了传统子块合并过程中复杂的相邻三角形搜索及优化处理，仅需简单的一步优化即可完成相邻子块的合并， 大大提高了算法的效率。经实验证明，该算法简单、高效且稳定性好，尤其对于大数据量的机载ＬｉＤＡＲ点云 Ｄｅｌａｕｎａｙ三角网生成具有明显的优势。 关键词：ＬｉＤＡＲ；Ｄｅｌａｕｎａｙ三角网；凸包；自适应分块；ＬＯＰ 中图分类号：Ｐ２３７ 文献标志码：Ａ 文章编号：１６７１—３０４４（２０１４）０２—００１８—０３ １ 引 言 效率，徐青、刘永和等 一 提出了自适应分块算法， 提高了构网效率，但在子块合并过程中仍需进行大 机载激光雷达（ＬｉＤＡＲ）能够快速精确地获取地 物目标表面的位置和高度信息，为目标信息提取和 三维重建提供了新的数据源。ＬｉＤＡＲ点云中各激 光点是离散的，现有的代表性的离散点云数据表达 形式主要有：规则格网、不规则三角网（ＴＩＮ）、剖面 （ｐｒｏｆｉｌｅｓ）和体元（ｖｏｌｕｍｅｔｒｉｃ ｐｉｘｅｌ，Ｖｏｘｅ１）等，各种形 量的相邻三角形搜索与优化计算，且在连接相邻子 块区域时需生成大量新的三角形，算法的稳定性较 差。因此，如何在提高构网效率的同时兼顾算法的 稳定性是本文研究的重点。本文基于分块算法的思 想，改进点云的分块方式，利用点云的初始凸包点及 重心点进行点云数据分块，仅需简单的一步优化处 理即可实现相邻子块间的合并，从而大大简化各子 块的合并处理过程，提高整体Ｄｅｌａｕｎａｙ网生成的效 率与稳定性。 ２．１ 点云数据分块 式在特定应用中具有各自的优势…。其中，ＴＩＮ具 有存储高效、数据结构简单、适合表现不规则地面特 征、能够表示线性特征和迭加任意形状的区域边界 等优点，能更好地表达目标的几何空间特征，更大程 度保留地物的形态便于后续处理和分析 Ｊ。在 ＴＩＮ生成方法中，Ｄｅｌａｕｎａｙ三角剖分具有最小角最 大的良好性质，是被公认的最优三角剖分，因此本文 采用Ｄｅｌａｕｎａｙ构网法生成点云的ＴＩＮ，将所有激光 点投影到水平面上生成点云二维Ｄｅｌａｕｎａｙ三角网， 生成完毕后赋回各激光点的高程坐标，实现三维空 间内的机载ＬｉＤＡＲ点云Ｄｅｌａｕｎａｙ三角网生成。 ２机载ＬｉＤＡＲ点云数据Ｄｅｌａｕｎａｙ网生成原理及 方法 一对点云数据中的所有激光点进行三角形区域分 块，并确保每个子块内激光点个数不超过个数阈值 ，具体步骤如下： （１）生成点云凸包。将所有激光点中 ，Ｙ，ｘ＋ｙ， —Ｙ最大值和最小值点作为初始凸包点 Ｊ，按照顺 时针方向生成初始凸包，再利用比较斜率的方法逐 步生成点云的凸包 （如图１中凸包点Ｃ ，ｉ＝１，２， …，８）。 （２）搜索点云重心点。计算所有激光点坐标的 平均值，在点云中搜索与平均值距离最近的激光点， 作为点云的重心点（如图１中的重心点Ｐ ）。 （３）构建初始子块。按照顺时针的方向依次连 接两个相邻凸包点与点云重心点，生成初始的三角 形子块区域（如图１中的初始子块Ｂ ，ｉ＝１，２，…， 般情况下机载ＬｉＤＡＲ点云的数据量较大，而 传统Ｄｅｌａｕｎａｙ网生成算法如逐点插入法、三角网扩 展法、凸包切割法等 随着离散点个数增加构网 时间成指数增长，为了改进大数据量离散点的构网 收稿日期：２０１３—０６－０３；修回１５ｔ期：２０１３—１１－２２ 作者简介：罗胜（１９８２一），男，安徽肥东人，讲师，博士研究生，主要从事数字摄影测量与遥感影像处理与应用研究。 ２４ 海洋测绘 第３４卷 Ａ Ｓｏｎｇ，Ｍ Ｂａｄｉｅｙ．Ｉｍｐａｃｔ ｏｆ ｓｏｕｒｃｅ ｄｅｐｔｈ ｏｎ ｃｏｈｅｒｅｎｔ Ｓｍｉｔｈ Ｋ Ｂ，Ｔａｐｐｅ￣Ｆ Ｄ．ＵＭＰＥ：Ｔｈｅ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ ｕｎｄｅｒｗａｔｅｒ ａｃｏｕｓｔｉｃ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ［Ｊ］．Ｊ．Ａｃｏｕｓｔ． Ｓｏｃ．Ａｍ，２０１０，１２８（２）：５５５—５５８． Ｍｉａｍｉ Ｐａｒａｂｏｌｉｃ Ｅｑｕａｔｉｏｎ Ｍｏｄｅｌ，Ｖｅｒｓｉｏｎ １．０［Ｒ］． Ｍａｒｉｎｅ Ｐｈｙｓｉｃａｌ Ｌａｂｏｒａｔｏｒｙ Ｔｅｃｈｎｉｃａｌ Ｍｅｍｏ ４３２，１ ９９３． 张旭，张永刚．浅海温跃层对声信道影响的仿真研 侍茂崇，等．物理海洋学［Ｍ］．济南：山东教育出版社， ［１１］ ２００４：４９—６１，７３－７４． 究［Ｊ］．系统仿真学报，２０１２，２４（１０）：２１６７—２１７１． Ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ａｎ Ａｃｏｕｓｔｉｃ Ｍｏｄｅｌ ｔｏ Ｓｉｍｕｌａｔｅ Ｔｒａｎｓｍｉｓｓｉｏｎ Ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ Ｓｏｕｎｄ Ｃｕｒｖｅｓ Ｃｏｎｔｒｏｌｌｅｄ ｂｙ Ｓｏｕｎｄ Ｓｐｅｅｄ Ｔｈｅｒｍｏｃｌｉｎｅ ＧＡＯ Ｆｅｉ ，ＰＡＮ Ｃｈａｎｇｍｉｎｇ ，ＬＩ Ｓｈｅｎｇｑｕａｎ ，ＬＩＵ Ｙｕｈｏｎｇ （１．Ｃｏｌｌｅｇｅ ｏｆ Ｍｅｔｅｏｒｏｌｏｇｙ ａｎｄ ｏｃｅａｎｏｇｒａｐｈｙ，ＰＬＡ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ ２１１１０１，Ｃｈｉｎａ； ２．Ｎａｖａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｈｙｄｒｏｇｒａｐｈｉｃ Ｓｕｒｖｅｙｉｎｇ ａｎｄ Ｃｈａｒｔｉｎｇ，Ｔｉａｎｊｉｎ ３０００６１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｔｒａｎｓｍｉｓｓｉｏｎ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｓｏｕｎｄ ｃｕｒｖｅｓ ａｒｅ ａｆｆｅｃｔｅｄ ｂｙ ｓｏｕｎｄ ｓｐｅｅｄ ｐｒｏｆｉｌｅｓ，ｓｏ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｓｏｕｎｄ ｃｕｒｖｅｓ’ｔｒａｎｓｍｉｓｓｉｏｎ ｆｅａｔｕｒｅ ｔｈｒｏｕｇｈ ｃｏｎｓｔｒｕｃｔｉｎｇ ａｃｏｕｓｔｉｃ ｍｏｄｅｌｓ ｉｓ ｏｆ ｇｒｅａｔ ｉｎｓｔｒｕｃｔｉｏｎ ｓｉｇｎｉｆｉｃａｎｃｅ ｔｏ ｓｔｕｄｙ ｔｈｅ ｆｅａｔｕｒｅ ｏｆ ｕｎｄｅｒｗａｔｅｒ ａｃｏｕｓｔｉｃ ｔｒａｎｓｍｉｓｓｉｏｎ ｐｒｏｐａｇａｔｉｏｎ ａｎｄ ｓｏｍｅ ａｃｏｕｓｔｉｃ ｐｈｅｎｏｍｅｎｏｎ（ｓｈａｄｏｗ ｚｏｎｅ，ｃｏｎｖｅｒｇｅｎｃｅ ｚｏｎｅ）ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｏｃｅａｎ ｅｎｖｉｒｏｎｍｅｎｔｓ．Ｂａｓｅｄ ｏｎ ｔｈｅ Ｓｎｉｅｒ Ｒｅｆｒａｃｔｉｏｎ Ｔｈｅｏｒｙ，ｔｈｅ ｓｅａ ｗａｔｅｒ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ ｓｅｖｅｒａｌ ｅｑｕａｌ ｐａｒｔｓ ｖｅｒｔｉｃａｌｌｙ，ａｎｄ ｔｈｅ Ｆｏｕｒｉｅｒ Ｓｔｅｐ ｃａｌｃｕｌａｔｉｏｎ ｍｅｔｈｏｄ ｉｓ ｍａｄｅ ｕｓｅ ｏｆ ｔｏ ｃｏｎｓｔｕｃｔ ａｃｏｕｓｔｒｉｃ ｃｕｒｖｅ ｔｒａｎｓｍｉｓｓｉｏｎ ｍｏｄｅ１．ｗｈｉｃｈ ｉｓ ｃｏｎｔｒｏｌｌｅｄ ｂｙ ｓｏｕｎｄ ｓｐｅｅｄ ｐｒｏｆｉｌｅｓ．Ｔｈｅｎ ｔｈｅ ｍｏｄｅｌｉｓ ｕｓｅｄ ｔｏ ｔｈｅ ｅｆｆｅｃｔｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｋｉｎｄｓ ｏｆ ｔｈｅｒｍｏｃｌｉｎｅｓ ｔｏ ｓｏｕｎｄ ｃｕｒｖｅ ｔｒａｎｓｍｉｓｓｉｏｎ ｉｎ ｓｈａｌｌｏｗ—ｗａｔｅｒ．ａｎｄ ｔｈｅ ｃｏｎｃｌｕｓｉｏｎ ｉｓ ｏｂｔｍｎｅｄ ｔｈａｔ ｔｈｅ ｌｅｎｇｔｈ ｏｆ ｗａｖｅ ａｎｄ ｔｒａｃｋ ｏｆ ｓｏｕｎｄ ｃｕｒｖｅｓ ｉｎｃｒｅａｓｅ ｉｎ ｔｈｅ ｏｒｄｅｒ ｏｆ ｎｅｇａｔｉｖｅ ｔｈｅｒｍｏｃｌｉｎｅ，ｎｏｎｅ ｔｈｅｒｍｏｃｌｉｎｅ，ｐｏｓｉｔｉｖｅ ｔｈｅｒｍｏｃｌｉｎｅ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅ ｑｕａｎｔｉｔａｔｉｖｅ ａｎａｌｙｓｉｓ ｏｆ ｅｆｆｅｃｔｓ ｏｆ ｔｈｅｒｍｏｃｌｉｎｅ ｄｅｐｔｈ， ｔｈｅｒｍｏｃｌｉｎｅ ｇｒａｔｉｔｕｄｅ，ｔｈｅｒｍｏｃｌｉｎｅ ｔｈｉｃｋｎｅｓｓ ｉｓ ｍａｄｅ，ａｎｄ ｔｈｅ ｃｏｎｃｌｕｓｉｏｎ ｉｓ ｇｏｔｔｅｎ ｔｈａｔ ｔｈｅ ｗａｖｅｌｅｎｇｔｈ ｂｅｃｏｍｅｓ ｂｉｇｇｅｒ ｗｈｅｎ ｔｈｅ ｎｅｇａｔｉｖｅ ｔｈｅｒｍｏｃｌｉｎｅ ｇｒａｔｉｔｕｄｅ ｏｒ ｔｈｉｃｋｎｅｓｓ ｉｎｃｒｅａｓｅｓ，ｏｒ ｔｈｅ ｄｅｐｔｈ ｄｅｃｒｅａｓｅｓ．Ｔｈｅ ｔｈｒｅｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｐａｒａｍｅｔｅｒｓ ｏｆ ｐｏｓｉｔｉｖｅ ｔｈｅｒｍｏｃｌｉｎｅ ａｆｆｅｃｔ ａｃｏｕｓｔｉｃ ｃｕｒｖｅｓ’ｔｒａｎｓｍｉｓｓｉｏｎ ｏｐｐｏｓｉｔｅｌｙ． Ｋｅｙ ｗｏｒｄｓ：ａｃｏｕｓｔｉｃ ｃｕｒｖｅｓ’ｔｒａｎｓｍｉｓｓｉｏｎ；ｓｏｕｎｄ ｓｐｅｅｄ ｔｈｅｒｍｏｃｌｉｎｅ；ｔｈｅ ｍｏｄｅｌ ｏｆ ａｃｏｕｓｔｉｃ ｃｕｒｖｅｓ’ｔｒａｎｓｍｉｓｓｉｏｎ ◆Ｉｉｉｉ◆ｉｉＩ◆Ｉｉｉｉ◆Ｉｆ◆ｉ◆ｌｌｌ◆ｉ◆Ｉｉｉｉ●ｉｉ ｉ◆ｉｉ◆ｉ ｉｉ◆◆川◆ＩＩ◆ｉ◆Ｉｉｉｉ◆ｉＩ◆ｆｉｉｉ◆ｉｉｌ◆ｌＩｌ◆｛ｉ◆ｉ◆ ◆ＩＩ◆ｉ ｉ◆ｉｉｉ◆ｆｉｉ◆ｉｉｉ◆ｉ ｉｌ◆｝１ｉｉ◆ｉｉｉ◆ｉｉ◆ｉｉｉ◆『ｉｉ◆ｉｉｉ◆ｉｉｉ◆ｌｉｉｉ◆ｉ｛◆Ｉｉｉｉ◆ｉ◆Ｉｉｉｉ◆ｉｉｉ◆ｉ ｉＩ◆ｉｉｉ◆ｉｉ◆ （上接第２０页） Ａｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｑｕｉｃｋ Ｇｅｎｅｒａｔｉｏｎ ｏｆ Ｄｅｌａｕｎａｙ Ｔｒｉｎｇｕｌａａｒ Ｎｅｔ ｆｏｒ Ａｉｒｂｏｒｎｅ ＬｉＤＡＲ Ｐｏｉｎｔ Ｃｌｏｕｄ ＬＵＯ Ｓｈｅｎｇ ，ＷＡＮＧ Ｘｉｎ ，ＳＵＮ Ｙｕｐｉｎｇ （１．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｕｒｖｅｙｉｎｇ ａｎｄ Ｍａｐｐｉｎｇ，Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５００５２，Ｃｈｉｎａ； ２．６１３６３ Ｔｒｏｏｐｓ，Ｘｉ’ａｎ ７１００５４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｉｃｉｅｎｃｙ ａｎｄ ｓｔａｂｉｆｌｉｔｙ ｏｆ ｔｈｅ Ｄｅｌａｕｎａｙ ｔｉａｎｇｕｌａｒｒ ｎｅｔ ｇｅｎｅｒａｔｉｏｎ ｆｏｒ ｔｈｅ ａｉｒｂｏｒｎｅ ＬｉＤＡＲ ｐｏｉｎｔ ｃｌｏｕｄ，ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｉｄｅａ ｏｆ ｄｉｖｉｓｉｏｎ—ｍｅｒｇｅｎｃｅ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｅ ｐａｐｅｒ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｍｐｒｏｖｅｓ ｔｈｅ ｍｅｔｈｏｄ ｏｆ ｂｌｏｃｋ ｄｉｖｉｓｉｏｎ ｂｙ ｃｏｎｎｅｃｔｉｎｇ ｔｈｅ ｃｏｎｖｅｘ ｈｕｌｌ ｐｏｉｎｔｓ ｗｉｔｈ ｔｈｅ ａｒｅａｌ ｃｅｎｔｅｒ ｐｏｉｎｔ，ａｎｄ ｔｈｅ ｂｌｏｃｋ ｉｓ ｆｕｒｔｈｅｒ ｓｕｂｄｉｖｉｄｅｄ ｗｈｅｎ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ＬｉＤＡＲ ｐｏｉｎｔｓ ｉｎ ｔｈｉｓ ｂｌｏｃｋ ｉｓ ｌａｒｇｅｒ ｔｈａｎ ｔｈｅ ｑｕａｎｔｉｔｙ ｔｈｒｅｓｈｏｌｄ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｎｅｅｄｓ ｏｎｌｙ ｏｎｅ ｓｔｅｐ ｏｆ ＬＯＰ ｏｐｔｉｍｉｚｉｎｇ ｔｏ ｍｅｒｇｅ ｔｗｏ ａｄｊａｃｅｎｔ ｂｌｏｃｋｓ ｗｉｔｈｏｕｔ ｃｏｍｐｌｅｘ ａｄｊａｃｅｎｔ ｔｒｉａｎｇｌｅｓ ｓｅａｒｃｈｉｎｇ ｗｈｉｃｈ ｉｓ ｇｅｎｅｒａｌｌｙ ｅｘｉｓｔｅｎｔ ｉｎ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ，ａｎｄ ｔｈｅ ｅｆｉｃｉｆｅｎｃｙ ａｎｄ ｓｔａｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ｂｅｅｎ ｇｒｅａｔｌｙ ｉｍｐｒｏｖｅｄ．Ｔｅｓｔｅｄ ｂｙ ｔｈｅ ｅｘｐｅｒｉｍｅｎｔ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｓｉｍｐｌｅ，ｅｆｉｃｉｅｎｔｆ ａｎｄ ｓｔａｂｌｅ，ａｎｄ ｈａｓ ｏｂｖｉｏｕｓ ａｄｖａｎｔａｇｅｓ ｅｓｐｅｃｉａｌｌｙ ｆｏｒ ｔｈｅ ｌａｒｇｅ ａｍｏｕｎｔ ｏｆ ｄａｔａ ａｉｒｂｏｒｎｅ ＬｉＤＡＲ ｐｏｉｎｔｓ． Ｋｅｙ ｗｏｒｄｓ：ＬｉＤＡＲ；Ｄｅｌａｕｎａｙ ｔｒｉａｎｇｕｌａｒ ｎｅｔ；ｃｏｎｖｅｘ ｈｕｌｌ；ｓｅｌｆ—ａｄａｐｔ ｃｌｕｍｐ ｏｒｇａｎｉｚａｔｉｏｎ；ｌｏｃａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｃｅｄｕｒｅ（ＬＯＰ）
