overrun.c

NIST Handwriting OCR Testbed

/*
# proc: max_overlap_run_along_x - analyzes a system of horizontal runs and
# proc:                assigns a vector of y values accoriding to the maximum
# proc:                length run at each x posistion.
# proc: init_markers - initializes markers to a specifiec x position to keep
# proc:                track of processing within the system of horizontal runs.
*/

#include <defs.h>

#define DONE -1
/***************************************************************************/
max_overlap_run_along_x(ptsx, ptsy, npts, sx, ex, rx, ry, rlen, nruns, w, h)
int **ptsx, **ptsy, *npts;
int sx, ex;
int *rx, *ry, *rlen, nruns;
int w, h;
{
   int ri, xlen, px, py;
   int maxri, maxrlen;
   int *rx2;
   int *rankyx;
   int *sort_index_on_int_2ii();
   int *markers, test_length;
   int mark;

   /* sort runs on y, then x */
   rankyx = sort_index_on_int_2ii(ry, rx, nruns);

   xlen = ex-sx+1;
   malloc_int(ptsx, xlen, "max_overlap_run_along_x: ptsx");
   malloc_int(ptsy, xlen, "max_overlap_run_along_x: ptsy");
   *npts = 0;

   /* compute run endpoints x-coordinate up front */
   malloc_int(&rx2, nruns, "max_overlap_run_along_x: rx2");
   for(ri = 0; ri < nruns; ri++)
      rx2[ri] = rx[rankyx[ri]] + rlen[rankyx[ri]];

   /* set up markers to point to most relevant runs on each scanline */
   malloc_int(&markers, h, "max_overlap_run_along_x: markers");
   init_markers(sx, markers, h, rx, rx2, ry, rankyx, nruns);

   for(px = sx; px <= ex; px++){
      /* reset max overlapping run for current x */
      maxri = NOT_FOUND;
      maxrlen = -1;
      /* for each scanline ... */
      for(py = 0; py < h; py++){
         mark = markers[py];
         /* if marker set to DONE OR x left of marked run, then continue */
         if((mark != DONE) && (px >= rx[rankyx[mark]])){
            test_length = FALSE;
            /* if x right of marked run, then advance marker */
            if(px >= rx2[rankyx[mark]]){
               (markers[py])++;
               mark = markers[py];
               /* if no more runs on current scanline ... */
               if((mark >= nruns) || (ry[rankyx[mark]] != py))
                  markers[py] = DONE;
               else{
               /* otherwise if marked run overlaps with current x ... */
                  if(rx[rankyx[mark]] == px)
                     /* turn test flag ON */
                     test_length = TRUE;
               }
            }
            /* otherwise marked run intersects with current x */
            else
               /* turn test flag ON */
               test_length = TRUE;
            if(test_length){
               /* test for max length run */
               if(rlen[rankyx[mark]] > maxrlen){
                  /* store current run */
                  maxri = mark;
                  maxrlen = rlen[rankyx[mark]];
               }
            }
         }
      }
      if(maxri != NOT_FOUND){
         (*ptsx)[*npts] = px;
         (*ptsy)[(*npts)++] = ry[rankyx[maxri]];
      }
   }
   free(rankyx);
   free(rx2);
   free(markers);
}

/***************************************************************************/
init_markers(sx, markers, nmarks, rx, rx2, ry, rankyx, nruns)
int sx, *markers, nmarks;
int *rx, *rx2, *ry, *rankyx, nruns;
{
   int i, cy, ri;

   /* by default all scanlines are marked DONE */
   for(i = 0; i < nmarks; i++)
      markers[i] = DONE;

   ri = 0;
   while(ri < nruns){
      /* get current y of runs */
      cy = ry[rankyx[ri]];
      /* mark first run to overlap with sx or first run to the right */
      while((ri < nruns) && (ry[rankyx[ri]] == cy) && (sx > rx2[rankyx[ri]]))
         ri++;
      /* if no more runs, then quit */
      if(ri >= nruns)
         break;
      /* if current run is on same scanline ... */
      if(ry[rankyx[ri]] == cy)
         markers[cy] = ri;
      /* skip to next scanline */
      while((ri < nruns) && (ry[rankyx[ri]] == cy))
         ri++;
   }
}