当前端遇到了自动驾驶

这是一篇用ThreeJS开发自动驾驶点云标注系统的实战记录，也是《THREEJS无师自通》的第一篇。通常情况，一个系列文章开篇应该是Quick Start或者Guide之类的简单口水文，而我选择以此开篇，最主要的原因还是因为这次经历足够有趣。

公众号｜沐洒（ID：musama2018）

前端开发，大家熟啊，有很多亲(bi)切(shi)的称谓，诸如“切图仔”，“Bug路由器”。自动驾驶，大家更熟了吧，最近几年但凡新能源汽车，谁要是不说自己搭配点自动驾驶（或辅助驾驶）功能，都不好意思拿出来卖。那么，当前端和自动驾驶碰到了一起，会发生什么有意思的事呢？

有点云标注相关背景的可以跳过背景普及，直接看方案。

背景   

去年9月，我们业务因为某些原因（商业机密）开始接触自动驾驶领域的数据处理，经过仔细一系列调研和盘算，我们最终决定从零开始，独立自研一套自动驾驶点云数据标注系统。你可能要说了，自动驾驶我知道啊，但是“点云”是个啥？呐，就是这玩意儿：

点云的学术定义比较复杂，大家可以自行搜索学习，这里我简单贴一个引述：
点云是指目标表面特性的海量点集合。
根据激光测量原理得到的点云，包括三维坐标（XYZ）和激光反射强度（Intensity）。 
根据摄影测量原理得到的点云，包括三维坐标（XYZ）和颜色信息（RGB）。
结合激光测量和摄影测量原理得到点云，包括三维坐标（XYZ）、激光反射强度（Intensity）和颜色信息（RGB）。 
在获取物体表面每个采样点的空间坐标后，得到的是一个点的集合，称之为“点云”(Point Cloud)。

看不懂？没事，不重要，你只需要知道，我们周围的世界，都是点构成的，而点云只不过是用一些仪器（比如激光雷达），对真实世界进行了采样（且只对部分属性进行采样）。

好了，假设你已经知道“点云”是啥了，但你心里肯定还有十万个为什么：

你不是说自动驾驶么？前端呢？这仨有啥关联么？这东西自研成本很高么？

别急，容我慢慢解释，先快速普及一下啥叫“数据标注”：

人工智能数据标注是对文本、视频、图像等元数据进行标注的过程，标记好的数据将用于训练机器学习的模型。常见的数据标注类型有文本标注、语义分割和图像视频标注。

这些经标注的训练数据集可用于训练自动驾驶、聊天机器人、翻译系统、智能客服和搜索引擎等人工智能应用场景之中

假设你懒得看，或者看不懂，我再给你翻译翻译，什么叫数据标注：

一个婴儿来到这个世界，你在它面前放两张卡片，一张红色，一张绿色，你问它，这是什么颜色，它必然是不知道的（我们假设它能听懂并理解你的话）。只有当你一遍又一遍的，不断的告诉它，这是红色，这是绿色，它才会记住。等下次你带它过马路时，它就能准确地识别出红绿灯，并在你面前大声喊出来 “红色（的灯）！”没错，你应该猜到了，那两张卡片本身没有标签（元数据），是你给它们“打上了标”（分别标注了红色和绿色），然后把这个“结构化的数据”，“喂养”给你的宝宝，久而久之，这个宝宝就学会了分辨世间万物，成为一个“智人”。

（图片来源于网络）

你的“喂养”，就是人工；宝宝的成长，就是智能。人工智能（AI，Artificial Intelligence），就是数据喂养的成果，没有数据标注，就没有人工智能。

从这个意义上聊，你和我，都是别人（父母，老师，朋友…）用成千上万的标注数据喂养出来的AI。

扯远了，收！我们说回自动驾驶。

大家都知道现在自动驾驶很火啊，那自动驾驶的“智能”是怎么训练的呢？当然是算法工程师用模型训练出来的啦，而自动驾驶模型需要喂养的数据，就是点云。仪器扫描回来的点云数据里，仅仅只是包含了所有点的基本信息（位置，颜色，激光强度等），模型怎么知道这个点是人身上采的，还是出租车上采的呢？!

（图片来源于网络）

于是这些点就需要被加工（标注），被我们用一系列手段（包括人工和机器）给点赋予更多的信息，区分出每一个点的含义（语义分割）。在自动驾驶领域的点云标注里，我们需要通过2D+3D工具，把物体识别出来。本文重点讲3D的部分。可以先看下3D框的效果：

