SYSTEM AND METHOD FOR GENERATING LINEAR FEATURE DATA ASSOCIATED WITH ROAD LANES

A system for generating linear feature data is provided. The system may determine, from sensor data, detection data associated with at least one link. The at least one link comprises a plurality of sub links. The system may further determine, using map data, one or more linear feature clusters for each of the plurality of sub links, based on the detection data. Furthermore, the system may determine a plurality of linear feature groups for the at least one link, based on at least one set of feature matched distances and the determined linear feature clusters, where a given linear feature group respectively comprises at least one first linear feature cluster associated with a first sub link and at least one second linear feature cluster associated with a second sub link. Furthermore, the system may generate the linear feature data, based on the plurality of linear feature groups.

TECHNOLOGICAL FIELD

The present disclosure generally relates to routing and navigation systems, and more particularly relates to methods and systems for generating linear feature data in routing and navigation systems.

BACKGROUND

Currently, various navigation systems are available for vehicle navigation. These navigation systems generally request navigation related data or map data thereof from a navigation service. The map data stored in the navigation service may be updated by using sensor data aggregated from various vehicles. The sensor data may include data about linear feature detections indicative of lane markings, guardrails, roadwork zones, roadwork extensions and the like on a route. The navigation systems based on such navigation related data may be used for vehicle navigation of autonomous, semi-autonomous, or manual vehicles.

Therefore, the sensor data should be accurate to help enable reliable vehicle navigation or the like. However, in many cases, the sensor data may not be accurate or reliable.

BRIEF SUMMARY OF SOME EXAMPLE EMBODIMENTS

Generally, the sensor data that include the data about the linear feature detections may not be accurate, due to occlusions (caused by interference of other vehicles), noise in sensors, or other defects in the sensors. Hereinafter, the ‘data about the linear feature detections’ and ‘detection data’ may be interchangeably used to mean the same.

In order to solve the foregoing problem, a system, a method, and a computer program product are provided in accordance with an example embodiment for generating linear feature data.

In one aspect, a system for generating the linear feature data is disclosed. The system comprises a memory configured to store computer-executable instructions; and at least one processor configured to execute the computer-executable instructions to: determine, from sensor data, detection data associated with at least one link, wherein the at least one link comprises a plurality of sub links; determine, using map data, one or more linear feature clusters respectively for each of the plurality of sub links, based on the detection data, wherein the one or more linear feature clusters are associated with at least one set of feature matched distances, wherein the at least one set of feature matched distances comprises a respective feature matched distance for each linear feature cluster; determine a plurality of linear feature groups for the at least one link, based on the at least one set of feature matched distances and the determined one or more linear feature clusters, wherein a given linear feature group respectively comprises at least a first linear feature cluster associated with a first sub link and at least a second linear feature cluster associated with a second sub link; and generate the linear feature data, based on the determined plurality of linear feature groups.

In additional system embodiments, determining the plurality of linear feature groups comprises group the first linear feature cluster and the second linear feature cluster into a linear feature group, when a difference between (i) the respective feature matched distance of the first linear feature cluster and (ii) the respective feature matched distance of the second linear feature cluster is less than a threshold difference value.

In additional system embodiments, determining the one or more linear feature clusters for a sub link of the plurality of sub links comprises: identify, from the detection data, a plurality of linear feature points associated with the sub link; determine, using the map data, a matched distance for each of the plurality of linear feature points associated with the sub link; and determine a linear feature cluster for the sub link based on a clustering criteria, wherein the clustering criteria comprises the determined matched distance, and wherein each linear feature cluster of the one or more linear feature clusters of the sub link comprises one or more linear feature point with identical matched distances.

In additional system embodiments, the feature matched distance associated with the linear feature cluster of the one or more linear feature clusters is a weighted median of the corresponding matched distances associated with the linear feature cluster.

In additional system embodiments, the at least one processor is further configured to remove diagonal detection data from the detection data, wherein the diagonal detection data comprises at least two linear feature points, and wherein each of the at least two linear feature points is associated with a different linear feature cluster in the one or more linear feature clusters.

In additional system embodiments, the at least one processor is further configured to update the map data to include the generated linear feature data for the at least one link.

In additional system embodiments, the at least one processor is further configured to: determine a status of the detection data associated with the at least one link, wherein the status of the detection data comprises at least one of discontinuous detection data or continuous detection data; and determine the one or more linear feature clusters respectively for each of the plurality of sub links, in response to determining the status of the detection data is the discontinuous detection data.

In additional system embodiments, determining the detection data associated with the at least one link comprises: obtain the sensor data; map-match, using the map data, the sensor data to identify the at least one link; and determine, from the sensor data, the detection data associated with the identified at least one link.

In another aspect, a method for generating linear feature data is provided. The method includes: determining, from sensor data, detection data associated with at least one link, wherein the at least one link comprises a plurality of sub links; determining, using map data, one or more linear feature clusters respectively for each of the plurality of sub links, based on the detection data, wherein the one or more linear feature clusters are associated with at least one set of feature matched distances, wherein the at least one set of feature matched distances comprises a respective feature matched distance for each linear feature cluster; determining a plurality of linear feature groups for the at least one link, based on the at least one set of feature matched distances and the determined one or more linear feature clusters, wherein a given linear feature group respectively comprises at least a first linear feature cluster associated with a first sub link and at least a second linear feature cluster associated with a second sub link; and generating the linear feature data, based on the determined plurality of linear feature groups.

In additional method embodiments, determining the plurality of linear feature groups further comprises grouping the first linear feature cluster and the second linear feature cluster into a linear feature group, based on (i) the respective feature matched distance of the first linear feature cluster and (ii) the respective feature matched distance the second linear feature cluster substantially matching one another.

In additional method embodiments, determining the one or more linear feature clusters for a sub link of the plurality of sub links comprises: identifying, from the detection data, a plurality of linear feature points associated with the sub link; determining, using the map data, a matched distance for each of the plurality of linear feature points associated with the sub link; and determining a linear feature cluster for the sub link based on a clustering criteria, wherein the clustering criteria comprises the determined matched distance, and wherein each linear feature cluster of the one or more linear feature clusters of the sub link comprises one or more linear feature points with identical matched distances.

In additional method embodiments, the feature matched distance associated with the linear feature cluster of the one or more linear feature clusters is a weighted median of the corresponding matched distances associated with the linear feature cluster.

In additional method embodiments, the method further comprises removing diagonal detection data from the detection data, wherein the diagonal detection data comprises at least two linear feature points, and wherein each of the at least two linear feature points is associated with a different linear feature cluster in the one or more linear feature clusters.

In additional method embodiments, the method further comprises updating the map data to include the generated linear feature data for the at least one link.

In yet another aspect, a computer program product comprising a non-transitory computer readable medium having stored thereon computer executable instruction which when executed by at least one processor, cause the at least one processor to carry out operations for generating linear feature data, the operations comprising: determining, from sensor data, detection data associated with at least one link, wherein the at least one link comprises a plurality of sub links; determining, using map data, one or more linear feature clusters respectively for each of the plurality of sub links, based on the detection data, wherein the one or more linear feature clusters are associated with at least one set of feature matched distances, wherein the at least one set of feature matched distances comprises a respective feature matched distance for each linear feature cluster; determining a plurality of linear feature groups for the at least one link, based on the at least one set of feature matched distances and the determined one or more linear feature clusters, wherein a given linear feature group respectively comprises at least a first linear feature cluster associated with a first sub link and at least a second linear feature cluster associated with a second sub link; and generating the linear feature data, based on the determined plurality of linear feature groups.

In additional computer program product embodiments, for determining the plurality of linear feature groups, the operations further comprise grouping the first linear feature cluster and the second linear feature cluster into a linear feature group, when a difference between (i) the respective feature matched distance of the first linear feature cluster and (ii) the respective feature matched distance of the second linear feature cluster is less than a threshold difference value.

In additional computer program product embodiments, for determining the one or more linear feature clusters for a sub link of the plurality of sub links, the operations further comprise: identifying, from the detection data, a plurality of linear feature points associated with the sub link; determining, using the map data, a matched distance for each of the plurality of linear feature points associated with the sub link; and determining a linear feature cluster for the sub link based on a clustering criteria, wherein the clustering criteria comprises the determined matched distances, and wherein each linear feature cluster of the one or more linear feature clusters of the sub link comprises one or more linear feature points with identical matched distances.

In additional computer program product embodiments, the feature matched distance associated with the linear feature cluster of the one or more linear feature clusters is a weighted median of the corresponding matched distances associated with the linear feature cluster.

In additional computer program product embodiments, the operations further comprise removing diagonal detection data from the detection data, wherein the diagonal detection data includes at least two linear feature points, and wherein each of the at least two linear feature points is associated with a different linear feature cluster in the one or more linear feature clusters.

In additional computer program product embodiments, the operations further comprise updating the map data to include the generated linear feature data for the at least one link.

DETAILED DESCRIPTION

Reference in this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present disclosure. The appearance of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. Further, the terms “a” and “an” herein do not denote a limitation of quantity, but rather denote the presence of at least one of the referenced items. Moreover, various features are described which may be exhibited by some embodiments and not by others. Similarly, various requirements are described which may be requirements for some embodiments but not for other embodiments.

As defined herein, a “computer-readable storage medium,” which refers to a non-transitory physical storage medium (for example, volatile or non-volatile memory device), may be differentiated from a “computer-readable transmission medium,” which refers to an electromagnetic signal.

A system, a method, and a computer program product are provided for generating the linear feature data. Various embodiments are provided for determining, from sensor data, detection data associated with the at least one link. Hereinafter, ‘detection data’ and ‘linear feature detection data’ may be interchangeably used to mean the same. For instance, the liner feature detection data may include a plurality of linear feature points, where each linear feature point may indicate data (e.g., image data) of a linear feature. As used herein, the linear feature may correspond to a border of a link (and/or a border of a lane of the link), where the border may be represented by one or more of lane markings, guardrails, road curbs, road medians, road barriers, and the like. In some embodiments, the at least one link may include a plurality of sub links.

Various embodiments are provided for determining, using map data, one or more linear feature clusters for each of the plurality of sub links, based on the linear feature detection data. In some example embodiments, the one or more linear feature clusters may be determined based on a clustering criteria. In some embodiments, the one or more linear feature clusters may be associated with at least one set of feature matched distances, where the at least one set of feature matched distances includes a respective feature matched distance for each linear feature cluster.

Various embodiments are provided for determining a plurality of linear feature groups for the at least one link, based on the at least one set of feature matched distances and the determined one or more linear feature clusters, where a given linear feature group respectively includes at least a first linear feature cluster associated with a first sub link and at least a second linear feature cluster associated with a second sub link. The first sub link and the second sub link are adjacent to each other in the plurality of sub links. In some embodiments, the first linear feature cluster and the second linear feature cluster may be grouped if a difference between the respective feature matched distance of the first linear feature cluster and the respective feature matched distance of the second linear feature cluster is less than a threshold difference value.

