基于HMM和仿射不变矩三维模型归类与检索算法

强会英，李雨虹，王洪申，杨笑蕊

（1.兰州交通大学 数理学院，兰州 730070；2.兰州理工大学 机电工程学院，兰州 730050）

0 引言

对机械零件三维模型的产品设计时，找出已有相似性产品并推断其功能结构和理念，可以有效重用各环节的设计成果，即如何快速地从大量的实例中检索出所需要的相似性案例成为急需解决的问题。特征提取是三维模型相似性归类与检索的重要步骤，如何使提取的特征具有鲁棒性是实现模型归类与检索的关键。不变矩是模型的相似性归类与检索中重要而有效的特征提取方法并且已经成为使用较为广泛的模型形状描述子之一。Hu[1]于1962年第一次系统的提出不变矩的理论，他用代数不变量理论推到了7个经典的不变矩，具有平移、旋转和尺度不变性，但该矩也有一些缺点，其中之一是随着矩的阶数的升高计算量会迅速增长，另一个缺点是这些矩不是源于正交函数族，所以包含了大量的冗余信息，尽管存在这些固有的局限性，但其经常被用作模型形状的首选描述子。Teague[2]在Hu不变矩的基础上推导出了基于正交多项式的Zernike矩，使用Zernike矩可以很容易的计算任意高阶矩不变量。D.Shen等[3]提出了基于小波变换的特征提取方法即小波矩不变量，李晓兵等[4]，张虹等[5]进一步的将小波矩用于图像和目标的识别中，并取得了很好的效果。仿射不变矩在与视角无关的目标识别中起到至关重要的作用，不仅被广泛的应用于图像发生仿射形变的任务中，也经常被用于替代投影不变量。第一次尝试推导仿射变换下的矩不变量可在文献[1]中找到，但有少许错误，30年后，Reiss[6]，Flusser[7]和Suk[8]分别独立的发现并更正了这一错误，发表了新的仿射不变量集合，此后，李迎春等[9]将仿射不变矩与人工神经网络相结合用于飞机图像的模式识别，路鹰[10]，徐胜等[11]将仿射不变矩用于三维模型的识别。Hu不变矩和仿射不变矩是图像在整个空间中的统计特性，当从不同的角度拍摄时，三维物体的正等测轴测图会发生形变，也就是仿射变换，这时，只用Hu不变矩反映图像的特征是不够的，仿射变换被证明是模拟图像视点变换的最佳方法即该变换具有仿射不变性。匡逊君等[12]结合这两种不变矩各自的优点，使用组合不变矩结合SVM分类器进行图像识别，当图像发生形变时，能够稳定、可靠地识别形状差异较大的特征，提高了分类的准确度并可以进一步地扩大应用范围。

三维模型的归类是将未知模型划分到某个预先定义的模型类别中，即首先确定该模型所属的类别，然后在此特定类别的范围内进行检索，从而减小了搜索范围。因此，对海量三维模型进行正确归类与检索有着十分重要的社会价值和经济意义。传统的归类方法在处理小样本问题时不仅容易出现过学习现象，而且有可能会导致算法的推广性和学习的性能差，使得在处理非线性问题时算法过于复杂。统计学习理论是一种专门针对小样本的统计理论，基于统计学习理论的隐马尔科夫模型是一种新的模型识别方法，不仅能够较好的解决小样本的学习问题，而且实现简单，算法训练时间短，识别率稳定。2002年，HMM广泛应用于平面物体的归类问题中[13]，后来Panuccio等[14]和刘小明等[15]将HMM用于基于内容的三维物体的识别中，郭竞等[16]针对三维模型的归类问题，提出了一种基于HMM和最大期望算法的三维模型自动归类方法并取得了很好的效果。故本文将Hu不变矩的7个分量V1，V2，…，V7和仿射不变矩的三个分量I1，I2，I3组合成一个包含10个特征元素的组合不变矩，通过隐马尔科夫分类模型进行机械零件的相似性归类与检索。

1 基于HMM的机械零件分类

