CN101996420A

CN101996420A - 信息处理装置、信息处理方法及程序

Info

Publication number: CN101996420A
Application number: CN2010102547490A
Authority: CN
Inventors: 多井坚一郎; 福地正树
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 2009-08-21
Filing date: 2010-08-13
Publication date: 2011-03-30
Anticipated expiration: 2030-08-13
Also published as: JP2011043419A; EP2302586B1; US20110044504A1; EP2302586A1; CN101996420B; US8861785B2

Abstract

公开了信息处理装置、信息处理方法及程序。该信息处理装置包括：三维信息产生部分，用于通过连续接收来自不同视点的拍摄图像并使用包括特征点跟踪信息的观测信息更新状态数据来获得移动照相机的位置和姿态或者特征点的三维位置，该状态数据包括该图像内的特征点的三维位置以及照相机的位置和姿态信息；以及子地图产生部分，用于通过分割要被计算三维位置的区域来产生子地图。该三维信息产生部分通过针对所产生的各个子地图而产生与不包括关于子地图区域外的特征点的信息的子地图相对应的状态数据并更新所产生的对应于子地图的状态数据，来获得照相机的位置和姿态或特征点的三维位置。

Description

信息处理装置、信息处理方法及程序

技术领域

本发明涉及信息处理装置、信息处理方法及程序。更具体来说，本发明涉及用于分析三维空间的信息处理装置、信息处理方法及程序。

背景技术

在一种方法中，通过用照相机拍摄三维空间并分析拍摄的图像来分析该空间。例如，从拍摄的图像中提取两个或更多个特征点(也称为标志点(landmark))并估计这些特征点的三维位置。

在这种方式中，用移动照相机拍摄图像并分析在两个或更多个拍摄图像中包括的特征点的轨迹。由此估计(即，定位)该特征点的三维位置和照相机(自身)的位置和姿态。可以使用关于这些特征点的三维位置信息产生(即，绘制)周围地图(即，环境地图)。这些照相机(自身)的定位和周围地图(即，环境地图)的绘制同时进行，这被称为并行定位和绘制(simultaneous localization and mapping，SLAM)。

用于SLAM的方式包括基于EKF的SLAM，其采用扩展卡尔曼滤波器(Extended Kalman filter，EKF)。例如，在作者为S.Thrun、W.Burgard和D.Fox的″Probabilistic Robotics″(The MIT Press，Cambridge，MA，2005)中描述了基于EKF的SLAM。

在基于EKF的SLAM中，例如，用移动照相机连续拍摄图像，获得在每个图像中包括的特征点的轨迹(即，跟踪信息)，然后用移动立体方法(moving stereo method)同时估计照相机的行进距离和特征点的三维位置。

基于EKF的SLAM使用包括多维正态分布数据的“状态数据”作为包括例如照相机的位置、姿态、速度和角速度以及关于各特征点的位置信息的数据的概率分布模型。利用卡尔曼滤波器或扩展卡尔曼滤波器更新该“状态数据”，以估计特征点和照相机的位置。

该“状态数据”由包括均值矢量(mean vector)和方差-协方差矩阵(variance-covariance matrix)的多维正态分布数据构成。均值矢量代表照相机的位置、姿态、速度和角速度以及关于各特征点的位置信息。方差-协方差矩阵包括例如照相机的位置、姿态、速度和角速度以及关于各特征点的位置信息的固有状态值的方差和对应于上述状态值当中不同状态值的相关信息的组合的协方差。将结合本发明的实施例详细描述该数据结构。

在基于EKF的SLAM中，使用由照相机拍摄的图像更新“状态数据”。因此，也更新与在“状态数据”中注册的但未被包括在作为要处理的图像输入的最近拍摄的图像中的特征点相关的信息。也就是说，在先前输入图像中包括的一些特征点未被包括在最近输入的图像中。在先前输入图像中包括的特征点的信息被注册在“状态数据”中。因此，也利用卡尔曼滤波器更新与“状态数据”包括中的“由照相机拍摄的特征点”和“不是由照相机拍摄的特征点”之间的关联性相关的信息。

这说明被产生地图的区域越大，该区域涉及的特征点的数量越多。如果“状态数据”包括大量特征点信息，则使用卡尔曼滤波器或扩展卡尔曼滤波器对“状态数据”的更新涉及增加的计算量。

如上所述，“状态数据”包括方差-协方差矩阵，其保持与各特征点和照相机之间的关联性相关的信息。数量增加的特征点涉及尺寸增加的方差-协方差矩阵。使用卡尔曼滤波器或扩展卡尔曼滤波器更新“状态数据”时的计算量关于特征点的数量n以O(9n²)的量级增加。由于数据将被重复地更新，所以存在为了产生具有大量特征点的大尺寸的三维地图而导致计算负荷和处理时间过度增加的问题。

发明内容

因此，希望提供一种信息处理装置、信息处理方法和程序，其通过用于经由对拍摄的图像进行分析来估计特征点位置的配置，减小处理负荷，准确度没有任何减小地预测特征点的三维位置，并产生三维地图。

本发明的第一实施例是一种信息处理装置，包括：三维信息产生部分，用于通过连续接收利用在空间中移动的照相机从两个或更多个不同视点拍摄的图像并使用包括特征点跟踪信息的观测信息更新状态数据来获得照相机的位置和姿态或者特征点的三维位置，该状态数据包括该图像内的特征点的三维位置以及该照相机的位置和姿态信息；以及子地图产生部分，用于通过分割要被计算三维位置的区域来产生子地图，其中三维信息产生部分通过针对子地图产生部分产生的各个子地图而产生与不包括关于子地图区域外的特征点的信息的子地图相对应的状态数据并更新所产生的对应于子地图的状态数据，来获得照相机的位置和姿态或特征点的三维位置。

在根据本发明实施例的信息处理装置中，三维信息产生部分与各个子地图相对应地产生多维正态分布数据作为对应于所述子地图的状态数据，并使用所述观测信息更新对应于所述子地图的多维正态分布数据，该多维正态分布数据包括代表所述照相机的位置和姿态以及所述子地图中各个特征点的位置的均值矢量以及方差-协方差矩阵。

在根据本发明实施例的信息处理装置中，该方差-协方差矩阵包括如照相机的位置和姿态以及关于各个特征点的位置信息的固有状态值的方差和对应于所述状态值当中不同状态值的相关信息组合的协方差。

在根据本发明实施例的信息处理装置中，三维信息产生部分使用卡尔曼滤波器或扩展卡尔曼滤波器(EKF)更新对应于子地图的状态数据。

在根据本发明实施例的信息处理装置中，如果从先前的子地图到当前子地图地顺序地处理子地图，则三维信息产生部分使用在对应于先前的子地图的状态数据中包括的照相机信息而直接产生对应于当前子地图的状态数据。

在根据本发明实施例的信息处理装置中，当子地图中包括的特征点的数量达到预定的上限数量N或以上时，子地图产生部分将该子地图分割成其间形成重叠区域的两个子地图，这两个子地图具有至少一个共同的特征点。

在根据本发明实施例的信息处理装置中，三维信息产生部分产生与通过分割所述子地图而产生的各个子地图相对应的状态数据，并且通过从与尚未被分割的子地图相对应的状态数据当中删除关于未被包括在被分割的各个子地图中的特征点的信息而产生与该两个被分割的子地图的每个相对应的状态数据。

在根据本发明实施例的信息处理装置中，子地图产生部分将通过对要被计算三维位置的区域的投影变换而产生的二维平面分割成其间具有重叠区域的两个或更多个预定尺寸的子地图。

在根据本发明实施例的信息处理装置中，三维信息产生部分通过束调整(bundle adiustment)来修正特征点的位置。

在根据本发明实施例的信息处理装置中，三维信息产生部分执行同时的定位和地图化(simultaneous localization and mapping，SLAM)，其中同时进行照相机的定位和周围地图(即，环境地图)的地图化。

本发明的第二实施例是一种在信息处理装置中执行的信息处理方法，该方法包括以下步骤：由子地图产生部分通过分割要被计算三维位置的区域来产生子地图；以及由三维信息产生部分产生三维信息，所述三维信息产生部分通过连续接收利用在空间中移动的照相机从两个或更多个不同视点拍摄的图像并使用包括特征点跟踪信息的观测信息更新状态数据来获得照相机的位置和姿态或者特征点的三维位置，所述状态数据包括所述图像内的特征点的三维位置和所述照相机的位置和姿态信息，其中所述产生三维信息的步骤通过针对所述子地图产生部分产生的各个子地图而产生与不包括关于子地图区域外的特征点的信息的子地图相对应的状态数据并更新所产生的对应于子地图的状态数据，来获得所述照相机的位置和姿态或所述特征点的三维位置。

