图像分割完成后，结果保存在“物体”数组中，每一个“物体”就是图像中一个连通的黑色区域。“物体”的属性也已经计算出来，包括其位置，大小，取向，外接矩形。几何匹配算法所做的就是在“物体”中寻找可能是人脸器官的组合，所利用的判据则是人脸器官之间所固有的几何关系。使用这些判据按照一定的权重组合，可以对每一组可能被当作面部特征组合的“物体”计算一个评价函数。如果这个函数值超过了一定的阈值，就认为它是一张人脸。
几何关系的模型参考的是Shi-Hong Jeng，Hong Yuan Mark Liao等人（1）的工作，但是在评价函数的构造上有一些改动。详细的规则在下面解释每个评价函数时介绍。举个例子来说明几何模型的意义。如图9，以两眼中心连线为基线，两眼中心距离为D，则鼻孔，眉毛和嘴巴到基线的垂直距离分别约为0.6D，0.3D和1.0D。越符合这个标准的“物体”组合，其评价函数值越大。
图9 Shi-Hong Jeng，Hong Yuan Mark Liao等人的人脸几何模型
|
实际的照片中，眉毛常和头发粘连在一起无法分割出来，而鼻子往往因为与脸部皮肤的对比太不强烈而根本不出现在二值化图像中。经过实践，发现使用仅仅包括眼睛和嘴巴的几何模型就足以解决问题，所以我的算法只考虑了眼睛和嘴巴。
具体的算法是这样的：
1．首先任意挑选一对“物体”（设为eye1和eye2），计算它们作为一对眼睛的评价函数：
强制性条件：eye1必须在eye2的左边（防止同一对“物体”被考虑两遍）；eye1和eye2的连线倾角必须在
之间（人脸的角度不能太倾斜）。
评价函数表达式：
其中l1和l2分别是eye1和eye2的归一化长度（长度除以eye1和eye2的中心距离D），O1是eye1的主轴倾角，O2是eye2的主轴倾角，O是eye1和eye2连线的倾角。
易知表达式中各项越接近0，则评价函数值越大，越接近1。
评价函数中各项代表的含义：
(l1-l2)2：两眼的长度应该相等。
(l1+l2-1)2：两眼长度之和应该大致等于两眼的中心距。
(O1-O)2，(O2-O)2：两眼的倾角应该都等于两眼中心连线的倾角。
如果Eeye超过一定的阈值（0.85），那么认为这一对“物体”很可能是一对眼睛，进入下一步2。否则舍弃这对“物体”，另取一对重新做1。
2．在其余的“物体”中任取一个，计算它作为嘴巴的评价函数：
强制性条件：该“物体”须在眼睛的下面；该物体长宽比不能小于2（否则作为嘴巴来说太宽了）。
评价函数表达式：
其中dm是“物体”中心到两眼中心连线的垂直距离，O是两眼中心连线的倾角（在1中算出），mO是“物体”的倾角，xm是“物体”相对于两眼中心连线中点的横向坐标（计算方法：先把坐标系原点移动到两眼中心连线中点，然后旋转坐标系使得两眼中心连线与x轴重合，此时“物体”的重心的x坐标就是xm），ml是“物体”的长度，el是两眼长度的平均值。
评价函数中各项代表的含义：
(dm-1)2：嘴到两眼中心连线的垂直距离应该大致等于两眼的中心距。
(O-mO)2：嘴的倾角应该等于两眼中心连线的倾角。
xm2：嘴的左右位置应该和两眼中心连线的中点一致。
(ml-1.5el)2：嘴的长度应该大致等于眼睛长度的1.5倍。
如果Emouth超过了一定的阈值（0.7），那么认为“物体”很可能是一张嘴。如果这是第一个找到的嘴的候选者，那么把它存储起来。如果它不是第一个，那么就和存储的嘴的候选者进行比较，保留评价函数值较大的那一个。把所有的物体（除了两个眼睛）都检查过一遍之后，进入下一步3。
由于照片中嘴和脸部皮肤之间的对比差别往往不大，所以经过二值化和分割以后，嘴常常会破碎成两块或更多块。所以我引入了一种方法来拼合这些碎块。当每次遇到一个可能是嘴的“物体”时（记为m），不是简单的和已存储的候选者（记为mouth）作比较二选一，而是尝试把它们合并成一个新的“物体”（记为mmerge），然后在m，mouth，mmerge三个“物体”中选出评价函数最高的那一个作为新的mouth存储起来。这样如果有几个碎块拼在一起更符合嘴的要求的话，算法就会把它们拼起来。考虑到嘴的碎片常常不符合长宽比不小于2的要求，上面提到的强制要求的第二条被取消，代之以要求拼合后嘴的长宽比不小于2。对拼合的嘴还有另一个强制要求，就是两个需要被拼合的碎块相距不能超过两个标准嘴的长度（眼睛平均长度的3倍）。
  图像分割的结果 几何匹配的结果
