关键帧提取和优化算法的流程如图1所示，分为特征提取、K-means聚类、清晰度优化、点密度优化4个关键部分。

图  1  关键帧提取算法流程图

Figure 1.  Flow chart of key frame extraction algorithm

传统的K-means聚类提取视频关键帧的方法是计算各帧图像在像素空间的欧氏距离来衡量图像之间的差异，从而完成图像聚类。这种传统方法运用的是图像像素级特征，然而单个像素不能携带足够的图像语义信息，容易受到噪声的影响，而且会因图像尺寸大而导致计算量大。因此，本文考虑在特征空间中计算欧氏距离来衡量图像之间的差异，即采用自编码器网络^[10]的一种——卷积自编码器（Convolutional Auto-Encoders，CAE）^[11]来实现手语视频每一帧的深度特征提取。自动编码器主要应用于图像重构^[12]、图像压缩^[13]和特征提取等，通过编码器将输入数据压缩到一个潜在表示空间里，然后再通过解码器将潜在空间的数据进行重构，从而得到和输入相似的输出数据。CAE网络结构如图2所示。采用卷积层代替简单自编码器中的全连接层，利用卷积神经网络的卷积和池化操作，对输入的图像进行下采样以提供较小维度潜在表示，实现无监督特征提取。

图  2  用于特征提取的CAE网络结构

Figure 2.  CAE network structure for feature extraction

本文中CAE的训练集是从SLR Dataset中的彩色视频中随机截取的视频帧。考虑到实验操作的便利，将所有的训练数据统一为252 × 252的灰度图像，归一化处理后作为训练集，在无监督训练下训练。网络训练好后，对尺寸大小为1 080 × 720的手语视频的每一帧作同样的数据预处理，输入网络中的编码器后可得到56 × 56的能代表该帧重要特征属性的二维特征向量，作为K-means聚类的输入。

K-means聚类算法是聚类分析中运用最为广泛的算法之一。无论在数据处理或是图像、视频处理中，都运用得相当广泛，其基本思想是将相似对象归到同一簇，将不相似的对象归到不同簇。本文利用该算法对提取出的视频帧的深度特征进行聚类，将每一帧的图像特征展开成一个56 × 56 = 3 136维的向量，通过聚类可以得到K簇3 136维的特征向量。假如视频的特征序列为${{F}} = \left\{ {{{{x}}_{\rm{0}}},{{{x}}_{\rm{1}}}, \cdots ,{{{x}}_n}} \right\}$，${{{x}}_i} \in {{\bf R}^N}$，其中n为视频序列总帧数；i为视频中的第i帧，${{{x}}_i}$为视频中第i帧的特征向量，${{{x}}_n}$是m维向量，其中$m = 3\;1 36$。对于绝大多数手语，一个关键手势的帧数不会超过6帧，那么本文选取聚类数目$K = {\rm len}({{F}})/6$，其中${\rm len}({{F}})$为F中特征向量的个数。具体算法如下：

（1）从F中随机选取K个聚类质心(Cluster centroids)，记为${{{u}}_1},{{{u}}_2},\cdots, {{{u}}_k},{{{u}}_j} \in {{\bf{R}}^n}\left( {0 < j < k} \right)$，其中${u_j}$为第j类的聚类质心。

（2）依次计算各个点到每个聚类质心的欧氏距离。定义样本${{{x}}_i}$到质心${{ u}_j}$的欧氏距离为${{ D}_{ij}} = \left\| {{{{x}}_i} - {{{u}}_j}} \right\|$，记集合${{{D}}_{{i}}} = \left\{ {{D_{i{\rm{1}}}},{D_{i{\rm{2}}}},\cdots,{D_{ik}}} \right\}$，选取${{ D}_i}$中的最小值${{{D}}_{ij}}$，此时将${{{x}}_i}$归入第j类。

（3）再对第j类的所有样本取均值，重新计算该类的质心。

（4）重复步骤（2）、（3），直到上个质心与重新计算的质心的差距最小。

