物体识别是计算机视觉领域最重要的问题之一.目前识别率较高的方法是基于纹理、颜色等局部特征的机器学习方法, 而这些向量形式的特征并不是我们人类可以直接理解的特征.形状是人类视觉认知的主要特征之一, 基于形状的匹配方法^[1-3]已被很多学者应用于物体识别、字符识别和图像检索等领域中.形状表示作为计算机视觉的基本问题尽管已经被研究了几十年, 近些年来国内外对它的研究依然很活跃.形状主要有点集、轮廓和骨架三种描述方式.其中, 基于骨架的表示方式是一种将形状理想化细化的一种方式, 它不仅包含了原物体的几何特征, 还保留了原物体的拓扑结构; 骨架作为一种全局特征, 可以用图模型简练地表达, 用骨架清晰地表示出物体的结构特征具有极其重要的意义.因此, 骨架的提取和描述吸引了大量学者的关注, 并取得了很多重要的研究成果.例如, 2009年Bai等^[4]通过学习同类物体的骨架信息实现目标的检测; 文献[5-9]实现了基于骨架的形状分类; 文献[10]在文献[11]所提的骨架思路基础上, 基于离散曲线演化进行剪枝, 并实现手写字符识别等.

骨架, 又称为物体的中轴(Medial axis)^[12].传统骨架提取方法主要分为五种类型^[13]:

1)拓扑细化算法(Topology thinning)^[14-15], 又称模拟火烧稻草法.此类算法主要思路是:从所有边界同时向轮廓内部进行细化, 直至得到一维骨架.拓扑细化算法的优点是能得到连通的骨架, 保持了原物体的拓扑结构, 且实现起来简单, 但是它对边界噪声较敏感, 易产生很多较小的分支.

2)基于Voronoi图的离散域算法^[16-17], 即将轮廓多边形内部最大圆盘中心的轨迹作为骨架点.这一行用于第一页末尾Voronoi图方法所提取的骨架精确, 但是易受到边界噪声的影响, 并且时间复杂度较高, 不具有鲁棒性.

3)基于迭代收缩物体轮廓算法^[18-20].该方法直接对近似的形状多边形进行对称轴计算, 容易受边界噪声影响, 并且很难处理有洞的物体形状的骨架.

4)基于距离变换及其改进算法^[21-25].该类算法的主要思路是:首先生成原始模型的距离场, 然后提取并连接距离场中的局部极值点, 最后适当调整细化得到骨架.该类算法可以提取准确的骨架点, 但是时间复杂度较高.

5)基于数学形态学算法^[26-29].该方法可以获得精确的骨架, 但时间复杂度较高.

骨架化算法存在的主要问题是对轮廓细节过于敏感, 容易产生很多小的分支, 从而导致后续的识别工作几乎无法进行.人类视觉总是可以仅关注物体骨架的主要分支, 而忽略一些由于边界轮廓微小变化产生的小分支.因此在骨架化的同时需要对骨架进行剪枝, 目前较好的剪枝效果为Bai等提出的基于离散曲线演化^[30]的骨架剪枝算法^[31]和Shen等提出的基于贝叶斯后验概率的剪枝算法^[32], 所应用的骨架是采用距离变换^[33]方法得到的.虽然这两种算法提取的骨架很精确, 并且没有细小分支, 但是其算法复杂度较高, 运行速度相对较慢.由于在视频监控应用中, 智能监控的需求是实现近似实时的对关键事物进行识别和行为分析, 因此作为基础性算法的骨架化算法需要满足实时处理要求, 这是传统骨架化算法所不能实现的.为满足实时性要求, 本文提出一种快速的骨架提取算法.

本文算法的主要框架为:在轮廓多边形离散曲线演化的基础上, 根据显著凹凸顶点将轮廓多边形进行分块分类; 然后选择平行线族扫描每一个轮廓块, 用割线的中点来近似最大内接圆圆心作为骨架点; 最后连接骨架点得到连通的骨架.虽然本文方法得到的骨架点位置并不是很精确的, 但对形状识别的影响较小, 而且在对自然图像的处理中具有良好的效果, 尤其是在运动行人的骨架提取中, 文中算法所提取的骨架效果良好, 对于后期行人的行为分析具有一定的实用性.重要的是, 与传统算法相比, 该算法时间复杂度低, 当研究的对象是视频图像时, 算法可以达到实时性要求.

1.   骨架提取方法

