一种主动形状模型的对应点搜索方法及终端设备

摘要

本发明提供一种主动形状模型的对应点搜索方法及终端设备，根据形状模型的参数生成模型轮廓的标记点，将所述标记点划分为多个组，对每个标记点分配一个组号；确定轮廓曲线在每个标记点的法线方向；沿每个标记点对应的法线方向，在图像中搜索最匹配的特征点，特征点作为标记点的对应点。这样，在搜索对应点的过程中，通过分组信息明确对应点的提取特征的方向，增加了对应点搜索的可靠性。再利用轮廓的尺寸信息实现对应点的多尺度搜索过程，增加了可靠性和稳定性；还有就是利用主成份分析方法改进了匹配算法，增加了匹配的速度及提高了可靠性。

说明书

技术领域

本发明涉及一种图像处理技术领域，特别涉及一种主动形状模型的对应点搜索方法及终端设备。

背景技术

主动形状模型的形状由标记点(landmark)来表示，标记点是一种人为规定的用于形状描述的点，顺序连接标记点可以勾绘出一个轮廓的形状，如人手、头部等的轮廓，可以用数个标记点来勾绘。

主动形状模型建立在大量的训练形状样本的基础之上，实际操作过程是先用手工的方法采集许多样本轮廓的点集，并基于这于点集构造出形状模型。主动形状模形采用主成分分析的方法进行建模。一个主动形状模形主要由两部分组成：1)模板轮廓，2)形状参数。设表示一个N个标记点的轮廓，将这2N个数据按顺序排列下来，可以行成一个2N维向量x，主动形状模型由下面的公式(1)表示：

$x=\bar{x}+\mathrm{Pb}---\left(1\right)$

这里，为模板形状，也是训练集的平均轮廓，P为经训练学习得到的2N×M维矩阵，b为M维向量，也就是形状参数，改变b的分量的取值，可以在模板形状的基础上得到相应的形状变形。即不同的分量取值产生不同的形状变形。

在上述模型的基础上再加上形状的平移、旋转及尺度变换，则构成如下的形状模形：

$X=M[s,\theta ,x_t,y_t](\bar{x}+\mathrm{Pb})---\left(2\right)$

这里x_t，y_t分别为水平及竖直方向的平移参数，s，θ分别为尺度及旋转角度参数，M为姿态及平移变换算子，变换方程如下式：

$M[s,\theta ,x_t,y_t]\left(\begin{array}{c}x\\ y\end{array}\right)\left(\begin{array}{cc}s\cos \theta & -s\sin \theta \\ s\sin \theta & s\cos \theta \end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)+\left(\begin{array}{c}{x}_t\\ y_t\end{array}\right)---\left(3\right)$

主动形状模型由两部分组成：1)对应点的搜索；2)主动形状模型的拟合，其中：

1)对应点的搜索

对应点的搜索过程主要由下面三个步聚组成。第一步先根据形状模型的参数s，θ，x_t，y_t，b按照公式(2)及公式(3)生成模型轮廓的标记点；第二步确定轮廓曲线在每个标记点的法线方向；第三步对每个标记点沿其对应的法线方向在图像中搜索最匹配的特征点，搜索到的点即为标记点的对应点。

具体的搜索过程如图1所示。在图1中，实线为模型轮廓，虚线为图像中的候选目标的边缘，空心圆为搜索到的对应点。

2)主动形状模型的拟合

主动形状模型的拟合就是指对搜索到的对应点按形状模型(公式3)，依照最小二乘法的原则，求取旋转、尺度、平移以及形状参数的估计的过程。设向量Y代表由搜索到的对应点构成的向量，则拟合算法就是求取公式(4)的最小二乘解。

$(\hat{s},\hat{\theta },{\hat{x}}_t,{\hat{y}}_t,\hat{b})=\underset{(s,\theta ,x_t,y_t)}{\arg \min }{\left|\right|Y-M[s,\theta ,x_t,y_t](\bar{x}+\mathrm{Pd})\left|\right|}^2---\left(4\right)$

主动形状模型的算法如下：

输入：1)当前第k帧灰度图像I(k)，2)上一帧图像的姿态参数s(k-1)，θ(k-1)，x_t(k-1)，y_t(k-1)以及形状参数b(k-1)

输出：与I(k)中目标的轮廓相匹配的姿态参数s(k)，θ(k)，x_t(k)，y_t(k)以及形状参数b(k)。然后进行以下步骤：

1)、初始化s(k)＝s(k-1)，θ(k)＝θ(k-1)，x_t(k)＝x_t(k-1)，y_t(k)＝y_t(k-1)，b(k)＝b(k-1)

2)、利用公式(2)计算生成轮廓模型的标记点

3)、对于轮廓模型的每一个标记点在I(k)中按照法线方向搜索目标点

