Canny Edge Detector in C

Question

I am looking for a bit of clarification on how the algorithms implemented in Canny edge detection - Wikipedia entry - work. It seems pretty straightforward to perform noise reduction using a 2D Gaussian filter, but I have heard that using two 1D filters - how is this accomplished? It's also simple to calculate the gradient and edge direction. However, when performing non-maximum suppression is there a neat trick to getting the rounded angle? What I'm currently doing is dividing the edge direction (theta) value by pi/4, casting it to an integer and using a switch statement. But, how does one handle the negative theta values - ie should -pi/4 be handled the same way as 3*pi/4 or the same as pi/4?

Any advice/links are much appreciated!

Thanks, Ben

Answer 1

Gauss distribution:

[constants are omitted for simplicity]

g2d(x,y)=exp(-xx-yy)=exp(-x^2) * exp(-y^2)=g1d(x) * g1d(y)

Thus is can be separated into multiplication of 1d-distributions. And thus filtration can be done first in x-direction (independently on each row) and then in y-direction (independently on each column)

rounded angle:

If angle is outside of [0..pi) it's correct in this case to add/subtract pi as many times as needed (or use function fmod), and for [0..pi) all is clear.

Also depending on platform it may be better to avoid arctan usage at all: you can draw a circle, divide it in 4 areas and produce a set of conditions for gradient components which use only arithmetic operations and give you answer in which area direction is.

Answer 2

Do you have to implement it yourself or can you use a library? OpenCv is a huge C library of algorithms in computer vision including edge detection: http://opencv.willowgarage.com/documentation/image_processing.html?highlight=canny#cvCanny .

If you are doing it for educational purposes, I suggest considering the purchase of a good text on computer vision. Almost any introductory text will discuss filtering with the Gaussian (and the well documented 1d trick) as well as canny edge detection and non-maximum suppression.

Answer 3

I think that -pi/4 should be handled the same way as 3*pi/4, because both define the same diagonal.

If you can normalize the angle of the gradient so that it lies in [0, pi), then you could use a simple function like the following to quantize the angle:

enum Angle
{
    HORIZONTAL,
    DIAG_UP,
    VERTICAL,
    DIAG_DOWN
};

Angle quantizeAngle(double theta)
{
    if (0 <= theta && theta < PI/8.0) || (7.0*PI/8.0 <= theta && theta < PI))
        return HORIZONTAL;
    else if (PI/8.0 <= theta && theta < 3.0*PI/8.0)
        return DIAG_UP;
    else if (3.0*PI/8.0 <= theta && theta < 5.0*PI/8.0)
        return VERTICAL;
    else 
        return DIAG_DOWN;
}