（图中黄色高亮的点，就是被3D框圈中的点云）

挑战   

以往我们较为常见的数据标注，主要集中在文本，图片，视频等类型，例如文本翻译，音频转写，图片分类等等，涉及的工具基本上都是传统web开发知识可以搞定的，而点云标注则完全不同，点云需要作为3D数据渲染到立体空间内，这就需要使用到3D渲染引擎。我们使用的是ThreeJS，这是一个基于WebGL封装的3D引擎。

写了10年的web前端代码，能有机会把玩一下3D技术，还真是挺令人兴奋的。于是我们吭哧吭哧把基本的3D拉框功能做出来了，效果是这样的：

（3D拉框 - 人工调整边缘：2倍速录制）

动图是我加了2倍速的效果，真实情况是，要标出图上这辆小汽车，我需要先拉出一个大概的2D矩形区域，然后在三视图上不断的人工调整边缘细节，确保把应该纳入的点都框进去（未框入的点呈白色，框体垂直方向未框入则呈现蓝色，框入的呈现黄色）

看起来好像也还行？

no，no，no！你知道一份完整的点云标注任务需要标多少个框么？也不吓唬大家，保守点，一般情况一份连续帧平均20帧左右，每帧里要标注的框体保守点，取100个吧，而这一份连续帧标注，必须同一个标注员完成，那么20帧至少有2000个框体需要标注！

按照上面实现的这种人工调节边缘的方式来拉框，一个框需要22秒（GIF共11秒，2倍速），熟练工可能能在10秒内调整完成。那么2000个框体，单纯只是拉框这一件小事，不包括其他工序（打标等），就需要耗费20000秒，约等于5.5小时！

这是什么概念？通常情况标注员都是坐班制，平均一天有效工作时长不超过6小时，也就是说，一个标注员，在工位上一动不动，大气都不敢喘一下的工作一天，就只能把一条点云数据标完，哦不对，仅仅只是拉完框！没错，只是拉框而已。

这种低效的重复性工作，哪个组织受得了？怎么办呢？

方法比较容易想，不就是引入自动化能力么，实现自动边缘检测，嗯，想想倒是挺简单的，问题是怎么实现呢？

以下进入干货区，友情提示：货很干，注意补水。

方案

点云分类

基本思路就是进行边缘探测：

找出三个坐标轴(XYZ)方向上的框体边缘点，计算出边缘点之间的距离，调整框体的长宽高，进而将框体贴合到边缘点。

边缘的定义：

某方向上的同值坐标点数大于某个设定值（可配置，默认3，三者为众）

找出边缘点的核心算法：

遍历框体内的点，分别将XYZ方向的坐标值存入数组，加权，排序，取第一个满足边缘定义的点，作为该方向极限值。

进行边缘判定之前，我们得先找出存在于框体内的点，这就涉及到第一个核心问题：点云和3D框的相对位置判断。

为了更好的管理与框体“强相关”的点云，我们先对点云进行一个基本分类：

从俯视图看，把3D图降维成2D图，立方体则看作矩形，如下图：

则点与框的相对位置可以降维等效为：

第一类（点在立方体内）

点在矩形内，且点的Z值在立方体[Zmin, Zmax]范围内

第二类（点在立方体垂直方向）

点在矩形内，且Z值在立方体[Zmin, Zmax]范围外

第三类（点在立方体周围）

点在延展矩形（向外延展N个距离）内，且不属于第二类。

我们先按这个思路实现一版代码：

// 判断点是否位于框体XY平面区域内
function isPointInXYPlane(gap: IGap, distance = 0) {
const { gapL, gapR, gapB, gapU } = gap;
// 在框体XY平面区域内
return gapL > - distance && gapR < distance && gapU < distance && gapB > - distance;

}
// 在框体垂直方向上下边界内
function isPointInVerticalBoundry(up: number, bottom: number, z: number) {
return z >= bottom && z <= up;

}

// 位于框体XY平面向外延伸NEAR_DISTANCE距离的区域内
if (isPointInXYPlane(posInfo.gap, NEAR_DISTANCE)) {
const isInVerticalBoundry = isPointInVerticalBoundry(posInfo.up, posInfo.bottom, posInfo.z);
// 位于框体XY平面区域内
if (isPointInXYPlane(posInfo.gap)) {
// 在框体内
if (isInVerticalBoundry) {

      isInside = true;

    } else {
// 在框体外的垂直方向上

      isVertical = true;

    }

  }
// 在框体上下边界内
if (isInVerticalBoundry) {

    isNearBy = true;

  }

}

