seedfilllow.c

Go to the documentation of this file.

/*====================================================================*
 -  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.
 *====================================================================*/

/*
 *  seedfilllow.c
 *
 *      Seedfill:
 *      Gray seedfill (source: Luc Vincent:fast-hybrid-grayscale-reconstruction)
 *               void   seedfillBinaryLow()
 *               void   seedfillGrayLow()
 *               void   seedfillGrayInvLow()
 *               void   seedfillGrayLowSimple()
 *               void   seedfillGrayInvLowSimple()
 *
 *      Distance function:
 *               void   distanceFunctionLow()
 *
 *      Seed spread:
 *               void   seedspreadLow()
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "allheaders.h"

struct L_Pixel
{
    l_int32    x;
    l_int32    y;
};
typedef struct L_Pixel  L_PIXEL;


/*-----------------------------------------------------------------------*
 *                 Vincent's Iterative Binary Seedfill                   *
 *-----------------------------------------------------------------------*/
/*!
 *  seedfillBinaryLow()
 *
 *  Notes:
 *      (1) This is an in-place fill, where the seed image is
 *          filled, clipping to the filling mask, in one full
 *          cycle of UL -> LR and LR -> UL raster scans.
 *      (2) Assume the mask is a filling mask, not a blocking mask.
 *      (3) Assume that the RHS pad bits of the mask
 *          are properly set to 0.
 *      (4) Clip to the smallest dimensions to avoid invalid reads.
 */
void
seedfillBinaryLow(l_uint32  *datas,
                  l_int32    hs,
                  l_int32    wpls,
                  l_uint32  *datam,
                  l_int32    hm,
                  l_int32    wplm,
                  l_int32    connectivity)
{
l_int32    i, j, h, wpl;
l_uint32   word, mask;
l_uint32   wordabove, wordleft, wordbelow, wordright;
l_uint32   wordprev;  /* test against this in previous iteration */
l_uint32  *lines, *linem;

    PROCNAME("seedfillBinaryLow");

    h = L_MIN(hs, hm);
    wpl = L_MIN(wpls, wplm);

    switch (connectivity)
    {
    case 4:
            /* UL --> LR scan */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < wpl; j++) {
                word = *(lines + j);
                mask = *(linem + j);

                    /* OR from word above and from word to left; mask */
                if (i > 0) {
                    wordabove = *(lines - wpls + j);
                    word |= wordabove;
                }
                if (j > 0) {
                    wordleft = *(lines + j - 1);
                    word |= wordleft << 31;
                }
                word &= mask;

                    /* No need to fill horizontally? */
                if (!word || !(~word)) {
                    *(lines + j) = word;
                    continue;
                }

                while (1) {
                    wordprev = word;
                    word = (word | (word >> 1) | (word << 1)) & mask;
                    if ((word ^ wordprev) == 0) {
                        *(lines + j) = word;
                        break;
                    }
                }
            }
        }

            /* LR --> UL scan */
        for (i = h - 1; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = wpl - 1; j >= 0; j--) {
                word = *(lines + j);
                mask = *(linem + j);

                    /* OR from word below and from word to right; mask */
                if (i < h - 1) {
                    wordbelow = *(lines + wpls + j);
                    word |= wordbelow;
                }
                if (j < wpl - 1) {
                    wordright = *(lines + j + 1);
                    word |= wordright >> 31;
                }
                word &= mask;

                    /* No need to fill horizontally? */
                if (!word || !(~word)) {
                    *(lines + j) = word;
                    continue;
                }

                while (1) {
                    wordprev = word;
                    word = (word | (word >> 1) | (word << 1)) & mask;
                    if ((word ^ wordprev) == 0) {
                        *(lines + j) = word;
                        break;
                    }
                }
            }
        }
        break;

    case 8:
            /* UL --> LR scan */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < wpl; j++) {
                word = *(lines + j);
                mask = *(linem + j);

                    /* OR from words above and from word to left; mask */
                if (i > 0) {
                    wordabove = *(lines - wpls + j);
                    word |= (wordabove | (wordabove << 1) | (wordabove >> 1));
                    if (j > 0)
                        word |= (*(lines - wpls + j - 1)) << 31;
                    if (j < wpl - 1)
                        word |= (*(lines - wpls + j + 1)) >> 31;
                }
                if (j > 0) {
                    wordleft = *(lines + j - 1);
                    word |= wordleft << 31;
                }
                word &= mask;

                    /* No need to fill horizontally? */
                if (!word || !(~word)) {
                    *(lines + j) = word;
                    continue;
                }

                while (1) {
                    wordprev = word;
                    word = (word | (word >> 1) | (word << 1)) & mask;
                    if ((word ^ wordprev) == 0) {
                        *(lines + j) = word;
                        break;
                    }
                }
            }
        }

            /* LR --> UL scan */
        for (i = h - 1; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = wpl - 1; j >= 0; j--) {
                word = *(lines + j);
                mask = *(linem + j);

                    /* OR from words below and from word to right; mask */
                if (i < h - 1) {
                    wordbelow = *(lines + wpls + j);
                    word |= (wordbelow | (wordbelow << 1) | (wordbelow >> 1));
                    if (j > 0)
                        word |= (*(lines + wpls + j - 1)) << 31;
                    if (j < wpl - 1)
                        word |= (*(lines + wpls + j + 1)) >> 31;
                }
                if (j < wpl - 1) {
                    wordright = *(lines + j + 1);
                    word |= wordright >> 31;
                }
                word &= mask;

                    /* No need to fill horizontally? */
                if (!word || !(~word)) {
                    *(lines + j) = word;
                    continue;
                }

                while (1) {
                    wordprev = word;
                    word = (word | (word >> 1) | (word << 1)) & mask;
                    if ((word ^ wordprev) == 0) {
                        *(lines + j) = word;
                        break;
                    }
                }
            }
        }
        break;

    default:
        L_ERROR("connectivity must be 4 or 8", procName);
    }

    return;
}



/*-----------------------------------------------------------------------*
 *                 Vincent's Hybrid Grayscale Seedfill                *
 *-----------------------------------------------------------------------*/