手语“丑”的关键手势在《中国手语》中的定义如图3所示。该手语中手势可能在同一地点不同时间出现，时间上相隔较远的两帧可能会出现在同一类中，例如图4中的第25帧和40帧。一般来说，相似的图像具有连续性，则每一类中会包含连续帧段。考虑到有些手语中会有相同但不相邻的关键手势，如果将其盲目归为一类，则有可能造成手语语义的缺失。将聚得的每类中的非连续帧段分开另为一类，再由时间先后将所有类排序。例如第2类应被分为[18，19，20，21，22，23，24，25]和[38，39，40]两类，此时既可以得到完整的相似帧的分类结果，又没有丢失运动序列的重要信息。

图  3  手语“丑”的关键手势定义

Figure 3.  Key gesture definition of sign language "ugly"

图  4  手语“丑”中处于同一类中非相邻的两帧（24帧和40帧）

Figure 4.  Two non-adjacent frames in the same class of sign language "ugly"

根据K-means聚得的每类中包含的帧为相似的帧，那么应选取其中最清晰的一帧作为最能代表该类的关键帧。文献[14]提出图像的清晰度可以由其边缘来判断，图像的灰度级突变越大，图像边缘特征越明显，图像越清晰，其目标物体与背景边缘越锐利，反之图像越模糊。图像的梯度可以很好地反映图像中目标物体边缘灰度，基于Tenengrad梯度函数的图像清晰度定义如下：

其中：${G_x}\left( {x,y} \right)$和${G_y}\left( {x,y} \right)$分别是图像像素点$\left( {x,y} \right)$处的像素灰度值$f\left( {x,y} \right)$与Sobel水平和垂直方向边缘检测算子的卷积，本文中使用的Sobel梯度算子为

取每一类中$G\left( {x,y} \right)$值最大的一帧便得到首次提取的关键帧序列。对于大多数手语词语，包含同一关键手势的帧数不超过6帧，也就是说，这6帧里一般不会包含两个不同手势的关键帧，因此应在提取出的关键帧上再进行帧间隔优化，即相邻帧如果相距小于一个阈值$a$（本文中取$a = 3$），则去掉这相邻两帧中序列号较小的一帧，这样有效地去除了首次提取关键帧的小部分冗余过渡帧。

本文定义关键手势为《中国手语》中每个词语对应的手势，那么手语视频中能清晰地显示这些手势的视频帧即为关键帧。本文的目的是希望最终提取的众多关键帧中存在包含这个手势的视频帧，并且尽可能减少动作过渡帧和不清晰帧的数量。初次提取的关键帧有大量的重复帧，对比这些重复的关键帧可以发现，一般是由于动作过于缓慢，最终导致本应归为一类的相似的两帧相似度变小。根据大量的统计实验发现，手语者做出关键动作时，手部往往会有下意识的短暂停留，导致K-means方法提取出的关键帧在关键手势附近比较密集。因此本文利用点密度对提取出的关键帧进行二次提取，优化关键帧序列，具体方法如下：

（1）依次记录1.2节中提取出的关键帧数量M，将这些关键帧在视频中的位置序列号记为p，并得到视频关键帧位置序号数组${{p}} = \left\{ {{p_i}|i = 1,2, \cdots ,M} \right\}$；

（2）依次计算p中每个点的点密度。定义第j个点${p_j}$的点密度：

其中，${\rm dis}\left( {{p_j},{p_i}} \right)$表示${p_j}$和${p_i}$之间的欧氏距离。式（3）用于计算在p中有多少个点与${p_j}$之间的距离小于阈值$\delta $，满足条件的${p_i}$越多，表示${p_j}$的点密度越大，反之则表示${p_j}$的点密度越小。定义阈值$\delta $为p上所有相邻点之间的距离之和的平均值，即

