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

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

 * <pre>

 *

 *      Binary seedfill (source: Luc Vincent)

 *               PIX         *pixSeedfillBinary()

 *               PIX         *pixSeedfillBinaryRestricted()

 *               static void  seedfillBinaryLow()

 *

 *      Applications of binary seedfill to find and fill holes,

 *      remove c.c. touching the border and fill bg from border:

 *               PIX         *pixHolesByFilling()

 *               PIX         *pixFillClosedBorders()

 *               PIX         *pixExtractBorderConnComps()

 *               PIX         *pixRemoveBorderConnComps()

 *               PIX         *pixFillBgFromBorder()

 *

 *      Hole-filling of components to bounding rectangle

 *               PIX         *pixFillHolesToBoundingRect()

 *

 *      Gray seedfill (source: Luc Vincent:fast-hybrid-grayscale-reconstruction)

 *               l_int32      pixSeedfillGray()

 *               l_int32      pixSeedfillGrayInv()

 *               static void  seedfillGrayLow()

 *               static void  seedfillGrayInvLow()

 *

 *      Gray seedfill (source: Luc Vincent: sequential-reconstruction algorithm)

 *               l_int32      pixSeedfillGraySimple()

 *               l_int32      pixSeedfillGrayInvSimple()

 *               static void  seedfillGrayLowSimple()

 *               static void  seedfillGrayInvLowSimple()

 *

 *      Gray seedfill variations

 *               PIX         *pixSeedfillGrayBasin()

 *

 *      Distance function (source: Luc Vincent)

 *               PIX         *pixDistanceFunction()

 *               static void  distanceFunctionLow()

 *

 *      Seed spread (based on distance function)

 *               PIX         *pixSeedspread()

 *               static void  seedspreadLow()

 *

 *      Local extrema:

 *               l_int32      pixLocalExtrema()

 *            static l_int32  pixQualifyLocalMinima()

 *               l_int32      pixSelectedLocalExtrema()

 *               PIX         *pixFindEqualValues()

 *

 *      Selection of minima in mask of connected components

 *               PTA         *pixSelectMinInConnComp()

 *

 *      Removal of seeded connected components from a mask

 *               PIX         *pixRemoveSeededComponents()

 *

 *

 *           ITERATIVE RASTER-ORDER SEEDFILL

 *

 *      The basic method in the Vincent seedfill (aka reconstruction)

 *      algorithm is simple.  We describe here the situation for

 *      binary seedfill.  Pixels are sampled in raster order in

 *      the seed image.  If they are 4-connected to ON pixels

 *      either directly above or to the left, and are not masked

 *      out by the mask image, they are turned on (or remain on).

 *      (Ditto for 8-connected, except you need to check 3 pixels

 *      on the previous line as well as the pixel to the left

 *      on the current line.  This is extra computational work

 *      for relatively little gain, so it is preferable

 *      in most situations to use the 4-connected version.)

 *      The algorithm proceeds from UR to LL of the image, and

 *      then reverses and sweeps up from LL to UR.

 *      These double sweeps are iterated until there is no change.

 *      At this point, the seed has entirely filled the region it

 *      is allowed to, as delimited by the mask image.

 *

 *      The grayscale seedfill is a straightforward generalization

 *      of the binary seedfill, and is described in seedfillLowGray().

 *

 *      For some applications, the filled seed will later be OR'd

 *      with the negative of the mask.   This is used, for example,

 *      when you flood fill into a 4-connected region of OFF pixels

 *      and you want the result after those pixels are turned ON.

 *

 *      Note carefully that the mask we use delineates which pixels

 *      are allowed to be ON as the seed is filled.  We will call this

 *      a "filling mask".  As the seed expands, it is repeatedly

 *      ANDed with the filling mask: s & fm.  The process can equivalently

 *      be formulated using the inverse of the filling mask, which

 *      we will call a "blocking mask": bm = ~fm.   As the seed

 *      expands, the blocking mask is repeatedly used to prevent

 *      the seed from expanding into the blocking mask.  This is done

 *      by set subtracting the blocking mask from the expanded seed:

 *      s - bm.  Set subtraction of the blocking mask is equivalent

 *      to ANDing with the inverse of the blocking mask: s & (~bm).

 *      But from the inverse relation between blocking and filling

 *      masks, this is equal to s & fm, which proves the equivalence.

 *

 *      For efficiency, the pixels can be taken in larger units

 *      for processing, but still in raster order.  It is natural

 *      to take them in 32-bit words.  The outline of the work

 *      to be done for 4-cc (not including special cases for boundary

 *      words, such as the first line or the last word in each line)

 *      is as follows.  Let the filling mask be m.  The

 *      seed is to fill "under" the mask; i.e., limited by an AND

 *      with the mask.  Let the current word be w, the word

 *      in the line above be wa, and the previous word in the

 *      current line be wp.   Let t be a temporary word that

 *      is used in computation.  Note that masking is performed by

 *      w & m.  (If we had instead used a "blocking" mask, we

 *      would perform masking by the set subtraction operation,

 *      w - m, which is defined to be w & ~m.)

 *

 *      The entire operation can be implemented with shifts,

 *      logical operations and tests.  For each word in the seed image

 *      there are two steps.  The first step is to OR the word with

 *      the word above and with the rightmost pixel in wp (call it "x").

 *      Because wp is shifted one pixel to its right, "x" is ORed

 *      to the leftmost pixel of w.  We then clip to the ON pixels in

 *      the mask.  The result is

 *               t  <--  (w | wa | x000... ) & m

 *      We've now finished taking data from above and to the left.

 *      The second step is to allow filling to propagate horizontally

 *      in t, always making sure that it is properly masked at each

 *      step.  So if filling can be done (i.e., t is neither all 0s

 *      nor all 1s), iteratively take:

 *           t  <--  (t | (t >> 1) | (t << 1)) & m

 *      until t stops changing.  Then write t back into w.

 *

 *      Finally, the boundary conditions require we note that in doing

 *      the above steps:

 *          (a) The words in the first row have no wa

 *          (b) The first word in each row has no wp in that row

 *          (c) The last word in each row must be masked so that

 *              pixels don't propagate beyond the right edge of the

 *              actual image.  (This is easily accomplished by

 *              setting the out-of-bound pixels in m to OFF.)

 * </pre>

 */

