312.5边缘检测快速算法前向递推y.(n)x(n)y(n)J+(n)后向递推图2.20指数滤波器递推算法dH(z)若h(n）的Z变换为H（z），则nh（n）的Z变换为一dz由上述性质,形式为 p(n)e-(p(n)为关于 n的多项式)的 Z 变换均可表示为-号的Z变换H(z)与H(z）的各次导数的和，下面举个最简单的例子，即Deriche提出的一阶微分滤波器h(n)=cne-号，其中c为上面讲过的归一化系数.由式(2.40)和式(2.41)，若H为e-号的Z变换，ze-11H-H++H.:-e-12则由 Z 变换性质,h(n)=cne-号的 Z 变换为dHdH+H(z)dzdze-12(1-e-1z)2(1-e--1)2-02-e-ax1-2e-02-1+e-221-2e-z+e-22=H++H.类似于式（2.43）及（2.44)的推导，得到递推公式为y+ (n) = (2e-y+ (n + 1) -e-号y+ (n + 2) - ce-α(n +1))y-(n)=(2e-y- (n1)—e-号y-(n-2)- ce-(n-1))y=y+ (n) +y_ (n)注意到计算y+(n）与y-(n)时递推阶数为2(如计算y+（n）时需要y+（n+1)与y+（n+2)），总的计算复杂性为乘法次数5N，加法次数4N.一般来讲，e-前的多项式次数越高，递推阶数也越高.利用上述性质与Lagurre正交多项式的性质，李炳成、马颂德[Li1994]提出了将任意形状（例高斯滤波器）的滤波器用Lagurre正交多项式与对称指数函数的乘积来逼近，可以证明，当多项式次数为2次或3次时就能很好逼近高斯函数，用此方法，任意形状的滤波器（例如√G）都可以递推实现
32第二章边缘检测形状为h(n)=sin(wn)e-(Deriche一阶微分滤波器的准确形式)的滤波器也可以用递推实现，方法是将sinam写成一），从而使h（n）可写成两个指数函数的差，e再用前面所说的方法实现递推算法.可以证明，该滤波器的递推阶数也是2（详见[Deriche1987]).2.5.2二维可分离滤波器一般的二维滤波器h（m，n），对NXN图像进行一次卷积需N2Xw2运算（w为滤波器宽度），但如果h（m，n）可写成如下可分离形式：h(m.n)=h,(m)hz(n)则上式Z变换为H(21+22) = H,(21) .H2(22)上式表示，H（21，22)滤波器可用两个串联的滤波器H,（2.）与H（2）实现，由于H（2）只与有关，在空间域中就是将图像各列看作一维信号，逐列作一维卷积：然后将卷积后所得图像再用H（z）滤波，即将图像各行看作一维信号，逐行作一维卷积.由于每个一维滤波器的计算复杂性为N?（w为滤波器窗口大小，若为递推滤波器，则w为递推阶数），故总的计算复杂性为2Nw，与原计算复杂性Nw2相比，当w较大时，可减少很多.上节提到的一些滤波器的二维形式可采用如下可分离滤波器：（1）高斯滤波器若将一维高斯平滑滤波器记作g（），则各向同性的二维高斯平滑滤波器为+yG(r,y) = g(r) · g(y) :202元g2显然，该滤波器为可分离滤波器而二维高斯-拉普拉斯两阶微分滤波器为G+G1+VG=ar+aye=2元g+a该滤波器显然不是可分离的，但可写成1f-1e+(1)e-2e-2=G +GzVG=2元g2元g0可见，√G为两个滤波器G，Gz之和，而G,与G，均为可分离滤波器.其中G（或G2）分别为y（或r)方向上的平滑滤波器与r（或y)方向上的两阶微分滤波器.若高斯函数的有效窗口尺寸为w（w=6a），则以上算法总的计算复杂性为N2（w+w）×2=4Nw，若不用分离算法，则为Nw，当w>4时，分离算法速度快，（2）.对称指数滤波器一维指数平滑滤波器为a-上Eih(r) =2g各向同性的二维对称指数滤波器为
332.6图像低层次处理的其他问题-e-tzl = h(r)h(y)h(α,y) =4g2显然，上述滤波器为可分离滤波器.两阶微分指数滤波器为子h(r,y)子h(r,y)=+9(le-t-8()e--(y)e-号Vh=ar2g3/20ay211国一号--2g3/.2g2320实现√h的递推算法可用图2.21表示，其中，h（a）与h（y）分别为图像行与列方向上的指数平滑滤波器.由2.5.1节知，它们分别由行方向或列方向上的双向递推实现（算法如图2.20所示），计算复杂性分别为3N2，故总的计算复杂性为12N2h)hx)输人俞出图2.21二维两阶差分可分离指数滤波器对于以上章节中所提到的其他滤波器，也可以类似处理，2.6图像低层次处理的其他问题在本书引言中讲到了Marr的计算视觉理论框架，在计算机视觉中常常将该理论框架中求基元图的部分称为图像低层次处理，本章主要讲述边缘点抽取的一系列算法，在以后的许多章节中包含了大量的基于边缘特征点的各种三维视觉算法，故我们将边缘点检测，这一本应由图像处理的专著介绍的内容放在本书作为第二章，实际上，在三维计算机视觉中，除了常需要边缘点的信息外，还需要许多由图像处理方法得到的信息，主要有：（1）我们常需要将孤立的边缘点连接起来，构成某一物体在图像上形成的一个区域的边界线.因此，用上几节讲述的方法求出边缘点后，还需要进行一系列的后处理，将边缘点连接成闭合的曲线（作为物体的边界线）或有意义的直线段或曲线段（例如多面体的校边，圆柱体两边的椭圆）.由于噪声与图像离散化的影响，在链接与曲线拟合中都需要有效的算法克服边缘点位置误差与虚假边缘点的影响，当各种边缘曲线由于物体的互相遮挡而互相相交或互相遮挡时，如何决定哪些边缘应放在一起处理以构成有意义的边界线更是一个复杂的问题.（2）在Marr的基元图中还包括一些基元，如角点，线段的端点，区域图像的纹理特征等，这些基元的抽取也有不少工作需要研究，（3）找出具有相同纹理特征的区域或由边缘点组成的闭合曲线围成的区域，称为图像分割（imagesegmentation），物体与背景一般属于不同区域，在一些简单工业场合（例传
34第二章边缘检测送带上的简单工件），这种分割比较容易，在室外自然环境或称非结构环境中则相当困难。以上这些问题在一般图像处理的书中都会讲到.读者可阅读[Haralick1992].应该指出的是，虽然图像处理已有将近40年的历史，但以上这些问题仍没有很好地解决，或者计算复杂性很高，或者不能适应多种变化的场景，或者抗噪声能力差等等.因此，图像低层次处理仍然是一个活跃的研究领域。从方法上来讲，本节讲到的边缘抽取方法都是基于线性算子的滤波方法，近年来，一些基于非线性算子的方法也得到很大重视，尤其是基于数学形态学的方法，读者可参阅[Haralick 1992].思考题1.设信号为以下矩形脉冲函数：10,<0,>Af(r) =0≤AC:试推导当两阶微分滤波器分别为表2.1给出的六种滤波器时，过零点与边界点的偏差。2.若对称平滑滤波器满足规一化条件f(a)dr=1，证明由它的n阶微分得到的n阶微分滤波器f.(r）满足以下规一化条件：0,0<i<n"f.(r)dr((- 1)"n!,i=n其中1为整数.证明在离散形式下，上述关系也成立（见2.5.1节）.3.由上述规一化条件，推导一阶差分滤波器f(n）*csinwze-号的规一化系数c.推导实现该滤波器的递推公式.+为旋转不变算子，即当图像于(z,)旋转后，计算值在对4.证明Laplace算子vf(t，y）=azfay应点相等.5.在有噪声的情况下求离散信号f(n）的一阶差分时，本书讲述的方法是用某种平滑滤波器的一阶差分（即一阶差分滤波器）对信号滤波，还有一种方法：在每一点n二n处，按该点与该点邻域点的f（n）的值，用最小二乘法将（n）用一次、两次或三次曲线逼近，再用连续函数求导的方法求该点的微分，试证明，这种方法等同于用某种一阶差分滤波器滤波的方法.试分别推导当采用一次、两次或三次曲线逼近时所等同的一阶差分滤波器，参考文献[Babaud 1986] J.Babaud,A.Witkin and R.Duda,Uniqueness of the Gaussian Kernel for Scaling-Space Filtering,IEEETrans.PAMI,Vol.PAMI-8,1986.[Canny1983] Canny,FindingEdges and Lines in Images,MITTechnical Report,Rep.720,1983.[Canny1986]Canny，AComputational ApproachtoEdgeDetection，IEEETrans.PAMl,Vol.PAMI-8.1986.[Cong1996] G.Cong and S.D.Ma,Nonlinear Diffusion for Early Vision,Proc.of 13th ICPR,Vienna,Austria,Aug.,1996.[Deriche 1987] R. Deriche, Using Canny's Criteria to Derive a Recursively Implemented Optimal Edge Detector, Int.J.ComputerVision,Vol.6,1987.[Haralick 1992] R.M.Haralick and L.G.Shapiro,Computer and Robot Vision,Addison-Wesley Publishing Compa-
参考文献35ny,1992.[Li 1994J B. C.Li and S. D. Ma,Approximation of an Arbitary Filter and Its Recursive Implementation, PatternRecognition,Vol.27,No.12,1994.[Ma 199s] S.D.Ma and B.C.Li,Derivative Computation by MultiscaleFiletrs,Europe-China Workshop on Geometric Modeling and Invariant, Xi'an, China,1995.[Marr1982]D.Marr，Vision，W.H.FreemanandCompany，SanFrancisco，1982.中译本：规觉计算理论，姚国正、刘磊、汪云九译，科学出版社，1988.[Poggio 1985] T.Poggio,H.Voornees and A.L.Yuille, ARegularized Solution to EdgeDetection, Technical Report,Rep.AIM-833,MITAI Lab.,May,1985.[Sarkar 1991] s. Sarkar and K.L. Boyer, Optimal Infinite Impulse Response Zero Crossing Based Edge Detection,CVGIP:Image Understanding,Vol.54,No.2,1991.[Shen1985]J.Shen andS.Castan,Fast FilterTransformTheoryandDesign for ImageProcessing,Proc.IEEECon-Ferenceon ComputerVision andPatternRecognition,SanFrancisco,USA,1985.[Shen1992]J.Shen and S.Castan,AnOptimal LinearOperator forStepEdgeDetection,CVGIP:Graphical ModelsandImageProcessing,Vol.54,No.2,1992.Tikhonoy1gzzIA.N.Tikhonoy and V.Y.Arsenin,Solution of Ill-posed Problems.New YorkUSA:Halsted1977.[Witkin1983]A.Witkin,Scale SpaceFiltering,Proc.Int.Joint Conf.Artif.Intell.,Karlsruhe,Germany,1983.[Wu1990] L.D.Wu and S.H.Xie,Scaling Theorem for Zero Crossing,IEEETrans.PAMI,Vol.PAMI-12,1990.【Wu1993］吴立德，计算机视觉，复且大学出版社，1993.[Yuille1986]A.L.Yuille and T.A.Poggio,Scaling Thereoms for Zero Crossing,IEEE Trans.PAMI,Vol.PAMI-8,No.1,Jan.,1986