Logo Search packages:      
Sourcecode: leptonlib version File versions  Download package

runlength.c

/*====================================================================*
 -  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 "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:  0 if OK; 1 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);

    w = pixGetWidth(pixs);
    h = pixGetHeight(pixs);
    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((void *)start);
    FREE((void *)end);
    FREE((void *)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, j, wpl, val;
l_uint32  *line;

    PROCNAME("pixFindHorizontalRuns");


    if (!pix)
        return ERROR_INT("pix not defined", procName, 1);
    if (pixGetDepth(pix) != 1)
        return ERROR_INT("pix not 1 bpp", procName, 1);
    if (y < 0 || y >= pixGetHeight(pix))
        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);
    if (!pn)
        return ERROR_INT("&n not defined", procName, 1);
    *pn = 0;

    w = pixGetWidth(pix);
    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, h, i, wpl, val;
l_uint32  *data, *line;

    PROCNAME("pixFindVerticalRuns");

    if (!pix)
        return ERROR_INT("pix not defined", procName, 1);
    if (pixGetDepth(pix) != 1)
        return ERROR_INT("pix not 1 bpp", procName, 1);
    if (x < 0 || x >= pixGetWidth(pix))
        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);
    if (!pn)
        return ERROR_INT("&n not defined", procName, 1);
    *pn = 0;

    h = pixGetHeight(pix);
    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.
 */
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 the MS bit location (starting at 0
 *              with the MSBit in the byte) of an input byte,
 *              or null on error.
 *
 *  Notes:
 *      (1) If bitval = 1, it finds the leftmost ON pixel in a byte;
 *          otherwise 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;
}



Generated by  Doxygen 1.6.0   Back to index