（信号与信息处理专业论文）人脸检测跟踪算法的研究与基于davinci的人脸检测系统实现.pdf

上海交通大学硕士学位论文 摘 要 人脸检测与跟踪算法的研究与基于davinci的人脸检测系统 实现 人脸检测与跟踪算法的研究与基于davinci的人脸检测系统 实现 摘摘 要要 随着人工智能和计算机技术的发展，机器视觉研究取得了长足的 进步， 并引起了越来越多的关注， 其研究成果被广泛应用于国防建设、 航空航海、医药卫生、安全监控等国民经济的各个领域。人脸检测与 跟踪则是其中一个重要的应用方向。 人脸检测的目的是检测某监控区 域内是否存在人脸并确定人脸出现的位置、大小等信息；目标跟踪的 目的是对选中的目标进行轨迹的描述，涉及到目标特征的提取、目标 的匹配等多个方面。 本文研究的主要目的是实现对视频序列中人脸的实时监控。系统 由检测和跟踪两部分组成。检测算法主要基于 adaboost 算法，通过 分析 adaboost 算法，训练得到正面人脸的级联检测器。本文的跟踪 算法主要基于 camshift 算法。通过分析影响跟踪不稳定的原因，选 用 hsv 颜色空间的 h 和 s 分量产生目标的二维颜色直方图，并对其 中的直方项进行归并和加权处理， 降低了目标区域中的非目标像素点 对跟踪结果造成的影响， 使目标的二维颜色直方图能更加准确地描述 目标模式，从而在保持 camshift 算法快速性的同时提高其跟踪鲁棒 性。然后，本文将检测和跟踪结合起来，在 pc 平台上实现出能对 qvga 视频实时监控的人脸检测跟踪系统。 第 iii 页 上海交通大学硕士学位论文 摘 要 另外， 本文还研究了 ti davinci 处理器的软件开发， 基于 adaboost 和改进的camshift算法设计了基于davinci处理器的人脸检测与跟踪 系统的模型。通过设计定点算法，将人脸检测程序移植到 davinci 的 c64x+ dsp 处理器上，利用编译器优化选项、intrinsics、线性汇编、 cache 对程序进行优化， 并根据 xdais-dm 算法标准将经优化后的人 脸检测算法封装成可重用的算法包。随后，本文分析了 davinci 处理 器的 codec engine 软件架构及其远程方法调用的机制，最后，在 davinci处理器的arm端通过v4l2和fb驱动程序并利用visa api 调用在 dsp 端运行的人脸检测算法模块完成人脸检测应用程序，从 而在davinci处理器上实现出完整的人脸检测系统， 对qvga和vga 视频分别达到 6.4fps、1.63fps 的检测速率。 关键字：人脸检测，人脸跟踪，adaboost，camshift，davinci 第 iv 页 上海交通大学硕士学位论文 abstract research of face detecting and tracking algorithm and implementation of face detecting system based on davinci processor abstract with the development of artificial intelligence and computer science, machine vision technology has made considerable progress and attracts more and more attention, and it has been widely used in various economic aspects, such as national defense, aviation and navigation, medical treatment and health care, security monitoring, and so on. face detecting and tracking is one of the most important applications. the purpose of face detecting is to detect if there exist faces in the surveillant area. if that, then determine the information of location and size of the faces. object tracking is also an important application branch of computer vision. the goal of tracking is to recognize target objects from the background and extract features, then to depict the moving locus of them. the aim of this paper is to implement real-time surveillance on human faces appeared in video. the system can be divided into two parts of detecting and tracking. detecting algorithm is mainly based on 第 v 页 上海交通大学硕士学位论文 abstract adaboost. by analyzing it, a cascaded detector of frontal face has been trained. tracking method of the paper is mainly based on camshift algorithm. by analyzing its instability during tracking process, h and s components of hsv color space have been chosen to generate a 2d color histogram which describes the object region. besides, the 2d histogram is processed by merging and weighting operation to decrease the interference from non-object pixels in object region greatly. in this way, the object pattern can be more accurately described by 2d color histogram, and camshift algorithm becomes much more robust while keeping its appealing processing speed. after that, detecting and tracking algorithms are combined to implement a real-time face detecting and tracking system to qvga video on pc. in addition, the software development of ti davinci processor is also researched in this paper, and a model of davinci based face detecting and tracking system has been designed by adaboost and improved camshift algorithms. by design of fix-pointed algorithms, face detecting and tracking program has been transplanted to the c64x+ dsp on davinci. optimization options of compiler, intrinsics, linear assembly and cache have been utilized to optimize the program, and the optimized face detecting algorithm has been packaged according to the xdais-dm standard. after that, codec engine framework of davinci processor and its rpc mechanism have been analyzed in the paper. in the end, by v4l2 第 vi 页 上海交通大学硕士学位论文 abstract and fb driver and calling face detecting algorithm module run on dsp end by visa apis, a completed face detecting application has been finished on the arm end of davinci. detecting rate of 6.4fps and 1.63fps has been acquired on qvga and vga video respectively. keywords: face detecting, face tracking, adaboost, camshift, davinci 第 vii 页 上海交通大学硕士学位论文 作者攻读学位期间发表的学术论文 第 78 页 上海交通大学硕士学位论文 作者攻读学位期间发表的学术论文 第 77 页 上海交通大学硕士学位论文 第一章 绪 论 第第 1 章章 绪论绪论 1.1 引言 随着人工智能和计算机技术的发展， 模式识别和机器视觉领域的研究也取得 了长足的进步。人脸检测与跟踪作为机器视觉研究领域的一个热门课题，近年来 已经吸引了越来越多的科研人员的注意， 且其研究成果可被广泛应用于全新人机 交互界面、基于内容的媒体检索、数字视频处理、智能监控等许多领域。 人脸检测与跟踪的基本流程框图如图 1-1 所示。人脸检测（face detection） 是指在输入图像中判断是否存在人脸，并进一步确定人脸的位置、大小、方向等 信息。人脸检测问题最初来源于人脸识别（face recognition） 。人脸识别的研究 可以追溯到 20 世纪 6070 年代，经过几十年的曲折发展已经获得很大的进步。 人脸检测是自动识别人脸的系统中的一个关键环节， 但是早期的人脸识别研究主 要针对具有较强约束条件的人脸图像（如无背景的图像） ，往往假设人脸位置已 知或很容易获得，因此人脸检测问题并未受到重视。近几年随着电子商务等应用 的发展，人脸识别成为最具有潜力的生物身份验证手段，这种应用背景要求自动 识别系统能够对一般环境图像具有一定的适应能力， 由此所面临的一系列问题使 得人脸检测开始作为一个独立的课题受到研究者的重视。今天，人脸检测的应用 背景已经远远超出了人脸识别系统的范畴，在基于内容的检索，数字视频处理， 视觉监听等方面有着重要的应用价值，与完全监控，安检系统，智能人机接口， 犯罪搜捕等许多应用领域密切相关，因此，人脸检测的研究具有极为广泛的应用 价值。 图 1-1 人脸检测与跟踪的基本流程 fig.1-1 basic process of face detection and tracking 由于背景的复杂性、人脸姿态的多样性，人脸检测需要考虑多方面的问题， 既要保证较高的检出率，又要保证较低的误检率，因此尽管国内外的专家学者们 对该课题做了大量的研究，但人脸检测的性能仍然无法达到理想的程度，其主要 第 1 页 上海交通大学硕士学位论文 第一章 绪 论 源于以下几方面的挑战： 1) 人脸的多样性：人脸中包含了很多细节和特征，存在人的发型、肤色、眼睛 大小和睁闭、表情等差异，都可能给人脸检测带来困难。 2) 人脸的遮挡：如饰物、额前的长发对人脸部分器官的遮挡，还有外界环境所 引起的遮挡等等。 3) 人脸的拍摄视角：如拍摄到的是在平面内有一定角度旋转的人脸、上仰或下 俯的人脸，也可能是侧面的人脸。 4) 复杂的背景：如人脸的背景区域中有大量类似人脸的区域或有很多与肤色很 接近的颜色区域，这可能造成误检。 5) 成像条件：主要是光照、阴影、成像设备限制等方面的影响。 如果在人脸检测中能充分考虑到各方面的限制并加以解决， 则可以得到较好 的人脸检测效果。 目标跟踪方法的研究和应用也是机器视觉的一个重要分支， 实现目标跟踪的 关键在于从背景中尽可能精确地分割出目标、提取能够较好地描述目标的特征、 选择精度和速度并优的目标跟踪算法。如今，目标跟踪更多的是应用于对动态目 标的监控， 如对车辆行驶路线的跟踪等， 人脸跟踪也是其中一个重要的应用场合。 与检测过程相似，目标跟踪同样存在着图像背景的复杂变化、目标物体形状 的变化、目标被其它物体遮挡、目标运动轨迹的随机性等问题，这些都给目标跟 踪带来一定的困难。 因此，如果能找到解决检测与跟踪过程中所存在的这些问题的方法，成功地 构造出人脸检测与跟踪系统， 将为解决其它类似的复杂模式检测问题提供重要的 启示。 1.2 人脸检测与跟踪算法的发展现状 常用的人脸检测方法主要可分为：基于人脸几何特征的方法、基于肤色模型 的方法、基于统计理论的方法和基于机器学习的方法。 1) 基于人脸几何特征的方法：所谓人脸的几何特征是指人脸的面部器官 （如：眼睛、鼻子、嘴巴、耳朵等）在几何分布上所体现出来的特征。该类方法 主要包括：基于先验知识的方法、基于特征不变性的方法和基于模板的方法。基 于先验知识的方法是将人脸面部器官之间的关系（如：人脸面部器官的对称性、 灰度的差异等）定义为一系列准则，当图像中的待测区域符合准则，就被检测为 人脸。 yang和huang在 1994 年提出的方法1就是基于先验知识的人脸检测方法的 典型例子。他们的方法是对三级不同分辨率的图像使用不同的准则进行人脸检 测，对低分辨率图像所使用的检测准则主要体现了人脸的大致轮廓，而对高分辨 率的图像所使用的准则主要体现了人脸的细节特征。虽然yang和huang所提出的 第 2 页 上海交通大学硕士学位论文 第一章 绪 论 方法在人脸检测性能方面的表现并不突出， 但这种由粗到细的检测思想对此后的 研究工作有十分重要的指导意义。 基于特征不变性的方法着眼于检测面部的一些 不变特征，例如眼睛、鼻子、嘴巴等，然后综合这些找到的不变特征来确定待检 测区域是否是人脸。人的面部特征一般利用边缘检测器提取，根据提取的特征， 建立统计模型描述特征之间的关系并确定待检测图像中是否存在人脸。 该方法的 一个最大的问题是它对待检测图像中的环境或成像条件的变化相当敏感， 光照不 均、 噪声和面部遮挡都将使图像中与检测算法性能息息相关的人脸特征被严重破 坏，人脸的特征边缘被削弱，造成检测器的性能表现急剧下降。基于模板的方法 则是预先将标准脸部模型通过函数式预定义或参数化， 在进行检测时对给定的一 幅输入图像，分别计算脸部轮廓、眼睛、鼻子以及嘴等与标准模板比较所得的相 关值，人脸存在与否就根据这些相关值来确定。miao等提出了一种层次模板匹 配的方法2。首先将输入图像从-20+20以 5为步长进行旋转以增强检测倾斜 人脸的性能，然后使用laplace算子进行边缘提取，组合提取出的 6 个人脸器官 （两个眉毛、一双眼睛以及鼻子和嘴）的边缘作为人脸模板，最后应用分级式的 方法检测人脸。 2) 基于肤色模型的人脸检测方法：该方法根据人脸的肤色在彩色空间中的 聚集分布特性来将人脸与非人脸模式进行有效分离。在彩色图像中，人脸的肤色 是一个区别于非人脸的很显著的特征，因此，利用人脸的肤色在彩色图像中检测 人脸是一种很自然的想法。研究发现： 1在灰度图像中两个外形相似的物体很可 能在颜色空间下相差甚远； 2不同人种的人脸肤色能在颜色空间中聚集成相异的 紧凑的类3； 3造成不同人种肤色产生差异的主要因素在于颜色的亮度而不是色 度4。根据以上性质，人们在研究中经常使用的颜色空间有rgb（三基色） 、rgb （亮度归一化的三基色） 、hsv/his（色调、饱和度、亮度） 、ycrcb（ccir601 编码方式的色度模型） 、ucs（cie提出的一种均匀色标体系） 。j. c. terrillon等5 对基于两种不同颜色模型以及在九种颜色空间下对人脸检测的性能进行了分析 和比较， 为如何选取合适的颜色空间进行基于肤色的人脸检测提供了重要的参考 依据。jones等6搜集了上万张肤色区域标定的图片（包括上十亿个像素点）来建 立肤色和非肤色两大类的直方图模型， 并且比较了直方图模型和混合高斯模型的 性能，得出前者在检测精度和计算量这两者的性能上都优于后者。 3) 基于统计理论的人脸检测方法主要有主元分析法（pca） 。主元分析法将 样本图像进行kl变换以消除原来各分量之间的相关性，取变换后最大的若干个 特征向量（特征子图）的线性组合来表示原来图像，这若干个特征向量就称为主 元（pc，primary component） 。turk等7将pca方法用于人脸检测与识别，他们 将人脸图像投影到一个由若干最能表示人脸特征的特征向量 （这些特征向量并不 对应于特定的面部器官，如：眼睛、鼻子、嘴等）所张成的子空间中，若要表示 某个特定的人脸，只需要通过对这些特征向量进行线性组合即可，所以这些特征 第 3 页 上海交通大学硕士学位论文 第一章 绪 论 向量也被称为“特征脸（eigenfaces）”，该方法也常被称为特征脸方法。 4) 基于机器学习的方法主要有神经网络法、支持向量机（svm） 、隐马尔 可夫方法（hmm）以及基于boosting（提升）的方法。神经网络方法通过构造 神经网络系统作为分类器，使用人脸和非人脸样本对该系统进行训练，让系统自 动学习两类样本之间复杂的类条件密度， 这样就避免了人为假设类条件密度函数 所带来的问题。 神经网络方法最大的优点是使通过训练一个系统来获得人脸模式 的复杂类条件密度成为可能，而缺点是必须大范围地调整网络结构（如：层的个 数、节点的个数、学习速度等）以获得比较理想的检测性能。rowley等8在 1996 年提出的基于神经网络的人脸检测系统分为两个处理阶段， 第一阶段是通过一个 基于神经网络的分类器对规定尺寸的输入检测区域给出-1+1 的结果，第二阶 段是合并重复检测结果并判决， 此阶段使用一个单层的神经网络对第一阶段中的 重复检测结果进行合并，并使用一个多层的神经网络对检测结果进行判决，该方 法只适用于平面内不带角度旋转的正面人脸的检测。在 1998 年，rowley等9又 提出了改进的方法，使得该系统可以检测图像中经任意角度在平面内旋转的人 脸。支持向量机方法（svm）是由v. n. vapnik在 1995 年提出的一种新的统计学 习理论，使用该方法进行人脸检测的思路是首先将模式投影到较高维的空间中， 然后在投影的人脸和非人脸模式之间形成一个决策面以进行分类判决，svm分 类器是线性分类器， 分类超平面的选取准则是使未知测试样本的分类错误达到最 小。使用svm进行人脸检测会面临两方面困难： 1训练svm是一个求解二次规 划的问题，计算量巨大； 2训练非人脸样本需要大量样本，这样就会导致出现大 量的支持向量。osuna等10使用svm方法进行人脸检测，它利用“自举”的方法搜 集大量的非人脸样本， 然后使用优化逼近的方法选择出少量的支持向量为关键支 持向量，这样可以大大减小运算中支持向量的数目。此后，j. c. platt11提出了顺 序最小最优化（sequential minimal optimization, smo）的支持向量机训练方法， 将一个大型的求解二次规划的问题分成一系列尽可能小的二次规划问题， 这样可 以大大提高训练速度。当前，人脸检测应用最多的是基于boosting的算法。该方 法在目前被认为是解决人脸检测问题最有效的方法， 其有效性不仅体现在能够使 检测系统获得很高的检测准确度，而且还体现在该算法具有很高的检测速度，因 而成为国内外专家学者们的研究热点。adaboost算法最早于 1996 年由y. freund 和r. e. schapire提出12，算法的核心思想是训练一组分类效果略好于随机猜测 （分类准确率略大于 50%）的弱分类器并最终级联成分类精度无限趋于 1（视弱 分类器的级联个数而定）的强分类器。随后，schapire等13又改进了adaboost算 法，提出了使用置信率信息的adaboost算法。viola和jones1415利用级联结构改 进了adaboost算法并将其成功地应用于人脸检测领域， 他们构造出了在检测精度 和检测速度两方面都能获得优秀性能的人脸检测系统， 这才使得人脸检测系统在 真正意义上开始走向实用。adaboost算法是本文所采用的检测算法的基础，其具 第 4 页 上海交通大学硕士学位论文 第一章 绪 论 体的算法思想将在下一章节中进行详细的介绍。 本文中还涉及到了目标跟踪算法的应用。目标跟踪的目的是在图像序列中描 述运动目标的轨迹，实现跟踪的前提是运动目标被正确分割和检测，在本文中用 于跟踪的目标是人脸检测的结果。主要的跟踪算法有三大类，分别是基于跟踪对 象的特征点、统计信息和区域。基于特征点16的目标跟踪是早期研究的主要方 向，要求对物体的形状和运动信息作比较强的先验假设，才能由特征点恢复出对 象区域。 在基于统计的各种跟踪算法中， m. isard和a. blake17提出了比较流行的 condensation算法，作为粒子滤波的一种，它用蒙特卡罗采样的方法，求得使后 验概率最大的跟踪区域。基于区域的目标跟踪方法是目前比较常用的方法，有 meanshift算法1819、camshift20算法、kalman滤波算法和粒子滤波算法等。 meanshift方法在解决目标跟踪方面表现出了良好的鲁棒性和较高的处理速度， 该方法的发展为同时解决目标跟踪的稳定性和实时性提供了一个有力的工具。 meanshift方法具有很高的稳定性，能够适应目标形状、大小的连续变化，而且 计算速度很快，抗干扰能力强，能够保证系统的实时性和稳定性。meanshift方 法的主要缺陷是对初始预测位置的要求较高，如果给定的初始值不够精确，该方 法将无法准确地跟踪目标，甚至丢失目标。将meanshift算法扩展到连续图像序 列，就形成了camshift算法。camshift算法是基于连续图像中初始目标区域颜色 概率分布的一种跟踪算法，具有鲁棒性强和实时性好等优点。它利用目标的颜色 特征在视频图像中找到运动目标的位置和大小， 并在下一帧视频图像中利用运动 目标当前的位置和大小初始化搜索窗口， 重复这个过程就可以实现对目标的连续 跟踪，其缺点是受图像的颜色概率分布影响，主要适用于与背景相比具有明显色 彩差异的彩色目标跟踪。后来，人们利用粒子滤波器（particle filter）和kalman 滤波器的预测功能， 与区域匹配相结合进行目标跟踪。 粒子滤波器的主要思想是： 根据目标物体当前的中心位置和随机高斯分布产生n个粒子作为目标下一时刻 可能出现的位置。然后根据相似度进行排序，取出相似度最大的k个点。然后再 以这k个点作为中心取高斯分布离散点，重新排序后将相似度最大的点作为当前 帧中目标物体的中心位置。在此基础上，kenji okuma21, zia khan22等分别提出 了自启动和结合蒙特卡洛方法的多物体跟踪的粒子滤波器方法。 1.3 本文的主要内容和研究创新 本文对 adaboost 目标检测算法及 camshift 目标跟踪算法进行研究。由于 camshift 算法对跟踪目标的颜色特征敏感， 当背景与跟踪目标具有相近的颜色分 布时 camshift 算法的性能就会明显下降，很容易出现跟踪目标丢失的情况，为 此本文对 camshift 算法做出改进，通过在产生待跟踪目标的颜色特征模板时， 第 5 页 上海交通大学硕士学位论文 第一章 绪 论 选用 hsv 颜色空间的 h 和 s 分量产生跟踪目标的二维颜色直方图，进而在保证 camshift 算法跟踪速度的同时提高了它的跟踪鲁棒性。随后本文基于 adaboost 和 camshift 算法设计了一个便于嵌入式系统实现的人脸检测与跟踪系统，并在 ti 针对视频应用领域所推出的 davinci 处理器上实现了人脸检测系统。 本文的具 体章节安排如下： 第一章， 介绍了研究人脸检测与跟踪算法的意义，概括性地介绍了当前人脸检 测和跟踪技术的发展现状。 第二章， 详细介绍了作为本文所设计的人脸检测与跟踪系统基础的 adaboost、 meanshift 和 camshift 算法，归纳总结这几种算法的优点和存在的不 足。 第三章， 详细介绍了基于adaboost和camshift的人脸检测与跟踪算法的实现， 并对 camshift 算法进行改进， 通过实验数据给出算法改进前后目标跟 踪性能的对比，证明了算法改进的有效性，最后在 pc 上实现了一个 对 qvga 视频达到实时性能的人脸检测与跟踪系统。 第四章， 设计了便于在嵌入式 davinci 平台上实现的人脸检测与跟踪系统，将 人脸检测算法程序移植至 davinci 处理器平台，设计其定点算法，利 用 intrinsics、线性汇编、cache 对人脸检测算法进行大规模优化，根 据 ti 的 xdais-dm 算法标准封装优化后的人脸检测算法，最后在 davinci 平台上利用 codec engine 软件框架实现人脸检测系统。 第五章， 对本文的研究工作进行总结，并在此基础上提出今后需要进一步努力 的方向。 第 6 页 上海交通大学硕士学位论文 第二章 人脸检测跟踪算法原理 第第 2 章章 人脸检测跟踪算法原理人脸检测跟踪算法原理 人脸检测和跟踪技术是模式识别和计算机视觉领域的研究热点， 并具有非常 高的实用价值，它在安全监控、智能人机交互接口、基于内容的视频检索等领域 均有很广泛的应用。在上述这些应用领域中，大多对算法的实时性能要求严格， 而本文研究的重点就是在视频中进行实时人脸检测与跟踪的技术。 在绪论一章中已经给出目前常用的各种人脸检测与跟踪算法的简单介绍， 从 中不难看出基于 adaboost 级联分类器的人脸检测算法无论在检测精度或在检测 速度上均表现出众，因此受到广大研究人员的倾赖。而在目标跟踪算法中，基于 mean shift 的 camshift 算法同样是跟踪性能与速度并优的， 便于在嵌入式系统上 实现，所以本文接下来就将重点讨论上述两种算法的原理。 2.1 基于 adaboost 的人脸检测算法 adaboost（adaptive boosting）算法是一种分类器自动学习算法，它的应用 场合十分广泛，既适用于对两类样本进行分类的场合，也适用于对多类样本进行 分类， 人脸检测问题可以简化为对样本集合中的人脸样本与非人脸样本进行分类 的问题，所以它是一个典型的两类分类问题。基于 adaboost 算法产生人脸检测 器需要解决以下两大核心问题： 1）如何定义用于人脸检测的弱分类器； 2）如何通过弱分类器构建解决实际人脸检测问题的强分类器。 下面将根据以上两条线索介绍基于 adaboost 的人脸检测算法。 2.1.2 类 haar 特征与积分图 本节将解决如何定义和选取adaboost算法中的弱分类器的问题。viola等在 文献14中提出以矩形特征作为弱分类器，并给出 4 类矩形特征，如图 2-1 所示。 矩形特征被定义为黑色矩形和白色矩形在图像子窗口中所对应区域的灰度值总 和之差，它反映了图像中局部区域的灰度变化，可以由以下数学表达式来定义： = = n i iik rcsumwf 1 )(re 式（2.1） 其中，是矩形的权重，是矩形内的所有像素点的灰度值之 和，是构成矩形特征的矩形个数。 rwi i r)(re i rcsum i r n k f 第 7 页 上海交通大学硕士学位论文 第二章 人脸检测跟踪算法原理 ()yxsat, () 11, y x() 12, y x () 21, y x() 22, y x r 图 2-1 viola定义的 4 类基本矩形特征14 fig.2-1 4 types of rectangular features defined by viola14 图 2-2 矩形框像素之和计算示例 fig.2-2 example of computing sum of pixel values in rectangular window 由于这些简单的矩形特征与haar小波基十分类似， 故也将它们形象地称为类 haar特征。viola14在定义了这些矩形特征的同时还给出了一种只需要常数时间 复杂度就能对它们进行特征值计算的算法，该算法需要借助于积分图。积分图由 下式定义： ()() = yyxx yxiyxsat , , , 式（2.2） 其中，是原图像在处的像素值，(, yxi)(, yx()yxsat,是原图像所对应的积分 图在(处的值。对任意一幅给定的灰度图可以由以下递推公式和初始条件逐 行逐列地计算得出其积分图， 使用这种计算方法的优点是只要对灰度图遍历一次 就可以计算出它所对应的积分图。 ) ) yx, ()() ()()()()( += = 1, 1, 11, 01, 1 yxsatyxiyxsatyxsatyxsat xsatysat 式（2.3） 借助上述积分图的定义及其计算方法，就可以通过式（2.4）实现对图像中任意 大小的矩形框的灰度值之和进行计算了，进而利用式（2.1）得出矩形特征的特 征值。 ( )()()()() 12212211 ,reyxsatyxsatyxsatyxsatrcsum+= 式（2.4） 其中，、() 11,y x() 12,y x、() 21,y x() 22,y x是矩形框左上角、右上角、左下角、 右下角这四个顶点的坐标，如图 2-2 所示。 后来， intel公司的rainer lienhart和jochen maydt在viola的基本矩形特征之上 提出了扩展矩形特征23，如图 2-3 所示。在扩展矩形特征中加入了经 45旋转的 矩形特征，针对这部分特征，rainer和maydt引入旋转积分图23以常数时间复杂 度计算它们的特征值，但是必须付出计算旋转积分图所带来的额外开销。因此， 本文综合了viola和rainer所采用的正直矩形特征从而产生出兼顾性能和计算速 度的矩形特征，如图 2-4 所示，对这些矩形特征值的计算只需要计算原始灰度图 像的积分图即可，省去了旋转积分图的计算。 第 8 页 上海交通大学硕士学位论文 第二章 人脸检测跟踪算法原理 图 2-3 扩展的矩形特征 fig.2-3 extended rectangular features 图 2-4 本文所采用的矩形特征 fig.2-4 rectangular features adopted in this paper 2.1.2 boosting 算法概述 boosting是一种分类器融合算法。通常，boosting算法可以用于提高任何给 定的分类器的分类准确度，它的主要思想来源于赛马赌博27。赌马者为了赢得 比赛通常会参考每匹赛马以往的输赢记录，并且会听取一些专家的意见，不同的 专家可能会给出不同的意见，而且专家的经验也不尽相同，赌马者既不能全信这 些意见，也不能偏信某个专家的意见，那么，赌马者怎样挑选好的专家意见来评 估赛马结果呢？怎样把各个专家的意见综合起来呢？boosting算法提供了一种 思路，通过考虑样本的状况，综合一些初步的、不太精确的判断准则，最后形成 一个总体比较精确的判断结果。 1984 年，vapnik 提出了 pac（parallel analysis complexity）机器学习模型， 建立了 boosting 算法的理论框架基础。除此之外，kearns 和 valiant 提出了弱学 习算法与强学习算法的等价性问题，即：在 pac 学习模型，若存在一个多项式 级的学习算法可以识别一组概念，并且识别正确率很高，则这组概念就是强可学 习的；而如果学习算法识别一组概念的正确率仅比随机猜测的结果略好，则这组 概念就是弱可学习。 那么是否可以将一个弱学习算法提升成一个强学习算法呢？ 结论是：如果两者等价的话，则在学习时只要能够找到一个比随机猜测略好的弱 学习算法，就可以将其提升为强学习算法，而不必直接去寻找在一般情况下很难 得到的强学习算法。adaboost 算法的提出很好地解决了上述问题。 第 9 页 上海交通大学硕士学位论文 第二章 人脸检测跟踪算法原理 2.1.3 adaboost 算法原理 adaboost算法最早由freund和schapire于 1996 年提出12， 其核心思想是从一 个分类效果略好于随机猜测（正确分类的概率是 0.5）的弱分类器集合中自适应 地选取有利于解决当前分类问题的弱分类器并对它们进行加权融合以提升为分 类性能较好的强分类器。adaboost算法原理如下： 给定一系列训练样本(x0,y0),(x1,y1),(x2,y2),(xn,yn)，其中xi表示训练样本， yi表示样本的分类标识，yi=0 表示负样本，即不属于目标分类的样本，yi=1 表示 正样本，即属于目标分类的样本，n表示训练样本集的容量。现假定弱分类器用 以下函数式来定义： () ( ) ( ) = pxpf pxpf pfxh , 0 , 1 , 式（2.5） 其中，表示一个用于分类的特征，f表示分类阈值，表示不等号方向。 p step 1：初始化训练样本的权重：( ) n idwi 1 0 =，其中 i=1,2,n。 step 2：对 t=1,2,t， 1）归一化训练样本的权重： = = n i t i t it i w w p 1 ； 2）计算弱分类器对样本的分类结果：； t h( ) = 判为正样本 判为负样本 , 1 , 0 it xh 3）计算分类器的训练误差：( ) = = n i iit t it yxhp 1 ； 式（2.6） 4）更新训练样本的权重：令 t t t = 1 ， () iit yxh t t i t i ww + = 1 1 ； 式（2.7） step 3：最终训练得到的强分类器为： ( ) ( ) = = otherwise xhif xh t t t t ttt , 0 2 1 , 1 1 =1 式（2.8） 其中， t t 1 log=。 第 10 页 上海交通大学硕士学位论文 第二章 人脸检测跟踪算法原理 adaboost 算法的精髓是：在每次迭代过程中，训练器都不断调整样本的权 重，通过降低被正确分类的训练样本权重来间接地增加被分类错误的样本权值， 从而使下一轮训练的重心始终放在那些被分类错误的样本上， 由于上述样本权值 更新过程完全是自适应的，所以该算法称为 adaptive boosting，简称 adaboost。 2.1.4 基于 adaboost 的级联结构人脸检测器 adaboost算法旨在将弱分类器提升为强分类器， 当将其应用在人脸检测器的 训练过程中， 其目的就是从由矩形特征所形成的特征集合中筛选出对人脸模式最 具分辨能力的特征以产生强分类器，即人脸检测器。viola在此基础上提出了级 联结构的人脸检测器14，如图 2-5 所示，该检测器的每一级都是由adaboost算法 所训练出来的一个强分类器，前级的检测器由少量最具代表性的矩形特征构成， 对非人脸样本的排除能力最强， 所以能以最小的运算量淘汰掉待检测样本集中绝 大多数的非人脸样本，而越靠后级的检测器就由越多的矩形特征构成，它们对样 本集进行人脸检测的运算量较大，能排除那些难以被分辨的非人脸样本，但考虑 到能够到达后级的样本数目已远远小于前级，所以并不会造成运算量的大幅增 加，从而保证了这种级联结构人脸检测器的快速性。 图 2-5 级联结构的人脸检测器 fig.2-5 cascaded face detector 2.2 基于 camshift 的人脸跟踪算法 mean shift这个概念最早是由fukunaga和hostetler于 1975 年在一篇关于概率 密度函数梯度估计的文献25中提出的，其最初的含义正如其名，就是偏移的均 值向量，然而在这之后的很长一段时间内mean shift并没有引起人们的注意，直 到 1995 年，y.cheng在文献18中给出了mean shift的一般形式，并对mean shift 第 11 页 上海交通大学硕士学位论文 第二章 人脸检测跟踪算法原理 算法可能的应用领域进行探讨， 这才引起了学术界对mean shift算法的重视。 1998 年intel公司的g.r.bradski在mean shift的基础上提出了camshift算法20以及基于 此算法的人脸跟踪系统，将mean shift算法扩展到对运动目标跟踪的领域里。由 于camshift算法的核心仍旧是mean shift，所以本文将首先介绍mean shift算法。 2.2.1 mean shift 算法原理 mean shift 是一种鲁棒的特征空间分析方法，其原理属于核密度估计。 假设有 d r 空间内 n 个点所组成的集合 nii x k1= ，则点 x 的多变量核密度估计 函数可表示为： ( ) = = n i i d h xx k nh xf 1 1 式（2.9） 式中，k(x)是核函数，h 为窗口半径（带宽） 。在众多核函数中，能产生最小平均 积分平方误差（mise）的是 epanechnikov 核： ( ) + = otherwise xxdc xk d e 0 1)1)(2( 2 12 1 式（2.10） 其中，是单位 d 维空间的体积。另一个常用的核函数是多变量正态核： d c ) 2 1 exp()2()( 2 2 xxk d n = 式（2.11） 因为核函数都只与变量模的平方相关，所以可以定义影子（profile）核函数 k(x) 为： )()( 2 xkxk= 式（2.12） 这样可以将式（2.9）重写成： = = n i i d h xx k nh xf 1 2 1 )( 式（2.13） 如果 k(x)在上除有限个点外均可导，则定义： ), 0 )( )(xkxg= 式（2.14） 再由 g(x)可以导出新的核函数： )()( 2 xcgxg= 式（2.15） 其中，c 是归一化因子。由上面这些定义可以导出多变量核密度估计的梯度为： 第 12 页 上海交通大学硕士学位论文 第二章 人脸检测跟踪算法原理 = = = = + x h xx g h xx gx h xx g nh xfxf n i i n i i i n i i d kk 1 2 1 2 1 2 2 2 )( )( 式（2.16） 因为这里只关心梯度为零的点，而 = n i i h xx g 1 2 可以认为是非零的，所以只需 要考虑式（2.16）中最后一个方括号内的项，并将其定义为 mean shift 向量： x h