本发明的第三实施例是一种使信息处理装置处理信息的程序，该程序包括以下步骤：使子地图产生部分通过分割要被计算三维位置的区域来产生子地图；以及使三维信息产生部分通过以下方式来产生三维信息：通过连续接收利用在空间中移动的照相机从两个或更多个不同视点拍摄的图像并使用包括特征点跟踪信息的观测信息更新状态数据，来获得照相机的位置和姿态或者特征点的三维位置，所述状态数据包括所述图像内的特征点的三维位置和所述照相机的位置和姿态信息，其中所述产生三维信息的步骤通过针对所述子地图产生部分产生的各个子地图而产生与不包括关于子地图区域外的特征点的信息的子地图相对应的状态数据并更新所产生的对应于子地图的状态数据，来获得所述照相机的位置和姿态或所述特征点的三维位置。

本发明的程序可以由向图像处理装置和计算机系统提供各种计算机可读程序代码的存储介质和通信介质来提供。该图像处理装置和计算机系统利用这些计算机可读程序执行根据该程序的处理。

通过以下对本发明的详细描述和附图，本发明的其它目的、特征和优点对本领域的技术人员来说是明显的。在本文中使用的术语“系统”描述不一定在单个壳体中的多个装置的逻辑集合配置。

本发明的实施例提供一种用于减小计算量并有效产生三维位置信息的配置。在SLAM处理(即，用于使用作为观测数据输入的利用照相机拍摄的图像获得特征点的三维位置且随后更新具有包括特征点位置信息的多维正态分布数据的状态数据的处理)中，通过分割要被产生三维信息的区域来产生子地图。然后，基于观测数据而产生并更新与不包括和不属于子地图的特征点相关的数据的子地图相对应的状态数据。该配置可以减小在更新状态数据时涉及到的状态数据的量和计算量，从而实现有效的处理。

附图说明

图1示意性地示出同时的定位和地图化(SLAM)处理；

图2示出在SLAM中使用的状态数据的配置；

图3示出针孔照相机(pinhole camera)模型；

图4示出针孔照相机模型；

图5示出在SLAM中使用的状态数据的配置；

图6示出在根据本发明实施例的信息处理装置的处理中使用的子地图和状态数据；

图7示出在根据本发明实施例的信息处理装置的处理中使用的子地图和图像帧之间的关联性；

图8示出在根据本发明实施例的信息处理装置的处理中使用的子地图和状态数据；

图9示出根据本发明实施例的信息处理装置的示例性配置；

图10是根据本发明实施例的信息处理装置中执行的处理序列的流程图；

图11是图10的流程图中的步骤S101中用于选择关注的子地图的序列的详细流程图；

图12是图10的流程图中的步骤S102中用于准备针对关注的子地图的“状态数据”的处理的流程图；

图13示出对应于子地图的状态数据；

图14是用于当包括在关注的子地图中的特征点的数量达到预定的上限或以上时分割关注的子地图的处理序列的流程图；

图15是用于图14的流程图中的步骤S303中的“分割关注的子地图”的序列的详细流程图；

图16示出图15的流程图中的步骤S452至S454中的分割子地图的示例性处理；

图17示出图15的流程图中的步骤S455和S456中对应于子地图的状态数据的示例性处理；

图18示出图15的流程图中的步骤S455和S456中对应于子地图的状态数据的示例性处理；

图19示出图15的流程图中的步骤S455和S456中对应于子地图的状态数据的示例性处理；

图20是用于通过将三维地图投影近似到二维地图上而在二维地图上将关注的子地图在空间上分割成规则间隔的序列的详细流程图；

图21示出用于通过将三维地图投影近似到二维地图上而在二维地图上将关注的子地图在空间上分割成规则间隔的示例性处理；

图22示出用于通过将三维地图投影近似到二维地图上而在二维地图上将关注的子地图在空间上分割成规则间隔的示例性处理；

图23是用于图10的流程图中的步骤S108的总体优化的序列的详细流程图；

图24示出束调整；

图25说明子地图的重叠区域的必要性；以及

图26说明子地图之间的重叠区域的必要性。

具体实施方式

下面对照附图描述根据本发明实施例的信息处理装置、信息处理方法和程序。将按照以下顺序进行描述。

1.SLAM处理的概要

2.子地图

3.信息处理装置的示例性配置及使用子地图的示例性处理

4.用于产生子地图的附加方法

1.SLAM处理概要

根据本发明实施例的信息处理装置基于在利用照相机拍摄的图像中包括的特征点信息来估计特征点的三维位置。例如通过同时定位和地图化(simultaneous localization and mapping，SLAM)来进行预测，其中同时标识照相机的位置(即，定位)和产生周围地图(即，地图化)。

具体来说，该信息处理装置在移动照相机时连续拍摄图像并获得在所拍摄的图像中包括的特征点的轨迹(即，跟踪信息)。然后该信息处理装置在移动立体处理中同时估计照相机的行进距离和特征点的三维位置。

如上所述，用于SLAM的方法包括采用卡尔曼滤波器的SLAM和采用扩展卡尔曼滤波器(Extended Kalman filter，EKF)的基于EKF的SLAM。将对照图1和其它图描述SLAM。在图1中所示的系统中，输入并分析利用单筒照相机(monocular camera)101拍摄的图像。照相机101在移动的同时连续拍摄图像。在SLAM中，基于特征点的行进距离(即，跟踪结果)在移动立体处理中同时地检测图像中的特征点的轨迹和估计照相机的行进距离以及特征点的三维位置。

在SLAM中使用图2中所示的状态数据。具体来说，基于表现为多维正态分布的“状态数据”而估计图1中所示的照相机101的行进距离和在由照相机101拍摄的图像中包括的特征点103的位置。

如图2中所示，该“状态数据”由代表用于拍摄图像的照相机和特征点的状态的状态值的多维正态分布数据构成。具体来说，该“状态数据”由包括均值矢量和方差-协方差矩阵的多维正态分布数据构成。均值矢量代表状态值，如照相机的位置、姿态、速度和角速度以及各特征点(P1至PN)的位置信息。方差-协方差矩阵包括例如照相机的位置、姿态、速度和角速度以及各特征点的位置信息等的固有状态值的方差(σ_aa)、以及对应于上述状态值当中的不同状态值的相关信息组合的协方差(σ_ab)。

该照相机在移动的同时拍摄图像并且连续地从拍摄的图像获得特征点跟踪信息(轨迹)。使用卡尔曼滤波器或扩展卡尔曼滤波器(EKF)更新状态数据以识别照相机的位置(即，定位)并产生(即，地图化)周围地图(即，环境地图)。单筒照相机适合于针孔照相机模型并且假定所有特征点都是静止的。

将对照图3和图4描述针孔照相机模型。利用针孔照相机模型，可以用以下等式1计算图像帧中的特征点的位置。

λ \tilde{m} = {AR}_{w} ({M - C}_{w})

(等式1)

将对照图3和图4描述等式1。等式1示出以下两个位置之间的关联性：对应于所拍摄的图像130中的对象131的点(m)的由照相机拍摄的图像平面上的像素位置132(即，由照相机坐标系统表示的位置)，以及世界坐标系统中的对象120的三维位置(M)121。

用照相机拍摄的图像平面上的像素位置132由照相机坐标系统表示。照相机坐标系统具有以照相机的焦点为原点C的二维平面Xc和Yc以及深度Zc。原点C随着照相机移动而移动。

对象120的三维位置(M)121由具有三个轴X、Y和Z且原点O固定而与照相机的移动无关的三轴世界坐标系统表示。表示不同坐标系统中的对象位置之间的关联性的等式被定义为针孔照相机模型。

如图4中所示，在等式1中，λ代表正规化参数，A代表照相机内部参数，Cw代表照相机位置，Rw代表照相机旋转矩阵。

下面的等式代表照相机在由齐次坐标系统表示的图像平面上的位置。

\tilde{m} = [\begin{matrix} m_{u} \\ m_{v} \\ 1 \end{matrix}]