Various embodiments are provided for generating the linear feature data, based on the determined plurality of linear feature groups. In various embodiments, the generated linear feature data may be used to update the map data and/or to provide one or more navigation functions. Some non-limiting examples of the navigation functions includes providing vehicle speed guidance, vehicle speed handling and/or control, providing a route for navigation (e.g., via a user interface), localization, route determination, lane level speed determination, operating the vehicle along a lane level route, route travel time determination, lane maintenance, route guidance, provision of traffic information/data, provision of lane level traffic information/data, vehicle trajectory determination and/or guidance, route and/or maneuver visualization, and/or the like.

FIG.1illustrates a block diagram100showing a network environment of a system101for generating the linear feature data, in accordance with one or more example embodiments. The system101may be communicatively coupled, via a network105, to one or more of a mapping platform103, a user equipment107a, and/or an OEM (Original Equipment Manufacturer) cloud109. The OEM cloud109may be further connected to a user equipment107b. The components described in the block diagram100may be further broken down into more than one component such as one or more sensors or application in user equipment and/or combined together in any suitable arrangement. Further, it is possible that one or more components may be rearranged, changed, added, and/or removed without deviating from the scope of the present disclosure.

In an example embodiment, the system101may be embodied in one or more of several ways as per the required implementation. For example, the system101may be embodied as a cloud-based service, a cloud-based application, a cloud-based platform, a remote server-based service, a remote server-based application, a remote server-based platform, or a virtual computing system. As such, the system101may be configured to operate inside the mapping platform103and/or inside at least one of the user equipment107aand the user equipment107b.

In some embodiments, the system101may be embodied within one or both of the user equipment107aand the user equipment107b, for example as a part of an in-vehicle navigation system, a navigation app in a mobile device and the like. In each of such embodiments, the system101may be communicatively coupled to the components shown inFIG.1to carry out the desired operations and wherever required modifications may be possible within the scope of the present disclosure. The system101may be implemented in a vehicle, where the vehicle may be an autonomous vehicle, a semi-autonomous vehicle, or a manually driven vehicle. In an embodiment, the system101may be deployed in a consumer vehicle to generate the linear feature data.

In some other embodiments, the system101may be a server103bof the mapping platform103and therefore may be co-located with or within the mapping platform103. In yet other embodiments, the system101may be implemented within an OEM (Original Equipment Manufacturer) cloud, such as the OEM cloud109. The OEM cloud109may be configured to anonymize any data received from the system101, such as the vehicle, before using the data for further processing, such as before sending the data to the mapping platform103. In some embodiments, anonymization of data may be done by the mapping platform103. Further, in yet other embodiments, the system101may be a standalone unit configured to generate the linear feature data for the autonomous vehicle. Additionally, the system101may be coupled with an external device such as the autonomous vehicle.

The mapping platform103may include a map database103a(also referred to as geographic database103a) for storing map data and a processing server103bfor carrying out the processing functions associated with the mapping platform103. The map database103amay store node data, road segment data or link data, point of interest (POI) data, road obstacles related data, traffic objects related data, posted signs related data, such as road sign data, or the like. The map database103amay also include cartographic data and/or routing data. According to some example embodiments, the link data may be stored in link data records, where the link data may represent links or segments representing roads, streets, or paths, as may be used in calculating a route or recorded route information for determination of one or more personalized routes. The node data may be stored in node data records, where the node data may represent end points corresponding to the respective links or segments of the road segment data. One node represents a point at one end of the respective link and the other node represents a point at the other end of the respective link. The node at either end of a link corresponds to a location at which the road meets another road, e.g., an intersection, or where the road dead ends. An intersection may not necessarily be a place at which a turn from one road to another is permitted but represents a location at which one road and another road have the same latitude, longitude, and elevation. In some cases, a node may be located along a portion of a road between adjacent intersections, e.g., to indicate a change in road attributes, a railroad crossing, or for some other reason. (The terms “node” and “link” represent only one terminology for describing these physical geographic features and other terminology for these features is intended to be encompassed within the scope of these concepts.) The link data and the node data may represent a road network used by vehicles such as cars, trucks, buses, motorcycles, and/or other entities.

Additionally, the map database103amay contain path segment and node data records, or other data that may represent pedestrian paths or areas in addition to or instead of the vehicle road record data, for example. The links/road segments and nodes may be associated with attributes, such as geographic coordinates and other navigation related attributes, as well as POIs, such as fueling stations, hotels, restaurants, museums, stadiums, offices, auto repair shops, buildings, stores, parks, etc. The navigation related attributes may include one or more of travel speed data (e.g. data indicative of a permitted speed of travel) on the road represented by the link data record, a travel direction data (e.g. data indicative of a permitted direction of travel) on the road represented by the link data record, the linear feature data on the road represented by the link data record, street address ranges of the road represented by the link data record, the name of the road represented by the link data record, and the like. As used herein, the ‘linear feature data’ may be data indicative of a linear feature along the road represented by the link data record. The linear feature may be at least one of lane markings, road curbs, guardrails, road medians, road barriers, and the like along the road. These various navigation related attributes associated with a link may be stored in a single data record or may be stored in more than one type of record.

Each link data record that represents other-than-straight link (for example, a curved link) may include shape location data. A shape location is a location along a link between its endpoints. For instance, to represent the shape of other-than-straight roads/links, a geographic database developer may select one or more shape locations along the link portion. The shape location data included in the link data record may indicate a position, (e.g., latitude, longitude, and optionally, altitude or elevation) of the selected shape point(s) along the represented link.

Additionally, the map database103amay also include data about the POIs and their respective locations in the POI records. The map database103amay further include data about places, such as cities, towns, or other communities, and other geographic features such as bodies of water, mountain ranges, etc. Such place or feature data may be part of the POI data or may be associated with POIs or POI data records (such as a data point used for displaying a city). In addition, the map database103amay include event data (e.g., traffic incidents, construction activities, scheduled events, unscheduled events, etc.) associated with the POI data records or other records of the map database103a.

The map database103amay be maintained by a content provider e.g., a map developer. By way of example, the map developer may collect the map data to generate and enhance the map database103a. There may be different ways used by the map developer to collect data. These ways may include obtaining data from other sources, such as municipalities or respective geographic authorities. In addition, the map developer may employ field personnel to travel by vehicle (also referred to as a dedicated vehicle) along roads throughout a geographic region to observe features and/or record information about them, for example. Also, remote sensing, such as aerial or satellite photography, may be used to collect the map data. In some example embodiments, the map data in the map database103amay be stored as a digital map. The digital map may correspond to satellite raster imagery, bitmap imagery, or the like. The satellite raster imagery/bitmap imagery may include map features (such as link/road segments, nodes, and the like) and the navigation related attributes associated with the map features. In some embodiments, the map features may have a vector representation form. Additionally, the satellite raster imagery may include three-dimensional (3D) map data that corresponds to 3D map features, which are defined as vectors, voxels, or the like.

According to some embodiments, the map database103amay be a master map database stored in a format that facilitates updating, maintenance and development. For example, the master map database or data in the master map database may be in an Oracle spatial format or other spatial format, such as for development or production purposes. The Oracle spatial format or development/production database may be compiled into a delivery format, such as a geographic data files (GDF) format. The data in the production and/or delivery formats may be compiled or further compiled to form geographic database products or databases, which may be used in end user navigation devices or systems.

For example, the map data may be compiled (such as into a platform specification format (PSF format)) to organize and/or configure the data for performing navigation-related functions and/or services, such as route calculation, route guidance, map display, speed calculation, distance and travel time functions, navigation instruction generation and other functions, by a navigation device, such as by the user equipment107aand/or107b. The navigation-related functions may correspond to vehicle navigation, pedestrian navigation, navigation instruction suppression, navigation instruction generation based on user preference data or other types of navigation. The compilation to produce the end user databases may be performed by a party or entity separate from a map developer. For example, a customer of the map developer, such as a navigation device developer or other end user device developer, a navigation app service provider and the like may perform compilation on a received map database in a delivery format to produce one or more compiled navigation databases.

As mentioned above, the map database103amay be a master geographic database, but in alternate embodiments, the map database103amay be embodied as a client-side map database and may represent a compiled navigation database that may be used in or with end user equipment such as the user equipment107aand/or the user equipment107bto provide navigation and/or map-related functions. For example, the map database103amay be used with the user equipment107aand/or the user equipment107bto provide an end user with navigation features. In such a case, the map database103amay be downloaded or stored locally (cached) on the user equipment107aand/or the user equipment107b.

The processing server103bmay include processing means, and communication means. For example, the processing means may include one or more processors configured to process requests received from the user equipment107aand/or the user equipment107b. The processing means may fetch map data from the map database103aand transmit the same to the user equipment107bvia the OEM cloud109in a format suitable for use by the one or both of the user equipment107aand/or the user equipment107b. In one or more example embodiments, the mapping platform103may periodically communicate with the user equipment107aand/or the user equipment107bvia the processing server103bto update a local cache of the map data stored on the user equipment107aand/or the user equipment107b. Accordingly, in some example embodiments, the map data may also be stored on the user equipment107aand/or the user equipment107band may be updated based on periodic communication with the mapping platform103via the network105.

In some example embodiments, the user equipment107aand the user equipment107bmay be any user accessible device such as a mobile phone, a smartphone, a portable computer, and the like that are portable in themselves or as a part of another portable/mobile object such as a vehicle. The user equipment107aand107bmay include a processor, a memory, and a communication interface. The processor, the memory, and the communication interface may be communicatively coupled to each other. In some example embodiments, the user equipment107aand107bmay be associated, coupled, or otherwise integrated with a vehicle, such as an advanced driver assistance system (ADAS), a personal navigation device (PND), a portable navigation device, an infotainment system and/or other device that may be configured to provide route guidance and navigation related functions to the user. In such example embodiments, the user equipment107aand107bmay include processing means such as a central processing unit (CPU), storage means such as on-board read only memory (ROM) and random access memory (RAM), acoustic sensors such as a microphone array, position sensors such as a GPS sensor, gyroscope, a LIDAR sensor, a proximity sensor, motion sensors such as accelerometer, a display enabled user interface such as a touch screen display, and other components as may be required for specific functionalities of the user equipment107aand107b. For example, the user equipment107aand107bmay be configured to execute and run mobile applications such as a messaging application, a browser application, a navigation application, and the like.

In one embodiment, at least one user equipment such as the user equipment107amay be directly coupled to the system101via the network105. For example, the user equipment107amay be a dedicated vehicle (or a part thereof) for gathering data for development of the map data stored in the map database103a. In another embodiment, at least one user equipment such as the user equipment107bmay be coupled to the system101via the OEM cloud109and the network105. For example, the user equipment107bmay be a consumer vehicle or a probe vehicle (or a part thereof) and may be a beneficiary of the services provided by the system101. In some example embodiments, one or more of the user equipment107aand107bmay serve the dual purpose of a data gatherer and a beneficiary device. At least one of the user equipment107aand107bmay be configured to capture sensor data associated with the link/road segment, while traversing along the link/road segment. For example, the sensor data may include image data of the linear feature along the link/road segment, among other things. The sensor data may be collected from one or more sensors in the user equipment107aand/or user equipment107b. As disclosed in conjunction with various embodiments disclosed herein, the system101may generate the linear feature data using the sensor data and the map database103adata.

