第3期 余思泉，等：基于空间金字塔特征包的手势识别算法 ·431. 计算其权值。最终得到16×8=128个梯度信息即为 法)聚类。传统的K-means算法由于初始聚类中心 关键点的特征向量。SIFT特征点的SFT描述过程 的不同，迭代次数和聚类结果会有很大差别。为了提 如图2所示。 高算法的稳定性，使用K-means++算法来获得初始聚 类中心。从手势样本库的所有手势图像中提取m个 图密蜜图 特征点，每个特征点的SFT特征描述向量为 图闲快密 x:(i=1,2,,m),则构成的手势样本库的特征向 图图图 量空间为X=[x1x2…xm],确定K-means++ 密粥离 实现步骤如下： ●特征点 4×4×8=128维描述符 a)从特征向量空间X=[x1x2…xm]中， 图2SFT描述子的生成过程 任取一个向量为第1个聚类中心c1。 Fig.2 SIFT descriptor generation process b)根据概率 2.2生成BoF-SIFT描述子 D(x:) p(r:)= D(x) BoF算法是2004年由Csurka引入到图像处理 ∑e…)t）2 领域o。BoF算法叫做作词袋算法，其思想是把一 确定下一个初始聚类中心c:=x,。其中D(x)表示 张图像看作包含若干特征的集合，用这些特征的直 向量x到目前已选出的所有聚类中心中的最近距离。 方图表征图像特征。BoF算法首先要构造视觉词汇 c)重复步骤b),直到选出所有的初始聚类中心 表(vsual vocabulary)。通常采用K-means算法将生 C={c1,c2,,Ck}。 成的SFT描述符进行聚类，选取聚类中心作为视觉 d)确定所有的初始聚类中心后，用K-means算 词汇表，图像的特征点可以利用与其最近邻的视觉 法聚类，得到了最终的K个聚类中心。 词汇表示。通过直方图方式进行量化，得到图像的 4)将得到的K个聚类中心作为视觉词汇表，在 视觉码字就是该图像的BoF-SIFT特征描述子。 步骤1)构造的图像金字塔中的每一层图像的子块中 3空间金字塔特征包手势识别算法 用BoF算法进行特征提取。在图像金字塔中的每一 层子块中生成K个视觉码字的BoF-SFT描述子。 3.1空间金字塔特征包算法提取图像特征 5)将每层的直方图描述子加权组合构造整张 BoF-SIFT算法通过统计整张图像的特征点特 图像的特征描述子。 征生成全局直方图，该方法丢失了图像特征点的分 布信息，因此不能很好地反应图像特征点的分布特 目 性。空间金字塔算法是一种利用空间金字塔进行图 “山L1个K维列向量 像匹配、识别、分类的算法。将空间金字塔思想 … 与BoF算法结合。通过构造空间图像金字塔，对图 的 4个K维列向量 像分层运用BoF-SIFT算法，能在保持BoF-SIFT特 征原有优势的基础上，有效地表征目标图像的局部 16个k维列向量 特征和全局特征，并能更好地表示图像特征点的分 第1层 K个聚类中心，统计K个直方图 生成SFT描述 布特性。SPM-BoF算法框图如图3所示，具体的处 图3空间金字塔特征包算法 理过程如下： Fig.3 The schematic diagram of space pyramid BoF algorithm 1)将原图像分成不同大小的块，构造一个3层 的图像金字塔，第1层将整个图像划分为16个子 3.2直方图相交核支持向量机 块，第2层将整个图像划分为4个子块，第3层为整 支持向量机(SVM)在解决小样本、非线性及高 个图像。 维的模式识别问题中表现出许多特有的优势1。 2)生成图像的SIFT描述子，由于D.G.Lowe提 其解决无法线性分类的样本的关键在于核函数的选 出的检测特征点的方法同时会模糊图像的边缘信 择。直方图相交核支持向量机利用直方图描述的图 息，造成检测到的兴趣点数目较少。本文直接将图 像特征能够很好解决图像分类和识别问题[)。直 像均匀分成若干个像素为16×16的块，以每个小块 方图相交核的定义为 的中心作为特征点生成SFT描述子。 Kim (A,B)= mina,by (3) 3)将所有图像的SIFT描述子用K-means++算 i=1计算其权值。 最终得到 １６×８ ＝ １２８ 个梯度信息即为 关键点的特征向量。 ＳＩＦＴ 特征点的 ＳＩＦＴ 描述过程 如图 ２ 所示。 图 ２ ＳＩＦＴ 描述子的生成过程 Ｆｉｇ． ２ ＳＩＦＴ ｄｅｓｃｒｉｐｔｏｒ ｇｅｎｅｒａｔｉｏｎ ｐｒｏｃｅｓｓ ２．２ 生成 ＢｏＦ⁃ＳＩＦＴ 描述子 ＢｏＦ 算法是 ２００４ 年由 Ｃｓｕｒｋａ 引入到图像处理 领域［１０］ 。 ＢｏＦ 算法叫做作词袋算法，其思想是把一 张图像看作包含若干特征的集合，用这些特征的直 方图表征图像特征。 ＢｏＦ 算法首先要构造视觉词汇 表（ｖｓｕａｌ ｖｏｃａｂｕｌａｒｙ）。 通常采用 Ｋ⁃ｍｅａｎｓ 算法将生 成的 ＳＩＦＴ 描述符进行聚类，选取聚类中心作为视觉 词汇表，图像的特征点可以利用与其最近邻的视觉 词汇表示。 通过直方图方式进行量化，得到图像的 视觉码字就是该图像的 ＢｏＦ⁃ＳＩＦＴ 特征描述子。 ３ 空间金字塔特征包手势识别算法 ３．１ 空间金字塔特征包算法提取图像特征 ＢｏＦ⁃ＳＩＦＴ 算法通过统计整张图像的特征点特 征生成全局直方图，该方法丢失了图像特征点的分 布信息，因此不能很好地反应图像特征点的分布特 性。 空间金字塔算法是一种利用空间金字塔进行图 像匹配、识别、分类的算法［１０］ 。 将空间金字塔思想 与 ＢｏＦ 算法结合。 通过构造空间图像金字塔，对图 像分层运用 ＢｏＦ⁃ＳＩＦＴ 算法，能在保持 ＢｏＦ⁃ＳＩＦＴ 特 征原有优势的基础上，有效地表征目标图像的局部 特征和全局特征，并能更好地表示图像特征点的分 布特性。 ＳＰＭ⁃ＢｏＦ 算法框图如图 ３ 所示，具体的处 理过程如下： １）将原图像分成不同大小的块，构造一个 ３ 层 的图像金字塔，第 １ 层将整个图像划分为 １６ 个子 块，第 ２ 层将整个图像划分为 ４ 个子块，第 ３ 层为整 个图像。 ２）生成图像的 ＳＩＦＴ 描述子，由于 Ｄ． Ｇ． Ｌｏｗｅ 提 出的检测特征点的方法同时会模糊图像的边缘信 息，造成检测到的兴趣点数目较少。 本文直接将图 像均匀分成若干个像素为 １６×１６ 的块，以每个小块 的中心作为特征点生成 ＳＩＦＴ 描述子。 ３）将所有图像的 ＳＩＦＴ 描述子用 Ｋ⁃ｍｅａｎｓ＋＋算 法［１１］聚类。 传统的 Ｋ⁃ｍｅａｎｓ 算法由于初始聚类中心 的不同，迭代次数和聚类结果会有很大差别。 为了提 高算法的稳定性，使用 Ｋ⁃ｍｅａｎｓ＋＋算法来获得初始聚 类中心。 从手势样本库的所有手势图像中提取 ｍ 个 特征 点， 每 个 特 征 点 的 ＳＩＦＴ 特 征 描 述 向 量 为 ｘｉ (ｉ ＝ １，２，．．．，ｍ) ，则构成的手势样本库的特征向 量空间为 Ｘ ＝ ｘ１ ｘ２ [ ．．． ｘｍ ] ，确定 Ｋ⁃ｍｅａｎｓ＋＋ 实现步骤如下： ａ）从特征向量空间 Ｘ ＝ ｘ１ ｘ２ [ ．．． ｘｍ ] 中， 任取一个向量为第 １ 个聚类中心 ｃ１ 。 ｂ）根据概率 ｐ ｘｉ ( ) ＝ Ｄ ｘｉ ( ) ∑ｘ′∈ ｘ１ ，ｘ２ { ，．．．，ｘｍ} Ｄ (ｘ′) ２ ∝ Ｄ(ｘ) 确定下一个初始聚类中心 ｃｊ ＝ ｘｊ 。 其中 Ｄ(ｘ) 表示 向量 ｘ 到目前已选出的所有聚类中心中的最近距离。 ｃ）重复步骤 ｂ），直到选出所有的初始聚类中心 Ｃ ＝ ｃ１ ，ｃ２ ，．．．，ｃｋ { } 。 ｄ）确定所有的初始聚类中心后，用 Ｋ⁃ｍｅａｎｓ 算 法聚类，得到了最终的 Ｋ 个聚类中心。 ４）将得到的 Ｋ 个聚类中心作为视觉词汇表，在 步骤 １）构造的图像金字塔中的每一层图像的子块中 用 ＢｏＦ 算法进行特征提取。 在图像金字塔中的每一 层子块中生成 Ｋ 个视觉码字的 ＢｏＦ⁃ＳＩＦＴ 描述子。 ５）将每层的直方图描述子加权组合构造整张 图像的特征描述子。 图 ３ 空间金字塔特征包算法 Ｆｉｇ． ３ Ｔｈｅ ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ｓｐａｃｅ ｐｙｒａｍｉｄ ＢｏＦ ａｌｇｏｒｉｔｈｍ ３．２ 直方图相交核支持向量机 支持向量机（ＳＶＭ）在解决小样本、非线性及高 维的模式识别问题中表现出许多特有的优势［１２］ 。 其解决无法线性分类的样本的关键在于核函数的选 择。 直方图相交核支持向量机利用直方图描述的图 像特征能够很好解决图像分类和识别问题［１３］ 。 直 方图相交核的定义为 Ｋｉｎｔ (Ａ，Ｂ) ＝ ∑ ｍ ｉ ＝ １ ｍｉｎ ａｉ，ｂｉ { } （３） 第 ３ 期 余思泉，等：基于空间金字塔特征包的手势识别算法 ·４３１·