Leptonica 1.83.1
Image processing and image analysis suite
Loading...
Searching...
No Matches
boxfunc2.c
Go to the documentation of this file.
1/*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
67#ifdef HAVE_CONFIG_H
68#include <config_auto.h>
69#endif /* HAVE_CONFIG_H */
70
71#include <math.h>
72#include "allheaders.h"
73#include "pix_internal.h"
74
75 /* For more than this number of c.c. in a binarized image of
76 * semi-perimeter (w + h) about 5000 or less, the O(n) binsort
77 * is faster than the O(nlogn) shellsort. */
78static const l_int32 MinCompsForBinSort = 200;
79
80/*---------------------------------------------------------------------*
81 * Boxa/Box transform (shift, scale) and orthogonal rotation *
82 *---------------------------------------------------------------------*/
102BOXA *
103boxaTransform(BOXA *boxas,
104 l_int32 shiftx,
105 l_int32 shifty,
106 l_float32 scalex,
107 l_float32 scaley)
108{
109l_int32 i, n;
110BOX *boxs, *boxd;
111BOXA *boxad;
112
113 if (!boxas)
114 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
115 n = boxaGetCount(boxas);
116 if ((boxad = boxaCreate(n)) == NULL)
117 return (BOXA *)ERROR_PTR("boxad not made", __func__, NULL);
118 for (i = 0; i < n; i++) {
119 if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
120 boxaDestroy(&boxad);
121 return (BOXA *)ERROR_PTR("boxs not found", __func__, NULL);
122 }
123 boxd = boxTransform(boxs, shiftx, shifty, scalex, scaley);
124 boxDestroy(&boxs);
125 boxaAddBox(boxad, boxd, L_INSERT);
126 }
127
128 return boxad;
129}
130
131
150BOX *
151boxTransform(BOX *box,
152 l_int32 shiftx,
153 l_int32 shifty,
154 l_float32 scalex,
155 l_float32 scaley)
156{
157 if (!box)
158 return (BOX *)ERROR_PTR("box not defined", __func__, NULL);
159 if (box->w <= 0 || box->h <= 0)
160 return boxCreate(0, 0, 0, 0);
161 else
162 return boxCreate((l_int32)(L_MAX(0, scalex * (box->x + shiftx) + 0.5)),
163 (l_int32)(L_MAX(0, scaley * (box->y + shifty) + 0.5)),
164 (l_int32)(L_MAX(1.0, scalex * box->w + 0.5)),
165 (l_int32)(L_MAX(1.0, scaley * box->h + 0.5)));
166}
167
168
202BOXA *
203boxaTransformOrdered(BOXA *boxas,
204 l_int32 shiftx,
205 l_int32 shifty,
206 l_float32 scalex,
207 l_float32 scaley,
208 l_int32 xcen,
209 l_int32 ycen,
210 l_float32 angle,
211 l_int32 order)
212{
213l_int32 i, n;
214BOX *boxs, *boxd;
215BOXA *boxad;
216
217 if (!boxas)
218 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
219 n = boxaGetCount(boxas);
220 if ((boxad = boxaCreate(n)) == NULL)
221 return (BOXA *)ERROR_PTR("boxad not made", __func__, NULL);
222 for (i = 0; i < n; i++) {
223 if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
224 boxaDestroy(&boxad);
225 return (BOXA *)ERROR_PTR("boxs not found", __func__, NULL);
226 }
227 boxd = boxTransformOrdered(boxs, shiftx, shifty, scalex, scaley,
228 xcen, ycen, angle, order);
229 boxDestroy(&boxs);
230 boxaAddBox(boxad, boxd, L_INSERT);
231 }
232
233 return boxad;
234}
235
236
290BOX *
291boxTransformOrdered(BOX *boxs,
292 l_int32 shiftx,
293 l_int32 shifty,
294 l_float32 scalex,
295 l_float32 scaley,
296 l_int32 xcen,
297 l_int32 ycen,
298 l_float32 angle,
299 l_int32 order)
300{
301l_int32 bx, by, bw, bh, tx, ty, tw, th;
302l_int32 xcent, ycent; /* transformed center of rotation due to scaling */
303l_float32 sina, cosa, xdif, ydif, rx, ry, rw, rh;
304BOX *boxd;
305
306 if (!boxs)
307 return (BOX *)ERROR_PTR("boxs not defined", __func__, NULL);
308 if (order != L_TR_SC_RO && order != L_SC_RO_TR && order != L_RO_TR_SC &&
309 order != L_TR_RO_SC && order != L_RO_SC_TR && order != L_SC_TR_RO)
310 return (BOX *)ERROR_PTR("order invalid", __func__, NULL);
311
312 boxGetGeometry(boxs, &bx, &by, &bw, &bh);
313 if (bw <= 0 || bh <= 0) /* invalid */
314 return boxCreate(0, 0, 0, 0);
315 if (angle != 0.0) {
316 sina = sin(angle);
317 cosa = cos(angle);
318 }
319
320 if (order == L_TR_SC_RO) {
321 tx = (l_int32)(scalex * (bx + shiftx) + 0.5);
322 ty = (l_int32)(scaley * (by + shifty) + 0.5);
323 tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
324 th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
325 xcent = (l_int32)(scalex * xcen + 0.5);
326 ycent = (l_int32)(scaley * ycen + 0.5);
327 if (angle == 0.0) {
328 boxd = boxCreate(tx, ty, tw, th);
329 } else {
330 xdif = tx + 0.5 * tw - xcent;
331 ydif = ty + 0.5 * th - ycent;
332 rw = L_ABS(tw * cosa) + L_ABS(th * sina);
333 rh = L_ABS(th * cosa) + L_ABS(tw * sina);
334 rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
335 ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
336 boxd = boxCreate((l_int32)rx, (l_int32)ry, (l_int32)rw,
337 (l_int32)rh);
338 }
339 } else if (order == L_SC_TR_RO) {
340 tx = (l_int32)(scalex * bx + shiftx + 0.5);
341 ty = (l_int32)(scaley * by + shifty + 0.5);
342 tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
343 th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
344 xcent = (l_int32)(scalex * xcen + 0.5);
345 ycent = (l_int32)(scaley * ycen + 0.5);
346 if (angle == 0.0) {
347 boxd = boxCreate(tx, ty, tw, th);
348 } else {
349 xdif = tx + 0.5 * tw - xcent;
350 ydif = ty + 0.5 * th - ycent;
351 rw = L_ABS(tw * cosa) + L_ABS(th * sina);
352 rh = L_ABS(th * cosa) + L_ABS(tw * sina);
353 rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
354 ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
355 boxd = boxCreate((l_int32)rx, (l_int32)ry, (l_int32)rw,
356 (l_int32)rh);
357 }
358 } else if (order == L_RO_TR_SC) {
359 if (angle == 0.0) {
360 rx = bx;
361 ry = by;
362 rw = bw;
363 rh = bh;
364 } else {
365 xdif = bx + 0.5 * bw - xcen;
366 ydif = by + 0.5 * bh - ycen;
367 rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
368 rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
369 rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
370 ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
371 }
372 tx = (l_int32)(scalex * (rx + shiftx) + 0.5);
373 ty = (l_int32)(scaley * (ry + shifty) + 0.5);
374 tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
375 th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
376 boxd = boxCreate(tx, ty, tw, th);
377 } else if (order == L_RO_SC_TR) {
378 if (angle == 0.0) {
379 rx = bx;
380 ry = by;
381 rw = bw;
382 rh = bh;
383 } else {
384 xdif = bx + 0.5 * bw - xcen;
385 ydif = by + 0.5 * bh - ycen;
386 rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
387 rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
388 rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
389 ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
390 }
391 tx = (l_int32)(scalex * rx + shiftx + 0.5);
392 ty = (l_int32)(scaley * ry + shifty + 0.5);
393 tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
394 th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
395 boxd = boxCreate(tx, ty, tw, th);
396 } else if (order == L_TR_RO_SC) {
397 tx = bx + shiftx;
398 ty = by + shifty;
399 if (angle == 0.0) {
400 rx = tx;
401 ry = ty;
402 rw = bw;
403 rh = bh;
404 } else {
405 xdif = tx + 0.5 * bw - xcen;
406 ydif = ty + 0.5 * bh - ycen;
407 rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
408 rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
409 rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
410 ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
411 }
412 tx = (l_int32)(scalex * rx + 0.5);
413 ty = (l_int32)(scaley * ry + 0.5);
414 tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
415 th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
416 boxd = boxCreate(tx, ty, tw, th);
417 } else { /* order == L_SC_RO_TR) */
418 tx = (l_int32)(scalex * bx + 0.5);
419 ty = (l_int32)(scaley * by + 0.5);
420 tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
421 th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
422 xcent = (l_int32)(scalex * xcen + 0.5);
423 ycent = (l_int32)(scaley * ycen + 0.5);
424 if (angle == 0.0) {
425 rx = tx;
426 ry = ty;
427 rw = tw;
428 rh = th;
429 } else {
430 xdif = tx + 0.5 * tw - xcent;
431 ydif = ty + 0.5 * th - ycent;
432 rw = L_ABS(tw * cosa) + L_ABS(th * sina);
433 rh = L_ABS(th * cosa) + L_ABS(tw * sina);
434 rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
435 ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
436 }
437 tx = (l_int32)(rx + shiftx + 0.5);
438 ty = (l_int32)(ry + shifty + 0.5);
439 tw = (l_int32)(rw + 0.5);
440 th = (l_int32)(rh + 0.5);
441 boxd = boxCreate(tx, ty, tw, th);
442 }
443
444 return boxd;
445}
446
447
462BOXA *
463boxaRotateOrth(BOXA *boxas,
464 l_int32 w,
465 l_int32 h,
466 l_int32 rotation)
467{
468l_int32 i, n;
469BOX *boxs, *boxd;
470BOXA *boxad;
471
472 if (!boxas)
473 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
474 if (rotation < 0 || rotation > 3)
475 return (BOXA *)ERROR_PTR("rotation not in {0,1,2,3}", __func__, NULL);
476 if (rotation == 0)
477 return boxaCopy(boxas, L_COPY);
478
479 n = boxaGetCount(boxas);
480 if ((boxad = boxaCreate(n)) == NULL)
481 return (BOXA *)ERROR_PTR("boxad not made", __func__, NULL);
482 for (i = 0; i < n; i++) {
483 if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL) {
484 boxaDestroy(&boxad);
485 return (BOXA *)ERROR_PTR("boxs not found", __func__, NULL);
486 }
487 boxd = boxRotateOrth(boxs, w, h, rotation);
488 boxDestroy(&boxs);
489 boxaAddBox(boxad, boxd, L_INSERT);
490 }
491
492 return boxad;
493}
494
495
512BOX *
513boxRotateOrth(BOX *box,
514 l_int32 w,
515 l_int32 h,
516 l_int32 rotation)
517{
518l_int32 bx, by, bw, bh, xdist, ydist;
519
520 if (!box)
521 return (BOX *)ERROR_PTR("box not defined", __func__, NULL);
522 if (rotation < 0 || rotation > 3)
523 return (BOX *)ERROR_PTR("rotation not in {0,1,2,3}", __func__, NULL);
524 if (rotation == 0)
525 return boxCopy(box);
526
527 boxGetGeometry(box, &bx, &by, &bw, &bh);
528 if (bw <= 0 || bh <= 0) /* invalid */
529 return boxCreate(0, 0, 0, 0);
530 ydist = h - by - bh; /* below box */
531 xdist = w - bx - bw; /* to right of box */
532 if (rotation == 1) /* 90 deg cw */
533 return boxCreate(ydist, bx, bh, bw);
534 else if (rotation == 2) /* 180 deg cw */
535 return boxCreate(xdist, ydist, bw, bh);
536 else /* rotation == 3, 270 deg cw */
537 return boxCreate(by, xdist, bh, bw);
538}
539
540
565BOXA *
566boxaShiftWithPta(BOXA *boxas,
567 PTA *pta,
568 l_int32 dir)
569{
570l_int32 i, n, x, y, full;
571BOX *box1, *box2;
572BOXA *boxad;
573
574 if (!boxas)
575 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
576 boxaIsFull(boxas, &full);
577 if (!full)
578 return (BOXA *)ERROR_PTR("boxas not full", __func__, NULL);
579 if (!pta)
580 return (BOXA *)ERROR_PTR("pta not defined", __func__, NULL);
581 if (dir != 1 && dir != -1)
582 return (BOXA *)ERROR_PTR("invalid dir", __func__, NULL);
583 n = boxaGetCount(boxas);
584 if (n != ptaGetCount(pta))
585 return (BOXA *)ERROR_PTR("boxas and pta not same size", __func__, NULL);
586
587 if ((boxad = boxaCreate(n)) == NULL)
588 return (BOXA *)ERROR_PTR("boxad not made", __func__, NULL);
589 for (i = 0; i < n; i++) {
590 box1 = boxaGetBox(boxas, i, L_COPY);
591 ptaGetIPt(pta, i, &x, &y);
592 box2 = boxTransform(box1, dir * x, dir * y, 1.0, 1.0);
593 boxaAddBox(boxad, box2, L_INSERT);
594 boxDestroy(&box1);
595 }
596 return boxad;
597}
598
599
600/*---------------------------------------------------------------------*
601 * Boxa sort *
602 *---------------------------------------------------------------------*/
623BOXA *
624boxaSort(BOXA *boxas,
625 l_int32 sorttype,
626 l_int32 sortorder,
627 NUMA **pnaindex)
628{
629l_int32 i, n, x, y, w, h, size;
630BOXA *boxad;
631NUMA *na, *naindex;
632
633 if (pnaindex) *pnaindex = NULL;
634 if (!boxas)
635 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
636 if ((n = boxaGetCount(boxas)) == 0) {
637 L_WARNING("boxas is empty\n", __func__);
638 return boxaCopy(boxas, L_COPY);
639 }
640 if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
641 sorttype != L_SORT_BY_RIGHT && sorttype != L_SORT_BY_BOT &&
642 sorttype != L_SORT_BY_WIDTH && sorttype != L_SORT_BY_HEIGHT &&
643 sorttype != L_SORT_BY_MIN_DIMENSION &&
644 sorttype != L_SORT_BY_MAX_DIMENSION &&
645 sorttype != L_SORT_BY_PERIMETER &&
646 sorttype != L_SORT_BY_AREA &&
647 sorttype != L_SORT_BY_ASPECT_RATIO)
648 return (BOXA *)ERROR_PTR("invalid sort type", __func__, NULL);
649 if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
650 return (BOXA *)ERROR_PTR("invalid sort order", __func__, NULL);
651
652 /* Use O(n) binsort if possible */
653 if (n > MinCompsForBinSort &&
654 ((sorttype == L_SORT_BY_X) || (sorttype == L_SORT_BY_Y) ||
655 (sorttype == L_SORT_BY_WIDTH) || (sorttype == L_SORT_BY_HEIGHT) ||
656 (sorttype == L_SORT_BY_PERIMETER)))
657 return boxaBinSort(boxas, sorttype, sortorder, pnaindex);
658
659 /* Build up numa of specific data */
660 if ((na = numaCreate(n)) == NULL)
661 return (BOXA *)ERROR_PTR("na not made", __func__, NULL);
662 for (i = 0; i < n; i++) {
663 boxaGetBoxGeometry(boxas, i, &x, &y, &w, &h);
664 switch (sorttype)
665 {
666 case L_SORT_BY_X:
667 numaAddNumber(na, x);
668 break;
669 case L_SORT_BY_Y:
670 numaAddNumber(na, y);
671 break;
672 case L_SORT_BY_RIGHT:
673 numaAddNumber(na, x + w - 1);
674 break;
675 case L_SORT_BY_BOT:
676 numaAddNumber(na, y + h - 1);
677 break;
678 case L_SORT_BY_WIDTH:
679 numaAddNumber(na, w);
680 break;
681 case L_SORT_BY_HEIGHT:
682 numaAddNumber(na, h);
683 break;
684 case L_SORT_BY_MIN_DIMENSION:
685 size = L_MIN(w, h);
686 numaAddNumber(na, size);
687 break;
688 case L_SORT_BY_MAX_DIMENSION:
689 size = L_MAX(w, h);
690 numaAddNumber(na, size);
691 break;
692 case L_SORT_BY_PERIMETER:
693 size = w + h;
694 numaAddNumber(na, size);
695 break;
696 case L_SORT_BY_AREA:
697 size = w * h;
698 numaAddNumber(na, size);
699 break;
700 case L_SORT_BY_ASPECT_RATIO:
701 numaAddNumber(na, (l_float32)w / (l_float32)h);
702 break;
703 default:
704 L_WARNING("invalid sort type\n", __func__);
705 }
706 }
707
708 /* Get the sort index for data array */
709 naindex = numaGetSortIndex(na, sortorder);
710 numaDestroy(&na);
711 if (!naindex)
712 return (BOXA *)ERROR_PTR("naindex not made", __func__, NULL);
713
714 /* Build up sorted boxa using sort index */
715 boxad = boxaSortByIndex(boxas, naindex);
716
717 if (pnaindex)
718 *pnaindex = naindex;
719 else
720 numaDestroy(&naindex);
721 return boxad;
722}
723
724
745BOXA *
746boxaBinSort(BOXA *boxas,
747 l_int32 sorttype,
748 l_int32 sortorder,
749 NUMA **pnaindex)
750{
751l_int32 i, n, x, y, w, h;
752BOXA *boxad;
753NUMA *na, *naindex;
754
755 if (pnaindex) *pnaindex = NULL;
756 if (!boxas)
757 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
758 if ((n = boxaGetCount(boxas)) == 0) {
759 L_WARNING("boxas is empty\n", __func__);
760 return boxaCopy(boxas, L_COPY);
761 }
762 if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
763 sorttype != L_SORT_BY_WIDTH && sorttype != L_SORT_BY_HEIGHT &&
764 sorttype != L_SORT_BY_PERIMETER)
765 return (BOXA *)ERROR_PTR("invalid sort type", __func__, NULL);
766 if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
767 return (BOXA *)ERROR_PTR("invalid sort order", __func__, NULL);
768
769 /* Generate Numa of appropriate box dimensions */
770 if ((na = numaCreate(n)) == NULL)
771 return (BOXA *)ERROR_PTR("na not made", __func__, NULL);
772 for (i = 0; i < n; i++) {
773 boxaGetBoxGeometry(boxas, i, &x, &y, &w, &h);
774 switch (sorttype)
775 {
776 case L_SORT_BY_X:
777 numaAddNumber(na, x);
778 break;
779 case L_SORT_BY_Y:
780 numaAddNumber(na, y);
781 break;
782 case L_SORT_BY_WIDTH:
783 numaAddNumber(na, w);
784 break;
785 case L_SORT_BY_HEIGHT:
786 numaAddNumber(na, h);
787 break;
788 case L_SORT_BY_PERIMETER:
789 numaAddNumber(na, w + h);
790 break;
791 default:
792 L_WARNING("invalid sort type\n", __func__);
793 }
794 }
795
796 /* Get the sort index for data array */
797 naindex = numaGetBinSortIndex(na, sortorder);
798 numaDestroy(&na);
799 if (!naindex)
800 return (BOXA *)ERROR_PTR("naindex not made", __func__, NULL);
801
802 /* Build up sorted boxa using the sort index */
803 boxad = boxaSortByIndex(boxas, naindex);
804
805 if (pnaindex)
806 *pnaindex = naindex;
807 else
808 numaDestroy(&naindex);
809 return boxad;
810}
811
812
820BOXA *
821boxaSortByIndex(BOXA *boxas,
822 NUMA *naindex)
823{
824l_int32 i, n, index;
825BOX *box;
826BOXA *boxad;
827
828 if (!boxas)
829 return (BOXA *)ERROR_PTR("boxas not defined", __func__, NULL);
830 if ((n = boxaGetCount(boxas)) == 0) {
831 L_WARNING("boxas is empty\n", __func__);
832 return boxaCopy(boxas, L_COPY);
833 }
834 if (!naindex)
835 return (BOXA *)ERROR_PTR("naindex not defined", __func__, NULL);
836
837 boxad = boxaCreate(n);
838 for (i = 0; i < n; i++) {
839 numaGetIValue(naindex, i, &index);
840 box = boxaGetBox(boxas, index, L_COPY);
841 boxaAddBox(boxad, box, L_INSERT);
842 }
843
844 return boxad;
845}
846
847
895BOXAA *
896boxaSort2d(BOXA *boxas,
897 NUMAA **pnaad,
898 l_int32 delta1,
899 l_int32 delta2,
900 l_int32 minh1)
901{
902l_int32 i, index, h, nt, ne, n, m, ival;
903BOX *box;
904BOXA *boxa, *boxae, *boxan, *boxa1, *boxa2, *boxa3, *boxav, *boxavs;
905BOXAA *baa, *baa1, *baad;
906NUMA *naindex, *nae, *nan, *nah, *nav, *na1, *na2, *nad, *namap;
907NUMAA *naa, *naa1, *naad;
908
909 if (pnaad) *pnaad = NULL;
910 if (!boxas)
911 return (BOXAA *)ERROR_PTR("boxas not defined", __func__, NULL);
912 if (boxaGetCount(boxas) == 0)
913 return (BOXAA *)ERROR_PTR("boxas is empty", __func__, NULL);
914
915 /* Sort from left to right */
916 if ((boxa = boxaSort(boxas, L_SORT_BY_X, L_SORT_INCREASING, &naindex))
917 == NULL)
918 return (BOXAA *)ERROR_PTR("boxa not made", __func__, NULL);
919
920 /* First pass: assign taller boxes to boxa by row */
921 nt = boxaGetCount(boxa);
922 baa = boxaaCreate(0);
923 naa = numaaCreate(0);
924 boxae = boxaCreate(0); /* save small height boxes here */
925 nae = numaCreate(0); /* keep track of small height boxes */
926 for (i = 0; i < nt; i++) {
927 box = boxaGetBox(boxa, i, L_CLONE);
928 boxGetGeometry(box, NULL, NULL, NULL, &h);
929 if (h < minh1) { /* save for 2nd pass */
930 boxaAddBox(boxae, box, L_INSERT);
931 numaAddNumber(nae, i);
932 } else {
933 n = boxaaGetCount(baa);
934 boxaaAlignBox(baa, box, delta1, &index);
935 if (index < n) { /* append to an existing boxa */
936 boxaaAddBox(baa, index, box, L_INSERT);
937 } else { /* doesn't align, need new boxa */
938 boxan = boxaCreate(0);
939 boxaAddBox(boxan, box, L_INSERT);
940 boxaaAddBoxa(baa, boxan, L_INSERT);
941 nan = numaCreate(0);
942 numaaAddNuma(naa, nan, L_INSERT);
943 }
944 numaGetIValue(naindex, i, &ival);
945 numaaAddNumber(naa, index, ival);
946 }
947 }
948 boxaDestroy(&boxa);
949 numaDestroy(&naindex);
950
951 /* Second pass: feed in small height boxes */
952 ne = boxaGetCount(boxae);
953 for (i = 0; i < ne; i++) {
954 box = boxaGetBox(boxae, i, L_CLONE);
955 n = boxaaGetCount(baa);
956 boxaaAlignBox(baa, box, delta2, &index);
957 if (index < n) { /* append to an existing boxa */
958 boxaaAddBox(baa, index, box, L_INSERT);
959 } else { /* doesn't align, need new boxa */
960 boxan = boxaCreate(0);
961 boxaAddBox(boxan, box, L_INSERT);
962 boxaaAddBoxa(baa, boxan, L_INSERT);
963 nan = numaCreate(0);
964 numaaAddNuma(naa, nan, L_INSERT);
965 }
966 numaGetIValue(nae, i, &ival); /* location in original boxas */
967 numaaAddNumber(naa, index, ival);
968 }
969
970 /* Third pass: merge some boxa whose extent is overlapping.
971 * Think of these boxa as text lines, where the bounding boxes
972 * of the text lines can overlap, but likely won't have
973 * a huge overlap.
974 * First do a greedy find of pairs of overlapping boxa, where
975 * the two boxa overlap by at least 50% of the smaller, and
976 * the smaller is not more than half the area of the larger.
977 * For such pairs, call the larger one the primary boxa. The
978 * boxes in the smaller one are appended to those in the primary
979 * in pass 3a, and the primaries are extracted in pass 3b.
980 * In this way, all boxes in the original baa are saved. */
981 n = boxaaGetCount(baa);
982 boxaaGetExtent(baa, NULL, NULL, NULL, &boxa3);
983 boxa1 = boxaHandleOverlaps(boxa3, L_REMOVE_SMALL, 1000, 0.5, 0.5, &namap);
984 boxaDestroy(&boxa1);
985 boxaDestroy(&boxa3);
986 for (i = 0; i < n; i++) { /* Pass 3a: join selected copies of boxa */
987 numaGetIValue(namap, i, &ival);
988 if (ival >= 0) { /* join current to primary boxa[ival] */
989 boxa1 = boxaaGetBoxa(baa, i, L_COPY);
990 boxa2 = boxaaGetBoxa(baa, ival, L_CLONE);
991 boxaJoin(boxa2, boxa1, 0, -1);
992 boxaDestroy(&boxa2);
993 boxaDestroy(&boxa1);
994 na1 = numaaGetNuma(naa, i, L_COPY);
995 na2 = numaaGetNuma(naa, ival, L_CLONE);
996 numaJoin(na2, na1, 0, -1);
997 numaDestroy(&na1);
998 numaDestroy(&na2);
999 }
1000 }
1001 baa1 = boxaaCreate(n);
1002 naa1 = numaaCreate(n);
1003 for (i = 0; i < n; i++) { /* Pass 3b: save primary boxa */
1004 numaGetIValue(namap, i, &ival);
1005 if (ival == -1) {
1006 boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1007 boxaaAddBoxa(baa1, boxa1, L_INSERT);
1008 na1 = numaaGetNuma(naa, i, L_CLONE);
1009 numaaAddNuma(naa1, na1, L_INSERT);
1010 }
1011 }
1012 numaDestroy(&namap);
1013 boxaaDestroy(&baa);
1014 baa = baa1;
1015 numaaDestroy(&naa);
1016 naa = naa1;
1017
1018 /* Sort the boxes in each boxa horizontally */
1019 m = boxaaGetCount(baa);
1020 for (i = 0; i < m; i++) {
1021 boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1022 boxa2 = boxaSort(boxa1, L_SORT_BY_X, L_SORT_INCREASING, &nah);
1023 boxaaReplaceBoxa(baa, i, boxa2);
1024 na1 = numaaGetNuma(naa, i, L_CLONE);
1025 na2 = numaSortByIndex(na1, nah);
1026 numaaReplaceNuma(naa, i, na2);
1027 boxaDestroy(&boxa1);
1028 numaDestroy(&na1);
1029 numaDestroy(&nah);
1030 }
1031
1032 /* Sort the boxa vertically within boxaa, using the first box
1033 * in each boxa. */
1034 m = boxaaGetCount(baa);
1035 boxav = boxaCreate(m); /* holds first box in each boxa in baa */
1036 naad = numaaCreate(m);
1037 if (pnaad)
1038 *pnaad = naad;
1039 baad = boxaaCreate(m);
1040 for (i = 0; i < m; i++) {
1041 boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1042 box = boxaGetBox(boxa1, 0, L_CLONE);
1043 boxaAddBox(boxav, box, L_INSERT);
1044 boxaDestroy(&boxa1);
1045 }
1046 boxavs = boxaSort(boxav, L_SORT_BY_Y, L_SORT_INCREASING, &nav);
1047 for (i = 0; i < m; i++) {
1048 numaGetIValue(nav, i, &index);
1049 boxa = boxaaGetBoxa(baa, index, L_CLONE);
1050 boxaaAddBoxa(baad, boxa, L_INSERT);
1051 nad = numaaGetNuma(naa, index, L_CLONE);
1052 numaaAddNuma(naad, nad, L_INSERT);
1053 }
1054
1055
1056/* lept_stderr("box count = %d, numaa count = %d\n", nt,
1057 numaaGetNumberCount(naad)); */
1058
1059 boxaaDestroy(&baa);
1060 boxaDestroy(&boxav);
1061 boxaDestroy(&boxavs);
1062 boxaDestroy(&boxae);
1063 numaDestroy(&nav);
1064 numaDestroy(&nae);
1065 numaaDestroy(&naa);
1066 if (!pnaad)
1067 numaaDestroy(&naad);
1068
1069 return baad;
1070}
1071
1072
1080BOXAA *
1081boxaSort2dByIndex(BOXA *boxas,
1082 NUMAA *naa)
1083{
1084l_int32 ntot, boxtot, i, j, n, nn, index;
1085BOX *box;
1086BOXA *boxa;
1087BOXAA *baa;
1088NUMA *na;
1089
1090 if (!boxas)
1091 return (BOXAA *)ERROR_PTR("boxas not defined", __func__, NULL);
1092 if ((boxtot = boxaGetCount(boxas)) == 0)
1093 return (BOXAA *)ERROR_PTR("boxas is empty", __func__, NULL);
1094 if (!naa)
1095 return (BOXAA *)ERROR_PTR("naindex not defined", __func__, NULL);
1096
1097 /* Check counts */
1098 ntot = numaaGetNumberCount(naa);
1099 if (ntot != boxtot)
1100 return (BOXAA *)ERROR_PTR("element count mismatch", __func__, NULL);
1101
1102 n = numaaGetCount(naa);
1103 baa = boxaaCreate(n);
1104 for (i = 0; i < n; i++) {
1105 na = numaaGetNuma(naa, i, L_CLONE);
1106 nn = numaGetCount(na);
1107 boxa = boxaCreate(nn);
1108 for (j = 0; j < nn; j++) {
1109 numaGetIValue(na, i, &index);
1110 box = boxaGetBox(boxas, index, L_COPY);
1111 boxaAddBox(boxa, box, L_INSERT);
1112 }
1113 boxaaAddBoxa(baa, boxa, L_INSERT);
1114 numaDestroy(&na);
1115 }
1116
1117 return baa;
1118}
1119
1120
1121/*---------------------------------------------------------------------*
1122 * Boxa array extraction *
1123 *---------------------------------------------------------------------*/
1147l_ok
1148boxaExtractAsNuma(BOXA *boxa,
1149 NUMA **pnal,
1150 NUMA **pnat,
1151 NUMA **pnar,
1152 NUMA **pnab,
1153 NUMA **pnaw,
1154 NUMA **pnah,
1155 l_int32 keepinvalid)
1156{
1157l_int32 i, n, left, top, right, bot, w, h;
1158
1159 if (!pnal && !pnat && !pnar && !pnab && !pnaw && !pnah)
1160 return ERROR_INT("no output requested", __func__, 1);
1161 if (pnal) *pnal = NULL;
1162 if (pnat) *pnat = NULL;
1163 if (pnar) *pnar = NULL;
1164 if (pnab) *pnab = NULL;
1165 if (pnaw) *pnaw = NULL;
1166 if (pnah) *pnah = NULL;
1167 if (!boxa)
1168 return ERROR_INT("boxa not defined", __func__, 1);
1169 if (!keepinvalid && boxaGetValidCount(boxa) == 0)
1170 return ERROR_INT("no valid boxes", __func__, 1);
1171
1172 n = boxaGetCount(boxa);
1173 if (pnal) *pnal = numaCreate(n);
1174 if (pnat) *pnat = numaCreate(n);
1175 if (pnar) *pnar = numaCreate(n);
1176 if (pnab) *pnab = numaCreate(n);
1177 if (pnaw) *pnaw = numaCreate(n);
1178 if (pnah) *pnah = numaCreate(n);
1179 for (i = 0; i < n; i++) {
1180 boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1181 if (!keepinvalid && (w <= 0 || h <= 0))
1182 continue;
1183 right = left + w - 1;
1184 bot = top + h - 1;
1185 if (pnal) numaAddNumber(*pnal, left);
1186 if (pnat) numaAddNumber(*pnat, top);
1187 if (pnar) numaAddNumber(*pnar, right);
1188 if (pnab) numaAddNumber(*pnab, bot);
1189 if (pnaw) numaAddNumber(*pnaw, w);
1190 if (pnah) numaAddNumber(*pnah, h);
1191 }
1192
1193 return 0;
1194}
1195
1196
1226l_ok
1227boxaExtractAsPta(BOXA *boxa,
1228 PTA **pptal,
1229 PTA **pptat,
1230 PTA **pptar,
1231 PTA **pptab,
1232 PTA **pptaw,
1233 PTA **pptah,
1234 l_int32 keepinvalid)
1235{
1236l_int32 i, n, left, top, right, bot, w, h;
1237
1238 if (!pptal && !pptar && !pptat && !pptab && !pptaw && !pptah)
1239 return ERROR_INT("no output requested", __func__, 1);
1240 if (pptal) *pptal = NULL;
1241 if (pptat) *pptat = NULL;
1242 if (pptar) *pptar = NULL;
1243 if (pptab) *pptab = NULL;
1244 if (pptaw) *pptaw = NULL;
1245 if (pptah) *pptah = NULL;
1246 if (!boxa)
1247 return ERROR_INT("boxa not defined", __func__, 1);
1248 if (!keepinvalid && boxaGetValidCount(boxa) == 0)
1249 return ERROR_INT("no valid boxes", __func__, 1);
1250
1251 n = boxaGetCount(boxa);
1252 if (pptal) *pptal = ptaCreate(n);
1253 if (pptat) *pptat = ptaCreate(n);
1254 if (pptar) *pptar = ptaCreate(n);
1255 if (pptab) *pptab = ptaCreate(n);
1256 if (pptaw) *pptaw = ptaCreate(n);
1257 if (pptah) *pptah = ptaCreate(n);
1258 for (i = 0; i < n; i++) {
1259 boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1260 if (!keepinvalid && (w <= 0 || h <= 0))
1261 continue;
1262 right = left + w - 1;
1263 bot = top + h - 1;
1264 if (pptal) ptaAddPt(*pptal, i, left);
1265 if (pptat) ptaAddPt(*pptat, i, top);
1266 if (pptar) ptaAddPt(*pptar, i, right);
1267 if (pptab) ptaAddPt(*pptab, i, bot);
1268 if (pptaw) ptaAddPt(*pptaw, i, w);
1269 if (pptah) ptaAddPt(*pptah, i, h);
1270 }
1271
1272 return 0;
1273}
1274
1275
1294PTA *
1295boxaExtractCorners(BOXA *boxa,
1296 l_int32 loc)
1297{
1298l_int32 i, n, left, top, right, bot, w, h;
1299PTA *pta;
1300
1301 if (!boxa)
1302 return (PTA *)ERROR_PTR("boxa not defined", __func__, NULL);
1303 if (loc != L_UPPER_LEFT && loc != L_UPPER_RIGHT && loc != L_LOWER_LEFT &&
1304 loc != L_LOWER_RIGHT && loc != L_BOX_CENTER)
1305 return (PTA *)ERROR_PTR("invalid location", __func__, NULL);
1306
1307 n = boxaGetCount(boxa);
1308 if ((pta = ptaCreate(n)) == NULL)
1309 return (PTA *)ERROR_PTR("pta not made", __func__, NULL);
1310
1311 for (i = 0; i < n; i++) {
1312 boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
1313 right = left + w - 1;
1314 bot = top + h - 1;
1315 if (w == 0 || h == 0) { /* invalid */
1316 left = 0;
1317 top = 0;
1318 right = 0;
1319 bot = 0;
1320 }
1321 if (loc == L_UPPER_LEFT)
1322 ptaAddPt(pta, left, top);
1323 else if (loc == L_UPPER_RIGHT)
1324 ptaAddPt(pta, right, top);
1325 else if (loc == L_LOWER_LEFT)
1326 ptaAddPt(pta, left, bot);
1327 else if (loc == L_LOWER_RIGHT)
1328 ptaAddPt(pta, right, bot);
1329 else if (loc == L_BOX_CENTER)
1330 ptaAddPt(pta, (left + right) / 2, (top + bot) / 2);
1331 }
1332
1333 return pta;
1334}
1335
1336
1337/*---------------------------------------------------------------------*
1338 * Boxa statistics *
1339 *---------------------------------------------------------------------*/
1371l_ok
1372boxaGetRankVals(BOXA *boxa,
1373 l_float32 fract,
1374 l_int32 *px,
1375 l_int32 *py,
1376 l_int32 *pr,
1377 l_int32 *pb,
1378 l_int32 *pw,
1379 l_int32 *ph)
1380{
1381l_float32 xval, yval, rval, bval, wval, hval;
1382NUMA *nax, *nay, *nar, *nab, *naw, *nah;
1383
1384 if (px) *px = 0;
1385 if (py) *py = 0;
1386 if (pr) *pr = 0;
1387 if (pb) *pb = 0;
1388 if (pw) *pw = 0;
1389 if (ph) *ph = 0;
1390 if (!boxa)
1391 return ERROR_INT("boxa not defined", __func__, 1);
1392 if (fract < 0.0 || fract > 1.0)
1393 return ERROR_INT("fract not in [0.0 ... 1.0]", __func__, 1);
1394 if (boxaGetValidCount(boxa) == 0)
1395 return ERROR_INT("no valid boxes in boxa", __func__, 1);
1396
1397 /* Use only the valid boxes */
1398 boxaExtractAsNuma(boxa, &nax, &nay, &nar, &nab, &naw, &nah, 0);
1399
1400 if (px) {
1401 numaGetRankValue(nax, 1.0 - fract, NULL, 1, &xval);
1402 *px = (l_int32)xval;
1403 }
1404 if (py) {
1405 numaGetRankValue(nay, 1.0 - fract, NULL, 1, &yval);
1406 *py = (l_int32)yval;
1407 }
1408 if (pr) {
1409 numaGetRankValue(nar, fract, NULL, 1, &rval);
1410 *pr = (l_int32)rval;
1411 }
1412 if (pb) {
1413 numaGetRankValue(nab, fract, NULL, 1, &bval);
1414 *pb = (l_int32)bval;
1415 }
1416 if (pw) {
1417 numaGetRankValue(naw, fract, NULL, 1, &wval);
1418 *pw = (l_int32)wval;
1419 }
1420 if (ph) {
1421 numaGetRankValue(nah, fract, NULL, 1, &hval);
1422 *ph = (l_int32)hval;
1423 }
1424 numaDestroy(&nax);
1425 numaDestroy(&nay);
1426 numaDestroy(&nar);
1427 numaDestroy(&nab);
1428 numaDestroy(&naw);
1429 numaDestroy(&nah);
1430 return 0;
1431}
1432
1433
1451l_ok
1452boxaGetMedianVals(BOXA *boxa,
1453 l_int32 *px,
1454 l_int32 *py,
1455 l_int32 *pr,
1456 l_int32 *pb,
1457 l_int32 *pw,
1458 l_int32 *ph)
1459{
1460 if (!boxa)
1461 return ERROR_INT("boxa not defined", __func__, 1);
1462 if (boxaGetValidCount(boxa) == 0)
1463 return ERROR_INT("no valid boxes in boxa", __func__, 1);
1464
1465 return boxaGetRankVals(boxa, 0.5, px, py, pr, pb, pw, ph);
1466}
1467
1468
1477l_ok
1478boxaGetAverageSize(BOXA *boxa,
1479 l_float32 *pw,
1480 l_float32 *ph)
1481{
1482l_int32 i, n, bw, bh;
1483l_float32 sumw, sumh;
1484
1485 if (pw) *pw = 0.0;
1486 if (ph) *ph = 0.0;
1487 if (!boxa)
1488 return ERROR_INT("boxa not defined", __func__, 1);
1489 if ((n = boxaGetCount(boxa)) == 0)
1490 return ERROR_INT("boxa is empty", __func__, 1);
1491
1492 sumw = sumh = 0.0;
1493 for (i = 0; i < n; i++) {
1494 boxaGetBoxGeometry(boxa, i, NULL, NULL, &bw, &bh);
1495 sumw += bw;
1496 sumh += bh;
1497 }
1498
1499 if (pw) *pw = sumw / n;
1500 if (ph) *ph = sumh / n;
1501 return 0;
1502}
1503
1504
1505/*---------------------------------------------------------------------*
1506 * Other Boxaa functions *
1507 *---------------------------------------------------------------------*/
1530l_ok
1531boxaaGetExtent(BOXAA *baa,
1532 l_int32 *pw,
1533 l_int32 *ph,
1534 BOX **pbox,
1535 BOXA **pboxa)
1536{
1537l_int32 i, n, x, y, w, h, xmax, ymax, xmin, ymin, found;
1538BOX *box1;
1539BOXA *boxa, *boxa1;
1540
1541 if (!pw && !ph && !pbox && !pboxa)
1542 return ERROR_INT("no ptrs defined", __func__, 1);
1543 if (pw) *pw = 0;
1544 if (ph) *ph = 0;
1545 if (pbox) *pbox = NULL;
1546 if (pboxa) *pboxa = NULL;
1547 if (!baa)
1548 return ERROR_INT("baa not defined", __func__, 1);
1549
1550 n = boxaaGetCount(baa);
1551 if (n == 0)
1552 return ERROR_INT("no boxa in baa", __func__, 1);
1553
1554 boxa = boxaCreate(n);
1555 xmax = ymax = 0;
1556 xmin = ymin = 100000000;
1557 found = FALSE;
1558 for (i = 0; i < n; i++) {
1559 boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
1560 boxaGetExtent(boxa1, NULL, NULL, &box1);
1561 boxaDestroy(&boxa1);
1562 boxGetGeometry(box1, &x, &y, &w, &h);
1563 if (w > 0 && h > 0) { /* a valid extent box */
1564 found = TRUE; /* found at least one valid extent box */
1565 xmin = L_MIN(xmin, x);
1566 ymin = L_MIN(ymin, y);
1567 xmax = L_MAX(xmax, x + w);
1568 ymax = L_MAX(ymax, y + h);
1569 }
1570 boxaAddBox(boxa, box1, L_INSERT);
1571 }
1572 if (found == FALSE) /* no valid extent boxes */
1573 xmin = ymin = 0;
1574
1575 if (pw) *pw = xmax;
1576 if (ph) *ph = ymax;
1577 if (pbox)
1578 *pbox = boxCreate(xmin, ymin, xmax - xmin, ymax - ymin);
1579 if (pboxa)
1580 *pboxa = boxa;
1581 else
1582 boxaDestroy(&boxa);
1583 return 0;
1584}
1585
1586
1608BOXA *
1609boxaaFlattenToBoxa(BOXAA *baa,
1610 NUMA **pnaindex,
1611 l_int32 copyflag)
1612{
1613l_int32 i, j, m, n;
1614BOXA *boxa, *boxat;
1615BOX *box;
1616NUMA *naindex;
1617
1618 if (pnaindex) *pnaindex = NULL;
1619 if (!baa)
1620 return (BOXA *)ERROR_PTR("baa not defined", __func__, NULL);
1621 if (copyflag != L_COPY && copyflag != L_CLONE)
1622 return (BOXA *)ERROR_PTR("invalid copyflag", __func__, NULL);
1623 if (pnaindex) {
1624 naindex = numaCreate(0);
1625 *pnaindex = naindex;
1626 }
1627
1628 n = boxaaGetCount(baa);
1629 boxa = boxaCreate(n);
1630 for (i = 0; i < n; i++) {
1631 boxat = boxaaGetBoxa(baa, i, L_CLONE);
1632 m = boxaGetCount(boxat);
1633 if (m == 0) { /* placeholder box */
1634 box = boxCreate(0, 0, 0, 0);
1635 boxaAddBox(boxa, box, L_INSERT);
1636 if (pnaindex)
1637 numaAddNumber(naindex, i); /* save 'row' number */
1638 } else {
1639 for (j = 0; j < m; j++) {
1640 box = boxaGetBox(boxat, j, copyflag);
1641 boxaAddBox(boxa, box, L_INSERT);
1642 if (pnaindex)
1643 numaAddNumber(naindex, i); /* save 'row' number */
1644 }
1645 }
1646 boxaDestroy(&boxat);
1647 }
1648
1649 return boxa;
1650}
1651
1652
1672BOXA *
1673boxaaFlattenAligned(BOXAA *baa,
1674 l_int32 num,
1675 BOX *fillerbox,
1676 l_int32 copyflag)
1677{
1678l_int32 i, j, m, n, mval, nshort;
1679BOXA *boxat, *boxad;
1680BOX *box;
1681
1682 if (!baa)
1683 return (BOXA *)ERROR_PTR("baa not defined", __func__, NULL);
1684 if (copyflag != L_COPY && copyflag != L_CLONE)
1685 return (BOXA *)ERROR_PTR("invalid copyflag", __func__, NULL);
1686
1687 n = boxaaGetCount(baa);
1688 boxad = boxaCreate(n);
1689 for (i = 0; i < n; i++) {
1690 boxat = boxaaGetBoxa(baa, i, L_CLONE);
1691 m = boxaGetCount(boxat);
1692 mval = L_MIN(m, num);
1693 nshort = num - mval;
1694 for (j = 0; j < mval; j++) { /* take the first %num if possible */
1695 box = boxaGetBox(boxat, j, copyflag);
1696 boxaAddBox(boxad, box, L_INSERT);
1697 }
1698 for (j = 0; j < nshort; j++) { /* add fillers if necessary */
1699 if (fillerbox) {
1700 boxaAddBox(boxad, fillerbox, L_COPY);
1701 } else {
1702 box = boxCreate(0, 0, 0, 0); /* invalid placeholder box */
1703 boxaAddBox(boxad, box, L_INSERT);
1704 }
1705 }
1706 boxaDestroy(&boxat);
1707 }
1708
1709 return boxad;
1710}
1711
1712
1728BOXAA *
1729boxaEncapsulateAligned(BOXA *boxa,
1730 l_int32 num,
1731 l_int32 copyflag)
1732{
1733l_int32 i, j, n, nbaa, index;
1734BOX *box;
1735BOXA *boxat;
1736BOXAA *baa;
1737
1738 if (!boxa)
1739 return (BOXAA *)ERROR_PTR("boxa not defined", __func__, NULL);
1740 if (copyflag != L_COPY && copyflag != L_CLONE)
1741 return (BOXAA *)ERROR_PTR("invalid copyflag", __func__, NULL);
1742
1743 n = boxaGetCount(boxa);
1744 nbaa = n / num;
1745 if (num * nbaa != n)
1746 L_ERROR("inconsistent alignment: num doesn't divide n\n", __func__);
1747 baa = boxaaCreate(nbaa);
1748 for (i = 0, index = 0; i < nbaa; i++) {
1749 boxat = boxaCreate(num);
1750 for (j = 0; j < num; j++, index++) {
1751 box = boxaGetBox(boxa, index, copyflag);
1752 boxaAddBox(boxat, box, L_INSERT);
1753 }
1754 boxaaAddBoxa(baa, boxat, L_INSERT);
1755 }
1756
1757 return baa;
1758}
1759
1760
1780BOXAA *
1781boxaaTranspose(BOXAA *baas)
1782{
1783l_int32 i, j, ny, nb, nbox;
1784BOX *box;
1785BOXA *boxa;
1786BOXAA *baad;
1787
1788 if (!baas)
1789 return (BOXAA *)ERROR_PTR("baas not defined", __func__, NULL);
1790 if ((ny = boxaaGetCount(baas)) == 0)
1791 return (BOXAA *)ERROR_PTR("baas empty", __func__, NULL);
1792
1793 /* Make sure that each boxa in baas has the same number of boxes */
1794 for (i = 0; i < ny; i++) {
1795 if ((boxa = boxaaGetBoxa(baas, i, L_CLONE)) == NULL)
1796 return (BOXAA *)ERROR_PTR("baas is missing a boxa", __func__, NULL);
1797 nb = boxaGetCount(boxa);
1798 boxaDestroy(&boxa);
1799 if (i == 0)
1800 nbox = nb;
1801 else if (nb != nbox)
1802 return (BOXAA *)ERROR_PTR("boxa are not all the same size",
1803 __func__, NULL);
1804 }
1805
1806 /* baad[i][j] = baas[j][i] */
1807 baad = boxaaCreate(nbox);
1808 for (i = 0; i < nbox; i++) {
1809 boxa = boxaCreate(ny);
1810 for (j = 0; j < ny; j++) {
1811 box = boxaaGetBox(baas, j, i, L_COPY);
1812 boxaAddBox(boxa, box, L_INSERT);
1813 }
1814 boxaaAddBoxa(baad, boxa, L_INSERT);
1815 }
1816 return baad;
1817}
1818
1819
1837l_ok
1838boxaaAlignBox(BOXAA *baa,
1839 BOX *box,
1840 l_int32 delta,
1841 l_int32 *pindex)
1842{
1843l_int32 i, n, m, y, yt, h, ht, ovlp, maxovlp, maxindex;
1844BOX *boxt;
1845BOXA *boxa;
1846
1847 if (pindex) *pindex = 0;
1848 if (!baa)
1849 return ERROR_INT("baa not defined", __func__, 1);
1850 if (!box)
1851 return ERROR_INT("box not defined", __func__, 1);
1852 if (!pindex)
1853 return ERROR_INT("&index not defined", __func__, 1);
1854
1855 n = boxaaGetCount(baa);
1856 boxGetGeometry(box, NULL, &y, NULL, &h);
1857 maxovlp = -10000000;
1858 for (i = 0; i < n; i++) {
1859 boxa = boxaaGetBoxa(baa, i, L_CLONE);
1860 if ((m = boxaGetCount(boxa)) == 0) {
1861 boxaDestroy(&boxa);
1862 L_WARNING("no boxes in boxa\n", __func__);
1863 continue;
1864 }
1865 boxaGetExtent(boxa, NULL, NULL, &boxt);
1866 boxGetGeometry(boxt, NULL, &yt, NULL, &ht);
1867 boxDestroy(&boxt);
1868 boxaDestroy(&boxa);
1869
1870 /* Overlap < 0 means the components do not overlap vertically */
1871 if (yt >= y)
1872 ovlp = y + h - 1 - yt;
1873 else
1874 ovlp = yt + ht - 1 - y;
1875 if (ovlp > maxovlp) {
1876 maxovlp = ovlp;
1877 maxindex = i;
1878 }
1879 }
1880
1881 if (maxovlp + delta >= 0)
1882 *pindex = maxindex;
1883 else
1884 *pindex = n;
1885 return 0;
1886}
boxaaFlattenToBoxa
BOXA * boxaaFlattenToBoxa(BOXAA *baa, NUMA **pnaindex, l_int32 copyflag)
boxaaFlattenToBoxa()
Definition: boxfunc2.c:1609
boxaaAlignBox
l_ok boxaaAlignBox(BOXAA *baa, BOX *box, l_int32 delta, l_int32 *pindex)
boxaaAlignBox()
Definition: boxfunc2.c:1838
boxaGetRankVals
l_ok boxaGetRankVals(BOXA *boxa, l_float32 fract, l_int32 *px, l_int32 *py, l_int32 *pr, l_int32 *pb, l_int32 *pw, l_int32 *ph)
boxaGetRankVals()
Definition: boxfunc2.c:1372
boxaTransformOrdered
BOXA * boxaTransformOrdered(BOXA *boxas, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley, l_int32 xcen, l_int32 ycen, l_float32 angle, l_int32 order)
boxaTransformOrdered()
Definition: boxfunc2.c:203
boxaShiftWithPta
BOXA * boxaShiftWithPta(BOXA *boxas, PTA *pta, l_int32 dir)
boxaShiftWithPta()
Definition: boxfunc2.c:566
boxaaGetExtent
l_ok boxaaGetExtent(BOXAA *baa, l_int32 *pw, l_int32 *ph, BOX **pbox, BOXA **pboxa)
boxaaGetExtent()
Definition: boxfunc2.c:1531
boxaaTranspose
BOXAA * boxaaTranspose(BOXAA *baas)
boxaaTranspose()
Definition: boxfunc2.c:1781
boxaEncapsulateAligned
BOXAA * boxaEncapsulateAligned(BOXA *boxa, l_int32 num, l_int32 copyflag)
boxaEncapsulateAligned()
Definition: boxfunc2.c:1729
boxRotateOrth
BOX * boxRotateOrth(BOX *box, l_int32 w, l_int32 h, l_int32 rotation)
boxRotateOrth()
Definition: boxfunc2.c:513
boxaRotateOrth
BOXA * boxaRotateOrth(BOXA *boxas, l_int32 w, l_int32 h, l_int32 rotation)
boxaRotateOrth()
Definition: boxfunc2.c:463
boxTransform
BOX * boxTransform(BOX *box, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley)
boxTransform()
Definition: boxfunc2.c:151
boxaBinSort
BOXA * boxaBinSort(BOXA *boxas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
boxaBinSort()
Definition: boxfunc2.c:746
boxaGetMedianVals
l_ok boxaGetMedianVals(BOXA *boxa, l_int32 *px, l_int32 *py, l_int32 *pr, l_int32 *pb, l_int32 *pw, l_int32 *ph)
boxaGetMedianVals()
Definition: boxfunc2.c:1452
boxaGetAverageSize
l_ok boxaGetAverageSize(BOXA *boxa, l_float32 *pw, l_float32 *ph)
boxaGetAverageSize()
Definition: boxfunc2.c:1478
boxTransformOrdered
BOX * boxTransformOrdered(BOX *boxs, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley, l_int32 xcen, l_int32 ycen, l_float32 angle, l_int32 order)
boxTransformOrdered()
Definition: boxfunc2.c:291
boxaExtractCorners
PTA * boxaExtractCorners(BOXA *boxa, l_int32 loc)
boxaExtractCorners()
Definition: boxfunc2.c:1295
boxaTransform
BOXA * boxaTransform(BOXA *boxas, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley)
boxaTransform()
Definition: boxfunc2.c:103
boxaSortByIndex
BOXA * boxaSortByIndex(BOXA *boxas, NUMA *naindex)
boxaSortByIndex()
Definition: boxfunc2.c:821
boxaSort
BOXA * boxaSort(BOXA *boxas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
boxaSort()
Definition: boxfunc2.c:624
boxaSort2dByIndex
BOXAA * boxaSort2dByIndex(BOXA *boxas, NUMAA *naa)
boxaSort2dByIndex()
Definition: boxfunc2.c:1081
boxaExtractAsPta
l_ok boxaExtractAsPta(BOXA *boxa, PTA **pptal, PTA **pptat, PTA **pptar, PTA **pptab, PTA **pptaw, PTA **pptah, l_int32 keepinvalid)
boxaExtractAsPta()
Definition: boxfunc2.c:1227
boxaSort2d
BOXAA * boxaSort2d(BOXA *boxas, NUMAA **pnaad, l_int32 delta1, l_int32 delta2, l_int32 minh1)
boxaSort2d()
Definition: boxfunc2.c:896
boxaExtractAsNuma
l_ok boxaExtractAsNuma(BOXA *boxa, NUMA **pnal, NUMA **pnat, NUMA **pnar, NUMA **pnab, NUMA **pnaw, NUMA **pnah, l_int32 keepinvalid)
boxaExtractAsNuma()
Definition: boxfunc2.c:1148
boxaaFlattenAligned
BOXA * boxaaFlattenAligned(BOXAA *baa, l_int32 num, BOX *fillerbox, l_int32 copyflag)
boxaaFlattenAligned()
Definition: boxfunc2.c:1673
L_SORT_BY_AREA
@ L_SORT_BY_AREA
Definition: pix.h:537
L_SORT_BY_MIN_DIMENSION
@ L_SORT_BY_MIN_DIMENSION
Definition: pix.h:534
L_SORT_BY_PERIMETER
@ L_SORT_BY_PERIMETER
Definition: pix.h:536
L_SORT_BY_WIDTH
@ L_SORT_BY_WIDTH
Definition: pix.h:532
L_SORT_BY_RIGHT
@ L_SORT_BY_RIGHT
Definition: pix.h:530
L_SORT_BY_BOT
@ L_SORT_BY_BOT
Definition: pix.h:531
L_SORT_BY_ASPECT_RATIO
@ L_SORT_BY_ASPECT_RATIO
Definition: pix.h:538
L_SORT_BY_HEIGHT
@ L_SORT_BY_HEIGHT
Definition: pix.h:533
L_SORT_BY_MAX_DIMENSION
@ L_SORT_BY_MAX_DIMENSION
Definition: pix.h:535
L_SORT_BY_Y
@ L_SORT_BY_Y
Definition: pix.h:529
L_SORT_BY_X
@ L_SORT_BY_X
Definition: pix.h:528
L_COPY
@ L_COPY
Definition: pix.h:505
L_CLONE
@ L_CLONE
Definition: pix.h:506
L_INSERT
@ L_INSERT
Definition: pix.h:504
L_UPPER_RIGHT
@ L_UPPER_RIGHT
Definition: pix.h:910
L_LOWER_RIGHT
@ L_LOWER_RIGHT
Definition: pix.h:912
L_UPPER_LEFT
@ L_UPPER_LEFT
Definition: pix.h:909
L_BOX_CENTER
@ L_BOX_CENTER
Definition: pix.h:913
L_LOWER_LEFT
@ L_LOWER_LEFT
Definition: pix.h:911
L_REMOVE_SMALL
@ L_REMOVE_SMALL
Definition: pix.h:881
L_SORT_DECREASING
@ L_SORT_DECREASING
Definition: pix.h:523
L_SORT_INCREASING
@ L_SORT_INCREASING
Definition: pix.h:522
L_RO_TR_SC
@ L_RO_TR_SC
Definition: pix.h:679
L_TR_RO_SC
@ L_TR_RO_SC
Definition: pix.h:680
L_SC_RO_TR
@ L_SC_RO_TR
Definition: pix.h:678
L_TR_SC_RO
@ L_TR_SC_RO
Definition: pix.h:677
L_SC_TR_RO
@ L_SC_TR_RO
Definition: pix.h:682
L_RO_SC_TR
@ L_RO_SC_TR
Definition: pix.h:681
pix_internal.h
Box::y
l_int32 y
Definition: pix_internal.h:258
Box::x
l_int32 x
Definition: pix_internal.h:257
Box::w
l_int32 w
Definition: pix_internal.h:259
Box::h
l_int32 h
Definition: pix_internal.h:260