detect.c

NIST Handwriting OCR Testbed

/*
# proc: hough_lines_hori - computes the hough transform(s) for detecting lines
# proc:                    with angles in the range [-range .. +range].
# proc: hough_lines - computes the hough transform for detecting lines within the
# proc:               specified range of "normal" angles.
# proc: gen_slope_point - computes a line's slope and normal vector intersection
# proc:                   point given a location within a hough transform matrix.
*/

#include <stdio.h>
#include <math.h>
#include <values.h>
#include <defs.h>
#include <mytrace.h>


/***************************************************************************/
/* hough_lines_hori - conducts two separate hough line transforms, one for */
/* lines with angles in the range [-range .. 0], and the other for lines   */
/* with angles in the range [0 .. range].                                  */
/***************************************************************************/
hough_lines_hori(cdata, w, h, delta, range, pmin, pmax, pacc, pax, pay,
                 nmin, nmax, nacc, nax, nay)
unsigned char *cdata;
int w, h;
float delta, range;
float *pmin, *pmax, *nmin, *nmax;
int **pacc, **nacc;
int *pax, *pay, *nax, *nay;
{
   /* two separate hough transforms are required because the lines with angles */
   /* in the range [-range .. +range] are divided into two separate groups     */
   /* ( [(90 - range) .. 90] and [-90 .. (-90 + range)] ) when represented by  */
   /* their normal vectors, which are used by the hough transform to avoid     */
   /* discontinuities of lines with perfectly vertical slope.                  */

   /* the normal vectors for lines with angle [-range .. 0] */
   /* are on the range [(90 - range) .. 90] */
   *pmax = M_PI_2;
   *pmin = *pmax - range;

   /* conduct hough transform for lines [-range .. 0] */
   hough_lines(cdata, w, h, *pmin, *pmax, delta, pacc, pax, pay);

   /* the normal vectors for lines with angle [0 .. range] */
   /* are on the range [-90 .. (-90 + range)] */
   *nmin = -M_PI_2;
   *nmax = *nmin + range;

   /* conduct hough transform for lines [0 .. range] */
   hough_lines(cdata, w, h, *nmin, *nmax, delta, nacc, nax, nay);
}

/***************************************************************************/
/* hough_lines - conducts a hough line transformation on the given image   */
/* across a specified range of "normal" angles. The routine returns a      */
/* matrix whose locations of maximal value represent the dominant lines in */
/* the image. The locations in the matrix are (rho, theta) pairs that      */
/* represent unique lines in the image according to each line's normal     */
/* vector representation.                                                  */
/***************************************************************************/
hough_lines(data, w, h, tmin, tmax, td, acc, ax, ay)
unsigned char *data;
int w, h;
float tmin, tmax, td;
int **acc, *ax, *ay;
{
   int x, y, *aptr, hax;
   unsigned char *dptr;
   float theta;
   int rho;

   /* calculate allocation dimensions */

   /* the hough line transform is conducted using the normal vector   */
   /* representation of the line. this avoids discontinuities in      */
   /* perfectly vertical slopes. each possible line in the image is   */
   /* represented in the hough matrix by 1.) the angle of the normal  */
   /* vector extending from the origin to the point on the line       */
   /* where the intersection forms a right angle and 2.) the radial   */
   /* distance from the origin to the intersection point on the line. */
   /* the resulting transform matrix will be dimensioned with y       */
   /* coordinates representing the angle of the normal vector and x   */
   /* coordinates representing the radial distance to the "normal"    */
   /* point on the line.                                              */

   /* y dimension is based on the specified range of angles to be searched */
   /* over divided by the angle increment. */
   *ay = (int)ceil((tmax - tmin)/td);

   /* x dimension is based on the diagonal distance across the image */
   /* time 2 because the radial distance can be measured both positive */
   /* and negative. */
   hax = (int)ceil(sqrt((float)(w*w + h*h)));
   *ax = 2 * hax;

   /* allocate the 2d hough transform matrix */
   calloc_int(acc, (*ax)*(*ay), "hough_lines : acc");

   /* for every point in the image ... */
   dptr = data;
   for(y = 0; y < h; y++){
      for(x = 0; x < w; x++){
         /* if the current pixel is black ... */
         if(*dptr++){
            /* for all the possible angles of lines intersecting this pixel ... */
            for(theta = tmin, aptr = (*acc); theta <= tmax; theta += td, aptr+=*ax){

               /* compute the radial distance to the point on the line */
               /* where its "normal" vector intersects the line */
               rho = sround(x * cos(theta)) + (y * sin(theta));

               /* increment the location corresponding to the current  */
               /* (rho, theta) pair. each (rho, theta) pair represents */
               /* a unique line in the image. once every pixel in the  */
               /* image is processed, the locations in the matrix with */
               /* the highest count will represent the most dominant   */
               /* lines in the image.                                  */
               (*(aptr+(rho+hax)))++;
            }
         }
      }
   }
}

/***************************************************************************/
/* gen_slope_point - determines the line's slope and the normal vector's   */
/* intersection point represented by the specified location within a hough */
/* transform matrix. The routine requires a number of the hough transform  */
/* set-up parameters to make the calculations.                             */
/***************************************************************************/
gen_slope_point(slope, nx, ny, mx, my, tmin, tmax, td, xoffset)
float *slope, tmin, tmax, td;
int *nx, *ny, xoffset;
int mx, my;
{
   float mt, nt, theta_npi2pi();
   int mr;

   /* the x dimension is divided into positive and negative rho's */
   /* so an offset is needed to translate the x address into its  */
   /* real rho value. */
   mr = mx - xoffset;

   /* the y dimension represents a range of angles [tmin .. tmax] */
   /* sampled according to the increment td, so to compute the    */
   /* real angle represented by my, multiply it by the sample     */
   /* increment and then translate it by tmin. this give the      */
   /* angle of the "normal" vector to the line.                   */
   nt = (my * td) + tmin;

   /* convert the normal vector angle to the actual angle of the  */
   /* line by reflecting the normal angle forward 90 degrees and  */
   /* then make sure the resulting angle is in quadrants 1 or 4.  */
   mt = nt + M_PI_2;
   mt = theta_npi2pi(mt);

   /* calculate the line's slope from its angle */
   *slope = tan(mt);

   /* calculate the coordinates of the point where the line's */
   /* normal vector intersects the line. */
   *nx = sround(mr * cos(nt));
   *ny = sround(mr * sin(nt));

   my_trace4("line's: theta = %f, slope = %f, point = (%d, %d)\n",
             mt * (180.0/M_PI), *slope, *nx, *ny);
}