/* * hough.c * * Practical Algorithms for Image Analysis * * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC */ /* HOUGH: program performs Hough transform on binary image * and yields an image of the transform space as well * as the line corresponding to the highest peak */ #include #include #include #include /* tiff info on images */ #include #include extern void print_sos_lic (); #define ON 0 #define DFLT_BORDER 2 /* default border of image */ #if defined(WIN32) #define PI 3.1415926536 #endif #define PID2 1.5707963268 #define TAN_TOO_BIG 263.0 /* tan so big that angle is PI/2 */ #define INBOUNDX(X) ((X) >= 0 && (X) < width) #define INBOUNDY(Y) ((Y) >= 0 && (Y) < height) int usage (short); int input (int, char **, long *, short *); main (argc, argv) int argc; char *argv[]; { Image *imgI, *imgH; /* I/O image structures */ unsigned char **imgIn, **hough; /* input/output images */ long width, height; /* input image size */ long border; /* zero out border of image */ short dFlag; /* if = 0, display peak in Hough space */ long xEnd, yEnd; /* end of image within borders */ long thetaHt, rhoWid; /* width and height of Hough space */ long rhoWidM1; /* rho width minus 1 */ double rho, theta; /* radius and angle in Hough space */ double tanTheta; /* tan of theta angle */ double denom; /* denominator */ double rhoNorm; /* normalization factor for rho */ long max, xMax, yMax; /* peak point in Hough space */ double x1, y1; long i, j; long x, y; if ((input (argc, argv, &border, &dFlag)) < 0) return (-1); /* open input and output images */ imgI = ImageIn (argv[1]); imgIn = imgI->img; height = ImageGetHeight (imgI); width = ImageGetWidth (imgI); printf ("image size is %dx%d.\n", width, height); rhoWid = width; thetaHt = height; rhoWidM1 = rhoWid - 1; imgH = ImageAlloc (thetaHt, rhoWid, 8); hough = ImageGetPtr (imgH); /* initialize accumulator bins */ for (i = 0; i < thetaHt; i++) for (j = 0; j < rhoWid; j++) hough[i][j] = 0; /* perform Hough transform */ rhoNorm = rhoWidM1 / sqrt ((double) (width * width) + (double) height * height); yEnd = height - border; xEnd = width - border; for (y = border + 1; y < yEnd; y++) { for (x = border + 1; x < xEnd; x++) { if (imgIn[y][x] == ON) { for (i = 0; i < thetaHt; i++) { theta = (double) i *PI / (double) thetaHt; tanTheta = tan (theta); if (tanTheta > TAN_TOO_BIG) { /*printf ("too big: x = %d, i = %d, j = %d\n", x, i, j);*/ rho = (double) x; } else { denom = tanTheta * tanTheta + 1.0; y1 = ((double) y - (double) x * tanTheta) / denom; x1 = ((double) x * tanTheta * tanTheta - (double) y * tanTheta) / denom; rho = sqrt (x1 * x1 + y1 * y1); } j = (long) (rho * rhoNorm + 0.5); if (hough[i][j] < 255) hough[i][j]++; } } } } /* determine peak in Hough space and (theta, rho) coords */ max = 0; for (i = 0; i < thetaHt; i++) { for (j = 0; j < rhoWid; j++) { if (hough[i][j] > max) { max = hough[i][j]; xMax = j; yMax = i; } } } if (max > 0) { rho = xMax / rhoNorm; theta = yMax * PI / (double) thetaHt; printf ("Line located with parameters:\n"); printf ("\tpolar coords: (%5.2f, %5.2f) (rho [pixels], theta [radians])\n", rho, theta); if (dFlag) { /* display peak if flag set */ printf ("Peak located at: (%d,%d)\n", xMax, yMax); for (i = yMax - 3; i <= yMax + 3; i++) { if (INBOUNDY (i)) { if (INBOUNDX (xMax - 3)) hough[i][xMax - 3] = (hough[i][xMax - 3] > 128) ? 0 : 255; if (INBOUNDX (xMax + 4)) hough[i][xMax + 3] = (hough[i][xMax + 3] > 128) ? 0 : 255; } } for (j = xMax - 3; j <= xMax + 3; j++) { if (INBOUNDX (j)) { if (INBOUNDY (yMax - 3)) hough[yMax - 3][j] = (hough[yMax - 3][j] > 128) ? 0 : 255; if (INBOUNDY (yMax + 4)) hough[yMax + 3][j] = (hough[yMax + 3][j] > 128) ? 0 : 255; } } } } else printf ("No line found.\n"); /* invert Hough image for display */ for (i = 0; i < thetaHt; i++) for (j = 0; j < rhoWid; j++) hough[i][j] = 255 - hough[i][j]; ImageOut (argv[2], imgH); return (0); } /* USAGE: function gives instructions on usage of program * usage: usage (flag) * When flag is 1, the long message is given, 0 gives short. */ int usage (flag) short flag; /* flag =1 for long message; =0 for short message */ { /* print short usage message or long */ printf ("USAGE: hough inimg outimg [-b BORDER] [-d] [-L]\n"); if (flag == 0) return (-1); printf ("\nhough transforms binary image from\n"); printf ("spatial domain ((x,y) coordinates) to polar coordinate\n"); printf ("domain ((rho, theta) coordinates); peak in the polar\n"); printf ("(\"Hough\")domain indicates a dominant line in the spatial domain;\n"); printf ("NOTE: origin (0,0) of Hough transform\n"); printf (" image is in top-left corner;\n"); printf (" rho increases along horizontal axis to\n"); printf (" maximum rho equal to image diagonal length;\n"); printf (" theta increases downward from 0 radians to PI radians.\n\n"); printf ("ARGUMENTS:\n"); printf (" inimg: input image filename (TIF)\n"); printf (" outimg: output image filename (TIF)\n\n"); printf ("OPTIONS:\n"); printf (" -b BORDER: to remove noise at borders of image by omitting\n"); printf (" image for this number of rows/cols [default = %d].\n", DFLT_BORDER); printf (" -d: display peak in Hough transform space.\n"); printf (" -L: print Software License for this module\n"); return (-1); } /* INPUT: function reads input parameters * usage: input (argc, argv, &dFlag) */ #define USAGE_EXIT(VALUE) {usage (VALUE); return (-1);} int input (argc, argv, border, dFlag) int argc; char *argv[]; long *border; /* zero out border of image */ short *dFlag; /* if = 1, display peak */ { long n; if (argc == 1) USAGE_EXIT (1); if (argc == 2) USAGE_EXIT (0); *dFlag = 0; *border = DFLT_BORDER; for (n = 3; n < argc; n++) { if (strcmp (argv[n], "-b") == 0) { if (++n == argc || argv[n][0] == '-') USAGE_EXIT (0); *border = atol (argv[n]); } else if (strcmp (argv[n], "-d") == 0) *dFlag = 1; else if (strcmp (argv[n], "-L") == 0) { print_sos_lic (); exit (0); } else USAGE_EXIT (0); } return (0); }