1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16 /*
17 * boxfunc3.c
18 *
19 * Boxa/Boxaa painting into pix
20 * PIX *pixMaskConnComp()
21 * PIX *pixMaskBoxa()
22 * PIX *pixPaintBoxa()
23 * PIX *pixPaintBoxaRandom()
24 * PIX *pixBlendBoxaRandom()
25 * PIX *pixDrawBoxa()
26 * PIX *pixDrawBoxaRandom()
27 * PIX *boxaaDisplay()
28 *
29 * Split mask components into Boxa
30 * BOXA *pixSplitIntoBoxa()
31 * BOXA *pixSplitComponentIntoBoxa()
32 * static l_int32 pixSearchForRectangle()
33 *
34 * See summary in pixPaintBoxa() of various ways to paint and draw
35 * boxes on images.
36 */
37
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include "allheaders.h"
41
42 static l_int32 pixSearchForRectangle(PIX *pixs, BOX *boxs, l_int32 minsum,
43 l_int32 skipdist, l_int32 delta,
44 l_int32 maxbg, l_int32 sideflag,
45 BOXA *boxat, NUMA *nascore);
46
47 #ifndef NO_CONSOLE_IO
48 #define DEBUG_SPLIT 0
49 #endif /* ~NO_CONSOLE_IO */
50
51
52 /*---------------------------------------------------------------------*
53 * Boxa/Boxaa painting into Pix *
54 *---------------------------------------------------------------------*/
55 /*!
56 * pixMaskConnComp()
57 *
58 * Input: pixs (1 bpp)
59 * connectivity (4 or 8)
60 * &boxa (<optional return> bounding boxes of c.c.)
61 * Return: pixd (1 bpp mask over the c.c.), or null on error
62 *
63 * Notes:
64 * (1) This generates a mask image with ON pixels over the
65 * b.b. of the c.c. in pixs. If there are no ON pixels in pixs,
66 * pixd will also have no ON pixels.
67 */
68 PIX *
pixMaskConnComp(PIX * pixs,l_int32 connectivity,BOXA ** pboxa)69 pixMaskConnComp(PIX *pixs,
70 l_int32 connectivity,
71 BOXA **pboxa)
72 {
73 BOXA *boxa;
74 PIX *pixd;
75
76 PROCNAME("pixMaskConnComp");
77
78 if (!pixs || pixGetDepth(pixs) != 1)
79 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
80 if (connectivity != 4 && connectivity != 8)
81 return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
82
83 boxa = pixConnComp(pixs, NULL, connectivity);
84 pixd = pixCreateTemplate(pixs);
85 if (boxaGetCount(boxa) != 0)
86 pixMaskBoxa(pixd, pixd, boxa, L_SET_PIXELS);
87 if (pboxa)
88 *pboxa = boxa;
89 else
90 boxaDestroy(&boxa);
91 return pixd;
92 }
93
94
95 /*!
96 * pixMaskBoxa()
97 *
98 * Input: pixd (<optional> may be null)
99 * pixs (any depth; not cmapped)
100 * boxa (of boxes, to paint)
101 * op (L_SET_PIXELS, L_CLEAR_PIXELS, L_FLIP_PIXELS)
102 * Return: pixd (with masking op over the boxes), or null on error
103 *
104 * Notes:
105 * (1) This can be used with:
106 * pixd = NULL (makes a new pixd)
107 * pixd = pixs (in-place)
108 * (2) If pixd == NULL, this first makes a copy of pixs, and then
109 * bit-twiddles over the boxes. Otherwise, it operates directly
110 * on pixs.
111 * (3) This simple function is typically used with 1 bpp images.
112 * It uses the 1-image rasterop function, rasteropUniLow(),
113 * to set, clear or flip the pixels in pixd.
114 * (4) If you want to generate a 1 bpp mask of ON pixels from the boxes
115 * in a Boxa, in a pix of size (w,h):
116 * pix = pixCreate(w, h, 1);
117 * pixMaskBoxa(pix, pix, boxa, L_SET_PIXELS);
118 */
119 PIX *
pixMaskBoxa(PIX * pixd,PIX * pixs,BOXA * boxa,l_int32 op)120 pixMaskBoxa(PIX *pixd,
121 PIX *pixs,
122 BOXA *boxa,
123 l_int32 op)
124 {
125 l_int32 i, n, x, y, w, h;
126 BOX *box;
127
128 PROCNAME("pixMaskBoxa");
129
130 if (!pixs)
131 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
132 if (pixGetColormap(pixs))
133 return (PIX *)ERROR_PTR("pixs is cmapped", procName, NULL);
134 if (pixd && (pixd != pixs))
135 return (PIX *)ERROR_PTR("if pixd, must be in-place", procName, NULL);
136 if (!boxa)
137 return (PIX *)ERROR_PTR("boxa not defined", procName, NULL);
138 if (op != L_SET_PIXELS && op != L_CLEAR_PIXELS && op != L_FLIP_PIXELS)
139 return (PIX *)ERROR_PTR("invalid op", procName, NULL);
140
141 pixd = pixCopy(pixd, pixs);
142 if ((n = boxaGetCount(boxa)) == 0) {
143 L_WARNING("no boxes to mask", procName);
144 return pixd;
145 }
146
147 for (i = 0; i < n; i++) {
148 box = boxaGetBox(boxa, i, L_CLONE);
149 boxGetGeometry(box, &x, &y, &w, &h);
150 if (op == L_SET_PIXELS)
151 pixRasterop(pixd, x, y, w, h, PIX_SET, NULL, 0, 0);
152 else if (op == L_CLEAR_PIXELS)
153 pixRasterop(pixd, x, y, w, h, PIX_CLR, NULL, 0, 0);
154 else /* op == L_FLIP_PIXELS */
155 pixRasterop(pixd, x, y, w, h, PIX_NOT(PIX_DST), NULL, 0, 0);
156 boxDestroy(&box);
157 }
158
159 return pixd;
160 }
161
162
163 /*!
164 * pixPaintBoxa()
165 *
166 * Input: pixs (any depth, can be cmapped)
167 * boxa (of boxes, to paint)
168 * val (rgba color to paint)
169 * Return: pixd (with painted boxes), or null on error
170 *
171 * Notes:
172 * (1) If pixs is 1 bpp or is colormapped, it is converted to 8 bpp
173 * and the boxa is painted using a colormap; otherwise,
174 * it is converted to 32 bpp rgb.
175 * (2) There are several ways to display a box on an image:
176 * * Paint it as a solid color
177 * * Draw the outline
178 * * Blend the outline or region with the existing image
179 * We provide painting and drawing here; blending is in blend.c.
180 * When painting or drawing, the result can be either a
181 * cmapped image or an rgb image. The dest will be cmapped
182 * if the src is either 1 bpp or has a cmap that is not full.
183 * To force RGB output, use pixConvertTo8(pixs, FALSE)
184 * before calling any of these paint and draw functions.
185 */
186 PIX *
pixPaintBoxa(PIX * pixs,BOXA * boxa,l_uint32 val)187 pixPaintBoxa(PIX *pixs,
188 BOXA *boxa,
189 l_uint32 val)
190 {
191 l_int32 i, n, d, rval, gval, bval, newindex;
192 l_int32 mapvacancy; /* true only if cmap and not full */
193 BOX *box;
194 PIX *pixd;
195 PIXCMAP *cmap;
196
197 PROCNAME("pixPaintBoxa");
198
199 if (!pixs)
200 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
201 if (!boxa)
202 return (PIX *)ERROR_PTR("boxa not defined", procName, NULL);
203
204 if ((n = boxaGetCount(boxa)) == 0) {
205 L_WARNING("no boxes to paint; returning a copy", procName);
206 return pixCopy(NULL, pixs);
207 }
208
209 mapvacancy = FALSE;
210 if ((cmap = pixGetColormap(pixs)) != NULL) {
211 if (pixcmapGetCount(cmap) < 256)
212 mapvacancy = TRUE;
213 }
214 if (pixGetDepth(pixs) == 1 || mapvacancy)
215 pixd = pixConvertTo8(pixs, TRUE);
216 else
217 pixd = pixConvertTo32(pixs);
218 if (!pixd)
219 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
220
221 d = pixGetDepth(pixd);
222 if (d == 8) { /* colormapped */
223 cmap = pixGetColormap(pixd);
224 extractRGBValues(val, &rval, &gval, &bval);
225 if (pixcmapAddNewColor(cmap, rval, gval, bval, &newindex))
226 return (PIX *)ERROR_PTR("cmap full; can't add", procName, NULL);
227 }
228
229 for (i = 0; i < n; i++) {
230 box = boxaGetBox(boxa, i, L_CLONE);
231 if (d == 8)
232 pixSetInRectArbitrary(pixd, box, newindex);
233 else
234 pixSetInRectArbitrary(pixd, box, val);
235 boxDestroy(&box);
236 }
237
238 return pixd;
239 }
240
241
242 /*!
243 * pixPaintBoxaRandom()
244 *
245 * Input: pixs (any depth, can be cmapped)
246 * boxa (of boxes, to paint)
247 * Return: pixd (with painted boxes), or null on error
248 *
249 * Notes:
250 * (1) If pixs is 1 bpp, we paint the boxa using a colormap;
251 * otherwise, we convert to 32 bpp.
252 * (2) We use up to 254 different colors for painting the regions.
253 * (3) If boxes overlap, the later ones paint over earlier ones.
254 */
255 PIX *
pixPaintBoxaRandom(PIX * pixs,BOXA * boxa)256 pixPaintBoxaRandom(PIX *pixs,
257 BOXA *boxa)
258 {
259 l_int32 i, n, d, rval, gval, bval, index;
260 l_uint32 val;
261 BOX *box;
262 PIX *pixd;
263 PIXCMAP *cmap;
264
265 PROCNAME("pixPaintBoxaRandom");
266
267 if (!pixs)
268 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
269 if (!boxa)
270 return (PIX *)ERROR_PTR("boxa not defined", procName, NULL);
271
272 if ((n = boxaGetCount(boxa)) == 0) {
273 L_WARNING("no boxes to paint; returning a copy", procName);
274 return pixCopy(NULL, pixs);
275 }
276
277 if (pixGetDepth(pixs) == 1)
278 pixd = pixConvert1To8(NULL, pixs, 255, 0);
279 else
280 pixd = pixConvertTo32(pixs);
281 if (!pixd)
282 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
283
284 cmap = pixcmapCreateRandom(8, 1, 1);
285 d = pixGetDepth(pixd);
286 if (d == 8) /* colormapped */
287 pixSetColormap(pixd, cmap);
288
289 for (i = 0; i < n; i++) {
290 box = boxaGetBox(boxa, i, L_CLONE);
291 index = 1 + (i % 254);
292 if (d == 8)
293 pixSetInRectArbitrary(pixd, box, index);
294 else { /* d == 32 */
295 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
296 composeRGBPixel(rval, gval, bval, &val);
297 pixSetInRectArbitrary(pixd, box, val);
298 }
299 boxDestroy(&box);
300 }
301
302 if (d == 32)
303 pixcmapDestroy(&cmap);
304 return pixd;
305 }
306
307
308 /*!
309 * pixBlendBoxaRandom()
310 *
311 * Input: pixs (any depth; can be cmapped)
312 * boxa (of boxes, to blend/paint)
313 * fract (of box color to use)
314 * Return: pixd (32 bpp, with blend/painted boxes), or null on error
315 *
316 * Notes:
317 * (1) pixs is converted to 32 bpp.
318 * (2) This differs from pixPaintBoxaRandom(), in that the
319 * colors here are blended with the color of pixs.
320 * (3) We use up to 254 different colors for painting the regions.
321 * (4) If boxes overlap, the final color depends only on the last
322 * rect that is used.
323 */
324 PIX *
pixBlendBoxaRandom(PIX * pixs,BOXA * boxa,l_float32 fract)325 pixBlendBoxaRandom(PIX *pixs,
326 BOXA *boxa,
327 l_float32 fract)
328 {
329 l_int32 i, n, rval, gval, bval, index;
330 l_uint32 val;
331 BOX *box;
332 PIX *pixd;
333 PIXCMAP *cmap;
334
335 PROCNAME("pixBlendBoxaRandom");
336
337 if (!pixs)
338 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
339 if (!boxa)
340 return (PIX *)ERROR_PTR("boxa not defined", procName, NULL);
341 if (fract < 0.0 || fract > 1.0) {
342 L_WARNING("fract must be in [0.0, 1.0]; setting to 0.5", procName);
343 fract = 0.5;
344 }
345
346 if ((n = boxaGetCount(boxa)) == 0) {
347 L_WARNING("no boxes to paint; returning a copy", procName);
348 return pixCopy(NULL, pixs);
349 }
350
351 if ((pixd = pixConvertTo32(pixs)) == NULL)
352 return (PIX *)ERROR_PTR("pixd not defined", procName, NULL);
353
354 cmap = pixcmapCreateRandom(8, 1, 1);
355 for (i = 0; i < n; i++) {
356 box = boxaGetBox(boxa, i, L_CLONE);
357 index = 1 + (i % 254);
358 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
359 composeRGBPixel(rval, gval, bval, &val);
360 pixBlendInRect(pixd, box, val, fract);
361 boxDestroy(&box);
362 }
363
364 pixcmapDestroy(&cmap);
365 return pixd;
366 }
367
368
369 /*!
370 * pixDrawBoxa()
371 *
372 * Input: pixs (any depth; can be cmapped)
373 * boxa (of boxes, to draw)
374 * width (of lines)
375 * val (rgba color to draw)
376 * Return: pixd (with outlines of boxes added), or null on error
377 *
378 * Notes:
379 * (1) If pixs is 1 bpp or is colormapped, it is converted to 8 bpp
380 * and the boxa is drawn using a colormap; otherwise,
381 * it is converted to 32 bpp rgb.
382 */
383 PIX *
pixDrawBoxa(PIX * pixs,BOXA * boxa,l_int32 width,l_uint32 val)384 pixDrawBoxa(PIX *pixs,
385 BOXA *boxa,
386 l_int32 width,
387 l_uint32 val)
388 {
389 l_int32 rval, gval, bval, newindex;
390 l_int32 mapvacancy; /* true only if cmap and not full */
391 PIX *pixd;
392 PIXCMAP *cmap;
393
394 PROCNAME("pixDrawBoxa");
395
396 if (!pixs)
397 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
398 if (!boxa)
399 return (PIX *)ERROR_PTR("boxa not defined", procName, NULL);
400 if (width < 1)
401 return (PIX *)ERROR_PTR("width must be >= 1", procName, NULL);
402
403 if (boxaGetCount(boxa) == 0) {
404 L_WARNING("no boxes to draw; returning a copy", procName);
405 return pixCopy(NULL, pixs);
406 }
407
408 mapvacancy = FALSE;
409 if ((cmap = pixGetColormap(pixs)) != NULL) {
410 if (pixcmapGetCount(cmap) < 256)
411 mapvacancy = TRUE;
412 }
413 if (pixGetDepth(pixs) == 1 || mapvacancy)
414 pixd = pixConvertTo8(pixs, TRUE);
415 else
416 pixd = pixConvertTo32(pixs);
417 if (!pixd)
418 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
419
420 extractRGBValues(val, &rval, &gval, &bval);
421 if (pixGetDepth(pixd) == 8) { /* colormapped */
422 cmap = pixGetColormap(pixd);
423 pixcmapAddNewColor(cmap, rval, gval, bval, &newindex);
424 }
425
426 pixRenderBoxaArb(pixd, boxa, width, rval, gval, bval);
427 return pixd;
428 }
429
430
431 /*!
432 * pixDrawBoxaRandom()
433 *
434 * Input: pixs (any depth, can be cmapped)
435 * boxa (of boxes, to draw)
436 * width (thickness of line)
437 * Return: pixd (with box outlines drawn), or null on error
438 *
439 * Notes:
440 * (1) If pixs is 1 bpp, we draw the boxa using a colormap;
441 * otherwise, we convert to 32 bpp.
442 * (2) We use up to 254 different colors for drawing the boxes.
443 * (3) If boxes overlap, the later ones draw over earlier ones.
444 */
445 PIX *
pixDrawBoxaRandom(PIX * pixs,BOXA * boxa,l_int32 width)446 pixDrawBoxaRandom(PIX *pixs,
447 BOXA *boxa,
448 l_int32 width)
449 {
450 l_int32 i, n, rval, gval, bval, index;
451 BOX *box;
452 PIX *pixd;
453 PIXCMAP *cmap;
454 PTAA *ptaa;
455
456 PROCNAME("pixDrawBoxaRandom");
457
458 if (!pixs)
459 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
460 if (!boxa)
461 return (PIX *)ERROR_PTR("boxa not defined", procName, NULL);
462 if (width < 1)
463 return (PIX *)ERROR_PTR("width must be >= 1", procName, NULL);
464
465 if ((n = boxaGetCount(boxa)) == 0) {
466 L_WARNING("no boxes to draw; returning a copy", procName);
467 return pixCopy(NULL, pixs);
468 }
469
470 /* Input depth = 1 bpp; generate cmapped output */
471 if (pixGetDepth(pixs) == 1) {
472 ptaa = generatePtaaBoxa(boxa);
473 pixd = pixRenderRandomCmapPtaa(pixs, ptaa, 1, width, 1);
474 ptaaDestroy(&ptaa);
475 return pixd;
476 }
477
478 /* Generate rgb output */
479 pixd = pixConvertTo32(pixs);
480 cmap = pixcmapCreateRandom(8, 1, 1);
481 for (i = 0; i < n; i++) {
482 box = boxaGetBox(boxa, i, L_CLONE);
483 index = 1 + (i % 254);
484 pixcmapGetColor(cmap, index, &rval, &gval, &bval);
485 pixRenderBoxArb(pixd, box, width, rval, gval, bval);
486 boxDestroy(&box);
487 }
488 pixcmapDestroy(&cmap);
489 return pixd;
490 }
491
492
493 /*!
494 * boxaaDisplay()
495 *
496 * Input: boxaa
497 * linewba (line width to display boxa)
498 * linewb (line width to display box)
499 * colorba (color to display boxa)
500 * colorb (color to display box)
501 * w (of pix; use 0 if determined by boxaa)
502 * h (of pix; use 0 if determined by boxaa)
503 * Return: 0 if OK, 1 on error
504 */
505 PIX *
boxaaDisplay(BOXAA * boxaa,l_int32 linewba,l_int32 linewb,l_uint32 colorba,l_uint32 colorb,l_int32 w,l_int32 h)506 boxaaDisplay(BOXAA *boxaa,
507 l_int32 linewba,
508 l_int32 linewb,
509 l_uint32 colorba,
510 l_uint32 colorb,
511 l_int32 w,
512 l_int32 h)
513 {
514 l_int32 i, j, n, m, rbox, gbox, bbox, rboxa, gboxa, bboxa;
515 BOX *box;
516 BOXA *boxa;
517 PIX *pix;
518 PIXCMAP *cmap;
519
520 PROCNAME("boxaaDisplay");
521
522 if (!boxaa)
523 return (PIX *)ERROR_PTR("boxaa not defined", procName, NULL);
524 if (w == 0 || h == 0)
525 boxaaGetExtent(boxaa, &w, &h, NULL);
526
527 pix = pixCreate(w, h, 8);
528 cmap = pixcmapCreate(8);
529 pixSetColormap(pix, cmap);
530 extractRGBValues(colorb, &rbox, &gbox, &bbox);
531 extractRGBValues(colorba, &rboxa, &gboxa, &bboxa);
532 pixcmapAddColor(cmap, 255, 255, 255);
533 pixcmapAddColor(cmap, rbox, gbox, bbox);
534 pixcmapAddColor(cmap, rboxa, gboxa, bboxa);
535
536 n = boxaaGetCount(boxaa);
537 for (i = 0; i < n; i++) {
538 boxa = boxaaGetBoxa(boxaa, i, L_CLONE);
539 boxaGetExtent(boxa, NULL, NULL, &box);
540 pixRenderBoxArb(pix, box, linewba, rboxa, gboxa, bboxa);
541 boxDestroy(&box);
542 m = boxaGetCount(boxa);
543 for (j = 0; j < m; j++) {
544 box = boxaGetBox(boxa, j, L_CLONE);
545 pixRenderBoxArb(pix, box, linewb, rbox, gbox, bbox);
546 boxDestroy(&box);
547 }
548 boxaDestroy(&boxa);
549 }
550
551 return pix;
552 }
553
554
555 /*---------------------------------------------------------------------*
556 * Split mask components into Boxa *
557 *---------------------------------------------------------------------*/
558 /*!
559 * pixSplitIntoBoxa()
560 *
561 * Input: pixs (1 bpp)
562 * minsum (minimum pixels to trigger propagation)
563 * skipdist (distance before computing sum for propagation)
564 * delta (difference required to stop propagation)
565 * maxbg (maximum number of allowed bg pixels in ref scan)
566 * maxcomps (use 0 for unlimited number of subdivided components)
567 * remainder (set to 1 to get b.b. of remaining stuff)
568 * Return: boxa (of rectangles covering the fg of pixs), or null on error
569 *
570 * Notes:
571 * (1) This generates a boxa of rectangles that covers
572 * the fg of a mask. For each 8-connected component in pixs,
573 * it does a greedy partitioning, choosing the largest
574 * rectangle found from each of the four directions at each iter.
575 * See pixSplitComponentsIntoBoxa() for details.
576 * (2) The input parameters give some flexibility for boundary
577 * noise. The resulting set of rectangles may cover some
578 * bg pixels.
579 * (3) This should be used when there are a small number of
580 * mask components, each of which has sides that are close
581 * to horizontal and vertical. The input parameters @delta
582 * and @maxbg determine whether or not holes in the mask are covered.
583 * (4) The parameter @maxcomps gives the maximum number of allowed
584 * rectangles extracted from any single connected component.
585 * Use 0 if no limit is to be applied.
586 * (5) The flag @remainder specifies whether we take a final bounding
587 * box for anything left after the maximum number of allowed
588 * rectangle is extracted.
589 */
590 BOXA *
pixSplitIntoBoxa(PIX * pixs,l_int32 minsum,l_int32 skipdist,l_int32 delta,l_int32 maxbg,l_int32 maxcomps,l_int32 remainder)591 pixSplitIntoBoxa(PIX *pixs,
592 l_int32 minsum,
593 l_int32 skipdist,
594 l_int32 delta,
595 l_int32 maxbg,
596 l_int32 maxcomps,
597 l_int32 remainder)
598 {
599 l_int32 i, n;
600 BOX *box;
601 BOXA *boxa, *boxas, *boxad;
602 PIX *pix;
603 PIXA *pixas;
604
605 PROCNAME("pixSplitIntoBoxa");
606
607 if (!pixs || pixGetDepth(pixs) != 1)
608 return (BOXA *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
609
610 boxas = pixConnComp(pixs, &pixas, 8);
611 n = boxaGetCount(boxas);
612 boxad = boxaCreate(0);
613 for (i = 0; i < n; i++) {
614 pix = pixaGetPix(pixas, i, L_CLONE);
615 box = boxaGetBox(boxas, i, L_CLONE);
616 boxa = pixSplitComponentIntoBoxa(pix, box, minsum, skipdist,
617 delta, maxbg, maxcomps, remainder);
618 boxaJoin(boxad, boxa, 0, 0);
619 pixDestroy(&pix);
620 boxDestroy(&box);
621 boxaDestroy(&boxa);
622 }
623
624 pixaDestroy(&pixas);
625 boxaDestroy(&boxas);
626 return boxad;
627 }
628
629
630 /*!
631 * pixSplitComponentIntoBoxa()
632 *
633 * Input: pixs (1 bpp)
634 * box (<optional> location of pixs w/rt an origin)
635 * minsum (minimum pixels to trigger propagation)
636 * skipdist (distance before computing sum for propagation)
637 * delta (difference required to stop propagation)
638 * maxbg (maximum number of allowed bg pixels in ref scan)
639 * maxcomps (use 0 for unlimited number of subdivided components)
640 * remainder (set to 1 to get b.b. of remaining stuff)
641 * Return: boxa (of rectangles covering the fg of pixs), or null on error
642 *
643 * Notes:
644 * (1) This generates a boxa of rectangles that covers
645 * the fg of a mask. It does so by a greedy partitioning of
646 * the mask, choosing the largest rectangle found from
647 * each of the four directions at each step.
648 * (2) The input parameters give some flexibility for boundary
649 * noise. The resulting set of rectangles must cover all
650 * the fg pixels and, in addition, may cover some bg pixels.
651 * Using small input parameters on a noiseless mask (i.e., one
652 * that has only large vertical and horizontal edges) will
653 * result in a proper covering of only the fg pixels of the mask.
654 * (3) The input is assumed to be a single connected component, that
655 * may have holes. From each side, sweep inward, counting
656 * the pixels. If the count becomes greater than @minsum,
657 * and we have moved forward a further amount @skipdist,
658 * record that count ('countref'), but don't accept if the scan
659 * contains more than @maxbg bg pixels. Continue the scan
660 * until we reach a count that differs from countref by at
661 * least @delta, at which point the propagation stops. The box
662 * swept out gets a score, which is the sum of fg pixels
663 * minus a penalty. The penalty is the number of bg pixels
664 * in the box. This is done from all four sides, and the
665 * side with the largest score is saved as a rectangle.
666 * The process repeats until there is either no rectangle
667 * left, or there is one that can't be captured from any
668 * direction. For the latter case, we simply accept the
669 * last rectangle.
670 * (4) The input box is only used to specify the location of
671 * the UL corner of pixs, with respect to an origin that
672 * typically represents the UL corner of an underlying image,
673 * of which pixs is one component. If @box is null,
674 * the UL corner is taken to be (0, 0).
675 * (5) The parameter @maxcomps gives the maximum number of allowed
676 * rectangles extracted from any single connected component.
677 * Use 0 if no limit is to be applied.
678 * (6) The flag @remainder specifies whether we take a final bounding
679 * box for anything left after the maximum number of allowed
680 * rectangle is extracted.
681 * (7) So if @maxcomps > 0, it specifies that we want no more than
682 * the first @maxcomps rectangles that satisfy the input
683 * criteria. After this, we can get a final rectangle that
684 * bounds everything left over by setting @remainder == 1.
685 * If @remainder == 0, we only get rectangles that satisfy
686 * the input criteria.
687 * (8) It should be noted that the removal of rectangles can
688 * break the original c.c. into several c.c.
689 * (9) Summing up:
690 * * If @maxcomp == 0, the splitting proceeds as far as possible.
691 * * If @maxcomp > 0, the splitting stops when @maxcomps are
692 * found, or earlier if no more components can be selected.
693 * * If @remainder == 1 and components remain that cannot be
694 * selected, they are returned as a single final rectangle;
695 * otherwise, they are ignored.
696 */
697 BOXA *
pixSplitComponentIntoBoxa(PIX * pix,BOX * box,l_int32 minsum,l_int32 skipdist,l_int32 delta,l_int32 maxbg,l_int32 maxcomps,l_int32 remainder)698 pixSplitComponentIntoBoxa(PIX *pix,
699 BOX *box,
700 l_int32 minsum,
701 l_int32 skipdist,
702 l_int32 delta,
703 l_int32 maxbg,
704 l_int32 maxcomps,
705 l_int32 remainder)
706 {
707 l_int32 i, w, h, boxx, boxy, bx, by, bw, bh, maxdir, maxscore;
708 l_int32 iter;
709 BOX *boxs; /* shrinks as rectangular regions are removed */
710 BOX *boxt1, *boxt2, *boxt3;
711 BOXA *boxat; /* stores rectangle data for each side in an iteration */
712 BOXA *boxad;
713 NUMA *nascore, *nas;
714 PIX *pixs;
715
716 PROCNAME("pixSplitComponentIntoBoxa");
717
718 if (!pix || pixGetDepth(pix) != 1)
719 return (BOXA *)ERROR_PTR("pix undefined or not 1 bpp", procName, NULL);
720
721 pixs = pixCopy(NULL, pix);
722 pixGetDimensions(pixs, &w, &h, NULL);
723 if (box)
724 boxGetGeometry(box, &boxx, &boxy, NULL, NULL);
725 else
726 boxx = boxy = 0;
727 boxs = boxCreate(0, 0, w, h);
728 boxad = boxaCreate(0);
729
730 iter = 0;
731 while (boxs != NULL) {
732 boxGetGeometry(boxs, &bx, &by, &bw, &bh);
733 boxat = boxaCreate(4); /* potential rectangular regions */
734 nascore = numaCreate(4);
735 for (i = 0; i < 4; i++) {
736 pixSearchForRectangle(pixs, boxs, minsum, skipdist, delta, maxbg,
737 i, boxat, nascore);
738 }
739 nas = numaGetSortIndex(nascore, L_SORT_DECREASING);
740 numaGetIValue(nas, 0, &maxdir);
741 numaGetIValue(nascore, maxdir, &maxscore);
742 #if DEBUG_SPLIT
743 fprintf(stderr, "Iteration: %d\n", iter);
744 boxPrintStreamInfo(stderr, boxs);
745 boxaWriteStream(stderr, boxat);
746 fprintf(stderr, "\nmaxdir = %d, maxscore = %d\n\n", maxdir, maxscore);
747 #endif /* DEBUG_SPLIT */
748 if (maxscore > 0) { /* accept this */
749 boxt1 = boxaGetBox(boxat, maxdir, L_CLONE);
750 boxt2 = boxTransform(boxt1, boxx, boxy, 1.0, 1.0);
751 boxaAddBox(boxad, boxt2, L_INSERT);
752 pixClearInRect(pixs, boxt1);
753 boxDestroy(&boxt1);
754 pixClipBoxToForeground(pixs, boxs, NULL, &boxt3);
755 boxDestroy(&boxs);
756 boxs = boxt3;
757 if (boxs) {
758 boxGetGeometry(boxs, NULL, NULL, &bw, &bh);
759 if (bw < 2 || bh < 2)
760 boxDestroy(&boxs); /* we're done */
761 }
762 }
763 else { /* no more valid rectangles can be found */
764 if (remainder == 1) { /* save the last box */
765 boxt1 = boxTransform(boxs, boxx, boxy, 1.0, 1.0);
766 boxaAddBox(boxad, boxt1, L_INSERT);
767 }
768 boxDestroy(&boxs); /* we're done */
769 }
770 boxaDestroy(&boxat);
771 numaDestroy(&nascore);
772 numaDestroy(&nas);
773
774 iter++;
775 if ((iter == maxcomps) && boxs) {
776 if (remainder == 1) { /* save the last box */
777 boxt1 = boxTransform(boxs, boxx, boxy, 1.0, 1.0);
778 boxaAddBox(boxad, boxt1, L_INSERT);
779 }
780 boxDestroy(&boxs); /* we're done */
781 }
782 }
783
784 pixDestroy(&pixs);
785 return boxad;
786 }
787
788
789 /*!
790 * pixSearchForRectangle()
791 *
792 * Input: pixs (1 bpp)
793 * boxs (current region to investigate)
794 * minsum (minimum pixels to trigger propagation)
795 * skipdist (distance before computing sum for propagation)
796 * delta (difference required to stop propagation)
797 * maxbg (maximum number of allowed bg pixels in ref scan)
798 * sideflag (side to search from)
799 * boxat (add result of rectangular region found here)
800 * nascore (add score for this rectangle here)
801 * Return: 0 if OK, 1 on error
802 *
803 * Notes:
804 * (1) See pixSplitByRectangles() for an explanation of the algorithm.
805 * This does the sweep from a single side. For each iteration
806 * in pixSplitByRectangles(), this will be called 4 times,
807 * for @sideflag = {0, 1, 2, 3}.
808 * (2) If a valid rectangle is not found, add a score of 0 and
809 * input a minimum box.
810 */
811 static l_int32
pixSearchForRectangle(PIX * pixs,BOX * boxs,l_int32 minsum,l_int32 skipdist,l_int32 delta,l_int32 maxbg,l_int32 sideflag,BOXA * boxat,NUMA * nascore)812 pixSearchForRectangle(PIX *pixs,
813 BOX *boxs,
814 l_int32 minsum,
815 l_int32 skipdist,
816 l_int32 delta,
817 l_int32 maxbg,
818 l_int32 sideflag,
819 BOXA *boxat,
820 NUMA *nascore)
821 {
822 l_int32 bx, by, bw, bh, width, height, setref, atref;
823 l_int32 minincol, maxincol, mininrow, maxinrow, minval, maxval, bgref;
824 l_int32 x, y, x0, y0, xref, yref, colsum, rowsum, score, countref, diff;
825 void **lines1;
826 BOX *boxr;
827
828 PROCNAME("pixSearchForRectangle");
829
830 if (!pixs || pixGetDepth(pixs) != 1)
831 return ERROR_INT("pixs undefined or not 1 bpp", procName, 1);
832 if (!boxs)
833 return ERROR_INT("boxs not defined", procName, 1);
834 if (!boxat)
835 return ERROR_INT("boxat not defined", procName, 1);
836 if (!nascore)
837 return ERROR_INT("nascore not defined", procName, 1);
838
839 lines1 = pixGetLinePtrs(pixs, NULL);
840 boxGetGeometry(boxs, &bx, &by, &bw, &bh);
841 boxr = NULL;
842 setref = 0;
843 atref = 0;
844 maxval = 0;
845 minval = 100000;
846 score = 0; /* sum of all (fg - bg) pixels seen in the scan */
847 xref = yref = 100000; /* init to impossibly big number */
848 if (sideflag == L_FROM_LEFT) {
849 for (x = bx; x < bx + bw; x++) {
850 colsum = 0;
851 maxincol = 0;
852 minincol = 100000;
853 for (y = by; y < by + bh; y++) {
854 if (GET_DATA_BIT(lines1[y], x)) {
855 colsum++;
856 if (y > maxincol) maxincol = y;
857 if (y < minincol) minincol = y;
858 }
859 }
860 score += colsum;
861
862 /* Enough fg to sweep out a rectangle? */
863 if (!setref && colsum >= minsum) {
864 setref = 1;
865 xref = x + 10;
866 if (xref >= bx + bw)
867 goto failure;
868 }
869
870 /* Reached the reference line; save the count;
871 * if there is too much bg, the rectangle is invalid. */
872 if (setref && x == xref) {
873 atref = 1;
874 countref = colsum;
875 bgref = maxincol - minincol + 1 - countref;
876 if (bgref > maxbg)
877 goto failure;
878 }
879
880 /* Have we left the rectangle? If so, save it along
881 * with the score. */
882 if (atref) {
883 diff = L_ABS(colsum - countref);
884 if (diff >= delta || x == bx + bw - 1) {
885 height = maxval - minval + 1;
886 width = x - bx;
887 if (x == bx + bw - 1) width = x - bx + 1;
888 boxr = boxCreate(bx, minval, width, height);
889 score = 2 * score - width * height;
890 goto success;
891 }
892 }
893 maxval = L_MAX(maxval, maxincol);
894 minval = L_MIN(minval, minincol);
895 }
896 goto failure;
897 }
898 else if (sideflag == L_FROM_RIGHT) {
899 for (x = bx + bw - 1; x >= bx; x--) {
900 colsum = 0;
901 maxincol = 0;
902 minincol = 100000;
903 for (y = by; y < by + bh; y++) {
904 if (GET_DATA_BIT(lines1[y], x)) {
905 colsum++;
906 if (y > maxincol) maxincol = y;
907 if (y < minincol) minincol = y;
908 }
909 }
910 score += colsum;
911 if (!setref && colsum >= minsum) {
912 setref = 1;
913 xref = x - 10;
914 if (xref < bx)
915 goto failure;
916 }
917 if (setref && x == xref) {
918 atref = 1;
919 countref = colsum;
920 bgref = maxincol - minincol + 1 - countref;
921 if (bgref > maxbg)
922 goto failure;
923 }
924 if (atref) {
925 diff = L_ABS(colsum - countref);
926 if (diff >= delta || x == bx) {
927 height = maxval - minval + 1;
928 x0 = x + 1;
929 if (x == bx) x0 = x;
930 width = bx + bw - x0;
931 boxr = boxCreate(x0, minval, width, height);
932 score = 2 * score - width * height;
933 goto success;
934 }
935 }
936 maxval = L_MAX(maxval, maxincol);
937 minval = L_MIN(minval, minincol);
938 }
939 goto failure;
940 }
941 else if (sideflag == L_FROM_TOP) {
942 for (y = by; y < by + bh; y++) {
943 rowsum = 0;
944 maxinrow = 0;
945 mininrow = 100000;
946 for (x = bx; x < bx + bw; x++) {
947 if (GET_DATA_BIT(lines1[y], x)) {
948 rowsum++;
949 if (x > maxinrow) maxinrow = x;
950 if (x < mininrow) mininrow = x;
951 }
952 }
953 score += rowsum;
954 if (!setref && rowsum >= minsum) {
955 setref = 1;
956 yref = y + 10;
957 if (yref >= by + bh)
958 goto failure;
959 }
960 if (setref && y == yref) {
961 atref = 1;
962 countref = rowsum;
963 bgref = maxinrow - mininrow + 1 - countref;
964 if (bgref > maxbg)
965 goto failure;
966 }
967 if (atref) {
968 diff = L_ABS(rowsum - countref);
969 if (diff >= delta || y == by + bh - 1) {
970 width = maxval - minval + 1;
971 height = y - by;
972 if (y == by + bh - 1) height = y - by + 1;
973 boxr = boxCreate(minval, by, width, height);
974 score = 2 * score - width * height;
975 goto success;
976 }
977 }
978 maxval = L_MAX(maxval, maxinrow);
979 minval = L_MIN(minval, mininrow);
980 }
981 goto failure;
982 } else if (sideflag == L_FROM_BOTTOM) {
983 for (y = by + bh - 1; y >= by; y--) {
984 rowsum = 0;
985 maxinrow = 0;
986 mininrow = 100000;
987 for (x = bx; x < bx + bw; x++) {
988 if (GET_DATA_BIT(lines1[y], x)) {
989 rowsum++;
990 if (x > maxinrow) maxinrow = x;
991 if (x < mininrow) mininrow = x;
992 }
993 }
994 score += rowsum;
995 if (!setref && rowsum >= minsum) {
996 setref = 1;
997 yref = y - 10;
998 if (yref < by)
999 goto failure;
1000 }
1001 if (setref && y == yref) {
1002 atref = 1;
1003 countref = rowsum;
1004 bgref = maxinrow - mininrow + 1 - countref;
1005 if (bgref > maxbg)
1006 goto failure;
1007 }
1008 if (atref) {
1009 diff = L_ABS(rowsum - countref);
1010 if (diff >= delta || y == by) {
1011 width = maxval - minval + 1;
1012 y0 = y + 1;
1013 if (y == by) y0 = y;
1014 height = by + bh - y0;
1015 boxr = boxCreate(minval, y0, width, height);
1016 score = 2 * score - width * height;
1017 goto success;
1018 }
1019 }
1020 maxval = L_MAX(maxval, maxinrow);
1021 minval = L_MIN(minval, mininrow);
1022 }
1023 goto failure;
1024 }
1025
1026 failure:
1027 numaAddNumber(nascore, 0);
1028 boxaAddBox(boxat, boxCreate(0, 0, 1, 1), L_INSERT); /* min box */
1029 FREE(lines1);
1030 return 0;
1031
1032 success:
1033 numaAddNumber(nascore, score);
1034 boxaAddBox(boxat, boxr, L_INSERT);
1035 FREE(lines1);
1036 return 0;
1037 }
1038
1039
1040