以手语“丑”为例，从手语视频“丑”中按照1.2节的方法提取出的关键帧一共有7帧，即$M = 7$，计算得到的点密度散点图如图5（a）所示。理论上，点密度大于阈值的点即为符合要求的关键帧，因此我们还需设定一个阈值T。阈值的选取可以有以下几种方式：（1）点密度的中位数；（2）所有点密度的平均值；（3）点密度最大值与最小值的均值。经过多次实验，本文选取所有点密度的平均值作为阈值T，如图5中$T = 2.14$。超过阈值的点并非全部对应关键帧，并且对于大多数手语词语，包含关键手势的帧数不超过5帧，而有相邻两帧超过阈值的点的水平距离小于5帧的情况不少，此处必定会产生冗余的过渡帧或者重复的关键手势帧，因此对点密度图按照5帧的间隔进行等间隔划分，在每个区间中认定大于阈值T的第一个最大值对应的点为关键帧。如图5（b）所示，被划分的区间应为1.2节中进行K-means聚类的帧的序号区间，即6~68帧，最后获得的关键帧为空心圆圈出的点，一共2帧。

图  5  手语“丑”的点密度图

Figure 5.  Point density maps of sign language "ugly"

从图5中可以看出关键帧的数量减少了很多，但由于动作的连贯性，仍有重复的关键帧出现，但并未漏帧，只要保证未漏掉关键帧就可保证语义的完整性。图5中完整包含了手语词汇“丑”的所有关键帧。

为了识别手语的含义，还需对得到的关键帧进行手势识别，本文采用SSD（Single Shot MultiBox）目标检测网络对手势进行定位和分类。SSD是近年来在目标检测中识别率较高、速度较快的算法，并且在小物体检测上尤为出色，其网络结构如图6所示。它使用VGG16作为基础网络，本文中该网络的输入为300 × 300的图像，分别在基础网络中的6个特征层上预测目标，每个特征层都负责预测特定尺寸的目标，整个网络通过端对端的训练方案在所有预测图上用定位损失和分类损失的加权进行优化。SSD在6个特征层上将整幅图像分割成网格单元，在每个网格单元中围绕中心点构造不同尺寸的边界框用于检测物体，再将不同特征层中所有边界框结合起来，经过NMS（非最大值抑制）方法抑制一部分重叠或者不正确的边界框，最终生成的边界框集合即为检测结果。

图  6  SSD网络结构图

Figure 6.  Network structure of SSD

SSD的训练集由多个手语视频的关键帧组成，在训练SSD时，把每种手势都作为一个输入类别，那么输入的总类别有C（手势类别数）+1（背景）个，这样就可以通过SSD检测出每一帧图像中的每只手的手势类别，再通过手势类别序列与由关键手势组成的标准模板库进行匹配，得到该序列所表示的手语汉字。

实验选用中科院SLR Dataset数据集中10种不同手语词汇的彩色视频，每个手语词汇由50个不同的手语者录制，每个手语时长都不相同，平均时长为3~5 s，拍摄条件相同，所有视频的采样频率都为每秒30帧，实验平台为Python3.6。

为了验证CAE深度特征提取、清晰度优化和点密度优化在本文算法中的作用，实验选取手语“松”的50个视频作为测试集，平均每个视频的帧数为37.42帧，关键帧有2个。在测试集上进行消融实验的结果见表1。其中方法1、2、3分别表示在本文算法的基础上单独去掉CAE特征提取、清晰度优化、点密度优化的方法。

从表1中可以看出，每个部分都能在识别效果上单独起到作用。其中方法1直接使用720×720的图像进行聚类，而本文方法则是先进行CAE特征提取，再利用65×65的特征向量进行聚类，由于聚类的计算复杂度会随着输入样本的尺寸而改变，CAE特征提取也会消耗时间，因此在识别时间上不会呈现数量级的差异。方法2相比于本文算法提取到的关键帧不太清晰，因此准确率受到相对大的影响。方法3省略了点密度二次优化，所提取到的关键帧数量相比本文算法明显增多，并会因冗余帧的误识别影响识别准确率。

