最大化泊松盘采样方法及其在媒体处理中的应用

Sampling technique is fundamental in multimedia processing and computer graphics, which is important to image synthesis, realistic rendering, mesh generation, and many other interdisciplinary applications. Among all sampling techniques, Maximal Poisson-disk Sampling (MPS) has attracted the most attention since it generates point set with the blue-noise property, which is desired in many of those applications. The most difficult parts of MPS lie in (1) the detection and extraction of gaps in a non-maximal sampling set, (2) the relationship between an MPS and mesh generation, and (3) generation of MPS in dynamic domain, such as video, vector field, and dynamic surfaces. In this work, we shall investigate the method of generating MPS and its applications in digital multimedia processing. Our research will concentrate on four topics: (1) theoretical analysis of MPS in Euclidean space and the corresponding sampling framework; (2) MPS both on polygonal mesh surfaces and in 3D volumes, and applications of MPS in surface remeshing and tetrahedral mesh generation; (3) dynamic MPS, and its applications in multimedia processing, and (4) the quality evaluation framework of the MPS. The technical innovations include (1) solid theoretical analysis of the condition of the existence of gaps in a ready-sampled point set, (3) a series of simple and efficient algorithms for MPS in Euclidean spaces and on manifolds, and (4) generalization of the static MPS algorithms in dynamic multimedia data. We demonstrate our sampling techniques with applications including video stippling, vector field visualization, dynamic surface sampling and dynamic mesh generation, which are ready to be used in digital multimedia and entertainment applications. The problems involved in this project are of great significance in digital media processing and computer graphics.

采样方法是多媒体和三维内容处理的基础技术之一，其中生成具有蓝噪声点集的最大化泊松圆盘采样方法是国际研究热点。本项目研究的内容为高质量的最大化泊松圆盘采样方法，以及在网格生成和多媒体信息处理的技术问题，有四个方面：①欧式空间中最大化泊松圆盘采样的理论及技术框架；②网格曲面上的采样及重新网格化，三维体内部采样及四面体网格生成；③动态区域的采样技术以及在多媒体处理中的应用（视频的点绘，流场可视化，三维动态形变网格生成等）， ④采样算法的评估方法。技术创新在于采样方法的理论分析和最大化泊松采样方法的技术关键、定位和提取已有采样点集的空隙区域、将该理论推广到三维网格曲面和三维形体内部、网格生成及优化算法。主要技术难点在于欧式空间以及曲面上空隙区域的定位以及提取，最大化泊松圆盘采样点集与网格生成之间的关系，以及针对不同动态区域的采样方法。

蓝噪声采样方法是计算机图形学，多媒体处理，以及许多交叉学科中都涉及到的一个基础问题。而最大化泊松圆盘采样方法又是众多蓝噪声采样方法中最具代表性的算法之一，广泛应用于生物，物理，化学，医学以及艺术等诸多领域。..本项目的主要研究内容包括五个问题：①MPS 的理论及方法，②曲面和三维形体的MPS 及网格生成，③动态MPS 方法，④基于MPS 的媒体处理，⑤MPS 的质量评估。..我们针对这五个主要问题展开研究，并且针对相关领域的关键问题进行了探索，取得了一系列高水平的研究成果。主要成果可以分为三类：(1)提出了一系列蓝噪声采样的方法，并且用于媒体处理等应用；（2）提出一系列网格生成及优化方法；（3）在多个相关领域进行深入研究，比如三维形状的理解，建模等。..在这些方面，总共发表论文30余篇，其中包括计算机图形学领域顶级期刊ACM Transaction on Graphics (ACM TOG)、可视化领域顶级期刊IEEE Transaction on Visualization and Computer Graphics、欧洲图形学权威期刊Computer Graphics Forum (CGF)2篇等，并且获图形学重要会议Shape Modeling International (SMI) 2014年最佳论文提名奖。..其中具有代表性的结果包括我们首次提出了变半径采样下达到最大化采样的理论条件，并且给出了具体算法实现。首次将最大化泊松圆盘采样推广到三维网格曲面以及等值面，并且首次提出具有蓝噪声性质的重新网格化概念。这些工作分别发表于2013年的图形学顶级期刊ACM TOG以及2014、2017年的IEEE TVCG。为了提升网格质量，我们提出了基于局部限制Voronoi图的重新网格化方法（TVCG 2014），基于重心Voronoi图的去钝角方法（TVCG 2016），以及基于最小角优化的重新网格化方法（TVCG 2017）等。此外，我们首次提出了基于图像规则性分析的逆向过程建模方法，发表于图形学顶级会议ACM Siggraph 2014，全文收录于ACM TOG。其后续工作关于二维布局的规则化方法发表于IEEE TVCG 2016。..这些方法极大的推动了蓝噪声采样技术的发展，受到了国际同行的许多好评，相关论文也被多次引用。也为我们的后续工作奠定了基础。