我在毕业设计中采用的是区域生长方法中的分合算法。分合算法70年代就由Horowitz和Pavlidis（3）提出，发展至今已经是一种非常成熟的经典算法，被广泛用于图像分割的应用，比如卫星遥感照片的自动分割等。这种方法被证明效果较好，但是计算和存储量大。
我的论文工作的目标是寻找一种切实可行的人脸定位算法，并且编制出演示的软件。我采用的是分合的分割算法和几何匹配的算法。算法和软件的实现采用的是Borland Delphi 3。Windows位图的基本操作和一些数字图像处理的基本操作来自钟立晨老师所编制的模块，其余的各模块是由我自己编写的，包括：演示软件主程序；图像的预处理；分合算法；几何人脸匹配算法；基本的链表，堆栈和队列的数据结构。
在引言中已经说明了图像分割的基本概念和常见的算法类型。这里更加详细地讨论在人脸定位中图像分割的方法。
TIFY: inter-ideograph; TEXT-INDENT: 25pt; TEXT-ALIGN: justify">图像分割的目的是把人脸的器官与脸的其他部分分离开来，并保存每个器官的完整性。在照片中，人脸比较明显而易辨别的特征主要是面部器官：眼睛，嘴巴，鼻子和眉毛。鼻子往往与脸的反差不大，因此通常用鼻孔代替。这几个面部特征在灰度图像中一般比周围区域暗。尤其是眼睛和嘴巴在绝大部分情况下都清晰可见。因此图像分割可以利用的特征就是：灰度比周围区域暗的区域。在我的毕业设计中，为了减少图像分割这一步的运算量，预处理的时候就对图像做了二值化。因此事实上分割的对象已经是黑白图像，分割简化为找出所有黑色的连通区域，它们都成为人脸器官的候选者。
TIFY: inter-ideograph; TEXT-INDENT: 25pt; TEXT-ALIGN: justify">对分割算法有两个要求：
TIFY: inter-ideograph; MARGIN-LEFT: 18pt; TEXT-INDENT: -18pt; TEXT-ALIGN: justify; mso-list: l0 level1 lfo19; tab-stops: list 18.0pt">1. 一定的抗噪声能力。经过二值化的黑白图像中，难免会有很多与主旨无关的细碎黑色像素连接了本应分开的特征，而某些单一的特征也可能会破碎成几块。要求分割算法具有一定的能力抵抗这些噪声，将应该分开的特征分开，应该成为整体的部分连起来。
TIFY: inter-ideograph; MARGIN-LEFT: 18pt; TEXT-INDENT: -18pt; TEXT-ALIGN: justify; mso-list: l0 level1 lfo19; tab-stops: list 18.0pt">2. 运行速度要快。人脸定位和识别系统常常作为实时应用，在这些场合要求系统的运行不能耗时过长，否则就失去意义了。从几何匹配方法来看，最耗时的步骤就是图像分割这一步。所以这一步的速度决定了整个人脸定位方法的运行速度。
由于我们需要的是能够把黑色连通的区域分别标记出来的分割算法，选择区域生长法就是最自然的了。
在区域生长法中，有两类算法最常见：分合算法和运行长度表方法。分合算法抗噪声能力好一些，所以它成为了我首选的算法。但是经过实践发现它的最大弱点是计算量大，而且计算量随问题规模的增长是非线性的，这就导致对大的或者复杂图像的处理时间很长。运行长度表方法优点是速度快，缺点则是没有多少抗噪声能力。
下面具体描述分合算法和我在它的实现中的一些考虑。具体的模块组织见4.1“软件的组成”。
要事先说明的一点是，现在个人计算机的内存一般都有几十M以上，对于人脸定位的应用绰绰有余，所以运行在个人计算机上的算法完全不必为了节省内存空间而做专门的考虑。但是如果希望算法能够运行在数字图像处理芯片上，就需要做改写以适应节省内存的要求了。
分合算法的目的是把图像分割为许多这样的区域：具有某种共同特征并且相互连通的像素分在同一个区域，而特征不同或者不相互连通的像素分在不同的区域。（我使用的连通性定义是四连通。关于四连通和八连通的概念参见Kenneth R. Castleman（4）TICAL-ALIGN: baseline">）。
判定区域R内的像素是不是具有共同的特征需要均匀性判据H(R)，H(R)为True表示区域均匀（从而可以认为像素具有共同的特征），否则表示不均匀。一般应用的均匀性判据往往是区域内的灰度比较均匀，比如区域内最大和最小的灰度值之差不超过一定阈值（5）。在我的应用中，因为图像已事先做了二值化，所以均匀性的判定有所不同。我只关心黑色的区域，因为只有黑色区域可能代表人脸特征。当一个区域中黑色像素占了绝大部分时，我就认为它是均匀的。具体的判据将在算法中给出。
分合算法采用金字塔数据结构。首先讨论以像素计的边长是2的整数次幂的正方形图像。塔的底层（第0层）是原始图像（在我的应用中是已经过二值化的图像）。用相邻排作正方形的四个像素作为子结点，计算上一层相应像素的取值。这样每上溯一层（层编号加1），像素数目成为原来的1/4。当整幅图只剩下一个像素时，金字塔构造完毕（见图1）。数据结构某一层中的一个像素事实上代表了第0层中2j个像素组成的一个数据方块（j是该层编号）。为
图1 金字塔数据结构 |
图2 数据块编码规则
|
了表示和计算方便起见，用编码来代表这样的一个数据块。设数据结构中最高一层的编号为n，则这个编码共有n位。把一个方块内的四个子方块按照图2顺时针标记为1，2，3，4。为了表示一个数据块，我们首先把原始图像划分成四个正方形，第一位编码就描述该数据块落在了1，2，3，4中哪个正方形里。然后对包含该数据块的正方形再划分为四个小正方形，第二位编码就描述该数据块落在了哪个小正方形里。如此反复，直到某个小正方形恰好是该数据块，此后的编码就全部取0，表示不必再细分。例如图2所示的3层金字塔结构：
对于一幅普通的图像，一般都不会恰好是正方形，边长也不会恰好是2的整数次幂。我便以128×128的方块作为基本单位，用m×n个这样的方块对图像做覆盖。遇到图像中某个部分填不满一个方块的情形，就补上白色（白色不作为特征，看成空白）。每个方块都产生自己的一个7层金字塔数据结构，相互独立地运行分裂算法和合并算法。在相邻归并算法中，不处于同一个128×128划分块但是相邻的数据块应该被归入同一个特征块，所以数据块编码需要在全图像内唯一。我使用的数据块编码是在每个金字塔7位编码的基础上再加两位，分别表示在m×n个128×128划分块中该数据块所处的划分块的x和y位置。因此完整的编码是9位。