图10 嘴的拼合效果 |
图10显示了图像分割的结果与几何匹配的结果。可以从图中看到，嘴的拼合的确解决了嘴巴破碎的问题。
3．计算综合的评价函数，表达式为：
如果这个评价函数值超过了一定的阈值（0.8），那么认为这些找到的“物体”合起来的确是一张人脸。
有些情况下，程序可能错把眉毛当作眼睛，与嘴合起来形成一张“人脸”，这样同一张人脸就可能被检测到两次。经过实验，我发现单纯提高评价函数的阈值无法很好地解决这个问题。阈值设得大，虽然可以排除掉眉毛与嘴巴的组合，却会导致漏判其他的人脸。所以我在3中又增加了一层判断：如果发现新找到的人脸与已经找到的人脸占用了共同的“物体”，那么就比较这两个人脸的评价函数值，仅仅保留评价函数值较大的那个作为检测结果。实践证明这种方法能够较好地解决上述问题。
几何匹配结束后，在图像中显示代表眼睛和嘴巴的“物体”，表示找到的人脸的位置。图11是两个例子，其中右面一幅有3张人脸，全部被成功地检测出来了。
|
  图
11 人脸定位结果示例
|
我的人脸定位演示软件采用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写成）
应用层和基础层代码份量虽然不小，但是不涉及主要算法，所以这里就不详细展开了。基本的数字图像处理方法参考了Kenneth R. Castleman, Digital Image Processing（4）和Anil K. Jain, Fundamentals of Digital Image Processing（8）；基本数据结构部分参考了徐士良和朱明方，软件应用技术基础（10）。
下面一一介绍算法层的三个模块：
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，是几何匹配算法中用到的各个评价函数阈值。
这个演示软件的界面和操作十分简单。其界面如图：
 图12 演示软件的界面
|
使用时首先点击窗口右面偏下的“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内存的个人计算机上不是问题。但是运行速度慢却是一个瓶颈，限制了它的应用。
  效果不好，原因：嘴与脸部皮肤对比度差,造成破碎
  失效，原因：眼睛与头发粘连
  失效，原因：人脸太小，光照极不均匀
图13 几何匹配算法/分合算法效果不好或失效的例子 |
图13是一些几何匹配算法/分合算法效果不好或失效的例子：
根据现在已经做出的结果，将来可以从两个方面寻找出路。
首先是改进几何匹配算法，这主要又包括三点，就是改进二值化效果；换用更快的分割算法（比如运行长度当地表方法（1））；增加用于匹配的几何模板（比如侧脸只有一只眼睛出现的模板）。
其次可以考虑引入利用标准人脸图像或者其变换结果直接或者经特征提取后进行匹配的方法。例如采用小波变换，对由几何方法选定的感兴趣区域提取特征，然后和标准人脸的特征进行匹配。
在毕业设计工作中，钟立晨老师给予了我精心的指导。他不仅为我指出了总的工作方向，而且为我提供了大量的参考文献，编制了部分基础层的模块供我学习Delphi下的图像编程。更重要的是他常常和我探讨工作中遇到的问题，教会我开阔思路，灵活地克服困难，使我少走很多弯路。在此我对钟立晨老师表示由衷的感谢。
同组的康大海同学和王志鹏同学常和我讨论工作中的疑难问题，使我对问题的认识更加清晰深刻。在此也一并致谢。
1．Shi-Hong Jeng, Hong Yuan Mark Liao, Chin Chuan Han, Ming Yang Chern and Yao Tsorng Liu, Facial feature detection using geometrical face model：an efficient approach, Pattern Recognition 31 (3), 273-282 (1998).
2．Toshiaki Kondo and Hong Yan, Automatic human face detection and recognition under non-uniform illumination, Pattern Recognition 32, 1707-1718 (1999).
3．S. L. Horowitz and T. Pavlidis, Picture segmentation by a directed split-and-merge procedure, Proc. 2nd IJCPR, 424-433 (1974).
4．Kenneth R. Castleman, Digital Image Processing，Prentice Hall, 1996.
5．荆仁杰, 叶秀清, 徐胜荣, 陈存椿, 计算机图像处理, 浙江大学出版社, 1990.
6．Robert M. Haralick and Linda G. Shapiro, Computer and Robot Vision, Volume 1, Addison-Wesley, 1992.
7．梁路宏, 艾海舟, 何克忠, 基于多模板匹配的单人脸检测, 中国图像图形学报, Vol 4(A), No. 10 (1999).
8．Anil K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, 1989.
9．Jun Miao, Baocai Yin, Kongqiao Wang, Lansun Shen and Xuecun Chen, A hierarchical multiscale and multiangle system for human face detection in a complex background using gravity-center template, Pattern Recognition 32 (7), 1237-1248 (1999).
10．徐士良，朱明方，软件应用技术基础，清华大学出版社，1994.
11．卢春雨，张长水，闻芳，阎平凡，基于区域特征的快速人脸检测法，清华大学学报（自然科学版），Vol. 39, No. 1 (1999).