WO2021212294A1

WO2021212294A1 - Systems and methods for determining a two-dimensional map

Info

Publication number: WO2021212294A1
Application number: PCT/CN2020/085757
Authority: WO
Inventors: Minkang WANG; Fei Wang
Original assignee: Beijing Didi Infinity Technology And Development Co., Ltd.
Priority date: 2020-04-21
Filing date: 2020-04-21
Publication date: 2021-10-28
Also published as: CN112889041A; CN112889041B

Abstract

A system (100) and method for determining a two-dimensional map. The method may include obtaining a pose graph of a region. The pose graph may include a plurality of route-tracking datasets in the region. Each route-tracking dataset may include a plurality of nodes (710, 720). The method may also include determining at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets. At least two of the plurality of route-tracking datasets may overlap at one of the at least one overlapped sub-region and the at least two of the plurality of route-tracking datasets may satisfy a condition. Further, the method may include determining a plurality of layers of roads in the region based on the at least one overlapped sub-region. The method may also include determining a target map based on the plurality of layers of roads and the pose graph.

Description

SYSTEMS AND METHODS FOR DETERMINING A TWO-DIMENSIONAL MAP

TECHNICAL FIELD

The present disclosure generally relates to systems and methods for determining a two-dimensional (2D) map, and in particular, to systems and methods for determining the 2D map based on a pose graph and route-tracking datasets.

BACKGROUND

With the development of advanced driving assistance systems (ADASs) and intelligent driving technologies, high-definition maps, as an important part thereof, have received more and more attention. In some cases, semantic information of the high-definition map is generated based on a three-dimensional (3D) map, which is time-consuming since map data of the 3D map is massive. In some cases, semantic information of the high-definition map is generated based on a two-dimensional (2D) map, which costs less time but at the prices of discarding a portion of the semantic information of the high definition map. Take an overlapped region, e.g., an overpass associated with an upper layer of road and a lower layer of road, as an example, the 2D map includes either map data of the upper layer of road or map data of the lower layer of road, but not both. Accordingly, semantic information for the upper layer of road or the lower layer of road is unlikely to be generated based on the 2D map. Therefore, it is desirable to provide systems and methods for determining a 2D map with map data of all layers of roads in overlapped regions.

SUMMARY

In one aspect of the present disclosure, a system for determining a two-dimensional map is provided. The system may include at least one storage medium and at least one processor in communication with the at least one storage medium. The at least one storage medium may include a set of instructions. When executing the set of instructions, the at least one processor may be directed to obtain a pose graph of a region. The pose graph may include a plurality of route-tracking datasets in the region. Each of the plurality of route-tracking datasets may include a plurality of nodes. The at least one processor may also be directed to determine at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region. At least two of the plurality of route-tracking datasets may overlap at one of the at least one overlapped sub-region and the at least two of the plurality of route-tracking datasets may satisfy a condition. The at least one processor may also be directed to determine a plurality of layers of roads in the region based on the at least one overlapped sub-region. The at least one processor may also be directed to determine a target map based on the plurality of layers of roads and the pose graph.

In some embodiments, wherein to determine that the at least two of the plurality of route-tracking datasets satisfy the condition, the at least one processor may be directed to determine whether a height difference between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two of the plurality of route-tracking datasets is greater than a threshold. In response to a determination that the height difference is greater than the threshold, the at least one processor may be directed to determine that the at least two of the plurality of route-tracking datasets satisfy the condition.

In some embodiments, wherein to determine that the at least two of the plurality of route-tracking datasets satisfy the condition, the at least one processor may be directed to determine whether a geometric match degree between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two of the plurality of route-tracking datasets is smaller than a threshold. In response to a determination that the geometric match degree is smaller than the threshold, the at least one processor may also be directed to determine that the at least two of the plurality of route-tracking datasets satisfy the condition.

In some embodiments, wherein to determine the at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region, the at least one processor may be directed to determine whether more than one of the plurality of route-tracking datasets belongs to a same road based on text information. In response to a determination that the more than one of the plurality of route-tracking datasets belongs to the same road, the at least one processor may be directed to keep one of the more than one of the plurality route-tracking datasets.

In some embodiments, wherein to determine the plurality of layers of roads in the region based on the at least one overlapped sub-region, the at least one of processor may be directed to, for each of the at least one overlapped sub-region, classify at least a portion of the plurality of nodes into a plurality of groups. The plurality of groups may correspond to the plurality of layers of roads. The at least one processor may also be directed to determine an area containing the at least a portion of the plurality nodes in each of the plurality of groups. The at least one processor may also be directed to determine a boundary of each of the plurality of layers of roads based on the areas.

In some embodiments, wherein to determine the boundary of each of the plurality of layers of roads based on the areas, the at least one processor may be directed to expand a portion of the areas. The at least one processor may also be directed to determine the boundary of each of the plurality of layers of roads based on the expanded areas.

In some embodiments, wherein to expand the portion of the areas, the at least one of processor may be directed to determine a bounding box corresponding to each of the plurality of nodes. The at least one processor may also be directed to determine whether an overlapped degree between any two corresponding bounding boxes of the bounding box located within a neighboring area and the area, respectively, is greater than a threshold. In response to a determination that the overlapped degree is greater than the threshold, the at least one processor may also be directed to expand the area by including the node located in the neighboring area to the area.

In some embodiments, wherein to determine the target map based on the pose graph, the at least one of processor may be directed to determine a sub map for each of the plurality of layers of roads based on the pose graph. The at least one processor may also be directed to determine the target map based on the sub maps.

In some embodiments, the at least one overlapped sub-region may correspond to at least one of: an interchange, an overpass, or a viaduct.

In some embodiments, the region may also include one or more sub-regions other than the at least one overlapped sub-region. The at least one processor may be further directed to determine the one or more sub-regions other than the at least one overlapped sub-region as one of the plurality of layers of roads based on the sub-regions.

In another aspect of the present disclosure, a method for determining a two-dimensional map is provided. The method may be implemented on a computing device having at least one processor, at least one storage medium, and a communication platform connected to a network. The method may include obtaining a pose graph of a region. The pose graph may include a plurality of route-tracking datasets in the region. Each of the plurality of route-tracking datasets may include a plurality of nodes. The method may also include determining at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region. At least two of the plurality of route-tracking datasets may overlap at one of the at least one overlapped sub-region and the at least two of the plurality of route-tracking datasets may satisfy a condition. The method may also include determining a plurality of layers of roads in the region based on the at least one overlapped sub-region. The method may also include determining a target map based on the plurality of layers of roads and the pose graph.

In some embodiments, the method may also include determining whether a height difference between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two of the plurality of route-tracking datasets is greater than a threshold. In response to a determination that the height difference is greater than the threshold, the method may also include determining that the at least two of the plurality of route-tracking datasets satisfy the condition.

In some embodiments, the method may also include determining whether a geometric match degree between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two of the plurality of route-tracking datasets is smaller than a threshold. In response to a determination that the geometric match degree is smaller than the threshold, the method may also include determining that the at least two of the plurality of route-tracking datasets satisfy the condition.

In some embodiments, the method may also include determining whether more than one of the plurality of route-tracking datasets belongs to a same road based on text information. In response to a determination that the more than one of the plurality of route-tracking datasets belongs to the same road, the method may also include keeping one of the more than one of the plurality route-tracking datasets.

In some embodiments, the method may also include, for each of the at least one overlapped sub-region, classifying at least a portion of the plurality of nodes into a plurality of groups. The plurality of groups may correspond to the plurality of layers of roads. The method may also include determining an area containing the at least a portion of the plurality nodes in each of the plurality of groups. The method may also include determining a boundary of each of the plurality of layers of roads based on the areas.

In some embodiments, the method may also include expanding a portion of the areas. The method may also include determining the boundary of each of the plurality of layers of roads based on the expanded areas.

In some embodiments, the method may also include determining a bounding box corresponding to each of the plurality of nodes. The method may also include determining whether an overlapped degree between any two corresponding bounding boxes of the bounding box located within a neighboring area and the area, respectively, is greater than a threshold. In response to a determination that the overlapped degree is greater than the threshold, the method may include expanding the area by including the node located in the neighboring area to the area.

In some embodiments, the method may include determining a sub map for each of the plurality of layers of roads based on the pose graph. The method may also include determining the target map based on the sub maps.

In some embodiments, the region may also include one or more sub-regions other than the at least one overlapped sub-region. The method may include determining the one or more sub-regions other than the at least one overlapped sub-region as one of the plurality of layers of roads based on the sub-regions.

In another aspect of the present disclosure, a non-transitory computer readable medium for determining a target position of a target subject is provided. The non-transitory computer readable medium, including executable instructions that, when executed by at least one processor, may direct the at least one processor to perform a method. The method may include obtaining a pose graph of a region. The pose graph may include a plurality of route-tracking datasets in the region. Each of the plurality of route-tracking datasets may include a plurality of nodes. The method may also include determining at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region. At least two of the plurality of route-tracking datasets may overlap at one of the at least one overlapped sub-region and the at least two of the plurality of route-tracking datasets may satisfy a condition. The method may also include determining a plurality of layers of roads in the region based on the at least one overlapped sub-region. The method may also include determining a target map based on the plurality of layers of roads and the pose graph.

Additional features will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following and the accompanying drawings or may be learned by production or operation of the examples. The features of the present disclosure may be realized and attained by practice or use of various aspects of the methodologies, instrumentalities, and combinations set forth in the detailed examples discussed below.

BRIEF DESCRIPTION OF THE DRAWINGS

The present disclosure is further described in terms of exemplary embodiments. These exemplary embodiments are described in detail with reference to the drawings. These embodiments are non-limiting exemplary embodiments, in which like reference numerals represent similar structures throughout the several views of the drawings, and wherein:

FIG. 1 is a schematic diagram illustrating an exemplary mapping system according to some embodiments of the present disclosure;

FIG. 2 is a schematic diagram illustrating exemplary hardware and/or software components of a computing device according to some embodiments of the present disclosure;

FIG. 3 is a schematic diagram illustrating exemplary hardware and/or software components of a mobile device according to some embodiments of the present disclosure;

