RSD-TR-12-83 EDGE DETECTION USING CONTOUR TRACING1 Edward J-elp Chee-Hung Henry Chu July 1983 Center for Robotics and Integrated Manufacturing Robot Systems Division COLLEGE OF ENGINEERING ANN ARBOR, MICHIGAN 48109 THF UN'VERSITY OF MICHIGAN E'ENGINEERING LIBRARY 1This research was partially sponsored by the Center for Robotics and Integrated Manufacturing, Robot Systems Division, College of Engineering, University of Michigan and the Air Force Office of Scientific Research under Grant F49620-82-C-0089.

-2fL A "uM 6 -

ABSIRACT An approach to edge detection using the direction information provided by ioth the gradient masks and template masks operators is examined. The edge lirection is used to trace an edge segment. Five edge operators developed using his approach are discussed. An evaluation of their performances compared to onventional operators like the Sobel operator, three-level template matching perator and the Frei-Chen operator indicates they produce better connected dge segments and thinner edges. Results of applying these edge detectors to eal-world images are also presented.

1 1. Introduction The fundamental step of image analysis is segmentation, which partitions the image into individual objects. One method of segmentation is gray level edge detection. The output of edge detectors are usually linked together to form continuous boundaries for further processing, such as shape analysis. Hence, besides the accuracy in edge location, desirable features of the output should also include thinness and continuity of edge segments. One approach to the problem of edge detection is the parallel algorithms which are discussed by Davis [1]. The parallel enhancement/thresholding algorithms use spatial operators to enhance the original image to form an edge enhancement strength map. The value of the edge strength map at each pixel is a function of the two-dimensional spatial convolution of the spatial operators and the image subarea in the neighborhood of that pixel. Typically, these spatial operators are 3 x3 or 2 x 2 windows. The strength map contains values that are high at areas with large change in gray level and low at areas with almost constant gray level. A thresholding decision can then be applied to the strength map to determine the presence or absence of edge points. The spatial operators can be differential operators (e.g. gradient-like operators) or template matching operators: Both types of operators provide a measure of the rate of increase/decrease of the gray level as well as the direction of the maximum increase/decrease. The direction information at any point can be used to determine the edge direction. Robinson [2] showed that the edge direction information can be used to improve the performance of the enhancement/thresholding edge detectors. This paper presents an edge detection algorithm that makes use of direction information for connectivity analysis. The basic scheme of the method is shown in Figure 1. The decision strategy classifies a pixel as an edge point

2 -- -- Figure 1. Overview of Proposed Edge Detection Algorithm according to its location, strength of the edge enhancement map, edge direction, and the gray level value at the pixel. The strength map is thresholded and connectivity analysis is used to trace an edge segment. This segmentationfollowing-enhancement approach can be implemented as a sequential edge detector. Based on different connectivity strategies and methods of thresholding the strength values, five edge operators have been implemented. An empirical evaluation of their performance under additive white Gaussian noise and saltand-pepper noise as well as the results of application of these edge operators to real-world images are presented. 2. 3 x 3 Spatial Operators In this section we introduce the types of edge operators used in our study and how the direction or angle information of these operators is obtained. The inner product of a 3 x 3 mask and 3 x 3 image subarea is defined as (the notation is due to Frei and Chen[3]):

