一种基于Reeb图的立交桥三维建模方法

摘要

本发明公开了一种基于Reeb图的立交桥三维建模方法，包括：1、获取任意的立交桥三维的离散坐标；2、提取立交桥相互遮挡的结构并对这些结构进行投影；3、确定投影的散点的边界；4、进行Delaunay三角划分、5、在三角网的基础上进行Reeb图生成；6、判断Reeb图的关键点，分割Reeb图；7、填充Reeb图并拟合散点。本发明通过立交桥三维建模方法，来实现电子地图中立交桥等复杂路段的三维建模，使得电子地图中高效地表现出地图中各种复杂路段的道路信息，从而使得导航系统能够与电子地图相互衔接，更加丰富和完善当前电子地图中的道路信息，为用户出行提供更加准确的道路信息。

说明书

技术领域

本发明属于立交桥三维建模领域，具体的说是一种基于Reeb图的立交桥三维建模方法。

背景技术

近几年来，随着人们生活水平的提高，家庭的汽车拥有量逐步增多。在驾驶过程中，人们对于导航地图的需求和要求都越来越高，对于导航地图中最基本的就是要显示所驾驶的车辆在地图中的位置以及地图中各个道路结构的完整信息情况。目前一般的电子地图对于高速路网等比较简单的道路形式都有非常完善的建模方法，它们都能通过简单的平面建模方式将现实中的道路信息描述出来，再通过GPS导航技术对于车辆进行定位，并且把车辆的位置信息告诉驾驶员。但是目前的电子地图对于现实中立交桥这些复杂的道路路段的模型建立还不完善，不能再电子地图中体现立交桥等这些复杂路段的完整道路信息。

现在的电子地图中立交桥的模型一般采用平面模型进行表示，这种表现形式会给导航地图在向驾驶人发送位置信息，导致驾驶人不能够清晰地判断车辆位于立交桥中遮挡结构的哪个位置。此外在很多的立交桥的三维建模方法中都是将立交桥整体进行拟合，这种方式容易使得立交桥模型的结构与现实立交桥存在很大的差异，无法准确地描述立交桥的结构细节。

发明内容

本发明是为了克服现有技术存在的不足之处，提供一种基于Reeb图的立交桥三维建模方法，以期通过立交桥三维建模方法，来实现电子地图中立交桥等复杂路段的三维建模，使得在电子地图中高效地表现出地图中各种复杂路段的道路信息，从而使得导航系统能够与电子地图相互衔接，更加丰富和完善当前电子地图中的道路信息，为用户出行提供更加准确的道路信息。

本发明为解决技术问题采用如下技术方案：

本发明一种基于Reeb图的立交桥三维建模方法的特点是按如下步骤进行：

步骤1、立交桥桥面数据的提取：

通过机载LIDAR空间测量系统得到立交桥桥面的三维坐标点集合，记为W＝{w₁,w₂,…,w_n,…,w_N}，w_n表示第n个三维坐标点，并有w_n(x_n,y_n,z_n)；x_n表示第n个三维坐标点的x轴坐标，y_n表示第n个三维坐标点的y轴坐标，z_n表示第n个三维坐标点的z轴坐标，n＝1,2,…,N；

步骤2、立交桥桥面遮挡结构数据的提取：

步骤2.1、在三维坐标点集合W中寻找所有x轴坐标和y轴坐标都相同三维坐标点组成点集，记为W′＝{w′₁,w′₂,…,w′_i,…,w′_M}；w′_i表示第i个x轴坐标和y轴坐标都相同的三维坐标点集；并有w″_ij表示第i个三维坐标点集中第j个三维坐标点；i＝1,2,…,M；j＝1,2,…,K_i；M表示所有x轴坐标和y轴坐标相同都三维坐标点集的个数，K_i表示第i个三维坐标点集中x轴坐标和y轴坐标都相同三维坐标点的个数；

步骤2.2、初始化i＝1；初始化三维坐标点集W和三维坐标点集w′_i；

步骤2.3、从三维坐标点集W中获取z轴坐标值最大的点，记为w″_imax，并放入集合中；

步骤2.4、将w″_imax记为w″_i(s-1)；初始化变量s＝1；

步骤2.5、以w″_i(s-1)为球心，以α为半径建立第s个球形区域；

步骤2.6、从三维坐标点集合W中获取包含在第s个球形区域内的所有三维坐标点构成第s个球形区域坐标集，从所述第s个球形区域坐标集中获取一个次高坐标点，记为w″_is；次高坐标点w″_is的z轴坐标值小于等于w″_i(s-1)，但大于等于第s个球形区域坐标集中其他三维坐标点；

