模式识别在人脸识别中的应用

模式识别在人脸识别中的应用

目前在人脸定位领域，几何模型匹配方法得到了广泛的使用。

本文对几何模型匹配方法进行了研究，提出了一套完整的人脸定位算法。在预处理部分，采用了特别的增强人脸特征与脸部皮肤之间对比度的方法及局域取阈值二值化方法，改进了预处理的效果。在图像分割部分，实现了经典的分合算法，并且使用成组算法改进了分合的效果。在人脸匹配部分，实现了基于眼睛和嘴的几何模型匹配，并对评价函数的构造进行了研究。

此篇论文所涉及到的是人脸的定位和识别。简单来说，所谓人脸的定位，就是在照片(静态图像) 或视频(动态图像) 中标出人脸所在的位置，把人脸选取出来。而人脸的识别就是把选取出来的人脸与数据库中已有的人脸进行比较，找出匹配的档案来。有的文献把人脸的定位和识别统称为人脸识别，定位和识别则是两个主要的步骤。完整的人脸识别系统涉及到决定照片或视频中有无人脸，并计数，定位，定出大小，然后根据数据库识别出个人，可能的话还要识别表情，以及根据脸的图像做出描述（瓜子脸，丹凤眼等等就是日常生活中“描述”的例子），或者反过来根据描述挑选匹配的人脸图像。

从模型匹配的方法来看，目前的人脸定位算法可以粗略地分为两大类：第一类是利用人脸各器官之间的几何关系的方法；第二类是利用标准人脸图像或者其变换结果直接或者经特征提取后进行匹配的方法。第一类方法利用了明显的先验知识，因而方法简单明了，执行速度较快，对人脸的方向和表情有一定的适应性（在一定的变化范围内面部特征的相对几何关系变化很小）, 但是准确率往往不高（漏判和误判），而且对预处理要求高，依赖于所有面部特征都完整地被提取，所以对转角较大的侧脸, 光照极度不均匀, 部分脸被遮蔽（眼镜, 围巾等）适应性不好。第二类方法利用了更多的图像信息, 准确率高，不易受欺骗；缺点是计算量大，而且使用的人脸模板受人脸库中已有资料的影响，可能会有通用性不好的问题（比如不同人种的人脸模板不能通用）。

利用人脸各器官之间的几何关系的方法可以作为完整的人脸定位算法的一个基础， 就是说利用几何匹配先大致找到图像中的人脸（可能含有很多错误），然后使用利用标准人脸图像或者其变换结果直接或者经特征提取后进行匹配的

方法来确证，剔除实际不是人脸的区域。这样既可以利用第一类方法的速度优势，又可以利用第二类方法的准确度优势。

从一幅图中，按一定规则划分出感兴趣的部分或区域叫做分割。对于利用人脸各器官之间的几何关系的人脸定位方法来说，分割算法是十分重要而关键的。在这里，感兴趣的部分是人脸的器官（眼睛，嘴巴，眉毛，鼻子等等）。分割算法如果能够有效地把人脸器官和脸的其他部分分离开来，并且保持器官的完整性（比如嘴巴没有破碎成几段），就是成功地达到了目的。

最常见的几类方法是：按像素或处理过的像素的灰度值进行分割（其实就是取阈值做二值化）；提取边缘，利用边缘进行分割；区域生长方法。

区域生长方法寻找互相连接在一起，并有相同特征的像素所形成的区域（我把这样的区域称作特征块或者“物体”），是实现图像分割的一种重要方法。区域是一个二维连通区，所以生成区域的办法大致有三类：局部法：这是根据像素的性质或像素的临近像素的性质决定像素分在什么区域；总体法：这是根据遍及整幅图中大量像素的性质决定把一群像素划分到一个区域中；分裂合并法（简称分合）：这是利用状态空间技术分裂或合并区域，用图结构表示区域和边界，这时要利用局部和总体的合并与分裂准则。