FIG. 4 is a block diagram illustrating an exemplary processing engine according to some embodiments of the present disclosure;

FIG. 5 is a flowchart illustrating an exemplary process for determining a target map based on route-tracking datasets and a pose graph according to some embodiments of the present disclosure;

FIG. 6 is a flowchart illustrating an exemplary process for determining boundaries of layers of roads according to some embodiments of the present disclosure; and

FIG. 7 is a schematic diagram illustrating an exemplary overlapped sub-region according to some embodiments of the present disclosure.

DETAILED DESCRIPTION

The following description is presented to enable any person skilled in the art to make and use the present disclosure and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present disclosure. Thus, the present disclosure is not limited to the embodiments shown but is to be accorded the widest scope consistent with the claims.

The terminology used herein is for the purpose of describing particular example embodiments only and is not intended to be limiting. As used herein, the singular forms “a, ” “an, ” and “the” may be intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprise, ” “comprises, ” and/or “comprising, ” “include, ” “includes, ” and/or “including, ” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

These and other features, and characteristics of the present disclosure, as well as the methods of operation and functions of the related elements of structure and the combination of parts and economies of manufacture, may become more apparent upon consideration of the following description with reference to the accompanying drawings, all of which form a part of this disclosure. It is to be expressly understood, however, that the drawings are for the purpose of illustration and description only and are not intended to limit the scope of the present disclosure. It is understood that the drawings are not to scale.

The flowcharts used in the present disclosure illustrate operations that systems implement according to some embodiments of the present disclosure. It is to be expressly understood, the operations of the flowchart may be implemented not in order. Conversely, the operations may be implemented in inverted order, or simultaneously. Moreover, one or more other operations may be added to the flowcharts. One or more operations may be removed from the flowcharts.

An aspect of the present disclosure relates to systems and methods for determining a two-dimensional (2D) map. The system may determine at least one overlapped sub-region based on a pose graph of a region and a plurality of route-tracking datasets in the region. As used herein, the overlapped sub-region may be associated with a grade separation structure (e.g., overpass, underpass, interchange, viaduct) , which is a junction of a plurality of layers of roads at different heights (or grades) . For illustration purposes, the system may determine the at least one overlapped sub-region based on height differences associated with the plurality of route-tracking datasets, geometric match degrees associated with the plurality of route-tracking datasets, text information associated with the plurality of route-tracking datasets, or the like, or any combination thereof. The system may determine a plurality of layers of roads in the region based at least on the at least one overlapped sub-region. For illustration purposes, the plurality of layers of roads in the region may at least include the plurality of layers of roads in each of the at least one overlapped sub-region. Further, the system may determine the 2D map including map data of the plurality of layers of roads in the region at least based on the pose graph.

In the present disclosure, the 2D map may include the map data of the plurality of layers of roads, which may symbolically display or represent the grade separation structure (s) in the region more accurately than a current 2D map only including map data of one of the plurality of layers of roads with respect to each of the grade separation structures.

FIG. 1 is a schematic diagram illustrating an exemplary mapping system 100 according to some embodiments of the present disclosure. In some embodiments, the mapping system 100 may include a server 110, a storage device 120, a network 130, one or more terminal devices 140, and one or more positioning devices 150.

In some embodiments, the server 110 may be a single server or a server group. The server group may be centralized or distributed (e.g., the server 110 may be a distributed system) . In some embodiments, the server 110 may be local or remote. For example, the server 110 may access information and/or data stored in the storage device 120, the terminal device (s) 140, the positioning device (s) 150, etc., via the network 130. As another example, the server 110 may be directly connected to the storage device 120, the terminal device (s) 140, the positioning device (s) 150, etc., to access stored information and/or data. In some embodiments, the server 110 may be implemented on a cloud platform or an onboard computer. Merely by way of example, the cloud platform may include a private cloud, a public cloud, a hybrid cloud, a community cloud, a distributed cloud, an inter-cloud, a multi-cloud, or the like, or any combination thereof. In some embodiments, the server 110 may be implemented on a computing device 200 having one or more components illustrated in FIG. 2 in the present disclosure.

In some embodiments, the server 110 may include a processing engine 112. The processing engine 112 may process information and/or data associated with the mapping system 100 to perform one or more functions described in the present disclosure. For example, the processing engine 112 may obtain a pose graph of a region. As another example, the processing engine 112 may determine at least one overlapped sub-region included in a region based on a pose graph of the region and a plurality of route-tracking datasets in the region. In some embodiments, the processing engine 112 may include one or more processing engines (e.g., single-core processing engine (s) or multi-core processor (s) ) . Merely by way of example, the processing engine 112 may include a central processing unit (CPU) , an application-specific integrated circuit (ASIC) , an application-specific instruction-set processor (ASIP) , a graphics processing unit (GPU) , a physics processing unit (PPU) , a digital signal processor (DSP) , a field-programmable gate array (FPGA) , a programmable logic device (PLD) , a controller, a microcontroller unit, a reduced instruction-set computer (RISC) , a microprocessor, or the like, or any combination thereof.

In some embodiments, the server 110 may be connected to the network 130 to communicate with one or more components (e.g., the storage device 120, the terminal device (s) 140, the positioning device (s) 150) of the mapping system 100. In some embodiments, the server 110 may be directly connected to or communicate with one or more components (e.g., the storage device 120, the terminal device (s) 140, the positioning device (s) 150) of the mapping system 100.

The storage device 120 may store data and/or instructions. In some embodiments, the storage device 120 may store data obtained from the storage device 120, the terminal device (s) 140, the positioning device (s) 150, an external storage device, etc. For example, the storage device 120 may store a pose graph of a region. As another example, the storage device 120 may store a target map determined based on a plurality of layers of roads and a pose graph. In some embodiments, the storage device 120 may store data and/or instructions that the server 110 may execute or use to perform exemplary methods described in the present disclosure. For example, the storage device 120 may store instructions that the mapping system 100 may execute or use to obtain a pose graph of a region. As another example, the storage device 120 may store instructions that the mapping system 100 may execute or use to determine a target map based on a plurality of layers of roads and a pose graph.

In some embodiments, the storage device 120 may include a mass storage, a removable storage, a volatile read-and-write memory, a read-only memory (ROM) , or the like, or any combination thereof. Exemplary mass storage may include a magnetic disk, an optical disk, a solid-state drive, etc. Exemplary removable storage may include a flash drive, a floppy disk, an optical disk, a memory card, a zip disk, a magnetic tape, etc. Exemplary volatile read-and-write memory may include a random access memory (RAM) . Exemplary RAM may include a dynamic RAM (DRAM) , a double date rate synchronous dynamic RAM (DDR SDRAM) , a static RAM (SRAM) , a thyristor RAM (T-RAM) , and a zero-capacitor RAM (Z-RAM) , etc. Exemplary ROM may include a mask ROM (MROM) , a programmable ROM (PROM) , an erasable programmable ROM (EPROM) , an electrically-erasable programmable ROM (EEPROM) , a compact disk ROM (CD-ROM) , and a digital versatile disk ROM, etc. In some embodiments, the storage device 120 may be implemented on a cloud platform. Merely by way of example, the cloud platform may include a private cloud, a public cloud, a hybrid cloud, a community cloud, a distributed cloud, an inter-cloud, a multi-cloud, or the like, or any combination thereof.

In some embodiments, the storage device 120 may be connected to the network 130 to communicate with one or more components (the storage device 120, the terminal device (s) 140, the positioning device (s) 150) of the mapping system 100. One or more components of the mapping system 100 may access the data or instructions stored in the storage device 120 via the network 130. In some embodiments, the storage device 120 may be directly connected to or communicate with one or more components (the storage device 120, the terminal device (s) 140, the positioning device (s) 150) of the mapping system 100. In some embodiments, the storage device 120 may be part of the server 110. For example, the storage device 120 may be integrated into the server 110.

The network 130 may facilitate the exchange of information and/or data. In some embodiments, one or more components (the storage device 120, the terminal device (s) 140, the positioning device (s) 150) of the mapping system 100 may send information and/or data to other component (s) of the mapping system 100 via the network 130. For example, the server 110 may obtain a pose graph of a region from the storage device 120 via the network 130. In some embodiments, the network 130 may be any type of wired or wireless network, or combination thereof. Merely by way of example, the network 130 may include a cable network, a wireline network, an optical fiber network, a telecommunications network, an intranet, an Internet, a local area network (LAN) , a wide area network (WAN) , a wireless local area network (WLAN) , a metropolitan area network (MAN) , a wide area network (WAN) , a public telephone switched network (PSTN) , a Bluetooth network, a ZigBee network, a near field communication (NFC) network, or the like, or any combination thereof. In some embodiments, the network 130 may include one or more network access points. For example, the network 130 may include wired or wireless network access points (e.g., 140-1, 140-2) , through which one or more components of the mapping system 100 may be connected to the network 130 to exchange data and/or information.

In some embodiments, the terminal device (s) 140 may include a mobile device 140-1, a tablet computer 140-2, a laptop computer 140-3, a built-in device in a vehicle 140-4, a smartwatch 140-5, or the like, or any combination thereof. In some embodiments, the mobile device 140-1 may include a smart home device, a wearable device, a smart mobile device, a virtual reality device, an augmented reality device, or the like, or any combination thereof. In some embodiments, the smart home device may include a smart lighting device, a control device of an intelligent electrical apparatus, a smart monitoring device, a smart television, a smart video camera, an interphone, or the like, or any combination thereof. In some embodiments, the wearable device may include a smart bracelet, a smart footgear, a smart glass, a smart helmet, a smartwatch, smart clothing, a smart backpack, a smart accessory, or the like, or any combination thereof. In some embodiments, the smart mobile device may include a smartphone, a personal digital assistant (PDA) , a gaming device, a navigation device, a point of sale (POS) device, or the like, or any combination thereof. In some embodiments, the virtual reality device and/or the augmented reality device may include a virtual reality helmet, a virtual reality glass, a virtual reality patch, an augmented reality helmet, an augmented reality glass, an augmented reality patch, or the like, or any combination thereof. For example, the virtual reality device and/or the augmented reality device may include a Google ^TM Glass, an Oculus Rift, a HoloLens, a Gear VR, etc. In some embodiments, the built-in device in the vehicle 140-4 may include an onboard computer, an onboard television, etc. In some embodiments, the server 110 may be integrated into the terminal device (s) 140.

