流体模拟的压缩感知上采样方法研究

摘要/Abstract

摘要： 在计算机流体动画模拟中,欧拉网格方法是一种比较成熟和常用的模拟方法,但其关键瓶颈在于数据采样环节,受限于传统的Nyquist采样理论,难以缩减流场中的海量数据采样和计算。针对这一问题,基于压缩感知理论,探究流体动画中突破传统数据采样的局限性的方法。通过研究流体速度场数据的稀疏性和可压缩性特征,选取了适合于流体模拟的采样基、压缩基和重构算法,建立流体模拟的压缩感知上采样方法的框架。多种场景下的模拟结果显示,流体模拟的压缩感知上采样方法可以一定程度上恢复得到流场的细节,验证了压缩感知理论在流体动画上应用的可行性。

关键词: 流体模拟, 压缩感知, 上采样, 稀疏表示, 重构算法

Abstract: In computer fluid animation, the grid-based Euler method is a well-matured and effective way of simulating fluids, but a key bottleneck of Euler method is that it is limited to the traditional Nyquist-Shannon sampling theorem in sampling step. So it cannot effectively reduce the massive data and computing of the large-scale flow fields. In order to solve this problem, compressed sensing theory was used to probe a way to break through the limitation of the sampling theorem in fluid simulation. The sparsity and compressibility of fluid data were explored, then applicable sampling function, compressive basis and reconstruction algorithm for fluid data are selected. A compressed-sensing based up-sampling method and framework for fluid simulation was constructed based on researches and experiments. Several scenes of smoke animation were presented, the results show that compressed-sensing based up-sampling method can recover the details of the flow field to a certain extent, and prove the compressed sensing theory can apply to fluid simulation.

Key words: fluid simulation, compressed sensing, up-sampling, sparse representation, reconstruction algorithm

中图分类号:

TP391.9

钱宜婧, 杨旭波. 流体模拟的压缩感知上采样方法研究[J]. 系统仿真学报, 2015, 27(7): 1426-1434.

Qian Yijing, Yang Xubo. Compressed-sensing Based Up-sampling Method for Fluid Simulation[J]. Journal of System Simulation, 2015, 27(7): 1426-1434.

参考文献

