ccthin.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 "allheaders.h"

    /* ------------------------------------------------------------
     * The sels used here (and their rotated counterparts) are the
     * useful 3x3 Sels for thinning.   They are defined in sel2.c,
     * and the sets are constructed in selaMakeThinSets().
     * The notation is based on "Connectivity-preserving morphological
     * image transformations", a version of which can be found at
     *           http://www.leptonica.com/papers/conn.pdf
     * ------------------------------------------------------------ */

/*----------------------------------------------------------------*
 *                      CC-preserving thinning                    *
 *----------------------------------------------------------------*/
PIXA *
pixaThinConnected(PIXA    *pixas,
                  l_int32  type,
                  l_int32  connectivity,
                  l_int32  maxiters)
{
l_int32  i, n, d, same;
PIX     *pix1, *pix2;
PIXA    *pixad;
SELA    *sela;

    PROCNAME("pixaThinConnected");

    if (!pixas)
        return (PIXA *)ERROR_PTR("pixas not defined", procName, NULL);
    if (type != L_THIN_FG && type != L_THIN_BG)
        return (PIXA *)ERROR_PTR("invalid fg/bg type", procName, NULL);
    if (connectivity != 4 && connectivity != 8)
        return (PIXA *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
    if (maxiters == 0) maxiters = 10000;

    pixaVerifyDepth(pixas, &same, &d);
    if (d != 1)
        return (PIXA *)ERROR_PTR("pix are not all 1 bpp", procName, NULL);

    if (connectivity == 4)
        sela = selaMakeThinSets(1, 0);
    else  /* connectivity == 8 */
        sela = selaMakeThinSets(5, 0);

    n = pixaGetCount(pixas);
    pixad = pixaCreate(n);
    for (i = 0; i < n; i++) {
        pix1 = pixaGetPix(pixas, i, L_CLONE);
        pix2 = pixThinConnectedBySet(pix1, type, sela, maxiters);
        pixaAddPix(pixad, pix2, L_INSERT);
        pixDestroy(&pix1);
    }

    selaDestroy(&sela);
    return pixad;
}


PIX *
pixThinConnected(PIX     *pixs,
                 l_int32  type,
                 l_int32  connectivity,
                 l_int32  maxiters)
{
PIX   *pixd;
SELA  *sela;

    PROCNAME("pixThinConnected");

    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 (type != L_THIN_FG && type != L_THIN_BG)
        return (PIX *)ERROR_PTR("invalid fg/bg type", procName, NULL);
    if (connectivity != 4 && connectivity != 8)
        return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
    if (maxiters == 0) maxiters = 10000;

    if (connectivity == 4)
        sela = selaMakeThinSets(1, 0);
    else  /* connectivity == 8 */
        sela = selaMakeThinSets(5, 0);

    pixd = pixThinConnectedBySet(pixs, type, sela, maxiters);

    selaDestroy(&sela);
    return pixd;
}


PIX *
pixThinConnectedBySet(PIX     *pixs,
                      l_int32  type,
                      SELA    *sela,
                      l_int32  maxiters)
{
l_int32  i, j, r, nsels, same;
PIXA    *pixahmt;
PIX    **pixhmt;  /* array owned by pixahmt; do not destroy! */
PIX     *pix1, *pix2, *pixd;
SEL     *sel, *selr;

    PROCNAME("pixThinConnectedBySet");

    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 (type != L_THIN_FG && type != L_THIN_BG)
        return (PIX *)ERROR_PTR("invalid fg/bg type", procName, NULL);
    if (!sela)
        return (PIX *)ERROR_PTR("sela not defined", procName, NULL);
    if (maxiters == 0) maxiters = 10000;

        /* Set up array of temp pix to hold hmts */
    nsels = selaGetCount(sela);
    pixahmt = pixaCreate(nsels);
    for (i = 0; i < nsels; i++) {
        pix1 = pixCreateTemplate(pixs);
        pixaAddPix(pixahmt, pix1, L_INSERT);
    }
    pixhmt = pixaGetPixArray(pixahmt);
    if (!pixhmt) {
        pixaDestroy(&pixahmt);
        return (PIX *)ERROR_PTR("pixhmt array not made", procName, NULL);
    }

        /* Set up initial image for fg thinning */
    if (type == L_THIN_FG)
        pixd = pixCopy(NULL, pixs);
    else  /* bg thinning */
        pixd = pixInvert(NULL, pixs);

        /* Thin the fg, with up to maxiters iterations */
    for (i = 0; i < maxiters; i++) {
        pix1 = pixCopy(NULL, pixd);  /* test for completion */
        for (r = 0; r < 4; r++) {  /* over 90 degree rotations of Sels */
            for (j = 0; j < nsels; j++) {  /* over individual sels in sela */
                sel = selaGetSel(sela, j);  /* not a copy */
                selr = selRotateOrth(sel, r);
                pixHMT(pixhmt[j], pixd, selr);
                selDestroy(&selr);
                if (j > 0)
                    pixOr(pixhmt[0], pixhmt[0], pixhmt[j]);  /* accum result */
            }
            pixSubtract(pixd, pixd, pixhmt[0]);  /* remove result */
        }
        pixEqual(pixd, pix1, &same);
        pixDestroy(&pix1);
        if (same) {
/*            L_INFO("%d iterations to completion\n", procName, i); */
            break;
        }
    }

        /* This is a bit tricky. If we're thickening the foreground, then
         * we get a fg border of thickness equal to the number of
         * iterations.  This border is connected to all components that
         * were initially touching the border, but as it grows, it does
         * not touch other growing components -- it leaves a 1 pixel wide
         * background between it and the growing components, and that
         * thin background prevents the components from growing further.
         * This border can be entirely removed as follows:
         * (1) Subtract the original (unthickened) image pixs from the
         *     thickened image. This removes the pixels that were originally
         *     touching the border.
         * (2) Get all remaining pixels that are connected to the border.
         * (3) Remove those pixels from the thickened image.  */
    if (type == L_THIN_BG) {
        pixInvert(pixd, pixd);  /* finish with duality */
        pix1 = pixSubtract(NULL, pixd, pixs);
        pix2 = pixExtractBorderConnComps(pix1, 4);
        pixSubtract(pixd, pixd, pix2);
        pixDestroy(&pix1);
        pixDestroy(&pix2);
    }

    pixaDestroy(&pixahmt);
    return pixd;
}


SELA *
selaMakeThinSets(l_int32  index,
                 l_int32  debug)
{
SEL   *sel;
SELA  *sela1, *sela2, *sela3;

    PROCNAME("selaMakeThinSets");

    if (index < 1 || index > 11)
        return (SELA *)ERROR_PTR("invalid index", procName, NULL);

    sela2 = selaCreate(4);
    switch(index)
    {
    case 1:
        sela1 = sela4ccThin(NULL);
        selaFindSelByName(sela1, "sel_4_1", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_4_2", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_4_3", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        break;
    case 2:
        sela1 = sela4ccThin(NULL);
        selaFindSelByName(sela1, "sel_4_1", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_4_5", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_4_6", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        break;
    case 3:
        sela1 = sela4ccThin(NULL);
        selaFindSelByName(sela1, "sel_4_1", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_4_7", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        sel = selRotateOrth(sel, 1);
        selaAddSel(sela2, sel, "sel_4_7_rot", L_INSERT);
        break;
    case 4:
        sela1 = sela4and8ccThin(NULL);
        selaFindSelByName(sela1, "sel_48_1", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        sel = selRotateOrth(sel, 1);
        selaAddSel(sela2, sel, "sel_48_1_rot", L_INSERT);
        selaFindSelByName(sela1, "sel_48_2", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        break;
    case 5:
        sela1 = sela8ccThin(NULL);
        selaFindSelByName(sela1, "sel_8_2", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_3", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_5", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_6", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        break;
    case 6:
        sela1 = sela8ccThin(NULL);
        sela3 = sela4and8ccThin(NULL);
        selaFindSelByName(sela1, "sel_8_2", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_3", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela3, "sel_48_2", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaDestroy(&sela3);
        break;
    case 7:
        sela1 = sela8ccThin(NULL);
        selaFindSelByName(sela1, "sel_8_1", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_5", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_6", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        break;
    case 8:
        sela1 = sela8ccThin(NULL);
        selaFindSelByName(sela1, "sel_8_2", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_3", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_8", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_9", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        break;
    case 9:
        sela1 = sela8ccThin(NULL);
        selaFindSelByName(sela1, "sel_8_5", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_6", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_8_7", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        sel = selRotateOrth(sel, 1);
        selaAddSel(sela2, sel, "sel_8_7_rot", L_INSERT);
        break;
    case 10:  /* thicken for this one; use just a few iterations */
        sela1 = sela4ccThin(NULL);
        selaFindSelByName(sela1, "sel_4_2", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        selaFindSelByName(sela1, "sel_4_3", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        break;
    case 11:  /* thicken for this one; use just a few iterations */
        sela1 = sela8ccThin(NULL);
        selaFindSelByName(sela1, "sel_8_4", NULL, &sel);
        selaAddSel(sela2, sel, NULL, L_COPY);
        break;
    }

        /* Optionally display the sel set */
    if (debug) {
        PIX  *pix1;
        char  buf[32];
        lept_mkdir("/lept/sels");
        pix1 = selaDisplayInPix(sela2, 35, 3, 15, 4);
        snprintf(buf, sizeof(buf), "/tmp/lept/sels/set%d.png", index);
        pixWrite(buf, pix1, IFF_PNG);
        pixDisplay(pix1, 100, 100);
        pixDestroy(&pix1);
    }

    selaDestroy(&sela1);
    return sela2;
}