/*!
 *  seedfillGrayLow()
 *
 *  Notes:
 *      (1) The pixels are numbered as follows:
 *              1  2  3
 *              4  x  5
 *              6  7  8
 *          This low-level filling operation consists of two scans,
 *          raster and anti-raster, covering the entire seed image.
 *          This is followed by a breadth-first propagation operation to
 *          complete the fill.
 *          During the anti-raster scan, every pixel p whose current value
 *          could still be propagated after the anti-raster scan is put into
 *          the FIFO queue.
 *          The propagation step is a breadth-first fill to completion.
 *          Unlike the simple grayscale seedfill pixSeedfillGraySimple(),
 *          where at least two full raster/anti-raster iterations are required
 *          for completion and verification, the hybrid method uses only a
 *          single raster/anti-raster set of scans.
 *      (2) The filling action can be visualized from the following example.
 *          Suppose the mask, which clips the fill, is a sombrero-shaped
 *          surface, where the highest point is 200 and the low pixels
 *          around the rim are 30.  Beyond the rim, the mask goes up a bit.
 *          Suppose the seed, which is filled, consists of a single point
 *          of height 150, located below the max of the mask, with
 *          the rest 0.  Then in the raster scan, nothing happens until
 *          the high seed point is encountered, and then this value is
 *          propagated right and down, until it hits the side of the
 *          sombrero.   The seed can never exceed the mask, so it fills
 *          to the rim, going lower along the mask surface.  When it
 *          passes the rim, the seed continues to fill at the rim
 *          height to the edge of the seed image.  Then on the
 *          anti-raster scan, the seed fills flat inside the
 *          sombrero to the upper and left, and then out from the
 *          rim as before.  The final result has a seed that is
 *          flat outside the rim, and inside it fills the sombrero
 *          but only up to 150.  If the rim height varies, the
 *          filled seed outside the rim will be at the highest
 *          point on the rim, which is a saddle point on the rim.
 *      (3) Reference paper :
 *            L. Vincent, Morphological grayscale reconstruction in image
 *            analysis: applications and efficient algorithms, IEEE Transactions
 *            on  Image Processing, vol. 2, no. 2, pp. 176-201, 1993.
 */
