一种用于道路交叉口拓扑结构生成的方法和装置与流程

1.本说明书涉及导航道路网领域，特别涉及一种用于道路交叉口拓扑结构生成的方法和装置。


背景技术：

2.城市导航道路网是路径规划、快递物流、行程时间估计、网约车分单等应用服务的数据基石。道路交叉口拓扑生成是构建高精度导航道路网拓扑数据的关键环节。随着大数据时代的到来，车辆记录了大量的行驶数据，可以基于车辆的行驶数据进行道路交叉口拓扑结构的生成。现有方法主要依据轨迹转向与速度变化等特征识别道路交叉口位置与范围，进而对交叉口内部道路拓扑进行重建。主要技术方法包括基于轨迹聚类的方法和基于出入口点的方法。其中，基于轨迹聚类的方法，对交叉口内的轨迹线段进行聚类，获得轨迹簇，对每个簇进行中心线拟合，生成交叉口内部道路，这类方法需要预先指定聚类数目，而实际生产应用中很难预先知道交叉口内部所包含的道路数目，导致聚类不精确；基于出入口点的方法，先提取交叉口范围边界与原始轨迹线的相交点，然后利用密度聚类或基于图的聚类算法对相交点进行聚类，以聚类的中心点作为识别的交叉口出入口点，对连接出入口点对的轨迹进行中心线拟合生成交叉口内部道路，这类方法可以构建精细的交叉口拓扑模型，但是由于轨迹噪声等影响，通过密度聚类或基于图的硬性聚类算法容易产生出入口点识别冗余或丢失问题。因此，如何利用车辆记录的行驶数据来进行道路交叉口拓扑生成，提升算法在高轨迹噪声环境下的鲁棒性和适应性，成为目前亟需解决的问题。
3.因此，希望提供一种用于道路交叉口拓扑结构生成的方法和装置，可以对道路交叉口的道路进行拓扑构建，提升道路交叉口拓扑的准确性。


技术实现要素：