步骤2.7、判断次高坐标点w″_is是否已放入集合中，若已放入，则执行步骤2.9；否则判断次高坐标点w″_is存在于点集w′_i中且w″_is不是为点集w′_i中z轴坐标值最大的点，若存在，则执行步骤2.9；否则，将次高坐标点w″_is并放入集合中；

步骤2.8、将s+1赋值给s并返回步骤2.5；

步骤2.9、更新三维坐标点集合W和三维坐标集合w′_i；三维坐标点集合W为之后剩余的坐标集合；三维坐标集合w′_i为后剩余的坐标集合；将i+1赋值给i并返回步骤2.3，直到W中的坐标点个数为零为止；

步骤2.10、将集合中的所有三维坐标点投影得到二维坐标系中，得到二维坐标点集合，记为V＝{v₁,v₂,…,v_i,…,v_M}，v_i表示第i个集合中的所有三维坐标点投影得到的二维坐标点集合；并有v_i＝{v′_i1,v′_i2,…,v′_ip，…v′_iP}，v′_ip表示第i个二维坐标点集合v_i中第p个坐标点，p＝1,2,…,P；

步骤3、立交桥坐标集数据边界确定：

基于搜索盒边界算法确定第i个二维坐标点集合v_i的边界，记为U_i；

步骤4、立交桥坐标集数据的Delaunay三角剖分：

基于带内外边界约束的平面点集Delaunay三角剖分方法对第i个二维坐标点集合v_i进行处理，得到第i个带边界平面散点的三角剖分图；所述第i个带边界平面散点的三角剖分图中包含R_i个三角形；令第r个三角形的三个顶点记为A_r、B_r和C_r；

步骤5、立交桥坐标集合数据的Delaunay三角剖分图的Reeb图的转化：

步骤5.1、构造Morse函数：

利用式(1)构造Morse函数：

g(x)＝Geo(x,v′_imax)(1)

式(1)中，v′_imax为标准点，表示第i个二维坐标点集合v_i中的y轴坐标值最大的点；Geo(x,v′_imax)表示任意一个自变量x到标准点v′_imax的最短路径长度；

步骤5.2、选取第i个带边界二维散点的三角剖分图；从第i个带边界二维散点的三角剖分图中选取第r个三角形；第r个三角形中第n条边记为若第n条边上任意一点的坐标值发生了变化，则令否则

若选取的第r个三角形的第n条边则将第r个三角形的三个顶点A_r、B_r和C_r分别作为自变量x并代入式(1)中，从而获得第r个三角形的三个顶点的测地距离；并以所述第r个三角形的三个顶点中测地距离最小的顶点为起点，测地距离最大的顶点为终点；

若选取的第r个三角形存在第n条边则将第r个三角形和第n条边的Reeb图组成新的图形，并定义为第r个链；并将第r个链中第h个顶点r_h记为h＝1,2,…,Z；将第h个顶点作为自变量x并代入式(1)中，从而获得第r个链中第h个顶点r_h的测地距离；以所述第r个链的Z个顶点中测地距离最小的顶点为起点，测地距离最大的顶点为终点；

步骤5.3、通过Morse函数构建Reeb图：

判断所述第r个三角形或链中除起点和终点以外的顶点r_m的y轴坐标是否在起点的y轴坐标和终点的y轴坐标的之间，其中，m＝1,2,3…M；若是，则选取第r个三角形或链中除起点和终点以外的顶点r_m的x轴坐标值并利用式(2)得到第r个三角形或链中顶点r_m在Reeb图中的x轴坐标值y轴坐标值不变，记为顶点r′_m，从而得到第r个三角形或链中，除起点和终点以外的顶点在Reeb图中的坐标；

否则，则选取第r个三角形或链中，除起点和终点以外的顶点r_m的y轴坐标值并利用式(2)得到第r个三角形或链中顶点r_m在Reeb图中的y轴坐标值x轴坐标值不变，记为顶点r′_m；直至m＝M；从而得到第r个三角形或链中，除起点和终点以外的顶点在Reeb图中的坐标；

式(2)中，表示第r个三角形或链中除去起点和终点以外的顶点r_m的权重；表示第m个交点的权重；表示第m个交点和坐标值对应的坐标值；第m个交点为第r个三角形或链中起点和终点之间的边与经过除去起点和终点以外的顶点r_m且平行于x轴的直线所形成的点；

