RSD-TR-2-8 7 Behavior of Edges In Scale Space by Yi Lu Ramesh C. Jain Department of Electrical Engineering Computer Science The University of Michigan Rnn Arbor, Michigan 48109 January 1987 Center for Research on Integrated Manufacturing Robot Systems Division College Of Engineering The University of Michigan Ann Arbor, Michgan 48109- 1109

Table of Contents 1. Introduction.................................... 2 2. A Survey of the Related Research Work........................................ 8 3. Definitions........................................ 22 4. The Scaling Properties of Edge curves.......................................24 4.1 D-isolated edge curve........................................ 26 4.2 Pulse edges............................................................................................. 27 4.3 Staircase edges........................................................................................ 31 4.4 Theorems and experiments......................................36 5. Properties of Regions in Scale Space........................................40 6. Discussion........................................ 43 7. Acknowledgements.......................................45 8. Reference.................................... 46 9. Appendix....................................... 51 10. Figures........................................ 96

RSD-TR-2-87 Abstract The analysis of multi-resolution edge detectors is facilitated in scale space. This report presents some mathematical results for understanding behavior of linear edges in scale space. A rigorous analysis of linear edges at different scales in images was performed to study the influence of other edges. Our analysis identifies precisely at what scale neighboring edges start influencing the response of an edge detector. Dislocation of edges, false edges, and merging of edges in scale space is studied to formulate rules for reasoning in scale space. The theorems, corollaries, and assertions presented in this report can be used to recover edges, and related features, in complex images. Our analysis is supported by several experiments. The future work for reasoning in the scale space is outlined. In addition, a related literature review is included in this report. This literature review allows us to learn from the experience of other people's work in edge detection, multiresolution problem and the scale space exploration. It also verifies that our research direction has not been investigated, and the results we have achieved are novel in the literature. Behavior 1

RSD-TR-2-87 1. Introduction In computer vision, the term "edge" usually refers to the point between two regions. Edges may represent the boundaries of objects, shadow lines, and so on. Edge detection usually forms the first stage of computation in a large number of vision modules. The success of high level computer vision processes relies heavily on good output from the edge detector. The importance of edge detection in computer vision has led to extensive work on this topic. In a gray level image, an edge point is a point where an intensity change is taking place; however, not all intensity changes are edge points. Many edge detectors start by detecting intensity changes in the image, and then apply some criteria to delete irrelevant information in order to extract true edges. Gradient-type operators are used to detect intensity changes. The gradient-type operators include the directional first and second differences and the rotationally symmetric Laplacian [12, 37, 42, 35, 3, 43, 40]. Other edge detectors fit a function to intensity values to detect edges. These edge operators view the image intensity function as a surface which is approximated by a set of basis functions. The edge detector parameters are estimated from the modeled image surface. Prewitt 138] was the first to suggest the fitting idea. Hueckel [23], Brooks [7], Haralick [18, 191], Haralick and Watson [20], all use this type of technique in detecting edges. Frequently, changes in light intensity reflect many spatial scales at which visible edges are formed. Changes of intensity take place at many spatial scales, depending on their physical origin. The presence of edges at many scales in an Behavior 2