The positioning device (s) 150 may determine information associated with an object, for example, one or more of the terminal device (s) 140, etc. In some embodiments, the positioning device (s) 150 may be a global positioning system (GPS) , a global navigation satellite system (GLONASS) , a compass navigation system (COMPASS) , a BeiDou navigation satellite system, a Galileo positioning system, a quasi-zenith satellite system (QZSS) , etc. The information may include a location, an elevation, a velocity, or an acceleration of the object, or a current time. The positioning device (s) 150 may include one or more satellites, for example, a satellite 150-1, a satellite 150-2, and a satellite 150-3. The satellites 150-1 through 150-3 may determine the information mentioned above independently or jointly. The satellite positioning device (s) 150 may send the information mentioned above to the network 130, the terminal device (s) 140, etc., via wireless connections.

In some embodiments, the pose graph of the region as illustrated above may be determined by the mapping system 100. The mapping system 100 may also include one or more vehicles 160. The vehicle (s) 160 may be connected to the network 130 to communicate with one or more components (e.g., the storage device 120, the terminal device (s) 140, the positioning device (s) 150) of the mapping system 100. For illustration purposes, the vehicle (s) 160 may include vehicles160-1, 160-2, …, and 160-n.

In some embodiments, the vehicle (s) 160 may acquire data (e.g., point cloud data, images of the region) for constructing the posh graph of the region. The vehicle (s) 160 may be equipped with one or more sensors 162 configured to acquire the data. The sensor (s) 162 may include a GPS device, light detection and ranging (LiDAR) , a camera, an inertial measurement unit (IMU) sensor, or the like, or any combination thereof. The LiDAR may be configured to scan the surrounding and generate point cloud data. The LiDAR may measure a distance to an object by illuminating the object with pulsed laser light and measuring the reflected pulses with a sensor. Differences in laser return times and wavelengths may then be used to make digital 3-D representations of the object. The light used for LiDAR scan may be ultraviolet, visible, near-infrared, etc. Because a narrow laser beam may map physical features with very high resolution, the LiDAR may be particularly suitable for high-definition map surveys. The camera may be configured to obtain one or more images relating to objects that are within the scope of the camera. The GPS device may refer to a device that is capable of receiving geolocation and time information from GPS satellites and then to calculate the device's geographical position. The IMU sensor may refer to an electronic device that measures and provides a vehicle’s specific force, angular rate, and sometimes the magnetic field surrounding the vehicle, using various inertial sensors, such as accelerometers and gyroscopes, sometimes also magnetometers. By combining the GPS device and the IMU sensor, the sensor 112 can provide real-time pose information of the vehicle (s) 160 as it travels, including the positions and orientations (e.g., Euler angles) of the vehicle (s) 160 at each time point. Consistent with the present disclosure, the sensor (s) 162 may take measurements of pose information at the same time points where the sensor (s) 162 captures the point cloud data. Accordingly, the pose information may be associated with the respective point cloud data. In some embodiments, the combination of point cloud data and its associated pose information may be used to position the vehicle (s) 160. In some embodiments, the GPS device may also be replaced by other positioning devices, such as BeiDou.

In some embodiments, the sensor (s) 162 may be mounted to the body of the vehicle (s) 160 via a mounting structure. The mounting structure may be an electro-mechanical device installed or otherwise attached to the body of the vehicle (s) 160. In some embodiments, the mounting structure may use screws, adhesives, or another mounting mechanism. The vehicle (s) 160 may be additionally equipped with the one or more sensor (s) 162 inside or outside the body using any suitable mounting mechanisms.

In some embodiments, the vehicle (s) 160 may be an electric vehicle, a fuel cell vehicle, a hybrid vehicle, a conventional internal combustion engine vehicle, etc. In some embodiments, the vehicle (s) 160 may be operated by an operator occupying the vehicle, remotely controlled, and/or autonomous. It should be noted that the vehicle (s) 160 are used as examples for illustration purposes, any object that is able to move can be used to acquire the data for constructing the posh graph. For example, the object may include unmanned airplanes, robots, pedestrians, etc.

It should be noted that the mapping system 100 is merely provided for the purposes of illustration, and is not intended to limit the scope of the present disclosure. For persons having ordinary skills in the art, multiple variations or modifications may be made under the teachings of the present disclosure. However, those variations and modifications do not depart from the scope of the present disclosure.

FIG. 2 is a schematic diagram illustrating exemplary hardware and/or software components of a computing device 200 according to some embodiments of the present disclosure. In some embodiments, the server 110, and/or the terminal device (s) 140 may be implemented on the computing device 200. For example, the processing engine 112 may be implemented on the computing device 200 and configured to perform functions of the processing engine 112 disclosed in this disclosure.

The computing device 200 may be used to implement any component of the mapping system 100 as described herein. For example, the processing engine 112 may be implemented on the computing device 200, via its hardware, software program, firmware, or a combination thereof. Although only one such computer is shown, for convenience, the computer functions as described herein may be implemented in a distributed fashion on a number of similar platforms to distribute the processing load.

The computing device 200, for example, may include COM ports 250 connected to and from a network connected thereto to facilitate data communications. The computing device 200 may also include a processor 220, in the form of one or more processors (e.g., logic circuits) , for executing program instructions. For example, the processor 220 may include interface circuits and processing circuits therein. The interface circuits may be configured to receive electronic signals from a bus 210, wherein the electronic signals encode structured data and/or instructions for the processing circuits to process. The processing circuits may conduct logic calculations, and then determine a conclusion, a result, and/or an instruction encoded as electronic signals. Then the interface circuits may send out the electronic signals from the processing circuits via the bus 210.

The computing device 200 may further include program storage and data storage of different forms including, for example, a disk 270, and a read only memory (ROM) 230, or a random access memory (RAM) 240, for various data files to be processed and/or transmitted by the computing device. The exemplary computer platform may also include program instructions stored in the ROM 230, RAM 240, and/or other type of non-transitory storage medium to be executed by the processor 220. The methods and/or processes of the present disclosure may be implemented as the program instructions. The computing device 200 also includes an I/O component 260, supporting input/output between the computer and other components. The computing device 200 may also receive programming and data via network communications.

Merely for illustration, only one processor is described in FIG. 2. Multiple processors are also contemplated, thus operations and/or method steps performed by one processor as described in the present disclosure may also be jointly or separately performed by the multiple processors. For example, if in the present disclosure the processor of the computing device 200 executes both step A and step B, it should be understood that step A and step B may also be performed by two different CPUs and/or processors jointly or separately in the computing device 200 (e.g., the first processor executes step A and the second processor executes step B, or the first and second processors jointly execute steps A and B) .

FIG. 3 is a schematic diagram illustrating exemplary hardware and/or software components of a mobile device 300 on which the terminal device (s) 140 may be implemented according to some embodiments of the present disclosure. As illustrated in FIG. 3, the mobile device 300 may include a communication platform 310, a display 320, a graphic processing unit (GPU) 330, a central processing unit (CPU) 340, an I/O 350, a memory 360, a mobile operating system (OS) 370, and a storage 390. In some embodiments, any other suitable component, including but not limited to a system bus or a controller (not shown) , may also be included in the mobile device 300.

In some embodiments, the mobile operating system 370 (e.g., iOS ^TM, Android ^TM, Windows Phone ^TM, etc. ) and one or more applications 380 may be loaded into the memory 360 from the storage 390 in order to be executed by the CPU 340. The applications 380 may include a browser or any other suitable mobile apps for receiving and rendering information from the mapping system 100. User interactions with the information stream may be achieved via the I/O 350 and provided to the processing engine 112 and/or other components of the mapping system 100 via the network 120.

FIG. 4 is a block diagram illustrating an exemplary processing engine 112 according to some embodiments of the present disclosure. The processing engine 112 may include a pose graph obtaining module 410, a sub-region determination module 420, a road layer determination module 430, and a map determination module 440.

The pose graph obtaining module 410 may be configured to obtain a pose graph of a region. The pose graph may include a plurality of objects in the region. In some embodiments, the objects may include objects located on driving paths (or roads) , objects located on pedestrian paths (or roads) , landmark objects, etc. In some embodiments, map data of the pose graph may include location information of the objects, semantic information of the objects, etc.

In some embodiments, the pose graph may also include a plurality of route-tracking datasets in the region. Each node may correspond to a pose where the one or more sensors capture a portion of the point cloud data. The node may include the portion of point cloud data captured at the pose. For illustration purposes, the node may include one or more point clouds included in the at least a portion of the point cloud data captured along the at least one road.

In some embodiments, the pose graph obtaining module 410 may obtain the pose graph from a storage device (e.g., the storage device 120, the storage 320) of the mapping system 100 or a third party (e.g., an external device) . In some embodiments, the pose graph obtaining module 410 may determine the pose graph of the region based on data associated with the region. The data may be captured by one or more sensors mounted on at least one moving object (e.g., vehicles, robots, unmanned planes, pedestrians) . As described in FIG. 1, the at least one moving object may travel along reference routes within the region, and the one or more sensors may simultaneously capture the data by scanning a space around a current location of the moving object along the reference routes. In some embodiments, a plurality of routes corresponding to the plurality of route-tracking datasets may include at least a portion of the reference routes. For example, a route corresponding to a route-tracking dataset may be one of the reference routes or a portion thereof.

The sub-region determination module 420 may be configured to determine at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets. As used herein, an overlapped sub-region may be associated with a grade separation structure. The grade separation structure may be a junction of a plurality of layers of roads at different heights (or grades) in the region and traffic on different layers of roads may not disrupt each other.

