RSD-TR-7-86 PULSE AND STAIRCASE MODELS FOR DETECTING EDGES AT MULTIPLE RESOLUTION1 Mubarak Shah and Arun Sood Department of Electrical and Computer Engineering Wayne State University Detroit, Michigan 48202 Ramesh Jain Department of Electrical Engineering and Computer Science The University of Michigan Ann Arbor, Michigan 48109 June 1985 CENTER FOR RESEARCH ON INTEGRATED MANUFACTURING Robot Systems Division COLLEGE OF ENGINEERING THE UNIVERSITY OF MICHIGAN ANN ARBOR, MICHIGAN 48109-1109'This research ws jointly conducted at Computing Research Lab at Wayne State University, ad at Robotics Division of CRIM at the University of Michigan under U.S. AFOSR Contract No. F49620-82-C-0089.

TABLE OF CONTENTS 1. Introduction..................................................................................................... 2 2. Edge Operators:................................................................... 5 3. Laplacian of Gaussian Operator...................................................................... 7 4. Edge Models........................................................................ 10 4.1. Step Edge................................................................... 11 4.2. Ramp Edge............................................................................................. 12 4.3. Pulse Function...................................................................................... 17 4.4. Staircase Function................................................................................. 18 5. Zero-crossing Contours................................................................................ 18 6. Noise Analysis..................................................................... 28 7. Two Dimension Case:..................................................................................... 29 8. Summary and Conclusion...........................................................37 9. References...................................................................................................... 39 so u

RSD-TR-7-86 ABSTRACT Present step and ramp edge models are inadequate for edges detected by multiresolution operators. Since isolated edges rarely occur in real scenes, we propose new edge models based on the pulse and staircase functions. In these models we include the effect of one edge on another neighboring edge which propagates through at higher operator size. Depending on the mutual polarities of the steps in the staircase and pulse functions, the edge points related to these discontinuities attract or repel each other when the operator size increases. When they attract each other at some scale they collapse into one. In this paper, we demonstrate our models for the Laplacian of Gaussian operator, however, our results are equally valid for other multi-resolution operators. Index Terms: Edge models, multi-resolution operator, Scale-Space, Laplacian of Gaussian operator. Pulse and Staircase Models 1

RSD-TR-7-85 1. Introduction Edge detection is the first stage in most Computer Vision systems. Past experience with various edge operators has indicated that the problem of detecting edges in real scenes is extremely difficult. In an image, changes of intensity take place at many spatial scales depending on their physical origin. Therefore, the detection of all significant edges present in a scene requires that an edge operator be applied at various resolutions so that the discontinuities in intensities at all levels can be captured. An edge detection scheme based on multiscale analysis performed with filters of different sizes was first introduced by Rosenfeld and Thurston[RoT71]. Recently, Marr[Mar82] argued on these same lines by proposing multiple sized Laplacian of Gaussian operators. In his approach, the image is convolved with the Laplacian of Gaussian operator and the edge points are detected by locating the zero-crossings in the convolved image. By convolving the image with the operators having different variance, the intensity changes are separated at various scales. Once the discontinuity points1 are obtained at various scales2, the next step is to manage them efficiently in a representation which is better than the information present at any one scale independently. This problem has been called a channel integration problem. A set of discontinuity points detected at one scale is called a channel, so the idea is to combine all channels to come up with some representation which is better than any single channel independently.'We will use the terms discontinuity and edge points interchangeably.'The use of the term'scale" has been confused in the literature. One interpretation of scale is the degree of smoothing which essentially can be controlled by varying the variance of Gaussian. Scale has also been related to the rate of intensity changes in the gray level images. Since both of these are closely related in multi-resolution edge operators, we will use this term for both contexts without resolving the confusion. Pulse and Staircase Models 2

RSD-TR-7-85 One point of view has been that at lower scale, many edge points are obtained because some false edges are also detected. So an effort should be made to remove false edge points. Eklund et al [EEN80] do exactly this. They apply a threshold to the magnitude and the direction of edges to remove the false edge points. The removal of some edge points in busy areas usually creates gaps in the edge contours which are otherwise closed. They apply the good continuation measure to fill the gaps between any two end points of a broken contour. The good continuation measure is the function of the distance between two end points and the angle between the line joining those two points. The problem with this approach is that it uses the thresholding explicitly. Moreover, distinguishing between the false and the true edge points is not an easy task. Due to the nature of the operator, some false edge points are detected at all scales and some of the true edge points disappear at higher scale. Witkin [Wit83] presented a Scale-Space Filtering approach to this problem. In his approach, he convolves the signal with multiple-sized second derivative of Gaussian filters and detects the zero-crossings in the output of the filters. Those zero-crossing when plotted in (z,a) space form the contours. In order to simplify the representation, he proposed a ternary tree of zero-crossings called an interval-tree. The interval- tree transforms the zero-crossings contours into a data structure which can be easily handled. By proposing the Scale-Space approach, Witkin not only reaffirmed the importance and complexity of this problem but also intrigued many researchers ( see [ZuH84], [YuP83a], [YuP83b], [AsB84], [BWD83] etc ). Witkin's elegant approach motivated us to consider this problem in more detail in order to get a better understanding of Scale-Space in quantitative terms. In the long term our aim is to characterize the scene by a set of primitives. We want to fit the 3 Pulse and Staircase Models