FIG.2illustrates a block diagram200of the system101for generating the linear feature data, in accordance with one or more example embodiment. The system101may include at least one processor201, a memory203, and a communication interface205. Further, the system101may include a reception module201a, a linear feature detection module201b, a linear feature cluster determination module201b, a linear feature group determination module201d, and a linear feature generation module201e. In an embodiment, the reception module201amay be configured to obtain the sensor data. In an embodiment, the linear feature detection module201bmay be configured to determine, from the sensor data, linear feature data associated with at least one link. In an embodiment, the at least one link may include a plurality of sub links. In an embodiment, the linear feature cluster determination module201cmay be configured to determine, using map data, one or more linear feature clusters respectively for each of the plurality of sub links, based on the linear feature detection data. In an example embodiment, the one or more linear feature clusters may be associated with at least one set of feature matched distances, where the at least one set of feature matched distances include a feature matched distance for each linear feature cluster. In an embodiment, the linear feature group determination module201dmay be configured to generate a plurality of linear feature groups for the at least one link, based on the at least one set of feature matched distances, and the determined one or more linear feature clusters. For instance, a given linear feature group respectively includes at least a first linear feature cluster associated with the first sub link and at least a second linear feature cluster associated with a second link, where the first sub link and the second sub link are adjacent to each other within the plurality of sub links. In an embodiment, the linear feature generation module201emay be configured to generate the linear feature data, based on the determined plurality of linear feature groups.

According to an embodiment, each of the modules201a-201emay be embodied in the processor201. The processor201may retrieve computer-executable instructions that may be stored in the memory203for execution of the computer-executable instructions, which when executed configures the processor201for generating the linear feature data.

Additionally, or alternatively, the processor201may include one or more processors capable of processing large volumes of workloads and operations to provide support for big data analysis. In an example embodiment, the processor201may be in communication with the memory203via a bus for passing information to mapping platform103. The memory203may be non-transitory and may include, for example, one or more volatile and/or non-volatile memories. In other words, for example, the memory203may be an electronic storage device (for example, a computer readable storage medium) comprising gates configured to store data (for example, bits) that may be retrievable by a machine (for example, a computing device like the processor201). The memory203may be configured to store information, data, content, applications, instructions, or the like, for enabling the system101to carry out various functions in accordance with an example embodiment of the present disclosure. For example, the memory203may be configured to buffer input data for processing by the processor201. As exemplarily illustrated inFIG.2, the memory203may be configured to store instructions for execution by the processor201. As such, whether configured by hardware or software methods, or by a combination thereof, the processor201may represent an entity (for example, physically embodied in circuitry) capable of performing operations according to an embodiment of the present disclosure while configured accordingly. Thus, for example, when the processor201is embodied as an ASIC, FPGA or the like, the processor201may be specifically configured hardware for conducting the operations described herein. Alternatively, as another example, when the processor201is embodied as an executor of software instructions, the instructions may specifically configure the processor201to perform the algorithms and/or operations described herein when the instructions are executed. However, in some cases, the processor201may be a processor specific device (for example, a mobile terminal or a fixed computing device) configured to employ an embodiment of the present invention by further configuration of the processor201by instructions for performing the algorithms and/or operations described herein. The processor201may include, among other things, a clock, an arithmetic logic unit (ALU) and logic gates configured to support operation of the processor201.

In some embodiments, the processor201may be configured to provide Internet-of-Things (IoT) related capabilities to a user of the system101, where the user may be a traveler, a driver of the vehicle and the like. In some embodiments, the user may be or correspond to an autonomous or semi-autonomous vehicle. The IoT related capabilities may in turn be used to provide smart navigation solutions by providing real time updates to the user to take pro-active decision on lane maintenance, speed determination, lane-level speed determination, turn-maneuvers, lane changes, overtaking, merging and the like. The system101may be accessed using the communication interface205. The communication interface205may provide an interface for accessing various features and data stored in the system101. For example, the communication interface205may include I/O interface which may be in the form of a GUI, a touch interface, a voice enabled interface, a keypad, and the like. For example, the communication interface205may be a touch enabled interface of a navigation device installed in a vehicle, which may also display various navigation related data to the user of the vehicle. Such navigation related data may include information about upcoming conditions on a route, route display and alerts about lane maintenance, turn-maneuvers, vehicle speed, and the like.

FIG.3Aillustrates a first working environment300aof the system101for generating the linear feature data, in accordance with one or more example embodiments. As illustrated inFIG.3A, the first working environment300aincludes the system101, the mapping platform103, the network105, a plurality of vehicles301,303, and305, a link307, linear features311,313,315and317associated with the link307. Each of the plurality of vehicles301,303, and305may correspond to any one of: an autonomous vehicle, a semi-autonomous vehicle, or a manual vehicle. As used herein, the autonomous vehicle may be a vehicle that is capable of sensing its environment and operating without human involvement. For instance, the autonomous vehicle may be a self-driving car and the like. As used herein, the ‘vehicle’ may include a motor vehicle, a non-motor vehicle, an automobile, a car, a scooter, a truck, a van, a bus, a motorcycle, a bicycle, a Segway, and/or the like.

As used herein, the ‘link’ (e.g., the link307) may be a road segment between two nodes. The link307may be a freeway, an expressway, a highway, or the like. The link307may include three lanes309a,309b, and309c, as illustrated inFIG.3A. For purpose of explanation, the link307comprising three lanes309a,309b, and309cis considered, however the link307may include any finite number of lanes without deviating from the scope of the present disclosure.

Each of the lanes309a,309b, and309cmay be identified (or defined) by at least two linear features. As used herein, the ‘linear feature’ may be a border (or a boundary) of one particular lane of a link (e.g., the link307), a border (or a boundary) of the link, and/or a shared border (or a shared boundary) between two lanes of the links. For instance, the lane309amay be identified by the linear features311and313. Similarly, the lane309bmay be identified by the linear features313and315and the lane309cmay be identified by the linear features315and317. For instance, the linear features311and317may the borders of the link307. For instance, the linear feature313may be the shared boarder between the lanes309aand309b. Similarly, the linear feature315may be the shared boarder between the lanes309band309c. The linear features311,313,315, and317may include, but are not limited to, at least one of the lane markings, the guardrails, the road curbs, the road medians, and/or the road barriers.

Some embodiments are based on the recognition that the linear features311,313,315, and317may be used in vehicle navigation for assisting the vehicles301,303, and/or305. For instance, the linear features311,313,315, and317may be used in lane maintenance application. To this end, in some embodiments, the vehicles301,303, and/or305may be equipped with various sensors to capture the linear features311,313,315, and317. For instance, the sensors may include a radar system, a LiDAR system, a global positioning sensor for gathering location data (e.g., GPS), image sensors, temporal information sensors, orientation sensors augmented with height sensors, tilt sensors, and the like. In some example embodiments, the sensors may collect the linear features311,313,315, and317as linear feature points, leading to linear feature detection data. In these embodiments, sensor data obtained from the sensors include the linear feature detection data, among other things. For instance, each linear feature point in the linear feature detection data may represent image data corresponding to at least one of the linear features309,311,313, and315.

However, in most of cases, the sensors may fail to continuously capture the linear features311,313,315, and317, leading to discontinuities in the linear feature detection data. For instance, the sensors may fail to continuously capture the linear features311,313,315, and317, due to occlusions (caused by interference of other vehicles), noise in the sensors, or other defects in the sensors. In other words, the discontinuities in the linear feature detection data may occur when the sensors fail to completely capture the linear features311,313,315, and317. As a result, a gap may be formed between any two consecutive linear feature points in the linear feature detection data. As used herein, the gap between any two consecutive linear feature points may be indicative of a distance of discontinuity. Hereinafter, the ‘discontinuities in the linear feature detection data’ and ‘discontinuous detection data’ may be interchangeably used to mean the same. In some instances, the gap between two consecutive linear feature points may be huge. For instance, the gap may be greater than a threshold distance of discontinuity. In these cases, the gap should not be complemented (filled) using a heading-and-distance-bound algorithm. According to the heading-and-distance-bound algorithm, the gap between two consecutive linear feature points may be complemented, if a heading difference of the two consecutive linear feature points is within a threshold heading value and the distance between the two consecutive linear feature points is less than the threshold distance of discontinuity.

Further, the linear feature data extracted from the sensor data may include lateral position error data, when (i) the vehicle(s) is not propagating within the lanes and/or (ii) there are defects in the sensor. Furthermore, the linear feature data extracted from the sensor data may include diagonal detection data when the vehicle(s) is propagating from one lane to another lane.

Thereby, the linear feature detection data extracted from the sensor data may not be accurate to provide the vehicle navigation. Furthermore, if this inaccurate linear feature detection data is used in the vehicle navigation, a vehicle may end-up with unwanted conditions such as entering a wrong lane, road accidents, traffic congestions, vehicle efficiency reduction, environmental pollutions, and the like. To this end, when the linear feature detection data is inaccurate, the system101is provided for generating the linear feature data from the in accurate linear feature detection data such that the unwanted conditions are avoided. Further, to generate the linear feature data, the system101may be configured as explained in the detailed description ofFIG.3B-FIG.3E.

FIG.3Billustrates a schematic diagram300bfor determining, from the sensor data, the linear feature detection data associated with the link307, in accordance with one or more example embodiments.FIG.3Bis explained in conjunction withFIG.3A. As illustrated inFIG.3B, the schematic diagram300bmay include linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, a plurality of sub links307aand307b, and a plurality of nodes347a,347b, and347c. In an embodiment, the system101may be configured to obtain, from the sensors, the sensor data. For instance, the reception module201amay obtain the sensor data from the sensors. In an embodiment, the sensor data may include the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345. For instance, the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345may be obtained from a plurality of vehicles (e.g., the vehicles301,303, and305). The linear feature detection data319,321,323, and325may correspond to the linear feature311of the link307. The linear feature detection data327,329, and331may correspond to the linear feature313of the link307. The linear feature detection data333,335,337, and339may correspond to the linear feature315of the link307. The linear feature detection data341,343, and345may correspond to the linear feature317of the link307. In an embodiment, each of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345may include a plurality of linear feature points. For instance, the linear feature detection data319may include a plurality of linear feature points319a, where each linear feature point319amay be data (e.g., image data) associated with the corresponding linear feature, such as the linear feature311corresponding to the linear feature detection data319. Similarly, the linear feature detection data321may include a plurality of linear feature points321a, the linear feature detection data323may include a plurality of linear feature points323a, the linear feature detection data325may include a plurality of linear feature points325a, the linear feature detection data327may include a plurality of linear feature points327a, the linear feature detection data329may include a plurality of linear feature points329a, the linear feature detection data331may include a plurality of linear feature points331a, the linear feature detection data333may include a plurality of linear feature points333a, the linear feature detection data335may include a plurality of linear feature points335a, the linear feature detection data337may include a plurality of linear feature points337a, the linear feature detection data339may include a plurality of linear feature points339a, the linear feature detection data341may include a plurality of linear feature points341a, the linear feature detection data343may include a plurality of linear feature points343a, and the linear feature detection data345may include a plurality of linear feature points345a.

In an example embodiment, the sensor data may further include time stamp data, vehicle location data, and lateral position data along with the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345. The time stamp data may include a time stamp for each linear feature point of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345. As used herein, the time stamp may indicate a time instance at which a particular linear feature point was recorded by the sensors. The vehicle location data may include a vehicle location for each linear feature point of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345. As used herein, the vehicle location may indicate a location of a vehicle at where a particular linear feature point was recorded by the sensors.