图像分割的目的是把人脸的器官与脸的其他部分分离开来，并保存每个器官的完整性。在照片中，人脸比较明显而易辨别的特征主要是面部器官：眼睛，嘴巴，鼻子和眉毛。鼻子往往与脸的反差不大，因此通常用鼻孔代替。这几个面部特征在灰度图像中一般比周围区域暗。尤其是眼睛和嘴巴在绝大部分情况下都清晰可见。因此图像分割可以利用的特征就是：灰度比周围区域暗的区域。在我的毕业设计中，为了减少图像分割这一步的运算量，预处理的时候就对图像做了二值化。因此事实上分割的对象已经是黑白图像，分割简化为找出所有黑色的连通区域，它们都成为人脸器官的候选者。

对分割算法有两个要求：

1、一定的抗噪声能力。经过二值化的黑白图像中，难免会有很多与主旨无关的细碎黑色像素连接了本应分开的特征，而某些单一的特征也可能会破碎成几块。要求分割算法具有一定的能力抵抗这些噪声，将应该分开的特征分开，应该成为整体的部分连起来。

2、运行速度要快。人脸定位和识别系统常常作为实时应用，在这些场合要求系统的运行不能耗时过长，否则就失去意义了。从几何匹配方法来看，最耗时的步骤就是图像分割这一步。所以这一步的速度决定了整个人脸定位方法的运行速度。

分合算法的目的是把图像分割为许多这样的区域：具有某种共同特征并且相互连通的像素分在同一个区域，而特征不同或者不相互连通的像素分在不同的区域。

判定区域R 内的像素是不是具有共同的特征需要均匀性判据H(R)，H(R)为True 表示区域均匀，否则表示不均匀。一般应用的均匀性判据往往是区域内的灰度比较均匀，比如区域内最大和最小的灰度值之差不超过一定阈值（5）。在我的应用中，因为图像已事先做了二值化，所以均匀性的判定有所不同。我只关心黑色的区域，因为只有黑色区域可能代表人脸特征。当一个区域中黑色像素占了绝大部分时，我就认为它是均匀的。

分合算法采用金字塔数据结构。首先讨论以像素计的边长是2的整数次幂的正方形图像。塔的底层（第0层）是原始图像（在我的应用中是已经过二值化的图像）。用相邻排作正方形的四个像素作为子结点，计算上一层相应像素的取值。这样每上溯一层（层编号加1），像素数目成为原来的1/4。当整幅图只剩下一个像素时，金字塔构造完毕（见图1）。数据结构某一层中的一个像素事实上代表了第0层中2j 个像素组成的一个数据方块（j 是该层编号）。

图1 金字塔数据结构

为了表示和计算方便起见，用编码来代表这样的一个数据块。设数据结构中最高一层的编号为n ，则这个编码共有n 位。把一个方块内的四个子方块按照图2顺时针标记为1，2，3，4

。为了表示一个数据块，我们首先把原始图像划分成

四个正方形，第一位编码就描述该数据块落在了1，2，3，4中哪个正方形里。然后对包含该数据块的正方形再划分为四个小正方形，第二位编码就描述该数据块落在了哪个小正方形里。如此反复，直到某个小正方形恰好是该数据块，此后的编码就全部取0，表示不必再细分。例如图2所示的3层金字塔结构：

图2 数据块编码规则

对于一幅普通的图像，一般都不会恰好是正方形，边长也不会恰好是2的整数次幂。我便以128×128的方块作为基本单位，用m ×n 个这样的方块对图像做覆盖。遇到图像中某个部分填不满一个方块的情形，就补上白色（白色不作为特征，看成空白）。每个方块都产生自己的一个7层金字塔数据结构，相互独立地运行分裂算法和合并算法。在相邻归并算法中，不处于同一个128×128划分块但是相邻的数据块应该被归入同一个特征块，所以数据块编码需要在全图像内唯

一。我使用的数据块编码是在每个金字塔7位编码的基础上再加两位，分别表示在m ×n 个128×128划分块中该数据块所处的划分块的x 和y 位置。因此完整的编码是9位。

根据子结点像素计算父结点像素时常用的是灰度平均法。我的应用中有所不同：如果四个像素中白色占了3块以上则父结点像素赋值为白色；如果黑白2：2对角分布也赋值为白色；如果黑色占了三块以上则赋值为黑色；如果黑白2：2各占据一侧则赋值为黑色。这样的好处是可以消除一部分不紧密的连接（2：2对角分布），而保留所有可能的紧密的连接（2：2同侧分布）。

