Debian Codegraph @

src/alg/split.c

raw
1 /*
2 * split.c - splitting bitmaps to letters
3 */
4
5 #include "../base/mdjvucfg.h"
6 #include <minidjvu/minidjvu.h>
7 #include <assert.h>
8 #include <stdlib.h>
9 #include <string.h>
10
11 /* _______________________ managing splitter options ___________________ */
12
13 mdjvu_split_options_t mdjvu_split_options_create(void)
14 {
15 int32 *p = (int32 *) malloc(sizeof(int32));
16 mdjvu_init();
17 *p = 0;
18 return (mdjvu_split_options_t) p;
19 }
20
21 void mdjvu_split_options_set_maximum_shape_size(mdjvu_split_options_t opt, int32 size)
22 {
23 assert(size > 0);
24 * (int32 *) opt = size;
25 }
26
27 void mdjvu_split_options_destroy(mdjvu_split_options_t opt)
28 {
29 free(opt);
30 }
31
32 /* _________________________ interpreting runs _________________________ */
33
34 /* Runs are stored in a "map".
35 * A map entry may be 0 (same-as-prev), BLACK_RUN(1) and WHITE_RUN(2).
36 * Each run is started by BLACK_RUN or WHITE_RUN and continues with zeros.
37 * First run is white.
38 *
39 * Here's an example:
40 *
41 * map: 001002001000210
42 * interpreted line: 001110001111011
43 */
44 #define BLACK_RUN 1
45 #define WHITE_RUN 2
46
47 /* This function does three things simultaneously:
48 * 1) renders `map' into `result_line' and applies AND with line
49 * 2) deletes black pixels in `line'
50 * 3) clears `map' including the last (max_x + 1) column
51 *
52 * Indices in `map' are min_x..max_x.
53 * Indices in `line' are min_x..max_x.
54 * Indices in `result_line' are 0..max_x-min_x.
55 *
56 */
57 static void interpret_runs_in_a_line(int32 min_x, int32 max_x,
58 unsigned char *map,
59 unsigned char *result_line,
60 unsigned char *line)
61 {
62 int32 i = min_x;
63 memset(result_line, 0, max_x - min_x + 1);
64 map[max_x + 1] = 0;
65 while (1)
66 {
67 /* white run */
68 while (map[i] != BLACK_RUN)
69 {
70 if (++i > max_x) return;
71 }
72
73 map[i] = 0;
74
75 /* black run */
76 while (map[i] != WHITE_RUN)
77 {
78 result_line[i - min_x] = line[i]; /* copy instead of paint */
79 line[i] = 0;
80 if (++i > max_x) return;
81 }
82
83 map[i] = 0;
84 }
85 }
86
87 /* This function does the same as interpret_runs_in_a_line(),
88 * but on a rectangle.
89 * Returns the rendered result.
90 * Also clears it in pixels[][].
91 * `map' is cleared.
92 */
93 static mdjvu_bitmap_t interpret_runs(int32 min_x, int32 max_x,
94 int32 min_y, int32 max_y,
95 unsigned char **map,
96 unsigned char **pixels)
97 {
98 int32 w = max_x - min_x + 1;
99 int32 h = max_y - min_y + 1;
100 unsigned char *line_buf = (unsigned char *) malloc(w);
101 mdjvu_bitmap_t bmp = mdjvu_bitmap_create(w, h);
102 int32 y;
103 for (y = min_y; y <= max_y; y++)
104 {
105 interpret_runs_in_a_line(min_x, max_x, map[y], line_buf, pixels[y]);
106 mdjvu_bitmap_pack_row(bmp, line_buf, y - min_y);
107 }
108 free(line_buf);
109 return bmp;
110 }
111
112 /* ________________________ walking along contours _____________________ */
113
114 /* (start_x, start_y) should be the leftmost of the topmost black pixels.
115 * Walking is counterclockwise.
116 * map must be cleared.
117 */
118
119 static void walk_around_a_black_contour(unsigned char **pixels,
120 unsigned char **map,
121 int32 start_x, int32 start_y,
122 int32 *pmin_x, int32 *pmax_x,
123 int32 *pmin_y, int32 *pmax_y)
124 {
125 int32 x = start_x, y = start_y; /* current black pixel */
126 int32 dx = 0, dy = 1; /* vector along the contour*/
127 /* it's always true that abs(dx) == 1 && dy == 0
128 * ||
129 * abs(dy) == 1 && dx == 0
130 */
131
132 /* Bounding box. start_y will always be minimal y. */
133 int32 min_x = start_x;
134 int32 max_x = start_x;
135 int32 max_y = start_y;
136
137 /* Starting picture:
138 *
139 * | w | w |
140 * ----+---|
141 * | w | b | <- start_y
142 * ^
143 * start_x
144 *
145 * and we're heading down
146 */
147
148 /* Generic picture (===> denotes contour fragment along (dx,dy)):
149 *
150 * (1) | b | ? | (3)
151 * ====>----
152 * (2) | w | ? | (4)
153 *
154 * ===> vector is (dx,dy)
155 * up vector (that is, (dx,dy) rotated counterclockwise) is (dy, -dx).
156 * down vector (that is, (dx,dy) rotated clockwise) is (-dy, dx).
157 * (the coordinate system is left)
158 */
159
160 /* MAIN IMAGE WALKING LOOP */
161 while (x != start_x || y != start_y || dx != -1)
162 {
163 assert(pixels[y][x] /* is black */);
164
165 /* see if this pixel enlarges bbox */
166 if (x < min_x) min_x = x; else if (x > max_x) max_x = x;
167 if (y > max_y) max_y = y;
168
169 /* fill contour map if needed */
170 if (dx == 0)
171 {
172 if (dy > 0)
173 map[y][x] = BLACK_RUN;
174 else
175 map[y][x + 1] = WHITE_RUN; /* map has the right margin */
176 }
177
178 /* proceed with contour */
179 if (pixels[y + dy][x + dx]) /* testing (3) */
180 {
181 int32 x4 = x + dx - dy, y4 = y + dy + dx;
182
183 if (pixels[y4][x4]) /* testing (4) */
184 {
185 /* (3) and (4) are black - right turn */
186 /* (-dy,dx) becomes new (dx,dy) (coordinate system is left) */
187 /* pixel (4) becomes (x,y) */
188 int32 old_dx = dx;
189 dx = -dy;
190 dy = old_dx;
191 x = x4; y = y4;
192 }
193 else
194 {
195 /* go straight: pixel (3) becomes (x,y) */
196 x += dx; y += dy;
197 }
198 }
199 else
200 {
201 /* (3) is white - left turn */
202 /* (dy,-dx) becomes new (dx,dy) (coordinate system is left) */
203 int32 old_dx = dx;
204 dx = dy;
205 dy = -old_dx;
206 }
207 }
208 *pmin_x = min_x;
209 *pmax_x = max_x;
210 *pmin_y = start_y;
211 *pmax_y = max_y;
212 }
213
214 /* ____________________________ process row ____________________________ */
215
216 static void add_to_image(mdjvu_image_t image,
217 mdjvu_bitmap_t bitmap,
218 int32 dpi,
219 mdjvu_split_options_t opt,
220 int32 blit_shift_x,
221 int32 blit_shift_y,
222 int big);
223
224
225 /* This function scans the y-th row for contours. */
226 /* Margins (1 pixel) from each side are required. */
227 static void process_row(unsigned char **pixels, unsigned char **map,
228 int32 y, int32 w, int32 h,
229 mdjvu_image_t image, int32 shift_x, int32 shift_y,
230 int32 max_shape_width,
231 int32 blit_shift_x, int32 blit_shift_y,
232 int32 dpi, mdjvu_split_options_t opt,
233 int big)
234 {
235 unsigned char *row = pixels[y];
236 int32 i;
237 for (i = 0; i < w; i++)
238 {
239 if (row[i])
240 {
241 int32 min_x, max_x, min_y, max_y, shape_width;
242
243 /* extract the contour */
244 mdjvu_bitmap_t bitmap;
245 walk_around_a_black_contour(pixels, map, i, y,
246 &min_x, &max_x, &min_y, &max_y);
247 bitmap = interpret_runs(min_x, max_x,
248 min_y, max_y,
249 map, pixels);
250 shape_width = mdjvu_bitmap_get_width(bitmap);
251 assert(shape_width == max_x - min_x + 1);
252 assert(mdjvu_bitmap_get_height(bitmap) == max_y - min_y + 1);
253 if (shape_width <= max_shape_width)
254 {
255 mdjvu_image_add_bitmap(image, bitmap);
256 mdjvu_image_add_blit(image, shift_x + min_x + blit_shift_x,
257 y + shift_y + blit_shift_y, bitmap);
258 mdjvu_image_set_suspiciously_big_flag(image, bitmap, big);
259 }
260 else
261 {
262 /* further split the bitmap */
263 int32 number_of_chunks = (shape_width + max_shape_width - 1)
264 /
265 max_shape_width;
266 int32 j;
267 int32 shape_height = mdjvu_bitmap_get_height(bitmap);
268 for (j = 0; j < number_of_chunks; j++)
269 {
270 int32 chunk_x = shape_width * j / number_of_chunks;
271 mdjvu_bitmap_t chunk = mdjvu_bitmap_crop(bitmap,
272 chunk_x, 0,
273 shape_width * (j+1) / number_of_chunks - chunk_x,
274 shape_height
275 );
276 /* After splitting, some white margins may be left,
277 * or the bitmap may lose connectivity.
278 * Apply the algorithm recursively to the chunk.
279 */
280 add_to_image(image, chunk, dpi, opt,
281 shift_x + chunk_x + min_x + blit_shift_x,
282 y + shift_y + blit_shift_y, /* big: */ 1);
283 mdjvu_bitmap_destroy(chunk);
284 }
285 mdjvu_bitmap_destroy(bitmap);
286 } /* if (shape_width <= max_shape_width) */
287 }
288 }
289 }
290
291 /* _________________________ the main routines _________________________ */
292
293 /* Not much job left to do here, mostly moving a window through the image. */
294
295 static void add_to_image(mdjvu_image_t image,
296 mdjvu_bitmap_t bitmap,
297 int32 dpi,
298 mdjvu_split_options_t opt,
299 int32 blit_shift_x,
300 int32 blit_shift_y,
301 int big)
302 {
303 int32 max_shape_size = opt ? * (int32 *) opt : 0;
304 int32 width = mdjvu_bitmap_get_width(bitmap);
305 int32 height = mdjvu_bitmap_get_height(bitmap);
306 unsigned char **buf, **window_base, **window_buf, **map;
307 int32 window_shift = 0, y = 0, i;
308
309 if (!max_shape_size)
310 max_shape_size = dpi;
311 if (max_shape_size > height)
312 max_shape_size = height;
313
314 /* n-th line will be unpacked into buf[n % max_shape_size] + 1.
315 * ( +1 is to make the left margin)
316 * buf[max_shape_size] will always be blank.
317 *
318 * window_base[window_shift - 1]
319 * points to buf[max_shape_size] + 1 (blank line) - top margin
320 * window_base[window_shift + max_shape_size]
321 * points to buf[max_shape_size] + 1 (blank line) - bottom margin
322 * window_base[window_shift + i]
323 * points to buf[(window_shift + i) % max_shape_size] + 1.
324 */
325
326 /* map has the right margin of 1 */
327 map = mdjvu_create_2d_array(width + 1, max_shape_size);
328
329 /* buf has left, right and bottom margins of 1 */
330 buf = mdjvu_create_2d_array(width + 2, max_shape_size + 1);
331 window_buf = (unsigned char **)
332 malloc(2 * (max_shape_size + 2) * sizeof(unsigned char *));
333 window_base = window_buf + 1;
334
335 /* Unpack initial portion of the bitmap; bind the window to the buffer */
336 for (i = 0; i < max_shape_size; i++)
337 {
338 window_base[i] = window_base[max_shape_size + i] = buf[i] + 1;
339 mdjvu_bitmap_unpack_row(bitmap, buf[i] + 1, i);
340 }
341
342 /* Setup top and bottom white margins */
343 window_base[-1] =
344 window_base[2 * max_shape_size - 1] =
345 buf[max_shape_size] + 1;
346
347 /* The "window moving" loop.
348 * We're moving a (width x max_shape_size) window through the image.
349 */
350 while(1)
351 {
352 /* Extract some shapes from the window
353 * (shapes touching the topmost row will be affected).
354 */
355
356 unsigned char *top_margin_save = /* make the top margin */
357 window_base[window_shift - 1]; /* (save what was there) */
358 unsigned char *bot_margin_save = /* same with the bottom margin */
359 window_base[window_shift + max_shape_size];
360 int32 old_window_shift;
361 window_base[window_shift - 1] = buf[max_shape_size] + 1; /* clear them */
362 window_base[window_shift + max_shape_size] = buf[max_shape_size] + 1;
363
364 process_row(window_base + window_shift, map,
365 /* index of a row to process: */ 0,
366 width, max_shape_size, image, 0, y, max_shape_size,
367 blit_shift_x, blit_shift_y, dpi, opt, big);
368
369 window_base[window_shift - 1] = top_margin_save; /* restore margins */
370 window_base[window_shift + max_shape_size] = bot_margin_save;
371
372 /* Shift the window */
373 y++;
374 old_window_shift = window_shift;
375 window_shift = y % max_shape_size;
376 if (y + max_shape_size > height)
377 break;
378
379 /* Unpack a new row into the bottom window row */
380 mdjvu_bitmap_unpack_row(bitmap, buf[old_window_shift] + 1,
381 y + max_shape_size - 1);
382 }
383
384 /* Process the last window fully */
385 for (i = 0; y + i < height; i++)
386 {
387 process_row(window_base + window_shift, map,
388 /* index of a row to process: */ i,
389 width, max_shape_size, image, 0, y, max_shape_size,
390 blit_shift_x, blit_shift_y, dpi, opt, big);
391 }
392
393 /* Clean up */
394 free(window_buf);
395 mdjvu_destroy_2d_array(map);
396 mdjvu_destroy_2d_array(buf);
397 }
398
399 mdjvu_image_t
400 mdjvu_split(mdjvu_bitmap_t bitmap, int32 dpi, mdjvu_split_options_t opt)
401 {
402 int32 width = mdjvu_bitmap_get_width(bitmap);
403 int32 height = mdjvu_bitmap_get_height(bitmap);
404 mdjvu_image_t result = mdjvu_image_create(width, height);
405 mdjvu_image_enable_suspiciously_big_flags(result);
406 mdjvu_image_set_resolution(result, dpi);
407 add_to_image(result, bitmap, dpi, opt, 0, 0, /* big: */ 0);
408 return result;
409 }