/**********************************************************************
* @author Jason Altschuler
*
* Description of EdgeDetectors repo
**********************************************************************/
** PURPOSE: Detect edges in images
** ALGORITHMS: This repo contains 5 different edge detection algorithms:
1. Canny edge detector (also commonly called the "optimal edge detector")
2. Laplacian edge detector
3. Sobel edge detector
4. Prewitt edge detector
5. Roberts Cross edge detector
3, 4, and 5 are all very similar. Descriptions of each algorithm below.
** OVERVIEW:
The standard CV definition of edge is:
1. Where change in intensity is very positive (first derivative is large)
2. One-pixel thick
To achieve part 1 of the edge definition, Canny, Sobel, Prewitt, and Roberts
(all but Laplacian) all use discrete kernel convolutions (discrete
approximations of 2D Fourier Transforms) to calculate the image's first
derivative of the image in each direction. They then calculate the
magnitude of the gradient and find pixels where this value is high.
In contrast, Laplacian uses discrete kernel convolutions to approximate
the image's second derivative, and identifies pixels where this is 0. However,
in practice, this often also identifies false edges because it
finds local extrema in 1st derivative (so local min as well as local max).
To achieve part 2 of the edge definition, all 5 of the edge detectors
also apply non-maximum suppression. Essentially, for each pixel that has
passed the above tests, find the angle tangent to the edge direction and
round it to the nearest 45 degrees. If either of the pixel's two neighbors
in that direction have a higher gradient magnitude, suppress the original
pixel. This ensures that the detected edges are always one-pixel thick.
In addition, Canny and Laplacian both apply Gaussian smoothing (also
called Gaussian blurring) in the beginning to reduce noise. Essentially,
this applies a Gaussian filter to the image, expressing each pixel's
intensity as a weighted linear combination of its neighbors and itself.
This reduces noise, but also makes the edges less precise.
Canny, which is by far the most involved edge detection algorithm,
has a few extra steps. After Gaussian blurring, calculating the
gradient magnitudes and edge angles, and non-maximum suppression,
we then perform hysteresis and edge tracing. Essentially, hysteresis
is double thresholding. We automatically calculate a low and high
threshold (by performing KMeans++ with 3 clusters in 1 dimension).
Edges with gradient magnitude > high threshold are strong edges.
Edges with gradient magnitude between low and high threshold are weak edges.
The strong edges are guaranteed to be edges, but the weak edges
are only considered edges if they are connected a strong edge.
This is performed by a simple depth-first search.
An improvement to Canny that is implemented here is that we can
discard edges which consist of few pixels (the exact number is a
user-defined input parameter).
** EXAMPLE RUNS: There are full examples in the main method of each
edge detector java file (CannyEdgeDetector.java, SobelEdgeDetector.java, etc.)
There is also another example in EdgeDetectorViewer.java
** DEMOS: See the screenshots in the folder: demos/