4)、根据模型点与搜索到的目标点，按照公式(4)更新姿态参数s(k)，θ(k)，x_t(k)，y_t(k)以及形状参数b(k)

5)、若收敛或到达限定的循环次数，则步骤6)，否则转步骤2)

6)、结束

现有技术提出了在灰度图像中搜索对应点的方法，搜索对应点的过程是一种特征匹配的过程。具体匹配过程由下面两步实现：1)模型训练，2)模型匹配，其中：

1)模型训练过程

模型训练过程是利用大量的训练图像发现每一个标记点处的灰度级信息的过程，也就是对在训练图像中的每个标记点处提取的特征向量的统计学习过程。具体方法为：设N_j为第j个标记点的训练样本数，为第j个标记点在第k(k＝1，2，....N_j)个训练图像中提取的特征向量。所有的标记点的特征向量的维数均为M。计算特征向量的均值及协方差：

${\bar{v}}_j=\frac{1}{N_j}\underset{k=1}{\overset{N_j}{\Sigma }}{v}_j^k--\left(5\right)$

$C_j=\frac{1}{N_j-1}\underset{k=1}{\overset{N_j}{\Sigma }}(v_j^k-{\bar{v}}_j){(v_j^k-{\bar{v}}_j)}^T---\left(6\right)$

特征向量的提取过程由下面三个步聚完成：

1.在第k个训练图像中，在第j个标记点，沿着轮廓模型的法线方向获得图像的灰度值，得到：这里np为沿法线方向提取灰度级的个数。具体的来说，设为单位法线方向向量，为第j个标记点，g^k代表灰度图像，则这里step为沿方向采样图像数据的步长。

2.计算灰度级差分：

${\mathrm{dV}}_{\mathrm{jk}}=[g_{j,1}^k-g_{j,0}^k,g_{j,2}^k-g_{j,1}^k,...,g_{j,\mathrm{np}-1}^k-g_{j,\mathrm{np}-2}^k]$

3.对差分进行归一化：

$S_{\mathrm{jk}}=\underset{i=0}{\overset{\mathrm{np}-2}{\Sigma }}|g_{\mathrm{jk},i+1}-g_{\mathrm{jk},i}|$

v_jk＝dV_jk/S_jk

2)模型匹配

模型匹配过程就是利用经训练学习得到的每个标记点的灰度信息，在测试图像上对每一个标记点沿轮廓模型的法线方向提取特征向量序列，进行匹配的过程。

设为在当前一帧图像中的第j个标记点沿着法线方向提取的特征向量序列，nv为提取的特征向量的个数，每个特征向量的提取方法与训练过程中的提取方法相同。模型匹配过程就是按照Mahalanobis距离最小化的原则找到对应点。

即：

$i_{\mathrm{find}}=\arg \underset{i}{\min }\sqrt{{(z_j^i-{\bar{v}}_j)}^T{C_j}^{-1}(z_j^i-{\bar{v}}_j)}---\left(7\right)$

这里为经训练学习获得的均值向量与协方差矩阵。

由图2所示，设p_j为在图像中的第j个标记点确定的法线方向。显然，由上述特征匹配的特征向量的提取过程可知，沿p_j及-p_j两个相反方向提取的特征向量具有很大的差异。而原方法中并没有对其进行区分，这样在训练的过程中会因为这个不一致性导致统计特性的缺失，另外，在匹配的过程中也容易造成误匹配。图3为易造成主动形状模型的对应点搜索误匹配的示意图。在该图中，P点为标记点，显然，(或者)都有可能作为在P点的搜索方向。由于原算法并未明确指定搜索方向，因而在搜索P点的对应点时，易造成A或C作为P的对应点(误匹配)。

发明内容

鉴于上述现有技术的不足之处，本发明的目的在于提供一种主动形状模型的对应点搜索方法及终端设备，增加了主动形状模型的对应点搜索的可靠性。

为了达到上述目的，本发明采取了以下技术方案：

一种主动形状模型的对应点搜索方法，其特征在于，包括：

根据形状模型的参数生成模型轮廓的标记点，将所述标记点划分为多个组，对每个标记点分配一个组号；

确定轮廓曲线在每个标记点的法线线方向；

沿每个标记点对应的法线方向，在图像中搜索最匹配的特征点，所述搜索到的特征点为标记点的对应点。

其中，所述搜索到的特征点为标记点的对应点之后，进一步包括：按照形状模型，求取所述搜索到的对应点旋转、尺度、平移和形状参数。

其中，根据形状模型的参数生成模型轮廓的标记点，具体包括：

根据形状模型的参数s，θ，x_t，y_t，b按照公式和公式生成模型轮廓的标记点；其中，x_t，y_t分别为水平及竖直方向的平移参数；s，θ分别为尺度及旋转角度参数；M为姿态及平移变换算子；P为经训练学习得到的2N×M维矩阵；b为M维向量，即形状参数；为模板形状，即训练集的平均轮廓；

