DEM Construction from Contour lines based on Regional Optimum Control Dunjiang Song( 宋敦江 ) 2010 7 31 Institute of Policy and Management, Chinese Academy of Sciences(CAS),100190 Tel:13488734079 e Mail: songdj@casipm.ac.cn Joint work with Tianxiang Yue at Institute of Geographical Sciences and Jo t o t a a g ue at st tute o Geog ap ca Sc e ces a d Natural Resources Research, CAS, supported by NSF 40801187 and 40825003.
DEM Construction from Contour lines based on Regional Optimum Control I. Background II. HASMROC(Regional Optimum Control ) Method III. Case Study IV. Discussion V. References
DEM Construction from Contour lines based on Regional Optimum Control I. Background II. HASMROC(Regional Optimum Control ) Method III. Case Study IV. Discussion V. References
I Background Digital Elevation Model (DEM) is a representation of terrain elevation as a function of geographic location.
I Background(continued) A contour line is a series of connected points of the same heights. Contour lines form "line group", which describes the geomorphologic characteristics, such as the terrain valley and ridge.
I Background(continued) Methods for transforming Contour lines to DEM 1. TIN (Triangulated Irregular Network) 2. Thin Plate Spline(TPS, implemented in software ANUDEM) 3. Skeleton 4. Contour Dilation 5. Steep Slope TIN Skeleton TPS
DEM Construction from Contour lines based on Regional Optimum Control I. Background II. HASMROC(Regional Optimum Control ) Method III. Case Study IV. Discussion V. References
HASM (High Accuracy Surface Modeling) HASM (High Accuracy Surface Modeling) is a method for surface modeling, based on the theory of surface, which means that except its position in space, a surface is uniquely defined by its first fundamental coefficients and second fundamental coefficients. Ifwecangetmorepreciseitsfirst fundamental coefficients and second fundamental coefficients, then we can get a more precise shape about the surface. Theoretically, through iterative method, with the boundary value and by use of iteration, we can achieve this goal.
Backgroud of HASM
HASM (Continued) If a surface is graphed by a function z f ( x, y) = or the monge patch by r ( x, y) = ( x, y, f ( x, y)), the first fundamental coefficients, E and G, and the second fundamental coefficients, L and N, have the following relationship described in terms of finite difference equations: n+ 1 n+ 1 n+ 1 n n n n n fi+ 1, j 2 fi, j + fi 1, j 1 n fi+ 1, j fi 1, j 2 n fi, j+ 1 fi, j 1 Li, j = 2 ( Γ 11) + ( Γ 11 ) + h i, j 2h i, j 2h n n Ei, j + Gi, j 1 n+ 1 n+ 1 n+ 1 n n n n n fi, j+ 1 2 fi, j + fi, j 1 1 n fi+ 1, j fi 1, j 2 n fi, j+ 1 fi, j 1 Ni, j = 2 ( Γ 22 ) + ( Γ 22 ) + h i, j 2h i, j 2h n n Ei, j+ Gi, j 1 (1) h where h represents simulation step length, j n i, j n f i, denotes f ( x y ) f, value at the grid (i,j) at the n th iteration, ( Γ j ) denotes Γ j value at the grid (i,j) at the n th j iteration. details about Γii ( i = 1,2, j = 1,2), E, G, L ii and N can be referred to [1-2]. ii
HASM (Continued) The matrix formulation of equations set t(1) can be expressed as, n+ 1 n A1 F = b1 (1) n+ 1 n A2 F = b2 where F = [ f, f, L, f, f, f, L, f, L, f, f, L, f ] ; 1 n+ 1 n+ 1 n+ 1 n+ 1 n+ 1 n+ 1 n+ 1 n+ 1 n+ 1 n+ 1 T 1,1 1,2 1, My 2,1 2,2 2, My Mx,1 Mx,2 Mx, My A and A2 respectively represent coefficient matrices of the first equation and the second equation in equations set (1); n b 1 and b n 2 are respectively the right-hand vectors of equations set (1) at the n th iteration. Integrating sampling points constraint equations, the HASM simulation equations could be reformulated as, n+ 1 n min AF b 2 n+ 1 stcf.. = d λ For a number λ sufficiently large, HASM could be transformed to unconstrained least squares approximation [15], A min [ ] F f λc n 1 (1) n + b [ ] (2) 2 λd or [ A T T A n+ 1 T T b λ C ][ ] F = [ A λc ][ ] (3) λc λd
实现技术流程HASM 的图
HASMROC(Regional Optimum Control) DEM simulation( from scattered points) equations could be reformulated as: Equations from sampling n 1 st.. S F + = t 1 min [ T ] n + A A F b n 2 (1) HASM When more information is available, DEM simulation can be expressed as: n+ 1 ti min AF b from st.. points n+ 1 S F = t n+ 1 from l < F < u Equations sampled Equations unsample dpoints n 2 HASMROC
Details about Coefficient Matrix A A is a matrix from discretization of elliptic system, A=[A 1 ; A 2 ], A 1 and A 2 is as follows: If computational domain can be divided as orthogonal division [, Lx ] [ 0, Ly ] 0 ( max( Lx, Ly ) = 1 ), Lx Ly h = I = + 1 J +1 is the grid cell size, in order to get the values of grid center points {( xi, y j ) 0 i I + 1, 0 j J +1} in some simulation, a difference equations can be set up in two axis. A 1 2 I J I J I J 2I J I J = O O O I J 2I I J J I J 2I J ( I* J ) ( I* J ) A 2 2 1 1 2 1 O O O = 1 2 1 O O O 1 2 1 1 2 I J I J ( * ) ( * )
HASMROC vs. HASM HASMROC Red is outer bound,yellow inner bound(buffer),green is valid simulation region (Minimum Rectangular Boundary of the Original data) Solid point is the boundary, solid triangle is the sampling point, circle points is to be simulated. HASM
lower and upper bounds for every DEM grids For each Gid(ij) Grid(i,j) While(1) Find any contour C(k) which contains Grid(i,j) in contours C; Hk=C(k).Z; If C(k) is a leaf node Grid(i,j) s lower bound is Hk; Grid(i,j) s upper bound is Hk plus one contour interval; Else Look for among C(k) s children and find the contour C(w) which contains Grid(i,j); If contour C(w) is empty Grid(i,j) s lower bound is Hk; Grid(i,j) s upper bound is Hk plus one contour interval; Else Set C(k)= C(w); End If End If End While End For. P3. P2. P1. P2 a) b) 图 1 等高线及等高线树图,a) 等高线,b) 等高线树. P2. P1 图 2 Single Hills 图 3 Multi-hills
0 4 6 8 0 4 Some results of lower and upper bounds for every DEM grids 3 2 2 0 2 6 4 1 0 2-2 2 0-2 2 0 2-1 2 0-2 -4 0-6 -4-2 -2-2 -3-3 -2-1 0 1 2 3
Details about HASMROC 1. 为方便求解, 本文在利用 HASMOC 方法进行实际模拟 DEM 时, 将采样数据的等式约束方程转换为上下界约束, 让采样点的模拟结果值可以在采样值附近微小活动 ( 上下界为采样值 ± 一个微小量 ), 这样所有格网点都转换为上下界约束, 便于使用 Matlab 求解模拟 2. 求解使用 Matlab 7.8 中的 lsqlin 函数 :lsqlin 主要用于解决不等式约束的最小二乘的曲线拟合问题, 可以用于求解大规模的仅有界约束的优化问题, 对于具有等式和不等式约束的优化问题, 只能求解很小规模
DEM Construction from Contour lines based on Regional Optimum Control I. Background II. HASMROC(Regional Optimum Control ) Method III. Case Study IV. Discussion V. References
III Case Study 1. Mathematical (Gaussian Synthetic ) surface 2. Real terrain surface
Case I: Gaussian Synthetic Surface Zrange inbetween ( 6.551, 8.106) x 1 z = 3*(1 x) * e 10*( x y )* e * e 5 3 2 2 2 2 2 2 2 ( x ( y + 1) ) 3 5 ( x y ) ( ( x + 1) y )
Simulation results 3D Shaded relief from HASMROC simulated DEM Derived contour lines from HASMROC and original Gauss Synthesis surface
Resolution=0.12 TPS(Thin Plate Spline) Blue is the original contour lines Red is the derived ones HASMROC
Resolution=0.0606 TPS(Thin Plate Spline) Blue is the original contour lines Red is the derived ones HASMROC
Convergenc Analysis
Case II: Manually vectorized data 江西省千烟洲生态试验站地理位置千烟洲扫描矢量化原始等高线图 (20m 等高距 )
3 Results compared with TIN a) b) Interpolated DEM of, a)tin(triangulated Irregular Network), b)hasmroc
3 Results compared with TIN(2) Black is the original contour lines Blue is the derived ones a) b) a) b) Overlay of the derived contour lines with original contour lines from, a)tin(triangulated Irregular Network),b)HASMROC
3 Results compared with TIN(3) 8 x 104 3 x 104 7 2.5 6 a) 5 2 频数 4 频数 1.5 3 1 2 0.5 1 0 70 80 90 100 110 120 130 140 高程 b) 0 70 80 90 100 110 120 130 140 高程 a) b) Histogram of DEM fromfrom, a)tin(triangulated Irregular Network),b)HASMROC
4 Results compared with TPS a) b) Interpolated DEM of, a)tps(thin Plate Spline), b)hasmroc
4 Results compared with TPS(2) Black is the original contour lines Blue is the derived ones a) b) a) b) Overlay of the derived contour lines with original contour lines from, a)tps(thin Plate Spline,b)HASMROC
DEM Construction from Contour lines based on Regional Optimum Control I. Background II. HASMROC(Regional Optimum Control ) Method III. Case Study IV. Discussion V. References
Discussion 1. By solving a simple optimization problem, DEM can be secured, which is smooth and of high fidelity to original contours. 2. Mathematical and real contour lines examples are given, and results from HASMROC are compared with that from TIN (Triangulated Irregular Network) and TPS (Thin Plate Spline) method, HASMROC is superior to the latter s in DEM construction in two cases, TPS 和 TIN 忽略了很多地形细节, 而 HASMOC 方法却保留了大量的地形细节 ; 回放等高线显示,TIN 与 TPS 方法回放效果差
Future work 1. Large scale constraint Optimization: 大规模约束优化求解方法的 C++ 底层实现,; 2. Quick algorithms: 快速任意点的值范围 ( 上下界 ) 的确定方法, 结合等高线树 约束 TIN 及射线求交法, 根据模拟精度 ( 分辨率 ) 的要求提取地形特征点 特征线与特征面, 或从遥感数据或实地测量获得有用地形信息, 并建立对应的约束优化方程, 从而建立更加符合实际的 DEM; 3. Real applications: 数字土壤制图, 气候数据制图, 多尺度数据综合的研究, 基于等高线与地形特征的地形简化 ;
Future work Proposed Scheme: 1. Quadratic Programming + Interior point methods; 2. 增广 Lagrange 算法 + Projection method + Slash variables; 3. Specific methods(equality constraint least square methods); Assistant Tools and software: 1. sparse matrix solvers (e.g., KNITRO and IPOPT) 2. NEOS server 3. Modeling system (AMPL or GAMS) 大规模约束优化求解方法
Future work(continued) 等高线树 TIN 任意点的值约束方程的确定
Future work(continued) 等高线树 TIN 任意点的值约束方程的确定之二
Main References 1. YUE T.X., Du Z.P., SONG D.J., GONG J., A new method of surface modeling and its application to DEM construction, ti Geomorphology, 2007, 91 (12), 161-172 172 2. Yue T.X., Song D.J., Du Z.P., Wang W., High accuracy surface modeling and its application to DEM generation [J]. International Journal of Remote Sensing, 2010, 2205-2226 3. Ciarlet, Philippe G. (2002). A surface is a continuous function of its two fundamental forms. C. R. Acad. Sci. Paris, Ser. I 335: 609-614. 4. Ciarlet, Philippe G., F. Larsonneur (2002). On the recovery of a surface with prescribed first and second fundamental forms. J. Math. Pures Appl. 81: 167-185. 185. 5. SONG D.J., YUE T.X., Du Z.P., DEM Construction from Contour lines based on Regional Optimum Control[C], in Proceedings of the Third International Joint Conference on Computational Sciences and Optimization, CSO 2010, 162-165. 6. 宋敦江, 岳天祥, 杜正平, 等高线树的构建及其在建立高保真 DEM 中的应用, 中国图像图形学报, 2010(Accepted) 7. 宋敦江, 岳天祥, 杜正平, 陈传法. 简单地形特征建立 DEM 的 HASM 方法 [J], 武汉大学学报 - 信息科学版, 2010(Accepted) 8. 宋敦江, 岳天祥, 杜正平, 等高线反演 DEM 的区域优化控制方法, 测绘学报, 2010(submitted) 9. Z.L. Li, Q. Zhu, Christopher Gold. Digital terrain modeling : principles and methodology. Boca Raton, Florida New York, N.Y., Taylor & Francis,2005
Dunjiang Song( 宋敦江 ) Tel:13488734079 e-mail: songdj@casipm.ac.cn