为了降低骨架提取算法的时间复杂度, 本文主要采用了平行截线法来近似得到形状中轴, 即用一族平行线截取轮廓, 并用截线段的中点来近似轮廓的内接圆圆心, 以下简称截线法.本文中骨架提取算法的主要实现思路为:首先得到二值图像的轮廓, 当处理对象为视频时, 采用背景差分法提取出前景(二值图像); 在对轮廓预处理之后, 基于离散曲线演化, 得到轮廓多边形上对曲线形状影响较大的凹凸顶点, 从而实现原轮廓多边形的分割与分段; 其次, 将对曲线形状贡献较大的凸顶点作为骨架图模型中的端节点, 利用截线法对闭合轮廓块进行中轴(骨架点)提取.最后连接骨架点得到连通的骨架.本文方法提取出的每个骨架分支均是物体形状的主要分支, 从而为物体识别及行为分析提供了较好的全局特征.

1.1   轮廓的表示

关于本文采用梯度方法提取二值图像中物体的边缘并通过边缘扫描得到轮廓链.单连通区域的轮廓只包含一个闭合的轮廓, 而多连通区域的轮廓可以包含多个闭合轮廓.为了方便起见, 本文将轮廓定义为多边形无向图的集合, 并做如下符号化规定.

定义1. 无向图 $C:=G(V, E)$ , 其中, $V=\{s_{0}, s_{1}, \cdots, s_{n-1} \}$ 为顶点集, $E=\{(s_{j-1}, s_j)\colon j=0, 1, \cdots, n-1, $ 下标对 $n$ 取模 $\}$ 为边集, 则称该无向图C为闭合轮廓.多个闭合轮廓的并称为物体轮廓, 记为 $\mathcal{C}=C_1\cup C_2\cup\cdots \cup C_m$ , 其中 ${C_i}(1 \leqslant i \leqslant m)$ 为闭合轮廓, 物体轮廓的点集 $V(\mathcal{C})=\cup_{C\in\mathcal{C}}V(C)$ , 物体轮廓的边集 $E(\mathcal{C})=\cup_{C\in\mathcal{C}}E(C)$ .

1.2   轮廓的离散曲线演化

在图像处理中, 物体的轮廓线不可避免地受到边界噪声的影响, 同时轮廓上一些细小的突起总是会产生小的骨架分支.通常这些小的骨架分支不能描述物体的不变特征, 而且会对识别过程造成一定的干扰, 导致识别不准确.在理论和实验两方面, 离散曲线演化已经被证明是一种有效删除噪声点的方法^[30].离散曲线演化是一种递归删除对多边形形状贡献最小的点, 从而不断简化多边形的方法, 通过不断演化的过程可以得到多层次的轮廓多边形, 进而得到轮廓上显著的凹凸顶点, 即对轮廓形状贡献较大的点, 基于该显著凸顶点可以实现对原轮廓的分段.对于一条闭合轮廓C, $V(C)=(s_0, s_1, \cdots, s_{n-1})$ , $E=\{ ({s_{j-1}}, {s_j})j=0, 1, \cdots, n-1, $ 下标对 $n$ 取模 $\}$ , 离散曲线演化对每一个顶点 $s_i$ 定义一种对形状贡献的度量:

其中, $e_{i-1}$ 表示连接点 $s_{i-1}$ 和点 $s_i$ 的直线段, $e_{i}$ 表示连接点 $s_{i}$ 和点 $s_{i+1}$ 的直线段, 如图 1所示. $l(e_{i-1})$ 和 $l(e_{i})$ 分别表示为线段 $e_{i-1}$ 和线段 $e_i$ 的长度. $\beta(s_i)$ 表示顶点 $s_i$ 处线段 $e_{i-1}$ 和线段 $e_i$ 偏转角的弧度值(下标均对 $n$ 取模).顶点的K值越大, 代表了该顶点对形状的贡献越大.

图 1  顶点s_i处的离散曲线演化

Fig. 1  Discrete curve evolution on vertex s_i

下载: 全尺寸图片 幻灯片

轮廓离散递归演化过程( $DCE(C^0)$ ):

1)依据式(1)计算 $C^0$ 中所有顶点的K值;

2)从 $C^0$ 中删除K值最小的顶点, 重新计算并更新该点相邻的两个顶点的K值;

3)判断当前最小K值是否大于等于阈值 $K^*$ ; 成立则执行4), 否则转至2);

4)递归结束.

定义2. 一个闭合轮廓 $C^0$ , 对 $C^0$ 进行离散曲线演化得到新的闭合轮廓, 记为 $DCE(C^0)=C^*$ , 则称 $C^0$ 为原始闭合轮廓, $C^*$ 为显著闭合轮廓, $V({C^*}) \subset V({C^0})$ .如果点 $s\in V(C^0)\cap V(C^*)$ , 则称S为 $C^0$ 中的显著顶点, 如果S在 $C^*$ 中为凸的, 则称S为 $C^0$ 中的显著凸顶点, 反之称S为 $C^0$ 中的显著凹顶点.

