/* minidjvu - library for handling bilevel images with DjVuBitonal support * * classify.c - classifying patterns * * Copyright (C) 2005 Ilya Mezhirov * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * * * minidjvu is derived from DjVuLibre (http://djvu.sourceforge.net) * All over DjVuLibre there is a patent alert from LizardTech * which I guess I should reproduce (don't ask me what does this mean): * * ------------------------------------------------------------------ * | DjVu (r) Reference Library (v. 3.5) * | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved. * | The DjVu Reference Library is protected by U.S. Pat. No. * | 6,058,214 and patents pending. * | * | This software is subject to, and may be distributed under, the * | GNU General Public License, either Version 2 of the license, * | or (at your option) any later version. The license should have * | accompanied the software or you may obtain a copy of the license * | from the Free Software Foundation at http://www.fsf.org . * | * | The computer code originally released by LizardTech under this * | license and unmodified by other parties is deemed "the LIZARDTECH * | ORIGINAL CODE." Subject to any third party intellectual property * | claims, LizardTech grants recipient a worldwide, royalty-free, * | non-exclusive license to make, use, sell, or otherwise dispose of * | the LIZARDTECH ORIGINAL CODE or of programs derived from the * | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU * | General Public License. This grant only confers the right to * | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to * | the extent such infringement is reasonably necessary to enable * | recipient to make, have made, practice, sell, or otherwise dispose * | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to * | any greater extent that may be necessary to utilize further * | modifications or combinations. * | * | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY * | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED * | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF * | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. * +------------------------------------------------------------------ */ #include "mdjvucfg.h" #include "minidjvu.h" #include /* Stuff for not using malloc in C++ * (made by Leon Bottou; has no use in minidjvu, * but left here for potential DjVuLibre compatibility) */ #ifdef __cplusplus # define MALLOC(Type) new Type # define FREE(p) delete p # define MALLOCV(Type,n) new Type[n] # define FREEV(p) delete [] p #else # define MALLOC(Type) ((Type*)malloc(sizeof(Type))) # define FREE(p) do{if(p)free(p);}while(0) # define MALLOCV(Type,n) ((Type*)malloc(sizeof(Type)*(n))) # define FREEV(p) do{if(p)free(p);}while(0) #endif /* Classes are single-linked lists with an additional pointer to the last node. * This is an class item. */ typedef struct ClassNode { mdjvu_pattern_t ptr; struct ClassNode *next; /* NULL if this node is the last one */ struct ClassNode *global_next; /* next among all nodes to classify */ int32 tag; /* filled before the final dumping */ } ClassNode; /* Classes themselves are composed in double-linked list. */ typedef struct Class { ClassNode *first, *last; struct Class *prev_class; struct Class *next_class; } Class; typedef struct Classification { Class *first_class; ClassNode *first_node, *last_node; } Classification; /* Creates an empty class and links it to the list of classes. */ static Class *new_class(Classification *cl) { Class *c = MALLOC(Class); c->first = c->last = NULL; c->prev_class = NULL; c->next_class = cl->first_class; if (cl->first_class) cl->first_class->prev_class = c; cl->first_class = c; return c; } /* Unlinks a class and deletes it. Its nodes are not deleted. */ static void delete_class(Classification *cl, Class *c) { Class *prev = c->prev_class, *next = c->next_class; if (prev) prev->next_class = next; else cl->first_class = next; if (next) next->prev_class = prev; FREE(c); } /* Creates a new node and adds it to the given class. */ static ClassNode *new_node(Classification *cl, Class *c, mdjvu_pattern_t ptr) { ClassNode *n = MALLOC(ClassNode); n->ptr = ptr; n->next = c->first; c->first = n; if (!c->last) c->last = n; n->global_next = NULL; if (cl->last_node) cl->last_node->global_next = n; else cl->first_node = n; cl->last_node = n; return n; } /* Merge two classes and delete one of them. */ static Class *merge(Classification *cl, Class *c1, Class *c2) { if (!c1->first) { delete_class(cl, c1); return c2; } if (c2->first) { c1->last->next = c2->first; c1->last = c2->last; } delete_class(cl, c2); return c1; } /* Puts a tag on each node corresponding to its class. */ static unsigned put_tags(Classification *cl) { int32 tag = 1; Class *c = cl->first_class; while (c) { ClassNode *n = c->first; while (n) { n->tag = tag; n = n->next; } c = c->next_class; tag++; } return tag - 1; } /* Deletes all classes; nodes are untouched. */ static void delete_all_classes(Classification *cl) { Class *c = cl->first_class; while (c) { Class *t = c; c = c->next_class; FREE(t); } } /* Compares p with nodes from c until a meaningful result. */ static int compare_to_class(mdjvu_pattern_t p, Class *c, int32 dpi, mdjvu_matcher_options_t options) { int r = 0; ClassNode *n = c->first; while(n) { r = mdjvu_match_patterns(p, n->ptr, dpi, options); if (r) break; n = n->next; } return r; } static void classify(Classification *cl, mdjvu_pattern_t p, int32 dpi, mdjvu_matcher_options_t options) { Class *class_of_this = NULL; Class *c, *next_c = NULL; for (c = cl->first_class; c; c = next_c) { next_c = c->next_class; /* That's because c may be deleted in merging */ if (class_of_this == c) continue; if (compare_to_class(p, c, dpi, options) != 1) continue; if (class_of_this) class_of_this = merge(cl, class_of_this, c); else class_of_this = c; } if (!class_of_this) class_of_this = new_class(cl); new_node(cl, class_of_this, p); } MDJVU_IMPLEMENT int32 mdjvu_classify_patterns (mdjvu_pattern_t *b, int32 *r, int32 n, int32 dpi, mdjvu_matcher_options_t options) { int32 i, max_tag; ClassNode *node; Classification cl; cl.first_class = NULL; cl.first_node = cl.last_node = NULL; for (i = 0; i < n; i++) if (b[i]) classify(&cl, b[i], dpi, options); max_tag = put_tags(&cl); delete_all_classes(&cl); i = 0; node = cl.first_node; while (node) { ClassNode *t; while (!b[i]) r[i++] = 0; r[i++] = node->tag; t = node; node = node->global_next; FREE(t); } if (i < n) while (i < n) r[i++] = 0; return max_tag; } #ifndef NO_MINIDJVU MDJVU_IMPLEMENT int32 mdjvu_classify_bitmaps_in_image (mdjvu_image_t image, int32 *result, mdjvu_matcher_options_t options) { int32 i, n = mdjvu_image_get_bitmap_count(image); int32 dpi = mdjvu_image_get_resolution(image); mdjvu_pattern_t *patterns = MALLOCV(mdjvu_pattern_t, n); int32 max_tag; for (i = 0; i < n; i++) { mdjvu_bitmap_t bitmap = mdjvu_image_get_bitmap(image, i); if (mdjvu_image_get_no_substitution_flag(image, bitmap)) patterns[i] = NULL; else patterns[i] = mdjvu_pattern_create(bitmap); } max_tag = mdjvu_classify_patterns(patterns, result, n, dpi, options); for (i = 0; i < n; i++) if (patterns[i]) mdjvu_pattern_destroy(patterns[i]); FREEV(patterns); return max_tag; } #endif /* NO_MINIDJVU */