通过以上逻辑，我们就拿到了与框体“相关”的点云（正确与否先按下不表，后面会说），我们先存起来，后面做极值寻找（即边缘检测）时候使用。

第一版效果

看起来好像还行，基本实现了贴合，但是……我们旋转一下看看：

好家伙，旋转后框体边界没更新！所以点云高亮也没变化。

这个问题其实也好理解，我们在处理边界的时候，只采用position和scale计算，并没有使用rotation属性，所以当框体的旋转分量发生变化，我们计算边界时没有及时调整，程序就会认为框体此时仍然留在原地未动呢。

我们来优化一下。我先尝试用三角函数来计算旋转后的新坐标点，类似这样

折腾了很久的三角函数，有点变化了，但是效果却成了这样：

已经接近真相了，只需要把待判定点放到三角函数判定公式里，就可以知道该点是否在旋转后的框体内了，不过到这里我突然意识到问题被我搞复杂了，是不是可以有更简单的方法来判定矩形内部点呢？

我们回到最初的问题：判断一个点，与一个立方体的相对位置

对这个原始问题进行逻辑拆解，可以拆为3个子问题：

关于问题1，第一反应还是立体几何，而且我笃定这是个非常成熟的几何问题，没必要自己硬憋。于是我就上网搜索：How to determine a point is inside or outside a cube? 结果如下：

上面是stackoverflow上大神给的两种数学方法，一看就知道能解，奈何我看图是看懂了，公式没有完全吸收透，于是最终没有采纳（尽量不干不求甚解的事，写成代码就要求自己得是真的懂）

于是我进一步思考：

几种数学方法确实都很虎，但我是不是把问题搞复杂了？能不能没事踩踩别人的肩膀呢？

看看ThreeJS 是否有相应的API……果然有：

这不正好就是我想要的效果么？踏破铁鞋无觅处，得来全不费功夫啊！

直接拿来用，搞定！

但问题来了，人家是怎么做到的呢？带着这个疑问，我开始翻相关源码。

首先看到containsPoint，其实就和我们用的方法是一样的：

// 
containsPoint( point ) {
return point.x < this.min.x || point.x > this.max.x ||

    point.y < this.min.y || point.y > this.max.y ||

    point.z < this.min.z || point.z > this.max.z ? false : true;

}

而核心问题还是得想办法计算出box.min和box.max，那ThreeJS是怎么计算的呢？继续看：

// 
computeBoundingBox() {
// ..... 省略部分代码 ....
const position = this.attributes.position;
if ( position !== undefined ) {
this.boundingBox.setFromBufferAttribute(position);

  }
// ..... 省略部分代码 ....

}

看起来boundingBox的属性来自于attributes.position，这个position就是box在世界坐标里的具体位置，是我们在创建box时候设定的。再继续深挖下setFromBufferAttribute：

// 
setFromBufferAttribute( attribute ) {
// ..... 省略部分代码 ....
for ( let i = 0, l = attribute.count; i < l; i ++ ) {
const x = attribute.getX( i );
const y = attribute.getY( i );
const z = attribute.getZ( i );
if ( x < minX ) minX = x;
if ( y < minY ) minY = y;
if ( z < minZ ) minZ = z;
if ( x > maxX ) maxX = x;
if ( y > maxY ) maxY = y;
if ( z > maxZ ) maxZ = z;

  }
this.min.set( minX, minY, minZ );
this.max.set( maxX, maxY, maxZ );
return this;

}

平平无奇啊这代码，几乎和我们自己写的边界判定代码一模一样啊，也没引入rotation变量，那到底怎么是在哪处理的旋转分量呢？

关键点在这里：

我尝试给你解释下：

在调用containsPoint之前，我们使用box的转换矩阵，对point使用了一次矩阵逆变换，从而把point的坐标系转换到了box的坐标系，而这个转换矩阵，是一个Matrix4（四维矩阵），而point是一个Vector3（三维向量）。
使用四维矩阵对三维向量进行转换的时候，会逐一提取出矩阵的position（位置），scale（缩放）和rotation（旋转）分量，分别对三维向量做矩阵乘法。
也就是这么一个操作，使得该point在经过矩阵变换之后，其position已经是一个附加了rotation分量的新的坐标值了，然后就可以直接拿来和box的8个顶点的position做简单的边界比对了。