拉姆达(λ)代表正规化参数，它被定义为满足下面等式的第三项。

照相机内部参数A包括以下值：f：焦距；西塔(θ)：图像轴的正交性(理想地为90度)；k_u：纵轴的标度(scale)(从三维位置的标度到二维图像的标度的变换)；k_v：横轴的标度(从三维位置的标度到二维图像的标度的变换)；以及(u₀，v₀)：图像中心位置。

在世界坐标系统中的特征点由位置M表示。照相机由位置Cw和姿态(即，旋转矩阵)Rw表示。照相机的焦点位置和图像中心由照相机内部参数A表示。利用这些参数，投影在“照相机的图像平面”上的“世界坐标系统中的特征点”的位置之间的关系可以由等式1表示。

如果由旋转矩阵Rw和平移矢量tw表示照相机的位置和姿态，则下面的等式2被满足。平移矢量tw和照相机拉置之间的关系由等式3表示。

λ \tilde{m} = {AR}_{w} M + t_{w}

(等式2)

t_w＝-R_w·C_w (等式3)

图1中所示的系统中的单筒照相机101适合于这种针孔照相机模型。该照相机在移动的同时拍摄图像并且连续地从所拍摄的图像获得特征点跟踪信息(轨迹)。使用卡尔曼滤波器或者扩展卡尔曼滤波器更新状态数据以识别照相机的位置(即，定位)并产生(即，地图化)周围地图(即，环境地图)。

下面描述卡尔曼滤波器和扩展卡尔曼滤波器。卡尔曼滤波器是顺序估计(预测)滤波器，用来顺序输入构成由照相机拍摄的图像的帧并且基于先前帧的状态(即，估计值)和从当前帧获得的观测值(即，特征点跟踪结果)获得要处理的帧的当前状态(即，估计值)。该“状态”对应于由图2中所示的(a)均值矢量和(b)方差-协方差矩阵构成的多维正态分布模型代表的状态数据。

下面示出与卡尔曼滤波器相关的等式。

预测模型：

(计算预测的“状态”的均值矢量)

(计算预测的“状态”的方差-协方差矩阵)

观测模型：

(计算观测的估计值

)

(计算估计值x和实际观测值z之间的差的均值矢量)

(计算差v_t的方差-协方差矩阵)

(计算卡尔曼增益)

(更新“状态”)

(更新“状态”的方差-协方差矩阵，其中I代表单位矩阵(unit matrix))

在上面的等式中，Ft代表预测模型(矩阵)，Ht代表观测模型(矩阵)。所述等式表示根据平均值为0且方差-协方差为Qt的多维正态分布模型的预测模型误差和根据平均值为0且方差-协方差为Rt的多维正态分布模型的观测模型误差。

^代表预测值。例如可以按照http://en.wikipedia.org/wiki/Kalman_fil ter#Examples中描述的方式设置各模型。

由于Ft和Ht是矩阵，所以卡尔曼滤波器局限于线性模型。为了解决该问题，开发了扩展卡尔曼滤波器(EKF)。EKF可以应用于非线性预测模型和观测模型。下面示出与EKF相关的等式。

预测模型：

(计算估计的“状态”的均值矢量)

(计算估计的“状态”的方差-协方差)

观测模型：

(计算观测的估计值

)

(计算估计值x和观测值z之间的差v)

(计算差v_t的方差-协方差矩阵)

(计算卡尔曼增益)

(更新“状态”)

(更新“状态”的方差-协方差矩阵，其中I代表单位矩阵)

在上面的等式中，F代表预测模型函数，H代表观测模型函数，

代表函数F的雅可比矩阵(Jacobian matrix)，

)代表函数H的雅可比矩阵，Qt代表(根据平均值为0且方差-协方差为Qt的多维正态分布模型的)预测模型误差，以及Rt代表(根据平均值为0且方差-协方差为Rt的多维正态分布模型的)观测模型误差。

图1中所示的照相机101在移动的同时拍摄图像，并连续地从拍摄的图像获得特征点跟踪信息(轨迹)。使用卡尔曼滤波器或扩展卡尔曼滤波器更新状态数据以识别照相机的位置(即，定位)并产生(即，地图化)周围地图(即，环境地图)。

如上面对照图2描述的，基于由图2中所示的多维正态分布表示的“状态数据”来估计图1中所示的照相机101的行进距离和在用照相机101拍摄的图像中包括的特征点103的位置。

“状态数据”由如图2中所示的代表用于拍摄图像的照相机的状态和特征点的状态值的多维正态分布数据构成。具体来说，“状态数据”由包括均值矢量和方差-协方差矩阵的多维正态分布数据构成。均值矢量代表状态值，如照相机的位置、姿态、速度和角速度以及各特征点(P1至PN)的位置信息。如图5A中所示，方差-协方差矩阵包括固有状态值(如照相机的位置、姿态、速度和角速度以及关于各特征点的位置信息)的方差、以及与上述状态值当中的不同状态值的相关信息组合相对应的协方差。

在图2和图5中所示的状态数据中，特征点#1至#N的位置由P1至PN表示。作为特征点#1至#N的位置的关于P1至PN的协方差数据被包括在方差-协方差矩阵中作为要素。

由于照相机在移动的同时连续拍摄图像，所以在所拍摄的图像中包括的特征点顺序地出现和消失。这意味着特征点#1至#N不一定被包括在所有帧中。因此，一些特征点被包括在图像帧F1中但是不被包括在随后的图像帧F2中，同时其他特征点被包括在图像帧F2中，但是不被包括在先前的图像帧F1中。

如图5B中所示，由于照相机151在沿着移动线152移动的同时连续拍摄图像，所以在所拍摄的图像中包括的特征点顺序地出现和消失。例如，当在时间tn拍摄的图像是图像拍摄区域153内的图像时，特征点A1至A3被包括在所拍摄的图像中。特征点B和C不被包括在所拍摄的图像中，但是被包括在先前的图像或随后的图像中。

在相关技术的基于EKF的SLAM中，使用在处理时获得的包括关于特征点的所有信息的“状态数据”。在SLAM中，例如，使用帧f01至fnn的图像，产生并更新包括在帧f01至fnn中检测到的全部特征点的状态数据。

因此，一些特征点被记录在要使用卡尔曼滤波器和EKF更新的状态数据中，但是不被包括在作为观测值输入的图像帧中。在此情况下，还更新在状态数据中包括的、不被包括在作为观测值的输入图像帧中的特征点信息。基于状态数据中包括的作为协方差数据的“用照相机拍摄的特征点”与“不是用照相机拍摄的特征点”之间的相关信息使用卡尔曼滤波器和EKF更新状态数据。

因此在SLAM中必须更新涉及多条特征点信息的数据，并且使用不是从当前图像获得的特征点的位置信息更新状态数据。这种更新处理增加了计算成本并导致效率低的处理。

将给出以下例子：其中，在当前拍摄的图像中包括的特征点(即，“出现在图像中的特征点的位置”)是正确的(即，估计值对应于实际值)而包括在当前拍摄的图像中的特征点(即，“照相机的位置和姿态以及不出现在图像中的特征点的位置”)是不正确的。在“状态数据”中不包括相关信息(即，方差-协方差矩阵的所有协方差分量为0)的模型中，只更新照相机位置。在“状态数据”中包括相关信息(即，方差-协方差矩阵的协方差分量不都为0)的模型中，根据照相机位置和姿态及相关信息的更新水平，还更新不出现在图像中的特征点的位置。

由于方差-协方差矩阵保持所有特征点和照相机之间的相关信息，所以特征点的数量越大，方差-协方差矩阵的尺寸越大。计算量关于特征点的数量以O(9n²)的数量级增加。尤其对于实时处理来说，方差-协方差矩阵的尺寸的增加是个较大的问题。因此，如果在状态数据中包括大量特征点信息，则处理时间和处理负荷增加，这是个问题。

2.子地图

为了解决这些问题，在本发明中将如图6中所示的代表要关于三维位置分析的整个区域的地图200分割成子地图211和221。每个子地图与(a)子地图的标识号(ID)和(b)在SLAM的计算中使用的状态数据相关联。

