lib/gocr/box.c

   1 /*
   2 This is a Optical-Character-Recognition program
   3 Copyright (C) 2000-2007  Joerg Schulenburg
   4
   5 This program is free software; you can redistribute it and/or
   6 modify it under the terms of the GNU General Public License
   7 as published by the Free Software Foundation; either version 2
   8 of the License, or (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18
  19  see README for EMAIL address
  20
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <assert.h>
  26 #include <string.h>
  27 /* do we need #include <math.h>? conflicts with INFINITY in unicode.h */
  28 #include "gocr.h"
  29 #include "pgm2asc.h"
  30
  31 /* for sorting letters by position on the image
  32 / ToDo: - use function same line like this or include lines.m1 etc. */
  33 int box_gt(struct box *box1, struct box *box2) {
  34  // box1 after box2 ?
  35   if (box1->line > box2->line)
  36     return 1;
  37   if (box1->line < box2->line)
  38     return 0;
  39   if (box1->x0 > box2->x1)      // before
  40     return 1;
  41   if (box1->x1 < box2->x0)      // before
  42     return 0;
  43   if (box1->x0 > box2->x0)      // before,  overlapping!
  44     return 1;
  45
  46   return 0;
  47 }
  48
  49 /* --- copy part of pix p into new pix b        ---- len=10000
  50  * Returns: 0 on success, 1 on error.
  51  * naming it as copybox isnt very clever, because it dont have to do with the
  52  *   char boxes (struct box)
  53  */
  54 int copybox (pix * p, int x0, int y0, int dx, int dy, pix * b, int len) {
  55   int x, y;
  56
  57   /* test boundaries */
  58   if (b->p == NULL || dx < 0 || dy < 0 || dx * dy > len) {
  59     fprintf(stderr, " error-copybox x=%5d %5d  d=%5d %5d\n", x0, y0, dx, dy);
  60     return 1;
  61   }
  62
  63   b->x = dx;
  64   b->y = dy;
  65   b->bpp = 1;
  66 #ifdef FASTER_INCOMPLETE
  67   for (y = 0; y < dy; y++)
  68     memcpy(&pixel_atp(b, 0, y), &pixel_atp(p, x0, y + y0 ), dx);
  69   // and unmark pixels
  70 #else
  71   for (y = 0; y < dy; y++)
  72     for (x = 0; x < dx; x++)
  73       pixel_atp(b, x, y) = getpixel(p, x + x0, y + y0);
  74 #endif
  75
  76   return 0;
  77 }
  78
  79 /* reset table of alternative chars (and free memory) */
  80 int reset_box_ac(struct box *box){
  81   int i;
  82   for (i=0; i<box->num_ac; i++)
  83     if (box->tas[i]) {
  84        /* fprintf(stderr,"DBG free_s[%d] %p %s\n",i,box->tas[i],box->tas[i]); */
  85        free(box->tas[i]);
  86        box->tas[i]=0;     /* prevent double freeing */
  87      }
  88   box->num_ac=0;  /* mark as freed */
  89   return 0;
  90 }
  91
  92 /* ini or copy a box: get memory for box and initialize the memory */
  93 struct box *malloc_box (struct box *inibox) {
  94   struct box *buf;
  95   int i;
  96
  97   buf = (struct box *) malloc(sizeof(struct box));
  98   if (!buf)
  99     return NULL;
 100   if (inibox) {
 101     memcpy(buf, inibox, sizeof(struct box));
 102     /* only pointer are copied, we want to copy the contents too */
 103     for (i=0;i<inibox->num_ac;i++) {
 104       if (inibox->tas[i]) {
 105         buf->tas[i]=(char *)malloc(strlen(inibox->tas[i])+1);
 106         memcpy(buf->tas[i], inibox->tas[i], strlen(inibox->tas[i])+1);
 107       }
 108     }
 109   }
 110   else { /* ToDo: init it */
 111     buf->num_ac=0;
 112     buf->num_frames=0;
 113   }
 114   /* fprintf(stderr,"\nDBG ini_box %p",buf); */
 115   return buf;
 116 }
 117
 118 /* free memory of box */
 119 int free_box (struct box *box) {
 120   if (!box) return 0;
 121   /* fprintf(stderr,"DBG free_box %p\n",box); out_x(box); */
 122   reset_box_ac(box); /* free alternative char table */
 123   free(box);         /* free the box memory */
 124   return 0;
 125 }
 126
 127 /* simplify the vectorgraph,
 128  *  but what is the best way?
 129  *   a) melting two neighbouring vectors with nearly same direction?
 130  *      (nearest angle to pi)
 131  *   b) melting three neigbours with smallest area?
 132  * ToDo:
 133  * mode = 0 - only lossless
 134  * mode = 1 - reduce one vector, smallest possible loss
 135  * mode = 2 - remove jitter (todo, or somewhere else)
 136  * ToDo: include also loop around (last - first element)
 137  * ToDo: reduce by 10..50%
 138  */
 139 int reduce_vectors ( struct box *box1, int mode ) {
 140   int i1, i2, nx, ny, mx, my, len,
 141       minlen=1024, /* minlength of to neighbouring vectors */
 142       besti1=0,  /* frame for best reduction */
 143       besti2=2;  /* vector replacing its predecessor */
 144   double  sprod, maxsprod=-1;
 145   if (mode!=1) fprintf(stderr,"ERR not supported yet, ToDo\n");
 146   for (i2=1,i1=0; i1<box1->num_frames; i1++) {    /* every frame */
 147     for (;i2<box1->num_frame_vectors[i1]-1; i2++) { /* every vector */
 148       /* predecessor n */
 149       nx = box1->frame_vector[i2-0][0] - box1->frame_vector[i2-1][0];
 150       ny = box1->frame_vector[i2-0][1] - box1->frame_vector[i2-1][1];
 151       /* successor   m */
 152       mx = box1->frame_vector[i2+1][0] - box1->frame_vector[i2-0][0];
 153       my = box1->frame_vector[i2+1][1] - box1->frame_vector[i2-0][1];
 154       /* angle is w = a*b/(|a|*|b|) = 1 means parallel   */
 155       /* normalized: minimize w^2 = (a*b/(|a|*|b|)-1)^2  */
 156       /*             -1=90grd, 0=0grd, -2=180grd         */
 157       sprod = /* fabs */(abs(nx*mx+ny*my)*(nx*mx+ny*my)
 158                        /(1.*(nx*nx+ny*ny)*(mx*mx+my*my))-1);
 159       /* we dont include math.h because INFINITY conflicts to unicode,h */
 160       if (sprod<0) sprod=-sprod;
 161       len =           (mx*mx+my*my)*(nx*nx+ny*ny); /* sum lengths^2 */
 162 // ..c          ###c           ...          ..          ...
 163 // .b. len=2+2  #b.. len=2+5   #bc len=1+2  bc len=1+1  b#a len=4+5
 164 // a.. spr=0    a... spr=1/10  a.. spr=1/4  a. spr=1    ##c spr=9/5
 165 //
 166       if (   len*   sprod*   sprod*   sprod*   sprod
 167          <minlen*maxsprod*maxsprod*maxsprod*maxsprod
 168        || maxsprod<0) /* Bad! ToDo! */
 169       { maxsprod=sprod; besti1=i1; besti2=i2; minlen=len; }
 170     }
 171   }
 172   if (box1->num_frames>0)
 173   for (i2=besti2; i2<box1->num_frame_vectors[ box1->num_frames-1 ]-1; i2++) {
 174     box1->frame_vector[i2][0]=box1->frame_vector[i2+1][0];
 175     box1->frame_vector[i2][1]=box1->frame_vector[i2+1][1];
 176   }
 177   for (i1=besti1; i1<box1->num_frames; i1++)
 178     box1->num_frame_vectors[i1]--;
 179 //  fprintf(stderr,"\nDBG_reduce_vectors i= %d nv= %d sprod=%f len2=%d\n# ...",
 180 //     besti2,box1->num_frame_vectors[ box1->num_frames-1 ],maxsprod,minlen);
 181 //  out_x(box1);
 182   return 0;
 183 }
 184
 185 /* add the contents of box2 to box1
 186  * especially add vectors of box2 to box1
 187  */
 188 int merge_boxes( struct box *box1, struct box *box2 ) {
 189   int i1, i2, i3, i4;
 190   struct box tmpbox, *bsmaller, *bbigger; /* for mixing and sorting */
 191   /* DEBUG, use valgrind to check uninitialized memory */
 192 #if 0
 193   fprintf(stderr,"\nDBG merge_boxes_input:"); out_x(box1); out_x(box2);
 194 #endif
 195   /* pair distance is to expendable, taking borders is easier */
 196   if ((box2->x1 - box2->x0)*(box2->y1 - box2->y0)
 197      >(box1->x1 - box1->x0)*(box1->y1 - box1->y0)) {
 198       bbigger=box2; bsmaller=box1; }
 199   else {
 200       bbigger=box1; bsmaller=box2; }
 201   /* ToDo: does not work if a third box is added */
 202   if (box2->y0>box1->y1 || box2->y1<box1->y0
 203    || box2->x0>box1->x1 || box2->x1<box1->x0) {
 204     box1->num_boxes    += box2->num_boxes;    /* num seperate objects 2=ij */
 205   } else {
 206     if (box2->num_boxes>box1->num_boxes) box1->num_boxes=box2->num_boxes;
 207     box1->num_subboxes += box2->num_subboxes+1; /* num holes 1=abdepq 2=B */
 208   }
 209   box1->dots         += box2->dots;         /* num i-dots */
 210   if ( box2->x0 < box1->x0 ) box1->x0 = box2->x0;
 211   if ( box2->x1 > box1->x1 ) box1->x1 = box2->x1;
 212   if ( box2->y0 < box1->y0 ) box1->y0 = box2->y0;
 213   if ( box2->y1 > box1->y1 ) box1->y1 = box2->y1;
 214   i1 = i2 = 0;
 215   if (bbigger->num_frames)
 216     i1 =  bbigger->num_frame_vectors[  bbigger->num_frames - 1 ];
 217   if (bsmaller->num_frames)
 218     i2 = bsmaller->num_frame_vectors[ bsmaller->num_frames - 1 ];
 219   while (i1+i2 > MaxFrameVectors) {
 220     if (i1>i2) { reduce_vectors(  bbigger, 1 ); i1--; }
 221     else       { reduce_vectors( bsmaller, 1 ); i2--; }
 222   }
 223   /* if i1+i2>MaxFrameVectors  simplify the vectorgraph */
 224   /* if sum num_frames>MaxNumFrames  through shortest graph away and warn */
 225   /* first copy the bigger box */
 226   memcpy(&tmpbox, bbigger, sizeof(struct box));
 227   /* attach the smaller box */
 228   for (i4=i3=0; i3<bsmaller->num_frames; i3++) {
 229     if (tmpbox.num_frames>=MaxNumFrames) break;
 230
 231     for  (; i4<bsmaller->num_frame_vectors[i3]; i4++) {
 232       memcpy(tmpbox.frame_vector[i1],
 233           bsmaller->frame_vector[i4],2*sizeof(int));
 234       i1++;
 235     }
 236     tmpbox.num_frame_vectors[ tmpbox.num_frames ] = i1;
 237     tmpbox.frame_vol[ tmpbox.num_frames ] = bsmaller->frame_vol[ i3 ];
 238     tmpbox.frame_per[ tmpbox.num_frames ] = bsmaller->frame_per[ i3 ];
 239     tmpbox.num_frames++;
 240     if (tmpbox.num_frames>=MaxNumFrames) {
 241       if (JOB->cfg.verbose)
 242         fprintf(stderr,"\nDBG merge_boxes MaxNumFrames reached");
 243       break;
 244     }
 245   }
 246   /* copy tmpbox to destination */
 247   box1->num_frames = tmpbox.num_frames;
 248   memcpy(box1->num_frame_vectors,
 249          tmpbox.num_frame_vectors,sizeof(int)*MaxNumFrames);
 250   memcpy(box1->frame_vol,
 251          tmpbox.frame_vol,sizeof(int)*MaxNumFrames);
 252   memcpy(box1->frame_per,
 253          tmpbox.frame_per,sizeof(int)*MaxNumFrames);
 254   memcpy(box1->frame_vector,
 255          tmpbox.frame_vector,sizeof(int)*2*MaxFrameVectors);
 256 #if 0
 257   if (JOB->cfg.verbose)
 258     fprintf(stderr,"\nDBG merge_boxes_result:"); out_x(box1);
 259 #endif
 260   return 0;
 261 }
 262
 263 /* used for division of glued chars
 264  * after a box is splitted into 2, where vectors are copied to both,
 265  * vectors outside the new box are cutted and thrown away,
 266  * later replaced by
 267  *  - 1st remove outside vectors with outside neighbours (complete frames?)
 268  *        add vector on outside vector with inside neighbours
 269  *        care about connections through box between outside vectors
 270  *  - 2nd reduce outside crossings (inclusive splitting frames if necessary)
 271  *        depending on direction (rotation) of outside connections
 272  *  - 3th shift outside vectors to crossing points
 273  *  - split add this points, connect only in-out...out-in,
 274  *  - cutting can result in more objects
 275  * ToDo: dont connect  --1---2--------3----4--  new-y1 (inside above not drawn)
 276  *                        \   \->>>>-/    /             outside
 277  *                         \----<<<<-----/      old-y1
 278  *                            |======| subtractable?
 279  *
 280  *       only connect  --1---2--------3----4--  new-y1
 281  *                        \>>/        \>>>/     old-y1  outside
 282  *
 283  *  ToDo: new vol, per
 284  */
 285 int cut_box( struct box *box1) {
 286   int i1, i2, i3, i4, x, y, lx, ly, dbg=0;
 287   if (JOB->cfg.verbose) dbg=1;  // debug level, enlarge to get more output
 288   if (dbg) fprintf(stderr,"\n cut box x= %3d %3d", box1->x0, box1->y0);
 289   /* check if complete frames are outside the box */
 290   for (i1=0; i1<box1->num_frames; i1++){
 291     if (dbg>2) fprintf(stderr,"\n checking frame %d outside", i1);
 292     i2 = ((i1)?box1->num_frame_vectors[ i1-1 ]:0); // this frame
 293     i3 =       box1->num_frame_vectors[ i1   ];    // next frame
 294     for (i4=i2; i4 < i3; i4++) {
 295       x = box1->frame_vector[i4][0];
 296       y = box1->frame_vector[i4][1];
 297       /* break, if one vector is lying inside */
 298       if (x>=box1->x0 && x<=box1->x1 && y>=box1->y0 && y<=box1->y1) break;
 299     }
 300     if (i4==i3) { /* all vectors outside */
 301       if (dbg>1) fprintf(stderr,"\n remove frame %d",i1);
 302       /* replace all frames i1,i1+1,... by i1+1,i1+2,... */
 303       /* replace (x,y) pairs first */
 304       for (i4=i2; i4<box1->num_frame_vectors[ box1->num_frames-1 ]-(i3-i2);
 305            i4++) {
 306         box1->frame_vector[i4][0] = box1->frame_vector[i4+i3-i2][0];
 307         box1->frame_vector[i4][1] = box1->frame_vector[i4+i3-i2][1];
 308       }
 309       /* replace the num_frame_vectors */
 310       for (i4=i1; i4<box1->num_frames-1; i4++)
 311         box1->num_frame_vectors[ i4 ] =
 312           box1->num_frame_vectors[ i4+1 ]-(i3-i2);
 313       box1->num_frames--; i1--;
 314     }
 315   }
 316   /* remove vectors outside the box */
 317   i3=0;
 318   for (i1=0; i1<box1->num_frames; i1++){
 319     if (dbg>2) fprintf(stderr,"\n check cutting vectors on frame %d", i1);
 320     x = box1->frame_vector[0][0]; /* last x */
 321     y = box1->frame_vector[0][1]; /* last y */
 322     /* ToDo: start inside to get a closed object */
 323     if (x<box1->x0 || x>box1->x1 || y<box1->y0 || y>box1->y1) i3=1;
 324     for (i2=0; i2<box1->num_frame_vectors[ i1 ]; i2++) {
 325       lx = x; /* last x */
 326       ly = y; /* last y */
 327       x = box1->frame_vector[i2][0];
 328       y = box1->frame_vector[i2][1];
 329       // fprintf(stderr,"DBG LEV3 i2= %3d  xy= %3d %3d",i2,x,y);
 330       /* check if outside */
 331       if (x<box1->x0 || x>box1->x1 || y<box1->y0 || y>box1->y1) {
 332         /* replace by nearest point at border, ToDo: better crossingpoint */
 333         if (i3==0) {  /* wrong if it starts outside */
 334           if (x < box1->x0) x = box1->frame_vector[i2][0] = box1->x0;
 335           if (x > box1->x1) x = box1->frame_vector[i2][0] = box1->x1;
 336           if (y < box1->y0) y = box1->frame_vector[i2][1] = box1->y0;
 337           if (y > box1->y1) y = box1->frame_vector[i2][1] = box1->y1;
 338         } else {
 339           /* remove vector */
 340           if (dbg>1) fprintf(stderr,"\n remove vector[%d][%d] x= %2d %2d",i1,i2,x-box1->x0,y-box1->y0);
 341           for (i4=i2;i4<box1->num_frame_vectors[ box1->num_frames-1 ]-1;i4++) {
 342             box1->frame_vector[i4][0] = box1->frame_vector[i4+1][0];
 343             box1->frame_vector[i4][1] = box1->frame_vector[i4+1][1];
 344           }
 345           for (i4=i1; i4<box1->num_frames; i4++)
 346                          box1->num_frame_vectors[ i4 ]--;
 347           i2--; /* next element is shiftet now, setting back the counter */
 348         }
 349         i3++;
 350         // fprintf(stderr," outside i3= %d\n",i3);
 351         continue;
 352       }
 353       // fprintf(stderr," inside  i3= %d",i3);
 354       if (i3) { /* ToDo: better crossing point last vector and border */
 355           if (lx < box1->x0) lx = box1->x0;
 356           if (lx > box1->x1) lx = box1->x1;
 357           if (ly < box1->y0) ly = box1->y0;
 358           if (ly > box1->y1) ly = box1->y1;
 359           x = box1->frame_vector[i2][0] = lx;
 360           y = box1->frame_vector[i2][1] = ly;
 361           i3 = 0;
 362       }
 363       // fprintf(stderr," xy= %3d %3d\n",x,y);
 364     }
 365   }
 366   //if (dbg>2) { fprintf(stderr,"\nDBG cut_box_result:"); out_x(box1); }
 367   return 0;
 368 }
 369