The lateral position data may include a lateral position distance for each linear feature point of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345. As used herein, the lateral position distance may be a distance from the vehicle to a particular linear feature point recorded by the sensors. In some embodiments, the lateral position distance may be associated with a sign (e.g., a positive sign or a negative sign). For instance, the lateral position distance with the positive sign may indicate that the particular linear feature point is located on right side with respect to the vehicle in a direction of travel of the vehicle. Conversely, the lateral position distance with the negative sign may indicate that the particular linear feature point is located on left side with respect to the vehicle in a direction of travel of the vehicle.

For example, once the system101receives the sensor data (e.g., the linear feature points319a, the time stamp data associated with the linear feature points319a, the vehicle location data associated with the linear feature points319a, and the lateral position data associated with the linear feature points319a), the system101may be configured to identify, using the map data stored in the map database103a, the link307based on the sensor data. For instance, the system101(e.g., linear feature detection module201b) may map-match the sensor data (specifically, the vehicle location data) with the map data to identify the link307. In various embodiments, the link307may be identified as at least one vector line. In some example embodiments, when the link307corresponds to the other-than-straight road segment (e.g., a curved link), the system101may be configured to identify, using the map data, the plurality of nodes347a,347b, and347cassociated with the link307. For instance, the node347amay be a start node of the link307, the node307cmay be an end node of the link307, and the node307bmay be a shape location between the nodes307aand307c. For example, the node307bmay be used to represent the curvature nature of the link307. In other words, the node307bmay divide the link307(represented by the vector line) into at least two sub links307aand307b. Accordingly, when the link307corresponds to the other-than-straight road segment, the system101may be configured to identify at least two sub links307aand307bthat represent the link307, based on the plurality of nodes347a,347b, and347c. For instance, the sub link307a(also referred to as a first sub link307a) and the sub link307b(also referred to as a second sub link307b) may be identified as the vector lines as illustrated in theFIG.3B. For purpose of explanation, the link307comprising two sub links307aand307bis considered. However, the link307may include any finite number of sub links without deviating from the scope of the present disclosure.

Once the link307(or the plurality of sub links307aand307b) are identified, the system101may be configured to determine, from the sensor data, the linear feature detection data319associated with the link307by arranging the plurality of linear feature points319awith respect to the link307(or the plurality of sub links307aand307b), based on the vehicle location data associated with the linear feature points319a, the time stamp data associated with the linear feature points319a, the lateral position data associated with the linear feature points319a, or a combination thereof. For instance, the linear feature detection module201bmay be configured to determine, from the sensor data, the linear feature detection data319associated with the link307.

Similarly, the system101may determine, from the sensor data, the linear feature detection data321,323,325,327,329,331,333,335,337,339,341,343, and345associated with the link307. Once the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345associated with the link307are determined, the system101may be further configured to determine a status of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345associated with the link307. For instance, the linear feature detection module201bmay be configured to determine the status of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345. In an embodiment, the system101may determine the status of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345as at least one of the discontinuous detection data or continuous detection data. For instance, the system101may determine the status as the discontinuous detection data, if a distance between any two consecutive linear feature points of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345is greater than a threshold distance. In other words, the system101may determine the status as the discontinuous detection data, if a distance between any two consecutive linear feature detection data of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345is greater than a threshold distance. For instance, the system101may determine the status as the discontinuous detection data, if a distance between the linear feature detection data319(or the linear feature point319a) and the linear feature detection data321(or the linear feature point321a) is greater than the threshold distance.

Alternatively, the system101may determine the status as the continuous detection data, if distances between all consecutive linear feature detection data of the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345are less than the threshold distance. For instance, if the status is determined as the continuous detection data, the system101may use the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345as the linear feature data to aid a vehicle in vehicle navigation. Alternatively, in response to determining the status as the discontinuous detection data, the system101may be configured to determine, using the map data, one or more linear feature clusters respectively for each of the sub links307aand307b(or the link307), based on the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345. For instance, the system101may determine the one or more linear feature clusters for each of the sub links307aand307bas explained in the detailed description ofFIG.3C.

FIG.3Cillustrates a schematic diagram300cfor determining the one or more linear feature clusters for each of the sub links307aand307b, in accordance with one or more example embodiments.FIG.3Cis explained in conjunction withFIG.3B. As illustrated inFIG.3C, the schematic diagram300cmay include the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, the plurality of sub links307aand307b, the plurality of nodes347a,347b, and347c, one or more linear feature clusters349,351,353, and355associated with the sub link307a, and one or more linear feature clusters357,359,361,363,365,367,369, and371associated with the sub link307b. According to an embodiment, the system101may be configured to determine, based on the map data and the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, the one or more linear feature clusters349,351,353, and355for the sub link307aand the one or more linear feature clusters357,359,361,363,365,367,369, and371for the sub link307b. For instance, the linear feature cluster determination module201cmay be configured to determine, based on the map data and the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, the one or more linear feature clusters349,351,353, and355for the sub link307aand the one or more linear feature clusters357,359,361,363,365,367,369, and371for the sub link307b.

In an example embodiment, to determine the one or more linear feature clusters349,351,353, and355for the sub link307a, the system101may be configured to identify, from the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, linear feature detection data associated with the sub link307a. For instance, the linear feature detection data319,327,329,333,341, and343may be identified as the linear feature detection data associated with the sub link307a.

Once the linear feature detection data319,327,329,333,341, and343(or the plurality of linear feature points319a,327a,329a,333a,341a, and343a) associated with the sub link307aare identified, the system101may be configured to determine, using the map data, a matched distance for each linear feature point of each of the linear feature detection data319,327,329,333,341, and343. As used herein, the matched distance may be a distance between a sub link (e.g., the sub link307a) and a particular linear feature point. Accordingly, in an example embodiment, the system101may determine the matched distance between the sub link307aand each linear feature point of each of the linear feature detection data319,327,329,333,341, and343. In other words, the system101may determine the matched distances between the sub link307aand the plurality of linear feature points319a, the matched distances between the sub link307aand the plurality of linear feature points327a, the matched distances between the sub link307aand the plurality of linear feature points329a, the matched distances between the sub link307aand the plurality of linear feature points333a, the matched distances between the sub link307aand the plurality of linear feature points341a, and the matched distances between the sub link307aand the plurality of linear feature points343a.

Once the matched distance for each linear feature point of each of the linear feature detection data319,327,329,333,341, and343is determined, the system101may be configured to determine the linear feature cluster349, based on a clustering criteria. According to the clustering criteria, the system101may determine one linear feature cluster by clustering one or more linear feature points of the plurality of linear feature points319a,327a,329a,333a,341a, and343ainto one linear feature cluster, if the matched distance associated with each of the one or more linear feature points is identical (or similar). So accordingly, for example, the system101may cluster the plurality of linear feature points319ainto the linear feature cluster349, if the matched distances associated with each of the plurality of linear feature points319ais identical. For example, the system101may cluster the plurality of linear feature points327aand the plurality of linear feature points329ainto the linear feature cluster351, if the matched distances associated with each of the plurality of linear feature points327aand329aare identical. Similarly, the system101may cluster the plurality of linear feature points333ainto the linear feature cluster353; and the plurality of linear feature points341aand343ainto the linear feature355. To this end, the system101may determine the one or more linear feature clusters349,351,353, and355associated with the sub link307a, where each linear feature cluster may include one or more linear feature points of the plurality of linear feature points319a,327a,329a,333a,341a, and343asuch that the matched distance associated with each of the one or more linear feature points is identical. The one or more linear feature clusters349,351,353, and355associated with the sub link307a(the first sub link307a) may be referred to as one or more first linear feature clusters349,351,353, and355.

Once the one or more linear feature clusters349,351,353, and355are determined for the sub link307a, the system101may be configured to identify the sub link307bthat is adjacent (or connected) to the sub link307a. For instance, the system101may identify, in the direction of travel defined by the sub link307a, the sub link307bis adjacent to the sub link307a.

Further, the system101may be configured to identify, from the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, linear feature detection data associated with the sub link307b. For instance, the linear feature detection data321,323,325,331,335,337,339, and345may be identified as the linear feature detection data associated with the sub link307b. Once the linear feature detection data321,323,325,331,335,337,339, and345(or the plurality of linear feature points321a,323a,325a,331a,335a,337a,339a, and345a) associated with the sub link307bare identified, the system101may be configured to determine, using the map data, the matched distance for each linear feature point of each of the linear feature detection data321,323,325,331,335,337,339, and345. In an example embodiment, the system101may determine the matched distance between the sub link307band each linear feature point of each of the linear feature detection data321,323,325,331,335,337,339, and345.

Once the matched distance for each linear feature point of each of the linear feature detection data321,323,325,331,335,337,339, and345is determined, the system101may be configured to cluster, based on the clustering criteria, the linear feature detection data321,323,325,331,335,337,339, and345associated with the sub link307binto the one or more linear feature clusters357,359,361,363,365,367,369, and371. For example, the system101may cluster the plurality of linear feature points321aand the plurality of linear feature points325ainto the linear feature cluster357, if the matched distance associated with each of the plurality of linear feature points321aand the matched distance associated with each of the plurality of linear feature points325aare identical. Similarly, the system101may cluster the plurality of linear feature points331ainto the linear feature cluster361; the plurality of linear feature points335aand the plurality of linear feature points339ainto the linear feature cluster363; and the plurality of linear feature points345ainto the linear feature cluster371. Specifically, the matched distance associated each linear feature point337aof the linear feature detection data337may be continuously varying, so accordingly, the system101may cluster each linear feature point337ainto a separate cluster. For example, the system101may generate three linear feature clusters365,367, and369for the three linear feature points337a, since the matched distance associated with each linear feature point337aof the linear feature detection data337is different (or continuously varying). To this end, the system101may determine the one or more linear feature clusters357,359,361,363,365,367,369, and371. The one or more linear feature clusters357,359,361,363,365,367,369, and371associated with the sub link307b(the second sub link307b) may also referred to as one or more second linear feature clusters357,359,361,363,365,367,369, and371.

In this way, the system101may be configured to determine the one or more linear feature clusters349,351,353, and355for the sub link307aand the one or more linear feature clusters357,359,361,363,365,367,369, and371for the sub link307b. Once the linear feature clusters349,351,353,355,357,359,361,363,365,367,369, and371are determined, the system101may be configured to determine a plurality of linear feature groups for the link307, based on the determined linear feature clusters349,351,353,355,357,359,361,363,365,367,369, and371.

Some embodiments are based on the recognition that the linear feature detection data (or the linear feature points) reported by the vehicle(s) (e.g., the vehicles301,305, and307) may be inaccurate, if the vehicle(s) is traversing from one to another lane. Hereinafter, ‘the linear feature detection data reported by the vehicle(s) while the vehicle(s) is traversing from one lane to another lane’ and ‘diagonal detection data’ may be interchangeably used to mean the same.

To this end, in some example embodiments, the system101may be further configured to remove from the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, the diagonal detection data, before generating the plurality of linear feature groups. In an example embodiment, the system101may remove linear feature detection data as the diagonal detection data, if the linear feature detection data includes at least two linear feature points such that each of the at least two linear feature points is associated with a different linear feature cluster in the determined linear feature clusters. For example, the system101may remove the linear feature detection data337as the diagonal detection data, because the linear feature detection data337includes the different linear feature points337aassociated with different linear feature clusters: the linear feature cluster365, the linear feature cluster367, and the linear feature cluster369.