在本实施例中，M1、M2...被用作子地图的标识符(ID)。例如，在图6的下半部示出子地图M1 211和M2 221。对应于这些子地图的状态数据212和222类似于对照图2描述的状态数据，并且由代表拍摄图像的照相机和特征点的状态的状态值的多维正态分布数据构成。具体来说，“状态数据”由包括均值矢量和方差-协方差矩阵的多维正态分布数据构成。均值矢量代表状态值，如照相机的位置、姿态、速度和角速度以及各特征点(P1至PN)的位置信息。方差-协方差矩阵包括固有状态值的方差(σ_aa)，如照相机的位置、姿态、速度和角速度及各特征点的位置信息，以及对应于上述状态值当中的不同状态值的相关信息组合的协方差(σ_ab)。

注意，在对应于特定子地图的状态数据中包括的特征点信息只是该子地图中包括的特征点的信息。这意味着对应于图6中所示的子地图M1211的状态数据212由包括均值矢量和方差-协方差矩阵的多维正态分布数据构成。均值矢量代表照相机的位置、姿态、速度和角速度、子地图M1 211中的特征点a、b、c、d、e的位置信息及其状态值。

对应于子地图M2 221的状态数据222由包括均值矢量和方差-协方差矩阵的多维正态分布数据构成。均值矢量代表照相机的位置、姿态、速度和角速度、子地图M2 221中的特征点d、e、f、g、h的位置信息及其状态值。

对应于各子地图的状态数据不包括以下数据：只包括在其自身的子地图中的特征点和只包括在不同子地图中的那些特征点之间的相关信息(即，协方差数据)；以及与不包括在其自身的子地图中的特征点相关的均值矢量和方差-协方差数据。

例如，在子地图M1 211的状态数据212中不包括只包括在子地图M1 211中的特征点(a、b、c)和只包括在子地图M2 221中的特征点(f、g、h)之间的相关信息(即，协方差数据)。类似地，在子地图M2 221的状态数据222中不包括只包括在子地图M2 221中的特征点(f、g、h)和只包括在子地图M1 211中的特征点(a、b、c)之间的相关信息(即，协方差数据)。

关于各子地图211和221产生的“状态数据”212和222都由世界坐标系统表示。在SLAM中，通过只处理对应于特定子地图的“状态数据”，例如通过使用卡尔曼滤波器和扩展卡尔曼滤波器更新状态数据，减小了计算量。

该子地图是被产生作为用于执行SLAM的单位的区域，因此不对应于如图1中所示的用照相机101拍摄的图像帧。图7中示出用照相机101拍摄的图像帧和子地图之间的示例性关联性。

照相机101在从点A向点B移动的同时连续拍摄例如100帧f001至f100。从这些众多的图像帧中提取多个特征点并获得特征点的跟踪(轨迹)数据。

子地图M1 211是用于使用例如60个图像帧f001至f060的SLAM的区域。子地图M2221是用于使用例如60个图像帧f041至f100的SLAM的区域。如上所述，子地图M1、M2...是作为用于执行SLAM的单位而产生的区域。上述帧数量只是说明性的并且各子地图可以由任意数量的帧构成。

例如在单个子地图中包括的特征点的数量不大于预定的上限数量的条件下产生子地图区域。尽管图6和图7中只示出两个子地图，但是可以产生任意数量的子地图。在图8的例子中产生了四个子地图M1至M4。如图6至图8中所示，子地图被产生为相互重叠。在重叠区域中的特征点由各子地图的状态变量表示。这意味着重叠区域中的那些特征点保持两个或更多条位置信息。这两个或更多个特征点稍后将被优化，使得位置信息将收敛(图10的流程图中的“总体优化”)。稍后详细描述该处理。

3.信息处理装置的示例性配置和使用子地图的示例性处理

接下来描述本发明的信息处理装置的示例性配置和使用子地图的示例性处理。图9示出根据本发明的信息处理装置的示例性配置。利用本发明的信息处理装置300，基于用照相机301拍摄的图像数据获得特征点跟踪信息(即，轨迹)，使用卡尔曼滤波器或扩展卡尔曼滤波器更新状态数据以识别照相机的位置(即，定位)并产生(即，地图化)周围地图(即，环境地图)。照相机301适合于针孔照相机模型。

如图9中所示，在根据本发明实施例的信息处理装置300中，将用拍摄周围环境的照相机301拍摄的图像直接输入到装置300中。或者，将存储在拍摄图像存储部分302(即，数据库(DB)0)中的拍摄图像输入到装置300中。

子地图产生部分303将用来产生三维地图的要处理的区域(即，整个地图)分割成任意数量的子地图区域。用来产生三维地图的区域是如图9中所示的由照相机301拍摄的图像覆盖的区域。为了产生三维地图，可以实时地连续输入用照相机301拍摄的图像，或者可以从存储部分302获得该图像。

如果从该存储部分获得拍摄图像，则可以事先识别用来产生三维地图的要处理的区域(即，整个地图)并且可以将识别出的整个区域分割成两个或更多个子地图区域。可以任意地进行分割。例如，可以将整个区域分割成两个以提供初始的两个子地图。可以将整个区域分割成四个以提供四个子地图。或者，可以基于拍摄的图像帧特定数量或图像拍摄时间产生子地图。如上面对照图7描述的，子地图可以由覆盖有预定数量的图像帧如60帧的区域构成。或者，可以基于预定的照相机行进距离产生子地图。

当实时地连续输入用照相机301拍摄的图像时，子地图可以由覆盖有预定数量的图像帧的区域构成，或者可以被基于预定的照相机行进距离而产生。

子地图产生部分303输入用照相机301拍摄的图像或者从存储部分302输出以产生子地图。注意，可以最初产生单个地图，然后随着处理进行将其分割成两个或更多个子地图。例如，当特定的地图或者要处理的子地图中的特征点的数量达到预定的上限或更大时，可以将地图分割成两个。或者，特定地图或者要处理的子地图的空间区域达到预定尺寸或以上。稍后详细描述子地图的产生和分割。

信息处理装置300包括照相机位置和姿态检测部分304、特征点跟踪部分305、照相机位置和姿态存储部分306、特征点轨迹(跟踪)信息存储部分307、三维信息产生部分308和状态数据存储部分309。照相机位置和姿态检测部分304估计照相机的位置和姿态。照相机位置和姿态存储部分306(即，数据库(DB)1)存储由照相机位置和姿态检测部分304检测到的照相机位置和姿态信息。

特征点跟踪部分305跟踪在拍摄图像中包括的特征点。特征点轨迹(跟踪)信息存储部分307(即，数据库(DB)2)存储由特征点跟踪部分305检测到的特征点的轨迹信息。

三维信息产生部分308接收存储在照相机位置和姿态存储部分306中的照相机位置和姿态信息以及存储在特征点轨迹信息存储部分305中的特征点轨迹信息，并基于输入的信息计算照相机的位置和姿态以及特征点的三维位置。状态数据存储部分309存储自身(即，照相机)位置和包括特征点三维位置信息的对应于子地图的状态数据(存在概率分布数据)。

照相机位置和姿态检测部分304、特征点跟踪部分305和三维信息产生部分308基于由子地图产生部分303产生的子地图而执行其处理。

照相机301可以安装在移动机器人上或者由人类用户手动移动。这意味着照相机301的位置和姿态不固定。照相机301连续输入以变化的位置和姿态(即，从变化的视点)拍摄的图像帧(例如移动的图像)。如上所述，照相机301适合于针孔照相机模型。

照相机位置和姿态检测部分304基于从照相机301输入的图像中的特征点修正各帧的特征点的位置和照相机的位置。照相机位置和姿态检测部分304产生照相机位置(Cw)和照相机旋转矩阵(Rw)作为由照相机位置和姿态检测部分304确定的由世界坐标系统表示的估计的照相机的位置和姿态信息。然后照相机位置和姿态检测部分304将所产生的信息存储在照相机位置和姿态存储部分306中。

可以由例如作者为Andrew J.Davison的“Real-Time Simultaneous Localisation and Mapping with a Single Camera”(Proceedings of the 9^thInternational Conference on Computer Vision)中描述的方法执行这些处理。

对于照相机位置(Cw)和照相机旋转矩阵(Rw)中的每一个，照相机位置和姿态检测部分304根据正态分布产生具有存在概率分布的照相机位置和姿态信息，并将所产生的信息存储在照相机位置和姿态存储部分306中。

用照相机301拍摄的图像也被输入到特征点跟踪部分305中。特征点跟踪部分305获得从照相机301获得的帧图像中选择的局部区域(即，特征点)的帧之间的行进距离。例如，特征点跟踪部分305通过与先前帧的局部区域图像匹配的窗口获得特征点的帧之间的行进距离。

