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

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

项目编号： No.61272228

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 刘永进

作者单位： 清华大学

项目金额： 83万元

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

中文关键词： 测地线；几何结构；数字媒体应用；；

英文摘要： 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,

英文关键词： Geodesic；geometric structure；digital media applications；；