mirror of http://192.168.1.51:8099/lmh188/twain3.0
1929 lines
64 KiB
C
1929 lines
64 KiB
C
|
/*====================================================================*
|
||
|
- Copyright (C) 2001 Leptonica. All rights reserved.
|
||
|
-
|
||
|
- Redistribution and use in source and binary forms, with or without
|
||
|
- modification, are permitted provided that the following conditions
|
||
|
- are met:
|
||
|
- 1. Redistributions of source code must retain the above copyright
|
||
|
- notice, this list of conditions and the following disclaimer.
|
||
|
- 2. Redistributions in binary form must reproduce the above
|
||
|
- copyright notice, this list of conditions and the following
|
||
|
- disclaimer in the documentation and/or other materials
|
||
|
- provided with the distribution.
|
||
|
-
|
||
|
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
||
|
- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
||
|
- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
|
||
|
- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
|
||
|
- CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
||
|
- EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
||
|
- PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
||
|
- PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
|
||
|
- OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
|
||
|
- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
|
||
|
- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
||
|
*====================================================================*/
|
||
|
|
||
|
/*!
|
||
|
* \file boxfunc2.c
|
||
|
* <pre>
|
||
|
*
|
||
|
* Boxa/Box transform (shift, scale) and orthogonal rotation
|
||
|
* BOXA *boxaTransform()
|
||
|
* BOX *boxTransform()
|
||
|
* BOXA *boxaTransformOrdered()
|
||
|
* BOX *boxTransformOrdered()
|
||
|
* BOXA *boxaRotateOrth()
|
||
|
* BOX *boxRotateOrth()
|
||
|
* BOXA *boxaShiftWithPta()
|
||
|
*
|
||
|
* Boxa sort
|
||
|
* BOXA *boxaSort()
|
||
|
* BOXA *boxaBinSort()
|
||
|
* BOXA *boxaSortByIndex()
|
||
|
* BOXAA *boxaSort2d()
|
||
|
* BOXAA *boxaSort2dByIndex()
|
||
|
*
|
||
|
* Boxa statistics
|
||
|
* l_int32 boxaGetRankVals()
|
||
|
* l_int32 boxaGetMedianVals()
|
||
|
* l_int32 boxaGetAverageSize()
|
||
|
*
|
||
|
* Boxa array extraction
|
||
|
* l_int32 boxaExtractAsNuma()
|
||
|
* l_int32 boxaExtractAsPta()
|
||
|
* PTA *boxaExtractCorners()
|
||
|
*
|
||
|
* Other Boxaa functions
|
||
|
* l_int32 boxaaGetExtent()
|
||
|
* BOXA *boxaaFlattenToBoxa()
|
||
|
* BOXA *boxaaFlattenAligned()
|
||
|
* BOXAA *boxaEncapsulateAligned()
|
||
|
* BOXAA *boxaaTranspose()
|
||
|
* l_int32 boxaaAlignBox()
|
||
|
* </pre>
|
||
|
*/
|
||
|
|
||
|
#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 MinCompsForBinSort = 200;
|
||
|
|
||
|
|
||
|
/*---------------------------------------------------------------------*
|
||
|
* Boxa/Box transform (shift, scale) and orthogonal rotation *
|
||
|
*---------------------------------------------------------------------*/
|
||
|
/*!
|
||
|
* \brief boxaTransform()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[in] shiftx
|
||
|
* \param[in] shifty
|
||
|
* \param[in] scalex
|
||
|
* \param[in] scaley
|
||
|
* \return boxad, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) This is a very simple function that first shifts, then scales.
|
||
|
* (2) The UL corner coordinates of all boxes in the output %boxad
|
||
|
* (3) For the boxes in the output %boxad, the UL corner coordinates
|
||
|
* must be non-negative, and the width and height of valid
|
||
|
* boxes must be at least 1.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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) {
|
||
|
boxaDestroy(&boxad);
|
||
|
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;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxTransform()
|
||
|
*
|
||
|
* \param[in] box
|
||
|
* \param[in] shiftx
|
||
|
* \param[in] shifty
|
||
|
* \param[in] scalex
|
||
|
* \param[in] scaley
|
||
|
* \return boxd, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) This is a very simple function that first shifts, then scales.
|
||
|
* (2) If the box is invalid, a new invalid box is returned.
|
||
|
* (3) The UL corner coordinates must be non-negative, and the
|
||
|
* width and height of valid boxes must be at least 1.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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);
|
||
|
if (box->w <= 0 || box->h <= 0)
|
||
|
return boxCreate(0, 0, 0, 0);
|
||
|
else
|
||
|
return boxCreate((l_int32)(L_MAX(0, scalex * (box->x + shiftx) + 0.5)),
|
||
|
(l_int32)(L_MAX(0, 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)));
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaTransformOrdered()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[in] shiftx
|
||
|
* \param[in] shifty
|
||
|
* \param[in] scalex
|
||
|
* \param[in] scaley
|
||
|
* \param[in] xcen, ycen center of rotation
|
||
|
* \param[in] angle in radians; clockwise is positive
|
||
|
* \param[in] order one of 6 combinations: L_TR_SC_RO, ...
|
||
|
* \return boxd, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* 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.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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) {
|
||
|
boxaDestroy(&boxad);
|
||
|
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;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxTransformOrdered()
|
||
|
*
|
||
|
* \param[in] boxs
|
||
|
* \param[in] shiftx
|
||
|
* \param[in] shifty
|
||
|
* \param[in] scalex
|
||
|
* \param[in] scaley
|
||
|
* \param[in] xcen, ycen center of rotation
|
||
|
* \param[in] angle in radians; clockwise is positive
|
||
|
* \param[in] order one of 6 combinations: L_TR_SC_RO, ...
|
||
|
* \return boxd, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* 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.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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 (bw <= 0 || bh <= 0) /* invalid */
|
||
|
return boxCreate(0, 0, 0, 0);
|
||
|
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;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaRotateOrth()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[in] w, h of image in which the boxa is embedded
|
||
|
* \param[in] rotation 0 = noop, 1 = 90 deg, 2 = 180 deg, 3 = 270 deg;
|
||
|
* all rotations are clockwise
|
||
|
* \return boxad, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) See boxRotateOrth() for details.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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 || rotation > 3)
|
||
|
return (BOXA *)ERROR_PTR("rotation not in {0,1,2,3}", procName, NULL);
|
||
|
if (rotation == 0)
|
||
|
return boxaCopy(boxas, L_COPY);
|
||
|
|
||
|
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) {
|
||
|
boxaDestroy(&boxad);
|
||
|
return (BOXA *)ERROR_PTR("boxs not found", procName, NULL);
|
||
|
}
|
||
|
boxd = boxRotateOrth(boxs, w, h, rotation);
|
||
|
boxDestroy(&boxs);
|
||
|
boxaAddBox(boxad, boxd, L_INSERT);
|
||
|
}
|
||
|
|
||
|
return boxad;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxRotateOrth()
|
||
|
*
|
||
|
* \param[in] box
|
||
|
* \param[in] w, h of image in which the box is embedded
|
||
|
* \param[in] rotation 0 = noop, 1 = 90 deg, 2 = 180 deg, 3 = 270 deg;
|
||
|
* all rotations are clockwise
|
||
|
* \return boxd, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* 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.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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 || rotation > 3)
|
||
|
return (BOX *)ERROR_PTR("rotation not in {0,1,2,3}", procName, NULL);
|
||
|
if (rotation == 0)
|
||
|
return boxCopy(box);
|
||
|
|
||
|
boxGetGeometry(box, &bx, &by, &bw, &bh);
|
||
|
if (bw <= 0 || bh <= 0) /* invalid */
|
||
|
return boxCreate(0, 0, 0, 0);
|
||
|
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);
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaShiftWithPta()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[in] pta aligned with the boxes; determines shift amount
|
||
|
* \param[in] dir +1 to shift by the values in pta; -1 to shift
|
||
|
* by the negative of the values in the pta.
|
||
|
* \return boxad, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) In use, %pta may come from the UL corners of of a boxa, each
|
||
|
* of whose boxes contains the corresponding box of %boxas
|
||
|
* within it. The output %boxad is then a boxa in the (global)
|
||
|
* coordinates of the containing boxa. So the input %pta
|
||
|
* could come from boxaExtractCorners().
|
||
|
* (2) The operations with %dir == 1 and %dir == -1 are inverses if
|
||
|
* called in order (1, -1). Starting with an input boxa and
|
||
|
* calling twice with these values of %dir results in a boxa
|
||
|
* identical to the input. However, because box parameters can
|
||
|
* never be negative, calling in the order (-1, 1) may result
|
||
|
* in clipping at the left side and the top.
|
||
|
* </pre>
|
||
|
*/
|
||
|
BOXA *
|
||
|
boxaShiftWithPta(BOXA *boxas,
|
||
|
PTA *pta,
|
||
|
l_int32 dir)
|
||
|
{
|
||
|
l_int32 i, n, x, y, full;
|
||
|
BOX *box1, *box2;
|
||
|
BOXA *boxad;
|
||
|
|
||
|
PROCNAME("boxaShiftWithPta");
|
||
|
|
||
|
if (!boxas)
|
||
|
return (BOXA *)ERROR_PTR("boxas not defined", procName, NULL);
|
||
|
boxaIsFull(boxas, &full);
|
||
|
if (!full)
|
||
|
return (BOXA *)ERROR_PTR("boxas not full", procName, NULL);
|
||
|
if (!pta)
|
||
|
return (BOXA *)ERROR_PTR("pta not defined", procName, NULL);
|
||
|
if (dir != 1 && dir != -1)
|
||
|
return (BOXA *)ERROR_PTR("invalid dir", procName, NULL);
|
||
|
n = boxaGetCount(boxas);
|
||
|
if (n != ptaGetCount(pta))
|
||
|
return (BOXA *)ERROR_PTR("boxas and pta not same size", procName, NULL);
|
||
|
|
||
|
if ((boxad = boxaCreate(n)) == NULL)
|
||
|
return (BOXA *)ERROR_PTR("boxad not made", procName, NULL);
|
||
|
for (i = 0; i < n; i++) {
|
||
|
box1 = boxaGetBox(boxas, i, L_COPY);
|
||
|
ptaGetIPt(pta, i, &x, &y);
|
||
|
box2 = boxTransform(box1, dir * x, dir * y, 1.0, 1.0);
|
||
|
boxaAddBox(boxad, box2, L_INSERT);
|
||
|
boxDestroy(&box1);
|
||
|
}
|
||
|
return boxad;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*---------------------------------------------------------------------*
|
||
|
* Boxa sort *
|
||
|
*---------------------------------------------------------------------*/
|
||
|
/*!
|
||
|
* \brief boxaSort()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[in] sorttype L_SORT_BY_X, L_SORT_BY_Y,
|
||
|
* L_SORT_BY_RIGHT, L_SORT_BY_BOT,
|
||
|
* 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
|
||
|
* \param[in] sortorder L_SORT_INCREASING, L_SORT_DECREASING
|
||
|
* \param[out] pnaindex [optional] index of sorted order into
|
||
|
* original array
|
||
|
* \return boxad sorted version of boxas, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) An empty boxa returns a copy, with a warning.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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 ((n = boxaGetCount(boxas)) == 0) {
|
||
|
L_WARNING("boxas is empty\n", procName);
|
||
|
return boxaCopy(boxas, L_COPY);
|
||
|
}
|
||
|
if (sorttype != L_SORT_BY_X && sorttype != L_SORT_BY_Y &&
|
||
|
sorttype != L_SORT_BY_RIGHT && sorttype != L_SORT_BY_BOT &&
|
||
|
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 */
|
||
|
if (n > MinCompsForBinSort &&
|
||
|
((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_RIGHT:
|
||
|
numaAddNumber(na, x + w - 1);
|
||
|
break;
|
||
|
case L_SORT_BY_BOT:
|
||
|
numaAddNumber(na, y + h - 1);
|
||
|
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\n", procName);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/* Get the sort index for data array */
|
||
|
naindex = numaGetSortIndex(na, sortorder);
|
||
|
numaDestroy(&na);
|
||
|
if (!naindex)
|
||
|
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);
|
||
|
return boxad;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaBinSort()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[in] sorttype L_SORT_BY_X, L_SORT_BY_Y, L_SORT_BY_WIDTH,
|
||
|
* L_SORT_BY_HEIGHT, L_SORT_BY_PERIMETER
|
||
|
* \param[in] sortorder L_SORT_INCREASING, L_SORT_DECREASING
|
||
|
* \param[out] pnaindex [optional] index of sorted order into
|
||
|
* original array
|
||
|
* \return boxad sorted version of boxas, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* 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.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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 ((n = boxaGetCount(boxas)) == 0) {
|
||
|
L_WARNING("boxas is empty\n", procName);
|
||
|
return boxaCopy(boxas, L_COPY);
|
||
|
}
|
||
|
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 */
|
||
|
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\n", procName);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/* Get the sort index for data array */
|
||
|
naindex = numaGetBinSortIndex(na, sortorder);
|
||
|
numaDestroy(&na);
|
||
|
if (!naindex)
|
||
|
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);
|
||
|
return boxad;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaSortByIndex()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[in] 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 ((n = boxaGetCount(boxas)) == 0) {
|
||
|
L_WARNING("boxas is empty\n", procName);
|
||
|
return boxaCopy(boxas, L_COPY);
|
||
|
}
|
||
|
if (!naindex)
|
||
|
return (BOXA *)ERROR_PTR("naindex not defined", procName, NULL);
|
||
|
|
||
|
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;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaSort2d()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[out] pnaad [optional] numaa with sorted indices
|
||
|
* whose values are the indices of the input array
|
||
|
* \param[in] delta1 min separation that permits aggregation of a box
|
||
|
* onto a boxa of horizontally-aligned boxes; pass 1
|
||
|
* \param[in] delta2 min separation that permits aggregation of a box
|
||
|
* onto a boxa of horizontally-aligned boxes; pass 2
|
||
|
* \param[in] minh1 components less than this height either join an
|
||
|
* existing boxa or are set aside for pass 2
|
||
|
* \return baa 2d sorted version of boxa, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* 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 baa represents a sorted set
|
||
|
* of boxes from left to right.
|
||
|
* (2) Three passes are used to aggregate the boxas, which can correspond
|
||
|
* 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. In pass 2, the remaining
|
||
|
* vertically-challenged components are allowed to join an
|
||
|
* existing boxa or start a new one. In pass 3, boxa whose extent
|
||
|
* is overlapping are joined. After that, the boxes in each
|
||
|
* boxa are sorted horizontally, and finally the boxa are
|
||
|
* sorted vertically.
|
||
|
* (3) If %delta1 > 0, the first pass allows aggregation when
|
||
|
* boxes in the same boxa do not overlap vertically. In fact,
|
||
|
* %delta1 is the max distance by which they can miss and still
|
||
|
* be aggregated. If %delta1 < 0, the box must have vertical
|
||
|
* overlap of at least abs(%delta1) with the boxa before it
|
||
|
* can be merged. 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.
|
||
|
* (7) Typical values for the input parameters on 300 ppi text are:
|
||
|
* delta1 ~ 0
|
||
|
* delta2 ~ 0
|
||
|
* minh1 ~ 5
|
||
|
* </pre>
|
||
|
*/
|
||
|
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, *boxa1, *boxa2, *boxa3, *boxav, *boxavs;
|
||
|
BOXAA *baa, *baa1, *baad;
|
||
|
NUMA *naindex, *nae, *nan, *nah, *nav, *na1, *na2, *nad, *namap;
|
||
|
NUMAA *naa, *naa1, *naad;
|
||
|
|
||
|
PROCNAME("boxaSort2d");
|
||
|
|
||
|
if (pnaad) *pnaad = NULL;
|
||
|
if (!boxas)
|
||
|
return (BOXAA *)ERROR_PTR("boxas not defined", procName, NULL);
|
||
|
if (boxaGetCount(boxas) == 0)
|
||
|
return (BOXAA *)ERROR_PTR("boxas is empty", 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 */
|
||
|
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);
|
||
|
}
|
||
|
|
||
|
/* Third pass: merge some boxa whose extent is overlapping.
|
||
|
* Think of these boxa as text lines, where the bounding boxes
|
||
|
* of the text lines can overlap, but likely won't have
|
||
|
* a huge overlap.
|
||
|
* First do a greedy find of pairs of overlapping boxa, where
|
||
|
* the two boxa overlap by at least 50% of the smaller, and
|
||
|
* the smaller is not more than half the area of the larger.
|
||
|
* For such pairs, call the larger one the primary boxa. The
|
||
|
* boxes in the smaller one are appended to those in the primary
|
||
|
* in pass 3a, and the primaries are extracted in pass 3b.
|
||
|
* In this way, all boxes in the original baa are saved. */
|
||
|
n = boxaaGetCount(baa);
|
||
|
boxaaGetExtent(baa, NULL, NULL, NULL, &boxa3);
|
||
|
boxa1 = boxaHandleOverlaps(boxa3, L_REMOVE_SMALL, 1000, 0.5, 0.5, &namap);
|
||
|
boxaDestroy(&boxa1);
|
||
|
boxaDestroy(&boxa3);
|
||
|
for (i = 0; i < n; i++) { /* Pass 3a: join selected copies of boxa */
|
||
|
numaGetIValue(namap, i, &ival);
|
||
|
if (ival >= 0) { /* join current to primary boxa[ival] */
|
||
|
boxa1 = boxaaGetBoxa(baa, i, L_COPY);
|
||
|
boxa2 = boxaaGetBoxa(baa, ival, L_CLONE);
|
||
|
boxaJoin(boxa2, boxa1, 0, -1);
|
||
|
boxaDestroy(&boxa2);
|
||
|
boxaDestroy(&boxa1);
|
||
|
na1 = numaaGetNuma(naa, i, L_COPY);
|
||
|
na2 = numaaGetNuma(naa, ival, L_CLONE);
|
||
|
numaJoin(na2, na1, 0, -1);
|
||
|
numaDestroy(&na1);
|
||
|
numaDestroy(&na2);
|
||
|
}
|
||
|
}
|
||
|
baa1 = boxaaCreate(n);
|
||
|
naa1 = numaaCreate(n);
|
||
|
for (i = 0; i < n; i++) { /* Pass 3b: save primary boxa */
|
||
|
numaGetIValue(namap, i, &ival);
|
||
|
if (ival == -1) {
|
||
|
boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
|
||
|
boxaaAddBoxa(baa1, boxa1, L_INSERT);
|
||
|
na1 = numaaGetNuma(naa, i, L_CLONE);
|
||
|
numaaAddNuma(naa1, na1, L_INSERT);
|
||
|
}
|
||
|
}
|
||
|
numaDestroy(&namap);
|
||
|
boxaaDestroy(&baa);
|
||
|
baa = baa1;
|
||
|
numaaDestroy(&naa);
|
||
|
naa = naa1;
|
||
|
|
||
|
/* Sort the boxes in each boxa horizontally */
|
||
|
m = boxaaGetCount(baa);
|
||
|
for (i = 0; i < m; i++) {
|
||
|
boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
|
||
|
boxa2 = boxaSort(boxa1, L_SORT_BY_X, L_SORT_INCREASING, &nah);
|
||
|
boxaaReplaceBoxa(baa, i, boxa2);
|
||
|
na1 = numaaGetNuma(naa, i, L_CLONE);
|
||
|
na2 = numaSortByIndex(na1, nah);
|
||
|
numaaReplaceNuma(naa, i, na2);
|
||
|
boxaDestroy(&boxa1);
|
||
|
numaDestroy(&na1);
|
||
|
numaDestroy(&nah);
|
||
|
}
|
||
|
|
||
|
/* Sort the 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++) {
|
||
|
boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
|
||
|
box = boxaGetBox(boxa1, 0, L_CLONE);
|
||
|
boxaAddBox(boxav, box, L_INSERT);
|
||
|
boxaDestroy(&boxa1);
|
||
|
}
|
||
|
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;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaSort2dByIndex()
|
||
|
*
|
||
|
* \param[in] boxas
|
||
|
* \param[in] 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 ((boxtot = boxaGetCount(boxas)) == 0)
|
||
|
return (BOXAA *)ERROR_PTR("boxas is empty", procName, NULL);
|
||
|
if (!naa)
|
||
|
return (BOXAA *)ERROR_PTR("naindex not defined", procName, NULL);
|
||
|
|
||
|
/* Check counts */
|
||
|
ntot = numaaGetNumberCount(naa);
|
||
|
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;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*---------------------------------------------------------------------*
|
||
|
* Boxa array extraction *
|
||
|
*---------------------------------------------------------------------*/
|
||
|
/*!
|
||
|
* \brief boxaExtractAsNuma()
|
||
|
*
|
||
|
* \param[in] boxa
|
||
|
* \param[out] pnal [optional] array of left locations
|
||
|
* \param[out] pnat [optional] array of top locations
|
||
|
* \param[out] pnar [optional] array of right locations
|
||
|
* \param[out] pnab [optional] array of bottom locations
|
||
|
* \param[out] pnaw [optional] array of widths
|
||
|
* \param[out] pnah [optional] array of heights
|
||
|
* \param[in] keepinvalid 1 to keep invalid boxes; 0 to remove them
|
||
|
* \return 0 if OK, 1 on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) If you are counting or sorting values, such as determining
|
||
|
* rank order, you must remove invalid boxes.
|
||
|
* (2) If you are parametrizing the values, or doing an evaluation
|
||
|
* where the position in the boxa sequence is important, you
|
||
|
* must replace the invalid boxes with valid ones before
|
||
|
* doing the extraction. This is easily done with boxaFillSequence().
|
||
|
* </pre>
|
||
|
*/
|
||
|
l_ok
|
||
|
boxaExtractAsNuma(BOXA *boxa,
|
||
|
NUMA **pnal,
|
||
|
NUMA **pnat,
|
||
|
NUMA **pnar,
|
||
|
NUMA **pnab,
|
||
|
NUMA **pnaw,
|
||
|
NUMA **pnah,
|
||
|
l_int32 keepinvalid)
|
||
|
{
|
||
|
l_int32 i, n, left, top, right, bot, w, h;
|
||
|
|
||
|
PROCNAME("boxaExtractAsNuma");
|
||
|
|
||
|
if (!pnal && !pnat && !pnar && !pnab && !pnaw && !pnah)
|
||
|
return ERROR_INT("no output requested", procName, 1);
|
||
|
if (pnal) *pnal = NULL;
|
||
|
if (pnat) *pnat = NULL;
|
||
|
if (pnar) *pnar = NULL;
|
||
|
if (pnab) *pnab = NULL;
|
||
|
if (pnaw) *pnaw = NULL;
|
||
|
if (pnah) *pnah = NULL;
|
||
|
if (!boxa)
|
||
|
return ERROR_INT("boxa not defined", procName, 1);
|
||
|
if (!keepinvalid && boxaGetValidCount(boxa) == 0)
|
||
|
return ERROR_INT("no valid boxes", procName, 1);
|
||
|
|
||
|
n = boxaGetCount(boxa);
|
||
|
if (pnal) *pnal = numaCreate(n);
|
||
|
if (pnat) *pnat = numaCreate(n);
|
||
|
if (pnar) *pnar = numaCreate(n);
|
||
|
if (pnab) *pnab = numaCreate(n);
|
||
|
if (pnaw) *pnaw = numaCreate(n);
|
||
|
if (pnah) *pnah = numaCreate(n);
|
||
|
for (i = 0; i < n; i++) {
|
||
|
boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
|
||
|
if (!keepinvalid && (w <= 0 || h <= 0))
|
||
|
continue;
|
||
|
right = left + w - 1;
|
||
|
bot = top + h - 1;
|
||
|
if (pnal) numaAddNumber(*pnal, left);
|
||
|
if (pnat) numaAddNumber(*pnat, top);
|
||
|
if (pnar) numaAddNumber(*pnar, right);
|
||
|
if (pnab) numaAddNumber(*pnab, bot);
|
||
|
if (pnaw) numaAddNumber(*pnaw, w);
|
||
|
if (pnah) numaAddNumber(*pnah, h);
|
||
|
}
|
||
|
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaExtractAsPta()
|
||
|
*
|
||
|
* \param[in] boxa
|
||
|
* \param[out] pptal [optional] array of left locations vs. index
|
||
|
* \param[out] pptat [optional] array of top locations vs. index
|
||
|
* \param[out] pptar [optional] array of right locations vs. index
|
||
|
* \param[out] pptab [optional] array of bottom locations vs. index
|
||
|
* \param[out] pptaw [optional] array of widths vs. index
|
||
|
* \param[out] pptah [optional] array of heights vs. index
|
||
|
* \param[in] keepinvalid 1 to keep invalid boxes; 0 to remove them
|
||
|
* \return 0 if OK, 1 on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) For most applications, such as counting, sorting, fitting
|
||
|
* to some parametrized form, plotting or filtering in general,
|
||
|
* you should remove the invalid boxes. Each pta saves the
|
||
|
* box index in the x array, so replacing invalid boxes by
|
||
|
* filling with boxaFillSequence(), which is required for
|
||
|
* boxaExtractAsNuma(), is not necessary.
|
||
|
* (2) If invalid boxes are retained, each one will result in
|
||
|
* entries (typically 0) in all selected output pta.
|
||
|
* (3) Other boxa --> pta functions are:
|
||
|
* * boxaExtractCorners(): extracts any of the four corners as a pta.
|
||
|
* * boxaConvertToPta(): extracts sufficient number of corners
|
||
|
* to allow reconstruction of the original boxa from the pta.
|
||
|
* </pre>
|
||
|
*/
|
||
|
l_ok
|
||
|
boxaExtractAsPta(BOXA *boxa,
|
||
|
PTA **pptal,
|
||
|
PTA **pptat,
|
||
|
PTA **pptar,
|
||
|
PTA **pptab,
|
||
|
PTA **pptaw,
|
||
|
PTA **pptah,
|
||
|
l_int32 keepinvalid)
|
||
|
{
|
||
|
l_int32 i, n, left, top, right, bot, w, h;
|
||
|
|
||
|
PROCNAME("boxaExtractAsPta");
|
||
|
|
||
|
if (!pptal && !pptar && !pptat && !pptab && !pptaw && !pptah)
|
||
|
return ERROR_INT("no output requested", procName, 1);
|
||
|
if (pptal) *pptal = NULL;
|
||
|
if (pptat) *pptat = NULL;
|
||
|
if (pptar) *pptar = NULL;
|
||
|
if (pptab) *pptab = NULL;
|
||
|
if (pptaw) *pptaw = NULL;
|
||
|
if (pptah) *pptah = NULL;
|
||
|
if (!boxa)
|
||
|
return ERROR_INT("boxa not defined", procName, 1);
|
||
|
if (!keepinvalid && boxaGetValidCount(boxa) == 0)
|
||
|
return ERROR_INT("no valid boxes", procName, 1);
|
||
|
|
||
|
n = boxaGetCount(boxa);
|
||
|
if (pptal) *pptal = ptaCreate(n);
|
||
|
if (pptat) *pptat = ptaCreate(n);
|
||
|
if (pptar) *pptar = ptaCreate(n);
|
||
|
if (pptab) *pptab = ptaCreate(n);
|
||
|
if (pptaw) *pptaw = ptaCreate(n);
|
||
|
if (pptah) *pptah = ptaCreate(n);
|
||
|
for (i = 0; i < n; i++) {
|
||
|
boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
|
||
|
if (!keepinvalid && (w <= 0 || h <= 0))
|
||
|
continue;
|
||
|
right = left + w - 1;
|
||
|
bot = top + h - 1;
|
||
|
if (pptal) ptaAddPt(*pptal, i, left);
|
||
|
if (pptat) ptaAddPt(*pptat, i, top);
|
||
|
if (pptar) ptaAddPt(*pptar, i, right);
|
||
|
if (pptab) ptaAddPt(*pptab, i, bot);
|
||
|
if (pptaw) ptaAddPt(*pptaw, i, w);
|
||
|
if (pptah) ptaAddPt(*pptah, i, h);
|
||
|
}
|
||
|
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaExtractCorners()
|
||
|
*
|
||
|
* \param[in] boxa
|
||
|
* \param[in] corner L_UPPER_LEFT, L_UPPER_RIGHT, L_LOWER_LEFT,
|
||
|
* L_LOWER_RIGHT
|
||
|
* \return pta of corner coordinates, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) Extracts (0,0) for invalid boxes.
|
||
|
* (2) Other boxa --> pta functions are:
|
||
|
* * boxaExtractAsPta(): allows extraction of any dimension
|
||
|
* and/or side location, with each in a separate pta.
|
||
|
* * boxaConvertToPta(): extracts sufficient number of corners
|
||
|
* to allow reconstruction of the original boxa from the pta.
|
||
|
* </pre>
|
||
|
*/
|
||
|
PTA *
|
||
|
boxaExtractCorners(BOXA *boxa,
|
||
|
l_int32 corner)
|
||
|
{
|
||
|
l_int32 i, n, left, top, right, bot, w, h;
|
||
|
PTA *pta;
|
||
|
|
||
|
PROCNAME("boxaExtractCorners");
|
||
|
|
||
|
if (!boxa)
|
||
|
return (PTA *)ERROR_PTR("boxa not defined", procName, NULL);
|
||
|
if (corner != L_UPPER_LEFT && corner != L_UPPER_RIGHT &&
|
||
|
corner != L_LOWER_LEFT && corner != L_LOWER_RIGHT)
|
||
|
return (PTA *)ERROR_PTR("invalid corner", procName, NULL);
|
||
|
|
||
|
n = boxaGetCount(boxa);
|
||
|
if ((pta = ptaCreate(n)) == NULL)
|
||
|
return (PTA *)ERROR_PTR("pta not made", procName, NULL);
|
||
|
|
||
|
for (i = 0; i < n; i++) {
|
||
|
boxaGetBoxGeometry(boxa, i, &left, &top, &w, &h);
|
||
|
right = left + w - 1;
|
||
|
bot = top + h - 1;
|
||
|
if (w == 0 || h == 0) { /* invalid */
|
||
|
left = 0;
|
||
|
top = 0;
|
||
|
right = 0;
|
||
|
bot = 0;
|
||
|
}
|
||
|
if (corner == L_UPPER_LEFT)
|
||
|
ptaAddPt(pta, left, top);
|
||
|
else if (corner == L_UPPER_RIGHT)
|
||
|
ptaAddPt(pta, right, top);
|
||
|
else if (corner == L_LOWER_LEFT)
|
||
|
ptaAddPt(pta, left, bot);
|
||
|
else if (corner == L_LOWER_RIGHT)
|
||
|
ptaAddPt(pta, right, bot);
|
||
|
}
|
||
|
|
||
|
return pta;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*---------------------------------------------------------------------*
|
||
|
* Boxa statistics *
|
||
|
*---------------------------------------------------------------------*/
|
||
|
/*!
|
||
|
* \brief boxaGetRankVals()
|
||
|
*
|
||
|
* \param[in] boxa
|
||
|
* \param[in] fract use 0.0 for smallest, 1.0 for largest width and height
|
||
|
* \param[out] px [optional] rank value of x (left side)
|
||
|
* \param[out] py [optional] rank value of y (top side)
|
||
|
* \param[out] pr [optional] rank value of right side
|
||
|
* \param[out] pb [optional] rank value of bottom side
|
||
|
* \param[out] pw [optional] rank value of width
|
||
|
* \param[out] ph [optional] rank value of height
|
||
|
* \return 0 if OK, 1 on error or if the boxa is empty or has no valid boxes
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) This function does not assume that all boxes in the boxa are valid
|
||
|
* (2) The six box parameters are sorted independently.
|
||
|
* For rank order, the width and height are sorted in increasing
|
||
|
* order. But what does it mean to sort x and y in "rank order"?
|
||
|
* If the boxes are of comparable size and somewhat
|
||
|
* aligned (e.g., from multiple images), it makes some sense
|
||
|
* to give a "rank order" for x and y by sorting them in
|
||
|
* decreasing order. (By the same argument, we choose to sort
|
||
|
* the r and b sides in increasing order.) In general, the
|
||
|
* interpretation of a rank order on x and y (or on r and b)
|
||
|
* is highly application dependent. In summary:
|
||
|
* ~ x and y are sorted in decreasing order
|
||
|
* ~ r and b are sorted in increasing order
|
||
|
* ~ w and h are sorted in increasing order
|
||
|
* </pre>
|
||
|
*/
|
||
|
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)
|
||
|
{
|
||
|
l_float32 xval, yval, rval, bval, wval, hval;
|
||
|
NUMA *nax, *nay, *nar, *nab, *naw, *nah;
|
||
|
|
||
|
PROCNAME("boxaGetRankVals");
|
||
|
|
||
|
if (px) *px = 0;
|
||
|
if (py) *py = 0;
|
||
|
if (pr) *pr = 0;
|
||
|
if (pb) *pb = 0;
|
||
|
if (pw) *pw = 0;
|
||
|
if (ph) *ph = 0;
|
||
|
if (!boxa)
|
||
|
return ERROR_INT("boxa not defined", procName, 1);
|
||
|
if (fract < 0.0 || fract > 1.0)
|
||
|
return ERROR_INT("fract not in [0.0 ... 1.0]", procName, 1);
|
||
|
if (boxaGetValidCount(boxa) == 0)
|
||
|
return ERROR_INT("no valid boxes in boxa", procName, 1);
|
||
|
|
||
|
/* Use only the valid boxes */
|
||
|
boxaExtractAsNuma(boxa, &nax, &nay, &nar, &nab, &naw, &nah, 0);
|
||
|
|
||
|
if (px) {
|
||
|
numaGetRankValue(nax, 1.0 - fract, NULL, 1, &xval);
|
||
|
*px = (l_int32)xval;
|
||
|
}
|
||
|
if (py) {
|
||
|
numaGetRankValue(nay, 1.0 - fract, NULL, 1, &yval);
|
||
|
*py = (l_int32)yval;
|
||
|
}
|
||
|
if (pr) {
|
||
|
numaGetRankValue(nar, fract, NULL, 1, &rval);
|
||
|
*pr = (l_int32)rval;
|
||
|
}
|
||
|
if (pb) {
|
||
|
numaGetRankValue(nab, fract, NULL, 1, &bval);
|
||
|
*pb = (l_int32)bval;
|
||
|
}
|
||
|
if (pw) {
|
||
|
numaGetRankValue(naw, fract, NULL, 1, &wval);
|
||
|
*pw = (l_int32)wval;
|
||
|
}
|
||
|
if (ph) {
|
||
|
numaGetRankValue(nah, fract, NULL, 1, &hval);
|
||
|
*ph = (l_int32)hval;
|
||
|
}
|
||
|
numaDestroy(&nax);
|
||
|
numaDestroy(&nay);
|
||
|
numaDestroy(&nar);
|
||
|
numaDestroy(&nab);
|
||
|
numaDestroy(&naw);
|
||
|
numaDestroy(&nah);
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaGetMedianVals()
|
||
|
*
|
||
|
* \param[in] boxa
|
||
|
* \param[out] px [optional] median value of x (left side)
|
||
|
* \param[out] py [optional] median value of y (top side)
|
||
|
* \param[out] pr [optional] median value of right side
|
||
|
* \param[out] pb [optional] median value of bottom side
|
||
|
* \param[out] pw [optional] median value of width
|
||
|
* \param[out] ph [optional] median value of height
|
||
|
* \return 0 if OK, 1 on error or if the boxa is empty or has no valid boxes
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) See boxaGetRankVals()
|
||
|
* </pre>
|
||
|
*/
|
||
|
l_ok
|
||
|
boxaGetMedianVals(BOXA *boxa,
|
||
|
l_int32 *px,
|
||
|
l_int32 *py,
|
||
|
l_int32 *pr,
|
||
|
l_int32 *pb,
|
||
|
l_int32 *pw,
|
||
|
l_int32 *ph)
|
||
|
{
|
||
|
PROCNAME("boxaGetMedianVals");
|
||
|
|
||
|
if (!boxa)
|
||
|
return ERROR_INT("boxa not defined", procName, 1);
|
||
|
if (boxaGetValidCount(boxa) == 0)
|
||
|
return ERROR_INT("no valid boxes in boxa", procName, 1);
|
||
|
|
||
|
return boxaGetRankVals(boxa, 0.5, px, py, pr, pb, pw, ph);
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaGetAverageSize()
|
||
|
*
|
||
|
* \param[in] boxa
|
||
|
* \param[out] pw [optional] average width
|
||
|
* \param[out] ph [optional] average height
|
||
|
* \return 0 if OK, 1 on error or if the boxa is empty
|
||
|
*/
|
||
|
l_ok
|
||
|
boxaGetAverageSize(BOXA *boxa,
|
||
|
l_float32 *pw,
|
||
|
l_float32 *ph)
|
||
|
{
|
||
|
l_int32 i, n, bw, bh;
|
||
|
l_float32 sumw, sumh;
|
||
|
|
||
|
PROCNAME("boxaGetAverageSize");
|
||
|
|
||
|
if (pw) *pw = 0.0;
|
||
|
if (ph) *ph = 0.0;
|
||
|
if (!boxa)
|
||
|
return ERROR_INT("boxa not defined", procName, 1);
|
||
|
if ((n = boxaGetCount(boxa)) == 0)
|
||
|
return ERROR_INT("boxa is empty", procName, 1);
|
||
|
|
||
|
sumw = sumh = 0.0;
|
||
|
for (i = 0; i < n; i++) {
|
||
|
boxaGetBoxGeometry(boxa, i, NULL, NULL, &bw, &bh);
|
||
|
sumw += bw;
|
||
|
sumh += bh;
|
||
|
}
|
||
|
|
||
|
if (pw) *pw = sumw / n;
|
||
|
if (ph) *ph = sumh / n;
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*---------------------------------------------------------------------*
|
||
|
* Other Boxaa functions *
|
||
|
*---------------------------------------------------------------------*/
|
||
|
/*!
|
||
|
* \brief boxaaGetExtent()
|
||
|
*
|
||
|
* \param[in] baa
|
||
|
* \param[out] pw [optional] width
|
||
|
* \param[out] ph [optional] height
|
||
|
* \param[out] pbox [optional] minimum box containing all boxa
|
||
|
* in boxaa
|
||
|
* \param[out] pboxa [optional] boxa containing all boxes in each
|
||
|
* boxa in the boxaa
|
||
|
* \return 0 if OK, 1 on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) The returned w and h are the minimum size image
|
||
|
* that would contain all boxes untranslated.
|
||
|
* (2) Each box in the returned boxa is the minimum box required to
|
||
|
* hold all the boxes in the respective boxa of baa.
|
||
|
* (3) If there are no valid boxes in a boxa, the box corresponding
|
||
|
* to its extent has all fields set to 0 (an invalid box).
|
||
|
* </pre>
|
||
|
*/
|
||
|
l_ok
|
||
|
boxaaGetExtent(BOXAA *baa,
|
||
|
l_int32 *pw,
|
||
|
l_int32 *ph,
|
||
|
BOX **pbox,
|
||
|
BOXA **pboxa)
|
||
|
{
|
||
|
l_int32 i, n, x, y, w, h, xmax, ymax, xmin, ymin, found;
|
||
|
BOX *box1;
|
||
|
BOXA *boxa, *boxa1;
|
||
|
|
||
|
PROCNAME("boxaaGetExtent");
|
||
|
|
||
|
if (!pw && !ph && !pbox && !pboxa)
|
||
|
return ERROR_INT("no ptrs defined", procName, 1);
|
||
|
if (pw) *pw = 0;
|
||
|
if (ph) *ph = 0;
|
||
|
if (pbox) *pbox = NULL;
|
||
|
if (pboxa) *pboxa = NULL;
|
||
|
if (!baa)
|
||
|
return ERROR_INT("baa not defined", procName, 1);
|
||
|
|
||
|
n = boxaaGetCount(baa);
|
||
|
if (n == 0)
|
||
|
return ERROR_INT("no boxa in baa", procName, 1);
|
||
|
|
||
|
boxa = boxaCreate(n);
|
||
|
xmax = ymax = 0;
|
||
|
xmin = ymin = 100000000;
|
||
|
found = FALSE;
|
||
|
for (i = 0; i < n; i++) {
|
||
|
boxa1 = boxaaGetBoxa(baa, i, L_CLONE);
|
||
|
boxaGetExtent(boxa1, NULL, NULL, &box1);
|
||
|
boxaDestroy(&boxa1);
|
||
|
boxGetGeometry(box1, &x, &y, &w, &h);
|
||
|
if (w > 0 && h > 0) { /* a valid extent box */
|
||
|
found = TRUE; /* found at least one valid extent box */
|
||
|
xmin = L_MIN(xmin, x);
|
||
|
ymin = L_MIN(ymin, y);
|
||
|
xmax = L_MAX(xmax, x + w);
|
||
|
ymax = L_MAX(ymax, y + h);
|
||
|
}
|
||
|
boxaAddBox(boxa, box1, L_INSERT);
|
||
|
}
|
||
|
if (found == FALSE) /* no valid extent boxes */
|
||
|
xmin = ymin = 0;
|
||
|
|
||
|
if (pw) *pw = xmax;
|
||
|
if (ph) *ph = ymax;
|
||
|
if (pbox)
|
||
|
*pbox = boxCreate(xmin, ymin, xmax - xmin, ymax - ymin);
|
||
|
if (pboxa)
|
||
|
*pboxa = boxa;
|
||
|
else
|
||
|
boxaDestroy(&boxa);
|
||
|
return 0;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaaFlattenToBoxa()
|
||
|
*
|
||
|
* \param[in] baa
|
||
|
* \param[out] pnaindex [optional] the boxa index in the baa
|
||
|
* \param[in] copyflag L_COPY or L_CLONE
|
||
|
* \return boxa, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) This 'flattens' the baa to a boxa, taking the boxes in
|
||
|
* order in the first boxa, then the second, etc.
|
||
|
* (2) If a boxa is empty, we generate an invalid, placeholder box
|
||
|
* of zero size. This is useful when converting from a baa
|
||
|
* where each boxa has either 0 or 1 boxes, and it is necessary
|
||
|
* to maintain a 1:1 correspondence between the initial
|
||
|
* boxa array and the resulting box array.
|
||
|
* (3) If &naindex is defined, we generate a Numa that gives, for
|
||
|
* each box in the baa, the index of the boxa to which it belongs.
|
||
|
* </pre>
|
||
|
*/
|
||
|
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);
|
||
|
if (m == 0) { /* placeholder box */
|
||
|
box = boxCreate(0, 0, 0, 0);
|
||
|
boxaAddBox(boxa, box, L_INSERT);
|
||
|
if (pnaindex)
|
||
|
numaAddNumber(naindex, i); /* save 'row' number */
|
||
|
} else {
|
||
|
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;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaaFlattenAligned()
|
||
|
*
|
||
|
* \param[in] baa
|
||
|
* \param[in] num number extracted from each
|
||
|
* \param[in] fillerbox [optional] that fills if necessary
|
||
|
* \param[in] copyflag L_COPY or L_CLONE
|
||
|
* \return boxa, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) This 'flattens' the baa to a boxa, taking the first %num
|
||
|
* boxes from each boxa.
|
||
|
* (2) In each boxa, if there are less than %num boxes, we preserve
|
||
|
* the alignment between the input baa and the output boxa
|
||
|
* by inserting one or more fillerbox(es) or, if %fillerbox == NULL,
|
||
|
* one or more invalid placeholder boxes.
|
||
|
* </pre>
|
||
|
*/
|
||
|
BOXA *
|
||
|
boxaaFlattenAligned(BOXAA *baa,
|
||
|
l_int32 num,
|
||
|
BOX *fillerbox,
|
||
|
l_int32 copyflag)
|
||
|
{
|
||
|
l_int32 i, j, m, n, mval, nshort;
|
||
|
BOXA *boxat, *boxad;
|
||
|
BOX *box;
|
||
|
|
||
|
PROCNAME("boxaaFlattenAligned");
|
||
|
|
||
|
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);
|
||
|
|
||
|
n = boxaaGetCount(baa);
|
||
|
boxad = boxaCreate(n);
|
||
|
for (i = 0; i < n; i++) {
|
||
|
boxat = boxaaGetBoxa(baa, i, L_CLONE);
|
||
|
m = boxaGetCount(boxat);
|
||
|
mval = L_MIN(m, num);
|
||
|
nshort = num - mval;
|
||
|
for (j = 0; j < mval; j++) { /* take the first %num if possible */
|
||
|
box = boxaGetBox(boxat, j, copyflag);
|
||
|
boxaAddBox(boxad, box, L_INSERT);
|
||
|
}
|
||
|
for (j = 0; j < nshort; j++) { /* add fillers if necessary */
|
||
|
if (fillerbox) {
|
||
|
boxaAddBox(boxad, fillerbox, L_COPY);
|
||
|
} else {
|
||
|
box = boxCreate(0, 0, 0, 0); /* invalid placeholder box */
|
||
|
boxaAddBox(boxad, box, L_INSERT);
|
||
|
}
|
||
|
}
|
||
|
boxaDestroy(&boxat);
|
||
|
}
|
||
|
|
||
|
return boxad;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaEncapsulateAligned()
|
||
|
*
|
||
|
* \param[in] boxa
|
||
|
* \param[in] num number put into each boxa in the baa
|
||
|
* \param[in] copyflag L_COPY or L_CLONE
|
||
|
* \return baa, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) This puts %num boxes from the input %boxa into each of a
|
||
|
* set of boxa within an output baa.
|
||
|
* (2) This assumes that the boxes in %boxa are in sets of %num each.
|
||
|
* </pre>
|
||
|
*/
|
||
|
BOXAA *
|
||
|
boxaEncapsulateAligned(BOXA *boxa,
|
||
|
l_int32 num,
|
||
|
l_int32 copyflag)
|
||
|
{
|
||
|
l_int32 i, j, n, nbaa, index;
|
||
|
BOX *box;
|
||
|
BOXA *boxat;
|
||
|
BOXAA *baa;
|
||
|
|
||
|
PROCNAME("boxaEncapsulateAligned");
|
||
|
|
||
|
if (!boxa)
|
||
|
return (BOXAA *)ERROR_PTR("boxa not defined", procName, NULL);
|
||
|
if (copyflag != L_COPY && copyflag != L_CLONE)
|
||
|
return (BOXAA *)ERROR_PTR("invalid copyflag", procName, NULL);
|
||
|
|
||
|
n = boxaGetCount(boxa);
|
||
|
nbaa = n / num;
|
||
|
if (num * nbaa != n)
|
||
|
L_ERROR("inconsistent alignment: num doesn't divide n\n", procName);
|
||
|
baa = boxaaCreate(nbaa);
|
||
|
for (i = 0, index = 0; i < nbaa; i++) {
|
||
|
boxat = boxaCreate(num);
|
||
|
for (j = 0; j < num; j++, index++) {
|
||
|
box = boxaGetBox(boxa, index, copyflag);
|
||
|
boxaAddBox(boxat, box, L_INSERT);
|
||
|
}
|
||
|
boxaaAddBoxa(baa, boxat, L_INSERT);
|
||
|
}
|
||
|
|
||
|
return baa;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaaTranspose()
|
||
|
*
|
||
|
* \param[in] baas
|
||
|
* \return baad, or NULL on error
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) If you think of a boxaa as a 2D array of boxes that is accessed
|
||
|
* row major, then each row is represented by one of the boxa.
|
||
|
* This function creates a new boxaa related to the input boxaa
|
||
|
* as a column major traversal of the input boxaa.
|
||
|
* (2) For example, if %baas has 2 boxa, each with 10 boxes, then
|
||
|
* %baad will have 10 boxa, each with 2 boxes.
|
||
|
* (3) Require for this transpose operation that each boxa in
|
||
|
* %baas has the same number of boxes. This operation is useful
|
||
|
* when the i-th boxes in each boxa are meaningfully related.
|
||
|
* </pre>
|
||
|
*/
|
||
|
BOXAA *
|
||
|
boxaaTranspose(BOXAA *baas)
|
||
|
{
|
||
|
l_int32 i, j, ny, nb, nbox;
|
||
|
BOX *box;
|
||
|
BOXA *boxa;
|
||
|
BOXAA *baad;
|
||
|
|
||
|
PROCNAME("boxaaTranspose");
|
||
|
|
||
|
if (!baas)
|
||
|
return (BOXAA *)ERROR_PTR("baas not defined", procName, NULL);
|
||
|
if ((ny = boxaaGetCount(baas)) == 0)
|
||
|
return (BOXAA *)ERROR_PTR("baas empty", procName, NULL);
|
||
|
|
||
|
/* Make sure that each boxa in baas has the same number of boxes */
|
||
|
for (i = 0; i < ny; i++) {
|
||
|
if ((boxa = boxaaGetBoxa(baas, i, L_CLONE)) == NULL)
|
||
|
return (BOXAA *)ERROR_PTR("baas is missing a boxa", procName, NULL);
|
||
|
nb = boxaGetCount(boxa);
|
||
|
boxaDestroy(&boxa);
|
||
|
if (i == 0)
|
||
|
nbox = nb;
|
||
|
else if (nb != nbox)
|
||
|
return (BOXAA *)ERROR_PTR("boxa are not all the same size",
|
||
|
procName, NULL);
|
||
|
}
|
||
|
|
||
|
/* baad[i][j] = baas[j][i] */
|
||
|
baad = boxaaCreate(nbox);
|
||
|
for (i = 0; i < nbox; i++) {
|
||
|
boxa = boxaCreate(ny);
|
||
|
for (j = 0; j < ny; j++) {
|
||
|
box = boxaaGetBox(baas, j, i, L_COPY);
|
||
|
boxaAddBox(boxa, box, L_INSERT);
|
||
|
}
|
||
|
boxaaAddBoxa(baad, boxa, L_INSERT);
|
||
|
}
|
||
|
return baad;
|
||
|
}
|
||
|
|
||
|
|
||
|
/*!
|
||
|
* \brief boxaaAlignBox()
|
||
|
*
|
||
|
* \param[in] baa
|
||
|
* \param[in] box to be aligned with bext boxa in the baa, if possible
|
||
|
* \param[in] delta amount by which consecutive components can miss
|
||
|
* in overlap and still be included in the array
|
||
|
* \param[out] pindex 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
|
||
|
*
|
||
|
* <pre>
|
||
|
* Notes:
|
||
|
* (1) This is not greedy. It finds the boxa whose vertical
|
||
|
* extent has the closest overlap with the input box.
|
||
|
* </pre>
|
||
|
*/
|
||
|
l_ok
|
||
|
boxaaAlignBox(BOXAA *baa,
|
||
|
BOX *box,
|
||
|
l_int32 delta,
|
||
|
l_int32 *pindex)
|
||
|
{
|
||
|
l_int32 i, n, m, y, yt, h, ht, ovlp, maxovlp, maxindex;
|
||
|
BOX *boxt;
|
||
|
BOXA *boxa;
|
||
|
|
||
|
PROCNAME("boxaaAlignBox");
|
||
|
|
||
|
if (pindex) *pindex = 0;
|
||
|
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) {
|
||
|
boxaDestroy(&boxa);
|
||
|
L_WARNING("no boxes in boxa\n", procName);
|
||
|
continue;
|
||
|
}
|
||
|
boxaGetExtent(boxa, NULL, NULL, &boxt);
|
||
|
boxGetGeometry(boxt, NULL, &yt, NULL, &ht);
|
||
|
boxDestroy(&boxt);
|
||
|
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;
|
||
|
}
|