倒排索引优化的波形激光雷达数据存储和访问

卢 昊，庞 勇，李增元

LU Hao,PANG Yong,LI Zengyuan

中国林业科学研究院 资源信息研究所，北京100091

Institute of Forest Resources Information Techniques,Chinese Academy of Forestry,Beijing 100091,China

1 引言

激光雷达（LiDAR）技术是目前国际上发展迅速的一种主动遥感手段，具有直接快速获取地表三维信息的特点[1]。全波形激光雷达通过记录激光脉冲的完整回波，提供了更丰富的地物信息[2]。为了实现不同软硬件平台之间的数据交换，美国摄影测量与遥感协会设计发布了LAS 格式规范作为通用的激光数据存储格式，其中LAS1.0 至LAS1.2 仅仅支持点云信息存储，LAS1.3 开始增加了对波形数据的支持。Andre Samberg 在2007 年ISPRS 会议上解析并比较了多种版本的LAS 文件格式，张婧等（2008）进行了LAS 格式的解析并分析了其扩展域的应用[3]，赵自明（2010）等提出了采用内存映射技术对点云数据进行快速读取和显示的方法[4]，秦楠楠等（2013）对LAS1.3 文件格式进行了解析并提出了读取波形数据的方法，总结了快速读取波形数据的高效方法[5]。但LAS1.3 格式的主要关注点仍然是点数据的表达，波形信息只是作为一种额外的扩展字段附加在原始的点文件中。要访问波形数据，只能通过从点到波形的映射关系。对于全波形激光雷达来说，波形数据包含了激光脉冲回波的全部信息，回波点仅仅是其中的一个信息子集，从信息获取的角度讲，这种逻辑关系与原始信息流相反，并且带来了一些其他问题（见3.1 节）。波形数据的处理主要有波形分解和反卷积等，要求直接访问波形采样序列，而LAS1.3 格式并不支持此种访问方式。

倒排索引（Inverted index），也常被称为倒排索引、置入档案或倒排档案[6]，是一种常用于关系型数据库和搜索引擎检索算法的索引方法，可以用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构，源于实际应用中需要根据属性值来查找记录。倒排序索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。在这种索引方式下，不是由记录来确定属性值，而是由属性值来确定记录的位置。王智强等（2005）利用倒排索引实现了一种实时更新的索引结构[6]，用于实现搜索引擎对网页数据库的快速检索和实时更新。邓攀等（2008）提出一种高效的倒排索引结构[7]，设计了一种优化的倒排索引结构，充分考虑索引表的压缩和对磁盘IO 的降低以支持大规模的网络信息检索。郑榕增等（2010）利用Lucene 实现了中文倒排索引技术[8]，基于开源的全文检索引擎工具包Lucene 实现了对中文文档的高效分词和索引，较好地改进了搜索引擎对中文字符编码的支持。董长春（2011）基于Hadoop 进行了倒排索引技术的研究[9]，在Hadoop 集群上实现了多层次倒排索引结构，在减少了集群节点间通信代价的基础上进行大量信息的查询。可以看出，倒排索引是互联网与信息系统中的一种感觉常用技术，主要被应用于网络搜索引擎与文档处理系统，而尚未被应用于海量遥感数据处理。事实上，在全波形激光雷达大量数据的研究与后处理过程中，对于LAS1.3 格式中存在的只能从点云通过多对一映射访问波形而不能进行快速反向检索（详见3.1）的问题，利用倒排索引可以很好地解决。

2 波形数据的常规访问

根据LAS1.3 格式规范[10]可知，作为对较低版本格式的改进，它将波形数据作为一个扩展变长记录（EXTENDED VARIABLE LENGTH RECORD）字段挂接在点云文件末尾或独立同名文件中，一个包含了波形数据的LAS1.3 文件结构如图1 所示。

从图1 以及文献[10]看出，在旧版本的基础上，LAS1.3 格式有了如下改变：

（1）文件头部分结构基本不变，在文件头末尾增加了波形数据包记录起始位置（Start of Waveform Data Packet Record）字段，表示从文件开始到波形扩展变长记录区的偏移量。

（2）变长记录区中有一个变长记录为波形包描述符用户定义记录，其扩展域中有1～255 个描述符，其格式如表1 所示，每一个记录表示一种波形包量化方式。