#ifdef HAVE_CONFIG_H

#include <config_auto.h>

#endif  /* HAVE_CONFIG_H */

#include <math.h>

#include "allheaders.h"

struct L_Pixel

{

    l_int32    x;

    l_int32    y;

};

typedef struct L_Pixel  L_PIXEL;

static void seedfillBinaryLow(l_uint32 *datas, l_int32 hs, l_int32 wpls,

                              l_uint32 *datam, l_int32 hm, l_int32 wplm,

                              l_int32 connectivity);

static void seedfillGrayLow(l_uint32 *datas, l_int32 w, l_int32 h,

                            l_int32 wpls, l_uint32 *datam, l_int32 wplm,

                            l_int32 connectivity);

static void seedfillGrayInvLow(l_uint32 *datas, l_int32 w, l_int32 h,

                               l_int32 wpls, l_uint32 *datam, l_int32 wplm,

                               l_int32 connectivity);

static void seedfillGrayLowSimple(l_uint32 *datas, l_int32 w, l_int32 h,

                                  l_int32 wpls, l_uint32 *datam, l_int32 wplm,

                                  l_int32 connectivity);

static void seedfillGrayInvLowSimple(l_uint32 *datas, l_int32 w, l_int32 h,

                                     l_int32 wpls, l_uint32 *datam,

                                     l_int32 wplm, l_int32 connectivity);

static void distanceFunctionLow(l_uint32 *datad, l_int32 w, l_int32 h,

                                l_int32 d, l_int32 wpld, l_int32 connectivity);

static void seedspreadLow(l_uint32 *datad, l_int32 w, l_int32 h, l_int32 wpld,

                          l_uint32 *datat, l_int32 wplt, l_int32 connectivity);

static l_int32 pixQualifyLocalMinima(PIX *pixs, PIX *pixm, l_int32 maxval);

#ifndef  NO_CONSOLE_IO

#define   DEBUG_PRINT_ITERS    0

#endif  /* ~NO_CONSOLE_IO */

  /* Two-way (UL --> LR, LR --> UL) sweep iterations; typically need only 4 */

static const l_int32  MaxIters = 40;

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

 *              Vincent's Iterative Binary Seedfill method               *

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

