Edge Detection
Always filter noise before using edge detection to improve the results.
Derivative Filters
Derivative (gradient) filters are used to enhance edges as they can highlight sudden changes in an image.
The gradient operator is a vector function of a scalar field:
\[\nabla f=\begin{pmatrix}\frac{\partial f}{\partial x}\\\frac{\partial f}{\partial y}\end{pmatrix}\]As we don’t have a continuous domain we can use a finite approach:
\[\begin{aligned} \frac{\partial f}{\partial x}[x,y]&\approx f(x+1,y)-f(x,y)\\ \frac{\partial f}{\partial y}[x,y]&\approx f(x,y+1)-f(x,y) \end{aligned}\]gradient of an image $f$ is:
\[\nabla f=\left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right)\]Derivative of Images
Since pixel values represent intensities, gradient points are in the direction of the maximum change in intensity:
-
Change in $x$ direction:
\[\nabla f=\left(\frac{\partial f}{\partial x},0\right)\] -
Change in $y$ direction:
\[\nabla f=\left(0,\frac{\partial f}{\partial y}\right)\] -
Change diagonally:
\[\nabla f=\left(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y}\right)\]
The edge strength is given by the magnitude of the gradient:
\[\left\vert\nabla f\right\vert=\sqrt{\left(\frac{\partial f}{\partial x}\right)^2+\left(\frac{\partial f}{\partial y}\right)^2}\]The direction of the gradient is given by:
\[\theta=\tan^{-1}\left(\frac{\frac{\partial f}{\partial x}}{\frac{\partial f}{\partial y}}\right)\]Gradient Operators
Edge detection can be completed using small convolution filters, usually two or three pixels square.
Given an image $I$ and a derivate kernel $d$, a pixel value $p$ is computed as a convolution:
\[p=d*h_p(I)\]Three common gradient operators are:
-
Roberts:
\[\begin{pmatrix}1&0\\0&-1\end{pmatrix}\begin{pmatrix}0&1\\-1&0\end{pmatrix}\] -
Prewitt:
\[\begin{pmatrix}-1&-1&-1\\0&0&0\\1&1&1\end{pmatrix}\begin{pmatrix}-1&0&1\\-1&0&1\\-1&0&1\end{pmatrix}\] -
Prewitt:
\[\begin{pmatrix}-1&-2&-1\\0&0&0\\1&2&1\end{pmatrix}\begin{pmatrix}-1&0&1\\-2&0&2\\-1&0&1\end{pmatrix}\]
These operators sum to zero, so a region with no edges gives a zero response.
To use the operators:
- Sum the mask multiplies by the image (element by element) for each operator.
- Take the modulus of both components and add them both together.
Canny Edge Detection
Canny edge detection is good for detecting weak edges. It consists of:
-
Gaussian Blur
We can modify $\sigma$ to change the performance of the edge detection.
- Sobel Operator
-
Calculate Edge Strength (magnitude of Sobel operator)
This is checked to ensure that is a a true edge (local maxima).
-
Calculate the edge angle (arc-tan of the ratio of Sobel components)
This is rounded to 0, 45, 90 and 135 degrees to find the edge direction.
A large $\sigma$ for the Gaussian blur suits wide edges and vice-versa.
Hough Transform
Pronounced “Huff”, it is used to detect lines and other geometric shapes.
Any line can be described by an equation in the form:
\[x\cos\theta+y\sin\theta=\rho\]where $\rho$ and $\theta$ are parameters that specify the line. Any point on the same line has the same values for $\rho$ and $\theta$.
Algorithm for Detecting Straight Lines
- Detect Edges (Canny)
- Map the edges points to Hough Space
- Accumulate the number of points.
- Interpret the accumulator values to interpret lines of infinite length.
This is a computationally intensive task.