findblob.c

NIST Handwriting OCR Testbed

	  *p = *q = 1;
    else
      fatalerr("findblobnruns", "illegal value for erase_flag", NULL);
    *box_w = inner_bw;
    *box_h = inner_bh;
    return 1;
  }
  else
    fatalerr("findblobnruns", "illegal value for out_flag", NULL);
}

/********************************************************************/

/* Grows seed pixel into seed run. */

findblob_seed_to_run(y, q)
unsigned short y;
unsigned char *q;
{
  unsigned char *r, *w_on, *e_off;

  nlim = slim = y;
  e_off = (w_on = rasity + y * ww) + ww;
  for(*q = 0, r = q + 1; r < e_off && *r; r++)
    *r = 0;
  for(q--; q >= w_on && *q; q--)
    *q = 0;
  q++;
  list->y = y;
  wlim = (list->w_on = q) - w_on;
  list->e_off = r;
  elim = --r - w_on;
}

/********************************************************************/

/* Grows a run northward, i.e. finds any runs that touch its north
side. four way connectivity */

findblob_grow_n()
{
  unsigned char *q, *qs, *qe, *r, *w_on, *e_off;
  unsigned short y, yow;

  if(!(y = list_h->y))
    return;
  for(q = qs = list_h->w_on - ww, qe = list_h->e_off - ww;
    q < qe && !*q; q++);
  if(q >= qe)
    return;
  if(--y < nlim)
    nlim = y;
  e_off = (w_on = rasity + y * ww) + ww;
  for(*q = 0, r = q + 1; r < e_off && *r; r++)
    *r = 0;
  if(q == qs) {
    for(q--; q >= w_on && *q; q--)
      *q = 0;
    q++;
  }
  if(list_t == list_off)
    findblob_realloc_list();
  list_t->y = y;
  if((yow = (list_t->w_on = q) - w_on) < wlim)
    wlim = yow;
  (list_t++)->e_off = r;
  while(1) {
    for(q = r + 1; q < qe && !*q; q++);
    if(q >= qe)
      break;
    for(*q = 0, r = q + 1; r < e_off && *r; r++)
      *r = 0;
    if(list_t == list_off)
      findblob_realloc_list();
    list_t->y = y;
    list_t->w_on = q;
    (list_t++)->e_off = r;
  }
  if((yow = --r - w_on) > elim)
    elim = yow;
}

/* same growing but with eight way connectivity */
findblob_8grow_n()
{
  unsigned char *q, *qs, *qe, *r, *w_on, *e_off;
  unsigned short y, yow;

  if(!(y = list_h->y))
    return;
  e_off = (w_on = rasity + --y * ww) + ww;
  /* Extend limits by one on each end compared to 4-connected version,
  but careful not to fall off */
  if((qs = list_h->w_on - ww - 1) < w_on)
    qs++;
  if((qe = list_h->e_off - ww + 1) > e_off)
    qe--;
  for(q = qs; q < qe && !*q; q++);
  if(q >= qe)
    return;
  if(y < nlim)
    nlim = y;
  for(*q = 0, r = q + 1; r < e_off && *r; r++)
    *r = 0;
  if(q == qs) {
    for(q--; q >= w_on && *q; q--)
      *q = 0;
    q++;
  }
  if(list_t == list_off)
    findblob_realloc_list();
  list_t->y = y;
  if((yow = (list_t->w_on = q) - w_on) < wlim)
    wlim = yow;
  (list_t++)->e_off = r;
  while(1) {
    for(q = r + 1; q < qe && !*q; q++);
    if(q >= qe)
      break;
    for(*q = 0, r = q + 1; r < e_off && *r; r++)
      *r = 0;
    if(list_t == list_off)
      findblob_realloc_list();
    list_t->y = y;
    list_t->w_on = q;
    (list_t++)->e_off = r;
  }
  if((yow = --r - w_on) > elim)
    elim = yow;
}

/********************************************************************/

/* Grows a run southward, i.e. finds any runs that touch its south
side. uses four way connectivity */

