Canny's Filter For Edge Detection: A Java Implementation

Canny’s Filter for Edge Detection. A Java Implementation – José Iguelmar Miranda

1

Canny’s Filter for Edge Detection. A Java Implementation – José Iguelmar Miranda

Introduction The aim of this article is to present the Java implementation of the Canny’s filter for edge detection (Canny, 1986). Edge detection is one of the most common processes when analyzing digital images, counting with a great variety of algorithms. Edges carry useful information about object boundaries which can be used for image analysis, object identification and for image filtering. Nevertheless, there is no precise and widely accepted mathematical definition of an edge yet. This is so because the complexity of the image content and by the interference of high-level vision mechanisms in the human perception of the boundary of an object (Pitas, 2000). Edges, in the present approach, are transitions regions between two homogeneous regions in a digital image having different values for pixels intensity and generally define the borders between the object and its background. This means that if one can detect the edges, then objects and some of their features can be measured, like area, perimeter and shape. This is why the edge detection process is qualified as an essential tool in image analysis. Edge detection is part of a major procedure, known as segmentation – the identification of regions inside an image. There are two techniques in digital image processing that deal with edges: edge detection and edge enhancement. Technically, edge detection aims to localize the pixels in the borders of an object, while edge enhancement increases the contrast between edges and background, making them more visible (Parker, 1997). In practice, both terms are used with the same subject, because the majority of the algorithms for edge detection assign to the pixels in the borders values that make them more visible.

12

Canny’s Filter for Edge Detection. 2009

Theoretical Aspects There are some possible definitions for edges, applicable in differing situations. The most common and generic is ideal step border (Fig. 1a). This is a one dimensional example, where the edge is simply a change in grey level occurring at one specific location (x = 125), along the horizontal or absciaaxes. The bigger the gray level difference in the transition zone, the easier to detect edges. But, in real world, complexity happens. For instance, the quantization process realized by a satellite, the scene sampling not always can make a precise match between real object edges and the pixels that will represent them. Commonly, happens what is shown in Fig. 1b. In this case, the position of the edge is considered to be the center of the ramp connecting the low grey level to the high one.

2 25

1 75 N ível de cinza 1 25

75 25 0 0

25

75

12 5

17 5 x

Figure 1a. Ideal border example.

225

25 0

3

225

175 Nível de cinza 125

75 25 0 0

25

75

175

125

225

250

x

Figure 1b. Ideal border example. An additional difficulty has to do with the ubiquitous problem of noise. Due to some factors, like sun light intensity, camera model and lens, satellite movement, air temperature, atmospheric effects, among others, it is unlike that two pixels with the same gray level in the ground will have the same gray level in the digital image. Noises are random and systematic. Random noises are only characterized by a statistical distribution. Systematic noises are easier to detect and to remove. The net effect of noises in the image is to produce a random variation in the gray level values of the pixels, such that the ideal edge shown in Fig. 1 is not found in real images. That said, it is not possible to ignore the presence of random noise in images. The problem is that this noise cannot be identified and measured precisely, since one cannot differentiate its contribution in the pixels gray level values. Happily, sometimes, the random noise can be characterized by its effect in the image, expressed as a probability distribution with specific values of mean and standard deviation (Parker, 1997). So, before working with an image, it is necessary to filter this kind of noise, normally using an edge detection process. Since a border is defined as a change in the gray level, an operator that is sensible to this change has a task to detect edge. Generally, edge operators can be classified in three groups: (1) those based on partial derivatives, approximated by differences in the discrete case, whose task is to identify spots where there are great intensity

12

Canny’s Filter for Edge Detection. 2009

changes; (2) those that model the border with a small dimension kernel; and (3) those that use mathematical models for the borders, using partial differential equations, or diffusion models, that search for the maxima and minima of a function. The approach used here is a mix between (1) and (2).

