/*# proc: findblob - finds a 4-connected blob of true pixels from within a# proc:            binary character image, returning the blob as a character# proc:            image.# proc: findblob8 - finds an 8-connected blob of true pixels from within a# proc:            binary character image, returning the blob as a character# proc:            image.# proc: findblobnruns - finds a 4-connected blob of true pixels from within a# proc:            binary character image, returning the blob as a character# proc:            image and the horizontal runs comprising the blob.# proc: findblobnruns8 - finds an 8-connected blob of true pixels from within a# proc:            binary character image, returning the blob as a character# proc:            image and the horizontal runs comprising the blob.# proc: findbinblob - finds a connected blob of true pixels from within a# proc:               binary character image, returning the blob as a binary# proc:               bitmap.# proc: findblob_stats_rw - finds a blob of true pixels in a binary char image# proc:                     (search row maj) and returns the blob "stats"# proc: findblob_stats_cl - finds a blob of true pixels in a binary char image# proc:                     (search col maj) and returns the blob "stats"# proc: end_findblobs - deallocates memory upon completion of a findblob session.# proc:*/#include <stdio.h>#include <findblob.h>/************************************************************/findbinblob(ras, w, h, erase_flag, out_flag, start_x, start_y,            binras, bin_w, bin_h, box_x, box_y, box_w, box_h)unsigned char *ras, **binras;int w, h, erase_flag, out_flag;int *start_x, *start_y, *bin_w, *bin_h, *box_x, *box_y, *box_w, *box_h;{   int ret, tw, th;   unsigned char *charras;   /* if W_H_BLOB, must save box w & h inputs before they are overwritten */   tw = *box_w;   th = *box_h;   ret = findblob(ras, w, h, erase_flag, ALLOC, out_flag,                  start_x, start_y, &charras, box_x, box_y, box_w, box_h);   switch (ret){      case 1:         switch (out_flag){	    case ORIG_BLOB:               char2bin_exact(binras, bin_w, bin_h, charras, w, h);               break;	    case W_H_BLOB:               char2bin_exact(binras, bin_w, bin_h, charras, tw, th);               break;	    case BOUND_BLOB:               char2bin_exact(binras, bin_w, bin_h, charras, *box_w, *box_h);               break;	    default:               fatalerr("findbinblob", "unknown out_flag value", NULL);         }         free(charras);         break;      case 2:         char2bin_exact(binras, bin_w, bin_h, charras, *box_w, *box_h);         free(charras);         break;      default:         break;   }   return(ret);}/************************************************************//*         Routine:   findblob()                            *//*         Author:    G. T. Candela                         *//*         Date:      3/1/94                                *//*                                                          *//*         Modifications:                                   *//*           5/2/94 - faster version: uses runs             *//************************************************************//* Each time findblob is called, it either returns one blob of thetrue pixels of a binary raster, or indicates that it encountered noblobs in its col-major scan from the desired starting position to thebottom-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.  erase_flag: Can be ERASE or NO_ERASE:    ERASE     findblob erases blobs from input as it finds them.    NO_ERASE  Doesn't erase blobs.  CAUTION: If findblob is called     multiple times for a raster with NO_ERASE and caller does not     erase blobs from input raster after they are returned, findblob     will repeatedly find the same blob, unless caller changes     (start_x, start_y) between calls.  alloc_flag: Can be ALLOC or NO_ALLOC:    ALLOC     findblob will allocate output blob-rasters.    NO_ALLOC  findblob won't allocate rasters: caller must.  out_flag: Can be ORIG_BLOB, W_H_BLOB, or BOUND_BLOB:    ORIG_BLOB   Each blob is returned in an otherwise empty raster the      same shape as the input raster, and its location in this output      raster is the same as its location in the input raster.    W_H_BLOB    Each blob is returned centered in a raster of width      and height specified by box_w and box_h; but if ALLOC is      is used and width or height of blob is larger than      desired width or height, findblob allocates a raster just big      enough to hold the blob, and its returned function value warns      of this situation (return value 2).  If NO_ALLOC is used and      blob doesn't fit, that is a fatal error.    BOUND_BLOB  Each blob is returned in a raster just big enough to      contain it.  This option cannot be used with NO_ALLOC.  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.)  blobras: Address of the raster in which findblob returns the blob    it found, representing it in one byte per pixel.  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.    And if out_flag is W_H_BLOB, then box_w and    box_h are used as INPUTS as well as outputs.  To summarize:      If out_flag is ORIG_BLOB, then box_w and box_h are outputs        only, indicating the dimensions of the bounding box of the        blob, and the output raster containing the blob has the same        dimensions as the input raster.      If out_flag is W_H_BLOB, then box_w and box_h are both INPUTS        specifying the desired width and height of the output raster        in which the bounding box of the blob is to be centered (if        it fits), and OUTPUTS indicating the dimensions of the        bounding box.  (Therefore, a program that uses findblob to        find multiple blobs with W_H_BLOB and always the same specified        output raster dimensions, must reset these parms before each        call, since findblob will change them.)  If the bounding box        of the blob doesn't fit into the desired shape of output        raster, then if alloc_flag is NO_ALLOC this is a fatal error,        but if alloc_flag is ALLOC then findblob allocates an output        raster of the same shape as the blob's bounding box and        returns the blob in this raster.      If out_flag is BOUND_BLOB, then box_w and box_h are outputs        only, indicating the dimensions of the bounding box of the        blob, which are also the dimensions of the output raster:        findblob allocates the output raster just big enough        to contain the blob.  (BOUND_BLOB cannot be used with        NO_ALLOC.)The possible function values returned by findblob are:     0: It reached the bottom-right pixel without finding a blob.     1: It found a blob, and is returning it in desired format.     2: It found a blob, but ALLOC and W_H_BLOB are in effect and          blob doesn't fit into a raster of specified shape; so, it          has allocated a raster just big enough for the blob and is          returning the blob in this raster (as if BOUND_BLOB had          been used).*********************************************************************/static RUN *list = (RUN *)NULL, *list_off, *list_h, *list_t;static unsigned char *rasity;static unsigned short ww, hh, hh_m1, nlim, slim, elim, wlim;int findblob(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,             start_y, blobras, box_x, box_y, box_w, box_h)unsigned char *ras, **blobras;int w, h, erase_flag, alloc_flag, out_flag,    *start_x, *start_y, *box_x, *box_y, *box_w, *box_h;{RUN *oruns, *oruns_t, *oruns_off;return findblob_connect(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,                             start_y, blobras, box_x, box_y, box_w, box_h,                             &oruns, &oruns_t, &oruns_off, CONNECT4);}int findblob8(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,              start_y, blobras, box_x, box_y, box_w, box_h)unsigned char *ras, **blobras;int w, h, erase_flag, alloc_flag, out_flag,    *start_x, *start_y, *box_x, *box_y, *box_w, *box_h;{RUN *oruns, *oruns_t, *oruns_off;return findblob_connect(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,                             start_y, blobras, box_x, box_y, box_w, box_h,                             &oruns, &oruns_t, &oruns_off, CONNECT8);}/*********************************************************************/int findblobnruns(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,             start_y, blobras, box_x, box_y, box_w, box_h, oruns, oruns_t, oruns_off)unsigned char *ras, **blobras;int w, h, erase_flag, alloc_flag, out_flag,    *start_x, *start_y, *box_x, *box_y, *box_w, *box_h;RUN **oruns, **oruns_t, **oruns_off;{return findblob_connect(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,                             start_y, blobras, box_x, box_y, box_w, box_h,                             oruns, oruns_t, oruns_off, CONNECT4);}/*********************************************************************/int findblobnruns8(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,              start_y, blobras, box_x, box_y, box_w, box_h, oruns, oruns_t, oruns_off)unsigned char *ras, **blobras;int w, h, erase_flag, alloc_flag, out_flag,    *start_x, *start_y, *box_x, *box_y, *box_w, *box_h;RUN **oruns, **oruns_t, **oruns_off;{return findblob_connect(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,                        start_y, blobras, box_x, box_y, box_w, box_h,                        oruns, oruns_t, oruns_off, CONNECT8);}/*********************************************************************/int findblob_connect(ras, w, h, erase_flag, alloc_flag, out_flag, start_x,  start_y, blobras, box_x, box_y, box_w, box_h, oruns, oruns_t, oruns_off, connectivity)unsigned char *ras, **blobras;int w, h, erase_flag, alloc_flag, out_flag, connectivity,    *start_x, *start_y, *box_x, *box_y, *box_w, *box_h;RUN **oruns, **oruns_t, **oruns_off;{  RUN *runp;  unsigned char *p, *ps, *q, *blobrasity;  unsigned short x, y;  int offset, inner_bw, inner_bh, outer_bw, outer_bh, inner_wlim,    inner_nlim;  if(list == (RUN *)NULL) {    if(!(list = (RUN *)malloc(LIST_STARTSIZE * sizeof(RUN))))      syserr("findblobnruns_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("findblobnruns", "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. */  if (connectivity == CONNECT4)     for(list_t = (list_h = list) + 1; list_h < list_t; list_h++)     {       findblob_grow_n();       findblob_grow_s();     }  else  if (connectivity == CONNECT8)     for(list_t = (list_h = list) + 1; list_h < list_t; list_h++)     {       findblob_8grow_n();       findblob_8grow_s();     }  else     fatalerr("findblobnruns", "connectivity flag", "must be CONNECT4 or CONNECT8");  /* 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;  *oruns = list;  *oruns_t = list_t;  *oruns_off = list_off;  inner_bw = elim - wlim + 1;  inner_bh = slim - nlim + 1;  if(out_flag == ORIG_BLOB) {    if(alloc_flag == ALLOC) {      if(!(*blobras = (unsigned char *)calloc(ww * hh, 1)))	syserr("findblobnruns", "calloc", "blobras");    }    else if(alloc_flag == NO_ALLOC)      memset(*blobras, NULL, ww * hh);    else      fatalerr("findblobnruns", "illegal value for alloc_flag", NULL);    offset = *blobras - ras;    if(erase_flag == ERASE)      for(runp = list; runp < list_t; runp++)	for(ps = (p = runp->w_on + offset) + (runp->e_off -          runp->w_on); p < ps; p++)	  *p = 1;    else if(erase_flag == NO_ERASE)      for(runp = list; runp < list_t; runp++)	for(ps = (p = (q = runp->w_on) + offset) + (runp->e_off -          runp->w_on); p < ps; p++, q++)	  *p = *q = 1;    else      fatalerr("findblobnruns", "illegal value for erase_flag", NULL);    *box_w = inner_bw;    *box_h = inner_bh;    return 1;  }  else if(out_flag == W_H_BLOB) {    outer_bw = *box_w;    outer_bh = *box_h;    if(inner_bw <= outer_bw && inner_bh <= outer_bh) {      /* Blob's bounding box fits into a raster of the shape caller      has specified in box_w and box_h; center the bounding box in      such a raster. */      if(alloc_flag == ALLOC) {	if(!(*blobras = (unsigned char *)calloc(outer_bw * outer_bh,          1)))	  syserr("findblobnruns", "calloc", "blobras");      }      else if(alloc_flag == NO_ALLOC)	memset(*blobras, NULL, outer_bw * outer_bh);      else	fatalerr("findblobnruns", "illegal value for alloc_flag", NULL);      inner_wlim = (outer_bw - inner_bw) / 2;      inner_nlim = (outer_bh - inner_bh) / 2;      blobrasity = *blobras;      if(erase_flag == ERASE)	for(runp = list; runp < list_t; runp++)	  for(ps = (p = blobrasity + (runp->y - nlim + inner_nlim) *            outer_bw + (runp->w_on - ras) % (int)ww - wlim + inner_wlim) +            (runp->e_off - runp->w_on); p < ps; p++)	    *p = 1;      else if(erase_flag == NO_ERASE)	for(runp = list; runp < list_t; runp++)	  for(ps = (p = blobrasity + (runp->y - nlim + inner_nlim) *            outer_bw + ((q = runp->w_on) - ras) % (int)ww - wlim +            inner_wlim) + (runp->e_off - runp->w_on); p < ps; p++, q++)	    *p = *q = 1;      else	fatalerr("findblobnruns", "illegal value for erase_flag", NULL);      *box_w = inner_bw;      *box_h = inner_bh;      return 1;    }    else {      /* Blob's bounding box doesn't fit into a raster of the shape      caller has specified in box_w and box_h. */      if(alloc_flag == ALLOC) {	/* Allocate a raster of same shape as bounding box (as        for BOUND_BLOB), and return function value 2, warning        that a larger-than-specified raster was allocated. */	if(!(*blobras = (unsigned char *)calloc(inner_bw * inner_bh,          1)))	  syserr("findblobnruns", "calloc", "blobras");	blobrasity = *blobras;	if(erase_flag == ERASE)	  for(runp = list; runp < list_t; runp++)	    for(ps = (p = blobrasity + (runp->y - nlim) * inner_bw +              (runp->w_on - ras) % (int)ww - wlim) +  (runp->e_off -              runp->w_on); p < ps; p++)	      *p = 1;	else if(erase_flag == NO_ERASE)	  for(runp = list; runp < list_t; runp++)	    for(ps = (p = blobrasity + (runp->y - nlim) * inner_bw +              ((q = runp->w_on) - ras) % (int)ww - wlim) +  (runp->e_off -              runp->w_on); p < ps; p++, q++)	      *p = *q = 1;	else	  fatalerr("findblobnruns", "illegal value for erase_flag", NULL);	*box_w = inner_bw;	*box_h = inner_bh;	return 2;      }      else if(alloc_flag == NO_ALLOC)	fatalerr("findblobnruns", "Used NO_ALLOC and W_H_BLOB, and blob's \bounding box doesn't fit into specified output raster shape", NULL);      else	fatalerr("findblobnruns", "illegal value for alloc_flag", NULL);    }  }  else if(out_flag == BOUND_BLOB) {    if(alloc_flag == ALLOC) {      if(!(*blobras = (unsigned char *)calloc(inner_bw * inner_bh, 1)))	syserr("findblobnruns", "calloc", "blobras");    }    else if(alloc_flag == NO_ALLOC)      fatalerr("findblobnruns", "NO_ALLOC and BOUND_BLOB used together",        NULL);    else      fatalerr("findblobnruns", "illegal value for alloc_flag", NULL);    blobrasity = *blobras;    if(erase_flag == ERASE)      for(runp = list; runp < list_t; runp++)        for(ps = (p = blobrasity + (runp->y - nlim) * inner_bw +          (runp->w_on - ras) % (int)ww - wlim) + (runp->e_off -          runp->w_on); p < ps; p++)	  *p = 1;    else if(erase_flag == NO_ERASE)      for(runp = list; runp < list_t; runp++)        for(ps = (p = blobrasity + (runp->y - nlim) * inner_bw +          ((q = runp->w_on) - ras) % (int)ww - wlim) + (runp->e_off -          runp->w_on); p < ps; p++, q++)