1.基于墙约束的房间自动分割方法，其特征在于，包括以下步骤：

步骤一：检测墙中心线；从原始点云中提取墙约束，用以切断房间之间的连接完成初始分割，同时将结果作为构建图的输入，具体包括：A)检测墙线，首先遍历点云中被分类为墙的点云面片并判断其是否与水平面垂直，对于每一个近似垂直于水平面墙面片，使用最小二乘方法将其拟合成平面，然后计算出拟合的墙平面与水平面形成的交线即墙线，该交线即为墙平面在水平面的投影，计算出点云中所有的墙线的集合；

B)生成双墙中心线，在原始墙线的集合中搜索成对的双墙，首先判断两个墙线是否平行，然后计算它们之间的距离，距离小于给定的墙厚度阈值时即为成对的双墙，计算出成对的双墙之间的中心线将其作为墙中心线；

C)生成外墙中心线，设定外墙的厚度t，则原始墙线W向两侧扩展t/2距离为候选墙中心线的位置，设为L1、L2，对于两个候选墙中心线，分别计算它们与原始墙线围成的矩形范围内包含点云的非空栅格的数量SUM1、SUM2，则外墙中心线的选择遵循以下规则：，其中，centerline为外墙中心线；

步骤二：检测墙中心线；对缺失的墙进行推导，获得鲁棒的墙线集合，具体包括：D)将集合中每一条墙中心线的两个端点标记为自由端点和非自由端点，自由端点和非自由端点按照如下规则进行定义：如果在端点的一定范围内不存在其他墙中心线，即不与其他墙段相邻，为自由端点，反之称之为非自由端点；

E)根据墙中心线之间的邻接关系对集合中的墙中心线进行分组，以剔除房间之外的其他墙线的干扰，将检测到的墙中心线集合分为了3组；

F)对墙中心线数量大于3的组合，按照一定的策略对组合中的自由端点生成虚拟墙线；

假设墙线之间都是彼此垂直的，从自由端点出发，生成该自由端点所在墙中心线的垂线，垂线将与其他包含自由端点的墙中心线所在的直线相交，选择与距离最近的包含自由端点的直线构成的交点作为虚拟墙线的终点；如果不存在这样的墙中心线，则不生成这段虚拟墙线；

步骤三：利用墙中心线对点云进行初始分割；具体包括：

G)对点云进行栅格化，将包含天花板平面点云的网格标记为已占用，未包含的网格标记为未占用，选取偏移距离范围内的点云作为天花板平面点云，偏移距离设置为低于面积最大的天花板点云面片的高度的0.2m范围；

H)去除房间与房间之间相连接的部分，使每个房间成为彼此孤立的区域；以墙中心线为中轴，将其两侧等距范围内的占用网格设置成未占用网格，去除范围的宽度不大于对应位置的墙的厚度使得每个房间区域被未占用网格包围，成为彼此孤立的区域；

I)在得到了点云在二维平面的投影之后，将其进一步识别为不同的房间；在生成的二值图像上执行基于标记的分水岭算法，将二值图像分割成不同的区域，每个区域赋予唯一的编号，将图像分割结果赋值给点云，完成对点云的初始标记，遍历图像的所有像素，建立图像标签与房间编号的映射关系，然后以每个像素对应的栅格为单位，将像素值相同的所有栅格内的点标记为同一房间，直至完成对整个点云的标记；

步骤4：基于图切的全局最优分割；具体包括：

J)构建图；从墙中心线的集合构造无限长的线的排列，将水平面上所有墙壁候选中心线的交点，产生平面图 ，其中， 的面F是建筑布局的区域即房间的一部分或外部区域，边 是可能的墙的部分， 是墙中心线的交点；定义平面图 的对偶图为，这里的每个顶点V对应图 的面F，用其中心表示，边E表示 中每个面的邻接关系，如果 中两个面相邻，则它们之间会有一条边；

K)定义多标签能量函数；目标函数包括两项：将标签分配给 面的一元成本和将标签对分配给相邻面的二元成本，一元成本提供房间或外部区域位置的提示，二元成本指导选择适当的边来分隔不同标记的面；对应于对偶图W中，公式化形式表示如下：令为标签的集合，这里 是初始分割中每个标记区域的标签， 为未分割区域的标签， 为外部标签，给定一元成本函数 产生将 分配给顶点 的成本，二元成本函数 产生将成对标签 分配给顶点 的成本，最小化标签成本表示如下：

L)定义一元成本函数；首先获得每个栅格内的所有点标签并将其保存到一个有序集合中，然后选择该有序集合的中值作为所在栅格的标签，然后通过计算面 内每个标签的栅格数量占面 内所有栅格数的比例来获得每个面 属于每个房间或外部区域的概率，那么一元损失函数定义为：，

其中，为加权因子， 为单元复合形面内标签为 的数量， 为面内总标签的数量，用来惩罚单元复合形的面积对于标签分配的影响；

M)定义二元成本函数；对于二元损失函数 ，假设了一个虚拟外部顶点与房间顶点相连接构成边，那么二元损失函数定义为：，

这里 为加权因子， 为墙中心线，表示边 ， 为了惩罚两个cell的公共

边的不同长度的影响。