findblob_grow_s()
{
  unsigned char *q, *qs, *qe, *r, *w_on, *e_off;
  unsigned short y, yow;

  if((y = list_h->y + 1) == hh)
    return;
  for(q = qs = list_h->w_on + ww, qe = list_h->e_off + ww;
    q < qe && !*q; q++);
  if(q >= qe)
    return;
  if(y > slim)
    slim = y;
  e_off = (w_on = rasity + y * ww) + ww;
  for(*q = 0, r = q + 1; r < e_off && *r; r++)
    *r = 0;
  if(q == qs) {
    for(q--; q >= w_on && *q; q--)
      *q = 0;
    q++;
  }
  if(list_t == list_off)
    findblob_realloc_list();
  list_t->y = y;
  if((yow = (list_t->w_on = q) - w_on) < wlim)
    wlim = yow;
  (list_t++)->e_off = r;
  while(1) {
    for(q = r + 1; q < qe && !*q; q++);
    if(q >= qe)
      break;
    for(*q = 0, r = q + 1; r < e_off && *r; r++)
      *r = 0;
    if(list_t == list_off)
      findblob_realloc_list();
    list_t->y = y;
    list_t->w_on = q;
    (list_t++)->e_off = r;
  }
  if((yow = --r - w_on) > elim)
    elim = yow;
}

/* same growing except with eight way connectivity */
findblob_8grow_s()
{                 
  unsigned char *q, *qs, *qe, *r, *w_on, *e_off;
  unsigned short y, yow;                         
                         
  if((y = list_h->y + 1) == hh)
    return;                     
  e_off = (w_on = rasity + y * ww) + ww;
  if((qs = list_h->w_on + ww - 1) < w_on)
    qs++;                                 
  if((qe = list_h->e_off + ww + 1) > e_off)
    qe--;                                   
  for(q = qs; q < qe && !*q; q++);
  if(q >= qe)                      
    return;   
  if(y > slim)
    slim = y;  
  for(*q = 0, r = q + 1; r < e_off && *r; r++)
    *r = 0;                                    
  if(q == qs) {
    for(q--; q >= w_on && *q; q--)
      *q = 0;                      
    q++;      
  }      
  if(list_t == list_off)
    findblob_realloc_list();
  list_t->y = y;             
  if((yow = (list_t->w_on = q) - w_on) < wlim)
    wlim = yow;                                
  (list_t++)->e_off = r;
  while(1) {             
    for(q = r + 1; q < qe && !*q; q++);
    if(q >= qe)                         
      break;    
    for(*q = 0, r = q + 1; r < e_off && *r; r++)
      *r = 0;                                    
    if(list_t == list_off)
      findblob_realloc_list();
    list_t->y = y;             
    list_t->w_on = q;
    (list_t++)->e_off = r;
  }                        
  if((yow = --r - w_on) > elim)
    elim = yow;                 
}

/********************************************************************/

/* Reallocates the list to a larger size. */

findblob_realloc_list()
{
  unsigned int newsize;
  RUN *oldlist;

  if((newsize = list_off - (oldlist = list) + LIST_INCR) >
    LIST_MAXSIZE)
    fatalerr("findblob_realloc_list", "list would exceed \
LIST_MAXSIZE elts", NULL);
  if(!(list = (RUN *)realloc(oldlist, newsize * sizeof(RUN))))
    syserr("findblob_realloc_list", "realloc", "list");
  list_off = list + newsize;
  list_h = list + (list_h - oldlist);
  list_t = list + (list_t - oldlist);
}

/********************************************************************/


/************************************************************/
/*         Routine:   findblob_stats()                      */
/*         Author:    G. T. Candela -> "findblob()"         */
/*                                                          */
/*         Modifications:                                   */
/*           5/2/94 - faster version: uses runs             */
/*           Edited:    C. I. Watson  -> "findblob_stats()" */
/*           Date:      9/1/94                              */
/************************************************************/

/* Each time findblob_stats is called, it either returns blob stats of the
true pixels of a binary raster, or indicates that it encountered no
blobs in its col-major scan from the desired starting position to the
bottom-right corner of the raster.  Parameters are:

  ras: Input binary raster, represented using one byte per pixel.
  w: Width of ras.
  h: Height of ras.
  start_x, start_y: Addresses of the x- and y-coordinates of
    the pixel at which caller wants findblob to start -- or resume --
    its column-major scan for blobs.  (To find all blobs,
    caller can use a loop that initializes *start_x and
    *start_y to zeros and does not change them thereafter, and then
    should stop looping when findblob returns 0, which indicates
    that the previous call had returned the last blob; if raster has
    no blobs, first call of findblob will return 0.  But caller also
    has the options of starting *start_x and *start_y at
    something other than (0,0), and changing them between calls of
    findblob.)
  box_x, box_y: Addresses of the coordinates of the top-left corner
    of the bounding box of the blob that was found; the coordinates
    are with respect to the input raster.
  box_w, box_h: Upon return, these always contain the width and
    height of the bounding box of the blob that was found; these
    may or may not be the width and height of the output raster.

The possible function values returned by findblob_stats are:
     0: It reached the bottom-right pixel without finding a blob.
     1: It found a blob, and is returning it in desired format.

*********************************************************************/