其中，所述搜索方向与指向每组标记点的中心点的方向的夹角成锐角。

其中，在图像中搜索最匹配的特征点过程中包括：提取每一个标记点的特征向量，其中，在该提取每一个标记点的特征向量中，其采样的步长是随形状模型的尺寸自适应变化的。

其中，在图像中搜索最匹配的特征点过程中，利用主成份分析法获取所述对应点的公式为：其中：为特征值，d为特征向量的维数，U_j为正交矩阵，为第j个标记点的均值向量值，为在当前一帧图像中的第j个标记点沿着法线方向提取的特征向量。

本发明还提供一种终端设备，包括：

标记点划分单元，用于根据形状模型的参数生成模型轮廓的标记点，将所述标记点划分为多个组，对每个标记点分配一个组号；

方向确定单元，用于确定轮廓曲线在每个标记点的法线方向；

匹配单元，用于沿每个标记点对应的法线方向，在图像中搜索最匹配的特征点，所述搜索到的特征点为标记点的对应点。

其中，该终端设备，还包括：

参数获取单元，用于按照形状模型，求取所述搜索到的对应点旋转、尺度、平移和形状参数。

其中，所述标记点划分单元，用于：

根据形状模型的参数s，θ，x_t，y_t，b按照公式和公式生成模型轮廓的标记点；其中，x_t，y_t分别为水平及竖直方向的平移参数；s，θ分别为尺度及旋转角度参数；M为姿态及平移变换算子；P为经训练学习得到的2N×M维矩阵；b为M维向量，即形状参数；为模板形状，即训练集的平均轮廓；

其中，所述匹配单元，在该提取每一个标记点的特征向量中，其采样的步长是随形状模型的尺寸自适应变化的。

本发明提供一种主动形状模型的对应点搜索方法及终端设备，通过将构成轮廓的标记点进行分组，将所述标记点划分为多个组，对每个标记点分配一个组号；这样，在搜索对应点的过程中，通过分组信息明确对应点的提取特征的方向，增加了主动形状模型的对应点搜索的可靠性。另外，在利用轮廓的尺寸信息实现对应点的多尺度搜索过程，增加了可靠性和稳定性；还有就是利用主成份分析方法改进了匹配算法，增加了匹配的速度及提高了可靠性。

附图说明

图1是现有技术提供的主动形状模型的对应点搜索示意图；

图2是现有技术提供的特征提取的方向示意图；

图3是现有技术提供的主动形状模型的对应点搜索误匹配的示意图；

图4为本发明实施例提供的标记点的分组及有向搜索方向；

图5为本发明实施例提供的主动形状模型的对应点搜索方法的流程图；

图6为本发明实施例提供的终端设备的结构示意图。

具体实施方式

本发明实施例提供一种主动形状模型的对应点搜索方法及终端设备，根据形状模型的参数生成模型轮廓的标记点，将所述标记点划分为多个组，对每个标记点分配一个组号；确定轮廓曲线在每个标记点的法线方向；沿每个标记点对应的法线方向，在图像中搜索最匹配的特征点，所述搜索到的特征点为标记点的对应点。这样，在搜索对应点的过程中，通过分组信息明确对应点的提取特征的方向，增加了主动形状模型的对应点搜索的可靠性。

如图5所示，本发明实施例提供的主动形状模型的对应点搜索方法包括：

101、根据形状模型的参数生成模型轮廓的标记点，将所述标记点划分为多个组，对每个标记点分配一个组号。

在本实施例中具体为：根据形状模型的参数s，θ，x_t，y_t，b按照公式和公式生成模型轮廓的标记点；其中，x_t，y_t分别为水平及竖直方向的平移参数；s，θ分别为尺度及旋转角度参数；M为姿态及平移变换算子；P为经训练学习得到的2N×M维矩阵；b为M维向量，即形状参数；为模板形状，即训练集的平均轮廓；

在本实施例中：将标记点划分为多个组，对每个标记点分配唯一个组号。对标记点进行分组的目的，是确定每个分组的中心，而对每一个标记点指定一个分组号，是用来确定每个标记点的法线方向。图4为一对标记点进行分组的一种示意图，该形状的标记点按形态分为6组，每组的标记点构成如表1所示。每一个标记点分配的组号如表2所示。设第i组由标记点构成，G_i为构成该组的标记点数目。则该组的中心点的坐标由公式(8)确定：

$x_i^c=\frac{1}{G_i}\underset{k=1}{\overset{G_i}{\Sigma }}{x}_i^k,$$y_i^c=\frac{1}{G_i}\underset{k=1}{\overset{G_i}{\Sigma }}{y}_i^k---\left(8\right)$