In some embodiments, the sub-region determination module 420 may determine whether at least two of the plurality of route-tracking datasets (also referred to as “at least two candidate route-tracking datasets” ) overlap at a candidate sub-region. In response to a determination that the at least two candidate route-tracking datasets overlap at the candidate sub-region, the sub-region determination module 420 may further determine whether at least two of the at least two candidate route-tracking datasets (also referred to as “at least two route-tracking datasets” ) satisfy a condition. In response to a determination that the at least two route-tracking datasets satisfy a condition, the sub-region determination module 420 may designate the candidate sub-region as one of the at least one overlapped sub-region.

In some embodiments, more than one road corresponding to more than one of the at least two candidate route-tracking datasets at a candidate overlapped sub-regions may belong to the same roads. The sub-region determination module 420 may obtain the at least two route tracking datasets by keeping one of the more than one of the plurality route-tracking datasets among the at least two candidate route-tracking datasets for each of the same roads in the two-dimensional map. In some embodiments, the processing engine 112 may determine the more than one of the at least two candidate route-tracking datasets based on text information (also referred to as “first text information” ) associated with the at least two candidate route-tracking datasets. In some embodiments, the first text information may include the names of roads included in the at least two candidate route-tracking datasets at a corresponding candidate overlapped sub-region. The names of more than one road corresponding to the more than one of the at least two candidate route-tracking datasets may be the same at the corresponding candidate overlapped sub-region. For illustration purposes, if the text information indicates that the name of a road of a first candidate route-tracking dataset is the same as the name of a road of a second candidate route-tracking dataset at a corresponding candidate overlapped sub-region, the first candidate route-tracking dataset and the second candidate route-tracking dataset may belong to the same road.

In some embodiments, the sub-region determination module 420 may obtain the first text information from data such as map data of a third-party map (e.g., a semantic map included the roads) , voice data associated with the roads, image data associated with the roads, etc. In some embodiments, the sub-region determination module 420 may obtain the map data of the third-party map, the voice data, the image data, etc., from the mapping system 100 (e.g., the storage device, the terminal device (s) 140) or in a third party.

In some embodiments, if a height difference between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two route-tracking datasets is greater than a threshold, the sub-region determination module 420 may determine that the at least two of the plurality of route-tracking datasets satisfy the condition. As used herein, two corresponding nodes may include a first node in a first route- tracking dataset from the at least two route-tracking datasets and a second node in a second route-tracking dataset other than the first route-tracking dataset from the at least two route-tracking datasets. In some embodiments, the first node and the second node may be two nodes along the same vertical line. For illustration purposes, the first node and the second node may have the same latitude and longitude, and the height (or elevation) thereof may be different. In some embodiments, the first node and the second node may be two nodes substantially along the same vertical line, the deviation of which may be within a reasonable range to accurately indicate the height difference between the two corresponding nodes. For example, the vertical line may be the centerline of the first route-tracking dataset or the centerline of the second route-tracking dataset at a corresponding overlapped sub-region. As another example, the vertical line may be along a pillar that supports one or more upper lays of roads at an overlapped-region in a vertical direction.

The height as used herein may refer to an absolute height of a node. In some embodiments, the sub-region determination module 420 may obtain the heights of any two corresponding nodes from the pose graph, the sensor data (e.g., the point cloud data, the image data) or map data of a third-party map (e.g., a three-dimensional map, a semantic map) providing the heights. In some embodiments, the third-party map may be stored in the storage device of the mapping system 100 or stored in a third party.

In some embodiments, if a geometric match degree between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two route-tracking datasets is smaller than a threshold, the sub-region determination module 420 may determine that the at least two route-tracking datasets satisfy the condition. As used herein, similar to the above, two corresponding nodes may include a first node in a first route-tracking dataset from the at least two route-tracking datasets and a second node in a second route-tracking dataset other than the first route-tracking dataset from the at least two route-tracking datasets. In some embodiments, the first node and the second node may be two nodes along the same vertical line. For illustration purposes, the first node and the second node may have the same latitude and longitude, and the height (or elevation) thereof may be different. In some embodiments, the first node and the second node may be two nodes substantially along the same vertical line, the deviation of which may be within a reasonable range to accurately indicate the height difference between the two corresponding nodes. For example, the vertical line may be the centerline of the first route-tracking dataset or the centerline of the second route-tracking dataset at a corresponding overlapped sub-region. As another example, the vertical line may be along a pillar that supports one or more upper lays of roads at an overlapped-region in a vertical direction.

The geometric match degree may refer to a match degree between one or more point clouds of a first node and one or more point clouds of a second node. For illustration purposes, the first node and the second node may have the same latitude and longitude, and the height (or elevation) thereof may be different. In some embodiments, the vertical line may be the centerline of the first route-tracking dataset or the centerline of the second route-tracking dataset at a corresponding overlapped sub-region.

In some embodiments, the sub-region determination module 420 may determine the geometric match degree based on a point cloud registration algorithm. For example, the point cloud registration algorithm may include an iterative closest point (ICP) algorithm, a kernel correlation (KC) algorithm, a robust point matching algorithm, a LORAX algorithm, a 4-Points Congruent Sets (4PCS) algorithm, a super 4PCS algorithm, a semantic keypoint-4PCS (SK-4PCS) algorithm, a generalized 4PCS (G-4PCS) algorithm, or the like, or any combination thereof.

In some embodiments, if any two route-tracking datasets of the at least two route-tracking datasets belong to two different roads based on text information associated with the two route-tracking datasets (also referred to as “second text information” ) , the sub-region determination module 420 may determine that the at least two route-tracking datasets satisfy the condition. Similar to the first text information, the second text information may include the names of roads included in any two route-tracking datasets at a corresponding overlapped sub-region. The names of roads of the two route-tracking datasets may be different at the corresponding overlapped sub-region. For example, if the text information indicates that the name of a road of a first route-tracking dataset is different from the name of a road of a second route-tracking dataset at a corresponding overlapped sub-region, the first route-tracking dataset and the second route-tracking dataset may belong to two different roads.

In some embodiments, the sub-region determination module 420 may obtain the second text information from data such as map data of a third-party map (e.g., a semantic map included the roads) , voice data associated with the roads, image data associated with the roads, etc. In some embodiments, the sub-region determination module 420 may obtain the map data of the third-party map, the voice data, the image data, etc., from the mapping system 100 (e.g., the storage device, the terminal device (s) 140) or in a third party.

In some embodiments, the sub-region determination module 420 may preprocess the plurality of route-tracking datasets and determine the at least one overlapped sub-region included in the region based on the preprocessed route-tracking datasets. In some embodiments, the sub-region determination module 420 may remove a portion of the plurality of route-tracking datasets. Specifically, the sub-region determination module 420 may determine whether more than one of the plurality of route-tracking datasets belongs to the same road based on text information (also referred to as “third text information” ) associated with the plurality of route-tracking datasets. In response to a determination that the more than one of the plurality of route-tracking datasets belongs to the same road, the sub-region determination module 420 may keep one of the more than one of the plurality route-tracking datasets.

Similar to the first text information and/or the second text information, the third text information may include the names of roads included in the plurality of route-tracking datasets. For example, if the text information indicates that the name (s) of at least one road of a first route-tracking dataset is the same as the name (s) of at least one road of a second route-tracking dataset at the same sub-region, the first route-tracking dataset and the second route-tracking dataset may belong to the same road (s) . The sub-region determination module 420 may keep the first route-tracking dataset or the second route-tracking dataset. As another example, if the text information indicates that the name (s) of a portion of at least one road of a first route-tracking dataset is the same as the name (s) of a portion of at least one road of a second route-tracking dataset at the same sub-region, the portion of the first route-tracking dataset and the portion of the second route-tracking dataset may belong to the same road (s) . The sub-region determination module 420 may omit the portion of the first route-tracking dataset or the portion of the second route-tracking dataset.

In some embodiments, the sub-region determination module 420 may obtain the third text information from data such as map data of a third-party map (e.g., a semantic map included the roads) , voice data associated with the roads, image data associated with the roads, etc. In some embodiments, the sub-region determination module 420 may obtain the map data of the third-party map, the voice data, the image data, etc., from the mapping system 100 (e.g., the storage device, the terminal device (s) 140) or in a third party.

The road layer determination module 430 may be configured to determine a plurality of layers of roads in the region based on the at least one overlapped sub-region. As illustrated above, each of the overlapped sub-region may be associated with the plurality of layers of roads. In some embodiments, the plurality of layers of roads in the region may include the plurality of layers of roads included in the at least one overlapped region. In some embodiments, the region may also include one or more sub-regions (also referred to as “unoverlapped region” ) other than the at least one overlapped sub-region. As used herein, an unovelapped region may have no overlapped layers of roads in different heights and have only one layer of road. The road layer determination module 430 may also determine the layer of road corresponding to the one or more unoverlapped sub-regions as one of the plurality of layers of roads.

Each of the plurality of layers of roads may have a boundary. The boundary may be used to define the dimension of the layer of road. For an unoverlapped sub-region, the road layer determination module 430 may designate the boundary of the unoverlapped region as the boundary of a corresponding layer of road. In some embodiments, for an overlapped sub-region, the road layer determination module 430 may determine the boundary of a corresponding layer of road based on the boundary of an area associated with the corresponding layer of road. In some embodiments, the road layer determination module 430 may designate the boundary of the area as the boundary of the corresponding layer of road.

In some embodiments, the road layer determination module 430 may determine the area by classifying the plurality of nodes of the at least two route-tracking datasets, or a portion thereof. Specifically, the road layer determination module 430 may classify at least a portion of the plurality of nodes corresponding to an overlapped sub-region of each of at least two route-tracking datasets into two or more groups. The two or more groups may correspond to the two or more layers of roads. The road layer determination module 430 may determine the area containing the at least a portion of the plurality nodes in each of the two or more groups.

In some embodiments, when capturing point cloud data of one or more nodes adjacent to the at least a portion of nodes, a certain portion (e.g., larger than a threshold) of point cloud data of the at least a portion of nodes may be captured. The one or more adjacent nodes should be regarded to belong to the corresponding layer of road. Accordingly, the road layer determination module 430 may expand the area by including the at least a portion of one or more adjacent nodes.

