运动图搜索的DNA计算模型研究

This project takes motion capture reuse as research background, attempts to deal with the problem of searching optimal path in a large-scale motion graph, and aims to structure a new effective computing model by employing DNA computing. First, the project intends to study on the method of feature extraction from the original motion data, and plans to extract the key frames and sequence fragments to construct motion graph, which based on the methods dimension reduction and clustering. It is intends to covert motion synthesis into combinatorial optimization problem. Then, based on the different constraints of personalization, structure, semantic and kinematics of the motion capture data, the project will study on the DNA code model for expressing the motion graph, and focus on the establishment of DNA surface computing model. The project also plans to design a series of biology and chemical experiments to examine the DNA computing. Compared to the traditional ideas of 3D human motion data resue, the methods with DNA computing have the potential ability to meet the real-time mass data processing, and could help to promote the progress of the data processing theory in DNA computing.

本项目以运动捕捉中的数据重用为研究背景，针对数据合成中大规模运动图的最优路径搜索问题，结合具有高度并行性特质的DNA计算，探寻新的高效计算模型。项目首先研究运动数据的特征空间提取与表征方法，基于降维、聚类等算法思想完成运动捕捉数据的关键帧提取和关键运动片段切割，并在此基础上构建大规模运动图，将动作合成问题转化为图的最优路径搜索问题。然后综合考虑个性化、结构化、语义化以及运动学性能等约束特性，设计可有效将运动图转换为DNA编码的规则与方法。进而设计基于DNA表面计算的运动图搜索生化操作算法，并在传统电子计算机上完成运动图搜索的DNA计算模型仿真。本项目将DNA计算引入到人体运动数据合成重用领域，有助于拓展DNA计算的应用范围，推动基于DNA计算的数据处理理论方法的进展。

本项目以运动捕捉中的数据重用为研究背景，针对数据合成中最优运动路径搜索问题，结合具有高度并行性特质的DNA计算，探寻新的计算模型。第一步，项目从运动捕捉数据初始数据处理入手，研究了用于构建运动图的有效数据获取方法，即有效运动数据片段分割和有效数据关键帧获取方法，提出了一种基于LLE（locally linear embedding，流形学习）算法的运动分割技术和一种基于MPGA（Multiple Population Genetic Algorithm，多种群遗传算法）的运动捕捉数据关键帧提取方法。该部分的研究对于提高运动数据分割的准确率，减少关键帧提取的重构误差，实现了数据精简。第二步，结合运动图的特性与计算原理，提出了一种基于ISOMAP（Isometric Mapping，等距映射算法）算法的运动图构建方法。克服了标准方法使用运动数据段中所有运动帧计算跳转点导致的计算效率较低的问题，并进一步回避了标准方法会产生很多无用跳转点或违背物理规律的跳转点的问题，在保证计算准确度的前提下，大幅提高了运动图生成的计算效率。在运动图构建成功后，探索了基于DNA计算的理念来解决运动图的最优路线求解问题。第三步，针对数据转换时的DNA编码模式进行了研究。DNA编码在DNA计算中充当着重要的角色，编码的质量和数量对计算的精确度和效率有直接影响。该部分，项目组提出了一种基于小生境排挤机制的入侵杂草算法的DNA编码序列优化设计方法，并进一步提出了解决DNA编码优化问题的多目标入侵杂草智能算法。仿真实验表明，生成的DNA序列的质量较高，该部分为后续的建模求解提供了良好的基础。第四步，构建了基于DNA计算的最优运动路径的求解模型。基于运动图的有向性特点，将运动图求解问题转化为TSP（Traveling Salesman Problem，旅行商问题）问题，提出了一种基于PCR的DNA计算求解模型，采用双链DNA分子编码，给出用于求解TSP问题的一般方法。经过多次循环，将DNA序列片段连接成完整并包含前缀和后缀的DNA序列，然后对原有的特定长度的DNA链进行剪切和拼接，获得了全部的可行性路径，最后进行比较，得出最短最优路径，完成了运动图的最优路径求解。