软件学报
JOURNAL OF SOFTWARE
1999年　第10卷　第9期　Vol.10　No.9　1999



形态模板分解的逼近算法与应用*
邹荣金　蔡士杰　张福炎
摘要　文章描述了一种获取形态模板分解的逼近算法，实现了二维形态模板的双向正交分解，使算法具有较快的处理速度.形态模板分解对于提高形态图像处理计算的效率是一种非常有用的技术.文章还针对图像中的直线交点、端点形态模板检测进行了试验研究.
关键词　模板分解，卷积运算，最小二乘逼近，计算机图形学，图像识别.
中图法分类号　TP391
An Approximate Algorithm and Its Application of the Morphological Templates Decomposition
ZOU Rong-jin,CAI Shi-jie,ZHANG Fu-yan
(State Key Laboratory for Novel Software Technology Nanjing University　Nanjing　210093)
(Department of Computer Science Jiangsu University of Science and Technology　Zhenjiang　212000)
Abstract　In this paper, an approximate algorithm of obtaining morphological templates is described, and the bi-directional orthogonal decomposition of the two dimensional morphological templates is realized. The decomposition of morphological templates is a useful technique for enhancing the computational efficiency of morphological image processing operations. The recognition algorithm of the intersection points and the end points of the lines in engineering drawings based on the morphological templates is also proposed in this paper.
Key words　Template decomposition, intervolve product operation, least squares approximation, computer graphics, image recognition.
　　在过去的10年中，形态模板作为一种强有力的工具，已广泛用于图像处理和分析［1～3］.基本形态扩张和侵蚀以及它们的组合的图像运算操作也对形态模板元素的分析、提取起了很大的作用.对于形态模板分解的需求是基于下面两种要求提出的.第1，几种专门的支持形态运算图像处理模式（结构）对模板的大小和形状有一些约束条件，如典型的3×3模板.但是形态模板并无必要限制在这样小的一个邻域内.对于这种情况，将形态模板分解为小邻域模板的方法为形态模板的操作运算提供了有效手段.许多学者［1～6］已经注意到了关于二值图像或灰度图形态模板分解的问题.第2，它有助于降低计算一个特定的图像形态变化的复杂度.
　　一个可分解的模板是指，该模板可做成一个具有水平向量和垂直向量的向量矩阵模板，并且这个模板的分离部分在最小二乘意义上与原始模板逼近.本文提出的这种方法的实质是找出可分离模板的一组在子空间正交的基，然后将指定的模板投影到子空间的基模板中，所产生的模板与原始模板具有最小二乘意义上的逼近.对于原始模板可分解的情况，这种方法产生了模板的精确分解，但其要求的计算量很大，特别是取得N1×N2模板的最小二乘分解，需要2N1N2(N1+N2-1)次乘法和(2N1N2-1)(N1+N2-1)次加法.
　　本文提出了一种简化算法，用于实现形态模板的最小二乘逼近的分解，并降低计算复杂度.同时，针对图像中直线交点、端点的形态模板检测进行了试验研究.
1　用于图像信息提取的形态模板与卷积运算
　　为了对图像空间的各种结构信息进行提取，常常使用某种特定的二维形态模板进行空间卷积运算，以达到突出某种信息或抑制另一种信息的目的.空间卷积是对邻域的各点进行线性（加权）运算，卷积的权函数可以表示成一个矩阵，通常称为形态模板.根据选择，模板N1×N2的大小可以为3×3，5×5或7×7等.空间卷积的一般形式为
　　　　　　(1)
式中Q为输出图像阵列，F为输入图像阵列，W为卷积阵列.
　　平滑算子是一种常用的消除图像噪声的形态模板，以下是4种典型的模板算子.

　　对于线状物体，根据所要检测的方向线，可以设计一些方向算子，用以分别检测纵向、横向、左对角线和右对角线方向的线状物体，如下所示。