定义3. 给定物体轮廓 $\mathcal{C}$ , 将 $\mathcal{C}$ 中每个闭合轮廓分别执行离散曲线演化后, 得到的显著闭合轮廓的并称为物体显著轮廓, 记为 $DCE(\mathcal{C})=\mathcal{C}^*$ .

为了有效地去除骨架中的细小分支, 与文献[31]中的方法相同, 本文选择显著凸顶点作为轮廓分段的分段点, 将轮廓分段.只有截线段的两个端点位于不同的轮廓分段时, 该截线的中点才被保留下来.(注:当两个显著凸顶点在原闭合轮廓中相邻时, 本文方法选择这相邻两点的中点作为分段点, 而不是将两个点均作为分段点.因为实验发现在原闭合轮廓中相邻的两个显著凸顶点通常使得后续算法产生多余的分叉.)

1.3   轮廓的分割

由于水平截线法无法提取出骨架的水平分支, 轮廓的水平突起会导致水平截线骨架点的截线半径出现急剧增长, 因此需要将轮廓 $\mathcal{C}$ 进行分块.

定义4. 显著闭合轮廓中的凸顶点, 如果该点在显著轮廓中的两条邻边位于水平线的上下两侧, 则称为Ⅰ型显著凸顶点.显著闭合轮廓中的凸顶点, 如果该点在显著轮廓中的两条邻边位于水平线的同一侧, 则称为Ⅱ型显著凸顶点.

Ⅰ型和Ⅱ型显著凸顶点的结构如图 2所示.

图 2  显著凸顶点的分类

Fig. 2  Classification of salient convex vertices

下载: 全尺寸图片 幻灯片

由定义4可知, 轮廓中的显著凸顶点分类为两类, Ⅰ型显著凸顶点和Ⅱ型显著凸顶点.由于Ⅰ型显著凸顶点关联的两条边在不同的轮廓分段上, 因此只有垂直截线才能够得到Ⅰ型显著凸顶点连接的骨架分支, 该分支是趋于水平的.相反地, 对于一个水平分支, 其端点对应的显著凸顶点的两条邻边必然是一条在水平线上方, 一条在水平线下方.因此, Ⅰ型显著凸顶点对应着水平分支.

为了将水平分支分割出来, 只需将Ⅰ型显著凸顶点分割出来, 因此需要找到Ⅰ型点两端的分割点; 1)若Ⅰ型显著凸顶点两端分别连接着一个显著凹顶点, 则这两个凹顶点作为分割点; 2)若Ⅰ型显著凸顶点某一端连接着一个Ⅱ型显著凸顶点, 若这两点间存在凹顶点, 则该凹顶点作为分割点, 否则选择夹角最大的凸顶点作为分割点.连接这两个分割点, 即可将水平分支轮廓从原轮廓中分割出来, 剩下的作为主分支轮廓.分割出的每一个水平分支轮廓中的显著凸顶点都是Ⅰ型的, 主分支轮廓中的显著凸顶点都是Ⅱ型的.(注：对于只有Ⅰ型显著凸顶点而没有Ⅱ型显著凸顶点的轮廓, 可以将轮廓的所有X坐标和 $y$ 坐标交换, 得到转置后的轮廓, 从而将Ⅰ型显著凸顶点转化为Ⅱ型显著凸顶点, 然后再进行处理.)

1.4   近似骨架模型

为满足实时性要求, 本文所提取的骨架点与传统方法骨架化有一定区别, 主要采用截线段的中点来代替最大内切圆圆心作为骨架点.因此需要对骨架点及其获取方式进行重新定义.本文算法将采用水平截线法得到主分支轮廓的骨架, 用垂直截线法得到水平分支轮廓的骨架.水平截线法与垂直截线法是完全类似的, 这里我们只讨论水平截线法.

定义5. 给定一个物体轮廓 $\mathcal{C}$ , 设水平直线 $y=i$ 与 $\mathcal{C}$ 的交点为 $p$ 个, 记为 $x_1^i, x_2^i, \cdots, x_p^i$ (按X坐标从小到大排序), 计算中点 $m_j^i=(x_j^i+x_{j+1}^i)/2$ , 其中 $0\leq j\leq p-1$ ;若点 $m_j^i$ 位于轮廓内部, 并且 $x_j$ 和 $x_{j+1}$ 满足:

1)位于不同的闭合轮廓上;

2)或者位于同一闭合轮廓的不同轮廓分段上, 则称点 $m_j^i$ 为轮廓 $\mathcal{C}$ 的骨架点, 称点 $x_j^i$ 和点 $x_{j+1}^i$ 为骨架点 $m_j^i$ 的生成点, 称点 $x_j^i$ 到点 $x_{j+1}^i$ 的距离的一半为 $m_j^i$ 的截线半径.

