摘  要: 本文介绍了数学形态学中结构元素为4连通或8连通的3×3邻域时腐蚀、膨胀运算的快速算法。区域采用线段编码表示，腐蚀与膨胀运算在当前线段与其相邻的上下线段之间通过逻辑运算实现。4连通邻域结构元素下作腐蚀(或膨胀)运算时，先将当前线段两侧各除去(扩展)一个像素，再与上下邻接线段作与(或)运算。8连通邻域结构元素下与此相类似，不同在于参与运算的3条线段都需在两侧除去或扩展像素。运算速度一般可提高3~5倍。
关键词: 数学形态学；腐蚀；膨胀；快速算法；

1  引  言
  在计算机图形图像处理中有一些著名的处理算法，它们非常简单、巧妙，易于理解、易于实现，但往往存在运行速度慢的缺点，不经改进难以实际使用。例如，图像分割中的像素标记法[1]和计算机图形学中的边界填充算法[2](也称种子填充算法)。它们的操作对象是像素，具体地说是以当前像素为中心的邻域内的像素。处理速度慢的原因是处理过程需要遍历图像中的每一个像素，即必须检查每个像素的类型(对象还是背景)，并根据不同类型作出相应的处理。同时由于处理是在像素所在邻域中进行的，因此相邻像素的处理存在很多重复的操作。算法改进的思路是将处理对象由像素改为光栅扫描方向上相邻像素构成的水平线段[2][3]。与以像素邻域为处理单位的“点操作”相对应，本文中将以水平线段为处理单位的操作称为线操作。
  这些算法的另一个缺点是处理结果只提供了图像分割所需的半成品，只是将不同区域相区别，并未真正获得实际需要的区域信息，如区域的位置或其它特征参数。例如，在像素标记法中只为不同连通区域的像素用不同的数字作了标记，在边界填充算法中只对所需的区域用指定颜色作了填充等，并没有得到区域的实际参数，若要得到区域信息还需进行后续处理。
文献[4]将区域的描述方法分为两个大类，即轮廓表示法和线段表示法，其中后者可用于上述算法中区域的描述，见图1。线段表示法将区域表示为光栅扫描方向上的一条条水平线段，由它们的端点来记录区域的位置。文献[4]以线段表为基础将像素标记法改进为线段编码法，实现了连通区域的提取，还给出了分离外轮廓与孔和搜索种子点的例子。

  本文介绍以“线操作”来提高数学形态学中腐蚀、膨胀算法运行速度的原理和方法，算法的速度一般可提高十余倍，若与获得区域线段表的线段编码过程一并考虑，速度也可提高3~5倍。

2  线段的特性
2.1   线段的连通性
   处于上下行中的两线段的连通性可通过它们端点的位置来确定，可用下列逻辑关系进行判别：
IF (X1L<=X2R+no) AND (X2L<=X1R+no) THEN  T = TRUE
ELSE  T = FALSE
其中，(X1L ,X1R)、(X2L X2R) 分别表示相邻的上下行中两条线段左、右端点的X坐标。T等于TRUE表示两线段连通；T等于FALSE表示不连通。在两种连通条件下仅常数no取不同的值，4连通时取0，8连通时取1。
2.2   术语解释
    为了后面行文方便起见，根据线段的属性先定义几个后文用到的名词。
·内点：在其邻域内全部是对象点的点。
·边界点：在其邻域内既有对象点又有背景点的点。
·内边界点：本点为对象点的边界点。
·外边界点：本点为背景点的边界点。
·当前线段：处理过程中待处理的线段，主要考察它与上下相邻线段的关系。
·内点段：线段上由内点组成的部分。
·边界段：线段上由边界点组成的部分。
·顶部线段：与上一行没有邻接线段的线段。
·底部线段：与下一行没有邻接线段的线段。
·中间线段：与上、下两行都有邻接线段的线段。
2.3   线段的内点段与边界段
   构成区域的水平线段有顶部、中间和底部3种状态，图2给出了4连通时这些状态下内点段与边界段的区分。图中上方为原始图像，下方将当前线段区分为内点段和边界段，它们分别用黑色和白色表示。由图中可知，顶部线段(a)与底部线段(c)都是边界段，只有中间线段(b)中才可能存在内点段。不管线段的长短都按这种规则进行区分，线段愈长则效率愈高。

3  腐蚀与膨胀
数学形态学是图像处理中一类常用的处理算法，其基本运算有4种，即膨胀、腐蚀、开运算和闭运算。通常都是用集合论名词定义的，并用专门定义的结构元素对图像进行操作。其中应用最为广泛的是由4连通的3×3邻域(5点)或8连通的3×3邻域(9点)组成的结构元素，本文介绍的快速算法仅适用于这两种情况。
3.1   腐蚀
有了上面内、外边界的定义，对于由4连通或8连通的3×3邻域组成的结构元素定义的腐蚀、膨胀运算就不难实现了。腐蚀运算是把区域的内边界变成背景，使区域缩小一圈；膨胀运算则是将区域的外边界变成对象，使区域扩展一圈。关键在于如何确定每条线段的内点段和边界段，以及得到它们的端点坐标。
腐蚀运算实际上是寻找线段的内点段并将它们保存下来。图3给出了当前线段确定线段内点段进行腐蚀的原理，4连通与8连通之间的区别仅在于上下两线段的端点是否需要去除。在图3(b)、(c)中，腐蚀结果是三线段中灰色与黑色填充部分作与运算的结果。

