Leptonica
1.54
|
#define DEBUG_PRINT 0 |
l_int32 ccbaAddCcb | ( | CCBORDA * | ccba, |
CCBORD * | ccb | ||
) |
Input: ccba ccb (to be added by insertion) Return: 0 if OK; 1 on error
CCBORDA* ccbaCreate | ( | PIX * | pixs, |
l_int32 | n | ||
) |
Input: pixs (binary image; can be null) n (initial number of ptrs) Return: ccba, or null on error
void ccbaDestroy | ( | CCBORDA ** | pccba | ) |
Input: &ccba (<to be="" nulled>="">) Return: void
PIX* ccbaDisplayBorder | ( | CCBORDA * | ccba | ) |
Input: ccba Return: pix of border pixels, or null on error
Notes: (1) Uses global ptaa, which gives each border pixel in global coordinates, and must be computed in advance by calling ccbaGenerateGlobalLocs().
PIX* ccbaDisplayImage1 | ( | CCBORDA * | ccba | ) |
Input: ccborda Return: pix of image, or null on error
Notes: (1) Uses local ptaa, which gives each border pixel in local coordinates, so the actual pixel positions must be computed using all offsets. (2) For the holes, use coordinates relative to the c.c. (3) This is slower than Method 2. (4) This uses topological properties (Method 1) to do scan conversion to raster
This algorithm deserves some commentary.
I first tried the following:
x x x x x x x x x x x x x x x o x x x x x x x x x
if you 4-fill from the outside, the pixel 'o' will not be filled! XORing with the border leaves it OFF. Inverting then gives a single bad ON pixel that is not actually part of the hole.
So what you must do instead is 4-fill the holes from inside. You can do this from a seedfill, using a pix with the hole border as the filling mask. But you need to start with a pixel inside the hole. How is this determined? The best way is from the contour. We have a right-hand shoulder rule for inside (i.e., the filled region). Take the first 2 pixels of the hole border, and compute dx and dy (second coord minus first coord: dx = sx - fx, dy = sy - fy). There are 8 possibilities, depending on the values of dx and dy (which can each be -1, 0, and +1, but not both 0). These 8 cases can be broken into 4; see the simple algorithm below. Once you have an interior seed pixel, you fill from the seed, clipping with the hole border pix by filling into its invert.
You then successively XOR these interior filled components, in any order.
PIX* ccbaDisplayImage2 | ( | CCBORDA * | ccba | ) |
Input: ccborda Return: pix of image, or null on error
Notes: (1) Uses local chain ptaa, which gives each border pixel in local coordinates, so the actual pixel positions must be computed using all offsets. (2) Treats exterior and hole borders on equivalent footing, and does all calculations on a pix that spans the c.c. with a 1 pixel added boundary. (3) This uses topological properties (Method 2) to do scan conversion to raster (4) The algorithm is described at the top of this file (Method 2). It is preferred to Method 1 because it is between 1.2x and 2x faster than Method 1.
PIX* ccbaDisplaySPBorder | ( | CCBORDA * | ccba | ) |
Input: ccba Return: pix of border pixels, or null on error
Notes: (1) Uses spglobal pta, which gives each border pixel in global coordinates, one path per c.c., and must be computed in advance by calling ccbaGenerateSPGlobalLocs().
l_int32 ccbaExtendArray | ( | CCBORDA * | ccba | ) |
Input: ccba Return: 0 if OK; 1 on error
l_int32 ccbaGenerateGlobalLocs | ( | CCBORDA * | ccba | ) |
Input: ccba (with local chain ptaa of borders computed) Return: 0 if OK, 1 on error
Action: this uses the pixel locs in the local ptaa, which are all relative to each c.c., to find the global pixel locations, and stores them in the global ptaa.
l_int32 ccbaGenerateSinglePath | ( | CCBORDA * | ccba | ) |
Input: ccba Return: 0 if OK, 1 on error
Notes: (1) Generates a single border in local pixel coordinates. For each c.c., if there is just an outer border, copy it. If there are also hole borders, for each hole border, determine the smallest horizontal or vertical distance from the border to the outside of the c.c., and find a path through the c.c. for this cut. We do this in a way that guarantees a pixel from the hole border is the starting point of the path, and we must verify that the path intersects the outer border (if it intersects it, then it ends on it). One can imagine pathological cases, but they may not occur in images of text characters and un-textured line graphics. (2) Once it is verified that the path through the c.c. intersects both the hole and outer borders, we generate the full single path for all borders in the c.c. Starting at the start point on the outer border, when we hit a line on a cut, we take the cut, do the hold border, and return on the cut to the outer border. We compose a pta of the outer border pts that are on cut paths, and for every point on the outer border (as we go around), we check against this pta. When we find a matching point in the pta, we do its cut path and hole border. The single path is saved in the ccb.
l_int32 ccbaGenerateSPGlobalLocs | ( | CCBORDA * | ccba, |
l_int32 | ptsflag | ||
) |
Input: ccba ptsflag (CCB_SAVE_ALL_PTS or CCB_SAVE_TURNING_PTS) Return: 0 if OK, 1 on error
Notes: (1) This calculates the splocal rep if not yet made. (2) It uses the local pixel values in splocal, the single path pta, which are all relative to each c.c., to find the corresponding global pixel locations, and stores them in the spglobal pta. (3) This lists only the turning points: it both makes a valid svg file and is typically about half the size when all border points are listed.
l_int32 ccbaGenerateStepChains | ( | CCBORDA * | ccba | ) |
Input: ccba (with local chain ptaa of borders computed) Return: 0 if OK, 1 on error
Notes: (1) This uses the pixel locs in the local ptaa, which are all relative to each c.c., to find the step directions for successive pixels in the chain, and stores them in the step numaa. (2) To get the step direction, use 1 2 3 0 P 4 7 6 5 where P is the previous pixel at (px, py). The step direction is the number (from 0 through 7) for each relative location of the current pixel at (cx, cy). It is easily found by indexing into a 2-d 3x3 array (dirtab).
CCBORD* ccbaGetCcb | ( | CCBORDA * | ccba, |
l_int32 | index | ||
) |
Input: ccba Return: ccb, or null on error
l_int32 ccbaGetCount | ( | CCBORDA * | ccba | ) |
Input: ccba Return: count, with 0 on error
Input: filename Return: ccba, or null on error
CCBORDA* ccbaReadStream | ( | FILE * | fp | ) |
Input: stream Return: ccba, or null on error
Format: ccba: %7d cc
(num. c.c.) (ascii) (17B) pix width (4B) pix height (4B) [for i = 1, ncc] ulx (4B) uly (4B) w (4B) -- not req'd for reconstruction h (4B) -- not req'd for reconstruction number of borders (4B) [for j = 1, nb] startx (4B) starty (4B) [for k = 1, nb] 2 steps (1B) end in z8 or 88 (1B)
l_int32 ccbaStepChainsToPixCoords | ( | CCBORDA * | ccba, |
l_int32 | coordtype | ||
) |
Input: ccba (with step chains numaa of borders) coordtype (CCB_GLOBAL_COORDS or CCB_LOCAL_COORDS) Return: 0 if OK, 1 on error
Notes: (1) This uses the step chain data in each ccb to determine the pixel locations, either global or local, and stores them in the appropriate ptaa, either global or local. For the latter, the pixel locations are relative to the c.c.
Input: filename ccba Return: 0 if OK, 1 on error
l_int32 ccbaWriteStream | ( | FILE * | fp, |
CCBORDA * | ccba | ||
) |
Input: stream ccba Return: 0 if OK; 1 on error
Format: ccba: %7d cc
(num. c.c.) (ascii) (18B) pix width (4B) pix height (4B) [for i = 1, ncc] ulx (4B) uly (4B) w (4B) -- not req'd for reconstruction h (4B) -- not req'd for reconstruction number of borders (4B) [for j = 1, nb] startx (4B) starty (4B) [for k = 1, nb] 2 steps (1B) end in z8 or 88 (1B)
l_int32 ccbaWriteSVG | ( | const char * | filename, |
CCBORDA * | ccba | ||
) |
Input: filename ccba Return: 0 if OK, 1 on error
char* ccbaWriteSVGString | ( | const char * | filename, |
CCBORDA * | ccba | ||
) |
Input: filename ccba Return: string in svg-formatted, that can be written to file, or null on error.
Input: pixs (<optional>) Return: ccb or null on error
void ccbDestroy | ( | CCBORD ** | pccb | ) |
Input: &ccb (<to be="" nulled>="">) Return: void
l_int32 findNextBorderPixel | ( | l_int32 | w, |
l_int32 | h, | ||
l_uint32 * | data, | ||
l_int32 | wpl, | ||
l_int32 | px, | ||
l_int32 | py, | ||
l_int32 * | pqpos, | ||
l_int32 * | pnpx, | ||
l_int32 * | pnpy | ||
) |
Input: w, h, data, wpl (px, py), (current P) &qpos (input current Q; <return> new Q) (&npx, &npy) (<return> new P) Return: 0 if next pixel found; 1 otherwise
Notes: (1) qpos increases clockwise from 0 to 7, with 0 at location with Q to left of P: Q P (2) this is a low-level function that does not check input parameters. All calling functions should check them.
Input: pix (of c.c.) pta (of outer border) boxinner (b.b. of hole path) &dir (direction (0-3), returned; only needed for debug) &len (length of path, returned) Return: pta of pts on cut path from the hole border to the outer border, including end points on both borders; or null on error
Notes: (1) If we don't find a path, we return a pta with no pts in it and len = 0. (2) The goal is to get a reasonably short path between the inner and outer borders, that goes entirely within the fg of the pix. This function is cheap-and-dirty, may fail for some holes in complex topologies such as those you might find in a moderately dark scanned halftone. If it fails to find a path to any particular hole, it gives a warning, and because that hole path is not included, the hole will not be rendered.
void locateOutsideSeedPixel | ( | l_int32 | fpx, |
l_int32 | fpy, | ||
l_int32 | spx, | ||
l_int32 | spy, | ||
l_int32 * | pxs, | ||
l_int32 * | pys | ||
) |
Input: fpx, fpy (location of first pixel) spx, spy (location of second pixel) &xs, &xy (seed pixel to be returned)
Notes: (1) the first and second pixels must be 8-adjacent, so |dx| <= 1 and |dy| <= 1 and both dx and dy cannot be 0. There are 8 possible cases. (2) the seed pixel is OUTSIDE the foreground of the c.c. (3) these rules are for the situation where the INSIDE of the c.c. is on the right as you follow the border: cw for an exterior border and ccw for a hole border.
CCBORDA* pixGetAllCCBorders | ( | PIX * | pixs | ) |
Input: pixs (1 bpp) Return: ccborda, or null on error
CCBORD* pixGetCCBorders | ( | PIX * | pixs, |
BOX * | box | ||
) |
Input: pixs (1 bpp, one 8-connected component) box (xul, yul, width, height) in global coords Return: ccbord, or null on error
Notes: (1) We are finding the exterior and interior borders of an 8-connected component. This should be used on a pix that has exactly one 8-connected component. (2) Typically, pixs is a c.c. in some larger pix. The input box gives its location in global coordinates. This box is saved, as well as the boxes for the borders of any holes within the c.c., but the latter are given in relative coords within the c.c. (3) The calculations for the exterior border are done on a pix with a 1-pixel added border, but the saved pixel coordinates are the correct (relative) ones for the input pix (without a 1-pixel border) (4) For the definition of the three tables -- xpostab[], ypostab[] and qpostab[] -- see above where they are defined.
Input: ccb (the exterior border is already made) pixs (for the connected component at hand) box (for the specific hole border, in relative coordinates to the c.c.) xs, ys (first pixel on hole border, relative to c.c.) Return: 0 if OK, 1 on error
Notes: (1) we trace out hole border on pixs without addition of single pixel added border to pixs (2) therefore all coordinates are relative within the c.c. (pixs) (3) same position tables and stopping condition as for exterior borders
l_int32 pixGetOuterBorder | ( | CCBORD * | ccb, |
PIX * | pixs, | ||
BOX * | box | ||
) |
Input: ccb (unfilled) pixs (for the component at hand) box (for the component, in global coords) Return: 0 if OK, 1 on error
Notes: (1) the border is saved in relative coordinates within the c.c. (pixs). Because the calculation is done in pixb with added 1 pixel border, we must subtract 1 from each pixel value before storing it. (2) the stopping condition is that after the first pixel is returned to, the next pixel is the second pixel. Having these 2 pixels recur in sequence proves the path is closed, and we do not store the second pixel again.
PTA* pixGetOuterBorderPta | ( | PIX * | pixs, |
BOX * | box | ||
) |
Input: pixs (1 bpp, one 8-connected component) box (<optional> of pixs, in global coordinates) Return: pta (of outer border, in global coords), or null on error
Notes: (1) We are finding the exterior border of a single 8-connected component. (2) If box is NULL, the outline returned is in the local coords of the input pix. Otherwise, box is assumed to give the location of the pix in global coordinates, and the returned pta will be in those global coordinates.
PTAA* pixGetOuterBordersPtaa | ( | PIX * | pixs | ) |
Input: pixs (1 bpp) Return: ptaa (of outer borders, in global coords), or null on error
const l_int32 INITIAL_PTR_ARRAYSIZE = 20 [static] |
const l_int32 NMAX_HOLES = 150 [static] |