The Canny’s Filter John Canny (1986) specified three issues that an edge detector must address: 1. Good detection – there should be a low probability of failing to mark real edge points, and low probability of falsely marking nonedge points. This criterion corresponds to maximizing signal-to-noise ratio. 2. Localization – the distance between the edge pixels as found by the edge detector and the actual edge should be as small as possible. 3. Response – only one response to a single edge. Where there are two responses to the same edge, one of them must be considered false. According to the author, the challenge would be to transform these criteria in a mathematical formalism which is readily solvable. Canny assumed a step edge subject to white Gaussian noise. The edge detector was assumed to be a convolution filter, f, which would smooth the noise and locate the edge. The problem was to identify the one filter that optimizes the three edge detection criteria. He started his work analyzing the behavior of the above criteria in one dimension. Firstly, he considered the signal-to-noise ratio and localization, letting the function f(x) be the impulse response of the filter, and G(x), the edge itself; he assumed that the edge was centered at x = 0. The response of the filter to this edge, centered at HG, was given by a convolution integral (Canny, 1986): w

HG 

 G ( x) f ( x)dx

w

(1)

5

Where the filter has a finite impulse response bounded by [-w, w], and zero out of this interval. To the noise, n(x), consider the root-mean-squared response (Canny, 1986): w  H n  n 0   f 2 ( x)dx  w 

1