腐蚀运算的操作步骤如下：
⑴ 确定当前线段类型，删除顶部线段和底部线段，只处理中间线段。
⑵ 根据连通特性确定上下两行邻接线段的计算长度，4连通时它们采用原来长度，8连通时除去它们的两侧端点。
⑶ 当前线段除去两侧端点。
⑷ 相邻三线段的剩余部分作与运算得到当前线段的腐蚀结果。
⑸ 对于属于区域的所有水平线段都作⑴~⑷。
3.2   内边界
    由定义知，内边界是原区域与其腐蚀结果之差，所以它的处理步骤如下：
⑴ 确定当前线段类型，保留顶部线段和底部线段，对于中间线段作⑵、⑶。
⑵ 根据连通特性确定上下两行邻接线段的计算长度，与腐蚀的步骤⑵相同。
⑶ 上、下邻接线段作与运算。
⑷ 在当前线段中除去⑶求得的结果。
⑸ 对于属于区域的所有水平线段都作⑴~⑷。
3.3   膨胀
   与腐蚀运算相类似，膨胀运算可看作是将区域的外边界变成对象，使区域扩展一圈。
图4给出了当前线段进行膨胀的原理，图4(a)、(b)中灰色部分为原始图像，白色方框为外扩的端点。当前线段膨胀的结果由3条线段线框包围部分作或运算得到，见图4(c)、(d)。两种连通情况的差异仅在上下两线段的端点是否进行扩展。
顶部和底部线段运算只在两条线段间进行，上下各少一条线段。
膨胀运算的操作步骤如下：
⑴ 根据连通特性确定上下两行连通线段的计算长度，4连通时用原来长度，8连通时两侧各向外扩展一个像素。

⑵ 确定当前线段类型，顶部或底部线段，需在它们的上方或下方各增加一条边界线段，增加线段的长度由当前线段按⑴中的规则确定。
⑶ 当前线段在左右两侧各扩展一个像素，所有线段(包括顶部和底部线段)都需进行这种扩展。
⑷ 经过扩展的3条线段作或运算得到当前线段的膨胀结果，顶部和底部线段则只需相邻的两条线段进行运算。
⑸ 对于属于区域的所有水平线段都作⑴~⑷。
3.4   外边界
由定义知，外边界是区域膨胀结果与原区域之差。因此，寻找外边界的步骤与3.2节类似。

4  注意事项与效果分析
4.1   注意事项
   除了上面小节介绍的原理和处理步骤外，处理过程中还有一些需要加以注意的事项。
⑴ 与通常的卷积运算相似，处理采用并行算法，即在处理过程中原始数据应保持不变。同时，输出数据有时会多于输入数据，例如由于每条线段两侧都有边界段，得到的内边界的线段数几乎是原来的一倍。因此，输出单元最好能与输入单元分开。
⑵ 腐蚀运算中，并非每条线段都只收缩为一条短线段，当当前线段与上下行有多条线段相邻接时，也可能收缩为几个小段，处理时切勿遗漏。寻找内边界时也有类似情况。
⑶ 腐蚀运算和寻找内边界的处理过程中得到结果线段的顺序与光栅扫描顺序是一致的，可以直接存储起来。
⑷ 膨胀运算中遇到顶部线段或底部线段时输出线段的顺序就会与扫描顺序不一致，如果到处理结束后再进行排序会增加时间开销。故存放输出结果可用插入排序方法，及时将数据插入适当位置。
⑸ 膨胀运算中还会发生结果线段相交叠的情况，因此这种数据存储时也应及时进行合并。
4.2  效果分析
  图5是进行运行时间比较的原始图像，尺寸为231×141，图像总点数为32571，其中对象区域点数8004，由255条线段组成。区域经腐蚀、膨胀和寻找内边界后得到的线段数分别为246、230和507。

   表1给出了用线操作方法与传统算法处理例子图像所需的运行时间。表中数据的时间单位为微秒。运行时间采用程序开始和结束时的系统时间之差计算得到的。由于Windows是多任务操作系统，同时可能运行多个任务。程序执行时间与计算机速度、负载状况等因素有关，故测速时存在一定的干扰，故数据取多次测试的平均值。虽然所得数据并不十分精确，但重要的并不是它们的绝对值，而是它们的数量级及其比例关系。