4.本说明书实施例之一提供一种用于道路交叉口拓扑结构生成的方法。所述用于道路交叉口拓扑结构生成的方法包括：获取车辆轨迹数据；基于所述车辆轨迹数据获取道路交叉口的识别结果，所述识别结果包括所述道路交叉口的位置与范围；基于第一聚类模型对位于同一个道路交叉口范围内的车辆轨迹段进行聚类以获得初始轨迹聚类结果；基于第二聚类模型从所述初始轨迹聚类结果中提取所述道路交叉口的出口点以及入口点；以及基于所述出口点以及所述入口点，确定所述道路交叉口的道路拓扑。
5.本说明书实施例之一提供一种用于道路交叉口拓扑结构生成的装置，所述装置包括至少一个处理器和至少一个存储器，至少一个所述存储器中存储有程序指令，至少一个所述处理器读取所述程序指令后执行如前所述的用于道路交叉口拓扑结构生成方法。
6.本说明书实施例之一提供一种计算机可读存储介质，所述存储介质中存储有程序指令，计算机读取所述程序指令后执行如前所述的用于道路交叉口拓扑结构生成方法。
附图说明
7.本说明书将以示例性实施例的方式进一步说明，这些示例性实施例将通过附图进行详细描述。这些实施例并非限制性的，在这些实施例中，相同的编号表示相同的结构，其中：
8.图1是根据本说明书一些实施例所示的用于道路交叉口拓扑结构生成的系统的应用场景示意图；
9.图2是根据本说明书一些实施例所示的用于道路交叉口拓扑结构生成的装置的示例性模块图；
10.图3是根据本说明书一些实施例所示的用于道路交叉口拓扑结构生成的的方法的示例性流程图；
11.图4是根据本说明书一些实施例所示的基于第二聚类模型提取道路交叉口的出入口点的示例性流程图；
12.图5是根据本说明书一些实施例所示的基于车辆轨迹数据获取道路交叉口的识别结果的示例性流程图；
13.图6是根据本说明书一些实施例所示的确定道路交叉口的道路拓扑的示例性流程图；
14.图7是根据本说明书一些实施例所示的预处理的车辆轨迹数据的示例性示意图。
15.图8是根据本说明书一些实施例所示的初始轨迹聚类结果的示例性示意图。
16.图9是根据本说明书一些实施例所示的起始点集合和结束点集合的示例性示意图。
17.图10是根据本说明书一些实施例所示的提取道路交叉口的出口点和入口点的示例性示意图。
具体实施方式
18.为了更清楚地说明本说明书实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单的介绍。显而易见地，下面描述中的附图仅仅是本说明书的一些示例或实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图将本说明书应用于其它类似情景。除非从语言环境中显而易见或另做说明，图中相同标号代表相同结构或操作。
19.应当理解，本文使用的“系统”、“装置”、“单元”和/或“模块”是用于区分不同级别的不同组件、元件、部件、部分或装配的一种方法。然而，如果其他词语可实现相同的目的，则可通过其他表达来替换所述词语。
20.如本说明书和权利要求书中所示，除非上下文明确提示例外情形，“一”、“一个”、“一种”和/或“该”等词并非特指单数，也可包括复数。一般说来，术语“包括”与“包含”仅提示包括已明确标识的步骤和元素，而这些步骤和元素不构成一个排它性的罗列，方法或者设备也可能包含其它的步骤或元素。
21.本说明书中使用了流程图用来说明根据本说明书的实施例的系统所执行的操作。应当理解的是，前面或后面操作不一定按照顺序来精确地执行。相反，可以按照倒序或同时处理各个步骤。同时，也可以将其他操作添加到这些过程中，或从这些过程移除某一步或数
步操作。
22.图1是根据本说明书一些实施例所示的用于道路交叉口拓扑结构生成的系统的应用场景示意图。
23.如图1所示，用于道路交叉口拓扑结构生成系统100可以包括处理设备110、网络150和存储设备160。道路交叉口拓扑结构生成系统100生成的道路交叉口拓扑结构可以用于导航地图或者道路网生成。
24.在一些实施例中，用于道路交叉口拓扑结构生成系统100可以通过实施本说明书中所披露的方法和/或过程来实现道路交叉口拓扑结构的生成。例如，在一些应用场景中，处理设备110可以获取车辆轨迹数据120，基于车辆轨迹数据120获取道路交叉口的识别结果130，识别结果130可以包括道路交叉口的位置与范围。处理设备110可以基于第一聚类模型111对位于同一个道路交叉口范围内的车辆轨迹段进行聚类以获得初始轨迹聚类结果，基于第二聚类模型112从初始轨迹聚类结果中提取道路交叉口的出口点以及入口点，进而基于出口点以及入口点，确定道路交叉口的道路拓扑结构140。
25.处理设备110可以通过网络150与存储设备160通信以获取和/或存储数据和/或信息。例如，处理设备110可以通过网络150从存储设备160获取车辆轨迹数据、用于道路交叉口拓扑结构生成的模型或者算法(例如，聚类模型)等。处理设备110可以基于获取的数据、信息和/或处理结果执行程序指令，以实现对用于道路交叉口拓扑结构的生成。例如，处理设备110可以基于第一聚类模型对道路交叉口范围内的车辆轨迹段进行聚类以获得初始轨迹聚类结果，基于第二聚类模型从初始轨迹聚类结果中提取道路交叉口的出口点以及入口点。存储设备160可以存储道路交叉口拓扑结构生成过程中产生的中间数据或者结果，例如，预处理后的车辆轨迹数据、道路交叉口的识别结果、初始轨迹聚类结果、道路交叉口的出口点以及入口点、道路交叉口的道路拓扑等。以上各设备之间的信息传递关系仅作为示例，本技术并不局限于此。
26.在一些实施例中，处理设备110可以处理从其它设备或系统组成部分中获得的数据和/或信息，基于这些数据、信息和/或处理结果执行程序指令，以完成一个或多个本说明书中描述的道路交叉口拓扑结构生成的过程。例如，处理设备110可以从外部数据源(例如，数据库)获取车辆轨迹数据120通过处理获得道路交叉口的识别结果130。
27.在一些实施例中，处理设备110可以包括单个服务器或服务器组。服务器组可以是集中式的，也可以是分布式的。在一些实施例中，处理设备110可以是本地的或远程的。例如，处理设备110可以通过网络150从终端(例如，移动设备、车载设备)和/或存储设备160访问信息和/或数据。又例如，处理设备110可以直接连接终端和/或存储设备160以访问信息和/或数据。在一些实施例中，处理设备110可以在云平台上实现。例如，云平台可以包括私有云、公共云、混合云、社区云、分布式云、跨云、多云等其中一种或几种的组合。
28.网络150可以连接系统的各组成部分和/或连接系统与外部资源部分。网络150使得各组成部分之间，以及与系统之外其他部分之间可以进行通讯，促进数据和/或信息的交换。在一些实施例中，网络150可以是有线网络或无线网络中的任意一种或多种。例如，网络150可以包括电缆网络、光纤网络、电信网络、互联网、局域网络(lan)、广域网络(wan)、无线局域网络(wlan)、城域网(man)、设备内总线、设备内线路、线缆连接等或其任意组合。各部分之间的网络连接可以是采用上述一种方式，也可以是采取多种方式。在一些实施例中，网
络可以是点对点的、共享的、中心式的等各种拓扑结构或者多种拓扑结构的组合。
29.存储设备160可以用于存储数据和/或指令。存储设备160可以包括一个或多个存储组件，每个存储组件可以是一个独立的设备，也可以是其它设备的一部分。在一些实施例中，存储设备160可包括随机存取存储器(ram)、只读存储器(rom)、大容量存储器、可移动存储器、易失性读写存储器等或其任意组合。
30.在一些实施例中，道路交叉口拓扑结构生成系统100可以与导航系统通信。道路交叉口拓扑结构生成系统100可以将生成的道路交叉口拓扑结构发送给导航系统。导航系统可以包括在终端上实施应用程序(例如，导航应用程序)。终端可以包括用户界面，用于通过应用程序实现用户与导航系统之间的交互。例如，用户可以通过用户界面输入目的地，并通过应用程序发送给导航系统中的服务器，服务器可以为用户规划路径并进行导航。在导航过程中，服务器可以通过应用程序将道路交叉口拓扑结构显示在用户界面上。在一些实施例中，可以在用户界面突出显示道路交叉口的道路拓扑。例如，在用户界面通过方框和不同于其他道路标志的颜色来显示道路交叉口的道路拓扑。
31.图2是根据本说明书一些实施例所示的用于道路交叉口拓扑结构生成的装置的示例性模块图。
32.如图2所示，在一些实施例中，用于道路交叉口拓扑结构生成的装置200可以包括轨迹数据获取模块210、交叉口识别模块220、出入口确定模块230和拓扑结构生成模块240。
33.在一些实施例中，轨迹数据获取模块210可以用于获取车辆轨迹数据。
34.在一些实施例中，交叉口识别模块220可以用于基于车辆轨迹数据获取道路交叉口的识别结果，识别结果可以包括道路交叉口的位置与范围。
35.在一些实施例中，出入口确定模块230可以用于基于第一聚类模型对道路交叉口范围内的车辆轨迹段进行聚类以获得初始轨迹聚类结果。
36.在一些实施例中，出入口确定模块230可以用于基于第二聚类模型从初始轨迹聚类结果中提取道路交叉口的出口点和入口点。
37.在一些实施例中，拓扑结构生成模块240可以用于基于出口点和入口点，确定道路交叉口的道路拓扑。
38.在一些实施例中，第一聚类模型包括基于密度的聚类模型，出入口确定模块230还可以用于确定车辆轨迹段的轨迹差异，轨迹差异用于表示任意两个轨迹段之间的差异；以及基于轨迹差异，利用基于密度的聚类模型获得初始轨迹聚类结果，其中任意两个轨迹段之间的差异包括轨迹距离差异或轨迹方向差异中的至少一个。
39.在一些实施例中，第二聚类模型包括高斯混合模型，出入口确定模块230还可以用于对于初始轨迹聚类结果中的每个轨迹聚类结果，提取轨迹聚类结果中的轨迹段的起始点以及结束点以获得起始点集合和结束点集合；采用高斯混合模型，在不同聚类数目条件下，分别对起始点集合和结束点集合内的点进行聚类以确定多个起始点聚类结果和多个结束点聚类结果，每个起始点聚类结果包括在特定聚类数目下的起始点簇，每个结束点聚类结果包括在特定聚类数目下的结束点簇；基于贝叶斯信息准则，从多个起始点聚类结果和多个结束点聚类结果中确定最终起始点聚类结果和最终结束点聚类结果；以及分别基于最终起始点聚类结果和最终结束点聚类结果确定所述入口点以及所述出口点。
40.在一些实施例中，交叉口识别模块220还可以用于确定车辆轨迹数据中的轨迹点
对应的转角；基于轨迹点对应的转角对轨迹点进行筛选以获取筛选后的轨迹点；采用第三聚类模型对筛选后的轨迹点进行聚类以获得多个轨迹点簇；基于多个轨迹点簇中的轨迹点对应的转角对多个轨迹点簇进行筛选以获得筛选后的轨迹点簇；以及基于筛选后的轨迹点簇确定道路交叉口的识别结果。
41.在一些实施例中，交叉口识别模块220还可以用于确定筛选后的轨迹点簇对应的多个包围圆；对于多个包围圆中的任意一个包围圆，基于包围圆与其他包围圆之间的最小距离确定包围圆的缓冲区范围；以及基于包围圆与包围圆的缓冲区范围确定道路交叉口的识别结果。
42.在一些实施例中，交叉口识别模块220还可以用于基于热点分析模型确定轨迹点的热度值；以及从轨迹点中剔除热度值小于一定热度阈值以及转角小于一定角度阈值的轨迹点以获得筛选后的轨迹点。
43.在一些实施例中，拓扑结构生成模块240可以用于基于入口点、出口点以及位于道路交叉口的范围内的车辆轨迹段确定连接相同出口点和入口点的轨迹集合；从轨迹集合中确定参考轨迹；基于参考轨迹的特征参数确定中心线拟合模型；以及基于中心线拟合模型对轨迹集合中的轨迹线进行中心线拟合以生成连接相同出口点和入口点的道路拓扑。
44.在一些实施例中，参考轨迹的特征参数包括参考轨迹的长度与参考轨迹在道路交叉口范围内的起始点和结束点之间的距离之间的比值，若比值小于一定比值阈值，拓扑结构生成模块240可以确定中心线拟合模型包括b样条拟合模型；或者若比值大于一定比值阈值，拓扑结构生成模块240可以确定中心线拟合模型包括k段主曲线拟合模型。
45.应当理解，图2所示的系统及其模块可以利用各种方式来实现。例如，在一些实施例中，系统及其模块可以通过硬件、软件或者软件和硬件的结合来实现。
46.需要注意的是，以上对于系统及其模块的描述，仅为描述方便，并不能把本说明书限制在所举实施例范围之内。可以理解，对于本领域的技术人员来说，在了解该系统的原理后，可能在不背离这一原理的情况下，对各个模块进行任意组合，或者构成子系统与其他模块连接。在一些实施例中，图2中披露的轨迹数据获取模块210、交叉口识别模块220、出入口确定模块230和拓扑结构生成模块240可以是一个系统中的不同模块，也可以是一个模块实现上述的两个或两个以上模块的功能。例如，各个模块可以共用一个存储模块，各个模块也可以分别具有各自的存储模块。诸如此类的变形，均在本说明书的保护范围之内。
47.图3是根据本说明书一些实施例所示的用于道路交叉口拓扑结构生成的的方法的示例性流程图。如图3所示，在一些实施例中，流程300可以包括步骤310、步骤320、步骤330、步骤340以及步骤350。
48.步骤310，获取车辆轨迹数据。在一些实施例中，步骤310可以由处理设备110或轨迹数据获取模块210执行。
49.车辆轨迹数据可以包括多个车辆行驶在道路上的多条轨迹线。每条轨迹线由多个轨迹点形成。
50.在一些实施例中，轨迹数据获取模块210可以通过网络获取车辆轨迹数据。例如，利用网络获取通过车辆的全球导航卫星系统采集的车辆轨迹数据。在一些实施例中，轨迹数据获取模块210可以从存储设备(如存储设备160)获取车辆轨迹数据(如车辆轨迹数据120)。
51.在一些实施例中，轨迹数据获取模块210可以对车辆轨迹数据进行预处理。预处理可以指去除车辆轨迹数据中的异常数据。预处理可以包括异常轨迹段剔除、对车辆轨迹数据进行降噪、对同一条道路上分散的轨迹向道路中心位置进行聚合等处理中至少一个。
52.由于全球导航卫星系统的信号遮挡等原因，车辆轨迹数据中相邻的轨迹点会存在较大的时间间隔、距离间隔等，导致相邻轨迹点的距离异常，产生异常轨迹段。在一些实施例中，异常轨迹段可以包括相邻轨迹点的时间间隔大于多倍(如三倍)的平均采样间隔、距离间隔大于400米、500米等、采样点的车辆速度大于100km/h、120km/h等。在一些实施例中，轨迹数据获取模块210可以分割车辆轨迹数据中的异常轨迹段，分割成一个或多个车辆轨迹段，将异常轨迹段剔除。
53.车辆轨迹数据中可能存在一些噪声，影响道路拓扑，可以对车辆轨迹数据进行降噪。在一些实施例中，轨迹数据获取模块210可以基于轨迹长度和轨迹点的数目对车辆轨迹数据进行降噪。在一些实施例中，轨迹数据获取模块210可以对剔除异常轨迹段后的车辆轨迹数据或者初始的轨迹数据(例如，未剔除异常轨迹段的车辆轨迹数据)进行降噪。例如，如果一条轨迹长度大于长度阈值(例如300m或400m)，则删除该条轨迹。又例如，如果一条轨迹中轨迹点的个数小于计数阈值(例如30个、35个、40等)，删除该条轨迹。
54.全球导航卫星系统的信号有时会发生漂移，车辆轨迹有可能偏离道路中心。在一些实施例中，轨迹数据获取模块210可以通过引力-斥力轨迹数据聚合模型对同一条道路上分散的轨迹向道路中心位置进行聚合。
55.在一些实施例中，如图7所示，轨迹数据获取模块210通过对车辆轨迹数据710进行预处理，可以获取预处理后的车辆轨迹数据720。预处理后的车辆轨迹数据720剔除了异常轨迹段、删除了存在噪声的车辆轨迹、对同一条道路上分散的轨迹向道路中心位置进行聚合等，获得如图7所示的车辆轨迹数据720。
56.在本说明书一些实施例中，通过剔除异常轨迹段、对车辆轨迹数据进行降噪、对同一条道路上分散的轨迹向道路中心位置进行聚合等对车辆轨迹数据进行预处理，获取预处理后的车辆轨迹数据，可以减少由于全球导航卫星系统的信号遮挡、漂移对车辆轨迹数据的影响，保证车辆轨迹数据的准确性，更有利于道路交叉口的道路拓扑，以提高交叉口的道路拓扑结构生成的准确性。
57.步骤320，基于车辆轨迹数据获取道路交叉口的识别结果。在一些实施例中，步骤320可以由处理设备110或交叉口识别模块220执行。
58.道路交叉口可以指不同道路之间存在交叉的位置。例如，车辆可以通过道路交叉口从当前道路进入到其他道路。
59.在一些实施例中，识别结果可以包括道路交叉口的位置与范围。
60.在一些实施例中，交叉口识别模块220可以基于多个车辆轨迹数据，通过提取车辆轨迹数据中的轨迹点对应的转角(也可以称为转向角)，通过热点分析模型基于轨迹点对应的转角对轨迹点进行筛选获得筛选后的轨迹点(也可以称为热点)，对热点聚类获得轨迹点簇，通过确定轨迹点簇的多个包围圆获取道路交叉口的位置与范围。
61.在一些实施例中，交叉口识别模块220可以通过确定车辆轨迹数据中的轨迹点对应的转角，基于轨迹点对应的转角对轨迹点进行筛选以获取筛选后的轨迹点。交叉口识别模块220可以采用聚类模型(即第三聚类模型)对筛选后的轨迹点进行聚类以获得多个轨迹
点簇，基于多个轨迹点簇中的轨迹点对应的转角对多个轨迹点簇进行筛选以获得筛选后的轨迹点簇，进而基于筛选后的轨迹点簇确定道路交叉口的识别结果，具体说明请参见图5部分的相关描述。
62.步骤330，基于第一聚类模型对同一个道路交叉口范围内的车辆轨迹段进行聚类以获得初始轨迹聚类结果。在一些实施例中，步骤330可以由处理设备110或出入口确定模块230执行。
63.在一些实施例中，第一聚类模型可以包括硬聚类模型。在一些实施例中，第一聚类模型可以包括但不限于k均值聚类模型、层次聚类模型、基于密度的聚类模型等。
64.在一些实施例中，初始轨迹聚类结果可以指通过第一聚类模型对道路交叉口范围内的车辆轨迹段进行聚类的结果。在一些实施例中，第一聚类模型111的输入可以包括道路交叉口范围内的多个车辆轨迹段等。第一聚类模型111的输出可以包括初始轨迹聚类结果。在一些实施例中，初始轨迹聚类结果可以包括多个道路交叉口范围内的轨迹聚类结果。每个轨迹聚类结果可以对应一个道路交叉口。如图8所示，圆圈所示区域为道路交叉口，圆圈内为道路交叉口范围内的轨迹段的初始轨迹聚类结果。初始轨迹聚类结果包括道路交叉口范围内的车辆轨迹段。
65.在一些实施例中，出入口确定模块230可以利用基于密度的聚类模型获得初始轨迹聚类结果。具体的，出入口确定模块230可以确定车辆轨迹段的轨迹差异，基于轨迹差异，利用基于密度的聚类模型获得初始轨迹聚类结果。
66.基于密度的聚类模型可以包括dbscan聚类模型(density-based spatial clustering of applications with noise，dbscan)、optics聚类模型(ordering points to identify the clustering structure，optics)、denclue聚类模型(density-based clustering，denclue)等。
67.轨迹差异可以用于表示不同车辆轨迹段之间的差异。两个轨迹段之间的差异可以包括轨迹距离差异或轨迹方向差异中的至少一个。
68.在一些实施例中，可以以矩阵(即轨迹差异矩阵)的形式体现交叉口范围内的任意两个轨迹段之间的差异。例如，轨迹差异矩阵可以包括多个元素。每个元素可以对应两个轨迹段，元素值可以表示两个轨迹段的差异。
69.在一些实施例中，轨迹距离差异可以指车辆轨迹段距离的差异，例如，轨迹距离差异可以通过轨迹距离矩阵表示。轨迹距离矩阵可以包括多个元素，每个元素可以对应两个轨迹段，元素值可以表示两个轨迹段的距离差异。在一些实施例中，两个轨迹段的距离差异可以通过计算两个轨迹段的距离确定，例如，hausdorff距离、欧式距离等。
70.在一些实施例中，轨迹方向差异可以指车辆轨迹段方向的差异，例如，轨迹方向差异可以通过轨迹方向矩阵表示。轨迹方向矩阵可以包括多个元素，每个元素可以对应两个轨迹段，元素值可以表示两个轨迹段的方向差异。在一些实施例中，两个轨迹段的方向差异可以通过计算两个轨迹段对应的车辆运动方向或者运动矢量之间的夹角确定。
71.在一些实施例中，出入口确定模块230可以计算道路交叉口范围内的车辆轨迹段之间的hausdorff距离，构建轨迹距离矩阵。基于车辆行驶方向的角度差异来获得车辆轨迹段的之间的方向差异，构建轨迹方向差异矩阵，结合轨迹距离矩阵和轨迹方向差异矩阵获取轨迹差异矩阵。例如，可以将轨迹距离矩阵和轨迹方向差异矩阵之和确定为轨迹差异矩
阵。又例如，可以将轨迹距离矩阵和轨迹方向差异矩阵之加权和确定为轨迹差异矩阵。
72.仅作为示例，欧氏空间中的两条轨迹段a＝{a1,a2,
…
},b＝{b1,b2,
…
}，hausdorff距离计算公式(1)可以为：
73.其中，a1、a2、b1、b2等表示轨迹段中的轨迹点，根据计算公式(1)可以计算道路交叉口范围内的多个车辆轨迹段的hausdorff距离，得到轨迹距离矩阵(2)：
74.其中，d
11
、d
12
、d
nn
等表示多个车辆轨迹段之间的不同距离。又例如，基于车辆行驶方向的角度差异，将多个车辆轨迹段中每个轨迹段的起点到终点的连线方向作为车辆轨迹段的方向，通过以下计算公式(3)比较多个车辆轨迹段之间的方向差异公式：
75.其中，通过公式(3)得到的多个车辆轨迹段之间的方向差异构建得到方向差异矩阵(4)：
76.其中，可以设置两个轨迹段之间的方向差异大于阈值(例如18度)时，两条轨迹之间的方向差异为1；两个轨迹段之间的方向差异小于阈值(例如18度)时，两条轨迹之间的方向差异为0。
77.根据轨迹距离矩阵和方向差异矩阵，通过公式(5)计算得到任意两个轨迹段之间的差异，获取轨迹差异矩阵tsm，公式(5)如下式所示。tsm＝w1*m
hausdorff
+w3*w
dirction
ꢀꢀ
(5)
78.其中，w1和w2为距离矩阵和差异矩阵对应的权重值，在一些实施例中，w1可以等于1，w2可以设置为β可以为经验值3.5。
79.在一些实施例中，轨迹差异出入口确定模块230可以通过dbscan聚类模型获得初始轨迹聚类结果。在一些实施例中，dbscan聚类模型的输入可以包括轨迹差异矩阵tsm。dbscan聚类模型的输出可以包括初始轨迹聚类结果。出入口确定模块230可以将轨迹差异矩阵tsm输入dbscan聚类模型，dbscan聚类模型输出初始轨迹聚类结果。
80.在本说明书一些实施例中，基于轨迹差异利用基于密度的聚类模型获得初始聚类结果，可以同时考虑轨迹段之间的距离差异和方向差异，获取较好的聚类结果，有利于道路交叉口的道路拓扑。对道路交叉口范围内的车辆轨迹段进行采用硬聚类算法进行初始聚类可以使得交叉口范围内的处理轨迹段分类较为精细，为后续基于提取出入口点提供较为准确地数据。例如，对道路交叉口范围内的车辆轨迹段进行采用硬聚类算法进行初始聚类，可以把一些偏离车道比较远的轨迹去除，避免将这些轨迹也看成是一个出口点或入口点，造
成虚假出入口点产生。
81.步骤340，基于第二聚类模型从初始轨迹聚类结果中提取道路交叉口的出口点和入口点。在一些实施例中，步骤340可以由处理设备110或出入口确定模块230执行。
82.在一些实施例中，第二聚类模型包括软聚类模型(或者可以称为模糊聚类模型)。在一些实施例中，第二聚类模型可以包括但不限于高斯混合模型(gaussian mixed model，gmm)、模糊c均值模型等。
83.在一些实施例中，道路交叉口可以包括出口点和入口点。车辆可以通过入口点从当前道路进入道路交叉口，通过出口点驶离道路交叉口进入下一个道路。
84.在一些实施例中，对于初始轨迹聚类结果中的每个轨迹聚类结果，出入口确定模块230可以提取每个轨迹聚类结果中的轨迹段的起始点以及结束点以获得起始点集合和结束点集合；出入口确定模块230可以采用第二聚类模型(例如，高斯混合模型)，在不同聚类数目条件下，分别对起始点集合和结束点集合内的点进行聚类以确定多个起始点聚类结果和多个结束点聚类结果，每个起始点聚类结果包括在特定聚类数目下的起始点簇，每个结束点聚类结果包括在特定聚类数目下的结束点簇；出入口确定模块230可以从多个起始点聚类结果和多个结束点聚类结果中确定最终起始点聚类结果和最终结束点聚类结果；出入口确定模块230可以分别基于最终起始点聚类结果和最终结束点聚类结果确定入口点以及出口点。关于出入口点的提取具体说明请参见图4部分的相关描述。
85.步骤350，基于出口点以及入口点，确定道路交叉口的道路拓扑。在一些实施例中，步骤350可以由处理设备110或拓扑结构生成模块240执行。
86.道路拓扑可以指对道路交叉口范围的道路进行构建，以确定道路交叉口范围内的道路结构。
87.在一些实施例中，拓扑结构生成模块240基于出口点以及入口点，通过拟合模型确定道路交叉口的道路拓扑。
88.在一些实施例中，拓扑结构生成模块240可以基于入口点、出口点和位于道路交叉口的范围内的车辆轨迹段确定连接相同出口点和入口点的轨迹集合。拓扑结构生成模块240可以从轨迹集合中确定参考轨迹，基于参考轨迹的特征参数确定中心线拟合模型。进而基于中心线拟合模型对轨迹集合中的轨迹线进行中心线拟合以生成连接相同出口点和入口点的道路拓扑，具体说明请参见图6部分的相关描述。
89.在本说明书一些实施例中，通过第一聚类模型对道路交叉口范围内的车辆轨迹段进行聚类，由于第一聚类模型是一种硬性聚类算法，可以把一些偏离车道比较远的轨迹去除，避免将这些轨迹也看成是一个出口点或入口点，造成虚假出入口点产生，可以提高聚类结果的精细度，但是容易受轨迹噪声干扰，将邻近的道路上的轨迹聚合为一个簇(即存在欠分割问题)，本发明进一步通过软聚类模型(即第二聚类模型)，可以自适应的提取道路交叉口的出口点和入口点，可以减少噪声对车辆轨迹段的干扰，增强算法对不同应用场景(例如高轨迹噪声情况下)的适应性和鲁棒性，提高重建的道路拓扑结构的精确度。
90.图4是根据本说明书一些实施例所示的基于第二聚类模型提取道路交叉口的出入口点的示例性流程图。如图4所示，在一些实施例中，流程400可以包括步骤410、步骤420、步骤430、以及步骤440。
91.步骤410，对于初始轨迹聚类结果中的每个轨迹聚类结果，提取轨迹聚类结果中的
轨迹段的起始点以及结束点以获得起始点集合和结束点集合。在一些实施例中，步骤410可以由出入口确定模块230执行。
92.初始轨迹聚类结果中的轨迹聚类结果可以指通过第一聚类模型获得的在同一个道路交叉口范围内的轨迹聚类结果。初始轨迹聚类结果中可以包括多个轨迹聚类结果。不同的轨迹聚类结果可能对应位于同一个道路交叉口内的不同道路。例如，道路交叉口范围内可能包括多条道路，多条道路可以对应多个轨迹聚类结果。关于确定初始轨迹聚类结果的更多描述可以参考图3中的步骤330的详细描述。
93.轨迹段的起始点可以指轨迹段在车辆行驶方向上的起点。例如，车辆行驶的方向是由东向西行驶，轨迹段的方向也是和车辆行驶的方向相似或者相同的由东向西方向，轨迹段的起始点可以是轨迹段的由东向西方向的起点。
94.轨迹段的结束点可以指轨迹段在车辆行驶方向上的终点。例如，车辆行驶的方向是由东南向西北行驶，轨迹段的方向也是车辆行驶的方向相似的或相同由东南向西北方向，轨迹段的结束点可以是轨迹段的由东南向西北方向的终点。
95.起始点集合可以指包括在同一个道路交叉口范围内的多个轨迹段的起始点的集合。
96.结束点集合可以指包括在同一个道路交叉口范围内的多个轨迹段的结束点的集合。
97.在一些实施例中，出入口确定模块230可以通过提取每个轨迹聚类结果中的轨迹段的起始点以及结束点以获得起始点集合和结束点集合。例如，初始聚类结果包括5个轨迹聚类结果，出入口确定模块230可以分别提取每个轨迹聚类结果中的轨迹段的起始点和结束点，分别获得5个起始点集合和5个结束点集合。如图9所示，区域910可以是起始点集合或者结束点集合，区域920表示不同的起始点集合和结束点集合的数目。
98.在步骤420中，可以采用第二聚类模型在不同聚类数目分别对起始点集合和结束点集合中的点进行聚类以获得不同聚类数目对应的起始点聚类结果或结束点聚类结果。
99.在一些实施例中，第二聚类模型可以包括高斯混合模型(gaussian mixed model，gmm)。在一些实施例中，高斯混合模型的输入可以包括聚类数目、起始点集合、结束点集合等。高斯混合模型的输出可以包括不同聚类数目对应的起始点聚类结果或结束点聚类结果。聚类数目可以是指的是基于第二聚类模型进行聚类得到的聚类结果中类别(例如，簇)的个数。每个起始点聚类结果可以包括在特定聚类数目下的起始点簇。每个结束点聚类结果可以包括在特定聚类数目下的结束点簇。例如，聚类数目是3，起始点聚类结果为包含3个起始点的起始点簇，结束点聚类结果为包含3个结束点的结束点簇。又例如，聚类数目为10，起始点聚类结果为包含10个起始点的起始点簇，结束点聚类结果为包含10个结束点的结束点簇。
100.在一些实施例中，可以根据不同的需求，设定不同的聚类数目，通过高斯混合模型获取不同聚类数目对应的起始点簇和结束点簇。例如，聚类数目可以是2-20个，通过高斯混合模型可以分别获取聚类数目是2、3、
……
、20等对应的起始点簇和结束点簇。
101.在步骤420中，可以采用高斯混合模型，在不同聚类数目条件下，分别对起始点集合和结束点集合内的点进行聚类以确定多个起始点聚类结果和多个结束点聚类结果。
102.在一些实施例中，步骤420可以包括步骤420-1和步骤420-2。步骤420-1，采用高斯
混合模型，在不同聚类数目条件下，对起始点集合内的点进行聚类以确定多个起始点聚类结果。步骤420-2，采用高斯混合模型，在不同聚类数目条件下，对结束点集合内的点进行聚类多个结束点聚类结果。在一些实施例中，步骤420-1和步骤420-2可以由出入口确定模块230执行。
103.在一些实施例中，出入口确定模块230可以将聚类数目、起始点集合输入高斯混合模型，高斯混合模型可以输出不同聚类数目对应的起始点聚类结果。例如，起始点集合为po，聚类数目为k(k＝2、3、
…
、20)，可以通过高斯混合模型获取得到不同k值对应的起始点聚类结果。
104.在一些实施例中，出入口确定模块230可以将聚类数目、结束点集合输入高斯混合模型，高斯混合模型可以输出不同聚类数目对应的结束点聚类结果。例如，结束点集合为pd，聚类数目为k(k＝2、3、
…
、20)，可以通过高斯混合模型获取得到对应k值对应的结束点聚类结果。
105.在步骤430中，可以基于贝叶斯信息准则分别从多个起始点聚类结果和结束点聚类结果中确定最终起始点聚类结果和结束点聚类结果。
106.在一些实施例中，步骤430可以包括步骤430-1和步骤430-2。步骤430-1基于贝叶斯信息准则，从多个起始点聚类结果确定最终起始点聚类结果。步骤430-2基于贝叶斯信息准则，从多个结束点聚类结果中确定最终结束点聚类结果。在一些实施例中，步骤430-1和步骤430-2可以由出入口确定模块230执行。
107.最终起始点聚类结果可以是特定聚类数目下的聚类结果，例如，特定聚类数目为3，最终起始点聚类结果指聚类数目为3的起始点簇。
108.最终结束点聚类结果可以指特定聚类数目下的聚类结果，例如，特定聚类数目为3，最终结束点聚类结果指聚类数目为3的结束点簇。
109.在一些实施例中，出入口确定模块230可以基于贝叶斯准则(bayesian information criterion，bic)从多个起始点聚类结果和多个结束点聚类结果中确定最终起始点聚类结果和最终结束点聚类结果。例如，出入口确定模块230通过贝叶斯信息准则从(k＝2、3、
…
、20)多个起始点聚类结果中选择出bic值最小的起始点聚类结果作为最终起始点聚类结果。又例如，出入口确定模块230通过贝叶斯信息准则从(k＝2、3、
…
、20)多个结束点聚类结果中选择出bic值最小的结束点聚类结果作为最终结束点聚类结果。
110.在步骤440中，可以基于最终起始点聚类结果和结束点聚类结果确定出入口点。
111.在一些实施例中，步骤440可以包括步骤440-1和步骤440-2。步骤440-1基于最终起始点聚类结果确定入口点。步骤440-2基于最终结束点聚类结果确定出口点。在一些实施例中，步骤440-1和步骤440-2可以由出入口确定模块230执行。
112.在一些实施例中，出入口确定模块230可以计算最终起始点聚类结果中各个起始点簇对应的簇中心，并将各个起始点簇对应的簇中心作为交叉口的入口点。在一些实施例中，出入口确定模块230可以确定各个起始点簇对应的簇中心之间的距离，将簇中心之间的距离满足一定的距离阈值的两个起始点簇进行合并得到合并后的起始点簇，计算合并后的起始点簇中各个起始点簇对应的簇中心，并将各个起始点簇对应的簇中心作为交叉口的入口点。例如，可以设定距离阈值为2米，将簇中心小于距离阈值2米的起始点簇进行合并，重新计算合并后的起始点簇的簇中心，确认是否存在和合并后的起始点簇的簇中心的距离阈
值小于2米的簇中心，如果存在，继续进行合并，重新进行计算，依次类推，直至不存在和多次合并后的起始点簇的簇中心的距离阈值小于2米的簇中心，将多次合并后的起始点簇的簇中心确定为入口点。
113.基于最终结束点聚类结果确定出口点的方式和基于最终起始点聚类结果确定入口点的方式类似，此处不再赘述。如图10所示，图10中包括道路交叉口的多个出口点和入口点。例如，区域1010和区域1020均包括4个出口点和入口点，区域1030包括一个出口点或者入口点。
114.在本说明书一些实施例中，通过高斯混合模型和贝叶斯信息准则构建自适应的软聚类算法确定道路交叉口入口点和出口点，可以减少由于噪声将邻近道路的轨迹段聚合到一起，降低聚类的错误率，可以提高提取道路交叉口的出口点和入口点的准确性。
115.图5是根据本说明书一些实施例所示的基于车辆轨迹数据获取道路交叉口的识别结果的示例性流程图。如图5所示，在一些实施例中，流程500可以包括步骤510、步骤520、步骤530、步骤540以及步骤550。
116.步骤510，确定车辆轨迹数据中的轨迹点对应的转角。在一些实施例中，步骤510可以由交叉口识别模块220执行。
117.轨迹点可以指车辆轨迹中的某一点。
118.轨迹点对应的转角可以指车辆轨迹中某一点车辆行驶方向改变的角度(即转向角)。
119.在一些实施例中，交叉口识别模块220可以按照一定的规则确定车辆轨迹数据中的轨迹点对应的转角。例如，可以将轨迹点前的车辆轨迹对应的运动矢量(或运动方向)和轨迹点后的车辆轨迹对应的运动矢量(或运动方向)之间的角确定为轨迹点对应的转角。
120.在一些实施例中，交叉口识别模块220可以对原始车辆轨迹数据中的每条轨迹进行插值处理以获得车辆轨迹数据。原始车辆轨迹数据可以是交叉口识别模块220直接从存储设备或其他数据源中获得的轨迹数据。原始车辆轨迹数据可以是交叉口识别模块220对从存储设备或其他数据源中获得的轨迹数据进行预处理后获得车辆轨迹数据。
121.在一些实施例中，交叉口识别模块220可以对原始车辆轨迹数据以一定间隔距离进行插值获得车辆轨迹数据。例如，插值可以设为间隔距离5米，交叉口识别模块220根据间隔距离5米对每条轨迹进行标记，每条轨迹上可以有多个间隔距离5米的标记点，每个标记点可以看成一个轨迹点。
122.在一些实施例中，交叉口识别模块220可以通过轨迹点与前后轨迹点的之间的方向关系确定该轨迹点对应的转角。例如，轨迹点a可以与在轨迹点a之前的第4个轨迹点a4之间形成由轨迹点a4指向轨迹点a的向量a，轨迹点a可以与在轨迹点a之后的第4个轨迹点a4’形成由轨迹点a指向轨迹点a4’的向量b，向量a和向量b的交点为轨迹点a，向量a和向量b的夹角为轨迹点a对应的转角。向量a以及向量b的方向可以分别表示轨迹点a与前后轨迹点a4和a4’的之间的方向关系。
123.本说明书一些实施例中，通过对车辆轨迹数据中的每条轨迹进行插值处理，将每条轨迹间隔一定距离(如5米)进行加密处理，避免由于前后轨迹点距离相差较大，导致确定轨迹点对应的转角不准确，通过插值处理可以便于确定轨迹点对应的转角。
124.步骤520，基于轨迹点对应的转角对轨迹点进行筛选以获取筛选后的轨迹点。在一
些实施例中，步骤520可以由交叉口识别模块220执行。
125.筛选后的轨迹点可以指满足一定阈值的轨迹点，例如，筛选后的轨迹点可以是轨迹点对应的转角大于一定角度阈值、轨迹点的热度值大于一定热度阈值等。
126.在一些实施例中，交叉口识别模块220可以基于轨迹点对应的转角大于一定角度阈值对轨迹点进行筛选，获取筛选后的轨迹点。例如，角度阈值为12
°
，轨迹点对应的转角大于角度阈值12
°
为筛选后的轨迹点。
127.在一些实施例中，交叉口识别模块220可以基于热点分析模型确定轨迹点的热度值，从轨迹点中剔除热度值小于一定热度阈值以及转角小于一定角度阈值的轨迹点以获得筛选后的轨迹点。
128.在一些实施例中，热点分析模型的输入可以包括轨迹点对应的转角。热点分析模型的输出可以包括轨迹点的热度值。轨迹点的热度值可以表示轨迹点位于道路交叉口范围内的可能性。轨迹点的热度值越大，表示轨迹点越有可能是位于道路交叉口范围内。
129.在一些实施例中，交叉口识别模块220可以将轨迹点对应的转角输入热点分析模型，热点分析模型输出轨迹点的热度值。
130.热度阈值可以指轨迹点为筛选后的轨迹点的最小热度值。例如，热度阈值可以是1.93、1.96、1.98等。角度阈值可以指轨迹点为筛选后的轨迹点的最小转角。例如，角度阈值可以是8
°
、10
°
、12
°
等。
131.在一些实施例中，交叉口识别模块220可以从轨迹点中剔除热度值小于一定热度阈值以获得热点，并将转角小于一定角度阈值的热点剔除以获得筛选后的热点(即轨迹点)。例如，热度阈值为1.96，角度阈值为10
°
，交叉口识别模块220可以剔除轨迹点的热度值小于1.96的轨迹点，然后再剔除轨迹点对应的转角小于10
°
的轨迹点，获得筛选后的轨迹点。
132.在本说明书一些实施例中，通过热点分析模型确定轨迹点的热度值，从轨迹点中剔除热度值小于一定热度阈值的轨迹点、转角小于角度阈值的轨迹点，将不太可能是道路交叉口范围内的轨迹点进行剔除，有利于剔除受噪声影响的轨迹点，可以提高筛选后的轨迹点的准确性。
133.步骤530，采用第三聚类模型对筛选后的轨迹点进行聚类以获得多个轨迹点簇。在一些实施例中，步骤530可以由交叉口识别模块220执行。
134.第三聚类模型可以指对筛选后的轨迹点进行聚类的模型。例如，自适应空间聚类模型(ascdt)、具有噪声的基于密度的聚类模型(dbscan)等。在一些实施例中，第三聚类模型的输入可以包括筛选后的轨迹点。第三聚类模型的输出可以包括多个轨迹点簇。
135.在一些实施例中，交叉口识别模块220可以通过自适应空间聚类模型获得多个轨迹点簇。例如，交叉口识别模块220可以将筛选后的轨迹点输入自适应空间聚类模型，自适应空间聚类模型输出多个轨迹点簇。在一些实施例中，交叉口识别模块220可以通过具有噪声的基于密度的聚类模型获得多个轨迹点簇。例如，交叉口识别模块220可以将筛选后的轨迹点输入具有噪声的基于密度的聚类模型，具有噪声的基于密度的聚类模型输出多个轨迹点簇。
136.步骤540，基于多个轨迹点簇中的轨迹点对应的转角对多个轨迹点簇进行筛选以获得筛选后的轨迹点簇。在一些实施例中，步骤540可以由交叉口识别模块220执行。
137.筛选后的轨迹点簇可以指满足一定阈值的轨迹点簇，例如，筛选后的轨迹点簇可以是轨迹点簇中的存在转角大于一定角度阈值的轨迹点、轨迹点簇中的转角大于一定角度阈值的轨迹点的个数大于一定个数阈值等。
138.在一些实施例中，交叉口识别模块220可以基于轨迹点簇中的轨迹点对应的转角大于一定角度阈值对多个轨迹点簇进行筛选，获取筛选后的轨迹点簇。例如，角度阈值为45
°
，轨迹点簇d中的轨迹点对应的转角大于角度阈值45
°
，将轨迹点簇d确定为筛选后的轨迹点簇的其中一个。
139.在一些实施例中，交叉口识别模块220可以对于多个轨迹点簇中每个轨迹点簇，确定每个轨迹点簇中的轨迹点的转角大于第一阈值的轨迹点个数，将轨迹点个数小于第二阈值的轨迹点簇去除以获得多个筛选后的轨迹点簇。第一阈值可以指角度阈值(如40
°
、45
°
、50
°
等)。第二阈值可以是个数阈值(如，3个、5个、6个等)。例如，假设第一阈值为45
°
，第二阈值为3个，轨迹点簇a中轨迹点的转角大于第一阈值45
°
的轨迹点个数为4个，轨迹点个数4个大于第二阈值3个，轨迹点簇a为筛选后的轨迹点簇中的一个；轨迹点簇b中轨迹点的转角大于第一阈值45
°
的轨迹点个数为2个，轨迹点个数2个小于第二阈值3个，去除轨迹点簇b；轨迹点簇c中轨迹点的转角大于第一阈值45
°
的轨迹点个数为5个，轨迹点个数5个大于第二阈值3个，轨迹点簇c为筛选后的轨迹点簇中的一个。以此类推，交叉口识别模块220可以将多个轨迹点簇中的每个轨迹点簇进行确定，获得多个筛选后的轨迹点簇。
140.步骤550，基于筛选后的轨迹点簇确定道路交叉口的识别结果。在一些实施例中，步骤550可以由交叉口识别模块220执行。
141.在一些实施例中，交叉口识别模块220可以基于筛选后的轨迹点簇确定道路交叉口的识别结果。例如，交叉口识别模块220可以确定筛选后的轨迹点簇的包围圆，将包围圆所在位置确定为道路交叉口的位置和范围。又例如，交叉口识别模块220可以对重叠的包围圆进行合并，将合并后的包围圆所在位置确定为道路交叉口的位置和范围。
142.在一些实施例中，交叉口识别模块220可以对包围圆(或者合并后的包围圆)进行扩展(即增加一定的缓冲范围(例如，15米))并确定扩展后的包围圆是否重叠。若扩展后的包围圆存在重叠，则进一步合并重叠的包围圆，将合并后的包围圆确定为道路交叉口所在的位置和范围；若扩展后的包围圆不重叠，则直接将扩展后的包围圆确定为道路交叉口所在的位置和范围。
143.在一些实施例中，交叉口识别模块220可以确定筛选后的轨迹点簇对应的多个包围圆，对于多个包围圆中的任意一个包围圆，基于包围圆与其他包围圆之间的最小距离确定包围圆的缓冲区范围。交叉口识别模块220基于包围圆与包围圆的缓冲区范围确定道路交叉口的识别结果。
144.包围圆指可以将轨迹点簇中的每个轨迹点都包含在内的一个最小的圆。例如，如上所述的轨迹点簇a对应的包围圆可以将轨迹点簇a中的轨迹点都包含在包围圆里面。每个筛选后的轨迹点簇可以对应一个包围圆。在一些实施例中，每个筛选后的轨迹点簇对应的包围圆的大小可以相同或者不同，根据筛选后的轨迹点簇的情况进行确定。例如，轨迹点簇的轨迹点比较密集，轨迹点簇对应的包围圆可能小一些，轨迹点簇的轨迹点比较分散，轨迹点簇对应的包围圆可能大一些。
145.在一些实施例中，交叉口识别模块220可以通过多次计算得到一个轨迹点簇对应
的多个包围圆，通过比较、识别可以将轨迹点簇中的每个轨迹点都包含的最小的包围圆，将最小的包围圆确定为筛选后的轨迹点簇对应的包围圆。在一些实施例中，如果相邻的包围圆有重叠时，可以将包围圆进行合并，获取新的包围圆。例如，如上述所述的轨迹点簇a对应的包围圆和轨迹点簇c对应的包围圆有部分重叠，可以将轨迹点簇a和b对应的包围圆进行合并，获取新的包围圆。
146.包围圆的缓冲区范围可以指对包围圆进行扩大的范围。例如，在包围圆的周围添加10米、15米、30米等的缓冲区范围。
147.在一些实施例中，交叉口识别模块220可以基于包围圆与其他包围圆之间的最小距离确定包围圆的缓冲区范围。两个包围圆之间的最小距离可以指的是两个包围圆中心的连线的长度减去连线处于两个包围圆范围内的长度。两个包围圆之间的最小距离越小，两个包围圆对应的缓冲区范围越小。在一些实施例中，缓冲区范围可以小于两个包围圆的最小距离的一半，从而使得两个包围圆在进行扩展后不重叠。例如，包围圆的缓冲区范围可以为包围圆与其他包围圆之间的最小距离的1/3(示例性性的，包围圆与其他包围圆之间的最小距离为90米，包围圆的缓冲区范围为30米)。在一些实施例中，如果相邻的包围圆的缓冲区范围有重叠时，可以将包围圆的缓冲区范围进行合并，获取新的包围圆的缓冲区范围。例如，包围圆的缓冲区范围1和包围圆的缓冲区范围2有部分重叠，可以将缓冲区范围1和2进行合并，获取新的包围圆的缓冲区范围，直到每个包围圆的缓冲区范围无重叠。在一些实施例中，交叉口识别模块220可以基于包围圆与包围圆的缓冲区范围确定道路交叉口的识别结果。
148.在本说明书一些实施例中，通过包围圆与其他包围圆之间的最小距离确定包围圆的缓冲区范围，通过自适应来确定包围圆的缓冲区范围，可以更好的获取道路交口的范围，进而确定道路交叉口的识别结果，可以提高道路交叉口识别结果的准确性。
149.在本说明书一些实施例中，通过自适应空间聚类模型对筛选后的轨迹点进行聚类，可以提高对轨迹点聚类的准确性，进而可以提高道路交叉口识别结果的准确性。
150.图6是根据本说明书一些实施例所示的确定道路交叉口的道路拓扑的示例性流程图。如图6所示，在一些实施例中，流程600可以包括步骤610、步骤620、步骤630、以及步骤640。
151.步骤610，基于入口点、出口点以及位于道路交叉口的范围内的车辆轨迹段确定连接相同出口点和入口点的轨迹集合。在一些实施例中，步骤610可以由拓扑结构生成模块240执行。关于道路交叉口的出口点和入口点的提取的更多描述可以参考本技术其他部分的详细描述，例如，图4及其描述。
152.在一些实施例中，拓扑结构生成模块240可以基于入口点的车辆轨迹段集合和出口点的车辆轨迹段集合是否有交集确定连接相同出口点和入口点的轨迹集合。例如，假设每个出口点或入口点经过的车辆轨迹段集合为tr＝{tr1,tr2,
……
,trn}。在同一个道路交叉口，连接入口点1的车辆轨迹段集合为trs1，连接出口点1的车辆轨迹段集合为trs2，如果trs1和trs2有交集，表示有车辆轨迹段同时经过入口点1和出口点1，该道路交叉口中存在从入口点1到出口点1的可通行内部道路。将trs1和trs2相同的车辆轨迹段(即交集)确定为连接相同出口点和入口点的轨迹集合。通过上述方法，可以确定每个道路交叉口的连接相同出口点和入口点的轨迹集合。在一些实施例中，拓扑结构生成模块240可以遍历位于同一
道路交叉口的车辆轨迹，以确定每个车辆轨迹对应的入口点和出口点，以确定连接相同出口点和入口点的轨迹集合。
153.步骤620，从轨迹集合中确定参考轨迹。在一些实施例中，步骤620可以由拓扑结构生成模块240执行。
154.在一些实施例中，同一道路交叉口可能对应多个连接相同出口点和入口点的轨迹集合。每个轨迹集合中的轨迹具有相同的入口点和出口点；不同轨迹集合中的轨迹具有不同的入口点和/或出口点。拓扑结构生成模块240可以确定每个轨迹集合的参考轨迹。在一些实施例中，同一道路交叉口可能对应一个连接相同出口点和入口点的轨迹集合。拓扑结构生成模块240可以确定该轨迹集合的参考轨迹。
155.参考轨迹可以是距离其他轨迹距离总和最小的轨迹、轨迹集合中位置处于中间的轨迹等。
156.在一些实施例中，拓扑结构生成模块240可以确定轨迹集合中各个轨迹间的距离，选择轨迹集合中距离其他轨迹距离总和最小的轨迹作为参考轨迹。例如，各个轨迹间的距离可以为hausdorff距离，通过计算轨迹集合中各个轨迹间的hausdorff距离，可以确定轨迹集合中各个轨迹距离其他轨迹的距离总和，选择轨迹集合中距离其他轨迹距离总和最小的轨迹作为参考轨迹。关于hausdorff距离的计算方法可以参见图3的相关说明，此处不再赘述。
157.步骤630，基于参考轨迹的特征参数确定中心线拟合模型。在一些实施例中，步骤630可以由拓扑结构生成模块240执行。
158.参考轨迹的特征参数指可以表示参考轨迹的形态的参数，例如，参考轨迹的曲率(例如，最大曲率、平均曲率)、参考轨迹的长度与参考轨迹在道路交叉口范围内的起始点和结束点之间的距离之间的比值、参考轨迹在道路交叉口范围内的起始点和结束点之间连线与起始点或结束点处切线之间的夹角等。
159.中心线拟合模型可以指对轨迹集合中的轨迹线进行拟合的模型。在一些实施例中，中心线拟合模型可以包括b样条拟合模型、k段主曲线拟合模型等。中心线拟合模型的输入可以包括轨迹集合，中心线拟合模型的输出可以包括连接相同出口点和入口点的道路拓扑。
160.在一些实施例中，拓扑结构生成模块240可以基于参考轨迹的特征参数确定中心线拟合模型。例如，拓扑结构生成模块240可以比较参考轨迹的特征参数与特征参数对应的阈值，若是特征参数小于一定阈值，则确定所述中心线拟合模型包括b样条拟合模型；或者若特征参数大于一定阈值，则确定所述中心线拟合模型包括k段主曲线拟合模型。
161.例如，参考轨迹的特征参数可以包括参考轨迹的长度与参考轨迹在道路交叉口范围内的起始点和结束点之间的距离之间的比值。比值阈值可以是1.1、1.2、1.3等。如果比值小于一定比值阈值(如，1.2)，则确定中心线拟合模型包括b样条拟合模型；或者如果比值大于一定比值阈值(如，1.2)，则确定中心线拟合模型包括k段主曲线拟合模型。
162.在本说明书一些实施例中，通过参考轨迹的特征参数选择不同的中心线拟合模型，较直的轨迹线(比值较小)用b样条拟合效果更好，而弯曲的轨迹线(比值较大)，例如，自相交的轨迹线，k段主曲线拟合模型拟合效果更好，因此根据参考轨迹的特征参数选择不同的中心线拟合模型，实现了不同的中心线拟合模型的优势，可以提高对轨迹集合中的轨迹
线拟合的效果。
163.步骤640，基于中心线拟合模型对轨迹集合中的轨迹线进行中心线拟合以生成连接相同出口点和入口点的道路拓扑。在一些实施例中，步骤640可以由拓扑结构生成模块240执行。
164.在一些实施例中，拓扑结构生成模块240基于中心线拟合模型对轨迹集合中的轨迹线进行中心线拟合以生成连接相同出口点和入口点的道路拓扑。例如，对道路交叉口每一个连接相同入口点和出口点的轨迹集合进行步骤620-640，生成道路交叉口的道路拓扑，如图1所示的道路交叉口的道路拓扑结构140。
165.在本说明书一些实施例中，通过中心线拟合模型对轨迹集合中的轨迹线进行中心线拟合以生成连接相同出口点和入口点的道路拓扑，可以提高道路拓扑的准确性。
166.应当注意的是，上述有关流程的描述仅仅是为了示例和说明，而不限定本说明书的适用范围。对于本领域技术人员来说，在本说明书的指导下可以对流程上述进行各种修正和改变。然而，这些修正和改变仍在本说明书的范围之内。
167.上文已对基本概念做了描述，显然，对于本领域技术人员来说，上述详细披露仅仅作为示例，而并不构成对本说明书的限定。虽然此处并没有明确说明，本领域技术人员可能会对本说明书进行各种修改、改进和修正。该类修改、改进和修正在本说明书中被建议，所以该类修改、改进、修正仍属于本说明书示范实施例的精神和范围。
168.同时，本说明书使用了特定词语来描述本说明书的实施例。如“一个实施例”、“一实施例”、和/或“一些实施例”意指与本说明书至少一个实施例相关的某一特征、结构或特点。因此，应强调并注意的是，本说明书中在不同位置两次或多次提及的“一实施例”或“一个实施例”或“一个替代性实施例”并不一定是指同一实施例。此外，本说明书的一个或多个实施例中的某些特征、结构或特点可以进行适当的组合。
169.此外，除非权利要求中明确说明，本说明书所述处理元素和序列的顺序、数字字母的使用、或其他名称的使用，并非用于限定本说明书流程和方法的顺序。尽管上述披露中通过各种示例讨论了一些目前认为有用的发明实施例，但应当理解的是，该类细节仅起到说明的目的，附加的权利要求并不仅限于披露的实施例，相反，权利要求旨在覆盖所有符合本说明书实施例实质和范围的修正和等价组合。例如，虽然以上所描述的系统组件可以通过硬件设备实现，但是也可以只通过软件的解决方案得以实现，如在现有的服务器或移动设备上安装所描述的系统。
170.同理，应当注意的是，为了简化本说明书披露的表述，从而帮助对一个或多个发明实施例的理解，前文对本说明书实施例的描述中，有时会将多种特征归并至一个实施例、附图或对其的描述中。但是，这种披露方法并不意味着本说明书对象所需要的特征比权利要求中提及的特征多。实际上，实施例的特征要少于上述披露的单个实施例的全部特征。
171.一些实施例中使用了描述成分、属性数量的数字，应当理解的是，此类用于实施例描述的数字，在一些示例中使用了修饰词“大约”、“近似”或“大体上”来修饰。除非另外说明，“大约”、“近似”或“大体上”表明所述数字允许有
±
20％的变化。相应地，在一些实施例中，说明书和权利要求中使用的数值参数均为近似值，该近似值根据个别实施例所需特点可以发生改变。在一些实施例中，数值参数应考虑规定的有效数位并采用一般位数保留的方法。尽管本说明书一些实施例中用于确认其范围广度的数值域和参数为近似值，在具体
实施例中，此类数值的设定在可行范围内尽可能精确。
172.针对本说明书引用的每个专利、专利申请、专利申请公开物和其他材料，如文章、书籍、说明书、出版物、文档等，特此将其全部内容并入本说明书作为参考。与本说明书内容不一致或产生冲突的申请历史文件除外，对本说明书权利要求最广范围有限制的文件(当前或之后附加于本说明书中的)也除外。需要说明的是，如果本说明书附属材料中的描述、定义、和/或术语的使用与本说明书所述内容有不一致或冲突的地方，以本说明书的描述、定义和/或术语的使用为准。
173.最后，应当理解的是，本说明书中所述实施例仅用以说明本说明书实施例的原则。其他的变形也可能属于本说明书的范围。因此，作为示例而非限制，本说明书实施例的替代配置可视为与本说明书的教导一致。相应地，本说明书的实施例不仅限于本说明书明确介绍和描述的实施例。