void
seedfillGrayLow(l_uint32  *datas,
                l_int32    w,
                l_int32    h,
                l_int32    wpls,
                l_uint32  *datam,
                l_int32    wplm,
                l_int32    connectivity)
{
l_uint8    val1, val2, val3, val4, val5, val6, val7, val8;
l_uint8    val, maxval, maskval, boolval;
l_int32    i, j, imax, jmax, queue_size;
l_uint32  *lines, *linem;
L_PIXEL *pixel;
L_QUEUE  *lq_pixel;

    PROCNAME("seedfillGrayLow");

    imax = h - 1;
    jmax = w - 1;

        /* In the worst case, most of the pixels could be pushed
         * onto the FIFO queue during anti-raster scan.  However this
         * will rarely happen, and we initialize the queue ptr size to
         * the image perimeter. */
    lq_pixel = lqueueCreate(2 * (w + h));

    switch (connectivity)
    {
    case 4:
            /* UL --> LR scan  (Raster Order)
             * If I : mask image
             *    J : marker image
             * Let p be the currect pixel;
             * J(p) <- (max{J(p) union J(p) neighbors in raster order})
             *          intersection I(p) */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < w; j++) {
                if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
                    maxval = 0;
                    if (i > 0)
                        maxval = GET_DATA_BYTE(lines - wpls, j);
                    if (j > 0) {
                        val4 = GET_DATA_BYTE(lines, j - 1);
                        maxval = L_MAX(maxval, val4);
                    }
                    val = GET_DATA_BYTE(lines, j);
                    maxval = L_MAX(maxval, val);
                    val = L_MIN(maxval, maskval);
                    SET_DATA_BYTE(lines, j, val);
                }
            }
        }

            /* LR --> UL scan (anti-raster order)
             * Let p be the currect pixel;
             * J(p) <- (max{J(p) union J(p) neighbors in anti-raster order})
             *          intersection I(p) */
        for (i = imax; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = jmax; j >= 0; j--) {
                boolval = FALSE;
                if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
                    maxval = 0;
                    if (i < imax)
                        maxval = GET_DATA_BYTE(lines + wpls, j);
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        maxval = L_MAX(maxval, val5);
                    }
                    val = GET_DATA_BYTE(lines, j);
                    maxval = L_MAX(maxval, val);
                    val = L_MIN(maxval, maskval);
                    SET_DATA_BYTE(lines, j, val);

                        /*
                         * If there exists a point (q) which belongs to J(p)
                         * neighbors in anti-raster order such that J(q) < J(p)
                         * and J(q) < I(q) then
                         * fifo_add(p) */
                    if (i < imax) {
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        if ((val7 < val) &&
                            (val7 < GET_DATA_BYTE(linem + wplm, j))) {
                            boolval = TRUE;
                        }
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        if (!boolval && (val5 < val) &&
                            (val5 < GET_DATA_BYTE(linem, j + 1))) {
                            boolval = TRUE;
                        }
                    }
                    if (boolval) {
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
            }
        }

            /* Propagation step:
             *        while fifo_empty = false
             *          p <- fifo_first()
             *          for every pixel (q) belong to neighbors of (p)
             *            if J(q) < J(p) and I(q) != J(q)
             *              J(q) <- min(J(p), I(q));
             *              fifo_add(q);
             *            end
             *          end
             *        end */
        queue_size = lqueueGetCount(lq_pixel);
        while (queue_size) {
            pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
            i = pixel->x;
            j = pixel->y;
            FREE(pixel);
            lines = datas + i * wpls;
            linem = datam + i * wplm;

            if ((val = GET_DATA_BYTE(lines, j)) > 0) {
                if (i > 0) {
                    val2 = GET_DATA_BYTE(lines - wpls, j);
                    maskval = GET_DATA_BYTE(linem - wplm, j);
                    if (val > val2 && val2 != maskval) {
                        SET_DATA_BYTE(lines - wpls, j, L_MIN(val, maskval));
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i - 1;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }

                }
                if (j > 0) {
                    val4 = GET_DATA_BYTE(lines, j - 1);
                    maskval = GET_DATA_BYTE(linem, j - 1);
                    if (val > val4 && val4 != maskval) {
                        SET_DATA_BYTE(lines, j - 1, L_MIN(val, maskval));
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j - 1;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
                if (i < imax) {
                    val7 = GET_DATA_BYTE(lines + wpls, j);
                    maskval = GET_DATA_BYTE(linem + wplm, j);
                    if (val > val7 && val7 != maskval) {
                        SET_DATA_BYTE(lines + wpls, j, L_MIN(val, maskval));
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i + 1;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
                if (j < jmax) {
                    val5 = GET_DATA_BYTE(lines, j + 1);
                    maskval = GET_DATA_BYTE(linem, j + 1);
                    if (val > val5 && val5 != maskval) {
                        SET_DATA_BYTE(lines, j + 1, L_MIN(val, maskval));
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j + 1;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
            }

            queue_size = lqueueGetCount(lq_pixel);
        }

        break;

    case 8:
            /* UL --> LR scan  (Raster Order)
             * If I : mask image
             *    J : marker image
             * Let p be the currect pixel;
             * J(p) <- (max{J(p) union J(p) neighbors in raster order})
             *          intersection I(p) */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < w; j++) {
                if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
                    maxval = 0;
                    if (i > 0) {
                        if (j > 0)
                            maxval = GET_DATA_BYTE(lines - wpls, j - 1);
                        if (j < jmax) {
                            val3 = GET_DATA_BYTE(lines - wpls, j + 1);
                            maxval = L_MAX(maxval, val3);
                        }
                        val2 = GET_DATA_BYTE(lines - wpls, j);
                        maxval = L_MAX(maxval, val2);
                    }
                    if (j > 0) {
                        val4 = GET_DATA_BYTE(lines, j - 1);
                        maxval = L_MAX(maxval, val4);
                    }
                    val = GET_DATA_BYTE(lines, j);
                    maxval = L_MAX(maxval, val);
                    val = L_MIN(maxval, maskval);
                    SET_DATA_BYTE(lines, j, val);
                }
            }
        }

            /* LR --> UL scan (anti-raster order)
             * Let p be the currect pixel;
             * J(p) <- (max{J(p) union J(p) neighbors in anti-raster order})
             *          intersection I(p) */
        for (i = imax; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = jmax; j >= 0; j--) {
                boolval = FALSE;
                if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
                    maxval = 0;
                    if (i < imax) {
                        if (j > 0) {
                            maxval = GET_DATA_BYTE(lines + wpls, j - 1);
                        }
                        if (j < jmax) {
                            val8 = GET_DATA_BYTE(lines + wpls, j + 1);
                            maxval = L_MAX(maxval, val8);
                        }
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        maxval = L_MAX(maxval, val7);
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        maxval = L_MAX(maxval, val5);
                    }
                    val = GET_DATA_BYTE(lines, j);
                    maxval = L_MAX(maxval, val);
                    val = L_MIN(maxval, maskval);
                    SET_DATA_BYTE(lines, j, val);

                        /* If there exists a point (q) which belongs to J(p)
                         * neighbors in anti-raster order such that J(q) < J(p)
                         * and J(q) < I(q) then
                         * fifo_add(p) */
                    if (i < imax) {
                        if (j > 0) {
                            val6 = GET_DATA_BYTE(lines + wpls, j - 1);
                            if ((val6 < val) &&
                                (val6 < GET_DATA_BYTE(linem + wplm, j - 1))) {
                                boolval = TRUE;
                            }
                        }
                        if (j < jmax) {
                            val8 = GET_DATA_BYTE(lines + wpls, j + 1);
                            if (!boolval && (val8 < val) &&
                                (val8 < GET_DATA_BYTE(linem + wplm, j + 1))) {
                                boolval = TRUE;
                            }
                        }
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        if (!boolval && (val7 < val) &&
                            (val7 < GET_DATA_BYTE(linem + wplm, j))) {
                            boolval = TRUE;
                        }
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        if (!boolval && (val5 < val) &&
                            (val5 < GET_DATA_BYTE(linem, j + 1))) {
                            boolval = TRUE;
                        }
                    }
                    if (boolval) {
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
            }
        }

            /* Propagation step:
             *        while fifo_empty = false
             *          p <- fifo_first()
             *          for every pixel (q) belong to neighbors of (p)
             *            if J(q) < J(p) and I(q) != J(q)
             *              J(q) <- min(J(p), I(q));
             *              fifo_add(q);
             *            end
             *          end
             *        end */
        queue_size = lqueueGetCount(lq_pixel);
        while (queue_size) {
            pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
            i = pixel->x;
            j = pixel->y;
            FREE(pixel);
            lines = datas + i * wpls;
            linem = datam + i * wplm;

            if ((val = GET_DATA_BYTE(lines, j)) > 0) {
                if (i > 0) {
                    if (j > 0) {
                        val1 = GET_DATA_BYTE(lines - wpls, j - 1);
                        maskval = GET_DATA_BYTE(linem - wplm, j - 1);
                        if (val > val1 && val1 != maskval) {
                            SET_DATA_BYTE(lines - wpls, j - 1, L_MIN(val, maskval));
                            pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                            pixel->x = i - 1;
                            pixel->y = j - 1;
                            lqueueAdd(lq_pixel, pixel);
                        }
                    }
                    if (j < jmax) {
                        val3 = GET_DATA_BYTE(lines - wpls, j + 1);
                        maskval = GET_DATA_BYTE(linem - wplm, j + 1);
                        if (val > val3 && val3 != maskval) {
                            SET_DATA_BYTE(lines - wpls, j + 1, L_MIN(val, maskval));
                            pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                            pixel->x = i - 1;
                            pixel->y = j + 1;
                            lqueueAdd(lq_pixel, pixel);
                        }
                    }
                    val2 = GET_DATA_BYTE(lines - wpls, j);
                    maskval = GET_DATA_BYTE(linem - wplm, j);
                    if (val > val2 && val2 != maskval) {
                        SET_DATA_BYTE(lines - wpls, j, L_MIN(val, maskval));
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i - 1;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }

                }
                if (j > 0) {
                    val4 = GET_DATA_BYTE(lines, j - 1);
                    maskval = GET_DATA_BYTE(linem, j - 1);
                    if (val > val4 && val4 != maskval) {
                        SET_DATA_BYTE(lines, j - 1, L_MIN(val, maskval));
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j - 1;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
                if (i < imax) {
                    if (j > 0) {
                        val6 = GET_DATA_BYTE(lines + wpls, j - 1);
                        maskval = GET_DATA_BYTE(linem + wplm, j - 1);
                        if (val > val6 && val6 != maskval) {
                            SET_DATA_BYTE(lines + wpls, j - 1, L_MIN(val, maskval));
                            pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                            pixel->x = i + 1;
                            pixel->y = j - 1;
                            lqueueAdd(lq_pixel, pixel);
                        }
                    }
                    if (j < jmax) {
                        val8 = GET_DATA_BYTE(lines + wpls, j + 1);
                        maskval = GET_DATA_BYTE(linem + wplm, j + 1);
                        if (val > val8 && val8 != maskval) {
                            SET_DATA_BYTE(lines + wpls, j + 1, L_MIN(val, maskval));
                            pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                            pixel->x = i + 1;
                            pixel->y = j + 1;
                            lqueueAdd(lq_pixel, pixel);
                        }
                    }
                    val7 = GET_DATA_BYTE(lines + wpls, j);
                    maskval = GET_DATA_BYTE(linem + wplm, j);
                    if (val > val7 && val7 != maskval) {
                        SET_DATA_BYTE(lines + wpls, j, L_MIN(val, maskval));
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i + 1;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
                if (j < jmax) {
                    val5 = GET_DATA_BYTE(lines, j + 1);
                    maskval = GET_DATA_BYTE(linem, j + 1);
                    if (val > val5 && val5 != maskval) {
                        SET_DATA_BYTE(lines, j + 1, L_MIN(val, maskval));
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j + 1;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
            }

            queue_size = lqueueGetCount(lq_pixel);
        }
        break;

    default:
        L_ERROR("connectivity must be 4 or 8", procName);
        lqueueDestroy(&lq_pixel, TRUE);
    }

    lqueueDestroy(&lq_pixel, TRUE);
    return;
}


/*!
 *  seedfillGrayInvLow()
 *
 *  Notes:
 *      (1) The pixels are numbered as follows:
 *              1  2  3
 *              4  x  5
 *              6  7  8
 *          This low-level filling operation consists of two scans,
 *          raster and anti-raster, covering the entire seed image.
 *          During the anti-raster scan, every pixel p such that its
 *          current value could still be propogated during the next
 *          raster scanning is put into the FIFO-queue.
 *          Next step is the propagation step where where we update
 *          and propagate the values using FIFO structure created in
 *          anti-raster scan.
 *      (2) The "Inv" signifies the fact that in this case, filling
 *          of the seed only takes place when the seed value is
 *          greater than the mask value.  The mask will act to stop
 *          the fill when it is higher than the seed level.  (This is
 *          in contrast to conventional grayscale filling where the
 *          seed always fills below the mask.)
 *      (3) An example of use is a basin, described by the mask (pixm),
 *          where within the basin, the seed pix (pixs) gets filled to the
 *          height of the highest seed pixel that is above its
 *          corresponding max pixel.  Filling occurs while the
 *          propagating seed pixels in pixs are larger than the
 *          corresponding mask values in pixm.
 *      (4) Reference paper :
 *            L. Vincent, Morphological grayscale reconstruction in image
 *            analysis: applications and efficient algorithms, IEEE Transactions
 *            on  Image Processing, vol. 2, no. 2, pp. 176-201, 1993.
 */
void
seedfillGrayInvLow(l_uint32  *datas,
                   l_int32    w,
                   l_int32    h,
                   l_int32    wpls,
                   l_uint32  *datam,
                   l_int32    wplm,
                   l_int32    connectivity)
{
l_uint8    val1, val2, val3, val4, val5, val6, val7, val8;
l_uint8    val, maxval, maskval, boolval;
l_int32    i, j, imax, jmax, queue_size;
l_uint32  *lines, *linem;
L_PIXEL *pixel;
L_QUEUE  *lq_pixel;

    PROCNAME("seedfillGrayInvLow");

    imax = h - 1;
    jmax = w - 1;

        /* In the worst case, most of the pixels could be pushed
         * onto the FIFO queue during anti-raster scan.  However this
         * will rarely happen, and we initialize the queue ptr size to
         * the image perimeter. */
    lq_pixel = lqueueCreate(2 * (w + h));

    switch (connectivity)
    {
    case 4:
            /* UL --> LR scan  (Raster Order)
             * If I : mask image
             *    J : marker image
             * Let p be the currect pixel;
             * tmp <- max{J(p) union J(p) neighbors in raster order}
             * if (tmp > I(p))
             *   J(p) <- tmp
             * end */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < w; j++) {
                if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
                    maxval = GET_DATA_BYTE(lines, j);
                    if (i > 0) {
                        val2 = GET_DATA_BYTE(lines - wpls, j);
                        maxval = L_MAX(maxval, val2);
                    }
                    if (j > 0) {
                        val4 = GET_DATA_BYTE(lines, j - 1);
                        maxval = L_MAX(maxval, val4);
                    }
                    if (maxval > maskval)
                        SET_DATA_BYTE(lines, j, maxval);
                }
            }
        }

            /* LR --> UL scan (anti-raster order)
             * If I : mask image
             *    J : marker image
             * Let p be the currect pixel;
             * tmp <- max{J(p) union J(p) neighbors in anti-raster order}
             * if (tmp > I(p))
             *   J(p) <- tmp
             * end */
        for (i = imax; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = jmax; j >= 0; j--) {
                boolval = FALSE;
                if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
                    val = maxval = GET_DATA_BYTE(lines, j);
                    if (i < imax) {
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        maxval = L_MAX(maxval, val7);
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        maxval = L_MAX(maxval, val5);
                    }
                    if (maxval > maskval)
                        SET_DATA_BYTE(lines, j, maxval);
                    val = GET_DATA_BYTE(lines, j);

                        /*
                         * If there exists a point (q) which belongs to J(p)
                         * neighbors in anti-raster order such that J(q) < J(p)
                         * and J(p) > I(q) then
                         * fifo_add(p) */
                    if (i < imax) {
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        if ((val7 < val) &&
                            (val > GET_DATA_BYTE(linem + wplm, j))) {
                            boolval = TRUE;
                        }
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        if (!boolval && (val5 < val) &&
                            (val > GET_DATA_BYTE(linem, j + 1))) {
                            boolval = TRUE;
                        }
                    }
                    if (boolval) {
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
            }
        }

            /* Propagation step:
             *        while fifo_empty = false
             *          p <- fifo_first()
             *          for every pixel (q) belong to neighbors of (p)
             *            if J(q) < J(p) and J(p) > I(q)
             *              J(q) <- min(J(p), I(q));
             *              fifo_add(q);
             *            end
             *          end
             *        end */
        queue_size = lqueueGetCount(lq_pixel);
        while (queue_size) {
            pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
            i = pixel->x;
            j = pixel->y;
            FREE(pixel);
            lines = datas + i * wpls;
            linem = datam + i * wplm;

            if ((val = GET_DATA_BYTE(lines, j)) > 0) {
                if (i > 0) {
                    val2 = GET_DATA_BYTE(lines - wpls, j);
                    maskval = GET_DATA_BYTE(linem - wplm, j);
                    if (val > val2 && val > maskval) {
                        SET_DATA_BYTE(lines - wpls, j, val);
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i - 1;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }

                }
                if (j > 0) {
                    val4 = GET_DATA_BYTE(lines, j - 1);
                    maskval = GET_DATA_BYTE(linem, j - 1);
                    if (val > val4 && val > maskval) {
                        SET_DATA_BYTE(lines, j - 1, val);
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j - 1;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
                if (i < imax) {
                    val7 = GET_DATA_BYTE(lines + wpls, j);
                    maskval = GET_DATA_BYTE(linem + wplm, j);
                    if (val > val7 && val > maskval) {
                        SET_DATA_BYTE(lines + wpls, j, val);
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i + 1;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
                if (j < jmax) {
                    val5 = GET_DATA_BYTE(lines, j + 1);
                    maskval = GET_DATA_BYTE(linem, j + 1);
                    if (val > val5 && val > maskval) {
                        SET_DATA_BYTE(lines, j + 1, val);
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j + 1;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
            }

            queue_size = lqueueGetCount(lq_pixel);
        }

        break;

    case 8:
            /* UL --> LR scan  (Raster Order)
             * If I : mask image
             *    J : marker image
             * Let p be the currect pixel;
             * tmp <- max{J(p) union J(p) neighbors in raster order}
             * if (tmp > I(p))
             *   J(p) <- tmp
             * end */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < w; j++) {
                if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
                    maxval = GET_DATA_BYTE(lines, j);
                    if (i > 0) {
                        if (j > 0) {
                            val1 = GET_DATA_BYTE(lines - wpls, j - 1);
                            maxval = L_MAX(maxval, val1);
                        }
                        if (j < jmax) {
                            val3 = GET_DATA_BYTE(lines - wpls, j + 1);
                            maxval = L_MAX(maxval, val3);
                        }
                        val2 = GET_DATA_BYTE(lines - wpls, j);
                        maxval = L_MAX(maxval, val2);
                    }
                    if (j > 0) {
                        val4 = GET_DATA_BYTE(lines, j - 1);
                        maxval = L_MAX(maxval, val4);
                    }
                    if (maxval > maskval)
                        SET_DATA_BYTE(lines, j, maxval);
                }
            }
        }

            /* LR --> UL scan (anti-raster order)
             * If I : mask image
             *    J : marker image
             * Let p be the currect pixel;
             * tmp <- max{J(p) union J(p) neighbors in anti-raster order}
             * if (tmp > I(p))
             *   J(p) <- tmp
             * end */
        for (i = imax; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = jmax; j >= 0; j--) {
                boolval = FALSE;
                if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
                    maxval = GET_DATA_BYTE(lines, j);
                    if (i < imax) {
                        if (j > 0) {
                            val6 = GET_DATA_BYTE(lines + wpls, j - 1);
                            maxval = L_MAX(maxval, val6);
                        }
                        if (j < jmax) {
                            val8 = GET_DATA_BYTE(lines + wpls, j + 1);
                            maxval = L_MAX(maxval, val8);
                        }
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        maxval = L_MAX(maxval, val7);
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        maxval = L_MAX(maxval, val5);
                    }
                    if (maxval > maskval)
                        SET_DATA_BYTE(lines, j, maxval);
                    val = GET_DATA_BYTE(lines, j);

                        /*
                         * If there exists a point (q) which belongs to J(p)
                         * neighbors in anti-raster order such that J(q) < J(p)
                         * and J(p) > I(q) then
                         * fifo_add(p) */
                    if (i < imax) {
                        if (j > 0) {
                            val6 = GET_DATA_BYTE(lines + wpls, j - 1);
                            if ((val6 < val) &&
                                (val > GET_DATA_BYTE(linem + wplm, j - 1))) {
                                boolval = TRUE;
                            }
                        }
                        if (j < jmax) {
                            val8 = GET_DATA_BYTE(lines + wpls, j + 1);
                            if (!boolval && (val8 < val) &&
                                (val > GET_DATA_BYTE(linem + wplm, j + 1))) {
                                boolval = TRUE;
                            }
                        }
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        if (!boolval && (val7 < val) &&
                            (val > GET_DATA_BYTE(linem + wplm, j))) {
                            boolval = TRUE;
                        }
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        if (!boolval && (val5 < val) &&
                            (val > GET_DATA_BYTE(linem, j + 1))) {
                            boolval = TRUE;
                        }
                    }
                    if (boolval) {
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
            }
        }

            /* Propagation step:
             *        while fifo_empty = false
             *          p <- fifo_first()
             *          for every pixel (q) belong to neighbors of (p)
             *            if J(q) < J(p) and J(p) > I(q)
             *              J(q) <- min(J(p), I(q));
             *              fifo_add(q);
             *            end
             *          end
             *        end */
        queue_size = lqueueGetCount(lq_pixel);
        while (queue_size) {
            pixel = (L_PIXEL *)lqueueRemove(lq_pixel);
            i = pixel->x;
            j = pixel->y;
            FREE(pixel);
            lines = datas + i * wpls;
            linem = datam + i * wplm;

            if ((val = GET_DATA_BYTE(lines, j)) > 0) {
                if (i > 0) {
                    if (j > 0) {
                        val1 = GET_DATA_BYTE(lines - wpls, j - 1);
                        maskval = GET_DATA_BYTE(linem - wplm, j - 1);
                        if (val > val1 && val > maskval) {
                            SET_DATA_BYTE(lines - wpls, j - 1, val);
                            pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                            pixel->x = i - 1;
                            pixel->y = j - 1;
                            lqueueAdd(lq_pixel, pixel);
                        }
                    }
                    if (j < jmax) {
                        val3 = GET_DATA_BYTE(lines - wpls, j + 1);
                        maskval = GET_DATA_BYTE(linem - wplm, j + 1);
                        if (val > val3 && val > maskval) {
                            SET_DATA_BYTE(lines - wpls, j + 1, val);
                            pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                            pixel->x = i - 1;
                            pixel->y = j + 1;
                            lqueueAdd(lq_pixel, pixel);
                        }
                    }
                    val2 = GET_DATA_BYTE(lines - wpls, j);
                    maskval = GET_DATA_BYTE(linem - wplm, j);
                    if (val > val2 && val > maskval) {
                        SET_DATA_BYTE(lines - wpls, j, val);
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i - 1;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }

                }
                if (j > 0) {
                    val4 = GET_DATA_BYTE(lines, j - 1);
                    maskval = GET_DATA_BYTE(linem, j - 1);
                    if (val > val4 && val > maskval) {
                        SET_DATA_BYTE(lines, j - 1, val);
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j - 1;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
                if (i < imax) {
                    if (j > 0) {
                        val6 = GET_DATA_BYTE(lines + wpls, j - 1);
                        maskval = GET_DATA_BYTE(linem + wplm, j - 1);
                        if (val > val6 && val > maskval) {
                            SET_DATA_BYTE(lines + wpls, j - 1, val);
                            pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                            pixel->x = i + 1;
                            pixel->y = j - 1;
                            lqueueAdd(lq_pixel, pixel);
                        }
                    }
                    if (j < jmax) {
                        val8 = GET_DATA_BYTE(lines + wpls, j + 1);
                        maskval = GET_DATA_BYTE(linem + wplm, j + 1);
                        if (val > val8 && val > maskval) {
                            SET_DATA_BYTE(lines + wpls, j + 1, val);
                            pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                            pixel->x = i + 1;
                            pixel->y = j + 1;
                            lqueueAdd(lq_pixel, pixel);
                        }
                    }
                    val7 = GET_DATA_BYTE(lines + wpls, j);
                    maskval = GET_DATA_BYTE(linem + wplm, j);
                    if (val > val7 && val > maskval) {
                        SET_DATA_BYTE(lines + wpls, j, val);
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i + 1;
                        pixel->y = j;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
                if (j < jmax) {
                    val5 = GET_DATA_BYTE(lines, j + 1);
                    maskval = GET_DATA_BYTE(linem, j + 1);
                    if (val > val5 && val > maskval) {
                        SET_DATA_BYTE(lines, j + 1, val);
                        pixel = (L_PIXEL *)CALLOC(1, sizeof(L_PIXEL));
                        pixel->x = i;
                        pixel->y = j + 1;
                        lqueueAdd(lq_pixel, pixel);
                    }
                }
            }

            queue_size = lqueueGetCount(lq_pixel);
        }
        break;

    default:
        lqueueDestroy(&lq_pixel, TRUE);
        L_ERROR("connectivity must be 4 or 8", procName);
    }

    lqueueDestroy(&lq_pixel, TRUE);
    return;
}

/*-----------------------------------------------------------------------*
 *                 Vincent's Iterative Grayscale Seedfill                *
 *-----------------------------------------------------------------------*/
/*!
 *  seedfillGrayLowSimple()
 *
 *  Notes:
 *      (1) The pixels are numbered as follows:
 *              1  2  3
 *              4  x  5
 *              6  7  8
 *          This low-level filling operation consists of two scans,
 *          raster and anti-raster, covering the entire seed image.
 *          The caller typically iterates until the filling is
 *          complete.
 *      (2) The filling action can be visualized from the following example.
 *          Suppose the mask, which clips the fill, is a sombrero-shaped
 *          surface, where the highest point is 200 and the low pixels
 *          around the rim are 30.  Beyond the rim, the mask goes up a bit.
 *          Suppose the seed, which is filled, consists of a single point
 *          of height 150, located below the max of the mask, with
 *          the rest 0.  Then in the raster scan, nothing happens until
 *          the high seed point is encountered, and then this value is
 *          propagated right and down, until it hits the side of the
 *          sombrero.   The seed can never exceed the mask, so it fills
 *          to the rim, going lower along the mask surface.  When it
 *          passes the rim, the seed continues to fill at the rim
 *          height to the edge of the seed image.  Then on the
 *          anti-raster scan, the seed fills flat inside the
 *          sombrero to the upper and left, and then out from the
 *          rim as before.  The final result has a seed that is
 *          flat outside the rim, and inside it fills the sombrero
 *          but only up to 150.  If the rim height varies, the
 *          filled seed outside the rim will be at the highest
 *          point on the rim, which is a saddle point on the rim.
 */
void
seedfillGrayLowSimple(l_uint32  *datas,
                      l_int32    w,
                      l_int32    h,
                      l_int32    wpls,
                      l_uint32  *datam,
                      l_int32    wplm,
                      l_int32    connectivity)
{
l_uint8    val2, val3, val4, val5, val7, val8;
l_uint8    val, maxval, maskval;
l_int32    i, j, imax, jmax;
l_uint32  *lines, *linem;

    PROCNAME("seedfillGrayLowSimple");

    imax = h - 1;
    jmax = w - 1;

    switch (connectivity)
    {
    case 4:
            /* UL --> LR scan */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < w; j++) {
                if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
                    maxval = 0;
                    if (i > 0)
                        maxval = GET_DATA_BYTE(lines - wpls, j);
                    if (j > 0) {
                        val4 = GET_DATA_BYTE(lines, j - 1);
                        maxval = L_MAX(maxval, val4);
                    }
                    val = GET_DATA_BYTE(lines, j);
                    maxval = L_MAX(maxval, val);
                    val = L_MIN(maxval, maskval);
                    SET_DATA_BYTE(lines, j, val);
                }
            }
        }

            /* LR --> UL scan */
        for (i = imax; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = jmax; j >= 0; j--) {
                if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
                    maxval = 0;
                    if (i < imax)
                        maxval = GET_DATA_BYTE(lines + wpls, j);
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        maxval = L_MAX(maxval, val5);
                    }
                    val = GET_DATA_BYTE(lines, j);
                    maxval = L_MAX(maxval, val);
                    val = L_MIN(maxval, maskval);
                    SET_DATA_BYTE(lines, j, val);
                }
            }
        }
        break;

    case 8:
            /* UL --> LR scan */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < w; j++) {
                if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
                    maxval = 0;
                    if (i > 0) {
                        if (j > 0)
                            maxval = GET_DATA_BYTE(lines - wpls, j - 1);
                        if (j < jmax) {
                            val2 = GET_DATA_BYTE(lines - wpls, j + 1);
                            maxval = L_MAX(maxval, val2);
                        }
                        val3 = GET_DATA_BYTE(lines - wpls, j);
                        maxval = L_MAX(maxval, val3);
                    }
                    if (j > 0) {
                        val4 = GET_DATA_BYTE(lines, j - 1);
                        maxval = L_MAX(maxval, val4);
                    }
                    val = GET_DATA_BYTE(lines, j);
                    maxval = L_MAX(maxval, val);
                    val = L_MIN(maxval, maskval);
                    SET_DATA_BYTE(lines, j, val);
                }
            }
        }

            /* LR --> UL scan */
        for (i = imax; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = jmax; j >= 0; j--) {
                if ((maskval = GET_DATA_BYTE(linem, j)) > 0) {
                    maxval = 0;
                    if (i < imax) {
                        if (j > 0)
                            maxval = GET_DATA_BYTE(lines + wpls, j - 1);
                        if (j < jmax) {
                            val8 = GET_DATA_BYTE(lines + wpls, j + 1);
                            maxval = L_MAX(maxval, val8);
                        }
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        maxval = L_MAX(maxval, val7);
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        maxval = L_MAX(maxval, val5);
                    }
                    val = GET_DATA_BYTE(lines, j);
                    maxval = L_MAX(maxval, val);
                    val = L_MIN(maxval, maskval);
                    SET_DATA_BYTE(lines, j, val);
                }
            }
        }
        break;

    default:
        L_ERROR("connectivity must be 4 or 8", procName);
    }

    return;
}


/*!
 *  seedfillGrayInvLowSimple()
 *
 *  Notes:
 *      (1) The pixels are numbered as follows:
 *              1  2  3
 *              4  x  5
 *              6  7  8
 *          This low-level filling operation consists of two scans,
 *          raster and anti-raster, covering the entire seed image.
 *          The caller typically iterates until the filling is
 *          complete.
 *      (2) The "Inv" signifies the fact that in this case, filling
 *          of the seed only takes place when the seed value is
 *          greater than the mask value.  The mask will act to stop
 *          the fill when it is higher than the seed level.  (This is
 *          in contrast to conventional grayscale filling where the
 *          seed always fills below the mask.)
 *      (3) An example of use is a basin, described by the mask (pixm),
 *          where within the basin, the seed pix (pixs) gets filled to the
 *          height of the highest seed pixel that is above its
 *          corresponding max pixel.  Filling occurs while the
 *          propagating seed pixels in pixs are larger than the
 *          corresponding mask values in pixm.
 */
void
seedfillGrayInvLowSimple(l_uint32  *datas,
                         l_int32    w,
                         l_int32    h,
                         l_int32    wpls,
                         l_uint32  *datam,
                         l_int32    wplm,
                         l_int32    connectivity)
{
l_uint8    val1, val2, val3, val4, val5, val6, val7, val8;
l_uint8    maxval, maskval;
l_int32    i, j, imax, jmax;
l_uint32  *lines, *linem;

    PROCNAME("seedfillGrayInvLowSimple");

    imax = h - 1;
    jmax = w - 1;

    switch (connectivity)
    {
    case 4:
            /* UL --> LR scan */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < w; j++) {
                if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
                    maxval = GET_DATA_BYTE(lines, j);
                    if (i > 0) {
                        val2 = GET_DATA_BYTE(lines - wpls, j);
                        maxval = L_MAX(maxval, val2);
                    }
                    if (j > 0) {
                        val4 = GET_DATA_BYTE(lines, j - 1);
                        maxval = L_MAX(maxval, val4);
                    }
                    if (maxval > maskval)
                        SET_DATA_BYTE(lines, j, maxval);
                }
            }
        }

            /* LR --> UL scan */
        for (i = imax; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = jmax; j >= 0; j--) {
                if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
                    maxval = GET_DATA_BYTE(lines, j);
                    if (i < imax) {
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        maxval = L_MAX(maxval, val7);
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        maxval = L_MAX(maxval, val5);
                    }
                    if (maxval > maskval)
                        SET_DATA_BYTE(lines, j, maxval);
                }
            }
        }
        break;

    case 8:
            /* UL --> LR scan */
        for (i = 0; i < h; i++) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = 0; j < w; j++) {
                if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
                    maxval = GET_DATA_BYTE(lines, j);
                    if (i > 0) {
                        if (j > 0) {
                            val1 = GET_DATA_BYTE(lines - wpls, j - 1);
                            maxval = L_MAX(maxval, val1);
                        }
                        if (j < jmax) {
                            val2 = GET_DATA_BYTE(lines - wpls, j + 1);
                            maxval = L_MAX(maxval, val2);
                        }
                        val3 = GET_DATA_BYTE(lines - wpls, j);
                        maxval = L_MAX(maxval, val3);
                    }
                    if (j > 0) {
                        val4 = GET_DATA_BYTE(lines, j - 1);
                        maxval = L_MAX(maxval, val4);
                    }
                    if (maxval > maskval)
                        SET_DATA_BYTE(lines, j, maxval);
                }
            }
        }

            /* LR --> UL scan */
        for (i = imax; i >= 0; i--) {
            lines = datas + i * wpls;
            linem = datam + i * wplm;
            for (j = jmax; j >= 0; j--) {
                if ((maskval = GET_DATA_BYTE(linem, j)) < 255) {
                    maxval = GET_DATA_BYTE(lines, j);
                    if (i < imax) {
                        if (j > 0) {
                            val6 = GET_DATA_BYTE(lines + wpls, j - 1);
                            maxval = L_MAX(maxval, val6);
                        }
                        if (j < jmax) {
                            val8 = GET_DATA_BYTE(lines + wpls, j + 1);
                            maxval = L_MAX(maxval, val8);
                        }
                        val7 = GET_DATA_BYTE(lines + wpls, j);
                        maxval = L_MAX(maxval, val7);
                    }
                    if (j < jmax) {
                        val5 = GET_DATA_BYTE(lines, j + 1);
                        maxval = L_MAX(maxval, val5);
                    }
                    if (maxval > maskval)
                        SET_DATA_BYTE(lines, j, maxval);
                }
            }
        }
        break;

    default:
        L_ERROR("connectivity must be 4 or 8", procName);
    }

    return;
}


