| 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 |
} |