RSD-TR-2-87 image makes the selection of a threshold for marking edges very difficult. Moreover, the scale at which interesting edges occur in an image is seldom known. As suggested by Marr & Hildreth [30J and Rosenfeld & Thurston [44], by applying different sizes of edge operators on an image, we can get a description of the signal change at different scales. In general, for a small scale operator, we get fine details of the intensity changes and the operator is more noise sensitive; for a large scale operator, we get coarse intensity change information. It seems that multiscale analysis, for tracking the behavior of some features of the signal across varying scales, can reveal precious information about the nature of the underlying physical process. The problem is not so much to eliminate fine-scale noise, as to separate events at different scales arising from distinct physical processes. It is apparent that for many tasks no one scale of description is categorically correct. With the introduction of the scale-dependent operator, there comes an ambiguity problem. Every setting of the scale parameter yields a different description; new extremal points may appear, and existing ones may be in a different location or may completely disappear. The recognition of this problem with a varying scale has spawned considerable interest in multiresolution descriptions of signals. Rosenfeld [44] was among the first in the computer vision field to explicitly propose an edge detection scheme based on multiscale analysis performed with filters of different sizes. Rosenfeld believed that the relative orientation of the neighborhoods determines the detected direction of the edges, and the size of the neighborhoods determines the detected width of the edges. Mart and Hildreth [30] proposed an important edge detector, the Laplacian of Gaussian operator, which Behavior 3

RSD-TR-2-87 strongly advocated the use of different sizes of the operator. Many researchers have applied various schemes of combining information from multiple scales to solve problems such as reconstructing visual surfaces [39, 9, 45J. However, these multiscale techniques all have a fundamental shortcoming: they provide no means for relating the descriptions at different scales to one another, or of deciding which scale to use under what conditions. The ambiguity introduced by multiple scale is inherent and inescapable. Thus, the goal of scale dependent descriptions is not to eliminate this ambiguity, but rather to manage it effectively and reduce it where possible. The multiresolution problem involves two aspects: (1) how to select the scales of operators for an image, and (2) how to combine effectively the edge information recovered at different scales. Both problems remain open. Our research work is motivated by these two problems. Since there are no general principles for selecting proper scales for an image, we believe the scale space originally proposed by Witkin [51], is a good starting point to describe the signal. The second problem is strongly domain and knowledge dependent. Different tasks require different information from an image. Knowledge based reasoning in scale space is an effective approach for recovering useful features [8]. Our long-term research goal is to compute important features using a top-down reasoning approach in scale space. Behavior 4

RSD-TR-287 Reasoning in scale space to recover goal-oriented information necessitates a good understanding of the behavior of different types of edges in scale space. Simple heuristics like the presence of edges in two adjacent channels will work only in simple cases. To build a good knowledge base for reasoning, analysis of edge behavior in many realistic image situations is necessary. Our aim in this report is to present results of our efforts to build such a knowledge base by rigorously analyzing edge behavior in scale space. We start our work by probing the behavior of linear edges at various scales in two dimensional images and establishing a mathematical base which describes the feature of zero crossings in scale space. The Laplacian of Gaussian operator, proposed by Marr and Hildreth in 1980 [301, is the edge operator we use. Our motivation for selecting this operator is the ease with which the behavior of this operator can be analyzed at different scales. We will use the contraction, L-G, to represent the Laplacian of Gaussian operator. In vision literature, there are several descriptions of the analytic form of the L-G operator, which differ only in an overall multiplicative constant that does not change the shape of the operator. We adopt the following form of the L-G operator [17]. In two dimensions, 2 a 02 + - 2); G(x, y) = exp[- Z2+2]; vG(xy)-a2(l -2 2 Behavior l

RSD-TR-287 where o is the standard deviation. The standard deviation controls the size of the operator, so it is also called a scale parameter. The L-G operator has many good properties and is the best one for scale experiments. However, it faces three main problems when the scale changes: (1) dislocation of edges, (2) missing edges, and (3) false edges. These problems cause: distortion of an edge curve shape and region area; omission of an edge curve and region; and detection of a false edge curve and region. Our aim in this report is to analyze the behavior of the L-G operator at different scales under different conditions, and relate this behavior to the observed edges and intensity changes. The problems studied in this report include the following: (1) causes of edge dislocation, (2) conditions for generating false edges, (3) conditions which cause omission of an edge curve, and (4) behavior of the zero crossings under various conditions when a increases. This reports includes three main parts: (1) Literature Review. The review covers various edge detectors including the L-G operator, the multiscale problem and the scale space description approach. Behavior 6

RSD-TR-2-87 (2) Our research results. We present our research results in one lemma, three theorems, a number of corollaries and four assertions. The rigorous mathematical proofs for the theorems and corollaries are presented. These theorems and corollaries are further applied to more general situations, the results are summarized in four assertions. A qualitative description as well as some experimental results are presented for each assertion. (3) Future research direction. Further work for reasoning in scale space is outlined. Behavior 7

RSD-TR-2-87 2. A Survey of Related Research Work This literature review includes: (1) a review on edge detectors; (2) important properties of the L-G operator; (3) multiresolution computation. 2.1. A Review on Edge Detectors Edge detection is important and difficult, and much research has been devoted to it. As a consequence, the literature related to this problem is enormous. We do not intend to give a complete review on edge detection, instead, we will confine ourselves to a few of the more important and pertinent edge detection techniques. If the reader is interested in more detailed information, many edge detection surveys can be found in the literatue412, 37, 42, 35, 3, 431. We will consider only two dimensional digital images. We classify edge detection techniques into two categories: (1) Gradient-type operators, which will include first and second order spatial derivative operators, and Laplacian type operators; (2) surface fitting functions. 2.1.1 Gradient-type technique Most edge detectors in this category begin by applying small differential operators to an image, followed by a detection operation to locate small edge segments. The idea behind the edge operator in this category is that intensity changes rapidly on the boundary of two regions. A sharp change in intensity will give rise to a peak in the output of a first derivative, or zero-crossings in the output of the second derivative operator. Generally, the initial differentiation is Behavior 8

RSD-TR-2-87 followed by a peak detection, or zero-crossing detection, thresholding and thinning operations are applied to localized boundaries, and edge segments that arise from noise in the image process are removed. A range of differential operators have been explored. Directional first and second differences and the rotationally symmetric Laplacian operation are frequently used. Examples of the first and second derivative operators are Roberts, Sobel operators [40, 37]. The difference between Roberts' operator and Sobel's operator is that the latter one does local averaging computing which tends to reduce the effect of noise. Sobel's operator is less sensitive to noise and surface irregularities than Roberts' operator, and it is still farely simple in computation. The Laplacian operator has also been used as an edge operator [43, 37, 33]. The Laplacian operator is given by V2f _df o 2f This is an orientation independent derivative operator. Its discrete form is given by: v21 (i,j) = [I(i+l,j) + I(i-l,j) + I(i,j+l) + I(i,j-l)] - 41(i,j). The Laplacian operator does respond to edges, but it responds even more strongly to corners, lines, line ends and isolated points. Thus in a noisy image, the noise will produce higher Laplacian values than the edges, unless it has much lower contrast. Many edge detectors utilize the Laplacian operator as the differential operation. The L-G operator is one of such operators, We will discuss it Behavior 9

RSD-TR-2-87 in the next section. 2.1.2. Surface Fitting techniques The edge operators in this category view the image intensity function as a surface which is approximated by a set of basis functions. The edge parameters are estimated from the modelled image surface. These methods allow more direct estimates of edge properties such as position and orientation, but since the basis functions are usually not complete, the properties apply only to a projection of the actual image surface onto the subspace spanned by the basis functions. However, the basis functions are a major factor in operator performance, especially their ability to localize edges. Examples of this technique include the work of Hueckel and Haralick [23, 19]. Hueckel's edge operator is based on a set of requirements which should be met by an edge detection scheme. The algorithm he proposed was an local nonlinear operator which is optimum solution to meet these requirements. Let D be a disk shape subimage of I, with intensity function E(x,y). The set of requirements are: (1) Nullifying rounding errors on the periphery of the disk D = { (x,y) I 2 + u < 1}. (2) The weight of the input data decreases towards the disk's periphery. (3) An operator which locates edges need not be sensitvie to noise of high spatial frequencies. Behavior 10

RSD-TR-2-87 (4) An operator which locates edges is by its nature sensitive to noise of low spatial frequencies. (5) The computing time should be minimal. From the above requirements, a set of functional equations are generated. The task of the operator is to best approximate E(x,y) by an ideal edge element F. He has given the approach for constructing an edge operator for the ideal step edge function. Hueckel provides no analytical model for the relationship between the noise process and the noise and the performance of the operator. Haralick used a facet model to accomplish step edge detection. He regarded the digital picture function I as a sampling of the underlying continuous function t. F was called the underlying gray tone intensity surface. He assumed that each neighborhood of the image, f, took the form: f(r,c) = kI + k2r + kSc + k4r2 + k6rc + k6c2 + k7rs + kgr2c + kgrc2 + klocs where r and c are the row and column coordinates. By using the discrete orthogonal polynomials over a two-dimensional neighborhood, least square coefficients fitting, he was able to determine ki, k2, k3, k4, k6, k6, k7, k t, kt. A pixel was marked as an edge pixel if in the pixel's immediate area there is a zero crossing of the second directional derivative taken in the direction of the gradient and the slope of the zero crossing is negative. The directional derivative was taken on f. Haralick also provided the statistical analysis of his technique, Behavior 11

RSD-TR-2-87 illustrating how to determine confidence intervals for the direction of the gradient and how this interval determines a confidence interval for the placement of the zero crossing. To support the proposed scheme, Haralick evaluated its performance, under a variety of criteria, against several other edge detection operators, most notably, the Prewitt gradient operator and the L-G operator. The evalutation led to the conclusion that, under these criteria, Haralick's method performed the best. Haralick has shown that the error of the fit has a chi squared distribution with n degrees of freedom, where n is the size of a square neighborhood used in the fit. This means that we are able to decrease the noise by increasing the neighborhood size. He suggested using a larger neighborhood size than 3x3. But there are no guidelines for selecting the optimum neighborhood size to estimate the unknown coefficients. Also, by increasing the operator size, there is a possiblity that more than one edge comes into the field of the operator, which will result in the wrong estimate of the f function. Canny [9, 1O1 has proposed an edge detector which is the sum of four complex exponentials and can be approximated by the first derivative of a Gaussian. The edge detection is performed by convolving the image with a function f(x) and then marking edges at the maxima in the output of this convolution. He gave three performance criteria on the output of the edge operator. They are (1) Low probability of error at each point. The probability of failing to mark real edge points, and falsely marking an edge point should be low. (2) Good localization. The points marked as edges by the operator should be as close as possible to the center of the true edge. Beh avior 12

RSD-TR-2-87 (3) Only one response to a single edge. The variational techniques are used to find the function f(x) that maximizes the first two criteria. Then Canny uses the third criterion to eliminate the multiple responses. He reduced the probability of marking multiple edges by constraining the distance between adjacent maxima in the response of the operator to noise. 2.2 L-G Operator The Laplacian-Gaussian(L-G) operator was proposed by Marr and Hildreth [30. The L-G operator, V2G, has two components, 2 and G, where v2 is the Laplacian operation and G is the Gaussian distribution. The derivative part of the filter, v2, is economical in computation, since v2 is the lowest order isotropic differential operator. The use of the Laplacian operator raises the following question: Will the zero-crossings in the output of the Laplacian correctly capture the intensity changes that we want to detect? Hildreth [221 has proved that V2 can be used to detect intensity changes provided the image satisfies some quite weak requirement. The requirement is that the variation of intensity along the orientation of the intensity change is at most linear. If an image satisfies this condition, the zeros of the Laplacian coincide with the zeros of the second directional derivative. Fortunately, this condition is satisfied in most natural images. If the intensity variation along an intensity change is highly nonlinear, the positions of the zerocrossings in the Laplacian will deviate from those of the second directional Behavior 13

RSD-TR-2-87 derivatives. The Gaussian filter has some important properties, they are listed as follows: 1. It is capable of being turned to act at any desired scale, so different sizes of filters can be used to detect different events in the image. 2. Gaussian is symmetric and strictly decreasing about the mean. Therefore in the convolution operation, the weight assigned to signal values decreases smoothly with distance. 3. Gaussian distribution is the unique distribution that it is simultaneously and optimally localized in both the spatial and frequency domains. If a blurring operator is very smooth in both the spatial and frequency domain, it is least likely to introduce any changes that were not present in the original image. 4. Gaussian distribution behaves well near the limit of the scale parameter a, approaching the signal's mean for large a, while approaching the unsmoothed signal for small o. 5. Gaussian is differentiable and integrable. Combining the Gaussian and Laplacian into a single operator, the L-G operator, one can now detect intensity changes occurring at a particular scale by locating the zero-crossings in the output of v2G(x,y). V2G has strong support from neurophysiological studies of the early processing in the human vision system. The psychophysical studies on vision system also reveal many facts supporting V2G operator. We sense image at quite a high resoBehavior 14

RSD-TR-2-87 lution. Viewing from a distance of three feet, one square inch covers an array of about 200x200=40,000 photoreceptors in the central fovea of the eye. Several layers of cells in the retina process the detected light intensity. These cells culminate with the output of the retinal ganglion cells whose axons form the optic nerve fibers that carry information to the visual contex. The receptive fields of retinal ganglion cells are organized as shown in Fig. 1 [26, 41, 211. Light striking the center of the receptive field excites the activity of the cell, while light striking the surrounding area inhibits it. The shape of the sensitivity distribution can be distributed mathematically as the difference of two concentric Gaussian distributions: L e exp[- r2 r2 Gl(r,a,1) - G2(r,o2)= 2exp 2c 2c2 where r is the radius from the center, and a1 and ~2 are the spatial scale factors of the excitatory and inhibitory distributions respectively. This operator is called Difference-Of-Gaussians(DOG). The v'G operator approximates a band-pass filter with a bandwidth at half power of 1.25 octaves [32], and is intimately related to the DOG profile measured in biological experiments. The shape of the DOG pattern becomes identical to that of V2G when the spatial scales of the two Gaussian profiles are close, as they are in the biological case. Marr & Hildreth have shown [30]: (a) v2G is the limit of the DOG function as', the ratio of the inhibitory to excitatory space constant, tends to unity; and Behavior 15

RSD-TR-2-87 (b) that if an approximation to v2G is to be constructed out of the difference of two Gaussian distributions, one excitatory and the other inhibitory, then the optimal choice on engineering grounds for -.' is about 1.6. 2.3. Multiresolution Problem and Scale Space The importance of the idea of multiresolution problem has been realized and has drawn a lot of attention in the computer vision area. Rosenfeld was among the first in the computer vision field to explicitly propose an edge detection scheme based on multiscale analysis performed with filters of different sizes. Rosenfeld believed that the relative orientation of the neighborhoods determines the direction of the edges that will be detected, and the size of the neighborhoods determines the width of the edges that will be detected. To detect microedges, small neighborhoods must be used, but detecting edges between textured regions requires neighborhoods large enough for gross averaging over the detail in the textures. Thus he suggested that a complete edge detection system should employ, at each point, pairs of neighborhoods of various sizes and at various orientations; the largest of these should have the size comparable to that of the entire picture. Edge detectors of various sizes and orientations were obtained by shifting and pointwise subtracting blurred versions of a picture from themselves. He demonstrated using a class of edge detectors of various sizes to detect texture edges, such as "spots", and "streaks" in digitized pictures. He has shown that, by comparing the outputs of the operations corresponding to edges of different sizes, Beharrvior 18

RSD-TR-2-87 one can construct a composite output in which edges between differently textured regions are detected and isolated objects are also detected, but the objects composing the textures are ignored. From the study of the vision system, Marr suggested the multiscale idea in 1976 [31]. Along with the L-G operator, Marr has strongly advocated the use of different sizes of the operator with the goal of detecting changes in intensity at different scales [32]. Later, Marr and Hildreth [30] proposed some heuristic rules to combine information from different channels. Marr's idea of using the multiscale of the L-G operator has drawn a lot of research attention. But how to combine the results at different scale is a very difficult problem. People have used the multiresolution of the L-G operator to solve various problems, and tried various methods to deal with the problem of integrating information from different channels [14, 25, 4, 30, 27, 15, 16, 28, 29, 50, 24, 48, 53]. Canny's approach to edge detection as we discussed above also involves the idea of multiple scales of operators. As indicated earlier, there are no principles for selecting scales for an input image. Thus people explored other ways of describing signals. A new method of describing zero-crossings across scale was suggested by Witkin [511. Witkin's scale space description is for the 1-D signal. The 1-D signal is smoothed with the Gaussian distribution, F(x,o) = G*I. Behavior 17

RSD-TR-2-87 The standard deviation, a, and the location of signal, x, form the scale space, x-o plane; F is called the scale space image. For any x, such that 2F( ) __ 0, 02: x is called a zero crossing. When a increases, the locations of the zero-crossings form the zero-crossing contours in the x-a plane. The zero-crossing contours in the 2-D scale space have some nice features which enable Witkin to classify and label zero-crossings thereby achieving an effective description of a signal for purpose of recognition and registration. After Witkin's scale space description, Yuille and Poggio, Babaud & et al., and Shah have achieved further results on 2-D scale space. Asada & Brady, Mkhtarian & Mackworth have applied the scale space theory on the problem of recognition of planar curves and two dimensional curves [52, 2, 47, 34, 11. Based on these people's work, we summarize all the property of 2-D scale space and 3-D scale space as follows. 2.3.1 The Property of the 2-D Scale Space When z is one dimension, the scale space is a two dimensional plane (X,a), the zero-crossings in E(x,o)=f(x)*v2G(x,a) form the zerocrossings contours in the (x,o) plane. A typical scaling behavior of zero-crossings in the two dimensional scale space observed by Witkin is shown in Fig. 2. Babaud et a421 and Yuille & Poggio [521 have independently obtained the following striking result: In the one dimension signal, I the filter is Gaussian, when a increases, the zero-crossings are never created. Behavior 18

RSD-TR-2-87 They have further proved that in the one dimension signal, with the second derivative, Gaussian is the only filter which never creates zero-crossing when o increases. It means when a increases, zero-crossings may dissappear but can never be created. This property of the Gaussian is important for two reasons: (1) it allows coarse-to-fine tracking of zero-crossings in scale space, such as Witkin did by using a tree structure [51]. (2) it ensures that the scale space diagram contains, in some sense, a minimal number of zero-crossings (for o = 0, the number of zero-crossing is determined by the signal). From empirical observation, Yuille & Poggio [52] said that the generic zero-crossings generated by the Gaussian filter will never behave like the contours shown in Fig. 3. They also claimed that "true" zerocrossings can only disappear in pairs in the x-o plane. Only trivial zeros that do not cross zero can disappear by themselves, and these are not considered as true zero-crossings. Shah [471 studied of the behavior of the zero-crossing contours of step edge, pulse edge and staircase edge models in the 1-D signal and achieved some interesting results. Let U(x) 0 if z <0 Uc)=' if:z>0' The step edge function is defined as: f(x) =cU(x); then E(x,a)=f(x)*v2G = -c( )exp[- 2] Behavior 19

RSD-TR-2-87 The zero-crossing contour of the step edge is a straight line, it is illustrated in Fig. 4. The pulse edge model is defined as: f(x) = U(x-wl) - pU(x-w2) E(x,a) =f(x)*2G =- (z- 1) exp[- (z-w 1)2 + (z-) ex- - 2)2 by plotting the (x,o) points which satisfies E(x,o) = 0, the zero-crossing contours of the pulse edge in the scale space are illustrated in Fig. 5. The staircase edge model is defired as f(x) = U(x-wl) + pU(x-w2) F(x,o) = f(x)*v2G(x,a)=(zw 1) exp[l- (z 1) p (zw2)exp[- (Z2)2 a 2o2.2 2o2 The zero-crossing contours for p=1 and 2 plotted from the above function by Shah are shown in Fig. 6 and Fig. 7. 2.3.2 The 3-D Scale Space When I has two dimensions, x =(x,y), then the scale space is three dimensions. The behavior of the zero (or level) crossings is much more complicated than in the two dimensional scale space. Yuille & Poggio [52] proved the following important theorem for the three dimensional scale space: Behavior 20

RSD-TR-287 In the two dimensional signal case, If the frilter Its LG, zero-crossings are never created when a increases. And with the Laplacian operator, Gaussian is the only filter having this property. They proved the property by showing that the zero-crossing surface in the three dimensional scale space doesn't have a minima, i.e. the extrema of these zero-crossings are either maxima or saddle points. Even though the zero-crossings can never be created when o increases, the zero-crossing surface in the three dimensional scale space are free to split and merge, and the regions bounded by zero-crossings surfaces are free to split and merge, so that the number of zero-crossing surfaces is not monotonic with a. Thus it is very hard to describe their behavior. Behavior 21

RSD-TR-2-87 3. Deflnitions An edge curve is called D-isolated, if for any point on the curve, we can draw a disc centered at that point with radius D, and that disc will intersect no edges except those on this edge curve. When D — > oo, the image does not have an?=other edges except those on this edge curve. In this situation, we simply call it an isolated edge curve. n edge curves are D-Isolated n edge curves, if for every point on any one of the curves, we can draw a disc centered at that edge point with radius D, and that disc will intersect no edges except those on these n edge curves. An edge curve C(x,y) = O is shape invariant under a if its corresponding zero crossing curve from channel a, C,(u,v)=O, can be obtained from C(x,y)=O through rotation or translation of the axes. C(x,y)=O is shape invariant if C(u,v) is shape invariant under all os. A linear edge curve is tangent Invariant under a if its corresponding zero crossing curve from channel a is linear and has the same tangent value as the edge line. If a linear edge curve is tangent invariant under all as, it is tangent invariant. Behavior 22

RSD-TR-2-87 If a line function is y=ax+b, its location is, if the line function is x=c, its location is c. If an edge line has the same location as its corresponding zero crossing line from channel a, then the edge line is locational invariant under a. An edge line is locational invariant if it is locational invariant under all (s5. Let CI(x,y) = 0 and C2(x,y) = 0 be two edge curves. Then the distance between two edge curves is: dist = min { distance between (xl,yl) and (x2,y2) I Cl(xl,yl) = O and C2(x2,y2) = O }. We will use the following two symbols in this report: g(x,y) exp[- 2+ Y21 G(x,y) = v2g(x,y)= 2 +:+ Y )exp + Behavior 23

RSD-TR-2-87 4. The Scaling Properties of Edge Curves In computer vision, edge curves in a digital image are one of the most important features. A quantitative study on the scaling behavior of edge curves under the L-G operator is very important, and the results are the basis for reasoning in scale space. The two dimensional L-G operator is rotationally symmetric. The shape of the operator is shown in Fig. 8. The operator is a disk with radius, R-> +oo. The small bright disk in the center indicates the positive values in the operator, and the negative values form a wreath around the disk. The scale parameter, a, determines the size of the positive disk. The sum of the values on the operator disk is 0. An important property of the Gaussian function is that the weight at a point decreases monotonically with the distance from the central point. When the radius R is large enough, the wreath outside of the operator disk becomes very insignificant. R is the size of the operator and is determined by o. An edge curve under different sizes of the L-G operator can behave differently. Different edge curves behave differently under the same size of the operator. If there is only one edge curve within the operator disk, then only the edges on that curve can influence each other. Once there are more than one edge curves within the operator disk, the edge curves will affect each other. The results of our study on the behavior of the edge curves are presented in one lemma, three theorems and a number of corollaries. The lemma, the theorems and corollaries imply the following facts: Behavior 24

RSD-TR-2-87 1. A D-isolated edge curve has a corresponding zero crossing curve from the L-G operator with size a, such that a < L(D), where L(D) is a monotonically increasing function of D, and its existence is proved in the Lemma 1. An isolated edge curve has a corresponding zero crossing curve from every size of the LG operator. 2. A 1-isolated edge line is tangent and locational invariant in all channels a, such that a < T(D), where T(D) is a monotonically increasing function of D, and its existence is proved in Theorem 1. An isolated edge line is tangent and location invariant in all channels. 3. The dislocation of an edge line occurs only when there are more than one edge lines in the small neighborhood. 4. When two edge lines are pulse edge model, two corresponding zero crossing lines exist beyond the region bounded by the two edge lines. When r increases, the distance between the two zero crossing lines increases. 5. When two edge lines are staircase edge model, the corresponding zero crossing lines can only possibly exist within the region bounded by the two edge lines. 6. When two edge lines are staircase edge model at some small channels, we have a false zero crossing line. 7. When the two edge lines are staircase edge model at some large channels, we have only one zero crossing line. Behavior 25

RSD-TR-287 8. Zero crossing lines disappear in pairs. In the following sections, we present the theorems and corollaries along with the mathematical proofs. 4.1 D-isolated edge curve In our efforts to understand the behavior of edges, we consider D-isolated linear edge curves. Our aim is to identify conditions under which a linear edge in an image will give rise to zero crossing, and to determine when neighboring edges will start to influence the location of zero crossings. Lemma 1. For a D-isolated edge curve, there exists a function L(D), such that for every a < L(D), there is a corresponding zero crossing curve in channel a, where L is a monotonically increasing function with variable D. The proof is given in Appendix A. Theorem 1. For a D-isolated linear edge curve, there exists a monotonically increasing function, T1(D), such that for all a < T1(D), the linear edge curve is tangent and locational invariant under a. The function T1(D) is given by, T1(D) = D Behavior 26

RSD-TR-2487 where H is an upper bound constant of the gray level function, e is a positive real number in the range O<e<4Hv' and e approximates zero. In computer vision applications, H < 255, choosing e_0.048, T1 can be further simplified to T1(D) D The proof is given in Appendix B. 4.2 Pulse edges. It is common to find an object against a background. In such cases, the edges can be considered to be of pulse edge type [48]. Theorem 2 is concerned with the behavior of pulse edges. We also present four corollaries related to behavior of pulse edges in scale space. Theorem 2. For D-isolated two parallel edge lines that can be considered pulse lines (i.e. for 11 and 12, let gl indicate the gray level of the region next to 11, g3 indicate the gray level of the region next to 12 and g2 indicate the gray level of the region between them, such that either g2 > gl and g2 > g3, or g2 < gl and g2 < g3) then there exists a monotonically increasing function, T2(D), such that when a < T2(D), 1. we have two corresponding zero crossing lines for every a, and no other zero crossings are generated. 2. Each of the zero crossing lines has the property of tangent invariance. Behavior 27

RSD-TR-2-87 The function T2(D) is: T2(D)- min { } where H is an upper bound constant of the gray level function, W is the distance where H is an upper bound constant of the gray level function, W is the distance between the two edge lines and e is a small positive number in the range O<e<0.1, which approximates zero. In computer vision applications, H<255, choosing e=0.048, we can get D W T2(D)= min {,- } The proof is given in Appendix C. The following corollaries are true under the same conditions as theorem 2, and all the symbols used in the following corollaries have the same meaning as stated in theorem 2. Corollary 2.1 There are no zero crossings in the region B2 < y < B1. For every a value, the corresponding zero crossing lines, y=B01, y=Bo, are located as: y=B01 > B1, y=Bo2 B2. Proof. This is well indicated in Part 1 of Appendix C. Corollary 2.2 When a increases, the distance between the two zero crossing lines, y=B0, y=B02, increases, i.e. distance = Bol-Bo increases. Proof. In the proof of theorem 2, we indicated that Behavior 28

RSD-TR-2-87 I*G(x,y) < 0, when B2 < y < B1; I*G(x,y) > 0, when y = B1+a; I*G(x,y) > 0, when y - B2-a; When a increases, the two positive regions of M(x,y) shift away from y=B1 and y=B2. Hence, the zero crossing lines y=BO and y=B, are moving away from each other, consequently the distance between the two zero crossing lines increases. Corollary 2.3 In pulse edge situation, when g3=gl, i.e. g2-g3=g2-gl, then at each o value, the two zero crossing lines have the same amount of dislocation value, i.e. B2 - B02= Bo, - BI. Proof. Following (l.b.l) of the proof of theorem 2, at BI < y < B1 + a, v2(I*g) = I*vg) = I(x,y)*G(x,y) M(x,y) + E2; at B2 - a < y < B2, vxI*g) = I*v2(g) = I(x,y)*G(x,y) M(x,y) + El; where M(x,y) = (g3-g2) (Y-B2)'~ exp[- (y -B22) + (g2-gl) (YB 1)v. exp[- (Y -B 1) o, 20.2 2a2 2 El(x,y)= -g3 /('y-B 2+D) expl- (vY-B 2+D )2l Behavior 29

RSD-TR-2-87 E2(x,y) - gl (-B1-D ) exp[(V-B -D )2 U 2a2 Let g2-g3=g2-gl=G, d=Bo, - BI, and we know I*G(x,Bo,); M(x, Bo0) + E2 = (g3-g2) ( 2 e xp[- 2 (B (g2-2) (B - B 1) (Bo-B 1)2 1 (B0ol-B 1-D ) e (Bo -B 1-D +( gl) )] exp[- Jrgl eP[-...........2 ]+1... - (Bo01B 2)v/' m (B01or-B 2)2 d d2d-D_ )[ =-G exp|-( ~2 2)2 1 + G exp — I + gl exp(d-D)21 =. 202 We want to show y=B2-d is a zero crossing line too, i.e. I*G(x,B2-d) = 0. I*G(x,B2-d) z M(x,B2-d) + El(x,B2-d) = (g3-g2) -d exp- + (g2-gl) (B2-d-B 1)V2/ exp[-(B2-d-B 1)2 g3 Vi(B 2-d-B 2+D ) exp[- (B 2-d-B 2+D )2 202 a 2a2 d,f2-x d (Bol-B 2)vr27 (B 2-Bo): _ _ v(d -D ) [G d expl — I - G (B... exp[ (B2 B1) + gl expl(d -D )2 = M(x,Bol) = 0. So y=B2-d is a zero crossing line too. By theorem 2, we know there are only two zero crossing lines in the. region B2-o < y < Bl+a, so we have B50 = B2-d. Thus the two zero crossing lines have the same dislocation value, d. Behavior 30

RSD-TR-287 Corollary 2.4 In the scale space image of the two pulse edge curves, when g3=gl, the zero crossings form two symmetric contours(surfaces). Proof. This is a direct conclusion from corollary 2.3. 4.3 Staircase edges. A ramp edge usually becomes a staircase in discrete space. Since in many real images, it is common to find ramp edges, we study the behavior of staircase intensity functions. This section presents one theorem and some corollaries related to staircase intensity functions. Theorem 3. For )-isolated two parallel edge lines that can be considered staircase lines (i.e. for 11 and 12, let gl indicate the gray level of the region next to 11, g3 indicate the gray level of the region next to 12 and g2 indicate the gray level of the region between 11 and 12 such that either g3>g2>gl or g3<g2<gl), there exists a monotonically increasing function T3(D), such that when a < T3(D), we have the following results: 1. when a is very small in comparison with W, the distance between 11 and 12, then we have two zero crossing lines, each of them is tangent and locational invariant to its corresponding edge line; 2. when a increases, such that it is no longer small in comparison with W, we have three parallel zero crossing lines. Behavior 31

RSD-TR-2-87 3. when a is large, two of the three zero crossing lines will disappear together, and the third one will remain in all channels. The function T3(D) is: T3(D) D where H is an upper bound constant of the gray level function and e is a small positive real number which approximates zero. In computer vision applications, H<255, if we choose e=0.048, T3(D) = D The proof is given in Appendix D. The following corollaries are true under the same condition as in theorem 3. The symbols used in the following corollaries, have the same definition as stated in theorem 3. Corollary 3.1. For two isolated staircase edge lines, there are no zero crossings in the regions: y>B1 or y<B2, in any channel. Proof. This has been proved in (5.3) of the proof of theorem 3. Corollary 3.2. For two )-isolated staircase edge lines, if jg3-g21 = Ig2-gll, when a is not too small in comparison with W (a should be at least greater than W., then Behavior 32

RSD-TR-2-87 (1) y BI+B2 is a zero crossing line for every a, a < T3(D); (2) y=Bo,, and y=BO, are two zero crossing lines, where B2 < B, < B1+B2 < B0, < Bi; when a becomes large, they will disappear together. Proof. These results are shown in the part 2 and part 3 of the proof of theorem 3. Corollary 3.3. For two D-isolated staircase edge lines, when {g3-g2j > {g2-gll, for every a, a<T3(D) and 7 is not too small in comparison with W (a should be at least greater than, then 2 /31 2 (1) there is a zero crossing line y=Bo, where B2 < Bo < BI+B2 for every a, (2) we have two more zero crossing lines, y=BO3, y=B01 where B 1+B2 < B < Bo, < Bi; when a increases to a large value, the two will disappear together. When Ig3-g21 < Ig2-gll, we have the symmetric facts: (3) there is a zero crossing line y=B01, where B 1+B2 < B0o < B1, for every a, 2 (4) we have two more zero crossing lines, y=BO3, Y=Bo where B2 < Bo < Bos BI+B2 < 22; when a increases to a large value, the two will disappear together. Proof. Behavior 33

RSD-TR-2-87 We only need to prove (1) and (2), and without losing generality, we assume g3g2 > g2-gl. As we have shown in the proof of theorem 3, for B2<y<Bl, I*G(x,y) = M(x,y). B 12-B ( 2 ) -B2 B 2-B 1); B )B2B 2 ):____ )2 + M(xB +B 2 (g3-g2) exp[- 2 + (g2-gl) M(x,2 2o2 B 2-B1 )2 exp[- 2 > 0 and for all B'<B2, M(x,B') = (g3-g2)( -B 2) ex ( -B 2)2] + (g2-gl) (B -B 1) exp[a 2a2 (B -B1)1 < 0, 202 so there exists a zero crossing line y=Bo, where B2 < B < B1 B2 This zero crossing line is independent of a, i.e. y=B0 exists at all channels. From the proof of theorem 3, when a is relatively small, we have three zero crossing lines, so there are two more zero crossing lines in the region, B1+B2 < 2 y < BI. When a is large, there is only one zero crossing line, so these two zero crossing lines in B 1+B 2 < y < B, will disappear together eventually. 2 Behavior 34

RSD-TR-2-87 Corollary 3.4. For the two staircase edge lines, when o is increasing, the distance between B02 and Bo0 is decreasing, and if there is a zero crossing line, y=B03, in the middle, B0 will move towards Boll if 1g3-g2j > 1g2-gll; towards B02 if {g3-g21 < Ig2-gll. Eventually, Bo3 disappears with the closer one. Proof. (1) At g3-g2=g2-gl. From (3.1) of the proof of the theorem 3, we know B2 < B02 < B2 + a; B 1 - a < Bo, < B 1. When a increases, the distance between y=B01 and y=Bo2, is decreasing, where the distance = B1-B2 - 2o (2) At g3-g2 > g2-gl >O. (In the case, gl>g2>g3, and (gl-g2) > (g2-g3) >0, has the same proof method.) We have shown in (3.2) the proof of theorem 3, there is a zero crossing line y=B02 such that B2 < B02 < 2 Further, we have M(x, B2+o) > 0 and M(x,B2) < 0, so B2 < Bo2 < B2 + a. We have also shown that the zero crossing lines, y=Bo, and y=B03, lie in the region, BI - a < Bo, < B1. When o increases, B0, moves more and more towards y=Bo2, so the distance between these two zero crossing lines decreases, and the distance between y=B03 and y=B,0 decreases too. We have also shown in the proof of theorem 3 that y=Bo, disappears with Bo,. For the case that g3-g2<g2-gl, from (3.3) of the proof of theorem 3, we can get the same result. Behavior 35

RSD-TR-2 87 4.4. Theorems and experiments The lemma indicates the existence of a corresponding zero crossing curve for an isolated edge curve. In the proof of the lemma, we indicated the existence of the upper bound function L(D), and showed that it is a monotonically increasing function of D. According to this lemma, a very fine isolated edge curve has its corresponding zero crossing curve in every channel. Fig. 9 is such an example. Theorem 1 ensures that the linear edge curve is tangent and locational invariant. The condition'linear" is not only sufficient but necessary. Only the linear edge curves have these strong features under the L-G operator. When the edge curve is non-linear, the positions of some individual zero crossing points may not be the same as the corresponding edge points. The positions of some individual zero crossings change with the a value. Thus the shape of the entire curve changes shape as seen in Fig. 10. Fig. 10 shows an example of non-linear edge curve. As a increases, the shape and the size of the sine curve is obviously changing. The upper bound function in theorem 1, T1(D), can also be used to measure the influence of the edge curves. Let D be the distance of two edge lines, when a < -, the two corresponding zero crossing lines from channel a should not be effected by each other. D- is a least upper bound functions. Our experiments show that in some situations, the upper bound function could be _. Reader may want to refer to all the experimental results shown in this report and the paper Behavior 36

RSD-TR-2-87 by M. Piech [36]. Theorem 2 and theorem 3 refer to more than one edge line situation. The two theorems have shown that two parallel linear edge curves, if they have corresponding zero crossing curves, the zero crossing curves are also linear and have the same tangent value. In the pulse edge model, the two zero crossing lines will never disappear, because the zero crossing lines, y=Bo and y=B, exist in the region, BI<Bo,<Bl+a, B2-a<Bo2<B2. But the locations of the zero crossing lines are different when a changes. As we have shown in corollary 2.2, when a increases, dislocation value of the zero crossing line increases too. It brings up the dislocation problem. The dislocation problem occurs when there is more than one edge curve within the neighborhood. The condition in theorem 3 is different from theorem 2 in one aspect, namely, the gray levels form a staircase. This gray level condition causes the false zero crossing line at the smaller value of a and one real zero crossing curve missing at the larger scale. Therefore, we call this gray level condition as the false edge condition or missing edge condition. When a is very small in comparison with W, in fact we have shown that when a<, we have two zero crossing lines, y=B01 and y=BO, where Bo-=B2 and B0,=Bl. It means the zero crossing lines have the same location as the edge lines. When a is not too small, we have shown that we have three zero crossing lines, but we have only two edge curves in the original picture. The question is which one is false? If we register the edge line with the zero crossing line with minimum dislocation, Behavior 37

RSD-TR-2-87 then the one in the middle, i.e. y=B3, where B, < Boa < Bo,, is the false zero crossing line. Corollary 3.2 indicates that it is not necessary that the false one will disappear with a real one. When jg3-g2| = jg2-gl1, y = B1+B2 is always a zero crossing line for every a when it is not too small. This zero crossing line is a false one according to the above definition, it exists in all channels and never disappears. We have performed some experiments on various images. They are shown in Fig. 11 - Fig. 19. Since the input images contain the vertical edge lines in Fig. 13, Fig. 14, Fig. 16, Fig. 17, Fig. 18 and Fig. 10, we generated the zero crossing contours in a two dimensional scale space image in each case to assist the study. The horizontal dimension indicates the vertical position of the edge (zero crossing) line, i.e the x direction; the vertical dimension indicates the scale a. Fig. 13 and Fig. 15 verify Corollary 2.3 and 2.4. In the input image of Fig. 15, gl=g3=100, we see that the two zero crossing lines move away evenly. In the input image of Fig. 13, gl=g3=255, the zero crossing contours in the scale space image are two symmetric lines. If jg2 - g31 < jg2 - gl1, the zero crossing line between g2 and g3 moves away faster than the one between g2 and gl, and vice versa. For example in Fig. 14, i g3 - g2 I < I gl - g3 1, the zero crossing line, corresponding to e2, shifts further away from its actual position. From Fig. 13 - Fig. 15, we can see that there are no zero crossings between the two original edge lines, and the distance between two zero crossing lines increases when _ increases, so they have verified theorem 2, corollary 2.1 and corollary 2.2. Behavior 38

RSD-TR-2-87 Some of the experimental results for the staircase edge model are shown in Fig. 17, 18, 19. Fig. 17, Fig. 18 and Fig. 19 have verified Theorem 3 and Corollary 3.1 - 3.4. Especially in regards to Corollary 3.4, the results indicate that the false zero crossing curve always disappears with the real that has the smaller difference of gray levels on both sides. In Fig. 17, j g3 - g2 I < I g2 - gl 1, the false zero crossing curve disappeared with z2; in Fig. 18, 1 g2 - gl I < I g3 - g2 I, the false zero crossing curve disappeared with zl. Fig. 19 verifies that the false zero crossing line, y B l 2 exists for all o provided that a>2. All these experimental results have supported theorem 3 and its corollaries. Behavior 39

RSD-TR-2-87 S. Properties of Regions In Scale Space By applying the above theorems and corollaries to the more general situation, we come to the assertions listed below. A qualitative verification is presented for each assertion. These assertions are also supported by experimental results. Assertion 1. For a non-linear isolated edge curve, its corresponding zero crossing curve may change shape. For an isolated closed edge curve, the region which is surrounded by the corresponding zero crossing curve expands as a increases. When the edge curve is non-linear, the edges on the same curve may effect each other. The points which may change the locations are those on the sides of a ridge or a valley on the curve. The gray level condition on both sides of the curve must follow those in the theorem 2. From theorem 2, the points on each side of a ridge or valley repel each other. If we write the curve as y=f(x), the points are dislocated along the x axis. Thus, sharp parts of a curve will become smoother when a increases. So the shape of the zero crossing curve may change when a changes. The sine curve in Fig. 10 is a good example. When the edge curve is closed(see Fig. 20), the gray level condition along the edge curve must conform to theorem 2. From theorem 2, the edge points on the opposite side of the curve repel each other. Consequently the area surrounded by the zero crossing curve is expanding when u increases. Furthermore, the gray level condition on each side of the curve satisfies Corolary 2.3, hence, the expanBehavior 40

RSD-TR-2-87 sion of the region is even at each side. In addition to Fig. 9, Fig. 21 and Fig. 22 are good examples of this phenomena. Assertion 2. For two closed edge curves, let gl, g2 and g3 be the gray levels distributed as in Fig. 23; if g2, gl and g3 satisfy the pulse edge condition, i.e. gl>g2 and gl > g3 or gl<g2 and gl<g3, then the two corresponding closed zero crossing curves will eventually merge into one closed zero crossing curve when a is large enough. When g2, gi and g3 follow the pulse edge model, i.e. gl > g2 and gl > g3, then from Assertion 1, we know that each of the closed zero crossing curves is expanding as o increases. When o is large enough, they will eventually meet together and merge into one large closed curve. In Fig. 24, there are two regions nearby, and, when o>6, the two closed zero crossing curves merge into one bigger closed zero crossing curve. Assertion 3. If a region R contains one subregion, let gl, g2 and g3 be the gray levels within the regions(see Fig. 18), and if gl, g2 and g3 follow the staircase edge model, i.e. gl<g2<g3 (or g1>g2>g3), then we will have a false closed zero crossing curve in between the two real ones at the smaller a. The false zero crossing curve is also a closed one and it will merge and disappear with one of the real zero crossing curves when a becomes large. If jgl-g2j < Ig2-g3[, then el will disappear with the false one; if jgl-g21 > 1g2-g31, then e2 will disappear with the false one. Behavior 41

RSD-TR-2-87 From theorem 3, we know we will get the false zero crossing curve in between the two real edge curves. When ao changes, the zero crossing curves go through the following sequence. When a is very small in comparison with the distance between el and e2, then the two zero crossing curves are the same as el and e2; when a increases, a false zero crossing curve appears and the two real zero crossing curves are all attracted to the false one, i.e they all move towards it. When a increases to a large value, the false zero crossing curve merges with one of the true zero crossing curves. They may split into several closed curves, then eventually disappear together. The remaining closed zero crossing curve then starts to expand in accordance with Assertion 1. Fig. 26 shows such an example. Assertion 4. If a region has an abrupt change in its width, then when a increases its value, the closed zero crossing curve will split into two smaller closed curves. If a keeps increasing, the two regions surrounded by the two new closed curves will expand, eventually they will merge back to a big closed curve again. The split point occurs at the abrupt narrowing area. The two new smaller regions will follow the expanding, merging and expanding procedure. Such examples are shown in Fig. 27 and Fig. 28. In Fig. 27, the picture process has completed the split-expand-merge-expand procedure. In Fig. 28, the process has gone through split-expand. If we keep applying larger a values, it will complete the remaining procedure, culminating in merge-expand. Behavior 42

RSD-TR-2.87 The above theorem and assertions are generated for ideal images. The natural image has much more complicated gray level changes. But, in general, the zero crossing curves generated from the natural image will always behave in one of the above manner, or a sequence thereof. Behavior 43

RSD-TR-2-87 8. Discussion The most significant phenomena observed from the different channels of the 1,G operator are false edge curves, missing edge curves and edge dislocation. These problems are caused by the influence of edges. The theorems given in this report answered these problems. Another important proof is that for any isolated edge curve, we will get corresponding zero crossing curves in all channels. This applies even when the edge curve is very fine and the scale is very large. In addition, the theorems along with the corollaries give a good description of the behavior of the zero crossings under various conditions. Most of the theorems and the corollaries are proved for linear edge curves. But the results can be extended to the general curve and region situations. The four assertions were generated in this way. The assertions gave a good description on the behavior of the regions bounded by the zero crossing curves. These theorems, corollaries and assertions are supported by many experimental results. The theorems, corollaries and assertions are generated in the ideal step edge, pulse edge and staircase edge models. In the real world image, the behavior of the zero crossings are much more complicated. But they usually follow the processes discussed in section 5. For reasoning in scale space, we can follow the approach introduced by Waltz [49]. Based on the theorems, corollaries, and assertions, we can construct a knowledge base. This knowledge base will contain rules based on the behavior of zero crossings in scale space for simple cases. The complex unpredictable interactions of these simple cases is what makes real images so difficult to analyze. By applying the rules from the knowledge base, it may be possible to better analyze Beharrvior 44

RSD-TR-2-87 the behavior of edges in real images and detect presence of desired features. A simple example may help understand the feasibility of this approach. In Fig. 29, we show an image containing a noisy square on a noisy background. The zero crossings for this image are shown at different scales in the image. If we are interested in detecting the square, the edge image at lower scales has proper shape but with too many noisy edges. On higher scales, noise is reduced but shape is distorted. A reasoning process may allow to focus on the closed contour on higher scales and then track zero crossings corresponding to the closed contour to lower scales to find the proper shape. Even for complex images such an approach seems promising. 7. Acknowledgement We are thankful to Nancy Byrd, Lawrence Maloney, Brian Schunck, Richard Volz and Terry Weymouth for their help in improving this report. Behavior 45

RSD-TR-2-87 REFERENCE [1] Haruo Asada and Michael Brady, "The Curvature Primal Sketch," IEEE Trans. on PAMI, vol. PAMI-8, No.l, Jan. 1986. [2] J. Babaud, A. P. Witkin, M. Baudin and R. 0. Duda, "Uniqueness of the Gaussian Kernel for Scale-Space Filtering," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. PAMI-8, No.l, p. 26- 33, Jan. 1986. [3] P.A Blitcher, "Edge Detection and Geometric Methods in Computer Vision," Ph.D thesis, Department of Computer Science, Stanford University, 1985. [4] R.C. Bolles, P. Horaud and M.J. Hannah, "3DPO: A Three-Dimensional Part Orientation System," Proc. 8th IJCAI, vol. 2, pp. 1116-1120, Aug. 1983. (5] M. Brady, "Changing shape of computing vision," Artifitial Intelligence, vol. 17, pp. 1-15, Aug. 1981. [6] M. Brady, J. Ponce, A. Yuille and H. Asada, "Describing Surfaces," Computer Vision, Graphics and Image Processing, vol. 32, pp. 1-28, Oct. 1985. [71 M.J. Brooks, "Rationalizing edge detectors," Computer Graphics and Image Processing, vol. 8, pp. 277-285, 1978. [8] J.B. Burns, A.R. Hanson and E.M. Riseman, "Extracting straight lines," IEEE Trans. on PAMI, pp. 425-455, July, 1985. [91 J. F. Canny,''A variational approach to edge detection," AAAI Conf., pp. 54-57, Selpt., 1983. [10] John F. Canny, "Finding Edges and Lines in Images," Technical Report, AI-TR-720, June, 1983. Behavior 46

RSD..TR-2-87 [11] Compbell, F.W. and Robson, J.G., "Visual Adaptation to Patterns Containing two dimensional spatial structure," Vision Research, vol. 18, p. 93' 99, 1968. [12] Larry S. Davis, "A survey of Edge Detection Techniques," Computer Graphics and Image Processing, vol. 4, pp. 248-270, 1975. [13] Arthur P. Dempster, "A Generalization of Bayesian Inference," Journal of the Royal Statistical Society, vol. Series B, Vol. 30, pp. 205-247, 1968. [141 J-O Eklundh, T. Elfving and S. Nyberg, "Edge Detection using the Marr-Hildreth Operator with Different Sizes," IEEE International Conference on Pattern Recognition, vol. 2, 1982. [15] J. Glicksman, "A Cooperative Scheme for Image Understanding Using Multiple Sources of Information," Tech. Rep. TN 83-13, Nov. 1982. [16] J. Glicksman, "Using Multiple Information Sources in a Computational Vision System," Proc. 8th IJCAI, vol. 2, pp. 1078-1080, Aug. 1983. [171 W.E.L. Grimson and E.C. Hildreth, "Comments on'Digital Step Edges from Zero Crossings of Second Directional Derivatives'," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. PAMI-7, No.1, pp. 121129, January, 1985. [18] R. Haralick, "Edge and Region Analysis-for Digital Image Data," Computer Graphics Image Processing, vol. 12; pp. 60-73, 1980. [19] R. Haralick, "Digital Step Edges from Zero Crossing of Second Directional Derivatives," IEEE Trans. PAMI,, vol. PAMI-6, pp. 58-68, Jan. 1984. [20] R. Haralick and L. Watson, "A facet model for image data," computer Graphics and Image Processing, vol. 15, pp. 113-129, 1981. [211 Hildreth, E., "Edge Detection in Man and Machine," Robotics Age, p. 8- 14, Sept/Oct. 1981. [22] Ellen C. Hildreth, "The Detection of Intensity Changes by Computer and Biological Vision Systems," Computer Vision, Graphics and Image Processing, vol. 22, pp. 1-27, 1983. Behavior 47

RSD-TR-2-87 [23] M. Hueckel, "A Local Visual Operator Which Recognizes Edges and Lines," J. ACM, vol. 20, pp. 634-647, Oct. 1973. [24] Robert A. Hummel, "Representation Based on Zero-crossings in Scale Space," IEEE Computer Society Conference on Computer Vision and Pattern Recognition, June, 1986. [25] A.C. Kak, "Depth Perception for Robots," Tech. Report, TR-EE 83-44, Oct. 1883. [261 S.W. Kuffer, "Discharge Patterns and Functional Organization of the Mmmalian Retina," J. Neurophyical, vol. 16, pp. 37-68, 1965. [27] P.D. Lawrence and J.J. Clark, "Hierarchical Image Analysis System Based upon Oriented Zero Crossings os Band Passed Images," Multiresolution Image Analysis and Processing, 1983, A. Rosenfeld, Ed.. [28] D.T. Lawton, "Processing Translational Motion Sequences," Computer Vision, Graphics and Image Processing, vol. 22, pp. 116-144, 1983. [29] M.S. Majka, "Reasoning about Spatial Relationships in the Primal Sketch," M.S. Thesis, Sept., 1982. [30] D. Marr and E. Hildreth, "Theory of Edge Detection," Proc. Royal Society of London, vol. B207, pp. 187-217, 1980. [311 David Marr, "Early Processing of Visual Information," Trans. Royal Society, vol. 275, pp. 483-519, 1976. [32] David Marr, Vision. New York: W.H. Freeman and Company, 1982. [33] J. Modestino and R. Fries, "Edge Detection in Noisy Images using Recursive Digital Filtering," Computer Graphics and Image Processing vol. 6, pp. 409-433, 1977. [34] Farzin Mokhtarian and Alan Mackworth, "Scale-Based Description and Recognition of Planar Curves and Two-Dimensional Shapes," IEEE Trans. on PAMI, vol. PAMI-8, No.l, Jan. 1986. Behavior 48

RSD-TR-2-87 [351 Tamar Peli and D. Malah, "A Study of Edge Detection Algorithms," Computer Graphics and Image Processing, vol. 20, pp. 1-21, 1982. [36] M. Ann Piech, "Comments on Fingerprints of Two Dimensional Edge Models," Submitted for publication, 1986. [37] William K. Pratt, Digital Image Processing. John Willy & Sons, 1978. [38] J. Prewitt, "Object enhancement and extraction," Picture Processing and Psychopictorics, New York: Academic, pp. 75-149, 1970. [39] W. Richards, H. K. Nishihara and B. Dawson, "Cartoon: A biologically motivated edge detection algorithm," M.I. T. Artif. Intell. Lab. Memo.688, 1982. [40] L. Roberts, "Machine Perception of 3-dimensional Solids," Optical and Electro-Opt. Inf. Processing J., pp. 159-197, 1965. [41] R.W. Rodieck and J. Stone, "Analysis of Receptive Fields of Cat Retinal Ganglion Cells," J. ANeurophysiol, vol. 28, pp. 833-849, 1965, One of the earliest studies to describe the shape of the receptive fields of retinal cells. [42] Azriel Rosenfeld, "Picture Processing:1983," Computer Vision, Graphics and Image Processing, vol. 26, pp. 347-393, June, 1984. [43] A. Rosenfeld and Avinash C. Kak, Digital Picture Processing. Academic Press, 1976. [44] A. Rosenfeld and M. Thurston, "Edge and Curve Detection for Visual Scene Analysis," IEEE Trans. on Computer, vol. 20, pp. 562-569, 1971. [45] Brian G. Schunck, "Gaussian Filters and Edge Detection," GMAR-5586, Research Publication, october, 1986, General Motors Research Laboratories, Warren, Michigan 48090. [46] Glenn Shafer, A Mathematical Theory of Evidence. Princeton, NJ: Princeton University Press, 1976. Behavior 49

RSD-TR-2-87 [47] M. Shah, "Multiresolution edge detection," Ph.D dissertation, 1986, EE. Department, Wayne State University, Detroit, Mi 48202. [48] Mubarak Shah, Arun Sood and Ramesh Jain, "Pulse and Staircase Edge Model," Computer Vision, Graphics and Image Processing, vol. 34, pp. 321-343, 1986. [49] David Waltz, "Understanding line drawings of scenes with shadows," The Psychology of computer Vision, 1975, Ed. P.H. Winston, McGraw Hall. [50] A.P. Witkin, "Recovering Surface Shape and Orientation from Texture," A.I., vol. 17, pp. 17-45, 1981. [51] Andrew P. Witkin, "Scale-Space Filtering," IJCAI, vol. 2, pp. 1019-1022, 1983. [521 A. L. Yuille and T. A. Poggio, "Scaling Theorems for Zero Crossings," IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. PAMI-8, No.l, pp. 15-25, Jan. 1986. [531 X. Zhuang, T. S. Huang and H. H. Chen, "Multi-Scale Edge Detector Using Gaussian Filtering," IEEE Computer Society conference on Computer Vision and Pattern Recognition, 1986. Behavior 50

RSD-TR-2-87 Appendix A: The proof of Lemma 1 Here we only consider the open curve and the curve can be written as y=C(x). We also assume C(x) is continuous, has the first order derivatives, has the inverse function and they are all bounded. Let H be one of such upper bound constant. f YSj) < <C(z)-D I(x,y) = 2 (z)y <C(z)+D f A(z, ) C (z)+D < y where g174g2. v(I*g) = I*vlg) = I(x,y)*G(x,y) oI I -+~ (z-u) + (y -)2 exp-(-u) ()2 ldvdu + -C (u +D t,v)[2 + (z-u )+l(-v )2 exp[(z-u)2+(y-Uv)2 dvdu J -2 + ( _ )2 + ( )2 _U )2 + ( )2 — oo C (U ~D ) 2 0-4 2D2 +oo C](u e-D I + C ( )2 ( -u )2 + (y -v )21 ( e 2-u )2+ y -v)2 dvdu — oo(u o a4 261 Let I1= glf f[..[ + ]dvdu

RSD-TR-2-87 +100 +CO _- )2 + (y-,,)2 -+( 11= If l(u,)[l-2 + (] U)2+(u)Zlexp[- (Z-u)2+(u)2Idvdu - CC(v )+D e22.~coC(u)-O m f= I I 2U U0)(-2 + (-)2+ -)2 exp[-(-U)2 + (Y-V)2Ldvdu 111= f f!) + 44xDC(u )+D IV = g2f f i a2 + (-u)2 + (Y-v)2 exp[ (z-u)2+ (-v)2 ]dvdu - C(u) a 2r (1) We want to show II and mII are very insignificant when D is large and a is small in comparison with D.' "* 2 III < If J a2 f/(u,v)exp[- (z-u) + (-dvdul 2i 2 -Oo C(u )+Da 2o2 +I (z,,,)2 +1 I (y-v)2! (uv)exp- (Zu)2+ (Yv)dudv=.+.2+.3 -c C(Y )+D ~ 2 * If f L 4 f, (u,v)exp[- +2(y-v )]duv - C(u )+D 202 < Hr1 2(-)2+ (z.u)2 Wlddu H. = IfJ+ 2,v)expi-(z-U )2 + (y_ d 2du -.1 C (u )+D -ym, v / d(uI < H f f exp[ - +Behavior 52

RSD-TR-2-87 When D is large, a is small in comparison with D, 1.1 is very insignificant. II.2'= f (z7 -u) f l(uv)exp[- L( —)2+ ] dvdul -oo C(u )+D 2a < 7 (H-u)2 exp (z -)22+ W ldWdu <Hf 2(z-u)2 exp[(-, )2 + (C(u)+D- )2ldu < H (c(u.)+D-y)o2 ex 202 du When D is large, a is small in comparison with D, 11.2 is very insignificant. +00 (v-)2 II.3 = If I (y-)2, (Uav)eX (xp[-(Z-) + dvdu-.o C(u )+D Or 2V2 < Ha12 f(C(u)+D -y) exp[- C (U)+D- )2+(u)2 du O.__..O0_ 20'2 + -f f exp[T(-U) +(y-u)2dvdu r c(u 4+ 202 < f (C(u)+D-v) exp[-(C(u )+D, )2 + (z-u)2 ]du a2 _00 2__ +oo + 2Hf'() exp[- (Z-U)2 + (C(u +D-y )2ldu + 2H C(u )+D-y 2,2 When D is large, II.3 is very insignificant. Hence when D is large, a is small in comparison with D, II is very small and can be ignored in our discussion. +Cao(u D ao2C(rr )-D {ml < } f f f 2(u,v) exp[- -"....]dvdu[+f +jf ~ (z ) (uv) Behavior 53

RSD.TR-287 ex) dd + C(v )-D )2 expl- 2 + ]dudv + If f (y- V fu) expl ]dudvr = I.l + m.2 + 111.3 +~~C(v )- +oo4H 111.1 < Hf f 2 exp- -u)2 +(y- ) ]dvdu < D exp[( 2H c(D )2 e (z-U)2+( 1 dvdudu - -C.(u)+D 202 420 m2 < Hf r o(l-v)2 eXp-(-u)2+(y-v)a ]dvdu = 2(z -tu2 )2 ) exp[ (yC(U )+D )2Jdu 111.3 <H + (.- )2 exp[- ( - )2+ )2 dvdu =fHI f. _,2 = H.U-C(u )+ D) ep -(y -C(u )+D ) + (u )2du + f f exp[ ( ) )dvdu _ 02 22o Behavior 64

RSD-TR-287 + f -c(+D exp[- (- (,u)+D )2]du Since 1m.l, El.2 and 111.3 are all very insignificant when D is large and a is small, Ill can be disregarded in our discussion. Further more, II and m are the decreasing function of D, in fact lim (11+111) = 0, and thr are the increasing function of a. So for any real positive number e, there exists a monotonically increasing function, L(D), such that when a < L(D), III + E1 < e. When e is very small, it implies that II+m can be ignored in our discussion. (2) We want to show that for every z,, there exists some yi such that (i,, y) is a zero crossing of I1+IV. 11.2 pi= + CI) (-v)2 expl (z- u)2+ (Y-V)2]dvdu!.2: I f y-c(u)) exp[- I d ))2~+ - 0 f(y-C(u)+D)exp[- (y -C( (u)+D)2+ (Z u)2 du a -C(uyD 22 = (y- C(u)+D)exp[- (-()+ D )2 + (-u)2 -f exp[In our discussion range, we either have c-l(v) > C-1(v+D) or c-1(v+D) > C-l(v). Behavior 55

RSD-TR-2-87 Without losing the generality, we assume C-1(v+D) > C-1(v). I11 I9+o + -A +D) __-u)_ (_-_)_ _ dudv o_ (_z)ep -C-I(V ))2+ (-Y2Jdv +.c7 C() exp[ (-U)2+(Y ) 2dvdU -21 C) exp(z-)r+(y2 l dvdu + I1.2 + 11.3 )11.. ff -)2 +p (z-U " +0f (y-C(u))exp[- (C(u2]du 2 (y-C(u)+D)exp[(y -C(u )+D )2 + (Z-U)2 du 2a2 Following the similar procedure, we get = = 2 f ((-C(uC D)exp[- (-C(U D )2 + (z-u )2]du (y-C(u))eXP(y -C (u ))2 + (z -u )2 d+ Behavior 5

RSD-TR-2-87 + 2 f(Z-C-4(v)) expl-(z (U 2dv - (-C-('(v)v-D)) exp[(z -C -(v -D ))2 + ( ]' l dv 202 I(x,y)*G(x,y) P II + IV = (e 1 2) (y-C(u))exp[- (y-c(u )2 + (Z-U 2 + 2) (z- (v)) exp[- (Z-C(v ))+ (v) ]dv -g 1+00 (y-C(u)+Df)2+ _(-u )2 a2f (y-C(u)+D)expl- -2 du 2 +00 ((-C(u)-D)2+ (2 - U) + f (y-C(u)-D)exp[- 22 du xyy)1 ++ (I=v-)2 jd -00 + a2 J(-C-l(v+D )) exp[- (z -C (-+D ))2 + (yV- 2 dv — co I*G (z2,C( z)) sI1+IV (z-,C(-'))( M1 + E' > 0, 1C ( 2) r-(C()C c(u))ex[- (C(z(-C(u ))2 + (Z1-U )2d where M'_(-c-(2)) expju ( Behavior li

RSD-TR-2-87 + (2-g 1) f(z (zl-c-Cv ))- + (c (,J)-U ) J +E1 = a2 1 (C(Z)-C(U)+D~eX1(C(Z)-C(U)+D )2 + (l —U )2 + 27 I (C (z )-C(u)+D)exp[- (() -+o + -C D)exp[ (c(z-C (u-D )2 + (C (-u)2 Id +~ f (c(T, Y,(u)-D)exp[ 4+ (~(-C-'(v +D))2 + (C(1)v)2-d - (z -C1(v +D)) exp[- 22d -'00 2 fI (zl-c-(v-D)) exp[- v Since IE'I is small in comparison with iM1i, it implies that M' > 0. At y=C(zl) - P, where O<P<D, I*G(2,,C(Z,)-P) - II+IV(z,,C(},)-P)= M2 + M2 + M2 + E2 where M 2 (g Ig 2), (C (z tC U, )2 + (2 7_U )2 M 1-g ( 2) 7(C(z,)-C(u-P)exp[-((uP )2+ (z-u )]d 02 (C -Co 202 M:2 -- {2-g 1) C (z 1_-C-C'(v))2 + (C(z1)-v-P )2.2 -- fJ(_ C(v)) exp[- o dv M -1 (C(z,)-C(u)+D-P)exp[- (C(1)-C(u )+D-P) + (Z,-U) Behavior 82 Behavior 58

RSD-TR-2-87:2 +00 (C(z J-C(u")-D -P)2 + (Zr")] u E= 2 f (C(z)-C(u)D-P)exp[- (C(du.(D.P)2+(:.-u.d P l - I,, 20, 202 + (z- (v+D)) exp (z1-C-l(v+D))2 + (C(z).v -P)2] dv 2 vD p ( xz-C-(v-D))2 + (C(zl)tv-P )2 -I f(z1-C v-D)) exp...... ]dv When D is large enough, a is small in comparison with D, E2 is very small and can be ignored. Since P < D,M2 < 0. _ _... du 2(2 -C-() 2)) + (C(z1J-V-P )2d + (g 2-g 1) (z-C-'(v)) exp[-2 + (-g g2)P exp (C(z,JC(u )-P )2 + (z1-u)2 U 1 f9 [ 202exp d Once P is large enough, we will have M2 + M22 + M < O. It implies that there exists some P < D, such that I*G(z,,C(z,)-P) s I1+IV(z1,C(zl)-P) < 0. Since for y = C(x) - P, where O<P<D, I*G(x,y) is continuous for P, there exists some vyo. C(zx)-D < vo < C(21), such that I*G(z1,,yo) I(zl,voy) = 0. So (Z, vo) is a zero crossing. So for every x there exists a y, such that (x,y) is a zero point The existance of the zero-crossing does not depend on o, but the location Behavior 59

RSD-TR-2-87 of the zero-crossing is determined by o. So at any o value, as long as o and D together makes II(x,y) and ll(x,y) insignificant enough, i.e. o < L(D), where L is a monotonically increasing function of D, then we always get a zero-crossing curve corresponding to the edge curve. But we may get the zero-crossings at the different locations from the edge points when o changes. So we have proved the Lemma. Q.E.D. Behavior 60

RSD-TR-2-87 Appendix B: The proof of Theorem 1 Let the edge line be y=ax+b. We can rotate our coordinate system through angle u = arctan(a). Let the new coordinate system be (x',y'). The edge line under the new coordinate system are y' = V So we only need to discuss the situation that the edge line has the equations y = B. (For x = B, it has the similar proving procedure.) f,(z,v) y >B+D I(x,y) 2= B -y <B+D f(xY) y-B-D Let H be an upper bound constant of f (z,,) and f 2(z,). v2(I*g) = I*v(g) = I(x,y)*G(x,y)= 4.glf0 -t - 2 ( +(V ) - + (Y -2 J ldvdu + g2rJ I f,+)[ - +4 (z ) y 1 exp[ (1-U)2 + (y_)2 dvdu + Ie -v 2U ]dvdu + Jo r J2( 1Z 2 + ( —2 u )2+ vv 1 expf _(z-u )2 + (y-v )2 ldvdu = I1 + IItI + 4..V Beharrvior 61

RSD-TR-2-87 where - 2 z-0+( -v ]_exp[- 2U )(v-v)2 + ( 2]dvdu I1=glf f f (u,v)[- +.... 2 Ill=gI (f[2 + (s-u)2 (vD)21 [2 0)(-v4)2a2dvdu -oB +D a 22 II = gl f f 1 + (- 2+(-V ex ].dvdu -oo B - Iv = -g22J 2 (u(u) )2( + -v)2 (z- 2 + (y- ) +ooB -D -2 + T _U )2 + (yZE fff2(UV)I[-e 202 exp[-(U )2 + (-)21 I dvdu 202 44mB +D 4voB +D II = glf f| -2 exp[ (Z-u)2 +( U-v) ]dvdu + gl J (u exp[) 4ooB +D (z-u) + (y-V )2 ]dvdu + gl f J (v 4 ) exp[l(U ) +(y) Jldvdu 2002 - or4 22 II.1 + 11.2 + 11.3 +ooB+D +o2B +D 11.2 = glf ( 4 expI -( 2 JdYdu = ~ f exp[ -co B o 22 — po B (z-U + (y -v )2 ldvdu -,20 +ooB +D) 11.3 = glf f V exp[ (- (z-u )+ (-V2 dvdu gi(y-B-D)o exp[- (-v-B )2J iB B =l - gl (U i-),, exp[- (Y-B)2-+ g l r -, o 2 +glf f -- exp[ Behavior 62

RSD-TR-2-87 _ (-U)2 + (yv2 dvdu 202 So II = gl(y-B-D ) exp -(BD) gl(B-Bexp- 2 -B)B _ ) ex ) 22 | 2o2 r00 B 4-00 p[(-2B)(2 y 2 = g2 Y B _) I _2 l dvdu + g2 f fXJ2 exp( ( U )2 ++ 2 ]00.. 2) +(f_(y J ]dvdu + g2 (yV) exp[ f-(u + -V ( dvdu 202 -exB-D 0U 202 HI B- g2fs~oou exp[ ( — e I —x,y)Gxy + + -px uva 11.3= -B-D 20,4 B -- D 202 )2+3 ( vd g2 f f (y - e + (Y- ]dvdu --- B -D O44 2o0.So = g2 (y-B) v exp[ (y-B)2 g2 — B+D)J-r exp[(y-B+D)2 = a 202 a 202 I(xy)- G(xy) = M(xy) + E(x,y)

RSD-TR-2-87 where M(x,y) = - gl (y-B) v exp[- (y-B)2 +2 (v-) exp[- (-B)2l D)E(xy= gl-B-D) exp-) g2(-B+D)j -(-B+D + I E(xy) = ) ( exp-.(V-B +1 1] +I + IV Now we want to show that at y = B, E(x,y) is very insignificant. *W+m -2 (zu.)= + (Y-o)f + D -2( H +r[ r 2( + ( )2Jy- vdu Since at y=B, when << — and v > B+D, _2 + (u > 0; so.i H + (2-u)2 +(v-v)] expI-(Z-U ) + (-v)2]dvdu -o B +D 02 4 22+D p(- f )2 + (V)ddu + H (-) expl-((- )) +(-)dvdu = I(.-u + 1.2 (- 2 exp(-U)2+ (Y-v)2 dvdu 2 -o B +D 22 -B+D o ( ~ ~ ~ ~ ~ (-vexp[- -u + (_V)442y-)v exp[ - 2) - ]dvdu + Hf f (v-v)2 02 = 11.1 + 20= -.... 2 11.23 H J (-V ) exp=x- H f I-I 1-Ui e =]dvdu = (-U) + Behavio B4p[- a B 2 exp[a(iu )2 2dvdu= Behaviord64

RSD-TR-2-87 f f MH x[p ( U )2 + (yv)2f dvdu a+D P20] J8 2 202 HD 0exp[-U)2+ (yVf _V.S H' BD vr 2exp. + f f -2 exp[-( + (Y-f 2dvdu HDb D2 At y = B, IIlI < D v'expD 2 a 2'o +mBo -D + 2,f +,{Ivi < H f f 2.U + (y exp[ +.]dvdu irv 00 2 &U 202 D -2 (_ -_) _ + (Y -_ Since at y=B, when or< and v < B-D, + (z> 0; so I2 I- I 1 102 4 >Ol4 =I- H B-D -2 (z-U)2+(2-)2 eXP[((-)2+ (U V)2U dV dU P[_ HZ _U lV )2+ fB-'_exp[- d.... ex 2o (T-" )2+(Y —B'~dvdu + H f f a4 22V, p[U.2= H (-h)Jd expl- -( u) +4([ -) ldv(du = ol + V.2 + V.3IV. 2 =H H exp[()-U P +(Y U)(y-u H ex[( 2(V)dd]dvu I.3=HJ f j exp[-h 2f]dvdu f ~0-.O —.oo Behavior 65

RSD-TR-2.87 fI H expl-[ (U+(VU ldvdu HD D~Tex LD21 + cSB2-D 2 =H exp - + f H p —(ZU)2 + (V-V)2 ]dvdu 01 2a2 _- _= V 2o2 At y = B, lIVl < - vexp[-_] So at y = B, IE(x,B)I < gl -V exp_- + g2 f exp[- 2 + 2Il + IVI < o expD+gIexp ~ + D D2 D2 HD,-D2i e]- vexp[L 2- ]+2 e/ exp + - v2rexp[- Since gl < H and g2 S H, so E(x,B) < 4H 1)exp[- 2 W v e.5 Dxp[- D When - > 2.5, expD- _ 0.88 < 1, so E(x,B)< 4H\2' exp[- ]. For any real number e, O<e<4Hv2i', when a < TI(D) = min { D 2.5,' 3D4 } E(x,B) < e. In most cases, > D so we take TI(D) =. Obviously, T1 is a monotonically increasing function of D. So we have proved that E(x,y) is very insignificant, M(x,y) is the dominant part. Without losing the generality, let's assume g2 > gl. For y=B' < B, and B' is very close to B, I(x,B')*G(x,B') s M(x,B') = (g2Behavior 66

RSD-TR-2-87 gl) ( -B) expl- ([a )I < 0. P 202 For y=B' > B, and B' is very close to B, I(x,B')*G(x,B') t M(x,B') = (g2gl)(B -B) exp[-(Y B)j ]> 0. 0 202 At y = B, I(x,y)*G(x,y) -= M(x,y) + E(x,y) = M(x,B) = 0. So y = B is a zero crossing line. It has the same tangent and location as the edge line. Hence theorem 1 has been proved. In the computer vision application, T1 can be further simplified. If we have H<255, choosing e>0.46, TI(D) = -; choosing e>0.12, T1(D)=; choosing 4.5' 4.8' e>0.048, T1(D) = -. In most cases, T1(D) = D is sufficient. Q.E.D. Behavior 67

RSD-TR-2-87 Appendix C: The proof of Theorem 2. Let the two parallel lines be y=ax+bl and y=ax+b2. We can rotate our coordinate system through angle 4 = arctan(a). Let the new coordinate system be (x',y'). The edge lines under the new coordinate system are y' = L and y' V'T n V2 So we only need to discuss the situation that the two edge lines have the equations y = B1 and y = B2, where B1 > B2. f (z),>B1+D 9g B 1<y B1 +D I(x,y) = 92 B2<y <B g3 B2-D <y<B2 -f 2(,v) y <B 2D Let H be an upper bound constant of f i(z,y) and f 2( z,). v2(I*g) = I*v2(g) = I(x,y)*G(x,y)= I0 4,2 -(( - 2 + _ (y-VU)2_ep-(-U)22+ (y -) ldvdu + ooB 1+D+ gl I + - + (v- ) ] exp[[- + (v-u) g2o~ I 1_2x)2( - ( 2+ (y-v...dvdu + -oo B I + 2 XBU ( )I + (y- _ )2 X ________)2 _ _), g2fl [B 2 + (-)I exp[ (z-u)2+(y-u)2 dvdu + o BoE a 202 Behavior 68

RSDI-TR-2-87 f f2( )F-O2 +' ] e (- + (V(-v)21 ] l r_ dvdu -o0 -00 202 I1II + +III+ IV+ V where 4004+00 -2 - )' + (y-Z. J2 + 1= I f( fU,)[ 2 + (2-u)+(exp[ A-U)+(V - ]dv oo B +D +~lr(-2 + ( -u )2+(yv)2 exp[ (z-u)2 (-V2 Jdvdu Ill = g2J 1lo + ( ) o474 ) exp[2( - 7202(v ) ldvdu Hn glf f I? + a I 2_+IV =-2 (z-u )2 + (v-v)1 exp[ (zu v ]dvdu HI = g2 f f [-~+ 4 I epd2 ooB2-D 2 V f= ~ f2(uv)[_22 +'(y_ I exp[ -( z-U,)2 + (y-_v)2 ]dvdu - B02-D 2 202 +COB B 2-D -2.(2" )2 + dl -~ eXP[ (- _U 2 + (Vu —)2 dvdu Following the same proof of part II and part mI in theorem 1, II gl (y-B1-D) xp[- (y- 1-D )2 (v-Bl) o.- y-B ])2 a'7 2rep[ 202 aa 2oa2 = g2 (y-B 1) v, exp[- (y-B1) g2(y-B2),'i; exp[- (Y-B2)] 202 O 2a02 IV - g3(y -B 2) v exp[- (y -B 2)2 - g3 (y -B2+D) f exp[-(y-B 2+D )2 v2I*g) = I 2(g)= I(x,y)*G(x,y)= M(x,y)+ E(x,y) Behavior 69

RSD-TR-2-87 where E(x,y) =-g3 (V-B 2+ D) exp[- (y-B2+D) +gl(y1 ) exp[ 202 -a0 -00o2 & 22 V- )ep[-Z -Up)2 + ]] d vdu+ fy-B 2] f f!(u, v)[(2~ + (-u~+(~~<u pdvdu -oo B 1+D 2 = E + E2 + E3 + E4. M(x,y) = (g3-g2) (-B 2) expl- (y-2) | + (g2-gl) ( exp[- )- (y - )2 By the definmition, without losing generality, we assume g2 > g3, and g2 > gl. Let W = B1-B2. Part 1. To show that there are two zero crossing lines y=B01 at y > BI and y=Bo2 at y < B2. (l.a) To show B2<y<Bl is a negative region. When B2 < y < BI, then when a < D, tEll = 3 (exp[- (y-B+D)2 <g3 ) exp[- (vD2 2 = g (B 1+D ) exp- (B 1 ) <g D exp [ — D JE2C = gl e + - )/ exp[-.] When B2<yiBl, v < B2-D and o<_, then (y-v)2>D2>2~; it implies that Behavior 70

RSD-TR-287 (-2 + ( )2 + (y - ) > 0. Hence {E3{ < H f f [{2+ rT) exp[jE~j ~'B2-D +2 (z-u)2+(v1u)2+) [(z-u) +(1/v)2] d Hf.~ [4 2o2 Following the proof of part I of theorem 1, E31 < HJ f -2 1 (Z U )2 + (zu )2 ) exp-(Z - )2 +(y-v )2 J dvdu < HD exp[D2 02 When B2<v<Bl v > B1+D and o< D then (y-v)2>D2>2o2; it implies that 2 (- )2 + (.. ) > O. Hence E41 <H _ 2+ (z-u)2(y-)2) exp[- 1+(2-v) ] dvdu -<c B Il+D a.2a 2o2 Following the proof of part I of theorem 1, E4 j <~1 [(-2 + (z-u +(y-v )2 exp[-1'-u +(y-] J dvdu -o B 1+Da < no V2.exp[- P 1 Hence for a real number e, 0 < e < 4Hv, when u< T2(D)- Behavior 71

RSD-TR-2-87 El < El + E2 + E 321 + E31 + 1E41 < oD- Viexp[-22I < e. It shows that E is very insignificant when B2 < y < B1. When H<_255, choosing e>0.048, T2(D) = is sufficient. So for B2 < y < B1, I*G(x,y) s M(x,y). For B2 < y < B1, (y-B2) > 0, (y-Bl) < 0, (g3-g2)<0 and (g2-gl)>0, so M(x,y) < 0. It indicates that there are no zero crossings within the region, B2<y5Bl, this is a negative region. (l.b) To show that there exists B' > B1, such that M(x,B') > 0. (l.b.l) When g2-gl > g2-g3, for y- BI + o, IEl g3 = (W +a+D ) exp[- (W ++D )2 For any real number e, 0<e<g3VJ', when a < D + g 3V25 JEll = g3fi(W+a+D) expl- (W+o+D) j < H(W+D) exp[- (W )2 < e. a 2'2 a Note that T2(D) = D D < D+W y' 31n( V) 3 3 ( C Cv w For H<255, when a<, El <0.00006. Behavior 72

RSD-TR-2-87 4-0B2-D -2 "'-u + (L 2) ________2 ____ E3 = ~ f f (u,v) 2[(- + - 4( )exp[ - -U2+(' ldvdu For y = BI + o, v < B2-D, (v-v)2 = ((B1-B2)+o+D)2 > 2 o2, so -2 + ( -u ) + (y -v ) > 0. It implies that E3 is positive. E4= I r,(U,V)[( 2 + )expi-(2-u + (-v 2]dvdu E= B 1+D 02 + For y = B1 + o, v > B1+D, and oa<.+i, (v_v)2 = (o-D)2 > 2 a2, so (2 (z-u)+(y- ) )> 0. It implies that E4 is positive. When y=Bl+a, E2 = gl ( -B 1-D ) exp- D = gl (o-D ) exp[- (2D 1 < 0. a 202 a 2( At y=Bl+a, M(x,Bl+a)=(g2-g1l),vexp[-]- (g2-g3) (W+). v exp[- (W+o)2 g2-gl > g2-g3, and (W +~) vi exp[- (W+) 1 < exp[-2 1 so M(x,B1+a) > 0. For ( 202 2 M(x,Bl+o) + E2(xBl+a) — (g2-gl)Vi/exp[- I - (g2-g3) (W+a);f2 exp[- (W +o)2 -gl (DB) e xp[-(D-B1)22 let's consider the worst case, g2 = H, gl = H-2 and g3 = H-1. Behavior 73

RSD-TR-2-87 M(x,Bl+o) + E2(x,Bl+a) = 2v'exp[-24 - (W+O) vf exp[-(W+) -(H-2)() exp[- (DL-A 202 When a < 2W, lexp[ (W+ —) v ( exp[- (2 > 0~ When <-D (D-) exp[- 0)?Jo.28. -5 ~O 6a2 So when a < D 3 2/exp H- 2) -a exp[-l (D > - (H-2) exp[- > exp 0.28(H-2) exp[- (D) 2 2 20: 2 ['3 > 0. When e < 227, T2(D) D < D (H -2) 3 31n1+ 3, For 0 < H < 3000, when choosing O<e<l, T2(D) = D < D 1+ 3n So we have shown that when O<e<l, o < T2(D) = and a < 2W, I*G(x,Bl+a) > O. Behavior 74

RSD-TR-287 When H=255, a<., M(x,Bl+o) + E2(x,BI+o) > 2virexp[-ll - W+exp[ - (W+)2 1 253(D -) > 3-1.5-0.3 > 0. expl-(D.2 ) > 0.5 > 0. 22 01 202 So we have shown that for H<255, when a < D, I*G(x,Bl+o) > 0. (l.b.2) For g2-g3 > g2-gl, to show I*G(x,B1+a) > 0. At y=Bl+o, from the same analysis in (l.b.l), El, E3 and E4 can be ignored in our discussion, and E2 is negative. M(x,Bl+a)=(g2-gl) I/exp[- - (g2-g3) (W+) v exp[- (+2 Because g2-g3 > g2-gl, M(x,Bl+a) is not always positive. M(x,Bl+o) + E2(x,Bl+a) = (g2-gl)Vzexp- J - (g2-g3) (W+O) V2i exp- (w+f)2] gl(D-) exp[- (D 2] a 2o) Let's consider the worst case, g2 = H, gl = H-1 and g3 = 0. When o < D -E2 = gl ( ) exp[- (D)2] < 1.25. 1]+ x 20.2s) When o <,(g2-g3) i exp[- ) (W]) < 0.1, so M(x, Bl+a) 0 21 > 1.25, hence MI(x, Bl+o) + E2 > O. For H<1000, w < w Behavior 75

RSD-TR-2-87 Note that when e< 10 T2(D) = < For O<e<O.1, when H<1000, T2(D) = D D D WH For H<255 when a< D and a< W I*G(x,Bl+o) t M(x,B1+a) + E2(x,B1+o) = (g2-gl)V-exp[ —] - (g2g3) (W +O) exp[- (+)2] -gl(Di) expl- (D I] > 1.5 - 0.86 -0.342 > 0. Combining (l.b.l) and (l.b.2) we have shown that for 0 < e < 10 2 when a (H_,1) 3 < T2(D) = D and o, I*G(x,Bl+o) > 0. and c. - 1 D W For H<255, when _a<- and <,I*G(x,B+o) > 0. (1.c) To show I*G(x,B2-o) > 0. E2(x,B2-,) = (-glvW+2) (exp[ — (+-2 3)21 wg (wa+o+) exp[- (W+o+D)2 ] <H v'(V+D) exp[- (W+D 2) <e. Behaior when 31n g3V27-l) T2(D)=.. D w....~~~~~~~~~~~~~

RSD-TR-2-87 Note that T2(D) = D < D < D+W For H<255, a<5, IE21 < 0.00006. When y=B2-o, < d, v<B2-d, (v- )2>(D-oa)2>2a2, so (_2 + (-U)2+(y_2) > 0. It implies that E3 = -f f l(u,V)[( -2 + ((jd-!d) exp[-u -+ (- dvdu > 0. At y=B2-a. when v >B l+D, (y-v )2:(W++a+D )2>22, hence at y=B2-a, E4 = f f I-2,(-U 2) eX Z _[-: -2+ (Y-V)2 E4=(, -uf f f(u, + ) exp[- (dvdu -oo B I +D2 aYis positive. So we only need to discuss about E1l and M(x,y). (l.c.1) If g2-g3 > g2-gl, M(x,B2-o) =(g2-g3)v2 exp[- ] -(g2-gl) W+a exp[-f(W+l)J is positive. 2, 20.2 El(x,B2-a) =-g3v'2 (D-) exp[-(D?)2] is negative. M + E1 = (g2-g3)v-r exp[ —2 -(g2-gl) W -g3 exp-(W+)] g(D exp[fDo 2o2 a 2a2 Behavior 77

RSD-TR-2-87 Considering the worst case, g2=H, g3=H-2 and gl=H-l, following the same proving procedure in (1.b.l), for e< 2, when a < T2(D) < D I*G(x,B2-a); M(x,B2-o) + (H.-2)3 1+ 3 El(x,B2-a) > 0. When H<255, o<PD, I*G(x,B2-a) = M(x,B2-a) + El(x,B2-a) > 0.5 > 0. (l.c.2) For g2-gl > g2-g3. Considering the worst case g2=H, g3=H-1 and gl=H-2. Following the same proof procedure as in (1.b.2), we get When a < D,E1 > -1.25. i+. 31n(-1.25),/ When~< W <xp[ (W;U)1, K2~ ] < 0.1, so M(x, B2-o) > 1.25, hence M(x, B2-a) + El > 0. Note that when e< 10, T2(D)= D < (H-1)3 n(,/'F3 n( For H<255, when a< D and a< W I*G(x,B2-a)) M(x,B2-) + EI(x,B2-a) > O. Combining the results from (l.a), (l.b) and (l.c), we have shown that when Behavior 78

RSD-TR-2-87 0.00006<e<0.1, when o<T2(D) = I*G(x,Bl+o)>O, I*G(x,B2-o) > 0, I*G(x,BI) < O0 and I*G(x,B2),< 0. For y=B', BI<B'<bl+o, I*G(x,B') is a continuous function of B', so there exists y=B, such that I*G(x,B,,) = 0, where BI < Bo, < BI+o. For the same reason, there exists y=Bo, such that I*G((X,Bo) = 0, where B2-a < Ba < B2. (l.d) To show I*G(x,B') < 0, for B1< B' < Bo0; I*G(x,B') > 0 for Bo, < B' < Bl+a. (l.d.l) ForB<B' < Bo,. I*G M+E1+E2+E3+E4. M(x,Bo,) = (g3-o,)v (Bo0-B 2) exp- (BB2) + (g2-gl)2 - exp[( B 1)2 = MI + M2, 2o2 E1 = -g3~/- (Bo0-B 2+D) (Bol-B 2+D )2 El= -g3v'~ — exp[ 202 1, E2 = glV; ({B o0-B 1-D ) exp (B o-B 1-D )2 +oB2-D2 (-u )2 + (Bol-v)2) (Z-u )2 + (Bol-v)2d E3 —- f f fdu v)[( + )2 oE4 =00 Ir (z-u )2 + (Bol-v )2 (z-u)2 + (Bo1-V)2 E4== f f fl(Uv)[(- + 4x2]d -.-n I I /6(crPY) 62 0a' 2~2 -.oo B 1+ Obviously, M1 < 0, M2 > 0, El < 0 and E2 < 0, E3 > and E4 > O(as shown Behavior 79

RSD-TR-2-87 in (l.b)) and we have (M2+E3+E4) + (Ml+EI+E2) -- 0. For B', B1 < B' < Bo,, since BI < Bol < B1 +, 0 < B -B 1 < I-B < 1. V2 And Z = Vexp[[ — J is an increasing function when -1 < Z < 1, so /~ -B2 Bol-B 2 O<M2(x,B')<M2(x,Boi). Since a < W = BI-B2, 1 < < B.- function Z = Vexp is a decreasing function when Z > 1, so tion Z = Vexp[ —] is a decreasing function when Z > 1, so Ml(x,B')<MI(x,B,,)< 0. For the same reason, we have El(x, B') < E1(x,B01) < 0. When B' changes from Bo, to BI, E4 > 0 and decreases; E3 > 0 and increases. But when D is large enough, E3 does not increase as faster as E4's decrease, i.e. E4(x,Bo,)-E4(x,B') > E3(x,B')-E3(x,Bo,). Even though 0> E2(x,B') > E2(x,Bo1), but when D is large enough, E2(x,B') - E2(x,Bol) is very insignificant. So in general, the magnitude of the negative part of I*G increases and the positive part decreases, so I*G(x,B') < I*G(x,Bo,)= 0. So there is no zero crossings in region B1 < y < Bo0. (1.d.2) For y=B', B0,,B'<BI+a. When B' is changing from Bo, to Bl+a, -Ml(x,B') > 0 and is decreasing; -El(x,B') > 0 and is decreasing; M2(x,B') > 0 and is increasing, i.e. M2(X,Bo,)<M2(x,B'); E3(x,B') > 0 and is decreasing, E4(x,B') > 0 and is increasing; -E2(x,B') > 0 and is increasing. When D is large enough, E4 is increasing faster than E3's decreasing; and M2 is increasing faster Behavior 80

RSD-TR-2-87 than -E2's increasing. So in general, the magnitude of the negative part of I*G decreases and the positive part increases, so I*G(x,B') > I*G(x,Bo,)= 0. (l.b.3) For Bo2 < B' < B2, M(x,B2) ( BoB 2) (gg2)- (BOrB2)2 (g2.g)i(B-B 1) exp (B.rB 1)2 - M) + M2e (22exp[- ] =M1+ M2. (B()z"B2+D) (Ba-B2+D)} El = -g3v( ~' ) exp(- (22 E2 = gl, (B,-B 1-D) exp[ (B-B 1-D )2 B 2-D 2 (z-u) + (Bo2-v)2 (z-u)2+ (BOv)2 E3 = f f f 2(u V)[( + exp[- dvdu 4W +0 2 (ZU )2 + (BO2-v)2 v_ _ )2 + (Bv )2 E4= J J f (u,v)l[( + (- - )exp[- 2.. -] dvdu Obviously, M1 > 0, M2 < 0, El < O and E2 < 0, E3 > O and E4 > O(this is shown in (l.b))and we have (MI+E3+E4)+(M2+EI+E2)=O. Since B2-o < Bo2 < B' < B2, 0 < B < <, 0 < M(x, B') < M(x,B2). B1-Bo2 B 1-B' Since... > E- > I, IM2(x,Bo)l < IM2(x,B')I, i.e M2(x,B') < M2(x,Bo2) < 0. Behavior 81

RSD-TR-287 Since B1+D-B > B1+D,-B > 1, IE2(x,B0c)I < IE2(x,B')I, i.e E2(x,B') < E2(x,Bo2) < O. E3 is decreasing and E4 is increasing, and when D is large enough, E3 is decreasing faster than E4's increasing. Even though 0> El(x,B') > EI(x,B01), but when D is large enough, El(x,B') - El(x,B0o) is very insignificant. So in general, the magnitude of the negative part of I*G increases and the positive part decreases, so I*G(x,B') < I*G(x,Bo2)= 0. (l.d.4) For B2-a<B <Bin When B' is changing from Bo2 to B2-o, Ml(x,B') > 0 and is decreasing; -El(x,B') > O and is increasing; -M2(x,B') > 0 and is decreasing, i.e. M2(x,Bl)<M2(x,B'); E3(x,B') > O and is increasing, E4(x,B') > 0 and is decreasing; -E2(x,B') > 0 and is decreasing. When D is large enough, E3 is increasing faster than E4's decreasing; and -El's increasing very slowly. So in general, the magnitude of the negative part of I*G decreases and the positive part increases, so I*G(x,B') > I*G(x,Bo,)= 0. Combining the result from (l.b), (l.c) and (l.d), when 0.00006<e<0.1 and 8igma <T2(D) =, we have I*G(x,Bol) = I*G(x,Bo2) = 0, where B1<Bo<Bl+o, B2-a<Bo2<B2; for y=B', B1<B'<Bo, I*G(x,B') > 0, for B01<B<BI, I*G(x,B') < 0, for B2-u<B'<B,; I*G(x,B') > 0, for B0<B<B2 Behavior 82

RSD-TR-2-87 I*G(x,B') < 0; so y=B01 and y=B2 are zero crossing lines. Part 2. No other zero crossings. Combining the results from (l.a) and (l.d), region B,,o<y<Bl+o is a positive region; region B2 < y < Bo,; is a negative region, region B2-a<B'<BO2 is a positive region; so there is no zero crossing in these region. Hence y=Bo0 and y=Bo are the only zero crossing lines in the region B2-a<y<Bl+a. So there is no false zero crossings generated in our discussion region. Part 3. The two zero crossing lines are tangent invariant. As we have shown above that we have two zero crossing lines, y=B01, y=Bo, for every a < T2(D). Obviously, the zero crossings are linear and have the same tangent value as the edge lines. Q.E.D. Behavior 83

RSD-TR-2-87 Appendix D: The Proof of Theorem 3. Let the two parallel lines be y=ax+bl and y=ax+b2. We can rotate our coordinate system through angle 4 = arctan(a). Let the new coordinate system be (x',y'). The edge lines under the new coordinate system are y' -= l and y'._. FijiSo we only need to discuss the situation that the two edge lines have the equations y =- B1 and y = B2, where BI > B2. f t(z,v) y >B 1+D 01 Bl<y <B1+D I(x,y) = 2 B2<y<B1 g3 B2-D <y <B2 f2(2,Y) y<B 2-D Following the proof of theorem 2, we have v2(I*g) = I*v2(g) = M(x,y) + E(x,y) where M(x,y) = (g3-g2)(y-B 2)/ exp. (Y-B 2) + (g2-gl) (y-B1) exp[(y -B1) Let al - (y-B 2)' exp -(y2 -B2), a2 = (y-B 1)V1 ex[- (y-B 1)].- 2a2 a 20,2 M(x,y)-= (g3- g2)a, + (g2- gl)a2 E(x,y) = — g3VZf(Y-B2+ D) expl- (y-B 2+DP i + gl (Y-B-D exp[Behavior 84

RSD-TR-2-87 (-B I-D )2 +2 + (:-u)+(- ex 1 -)u+ (p-))21 1 dvdu + f f f AU, V) + ()+( )exp[-..(. +(l]l dvdu -BI+D 0' 2o2 El + E2 + E3 + E4. Part 1 To show that E is very insignificant when B2<y<BI. When B2<v<B1, following the proof of part (1.a) of theorem 2? we have the following result: for a real number e, 0 < e < 4H-v, when a< T3(D )= D 4HD D2 IEl < JEll + JE2+ E31 + E 3 + E41 < af V"exp [- ] < e. For H<255, choosing e > 0.048, T3(D) = -D is sufficient. It shows that E is very insignificant when B2 < y < B1. So M(x,y) is the dominant part, the rest of the theorem will be proved on M(x,y). Without losing the generality, we assume g3>g2>gl. M(x,B1) = (g3-g2) (B -B 2) exp[- (y-B 2)21 > 0. (BxBl))= a expi[(U 2oa 0 M(x,B2) = (g2-gl) (B2-B1)/' eXpl (y-B1)2a < O Part 2. To show that when a is very small in comparison with W, we have two Beharrvior 85

RSD-TR-2-87 zero crossing lines each of which is tangent and locational invariant to its corresponding edge line. (2.1) When a < -2, B2 < B2+a < BI-a<Bl. M(x,B2+o) = (g3-g2)exp[l-1 + (g2-gl) (B2-B1+ao)f; exp[- (B 2-B 1+o)2 2 a 202 = (g3-g2)exp[ —]- (g2-gl) (W-)v' exp[- (W-)] 2 ] When a < W, (g2-gl) (W?~)' exp[-(w —)] < e. When e (H - \;x47 202 approximates zero, this term can be regarded as zero. So M(x,B2+u) > 0. For H<255, when s<-, (g2-gl) (W -)2/ exp[- (W2] < 1.48*10-". For y=B', B2 < B' < B2+o, when B' changes from B2+o to B2, M2(x,B') = (g2-gl) (Bll- )2I- exp[l-8 B1)]2 decreases, so when a < e 2o1+ 2 /31ni H'l2 }' approximates zero and B1<B'<B2+o, we can disregard M2(x,B'). So M(x,B') = 0 -B2)\/r exp[- ( -B2)2 (g3-g2) - exp[( 2 I > 0 and M(x,B2) = 0. For B' > B2 and B' very close to B2, I*G(x,B'); M(x,B') < 0. So y = B2 is a zero crossing line. (2.2) The same argument can be made for zero crossing line y = BI. For y=B', Bl-o<B <B1, when a < W M(x, B') < 0; and M(x,Bl) = 0. For y=B', B' > B1 and B' is very close to B1, I*G(x,B') 8 M(x,B') > O; Hence Behavior 86

RSD-TR-2-87 we have y-B1 as a zero crossing line too. (2.3) Now we want to show that when a is small enough, there is no zero crossings in the region B2 < y < B1. When _< W-2 for all B', such that B'-B2 > w-2 and BI-B' > 2H"V2x 2 W ~22 2 n( M(x,B') < 2 + 2 = e. When e approximates zero, M(x, B') O0. 2 2 When g3-g2=g2-gl, B2+u < B' < B1+B2-2 M(x,B') > O, BI-a < B' < BL, M(x,B') < O. So the region, B2<y<B1, there is a positive zone, zero zone and negative zone, hence there is no zero crossings in this region. When g3-g24g2-gl, without losing generality, let's assume g3-g2 > g2-gl. For y=B', B2 < B' < B2+ W-2, Ml(x,B') > 0 and IM2(x,BI)l < e, so M(x,B') 2' > O so this is a positive zone. For y=B', B1- W2 < B' < Bi, M1(x,B') = (g3g2)5(i -B2) exp2 - (. -B2)2 ] is decreasing when B' changes from BI- w-2 to 2a~2 2 BI, so this term can be regarded as zero. M2(x,B') = (g2-gl)B'. (. -B 1) exp[(2 -B 1)2] is decreasing when B' changes, M2(x,B') < 0 and -M2(x,B') is increasW22 ing when B' changes from BI-w-2 to B1. So M(x,B') = M2(x,B') will change 2 from zero to negative, when B' changes from B1- w-2 to B1. Hence we have shown that region, B2<y<B1, has a positive zone, zero zone and negative zone, hence there is no zero crossings in this region. Behavior 87

RSD-TR-2-87 So we have shown that when a< 2, there is no zero crossing in the region B2 < y < B1. W-2 For H<255, choosing e = 0.00023, a<~ — is often sufficient. So we have shown that when a< -2, we have two zero crossing lines, y=BL and y=B2. These two zero crossing lines have the same tangent as the edge lines and each of them has the same location as its corresponding edge line. Part 3. To show that when a is not too small in comparison with W, we have three paralle zero crossing lines. (3.1) For g3-g2=g2-gl. At y=BI+B2 2 M(x, + ) = (g3-g2) (B 1-B 2) va exp- (B 1-B 2)21 (g2-gl) (B 1-B 2) v~ exp[MX 2 2a 802 2e (B 1-B2)21 = 0. 8a2 For B2 < B' < B1+B2 and a is not too small in comparison with B'-B2, i.e.''2.... (g3-g2) E-B2 exp[-IB -B2)2] cannot be regarded as zero, M(x,B') < 0; for 1+2 < B' < B, and is not too small in comparison with B1-B', i.e. (g2gl )B-B 1 exp - (I -B 1) ] cannot be regarded as zero, M(x,B') > 0. Behavior 88

RSD-TR-2-87 So y BI+B2 is a zero crossing line. S 2 When a< W B -B 2 0 < B2+a < B+B 2 2 2 2 M(x,B 2+o) = (g3.-g2)v2 exp[-4 i + (g2-gl) (B 2+a-B 1) VJ exp[-(B 1-B 2+2)2] Since _L7 1 exp- l] > (B2+o-B 1) exp[- (B1-B2+a)21, so M(X,B2+) > 0. 2 a 2a2 W2 When a is not too small, i.e. when (g2-gl)- exp[- I cannot be regarded as W 1112 zero, we have M(x,B2) = -(g2-gl) exp[- IJ < 0, M(x,B 2+a) > O and B2 < B1+B2 B2+o < 2, so there exists a zero crossing line,y= BC2, where B2 < Bo2 < 2. B2+a. 1 B1-B 2 B.1+B 2 When a< B-B2 B+B2 < B1-a < B1,'2 2 2 M(x,B 1-a) = (g3-g2) (B 1-B 2-a) r exp[- (B 1-B (g2-gl) exp[- 7 22a2 Since - 1 (B 1-B2-a) exp[- (B 1-B 2-) > exp so M(X,B -) < a 01 2o9 2 e, so M(x,B I-a) < 0. W w2 When a is not too small, i.e. Wexp[- I] cannot be regarded as zero, we have B >+B2 M(x, BI) > 0, M(x,B 1-o) < 0 and B+2 <BL-a<B1, so there exists a zero crossing line, y=Bo0, such that Bl-a < Bo0 < B1. Behavior 89

RSD-TR-2-87 So we have shown that there are three zero crossing lines in the region B2<y<BI. (3.2) when g3-g2 y g2-gl, without losing the generality, we assume g3-g2 > g2gl > 0. When o is not too small, i.e. 2' expl- 2!] cannot be regarded as zero, we have B1+B2 At y= MI = (g3-g2) ~~ Bl B2exp[-(B l-B2)2] > 0 2 8o2 M2 = (g2-gl) f B 2-B 1 exp[- (B I-B 2)2] < 0, U 2 8o2 so M(x, B +B 2) > 0. Since M(x,B2) < 0, so there always exists a zero crossing line, y = B,, such that B2 < Bo < B1+B2 For y=Bl-a, when o< W B1-B2 B 1+B2 <B 1-<B1. 2 2 2 M(X,B 1-)= (g3-g2) (W ) exp[- (22 (2-gl); exp[-] When a is not too small in comparison with W, -a is large, we will have (W-a) expe-(W-xa) (< 92-g ) 1p-1 = 0.6(2l) it implies that M(x,Bl-o) a 2 I (g 3-gx2) 2 (g 3-g 2)7 < 0. More precisely, when (W-) >2, i.e. a<.W (w-) exp[-(w". 2~] < 1.03. So Behavior 90

RSD-TRo2-87 (w- exp[-(W a)2] < 1.03expl-(W~) When a<.. _M(x,BI-a)<O. 1+I ( o 058(g 2- 1) Since M(x, Bl+B2) > 0, M(x,BI) > 0, M(x,BI-o) < 0 and B 1+B 2< B-o < 2 - "2 B1, there exist two zero crossing lines, y=Bo0 and y=B03, such that B 1+B2'"2 B03 < Bl-a < B0o < B1. (3.3) g2-gl > g3-g2. By the same proof procedure above, it can be shown that we have one zero crossing line, y=BOI, where 1+B2 < Bo < B1. When 2 a< W, we have two more zero crossing lines, y=B03 and ~1+ 31~g 2-g l 0.58(g 3-g 2) y=BB2, where B1+B2 > B03 > B2+a > Bo2 > B2. Combining the results from (3.1), (3.2) and (3.3), we have shown that when a is not too small and a <, we have three parallel zero cross0.58(g 2-g 1) ing lines. For g 3-g2 _ 255, when a<,M(x,BW-a)<O. g2-g 1 M For g 3-g2 For.. = 100, when <-, M(x,Bl-a)<O. For 9 = 10, when < M(x,BI-a)<O. Behavior 91

RSD-TR-2-87 For g 2-g 5, when a< W, M(x,Bl-a)<O. g 2-g 1 3.5 For 93-g = 2, when <ff, M(x,Bl-o)<O. g2-g 1 3 Part 4. To show that when a is large, we have only one zero crossing line. 0 -B2 ex[ 2) When o is not small, for any B', B2<B'<B1, (g3-g2) exp[ -B2) and (g2-gl)B 1-0 exp[- (B - B' )] are significant and can't be regarded as zero. or 202 (4.1) For g3-g2=g2-gl. As we have shown in (3.1), when a is not too small and a < T3(D), y= B1+B2 is always a zero crossing line. For y=B', where B2<B'< B1+B2 M(x,B') = (g3-gg2)(" _______ - (g -Bg1) (B 1 \ exp[(B1-Y )21 2a2 where B1-B' > B'-B2. When a> w, < -B2 < 1, a o (/Y -B 2) e( -B 22 (B 1-/ )2 -B exp[-( -2)2] <( exp[- (B i- )_, so M(x,B') < 0. 07 202'7 202 For y=B', where B1+B2 < B' < B1, Behavior 92

RSD-TR-2-87 M(x,B') = (g3-g2) ( 2 -B2)xi exp[-12 J (g2 -Bgl) (B I- 2 exp[U 2a2 a (B1-B )2 2u2 where BI-B' < B'-B2. When a2W, I b < B B2 < 1, 0U a ( -B2)exp[/l-..2)2 > (BI- )exp[.(Bl- )], 0 2 or 2V2 so M(x,B') > 0. Hence we have shown that when a > W, for y=B', B2B'< B +B2 M(xB') < 0; for B +B2<B'<B1, M(x,B') > 0. So y=B1+B2 is the only zero crossing 2 2 have shown in (3.2) that we have a zero crossing line, y=BO, for every a such that a<T3(D), where B2<Bo< B1+B 2 2 For every B', such that B1B < B' < B1. -B 2) r exp[ < -B __ B _1 M(x,B') = (g2g2)(B -B2)g exp- ( -B2)] (g2-gl) (B 1-B )v i/ exp[r 222 U (B 1-B )2 2a22 Behavior 93

RSD-TR-2-87 so M(x,B') > 0. It implies that there is no zero crossings in the region B 1B2< y < B1, So we have shown that when a> W, we have only one zero crossing line, B1+B2 y=Bo, where B2 < B. < B12 2 For g2-gl>g3-g2, it can be shown by the same proof procedure that when o> W, y=Boj, where 2 < Bo < BL, is the only zero crossing line. Part 5. To show that there is no zero crossing in regions, B1 < y _ Bl+a and B2 - a < y < B2. When D —.+oo, there is no zero crossing in regions, y>B1 and y<B2. (5.1) As we have shown in Part 1, at y=Bl and y=B2, when a < T3(D), IEI < e for all small positive number. It means that E is very small and can be ignored. We have also shown that I*G(x,BL) t M(x,B1) > O and I*G(x,B2) ^ M(x,B2) < 0. M(x,y) = MI + M2 = (g3-g2) (-B2)v exp[- (B2)2+ (g2-gl) (-B) 2 + (g2-gl) exp[- (Y —')2 E(x,y) = El + E2 + E3 + E4 = g3"y-(B2+D ) exp[- (y-B2+D)2 +gl(-B1D) expi(VB1-D)2 +,I I~2+(-u) +(,-v)exp[ (_U)2+(___)__ d Behavior 94

RSD-TRo2-87 +oo 2+( I oI +(D,v) +c- 2 (z-u ) ()+ (y- exp[ -z- dvdu B 1+D 2a (5.2) For BI < y=B' < Bl+a. We have Ml(x,B') > 0, M2(x,B') > 0, El(x,B') < 0, E2(x,B') < 0, E3(x,B') > 0, E4(x,B') > 0. Since the increase of M2 faster-than -E2, so M2(x,B')+E2(x,B') > O. When a < T3(D), E1l is very insignificant. So I*G(x,B') > 0. (5.3) For B2-o < y=B' < B2. We have Ml(x,B') < O. M2(x,B') < 0, El(x,B') < 0, E2(x,B') < 0, E3(x,B') > 0, E4(x,B') > 0. When B' changes from B2 to B2-o, E3 is increasing, but not as fast as -M1. When o < T3(D), E4 is very insignificant. So I*G(x,B') < 0. Combining the results from (5.2) and (5.3), we have shown that when a < T3(D), there are no zero crossings in the regions Bl<y5Bl+G( this is a positive region) and B2-o<y<B2(this is a negative region). (5.3) When D --- +oo, I*G(x,y) = M(x,y). When y>Bl, I*G(x,y) = M(x,y) > 0. When y<B2, I*G(x.y) = M(x,y) < 0. So there is no zero crossing in regions y>B1 and y<B2. Q.E.D. Behavior 95

RSD-TR-2-87 Fig. 1 The receptive fields of retlnal ganglion cells.. e Fig. 2 Typleical sero crossing contours In a scale space Image. ~S?,.hi Ph f Fig. 3 Examples of the Non sero crossing contours of L-G. I(6) {) (CI (d Behavior 96

RSD-TR-2-87 FIg. 4 The sero crossing contour of a step edge drawn by Shah. 16 O 9 50I W f _ 1'TI Fig. 5 The sero crossing contour of a pulse edge drawn by Shah. I1 0 I C C -6' 8 00 2 x -X Is Behasvior 97

RSD-TR-2-87 Flg. 6 The sero crossing contour of a stair edge drawn by Shah, P=I. 50 —.* -' -20 -8 00 8 00 0'4 00 x-ax is Fig. 7 The sero crossing contour of a star edge drawn by Shah, P=2. (C) 0 -2 0 -8 0 8 o00 2 o0 x-ax I s Behavior 98

RSD-TR-2*87 Fig. 8 Two dimensional L-G operator s shown using Intensity to ndlicate the value of the function at each point. Fig. 9 The sizse of the zero crossing curve incrc a Increases. IIWUT IIRGE SIG6M: 0.5 S16nR: 0.1 SIllS =: 0.9 SIGIa = I SIGlt 1.2 SIGMn II.5 SIGMI 2 0 SI09 = S Behavior 99

RSD-TR-2.87 Fig. 10 An example of an Isolated non-linear edge curve. When a changes, the shape of the sero crossing curve I changing too. IfUT IIIIIj SIGM2:: 2 SIGI: 65 SIG6lI B SIGMA: 10 SIGIA: 12 FIg. 11 An example oft D-solated linear edge curve, where D=-10, When a_3< D 3' we have linear sero crossing line; when >4>, the sero crosclng curve is not linear. i o..=:S l: = 8 Behavior 100

RSD-TR-2-87 FIg. 12 An example of a Dlsolated inear edge curve, where D=20. When a<4<, 4' D we have linesr zero croslng lie; when o~6>-, the rero crousng curve Is not linesr., - - 0 < %aWtIt,- 4 sEjV,sn' Is no Influence of edge lines, when o>3> 3, the zero crossing lines change the locations. Be ha-vi.:.ori.- t....101...........................I-. -: FBe. 13 An 101mple o two lolted pule edge lner ith idth=3. When a<2, there l~~~ sXrSv -tsa I~~'~II"I~l~heB~~ _~liJ~~T _ft-~ I S1#~~~~~~~~~~c~? SFT

RSD-TR-L287 D Fig 14 An example of two pulse edge lines with wldth=-10. When <_3< D, there hI D no Influence of edge lines; when 24>, the seo ross ino g line ehange the ocatlons. I1UO55 tIlV ~=1 Flg. 15 An example of two pulse edge 11es wrth rdth=10. When a<3<, there 1 no Influence of edge lines; wthen a24> D the zero crowlng tlnes change the locations. INPUT IK1fE SIGM: 2 SIGM -3 SIG61t M I11 M55 2[ID3 V=10 Behavior 102

RSD-TR-2-87 Fig. 16 An example of two pulse edge lines with wIdth=1. The sero crossing contours In the scale space show the dislocation of edge lines. Fig. 17 An example Of two staircase edge lines. The false one disppears with s2 at u>55. -t,.ng *ma S_ I-i_____; i SI I a IZR CRO$I - BehSa v ii or: 5:103 Behavior 103

RSD-TR-2-87 Fig. 18 An example of two stalrcase edge lines. The false one disappears with s1 at a25. Note the differences In Intensity levels I:. Im'~'lW~s...SlIGN: 2 S15M: ] SIGNm: q S It t _ 1SO t, Flg. 19 An example of two staircase edge lines. si and s2 move towards the false one evenly and disappear together at a>7.5. ehl a i SIG 2 S1IGM 3 S4M q Z Z Behaviio = 1 61f 0 4ws'tG

RSD-TR-2-87 FIx. 20 One closed resgon with gray levels gl and g2. gi 1 I FIg. 21 An example of one Isolated corner with wldth-3. The region expands with Increase In the value of a. 1WUT IMCE SIGR = SI6 1 3 SltrM = SIGMR = 5 SIGMnA SIGM: 1 Behavior

RSD-TR-2-87 Fig. 22 An example of one Isolated corner with width= —1. The region expands with Increas In the value of a. IIUTV IljtE SIWIf 2 SIM = 3 SIGM = SIlGM S SIGM - 6 SIG: - 1 SIGM = g Fig. 23 Two neighboring closed regions with gray levels gl, g2 and g3. 1913 gl Behavior 106

eSD-TR-2-87 FIg. 24 An example of the merging of two regions I PUT ImuGE SIA = 2 SIGM: SIGM:= 5 l, 01 ~o 1o SIG6D = 6 Sl[ - 1.1 SIA 1 SIM = 1.2 SIGnA = a SIG:e = 9 Fig. 25 One region contains a subregion with gray levels gl, g2 and g3. Behavior 107

RSD-TR-2-87 Fig. 28 An example of one false curve between two elosed eurves Note changes In sero crossings as o Increes. I~~~~~~~~~~~~~~~~~~~~~~~~~~~ q 8w~~~~i: ~ Fig. 27 An example of splittIng, merg~g and expandig JUT lM.E S1C = I.I f t:2 SIGM: 3 r~~ no no no Behl'Ul 108R SlM =.5 Sion S16M I -"' ~~~*0"i~~~;'~~Z ~-~~~~~~~-~:-:ajl~~~~~ll~?;~~~~h;J~~pp 3~~~,~ - ~ ~ ~ ~ r Sl-rR e Beharrior 108~~~~~..t~61

3 9015 03483 8105 Fig. 28 An example of expandIns and splitting. IW1UT IME SIGM 2 SIG11: 3 SIGI = Flg. 29 This Image shows a noisy square againt the noisy background. To recover the square, it may be requ-red to reason In the scale space. For a large a, the preseac of square may be detected and low a will give the location. IWUT 1lAfG SIGI61 = 2 SIGMR 3 SIGM fi x0 IOX.,0a,,f*:.S~~~