3 (W,X) = X2 ij (1) i=lj=l G11 C12 W13 where W = -c21 CJ2 c2 is the mask 3C1 C32 C33 Xll 212 Z13 and X = 2 21 22 z23 is the image subarea:31:32 s331 Two types of spatial operators have been considered: the differential operators and the template-matching operators. Differential operators implement a discrete gradient-like function and are of the form shown in Figure 2. The gradient of a function has a magnitude that measures the maximum rate of increase of the function and a direction that points towards the maximum rate of increase. Let X be the 3x3 subarea of the input gray-level image f centered at (ij). We define discrete differentiation at pixel (i,j) in the y direction as: (GV,X) = {xf (i,j + 1)+f (i+lj+l)+f (i-1,j+l) - {cxf (i,~-l)+f(i+1,j-l)+f (i-lj-1) (2) -1 0 1 -1-c -1 -c O c 0 0 0 - 1 0 1 C 1 Gy Gz Figure 2. Differential Gradient Operators ~~,,............

4 This is the 'difference of two weighted averages of f centered at (i,j+1) and (i,j-1). The weight is determined by the value of c. Similarly, discrete differentiation in-x direction is:(G..X) = {cxf (i+lj)+f (i+1j +l1)+f (i+lj -l1) - jcx(i.-j1)+f (i -lj+l)+f (i-1i-l)} (3) This is the difference of two weighted averages of f centered at (i+l,j) and (i-1,j). The weight is determined by the value of c. The strength of the enhancement map at pixel (ij) is the magnitude of the gradient at (ij) and is defined as: m(i,j) = 4/(G3X)z + %G.X) (4) and direction (or angle) of the gradient at pixel (ij) is defined as: 3(ij) = tan,'(GX) (5) (GzX) The isotropic gradient masks that we have used have c = V. The template matching operators do not produce a gradient-like magnitude. Instead, they produce a discrete differentiation in each of eight specific directions using a set of eight templates (Figure 3 shows one such set). The strength of the enhancement map at (ij) is the maximum output value from these eight templates. m(ij) = maz (wX) (6) where Wk's are the template masks. The direction value 6(i,j) corresponds to the direction associated with the largest output. The set that we have used is the 3-level template masks [2] as shown

5 in Figure 3. 3. Edge Detection by Contour Tracing In this section we discuss a new class of contour tracing edge detectors. We present first an overview of the algorithm and describe various properties and threshold selections. 3.1. Algorithm We shall assume that the edge direction at any point is perpendicular to the gradient direction. We define the edge direction at spatial coordinate (ij) d(i,j) to be d (ij) (ij)-. (7) where t(i,j) = direction value found by the spatial operator. 1 0 1 0 1 1 1 1 1 1 1 0 -101 -10 1 0 0 1 0 -1 - 1 0 1 -1 -1 0 -1 —1 0 — 1 -Wo W W2 Ws 1 0 -1 0 -1-1 -1-1 -1 0 1 0 -1 1 0 -1 0 0 0 -10 1 1 0 -1 1 1 0 1 1 1 0 1 '4 W5 We W7 Figure 3. 3-level template masks.

6 Depending on the connectivity scheme, d(i,j) can be quantized to one of 8 values using chain codes. In general terms, to be classified as an edge point, a pixel must be at the appropriate spatial location relative to a previously found edge point, have an edge direction that provides good continuation with previously found edge points, and have m(i,j) (i. e., edge strength) above a certain threshold. The gray level of the point and its neighbors can be used to vary this threshold from pixel to pixel. This is useful when correcting for illumination variance effects. This approach is similar to Davis' sequential edge detection procedure [1] and Rosenfeld and Kak's omnidirectional tracking algorithm [4]. Davis pointed out that the critical components in detecting edges sequentially are the choice of a good starting point, the dependence structure, and the terminating criterion. Rosenfeld and Kak's omnidirectional tracking algorithm for curve following scans the picture systematically and looks for points that meet a detection criterion. When such a point is found, a tracking criterion is applied to the neighborhood of that point to determine a next point. If no such point can be found, tracking of that branch terminates. The algorithm ends when the systematic scan is completed. In our decision strategy, the picture is..scanned row by row. Our criterion for a good starting point is for the edge strength value to be above a preset threshold. Two criteria that use both the strength value and the edge direction for determining the next edge point have been considered. We have implemented the decision strategy using a tracing algorithm that is similar to the one described by Graham [5]. The algorithm has two modes: a search mode that searches for a contour start point and a trace mode that traces an edge segment. The algorithm starts in the search mode. Starting at the upper left corner, it searches for a pixel with m(i,j) above a preset contour

7 start threshold and which is not already an edge point. This contour start point is classified as an edge point, and the algorithm enters the trace mode and begins to trace an edge segment. -- - Consider a 3 x 3 window centered on an edge point that has just been found. If the edge direction at the center pixel points in the direction d ( d e 0,1,...,7{ ) then only the 3 neighbors corresponding to (d - 1), d, and (d + 1) (mod 8) are considered as candidates for the next point on the edge. Two criteria for determining the next point have been considered: one emphasizing the edge strength value and the other emphasizing the edge direction value. Both of them will be discussed in detail below. After determining the next edge point, the window is moved to that pixel and another edge point is searched for. If no next point can be found, the edge segment is terminated. The newly found contour is merged with any previously found contours if they are connected to each other. If the contour length is below a minimum value, the contour is rejected. The algorithm then returns to the search mode at the neighbor of the original contour start point to search for the next start point. The algorithm terminates when the lower right corner is reached. 3.1.1. Strength Based Next Point Criterion The strength based criterion checks a connectivity condition first. The connectivity condition is satisfied if d -1 < dk d +1 (mod 8) (8) where dk = edge direction of the neighbor under consideration d = edge direction of center pixel In this case, the edge direction values would have already been quantized to be one of eight values as discussed above. Among those pixels that meet this

8 connectivity condition, the next point is chosen to be candidate i if rnL > ml for all j i and mn > edge point threshold. (9) where mi, mj are strength values of candidates i and j. 3.1.2. Direction Based Next Point Criterion The direction based criterion first rejects those candidates with strength below an edge point threshold. The connectivity condition for this criterion is based on previous work by Kitchen and Rosenfeld [6]. Let a(at) = 1- - (10) where a,gi are angles with values between 0 and 2rr then rk = a(d,dk)xa(.k,d) (11) where d4 = edge direction of neighbor k d = edge direction of the center pixel. In this case, the edge direction values range from 0 to 27i. rk is computed for the three neighbors lying to the left of the gradient. The next point is chosen to be candidate i if ri > r for all jsi and ri > continuity threshold. (12) 3.2. Threshold Selection Three different methods for thresholding the strength values discussed in Sections 3.1.1 and 3.1.2 have been considered.

9 (1) The strength value found by the spatial operators can be thresholded by a constant. This is computationally efficient. However, when the illumination is-not even throughout-the picture, edges in areas-with poor lighting tend to be missed. (2) In the case of template matching operators, a locally adaptive threshold [2] is defined for every point (i,j) as: LAT(i) = ma (WX) (13) LA T -j ) =(13) (MoX) where Wi's are the template masks. and Mo is the lowpass mask: 1 2 1 MO = ( 2 4 (14) This LAT value can be used as the strength value. (3) In the case of gradient operators, the strength value can be modified as f. (?, ) =(G. X)+(GYX)2 (15) (X,X) This is the Frei-Chen classification rule discussed in [3]. 3.3. Edge Detectors Implemented From the above discussion, different edge detectors can be developed using various combinations of spatial operators, next-point criteria, and threshold selection methods. The spatial operators, which can be gradient masks or template masks, are used to generate an edge strength map and an edge direction map. The edge strength map is then scanned row-by-row from the top left corner for a contour start point that has strength value above a contour start threshold and is not already an edge point. This start point is then classified as

10 an edge point. Once we are on an edge segment, either of the the two next point criteria that use both strength and direction information can be used to search for the next point on the contour. If-no next point-can be found-, the contour-is terminated and it is merged with any previously found contours that are connected to it. If a contour is too short, it is rejected. After tracing a contour, the edge detector returns to look for another contour start point until it reaches the lower right corner of the image. Five edge detectors have been implemented: (1) isotropic gradient masks, the strength based next-point criterion, and fixed threshold. (2) isotropic gradient masks, the strength based next-point criterion, and Frei-Chen classification rule. (3) 3-level template masks, the strength based next-point criterion, and fixed threshold. (4) 3-level template masks, the strength based next-point criterion, and locally adaptive thresholds. (5) isotropic gradient masks, the direction based next-point criterion, and fixed threshold. 4. Performance The desirable features of the output of an edge detector include accuracy of edge location, good continuation and thinness of edge segments. The new edge detectors that were presented above were evaluated using Pratt's Figure of Merit [7] and Kitchen and Rosenfeld's Measure [6] (see below). Also included in the tests for comparison are: (1) Sobel operator

11 (2) Isotropic gradient operator (3) Frei-Chen operator (4) 3-level template matching operator (5) 3-level template matching operator with Locally-Adaptive Thresholds The above operators do not use direction information. Robinson [2] proposed an edge detection algorithm that uses spatial operators to enhance a picture to form a magnitude map and an edge direction map. Both magnitude and direction value are then used to decide if an pixel is an edge point. The following operators are implemented with the Robinson's connectivity test and are included in our tests: (6) Sobel operator with Robinson's connectivity test (7) Isotropic gradient operator with Robinson's connectivity test (8) Frei-Chen operator with Robinson's connectivity test (9) 3-level template matching operator with Robinson's connectivity test (10) 3-level template matching operator with Locally-Adaptive Thresholds and Robinson's connectivity test Independent Gaussian noise was added to test images (discussed below) at signal to noise ratios of 100, 50, 20, 10, 5 and 2. Following Pratt's notation [7], the signal to noise ratio SNR is defined as: SNR = - (16) where h is the edge height and a is the standard deviation of the noise..Salt-and-pepper noise was added to test images at bit error probabilities of 10-5, 10-4, 10-3 and 10-2. The bit error probability is the probability that a particular bit of the image is toggled.

12 4.1. Pratt's Figure of Merit Pratt's Figure of Merit assesses edge location accuracy by the displacement of detected edge points from an ideal edge. The Figure of Merit is defined by: R =1 A (17) in=1 1+adi2 where In = max(fI,.A) If = number of ideal edge points IA = number of actual edge points d = displacement of actual edge points from ideal edge a = scaling constant. For our tests, we choose a =. 9 The test image used was 128 x 128 pixels and consisted of a left panel with gray level 115, a right panel with gray level 140, and a single central column of gray level 127. Figure 4a contains plots of the measure vs. SNR and Figure 4b contains plots of the measure vs. Bit Error Probability. In both of these plots, the thresholds for all operators were kept constant for all noise levels. The thresholds for the operators (1) to (10) of Section 4 were chosen so that the Figure of Merit is maximized at the lowest noise level. This is more realistic because in real life we rarely have control over the degradation of the picture that we are processing. 4.2. Kitchen and Rosenfeld's Measure This measure is based on the continuation and thinness of the edges. The measure E is defined by E = yC + (1 - 7)T (18)

13 where C is the continuation measure, T is the thinness measure and 7 is the scaling constant. We have chosen - to be 0.8 in our tests. T is the fraction of the remaining six pixels of the neighborhood that are not edge points. The continuation measure C is the average of the best continuation at the left and at the right. The best continuation at the left is the maximum value of the function: k I a (d,dj)xa( -,d + -2) if neighbor k is an edge point9) L (k) = 4 2 (19) L(k) = o0 otherwise. where d4 and d are directions returned from the spatial operators for the 3 neighbors to the left of the center pixel relative to the directions returned from the spatial operators, and a(a,3) is as defined in Equation 8. Similarly, the best continuation at the right is the maximum value of a(dd:)x a (-T,d - ) if neighbor k is an edge point( c/ 4 2 (20) R (k) 0 otherwise. where d4 and d are directions returned from the spatial operators for the 3 neighbors to the right of the center pixel 'relative to the directions returned from the spatial operators. The test image used was a "rings" image similar to the one used by Kitchen and Rosenfeld [6]. This image consisted of concentric rings with alternate pixel values of 115 and 140. The image was generated as a 512 x 512 image and then reduced to 128 x 128 pixels by replacing 4 x 4 blocks with the average pixel value of the block. This test image provides edges at all possible orientations. Figure 5a contains plots of the measure vs. SNR and Figure 5b contains plots of the measure vs. Bit Error Probability. In all of these plots, the thresholds for all

14 operators were kept constant for all noise levels, and thresholds were chosen as in Section 4.1. 5. Discussion The edge detectors implemented have been applied to real-world images. The results are shown in Figure 6 and compared to the Sobel operator and the Frei-Chen operator. While all operators can detect most of the edge points, the new edge detectors produce thin and connected edges. The results of the tests in Section 4 provides a quantitative measurement of the capabilities of various operators to produce well-formed edges. The plots in Figure 4 show the difference in performance between the operators with and those without edge direction information can be quite distinct for all noise levels. Peli and Malah [8] have pointed out that Pratt's Figure of Merit does not always give sufficient information about the resulting edge pictures, especially when the edges are broken. While the Kitchen-Rosenfeld Measure supplements this by measuring the continuation and thinness of the resulting edges, other problems can arise. When more edge points than ideal edge points were detected, Pratt's Figure of Merit (Equation (17)) can be viewed as the average of the weighted deviation values of the actual edge points. Since false edge points closer to the ideal edge have higher weights than those farther away, eliminating those false edge points with higher weights can result in a decrease of Pratt's Figure of Merit. This is especially significant when the false edge points are'not evenly distributed across the image, such as in the form of artifact segments. A similar phenomenon occurs when fewer edge points than ideal edge points were detected. The normalization factor in Equation (17) would then be the number of ideal edge points to penalize the missed edge points. In this case, eliminating any false edge points located anywhere in the image will lower Pratt's Figure of Merit, since less terms are included in the summation in

15 Equation (17), while the normalization factor is kept constant. It should also be noted that the weighted deviation approach is effective and, indeed, important for penalizing smeared and offset edges. However, when a 3x3 edge operator is applied to a ramp edge (Figure 7), any edge points detected outside a 3-pixel wide strip centered at the ideal edge point are caused by noise. Hence, it is not always desirable to weight false edge points when evaluating 3x3 operator-based detectors. Kitchen and Rosenfeld's Measure provides information about the thinness and good continuation of edge segments. The plots in Figure 5 show that the new operators perform better at all noise levels. However, the separation between the performance of operators that use contour tracing and that of operators that do not is not so marked for the Kitchen and Rosenfeld's Measure in the presence of salt-and-pepper noise. This is because, as pointed out by Kitchen and Rosenfeld[6], isolated noise points tend to produce locally well formed edge segments which receive favorable scores with the KitchenRosenfeld Measure. Moreover, notice that this measure does not have a wide range over different noise levels. This is partly due to the fact that while the Ideal Edge Point Figure 7. Ideal Ramp Edge.

17 accordingly to minimize unwanted background noise and to produce well-formed edges. 6. References [1] Davis, L., "A Survey of Edge Detection Techniques", Computer Graphics and Image Processing, Vol. 4, pp. 248-270, 1975. [2] Robinson, G., "Edge Detection by Compass Gradient Masks", Computer Graphics and Image Processing. Vol. 6, pp. 492-501, 1977. [3] Frei, W. and C. Chen, "Fast Boundary Detection: A Generalization and a new Algorithm", IEEE Transactions on Computers, pp. 988-998, Oct. 1977. [4] Rosenfeld, A. and A. Kak, Digital Picture Processing, Vol. 2, Second Edition, New York: Academic Press, 1982, pp. 133-135. [5] Graham, D. N., "Image Transmissions by Two-Dimensional Contour Coding", Proceedings of IEEE, Vol. 55, No. 3, pp. 336-347, March 1967. [6] Kitchen, L. and A. Rosenfeld, "Edge Evaluation Using Local Edge Coherence", IEEE Transactions on System, Man and Cybernetics, Vol. SMC-11, No. 9, pp. 597-605, Sept. 1981. [7] Pratt, W., Digital Image Processing, New York: Wiley, 1978, pp. 495-499. [8] Peli, T. and D. Malah, "A Study of Edge Detection Algorithms", Computer Graphics and Image Processing, Vol. 20, pp. 1-21, 1982.

18 b.OO- - -- r4 375 - 2 - r I 0/ / L.laso- t2So0.00 - -........,,. ~ -....-., 2 5 to 20 too Siqnal Lo noise ratio.- ---- -- Gradien;t maskss' Srernqh based criterlon, Fixed;hreshold - -- Sobel mfask s RFobnson' s Connect i1 xq es; -- — Sobel operacor Figure 4a. (i) Pratt's Figure of Merit vs. Signal to Noise Ratio.

19 i, O0f....._.__.._ -- F15J - LA. ~ILI X ^/ b.500- / / L / /,37 // - /J,250 - // 0.00. —........-......, 2. 5 tO 20 20 tOO Siqnal t.o notse racto.Gradlenc miasks. Strernqh based crtterlon. Ft ced threshold..... -- -Grd"adzert asks. IRobt:nson's conrict, trl t est -.. - - Isog optc qv i ad entc aslks Figure 4a, (ii) Pratt's Figure of Merit vs. Signal to Noise Ratio.

20, 500 C / // tAs c, /..3 5- ' Slqnal Lo noise racto..... Cradieln a ' *Sremqth based criteritot Fret-C!'n rule -F:re, t-Chen Gr"adtent Subspace ob. tson's Cornn~etit t, rest.....'Fret -Chen Gradtenr Subspace.Fret-Cen Ede ubace Figure 4a. (iii) Pratt's Figure of Merit s. Signal to Noise Ratio. ta ---,,, Frei-ChenZ" Edq - 9bspace Figure 4a. (iu) Pratt's Figure of Merit vs. Signal to Noise Ratio.

21 1.00 0 e~5/ / v 75' / /.625 / rj:.500- / / L,.=j - / 0.00 0.00 -........,..... -,-...., 2 5 t O 20 0 100 Siqnal.to noise racto - 3-lewiel masks. Scrench based crtyer Oin. F xced tlhreshold -- -3-le ewl masks. Robinson's Connectivi tq test - - -3-level Template Matchinq Operacors Figure 4a. (iv) Pratt's Figure of Merit vs. Signal to Noise Ratio.

22 1.00" - ---.875 / / 7 50 oL ci.625 - 0 / LL O /,375 -.5aso - /,. /las - t25 - 0.00 2 5 t1 20 0 100t Sinal to noise racto *- 3-lel masks. Screqh based criterion. LAT's... — 3 —le-el maseks itthi LAT. Robtnson's ConnectItvtI test —...- -- 3-tleel mnasks ut h Local tJ Adapclve Thresholds Figure 4a. (v) Pratt's Figure of Merit vs. Signal to Noise Ratio.

23 875-.625 - y /L~iO //.500- /. / f.2-500/ L.t2 0.00o --....,........ 2 5 tO 20 10oo Signal to noise ratio Gradient mesks, Directron based criterton. Flted threshold -- - " — Gradienc "rasks. Robtisor's Conrlnew ivtir cost --- -- Isocropic Gradient Masks Figure 4a. (vi) Pratt's Figure of Merit vs. Signal to Noise Ratio.

24 t.00 \1 14,. 751 - \\ \ *625- \ \ \ 0! L, 375 - Li 000.. tO-" tO - t 03 II Bic Error ProbabtliCL — Gradierni masks. Swenrgh based cr'ierion. Fa<ced xhreshold -— Sobel mnasks. Robinson' s Conrnect iitq t est..... ----Sobel oper ator 0o-e Figure 4b. (i) Pratt's Figure of Merit vs. Bit Error Probability

25 t.00 N 750l E \ N \.6 \ \ \ O \ \ 0.5001.500 LL.375 - 0.00. ' I | tO"0 I 0r --- Bit tEro P tObab -- - Bit Error Probabse ll, d Gradlen mnasks, Swrenqg sh based criterion. F ixed hrelshold.. — -Gradien n masks. Robinson's conneci tivtr t es ---. - -Isoropic qradten mnasks Figure 4b. (ii) Pratt's Figure of Merit vs. Bit Error Probability

26 S,, " 750 \ \ 625 \ \ 0 \..25-\ - t2" \.00 -. tO' tO tO -3 to Bic Error Probabtlitq Orad-ern *asks, Sprenq.h based crterjorn. Frem —Chen rUle -Fret-hen Gradient SubsDace. RobtnonV s ConnecLtvtj Lest. —..Frei-Chen Gradt er Subspace. ---.......Fr-t-Ch-n Edq. Subs-pac Figure 4b. (iii) Pratt's Figure of Merit vs. Bit Error Probability

27 1.00 -- ___. - Qs O Cr6 \ \ \. 25 \.500 \?.3? \ \ 0.00. -.,..........,. to" to' to tO Bi t Error Probab t 1 liLq,3-level masks, Srenq;h based crtGerion, F-ted \hrehold -3-l eie l masks. Robinson' s Connec ivt c~ n.est.. ---- 3 -Ieel I Teplat e Macch nq Opera~ors Figure 4b. (iv) Pratt's Figure of Merit vs. Bit Error Probability

28 1'00 -. 87 - Ira. 0a n3 nr L., 0 - *6a5 -.500 - N.250.125 0.00 tO - to.. E r... rb. I. t10- t-3 - Bit Error Probabtllcg l- 9-level masks. Strenqch based crixerion. LAT's -.- — 3-level masks wich LAT. Robinson's Connec;1vtiJ; es -.-.-3-leel masks tht Local lq adaptive Thresholds Figure 4b. (v) Pratt's Figure of Merit vs. Bit Error Probability

29 1.00 i.8o - 7500. 62.5 -\\ i, O.500 CI:. 50a - \ \ \.3 00 \ \ r-e \ BcIr Error Probabtl c Gradler masks. Dtrecoron based crtiter on. Ficed threshotd - 7 - -Gradiemnt. asks. R obinsorn's Cornmect L t q tes t.- --- sotropic Grad ernr Masks Figure 4b. (vi) Pratt's Figure of Merit vs. Bit Error Probability

30 a' 3 VI r Ul co a.ct o 0 C (a Lj YV t 00.87'5,625.500 - ~~wrcl-Y~~* /.250,125 0,00 2 - 5 to 20 Siqnal to noise racto 50o100 — Gradienr. masks. ScrPnqCh based criterion. --- ---- -Sobel mnasks. Robinson s Connecktyinq cest - -.-. Sobel oper ator Fie td thr;shold Figure 5a. (i) Kitchen and Rosenfeld's Measure vs. Signal to Noise Ratio.

31 t.00 -.875 - sL VI '3 C 0 or c, C U M/ /.500 -.375 - t25 - 0.00 i. — - -- 2..... I 5 1t 20 Siqnal to noise racto ) 0100 -Gradient mnasks. Screnqch based criteron. Fixed threshold -- - -Gradien masks. Robinsor's connecn v iq cesc -i -. — I sotiropt c qradternt rasks Figure 5a. (ii) Kitchen and Rosenfeld's Measure vs. Signal to Noise Ratio,

t.00 -.875 32 Qj!. 'J cl CL Vo IJ 10 C "1 M.150 -.625 - 500 -.375 -.t25 - 0.00.... I 5D too 2 5 t10 0 Siqnal.o notse racto Gradlern masks. Scrpnqch based crterton. Frpt-Chen rule -- - --— Frei-Chen Gradiernt subspace. Robtnson's Connecwtitvly - esz ---- -- ret-Chen Gradient Subspace Figure 5a. (iii) Kitchen and Rosenfeld's Measure vs. Signal to Noise Ratio.

33 1.00 -.875 - E nA I C C. C C c xeolp 750.500 -.375 -.oZ50 - 0.00 5 1t 20 Siqnal to noise racio 0to100 -3-level masks. Srrenqch based crterion. Flted threshold --- -- -— 3-le'el masks. Robinson's Conne~c~ tzt &est, - - --- 3-leel Template Matlchirq Operators Figure 5a. (iv) Kitchen and Rosenfeld's Measure vs. Signal to Noise Ratio.

34.00 ~.875 - ll —, VI C 03 VI C C.L cJ Ua.-a /.625 -.500 -.250 -, t25 - 0 00 2 5 1t Siqnal to noise 2r rac to w t0oo -- - 3-leivel masks. Sirenqih based criterion. LAT's - 3-l1evel masks itch LAT. Robinson's CornecrivitJl est -- -- — 3-level masks uich Local l Adaotuve Thresholds Figure 5a. (v) Kitchen and Rosenfeld's Measure vs. Signal to Noise Ratio.

35 tOO -.875 ~ rj.V -C U1 VI c CL 2O r u m-,orpPIT.625 -.500 -.375-.250 - 0.00 2 5 1t 20 Siqnal to noise racio 5t 100 Gradlent masks. Dtreclion based crlerion. Ftled chreshold - --- — Gradienrt asks. Robinson's Connect lvitq es. ---- -— IsotroPc Gradient Masks Figure 5a. (vi) Kitchen and Rosenfeld's Measure vs. Signal to Noise Ratio.

36 t.00 -.875 - L 1 =4 -%- -— %s,~Ic~~~-A ' -3K fj E (. c u C 0 c, VA 750 '.500 - 4 '11%% -.... I-V T I - -... r 0.00 L I I I. I w ~ m m" 'W F t1o' ~ I...... o10- 10t Bit Error Probabtll l ii 0-~ -Gradiernr masks. Screnqth based criterlon. Fixed threshold --- — Sobel masks, Robinson's Connecrivlq ' es; - - - - -Sobel oper acoor Figure 5b. (i) Kitchen and Rosenfeld's Measure vs. Bit Error Probability.

37 1.00 ".875 zo P -- --.. 11~ -- - -, a, d3 U1 VI c CI ao a Of ci. 65.500 ~.250 -.125 - 0.00 - tO - tO- to -3 Bit Error Probabillc q t10o IGradlen ri masks. Strenq h based criterion. Fixed zhreeshold -- -OGiradlenm 'nmasks5 Robinson's connec; vtl;q es$ - - - Isocropic qradcerlc masks Figure 5b. (ii) Kitchen and Rosenfeld's Measure vs. Bit Error Probability.

38 t 00 -.875 - I re - ~~~ I ~~~ -CL;I~~~r~~I~ —, 4 C L N%. - 3K~~~~~11% "I-% qat C U, C C. U, U c <b...750 -,500 "I-, 'N* I -17... I... I I.250 0 00 - -- I ' to-' ' '. I.......I to-1 tOBi1 Error ProbabLl.Lq II o-e Graduenl masks. Srenrqch based criterion. Fret-Chen rule.-..- -Fre —Chren Gradiernt subspace. RotArbsn's Conne't.l.Jit. test ---—.-Fret-Chen Gradierm Subspace Figure 5b. (iii) Kitchen and Rosenfeld's Measure vs. Bit Error Probability.

39 t1.00.875 - -- -- s b.c I- — %. -— N N a, S. E' VI Q6 C or (1( C u ~-~ V.500 -,250 ~ 0.00 t0-', - ~ -I-...... I 10c 10 ' Bic Error ProbabllicJ O -e to E 9-I leJeel masks. Strrenqch based criterton. Fisxed threshold -- - -- — 3-level masks. Robinson's Connectiliq j,es; - - - - -3-leivel Temnptate Matchrigq Operators Figure 5b. (iv) Kitchen and Rosenfeld's Measure vs. Bit Error Probability.

40 tO00 O Il I a, r3 VI c a, 0 4: ca ro U '-a r S- ~ ~ _< - "'I. 750 -.625 -.500 -.375 -.250 -.00125 0,00 - 1 4 - -. - -......... I- -.... I. I I — ' ' ~ ' ~ - * I r tO 1 tO 0 10to Bic Error Probab lll L tO - - - - - - - I - ----..3-level masks. Screrqch based crutr ion. LAT'S - ---- -- e3-le.el masks with LAtT. Robinson's Conriectzrtc estc ------- 3-le.el emasks with Locall t Adapttve Thresholds Figure 5b. (v) Kitchen and Rosenfeld's Measure vs. Bit Error Probability.

41 1.00 -,...0" - - I ---,- — )r4. N%. c. *3 vm E t, fAc a, Vi -a.c )iJ 750 -.625 -.125 - 0.00 t10o t10- 103 Bic Error Probabil1it 10 - - Gradiernc nasks. Dlreection based criterion. Fited chreshold - - - Gradlen; mnasks, Roblnson's Connec; ivijq;es; -.. ---- Tsootoptc Graderenc Mlasks Figure 5b. (vi) Kitchen and Rosenfeld's Measure vs. Bit Error Probability.

42 Figure 6(a). Upper Left: Upper Right: Lower Left: Lower Right: Examples of applying various edge operators. Original image. Output from Edge detector (1) in Section 3.3. Output from Frei-Chen operator. Output from Sobel operator.

43 Figure 6(a). Examples of applying various edge operators. Upper Left: Output from Edge detector (2) in Section 3.3. Upper Right: Output from Edge detector (4) in Section 3.3. Lower Left: Output from Edge detector (5) in Section 3.3. Lower Right: Output from Edge detector (3) in Section 3.3.

44 Figure 6(b). Upper Left: Upper Right: Lower Left: Lower Right: Examples of applying various edge operators. Original image. Output from Edge detector (1) in Section 3.3. Output from Frei-Chen operator. Output from Sobel operator.

45 Figure 6(b). Examples of applying various edge operators. Upper Left: Original image. Upper Right: Output from Edge detector (1) in Section 3.3. Lower Left: Output from Edge detector (5) in Section 3.3. Lower Right: Output from Edge detector (3) in Section 3.3.

46 1.00 "3 (D 0 r *0 C c c Li is O C C c U i-> U/.85.500 L %" A.- _ * -W t25 - 0.00. - -... I. II — 2 S Inal Siqnal tO 20 to noise racto 5 to00 -- 3-level Template Macchtng Operators Isotropic Gradient. Operator Figure 8a. Kitchen and Rosenfeld's Continuation Measure vs. Signal-to-noise Ratio for an edge picture with all pixels classified as edge pixels.

47 t.00 - o r-J!h. c 4I r-a,3 C 0 c a) T3 (1. C c U 0 K.875 1 -- -~ --- -i I-_..750.500 -.375.250 0.00 t0 — to t10 o - tO -' Bic Error ProbabtlicL 3-level Template Matching Operacors TIsotropic Gradtent Operator Figure 8b. Kitchen and Rosenfeld's Continuation Measure vs. Bit Error Probability for an edge picture with all pixels classified as edge pixels. UNIVERSITY OF MICHIGAN I3 9015 02844 0702ll Illl III I 3 9015 02844 0702