/* minidjvu - library for handling bilevel images with DjVuBitonal support * * frames.c - extracting frameworks and calculating "importance rating" * * 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. * +------------------------------------------------------------------ */ /* Frameworks are funny things... * The algorithm is to be commented yet. * Here's a picture illustrating what is a frame * (view with monospace font): * * Original letter: Its framework: * .....@@@@@@@@........ ..................... ...@@@@@@@@@@@@...... ......@@@@@.......... ..@@@@@@@@@@@@@@..... .....@@...@@@........ ..@@@@@...@@@@@@@.... ....@@......@@....... ..@@@@.....@@@@@@.... ....@........@....... .@@@@@.....@@@@@@.... ....@........@....... .@@@@@.....@@@@@@.... ....@........@....... ..@@@@.....@@@@@@.... ....@........@....... ..........@@@@@@@.... .............@....... .......@@@@@@@@@@.... .............@....... .....@@@@@@@@@@@@.... ........@@@@@@....... ...@@@@@@@@@@@@@@.... ......@@@....@....... ..@@@@@@@..@@@@@@.... .....@@......@....... .@@@@@@....@@@@@@.... ...@@@.......@....... .@@@@@.....@@@@@@.... ...@.........@....... @@@@@......@@@@@@.... ..@@.........@....... @@@@@......@@@@@@.... ..@..........@....... @@@@@.....@@@@@@@.... ..@..........@....... @@@@@@....@@@@@@@.@@@ ..@@.........@....... .@@@@@@@@@@@@@@@@@@@@ ...@@.....@@@@@...... .@@@@@@@@@@@@@@@@@@@@ ....@@..@@@...@@@@@.. ..@@@@@@@@@.@@@@@@@@. .....@@@@............ ....@@@@@....@@@@@... ..................... * A letter is converted into grayshades, * and a frame is the set of its purely black pixels after the transformation. * In the grayshade version of a letter, * all pixels that were white remain absolutely white, * the frame is black and the blackness falls down from it to the border. */ /* Offtopic: I wonder if this thing could help OCRing because frameworks * perfectly retain readability while becoming essentially 1-dimensional. */ #include "mdjvucfg.h" #include "minidjvu.h" #include #include #include #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 /* This determines the gray level of the border (ratio of black). * Setting it to 1 will effectively eliminate grayshading. */ #define BORDER_FALLOFF .7 /* this is the main constant in all the matcher... */ typedef unsigned char byte; static int donut_connectivity_test(byte *upper, byte *row, byte *lower)/*{{{*/ { /*(on the pictures below 0 is white, 1 is black or gray) * * 01. * 1 . -> 1 * ... * * .0. * 1 1 -> 1 * .0. * * all others -> 0 */ int sum, l, u, d, r; sum = (u = *upper ? 1 : 0) + (d = *lower ? 1 : 0) + (l = row[-1] ? 1 : 0) + (r = row[1] ? 1 : 0); switch(sum) { case 3:/*{{{*/ { int x = 6 - (u + (l << 1) + d + (d << 1)); switch(x) { case 0: /* l */ return upper[-1] && lower[-1] ? 0 : 1; case 1: /* d */ return lower[-1] && lower[1] ? 0 : 1; case 2: /* r */ return upper[1] && lower[1] ? 0 : 1; case 3: /* u */ return upper[-1] && upper[1] ? 0 : 1; default: assert(0); return 0; } } break;/*}}}*/ case 2:/*{{{*/ { int s = l + r; if (s & 1) { /* A1. * 1 0 - should be !A (2x2 square extermination) * .0. */ if (l) { if (u) return upper[-1] ? 0 : 1; else return lower[-1] ? 0 : 1; } else /* r */ { if (u) return upper[1] ? 0 : 1; else return lower[1] ? 0 : 1; } } else { /* .0. * 1 1 - surely should be 1 to preserve connection * .0. */ return 1; } } break;/*}}}*/ case 0: case 4: return 1; case 1: return 0; default: assert(0); return 0; } assert(0); return 0; }/*}}}*/ static byte donut_transform_pixel(byte *upper, byte *row, byte *lower)/*{{{*/ { /* (center pixel should be gray in order for this to work) * (on the pictures below 0 is white, 1 is black or gray) * * 01. * 1 . -> center will become 1 * ... * * .0. * 1 1 -> center will become 1 * .0. * * 00. * 1 0 -> center will become 1 * .0. * * 1.. * 1 0 -> center will become 0 * 1.. * * 11. * 1 0 -> center will become 0 * .0. * * .A. * A A -> center will become 1 * .A. */ int sum, l, u, d, r; if (!*row) return 0; sum = (u = *upper ? 1 : 0) + (d = *lower ? 1 : 0) + (l = row[-1] ? 1 : 0) + (r = row[1] ? 1 : 0); switch(sum) { case 1: case 3:/*{{{*/ { int x = u + (l << 1) + d + (d << 1); if (sum == 3) x = (6 - x) ^ 2; switch(x) { case 0: /* r */ return upper[1] && lower[1] ? 0 : 1; case 1: /* u */ return upper[-1] && upper[1] ? 0 : 1; case 2: /* l */ return upper[-1] && lower[-1] ? 0 : 1; case 3: /* d */ return lower[-1] && lower[1] ? 0 : 1; default: assert(0); return 0; } } break;/*}}}*/ case 2:/*{{{*/ { int s = l + r; if (s & 1) { /* A1. * 1 0 - should be !A (2x2 square extermination) * .0. */ if (l) { if (u) return upper[-1] ? 0 : 1; else return lower[-1] ? 0 : 1; } else /* r */ { if (u) return upper[1] ? 0 : 1; else return lower[1] ? 0 : 1; } } else { /* .0. * 1 1 - surely should be 1 to preserve connection * .0. */ return 1; } } break;/*}}}*/ case 0: case 4: return 1; /* lone pixels are NOT omitted */ default: assert(0); return 0; } assert(0); return 0; }/*}}}*/ /* `pixels' should have a margin of 1 pixel at each side * returns true if the image was changed */ static int flay(byte **pixels, int w, int h, int rank, int **ranks) { int i, j, result = 0; byte *buf = MALLOCV(byte, w * h); assert(pixels); assert(w); assert(h); for (i = 0; i < h; i++) for (j = 0; j < w; j++) { buf[w * i + j] = donut_transform_pixel(pixels[i-1] + j, pixels[i] + j, pixels[i+1] + j); } for (i = 0; i < h; i++) { byte *up = pixels[i-1], *row = pixels[i], *dn = pixels[i+1]; byte *buf_row = buf + w * i; int *rank_row = NULL; if (ranks) rank_row = ranks[i]; for (j = 0; j < w; j++) { if (row[j] && !buf_row[j]) { if (!donut_connectivity_test(up + j, row + j, dn + j)) { row[j] = buf_row[j]; if (rank) rank_row[j] = rank; result = 1; } } else row[j] = buf_row[j]; } } FREEV(buf); return result; } /* TODO: use less temporary buffers and silly copyings */ MDJVU_IMPLEMENT void mdjvu_soften_pattern(byte **result, byte **pixels, int32 w, int32 h)/*{{{*/ { byte *r = MALLOCV(byte, (w + 2) * (h + 2)); byte **pointers = MALLOCV(byte *, h + 2); int *ranks_buf = MALLOCV(int, w * h); int **ranks = MALLOCV(int *, h); int i, j, passes = 1; double level = 1, falloff; byte *colors; memset(r, 0, (w + 2) * (h + 2)); memset(ranks_buf, 0, w * h * sizeof(int)); for (i = 0; i < h + 2; i++) pointers[i] = r + (w + 2) * i + 1; for (i = 0; i < h; i++) memcpy(pointers[i+1], pixels[i], w); for (i = 0; i < h; i++) ranks[i] = ranks_buf + w * i; while(flay(pointers + 1, w, h, passes, ranks)) passes++; colors = MALLOCV(byte, passes + 1); falloff = pow(BORDER_FALLOFF, 1./passes); for (i = 0; i < passes; i++) { colors[i] = (byte) (level * 255); level *= falloff; } /* TODO: test the next line */ /* colors[passes - 1] = 50; pay less attention to border pixels */ colors[passes] = 0; pointers++; for (i = 0; i < h; i++) { for (j = 0; j < w; j++) { if (pointers[i][j]) { result[i][j] = 255; } else { result[i][j] = colors[passes - ranks[i][j]]; } } } pointers--; FREEV(colors); FREEV(ranks); FREEV(ranks_buf); FREEV(r); FREEV(pointers); }/*}}}*/