In an alternate embodiment, the system101may remove, from the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, the diagonal detection data (e.g. the linear feature detection data337), by comparing the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345with a pre-stored image (e.g. a satellite image) representing the linear features311,313,315, and317of the link307.

Some embodiments are based on the recognition that the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345may also include lateral position error data, due to defects in the sensors, noise in the sensors, or the like. To this end, in some example embodiments, the system101may be configured to remove from the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, the lateral position error data. As used herein, the lateral position error data may be linear feature detection data that do not accurately represent the linear feature (e.g., at least one of the linear features311,313,315, and317). For instance, the lateral position error data may be linear feature detection data that include at least one feature point such that the matched distance associated with the at least one linear feature point is not similar to an actual matched distance from the link307to a linear feature point representing the linear feature. In an example embodiment, the system101may remove from the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, the lateral position error data, by comparing the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345with the pre-stored image. For example, the system101may remove the linear feature detection data323as the lateral position error data, by comparing the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345with the pre-stored image.

In some example embodiments, after removing the linear feature detection data337and/or the linear feature detection data323from the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343, and345, the system101may be configured to determine the plurality of linear feature groups, based on the determined linear feature clusters349,351,353,355,357,361,363, and371. For instance, the system101may determine the plurality of linear feature groups, based on the determined linear feature clusters349,351,353,355,357,361,363, and371as explained in the detailed description ofFIG.3D.

FIG.3Dillustrates a schematic diagram300dfor determining the plurality of linear feature groups, based on the determined linear feature clusters349,351,353,355,357,361,363, and371, in accordance with one or more example embodiments.FIG.3Dis explained in conjunction withFIG.3C. As illustrated in theFIG.3D, the schematic diagram300dmay include the linear feature detection data319,321,325,327,329,331,333,335,339,341,343, and345, the plurality of sub links307aand307b, the plurality of nodes347a,347b, and347c, the linear feature clusters349,351,353,355,357,361,363, and371, a plurality of linear feature groups373,375,377, and379. According to an embodiment, the system101may be configured to determine the plurality of linear feature groups373,375,377, and379for the link307, based on the determined linear feature clusters349,351,353,355,357,361,363, and371. For instance, the linear feature group determination module201dmay be configured to determine the plurality of linear feature groups373,375,377, and379for the link307, based on the determined linear feature clusters349,351,353,355,357,361,363, and371.

In an example embodiment, to determine the plurality of linear feature groups373,375,377, and379, the system101may be configured to determine at least one set of matched distance for the link307, based on the determined linear feature clusters349,351,353,355,357,361,363, and371. For instance, the system101may determine a set of feature matched distances for each of the plurality of sub links307aand307b, based on the determined linear feature clusters349,351,353,355,357,361,363, and371. For instance, the system101may determine a first set of feature matched distances for the sub link307a(the first sub link307a) and a second set of feature matched distances for the sub link307b(the second sub link307b). The first set of feature matched distances may be associated with the one or more first linear feature clusters349,351,353, and355. The second set of feature matched distances may be associated with the one or more second linear feature clusters357,361,363, and371.

In an example embodiment, to determine the first set of feature matched distances, the system101may be configured to compute a respective feature matched distance for each of the one or more linear feature clusters349,351,353, and355associated with the sub link307a. For example, to compute the feature matched distance for the linear feature cluster349, the system101may be configured to compute a weighted median of the matched distances associated with the plurality of linear feature points319a. Accordingly, the feature matched distance associated the linear feature cluster349may be the weighted median of the matched distances associated with the plurality of linear feature points319aof the linear feature cluster349. In an example embodiment, to compute the weighted median of the matched distances associated with the plurality of linear feature points319a, the system101may be configured to assign a weight for each matched distance associated with each of the plurality of linear feature points319a, based on a length of the linear feature cluster349and/or the time stamp associated with each of the plurality of linear feature points319a. For example, if the system101has received a first linear feature point319aassociated with a first time instance (or a first time stamp) and a second linear feature point319aassociated with a second time instance (or a second time stamp) such that the first time instance is prior in time to the second time instance, then the system101may assign a first matched distance associated with the first linear feature point319awith a less weightage in comparison to a second matched distance associated with the second linear feature point319a. Further, the system101may be configured to compute the weighted median of the matched distances associated with the plurality of linear feature points319a, based on the weight assigned to each matched distance associated with each of the plurality of linear feature points319a. Similarly, the system101may be configured to compute the respective feature matched distance for each of the one or more linear feature clusters351,353, and355.

In an example embodiment, to determine the second set of feature matched distances, the system101may be configured to compute the respective feature matched distance for each of the one or more linear feature clusters357,361,363, and371associated with the sub link307b. For example, to compute the feature matched distance for the357, the system101may be configured to compute the weighted median of the matched distances associated with the plurality of linear feature points321aand325a. Similarly, the system101may be configured to calculate the respective feature matched distance for each of the one or more linear feature clusters361,363, and371. Once the set of feature matched distances for each of the plurality of sub links307aand307bis determined, the system101may be configured to determine the plurality of linear feature groups373,375,377, and379. For instance, the system101may determine the plurality of linear feature groups373,375,377, and379, based on the at least one set of feature matched distances and the determined linear feature clusters349,351,353,355,357,361,363, and371. For instance, the at least one set of feature matched distances may include the first set of feature matched distances associated with the sub link307aand the second set of featured matched distances associated with the sub link307b. For example, the system101may determine the plurality of linear feature groups373,375,377, and379, based on the determined linear feature clusters349,351,353,355,357,361,363, and371, the first set of feature matched distances and the second set of feature matched distances, as explained in the detailed description ofFIG.3E.

FIG.3Eillustrates a flowchart300efor determining the plurality of linear feature groups373,375,377, and379based on the determined linear feature clusters349,351,353,355,357,361,363, and371, the first set of feature matched distances and the second set of feature matched distances, in accordance with one or more example embodiments.FIG.3Eis explained in conjunction withFIG.3D. Starting at block381, the system101may compute a difference between a first feature matched distance in the first set of feature matched distances and a second feature matched distance in the second set of feature matched distances. For instance, the system101may compute a difference between the feature matched distance associated with the linear feature cluster349and the feature matched distance associated with the linear feature cluster357.

At block383, the system101may be configured to check if the computed difference is less than a threshold difference value. For example, the system101may check if the difference between the feature matched distance associated with the linear feature cluster349and the feature matched distance associated with the linear feature cluster357is less than the threshold difference value. For instance, the threshold difference value may be a value (e.g., ‘0.5’) that is predetermined based on experimentation and the like.

When the computed difference is less than the threshold difference value, the system101may continue with block385. At block385, the system101may be configured to group, into a linear feature group, a first linear feature cluster associated with the first feature matched distance and a second linear feature cluster associated with the second feature matched distance. For instance, the system101may group the linear feature cluster349and the linear feature357into the linear feature group373. In other words, the system101may group, into the linear feature group373, the linear feature cluster349(the first linear feature cluster349) and the linear feature cluster357(the second linear feature cluster357), if the first feature matched distance of the linear feature cluster349is substantially matching the second feature matched distance of the linear feature cluster357.

When the computed difference is not less than the threshold difference value, the system101may continue with block387. At block387, the system101may be configured to check if the second set of feature matched distances is empty. In other words, at block387, the system101may check if the difference between an element (i.e., the feature matched distance associated with the linear feature cluster349) in the first set of feature matched distances and each element in the second set of feature matched distances is computed. For instance, the elements in the second set of feature matched distance may include the feature matched distances for the one or more linear feature clusters357,361,363, and371.

When the second set of feature matched distances is not empty, the system101may continue with block389. At block389, the system101may be configured to select a next feature matched distance in the second set of feature matched distances. For example, the system101may select the feature matched distance associated with the linear feature cluster361.

Once the feature matched distance associated with the linear feature cluster361is selected, the system101may continue with block381. At block381, the system101may compute a difference between the first feature matched distance (e.g., the feature matched distance associated with the linear feature cluster349) and the next second feature matched distance (e.g., the feature matched distance associated with the linear feature cluster361).

At block383, the system101may check if the difference between the first feature matched distance and the next second feature matched distance is less than the threshold difference value. If the difference between the first feature matched distance and the next second feature matched distance is not less than the threshold difference value, the system101may continue with block387. At block387, the system101may check if the second set of feature matched distances is empty. If the second set of feature matched distances is not empty, the system101may continue with block389. At block389, the system101may be configured to select a next second feature matched distance in the second set of feature matched distances. For instance, the system101may select the feature matched distance associated with the linear feature cluster363. Once the feature matched distance associated with the linear feature cluster363is selected, the system101may continue with block381.

In this way, the system101may iteratively execute one or more blocks of the blocks381,383,385,387,389to group the linear feature cluster349associated with the sub link307awith at least one linear feature cluster (e.g. the linear feature cluster357) associated with the sub link307b, if the difference between the feature matched distance associated with the linear feature cluster349and the feature matched distance associated with the at least one linear feature cluster of the sub link307bis less than the threshold difference value.

When the second set of feature matched distances is empty, the system101may continue block391. At block391, the system101may configured to check if the first set of feature matched distances is empty. If the first set of feature matched distance is not empty, the system101may continue with step393. At step393, the system101may be configured to select a next first feature matched distance in the first set of feature matched distances. For instance, the system101may select the feature matched distance associated with the linear feature cluster351.

Once the feature matched distance associated with the linear feature cluster351is selected, the system101may iteratively execute one or more blocks of the blocks381,383,385,387,389to group the linear feature cluster351associated with the sub link307awith at least one linear feature cluster (e.g. the linear feature cluster361) associated with the sub link307b, if the difference between the feature matched distance associated with the linear feature cluster351and the feature matched distance associated with the at least one linear feature cluster of the sub link307bis less than the threshold difference value.

In this way, the system101may iteratively execute the flowchart300e, to group at least one first linear feature cluster associated with the sub link307awith at least one second linear feature cluster associated with the sub link307, if the difference between the feature matched distance associated with the at least one first linear feature cluster of the sub link307aand the feature matched distance associated with the at least one second linear feature cluster of the sub link307bis less than the threshold difference value.

Referring toFIG.3D, for example, the system101may group the linear feature cluster349and the linear feature cluster357into the linear feature group373, if the difference between the feature matched distance associated with the linear feature cluster349and the feature matched distance associated with the linear feature cluster357is less than the threshold value. Similarly, the system101may group the linear feature cluster351and the linear feature cluster361into the linear feature group375; the linear feature cluster353and the linear feature cluster363into the linear feature group377; and the linear feature cluster341and the linear feature cluster371into the linear feature group379.