隐马尔科夫模型（Hidden Markov Model，HMM）[17]是一个双重随机过程，其中一个描述状态转移序列，另一个是描述状态与观测序列之间的关系，该模型由五种元素构成，即 λ ={ π ,A,B,N,M}，其中N为隐状态的个数，M为不同的观测输出个数，π为初始状态概率分布矩阵，A为状态转移概率矩阵，B为状态输出概率矩阵。HMM作为一种统计分析模型，具有极强的建模能力和模式分类能力，它创立于20世纪70年代，80年代得到了传播和发展，成为信号处理的一个重要方向，现已成功地用于图像处理，语音识别，行为识别，文字识别以及模式分类等领域[18]。本文的研究是利用HMM来构建机械零件三维模型的分类识别模式。基于HMM的机械零件的分类方法如图1所示。

图1 基于HMM的机械零件分类结构框图

由图1可知，基于HMM的机械零件的分类过程为：首先使用Sobol算子提取三维模型的轴侧投影图，然后对该图进行Hu不变矩和仿射不变矩的特征提取，其次将提取到的特征值作为HMM的观测输入值，选取一部分作为标准样本训练初始的HMM，得到HMM的优化模型，将另一部分特征值输入该优化模型，进行检测，最后比较HMM的输出对数似然函数值，依据HMM的模式识别方法，得出机械零件的识别结果。

2 机械零件三维模型的特征提取

2.1 机械零件三维模型的表示

由于三维模型中含有的信息量大，直接作为检索对此无法满足速度的要求，因此，通常将三维模型进行特征提取，并形成描述子，通过描述子之间的比较实现模型检索。机械零件三维模型正等测轴测图的表达首先将该模型调整成轴测图的位置，然后取得其图像，再用Sobol算子[19]对图像的边缘轮廓图进行提取，获得如图2所示的机械零件三维模型及其轴测图外部轮廓。

图2 Sobol算子提取机械零件三维模型轮廓边缘

2.2 特征提取

对机械零件的正等测轴测图进行特征提取时，在现实场景下，外界因素会影响物体成像，其中最困难的问题之一是如何从任意尺度和视角所获取的同一场景的图像中提取不变的特征。当从不同的角度拍摄时，三维物体会发生形变，也就是仿射变换，这时，只用Hu不变矩反映目标物体的特征是不够的，仿射变换被证明是模拟图像视点变换的最佳方法，Jan Flusser等体提取了仿射不变矩作为特征，并证明在物体图像发生平移，比例，旋转，倾斜变换下仍具有不变性。仿射不变矩与Hu矩一样，也是源于代数不变性的，由Hu矩演变而来。通过将坐标原点平移到目标轮廓的中心（归一化），可以实现图像仿射不变矩的特征提取，从而进行图像的归类与识别。故本文将Hu不变矩与仿射不变矩各自的优点相结合形成组合不变矩，作为HMM的特征输入值。对于二维连续函数f（x，y），中心矩定义为：

归一化的中心矩为：

利用归一化的中心矩，可以获取对平移，缩放，镜像和旋转都不敏感的7个不变矩，定义如下：

离心率代表了图像长轴与短轴之间的比值，满足几何变换的不变性。离心率E的计算公式为：

仿射不变矩就是一种经过仿射变换后依然保持不变的特征量，我们只选取前3个仿射不变矩参与图像的相似性归类与检索。

3 算法原理及实现

3.1 算法原理

通过MATLAB软件对机械零件三维模型的轴侧投影图提取上述7个Hu不变矩和3个仿射不变矩形成组合不变矩的特征值，如表1（只列出部分）所示，然后将这些特征值通过排序编码的算法进行编码，如表2所示。将编码后的10维特征向量作为模型的输入观测值，利用B-W算法进行训练，获得HMM的λ优化模型，本文使用HMM模型中添加比例因子的多观测值的B-W算法，公式如下：

参数重估公式为：

算法训练的过程如下：

首先收集形状各异的K类图像，将每一类图像中的若干图像分为两部分，一部分用于样本对于初始模型的训练，另一部分用来测试模型。根据图像的先验知识首先为其初始一个HMM模型λ，然后利用样本集进行训练，执行如下步骤：

步骤1：已知有K类图像，每类图像中有L个训练样本，即L个观察值序列，n表示迭代次数，初始时刻n=1；

表1 组合不变矩的特征值

步骤6：利用重估式(17)对模型进行参数估计并得到新模型；

步骤7：判断模型参数的迭代收敛条件，计算后验概率的对数似然函数值：

