Image edge detection

By
Edge detection is a fundamental tool in image processing, machine vision and computer vision.

In this post we're going to take a look at a very basic edge detection algorithm, which takes into account a predefined tolerance value that can be adjusted to detect arbitrary fine details in a given image.

# Algorithm

The algorithm is extremely simple; it begins by iterating over each pixel in the image, then, for each pixel, it checks its neighbors.

+-------+-------+-------+
|       |       |       |
|   A   |   B   |   C   |
|       |       |       |
+-------+-------+-------+
|       |       |       |
|   D   |       |   E   |
|       |       |       |
+-------+-------+-------+
|       |       |       |
|   F   |   G   |   H   |
|       |       |       |
+-------+-------+-------+

If any two opposite neighbors differ in intensity by more than a predefined tolerance, then it marks the current pixel as part of an edge.

 The comparison is done by taking the absolute difference of each two opposite neighbors and mapping it to a percentage, which is then compared to the value of the tolerance:

abs(A - H) / 255 * 100 > t
abs(B - G) / 255 * 100 > t
abs(C - F) / 255 * 100 > t
abs(D - E) / 255 * 100 > t

In code, this can be written as: 
   abs(img[y  ][x-1] - img[y  ][x+1]) / 255 * 100 > t
or abs(img[y-1][x  ] - img[y+1][x  ]) / 255 * 100 > t
or abs(img[y-1][x-1] - img[y+1][x+1]) / 255 * 100 > t
or abs(img[y-1][x+1] - img[y+1][x-1]) / 255 * 100 > t

where "x" and "y" are the positions of the current pixel, and "t" is the tolerance value (ranging from 0 to 100).

If either one of the above statements is true, then an edge will be set at the current position:

edge[y][x] = true

Optionally, after this step, a noise removal algorithm can be used to remove unwanted edges, such as isolated pixels that are not connected to anything:

if (edge[y][x] == true) {
    if (!edge[y  ][x+1]
    and !edge[y  ][x-1]
    and !edge[y-1][x-1]
    and !edge[y-1][x  ]
    and !edge[y-1][x+1]
    and !edge[y+1][x-1]
    and !edge[y+1][x  ]
    and !edge[y+1][x+1]) {
        edge[y][x] = false
    }
}

# Conclusion

The described algorithm is simple, beautiful and easy to implement. Because it makes decisions based on a given tolerance, is easier to adjust it to a particular need where, for example, when a large amount of detail is required.

# Implementation

An implementation of the described algorithm can be found bellow:

Bonus, not quite an edge detector, but something similar, using a different method:

Comments

Post a Comment