| 1 |
/* |
| 2 |
* classify.c - classifying patterns |
| 3 |
*/ |
| 4 |
|
| 5 |
|
| 6 |
#include "../base/mdjvucfg.h" |
| 7 |
#include <minidjvu/minidjvu.h> |
| 8 |
#include <stdio.h> |
| 9 |
#include <stdlib.h> |
| 10 |
#include <string.h> |
| 11 |
#include <assert.h> |
| 12 |
|
| 13 |
|
| 14 |
/* Stuff for not using malloc in C++ |
| 15 |
* (left here for DjVuLibre compatibility) |
| 16 |
*/ |
| 17 |
#ifdef __cplusplus |
| 18 |
# define MALLOC(Type) new Type |
| 19 |
# define FREE(p) delete p |
| 20 |
# define MALLOCV(Type,n) new Type[n] |
| 21 |
# define FREEV(p) delete [] p |
| 22 |
#else |
| 23 |
# define MALLOC(Type) ((Type*)malloc(sizeof(Type))) |
| 24 |
# define FREE(p) do{if(p)free(p);}while(0) |
| 25 |
# define MALLOCV(Type,n) ((Type*)malloc(sizeof(Type)*(n))) |
| 26 |
# define FREEV(p) do{if(p)free(p);}while(0) |
| 27 |
#endif |
| 28 |
|
| 29 |
|
| 30 |
/* Classes are single-linked lists with an additional pointer to the last node. |
| 31 |
* This is an class item. |
| 32 |
*/ |
| 33 |
typedef struct ClassNode |
| 34 |
{ |
| 35 |
mdjvu_pattern_t ptr; |
| 36 |
struct ClassNode *next; /* NULL if this node is the last one */ |
| 37 |
struct ClassNode *global_next; /* next among all nodes to classify */ |
| 38 |
int32 tag; /* filled before the final dumping */ |
| 39 |
} ClassNode; |
| 40 |
|
| 41 |
/* Classes themselves are composed in double-linked list. */ |
| 42 |
typedef struct Class |
| 43 |
{ |
| 44 |
ClassNode *first, *last; |
| 45 |
struct Class *prev_class; |
| 46 |
struct Class *next_class; |
| 47 |
int32 last_page; /* last page on which this class was met */ |
| 48 |
} Class; |
| 49 |
|
| 50 |
|
| 51 |
typedef struct Classification |
| 52 |
{ |
| 53 |
Class *first_class; |
| 54 |
ClassNode *first_node, *last_node; |
| 55 |
} Classification; |
| 56 |
|
| 57 |
/* Creates an empty class and links it to the list of classes. */ |
| 58 |
static Class *new_class(Classification *cl) |
| 59 |
{ |
| 60 |
Class *c = MALLOC(Class); |
| 61 |
c->first = c->last = NULL; |
| 62 |
c->prev_class = NULL; |
| 63 |
c->next_class = cl->first_class; |
| 64 |
c->last_page = 0; |
| 65 |
if (cl->first_class) cl->first_class->prev_class = c; |
| 66 |
cl->first_class = c; |
| 67 |
return c; |
| 68 |
} |
| 69 |
|
| 70 |
/* Unlinks a class and deletes it. Its nodes are not deleted. */ |
| 71 |
static void delete_class(Classification *cl, Class *c) |
| 72 |
{ |
| 73 |
Class *prev = c->prev_class, *next = c->next_class; |
| 74 |
|
| 75 |
if (prev) |
| 76 |
prev->next_class = next; |
| 77 |
else |
| 78 |
cl->first_class = next; |
| 79 |
|
| 80 |
if (next) |
| 81 |
next->prev_class = prev; |
| 82 |
|
| 83 |
FREE(c); |
| 84 |
} |
| 85 |
|
| 86 |
/* Creates a new node and adds it to the given class. */ |
| 87 |
static ClassNode *new_node(Classification *cl, Class *c, mdjvu_pattern_t ptr) |
| 88 |
{ |
| 89 |
ClassNode *n = MALLOC(ClassNode); |
| 90 |
n->ptr = ptr; |
| 91 |
n->next = c->first; |
| 92 |
c->first = n; |
| 93 |
if (!c->last) c->last = n; |
| 94 |
n->global_next = NULL; |
| 95 |
|
| 96 |
if (cl->last_node) |
| 97 |
cl->last_node->global_next = n; |
| 98 |
else |
| 99 |
cl->first_node = n; |
| 100 |
|
| 101 |
cl->last_node = n; |
| 102 |
return n; |
| 103 |
} |
| 104 |
|
| 105 |
/* Merge two classes and delete one of them. */ |
| 106 |
static Class *merge(Classification *cl, Class *c1, Class *c2) |
| 107 |
{ |
| 108 |
if (!c1->first) |
| 109 |
{ |
| 110 |
delete_class(cl, c1); |
| 111 |
return c2; |
| 112 |
} |
| 113 |
if (c2->first) |
| 114 |
{ |
| 115 |
c1->last->next = c2->first; |
| 116 |
c1->last = c2->last; |
| 117 |
} |
| 118 |
delete_class(cl, c2); |
| 119 |
return c1; |
| 120 |
} |
| 121 |
|
| 122 |
/* Puts a tag on each node corresponding to its class. */ |
| 123 |
static unsigned put_tags(Classification *cl) |
| 124 |
{ |
| 125 |
int32 tag = 1; |
| 126 |
Class *c = cl->first_class; |
| 127 |
while (c) |
| 128 |
{ |
| 129 |
ClassNode *n = c->first; |
| 130 |
while (n) |
| 131 |
{ |
| 132 |
n->tag = tag; |
| 133 |
n = n->next; |
| 134 |
} |
| 135 |
c = c->next_class; |
| 136 |
tag++; |
| 137 |
} |
| 138 |
return tag - 1; |
| 139 |
} |
| 140 |
|
| 141 |
/* Deletes all classes; nodes are untouched. */ |
| 142 |
static void delete_all_classes(Classification *cl) |
| 143 |
{ |
| 144 |
Class *c = cl->first_class; |
| 145 |
while (c) |
| 146 |
{ |
| 147 |
Class *t = c; |
| 148 |
c = c->next_class; |
| 149 |
FREE(t); |
| 150 |
} |
| 151 |
} |
| 152 |
|
| 153 |
/* Compares p with nodes from c until a meaningful result. */ |
| 154 |
static int compare_to_class(mdjvu_pattern_t p, Class *c, int32 dpi, |
| 155 |
mdjvu_matcher_options_t options, int flag) |
| 156 |
{ |
| 157 |
int r = 0; |
| 158 |
ClassNode *n = c->first; |
| 159 |
while(n) |
| 160 |
{ |
| 161 |
r = mdjvu_match_patterns(p, n->ptr, dpi, options); |
| 162 |
if (r == flag) return 1; |
| 163 |
n = n->next; |
| 164 |
} |
| 165 |
return 0; |
| 166 |
} |
| 167 |
|
| 168 |
static void classify(Classification *cl, mdjvu_pattern_t p, |
| 169 |
int32 dpi, mdjvu_matcher_options_t options, |
| 170 |
int32 page /* of current pattern */) |
| 171 |
{ |
| 172 |
Class *class_of_this = NULL; |
| 173 |
Class *c, *next_c = NULL; |
| 174 |
for (c = cl->first_class; c; c = next_c) |
| 175 |
{ |
| 176 |
next_c = c->next_class; /* That's because c may be deleted in merging */ |
| 177 |
|
| 178 |
if (class_of_this == c) continue; |
| 179 |
if (c->last_page < page - 1) continue; /* multipage optimization */ |
| 180 |
if (compare_to_class(p, c, dpi, options, -1) || |
| 181 |
!compare_to_class(p, c, dpi, options, 1)) continue; |
| 182 |
|
| 183 |
if (class_of_this) |
| 184 |
class_of_this = merge(cl, class_of_this, c); |
| 185 |
else |
| 186 |
class_of_this = c; |
| 187 |
} |
| 188 |
if (!class_of_this) class_of_this = new_class(cl); |
| 189 |
if (page > class_of_this->last_page) |
| 190 |
class_of_this->last_page = page; |
| 191 |
new_node(cl, class_of_this, p); |
| 192 |
} |
| 193 |
|
| 194 |
static int32 get_tags_from_classification(mdjvu_pattern_t *b, int32 *r, int32 n, Classification *cl) |
| 195 |
{ |
| 196 |
int32 i; |
| 197 |
int32 max_tag = put_tags(cl); |
| 198 |
ClassNode *node; |
| 199 |
|
| 200 |
delete_all_classes(cl); |
| 201 |
|
| 202 |
i = 0; |
| 203 |
node = cl->first_node; |
| 204 |
while (node) |
| 205 |
{ |
| 206 |
ClassNode *t; |
| 207 |
while (!b[i]) |
| 208 |
{ |
| 209 |
r[i++] = 0; |
| 210 |
assert(i < n); /* because we have a node */ |
| 211 |
} |
| 212 |
r[i++] = node->tag; |
| 213 |
t = node; |
| 214 |
node = node->global_next; |
| 215 |
FREE(t); |
| 216 |
} |
| 217 |
if (i < n) while (i < n) r[i++] = 0; |
| 218 |
return max_tag; |
| 219 |
} |
| 220 |
|
| 221 |
static void init_classification(Classification *c) |
| 222 |
{ |
| 223 |
c->first_class = NULL; |
| 224 |
c->first_node = c->last_node = NULL; |
| 225 |
} |
| 226 |
|
| 227 |
MDJVU_IMPLEMENT int32 mdjvu_classify_patterns |
| 228 |
(mdjvu_pattern_t *b, int32 *r, int32 n, int32 dpi, |
| 229 |
mdjvu_matcher_options_t options) |
| 230 |
{ |
| 231 |
int32 i; |
| 232 |
Classification cl; |
| 233 |
init_classification(&cl); |
| 234 |
|
| 235 |
for (i = 0; i < n; i++) if (b[i]) classify(&cl, b[i], dpi, options, 1); |
| 236 |
|
| 237 |
return get_tags_from_classification(b, r, n, &cl); |
| 238 |
} |
| 239 |
|
| 240 |
|
| 241 |
static void get_cheap_center(mdjvu_bitmap_t bitmap, int32 *cx, int32 *cy) |
| 242 |
{ |
| 243 |
*cx = mdjvu_bitmap_get_width(bitmap) / 2; |
| 244 |
*cy = mdjvu_bitmap_get_height(bitmap) / 2; |
| 245 |
} |
| 246 |
|
| 247 |
|
| 248 |
#ifndef NO_MINIDJVU |
| 249 |
|
| 250 |
MDJVU_IMPLEMENT int32 mdjvu_classify_bitmaps |
| 251 |
(mdjvu_image_t image, int32 *result, mdjvu_matcher_options_t options, |
| 252 |
int centers_needed) |
| 253 |
{ |
| 254 |
int32 i, n = mdjvu_image_get_bitmap_count(image); |
| 255 |
int32 dpi = mdjvu_image_get_resolution(image); |
| 256 |
mdjvu_pattern_t *patterns = MALLOCV(mdjvu_pattern_t, n); |
| 257 |
int32 max_tag; |
| 258 |
|
| 259 |
for (i = 0; i < n; i++) |
| 260 |
{ |
| 261 |
mdjvu_bitmap_t bitmap = mdjvu_image_get_bitmap(image, i); |
| 262 |
if (mdjvu_image_get_not_a_letter_flag(image, bitmap)) |
| 263 |
patterns[i] = NULL; |
| 264 |
else |
| 265 |
patterns[i] = mdjvu_pattern_create(options, bitmap); |
| 266 |
} |
| 267 |
|
| 268 |
max_tag = mdjvu_classify_patterns(patterns, result, n, dpi, options); |
| 269 |
|
| 270 |
if (centers_needed) |
| 271 |
{ |
| 272 |
mdjvu_image_enable_centers(image); |
| 273 |
for (i = 0; i < n; i++) |
| 274 |
{ |
| 275 |
int32 cx, cy; |
| 276 |
mdjvu_bitmap_t bitmap = mdjvu_image_get_bitmap(image, i); |
| 277 |
if (patterns[i]) |
| 278 |
mdjvu_pattern_get_center(patterns[i], &cx, &cy); |
| 279 |
else |
| 280 |
get_cheap_center(bitmap, &cx, &cy); |
| 281 |
mdjvu_image_set_center(image, bitmap, cx, cy); |
| 282 |
} |
| 283 |
} |
| 284 |
|
| 285 |
for (i = 0; i < n; i++) |
| 286 |
if (patterns[i]) mdjvu_pattern_destroy(patterns[i]); |
| 287 |
FREEV(patterns); |
| 288 |
|
| 289 |
return max_tag; |
| 290 |
} |
| 291 |
|
| 292 |
|
| 293 |
/* ____________________________ multipage stuff ________________________ */ |
| 294 |
|
| 295 |
/* FIXME: wrong dpi handling */ |
| 296 |
MDJVU_IMPLEMENT int32 mdjvu_multipage_classify_patterns |
| 297 |
(int32 npages, int32 total_patterns_count, int32 *npatterns, |
| 298 |
mdjvu_pattern_t **patterns, int32 *result, |
| 299 |
int32 *dpi, mdjvu_matcher_options_t options, |
| 300 |
void (*report)(void *, int), void *param) |
| 301 |
{ |
| 302 |
/* a kluge for NULL patterns */ |
| 303 |
/* FIXME: do it decently */ |
| 304 |
mdjvu_pattern_t *all_patterns = MDJVU_MALLOCV(mdjvu_pattern_t, total_patterns_count); |
| 305 |
int32 patterns_gathered; |
| 306 |
int32 page; |
| 307 |
int32 max_tag; |
| 308 |
|
| 309 |
Classification cl; |
| 310 |
init_classification(&cl); |
| 311 |
|
| 312 |
patterns_gathered = 0; |
| 313 |
for (page = 0; page < npages; page++) |
| 314 |
{ |
| 315 |
int32 n = npatterns[page]; |
| 316 |
int32 d = dpi[page]; |
| 317 |
mdjvu_pattern_t *p = patterns[page]; |
| 318 |
|
| 319 |
int32 i; |
| 320 |
for (i = 0; i < n; i++) |
| 321 |
{ |
| 322 |
all_patterns[patterns_gathered++] = p[i]; |
| 323 |
if (p[i]) classify(&cl, p[i], d, options, page); |
| 324 |
} |
| 325 |
report(param, page); |
| 326 |
} |
| 327 |
|
| 328 |
max_tag = get_tags_from_classification |
| 329 |
(all_patterns, result, total_patterns_count, &cl); |
| 330 |
|
| 331 |
MDJVU_FREEV(all_patterns); |
| 332 |
return max_tag; |
| 333 |
} |
| 334 |
|
| 335 |
|
| 336 |
MDJVU_IMPLEMENT int32 mdjvu_multipage_classify_bitmaps |
| 337 |
(int32 npages, int32 total_patterns_count, mdjvu_image_t *pages, |
| 338 |
int32 *result, mdjvu_matcher_options_t options, |
| 339 |
void (*report)(void *, int), void *param, int centers_needed) |
| 340 |
{ |
| 341 |
int32 max_tag, k, page; |
| 342 |
int32 *npatterns = (int32 *) malloc(npages * sizeof(int32)); |
| 343 |
int32 *dpi = (int32 *) malloc(npages * sizeof(int32)); |
| 344 |
mdjvu_pattern_t *patterns = (mdjvu_pattern_t *) |
| 345 |
malloc(total_patterns_count * sizeof(mdjvu_pattern_t)); |
| 346 |
mdjvu_pattern_t **pointers = (mdjvu_pattern_t **) |
| 347 |
malloc(npages * sizeof(mdjvu_pattern_t *)); |
| 348 |
|
| 349 |
int32 patterns_created = 0; |
| 350 |
for (page = 0; page < npages; page++) |
| 351 |
{ |
| 352 |
mdjvu_image_t current_image = pages[page]; |
| 353 |
int32 c = npatterns[page] = mdjvu_image_get_bitmap_count(current_image); |
| 354 |
int32 i; |
| 355 |
dpi[page] = mdjvu_image_get_resolution(current_image); |
| 356 |
|
| 357 |
pointers[page] = patterns + patterns_created; |
| 358 |
for (i = 0; i < c; i++) |
| 359 |
{ |
| 360 |
if (mdjvu_image_get_not_a_letter_flag(current_image, mdjvu_image_get_bitmap(current_image, i))) |
| 361 |
patterns[patterns_created++] = NULL; |
| 362 |
else |
| 363 |
{ |
| 364 |
patterns[patterns_created++] = mdjvu_pattern_create( |
| 365 |
options, |
| 366 |
mdjvu_image_get_bitmap(current_image, i) |
| 367 |
); |
| 368 |
} |
| 369 |
} |
| 370 |
} |
| 371 |
|
| 372 |
max_tag = mdjvu_multipage_classify_patterns |
| 373 |
(npages, total_patterns_count, npatterns, |
| 374 |
pointers, result, dpi, options, report, param); |
| 375 |
|
| 376 |
if (centers_needed) |
| 377 |
{ |
| 378 |
int32 patterns_processed = 0; |
| 379 |
|
| 380 |
for (page = 0; page < npages; page++) |
| 381 |
{ |
| 382 |
mdjvu_image_t current_image = pages[page]; |
| 383 |
int32 n = mdjvu_image_get_bitmap_count(current_image); |
| 384 |
int32 i; |
| 385 |
mdjvu_image_enable_centers(current_image); |
| 386 |
for (i = 0; i < n; i++) |
| 387 |
{ |
| 388 |
int32 cx, cy; |
| 389 |
mdjvu_bitmap_t bitmap = mdjvu_image_get_bitmap(current_image, i); |
| 390 |
if (patterns[patterns_processed]) |
| 391 |
mdjvu_pattern_get_center(patterns[patterns_processed], &cx, &cy); |
| 392 |
else |
| 393 |
get_cheap_center(bitmap, &cx, &cy); |
| 394 |
patterns_processed++; |
| 395 |
mdjvu_image_set_center(current_image, bitmap, cx, cy); |
| 396 |
} |
| 397 |
} |
| 398 |
} |
| 399 |
|
| 400 |
for (k = 0; k < total_patterns_count; k++) |
| 401 |
{ |
| 402 |
if (patterns[k]) |
| 403 |
mdjvu_pattern_destroy(patterns[k]); |
| 404 |
} |
| 405 |
free(patterns); |
| 406 |
free(pointers); |
| 407 |
free(npatterns); |
| 408 |
free(dpi); |
| 409 |
|
| 410 |
return max_tag; |
| 411 |
} |
| 412 |
|
| 413 |
|
| 414 |
MDJVU_IMPLEMENT void mdjvu_multipage_get_dictionary_flags |
| 415 |
(int32 n, |
| 416 |
int32 *npatterns, |
| 417 |
int32 max_tag, |
| 418 |
int32 *tags, |
| 419 |
unsigned char *dictionary_flags) |
| 420 |
{ |
| 421 |
int32 page_number; |
| 422 |
int32 *first_page_met = (int32 *) malloc((max_tag + 1) * sizeof(int32)); |
| 423 |
int32 i, total_bitmaps_passed = 0; |
| 424 |
memset(dictionary_flags, 0, max_tag + 1); |
| 425 |
for (i = 0; i <= max_tag; i++) first_page_met[i] = -1; |
| 426 |
|
| 427 |
for (page_number = 0; page_number < n; page_number++) |
| 428 |
{ |
| 429 |
int32 bitmap_count = npatterns[page_number]; |
| 430 |
|
| 431 |
for (i = 0; i < bitmap_count; i++) |
| 432 |
{ |
| 433 |
int32 tag = tags[total_bitmaps_passed++]; |
| 434 |
if (!tag) continue; /* skip non-substitutable bitmaps */ |
| 435 |
|
| 436 |
if (first_page_met[tag] == -1) |
| 437 |
{ |
| 438 |
/* never met this tag before */ |
| 439 |
first_page_met[tag] = page_number; |
| 440 |
} |
| 441 |
else if (first_page_met[tag] != page_number) |
| 442 |
{ |
| 443 |
/* met this tag on another page */ |
| 444 |
dictionary_flags[tag] = 1; |
| 445 |
} |
| 446 |
} |
| 447 |
} |
| 448 |
|
| 449 |
free(first_page_met); |
| 450 |
} |
| 451 |
|
| 452 |
|
| 453 |
#endif /* NO_MINIDJVU */ |