[go: up one dir, main page]

CN110036392B - 用于基于多行程数据来绘图的系统和方法 - Google Patents

用于基于多行程数据来绘图的系统和方法 Download PDF

Info

Publication number
CN110036392B
CN110036392B CN201780075008.6A CN201780075008A CN110036392B CN 110036392 B CN110036392 B CN 110036392B CN 201780075008 A CN201780075008 A CN 201780075008A CN 110036392 B CN110036392 B CN 110036392B
Authority
CN
China
Prior art keywords
data
clustering
object data
similarity measure
cluster
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201780075008.6A
Other languages
English (en)
Other versions
CN110036392A (zh
Inventor
O·J·达比尔
K·索马孙达拉姆
R·D·高韦卡尔
R·T·苏克哈瓦斯
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Qualcomm Inc
Original Assignee
Qualcomm Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Qualcomm Inc filed Critical Qualcomm Inc
Priority to CN202410054447.0A priority Critical patent/CN117889874A/zh
Publication of CN110036392A publication Critical patent/CN110036392A/zh
Application granted granted Critical
Publication of CN110036392B publication Critical patent/CN110036392B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V20/00—Scenes; Scene-specific elements
    • G06V20/50—Context or environment of the image
    • G06V20/56—Context or environment of the image exterior to a vehicle by using sensors mounted on the vehicle
    • G06V20/58—Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads
    • G06V20/582—Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads of traffic signs
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V20/00—Scenes; Scene-specific elements
    • G06V20/50—Context or environment of the image
    • G06V20/56—Context or environment of the image exterior to a vehicle by using sensors mounted on the vehicle
    • G06V20/588—Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/28—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network with correlation of data from several navigational instruments
    • G01C21/30—Map- or contour-matching
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/28—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network with correlation of data from several navigational instruments
    • G01C21/30—Map- or contour-matching
    • G01C21/32—Structuring or formatting of map data
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34—Route searching; Route guidance
    • G01C21/36—Input/output arrangements for on-board computers
    • G01C21/3602—Input other than that of destination using image analysis, e.g. detection of road signs, lanes, buildings, real preceding vehicles using a camera
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/38—Electronic maps specially adapted for navigation; Updating thereof
    • G01C21/3804—Creation or updating of map data
    • G01C21/3833—Creation or updating of map data characterised by the source of data
    • G01C21/3841—Data obtained from two or more sources, e.g. probe vehicles
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/38—Electronic maps specially adapted for navigation; Updating thereof
    • G01C21/3863—Structures of map data
    • G01C21/3867—Geometry of map features, e.g. shape points, polygons or for simplified maps
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/38—Electronic maps specially adapted for navigation; Updating thereof
    • G01C21/3863—Structures of map data
    • G01C21/387—Organisation of map data, e.g. version management or database structures
    • G01C21/3881—Tile-based structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/21—Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
    • G06F18/213—Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
    • G06F18/2135—Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods based on approximation criteria, e.g. principal component analysis
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/22—Matching criteria, e.g. proximity measures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/23—Clustering techniques
    • G06F18/231—Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/23—Clustering techniques
    • G06F18/232—Non-hierarchical techniques
    • G06F18/2321—Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions
    • G06F18/23213—Non-hierarchical techniques using statistics or function optimisation, e.g. modelling of probability density functions with fixed number of clusters, e.g. K-means clustering
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/05—Geographic models
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/74—Image or video pattern matching; Proximity measures in feature spaces
    • G06V10/761—Proximity, similarity or dissimilarity measures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/762—Arrangements for image or video recognition or understanding using pattern recognition or machine learning using clustering, e.g. of similar faces in social networks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/762—Arrangements for image or video recognition or understanding using pattern recognition or machine learning using clustering, e.g. of similar faces in social networks
    • G06V10/7625—Hierarchical techniques, i.e. dividing or merging patterns to obtain a tree-like representation; Dendograms
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/762—Arrangements for image or video recognition or understanding using pattern recognition or machine learning using clustering, e.g. of similar faces in social networks
    • G06V10/763—Non-hierarchical techniques, e.g. based on statistics of modelling distributions
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/77—Processing image or video features in feature spaces; using data integration or data reduction, e.g. principal component analysis [PCA] or independent component analysis [ICA] or self-organising maps [SOM]; Blind source separation
    • G06V10/7715—Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V20/00—Scenes; Scene-specific elements
    • G06V20/10—Terrestrial scenes
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V20/00—Scenes; Scene-specific elements
    • G06V20/50—Context or environment of the image
    • G06V20/56—Context or environment of the image exterior to a vehicle by using sensors mounted on the vehicle

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Remote Sensing (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Multimedia (AREA)
  • Data Mining & Analysis (AREA)
  • Evolutionary Computation (AREA)
  • Artificial Intelligence (AREA)
  • Software Systems (AREA)
  • Databases & Information Systems (AREA)
  • Automation & Control Theory (AREA)
  • General Health & Medical Sciences (AREA)
  • Medical Informatics (AREA)
  • Computing Systems (AREA)
  • Health & Medical Sciences (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Evolutionary Biology (AREA)
  • General Engineering & Computer Science (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Geometry (AREA)
  • Probability & Statistics with Applications (AREA)
  • Computer Graphics (AREA)
  • Traffic Control Systems (AREA)
  • Image Analysis (AREA)
  • Navigation (AREA)

Abstract

描述了一种由设备执行的方法。所述方法包含接收对应于第一行程的第一组对象数据。所述方法还包含接收对应于第二行程的第二组对象数据。所述方法进一步包含确定所述第一组对象数据与所述第二组对象数据之间的相似性度量。所述相似性度量指示至少一个对象的所述第一组对象数据与所述第二组对象数据之间的距离。所述方法另外包含基于所述相似性度量来聚类所述至少一个对象的所述第一组对象数据和所述第二组对象数据，以产生至少一个对象簇。所述方法还包含基于所述至少一个对象簇来产生地图数据。

Description

用于基于多行程数据来绘图的系统和方法
相关申请
本申请涉及并要求2017年1月4日提交的美国临时专利申请序列号62/442,404的“用于基于多行程数据来绘制对象的系统和方法(SYSTEMS AND METHODS FOR MAPPING ANOBJECT BASED ON MULTI-JOURNEY DATA)”的优先权。
技术领域
本公开一般涉及电子装置。更具体地，本公开涉及用于基于多行程数据来绘图的系统和方法。
背景技术
一些电子装置(例如，相机、视频摄像机、数码相机、蜂窝电话、智能电话、计算机、电视、汽车、个人相机、可穿戴相机、虚拟现实装置(例如，头戴式耳机)、增强现实装置(例如，头戴式耳机)、混合现实装置(例如，头戴式耳机)、运动相机、监视相机、安装式相机、连接式相机、机器人、无人机、医疗保健设备、机顶盒等)捕捉和/或利用图像。例如，智能电话可以捕捉和/或处理静止和/或视频图像。图像可以被处理、显示、存储和/或传输。例如，图像可以描绘包含风景和/或对象的场景。
在一些情况下，可能难以定位对象。例如，可能难以基于图像定位对象。从本讨论中可以看出，改善定位对象的系统和方法可能是有益的。
发明内容
描述了一种由设备执行的方法。所述方法包含接收对应于第一行程的第一组对象数据。所述方法还包含接收对应于第二行程的第二组对象数据。所述方法进一步包含确定第一组对象数据与第二组对象数据之间的相似性度量。相似性度量指示至少一个对象的第一组对象数据与第二组对象数据之间的距离。所述方法另外包含基于相似性度量来聚类至少一个对象的第一组对象数据和第二组对象数据，以产生至少一个对象簇。所述方法还包含基于至少一个对象簇来产生地图数据。对象数据可以包含对象位姿信息。产生地图数据可以包含基于至少一个对象簇来细化地图数据。
相似性度量可以基于对象类型。可以针对标志对象类型确定相似性度量。所述方法还可以包含针对车道标记对象类型确定第二相似性度量。
第一组对象数据和第二组对象数据可以包含标志数据。相似性度量可以指示来自不同行程的标志的点之间的距离。
第一组对象数据和第二组对象数据可以包含车道标记数据。相似性度量可以指示来自不同行程的车道标记数据之间或某一区域内的车道标记数据的点之间的最小距离中的至少一个。
聚类第一组对象数据和第二组对象数据可以包含执行分层聚类。执行分层聚类可以包含执行多个不同的聚类步骤。第一聚类步骤可以包含基于第一距离参数来聚类，并且第二聚类步骤可以包含基于第二距离参数来聚类。第二距离参数可以小于第一距离参数。
聚类第一组对象数据和第二组对象数据可以包含执行谱聚类。可以在一或多个关联块中的每一个内执行聚类。
所述方法可以包含基于至少一个对象簇来执行捆绑调整。所述方法可以包含将所产生的地图数据传输到至少一个车辆。
还描述了一种设备。所述设备包含存储器和耦合到存储器的处理器。处理器经配置以接收对应于第一行程的第一组对象数据。处理器还经配置以接收对应于第二行程的第二组对象数据。处理器进一步经配置以确定第一组对象数据与第二组对象数据之间的相似性度量。相似性度量指示至少一个对象的第一组对象数据与第二组对象数据之间的距离。处理器还经配置以基于相似性度量来聚类用于至少一个对象的第一组对象数据和第二组对象数据，以产生至少一个对象簇。处理器另外经配置以基于至少一个对象簇来产生地图数据。
还描述了一种存储计算机可执行代码的非暂时性有形计算机可读介质。所述计算机可读介质包含用于使电子装置接收对应于第一行程的第一组对象数据的代码。所述计算机可读介质还包含用于使电子装置接收对应于第二行程的第二组对象数据的代码。所述计算机可读介质进一步包含用于使电子装置确定第一组对象数据与第二组对象数据之间的相似性度量的代码。相似性度量指示至少一个对象的第一组对象数据与第二组对象数据之间的距离。所述计算机可读介质另外包含用于使电子装置基于相似性度量来聚类至少一个对象的第一组对象数据和第二组对象数据以产生至少一个对象簇的代码。所述计算机可读介质还包含用于使电子装置基于至少一个对象簇来产生地图数据的代码。
还描述了一种设备。所述设备包含用于接收对应于第一行程的第一组对象数据的装置。所述设备还包含用于接收对应于第二行程的第二组对象数据的装置。所述设备进一步包含用于确定第一组对象数据与第二组对象数据之间的相似性度量的装置。相似性度量指示至少一个对象的第一组对象数据与第二组对象数据之间的距离。所述设备另外包含用于基于相似性度量来聚类至少一个对象的第一组对象数据和第二组对象数据以产生至少一个对象簇的装置。所述设备还包含用于基于至少一个对象簇来产生地图数据的装置。
附图说明
图1是示出了可以实施基于多行程数据来绘图的系统和方法的设备的一个实例的框图；
图2是示出了用于基于多行程数据来绘图的方法的一种配置的流程图；
图3是示出了可以根据本文公开的系统和方法的一些配置执行的一或多个组件、元件和/或功能的一个实例的框图；
图4A是示出了使用谱聚类来跨多个行程关联三角测量标志的一个实例的图；
图4B是示出了多行程标志关联方法的一个实例的图；
图5是示出了单行程三角测量的实例的图；
图6是示出了来自多行程捆绑调整的重建的一个实例的图；
图7是示出了车道标记模拟设置的图；
图8是示出了X-Y平面中的一些样本条带的图；
图9是示出了用于基于多行程数据来绘图的方法的一种更具体配置的流程图；
图10是示出了用于基于多行程数据来绘图的方法的另一种更具体配置的流程图；和
图11示出了可以包含在经配置以实施本文公开的系统和方法的各种配置的设备内的某些组件。
具体实施方式
本文公开的系统和方法的一些配置可以涉及用于基于多行程数据来绘图的系统和方法。例如，一些配置可以涉及用于使用众包数据构建精确的三维(3D)地图的多行程关联和细化(例如，优化)。一些配置可以包含多行程标志关联和/或批量调整。
自主设备(例如，车辆、机器人等)可以依靠精确的3D地图来定位自己并获取局部语义信息(例如，速度限制)。一些方法使用昂贵的精确校准设备来构建这些地图，并且由于信息的动态性质而难以维护。例如，道路可能改变，道路标记和交通标志可能更新，和/或一些标牌(例如，道路施工标志)可能是临时的。本文公开的系统和方法的一些配置可以描述用于使用众包数据(例如，多个行程)来建立精确3D地图的一或多个规程(例如，线路(pipeline))。例如，一些配置可以采用对象位置数据(例如，三角测量器输出)和来自感知(例如，检测)的相关输入以及来自多个行程(例如，来自不同时间的同一车辆和/或来自不同车辆)的定位作为输入。输出可以是具有对象(例如，标志(例如，每个标志的6自由度位姿)和车道(例如，3D样条))的地图。一些配置可以包含增量地图更新和/或联合多行程处理。
在一些方法中，3D地图创建可以包含两个功能：6自由度(DOF)地标位姿的多行程关联和细化(例如，优化)。本文公开的系统和方法的一些配置可以包含现有地图的增量更新和/或使用所有当时可用的数据的冷启动或周期性地图创建。来自多个行程的数据(例如，使用多个汽车和/或多个时间(例如，天))可以被收集在存储库(例如，云中的中央存储库)中。数据可以包含图像(例如，相机)帧中的地标检测、相关图像特征和/或6DOF相机位姿。
多行程关联可以包含估计待生成的地图中的真实地标的数量和/或聚类所有数据。地标的聚类可能取决于地标的类型。一些方法可以包含创建距离度量和/或使用用于谱聚类和/或分层聚类的距离度量。
聚类交通标志的一个实例如下。例如，在交通标志的第一轮聚类中，可以使用语义信息将标志分成多个簇。例如，可以使用标志的形状(例如，矩形、菱形等)将标志分成多个簇。在第二轮聚类中，可以利用基于标志中心的距离度量来将来自第一轮簇的标志聚类成地理上邻近的簇。这可能正确地将不邻近其它标志的标志聚类。在某些情况下，地理上邻近的不同标志(例如，杆上的标志)可能会错误地落入一个簇中。在第三轮(例如，最后一轮)中，可以使用标志检测专用的图像特征来分开邻近的标志(例如，同一杆上的两个交叉街道标志)。
聚类交通车道的一个实例如下。对于交通车道，可以采用一或多个不同的度量和/或可以使用多轮聚类。例如，车道三角测量之间的距离度量可以包含若干个别度量：两个车道三角测量之间的纵向距离、横向距离和/或阈值距离内的点的数量等。为了创建长链的车道三角测量，可以使用多轮聚类。
一旦数据被聚类，可以细化(例如，优化)6DOF地标位姿以及相机参数(例如，内在函数和6DOF位姿)以最佳地解释来自存储库中的所有数据的所有图像水平检测。这种细化(例如，优化)可以产生更好的准确性和/或可以使地图在一次行程中对校准误差和相机位置的偏差具有弹性。
可以在本文公开的系统和方法的一些配置中实施一或多个多行程关联选项。例如，可以实施使用直到当前时间的所有数据的联合多行程关联。可以实施使用当前时间的地图估计的增量多行程关联。在一些方法中，可以在冷启动期间(例如，在没有先前数据的情况下)利用联合多行程关联。一旦现有的高清(HD)地图达到置信水平，就可以频繁使用增量多行程关联。可以执行偶尔的联合多行程关联以减少和/或消除任何增量多行程关联不准确性。
对于对地图的增量更新(例如，临时放置的车道关闭标志)，可以将地标三角测量连同相应的置信测量与现有地图进行比较，可以执行此地标周围的局部优化，和/或可以更新地图。为了确保由于许多增量更新而导致的误差不会累积，例如，可以使用此点可用的所有数据周期性地构建完整的地图。
现在参考附图描述各种配置，其中相似的附图标记可以指示功能相似的元件。如本文附图中一般描述和说明的系统和方法可以以各种不同的配置来布置和设计。因此，如附图所示，若干配置的以下更详细的描述并非旨在限制所要求的范围，而是仅仅表示系统和方法。
图1是可以实施基于多行程数据来绘图的系统和方法的设备102的一个实例的框图。例如，设备102可以经配置以基于来自多个行程(例如，多个车辆、多个旅程和/或多个时间等)的对象位置数据来定位环境(例如，三维(3D)地图)中的一或多个对象。设备102的实例包含电子装置、服务器、计算机(例如，台式计算机、膝上型计算机等)、网络装置、相机、视频摄像机、数码相机、蜂窝电话、智能电话、平板装置、车辆、汽车、个人相机、可穿戴相机、虚拟现实装置(例如，头戴式耳机)、增强现实装置(例如，头戴式耳机)、混合现实装置(例如，头戴式耳机)、运动相机、监视相机、安装式相机、连接式相机、机器人、飞机、无人机、无人驾驶飞行器(UAV)、游戏控制台、电器等。设备102可以包含一或多个组件或元件。一或多个组件或元件可以以硬件(例如，电路)、硬件和软件的组合(例如，具有指令的处理器)和/或硬件和固件的组合来实施。
在一些配置中，设备102可以是与一或多个车辆通信的网络装置(例如，服务器、云装置等)。在一些方法中，车辆中的一或多个可以是自主车辆(即自动驾驶车辆)和/或可以具有高级驾驶员辅助系统(ADAS)等。例如，设备102可以从一或多个车辆接收信息(例如，行程数据、对象检测数据、位姿数据、原始图像数据、对象数据等)。设备102可以确定绘图信息(例如，3D绘图数据、细化的对象位置数据等)，设备102可以将其提供到一或多个车辆。
另外地或可替代地，设备102可以是经配置以产生绘图信息的车辆。例如，设备102可以基于多个行程来确定绘图信息。在一些配置中，设备102可以是与一或多个其它车辆通信的车辆。例如，设备102可以从一或多个车辆接收信息(例如，行程数据、对象检测数据、位姿数据、原始图像数据、对象数据等)和/或可以将信息发送到一或多个车辆(例如，可以分享信息)。设备102可以产生和/或接收绘图信息，岁数绘图信息可以与一或多个其它车辆共享。
在一些配置中，设备102可以包含处理器112、存储器126、一或多个显示器132、一或多个图像传感器104、一或多个光学系统106和/或一或多个通信接口108。处理器112可以与存储器126、显示器132、图像传感器104、光学系统106和/或通信接口108耦合(例如，进行电子通信)。应注意。图1中所示的一或多个元件可以是任选的。特别地，在一些配置中，设备102可以不包含图1中所示的一或多个元件。例如，设备102可以包含或不包含图像传感器104和/或光学系统106。另外地或可替代地，设备102可以包含或不包含显示器132。另外地或可替代地，设备102可以包含或不包含通信接口108和/或天线110。
在一些配置中，设备102可以执行结合图1-11中的一或多个描述的功能、规程、方法、步骤等中的一或多个。另外地或可替代地，设备102可以包含结合图1-11中的一或多个描述的结构中的一或多个。
通信接口108可以使设备102与一或多个其它设备(例如，电子装置、车辆等)通信。例如，通信接口108可以提供用于有线和/或无线通信的接口。在一些配置中，通信接口108可以耦合到用于传输和/或接收射频(RF)信号的一或多个天线110。另外地或可替代地，通信接口108可以实现一或多种有线(例如，通用串行总线(USB)、以太网等)通信。
在一些配置中，可以实施和/或利用多个通信接口108。例如，一个通信接口可以是蜂窝(例如，3G、长期演进(LTE)、CDMA等)通信接口，另一个通信接口可以是以太网接口，另一个通信接口可以是通用串行总线(USB)接口，又一个通信接口可以是无线局域网(WLAN)接口(例如，电气与电子工程师协会(IEEE)802.11接口)。在一些配置中，通信接口可以向另一设备102或装置(例如，车辆、智能电话、相机、显示器、远程服务器等)发送信息(例如，图像信息、位姿信息、位置信息、对象检测信息、地图信息、对象数据等)和/或从另一设备或装置接收信息。
在一些配置中，设备102可以获取一或多个图像(例如，数字图像、图像帧、视频等)。例如，设备102可以包含图像传感器104和光学系统106(例如，镜头)，其将位于光学系统视场内的场景和/或对象的图像聚焦到图像传感器上。光学系统106可以耦合到处理器112和/或由其控制。
相机(例如，可见光谱相机或其它)可以包含至少一个图像传感器和至少一个光学系统。因此，在一些实施方案中，设备102可以是一或多个相机和/或可以包含一或多个相机。在一些配置中，图像传感器104可以捕捉一或多个图像(例如，图像帧、视频、静止图像、突发模式图像、立体图像等)。在一些配置中，图像传感器104可以捕捉一或多个图像。在一些实施方案中，设备102可以包含单个图像传感器104和/或单个光学系统106。例如，可以以特定帧速率(例如，每秒30帧(fps)、60fps、120fps等)使用具有特定分辨率(例如，视频图形阵列(VGA)分辨率，1280x 800像素等)的单个相机。在其它实施方案中，设备102可以包含多个光学系统106和/或多个图像传感器104。例如，在一些配置中，设备102可以包含两个或两个以上镜头。镜头可以具有相同的焦距或不同的焦距。
另外地或可替代地，设备102可以请求和/或接收来自另一设备或装置(例如，车辆相机、耦合到设备102的一或多个外部相机、网络服务器、交通相机等)的一或多个图像。在一些配置中，设备102可以经由通信接口请求和/或接收一或多个图像。例如，设备102可以包含或不包含相机(例如，图像传感器104和/或光学系统106)，并且可以从一或多个远程装置(例如，车辆)接收图像。
一或多个图像(例如，图像帧)可以包含一或多个场景和/或一或多个对象。在一些情况下，图像可以包含一或多个对象(例如，地标、道路标志、车道标记、交通灯、施工区锥体、障碍物、灯杆、道路标记、静止对象等)。
在一些实例中，图像传感器104和/或光学系统106可以机械地耦合到设备102或远程设备(例如，可以附接到，安装在和/或集成到车辆的车身、汽车的引擎盖、后视镜支架、侧视镜、保险杠等，和/或可以集成到智能电话或其它装置等中)。图像传感器104和/或光学系统106可以经由有线和/或无线链路链接到设备102。例如，图像传感器104和/或光学系统106可以硬连线到车辆中的控制机构(例如，处理器112)，或者由图像传感器104和/或光学系统106捕捉的信息可以无线地传输(例如，流传输或以其它方式无线地传送)到控制机构(例如，处理器112)。
存储器126可以存储指令和/或数据。处理器112可以访问存储器126(例如，从其读取和/或写入其)。可以由存储器126存储的指令和/或数据的实例可以包含多行程数据128、图像数据、对象检测数据、对象位置数据、2D对象位置数据(例如，像素数据)、特征点、关键点、角点、对象绘图数据、3D对象位置数据、相机位姿信息、道路法向矢量数据等、图像获取器指令、多行程数据获取器114指令、相似性度量确定器116指令、对象聚类器118指令、绘图器120指令和/或一或多个其它元件的指令等。
在一些配置中，设备102可以包含图像数据缓冲器(未示出)。图像数据缓冲器可以缓冲(例如，存储)来自图像传感器104和/或外部相机的图像数据。可以将缓冲的图像数据提供到处理器112。
在一些配置中，设备102可以包含一或多个显示器132。在一些方法中，由图像传感器104捕捉的图像(例如，场景和/或对象)可以呈现在显示器132上。在一些配置中，这些图像可以以相对高的帧速率快速连续地显示，使得在任何给定的时刻，位于光学系统106的视场内的对象可以呈现在显示器132上。由设备102获取的一或多个图像可以是一或多个视频帧和/或一或多个静止图像。例如，显示器132可以经配置以输出一或多个对象(例如，标志、车道标记、地标等)的视图。
显示器132可以集成到设备102中和/或可以耦合到设备102。例如，设备102可以是具有集成显示器132的虚拟现实头戴式耳机。在另一个实例中，设备102可以是耦合到具有显示器132的虚拟现实头戴式耳机的计算机。在又一个实例中，设备102可以是车辆。
在一些配置中，设备102可以在显示器132上呈现用户界面134。例如，用户界面134可以使用户与设备102交互。在一些配置中，显示器132可以是从物理触摸(例如，通过手指、触笔或其它工具)接收输入的触摸屏。另外地或可替代地，设备102可以包含另一输入接口或与其耦合。例如，设备102可以包含面向用户的相机并且可以检测用户姿态(例如，手部姿态、手臂姿态、眼睛跟踪、眼皮眨动等)。在另一个实例中，设备102可以耦合到鼠标并且可以检测鼠标点击。在一些配置中，可以在显示器132和/或用户界面134上呈现本文描述的一或多个图像。在一些配置中，用户界面134可以使用户指示偏好(例如，视图设置)和/或与视图互动。
在一些配置中，设备102(例如，处理器112)可以任选地耦合到一或多种装置，作为其一部分(例如，集成到其中)，包含其和/或实施其。例如，设备102可以在配备有一或多个相机的车辆中实施。
处理器112可以经配置以实施本文公开的一或多种方法。例如，处理器112可以经配置以产生对象绘图数据(例如，3D地图中的对象位置信息、对象位姿信息等)。
在一些配置中，处理器112可以包含和/或实施图像获取器。可以向图像获取器提供一或多个图像帧。例如，图像获取器可以从一或多个相机(例如，普通相机、广角相机、鱼眼相机、立体相机等)获取图像。例如，图像获取器可以从一或多个图像传感器104，从一或多个外部相机和/或从一或多个远程相机(例如，远程车辆相机)接收图像数据。可以从一或多个相机(例如，在不同位置)捕捉图像。如上所述，可以从包含在设备102中的图像传感器104捕捉图像，或者可以从一或多个远程相机捕捉图像。
在一些配置中，图像获取器可以请求和/或接收一或多个图像。例如，图像获取器可以经由通信接口108请求和/或接收来自远程装置(例如，外部相机、远程服务器、远程电子装置、远程车辆等)的一或多个图像。
处理器112可以包含和/或实施多行程数据获取器114。多行程数据获取器114可以获取(例如，请求和/或接收)对应于多个行程的数据(例如，多行程数据128)。例如，多行程数据获取器114可以获取对象数据、对象检测信息(例如，一或多个特征点、关键点、二维(2D)对象位置数据(例如，在图像平面中)等)、时间戳、对象类型(例如，标志、矩形标志、八角形标志、三角形标志、圆形标志等、车道标记、道路标记等))、对象位姿信息(例如，2D标志参数、2D车道参数、3D标志参数、3D车道参数、3D位置数据和/或定向数据等)、相机位姿信息(例如，6DOF相机位姿、相机位置数据和/或定向数据等)、三角测量输出、道路法向矢量、车辆位置数据、车辆定向数据、原始数据(例如，原始图像数据和/或原始对象检测数据等)等。对象数据(例如，对象位姿信息)可以包含对象位置数据(例如，3D对象位置、3D对象平移等)和/或对象定向数据(例如，3D对象旋转)。在一些配置中，对象数据(例如，对象位姿信息)可以包含相机位姿信息。多行程数据可以对应于多个车辆，对应于多个时间的单个车辆，对应于多个时间的多个车辆，对应于由一或多个车辆行进的多个行程等。例如，设备102可以接收对应于多个车辆和/或对应于多个行程的多行程数据128。在一些配置中，多行程数据128可以作为来自被组合成多行程数据128的个别行程的数据获取。例如，一或多个车辆可以在个别行程的行进中收集数据。来自每个个别行程的数据可以被提供到设备102。
在一些配置中，设备102(例如，多行程数据获取器114)可以经由通信接口108接收多行程数据128。另外地或可替代地，设备102(例如，多行程数据获取器114)可以基于执行一或多个对象位置函数(例如，三角测量、帧间对象关联、帧间标志关联、中点确定、角点调整、标志位姿调整、帧间车道标记关联、法向矢量估计、样条拟合、样条参数调整等)来获取、接收和/或产生多行程数据128。
例如，在一些配置中，处理器112可以包含和/或实施帧间关联器。帧间关联器可以关联在行程期间收集的帧(例如，在一系列帧中)之间的一或多个对象以产生二维对象位置数据。在一些配置中，帧间关联器可以基于一或多个对象像素(例如，一或多个图像中的对象的一或多个像素)、一或多个对象特征(例如，特征点、关键点、角点、中心点等)和/或一或多个像素相机位置(例如，对应于一或多个像素的相机位姿信息)来关联帧之间的一或多个对象。在一些配置中，帧间关联器可以执行一或多个道路标志的帧间关联。另外地或可替代地，帧间关联器可以执行一或多个车道标记的帧间关联。在一些方法中(例如，针对车道标记位姿估计)，处理器112可估计道路法向矢量。在一些配置中，可以将由帧间关联产生的对象位置数据(例如，标志位置数据、标志位姿数据、车道标记位置数据等)作为行程数据(例如，多行程数据128的部分)存储、发送和/或利用。
处理器112可以包含和/或实施相似性度量确定器116。相似性度量确定器116可以确定对应于两个或两个以上行程的对象数据(例如，3D对象位置数据和/或定向数据等)之间的一或多个相似性度量。相似性度量可以指示来自对象数据的对象之间的距离。在一些方法中，相似性度量可以基于对象类型。例如，可以针对不同的对象类型确定和/或利用不同的相似性度量。例如，可以针对标志对象类型(例如，道路标志)利用一种相似性度量，而可以针对车道标记对象类型(例如，车道条带)利用另一种相似性度量。
在一些配置中，相似性度量可以指示来自不同行程的标志对象的相应点(例如，中心点、角点等)之间的一或多个相应距离。另外地或可替代地，相似性度量可以指示车道标记和/或车道标记点(例如，来自不同的行程)之间的距离(例如，最小距离)。例如，相似性度量可以指示车道标记(例如，车道三角测量)之间的纵向距离、横向距离和/或某一区域内(例如，在阈值距离内，在径向区域内等)车道点的数量。在一些配置中，还可以使用核函数。例如，相似性度量可以基于核函数。可以控制距离阈值的形状和大小。可以关于本文中的一或多个附图提供更多细节。在一些配置中，相似性度量可以基于位姿信息(例如，3D几何信息)。例如，相似性度量计算可以不考虑其它类型的信息(例如，颜色、图像数据等)。
用于确定标志相似性度量的方法的一个实例如下。特别地，本方法示出了对象位置之间的相似性度量(例如，来自不同行程的两个标志、两个三角测量输出等)。应注意，在一些方法中，可以分别聚类不同类型(例如，形状)的标志和/或车道标记。
在一些配置中，相似性度量可以在某一取值范围内。例如，相似性度量可以具有范围[0,1]中的值。例如，0可以指示不同的对象和/或1可以指示完美匹配。在一些方法中，相同形状且来自不同行程的标志观察(例如，对象位置数据)可以表示为Os1和Os2。例如，Os1可以表示第一标志观察的一或多个点(例如，角点、特征点、中心点、3D坐标等)，并且Os2可以表示第二标志观察的一或多个点(例如，角点、特征点、中心点、3D坐标等)。等式(1)中给出了相似性度量的一个实例。
在等式(1)中，S是相似性度量(例如，Os1和Os2之间)，Os1是第一标志观察(例如，来自第一行程的对象位置)，Os2是第二标志观察(例如，来自第二行程的对象位置)，L()是核函数，d()是距离函数，dc是隐式控制聚类半径的距离参数(例如，较大的dc聚类较大地理区域中的标志或较小的dc聚类较小的地理区域中的标志)。应注意，dc可以是可调参数。例如，默认dc＝5米(m)，但是dc可以微调到其它值。在一些配置中，L(0)＝1并且L(∞)＝0，其中L()可以是非递增函数。
在一些配置中，距离函数d()可以如等式(2)中所示给出。
d(Os1,Os2)＝||corners(Os1)-corners(Os2)|| (2)
在等式(2)中，corners()是标志的角点的集合(例如，标志角点的3D位置)，并且||||表示范数。
在一些配置中，距离函数d()可以可替代地如等式(3)中所示给出。
d2(Os1,Os2)＝||t(Os1)-t(Os2)||2+C||R(Os1)-R(Os2)||2+D||size(Os1)-size(Os2)||2 (3)
在等式(3)中，t(例如，平移t)表示位置，R(例如，旋转矩阵R)表示标志的定向，C和D是确定各个因数的相对权重和/或重要性的常数(或系数)(例如，选定的和/或预定的系数)，并且size()是标志大小。应注意，可以针对C，针对D(其中D≥0)，和/或针d()利用其它选项(例如，公式)。应注意，如果标志三角测量是有噪声的，则d(Os1,Os2)＝||t(Os1)-t(Os2)||可能是相对稳健的测量。
在一些配置中，核函数L(u)可以如等式(4)中所示给出。
L(u)＝exp(-K*u2) (4)
在等式(4)中，u是核函数的输入值，K是可调比例因数，并且exp()表示指数函数。
在一些配置中，核函数L(u)可以可替代地如等式(5)中所示给出。
L(u)＝exp(-Ku) (5)
在一些方法中，默认K＝1。另外地或可替代地，核函数可以具有接近1的“瀑布(waterfall)”和/或L(u)可以在范围[0,1]内的指标。
用于确定车道相似性度量的方法的一个实例如下给出。特别地，本方法示出了对象位置(例如，车道观察等)之间的相似性度量。在一些配置中，车道标记观察可以表示为Ol1和Ol2。在一些方法中，车道标记观察可以表示为样条(例如，3D样条)。距离函数可以如等式(6)中所示给出。
d(Ol1,Ol2)＝min||xi-yj||2 (6)
在等式(6)中，xi和yj是车道标记(例如，条带)上的点的采样，其中最小值取自i和j。本方法可以允许车道标记(例如，条带)的链接。
另外地或可替代地，可以在Ol1上对点(例如，在3D世界坐标中)进行采样。在一些配置中，可以沿样条均匀地对点进行采样。点可以表示为x1、x2、……、xM。点y1、y2、……、yM可以是Ol2上最接近的对应点。可替代距离函数可以如等式(7)中所示给出。
相似性度量的另一个实例在等式(8)中给出。
如可以观察到，可以针对不同的对象类型(例如，车道标记、标志等)确定相似性度量S(O1,O2)。例如，相似性度量确定器116可以确定标志的第一相似性度量和车道标记的第二相似性度量。不同对象类型的相似性度量可以采用不同的观察、不同的距离函数、不同的核函数和/或不同的距离参数等。
在一些方法中，可以针对不同水平的分层聚类来确定和/或利用不同的相似性度量(例如，利用不同距离函数、不同核函数、不同距离参数和/或不同观察等的相似性度量)。例如，某一水平的标志聚类可以利用标志中心点来确定相似性度量，而另一水平的标志聚类可以利用标志角点。
在一些配置中，可以仅在关联块内和/或仅在簇内确定观察对的相似性度量。关联块可以是地图区域的区域(例如，地理区域)，在此区域内可以确定相似性度量和/或可以在其中执行聚类。例如，可以仅比较一个关联块内的观察。在一些配置中，可以使用重叠的关联块。
在一些配置中，对象数据的范围(例如，所有三角测量输出的范围)可以表示为[minE,maxE](例如，最小值东到最大值东)和[minN,maxN](例如，最小值北到最大值北)。对象数据的范围可以覆盖所有行程和/或可以是地图的最大范围。在一些方法中，位姿平移可以用于标志。对于车道标记(例如，车道条带)，可以使用沿样条的最小值和/或最大值。
地图(例如，地图区域)可以用关联块覆盖。关联块可以是正方形、矩形、圆形和/或不规则形状。例如，可以将每个块的块大小表示为assocTileSize x assocTileSize。块可以分别与东和北的strideE和strideN步级重叠。在一些配置中，可以为每个块维护标记。例如，可以为每个关联块维护dataPresentFlag。只能处理具有数据的块。可以根据本文公开的系统和方法利用其它铺块方法。随着更多数据的获取，可以递增地更新关联块和关联块占用。
在一些配置中，相似性度量确定器116可以形成相似性矩阵(例如，完全相似性矩阵)。例如，Sim可以表示所有对象数据(例如，特定地标类型的所有对象数据，例如三角测量输出)之间的相似性矩阵。相似性矩阵可以是对称的，其中各项在[0,1]的范围内。在一些方法中，可以将相似性矩阵(例如，Sim)初始化为单位矩阵或其它初始值。
在列表(1)中提供了用于形成每个关联块的相似性矩阵的伪代码的一个实例。
针对大小为assocTiles的每个块：
如果块.dataPresentFlag：
评价块中所有观察对的Sim(.,.)(例如，如果观察尚未进行比较)；
如果位姿平移(E,N)在块中，则标志属于块；
如果车道标记上的某一点具有块内的(E,N)，则车道标记属于块；
更新Sim(O1,O2)和Sim(O2,O1)二者，以确保Sim是对称的。
列表(1)
处理器112可以包含和/或实施对象聚类器118。对象聚类器118可以基于一或多个相似性度量来聚类来自对象数据(例如，多行程数据128)的对象以产生一或多个对象簇。例如，对象聚类器118可以将对象(例如，对应于相同或不同物理对象的对象数据)分组到一或多个簇中。簇可以包含对象数据(例如，对应于一或多个物理对象的一组观察)。例如，簇可以包含来自第一行程的第一观察(例如，对象位置数据、对象位姿等)和来自第二行程的第二观察(例如，对象位置数据、对象位姿等)。在一些配置中和/或情况下，单个簇可以对应于一或多个物理对象。对象聚类器118可以产生一或多个簇。在一些配置中，可以将一或多个簇提供到绘图器120。应注意，在一些配置中，对象聚类器118可以执行无监督聚类。在一些情况下，仅具有一个对象观察的簇(例如，单个簇)可以由聚类产生。
在一些配置中，对象聚类器118可以执行仅限于位于每个关联块内的对象的聚类。这可能有助于减少大面积的处理负担。
在一些配置中，对象聚类器118可以确定(例如，估计)多个对象(例如，实际对象、物理对象、地面实况对象等)。如上所述，Sim可以表示相似性矩阵(例如，所有对象之间的相似性矩阵)。在一些方法中，可以根据以下确定对象的数量。矩阵D可以是对角矩阵，其中对角线值是来自相似性矩阵的对应行的总和。(例如，D＝diag(rowsum(Sim)))。对象聚类器118可以确定基于Sim和D的矩阵W的特征矢量和特征值。例如，[特征矢量，特征值]＝eig(W)，其中W＝D-1/2Sim D-1/2。这可以提供对称公式。在一些配置中，特征值(W)＝特征值(随机游走转移矩阵D-1Sim)和特征矢量(W)＝D1/2特征矢量(D-1Sim)。
在一些方法中，多个簇KC(例如，多个对象)可以是大于特征值阈值的(例如，矩阵W的)多个特征值。例如，可以根据以下公式确定KC：KC＝特征值的数量>特征值阈值。在一些配置中，特征值阈值可以是默认值(例如，0.75)或某个其它值。例如，对于完美的簇，特征值1的重数即等于簇的数量。
用于确定簇的数量的可替代公式如下给出：L＝I–W。在本方法中，多个簇KC(例如，多个对象)可以是小于特征值阈值的(例如，矩阵L的)多个特征值。例如，可以根据以下公式确定KC：KC＝特征值的数量<特征值阈值。在一些配置中，特征值阈值可以是默认值(例如，0.3)或某个其它值。
在一些配置中，聚类可以包含执行多行程关联。例如，对象聚类器118可以关联来自多个行程的对象(例如，对象数据)。在一些方法中，U可以表示对应于KC主特征值的特征矢量的N x KC矩阵。多行程关联可以是来自U的行聚类的簇。在一些实施方案中，可以利用具有欧几里德度量的k均值聚类(例如，k均值函数)来完成行聚类。在其它实施方案中，可以使用可替代方法。可替代方法可以包含将第2列的符号带到KC。第1列可能是非负的，可能不会影响结果。每行的二进制代码可以给出簇索引。应注意，簇的数量可能不一定是KC。可以在一些方法中调整KC以提高性能。在一个反例中，考虑等式(9)中的矩阵。
此矩阵可以产生行{1,2}和{3,4}的簇，而不是{1}、{2,3}、{4}。
在利用聚类方法时，单个行程的邻近对象(例如，邻近的三角测量对象、邻近的物理对象等)可能会混淆，并且因此将其合并成单个对象。例如，假设在两个行程J1和J2中观察到两个邻近的标志，表示为Os1(J1)和Os2(J2)。设置S(Os1(Ji),Os2(Ji))＝0可能不足以将对应于Os1和Os2的观察分入不同的簇。在没有适当选择距离参数(例如，临界距离dc等)的情况下，可以合并这4个标志对象。这可能是一些聚类方法的限制。
为了缓解这个问题，可以对一或多种聚类算法进行一或多个增强。例如，对象聚类器118可以执行分层聚类和/或约束谱聚类。
关于分层聚类的更多细节如下给出。分层聚类包含多个聚类水平和/或步骤(例如，不同的聚类水平和/或步骤)。例如，分层聚类可以包含多阶段(例如，两阶段，三阶段等)聚类。分层聚类可以在聚类水平和/或步骤之间具有一或多个差异。例如，一或多个参数(例如，距离参数)可以在两个或两个以上水平之间不同，相似性度量(例如，利用不同距离函数、不同核函数、不同距离参数和/或不同观察的相似性度量等)可以在两个或两个以上水平之间不同，和/或初始簇可以在两个或两个以上水平之间不同。应注意，簇的数量可以在每个水平扩展或收缩(或者在一些情况下可以相等)。例如，可以执行“自上而下”和/或“自下而上”聚类。在一些方法中，可以在多个聚类水平上将标志分成越来越多的簇。在一些方法中，车道标记可以在多个聚类水平上合并成越来越少的簇。在一些配置中，可以撤消在前一水平执行的一些或所有聚类以进行下一水平。
在一些配置中，对象聚类器118可以执行分层聚类，其中距离参数可以对于两个或两个以上聚类水平和/或步骤而不同。例如，第一聚类步骤(例如，水平)可以包含聚类彼此邻近的所有标志(例如，同一杆上的多个标志)。然后，第二聚类步骤(例如，水平)可以包含聚类杆上的各个标志。例如，簇可以包含附接到同一杆的两个标志。可以执行进一步的聚类以产生簇，其中每个簇仅表示单个物理对象。例如，可以基于两个标志的簇来执行聚类以产生两个簇，其中每个簇仅对应于一个标志。
在没有适当选择距离参数(例如，临界距离dc等)的情况下，邻近和远处地标(例如，标志)的簇分离可能不同。在一个实例中，分层聚类可以包含执行两个水平的聚类。在第一水平的聚类(例如，水平1)中，可以使用距离参数的高值来聚类地标(例如，标志)，以辨别相对较远的标志。例如，默认距离参数可以是4m(例如，dc＝4m，并且特征值阈值＝0.3)。例如，这可以聚类来自不同交叉点的标志。在第二水平的聚类(例如，水平2)中，可以使用针对相似性度量的距离参数的较低值来聚类地标(例如，标志)，以辨别彼此邻近的标志。例如，默认距离参数可以是1m(例如，dc＝1m，并且特征值阈值＝0.3)。例如，这可以聚类给定交叉点中的不同标志。
除了分层聚类之外或作为其替代，在一些配置中，对象聚类器118可以执行约束谱聚类。谱聚类可以是一种无监督聚类。可以使用约束矩阵对某些观察可能属于不同簇(例如，来自相同轨迹的邻近标志)的观念进行编码。约束矩阵Q的一个实例在等式(10)中给出。
在等式(10)中，Q∈[0,-1](n×n)，其中n是观察的数量。当认为对象Oi和Oj属于不同簇时，可以强制执行Q(Oi,Oj)＝-1。
在一些配置中，对象聚类器118可以根据以下方法执行约束谱聚类。例如，本方法可以提供KC路划分的约束谱聚类的算法。Sim是相似性矩阵(例如，其可以另外地或可替代地被称为亲和矩阵)。β是需要满足的约束的数量的阈值。KC是簇的数量。在一些实施方案中，可从等式(11)的谱间隙确定KC。
在等式(11)中，是对应于待聚类的元素的图的拉普拉斯L的对称形式(例如，称为约束图)，v是/>的非平凡特征矢量，λ是对应的特征值，并且vol是约束图的所有节点的度数之和。列表(2)提供了约束谱聚类的算法的一个实例。所述算法可以采用相似性矩阵Sim、约束矩阵Q、β和KC作为输入。所述算法可以输出簇分配指标u*。
的最大特征值；
如果β≥λK-1vol，则
返回u*＝0；
结束
否则
求解等式(11)(例如，归一化的特征值系统)；
去除对应于非正特征值的特征矢量，并用归一化余项；
追踪/>其中V列是前一步骤中生成的可行特征矢量的子集；
返回
结束
列表(2)
处理器112可以包含和/或实施绘图器120。绘图器120可以基于一或多个对象簇来产生地图数据。例如，绘图器120可以产生和/或更新由对应于一或多个对象簇的一或多个对象填充的区域的三维(3D)图。例如，每个对象簇可以表示单个对象(例如，单个对象的多个行程的多个测量实例)。在一些配置中，绘图器120可以产生具有标志(例如，6DOF位姿)和车道(例如，3D样条)的地图。在一些配置中，处理器112(例如，相似性度量确定器116、对象聚类器118和/或绘图器120)可以执行增量地图更新。例如，在满足对象的置信度阈值的情况下，处理器112(例如，绘图器120)可以将新对象添加到地图。另外地或可替代地，在具有置信度阈值的对象数据中未指示对象的情况下，处理器112(例如，绘图器120)可以从地图去除对象。
关于可以由设备102以本文公开的系统和方法的一些配置执行的多行程绘图的另外的细节如下给出。例如，可以由处理器112(例如，多行程数据获取器114、相似性度量确定器116、对象聚类器118和/或绘图器120)执行以下操作、功能、方法等中的一或多个。
设备102可以使用从多个行程聚合的信息来执行标志和车道地标的3D重建。例如，设备102(例如，处理器112)可以利用标志和车道标记的行程间关联方案，并且可以利用算法来进行这些地标的3D重建。
在一些配置中，地标可以如下表示。标志Signi可以表示为3D标志角点的有序序列{Signij,1≤j≤Csign}，其中Csign是标志面的标志角点的数量。车道标记可以表示为具有多个(例如，2个、3个、4个、5个等)控制点的三次样条。车道标记Li可以由控制点序列{Lij,1≤j≤CL}给出，其中CL是控制点的数量。设备102(例如，处理器112)可以独立地针对标志和车道标记跨多个行程中执行关联。标志和车道标记的算法的实例(例如，多行程地标聚类)如下给出。
可以(例如，在设备102中，在存储器126中，在车辆中和/或在后端绘图服务器中等)存储来自个别行程的三角测量地标及其相关的定位和几何观察。多行程标志和/或车道标记聚类的目的可以是标识对应于相同真实基础地标对象(例如，物理对象)的若干个别行程(来自不同车辆，跨不同时间等)的三角测量输出群组。可以利用聚类来解决此问题。
在一些配置中，可以利用谱聚类，因为谱聚类可以能够估计作为来自多个行程的三角测量输出的基础的簇的数量(例如，真实地标的数量)。若已知任何两个地标，则可以限定地标之间的相似性度量。在一些方法中，相似性度量可以采用[0,1]范围内的值，其中值1指示完美匹配，而0可以暗示不同对象。谱聚类可以依赖于相似性矩阵(或者关联的概率转移矩阵或例如拉普拉斯矩阵)的特征值和特征矢量来形成簇。
在无噪声场景中，如果存在恰好P个不同的地标，则相似性矩阵可以表示为块对角矩阵，其中P个对角块中的每一个是全一矩阵。例如，矩阵可以具有重复P次的特征值1，并且所有其它特征值都是零。在现实世界场景种，尽管存在非理想性，但是谱间隙可能是明显的，这可以允许估计簇的数量。一旦标识出簇的数量，拉普拉斯特征矢量矩阵的行的k均值聚类可以产生最终簇。用于交通标志和车道标记的特定相似性度量如下描述。
在一些配置中，可以执行跨多个行程的标志聚类。在一些方法中，视觉特征(例如，图像分块)可能不可用和/或可能不被用于跨来自多个行程的不同三角测量标志执行数据关联。例如，在一些方法中，可以使用关于三角测量标志的几何信息(例如，3D几何信息)(并且例如，不是视觉信息)。利用几何信息可以为一些公路和郊区道路提供足够的精度。在其它方法中，视觉特征可以用于标志聚类。
在多行程设置中，上标可以用于表示与地标关联的第(k)个行程。为了经由谱聚类(在一些配置中和/或在一或多个分层水平)执行数据关联，可以使用标志面的中心，其可以被表示为/>在一些方法中，标志中心可能对聚类过程的三角测量噪声不太敏感。两个标志三角测量/>和/>之间的距离可能是标志中心之间的L2距离：为了将距离度量绘制为[0；1]中的相似性值，可以在一些方法中利用高斯核来调节距离度量，如等式(12)中所示。
在等式(12)中，dc是可调距离参数(例如，临界距离参数)，其隐式控制聚类半径。例如，较大的dc将聚类较大的地理区域中的标志三角测量，而较小的dc将聚类较小的地理区域中的标志三角测量。可以通过初始化来编码来自单个行程的三角测量不同的先验。应注意，这可能是一种软约束，并且可能不会强制来自同一行程的标志不被聚类。
一旦计算出相似性矩阵，就可以执行谱聚类以将标志三角测量聚类为不同簇。例如，设置dc＝4m可以实现聚类来自不同标志杆的标志，但是所述聚类算法可能难以分开给定标志杆中的标志。使用较小的距离参数(例如，dc＝1m)最初可以创建许多簇，其即使在聚类之后也产生几个重复的标志。为了解决本问题，可以执行分层聚类。例如，设备102(例如，处理器112、对象聚类器118等)可以以自上而下的方式执行两阶段分层聚类。例如，聚类的第一阶段可以用dc＝4m来执行。在聚类的第二阶段中，可以使用dc＝1m进一步聚类来自第一阶段的簇的每个标志。本方法可以提供改进的聚类和数据关联。
在多行程框架(例如，多行程众包框架)中，一些单行程重建对象可能具有高误差，这可能形成聚类方法的异常点。为了过滤异常值，可以丢弃具有少于阈值数量的标志的所有簇。在一个保守实例中，可以仅丢弃仅具有一个标志对象的标志簇(例如，单个簇)。可以量化本方案的数据丢失。
在一些方法中，对于每个簇，可以限定通过对给定簇中的所有标志的相应标志角点进行平均而获取的簇头标志Signi Si。此后，Signi可以用作唯一描述标志的代表标志。可以在捆绑调整规程的初始化步骤中使用Signi标志角点。
设备102可以跨多个行程执行车道标记聚类。在一些方法中，车道标记Lanei可以由样条控制点Lanei,j限定，并且可以从每个行程获取。可以聚合从不同行程获取的车道标记信息。在一些配置中，可以表示来自行程k的三角测量车道标记。
若已知来自多个行程的三角测量车道标记(例如，其可以由样条参数化)，则设备102(例如，处理器112)可以确定哪些车道标记来自相同的真实世界车道标记(例如，物理车道标记)。为了确定哪些车道标记对应于相同的真实世界车道标记，设备102(例如，相似性度量确定器116)可以确定一对样条的相似性度量，并通过计算每对样条(例如，关联块内的每对样条)的相似性度量来创建相似性矩阵。可以对相似性矩阵执行谱聚类。在一些配置中，设备102可以将相似性度量和层级聚类用于车道标记。
车道标记的相似性度量的一个实例如下给出。在三角测量输出中，样条可以由取决于长度的自适应数量的控制点来限定。为了计算相似性度量，设备102(例如，处理器112、相似性度量确定器116等)可以更精细地对每个样条进行采样。例如，可以对每个样条进行采样以具有特定密度的样本(例如，具有与以米为单位的近似样条长度一样多的样本点)。对于两个样条Lanei和Lanej(其中样本点由集合A＝{ai}和B＝{bj}给出)，设备102(例如，相似性度量确定器116)可以得出每对样本点ai和bj之间的距离L2：d(ai,bj)。度量可以指示样条彼此有多接近。利用阈值r，可以计算等式(13)。
在等式(13)中，N是两个样条在彼此距离r内的样本点对的数量(例如，归一化数量)。这可以指示样条彼此并排的部分。这些度量中的每一个都可以独立地使用。在一些配置中，组合两个度量的相似性度量可以被计算为在一些方法中，还可以使用高斯核，如等式(14)中所示。
在等式(14)中，d可以是可调参数。
在一些配置中，设备102(例如，处理器112、对象聚类器118)可以执行分层聚类。一旦计算出相似性矩阵，设备(例如，对象聚类器118)可以计算相似性矩阵的特征值，可以确定簇的数量，和/或可以通过对特征矢量进行分箱(bin)来获取簇。分层聚类可能是有益的。例如，代替在单个步骤中创建多个簇，分层聚类可以包含多个阶段(例如，水平、步骤等)。在一些配置中，分层聚类可以包含对前一轮聚类的输出簇执行后一轮聚类。例如，可以执行两个、三个或更多个聚类阶段。与仅执行一轮聚类相比，分层聚类可以提供更好的误差性能。在一些方法中，分层聚类可以减少每个聚类阶段的簇的数量。
聚类可以确定哪些三角测量车道标记对象聚合在一起。通过从这些三角测量车道标记的控制点创建点云并将样条拟合到点云，可以获取车道标记对象Lanei。车道标记对象Lanei可以用于地标重建。Lanei可以用作给定簇的所有车道标记对象的簇头车道标记对象。
在一些配置中，设备102可以执行地标重建。可以使用被称为捆绑调整(BA)的规程来重建地标(例如，标志和车道标记地标)，所述规程细化了地标的3D位置和相机位姿。在一些配置中，处理器112(例如，相似性度量确定器116、对象聚类器118和/或绘图器120)可以执行捆绑调整。
在一些方法中，三角测量可以包含固定相机6DOF位姿和估计对象位置信息(例如，标志6DOF位姿、大小、车道标记样条等)。捆绑调整可以包含联合估计相机和对象位姿(例如，标志6DOF位姿和/或大小等)。可以利用三角测量和捆绑调整来避免重投影误差的不良局部最小值。所产生的地图可以提供6DOF标志位姿、大小、标志类型、内容等。
关于捆绑调整(例如，BA)和成本函数的更多细节如下给出。具体地，可以根据以下的一或多个方面来实施本文公开的具有多行程设置的系统和方法的一些配置。初始化可以将簇中的地标(例如，标志)位姿的“均值”用于基线地图。非线性捆绑调整可以包含两个约束：重投影误差和参考成本。重投影误差可以是估计的3D对象的投影(例如，标志角点和车道标记)到图像平面观察到的检测(例如，来自感知和/或对象检测)之间的误差。可以在每个行程中将常见偏差变量(6DOF)添加到相机位姿变量。每个行程都可能存在一个此变量。参考成本可以是相机位姿变量与来自自我定位系统的相机位姿观察之间的误差。
BA原语可以是非线性优化，其联合细化(例如，优化)相机位姿pn和地标位置。BA可以使用相机重投影误差作为细化(例如，优化)的误差度量。每个标志Signi可以具有一组关联的图像观察。对于所有帧fn(其中位姿pn具有标志Signi的观察(由sn,i表示))，标志再投影成本可以被限定为其中/>是标志角点到位姿pn的图像坐标的投影。可以将误差计算为图像坐标中的标志角点之间的L2距离。每个车道标记Lanei还可以具有一组关联的图像观察。对于所有帧fn(其中位姿pn含有车道标记Lanei的观察)，车道标记重投影成本可以被限定为/>其中Lanei是投影时最接近观察ln,i的样条点，并且/>是位姿pn的到此样条点的图像坐标的投影。可以将误差计算为图像坐标中的标志角点之间的L2距离。BA优化可以根据等式(15)执行细化(例如，优化)。
求解方程(15)可以产生细化的相机位姿、标志角点和车道标记参数(样条参数)。问题可能是高度非凸的问题。在一些配置中，可以使用迭代列文伯格-马夸尔特算法来得出局部最小值。重建的保真度可能对相机位姿和地标参数的初始化敏感。为了初始化和的标志性参数值Signi和Lanei，可以使用来自聚类的簇头。为了初始化相机位姿参数pn值，可以聚合来自多个行程的信息以补偿单行程相机位姿中的观察到的偏差。可以通过平均跨多个行程的相机位姿和地标重建来推断偏差。可以使用偏差补偿相机位姿来初始化pn值。为了使上述优化问题对异常观察不太敏感，可以将图基(Tukey)加权函数应用于上述成本函数以使优化原语具有鲁棒性。
应注意，可以组合和/或分隔电子装置的一或多个元件或组件。例如，可以组合多行程数据获取器114、相似性度量确定器116、对象聚类器118和/或绘图器120。另外地或可替代地，多行程数据获取器114、相似性度量确定器116、对象聚类器118和/或绘图器120可以被分为执行其操作的子集的元件或组件。
应注意，结合处理器112描述的一或多个元件或组件可以是任选的。例如，在一些配置中，设备102可以包含或不包含和/或可以实施或不实施多行程数据获取器114、相似性度量确定器116、对象聚类器118和/或绘图器120。在一些实施方案中，多行程数据获取器114、相似性度量确定器116、对象聚类器118和/或绘图器120可以被实施为独立电路(例如，并非作为处理器112的一部分)。在一些配置中，一组设备(例如，无人机群，一组车辆等)可以协作。例如，一组设备102可以将行程数据提供(例如，发送、传输等)到可以绘制一或多个对象的另一设备(例如，服务器、车辆等)。
图2是示出了用于基于多行程数据来绘图的方法200的一种配置的流程图。方法200可以由结合图1描述的设备102执行。设备102可以确定202对应于多个行程的对象数据之间的相似性度量。这可以如结合图1所描述的那样完成。例如，设备102可以从多个行程的对象数据确定指示对象(例如，对象角点、对象中心、最近点等)之间的距离的相似性度量。
设备102可以基于相似性度量从对象数据聚类204对象以产生一或多个对象簇。这可以如结合图1所描述的那样完成。例如，设备102可以对多个行程之间的对象进行分组。应注意，在一些情况下，来自多个行程的“对象”可以对应于相同或不同的物理对象。在一些配置中，聚类可以包含分层聚类和/或约束谱聚类。
设备102可以基于一或多个对象簇来产生206地图数据。这可以如结合图1所描述的那样完成。例如，设备102可以产生包含与一或多个对象簇相对应的一或多个对象的地图。
图3是示出了可以根据本文公开的系统和方法的一些配置执行的一或多个组件、元件和/或功能的一个实例的框图。特别地，图3示出了单行程调整器338、行程间标志关联器342、标志位姿初始化器344、行程间车道标记关联器、车道标记位姿初始化器352和多行程调整器346。在一些配置中，结合图3描述的组件、元件和/或功能中的一或多个可以在结合图1描述的设备102中实施。
设备102可以获取(例如，接收)行程数据336(例如，单行程和/或多行程数据)。例如，数据336可以包含来自一或多个行程的一或多个车辆的原始数据(例如，图像、检测输出等)和/或三角测量输出。在一些配置中，可以将行程数据336提供到单行程调整器338。单行程调整器338可以执行单行程捆绑调整。例如，单行程调整器338可以在单个行程内(例如，在一或多个单个行程中的每一个内)细化相机位姿和地标位置。在一些配置中，可以如结合图1所描述的那样执行捆绑调整。应注意，单行程捆绑调整可以是任选的(例如，可以在某些配置中和/或针对一些数据实施和/或执行或不实施和/或执行)。
可以将行程数据340(例如，原始数据、三角测量输出、对象位置数据、对象位姿数据、单行程细化数据(例如，捆绑调整输出)、关联、其子集等)提供到行程间标志关联器342、行程间车道标记关联器350和/或多行程调整器346。行程间标志关联器342可以关联行程之间的标志(例如，标志观察、标志数据、标志位姿等)。这可以如结合图1所描述的那样完成。例如，行程间标志关联器342可以确定对应于多个行程的标志数据之间的一或多个相似性度量。行程间标志关联器342还可以基于相似性度量来聚类标志数据(例如，标志观察、标志位姿等)。
标志位姿初始化器344可以执行标志位姿初始化。这可以如结合图1所描述的那样完成。例如，标志位姿初始化器344可以利用来自标志聚类的簇头。可以将标志位姿初始化器输出提供到多行程调整器346。
行程间车道标记关联器350可以关联行程之间的车道标记(例如，车道标记观察、车道标记数据、样条等)。这可以如结合图1所描述的那样完成。例如，行程间车道标记关联器350可以确定对应于多个行程的车道标记数据之间的一或多个相似性度量。行程间车道标记关联器350还可以基于相似性度量来聚类车道标记数据(例如，车道标记观察、车道标记位姿等)。可以将行程间车道标记关联器350的输出提供到车道标记位姿初始化器352。
车道标记位姿初始化器352可以执行车道标记位姿初始化。这可以如结合图1所描述的那样完成。例如，车道标记位姿初始化器352可以利用来自车道标记聚类的簇头。可以将车道标记位姿初始化器352输出提供到多行程调整器346。
多行程调整器346可以基于标志位姿初始化数据、车道标记位姿初始化数据和/或原始数据来执行多行程捆绑调整。这可以如结合图1所描述的那样完成。例如，多行程调整器346可以细化相机位姿和/或地标(例如，标志和车道标记)位置。多行程调整器346可以产生地图348。例如，地图348可以包含3D地图中的一或多个地标(例如，标志和/或车道标记)的一或多个位置。在一些配置中，地图348可以指示相对于3D世界坐标的地标位置。在一些配置中，可以将地图348和/或反馈(例如，校正反馈)提供到行程间标志关联器342和/或行程间车道标记关联器350。
图4A是示出了使用谱聚类来跨多个行程关联三角测量标志的一个实例的图。例如，图4A示出了来自两个行程J1和J2的两个标志(第一标志和第二标志)的观察。特别地，图4A示出了来自第一行程的第一标志的第一观察460a(例如，Os1(J1))和来自第二行程的第一标志的第二观察460b(例如，Os2(J2))。图4A还示出了来自第一行程的第二标志的第一观察462a(例如，Os3(J1))和来自第二行程的第二标志的第二观察462b(例如，Os4(J2))。在本实例中，本文公开的系统和方法的一些配置的目的可以是将4个观察Os1、Os2、Os3和Os4分成两个簇。两个簇可以对应于两个标志(例如，两个实际标志、两个物理标志等)。
图4B是示出了多行程标志关联方法的一个实例的图。例如，设备102可以执行如结合图4B所描述的谱聚类，以便聚类结合图4A描述的标志。在一些方法中，可以分别聚类不同的形状。在其它方法中，可以利用其它分箱标准。在一些配置中，设备102可以计算三角测量输出的距离矩阵，用dc归一化各项，和/或绘制为相似性(例如，采用[0,1]中的值)。簇可能是强连通分量。标志的数量(例如，“numSigns”)可以是接近零的拉普拉斯特征值的数量。如结合图1所描述，设备102可以使用k均值方法或标志方法(例如，列标志)来聚类相应的特征矢量矩阵的行。
特别地，图4B示出了相似性矩阵的一个实例454。实例454是列458上行456中示出的图。在实例454中，高值(例如，1)以黑色示出，而低值(例如，0)以白色示出。谱聚类可以利用相似性矩阵中的块对角状结构来推断唯一标志的数量。可以基于本提示来执行聚类。
在一些配置中，设备102可以执行分层聚类(例如，多阶段聚类、两阶段聚类等)。例如，为了解决不同分开量的标志，可以执行两个水平的聚类。在第一水平，设备102可以使用较高临界距离值(例如，dc＝4m)来聚类标志，以辨别以相对大的距离分开的标志(例如，来自不同交叉点的标志)。在第二水平，设备102可以使用相似性度量的较低临界距离值(例如，dc＝1m)来聚类标志，以辨别相对邻近的标志(例如，在给定交叉点中)。
图5是示出了单行程三角测量564a-c的实例的图。特别地，图5示出了三个单行程三角测量的相机位姿566和标志位姿568的实例。如本文描述，车辆可以收集单行程数据(例如，单行程三角测量564a-c)。另外地或可替代地，多个车辆可以收集单行程数据(例如，单行程三角测量564a-c)。在一些方法中，可以将单行程三角测量564a-c提供到设备102。
图6是示出了来自多行程捆绑调整的重建670(例如，地图)的一个实例的图。特别地，图6示出了可以基于本文公开的系统和方法的一些配置(例如，多行程线路)重建的相机位姿672和标志位姿674的实例。例如，结合图1描述的设备102可以利用来自图5的单行程三角测量564a-c来产生图6中所示的重建670。可以通过确定标志观察之间的相似性度量并通过根据本文公开的系统和方法的一些配置聚类标志观察来产生重建670(例如，地图)。表(1)示出了通过平均初始化的重建结果的一个实例。
标志ID t1 t2 t3 rotX rotY rotZ w h
1 29.9 1.4 2.3 91.7 -6.4 106.5 0.8 0.8
2 40.0 1.5 2.5 95.3 -11.7 110.8 1.0 0.6
3 69.3 5.9 1.5 82.4 -7.8 92.9 1.3 1.6
4 49.9 1.5 2.2 92.5 -5.6 91.8 0.8 0.7
5 60.0 1.5 2.1 91.7 -4.8 90.8 0.7 0.6
表(1)
表(2)示出了捆绑调整之后的重建结果的一个实例。
标志ID t1 t2 t3 rotX rotY rotZ w h
1 29.7 1.1 2.6 90.6 -5.8 99.7 0.8 0.8
2 39.9 1.3 2.3 95.2 -6.1 104.4 0.7 0.6
3 69.3 6.1 1.3 95.3 -4.4 91.1 1.2 1.3
4 50.1 1.8 1.9 96.0 -6.0 91.9 0.9 0.7
5 60.2 1.8 1.9 93.3 -5.0 90.5 0.7 0.7
表(2)
图7是示出了车道标记模拟设置的图。特别地，图7示出了车道标记A 780a和车道标记B 780b。Y轴(例如，图7中的纵轴)782以米为单位示出，X轴(例如，图7中的横轴)784以米为单位示出。例如，两个模拟“车道标记”可以在Z中从左到右以恒定梯度形成。在此设置中，车道宽度＝4m，内半径＝100m，条带长度＝30m。每个车道标记200个条带。沿条带进行1m采样以进行计算。还添加了三角测量噪声(例如，X、Y、Z方向上的IID高斯、零均值、1m标准偏差噪声)。
图8是示出了X-Y平面中的一些样本条带的图。特别地，图8示出了来自使用结合图7描述的车道标记780a-b的模拟的一些车道标记样本886。Y轴(例如，图8中的纵轴)888以米为单位示出，X轴(例如，在图8中的横轴)890以米为单位示出。使用不同的符号来示出样本组。在一些方法中，结合图1描述的设备102可以根据以下的一或多个方面执行车道标记的谱聚类。可以计算条带之间的成对“距离”(例如，相似性度量)。对于距离度量，基线可以是使用两个条带之间的最小距离(mindist)(例如，找到条带在何处彼此最接近并使用此距离)。可以精细地对每个条带进行采样。对于一对条带，可以对阈值内的成对点的数量进行计数(例如，count)。当条带在全部或部分路径上彼此并排或叠置时，这是很高的。在一些方法中，可以将上述两者组合，有可能使用核函数。例如，count*exp(-Kmindist2)。可以将距离绘制为[0,1]中的相似性得分。在基线方法中，如果mindist<2m，则相似性度量可以是1，否则为0(例如，指标L(.))。在一些方法中，可以执行关于标志聚类的谱聚类。
在一些方法中，还可以执行针对车道标记的分层聚类。例如，设备102可以在两个或三个阶段中聚类。例如，以200个条带开始，设备102可以确定75个簇。设备102可以进一步将簇减少到25，然后减少到12。“点云”上的第二轮和/或第三轮聚类可以由前一轮给出。可替代地，在每个聚类阶段之后，设备102可以将新条带拟合到簇，并且下一聚类阶段可以基于新样条工作。可以将距离绘制为[0,1]中的相似性得分。在基线方法中，如果mindist<2m，则相似性度量为1，否则为0(指标L(.))。可以关于标志聚类应用谱聚类。例如，簇的数量可以在每个水平增加或减少。
图9是示出了用于基于多行程数据来绘图的方法900的一种更具体配置的流程图。方法900可以由结合图1描述的设备102执行。设备102可以获取902多行程标志数据。这可以如结合图1和3中的一或多个所描述的那样完成。例如，设备102可以捕捉、确定和/或可以接收多行程标志数据。
设备102可以确定904对应于多个行程的标志数据之间的一或多个相似性度量。这可以如结合图1-3中的一或多个所描述的那样完成。例如，设备102可以从多个行程的标志数据确定指示标志(例如，标志角点、标志中心等)之间的距离的相似性度量。在一些方法中，可以针对关联块内的标志观察对确定904相似性度量。
设备102可以聚类906标志数据(例如，来自多行程标志数据的一或多个标志)以产生一或多个对象簇。这可以如结合图1-4B和6中的一或多个所描述的那样完成。聚类906标志数据(例如，标志)可以基于一或多个相似性度量。在一些配置中，聚类可以包含分层聚类和/或约束谱聚类。在一些方法中，可以基于标志形状(例如，指示标志是矩形、菱形、三角形、八边形等的语义数据)来聚类标志数据(例如，标志)。在一些方法中，可以执行分层聚类，其中针对每个阶段或水平的聚类改变距离参数(例如，临界距离)。例如，可以利用第一距离参数(例如，较大的距离参数)确定904相似性度量，并且可以以第一水平执行聚类906。然后，可以利用第二距离参数(例如，较小的距离参数)确定904相似性度量，并且可以以第二水平执行聚类906等。在一些方法中，可以利用图像特征来执行某一水平的聚类906。在一些方法中，可以另外地或可替代地执行谱聚类。
设备102可以细化908标志数据以产生地图数据。这可以如结合图1和3中的一或多个所描述的那样完成。例如，设备102可以基于标志簇执行多行程捆绑调整以产生地图数据。另外地或可替代地，设备102可以细化地图数据。例如，设备102可以执行捆绑调整以细化地图数据(例如，对应于地图的对象位姿信息和/或相机位姿信息)和/或可以基于对象(例如，标志)数据和/或后续的对象数据来更新地图。
图10是示出了用于基于多行程数据来绘图的方法1000的另一种更具体配置的流程图。方法1000可以由结合图1描述的设备102执行。设备102可以获取1002多行程车道标记数据。这可以如结合图1和3中的一或多个所描述的那样完成。例如，设备102可以捕捉、确定和/或可以接收多行程车道标记数据。
设备102可以确定1004对应于多个行程的车道标记数据之间的一或多个相似性度量。这可以如结合图1-3中的一或多个所描述的那样完成。例如，设备102可以从多个行程的车道标记数据确定指示车道标记之间的距离的相似性度量。在一些方法中，可以针对关联块内的车道标记观察确定1004相似性度量。
设备102可以聚类1006车道标记数据(例如，来自多行程车道标记数据的一或多个车道标记)以产生一或多个对象簇。这可以如结合图1-3和8中的一或多个所描述的那样完成。聚类1006车道标记数据(例如，车道标记)可以基于一或多个相似性度量。在一些配置中，聚类可以包含分层聚类和/或约束谱聚类。在一些方法中，可以执行分层聚类，其中针对每个阶段或水平的聚类改变相似性度量。在一些方法中，可以另外地或可替代地执行谱聚类。
设备102可以细化1008车道标记数据以产生地图数据。这可以如结合图1和3中的一或多个所描述的那样完成。例如，设备102可以基于车道标记簇执行多行程捆绑调整以产生地图数据。另外地或可替代地，设备102可以细化地图数据。例如，设备102可以执行捆绑调整以细化地图数据(例如，对应于地图的对象位姿信息和/或相机位姿信息)和/或可以基于对象(例如，车道标记)数据和/或后续的对象数据来更新地图。
图11示出了可以包含在经配置以实施本文公开的系统和方法的各种配置的设备1102内的某些组件。设备1102的实例可以包含服务器、相机、视频摄像机、数码相机、蜂窝电话、智能电话、计算机(例如，台式计算机、膝上型计算机等)、平板装置、媒体播放器、电视、车辆、汽车、个人相机、可穿戴相机、虚拟现实装置(例如，头戴式耳机)、增强现实装置(例如，头戴式耳机)、混合现实装置(例如，头戴式耳机)、运动相机、监视相机、安装式相机、连接式相机、机器人、飞机、无人机、无人驾驶飞行器(UAV)、医疗保健设备、游戏控制台、个人数字助理(PDA)、机顶盒等。设备1102可以根据本文描述的一或多个设备来实施。
设备1102包含处理器1121。处理器1121可以是通用单芯片或多芯片微处理器(例如，ARM)、专用微处理器(例如，数字信号处理器(DSP))、微控制器、可编程门阵列等。处理器1121可以被称为中央处理单元(CPU)。尽管在设备1102中仅示出了单个处理器1121，但是在一种可替代配置中，可以实施处理器的组合(例如，ARM和DSP)。
设备1102还包含存储器1101。存储器1101可以是能够存储电子信息的任何电子组件。存储器1101可以被体现为随机存取存储器(RAM)、只读存储器(ROM)、磁盘存储介质、光存储介质、RAM中的闪存装置、包含有处理器的板上存储器、EPROM存储器、EEPROM存储器、寄存器等(包含其组合)。
数据1105a和指令1103a可以存储在存储器1101中。指令1103a可以由处理器1121执行以实施本文描述的方法、规程、步骤和/或功能中的一或多个。执行指令1103a可以涉及存储在存储器1101中的数据1105a的使用。当处理器1121执行指令1103时，指令1103b的各个部分可以被加载到处理器1121上，和/或各个数据1105b可以被加载到处理器1121上。
设备1102还可以包含发送器1111和/或接收器1113，以允许向设备1102发送信号和从其接收信号。发送器1111和接收器1113可以被统称为收发器1115。一或多个天线1109a-b可以电耦合到收发器1115。设备1102还可以包含(未示出)多个发送器、多个接收器、多个收发器和/或另外的天线。
设备1102可以包含数字信号处理器(DSP)1117。设备1102还可以包含通信接口1119。通信接口1119可以允许和/或实现一或多种输入和/或输出。例如，通信接口1119可以包含用于将其它设备链接到设备1102的一或多个端口和/或通信装置。在一些配置中，通信接口1119可以包含发送器1111、接收器1113或两者(例如，收发器1115)。另外地或可替代地，通信接口1119可以包含一或多个其它接口(例如，触摸屏、小键盘、键盘、麦克风、相机等)。例如，通信接口1119可以使用户能够与设备1102交互。
设备1102的各个组件可以通过一或多个总线耦合在一起，总线可以包含电源总线、控制信号总线、状态信号总线、数据总线等。为了清楚起见，各种总线是在图11中被示出为总线系统1107。
术语“确定”涵盖各种动作，因此，“确定”可以包含计算(calculating/computing)、处理、推导、核查、查找(例如，在表格、数据库或其它数据结构中查找)、查明等等。而且，“确定”可以包含接收(例如，接收信息)、访问(例如，访问存储器中的数据)等。而且，“确定”可以包含解决、选择(selecting/choosing)、建立等。
除非另有明确说明，否则短语“基于”并不意味着“仅基于”。换句话说，短语“基于”描述了“仅基于”和“至少基于”。
术语“处理器”应广义地解释为涵盖通用处理器、中央处理单元(CPU)、微处理器、数字信号处理器(DSP)、控制器、微控制器、状态机等。在某些情况下，“处理器”可以是指专用集成电路(ASIC)、可编程逻辑装置(PLD)、现场可编程门阵列(FPGA)等。术语“处理器”可以是指处理装置的组合，例如DSP和微处理器的组合、多个微处理器、结合DSP内核的一或多个微处理器或任何其它此配置。
术语“存储器”应广义地解释为涵盖能够存储电子信息的任何电子组件。术语存储器可以是指各种类型的处理器可读介质，例如随机存取存储器(RAM)、只读存储器(ROM)、非易失性随机存取存储器(NVRAM)、可编程只读存储器(PROM)、可擦除可编程只读存储器(EPROM)、电可擦除PROM(EEPROM)、闪存、磁或光数据存储装置、寄存器等。如果处理器可以从存储器读取信息和/或向其写入信息，则存储器被称为与处理器电子通信。构成处理器所必需的存储器与处理器电子通信。
术语“指令”和“代码”应广义地解释为包含任何类型的计算机可读语句。例如，术语“指令”和“代码”可以是指一或多个程序、例程、子例程、功能、规程等。“指令”和“代码”可以包括单个计算机可读语句或许多计算机可读语句。
本文描述的功能可以由硬件执行的软件或固件实施。这些功能可以作为一或多个指令存储在计算机可读介质上。术语“计算机可读介质”或“计算机程序产品”是指可以由计算机或处理器访问的任何有形存储介质。作为实例而非限制，计算机可读介质可以包括RAM、ROM、EEPROM、CD-ROM或其它光盘存储装置、磁盘存储装置或其它磁存储装置、或可以用于以指令或数据结构的形式携带或存储所需的程序代码并且可以由计算机访问的任何其它介质。如本文使用，磁盘和光盘包含压缩盘(CD)、激光盘、光盘、数字通用盘(DVD)、软盘和盘，其中磁盘通常以磁性方式再现数据，而光盘通过激光光学地再现数据。应注意，计算机可读介质可以是有形的和非暂时的。术语“计算机程序产品”是指与可以由计算装置或处理器执行、处理或计算的代码或指令(例如，“程序”)组合的计算装置或处理器。如本文使用，术语“代码”可以是指可由计算装置或处理器执行的软件、指令、代码或数据。
还可以通过传输介质传输软件或指令。例如，如果使用同轴电缆、光纤电缆、双绞线、数字用户线(DSL)或无线技术(例如，红外线、无线电和微波)从网站、服务器或其它远程源传输软件，则同轴电缆、光纤电缆、双绞线、DSL或无线技术(例如，红外线、无线电和微波)都包含在传输介质的定义中。
本文公开的方法包括用于实现所描述的方法的一或多个步骤或动作。在不脱离权利要求的范围的情况下，方法步骤和/或动作可以彼此互换。换句话说，除非所描述的方法的正确操作需要特定顺序的步骤或动作，否则在不脱离权利要求的范围的情况下，可以修改特定步骤和/或动作的顺序和/或使用。
此外，应理解，可以通过装置下载和/或以其它方式获取用于执行本文描述的方法和技术的模块和/或其它适当的装置。例如，装置可以耦合到服务器，以便用于执行本文描述的方法的装置的转移。可替代地，可以经由存储装置(例如，随机存取存储器(RAM)、只读存储器(ROM)、物理存储介质(例如，压缩盘(CD)或软盘)等)来提供本文描述的各种方法，使得装置可以在将存储装置耦合或提供到装置时获取各种方法。
如本文使用，术语“和/或”应解释为表示一或多个项目。例如，短语“A、B和/或C”应解释为表示以下任何一种：仅A、仅B、仅C、A和B(但没有C)、B和C(但没有A)、A和C(但没有B)、或者A、B和C全部。如本文使用，短语“……中的至少一个”应解释为表示一或多个项目。例如，短语“A、B和C中的至少一个”或短语“A、B或C中的至少一个”应解释为表示以下任何一种：仅A、仅B、仅C、A和B(但没有C)、B和C(但没有A)、A和C(但没有B)、或者A、B和C全部。如本文使用，短语“……中的一或多个”应解释表示一或多个项目。例如，短语“A、B和C中的一或多个”或短语“A、B或C中的一或多个”应解释为表示以下任何一种：仅A、仅B、仅C、A和B(但没有C)、B和C(但没有A)、A和C(但没有B)、或者A、B和C全部。
应理解，权利要求不限于上面说明的精确配置和组件。在不脱离权利要求的范围的情况下，可以对本文描述的系统、方法和设备的布置、操作和细节进行各种修改、改变和变化。

Claims (74)

1.一种由设备执行的用于基于多个行程绘图的方法，其包括：
接收对应于第一行程的第一组对象数据；
接收对应于第二行程的第二组对象数据；
确定所述第一组对象数据与所述第二组对象数据之间的相似性度量，其中所述相似性度量指示至少一个对象的所述第一组对象数据的点与所述第二组对象数据的点之间的距离；
基于所述相似性度量来聚类所述至少一个对象的所述第一组对象数据和所述第二组对象数据，以产生至少一个对象簇，其中，所述聚类用于将所述第一组对象数据的对象与所述第二组对象数据中的对象进行关联，其中，所述聚类包括使用所述相似性度量来执行分层聚类，其中，使用物理距离作为针对两个或更多个聚类水平和/或步骤而不同的参数；和
基于所述至少一个对象簇来产生地图数据。
2.根据权利要求1所述的方法，其中所述相似性度量基于对象类型。
3.根据权利要求2所述的方法，其中针对标志对象类型确定所述相似性度量，并且其中所述方法进一步包括针对车道标记对象类型确定第二相似性度量。
4.根据权利要求1所述的方法，其中所述第一组对象数据和所述第二组对象数据包括标志数据，并且其中所述相似性度量指示来自不同行程的标志的点之间的距离。
5.根据权利要求1所述的方法，其中所述第一组对象数据和所述第二组对象数据包括车道标记数据，并且其中所述相似性度量指示来自不同行程的所述车道标记数据之间或某一区域内的所述车道标记数据的点之间的最小距离中的至少一个。
6.根据权利要求1所述的方法，其中执行分层聚类包括执行多个不同的聚类步骤。
7.根据权利要求6所述的方法，其中第一聚类步骤包括基于第一距离参数来聚类，并且第二聚类步骤包括基于第二距离参数来聚类，其中所述第二距离参数小于所述第一距离参数。
8.根据权利要求1所述的方法，其中聚类所述第一组对象数据和所述第二组对象数据包括执行谱聚类。
9.根据权利要求1所述的方法，其进一步包括基于所述至少一个对象簇来执行捆绑调整。
10.根据权利要求1所述的方法，其中在一或多个关联块中的每一个内执行聚类。
11.根据权利要求1所述的方法，其中产生所述地图数据包含基于所述至少一个对象簇来细化地图数据。
12.根据权利要求1所述的方法，其进一步包括将所产生的地图数据传输到至少一个车辆。
13.根据权利要求1所述的方法，其中所述对象数据包括对象位姿信息。
14.一种用于基于多个行程绘图的设备，其包括：
存储器；
处理器，其耦合到所述存储器，其中所述处理器经配置以：
接收对应于第一行程的第一组对象数据；
接收对应于第二行程的第二组对象数据；
确定所述第一组对象数据与所述第二组对象数据之间的相似性度量，其中所述相似性度量指示至少一个对象的所述第一组对象数据的点与所述第二组对象数据的点之间的距离；
基于所述相似性度量来聚类所述至少一个对象的所述第一组对象数据和所述第二组对象数据，以产生至少一个对象簇，其中，所述聚类用于将所述第一组对象数据的对象和所述第二组对象数据的对象进行关联，其中，所述聚类包括使用所述相似性度量来执行分层聚类，其中，使用物理距离作为针对两个或更多个聚类水平和/或步骤而不同的参数；和
基于所述至少一个对象簇来产生地图数据。
15.根据权利要求14所述的设备，其中所述相似性度量基于对象类型。
16.根据权利要求15所述的设备，其中所述处理器经配置以针对标志对象类型确定所述相似性度量，并且其中所述处理器经配置以针对车道标记对象类型确定第二相似性度量。
17.根据权利要求14所述的设备，其中所述第一组对象数据和所述第二组对象数据包括标志数据，并且其中所述相似性度量指示来自不同行程的标志的点之间的距离。
18.根据权利要求14所述的设备，其中所述第一组对象数据和所述第二组对象数据包括车道标记数据，并且其中所述相似性度量指示来自不同行程的所述车道标记数据之间或某一区域内的所述车道标记数据的点之间的最小距离中的至少一个。
19.根据权利要求14所述的设备，其中执行分层聚类包括执行多个不同的聚类步骤。
20.根据权利要求19所述的设备，其中第一聚类步骤包括基于第一距离参数来聚类，并且第二聚类步骤包括基于第二距离参数来聚类，其中所述第二距离参数小于所述第一距离参数。
21.根据权利要求14所述的设备，其中所述处理器经配置以通过执行谱聚类来聚类所述第一组对象数据和所述第二组对象数据。
22.根据权利要求14所述的设备，其中所述处理器经配置以基于所述至少一个对象簇来执行捆绑调整。
23.根据权利要求14所述的设备，其中所述处理器经配置以在一或多个关联块中的每一个内执行聚类。
24.根据权利要求14所述的设备，其中所述处理器经配置以通过基于所述至少一个对象簇来细化地图数据来产生所述地图数据。
25.根据权利要求14所述的设备，其中所述处理器经配置以将所产生的地图数据传输到至少一个车辆。
26.根据权利要求14所述的设备，其中所述对象数据包括对象位姿信息。
27.一种存储计算机可执行代码以用于基于多个行程绘图的非暂时性有形计算机可读介质，其包括：
用于使电子装置接收对应于第一行程的第一组对象数据的代码；
用于使所述电子装置接收对应于第二行程的第二组对象数据的代码；
用于使所述电子装置确定所述第一组对象数据与所述第二组对象数据之间的相似性度量的代码，其中所述相似性度量指示至少一个对象的所述第一组对象数据的点与所述第二组对象数据的点之间的距离；
用于使所述电子装置基于所述相似性度量来聚类所述至少一个对象的所述第一组对象数据和所述第二组对象数据以产生至少一个对象簇的代码，其中，所述聚类用于将所述第一组对象数据的对象和所述第二组对象数据的对象进行关联，其中，所述聚类包括使用所述相似性度量来执行分层聚类，其中，使用物理距离作为针对两个或更多个聚类水平和/或步骤而不同的参数；和
用于使所述电子装置基于所述至少一个对象簇来产生地图数据的代码。
28.根据权利要求27所述的计算机可读介质，其中所述相似性度量基于对象类型。
29.一种用于基于多个行程绘图的设备，其包括：
用于接收对应于第一行程的第一组对象数据的装置；
用于接收对应于第二行程的第二组对象数据的装置；
用于确定所述第一组对象数据与所述第二组对象数据之间的相似性度量的装置，其中所述相似性度量指示至少一个对象的所述第一组对象数据的点与所述第二组对象数据的点之间的距离；
用于基于所述相似性度量来聚类所述至少一个对象的所述第一组对象数据和所述第二组对象数据以产生至少一个对象簇的装置，其中，所述聚类用于将所述第一组对象数据的对象和所述第二组对象数据的对象进行关联，其中，所述聚类包括使用所述相似性度量来执行分层聚类，其中，使用物理距离作为针对两个或更多个聚类水平和/或步骤而不同的参数；和
用于基于所述至少一个对象簇来产生地图数据的装置。
30.根据权利要求29所述的设备，其中所述相似性度量基于对象类型。
31.一种车辆，其包括：
存储器；
处理器，其耦合到所述存储器，其中所述处理器经配置以：
接收由所述车辆在第一行程期间收集的第一对象数据；
传输所述第一对象数据；
接收地图数据，所述地图数据是基于指示至少一个对象的所述第一对象数据的点与第二对象数据的点之间的距离的相似性度量，通过针对所述至少一个对象对所述第一对象数据和所述第二对象数据进行聚类来生成的，其中所述第二对象数据是在先前行进的第二行程期间收集的，其中，所述聚类用于将所述第一对象数据的对象和所述第二对象数据的对象进行关联，其中，所述聚类包括使用所述相似性度量来执行分层聚类，其中，使用物理距离作为针对两个或更多个聚类水平和/或步骤而不同的参数；以及
根据所接收地图数据对所述车辆进行定位。
32.根据权利要求31所述的车辆，其中所述相似性度量基于对象类型。
33.根据权利要求32所述的车辆，其中所述相似性度量基于标志对象类型，且其中第二相似性度量基于车道标记对象类型。
34.根据权利要求31所述的车辆，其中所述地图数据是基于至少一个对象簇产生的，其中所述对象簇基于所述至少一个对象的所述第一对象数据和所述第二对象数据。
35.根据权利要求34所述的车辆，其中所述地图数据基于捆绑调整，所述捆绑调整基于所述至少一个对象簇。
36.根据权利要求34所述的车辆，其中所述至少一个对象簇基于一或多个关联块中的每一个。
37.根据权利要求31所述的车辆，其中所述第一对象数据或所述第二对象数据包括以下各项中的至少一个：帧、对象特征、相机位姿信息、二维2D对象位置数据、三维3D对象位置数据或3D定向数据。
38.根据权利要求31所述的车辆，其中所述地图数据包括地图或地图更新。
39.根据权利要求31所述的车辆，其中对象包括标志、车道、车道标记或样条。
40.根据权利要求31所述的车辆，其中所述第二行程由所述车辆或第二车辆行进。
41.根据权利要求31所述的车辆，其中所述地图数据对应于一个或多个块。
42.一种用于车辆的方法，其包括：
接收由所述车辆在第一行程期间收集的第一对象数据；
传输所述第一对象数据；
接收地图数据，所述地图数据是基于指示至少一个对象的所述第一对象数据的点与第二对象数据的点之间的距离的相似性度量，通过针对所述至少一个对象对所述第一对象数据和所述第二对象数据进行聚类来生成的，其中所述第二对象数据是在先前行进的第二行程期间收集的，其中，所述聚类用于将所述第一对象数据的对象和所述第二对象数据的对象进行关联，其中，所述聚类包括使用所述相似性度量来执行分层聚类，其中，使用物理距离作为针对两个或更多个聚类水平和/或步骤而不同的参数；以及
根据所接收地图数据对所述车辆进行定位。
43.根据权利要求42所述的方法，其中所述相似性度量基于对象类型。
44.根据权利要求43所述的方法，其中所述相似性度量基于标志对象类型，且其中第二相似性度量基于车道标记对象类型。
45.根据权利要求42所述的方法，其中所述地图数据是基于至少一个对象簇产生的，其中所述对象簇基于所述至少一个对象的所述第一对象数据和所述第二对象数据。
46.根据权利要求45所述的方法，其中所述地图数据基于捆绑调整，所述捆绑调整基于所述至少一个对象簇。
47.根据权利要求45所述的方法，其中所述至少一个对象簇基于一或多个关联块中的每一个。
48.根据权利要求42所述的方法，其中所述第一对象数据或所述第二对象数据包括以下各项中的至少一个：帧、对象特征、相机位姿信息、二维2D对象位置数据、三维3D对象位置数据或3D定向数据。
49.根据权利要求42所述的方法，其中所述地图数据包括地图或地图更新。
50.根据权利要求42所述的方法，其中对象包括标志、车道、车道标记或样条。
51.根据权利要求42所述的方法，其中所述第二行程由所述车辆或第二车辆行进。
52.根据权利要求42所述的方法，其中所述地图数据对应于一个或多个块。
53.一种用于车辆的设备，其包括：
处理器，其耦合到存储器，其中所述处理器经配置以：
从车辆接收第一对象数据，其中所述第一对象数据由所述车辆在第一行程期间收集；以及
传输地图数据，所述地图数据是基于指示至少一个对象的所述第一对象数据的点与第二对象数据的点之间的距离的相似性度量，通过针对所述至少一个对象对所述第一对象数据和所述第二对象数据进行聚类来生成的，其中所述第二对象数据是在先前行进的第二行程期间收集的，其中，所述聚类用于将所述第一对象数据的对象和所述第二对象数据的对象进行关联，其中，所述聚类包括使用所述相似性度量来执行分层聚类，其中，使用物理距离作为针对两个或更多个聚类水平和/或步骤而不同的参数。
54.根据权利要求53所述的设备，其中所述相似性度量基于对象类型。
55.根据权利要求54所述的设备，其中所述相似性度量基于标志对象类型，且其中所述处理器经配置以基于车道标记对象类型确定第二相似性度量。
56. 根据权利要求53所述的设备，其中所述处理器经配置以：
聚类所述第一对象数据和所述第二对象数据，以产生至少一个对象簇；以及
基于至少一个对象簇来产生所述地图数据。
57.根据权利要求56所述的设备，其中所述处理器经配置以基于所述至少一个对象簇来执行捆绑调整。
58.根据权利要求56所述的设备，其中所述处理器经配置以在一或多个关联块中的每一个内执行聚类。
59.根据权利要求53所述的设备，其中所述第一对象数据或所述第二对象数据包括以下各项中的至少一个：帧、对象特征、相机位姿信息、二维2D对象位置数据、三维3D对象位置数据或3D定向数据。
60.根据权利要求53所述的设备，其中所述地图数据包括地图或地图更新。
61.根据权利要求53所述的设备，其中对象包括标志、车道、车道标记或样条。
62.根据权利要求53所述的设备，其中所述第二行程由所述车辆或第二车辆行进。
63.根据权利要求53所述的设备，其中所述地图数据对应于一个或多个块。
64. 一种用于地图数据的方法，其包括：
从车辆接收第一对象数据，其中所述第一对象数据由所述车辆在第一行程期间收集：以及
传输地图数据，所述地图数据是基于指示至少一个对象的所述第一对象数据的点与第二对象数据的点之间的距离的相似性度量，通过针对所述至少一个对象对所述第一对象数据和所述第二对象数据进行聚类来生成的，其中所述第二对象数据是在先前行进的第二行程期间收集的，其中，所述聚类用于将所述第一对象数据的对象和所述第二对象数据的对象进行关联，其中，所述聚类包括使用所述相似性度量来执行分层聚类，其中，使用物理距离作为针对两个或更多个聚类水平和/或步骤而不同的参数。
65.根据权利要求64所述的方法，其中所述相似性度量基于对象类型。
66.根据权利要求65所述的方法，其中所述相似性度量基于标志对象类型，且其中所述方法进一步包括以基于车道标记对象类型确定第二相似性度量。
67. 根据权利要求64所述的方法，其进一步包括：
聚类所述第一对象数据和所述第二对象数据，以产生至少一个对象簇；以及
基于至少一个对象簇来产生所述地图数据。
68.根据权利要求67所述的方法，其进一步包括：
基于所述至少一个对象簇来执行捆绑调整。
69.根据权利要求67所述的方法，其进一步包括：
在一或多个关联块中的每一个内执行聚类。
70.根据权利要求64所述的方法，其中所述第一对象数据或所述第二对象数据包括以下各项中的至少一个：帧、对象特征、相机位姿信息、二维2D对象位置数据、三维3D对象位置数据或3D定向数据。
71.根据权利要求64所述的方法，其中所述地图数据包括地图或地图更新。
72.根据权利要求64所述的方法，其中对象包括标志、车道、车道标记或样条。
73.根据权利要求64所述的方法，其中所述第二行程由所述车辆或第二车辆行进。
74.根据权利要求64所述的方法，其中所述地图数据对应于一个或多个块。
CN201780075008.6A 2017-01-04 2017-10-25 用于基于多行程数据来绘图的系统和方法 Active CN110036392B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202410054447.0A CN117889874A (zh) 2017-01-04 2017-10-25 用于基于多行程数据来绘图的系统和方法

Applications Claiming Priority (5)

Application Number Priority Date Filing Date Title
US201762442404P 2017-01-04 2017-01-04
US62/442,404 2017-01-04
US15/620,167 2017-06-12
US15/620,167 US10296812B2 (en) 2017-01-04 2017-06-12 Systems and methods for mapping based on multi-journey data
PCT/US2017/058240 WO2018128674A1 (en) 2017-01-04 2017-10-25 Systems and methods for mapping based on multi-journey data

Related Child Applications (1)

Application Number Title Priority Date Filing Date
CN202410054447.0A Division CN117889874A (zh) 2017-01-04 2017-10-25 用于基于多行程数据来绘图的系统和方法

Publications (2)

Publication Number Publication Date
CN110036392A CN110036392A (zh) 2019-07-19
CN110036392B true CN110036392B (zh) 2024-01-05

Family

ID=62711757

Family Applications (2)

Application Number Title Priority Date Filing Date
CN201780075008.6A Active CN110036392B (zh) 2017-01-04 2017-10-25 用于基于多行程数据来绘图的系统和方法
CN202410054447.0A Pending CN117889874A (zh) 2017-01-04 2017-10-25 用于基于多行程数据来绘图的系统和方法

Family Applications After (1)

Application Number Title Priority Date Filing Date
CN202410054447.0A Pending CN117889874A (zh) 2017-01-04 2017-10-25 用于基于多行程数据来绘图的系统和方法

Country Status (4)

Country Link
US (4) US10296812B2 (zh)
EP (1) EP3566173B1 (zh)
CN (2) CN110036392B (zh)
WO (1) WO2018128674A1 (zh)

Families Citing this family (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP6552979B2 (ja) * 2016-02-16 2019-07-31 株式会社日立製作所 画像処理装置、警告装置、画像処理システム、画像処理方法
US10296812B2 (en) 2017-01-04 2019-05-21 Qualcomm Incorporated Systems and methods for mapping based on multi-journey data
US10713940B2 (en) 2017-10-31 2020-07-14 Waymo Llc Detecting and responding to traffic redirection for autonomous vehicles
US10401862B2 (en) * 2017-10-31 2019-09-03 Waymo Llc Semantic object clustering for autonomous vehicle decision making
US10852731B1 (en) * 2017-12-28 2020-12-01 Waymo Llc Method and system for calibrating a plurality of detection systems in a vehicle
US20190325349A1 (en) * 2018-04-19 2019-10-24 Here Global B.V. Method, apparatus, and system for traffic sign learning based on road network connectivity
DE102018209607A1 (de) * 2018-06-14 2019-12-19 Volkswagen Aktiengesellschaft Verfahren und Vorrichtung zum Bestimmen einer Position eines Kraftfahrzeugs
US11023752B2 (en) * 2018-08-29 2021-06-01 Here Global B.V. Method and system for learning about road signs using hierarchical clustering
FR3085761B1 (fr) * 2018-09-11 2021-01-15 Continental Automotive France Systeme et procede de localisation de la position d'un objet routier par apprentissage automatique non supervise
US10706587B1 (en) * 2018-09-25 2020-07-07 Amazon Technologies, Inc. Calibration of multiple cameras
US10782136B2 (en) * 2018-09-28 2020-09-22 Zoox, Inc. Modifying map elements associated with map data
US11244177B2 (en) * 2018-12-12 2022-02-08 Here Global B.V. Methods and systems for roadwork zone identification
US11790667B2 (en) * 2018-12-20 2023-10-17 Here Global B.V. Method and apparatus for localization using search space pruning
CN113678168B (zh) * 2019-01-28 2023-12-15 弗劳恩霍夫应用研究促进协会 空间中的元素定位
US11681030B2 (en) 2019-03-05 2023-06-20 Waymo Llc Range calibration of light detectors
JP7245084B2 (ja) * 2019-03-15 2023-03-23 日立Astemo株式会社 自動運転システム
US10887928B2 (en) * 2019-04-24 2021-01-05 Here Global B.V. Lane aware clusters for vehicle to vehicle communication
CN110097570B (zh) * 2019-04-30 2022-03-01 腾讯科技（深圳）有限公司 一种图像处理方法和装置
CN112219206B (zh) * 2019-07-25 2024-09-06 北京航迹科技有限公司 用于确定位姿的系统和方法
US11315431B2 (en) * 2019-10-09 2022-04-26 Uatc, Llc Systems and methods for autonomous vehicle controls
US11747453B1 (en) 2019-11-04 2023-09-05 Waymo Llc Calibration system for light detection and ranging (lidar) devices
DE102019217658A1 (de) * 2019-11-15 2021-05-20 Robert Bosch Gmbh Verfahren zum Extrahieren von Merkmalen aus crowd-basiert gesammelten Messdaten
CN110991336B (zh) * 2019-12-02 2023-04-28 深圳大学 一种基于感官替代的辅助感知方法和系统
CN113129438B (zh) * 2020-01-15 2023-06-23 阿里巴巴集团控股有限公司 一种车道线的精度提升方法、装置及可读存储介质
DE102020128391A1 (de) * 2020-10-28 2022-04-28 Bayerische Motoren Werke Aktiengesellschaft Vorrichtung und Verfahren zur Ermittlung von Kartendaten anhand von Observationen
US20220178718A1 (en) * 2020-12-04 2022-06-09 Mitsubishi Electric Automotive America, Inc. Sensor fusion for dynamic mapping
CN116888563A (zh) 2020-12-22 2023-10-13 奇跃公司 用于虚拟或增强现实系统的校准
US12353966B2 (en) * 2021-07-23 2025-07-08 International Business Machines Corporation Spectral clustering of high-dimensional data
CN113673582B (zh) * 2021-07-30 2023-05-09 西南交通大学 基于系统聚类分析的铁路动态基准点多层级分群方法
CN114492619B (zh) * 2022-01-22 2023-08-01 电子科技大学 一种基于统计和凹凸性的点云数据集构建方法及装置
CN115272681B (zh) * 2022-09-22 2022-12-20 中国海洋大学 基于高阶特征类解耦的海洋遥感图像语义分割方法及系统
US12422276B1 (en) * 2022-11-16 2025-09-23 Amazon Technologies, Inc. System to determine map data for autonomous mobile device map
CN118509566B (zh) * 2024-06-17 2024-11-22 深圳市强普光电有限公司 投影机控制参数分析方法、装置及设备
CN119292671B (zh) * 2024-12-13 2025-05-02 杭州宇泛智能科技股份有限公司 跨芯片平台的指令转换方法

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1453747A (zh) * 2002-04-25 2003-11-05 微软公司 聚类
CN103699578A (zh) * 2013-12-01 2014-04-02 北京航空航天大学 一种基于谱图分析的图像检索方法
CN104766058A (zh) * 2015-03-31 2015-07-08 百度在线网络技术（北京）有限公司 一种获取车道线的方法和装置
WO2016099866A1 (en) * 2014-12-19 2016-06-23 Qualcomm Incorporated Scalable 3d mapping system
DE102015203016A1 (de) * 2015-02-19 2016-08-25 Volkswagen Aktiengesellschaft Verfahren und Vorrichtung zur optischen Selbstlokalisation eines Kraftfahrzeugs in einem Umfeld
CN106030684A (zh) * 2013-12-11 2016-10-12 高通股份有限公司 用于复杂地图的经优化呈现的方法和设备

Family Cites Families (27)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7353109B2 (en) 2004-02-05 2008-04-01 Alpine Electronics, Inc. Display method and apparatus for navigation system for performing cluster search of objects
US7512487B1 (en) 2006-11-02 2009-03-31 Google Inc. Adaptive and personalized navigation system
JP4420011B2 (ja) * 2006-11-16 2010-02-24 株式会社日立製作所 物体検知装置
KR100923723B1 (ko) 2007-03-16 2009-10-27 제주대학교 산학협력단 도로 네트워크 공간에서 이동객체의 유사 궤적 클러스터링방법
JP4990115B2 (ja) 2007-12-06 2012-08-01 株式会社デンソー 位置範囲設定装置、移動物体搭載装置の制御方法および制御装置、ならびに車両用空調装置の制御方法および制御装置
CA2712673A1 (en) * 2008-02-04 2009-08-13 Tele Atlas North America Inc. Method for map matching with sensor detected objects
KR100955483B1 (ko) * 2008-08-12 2010-04-30 삼성전자주식회사 3차원 격자 지도 작성 방법 및 이를 이용한 자동 주행 장치의 제어 방법
US20120047087A1 (en) 2009-03-25 2012-02-23 Waldeck Technology Llc Smart encounters
JP4957747B2 (ja) * 2009-05-18 2012-06-20 トヨタ自動車株式会社 車両環境推定装置
CA2770183C (en) 2009-08-14 2016-10-11 Telogis, Inc. Real time map rendering with data clustering and expansion and overlay
US20120033896A1 (en) * 2010-08-08 2012-02-09 Geoffrey Louis Barrows Visual Motion Processing with Offset Downsampling
CN103123722B (zh) * 2011-11-18 2016-04-27 株式会社理光 道路对象检测方法和系统
US8892350B2 (en) 2011-12-16 2014-11-18 Toyoda Jidosha Kabushiki Kaisha Journey learning system
US9116981B2 (en) * 2012-07-05 2015-08-25 Canon Kabushiki Kaisha Systems and methods for cluster analysis with relational truth
US20140012494A1 (en) * 2012-07-06 2014-01-09 International Business Machines Corporation Collaborative gps tracking
US10115202B2 (en) * 2012-12-27 2018-10-30 Arria Data2Text Limited Method and apparatus for motion detection
US20150285639A1 (en) 2014-04-04 2015-10-08 Umm-Al-Qura University Method and system for crowd sensing to be used for automatic semantic identification
US9733097B2 (en) * 2014-10-31 2017-08-15 Toyota Jidosha Kabushiki Kaisha Classifying routes of travel
US9569693B2 (en) 2014-12-31 2017-02-14 Here Global B.V. Method and apparatus for object identification and location correlation based on received images
CN118816924A (zh) 2015-02-10 2024-10-22 御眼视觉技术有限公司 用于自主车辆导航的稀疏地图
US9631932B2 (en) 2015-06-05 2017-04-25 Nokia Technologies Oy Crowd sourced interaction of browsing behavior in a 3D map
US10534814B2 (en) * 2015-11-11 2020-01-14 Facebook, Inc. Generating snippets on online social networks
US20170276504A1 (en) * 2016-03-22 2017-09-28 Toyota Jidosha Kabushiki Kaisha Vehicular Traffic Assistance Based on Traffic Management Decisions
US10248124B2 (en) 2016-07-21 2019-04-02 Mobileye Vision Technologies, Inc. Localizing vehicle navigation using lane measurements
US10353931B2 (en) * 2016-12-30 2019-07-16 DeepMap Inc. High definition map and route storage management system for autonomous vehicles
US10296812B2 (en) 2017-01-04 2019-05-21 Qualcomm Incorporated Systems and methods for mapping based on multi-journey data
US10803361B2 (en) * 2017-05-11 2020-10-13 Facebook, Inc. Systems and methods for partitioning geographic regions

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1453747A (zh) * 2002-04-25 2003-11-05 微软公司 聚类
CN103699578A (zh) * 2013-12-01 2014-04-02 北京航空航天大学 一种基于谱图分析的图像检索方法
CN106030684A (zh) * 2013-12-11 2016-10-12 高通股份有限公司 用于复杂地图的经优化呈现的方法和设备
WO2016099866A1 (en) * 2014-12-19 2016-06-23 Qualcomm Incorporated Scalable 3d mapping system
DE102015203016A1 (de) * 2015-02-19 2016-08-25 Volkswagen Aktiengesellschaft Verfahren und Vorrichtung zur optischen Selbstlokalisation eines Kraftfahrzeugs in einem Umfeld
CN104766058A (zh) * 2015-03-31 2015-07-08 百度在线网络技术（北京）有限公司 一种获取车道线的方法和装置

Also Published As

Publication number Publication date
CN110036392A (zh) 2019-07-19
EP3566173B1 (en) 2023-06-21
US11776280B2 (en) 2023-10-03
US10296812B2 (en) 2019-05-21
US20230419685A1 (en) 2023-12-28
US11120296B2 (en) 2021-09-14
WO2018128674A1 (en) 2018-07-12
EP3566173A1 (en) 2019-11-13
US20180189601A1 (en) 2018-07-05
US20190236405A1 (en) 2019-08-01
US20210397884A1 (en) 2021-12-23
CN117889874A (zh) 2024-04-16

Similar Documents

Publication Publication Date Title
CN110036392B (zh) 用于基于多行程数据来绘图的系统和方法
US10630962B2 (en) Systems and methods for object location
US10867189B2 (en) Systems and methods for lane-marker detection
CN112105890B (zh) 用于自动驾驶车辆的基于rgb点云的地图生成系统
CN112105893B (zh) 用于自动驾驶车辆的实时地图生成系统
CN111771206B (zh) 用于自动驾驶车辆的地图分区系统
CN112055805B (zh) 用于自动驾驶车辆的点云登记系统
US10284875B2 (en) Systems and methods for determining feature point motion
US10937214B2 (en) System and method for merging maps
CN109997150B (zh) 用于对道路特征进行分类的系统和方法
CN107735797B (zh) 用于确定第一坐标系与第二坐标系之间的运动的方法
CN108279670B (zh) 用于调整点云数据采集轨迹的方法、设备以及计算机可读介质
Eynard et al. Real time UAV altitude, attitude and motion estimation from hybrid stereovision
Fanani et al. Keypoint trajectory estimation using propagation based tracking
US10636205B2 (en) Systems and methods for outlier edge rejection
CN115222815A (zh) 障碍物距离检测方法、装置、计算机设备和存储介质
CN109325962B (zh) 信息处理方法、装置、设备以及计算机可读存储介质
US20200242779A1 (en) Systems and methods for extracting a surface normal from a depth image
US20180001821A1 (en) Environment perception using a surrounding monitoring system
CN115088255A (zh) 定位方法、电子设备和存储介质

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
TG01 Patent term adjustment
TG01 Patent term adjustment