lib/pdf/bbox.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <memory.h>
   4 #include <math.h>
   5 #include <assert.h>
   6 #include "../types.h"
   7 #include "../mem.h"
   8
   9 typedef struct _ibbox {
  10     int xmin,ymin,xmax,ymax;
  11     struct _ibbox*next;
  12 } ibbox_t;
  13
  14 ibbox_t* ibbox_new(int x1, int y1, int x2, int y2)
  15 {
  16     ibbox_t*b = (ibbox_t*)rfx_calloc(sizeof(ibbox_t));
  17     b->xmin = x1;
  18     b->ymin = y1;
  19     b->xmax = x2;
  20     b->ymax = y2;
  21     return b;
  22 }
  23
  24 void ibbox_destroy(ibbox_t*b)
  25 {
  26     while(b) {
  27         ibbox_t*next = b->next;
  28         free(b);
  29         b = next;
  30     }
  31 }
  32
  33 ibbox_t*get_bitmap_bboxes_simple(unsigned char*alpha, int width, int height)
  34 {
  35     int ymin = -1;
  36     int ymax = -1;
  37     int xmin = width;
  38     int xmax = 0;
  39
  40     int x,y;
  41     for(y=0;y<height;y++) {
  42         unsigned char*a = &alpha[y*width];
  43         for(x=0;x<width;x++) {
  44             if(a[x]) break;
  45         }
  46         int left = x; //first occupied pixel from left
  47         int right = x+1; //last non-occupied pixel from right
  48         for(;x<width;x++) {
  49             if(a[x]) right=x+1;
  50         }
  51
  52         if(left!=width) {
  53             if(ymin<0)
  54                 ymin=y;
  55             ymax=y+1;
  56             if(left<xmin) xmin = left;
  57             if(right>xmax) xmax = right;
  58         }
  59     }
  60     ibbox_t* bbox = 0;
  61     if(xmin<xmax || ymin<ymax) {
  62         bbox = ibbox_new(xmin, ymin, xmax, ymax);
  63     }
  64     return bbox;
  65 }
  66
  67 typedef struct _head {
  68     ptroff_t magic;
  69     ibbox_t bbox;
  70     int nr;
  71     int pos;
  72     int rank;
  73     int x,y;
  74     char seen;
  75     struct _head*next;
  76     struct _head*prev;
  77 } head_t;
  78
  79 typedef struct _context {
  80     void**group;
  81     unsigned char*alpha;
  82     int width;
  83     int height;
  84     head_t*heads;
  85     int count;
  86 } context_t;
  87
  88 #define HEAD_MAGIC ((ptroff_t)-1)
  89
  90 static head_t*head_new(context_t*context, int x, int y)
  91 {
  92     int pos = context->width*y+x;
  93     head_t*h = rfx_calloc(sizeof(head_t));
  94     h->magic = HEAD_MAGIC;
  95     h->nr = context->count++;
  96     h->pos = pos;
  97     h->x = x;
  98     h->y = y;
  99     h->bbox.xmin = h->bbox.xmax = x;
 100     h->bbox.ymin = h->bbox.ymax = y;
 101     h->next = context->heads;
 102     context->heads = h;
 103     if(h->next) {
 104         h->next->prev = h;
 105     }
 106     return h;
 107 }
 108
 109 static void head_delete(context_t*context, head_t*h)
 110 {
 111     if(h->prev) {
 112         h->prev->next = h->next;
 113     }
 114     if(h->next) {
 115         h->next->prev = h->prev;
 116     }
 117     if(h==context->heads) {
 118         assert(!h->prev);
 119         context->heads = h->next;
 120     }
 121 }
 122
 123 #define POINTS_TO_HEAD(ptr) (((head_t*)(ptr))->magic==HEAD_MAGIC)
 124
 125 static inline void link_to(context_t*context, int from, int to)
 126 {
 127     // path compression
 128     void**data = context->group;
 129     int head = to;
 130     assert(data[head]);
 131     while(!POINTS_TO_HEAD(data[head])) {
 132         assert(data[head]!=(void*)&data[head]); // check that we're not in an infinite loop
 133         head=(void**)data[head]-(void**)data;
 134     }
 135     head_t*h = (head_t*)data[head];
 136     int x = from%context->width;
 137     int y = from/context->width;
 138     if(x < h->bbox.xmin) h->bbox.xmin = x;
 139     if(y < h->bbox.ymin) h->bbox.ymin = y;
 140     if(x > h->bbox.xmax) h->bbox.xmax = x;
 141     if(y > h->bbox.ymax) h->bbox.ymax = y;
 142
 143     data[from] = (void*)&data[head];
 144 }
 145 static char ibbox_does_overlap(ibbox_t*b1, ibbox_t*b2)
 146 {
 147     if(b1->xmax < b2->xmin) return 0;
 148     if(b2->xmax < b1->xmin) return 0;
 149     if(b1->ymax < b2->ymin) return 0;
 150     if(b2->ymax < b1->ymin) return 0;
 151     return 1;
 152 }
 153 static void ibbox_expand(ibbox_t*src, ibbox_t*add)
 154 {
 155     if(add->xmin < src->xmin)
 156         src->xmin = add->xmin;
 157     if(add->ymin < src->ymin)
 158         src->ymin = add->ymin;
 159     if(add->xmax > src->xmax)
 160         src->xmax = add->xmax;
 161     if(add->ymax > src->ymax)
 162         src->ymax = add->ymax;
 163 }
 164 static inline void merge(context_t*context, int set1, int set2)
 165 {
 166     void**data = context->group;
 167     assert(data[set1]);
 168     assert(data[set2]);
 169     int head1 = set1;
 170     int head2 = set2;
 171     while(!POINTS_TO_HEAD(data[head1])) {
 172         head1=(void**)data[head1]-(void**)data;
 173     }
 174     while(!POINTS_TO_HEAD(data[head2])) {
 175         head2=(void**)data[head2]-(void**)data;
 176     }
 177     head_t*h1 = (head_t*)data[head1];
 178     head_t*h2 = (head_t*)data[head2];
 179     if(h1==h2)
 180         return;
 181
 182     if(h1->rank>h2->rank) {
 183         h1->rank++;
 184         ibbox_expand(&h1->bbox,&h2->bbox);
 185         data[head2] = (void*)&data[head1];
 186         head_delete(context, h2);
 187     } else {
 188         h2->rank++;
 189         ibbox_expand(&h2->bbox,&h1->bbox);
 190         data[head1] = (void*)&data[head2];
 191         head_delete(context, h1);
 192     }
 193 }
 194
 195 static void** annotate(context_t*context)
 196 {
 197     unsigned char*alpha = context->alpha;
 198     int width = context->width;
 199     int height = context->height;
 200     void** group = rfx_calloc(width*height*sizeof(void*));
 201     context->group = group;
 202     int x,y;
 203
 204     for(x=1;x<width;x++) {
 205         if(alpha[x]) {
 206             if(group[x-1])
 207                 link_to(context,x,x-1);
 208             else
 209                 group[x]=head_new(context,x,0);
 210         }
 211     }
 212     int pos = 0;
 213     for(y=1;y<height;y++) {
 214         pos += width;
 215         if(alpha[pos]) {
 216             if(group[pos-width])
 217                 link_to(context,pos,pos-width);
 218             else
 219                 group[pos]=head_new(context,0,y);
 220         }
 221         for(x=1;x<width;x++) {
 222             /* once this code is stable we should copy&paste it
 223                out of the loop, change the loop end to width-1 and
 224                add the pos-width+1 case */
 225             if(alpha[pos+x]) {
 226                 if(group[pos+x-width]) {
 227                     link_to(context,pos+x,pos+x-width);
 228                     if(group[pos+x-1])
 229                         merge(context,pos+x,pos+x-1);
 230                 } else if(group[pos+x-1]) {
 231                     link_to(context,pos+x,pos+x-1);
 232                 } else if(group[pos+x-width-1]) {
 233                     link_to(context,pos+x,pos+x-width-1);
 234                 } else {
 235                     group[pos+x]=head_new(context,x,y);
 236                 }
 237             }
 238         }
 239     }
 240     return group;
 241 }
 242
 243 static void overlap_bboxes(context_t*context)
 244 {
 245     char changed;
 246     do {
 247         head_t*h1 = context->heads;
 248         changed = 0;
 249         while(h1) {
 250             head_t*next = h1->next;
 251             head_t*h2 = context->heads;
 252             while(h2) {
 253                 if(h1!=h2) {
 254                     if(ibbox_does_overlap(&h1->bbox, &h2->bbox)) {
 255                         merge(context, h1->pos, h2->pos);
 256                         changed = 1;
 257                         break;
 258                     }
 259                 }
 260                 h2 = h2->next;
 261             }
 262             h1 = next;
 263         }
 264     } while(changed);
 265 }
 266
 267 static head_t* search_vicinity(context_t*context, head_t*h, int max_radius, double*cos, double*sin)
 268 {
 269     int t;
 270     void**data = context->group;
 271     /* FIXME: this function isn't very efficient. We need a better way to iterate
 272        through all points, sorted by distance, in the neighborhood of a coordinate */
 273     for(t=3;t<max_radius*2;t++) {
 274         int s;
 275         for(s=0;s<256;s++) {
 276             int x=h->x+cos[s]*t/4.0+0.5;
 277             int y=h->y+sin[s]*t/4.0+0.5;
 278             if(x>=0 && y>=0 && x<context->width && y<context->height) {
 279                 int pos = y*context->width+x;
 280                 if(data[pos]) {
 281                     while(!POINTS_TO_HEAD(data[pos])) {
 282                         pos=(void**)data[pos]-(void**)data;
 283                     }
 284                     head_t*new_head = (head_t*)data[pos];
 285                     if(new_head != h) {
 286                         return new_head;
 287                     }
 288                 }
 289             }
 290         }
 291     }
 292     return 0;
 293 }
 294
 295 static void fix_small_boxes(context_t*context)
 296 {
 297     double sintab[256];
 298     double costab[256];
 299     int t;
 300     for(t=0;t<256;t++) {
 301         sintab[t] = sin(t*M_PI/128);
 302         costab[t] = cos(t*M_PI/128);
 303     }
 304
 305     head_t*h = context->heads;
 306     while(h) {
 307         h->seen = 0;
 308         h = h->next;
 309     }
 310
 311     char changed;
 312     do {
 313         changed = 0;
 314         head_t*h = context->heads;
 315         while(h) {
 316             head_t*next = h->next;
 317             if(!h->seen) {
 318                 if(h->bbox.xmax - h->bbox.ymin < 16
 319                 && h->bbox.ymax - h->bbox.ymin < 16) {
 320                     head_t*other = search_vicinity(context, h, 64, costab, sintab);
 321                     if(other) {
 322                         merge(context, h->pos, other->pos);
 323                         changed = 1;
 324                         break;
 325                     } else {
 326                         h->seen = 1;
 327                     }
 328                 }
 329             }
 330             h = next;
 331         }
 332     } while(changed);
 333 }
 334
 335 static void display(context_t*context)
 336 {
 337     int width = context->width;
 338     int height = context->height;
 339     void**group = context->group;
 340
 341     int x,y;
 342     for(y=0;y<height;y++) {
 343         for(x=0;x<width;x++) {
 344             if(!group[y*width+x]) {
 345                 printf(" -- ");
 346             } else if(POINTS_TO_HEAD(group[y*width+x])) {
 347                 printf("g%02d ", ((head_t*)group[y*width+x])->nr);
 348             } else {
 349                 printf("x%02d ", (void**)group[y*width+x]-(void**)group);
 350             }
 351         }
 352         printf("\n");
 353     }
 354
 355     head_t*h = context->heads;
 356     while(h) {
 357         printf("head: %d\n", h->nr);
 358         printf(" pos: %d/%d\n", h->pos%width, h->pos/width);
 359         printf(" bbox: [%d/%d,%d/%d]\n", h->bbox.xmin, h->bbox.ymin, h->bbox.xmax, h->bbox.ymax);
 360         h = h->next;
 361     }
 362 }
 363
 364 ibbox_t*get_bitmap_bboxes(unsigned char*alpha, int width, int height)
 365 {
 366     int size = width*height;
 367     if(width<=1 || height<=1)
 368         return get_bitmap_bboxes_simple(alpha, width, height);
 369
 370     context_t context;
 371     context.alpha = alpha;
 372     context.width = width;
 373     context.height = height;
 374     context.heads = 0;
 375     context.count = 1;
 376
 377     void**group = annotate(&context);
 378     fix_small_boxes(&context);
 379     overlap_bboxes(&context);
 380
 381     ibbox_t*bboxes = 0;
 382
 383     head_t*h = context.heads;
 384     while(h) {
 385         head_t*next = h->next;
 386         ibbox_t*bbox = malloc(sizeof(ibbox_t));
 387         memcpy(bbox, &h->bbox, sizeof(ibbox_t));
 388
 389         /* ibbox_t defines the open upper bound */
 390         bbox->xmax++;
 391         bbox->ymax++;
 392
 393         bbox->next = bboxes;
 394         bboxes = bbox;
 395         free(h);
 396         h = next;
 397     }
 398     free(context.group);
 399     return bboxes;
 400 }
 401
 402 #ifdef MAIN
 403 int main(int argn, char*argv[])
 404 {
 405     unsigned char alpha[8*8]=
 406         "\0\0\1\0\0\0\0\0"
 407         "\1\0\0\1\0\1\0\0"
 408         "\0\0\0\0\0\0\1\0"
 409         "\0\0\1\0\1\0\0\0"
 410         "\1\0\1\0\1\0\0\0"
 411         "\1\0\1\1\1\0\0\1"
 412         "\1\0\0\0\0\0\1\0"
 413         "\1\1\1\0\0\0\0\0";
 414
 415     get_bitmap_bboxes(alpha, 8,8);
 416 }
 417 #endif