三维形状对应是在两个或多个三维模型之间寻找一种关于模型元素之间的有意义的映射关系，它是计算机图形学和计算机视觉的基本问题，也是很多计算机应用的基础。形状对应在形状分析领域具有重要的地位，是近几年研究的热点领域，同时也是一个具有很强挑战性的难题。本文主要研究非刚性等距（近似等距）模型的对应问题。为了解决等距对应问题本文首先提出了一种新的表示模型的标架，借助该标架将模型嵌入到一个 空间，进而在 空间中将对应问题转换成一个最小费用最大流问题（MCFP），进而求解对应问题。本文主要的工作和创新点如下：1. 为了消除刚性变换以及非刚性等距变换对模型的影响，本文提出了一种与等距变换无关的模型描述标架。 2.提出了一种计算等距模型之间对应关系的算法。将对应问题转换成嵌入的 空间中两个点集合之间每个点的最近邻点问题。为了解决该问题，在两个集合之间构建一个代价流网络，并进行最小费用最大流问题求解以获得最后的对应结果。本文算法的流程是一种计算对应问题的框架，不仅可以应用到等距模型对应问题，也可以应用到一般的非刚性模型之间的对应问题。本文方法不仅可以计算等距模型之间的稀疏到稠密的对应结果，也可以解决近似等距模型之间的稀疏对应及稠密对应问题。 3. 本文提出了一种加速求解三维形状对应问题的方法，基于分治策略对模型进行分层采样，在相对较小的搜索域进行对应结果的查找，最后将所有层次的对应结果合并成一个稠密的对应结果。本文利用最远距离采样方法以确保采样结果在模型上均匀分布，使用外特征点作为采样的初始采样点，在等距模型上得到一种分层采样结果，进而将稠密对应分解成为多个小的对应问题，再将其分别转化成最小费用最大流问题进行求解。最后将每层得到的对应结果进行合并以得到稠密的对应结果。本文的方法已经在几个不同的公开三维模型数据集上进行实验，实验结果表明本方法的正确性和有效性。

Three-dimensional shape correspondence is to find a meaningful relationship between the elements of two or more objects.It is a fundamental problem in computer graphics and computer vision, as well as is aprimary work in wide range of applications. Moreover, it has an important role in the field of shape analysis, and is a hot area of research in recent years, at the same time, also a challenging task in numerous applications.This thesisfocuses on the study of non-rigid (nearly) isometric shape correspondence. Tosolve the problem, Ifirst propose the corresponding frame of a new representation of the model. By taking advantage of the frame representation, the modelsare embedded into a space, and then the corresponding problem hasbeen converted into a Minimum-cost flow problem (MCFP), itssolution provides the correspondencesmap.The main contributions and innovations of my work are as follows:1. In order to eliminate the impact of rigid transformation and isometric transformation on the model, a new description frame is proposed which is independent the model’s isometric transformation.2. A novel approach is proposed to calculate the corresponding between isometric models. In the embedded space, at first, corresponding problem will be converted into finding the nearest neighbor points between two point sets. It is computed by constructing a cost flow.And the final correspondence has been achieved through solving minimum cost maximum flow problem. The proposed algorithm is a kind of general framework, which is apply to solve other correspondence problems. The proposed solution can be applied in corresponding research not only isometric model, but also applicable innon-rigid model. The corresponding results from sparse to dense have been presented.The algorithm also can figure out approximate isometric model’s sparse and dense corresponding problem.3. I put forward an accelerating methodof the above corresponding algorithm. Firstly stratify sampling is implemented through adopting divide and conquer strategy. Thus the whole correspondence problem will be divided into many small corresponding problems.The corresponding results in all levels are merged into a dense corresponding outcome in the end. In this study, based on the farthest distance sampling method, it is guaranteed that the sampling results are evenly distributed. Here out feature points are employed as initialization to obtain peculiar layered sampling results on the isometric models. Then the dense correspondences are divided into many small corresponding problems. After that, these small problems are transformed into the minimum cost maximum flow issue respectively. Finally, I combine the corresponding results that extracts from every levels into the final dense corresponding results.In this thesis, the above methods are tested on multiple benchmark databases. The experimental results show the correctness and effectiveness of the method.