/*!

 * \brief   pixSeedfillBinary()

 *

 * \param[in]    pixd          [optional]; can be null, equal to pixs,

 *                             or different from pixs; 1 bpp

 * \param[in]    pixs          1 bpp seed

 * \param[in]    pixm          1 bpp filling mask

 * \param[in]    connectivity  4 or 8

 * \return  pixd always

 *

 * <pre>

 * Notes:

 *      (1) This is for binary seedfill (aka "binary reconstruction").

 *      (2) There are 3 cases:

 *            (a) pixd == null (make a new pixd)

 *            (b) pixd == pixs (in-place)

 *            (c) pixd != pixs

 *      (3) If you know the case, use these patterns for clarity:

 *            (a) pixd = pixSeedfillBinary(NULL, pixs, ...);

 *            (b) pixSeedfillBinary(pixs, pixs, ...);

 *            (c) pixSeedfillBinary(pixd, pixs, ...);

 *      (4) The resulting pixd contains the filled seed.  For some

 *          applications you want to OR it with the inverse of

 *          the filling mask.

 *      (5) The input seed and mask images can be different sizes, but

 *          in typical use the difference, if any, would be only

 *          a few pixels in each direction.  If the sizes differ,

 *          the clipping is handled by the low-level function

 *          seedfillBinaryLow().

 * </pre>

 */

PIX *

pixSeedfillBinary(PIX     *pixd,

                  PIX     *pixs,

                  PIX     *pixm,

                  l_int32  connectivity)

{

l_int32    i, boolval;

l_int32    hd, hm, wpld, wplm;

l_uint32  *datad, *datam;

PIX       *pixt;

    if (!pixs || pixGetDepth(pixs) != 1)

        return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, pixd);

    if (!pixm || pixGetDepth(pixm) != 1)

        return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", __func__, pixd);

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

        return (PIX *)ERROR_PTR("connectivity not in {4,8}", __func__, pixd);

        /* Prepare pixd as a copy of pixs if not identical */

    if ((pixd = pixCopy(pixd, pixs)) == NULL)

        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);

    pixSetPadBits(pixd, 0);  /* be safe: */

    pixSetPadBits(pixm, 0);  /* avoid using uninitialized memory */

        /* pixt is used to test for completion */

    if ((pixt = pixCreateTemplate(pixs)) == NULL)

        return (PIX *)ERROR_PTR("pixt not made", __func__, pixd);

    hd = pixGetHeight(pixd);

    hm = pixGetHeight(pixm);  /* included so seedfillBinaryLow() can clip */

    datad = pixGetData(pixd);

    datam = pixGetData(pixm);

    wpld = pixGetWpl(pixd);

    wplm = pixGetWpl(pixm);

    for (i = 0; i < MaxIters; i++) {

        pixCopy(pixt, pixd);

        seedfillBinaryLow(datad, hd, wpld, datam, hm, wplm, connectivity);

        pixEqual(pixd, pixt, &boolval);

        if (boolval == 1) {

#if DEBUG_PRINT_ITERS

            lept_stderr("Binary seed fill converged: %d iters\n", i + 1);

#endif  /* DEBUG_PRINT_ITERS */

            break;

        }

    }

    pixDestroy(&pixt);

    return pixd;

}

/*!

 * \brief   pixSeedfillBinaryRestricted()

 *

 * \param[in]    pixd          [optional]; can be null, equal to pixs,

 *                             or different from pixs; 1 bpp

 * \param[in]    pixs          1 bpp seed

 * \param[in]    pixm          1 bpp filling mask

 * \param[in]    connectivity  4 or 8

 * \param[in]    xmax          max distance in x direction of fill into mask

 * \param[in]    ymax          max distance in y direction of fill into mask

 * \return  pixd always

 *

 * <pre>

 * Notes:

 *      (1) See usage for pixSeedfillBinary(), which has unrestricted fill.

 *          In pixSeedfillBinary(), the filling distance is unrestricted

 *          and can be larger than pixs, depending on the topology of

 *          th mask.

 *      (2) There are occasions where it is useful not to permit the

 *          fill to go more than a certain distance into the mask.

 *          %xmax specifies the maximum horizontal distance allowed

 *          in the fill; %ymax does likewise in the vertical direction.

 *      (3) Operationally, the max "distance" allowed for the fill

 *          is a linear distance from the original seed, independent

 *          of the actual mask topology.

 *      (4) Another formulation of this problem, not implemented,

 *          would use the manhattan distance from the seed, as

 *          determined by a breadth-first search starting at the seed

 *          boundaries and working outward where the mask fg allows.

 *          How this might use the constraints of separate xmax and ymax

 *          is not clear.

 * </pre>

 */

