binarize.c

Go to the documentation of this file.

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. Redistributions in binary form must reproduce the above
 -     copyright notice, this list of conditions and the following
 -     disclaimer in the documentation and/or other materials
 -     provided with the distribution.
 -
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *====================================================================*/
 
#ifdef HAVE_CONFIG_H
#include <config_auto.h>
#endif  /* HAVE_CONFIG_H */
 
#include <math.h>
#include "allheaders.h"
 
static PIX *pixSauvolaGetThreshold(PIX *pixm, PIX *pixms, l_float32 factor,
                                   PIX **ppixsd);
static PIX *pixApplyLocalThreshold(PIX *pixs, PIX *pixth);
 
/*------------------------------------------------------------------*
 *                 Adaptive Otsu-based thresholding                 *
 *------------------------------------------------------------------*/
l_ok
pixOtsuAdaptiveThreshold(PIX       *pixs,
                         l_int32    sx,
                         l_int32    sy,
                         l_int32    smoothx,
                         l_int32    smoothy,
                         l_float32  scorefract,
                         PIX      **ppixth,
                         PIX      **ppixd)
{
l_int32     w, h, nx, ny, i, j, thresh;
l_uint32    val;
PIX        *pixt, *pixb, *pixthresh, *pixth, *pixd;
PIXTILING  *pt;
 
    if (!ppixth && !ppixd)
        return ERROR_INT("neither &pixth nor &pixd defined", __func__, 1);
    if (ppixth) *ppixth = NULL;
    if (ppixd) *ppixd = NULL;
    if (!pixs || pixGetDepth(pixs) != 8)
        return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
    if (sx < 16 || sy < 16)
        return ERROR_INT("sx and sy must be >= 16", __func__, 1);
 
        /* Compute the threshold array for the tiles */
    pixGetDimensions(pixs, &w, &h, NULL);
    nx = L_MAX(1, w / sx);
    ny = L_MAX(1, h / sy);
    smoothx = L_MIN(smoothx, (nx - 1) / 2);
    smoothy = L_MIN(smoothy, (ny - 1) / 2);
    pt = pixTilingCreate(pixs, nx, ny, 0, 0, 0, 0);
    pixthresh = pixCreate(nx, ny, 8);
    for (i = 0; i < ny; i++) {
        for (j = 0; j < nx; j++) {
            pixt = pixTilingGetTile(pt, i, j);
            pixSplitDistributionFgBg(pixt, scorefract, 1, &thresh,
                                     NULL, NULL, NULL);
            pixSetPixel(pixthresh, j, i, thresh);  /* see note (4) */
            pixDestroy(&pixt);
        }
    }
 
        /* Optionally smooth the threshold array */
    if (smoothx > 0 || smoothy > 0)
        pixth = pixBlockconv(pixthresh, smoothx, smoothy);
    else
        pixth = pixClone(pixthresh);
    pixDestroy(&pixthresh);
 
        /* Optionally apply the threshold array to binarize pixs */
    if (ppixd) {
        pixd = pixCreate(w, h, 1);
        pixCopyResolution(pixd, pixs);
        for (i = 0; i < ny; i++) {
            for (j = 0; j < nx; j++) {
                pixt = pixTilingGetTile(pt, i, j);
                pixGetPixel(pixth, j, i, &val);
                pixb = pixThresholdToBinary(pixt, val);
                pixTilingPaintTile(pixd, i, j, pixb, pt);
                pixDestroy(&pixt);
                pixDestroy(&pixb);
            }
        }
        *ppixd = pixd;
    }
 
    if (ppixth)
        *ppixth = pixth;
    else
        pixDestroy(&pixth);
 
    pixTilingDestroy(&pt);
    return 0;
}
 
 
/*------------------------------------------------------------------*
 *      Otsu thresholding on adaptive background normalization      *
 *------------------------------------------------------------------*/