将第r个三角形或链中，相邻的顶点r′_m相连，从而得到第r个三角形或链的Reeb图；

步骤5.4、将r+1赋值给r并返回步骤5.2，直到r＝R_i为止，从而得到第i个二维坐标点集合v_i的Reeb图；

步骤5.5、将i+1赋值给i并返回步骤5.2，直到i＝M为止；从而得到二维坐标点集合V的Reeb图；

步骤6、将二维坐标点集合V的Reeb图在关键点处进行分割，并对分割后的坐标点集进行拟合，生成部分立交桥结曲面，再将拟合后的曲面在关键点处进行拼接，从而得到立交桥三维模型；其中，关键点为二维坐标点集合V的Reeb图中度不等于2的顶点。

与现有技术相比，本发明的有益效果在于：

1、本发明通过基于Reeb图的立交桥三维建模方法，通过将Reeb图对立交桥结构进行划分，在对各个部分进行拟合，得到完整的立交桥三维模型，更加准确地描述立交桥结构，从而使得导航系统能够与电子地图相互衔接，更加丰富和完善了当前的电子地图中道路信息，为用户出行提供更加准确的道路信息。

2、本发明中通过提取立交桥的遮挡结构，将立交桥的结构划分为三维的无遮挡结构，将复杂的机构进行的分离，将立交桥模型整体分解为结构单一的模块，大大降低了三维重建的技术难度，为复杂模型的建模提供了一种复杂结构如何进行分解的思路。

3、本发明中通过将遮挡结构的投影得到了二维的平面结构，投影的二维结构既包含了原始遮挡结构的拓扑关系，又能更加直观地表达遮挡结构的信息。

4、本发明中通过将Reeb图引入到立交桥的结构划分中，并通过基于三角网络的Reeb图生成拓扑关系结构，可以更加准确地将立交桥道路结构进行划分，并提高立交桥结构划分的效率和精度。

附图说明

图1为本发明流程图；

图2为本发明流程图细节图；

图3a为本发明实例中任意一个三角形的Reeb图生成过程；

图3b为本发明实例中任意一个链；

图3c为本发明实例中任意一个链的Reeb图生成过程；

图4a为本发明实例中任意一个三角形网络；

图4b为本发明实例中三角网络中一个三角形的Reeb图生成过程；

图4c为本发明实例中三角网络中两个相邻三角形的Reeb图生成过程；

图4d为本发明实例中三角网络中三个相邻三角形的Reeb图生成过程；

图4e为本发明实例中三角网络中四个相邻三角形的Reeb图生成过程；

图4f为本发明实例中一个三角网络的Reeb图生成过程。

具体实施方式

本实施例中，如图1所示，一种基于Reeb图的立交桥三维建模方法，是应用于任意的立交桥三维的离散坐标，并按如下步骤进行：

步骤1、立交桥桥面数据的提取：

通过机载LIDAR空间测量系统得到立交桥桥面的三维坐标点集合，记为W＝{w₁,w₂,…,w_n,…,w_N}，w_n表示第n个三维坐标点，并有w_n(x_n,y_n,z_n)；x_n表示第n个三维坐标点的x轴坐标，y_n表示第n个三维坐标点的y轴坐标，z_n表示第n个三维坐标点的z轴坐标，n＝1,2,…,N；

在立交桥遮挡结构提取前，将机载LIDAR空间测量系统得到的立交桥桥面的三维坐标集合的内容进行定义，便于在立交桥遮挡结构提取时对坐标集合的使用。

步骤2、立交桥桥面遮挡结构数据的提取：

步骤2.1、在三维坐标点集合W中寻找所有x轴坐标和y轴坐标都相同三维坐标点组成点集，记为W′＝{w′₁,w′₂,…,w′_i,…,w′_M}；w′_i表示第i个x轴坐标和y轴坐标都相同的三维坐标点集；并有；w″_ij表示第i个三维坐标点集中第j个三维坐标点；i＝1,2,…,M；j＝1,2,…,K_i；M表示所有x轴坐标和y轴坐标相同都三维坐标点集的个数，K_i表示第i个三维坐标点集中x轴坐标和y轴坐标都相同三维坐标点的个数；通过对于坐标集合中x轴坐标和y轴坐标都相同三维坐标点进行判断找到立交桥结构中存在遮挡的部分。

步骤2.2、初始化i＝1；初始化三维坐标点集W和三维坐标点集w′_i

