Leptonica 1.68
C Image Processing Library

seedfill.c

Go to the documentation of this file.
00001 /*====================================================================*
00002  -  Copyright (C) 2001 Leptonica.  All rights reserved.
00003  -  This software is distributed in the hope that it will be
00004  -  useful, but with NO WARRANTY OF ANY KIND.
00005  -  No author or distributor accepts responsibility to anyone for the
00006  -  consequences of using this software, or for whether it serves any
00007  -  particular purpose or works at all, unless he or she says so in
00008  -  writing.  Everyone is granted permission to copy, modify and
00009  -  redistribute this source code, for commercial or non-commercial
00010  -  purposes, with the following restrictions: (1) the origin of this
00011  -  source code must not be misrepresented; (2) modified versions must
00012  -  be plainly marked as such; and (3) this notice may not be removed
00013  -  or altered from any source or modified source distribution.
00014  *====================================================================*/
00015 
00016 /*
00017  *  seedfill.c
00018  *
00019  *      Binary seedfill (source: Luc Vincent)
00020  *               PIX      *pixSeedfillBinary()
00021  *               PIX      *pixSeedfillBinaryRestricted()
00022  *
00023  *      Applications of binary seedfill to find and fill holes,
00024  *      and to remove c.c. touching the border:
00025  *               PIX      *pixHolesByFilling()
00026  *               PIX      *pixFillClosedBorders()
00027  *               PIX      *pixExtractBorderConnComps()
00028  *               PIX      *pixRemoveBorderConnComps()
00029  *
00030  *      Hole-filling of components to bounding rectangle
00031  *               PIX      *pixFillHolesToBoundingRect()
00032  *
00033  *      Gray seedfill (source: Luc Vincent:fast-hybrid-grayscale-reconstruction)
00034  *               l_int32   pixSeedfillGray()
00035  *               l_int32   pixSeedfillGrayInv()
00036  *
00037  *      Gray seedfill (source: Luc Vincent: sequential-reconstruction algorithm)
00038  *               l_int32   pixSeedfillGraySimple()
00039  *               l_int32   pixSeedfillGrayInvSimple()
00040  *
00041  *      Gray seedfill variations
00042  *               PIX      *pixSeedfillGrayBasin()
00043  *
00044  *      Distance function (source: Luc Vincent)
00045  *               PIX      *pixDistanceFunction()
00046  *
00047  *      Seed spread (based on distance function)
00048  *               PIX      *pixSeedspread()
00049  *
00050  *      Local extrema:
00051  *               l_int32   pixLocalExtrema()
00052  *        static l_int32   pixQualifyLocalMinima()
00053  *               l_int32   pixSelectedLocalExtrema()
00054  *               PIX      *pixFindEqualValues()
00055  *
00056  *      Selection of minima in mask of connected components
00057  *               PTA      *pixSelectMinInConnComp()
00058  *
00059  *      Removal of seeded connected components from a mask
00060  *               PIX      *pixRemoveSeededComponents()
00061  *
00062  *
00063  *           ITERATIVE RASTER-ORDER SEEDFILL
00064  *
00065  *      The basic method in the Vincent seedfill (aka reconstruction)
00066  *      algorithm is simple.  We describe here the situation for
00067  *      binary seedfill.  Pixels are sampled in raster order in
00068  *      the seed image.  If they are 4-connected to ON pixels
00069  *      either directly above or to the left, and are not masked
00070  *      out by the mask image, they are turned on (or remain on).
00071  *      (Ditto for 8-connected, except you need to check 3 pixels
00072  *      on the previous line as well as the pixel to the left
00073  *      on the current line.  This is extra computational work
00074  *      for relatively little gain, so it is preferable
00075  *      in most situations to use the 4-connected version.)
00076  *      The algorithm proceeds from UR to LL of the image, and
00077  *      then reverses and sweeps up from LL to UR.
00078  *      These double sweeps are iterated until there is no change.
00079  *      At this point, the seed has entirely filled the region it
00080  *      is allowed to, as delimited by the mask image.
00081  *
00082  *      The grayscale seedfill is a straightforward generalization
00083  *      of the binary seedfill, and is described in seedfillLowGray().
00084  *
00085  *      For some applications, the filled seed will later be OR'd
00086  *      with the negative of the mask.   This is used, for example,
00087  *      when you flood fill into a 4-connected region of OFF pixels
00088  *      and you want the result after those pixels are turned ON.
00089  *
00090  *      Note carefully that the mask we use delineates which pixels
00091  *      are allowed to be ON as the seed is filled.  We will call this
00092  *      a "filling mask".  As the seed expands, it is repeatedly
00093  *      ANDed with the filling mask: s & fm.  The process can equivalently
00094  *      be formulated using the inverse of the filling mask, which
00095  *      we will call a "blocking mask": bm = ~fm.   As the seed
00096  *      expands, the blocking mask is repeatedly used to prevent
00097  *      the seed from expanding into the blocking mask.  This is done
00098  *      by set subtracting the blocking mask from the expanded seed:
00099  *      s - bm.  Set subtraction of the blocking mask is equivalent
00100  *      to ANDing with the inverse of the blocking mask: s & (~bm).
00101  *      But from the inverse relation between blocking and filling
00102  *      masks, this is equal to s & fm, which proves the equivalence.
00103  *
00104  *      For efficiency, the pixels can be taken in larger units
00105  *      for processing, but still in raster order.  It is natural
00106  *      to take them in 32-bit words.  The outline of the work
00107  *      to be done for 4-cc (not including special cases for boundary
00108  *      words, such as the first line or the last word in each line)
00109  *      is as follows.  Let the filling mask be m.  The
00110  *      seed is to fill "under" the mask; i.e., limited by an AND
00111  *      with the mask.  Let the current word be w, the word
00112  *      in the line above be wa, and the previous word in the
00113  *      current line be wp.   Let t be a temporary word that
00114  *      is used in computation.  Note that masking is performed by
00115  *      w & m.  (If we had instead used a "blocking" mask, we
00116  *      would perform masking by the set subtraction operation,
00117  *      w - m, which is defined to be w & ~m.)
00118  *
00119  *      The entire operation can be implemented with shifts,
00120  *      logical operations and tests.  For each word in the seed image
00121  *      there are two steps.  The first step is to OR the word with
00122  *      the word above and with the rightmost pixel in wp (call it "x").
00123  *      Because wp is shifted one pixel to its right, "x" is ORed
00124  *      to the leftmost pixel of w.  We then clip to the ON pixels in
00125  *      the mask.  The result is
00126  *               t  <--  (w | wa | x000... ) & m
00127  *      We've now finished taking data from above and to the left.
00128  *      The second step is to allow filling to propagate horizontally
00129  *      in t, always making sure that it is properly masked at each
00130  *      step.  So if filling can be done (i.e., t is neither all 0s
00131  *      nor all 1s), iteratively take:
00132  *           t  <--  (t | (t >> 1) | (t << 1)) & m
00133  *      until t stops changing.  Then write t back into w.
00134  *
00135  *      Finally, the boundary conditions require we note that in doing
00136  *      the above steps:
00137  *          (a) The words in the first row have no wa
00138  *          (b) The first word in each row has no wp in that row
00139  *          (c) The last word in each row must be masked so that
00140  *              pixels don't propagate beyond the right edge of the
00141  *              actual image.  (This is easily accomplished by
00142  *              setting the out-of-bound pixels in m to OFF.)
00143  */
00144 
00145 #include <stdio.h>
00146 #include <stdlib.h>
00147 #include "allheaders.h"
00148 
00149 #ifndef  NO_CONSOLE_IO
00150 #define   DEBUG_PRINT_ITERS    0
00151 #endif  /* ~NO_CONSOLE_IO */
00152 
00153   /* Two-way (UL --> LR, LR --> UL) sweep iterations; typically need only 4 */
00154 static const l_int32  MAX_ITERS = 40;
00155 
00156     /* Static function */
00157 static l_int32 pixQualifyLocalMinima(PIX *pixs, PIX *pixm, l_int32 maxval);
00158 
00159 
00160 /*-----------------------------------------------------------------------*
00161  *              Vincent's Iterative Binary Seedfill method               *
00162  *-----------------------------------------------------------------------*/
00163 /*!
00164  *  pixSeedfillBinary()
00165  *
00166  *      Input:  pixd  (<optional>; this can be null, equal to pixs,
00167  *                     or different from pixs; 1 bpp)
00168  *              pixs  (1 bpp seed)
00169  *              pixm  (1 bpp filling mask)
00170  *              connectivity  (4 or 8)
00171  *      Return: pixd always
00172  *
00173  *  Notes:
00174  *      (1) This is for binary seedfill (aka "binary reconstruction").
00175  *      (2) There are 3 cases:
00176  *            (a) pixd == null (make a new pixd)
00177  *            (b) pixd == pixs (in-place)
00178  *            (c) pixd != pixs
00179  *      (3) If you know the case, use these patterns for clarity:
00180  *            (a) pixd = pixSeedfillBinary(NULL, pixs, ...);
00181  *            (b) pixSeedfillBinary(pixs, pixs, ...);
00182  *            (c) pixSeedfillBinary(pixd, pixs, ...);
00183  *      (4) The resulting pixd contains the filled seed.  For some
00184  *          applications you want to OR it with the inverse of
00185  *          the filling mask.
00186  *      (5) The input seed and mask images can be different sizes, but
00187  *          in typical use the difference, if any, would be only
00188  *          a few pixels in each direction.  If the sizes differ,
00189  *          the clipping is handled by the low-level function
00190  *          seedfillBinaryLow().
00191  */
00192 PIX *
00193 pixSeedfillBinary(PIX     *pixd,
00194                   PIX     *pixs,
00195                   PIX     *pixm,
00196                   l_int32  connectivity)
00197 {
00198 l_int32    i, boolval;
00199 l_int32    hd, hm, wpld, wplm;
00200 l_uint32  *datad, *datam;
00201 PIX       *pixt;
00202 
00203     PROCNAME("pixSeedfillBinary");
00204 
00205     if (!pixs || pixGetDepth(pixs) != 1)
00206         return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, pixd);
00207     if (!pixm || pixGetDepth(pixm) != 1)
00208         return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", procName, pixd);
00209     if (connectivity != 4 && connectivity != 8)
00210         return (PIX *)ERROR_PTR("connectivity not in {4,8}", procName, pixd);
00211 
00212         /* Prepare pixd as a copy of pixs if not identical */
00213     if ((pixd = pixCopy(pixd, pixs)) == NULL)
00214         return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
00215 
00216         /* pixt is used to test for completion */
00217     if ((pixt = pixCreateTemplate(pixs)) == NULL)
00218         return (PIX *)ERROR_PTR("pixt not made", procName, pixd);
00219 
00220     hd = pixGetHeight(pixd);
00221     hm = pixGetHeight(pixm);  /* included so seedfillBinaryLow() can clip */
00222     datad = pixGetData(pixd);
00223     datam = pixGetData(pixm);
00224     wpld = pixGetWpl(pixd);
00225     wplm = pixGetWpl(pixm);
00226 
00227     pixSetPadBits(pixm, 0);
00228 
00229     for (i = 0; i < MAX_ITERS; i++) {
00230         pixCopy(pixt, pixd);
00231         seedfillBinaryLow(datad, hd, wpld, datam, hm, wplm, connectivity);
00232         pixEqual(pixd, pixt, &boolval);
00233         if (boolval == 1) {
00234 #if DEBUG_PRINT_ITERS
00235             fprintf(stderr, "Binary seed fill converged: %d iters\n", i + 1);
00236 #endif  /* DEBUG_PRINT_ITERS */
00237             break;
00238         }
00239     }
00240 
00241     pixDestroy(&pixt);
00242     return pixd;
00243 }
00244 
00245 
00246 /*!
00247  *  pixSeedfillBinaryRestricted()
00248  *
00249  *      Input:  pixd  (<optional>; this can be null, equal to pixs,
00250  *                     or different from pixs; 1 bpp)
00251  *              pixs  (1 bpp seed)
00252  *              pixm  (1 bpp filling mask)
00253  *              connectivity  (4 or 8)
00254  *              xmax (max distance in x direction of fill into the mask)
00255  *              ymax (max distance in y direction of fill into the mask)
00256  *      Return: pixd always
00257  *
00258  *  Notes:
00259  *      (1) See usage for pixSeedfillBinary(), which has unrestricted fill.
00260  *          In pixSeedfillBinary(), the filling distance is unrestricted
00261  *          and can be larger than pixs, depending on the topology of
00262  *          th mask.
00263  *      (2) There are occasions where it is useful not to permit the
00264  *          fill to go more than a certain distance into the mask.
00265  *          @xmax specifies the maximum horizontal distance allowed
00266  *          in the fill; @ymax does likewise in the vertical direction.
00267  *      (3) Operationally, the max "distance" allowed for the fill
00268  *          is a linear distance from the original seed, independent
00269  *          of the actual mask topology.
00270  *      (4) Another formulation of this problem, not implemented,
00271  *          would use the manhattan distance from the seed, as
00272  *          determined by a breadth-first search starting at the seed
00273  *          boundaries and working outward where the mask fg allows.
00274  *          How this might use the constraints of separate xmax and ymax
00275  *          is not clear.
00276  */
00277 PIX *
00278 pixSeedfillBinaryRestricted(PIX     *pixd,
00279                             PIX     *pixs,
00280                             PIX     *pixm,
00281                             l_int32  connectivity,
00282                             l_int32  xmax,
00283                             l_int32  ymax)
00284 {
00285 l_int32  w, h;
00286 PIX     *pixr, *pixt;
00287 
00288     PROCNAME("pixSeedfillBinaryRestricted");
00289 
00290     if (xmax <= 0 && ymax <= 0)  /* no filling permitted */
00291         return pixClone(pixs);
00292     if (xmax < 0 || ymax < 0)
00293         return (PIX *)ERROR_PTR("pixt not made", procName, pixd);
00294 
00295         /* Full fill from the seed into the mask. */
00296     if ((pixt = pixSeedfillBinary(NULL, pixs, pixm, connectivity)) == NULL)
00297         return (PIX *)ERROR_PTR("pixt not made", procName, pixd);
00298 
00299         /* Dilate the seed.  This gives the maximal region where changes
00300          * are permitted.  Invert to get the region where pixs is
00301          * not allowed to change.  */
00302     pixr = pixDilateCompBrick(NULL, pixs, 2 * xmax + 1, 2 * ymax + 1);
00303     pixInvert(pixr, pixr);
00304 
00305         /* Blank the region of pixt specified by the fg of pixr.
00306          * This is not the final result, because it may have fg that
00307          * is not accessible from the seed in the restricted distance.
00308          * There we treat this as a new mask, and eliminate the
00309          * bad fg regions by doing a second seedfill from the original seed. */
00310     pixGetDimensions(pixs, &w, &h, NULL);
00311     pixRasterop(pixt, 0, 0, w, h, PIX_DST & PIX_NOT(PIX_SRC), pixr, 0, 0);
00312 
00313         /* Fill again from the seed, into this new mask. */
00314     pixd = pixSeedfillBinary(pixd, pixs, pixt, connectivity);
00315 
00316     pixDestroy(&pixt);
00317     pixDestroy(&pixr);
00318     return pixd;
00319 }
00320 
00321 
00322 /*!
00323  *  pixHolesByFilling()
00324  *
00325  *      Input:  pixs (1 bpp)
00326  *              connectivity (4 or 8)
00327  *      Return: pixd  (inverted image of all holes), or null on error
00328  *
00329  * Action:
00330  *     (1) Start with 1-pixel black border on otherwise white pixd
00331  *     (2) Use the inverted pixs as the filling mask to fill in
00332  *         all the pixels from the border to the pixs foreground
00333  *     (3) OR the result with pixs to have an image with all
00334  *         ON pixels except for the holes.
00335  *     (4) Invert the result to get the holes as foreground
00336  *
00337  * Notes:
00338  *     (1) To get 4-c.c. holes of the 8-c.c. as foreground, use
00339  *         4-connected filling; to get 8-c.c. holes of the 4-c.c.
00340  *         as foreground, use 8-connected filling.
00341  */
00342 PIX *
00343 pixHolesByFilling(PIX     *pixs,
00344                   l_int32  connectivity)
00345 {
00346 PIX  *pixsi, *pixd;
00347 
00348     PROCNAME("pixHolesByFilling");
00349 
00350     if (!pixs || pixGetDepth(pixs) != 1)
00351         return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00352     if (connectivity != 4 && connectivity != 8)
00353         return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00354 
00355     if ((pixd = pixCreateTemplate(pixs)) == NULL)
00356         return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
00357     if ((pixsi = pixInvert(NULL, pixs)) == NULL)
00358         return (PIX *)ERROR_PTR("pixsi not made", procName, NULL);
00359 
00360     pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
00361     pixSeedfillBinary(pixd, pixd, pixsi, connectivity);
00362     pixOr(pixd, pixd, pixs);
00363     pixInvert(pixd, pixd);
00364     pixDestroy(&pixsi);
00365 
00366     return pixd;
00367 }
00368 
00369 
00370 /*!
00371  *  pixFillClosedBorders()
00372  *
00373  *      Input:  pixs (1 bpp)
00374  *              filling connectivity (4 or 8)
00375  *      Return: pixd  (all topologically outer closed borders are filled
00376  *                     as connected comonents), or null on error
00377  *
00378  *  Notes:
00379  *      (1) Start with 1-pixel black border on otherwise white pixd
00380  *      (2) Subtract input pixs to remove border pixels that were
00381  *          also on the closed border
00382  *      (3) Use the inverted pixs as the filling mask to fill in
00383  *          all the pixels from the outer border to the closed border
00384  *          on pixs
00385  *      (4) Invert the result to get the filled component, including
00386  *          the input border
00387  *      (5) If the borders are 4-c.c., use 8-c.c. filling, and v.v.
00388  *      (6) Closed borders within c.c. that represent holes, etc., are filled.
00389  */
00390 PIX *
00391 pixFillClosedBorders(PIX     *pixs,
00392                      l_int32  connectivity)
00393 {
00394 PIX  *pixsi, *pixd;
00395 
00396     PROCNAME("pixFillClosedBorders");
00397 
00398     if (!pixs || pixGetDepth(pixs) != 1)
00399         return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00400     if (connectivity != 4 && connectivity != 8)
00401         return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00402 
00403     if ((pixd = pixCreateTemplate(pixs)) == NULL)
00404         return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
00405     pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
00406     pixSubtract(pixd, pixd, pixs);
00407     if ((pixsi = pixInvert(NULL, pixs)) == NULL)
00408         return (PIX *)ERROR_PTR("pixsi not made", procName, NULL);
00409 
00410     pixSeedfillBinary(pixd, pixd, pixsi, connectivity);
00411     pixInvert(pixd, pixd);
00412     pixDestroy(&pixsi);
00413 
00414     return pixd;
00415 }
00416 
00417 
00418 /*!
00419  *  pixExtractBorderConnComps()
00420  *
00421  *      Input:  pixs (1 bpp)
00422  *              filling connectivity (4 or 8)
00423  *      Return: pixd  (all pixels in the src that are in connected
00424  *                     components touching the border), or null on error
00425  */
00426 PIX *
00427 pixExtractBorderConnComps(PIX     *pixs,
00428                           l_int32  connectivity)
00429 {
00430 PIX  *pixd;
00431 
00432     PROCNAME("pixExtractBorderConnComps");
00433 
00434     if (!pixs || pixGetDepth(pixs) != 1)
00435         return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00436     if (connectivity != 4 && connectivity != 8)
00437         return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00438 
00439         /* Start with 1 pixel wide black border as seed in pixd */
00440     if ((pixd = pixCreateTemplate(pixs)) == NULL)
00441         return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
00442     pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET);
00443 
00444        /* Fill in pixd from the seed, using pixs as the filling mask.
00445         * This fills all components from pixs that are touching the border. */
00446     pixSeedfillBinary(pixd, pixd, pixs, connectivity);
00447 
00448     return pixd;
00449 }
00450 
00451 
00452 /*!
00453  *  pixRemoveBorderConnComps()
00454  *
00455  *      Input:  pixs (1 bpp)
00456  *              filling connectivity (4 or 8)
00457  *      Return: pixd  (all pixels in the src that are not touching the
00458  *                     border) or null on error
00459  */
00460 PIX *
00461 pixRemoveBorderConnComps(PIX     *pixs,
00462                          l_int32  connectivity)
00463 {
00464 PIX  *pixd;
00465 
00466     PROCNAME("pixRemoveBorderConnComps");
00467 
00468     if (!pixs || pixGetDepth(pixs) != 1)
00469         return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00470     if (connectivity != 4 && connectivity != 8)
00471         return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00472 
00473        /* Fill from a 1 pixel wide seed at the border into all components
00474         * in pixs (the filling mask) that are touching the border */
00475     pixd = pixExtractBorderConnComps(pixs, connectivity);
00476 
00477        /* Save in pixd only those components in pixs not touching the border */
00478     pixXor(pixd, pixd, pixs);
00479 
00480     return pixd;
00481 }
00482 
00483 
00484 /*-----------------------------------------------------------------------*
00485  *            Hole-filling of components to bounding rectangle           *
00486  *-----------------------------------------------------------------------*/
00487 /*!
00488  *  pixFillHolesToBoundingRect()
00489  *
00490  *      Input:  pixs (1 bpp)
00491  *              minsize (min number of pixels in the hole)
00492  *              maxhfract (max hole area as fraction of fg pixels in the cc)
00493  *              minfgfract (min fg area as fraction of bounding rectangle)
00494  *      Return: pixd (pixs, with some holes possibly filled and some c.c.
00495  *                    possibly expanded to their bounding rects),
00496  *                    or null on error
00497  *
00498  *  Notes:
00499  *      (1) This does not fill holes that are smaller in area than 'minsize'.
00500  *      (2) This does not fill holes with an area larger than
00501  *          'maxhfract' times the fg area of the c.c.
00502  *      (3) This does not expand the fg of the c.c. to bounding rect if
00503  *          the fg area is less than 'minfgfract' times the area of the
00504  *          bounding rect.
00505  *      (4) The decisions are made as follows:
00506  *           - Decide if we are filling the holes; if so, when using
00507  *             the fg area, include the filled holes.
00508  *           - Decide based on the fg area if we are filling to a bounding rect.
00509  *             If so, do it.
00510  *             If not, fill the holes if the condition is satisfied.
00511  *      (5) The choice of minsize depends on the resolution.
00512  *      (6) For solidifying image mask regions on printed materials,
00513  *          which tend to be rectangular, values for maxhfract
00514  *          and minfgfract around 0.5 are reasonable.
00515  */
00516 PIX *
00517 pixFillHolesToBoundingRect(PIX       *pixs,
00518                            l_int32    minsize,
00519                            l_float32  maxhfract,
00520                            l_float32  minfgfract)
00521 {
00522 l_int32    i, x, y, w, h, n, nfg, nh, ntot, area;
00523 l_int32   *tab;
00524 l_float32  hfract;  /* measured hole fraction */
00525 l_float32  fgfract;  /* measured fg fraction */
00526 BOXA      *boxa;
00527 PIX       *pixd, *pixfg, *pixh;
00528 PIXA      *pixa;
00529 
00530     PROCNAME("pixFillHolesToBoundingRect");
00531 
00532     if (!pixs || pixGetDepth(pixs) != 1)
00533         return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, NULL);
00534 
00535     pixd = pixCopy(NULL, pixs);
00536     boxa = pixConnComp(pixd, &pixa, 8);
00537     n = boxaGetCount(boxa);
00538     tab = makePixelSumTab8();
00539     for (i = 0; i < n; i++) {
00540         boxaGetBoxGeometry(boxa, i, &x, &y, &w, &h);
00541         area = w * h;
00542         if (area < minsize)
00543             continue;
00544         pixfg = pixaGetPix(pixa, i, L_COPY);
00545         pixh = pixHolesByFilling(pixfg, 4);  /* holes only */
00546         pixCountPixels(pixfg, &nfg, tab);
00547         pixCountPixels(pixh, &nh, tab);
00548         hfract = (l_float32)nh / (l_float32)nfg;
00549         ntot = nfg;
00550         if (hfract <= maxhfract)  /* we will fill the holes (at least) */
00551             ntot = nfg + nh;
00552         fgfract = (l_float32)ntot / (l_float32)area;
00553         if (fgfract >= minfgfract) {  /* fill to bounding rect */
00554             pixSetAll(pixfg);
00555             pixRasterop(pixd, x, y, w, h, PIX_SRC, pixfg, 0, 0);
00556         }
00557         else if (hfract <= maxhfract) {  /* fill just the holes */
00558             pixRasterop(pixd, x, y, w, h, PIX_DST | PIX_SRC , pixh, 0, 0);
00559         }
00560         pixDestroy(&pixfg);
00561         pixDestroy(&pixh);
00562     }
00563     boxaDestroy(&boxa);
00564     pixaDestroy(&pixa);
00565     FREE(tab);
00566 
00567     return pixd;
00568 }
00569 
00570 
00571 /*-----------------------------------------------------------------------*
00572  *             Vincent's hybrid Grayscale Seedfill method             *
00573  *-----------------------------------------------------------------------*/
00574 /*!
00575  *  pixSeedfillGray()
00576  *
00577  *      Input:  pixs  (8 bpp seed; filled in place)
00578  *              pixm  (8 bpp filling mask)
00579  *              connectivity  (4 or 8)
00580  *      Return: 0 if OK, 1 on error
00581  *
00582  *  Notes:
00583  *      (1) This is an in-place filling operation on the seed, pixs,
00584  *          where the clipping mask is always above or at the level
00585  *          of the seed as it is filled.
00586  *      (2) For details of the operation, see the description in
00587  *          seedfillGrayLow() and the code there.
00588  *      (3) As an example of use, see the description in pixHDome().
00589  *          There, the seed is an image where each pixel is a fixed
00590  *          amount smaller than the corresponding mask pixel.
00591  *      (4) Reference paper :
00592  *            L. Vincent, Morphological grayscale reconstruction in image
00593  *            analysis: applications and efficient algorithms, IEEE Transactions
00594  *            on  Image Processing, vol. 2, no. 2, pp. 176-201, 1993.
00595  */
00596 l_int32
00597 pixSeedfillGray(PIX     *pixs,
00598                 PIX     *pixm,
00599                 l_int32  connectivity)
00600 {
00601 l_int32    h, w, wpls, wplm;
00602 l_uint32  *datas, *datam;
00603 
00604     PROCNAME("pixSeedfillGray");
00605 
00606     if (!pixs || pixGetDepth(pixs) != 8)
00607         return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
00608     if (!pixm || pixGetDepth(pixm) != 8)
00609         return ERROR_INT("pixm not defined or not 8 bpp", procName, 1);
00610     if (connectivity != 4 && connectivity != 8)
00611         return ERROR_INT("connectivity not in {4,8}", procName, 1);
00612 
00613         /* Make sure the sizes of seed and mask images are the same */
00614     if (pixSizesEqual(pixs, pixm) == 0)
00615         return ERROR_INT("pixs and pixm sizes differ", procName, 1);
00616 
00617     datas = pixGetData(pixs);
00618     datam = pixGetData(pixm);
00619     wpls = pixGetWpl(pixs);
00620     wplm = pixGetWpl(pixm);
00621     pixGetDimensions(pixs, &w, &h, NULL);
00622     seedfillGrayLow(datas, w, h, wpls, datam, wplm, connectivity);
00623 
00624     return 0;
00625 }
00626 
00627 
00628 /*!
00629  *  pixSeedfillGrayInv()
00630  *
00631  *      Input:  pixs  (8 bpp seed; filled in place)
00632  *              pixm  (8 bpp filling mask)
00633  *              connectivity  (4 or 8)
00634  *      Return: 0 if OK, 1 on error
00635  *
00636  *  Notes:
00637  *      (1) This is an in-place filling operation on the seed, pixs,
00638  *          where the clipping mask is always below or at the level
00639  *          of the seed as it is filled.  Think of filling up a basin
00640  *          to a particular level, given by the maximum seed value
00641  *          in the basin.  Outside the filled region, the mask
00642  *          is above the filling level.
00643  *      (2) Contrast this with pixSeedfillGray(), where the clipping mask
00644  *          is always above or at the level of the fill.  An example
00645  *          of its use is the hdome fill, where the seed is an image
00646  *          where each pixel is a fixed amount smaller than the
00647  *          corresponding mask pixel.
00648  *      (3) The basin fill, pixSeedfillGrayBasin(), is a special case
00649  *          where the seed pixel values are generated from the mask,
00650  *          and where the implementation uses pixSeedfillGray() by
00651  *          inverting both the seed and mask.
00652  */
00653 l_int32
00654 pixSeedfillGrayInv(PIX     *pixs,
00655                    PIX     *pixm,
00656                    l_int32  connectivity)
00657 {
00658 l_int32    h, w, wpls, wplm;
00659 l_uint32  *datas, *datam;
00660 
00661     PROCNAME("pixSeedfillGrayInv");
00662 
00663     if (!pixs || pixGetDepth(pixs) != 8)
00664         return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
00665     if (!pixm || pixGetDepth(pixm) != 8)
00666         return ERROR_INT("pixm not defined or not 8 bpp", procName, 1);
00667     if (connectivity != 4 && connectivity != 8)
00668         return ERROR_INT("connectivity not in {4,8}", procName, 1);
00669 
00670         /* Make sure the sizes of seed and mask images are the same */
00671     if (pixSizesEqual(pixs, pixm) == 0)
00672         return ERROR_INT("pixs and pixm sizes differ", procName, 1);
00673 
00674     datas = pixGetData(pixs);
00675     datam = pixGetData(pixm);
00676     wpls = pixGetWpl(pixs);
00677     wplm = pixGetWpl(pixm);
00678     pixGetDimensions(pixs, &w, &h, NULL);
00679     seedfillGrayInvLow(datas, w, h, wpls, datam, wplm, connectivity);
00680 
00681     return 0;
00682 }
00683 
00684 /*-----------------------------------------------------------------------*
00685  *             Vincent's Iterative Grayscale Seedfill method             *
00686  *-----------------------------------------------------------------------*/
00687 /*!
00688  *  pixSeedfillGraySimple()
00689  *
00690  *      Input:  pixs  (8 bpp seed; filled in place)
00691  *              pixm  (8 bpp filling mask)
00692  *              connectivity  (4 or 8)
00693  *      Return: 0 if OK, 1 on error
00694  *
00695  *  Notes:
00696  *      (1) This is an in-place filling operation on the seed, pixs,
00697  *          where the clipping mask is always above or at the level
00698  *          of the seed as it is filled.
00699  *      (2) For details of the operation, see the description in
00700  *          seedfillGrayLowSimple() and the code there.
00701  *      (3) As an example of use, see the description in pixHDome().
00702  *          There, the seed is an image where each pixel is a fixed
00703  *          amount smaller than the corresponding mask pixel.
00704  *      (4) Reference paper :
00705  *            L. Vincent, Morphological grayscale reconstruction in image
00706  *            analysis: applications and efficient algorithms, IEEE Transactions
00707  *            on  Image Processing, vol. 2, no. 2, pp. 176-201, 1993.
00708  */
00709 l_int32
00710 pixSeedfillGraySimple(PIX     *pixs,
00711                       PIX     *pixm,
00712                       l_int32  connectivity)
00713 {
00714 l_int32    i, h, w, wpls, wplm, boolval;
00715 l_uint32  *datas, *datam;
00716 PIX       *pixt;
00717 
00718     PROCNAME("pixSeedfillGraySimple");
00719 
00720     if (!pixs || pixGetDepth(pixs) != 8)
00721         return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
00722     if (!pixm || pixGetDepth(pixm) != 8)
00723         return ERROR_INT("pixm not defined or not 8 bpp", procName, 1);
00724     if (connectivity != 4 && connectivity != 8)
00725         return ERROR_INT("connectivity not in {4,8}", procName, 1);
00726 
00727         /* Make sure the sizes of seed and mask images are the same */
00728     if (pixSizesEqual(pixs, pixm) == 0)
00729         return ERROR_INT("pixs and pixm sizes differ", procName, 1);
00730 
00731         /* This is used to test for completion */
00732     if ((pixt = pixCreateTemplate(pixs)) == NULL)
00733         return ERROR_INT("pixt not made", procName, 1);
00734 
00735     datas = pixGetData(pixs);
00736     datam = pixGetData(pixm);
00737     wpls = pixGetWpl(pixs);
00738     wplm = pixGetWpl(pixm);
00739     pixGetDimensions(pixs, &w, &h, NULL);
00740     for (i = 0; i < MAX_ITERS; i++) {
00741         pixCopy(pixt, pixs);
00742         seedfillGrayLowSimple(datas, w, h, wpls, datam, wplm, connectivity);
00743         pixEqual(pixs, pixt, &boolval);
00744         if (boolval == 1) {
00745 #if DEBUG_PRINT_ITERS
00746             L_INFO_INT("Gray seed fill converged: %d iters", procName, i + 1);
00747 #endif  /* DEBUG_PRINT_ITERS */
00748             break;
00749         }
00750     }
00751 
00752     pixDestroy(&pixt);
00753     return 0;
00754 }
00755 
00756 
00757 /*!
00758  *  pixSeedfillGrayInvSimple()
00759  *
00760  *      Input:  pixs  (8 bpp seed; filled in place)
00761  *              pixm  (8 bpp filling mask)
00762  *              connectivity  (4 or 8)
00763  *      Return: 0 if OK, 1 on error
00764  *
00765  *  Notes:
00766  *      (1) This is an in-place filling operation on the seed, pixs,
00767  *          where the clipping mask is always below or at the level
00768  *          of the seed as it is filled.  Think of filling up a basin
00769  *          to a particular level, given by the maximum seed value
00770  *          in the basin.  Outside the filled region, the mask
00771  *          is above the filling level.
00772  *      (2) Contrast this with pixSeedfillGraySimple(), where the clipping mask
00773  *          is always above or at the level of the fill.  An example
00774  *          of its use is the hdome fill, where the seed is an image
00775  *          where each pixel is a fixed amount smaller than the
00776  *          corresponding mask pixel.
00777  */
00778 l_int32
00779 pixSeedfillGrayInvSimple(PIX     *pixs,
00780                          PIX     *pixm,
00781                          l_int32  connectivity)
00782 {
00783 l_int32    i, h, w, wpls, wplm, boolval;
00784 l_uint32  *datas, *datam;
00785 PIX       *pixt;
00786 
00787     PROCNAME("pixSeedfillGrayInvSimple");
00788 
00789     if (!pixs || pixGetDepth(pixs) != 8)
00790         return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
00791     if (!pixm || pixGetDepth(pixm) != 8)
00792         return ERROR_INT("pixm not defined or not 8 bpp", procName, 1);
00793     if (connectivity != 4 && connectivity != 8)
00794         return ERROR_INT("connectivity not in {4,8}", procName, 1);
00795 
00796         /* Make sure the sizes of seed and mask images are the same */
00797     if (pixSizesEqual(pixs, pixm) == 0)
00798         return ERROR_INT("pixs and pixm sizes differ", procName, 1);
00799 
00800         /* This is used to test for completion */
00801     if ((pixt = pixCreateTemplate(pixs)) == NULL)
00802         return ERROR_INT("pixt not made", procName, 1);
00803 
00804     datas = pixGetData(pixs);
00805     datam = pixGetData(pixm);
00806     wpls = pixGetWpl(pixs);
00807     wplm = pixGetWpl(pixm);
00808     pixGetDimensions(pixs, &w, &h, NULL);
00809     for (i = 0; i < MAX_ITERS; i++) {
00810         pixCopy(pixt, pixs);
00811         seedfillGrayInvLowSimple(datas, w, h, wpls, datam, wplm, connectivity);
00812         pixEqual(pixs, pixt, &boolval);
00813         if (boolval == 1) {
00814 #if DEBUG_PRINT_ITERS
00815             L_INFO_INT("Gray seed fill converged: %d iters", procName, i + 1);
00816 #endif  /* DEBUG_PRINT_ITERS */
00817             break;
00818         }
00819     }
00820 
00821     pixDestroy(&pixt);
00822     return 0;
00823 }
00824 
00825 
00826 /*-----------------------------------------------------------------------*
00827  *                         Gray seedfill variations                      *
00828  *-----------------------------------------------------------------------*/
00829 /*!
00830  *  pixSeedfillGrayBasin()
00831  *
00832  *      Input:  pixb  (binary mask giving seed locations)
00833  *              pixm  (8 bpp basin-type filling mask)
00834  *              delta (amount of seed value above mask)
00835  *              connectivity  (4 or 8)
00836  *      Return: pixd (filled seed) if OK, null on error
00837  *
00838  *  Notes:
00839  *      (1) This fills from a seed within basins defined by a filling mask.
00840  *          The seed value(s) are greater than the corresponding
00841  *          filling mask value, and the result has the bottoms of
00842  *          the basins raised by the initial seed value.
00843  *      (2) The seed has value 255 except where pixb has fg (1), which
00844  *          are the seed 'locations'.  At the seed locations, the seed
00845  *          value is the corresponding value of the mask pixel in pixm
00846  *          plus @delta.  If @delta == 0, we return a copy of pixm.
00847  *      (3) The actual filling is done using the standard grayscale filling
00848  *          operation on the inverse of the mask and using the inverse
00849  *          of the seed image.  After filling, we return the inverse of
00850  *          the filled seed.
00851  *      (4) As an example of use: pixm can describe a grayscale image
00852  *          of text, where the (dark) text pixels are basins of
00853  *          low values; pixb can identify the local minima in pixm (say, at
00854  *          the bottom of the basins); and delta is the amount that we wish
00855  *          to raise (lighten) the basins.  We construct the seed
00856  *          (a.k.a marker) image from pixb, pixm and @delta.
00857  */
00858 PIX *
00859 pixSeedfillGrayBasin(PIX     *pixb,
00860                      PIX     *pixm,
00861                      l_int32  delta,
00862                      l_int32  connectivity)
00863 {
00864 PIX  *pixbi, *pixmi, *pixsd;
00865 
00866     PROCNAME("pixSeedfillGrayBasin");
00867 
00868     if (!pixb || pixGetDepth(pixb) != 1)
00869         return (PIX *)ERROR_PTR("pixb undefined or not 1 bpp", procName, NULL);
00870     if (!pixm || pixGetDepth(pixm) != 8)
00871         return (PIX *)ERROR_PTR("pixm undefined or not 8 bpp", procName, NULL);
00872     if (connectivity != 4 && connectivity != 8)
00873         return (PIX *)ERROR_PTR("connectivity not in {4,8}", procName, NULL);
00874 
00875     if (delta <= 0) {
00876         L_WARNING("delta <= 0; returning a copy of pixm", procName);
00877         return pixCopy(NULL, pixm);
00878     }
00879 
00880         /* Add delta to every pixel in pixm */
00881     pixsd = pixCopy(NULL, pixm);
00882     pixAddConstantGray(pixsd, delta);
00883 
00884         /* Prepare the seed.  Write 255 in all pixels of
00885          * ([pixm] + delta) where pixb is 0. */
00886     pixbi = pixInvert(NULL, pixb);
00887     pixSetMasked(pixsd, pixbi, 255);
00888 
00889         /* Fill the inverse seed, using the inverse clipping mask */
00890     pixmi = pixInvert(NULL, pixm);
00891     pixInvert(pixsd, pixsd);
00892     pixSeedfillGray(pixsd, pixmi, connectivity);
00893 
00894         /* Re-invert the filled seed */
00895     pixInvert(pixsd, pixsd);
00896 
00897     pixDestroy(&pixbi);
00898     pixDestroy(&pixmi);
00899     return pixsd;
00900 }
00901 
00902 
00903 /*-----------------------------------------------------------------------*
00904  *                   Vincent's Distance Function method                  *
00905  *-----------------------------------------------------------------------*/
00906 /*!
00907  *  pixDistanceFunction()
00908  *
00909  *      Input:  pixs  (1 bpp source)
00910  *              connectivity  (4 or 8)
00911  *              outdepth (8 or 16 bits for pixd)
00912  *              boundcond (L_BOUNDARY_BG, L_BOUNDARY_FG)
00913  *      Return: pixd, or null on error
00914  *
00915  *  Notes:
00916  *      (1) This computes the distance of each pixel from the nearest
00917  *          background pixel.  All bg pixels therefore have a distance of 0,
00918  *          and the fg pixel distances increase linearly from 1 at the
00919  *          boundary.  It can also be used to compute the distance of
00920  *          each pixel from the nearest fg pixel, by inverting the input
00921  *          image before calling this function.  Then all fg pixels have
00922  *          a distance 0 and the bg pixel distances increase linearly
00923  *          from 1 at the boundary.
00924  *      (2) The algorithm, described in Leptonica on the page on seed
00925  *          filling and connected components, is due to Luc Vincent.
00926  *          In brief, we generate an 8 or 16 bpp image, initialized
00927  *          with the fg pixels of the input pix set to 1 and the
00928  *          1-boundary pixels (i.e., the boundary pixels of width 1 on
00929  *          the four sides set as either:
00930  *            * L_BOUNDARY_BG: 0
00931  *            * L_BOUNDARY_FG:  max
00932  *          where max = 0xff for 8 bpp and 0xffff for 16 bpp.
00933  *          Then do raster/anti-raster sweeps over all pixels interior
00934  *          to the 1-boundary, where the value of each new pixel is
00935  *          taken to be 1 more than the minimum of the previously-seen
00936  *          connected pixels (using either 4 or 8 connectivity).
00937  *          Finally, set the 1-boundary pixels using the mirrored method;
00938  *          this removes the max values there.
00939  *      (3) Using L_BOUNDARY_BG clamps the distance to 0 at the
00940  *          boundary.  Using L_BOUNDARY_FG allows the distance
00941  *          at the image boundary to "float".
00942  *      (4) For 4-connected, one could initialize only the left and top
00943  *          1-boundary pixels, and go all the way to the right
00944  *          and bottom; then coming back reset left and top.  But we
00945  *          instead use a method that works for both 4- and 8-connected.
00946  */
00947 PIX *
00948 pixDistanceFunction(PIX     *pixs,
00949                     l_int32  connectivity,
00950                     l_int32  outdepth,
00951                     l_int32  boundcond)
00952 {
00953 l_int32    w, h, wpld;
00954 l_uint32  *datad;
00955 PIX       *pixd;
00956 
00957     PROCNAME("pixDistanceFunction");
00958 
00959     if (!pixs || pixGetDepth(pixs) != 1)
00960         return (PIX *)ERROR_PTR("!pixs or pixs not 1 bpp", procName, NULL);
00961     if (connectivity != 4 && connectivity != 8)
00962         return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
00963     if (outdepth != 8 && outdepth != 16)
00964         return (PIX *)ERROR_PTR("outdepth not 8 or 16 bpp", procName, NULL);
00965     if (boundcond != L_BOUNDARY_BG && boundcond != L_BOUNDARY_FG)
00966         return (PIX *)ERROR_PTR("invalid boundcond", procName, NULL);
00967 
00968     pixGetDimensions(pixs, &w, &h, NULL);
00969     if ((pixd = pixCreate(w, h, outdepth)) == NULL)
00970         return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
00971     datad = pixGetData(pixd);
00972     wpld = pixGetWpl(pixd);
00973 
00974         /* Initialize the fg pixels to 1 and the bg pixels to 0 */
00975     pixSetMasked(pixd, pixs, 1);
00976 
00977     if (boundcond == L_BOUNDARY_BG)
00978         distanceFunctionLow(datad, w, h, outdepth, wpld, connectivity);
00979     else {  /* L_BOUNDARY_FG: set boundary pixels to max val */
00980         pixRasterop(pixd, 0, 0, w, 1, PIX_SET, NULL, 0, 0);   /* top */
00981         pixRasterop(pixd, 0, h - 1, w, 1, PIX_SET, NULL, 0, 0);   /* bot */
00982         pixRasterop(pixd, 0, 0, 1, h, PIX_SET, NULL, 0, 0);   /* left */
00983         pixRasterop(pixd, w - 1, 0, 1, h, PIX_SET, NULL, 0, 0);   /* right */
00984 
00985         distanceFunctionLow(datad, w, h, outdepth, wpld, connectivity);
00986 
00987             /* Set each boundary pixel equal to the pixel next to it */
00988         pixSetMirroredBorder(pixd, 1, 1, 1, 1);
00989     }
00990 
00991     return pixd;
00992 }
00993 
00994 
00995 /*-----------------------------------------------------------------------*
00996  *                Seed spread (based on distance function)               *
00997  *-----------------------------------------------------------------------*/
00998 /*!
00999  *  pixSeedspread()
01000  *
01001  *      Input:  pixs  (8 bpp source)
01002  *              connectivity  (4 or 8)
01003  *      Return: pixd, or null on error
01004  *
01005  *  Notes:
01006  *      (1) The raster/anti-raster method for implementing this filling
01007  *          operation was suggested by Ray Smith.
01008  *      (2) This takes an arbitrary set of nonzero pixels in pixs, which
01009  *          can be sparse, and spreads (extrapolates) the values to
01010  *          fill all the pixels in pixd with the nonzero value it is
01011  *          closest to in pixs.  This is similar (though not completely
01012  *          equivalent) to doing a Voronoi tiling of the image, with a
01013  *          tile surrounding each pixel that has a nonzero value.
01014  *          All pixels within a tile are then closer to its "central"
01015  *          pixel than to any others.  Then assign the value of the
01016  *          "central" pixel to each pixel in the tile.
01017  *      (3) This is implemented by computing a distance function in parallel
01018  *          with the fill.  The distance function uses free boundary
01019  *          conditions (assumed maxval outside), and it controls the
01020  *          propagation of the pixels in pixd away from the nonzero
01021  *          (seed) values.  This is done in 2 traversals (raster/antiraster).
01022  *          In the raster direction, whenever the distance function
01023  *          is nonzero, the spread pixel takes on the value of its
01024  *          predecessor that has the minimum distance value.  In the
01025  *          antiraster direction, whenever the distance function is nonzero
01026  *          and its value is replaced by a smaller value, the spread
01027  *          pixel takes the value of the predecessor with the minimum
01028  *          distance value.
01029  *      (4) At boundaries where a pixel is equidistant from two
01030  *          nearest nonzero (seed) pixels, the decision of which value
01031  *          to use is arbitrary (greedy in search for minimum distance).
01032  *          This can give rise to strange-looking results, particularly
01033  *          for 4-connectivity where the L1 distance is computed from
01034  *          steps in N,S,E and W directions (no diagonals).
01035  */
01036 PIX *
01037 pixSeedspread(PIX     *pixs,
01038               l_int32  connectivity)
01039 {
01040 l_int32    w, h, wplt, wplg;
01041 l_uint32  *datat, *datag;
01042 PIX       *pixm, *pixt, *pixg, *pixd;
01043 
01044     PROCNAME("pixSeedspread");
01045 
01046     if (!pixs || pixGetDepth(pixs) != 8)
01047         return (PIX *)ERROR_PTR("!pixs or pixs not 8 bpp", procName, NULL);
01048     if (connectivity != 4 && connectivity != 8)
01049         return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
01050 
01051         /* Add a 4 byte border to pixs.  This simplifies the computation. */
01052     pixg = pixAddBorder(pixs, 4, 0);
01053     pixGetDimensions(pixg, &w, &h, NULL);
01054 
01055         /* Initialize distance function pixt.  Threshold pixs to get
01056          * a 0 at the seed points where the pixs pixel is nonzero, and
01057          * a 1 at all points that need to be filled.  Use this as a
01058          * mask to set a 1 in pixt at all non-seed points.  Also, set all
01059          * pixt pixels in an interior boundary of width 1 to the
01060          * maximum value.   For debugging, to view the distance function,
01061          * use pixConvert16To8(pixt, 0) on small images.  */
01062     pixm = pixThresholdToBinary(pixg, 1);
01063     pixt = pixCreate(w, h, 16);
01064     pixSetMasked(pixt, pixm, 1);
01065     pixRasterop(pixt, 0, 0, w, 1, PIX_SET, NULL, 0, 0);   /* top */
01066     pixRasterop(pixt, 0, h - 1, w, 1, PIX_SET, NULL, 0, 0);   /* bot */
01067     pixRasterop(pixt, 0, 0, 1, h, PIX_SET, NULL, 0, 0);   /* left */
01068     pixRasterop(pixt, w - 1, 0, 1, h, PIX_SET, NULL, 0, 0);   /* right */
01069     datat = pixGetData(pixt);
01070     wplt = pixGetWpl(pixt);
01071 
01072         /* Do the interpolation and remove the border. */
01073     datag = pixGetData(pixg);
01074     wplg = pixGetWpl(pixg);
01075     seedspreadLow(datag, w, h, wplg, datat, wplt, connectivity);
01076     pixd = pixRemoveBorder(pixg, 4);
01077 
01078     pixDestroy(&pixm);
01079     pixDestroy(&pixg);
01080     pixDestroy(&pixt);
01081     return pixd;
01082 }
01083 
01084 
01085 
01086 /*-----------------------------------------------------------------------*
01087  *                              Local extrema                            *
01088  *-----------------------------------------------------------------------*/
01089 /*!
01090  *  pixLocalExtrema()
01091  *
01092  *      Input:  pixs  (8 bpp)
01093  *              maxmin (max allowed for the min in a 3x3 neighborhood;
01094  *                      use 0 for default which is to have no upper bound)
01095  *              minmax (min allowed for the max in a 3x3 neighborhood;
01096  *                      use 0 for default which is to have no lower bound)
01097  *              &ppixmin (<optional return> mask of local minima)
01098  *              &ppixmax (<optional return> mask of local maxima)
01099  *      Return: 0 if OK, 1 on error
01100  *
01101  *  Notes:
01102  *      (1) This gives the actual local minima and maxima.
01103  *          A local minimum is a pixel whose surrounding pixels all
01104  *          have values at least as large, and likewise for a local
01105  *          maximum.  For the local minima, @maxmin is the upper
01106  *          bound for the value of pixs.  Likewise, for the local maxima,
01107  *          @minmax is the lower bound for the value of pixs.
01108  *      (2) The minima are found by starting with the erosion-and-equality
01109  *          approach of pixSelectedLocalExtrema.  This is followed
01110  *          by a qualification step, where each c.c. in the resulting
01111  *          minimum mask is extracted, the pixels bordering it are
01112  *          located, and they are queried.  If all of those pixels
01113  *          are larger than the value of that minimum, it is a true
01114  *          minimum and its c.c. is saved; otherwise the c.c. is
01115  *          rejected.  Note that if a bordering pixel has the
01116  *          same value as the minimum, it must then have a
01117  *          neighbor that is smaller, so the component is not a
01118  *          true minimum.
01119  *      (3) The maxima are found by inverting the image and looking
01120  *          for the minima there.
01121  *      (4) The generated masks can be used as markers for
01122  *          further operations.
01123  */
01124 l_int32
01125 pixLocalExtrema(PIX     *pixs,
01126                 l_int32  maxmin,
01127                 l_int32  minmax,
01128                 PIX    **ppixmin,
01129                 PIX    **ppixmax)
01130 {
01131 PIX  *pixmin, *pixmax, *pixt1, *pixt2;
01132 
01133     PROCNAME("pixLocalExtrema");
01134 
01135     if (!pixs || pixGetDepth(pixs) != 8)
01136         return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
01137     if (!ppixmin && !ppixmax)
01138         return ERROR_INT("neither &pixmin, &pixmax are defined", procName, 1);
01139     if (maxmin <= 0) maxmin = 254;
01140     if (minmax <= 0) minmax = 1;
01141 
01142     if (ppixmin) {
01143         pixt1 = pixErodeGray(pixs, 3, 3);
01144         pixmin = pixFindEqualValues(pixs, pixt1);
01145         pixDestroy(&pixt1);
01146         pixQualifyLocalMinima(pixs, pixmin, maxmin);
01147         *ppixmin = pixmin;
01148     }
01149 
01150     if (ppixmax) {
01151         pixt1 = pixInvert(NULL, pixs);
01152         pixt2 = pixErodeGray(pixt1, 3, 3);
01153         pixmax = pixFindEqualValues(pixt1, pixt2);
01154         pixDestroy(&pixt2);
01155         pixQualifyLocalMinima(pixt1, pixmax, 255 - minmax);
01156         *ppixmax = pixmax;
01157         pixDestroy(&pixt1);
01158     }
01159 
01160     return 0;
01161 }
01162 
01163 
01164 /*!
01165  *  pixQualifyLocalMinima()
01166  *
01167  *      Input:  pixs  (8 bpp)
01168  *              pixm  (1 bpp mask of values equal to min in 3x3 neighborhood)
01169  *              maxval (max allowed for the min in a 3x3 neighborhood;
01170  *                      use 0 for default which is to have no upper bound)
01171  *      Return: 0 if OK, 1 on error
01172  *
01173  *  Notes:
01174  *      (1) This function acts in-place to remove all c.c. in pixm
01175  *          that are not true local minima.  See notes in pixLocalExtrema().
01176  *      (2) The maximum allowed value for each local minimum can be
01177  *          bounded with @maxval.  Use 0 for default, which is to have
01178  *          no upper bound (equivalent to maxval == 254).
01179  */
01180 static l_int32
01181 pixQualifyLocalMinima(PIX     *pixs,
01182                       PIX     *pixm,
01183                       l_int32  maxval)
01184 {
01185 l_int32    n, i, j, k, x, y, w, h, xc, yc, wc, hc, xon, yon;
01186 l_int32    vals, wpls, wplc, ismin;
01187 l_uint32   val;
01188 l_uint32  *datas, *datac, *lines, *linec;
01189 BOXA      *boxa;
01190 PIX       *pixt1, *pixt2, *pixc;
01191 PIXA      *pixa;
01192 
01193     PROCNAME("pixQualifyLocalMinima");
01194 
01195     if (!pixs || pixGetDepth(pixs) != 8)
01196         return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
01197     if (!pixm || pixGetDepth(pixm) != 1)
01198         return ERROR_INT("pixm not defined or not 1 bpp", procName, 1);
01199     if (maxval <= 0) maxval = 254;
01200 
01201     pixGetDimensions(pixs, &w, &h, NULL);
01202     datas = pixGetData(pixs);
01203     wpls = pixGetWpl(pixs);
01204     boxa = pixConnComp(pixm, &pixa, 8);
01205     n = pixaGetCount(pixa);
01206     for (k = 0; k < n; k++) {
01207         boxaGetBoxGeometry(boxa, k, &xc, &yc, &wc, &hc);
01208         pixt1 = pixaGetPix(pixa, k, L_COPY);
01209         pixt2 = pixAddBorder(pixt1, 1, 0);
01210         pixc = pixDilateBrick(NULL, pixt2, 3, 3);
01211         pixXor(pixc, pixc, pixt2);  /* exterior boundary pixels */
01212         datac = pixGetData(pixc);
01213         wplc = pixGetWpl(pixc);
01214         nextOnPixelInRaster(pixt1, 0, 0, &xon, &yon);
01215         pixGetPixel(pixs, xc + xon, yc + yon, &val);
01216         if (val > maxval) {  /* too large; erase */
01217             pixRasterop(pixm, xc, yc, wc, hc, PIX_XOR, pixt1, 0, 0);
01218             pixDestroy(&pixt1);
01219             pixDestroy(&pixt2);
01220             pixDestroy(&pixc);
01221             continue;
01222         }
01223         ismin = TRUE;
01224         for (i = 0, y = yc - 1; i < hc + 2 && y >= 0 && y < h; i++, y++) {
01225             lines = datas + y * wpls;
01226             linec = datac + i * wplc;
01227             for (j = 0, x = xc - 1; j < wc + 2 && x >= 0 && x < w; j++, x++) {
01228                 if (GET_DATA_BIT(linec, j)) {
01229                     vals = GET_DATA_BYTE(lines, x);
01230                     if (vals <= val) {  /* not a minimum! */
01231                         ismin = FALSE;
01232                         break;
01233                     }
01234                 }
01235             }
01236             if (!ismin)
01237                 break;
01238         }
01239         if (!ismin)  /* erase it */
01240             pixRasterop(pixm, xc, yc, wc, hc, PIX_XOR, pixt1, 0, 0);
01241         pixDestroy(&pixt1);
01242         pixDestroy(&pixt2);
01243         pixDestroy(&pixc);
01244     }
01245 
01246     boxaDestroy(&boxa);
01247     pixaDestroy(&pixa);
01248     return 0;
01249 }
01250 
01251 
01252 /*!
01253  *  pixSelectedLocalExtrema()
01254  *
01255  *      Input:  pixs  (8 bpp)
01256  *              mindist (-1 for keeping all pixels; >= 0 specifies distance)
01257  *              &ppixmin (<return> mask of local minima)
01258  *              &ppixmax (<return> mask of local maxima)
01259  *      Return: 0 if OK, 1 on error
01260  *
01261  *  Notes:
01262  *      (1) This selects those local 3x3 minima that are at least a
01263  *          specified distance from the nearest local 3x3 maxima, and v.v.
01264  *          for the selected set of local 3x3 maxima.
01265  *          The local 3x3 minima is the set of pixels whose value equals
01266  *          the value after a 3x3 brick erosion, and the local 3x3 maxima
01267  *          is the set of pixels whose value equals the value after
01268  *          a 3x3 brick dilation.
01269  *      (2) mindist is the minimum distance allowed between
01270  *          local 3x3 minima and local 3x3 maxima, in an 8-connected sense.
01271  *          mindist == 1 keeps all pixels found in step 1.
01272  *          mindist == 0 removes all pixels from each mask that are
01273  *          both a local 3x3 minimum and a local 3x3 maximum.
01274  *          mindist == 1 removes any local 3x3 minimum pixel that touches a
01275  *          local 3x3 maximum pixel, and likewise for the local maxima.
01276  *          To make the decision, visualize each local 3x3 minimum pixel
01277  *          as being surrounded by a square of size (2 * mindist + 1)
01278  *          on each side, such that no local 3x3 maximum pixel is within
01279  *          that square; and v.v.
01280  *      (3) The generated masks can be used as markers for further operations.
01281  */
01282 l_int32
01283 pixSelectedLocalExtrema(PIX     *pixs,
01284                         l_int32  mindist,
01285                         PIX    **ppixmin,
01286                         PIX    **ppixmax)
01287 {
01288 PIX  *pixmin, *pixmax, *pixt, *pixtmin, *pixtmax;
01289 
01290     PROCNAME("pixSelectedLocalExtrema");
01291 
01292     if (!pixs || pixGetDepth(pixs) != 8)
01293         return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
01294     if (!ppixmin || !ppixmax)
01295         return ERROR_INT("&pixmin and &pixmax not both defined", procName, 1);
01296 
01297     pixt = pixErodeGray(pixs, 3, 3);
01298     pixmin = pixFindEqualValues(pixs, pixt);
01299     pixDestroy(&pixt);
01300     pixt = pixDilateGray(pixs, 3, 3);
01301     pixmax = pixFindEqualValues(pixs, pixt);
01302     pixDestroy(&pixt);
01303 
01304         /* Remove all points that are within the prescribed distance
01305          * from each other. */
01306     if (mindist < 0) {  /* remove no points */
01307         *ppixmin = pixmin;
01308         *ppixmax = pixmax;
01309     } else if (mindist == 0) {  /* remove points belonging to both sets */
01310         pixt = pixAnd(NULL, pixmin, pixmax);
01311         *ppixmin = pixSubtract(pixmin, pixmin, pixt);
01312         *ppixmax = pixSubtract(pixmax, pixmax, pixt);
01313         pixDestroy(&pixt);
01314     } else {
01315         pixtmin = pixDilateBrick(NULL, pixmin,
01316                                  2 * mindist + 1, 2 * mindist + 1);
01317         pixtmax = pixDilateBrick(NULL, pixmax,
01318                                  2 * mindist + 1, 2 * mindist + 1);
01319         *ppixmin = pixSubtract(pixmin, pixmin, pixtmax);
01320         *ppixmax = pixSubtract(pixmax, pixmax, pixtmin);
01321         pixDestroy(&pixtmin);
01322         pixDestroy(&pixtmax);
01323     }
01324     return 0;
01325 }
01326 
01327 
01328 /*!
01329  *  pixFindEqualValues()
01330  *
01331  *      Input:  pixs1 (8 bpp)
01332  *              pixs2 (8 bpp)
01333  *      Return: pixd (1 bpp mask), or null on error
01334  *
01335  *  Notes:
01336  *      (1) The two images are aligned at the UL corner, and the returned
01337  *          image has ON pixels where the pixels in pixs1 and pixs2
01338  *          have equal values.
01339  */
01340 PIX *
01341 pixFindEqualValues(PIX  *pixs1,
01342                    PIX  *pixs2)
01343 {
01344 l_int32    w1, h1, w2, h2, w, h;
01345 l_int32    i, j, val1, val2, wpls1, wpls2, wpld;
01346 l_uint32  *datas1, *datas2, *datad, *lines1, *lines2, *lined;
01347 PIX       *pixd;
01348 
01349     PROCNAME("pixFindEqualValues");
01350 
01351     if (!pixs1 || pixGetDepth(pixs1) != 8)
01352         return (PIX *)ERROR_PTR("pixs1 undefined or not 8 bpp", procName, NULL);
01353     if (!pixs2 || pixGetDepth(pixs2) != 8)
01354         return (PIX *)ERROR_PTR("pixs2 undefined or not 8 bpp", procName, NULL);
01355     pixGetDimensions(pixs1, &w1, &h1, NULL);
01356     pixGetDimensions(pixs2, &w2, &h2, NULL);
01357     w = L_MIN(w1, w2);
01358     h = L_MIN(h1, h2);
01359     pixd = pixCreate(w, h, 1);
01360     datas1 = pixGetData(pixs1);
01361     datas2 = pixGetData(pixs2);
01362     datad = pixGetData(pixd);
01363     wpls1 = pixGetWpl(pixs1);
01364     wpls2 = pixGetWpl(pixs2);
01365     wpld = pixGetWpl(pixd);
01366 
01367     for (i = 0; i < h; i++) {
01368         lines1 = datas1 + i * wpls1;
01369         lines2 = datas2 + i * wpls2;
01370         lined = datad + i * wpld;
01371         for (j = 0; j < w; j++) {
01372             val1 = GET_DATA_BYTE(lines1, j);
01373             val2 = GET_DATA_BYTE(lines2, j);
01374             if (val1 == val2)
01375                 SET_DATA_BIT(lined, j);
01376         }
01377     }
01378 
01379     return pixd;
01380 }
01381 
01382 
01383 /*-----------------------------------------------------------------------*
01384  *             Selection of minima in mask connected components          *
01385  *-----------------------------------------------------------------------*/
01386 /*!
01387  *  pixSelectMinInConnComp()
01388  *
01389  *      Input:  pixs (8 bpp)
01390  *              pixm (1 bpp)
01391  *              &nav (<optional return> numa of minima values)
01392  *      Return: pta (of min pixels), or null on error
01393  *
01394  *  Notes:
01395  *      (1) For each 8 connected component in pixm, this finds
01396  *          a pixel in pixs that has the lowest value, and saves
01397  *          it in a Pta.  If several pixels in pixs have the same
01398  *          minimum value, it picks the first one found.
01399  *      (2) For a mask pixm of true local minima, all pixels in each
01400  *          connected component have the same value in pixs, so it is
01401  *          fastest to select one of them using a special seedfill
01402  *          operation.  Not yet implemented.
01403  */
01404 PTA *
01405 pixSelectMinInConnComp(PIX    *pixs,
01406                        PIX    *pixm,
01407                        NUMA  **pnav)
01408 {
01409 l_int32    ws, hs, wm, hm, w, h, bx, by, bw, bh, i, j, c, n;
01410 l_int32    xs, ys, minx, miny, wpls, wplt, val, minval;
01411 l_uint32  *datas, *datat, *lines, *linet;
01412 BOXA      *boxa;
01413 NUMA      *nav;
01414 PIX       *pixt;
01415 PIXA      *pixa;
01416 PTA       *pta;
01417 
01418     PROCNAME("pixSelectMinInConnComp");
01419 
01420     if (!pixs || pixGetDepth(pixs) != 8)
01421         return (PTA *)ERROR_PTR("pixs undefined or not 8 bpp", procName, NULL);
01422     if (!pixm || pixGetDepth(pixm) != 1)
01423         return (PTA *)ERROR_PTR("pixm undefined or not 1 bpp", procName, NULL);
01424     pixGetDimensions(pixs, &ws, &hs, NULL);
01425     pixGetDimensions(pixm, &wm, &hm, NULL);
01426     w = L_MIN(ws, wm);
01427     h = L_MIN(hs, hm);
01428 
01429     boxa = pixConnComp(pixm, &pixa, 8);
01430     n = boxaGetCount(boxa);
01431     pta = ptaCreate(n);
01432     nav = numaCreate(n);
01433     datas = pixGetData(pixs);
01434     wpls = pixGetWpl(pixs);
01435     for (c = 0; c < n; c++) {
01436         pixt = pixaGetPix(pixa, c, L_CLONE);
01437         boxaGetBoxGeometry(boxa, c, &bx, &by, &bw, &bh);
01438         if (bw == 1 && bh == 1) {
01439             ptaAddPt(pta, bx, by);
01440             numaAddNumber(nav, GET_DATA_BYTE(datas + by * wpls, bx));
01441             pixDestroy(&pixt);
01442             continue;
01443         }
01444         datat = pixGetData(pixt);
01445         wplt = pixGetWpl(pixt);
01446         minx = miny = 1000000;
01447         minval = 256;
01448         for (i = 0; i < bh; i++) {
01449             ys = by + i;
01450             lines = datas + ys * wpls;
01451             linet = datat + i * wplt;
01452             for (j = 0; j < bw; j++) {
01453                 xs = bx + j;
01454                 if (GET_DATA_BIT(linet, j)) {
01455                     val = GET_DATA_BYTE(lines, xs);
01456                     if (val < minval) {
01457                         minval = val;
01458                         minx = xs;
01459                         miny = ys;
01460                     }
01461                 }
01462             }
01463         }
01464         ptaAddPt(pta, minx, miny);
01465         numaAddNumber(nav, GET_DATA_BYTE(datas + miny * wpls, minx));
01466         pixDestroy(&pixt);
01467     }
01468 
01469     boxaDestroy(&boxa);
01470     pixaDestroy(&pixa);
01471     if (pnav)
01472         *pnav = nav;
01473     else
01474         numaDestroy(&nav);
01475     return pta;
01476 }
01477 
01478 
01479 /*-----------------------------------------------------------------------*
01480  *            Removal of seeded connected components from a mask         *
01481  *-----------------------------------------------------------------------*/
01482 /*!
01483  *  pixRemoveSeededComponents()
01484  *
01485  *      Input:  pixd  (<optional>; this can be null or equal to pixm; 1 bpp)
01486  *              pixs  (1 bpp seed)
01487  *              pixm  (1 bpp filling mask)
01488  *              connectivity  (4 or 8)
01489  *              bordersize (amount of border clearing)
01490  *      Return: pixd, or null on error
01491  *
01492  *  Notes:
01493  *      (1) This removes each component in pixm for which there is
01494  *          at least one seed in pixs.  If pixd == NULL, this returns
01495  *          the result in a new pixd.  Otherwise, it is an in-place
01496  *          operation on pixm.  In no situation is pixs altered,
01497  *          because we do the filling with a copy of pixs.
01498  *      (2) If bordersize > 0, it also clears all pixels within a
01499  *          distance @bordersize of the edge of pixd.  This is here
01500  *          because pixLocalExtrema() typically finds local minima
01501  *          at the border.  Use @bordersize >= 2 to remove these.
01502  */
01503 PIX *
01504 pixRemoveSeededComponents(PIX     *pixd,
01505                           PIX     *pixs,
01506                           PIX     *pixm,
01507                           l_int32  connectivity,
01508                           l_int32  bordersize)
01509 {
01510 PIX  *pixt;
01511 
01512     PROCNAME("pixRemoveSeededComponents");
01513 
01514     if (!pixs || pixGetDepth(pixs) != 1)
01515         return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", procName, pixd);
01516     if (!pixm || pixGetDepth(pixm) != 1)
01517         return (PIX *)ERROR_PTR("pixm undefined or not 1 bpp", procName, pixd);
01518     if (pixd && pixd != pixm)
01519         return (PIX *)ERROR_PTR("operation not inplace", procName, pixd);
01520 
01521     pixt = pixCopy(NULL, pixs);
01522     pixSeedfillBinary(pixt, pixt, pixm, connectivity);
01523     pixd = pixXor(pixd, pixm, pixt);
01524     if (bordersize > 0)
01525         pixSetOrClearBorder(pixd, bordersize, bordersize, bordersize,
01526                             bordersize, PIX_CLR);
01527     pixDestroy(&pixt);
01528     return pixd;
01529 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines