/*====================================================================*
- Copyright (C) 2001 Leptonica. All rights reserved.
- This software is distributed in the hope that it will be
- useful, but with NO WARRANTY OF ANY KIND.
- No author or distributor accepts responsibility to anyone for the
- consequences of using this software, or for whether it serves any
- particular purpose or works at all, unless he or she says so in
- writing. Everyone is granted permission to copy, modify and
- redistribute this source code, for commercial or non-commercial
- purposes, with the following restrictions: (1) the origin of this
- source code must not be misrepresented; (2) modified versions must
- be plainly marked as such; and (3) this notice may not be removed
- or altered from any source or modified source distribution.
*====================================================================*/
/*
* boxfunc2.c
*
* Boxa/Box transform (shift, scale) and orthogonal rotation
* BOXA *boxaTransform()
* BOX *boxTransform()
* BOXA *boxaTransformOrdered()
* BOX *boxTransformOrdered()
* BOXA *boxaRotateOrth()
* BOX *boxRotateOrth()
*
* Boxa sort
* BOXA *boxaSort()
* BOXA *boxaBinSort()
* BOXA *boxaSortByIndex()
* BOXAA *boxaSort2d()
* BOXAA *boxaSort2dByIndex()
*
* Other boxaa functions
* l_int32 boxaaGetExtent()
* BOXA *boxaaFlattenToBoxa()
* l_int32 boxaaAlignBox()
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "allheaders.h"
/* For more than this number of c.c. in a binarized image of
* semi-perimeter (w + h) about 5000 or less, the O(n) binsort
* is faster than the O(nlogn) shellsort. */
static const l_int32 MIN_COMPS_FOR_BIN_SORT = 500;
/*---------------------------------------------------------------------*
* Boxa/Box transform (shift, scale) and orthogonal rotation *
*---------------------------------------------------------------------*/
/*!
* boxaTransform()
*
* Input: boxa
* shiftx, shifty
* scalex, scaley
* Return: boxad, or null on error
*
* Notes:
* (1) This is a very simple function that first shifts, then scales.
*/
BOXA *
boxaTransform(BOXA *boxas,
l_int32 shiftx,
l_int32 shifty,
l_float32 scalex,
l_float32 scaley)
{
l_int32 i, n;
BOX *boxs, *boxd;
BOXA *boxad;
PROCNAME("boxaTransform");
if (!boxas)
return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
n = boxaGetCount(boxas);
if ((boxad = boxaCreate(n)) == NULL)
return (BOXA *)ERROR_PTR("boxad not made", procName, NULL);
for (i = 0; i < n; i++) {
if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL)
return (BOXA *)ERROR_PTR("boxs not found", procName, NULL);
boxd = boxTransform(boxs, shiftx, shifty, scalex, scaley);
boxDestroy(&boxs);
boxaAddBox(boxad, boxd, L_INSERT);
}
return boxad;
}
/*!
* boxTransform()
*
* Input: box
* shiftx, shifty
* scalex, scaley
* Return: boxd, or null on error
*
* Notes:
* (1) This is a very simple function that first shifts, then scales.
*/
BOX *
boxTransform(BOX *box,
l_int32 shiftx,
l_int32 shifty,
l_float32 scalex,
l_float32 scaley)
{
PROCNAME("boxTransform");
if (!box)
return (BOX *)ERROR_PTR("box not defined", procName, NULL);
return boxCreate((l_int32)(scalex * (box->x + shiftx) + 0.5),
(l_int32)(scaley * (box->y + shifty) + 0.5),
(l_int32)(L_MAX(1.0, scalex * box->w + 0.5)),
(l_int32)(L_MAX(1.0, scaley * box->h + 0.5)));
}
/*!
* boxaTransformOrdered()
*
* Input: boxa
* shiftx, shifty
* scalex, scaley
* xcen, ycen (center of rotation)
* angle (in radians; clockwise is positive)
* order (one of 6 combinations: L_TR_SC_RO, ...)
* Return: boxd, or null on error
*
* Notes:
* (1) This allows a sequence of linear transforms on each box.
* the transforms are from the affine set, composed of
* shift, scaling and rotation, and the order of the
* transforms is specified.
* (2) Although these operations appear to be on an infinite
* 2D plane, in practice the region of interest is clipped
* to a finite image. The center of rotation is usually taken
* with respect to the image (either the UL corner or the
* center). A translation can have two very different effects:
* (a) Moves the boxes across the fixed image region.
* (b) Moves the image origin, causing a change in the image
* region and an opposite effective translation of the boxes.
* This function should only be used for (a), where the image
* region is fixed on translation. If the image region is
* changed by the translation, use instead the functions
* in affinecompose.c, where the image region and rotation
* center can be computed from the actual clipping due to
* translation of the image origin.
* (3) See boxTransformOrdered() for usage and implementation details.
*/
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)
{
l_int32 i, n;
BOX *boxs, *boxd;
BOXA *boxad;
PROCNAME("boxaTransformOrdered");
if (!boxas)
return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
n = boxaGetCount(boxas);
if ((boxad = boxaCreate(n)) == NULL)
return (BOXA *)ERROR_PTR("boxad not made", procName, NULL);
for (i = 0; i < n; i++) {
if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL)
return (BOXA *)ERROR_PTR("boxs not found", procName, NULL);
boxd = boxTransformOrdered(boxs, shiftx, shifty, scalex, scaley,
xcen, ycen, angle, order);
boxDestroy(&boxs);
boxaAddBox(boxad, boxd, L_INSERT);
}
return boxad;
}
/*!
* boxTransformOrdered()
*
* Input: boxs
* shiftx, shifty
* scalex, scaley
* xcen, ycen (center of rotation)
* angle (in radians; clockwise is positive)
* order (one of 6 combinations: L_TR_SC_RO, ...)
* Return: boxd, or null on error
*
* Notes:
* (1) This allows a sequence of linear transforms, composed of
* shift, scaling and rotation, where the order of the
* transforms is specified.
* (2) The rotation is taken about a point specified by (xcen, ycen).
* Let the components of the vector from the center of rotation
* to the box center be (xdif, ydif):
* xdif = (bx + 0.5 * bw) - xcen
* ydif = (by + 0.5 * bh) - ycen
* Then the box center after rotation has new components:
* bxcen = xcen + xdif * cosa + ydif * sina
* bycen = ycen + ydif * cosa - xdif * sina
* where cosa and sina are the cos and sin of the angle,
* and the enclosing box for the rotated box has size:
* rw = |bw * cosa| + |bh * sina|
* rh = |bh * cosa| + |bw * sina|
* where bw and bh are the unrotated width and height.
* Then the box UL corner (rx, ry) is
* rx = bxcen - 0.5 * rw
* ry = bycen - 0.5 * rh
* (3) The center of rotation specified by args @xcen and @ycen
* is the point BEFORE any translation or scaling. If the
* rotation is not the first operation, this function finds
* the actual center at the time of rotation. It does this
* by making the following assumptions:
* (1) Any scaling is with respect to the UL corner, so
* that the center location scales accordingly.
* (2) A translation does not affect the center of
* the image; it just moves the boxes.
* We always use assumption (1). However, assumption (2)
* will be incorrect if the apparent translation is due
* to a clipping operation that, in effect, moves the
* origin of the image. In that case, you should NOT use
* these simple functions. Instead, use the functions
* in affinecompose.c, where the rotation center can be
* computed from the actual clipping due to translation
* of the image origin.
*/
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)
{
l_int32 bx, by, bw, bh, tx, ty, tw, th;
l_int32 xcent, ycent; /* transformed center of rotation due to scaling */
l_float32 sina, cosa, xdif, ydif, rx, ry, rw, rh;
BOX *boxd;
PROCNAME("boxTransformOrdered");
if (!boxs)
return (BOX *)ERROR_PTR("boxs not defined", procName, NULL);
if (order != L_TR_SC_RO && order != L_SC_RO_TR && order != L_RO_TR_SC &&
order != L_TR_RO_SC && order != L_RO_SC_TR && order != L_SC_TR_RO)
return (BOX *)ERROR_PTR("order invalid", procName, NULL);
boxGetGeometry(boxs, &bx, &by, &bw, &bh);
if (angle != 0.0) {
sina = sin(angle);
cosa = cos(angle);
}
if (order == L_TR_SC_RO) {
tx = (l_int32)(scalex * (bx + shiftx) + 0.5);
ty = (l_int32)(scaley * (by + shifty) + 0.5);
tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
xcent = (l_int32)(scalex * xcen + 0.5);
ycent = (l_int32)(scaley * ycen + 0.5);
if (angle == 0.0)
boxd = boxCreate(tx, ty, tw, th);
else {
xdif = tx + 0.5 * tw - xcent;
ydif = ty + 0.5 * th - ycent;
rw = L_ABS(tw * cosa) + L_ABS(th * sina);
rh = L_ABS(th * cosa) + L_ABS(tw * sina);
rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
boxd = boxCreate((l_int32)rx, (l_int32)ry, (l_int32)rw,
(l_int32)rh);
}
}
else if (order == L_SC_TR_RO) {
tx = (l_int32)(scalex * bx + shiftx + 0.5);
ty = (l_int32)(scaley * by + shifty + 0.5);
tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
xcent = (l_int32)(scalex * xcen + 0.5);
ycent = (l_int32)(scaley * ycen + 0.5);
if (angle == 0.0)
boxd = boxCreate(tx, ty, tw, th);
else {
xdif = tx + 0.5 * tw - xcent;
ydif = ty + 0.5 * th - ycent;
rw = L_ABS(tw * cosa) + L_ABS(th * sina);
rh = L_ABS(th * cosa) + L_ABS(tw * sina);
rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
boxd = boxCreate((l_int32)rx, (l_int32)ry, (l_int32)rw,
(l_int32)rh);
}
}
else if (order == L_RO_TR_SC) {
if (angle == 0.0) {
rx = bx;
ry = by;
rw = bw;
rh = bh;
}
else {
xdif = bx + 0.5 * bw - xcen;
ydif = by + 0.5 * bh - ycen;
rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
}
tx = (l_int32)(scalex * (rx + shiftx) + 0.5);
ty = (l_int32)(scaley * (ry + shifty) + 0.5);
tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
boxd = boxCreate(tx, ty, tw, th);
}
else if (order == L_RO_SC_TR) {
if (angle == 0.0) {
rx = bx;
ry = by;
rw = bw;
rh = bh;
}
else {
xdif = bx + 0.5 * bw - xcen;
ydif = by + 0.5 * bh - ycen;
rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
}
tx = (l_int32)(scalex * rx + shiftx + 0.5);
ty = (l_int32)(scaley * ry + shifty + 0.5);
tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
boxd = boxCreate(tx, ty, tw, th);
}
else if (order == L_TR_RO_SC) {
tx = bx + shiftx;
ty = by + shifty;
if (angle == 0.0) {
rx = tx;
ry = ty;
rw = bw;
rh = bh;
}
else {
xdif = tx + 0.5 * bw - xcen;
ydif = ty + 0.5 * bh - ycen;
rw = L_ABS(bw * cosa) + L_ABS(bh * sina);
rh = L_ABS(bh * cosa) + L_ABS(bw * sina);
rx = xcen + xdif * cosa - ydif * sina - 0.5 * rw;
ry = ycen + ydif * cosa + xdif * sina - 0.5 * rh;
}
tx = (l_int32)(scalex * rx + 0.5);
ty = (l_int32)(scaley * ry + 0.5);
tw = (l_int32)(L_MAX(1.0, scalex * rw + 0.5));
th = (l_int32)(L_MAX(1.0, scaley * rh + 0.5));
boxd = boxCreate(tx, ty, tw, th);
}
else { /* order == L_SC_RO_TR) */
tx = (l_int32)(scalex * bx + 0.5);
ty = (l_int32)(scaley * by + 0.5);
tw = (l_int32)(L_MAX(1.0, scalex * bw + 0.5));
th = (l_int32)(L_MAX(1.0, scaley * bh + 0.5));
xcent = (l_int32)(scalex * xcen + 0.5);
ycent = (l_int32)(scaley * ycen + 0.5);
if (angle == 0.0) {
rx = tx;
ry = ty;
rw = tw;
rh = th;
}
else {
xdif = tx + 0.5 * tw - xcent;
ydif = ty + 0.5 * th - ycent;
rw = L_ABS(tw * cosa) + L_ABS(th * sina);
rh = L_ABS(th * cosa) + L_ABS(tw * sina);
rx = xcent + xdif * cosa - ydif * sina - 0.5 * rw;
ry = ycent + ydif * cosa + xdif * sina - 0.5 * rh;
}
tx = (l_int32)(rx + shiftx + 0.5);
ty = (l_int32)(ry + shifty + 0.5);
tw = (l_int32)(rw + 0.5);
th = (l_int32)(rh + 0.5);
boxd = boxCreate(tx, ty, tw, th);
}
return boxd;
}
/*!
* boxaRotateOrth()
*
* Input: boxa
* w, h (of image in which the boxa is embedded)
* rotation (0 = noop, 1 = 90 deg, 2 = 180 deg, 3 = 270 deg;
* all rotations are clockwise)
* Return: boxad, or null on error
*
* Notes:
* (1) See boxRotateOrth() for details.
*/
BOXA *
boxaRotateOrth(BOXA *boxas,
l_int32 w,
l_int32 h,
l_int32 rotation)
{
l_int32 i, n;
BOX *boxs, *boxd;
BOXA *boxad;
PROCNAME("boxaRotateOrth");
if (!boxas)
return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
if (rotation == 0)
return boxaCopy(boxas, L_COPY);
if (rotation < 1 || rotation > 3)
return (BOXA *)ERROR_PTR("rotation not in {0,1,2,3}", procName, NULL);
n = boxaGetCount(boxas);
if ((boxad = boxaCreate(n)) == NULL)
return (BOXA *)ERROR_PTR("boxad not made", procName, NULL);
for (i = 0; i < n; i++) {
if ((boxs = boxaGetBox(boxas, i, L_CLONE)) == NULL)
return (BOXA *)ERROR_PTR("boxs not found", procName, NULL);
boxd = boxRotateOrth(boxs, w, h, rotation);
boxDestroy(&boxs);
boxaAddBox(boxad, boxd, L_INSERT);
}
return boxad;
}
/*!
* boxRotateOrth()
*
* Input: box
* w, h (of image in which the box is embedded)
* rotation (0 = noop, 1 = 90 deg, 2 = 180 deg, 3 = 270 deg;
* all rotations are clockwise)
* Return: boxd, or null on error
*
* Notes:
* (1) Rotate the image with the embedded box by the specified amount.
* (2) After rotation, the rotated box is always measured with
* respect to the UL corner of the image.
*/
BOX *
boxRotateOrth(BOX *box,
l_int32 w,
l_int32 h,
l_int32 rotation)
{
l_int32 bx, by, bw, bh, xdist, ydist;
PROCNAME("boxRotateOrth");
if (!box)
return (BOX *)ERROR_PTR("box not defined", procName, NULL);
if (rotation == 0)
return boxCopy(box);
if (rotation < 1 || rotation > 3)
return (BOX *)ERROR_PTR("rotation not in {0,1,2,3}", procName, NULL);
boxGetGeometry(box, &bx, &by, &bw, &bh);
ydist = h - by - bh; /* below box */
xdist = w - bx - bw; /* to right of box */
if (rotation == 1) /* 90 deg cw */
return boxCreate(ydist, bx, bh, bw);
else if (rotation == 2) /* 180 deg cw */
return boxCreate(xdist, ydist, bw, bh);
else /* rotation == 3, 270 deg cw */
return boxCreate(by, xdist, bh, bw);
}
/*---------------------------------------------------------------------*
* Boxa sort *
*---------------------------------------------------------------------*/
/*!
* boxaSort()
*
* Input: boxa
* sorttype (L_SORT_BY_X, L_SORT_BY_Y, L_SORT_BY_WIDTH,
* L_SORT_BY_HEIGHT, L_SORT_BY_MIN_DIMENSION,
* L_SORT_BY_MAX_DIMENSION, L_SORT_BY_PERIMETER,
* L_SORT_BY_AREA, L_SORT_BY_ASPECT_RATIO)
* sortorder (L_SORT_INCREASING, L_SORT_DECREASING)
* &naindex (<optional return> index of sorted order into
* original array)
* Return: boxad (sorted version of boxas), or null on error
*/
BOXA *
boxaSort(BOXA *boxas,
l_int32 sorttype,
l_int32 sortorder,
NUMA **pnaindex)
{
l_int32 i, n, x, y, w, h, size;
BOXA *boxad;
NUMA *na, *naindex;
PROCNAME("boxaSort");
if (pnaindex) *pnaindex = NULL;
if (!boxas)
return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
sorttype != L_SORT_BY_WIDTH && sorttype != L_SORT_BY_HEIGHT &&
sorttype != L_SORT_BY_MIN_DIMENSION &&
sorttype != L_SORT_BY_MAX_DIMENSION &&
sorttype != L_SORT_BY_PERIMETER &&
sorttype != L_SORT_BY_AREA &&
sorttype != L_SORT_BY_ASPECT_RATIO)
return (BOXA *)ERROR_PTR("invalid sort type", procName, NULL);
if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
return (BOXA *)ERROR_PTR("invalid sort order", procName, NULL);
/* Use O(n) binsort if possible */
n = boxaGetCount(boxas);
if (n > MIN_COMPS_FOR_BIN_SORT &&
((sorttype == L_SORT_BY_X) || (sorttype == L_SORT_BY_Y) ||
(sorttype == L_SORT_BY_WIDTH) || (sorttype == L_SORT_BY_HEIGHT) ||
(sorttype == L_SORT_BY_PERIMETER)))
return boxaBinSort(boxas, sorttype, sortorder, pnaindex);
/* Build up numa of specific data */
if ((na = numaCreate(n)) == NULL)
return (BOXA *)ERROR_PTR("na not made", procName, NULL);
for (i = 0; i < n; i++) {
boxaGetBoxGeometry(boxas, i, &x, &y, &w, &h);
switch (sorttype)
{
case L_SORT_BY_X:
numaAddNumber(na, x);
break;
case L_SORT_BY_Y:
numaAddNumber(na, y);
break;
case L_SORT_BY_WIDTH:
numaAddNumber(na, w);
break;
case L_SORT_BY_HEIGHT:
numaAddNumber(na, h);
break;
case L_SORT_BY_MIN_DIMENSION:
size = L_MIN(w, h);
numaAddNumber(na, size);
break;
case L_SORT_BY_MAX_DIMENSION:
size = L_MAX(w, h);
numaAddNumber(na, size);
break;
case L_SORT_BY_PERIMETER:
size = w + h;
numaAddNumber(na, size);
break;
case L_SORT_BY_AREA:
size = w * h;
numaAddNumber(na, size);
break;
case L_SORT_BY_ASPECT_RATIO:
numaAddNumber(na, (l_float32)w / (l_float32)h);
break;
default:
L_WARNING("invalid sort type", procName);
}
}
/* Get the sort index for data array */
if ((naindex = numaGetSortIndex(na, sortorder)) == NULL)
return (BOXA *)ERROR_PTR("naindex not made", procName, NULL);
/* Build up sorted boxa using sort index */
boxad = boxaSortByIndex(boxas, naindex);
if (pnaindex)
*pnaindex = naindex;
else
numaDestroy(&naindex);
numaDestroy(&na);
return boxad;
}
/*!
* boxaBinSort()
*
* Input: boxa
* sorttype (L_SORT_BY_X, L_SORT_BY_Y, L_SORT_BY_WIDTH,
* L_SORT_BY_HEIGHT, L_SORT_BY_PERIMETER)
* sortorder (L_SORT_INCREASING, L_SORT_DECREASING)
* &naindex (<optional return> index of sorted order into
* original array)
* Return: boxad (sorted version of boxas), or null on error
*
* Notes:
* (1) For a large number of boxes (say, greater than 1000), this
* O(n) binsort is much faster than the O(nlogn) shellsort.
* For 5000 components, this is over 20x faster than boxaSort().
* (2) Consequently, boxaSort() calls this function if it will
* likely go much faster.
*/
BOXA *
boxaBinSort(BOXA *boxas,
l_int32 sorttype,
l_int32 sortorder,
NUMA **pnaindex)
{
l_int32 i, n, x, y, w, h;
BOXA *boxad;
NUMA *na, *naindex;
PROCNAME("boxaBinSort");
if (pnaindex) *pnaindex = NULL;
if (!boxas)
return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
sorttype != L_SORT_BY_WIDTH && sorttype != L_SORT_BY_HEIGHT &&
sorttype != L_SORT_BY_PERIMETER)
return (BOXA *)ERROR_PTR("invalid sort type", procName, NULL);
if (sortorder != L_SORT_INCREASING && sortorder != L_SORT_DECREASING)
return (BOXA *)ERROR_PTR("invalid sort order", procName, NULL);
/* Generate Numa of appropriate box dimensions */
n = boxaGetCount(boxas);
if ((na = numaCreate(n)) == NULL)
return (BOXA *)ERROR_PTR("na not made", procName, NULL);
for (i = 0; i < n; i++) {
boxaGetBoxGeometry(boxas, i, &x, &y, &w, &h);
switch (sorttype)
{
case L_SORT_BY_X:
numaAddNumber(na, x);
break;
case L_SORT_BY_Y:
numaAddNumber(na, y);
break;
case L_SORT_BY_WIDTH:
numaAddNumber(na, w);
break;
case L_SORT_BY_HEIGHT:
numaAddNumber(na, h);
break;
case L_SORT_BY_PERIMETER:
numaAddNumber(na, w + h);
break;
default:
L_WARNING("invalid sort type", procName);
}
}
/* Get the sort index for data array */
if ((naindex = numaGetBinSortIndex(na, sortorder)) == NULL)
return (BOXA *)ERROR_PTR("naindex not made", procName, NULL);
/* Build up sorted boxa using the sort index */
boxad = boxaSortByIndex(boxas, naindex);
if (pnaindex)
*pnaindex = naindex;
else
numaDestroy(&naindex);
numaDestroy(&na);
return boxad;
}
/*!
* boxaSortByIndex()
*
* Input: boxas
* naindex (na that maps from the new boxa to the input boxa)
* Return: boxad (sorted), or null on error
*/
BOXA *
boxaSortByIndex(BOXA *boxas,
NUMA *naindex)
{
l_int32 i, n, index;
BOX *box;
BOXA *boxad;
PROCNAME("boxaSortByIndex");
if (!boxas)
return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
if (!naindex)
return (BOXA *)ERROR_PTR("naindex not defined", procName, NULL);
n = boxaGetCount(boxas);
boxad = boxaCreate(n);
for (i = 0; i < n; i++) {
numaGetIValue(naindex, i, &index);
box = boxaGetBox(boxas, index, L_COPY);
boxaAddBox(boxad, box, L_INSERT);
}
return boxad;
}
/*!
* boxaSort2d()
*
* Input: boxas
* &naa (<optional return> numaa with sorted indices
* whose values are the indices of the input array)
* delta1 (min overlap that permits aggregation of a box
* onto a boxa of horizontally-aligned boxes; pass 1)
* delta2 (min overlap that permits aggregation of a box
* onto a boxa of horizontally-aligned boxes; pass 2)
* minh1 (components less than this height either join an
* existing boxa or are set aside for pass 2)
* Return: boxaa (2d sorted version of boxa), or null on error
*
* Notes:
* (1) The final result is a sort where the 'fast scan' direction is
* left to right, and the 'slow scan' direction is from top
* to bottom. Each boxa in the boxaa represents a sorted set
* of boxes from left to right.
* (2) Two passes are used to aggregate the boxas, which can corresond
* to characters or words in a line of text. In pass 1, only
* taller components, which correspond to xheight or larger,
* are permitted to start a new boxa, whereas in pass 2,
* the remaining vertically-challenged components are allowed
* to join an existing boxa or start a new one.
* (3) If delta1 < 0, the first pass allows aggregation when
* boxes in the same boxa do not overlap vertically.
* The distance by which they can miss and still be aggregated
* is the absolute value |delta1|. Similar for delta2 on
* the second pass.
* (4) On the first pass, any component of height less than minh1
* cannot start a new boxa; it's put aside for later insertion.
* (5) On the second pass, any small component that doesn't align
* with an existing boxa can start a new one.
* (6) This can be used to identify lines of text from
* character or word bounding boxes.
*/
BOXAA *
boxaSort2d(BOXA *boxas,
NUMAA **pnaad,
l_int32 delta1,
l_int32 delta2,
l_int32 minh1)
{
l_int32 i, index, h, nt, ne, n, m, ival;
BOX *box;
BOXA *boxa, *boxae, *boxan, *boxat1, *boxat2, *boxav, *boxavs;
BOXAA *baa, *baad;
NUMA *naindex, *nae, *nan, *nah, *nav, *nat1, *nat2, *nad;
NUMAA *naa, *naad;
PROCNAME("boxaSort2d");
if (pnaad) *pnaad = NULL;
if (!boxas)
return (BOXAA *)ERROR_PTR("boxas not defined", procName, NULL);
/* Sort from left to right */
if ((boxa = boxaSort(boxas, L_SORT_BY_X, L_SORT_INCREASING, &naindex))
== NULL)
return (BOXAA *)ERROR_PTR("boxa not made", procName, NULL);
/* First pass: assign taller boxes to boxa by row */
nt = boxaGetCount(boxa);
baa = boxaaCreate(0);
naa = numaaCreate(0);
boxae = boxaCreate(0); /* save small height boxes here */
nae = numaCreate(0); /* keep track of small height boxes */
for (i = 0; i < nt; i++) {
box = boxaGetBox(boxa, i, L_CLONE);
boxGetGeometry(box, NULL, NULL, NULL, &h);
if (h < minh1) { /* save for 2nd pass */
boxaAddBox(boxae, box, L_INSERT);
numaAddNumber(nae, i);
}
else {
n = boxaaGetCount(baa);
boxaaAlignBox(baa, box, delta1, &index);
if (index < n) { /* append to an existing boxa */
boxaaAddBox(baa, index, box, L_INSERT);
}
else { /* doesn't align, need new boxa */
boxan = boxaCreate(0);
boxaAddBox(boxan, box, L_INSERT);
boxaaAddBoxa(baa, boxan, L_INSERT);
nan = numaCreate(0);
numaaAddNuma(naa, nan, L_INSERT);
}
numaGetIValue(naindex, i, &ival);
numaaAddNumber(naa, index, ival);
}
}
boxaDestroy(&boxa);
numaDestroy(&naindex);
/* Second pass: feed in small height boxes;
* TODO: this correctly, using local y position! */
ne = boxaGetCount(boxae);
for (i = 0; i < ne; i++) {
box = boxaGetBox(boxae, i, L_CLONE);
n = boxaaGetCount(baa);
boxaaAlignBox(baa, box, delta2, &index);
if (index < n) { /* append to an existing boxa */
boxaaAddBox(baa, index, box, L_INSERT);
}
else { /* doesn't align, need new boxa */
boxan = boxaCreate(0);
boxaAddBox(boxan, box, L_INSERT);
boxaaAddBoxa(baa, boxan, L_INSERT);
nan = numaCreate(0);
numaaAddNuma(naa, nan, L_INSERT);
}
numaGetIValue(nae, i, &ival); /* location in original boxas */
numaaAddNumber(naa, index, ival);
}
/* Sort each boxa in the boxaa */
m = boxaaGetCount(baa);
for (i = 0; i < m; i++) {
boxat1 = boxaaGetBoxa(baa, i, L_CLONE);
boxat2 = boxaSort(boxat1, L_SORT_BY_X, L_SORT_INCREASING, &nah);
boxaaReplaceBoxa(baa, i, boxat2);
nat1 = numaaGetNuma(naa, i, L_CLONE);
nat2 = numaSortByIndex(nat1, nah);
numaaReplaceNuma(naa, i, nat2);
boxaDestroy(&boxat1);
numaDestroy(&nat1);
numaDestroy(&nah);
}
/* Sort boxa vertically within boxaa, using the first box
* in each boxa. */
m = boxaaGetCount(baa);
boxav = boxaCreate(m); /* holds first box in each boxa in baa */
naad = numaaCreate(m);
if (pnaad)
*pnaad = naad;
baad = boxaaCreate(m);
for (i = 0; i < m; i++) {
boxat1 = boxaaGetBoxa(baa, i, L_CLONE);
box = boxaGetBox(boxat1, 0, L_CLONE);
boxaAddBox(boxav, box, L_INSERT);
boxaDestroy(&boxat1);
}
boxavs = boxaSort(boxav, L_SORT_BY_Y, L_SORT_INCREASING, &nav);
for (i = 0; i < m; i++) {
numaGetIValue(nav, i, &index);
boxa = boxaaGetBoxa(baa, index, L_CLONE);
boxaaAddBoxa(baad, boxa, L_INSERT);
nad = numaaGetNuma(naa, index, L_CLONE);
numaaAddNuma(naad, nad, L_INSERT);
}
/* fprintf(stderr, "box count = %d, numaa count = %d\n", nt,
numaaGetNumberCount(naad)); */
boxaaDestroy(&baa);
boxaDestroy(&boxav);
boxaDestroy(&boxavs);
boxaDestroy(&boxae);
numaDestroy(&nav);
numaDestroy(&nae);
numaaDestroy(&naa);
if (!pnaad)
numaaDestroy(&naad);
return baad;
}
/*!
* boxaSort2dByIndex()
*
* Input: boxas
* naa (numaa that maps from the new baa to the input boxa)
* Return: baa (sorted boxaa), or null on error
*/
BOXAA *
boxaSort2dByIndex(BOXA *boxas,
NUMAA *naa)
{
l_int32 ntot, boxtot, i, j, n, nn, index;
BOX *box;
BOXA *boxa;
BOXAA *baa;
NUMA *na;
PROCNAME("boxaSort2dByIndex");
if (!boxas)
return (BOXAA *)ERROR_PTR("boxas not defined", procName, NULL);
if (!naa)
return (BOXAA *)ERROR_PTR("naindex not defined", procName, NULL);
/* Check counts */
ntot = numaaGetNumberCount(naa);
boxtot = boxaGetCount(boxas);
if (ntot != boxtot)
return (BOXAA *)ERROR_PTR("element count mismatch", procName, NULL);
n = numaaGetCount(naa);
baa = boxaaCreate(n);
for (i = 0; i < n; i++) {
na = numaaGetNuma(naa, i, L_CLONE);
nn = numaGetCount(na);
boxa = boxaCreate(nn);
for (j = 0; j < nn; j++) {
numaGetIValue(na, i, &index);
box = boxaGetBox(boxas, index, L_COPY);
boxaAddBox(boxa, box, L_INSERT);
}
boxaaAddBoxa(baa, boxa, L_INSERT);
numaDestroy(&na);
}
return baa;
}
/*---------------------------------------------------------------------*
* Other Boxaa functions *
*---------------------------------------------------------------------*/
/*!
* boxaaGetExtent()
*
* Input: boxaa
* &w (<optional return> width)
* &h (<optional return> height)
* &box (<optional return>, minimum box containing all boxa
* in boxaa)
* Return: 0 if OK, 1 on error
*
* Notes:
* (1) The returned w and h are the minimum size image
* that would contain all boxes untranslated.
*/
l_int32
boxaaGetExtent(BOXAA *boxaa,
l_int32 *pw,
l_int32 *ph,
BOX **pbox)
{
l_int32 i, j, n, m, x, y, w, h, xmax, ymax, xmin, ymin;
BOXA *boxa;
PROCNAME("boxaaGetExtent");
if (!pw && !ph && !pbox)
return ERROR_INT("no ptrs defined", procName, 1);
if (pbox) *pbox = NULL;
if (pw) *pw = 0;
if (ph) *ph = 0;
if (!boxaa)
return ERROR_INT("boxaa not defined", procName, 1);
n = boxaaGetCount(boxaa);
if (n == 0)
return ERROR_INT("no boxa in boxaa", procName, 1);
xmax = ymax = 0;
xmin = ymin = 100000000;
for (i = 0; i < n; i++) {
boxa = boxaaGetBoxa(boxaa, i, L_CLONE);
m = boxaGetCount(boxa);
for (j = 0; j < m; j++) {
boxaGetBoxGeometry(boxa, j, &x, &y, &w, &h);
xmin = L_MIN(xmin, x);
ymin = L_MIN(ymin, y);
xmax = L_MAX(xmax, x + w);
ymax = L_MAX(ymax, y + h);
}
}
if (pw) *pw = xmax;
if (ph) *ph = ymax;
if (pbox)
*pbox = boxCreate(xmin, ymin, xmax - xmin, ymax - ymin);
return 0;
}
/*!
* boxaaFlattenToBoxa()
*
* Input: boxaa
* &naindex (<optional return> the boxa index in the boxaa)
* copyflag (L_COPY or L_CLONE)
* Return: boxa, or null on error
*
* Notes:
* (1) This 'flattens' the boxaa to a boxa, taking the boxes in
* order in the first boxa, then the second, etc.
* (2) If &naindex is defined, we generate a Numa that gives, for
* each box in the boxaa, the index of the boxa to which it belongs.
*/
BOXA *
boxaaFlattenToBoxa(BOXAA *baa,
NUMA **pnaindex,
l_int32 copyflag)
{
l_int32 i, j, m, n;
BOXA *boxa, *boxat;
BOX *box;
NUMA *naindex;
PROCNAME("boxaaFlattenToBoxa");
if (pnaindex) *pnaindex = NULL;
if (!baa)
return (BOXA *)ERROR_PTR("baa not defined", procName, NULL);
if (copyflag != L_COPY && copyflag != L_CLONE)
return (BOXA *)ERROR_PTR("invalid copyflag", procName, NULL);
if (pnaindex) {
naindex = numaCreate(0);
*pnaindex = naindex;
}
n = boxaaGetCount(baa);
boxa = boxaCreate(n);
for (i = 0; i < n; i++) {
boxat = boxaaGetBoxa(baa, i, L_CLONE);
m = boxaGetCount(boxat);
for (j = 0; j < m; j++) {
box = boxaGetBox(boxat, j, copyflag);
boxaAddBox(boxa, box, L_INSERT);
if (pnaindex)
numaAddNumber(naindex, i); /* save 'row' number */
}
boxaDestroy(&boxat);
}
return boxa;
}
/*!
* boxaaAlignBox()
*
* Input: boxaa
* box (to be aligned with the last of one of the boxa
* in boxaa, if possible)
* delta (amount by which consecutive components can miss
* in overlap and still be included in the array)
* &index (of boxa with best overlap, or if none match,
* this is the index of the next boxa to be generated)
* Return: 0 if OK, 1 on error
*
* Notes:
* (1) This is not greedy; it finds the boxa whose last box has
* the biggest overlap with the input box.
*/
l_int32
boxaaAlignBox(BOXAA *baa,
BOX *box,
l_int32 delta,
l_int32 *pindex)
{
l_int32 i, n, m, y, yt, h, ht, ovlp, maxovlp, maxindex;
BOXA *boxa;
PROCNAME("boxaaAlignBox");
if (!baa)
return ERROR_INT("baa not defined", procName, 1);
if (!box)
return ERROR_INT("box not defined", procName, 1);
if (!pindex)
return ERROR_INT("&index not defined", procName, 1);
n = boxaaGetCount(baa);
boxGetGeometry(box, NULL, &y, NULL, &h);
maxovlp = -10000000;
for (i = 0; i < n; i++) {
boxa = boxaaGetBoxa(baa, i, L_CLONE);
if ((m = boxaGetCount(boxa)) == 0) {
L_WARNING("no boxes in boxa", procName);
continue;
}
boxaGetBoxGeometry(boxa, m - 1, NULL, &yt, NULL, &ht); /* last one */
boxaDestroy(&boxa);
/* Overlap < 0 means the components do not overlap vertically */
if (yt >= y)
ovlp = y + h - 1 - yt;
else
ovlp = yt + ht - 1 - y;
if (ovlp > maxovlp) {
maxovlp = ovlp;
maxindex = i;
}
}
if (maxovlp + delta >= 0)
*pindex = maxindex;
else
*pindex = n;
return 0;
}