数字媒体几何结构的离散化表示与分析方法研究

In many applications of digital media computing, the massive media data is treated as a dense point cloud which distributed in a low-dimensional manifold embedded in a very high dimensional feature space. Traditionally the low dimensional manifolds representing media data were assumed to be C^\infty smooth. Then the k-adjacence graph or tangent space are regarded as the first-order approximation of this smooth manifold and the numerical solution is made feasibly by discretizing the problem space; for example, the classic ISMAP method and the level set method. In this proposal, we propose using simplex structure to describe the low-dimensional manifold consisting of sample points. By connecting points into simplicial complex, our proposed modeling approach has several distinguishing advantages when compared to the traditional methods. First, the assumption of C^\infty smoothness is no longer required in our approach. Secondly the Riemannian metric on C^\infty smooth manifold is no longer required in our approach. To achieve these merits, we introduce the continuous Dijkstra algorithm in computational geometry and extend it for computing the exact geodesic in simplicial complex. Given the necessary geodesic metric in simplicial complex, we propose to use computational geometry algorithms including Voronoi diagram, Delaunay triangulation, subdivision, point and region location methods, to build optimal geometric structures in simplicial complex, for achieving novel and efficient algorithms in the application of media classification, media reconstruction and manifold learning. In addition to its theoretical value, the proposed simplicial complex representation for low-dimensional manifold and its associated computational geometry methods also have contributions to practical applications in media computation.

数字媒体的大量应用中，都将海量媒体数据视为分布在高维特征空间中低维流形结构上的稠密离散点集。传统的流形结构分析方法和计算方法，都预先假定流形是无穷光滑的，再将k-近邻图或切空间视为光滑流形的一阶近似对求解的问题进行离散化，从而采用数值解法得到近似解。本项申请中提出使用单纯形结构来直接表征高维空间中的低维流形，通过将高维空间中的离散点集连接成单纯复形，避免了传统方法中预先假定光滑流形以及估计黎曼度量的限制。在单纯复形的流形结构表达中，最重要的是得到任意两点间的精确测地距离，本项申请拟将计算几何中连续Dijkstra算法推广到高维单纯复形结构中来计算测地度量，并将几何对象表征、几何查找（点定位和区域查找）和几何优化等计算几何算法应用在单纯复形流形结构中，面向数字媒体分类、流形重构和流形学习等应用研究高效实用算法。提出的研究内容密切结合当前数字媒体技术的发展趋势，具有较大的理论和应用价值。

本项目在任务书中提出将海量媒体数据视为分布在高维特征空间中低维流形结构上的稠密离散点集，使用单纯形结构来直接表征高维空间中的低维流形，从而避免传统方法中预先假定光滑流形以及估计黎曼度量所带来的限制。最主要研究内容包括提出基于单纯复形的流形表示方法，提出基于单纯复形流形表征的测地线计算方法，点集数据的流形学习与重构，以及新方法在数字媒体中的应用。..本项目经过四年的实施，取得了如下重要结果。（1）研究了二流形网格上精确测地度量结构，证明了经典MMP结构可以在表征网格的半边结构中进行合并，从而将MMP的运行速度提高一倍以上；进一步提出了快速计算精确测地度量的FWP框架；（2）基于精确度量，研究了二流形网格上的Voronoi图组合结构，提出了构造算法并证明给出了组合复杂度；（3）将有关测地度量和Voronoi图计算方法，应用在数字媒体的识别、分类检索、点云重构、视频摘要中，形成了一个较完整的技术体系。..本项目截止到目前，共发表或录取论文21篇，其中包括IEEE Trans. Pattern Analysis and Machine Intelligence、IEEE Trans. Visualization and Computer Graphics、IEEE Trans. Automation Science and Engineering、IEEE Trans. Multimedia、Neurocomputing、Computer-Aided Design等国际著名SCI期刊论文17篇，中文知名期刊《中国科学：信息卷》和《计算机辅助设计与图形学学报》论文2篇，完成了项目任务书中提出的预期成果。