2019 杭州云栖大会上, 高德地图技术团队向与会者分享了包括视觉与机器智能, 路线规划, 场景化 / 精细化定位时空数据应用, 亿级流量架构演进等多个出行技术领域的热门话题. 现场火爆, 听众反响强烈. 我们把其中的优秀演讲内容整理成文并陆续发布出来, 本文为其中一篇.
阿里巴巴高级地图技术专家方兴在高德技术专场做了题为《向场景化, 精细化演进的定位技术》的演讲, 主要分享了高德在提升定位精度方面的探索和实践, 本文根据现场内容整理而成 (在不影响原意的情况下对文字略作编辑), 更多定位技术的实现细节请关注后续系列文章.
以下为方兴演讲内容的简版实录:
今天要分享的主题是关于定位的场景化, 精细化. 高德定位, 并不只是服务于高德地图本身, 而是面向所有的应用开发者和手机设备厂商提供定位服务. 目前已有 30 万以上的 App 在使用高德的定位服务.
用户每天会大量使用定位服务, 比如看新闻, 打车, 订外卖, 甚至是购物, 首先都是要获得位置信息, 有了更精准的位置信息, 才可能获得更好的服务体验.
高德地图有超过 1 亿的日活用户, 但是使用定位的有好几个亿, 每天的定位请求数量有一千亿次. 如此大的数据量, 高德定位服务可以保持毫秒级的响应速度, 我们在这里面做了很多工作. 此外, 我们还提供全场景的定位能力, 不管为手机, 车机还是任何厂家, 都能提供位置服务.
我今天从四个方面介绍, 分别是:
定位面临的挑战
高德地图全场景定位
分场景提升定位精度
未来机遇
定位面临的挑战
大家可能都知道 GPS,GPS 在大部分情况下可以提供很好的精度, 但是对于某些场景还是不够, 比如驾车, GPS 给出的精度大概是 10 米, 如果仅靠 GPS 定位甚至无法区分出在马路的哪一侧.
第二个场景是在室内, 室内收不到 GPS 信号, 这样的场景下如何实现比较准确的定位? 第三个场景是如何在精度和成本之间取得平衡, 因为不可能为了追求一个很好的精度去无限投入成本. 只有通过海量大数据挖掘, 算法和数据质量的提升, 达到效果的持续优化, 才能达到最终对各种场景的全覆盖.
有很多技术可以选择, 除了 GPS 定位, 还有基于网络定位, Wi-Fi 基站, 原理就是通过扫描到的 Wi-Fi 和基站列表, 信号强度, 进行数据库查找, 找到 Wi-Fi 位置, 定位.
除此之外还有惯性导航定位, 惯性导航是一种相对定位的方式, 可以不断计算跟上次定位的偏移量, 有了初始定位之后, 根据连续计算可以获得最终的位置.
还有根据地图匹配定位, 比如 GPS 的点落在一个湖里, 显然是有问题的, 可以通过地图匹配, 找到最近的一条路, 这时候精度就得到了提升.
还有一些定位方式最近几年变得很热门, 例如视觉, 雷达, 激光, 自动驾驶的概念推动了这些技术的发展, 这些方式各有各的定位精度和差异性. 例如视觉, 在实践中往往需要大量计算和存储的开销.
很多时候, 还是要基于 Wi-Fi 的定位, 获得初始定位, 然后在不同场景下不断的优化, 通过不同的数据源提升精度.
高德地图如何实现全场景定位
高德主要分为两个业务场景, 手机和车机. 在手机上主要是 GPS + 网络定位. 驾车的场景下, 我们还会做一些根据地图的匹配, 实现对特殊道路的支持.
以往, 很多用户会反馈说会遇到 GPS 信号不好, 导致无法定位, 无法导航的情形. 约有 60% 的情况是因为用户位于地下停车场或者在隧道里, 约 30% 的情况是附近有严重的遮挡, 比如在高架桥下, 或者在很高的高楼旁. 这些都会造成对 GPS 比较严重的遮挡.
我们打电话的时候, 连接的基站可能就在一公里范围内, 这样短的距离传输信号还时常会出现信号中断, 如果 GPS 信号距离两万多米的高度, 出现问题的可能性还是存在的. 所以必须通过其他方式, 例如地图匹配或者惯性导航来对 GPS 进行补充.
在室内的场景, 需要解决的是如何去挖掘 Wi-Fi 基站的位置, 提升精度.
在车机的场景, 我们会结合更多来自于汽车的数据输入来帮助我们.
定位的基础能力
网络定位本质上是一个数据闭环, 每个人在定位的时候, 实际上是发送了本身的基站和 Wi-Fi 列表, 发送的数据一方面可以用来定位, 另一方面也可以用做数据训练. 数据训练主要产出两种数据, 一个是 Wi-Fi 基站的位置, 通过数据挖掘, 我们就可以获得大概的位置 (初始定位), 但是精度比较差. 第二个是产生更详细的空间信号强度分布图. 有了这个图以后, 就可以进行比较精准的定位了, 根据信号强度判断我距离这个基站和 Wi-Fi 有多远, 从而对精度进行改进.
数据闭环完成以后, 就是一个正向的反馈, 数据越多, 训练结果越多, 定位结果就越准确, 从而吸引更多的用户来使用 (产生数据). 这就是通过数据挖掘, 不断提升精度的闭环.
算法部分, 我们也经过了不断的迭代. 最早是基于经典的聚类模型, 就是扫描基站 Wi-Fi 列表, 聚类以后选择其中一处作为我的位置, 这个方法效率比较高, 很快可以得到结果, 但是精度很差.
第二步, 我们把空间进行了精细的划分, 在每个网格内统计一些基础的特征, 比如历史上的点定位的数量, 定位的次数, Wi-Fi 的数量等等, 计算出一个网格的打分, 再对网格进行排序, 最后你的定位点就是这个网格. 通过这种方法, 30 米精度的占比提升了 15%.
这种方法也有局限性, 人工调参带来的收益是有限的, 调到一定程度就没办法再提升了. 所以, 第三步就是把机器学习算法引入这个过程, 利用监督的学习提升到最佳的模型和参数, 这样可以在特定场景下获得显著提升. 主要的场景就是解决大误差的 Case.
一个比较典型的问题就是, 扫描到的基站 Wi-Fi 可能只有一个基站, 一个 Wi-Fi, 没有别的信息了. 这个基站 Wi-Fi 又离的特别远, 无论选择基站还是 Wi-Fi, 都有 50% 的概率是算错了. 有监督学习, 就可以把海量的配送拿出来, 精细化的挖掘细微的差异, 达到全局最优的效果, 在某一情况下选基站, 某一情况下选 Wi-Fi. 把犯错的比例降低了 50%.
上图就是我们的线上神经网络的模型, 神经网络用于在线服务现在是比较流行的方式, 我们在这里实际上是利用基站和 Wi-Fi 的信号强度和混合特征作为特征输入, 同时把历史位置也作为序列放进来, 这个历史位置特征会放入一个 RNN 模型, 预测现在的位置, 使用预测的结果和基站 Wi-Fi 列表特征, 再往下预测, 最后是网格的打分. 最终输出一个概率最高的网格作为输出.
这个方法最大的挑战并不是在算法, 而是算法效果和工程上的可实现性, 如何能够达到最优. 高德每天有上千亿次的调用, 延时要在 10 毫秒以内.
另外, 数据量很大, 所有的数据, 每条都有很多特征, 在线的数据存储大概有几十个 TB, 这个数据量也不可能放在在线服务里做, 所以要做相应的优化.
我们做了三个方面的优化, 第一是分级排序. 把定位过程变成一个显微镜步骤, 先做一个很粗略的定位, 然后逐步收敛到很精确的位置. 粗略定位的时候可以用很大的网格, 用很少的特征, 快速过滤掉一些不可能的位置.
然后, 在很精细的网格里, 用更多的特征, 更多的网格进行排序. 通过这种方法, 就可以极大提升计算的效率, 把一些不必要的计算过滤掉.
第二是模型简化. 虽然深度学习的效果很好, 但是不可能在线上用很复杂的模型, 我们通过减少层数和节点数, 把浮点数精度降低.
第三是特征压缩. 这里面有特色的一点是我们根据模型进行的压缩, 原始特征的输入的数量是很大的, 我们增加一个编码层, 输入的特征经过编码层以后, 只输出两个字节的特征. 我们把在线, 离线的数据处理好以后, 最后在线只存储两个字节. 通过这种方法, 在线特征的数据量降低了 10 倍, 降低到 1 个 TB 以内. 以上是解决的几个主要问题.
不同场景下的精度提升
在室内场景, 经常会定位到室外去, 这跟刚才介绍的序列流程是有关系的, 因为采集过程更大概率是在室外, 序列后的 Wi-Fi 位置都在马路上, 所以定位最后的概率也是在马路上, 但是这对用户体验是很差的. 比如打车, 可能在室内叫车, 定位在对面的马路上, 但这条马路可能是不对的, 需要找到我在哪个楼里, 离哪个道路比较近.
怎么解决这个问题? 一种方法是通过数据采集, 就是在室内进行人工的采集, 使训练数据的数据分布跟实际的预测数据分布保持一致, 这种方法当然精度比较好, 但是主要缺陷是成本非常高, 目前也只是在热门商场和交通枢纽进行这样的数据采集, 这肯定不是一个可扩展的方法.
我们的方法是想通过引入更多的数据优化定位过程. 如果能基于地图数据挖掘出 Wi-Fi 和 POI 的关系, 就可以用数据关联提升精度. 比如扫到一个 Wi-Fi, 名字叫 KFC, 有一个可能就是你在肯德基里, 这个方法比较简单. 实际用的方法会更加复杂.
我们是利用 Wi-Fi 信号的分布反向挖掘出位置, 上图里蓝色的部分就是楼块的位置, 红色的点是 Wi-Fi 的真实位置, 绿色的点是采集到 Wi-Fi 的位置, 绿色越亮, 代表这个地方的信号强度越强, 通过这个图放入图像学习, 比如用 CNN 挖掘出它的位置以后, 我们就可以建立一个 Wi-Fi 跟楼块或者跟 POI 的关联, 通过这个方法可以使全量 Wi-Fi 的 30% 都能关联上相应的 POI 或者楼块.
在线的时候需要知道用户什么时候在室内, 什么时候在室外. 我们用的是利用信号强度特征做区分的算法, 在室内室外扫描到的 Wi-Fi 列表和强度会有很大差别, 通过这个差别可以训练出模型. 绿色的点预测为室内的点, 蓝色的点是室外的点. 通过这种方法, 定位精度提升了 15%.
驾车场景, 导航过程中可能会遇到的常见问题. 第一个问题是无法定位, 开到停车场或者有遮挡的地方, 第二个场景是点会有漂移, 因为 GPS 受到建筑或者其他遮挡的时候, 会产生精度下降的情况. 第三种情况是无法区分主路, 可能会错过路口.
对于以上问题, 我们采用的是 "软 + 硬" 融合定位, 软的部分包括两部分, 一个是基于移动定位, 第二个是根据地图匹配. 经过两个 "软 + 硬" 结合之后, 我们在 GPS 10 米精度做到 90% 以上, 可以实现高架主路和停车场的持续导航.
这里面关键的就是如何实现融合定位, 比较有特色的一点就是我们做车机的传感器模块是低成本的, 成本不到 100 元, 其他类似产品成本是比较高的, 可能需要几千块钱. 使用低成本的器件, 能够更容易得到普及. 缺点是精度比较差, 定位准确性差一些. 要通过软件的方法弥补硬件上的缺点.
我们的解决办法分成三个步骤, 首先是航向融合. 陀螺仪有相对的角度可以算出来, 加速器可以算出地球引力的方向, 这两个结合以后就可以建立一个滤波方程, 把真实的方向持续不断的输出. 第二, 把三维的方向和 GPS 的结果进行一次融合, 就可以计算出修正后的位置. 第三步, 再和地图匹配做对比, 因为我们知道它的方向, 位置以后, 就知道它是在上坡还是下坡, 是在高架上还是高架下. 还有一点, 匹配后的位置跟 GPS 原始位置做对比, 如果差别很大, GPS 可能发生了偏移, 我们就把 GPS 舍弃掉, 只用惯性导航推算.
这里面有三个特点, 第一, 参数动态标定, 不需要对器件有初始的标的, 我们通过三维的计算出方向, 用地图匹配反馈. 关于地图匹配的部分, 核心是我们利用 HMM 的算法进行位置的匹配, 推算每个点的道路. 这里面比较关键的概率, 一个是发射概率, 一个是位置转移概率.
第二, 我们把角度也考虑进来, 角度的变化同样用于决策转移概率, 这里面跟位置转移概率的区别就是引入了速度做变量, 不同的速度下, 发生转角的概率是不一样的, 速度慢了可能会转向, 速度快也可能转向, 所以我们针对每个速率都有一个曲线.
上图是定位效果, 红色的点是实际修正后的轨迹, 蓝色的点是原始的 GPS 点, 下面是在高架下的效果, 可以看到高架下 GPS 点已经非常发散了, 飘的到处都是, 但是修正之后跟绿色的点是重叠的. 下面的图是在停车场里, 在停车场进去的时候, 蓝色的点就已经消失了, 但是红色的点可以很好的还原出用户在停车场里持续的轨迹.
高精定位方面, 高德主要建立两种定位能力, 一种是基于图像定位, 一种是基于融合定位. 图像定位是只用图像就可以形成比较好的分米级精度, 融合定位主要是引入了两个新的定位技术, 一个是 VSLAM, 一个是差分 GPS. 这两个方法分别应用于有 GPS 和没有 GPS 的情况, 可以提供很好的精度. VSLAM 可以做到误差很小, 因为可以有图像的方法进行修正.
自动驾驶是一个方向, 并且需要从辅助驾驶过渡到自动驾驶, 但系统性变化到来之前会有阶段性的变化, 就是服务于人的导航服务的精细化, 即车道级导航. 车道级导航需要高精地图, 至少是分米级的精度.
对未来定位技术发展的理解. 基础能力部分, 我们认为 5G 的出现会为定位提供一种新的可能性, 因为 5G 的频率比 4G 更高, 波长会更短. 它可以测距, 以前基于基站和 Wi-Fi 的定位都是基于信号强度的. 但是 5G 支持了测距以后, 它就可以提供一个很好的精度, 所以可能会出现一种方式, 基于 5G 的定位可以达到类似 GPS 的效果.
第二是融合定位, 随着各种新的数据源不断出现, 用新的算法去发挥不同数据源的特点, 从而达到整体效果的提升. 驾车部分, 视觉定位和差分 GPS 技术的逐渐普及. 室内部分, 有超宽带的定位, 除此之外还有蓝牙和 Wi-Fi 的精准定位. 在最新的技术标准里, 也都支持了测距和测角的技术, 也就是未来新的蓝牙或者 Wi-Fi 的 App, 可能就能提供一部分的定位能力.
所以, 未来 10 年内, 我们可能会看到这几种方式相互融合, 精度会得到质的改变. 以上就是我介绍的内容, 谢谢大家!
关注高德技术, 找到更多出行技术领域专业内容
来源: https://www.cnblogs.com/amap_tech/p/11725449.html