pixlabel.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"



/*-----------------------------------------------------------------------*
 *      Label pixels by an index for connected component membership      *
 *-----------------------------------------------------------------------*/
PIX *
pixConnCompTransform(PIX     *pixs,
                     l_int32  connect,
                     l_int32  depth)
{
l_int32  i, n, index, w, h, xb, yb, wb, hb;
BOXA    *boxa;
PIX     *pix1, *pix2, *pixd;
PIXA    *pixa;

    PROCNAME("pixConnCompTransform");

    if (!pixs || pixGetDepth(pixs) != 1)
        return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
    if (connect != 4 && connect != 8)
        return (PIX *)ERROR_PTR("connectivity must be 4 or 8", procName, NULL);
    if (depth != 0 && depth != 8 && depth != 16 && depth != 32)
        return (PIX *)ERROR_PTR("depth must be 0, 8, 16 or 32", procName, NULL);

    boxa = pixConnComp(pixs, &pixa, connect);
    n = pixaGetCount(pixa);
    boxaDestroy(&boxa);
    pixGetDimensions(pixs, &w, &h, NULL);
    if (depth == 0) {
        if (n < 254)
            depth = 8;
        else if (n < 0xfffe)
            depth = 16;
        else
            depth = 32;
    }
    pixd = pixCreate(w, h, depth);
    pixSetSpp(pixd, 1);
    if (n == 0) {  /* no fg */
        pixaDestroy(&pixa);
        return pixd;
    }

       /* Label each component and blit it in */
    for (i = 0; i < n; i++) {
        pixaGetBoxGeometry(pixa, i, &xb, &yb, &wb, &hb);
        pix1 = pixaGetPix(pixa, i, L_CLONE);
        if (depth == 8) {
            index = 1 + (i % 254);
            pix2 = pixConvert1To8(NULL, pix1, 0, index);
        } else if (depth == 16) {
            index = 1 + (i % 0xfffe);
            pix2 = pixConvert1To16(NULL, pix1, 0, index);
        } else {  /* depth == 32 */
            index = 1 + i;
            pix2 = pixConvert1To32(NULL, pix1, 0, index);
        }
        pixRasterop(pixd, xb, yb, wb, hb, PIX_PAINT, pix2, 0, 0);
        pixDestroy(&pix1);
        pixDestroy(&pix2);
    }

    pixaDestroy(&pixa);
    return pixd;
}


/*-----------------------------------------------------------------------*
 *         Label pixels by the area of their connected component         *
 *-----------------------------------------------------------------------*/
PIX *
pixConnCompAreaTransform(PIX     *pixs,
                         l_int32  connect)
{
l_int32   i, n, npix, w, h, xb, yb, wb, hb;
l_int32  *tab8;
BOXA     *boxa;
PIX      *pix1, *pix2, *pixd;
PIXA     *pixa;

    PROCNAME("pixConnCompAreaTransform");

    if (!pixs || pixGetDepth(pixs) != 1)
        return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
    if (connect != 4 && connect != 8)
        return (PIX *)ERROR_PTR("connectivity must be 4 or 8", procName, NULL);

    boxa = pixConnComp(pixs, &pixa, connect);
    n = pixaGetCount(pixa);
    boxaDestroy(&boxa);
    pixGetDimensions(pixs, &w, &h, NULL);
    pixd = pixCreate(w, h, 32);
    pixSetSpp(pixd, 1);
    if (n == 0) {  /* no fg */
        pixaDestroy(&pixa);
        return pixd;
    }

       /* Label each component and blit it in */
    tab8 = makePixelSumTab8();
    for (i = 0; i < n; i++) {
        pixaGetBoxGeometry(pixa, i, &xb, &yb, &wb, &hb);
        pix1 = pixaGetPix(pixa, i, L_CLONE);
        pixCountPixels(pix1, &npix, tab8);
        pix2 = pixConvert1To32(NULL, pix1, 0, npix);
        pixRasterop(pixd, xb, yb, wb, hb, PIX_PAINT, pix2, 0, 0);
        pixDestroy(&pix1);
        pixDestroy(&pix2);
    }

    pixaDestroy(&pixa);
    LEPT_FREE(tab8);
    return pixd;
}


