Image Filtering, Edge Detection, Edge Tracing Using Fuzzy Reasoning

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, NO. 5, MAY 1996

48 1

Image Filtering, Edge Detection, and Edge Tracing Using Fuzzy Reasoning Todd Law, Student Member, /€€E, Hidenori Itoh, and Hirohisa Seki, Member, /€€E Abstract-We characterize the problem of detecting edges in images as a fuzzy reasoning problem. The edge detection problem is divided into three staged: filtering, detection, and tracing. Images are filtered by applying fuzzy reasoning based on local pixel characteristics to control the degree of Gaussian smoothing. Filtered images are then subjected to a simple edge detection algorithm which evaluates the edge fuzzy membership value for each pixel, based on local image characteristics. Finally, pixels having high edge membership are traced and assembled into structures, again using fuzzy reasoning to guide the tracing process. The filtering, detection, and tracing algorithms are tested on several test images. Comparisori is made with a standard edge detection technique. Index Terms-Fuzzy reasoning, filtering, edge detection, tracing, joins.

1 INTRODUCTION

I

of real scenes very frequently contain data which is incomplete and ambiguous. In particular, the problem of determining what is and what is not an edge in an image is confounded by the fact that edges are often partially hidden (incomplete) or distorted (ambiguous) by various effects such as uneven lighting. Furthermore, images frequently contain data with edge-like characteristics, such as high gradient, but a confident classification of such data can best be resolved when high-level constraints are imposed on the interpretation of an image. Human beings are able to make some sense of even unfamiliar objects, which necessarily have an imperfect high level representation. We suggest that this is possible because our visual systems have built up much experience viewing different objects under a wide variety of conditions. For edge detection, it appears that the eye-brain is familiar with different types of edges, and how these edges appear under different conditions. To perceive unfamiliar objects, or to perceive familiar objects in imperfect images, it appears that humans are applying heuristic algorithms to understand such images. Although these algorithms may be "implemented in the wetware of our visual systems, we believe that it is possible to characterize an equivalent process systematically.We submit that fuzzy reasoning is a suitable framework for expressing heuristic processes applied to incomplete and imperfect data. To extract rules for detecting edges, it is helpful to have some familiarity with different kinds of edges in order to construct a suitable characterization. Typically, researchers have characterized edges as a step function or as a slope between two flat regions (see Fig. 1). MAGES

The authors are with the ltoh Laboratory, Department of Artificial Intelligence and Computer Science, Nagoya Institute of Technology, Gokiso-cho, Showa-ku, Nagoya 466, Japan. E-mail: [email protected]. Manuscript received June 27,1994; revised Feb. 5,1996. Recommended for acceptance by K. Boyer. For information on obtaining reprints of this article, please send e-mail to: [email protected], and reference IEEECS Log Number P96014. e

Fig. 1. Some common naive idealizations of edges.

In reality however, edges may deviate from these cases in any number of manners. Fig. 2 shows some examples of how (continuous) edges may manifest themselves in the real world. Edges may be

1) gradual in transition, 2) between areas of non-uniform intensity, 3) between areas of similar intensity, 4) noisy, or 5) any combination of these problems. 6) If these deviations from the ideal are severe enough, edge data may become nearly indistinguishable from noise. Furthermore, effective edge detection must go beyond local shape characteristics to reflect structural constraints. Edges appear not only as a local phenomenon, but as part of larger structures which can also be characterized heuristically. Again, we argue that it is possible to express structural constraints heuristically in a systematic way. We employ fuzzy reasoning for these tasks because the nature of the data is indeterminate at a low-level stage of processing. Fuzzy reasoning, as outlined by Zadeh [30], with the power to model and respond usefully to approximate situations, is ideally suited to these problems.

0162-8828/96$05.00 01996 IEEE

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

482

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL 18, NO 5, MAY 1996

Fig. 2. Cross-sections of some nonideal (continuous) edges.

In the following sections, we attempt to characterize real edges, then develop algorithms based on fuzzy reasoning to enhance edges (filtering), detect edge points, and assemble edge points into edge structures.

