/*# proc: blob_split_n_test - splits an image along a specified vertical path and then# proc:              tests to see if any of the resulting pieces is empty or too small# proc:              in which case cut points are adjusted and a new path is found.# proc: find_cut_path - given a starting x position, finds a vertical cut path through# proc:              the image by following the gradient of character stroke edges.# proc: split_blob_along_path - given a vertical path, actually divides the image into# proc:              two separate pieces.# proc: join_2_vert_paths - joins to vertical paths at their closest points and ensures# proc:              that there is one and only one point in the resulting path for each# proc:              y-value in the image.# proc: cut_caused_fragments - determines if cut created spurious fragments of characters# proc:              by counting the number of non-dot blobs in the resulting pieces.*/#include <math.h>#include <blobls.h>#include <stdio.h>#include <defs.h>#include <segchars.h>/*******************************************************************/blob_split_n_test(lblob, rblob, px, py, pn, pa, cut_x, esw, sblob)BLOB **lblob, **rblob, *sblob;int **px, **py, *pn, *pa;int cut_x, esw;{   int count_limit, count, next_x, xlimit, found;   count_limit = max(1,(sblob->w>>1)/esw); /* half the image's width in strokes */   count = 0;   next_x = cut_x;   xlimit = sblob->w-esw;   *lblob = (BLOB *)NULL;   *rblob = (BLOB *)NULL;   found = 0;   /* if we haven't looped too much, and the left or right piece is too small */   while((!found) && (count++ < count_limit)){      /* find cut path from new starting points */      find_cut_path(px, py, pn, pa, sblob->data, next_x, esw, sblob->w, sblob->h);      split_blob_along_path(lblob, rblob, *px, *py, *pn, sblob);      /* left and right piece should never both be too small */      /* move cut points one stroke width away from piece that's too small */      if((*lblob == NULL) || is_noise_blob(*lblob, esw)){         if(*lblob != NULL)            free_blob(*lblob);         if(*rblob != NULL)            free_blob(*rblob);         free(*px);         free(*py);         next_x += esw;         if(next_x >= xlimit){            break;         }      }      else if((*rblob == NULL) || is_noise_blob(*rblob, esw)){         if(*lblob != NULL)            free_blob(*lblob);         if(*rblob != NULL)            free_blob(*rblob);         free(*px);         free(*py);         next_x -= esw;         if(next_x < esw){            break;         }      }      else         found = 1;   }   /* if never found successful cut path ... */   if(!found){      return(FALSE);   }   else if(cut_caused_fragments(sblob, *lblob, *rblob, esw, sblob->h)){      free(*px);      free(*py);      free_blob(*lblob);      free_blob(*rblob);      return(FALSE);   }   else{      return(TRUE);   }}/*******************************************************************/blob_split_n_test_orig(lblob, rblob, px, py, pn, pa, cut_x, esw, sblob)BLOB **lblob, **rblob, *sblob;int **px, **py, *pn, *pa;int cut_x, esw;{   int count_limit, count, next_x, xlimit, ltest, found;   /* find cut path from starting points */   find_cut_path(px, py, pn, pa, sblob->data, cut_x, esw, sblob->w, sblob->h);   /* split the image along the path */   split_blob_along_path(lblob, rblob, *px, *py, *pn, sblob);   /* test left and right pieces */   count_limit = max(1,(sblob->w>>1)/esw); /* half the image's width in strokes */   count = 0;   next_x = cut_x;   xlimit = sblob->w-esw;   found = 1;   /* if we haven't looped too much, and the left or right piece is too small */   while((count++ < count_limit) &&         (ltest = ((*lblob == NULL) || is_noise_blob(*lblob, esw)) ||          (*rblob == NULL) || is_noise_blob(*rblob, esw))){      /* left and right piece should never both be too small */      /* move cut points one stroke width away from piece that's too small */      if(ltest){         next_x += esw;         if(next_x >= xlimit){            found = 0;            break;         }      }      else{         next_x -= esw;         if(next_x < esw){            found = 0;            break;         }      }      if(*lblob != NULL)         free_blob(*lblob);      if(*rblob != NULL)         free_blob(*rblob);      free(*px);      free(*py);      /* find cut path from new starting points */      find_cut_path(px, py, pn, pa, sblob->data, next_x, esw, sblob->w, sblob->h);      split_blob_along_path(lblob, rblob, *px, *py, *pn, sblob);   }   /* if never found successful cut path ... */   if((count > count_limit) || (!found)){      free(*px);      free(*py);      if(*lblob != NULL)         free_blob(*lblob);      if(*rblob != NULL)         free_blob(*rblob);      return(FALSE);   }   else if(cut_caused_fragments(sblob, *lblob, *rblob, esw, sblob->h)){      free(*px);      free(*py);      free_blob(*lblob);      free_blob(*rblob);      return(FALSE);   }   else{      return(TRUE);   }}/*******************************************************************/find_cut_path(px, py, pn, pa, cdata, cx, winw, w, h)int **px, **py, *pn, *pa;unsigned char *cdata;int cx, winw, w, h;{   int *dx, *dy, dn, da;   int *ux, *uy, un, ua, ui;   dribble_down_up(&dx, &dy, &dn, &da, &ux, &uy, &un, &ua,                     cdata, cx, winw, w, h);   /* if both paths pass all the way through the image ... */   if((dn == h) && (un == h)){      /* choose path whose midpt y is closer to the cut line */      if(abs(cx - dy[dn>>1]) > abs(cx - uy[un>>1])){         /* choose upward path */         dn = 0;         for(ui = un - 1; ui >= 0; ui--)            add_point(ux[ui], uy[ui], &dx, &dy, &dn, &da);      }      /* otherwise use downward path (by default) */   }   /* if downward path cuts all the way through the image ... */   else if (dn == h){      /* use downward path by default */   }   /* if upward path cuts all the way through the image ... */   else if (un == h){      dn = 0;      for(ui = un - 1; ui >= 0; ui--)         add_point(ux[ui], uy[ui], &dx, &dy, &dn, &da);   }   /* if both paths have some points ... */   else if((dn > 0) && (un > 0)){      join_2_vert_paths(&dx, &dy, &dn, &da, &ux, &uy, &un, &ua);   }   /* otherwise, should never have no cut points */   free(ux);   free(uy);   *px = dx;   *py = dy;   *pn = dn;   *pa = da;}/*******************************************************************//* split_blob_along_path returns NULL blob pointers if unsuccessful*//*******************************************************************/split_blob_along_path(lblob, rblob, px, py, pn, sblob)BLOB **lblob, **rblob, *sblob;int *px, *py, pn;{   unsigned char *ldata, *rdata, *lptr, *rptr, *cptr;   unsigned char *mallocate_image(), *allocate_image();   int i, w, h, min_px, max_px;   int lw, rw;   int blx, bly, blw, blh;   int brx, bry, brw, brh;   static int flags = BLOB_XY1S | BLOB_WHS | BLOB_AS;   if(pn != sblob->h)      fatalerr("split_blob_along_path",               "number of points not equal to height of blob image", NULL);   w = sblob->w;   h = sblob->h;   find_first_max_forward(px, 0, pn, &i, &max_px);   lw = max_px;   find_first_min_forward(px, 0, pn, &i, &min_px);   rw = w - min_px;   /* if left or right piece empty ... */   if((lw == 0) || (rw == 0)){      *lblob = (BLOB *)NULL;      *rblob = (BLOB *)NULL;      return;   }   ldata = allocate_image(lw, h, 8);   rdata = allocate_image(rw, h, 8);   lptr = ldata;/* more readable, but less efficient *//*   rptr = rdata; */   rptr = rdata - min_px;   cptr = sblob->data;   for(i = 0; i < pn; i++){      memcpy(lptr, cptr, px[i]);      /* more readable, but less efficient *//*      memcpy(rptr+px[i]-min_px, cptr+px[i], w-px[i]); */      memcpy(rptr+px[i], cptr+px[i], w-px[i]);      lptr += lw;      rptr += rw;      cptr += w;   }   find_corners8(&blx, &bly, &blw, &blh, ldata, lw, h);   if((blw != 0) && (blh != 0)){      build_blob(lblob, flags, mallocate_image(blw, blh, 8), blx, bly, blw, blh);      subimage_copy(ldata, lw, h, (*lblob)->data, blw, blh, blx, bly, blw, blh, 0, 0);   }   else      *lblob = (BLOB *)NULL;   find_corners8(&brx, &bry, &brw, &brh, rdata, rw, h);   if((brw != 0) && (brh != 0)){      build_blob(rblob, flags, mallocate_image(brw, brh, 8),                 min_px+brx, bry, brw, brh);      subimage_copy(rdata, rw, h, (*rblob)->data, brw, brh, brx, bry, brw, brh, 0, 0);   }   else      *rblob = (BLOB *)NULL;   free(ldata);   free(rdata);}/*******************************************************************/split_blob_along_path_orig(lblob, rblob, px, py, pn, sblob)BLOB **lblob, **rblob, *sblob;int *px, *py, pn;{   unsigned char *ldata, *rdata, *lptr, *rptr, *cptr;   unsigned char *mallocate_image(), *allocate_image();   int i, w, h, min_px, max_px;   int lw, rw;   int blx, bly, blw, blh;   int brx, bry, brw, brh;   static int flags = BLOB_XY1S | BLOB_WHS | BLOB_AS;   if(pn != sblob->h)      fatalerr("split_blob_along_path",               "number of points not equal to height of blob image", NULL);   w = sblob->w;   h = sblob->h;   find_first_max_forward(px, 0, pn, &i, &max_px);   lw = max_px;   ldata = allocate_image(lw, h, 8);   find_first_min_forward(px, 0, pn, &i, &min_px);   rw = w - min_px;   rdata = allocate_image(rw, h, 8);   lptr = ldata;/* more readable, but less efficient *//*   rptr = rdata; */   rptr = rdata - min_px;   cptr = sblob->data;   for(i = 0; i < pn; i++){      memcpy(lptr, cptr, px[i]);      /* more readable, but less efficient *//*      memcpy(rptr+px[i]-min_px, cptr+px[i], w-px[i]); */      memcpy(rptr+px[i], cptr+px[i], w-px[i]);      lptr += lw;      rptr += rw;      cptr += w;   }   find_corners8(&blx, &bly, &blw, &blh, ldata, lw, h);   if((blw != 0) && (blh != 0)){      build_blob(lblob, flags, mallocate_image(blw, blh, 8), blx, bly, blw, blh);      subimage_copy(ldata, lw, h, (*lblob)->data, blw, blh, blx, bly, blw, blh, 0, 0);   }   else      *lblob = (BLOB *)NULL;   find_corners8(&brx, &bry, &brw, &brh, rdata, rw, h);   if((brw != 0) && (brh != 0)){      build_blob(rblob, flags, mallocate_image(brw, brh, 8),                 min_px+brx, bry, brw, brh);      subimage_copy(rdata, rw, h, (*rblob)->data, brw, brh, brx, bry, brw, brh, 0, 0);   }   else      *rblob = (BLOB *)NULL;   free(ldata);   free(rdata);}/*******************************************************************/join_2_vert_paths(dx, dy, dn, da, ux, uy, un, ua)int **dx, **dy, *dn, *da;int **ux, **uy, *un, *ua;{   int last_y;   int *sx, *sy, sn, sa, si, ui;   int dcx, dcy, dci, ucx, ucy, uci;   find_closest_pts(&dcx, &dcy, &dci, &ucx, &ucy, &uci, *dx, *dy, *dn, *ux, *uy, *un);   /* interpolate line between (dcx, dcy) and (ucx, ucy) */   sa = 0;   bres_line_alloc(dcx, dcy, ucx, ucy, &sx, &sy, &sn, &sa);   /* reset down list so point at dci is last point in list */   *dn = dci + 1;   /* append interpolated line to down list */   /* do not copy endpoints (dcx, dcy) and (ucx, ucy) */   /* do not copy consecutive ponts with same y coord */   last_y = dcy;   for(si = 1; si < sn - 1; si++){      if(sy[si] > last_y){         add_point(sx[si], sy[si], dx, dy, dn, da);         last_y = sy[si];      }   }   /* append upward points in reverse order from (ucx, ucy) */   if(last_y == ucy)      ui = uci - 1;   else      ui = uci;   for(; ui >= 0; ui--){      if((*uy)[ui] > last_y){         add_point((*ux)[ui], (*uy)[ui], dx, dy, dn, da);         last_y = (*uy)[ui];      }   }   free(sx);   free(sy);}/************************************************************/cut_caused_fragments(blob, lblob, rblob, esw, charh)BLOB *blob, *lblob, *rblob;int esw, charh;{   int hlimit;   int otot, ltot, rtot;   hlimit = sround(charh * FRAG_HEIGHT);   /* if left or right piece is a fragment */   if((lblob->h < hlimit) || (rblob->h < hlimit))      return(TRUE);   /* count number of non-dots in original blob */   otot = count_nondots_blob(blob, esw);   /* count number of non-dots in left piece */   ltot = count_nondots_blob(lblob, esw);   /* count number of non-dots in right piece */   rtot = count_nondots_blob(rblob, esw);   if(otot != ltot + rtot - 1)      return(TRUE);   else      return(FALSE);}