表1  线操作法与传统算法运行速度的比较

   从表中可以看出对于同类操作，两者的运行时间相差一个数量级，约有十余倍之多。如果由于两者的处理条件不尽相同还缺乏说服力的话，再以实现相同任务，即以最终都获得处理结果的线段编码为目标作比较，即线操作法时先进行线段编码，再采用线段表作形态学运算；对照组先用传统算法作形态学运算，再对结果进行线段编码，这时可以得到相同的结果。它们的运行时间见表2。从表中可见，速度也有3~5倍的提高。
   对例图作一次线段编码约需450~600微秒，处理时只需作一次。因此加上它以后，虽然对单个腐蚀、膨胀操作效果的改善大打折扣，而对于开运算、闭运算、圆形结构元素的腐蚀膨胀、极限腐蚀和条件膨胀[5]等需要连续进行多次基本腐蚀膨胀操作的运算而言，速度的提高仍然十分明显。更为重要的是也能同时得到区域的线段表。

表2  包括线段编码时的运行时间

5  应用实例
 5.1  形状保真腐蚀膨胀
   文献[6]介绍了结构元素的分解。对于二维卷积，可以将大的脉冲响应分解成一系列小的成形核，对于腐蚀膨胀运算也存在类似的分解算法。典型的分解有如下几种，见图6，为5×5的结构元素分解成两个3×3的结构元素。

  结构元素的分解意味着用分解前后两种结构元素进行的腐蚀膨胀操作是等效的。如图6(a)，用5×5方型结构元素进行的腐蚀膨胀操作与用8连通3×3方型结构元素连续进行两次所得结果相同。反过来看，由图6(a)可知，用8连通3×3邻域结构元素连续作膨胀操作得到方形图案。同样，用4连通3×3邻域结构元素连续作膨胀操作得到菱形图案。两者都使图形产生很大的失真。而由图6(b)可知，若两种结构元素交替使用可得圆形的图案。图7(a)~(c)分别给出了这3种结构元素连续膨胀、腐蚀得到的结果[5]。图中，都是在半径为50的圆的基础上用5×5邻域的结构元素连续腐蚀或膨胀8次，上方为连续腐蚀，下方为连续膨胀。上半图中，大圆与小圆的半径分别为50与34；下半图中，小圆与大圆的半径分别为50与66，后者都作为形状比较的基准。显然，圆形结构元素的处理结果失真最小，它是通过交替使用8连通与4连通的3×3邻域结构元素(即8-4连通交替)实现的。
  从图7(b)看，效果还不甚理想，还存在较大误差。而从图中(a)与(c)的比较可以看出，两者的误差是互补的，同时前者的误差约是后者的两倍，因此

   结构元素若采用8-4-4连通交替，腐蚀膨胀时形状的失真可以更小，见图7(d)。由于失真小，特将这种处理方式称为形状保真腐蚀膨胀。图8为区域经过36次这种膨胀所得的结果，图中深灰部分是原始区域，外侧则为膨胀36次所得的图形。

  利用线操作可以迅速、简便地实现这种形状保真膨胀，程序的执行速度也有很大的提高，见表3。不计显示时间，处理速度可提高40余倍，与显示时间一并考虑速度也可提高一倍多。

表3  形状保真膨胀执行时间

5.2   根据线段属性确定分割位置
   文献[4]介绍了对粘连图像进行距离变换后作等值(距)线跟踪实现粘连区域的分割，由此得到光滑的区域边界，但处理速度较慢。文献[7]改进了寻找分割位置的方法，即先根据像素属性直接找到粘连区域的瓶颈部位，再由后续处理确定最终分割点实现分割。这种方法极大地提高了处理的速度，图9(a)为其处理结果。图中浅灰色线描出区域的边界，黑点与黑线为寻找到的瓶颈区域的位置。现在采用线操作的形状保真腐蚀，根据线段属性同样可以方便地实现，见图9(b)。

   运行时间见表4。其中的预处理在像素属性法中是距离变换，在线段属性法中是种子填充法搜索区域。可见采用线操作处理速度提高了40倍。

表4   确定分割点位置执行时间

6  结论
   采用线操作的腐蚀膨胀可提高处理的速度，并可同时获得结果区域的描述 (线段表)。处理本身的速度一般可提高10~40倍，若与预处理和结果的显示一并考虑，则仅能提高3~5倍。因此，这种算法适宜于连续施行腐蚀膨胀操作的场合，如区域等宽度内、外边界的确定。后一优点则特别适用于区域生长时迅速确定区域的扩展部分。
参 考 文 献
[1]谷口庆治. 数字图像处理(基础篇)[M]. 北京:科学出版社, 2002. 118~119
[2]Donald Hearn，M Pauline Baker. 计算机图形学(第二版)[M]. 北京: 电子工业出版社, 2002. 91~95
[3]K R Castleman.  数字图像处理[M]. 北京: 电子工业出版社, 1998. 416~418
[4]陆宗骐. C/C++图像处理编程[M]. 北京: 清华大学出版社, 2005. 277~281, 319~360
[5]陆宗骐, 金登男. Visual C++.NET图像处理编程[M]. 北京: 清华大学出版社, 2006. 269~279, 379~389
[6]William K Pratt.  数字图像处理(原书第3版)[M]. 北京: 机械工业出版社, 2005. 290~291
[7]陆宗骐, 傅江桃. 根据像素属性确定粘连区域分割位置. 第十二届全国图象图形学学术会议论文集[M]. 北京: 清华大学出版社, 2005. 185~188