图3 2:2对角和2:2同侧分布

分合算法的思路是（5）：

任取一层数据结构，检验其均匀性H ，若对于该结构中某一区域R 有

H(R)=false，则分裂这个区域为4个子区；若4个彼此相邻属于同一个父结点的区域R k1，…，R k4满足H(Rk1∪R k2∪R k3∪R k4)=true，则合并它们成为单一区域。当

不再有区域可分裂或合并时，停止分割。

如果二任意相邻区域R i 和R （可以不属于同一个父结点；可以有不同的大小）j

使得H(Ri ∪R j )=true，则合并它们。

分割算法的描述如下：

1. 把金字塔数据结构中起始某个中间层的数据块编码全部压入工作堆栈RgStack 。

2. 从RgStack 弹出一个数据块编码Code 。如果Code 代表的数据块不均匀，就把Code 分裂为四个数据块，再把颜色为黑色的那些块的编码压入堆栈RgStack 。如果均匀，或者Code 代表的已经是不可分的像素，那么把Code 压入中间结果堆栈RgCode 。

3. 反复执行2，直至堆栈RgStack 空。

合并算法的描述如下：

1. 把中间层里所有均匀的数据块的编码存入工作队列RgA 。

2. 从RgA 出队一个编码Code 。在RgA 中寻找和Code 属于同一个父结点的其他数据块。如果找不齐所有四个，那么把Code 和找到的都从RgA 删除，

而压入中间

接果数组RgCode 。如果找齐了，那么把这四个编码都从RgA 删除，而把父结点的数据块编码入队到RgA 中。

3. 反复执行2，直至队RgA 空

相邻归并算法的描述如下：

1. 从RgCode 中弹出一个编码，压入工作堆栈RgStack 。

2. 从RgStack 中弹出一个编码Code ，将它入队到RgA 。扫描RgCode ，把所有与Code 相邻的数据块的编码都压入堆栈RgStack 。

3. 反复执行2，直至栈RgStack 空。此时RgA 里面存有的一系列数据块编码就是属于同一个特征块的，可以用来计算这个特征块的形状属性并保存起来。具体计算方法见2.4“形状属性的计算”。

4. 反复执行1-2-3，直至栈RgCode 空

引入成组算法出于如下事实：一些本属于同一个脸部器官的特征块在分合之后仍然是分开的。分开的特征块的中心、大小、取向等等参数相对于一个代表完整的器官的特征块而言都是错误的，导致后面的几何匹配得不到正确结果。成组算法就是用来把挨得足够近的可能本属于同一个器官的特征块合并起来（尽管它们并不是连通的）。算法有两个特点：1. 合并半径取决于待合并的特征块的大小（一个重要参数－最大合并半径N max 事先指定），特征块越大，则合并半径越

小；2. 如果待合并的两个数据块中任一个大于N max ，那么它们必须位于同一主轴

上（主轴的定义在形状属性的计算中介绍）才能合并。下面的伪代码描述了成组算法，其中N(i)代表第i 个块B i 包含的像素个数，N b 代表图像中特征块的总数。

Procedure Grouping

for N := 1 to Nmax do

R := 8 – 6 * (N-1) / (Nmax -1)

for i :=1 to Nb do

if N(i) = N then

“找到所有位于B i 的r 邻域内的特征块{Bj }”

if {Bj } ≠φ then

“从{Bj }中找出离B i 最近的块B k ”