PIX *

pixSeedfillBinaryRestricted(PIX     *pixd,

                            PIX     *pixs,

                            PIX     *pixm,

                            l_int32  connectivity,

                            l_int32  xmax,

                            l_int32  ymax)

{

l_int32  w, h;

PIX     *pix1, *pix2;

    if (!pixs || pixGetDepth(pixs) != 1)

        return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, pixd);

    if (!pixm || pixGetDepth(pixm) != 1)

        return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", __func__, pixd);

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

        return (PIX *)ERROR_PTR("connectivity not in {4,8}", __func__, pixd);

    if (xmax == 0 && ymax == 0)  /* no filling permitted */

        return pixClone(pixs);

    if (xmax < 0 || ymax < 0) {

        L_ERROR("xmax and ymax must be non-negative", __func__);

        return pixClone(pixs);

    }

        /* Full fill from the seed into the mask. */

    if ((pix1 = pixSeedfillBinary(NULL, pixs, pixm, connectivity)) == NULL)

        return (PIX *)ERROR_PTR("pix1 not made", __func__, pixd);

        /* Dilate the seed.  This gives the maximal region where changes

         * are permitted.  Invert to get the region where pixs is

         * not allowed to change.  */

    pix2 = pixDilateCompBrick(NULL, pixs, 2 * xmax + 1, 2 * ymax + 1);

    pixInvert(pix2, pix2);

        /* Blank the region of pix1 specified by the fg of pix2.

         * This is not yet the final result, because it may have fg pixels

         * that are not accessible from the seed in the restricted distance.

         * For example, such pixels may be connected to the original seed,

         * but through a path that goes outside the permitted region. */

    pixGetDimensions(pixs, &w, &h, NULL);

    pixRasterop(pix1, 0, 0, w, h, PIX_DST & PIX_NOT(PIX_SRC), pix2, 0, 0);

        /* To get the accessible pixels in the restricted region, do

         * a second seedfill from the original seed, using pix1 as

         * a mask.  The result, in pixd, will not have any bad fg

         * pixels that were in pix1. */

    pixd = pixSeedfillBinary(pixd, pixs, pix1, connectivity);

    pixDestroy(&pix1);

    pixDestroy(&pix2);

    return pixd;

}

/*!

 * \brief   seedfillBinaryLow()

 *

 *  Notes:

 *      (1) This is an in-place fill, where the seed image is

 *          filled, clipping to the filling mask, in one full

 *          cycle of UL -> LR and LR -> UL raster scans.

 *      (2) Assume the mask is a filling mask, not a blocking mask.

 *      (3) Assume that the RHS pad bits of the mask

 *          are properly set to 0.

 *      (4) Clip to the smallest dimensions to avoid invalid reads.

 */

static void

seedfillBinaryLow(l_uint32  *datas,

                  l_int32    hs,

                  l_int32    wpls,

                  l_uint32  *datam,

                  l_int32    hm,

                  l_int32    wplm,

                  l_int32    connectivity)