对同样的样本进行关键帧提取，并利用SSD网络分别对本文算法、文献[9]算法、文献[15]算法得到的关键帧进行手势识别。本组实验利用数据集中的500个手语视频进行测试，对每个手语单词的结果取平均值，结果见表2。从表2中可以清晰地观测到，与另外两种算法相比，本文算法提取的关键帧数量大大减少，因此在对关键帧手势识别上消耗的时间更少，所以识别时间远优于其他算法；其次，在另外两种算法上提取的关键帧包含多张冗余帧，即包含不清晰关键帧和非关键帧，因此在手势识别过程中会产生错误分类的影响，导致手势识别失败，识别准确率下降。

目前，对于手语视频关键帧的提取效果还没有统一的指标进行判定，本文采用压缩率、误检率和漏检率3个参数来检验视频关键帧的提取效果，定义如下：

压缩率 = 提取关键帧数/总帧数

误检率 = 不包含关键手势的关键帧/总关键帧数

漏检率 = 没检测到的关键手势数/定义的关键手势数

压缩率越大说明该算法消除冗余帧越多，提取的关键帧更具代表性。提取出的视频关键帧将作为后期手势识别模块的输入，并且在提取出的视频关键帧中不包含关键手势的视频帧占比越大，在手势识别时消耗在无效关键帧的时间越多，有时还会因为被识别成错误的手势导致手语识别过程的成功率下降。因此误检率越小，说明关键帧提取效果越好。提取出的关键帧中缺失任意一个重要手势都会导致手语识别失败，所以为了提高手势识别的成功率，漏检率越小越好，表明算法的稳定性也越高。因此在实验时只需要检测以上3个指标即可充分衡量算法的优劣。对数据集中500个视频的3个指标求取平均值，实验结果如表3所示。

从实验结果可以看出，本文算法的压缩率和误检率相比另外两种算法有很大优势，一方面极大地减少了冗余关键帧，包含关键手势的帧占总结果帧数的比例高；另一方面，提取出的正确关键帧的能力更强。漏检率相比其他方法没有增大，因此该算法也保持了良好的稳定性。

图7示出了采用3种算法从一位手语者做手语“松”动作时提取的关键帧。其关键手势有2个，即一手握拳，之后再一手完全张开，图中的“1”表示该帧属于第一帧关键帧，“2”则表示该帧属于第二帧关键帧。可以看出图7（a）中由文献[15]提取出的关键帧最多，相比之下，图7（b）中文献[9]对提取的关键帧二次优化后，关键帧数量减少了2帧，虽然减少了一定的冗余帧，但一般由K-means聚类得出的关键帧较为分散，相邻小于3帧的情况较少，因此文献[9]的优化算法在冗余关键帧去除效果上并不明显。而本文针对一般人在做手语关键动作时的下意识的停顿动作，导致K-means在停顿时间较长处提取出的关键帧的点密集大这一问题，利用点密度筛选出停顿时间较长处即点密度大的视频帧，更有目的性地提取关键帧，因此除去的冗余帧更多。由图7（c）可看出，本文算法提取出的视频帧只有3帧，其中完整地包括了两个关键手势。第二个关键手势有重复帧，但在后期识别时，一旦一个手语单词视频中识别出相同的手势则自动略去，不会影响识别结果，因此本文算法的结果在3种方法中效果最优。

图  7  3种算法提取的手语“松”的关键帧

Figure 7.  Key frames extracted by three algorithms of sign language “loose”

本文提出了一种面向手语识别的视频关键帧提取和优化算法。利用卷积自编码器提取出的图像高级特征进行K-means聚类，根据清晰度算法选择聚得每一类中相似的视频帧中最清晰的一帧，再利用手语动作中关键手势时的停顿，通过点密度筛选出密集度大的视频帧。该算法有效地将K-means算法存在的不足进行了改进，避免了聚类算法中关键帧提取不清晰而造成的关键帧提取效果不理想的问题，使提取的关键帧质量更高，进而提高后期的手势识别准确率。经过实验验证，本文算法在手语识别上具有非常快的识别速度和较高的准确率，尤其在减少冗余帧方面表现更加出色。在今后的学习研究中，对本文算法继续加以改进，以提升运算速度和效率。