2

) (2

Where n02 is the mean-squared noise amplitude per unit length. So, the first criterion, the output signal-to-noise ration, can be formalized as the quotient of these two responses (Canny, 1986): W

SNR 



W

n0

G(  x) f ( x) dx ) (3



w

w

f 2 ( x) dx

For the second criterion, Canny considered some measure that increased as localization improved, using the root-mean-squared distance between the marked edges from the center of the true edge. Edges marking happened in local maxima in the response of the operator f(x), i.e., where its first derivative was zero. The reader can obtain further details in Canny’s article, for finding the localization measure: W

Localização 



W

n0

G ( x) f ( x)dx ) (4



w

w

2

f  ( x)dx

Canny showed that using only the first two criteria, the optimal detector for step edges with noise is a truncated step (Fig. 2a), similar to using a difference of boxes filter (Fig. 2c).

12

Canny’s Filter for Edge Detection. 2009

x - w/2

(a)

x + w/2 (c)

(b)

Figure 2. Signal-to-noise, DoG, and difference of boxes filters.

This filter, however, has a very high bandwidth and tends to exhibit many maxima in its response to noisy step edges, which should be considered erroneous according to the first criterion. The mean distance between adjacent maxima and the noise output of f(x), called x max, will restrict the selection of f(x) according to a single criterion, the third: xmax [f(x)] = kw

(5)

Where k is some fraction of the operator width, w. Due to the complexity of the formulation, no analytical solution was found. A variant was developed, enabling the edge detection. For small values of xmax, the Canny’s operator becomes close to the action of a difference of boxes filter (Fig. 1c). For bigger values of xmax, it becomes close to the action of a filter of the first derivative of a Gaussian function (Fig. 1b), also known as derivative of Gaussian (DoG). In two dimensions, an edge also has an orientation, meaning the direction of the direction of the tangent to the contour that the edge defines in two directions. Canny created a two-dimensional mask for this orientation by convolving a linear edge detection function aligned normal to the edge direction with a projection function parallel to the edge direction. In two dimensions, the Gaussian function is given by:

7

 x2  y2 G ( x, y )   2 exp   2  2

  

) (6

Hence, the approximation of the Canny’s optimal filter for edge detection is G’ (first derivative), and so by convolving the input image with G’ we obtain an image E that has enhanced edges, even in the presence of noise, which has been incorporated into the model of the edge image. A convolution is simple to implement, but is expensive computationally, especially a two dimensional convolution. However, a convolution with a two dimensional Gaussian can be separated into two convolutions with one dimensional Gaussians, and the differentiation can be done afterwards. Indeed, the differentiation can also be done by convolutions in one dimension, giving two images: one is the x component of the convolution with G’ and the other is the y component. The reader interested in details can take a look at the comprehensive Canny’s article (1986). Fig. 3 shows the approximated effect of the DoG filter (Fig. 2a, and difference of boxes, Fig. 2c) in the signal shown in Fig. 2a. The filtered signal with the difference of boxes filter shows local maxima problems.

(a)

(b)

Figure 3. Effects of the filters DoG and difference of boxes in the signal shown in Fig. 2a.

The Java Implementation Java language is an alternative for implementation of applications not only for the web, but for others uses. The facility to run Java applications in whatever operating system is a strong appeal to use Java. At least, this advantage motivated the present

12

Canny’s Filter for Edge Detection. 2009

work. In the following sections, the reader is presented with the whole source code of the application. You can add it to an IDE, like NetBeans or Eclipse, or simply compile and execute through a DOS/Term prompt. Initially, it was developed to run in Windows environment, using a DOS prompt. The filter implementation was developed as a pure Java application, containing only the constructor, called from the main() method. In Windows, the compilation is done calling: C:[instalation dir]>javac -deprecation FiltroCanny.java

To execute it: C:[instalation dir]>java FiltroCanny <sup>

Where the parameters are: 

– the image to be filtered.



– the standard deviation.



– low hysteresis threshold value.



<sup> – high hysteresis threshold value.

Values of the standard deviation and thresholds must be tested by the user, till he founds an output image with good result. At this point, we suggest the construction of a graphical interface that allows dynamical change in these values, as of using the JSlider. The constructor of the filter is defined as: public CannyFilter(String aFile, double s, int inf, int sup) {  }

Where: 1. aFile: input image archive. 2. s: standard deviation.

9

3. inf, sup: low and high hysteresis threshold values. Any pixel in the image that has a value greater than highTh is presumed to be an edge pixel, and is marked as such. Then, pixels that are connected to this edge pixel and that have a value greater than lowTh are also selected as edge pixels, and are marked too. The constructor has four tasks: (1) read the input image to be filtered; (2) call the canny method, that implements the Canny filter; (3) define the edge pixels, using the parameters values (lowTh and highTh); and (4) shows the output (filtered) image. The canny method implements the main steps of the algorithm, described as (Parker, 1997): 1. Read in the image to be processed, I. 2. Create a 1D Gaussian mask G to convolve with I. The standard deviation s of this Gaussian is a parameter to the edge detector. double funcGauss[]

3. Create a 1D mask for the first derivative of the Gaussian in the x and y directions; call these Gx and Gy. The same s value is used as in step 2. double derivadaGauss[]

4. Convolve the image I with G along the rows to give the x component image Ix, and down the columns to give the y component image Iy. convolveImagemXY(imagem, funcGauss, width, componenteX, componenteY);

5. Convolve Ix with Gx to give Ix’, the x component of I convolved with the derivative of the Gaussian, and convolve Iy with Gy to give Iy’. derivadaX = convolveDerivadaXY(componenteX, nr, nc, derivadaGauss, width, 1); derivadaY = convolveDerivadaXY(componenteY, nr, nc, derivadaGauss, width, 0);

6. The magnitude of the result is computed at each pixel (x, y) as: z = norma(derivadaX[j][i], derivadaY[j][i]);

Which corresponds to the following equation:

M ( x, y)  I x ( x, y ) 2  I y ( x, y ) 2 7. Finally, suppress pixels that are not local maxima.

12

Canny’s Filter for Edge Detection. 2009

removeFalsoMax(derivadaX, derivadaY, nr, nc, imagemMag, imagemOrig);

The Java Source Code

/********************************************************************* FiltroCanny.java – implements the Canny filter. WRITTEN BY: José Iguelmar Miranda & João Camargo Neto. DATE:

September 2008

Copyright (c) 2009 Embrapa Informática Agropecuária PERMISSION TO COPY: This program is free software, under the GNU General Public License (GPL); permission to use, copy and modify this software and its documentation for NON-COMMERCIAL purposes is granted, without fee, provided that an acknowledgement to the authors, José Iguelmar Miranda & João Camargo Neto, at www.cnptia.embrapa.br, appears in all copies. Embrapa Informática Agropecuária makes no representations about the suitability or fitness of the software for any or for a particular purpose. Embrapa Informática Agropecuária shall not be liable for any damages suffered as a result of using, modifying or distributing this software or its derivatives. For a copy of GNU General Public License, write to: Free Software Foundation, Inc., 59 Temple Street, Suite 330, Boston, MA 02111-1307 USA. ********************************************************************* Description: This program implements the Canny filter. Reference paper: CANNY, J. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence. 8(6):679-698, 1986. *********************************************************************/ // Generic packages import java.io.File; // AWT packages import java.awt.image.WritableRaster;

1

import java.awt.image.BufferedImage; import java.awt.image.Raster; import java.awt.GridLayout; // Swing packages for graphical interface import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.ImageIcon; import javax.swing.JScrollPane; // Immediate mode reading - J2SE 1.4+ import javax.imageio.ImageIO; public class FiltroCanny extends JFrame { // Attributes // Image scale and magnitude static double ORI_SCALE = 40.0; static double MAG_SCALE = 20.0; // Kernel mask maximum size static int MAX_MASK_SIZE = 20; // Fraction of pixels that should be above the HIGH threshold double ratio = 0.1; int LARGURA = 0; public static void main(String args[]) { double dp = 1.0; int inf = 0, sup = 0; // Parameters ok? if (args.length != 4) { String msga = "Uso: java -cp . FiltroCanny <sup>"; String msgb = "\n dp => standard deviation."; String msgc = "\n inf => LOW threshold."; String msgd = "\n sup => HIGH threshold."; System.out.println(msga + msgb + msgc + msgd); System.exit(0); } // Show JFrame decorated by Swing JFrame.setDefaultLookAndFeelDecorated(true); try { dp = Double.parseDouble(args[1]); } catch (NumberFormatException e) { System.out.println("Valor do parametro invalido"); System.exit(0); }

12

Canny’s Filter for Edge Detection. 2009

try { inf = Integer.parseInt(args[2]); } catch (NumberFormatException e) { System.out.println("Valor do parametro invalido"); System.exit(0); } try { sup = Integer.parseInt(args[3]); } catch (NumberFormatException e) { System.out.println("Valor do parametro <sup> invalido"); System.exit(0); } // Call the constructor if (dp <= 0.0) dp = 1.0; if (inf < 0) inf = 0; if (sup > 255) sup = 255; long eq_time = System.currentTimeMillis(); FiltroCanny fc = new FiltroCanny(args[0], dp, inf, sup); eq_time = System.currentTimeMillis() - eq_time; String msg = "Canny: tempo de execucao "; System.out.println(msg + eq_time + " milisseg."); // If “X” clicked, close the application fc.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); fc.setVisible(true); } public FiltroCanny(String aFile, double s, int inf, int sup) { BufferedImage imagem = null, imagemMagnitude = null, imagemOriginal = null; int w, h, tipo; JLabel img1; // Does the image file exist? File file = new File(aFile); try { imagem = ImageIO.read(file); } catch(Exception e) { System.out.println("Imagem '" + aFile + "' nao existe."); System.exit(0); }

13

String msga = "\nParametros para Canny:\n"; String msgb = "==> limiar inferior " + inf + "\n"; String msgc = "==> limiar superior " + sup + "\n"; String msgd = "==> desvio padrao " + s + "\n"; System.out.println(msga + msgb + msgc + msgd); // Atribui nome ao frame setTitle("Canny: " + file.getName()); // Cria imagem local w = imagem.getWidth(); h = imagem.getHeight(); tipo = BufferedImage.TYPE_BYTE_GRAY; imagemMagnitude = new BufferedImage(w, h, tipo); imagemOriginal = new BufferedImage(w, h, tipo); WritableRaster imWR = imagem.getRaster(); // Call the Canny method canny(s, imagem, imagemMagnitude, imagemOriginal); // Define edge pixels using threshold values HIGH and LOW linhasBordas(sup, inf, imagem, imagemMagnitude, imagemOriginal); for (int i = 0; i < LARGURA; i++) for (int j = 0; j < w; j++) imWR.setSample(j, i, 0, 255); for (int i = h - 1; i > h - 1 - LARGURA; i--) for (int j = 0; j < w; j++) imWR.setSample(j, i, 0, 255); for (int i = 0; i < h; i++) for (int j = 0; j < LARGURA; j++) imWR.setSample(j, i, 0, 255); for (int i = 0; i < h; i++) for (int j = w - LARGURA - 1; j < w; j++) imWR.setSample(j, i, 0, 255); // Create gridLayout de 1 x 1 getContentPane().setLayout(new GridLayout(1, 1)); img1 = new JLabel(new ImageIcon(imagem)); setSize(w, h); getContentPane().add(new JScrollPane(img1)); } private void canny(double s, BufferedImage imagem, BufferedImage imagemMag, BufferedImage imagemOrig) { int width = 0, k, n, nc, nr; double[][] componenteX, // x component of the original image convolved // with the Gaussian.

12

Canny’s Filter for Edge Detection. 2009

componenteY, derivadaX, derivadaY; double funcGauss[], derivadaGauss[], z;

// // // // // // // //

y component of the original image convolved with the Gaussian. x component of the convolved image (componenteX) with Gaussian derivative y component of the convolved image (componenteY) with Gaussian derivative Gaussian values Values of the Gaussian first derivative

funcGauss = new double[MAX_MASK_SIZE]; derivadaGauss = new double[MAX_MASK_SIZE]; nc = imagem.getWidth(); nr = imagem.getHeight(); // Create a mask of the Gaussian filter and its derivative for (int i = 0; i < MAX_MASK_SIZE; i++) { funcGauss[i] = mediaGauss((double)i, s); if (funcGauss[i] < 0.005) { width = i; break; } derivadaGauss[i] = dGauss((double)i, s); } n = 2*width + 1; LARGURA = (int)width/2; System.out.println("Suavizando com uma Gaussiana (largura = " + n + ") ...\n"); componenteX = new double[nc][nr]; componenteY = new double[nc][nr]; // Convolve original image with Gaussian mask in x and y directions convolveImagemXY(imagem, funcGauss, width, componenteX, componenteY); // Convolve smoothed image with derivative System.out.println("Convolucao com a derivada da Gaussiana...\n"); derivadaX = convolveDerivadaXY(componenteX, nr, nc, derivadaGauss, width, 1); derivadaY = convolveDerivadaXY(componenteY, nr, nc, derivadaGauss, width, 0); WritableRaster magWR = imagemMag.getRaster(); // Create magnitude image from the x and y derivatives (gradient) for (int i = 0; i < nr; i++) for (int j = 0; j < nc; j++) { z = norma(derivadaX[j][i], derivadaY[j][i]);

15

magWR.setSample(j, i, 0, (int)z*MAG_SCALE); } // Suppress false maxima removeFalsoMax(derivadaX, derivadaY, nr, nc, imagemMag, imagemOrig); } // Compute mean of Gaussian function private double mediaGauss(double x, double sigma) { double z; z = (gauss(x,sigma)+gauss(x+0.5,sigma)+gauss(x-0.5,sigma))/3.0; z = z/(Math.PI*2.0*sigma*sigma); return z; } // Compute value for Gaussian function private double gauss(double x, double sigma) { double expoente; if (sigma == 0) return 0.0; expoente = Math.exp(((-x*x)/(2*sigma*sigma))); return expoente; } // Compute first derivative value of Gaussian function private double dGauss(double x, double sigma) { return (-x/(sigma*sigma)*gauss(x, sigma)); } // Convolve components x and y of the image. private void convolveImagemXY(BufferedImage imagem, double[] funcGauss, int width, double[][] compX, double[][] compY) { int i1, i2, nr, nc; double x, y; nc = imagem.getWidth(); nr = imagem.getHeight(); Raster imR = imagem.getRaster(); for (int i = 0; i < nr; i++) for (int j = 0; j < nc; j++) { x = funcGauss[0]*imR.getSample(j, i, y = funcGauss[0]*imR.getSample(j, i, for (int k = 1; k < width; k++) { i1 = (i+k)%nr; i2 = (i-k+nr)%nr; y += funcGauss[k]*imR.getSample(j, funcGauss[k]*imR.getSample(j,