在特征点跟踪部分305中获得的特征点跟踪结果作为特征点跟踪数据而被记录在特征点轨迹(跟踪)信息存储部分307中。

图9中所示的照相机位置和姿态存储部分306和特征点轨迹(跟踪)信息存储部分307分别保持来自与由照相机位置和姿态检测部分304检测到的照相机位置和姿态信息以及由特征点跟踪部分305检测到的特征点轨迹信息相关的所有帧的输出结果。在此假定数据的帧时间被同步化。

三维信息产生部分308接收存储在照相机位置姿态存储部分306和特征点轨迹(跟踪)信息存储部分307中的照相机位置和姿态信息以及特征点轨迹(跟踪)信息，基于状态数据是否对应于子地图而执行SLAM，并估计照相机的位置和姿态(“定位”)和特征点的三维位置(地图化)。这些处理包括更新对应于子地图的状态数据，即，使用上述卡尔曼滤波器和扩展卡尔曼滤波器更新对应于子地图的状态数据。对应于子地图的状态数据被存储在状态数据存储部分309(即，数据库(DB)3)中并被根据需要而更新。

注意，在图9中所示的配置中，每个处理块可以配置为固有硬件或者可以执行对应于例如信息处理装置如PC中的各处理块的预定程序。例如，用于执行图10中所示的处理序列的程序可以被存储在存储器中，并且该程序可以在提供有作为程序执行部的CPU的控制部分中执行。稍后描述该处理序列。

将对照图10的流程图描述本发明的信息处理装置执行的处理序列。首先概述该处理，然后详细描述每个步骤。在每次输入图像帧时执行图10的流程图中的步骤S101至S107。假定作为步骤S108中的总体优化的单位的帧数量是L(例如，L＝60)。对每一输入帧重复步骤S101至S107的处理，直到处理帧的数量达到L。

在步骤S107中，当帧的数量达到L时，在步骤S108中执行总体优化。然后，在步骤S109中计数器复位到0并且程序返回到步骤S101，开始对后续的输入帧的处理。

图10中的存储部分(DB)320对应于图9中所示的四个存储部分DB0至DB3。这四个存储部分DB0至DB3各自对应于拍摄图像存储部分302(DB0)、照相机位置和姿态存储部分306(DB1)、特征点轨迹(跟踪)信息存储部分307(DB2)和状态数据存储部分309(DB3)。

概述图10的流程图的整个处理。

在步骤S101，选择关注的子地图。

在步骤S102，准备与关注的子地图相关的“状态数据”。

在步骤S103，初始化处理帧(只针对第一处理帧)。

在步骤S104，基于关注的子地图的状态数据更新状态数据。例如通过基于EKF的SLAM更新状态数据。尽管将在本实施例中描述使用EKF(扩展卡尔曼滤波器)的示例性处理，但是也可以采用卡尔曼滤波器。

在步骤S105，根据需要分割关注的子地图。在预定条件下，例如，当特征点的数量超过固定的上限数量时，将关注的子地图分割成两个。

在步骤S106，将处理的数量(即，处理帧的数量)的计数值更新(+1)。

在步骤S107，确定处理的数量(即，处理帧的数量)是否已经超过预定的处理数量L。

在步骤S108，进行总体优化。

在步骤S109，将计数值复位为0。

重复这些步骤的处理。

只对第一处理帧执行步骤S103的处理，其中如果需要则对SLAM处理执行初始化。在该初始化步骤中产生的第一子地图是“子地图M1”。

对预定数量的帧(即，L帧)的每一个进行总体优化(即，“束调整”)。进行总体优化以将子地图相互对准并且使重叠区域中的特征点的位置收敛。

下面详细描述图10的流程图的每个步骤。

步骤S101：关注地图的选择

现在参考图11的流程图，将描述图10的流程图的步骤S101中选择关注地图的详细序列。

在步骤S151中，产生包括至少一部分用来产生三维地图的要处理的区域的子地图。可以最初产生单个子地图，或者可以通过将要处理的区域分割成两个或更多个区域来产生两个或更多个子地图区域。

用来产生三维地图的区域是覆盖有如图9中所示的用照相机301拍摄的图像的区域。为了产生三维地图，用照相机301拍摄的图像可以实时地连续输入，或者可以从存储部分获得。

可以用各种方式产生子地图。例如，当已经识别出整个地图时，可以最初将整个地图视为单个子地图，或者，可以事先产生两个或更多个子地图。如果产生两个或更多个子地图，则可以任意地分割整个地图，例如基于照相机的行进距离、拍摄的帧数量和拍摄时间。

当实时地连续输入用照相机301拍摄的图像时，由通过连续输入的图像帧获得的区域构成单个子地图。在此情况下，最初产生单个子地图，并且子地图区域随着输入的图像帧的数量增加而增加。通过稍后详细描述的步骤S105中的地图分割将尺寸增加的子地图分割成两个子地图。

在图11的流程图中的步骤S152中，针对步骤S151中产生的每个子地图，扫描用照相机拍摄的特征点。基于初始设置信息或者来自使用卡尔曼滤波器或EKF的SLAM的估计结果并根据针孔照相机模型(见图3和图4)扫描照相机的位置和姿态。

接下来，在步骤S153，确定扫描的特征点属于哪个子地图并且将最大数量的特征点所属的子地图定义为关注的子地图。如果存在两个或更多个最大数量的特征点所属的子地图，则选择具有该最大数量(ID)的子地图作为关注的子地图。由此选择关注的子地图。

步骤S102：准备与关注的子地图相关的“状态数据”

接下来，对照图12的流程图描述图10的流程图中的步骤S102中的准备与关注的子地图相关的“状态数据”的处理。

首先，在步骤S201保存当前的关注子地图的标识符(ID)。保存当前的关注子地图的标识符(ID)是为了例如识别对应于当前处理帧的先前帧的关注子地图标识符(ID(编号))。

在步骤S202，判断当前帧的关注子地图是否不同于先前帧中的关注子地图。如果判断结果是肯定的，则在步骤S203中用先前帧中的关注子地图的“状态数据”的照相机信息重写(overwrite)当前帧的关注子地图的“状态数据”的照相机信息。

该“状态数据”由如图2中所示的代表用于拍摄图像的照相机的状态和特征点的状态值的多维正态分布数据构成。具体来说，该“状态数据”由包括均值矢量和方差-协方差矩阵的多维正态分布数据构成。均值矢量代表照相机的位置、姿态、速度和角速度及其状态值、各特征点(P1至PN)的位置信息。该状态数据被产生作为对应于子地图的状态数据，并且只包括每个子地图中包括的特征点信息作为与特征点相关的信息。

在步骤S203中，当处理新的子地图时，采用对应于先前帧的子地图的状态数据，该状态数据与包括在对应于该子地图的状态数据中的照相机信息(即，关于照相机的位置、姿态、速度和角速度的信息)相关。

图13中示出对应于该子地图的示例性状态数据。当前的状态数据中的照相机信息包括(a)均值矢量的数据区域321和(b)方差-协方差矩阵的数据区域331。对这些数据区域直接复制对应于先前帧的子地图的状态数据。

在步骤S203中，将状态数据中的方差-协方差矩阵中包括的照相机和特征点的所有协方差值设置为0。复位该数据是因为先前的子地图的照相机位置是基于与先前的子地图中的特征点之间的关系而获得的，因此不适用于当前的子地图。

图13中所示的方差-协方差矩阵的(b)数据区域332和333的所有协方差值被设置为0。

由此完成针对基于EKF的SLAM的“状态数据”的预处理。

步骤S104：使用关注的子地图的状态数据更新状态数据

在步骤S104中，使用例如卡尔曼滤波器和扩展卡尔曼滤波器基于关注的子地图的状态数据而更新状态数据。基于从输入帧获得的信息(即，关于照相机的位置、姿态、速度和角速度的信息以及关于各特征点的位置信息)，更新对应于关注的子地图的状态数据。

例如作者为Andrew J.Davison的“Real-Time Simultaneous Localisation and Mapping with a Single Camera”(Proceedings of the 9^thInternational Conference on Computer Vision，Ninth(2003))中描述了使用扩展卡尔曼滤波器的处理，即，基于EKF的SLAM。由本申请人提交的日本未审专利申请2008-304269也公开了基于EKF的SLAM。可以采用这些公开的方法。注意，在本发明中使用的状态数据(即，要更新的状态数据)是对应于子地图的状态数据。关于除了包括在子地图中的特征点之外的特征点的位置信息和相关信息不被包括在对应于该子地图的状态数据中。因此，数据量被减小以有助于非常高速度的计算。