/*-----------------------------------------------------------------------*
 *                   Vincent's Distance Function method                  *
 *-----------------------------------------------------------------------*/
/*!
 *  distanceFunctionLow()
 */
void
distanceFunctionLow(l_uint32  *datad,
                    l_int32    w,
                    l_int32    h,
                    l_int32    d,
                    l_int32    wpld,
                    l_int32    connectivity)
{
l_int32    val1, val2, val3, val4, val5, val6, val7, val8, minval, val;
l_int32    i, j, imax, jmax;
l_uint32  *lined;

    PROCNAME("distanceFunctionLow");

        /* One raster scan followed by one anti-raster scan.
         * This does not re-set the 1-boundary of pixels that
         * were initialized to either 0 or maxval. */
    imax = h - 1;
    jmax = w - 1;
    switch (connectivity)
    {
    case 4:
        if (d == 8) {
                /* UL --> LR scan */
            for (i = 1; i < imax; i++) {
                lined = datad + i * wpld;
                for (j = 1; j < jmax; j++) {
                    if ((val = GET_DATA_BYTE(lined, j)) > 0) {
                        val2 = GET_DATA_BYTE(lined - wpld, j);
                        val4 = GET_DATA_BYTE(lined, j - 1);
                        minval = L_MIN(val2, val4);
                        minval = L_MIN(minval, 254);
                        SET_DATA_BYTE(lined, j, minval + 1);
                    }
                }
            }

                /* LR --> UL scan */
            for (i = imax - 1; i > 0; i--) {
                lined = datad + i * wpld;
                for (j = jmax - 1; j > 0; j--) {
                    if ((val = GET_DATA_BYTE(lined, j)) > 0) {
                        val7 = GET_DATA_BYTE(lined + wpld, j);
                        val5 = GET_DATA_BYTE(lined, j + 1);
                        minval = L_MIN(val5, val7);
                        minval = L_MIN(minval + 1, val);
                        SET_DATA_BYTE(lined, j, minval);
                    }
                }
            }
        }
        else {  /* d == 16 */
                /* UL --> LR scan */
            for (i = 1; i < imax; i++) {
                lined = datad + i * wpld;
                for (j = 1; j < jmax; j++) {
                    if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
                        val2 = GET_DATA_TWO_BYTES(lined - wpld, j);
                        val4 = GET_DATA_TWO_BYTES(lined, j - 1);
                        minval = L_MIN(val2, val4);
                        minval = L_MIN(minval, 0xfffe);
                        SET_DATA_TWO_BYTES(lined, j, minval + 1);
                    }
                }
            }

                /* LR --> UL scan */
            for (i = imax - 1; i > 0; i--) {
                lined = datad + i * wpld;
                for (j = jmax - 1; j > 0; j--) {
                    if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
                        val7 = GET_DATA_TWO_BYTES(lined + wpld, j);
                        val5 = GET_DATA_TWO_BYTES(lined, j + 1);
                        minval = L_MIN(val5, val7);
                        minval = L_MIN(minval + 1, val);
                        SET_DATA_TWO_BYTES(lined, j, minval);
                    }
                }
            }
        }
        break;

    case 8:
        if (d == 8) {
                /* UL --> LR scan */
            for (i = 1; i < imax; i++) {
                lined = datad + i * wpld;
                for (j = 1; j < jmax; j++) {
                    if ((val = GET_DATA_BYTE(lined, j)) > 0) {
                        val1 = GET_DATA_BYTE(lined - wpld, j - 1);
                        val2 = GET_DATA_BYTE(lined - wpld, j);
                        val3 = GET_DATA_BYTE(lined - wpld, j + 1);
                        val4 = GET_DATA_BYTE(lined, j - 1);
                        minval = L_MIN(val1, val2);
                        minval = L_MIN(minval, val3);
                        minval = L_MIN(minval, val4);
                        minval = L_MIN(minval, 254);
                        SET_DATA_BYTE(lined, j, minval + 1);
                    }
                }
            }

                /* LR --> UL scan */
            for (i = imax - 1; i > 0; i--) {
                lined = datad + i * wpld;
                for (j = jmax - 1; j > 0; j--) {
                    if ((val = GET_DATA_BYTE(lined, j)) > 0) {
                        val8 = GET_DATA_BYTE(lined + wpld, j + 1);
                        val7 = GET_DATA_BYTE(lined + wpld, j);
                        val6 = GET_DATA_BYTE(lined + wpld, j - 1);
                        val5 = GET_DATA_BYTE(lined, j + 1);
                        minval = L_MIN(val8, val7);
                        minval = L_MIN(minval, val6);
                        minval = L_MIN(minval, val5);
                        minval = L_MIN(minval + 1, val);
                        SET_DATA_BYTE(lined, j, minval);
                    }
                }
            }
        }
        else {  /* d == 16 */
                /* UL --> LR scan */
            for (i = 1; i < imax; i++) {
                lined = datad + i * wpld;
                for (j = 1; j < jmax; j++) {
                    if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
                        val1 = GET_DATA_TWO_BYTES(lined - wpld, j - 1);
                        val2 = GET_DATA_TWO_BYTES(lined - wpld, j);
                        val3 = GET_DATA_TWO_BYTES(lined - wpld, j + 1);
                        val4 = GET_DATA_TWO_BYTES(lined, j - 1);
                        minval = L_MIN(val1, val2);
                        minval = L_MIN(minval, val3);
                        minval = L_MIN(minval, val4);
                        minval = L_MIN(minval, 0xfffe);
                        SET_DATA_TWO_BYTES(lined, j, minval + 1);
                    }
                }
            }

                /* LR --> UL scan */
            for (i = imax - 1; i > 0; i--) {
                lined = datad + i * wpld;
                for (j = jmax - 1; j > 0; j--) {
                    if ((val = GET_DATA_TWO_BYTES(lined, j)) > 0) {
                        val8 = GET_DATA_TWO_BYTES(lined + wpld, j + 1);
                        val7 = GET_DATA_TWO_BYTES(lined + wpld, j);
                        val6 = GET_DATA_TWO_BYTES(lined + wpld, j - 1);
                        val5 = GET_DATA_TWO_BYTES(lined, j + 1);
                        minval = L_MIN(val8, val7);
                        minval = L_MIN(minval, val6);
                        minval = L_MIN(minval, val5);
                        minval = L_MIN(minval + 1, val);
                        SET_DATA_TWO_BYTES(lined, j, minval);
                    }
                }
            }
        }
        break;

    default:
        L_ERROR("connectivity must be 4 or 8", procName);
        break;
    }

    return;
}