{

l_int32    i, j, h, wpl;

l_uint32   word, mask;

l_uint32   wordabove, wordleft, wordbelow, wordright;

l_uint32   wordprev;  /* test against this in previous iteration */

l_uint32  *lines, *linem;

    h = L_MIN(hs, hm);

    wpl = L_MIN(wpls, wplm);

    switch (connectivity)

    {

    case 4:

            /* UL --> LR scan */

        for (i = 0; i < h; i++) {

            lines = datas + i * wpls;

            linem = datam + i * wplm;

            for (j = 0; j < wpl; j++) {

                word = *(lines + j);

                mask = *(linem + j);

                    /* OR from word above and from word to left; mask */

                if (i > 0) {

                    wordabove = *(lines - wpls + j);

                    word |= wordabove;

                }

                if (j > 0) {

                    wordleft = *(lines + j - 1);

                    word |= wordleft << 31;

                }

                word &= mask;

                    /* No need to fill horizontally? */

                if (!word || !(~word)) {

                    *(lines + j) = word;

                    continue;

                }

                while (1) {

                    wordprev = word;

                    word = (word | (word >> 1) | (word << 1)) & mask;

                    if ((word ^ wordprev) == 0) {

                        *(lines + j) = word;

                        break;

                    }

                }

            }

        }

            /* LR --> UL scan */

        for (i = h - 1; i >= 0; i--) {

            lines = datas + i * wpls;

            linem = datam + i * wplm;

            for (j = wpl - 1; j >= 0; j--) {

                word = *(lines + j);

                mask = *(linem + j);

                    /* OR from word below and from word to right; mask */

                if (i < h - 1) {

                    wordbelow = *(lines + wpls + j);

                    word |= wordbelow;

                }

                if (j < wpl - 1) {

                    wordright = *(lines + j + 1);

                    word |= wordright >> 31;

                }

                word &= mask;

                    /* No need to fill horizontally? */

                if (!word || !(~word)) {

                    *(lines + j) = word;

                    continue;

                }

                while (1) {

                    wordprev = word;

                    word = (word | (word >> 1) | (word << 1)) & mask;

                    if ((word ^ wordprev) == 0) {

                        *(lines + j) = word;

                        break;

                    }

                }

            }

        }

        break;

    case 8:

            /* UL --> LR scan */

        for (i = 0; i < h; i++) {

            lines = datas + i * wpls;

            linem = datam + i * wplm;

            for (j = 0; j < wpl; j++) {

                word = *(lines + j);

                mask = *(linem + j);

                    /* OR from words above and from word to left; mask */

                if (i > 0) {

                    wordabove = *(lines - wpls + j);

                    word |= (wordabove | (wordabove << 1) | (wordabove >> 1));

                    if (j > 0)

                        word |= (*(lines - wpls + j - 1)) << 31;

                    if (j < wpl - 1)

                        word |= (*(lines - wpls + j + 1)) >> 31;

                }

                if (j > 0) {

                    wordleft = *(lines + j - 1);

                    word |= wordleft << 31;

                }

                word &= mask;

                    /* No need to fill horizontally? */

                if (!word || !(~word)) {

                    *(lines + j) = word;

                    continue;

                }

                while (1) {

                    wordprev = word;

                    word = (word | (word >> 1) | (word << 1)) & mask;

                    if ((word ^ wordprev) == 0) {

                        *(lines + j) = word;

                        break;

                    }

                }

            }

        }

            /* LR --> UL scan */

        for (i = h - 1; i >= 0; i--) {

            lines = datas + i * wpls;

            linem = datam + i * wplm;

            for (j = wpl - 1; j >= 0; j--) {

                word = *(lines + j);

                mask = *(linem + j);

                    /* OR from words below and from word to right; mask */

                if (i < h - 1) {

                    wordbelow = *(lines + wpls + j);

                    word |= (wordbelow | (wordbelow << 1) | (wordbelow >> 1));

                    if (j > 0)

                        word |= (*(lines + wpls + j - 1)) << 31;

                    if (j < wpl - 1)

                        word |= (*(lines + wpls + j + 1)) >> 31;

                }

                if (j < wpl - 1) {

                    wordright = *(lines + j + 1);

                    word |= wordright >> 31;

                }

                word &= mask;

                    /* No need to fill horizontally? */

                if (!word || !(~word)) {

                    *(lines + j) = word;

                    continue;

                }

                while (1) {

                    wordprev = word;

                    word = (word | (word >> 1) | (word << 1)) & mask;

                    if ((word ^ wordprev) == 0) {

                        *(lines + j) = word;

                        break;

                    }

                }

            }

        }

        break;

    default:

        L_ERROR("connectivity must be 4 or 8\n", __func__);

    }

}

/*!

 * \brief   pixHolesByFilling()

 *

 * \param[in]    pixs           1 bpp

 * \param[in]    connectivity   4 or 8

 * \return  pixd  inverted image of all holes, or NULL on error

 *

 * Action:

 *     1 Start with 1-pixel black border on otherwise white pixd

 *     2 Use the inverted pixs as the filling mask to fill in

 *         all the pixels from the border to the pixs foreground

 *     3 OR the result with pixs to have an image with all

 *         ON pixels except for the holes.

 *     4 Invert the result to get the holes as foreground

 *

 * <pre>

 * Notes:

 *     (1) To get 4-c.c. holes of the 8-c.c. as foreground, use

 *         4-connected filling; to get 8-c.c. holes of the 4-c.c.

 *         as foreground, use 8-connected filling.

 * </pre>

 */