[1] Foster N, Metaxas D.Realistic animation of liquids[J]. Graphical models and image processing (S1077-3169), 1996, 58(5): 471-483.
[2] Stam J.Stable fluids [C]// Proceedings of the 26th annual conference on Computer graphics and interactive techniques (ISBN: 0-201-48560-5). USA: ACM Press/Addison-Wesley Publishing Co., 1999: 121-128.
[3] Fedkiw R, Stam J, Jensen H W.Visual simulation of smoke[C]// Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques,(ISBN: 1-58113-374-X). USA: ACM, 2001: 15-22.
[4] Monaghan J J.Smoothed particle hydrodynamics[J]. Annual Review of Astronomy and Astrophysics (S0066-4146), 1992, 30(8): 543-574.
[5] Müller M, Charypar D, Gross M.Particle-based fluid simulation for interactive applications[C]// Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (ISBN: 1-58113-659-5). USA: ACM, Eurographics Association, 2003: 154-159.
[6] Losasso F, Gibou F, Fedkiw R.Simulating water and smoke with an octree data structure[J]. ACM Transactions on Graphics (TOG), ACM (S0730-0301), 2004, 23(3): 457-462.
[7] Zhu B, Lu W, Cong M, et al. A new grid structure for domain extension[J]. ACM Transactions on Graphics (TOG)(S0730-0301), 2013, 32(4): 96-96.
[8] Lentine M, Zheng W, Fedkiw R.A novel algorithm for incompressible flow using only a coarse grid projection[J]. ACM Transactions on Graphics (TOG)(S0730-0301), 2010, 29(4): 157-166.
[9] Wu X, Yang X, Yang Y.A Novel Projection Technique with Detail Capture and Shape Correction for Smoke Simulation [C]// Computer Graphics Forum. USA: Blackwell Publishing Ltd, 2013, 32(2): 389-397.
[10] Kim T, Thürey N, James D, et al. Wavelet turbulence for fluid simulation[J]. ACM Transactions on Graphics (TOG), ACM (S0730-0301), 2008, 27(3): 15-19.
[11] Pfaff T, Thuerey N, Cohen J, ,et al. Scalable fluid simulation using anisotropic turbulence particles [J]. ACM Transactions on Graphics. Scalable fluid simulation using anisotropic turbulence particles [J]. ACM Transactions on Graphics (TOG), ACM (S0730-0301), 2010, 29(6): 174(1)-174(8).
[12] Zhang Y, Ma K L.Spatio-temporal Extrapolation for Fluid Animation[J]. ACM Transactions on Graphics (S0730-0301), 2013, 32(6): 2504-2507.
[13] Treuille A, Lewis A, Popović Z.Model reduction for real-time fluids[J]. ACM Transactions on Graphics (TOG)(S0730-0301), 2006, 25(3): 826-834.
[14] Wicke M, Stanton M, Treuille A.Modular bases for fluid dynamics[C]//ACM Transactions on Graphics (TOG). ACM (S0730-0301), 2009, 28(3): 341-352.
[15] Candes E J, Tao T.Near-optimal signal recovery from random projections: Universal encoding strategies?[J]. Information Theory, IEEE Transactions on (S0018-9448), 2006, 52(12): 5406-5425.
[16] Donoho D L.Compressed sensing[J]. Information Theory, IEEE Transactions on (S0018-9448), 2006, 52(4): 1289-1306.
[17] Candès E J, Wakin M B.An introduction to compressive sampling[J]. Signal Processing Magazine, IEEE (S1053-5888), 2008, 25(2): 21-30.
[18] Takhar D, Laska J N, Wakin M B, et al. A new compressive imaging camera architecture using optical-domain compression[C]// Electronic Imaging 2006. International Society for Optics and Photonics. 2006: 43-52.
[19] M Lustig, D Donoho, J M Pauly.Sparse MRI: The application of compressed sensing for rapid MR imaging[J]. Magnetic Resonance in Medicine (S1522-2594), 2007, 58(6): 1182-1195.
[20] Sen P, Darabi S.Compressive image super-resolution[C]// Signals, Systems and Computers, 2009 Conference Record of the Forty-Third Asilomar Conference on (ISBN: 978-1-4244-5825-7). USA: IEEE, 2009: 1235-1242.
[21] Yang J, Wright J, Huang T S, et al. Image super-resolution via sparse representation[J]. Image Processing, IEEE Transactions on (S1057-7149), 2010, 19(11): 2861-2873.
[22] Yang J, Lin Z, Cohen S.Fast Image Super-Resolution Based on In-Place Example Regression[C]// Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on (ISBN: 978-0-7695-4989-7). USA: IEEE, 2013: 1059-1066.
[23] Wright J, Yang A Y, Ganesh A, et al. Robust face recognition via sparse representation[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on (S0162-8828), 2009, 31(2): 210-227.
[24] Gu J, Nayar S K, Grinspun E, et al. Compressive structured light for recovering inhomogeneous participating media[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on (S0162-8828), 2013, 35(3): 1-1.
[25] Sen P, Darabi S.Compressive dual photography [C]// Computer Graphics Forum. USA: Blackwell Publishing Ltd, 2009, 28(2): 609-618.
[26] Marwah K, Wetzstein G, Bando Y, et al. Compressive light field photography using overcomplete dictionaries and optimized projections[J]. ACM Transactions on Graphics (TOG)(S0730-0301), 2013, 32(4): 46.
[27] Candès E J, Romberg J, Tao T.Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[J]. Information Theory, IEEE Transactions on (S0018-9448), 2006, 52(2): 489-509.
[28] Tropp J A, Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit[J]. Information Theory, IEEE Transactions on (S0018-9448), 2007, 53(12): 4655-4666.
[29] Needell D, Vershynin R.Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit[J]. Selected Topics in Signal Processing, IEEE Journal of (S1932-4553), 2010, 4(2): 310-316.
[30] Chen S S, Donoho D L, Saunders M A.Atomic decomposition by basis pursuit[J]. SIAM journal on scientific computing (S1095-7197, S1064-8275), 1998, 20(1): 33-61.
[31] Tibshirani R.Regression shrinkage and selection via the lasso[J]. Journal of the Royal Statistical Society. Series B (Methodological)(S1467-9868), 1996, 58(1): 267-288.
[32] Van Den Berg E, Friedlander M P. Probing the Pareto frontier for basis pursuit solutions[J]. SIAM Journal on Scientific Computing (S1095-7197, S1064-8275), 2008, 31(2): 890-912.