在计算机图像配准领域中,点模式匹配问题的研究在其中占据极其重要的地位,是众多学者研究的重点内容,广泛应用在诸如图像识别、追踪运动物体、安全等领域。该问题是一个NP问题,由于问题背景广泛、几何变化复杂、外界干扰众多的缘故,目前的研究工作仍处于探索阶段,解决该问题仍然是一项具有挑战性和实用价值的工作。本文研究了多种点模式匹配的算法,尤其着重研究了以形状上下文为基础的匹配算法。形状上下文方法的核心思想是利用某个点周围其他点的分布作为其特征,以三维点集的整体分布情况作为匹配要素,这导致该算法受异常点分布影响较大,鲁棒性不强;另外,此算法对混合点集的匹配效果很差。因此,本文提出了一种新的三维点模式匹配方法——基于聚类的引力形状上下文算法模型(Gravitational Shape Context,GSC)。该算法的核心思想是首先利用聚类算法在无先验知识的情况下拆分混合点集,然后将待匹配的点集和混合点集的每个簇进行匹配,获得最佳映射。本文的创新点包括四个方面:(1)基于3s原则和Tukey箱型图混合算法,对点集进行过滤,删除离群点。(2)利用聚类算法对混合点集进行拆分,让待匹配点集与混合点集的各个簇进行匹配。(3)受到万有引力公式启发,重新定义了特征提取方式,简化了原本同心球区域分割的特征提取方式。(4)提取三维空间内某个点的特征时,本文提出了一种新的计算方式计算空间相对不变点,可以根据不同簇的聚类中心,并结合当前簇内点的数量大小来分配权值,计算出空间相对不变点。在算法的匹配度计算环节,本文提出了一种基于团匹配验证方法。将原本待匹配的点集经过旋转平移放缩等刚性变换得到一个新点集,让三个点集两两匹配,找到各自的映射点对。然后利用团匹配算法构建多点集点对间的无向图,找到所有点集中的公共点。将此公共点视为最终正确匹配的点,计算匹配度。本文的实验数据是三维空间内的模拟数据和物体的真实数据,用来测试本文提出的基于聚类的引力形状上下文算法和团匹配验证结果,并将本文提出的算法和其他点模式匹配算法进行比较。实验结果显示,基于聚类的引力形状上下文模型算法在混合点集匹配的问题中正确匹配率较其他算法优势明显。