/*====================================================================*

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

 *====================================================================*/

/*!

 * \file ccthin.c

 * <pre>

 *

 *     PIXA   *pixaThinConnected()

 *     PIX    *pixThinConnected()

 *     PIX    *pixThinConnectedBySet()

 *     SELA   *selaMakeThinSets()

 * </pre>

 */

#ifdef HAVE_CONFIG_H

#include <config_auto.h>

#endif  /* HAVE_CONFIG_H */

#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                    *

 *----------------------------------------------------------------*/

/*!

 * \brief   pixaThinConnected()

 *

 * \param[in]   pixas          of 1 bpp pix

 * \param[in]   type           L_THIN_FG, L_THIN_BG

 * \param[in]   connectivity   4 or 8

 * \param[in]   maxiters       max number of iters allowed;

 *                             use 0 to iterate until completion

 * \return  pixds, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) See notes in pixThinConnected().

 * </pre>

 */

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;

    if (!pixas)

        return (PIXA *)ERROR_PTR("pixas not defined", __func__, NULL);

    if (type != L_THIN_FG && type != L_THIN_BG)

        return (PIXA *)ERROR_PTR("invalid fg/bg type", __func__, NULL);

    if (connectivity != 4 && connectivity != 8)

        return (PIXA *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);

    if (maxiters == 0) maxiters = 10000;

    pixaVerifyDepth(pixas, &same, &d);

    if (d != 1)

        return (PIXA *)ERROR_PTR("pix are not all 1 bpp", __func__, 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;

}

/*!

 * \brief   pixThinConnected()

 *

 * \param[in]   pixs           1 bpp

 * \param[in]   type           L_THIN_FG, L_THIN_BG

 * \param[in]   connectivity   4 or 8

 * \param[in]   maxiters       max number of iters allowed;

 *                             use 0 to iterate until completion

 * \return  pixd, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) See "Connectivity-preserving morphological image transformations,"

 *          Dan S. Bloomberg, in SPIE Visual Communications and Image

 *          Processing, Conference 1606, pp. 320-334, November 1991,

 *          Boston, MA.   A web version is available at

 *              http://www.leptonica.com/papers/conn.pdf

 *      (2) This is a simple interface for two of the best iterative

 *          morphological thinning algorithms, for 4-c.c and 8-c.c.

 *          Each iteration uses a mixture of parallel operations

 *          (using several different 3x3 Sels) and serial operations.

 *          Specifically, each thinning iteration consists of

 *          four sequential thinnings from each of four directions.

 *          Each of these thinnings is a parallel composite

 *          operation, where the union of a set of HMTs are set

 *          subtracted from the input.  For 4-cc thinning, we

 *          use 3 HMTs in parallel, and for 8-cc thinning we use 4 HMTs.

 *      (3) A "good" thinning algorithm is one that generates a skeleton

 *          that is near the medial axis and has neither pruned

 *          real branches nor left extra dendritic branches.

 *      (4) Duality between operations on fg and bg require switching

 *          the connectivity.  To thin the foreground, which is the usual

 *          situation, use type == L_THIN_FG.  Thickening the foreground

 *          is equivalent to thinning the background (type == L_THIN_BG),

 *          where the alternate connectivity gets preserved.

 *          For example, to thicken the fg with 2 rounds of iterations

 *          using 4-c.c., thin the bg using Sels that preserve 8-connectivity:

 *             Pix *pix = pixThinConnected(pixs, L_THIN_BG, 8, 2);

 *      (5) This makes and destroys the sela set each time. It's not a large

 *          overhead, but if you are calling this thousands of times on

 *          very small images, you can avoid the overhead; e.g.

 *             Sela *sela = selaMakeThinSets(1, 0);  // for 4-c.c.

 *             Pix *pix = pixThinConnectedBySet(pixs, L_THIN_FG, sela, 0);

 *          using set 1 for 4-c.c. and set 5 for 8-c.c operations.

 * </pre>

 */

PIX *

pixThinConnected(PIX     *pixs,

                 l_int32  type,

                 l_int32  connectivity,

                 l_int32  maxiters)

{

PIX   *pixd;

SELA  *sela;

    if (!pixs)

        return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);

    if (pixGetDepth(pixs) != 1)

        return (PIX *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);

    if (type != L_THIN_FG && type != L_THIN_BG)

        return (PIX *)ERROR_PTR("invalid fg/bg type", __func__, NULL);

    if (connectivity != 4 && connectivity != 8)

        return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, 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;

}

/*!

 * \brief   pixThinConnectedBySet()

 *

 * \param[in]   pixs       1 bpp

 * \param[in]   type       L_THIN_FG, L_THIN_BG

 * \param[in]   sela       of Sels for parallel composite HMTs

 * \param[in]   maxiters   max number of iters allowed;

 *                         use 0 to iterate until completion

 * \return  pixd, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) See notes in pixThinConnected().

 *      (2) This takes a sela representing one of 11 sets of HMT Sels.

 *          The HMTs from this set are run in parallel and the result

 *          is OR'd before being subtracted from the source.  For each

 *          iteration, this "parallel" thin is performed four times

 *          sequentially, for sels rotated by 90 degrees in all four

 *          directions.

 *      (3) The "parallel" and "sequential" nomenclature is standard

 *          in digital filtering.  Here, "parallel" operations work on the

 *          same source (pixd), and accumulate the results in a temp

 *          image before actually applying them to the source (in this

 *          case, using an in-place subtraction).  "Sequential" operations

 *          operate directly on the source (pixd) to produce the result

 *          (in this case, with four sequential thinning operations, one

 *          from each of four directions).

 * </pre>

 */

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;

    if (!pixs)

        return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);

    if (pixGetDepth(pixs) != 1)

        return (PIX *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);

    if (type != L_THIN_FG && type != L_THIN_BG)

        return (PIX *)ERROR_PTR("invalid fg/bg type", __func__, NULL);

    if (!sela)

        return (PIX *)ERROR_PTR("sela not defined", __func__, 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", __func__, 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", __func__, 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;

}

/*!

 * \brief   selaMakeThinSets()

 *

 * \param[in]   index   into specific sets

 * \param[in]   debug   1 to output display of sela

 * \return  sela, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) These are specific sets of HMTs to be used in parallel for

 *          for thinning from each of four directions.

 *      (2) The sets are indexed as follows:

 *          For thinning (e.g., run to completion):

 *              index = 1     sel_4_1, sel_4_2, sel_4_3

 *              index = 2     sel_4_1, sel_4_5, sel_4_6

 *              index = 3     sel_4_1, sel_4_7, sel_4_7_rot

 *              index = 4     sel_48_1, sel_48_1_rot, sel_48_2

 *              index = 5     sel_8_2, sel_8_3, sel_8_5, sel_8_6

 *              index = 6     sel_8_2, sel_8_3, sel_48_2

 *              index = 7     sel_8_1, sel_8_5, sel_8_6

 *              index = 8     sel_8_2, sel_8_3, sel_8_8, sel_8_9

 *              index = 9     sel_8_5, sel_8_6, sel_8_7, sel_8_7_rot

 *          For thickening (e.g., just a few iterations):

 *              index = 10    sel_4_2, sel_4_3

 *              index = 11    sel_8_4

 *      (3) For a very smooth skeleton, use set 1 for 4 connected and

 *          set 5 for 8 connected thins.

 * </pre>

 */

SELA *

selaMakeThinSets(l_int32  index,

                 l_int32  debug)

{

SEL   *sel;

SELA  *sela1, *sela2, *sela3;

    if (index < 1 || index > 11)

        return (SELA *)ERROR_PTR("invalid index", __func__, 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;

}