runlength.c

Go to the documentation of this file.

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

/*
 *  runlength.c
 *
 *     Label pixels by membership in runs
 *           PIX        *pixRunlengthTransform()
 *
 *     Find runs along horizontal and vertical lines
 *           l_int32     pixFindHorizontalRuns()
 *           l_int32     pixFindVerticalRuns()
 *
 *     Compute runlength-to-membership transform on a line
 *           l_int32     runlengthMembershipOnLine()
 *
 *     Make byte position LUT
 *           l_int32     makeMSBitLocTab()
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "allheaders.h"


/*-----------------------------------------------------------------------*
 *                   Label pixels by membership in runs                  *
 *-----------------------------------------------------------------------*/
/*!
 *  pixRunlengthTransform()
 *
 *      Input:   pixs (1 bpp)
 *               color (0 for white runs, 1 for black runs)
 *               direction (L_HORIZONTAL_RUNS, L_VERTICAL_RUNS)
 *               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) The 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 ((pixd = pixCreate(w, h, depth)) == NULL)
        return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
    datad = pixGetData(pixd);
    wpld = pixGetWpl(pixd);

    if ((start = (l_int32 *)CALLOC(maxsize, sizeof(l_int32))) == NULL)
        return (PIX *)ERROR_PTR("start not made", procName, NULL);
    if ((end = (l_int32 *)CALLOC(maxsize, sizeof(l_int32))) == NULL)
        return (PIX *)ERROR_PTR("end not made", procName, NULL);
    if ((buffer = (l_int32 *)CALLOC(bufsize, sizeof(l_int32))) == NULL)
        return (PIX *)ERROR_PTR("buffer not made", procName, NULL);

        /* 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);
    FREE(start);
    FREE(end);
    FREE(buffer);
    return pixd;
}


/*-----------------------------------------------------------------------*
 *               Find runs along horizontal and vertical lines           *
 *-----------------------------------------------------------------------*/
/*!
 *  pixFindHorizontalRuns()
 *
 *      Input:  pix (1 bpp)
 *              y (line to traverse)
 *              xstart (returns array of start positions for fg runs)
 *              xend (returns array of end positions for fg runs)
 *              &n  (<return> 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) The 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_int32
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;
}


/*!
 *  pixFindVerticalRuns()
 *
 *      Input:  pix (1 bpp)
 *              x (line to traverse)
 *              ystart (returns array of start positions for fg runs)
 *              yend (returns array of end positions for fg runs)
 *              &n   (<return> 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) The 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_int32
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;
}


/*-----------------------------------------------------------------------*
 *            Compute runlength-to-membership transform on a line        *
 *-----------------------------------------------------------------------*/
/*!
 *  runlengthMembershipOnLine()
 *
 *      Input:   buffer (into which full line of data is placed)
 *               size (full size of line; w or h)
 *               depth (8 or 16 bpp)
 *               start (array of start positions for fg runs)
 *               end (array of end positions for fg runs)
 *               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_int32
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                          *
 *-----------------------------------------------------------------------*/
/*!
 *  makeMSBitLocTab()
 *
 *      Input:  bitval (either 0 or 1)
 *      Return: table (giving, 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;

    PROCNAME("makeMSBitLocTab");

    if ((tab = (l_int32 *)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;
}