/*-------------------------------------------------------------------------*
 *  Label pixels to allow incremental computation of connected components  *
 *-------------------------------------------------------------------------*/
l_ok
pixConnCompIncrInit(PIX     *pixs,
                    l_int32  conn,
                    PIX    **ppixd,
                    PTAA   **pptaa,
                    l_int32 *pncc)
{
l_int32  empty, w, h, ncc;
PIX     *pixd;
PTA     *pta;
PTAA    *ptaa;

    PROCNAME("pixConnCompIncrInit");

    if (ppixd) *ppixd = NULL;
    if (pptaa) *pptaa = NULL;
    if (pncc) *pncc = 0;
    if (!ppixd || !pptaa || !pncc)
        return ERROR_INT("&pixd, &ptaa, &ncc not all defined", procName, 1);
    if (!pixs || pixGetDepth(pixs) != 1)
        return ERROR_INT("pixs undefined or not 1 bpp", procName, 1);
    if (conn != 4 && conn != 8)
        return ERROR_INT("connectivity must be 4 or 8", procName, 1);

    pixGetDimensions(pixs, &w, &h, NULL);
    pixZero(pixs, &empty);
    if (empty) {
        *ppixd = pixCreate(w, h, 32);
        pixSetSpp(*ppixd, 1);
        pixSetSpecial(*ppixd, conn);
        *pptaa = ptaaCreate(0);
        pta = ptaCreate(1);
        ptaaAddPta(*pptaa, pta, L_INSERT);  /* reserve index 0 for background */
        return 0;
    }

        /* Set up the initial labeled image and indexed pixel arrays */
    if ((pixd = pixConnCompTransform(pixs, conn, 32)) == NULL)
        return ERROR_INT("pixd not made", procName, 1);
    pixSetSpecial(pixd, conn);
    *ppixd = pixd;
    if ((ptaa = ptaaIndexLabeledPixels(pixd, &ncc)) == NULL)
        return ERROR_INT("ptaa not made", procName, 1);
    *pptaa = ptaa;
    *pncc = ncc;
    return 0;
}


