高精度的舆图须要宏大的舆图客栈，供应道由、导航指令和ETA筹算等任事。以往， Uber工程师应用各样反应来识别舆图差池，比方，记载和剖析用户反应的机械进修模子

高精度的舆图须要宏大的舆图客栈，供应道由、导航指令和ETA筹算等任事。以往， Uber工程师应用各样反应来识别舆图差池，比方，记载和剖析用户反应的机械进修模子，或通过评估舆图目标来升高舆图精度。此次，Uber揭晓博客称，Uber工程师修建了CatchME体例。

CatchMapError（CatchME）是一个人例，能够通过驱动秩序操纵秩序中的匿名GPS跟踪自愿捉拿舆图数据中的差池。CatchME应用来高慢型地舆区域的数万万次驾驶的匿名和凑集数据来捉拿舆图数据差池。通过CatchME，运营商能够敏捷识别并修复这些差池，从而正在Uber平台上告终更确实的道道和改正的驾驶员团结体验。

图1：左侧舆图上贫乏的道段导致7.6分钟的ETA；右侧的切确舆图明显下降了ETA，为骑手和驾驶者供应了更好的体验。

CatchME的根本理念是Uber应用GPS追踪反响地面实况。通过阐发道道舆图般配的相当，CatchME识别舆图与地面实况之间的分别。这些分别平时是由舆图数据差池惹起的，能够通过更新舆图来处分。

CatchME的第一个寻事是寻找驾驶员的导航举止（由GPS轨迹记载）是否与提倡的舆图道道显示不相似。CatchME，应用隐马尔可夫模子（HMM）正在舆图数据上逮捕GPS轨迹，从而陈诉预期道道和本质道道之间的分别。

正在都会境遇中，GPS轨迹并不齐备确实，所以无法得知平台上车辆确凿凿处所。Uber工程师将车辆处所概率放入HMM中，维特比算法凭据这些轨迹筹算出车辆驶过的最大概的道段序列。有了这些新闻，CatchME会陈诉此序列中的跟踪相当，并卓绝显示驱动秩序举止与操纵秩序提倡旅途之间的分别。下面的图2描写了GPS轨迹怎样卓绝舆图数据中的不确实性的示例。正在这种情景下，旧金山金门公园的一条道道（a）显示一名司机正在第8大道和富尔顿街的交叉道口右转，但司机偏离了（b）提倡道道中，能够望睹存正在右转束缚，不准平台上的驾驶员向右转。不过，凭据驾驶员的举止，能够判决这条新闻大概不确实。CatchME察觉了平台提倡的导航和本质驾驶员举止之间的分别，使体例也许识别并修复差池。提倡道道与GPS轨迹之间的分别不肯定是因为舆图数据差池变成的。下面的图3卓绝显示了变成这些分别的其它两个大概原由：（a）犯警或伤害的驾驶员举止；（b）噪声GPS轨迹，即没有供应足够的详细数据来领会地确定所采用的道道（a）：一名驾驶员左转犯警，正在此图像中以红点卓绝显示。驾驶员举止导致本质行程道道与提倡道道之间的分别。

如前所述，HMM是将GPS点与舆图数据连结起来的桥梁。从观念上讲，维特比算法通过HMM中的一齐大概状况筹算囊括最大概状况序列的旅途。理思情景下，此序列中的状况转换正在一齐大概状况中应具有高概率。不过，倘若存正在舆图数据差池，则此序列仍将囊括具有低概率的状况转换。正在这种情景下，咱们将序列中的状况之间的低概率称为相当概率。排放概率（EP）和转变概率（TP）将最先放入HMM中。EP表现车辆正在某些光阴显示正在某些道段上的大概性。TP表现车辆正在肯定连续韶华内从一个道段搬动到另一个道段的大概性。所以，看待邻近具有m个道段的一个GPS点，将存正在m个EP，其表现每个道段上的该GPS轨迹的大概性。看待GPS点G1，个中有米邻近的部门，和G2，个中有ñ左近段，有m*n个TP。这些概率正在HMM中，维特比算法从中获取具有最概略率的状况序列，该概率最大概代表车辆正正在搬动的道段。

GPS点与道段上的逮捕点之间的半径隔绝正在哪里。EP表现倘若车辆本质上正在道段上，GPS将被考察的大概性。（正在MicrosoftResearch论文中清晰相合发射概率的更众新闻，通过噪声和稀少性般配障翳马尔可夫舆图）。图5：通过正在其逮捕点S1到S2之间创筑道道显示出了用于筹算合于一个点的GPS转变概率商讨到的身分上的特定段到另一GPS点上的特定段，应用下面的公式筹算：

是两个GPS点的半径隔绝与两个与GPS点联系联的逮捕点之间的可道由隔绝之间的差值的绝对值。当发射GPS处所时车辆穿过这两个部门的大概性小于其他部门。