表1 波形包描述符字段格式

也就是说，一个LAS1.3 文件中的波形，从量化比特数、采样数和采样间隔等信息来看，最多只能有255 种不同情况，超过255 种则无法完全表示。实际应用中，由于设备在使用时并没有修改其记录方式，所以一般只有1 个记录，这样对于数据读写比较方便。

（3）对于包含波形数据的LAS 文件，点格式必须是FORMAT4 或FORMAT5，这时点记录中增加了几个字段用于关联和表达波形信息，以FORMAT4 为例，其中与波形相关的属性如表2 所示。

其中，Wave Packet Descriptor Index 为0 代表该点不存在波形，1～255 则表示该点存在波形，且描述该波形的量化参数保存在前面变长记录字段的1～255 里对应的位置。Byte offset to waveform data 表示该点所属的激光脉冲回波波形数据从evlr 字段开始到其第一个采样的字节偏移量。

图1 带波形的LAS1.3 文件结构

表2 LAS1.3 格式FORMAT4 点记录字段

综上所述，LAS1.3 文件中波形的访问方式可以概况为：

（1）读入公共文件头及相关参数。

（2）遍历可变长度记录：逐一判断每个可变长度记录头部，若为波形包描述符用户定义记录，则获取波形包描述符用户定义记录个数，并全部读入数组。每个记录的长度固定为26 字节。

（3）遍历读取每个点记录，判断是否存在波形。如存在，则首先根据波形包描述符索引（Wave Packet Descriptor Index）获取描述符数组中对应元素，然后根据描述符中信息访问波形数据字段。此时，内存中存在（a）该点数据；（b）波形描述数据；（c）波形采样数据，根据这些信息可以进行对该波形的算法处理。

步骤（3）中之所以会出现不存在波形的情况，是由于某些激光雷达系统受到硬件存储速度的限制，工作时会以一定的采样比例对点云进行波形记录，导致部分点云并不关联其对应激光脉冲的波形。如Leica ALS 60系统对脉冲回波以1∶1 的比例对点云进行波形采集和丢弃，使文件中一半的点云不存在相应脉冲回波记录，这一现象源于硬件技术的限制，不利于全波形数据的研究与应用。而在具备真正全波形记录能力的系统中，脉冲回波将被全部记录。如Riegl LMS Q680 系统[11]可以对脉冲的全部有效回波信号进行记录，其后处理软件根据波形信息进行点云解算，故该系统获取的点云数据中全部的点都会关联其对应激光脉冲信号而无一遗漏。LAS1.3 格式通过这种可选的存储方式可以兼容不同的硬件设备所采集的点云和波形数据。

3 倒排索引文件格式

3.1 LAS1.3 格式存储波形数据的缺陷

按照LAS1.3 格式定义，波形数据的存储和访问存在的问题包括：一、允许存在的波形量化参数组合是有限的，所以不能存储任意个数任意长度的波形。二、波形往往不是完整的，只是对部分有效信号进行记录。三、存储的方式是从点到波形的多对一映射，故只能从点到波形访问，多对一的情况下存在重复访问，在波形分解等算法中这是不被允许的。四、访问一个波形时，由于原文件不存在相应的映射关系，因此并不知道哪些点记录由该波形得到。一般而言，虽然同属于一个波形的点记录前后相邻，但无法保证点数据读取的准确和无遗漏。在常规的访问方式下，如果需要随机访问指定回波波形数据关联的点云数据，会引入大量的查找计算和磁盘IO，显著降低索引访问的速度。

3.2 构建倒排索引

针对这些问题，本文设计了一种简化访问的索引文件格式，目的是为了建立从波形到点的一对多映射关系，同时简化波形的访问，便于进行波形分解与系统生成点记录的比对。

首先将原始LAS1.3 文件进行分割，将除最后一个波形扩展变长记录（evlr）字段之外的其余部分视为点文件（*.pts），将原始文件中波形包描述符用户定义记录与末尾的波形扩展变长记录（evlr）字段放在一起，构成波形数据包文件（*.wdp），然后创建索引文件，实现从波形到点的映射，具体操作是：

（1）计算出波形条数N，原始文件中并没有给出，需要根据总波形长度与波形字节长度求出。