Once the plurality of linear feature groups373,375,377, and379is determined, the system101may be configured to generate the linear feature data. For example, the system101may generate the linear feature data based on the determined plurality of linear feature groups373,375,377, and379. In an example embodiment, to generate the linear feature data, the system101may be configured to fill one or more gaps in each of the plurality of linear feature groups373,375,377, and379. For instance, to accurately represent the linear feature311, the system101may fill a gap between the linear feature cluster349(or the linear feature detection data319) and the linear feature cluster357(or the linear feature detection data321); and a gap between the linear feature detection data321and the linear feature detection data325. For instance, to accurately represent the linear feature313, the system101may fill a gap between the linear feature detection data327and the linear feature detection data329. For instance, to accurately represent the linear feature315, the system101may fill a gap between the linear feature detection data335and the linear feature detection data339. For instance, to accurately represent the linear feature317, the system101may fill a gap between the linear feature detection data341and the linear feature detection data343.

In this way, the system101may generate, based on the determined plurality of groups373,375,377, and379, the linear feature data representing the linear features311,313,315, and317such that the unwanted conditions are avoided. In an example embodiment, after generating the linear feature data, the system101may be configured to update the map data associated with the mapping platform103to include the generated linear feature data. In an example embodiment, the system101may be further configured to provide, using one or more of the generated linear feature data and the updated map data, one or more navigation functions for a vehicle. Some non-limiting examples of the navigation functions includes providing vehicle speed guidance, vehicle speed handling and/or control, providing a route for navigation (e.g., via a user interface), localization, route determination, lane level speed determination, operating the vehicle along a lane level route, route travel time determination, lane maintenance, route guidance, provision of traffic information/data, provision of lane level traffic information/data, vehicle trajectory determination and/or guidance, route and/or maneuver visualization, and/or the like.

For purpose of explanation, inFIG.3A-3D, the system101configured to generate the linear feature data for the other-than straight road segment (i.e., the link307) is considered. However, the system101may also be configured to generate the linear feature data for one or more straight road segments. For instance, the system101may generate the linear feature data for the one or more straight road segments, as explained in the detailed description ofFIG.4A-4D.

FIG.4Aillustrates a second working environment400aof the system101for generating the linear feature data, in accordance with one or more example embodiments. As illustrated inFIG.4A, the second working environment400aincludes the system101, the mapping platform103, the network105, a plurality of vehicles401and403, a first link405, a second link407adjacent to the first link405, linear features409and411associated with the first link405, linear features413and415associated with the second link407. Each of the plurality of vehicles401and403may correspond to any one of: the autonomous vehicle, the semi-autonomous vehicle, or the manual vehicle.

As used herein, the ‘link’ (e.g., the link405and the link407) may be a road segment between two nodes. Each of the links405and407may be the freeway, the expressway, the highway, or the like. The link405may be associated with the linear feature409and411. For instance, each of the linear features409and411may correspond to a border of the link405(and/or a boarder of a lane of the link405), where the border may be represented by one or more of: the lane markings, the guardrails, the road curbs, the road medians, the road barriers, or the like. The link407may be associated with the linear feature413and415. For instance, each of the linear features413and415may correspond to a border of the link405(and/or a boarder of a lane of the link405), where the border may be represented by one or more of: the lane markings, the guardrails, the road curbs, the road medians, the road barriers, or the like.

Some embodiments are based on the recognition that the linear features409,411,413, and415may be used in vehicle navigation for assisting the vehicles401and/or403. For instance, the linear features409,411,413, and415may be used in lane maintenance application and the like. To this end, in some embodiments, the vehicles401and403may be equipped with various sensors to capture the linear features409,411,413, and415. For instance, the sensors may include the radar system, the LiDAR system, the global positioning sensor for gathering location data (e.g., GPS), the image sensors, the temporal information sensors, the orientation sensors augmented with the height sensors, the tilt sensors, and the like. In some example embodiments, the sensors may collect the linear features409,411,413, and415as linear feature points, leading to linear feature detection data. In these embodiments, sensor data obtained from the sensors include the linear feature detection data, among other things. For instance, each linear feature point in the linear feature detection data may represent image data corresponding to at least one of the linear features409,411,413, and415.

However, in most of cases, the sensors may fail to continuously capture the linear features409,411,413, and415, leading to discontinuities in the linear feature detection data. For instance, the sensors may fail to continuously capture the linear features409,411,413, and415, due to occlusions (caused by interference of other vehicles), noise in the sensors, or other defects in the sensors. In other words, the discontinuities in the linear feature detection data may occur when the sensors fail to completely capture the linear features409,411,413, and415. As a result, a gap may be formed between any two consecutive linear feature points in the linear feature detection data. As used herein, the gap between any two consecutive linear feature points may be indicative of a distance of discontinuity. Hereinafter, the ‘discontinuities in the linear feature detection data’ and ‘discontinuous detection data’ may be interchangeably used to mean the same.

Thereby, the linear feature detection data extracted from the sensor data may not be accurate to provide the vehicle navigation when the linear feature detection data corresponds to the discontinuous detection data. Furthermore, if the discontinuous detection data is used in the vehicle navigation, a vehicle may end-up with unwanted conditions such as entering a wrong lane, road accidents, traffic congestions, vehicle efficiency reduction, environmental pollutions, and the like. To this end, when the linear feature detection data corresponds to the discontinuous detection data, the system101is provided for generating the linear feature data such that the unwanted conditions are avoided. Further, to generate the linear feature data, the system101may be configured as explained in the detailed description ofFIG.4B-FIG.4D.

FIG.4Billustrates a schematic diagram400bfor determining, from the sensor data, the linear feature detection data associated with the at least one link405and407, in accordance with one or more example embodiments.FIG.4Bis explained in conjunction withFIG.4A. As illustrated inFIG.4B, the schematic diagram400bmay include linear feature detection data417,419,421,423,425, and427, the at least one link405and407. In an embodiment, the system101may be configured to obtain, from the sensors, the sensor data. For instance, the reception module201amay obtain the sensor data from the sensors. In an example embodiment, the sensor data may include the linear feature detection data417,419,421,423,425, and427. The linear feature detection data417may correspond to the linear feature409. The linear feature detection data419may correspond to the linear feature413. The linear feature detection data421and423may correspond to the linear feature411. The linear feature detection data425and427may correspond to the linear feature415. In an example embodiment, each of the linear feature detection data417,419,421,423,425, and427may include a plurality of linear feature points. For instance, the linear feature detection data417may include a plurality of linear feature points417a, where each linear point417amay be data (e.g., image data) indicating the linear feature409. Similarly, the linear feature detection data491may include a plurality of linear feature points419a, the linear feature detection data421may include a plurality of linear feature points421a, the linear feature detection data423may include a plurality of linear feature points423a, the linear feature detection data425may include a plurality of linear feature points425a, and the linear feature detection data427may include a plurality of linear feature points427a.

In an example embodiment, the sensor data may further include time stamp data, vehicle location data, and lateral position data along with the linear feature detection data417,419,421,423,425, and427. The time stamp data may include the time stamp for each linear feature point of the linear feature detection data417,419,421,423,425, and427. As used herein, the time stamp may indicate a time instance at which a particular linear feature point was recorded by the sensors. The vehicle location data may include the vehicle location for each linear feature point of the linear feature detection data417,419,421,423,425, and427. As used herein, the vehicle location may indicate a location of a vehicle at where a particular linear feature point was recorded by the sensors. The lateral position data may include a lateral position distance for each linear feature point of the linear feature detection data417,419,421,423,425, and427. As used herein, the lateral position distance may be a distance from the vehicle to a particular linear feature point recorded by the sensors. In some embodiments, the lateral position distance may be associated with a sign (e.g., a positive sign or a negative sign). For instance, the lateral position distance with the positive sign may indicate that the particular linear feature point is located on right side with respect to a direction of travel of the vehicle. Conversely, the lateral position distance with the negative sign may indicate that the particular linear feature point is located on left side with respect to a direction of travel of the vehicle.

For example, once the system101receives the sensor data (e.g., the linear feature points417a, the time stamp data associated with the linear feature points417a, the vehicle location data associated with the linear feature points417a, and the lateral position data associated with the linear feature points417a), the system101may be configured to identify, using the map data, the first link405(also referred to as a first sub link405) based on the sensor data. For instance, the linear feature detection module201bof the system101may map-match the sensor data (specifically, the vehicle location data) with the map data to identify the first link405. In various embodiments, the first link405may be identified as at least one vector line. In some example embodiments, after identifying the first link405, the system101may be configured to check if the first link405is a straight road segment or not. In an example embodiment, the system101may check if the first link405is the straight road segment or not, based on a plurality of nodes associated with the first link405. For instance, if the plurality of nodes associated with the first link405does not include at least one shape location, then the system101may identify the first link405as the straight road segment.

In response to identifying the first link405as the straight road segment, the system101may be configured to identify, using the map data, the second link407(also referred to as a second sub link407) adjacent to the first link405. In other words, the system101may identify, in a direction of travel associated with the first link405, at least one second link (e.g., the second link407) connected to the first link405, based on the map data. For instance, the second link407may be (i) a link that is connected to the first link305and/or (ii) a link that is within a threshold distance from the first link405. Accordingly, the system101may be configured to identify, using the sensor data and the map data, the at least one link comprising the first link405and the second link407.

Once the first link405and the second link407are identified, the system101may be configured to determine, from the sensor data, the linear feature detection data417associated with the first link405by arranging the plurality of linear feature points417awith respect to the first link405, based on the vehicle location data associated with the linear feature points417a, the time stamp data associated with the linear feature points417a, and the lateral position data associated with the linear feature points417a. For instance, the linear feature detection module201bmay be configured to determine, from the sensor data, the linear feature detection data417associated with the first link405.

Similarly, the system101may determine, from the sensor data, the linear feature detection data421and423associated with the first link405and the linear feature detection data419,425, and427associated with the second link407. Once the linear feature detection data417,419,421,423,425, and427are determined, the system101may be further configured to determine a status of the linear feature detection data417,419,421,423,425, and427associated with the at least one link405and407. For instance, the linear feature detection module201bmay be configured to determine the status of the linear feature detection data417,419,421,423,425, and427. In an embodiment, the system101may determine the status of the linear feature detection data417,419,421,423,425, and427as at least one of the discontinuous detection data or continuous detection data. For instance, the system101may determine the status as the discontinuous detection data, if a distance between any two consecutive linear feature points of the linear feature data417,419,421,423,425, and427is greater than a threshold distance. In other words, the system101may determine the status as the discontinuous detection data, if a distance between any two consecutive linear feature detection data of the linear feature detection data417,419,421,423,425, and427is greater than the threshold distance. For instance, the system101may determine the status as the discontinuous detection data, if a distance between the linear feature detection data417(or the linear feature point417a) and the linear feature detection data419(or the linear feature point419a) is greater than the threshold distance.

Alternatively, the system101may determine the status as the continuous detection data, if distances between all consecutive linear feature detection data of the linear feature detection data417,419,421,423,425, and427are less than the threshold distance. For instance, if the status is determined as the continuous detection data, the system101may use the linear feature detection data417,419,421,423,425, and427as the linear feature data to aid a vehicle in the vehicle navigation. Alternatively, in response to determining the status as the discontinuous detection data, the system101may be configured to determine, using the map data, one or more linear feature clusters respectively for each of the first link405and the second link407, based on the linear feature detection data417,419,421,423,425, and427. For instance, the system101may determine the one or more linear feature clusters respectively for each of the first link405and the second link407as explained in the detailed description ofFIG.4C.