步骤2.3、从三维坐标点集W中获取z轴坐标值最大的点，记为w_i″_max，并放入集合中；

步骤2.4、将w″_imax记为w″_i(s-1)；初始化变量s＝1；

步骤2.5、以w″_i(s-1)为球心，以α为半径建立第s个球形区域；实际选择半径时，由于机载LIDAR空间测量系统测量的数据的间隔为1m左右，所以在选择半径时α取1.5m，来保证球形判断区域中有包含了下一个待确定的点。

步骤2.6、从三维坐标点集合W中获取包含在第s个球形区域内的所有三维坐标点构成第s个球形区域坐标集，从所述第s个球形区域坐标集中获取一个次高坐标点，记为w″_is；次高坐标点w″_is的z轴坐标值小于等于w″_i(s-1)，但大于等于第s个球形区域坐标集中其他三维坐标点；通过确定一个次高坐标点的概念，保证了判断邻域过程的中下一个判断点的定义，确保了搜索邻域过程中的可实现性，为后面对次高坐标点的判断提供依据。

步骤2.7、次高点的选择决定了搜索邻域的方向，通过次高点可以按照一个从立交桥由上而下的方向进行立交桥遮挡结构的提取，将立交桥根据遮挡结构分为上下部分，从而对立交桥进行遮挡结构分离；判断次高坐标点w″_is是否已放入集合中，在遮挡结构下方会存在一半属于而另一半属于且i≠j；所以要先判断w″_is是否已经放入了集合中，确保只有集合包含该点；若已放入，则执行步骤2.9；否则判断次高坐标点w″_is存在于点集w′_i中且w″_is不是为点集w′_i中z轴坐标值最大的点；当高坐标点w″_is存在于点集w′_i中时，则次高点坐标w″_is的位置情况有两种，一种为点集w′_i中z轴坐标值最大的点，另一种为点集w′_i中z轴坐标值最大的点以外的点；若存在，则执行步骤2.9；否则，将次高坐标点w″_is并放入集合中；

步骤2.8、将s+1赋值给s并返回步骤2.5；

步骤2.9、更新三维坐标点集合W和三维坐标集合w′_i；三维坐标点集合W为之后剩余的坐标集合；三维坐标集合w′_i为后剩余的坐标集合；将i+1赋值给i并返回步骤2.3，直到W中的坐标点个数为零为止；通过更新三维坐标点集合W和三维坐标集合w′_i，可以将已经判断的点集剔除出去，方便后面的循环判断，减少了不必要的工作量，提高效率。

步骤2.10、将集合中的所有三维坐标点投影得到二维坐标系中，得到二维坐标点集合，记为V＝{v₁,v₂,…,v_i,…,v_M}，v_i表示第i个集合中的所有三维坐标点投影得到的二维坐标点集合；并有：v_i＝{v′_i1,v′_i2,…,v′_ip，…v′_iP}，v′_ip表示第i个二维坐标点集合v_i中第p个坐标点，p＝1,2,…,P；通过分别将集合中的点向xoy平面上投影，得到的平面二维坐标点集合，这样彻底将立交桥的遮挡结构进行分离。

步骤3、立交桥坐标集数据边界确定：

基于搜索盒边界算法确定第i个二维坐标点集合v_i的边界，记为U_i

步骤4、立交桥坐标集数据的Delaunay三角剖分：

基于带内外边界约束的平面点集Delaunay三角剖分方法对第i个二维坐标点集合v_i进行处理，得到第i个带边界平面散点的三角剖分图；第i个带边界平面散点的三角剖分图中包含R_i个三角形；令第r个三角形的三个顶点记为A_r、B_r和C_r；

步骤5、立交桥坐标集合数据的Delaunay三角剖分图的Reeb图的转化：如图2所示为Reeb图生成过程的细节流程图。

步骤5.1、构造Morse函数：

利用式(1)构造Morse函数：

g(x)＝Geo(x,v′_imax)(1)

式(1)中，v′_imax为标准点，表示第i个二维坐标点集合v_i中的y轴坐标值最大的点；Geo(x,v′_imax)表示任意一个自变量x到标准点v′_imax的最短路径长度；Morse函数是定义在二维流形上的一个函数；Morse理论是流形本身属性和Reeb图联系的桥梁；其能保证流形本身属性在Reeb图的提取过程中不会发生改变，这里的主要属性指的是流形本身固有的拓扑特性。一般Morse函数高度函数、拉普拉斯等式和测地距离来构造，采用测地距离构造Morse函数可以保证在沿水平方向分布的图形可以准确的提取其Reeb图；正因为Morse函数由测地距离构成则保证了在任何方向上都可以准确地表达图形的结构。Reeb图的结构为顶点和边的集合，它用来描述图形的拓扑结构。