RSD-TR-7-85 primitives to the edge points in the scale-space of an image. We want to use a priori knowledge about the behavior of the primitives in the scale-space in order to get a consistent fit of primitives at all scales. In this paper, we consider the known edge models and study their behavior in the Scale-Space. We have found that modeling edges using step and ramp functions is inadequate for the multi-resolution operators. It is noted that in real scenes isolated step and ramp edges are rarely encountered. In the case of edges which are present close to each other, at the bigger operator sizes, one edge affects a neighboring edge. Therefore, in this case, the behavior of such edges at bigger operator size is not similar to the behavior of an isolated edge. We will present new edge models based on the pulse and staircase functions. The pulse and staircase functions have two discontinuities close to each other. We find that depending on the mutual polarities of the steps in those functions, the zero-crossings attract or repel each other as the operator size increases. We will demonstrate our point of view by considering the second derivative of Gaussian operator or the Laplacian of Gaussian in two dimensions only. However, our results are equally valid for any other multi-resolution operator. In the next section, we review the related work on edge operators. In section 3, we define the second derivative of Gaussian operator in order to establish the notations. In section 4.1, we consider the step and ramp edge models and analyze their behavior at multiple scales. In section 4.2, we discuss the pulse and the staircase functions as candidates for edges which are detected at multiple scales. In section 5, we discuss the zero-crossing contours related to the intensity functions considered in section 4. In section 6, we study the effect of noise on our models. Finally, in section 7 we extend our results for 2-dimensional images. Pulse and Staircase Models 4

RSD-TR-7-85 2. Edge Operators: Most of the previous operators e.g. Beaudet, Robert, Kirsh, Heuckel and Sobel were differential in nature[BaB82, RoK82]. These operators essentially measure the first derivative which gives a rate of change of intensity values. The points where the local maxima of the first derivative occur are declared as the edge points. These maxima are located by using thresholding. Marr and Hildreth[MaH786] proposed the Laplacian of Gaussian operator. Under certain conditions the Laplacian approximates the second derivative[Hil83]. Therefore, the locations of zeros in the Laplacian signify the locations of extrema in the first derivative. The main motivation for this operator was the biological vision systems, because the output of this operator resembles the response of the center-surround cells found in biological visual systems. When Marr and Hildreth used this operator at multiple resolutions in their work it was first time that large mask sizes were used. In comparison to the previous commonly used 3 by 3 masks, the smallest mask they used was 31 by 31. It was found that the larger operators were able to suppress the noise to some extent. The next problem was to combine the output obtained from variable sized operators. They suggested a criterion that the zerocrossings that coincide over several scales are physically significant. This claim, however, was never justified. In recent literature two more edge operators for detecting step discontinuities have been proposed: Haralick's zero-crossing operator([Har80], [Har8l], [Har82], [Har84]) and Canny's edge detector[Can83]. Haralick fits a bi-cubic polynomial to the neighborhood of a pixel. He computes the first and the second directional derivative in the direction of the gradient of the intensity function in terms of coefficients of the polynomial. The coefficients for a given pixel location are found by using a least square fit to the gray 6 Pulse and Staircase Models

RSD-TR-7-85 level neighborhood of the pixel. A given pixel is declared an edge point if (i)the first derivative is above some threshold and (ii)the second derivative is equal to zero. There are two main differences between Haralick's operator and the Laplacian of Gaussian operator. Firstly Haralick's operator is directional while the Laplacian of Gaussian is not. In 2-D images at the points where Laplacian does not approximate the second derivative, Haralick's operator correctly detects the gray level changes in comparison to the Laplacian of Gaussian operator. Secondly Haralick's operator needs an explicit thresholding for the first derivative while the Laplacian of Gaussian operator does not generally require thresholding. Canny[Can83] proposed an edge operator for detecting step edges. The operator has a shape similar to the first derivative of Gaussian. In order to detect edge points, Canny finds out the extremas in the first derivative which are essentially zero crossings in the second derivative. Canny has claimed that Haralick's operator is equivalent to his operator. He further proposed that the bi-cubic is the only polynomial which can be used in Haralick's zero-crossing edge operator in order to get an optimum edge operator for the step edges. If the degree of polynomial is changed, the operator would not be optimum. His argument is based on the comparison between the graphs of the first derivative of Gaussian and Haralick's operator. Canny's first derivative of Gaussian operator is designed for detecting the step edges, but the methodology he has developed can be used to come up with an operator to detect any other function e.g. ramp. He has also proposed that his operator should be applied at various scales. When comparing Canny's operator with Haralick's operator, one may raise many interesting questions: Do we need to apply Haralick's operator at multiple scales? If yes, what is the scale in the Facet model? Is it the degree of poly Pulse and Staircase Models 6

