/*====================================================================* - Copyright (C) 2001 Leptonica. All rights reserved. - This software is distributed in the hope that it will be - useful, but with NO WARRANTY OF ANY KIND. - No author or distributor accepts responsibility to anyone for the - consequences of using this software, or for whether it serves any - particular purpose or works at all, unless he or she says so in - writing. Everyone is granted permission to copy, modify and - redistribute this source code, for commercial or non-commercial - purposes, with the following restrictions: (1) the origin of this - source code must not be misrepresented; (2) modified versions must - be plainly marked as such; and (3) this notice may not be removed - or altered from any source or modified source distribution. *====================================================================*/ /* * seedfill.c: Luc Vincent iterative raster algorithms * * Binary seedfill: * PIX *pixSeedfillBinary() * * Applications of binary seedfill to find and fill holes, * and to remove c.c. touching the border: * PIX *pixHolesByFilling() * PIX *pixFillClosedBorders() * PIX *pixRemoveBorderConnComps() * * Gray seedfill: * l_int32 pixSeedfillGray() * * Distance function: * PIX *pixDistanceFunction() * * * * 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. * * 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, because the machine operations * on the PIII work on 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.) * */ #include <stdio.h> #include <stdlib.h> #include "allheaders.h" #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 MAX_ITERS = 40; /*-----------------------------------------------------------------------* * Vincent's Iterative Binary Seedfill method * *-----------------------------------------------------------------------*/ /*! * pixSeedfillBinary() * * Input: pixd (<optional> destination: this can be null, * equal to pixs, or different from pixs) * pixs (seed) * pixm (filling mask) * connectivity (4 or 8) * Return: pixd, or null on error * * Notes: * (1) This is for binary seedfill * (2) If pixs == pixd, the fill is in-place * (3) The returned pixd is the filled seed. For some * applications you want to OR it with the inverse of * the filling mask. * (4) The 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(). */ 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; PROCNAME("pixSeedfillBinary"); if (!pixs) return (PIX *)ERROR_PTR("pixs not defined", procName, pixd); if (!pixm) return (PIX *)ERROR_PTR("pixm not defined", procName, pixd); if (connectivity != 4 && connectivity != 8) return (PIX *)ERROR_PTR("connectivity not in {4,8}", procName, pixd); if (pixGetDepth(pixs) != 1 || pixGetDepth(pixm) != 1) return (PIX *)ERROR_PTR("pixs must be binary", procName, pixd); /* pixd starts out as a copy or identity with pixs */ if (pixd != pixs) { if ((pixd = pixCopy(pixd, pixs)) == NULL) return (PIX *)ERROR_PTR("pixd not made", procName, pixd); } /* pixt is used to test for completion */ if ((pixt = pixCreateTemplate(pixs)) == NULL) return (PIX *)ERROR_PTR("pixt not made", procName, pixd); hd = pixGetHeight(pixd); hm = pixGetHeight(pixm); /* included so seedfillBinaryLow() can clip */ datad = pixGetData(pixd); datam = pixGetData(pixm); wpld = pixGetWpl(pixd); wplm = pixGetWpl(pixm); pixSetPadBits(pixm, 0); for (i = 0; i < MAX_ITERS; i++) { pixCopy(pixt, pixd); seedfillBinaryLow(datad, hd, wpld, datam, hm, wplm, connectivity); pixEqual(pixd, pixt, &boolval); if (boolval == 1) { #if DEBUG_PRINT_ITERS fprintf(stderr, "Binary seed fill converged: %d iters\n", i + 1); #endif /* DEBUG_PRINT_ITERS */ break; } } pixDestroy(&pixt); return pixd; } /*! * pixHolesByFilling() * * Input: pixs, 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 * * Note: 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. */ PIX * pixHolesByFilling(PIX *pixs, l_int32 connectivity) { PIX *pixsi, *pixd; PROCNAME("pixHolesByFilling"); if (!pixs) return (PIX *)ERROR_PTR("pixs not defined", procName, NULL); if (connectivity != 4 && connectivity != 8) return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL); if ((pixd = pixCreateTemplate(pixs)) == NULL) return (PIX *)ERROR_PTR("pixd not made", procName, NULL); if ((pixsi = pixInvert(NULL, pixs)) == NULL) return (PIX *)ERROR_PTR("pixsi not made", procName, 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; } /*! * pixFillClosedBorders() * * Input: pixs * filling connectivity (4 or 8) * Return: pixd (all topologically outer closed borders are filled * as connected comonents), or null on error * * Action: * (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 * * Note: (1) if the borders are 4-c.c., use 8-c.c. filling, and v.v. * (2) closed borders within c.c. that represent holes, etc., are filled. */ PIX * pixFillClosedBorders(PIX *pixs, l_int32 connectivity) { PIX *pixsi, *pixd; PROCNAME("pixFillClosedBorders"); if (!pixs) return (PIX *)ERROR_PTR("pixs not defined", procName, NULL); if (connectivity != 4 && connectivity != 8) return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL); if ((pixd = pixCreateTemplate(pixs)) == NULL) return (PIX *)ERROR_PTR("pixd not made", procName, NULL); pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET); pixSubtract(pixd, pixd, pixs); if ((pixsi = pixInvert(NULL, pixs)) == NULL) return (PIX *)ERROR_PTR("pixsi not made", procName, NULL); pixSeedfillBinary(pixd, pixd, pixsi, connectivity); pixInvert(pixd, pixd); pixDestroy(&pixsi); return pixd; } /*! * pixRemoveBorderConnComps() * * Input: pixs * filling connectivity (4 or 8) * Return: pixd (all pixels in the src that are not touching the * border) or null on error * * Note: This is a very simple application of seedfill, where * we find all components that are touching the borders * and remove them. */ PIX * pixRemoveBorderConnComps(PIX *pixs, l_int32 connectivity) { PIX *pixd; PROCNAME("pixRemoveBorderConnComps"); if (!pixs) return (PIX *)ERROR_PTR("pixs not defined", procName, NULL); if (pixGetDepth(pixs) != 1) return (PIX *)ERROR_PTR("pixs not 1 bpp", procName, NULL); if (connectivity != 4 && connectivity != 8) return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL); if ((pixd = pixCreateTemplate(pixs)) == NULL) return (PIX *)ERROR_PTR("pixd not made", procName, NULL); /* pixd is the seed; start with 1 pixel wide black border */ pixSetOrClearBorder(pixd, 1, 1, 1, 1, PIX_SET); /* fill from the seed, using pixs as the filling mask, * to fill in all components that are touching the border */ pixSeedfillBinary(pixd, pixd, pixs, connectivity); /* get components in filling mask but not in seed */ pixXor(pixd, pixd, pixs); return pixd; } /*-----------------------------------------------------------------------* * Vincent's Iterative Grayscale Seedfill method * *-----------------------------------------------------------------------*/ /*! * pixSeedfillGray() * * Input: pixs (seed; filled in place) * pixm (filling mask) * connectivity (4 or 8) * Return: 0 if OK, 1 on error */ l_int32 pixSeedfillGray(PIX *pixs, PIX *pixm, l_int32 connectivity) { l_int32 i, h, w, wpls, wplm, boolval; l_uint32 *datas, *datam; PIX *pixt; PROCNAME("pixSeedfillGray"); if (!pixs) return ERROR_INT("pixs not defined", procName, 1); if (!pixm) return ERROR_INT("pixm not defined", procName, 1); if (connectivity != 4 && connectivity != 8) return ERROR_INT("connectivity not in {4,8}", procName, 1); if (pixGetDepth(pixs) != 8) return ERROR_INT("pixs must be 8 bpp", procName, 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", procName, 1); h = pixGetHeight(pixs); w = pixGetWidth(pixs); /* pixt is used to test for completion */ if ((pixt = pixCreateTemplate(pixs)) == NULL) return ERROR_INT("pixt not made", procName, 1); datas = pixGetData(pixs); datam = pixGetData(pixm); wpls = pixGetWpl(pixs); wplm = pixGetWpl(pixm); for (i = 0; i < MAX_ITERS; i++) { pixCopy(pixt, pixs); seedfillGrayLow(datas, w, h, wpls, datam, wplm, connectivity); pixEqual(pixs, pixt, &boolval); if (boolval == 1) { #if DEBUG_PRINT_ITERS fprintf(stderr, "Gray seed fill converged: %d iters\n", i + 1); #endif /* DEBUG_PRINT_ITERS */ break; } } pixDestroy(&pixt); return 0; } /*-----------------------------------------------------------------------* * Vincent's Distance Function method * *-----------------------------------------------------------------------*/ /*! * pixDistanceFunction() * * Input: pixs (1 bpp source) * connectivity (4 or 8) * depth (8 or 16 bits for pixd) * Return: pixd, or null on error * * This computes the distance of each pixel from the nearest * background pixel. All bg pixels therefore have a distance of 0, * and the fg pixel distances increase linearly from 1 at the * boundary. It can also be used to compute the distance of * each pixel from the nearest fg pixel, by inverting the input * image before calling this function. Then all fg pixels have * a distance 0 and the bg pixel distances increase linearly * from 1 at the boundary. * * The algorithm, described at Leptonica on the page on seed * filling and connected components, is due to Luc Vincent. * In brief, we generate an 8 or 16 bpp image, initialized to 1 for * the fg pixels of the input pix, subject to the constraint that * the boundary pixels are initialized to 0. We then do 2 sweeps, * in raster followed by anti-raster order, where the value of each * new pixel is taken to be 1 more than the minimum of the * previously-seen connected pixels (using either 4 or 8 * connectivity). */ PIX * pixDistanceFunction(PIX *pixs, l_int32 connectivity, l_int32 depth) { l_int32 w, h, wpld; l_uint32 *datad; PIX *pixd; PROCNAME("pixDistanceFunction"); if (!pixs) return (PIX *)ERROR_PTR("pixs not defined", procName, NULL); if (connectivity != 4 && connectivity != 8) return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL); if (depth != 8 && depth != 16) return (PIX *)ERROR_PTR("depth not 8 or 16 bpp", procName, NULL); if (pixGetDepth(pixs) != 1) return (PIX *)ERROR_PTR("pixs must be binary", procName, NULL); w = pixGetWidth(pixs); h = pixGetHeight(pixs); if ((pixd = pixCreate(w, h, depth)) == NULL) return (PIX *)ERROR_PTR("pixd not made", procName, NULL); datad = pixGetData(pixd); wpld = pixGetWpl(pixd); pixSetMasked(pixd, pixs, 1); distanceFunctionLow(datad, w, h, depth, wpld, connectivity); return pixd; }

Generated by Doxygen 1.6.0 Back to index