FIG.4Cillustrates a schematic diagram400cfor determining the one or more linear feature clusters for each of the first link405and the second link407, in accordance with one or more example embodiments.FIG.4Cis explained in conjunction withFIG.4B. As illustrated inFIG.4C, the schematic diagram400cmay include the linear feature detection data417,419,421,423,425, and427, the first link405, the second link407, one or more linear feature clusters429and431associated with the first link405, and one or more linear feature clusters433and435associated with the second link407. According to an embodiment, the system101may be configured to determine, based on the map data and the linear feature detection data417,419,421,423,425, and427, the one or more linear feature clusters429and431for the first link405and the one or more linear feature clusters433and435for the second link407. For instance, the linear feature cluster determination module201cmay be configured to determine, based on the map data and the linear feature detection data417,419,421,423,425, and427, the one or more linear feature clusters429and431for the first link405and the one or more linear feature clusters433and435for the second link407.

In an example embodiment, to determine the one or more linear feature clusters429and431for the first link405, the system101may be configured to identify, from the linear feature detection data417,419,421,423,425, and427, linear feature detection data associated with the first link405. For instance, the linear feature detection data417,421, and423may be identified as the linear feature detection data associated with the first link405.

Once the linear feature detection data417,421, and423(or the plurality of linear feature points417a,421a, and423a) associated with the first link405are identified, the system101may be configured to determine, using the map data, the matched distance for each linear feature point of each of the linear feature detection data417,421, and423. As used herein, the matched distance may be a distance between a link (e.g., the first link405) and a particular linear feature point. Accordingly, in an example embodiment, the system101may determine the matched distance between the first link405and each linear feature point of each of the linear feature detection data417,421,423. In other words, the system101may calculate the matched distances between the first link405and the plurality of linear feature points417a, the matched distances between the first link405and the plurality of linear feature points421a, and the matched distances between the first link405and the plurality of linear feature points423a.

Once the matched distance for each linear feature point of each of the linear feature detection data417,421, and423is determined, the system101may be configured to determine the linear feature cluster429for the first link405, based on the clustering criteria. According to the clustering criteria, the system101may determine one linear feature cluster by clustering one or more linear feature points of the plurality of linear feature points417a,421a, and423ainto one linear feature cluster, if the matched distance associated with each of the one or more linear feature points is identical (or similar). So accordingly, for example, the system101may cluster the plurality of linear feature points417ainto the linear feature cluster429, if the matched distances associated with each of the plurality of linear feature points417ais identical. Similarly, the system101may cluster the plurality of points421aand the plurality of points423ainto the linear feature cluster431if the matched distances associated with each of the plurality of linear feature points421aand the matched distances associated with each of the plurality of linear feature points423aare identical. To this end, the system101may determine the one or more linear feature clusters429and431, where each linear feature cluster includes one or more linear feature points with similar matched distances.

Once the one or more linear feature clusters429and431are generated for the first link405, the system101may be configured to identify the second link407is adjacent (or connected) to the first link405. Further, the system101may be configured to identify, from the linear feature detection data417,419,421,423,425, and427, linear feature detection data associated with the second link407. For instance, the linear feature detection data419,425, and427may be identified as the linear feature detection data associated with the second link407. Once the linear feature detection data419,425, and427(or the plurality of linear feature points419a,425a, and427a) associated with the second link407are identified, the system101may be configured to determine, using the map data, the matched distance for each linear feature point of each of the linear feature detection data419,425, and427. In an example embodiment, the system101may determine the matched distance between the second link407and each linear feature point of each of the linear feature detection data419,425, and435.

Once the matched distance for each linear feature point of each of the linear feature detection data419,425, and435is determined, the system101may be configured to cluster, based on the clustering criteria, the linear feature detection data419,425, and427associated with the second link407into the one or more linear feature clusters433and435. For example, the system101may cluster the plurality of linear feature points419ainto the linear feature cluster433, if the matched distance associated with each of the plurality of linear feature points419ais identical. Similarly, the system101may cluster the plurality of linear feature points425aand the plurality of linear feature points427ainto the linear feature cluster435. To this end, the system101may determine the one or more linear feature clusters433and435for the second link407.

In this way, the system101may be configured to determine the one or more linear feature clusters429and431for the first link405and the one or more linear feature clusters433and435for the second link407. Once the linear feature clusters429,431,433, and435are generated, the system101may be configured to determine a plurality of linear feature groups for the at least one link405and407, based on the determined linear feature clusters429,431,433, and435. In some example embodiments, before determining the plurality of linear feature groups, the system101may be configured to check if the linear feature detection data417,419,421,423,425, and427include the diagonal detection data and/or the lateral position error data. If the linear feature detection data417,419,421,423,425, and427include the diagonal data and/or the lateral position error data, the system101may be configured to remove from the linear feature detection data417,419,421,423,425, and427, the diagonal detection data and/or the lateral position error data. If the linear feature detection data417,419,421,423,425, and427do not include the diagonal detection data and/or the lateral position error data, the system101may be configured to determine the plurality of linear feature groups for the at least one link405and407, based on the determined linear feature clusters429,431,433, and435. For instance, the system101may determine the plurality of linear feature groups, based on the determined linear feature clusters429,431,433, and435as explained in the detailed description ofFIG.4D.

FIG.4Dillustrates a schematic diagram400dfor determining the plurality of groups, based on the determined linear feature clusters429,431,433, and435, in accordance with one or more example embodiments.FIG.4Dis explained in conjunction withFIG.4C. As illustrated in theFIG.4D, the schematic diagram400dmay include the linear feature detection data417,419,421,423,425, and427, the first link405, the second link407, the linear feature clusters429,431,433, and435, a plurality of linear feature groups437and439. According to an embodiment, the system101may be configured to determine the plurality of linear feature groups437and439for the at least one link405and407, based on the determined linear feature clusters429,431,433, and435. For instance, the linear feature group determination module201dmay be configured to determine the plurality of linear feature groups437and439for the at least one link405and407, based on the determined linear feature clusters429,431,433, and435.

In an example embodiment, to determine the plurality of linear feature groups437and439, the system101may be configured to determine a set of feature matched distances for each of the first link405and the second link407, based on the determined linear feature clusters429,431,433, and435. For instance, the system101may determine a first set of feature matched distances for the first link405and a second set of feature matched distances for the second link407.

In an example embodiment, to determine the first set of feature matched distances, the system101may be configured to compute a feature matched distance for each of the one or more linear feature clusters429and431associated with the first link405. For example, to compute the feature matched distance for the linear feature cluster429, the system101may be configured to compute the weighted median of the matched distances associated with the plurality of linear feature points417aof the linear feature cluster429. In an example embodiment, to compute the weighted median of the matched distances associated with the plurality of linear feature points417a, the system101may be configured to assign a weight for each matched distance associated with each of the plurality of linear feature points417a, based on a length of the linear feature cluster429and/or the time stamp associated with each of the plurality of linear feature points417a. Further, the system101may be configured to compute the weighted median of the matched distances associated with the plurality of linear feature points417a, based on the weight assigned to each matched distance associated with each of the plurality of linear feature points417a. Similarly, the system101may be configured to compute the feature matched distance for the linear feature cluster431.

In an example embodiment, to determine the second set of feature matched distances, the system101may be configured to compute the feature matched distance for each of the one or more linear feature clusters433and435. For example, to compute the feature matched distance for the linear feature cluster433, the system101may compute the weighted median of the matched distances associated with the plurality of linear feature points419aof the linear feature cluster433. Similarly, the system101may compute the feature matched distance for the linear feature cluster435. Once the set of feature matched distances for each of the first link405and the second link407is determined, the system101may be configured to determine the plurality of linear feature groups437and439for the at least one link405and407. For instance, the system101may determine the plurality of linear feature groups437and439, based on the determined linear feature clusters429,431,433, and435, the first set of feature matched distances associated with the first link405and the second set of featured matched distances associated with the second link407.

In an example embodiment, to determine the linear feature group437, the system101may be configured to compute a first difference between the feature matched distance associated with the linear feature cluster429and the feature matched distance associated with the linear feature cluster433. Further, the system101may be configured to check if the first difference is less than the threshold difference value. If the first difference is less than the threshold difference value, the system101may group the linear feature cluster429of the first link405with the linear feature cluster433of the second link407to determine the linear feature group437. Furthermore, the system101may be configured to compute a second difference between the feature matched distance associated with the linear feature cluster429and the feature matched distance associated with the linear feature cluster435. If the second difference is less than the threshold difference value, the system101may group the linear feature cluster429of the first link405, the linear feature cluster433of the second link407, and the linear feature cluster435of the second link407to determine the linear feature group437. If the second difference is not less than the threshold difference value, the system101may select a next linear feature cluster associated with the first link405. For instance, the system101may select the linear feature cluster431as the next linear feature cluster.

Once the linear feature cluster431is selected, the system101may be configured to compute a third difference between the feature matched distance associated with the linear feature cluster431and the feature matched distance associated with the linear feature cluster433. Further, the system101may be configured to check if the third difference is less than the threshold difference value. If the third difference value is not less than the threshold difference value, the system101may select a next linear feature cluster associated with the second link407. For instance, the system101may select the linear feature cluster435as the next linear feature cluster.

Once the linear feature cluster435is selected, the system101may be configured to compute a fourth difference between the feature matched distance associated with the linear feature cluster431and the feature matched distance associated with the linear feature cluster435. Further, the system101may be configured to check if the fourth difference is less than the threshold difference value. If the fourth difference is less than the threshold difference value, the system101may group the linear feature cluster431of the first link405with the linear feature cluster435of the second link407to determine the linear feature group439.

In this way, the system101may be configured to determine the plurality of linear feature groups437and439for the at least one link405and407, based on the determined linear feature clusters429,431,433, and435, the first set of feature matched distances associated with the first link405and the second set of featured matched distances associated with the second link407. In some other embodiments, the system101may determine a single set of feature matched distances for the at least one link405and407, rather than determining the set of featured matched for each of the links405and407. In these embodiments, the single set of feature matched distances may include the elements (the feature matched distances of the linear feature clusters429and431) of the first set of feature matched distances and the elements (the feature matched distances of the linear feature clusters433and435) of the second set of feature matched distances. To this end, the system101may determine the plurality of linear feature groups437and439for the at least one link405and407, by computing a difference between each element with each other element in the single set of feature matched distances and comparing the difference with the threshold difference value.

Once the plurality of groups437and439is determined, the system101may be configured to generate the linear feature data. In an example embodiment, to generate the linear feature data, the system101may be configured to fill one or more gaps in each of the plurality of groups437and439. For instance, to accurately represent the linear feature409, the system101may fill a gap between the linear feature cluster429(or the linear feature detection data417) and the linear feature cluster433(or the linear feature detection data419). For instance, to accurately represent the linear feature411, the system101may fill a gap between the linear feature detection data421and the linear feature detection data423; and a gap between the linear feature detection data423and the linear feature detection data425. For instance, to accurately represent the linear feature415, the system101may fill a gap between the linear feature detection data425and the linear feature detection data427.