因为在用平行于两底的平行线族截取梯形轮廓时, 得到的骨架点在同一条直线上, 所以水平截线法只需选择过轮廓顶点的水平线.例如, 图 3(a)为原始轮廓的一部分, 其中顶点 $A, B, C, D$ 为轮廓多边形中的四个顶点, 过顶点C的水平截线中点为E, 过顶点B的水平截线中点为G, 则由于截线中点 $F$ 的两个生成点分别落在边 $l_2$ 和 $l_5$ 上, 顶点 $F$ 必然会落在直线段 $EG$ 上, 所以过点 $F$ 的水平截线是多余的.因此仅需计算并保留生成点至少有一个是轮廓顶点的骨架点.

图 3  水平截线法的截线中点类型

Fig. 3  Types of middle points of horizontal secant segments

下载: 全尺寸图片 幻灯片

定义6. 当骨架点的两个生成点至少有一个点为闭合轮廓的顶点时, 称这个骨架点为有效骨架点.同时将显著凸顶点也记为有效骨架点, 主分支轮廓中所有有效骨架点的集合记为 $\mathcal{V}_m$ .

由于下文中算法仅考虑有效骨架点的生成与连接, 因此将有效骨架点简称为骨架点.

定义骨架点对应的两个函数来确定 $\mathcal{V}_m$ 中骨架点间的邻接关系.函数 $u, d:{\mathcal{V}_m} \mapsto E(\mathcal{C})E(\mathcal{C})$ , 对于任意 $x\in \mathcal{V}_m$ , 定义 $u(x)=(u_l, u_r)$ , 其中 $u_l$ 为过X的截线段(以左右生成点为端点)在微小上移后左端点所在的边, $u_r$ 为过X的截线段在微小上移后右端点所在的边.类似地, 定义 $d(x)$ 为二元组 $(d_l, d_r)$ , 其中 $d_l$ 为过X的截线段(以左右生成点为端点)在微小下移后左端点所在的边, $d_r$ 为过X的截线段在微小下移后右端点所在的边.

定义7. 定义集合 $\mathcal{E}_m=\{(x, y)\colon x, y\in\mathcal{V}_m\wedge \big(u(x)=d(y)\vee d(x)=u(y)\big)\}$ 为骨架的边集, 则无向图 $(\mathcal{V}_m, \mathcal{E}_m)$ 称为本文算法提取出的主分支轮廓的骨架.

如图 3(a)中, 对于骨架点E, $u(E)=(l_2, l_6)$ , $d(E)=(l_2, l_5)$ , 对骨架点G, $u(G)=(l_2, l_5)$ , $d(G)=(l_3, l_5)$ , 由于 $d(E)=u(G)$ , 所以E和G之间有连边.

根据骨架点的两个生成点的邻边类型, 可以将骨架点分为三类:骨架端点、骨架衔接点和普通骨架点.

1)若骨架点是Ⅱ型显著凸顶点, 如图 2(b)所示, 称这样的骨架点为骨架端点.并规定显著凸顶点C有 $u(C)=(l_1, l_2)$ , $d(C)=\emptyset$ ; 显著凸顶点D有 $u(D)=\emptyset$ , $d(D)=(l_1, l_2)$ .

2)骨架点至少有一个生成点是轮廓的顶点S, 若:

a)点S的两条邻边都在水平线上方, 或者都在水平线下方.如图 4(a)中C, E两点, 骨架点C和骨架点E公共的生成点B的两条邻边均在水平线下方.则 $u(C)=(l_2, l_5), d(C)=(l_2, l_3); u(E)=(l_2, l_5), d(E)=(l_4, l_5)$ .

图 4  衔接截线中点

Fig. 4  Connecting middle points of horizontal secant segments

下载: 全尺寸图片 幻灯片

b)点S一条邻边是水平的, 且该水平线的两条邻边都在水平线上方, 或者都在水平线下方.如图 4(b)中E, F两点, 骨架点E的右生成点A有一条水平邻边AB, 且该邻边AB的两条邻边 $l_2, l_3$ 均在水平线上方.则 $u(E)=(l_1, l_2), d(E)=(l_1, l_4); u(F)=(l_3, l_4), d(F)=(l_1, l_4)$ .

由于这类骨架点通常连接到骨架的分叉点上, 所以称这类骨架点为骨架衔接点.

3)既不是骨架端点也不是骨架衔接点的骨架点称为普通骨架点, 即该骨架点的生成点或者落在一条边上, 或者为轮廓的顶点, 且这个顶点的一条邻边在水平线上方, 另一条邻边在下方.

1.5   骨架的拼接

在用水平截线法得到主分支骨架, 用垂直截线法得到水平分支骨架后, 通过将多个水平分支骨架拼接在主轮廓骨架上, 便可以得到连通的整体骨架.

