Optimized method of building underwater terrain navigation database based on triangular irregular network

WANG Li-hui, GAO Xian-zhi, LIANG Bing-bing, YU Le, ZHU Xue-fen

(1. Key Laboratory of micro-inertial instrument and advanced navigation technology, Ministry of education, School of

Optimized method of building underwater terrain navigation database based on triangular irregular network

WANG Li-hui1, GAO Xian-zhi2, LIANG Bing-bing3, YU Le1, ZHU Xue-fen1

(1. Key Laboratory of micro-inertial instrument and advanced navigation technology, Ministry of education, School of

instrument science and engineering, Southeast University, Nanjin 210096, China; 2. Army representative of some institute in Tianjin, Tianjin 300131, China; 3. Science and Technology on Space Physics Laboratory, Beijing 100076, China)

In view that using a regular grid model to build a underwater terrain navigation database has the problems of low accuracy and low efficiency, an optimized method is proposed to build an underwater terrain navigation database based on a triangular irregular network. Convex hulls are calculated for each block of data points with latitude and longitude coordinates by using a divide and conquer algorithm. Then, according to the improved convex hull algorithm, the sub-triangular irregular networks are formed by adding nonconvex hull data points to the convex hulls. Adjacent convex shell blocks are combined by using an improved algorithm for triangulation, and the terrain navigation database is completed by merging and optimizing the sub-triangulations. Simulation results show that building a terrain navigation database using the construction methods associated with a triangular irregular network has such advantages as high efficiency, high accuracy, and the ability to adjust resolution.

underwater terrain navigation database; triangular irregular network; convex hull algorithm; divide and conquer algorithm

Most autonomous underwater vehicles (AUV) navigation systems are based on inertial navigation, inertial navigation systems drift off with time, even when velocity aiding is used. In order to allow extensive submerged operations, additional position fixes are needed. In order to increase the autonomy of the vehicleand avoid costly pre-deployment of underwater transponders, terrain-matching navigation is a favorable alternative[1]. The positioning accuracy of an inertia and terrain-matching navigation system depends on the resolution and accuracy of the terrain map database[2-4]. Two commonly used models for building a terrain navigation map database are the regular grid model and the triangular irregular network model. The regular grid model describes the terrain using a rectangular grid with equal spaces, interpolating position points among scattered data points. The interpolated position elevation points are obtained using a bilinear interpolation of four grid endpoints. Methods of building a terrain navigation database with a regular grid are simple[5-6], easy to store, and become mainstream models[3,7]. However, the methods are low in accuracy for describing complex terrain, and the number of data points cannot be adjusted because of topographic changes, which results in data redundancy issues.

A triangular irregular network (TIN) model describes the terrain by connecting the scattered data points with an irregular triangular unit and solves the problems described above. Sub-triangular networks are formed by using data points directly, without interpolation, and elevation points are obtained by interpolating within the triangular unit. Sub-triangular networks are then combined to generate the whole triangular mesh based on a triangulation split merge algorithm. The triangular irregular network model can adjust the density of the data points according to the change in the intensity of the terrain and is suitable for describing any terrain, especially where there are severe changes in the terrain. Relative to the regular grid model, the triangular irregular network model has higher accuracy and greater efficiency.

1 Triangular irregular network algorithm

TIN does not build cross-triangulations. The TIN connects the scattered data points with irregular triangular units through the topology[8,9]. The triangular irregular network terrain model can represent linear characteristics and the superposition of an arbitrary shape for the border region. The TIN is easy to update and can be adapted to a variety of data densities. The four main methods for modeling the triangular irregular network include triangulation growth, divide and conquer algorithms, a point-by-point insertion method, and split merge algorithms. The triangulation growth method has low efficiency, is computationally complex, and is rarely used. The incremental insertion algorithm is simple but low in efficiency. A divide and conquer algorithm must be recursive and have a high spatial complexity. A split merge algorithm combines the advantages of the divide and conquer algorithm with those of the point insertion algorithm to simply describe the map database with high precision.

Convex hull can be seen as a set of boundary points, which is defined as follows: Set S is n-dimensional space consisting of a collection of k points. Convex hull of S is defined as Conv(S), which is described by the following equation:

Convex hull means minimum convex area including a planar point set, and connection of any two points within the convex area. The convex hull has received considerable attention in computational geometry. (T. M. Chan, 1996) has presented optimal convex hull algorithms in two and three dimensions, and (Zhang Xianquan, 2006) has presented a kind of convex hull algorithm with high efficiency[8,10]. The triangular irregular network is generated in two steps. First, the initial triangulation is generated by using the convex hull as the initial polygon. Second, the remaining points are inserted into the initial triangulation. TIN contains a convex hull algorithm solving process, a split and merge process and a space optimization algorithm optimization process. The procedure is as follows:

Step 1.The source data are divided according to the latitude and longitude coordinates.

Step 2.The convex hulls in each data block are calculated.

Step 3.Sub-block triangulations are formed by adding nonconvex hull data.

Step 4.The whole triangulation is formed by merging with sub-blocks of adjacent convex hulls.

Fig.1 Process of constructing the triangulation

Fig.1 shows the process of constructing the triangulation. Data points were divided into four blocks,and sub-triangulation grids were constructed. The whole triangulation was formed by merging with sub-blocks of adjacent convex hulls.

The procedure of algorithm in three dimensions is as follows[10]:

Algorithm Hull3D(P, m, H), where P in Euclidean space E3, 4＜m＜n, and H ＞1.

1. partition P into subsets P1,....,P[n/m]each of size at most m

2. F, Q←{f0}, where f0is some initial facet of conv(P)

3. for k= 1, …, 2H-4, do

4. if Q = 0, then return F

5. pick some f in Q and set Q←Q -{f}

6. let ejbe the edges of f (j = 1, 2, 3)

7. for j = 1, 2, 3 do

8. for i = 1 … [n/m] do

9. compute the point qiin Pithat maximizes the angle between f and conv(ej∪ {qi}) by searching the hierarchy of conv(Pi)

10. pj← the point q from {ql,…,q[n/m]} that maximizes

the angle between f and conv(ej∪ {q})

11. fj←conv(ej∪ {pj})

12. if fjnot in F then

13. F ← F ∪ {fj}, Q←Q ∪ { fj}

14. return incomplete

2 Fast hull algorithm and improvement

The convex hull algorithm mainly includes the following steps: striking of convex hull points, forming convex hull sides[9,11]. The convex hull is a minimum convex polygon containing limited data points. The fast hull algorithm is now a mainstream convex hull algorithm[10,12]. The process is shown in Fig.2 and is described below. In Fig.2(a), the left and right extreme points (p1and p2) are obtained from a set of data points, and all of the points are divided into two parts by the vector linep1p2. In Fig.2(b), the point in the right section (pr_0) farthest from vector p1p2 is obtained, and all of the points within the triangular unit p1p2pr_0 are deleted, as these points cannot be a convex hull. The amount of computation to determine the points of the convex hull are thereby reduced. In Fig.2(c), the points in the right section (pr_1_1 and pr_1_2) farthest from the vectors of p1pr_0 and pr_0p2 are obtained. By iteration, all convex hull points to the right of the vector p1p2 are obtained. Similarly, all convex hull points to the left of the vector p1p2 are obtained in the right calculation process. Finally, all convex hull points are obtained.

The fast hull algorithm has several shortcomings such as low computational efficiency, consumption of processor memory, and great spatial complexity. To improve the efficiency of the algorithm, the convex hull algorithm needs to be improved. The proposed improvements to the fast hull algorithm are summarized below. The process is expressed in Fig.3 and described as follows. In Fig.3(a), the left and right extreme points of P1 and P2 are obtained from a set of data points in the same manner as Fig.3. In Fig.3(b), the farthest point in the right section (Pr_0) from vector P1P2 is obtained. The points pr_1_1 and pr_1_2 form the maximum angle with vector P1P2. This process is equivalent to computing the two-step process simultaneously for the traditional fast hull algorithm. All points within the quadrilateral p1.pr_1_1.pr_0.p2 are deleted because these points cannot be a convex hull, and the amount of computation required to determine the point of the convex hull is reduced. The computing process is then repeated by replacing p1pr_1_1, pr_1_1pr_0, pr_0pr_1_2, pr_1_2p2 with p1p2. All convex hull points to the right of the vector p1p2 are obtained. Similarly to the calculation process on the right, all convex hull points to the left of the vector p1p2 are obtained. Finally, all convex hull points are obtained. Obviously, the efficiency of the improved fast hull algorithm is significantly higher than the efficiency of the conventional fast hull algorithm.

Fig.2 Steps of the fast convex hull algorithm

Fig.3 Improved fast convex hull algorithm

3 Split merge algorithms and global space optimization of triangular irregular network

In the split merge algorithm, data points according to the latitude and longitude coordinates are divided into subsets of data points, and the convex hulls of the subset are computed based on the improved fast hull algorithm. Sub-block triangulations are then constructed with the convex hulls, and finally, sub-block triangulations are combined to form a complete triangulation. The process of the split merge algorithm can be expressed in Fig.4 and includes the following steps. The procedure is as follows:

Step 1. The maximum value of the latitude coordinate data points (named y_max) and the minimum value of the latitude coordinate data points (named y_min) are obtained in coordinate data points.

Step 2. The width of the data interval along the latitude direction is set.

Step 3. The index numbers for the data block are sorted. Step 4. Sub-block triangulations are constructed with the convex hulls in data blocks.

Step 5. The top line and the bottom line of the convex hulls in adjacent sub-blocks are obtained, and all of the data blocks are merged recursively.

The convex hull problem has received considerable attention in computational geometry. Given a set P of n points in the Euclidean plane E2or Euclidean space E3, we consider the problem of computing the convex hull of P, cony(P), which is defined as the smallest convex set containing P[10]. By using the convex hull algorithm and the split merge algorithm, the entire triangular irregular network has been constructed. The topography of the adjacent points of the terrain are similar. However, the triangulation structure is calculated by the algorithm, and the topographical features calculated may not be consistent with the actual situation.

The idea of the optimization is to use the standard deviation of the interior space angle. In a tetrahedron consisting of two adjacent triangular irregular networks, the standard difference of the interior angle in the two triangular units should be lower than the standard difference of the interior angle in the two new triangular units after the exchange of the tetrahedral diagonal. The process of global space optimization of the triangular irregular network can be expressed in Fig.5.

In Fig.5(a), the two triangular units are formed with ABC and BCD. We calculate the standard difference of the interior angle in the two triangular units, with a value of Σ(ABC_BCD). In Fig.5(b), we exchange the tetrahedral diagonal of BC to AD, and there are two new triangular units with ABD and ACD. We calculate the standard difference of the interior angle in the two triangular units with the value of Σ(ABD_ACD). We decide to choose the tetrahedral diagonal of BC or AD by comparing the values of Σ(ABC_BCD) and Σ(ABD_ACD).

Fig.4 Process of the split merge algorithm

Fig.5 Process of global space optimization of the TIN

4 Simulation results

We select a set of terrain elevation data containing longitude, latitude and elevation, and then form a set of random discrete terrain data after sampling. According to the set of random discrete terrain data, we build a three-dimensional terrain map based on the triangular irregular network methods, as shown in Fig. 6. Then we build a three-dimensional terrain map based on the optimized triangular irregular network methods, as shown in Fig.7. Simulation results show that the optimi-zation of the triangular irregular network can improve the accuracy of triangulation of the terrain and avoid terrain distortion.

Fig.6 3D terrain map based on the TIN

Fig.7 3D terrain map based on the optimized TIN

5 Conclusions

As triangular elements are capable of expressing any terrain, the triangular irregular network terrain model presented in this paper can represent linear characteristics and superposition of the arbitrary shape of the border region. Particularly when the terrain changes severely, the irregular triangular network construction methods can adjust the density of data points in the terrain navigation database according to changes in the intensity of the terrain. The fast hull algorithm enhances the suitability after the improvement. The merge algorithm avoids a cross-segment in the sub-block triangulation merger process by using selection methods to determine the cross. By optimizing triangulation through space optimization rules, the triangular space terrain database units are selected, and the accuracy of the topographic features is improved. Simulation results show that the optimized construction methods of the terrain navigation database based on the irregular triangulation will not only improve the accuracy of triangulation of the terrain but will also avoid terrain distortion and meet the needs of a complex terrain.

[1] Anonsen K B, Hagen O K. An analysis of real-time terrain aided navigation results from a HUGIN AUV[C]//IEEE Oceans 2010 Conference. Seattle, WA, USA, 2010.

[2] Anonsen H K, Mandt M. The HUGIN real-time terrain navigation system[C]//IEEE Oceans 2010 Conference. Seattle, WA, USA, 2010.

[3] Deronde B, Houthuys R, Debruyn W. Use of airborne hyperspectral data and laserscan data to study beach morphodynamics along the Belgian coast[J]. Journal of Coastal Research, 2006, 22(5): 1108-1117.

[4] Nguyen V T. Building TIN (triangular irregular network) problem in Topology model[C]//2010 International Conference on Machine Learning and Cybernetics. 2010.

[5] Nam N M, Kiem H V, Nam N V. A fast algorithm for constructing constrained delaunay triangulation[C]//International Conference on Computing and Communication Technologies. 2009.

[6] Nordlund P J, Gustafsson F. Marginalized particle filter for accurate and reliable terrain-aided navigation[J]. Aerospace and Electronic Systems, 2009, 45(4): 1385-1399.

[7] Liu Yong-xue, Li Man-chun, Mao Liang, et al. Toward a method of constructing tidal flat digital elevation models with MODIS and medium-resolution satellite images[J]. Journal of Coastal Research, 2013, 29(2): 438-448.

[8] Zhang Xian-quan, Liu Lina. A convex hull algorithm based on convex polygon[J]. Computer Science, 2006, 33(9): 218-221.

张显全, 刘丽娜, 唐振军. 基于凸多边形的凸壳算法[J]. 计算机科学, 2006, 33(9): 218-221.

[9] Wu Xiao-bo, Wang Shi-xing, Xiao Chun-sheng. A new study of Delaunay triangulation creation[J]. Acta Geodaetica Acrtographica Sinica, 1999, 28(1): 28-35.

武晓波, 王世新, 肖春生. Delaunay三角网的生成算法研究[J]. 测绘学报, 1999, 28(1): 30-37.

[10] Chan T M. Optimal output-sensitive convex hull algorithms in two and three dimensions[J]. Geometry, 1996, 16(1): 361-368.

[11] Shi Min. Research and application development of Delaunay triangulation algorithm[D]. Huazhong University of Science, 2011.

施敏. Delaunay三角网算法研究和应用开发[D]. 华中科技大学硕士学位论文, 2011.

[12] Miccadei E, Mascioli F, Piacentini T, Ricci F. Geomorphological features of coastal dunes along the central adriatic coast[J]. Journal of Coastal Research, 2011, 27(6): 1122-1136.

[13] Anonsen K B, Hallingstad O. Terrain aided underwater navigation using point mass and particle filters[C]//IEEE Position, Location and Navigation Symposium. 2006: 1027-1035.

[14] Whyte H D, Bailey T. Simultaneous localization and mapping (SLAM): Part I - The essential algorithms[J]. IEEE Robotics and Automation Magazine, 2006, 13(2): 99-110.

[15] Bagnell J A, Bradley D, Silver D. Learning for autonomous navigation[J]. Robotics & Automation Magazine, 2010, 17(2): 74-84.

基于不规则三角网的水下地形导航数据库构建方法的优化

王立辉1，高贤志2，梁冰冰3，余 乐1，祝雪芬1
（1. 东南大学 仪器科学与工程学院 微惯性仪表与先进导航技术教育部重点实验室，南京 210096；2. 天津某所军事代表，天津 300131；3. 空间物理重点实验室，北京 100076）

采用规则格网模型构建地形导航数据库时，存在精度较低以及效率较低的问题。为了优化地形导航数据库构建方法，提出了一种基于不规则三角网的地形导航数据库构建方法。基于分割合并法对源数据点按经纬度坐标进行分割，分别求出每个数据块数据点的凸壳，然后依据改进的凸壳算法逐点加入非凸壳数据点形成子块三角网，用改进的三角网合并算法对相邻的凸壳子块进行合并，完成子三角网的优化合并形成完整的地形导航数据库。仿真结果表明基于不规则三角网的地形导航数据库构建方法具有效率高、精度高、分辨率可调整的优点。

水下地形导航数据库；不规则三角格网；凸壳算法；分割合并算法

U666.1

A

1005-6734(2015)03-0345-05

2015-02-25；

2015-06-12

国家自然科学基金资助项目（61203192，51477028，51405203）；中央高校基本科研业务费专项资金资助（东南大学优秀青年教师项目-2242013R30016）；船舶工业预研基金（13J3.8.4）

王立辉（1979—），男，博士生导师，副教授，从事导航、光学传感等方面的应用研究。E-mail：wlhseu@163.com

10.13695/j.cnki.12-1222/o3.2015.03.012