Debian Codegraph @

src/alg/classify.c

raw
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 */