0); 0);

i1, 0) + i2, 0);

12

Canny’s Filter for Edge Detection. 2009

i1 = (j+k)%nc; i2 = (j-k+nc)%nc; x += funcGauss[k]*imR.getSample(i1, i, 0) + funcGauss[k]*imR.getSample(i2, i, 0); } compX[j][i] = x; compY[j][i] = y; } } // Do the convolution in the derivatives of the x and y components of the // convolved image private double[][] convolveDerivadaXY(double[][] imagem, int nr, int nc, double[] funcGauss, int width, int compXY) { int i1, i2; double x; double[][] componente = new double[nc][nr]; for (int i = 0; i < nr; i++) for (int j = 0; j < nc; j++) { x = 0.0; for (int k = 1; k < width; k++) { switch (compXY){ case 0: // y component i1 = (i+k)%nr; i2 = (i-k+nr)%nr; x += -funcGauss[k]*imagem[j][i1] + funcGauss[k]*imagem[j][i2]; break; case 1: // x component i1 = (j+k)%nc; i2 = (j-k+nc)%nc; x += -funcGauss[k]*imagem[i1][i] + funcGauss[k]*imagem[i2][i]; break; } } componente[j][i] = x; } return componente; } // Suppress false maxima private void removeFalsoMax(double[][] derivX, double[][] derivY, int nr, int nc, BufferedImage imagemMag, BufferedImage imagemOrig) { int k, n, m, top, bottom, left, right; double xx, yy, grad1, grad2, grad3, grad4, gradiente, compX, compY;