PIX *

pixHolesByFilling(PIX     *pixs,

                  l_int32  connectivity)

{

PIX  *pixsi, *pixd;

    if (!pixs || pixGetDepth(pixs) != 1)

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

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

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

    if ((pixd = pixCreateTemplate(pixs)) == NULL)

        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);

    if ((pixsi = pixInvert(NULL, pixs)) == NULL) {

        pixDestroy(&pixd);

        return (PIX *)ERROR_PTR("pixsi not made", __func__, NULL);

    }

    pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);

    pixSeedfillBinary(pixd, pixd, pixsi, connectivity);

    pixOr(pixd, pixd, pixs);

    pixInvert(pixd, pixd);

    pixDestroy(&pixsi);

    return pixd;

}

/*!

 * \brief   pixFillClosedBorders()

 *

 * \param[in]    pixs           1 bpp

 * \param[in]    connectivity   filling connectivity 4 or 8

 * \return  pixd  all topologically outer closed borders are filled

 *                     as connected comonents, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) Start with 1-pixel black border on otherwise white pixd

 *      (2) Subtract input pixs to remove border pixels that were

 *          also on the closed border

 *      (3) Use the inverted pixs as the filling mask to fill in

 *          all the pixels from the outer border to the closed border

 *          on pixs

 *      (4) Invert the result to get the filled component, including

 *          the input border

 *      (5) If the borders are 4-c.c., use 8-c.c. filling, and v.v.

 *      (6) Closed borders within c.c. that represent holes, etc., are filled.

 * </pre>

 */

PIX *

pixFillClosedBorders(PIX     *pixs,

                     l_int32  connectivity)

{

PIX  *pixsi, *pixd;

    if (!pixs || pixGetDepth(pixs) != 1)

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

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

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

    if ((pixd = pixCreateTemplate(pixs)) == NULL)

        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);

    pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);

    pixSubtract(pixd, pixd, pixs);

    if ((pixsi = pixInvert(NULL, pixs)) == NULL) {

        pixDestroy(&pixd);

        return (PIX *)ERROR_PTR("pixsi not made", __func__, NULL);

    }

    pixSeedfillBinary(pixd, pixd, pixsi, connectivity);

    pixInvert(pixd, pixd);

    pixDestroy(&pixsi);

    return pixd;

}

/*!

 * \brief   pixExtractBorderConnComps()

 *

 * \param[in]    pixs           1 bpp

 * \param[in]    connectivity   filling connectivity 4 or 8

 * \return  pixd  all pixels in the src that are in connected

 *                components touching the border, or NULL on error

 */

PIX *

pixExtractBorderConnComps(PIX     *pixs,

                          l_int32  connectivity)

{

PIX  *pixd;

    if (!pixs || pixGetDepth(pixs) != 1)

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

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

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

        /* Start with 1 pixel wide black border as seed in pixd */

    if ((pixd = pixCreateTemplate(pixs)) == NULL)

        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);

    pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);

       /* Fill in pixd from the seed, using pixs as the filling mask.

        * This fills all components from pixs that are touching the border. */

    pixSeedfillBinary(pixd, pixd, pixs, connectivity);

    return pixd;

}

/*!

 * \brief   pixRemoveBorderConnComps()

 *

 * \param[in]    pixs           1 bpp

 * \param[in]    connectivity   filling connectivity 4 or 8

 * \return  pixd  all pixels in the src that are not touching the

 *                border or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) This removes all fg components touching the border.

 * </pre>

 */

PIX *

pixRemoveBorderConnComps(PIX     *pixs,

                         l_int32  connectivity)

{

PIX  *pixd;

    if (!pixs || pixGetDepth(pixs) != 1)

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

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

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

       /* Fill from a 1 pixel wide seed at the border into all components

        * in pixs (the filling mask) that are touching the border */

    pixd = pixExtractBorderConnComps(pixs, connectivity);

       /* Save in pixd only those components in pixs not touching the border */

    pixXor(pixd, pixd, pixs);

    return pixd;

}