（2）创建索引数组，类型为8 字节无符号整型（保证足够访问大文件）。假定每个波形最多有5 次回波，每条波形对应一个5 元数组，数组对应位置存储pts 文件中从文件开始到某个点记录的偏移量。若该数组中某个元素（偏移量）为0 则代表波形没有该次回波。

（3）在原始LAS 文件中读取一个点记录，如果某点无波形则跳过；如果有波形，根据点记录中相应字段计算出波形包在evlr 中的位置(0，1，2，…，N-1)，该索引为idx。索引数组中下标为idx的元素即为该点对应的波形，若idx＜0 或idx＞N-1，属于数据异常，实际中存在数据错误的点记录会导致该情况。在这5 元数组中，将该点在pts 文件中从文件开始计算的偏移量填入第一个不为0 的位置。若5 个位置都已存在数据，说明原始文件中存在5 次以上回波的波形，属于异常。

（4）重复（3）步骤直到遍历完所有的点，得到最终的索引数组，写入索引文件（*.idx）。

三种文件的格式及访问逻辑关系如图2 所示。

图2 倒排索引文件结构

3.3 基于倒排索引的波形数据访问

经过分割和创建索引处理，原始点云和波形信息全部进入了新生成的文件，根据索引文件即可逐个访问波形记录并获取从该脉冲获取的点云数据。访问方式如下所示：

（1）读取idx 文件头部无符号长整型4 个字节，为波形个数。

（2）读取idx 文件中一个波形的索引记录，每个记录包含5 个8 字节无符号整型数据，共40 个字节。

（3）根据该索引记录的位置，计算对应波形在wdp文件中的位置，读取该波形数据包，长度为128 字节，每个采样1 字节（不同激光雷达设备量化方式可能不同）。

（4）遍历该波形的5 个索引记录数值，直到最后一个不为0 的位置，根据该文件偏移量读取pts 文件中的对应点记录，正常情况下数量为1～5。

（5）重复（2）直到结束。

4 实验结果

本文在Visual Studio 2010 环境下以C++语言实现了LAS1.3 文件的数据索引构建与波形数据访问，以Leica ALS 60 机载激光雷达[12]获取的带有波形数据的LAS1.3 文件为实验对象[13]。从实验结果看，基于倒排索引的格式与LAS1.3 格式在波形数据访问特性对比如表3 所示。其中，前三项反映出倒排索引文件可以完整保留原始LAS1.3 文件的属性而不造成信息丢失。由于倒排索引文件保留了原始点云数据的序列存储特征，所以仍然可以进行顺序访问，而由于点云信息的定长特征，所以能够通过序号计算偏移量定位任意点记录以实现随机访问。在LAS1.3 文件中，由于波形的起始位置只能通过某一点记录的属性进行索引定位，所以无法对波形直接进行遍历访问，不能支持顺序或随机访问。而在倒排索引文件中，全部波形的位置信息都以全局偏移量的形式保存在倒排索引文件中，且倒排索引文件采用了定长字段的设计，故同时支持波形数据的顺序和随机访问。倒排索引文件同时还保留了LAS1.3 文件内部的正排索引信息，故仍可以随机访问指定点记录的波形。由于采用了倒排索引结构，由指定激光脉冲所获取的点云记录，可以通过波形索引直接定位，这一特性在原始LAS1.3 中是无法实现的，若进行全局搜索则会带来巨大的磁盘IO 和计算代价。此外，对于点到波形的多对一映射，倒排索引有效地消除了波形重复访问的弊端，而随机访问特性保证了倒排索引较快的遍历速度。

从表3 可以看出，本文实现的索引文件组不仅保留了LAS1.3 格式包含的所有属性和结构特征，还增加了一些新的特性，有利于对波形数据和点云数据结合展开处理算法[14]。读取索引文件组的波形数据并获取关联的点云实例显示如图3 所示。波形数据遍历速度根据应用程序循环访问波形记录的磁盘IO 速率定量表征，一般用record/s 或MB/s 表示。表4 显示了针对一组测试数据进行的两种访问速度统计。从表中可以看出，对于不同测量环境下生成的激光雷达数据，通过倒排索引方式均能一定程度地加快波形数据寻址访问速度。从平均速率可以看出，常规访问方式下的速率表现出文件相关的特征，这是由于不同探测目标对于激光脉冲回波次数分布有差别，导致多脉冲回波造成的冗余访问各不相同所致。而在倒排索引访问方式下由于冗余访问得到了消除，所以总体速率几乎不受不同文件的影响趋于接近，其寻址速度主要由磁盘IO 性能决定。