如果在用于更新对应于子地图的状态数据的输入图像帧中检测到状态数据中未记录的新特征点，则将该新特征点添加到状态数据作为变量。

步骤S105：关注的子地图的分割

接下来，描述图10的流程图中的步骤S105中的关注的子地图的分割。

根据需要分割关注的子地图。在预定条件下分割当前要处理的关注的子地图。

下面描述两个示例性的分割处理。

(a)当包括在关注子地图中的特征点的数量达到预定的上限或以上时分割关注的子地图。

(b)通过三维地图到二维地图的投影近似将关注的子地图在空间上分割成二维地图上的规则间隔。

首先描述(a)的处理。

将对照图14的流程图描述分割处理的整个序列。

首先，在步骤S301中，对关注的子地图中特征点的总数进行计数。接下来，在步骤S302中，判断所计数的特征点的总数是否大于等于预定的上限数量N。

如果步骤S302中的判断结果是肯定的，则程序前进到步骤S303，分割当前要处理的关注的子地图。如果步骤S302中的判断结果是否定的，则结束处理而不分割关注的子地图。

例如根据照相机的条件确定预定的上限数量N。在本例子中，N＝125。

将对照图15的流程图描述图14的流程图中步骤S303的“分割关注的子地图”的详细序列。在图9中所示的信息处理装置300的子地图产生部分303中分割子地图。要分割的子地图是在图10的流程图中第一步骤S101中选择的关注的子地图。

首先，在步骤S451中，判断要处理的子地图(即，关注的子地图)是否具有任何与其它子地图重叠的区域。如果步骤S451中的判断结果是否定的，则程序前进到步骤S452。如果步骤S451中的判断结果是肯定的，则程序前进到步骤S453。

如果关注的子地图没有与其它子地图重叠的区域，则程序前进到步骤S452，在此得到关注的子地图中的特征点的组的重心，并将距该重心最远的特征点定义为点G。

如果关注的子地图具有任何与其它子地图重叠的区域，则程序前进到步骤S453，从关注的子地图中的特征点当中选择属于其它子地图的特征点，并将所选择的特征点的组的重心定义为点G。

执行这些处理。将对照图16描述这些处理。

图16示出用于(a)如果子地图之间没有重叠区域时分割子地图(步骤S452的处理)和(b)如果子地图之间有重叠区域时分割子地图(步骤S453的处理)的示例性处理。

在此要分割的关注子地图是子地图M4。

如图16A中所示，如果子地图之间没有重叠区域(步骤S452的处理)，则获得关注的子地图M4中的特征点的组的重心P1，并将距重心P1最远的特征点定义为点G1。

如图16B中所示，如果子地图之间有任何重叠区域(步骤S453的处理)，则从关注的子地图M4中的特征点当中选择属于重叠子地图M3的特征点，并将所选的特征点的组的重心定义为点G2。

在结束了这些处理之后，程序前进到步骤S454。

在步骤S454中，计算属于关注子地图的特征点和点G之间的距离。然后以距点G的距离的降序排列这些特征点，从而以如下方式设置对应于每个子地图的特征点：第一至第M特征点属于新添加的子地图；并且第(M+1)至第(2M)特征点在关注的子地图和新添加的子地图的重叠区域中。

在上述处理中产生新添加的子地图。

在一个例子中，M＝N×0.2，N代表关注的子地图中的特征点的数量。

当N＝125时，M＝25。在分割子地图时在新添加的子地图中设置50个特征点。在这50个特征点当中，25个特征点只属于新添加的子地图并且剩余的25个特征点属于新添加的子地图和关注的子地图的重叠区域。

图16中示出该处理。在(a)如果子地图之间没有重叠区域时分割子地图中，如图16A中所示产生新添加的子地图M5。在(b)如果子地图之间有任何重叠区域时分割子地图中，如图16B中所示设置新添加的子地图M5。

接下来，在步骤S455中，将还没有分割的关注子地图的“状态数据”复制到分割的新添加的子地图的“状态数据”。

最后，在步骤S456中，从关注的子地图和新添加的子地图的“状态数据”当中删除关于“不属于各子地图的特征点”的信息。以这种方式提供各子地图的状态数据。

将对照图17详细描述这些处理。图17示出对应于要分割的关注子地图M4的状态数据的复制。

图17A示出还没有分割的子地图M4和对应于子地图M4的状态数据351。如上面对照图2描述的，由包括均值矢量和方差-协方差矩阵的多维正态分布数据构成该状态数据。均值矢量代表状态值，例如照相机的位置、姿态、速度和角速度以及各特征点(P1至PN)的位置信息。

在步骤S455中，对应于图17A中所示的子地图M4的状态数据351被设置为如图17B中所示的对应于子地图M4的状态数据352和对应于子地图M5的状态数据353。对应于这些子地图的状态数据352和353是临时数据。

从对应于子地图M4的状态数据352和对应于子地图M5的状态数据353当中删除关于不属于子地图M4和M5的特征点的信息。

图18示出从状态数据中的均值矢量中删除信息的示例性处理。图19示出从方差-协方差矩阵中删除信息的示例性处理。在此情况下，从对应于子地图M4的状态数据352和对应于子地图M5的状态数据353中删除关于不属于子地图M4和M5的特征点的信息，然后更新并产生各子地图的最终状态数据。

通过该处理，完成图14的流程图中的步骤S303的关注子地图的分割。如上所述，图14的流程图中子地图的分割处理是在图10的流程图中的步骤S105中执行的关注子地图的示例性分割处理。

如上所述，根据需要，例如以下面的处理中的任一个，在图10的流程图中的步骤S105中分割关注的子地图。

(a)当包括在关注的子地图中的特征点的数量达到预定的上限数量或以上时分割关注的子地图。

(b)通过三维地图到二维地图的投影近似，在空间上将关注的子地图分割成二维地图上的规则间隔。

上面对照图14至图19描述的处理被包括在处理(a)中。

下面对照图20至26描述(b)处理。

图20中示出子地图分割处理的整个序列的流程图。

对照图20的流程图，描述用于通过三维地图到二维地图上的投影近似在空间上将关注的子地图分割成二维地图上的规则间隔的处理。

在开始图20的流程图的处理之前，如步骤S500的处理，确定要处理的三维空间的以下参数。

＊矢量k

＊矢量r₁

＊矢量r₂

＊分割中心O

＊距离d和e

将对照图21描述这些参数。

图21示出用来产生三维地图的空间(即，房间)。计算在该空间中设置的许多特征点的三维位置。

矢量k代表向二维地图的投影方向并且被适当地确定。在此，取图21中所示的房间的地图作为例子。如图21中所示，将垂直于地板表面的矢量设置为矢量k被认为是适当的。

如图21中所示，矢量r₁和r₂代表三维空间中二维地图的坐标轴矢量。矢量r1和r2被设置为满足以下条件。

(条件1)矢量k和通过投影变换产生的二维地图的坐标轴r₁和r₂彼此相互垂直。

(条件2)二维地图的坐标轴r1和r2彼此相互垂直。

适当地设置这些矢量以满足这些条件。

这些矢量k、r₁、r₂被表示为3×1矩阵。

分割中心O是如图22中所示的通过投影产生的二维地图中的分割基准点。

距离d是如图22中所示的在通过投影产生的二维地图中产生的子地图之间的距离。

距离e是如图22中所示的在通过投影产生的二维地图中产生的子地图的重叠区域的重叠宽度。

在图20的步骤S501中，属于三维空间的地图的所有特征点都被投影到二维地图。可以如图20中所示使用以下等式A实现投影变换。

[\begin{matrix} u \\ v \\ λ \end{matrix}] = {[\begin{matrix} r_{1} & r_{2} & k \end{matrix}]}^{T} \cdot [\begin{matrix} X \\ Y \\ Z \end{matrix}]

(等式A)

在等式A中，X、Y、Z代表特征点在三维空间中的位置，u和v代表特征点在二维地图上的位置，λ代表任意数量。

接下来，在步骤S502中，将投影到二维地图上的特征点分割成子地图。如图22中所示，以分割中心O作为中心并且以距离d和e将该地图分割成规则间隔。