/*!

 * \brief   pixFillBgFromBorder()

 *

 * \param[in]    pixs           1 bpp

 * \param[in]    connectivity   filling connectivity 4 or 8

 * \return  pixd with the background c.c. touching the border

 *               filled to foreground, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) This fills all bg components touching the border to fg.

 *          It is the photometric inverse of pixRemoveBorderConnComps().

 *      (2) Invert the result to get the "holes" left after this fill.

 *          This can be done multiple times, extracting holes within

 *          holes after each pair of fillings.  Specifically, this code

 *          peels away n successive embeddings of components:

 * \code

 *              pix1 = <initial image>

 *              for (i = 0; i < 2 * n; i++) {

 *                   pix2 = pixFillBgFromBorder(pix1, 8);

 *                   pixInvert(pix2, pix2);

 *                   pixDestroy(&pix1);

 *                   pix1 = pix2;

 *              }

 * \endcode

 * </pre>

 */

PIX *

pixFillBgFromBorder(PIX     *pixs,

                    l_int32  connectivity)

{

PIX  *pixd;

    if (!pixs || pixGetDepth(pixs) != 1)

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

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

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

       /* Invert to turn bg touching the border to a fg component.

        * Extract this by filling from a 1 pixel wide seed at the border. */

    pixInvert(pixs, pixs);

    pixd = pixExtractBorderConnComps(pixs, connectivity);

    pixInvert(pixs, pixs);  /* restore pixs */

       /* Bit-or the filled bg component with pixs */

    pixOr(pixd, pixd, pixs);

    return pixd;

}

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

 *            Hole-filling of components to bounding rectangle           *

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

/*!

 * \brief   pixFillHolesToBoundingRect()

 *

 * \param[in]    pixs         1 bpp

 * \param[in]    minsize      min number of pixels in the hole

 * \param[in]    maxhfract    max hole area as fraction of fg pixels in the cc

 * \param[in]    minfgfract   min fg area as fraction of bounding rectangle

 * \return  pixd   with some holes possibly filled and some c.c. possibly

 *                 expanded to their bounding rects, or NULL on error

 *

 * <pre>

 * Notes:

 *      (1) This does not fill holes that are smaller in area than 'minsize'.

 *          Use %minsize = 0 and %maxhfract = 1.0 to fill all holes.

 *      (2) This does not fill holes with an area larger than

 *          %maxhfract times the fg area of the c.c.

 *          Use 1.0 to fill all holes.

 *      (3) This does not expand the fg of the c.c. to bounding rect if

 *          the fg area is less than %minfgfract times the area of the

 *          bounding rect.  Use 1.0 to skip expanding to the bounding rect.

 *      (4) The decisions are made as follows:

 *           ~ Decide if we are filling the holes; if so, when using

 *             the fg area, include the filled holes.

 *           ~ Decide based on the fg area if we are filling to a bounding rect.

 *             If so, do it.

 *             If not, fill the holes if the condition is satisfied.

 *      (5) The choice of %minsize depends on the resolution.

 *      (6) For solidifying image mask regions on printed materials,

 *          which tend to be rectangular, values for %maxhfract

 *          and %minfgfract around 0.5 are reasonable.

 * </pre>

 */

PIX *

pixFillHolesToBoundingRect(PIX       *pixs,

                           l_int32    minsize,

                           l_float32  maxhfract,

                           l_float32  minfgfract)

{

l_int32    i, x, y, w, h, n, nfg, nh, ntot, area;

l_int32   *tab;

l_float32  hfract;  /* measured hole fraction */

l_float32  fgfract;  /* measured fg fraction */

BOXA      *boxa;

PIX       *pixd, *pixfg, *pixh;

PIXA      *pixa;

    if (!pixs || pixGetDepth(pixs) != 1)

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

    maxhfract = L_MIN(L_MAX(maxhfract, 0.0), 1.0);

    minfgfract = L_MIN(L_MAX(minfgfract, 0.0), 1.0);

    pixd = pixCopy(NULL, pixs);

    boxa = pixConnComp(pixd, &pixa, 8);

    n = boxaGetCount(boxa);

    tab = makePixelSumTab8();

    for (i = 0; i < n; i++) {

        boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);

        area = w * h;

        if (area < minsize)

            continue;

        pixfg = pixaGetPix(pixa, i, L_COPY);

        pixh = pixHolesByFilling(pixfg, 4);  /* holes only */

        pixCountPixels(pixfg, &nfg, tab);

        pixCountPixels(pixh, &nh, tab);

        hfract = (l_float32)nh / (l_float32)nfg;

        ntot = nfg;

        if (hfract <= maxhfract)  /* we will fill the holes (at least) */

            ntot = nfg + nh;

        fgfract = (l_float32)ntot / (l_float32)area;

        if (fgfract >= minfgfract) {  /* fill to bounding rect */

            pixSetAll(pixfg);

            pixRasterop(pixd, x, y, w, h, PIX_SRC, pixfg, 0, 0);

        } else if (hfract <= maxhfract) {  /* fill just the holes */

            pixRasterop(pixd, x, y, w, h, PIX_DST | PIX_SRC , pixh, 0, 0);

        }

        pixDestroy(&pixfg);

        pixDestroy(&pixh);

    }

    boxaDestroy(&boxa);

    pixaDestroy(&pixa);

    LEPT_FREE(tab);

    return pixd;

}

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

 *               Vincent's hybrid Grayscale Seedfill method              *

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