2 FUZZY GAUSSIAN FILTERING Image blurring/sharpening is a common technique in the edge detection process, with the objective of removing noise and enhancing edges Furthermore, good filtering preserves shape for high curvature edge structures such as at corners and T-junctions Typical algorithms adjust the value of each pixel according to a weighted average of the pixels in a surrounding neighborhood For example, Graham [7] used an algorithm which blurred images across edges but not along edges, in order to preserve edge information Recent versions of such filtering are by Perona and Malik [21] who formulate smoothing as a diffusion process, and Nitzberg et a1 [18]who extend this idea to include preservation of cornerness (high curvature edges) For any algorithm, it is difficult to know where to blur and where to sharpen without some idea of where edges may be located Overblurring can eliminate edge information, while oversharpening can produce edges in unexpected places Many algorithms have arbitrary parameters, which must be judiciously selected for a given image, and may perform poorly with a different image Consequently, we seek a blurring/sharpening algorithm which is immune to the particular information content in an image The algorithm should reduce noise as much as possible, while not assuming the existence of edges, and simultaneously preserving dominant shape Below, we present a technique for blurring and sharpening images with these objectives in mind Our technique is a form of controllable Gaussian filtering, where the size, shape, and direction of the filter are selected to achieve the goals of reducing noise while bringing out edges This technique, which we refer to as fuzzy Gaussian filtering is documented in [13]

gradient in a local region und a pixel Due to the presence of noise in an image, s usually quite difficult to accurately determine the direction of the gradient. Simply choosing the direction of greatest ascent is unsatisfactory, because such a method is vulnerable to minute noise variations, which have a particularly strong effect in small-scale regions of a few pixels Furthermore, this method is also unsatisfactory because there may be several directions with the same gradient. Consequently, we offer a new notion of gradient, which is determined by the characteristics of two regions one either side of a dividing line (see Fig. 3) in the digitized image. First, to ignore noise effects as much as possible, we consider the average value of pixels in each region, ignoring pixels directly on the dividing line. The difference in the two averages gives us an idea of steepness between the two regions. Second, to settle the issue of several directions possibly having the same steepness between their respective regions, we also measure the symmetry of both regions across the line of the candidate gradient In Fig. 3, it can be seen that choosing a direction with high reflective symmetry means choosing the tangent to the surface of an edge. In other words, we claim that the direction of significant gradient is a measure of high steepness between regions, and high reflective symmetry across the line of gradient. We express this using fuzzy rules, as expressed in Table 1 The exact method of fuzzy calculation is specified in Appendix A. The method of symmetry evaluation is defined precisely in Section 3.1. Using this method to select the gradient direction, the gradient magnitude is simply the difference in the average values of pixels on either side of the dividing line. direction with highest degree of gradienl magnitude and symmetry is selected

plane In direction of consideration

Fig 3. Evaluating gradient.

TABLE 1 DETERMINING GRADIENT WITH FUZZY RULES radient

2.1 Determining Gradient

Before we can select a suitable filter shape, it is necessary to have an accurate idea of the direction and magnitude of the

small small large

medium

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

LAW ET AL.: IMAGE FILTERING, EDGE DETECTION, AND EDGE TRACING U$;ING FUZZY REASONING

483

2.2 Controllable Gaussian Filtering

1

(3)

Regular Gaussian filtering can be expressed as the convolution of the original image I with a Gaussian shaped kernel W

P=I* W

Rotating W to the angle of the gradient, we can define a (1) new coordinate axis system U and v, with W separated as

where W has the (discrete) form