/*-----------------------------------------------------------------------*
 *                 Seed spread (based on distance function)              *
 *-----------------------------------------------------------------------*/
/*!
 *  seedspreadLow()
 *
 *    See pixSeedspread() for a brief description of the algorithm here.
 */
void
seedspreadLow(l_uint32  *datad,
              l_int32    w,
              l_int32    h,
              l_int32    wpld,
              l_uint32  *datat,
              l_int32    wplt,
              l_int32    connectivity)
{
l_int32    val1t, val2t, val3t, val4t, val5t, val6t, val7t, val8t;
l_int32    i, j, imax, jmax, minval, valt, vald;
l_uint32  *linet, *lined;

    PROCNAME("seedspreadLow");

        /* One raster scan followed by one anti-raster scan.
         * pixt is initialized to have 0 on pixels where the
         * input is specified in pixd, and to have 1 on all
         * other pixels.  We only change pixels in pixt and pixd
         * that are non-zero in pixt. */
    imax = h - 1;
    jmax = w - 1;
    switch (connectivity)
    {
    case 4:
            /* UL --> LR scan */
        for (i = 1; i < h; i++) {
            linet = datat + i * wplt;
            lined = datad + i * wpld;
            for (j = 1; j < jmax; j++) {
                if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
                    val2t = GET_DATA_TWO_BYTES(linet - wplt, j);
                    val4t = GET_DATA_TWO_BYTES(linet, j - 1);
                    minval = L_MIN(val2t, val4t);
                    minval = L_MIN(minval, 0xfffe);
                    SET_DATA_TWO_BYTES(linet, j, minval + 1);
                    if (val2t < val4t)
                        vald = GET_DATA_BYTE(lined - wpld, j);
                    else
                        vald = GET_DATA_BYTE(lined, j - 1);
                    SET_DATA_BYTE(lined, j, vald);
                }
            }
        }

            /* LR --> UL scan */
        for (i = imax - 1; i > 0; i--) {
            linet = datat + i * wplt;
            lined = datad + i * wpld;
            for (j = jmax - 1; j > 0; j--) {
                if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
                    val7t = GET_DATA_TWO_BYTES(linet + wplt, j);
                    val5t = GET_DATA_TWO_BYTES(linet, j + 1);
                    minval = L_MIN(val5t, val7t);
                    minval = L_MIN(minval + 1, valt);
                    if (valt > minval) {  /* replace */
                        SET_DATA_TWO_BYTES(linet, j, minval);
                        if (val5t < val7t)
                            vald = GET_DATA_BYTE(lined, j + 1);
                        else
                            vald = GET_DATA_BYTE(lined + wplt, j);
                        SET_DATA_BYTE(lined, j, vald);
                    }
                }
            }
        }
        break;
    case 8:
            /* UL --> LR scan */
        for (i = 1; i < h; i++) {
            linet = datat + i * wplt;
            lined = datad + i * wpld;
            for (j = 1; j < jmax; j++) {
                if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
                    val1t = GET_DATA_TWO_BYTES(linet - wplt, j - 1);
                    val2t = GET_DATA_TWO_BYTES(linet - wplt, j);
                    val3t = GET_DATA_TWO_BYTES(linet - wplt, j + 1);
                    val4t = GET_DATA_TWO_BYTES(linet, j - 1);
                    minval = L_MIN(val1t, val2t);
                    minval = L_MIN(minval, val3t);
                    minval = L_MIN(minval, val4t);
                    minval = L_MIN(minval, 0xfffe);
                    SET_DATA_TWO_BYTES(linet, j, minval + 1);
                    if (minval == val1t)
                        vald = GET_DATA_BYTE(lined - wpld, j - 1);
                    else if (minval == val2t)
                        vald = GET_DATA_BYTE(lined - wpld, j);
                    else if (minval == val3t)
                        vald = GET_DATA_BYTE(lined - wpld, j + 1);
                    else  /* minval == val4t */
                        vald = GET_DATA_BYTE(lined, j - 1);
                    SET_DATA_BYTE(lined, j, vald);
                }
            }
        }

            /* LR --> UL scan */
        for (i = imax - 1; i > 0; i--) {
            linet = datat + i * wplt;
            lined = datad + i * wpld;
            for (j = jmax - 1; j > 0; j--) {
                if ((valt = GET_DATA_TWO_BYTES(linet, j)) > 0) {
                    val8t = GET_DATA_TWO_BYTES(linet + wplt, j + 1);
                    val7t = GET_DATA_TWO_BYTES(linet + wplt, j);
                    val6t = GET_DATA_TWO_BYTES(linet + wplt, j - 1);
                    val5t = GET_DATA_TWO_BYTES(linet, j + 1);
                    minval = L_MIN(val8t, val7t);
                    minval = L_MIN(minval, val6t);
                    minval = L_MIN(minval, val5t);
                    minval = L_MIN(minval + 1, valt);
                    if (valt > minval) {  /* replace */
                        SET_DATA_TWO_BYTES(linet, j, minval);
                        if (minval == val5t + 1)
                            vald = GET_DATA_BYTE(lined, j + 1);
                        else if (minval == val6t + 1)
                            vald = GET_DATA_BYTE(lined + wpld, j - 1);
                        else if (minval == val7t + 1)
                            vald = GET_DATA_BYTE(lined + wpld, j);
                        else  /* minval == val8t + 1 */
                            vald = GET_DATA_BYTE(lined + wpld, j + 1);
                        SET_DATA_BYTE(lined, j, vald);
                    }
                }
            }
        }
        break;
    default:
        L_ERROR("connectivity must be 4 or 8", procName);
        break;
    }

    return;
}