PIX *
pixOtsuThreshOnBackgroundNorm(PIX       *pixs,
                              PIX       *pixim,
                              l_int32    sx,
                              l_int32    sy,
                              l_int32    thresh,
                              l_int32    mincount,
                              l_int32    bgval,
                              l_int32    smoothx,
                              l_int32    smoothy,
                              l_float32  scorefract,
                              l_int32   *pthresh)
{
l_int32   w, h;
l_uint32  val;
PIX      *pixn, *pixt, *pixd;
 
    if (pthresh) *pthresh = 0;
    if (!pixs || pixGetDepth(pixs) != 8)
        return (PIX *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
    if (pixGetColormap(pixs))
        return (PIX *)ERROR_PTR("pixs is colormapped", __func__, NULL);
    if (sx < 4 || sy < 4)
        return (PIX *)ERROR_PTR("sx and sy must be >= 4", __func__, NULL);
    if (mincount > sx * sy) {
        L_WARNING("mincount too large for tile size\n", __func__);
        mincount = (sx * sy) / 3;
    }
 
    pixn = pixBackgroundNorm(pixs, pixim, NULL, sx, sy, thresh,
                             mincount, bgval, smoothx, smoothy);
    if (!pixn)
        return (PIX *)ERROR_PTR("pixn not made", __func__, NULL);
 
        /* Just use 1 tile for a global threshold, which is stored
         * as a single pixel in pixt. */
    pixGetDimensions(pixn, &w, &h, NULL);
    pixOtsuAdaptiveThreshold(pixn, w, h, 0, 0, scorefract, &pixt, &pixd);
    pixDestroy(&pixn);
 
    if (pixt && pthresh) {
        pixGetPixel(pixt, 0, 0, &val);
        *pthresh = val;
    }
    pixDestroy(&pixt);
 
    if (!pixd)
        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
    else
        return pixd;
}
 
 
 
/*----------------------------------------------------------------------*
 *    Masking and Otsu estimate on adaptive background normalization    *
 *----------------------------------------------------------------------*/
PIX *
pixMaskedThreshOnBackgroundNorm(PIX       *pixs,
                                PIX       *pixim,
                                l_int32    sx,
                                l_int32    sy,
                                l_int32    thresh,
                                l_int32    mincount,
                                l_int32    smoothx,
                                l_int32    smoothy,
                                l_float32  scorefract,
                                l_int32   *pthresh)
{
l_int32   w, h, highthresh;
l_uint32  val;
PIX      *pixn, *pixm, *pixd, *pix1, *pix2, *pix3, *pix4;
 
    if (pthresh) *pthresh = 0;
    if (!pixs || pixGetDepth(pixs) != 8)
        return (PIX *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
    if (pixGetColormap(pixs))
        return (PIX *)ERROR_PTR("pixs is colormapped", __func__, NULL);
    if (sx < 4 || sy < 4)
        return (PIX *)ERROR_PTR("sx and sy must be >= 4", __func__, NULL);
    if (mincount > sx * sy) {
        L_WARNING("mincount too large for tile size\n", __func__);
        mincount = (sx * sy) / 3;
    }
 
        /* Standard background normalization */
    pixn = pixBackgroundNorm(pixs, pixim, NULL, sx, sy, thresh,
                             mincount, 255, smoothx, smoothy);
    if (!pixn)
        return (PIX *)ERROR_PTR("pixn not made", __func__, NULL);
 
        /* Special background normalization for adaptation to quickly
         * varying background.  Threshold on the very light parts,
         * which tend to be near significant edges, and dilate to
         * form a mask over regions that are typically text.  The
         * dilation size is chosen to cover the text completely,
         * except for very thick fonts. */
    pix1 = pixBackgroundNormFlex(pixs, 7, 7, 1, 1, 20);
    pix2 = pixThresholdToBinary(pix1, 240);
    pixInvert(pix2, pix2);
    pixm = pixMorphSequence(pix2, "d21.21", 0);
    pixDestroy(&pix1);
    pixDestroy(&pix2);
 
        /* Use Otsu to get a global threshold estimate for the image,
         * which is stored as a single pixel in pix3. */
    pixGetDimensions(pixs, &w, &h, NULL);
    pixOtsuAdaptiveThreshold(pixs, w, h, 0, 0, scorefract, &pix3, NULL);
    pixGetPixel(pix3, 0, 0, &val);
    if (pthresh) *pthresh = val;
    pixDestroy(&pix3);
 
        /* Threshold the background normalized images differentially,
         * using a high value correlated with the background normalization
         * for the part of the image under the mask (i.e., near the
         * darker, thicker foreground), and a value that depends on the Otsu
         * threshold for the rest of the image.  This gives a solid
         * (high) thresholding for the foreground parts of the image,
         * while allowing the background and light foreground to be
         * reasonably well cleaned using a threshold adapted to the
         * input image. */
    highthresh = L_MIN(256, val + 30);
    pixd = pixThresholdToBinary(pixn, highthresh);  /* for bg and light fg */
    pix4 = pixThresholdToBinary(pixn, 190);  /* for heavier fg */
    pixCombineMasked(pixd, pix4, pixm);
    pixDestroy(&pix4);
    pixDestroy(&pixm);
    pixDestroy(&pixn);
 
    if (!pixd)
        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
    else
        return pixd;
}
 
 
/*----------------------------------------------------------------------*
 *                           Sauvola binarization                       *
 *----------------------------------------------------------------------*/
l_ok
pixSauvolaBinarizeTiled(PIX       *pixs,
                        l_int32    whsize,
                        l_float32  factor,
                        l_int32    nx,
                        l_int32    ny,
                        PIX      **ppixth,
                        PIX      **ppixd)
{
l_int32     i, j, w, h, xrat, yrat;
PIX        *pixth = NULL, *pixd = NULL, *tileth = NULL, *tiled = NULL, *pixt;
PIX       **ptileth, **ptiled;
PIXTILING  *pt;
 
    if (!ppixth && !ppixd)
        return ERROR_INT("no outputs", __func__, 1);
    if (ppixth) *ppixth = NULL;
    if (ppixd) *ppixd = NULL;
    if (!pixs || pixGetDepth(pixs) != 8)
        return ERROR_INT("pixs undefined or not 8 bpp", __func__, 1);
    if (pixGetColormap(pixs))
        return ERROR_INT("pixs is cmapped", __func__, 1);
    pixGetDimensions(pixs, &w, &h, NULL);
    if (whsize < 2)
        return ERROR_INT("whsize must be >= 2", __func__, 1);
    if (w < 2 * whsize + 3 || h < 2 * whsize + 3)
        return ERROR_INT("whsize too large for image", __func__, 1);
    if (factor < 0.0)
        return ERROR_INT("factor must be >= 0", __func__, 1);
 
    if (nx <= 1 && ny <= 1)
        return pixSauvolaBinarize(pixs, whsize, factor, 1, NULL, NULL,
                                  ppixth, ppixd);
 
        /* Test to see if the tiles are too small.  The required
         * condition is that the tile dimensions must be at least
         * (whsize + 2) x (whsize + 2).  */
    xrat = w / nx;
    yrat = h / ny;
    if (xrat < whsize + 2) {
        nx = w / (whsize + 2);
        L_WARNING("tile width too small; nx reduced to %d\n", __func__, nx);
    }
    if (yrat < whsize + 2) {
        ny = h / (whsize + 2);
        L_WARNING("tile height too small; ny reduced to %d\n", __func__, ny);
    }
    if (nx <= 1 && ny <= 1)
        return pixSauvolaBinarize(pixs, whsize, factor, 1, NULL, NULL,
                                  ppixth, ppixd);
 
        /* We can use pixtiling for painting both outputs, if requested */
    if (ppixth) {
        pixth = pixCreate(w, h, 8);
        *ppixth = pixth;
    }
    if (ppixd) {
        pixd = pixCreate(w, h, 1);
        *ppixd = pixd;
    }
    pt = pixTilingCreate(pixs, nx, ny, 0, 0, whsize + 1, whsize + 1);
    pixTilingNoStripOnPaint(pt);  /* pixSauvolaBinarize() does the stripping */
 
    for (i = 0; i < ny; i++) {
        for (j = 0; j < nx; j++) {
            pixt = pixTilingGetTile(pt, i, j);
            ptileth = (ppixth) ? &tileth : NULL;
            ptiled = (ppixd) ? &tiled : NULL;
            pixSauvolaBinarize(pixt, whsize, factor, 0, NULL, NULL,
                               ptileth, ptiled);
            if (ppixth) {  /* do not strip */
                pixTilingPaintTile(pixth, i, j, tileth, pt);
                pixDestroy(&tileth);
            }
            if (ppixd) {
                pixTilingPaintTile(pixd, i, j, tiled, pt);
                pixDestroy(&tiled);
            }
            pixDestroy(&pixt);
        }
    }
 
    pixTilingDestroy(&pt);
    return 0;
}
 
 
l_ok
pixSauvolaBinarize(PIX       *pixs,
                   l_int32    whsize,
                   l_float32  factor,
                   l_int32    addborder,
                   PIX      **ppixm,
                   PIX      **ppixsd,
                   PIX      **ppixth,
                   PIX      **ppixd)
{
l_int32  w, h;
PIX     *pixg, *pixsc, *pixm = NULL, *pixms = NULL, *pixth = NULL, *pixd = NULL;
 
    if (ppixm) *ppixm = NULL;
    if (ppixsd) *ppixsd = NULL;
    if (ppixth) *ppixth = NULL;
    if (ppixd) *ppixd = NULL;
    if (!ppixm && !ppixsd && !ppixth && !ppixd)
        return ERROR_INT("no outputs", __func__, 1);
    if (!pixs || pixGetDepth(pixs) != 8)
        return ERROR_INT("pixs undefined or not 8 bpp", __func__, 1);
    if (pixGetColormap(pixs))
        return ERROR_INT("pixs is cmapped", __func__, 1);
    pixGetDimensions(pixs, &w, &h, NULL);
    if (whsize < 2)
        return ERROR_INT("whsize must be >= 2", __func__, 1);
    if (w < 2 * whsize + 3 || h < 2 * whsize + 3)
        return ERROR_INT("whsize too large for image", __func__, 1);
    if (factor < 0.0)
        return ERROR_INT("factor must be >= 0", __func__, 1);
 
    if (addborder) {
        pixg = pixAddMirroredBorder(pixs, whsize + 1, whsize + 1,
                                    whsize + 1, whsize + 1);
        pixsc = pixClone(pixs);
    } else {
        pixg = pixClone(pixs);
        pixsc = pixRemoveBorder(pixs, whsize + 1);
    }
    if (!pixg || !pixsc)
        return ERROR_INT("pixg and pixsc not made", __func__, 1);
 
        /* All these functions strip off the border pixels. */
    if (ppixm || ppixth || ppixd)
        pixm = pixWindowedMean(pixg, whsize, whsize, 1, 1);
    if (ppixsd || ppixth || ppixd)
        pixms = pixWindowedMeanSquare(pixg, whsize, whsize, 1);
    if (ppixth || ppixd)
        pixth = pixSauvolaGetThreshold(pixm, pixms, factor, ppixsd);
    if (ppixd) {
        pixd = pixApplyLocalThreshold(pixsc, pixth);
        pixCopyResolution(pixd, pixs);
    }
 
    if (ppixm)
        *ppixm = pixm;
    else
        pixDestroy(&pixm);
    pixDestroy(&pixms);
    if (ppixth)
        *ppixth = pixth;
    else
        pixDestroy(&pixth);
    if (ppixd)
        *ppixd = pixd;
    pixDestroy(&pixg);
    pixDestroy(&pixsc);
    return 0;
}
 
 
static PIX *
pixSauvolaGetThreshold(PIX       *pixm,
                       PIX       *pixms,
                       l_float32  factor,
                       PIX      **ppixsd)
{
l_int32     i, j, w, h, tabsize, wplm, wplms, wplsd, wpld, usetab;
l_int32     mv, ms, var, thresh;
l_uint32   *datam, *datams, *datasd = NULL, *datad;
l_uint32   *linem, *linems, *linesd = NULL, *lined;
l_float32   sd;
l_float32  *tab = NULL;  /* of 2^16 square roots */
PIX        *pixsd = NULL, *pixd = NULL;
 
    if (ppixsd) *ppixsd = NULL;
    if (!pixm || pixGetDepth(pixm) != 8)
        return (PIX *)ERROR_PTR("pixm undefined or not 8 bpp", __func__, NULL);
    if (pixGetColormap(pixm))
        return (PIX *)ERROR_PTR("pixm is colormapped", __func__, NULL);
    if (!pixms || pixGetDepth(pixms) != 32)
        return (PIX *)ERROR_PTR("pixms undefined or not 32 bpp",
                                __func__, NULL);
    if (factor < 0.0)
        return (PIX *)ERROR_PTR("factor must be >= 0", __func__, NULL);
 
        /* Only make a table of 2^16 square roots if there
         * are enough pixels to justify it. */
    pixGetDimensions(pixm, &w, &h, NULL);
    usetab = (w * h > 100000) ? 1 : 0;
    if (usetab) {
        tabsize = 1 << 16;
        tab = (l_float32 *)LEPT_CALLOC(tabsize, sizeof(l_float32));
        for (i = 0; i < tabsize; i++)
            tab[i] = sqrtf((l_float32)i);
    }
 
    pixd = pixCreate(w, h, 8);
    if (ppixsd) {
        pixsd = pixCreate(w, h, 8);
        *ppixsd = pixsd;
    }
    datam = pixGetData(pixm);
    datams = pixGetData(pixms);
    if (ppixsd) datasd = pixGetData(pixsd);
    datad = pixGetData(pixd);
    wplm = pixGetWpl(pixm);
    wplms = pixGetWpl(pixms);
    if (ppixsd) wplsd = pixGetWpl(pixsd);
    wpld = pixGetWpl(pixd);
    for (i = 0; i < h; i++) {
        linem = datam + i * wplm;
        linems = datams + i * wplms;
        if (ppixsd) linesd = datasd + i * wplsd;
        lined = datad + i * wpld;
        for (j = 0; j < w; j++) {
            mv = GET_DATA_BYTE(linem, j);
            ms = linems[j];
            var = ms - mv * mv;
            if (usetab)
                sd = tab[var];
            else
                sd = sqrtf((l_float32)var);
            if (ppixsd) SET_DATA_BYTE(linesd, j, (l_int32)sd);
            thresh = (l_int32)(mv * (1.0 - factor * (1.0 - sd / 128.)));
            SET_DATA_BYTE(lined, j, thresh);
        }
    }
 
    if (usetab) LEPT_FREE(tab);
    return pixd;
}
 
 
static PIX *
pixApplyLocalThreshold(PIX     *pixs,
                       PIX     *pixth)
{
l_int32    i, j, w, h, wpls, wplt, wpld, vals, valt;
l_uint32  *datas, *datat, *datad, *lines, *linet, *lined;
PIX       *pixd;
 
    if (!pixs || pixGetDepth(pixs) != 8)
        return (PIX *)ERROR_PTR("pixs undefined or not 8 bpp", __func__, NULL);
    if (pixGetColormap(pixs))
        return (PIX *)ERROR_PTR("pixs is colormapped", __func__, NULL);
    if (!pixth || pixGetDepth(pixth) != 8)
        return (PIX *)ERROR_PTR("pixth undefined or not 8 bpp", __func__, NULL);
 
    pixGetDimensions(pixs, &w, &h, NULL);
    pixd = pixCreate(w, h, 1);
    datas = pixGetData(pixs);
    datat = pixGetData(pixth);
    datad = pixGetData(pixd);
    wpls = pixGetWpl(pixs);
    wplt = pixGetWpl(pixth);
    wpld = pixGetWpl(pixd);
    for (i = 0; i < h; i++) {
        lines = datas + i * wpls;
        linet = datat + i * wplt;
        lined = datad + i * wpld;
        for (j = 0; j < w; j++) {
            vals = GET_DATA_BYTE(lines, j);
            valt = GET_DATA_BYTE(linet, j);
            if (vals < valt)
                SET_DATA_BIT(lined, j);
        }
    }
 
    return pixd;
}
 
 
/*----------------------------------------------------------------------*
 *      Contrast normalization followed by Sauvola binarization         *
 *----------------------------------------------------------------------*/
PIX  *
pixSauvolaOnContrastNorm(PIX     *pixs,
                         l_int32  mindiff,
                         PIX    **ppixn,
                         PIX    **ppixth)
{
l_int32  w, h, d, nx, ny;
PIX     *pixg, *pix1, *pixd;
 
    if (ppixn) *ppixn = NULL;
    if (ppixth) *ppixth = NULL;
    if (!pixs || (d = pixGetDepth(pixs)) < 8)
        return (PIX *)ERROR_PTR("pixs undefined or d < 8 bpp", __func__, NULL);
    if (d == 32)
        pixg = pixConvertRGBToGray(pixs, 0.3f, 0.4f, 0.3f);
    else
        pixg = pixConvertTo8(pixs, 0);
 
    pix1 = pixContrastNorm(NULL, pixg, 50, 50, mindiff, 2, 2);
 
        /* Use tiles of size approximately 250 x 250 */
    pixGetDimensions(pix1, &w, &h, NULL);
    nx = L_MAX(1, (w + 125) / 250);
    ny = L_MAX(1, (h + 125) / 250);
    pixSauvolaBinarizeTiled(pix1, 25, 0.40f, nx, ny, ppixth, &pixd);
    pixDestroy(&pixg);
    if (ppixn)
        *ppixn = pix1;
    else
        pixDestroy(&pix1);
    return pixd;
}
 
 
/*----------------------------------------------------------------------*
 *      Contrast normalization followed by background normalization     *
 *                            and thresholding                          *
 *----------------------------------------------------------------------*/
PIX  *
pixThreshOnDoubleNorm(PIX     *pixs,
                      l_int32  mindiff)
{
l_int32    d, ival;
l_uint32   val;
PIX       *pixg, *pix1, *pixd;
 
    if (!pixs || (d = pixGetDepth(pixs)) < 8)
        return (PIX *)ERROR_PTR("pixs undefined or d < 8 bpp", __func__, NULL);
    if (d == 32)
        pixg = pixConvertRGBToGray(pixs, 0.3f, 0.4f, 0.3f);
    else
        pixg = pixConvertTo8(pixs, 0);
 
        /* Use the entire image for the estimate; pix1 is 1x1 */
    pixOtsuAdaptiveThreshold(pixg, 5000, 5000, 0, 0, 0.1f, &pix1, NULL);
    pixGetPixel(pix1, 0, 0, &val);
    ival = (l_int32)val;
    ival = L_MIN(ival, 110);
    pixDestroy(&pix1);
 
        /* Double normalization */
    pixContrastNorm(pixg, pixg, 50, 50, mindiff, 2, 2);
    pix1 = pixBackgroundNormSimple(pixg, NULL, NULL);
    pixDestroy(&pixg);
 
/*    lept_stderr("ival = %d\n", ival); */
    pixd = pixThresholdToBinary(pix1, ival);
    pixDestroy(&pix1);
    return pixd;
}
 
 
/*----------------------------------------------------------------------*
 *            Global thresholding using connected components            *
 *----------------------------------------------------------------------*/
l_ok
pixThresholdByConnComp(PIX       *pixs,
                       PIX       *pixm,
                       l_int32    start,
                       l_int32    end,
                       l_int32    incr,
                       l_float32  thresh48,
                       l_float32  threshdiff,
                       l_int32   *pglobthresh,
                       PIX      **ppixd,
                       l_int32    debugflag)
{
l_int32    i, thresh, n, n4, n8, mincounts, found, globthresh;
l_float32  count4, count8, firstcount4, prevcount4, diff48, diff4;
GPLOT     *gplot;
NUMA      *na4, *na8;
PIX       *pix1, *pix2, *pix3;
 
    if (pglobthresh) *pglobthresh = 0;
    if (ppixd) *ppixd = NULL;
    if (!pixs || pixGetDepth(pixs) == 1)
        return ERROR_INT("pixs undefined or 1 bpp", __func__, 1);
    if (pixm && pixGetDepth(pixm) != 1)
        return ERROR_INT("pixm must be 1 bpp", __func__, 1);
 
        /* Assign default values if requested */
    if (start <= 0) start = 80;
    if (end <= 0) end = 200;
    if (incr <= 0) incr = 10;
    if (thresh48 <= 0.0) thresh48 = 0.01f;
    if (threshdiff <= 0.0) threshdiff = 0.01f;
    if (start > end)
        return ERROR_INT("invalid start,end", __func__, 1);
 
        /* Make 8 bpp, using the max component if color. */
    if (pixGetColormap(pixs))
        pix1 = pixRemoveColormap(pixs, REMOVE_CMAP_BASED_ON_SRC);
    else
        pix1 = pixClone(pixs);
    if (pixGetDepth(pix1) == 32)
        pix2 = pixConvertRGBToGrayMinMax(pix1, L_CHOOSE_MAX);
    else
        pix2 = pixConvertTo8(pix1, 0);
    pixDestroy(&pix1);
 
        /* Mask out any non-text regions.  Do this in-place, because pix2
         * can never be the same pix as pixs. */
    if (pixm)
        pixSetMasked(pix2, pixm, 255);
 
        /* Make sure there are enough components to get a valid signal */
    pix3 = pixConvertTo1(pix2, start);
    pixCountConnComp(pix3, 4, &n4);
    pixDestroy(&pix3);
    mincounts = 500;
    if (n4 < mincounts) {
        L_INFO("Insufficient component count: %d\n", __func__, n4);
        pixDestroy(&pix2);
        return 1;
    }
 
        /* Compute the c.c. data */
    na4 = numaCreate(0);
    na8 = numaCreate(0);
    numaSetParameters(na4, start, incr);
    numaSetParameters(na8, start, incr);
    for (thresh = start, i = 0; thresh <= end; thresh += incr, i++) {
        pix3 = pixConvertTo1(pix2, thresh);
        pixCountConnComp(pix3, 4, &n4);
        pixCountConnComp(pix3, 8, &n8);
        numaAddNumber(na4, n4);
        numaAddNumber(na8, n8);
        pixDestroy(&pix3);
    }
    if (debugflag) {
        lept_mkdir("lept/binarize");
        gplot = gplotCreate("/tmp/lept/binarize", GPLOT_PNG,
                            "number of cc vs. threshold",
                            "threshold", "number of cc");
        gplotAddPlot(gplot, NULL, na4, GPLOT_LINES, "plot 4cc");
        gplotAddPlot(gplot, NULL, na8, GPLOT_LINES, "plot 8cc");
        gplotMakeOutput(gplot);
        gplotDestroy(&gplot);
    }
 
    n = numaGetCount(na4);
    found = FALSE;
    for (i = 0; i < n; i++) {
        if (i == 0) {
            numaGetFValue(na4, i, &firstcount4);
            prevcount4 = firstcount4;
        } else {
            numaGetFValue(na4, i, &count4);
            numaGetFValue(na8, i, &count8);
            diff48 = (count4 - count8) / firstcount4;
            diff4 = L_ABS(prevcount4 - count4) / firstcount4;
            if (debugflag) {
                lept_stderr("diff48 = %7.3f, diff4 = %7.3f\n",
                            diff48, diff4);
            }
            if (diff48 < thresh48 && diff4 < threshdiff) {
                found = TRUE;
                break;
            }
            prevcount4 = count4;
        }
    }
    numaDestroy(&na4);
    numaDestroy(&na8);
 
    if (found) {
        globthresh = start + i * incr;
        if (pglobthresh) *pglobthresh = globthresh;
        if (ppixd) {
            *ppixd = pixConvertTo1(pix2, globthresh);
            pixCopyResolution(*ppixd, pixs);
        }
        if (debugflag) lept_stderr("global threshold = %d\n", globthresh);
        pixDestroy(&pix2);
        return 0;
    }
 
    if (debugflag) lept_stderr("no global threshold found\n");
    pixDestroy(&pix2);
    return 1;
}
 
/*----------------------------------------------------------------------*
 *                   Global thresholding by histogram                   *
 *----------------------------------------------------------------------*/
l_ok
pixThresholdByHisto(PIX       *pixs,
                    l_int32    factor,
                    l_int32    halfw,
                    l_int32    skip,
                    l_int32   *pthresh,
                    PIX      **ppixd,
                    NUMA     **pnahisto,
                    PIX      **ppixhisto)
{
l_float32  maxval, fract;
NUMA      *na1, *na2, *na3;
 
    if (ppixd) *ppixd = NULL;
    if (pnahisto) *pnahisto = NULL;
    if (ppixhisto) *ppixhisto = NULL;
    if (!pthresh)
        return ERROR_INT("&thresh not defined", __func__, 1);
    *pthresh = 0;
    if (!pixs || pixGetDepth(pixs) != 8)
        return ERROR_INT("pixs undefined or not 8 bpp", __func__, 1);
    if (pixGetColormap(pixs))
        return ERROR_INT("pixs has colormap", __func__, 1);
    if (factor < 1)
        return ERROR_INT("sampling must be >= 1", __func__, 1);
    if (halfw <= 0) halfw = 20;
    if (skip <= 0) skip = 20;
 
        /* Make a histogram of pixel values where the largest peak
         * is normalized to a value of 1.0. */
    na1 = pixGetGrayHistogram(pixs, factor);
    na2 = numaWindowedMean(na1, halfw);  /* smoothing */
    numaGetMax(na2, &maxval, NULL);
    na3 = numaTransform(na2, 0.0, 1.0 / maxval);  /* rescale to max of 1.0 */
    numaDestroy(&na1);
    numaDestroy(&na2);
 
    if (numaFindLocForThreshold(na3, skip, pthresh, &fract) == 1) {
        numaDestroy(&na3);
        return ERROR_INT("failure to find threshold", __func__, 1);
    }
    L_INFO("fractional area under first peak: %5.3f\n", __func__, fract);
 
    if (ppixhisto) {
        lept_mkdir("lept/histo");
        gplotSimple1(na3, GPLOT_PNG, "/tmp/lept/histo/histo", NULL);
        *ppixhisto = pixRead("/tmp/lept/histo/histo.png");
    }
    if (pnahisto)
        *pnahisto = na3;
    else
        numaDestroy(&na3);
    if (*pthresh > 0 && ppixd)
        *ppixd = pixThresholdToBinary(pixs, *pthresh);
    return 0;
}