In this way, the system101may generate, based on the generated plurality of groups437and439, the linear feature data representing the linear features409,411,413, and415such that the unwanted conditions are avoided. In an example embodiment, after generating the linear feature data, the system101may be configured to update the map data associated with the mapping platform103to include the generated linear feature data. In an example embodiment, the system101may be further configured to provide, using one or more of the generated linear feature data and the updated map data, the one or more navigation functions for the vehicle. Some non-limiting examples of the navigation functions includes providing vehicle speed guidance, vehicle speed handling and/or control, providing a route for navigation (e.g., via a user interface), localization, route determination, lane level speed determination, operating the vehicle along a lane level route, route travel time determination, lane maintenance, route guidance, provision of traffic information/data, provision of lane level traffic information/data, vehicle trajectory determination and/or guidance, route and/or maneuver visualization, and/or the like.

Starting at block501, the method500may include determining, from the sensor data, the detection data associated with the at least one link. For instance, the linear feature detection module201bmay determine, from the sensor data, the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343,345associated with the at least one link307as explained in the detailed description ofFIG.3B. In an example embodiment, the at least one link may include a plurality of sub links.

At block503, the method500may include determining, using the map data, the one or more linear feature clusters respectively for each of the plurality of sub links, based on the detection data. For instance, the linear feature cluster determination module201cmay determine, using the map data and the linear feature detection data319,321,323,325,327,329,331,333,335,337,339,341,343,345, the one or more linear feature clusters349,351,353,355for the sub link307a; and the one or more linear feature clusters357,359,361,363,365,367,369, and371for the sub link307b, as explained in the detailed description ofFIG.3C. Further, the determined linear feature clusters may be associated with at least one set of feature matched distances. For instance, the one or more linear feature clusters349,351,353,355are associated with the first set of featured matched distances and the one or more linear feature clusters357,359,361,363,365,367,369, and371are associated with the second set of feature matched distances. For instance, the first set of featured matched distances include the respective featured matched distance for each of the one or more linear feature clusters349,351,353,355. For instance, the second set of featured matched distances include the respective featured matched distance for each of the one or more linear feature clusters357,359,361,363,365,367,369, and371.

At block505, the method500may include determining the plurality of linear feature groups for the at least one link, based on the at least one set of feature matched distances and the determined one or more linear feature clusters. For instance, the linear feature group determination module201dmay determine the plurality of linear feature groups373,375,377, and379for the at least one link307, based on the first set of feature matched distances, the second set of feature matched distances, and the determined linear feature clusters349,351,353,355,357,359,361,363,365,367,369, and371, as explained in the detailed description ofFIG.3DandFIG.3E. In an example embodiment, a given linear feature group (e.g., the linear feature group373) respectively includes at least a first liner feature cluster (e.g., the linear feature cluster349) associated with the first sub link (e.g., the sub link307a) and at least a second linear feature cluster (e.g., the linear feature cluster357) associated with the second sub link (e.g., the sub link307b).

At block507, the method500may include generating the linear feature data, based on the determined plurality of linear feature groups. For instance, the linear feature generating module201emay generate the linear feature data, based on the determined plurality of linear feature groups373,375,377, and379, as explained in the detailed description ofFIG.3D.

On implementing the method500disclosed herein, the system101may be configured to generate the linear feature data, when the detection data is in accurate. Further, the system101may be configured to provide, using at least one of the generated linear feature data and/or the updated map data, the one or more navigation functions for the vehicle. Thereby, the system101may avoid the unwanted conditions.

FIG.6Ashows format of map data600astored in the map database103a, in accordance with one or more example embodiments.FIG.6Ashows a link data record601that may be used to store data about one or more of the linear features, for example, the linear features311,313,315, and317illustrated inFIG.3A. This link data record601has information (such as “attributes”, “fields”, etc.) associated with it that allows identification of the nodes associated with the link and/or the geographic positions (e.g., the latitude and longitude coordinates and/or altitude or elevation) of the two nodes. In addition, the link data record601may have information (e.g., more “attributes”, “fields”, etc.) associated with it that specify the permitted speed of travel on the portion of the road represented by the link record, the direction of travel permitted on the road portion represented by the link record, what, if any, turn restrictions exist at each of the nodes which correspond to intersections at the ends of the road portion represented by the link record, the street address ranges of the roadway portion represented by the link record, the name of the road, and so on. The various attributes associated with a link may be included in a single data record or are included in more than one type of record which are referenced to each other.

Each link data record that represents another-than-straight road segment may include shape point data. A shape point is a location along a link between its endpoints. To represent the shape of other-than-straight roads, the mapping platform103and its associated map database developer selects one or more shape points along the other-than-straight road portion. Shape point data included in the link data record601indicate the position, (e.g., latitude, longitude, and optionally, altitude or elevation) of the selected shape points along the represented link.

Additionally, in the compiled geographic database, such as a copy of the map database103athat is compiled and provided to a user interface, there may also be a node data record603for each node. The node data record603may have associated with it information (such as “attributes”, “fields”, etc.) that allows identification of the link(s) that connect to it and/or its geographic position (e.g., its latitude, longitude, and optionally altitude or elevation).

In some embodiments, compiled geographic databases are organized to facilitate the performance of various navigation-related functions. One way to facilitate performance of navigation-related functions is to provide separate collections or subsets of the geographic data for use by specific navigation-related functions. Each such separate collection includes the data and attributes needed for performing the particular associated function but excludes data and attributes that are not needed for performing the function. Thus, the map data may be alternately stored in a format suitable for performing types of navigation functions, and further may be provided on-demand, depending on the type of navigation function.

FIG.6Bshows another format of map data600bstored in the map database103a, in accordance with one or more example embodiments. InFIG.6B, the map data600bis stored by specifying a road segment data record605. The road segment data record605is configured to represent data that represents a road network. InFIG.6B, the map database103acontains at least one road segment data record605(also referred to as “entity” or “entry”) for each road segment in a geographic region.

The map database103athat represents the geographic region also includes a database record607(a node data record607aand a node data record607b) (or “entity” or “entry”) for each node associated with the at least one road segment shown by the road segment data record605. (The terms “nodes” and “segments” represent only one terminology for describing these physical geographic features and other terminology for describing these features is intended to be encompassed within the scope of these concepts). Each of the node data records607aand607bmay have associated information (such as “attributes”, “fields”, etc.) that allows identification of the road segment(s) that connect to it and/or its geographic position (e.g., its latitude and longitude coordinates).

FIG.6Bshows some of the components of the road segment data record605contained in the map database103a. The road segment data record605includes a segment ID605aby which the data record can be identified in the map database103a. Each road segment data record605has associated with it information (such as “attributes”, “fields”, etc.) that describes features of the represented road segment. The road segment data record605may include data605bthat indicate the restrictions, if any, on the direction of vehicular travel permitted on the represented road segment. The road segment data record605includes data605cthat indicate a static speed limit or speed category (i.e., a range indicating maximum permitted vehicular speed of travel) on the represented road segment. The static speed limit is a term used for speed limits with a permanent character, even if they are variable in a pre-determined way, such as dependent on the time of the day or weather. The static speed limit is the sign posted explicit speed limit for the road segment, or the non-sign posted implicit general speed limit based on legislation.

The road segment data record605may also include data605dindicating the two-dimensional (“2D”) geometry or shape of the road segment. If a road segment is straight, its shape can be represented by identifying its endpoints or nodes. However, if a road segment is other-than-straight, additional information is required to indicate the shape of the road. One way to represent the shape of an other-than-straight road segment is to use shape points. Shape points are points through which a road segment passes between its end points. By providing the latitude and longitude coordinates of one or more shape points, the shape of an other-than-straight road segment can be represented. Another way of representing other-than-straight road segment is with mathematical expressions, such as polynomial splines.

The road segment data record605also includes road grade data605ethat indicate the grade or slope of the road segment. In one embodiment, the road grade data605einclude road grade change points and a corresponding percentage of grade change. Additionally, the road grade data605emay include the corresponding percentage of grade change for both directions of a bi-directional road segment. The location of the road grade change point is represented as a position along the road segment, such as thirty feet from the end or node of the road segment. For example, the road segment may have an initial road grade associated with its beginning node. The road grade change point indicates the position on the road segment wherein the road grade or slope changes, and percentage of grade change indicates a percentage increase or decrease of the grade or slope. Each road segment may have several grade change points depending on the geometry of the road segment. In another embodiment, the road grade data605eincludes the road grade change points and an actual road grade value for the portion of the road segment after the road grade change point until the next road grade change point or end node. In a further embodiment, the road grade data605eincludes elevation data at the road grade change points and nodes. In an alternative embodiment, the road grade data605eis an elevation model which may be used to determine the slope of the road segment.

The road segment data record605also includes data605gproviding the geographic coordinates (e.g., the latitude and longitude) of the end points of the represented road segment. In one embodiment, the data605gare references to the node data records607that represent the nodes corresponding to the end points of the represented road segment.

The road segment data record605may also include or be associated with other data605fthat refer to various other attributes of the represented road segment. The various attributes associated with a road segment may be included in a single road segment record or may be included in more than one type of record which cross-reference each other. For example, the road segment data record605may include data identifying the name or names by which the represented road segment is known, the street address ranges along the represented road segment, and so on.

FIG.6Balso shows some of the components of the node data record607contained in the map database103a. Each of the node data records607may have associated information (such as “attributes”, “fields”, etc.) that allows identification of the road segment(s) that connect to it and/or it is geographic position (e.g., its latitude and longitude coordinates). For the embodiment shown inFIG.6B, the node data records607aand607binclude the latitude and longitude coordinates607a1and607b1for their nodes. The node data records607aand607bmay also include other data607a2and607b2that refer to various other attributes of the nodes. In some embodiments, the node data records607aand607bmay be associated with linear feature points, which may be the linear features to be generated.

Thus, the overall data stored in the map database103amay be organized in the form of different layers for greater detail, clarity, and precision. Specifically, in the case of high-definition maps, the map data may be organized, stored, sorted, and accessed in the form of three or more layers. These layers may include road level layer, lane level layer and localization layer. The data stored in the map database103ain the formats shown inFIGS.6A and6Bmay be combined in a suitable manner to provide these three or more layers of information. In some embodiments, there may be lesser or fewer number of layers of data also possible, without deviating from the scope of the present disclosure.

FIG.6Cillustrates a block diagram600cof the map database103a, in accordance with one or more example embodiments. The map database103astores map data or geographic data613in the form of road segments/links, nodes, and one or more associated attributes as discussed above. For instance, the road segments may be represented using the road segment data records605and the nodes may be represented using the node data records607. The attributes may refer to features or data layers associated with the link-node database, such as an HD lane data layer.

In addition, the map data613may also include other kinds of data609. The other kinds of data609may represent other kinds of geographic features or anything else. For instance, the other kinds of data609may include point of interest data. For example, the point of interest data may include point of interest records comprising a type (e.g., the type of point of interest, such as restaurant, hotel, city hall, police station, historical marker, ATM, golf course, etc.), location of the point of interest, a phone number, hours of operation, etc. The map database103aalso includes indexes611. The indexes611may include various types of indexes that relate the different types of data to each other or that relate to other aspects of the data contained in the geographic database103a.

The data stored in the map database103ain the various formats discussed above may help in provide precise data for high-definition mapping applications, autonomous vehicle navigation and guidance, cruise control using ADAS, direction control using accurate vehicle maneuvering and other such services. For example, the system101may use the map data613along with the sensor data to generate the linear feature data and provide one or more navigation functions for the vehicle such that the unwanted conditions are avoided.