拼接方法具体描述为:在分割水平分支时将分割线的中点S人为地标注为水平分支轮廓的显著凸顶点, 并作为该水平分支轮廓的轮廓分段点, 即中点S为水平分支骨架的一个端点.在主分支轮廓中, 将中点S标注为主分支轮廓多边形的顶点, 当对主分支轮廓多边形采用水平截线法时, 会产生一个以点S为生成点的骨架点X.在得到主分支骨架和水平分支骨架后, X为主分支骨架中的一个骨架点, 而S为水平分支骨架的一个端点, 通过连接X与S便可实现水平分支骨架与主分支骨架的拼接.

例如, 在图 5(a)中, 顶点C为Ⅰ型显著凸顶点, 以相邻凹顶点A和D作为分割点, 将ABCDA分割出来作为水平分支轮廓, 同时将割线AD的中点L作为该水平分支轮廓的显著凸顶点, 并将L标记为剩余轮廓的顶点, 而作为Ⅱ型显著凸顶点的G点, 则不做切分, 如图 5(b)中所示.通过连接水平分支骨架端点L和主分支骨架点K, 得到最终骨架, 如图 5(c)所示.

图 5  水平分支骨架与主分支骨架的拼接

Fig. 5  Connecting of horizontal branches and main branch

下载: 全尺寸图片 幻灯片

2.   算法的描述及复杂性分析

骨架提取算法主要分为轮廓提取、轮廓简化、离散曲线演化、截线法提取骨架四个部分.其中截线法提取骨架又可以分轮廓分割、截线法和骨架拼接三个阶段.算法1和算法2给出了该骨架提取算法的描述, 其中算法2为算法1的一个子算法.

算法1.骨架提取算法

输入.一个连通区域的二值图像

输出.一个连通的骨架

1)用梯度法提取边缘并通过边缘扫描得到轮廓像素点;

2)用贪心算法得到轮廓的多边形近似;

3)设置阈值 $K_0$ , 将K值过小的多边形顶点删除得到原始轮廓 $\mathcal{C}^0$ ;

4)对原始轮廓 $\mathcal{C}^0$ 进行离散曲线演化, 得到显著轮廓 $\mathcal{C^*}$ ;

5)将显著凸顶点分类为Ⅰ型和Ⅱ型;

6)根据显著凸顶点的类型, 将原始轮廓 $\mathcal{C}^0$ 分割为一个主分支轮廓和多个水平分支轮廓;

7)用算法2中的方法提取主分支骨架和水平分支骨架;

8)将水平分支骨架拼接在主分支骨架上, 得到最终的骨架.

算法2.水平截线法

输入.一个主分支轮廓 $\mathcal{C}$

输出.主分支骨架 $G(\mathcal{V}, \mathcal{E})$

1)将 $\mathcal{C}$ 中的显著凸顶点放到骨架顶点集合 $\mathcal{V}$ 中;

2)按照显著凸顶点对 $\mathcal{C}$ 进行轮廓分段;

3)将 $\mathcal{C}$ 中顶点的 $y$ 坐标从小到大排序, 排除重复值得到序列 $(y_1, y_2, \cdots, y_N)$ ;

4) for $i=1; i < N; i++$ do

5) 将水平线 $y=y_i$ 上的 $\mathcal{C}$ 中顶点放到集合 $\mathcal{U}_{i}$ 中;

6) 将水平线 $y=y_i$ 与 $E(\mathcal{C})$ 中边的所有交点放到集合 $\mathcal{U}_{i}$ 中;

7) 对 $\mathcal{U}_{i}$ 中的点按照X坐标从小到大排序, 并将相邻两点的中点置于截线中点集合 $\mathcal{V}_{i}$ 中;

8) 从 $\mathcal{V}_{i}$ 中删除非有效骨架点;

9) 对 $\mathcal{V}_{i}$ 中的每一个骨架点 $v$ , 计算函数值 $u(v)$ 和 $d(v)$ ;

10) 骨架顶点集合 $\mathcal{V}=\mathcal{V}\cup\mathcal{V}_{i}$ ;

11) end for

12)按照 $\mathcal{V}$ 中每个顶点的 $u$ 值和D值确定边集合 $\mathcal{E}$ .