　　　　　　(a) 横向　 　 (b) 右对角线方向　　　 (c) 纵向　　　　　 (d) 左对角线方向
　　由于在形态模板移动运算过程中，每个像素点需要进行n×n区域的局部运算，其计算量很大，尤其对于大幅面工程图纸扫描图像以及实时性要求较高的应用系统，其影响较为显著.同时，随着目前扫描分辨率的显著提高，图像的精细程度也在明显提高，使用小的形态模板，一方面限制了图形结构的完整性分析，另一方面,计算量也显著增加，因此,越来越多的各种扩展形态模板（n>3）使用到实际的图像结构分析之中.考虑到相邻点的相关性，如何找到两组正交的一维基来取代这种二维的局部运算是本文考虑的关键之所在.即通过对图像进行两个正交的方向各只进行一次的一维运算，来完成形态模板的二维运算功能.
2　形态模板的分解逼近算法
　　设有一个N1×N2的矩阵形态模板
　　　　　　　　　　　(2)
这里的关键是确定两个模板，一个是起垂直作用的，另一个是起水平作用的，即
　　　　　　　　　　　　　(3)
并且要求这些分离的模板与原模板具有最小二乘逼近.该模板在平方误差意义上逼近，即
　　　　　　　　　　(4)
因此，逼近误差为
　　　　　　　　　　　　(5)
由于该误差ε要求最小（最小二乘准则），则
　　　　　　　　　　　　　　(6)
　　　　　　　　　　　　　　(7)
将式(6)展开并简化，则得到
　　　　　　　　　　　(8)
同样地，由式(7)展开并简化，则得到
　　　　　　　　　　　(9)
式(8)和式(9)的集合表示了N1+N2个线性方程组，并且有N1+N2个变量，但是，其中只有N1+N2-1个方程是线性无关的，因此，可任选rN2-1=0，则其余方程用矩阵表示为
PQ=S，　　　　　　　　　　　　　　　　　　(10)
其中，
　　　　　　　(11)
这里,IN是N×N单位矩阵，ZN×M是一个N×M的矩阵，其元素由式(2)算出.CN1是一个N1个元素的列向量(c0,c1,...,cN1-1)T，RN2-1是N2-1个元素的列向量(r0,r1,...,rN2-2)T.类似地，XN1和YN2-1也是列向量，其元素由下列公式算出.
　　　　　　　　　　　　(12)
　　　　　　　　　　(13)
　　上面N1+N2-1个线性方程所表示的矩阵方程可以通过计算矩阵P的逆矩阵获得求解.考虑到矩阵P是对称矩阵，其逆矩阵也是对称矩阵.为计算矩阵P的逆矩阵，本文使用下面两个矩阵理论的结论.
　　结论1. 设A，D为对称矩阵，则出现在表达式中的逆矩阵存在.即
　　　　　　　　(14)
这里,E=D-BTA-1B,F=A-1B.
　　结论2. 设G是一个非奇异矩阵，且U，V是两个列向量
　　　　　　　　　　(15)
该式给出了从矩阵G的逆阵计算［G+UVT］的逆阵的一种方法.
　　本文运用结论1，其相应的元素表示为
A=N2IN1,B=ZN1×(N2-1),D=N1IN2-1,　　　　　　　　　　　(16)
这样就可以得到
A-1=N-12IN1,F=N-12ZN1×(N2-1)，E=N1IN2-1-N1N-12Z(N2-1)(N2-1).　　　　(17)
　　为了计算矩阵E的逆阵，使用结论2，则
　　　　　　(18)
代入上面结论公式，并加以简化，则有
E-1=N-11［IN2-1+Z(N2-1)×(N2-1)］.　　　　　　　　　　(19)
因此，可以得到
FE-1=N-11ZN1×(N2-1),　　　　　　　　　　　　　(20)
A-1+FE-1FT=N-12IN1+(N1N2)-1(N2-1)ZN1×N1.　　　　　　　　　(21)
　　所以，式(14)中矩阵P的逆阵可由下式给出．
　　　　(22)
　　在最小二乘逼近条件下的模板分解的分量公式可简单地由Q=P-1S求出.这样，模板分解的垂直向量为
ci1=N-12xi1+α， 0≤i1<N1,　　　　　　　　　　　　　(23)
其中
　　　　　　　　　　(24)
类似地，模板水平向量为
ri2=N-11(yi2-yN2-1)，0≤i2<(N2-1).　　　　　　　　　　　(25)
　　形态模板分解算法过程如下
　　〈1〉 计算
　　　　　　　　　　　　(26)
　　〈2〉 计算
　　　　　　　　　　　　(27)
　　〈3〉 计算
　　　　　　　　　　　(28)
　　〈4〉 由式(23)计算　　　　　　　{ci1;0≤i1<N1}．
　　〈5〉 由式(25)计算　　　　　　　{ri2;0≤i2<(N2-1)}，其中rN2-1=0．
以上算法需要N1+N2-1次乘法和2N1N2+2N1+N2次加法.
3　应用实例——基于形态模板的交点搜索算法
　　本文以图纸矢量化技术中的交点测试试验为应用实例，导出以距离测试函数为依据的二维形态模板，通过形态模板的分解计算来实现交点的快速计算和检测，具体描述如下.
　　在工程图纸扫描图像中，大量的图形是以直线表示的，若能准确识别直线的交点中心位置及直线端点，则采用任意两点之间的光栅点检测算法就可以判定直线的存在性.
　　图1列出了扫描图像中直线交点的存在形态.现在的问题是：如何建立一种模板对每个像素的邻域进行形态学运算，并产生一个新的图像.在这个新的图像中，直线的交点、端点信息应充分表现出来.从视觉的角度来看，直线的交点总是表现为较黑的区域，即黑色线素密度较高的区域，如图1中(b)～(d)、(g)、(i)、(j)中的中心区域即为高密度区域.直线的端点位置一般位于局部高密度线的截断点位置.普通直线的中间部位不存在这种截断点位置.