步骤5.2、选取第i个带边界二维散点的三角剖分图；从第i个带边界二维散点的三角剖分图选取第r个三角形；第r个三角形中第n条边记为若第n条边上任意一点的坐标值发生了变化，则否则n＝1,2,3。如图3b和图3c所示为一条边的三角形的Reeb图生成过程；

若选取的第r个三角形的第n条边如图3a为选取的第r个三角形的n条边第r个三角形的Reeb图生成过程；将第r个三角形的三个顶点A_r、B_r和C_r分别作为自变量x并代入式(1)中，从而获得第r个三角形的三个顶点的测地距离；并以所述第r个三角形的三个顶点中测地距离最小的顶点为起点，测地距离最大的顶点为终点；

若选取的第r个三角形存在第n条边将第r个三角形和的边的Reeb图组成新的图形，并定义为第r个链，链中存在边且是三角形的边与Reeb图形构成。如图3b细实线为链；则将第r个链中的顶点r_h记为其中r_h为链中第h个顶点，h＝1,2,…,Z；将作为自变量x并代入式(1)中，从而获得第r个链顶点r_h的测地距离：以第r个链的Z个顶点中测地距离最小的顶点为起点，测地距离最大的顶点为终点；

步骤5.3、通过Morse函数构建Reeb图：

如图4a到图4f为一个实例中的部分三角网生成Reeb图的过程；判断第r个三角形或链中的顶点，其中除去起点和终点以外的顶点r_m的y轴坐标是否在起点的y轴坐标和终点的y轴坐标的之间，其中，m＝1,2,3…M；通过判断起点和终点以外的点在起点和终点之间的位置关系可以确定该三角形或链的图形是沿水平拓展还是沿垂直方向拓展，由此确定在公式中的坐标含义；若是，则选取第r个三角形或链中除去起点和终点以外的顶点r_m的x轴坐标值并利用式(2)得到第r个三角形或链中顶点r_m在Reeb图中的x轴坐标值y轴坐标值不变，记为顶点r′_m；从而得到第r个三角形或链中除去起点和终点以外的顶点在Reeb图中的坐标；

否则，则选取第r个三角形或链中除去起点和终点以外的顶点r_m的y轴坐标值并利用式(2)得到第r个三角形或链中顶点r_m在Reeb图中的y轴坐标值x轴坐标值不变，记为顶点r′_m；直至m＝M；从而得到第r个三角形或链中，除去起点和终点以外的顶点在Reeb图中的坐标；

式(2)中，表示第r个三角形或链中除去起点和终点以外的顶点r_m的权重；表示第m个交点的权重；表示第m个交点和坐标值对应的坐标值；第m个交点为第r个三角形或链中起点和终点之间的边与经过除去起点和终点以外的顶点r_m且平行于x轴的直线所形成的点；如图3-a所示，第m个交点为虚线与起点和终点之间的边的交点。

将第r个三角形或链中，相邻的顶点r′_m相连，从而得到第r个三角形或链的Reeb图；

图3b到图3c所示为第r个链生成Reeb图的过程。黑色粗实线为生成后的Reeb图。

步骤5.4、将r+1赋值给r并返回步骤5.2，直到r＝R_i为止，从而得到第i个二维坐标点集合v_i的Reeb图；

步骤5.5、将i+1赋值给i并返回步骤5.2，直到i＝M为止；从而得到二维坐标点集合V的Reeb图；图4a为选取第i个带边界二维散点的三角剖分图中的一部分三角网络，图4b为在图4a的基础上选择一个三角形进行Reeb图生成，图4c为图4b基础上在选取一个三角形，选取三角形中的边与图4b中的Reeb图组成链，并通过公式(2)生成链的Reeb图。图4d、图4c和图4f重复图4c的过程，完成这个三角网络的Reeb图生成。

步骤6、将二维坐标点集合V的Reeb图在关键点处进行分割，并对分割后的坐标点集进行拟合，生成部分立交桥结曲面，再将拟合后的曲面在关键点处进行拼接，从而得到立交桥三维模型；其中，关键点为二维坐标点集合V的Reeb图中度不等于2的顶点。