算法步骤的复杂度分析:算法1中第1)步轮廓提取的时间复杂度为O $(mn)$ ( $m, n$ 为图像的长和宽).算法1中第2)步和第3)步的功能是对轮廓进行简化, 设第1)步提取出的轮廓总顶点个数为 $N_0$ ;第2)步采用贪心算法进行顶点删除实现轮廓的多边形近似, 得到新的轮廓顶点数记为 $N_1$ ;第3)步设定阈值 $K^{0}$ , 将轮廓上K值小于 $K^{0}$ 的顶点一次性删除后(非递归删除), 得到原始轮廓 $\mathcal{C}^0$ , 顶点个数记为 $N$ , 整个过程的时间复杂度为O $(N_0)$ .离散曲线演化(算法1第4)步)在原始轮廓 $\mathcal{C}^0$ 基础上进行, 采用优先队列实现, 每一次迭代选择并删除队列中K值最小的顶点, 同时更新该点两个相邻顶点的K值, 其时间复杂度为O $(N{\rm log}N)$ .轮廓分割过程中需要扫描轮廓中的所有顶点, 时间复杂度为O $(N)$ .截线法需要对原始轮廓中所有顶点的 $y$ 坐标进行排序(算法2中第3)步), 时间复杂度为O $(N\log N)$ .通常情况下水平或垂直截线与轮廓的交点为常数个, 所以算法2中第4) $\sim$ 11)步的时间复杂度为O $(N)$ .算法2第12)步计算骨架的连边集合可以用哈希表实现, 对于每个骨架点 $v$ 生成两组键值对:定义键为 $u(v)$ , 对应的值为 $(v, up)$ ; 定义键为 $d(v)$ , 对应的值为 $(v, down)$ , 其中 $up, down$ 为骨架点键的类型.将键相同但是类型不同的骨架点进行连边, 使得算法在O $(M)$ 的时间内得到最终的骨架, 其中 $M$ 为骨架点的个数.骨架拼接的时间复杂度为O $(k)$ , K为骨架分支的个数.通常情况下骨架点个数与轮廓的顶点个数为同一个数量级, 因此除轮廓提取外本文算法的时间复杂度为O $(N{\rm log}N)$ ( $N$ 为原始轮廓顶点个数), 而除轮廓提取外基于距离变换法的骨架提取算法的时间复杂度仍然为O $(mn)$ .

3.   实验结果与分析

在Intel Core i5、CPU主频1.7 GHz和4 GB内存的64位Windows7操作系统下, 我们基于Microsoft Visual Studio2010编程平台利用Opencv函数库对本文算法进行了C++实现.文献[32]中提出的骨架提取算法是目前最好的骨架提取算法之一, 该文献的作者提供了算法的Matlab实现源码.本节首先讨论了本文算法的实现和参数的选取; 其次在3个数据集上与文献[32]中算法进行了对比实验; 然后, 分析了本文算法在运行时间上的优势; 最后简要说明本文算法对边界噪声的鲁棒性.

3.1   算法实现与参数选取

根据第2节中的算法描述对本文算法进行实现.算法的输入为一张给定的二值图像, 如图 6(a)所示.首先调用Opencv函数库中的轮廓提取函数得到物体的轮廓, 如图 6(b); 然后用贪心算法得到物体轮廓的多边形近似(如图 6(c)); 设定阈值 $K_0$ , 将对多边形形状贡献度小于 $K_0$ 的顶点从近似多边形顶点集中删除, 从而得到原始轮廓 $\mathcal{C}^0$ (如图 6(d)); 在原始轮廓 $\mathcal{C}^0$ 基础上进行离散曲线演化, 得到其显著凹凸顶点, 如图 6(e)所示的轮廓中, 颜色深的顶点为显著凸顶点, 颜色浅的顶点为显著凹顶点; %粉红色顶点为显著凸顶点, 黄色顶点为显著凹顶点; 最后在原始轮廓 $\mathcal{C}^0$ 上采用截线法得到轮廓的骨架(如图 6(f)), 骨架图的骨架点为图上形状内的顶点.的的绿色顶点.

图 6  算法流程结果

Fig. 6  Procedures of the algorithm

下载: 全尺寸图片 幻灯片

由于轮廓预处理中 $K_0$ 值的大小直接影响了原始轮廓的形状和顶点个数, 我们首先考察了不同 $K_0$ 值对原始轮廓 $\mathcal{C}^0$ 的影响, 如图 7所示.容易看出, 通过设置 $K_0$ 对多边形中顶点进行过滤, 可以使得原始轮廓多边形更加简单, 去除轮廓的一些细节变化, 即边界噪声. $K_0$ 值越大, 原始轮廓中的顶点个数 $N$ 值越小.因此选择合适的 $K_0$ 值, 不仅可以简化轮廓的细节部分, 而且还可以加快后续算法步骤.但若 $K_0$ 值过大, 则不但会导致原始轮廓失去物体本来的形状, 而且还会降低所提取的骨架点位置的精确度.根据实验效果, 本文中设定 $K_0$ 为1.5.

图 7  不同的K₀值得到的原始轮廓和顶点个数N

Fig. 7  Original contour with different vertices number N according to different K₀

下载: 全尺寸图片 幻灯片

离散曲线演化过程即迭代删除队列中K值最小的顶点, 并更新该点相邻两顶点的K值, 演化过程停止条件为轮廓上所有顶点的K值均大于阈值 $K^*$ , 此时轮廓上顶点为显著顶点.离散曲线演化中 $K^*$ 值影响了显著顶点的个数, 最终影响骨架中的分支个数.通过在多个数据集上的实验效果观察, 本文中设定 $K^*$ 为15.

