#include "allheaders.h"
static PIX *pixFindMinRunsOrthogonal(PIX *pixs, l_float32 angle, l_int32 depth);
/*-----------------------------------------------------------------------*
* Label pixels by membership in runs *
*-----------------------------------------------------------------------*/
/*!
* \brief pixStrokeWidthTransform()
*
* \param[in] pixs 1 bpp
* \param[in] color 0 for white runs, 1 for black runs
* \param[in] depth of pixd: 8 or 16 bpp
* \param[in] nangles 2, 4, 6 or 8
* \return pixd 8 or 16 bpp, or NULL on error
*
*
* Notes:
* (1) The dest Pix is 8 or 16 bpp, with the pixel values
* equal to the stroke width in which it is a member.
* The values are clipped to the max pixel value if necessary.
* (2) %color determines if we're labelling white or black strokes.
* (3) A pixel that is not a member of the chosen color gets
* value 0; it belongs to a width of length 0 of the
* chosen color.
* (4) This chooses, for each dest pixel, the minimum of sets
* of runlengths through each pixel. Here are the sets:
* nangles increment set
* ------- --------- --------------------------------
* 2 90 {0, 90}
* 4 45 {0, 45, 90, 135}
* 6 30 {0, 30, 60, 90, 120, 150}
* 8 22.5 {0, 22.5, 45, 67.5, 90, 112.5, 135, 157.5}
* (5) Runtime scales linearly with (%nangles - 2).
*
*/
PIX *
pixStrokeWidthTransform(PIX *pixs,
l_int32 color,
l_int32 depth,
l_int32 nangles)
{
l_float32 angle, pi;
PIX *pixh, *pixv, *pixt, *pixg1, *pixg2, *pixg3, *pixg4;
PROCNAME("pixStrokeWidthTransform");
if (!pixs || pixGetDepth(pixs) != 1)
return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
if (depth != 8 && depth != 16)
return (PIX *)ERROR_PTR("depth must be 8 or 16 bpp", procName, NULL);
if (nangles != 2 && nangles != 4 && nangles != 6 && nangles != 8)
return (PIX *)ERROR_PTR("nangles not in {2,4,6,8}", procName, NULL);
/* Use fg runs for evaluation */
if (color == 0)
pixt = pixInvert(NULL, pixs);
else
pixt = pixClone(pixs);
/* Find min length at 0 and 90 degrees */
pixh = pixRunlengthTransform(pixt, 1, L_HORIZONTAL_RUNS, depth);
pixv = pixRunlengthTransform(pixt, 1, L_VERTICAL_RUNS, depth);
pixg1 = pixMinOrMax(NULL, pixh, pixv, L_CHOOSE_MIN);
pixDestroy(&pixh);
pixDestroy(&pixv);
pixg2 = pixg3 = pixg4 = NULL;
pi = 3.1415926535f;
if (nangles == 4 || nangles == 8) {
/* Find min length at +45 and -45 degrees */
angle = pi / 4.0;
pixg2 = pixFindMinRunsOrthogonal(pixt, angle, depth);
}
if (nangles == 6) {
/* Find min length at +30 and -60 degrees */
angle = pi / 6.0;
pixg2 = pixFindMinRunsOrthogonal(pixt, angle, depth);
/* Find min length at +60 and -30 degrees */
angle = pi / 3.0;
pixg3 = pixFindMinRunsOrthogonal(pixt, angle, depth);
}
if (nangles == 8) {
/* Find min length at +22.5 and -67.5 degrees */
angle = pi / 8.0;
pixg3 = pixFindMinRunsOrthogonal(pixt, angle, depth);
/* Find min length at +67.5 and -22.5 degrees */
angle = 3.0 * pi / 8.0;
pixg4 = pixFindMinRunsOrthogonal(pixt, angle, depth);
}
pixDestroy(&pixt);
if (nangles > 2)
pixMinOrMax(pixg1, pixg1, pixg2, L_CHOOSE_MIN);
if (nangles > 4)
pixMinOrMax(pixg1, pixg1, pixg3, L_CHOOSE_MIN);
if (nangles > 6)
pixMinOrMax(pixg1, pixg1, pixg4, L_CHOOSE_MIN);
pixDestroy(&pixg2);
pixDestroy(&pixg3);
pixDestroy(&pixg4);
return pixg1;
}
/*!
* \brief pixFindMinRunsOrthogonal()
*
* \param[in] pixs 1 bpp
* \param[in] angle in radians
* \param[in] depth of pixd: 8 or 16 bpp
* \return pixd 8 or 16 bpp, or NULL on error
*
*
* Notes:
* (1) This computes, for each fg pixel in pixs, the minimum of
* the runlengths going through that pixel in two orthogonal
* directions: at %angle and at (90 + %angle).
* (2) We use rotation by shear because the forward and backward
* rotations by the same angle are exact inverse operations.
* As a result, the nonzero pixels in pixd correspond exactly
* to the fg pixels in pixs. This is not the case with
* sampled rotation, due to spatial quantization. Nevertheless,
* the result suffers from lack of exact correspondence
* between original and rotated pixels, also due to spatial
* quantization, causing some boundary pixels to be
* shifted from bg to fg or v.v.
*
*/
static PIX *
pixFindMinRunsOrthogonal(PIX *pixs,
l_float32 angle,
l_int32 depth)
{
l_int32 w, h, diag, xoff, yoff;
PIX *pixb, *pixr, *pixh, *pixv, *pixg1, *pixg2, *pixd;
BOX *box;
PROCNAME("pixFindMinRunsOrthogonal");
if (!pixs || pixGetDepth(pixs) != 1)
return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
/* Rasterop into the center of a sufficiently large image
* so we don't lose pixels for any rotation angle. */
pixGetDimensions(pixs, &w, &h, NULL);
diag = (l_int32)(sqrt((l_float64)(w * w + h * h)) + 2.5);
xoff = (diag - w) / 2;
yoff = (diag - h) / 2;
pixb = pixCreate(diag, diag, 1);
pixRasterop(pixb, xoff, yoff, w, h, PIX_SRC, pixs, 0, 0);
/* Rotate about the 'center', get the min of orthogonal transforms,
* rotate back, and crop the part corresponding to pixs. */
pixr = pixRotateShear(pixb, diag / 2, diag / 2, angle, L_BRING_IN_WHITE);
pixh = pixRunlengthTransform(pixr, 1, L_HORIZONTAL_RUNS, depth);
pixv = pixRunlengthTransform(pixr, 1, L_VERTICAL_RUNS, depth);
pixg1 = pixMinOrMax(NULL, pixh, pixv, L_CHOOSE_MIN);
pixg2 = pixRotateShear(pixg1, diag / 2, diag / 2, -angle, L_BRING_IN_WHITE);
box = boxCreate(xoff, yoff, w, h);
pixd = pixClipRectangle(pixg2, box, NULL);
pixDestroy(&pixb);
pixDestroy(&pixr);
pixDestroy(&pixh);
pixDestroy(&pixv);
pixDestroy(&pixg1);
pixDestroy(&pixg2);
boxDestroy(&box);
return pixd;
}
/*!
* \brief pixRunlengthTransform()
*
* \param[in] pixs 1 bpp
* \param[in] color 0 for white runs, 1 for black runs
* \param[in] direction L_HORIZONTAL_RUNS, L_VERTICAL_RUNS
* \param[in] depth 8 or 16 bpp
* \return pixd 8 or 16 bpp, or NULL on error
*
*
* Notes:
* (1) The dest Pix is 8 or 16 bpp, with the pixel values
* equal to the runlength in which it is a member.
* The length is clipped to the max pixel value if necessary.
* (2) %color determines if we're labelling white or black runs.
* (3) A pixel that is not a member of the chosen color gets
* value 0; it belongs to a run of length 0 of the
* chosen color.
* (4) To convert for maximum dynamic range, either linear or
* log, use pixMaxDynamicRange().
*
*/
PIX *
pixRunlengthTransform(PIX *pixs,
l_int32 color,
l_int32 direction,
l_int32 depth)
{
l_int32 i, j, w, h, wpld, bufsize, maxsize, n;
l_int32 *start, *end, *buffer;
l_uint32 *datad, *lined;
PIX *pixt, *pixd;
PROCNAME("pixRunlengthTransform");
if (!pixs)
return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
if (pixGetDepth(pixs) != 1)
return (PIX *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
if (depth != 8 && depth != 16)
return (PIX *)ERROR_PTR("depth must be 8 or 16 bpp", procName, NULL);
pixGetDimensions(pixs, &w, &h, NULL);
if (direction == L_HORIZONTAL_RUNS)
maxsize = 1 + w / 2;
else if (direction == L_VERTICAL_RUNS)
maxsize = 1 + h / 2;
else
return (PIX *)ERROR_PTR("invalid direction", procName, NULL);
bufsize = L_MAX(w, h);
if (bufsize > 1000000) {
L_ERROR("largest image dimension = %d; too big\n", procName, bufsize);
return NULL;
}
if ((pixd = pixCreate(w, h, depth)) == NULL)
return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
datad = pixGetData(pixd);
wpld = pixGetWpl(pixd);
start = (l_int32 *)LEPT_CALLOC(maxsize, sizeof(l_int32));
end = (l_int32 *)LEPT_CALLOC(maxsize, sizeof(l_int32));
buffer = (l_int32 *)LEPT_CALLOC(bufsize, sizeof(l_int32));
/* Use fg runs for evaluation */
if (color == 0)
pixt = pixInvert(NULL, pixs);
else
pixt = pixClone(pixs);
if (direction == L_HORIZONTAL_RUNS) {
for (i = 0; i < h; i++) {
pixFindHorizontalRuns(pixt, i, start, end, &n);
runlengthMembershipOnLine(buffer, w, depth, start, end, n);
lined = datad + i * wpld;
if (depth == 8) {
for (j = 0; j < w; j++)
SET_DATA_BYTE(lined, j, buffer[j]);
} else { /* depth == 16 */
for (j = 0; j < w; j++)
SET_DATA_TWO_BYTES(lined, j, buffer[j]);
}
}
} else { /* L_VERTICAL_RUNS */
for (j = 0; j < w; j++) {
pixFindVerticalRuns(pixt, j, start, end, &n);
runlengthMembershipOnLine(buffer, h, depth, start, end, n);
if (depth == 8) {
for (i = 0; i < h; i++) {
lined = datad + i * wpld;
SET_DATA_BYTE(lined, j, buffer[i]);
}
} else { /* depth == 16 */
for (i = 0; i < h; i++) {
lined = datad + i * wpld;
SET_DATA_TWO_BYTES(lined, j, buffer[i]);
}
}
}
}
pixDestroy(&pixt);
LEPT_FREE(start);
LEPT_FREE(end);
LEPT_FREE(buffer);
return pixd;
}
/*-----------------------------------------------------------------------*
* Find runs along horizontal and vertical lines *
*-----------------------------------------------------------------------*/
/*!
* \brief pixFindHorizontalRuns()
*
* \param[in] pix 1 bpp
* \param[in] y line to traverse
* \param[in] xstart returns array of start positions for fg runs
* \param[in] xend returns array of end positions for fg runs
* \param[out] pn the number of runs found
* \return 0 if OK; 1 on error
*
*
* Notes:
* (1) This finds foreground horizontal runs on a single scanline.
* (2) To find background runs, use pixInvert() before applying
* this function.
* (3) %xstart and %xend arrays are input. They should be
* of size w/2 + 1 to insure that they can hold
* the maximum number of runs in the raster line.
*
*/
l_ok
pixFindHorizontalRuns(PIX *pix,
l_int32 y,
l_int32 *xstart,
l_int32 *xend,
l_int32 *pn)
{
l_int32 inrun; /* boolean */
l_int32 index, w, h, d, j, wpl, val;
l_uint32 *line;
PROCNAME("pixFindHorizontalRuns");
if (!pn)
return ERROR_INT("&n not defined", procName, 1);
*pn = 0;
if (!pix)
return ERROR_INT("pix not defined", procName, 1);
pixGetDimensions(pix, &w, &h, &d);
if (d != 1)
return ERROR_INT("pix not 1 bpp", procName, 1);
if (y < 0 || y >= h)
return ERROR_INT("y not in [0 ... h - 1]", procName, 1);
if (!xstart)
return ERROR_INT("xstart not defined", procName, 1);
if (!xend)
return ERROR_INT("xend not defined", procName, 1);
wpl = pixGetWpl(pix);
line = pixGetData(pix) + y * wpl;
inrun = FALSE;
index = 0;
for (j = 0; j < w; j++) {
val = GET_DATA_BIT(line, j);
if (!inrun) {
if (val) {
xstart[index] = j;
inrun = TRUE;
}
} else {
if (!val) {
xend[index++] = j - 1;
inrun = FALSE;
}
}
}
/* Finish last run if necessary */
if (inrun)
xend[index++] = w - 1;
*pn = index;
return 0;
}
/*!
* \brief pixFindVerticalRuns()
*
* \param[in] pix 1 bpp
* \param[in] x line to traverse
* \param[in] ystart returns array of start positions for fg runs
* \param[in] yend returns array of end positions for fg runs
* \param[out] pn the number of runs found
* \return 0 if OK; 1 on error
*
*
* Notes:
* (1) This finds foreground vertical runs on a single scanline.
* (2) To find background runs, use pixInvert() before applying
* this function.
* (3) %ystart and %yend arrays are input. They should be
* of size h/2 + 1 to insure that they can hold
* the maximum number of runs in the raster line.
*
*/
l_ok
pixFindVerticalRuns(PIX *pix,
l_int32 x,
l_int32 *ystart,
l_int32 *yend,
l_int32 *pn)
{
l_int32 inrun; /* boolean */
l_int32 index, w, h, d, i, wpl, val;
l_uint32 *data, *line;
PROCNAME("pixFindVerticalRuns");
if (!pn)
return ERROR_INT("&n not defined", procName, 1);
*pn = 0;
if (!pix)
return ERROR_INT("pix not defined", procName, 1);
pixGetDimensions(pix, &w, &h, &d);
if (d != 1)
return ERROR_INT("pix not 1 bpp", procName, 1);
if (x < 0 || x >= w)
return ERROR_INT("x not in [0 ... w - 1]", procName, 1);
if (!ystart)
return ERROR_INT("ystart not defined", procName, 1);
if (!yend)
return ERROR_INT("yend not defined", procName, 1);
wpl = pixGetWpl(pix);
data = pixGetData(pix);
inrun = FALSE;
index = 0;
for (i = 0; i < h; i++) {
line = data + i * wpl;
val = GET_DATA_BIT(line, x);
if (!inrun) {
if (val) {
ystart[index] = i;
inrun = TRUE;
}
} else {
if (!val) {
yend[index++] = i - 1;
inrun = FALSE;
}
}
}
/* Finish last run if necessary */
if (inrun)
yend[index++] = h - 1;
*pn = index;
return 0;
}
/*-----------------------------------------------------------------------*
* Find max runs along horizontal and vertical lines *
*-----------------------------------------------------------------------*/
/*!
* \brief pixFindMaxRuns()
*
* \param[in] pix 1 bpp
* \param[in] direction L_HORIZONTAL_RUNS or L_VERTICAL_RUNS
* \param[out] pnastart [optional] start locations of longest runs
* \return na of lengths of runs, or NULL on error
*
*
* Notes:
* (1) This finds the longest foreground runs by row or column
* (2) To find background runs, use pixInvert() before applying
* this function.
*
*/
NUMA *
pixFindMaxRuns(PIX *pix,
l_int32 direction,
NUMA **pnastart)
{
l_int32 w, h, i, start, size;
NUMA *nasize;
PROCNAME("pixFindMaxRuns");
if (pnastart) *pnastart = NULL;
if (direction != L_HORIZONTAL_RUNS && direction != L_VERTICAL_RUNS)
return (NUMA *)ERROR_PTR("direction invalid", procName, NULL);
if (!pix || pixGetDepth(pix) != 1)
return (NUMA *)ERROR_PTR("pix undefined or not 1 bpp", procName, NULL);
pixGetDimensions(pix, &w, &h, NULL);
nasize = numaCreate(w);
if (pnastart) *pnastart = numaCreate(w);
if (direction == L_HORIZONTAL_RUNS) {
for (i = 0; i < h; i++) {
pixFindMaxHorizontalRunOnLine(pix, i, &start, &size);
numaAddNumber(nasize, size);
if (pnastart) numaAddNumber(*pnastart, start);
}
} else { /* vertical scans */
for (i = 0; i < w; i++) {
pixFindMaxVerticalRunOnLine(pix, i, &start, &size);
numaAddNumber(nasize, size);
if (pnastart) numaAddNumber(*pnastart, start);
}
}
return nasize;
}
/*!
* \brief pixFindMaxHorizontalRunOnLine()
*
* \param[in] pix 1 bpp
* \param[in] y line to traverse
* \param[out] pxstart [optional] start position
* \param[out] psize the size of the run
* \return 0 if OK; 1 on error
*
*
* Notes:
* (1) This finds the longest foreground horizontal run on a scanline.
* (2) To find background runs, use pixInvert() before applying
* this function.
*
*/
l_ok
pixFindMaxHorizontalRunOnLine(PIX *pix,
l_int32 y,
l_int32 *pxstart,
l_int32 *psize)
{
l_int32 inrun; /* boolean */
l_int32 w, h, j, wpl, val, maxstart, maxsize, length, start;
l_uint32 *line;
PROCNAME("pixFindMaxHorizontalRunOnLine");
if (pxstart) *pxstart = 0;
if (!psize)
return ERROR_INT("&size not defined", procName, 1);
*psize = 0;
if (!pix || pixGetDepth(pix) != 1)
return ERROR_INT("pix not defined or not 1 bpp", procName, 1);
pixGetDimensions(pix, &w, &h, NULL);
if (y < 0 || y >= h)
return ERROR_INT("y not in [0 ... h - 1]", procName, 1);
wpl = pixGetWpl(pix);
line = pixGetData(pix) + y * wpl;
inrun = FALSE;
start = 0;
maxstart = 0;
maxsize = 0;
for (j = 0; j < w; j++) {
val = GET_DATA_BIT(line, j);
if (!inrun) {
if (val) {
start = j;
inrun = TRUE;
}
} else if (!val) { /* run just ended */
length = j - start;
if (length > maxsize) {
maxsize = length;
maxstart = start;
}
inrun = FALSE;
}
}
if (inrun) { /* a run has continued to the end of the row */
length = j - start;
if (length > maxsize) {
maxsize = length;
maxstart = start;
}
}
if (pxstart) *pxstart = maxstart;
*psize = maxsize;
return 0;
}
/*!
* \brief pixFindMaxVerticalRunOnLine()
*
* \param[in] pix 1 bpp
* \param[in] x column to traverse
* \param[out] pystart [optional] start position
* \param[out] psize the size of the run
* \return 0 if OK; 1 on error
*
*
* Notes:
* (1) This finds the longest foreground vertical run on a scanline.
* (2) To find background runs, use pixInvert() before applying
* this function.
*
*/
l_ok
pixFindMaxVerticalRunOnLine(PIX *pix,
l_int32 x,
l_int32 *pystart,
l_int32 *psize)
{
l_int32 inrun; /* boolean */
l_int32 w, h, i, wpl, val, maxstart, maxsize, length, start;
l_uint32 *data, *line;
PROCNAME("pixFindMaxVerticalRunOnLine");
if (pystart) *pystart = 0;
if (!psize)
return ERROR_INT("&size not defined", procName, 1);
*psize = 0;
if (!pix || pixGetDepth(pix) != 1)
return ERROR_INT("pix not defined or not 1 bpp", procName, 1);
pixGetDimensions(pix, &w, &h, NULL);
if (x < 0 || x >= w)
return ERROR_INT("x not in [0 ... w - 1]", procName, 1);
wpl = pixGetWpl(pix);
data = pixGetData(pix);
inrun = FALSE;
start = 0;
maxstart = 0;
maxsize = 0;
for (i = 0; i < h; i++) {
line = data + i * wpl;
val = GET_DATA_BIT(line, x);
if (!inrun) {
if (val) {
start = i;
inrun = TRUE;
}
} else if (!val) { /* run just ended */
length = i - start;
if (length > maxsize) {
maxsize = length;
maxstart = start;
}
inrun = FALSE;
}
}
if (inrun) { /* a run has continued to the end of the column */
length = i - start;
if (length > maxsize) {
maxsize = length;
maxstart = start;
}
}
if (pystart) *pystart = maxstart;
*psize = maxsize;
return 0;
}
/*-----------------------------------------------------------------------*
* Compute runlength-to-membership transform on a line *
*-----------------------------------------------------------------------*/
/*!
* \brief runlengthMembershipOnLine()
*
* \param[in] buffer into which full line of data is placed
* \param[in] size full size of line; w or h
* \param[in] depth 8 or 16 bpp
* \param[in] start array of start positions for fg runs
* \param[in] end array of end positions for fg runs
* \param[in] n the number of runs
* \return 0 if OK; 1 on error
*
*
* Notes:
* (1) Converts a set of runlengths into a buffer of
* runlength membership values.
* (2) Initialization of the array gives pixels that are
* not within a run the value 0.
*
*/
l_ok
runlengthMembershipOnLine(l_int32 *buffer,
l_int32 size,
l_int32 depth,
l_int32 *start,
l_int32 *end,
l_int32 n)
{
l_int32 i, j, first, last, diff, max;
PROCNAME("runlengthMembershipOnLine");
if (!buffer)
return ERROR_INT("buffer not defined", procName, 1);
if (!start)
return ERROR_INT("start not defined", procName, 1);
if (!end)
return ERROR_INT("end not defined", procName, 1);
if (depth == 8)
max = 0xff;
else /* depth == 16 */
max = 0xffff;
memset(buffer, 0, 4 * size);
for (i = 0; i < n; i++) {
first = start[i];
last = end[i];
diff = last - first + 1;
diff = L_MIN(diff, max);
for (j = first; j <= last; j++)
buffer[j] = diff;
}
return 0;
}
/*-----------------------------------------------------------------------*
* Make byte position LUT *
*-----------------------------------------------------------------------*/
/*!
* \brief makeMSBitLocTab()
*
* \param[in] bitval either 0 or 1
* \return table: for an input byte, the MS bit location, starting at 0
* with the MSBit in the byte, or NULL on error.
*
*
* Notes:
* (1) If %bitval == 1, it finds the leftmost ON pixel in a byte;
* otherwise if %bitval == 0, it finds the leftmost OFF pixel.
* (2) If there are no pixels of the indicated color in the byte,
* this returns 8.
*
*/
l_int32 *
makeMSBitLocTab(l_int32 bitval)
{
l_int32 i, j;
l_int32 *tab;
l_uint8 byte, mask;
tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
for (i = 0; i < 256; i++) {
byte = (l_uint8)i;
if (bitval == 0)
byte = ~byte;
tab[i] = 8;
mask = 0x80;
for (j = 0; j < 8; j++) {
if (byte & mask) {
tab[i] = j;
break;
}
mask >>= 1;
}
}
return tab;
}