技术特征：
1.一种用于道路交叉口拓扑结构生成的方法，其特征在于，包括：获取车辆轨迹数据；基于所述车辆轨迹数据获取道路交叉口的识别结果，所述识别结果包括所述道路交叉口的位置与范围；基于第一聚类模型对位于同一个道路交叉口范围内的车辆轨迹段进行聚类以获得初始轨迹聚类结果；基于第二聚类模型从所述初始轨迹聚类结果中提取所述道路交叉口的出口点以及入口点；以及基于所述出口点以及所述入口点，确定所述道路交叉口的道路拓扑。2.根据权利要求1所述的方法，其特征在于，所述第一聚类模型包括基于密度的聚类模型，以及所述基于第一聚类模型对所述道路交叉口范围内的车辆轨迹段进行聚类以获得初始轨迹聚类结果包括：确定所述车辆轨迹段的轨迹差异，所述轨迹差异表示任意两个轨迹段之间的差异；以及基于所述轨迹差异，利用所述基于密度的聚类模型获得所述初始轨迹聚类结果，其中所述任意两个轨迹段之间的差异包括轨迹距离差异或轨迹方向差异中的至少一个。3.根据权利要求1所述的方法，其特征在于，所述第二聚类模型包括高斯混合模型，所述基于第二聚类模型从所述初始轨迹聚类结果中提取所述道路交叉口的出入口点包括：对于所述初始轨迹聚类结果中的每个轨迹聚类结果，提取所述轨迹聚类结果中的轨迹段的起始点以及结束点以获得起始点集合和结束点集合；采用所述高斯混合模型，在不同聚类数目条件下，分别对所述起始点集合和所述结束点集合内的点进行聚类以确定多个起始点聚类结果和多个结束点聚类结果，每个起始点聚类结果包括在特定聚类数目下的起始点簇，每个结束点聚类结果包括在特定聚类数目下的结束点簇；基于贝叶斯信息准则，从所述多个起始点聚类结果和多个结束点聚类结果中确定最终起始点聚类结果和最终结束点聚类结果；以及分别基于所述最终起始点聚类结果和所述最终结束点聚类结果确定所述入口点以及所述出口点。4.根据权利要求1所述的方法，其特征在于，所述基于所述车辆轨迹数据获取道路交叉口的识别结果包括：确定所述车辆轨迹数据中的轨迹点对应的转角；基于所述轨迹点对应的转角对所述轨迹点进行筛选以获取筛选后的轨迹点；采用第三聚类模型对所述筛选后的轨迹点进行聚类以获得多个轨迹点簇；基于所述多个轨迹点簇中的轨迹点对应的转角对所述多个轨迹点簇进行筛选以获得筛选后的轨迹点簇；以及基于所述筛选后的轨迹点簇确定所述道路交叉口的识别结果。5.根据权利要求4所述的方法，其特征在于，所述基于所述筛选后的轨迹点簇确定所述道路交叉口的识别结果包括：
确定所述筛选后的轨迹点簇对应的多个包围圆；对于所述多个包围圆中的任意一个包围圆，基于所述包围圆与其他包围圆之间的最小距离确定所述包围圆的缓冲区范围；以及基于所述包围圆与所述包围圆的缓冲区范围确定所述道路交叉口的识别结果。6.根据权利要求4所述的方法，其特征在于，所述基于所述轨迹点对应的转角对所述轨迹点进行筛选以获取筛选后的轨迹点包括：基于热点分析模型确定所述轨迹点的热度值；以及从所述轨迹点中剔除热度值小于一定热度阈值以及转角小于一定角度阈值的轨迹点以获得所述筛选后的轨迹点。7.根据权利要求1所述的方法，其特征在于，所述基于所述入口点、所述出口点以及位于所述道路交叉口的范围内的车辆轨迹段，确定所述道路交叉口的道路拓扑包括：基于所述入口点、所述出口点以及位于所述道路交叉口的范围内的车辆轨迹段确定连接相同出口点和入口点的轨迹集合；从所述轨迹集合中确定参考轨迹；基于所述参考轨迹的特征参数确定中心线拟合模型；以及基于所述中心线拟合模型对所述轨迹集合中的轨迹线进行中心线拟合以生成连接所述相同出口点和入口点的道路拓扑。8.根据权利要求7所述的方法，其特征在于，所述参考轨迹的特征参数包括所述参考轨迹的长度与所述参考轨迹在所述道路交叉口范围内的起始点和结束点之间的距离之间的比值，以及所述基于所述参考轨迹的特征参数确定中心线拟合模型包括：若所述比值小于一定比值阈值，则确定所述中心线拟合模型包括b样条拟合模型；或者若所述比值大于一定比值阈值，则确定所述中心线拟合模型包括k段主曲线拟合模型。9.一种用于道路交叉口拓扑结构生成的装置，其特征在于，所述装置包括至少一个处理器和至少一个存储器，至少一个所述存储器中存储有程序指令，至少一个所述处理器读取所述程序指令后执行权利要求1-8任一项所述的用于道路交叉口拓扑结构生成方法。10.一种存储介质，其特征在于，所述存储介质中存储有程序指令，计算机读取所述程序指令后执行权利要求1-8任一项所述的用于道路交叉口拓扑结构生成方法。

技术总结
本说明书实施例提供一种用于道路交叉口拓扑结构生成的方法和装置，该方法包括：获取车辆轨迹数据；基于车辆轨迹数据获取道路交叉口的识别结果，识别结果包括道路交叉口的位置与范围；基于第一聚类模型对位于同一个道路交叉口范围内的车辆轨迹段进行聚类以获得初始轨迹聚类结果；基于第二聚类模型从初始轨迹聚类结果中提取道路交叉口的出口点以及入口点；以及基于出口点以及入口点，确定道路交叉口的道路拓扑。道路拓扑。道路拓扑。


技术研发人员：刘国平 车林 温翔 马楠 胡润波
受保护的技术使用者：北京嘀嘀无限科技发展有限公司
技术研发日：2021.12.23
技术公布日：2023/7/4