图22包括由粗线示出的6个子地图M1至M6。在以分割中心O为分割基准点通过投影产生的二维地图中，以子地图间隔为d并且子地图的重叠区域中的重叠宽度为e产生6个子地图。该处理用于通过三维地图在二维地图上的投影近似而将关注的子地图在空间上分割成二维地图上的规则间隔。如果需要产生新的子地图，则用不同于现有子地图的标识符的新分配的标识符来标识新添加的子地图，例如，用通过将现在的标识符的最大编号加1获得的编号作标识符。

如上所述，图10的步骤S105中的地图分割成子地图是通过以下处理之一进行的：

(a)对照图14至图19描述的当包括在关注的子地图中的特征点的数量达到预定的上限数量或以上时分割关注的子地图；或者

(b)对照图20至图22描述的通过三维地图到二维地图的投影近似而在空间上将关注的子地图分割成二维地图上的规则间隔。

处理(a)和(b)可以结合在一起。

继续描述图10的流程图。在步骤S105中根据需要结束地图的分割之后，在步骤S106中更新输入帧的计数器。也就是说，该计数器被更新以对每个处理帧加1。

接下来，在步骤S107中，将作为用于步骤S108中的总体优化的预定单位的帧数量L与计数器值比较。如果计数器值小于L，则对每个输入帧重复步骤S101至S107的处理，直到处理帧达到L。L例如是60帧。

在步骤S107中，当帧数量达到L时，在步骤S108中执行总体优化。在步骤S109中，将计数器复位为0并且程序返回到步骤S101，开始对随后的输入帧的处理。

对照图23和图24描述步骤S108中的总体优化。对照图23的流程图描述步骤S108中的总体优化的详细序列。

通过束调整进行总体优化。在描述图23的流程图之前对照图24概述束调整。

在示例性的束调整中，如图24中所示，使用从在三个不同位置拍摄的图像411至413，以利用从拍摄的图像411至413检测到的特征点421至423来获得特征点的三维位置。如图24中所示的特征点421中，对于在两个或更多个图像中包括的特征点当中的对应的特征点的位置，连接各图像的拍摄点和特征点421的线(即，束)应在单个特征点421处交叉。

然而，例如照相机位置和图像中的特征点的位置信息等的信息不一定被准确地计算，并且由于各种因素而具有误差。这种误差应该被修正。特别地，进行修正使得连接特定的对应特征点的三维位置和照相机位置的线可以在该特征点处交叉。因此，需要修正已经计算出的照相机位置和特征点位置。作为束调整执行该处理。因此，使用通过束调整修正的特征点位置信息和照相机位置信息可以产生具有更高准确性的三维信息。可以利用相关技术的方法提供束调整，包括在作者为M.I.A.Lourakis和A.A.Argyros的“The Design and Implementation of a Generic Sparse Bundle Adjustment Software Package Based on the Levenberg-Marquardt Algorithm”(2004年8月)中公开的方法。

描述图23的流程图的每个步骤。由图9中所示的三维信息产生部分308执行该处理。在该处理中，输入以下信息：照相机位置和姿态的历史；最近的帧中的所有特征点位置；以及特征点跟踪结果(即，图像中特征点的位置和与照相机位置的历史相关的所有图像)。

从针对各帧执行的基于EKF的SLAM处理(即，图10的流程图的步骤S104中的处理)的结果获得照相机位置的历史和特征点跟踪结果。

首先，在步骤S601中，从特征点所属的子地图的状态数据获得最近的帧的特征点位置。从该特征点所属的子地图的状态数据的均值矢量(图2A)获得该特征点位置。对于属于两个或更多个子地图的特征点(图7的d和e)，从该特征点所属的各子地图的状态数据的均值矢量获得该特征点所属的多个子地图的特征点的位置信息，然后计算所获得的特征点位置的平均值。将所获得的特征点位置定义为初始值。

在步骤S602中，获得最近的照相机位置和姿态信息。可以从要处理的子地图的状态数据获得该信息。

在步骤S603中，通过对照图24描述的束调整执行总体优化。具体来说，获得在其中拍摄了相同特征点的两个或更多个图像帧，并且使这些图像帧中的该特征点的位置相互对应。

利用该处理，特征点位置被微调整。因此需要基于微调整的特征点位置信息而更新子地图的状态数据。具体来说，在步骤S604中，各特征点所属的子地图中的微调整的特征点位置被重写(overwrite)。属于两个或更多个子地图的特征点(图7中的d和e)利用优化的位置信息重写该特征点所属的各子地图的状态数据的均值矢量(图2A)。

在步骤S605中，重写最近的照相机位置和姿态。

以这种方式完成图10中所示的流程图的步骤S108中的总体优化。

由于其繁重的计算负荷，如图10的流程图中所示，每L个帧执行一次总体优化。

以这种方式计算产生本发明的三维地图所必需的特征点位置。

从以上说明可以理解，在本发明的处理中，用来产生三维地图的整个区域被分割成两个或更多个子地图，并且产生对应于各子地图的状态数据。使用卡尔曼滤波器或扩展卡尔曼滤波器(EKF)更新对应于该子地图的状态数据。利用这种结构，可以显著减小在更新状态数据期间的计算量并且实现有效的SLAM，即，特征点的三维位置的分析、照相机位置和姿态的计算以及三维环境地图的产生。

4.产生子地图的附加方法

在关于产生子地图的上述说明中，相邻的子地图优选地具有其中具有共同特征点的重叠区域。对照图25和图26描述其理由。

相邻的子地图优选地具有其中具有共同特征点的重叠区域的理由是该重叠区域提供该地图的更精确的总体优化(即，束调整)。

图25示出以重叠的方式排列相邻子地图的例子。星号标记代表特征点。照相机在沿着所示出的移动轨迹从左向右移动时在位置1a、1b、1c、2a、2b和2c处拍摄图像。

照相机在1a处拍摄子地图M1的区域的图像。

照相机在1b、1c、2a和2b处拍摄子地图M1和M2的重叠区域的图像。

照相机在2c处拍摄子地图M2的区域的图像。

连接各照相机位置1a、1b、1c、2a、2b、2c和用星号标记示出的特征点的直线代表特征点的束(跟踪结果)。

利用该结构，描述特征点451和452的束调整。例如，讨论属于子地图M1和M2二者的特征点451。存在连接特征点451和各照相机位置1b、1c和2a的三个束信息(即，跟踪结果)。通过如上所述的基于EKF的SLAM(图10的流程图中的步骤S104)产生连接特征点451和各照相机位置1b、1c和2a的束(即，跟踪信息)。仅将单个子地图输入到基于EKF的SLAM中。

由于当照相机在位置1b和1c处时关注的子地图是子地图M1，所以通过基于EKF的SLAM从子地图M1产生连接特征点451和各照相机位置1b和1c的束(即，跟踪信息)。

由于当照相机在位置2a处时关注的子地图是子地图M2，所以通过基于EKF的SLAM从子地图M2产生连接特征点451和照相机位置2a的束(即，跟踪信息)。

尽管从不同的子地图产生连接特征点451和各照相机位置1b、1c和2a的各个束，但是由于知道特征点451属于子地图M1和M2二者，所以该束在特征点451处相遇。

在束调整中可以使用在三个不同的照相机位置1b、1c和2a处的束信息，从而实现对照图24描述的束调整。

讨论属于子地图M1和M2的特征点452。存在连接特征点452和各照相机位置1c、2a和2b的三个束信息(即，跟踪结果)。通过如上所述的基于EKF的SLAM(图10的流程图中的步骤S104)产生连接特征点452和各照相机位置1c、2a和2b的束(即，跟踪信息)。只将单个子地图输入到基于EKF的SLAM中。

由于当照相机在位置1c处时关注的子地图是子地图M1，所以通过基于EKF的SLAM从子地图M1产生连接特征点452和照相机位置1c的束(即，跟踪信息)。

由于当照相机在位置2a和2b处时关注的子地图是子地图M2，所以通过基于EKF的SLAM从子地图M2产生连接特征点452和各照相机位置2a和2b的束(即，跟踪信息)。

尽管从不同的子地图产生连接特征点452和各照相机位置1c、2a和2b的各个束，但是由于知道特征点452属于子地图M1和M2二者，所以该束在特征点452处相遇。

在束调整中可以使用在三个不同的照相机位置1c、2a和2b处的束信息，从而实现对照图24描述的束调整。

