模型的配准是很多科研应用领域的基础问题。给定两个三维模型，配准算法对其中一个模型（源模型）作变换使得变换后的模型与另一个模型（目标模型）满足某种（如几何上或拓扑上）对应关系。本文提出了一种基于BHFC算法和统计分析的三维模型配准算法。给定源模型和目标模型，以及每个模型上一组对应的特征点序列，本文算法将源模型中的每个顶点匹配到目标模型中的一个顶点，建立源模型与目标模型之间的对应关系。本算法要求目标模型是三角面片模型或者可转化为三角面片模型。聚类是这样一种数据处理技术，它将复杂数据集分解为若干数据子集(聚类)，使各子集内的元素与子集之间的元素相比具有某种相似性。平衡层次面片聚类（BHFC）算法是面片层次聚类算法（HFC）的改进。BHFC算法将面片模型从底向上进行迭代聚类，每次聚类合并的结果作为下次合并的输入，如此建立模型的二叉树结构的分区，并使二叉树的每一层的面片子集保持相对的平衡结构。在BHFC算法实现过程中，对偶图和优先级队列等数据结构被用于对算法进行简化和加速。本文的配准算法从用BHFC算法建立目标模型的平衡二叉树开始。对源模型中的每个顶点，算法利用源模型与目标模型的特征点序列建立目标模型空间的匹配函数。匹配函数是用于衡量源模型和目标模型中顶点匹配度的度量标准。然后算法利用对二叉树结点所对应的面片子集的统计分析，逐步缩小对应顶点可能存在的区域。具体做法是，从二叉树的根节点开始，利用面片子集的匹配度量和度量比函数，自顶向下逐层地迭代剔除对应顶点不可能出现的面片子集。当面片子集包含顶点少于预设阈值或迭代达到二叉树底层，算法直接比较面片子集中各顶点的匹配函数值寻找对应顶点。此迭代过程对源模型中每个顶点进行，建立起源模型与目标模型顶点之间的对应关系。

Registration is fundamental issue in many scientific research and application areas. Given two 3D models, registration algorithm transforms one model (source model) so that it corresponds to the other model (target model) in some sense (for example, geometric or topological). This paper proposes the 3D model registration algorithm based on BHFC and statistical analysis. Given a source model and a target model, as well as a set of corresponding feature points on them, the algorithm matches every point in the source model to one point in the target model, constructing the corresponding relations between models. The algorithm requires the target model is or can be converted to triangle meshes. Clustering is the data-processing technology that divides complex data set into subsets (clusters), so that the data in each subset share some common trait. Balanced Hierarchical Face Clustering (BHFC) is the improvement of Hierarchical Face Clustering (HFC) algorithm. BHFC iteratively merges clusters in the bottom-up way, and the result of one merger is the source of afterward merger. In this way, BHFC creates a binary tree structure of initial model, whose clusters on every hierarchy are relatively balanced. In the implementation of BHFC, data structures such as dual graph and priority queue are employed to accelerate the algorithm.This paper’s registration algorithm begins with constructing balanced binary tree of target model. For every point in the source model, the algorithm utilizes feature points of source and target model to establish a match function, which is used to measure the corresponding relation of points. Then, the algorithm makes statistical analyses to mesh subsets correspond to vertices of the binary tree, and gradually narrows the possible subsets of corresponding point. The specific approach is, start from the root of tree and in the top-way way, use match function to rule out subsets that corresponding point cannot be in. When the point number in the left subsets is less than the default threshold or the bottom of binary tree is reached, the algorithm focus on direct comparison of match function value of left points, finding the corresponding point. These iterations are processed to every point in the source model and the point corresponding relation is thereby established.