l_int32
pixConnCompIncrAdd(PIX       *pixs,
                   PTAA      *ptaa,
                   l_int32   *pncc,
                   l_float32  x,
                   l_float32  y,
                   l_int32    debug)
{
l_int32   conn, i, j, w, h, count, nvals, ns, firstindex;
l_uint32  val;
l_int32  *neigh;
PTA      *ptas, *ptad;

    PROCNAME("pixConnCompIncrAdd");

    if (!pixs || pixGetDepth(pixs) != 32)
        return ERROR_INT("pixs not defined or not 32 bpp", procName, 1);
    if (!ptaa)
        return ERROR_INT("ptaa not defined", procName, 1);
    if (!pncc)
        return ERROR_INT("&ncc not defined", procName, 1);
    conn = pixs->special;
    if (conn != 4 && conn != 8)
        return ERROR_INT("connectivity must be 4 or 8", procName, 1);
    pixGetDimensions(pixs, &w, &h, NULL);
    if (x < 0 || x >= w)
        return ERROR_INT("invalid x pixel location", procName, 1);
    if (y < 0 || y >= h)
        return ERROR_INT("invalid y pixel location", procName, 1);

    pixGetPixel(pixs, x, y, &val);
    if (val > 0)  /* already belongs to a set */
        return -1;

        /* Find unique neighbor pixel values in increasing order of value.
         * If %nvals > 0, these are returned in the %neigh array, which
         * is of size %nvals.  Note that the pixel values in each
         * connected component are used as the index into the pta
         * array of the ptaa, giving the pixel locations. */
    pixGetSortedNeighborValues(pixs, x, y, conn, &neigh, &nvals);

        /* If there are no neighbors, just add a new component */
    if (nvals == 0) {
        count = ptaaGetCount(ptaa);
        pixSetPixel(pixs, x, y, count);
        ptas = ptaCreate(1);
        ptaAddPt(ptas, x, y);
        ptaaAddPta(ptaa, ptas, L_INSERT);
        *pncc += 1;
        LEPT_FREE(neigh);
        return 0;
    }

        /* Otherwise, there is at least one neighbor.  Add the pixel
         * to the first neighbor c.c. */
    firstindex = neigh[0];
    pixSetPixel(pixs, x, y, firstindex);
    ptaaAddPt(ptaa, neigh[0], x, y);
    if (nvals == 1) {
        if (debug == 1)
            fprintf(stderr, "nvals = %d: neigh = (%d)\n", nvals, neigh[0]);
        LEPT_FREE(neigh);
        return 0;
    }

        /* If nvals > 1, there are at least 2 neighbors, so this pixel
         * joins at least one pair of existing c.c.  Join each component
         * to the first component in the list, which is the one with
         * the smallest integer label.  This is done in two steps:
         *  (a) re-label the pixels in the component to the label of the
         *      first component, and
         *  (b) save the pixel locations in the pta for the first component. */
    if (nvals == 2) {
        if (debug >= 1 && debug <= 2) {
            fprintf(stderr, "nvals = %d: neigh = (%d,%d)\n", nvals,
                    neigh[0], neigh[1]);
        }
    } else if (nvals == 3) {
        if (debug >= 1 && debug <= 3) {
            fprintf(stderr, "nvals = %d: neigh = (%d,%d,%d)\n", nvals,
                    neigh[0], neigh[1], neigh[2]);
        }
    } else {  /* nvals == 4 */
        if (debug >= 1 && debug <= 4) {
            fprintf(stderr, "nvals = %d: neigh = (%d,%d,%d,%d)\n", nvals,
                    neigh[0], neigh[1], neigh[2], neigh[3]);
        }
    }
    ptad = ptaaGetPta(ptaa, firstindex, L_CLONE);
    for (i = 1; i < nvals; i++) {
        ptas = ptaaGetPta(ptaa, neigh[i], L_CLONE);
        ns = ptaGetCount(ptas);
        for (j = 0; j < ns; j++) {  /* relabel pixels */
            ptaGetPt(ptas, j, &x, &y);
            pixSetPixel(pixs, x, y, firstindex);
        }
        ptaJoin(ptad, ptas, 0, -1);  /* add relabeled pixel locations */
        *pncc -= 1;
        ptaDestroy(&ptaa->pta[neigh[i]]);
        ptaDestroy(&ptas);  /* the clone */
    }
    ptaDestroy(&ptad);  /* the clone */
    LEPT_FREE(neigh);
    return 0;
}


l_ok
pixGetSortedNeighborValues(PIX       *pixs,
                           l_int32    x,
                           l_int32    y,
                           l_int32    conn,
                           l_int32  **pneigh,
                           l_int32   *pnvals)
{
l_int32       i, npt, index;
l_int32       neigh[4];
l_uint32      val;
l_float32     fx, fy;
L_ASET       *aset;
L_ASET_NODE  *node;
PTA          *pta;
RB_TYPE       key;

    PROCNAME("pixGetSortedNeighborValues");

    if (pneigh) *pneigh = NULL;
    if (pnvals) *pnvals = 0;
    if (!pneigh || !pnvals)
        return ERROR_INT("&neigh and &nvals not both defined", procName, 1);
    if (!pixs || pixGetDepth(pixs) < 8)
        return ERROR_INT("pixs not defined or depth < 8", procName, 1);

        /* Identify the locations of nearest neighbor pixels */
    if ((pta = ptaGetNeighborPixLocs(pixs, x, y, conn)) == NULL)
        return ERROR_INT("pta of neighbors not made", procName, 1);

        /* Find the pixel values and insert into a set as keys */
    aset = l_asetCreate(L_UINT_TYPE);
    npt = ptaGetCount(pta);
    for (i = 0; i < npt; i++) {
        ptaGetPt(pta, i, &fx, &fy);
        pixGetPixel(pixs, (l_int32)fx, (l_int32)fy, &val);
        key.utype = val;
        l_asetInsert(aset, key);
    }

        /* Extract the set keys and put them into the %neigh array.
         * Omit the value 0, which indicates the pixel doesn't
         * belong to one of the sets of connected components. */
    node = l_asetGetFirst(aset);
    index = 0;
    while (node) {
        val = node->key.utype;
        if (val > 0)
            neigh[index++] = (l_int32)val;
        node = l_asetGetNext(node);
    }
    *pnvals = index;
    if (index > 0) {
        *pneigh = (l_int32 *)LEPT_CALLOC(index, sizeof(l_int32));
        for (i = 0; i < index; i++)
            (*pneigh)[i] = neigh[i];
    }

    ptaDestroy(&pta);
    l_asetDestroy(&aset);
    return 0;
}