The map determination module 440 may be configured to determine a target map (e.g., the target 2D map) based on the plurality of layers of roads and the pose graph. In some embodiments, the map determination module 440 may determine map data of the target map hierarchically with respect to the plurality of layers of roads. In some embodiments, the map determination module 440 may determine the target map based on a sub map for each of the plurality of layers of roads. The map determination module 440 may determine the target map by combining the sub maps. For illustration purposes, the map determination module 440 may determine the target map by overlaying the sub maps. In some embodiments, the map determination module 440 may determine the target map by overlaying a sub map of a layer of road with respect to the unoverlapeed sub-region (s) at the bottom.

Each sub map may include map data of a layer of road, and all of the sub maps may have the same coordinate system (e.g., a world coordinate system) . For example, the map data of the layer of road may include location information of objects associated with the layer of road, semantic information of objects associated with the layer of road, etc. Exemplary location information of an object may include a geometric location of the object in latitude, longitude, and height (or elevation) , or the like, or any combination thereof. Exemplary semantic information of an object may include a name of a road, the type of a road, a restriction of the direction of a driving path, a speed restriction of a driving path, the type of a pedestrian, a restriction of changing a direction (e.g., going straight, turning left, turning right, one-way, do-not-enter) , connectivity to other paths, the count (or number) of lanes of road, or the like, or any combination thereof. In some embodiments, the map determination module 440 may obtain the location information and the semantic information of the sub map based on the pose graph, the sensor data, a third-party map (e.g., a 3D map, a semantic map) , etc.

In some embodiments, the map determination module 440 may mark the layers of roads or the sub maps. For an overlapped sub region, the map determination module 440 may mark two or more sub maps corresponding to two or more layers of roads differently. The map determination module 440 may mark the two or more sub maps by any form, such as but not limited to characters, letters, digits, symbols, images, codes, colors, or a combination thereof.

In some embodiments, roads in the region may change due to road construction. Accordingly, the map determination module 440 may update the target map based on newly obtained pose graph and a plurality of newly obtained route-tracking datasets.

The modules in the processing engine 112 may be connected to or communicated with each other via a wired connection or a wireless connection. The wired connection may include a metal cable, an optical cable, a hybrid cable, or the like, or any combination thereof. The wireless connection may include a Local Area Network (LAN) , a Wide Area Network (WAN) , a Bluetooth, a ZigBee, a Near Field Communication (NFC) , or the like, or any combination thereof. Two or more of the modules may be combined into a single module, and any one of the modules may be divided into two or more units. For example, the pose graph obtaining module 410 and the map determination module 440 may be combined as a single module which may both obtain the pose graph of the region and determine the target map based on the plurality of layers of roads and the pose graph. As another example, the processing engine 112 may include a storage module (not shown) which may be used to store data generated by the above-mentioned modules.

FIG. 5 is a flowchart illustrating an exemplary process for determining a target map based on route-tracking datasets and a pose graph according to some embodiments of the present disclosure. In some embodiments, the process 500 may be implemented as a set of instructions (e.g., an application) stored in the ROM 230 or RAM 240. The processor 220 and/or the modules in FIG. 4 may execute the set of instructions, and when executing the instructions, the processor 220 and/or the modules may be configured to perform the process 500. The operations of the illustrated process presented below are intended to be illustrative. In some embodiments, the process 500 may be accomplished with one or more additional operations not described and/or without one or more of the operations herein discussed. Additionally, the order in which the operations of the process as illustrated in FIG. 5 and described below is not intended to be limiting. In some embodiments, a pose graph of a region may be a two-dimensional (2D) map. The pose graph may be unlikely to include all map data of a plurality of layers of roads associated with an overlapped sub-region corresponding to a grade separation structure (e.g., overpass, underpass, interchange, viaduct) in the region. In some embodiments, the pose graph may include map data of one of the plurality of layers of roads. For example, the pose graph may include only map data of an upper layer of road for an overpass, but not a lower layer of road. Thus, the pose graph may be unlikely to symbolically display or represent the whole grade separation structure (e.g., overpass, underpass, interchange, viaduct) in the region accurately. The process 500 may be implemented to determine a target map to have all map data of the plurality of layers of roads at least based on the pose graph and a plurality of route-tracking datasets in the region.

In 510, the processing engine 112 (e.g., the pose graph obtaining module 410) may obtain a pose graph of a region. The pose graph may include a plurality of objects in the region. In some embodiments, the objects may include objects located on driving paths (or roads) , objects located on pedestrian paths (or roads) , landmark objects, etc. Exemplary objects located on the driving paths may include lane, highway, interchange, viaduct, beltway, or the like, or any combination thereof. Exemplary objects located on the pedestrian paths may include crosswalk, sidewalk, overpass, underpass, or the like, or any combination thereof. Exemplary landmark objects may include speed bump, curb, stop sign, traffic light, stop line, vehicle, pedestrian, lanes of road, building, tree, river, or the like, or any combination thereof.

In some embodiments, map data of the pose graph may include location information of the objects, semantic information of the objects, etc. Exemplary location information of an object may include a geometric location of the object in latitude, longitude, and height (or elevation) , or the like, or any combination thereof. Exemplary semantic information of an object may include a name of a driving path, a restriction of the direction of a driving path, a speed restriction of a driving path, the type of a driving path, the type of a pedestrian, a restriction of changing a direction (e.g., going straight, turning left, turning right, one-way, do-not-enter) , connectivity to other paths, the count (or number) of lanes of a road, or the like, or any combination thereof.

In some embodiments, the map data of the pose graph may be determined based on data associated with the region. The data may be captured by one or more sensors mounted on at least one moving object (e.g., vehicles, robots, unmanned planes, pedestrians) . As described in FIG. 1, the at least one moving object may travel along reference routes within the region, and the one or more sensors may simultaneously capture the data by scanning a space around a current location of the moving object along the reference routes. For example, the sensor (s) may include a GPS device, light detection and ranging (LiDAR) , a camera, an inertial measurement unit (IMU) sensor, or the like, or any combination thereof.

For illustration purposes, the data may include point cloud data associated with the reference routes, image data associated with the reference routes, etc. In some embodiments, the pose graph may be determined by combining the point cloud data and/or image data. In some embodiments, the point cloud data may include a plurality of point clouds. Each of the point clouds may symbolically represent at least a portion of the objects in the region. The point cloud may include a set of data points associated with one or more objects around the current location of the moving object along the reference routes in the region. In some embodiments, the set of data points may represent feature information of the one or more objects. The feature information may include a contour of an object in the region, a surface of an object in the region, a size of an object in the region, or the like, or any combination thereof. Each data point may correspond to data of a point or a portion of an object in the region. Merely by way of example, each data point may include location information of the point, color information of the point, intensity information of the point, texture information of the point, or the like, or any combination thereof.

In some embodiments, a plurality of route-tracking datasets in the region may be generated based on the point cloud data (or the point clouds) . Each of the plurality of route-tracking datasets may be associated with at least one road (e.g., driving paths, pedestrian paths) in the region. In some embodiments, the route-tracking dataset may be associated with point cloud data captured along the at least one road. The route-tracking dataset may include at least a portion of point cloud data captured along the at least one road of the point cloud data. For illustration purposes, the route-tracking dataset may include all of the point cloud data captured along the at least one road. For illustration purposes, the route-tracking dataset may include a portion of the point cloud data captured along the at least one road. In some embodiments, the at least a portion of the point cloud data along the at least one road may represent spatial information of a plurality of objects on the at least one road, semantic information of a plurality of object on the at least one road, etc.

The route-tracking dataset may include a plurality of nodes with respect to the at least one road. Each node may correspond to a pose where the one or more sensors capture a portion of the point cloud data. The node may include the portion of point cloud data captured at the pose. For illustration purposes, the node may include one or more point clouds included in the at least a portion of the point cloud data captured along the at least one road. In some embodiments, a plurality of routes corresponding to the plurality of route-tracking datasets may include at least a portion of the reference routes. For example, a route corresponding to a route-tracking dataset may be one of the reference routes or a portion thereof.

In some embodiments, the pose graph may be provided by the mapping system 100 (e.g., the processing engine 112, a storage device of the mapping system 100) or a third party (e.g., an external device) . In some embodiments, the mapping system 100 may predetermine the pose graph based on the process for determining the pose graph as illustrated above and store the pose graph in the storage device (e.g., the storage device 120, the storage 320) disclosed elsewhere in the present disclosure.

In 520, the processing engine 112 (e.g., the sub-region determination module 420) may determine at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region. As used herein, an overlapped sub-region may be associated with a grade separation structure. The grade separation structure may be a junction of a plurality of layers of roads at different heights (or grades) in the region and traffic on different layers of roads may not disrupt each other. For example, the grade separation structure may include an interchange, an overpass, a viaduct, an underpass, etc. In some embodiments, types of the plurality of layers of roads may be different or the same. Exemplary types of the roads may include a footway, a bridge, a railway, a high way, a canal, an airport runway, a tunnel, etc. For example, an overpass may include a footpath that crosses over a highway. The footway and the high way may separately correspond to two layers of roads. As another example, an interchange may include a first high way that crosses over a second highway. The first high way and the second high way may separately correspond to two layers of roads. As a further example, an interchange may include several highways that cross over each other. The several high ways may correspond to several layers of roads, respectively.

In some embodiments, the processing engine 112 may determine whether at least two of the plurality of route-tracking datasets (also referred to as “at least two candidate route-tracking datasets” ) overlap at a candidate sub-region. In response to a determination that the at least two candidate route-tracking datasets overlap at the candidate sub-region, the processing engine 112 may further determine whether at least two of the at least two candidate route-tracking datasets (also referred to as “at least two route-tracking datasets” ) satisfy a condition. In response to a determination that the at least two route-tracking datasets satisfy a condition, the processing engine 112 may designate the candidate sub-region as one of the at least one overlapped sub-region.