正在该筹算中，EP和TP造成矩阵。维特比以最概略率获取环球最佳道段序列，这些概率最有大概是车辆正老手驶的道道是段，绿色圆圈是发射概率，玄色箭头是转换概率。运转维特比算法后，获得道段序列S4，S3和S1，以及G1，G2和G3的表现络续这些序列。

图6：正在该示例中，维特比算法通过应用HMM来筹算道途经渡S4，S3和S1的最大概的分段序列。这三个段代表GPSG1，G2和G3。图7：道段A和B之间存正在缺失段。不过，由绿色和蓝色点标帜的GPS点显示驾驶员穿过A到B。从GPS点G1到GPS点G2的转换概率相当低，解释G1和G2界限大概存正在舆图差池。

平时，维特比算法从HMM中拾取的道段序列表现车辆历程的道段。不过，倘若舆图数据有差池，比方图7中描写的段，则该序列将囊括相当低的转变概率，解释车辆无法正在段上行进或正在舆图数据上下文中的某些段之间转换。CatchME通过应用绿色和蓝色颜色可视化可疑的GPS点来识别GPS轨迹之间的分别，这些颜色指示给定道道）。正在这些情景下，操作员能够敏捷找到该区域并修复这些差池（图2）。

因为提倡道道和实际道道之间的分别不肯定表现舆图数据中的差池，所以逮捕给定道道上的差池不行仅依赖于一次驾驶的结果。相反，CatchME应用来高慢地舆区域的数万万次驾驶的匿名和凑集数据来捉拿舆图数据差池。CatchME采用分而治之（D＆C）要领正在差异行程中横向扩展。D＆C的紧要目的是对GPS轨迹和舆图数据举行分片，以便能够并行管束它们。分片基于跟踪和舆图数据的S2单位。超过众个S2细胞的迹线被分成众个子迹线细胞齐备包罗。检测正在差异的S2细胞中平行独立运转。下面的图8注解了这种高级分片。为了保障每个S2单位囊括可用于检测差池的一齐舆图数据，咱们平时扩展S2单位界限，以便一齐舆图数据及其联系的GPS点都正在畛域内。

图8：应用S2单位对GPS轨迹和舆图数据举行分片使咱们也许大范围地收罗相合舆图数据差池的主睹。

不过，应用静态S2单位分区行程和照射数据有时无法供应足够的并发性。比方，旧金山国际机场（SFO）等某些区域的S2小区的驾驶次数远远众于墟落区域好像水准的S2小区。为了进一步升高CatchME的本能，为每个高密度单位制制了众个副本。每个副本具有好像的舆图数据，不过具有差异且平均分散的行程集，如下面的图9所示：这种要领消逝了由高密度单位惹起的瓶颈，而且导致更确实的结果，由于每个单位已经足够大，以包罗用于舆图般配和差池检测的完全舆图数据上下文和GPS点。举动缩放CatchME的结果，足够的分别信号（相当概率）供应了用于评估数据差池的统计视图。凑集来高慢量驾驶的结果背后的玄学是，倘若看到正在驾驶陈诉的给定地址的相当概率的相似性，这种分别的基础原由更大概是舆图数据差池而倒霉害法驾驶举止或噪声GPS信号。

因为CatchME依然确定了位于具有16级巨细（S2小区统计）的某些S2小区中的GPS点之间的相当概率方面的分别，均匀巨细为19，793平方米，所以CatchME将每个S2小区视为根本差池单位。通过凑集这些单位，CatchME能够确定哪些差池更有大概影响驱动秩序团结伙伴操纵秩序的用户体验。如图3（b）所示，分别不肯定是差池。CatchME连结GPS点，个中视差信号（或相当转变概率）举动众边形链存正在（平时该众边形链囊括大约40个GPS点）。倘若此链的几何无效，CatchME将大意此差池信号。CatchME还考察到肯定数目的差池警报，这些差池警报是因为下面的图10所示的GPS轨迹偏移惹起的，个中GPS轨迹穿过筑造物而不是贴近道道搬动。倘若这些GPS点超过众个物理筑造大于某个阈值，CatchME将大意这种分别。图10：由黄点动画显示的GPS跟踪显示GPS跟踪移位。CatchME大意了这种情景，假使它激发了视差信号。

CatchME的结果依然说明了一种极端有前景的要领。正在推出后的前三个月内，CatchME检测到高出28，000个舆图差池。正在Uber的舆图上矫正这些差池大大升高了驾驶ETA，导航和用户体验确凿实性。来日，Uber打算通过加强算法和运用卫星图像等其他证据来进一步升高CatchME的精度。纠合客户陈诉的舆图差池，CatchME察觉的舆图差池将为驾驶员供应更好的体验。[2] Newson P , Krumm J . [ACM Press the 17th ACMSIGSPATIAL Internatio