图1　图纸扫描图像中的直线交点形态
　　实现这一思想的方法是计算每一个像素点（邻域内）的密度值，该密度值反映了以该像素点为中心的小窗口（邻域）内的黑度情况.为此，建立一个距离权函数w(t)，如图2所示，愈是靠近中心点的像素（即邻域内t值愈小的像素点），其密度贡献愈大，一般可表示为
w(ti)=1/(tni+1)， n=1,2,3,...，n为收敛指数，　　　　　　(29)
　　　　　　　　(30)
式中ρ(i)为密度函数.距离权函数w(t)的选择方式很多，可以是指数衰减函数、对数衰减函数或倒数衰减函数等，距离t值的计算一般用欧几里德距离表示.以一个5×5（m=5）的距离函数为例［7］，设距离模板为

使用以上模板分解算法，可得到

其中为由(4)式得到的逼近的分离模板，由(5)式可计算逼近误差为ε＝0.6228.

图2　距离权函数ω(t)
　　由于和为两组正交的基，在两个方向所进行的计算是线性无关的，并且λ和λ也是线性无关的（λ为任意比例系数）.因此,分别在x和y方向使用向量模板和所产生的累计密度函数ρ与直接使用二维模板计算的结果是一致的，仍然满足最小二乘逼近.
　　这样，由式(29)、(30)可计算图像中每个像素点上的密度值，对于孤立的直线或直线的非相交部分，高密度值反映了直线的中心位置，这一点所产生的效果与细化算法产生的效果是一致的.但在直线相交的地方，则明显产生较高密度值，而局部最高密度值的位置正好是交点的中心，由此可以确定直线交点的中心位置.直线的交点和端点位置是在密度图像上局部搜索完成的.
　　判断一个像素点p为交点的必要条件是：
　　〈1〉 在p邻域窗口内，满足ρ(p)>ρ(i)，i=1,2,...,N，且p≠i.
　　〈2〉 由p向外延伸的搜索最远密度值相近点j∈（ρ(p)-ρ(j)<δ），满足两点距离|j-|<η.
　　判断一个像素点p为端点的必要条件是：
　　〈1〉 在p邻域窗口内，满足ρ(p)-ρ(i)>ε（ε可取负数，-1.0<ε<0.0），i=1,2,...,N，且p≠i.
　　〈2〉 由p向外延伸的等高密度线{j}（|ρ(p)-ρ(j)|<δ）只有一个方向，且位于同一方向，即αj1p,j2p<μ（呈直线向外延伸）.
　　在直线交点及端点确定的基础上，对任意两点之间直线的存在性进行光栅、矢量混合检测，采用递归求中点的方法（Fractal算法），判别中点是否落在黑色像素点上，满足两点间所有像素都在黑色像素上，则两点构成直线.由于采用逐次迭代算法，两点间不构成直线的中点一般只迭代1～2次即可终止，因此，实际计算量较小.
4　结　论
　　本文提出一种形态模板的分解逼近算法，它将局部二维运算改变为两个正交方向的一维线性运算，满足最小二乘逼近准则，对于提高形态图像处理的计算效率是一种非常有用的技术.同时，文章结合图像识别中的线矢量化问题提出了一种应用形态模板处理技术识别直线的交点和端点，它与细化算法相比具有较高的定位精度和较快的运算速度.目前这种算法还只是针对直线的情况，进一步的研究将扩展到对一般图素的特征点识别上.该技术的难度在于,需要找到一种或几种正交的理想形态模板，用于检测各种类型的特征点.
*　本文研究得到香港有利集团基金资助.
本文通讯联系人：邹荣金，南京210093,南京大学计算机软件新技术国家重点实验室
作者简介：邹荣金，1962年生，博士，副教授，主要研究领域为计算机图形学，图像识别.
　　　　　蔡士杰，1945年生，教授，博士生导师，主要研究领域为计算机图形学，CAD技术.
　　　　　张福炎，1939年生，教授，博士生导师，主要研究领域为多媒体技术，计算机图形学.
作者单位：邹荣金，蔡士杰，张福炎（南京大学计算机软件新技术国家重点实验室　南京　210093）
　　　　　邹荣金，蔡士杰，张福炎（江苏理工大学计算机科学系　镇江　212000，E-mail: zjzrj@public.zj.js.cn）
参考文献：
［1］Shih F Y, Mitchell O R. Decomposition of gray scale morphological structuring elements. Pattern Recognition, 1991,24(3):195～203
［2］Chang J Y, Chen C C. Decomposition of additively separable structuring elements with application. Pattern Recognition, 1993,26(8):867～875
［3］Zhuang Z, Haralick R M. Morphological structuring elements decomposition. Computer Vision, Graphics Image Processing, 1986,35(4):370～382
［4］Davidson J L. Nonlinear matrix decompositions and an application to parallel processing. Journal of Mathematics Image Vision, 1992,10(1):169～192
［5］Gader P D. Separable decompositions and approximations of gray scale morphological templates. Computer Vision, Graphics Image Processing, 1991,53(5):288～296
［6］Goutsias J. Morphological representation of discrete and binary image. IEEE Transactions on Image Processing, 1991,25(6):1369～1379
［7］吴敏金.图像形态学.上海:上海科学技术文献出版社，1990. 23～57
(Wu Min-jin. Image Morphologic. Shanghai: Shanghai Scientific and Technological Literature Publishing House, 1990. 23～57)
收稿日期：1997-11-20，修改日期：1998-09-25