In some embodiments, more than one road corresponding to more than one of the at least two candidate route-tracking datasets at a candidate overlapped sub-regions may belong to the same roads. The processing engine 112 may obtain the at least two route tracking datasets by keeping one of the more than one of the plurality route-tracking datasets among the at least two candidate route-tracking datasets for each of the same roads. In some embodiments, the processing engine 112 may determine the more than one of the at least two candidate route-tracking datasets based on text information (also referred to as “first text information” ) associated with the at least two candidate route-tracking datasets. In some embodiments, the first text information may include the names of roads included in the at least two candidate route-tracking datasets at a corresponding candidate overlapped sub-region. The names of more than one road corresponding to the more than one of the at least two candidate route-tracking datasets may be the same at the corresponding candidate overlapped sub-region. For illustration purposes, if the text information indicates that the name of a road of a first candidate route-tracking dataset is the same as the name of a road of a second candidate route-tracking dataset at a corresponding candidate overlapped sub-region, the first candidate route-tracking dataset and the second candidate route-tracking dataset may belong to the same road. For example, if the name of a road of route-tracking dataset A at an overpass is the same as the name of a road of route-tracking dataset B at the overpass, the processing engine 112 may determine that the route-tracking dataset A and the second route-tracking dataset B belong to the same road at the overpass.

In some embodiments, the processing engine 112 may obtain the first text information from data such as map data of a third-party map (e.g., a semantic map included the roads) , voice data associated with the roads, image data associated with the roads, etc. In some embodiments, the processing engine 112 may obtain the map data of the third-party map, the voice data, the image data, etc., from the mapping system 100 (e.g., the storage device, the terminal device (s) 140) or in a third party.

In some embodiments, if a height difference between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two route-tracking datasets is greater than a threshold, the processing engine 112 may determine that the at least two of the plurality of route-tracking datasets satisfy the condition. As used herein, two corresponding nodes may include a first node in a first route-tracking dataset from the at least two route-tracking datasets and a second node in a second route-tracking dataset other than the first route-tracking dataset from the at least two route-tracking datasets. In some embodiments, the first node and the second node may be two nodes along the same vertical line. For illustration purposes, the first node and the second node may have the same latitude and longitude, and the height (or elevation) thereof may be different. In some embodiments, the first node and the second node may be two nodes substantially along the same vertical line, the deviation of which may be within a reasonable range to accurately indicate the height difference between the two corresponding nodes. For example, the vertical line may be the centerline of the first route-tracking dataset or the centerline of the second route-tracking dataset at a corresponding overlapped sub-region. As another example, the vertical line may be along a pillar that supports one or more upper lays of roads at an overlapped-region in a vertical direction.

The height as used herein may refer to an absolute height of a node. In some embodiments, the processing engine 112 may obtain the heights of any two corresponding nodes from the pose graph, the sensor data (e.g., the point cloud data, the image data) or map data of a third-party map (e.g., a three-dimensional map, a semantic map) providing the heights. In some embodiments, the third-party map may be stored in the storage device of the mapping system 100 or stored in a third party.

In some embodiments, if a geometric match degree between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two route-tracking datasets is smaller than a threshold, the processing engine 112 may determine that the at least two route-tracking datasets satisfy the condition. As used herein, similar to the above, two corresponding nodes may include a first node in a first route-tracking dataset from the at least two route-tracking datasets and a second node in a second route-tracking dataset other than the first route-tracking dataset from the at least two route-tracking datasets. In some embodiments, the first node and the second node may be two nodes along the same vertical line. For illustration purposes, the first node and the second node may have the same latitude and longitude, and the height (or elevation) thereof may be different. In some embodiments, the first node and the second node may be two nodes substantially along the same vertical line, the deviation of which may be a reasonable range to accurately indicate the height difference between the two corresponding nodes. For example, the vertical line may be the centerline of the first route-tracking dataset or the centerline of the second route-tracking dataset at a corresponding overlapped sub-region. As another example, the vertical line may along a pillar that supports one or more upper lays of roads at an overlapped-region in a vertical direction.

In some embodiments, the processing engine 112 may determine the geometric match degree based on a point cloud registration algorithm. For example, the point cloud registration algorithm may include an iterative closest point (ICP) algorithm, a kernel correlation (KC) algorithm, a robust point matching algorithm, a LORAX algorithm, a 4-Points Congruent Sets (4PCS) algorithm, a super 4PCS algorithm, a semantic keypoint-4PCS (SK-4PCS) algorithm, a generalized 4PCS (G-4PCS) algorithm, or the like, or any combination thereof.

In some embodiments, if any two route-tracking datasets of the at least two route-tracking datasets belong to two different roads based on text information associated with the two route-tracking datasets (also referred to as “second text information” ) , the processing engine 112 may determine that the at least two route-tracking datasets satisfy the condition. Similar to the first text information, the second text information may include the names of roads included in any two route-tracking datasets at a corresponding overlapped sub-region. The names of roads of the two route-tracking datasets may be different at the corresponding overlapped sub-region. For example, if the text information indicates that the name of a road of a first route-tracking dataset is different from the name of a road of a second route-tracking dataset at a corresponding overlapped sub-region, the first route-tracking dataset and the second route-tracking dataset may belong to two different roads. For example, if the name of a road of route-tracking dataset A at an overpass is different from the name of a road of route-tracking dataset B at the overpass, the processing engine 112 may determine that the route-tracking dataset A and the second route-tracking dataset B belong to two different roads at the overpass.

In some embodiments, the processing engine 112 may obtain the second text information from data such as map data of a third-party map (e.g., a semantic map included the roads) , voice data associated with the roads, image data associated with the roads, etc. In some embodiments, the sub-region determination module 420 may obtain the map data of the third-party map, the voice data, the image data, etc., from the mapping system 100 (e.g., the storage device, the terminal device (s) 140) or in a third party.

In some embodiments, the processing engine 112 may preprocess the plurality of route-tracking datasets and determine the at least one overlapped sub-region based on the preprocessed route-tracking datasets. In some embodiments, the processing engine 112 may remove a portion of the plurality of route-tracking datasets. Specifically, the processing engine 112 may determine whether more than one of the plurality of route-tracking datasets belongs to the same road based on text information (also referred to as “third text information” ) associated with the plurality of route-tracking datasets. In response to a determination that the more than one of the plurality of route-tracking datasets belongs to the same road, the processing engine 112 may keep one of the more than one of the plurality route-tracking datasets.

Similar to the first text information and/or the second text information, the third text information may include the names of roads included in the plurality of route-tracking datasets. For illustration purposes, if the text information indicates that the name (s) of at least one road of a first route-tracking dataset is the same as the name (s) of at least one road of a second route-tracking dataset at the same sub-region, the first route-tracking dataset and the second route-tracking dataset may belong to the same road (s) . The processing engine 112 may keep the first route-tracking dataset or the second route-tracking dataset. For example, if the name of a road of route-tracking dataset A at a sub-region is the same as the name of a road of route-tracking dataset B at the sub-region, the processing engine 112 may keep the route-tracking dataset A or the second route-tracking dataset B in the two-dimensional map. For illustration purposes, if the text information indicates that the name (s) of a portion of at least one road of a first route-tracking dataset is the same as the name (s) of a portion of at least one road of a second route-tracking dataset at the same sub-region, the portion of the first route-tracking dataset and the portion of the second route-tracking dataset may belong to the same road (s) . The processing engine 112 may omit the portion of the first route-tracking dataset or the portion of the second route-tracking dataset. For example, if a route corresponding to route-tracking dataset A is along a first road and a second road, a route corresponding to route-tracking dataset B is along the second road and a third road different from the first road, the processing engine 112 may omit a portion of the route-tracking dataset A corresponding to the second road or a portion of the route-tracking dataset B corresponding to the second road. In some embodiments, the processing engine 112 may obtain the third text information from data such as map data of a third-party map (e.g., a semantic map included the roads) , voice data associated with the roads, image data associated with the roads, etc. In some embodiments, the processing engine 112 may obtain the map data of the third-party map, the voice data, the image data, etc., from the mapping system 100 (e.g., the storage device, the terminal device (s) 140) or in a third party.

In 530, the processing engine 112 (e.g., the road layer determination module 430) may determine a plurality of layers of roads in the region based on the at least one overlapped sub-region. In some embodiments, the plurality of layers of roads in the region may include the plurality of layers of roads included in the at least one overlapped region. In some embodiments, the region may also include one or more sub-regions (also referred to as “unoverlapped region” ) other than the at least one overlapped sub-region. As used herein, an unovelapped region may have no overlapped layers of roads in different heights and have only one layer of road. The processing engine 112 may also determine the layer of road corresponding to the one or more unoverlapped sub-regions as one of the plurality of layers of roads.

Each of the plurality of layers of roads may have a boundary. The boundary may be used to define the dimension of the layer of road. For an unoverlapped sub-region, the processing engine 112 may designate the boundary of the unoverlapped region as the boundary of a corresponding layer of road. In some embodiments, for an overlapped sub-region, the processing engine 112 may determine the boundary of a corresponding layer of road based on the boundary of an area associated with the corresponding layer of road. In some embodiments, the processing engine 112 may designate the boundary of the area as the boundary of the corresponding layer of road.

In some embodiments, the processing engine 112 may determine the area by classifying the plurality of nodes of the at least two route-tracking datasets, or a portion thereof. Specifically, the processing engine 112 may classify at least a portion of the plurality of nodes corresponding to an overlapped sub-region of each of at least two route-tracking datasets into a plurality of groups. The plurality of groups may correspond to the plurality of layers of roads. The processing engine 112 may determine the area containing the at least a portion of the plurality nodes in each of the plurality of groups.

In some embodiments, when capturing point cloud data of one or more nodes adjacent to the at least a portion of nodes, a certain portion (e.g., larger than a threshold) of point cloud data of the at least a portion of nodes may be captured. The one or more adjacent nodes should be regarded to belong to the corresponding layer of road. Accordingly, the processing engine 112 may expand the area by including the at least a portion of one or more adjacent nodes. For example, as illustrated in FIG. 7, when the one or more sensors capture point cloud data (also referred to as “point cloud data of one or more nodes” ) at one or more nodes (also referred to as “one or more adjacent nodes” ) in an area 720 adjacent to black nodes in an area 740, the one or more sensors may also capture a certain portion of point cloud data of the black nodes. The one or more adjacent nodes should be regarded to belong to an upper layer of road including the black nodes. i.e., the area 740. Accordingly, the processing engine 112 may expand the area 740 by including the one or more adjacent nodes. More detailed descriptions of expanding the area may be found elsewhere in the present disclosure. See, FIGs. 6-7 and the descriptions thereof.

