近日，智行者高翔博士带领的定位团队撰写的论文《Faster－LIO： Lightweight Tightly Coupled Lidar－inertial Odometry using Parallel Sparse Incremental Voxels》被国际公认的自动驾驶领域TOP级期刊IEEE Robotics and Automation Letters收录刊登。

该论文主要对激光雷达算法进行了深入探讨，智行者提出了一种基于iVox（incremental voxels）的算法，以快速跟踪旋转的激光雷达－惯性里程计（LIO）方法固态激光雷达扫描。在该算法中，智行者定位团队使用iVox作为点云空间数据结构，即从传统的体素修改，支持增量插入和并行近似k－NN查询。该算法可以有效的降低点云配准时的耗时，也不会影响LIO的精度表现。

高翔博士认为，目前行业内已有的开源的LIO大部分只能在自己的数据集上跑，换一个数据集就很容易出现问题。虽然近期的方案稳定性有了一定程度的提升，但依然没有纯Lidar方案那么稳定，各种指标也有一定的提升空间。

据了解，本论文中提及的Faster－LIO是基于FastLIO2开发的。FastLIO2是开源LIO中较为优秀的代表，其前端使用了增量的kdtree（ikd－tree），后端使用了迭代ESKF（IEKF），具有流程短、计算快等优势特点。Faster－LIO则把ikd－tree替换为iVox，同时优化了一些代码逻辑，实现了更快的LIO。

众所周知，kd树类结构的优势在于可以严格地查询K近邻，也可以以范围或盒子形式来查询最近邻（range search／box search），查询过程中可以设置最大距离等限制条件，实现快速的近似最近邻查找（Aproximate Nearest Neighbor， ANN）。然而传统的Kd树是不带增量结构的。像ikd－tree这种带增量加点的结构，虽然不用完全重新构建，但也需要花额外的时间去维护这个树的结构。

FasterLIO使用了一种基于稀疏体素的近邻结构iVox（incremental voxels）。高翔博士表示：“我们会发现这种结构用来做LIO更加合适，可以有效的降低点云配准时的耗时，也不会影响LIO的精度表现。我们使用两个版本的iVox：一种是线性的，一种是基于空间填充曲线的（伪希尔伯特空间曲线，pseudo－Hilbert curve， PHC）。”

对于此全新的基于ivox激光雷达算法，智行者定位团队进行了详尽的仿真实验和数据集实验。其中，仿真实验是在一个随机生成的点云里进行K近邻查找以及新增地图点的实验，对比了Kdtree flann， ikd－tree， nanoflann R－tree， faiss－IVF， nmslib几个库。智行者定位团队发现iVox在K近邻查找和新增的耗时都很少，但它们随地图点数的增长会更快。

同时，团队对iVox的K近邻质量问题也进行了比较，发现大部分时候由于天然的有范围限制iVox的K近邻是不严格的。我们把K近邻的结果与暴力搜索的结果进行比对，可以得到它的召回率（recall）。如果要求iVox有很高的召回，那就不得不设置很大的体素尺寸或者很大的搜索近邻，这时候iVox的查找时间会增长很快，不过LIO系统在70％左右的召回率下就能很好地工作。

数据集实验则主要比较整个LIO系统的耗时和计算精度。以框架基本相同的FastLIO2为主要对标。实验发现，主要的耗时在IEKF＋ICP的迭代过程，iVox替代iKd－tree时，这个过程明显缩短。UTBM数据集要明显一些，我们可以把差不多20ms的IEKF迭代降到5－8ms左右，整个流程可以从30ms左右降到10ms左右，实现明显的效率提升。

上述实验均表明，在同等精度指标下可以明显提升LIO计算速度，这为基于ivox的全新激光雷达算法提供了可靠的数据支撑。同时，这一算法的提出也将成为激光雷达技术发展提供更多可能。