Canny edge detector: Difference between revisions
(More types and stronger C code) |
(Better C code) |
||
Line 26: | Line 26: | ||
* Note: the magic number has been removed from the bmpfile_header structure |
* Note: the magic number has been removed from the bmpfile_header structure |
||
* since it causes alignment problems |
* since it causes alignment problems |
||
* |
* bmpfile_magic should be written/read first |
||
* followed by the |
* followed by the |
||
* |
* bmpfile_header |
||
* [this avoids compiler-specific alignment pragmas etc.] |
* [this avoids compiler-specific alignment pragmas etc.] |
||
*/ |
*/ |
||
typedef struct { |
|||
⚫ | |||
unsigned char magic[2]; |
unsigned char magic[2]; |
||
⚫ | |||
}; |
|||
typedef struct { |
|||
⚫ | |||
uint32_t filesz; |
uint32_t filesz; |
||
uint16_t creator1; |
uint16_t creator1; |
||
uint16_t creator2; |
uint16_t creator2; |
||
uint32_t bmp_offset; |
uint32_t bmp_offset; |
||
⚫ | |||
}; |
|||
typedef struct { |
typedef struct { |
||
Line 72: | Line 72: | ||
{ |
{ |
||
FILE *filePtr; // our file pointer |
FILE *filePtr; // our file pointer |
||
bmpfile_magic mag; |
|||
bmpfile_header bitmapFileHeader; // our bitmap file header |
|||
pixel_t *bitmapImage; // store image data |
pixel_t *bitmapImage; // store image data |
||
size_t i; |
size_t i; |
||
unsigned char c; |
unsigned char c; |
||
filePtr = fopen(filename,"r"); |
filePtr = fopen(filename, "r"); |
||
if (filePtr == NULL) { |
if (filePtr == NULL) { |
||
perror("fopen()"); |
perror("fopen()"); |
||
Line 84: | Line 84: | ||
} |
} |
||
assert(fread(&mag, sizeof( |
assert(fread(&mag, sizeof(bmpfile_magic), 1, filePtr) == 1); |
||
// verify that this is a bmp file by check bitmap id |
// verify that this is a bmp file by check bitmap id |
||
// warning: dereferencing type-punned pointer will break |
// warning: dereferencing type-punned pointer will break |
||
// strict-aliasing rules [-Wstrict-aliasing] |
// strict-aliasing rules [-Wstrict-aliasing] |
||
if (*((uint16_t*) |
if (*((uint16_t*)mag.magic) != 0x4D42) { |
||
fprintf(stderr, "Not a BMP file: magic=%c%c\n", mag.magic[0], mag.magic[1]); |
fprintf(stderr, "Not a BMP file: magic=%c%c\n", mag.magic[0], mag.magic[1]); |
||
fclose(filePtr); |
fclose(filePtr); |
||
Line 96: | Line 96: | ||
// read the bitmap file header |
// read the bitmap file header |
||
assert(fread(&bitmapFileHeader, sizeof( |
assert(fread(&bitmapFileHeader, sizeof(bmpfile_header), 1, filePtr) == 1); |
||
// read the bitmap info header |
// read the bitmap info header |
||
Line 108: | Line 108: | ||
// allocate enough memory for the bitmap image data |
// allocate enough memory for the bitmap image data |
||
bitmapImage = (pixel_t |
bitmapImage = (pixel_t*)malloc(bitmapInfoHeader->bmp_bytesz * sizeof(pixel_t)); |
||
// verify memory allocation |
// verify memory allocation |
||
if ( |
if (bitmapImage == NULL) { |
||
⚫ | |||
fclose(filePtr); |
fclose(filePtr); |
||
return NULL; |
return NULL; |
||
Line 120: | Line 119: | ||
for (i = 0; i < bitmapInfoHeader->bmp_bytesz; i++) { |
for (i = 0; i < bitmapInfoHeader->bmp_bytesz; i++) { |
||
assert(fread(&c, sizeof(unsigned char), 1, filePtr) == 1); |
assert(fread(&c, sizeof(unsigned char), 1, filePtr) == 1); |
||
bitmapImage[i] = (int) |
bitmapImage[i] = (int)c; |
||
} |
} |
||
Line 134: | Line 133: | ||
int save_bmp(const char *filename, const BITMAPINFOHEADER *bmp_ih, const pixel_t *data) |
int save_bmp(const char *filename, const BITMAPINFOHEADER *bmp_ih, const pixel_t *data) |
||
{ |
{ |
||
⚫ | |||
unsigned int offset = |
|||
⚫ | |||
sizeof(struct bmpfile_magic) |
|||
⚫ | |||
+ sizeof(BITMAPINFOHEADER) |
|||
⚫ | |||
bmpfile_header bmp_fh = { |
|||
.filesz = offset + bmp_ih->bmp_bytesz, |
.filesz = offset + bmp_ih->bmp_bytesz, |
||
.creator1 = 0, |
.creator1 = 0, |
||
Line 147: | Line 143: | ||
}; |
}; |
||
bmpfile_magic mag = {{0x42, 0x4d}}; |
|||
rgb_t color = {0, 0, 0, 0}; |
rgb_t color = {0, 0, 0, 0}; |
||
size_t i; |
size_t i; |
||
Line 155: | Line 151: | ||
return 1; |
return 1; |
||
fwrite(&mag, 1, sizeof( |
fwrite(&mag, 1, sizeof(bmpfile_magic), fp); |
||
fwrite(&bmp_fh, 1, sizeof( |
fwrite(&bmp_fh, 1, sizeof(bmpfile_header), fp); |
||
fwrite(bmp_ih, 1, sizeof(BITMAPINFOHEADER), fp); |
fwrite(bmp_ih, 1, sizeof(BITMAPINFOHEADER), fp); |
||
Line 170: | Line 166: | ||
// fwrite(data, 1, bmp_ih->bmp_bytesz, fp); |
// fwrite(data, 1, bmp_ih->bmp_bytesz, fp); |
||
for (i = 0; i < bmp_ih->bmp_bytesz; i++) { |
for (i = 0; i < bmp_ih->bmp_bytesz; i++) { |
||
unsigned char c = (unsigned char) |
unsigned char c = (unsigned char)data[i]; |
||
fwrite(&c, sizeof(unsigned char), 1, fp); |
fwrite(&c, sizeof(unsigned char), 1, fp); |
||
} |
} |
||
Line 211: | Line 206: | ||
if (norm) |
if (norm) |
||
pixel = MAX_BRIGHTNESS * (pixel - min) / (max - min); |
pixel = MAX_BRIGHTNESS * (pixel - min) / (max - min); |
||
out[n * nx + m] = (pixel_t) |
out[n * nx + m] = (pixel_t)pixel; |
||
} |
} |
||
} |
} |
||
Line 307: | Line 302: | ||
dir = (float)(fmod(atan2(after_Gy[c], after_Gx[c]) + M_PI, M_PI) / M_PI) * 8; |
dir = (float)(fmod(atan2(after_Gy[c], after_Gx[c]) + M_PI, M_PI) / M_PI) * 8; |
||
if ( |
if (((dir <= 1 || dir > 7) && G[c] > G[ee] && G[c] > G[ww]) || // 0 deg |
||
|| |
((dir > 1 && dir <= 3) && G[c] > G[nw] && G[c] > G[se]) || // 45 deg |
||
((dir > |
((dir > 3 && dir <= 5) && G[c] > G[nn] && G[c] > G[ss]) || // 90 deg |
||
⚫ | |||
⚫ | |||
((dir > 3 && dir <= 5) && G[c] > G[nn] && G[c] > G[ss]) // 90 deg |
|||
|| |
|||
⚫ | |||
) |
|||
nms[c] = G[c]; |
nms[c] = G[c]; |
||
else |
else |
||
Line 351: | Line 342: | ||
edges[nedges++] = nbs[k]; |
edges[nedges++] = nbs[k]; |
||
} |
} |
||
} while(nedges > 0); |
} while (nedges > 0); |
||
} |
} |
||
c++; |
c++; |
||
Line 372: | Line 363: | ||
bitmap_data = load_bmp(argv[1], &ih); |
bitmap_data = load_bmp(argv[1], &ih); |
||
if (bitmap_data == NULL) |
|||
⚫ | |||
temp_image = (pixel_t*)malloc(ih.bmp_bytesz * sizeof(pixel_t)); |
temp_image = (pixel_t*)malloc(ih.bmp_bytesz * sizeof(pixel_t)); |
||
if (temp_image == NULL) |
|||
⚫ | |||
printf("Info: %d x %d x %d\n", ih.width, ih.height, ih.bitspp); |
printf("Info: %d x %d x %d\n", ih.width, ih.height, ih.bitspp); |
Revision as of 19:56, 9 March 2012
Task: Write a program that performs so-called canny edge detection on an image. The algorithm consists of the following steps:
- Noise reduction. May be performed by Gaussian filter.
- Compute intensity gradient (matrices and ) and its magnitude .
May be performed by convolution of an image with Sobel operators. - Non-maximum suppression. For each pixel compute the orientation of intensity gradient vector: . Transform angle to one of four directions: 0, 45, 90, 135 degrees. Compute new array : if
where is the current pixel, and are the two neighbour pixels in the direction of gradient, then , otherwise . Nonzero pixels in resulting array correspond to local maxima of in direction . - Tracing edges with hysteresis. At this stage two thresholds for the values of are introduced: and . Starting from pixels with find all paths of pixels with and put them to the resulting image.
C
The following program reads an 8 bits per pixel grayscale BMP file and saves the result to `out.bmp'. Compile with `-lm'. <lang c>#include <stdint.h>
- include <stdio.h>
- include <stdlib.h>
- include <float.h>
- include <math.h>
- include <string.h>
- include <assert.h>
- define MAX_BRIGHTNESS 255
/*
* Loading part taken from * http://www.vbforums.com/showthread.php?t=261522 * BMP info: * http://en.wikipedia.org/wiki/BMP_file_format * * Note: the magic number has been removed from the bmpfile_header structure * since it causes alignment problems * bmpfile_magic should be written/read first * followed by the * bmpfile_header * [this avoids compiler-specific alignment pragmas etc.] */
typedef struct {
unsigned char magic[2];
} bmpfile_magic;
typedef struct {
uint32_t filesz; uint16_t creator1; uint16_t creator2; uint32_t bmp_offset;
} bmpfile_header;
typedef struct {
uint32_t header_sz; int32_t width; int32_t height; uint16_t nplanes; uint16_t bitspp; uint32_t compress_type; uint32_t bmp_bytesz; int32_t hres; int32_t vres; uint32_t ncolors; uint32_t nimpcolors;
} BITMAPINFOHEADER;
typedef struct {
uint8_t r; uint8_t g; uint8_t b; uint8_t null;
} rgb_t;
BITMAPINFOHEADER ih;
// Use int instead `unsigned char' so that we can store negative values. typedef int pixel_t;
pixel_t *load_bmp(const char *filename, BITMAPINFOHEADER *bitmapInfoHeader) {
FILE *filePtr; // our file pointer bmpfile_magic mag; bmpfile_header bitmapFileHeader; // our bitmap file header pixel_t *bitmapImage; // store image data size_t i; unsigned char c;
filePtr = fopen(filename, "r"); if (filePtr == NULL) { perror("fopen()"); exit(1); }
assert(fread(&mag, sizeof(bmpfile_magic), 1, filePtr) == 1);
// verify that this is a bmp file by check bitmap id // warning: dereferencing type-punned pointer will break // strict-aliasing rules [-Wstrict-aliasing] if (*((uint16_t*)mag.magic) != 0x4D42) { fprintf(stderr, "Not a BMP file: magic=%c%c\n", mag.magic[0], mag.magic[1]); fclose(filePtr); return NULL; }
// read the bitmap file header assert(fread(&bitmapFileHeader, sizeof(bmpfile_header), 1, filePtr) == 1);
// read the bitmap info header assert(fread(bitmapInfoHeader, sizeof(BITMAPINFOHEADER), 1, filePtr) == 1);
if ( bitmapInfoHeader->compress_type != 0) fprintf(stderr, "Warning, compression is not supported.\n");
// move file point to the beginning of bitmap data fseek(filePtr, bitmapFileHeader.bmp_offset, SEEK_SET);
// allocate enough memory for the bitmap image data bitmapImage = (pixel_t*)malloc(bitmapInfoHeader->bmp_bytesz * sizeof(pixel_t));
// verify memory allocation if (bitmapImage == NULL) { fclose(filePtr); return NULL; }
// read in the bitmap image data for (i = 0; i < bitmapInfoHeader->bmp_bytesz; i++) { assert(fread(&c, sizeof(unsigned char), 1, filePtr) == 1); bitmapImage[i] = (int)c; }
// If we were using unsigned char as pixel_t, then: // fread(bitmapImage, 1, bitmapInfoHeader->bmp_bytesz, filePtr);
// close file and return bitmap image data fclose(filePtr); return bitmapImage;
}
// Return: nonzero on error. int save_bmp(const char *filename, const BITMAPINFOHEADER *bmp_ih, const pixel_t *data) {
uint32_t offset = sizeof(bmpfile_magic) + sizeof(bmpfile_header) + sizeof(BITMAPINFOHEADER) + ((1U << bmp_ih->bitspp) * 4);
bmpfile_header bmp_fh = { .filesz = offset + bmp_ih->bmp_bytesz, .creator1 = 0, .creator2 = 0, .bmp_offset = offset };
bmpfile_magic mag = Template:0x42, 0x4d; rgb_t color = {0, 0, 0, 0}; size_t i; FILE* fp = fopen(filename, "w");
if (fp == NULL) return 1;
fwrite(&mag, 1, sizeof(bmpfile_magic), fp); fwrite(&bmp_fh, 1, sizeof(bmpfile_header), fp); fwrite(bmp_ih, 1, sizeof(BITMAPINFOHEADER), fp);
// Palette for (i = 0; i < (1U << bmp_ih->bitspp); i++) { color.r = (uint8_t)i; color.g = (uint8_t)i; color.b = (uint8_t)i; fwrite(&color, 1, sizeof(rgb_t), fp); }
// We use int instead of uchar, so we can't write img in 1 call any more. // fwrite(data, 1, bmp_ih->bmp_bytesz, fp); for (i = 0; i < bmp_ih->bmp_bytesz; i++) { unsigned char c = (unsigned char)data[i]; fwrite(&c, sizeof(unsigned char), 1, fp); }
fclose(fp); return 0;
}
// if norm==1, map pixels to range 0..MAX_BRIGHTNESS void convolution(const pixel_t *in, pixel_t *out, const float *kernel,
int nx, int ny, int kn, int norm)
{
int i, j, m, n, c; int khalf = (int)floor(kn / 2.0); float pixel, min = FLT_MAX, max = FLT_MIN;
if (norm) for (m = khalf; m < nx - khalf; m++) for (n = khalf; n < ny - khalf; n++) { pixel = 0; c = 0; for (j = -khalf; j <= khalf; j++) for (i = -khalf; i <= khalf; i++) pixel += in[(n - j) * nx + m - i] * kernel[c++]; if (pixel < min) min = pixel; if (pixel > max) max = pixel; }
for (m = khalf; m < nx - khalf; m++) for (n = khalf; n < ny - khalf; n++) { pixel = 0; c = 0; for (j = -khalf; j <= khalf; j++) for (i = -khalf; i <= khalf; i++) pixel += in[(n - j) * nx + m - i] * kernel[c++];
if (norm) pixel = MAX_BRIGHTNESS * (pixel - min) / (max - min); out[n * nx + m] = (pixel_t)pixel; }
}
// http:// www.songho.ca/dsp/cannyedge/cannyedge.html // determine size of kernel (odd #) // 0.0 <= sigma < 0.5 : 3 // 0.5 <= sigma < 1.0 : 5 // 1.0 <= sigma < 1.5 : 7 // 1.5 <= sigma < 2.0 : 9 // 2.0 <= sigma < 2.5 : 11 // 2.5 <= sigma < 3.0 : 13 ... // kernelSize = 2 * int(2*sigma) + 3;
void gaussian_filter(const pixel_t *in, pixel_t *out, int nx, int ny, float sigma) {
int i, j, c = 0; const int n = 2 * (int)(2 * sigma) + 3; float mean = (float)floor(n / 2.0); float kernel[n * n];
fprintf(stderr, "gaussian_filter: kernel size %d, sigma=%g\n", n, sigma); for (i = 0; i < n; i++) for (j = 0; j < n; j++) kernel[c++] = exp(-0.5 * (pow((i - mean) / sigma, 2.0) + pow((j - mean) / sigma, 2.0))) / (2 * M_PI * sigma * sigma); convolution(in, out, kernel, nx, ny, n, 1);
}
/*
* Links: * http:// en.wikipedia.org/wiki/Canny_edge_detector * http:// www.tomgibara.com/computer-vision/CannyEdgeDetector.java * http:// fourier.eng.hmc.edu/e161/lectures/canny/node1.html * http:// www.songho.ca/dsp/cannyedge/cannyedge.html * * Note: T1 and T2 are lower and upper thresholds. */
void canny_edge_detection(const pixel_t *in, pixel_t *out, int nx, int ny,
int tmin, int tmax, float sigma)
{
int i, j, c, Gmax;
float Gx[] = {-1, 0, 1, -2, 0, 2, -1, 0, 1};
float Gy[] = { 1, 2, 1, 0, 0, 0, -1,-2,-1};
pixel_t *G = calloc(nx * ny * sizeof(pixel_t), 1); if (!G) exit(1); pixel_t *after_Gx = calloc(nx * ny * sizeof(pixel_t), 1); if (!after_Gx) exit(1); pixel_t *after_Gy = calloc(nx * ny * sizeof(pixel_t), 1); if (!after_Gy) exit(1); pixel_t *nms = calloc(nx * ny * sizeof(pixel_t), 1); if (!nms) exit(1); pixel_t *edges; int nedges, k, t; int nbs[8]; // neighbours
gaussian_filter(in, out, nx, ny, sigma);
convolution(out, after_Gx, Gx, nx, ny, 3, 0); convolution(out, after_Gy, Gy, nx, ny, 3, 0);
Gmax = 0; for (i = 1; i < nx - 1; i++) for (j = 1; j < ny - 1; j++) { c = i + nx * j; // G[c] = abs(after_Gx[c]) + abs(after_Gy[c]); G[c] = (pixel_t)hypot(after_Gx[c], after_Gy[c]); if (G[c] > Gmax) Gmax = G[c]; }
// Non-maximum suppression, straightforward implementation. for (i = 1; i < nx - 1; i++) for (j = 1; j < ny - 1; j++) { float dir; int nn, ss, ww, ee, nw, ne, sw, se;
c = i + nx * j; nn = c - nx; ss = c + nx; ww = c + 1; ee = c - 1; nw = nn + 1; ne = nn - 1; sw = ss + 1; se = ss - 1;
dir = (float)(fmod(atan2(after_Gy[c], after_Gx[c]) + M_PI, M_PI) / M_PI) * 8;
if (((dir <= 1 || dir > 7) && G[c] > G[ee] && G[c] > G[ww]) || // 0 deg ((dir > 1 && dir <= 3) && G[c] > G[nw] && G[c] > G[se]) || // 45 deg ((dir > 3 && dir <= 5) && G[c] > G[nn] && G[c] > G[ss]) || // 90 deg ((dir > 5 && dir <= 7) && G[c] > G[ne] && G[c] > G[sw])) // 135 deg nms[c] = G[c]; else nms[c] = 0; }
// Reuse array edges = after_Gy; // used as a stack memset(out, 0, sizeof(pixel_t) * nx * ny); memset(edges, 0, sizeof(pixel_t) * nx * ny);
// Tracing edges with hysteresis . Non-recursive implementation. for (c = 1, j = 1; j < ny - 1; j++) for (i = 1; i < nx-1; i++) { if (nms[c] >= tmax && out[c] == 0) { // trace edges out[c] = MAX_BRIGHTNESS; nedges = 1; edges[0] = c;
do { nedges--; t = edges[nedges];
nbs[0] = t - nx; // nn nbs[1] = t + nx; // ss nbs[2] = t + 1; // ww nbs[3] = t - 1; // ee nbs[4] = nbs[0] + 1; // nw nbs[5] = nbs[0] - 1; // ne nbs[6] = nbs[1] + 1; // sw nbs[7] = nbs[1] - 1; // se
for (k = 0; k < 8; k++) if (nms[nbs[k]] >= tmin && out[ nbs[k] ] == 0) { out[nbs[k]] = MAX_BRIGHTNESS; edges[nedges++] = nbs[k]; } } while (nedges > 0); } c++; }
free(after_Gx); free(after_Gy); free(G); free(nms);
}
int main(int argc, const char ** const argv) {
pixel_t *bitmap_data, *temp_image;
if (argc < 2) { printf("Usage: %s image.bmp\n", argv[0]); exit(1); }
bitmap_data = load_bmp(argv[1], &ih); if (bitmap_data == NULL) exit(1); temp_image = (pixel_t*)malloc(ih.bmp_bytesz * sizeof(pixel_t)); if (temp_image == NULL) exit(1);
printf("Info: %d x %d x %d\n", ih.width, ih.height, ih.bitspp);
canny_edge_detection(bitmap_data, temp_image, ih.width, ih.height, 45, 50, 1.0f);
assert(save_bmp("out.bmp", &ih, temp_image) == 0); free(bitmap_data); free(temp_image);
return 0;
}</lang>