if (N(k)

“把B i 和B k 合并”

end for

end for

end Grouping

预处理常常有以下几个目的：把图像变成便于后续处理的形式；提高对比度，抑制背景而突出面部特征；去除噪声和其他有害的信息。在我的应用中，把图像变成分合算法能够处理的二值化图像是预处理最重要的功能。其次，希望预处理能够提高二值化前的对比度，把面部器官清晰地突出出来，这样加上合适的二值化方法，就能够保证二值化后的图像中，面部器官以黑色特征块的形式被尽量完整而独立地保留下来。

增强图像对比度有很多种方法，常见的有“S ”形变换，直方图均衡化方法等等（参见Kenneth R. Castleman, Digital Image Processing（4）），都是十分经典而使用很广的，这里就不赘述其具体实现了。简单地说，“S ”形变换办法将灰度处于某一范围内（比如灰度很大和很小，或者灰度取值处于中间）的像素的灰度分布差距拉大，从而使对比度提高，这是以牺牲其他灰度范围的对比度为代价的。直方图均衡化则把像素的灰度分布尽量展开在所有可能的灰度取值上，同样能够使对比度提高。

尝试把这些方法应用到人脸定位的预处理中时，效果却不好。原因是这些方法增强对比度没有针对性，结果往往不仅不能突出脸部器官的特征，有时还会造成特征的损失。尤其是直方图均衡化，其结果往往是不能忍受的。

在这样的情况下，我根据实际的需要找到了一种能够突出脸部特征，有针对地增强对比度的方法。

众所周知，边缘提取是特征提取中的一种重要方法。利用边缘提取，可以把图像中灰度发生跳跃变化的地方全部显现出来。脸部器官（尤其是眼睛和嘴）表现为在整个脸的较均匀灰度的背景上的暗团块。所以利用边缘提取可以得到脸部器官的轮廓和内部发生灰度突变的所有边缘。

但是实践证明直接采用边缘提取来提取脸部器官的特征，其效果并不好。边缘提取可类比于微分运算，对于噪声十分敏感，容易造成本不相连的区域粘连起来。

我的人脸定位演示软件采用Delphi 3.0书写，应用了面向对象的编程方法，有简单明了的界面。下面详细介绍其组成和操作。

人脸定位演示软件由以下一些模块组成，可以分为三个层次:

应用层：

Main.pas 软件主模块，负责接受用户输入，调用其他模块完成人脸定位的任务，并将结果显示给用户

算法层：

z_FLoCat.pas 人脸定位主处理模块，包括人脸定位主类（图像的装载和初始化，预处理，常用数字图像处理方法），基本类型定义，基本常数定义和一些函数

z_FLoRG.pas 区域生长算法模块，包括区域生长类（分合算法），金字塔数据结构

z_FLoMatch.pas

基础层：

z_Point.pas 基本数字图像处理模块，包括常用的数字图像处理函数（没有做成类）

z_DataStructure.pas 基本数据结构模块，包括链表，堆栈和队列类 z_DIB.pas Windows位图处理模块，为了能够把位图装载成为可以获取的内存数据（Delphi 不提供这样的低级功能，使用Windows API写成）

下面一一介绍算法层的三个模块：

1．z_FLoCat.pas

在这个模块中，定义了人脸定位主类TFLoc ，它的成员主要包括涉及位图操作的变量（比如图像数据临时内存FLoT ），位图读取（如GetDIBFromFile ）、初始化（InitFLoDIB ）、显示（如PaintImg ）、转化（如BmpFromFLoDat ）的方法，数字图像处理常用的方法（如提取边缘的Sobel ，直方图均衡化

FlattenBMPbyDat 等等），人脸定位算法中的预处理部分PreProcessing （调用人脸匹配模块，包括几何匹配类

了本模块的Sobel ，Add 和z_Point中的LocalThresholding 等过程来实现预处理）。模块还定义了重要的全局变量，如存放图像数据的FLoDat ，临时存放图像数据用于显示结果的FLoT2，图像高度FLoH ，图像宽度FLoW ，为了配合计算机的32位对齐方式而设的折合图像宽度bbWidth ，图像像素总数nFaceFLoDim ，存放“物体”的链表FloObjects 。模块也定义了一些非常重要的数据类型，比如存放图像的内存数组类型FLoD ，存放一维整型直方图的数组类型Hist 和浮点型直方图的数组类型sgHist ，金字塔数据结构要用到的各层数组类型PyR0~PyR7，金字塔数据结构类型Pyramid ，“物体”类型FloObject ，人脸类型Face 。模块还定义了一些常量，比如EPS 表明两个浮点数相差不超过多大时可以认为相等，ORIGINAL_SOBEL_RATIO表示的是在预处理中，原灰度图像和sobel 提取边缘后的灰度图像相加时各自所占比重的比值。最后，模块还包含了一些常常要用到的不属于数字图像处理范畴的过程和函数，比如在FLoT2中画线的Line ，画物体的DrawObject ，计算坐标旋转的Rotate ，求最大和最小值的Max 和Min 等。

2．z_FLoRG.pas

在这个模块中，定义了区域生长类TFLoRG. ，其成员主要包括金字塔数据结构PyR ，工作堆栈和队列RgStack ，RgCode ，RgA 等变量，还有金字塔数据结构初始化InitPyramid ，寻找“物体”FindObjects （通过调用分合算法Split ，Merge 和MergeNeighbor 实现），成组Grouping ，显示“物体”DisplayObjects 等方法，及一些支持分合算法的过程和函数。模块中还包括常量START_LEVEL（分合算法的起始层号）和NMAX （Grouping 算法中除了共线的特殊情形最大可合并块的大小）。

3．z_FLoMatch.pas

在这个模块中，定义了几何匹配类TFloGeometricMatch ，其成员主要有存放找到的人脸结果的堆栈Candidates ，人脸个数FaceCount ，保存拼合后的嘴的链表MergedMouths ，执行几何匹配算法的FindFaces 等。这个模块定义的常量有EEYE_THRESH，EMOUTH_THRESH和EVAL_THRESH，是几何匹配算法中用到的各个评价函数阈值。

使用时首先点击窗口右面偏下的“Load ”按钮，用“打开文件”对话框选择自己要处理的图像文件（必须是Windows 256级灰度位图，大小不能超过512×

384像素）。图像装载进来以后，点击“Preprocess ”进行预处理，结果是一幅二值图像。点击“Find Objects ”，程序使用分合算法寻找“物体”，并把结果显示在窗口中。这一个过程往往需要比较长的时间。点击“Find Faces ”，程序使用几何匹配算法搜寻人脸，并且把结果显示出来。“Shift Image”按钮用来切换原始灰度图像，预处理后二值图像，金字塔数据结构示意图，寻找“物体”的结果显示，寻找人脸的结果显示。除了“Shift Image”按钮随时都可以点击之外，其他四个按钮应依次点击，一步步执行。如果顺序颠倒了，程序会给出提示，并不执行命令。

窗口右面中间的“PyX ”，“PyY ”编辑框是在显示金字塔数据结构示意图时用来指定显示哪个128×128方块的。

窗口右面偏上的四个编辑框“Input1”，“Input2”， “Output1”，“Output2”和按钮“Debug RG ”都是用来调试分合算法的。只要在程序源代码中相应的部分做一点修改，就可以单独测试分合算法中的各个底层过程和函数。

几何匹配算法（利用人脸各器官之间的几何关系的方法）是人脸定位中常见的一种算法，仍然被频繁地以各种形式采用，比如Shi-Hong Jeng和Hong Yuan Mark Liao等（1），Jun Miao和Baocai Yin等（9），卢春雨和张长水等（11）。通过这次论文工作，我对几何匹配的优缺点有了直观的了解。它利用了人们对于人脸各器官间几何关系的先验知识，所以算法清晰简单，每一步骤，每一评价函数项都有直观的解释。它的执行速度在我的程序中主要受到了分割算法的瓶颈限制，如果换用一种更快的分割算法，那么速度将会是很快的。但是它的准确率不高，常会出现漏判。这是因为它依赖于所有面部特征都完整地被提取，所以对预处理要求高，而且对转角较大的侧脸、光照极度不均匀、部分脸被遮蔽（眼镜, 围巾等）适应性不好，因此我认为它不适合单独应用。但是如果有可能与利用标准人脸图像或者其变换结果直接或者经特征提取后进行匹配的方法结合起来使用，则它的快速的优点可以得到利用，而它的准确率不高的缺点可以避免。

在使用几何匹配算法之前必须对图像进行分割，而且分割的结果严重影响匹配的效果，所以分割算法是使用几何匹配方法的人脸定位系统中的重点。我目前采用的分合算法是一种经典而有效的算法，在很多图像处理/计算机视觉/模式识别的书中都有介绍。其优点是具有一定的抗噪声能力，符合人眼视觉多尺度的特

征。缺点是要求存储量大，运行速度慢。要求存储量大在拥有数十M 内存的个人计算机上不是问题。但是运行速度慢却是一个瓶颈，限制了它的应用。