| /*====================================================================* |
| - 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. |
| *====================================================================*/ |
| |
| /* |
| * runlength.c |
| * |
| * Label pixels by membership in runs |
| * PIX *pixRunlengthTransform() |
| * |
| * Find runs along horizontal and vertical lines |
| * l_int32 pixFindHorizontalRuns() |
| * l_int32 pixFindVerticalRuns() |
| * |
| * Compute runlength-to-membership transform on a line |
| * l_int32 runlengthMembershipOnLine() |
| * |
| * Make byte position LUT |
| * l_int32 makeMSBitLocTab() |
| */ |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| #include "allheaders.h" |
| |
| |
| /*-----------------------------------------------------------------------* |
| * Label pixels by membership in runs * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * pixRunlengthTransform() |
| * |
| * Input: pixs (1 bpp) |
| * color (0 for white runs, 1 for black runs) |
| * direction (L_HORIZONTAL_RUNS, L_VERTICAL_RUNS) |
| * depth (8 or 16 bpp) |
| * Return: 0 if OK; 1 on error |
| * |
| * Notes: |
| * (1) The dest Pix is 8 or 16 bpp, with the pixel values |
| * equal to the runlength in which it is a member. |
| * The length is clipped to the max pixel value if necessary. |
| * (2) The color determines if we're labelling white or black runs. |
| * (3) A pixel that is not a member of the chosen color gets |
| * value 0; it belongs to a run of length 0 of the |
| * chosen color. |
| * (4) To convert for maximum dynamic range, either linear or |
| * log, use pixMaxDynamicRange(). |
| */ |
| PIX * |
| pixRunlengthTransform(PIX *pixs, |
| l_int32 color, |
| l_int32 direction, |
| l_int32 depth) |
| { |
| l_int32 i, j, w, h, wpld, bufsize, maxsize, n; |
| l_int32 *start, *end, *buffer; |
| l_uint32 *datad, *lined; |
| PIX *pixt, *pixd; |
| |
| PROCNAME("pixRunlengthTransform"); |
| |
| 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 (depth != 8 && depth != 16) |
| return (PIX *)ERROR_PTR("depth must be 8 or 16 bpp", procName, NULL); |
| |
| w = pixGetWidth(pixs); |
| h = pixGetHeight(pixs); |
| if (direction == L_HORIZONTAL_RUNS) |
| maxsize = 1 + w / 2; |
| else if (direction == L_VERTICAL_RUNS) |
| maxsize = 1 + h / 2; |
| else |
| return (PIX *)ERROR_PTR("invalid direction", procName, NULL); |
| bufsize = L_MAX(w, h); |
| |
| if ((pixd = pixCreate(w, h, depth)) == NULL) |
| return (PIX *)ERROR_PTR("pixd not made", procName, NULL); |
| datad = pixGetData(pixd); |
| wpld = pixGetWpl(pixd); |
| |
| if ((start = (l_int32 *)CALLOC(maxsize, sizeof(l_int32))) == NULL) |
| return (PIX *)ERROR_PTR("start not made", procName, NULL); |
| if ((end = (l_int32 *)CALLOC(maxsize, sizeof(l_int32))) == NULL) |
| return (PIX *)ERROR_PTR("end not made", procName, NULL); |
| if ((buffer = (l_int32 *)CALLOC(bufsize, sizeof(l_int32))) == NULL) |
| return (PIX *)ERROR_PTR("buffer not made", procName, NULL); |
| |
| /* Use fg runs for evaluation */ |
| if (color == 0) |
| pixt = pixInvert(NULL, pixs); |
| else |
| pixt = pixClone(pixs); |
| |
| if (direction == L_HORIZONTAL_RUNS) { |
| for (i = 0; i < h; i++) { |
| pixFindHorizontalRuns(pixt, i, start, end, &n); |
| runlengthMembershipOnLine(buffer, w, depth, start, end, n); |
| lined = datad + i * wpld; |
| if (depth == 8) { |
| for (j = 0; j < w; j++) |
| SET_DATA_BYTE(lined, j, buffer[j]); |
| } else { /* depth == 16 */ |
| for (j = 0; j < w; j++) |
| SET_DATA_TWO_BYTES(lined, j, buffer[j]); |
| } |
| } |
| } else { /* L_VERTICAL_RUNS */ |
| for (j = 0; j < w; j++) { |
| pixFindVerticalRuns(pixt, j, start, end, &n); |
| runlengthMembershipOnLine(buffer, h, depth, start, end, n); |
| if (depth == 8) { |
| for (i = 0; i < h; i++) { |
| lined = datad + i * wpld; |
| SET_DATA_BYTE(lined, j, buffer[i]); |
| } |
| } else { /* depth == 16 */ |
| for (i = 0; i < h; i++) { |
| lined = datad + i * wpld; |
| SET_DATA_TWO_BYTES(lined, j, buffer[i]); |
| } |
| } |
| } |
| } |
| |
| pixDestroy(&pixt); |
| FREE(start); |
| FREE(end); |
| FREE(buffer); |
| return pixd; |
| } |
| |
| |
| /*-----------------------------------------------------------------------* |
| * Find runs along horizontal and vertical lines * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * pixFindHorizontalRuns() |
| * |
| * Input: pix (1 bpp) |
| * y (line to traverse) |
| * xstart (returns array of start positions for fg runs) |
| * xend (returns array of end positions for fg runs) |
| * &n (<return> the number of runs found) |
| * Return: 0 if OK; 1 on error |
| * |
| * Notes: |
| * (1) This finds foreground horizontal runs on a single scanline. |
| * (2) To find background runs, use pixInvert() before applying |
| * this function. |
| * (3) The xstart and xend arrays are input. They should be |
| * of size w/2 + 1 to insure that they can hold |
| * the maximum number of runs in the raster line. |
| */ |
| l_int32 |
| pixFindHorizontalRuns(PIX *pix, |
| l_int32 y, |
| l_int32 *xstart, |
| l_int32 *xend, |
| l_int32 *pn) |
| { |
| l_int32 inrun; /* boolean */ |
| l_int32 index, w, h, d, j, wpl, val; |
| l_uint32 *line; |
| |
| PROCNAME("pixFindHorizontalRuns"); |
| |
| if (!pn) |
| return ERROR_INT("&n not defined", procName, 1); |
| *pn = 0; |
| if (!pix) |
| return ERROR_INT("pix not defined", procName, 1); |
| pixGetDimensions(pix, &w, &h, &d); |
| if (d != 1) |
| return ERROR_INT("pix not 1 bpp", procName, 1); |
| if (y < 0 || y >= h) |
| return ERROR_INT("y not in [0 ... h - 1]", procName, 1); |
| if (!xstart) |
| return ERROR_INT("xstart not defined", procName, 1); |
| if (!xend) |
| return ERROR_INT("xend not defined", procName, 1); |
| |
| wpl = pixGetWpl(pix); |
| line = pixGetData(pix) + y * wpl; |
| |
| inrun = FALSE; |
| index = 0; |
| for (j = 0; j < w; j++) { |
| val = GET_DATA_BIT(line, j); |
| if (!inrun) { |
| if (val) { |
| xstart[index] = j; |
| inrun = TRUE; |
| } |
| } |
| else { |
| if (!val) { |
| xend[index++] = j - 1; |
| inrun = FALSE; |
| } |
| } |
| } |
| |
| /* Finish last run if necessary */ |
| if (inrun) |
| xend[index++] = w - 1; |
| |
| *pn = index; |
| return 0; |
| } |
| |
| |
| /*! |
| * pixFindVerticalRuns() |
| * |
| * Input: pix (1 bpp) |
| * x (line to traverse) |
| * ystart (returns array of start positions for fg runs) |
| * yend (returns array of end positions for fg runs) |
| * &n (<return> the number of runs found) |
| * Return: 0 if OK; 1 on error |
| * |
| * Notes: |
| * (1) This finds foreground vertical runs on a single scanline. |
| * (2) To find background runs, use pixInvert() before applying |
| * this function. |
| * (3) The ystart and yend arrays are input. They should be |
| * of size h/2 + 1 to insure that they can hold |
| * the maximum number of runs in the raster line. |
| */ |
| l_int32 |
| pixFindVerticalRuns(PIX *pix, |
| l_int32 x, |
| l_int32 *ystart, |
| l_int32 *yend, |
| l_int32 *pn) |
| { |
| l_int32 inrun; /* boolean */ |
| l_int32 index, w, h, d, i, wpl, val; |
| l_uint32 *data, *line; |
| |
| PROCNAME("pixFindVerticalRuns"); |
| |
| if (!pn) |
| return ERROR_INT("&n not defined", procName, 1); |
| *pn = 0; |
| if (!pix) |
| return ERROR_INT("pix not defined", procName, 1); |
| pixGetDimensions(pix, &w, &h, &d); |
| if (d != 1) |
| return ERROR_INT("pix not 1 bpp", procName, 1); |
| if (x < 0 || x >= w) |
| return ERROR_INT("x not in [0 ... w - 1]", procName, 1); |
| if (!ystart) |
| return ERROR_INT("ystart not defined", procName, 1); |
| if (!yend) |
| return ERROR_INT("yend not defined", procName, 1); |
| |
| wpl = pixGetWpl(pix); |
| data = pixGetData(pix); |
| |
| inrun = FALSE; |
| index = 0; |
| for (i = 0; i < h; i++) { |
| line = data + i * wpl; |
| val = GET_DATA_BIT(line, x); |
| if (!inrun) { |
| if (val) { |
| ystart[index] = i; |
| inrun = TRUE; |
| } |
| } |
| else { |
| if (!val) { |
| yend[index++] = i - 1; |
| inrun = FALSE; |
| } |
| } |
| } |
| |
| /* Finish last run if necessary */ |
| if (inrun) |
| yend[index++] = h - 1; |
| |
| *pn = index; |
| return 0; |
| } |
| |
| |
| /*-----------------------------------------------------------------------* |
| * Compute runlength-to-membership transform on a line * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * runlengthMembershipOnLine() |
| * |
| * Input: buffer (into which full line of data is placed) |
| * size (full size of line; w or h) |
| * depth (8 or 16 bpp) |
| * start (array of start positions for fg runs) |
| * end (array of end positions for fg runs) |
| * n (the number of runs) |
| * Return: 0 if OK; 1 on error |
| * |
| * Notes: |
| * (1) Converts a set of runlengths into a buffer of |
| * runlength membership values. |
| * (2) Initialization of the array gives pixels that are |
| * not within a run the value 0. |
| */ |
| l_int32 |
| runlengthMembershipOnLine(l_int32 *buffer, |
| l_int32 size, |
| l_int32 depth, |
| l_int32 *start, |
| l_int32 *end, |
| l_int32 n) |
| { |
| l_int32 i, j, first, last, diff, max; |
| |
| PROCNAME("runlengthMembershipOnLine"); |
| |
| if (!buffer) |
| return ERROR_INT("buffer not defined", procName, 1); |
| if (!start) |
| return ERROR_INT("start not defined", procName, 1); |
| if (!end) |
| return ERROR_INT("end not defined", procName, 1); |
| |
| if (depth == 8) |
| max = 0xff; |
| else /* depth == 16 */ |
| max = 0xffff; |
| |
| memset(buffer, 0, 4 * size); |
| for (i = 0; i < n; i++) { |
| first = start[i]; |
| last = end[i]; |
| diff = last - first + 1; |
| diff = L_MIN(diff, max); |
| for (j = first; j <= last; j++) |
| buffer[j] = diff; |
| } |
| |
| return 0; |
| } |
| |
| |
| |
| /*-----------------------------------------------------------------------* |
| * Make byte position LUT * |
| *-----------------------------------------------------------------------*/ |
| /*! |
| * makeMSBitLocTab() |
| * |
| * Input: bitval (either 0 or 1) |
| * Return: table (giving, for an input byte, the MS bit location, |
| * starting at 0 with the MSBit in the byte), |
| * or null on error. |
| * |
| * Notes: |
| * (1) If bitval == 1, it finds the leftmost ON pixel in a byte; |
| * otherwise if bitval == 0, it finds the leftmost OFF pixel. |
| * (2) If there are no pixels of the indicated color in the byte, |
| * this returns 8. |
| */ |
| l_int32 * |
| makeMSBitLocTab(l_int32 bitval) |
| { |
| l_int32 i, j; |
| l_int32 *tab; |
| l_uint8 byte, mask; |
| |
| PROCNAME("makeMSBitLocTab"); |
| |
| if ((tab = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL) |
| return (l_int32 *)ERROR_PTR("tab not made", procName, NULL); |
| |
| for (i = 0; i < 256; i++) { |
| byte = (l_uint8)i; |
| if (bitval == 0) |
| byte = ~byte; |
| tab[i] = 8; |
| mask = 0x80; |
| for (j = 0; j < 8; j++) { |
| if (byte & mask) { |
| tab[i] = j; |
| break; |
| } |
| mask >>= 1; |
| } |
| } |
| |
| return tab; |
| } |
| |
| |