/*-----------------------------------------------------------------------*
 *          Label pixels with spatially-dependent color coding           *
 *-----------------------------------------------------------------------*/
PIX *
pixLocToColorTransform(PIX  *pixs)
{
l_int32    w, h, w2, h2, wpls, wplr, wplg, wplb, wplcc, i, j, rval, gval, bval;
l_float32  invw2, invh2;
l_uint32  *datas, *datar, *datag, *datab, *datacc;
l_uint32  *lines, *liner, *lineg, *lineb, *linecc;
PIX       *pix1, *pixcc, *pixr, *pixg, *pixb, *pixd;

    PROCNAME("pixLocToColorTransform");

    if (!pixs || pixGetDepth(pixs) != 1)
        return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);

        /* Label each pixel with the area of the c.c. to which it belongs.
         * Clip the result to 255 in an 8 bpp pix. This is used for
         * the blue component of pixd.  */
    pixGetDimensions(pixs, &w, &h, NULL);
    w2 = w / 2;
    h2 = h / 2;
    invw2 = 255.0 / (l_float32)w2;
    invh2 = 255.0 / (l_float32)h2;
    pix1 = pixConnCompAreaTransform(pixs, 8);
    pixcc = pixConvert32To8(pix1, L_LS_TWO_BYTES, L_CLIP_TO_FF);
    pixDestroy(&pix1);

        /* Label the red and green components depending on the location
         * of the fg pixels, in a way that is 4-fold rotationally invariant. */
    pixr = pixCreate(w, h, 8);
    pixg = pixCreate(w, h, 8);
    pixb = pixCreate(w, h, 8);
    wpls = pixGetWpl(pixs);
    wplr = pixGetWpl(pixr);
    wplg = pixGetWpl(pixg);
    wplb = pixGetWpl(pixb);
    wplcc = pixGetWpl(pixcc);
    datas = pixGetData(pixs);
    datar = pixGetData(pixr);
    datag = pixGetData(pixg);
    datab = pixGetData(pixb);
    datacc = pixGetData(pixcc);
    for (i = 0; i < h; i++) {
        lines = datas + i * wpls;
        liner = datar + i * wplr;
        lineg = datag + i * wplg;
        lineb = datab + i * wplb;
        linecc = datacc+ i * wplcc;
        for (j = 0; j < w; j++) {
            if (GET_DATA_BIT(lines, j) == 0) continue;
            if (w < h) {
                rval = invh2 * L_ABS((l_float32)(i - h2));
                gval = invw2 * L_ABS((l_float32)(j - w2));
            } else {
                rval = invw2 * L_ABS((l_float32)(j - w2));
                gval = invh2 * L_ABS((l_float32)(i - h2));
            }
            bval = GET_DATA_BYTE(linecc, j);
            SET_DATA_BYTE(liner, j, rval);
            SET_DATA_BYTE(lineg, j, gval);
            SET_DATA_BYTE(lineb, j, bval);
        }
    }
    pixd = pixCreateRGBImage(pixr, pixg, pixb);

    pixDestroy(&pixcc);
    pixDestroy(&pixr);
    pixDestroy(&pixg);
    pixDestroy(&pixb);
    return pixd;
}