3.2 算法实现

本实验所使用的模型主要来自于ESB模型库[20]。在ESB模型库中选取五类不同的机械零件三维模型，每一类模型中有十个相似模型。这五类模型的代表模型见图3（每一类只列出两个相似模型）。

表2 组合不变矩特征值的编码

图3 机械零件的三维模型

每一类模型中取前5个模型作为训练样本集，将编码后的特征向量作为HMM的观测输入值，通过上面所陈述的添加比例因子的多观测值的B-W算法进行训练。初始模型的参数根据先验知识设定为状态总数N=5，输出观测值的个数M=5，初始概率π=（0.6，0.1，0.1，0.1，0.1），转移概率矩阵A与输出概率矩阵B由MATLAB随机生成，这5类模型最后可以训练出5个优化模型，分别为。接下来进行模型的检验和识别。在本实验中将每一类模型中的10个向量全部用于HMM优化模型的检验与识别，首先计算待识别模型的观测序列在模型下的输出后验概率对数似然函数值logP(Ol|λm),，1≤m≤5，计算取使得最大的模型，即输出似然函数值最大的那一个为待识别模型的所属类别。将本文所提方法Hu不变矩+仿射不变矩+HMM记为算法A，Hu不变矩+离心率+HMM记为算法B，Hu不变矩+仿射不变矩+欧氏距离记为算法C。表3是50个机械零件三维模型使用算法A在五类优化后HMM模型下的检测结果（只列出部分结果）。1号零件在这五类优化模型下的输出对数似然函数值分别为-6.6927，-8.1555，-7.4244，-6.9094，-7.3247，可以看出-6.9094是最大值，故判定该零件所属类别为第四类模型，而实际上1号零件属于第一类模型，所以该识别错误；3号零件在这五类优化模型下的输出对数似然函数值分别为-6.3564，-9.3103，-6.957，-7.479，-7.3542，可以看出-6.3564是最大值，故判定该零件所属类别为第一类模型，识别结果正确。故从表3可以看出，算法A对第一类模型正确识别的结果为8个，第二类模型为10个，第三类模型为9个，第四类模型为9个，第五类模型为6个。而算法B对这五类模型正确识别的结果分别为7，9，6，9，7个，算法C对这五类模型正确识别的结果分别为6，4，3，4，5个。表4和表5是这三种算法的检索结果，图4是这三种检索结果所得的查准率与查全率的效率曲线（由于篇幅限制，只列出优化模型四和优化模型五的检索结果和效率曲线图，并只列出相似性检索结果排列在前9位的图像）。可以看出，当使用相同的HMM这一分类器时，算法A的识别率高于算法B的识别率，是因为在特征提取时仿射不变矩的仿射不变性对于图像具有较高的描述能力，从而提高了识别的准确度；当使用相同的特征描述子Hu不变矩和仿射不变矩时，算法A的识别率高于算法C的识别率，是因为基于统计学习理论的HMM模型具有较强的分类能力并优于传统的基于欧式距离的判别方法。故本文所提算法具有一定的意义和使用价值。

图4 优化模型的检索效率

表4 nut1在优化模型三中的检索结果排序

表5 screw1在优化模型四中的检索结果排序

4 结束语

对机械零件三维模型，本文首先使用Sobol算子提取其轴侧投影图，然后对该图进行Hu不变矩和仿射不变矩形成组合不变矩的特征提取，其次通过排序编码的方法对该特征值进行编码，最后使用HMM模型中添加比例因子的多观测值B-W算法进行训练与识别，并将本文所提算法与另外两种算法Hu不变矩与离心率结合HMM模型模式分类算法与Hu不变矩和仿射不变矩结合欧氏距离的判别算法进行实验与对比，实验结果显示根据本文所提出的算法可以实现机械零件三维物体模型的有效分类与识别，并能取得较高的查全率与查准率。

本文是根据先验知识为HMM模型拟定一个初始值，并通过添加比例因子的多观测值B-W算法进行训练，但是B-W算法本身对初始值很敏感以及其爬山似的迭代搜索方式使训练得到最终的HMM模型对于细节比较丰富的机械零件的判别可能存在一定的误差，因此接下来进一步的研究内容是在HMM模型的初值选取和训练算法上做进一步的改善和优化。