In 540, the processing engine 112 (e.g., the map determination module 440) may determine a target map (e.g., the target 2D map) based on the plurality of layers of roads and the pose graph. In some embodiments, the processing engine 112 may determine map data of the target map hierarchically with respect to the plurality of layers of roads. In some embodiments, the processing engine 112 may determine the target map based on a sub map for each of the plurality of layers of roads. The processing engine 112 may determine the target map by combining the sub maps. For illustration purposes, the processing engine 112 may determine the target map by overlaying the sub maps. In some embodiments, the processing engine 112 may determine the target map by overlaying a sub map of a layer of road with respect to the unoverlapeed sub-region (s) at the bottom.

Each sub map may include map data of a layer of road, and all of the sub maps may have the same coordinate system (e.g., a world coordinate system) . For example, the map data of the layer of road may include location information of objects associated with the layer of road, semantic information of objects associated with the layer of road, etc. Exemplary location information of an object may include a geometric location of the object in latitude, longitude, and height (or elevation) , or the like, or any combination thereof. Exemplary semantic information of an object may include a name of a road, the type of a road, a restriction of the direction of a driving path, a speed restriction of a driving path, the type of a pedestrian, a restriction of changing a direction (e.g., going straight, turning left, turning right, one-way, do-not-enter) , connectivity to other paths, the count (or number) of lanes of road, or the like, or any combination thereof. In some embodiments, the processing engine 112 may obtain the location information and the semantic information of the sub map based on the pose graph, the sensor data, a third-party map (e.g., a 3D map, a semantic map) , etc.

In some embodiments, the processing engine 112 may mark the layers of roads or the sub maps. For an overlapped sub region, the processing engine 112 may mark a plurality of sub maps corresponding to a plurality of layers of roads differently. The processing engine 112 may mark the plurality of sub maps by any form, such as but not limited to characters, letters, digits, symbols, images, codes, colors, or a combination thereof. For example, the processing engine 112 may mark the plurality of sub maps with a series of digits such as 1, 2, 3, …, n, from bottom to up or from up to bottom. As another example, the processing engine 112 may mark the plurality of sub maps with different colors.

In some embodiments, roads in the region may change due to road construction. Accordingly, the processing engine 112 may update the target map based on newly obtained pose graph and a plurality of newly obtained route-tracking datasets. In some embodiments, the target map may be used in various application scenarios, e.g., navigation for vehicles or pedestrians, route planning for vehicles or pedestrians, determining points of interest (POIs) for users, etc.

It should be noted that the above description is merely provided for the purposes of illustration, and not intended to limit the scope of the present disclosure. For persons having ordinary skills in the art, multiple variations or modifications may be made under the teachings of the present disclosure. However, those variations and modifications do not depart from the scope of the present disclosure. For example, one or more other optional steps (e.g., a storing step) may be added elsewhere in the process 500. In the storing step, the processing engine 112 may store information (e.g., the pose graph, the at least one overlapped sub-region, the plurality of layers of roads, the target map) associated with the target subject in a storage device (e.g., the storage device 120) , such as the ones disclosed elsewhere in the present disclosure.

FIG. 6 is a flowchart illustrating an exemplary process for determining boundaries of layers of roads according to some embodiments of the present disclosure. In some embodiments, the process 600 may be implemented as a set of instructions (e.g., an application) stored in the ROM 230 or RAM 240. The processor 220 and/or the modules in FIG. 4 may execute the set of instructions, and when executing the instructions, the processor 220 and/or the modules may be configured to perform the process 600. The operations of the illustrated process presented below are intended to be illustrative. In some embodiments, the process 600 may be accomplished with one or more additional operations not described and/or without one or more of the operations herein discussed. Additionally, the order in which the operations of the process as illustrated in FIG. 6 and described below is not intended to be limiting. In some embodiments, operation 530 of the process 500 may be implemented based on the process 600.

In 610, for each area, the processing engine 112 (e.g., the road layer determination module 430) may determine a bounding box corresponding to each of a plurality of nodes in a route-tracking dataset associated with the area. As illustrated in FIG. 5, each of the plurality of nodes may be associated with one or more point clouds. A boundary box corresponding to the node may enclose the one or more point clouds. In some embodiments, the bounding box may be the minimum bounding or smallest bounding to enclose the one or more point clouds. For example, the bounding box may include a simple bounding sphere, an axis-aligned bounding box (AABB) , an arbitrarily oriented bounding box, an object-oriented bounding box, etc.

In 620, the processing engine 112 (e.g., the road layer determination module 430) may determine whether an overlapped degree between any two corresponding bounding boxes located within a neighboring area and an area, respectively, is greater than a threshold. As used herein, the neighboring area may be an area adjacent to the area. The neighboring area may in a forward direction or backward direction of the area along the layer of road. The size of the neighboring area may be default settings or predetermined by the mapping system 100 or by a user.

As used herein, two corresponding bounding boxes may refer to a first bounding box of a first node within the neighboring area and a second bounding box of a second node within the area on the same road. In some embodiments, the first node may be any node within the neighboring area. The second node may be a node adjacent to the neighboring area. For example, if the neighboring area is in the front of the area along the forward direction of the road, the second node within the area may include a bounding box near the first node, i.e., the first bounding box. As another example, if the neighboring area is behind the area along the forward direction of the road, the second node within the area may include a bounding box near to the first node, i.e., the first bounding box.

The overlapped degree may refer to a degree that a first bounding box overlaps a second bounding box. In some embodiments, the overlapped degree may relate to an overlapped volume of the first bounding box and the second bounding box. For illustration purposes, the greater a ratio of the overlapped volume with respect to the first bounding box and the second bounding box, the greater the overlapped degree may be.

In response to a determination that the overlapped degree is greater than the threshold, the processing engine 112 (e.g., the road layer determination module 430) may expand the area by including one or more nodes located in the neighboring area to the area in 630. As used herein, one or more overlapped degrees of one or more bounding boxes corresponding to the one or more nodes located in the neighboring area and the second bounding box are greater than the threshold. Further, the processing engine 112 (e.g., the road layer determination module 430) may determine a boundary of each of a plurality of layers of roads at an overlapped sub-region based on the expanded area in 640. For illustration purposes, the processing engine 112 may designate the boundary of the expanded area as the boundary of the layer of road.

In response to a determination that the overlapped degree is smaller than or equal to the threshold, the processing engine 112 may not expand the area, operation 630 and operation 640 may be omitted.

It should be noted that the above description is merely provided for the purposes of illustration, and not intended to limit the scope of the present disclosure. For persons having ordinary skills in the art, multiple variations or modifications may be made under the teachings of the present disclosure. However, those variations and modifications do not depart from the scope of the present disclosure.

As shown in FIG. 7, nodes 710 may represent at least a portion of a plurality of nodes included in a first route-tracking dataset. Nodes 720 may represent at least a portion of a plurality of nodes included in a second route-tracking dataset. The first route-tracking dataset and the second route-tracking dataset may be two examples of the plurality of route-tracking datasets as illustrated in FIGs. 4-6. Circle 730 may represent a grade separation structure or an overlapped sub-region associated with the first route-tracking dataset and the second-route-tracking dataset. The grade separation structure or the overlapped sub-region may be associated with two layers of roads, i.e., an upper layer of road and a lower layer of road. For the upper layer of road, black nodes among the nodes 720 may be associated with the grade separation structure or the overlapped sub-region. An area 740 containing the black nodes among the nodes 720 may be designated as a boundary of the upper layer of the road.

In some embodiments, as illustrated in FIGs. 6-7, when the one or more sensors capture point cloud data (also referred to as “point cloud data of one or more adjacent nodes” ) at one or more nodes (also referred to as one or more adjacent nodes) in the area 720 adjacent to the black nodes in the area 740, the one or more sensors may also capture a certain portion (e.g., larger than a threshold) of point cloud data of the black nodes. The one or more adjacent nodes should be regarded to belong to the upper layer of road including the black nodes. i.e., the area 740. Accordingly, the processing engine 112 may expand the area 740 by including the one or more adjacent nodes. As shown in FIG. 7, for the area 740, gray nodes among the nodes 720 may be the one or more adjacent nodes. An area 750 may be the expanded area of the area 740. The area 750 containing the black nodes and the gray nodes may be designated as the boundary of the upper layer of road.

Having thus described the basic concepts, it may be rather apparent to those skilled in the art after reading this detailed disclosure that the foregoing detailed disclosure is intended to be presented by way of example only and is not limiting. Various alterations, improvements, and modifications may occur and are intended to those skilled in the art, though not expressly stated herein. These alterations, improvements, and modifications are intended to be suggested by this disclosure, and are within the spirit and scope of the exemplary embodiments of this disclosure.

Moreover, certain terminology has been used to describe embodiments of the present disclosure. For example, the terms “one embodiment, ” “an embodiment, ” and/or “some embodiments” mean that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment of the present disclosure. Therefore, it is emphasized and should be appreciated that two or more references to “an embodiment” or “one embodiment” or “an alternative embodiment” in various portions of this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures or characteristics may be combined as suitable in one or more embodiments of the present disclosure.

Further, it will be appreciated by one skilled in the art, aspects of the present disclosure may be illustrated and described herein in any of a number of patentable classes or context including any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof. Accordingly, aspects of the present disclosure may be implemented entirely hardware, entirely software (including firmware, resident software, micro-code, etc. ) or combining software and hardware implementation that may all generally be referred to herein as a “unit, ” “module, ” or “system. ” Furthermore, aspects of the present disclosure may take the form of a computer program product embodied in one or more computer readable media having computer readable program code embodied thereon.

