/*====================================================================*
- 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.
*====================================================================*/
/*
* baseline.c
*
* Locate text baselines in an image
* NUMA *pixFindBaselines()
*
* Projective transform to remove local skew
* PIX *pixDeskewLocal()
*
* Determine local skew
* l_int32 pixGetLocalSkewTransform()
* NUMA *pixGetLocalSkewAngles()
*
* We have two apparently different functions here:
* - finding baselines
* - finding a projective transform to remove keystone warping
* The function pixGetLocalSkewAngles() returns an array of angles,
* one for each raster line, and the baselines of the text lines
* should intersect the left edge of the image with that angle.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "allheaders.h"
#ifndef NO_CONSOLE_IO
#define DEBUG_PLOT 0
#endif /* NO_CONSOLE_IO */
/* Min to travel after finding max before abandoning peak */
static const l_int32 MIN_DIST_IN_PEAK = 35;
/* Thresholds for peaks and zeros, relative to the max peak */
static const l_int32 PEAK_THRESHOLD_RATIO = 20;
static const l_int32 ZERO_THRESHOLD_RATIO = 100;
/* Default values for determining local skew */
static const l_int32 DEFAULT_SLICES = 10;
static const l_int32 DEFAULT_SWEEP_REDUCTION = 2;
static const l_int32 DEFAULT_BS_REDUCTION = 1;
static const l_float32 DEFAULT_SWEEP_RANGE = 5.; /* degrees */
static const l_float32 DEFAULT_SWEEP_DELTA = 1.; /* degrees */
static const l_float32 DEFAULT_MINBS_DELTA = 0.01; /* degrees */
/* Overlap slice fraction added to top and bottom of each slice */
static const l_float32 OVERLAP_FRACTION = 0.5;
/* Minimum allowed confidence (ratio) for accepting a value */
static const l_float32 MIN_ALLOWED_CONFIDENCE = 3.0;
/*---------------------------------------------------------------------*
* Locate text baselines in an image *
*---------------------------------------------------------------------*/
/*!
* pixFindBaselines()
*
* Input: pixs (1 bpp)
* &pta (<optional return> pairs of pts corresponding to
* approx. ends of each text line)
* debug (usually 0; set to 1 for debugging output)
* Return: na (of baseline y values), or null on error
*
* Notes:
* (1) Input binary image must have text lines already aligned
* horizontally. This can be done by either rotating the
* image with pixDeskew(), or, if a projective transform
* is required, by doing pixDeskewLocal() first.
* (2) Input null for &pta if you don't want this returned.
* The pta will come in pairs of points (left and right end
* of each baseline).
* (3) Caution: this will not work properly on text with multiple
* columns, where the lines are not aligned between columns.
* If there are multiple columns, they should be extracted
* separately before finding the baselines.
* (4) This function constructs different types of output
* for baselines; namely, a set of raster line values and
* a set of end points of each baseline.
* (5) This function was designed to handle short and long text lines
* without using dangerous thresholds on the peak heights. It does
* this by combining the differential signal with a morphological
* analysis of the locations of the text lines. One can also
* combine this data to normalize the peak heights, by weighting
* the differential signal in the region of each baseline
* by the inverse of the width of the text line found there.
* (6) There are various debug sections that can be turned on
* with the debug flag.
*/
NUMA *
pixFindBaselines(PIX *pixs,
PTA **ppta,
l_int32 debug)
{
l_int32 w, h, i, j, nbox, val1, val2, ndiff, bx, by, bw, bh;
l_int32 imaxloc, peakthresh, zerothresh, inpeak;
l_int32 mintosearch, max, maxloc, nloc, locval;
l_int32 *array;
l_float32 maxval;
BOXA *boxa1, *boxa2, *boxa3;
GPLOT *gplot;
NUMA *nasum, *nadiff, *naloc, *naval;
PIX *pixt1, *pixt2;
PTA *pta;
PROCNAME("pixFindBaselines");
if (!pixs)
return (NUMA *)ERROR_PTR("pixs not defined", procName, NULL);
pta = NULL;
if (ppta) {
pta = ptaCreate(0);
*ppta = pta;
}
/* Close up the text characters, removing noise */
pixt1 = pixMorphSequence(pixs, "c25.1 + e3.1", 0);
/* Save the difference of adjacent row sums.
* The high positive-going peaks are the baselines */
if ((nasum = pixCountPixelsByRow(pixt1, NULL)) == NULL)
return (NUMA *)ERROR_PTR("nasum not made", procName, NULL);
w = pixGetWidth(pixs);
h = pixGetHeight(pixs);
nadiff = numaCreate(h);
numaGetIValue(nasum, 0, &val2);
for (i = 0; i < h - 1; i++) {
val1 = val2;
numaGetIValue(nasum, i + 1, &val2);
numaAddNumber(nadiff, val1 - val2);
}
if (debug) /* show the difference signal */
gplotSimple1(nadiff, GPLOT_X11, "junkdiff", "difference");
/* Use the zeroes of the profile to locate each baseline. */
array = numaGetIArray(nadiff);
ndiff = numaGetCount(nadiff);
numaGetMax(nadiff, &maxval, &imaxloc);
/* Use this to begin locating a new peak: */
peakthresh = (l_int32)maxval / PEAK_THRESHOLD_RATIO;
/* Use this to begin a region between peaks: */
zerothresh = (l_int32)maxval / ZERO_THRESHOLD_RATIO;
naloc = numaCreate(0);
naval = numaCreate(0);
inpeak = FALSE;
for (i = 0; i < ndiff; i++) {
if (inpeak == FALSE) {
if (array[i] > peakthresh) { /* transition to in-peak */
inpeak = TRUE;
mintosearch = i + MIN_DIST_IN_PEAK; /* accept no zeros
* between i and mintosearch */
max = array[i];
maxloc = i;
}
}
else { /* inpeak == TRUE; look for max */
if (array[i] > max) {
max = array[i];
maxloc = i;
mintosearch = i + MIN_DIST_IN_PEAK;
}
else if (i > mintosearch && array[i] <= zerothresh) { /* leave */
inpeak = FALSE;
numaAddNumber(naval, max);
numaAddNumber(naloc, maxloc);
}
}
}
/* If array[ndiff-1] is max, eg. no descenders, baseline at bottom */
if (inpeak) {
numaAddNumber(naval, max);
numaAddNumber(naloc, maxloc);
}
FREE(array);
if (debug) { /* show the raster locations for the peaks */
gplot = gplotCreate("junkloc", GPLOT_X11, "Peak locations",
"rasterline", "height");
gplotAddPlot(gplot, naloc, naval, GPLOT_POINTS, "locs");
gplotMakeOutput(gplot);
gplotDestroy(&gplot);
}
/* Generate an approximate profile of text line width.
* First, filter the boxes of text, where there may be
* more than one box for a given textline. */
pixt2 = pixMorphSequence(pixt1, "r11 + c25.1 + o7.1 +c1.3", 0);
boxa1 = pixConnComp(pixt2, NULL, 4);
boxa2 = boxaTransform(boxa1, 0, 0, 4., 4.);
boxa3 = boxaSort(boxa2, L_SORT_BY_Y, L_SORT_INCREASING, NULL);
/* Then find the baseline segments */
if (pta) {
nloc = numaGetCount(naloc);
nbox = boxaGetCount(boxa3);
for (i = 0; i < nbox; i++) {
boxaGetBoxGeometry(boxa3, i, &bx, &by, &bw, &bh);
for (j = 0; j < nloc; j++) {
numaGetIValue(naloc, j, &locval);
if (L_ABS(locval - (by + bh)) > 25)
continue;
ptaAddPt(pta, bx, locval);
ptaAddPt(pta, bx + bw, locval);
break;
}
}
}
if (debug) { /* display baselines */
PIX *pixd;
l_int32 npts, x1, y1, x2, y2;
if (pta) {
pixd = pixConvertTo32(pixs);
npts = ptaGetCount(pta);
for (i = 0; i < npts; i += 2) {
ptaGetIPt(pta, i, &x1, &y1);
ptaGetIPt(pta, i + 1, &x2, &y2);
pixRenderLineArb(pixd, x1, y1, x2, y2, 1, 255, 0, 0);
}
pixDisplay(pixd, 200, 200);
pixWrite("junkbaselines", pixd, IFF_PNG);
pixDestroy(&pixd);
}
}
boxaDestroy(&boxa1);
boxaDestroy(&boxa2);
boxaDestroy(&boxa3);
pixDestroy(&pixt1);
pixDestroy(&pixt2);
numaDestroy(&nasum);
numaDestroy(&nadiff);
numaDestroy(&naval);
return naloc;
}
/*---------------------------------------------------------------------*
* Projective transform to remove local skew *
*---------------------------------------------------------------------*/
/*!
* pixDeskewLocal()
*
* Input: pixs
* nslices (the number of horizontal overlapping slices; must
* be larger than 1 and not exceed 20; use 0 for default)
* redsweep (sweep reduction factor: 1, 2, 4 or 8;
* use 0 for default value)
* redsearch (search reduction factor: 1, 2, 4 or 8, and
* not larger than redsweep; use 0 for default value)
* sweeprange (half the full range, assumed about 0; in degrees;
* use 0.0 for default value)
* sweepdelta (angle increment of sweep; in degrees;
* use 0.0 for default value)
* minbsdelta (min binary search increment angle; in degrees;
* use 0.0 for default value)
* Return: pixd, or null on error
*
* Notes:
* (1) This function allows deskew of a page whose skew changes
* approximately linearly with vertical position. It uses
* a projective tranform that in effect does a differential
* shear about the LHS of the page, and makes all text lines
* horizontal.
* (2) The origin of the keystoning can be either a cheap document
* feeder that rotates the page as it is passed through, or a
* camera image taken from either the left or right side
* of the vertical.
* (3) The image transformation is a projective warping,
* not a rotation. Apart from this function, the text lines
* must be properly aligned vertically with respect to each
* other. This can be done by pre-processing the page; e.g.,
* by rotating or horizontally shearing it.
* Typically, this can be achieved by vertically aligning
* the page edge.
*/
PIX *
pixDeskewLocal(PIX *pixs,
l_int32 nslices,
l_int32 redsweep,
l_int32 redsearch,
l_float32 sweeprange,
l_float32 sweepdelta,
l_float32 minbsdelta)
{
l_int32 ret;
PIX *pixd;
PTA *ptas, *ptad;
PROCNAME("pixDeskewLocal");
if (!pixs)
return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
/* Skew array gives skew angle (deg) as fctn of raster line
* where it intersects the LHS of the image */
ret = pixGetLocalSkewTransform(pixs, nslices, redsweep, redsearch,
sweeprange, sweepdelta, minbsdelta,
&ptas, &ptad);
if (ret != 0)
return (PIX *)ERROR_PTR("transform pts not found", procName, NULL);
/* Use a projective transform */
pixd = pixProjectiveSampledPta(pixs, ptad, ptas, L_BRING_IN_WHITE);
ptaDestroy(&ptas);
ptaDestroy(&ptad);
return pixd;
}
/*---------------------------------------------------------------------*
* Determine the local skew *
*---------------------------------------------------------------------*/
/*!
* pixGetLocalSkewTransform()
*
* Input: pixs
* nslices (the number of horizontal overlapping slices; must
* be larger than 1 and not exceed 20; use 0 for default)
* redsweep (sweep reduction factor: 1, 2, 4 or 8;
* use 0 for default value)
* redsearch (search reduction factor: 1, 2, 4 or 8, and
* not larger than redsweep; use 0 for default value)
* sweeprange (half the full range, assumed about 0; in degrees;
* use 0.0 for default value)
* sweepdelta (angle increment of sweep; in degrees;
* use 0.0 for default value)
* minbsdelta (min binary search increment angle; in degrees;
* use 0.0 for default value)
* &ptas (<return> 4 points in the source)
* &ptad (<return> the corresponding 4 pts in the dest)
* Return: 0 if OK, 1 on error
*
* Notes:
* (1) This generates two pairs of points in the src, each pair
* corresponding to a pair of points that would lie along
* the same raster line in a transformed (dewarped) image.
* (2) The sets of 4 src and 4 dest points returned by this function
* can then be used, in a projective or bilinear transform,
* to remove keystoning in the src.
*/
l_int32
pixGetLocalSkewTransform(PIX *pixs,
l_int32 nslices,
l_int32 redsweep,
l_int32 redsearch,
l_float32 sweeprange,
l_float32 sweepdelta,
l_float32 minbsdelta,
PTA **pptas,
PTA **pptad)
{
l_int32 w, h, i;
l_float32 deg2rad, angr, angd, dely;
NUMA *naskew;
PTA *ptas, *ptad;
PROCNAME("pixGetLocalSkewTransform");
if (!pptas || !pptad)
return ERROR_INT("&ptas and &ptad not defined", procName, 1);
*pptas = *pptad = NULL;
if (!pixs)
return ERROR_INT("pixs not defined", procName, 1);
if (nslices < 2 || nslices > 20)
nslices = DEFAULT_SLICES;
if (redsweep < 1 || redsweep > 8)
redsweep = DEFAULT_SWEEP_REDUCTION;
if (redsearch < 1 || redsearch > redsweep)
redsearch = DEFAULT_BS_REDUCTION;
if (sweeprange == 0.0)
sweeprange = DEFAULT_SWEEP_RANGE;
if (sweepdelta == 0.0)
sweepdelta = DEFAULT_SWEEP_DELTA;
if (minbsdelta == 0.0)
minbsdelta = DEFAULT_MINBS_DELTA;
naskew = pixGetLocalSkewAngles(pixs, nslices, redsweep, redsearch,
sweeprange, sweepdelta, minbsdelta,
NULL, NULL);
if (!naskew)
return ERROR_INT("naskew not made", procName, 1);
deg2rad = 3.14159265 / 180.;
w = pixGetWidth(pixs);
h = pixGetHeight(pixs);
ptas = ptaCreate(4);
ptad = ptaCreate(4);
*pptas = ptas;
*pptad = ptad;
/* Find i for skew line that intersects LHS at i and RHS at h / 20 */
for (i = 0; i < h; i++) {
numaGetFValue(naskew, i, &angd);
angr = angd * deg2rad;
dely = w * tan(angr);
if (i - dely > 0.05 * h)
break;
}
ptaAddPt(ptas, 0, i);
ptaAddPt(ptas, w - 1, i - dely);
ptaAddPt(ptad, 0, i);
ptaAddPt(ptad, w - 1, i);
/* Find i for skew line that intersects LHS at i and RHS at 19h / 20 */
for (i = h - 1; i > 0; i--) {
numaGetFValue(naskew, i, &angd);
angr = angd * deg2rad;
dely = w * tan(angr);
if (i - dely < 0.95 * h)
break;
}
ptaAddPt(ptas, 0, i);
ptaAddPt(ptas, w - 1, i - dely);
ptaAddPt(ptad, 0, i);
ptaAddPt(ptad, w - 1, i);
numaDestroy(&naskew);
return 0;
}
/*!
* pixGetLocalSkewAngles()
*
* Input: pixs
* nslices (the number of horizontal overlapping slices; must
* be larger than 1 and not exceed 20; use 0 for default)
* redsweep (sweep reduction factor: 1, 2, 4 or 8;
* use 0 for default value)
* redsearch (search reduction factor: 1, 2, 4 or 8, and
* not larger than redsweep; use 0 for default value)
* sweeprange (half the full range, assumed about 0; in degrees;
* use 0.0 for default value)
* sweepdelta (angle increment of sweep; in degrees;
* use 0.0 for default value)
* minbsdelta (min binary search increment angle; in degrees;
* use 0.0 for default value)
* &a (<optional return> slope of skew as fctn of y)
* &b (<optional return> intercept at y=0 of skew as fctn of y)
* Return: naskew, or null on error
*
* Notes:
* (1) The local skew is measured in a set of overlapping strips.
* We then do a least square linear fit parameters to get
* the slope and intercept parameters a and b in
* skew-angle = a * y + b (degrees)
* for the local skew as a function of raster line y.
* This is then used to make naskew, which can be interpreted
* as the computed skew angle (in degrees) at the left edge
* of each raster line.
* (2) naskew can then be used to find the baselines of text, because
* each text line has a baseline that should intersect
* the left edge of the image with the angle given by this
* array, evaluated at the raster line of intersection.
*/
NUMA *
pixGetLocalSkewAngles(PIX *pixs,
l_int32 nslices,
l_int32 redsweep,
l_int32 redsearch,
l_float32 sweeprange,
l_float32 sweepdelta,
l_float32 minbsdelta,
l_float32 *pa,
l_float32 *pb)
{
l_int32 w, h, hs, i, ystart, yend, ovlap, npts;
l_float32 angle, conf, ycenter, a, b;
BOX *box;
NUMA *naskew;
PIX *pix;
PTA *pta;
PROCNAME("pixGetLocalSkewAngles");
if (!pixs)
return (NUMA *)ERROR_PTR("pixs not defined", procName, NULL);
if (nslices < 2 || nslices > 20)
nslices = DEFAULT_SLICES;
if (redsweep < 1 || redsweep > 8)
redsweep = DEFAULT_SWEEP_REDUCTION;
if (redsearch < 1 || redsearch > redsweep)
redsearch = DEFAULT_BS_REDUCTION;
if (sweeprange == 0.0)
sweeprange = DEFAULT_SWEEP_RANGE;
if (sweepdelta == 0.0)
sweepdelta = DEFAULT_SWEEP_DELTA;
if (minbsdelta == 0.0)
minbsdelta = DEFAULT_MINBS_DELTA;
h = pixGetHeight(pixs);
w = pixGetWidth(pixs);
hs = h / nslices;
ovlap = (l_int32)(OVERLAP_FRACTION * hs);
pta = ptaCreate(nslices);
for (i = 0; i < nslices; i++) {
ystart = L_MAX(0, hs * i - ovlap);
yend = L_MIN(h - 1, hs * (i + 1) + ovlap);
ycenter = (ystart + yend) / 2;
box = boxCreate(0, ystart, w, yend - ystart + 1);
pix = pixClipRectangle(pixs, box, NULL);
pixFindSkewSweepAndSearch(pix, &angle, &conf, redsweep, redsearch,
sweeprange, sweepdelta, minbsdelta);
if (conf > MIN_ALLOWED_CONFIDENCE)
ptaAddPt(pta, ycenter, angle);
pixDestroy(&pix);
boxDestroy(&box);
}
/* ptaWriteStream(stderr, pta, 0); */
/* Do linear least squares fit */
if ((npts = ptaGetCount(pta)) < 2) {
ptaDestroy(&pta);
return (NUMA *)ERROR_PTR("can't fit skew", procName, NULL);
}
ptaGetLinearLSF(pta, &a, &b, NULL);
if (pa) *pa = a;
if (pb) *pb = b;
/* Make skew angle array as function of raster line */
naskew = numaCreate(h);
for (i = 0; i < h; i++) {
angle = a * i + b;
numaAddNumber(naskew, angle);
}
#if DEBUG_PLOT
{ NUMA *nax, *nay;
GPLOT *gplot;
ptaGetArrays(pta, &nax, &nay);
gplot = gplotCreate("junkskew", GPLOT_X11, "skew as fctn of y",
"y (in raster lines from top)", "angle (in degrees)");
gplotAddPlot(gplot, NULL, naskew, GPLOT_POINTS, "linear lsf");
gplotAddPlot(gplot, nax, nay, GPLOT_POINTS, "actual data pts");
gplotMakeOutput(gplot);
gplotDestroy(&gplot);
numaDestroy(&nax);
numaDestroy(&nay);
}
#endif /* DEBUG_PLOT */
ptaDestroy(&pta);
return naskew;
}