oeffectively determinesthe breadth of W, and the value of W is constant for a given radius from the center of the function. Controllable Gaussian filtering permits the size of the filter, dictated by 0, and the shape of the filter, which we refer to as squashing (see Section 2.3.11, to be determined dynamically according to local data characteristics.

2.3 Filter Dimensions Controlling the value of o effectively determines the degree of smoothing of the image. We wish to smooth the pixel in consideration with pixels having similar values, i.e., in the same region, but must avoid smoothing with pixels of greatly differing values which may belong to different regions. In other words, we wish to smooth away small distortions caused by noise, but preserve dominant shape, i.e. edges, locally. Allowing o to fluctuate over a useful range (set between 0.1 and 5.25), we fixed the size of our filter to 7 x 7 pixels. However, we must recognize that pixels don’t always lie in even approximately uniform regions, but are often situated in regions of changing intensity, due to shape, lighting conditions, or other optical effects. Therefore, we loosen the restriction of smoothing with similarly valued pixels to a restriction of smoothing with pixels having similar dope. Consequently, we choose to make our filter directional to emphasize smoothing across the dominant slope and deemphasize along the dominant gradient. We do this by deforming the filter, or squashing, as explained in the next subsection. Our algorithm considers concentric square regions around the pixel in question, and measures the gradient for all opposing pairs of pixels on the perimeter square. This gradient measurement technique is illustrated in Fig. 3.

2.3.I Filter Shape Squashing Within the selected region, we choose to shape the Gaussian smoothing function according to local data. If the data has meaningful shape information in the direction of the gradient (i.e., edge or slope point), then it is preferable to smooth only perpendicular to the gradient so as to preserve that information. Our Gaussian smoothing function should be squashed in the direction of the gradient, so that smoothing occurs along the edge or slope, not across it. If the data has meaningful shape information both in the direction of the gradient, and perpendicular to the gradient (i.e., corner or T-junction), then it is preferable to tightly limit smoothing in both directions; the Gaussian function should be squashed in both in the direction of the gradient and perpendicular to the gradient. Rewriting W in polar coordinates,

where o, and o, control the squashing in the directions along and across the edge respectively. We control the two os using fuzzy control based on local shape information. We determine the nature of the shape in the local area from two parameters: gradient magnitude, and straightness. These two parameters are determined as follows. As mentioned above, the gradient magnitude is determined by the difference in average values of pixels on either side of a dividing line. The straightness is determined by comparing pixels translated along the direction of the edge. Similar to the determining of symmetry above, we expect that a pixel translated in the direction of a straight edge will line up with a pixel of similar value. Performing such comparisons for each of the pixels lying within the evaluation region and then averaging the deviation from the expected values produces a statistical measure of straightness. The reason for choosing these two parameters are as follows. High gradient magnitude indicates the strong possibility of an edge, where smoothing along the edge should be done as much as possible, but smoothing across the edge should be limited to preserve this dominant shape. However, if the edge segment xs curved, sharply angled, or at a triple point, then smoothing along the edge will only smear meaningful edge information, and should also be limited. If the gradient magnitude is low, this indicates the region is flat, and smoothing should be in all directions as much as possible. To increase the degree of smoothing in a particular direction, we simply increase the value of o in that direction, where the U direction is along the edge, and the v direction is across the edge. The idea of controlling o, and o, according to the gradient magnitude and straightness are expressed as fuzzy rules in Table 2. The calcuation of the two os is determined according to the procedure in Appendix A.

4 TABLE 2 BLURRING INTENSITY

FUZZY RULESFOR

small small large lar e

high

large large small small

large large small lar e

In Table 2, o,and o,are relative values, with the final 0, and onbeing set in (direct) proportion to the filter dimension, the size of surrounding square area selected as explained above. 2.4 Experimental Evaluation We stated that the objective of our filter was to smooth in accordance with the particular information in an image. To evaluate success in achieving these objectives, we created

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

Image Fig. 4 Fig 5-1 Fig. 5-2 Fig. 5-3

added error per pixel SNR 10.0 15.5 10.0 15 5 10 0 15.5 10.0 15.5

error after Gauss SNR i m p per pixel 71 ( ~ = 0 5 ) 2.45

9.1( g = 04) 8 0 ( g =0 5) 7.9( 0 = 0.5)

0.58 1 40 I .40

having an average value of 10.0 to each pixel (Fig. 4b), cor-

(all

ues of

(a2J

0 and

evaluated the result (Fig. 4d) when compared

(a3)

error after fuzzy Gauss per pixel SNR imp. (dB) 2.40 0.61 2.64 2 78

(hi)

(b3)

10.4 84 91 85

(Cl)

(dl)

(C2)

(d2)

(c3)

Fig. 5. Smoothing images with high curvature e ages, (b) with random added noise, (c) fuzzy Ga best Gaussian smoothing

Fig 4 Smoothing edges of different sizes (a) original image, (b) with added noise, (c) smoothed by fuzzy Gauss, (d) smoothed by regular Gauss (o=0 5)

The table shows that om algorithm is ing noise consistently better than Gaussi optimized value of 0 Furthermore, as it ca Fig. 5, our filter clearly preserves sharpness ners and triple points, while providing smoothing elsewhere. Lastly, we applied our filter to a real i version of the well-known Lena image shown in Fig. 6 Since the image contains inherent noise, no comparison can be made to an idealized image. However, interesting regions of the image to see the ter Fig. 6a shows the original image, and three-dimensional close-up view of a 50 x 50 white-bordered square in Fig. 6a) Figs. 6c and same after fuzzy Gaussian filtering. Note that the triple point is left largely intact while flat regions are well

Second, we created three test images with high curvature and triple points to evaluate the response of our filter (similar images were used by Nitzberg et al. [18]to evaluate the same objective) Fig. 5 shows the images for these ex-

and the triple point is largely obscured.

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

485

LAW ET AL.: IMAGE FILTERING, EDGE DETECTION, AND EDGE TRACING USING FUZZY REASONING

gradient direction

'\\\,\yl

-\uniformity

evaluation regions

Fig. 7. Corners and triple points do not satisfy a refined edge definition

processing stage. To identify the degree of membership in the fuzzy sets edge, coyner, and triple, we examine several local shape parameters. We have found that gradient, symmetry, and straightness are useful parameters for this purpose. An ideal edge point along a straight segment will have high gradient, high reflective symmetry, and a high level of straightness in a local neighborhood of pixels. An ideal corner point will have high gradient, high reflective symmetry, but a low level of straightness in a local neighborhood of pixels. An ideal triple point will have high gradient, low symmetry, and a low level of straightness in a local neighborhood of pixels. These ideas are summarized in Table 4. TABLE 4 EDGEFUZZYMEMBERSHIP RULES Fig. 6. Filtering applied to Lena image (a) original image, (b) partial 3D view, (c) fuzzy filtered, (d) partial 3D view, (e) Gaussian filtered, IS = 0.4, (f) partial 3D view, (9) Gaussian filtered, IS=1 .O, (h) partial 3D view.

3 DETECTION 3.1 Edges, Corners, Triples The edge detection problem necessitates an adequate characterization of an edge. Intuitively an edge corresponds to significant intensity change in an image. This leads to attempts to detect edges by locating local gradient maxima. Unfortunately, because of various image phenomena, such as noise or distortion from various sources, this is a poor definition for meaningful edge detection. To effectively characterize edges, we require a more effective definition which identifies the various attributes of an edge. A more refined definition for an edge would appear to be a point of high gradient between two uniformly flat regions. Such a definition excludes many undesirable wouldbe edge-points (such as noise), but may also exclude several points which are important in edge structures. Namely, such points occur as sharp corners and triple points. In other words, corners and triple points may be points of high gradient, but may not satisfy the condition of uniform flatness on either side of the edge point, as shown in Fig. 7 (continuous case shown). Consequently, it is useful to detect corners and triple points separately from edge points which occur along relatively straight segments. Yet, at such an early stage of processing, we cannot definitely say whether a point is an edge, a corner, or a triple point. Therefore, we chose to assign fuzzy membership values to each pixel for each category. This allows us to delay confident identification until a later

gradient low low low low high high high high

symmetry low low high high low low high high

straight-

ness low high low high low high low high

high high

Gradient (magnitude) was determined as in the previous section, i.e., as a difference in averages of neighboring regions, with the gradient direction selected for the highest degree of edgeness, as defined in Section 2.1. Symmetry y was determined by reflecting pixels across a line in the direction of the gradient passing through the center pixel, and then comparing pixel values (see Fig. 8). Comparisons are made for all possible pixel pairs which fall in the region of evaluation, which is an n x n square. The sum total of differences for all pairs of compared values is then used as a measure of symmetry, y. To make y a positive value which increases with symmetry, we subtract it from the largest possible value. nl2

n12

(5) where plly is the value of the reflected pixel across the line in the direction of the gradient. Straightness t is defined similarily to symmetry, except that pixels are translated rather than reflected (see Fig. 9). Pixels are translated a random distance in the edge direction, within a limited range so as to fall within the region of evaluation. Again, comparisons are made for all possible

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

IEEE TRANSACTIONS

486

ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL 18, NO

pixel pairs which fall in the region of evaluation. The sum total of differences for all pairs of compared values is then used as a measure of straightness, t. To make t a positive value which increases with symmetry, we subtract it from the largest possible value.

5, MAY 1996

3.2 Experimentation We used the impleme relations of Table 4, gen represent edgeness, corne

(6) where plI, is the value of the pixel translated in the direction of the edge.

<\

reflected pixel

plane in direction of consideration

pixel

images. Fig. 20 shows the algor1 version of the well-known Lena i

\

/ region for symmetry evaluation dividing line for symmetry evaluation (=gradient direction)

Fig. 8. Determining symmetry

edgeness plane, (c) cornerness plane, (d) triple plane

ness enhanced for viewing purposes. In the e (Fig. lob), darker regions indicate higher e values. Similarly in the cornerness plane (Fi

in similarity between the two planes.

sible set of conditions results in high cornerness, c Fig 9. Determining straightness.

edgeiiess conditions are much more common. The corner-

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

LAW ET AL.: IMAGE FILTERING, EDGE DETECTION, AND EDGE TRACING USING FUZZY REASONING

ness plane is also less pronounced than the tripleness plane simply because corners tend to occur less frequently than triple points in real images.

487

between two segments at a triple point (one end point, one mid-point) which are illustrated in Fig. 12.

4 TRACING AND JOINS The algorithm of the previous sections produces four planes of information, one for each of edgeness, cornerness, tripleness, and direction. In this section, we present an algorithm for tracing edge segments and for assembling edge segments into larger structures based on the information in these four planes.

\

4.1 Tracing Edge Skeleton

. A'

triple point

To trace the basic outline of edge segments, we chose a standard text book algorithm, as outlined in 1261. Briefly, this algorithm examines the edgeness at each pixel, and the edgeness of two neighboring pixels on either side of the line in the direction of edge at that point. If the edgeness of the center pixel exceeds the edgeness of the two neigboring pixels, we mark the pixel as a crisp edge point. Neighbouring pixels are determined by the direction of the edge, as determined in the previous section. In a 3 x 3 block of pixels, there are only four possible pairs of (opposing) neigbouring pixels, which divide the unit circle into 45" sections, as shown in Fig. 11.

I

/I

1'.

I

Fig. 1 1 . Neighbor pixels assigned to 45' segments.

This algorithm only compares relative edgeness, which we use as an initial guide for finding edge traces. Furthermore, we remove very weak edge points by thresholding, in order to simplify the tracing process. After this detection process, we also remove any spurious patterns which can affect the tracing process, namely any T-, Y-, or cross-shaped patterns. Besides simplifyingthe tracing process, this cleaning of the edges also removes any triple points, which we choose to detect explicitly, and use for assembly of edge segments, as explained in the next section.

4.2 Joining Edge Segments Finally, we wish to assemble the traced edges into larger structures. Corners and triple points provide natural cues for such joinery, although we also consider joins which do not occur at corners and triple points. Altogether, we consider four possible kinds of joins, between two aligned segments (two end points) between two segments at a corner (two end points) between three segments at a triple point (three end points)

point

/

/'

(4

(C)

Fig. 12. Different kinds of joins: (a) two aligned edges, (b) two edges at a corner, (c) three edges at a triple point, (d) two edges at a triple point (mid-point join).

Of course, we cannot expect the ideal situation of perfect alignment between edge segments, corners, and triple points. Once again, fuzzy logic is well-suited for evaluating such approximate situations. As before, we outline the qualifications for a good join. A simple edge-to-edge join (Fig. 12a) requires edge segments to be well aligned, to have end points relatively close together, and to have pixels of at least medium edgeness in between. A corner join of two edges (Fig. 12b) requires edge segments to intersect close to a strong corner point, and to have end points relatively close together. A 3-edge triple join (Fig. 12c) requires three edge segments to intersect close together to a strong triple point, and to have end points relatively close together. A 2-edge triple join (Fig. 12d) requires the end point of one edge segment to be relatively close to any point on another edge segment, and to have a strong triple point between the end point and the edge segment. Once again, we express this fuzzy reasoning in tabular form (Tables 5 to 8). In Tables 5 to 8, alignment refers to the difference in angle between two end points, and proximity refers to the Euclidean distance between two end points.

I

TABLE 5 FUZZY RULESFOR ALIGNED-EDGE JOIN alignment proximity interim I joinedgeness I ness

I

low high

low

low

medium

high high high

medium medium

TABLE 6

FUZZY RULESFOR CPRNER JOIN intersection

low

high

high

low

low low

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL 18, NO 5, MAY 1996

TABLE 7 FUZZY RULESFOR %EDGE TRIPLE JOIN

I tripleness at intersection low low high high

proxlmlty

I ioinness

low high

I

low high

low low IOW high

In Fig. 14, the results of appl shown, where the parameter o is set to 1.5. in Fi Canny’s edge detector is appl (specifymg the fraction of pixel border one pixel in width has been adde

intersection low low high high

low high low high

I low low low high

We then implemented this fuzzy reasoning process in program form. To simplify the joining process, we only consider endpoints which were inside a common 10 x 10 square. In the case of 3-edge triple joins, such joins can be detected as a combination of any two of the 2-point joins (straight, corner, or 2-point triple join), and thus do not require a separate implementation. Again using the Lena image as an example, results from applying our algorithm are shown in Fig. 13. Fig. 13a shows the results of the tracing algorithm, with simple thresholding of edgepoints with very weak edgeness. Fig. 13b shows the same image with short edges (less than three pixels) removed. Fig. 13c shows the same image with straight, corner, and triple joins completed.Fig. 13d shows only segments which have been connected by at least one kind of join.

(a)

Fig. 14. Other edge detection methods Canny’s edge detector.

(b)

(a) Laplacian of

In practice, triple joins appear the most common, lowed by straight joins, and corner joins. For example, Lena image in Fig. 13c contains 74 triple joins, 37 stra joins,and 19 corner joins. Since triple joins can appear as a Combination of corner joins and straight joins, however, these numbers can vary depending on the order in which they are detected. We noticed that points at the end of edge segments often contain the weakest edge information of the entire edge

spurious joins can appe function to refine the en specifying that 1) the edge-direction a

If an end point did not sat m o v e d . The removal p r o c e of four pixels, until a poi the end of each segment joining process. Figs. 15, 16, 17, and 18 sh three-stage algorithm (filt ing/joins) to some other test age, Figs. 16, 17, and 18 are while Fig. 19 is 512 by 512 pi level representation Fig 13 Final results of edge detector (a) basic edge skeleton, (b) with short lines (< 3 pixels) removed, (c) with joins completed, (d) with unconnected lines removed

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

LAW ET AL.: IMAGE FILTERING, EDGE DETECTION, AND EDGE TRACING USING FUZZY REASONING

Fig. 15. (a) original image, (b) after filtering, detection,tracing, and joins.

~489

brim of the hat in the Lena picture. During the tuning of the joining program, we noticed a tendency for parallel edges to cross over and fuse to their neighboring edge. These cases are especially difficult to resolve since they are weak, yet closely located distinct sets of information. The weakness of the data produces gaps in the tracing of such edges, and makes joining a sensitive process. This dilemma suggests that a specialized detector for nearby parallel edges would be useful. Furthermore, our joining process results in some joins which are not intuitive, as can be seen in the eyes and hair of the Lena image. The decision of whether to join or not to join is linked to the broader object recognition problem, and the problem of recognizing unfamiliar patterns in images.

5 RELATEDRESEARCH

(a)

(b)

Fig. 16. (a) original image, (b) after filtering, detection, tracing, and joins.

(a)

(b)

Fig. 17. (a) original image, (b)after filtering, detection, tracing, and joins.

Fig. 18. (a) original image, (b) after filtering, detection, tracing, and joins.

In many cases, close parallel edges appear due to shadows or subtle object shape, as seen in the thickness of the

Fuzzily controlled filters are related to the steerable filters proposed by Freeman [5], [61. Other fuzzy research applied to image processing include Pan and Kink 1191 who have used the concept of fuzzy sets in order to enhance the contrast between successive regions in x-ray images. In research by Bezdek [ll, fuzzy versions of c-means clustering have been developed, and [29] shows an application to astronomical images, while Jung et al. [ l l ] show an application for classifying images of tire treads. Bezdek 121 also describes fuzzy learning vector quantization clustering algorithms with an application to image segmentation. Kim et al. [12] apply fuzzy logic towards edge relaxation in the problem of connecting detected edge segments. A nonfuzzy technique for dealing with imperfect and incomplete data in images have been developed by Rao and Nevatia [23]. Since our research also uses simple textural statistical information (treated in a fuzzy way), it can be related to the various statistical work summarized by Reed and Hans du Buf [24]. Regarding edge detection in general, a large number of papers have been published. A discussion of edge detection methods can be found in Heijden [9], which includes references to several prominent and recent papers in the field. A fuzzy edge detection technique was also introduced by Tao and Thompson [27]. In this technique, sixteen possible edge structures in a 3 x 3 area are considered, and fuzzy edge membership is determined by fuzzy if-then rules. After redundant edge pixels are discarded, remaining edge pixels are thresholded based on a noise factor. Filtering and enhancement possibilities are not considered. A fuzzy filtering and edge detection technique was introduced by Tyan and Wang [28]. Tyan and Wang use fuzzy rules for contrast enhancement, requiring arbitrary definitions of dark and bright pixels, which the authors admit require adjustment by a human operator. Images are further enhanced by an interesting fuzzy low-pass filter. The edge detection scheme also relies on arbritary dark and bright definitions (again requiring user adjustment), and operates on a 2 x 2 area. A single test image is presented. Neither of the techniques in [271 and [28] acknowledge the possibility of various edge shapes such as corners and triple points, leaving gray-level differences among immediate neighbors as the only determining factor in edge extraction. Furthermore, in both techniques edge direction is ig-

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

I€€€

490

TRANSACTIONS ON P A I T E R N ANALYSIS AND MACHINE INTELLIGENCE, VOL 18, N O 5 MAY 1996

nored completely Also, both techniques operate on very small regions, ignoring the possibility of broader edges in the process The relation between neighboring edge points and connecting edge segments are also not considered. This research has unique merit for the following reasons. Our techniques acknowledge the existence of imperfect edges and of ambiguous edges, and then elaborates a linguistic framework for characterizing these ambiguihes and imperfections These characteristics are then approximated from local statistical parameters, and fuzzy rules based on heuristics are introduced to evaluate these parameters. This procedure is performed for image filtering, edge detection, and edge tracing Our research is the first to attack the edge detection problem with a fuzzy reasoning approach, and is the only research to apply fuzzy reasoning to multistage (1 e , filtering, detection, and tracing) edge detection

6 DISCUSSION/CONCLUSIONS

small and large respectiv B', we obtain fuzzy mem fuzzy sets low and high respecti The result C is determined b

fuzzy membership

method of simplified fuzzy reasonin to this example gives U,, =

In this research, fuzzy algorithms have been developed for the purpose of filtering images, detecting edge points, and assembling edge structures These algorithms have been implemented and tested on a variety of real images with positive results. Comparisons were made with standard image processing techniques. Current trends in image analysis show a shift towards top-down image processing techniques. (See for example, 141.) While our algorithm begins with bottom-level detail, we think of it as a bottom-middle algorithm, since it takes into account intermediate-level structural characteristics. Furthermore, we feel that our algorithm appropriately interprets low level results at an intermediate level, without premature assignment. Based on experience with common edge structures, our algorithm begins to assemble edge information in a meaningful way

which is a simultaneous versi producing a final value for t constants- (determined empirically) for Slow C and Fast C respectively, and each term in the numerator corresponds to a rule in Table Al.

APPENDIXB Calculation of signal-to-noise rati SNR in this research was perfor is the original image, and g(n, then the normalized mean squa

APPENDIX A In this paper, the calculation of a fuzzy variable is as follows. A set of fuzzy rules are expressed as in Table A l .

After the image has been filtered, the processed image

p(n,, E,) has NMSE of

TABLE AI EXAMPLE FUZZYRULES result C small small large

slow slow

First the fuzzy membership values, k, for A and B are determined as shown graphically in Fig. Al. " ~

K

x

3

SNR improvement = 10 log,, which simplifies to

P

P., " ....._..................... O

2 pa2....... -.-................. 4

The SNR improvement due to processing is given by

00 0.0

A'

A

SNR improvement

= 10log,,,

To calculate the SNR alone, if f(n,, n2)is the original signal, and v(n,,n,) is the added noise signal

Fig A I . Determining fuzzy membership values

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.

LAW ET AL.: IMAGE FILTERING, EDGE DETECTION, AND EDGE TRACING USING FUZZY REASONING

ACKNOWLEDGMENT This research was by the Japanese Ministry Of Education. The authors wish to thank the developers of the Vista [22]program library which was used for this research.

REFERENCES J.C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum, 1981. J.C. Bezdek, ”Prototype Generating Clustering Algorithms,” Proc. Fifth Int’l Fuzzy Systems World Congress, pp. XXXVI-XLIII, Seoul, 1993. J.F. Canny, ”Finding Edges and Lines in Images,” Technical Report AI-TR 720, Massachusetts Artificial Intelligence Laboratory, June, 1983. P. Cavanaugh, ”What’s Up in Top-Down Processing?” Representations of Vision: Trends and Tacit Assumptions in Vision Research, A. Gorea. ed., pp. 295-304,1991, W., Freeman, ”Steerable Filters and Analysis of Image Structure,” PhD thesis, MIT, Cambridge, Mass., 1992. W. Freeman and T. Adelson, ”Steerable Filters,” Proc. Third Int’l Conf. Computer Vision, Osaka, 1990. R. Graham, “Snow Removal: A Noise-Stripping Process for TV Signals,” IRE Trans. Information Theory, vol. 8, pp. 129-144,1962, W. Grimson, ”A Computer Implementation of a Theory of Human Stereo Vision,” AI Memo 565, Artificial Intelligence Laboratory, MIT, Cambridge, Mass., 1980. F. van der Heijden, “Edge and Line Feature Extraction Based on Covariance Models,” IEEE Trans. Pattern Analysis and Machine lntelligence, vol. 17, no. 1, pp. 69-77, Jan. 1995. G. Kanisza, Organization in Vision. New York: Praeger, 1979. S. Jung, S. Bae, Y. Kang, G. Park, and G. Kim, “Tire Tread Pattern Recognition Using Hierarchical Fuzzy Pattern Matching ADproarh,” Proc. Fiftvh Int’l Fuzzy Systems World Congress, P.; 1y7130, Seoul, 1993. J.S.’Kim, H.S. Cho, and S.K. Kim, “An Edge Relaxation Method Based on Fuzzy Logic and Neural Network Theory,” Proc. Fifth Int’l Fuzzy Systems World Congress, pp. 143-146, Seoul, 1993. T. Law, H. Itoh, H. Seki, ”Filtering Images for Edge Detection Using Fuzzy Reasoning,” Proc. Third Int‘l Conf. Automation, Robotics, and Computer Vision, Singapore, 1994. M. Levine, Vision in Man and Machine, Chap. 6, pp. 151-210. New York: McGraw-Hill, 1985. J.S. Lim, Two-Dimensional Signal and Image Processing, pp. 529-530. Prentice Hall, 1990. E.H. Mamdani, ”Advances in the Linguistic Synthesis of Fuzzy Controller,” lnt’l 1.Man-Machine Studies, vol. 8, no. 6, pp. 669-679, 1976. D. Marr and E. Hildreth, ”Theory of Edge Detection,” Proc. Royal Society, (London), ser. B, vol. 207, pp. 187-217,1980. M. Nitzberg, D. Mumford, and T. Shiota, “Filtering Segmentation and Depth,” Lecture Notes in Computer Science, G. Goos, J. Hartmannis, eds., Chaps. 1-3, pp. 1-49. Berlin: Springer-Verlag, 1991. S.K. Pal, and R.A. King, ”On Edge Detection of X-Ray Images Using Fuzzy Sets,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 5, no. 1, pp. 69-77,1983. S.K. Pal, ”A Note on the Quantitative Measurement of Image Enhancement Through Fuzziness,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 4, no. 2, pp. 204-208,1982, P. Perona and J. Malik, ”Scale-Space and Edge Detection Using Anisotropic Diffusion,” I E E E Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 7, pp. 629-639, July, 1990. A.R. Pope and D.G. Lowe, “Vista: A Software Environment for Computer Vision Research,” Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, 1994. K. Rao and R. Nevatia, ”Describing and Segmenting Scenes from Imperfect and Incomplete Data,” CVGIP: Image Understanding, vol. 57, no. 1, pp. 1-23, 1993. T.R. Reed and J.M. Hans du Buf, “A Review of Recent Texture Segmentation and Feature Extraction Techniques,” CVGIP Imape Understanding, vol. 7, no. 3, pp. 359-372, May, 1993.

49 1

[25] R. Rodieck, “Quantitative Analysis of Cat Retinal Ganglion Cell Response to Visual Stimuli,” Vision Research, vol. 5, no. 11/12, -pp. _ 583601,1965. [261 R.J. Schalkoff, Digital Image Processing and Computer Vision-An Introduction to Theory and Implementations, Chap. 6, -pp. - 267-270. New York: John Wiley & Sons, 1989. [27] C. Tao, W. Thompson, and J. Taur, “A Fuzzy If-Then Approach to Edge Detection,” Puoc. Second IEEE lnt’l Conf. Fuzzy Systems, vol. 11, pp. 1,356-1,360, San Francisco, 1993. 1281 C. Tyan and P. Wang, ”Image Processing-Enhancement, Filtering and Edge Detection Using the Fuzzy-Logic Approach,” Proc Second Int’l Conf Fuzzy Systems, vu1 I, pp 600-605, San Francisco, 1993 [291 X L Xie and G. Bmi, ”A Validity Measure for Fuzzy Clustering,” I E E E Trans Pattern Analysis and Machine Intelligence, vol. 13, no. 8, pp 841-847,Aug 1991 1301 L.A. Zadeh, ”The Concept of a Linguistic Variable and Its Application to Approximate Reasoning-I, 11,111,” Information Science, 8, 9,1975 ~

Todd W. Law (S’83) received the BEng (Honours) degree in electrical engineering from McGill University in Montreal, Canada, in 1987. From 1987 to 1990, he worked at Northern 1-elecom Limited. In 1992, he received the MSc degree from the Nagoya Institute of Technology, and is currently a doctoral candidate at that institution Mr. Law is a member of the Japanese Society for Information Processing.

Hidenori ltoh received a BSc degree from Fukui University in 1969, and an MSEE degree in 1971 and a PhD degree in 1974 from Nagoya Ilniversity. From 1974 to 1985, he worked at Nippon Telephone and Telegraph laboratories, developing operating systems. From 1985 to 1989, he worked at ICOT, the Fifth Generation Computer Project, developing knowledge base systems. Since 1989, he has been a professor at the Nagoya Institute of Technology, and is currently head of the Department of Intelligence and Computer Science. Dr. ltoh is a member of the Japanese Society for Information Processing Hirohisa Seki received the BEng, MEng, and DrEng degrees from the University of Tokyo in 1979, 1981, and 1991, respectively. He joined the Central Research Laboratory of Mitsubishi Electric Corporation in 1981 and engaged in the research on artificial intelligence. From 1985 to .I 989, he was with the Institute for New Generation Computer Technology (ICOT). Since 1992, he has been an associate professor in the Department of Intelligence and Computer Science at Nagoya Institute of Technology. His current research interests include logic programming, deductive databases and automated deduction. He is a member of ACM, IEEE Computer Society, IPSJ, and JSAI.

Authorized licensed use limited to: KTH THE ROYAL INSTITUTE OF TECHNOLOGY. Downloaded on September 24, 2009 at 12:06 from IEEE Xplore. Restrictions apply.