Microsoft PowerPoint - DEM Construction from Contour lines based on Regional Optimum Control ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - DEM Construction from Contour lines based on Regional Optimum Control ppt [兼容模式]"

册姚
6 years ago
Views:

1 DEM Construction from Contour lines based on Regional Optimum Control Dunjiang Song( 宋敦江 ) Institute of Policy and Management, Chinese Academy of Sciences(CAS), Tel: 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 and

2 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

3 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

4 I Background Digital Elevation Model (DEM) is a representation of terrain elevation as a function of geographic location.

5 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.

6 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

7 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

8 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.

9 Backgroud of HASM

10 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

11 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

12 实现技术流程HASM 的图

13 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

14 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 O O O = O O O I J I J ( * ) ( * )

15 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

16 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

17 Some results of lower and upper bounds for every DEM grids

18 Details about HASMROC 1. 为方便求解, 本文在利用 HASMOC 方法进行实际模拟 DEM 时, 将采样数据的等式约束方程转换为上下界约束, 让采样点的模拟结果值可以在采样值附近微小活动 ( 上下界为采样值 ± 一个微小量 ), 这样所有格网点都转换为上下界约束, 便于使用 Matlab 求解模拟 2. 求解使用 Matlab 7.8 中的 lsqlin 函数 :lsqlin 主要用于解决不等式约束的最小二乘的曲线拟合问题, 可以用于求解大规模的仅有界约束的优化问题, 对于具有等式和不等式约束的优化问题, 只能求解很小规模

19 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

20 III Case Study 1. Mathematical (Gaussian Synthetic ) surface 2. Real terrain surface

21 Case I: Gaussian Synthetic Surface Zrange inbetween ( 6.551, 8.106) x 1 z = 3*(1 x) * e 10*( x y )* e * e ( x ( y + 1) ) 3 5 ( x y ) ( ( x + 1) y )

22 Simulation results 3D Shaded relief from HASMROC simulated DEM Derived contour lines from HASMROC and original Gauss Synthesis surface

23 Resolution=0.12 TPS(Thin Plate Spline) Blue is the original contour lines Red is the derived ones HASMROC

24 Resolution= TPS(Thin Plate Spline) Blue is the original contour lines Red is the derived ones HASMROC

25 Convergenc Analysis

26 Case II: Manually vectorized data 江西省千烟洲生态试验站地理位置千烟洲扫描矢量化原始等高线图 (20m 等高距 )

27 3 Results compared with TIN a) b) Interpolated DEM of, a)tin(triangulated Irregular Network), b)hasmroc

28 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

29 3 Results compared with TIN(3) 8 x x a) 5 2 频数 4 频数高程 b) 高程 a) b) Histogram of DEM fromfrom, a)tin(triangulated Irregular Network),b)HASMROC

30 4 Results compared with TPS a) b) Interpolated DEM of, a)tps(thin Plate Spline), b)hasmroc

31 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

32 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

33 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 方法回放效果差

34 Future work 1. Large scale constraint Optimization: 大规模约束优化求解方法的 C++ 底层实现,; 2. Quick algorithms: 快速任意点的值范围 ( 上下界 ) 的确定方法, 结合等高线树约束 TIN 及射线求交法, 根据模拟精度 ( 分辨率 ) 的要求提取地形特征点特征线与特征面, 或从遥感数据或实地测量获得有用地形信息, 并建立对应的约束优化方程, 从而建立更加符合实际的 DEM; 3. Real applications: 数字土壤制图, 气候数据制图, 多尺度数据综合的研究, 基于等高线与地形特征的地形简化 ;

35 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) 大规模约束优化求解方法

36 Future work(continued) 等高线树 TIN 任意点的值约束方程的确定

37 Future work(continued) 等高线树 TIN 任意点的值约束方程的确定之二

38 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), 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, Ciarlet, Philippe G. (2002). A surface is a continuous function of its two fundamental forms. C. R. Acad. Sci. Paris, Ser. I 335: Ciarlet, Philippe G., F. Larsonneur (2002). On the recovery of a surface with prescribed first and second fundamental forms. J. Math. Pures Appl. 81: 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, 宋敦江, 岳天祥, 杜正平, 等高线树的构建及其在建立高保真 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

39 Dunjiang Song( 宋敦江 ) Tel: songdj@casipm.ac.cn

Thesis for the Master degree in Engineering Research on Negative Pressure Wave Simulation and Signal Processing of Fluid-Conveying Pipeline Leak Candi

U17 10220 UDC624 Thesis for the Master degree in Engineering Research on Negative Pressure Wave Simulation and Signal Processing of Fluid-Conveying Pipeline Leak Candidate:Chen Hao Tutor: Xue Jinghong