与上述结构相反，图26示出以非重叠的方式产生具有与图25中所示相同的特征点排列的子地图的例子。与图25的例子相比较，在图26的例子中不提供连接特征点451和照相机位置2a或连接特征点452和照相机位置1c的束。

由于以下原因不提供连接特征点451和照相机位置2a的束。在束(即，跟踪结果)产生期间只输入单个子地图用于基于EKF的SLAM。当照相机在位置2a处时，关注的子地图是M2。在此，只属于子地图M1的特征点451不被输入用于基于EKF的SLAM。因此，由于不通过基于EKF的SLAM产生连接特征点451和照相机位置2a的束(即，跟踪结果)，所以在图26的例子中不提供该束。

类似地，由于以下原因不提供连接特征点452和照相机位置1c的束。在束(即，跟踪结果)产生期间只输入单个子地图用于基于EKF的SLAM。当照相机在位置1c处时，关注的子地图是M1。在此，只属于子地图M2的特征点452不被输入用于基于EKF的SLAM。因此，由于不通过基于EKF的SLAM产生连接特征点452和照相机位置1c的束(即，跟踪结果)，所以在图26的例子中不提供该束。

在图26中，当要执行子地图M1的特征点451的束调整时，可以只使用对应于子地图M1的在两个不同的照相机位置1b和1c处的束信息。

类似地，当要执行子地图M2的特征点452的束调整时，可以只使用对应于子地图M2的在两个不同的照相机位置2a和2b处的束信息。

图26中不提供代表子地图M1和M2之间的关联性的束。利用该结构，出现图24的总体优化独立地优化子地图M1和子地图M2的问题，因此，子地图的边界(例如，图26中的特征点451、特征点452、照相机位置1c和照相机位置2a的位置和姿态的关系)不经过束调整(即，总体优化)。

结果，在相邻子地图之间不提供重叠区域的一些情况下，在子地图的端部处的特征点不经过束调整。在此情况下，特征点的三维位置的精确度可能下降。因为这个原因，优选地，在子地图的产生期间在相邻子地图之间提供其中拍摄有共同特征点的重叠区域。

已经对照特定实施例描述了本发明。然而，本领域的技术人员应当理解，在不背离本发明范围的情况下可以做出各种变型和替换。只是为了说明的目的公开了本发明，并且不应该将发明理解为限制性的。因此本发明的范围只由所附权利要求确定。

以上说明中描述的一系列处理可以由硬件、软件或其复合结构来执行。当由软件执行该处理时，可以将其上记录有处理序列的程序安装在包含在专用硬件中的计算机中的存储器中。或者，可以将该程序安装在可以执行各种处理的通用计算机中。

可以将该程序事先记录在诸如硬盘或只读存储区(ROM)等的记录介质上。也可以将该程序临时地或永久地存储(即，记录)在诸如软盘、压缩盘只读存储器(CD-ROM)、磁光(MO)盘、数字多用途盘(DVD)、磁盘和半导体存储器等的可拆卸记录介质中。可以作为软件封装提供这种可拆卸记录介质。

该程序可以被从如上所述的可拆卸记录介质安装在计算机中。或者，可以通过诸如无线网络、局域网(LAN)和因特网等的网络将该程序从下载站点下载到计算机上。该计算机可以接收由此传送来的程序并且可以将该程序安装在诸如内部硬盘等的记录介质中。

在以上说明中描述的各种处理不一定以上述时序执行，而是可以根据执行该处理的装置的能力或者根据需要而被并行地或单独地执行。在此使用的术语“系统”描述多个装置的逻辑集合结构，这些装置不一定在单个壳体中。

本申请包含2009年8月21日在日本专利局提交的日本优先权专利申请2009-192091中公开的相关主题，其全部内容通过引用包含于此。

本领域的技术人员应该理解，根据设计要求和其它因素可能出现各种变型、组合、子组合和替换，只要所述变型、组合、子组合和替换在所附权利要求或其等同内容的范围之内即可。

Claims

1.一种信息处理装置，包括：

三维信息产生部分，用于通过连续接收利用在空间中移动的照相机从两个或更多个不同视点拍摄的图像并使用包括特征点跟踪信息的观测信息更新状态数据来获得照相机的位置和姿态或者特征点的三维位置，所述状态数据包括所述图像内的特征点的三维位置和所述照相机的位置和姿态信息；以及

子地图产生部分，用于通过分割要被计算三维位置的区域来产生子地图，

其中所述三维信息产生部分通过针对所述子地图产生部分产生的各个子地图而产生与不包括关于子地图区域外的特征点的信息的子地图相对应的状态数据并更新所产生的对应于子地图的状态数据，来获得所述照相机的位置和姿态或所述特征点的三维位置。

2.根据权利要求1所述的信息处理装置，其中所述三维信息产生部分与各个子地图相对应地产生多维正态分布数据作为对应于所述子地图的状态数据，并使用所述观测信息更新对应于所述子地图的多维正态分布数据，其中所述多维正态分布数据包括代表所述照相机的位置和姿态以及所述子地图中各个特征点的位置的均值矢量以及方差-协方差矩阵。

3.根据权利要求2所述的信息处理装置，其中所述方差-协方差矩阵包括如照相机的位置和姿态以及关于各个特征点的位置信息的固有状态值的方差和对应于所述状态值当中不同状态值的相关信息组合的协方差。

4.根据权利要求1至3中任一项所述的信息处理装置，其中所述三维信息产生部分使用卡尔曼滤波器或扩展卡尔曼滤波器(EKF)更新对应于所述子地图的状态数据。

5.根据权利要求1所述的信息处理装置，其中如果从先前的子地图到当前子地图地顺序地处理所述子地图，则所述三维信息产生部分使用在对应于所述先前的子地图的状态数据中包括的照相机信息而直接产生对应于所述当前子地图的状态数据。

6.根据权利要求1至5中任一项所述的信息处理装置，其中当子地图中包括的特征点的数量达到预定的上限数量N或以上时，所述子地图产生部分将所述子地图分割成其间形成重叠区域的两个子地图，这两个子地图具有至少一个共同的特征点。

7.根据权利要求6所述的信息处理装置，其中所述三维信息产生部分产生与通过分割所述子地图而产生的各个子地图相对应的状态数据，并通过从与尚未被分割的子地图相对应的状态数据当中删除关于未被包括在所述分割的各个子地图中的特征点的信息而产生与所述两个分割的子地图的每个相对应的状态数据。

8.根据权利要求1至5中任一项所述的信息处理装置，其中所述子地图产生部分将通过对要被计算三维位置的区域的投影变换而产生的二维平面分割成其间具有重叠区域的两个或更多个预定尺寸的子地图。

9.根据权利要求1所述的信息处理装置，其中所述三维信息产生部分通过束调整来修正所述特征点的位置。

10.根据权利要求1至9中任一项所述的信息处理装置，其中所述三维信息产生部分执行同时的定位和地图化(SLAM)，其中同时进行照相机的定位和周围地图(即，环境地图)的地图化。

11.一种在信息处理装置中执行的信息处理方法，该方法包括以下步骤：

由子地图产生部分通过分割要被计算三维位置的区域来产生子地图；以及

由三维信息产生部分产生三维信息，所述三维信息产生部分通过连续接收利用在空间中移动的照相机从两个或更多个不同视点拍摄的图像并使用包括特征点跟踪信息的观测信息更新状态数据来获得照相机的位置和姿态或者特征点的三维位置，所述状态数据包括所述图像内的特征点的三维位置和所述照相机的位置和姿态信息，

其中所述产生三维信息的步骤通过针对所述子地图产生部分产生的各个子地图而产生与不包括关于子地图区域外的特征点的信息的子地图相对应的状态数据并更新所产生的对应于子地图的状态数据，来获得所述照相机的位置和姿态或所述特征点的三维位置。

12.一种使信息处理装置处理信息的程序，该程序包括以下步骤：

使子地图产生部分通过分割要被计算三维位置的区域来产生子地图；以及

使三维信息产生部分通过以下方式来产生三维信息：通过连续接收利用在空间中移动的照相机从两个或更多个不同视点拍摄的图像并使用包括特征点跟踪信息的观测信息更新状态数据，来获得照相机的位置和姿态或者特征点的三维位置，所述状态数据包括所述图像内的特征点的三维位置和所述照相机的位置和姿态信息，