/*!

 * \brief   pixSeedfillGray()

 *

 * \param[in]    pixs           8 bpp seed; filled in place

 * \param[in]    pixm           8 bpp filling mask

 * \param[in]    connectivity   4 or 8

 * \return  0 if OK, 1 on error

 *

 * <pre>

 * Notes:

 *      (1) This is an in-place filling operation on the seed, pixs,

 *          where the clipping mask is always above or at the level

 *          of the seed as it is filled.

 *      (2) For details of the operation, see the description in

 *          seedfillGrayLow() and the code there.

 *      (3) As an example of use, see the description in pixHDome().

 *          There, the seed is an image where each pixel is a fixed

 *          amount smaller than the corresponding mask pixel.

 *      (4) Reference paper :

 *            L. Vincent, Morphological grayscale reconstruction in image

 *            analysis: applications and efficient algorithms, IEEE Transactions

 *            on  Image Processing, vol. 2, no. 2, pp. 176-201, 1993.

 * </pre>

 */

l_ok

pixSeedfillGray(PIX     *pixs,

                PIX     *pixm,

                l_int32  connectivity)

{

l_int32    h, w, wpls, wplm;

l_uint32  *datas, *datam;

    if (!pixs || pixGetDepth(pixs) != 8)

        return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);

    if (!pixm || pixGetDepth(pixm) != 8)

        return ERROR_INT("pixm not defined or not 8 bpp", __func__, 1);

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

        return ERROR_INT("connectivity not in {4,8}", __func__, 1);

        /* Make sure the sizes of seed and mask images are the same */

    if (pixSizesEqual(pixs, pixm) == 0)

        return ERROR_INT("pixs and pixm sizes differ", __func__, 1);

    datas = pixGetData(pixs);

    datam = pixGetData(pixm);

    wpls = pixGetWpl(pixs);

    wplm = pixGetWpl(pixm);

    pixGetDimensions(pixs, &w, &h, NULL);

    seedfillGrayLow(datas, w, h, wpls, datam, wplm, connectivity);

    return 0;

}

/*!

 * \brief   pixSeedfillGrayInv()

 *

 * \param[in]    pixs           8 bpp seed; filled in place

 * \param[in]    pixm           8 bpp filling mask

 * \param[in]    connectivity   4 or 8

 * \return  0 if OK, 1 on error

 *

 * <pre>

 * Notes:

 *      (1) This is an in-place filling operation on the seed, pixs,

 *          where the clipping mask is always below or at the level

 *          of the seed as it is filled.  Think of filling up a basin

 *          to a particular level, given by the maximum seed value

 *          in the basin.  Outside the filled region, the mask

 *          is above the filling level.

 *      (2) Contrast this with pixSeedfillGray(), where the clipping mask

 *          is always above or at the level of the fill.  An example

 *          of its use is the hdome fill, where the seed is an image

 *          where each pixel is a fixed amount smaller than the

 *          corresponding mask pixel.

 *      (3) The basin fill, pixSeedfillGrayBasin(), is a special case

 *          where the seed pixel values are generated from the mask,

 *          and where the implementation uses pixSeedfillGray() by

 *          inverting both the seed and mask.

 * </pre>

 */

l_ok

pixSeedfillGrayInv(PIX     *pixs,

                   PIX     *pixm,

                   l_int32  connectivity)

{

l_int32    h, w, wpls, wplm;

l_uint32  *datas, *datam;

    if (!pixs || pixGetDepth(pixs) != 8)

        return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);

    if (!pixm || pixGetDepth(pixm) != 8)