The algorithm consists of four steps:
- Filter edges using a convolutional filter.
- Thin edges depending on it's gradient and direction.
- Threshold the image so all pixels where it's gradient is below a minimum threshold becomes black, all pixels where it's gradient is above a maximum threshold becomes white, and the rest becomes gray.
- Trace the edges so all gray pixels connected to white becomes white, and the rest becomes black.
Filter edges
There is no much to explain here, we just pick up some edge detector filter, and apply it to the image, this time we will also store the direction of the gradient for the next step. Sobel is the most commonly used here.
inline void sobel(const QImage &image,
QVector<int> &gradient,
QVector<int> &direction)
{
int size = image.width() * image.height();
gradient.resize(size);
direction.resize(size);
for (int y = 0; y < image.height(); y++) {
size_t yOffset = y * image.width();
const quint8 *grayLine = image.constBits() + yOffset;
const quint8 *grayLine_m1 = y < 1? grayLine: grayLine - image.width();
const quint8 *grayLine_p1 = y >= image.height() - 1? grayLine: grayLine + image.width();
int *gradientLine = gradient.data() + yOffset;
int *directionLine = direction.data() + yOffset;
for (int x = 0; x < image.width(); x++) {
int x_m1 = x < 1? x: x - 1;
int x_p1 = x >= image.width() - 1? x: x + 1;
int gradX = grayLine_m1[x_p1]
+ 2 * grayLine[x_p1]
+ grayLine_p1[x_p1]
- grayLine_m1[x_m1]
- 2 * grayLine[x_m1]
- grayLine_p1[x_m1];
int gradY = grayLine_m1[x_m1]
+ 2 * grayLine_m1[x]
+ grayLine_m1[x_p1]
- grayLine_p1[x_m1]
- 2 * grayLine_p1[x]
- grayLine_p1[x_p1];
gradientLine[x] = qAbs(gradX) + qAbs(gradY);
/* Gradient directions are classified in 4 possible cases
*
* dir 0
*
* x x x
* - - -
* x x x
*
* dir 1
*
* x x /
* x / x
* / x x
*
* dir 2
*
* \ x x
* x \ x
* x x \
*
* dir 3
*
* x | x
* x | x
* x | x
*/
if (gradX == 0 && gradY == 0)
directionLine[x] = 0;
else if (gradX == 0)
directionLine[x] = 3;
else {
qreal a = 180. * atan(qreal(gradY) / gradX) / M_PI;
if (a >= -22.5 && a < 22.5)
directionLine[x] = 0;
else if (a >= 22.5 && a < 67.5)
directionLine[x] = 1;
else if (a >= -67.5 && a < -22.5)
directionLine[x] = 2;
else
directionLine[x] = 3;
}
}
}
}
Thin edges
In this step we loop over each pixel, and compare the pixels with its neighbors in the same direction of the gradient, and if the gradient module is lower than at least one of its neighbors, make it black. Edge thinning is also called Non-Maximum Suppression.
inline QVector<int> thining(int width, int height,
const QVector<int> &gradient,
const QVector<int> &direction)
{
QVector<int> thinned(gradient.size());
for (int y = 0; y < height; y++) {
int yOffset = y * width;
const int *gradientLine = gradient.constData() + yOffset;
const int *gradientLine_m1 = y < 1? gradientLine: gradientLine - width;
const int *gradientLine_p1 = y >= height - 1? gradientLine: gradientLine + width;
const int *directionLine = direction.constData() + yOffset;
int *thinnedLine = thinned.data() + yOffset;
for (int x = 0; x < width; x++) {
int x_m1 = x < 1? 0: x - 1;
int x_p1 = x >= width - 1? x: x + 1;
int direction = directionLine[x];
int pixel = 0;
if (direction == 0) {
/* x x x
* - - -
* x x x
*/
if (gradientLine[x] < gradientLine[x_m1]
|| gradientLine[x] < gradientLine[x_p1])
pixel = 0;
else
pixel = gradientLine[x];
} else if (direction == 1) {
/* x x /
* x / x
* / x x
*/
if (gradientLine[x] < gradientLine_m1[x_p1]
|| gradientLine[x] < gradientLine_p1[x_m1])
pixel = 0;
else
pixel = gradientLine[x];
} else if (direction == 2) {
/* \ x x
* x \ x
* x x \
*/
if (gradientLine[x] < gradientLine_m1[x_m1]
|| gradientLine[x] < gradientLine_p1[x_p1])
pixel = 0;
else
pixel = gradientLine[x];
} else {
/* x | x
* x | x
* x | x
*/
if (gradientLine[x] < gradientLine_m1[x]
|| gradientLine[x] < gradientLine_p1[x])
pixel = 0;
else
pixel = gradientLine[x];
}
thinnedLine[x] = pixel;
}
}
return thinned;
}
Threshold
As explained before, all pixels below a minimum threshold becomes black, all pixels above a maximum threshold becomes white, the rest becomes gray.
inline QVector<int> threshold(int thLow, int thHi,
const QVector<int> &image)
{
QVector<int> thresholded(image.size());
for (int i = 0; i < image.size(); i++)
thresholded[i] = image[i] <= thLow? 0:
image[i] >= thHi? 255:
127;
return thresholded;
}
Trace edges
Finally, we loop over every pixel, look for white pixels, and recursively mark all gray neighbors as white. At end, all remaining gray pixels are marked as black. This is also called Hysteresis Threshold.
void trace(int width, int height, QVector<int> &image, int x, int y)
{
int yOffset = y * width;
int *cannyLine = image.data() + yOffset;
if (cannyLine[x] != 255)
return;
for (int j = -1; j < 2; j++) {
int nextY = y + j;
if (nextY < 0 || nextY >= height)
continue;
int *cannyLineNext = cannyLine + j * width;
for (int i = -1; i < 2; i++) {
int nextX = x + i;
if (i == j || nextX < 0 || nextX >= width)
continue;
if (cannyLineNext[nextX] == 127) {
cannyLineNext[nextX] = 255;
trace(width, height, image, nextX, nextY);
}
}
}
}
QVector<int> hysteresis(int width, int height,
const QVector<int> &image)
{
QVector<int> canny(image);
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
trace(width, height, canny, x, y);
for (int i = 0; i < canny.size(); i++)
if (canny[i] == 127)
canny[i] = 0;
return canny;
}
Download the source code for this post.
No comments:
Post a Comment