Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Canny Edge Detection

  1. #1
    Junior Member
    Join Date
    Mar 2010
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Canny Edge Detection

    Hi!
    I'm trying to make use of Tom Gibara's implementation of the canny edge detection. I get the application up and running and everything is as it should be.
    My problem:
    I want to extract the edge data from the edge image and use it to draw the edge on the original image.The drawing isn't my issue, just the part of getting the edge info and how to make use of it. Any ideas?
    Thanks everyone in advance!

    Tom's code:
    import java.awt.image.BufferedImage;
      2import java.util.Arrays;
      3import java.awt.*;
      4import java.awt.image.*;
      5import javax.swing.*;
      6
      7/**
      8 * <p><em>This software has been released into the public domain.
      9 * <strong>Please read the notes in this source file for additional information.
     10 * </strong></em></p>
     11 *
     12 * <p>This class provides a configurable implementation of the Canny edge
     13 * detection algorithm. This classic algorithm has a number of shortcomings,
     14 * but remains an effective tool in many scenarios. <em>This class is designed
     15 * for single threaded use only.</em></p>
     16 *
     17 * <p>Sample usage:</p>
     18 *
     19 * <pre><code>
     20 * //create the detector
     21 * CannyEdgeDetector detector = new CannyEdgeDetector();
     22 * //adjust its parameters as desired
     23 * detector.setLowThreshold(0.5f);
     24 * detector.setHighThreshold(1f);
     25 * //apply it to an image
     26 * detector.setSourceImage(frame);
     27 * detector.process();
     28 * BufferedImage edges = detector.getEdgesImage();
     29 * </code></pre>
     30 *
     31 * <p>For a more complete understanding of this edge detector's parameters
     32 * consult an explanation of the algorithm.</p>
     33 *
     34 * @author Tom Gibara
     35 *
     36 */
     37
     38public class CannyEdgeDetector {
     39
     40        // statics
     41
     42        private final static float GAUSSIAN_CUT_OFF = 0.005f;
     43        private final static float MAGNITUDE_SCALE = 100F;
     44        private final static float MAGNITUDE_LIMIT = 1000F;
     45        private final static int MAGNITUDE_MAX = (int) (MAGNITUDE_SCALE * MAGNITUDE_LIMIT);
     46
     47        // fields
     48
     49        private int height;
     50        private int width;
     51        private int picsize;
     52        private int[] data;
     53        private int[] magnitude;
     54        private BufferedImage sourceImage;
     55        private BufferedImage edgesImage;
     56
     57        private float gaussianKernelRadius;
     58        private float lowThreshold;
     59        private float highThreshold;
     60        private int gaussianKernelWidth;
     61        private boolean contrastNormalized;
     62
     63        private float[] xConv;
     64        private float[] yConv;
     65        private float[] xGradient;
     66        private float[] yGradient;
     67
     68        // constructors
     69
     70        /**
     71         * Constructs a new detector with default parameters.
     72         */
     73
     74        public CannyEdgeDetector() {
     75                lowThreshold = 2.5f;
     76                highThreshold = 7.5f;
     77                gaussianKernelRadius = 2f;
     78                gaussianKernelWidth = 16;
     79                contrastNormalized = false;
     80        }
     81
     82        // accessors
     83
     84        /**
     85         * The image that provides the luminance data used by this detector to
     86         * generate edges.
     87         *
     88         * @return the source image, or null
     89         */
     90
     91        public BufferedImage getSourceImage() {
     92                return sourceImage;
     93        }
     94
     95        /**
     96         * Specifies the image that will provide the luminance data in which edges
     97         * will be detected. A source image must be set before the process method
     98         * is called.
     99         *
    100         * @param image a source of luminance data
    101         */
    102
    103        public void setSourceImage(BufferedImage image) {
    104                sourceImage = image;
    105        }
    106
    107        /**
    108         * Obtains an image containing the edges detected during the last call to
    109         * the process method. The buffered image is an opaque image of type
    110         * BufferedImage.TYPE_INT_ARGB in which edge pixels are white and all other
    111         * pixels are black.
    112         *
    113         * @return an image containing the detected edges, or null if the process
    114         * method has not yet been called.
    115         */
    116
    117        public BufferedImage getEdgesImage() {
    118                return edgesImage;
    119        }
    120
    121        /**
    122         * Sets the edges image. Calling this method will not change the operation
    123         * of the edge detector in any way. It is intended to provide a means by
    124         * which the memory referenced by the detector object may be reduced.
    125         *
    126         * @param edgesImage expected (though not required) to be null
    127         */
    128
    129        public void setEdgesImage(BufferedImage edgesImage) {
    130                this.edgesImage = edgesImage;
    131        }
    132
    133        /**
    134         * The low threshold for hysteresis. The default value is 2.5.
    135         *
    136         * @return the low hysteresis threshold
    137         */
    138
    139        public float getLowThreshold() {
    140                return lowThreshold;
    141        }
    142
    143        /**
    144         * Sets the low threshold for hysteresis. Suitable values for this parameter
    145         * must be determined experimentally for each application. It is nonsensical
    146         * (though not prohibited) for this value to exceed the high threshold value.
    147         *
    148         * @param threshold a low hysteresis threshold
    149         */
    150
    151        public void setLowThreshold(float threshold) {
    152                if (threshold < 0) throw new IllegalArgumentException();
    153                lowThreshold = threshold;
    154        }
    155
    156        /**
    157         * The high threshold for hysteresis. The default value is 7.5.
    158         *
    159         * @return the high hysteresis threshold
    160         */
    161
    162        public float getHighThreshold() {
    163                return highThreshold;
    164        }
    165
    166        /**
    167         * Sets the high threshold for hysteresis. Suitable values for this
    168         * parameter must be determined experimentally for each application. It is
    169         * nonsensical (though not prohibited) for this value to be less than the
    170         * low threshold value.
    171         *
    172         * @param threshold a high hysteresis threshold
    173         */
    174
    175        public void setHighThreshold(float threshold) {
    176                if (threshold < 0) throw new IllegalArgumentException();
    177                highThreshold = threshold;
    178        }
    179
    180        /**
    181         * The number of pixels across which the Gaussian kernel is applied.
    182         * The default value is 16.
    183         *
    184         * @return the radius of the convolution operation in pixels
    185         */
    186
    187        public int getGaussianKernelWidth() {
    188                return gaussianKernelWidth;
    189        }
    190
    191        /**
    192         * The number of pixels across which the Gaussian kernel is applied.
    193         * This implementation will reduce the radius if the contribution of pixel
    194         * values is deemed negligable, so this is actually a maximum radius.
    195         *
    196         * @param gaussianKernelWidth a radius for the convolution operation in
    197         * pixels, at least 2.
    198         */
    199
    200        public void setGaussianKernelWidth(int gaussianKernelWidth) {
    201                if (gaussianKernelWidth < 2) throw new IllegalArgumentException();
    202                this.gaussianKernelWidth = gaussianKernelWidth;
    203        }
    204
    205        /**
    206         * The radius of the Gaussian convolution kernel used to smooth the source
    207         * image prior to gradient calculation. The default value is 16.
    208         *
    209         * @return the Gaussian kernel radius in pixels
    210         */
    211
    212        public float getGaussianKernelRadius() {
    213                return gaussianKernelRadius;
    214        }
    215
    216        /**
    217         * Sets the radius of the Gaussian convolution kernel used to smooth the
    218         * source image prior to gradient calculation.
    219         *
    220         * @return a Gaussian kernel radius in pixels, must exceed 0.1f.
    221         */
    222
    223        public void setGaussianKernelRadius(float gaussianKernelRadius) {
    224                if (gaussianKernelRadius < 0.1f) throw new IllegalArgumentException();
    225                this.gaussianKernelRadius = gaussianKernelRadius;
    226        }
    227
    228        /**
    229         * Whether the luminance data extracted from the source image is normalized
    230         * by linearizing its histogram prior to edge extraction. The default value
    231         * is false.
    232         *
    233         * @return whether the contrast is normalized
    234         */
    235
    236        public boolean isContrastNormalized() {
    237                return contrastNormalized;
    238        }
    239
    240        /**
    241         * Sets whether the contrast is normalized
    242         * @param contrastNormalized true if the contrast should be normalized,
    243         * false otherwise
    244         */
    245
    246        public void setContrastNormalized(boolean contrastNormalized) {
    247                this.contrastNormalized = contrastNormalized;
    248        }
    249
    250        // methods
    251
    252        public void process() {
    253                width = sourceImage.getWidth();
    254                height = sourceImage.getHeight();
    255                picsize = width * height;
    256                initArrays();
    257                readLuminance();
    258                if (contrastNormalized) normalizeContrast();
    259                computeGradients(gaussianKernelRadius, gaussianKernelWidth);
    260                int low = Math.round(lowThreshold * MAGNITUDE_SCALE);
    261                int high = Math.round( highThreshold * MAGNITUDE_SCALE);
    262                performHysteresis(low, high);
    263                thresholdEdges();
    264                writeEdges(data);
    265        }
    266
    267        // private utility methods
    268
    269        private void initArrays() {
    270                if (data == null || picsize != data.length) {
    271                        data = new int[picsize];
    272                        magnitude = new int[picsize];
    273
    274                        xConv = new float[picsize];
    275                        yConv = new float[picsize];
    276                        xGradient = new float[picsize];
    277                        yGradient = new float[picsize];
    278                }
    279        }
    280
    281        //NOTE: The elements of the method below (specifically the technique for
    282        //non-maximal suppression and the technique for gradient computation)
    283        //are derived from an implementation posted in the following forum (with the
    284        //clear intent of others using the code):
    285        //  [url=http://forum.java.sun.com/thread.jspa?threadID=546211&start=45&tstart=0]Java 2D - canny algorithm for edge detection [Locked][/url]
    286        //My code effectively mimics the algorithm exhibited above.
    287        //Since I don't know the providence of the code that was posted it is a
    288        //possibility (though I think a very remote one) that this code violates
    289        //someone's intellectual property rights. If this concerns you feel free to
    290        //contact me for an alternative, though less efficient, implementation.
    291
    292        private void computeGradients(float kernelRadius, int kernelWidth) {
    293
    294                //generate the gaussian convolution masks
    295                float kernel[] = new float[kernelWidth];
    296                float diffKernel[] = new float[kernelWidth];
    297                int kwidth;
    298                for (kwidth = 0; kwidth < kernelWidth; kwidth++) {
    299                        float g1 = gaussian(kwidth, kernelRadius);
    300                        if (g1 <= GAUSSIAN_CUT_OFF && kwidth >= 2) break;
    301                        float g2 = gaussian(kwidth - 0.5f, kernelRadius);
    302                        float g3 = gaussian(kwidth + 0.5f, kernelRadius);
    303                        kernel[kwidth] = (g1 + g2 + g3) / 3f / (2f * (float) Math.PI * kernelRadius * kernelRadius);
    304                        diffKernel[kwidth] = g3 - g2;
    305                }
    306
    307                int initX = kwidth - 1;
    308                int maxX = width - (kwidth - 1);
    309                int initY = width * (kwidth - 1);
    310                int maxY = width * (height - (kwidth - 1));
    311
    312                //perform convolution in x and y directions
    313                for (int x = initX; x < maxX; x++) {
    314                        for (int y = initY; y < maxY; y += width) {
    315                                int index = x + y;
    316                                float sumX = data[index] * kernel[0];
    317                                float sumY = sumX;
    318                                int xOffset = 1;
    319                                int yOffset = width;
    320                                for(; xOffset < kwidth ;) {
    321                                        sumY += kernel[xOffset] * (data[index - yOffset] + data[index + yOffset]);
    322                                        sumX += kernel[xOffset] * (data[index - xOffset] + data[index + xOffset]);
    323                                        yOffset += width;
    324                                        xOffset++;
    325                                }
    326
    327                                yConv[index] = sumY;
    328                                xConv[index] = sumX;
    329                        }
    330
    331                }
    332
    333                for (int x = initX; x < maxX; x++) {
    334                        for (int y = initY; y < maxY; y += width) {
    335                                float sum = 0f;
    336                                int index = x + y;
    337                                for (int i = 1; i < kwidth; i++)
    338                                        sum += diffKernel[i] * (yConv[index - i] - yConv[index + i]);
    339
    340                                xGradient[index] = sum;
    341                        }
    342
    343                }
    344
    345                for (int x = kwidth; x < width - kwidth; x++) {
    346                        for (int y = initY; y < maxY; y += width) {
    347                                float sum = 0.0f;
    348                                int index = x + y;
    349                                int yOffset = width;
    350                                for (int i = 1; i < kwidth; i++) {
    351                                        sum += diffKernel[i] * (xConv[index - yOffset] - xConv[index + yOffset]);
    352                                        yOffset += width;
    353                                }
    354
    355                                yGradient[index] = sum;
    356                        }
    357
    358                }
    359
    360                initX = kwidth;
    361                maxX = width - kwidth;
    362                initY = width * kwidth;
    363                maxY = width * (height - kwidth);
    364                for (int x = initX; x < maxX; x++) {
    365                        for (int y = initY; y < maxY; y += width) {
    366                                int index = x + y;
    367                                int indexN = index - width;
    368                                int indexS = index + width;
    369                                int indexW = index - 1;
    370                                int indexE = index + 1;
    371                                int indexNW = indexN - 1;
    372                                int indexNE = indexN + 1;
    373                                int indexSW = indexS - 1;
    374                                int indexSE = indexS + 1;
    375
    376                                float xGrad = xGradient[index];
    377                                float yGrad = yGradient[index];
    378                                float gradMag = hypot(xGrad, yGrad);
    379
    380                                //perform non-maximal supression
    381                                float nMag = hypot(xGradient[indexN], yGradient[indexN]);
    382                                float sMag = hypot(xGradient[indexS], yGradient[indexS]);
    383                                float wMag = hypot(xGradient[indexW], yGradient[indexW]);
    384                                float eMag = hypot(xGradient[indexE], yGradient[indexE]);
    385                                float neMag = hypot(xGradient[indexNE], yGradient[indexNE]);
    386                                float seMag = hypot(xGradient[indexSE], yGradient[indexSE]);
    387                                float swMag = hypot(xGradient[indexSW], yGradient[indexSW]);
    388                                float nwMag = hypot(xGradient[indexNW], yGradient[indexNW]);
    389                                float tmp;
    390                                /*
    391                                 * An explanation of what's happening here, for those who want
    392                                 * to understand the source: This performs the "non-maximal
    393                                 * supression" phase of the Canny edge detection in which we
    394                                 * need to compare the gradient magnitude to that in the
    395                                 * direction of the gradient; only if the value is a local
    396                                 * maximum do we consider the point as an edge candidate.
    397                                 *
    398                                 * We need to break the comparison into a number of different
    399                                 * cases depending on the gradient direction so that the
    400                                 * appropriate values can be used. To avoid computing the
    401                                 * gradient direction, we use two simple comparisons: first we
    402                                 * check that the partial derivatives have the same sign (1)
    403                                 * and then we check which is larger (2). As a consequence, we
    404                                 * have reduced the problem to one of four identical cases that
    405                                 * each test the central gradient magnitude against the values at
    406                                 * two points with 'identical support'; what this means is that
    407                                 * the geometry required to accurately interpolate the magnitude
    408                                 * of gradient function at those points has an identical
    409                                 * geometry (upto right-angled-rotation/reflection).
    410                                 *
    411                                 * When comparing the central gradient to the two interpolated
    412                                 * values, we avoid performing any divisions by multiplying both
    413                                 * sides of each inequality by the greater of the two partial
    414                                 * derivatives. The common comparand is stored in a temporary
    415                                 * variable (3) and reused in the mirror case (4).
    416                                 *
    417                                 */
    418                                if (xGrad * yGrad <= (float) 0 /*(1)*/
    419                                        ? Math.abs(xGrad) >= Math.abs(yGrad) /*(2)*/
    420                                                ? (tmp = Math.abs(xGrad * gradMag)) >= Math.abs(yGrad * neMag - (xGrad + yGrad) * eMag) /*(3)*/
    421                                                        && tmp > Math.abs(yGrad * swMag - (xGrad + yGrad) * wMag) /*(4)*/
    422                                                : (tmp = Math.abs(yGrad * gradMag)) >= Math.abs(xGrad * neMag - (yGrad + xGrad) * nMag) /*(3)*/
    423                                                        && tmp > Math.abs(xGrad * swMag - (yGrad + xGrad) * sMag) /*(4)*/
    424                                        : Math.abs(xGrad) >= Math.abs(yGrad) /*(2)*/
    425                                                ? (tmp = Math.abs(xGrad * gradMag)) >= Math.abs(yGrad * seMag + (xGrad - yGrad) * eMag) /*(3)*/
    426                                                        && tmp > Math.abs(yGrad * nwMag + (xGrad - yGrad) * wMag) /*(4)*/
    427                                                : (tmp = Math.abs(yGrad * gradMag)) >= Math.abs(xGrad * seMag + (yGrad - xGrad) * sMag) /*(3)*/
    428                                                        && tmp > Math.abs(xGrad * nwMag + (yGrad - xGrad) * nMag) /*(4)*/
    429                                        ) {
    430                                        magnitude[index] = gradMag >= MAGNITUDE_LIMIT ? MAGNITUDE_MAX : (int) (MAGNITUDE_SCALE * gradMag);
    431                                        //NOTE: The orientation of the edge is not employed by this
    432                                        //implementation. It is a simple matter to compute it at
    433                                        //this point as: Math.atan2(yGrad, xGrad);
    434                                } else {
    435                                        magnitude[index] = 0;
    436                                }
    437                        }
    438                }
    439        }
    440
    441        //NOTE: It is quite feasible to replace the implementation of this method
    442        //with one which only loosely approximates the hypot function. I've tested
    443        //simple approximations such as Math.abs(x) + Math.abs(y) and they work fine.
    444        private float hypot(float x, float y) {
    445                if (x == 0f) return y;
    446                if (y == 0f) return x;
    447                return (float) Math.sqrt(x * x + y * y);
    448        }
    449
    450        private float gaussian(float x, float sigma) {
    451                return (float) Math.exp(-(x * x) / (2f * sigma * sigma));
    452        }
    453
    454        private void performHysteresis(int low, int high) {
    455                //NOTE: this implementation reuses the data array to store both
    456                //luminance data from the image, and edge intensity from the processing.
    457                //This is done for memory efficiency, other implementations may wish
    458                //to separate these functions.
    459                Arrays.fill(data, 0);
    460
    461                int offset = 0;
    462                for (int x = 0; x < width; x++) {
    463                        for (int y = 0; y < height; y++) {
    464                                if (data[offset] == 0 && magnitude[offset] >= high) {
    465                                        follow(x, y, offset, low);
    466                                }
    467                                offset++;
    468                        }
    469                }
    470        }
    471
    472        private void follow(int x1, int y1, int i1, int threshold) {
    473                int x0 = x1 == 0 ? x1 : x1 - 1;
    474                int x2 = x1 == width - 1 ? x1 : x1 + 1;
    475                int y0 = y1 == 0 ? y1 : y1 - 1;
    476                int y2 = y1 == height -1 ? y1 : y1 + 1;
    477
    478                data[i1] = magnitude[i1];
    479                for (int x = x0; x <= x2; x++) {
    480                        for (int y = y0; y <= y2; y++) {
    481                                int i2 = x + y * width;
    482                                if ((y != y1 || x != x1)
    483                                        && data[i2] == 0
    484                                        && magnitude[i2] >= threshold) {
    485                                        follow(x, y, i2, threshold);
    486                                        return;
    487                                }
    488                        }
    489                }
    490        }
    491
    492        private void thresholdEdges() {
    493                for (int i = 0; i < picsize; i++) {
    494                        data[i] = data[i] > 0 ? -1 : 0xff000000;
    495                }
    496        }
    497
    498        private int luminance(float r, float g, float b) {
    499                return Math.round(0.299f * r + 0.587f * g + 0.114f * b);
    500        }
    501
    502        private void readLuminance() {
    503                int type = sourceImage.getType();
    504                if (type == BufferedImage.TYPE_INT_RGB || type == BufferedImage.TYPE_INT_ARGB) {
    505                        int[] pixels = (int[]) sourceImage.getData().getDataElements(0, 0, width, height, null);
    506                        for (int i = 0; i < picsize; i++) {
    507                                int p = pixels[i];
    508                                int r = (p & 0xff0000) >> 16;
    509                                int g = (p & 0xff00) >> 8;
    510                                int b = p & 0xff;
    511                                data[i] = luminance(r, g, b);
    512                        }
    513                } else if (type == BufferedImage.TYPE_BYTE_GRAY) {
    514                        byte[] pixels = (byte[]) sourceImage.getData().getDataElements(0, 0, width, height, null);
    515                        for (int i = 0; i < picsize; i++) {
    516                                data[i] = (pixels[i] & 0xff);
    517                        }
    518                } else if (type == BufferedImage.TYPE_USHORT_GRAY) {
    519                        short[] pixels = (short[]) sourceImage.getData().getDataElements(0, 0, width, height, null);
    520                        for (int i = 0; i < picsize; i++) {
    521                                data[i] = (pixels[i] & 0xffff) / 256;
    522                        }
    523                } else if (type == BufferedImage.TYPE_3BYTE_BGR) {
    524            byte[] pixels = (byte[]) sourceImage.getData().getDataElements(0, 0, width, height, null);
    525            int offset = 0;
    526            for (int i = 0; i < picsize; i++) {
    527                int b = pixels[offset++] & 0xff;
    528                int g = pixels[offset++] & 0xff;
    529                int r = pixels[offset++] & 0xff;
    530                data[i] = luminance(r, g, b);
    531            }
    532        } else {
    533                        throw new IllegalArgumentException("Unsupported image type: " + type);
    534                }
    535        }
    536
    537        private void normalizeContrast() {
    538                int[] histogram = new int[256];
    539                for (int i = 0; i < data.length; i++) {
    540                        histogram[data[i]]++;
    541                }
    542                int[] remap = new int[256];
    543                int sum = 0;
    544                int j = 0;
    545                for (int i = 0; i < histogram.length; i++) {
    546                        sum += histogram[i];
    547                        int target = sum*255/picsize;
    548                        for (int k = j+1; k <=target; k++) {
    549                                remap[k] = i;
    550                        }
    551                        j = target;
    552                }
    553
    554                for (int i = 0; i < data.length; i++) {
    555                        data[i] = remap[data[i]];
    556                }
    557        }
    558
    559        private void writeEdges(int pixels[]) {
    560                //NOTE: There is currently no mechanism for obtaining the edge data
    561                //in any other format other than an INT_ARGB type BufferedImage.
    562                //This may be easily remedied by providing alternative accessors.
    563                if (edgesImage == null) {
    564                        edgesImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);
    565                }
    566                edgesImage.getWritableTile(0, 0).setDataElements(0, 0, width, height, pixels);
    567        }
    Last edited by helloworld922; March 11th, 2010 at 03:50 PM.


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,607
    My Mood
    Hungover
    Thanks
    145
    Thanked 658 Times in 563 Posts

    Default Re: Canny Edge Detection

    Please don't resurrect old threads. Continue this conversation in your other post: canny algorithm
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. How to detect brightest spot among all spots?
    By BharatT in forum Java Theory & Questions
    Replies: 4
    Last Post: February 6th, 2009, 09:12 PM
  2. String substring, concatenation operation on linked list
    By oaks12 in forum Collections and Generics
    Replies: 1
    Last Post: January 15th, 2009, 07:12 AM