三维几何数据处理中若干压缩与检索算法的研究

摘要

三维数字获取技术的快速发展使得人类获得越来越多的三维几何模型数据，这些几何模型数据中典型的有静态的点模型数据和动态的运动捕获数据。为了对庞大三维几何模型数据集进行组织管理，设计高效的模型数据压缩和检索算法具有重要意义。本文工作的重点是三维点模型与运动捕获数据的压缩和实时检索算法。
　　 在三维点模型压缩方面，对基于最小生成树的算法进行了改进，结合浮点数压缩算法，提出了一个高效快速点模型无损压缩算法。首先将点模型表面切分成多个小面块。然后，以每个块为单位，生成最小生成树并按宽度优先顺序对树形结构进行编码，同时沿树形结构预测。最后，采用改进的浮点压缩算法对预测校正值进行压缩编码。算法在压缩时间和压缩率两项指标上均优于以往点模型无损压缩算法。
　　 在运动捕获数据无损压缩方面，提出了一个带参平行四边形预测器-APP。APP沿着运动捕获数据层次结构进行预测，它根据已经处理过的近邻自由度信息和当前节点的父节点自由度信息，来对当前自由度进行预测。同时，利用查找表技术来有效地索引存储预测参数口。实验结果表明，相对于传统无损压缩方法，APP取得较高压缩比，而在压缩时间上基本与传统方法持平。
　　 在运动数据检索方面，本文提出了一个实时运动检索算法-EigenMR。不同于以往基于时域比较的算法，EigenMR在变换域中进行匹配和比较。该方法将人体骨架分成多个层次和部分，接着从中抽取重要本征值与本征向量作为运动的索引。在实时检索时，EigenMR既对人体整体特征的索引进行匹配，也对身体各部分特征的索引进行匹配。实验结果表明，EigenMR在运算时间与检索精确性上都好于以前算法。
　　 基于提出的运动无损压缩算法和运动实时检索算法，本文提出了一个运动捕获数据库框架。该框架基于EigenMR中的匹配分数来定义两个运动的距离，并以此距离为基础，采用k-means算法进行聚类。接着根据聚类结果，将运动捕获数据组织成两层索引结构，第一层为聚类中心点，第二层指向经过APP压缩后的运动序列。这样，实时检索分为三个步骤，在前两步，两层的索引结构能够快速地对运动序列进行过滤，得到预选结果集。在第三步，只需要对预选结果集中数据进行解压，然后采用DTW算法进行精确匹配。实验结果表明，用户可以实时地从无损压缩的运动捕获数据中检索数据。