17

nc = imagemMag.getWidth(); nr = imagemMag.getHeight(); WritableRaster magWR = imagemMag.getRaster(); WritableRaster oriWR = imagemOrig.getRaster(); for (int i = 1; i < nr - 1; i++) { for (int j = 1; j < nc - 1; j++) { magWR.setSample(j, i, 0, 0); // x and y derivatives are components of a vector (gradient) compX = derivX[j][i]; compY = derivY[j][i]; if (Math.abs(compX) < 0.01 && Math.abs(compY) < 0.01) continue; gradiente = norma(compX, compY); // Fallow gradient direction, vector (compX, compY). // Keep edge pixels (local maxima). if (Math.abs(compY) > Math.abs(compX)) { // First case: y component is bigger. Gradient direction is // upward or downward. xx = Math.abs(compX)/Math.abs(compY); yy = 1.0; grad2 = norma(derivX[j][i-1], derivY[j][i-1]); grad4 = norma(derivX[j][i+1], derivY[j][i+1]); if (compX*compY > 0.0) { grad1 = norma(derivX[j-1][i-1], derivY[j-1][i-1]); grad3 = norma(derivX[j+1][i+1], derivY[j+1][i+1]); } else { grad1 = norma(derivX[j+1][i-1], derivY[j+1][i-1]); grad3 = norma(derivX[j-1][i+1], derivY[j-1][i+1]); } } else { // Second case: y component is bigger. Gradient direction is // left or right. xx = Math.abs(compY)/Math.abs(compX); yy = 1.0; grad2 = norma(derivX[j+1][i], derivY[j+1][i]); grad4 = norma(derivX[j-1][i], derivY[j-1][i]); if (compX*compY > 0.0) { grad1 = norma(derivX[j+1][i+1], derivY[j+1][i+1]); grad3 = norma(derivX[j-1][i-1], derivY[j-1][i-1]); } else { grad1 = norma(derivX[j+1][i-1], derivY[j+1][i-1]); grad3 = norma(derivX[j-1][i+1], derivY[j-1][i+1]); } } // Compute the interpolated value of the gradient magnitude if ((gradiente > (xx*grad1 + (yy-xx)*grad2)) && (gradiente > (xx*grad3 + (yy-xx)*grad4))) {

12

Canny’s Filter for Edge Detection. 2009

if (gradiente*MAG_SCALE <= 255) magWR.setSample(j, i, 0, (int)gradiente*MAG_SCALE); else magWR.setSample(j, i, 0, 255); oriWR.setSample(j, i, 0, (int)Math.atan2(compY, compX)*ORI_SCALE); } else { magWR.setSample(j, i, 0, 0); oriWR.setSample(j, i, 0, 0); } } } } // Define edge pixels private void linhasBordas(int sup, int inf, BufferedImage imagem, BufferedImage imagemMag, BufferedImage imagemOrig) { int nr, nc; nc = imagem.getWidth(); nr = imagem.getHeight(); WritableRaster imWR = imagem.getRaster(); Raster imR = imagem.getRaster(); Raster magR = imagemMag.getRaster(); System.out.println("Iniciando corte com limiares...\n"); for (int i = 0; i < nr; i++) for (int j = 0; j < nc; j++) imWR.setSample(j, i, 0, 0); if (sup < inf) { estimaLimiar(imagemMag, sup, inf); String str = "Limiar de corte (da imagem): SUPERIOR "; System.out.println(str + sup + " INFERIOR\n" + inf); } // For each edge with magnitude above HIGH threshold, draw the edge // pixels that are above the LOW threshold for (int i = 0; i < nr; i++) for (int j = 0; j < nc; j++) if (magR.getSample(j, i, 0) >= sup) trace(i, j, inf, imagem, imagemMag, imagemOrig); // Make the edge black for (int i = 0; i < nr; i++) for (int j = 0; j < nc; j++) if (imR.getSample(j, i, 0) == 0)