3.2   算法的实验结果对比

为了考察本文算法在自然场景中的应用效果, 本文采集了单人行走视频(帧频24/s)和人体手臂伸张视频(帧频24/s)所提取的前景图片作为骨架提取实验的数据集.针对单人行走数据集, 人体手臂伸展数据集和公用数据集Kimia三个数据集上与文献[32]所提算法进行对比实验.

1)行走数据集

行走数据集是对简单场景中单人行走视频采用背景差分法所提取的二值前景图片集.本文算法与文献[32]中算法的部分实验结果如图 8所示.

图 8  行人骨架提取结果

Fig. 8  Skeletons of walking persons

下载: 全尺寸图片 幻灯片

2)人体伸展数据集

人体伸展视频数据集是对在简单场景中的人体四肢伸展视频采用背景差分法所提取的二值前景图片集.本文算法和文献[32]中算法的部分实验结果如图 9所示.

图 9  伸展骨架提取结果

Fig. 9  Skeletons of persons with arms stretched

下载: 全尺寸图片 幻灯片

从图 8和图 9中的实验结果可以看出, 文献[32]中算法得到人体骨架的脚部有多余的分叉, 而本文算法得到的轮廓多边形上的显著凸顶点基本可以代表人体的头部和四肢, 并作为骨架分支的端点出现.此外, 本文算法得到的骨架为由骨架点和骨架点之间的连边构成的图模型, 而文献[32]中算法得到的骨架为一些像素点的集合, 当图像复杂、骨架点较多时会占用较多存储空间.

3)公用数据集Kimia

Sebastian等^[34]给出的Kimia数据库是评价形状匹配性能中常用的数据集之一.该数据库由三个数据集组成, 分别是Kimia 216、Kimia 99和Silhouette. Kimia 99数据库由9类组成, 每类有11个形状, 共99个形状. Kimia 216共有18类形状, 每类有12个形状. Silhouette有13类形状, 共149张图片. 图 10中给出了本文算法和文献[32]中算法的部分实验结果.

图 10  Kimia数据集骨架提取结果

Fig. 10  Skeletons of images from Kimia dataset

下载: 全尺寸图片 幻灯片

从图 10中的实验结果可以看出:与文献[32]中结果相比, 物体主分支轮廓左右极度不对称时, 如Kimia数据集中的倾斜飞机轮廓、大象轮廓等, 本文算法提取的骨架点精确度较差; 而当物体主分支轮廓左右相对对称时, 如Kimia数据集中手掌轮廓、鸟类轮廓和人体轮廓等, 则得到的骨架点精确度较好, 并且能很好地反映原图形的拓扑结构.

3.3   算法的运行时间对比

1)本文算法的各阶段时间分布

本文算法主要分为四个阶段:轮廓提取(算法2中第1)步)、轮廓简化(算法2中第2)、3)步), 离散曲线演化(算法2中第4)步), 截线法提取骨架(算法2中第5) $\sim$ 8)步).算法四个阶段在尺寸为 560\times 2 250$的二值前景图片的平均运行时间结果如表 1所示.从实验结果可以看出本文算法中截线法提取骨架阶段耗时最长.

表 1  图像骨架提取的运行时间

Table 1  The running time of skeletonization

图片大小	原始轮廓顶点数	轮廓提取	轮廓简化	离散曲线演化	截线法提取骨架
1 560×2 250	875	0.0171 s	0.0305 s	0.0045 s	0.1294 s

下载: 导出CSV 

| 显示表格

2)不同尺寸图像的运行时间对比

针对图片尺寸为 $6 \times 225$ 的一张二值行人前景图片, 通过同时增大图片的高度和宽度, 得到增长倍数为1倍到10倍的10张图片.采用本文算法和文献[32]中算法在这10张图片上进行对比实验, 由于这两种算法所提的骨架效果随图片倍数增加效果变化较小(如图 11), 因此仅进行运行时间的对比, 对比结果如表 2所示.

图 11  放大1, 5, 10倍实验结果

Fig. 11  Results of skeletonization with original image, magnified 5 times and magnified 10 times

下载: 全尺寸图片 幻灯片

表 2  不同尺寸图片骨架提取的运行时间对比

Table 2  The comparison of running time of skeletonization of different image sizes

	图片大小	本文算法		文献[32]算法运行时间
		原始轮廓顶点数	运行时间
1	156×225	51	0.0036 s	8.0328 s
2	312×450	100	0.0089 s	18.6070 s
3	468×675	100	0.0125 s	38.2181 s
4	624×900	309	0.0506 s	64.4884 s
5	780×1 125	327	0.0643 s	111.5206 s
6	936×1 350	412	0.0741 s	218.3063 s
7	1 092×1 575	437	0.0922 s	267.5379 s
8	1 248×1 800	598	0.1348 s	410.8053 s
9	1 404×2 025	783	0.1572 s	545.5659 s
10	1 560×2 250	875	0.2128 s	733.5245 s