RSD-TR-7-85 nomial or the neighborhood size or both? Recently Torre and Poggio[ToP841 proposed another edge operator which has the shape similar to the first derivative of Gaussian. In their approach they use the fact that the numerical differentiation of images is an ill posed problem. Therefore differentiation needs to be regularized by a regularizing filtering operation before differentiation. They show that the edge detection scheme consists of two steps: filtering step and the differentiation step. It is interesting to notice that these three edge detectors, proposed by Haralick, Canny, and Torre and Poggio, have similar shapes, however, they were designed by completely different approaches. 3. Laplacian of Gaussian Operator In this section, we describe the Laplacian of Gaussian operator and introduce some notations which will be used in this paper. For simplicity, we will consider only one dimensional case here. For one dimension the Laplacian becomes the second derivative. Our results, however, can easily be extended for two dimensional images. We denote the zero mean Gaussian density function with variance a by gf(z). Neglecting the multiplicative constant, gG(z) is given as follows: 2 C~()- 2ff2 (1) g (z) =e2 Let V2 represent the Laplacian (second derivative ) for two dimensions ( one dimension), and'*' represent the convolution operation. The second derivative of Gaussian is given as follows: 7 Pulse and Staircase Models

RSD-TR-7-85 S2 2 -2( = v2(~, = (l - 2 )e (2) The response of this operator for an input function f(x) can be computed by evaluating the following convolution integral. h(z) = (z) * v2g(z) (3) 00 h(2)= f f(t - I) V2g(7)d I -00 Using the linearity property of convolution, equation (3) can also be written as: h (z,a) = 2 I[f (z) * g9(z)] The convolution integral for discrete domain changes to summation as follows: 1 -m -1 h(t) = _ E f (a). o(i - a) _0 where m is the size of the image. Since O~ is circular symmetric, the above equation can be written as: 1 a-m -1 h"(i) = — S f (a). (o) (4) m oO According to the above equation, the response at a given pixel location is the weighted sum of neighboring pixels. The discontinuities in f(x) are related to the zero crossings in h (z). The positive zerocrossing can be defined as follows: if lim -.oh(z + ) < 0 and lim,-oh(2 - ) > 0 Pulse and Staircase Models 8

RSD-TR-7-86 then z is zero-crossing of h'(x ). Likewise the negative zerocrossing can be defined by reversing inequalities in the above expressions. The size of the neighborhood of a pixel used by the operators is called the mask size. In Eq.(4), we are performing convolution; therefore, the mask size should be the same as the image size. The Laplacian of Gaussian operator can be defined without referring to its mask size. In an implementation of the operator, however, we always have a finite number of bits. Therefore the effective value of g~ becomes zero for bigger neighborhood. Due to this fact it is not necessary to include the elements for which g9 is zero. The rate of decay of Gaussian depends on a. By knowing the word length used in an implementation, we can come up with an upper bound for a significant neighborhood size for a given a value. This way an approximate relationship between mask size and variance can be derived. Hildreth[Hil83] suggests two criterion to select the relationship between mask size and a. Firstly the positive area w of the operator must satisfy: w = V2i, which is motivated neurophysiologically. Secondly, the mask size should be such that the response of the operator for a uniform intensity must be zero. This last condition is a check for a numerical error. The idea is to consider a neighborhood size such that the values of the operator sum to zero. The Laplacian of Gaussian has positive values in the center surrounded by negative values. Truncating the operator by a smaller mask size would result in the loss of the negative surround. Thus, the overall sum would be positive instead of being zero( see [GrH85] and [Har85] ). In Figure 1 we show the operator having three different values of a. aFrom now onwards we will use the term'operator' for the Laplacian of Gaussian operator. 9 Pulse and Staircase Models

RSD-TR-7-85 l 00 278 l 00 (a) (b) 278 - 443 -'43 l 00 277 - 446 (c) Figure 1. Laplacian of Gaussian operator having a. a =3, b. a ==5, c. a = 7. 4. Edge Models Pulse and Staircase Models 10

RSD-TR-7-85 In this section, first we consider step and ramp edge models. Since the gray level function changes significantly at the edges of objects, the ideal edge can be modeled by a step function. In real images, however, the gray level change at the edges of object is not abrupt but, instead, changes gradually. Those edges can be modeled by the ramp function. Our aim here is to study the behavior of these simple edges as the function of A. In the next subsection, we will consider the pulse and staircase models for intensity functions. These functions contain two discontinuities which are a distance apart. We will then analyze the effects of a for these models. 4.1. Step Edge An ideal edge can be modeled by the step function. Step function, U(z), is defined as: 0 if z<0 U(x)=- C1 if x>0 If we convolve the step function with g (z) we get the following: h(zx)= c U(x) g (x) 00 2 h(z)= f cl U(zx-) g() dto= f c g~(r) d -00 -00 Now taking the second derivative, we get: Et (2) = V2 h()=-Cl ( ) fg() (6) In Figure 2.b-d we plot E for various values of a. The function E crosses zero at 11 Pulse and Staircase Models

RSD-TR-7-85 x = 0 for all values of a. The location of the zero-crossing corresponds to the location of the discontinuity in the step function. The amplitude c 1 of the step function appears as a multiplicative constant in Eq.(6). Thus this term essentially controls the amplitude but not the shape of the graphs shown in Figures 2.b-d. A zero-crossing is obtained at the corresponding location of a discontinuity regardless of the amplitude of the step function. Moreover, the location of zero-crossing does not change when a is changed in Eq.(6). 4.2. Ramp Edge Let us consider a ramp edge of width w and find out the response of the operator. The ramp function is defined as follows: 0 if 2<0 R(2)= c2z if 0<x<w (7) c2w if z>w f I, Let R and R denote the first and second derivative of the ramp function. Then from Eq.(7) we get: R' (2x)= Ce [U(z)- U(z - w) (8) R'()= c2t [6(x )- 6(x -w)1 (9) The ramp function is shown in Figure 3 with its second derivative. Convolution of R and R' with g (z) yields the following. x Z — R' * g9(2=) C 2w f C 2 9g() d q+ f JC 2 g()) dr] -00 -00 And Pulse and Staircase Models 12

RSD-TR-7-85 20 0 20 0 0 00 -20 0 -20 0 000 033 1 99 1 99 x-axis (X102) X-axis (XI02) (b) (6) 20 0 - 0 00 -20 0 20 0 -20 0 ns0 (c) 1 99 oco (d):<-x'102, -,.-'K~ -Z ". 1 Figure 2. The effect of a on the ideal step edge. In (a) we show the step function, while in (b) to (d) we show the output obtained by convolving the step function with the second derivative of Gaussian having a = 3,7,11 13 Pulse and Staircase Models

RSD-TR-7-85 E2'()= R ~ g~(2) E2' () = c 2 [6(2)-6(2 - w )] g9( ) which gives E2 (z) =e~2 [g1(z )- g9( -w)] (10) Figure 4 shows the graphs of E2' for various values of or. The function E2' has a zero-crossing at z = - which corresponds to the middle point of the ramp func2' tion. In this case the slope c of the ramp also appears as a multiplicative constant in Eq.(10). This implies the operator is not able to distinguish between two intensity changes which occur at a different rate. A zero-crossing is obtained in the second derivative corresponding to a discontinuity in step and ramp regardless of the rate of intensity changes. The actual value of an extrema of first derivative, not the position, carries the information about the rate intensity changes. Consider the example of ramp function R (x) defined in Eq.(7). The first derivative of this function is given in Eq.(8). An extrema of R' *9gx() is c 2w, which depends on the value of slope c 2 The slope c2 of ramp essentially tells the rate of intensity changes. Information about the rate of intensity changes is more important for operators which have a fixed mask size. Due to this fact, Haralick's operator and other fixed sized operators need some kind of thresholding for the first derivative of intensity function. However, when the discontinuities are detected at multiple scales this information is indirectly captured in the scale space of the image. Pulse and Staircase Models 14

RSD-TR-7-85 (A) (c) Figure 3. (a) ramp function (b) First derivative of ramp (c) second derivative of ramp. 15 Pulse and Staircase Models

RSD-TR-7-85 20 0 20 0 0 00 -20 0 000 (a) >3x-xls (X<102) 1 99 -20 0 00o 1 99 (b) x-axis (X 1C ) 20 0 20 o0 I /\ I' II 0 00 -20 0 (c) 000 x-ax 1 1 99 -2C 0 0<102) 00 1 99 (d) X-axis ( XI02) Figure 4. The effect of a on the ideal ramp edge. In (a) we show the ideal ramp edge, while in (b) to (d) we show the output obtained by convolving the ramp function with the second derivative of Gaussian having a = 3,7,11 Two remarks can be made concerning the ramp discontinuity. Firstly the zero Pulse and Staircase Models 16

RSD-TR-7-85 crossing in E r corresponding to the ramp discontinuity is solely due to the symmetric nature of the operator. Any other operator which is not symmetric will not be able to detect this discontinuity. Furthermore, in order to detect the discontinuity due to the ramp, the operator size should always be greater than the ramp width; otherwise the discontinuity will not be detected. In order to detect the discontinuities related to ramps of various widths we have to apply a variable sized operator. 4.3. Pulse Function Consider a function which is a pulse of width w as shown in the Figure 5.a. A pulse can be represented by the summation of two step functions i.e. f 3()= U(X)-cU(z-tw) where c is the ratio of the magnitudes of two steps. If we apply the operator to this function we get the following: h3() =f 3(x) * g (x) E3 (2x) = V2 h(' (x ) = - (2) + g ) ()+ C( -1) There are two discontinuities in the pulse function: one atz =0 and the other at -x=w as shown in Figure 5.a. We want the operator to respond at both of the discontinuity points, but the above equation cleary indicates that the locations of discontinuities are not necessarily at =0-O and w. For a fixed value of w, the pulse width, locations of discontinuity points depend upon the value of a. In Figures 5.b-d, we plot E' for three different values of a. It is easy to notice that the location of 17 Pulse and Staircase Models

RSD-TR-7-85 zero-crossings, corresponding to the discontinuities, shift as a increases. 4.4. Staircase Function The staircase function can be represented as the summation of two steps as follows. f 4(z)= U()+c2U(z-w) where 2 is the ratio of magnitudes of two steps. If we apply the operator to this function, we get the following: h(2.) = f /4() * 9'(2) E44 (2) = v) h4 () = 9 ( ) () - (2 g (2-w) (12) The staircase function has two discontinuities atz =0 and u=w, as shown in Figure 6.a. In principle we should get zero-crossings at these locations in function E4. We plot E' for three different values of a in Figure 6.b-d. In (b) E' crosses zero approximately at x = 0,w and also crosses zero at x -, a false zero-crossing. 2 While in (d) the function E' crosses zero only once. 5. Zero-crossing Contours The locations of zero-crossings in the function convolved with the second derivative of Gaussian can be plotted in the (z,o() space. These zero-crossings form the contours in the (z,a) space. In Figures 7-9 we show the zero-crossing contours for the Pulse and Staircase Models 18

RSD-TR-7-86 20 o 20 0 1 ii O 00 --— 1^ % I.... -20 o (a) 000 1 99 -20 0 o00 1 99 X-aXis (XIO) x-~~!5ik 22 (b) 20 0 0 00 20 0' r i ~~i \! \ 1 0 00 _-1,.' -20 0 r C3o (c) I 9g n I 99 -1 X, - axr I 3 XI,,. (d) X- x-ax I s ( XI0' Figure 5. The effect of a on the ideal pulse edge. In (a) we show the pulse function, while in (b) to (d) we show the output obtained by convolvi the pulse function with the second derivative of Gaussian having a - 3,7,13. The zero-crossings repel each other as a changes. 19 Pulse and Staircase Models

RSD-TR-7-85 20 0 -20 0 ({) 20 0 o 00 -20 o 000 300 1 99 1 99 x-axis (X102) X-ax is (XI02) (b) 20 0 0 CO -20 o (c) 20 0 - 1-1\ O 00 I -20 0 000 (d) / 1 99 I 99 x-3xlS(~~OD x ax S XI I Figure 8. The effect of a on the ideal staircase edge. In (a) we show the pulse function, while in (b) to (d) we show the output obtained by convolving the staircase function with the second derivative of Gaussian having a = 3,7,11. The sero-crossings attract each other as a is changed. Pulse and Staircase Models 20

RSD-TR-7-85 functions considered in the last section. The zero-crossing contours of the step and ramp functions are the straight lines as shown in Figure 7.a and 7.b respectively. The straight line in the (z,A) plane shows that the locations of zero-crossings due to the ramp and step do not change when a increases. In Figure 8 we show the zero-crossing contours of the staircase function. In these contours there is a straight line and a circular arc. The zero-crossings which constitute the straight line, in this case, are the false zero-crossings since they do not correspond to any actual discontinuities in the staircase function. They occur at this location due to the symmetric nature of the operator because for z = the expression for E4 in 2 equation (12) becomes zero regardless of the value of a. Note that the symmetry of the operator worked to our advantage in the case of ramp. The remaining two zerocrossings which correspond to the actual discontinuities in the staircase function make a circular arc. Since these zero-crossings shift towards each other as a is increased, at some value of a they collapse into one point which corresponds to the peak of the contour. In Figure 9 we show the zero-crossing contours for the pulse function. The zerocrossings related to the discontinuities in the pulse function make two diverging lines. Since the zero-crossings shift away from each other when a is increased, the two zerocrossings related to the pulse function never collapse into one. We can classify the zero-crossings in two categories. The first kind of zeros are not effected when the a is increased. The zeros related to isolated step or ramp fall in this class. At all scales the locations of those zeros are the same. Therefore we call these 21 Pulse and Staircase Models

RSD-TR-7-85 i (a) (b) Figure 7. The ero-crossing contours of the step (a) and the ramp(b) functions. The location of ero-crossing does not change as a is increased. Therefore, the sero-crossing contours for the ramp and the step functions are the straight lines. These Figures demonstrate that for ideal step and ramp we do not need multi-resolution operators. Pulse and Staircase Models 22

RSD-TR-7-85 Figure 8. The zero-crossing contours of the staircase function. The zero-crossings which make a straight line passing through the middle of the above contour are the false sero-crossings. Due to the propagation effect the true zero-crossings move towards each other when a increases. At some a' these zero-crossings collapse into one. 23 Pulse and Staircase Models

RSD-TR-7-85 zero-crossings Stationary Zero-crorsings. The second class contains the zeros of pulse and staircase functions. These zeros are Free Zero-crossings and, by increasing a, they can be displaced. In the case of pulse, the zero-crossings move away from each other, while in the case of the staircase they move towards each other. When the zero-crossings move towards each other, they collapse into one. The direction of displacement of free zeros depends on the mutual polarities of the two step functions: if both steps have same polarities, then the zero-crossings shift towards each other; if they have opposite polarities, then they shift away from each other. The zero-crossings shift at higher operator size because one edge affects neighboring edges. There are two step edges in the pulse and the staircase functions separated by a distance. Thus, at higher operator size the two steps affect each other and the zero-crossings get displaced. In the case of the ramp and step functions there is only one isolated edge, so the zero-crossings related to both of them do not move when a varies. We call this affect the Propagation Effect and define it as follows. Propagation Effect: The discontinuities within the field of an operator influence each other. Due to this the zero-crosaings attract or repel each other depending on the mutual polarities of steps. The value of a -at which two zero-crossings collapse into one is important. This corresponds to the peak of the zero-crossing contour. The location of the peak of curve u(z) can easily be found out from its maxima. Differentiating equation (12) with respect to dummy variable q along a contour in (z,) space we get: dE Edz E dor dr l 9 2 d al 9a d r dE Since E = 0 on the zero-crossings contour, so, - = Implicit Function d q Pulse and Staircase Models 24

RSD-TR-7-85 (a) (b) (c) Figure 9. The sero-crossing contours of the pulse function. The ratio of the magnitudes of two steps is 1,2 and 8 in a., b. and c. respectively. Due to the propagation effect the true sero-crossings move away from each other when a increases. 25 Pulse and Staircase Models

RSD-TR-7-85 (a) E r M (b) Figure 10. Propagation Effect. (a) at smaller operator size an edge is not affected by the neighboring edge. (b). due to bigger operator size the effect of the neighboring edge propagates. Theorem[VoG81/, we get: Pulse and Staircase Models 26

RSD-TR-7-86 d E d x da d E d d a The right side of the above equation vanishes when: d E d E _0. (13) dz Therefore the value of x where the above equation is satisfied is the peak of the curve a(z ). Now differentiating Eq.(12) with respect to x, we get: d E 1 _ 2 c (1Z — w )2 d"= ((1- ), (: )+ (1 - 0 ) g () - w ) (14) d a2 a2 + 2 22 The location of the peak of the contour can be computed by equating the right hand side of the above equation to zero. I x2 ~2 - (1- - )g'()+- 2 (1- ()2 )g (X-wV)= (15) If w is known this equation can be solved numerically to get the pair (z,) for the location of the peak of the contour. The value of a where the peak occurs sets an upper bound above which the discontinuities related to the staircase function of a given width can not be detected. On the other hand if the location of the peak in (z,a) space is known then the width w of the staircase can be computed from the above equation. The idea of the shifting of edge points is not new. It has been known qualitatively that the bigger operators dislocate the edge points and the smaller operators detect too many edge points. In fact, Canny found an uncertainity principle between the localization and detection. Which states that for a given signal to noise ratio an arbitrarily good localization or detection can be obtained by scaling but not both simultaneously. What is new is the Propagation Effect. This effect not only explains the localization 27 Pulse and Staircase Models

RSD-TR-7-85 quantitatively but it also describes the direction in which the zero-crossings shift. It has been proposed in the literature that the bigger operator can be used for good detection and the smaller operator for good localization. As it is clear from the Propagation Effect that this simple criterion will not work for the multi-resolution operators. For the zero-crossings which collapse into one at a particular scale, one always has to resolve the ambiguity of relating the one zero-crossing at higher scale to one of two zero-crossings present at the lower scale. An interesting observation which can be made from the above discussion is the following. It is known that the zero-crossing operator always favors closed contours. Isolated edge points are seldom obtained by this operator, but this was never explained before. The propagation effect explains the formation of the closed contours because the gray level functions corresponding to all the objects are the pulse or staircase functions. 8. Noise Analysis In the previous section, we considered the zero-crossings contours related to our edge models in the ideal situation. In this section, we study the effect of noise on these models. We introduce additive uniform noise with signal to noise ratio (SNR) of 1.5 and 6.25. We define SNR as follows: SNR = (Cin) where Cmi is the contrast of the smaller one of two steps present in the pulse and staircase functions, and a, is the standard deviation of the noise. This definition is close to one used by Abdou and Pratt[AbP79], except that we use the contrast of Pulse and Staircase Models 28

RSD-TR-7-85 smaller step since we have two steps in our models. In Figures 11-12 we show the results for the pulse and staircase functions with added noise. In Figure 11.a the signal with the added noise is plotted while in 1l.b we show the contour obtained by applying the operator to the noisy signal. In 11.c we apply a threshold to the magnitudes of the slope of zero-crossings in order to remove some of the noisy zero-crossings. In this analysis we are interested in two issues. Firstly we want to study the extent to which the actual shape of the contours are distorted due to noise. Secondly we want to know whether any false contour is formed due to the presence of noise whose shape is similar to the contours of the pulse or staircase functions. It is easy to notice that in the case of pulse function the actual shape of zerocrossing contour is well maintained even in the presence of noise. Very few of the noisy zero-crossings survive after the thresholding step. In the case of staircase the shape of contour remains the same in the presence of noise except straight line which passes through the center of the circular arc is distorted. As we mentioned before the reason for getting the zero-crossings which constitute the straight line is due to symmetry of the operator. In the presence of the noise the two terms in the Eq.(12) are not equal hence they do not cancel each other. Therefore, in some cases the zero-crossing in the center does not appear. 7. Two Dimension Case: In this section we apply results established for one dimension in the previous section to synthetic images. Our aim is to verify the Propagation Effect in the synthetic images and get an insight of behavior of zero-crossings at multiple scales. So that the 29 Pulse and Staircase Models

RSD-TR-7-86 70 0 45 0 20 o o 0 0 00 (a) 79 0 (b) 198 39 5 59 3'1 I a I 0 0 / i 1 J I i (c). Figure 11. Effect of Noise. a.Pulse function with SNR = 1.5 b. Zero-crossing contours without thresholding c.Contours obtained by applying threshold of 10 to the slope of ser-crossings. Pulse and Staircase Models 30

RSD-TR-7-85 75 0 47 5 20 0 - 0 00 19 8 39 5 59 3 79 0 1/' A \ /.'] * * v o (b)........ 1.-I....! ( (c) Figure 12. Effect of Noise. a.Staircase function with SNR - 8.25 b. Zero-crossing contours without thresholding c. Contours with threshold of 10 theory developed in this paper can be extended to solve the channel integration prob 31 Pulse and Staircase Models

RSD-TR-7-85 lem for the real scenes. In Figure 13.a we show a synthetic picture which has an infinite step edge. The gray levels related to the background and the object are 100 and 170 respectively. In b to d we show the results obtained by applying the operator having a equal to 3,5 and 7. For each operator size the step edge is detected at the actual location in the synthetic image. In the ramp in this case is 16 pixels. Each row in the synthetic image simulates the ramp function in one dimension. Therefore the overall image becomes some distorted form of the ideal step edge. In fact due to camera noise, quantization and lighting conditions in real scenes the step edges become ramp edges. As shown in Figure 14 the discontinuity related to ramp edge is detected by the operator at all operator size. The location of zero-crossing does not change when a varies. In Figure 16 we show a synthetic image with two infinite step edges separated by a distance. This image simulates a two dimensional staircase edge. The gray levels in each row of the image vary like one dimensional staircase function. In the part b and c of the Figure two edges besides the center edge are detected while in d only one edge is detected. This verifies the Propagation Effect. Finally in Figure 15 similar results are repeated for the pulse edge. Here the localization of edges due to Propagation Effect is obvious. In Figure 17 we show the image of a square object and the edges detected for a = 1,3,5,7. The behavior of edge points in the scale-space of this image is bit complex. In this example the Propagation Effect is present in all the the directions within a circular neighborhood of the operator. Therefore, the edge points close to the corners of the square are displaced farther than the points far from the corners. There is another reason for the large displacement of corner points besides the Propagation Effect. At Pulse and Staircase Models 32

RSD-TR7-865 (a) i-:i I (d) (b) Figure 13. a. Inmage of step edge. edges deteteed at b. a-3, c. a H5 and d. a: 7. The location of the edge does not change when a increases. 33 Pulse and Staircase Models

RSD-TRR-.785 Figture 14. a. Image of ramp edge. edgen detected at b. ar=3, c. a & 5 and d. a - 7. The location of the edge does not change when a inceremes, Pulse and Staircase Models 34

0 v 0 s 0:: *a 0W At %:::: O ~D:;:. _. Jn a *Q -,~'0 Z X5 o; 9$ = 0t a m: ~1 s~0 Q He~B Of5 i

RSDoTR47-86 (b) Figure 16. a. Image of staircae edge. edges detected at b. a: 3, c. e a - 5 and d. a 7. Two edges collapse into one in d. corner points the Ltaplacian does not approximate the second directional derivative Pulse and 8tair;case Models 36

RSD-TR-7-85 taken in the direction of gradient[Ber84]. In Figure 17.c a few points close to corners are displaced while in Figure 17.d most of the edge points are shifted except the central points. Due to this it appears that there are some kind of dents in the square. These dents disappear in Figure 17.d where the edge points in the middle are also displaced. Our aim, in this example, is not only to detect the edges of the square object. Any 5 by 5 operator will give reasonable results in this case. Motivation for this analysis is to gain knowledge about the behavior of the simple models in the scale space. The study about the models when integrated will ultimately lead us to detect the edges in a very complex real scene. 8. Summary and Conclusion In this paper we considered the problem of detecting gray level discontinuities at multiple scales. \We found that the current edge models are inadequate for edges detected by the multi-resolution operators. Since isolated step or ramp edges rarely occur in natural scenes, we proposed pulse and staircase models. In these models we include the effect of an edge on the neighboring edge which propagates through when the operator size increases. While analyzing the behavior of the pulse and the staircase models in the scale-space, we found that the zero-crossings attract or repel each other. When they attract each other at some value of a they collapse into one. In principle the Propagation Effect can be modeled such that one edge is affected by more than one neighboring edges. But for simplicity in this paper we considered only the effect of one neighboring edge. In our future work we want to fit the primitives to the discrete zerocrossings in the scale-space of the image. Using proposed models we expect to recover rich and 37 Pulse and Staircase Models

RSD-T4R-785 us to detect the edges in a very complex real scene. (b) (e) (d). Figure 17. a. Image of square object. edges detected at b. ra }, I c.c a 3, d. a 5 and e. a - 7. robust information about the intensity function. In particular we are interested to Pulse and Staircase Models 38

RSD-TR-7-86 extract information about the the contrast, slope and orientation of edges. 9. References [AbP79] I.Abdou and W.K.Pratt, "Quantitative Design and Evaluation of Enhancement Edge Detector Schemes", proceedings of IEEE, Vol. 67, 1979, pp. 753763. [AsB841 Asada H. and Brady, M. " The curvature Primal Sketch", MIT AI memo 758, 1984. [BWD83] J. Babaud, A. Witkin and R. Duda "Uniqueness of the Gaussian kernel for scale- space filtering" "Fairchild TR 645, Flair 2' [BaB82] Ballard D.H. and Brown, C.M. Computer Vision, Prentice Hall, Inc Englewood Cliff N.J. [Ber84] Berzins, V. "Accuracy of Laplacian Edge Detectors", computer vision, Graphics, and Image processing 27,195-210 (1984). [Can83J Canny, J.F. "Finding Edges and Lines in Images", M.S. thesis, MIT, 1983. [EEN80] Eklundh,J.,Elfving T.E. and Nyberg S. "Edge Detection Using the MarrHildreth Operator With Different Sizes", ICPR-6 1109-1112 [GrH85] Grimson, W.E. and Hildreth, E.C.'Comments on "Digital Step Edges from Zerocrossings of Second directional Derivative" ", IEEE PAMI-7 January 1985, pp 121-127. [Har80] Haralick, R.M. "Edge and region analysis for digital image data", Computer Graphics and Image processing, 12, 60-73, 1980. [Har8l] Haralick, R.M. "The digital edge" Proc. 1981 Conf. on Pattern Recognition 39 Pulse and Staircase Models

RSD-TR-7-85 and Image processing Dallas, Texas, 285-294, 1981 [Har82] Haralick, R.M. "Zero-crossings of Second Directional Derivative Edge Operator" SPIE proc on Robot Vision, Arlington Virginia, 1982. [Har84] Haralick, R.M.,"Digital Step Edges From Zero-crossings of Second Directional Derivative", pp 58-68, PAMI-8 January 1984. [Har85] Haralick, R.M. "Author's Reply", PAMI-7 January 1985, pp 127-129. [Hil83] Hildreth, E.C. "Detection of intensity changes by computer and biological vision systems", Computer vision, Graphics and Image Processing, 22, 1983, pp 1-27. [Mar82] Marr, David Vision, W.H.Freeman & company, San Francisco,!982. [MaH80] Marr, D. and Hildreth, E. "Theory of Edge Detection" Proc. R.Soc. Lond. B,207, 187-217, 1980. [RoK82] Azriel Rosenfeld and Avinash Kak, Digital Picture Processing, Academic Press. [RoT71] Rosenfeld, A. and Thurston, M. " Edge and Curve detection for visual scene", IEEE trans on Computers c-20, 1971 pp 562-569. [ToP84] V.Torre and T.Poggio "On Edge Detection", MIT AI memo 768, August 1984. [VoG81] Voxman.,W.I. and Goeschel, R.H. Advanced Calculus,Marcek Dekker Inc. New York, 1981. Wit83] Witkin Andrew, "Scale-Space Filtering", IJCAI-83 [YuP83a] A.L. Yuille and T. Poggio "Scaling Theorems for Zero-Crossings", MIT Pulse and Staircase Models 40

UNIVERSITY OF MICHIGAN 3 9015 03524 4295 RSD-TR-7-85 Artificial Intelligence Lab Memo NO. 722,1983. [YuP83b] A.L. Yuille and T.Poggio, "Scaling Theorems for Zero crossings", "MIT AI memo No: 272, 1983. [ZuH84] Zucker S. and Hummel R. w Receptive Fields and The Representation of Visual Information", 7-ICPR at Montreal, pp 515-517. 41 Pulse and Staircase Models