19

imWR.setSample(j, i, 0, 255); else imWR.setSample(j, i, 0, 0); } // Estimate the HIGH threshold private void estimaLimiar(BufferedImage imagemMag, int hi, int inf) { int histograma[], count, nr, nc, i, j, k; nc = imagemMag.getWidth(); nr = imagemMag.getHeight(); histograma = new int[256]; Raster magR = imagemMag.getRaster(); // Image histogram for (k = 0; k < 256; k++) histograma[k] = 0; for (i = LARGURA; i < nr - LARGURA; i++) for (j = LARGURA; j < nc - LARGURA; j++) histograma[magR.getSample(j, i, 0)]++; // O limiar superior deveria ser maior que 80 ou 90% dos pixels j = nr; if (j < nc) j = nc; j = (int)(0.9*j); k = 255; count = histograma[255]; while (count < j) { k--; if (k < 0) break; count += histograma[k]; } hi = k; i = 0; while (histograma[i] == 0) i++; inf = (int)(hi+i)/2; } // Trace, recursively, the edge pixels private int trace(int i, int j, int inf, BufferedImage imagem, BufferedImage imagemMag, BufferedImage imagemOrig) { int n, m; int flag = 0;

12

Canny’s Filter for Edge Detection. 2009

Raster magR = imagemMag.getRaster(); Raster imR = imagem.getRaster(); WritableRaster imWR = imagem.getRaster(); if (imR.getSample(j, i, 0) == 0) { imWR.setSample(j, i, 0, 255); flag = 0; for (n = -1; n <= 1; n++) { for(m = -1; m <= 1; m++) { if (i == 0 && m == 0) continue; if ((range(imagemMag, i+n, j+m) == 1) && (magR.getSample(j+m, i+n, 0)) >= inf) if (trace(i+n,j+m,inf,imagem,imagemMag,imagemOrig) == 1) flag = 1; break; } } if (flag == 1) break; } return 1; } return 0; } // Certificate that the pixel belongs to the image private int range(BufferedImage imagem, int i, int j) { int nc, nr; nc = imagem.getWidth(); nr = imagem.getHeight(); if ((i < 0) || (i >= nr)) return 0; if ((j < 0) || (j >= nc)) return 0; return 1; } // Compute the gradient magnitude private double norma(double x, double y) { return Math.sqrt(x*x + y*y); } }

