DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
This is a Non-final Office Action on the merits. Claims 1-21 are currently pending and are addressed below.
Priority
Acknowledgement is made of applicant’s claim of priority for foreign application IN202311087200, filed 12/20/2023.
Information Disclosure Statement
The information disclosure statement(s) (IDS) submitted on 12/18/2024 is/are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement(s) is/are being considered by the examiner.
Specification
The disclosure is objected to because of the following informalities:
[0008] recites “…in the described examples does include…”, in which the underlined portion appears to be grammatically incorrect.
[0110] recites “…extends to apparatus…”, which appears to be grammatically incorrect.
Appropriate correction is required.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 3 and 12 rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Regarding claim 3 (and claim 12 for reciting analogous limitations), the phrase "such as" renders the claim indefinite because it is unclear whether the limitations following the phrase are part of the claimed invention. See MPEP § 2173.05(d).
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claim 21 rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. The claim(s) does/do not fall within at least one of the four categories of patent eligible subject matter because the claimed invention is directed to software per se, as seen in the limitation “A computer program product…”.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-8 and 21 is/are rejected under 35 U.S.C. 103 as being unpatentable over Zhang of US 20230298362 A1, published 09/21/2023, hereinafter “Zhang”, in view of Jeong of US 20230126130 A1, published 04/27/2023, hereinafter “Jeong”.
Regarding claim 1, Zhang teaches:
A method of determining geometries of lane boundaries within a road section within a geographical area represented by a digital map, wherein the lane boundaries divide the road section into a set of one or more lanes, the method comprising: (See at least Abstract: “An approach is provided for lane width estimation from incomplete lane marking detections of a road lane. The approach, for example, involves generating one or more perpendicular lines respectively from location centers of one or more first lane marking detections. A respective lane marking detection represents at least a portion of a boundary of the road lane as a line delimited by two location data points in accordance with detections by at least one sensor device onboard at least one vehicle. The approach also involves identifying second lane marking detections that each respectively intersect one of the one or more perpendicular lines. The approach further involves selecting one or more candidate lane widths based on one or more respective distances from the location centers to the second lane marking detections. The approach further involves determining an estimated lane width of the road lane based on the one or more candidate lane widths.”)
obtaining plural sets of data representing a plurality of separate observations of lane boundaries within the road section, wherein different ones of the plural sets of data may represent either observations of the same or of different lane boundaries within the road section, and wherein each set of data includes a respective series of data points spaced along the road section and representing the position of the lane boundary; (See at least Figs. 3-4 & [0040]: “A lane marking detection can be constituted by at least one set of two or more feature points (e.g., location data points such as GPS points or equivalent) such that each set of two feature points represent a segment of the linear feature as a line. Multiple sets of the feature points can then form a polyline representation of the lane marking detection…The lane marking detection can include location data points that are ordered (e.g., the location data points are received with a travel direction) and grouped into at least one set of location data points. Each set respectively represent a separate portion of the lane marking.” See also [0037] regarding determining the lane marking detections from image data.)
identifying from the plural sets of data representing separate observations of lane boundaries within the road section an initial candidate group of sets of data for which it is to be further determined whether the sets of data should be clustered together as relating to the same, first lane boundary, (See at least [0051]: “…For each singular lane marking detection/line, the system 100 can determine (1) a center between each pair of location points 303 as a location center 307 in FIG. 3B (e.g., for selecting/qualifying lane marking detections to proceed to the clustering stage 215)…”)
determining, from the sets of data within the identified initial candidate group of sets of data, a cluster of sets of data that relate to the same, first lane boundary by calculating respective distances between corresponding data points for different sets of data and comparing the calculated distances to a distance threshold; and (See at least Figs. 4A-4B, [0053]: “During the lane marking location center clustering stage 215, the system 100 can cluster singular lane marking detections and/or continuous lane marking detections processed in Stage 213 (using K-means, DBSCAN, etc.) into different lane marking rows based on respective lateral distances to a map-matched road link segment…” & [0056]: “…The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…”)
determining, using the cluster of sets of data that have been determined to relate to the same, first lane boundary, a geometry of the first lane boundary. (See at least [0057]: “In another embodiment, referring back to FIG. 3A, the system 100 can cluster the continuous lane marking detections 301a-301h into three lane marking rows: lane marking detections 301a, 301b in a first lane marking row, lane marking detections 301c, 301d, 301e in a second lane marking row, lane marking detections 301f, 301g in a third lane marking row, while lane marking detection 301h in a fourth lane marking row. The system 100 can calculate candidate lane widths between continuous lane marking detections in different lane marking rows in Stage 217” & [0061]: “The system 100 can generate a candidate lane width for each qualified singular lane marking detection. The length of the perpendicular line from the target lane marking location center (e.g., the lane marking location center 403c) to the intersected location is taken as a candidate lane width shown as in FIG. 4B. Such calculation can be repeated for each singular lane marking detection associated with the road link segment 405 to generate a plurality of candidate lane widths for Stage 219.”)
Zhang does not explicitly teach:
wherein the identifying of the candidate group of sets of data is performed using a spatial indexing system in which the geographical area including the road section is subdivided into a plurality of tiles, each representing a respective subarea of the geographical area, and wherein the positions of the tiles are spatially indexed relative to each other such that it can be determined which tiles are adjacent to each other,
wherein sets of data are identified as being part of the initial candidate group of sets of data based on corresponding ones of the data points for the sets of data fitting into the same tile or in n-level neighbouring tiles of the spatial indexing system;
Jeong teaches:
wherein the identifying of the candidate group of sets of data is performed using a spatial indexing system in which the geographical area including the road section is subdivided into a plurality of tiles, each representing a respective subarea of the geographical area, and wherein the positions of the tiles are spatially indexed relative to each other such that it can be determined which tiles are adjacent to each other, (See at least Figs. 2A-2C & [0023]: “…the polygons representing road segments are joined together with annotating polygons representing other, separately identified, drivable surfaces to provide a total drivable surface. In addition, pursuant to at least some examples, map data including the joined polygons may be divided into hierarchical spatial tiles (e.g., the portions 240 and 245 in FIG. 2B illustrating tiles)…”. See also [0027] regarding spatial indexing.)
wherein sets of data are identified as being part of the initial candidate group of sets of data based on corresponding ones of the data points for the sets of data fitting into the same tile or in n-level neighbouring tiles of the spatial indexing system; (See at least [0035]: “…based on a vehicle pose and vehicle orientation (e.g., actual orientation or proposed orientation based on a proposed trajectory), the map data may be searched to determine a location of a boundary. For example, an initial tile may be identified (based on the pose) as described above. From the initial position, a search may be performed using a ray casting technique (e.g., along the direction of a given ray based on the orientation). For example, when the initial tile is determined to be drivable (e.g., completely within the drivable surface boundary), the search may proceed onto the neighboring tile hit by the ray, until the search identifies a boundary tile. That is, the search may iteratively proceed from one neighboring tile to the next (which may be drivable surface tiles) and along the ray direction until a boundary tile is reached. For example, from the initial position 254, a search may proceed in the direction of the ray 260 until a boundary tile 2312 (e.g., “B” in FIG. 2D) is reached. In some examples, the query may quickly and efficiently determine that tiles 2332 and 2314 are drivable (e.g., based on the identifiers) and move to the boundary tile 2312…”)
One having ordinary skill in the art, before the effective filing date of the claimed invention, would have found it obvious to combine Zhang’s method with Jeong’s tile-based spatial indexing. Doing so would be obvious “to improve search efficiencies” (See [0009] of Jeong).
NOTE: Claim 1 recites the following contingent limitation: “…such that it can be determined which tiles are adjacent to each other…”. This limitation is contingent because it is not positively recited and is instead recited as intended use. Therefore, the BRI of claim 1 does not require the aforementioned limitation.
Regarding claim 2, Zhang and Jeong in combination teach all the limitations of claim 1 as discussed above.
Zhang additionally teaches:
wherein obtaining plural sets of data comprises obtaining plural sets of data in a first format and processing the obtained plural sets of data to a desired format; and optionally wherein obtaining plural sets of data comprises, for each set of data of the plural sets of data: determining that the observation of the lane boundary represented by the set of data extends beyond a geographical limit; and dividing the set of data to form at least two sets of data, wherein one of the new sets of data is located entirely on one side of the geographical limit and the other one of the new sets of data is located entirely on the other side of the geographical limit; and/or optionally wherein obtaining plural sets of data comprises, for each set of data of the plural sets of data: determining that the series of data points within the set of data are not equally spaced along the road section; and resampling the set of data to obtain a set of data including a series of data points which are equally spaced along the road section; and, optionally, wherein a tile size of the spatial indexing system is selected based on a resampling interval, optionally wherein the tile size of the spatial indexing system is selected such that successive data points in a set of data are located in the same tile or in n-level neighbouring tiles in the spatial indexing system. (See at least [0047]: “During the lane marking location and orientation aggregation stage 213, the system 100 can first separate the continuous lane marking detections pre-filtered in Stage 211 into singular lane marking detections…”)
NOTE: Claim 2 recites the following contingent limitations: “…optionally wherein obtaining plural sets of data comprises, for each set of data of the plural sets of data: determining that the observation of the lane boundary represented by the set of data extends beyond a geographical limit; and dividing the set of data to form at least two sets of data, wherein one of the new sets of data is located entirely on one side of the geographical limit and the other one of the new sets of data is located entirely on the other side of the geographical limit; and/or optionally wherein obtaining plural sets of data comprises, for each set of data of the plural sets of data: determining that the series of data points within the set of data are not equally spaced along the road section; and resampling the set of data to obtain a set of data including a series of data points which are equally spaced along the road section; and, optionally, wherein a tile size of the spatial indexing system is selected based on a resampling interval, optionally wherein the tile size of the spatial indexing system is selected such that successive data points in a set of data are located in the same tile or in n-level neighbouring tiles in the spatial indexing system”. This limitation is contingent because recites the term “optionally”. Therefore, the BRI of claim 2 does not require the aforementioned limitations.
Regarding claim 3, Zhang and Jeong in combination teach all the limitations of claim 1 as discussed above.
Jeong additionally teaches:
wherein the spatial indexing system comprises a set of tiles that are regular polygons, such as a set of tiles that are regular hexagonal tiles, optionally wherein the spatial indexing system includes an H3 indexing system. (See at least [0023]: “…the polygons representing road segments are joined together with annotating polygons representing other, separately identified, drivable surfaces to provide a total drivable surface. In addition, pursuant to at least some examples, map data including the joined polygons may be divided into hierarchical spatial tiles (e.g., the portions 240 and 245 in FIG. 2B illustrating tiles)…”. See also [0027] regarding spatial indexing.)
NOTE: Claim 3 recites the following contingent limitation: “…optionally wherein the spatial indexing system includes an H3 indexing system”. This limitation is contingent because recites the term “optionally”. Therefore, the BRI of claim 3 does not require the aforementioned limitation.
Regarding claim 4, Zhang and Jeong in combination teach all the limitations of claim 1 as discussed above.
Zhang additionally teaches:
wherein determining, from the sets of data within the identified initial candidate group, a cluster of sets of data that relate to the same, first lane boundary comprises: calculating a Euclidian distance between a first data point from a first set of data of the initial candidate group and a corresponding first data point from a second set of data of the initial candidate group; (See at least [0055-0056]: “In one embodiment, the system 100 can cluster the singular lane marking detections based on their lateral distances (e.g., signed distances, Euclidean distances, etc.) to a corresponding link segment…FIG. 4A shows five singular lane marking detections 401a-401e with respective location centers 403a-403e towards a map-matched road link segment 405 with signed distances. The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…” & [0059]: “During the candidate lane width estimation stage 217, the system 100 can deploy the location centers (e.g., the location centers 403) to estimate lateral distances between any two singular lane marking detections 401 that are clustered into different lane marking rows in Stage 215…”)
calculating a Euclidian distance between a second data point from the first set of data and a corresponding second data point from the second set of data; (See at least [0076]: “In one embodiment, in step 705, the estimating module 607 can select one or more candidate lane widths based on one or more respective distances (e.g., the lengths of perpendicular lines 411a, 411d in FIG. 4B) from the location centers (e.g., the location center 403c) to the one or more second lane marking detections (e.g., the singular lane marking detections 401a, 401d).”)
determining that the first set of data and the second set of data should be clustered together as relating to the same, first lane boundary when the calculated distances fall below a desired comparison distance threshold; and optionally wherein determining that the first set of data and the second set of data should be clustered together as relating to the same, first lane boundary comprises: determining, based on the number of data points within the first set of data and/or the second set of data, a minimum number of corresponding data points for which a Euclidian distance is to be calculated; calculating a Euclidian distance between the determined number of corresponding pairs of data points from the first set of data and the second set of data; and determining that the first set of data and the second set of data should be grouped together as relating to the same, first lane boundary when all of the calculated distances fall below a desired comparison distance threshold. (See at least [0056]: “…The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…” & [0078]: “…the clustering module 605 can cluster the one or more first lane marking detections, the one or more second lane marking detections, or a combination thereof (e.g., the singular lane marking detections 401a-401e in FIG. 4A) into two or more clusters (e.g., the clusters 409a-409d) based on respective distances (e.g., the lengths of perpendicular lines 407a-407e) to a map-matched road link segment (e.g., the road link segment 405). For instance, at least one cluster (e.g., the cluster 409a) can represent a first lane marking row, and at least one other cluster (e.g., the cluster 409b) can represent at least one second lane marking row…”)
NOTE: Claim 4 recites the following contingent limitations: “…optionally wherein determining that the first set of data and the second set of data should be clustered together as relating to the same, first lane boundary comprises: determining, based on the number of data points within the first set of data and/or the second set of data, a minimum number of corresponding data points for which a Euclidian distance is to be calculated; calculating a Euclidian distance between the determined number of corresponding pairs of data points from the first set of data and the second set of data; and determining that the first set of data and the second set of data should be grouped together as relating to the same, first lane boundary when all of the calculated distances fall below a desired comparison distance threshold”. These limitations are contingent because they recite the term “optionally”. Therefore, the BRI of claim 4 does not require the aforementioned limitations.
Regarding claim 5, Zhang and Jeong in combination teach all the limitations of claim 1 as discussed above.
Zhang additionally teaches:
wherein a first data point of a first set of data is determined to correspond to a first data point of a second set of data based on a distance between the first data point of the first set of data and the first data point of the second set of data being shorter than a distance between the first data point of the first set of data and any other data point of the second set of data. (See at least Fig. 4A & [0056]: “…The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…”)
Regarding claim 6, Zhang and Jeong in combination teach all the limitations of claim 1 as discussed above.
Zhang additionally teaches:
wherein obtaining data comprises obtaining data from a plurality of separate journeys along the road section; and/or wherein the data in the plural sets of data is sensor data from on-board sensors. (See at least [0034]: “…vehicles 103 (e.g., equipped with vehicle sensors 104, such as camera), user equipment (UE) devices 105 (e.g., equipped with sensors 106, such as camera, and/or executing respective applications 107 for generating and reporting lane marking detections 109 from sensor data/image data), and/or any other devices capable of traveling over a road network can be used to collect lane marking detections 109 for lane width estimation from incomplete lane marking detections of a road lane…”)
Regarding claim 7, Zhang and Jeong in combination teach all the limitations of claim 1 as discussed above.
Zhang additionally teaches:
further comprising: generating a bounding box that encompasses the data points for all sets of data within the determined cluster; (See at least Fig. 4A, clusters 409a-409d)
determining the geometry of the lane boundary using the generated bounding box; and (See at least [0059]: “During the candidate lane width estimation stage 217, the system 100 can deploy the location centers (e.g., the location centers 403) to estimate lateral distances between any two singular lane marking detections 401 that are clustered into different lane marking rows in Stage 215. FIG. 4B is a diagram illustrating how to determine/estimate one or more candidate lane widths from location centers of singular lane marking detections, according to example embodiment(s). For instance, given the lane marking location center 403c of the lane marking detection 401c, perpendicular lines 411a, 411b, 411c can be drawn to its nearby singular lane marking detections/lines 401a, 401b, 401d to identify qualified singular lane marking detections.”)
updating the digital map to include the determined geometry of the first lane boundary; optionally wherein determining the geometry of the lane boundary using the generated bounding box comprises: determining a centreline of the bounding box, and using the determined centreline to determine the geometry of the lane boundary. (See at least [0085]: “Another use case includes identifying a lane width change or error of the geographic database 115. In this use case, the lane marking representation generated from sensor data captured by a mapping vehicle (e.g., a vehicle 103 with high accuracy location sensors) is compared against existing map data of the geographic database 115 to identify potential discrepancies and updated accordingly. This potential lane width error can then be marked and presented by manual review, verification, additional map data collection, etc.”)
NOTE: Claim 7 recites the following contingent limitations: “…optionally wherein determining the geometry of the lane boundary using the generated bounding box comprises: determining a centreline of the bounding box, and using the determined centreline to determine the geometry of the lane boundary”. These limitations are contingent because they recite the term “optionally”. Therefore, the BRI of claim 7 does not require the aforementioned limitations.
Regarding claim 8, Zhang and Jeong in combination teach all the limitations of claim 1 as discussed above.
Jeong additionally teaches:
wherein the method is performed in a distributed processing system including plural data processors configured to execute data processing operations, the method further comprising: (See at least Fig. 5 & [0071]: “The vehicle 502 can connect to computing device(s) 544 via network 542 and can include one or more processor(s) 546 and memory 548 communicatively coupled with the one or more processor(s) 546…”)
allocating data processing operations to respective ones of the plural data processors such that processing relating to an initial candidate group is performed by the same data processor. (See at least [0071]: “…the memory 548 may include a maps editor 550 for generating map data including a total drivable surface boundary. For example, the maps editor 550 may execute operations for generating drivable surface polygons (e.g., road-segment polygons) and unioning drivable surface polygons…”)
Regarding claim 21, Zhang teaches:
A computer program product including a set of instructions that, when executed by one or more processors, will perform a method of determining geometries of lane boundaries within a road section within a geographical area represented by a digital map, wherein the lane boundaries divide the road section into a set of one or more lanes, the method comprising: (See at least Abstract: “An approach is provided for lane width estimation from incomplete lane marking detections of a road lane. The approach, for example, involves generating one or more perpendicular lines respectively from location centers of one or more first lane marking detections. A respective lane marking detection represents at least a portion of a boundary of the road lane as a line delimited by two location data points in accordance with detections by at least one sensor device onboard at least one vehicle. The approach also involves identifying second lane marking detections that each respectively intersect one of the one or more perpendicular lines. The approach further involves selecting one or more candidate lane widths based on one or more respective distances from the location centers to the second lane marking detections. The approach further involves determining an estimated lane width of the road lane based on the one or more candidate lane widths.”)
obtaining plural sets of data representing a plurality of separate observations of lane boundaries within the road section, wherein different ones of the plural sets of data may represent either observations of the same or of different lane boundaries within the road section, and wherein each set of data includes a respective series of data points spaced along the road section and representing the position of the lane boundary; (See at least Figs. 3-4 & [0040]: “A lane marking detection can be constituted by at least one set of two or more feature points (e.g., location data points such as GPS points or equivalent) such that each set of two feature points represent a segment of the linear feature as a line. Multiple sets of the feature points can then form a polyline representation of the lane marking detection…The lane marking detection can include location data points that are ordered (e.g., the location data points are received with a travel direction) and grouped into at least one set of location data points. Each set respectively represent a separate portion of the lane marking.” See also [0037] regarding determining the lane marking detections from image data.)
identifying from the plural sets of data representing separate observations of lane boundaries within the road section an initial candidate group of sets of data for which it is to be further determined whether the sets of data should be clustered together as relating to the same, first lane boundary, (See at least [0051]: “…For each singular lane marking detection/line, the system 100 can determine (1) a center between each pair of location points 303 as a location center 307 in FIG. 3B (e.g., for selecting/qualifying lane marking detections to proceed to the clustering stage 215)…”)
determining, from the sets of data within the identified initial candidate group of sets of data, a cluster of sets of data that relate to the same, first lane boundary by calculating respective distances between corresponding data points for different sets of data and comparing the calculated distances to a distance threshold; and (See at least Figs. 4A-4B, [0053]: “During the lane marking location center clustering stage 215, the system 100 can cluster singular lane marking detections and/or continuous lane marking detections processed in Stage 213 (using K-means, DBSCAN, etc.) into different lane marking rows based on respective lateral distances to a map-matched road link segment…” & [0056]: “…The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…”)
determining, using the cluster of sets of data that have been determined to relate to the same, first lane boundary, a geometry of the first lane boundary, and/or an apparatus including one or more processors configured to perform said method. (See at least [0057]: “In another embodiment, referring back to FIG. 3A, the system 100 can cluster the continuous lane marking detections 301a-301h into three lane marking rows: lane marking detections 301a, 301b in a first lane marking row, lane marking detections 301c, 301d, 301e in a second lane marking row, lane marking detections 301f, 301g in a third lane marking row, while lane marking detection 301h in a fourth lane marking row. The system 100 can calculate candidate lane widths between continuous lane marking detections in different lane marking rows in Stage 217” & [0061]: “The system 100 can generate a candidate lane width for each qualified singular lane marking detection. The length of the perpendicular line from the target lane marking location center (e.g., the lane marking location center 403c) to the intersected location is taken as a candidate lane width shown as in FIG. 4B. Such calculation can be repeated for each singular lane marking detection associated with the road link segment 405 to generate a plurality of candidate lane widths for Stage 219.”)
Zhang does not explicitly teach:
wherein the identifying of the candidate group of sets of data is performed using a spatial indexing system in which the geographical area including the road section is subdivided into a plurality of tiles, each representing a respective subarea of the geographical area, and wherein the positions of the tiles are spatially indexed relative to each other such that it can be determined which tiles are adjacent to each other,
wherein sets of data are identified as being part of the initial candidate group of sets of data based on corresponding ones of the data points for the sets of data fitting into the same tile or in n-level neighbouring tiles of the spatial indexing system;
Jeong teaches:
wherein the identifying of the candidate group of sets of data is performed using a spatial indexing system in which the geographical area including the road section is subdivided into a plurality of tiles, each representing a respective subarea of the geographical area, and wherein the positions of the tiles are spatially indexed relative to each other such that it can be determined which tiles are adjacent to each other, (See at least Figs. 2A-2C & [0023]: “…the polygons representing road segments are joined together with annotating polygons representing other, separately identified, drivable surfaces to provide a total drivable surface. In addition, pursuant to at least some examples, map data including the joined polygons may be divided into hierarchical spatial tiles (e.g., the portions 240 and 245 in FIG. 2B illustrating tiles)…”. See also [0027] regarding spatial indexing.)
wherein sets of data are identified as being part of the initial candidate group of sets of data based on corresponding ones of the data points for the sets of data fitting into the same tile or in n-level neighbouring tiles of the spatial indexing system; (See at least [0035]: “…based on a vehicle pose and vehicle orientation (e.g., actual orientation or proposed orientation based on a proposed trajectory), the map data may be searched to determine a location of a boundary. For example, an initial tile may be identified (based on the pose) as described above. From the initial position, a search may be performed using a ray casting technique (e.g., along the direction of a given ray based on the orientation). For example, when the initial tile is determined to be drivable (e.g., completely within the drivable surface boundary), the search may proceed onto the neighboring tile hit by the ray, until the search identifies a boundary tile. That is, the search may iteratively proceed from one neighboring tile to the next (which may be drivable surface tiles) and along the ray direction until a boundary tile is reached. For example, from the initial position 254, a search may proceed in the direction of the ray 260 until a boundary tile 2312 (e.g., “B” in FIG. 2D) is reached. In some examples, the query may quickly and efficiently determine that tiles 2332 and 2314 are drivable (e.g., based on the identifiers) and move to the boundary tile 2312…”)
One having ordinary skill in the art, before the effective filing date of the claimed invention, would have found it obvious to combine Zhang’s method with Jeong’s tile-based spatial indexing. Doing so would be obvious “to improve search efficiencies” (See [0009] of Jeong).
Claim(s) 9-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Zhang in view of Liebner of US 20250102307 A1, filed 12/01/2022, hereinafter “Liebner”, and further in view of Jeong.
Regarding claim 9, Zhang teaches:
A method of determining a position of a lane boundary within a road section within a geographical area represented by a digital map, wherein the road section is divided into a set of one or more lanes each bounded by two lane boundaries, (See at least Abstract: “An approach is provided for lane width estimation from incomplete lane marking detections of a road lane. The approach, for example, involves generating one or more perpendicular lines respectively from location centers of one or more first lane marking detections. A respective lane marking detection represents at least a portion of a boundary of the road lane as a line delimited by two location data points in accordance with detections by at least one sensor device onboard at least one vehicle. The approach also involves identifying second lane marking detections that each respectively intersect one of the one or more perpendicular lines. The approach further involves selecting one or more candidate lane widths based on one or more respective distances from the location centers to the second lane marking detections. The approach further involves determining an estimated lane width of the road lane based on the one or more candidate lane widths.”)
identifying from the obtained plural sets of data an initial candidate group of sets of data for which it is to be further determined whether the sets of data should be clustered together as relating to the same, first lane boundary; (See at least [0051]: “…For each singular lane marking detection/line, the system 100 can determine (1) a center between each pair of location points 303 as a location center 307 in FIG. 3B (e.g., for selecting/qualifying lane marking detections to proceed to the clustering stage 215)…”)
determining, from the sets of data within the identified initial candidate group of sets of data, a first cluster of sets of data that relate to the same, first lane boundary by calculating respective distances between corresponding data points for different sets of data and comparing the calculated distances to a distance threshold; and (See at least Figs. 4A-4B, [0053]: “During the lane marking location center clustering stage 215, the system 100 can cluster singular lane marking detections and/or continuous lane marking detections processed in Stage 213 (using K-means, DBSCAN, etc.) into different lane marking rows based on respective lateral distances to a map-matched road link segment…” & [0056]: “…The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…”)
determining, using the first cluster of sets of data that have been determined to relate to the same, first lane boundary, the position of the lane boundary. (See at least [0057]: “In another embodiment, referring back to FIG. 3A, the system 100 can cluster the continuous lane marking detections 301a-301h into three lane marking rows: lane marking detections 301a, 301b in a first lane marking row, lane marking detections 301c, 301d, 301e in a second lane marking row, lane marking detections 301f, 301g in a third lane marking row, while lane marking detection 301h in a fourth lane marking row. The system 100 can calculate candidate lane widths between continuous lane marking detections in different lane marking rows in Stage 217” & [0061]: “The system 100 can generate a candidate lane width for each qualified singular lane marking detection. The length of the perpendicular line from the target lane marking location center (e.g., the lane marking location center 403c) to the intersected location is taken as a candidate lane width shown as in FIG. 4B. Such calculation can be repeated for each singular lane marking detection associated with the road link segment 405 to generate a plurality of candidate lane widths for Stage 219.”)
However, Zhang does not explicitly teach obtaining plural sets of data including a series of data points along a road section representing different vehicle trajectories or determining a position of a lane centerline.
Liebner teaches determining reference driving paths, which describe “the profile and the absolute position of the center line of lanes,” based on a “multiplicity of measured driving paths” from different vehicles (See at least [0029], [0103-0104] & [0110]). Liebner further teaches using a clustering algorithm to convert points of intersection for a set of measured driving paths into a set of interpolation points that are joined to form the reference driving path (See at least Fig. 2a-2d & [0112-0114]).
One having ordinary skill in the art, before the effective filing date of the claimed invention, would have found it obvious to combine Zhang’s method with Liebner’s technique of obtaining plural sets of data including a series of data points along a road section representing different vehicle trajectories and determining a position of a lane centerline. Doing so would be obvious “to reliably avoid determining non-existent lane center lines, thereby making it possible to increase the quality of autonomous driving functions.” (See [0115] of Liebner).
Zhang and Liebner in combination do not explicitly teach:
wherein the identifying of the initial candidate group of sets of data is performed using a spatial indexing system in which the geographical area including the road section is subdivided into a plurality of tiles, each representing a respective subarea of the geographical area, and wherein the positions of the tiles are spatially indexed relative to each other such that it can be determined which tiles are adjacent to each other,
wherein sets of data are identified as being part of the initial candidate group of sets of data based on corresponding ones of the data points for the sets of data fitting into the same tile or in n-level neighbouring tiles of the spatial indexing system;
Jeong teaches:
wherein the identifying of the initial candidate group of sets of data is performed using a spatial indexing system in which the geographical area including the road section is subdivided into a plurality of tiles, each representing a respective subarea of the geographical area, and wherein the positions of the tiles are spatially indexed relative to each other such that it can be determined which tiles are adjacent to each other, (See at least Figs. 2A-2C & [0023]: “…the polygons representing road segments are joined together with annotating polygons representing other, separately identified, drivable surfaces to provide a total drivable surface. In addition, pursuant to at least some examples, map data including the joined polygons may be divided into hierarchical spatial tiles (e.g., the portions 240 and 245 in FIG. 2B illustrating tiles)…”. See also [0027] regarding spatial indexing.)
wherein sets of data are identified as being part of the initial candidate group of sets of data based on corresponding ones of the data points for the sets of data fitting into the same tile or in n-level neighbouring tiles of the spatial indexing system; (See at least [0035]: “…based on a vehicle pose and vehicle orientation (e.g., actual orientation or proposed orientation based on a proposed trajectory), the map data may be searched to determine a location of a boundary. For example, an initial tile may be identified (based on the pose) as described above. From the initial position, a search may be performed using a ray casting technique (e.g., along the direction of a given ray based on the orientation). For example, when the initial tile is determined to be drivable (e.g., completely within the drivable surface boundary), the search may proceed onto the neighboring tile hit by the ray, until the search identifies a boundary tile. That is, the search may iteratively proceed from one neighboring tile to the next (which may be drivable surface tiles) and along the ray direction until a boundary tile is reached. For example, from the initial position 254, a search may proceed in the direction of the ray 260 until a boundary tile 2312 (e.g., “B” in FIG. 2D) is reached. In some examples, the query may quickly and efficiently determine that tiles 2332 and 2314 are drivable (e.g., based on the identifiers) and move to the boundary tile 2312…”)
One having ordinary skill in the art, before the effective filing date of the claimed invention, would have found it obvious to combine Zhang and Liebner’s method with Jeong’s tile-based spatial indexing. Doing so would be obvious “to improve search efficiencies” (See [0009] of Jeong).
NOTE: Claim 9 recites the following contingent limitation: “…such that it can be determined which tiles are adjacent to each other…”. This limitation is contingent because it is not positively recited and is instead recited as intended use. Therefore, the BRI of claim 1 does not require the aforementioned limitation.
Regarding claim 10, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Zhang additionally teaches:
wherein obtaining plural sets of data comprises obtaining plural sets of data in a first format and processing the obtained plural sets of data to a desired format; and/or wherein obtaining plural sets of data comprises, for each set of data of the plural sets of data: determining that the series of data points within the set of data are not equally spaced along the road section; and resampling the set of data to obtain a set of data including a series of data points which are equally spaced along the road section. (See at least [0047]: “During the lane marking location and orientation aggregation stage 213, the system 100 can first separate the continuous lane marking detections pre-filtered in Stage 211 into singular lane marking detections…”)
Regarding claim 11, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Jeong additionally teaches:
wherein the spatial indexing system is a hierarchical spatial indexing system including a first level having a first tile size and a second level having a second, smaller, tile size, (See at least [0023]: “…the polygons representing road segments are joined together with annotating polygons representing other, separately identified, drivable surfaces to provide a total drivable surface. In addition, pursuant to at least some examples, map data including the joined polygons may be divided into hierarchical spatial tiles (e.g., the portions 240 and 245 in FIG. 2B illustrating tiles)…”)
wherein each portion of the road section corresponds to an area covered by a respective tile of the first level of the spatial indexing system, (See at least [0027]: “…In the map data 220, a hierarchical data structure is illustrated in which a node “2” (e.g., first-level tile) has been divided into four sub-tiles (e.g., second-level tiles), including nodes “21,” “22,” “23,” and “24.” In addition, as depicted by the map data 235, which may be a lower level abstraction 236 of the map data 220, any of the four second-level nodes may be further divided into four, third-level tiles (e.g., 211-214; 221-224; 231-234; and 241-244). The map data 225 is also illustrated with a spatial data structure, in which a node “N2” (e.g., second level tile where “N” could be any integer) has been divided into sub-tiles (e.g., N21, N22, N23, and N24), at least some of which may be further divided into lower-level sub-tiles.”)
wherein obtaining plural sets of data comprises determining, for each set of data, one or more sets of data points, wherein each set of data points includes data points which fit within a respective tile of the first level, and (See at least [0030]: “In accordance with an example of the present disclosure, the polygons are unioned in leaf tiles. That is, a tile may be classified based on whether the tile is either completely within a drivable surface boundary, inclusive of a drivable surface boundary (e.g., a boundary segment extends through the tile), or entirely outside of a drivable surface boundary. For example, tiles N21 and N23 are completely within an outer drivable surface boundary 237 of the parking-lane polygon 230, such that these tiles may be classified as a drivable-type tile. In addition, since the entire N21 node and N23 node are classified as a drivable-type tile, the conversion need not further divide/partition the N21 node and the N23 node into sub-tiles (e.g., need not further divide into leaf tiles)…”)
wherein the tiles used to identify the initial candidate group of sets of data are tiles of the second level. (See at least [0030]: “…In another example, nodes N22 and N24 both include the outer boundary 237 and may be classified as a boundary-type tile. As such, any of the nodes N22 and N24 may be divided/partitioned into leaf-tiles (e.g., N221, N222, N223, N224, N241, and N242), and any of the leaf tiles may be further classified. For example, leaf tiles N221, N223, and N241 may be classified as a drivable-type tile (e.g., entirely within the drivable surface), and leaf tiles N222, N224, and N242 may be classified as boundary-type tiles (e.g., inclusive of a portion of the boundary 237)…”)
Regarding claim 12, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Jeong additionally teaches:
wherein the spatial indexing system comprises a set of tiles that are regular polygons, such as a set of tiles that are regular hexagonal tiles, optionally wherein the spatial indexing system includes an H3 indexing system. (See at least [0023]: “…the polygons representing road segments are joined together with annotating polygons representing other, separately identified, drivable surfaces to provide a total drivable surface. In addition, pursuant to at least some examples, map data including the joined polygons may be divided into hierarchical spatial tiles (e.g., the portions 240 and 245 in FIG. 2B illustrating tiles)…”. See also [0027] regarding spatial indexing.)
NOTE: Claim 12 recites the following contingent limitation: “…optionally wherein the spatial indexing system includes an H3 indexing system”. This limitation is contingent because recites the term “optionally”. Therefore, the BRI of claim 12 does not require the aforementioned limitation.
Regarding claim 13, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 11 as discussed above.
Jeong additionally teaches:
wherein a tile size of the tiles of the first level of the spatial indexing system is selected based on a dimension of the road section. (See at least [0024]: “…map data 201 indicating road segments may include control points (e.g., 202a, 202b, and 202c), tangent constraints (e.g., represented by the arrow 202d), and lane widths (e.g., 204a and 204b). In some examples, map data 201 may be used to generate 203 polygons (e.g., 206a, 206b, and 206c) representing road segments, as depicted by map data 205. That is, road-segment polygons may be generated in a post process, after map editing is completed (e.g., after the map data has been labeled to include various information, including the control points). For example, an adaptive curve sampling technique may be applied to the control points to generate simple polygons representing road segments. That is, a collection of Piecewise Clothoid Curves (PCC) may be fit to the control points (e.g., 202a-202c), and the curves may be iteratively sub-divided (e.g., see curve samples 202e) until they meet a curve constraint (e.g., user defined max length, max radian length, etc.). In some examples, the curves may be used to determine a longitudinal dimension of polygons. In addition, from the sub-divided curves, outermost lane boundaries (e.g., 208a, 208b, 208c, and 208d) may be determined based on the lane widths, which may provide opposing sides of the polygons. In examples, lateral dimensions may be based on the lane width(s). In addition, in some examples, the polygons may be longitudinally extended to ensure overlap with adjacent road segments.”)
Regarding claim 14, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Zhang additionally teaches:
wherein determining, from the sets of data within the identified first initial candidate group, a cluster of sets of data that relate to the same, first lane boundary comprises: calculating a Euclidian distance between a first data point from a first set of data of the first initial candidate group and a corresponding first data point from a second set of data of the first initial candidate group; (See at least [0055-0056]: “In one embodiment, the system 100 can cluster the singular lane marking detections based on their lateral distances (e.g., signed distances, Euclidean distances, etc.) to a corresponding link segment…FIG. 4A shows five singular lane marking detections 401a-401e with respective location centers 403a-403e towards a map-matched road link segment 405 with signed distances. The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…” & [0059]: “During the candidate lane width estimation stage 217, the system 100 can deploy the location centers (e.g., the location centers 403) to estimate lateral distances between any two singular lane marking detections 401 that are clustered into different lane marking rows in Stage 215…”)
calculating a Euclidian distance between a second data point from the first set of data and a corresponding second data point from the second set of data; (See at least [0076]: “In one embodiment, in step 705, the estimating module 607 can select one or more candidate lane widths based on one or more respective distances (e.g., the lengths of perpendicular lines 411a, 411d in FIG. 4B) from the location centers (e.g., the location center 403c) to the one or more second lane marking detections (e.g., the singular lane marking detections 401a, 401d).”)
determining that the first set of data and the second set of data should be clustered together as relating to the same, first lane boundary when the calculated distances fall below a desired comparison distance threshold. (See at least [0056]: “…The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…” & [0078]: “…the clustering module 605 can cluster the one or more first lane marking detections, the one or more second lane marking detections, or a combination thereof (e.g., the singular lane marking detections 401a-401e in FIG. 4A) into two or more clusters (e.g., the clusters 409a-409d) based on respective distances (e.g., the lengths of perpendicular lines 407a-407e) to a map-matched road link segment (e.g., the road link segment 405). For instance, at least one cluster (e.g., the cluster 409a) can represent a first lane marking row, and at least one other cluster (e.g., the cluster 409b) can represent at least one second lane marking row…”)
Liebner additionally teaches determining a reference driving path that indicates the profile and position of the center line of a lane, as discussed above in parent claim 9. Liebner further teaches determining the reference driving path, and thus the lane centerline, using a clustering algorithm and a distance metric such as “a Euclidean distance between the end point of the particular reference driving path and the starting point of the following reference driving path” (See at least [0043-0044] & [0138]).
Regarding claim 15, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Zhang additionally teaches:
wherein determining that the first set of data and the second set of data should be clustered together as relating to the same, first lane boundary comprises: determining, based on the number of data points within the first set of data and/or the second set of data, a minimum number of corresponding data points for which a Euclidian distance is to be calculated; (See at least [0051]: “…For each singular lane marking detection/line, the system 100 can determine (1) a center between each pair of location points 303 as a location center 307 in FIG. 3B (e.g., for selecting/qualifying lane marking detections to proceed to the clustering stage 215)…”)
calculating a Euclidian distance between the determined number of corresponding pairs of data points from the first set of data and the second set of data; and (See at least [0055]: “In one embodiment, the system 100 can cluster the singular lane marking detections based on their lateral distances (e.g., signed distances, Euclidean distances, etc.) to a corresponding link segment…” & [0059]: “During the candidate lane width estimation stage 217, the system 100 can deploy the location centers (e.g., the location centers 403) to estimate lateral distances between any two singular lane marking detections 401 that are clustered into different lane marking rows in Stage 215. FIG. 4B is a diagram illustrating how to determine/estimate one or more candidate lane widths from location centers of singular lane marking detections, according to example embodiment(s). For instance, given the lane marking location center 403c of the lane marking detection 401c, perpendicular lines 411a, 411b, 411c can be drawn to its nearby singular lane marking detections/lines 401a, 401b, 401d to identify qualified singular lane marking detections.” See also [0076].)
determining that the first set of data and the second set of data should be grouped together as relating to the same, first lane boundary when all of the calculated distances fall below a desired comparison distance threshold. (See at least [0056]: “…The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…” & [0078]: “…the clustering module 605 can cluster the one or more first lane marking detections, the one or more second lane marking detections, or a combination thereof (e.g., the singular lane marking detections 401a-401e in FIG. 4A) into two or more clusters (e.g., the clusters 409a-409d) based on respective distances (e.g., the lengths of perpendicular lines 407a-407e) to a map-matched road link segment (e.g., the road link segment 405). For instance, at least one cluster (e.g., the cluster 409a) can represent a first lane marking row, and at least one other cluster (e.g., the cluster 409b) can represent at least one second lane marking row…”)
Liebner additionally teaches determining a reference driving path that indicates the profile and position of the center line of a lane, as discussed above in parent claim 9. Liebner further teaches determining the reference driving path, and thus the lane centerline, using a clustering algorithm and a distance metric such as “a Euclidean distance between the end point of the particular reference driving path and the starting point of the following reference driving path” (See at least [0043-0045] & [0138]).
Regarding claim 16, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Zhang additionally teaches:
wherein a first data point of a first set of data is determined to correspond to a first data point of a second set of data based on a distance between the first data point of the first set of data and the first data point of the second set of data being shorter than a distance between the first data point of the first set of data and any other data point of the second set of data. (See at least Fig. 4A & [0056]: “…The location center pairs (e.g., singular lane marking detections 401d, 401e) with signed distances ranged in −5 meters and −5.1 meters can be put into the same cluster (e.g., a cluster 409a), while location center pairs (e.g., each of singular lane marking detections 401a, 401b, 410c forms their own clusters 409b, 409c, 409d) with signed distances ranged −5 meters and −2 meters can be put into different clusters…”)
Regarding claim 17, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Liebner additionally teaches:
further comprising: identifying that the road section includes a road junction located in a subarea of the geographical area represented by the digital map, the road junction allowing one of a plurality of different routes to be taken by a vehicle passing through the road junction, wherein at least a portion of each of at least two of the plurality of different routes overlaps; and (See at least [0126]: “In the case of a fork in a road 150 (for example at an exit or at an intersection) into two different adjoining roads 150 with different orientations, the measured driving paths 160 of vehicles 110 in a road section may differ depending on whether the vehicle 110 then drives onto the road section into the first adjoining road 150 or into the second adjoining road 150. By way of example, at a turning, the measured driving paths 160 of vehicles 110 driving straight ahead may differ (statistically) from the measured driving paths 160 of vehicles 110 that turn off. This is illustrated for example for a turning situation 400 in FIG. 4a. FIG. 4a in particular shows a (core) road section 410 followed by a following first (surrounding) road section 410 (when driving straight ahead) and followed by a second (surrounding) road section 410 (when turning right).”)
performing processing to deduplicate the overlapping portions of the different routes. (See at least Figs. 2a-2c & [0124]: “The method 300 furthermore comprises determining 304, for each of the sequence of interpolation point planes 271, a respective set of interpolation points 200 on the basis of the determined points of intersection 272 with the respective interpolation point plane 271. For this purpose, one or more clusters of points of intersection 272 may be determined in each individual interpolation point plane 271 on the basis of a clustering algorithm. Furthermore, a respective interpolation point 200 may be determined on the basis of each cluster (for example as a (possibly trimmed) average of the points of intersection 272 in the cluster).”)
Regarding claim 18, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Zhang additionally teaches:
wherein the data in the plural sets of data is sensor data from on-board sensors; and/or wherein the data in the plural sets of data is GNSS data, such as GPS data. (See at least [0034]: “…vehicles 103 (e.g., equipped with vehicle sensors 104, such as camera), user equipment (UE) devices 105 (e.g., equipped with sensors 106, such as camera, and/or executing respective applications 107 for generating and reporting lane marking detections 109 from sensor data/image data), and/or any other devices capable of traveling over a road network can be used to collect lane marking detections 109 for lane width estimation from incomplete lane marking detections of a road lane…”)
Regarding claim 19, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Zhang additionally teaches:
further comprising: generating a bounding box that encompasses the data points for all sets of data within the determined cluster; (See at least Fig. 4A, clusters 409a-409d)
determining the position of the lane boundary using the generated bounding box; and (See at least [0059]: “During the candidate lane width estimation stage 217, the system 100 can deploy the location centers (e.g., the location centers 403) to estimate lateral distances between any two singular lane marking detections 401 that are clustered into different lane marking rows in Stage 215. FIG. 4B is a diagram illustrating how to determine/estimate one or more candidate lane widths from location centers of singular lane marking detections, according to example embodiment(s). For instance, given the lane marking location center 403c of the lane marking detection 401c, perpendicular lines 411a, 411b, 411c can be drawn to its nearby singular lane marking detections/lines 401a, 401b, 401d to identify qualified singular lane marking detections.”)
updating the digital map to include the determined lane boundary; and, optionally, wherein determining the position of the lane centreline using the generated bounding box includes: determining a centreline of the bounding box; and using the determined centreline of the bounding box to determine the lane centreline. (See at least [0085]: “Another use case includes identifying a lane width change or error of the geographic database 115. In this use case, the lane marking representation generated from sensor data captured by a mapping vehicle (e.g., a vehicle 103 with high accuracy location sensors) is compared against existing map data of the geographic database 115 to identify potential discrepancies and updated accordingly. This potential lane width error can then be marked and presented by manual review, verification, additional map data collection, etc.”)
Liebner additionally teaches providing the reference driving paths, which indicate the position of lane centerlines, as map data for an HD map, which can then be used by vehicles to determine target trajectories (See at least [0014], [0029] & [0168]).
NOTE: Claim 19 recites the following contingent limitations: “…optionally, wherein determining the position of the lane centreline using the generated bounding box includes: determining a centreline of the bounding box; and using the determined centreline of the bounding box to determine the lane centreline”. These limitations are contingent because they recite the term “optionally”. Therefore, the BRI of claim 19 does not require the aforementioned limitations.
Regarding claim 20, Zhang, Liebner, and Jeong in combination teach all the limitations of claim 9 as discussed above.
Jeong additionally teaches:
wherein the method is performed in a distributed processing system including plural data processors configured to execute data processing operations, the method further comprising: (See at least Fig. 5 & [0071]: “The vehicle 502 can connect to computing device(s) 544 via network 542 and can include one or more processor(s) 546 and memory 548 communicatively coupled with the one or more processor(s) 546…”)
allocating data processing operations to respective ones of the plural data processors such that processing relating to an initial candidate group is performed by the same data processor. (See at least [0071]: “…the memory 548 may include a maps editor 550 for generating map data including a total drivable surface boundary. For example, the maps editor 550 may execute operations for generating drivable surface polygons (e.g., road-segment polygons) and unioning drivable surface polygons…”)
NOTE: Claim 20 recites the following contingent limitation: “…such that processing relating to an initial candidate group is performed by the same data processor”. This limitation is contingent because it is not positively recited and is instead recited as intended use. Therefore, the BRI of claim 20 does not require the aforementioned limitation.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
US 20220309281 A1 is directed to determining lane centerlines and boundaries using filtered sets of data.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Nikki Molina whose telephone number is (571) 272-5180. The examiner can normally be reached Monday - Thursday and alternate Fridays, 7:30-4:30 PT. Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice. If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Aniss Chad, can be reached on (571) 270-3832. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300. Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/NIKKI MARIE M MOLINA/Examiner, Art Unit 3662
/ANISS CHAD/Supervisory Patent Examiner, Art Unit 3662
Prosecution Insights