Debian Codegraph @

src/matcher/frames.c

raw
1 /*
2 * frames.c - extracting frameworks and calculating "importance rating"
3 */
4
5 /* Frameworks are funny things...
6 * The algorithm is to be commented yet.
7 * Here's a picture illustrating what is a frame
8 * (view with monospace font):
9 *
10 * Original letter: Its framework:
11 *
12 .....@@@@@@@@........ .....................
13 ...@@@@@@@@@@@@...... ......@@@@@..........
14 ..@@@@@@@@@@@@@@..... .....@@...@@@........
15 ..@@@@@...@@@@@@@.... ....@@......@@.......
16 ..@@@@.....@@@@@@.... ....@........@.......
17 .@@@@@.....@@@@@@.... ....@........@.......
18 .@@@@@.....@@@@@@.... ....@........@.......
19 ..@@@@.....@@@@@@.... ....@........@.......
20 ..........@@@@@@@.... .............@.......
21 .......@@@@@@@@@@.... .............@.......
22 .....@@@@@@@@@@@@.... ........@@@@@@.......
23 ...@@@@@@@@@@@@@@.... ......@@@....@.......
24 ..@@@@@@@..@@@@@@.... .....@@......@.......
25 .@@@@@@....@@@@@@.... ...@@@.......@.......
26 .@@@@@.....@@@@@@.... ...@.........@.......
27 @@@@@......@@@@@@.... ..@@.........@.......
28 @@@@@......@@@@@@.... ..@..........@.......
29 @@@@@.....@@@@@@@.... ..@..........@.......
30 @@@@@@....@@@@@@@.@@@ ..@@.........@.......
31 .@@@@@@@@@@@@@@@@@@@@ ...@@.....@@@@@......
32 .@@@@@@@@@@@@@@@@@@@@ ....@@..@@@...@@@@@..
33 ..@@@@@@@@@.@@@@@@@@. .....@@@@............
34 ....@@@@@....@@@@@... .....................
35
36 * A letter is converted into grayshades,
37 * and a frame is the set of its purely black pixels after the transformation.
38 * In the grayshade version of a letter,
39 * all pixels that were white remain absolutely white,
40 * the frame is black and the blackness falls down from it to the border.
41 */
42
43 /* Offtopic: I wonder if this thing could help OCRing because frameworks
44 * perfectly retain readability while becoming essentially 1-dimensional.
45 */
46
47 #include "../base/mdjvucfg.h"
48 #include <minidjvu/minidjvu.h>
49 #include <stdlib.h>
50 #include <assert.h>
51 #include <string.h>
52 #include <math.h>
53
54 /* Stuff for not using malloc in C++
55 * (made by Leon Bottou; has no use in minidjvu,
56 * but left here for potential DjVuLibre compatibility)
57 */
58 #ifdef __cplusplus
59 # define MALLOC(Type) new Type
60 # define FREE(p) delete p
61 # define MALLOCV(Type,n) new Type[n]
62 # define FREEV(p) delete [] p
63 #else
64 # define MALLOC(Type) ((Type*)malloc(sizeof(Type)))
65 # define FREE(p) do{if(p)free(p);}while(0)
66 # define MALLOCV(Type,n) ((Type*)malloc(sizeof(Type)*(n)))
67 # define FREEV(p) do{if(p)free(p);}while(0)
68 #endif
69
70
71 /* This determines the gray level of the border (ratio of black).
72 * Setting it to 1 will effectively eliminate grayshading.
73 */
74 #define BORDER_FALLOFF .7 /* this is the main constant in all the matcher... */
75
76 typedef unsigned char byte;
77
78 static int donut_connectivity_test(byte *upper, byte *row, byte *lower)/*{{{*/
79 {
80 /*(on the pictures below 0 is white, 1 is black or gray)
81 *
82 * 01.
83 * 1 . -> 1
84 * ...
85 *
86 * .0.
87 * 1 1 -> 1
88 * .0.
89 *
90 * all others -> 0
91 */
92
93 int sum, l, u, d, r;
94
95 sum = (u = *upper ? 1 : 0) + (d = *lower ? 1 : 0) +
96 (l = row[-1] ? 1 : 0) + (r = row[1] ? 1 : 0);
97
98 switch(sum)
99 {
100 case 3:/*{{{*/
101 {
102 int x = 6 - (u + (l << 1) + d + (d << 1));
103 switch(x)
104 {
105 case 0: /* l */
106 return upper[-1] && lower[-1] ? 0 : 1;
107 case 1: /* d */
108 return lower[-1] && lower[1] ? 0 : 1;
109 case 2: /* r */
110 return upper[1] && lower[1] ? 0 : 1;
111 case 3: /* u */
112 return upper[-1] && upper[1] ? 0 : 1;
113 default: assert(0); return 0;
114 }
115 }
116 break;/*}}}*/
117 case 2:/*{{{*/
118 {
119 int s = l + r;
120 if (s & 1)
121 {
122 /* A1.
123 * 1 0 - should be !A (2x2 square extermination)
124 * .0.
125 */
126 if (l)
127 {
128 if (u)
129 return upper[-1] ? 0 : 1;
130 else
131 return lower[-1] ? 0 : 1;
132 }
133 else /* r */
134 {
135 if (u)
136 return upper[1] ? 0 : 1;
137 else
138 return lower[1] ? 0 : 1;
139 }
140 }
141 else
142 {
143 /* .0.
144 * 1 1 - surely should be 1 to preserve connection
145 * .0.
146 */
147 return 1;
148 }
149 }
150 break;/*}}}*/
151 case 0: case 4:
152 return 1;
153 case 1:
154 return 0;
155 default: assert(0); return 0;
156 }
157 }/*}}}*/
158 static byte donut_transform_pixel(byte *upper, byte *row, byte *lower)/*{{{*/
159 {
160 /* (center pixel should be gray in order for this to work)
161 * (on the pictures below 0 is white, 1 is black or gray)
162 *
163 * 01.
164 * 1 . -> center will become 1
165 * ...
166 *
167 * .0.
168 * 1 1 -> center will become 1
169 * .0.
170 *
171 * 00.
172 * 1 0 -> center will become 1
173 * .0.
174 *
175 * 1..
176 * 1 0 -> center will become 0
177 * 1..
178 *
179 * 11.
180 * 1 0 -> center will become 0
181 * .0.
182 *
183 * .A.
184 * A A -> center will become 1
185 * .A.
186 */
187
188 int sum, l, u, d, r;
189 if (!*row) return 0;
190
191 sum = (u = *upper ? 1 : 0) + (d = *lower ? 1 : 0) +
192 (l = row[-1] ? 1 : 0) + (r = row[1] ? 1 : 0);
193
194 switch(sum)
195 {
196 case 1: case 3:/*{{{*/
197 {
198 int x = u + (l << 1) + d + (d << 1);
199 if (sum == 3) x = (6 - x) ^ 2;
200 switch(x)
201 {
202 case 0: /* r */
203 return upper[1] && lower[1] ? 0 : 1;
204 case 1: /* u */
205 return upper[-1] && upper[1] ? 0 : 1;
206 case 2: /* l */
207 return upper[-1] && lower[-1] ? 0 : 1;
208 case 3: /* d */
209 return lower[-1] && lower[1] ? 0 : 1;
210 default: assert(0); return 0;
211 }
212 }
213 break;/*}}}*/
214 case 2:/*{{{*/
215 {
216 int s = l + r;
217 if (s & 1)
218 {
219 /* A1.
220 * 1 0 - should be !A (2x2 square extermination)
221 * .0.
222 */
223 if (l)
224 {
225 if (u)
226 return upper[-1] ? 0 : 1;
227 else
228 return lower[-1] ? 0 : 1;
229 }
230 else /* r */
231 {
232 if (u)
233 return upper[1] ? 0 : 1;
234 else
235 return lower[1] ? 0 : 1;
236 }
237 }
238 else
239 {
240 /* .0.
241 * 1 1 - surely should be 1 to preserve connection
242 * .0.
243 */
244 return 1;
245 }
246 }
247 break;/*}}}*/
248 case 0: case 4:
249 return 1; /* lone pixels are NOT omitted */
250 default: assert(0); return 0;
251 }
252 }/*}}}*/
253
254 /* `pixels' should have a margin of 1 pixel at each side
255 * returns true if the image was changed
256 */
257 static int flay(byte **pixels, int w, int h, int rank, int **ranks)
258 {
259 int i, j, result = 0;
260
261 byte *buf = MALLOCV(byte, w * h);
262
263 assert(pixels);
264 assert(w);
265 assert(h);
266
267 for (i = 0; i < h; i++) for (j = 0; j < w; j++)
268 {
269 buf[w * i + j] =
270 donut_transform_pixel(pixels[i-1] + j, pixels[i] + j, pixels[i+1] + j);
271 }
272
273 for (i = 0; i < h; i++)
274 {
275 byte *up = pixels[i-1], *row = pixels[i], *dn = pixels[i+1];
276 byte *buf_row = buf + w * i;
277 int *rank_row = NULL;
278 if (ranks) rank_row = ranks[i];
279 for (j = 0; j < w; j++)
280 {
281 if (row[j] && !buf_row[j])
282 {
283 if (!donut_connectivity_test(up + j, row + j, dn + j))
284 {
285 row[j] = buf_row[j];
286 if (rank) rank_row[j] = rank;
287 result = 1;
288 }
289 }
290 else
291 row[j] = buf_row[j];
292 }
293 }
294
295 FREEV(buf);
296 return result;
297 }
298
299 /* TODO: use less temporary buffers and silly copyings */
300 MDJVU_IMPLEMENT void mdjvu_soften_pattern(byte **result, byte **pixels, int32 w, int32 h)/*{{{*/
301 {
302 byte *r = MALLOCV(byte, (w + 2) * (h + 2));
303 byte **pointers = MALLOCV(byte *, h + 2);
304 int *ranks_buf = MALLOCV(int, w * h);
305 int **ranks = MALLOCV(int *, h);
306
307 int i, j, passes = 1;
308 double level = 1, falloff;
309 byte *colors;
310
311 memset(r, 0, (w + 2) * (h + 2));
312 memset(ranks_buf, 0, w * h * sizeof(int));
313
314 for (i = 0; i < h + 2; i++)
315 pointers[i] = r + (w + 2) * i + 1;
316
317 for (i = 0; i < h; i++)
318 memcpy(pointers[i+1], pixels[i], w);
319
320 for (i = 0; i < h; i++)
321 ranks[i] = ranks_buf + w * i;
322
323 while(flay(pointers + 1, w, h, passes, ranks)) passes++;
324
325 colors = MALLOCV(byte, passes + 1);
326
327 falloff = pow(BORDER_FALLOFF, 1./passes);
328
329 for (i = 0; i < passes; i++)
330 {
331 colors[i] = (byte) (level * 255);
332 level *= falloff;
333 }
334 /* TODO: test the next line */
335 /* colors[passes - 1] = 50; pay less attention to border pixels */
336 colors[passes] = 0;
337
338 pointers++;
339 for (i = 0; i < h; i++)
340 {
341 for (j = 0; j < w; j++)
342 {
343 if (pointers[i][j])
344 {
345 result[i][j] = 255;
346 }
347 else
348 {
349 result[i][j] = colors[passes - ranks[i][j]];
350 }
351 }
352 }
353 pointers--;
354
355 FREEV(colors);
356 FREEV(ranks);
357 FREEV(ranks_buf);
358 FREEV(r);
359 FREEV(pointers);
360 }/*}}}*/