{

1 2

Case Study The following pictures show the application of the Canny’s filter for edge detection. In all pictures, the threshold values were inf = 10 and sup = 20. Only the standard deviation values were changed, showing a different behavior of the filter. The first picture shows edge detection for simple objects.

Figure 4. (a) Input image; (b) standard deviation = 1.5; (c) standard deviation = 2.6 Fig. 4(a) shows the source image. In Fig. 4(b) the standard deviation value was 1.5, and in Fig. 4(c), the standard deviation was 2.6. The first value of the standard deviation allows the filter to detect edges of the objects, but has some side effects, because a lot of noise, from the background, is by passing. Increasing the standard deviation value, the noise is filtered, yielding a better result. Fig. 5 shows a different image, with agricultural exploitation. In this image one can see two center pivot (circle area), bare soil (white), sugar-cane and riparian vegetation along some creeks. The first image was filtered with a standard deviation of 1.5. As happened with the previous image, this standard deviation value allows the present of noise, which, actually, are edges of small objects present in the image. Visually, the result is not good. Increasing the standard deviation value permits to filter the edges of the small objects, “cleaning” the final image, with a better visual appeal. As one increases the standard deviation value, the output image becomes much clean, but at the expense of obtaining an image with less edges.

12

Canny’s Filter for Edge Detection. 2009

Figure 5. (a) Input image; (b) standard deviation = 1.5; (c) standard deviation = 2.2 Fig. 6 is a medical image, with a set of globules. The first filter used a standard deviation of 1.5, with result similar to the previous images. The second filter used a standard deviation of 2.6, with a better visual output image. In this image, with only simple objects, the result is better, as happened with Fig. 4. When the image presents a different set of objects with more nuances, the filtering process must be conducted with care to identify the targets.

Figure 6. (a) Input image; (b) standard deviation = 1.5; (c) standard deviation = 2.6

Bibliography PARKER, J.R. Algorithms for image processing and computer vision. New York, NY: John Wiley & Sons, 1997. 417p.

3 2

PITAS, I. Digital image processing algorithms and applications. New York, NY: John Wiley & Sons, 2000. 419p.

12