下载: 导出CSV 

| 显示表格

从表 2中可以看出, 文献[32]中算法的运行时间对图片的尺寸更加敏感, 在图像的长和宽同时放大10倍后, 运行时间超过了10分钟, 是放大前运行时间的91倍, 而本文算法在放大10倍后的运行时间是放大前的59倍, 仍然可以达到实时的效果.

3)在三个数据集上的运行时间对比

本文算法与文献[32]中算法在不同数据集上的单张图片平均运行时间如表 3所示.从实验结果中可以看出本文算法在运行时间上有明显的可满足实时性的优势.

表 3  图像骨架提取的运行时间对比

Table 3  The comparison of running time of skeletonization

	数据集	图片数量	本文算法平均运行时间	文献[32]算法平均运行时间
1	人体伸展视频	420帧	0.0189 s	12.1216 s
2	人体步行视频	186帧	0.0064 s	14.6854 s
3	Kimia 216	216张	0.0094 s	2.2967 s
4	Kimia 99	99张	0.0039 s	1.8257 s
5	Silhouette	145张	0.0096 s	2.3505 s

下载: 导出CSV 

| 显示表格

3.4   骨架鲁棒性分析

给定一张二值前景图片(如图 12(a)所示), 基于中轴理论所得到的的骨架如图 12(b)所示, 可以看出该骨架图存在很多冗余分支, 这些分支均由轮廓边界上的微小变化引起的, 这会在很大程度上降低识别的精确性.文献[32]中算法提取的骨架(图 12(c))和本文中算法提取的骨架(图 12(d))中分支较少, 而且每一个分支都表示了物体轮廓的主要形状.在轮廓边界发生微小形变时, 这两种算法所提取的骨架并不会发生变化, 因此对边界噪声具有一定的鲁棒性.当物体轮廓是人体轮廓时, 本文算法提取的骨架更加简洁, 多数情况下骨架中的分支与人体的头部和四肢是对应的, 这使得本文算法非常适合于基于形状的行人识别问题以及用于步态分析.

图 12  不同骨架提取方法中的骨架分支

Fig. 12  Different skeletons according to different methods

下载: 全尺寸图片 幻灯片

3.5   实验结果分析

与文献[32]中结果相比, 当物体主分支轮廓左右极度不对称时, 如Kimia数据集中的倾斜飞机轮廓、大象轮廓等, 本文算法提取的骨架点精确度较差; 而当物体主分支轮廓左右相对对称时, 如Kimia数据集中手掌轮廓、鸟类轮廓和人体轮廓等, 则得到的骨架点精确度较好, 并且能很好地反映原图形的拓扑结构.由图 8和图 9可以看出, 轮廓多边形的显著凸顶点基本可以代表人体的头部和四肢, 并且是作为骨架分支的端点出现, 由此说明该算法对于人体的运动骨架提取效果较好.表 2和表 3显示了本文算法运行时间较快, 在考虑视频前景提取过程所耗时间的情况下, 本文算法平均每秒可以处理约7 $\sim$ 8帧图像, 在采用多线程或者进行适当的代码优化后完全可以满足视频实时处理的需求.此外, 从实验结果的骨架图中也可以看出, 由本文算法所提取的骨架的描述方式为图结构, 并且骨架点较少, 这不仅节省了存储空间, 而且对后续的识别处理工作也是非常有利的.另外, 本文算法非常适合于行人骨架的提取, 所提取的骨架可以很好地应用于步态的研究.

4.   结论

针对目前传统骨架化算法时间复杂度较大的问题, 本文提出了一种快速的骨架提取算法.在处理闭合轮廓的过程中, 采用离散曲线演化对骨架进行分段, 有效地去除了微小分支; 依据显著顶点的类型对闭合轮廓进行分割, 并对分割出的每一部分进行骨架提取, 提高了骨架点的精度.为了满足实时性要求, 该方法在保持骨架拓扑结构不变的情况下, 采用截线段中点来代替最大内切圆中心作为骨架点, 并结合骨架点的标记信息迅速得到连通的骨架.实验表明该算法在运动人体上的效果良好, 可以用于行人步态、行人识别等进一步的研究.与传统骨架化算法相比, 该算法运行时间较快, 可以达到实时的要求.由于该骨架提取算法对左右极度不对称的轮廓鲁棒性较差, 我们将在后续的研究中进一步改进该算法, 期望找到轮廓的最优近似对称轴方向, 并沿着该近似对称轴方向进行截线扫描, 从而提高算法的鲁棒性.