表3 两种文件格式的特征比较

图3 倒排索引文件访问波形及激光点云数据

表4 波形数据遍历速度量化实验结果

图3 中，黑色曲线为一束激光脉冲的回波波形，红色点为原始点云文件中由该脉冲回波获取的激光点云位置及振幅，通过直接获取点云数据，可以快速进行波形与系统点云结合的算法处理[15]。可以看出，该束激光脉冲获取了2 次反射回波，其位置由红色点表示。这两次回波信息可以从倒排文件中通过点记录直接获取。而在原始LAS1.3 文件中，无法得知这两个点记录与该波形记录的关系，只能在访问一个点记录时访问到该波形，故这种情况下同一波形记录将被重复访问2 次。

5 结论

本文通过对LAS1.3 格式的波形和点云数据进行倒排索引存储，实现了波形数据的直接快速访问，对波形数据处理是一种比较理想的转换格式。索引文件组既可以单独作为点云数据载体，也可以单独作为波形数据载体，或者作为波形与点云数据结合处理算法的载体，保持了激光脉冲回波与相应回波点云的逻辑关系，具有很好的灵活性，一定程度上消除了LAS1.3 格式规范中对波形数据支持的缺陷。但由于LAS1.3 格式并没有严格限定波形采样量化的方式，波形包的结构与实际回波情况相关，难以用一种固定的形式进行描述。索引文件结构的设计也无法很好地解决波形长度、量化比特数不一致的问题，这将成为后续研究的重点。但总体而言，本文设计的倒排索引结构体现了波形数据与激光点云的内在逻辑关系，可以作为一种激光雷达波形数据通用交换格式的设计思想。

[1] Wagner W.Gaussian decomposition and calibration of a novel small-footprint full-waveform digitising airborne laser scanner[J].ISPRS Journal of Photogrammetry & Remote Sensing，2006，60：100-112.

[2] 李奇，马洪超.基于激光雷达波形数据的点云生产[J].测绘学报，2008，37（3）：349-354.

[3] 张靖，高伟.LAS 格式解析及其扩展域的应用[J].测绘科学，2008，33（3）：154-155.

[4] 赵自明，史兵，田喜平，等.LAS 格式解析及其数据的读取与显示[J].测绘技术装备，2010：17-20.

[5] 秦楠楠，赖旭东.机载LiDAR波形数据快速读取方法研究[C]//第一届全国高分辨率遥感数据处理与应用研讨会，西安，2011：236-240.

[6] 王智强，刘建毅.一种实时更新索引结构的设计与实现[J].计算机系统与应用，2005，41（10）：79-82.

[7] 邓攀，刘功申.一种高效的倒排索引存储结构[J].计算机工程与应用，2008，44（31）：149-152.

[8] 郑榕增，林世平.基于Lucene的中文倒排索引技术的研究[J].计算机技术与发展，2010，20（3）：80-83.

[9] 董长春.基于Hadoop 的倒排索引技术的研究[D]沈阳：辽宁大学，2011.

[10] ASPRS.Las Specification Version 1.3 Spe[S].USA：ASPRS，2010.

[11] IGI GmbH.LiteMapper 6800 User Manual[S].Germany：IGI GmbH，2010.

[12] Leica Geosystems.Leica ALS60 Airborne Laser Scanner Product Specifications[S].Switzerland：Leica Geosystems，2008

[13] Lu H.Quantitative comparison between full waveform decomposition and discrete returns point clouds data from Small-footprint Airborne LiDAR[C]//13th International Conference on LiDAR Applications for Assessing Forest Ecosystems（SilviLaser2013），Beijing，China，2013：63-70.

[14] Pang Y.LiCHY：CAF’s LiDAR，CCD and Hyperspectral Airborne Imager[C]//13th International Conference on LiDAR Applications for Assessing Forest Ecosystems（SilviLaser2013），Beijing，China，2013：45-54.

[15] Isenburg M.PulseWaves-full waveform LiDAR specification（Version 0.3 Revision 8）[Z].Germany：rapidlasso GmbH，2011.