A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including electro-magnetic, optical, or the like, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that may communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device. Program code embodied on a computer readable signal medium may be transmitted using any appropriate medium, including wireless, wireline, optical fiber cable, RF, or the like, or any suitable combination of the foregoing.

Computer program code for carrying out operations for aspects of the present disclosure may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Scala, Smalltalk, Eiffel, JADE, Emerald, C++, C#, VB. NET, Python or the like, conventional procedural programming languages, such as the "C" programming language, Visual Basic, Fortran 2003, Perl, COBOL 2002, PHP, ABAP, dynamic programming languages such as Python, Ruby and Groovy, or other programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN) , or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider) or in a cloud computing environment or offered as a service such as a Software as a Service (SaaS) .

In some embodiments, the numbers expressing quantities, properties, and so forth, used to describe and claim certain embodiments of the application are to be understood as being modified in some instances by the term “about, ” “approximate, ” or “substantially. ” For example, “about, ” “approximate, ” or “substantially” may indicate ±20%variation of the value it describes, unless otherwise stated. Accordingly, in some embodiments, the numerical parameters set forth in the written description and attached claims are approximations that may vary depending upon the desired properties sought to be obtained by a particular embodiment. In some embodiments, the numerical parameters should be construed in light of the number of reported significant digits and by applying ordinary rounding techniques. Notwithstanding that the numerical ranges and parameters setting forth the broad scope of some embodiments of the application are approximations, the numerical values set forth in the specific examples are reported as precisely as practicable.

Furthermore, the recited order of processing elements or sequences, or the use of numbers, letters, or other designations therefore, is not intended to limit the claimed processes and methods to any order except as may be specified in the claims. Although the above disclosure discusses through various examples what is currently considered to be a variety of useful embodiments of the disclosure, it is to be understood that such detail is solely for that purpose, and that the appended claims are not limited to the disclosed embodiments, but, on the contrary, are intended to cover modifications and equivalent arrangements that are within the spirit and scope of the disclosed embodiments. For example, although the implementation of various components described above may be embodied in a hardware device, it may also be implemented as a software only solution, e.g., an installation on an existing server or mobile device.

Similarly, it should be appreciated that in the foregoing description of embodiments of the present disclosure, various features are sometimes grouped together in a single embodiment, figure, or description thereof for the purpose of streamlining the disclosure aiding in the understanding of one or more of the various embodiments. This method of disclosure, however, is not to be interpreted as reflecting an intention that the claimed subject matter requires more features than are expressly recited in each claim. Rather, claimed subject matter may lie in less than all features of a single foregoing disclosed embodiment.

Claims

A system configured to determine a two-dimensional map, comprising:

at least one storage medium including a set of instructions; and

at least one processor in communication with the at least one storage medium, wherein when executing the set of instructions, the at least one processor is directed to:

obtain a pose graph of a region, wherein the pose graph includes a plurality of route-tracking datasets in the region, and each of the plurality of route-tracking datasets includes a plurality of nodes;

determine at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region, wherein at least two of the plurality of route-tracking datasets overlap at one of the at least one overlapped sub-region and the at least two of the plurality of route-tracking datasets satisfy a condition;

determine a plurality of layers of roads in the region based on the at least one overlapped sub-region; and

determine a target map based on the plurality of layers of roads and the pose graph.
The system of claim 1, wherein to determine that the at least two of the plurality of route-tracking datasets satisfy the condition, the at least one processor is directed to:

determine whether a height difference between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two of the plurality of route-tracking datasets is greater than a threshold; and

in response to a determination that the height difference is greater than the threshold, determine that the at least two of the plurality of route-tracking datasets satisfy the condition.
The system of claim 1 or 2, wherein to determine that the at least two of the plurality of route-tracking datasets satisfy the condition, the at least one processor is directed to:

determine whether a geometric match degree between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two of the plurality of route-tracking datasets is smaller than a threshold; and

in response to a determination that the geometric match degree is smaller than the threshold, determine that the at least two of the plurality of route-tracking datasets satisfy the condition.
The system of any one of claims 1-3, wherein to determine the at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region, the at least one processor is directed to:

determine whether more than one of the plurality of route-tracking datasets belongs to a same road based on text information; and

in response to a determination that the more than one of the plurality of route-tracking datasets belongs to the same road, keep one of the more than one of the plurality route-tracking datasets.
The system of any one of claims 1-4, wherein to determine the plurality of layers of roads in the region based on the at least one overlapped sub-region, the at least one of processor is directed to:

for each of the at least one overlapped sub-region,

classify at least a portion of the plurality of nodes into a plurality of groups, wherein the plurality of groups correspond to the plurality of layers of roads in the overlapped sub-region,

determine an area containing the at least a portion of the plurality nodes in each of the plurality of groups; and

determine a boundary of each of the plurality of layers of roads in the overlapped sub-region based on the areas.
The system of claim 5, wherein to determine the boundary of each of the plurality of layers of roads in the overlapped sub-region based on the areas, the at least one processor is directed to:

expand a portion of the areas; and

determine the boundary of each of the plurality of layers of roads in the overlapped sub-region based on the expanded areas.
The system of claim 6, wherein to expand the portion of the areas, the at least one of processor is directed to:

determine a bounding box corresponding to each of the plurality of nodes;

determine whether an overlapped degree between any two corresponding bounding boxes of the bounding box located within a neighboring area and the area, respectively, is greater than a threshold; and

in response to a determination that the overlapped degree is greater than the threshold, expand the area by including the node located in the neighboring area to the area.
The system of any one of claims 1-7, wherein to determine the target map based on the pose graph, the at least one of processor is directed to:

determine a sub map for each of the plurality of layers of roads based on the pose graph; and

determine the target map based on the sub maps.
The system of any one of claims 1-8, wherein the at least one overlapped sub-region corresponds to at least one of: an interchange, an overpass, or a viaduct.
The system of any one of claims 1-9, wherein the region further includes one or more sub-regions other than the at least one overlapped sub-region, and the at least one processor is further directed to:

determine the one or more sub-regions other than the at least one overlapped sub-region as one of the plurality of layers of roads based on the sub-regions.
A method implemented on a computing device having at least one processor, at least one storage medium, and a communication platform connected to a network, the method comprising:

obtaining a pose graph of a region, wherein the pose graph includes a plurality of route-tracking datasets in the region, and each of the plurality of route-tracking datasets includes a plurality of nodes;

determining at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region, wherein at least two of the plurality of route-tracking datasets overlap at one of the at least one overlapped sub-region and the at least two of the plurality of route-tracking datasets satisfy a condition;

determining a plurality of layers of roads in the region based on the at least one overlapped sub-region; and

determining a target map based on the plurality of layers of roads and the pose graph.
The method of claim 11, wherein the determining that the at least two of the plurality of route-tracking datasets satisfy the condition includes:

determining whether a height difference between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two of the plurality of route-tracking datasets is greater than a threshold; and

in response to a determination that the height difference is greater than the threshold, determining that the at least two of the plurality of route-tracking datasets satisfy the condition.
The method of claim 11 or 12, wherein the determining that the at least two of the plurality of route-tracking datasets satisfy the condition includes:

determining whether a geometric match degree between any two corresponding nodes of the plurality nodes included in any two route-tracking datasets of the at least two of the plurality of route-tracking datasets is smaller than a threshold; and

in response to a determination that the geometric match degree is smaller than the threshold, determining that the at least two of the plurality of route-tracking datasets satisfy the condition.
The method of any one of claims 11-13, wherein the determining the at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region includes:

determining whether more than one of the plurality of route-tracking datasets belongs to a same road based on text information; and

in response to a determination that the more than one of the plurality of route-tracking datasets belongs to the same road, keeping one of the more than one of the plurality route-tracking datasets.
The method of any one of claims 11-14, wherein the determining the plurality of layers of roads in the region based on the at least one overlapped sub-region includes:

for each of the at least one overlapped sub-region,

classifying at least a portion of the plurality of nodes into a plurality of groups, wherein the plurality of groups correspond to the plurality of layers of roads in the overlapped sub-region;

determining an area containing the at least a portion of the plurality nodes in each of the plurality of groups; and

determine a boundary of each of the plurality of layers of roads in the overlapped sub-region based on the areas.
The method of claim 15, wherein the determining the boundary of each of the plurality of layers of roads in the overlapped sub-region based on the areas includes:

expanding a portion of the areas; and

determining the boundary of each of the plurality of layers of roads in the overlapped sub-region based on the expanded areas.
The method of claim 16, wherein the expanding the portion of the areas includes:

determining a bounding box corresponding to each of the plurality of nodes;

determining whether an overlapped degree between any two corresponding bounding boxes of the bounding box located within a neighboring area and the area, respectively, is greater than a threshold; and

in response to a determination that the overlapped degree is greater than the threshold, expanding the area by including the node located in the neighboring area to the area.
The method of any one of claims 11-17, wherein the determining the target map based on the pose graph includes:

determining a sub map for each of the plurality of layers of roads based on the pose graph; and

determining the target map based on the sub maps.
The method of any one of claims 11-18, wherein the at least one overlapped sub-region corresponds to at least one of: an interchange, an overpass, or a viaduct.
The method of any one of claims 11-19, wherein the region further includes one or more sub-regions other than the at least one overlapped sub-region, the method further includes:

determining the one or more sub-regions other than the at least one overlapped sub-region as one of the plurality of layers of roads based on the sub-regions.
A non-transitory computer readable medium, comprising executable instructions that, when executed by at least one processor, directs the at least one processor to perform a method, the method comprising:

obtaining a pose graph of a region, wherein the pose graph includes a plurality of route-tracking datasets in the region, and each of the plurality of route-tracking datasets includes a plurality of nodes;

determining at least one overlapped sub-region included in the region based on the plurality of route-tracking datasets in the region, wherein at least two of the plurality of route-tracking datasets overlap at one of the at least one overlapped sub-region and the at least two of the plurality of route-tracking datasets satisfy a condition;

determining a plurality of layers of roads in the region based on the at least one overlapped sub-region; and

determining a target map based on the plurality of layers of roads and the pose graph.