int findblob_stats_rw(ras, w, h, start_x, start_y, box_x, box_y, box_w, box_h)
unsigned char *ras;
int w, h, *start_x, *start_y;
int *box_x, *box_y, *box_w, *box_h;
{
  unsigned char *p, *ps;
  unsigned short x, y;

  if(list == (RUN *)NULL) {
    if(!(list = (RUN *)malloc(LIST_STARTSIZE * sizeof(RUN))))
      syserr("findblob_malloc_list", "malloc", "list");
    list_off = list + LIST_STARTSIZE;
  }
  rasity = ras;
  ww = w;
  hh_m1 = (hh = h) - 1;
  if(*start_x < 0 || *start_x >= (int)ww ||
     *start_y < 0 || *start_y >= (int)hh)
    fatalerr("findblob_stats_rw", "scan start position is off raster",
      "start_x, start_y");
  x = *start_x;
  y = *start_y;
  /* Col-majorly scan for a seed pixel. */
  for(p = ras + y * ww + x, ps = ras + y * ww + w-1; !*p;) {
    if(p < ps)
      p++;
    else {
      if(++y == hh)
	return 0;
      p = ras + y*ww;
      ps += ww;
    }
  }
  /* Grow seed pixel to a seed run. */
  findblob_seed_to_run(y, p);
  /* Use a queue to grow seed run into a complete blob.  Queue starts
  as just the seed run; read run from queue head, produce connecting
  runs (if any) and put them on queue tail, read another run from
  head, etc., until queue becomes empty.  List space is not recycled:
  when growth of blob is finished, list contains all runs that were
  ever in the queue. */
  for(list_t = (list_h = list) + 1; list_h < list_t; list_h++) {
    findblob_grow_n();
    findblob_grow_s();
  }
  /* Growth of blob is finished.  Go through list to find what pixels
  to set in output raster. */
  *start_x = x;
  *start_y = y;
  *box_x = wlim;
  *box_y = nlim;
  *box_w = elim - wlim + 1;
  *box_h = slim - nlim + 1;

  return 1;
}

/********************************************************************/
int findblob_stats_cl(ras, w, h, start_x, start_y, box_x, box_y, box_w, box_h)
unsigned char *ras;
int w, h, *start_x, *start_y;
int *box_x, *box_y, *box_w, *box_h;
{
  unsigned char *p, *ps;
  unsigned short x, y;

  if(list == (RUN *)NULL) {
    if(!(list = (RUN *)malloc(LIST_STARTSIZE * sizeof(RUN))))
      syserr("findblob_malloc_list", "malloc", "list");
    list_off = list + LIST_STARTSIZE;
  }
  rasity = ras;
  ww = w;
  hh_m1 = (hh = h) - 1;
  if(*start_x < 0 || *start_x >= (int)ww ||
     *start_y < 0 || *start_y >= (int)hh)
    fatalerr("findblob_stats_cl", "scan start position is off raster",
      "start_x, start_y");
  x = *start_x;
  y = *start_y;
  /* Col-majorly scan for a seed pixel. */
  for(p = ras + y * ww + x, ps = ras + hh_m1 * ww + x; !*p;) {
    if(p < ps)
      p += ww;
    else {
      if(++x == ww)
	return 0;
      p = ras + x;
      ps++;
    }
  }
  y = (p - ras) / (int)ww;
  /* Grow seed pixel to a seed run. */
  findblob_seed_to_run(y, p);
  /* Use a queue to grow seed run into a complete blob.  Queue starts
  as just the seed run; read run from queue head, produce connecting
  runs (if any) and put them on queue tail, read another run from
  head, etc., until queue becomes empty.  List space is not recycled:
  when growth of blob is finished, list contains all runs that were
  ever in the queue. */
  for(list_t = (list_h = list) + 1; list_h < list_t; list_h++) {
    findblob_grow_n();
    findblob_grow_s();
  }
  /* Growth of blob is finished.  Go through list to find what pixels
  to set in output raster. */
  *start_x = x;
  *start_y = y;
  *box_x = wlim;
  *box_y = nlim;
  *box_w = elim - wlim + 1;
  *box_h = slim - nlim + 1;

  return 1;
}

/********************************************************************/
/* should call this function when you are done with a session of    */
/* findblobs.                                                       */
/********************************************************************/
end_findblobs()
{
   if(list != (RUN *)NULL){
      free(list);
      list = (RUN *)NULL;
   }
}