runlength.c

Go to the documentation of this file.

/*====================================================================*
 -  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.
 *====================================================================*/

#include <string.h>
#include <math.h>
#include "allheaders.h"

static PIX *pixFindMinRunsOrthogonal(PIX *pixs, l_float32 angle, l_int32 depth);


/*-----------------------------------------------------------------------*
 *                   Label pixels by membership in runs                  *
 *-----------------------------------------------------------------------*/
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.1415926535;
    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;
}


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;
}


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           *
 *-----------------------------------------------------------------------*/
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;
}


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          *
 *-----------------------------------------------------------------------*/
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;
}


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;
}


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        *
 *-----------------------------------------------------------------------*/
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                          *
 *-----------------------------------------------------------------------*/
l_int32 *
makeMSBitLocTab(l_int32  bitval)
{
l_int32   i, j;
l_int32  *tab;
l_uint8   byte, mask;

    PROCNAME("makeMSBitLocTab");

    if ((tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32))) == NULL)
        return (l_int32 *)ERROR_PTR("tab not made", procName, NULL);

    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;
}