基于局部优化的重心Voronoi图计算
|
摘要
重心Voronoi图(centroidal Voronoi tessellation,CVT)是一个重要的几何结构,在地理信息系统,信号处理,网格生成/优化,可视化等领域有着重要应用。针对传统全局生成、优化的方法的不足,比如奇异点多、收敛速度较慢等问题,提出了生成优化与随机扰动两种局部优化方法,以及一个整合了层次生成、局部优化、蒙特卡罗优化的CVT生成算法框架。实验结果表明,相比于已有算法,本文方法在速度与质量上有综合的提升。
Centroidal Voronoi tessellation is a special geometric structure, which has many applications in various fields such as geographical information system, signal processing, mesh generation/optimization, visualization and so on. Due to the highly non-convex nature of the CVT energy function, the existing methods for computing CVT have several drawbacks, which always trap into local minima. We propose generation optimization and stochastic optimization schemes for further reducing the CVT energy. Experimental results show that the proposed method improves both quality and efficiency compared to the recent approaches.
Centroidal Voronoi tessellation is a special geometric structure, which has many applications in various fields such as geographical information system, signal processing, mesh generation/optimization, visualization and so on. Due to the highly non-convex nature of the CVT energy function, the existing methods for computing CVT have several drawbacks, which always trap into local minima. We propose generation optimization and stochastic optimization schemes for further reducing the CVT energy. Experimental results show that the proposed method improves both quality and efficiency compared to the recent approaches.
引文
[1]Du Q,Faber V,Gunzburger M.Centroidal Voronoi tessellations:Applications and algorithms[J].SIAMreview,(S0036-1445),1999,41(4):637-676.
[2]Du Q,Gunzburger M.Grid generation and optimization based on centroidal Voronoi tessellations[J].Applied Mathematics and Computation(S0096-3003),2002,133(2/3):591-607.
[3]Du Q,Gunzburger M D,Ju L.Constrained centroidal Voronoi tessellations for surfaces[J].SIAM Journal on Scientific Computing(S1064-8275),2003,24(5):1488-1506.
[4]Lloyd S.Least squares quantization in PCM[J].IEEEtransactions on information theory(S0018-9448),1982,28(2):129-137.
[5]Du Q,Emelianenko M,Ju L.Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations[J].SIAM journal on numerical analysis(S0036-1429),2006,44(1):102-119.
[6]Liu Y,Wang W,Lévy B,et al.On centroidal Voronoi tessellation-energy smoothness and fast computation[J].ACM Transactions on Graphics(To G)(S0730-0301),2009,28(4):101.
[7]Lu L,Sun F,Pan H,et al.Global optimization of centroidal voronoi tessellation with monte carlo approach[J].IEEE transactions on visualization and computer graphics(S1077-2626),2012,18(11):1880-1890.
[8]Wang L,Hétroy-Wheeler F,Boyer E.A hierarchical approach for regular centroidal Voronoi tessellations[J]Computer Graphics Forum(S0167-7055),2016,35(1):152-165.
[9]Du Q,Gunzburger M,Ju L.Advances in studies and applications of centroidal Voronoi tessellations[J].Numerical Mathematics:Theory,Methods and Applications(S1004-8979),2010,3(2):119-142.
[10]Gersho A.Asymptotically optimal block quantization[J].IEEE Transactions on information theory,(S0018-9448),1979,25(4):373-380.
[11]Fejes Tóth G.A stability criterion to the moment theorem[J].Studia Scientiarum Mathematicarum Hungarica(S0081-6906),2001,38(1/2/3/4):209-224.
[12]Asami,Y."A Note on the Derivation of the First and Second Derivatives of Objective Functions in Geographical Optimization Problems",Journal of Faculty of Engineering,University of Tokyo[J],1991,61(1),1-13.
[13]Iri M,Murota K,Ohya T.A fast Voronoi-diagram algorithm with applications to geographical optimization problems[M]Berlin,Heidelberg:System modelling and optimization.Springer,1984:273-288.
[14]Du Q,Emelianenko M.Acceleration schemes for computing centroidal Voronoi tessellations[J].Numerical linear algebra with applications(S1070-5325),2006,13(2/3):173-192.
[15]CGAL,Computational Geometry Algorithms Library.http://www.cgal.org.
[16]Yan D M,Wang K,Lévy B,et al.Computing 2D periodic centroidal Voronoi tessellation[C]//Voronoi Diagrams in Science and Engineering(ISVD),2011 Eighth International Symposium on.IEEE,2011:177-184.
[2]Du Q,Gunzburger M.Grid generation and optimization based on centroidal Voronoi tessellations[J].Applied Mathematics and Computation(S0096-3003),2002,133(2/3):591-607.
[3]Du Q,Gunzburger M D,Ju L.Constrained centroidal Voronoi tessellations for surfaces[J].SIAM Journal on Scientific Computing(S1064-8275),2003,24(5):1488-1506.
[4]Lloyd S.Least squares quantization in PCM[J].IEEEtransactions on information theory(S0018-9448),1982,28(2):129-137.
[5]Du Q,Emelianenko M,Ju L.Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations[J].SIAM journal on numerical analysis(S0036-1429),2006,44(1):102-119.
[6]Liu Y,Wang W,Lévy B,et al.On centroidal Voronoi tessellation-energy smoothness and fast computation[J].ACM Transactions on Graphics(To G)(S0730-0301),2009,28(4):101.
[7]Lu L,Sun F,Pan H,et al.Global optimization of centroidal voronoi tessellation with monte carlo approach[J].IEEE transactions on visualization and computer graphics(S1077-2626),2012,18(11):1880-1890.
[8]Wang L,Hétroy-Wheeler F,Boyer E.A hierarchical approach for regular centroidal Voronoi tessellations[J]Computer Graphics Forum(S0167-7055),2016,35(1):152-165.
[9]Du Q,Gunzburger M,Ju L.Advances in studies and applications of centroidal Voronoi tessellations[J].Numerical Mathematics:Theory,Methods and Applications(S1004-8979),2010,3(2):119-142.
[10]Gersho A.Asymptotically optimal block quantization[J].IEEE Transactions on information theory,(S0018-9448),1979,25(4):373-380.
[11]Fejes Tóth G.A stability criterion to the moment theorem[J].Studia Scientiarum Mathematicarum Hungarica(S0081-6906),2001,38(1/2/3/4):209-224.
[12]Asami,Y."A Note on the Derivation of the First and Second Derivatives of Objective Functions in Geographical Optimization Problems",Journal of Faculty of Engineering,University of Tokyo[J],1991,61(1),1-13.
[13]Iri M,Murota K,Ohya T.A fast Voronoi-diagram algorithm with applications to geographical optimization problems[M]Berlin,Heidelberg:System modelling and optimization.Springer,1984:273-288.
[14]Du Q,Emelianenko M.Acceleration schemes for computing centroidal Voronoi tessellations[J].Numerical linear algebra with applications(S1070-5325),2006,13(2/3):173-192.
[15]CGAL,Computational Geometry Algorithms Library.http://www.cgal.org.
[16]Yan D M,Wang K,Lévy B,et al.Computing 2D periodic centroidal Voronoi tessellation[C]//Voronoi Diagrams in Science and Engineering(ISVD),2011 Eighth International Symposium on.IEEE,2011:177-184.