这里涉及大量的数学知识和ThreeJS底层知识，就不展开讲了，后面找机会单独写一篇关于转换矩阵的。

我们接着看点与框体相对位置判断的第二个问题：如何判断一个点位于立方体的垂直方向（排除体内点）？

首先，我们置换下概念：

垂直方向上的点 = Z轴方向上的点 = 从俯视图看，在XY平面上投射的点 - 框内点

那么，如何判断一个点在一个矩形内，这个问题就进一步转化为：

(AB X AE ) * (CD X CE) >= 0 && (DA X DE ) * (BC X BE) >= 0

这里涉及到的数学知识是向量点乘和叉乘的几何意义，也不展开了，感兴趣的朋友可以自行搜索学习下。

还剩最后一个问题：如何判断一个点位于立方体的周围（排除垂直方向点）？

这个问题我们先放一放，周围点判断主要用来扩展框体的，并不影响本次的边界探测结果，以后再找机会展开讲，这里先跳过了。

到此为止，我们就至少拿到了两类点（框内点，和框体垂直方向的点），接下来就可以开始探测边缘了。

边缘探测   

边缘探测的核心逻辑其实也不复杂，就是：

遍历框体内的点，分别将X，Y，Z方向的坐标值存入数组，加权，排序，取第一个满足边缘定义的点，作为该方向极限值。

这里我们可以拆分位两个Step。

Step 1：点位排序

基本思路如下：

选择一个方向，遍历点云，取到该方向上点云的坐标值，放入一个map中，key为坐标值，value为出现次数。同时对该坐标进行排序，并返回有序数组。**

那么问题来了，点云的坐标值多半精确到小数点七八位，如果直接以原值作为key，那么这个map很难命中重复坐标，那map的意义就不大了，难以聚合坐标。

于是这里对原坐标取2个精度后作为key来聚合点云，效果如下：

可以明显看到已经有聚合了。这是源码实现：

Step 2：夹逼探测

拿到了点云坐标的聚合map，和排序数组，那么现在要检测边缘就很简单了，基本思路就是：

从排序数组的两头开始检查，只要该点的聚合度大于DENSE_COUNT（根据需要设置，默认为3），我们就认为这个点是一个相对可信的边缘点。

从这个算法描述来看，这不就是个夹逼算法么，可以一次遍历就拿到两个极值。

到这里，某方向的两个极值（low 和 high）就拿到手了，那么剩下的工作无非就是分别计算XYZ三个方向的极值就好了。

我们来看下效果，真的是“啪”一下，就贴上去了：

上面的案例录制的比较早，有点模糊，再来看个高清带色彩的版本：

这个体验是不是很丝滑？就这效率，拉框速度提升了10倍有吧？（22秒 -> 2秒）

读到这里，不知道大家还记不记得前面，我们刻意跳过了一个环节的介绍，就是“框体周围点位”这一部分，这里简单补充两句吧。

在实际的场景里，有很多物体是靠得很近的，还有很多物体的点云并没有那么整齐，会有一些离散点在物体周围。那么这些点就可能会影响到你的边缘极限值的判断。

因此我在这里引入了两个常量：

附近点判定距离 NEAR_DISTANCE（框体紧凑的场景，NEAR_DISTANCE就小一点，否则就大一点）!

密集点数 DENSE_COUNT（点云稀少的场景，就可以把DENSE_COUNT设置小一点，而点云密集厚重的场景，DENSE_COUNT就适当增加。）

通过在不同的场景下，调整这两个常量的取值，就可以使得边缘探测更加的准确。

遗留问题   

其实在3D的世界里，多一个维度之后，很多问题都会变得更加的麻烦起来。上面的方案，在处理大部分场景的时候都能work，但实际上依然有一些小众场景下存在问题，比如：

平时多半都是物体都是围绕Z轴旋转，但如果有上下坡路，物体围绕XY轴旋转，那垂直方向就需要进行矫正。

再比如：

用户移动了镜头方位，在屏幕上拉2D框的时候，就需要对2D框采集到的坐标进行3D投射，拿到真实的世界坐标，才能创建合适的立方体。

当然，这些问题在后面的版本都已经完善修复了，之所以放在遗留问题，是想说明，仅仅依照正文部分的方法去实现的话，还会有这些个遗留的问题需要单独处理。

如果大家感兴趣的话可以留言告诉我，我再决定要不要接着写。