如图2所示，设L_j为第j个标记点，i为该标记点分配的组号，为i组的中心点，p_j为提取特征向量的单位法线方向，则本实施例改进的搜索方向该q_j按公式(9)进行计算。这里<·>代表内积的计算，sign为符号函数，其定义如公式(10)所示，

$q_j=\mathrm{sign}(<\overrightarrow{L_j{G}_i^c},p_j>)p_j---\left(9\right)$

$\mathrm{sign}\left(x\right)=\left(\begin{array}{cc}1,& x\ge 0\\ -1,& x<0\end{array}\right)---\left(10\right)$

从公式(9)可以看出，改进的搜索方向必定与指向中心点的方向的夹角成锐角，也就是明确指定了搜索方向总是指向组的“内部”方向的。关于指向的示意图如图4所示的箭头所示。

  组号  标记点号  Group I  1，2，3，4，5，6，7，8  Group II  8，9，27，28，36，1  Group III  9，10，19，20，27  Group IV  10，11，12，13，14，15，16，17，18，19  Group V  20，21，22，23，24，25，26，27  Group VI  28，29，30，31，32，33，34，35，36

表1：每个分组分配的标记点

表2：每个标记点分配的用于确定法线方向的分组号

102、确定轮廓曲线在每个标记点的法线方向。

在模型训练过程是利用大量的训练图像发现每一个标记点处的灰度级信息的过程，也就是对在训练图像中的每个标记点处提取的特征向量的统计学习过程。其中，需要确定轮廓曲线在每个标记点的法线方向，

103、沿每个标记点对应的法线方向，在图像中搜索最匹配的特征点，所述搜索到的特征点为标记点的对应点。

在本实施例中，在图像中搜索最匹配的特征点过程中，需要提取每一个标记点的特征向量。在进一步的实施例中，在灰度图像中沿法线方向提取特征向量时，其采样的步长是随形状模型的尺寸自适应变化的，因为模型尺寸越大，步长因子也就越大。

本实施例按公式(11)定义了模型的尺寸

$\mathrm{size}=\frac{1}{2}\left(\underset{j}{\max }\right\{x_j\}+\underset{j}{\max }\{y_j\}-\underset{j}{\min }\{x_j\}-\underset{j}{\min }\{y_j\left\}\right)---\left(11\right)$

这里，size为定义的形状模型的尺寸，为形状模型的N个标记点坐标。基于该定义，设L_j为第j个标记点，q_j为按公式(11)进行计算的单位向量。g代表灰度图像，则改进后的特征提取过程中的灰度值如公式(12)：

V_j＝[g_j，0，g_j，1，g_j，2，...，g_j，np-1]＝

                                                                (12)

[g(L_j+τ·size·0·q_j)，g(L_j+τ·size·1·q_j)，...，g(L_j+τ·size·(np-1)·q_j)]

这里τ为一固定取值的比例因子，常取为1.0。

另外，在基于Mahalanobis距离匹配对应点时，直接按公式(7)进行计算具有较高的复杂度，影响算法的实时性能。为此本实施例的进一步的实施例提出采用基于主成份分析的计算方法。具体过程是：首先按奇异值值分解，将协方差矩阵C_j表示公式(13)：

$C_j=U_j{\Lambda }_j{U}_j^T---\left(13\right)$

这里，U_j为正交矩阵，A_j为对角矩阵，设特征值为(d为特征向量的维数)，则：

${\Lambda }_j=\left(\begin{array}{cccc}{\lambda }_j^1& & & \\ & {\lambda }_j^2& & \\ & & ...& \\ & & & {\lambda }_j^d\end{array}\right)---\left(14\right)$

这样，

$C_j^{-1}=U_j{\Lambda }_j^{-1}{U}_j^T---\left(15\right)$

将公式(15)代入(7)式，得到：

$i_{\mathrm{find}}=\arg \underset{i}{\min }\sqrt{{(z_j^i-{\bar{v}}_j)}^T{U}_j{\Lambda }_j^{-1}{U}_j^T(z_j^i-{\bar{v}}_j)}---\left(16\right)$

设则上式变为：

$i_{\mathrm{find}}=\arg \underset{i}{\min }\sqrt{\underset{k=1}{\overset{d}{\Sigma }}\frac{{\left(u_j^k\right)}^2}{{\lambda }_j^k}}---\left(17\right)$

为避免零特征值造成计算溢出，常用公式：来替换上公式(17)中的这里σ²为一小的正常数，以保证计算的稳定性。对比公式(7)与公式(17)，可见计算复杂度大大降低了。

应当理解的是，对本领域普通技术人员来说，可以根据上述说明加以改进或变换，而所有这些改进和变换都应属于本发明所附权利要求的保护范围。