Logo Search packages:      
Sourcecode: leptonlib version File versions  Download package

jbclass.c

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


/*
 * jbclass.c
 *
 *     These are functions for unsupervised classification of
 *     collections of connected components -- either characters or
 *     words -- in binary images.  They can be used as image
 *     processing steps in jbig2 compression.
 *
 *     Initialization
 *
 *         JbClasser  *jbRankHausInit()      [rank hausdorff encoder]
 *         JbClasser  *jbCorrelationInit()   [correlation encoder]
 *
 *     Classify the pages
 *
 *         l_int32     jbAddPages()
 *         l_int32     jbAddPage()
 *
 *     Rank hausdorff classifier
 *
 *         l_int32     jbClassifyRankHaus()
 *         l_int32     pixHaustest()
 *         l_int32     pixRankHaustest()
 *
 *     Binary correlation classifier
 *
 *         l_int32     jbClassifyCorrelation()
 *         l_float32   pixCorrelationScore()
 *
 *     Determine the image components we start with
 *
 *         l_int32     jbGetComponents()
 *
 *     Build grayscale composites (templates)
 *
 *         PIXA       *jbAccumulateComposites
 *         PIXA       *jbTemplatesFromComposites
 *
 *     Utility functions for Classer
 *
 *         JBCLASSER  *jbClasserCreate()
 *         void        jbClasserDestroy()
 *
 *     Utility functions for Data
 *
 *         JBDATA     *jbDataSave()
 *         void        jbDataDestroy()
 *         l_int32     jbDataWrite()
 *         JBDATA     *jbDataRead()
 *         PIXA       *jbDataRender()
 *         l_int32     jbGetULCorners()
 *         l_int32     jbGetLLCorners()
 *
 *     Static helpers
 *
 *         static NUMA    *findSimilarSizedTemplates()
 *         static l_int32  finalPositioningForAlignment()
 *
 *     Note: this is NOT an implementation of the JPEG jbig2
 *     proposed standard encoder, the specifications for which
 *     can be found at http://www.jpeg.org/jbigpt2.html.
 *     (See below for a full implementation.)
 *     It is an implementation of the lower-level part of an encoder that:
 *
 *        (1) identifies connected components that are going to be used
 *        (2) puts them in similarity classes (this is an unsupervised
 *            classifier), and
 *        (3) stores the result in a simple file format (2 files,
 *            one for templates and one for page/coordinate/template-index
 *            quartets).
 *
 *     An actual implementation of the official jbig2 encoder could
 *     start with parts (1) and (2), and would then compress the quartets
 *     according to the standards requirements (e.g., Huffman or
 *     arithmetic coding of coordinate differences and image templates).
 *
 *     The low-level part of the encoder provided here has the
 *     following useful features:
 *
 *         - It is accurate in the identification of templates
 *           and classes because it uses a windowed hausdorff
 *           distance metric.
 *         - It is accurate in the placement of the connected
 *           components, doing a two step process of first aligning
 *           the the centroids of the template with those of each instance,
 *           and then making a further correction of up to +- 1 pixel
 *           in each direction to best align the templates.
 *         - It is fast because it uses a morphologically based
 *           matching algorithm to implement the hausdorff criterion,
 *           and it selects the patterns that are possible matches
 *           based on their size.
 *
 *     We provide two different matching functions, one using Hausdorff
 *     distance and one using a simple image correlation.
 *     The Hausdorff method sometimes produces better results for the
 *     same number of classes, because it gives a relatively small
 *     effective weight to foreground pixels near the boundary,
 *     and a relatively  large weight to foreground pixels that are
 *     not near the boundary.  By effectively ignoring these boundary
 *     pixels, Hausdorff weighting corresponds better to the expected
 *     probabilities of the pixel values in a scanned image, where the
 *     variations in instances of the same printed character are much
 *     more likely to be in pixels near the boundary.  By contrast,
 *     the correlation method gives equal weight to all foreground pixels.
 *
 *     For best results, use the correlation method.  Correlation takes
 *     the number of fg pixels in the AND of instance and template,
 *     divided by the product of the number of fg pixels in instance
 *     and template.  It compares this with a threshold that, in
 *     general, depends on the fractional coverage of the template.
 *     For heavy text, the threshold is raised above that for light
 *     text,  By using both these parameters (basic threshold and
 *     adjustment factor for text weight), one has more flexibility
 *     and can arrive at the fewest substitution errors, although
 *     this comes at the price of more templates.
 *
 *     The strict Hausdorff scoring is not a rank weighting, because a
 *     single pixel beyond the given distance will cause a match
 *     failure.  A rank Hausdorff is more robust to non-boundary noise,
 *     but it is also more susceptible to confusing components that
 *     should be in different classes.  For implementing a jbig2
 *     application for visually lossless binary image compression,
 *     you have two choices:
 *
 *        (1) use a 3x3 structuring element (size = 3) and a strict
 *            Hausdorff comparison (rank = 1.0 in the rank Hausdorff
 *            function).  This will result in a minimal number of classes,
 *            but confusion of small characters, such as italic and
 *            non-italic lower-case 'o', can still occur.
 *        (2) use the correlation method with a threshold of 0.85
 *            and a weighting factor of about 0.7.  This will result in
 *            a larger number of classes, but should not be confused
 *            either by similar small characters or by extremely
 *            thick sans serif characters, such as in prog/cootoots.png.
 *
 *     As mentioned above, if visual substitution errors must be
 *     avoided, you should use the correlation method.
 *
 *     We provide executables that show how to do the encoding:
 *         prog/jbrankhaus.c
 *         prog/jbcorrelation.c
 *
 *     The basic flow for correlation classification goes as follows,
 *     where specific choices have been made for parameters (Hausdorff
 *     is the same except for initialization):
 *
 *             // Initialize and save data in the classer
 *         JBCLASSER *classer =
 *             jbCorrelationInit(JB_CONN_COMPS, 0, 0, 0.8, 0.7);
 *         SARRAY *safiles = getSortedPathnamesInDirectory(directory, 0, 0);
 *         jbAddPages(classer, safiles);
 *
 *             // Save the data in a data structure for serialization,
 *             // and write it into two files.
 *         JBDATA *data = jbDataSave(classer);
 *         jbDataWrite(rootname, data);
 *
 *             // Reconstruct (render) the pages from the encoded data.
 *         PIXA *pixa = jbDataRender(data, FALSE);
 *
 *     Adam Langley has recently built a jbig2 standards-compliant
 *     encoder, the first one to appear in open source.  You can get
 *     this encoder at:
 *
 *          http://www.imperialviolet.org/jbig2.html
 *
 *     It uses arithmetic encoding throughout.  It encodes binary images
 *     losslessly with a single arithmetic coding over the full image.
 *     It also does both lossy and lossless encoding from connected
 *     components, using leptonica to generate the templates representing
 *     each cluster.
 */

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

#ifndef  NO_CONSOLE_IO
#endif  /* ~NO_CONSOLE_IO */


static const l_int32  BUF_SIZE = 512;

    /* For jbClassifyRankHaus(): size of border added around
     * pix of each c.c., to allow further processing.  This
     * should be at least the sum of the MAX_DIFF_HEIGHT
     * (or MAX_DIFF_WIDTH) and one-half the size of the Sel  */
static const l_int32  JB_ADDED_PIXELS = 6;

    /* For pixHaustest(); choose these to be 2 or greater */
static const l_int32  MAX_DIFF_HEIGHT = 2;  /* use at least 2 */
static const l_int32  MAX_DIFF_WIDTH = 2;  /* use at least 2 */

    /* In initialization, you have the option to discard components
     * (cc, characters or words) that have either width or height larger
     * than a given size.  This is convenient for jbDataSave(), because
     * the components are placed onto a regular lattice with cell
     * dimension equal to the maximum component size.  The default
     * values are given here.  If you want to save all components,
     * use a sufficiently large set of dimensions. */
static const l_int32  MAX_CONN_COMP_WIDTH = 350;  /* default max cc width */
static const l_int32  MAX_CHAR_COMP_WIDTH = 350;  /* default max char width */
static const l_int32  MAX_WORD_COMP_WIDTH = 1000;  /* default max word width */
static const l_int32  MAX_COMP_HEIGHT = 120;  /* default max component height */

    /* static helper functions */
static NUMA *
findSimilarSizedTemplates(JBCLASSER *classer, PIX *pixs);

static l_int32
finalPositioningForAlignment(PIX *pixs, l_int32 x, l_int32 y,
                             l_int32 idelx, l_int32 idely, PIX *pixt,
                             l_int32 *sumtab, l_int32 *pdx, l_int32 *pdy);



/*----------------------------------------------------------------------*
 *                            Initialization                            *
 *----------------------------------------------------------------------*/
/*!
 *  jbRankHausInit()
 *
 *      Input:  components (JB_CONN_COMPS, JB_CHARACTERS, JB_WORDS)
 *              maxwidth (of component; use 0 for default)
 *              maxheight (of component; use 0 for default)
 *              size  (of square structuring element; 3, representing
 *                     3x3 sel, is best for accuracy without
 *                     undue class expansion)
 *              rank (rank val of match, each way; in [0.5 - 1.0])
 *      Return: jbclasser if OK; NULL on error
 */
JBCLASSER *
jbRankHausInit(l_int32    components,
               l_int32    maxwidth,
               l_int32    maxheight,
               l_int32    size,
               l_float32  rank)
{
JBCLASSER  *classer;

    PROCNAME("jbRankHausInit");

    if (components != JB_CONN_COMPS && components != JB_CHARACTERS &&
        components != JB_WORDS)
      return (JBCLASSER *)ERROR_PTR("invalid components", procName, NULL);
    if (size < 1 || size > 10)
      return (JBCLASSER *)ERROR_PTR("size not reasonable", procName, NULL);
    if (rank < 0.5 || rank > 1.0)
      return (JBCLASSER *)ERROR_PTR("rank not in [0.5-1.0]", procName, NULL);
    if (maxwidth == 0) {
        if (components == JB_CONN_COMPS)
          maxwidth = MAX_CONN_COMP_WIDTH;
        else if (components == JB_CHARACTERS)
          maxwidth = MAX_CHAR_COMP_WIDTH;
        else  /* JB_WORDS */
          maxwidth = MAX_WORD_COMP_WIDTH;
    }
    if (maxheight == 0)
      maxheight = MAX_COMP_HEIGHT;

    if ((classer = jbClasserCreate(JB_RANKHAUS, components)) == NULL)
      return (JBCLASSER *)ERROR_PTR("classer not made", procName, NULL);
    classer->maxwidth = maxwidth;
    classer->maxheight = maxheight;
    classer->sizehaus = size;
    classer->rankhaus = rank;
    classer->nahash = numaHashCreate(5507, 4);  /* 5507 is prime */
    return classer;
}


/*!
 *  jbCorrelationInit()
 *
 *      Input:  components (JB_CONN_COMPS, JB_CHARACTERS, JB_WORDS)
 *              maxwidth (of component; use 0 for default)
 *              maxheight (of component; use 0 for default)
 *              thresh (value for correlation score: in [0.4 - 0.9])
 *              weightfactor (corrects thresh for thick characters [0.0 - 1.0])
 *      Return: jbclasser if OK; NULL on error
 */
JBCLASSER *
jbCorrelationInit(l_int32    components,
                  l_int32    maxwidth,
                  l_int32    maxheight,
                  l_float32  thresh,
                  l_float32  weightfactor)
{
JBCLASSER  *classer;

    PROCNAME("jbCorrelationInit");

    if (components != JB_CONN_COMPS && components != JB_CHARACTERS &&
        components != JB_WORDS)
      return (JBCLASSER *)ERROR_PTR("invalid components", procName, NULL);
    if (thresh < 0.4 || thresh > 0.9)
      return (JBCLASSER *)ERROR_PTR("thresh not in range [0.4 - 0.9]",
              procName, NULL);
    if (weightfactor < 0.0 || weightfactor > 1.0)
      return (JBCLASSER *)ERROR_PTR("weightfactor not in range [0.0 - 1.0]",
              procName, NULL);
    if (maxwidth == 0) {
        if (components == JB_CONN_COMPS)
          maxwidth = MAX_CONN_COMP_WIDTH;
        else if (components == JB_CHARACTERS)
          maxwidth = MAX_CHAR_COMP_WIDTH;
        else  /* JB_WORDS */
          maxwidth = MAX_WORD_COMP_WIDTH;
    }
    if (maxheight == 0)
      maxheight = MAX_COMP_HEIGHT;


    if ((classer = jbClasserCreate(JB_CORRELATION, components)) == NULL)
      return (JBCLASSER *)ERROR_PTR("classer not made", procName, NULL);
    classer->maxwidth = maxwidth;
    classer->maxheight = maxheight;
    classer->thresh = thresh;
    classer->weightfactor = weightfactor;
    classer->nahash = numaHashCreate(5507, 4);  /* 5507 is prime */
    return classer;
}



/*----------------------------------------------------------------------*
 *                       Classify the pages                             *
 *----------------------------------------------------------------------*/
/*!
 *  jbAddPages()
 *
 *      Input:  jbclasser
 *              safiles (of page image file names)
 *      Return: 0 if OK; 1 on error
 *
 *  Note:
 *      (1) jbclasser makes a copy of the array of file names.
 *      (2) The caller is still responsible for destroying the input array.
 */
l_int32
jbAddPages(JBCLASSER  *classer,
           SARRAY     *safiles)
{
l_int32  i, nfiles;
char    *fname;
PIX     *pix;

    PROCNAME("jbAddPages");

    if (!classer)
      return ERROR_INT("classer not defined", procName, 1);
    if (!safiles)
      return ERROR_INT("safiles not defined", procName, 1);

    classer->safiles = sarrayCopy(safiles);
    nfiles = sarrayGetCount(safiles);
    for (i = 0; i < nfiles; i++) {
      fname = sarrayGetString(safiles, i, 0);
      if ((pix = pixRead(fname)) == NULL) {
          L_WARNING_INT("image file %d not read", procName, i);
          continue;
      }
      jbAddPage(classer, pix);
      pixDestroy(&pix);
    }

    return 0;
}


/*!
 *  jbAddPage()
 *
 *      Input:  jbclasser
 *              pixs (of input page)
 *      Return: 0 if OK; 1 on error
 */
l_int32
jbAddPage(JBCLASSER  *classer,
          PIX        *pixs)
{
l_int32  n;
BOXA    *boxas;
PIXA    *pixas;

    PROCNAME("jbAddPage");

    if (!classer)
      return ERROR_INT("classer not defined", procName, 1);
    if (!pixs)
      return ERROR_INT("pix not defined", procName, 1);

    pixDestroy(&classer->pixs);   /* previous page, if it exists */
    classer->pixs = pixClone(pixs);
    classer->w = pixGetWidth(pixs);
    classer->h = pixGetHeight(pixs);

      /* Get the appropriate components and their bounding boxes */
    if (jbGetComponents(pixs, classer->components, classer->maxwidth,
                        classer->maxheight, &boxas, &pixas))
      return ERROR_INT("components not made", procName, 1);

        /* Save these current components */
    boxaDestroy(&classer->boxas);  /* from previous page, if it exists */
    classer->boxas = boxas;
    pixaDestroy(&classer->pixas);  /* from previous page, if it exists */
    classer->pixas = pixas;

        /* Test for no components on the current page */
    if (boxaGetCount(boxas) == 0) {
      classer->npages++;
      return 0;
    }

      /* Get classes.  For hausdorff, it uses a specified size of
         * structuring element and specified rank.  For correlation,
         * it uses a specified threshold. */
    if (classer->method == JB_RANKHAUS) {
        if (jbClassifyRankHaus(classer, boxas, pixas))
            return ERROR_INT("rankhaus classification failed", procName, 1);
    }
    else {  /* classer->method == JB_CORRELATION */
        if (jbClassifyCorrelation(classer, boxas, pixas))
            return ERROR_INT("correlation classification failed", procName, 1);
    }

      /* Find the global UL corners, adjusted for each instance so
       * that the class template and instance will have their
       * centroids in the same place.  Then the template can be
       * used to replace the instance. */
    if (jbGetULCorners(classer, boxas))
      return ERROR_INT("UL corners not found", procName, 1);

        /* Update total component counts and number of pages processed */
    n = boxaGetCount(boxas);
    classer->baseindex += n;
    numaAddNumber(classer->nacomps, n);
    classer->npages++;

    return 0;
}


/*----------------------------------------------------------------------*
 *         Classification using windowed rank hausdorff metric          *
 *----------------------------------------------------------------------*/
/*!
 *  jbClassifyRankHaus()
 *
 *      Input:  jbclasser
 *              boxa (of new components for classification)
 *              pixas (of new components for classification)
 *      Return: 0 if OK; 1 on error
 */
l_int32
jbClassifyRankHaus(JBCLASSER  *classer,
                   BOXA       *boxa,
                   PIXA       *pixas)
{
l_int32    n, ns, nt, i, j, wt, ht, iclass, size, found, testval;
l_int32   *sumtab;
l_int32    npages, area1, area3;
l_int32   *tab8;
l_float32  rank, x1, y1, x2, y2;
BOX       *box;
NUMA      *naclass, *napage;
NUMA      *nafg;   /* fg area of all instances */
NUMA      *nafgt;  /* fg area of all templates */
NUMA      *nalist;  /* indices of templates similar in size to instance */
NUMAHASH  *nahash;
PIX       *pix, *pix1, *pix2, *pix3, *pix4;
PIXA      *pixa, *pixa1, *pixa2, *pixat, *pixatd;
PIXAA     *pixaa;
PTA       *pta, *ptac, *ptact;
SEL       *sel;

    PROCNAME("jbClassifyRankHaus");

    if (!classer)
      return ERROR_INT("classer not found", procName, 1);
    if (!boxa)
      return ERROR_INT("boxa not found", procName, 1);
    if (!pixas)
      return ERROR_INT("pixas not found", procName, 1);

    npages = classer->npages;
    size = classer->sizehaus;
    sel = selCreateBrick(size, size, size / 2, size / 2, SEL_HIT);

      /* Generate the bordered pixa, with and without dilation.
       * pixa1 and pixa2 contain all the input components. */
    n = pixaGetCount(pixas);
    pixa1 = pixaCreate(n);
    pixa2 = pixaCreate(n);
    for (i = 0; i < n; i++) {
      pix = pixaGetPix(pixas, i, L_CLONE);
      pix1 = pixAddBorderGeneral(pix, JB_ADDED_PIXELS, JB_ADDED_PIXELS,
                  JB_ADDED_PIXELS, JB_ADDED_PIXELS, 0);
      pix2 = pixDilate(NULL, pix1, sel);
      pixaAddPix(pixa1, pix1, L_INSERT);   /* un-dilated */
      pixaAddPix(pixa2, pix2, L_INSERT);   /* dilated */
      pixDestroy(&pix);
    }

      /* Get the centroids of all the bordered images.
       * These are relative to the UL corner of each (bordered) pix.  */
    pta = pixaCentroids(pixa1);  /* centroids for this page; use here */
    ptac = classer->ptac;  /* holds centroids of components up to this page */
    ptaJoin(ptac, pta, 0, 0);  /* save centroids of all components */
    ptact = classer->ptact;  /* holds centroids of templates */
      
      /* Use these to save the class and page of each component. */
    naclass = classer->naclass;
    napage = classer->napage;
    sumtab = makePixelSumTab8();

      /* Store the unbordered pix in a pixaa, in a hierarchical
       * set of arrays.  There is one pixa for each class,
       * and the pix in each pixa are all the instances found
       * of that class.  This is actually more than one would need
       * for a jbig2 encoder, but there are two reasons to keep
       * them around: (1) the set of instances for each class
       * can be used to make an improved binary (or, better,
       * a grayscale) template, rather than simply using the first
       * one in the set; (2) we can investigate the failures
       * of the classifier.  This pixaa grows as we process
       * successive pages. */
    pixaa = classer->pixaa;

      /* arrays to store class exemplars (templates) */
    pixat = classer->pixat;   /* un-dilated */
    pixatd = classer->pixatd;   /* dilated */

      /* Fill up the pixaa tree with the template exemplars as
       * the first pix in each pixa.  As we add each pix,
       * we also add the associated box to the pixa.
       * We also keep track of the centroid of each pix,
       * and use the difference between centroids (of the
       * pix with the exemplar we are checking it with)
       * to align the two when checking that the Hausdorff
       * distance does not exceed a threshold.
       * The threshold is set by the Sel used for dilating.
       * For example, a 3x3 brick, sel_3, corresponds to a
       * Hausdorff distance of 1.  In general, for an NxN brick,
       * with N odd, corresponds to a Hausdorff distance of (N - 1)/2.
       * We can't reasonably expect to use a smaller size than 3x3.
       * The larger the Sel you use, the fewer the number of classes,
       * and the greater the likelihood of putting semantically
       * different objects in the same class.  For simplicity,
       * we do this separately for the case of rank == 1.0 (exact
       * match within the Hausdorff distance) and rank < 1.0.  */
    rank = classer->rankhaus;
    nahash = classer->nahash;
    if (rank == 1.0) {
      for (i = 0; i < n; i++) {
          pix1 = pixaGetPix(pixa1, i, L_CLONE);
          pix2 = pixaGetPix(pixa2, i, L_CLONE);
          ptaGetPt(pta, i, &x1, &y1); 
            nt = pixaGetCount(pixat);  /* number of templates */
          found = FALSE;
            nalist = findSimilarSizedTemplates(classer, pix1);
            ns = numaGetCount(nalist);
          for (j = 0; j < ns; j++) {  /* search through templates */
                  /* Select the template */
                numaGetIValue(nalist, j, &iclass);

                /* Find score for this template */
            pix3 = pixaGetPix(pixat, iclass, L_CLONE);
            pix4 = pixaGetPix(pixatd, iclass, L_CLONE);
            ptaGetPt(ptact, iclass, &x2, &y2);
            testval = pixHaustest(pix1, pix2, pix3, pix4, x1 - x2, y1 - y2);
            pixDestroy(&pix3);
            pixDestroy(&pix4);
            if (testval == 1) {
                found = TRUE;
                numaAddNumber(naclass, iclass);
                numaAddNumber(napage, npages);
                pixa = pixaaGetPixa(pixaa, iclass, L_CLONE);
                pix = pixaGetPix(pixas, i, L_CLONE);
                pixaAddPix(pixa, pix, L_INSERT);
                box = boxaGetBox(boxa, i, L_CLONE);
                pixaAddBox(pixa, box, L_INSERT);
                pixaDestroy(&pixa);
                break;
            }
          }
          numaDestroy(&nalist);
          if (found == FALSE) {  /* new class */
            numaAddNumber(naclass, nt);
            numaAddNumber(napage, npages);
            pixa = pixaCreate(0);
            pix = pixaGetPix(pixas, i, L_CLONE);  /* unbordered instance */
            pixaAddPix(pixa, pix, L_INSERT);
            wt = pixGetWidth(pix);
              ht = pixGetHeight(pix);
                numaHashAdd(nahash, ht * wt, nt);
            box = boxaGetBox(boxa, i, L_CLONE);
            pixaAddBox(pixa, box, L_INSERT);
            pixaaAddPixa(pixaa, pixa, L_INSERT);  /* unbordered instance */
            ptaAddPt(ptact, x1, y1);
            pixaAddPix(pixat, pix1, L_INSERT);  /* bordered template */
            pixaAddPix(pixatd, pix2, L_INSERT);  /* bordered dil template */
          }
          else {   /* don't save them */
            pixDestroy(&pix1);
            pixDestroy(&pix2);
          }
      }
    }
    else {  /* rank < 1.0 */
      if ((nafg = pixaCountPixels(pixas)) == NULL)  /* areas for this page */
          return ERROR_INT("nafg not made", procName, 1);
      nafgt = classer->nafgt;
      tab8 = makePixelSumTab8();
      for (i = 0; i < n; i++) {   /* all instances on this page */
          pix1 = pixaGetPix(pixa1, i, L_CLONE);
          numaGetIValue(nafg, i, &area1);
          pix2 = pixaGetPix(pixa2, i, L_CLONE);
          ptaGetPt(pta, i, &x1, &y1);   /* use pta for this page */
          nt = pixaGetCount(pixat);  /* number of templates */
          found = FALSE;
            nalist = findSimilarSizedTemplates(classer, pix1);
            ns = numaGetCount(nalist);
          for (j = 0; j < ns; j++) {   /* search through templates */
                  /* Select the template */
                numaGetIValue(nalist, j, &iclass);

                /* Find score for this template */
            pix3 = pixaGetPix(pixat, iclass, L_CLONE);
            numaGetIValue(nafgt, iclass, &area3);
            pix4 = pixaGetPix(pixatd, iclass, L_CLONE);
            ptaGetPt(ptact, iclass, &x2, &y2);
            testval = pixRankHaustest(pix1, pix2, pix3, pix4,
                                x1 - x2, y1 - y2,
                                area1, area3, rank, tab8);
            pixDestroy(&pix3);
            pixDestroy(&pix4);
            if (testval == 1) {  /* greedy match; take the first */
                found = TRUE;
                numaAddNumber(naclass, iclass);
                numaAddNumber(napage, npages);
                pixa = pixaaGetPixa(pixaa, iclass, L_CLONE);
                pix = pixaGetPix(pixas, i, L_CLONE);
                pixaAddPix(pixa, pix, L_INSERT);
                box = boxaGetBox(boxa, i, L_CLONE);
                pixaAddBox(pixa, box, L_INSERT);
                pixaDestroy(&pixa);
                break;
            }
          }
          numaDestroy(&nalist);
          if (found == FALSE) {  /* new class */
            numaAddNumber(naclass, nt);
            numaAddNumber(napage, npages);
            pixa = pixaCreate(0);
            pix = pixaGetPix(pixas, i, L_CLONE);  /* unbordered instance */
            pixaAddPix(pixa, pix, L_INSERT);
                wt = pixGetWidth(pix);
                ht = pixGetHeight(pix);
                numaHashAdd(nahash, ht * wt, nt);
            box = boxaGetBox(boxa, i, L_CLONE);
            pixaAddBox(pixa, box, L_INSERT);
            pixaaAddPixa(pixaa, pixa, L_INSERT);  /* unbordered instance */
            ptaAddPt(ptact, x1, y1);
            pixaAddPix(pixat, pix1, L_INSERT);  /* bordered template */
            pixaAddPix(pixatd, pix2, L_INSERT);  /* ditto */
            numaAddNumber(nafgt, area1);
          }
          else {   /* don't save them */
            pixDestroy(&pix1);
            pixDestroy(&pix2);
          }
      }
      FREE((void *)tab8);
      numaDestroy(&nafg);
    }
    classer->nclass = pixaGetCount(pixat);

    FREE((void *)sumtab);
    ptaDestroy(&pta);
    pixaDestroy(&pixa1);
    pixaDestroy(&pixa2);
    selDestroy(&sel);
    return 0;
}



/*!
 *  pixHaustest()
 *
 *      Input:  pix1   (new pix, not dilated)
 *              pix2   (new pix, dilated)
 *              pix3   (exemplar pix, not dilated)
 *              pix4   (exemplar pix, dilated)
 *              delx   (x comp of centroid difference)
 *              dely   (y comp of centroid difference)
 *      Return: 0 (FALSE) if no match, 1 (TRUE) if the new
 *              pix is in the same class as the exemplar.
 *
 *  Note: we check first that the two pix are roughly
 *  the same size.  Only if they meet that criterion do
 *  we compare the bitmaps.  The Hausdorff is a 2-way
 *  check.  The centroid difference is used to align the two
 *  images to the nearest integer for each of the checks.
 *  These check that the dilated image of one contains
 *  ALL the pixels of the undilated image of the other.
 *  Checks are done in both direction.  A single pixel not
 *  contained in either direction results in failure of the test.
 */
l_int32
pixHaustest(PIX       *pix1,
            PIX       *pix2,
          PIX       *pix3,
          PIX       *pix4,
          l_float32  delx,   /* x(1) - x(3) */
          l_float32  dely)   /* y(1) - y(3) */
{
l_int32  wi, hi, wt, ht, delw, delh, idelx, idely, boolmatch;
PIX     *pixt;

      /* eliminate possible matches based on size difference */
    wi = pixGetWidth(pix1);
    hi = pixGetHeight(pix1);
    wt = pixGetWidth(pix3);
    ht = pixGetHeight(pix3);
    delw = L_ABS(wi - wt);
    if (delw > MAX_DIFF_WIDTH)
      return FALSE;
    delh = L_ABS(hi - ht);
    if (delh > MAX_DIFF_HEIGHT)
      return FALSE;

      /* round difference in centroid location to nearest integer;
       * use this as a shift when doing the matching. */
    if (delx >= 0)
      idelx = (l_int32)(delx + 0.5);
    else
      idelx = (l_int32)(delx - 0.5);
    if (dely >= 0)
      idely = (l_int32)(dely + 0.5);
    else
      idely = (l_int32)(dely - 0.5);

      /*  Do 1-direction hausdorff, checking that every pixel in pix1
       *  is within a dilation distance of some pixel in pix3.  Namely,
       *  that pix4 entirely covers pix1:
       *       pixt = pixSubtract(NULL, pix1, pix4), including shift
       *  where pixt has no ON pixels.  */
    pixt = pixCreateTemplate(pix1);
    pixRasterop(pixt, 0, 0, wi, hi, PIX_SRC, pix1, 0, 0);
    pixRasterop(pixt, idelx, idely, wi, hi, PIX_DST & PIX_NOT(PIX_SRC),
                pix4, 0, 0);
    pixZero(pixt, &boolmatch);
    if (boolmatch == 0) {
      pixDestroy(&pixt);
      return FALSE;
    }

      /*  Do 1-direction hausdorff, checking that every pixel in pix3
       *  is within a dilation distance of some pixel in pix1.  Namely,
       *  that pix2 entirely covers pix3:
       *      pixSubtract(pixt, pix3, pix2), including shift
       *  where pixt has no ON pixels. */
    pixRasterop(pixt, idelx, idely, wt, ht, PIX_SRC, pix3, 0, 0);
    pixRasterop(pixt, 0, 0, wt, ht, PIX_DST & PIX_NOT(PIX_SRC), pix2, 0, 0);
    pixZero(pixt, &boolmatch);
    pixDestroy(&pixt);
    return boolmatch;
}


/*!
 *  pixRankHaustest()
 *
 *      Input:  pix1   (new pix, not dilated)
 *              pix2   (new pix, dilated)
 *              pix3   (exemplar pix, not dilated)
 *              pix4   (exemplar pix, dilated)
 *              delx   (x comp of centroid difference)
 *              dely   (y comp of centroid difference)
 *              area1  (fg pixels in pix1)
 *              area3  (fg pixels in pix3)
 *              rank   (rank value of test, each way)
 *              tab8   (table of pixel sums for byte)
 *      Return: 0 (FALSE) if no match, 1 (TRUE) if the new
 *                 pix is in the same class as the exemplar.
 *
 *  Note: we check first that the two pix are roughly
 *  the same size.  Only if they meet that criterion do
 *  we compare the bitmaps.  We convert the rank value to
 *  a number of pixels by multiplying the rank fraction by the number
 *  of pixels in the undilated image.  The Hausdorff is a 2-way
 *  check.  The centroid difference is used to align the two
 *  images to the nearest integer for each of the checks.
 *  The rank hausdorff checks that the dilated image of one
 *  contains the rank fraction of the pixels of the undilated
 *  image of the other.   Checks are done in both direction. 
 *  Failure of the test in either direction results in failure
 *  of the test.
 */
l_int32
pixRankHaustest(PIX       *pix1,
                PIX       *pix2,
              PIX       *pix3,
              PIX       *pix4,
              l_float32  delx,   /* x(1) - x(3) */
              l_float32  dely,   /* y(1) - y(3) */
            l_int32    area1,
            l_int32    area3,
              l_float32  rank,
            l_int32   *tab8)
{
l_int32  wi, hi, wt, ht, delw, delh, idelx, idely, boolmatch;
l_int32  thresh1, thresh3;
PIX     *pixt;

      /* eliminate possible matches based on size difference */
    wi = pixGetWidth(pix1);
    hi = pixGetHeight(pix1);
    wt = pixGetWidth(pix3);
    ht = pixGetHeight(pix3);
    delw = L_ABS(wi - wt);
    if (delw > MAX_DIFF_WIDTH)
      return FALSE;
    delh = L_ABS(hi - ht);
    if (delh > MAX_DIFF_HEIGHT)
      return FALSE;

      /* upper bounds in remaining pixels for allowable match */
    thresh1 = (l_int32)(area1 * (1. - rank) + 0.5);
    thresh3 = (l_int32)(area3 * (1. - rank) + 0.5);

      /* round difference in centroid location to nearest integer;
       * use this as a shift when doing the matching. */
    if (delx >= 0)
      idelx = (l_int32)(delx + 0.5);
    else
      idelx = (l_int32)(delx - 0.5);
    if (dely >= 0)
      idely = (l_int32)(dely + 0.5);
    else
      idely = (l_int32)(dely - 0.5);

      /*  Do 1-direction hausdorff, checking that every pixel in pix1
       *  is within a dilation distance of some pixel in pix3.  Namely,
       *  that pix4 entirely covers pix1:
       *       pixt = pixSubtract(NULL, pix1, pix4), including shift
       *  where pixt has no ON pixels.  */
    pixt = pixCreateTemplate(pix1);
    pixRasterop(pixt, 0, 0, wi, hi, PIX_SRC, pix1, 0, 0);
    pixRasterop(pixt, idelx, idely, wi, hi, PIX_DST & PIX_NOT(PIX_SRC),
                pix4, 0, 0);
    pixThresholdPixels(pixt, thresh1, &boolmatch, tab8);
    if (boolmatch == 1) { /* above thresh1 */
      pixDestroy(&pixt);
      return FALSE;
    }

      /*  Do 1-direction hausdorff, checking that every pixel in pix3
       *  is within a dilation distance of some pixel in pix1.  Namely,
       *  that pix2 entirely covers pix3:
       *      pixSubtract(pixt, pix3, pix2), including shift
       *  where pixt has no ON pixels. */
    pixRasterop(pixt, idelx, idely, wt, ht, PIX_SRC, pix3, 0, 0);
    pixRasterop(pixt, 0, 0, wt, ht, PIX_DST & PIX_NOT(PIX_SRC), pix2, 0, 0);
    pixThresholdPixels(pixt, thresh3, &boolmatch, tab8);
    pixDestroy(&pixt);
    if (boolmatch == 1)  /* above thresh3 */
      return FALSE;
    else
      return TRUE;
}



/*----------------------------------------------------------------------*
 *            Classification using windowed correlation score           *
 *----------------------------------------------------------------------*/
/*!
 *  jbClassifyCorrelation()
 *
 *      Input:  jbclasser
 *              boxa (of new components for classification)
 *              pixas (of new components for classification)
 *      Return: 0 if OK; 1 on error
 */
l_int32
jbClassifyCorrelation(JBCLASSER  *classer,
                      BOXA       *boxa,
                      PIXA       *pixas)
{
l_int32    n, ns, nt, i, j, iclass, wt, ht, found, area, area1, area2, npages;
l_int32   *sumtab;
l_float32  x1, y1, x2, y2;
l_float32  thresh, weight, threshold, score;
BOX       *box;
NUMA      *naclass, *napage;
NUMA      *nafg;    /* fg area of all instances */
NUMA      *nafgt;   /* fg area of all templates */
NUMA      *naarea;   /* w * h area of all templates */
NUMA      *nalist;  /* indices of templates similar in size to instance */
NUMAHASH  *nahash;
PIX       *pix, *pix1, *pix2;
PIXA      *pixa, *pixa1, *pixat;
PIXAA     *pixaa;
PTA       *pta, *ptac, *ptact;

    PROCNAME("jbClassifyCorrelation");

    if (!classer)
      return ERROR_INT("classer not found", procName, 1);
    if (!boxa)
      return ERROR_INT("boxa not found", procName, 1);
    if (!pixas)
      return ERROR_INT("pixas not found", procName, 1);

    npages = classer->npages;

      /* Generate the bordered pixa, which contains all the the
       * input components.  This will not be saved.   */
    n = pixaGetCount(pixas);
    pixa1 = pixaCreate(n);
    for (i = 0; i < n; i++) {
      pix = pixaGetPix(pixas, i, L_CLONE);
      pix1 = pixAddBorderGeneral(pix, JB_ADDED_PIXELS, JB_ADDED_PIXELS,
                  JB_ADDED_PIXELS, JB_ADDED_PIXELS, 0);
      pixaAddPix(pixa1, pix1, L_INSERT);
      pixDestroy(&pix);
    }

      /* Get the centroids of all the bordered images.
       * These are relative to the UL corner of each (bordered) pix.  */
    pta = pixaCentroids(pixa1);  /* centroids for this page; use here */
    ptac = classer->ptac;  /* holds centroids of components up to this page */
    ptaJoin(ptac, pta, 0, 0);  /* save centroids of all components */
    ptact = classer->ptact;  /* holds centroids of templates */
      
        /* Use these to save the class and page of each component. */
    naclass = classer->naclass;
    napage = classer->napage;

      /* Get the number of fg pixels in each component.  */
    nafg = pixaCountPixels(pixa1);
    nafgt = classer->nafgt;    /* holds fg areas of the templates */
    sumtab = makePixelSumTab8();

    /* Store the unbordered pix in a pixaa, in a hierarchical
     * set of arrays.  There is one pixa for each class,
     * and the pix in each pixa are all the instances found
     * of that class.  This is actually more than one would need
     * for a jbig2 encoder, but there are two reasons to keep
     * them around: (1) the set of instances for each class
     * can be used to make an improved binary (or, better,
     * a grayscale) template, rather than simply using the first
     * one in the set; (2) we can investigate the failures
     * of the classifier.  This pixaa grows as we process
     * successive pages. */
    pixaa = classer->pixaa;

      /* Array to store class exemplars */
    pixat = classer->pixat;

      /* Fill up the pixaa tree with the template exemplars as
       * the first pix in each pixa.  As we add each pix,
       * we also add the associated box to the pixa.
       * We also keep track of the centroid of each pix,
       * and use the difference between centroids (of the
       * pix with the exemplar we are checking it with)
       * to align the two when checking that the correlation
       * score exceeds a threshold.  The correlation score
       * is given by the square of the area of the AND
       * between aligned instance and template, divided by
       * the product of areas of each image.  For identical
       * template and instance, the score is 1.0.
       * If the threshold is too small, non-equivalent instances
       * will be placed in the same class; if too large, there will
       * be an unnecessary division of classes representing the
       * same character.  The weightfactor adds in some of the
       * difference (1.0 - thresh), depending on the heaviness
       * of the template (measured as the fraction of fg pixels). */
    thresh = classer->thresh;
    weight = classer->weightfactor;
    naarea = classer->naarea;
    nahash = classer->nahash;
    for (i = 0; i < n; i++) {
      pix1 = pixaGetPix(pixa1, i, L_CLONE);
      numaGetIValue(nafg, i, &area1);
      ptaGetPt(pta, i, &x1, &y1);  /* centroid for this instance */
      nt = pixaGetCount(pixat);
      found = FALSE;
      nalist = findSimilarSizedTemplates(classer, pix1);
      ns = numaGetCount(nalist);
      for (j = 0; j < ns; j++) {  /* search through templates */
              /* Select the template */
            numaGetIValue(nalist, j, &iclass);
            
                /* Find score for this template */
          pix2 = pixaGetPix(pixat, iclass, L_CLONE);
          numaGetIValue(nafgt, iclass, &area2);
          ptaGetPt(ptact, iclass, &x2, &y2);  /* template centroid */
          score = pixCorrelationScore(pix1, pix2, area1, area2,
                      x1 - x2, y1 - y2, sumtab);
          pixDestroy(&pix2);

                /* Find threshold for this template */
            if (weight > 0.0) {
                numaGetIValue(naarea, iclass, &area);
                threshold = thresh + (1. - thresh) * weight * area2 / area;
            }
            else
                threshold = thresh;

          if (score >= threshold) {  /* greedy match */
            found = TRUE;
            numaAddNumber(naclass, iclass);
            numaAddNumber(napage, npages);
            pixa = pixaaGetPixa(pixaa, iclass, L_CLONE);
            pix = pixaGetPix(pixas, i, L_CLONE);
            pixaAddPix(pixa, pix, L_INSERT);
            box = boxaGetBox(boxa, i, L_CLONE);
            pixaAddBox(pixa, box, L_INSERT);
            pixaDestroy(&pixa);
            break;
          }
      }
      numaDestroy(&nalist);
      if (found == FALSE) {  /* new class */
          numaAddNumber(naclass, nt);
          numaAddNumber(napage, npages);
          pixa = pixaCreate(0);
          pix = pixaGetPix(pixas, i, L_CLONE);  /* unbordered instance */
          pixaAddPix(pixa, pix, L_INSERT);
          wt = pixGetWidth(pix);
          ht = pixGetHeight(pix);
            numaHashAdd(nahash, ht * wt, nt);
          box = boxaGetBox(boxa, i, L_CLONE);
          pixaAddBox(pixa, box, L_INSERT);
          pixaaAddPixa(pixaa, pixa, L_INSERT);  /* unbordered instance */
          ptaAddPt(ptact, x1, y1);
          numaAddNumber(nafgt, area1);
          pixaAddPix(pixat, pix1, L_INSERT);   /* bordered template */
            area = (pixGetWidth(pix1) - 2 * JB_ADDED_PIXELS) *
                   (pixGetHeight(pix1) - 2 * JB_ADDED_PIXELS);
          numaAddNumber(naarea, area);
      }
      else {   /* don't save it */
          pixDestroy(&pix1);
      }
    }
    classer->nclass = pixaGetCount(pixat);

    FREE((void *)sumtab);
    ptaDestroy(&pta);
    pixaDestroy(&pixa1);
    numaDestroy(&nafg);
    return 0;
}


/*!
 *  pixCorrelationScore()
 *
 *      Input:  pix1   (test pix)
 *              pix2   (exemplar pix)
 *              area1  (number of on pixels in pix1)
 *              area2  (number of on pixels in pix2)
 *              delx   (x comp of centroid difference)
 *              dely   (y comp of centroid difference)
 *              tab    (sum tab for byte)
 *      Return: correlation score 
 *
 *  Note: we check first that the two pix are roughly the same size.
 *  Only if they meet that criterion do we compare the bitmaps. 
 *  The centroid difference is used to align the two images to the
 *  nearest integer for the correlation.
 *
 *  The correlation score is the ratio of the square of the number of
 *  pixels in the AND of the two bitmaps to the product of the number
 *  of ON pixels in each.  Denote the number of ON pixels in pix1
 *  by |1|, the number in pix2 by |2|, and the number in the AND
 *  of pix1 and pix2 by |1 ^ 2|.  The correlation score is then
 *  (|1 ^ 2|)**2 / (|1|*|2|).
 *
 *  This score is compared with an input threshold, which can
 *  be modified depending on the weight of the template.
 *  The modified threshold is
 *     thresh + (1.0 - thresh) * weight * R
 *  where 
 *     weight is a fixed input factor between 0.0 and 1.0
 *     R = |2| / area(2)
 *  and area(2) is the total number of pixels in 2 (i.e., width x height).
 *
 *  To understand why a weight factor is useful, consider what happens
 *  with thick, sans-serif characters that look similar and have a value
 *  of R near 1.  Different characters can have a high correlation value,
 *  and the classifier will make incorrect substitutions.  The weight
 *  factor raises the threshold for these characters.
 *
 *  Yet another approach to reduce such substitutions is to run the classifier
 *  in a non-greedy way, matching to the template with the highest
 *  score, not the first template with a score satisfying the matching
 *  constraint.  However, this is not particularly effective.
 */
l_float32
pixCorrelationScore(PIX       *pix1,
                    PIX       *pix2,
                l_int32    area1,
                l_int32    area2,
                  l_float32  delx,   /* x(1) - x(3) */
                  l_float32  dely,   /* y(1) - y(3) */
                l_int32   *tab)
{
l_int32    wi, hi, wt, ht, delw, delh, idelx, idely, count;
l_float32  score;
PIX       *pixt;

      /* eliminate based on size difference */
    wi = pixGetWidth(pix1);
    hi = pixGetHeight(pix1);
    wt = pixGetWidth(pix2);
    ht = pixGetHeight(pix2);
    delw = L_ABS(wi - wt);
    if (delw > MAX_DIFF_WIDTH)
      return FALSE;
    delh = L_ABS(hi - ht);
    if (delh > MAX_DIFF_HEIGHT)
      return FALSE;

      /* round difference to nearest integer */
    if (delx >= 0)
      idelx = (l_int32)(delx + 0.5);
    else
      idelx = (l_int32)(delx - 0.5);
    if (dely >= 0)
      idely = (l_int32)(dely + 0.5);
    else
      idely = (l_int32)(dely - 0.5);

      /*  pixt = pixAnd(NULL, pix1, pix2), including shift */
    pixt = pixCreateTemplate(pix1);
    pixRasterop(pixt, 0, 0, wi, hi, PIX_SRC, pix1, 0, 0);
    pixRasterop(pixt, idelx, idely, wt, ht, PIX_SRC & PIX_DST, pix2, 0, 0);
    pixCountPixels(pixt, &count, tab);
    pixDestroy(&pixt);
    score = (l_float32)(count * count) / (l_float32)(area1 * area2);
/*    fprintf(stderr, "score = %7.3f, count = %d, area1 = %d, area2 = %d\n",
             score, count, area1, area2); */
    return score;
}


/*----------------------------------------------------------------------*
 *             Determine the image components we start with             *
 *----------------------------------------------------------------------*/
/*!
 *  jbGetComponents()
 *
 *      Input:  pixs (1 bpp)
 *              components (JB_CONN_COMPS, JB_CHARACTERS, JB_WORDS)
 *              maxwidth, maxheight (of saved components; larger are discarded)
 *              &pboxa (<return> b.b. of component items)
 *              &ppixa (<return> component items)
 *      Return: 0 if OK, 1 on error
 */
l_int32
jbGetComponents(PIX     *pixs,
                l_int32  components,
                l_int32  maxwidth,
                l_int32  maxheight,
                BOXA   **pboxad,
                PIXA   **ppixad)
{
l_int32    empty, i, res, redfactor, ndiff, imin, diffmin;
l_int32    ncc[10];
BOXA      *boxa, *boxat;
PIX       *pixt1, *pixt2, *pixt3;
PIXA      *pixa, *pixat, *pixat2;
SEL       *sel_6v, *sel_2h;

    PROCNAME("jbGetComponents");

    if (!pixs)
      return ERROR_INT("pixs not defined", procName, 1);
    if (!pboxad)
      return ERROR_INT("&boxad not defined", procName, 1);
    if (!ppixad)
      return ERROR_INT("&pixad not defined", procName, 1);
    if (components != JB_CONN_COMPS && components != JB_CHARACTERS &&
        components != JB_WORDS)
      return ERROR_INT("invalid components", procName, 1);

    pixZero(pixs, &empty);
    if (empty) {
        *pboxad = boxaCreate(0);
        *ppixad = pixaCreate(0);
        return 0;
    }

        /* If required, preprocess input pixs.  The method for both
         * characters and words is to generate a connected component
         * mask over the units that we want to aggregrate, which are,
       * in general, sets of related connected components in pixs.
       * For characters, we want to include the dots with
       * 'i', 'j' and '!', so we do a small vertical closing to
       * generate the mask.  For words, we make a mask over all
       * characters in each word.  This is a bit more tricky, because
       * the spacing between words is difficult to predict a priori,
       * and words can be typeset with variable spacing that can
       * in some cases be barely larger than the space between
       * characters.  The first step is to generate the mask and
       * identify each of its connected components.  */
    if (components == JB_CONN_COMPS) {  /* no preprocessing */
        boxa = pixConnComp(pixs, &pixa, 8);
    } 
    else if (components == JB_CHARACTERS) {
        sel_6v = selCreateBrick(6, 1, 2, 0, SEL_HIT);
        pixt1 = pixCloseSafe(NULL, pixs, sel_6v);
        boxa = pixConnComp(pixt1, &pixat, 8);
      pixa = pixaClipToPix(pixat, pixs);
        selDestroy(&sel_6v);
      pixDestroy(&pixt1);
      pixaDestroy(&pixat);
    } 
    else {  /* components == JB_WORDS */

          /* Do the operations at about 150 ppi resolution.
           * It is much faster at 75 ppi, but the results are
           * more accurate at 150 ppi.  This will segment the
           * words in body text.  It can be expected that relatively
           * infrequent words in a larger font will be split. */
        res = pixGetXRes(pixs);
        if (res < 600) {
            redfactor = 2;
            pixt1 = pixReduceRankBinaryCascade(pixs, 1, 0, 0, 0);
        }
        else {
            redfactor = 4;
            pixt1 = pixReduceRankBinaryCascade(pixs, 1, 1, 0, 0);
      }

          /* Find the optimal dilation to create the word mask.
           * Look for successively increasing dilations where the
           * number of connected components doesn't decrease.
           * This is the situation where the components in the
           * word mask should properly cover each word.  Use of
           * 4 cc slightly reduces words joining from different lines. */
        diffmin = 1000000;
      pixat2 = pixaCreate(6);

      pixaAddPix(pixat2, pixt1, L_COPY); 

        sel_2h = selCreateBrick(1, 2, 0, 1, SEL_HIT);
        for (i = 0; i < 6; i++) {
          if (i == 0)     /* first one not dilated */
              pixt2 = pixCopy(NULL, pixt1); 
            else    /* successive dilation by sel_2h */
            pixt2 = pixDilate(NULL, pixt1, sel_2h);
            boxat = pixConnCompBB(pixt2, 4);
            ncc[i] = boxaGetCount(boxat);
            if (i > 0) {
                ndiff = ncc[i - 1] - ncc[i];
/*          fprintf(stderr, "ndiff[%d] = %d\n", i - 1, ndiff); */
                if (ndiff < diffmin) {
                    imin = i;
                    diffmin = ndiff;
                }
            }
          pixaAddPix(pixat2, pixt2, L_COPY);
          pixDestroy(&pixt1);
          pixt1 = pixt2;
            boxaDestroy(&boxat);
        }

          /* Take the result of the optimal dilation, and expand
           * the word mask to full resolution. */
        pixt2 = pixaGetPix(pixat2, imin, L_CLONE);
        pixt3 = pixExpandBinary(pixt2, redfactor);
        boxa = pixConnComp(pixt3, &pixat, 4);
      pixa = pixaClipToPix(pixat, pixs);
      pixaDestroy(&pixat2);
      pixaDestroy(&pixat);
        selDestroy(&sel_2h);
      pixDestroy(&pixt1);
        pixDestroy(&pixt2);
        pixDestroy(&pixt3);
    }

        /* Remove large components, and save the results.  */
    *ppixad = pixaRemoveLargeComponents(pixa, maxwidth, maxheight,
                                        L_REMOVE_IF_EITHER);
    *pboxad = boxaRemoveLargeComponents(boxa, maxwidth, maxheight,
                                        L_REMOVE_IF_EITHER);
    pixaDestroy(&pixa);
    boxaDestroy(&boxa);

    return 0;
}


/*----------------------------------------------------------------------*
 *                 Build grayscale composites (templates)               *
 *----------------------------------------------------------------------*/
/*!
 *  jbAccumulateComposites()
 *
 *      Input:  pixaa (one pixa for each class)
 *              &pna (<return> number of samples used to build each composite)
 *              &ptad (<return> centroids of bordered composites)
 *      Return: pixad (accumulated sum of samples in each class),
 *                     or null on error
 *
 */
PIXA *
jbAccumulateComposites(PIXAA  *pixaa,
                       NUMA  **pna,
                       PTA   **pptat)
{
l_int32    n, nt, i, j, d, minw, maxw, minh, maxh, xdiff, ydiff;
l_float32  x, y, xave, yave;
NUMA      *na;
PIX       *pix, *pixt1, *pixt2, *pixsum;
PIXA      *pixa, *pixad;
PTA       *ptat, *pta;

    PROCNAME("jbAccumulateComposites");

    if (!pixaa)
      return (PIXA *)ERROR_PTR("pixaa not defined", procName, NULL);
    if (!pptat)
      return (PIXA *)ERROR_PTR("&ptat not defined", procName, NULL);
    if (!pna)
      return (PIXA *)ERROR_PTR("&na not defined", procName, NULL);

    n = pixaaGetCount(pixaa);
    if ((ptat = ptaCreate(n)) == NULL)
      return (PIXA *)ERROR_PTR("ptat not made", procName, NULL);
    *pptat = ptat;
    pixad = pixaCreate(n);
    na = numaCreate(n);
    *pna = na;

    for (i = 0; i < n; i++) {
        pixa = pixaaGetPixa(pixaa, i, L_CLONE);
      nt = pixaGetCount(pixa);
        numaAddNumber(na, nt);
        if (nt == 0) {
            L_WARNING("empty pixa found!", procName);
            pixaDestroy(&pixa);
            continue;
        }
        pixaSizeRange(pixa, &minw, &maxw, &minh, &maxh);
        pix = pixaGetPix(pixa, 0, L_CLONE);
        d = pixGetDepth(pix);
        pixDestroy(&pix);
      pixt1 = pixCreate(maxw, maxh, d);
      pixsum = pixInitAccumulate(minw, minh, 0);
        pta = pixaCentroids(pixa);

          /* find the average value of the centroids ... */
      xave = yave = 0;
      for (j = 0; j < nt; j++) {
          ptaGetPt(pta, j, &x, &y);
          xave += x;
          yave += y;
      }
      xave = xave / (l_float32)nt;
      yave = yave / (l_float32)nt;

          /* and place all centroids at their average value */
      for (j = 0; j < nt; j++) {
          pixt2 = pixaGetPix(pixa, i, L_CLONE);
          ptaGetPt(pta, j, &x, &y);
            xdiff = (l_int32)(x - xave);
            ydiff = (l_int32)(y - yave);
          pixClearAll(pixt1);
          pixRasterop(pixt1, xdiff, ydiff, maxw, maxh, PIX_SRC,
                      pixt2, 0, 0);
            pixAccumulate(pixsum, pixt1, ARITH_ADD);
          pixDestroy(&pixt2);
      }
      pixaAddPix(pixad, pixsum, L_INSERT);
      ptaAddPt(ptat, xave, yave);

      pixaDestroy(&pixa);
      pixDestroy(&pixt1);
      ptaDestroy(&pta);
    }

    return pixad;
}


/*!
 *  jbTemplatesFromComposites()
 *
 *      Input:  pixac (one pix of composites for each class)
 *              na (number of samples used for each class composite)
 *      Return: pixad (8 bpp templates for each class), or null on error
 *
 */
PIXA *
jbTemplatesFromComposites(PIXA  *pixac,
                          NUMA  *na)
{
l_int32    n, i;
l_float32  nt;  /* number of samples in the composite; always an integer */
l_float32  factor;
PIX       *pixsum;   /* accumulated composite */
PIX       *pixd;
PIXA      *pixad;

    PROCNAME("jbTemplatesFromComposites");

    if (!pixac)
      return (PIXA *)ERROR_PTR("pixac not defined", procName, NULL);
    if (!na)
      return (PIXA *)ERROR_PTR("na not defined", procName, NULL);

    n = pixaGetCount(pixac);
    pixad = pixaCreate(n);
    for (i = 0; i < n; i++) {
        pixsum = pixaGetPix(pixac, i, L_COPY);  /* changed internally */
        numaGetFValue(na, i, &nt);
        factor = 255. / nt;
        pixMultConstAccumulate(pixsum, factor, 0);  /* changes pixsum */
        pixd = pixFinalAccumulate(pixsum, 0, 8);
        pixaAddPix(pixad, pixd, L_INSERT);
        pixDestroy(&pixsum);
    }

    return pixad;
}



/*----------------------------------------------------------------------*
 *                       jbig2 utility routines                         *
 *----------------------------------------------------------------------*/
/*!
 *  jbClasserCreate()
 *
 *      Input:  method (JB_RANKHAUS, JB_CORRELATION) 
 *              components (JB_CONN_COMPS, JB_CHARACTERS, JB_WORDS)
 *      Return: jbclasser, or null on error
 */
JBCLASSER *
jbClasserCreate(l_int32  method,
                l_int32  components)
{
JBCLASSER  *classer;

    PROCNAME("jbClasserCreate");

    if ((classer = (JBCLASSER *)CALLOC(1, sizeof(JBCLASSER))) == NULL)
      return (JBCLASSER *)ERROR_PTR("classer not made", procName, NULL);
    if (method != JB_RANKHAUS && method != JB_CORRELATION)
      return (JBCLASSER *)ERROR_PTR("invalid type", procName, NULL);
    if (components != JB_CONN_COMPS && components != JB_CHARACTERS &&
        components != JB_WORDS)
      return (JBCLASSER *)ERROR_PTR("invalid type", procName, NULL);

    classer->method = method;
    classer->components = components;
    classer->nacomps = numaCreate(0);
    classer->pixaa = pixaaCreate(0);
    classer->pixat = pixaCreate(0);
    classer->pixatd = pixaCreate(0);
    classer->nafgt = numaCreate(0);
    classer->naarea = numaCreate(0);
    classer->ptac = ptaCreate(0);
    classer->ptact = ptaCreate(0);
    classer->naclass = numaCreate(0);
    classer->napage = numaCreate(0);
    classer->ptaul = ptaCreate(0);

    return classer;
}


/*
 *  jbClasserDestroy()
 *
 *      Input: &classer (<to be nulled>)
 *      Return: void
 */
void
jbClasserDestroy(JBCLASSER  **pclasser)
{
JBCLASSER  *classer;

    if (!pclasser)
        return;
    if ((classer = *pclasser) == NULL)
        return;

    sarrayDestroy(&classer->safiles);
    numaDestroy(&classer->nacomps);
    pixDestroy(&classer->pixs);
    boxaDestroy(&classer->boxas);
    pixaDestroy(&classer->pixas);
    pixaaDestroy(&classer->pixaa);
    pixaDestroy(&classer->pixat);
    pixaDestroy(&classer->pixatd);
    numaHashDestroy(&classer->nahash);
    numaDestroy(&classer->nafgt);
    numaDestroy(&classer->naarea);
    ptaDestroy(&classer->ptac);
    ptaDestroy(&classer->ptact);
    numaDestroy(&classer->naclass);
    numaDestroy(&classer->napage);
    ptaDestroy(&classer->ptaul);
    ptaDestroy(&classer->ptall);
    FREE((void *)classer);
    *pclasser = NULL;
    return;
}
    

/*!
 *  jbDataSave()
 *
 *      Input:  jbclasser
 *              latticew, latticeh (cell size used to store each
 *                  connected component in the composite)
 *      Return: jbdata, or null on error
 *
 *  Notes:
 *      (1) This routine stores the jbig2-type data required for
 *          generating a lossy jbig2 version of the image.
 *          It can be losslessly written to (and read from) two files.
 *      (2) It generates and stores the mosaic of templates.
 *      (3) It clones the Numa and Pta arrays, so these must all
 *          be destroyed by the caller.
 *      (4) Input 0 to use the default values for latticew and/or latticeh,
 */
JBDATA *
jbDataSave(JBCLASSER  *classer)
{
l_int32  maxw, maxh;
JBDATA  *data;
PIX     *pix;

    PROCNAME("jbDataSave");

    if (!classer)
      return (JBDATA *)ERROR_PTR("classer not defined", procName, NULL);

        /* Write the templates into an array. */
    pixaSizeRange(classer->pixat, NULL, NULL, &maxw, &maxh);
    if ((pix = pixaDisplayOnLattice(classer->pixat, maxw + 1, maxh + 1))
          == NULL)
      return (JBDATA *)ERROR_PTR("data not made", procName, NULL);

    if ((data = (JBDATA *)CALLOC(1, sizeof(JBDATA))) == NULL)
      return (JBDATA *)ERROR_PTR("data not made", procName, NULL);
    data->pix = pix;
    data->npages = classer->npages;
    data->w = classer->w;
    data->h = classer->h;
    data->nclass = classer->nclass;
    data->latticew = maxw + 1;
    data->latticeh = maxh + 1;
    data->naclass = numaClone(classer->naclass);
    data->napage = numaClone(classer->napage);
    data->ptaul = ptaClone(classer->ptaul);

    return data;
}


/*
 *  jbDataDestroy()
 *
 *      Input: &data (<to be nulled>)
 *      Return: void
 */
void
jbDataDestroy(JBDATA  **pdata)
{
JBDATA  *data;

    if (!pdata)
        return;
    if ((data = *pdata) == NULL)
        return;

    pixDestroy(&data->pix);
    numaDestroy(&data->naclass);
    numaDestroy(&data->napage);
    ptaDestroy(&data->ptaul);
    FREE((void *)data);
    *pdata = NULL;
    return;
}
    

/*!
 *  jbDataWrite()
 *
 *      Input:  rootname (for output files; everything but the extension)
 *              jbdata
 *      Return: 0 if OK, 1 on error
 *
 *  Note: Writes data in jbdata to file.
 */
l_int32
jbDataWrite(const char  *rootout,
            JBDATA      *jbdata)
{
char     buf[BUF_SIZE];
l_int32  w, h, nclass, npages, cellw, cellh, ncomp, i, x, y, iclass, ipage;
NUMA    *naclass, *napage;
PTA     *ptaul;
PIX     *pixt;
FILE    *fp;
    
    PROCNAME("jbDataWrite");

    if (!rootout)
        return ERROR_INT("no rootout", procName, 1);
    if (!jbdata)
        return ERROR_INT("no jbdata", procName, 1);

    npages = jbdata->npages;
    w = jbdata->w;
    h = jbdata->h;
    pixt = jbdata->pix;
    nclass = jbdata->nclass;
    cellw = jbdata->latticew;
    cellh = jbdata->latticeh;
    naclass = jbdata->naclass;
    napage = jbdata->napage;
    ptaul = jbdata->ptaul;

    snprintf(buf, BUF_SIZE, "%s%s", rootout, JB_TEMPLATE_EXT); 
    pixWrite(buf, pixt, IFF_PNG);

    snprintf(buf, BUF_SIZE, "%s%s", rootout, JB_DATA_EXT); 
    if ((fp = fopen(buf, "w")) == NULL)
      return ERROR_INT("stream not opened", procName, 1);
    ncomp = ptaGetCount(ptaul);
    fprintf(fp, "jb data file\n");
    fprintf(fp, "num pages = %d\n", npages);
    fprintf(fp, "page size: w = %d, h = %d\n", w, h);
    fprintf(fp, "num components = %d\n", ncomp);
    fprintf(fp, "num classes = %d\n", nclass);
    fprintf(fp, "template lattice size: w = %d, h = %d\n", cellw, cellh);
    for (i = 0; i < ncomp; i++) {
      numaGetIValue(napage, i, &ipage);
      numaGetIValue(naclass, i, &iclass);
      ptaGetIPt(ptaul, i, &x, &y);
      fprintf(fp, "%d %d %d %d\n", ipage, iclass, x, y);
    }
    fclose(fp);

    return 0;
}


/*!
 *  jbDataRead()
 *
 *      Input:  rootname (for template and data files)
 *      Return: jbdata, or NULL on error
 */
JBDATA *
jbDataRead(const char  *rootname)
{
char      fname[BUF_SIZE];
char     *linestr;
l_uint8  *data;
l_int32   nsa, i, w, h, cellw, cellh, x, y, iclass, ipage;
l_int32   nbytes, npages, nclass, ncomp;
JBDATA   *jbdata;
NUMA     *naclass, *napage;
PIX      *pixs;
PTA      *ptaul;
SARRAY   *sa;
    
    PROCNAME("jbDataRead");

    snprintf(fname, BUF_SIZE, "%s%s", rootname, JB_TEMPLATE_EXT);
    if ((pixs = pixRead(fname)) == NULL)
      return (JBDATA *)ERROR_PTR("pix not read", procName, NULL);

    snprintf(fname, BUF_SIZE, "%s%s", rootname, JB_DATA_EXT);
    if ((data = arrayRead(fname, &nbytes)) == NULL)
      return (JBDATA *)ERROR_PTR("data not read", procName, NULL);

    if ((sa = sarrayCreateLinesFromString((char *)data, 0)) == NULL)
      return (JBDATA *)ERROR_PTR("sa not made", procName, NULL);
    nsa = sarrayGetCount(sa);   /* number of cc + 6 */
    linestr = sarrayGetString(sa, 0, 0);
    if (strcmp(linestr, "jb data file"))
      return (JBDATA *)ERROR_PTR("invalid jb data file", procName, NULL);
    linestr = sarrayGetString(sa, 1, 0);
    sscanf(linestr, "num pages = %d", &npages);
    linestr = sarrayGetString(sa, 2, 0);
    sscanf(linestr, "page size: w = %d, h = %d", &w, &h);
    linestr = sarrayGetString(sa, 3, 0);
    sscanf(linestr, "num components = %d", &ncomp);
    linestr = sarrayGetString(sa, 4, 0);
    sscanf(linestr, "num classes = %d\n", &nclass);
    linestr = sarrayGetString(sa, 5, 0);
    sscanf(linestr, "template lattice size: w = %d, h = %d\n", &cellw, &cellh);

#if 1
    fprintf(stderr, "num pages = %d\n", npages);
    fprintf(stderr, "page size: w = %d, h = %d\n", w, h);
    fprintf(stderr, "num components = %d\n", ncomp);
    fprintf(stderr, "num classes = %d\n", nclass);
    fprintf(stderr, "template lattice size: w = %d, h = %d\n", cellw, cellh);
#endif

    if ((naclass = numaCreate(ncomp)) == NULL)
      return (JBDATA *)ERROR_PTR("naclass not made", procName, NULL);
    if ((napage = numaCreate(ncomp)) == NULL)
      return (JBDATA *)ERROR_PTR("napage not made", procName, NULL);
    if ((ptaul = ptaCreate(ncomp)) == NULL)
      return (JBDATA *)ERROR_PTR("pta not made", procName, NULL);
    for (i = 6; i < nsa; i++) {
      linestr = sarrayGetString(sa, i, 0);
      sscanf(linestr, "%d %d %d %d\n", &ipage, &iclass, &x, &y);
      numaAddNumber(napage, ipage);
      numaAddNumber(naclass, iclass);
      ptaAddPt(ptaul, x, y);
    }

    if ((jbdata = (JBDATA *)CALLOC(1, sizeof(JBDATA))) == NULL)
      return (JBDATA *)ERROR_PTR("data not made", procName, NULL);
    jbdata->pix = pixs;
    jbdata->npages = npages;
    jbdata->w = w;
    jbdata->h = h;
    jbdata->nclass = nclass;
    jbdata->latticew = cellw;
    jbdata->latticeh = cellh;
    jbdata->naclass = naclass;
    jbdata->napage = napage;
    jbdata->ptaul = ptaul;

    FREE((void *)data);
    sarrayDestroy(&sa);
    return jbdata;
}


/*!
 *  jbDataRender()
 *
 *      Input:  jbdata
 *              debugflag (if TRUE, writes into 4 bpp pix and adds 
 *                         component outlines in color)
 *      Return: pixa (reconstruction of original images, using templates) or
 *              null on error
 */
PIXA *
jbDataRender(JBDATA  *data,
             l_int32  debugflag)
{
l_int32   i, w, h, cellw, cellh, x, y, iclass, ipage;
l_int32   npages, nclass, ncomp, wp, hp;
BOX      *box;
NUMA     *naclass, *napage;
PIX      *pixt, *pixt2, *pix, *pixd;
PIXA     *pixat;   /* pixa of templates */
PIXA     *pixad;   /* pixa of output images */
PIXCMAP  *cmap;
PTA      *ptaul;
    
    PROCNAME("jbDataRender");

    npages = data->npages;
    w = data->w;
    h = data->h;
    pixt = data->pix;
    nclass = data->nclass;
    cellw = data->latticew;
    cellh = data->latticeh;
    naclass = data->naclass;
    napage = data->napage;
    ptaul = data->ptaul;
    ncomp = numaGetCount(naclass);
    
      /* Reconstruct the original set of images from the templates
       * and the data associated with each component.  First,
         * generate the output pixa as a set of empty pix. */
    if ((pixad = pixaCreate(npages)) == NULL)
      return (PIXA *)ERROR_PTR("pixad not made", procName, NULL);
    for (i = 0; i < npages; i++) {
      if (debugflag == FALSE)
          pix = pixCreate(w, h, 1);
      else {
          pix = pixCreate(w, h, 2);
          cmap = pixcmapCreate(2);
          pixcmapAddColor(cmap, 255, 255, 255);
          pixcmapAddColor(cmap, 0, 0, 0);
          pixcmapAddColor(cmap, 255, 0, 0);  /* for box outlines */
          pixSetColormap(pix, cmap);
      }
        pixaAddPix(pixad, pix, L_INSERT);
    }
    
        /* Put the class templates into a pixa. */
    if ((pixat = pixaCreateFromPix(pixt, nclass, cellw, cellh)) == NULL)
      return (PIXA *)ERROR_PTR("pixat not made", procName, NULL);

      /* Place each component in the right location on its page. */
    for (i = 0; i < ncomp; i++) {
      numaGetIValue(napage, i, &ipage);
      numaGetIValue(naclass, i, &iclass);
      pix = pixaGetPix(pixat, iclass, L_CLONE);  /* the template */
      wp = pixGetWidth(pix);
      hp = pixGetHeight(pix);
      ptaGetIPt(ptaul, i, &x, &y);
      pixd = pixaGetPix(pixad, ipage, L_CLONE);   /* the output page */
      if (debugflag == FALSE)
          pixRasterop(pixd, x, y, wp, hp, PIX_SRC | PIX_DST, pix, 0, 0);
        else {
          pixt2 = pixConvert1To2Cmap(pix);
          pixRasterop(pixd, x, y, wp, hp, PIX_SRC | PIX_DST, pixt2, 0, 0);
          box = boxCreate(x, y, wp, hp);
          pixRenderBoxArb(pixd, box, 1, 255, 0, 0);
          pixDestroy(&pixt2);
          boxDestroy(&box);
      }
      pixDestroy(&pix);   /* the clone only */
      pixDestroy(&pixd);  /* the clone only */
    }

    pixaDestroy(&pixat);
    return pixad;
}


/*!
 *  jbGetULCorners()
 *
 *      Input:  jbclasser
 *              boxa  (of c.c. bounding rectangles for this page)
 *      Return: 0 if OK, 1 on error
 *
 *  Notes:
 *      (1) This computes the ptaul field, which has the global UL corners,
 *          adjusted for each specific component, so that each component
 *          can be replaced by the template for its class and have the
 *          centroid in the template in the same position as the
 *          centroid of the original connected component.  It is important
 *          that this be done properly to avoid a wavy baseline in the
 *          result.
 *      (2) The array fields ptac and ptact give the centroids of
 *          those components relative to the UL corner of each component.
 *          Here, we compute the difference in each component, round to
 *          nearest integer, and correct the box->x and box->y by
 *          the appropriate integral difference.
 *      (3) The templates and stored instances are all bordered.
 */
l_int32
jbGetULCorners(JBCLASSER  *classer,
               BOXA       *boxa)
{
l_int32    i, baseindex, index, n, iclass, idelx, idely, x, y, dx, dy;
l_int32   *sumtab;
l_float32  x1, x2, y1, y2, delx, dely;
BOX       *box;
NUMA      *naclass;
PIX       *pixt;
PTA       *ptac, *ptact, *ptaul;

    PROCNAME("jbGetULCorners");

    if (!classer)
      return ERROR_INT("classer not defined", procName, 1);
    if (!boxa)
      return ERROR_INT("boxa not defined", procName, 1);

    n = boxaGetCount(boxa);
    ptaul = classer->ptaul;
    naclass = classer->naclass;
    ptac = classer->ptac;
    ptact = classer->ptact;
    baseindex = classer->baseindex;  /* num components before this page */
    sumtab = makePixelSumTab8();
    for (i = 0; i < n; i++) {
      index = baseindex + i;
      ptaGetPt(ptac, index, &x1, &y1);
      numaGetIValue(naclass, index, &iclass);
      ptaGetPt(ptact, iclass, &x2, &y2);
      delx = x2 - x1;
      dely = y2 - y1;
      if (delx >= 0)
          idelx = (l_int32)(delx + 0.5);
      else
          idelx = (l_int32)(delx - 0.5);
      if (dely >= 0)
          idely = (l_int32)(dely + 0.5);
      else
          idely = (l_int32)(dely - 0.5);
      if ((box = boxaGetBox(boxa, i, L_CLONE)) == NULL)
          return ERROR_INT("box not found", procName, 1);
      x = box->x;
      y = box->y;

            /* Get final increments dx and dy for best alignment */
      pixt = pixaGetPix(classer->pixat, iclass, L_CLONE);
      finalPositioningForAlignment(classer->pixs, x, y, idelx, idely,
                                   pixt, sumtab, &dx, &dy);
/*    if (i % 20 == 0)
          fprintf(stderr, "dx = %d, dy = %d\n", dx, dy); */
      ptaAddPt(ptaul, x - idelx + dx, y - idely + dy);
      boxDestroy(&box);
      pixDestroy(&pixt);
    }

    FREE((void *)sumtab);
    return 0;
}


/*!
 *  jbGetLLCorners()
 *
 *      Input:  jbclasser
 *      Return: 0 if OK, 1 on error
 *
 *  Notes:
 *      (1) This computes the ptall field, which has the global LL corners,
 *          adjusted for each specific component, so that each component
 *          can be replaced by the template for its class and have the
 *          centroid in the template in the same position as the
 *          centroid of the original connected component. It is important
 *          that this be done properly to avoid a wavy baseline in the result.
 *      (2) It is computed here from the corresponding UL corners, where
 *          the input templates and stored instances are all bordered.
 *          This should be done after all pages have been processed.
 *      (3) For proper substitution, the templates whose LL corners are
 *          placed in these locations must be UN-bordered.
 *          This is available for a realistic jbig2 encoder, which would
 *          (1) encode each template without a border, and (2) encode
 *          the position using the LL corner (rather than the UL 
 *          corner) because the difference between y-values
 *          of successive instances is typically close to zero.
 */
l_int32
jbGetLLCorners(JBCLASSER  *classer)
{
l_int32    i, iclass, n, x1, y1, h;
NUMA      *naclass;
PIX       *pix;
PIXA      *pixat;
PTA       *ptaul, *ptall;

    PROCNAME("jbGetLLCorners");

    if (!classer)
      return ERROR_INT("classer not defined", procName, 1);

    ptaul = classer->ptaul;
    naclass = classer->naclass;
    pixat = classer->pixat;

    ptaDestroy(&classer->ptall);
    n = ptaGetCount(ptaul);
    ptall = ptaCreate(n);
    classer->ptall = ptall;

        /* If the templates were bordered, we would add h - 1 to the UL
         * corner y-value.  However, because the templates to be used
         * here have their borders removed, and the borders are
         * JB_ADDED_PIXELS on each side, we add h - 1 - 2 * JB_ADDED_PIXELS
         * to the UL corner y-value.  */
    for (i = 0; i < n; i++) {
      ptaGetIPt(ptaul, i, &x1, &y1);
      numaGetIValue(naclass, i, &iclass);
      pix = pixaGetPix(pixat, iclass, L_CLONE);
      h = pixGetHeight(pix);
      ptaAddPt(ptall, x1, y1 + h - 1 - 2 * JB_ADDED_PIXELS);
      pixDestroy(&pix);
    }

    return 0;
}


/*----------------------------------------------------------------------*
 *                              Static helpers                          *
 *----------------------------------------------------------------------*/
/* When looking for similar matches we check templates whose size is +/- 2 in
 * each direction. This involves 25 possible sizes. This array contains the
 * offsets for each of those positions in a spirial pattern. There are 25 pairs
 * of numbers in this array: even positions are x values. */
static int two_by_two_walk[50] = {
  0, 0,
  0, 1,
  -1, 0,
  0, -1,
  1, 0,
  -1, 1,
  1, 1,
  -1, -1,
  1, -1,
  0, -2,
  2, 0,
  0, 2,
  -2, 0,
  -1, -2,
  1, -2,
  2, -1,
  2, 1,
  1, 2,
  -1, 2,
  -2, 1,
  -2, -1,
  -2, -2,
  2, -2,
  2, 2,
  -2, 2};

/*!
 *  findSimilarSizedTemplates()
 *
 *      Input:  classer
 *              pixs (instance to be matched)
 *      Return: nalist (of templates of similar size), or null on error
 *
 *  Note: the 'list' of similar sized templates can be empty.
 */
static NUMA *
findSimilarSizedTemplates(JBCLASSER  *classer,
                          PIX        *pixs)
{
l_int32   w, h, size, i, j, desiredh, desiredw;
l_int32  *array;
NUMA     *na, *nad;
PIX      *pixt;

    PROCNAME("findSimilarSizedTemplates");
   
    if (!classer)
        return (NUMA *)ERROR_PTR("classer not defined", procName, NULL);
    if (!pixs)
        return (NUMA *)ERROR_PTR("pixs not defined", procName, NULL);

    w = pixGetWidth(pixs) - 2 * JB_ADDED_PIXELS;
    h = pixGetHeight(pixs) - 2 * JB_ADDED_PIXELS;
    nad = numaCreate(5);
    
    for (i = 0; i < 25; ++i) {
        desiredw = w + two_by_two_walk[2 * i];
        desiredh = h + two_by_two_walk[2 * i + 1];
        if (desiredh < 1 || desiredw < 1) continue;
        na = numaHashGetNuma(classer->nahash, desiredh * desiredw);
      if (!na)
          continue;
        size = numaGetCount(na);
        array = numaGetIArray(na);
        for (j = 0; j < size; ++j) {
          pixt = pixaGetPix(classer->pixat, array[j], L_CLONE);
            if (pixGetWidth(pixt) - 2 * JB_ADDED_PIXELS == desiredw &&
                pixGetHeight(pixt) - 2 * JB_ADDED_PIXELS == desiredh) {
                numaAddNumber(nad, array[j]);
            }
            pixDestroy(&pixt);  /* the clone */
        }
        numaDestroy(&na);  /* the clone */
        FREE((void *)array);
    }

    return nad;
}


/*!
 *  finalPositioningForAlignment()
 *
 *      Input:  pixs (input page image)
 *              x, y (location of UL corner of bb of component in pixs)
 *              idelx, idely (compensation to match centroids of component
 *                            and template)
 *              pixt (template, with JB_ADDED_PIXELS of padding on all sides)
 *              sumtab (for summing fg pixels in an image)
 *              &dx, &dy (return delta on position for best match; each
 *                        one is in the set {-1, 0, 1})
 *      Return: 0 if OK, 1 on error
 *
 */
static l_int32
finalPositioningForAlignment(PIX      *pixs,
                             l_int32   x,
                             l_int32   y,
                             l_int32   idelx,
                             l_int32   idely,
                             PIX      *pixt,
                             l_int32  *sumtab,
                             l_int32  *pdx,
                             l_int32  *pdy)
{
l_int32  w, h, i, j, minx, miny, count, mincount;
PIX     *pixi;  /* clipped from source pixs */
PIX     *pixr;  /* temporary storage */
BOX     *box;

    PROCNAME("finalPositioningForAlignment");

    if (!pixs)
        return ERROR_INT("pixs not defined", procName, 1);
    if (!pixt)
        return ERROR_INT("pixt not defined", procName, 1);
    if (!pdx || !pdy)
        return ERROR_INT("&dx and &dy not both defined", procName, 1);
    if (!sumtab)
        return ERROR_INT("sumtab not defined", procName, 1);
    *pdx = *pdy = 0;

        /* Use JB_ADDED_PIXELS pixels padding on each side */
    w = pixGetWidth(pixt);
    h = pixGetHeight(pixt);
    box = boxCreate(x - idelx - JB_ADDED_PIXELS,
                    y - idely - JB_ADDED_PIXELS, w, h);
    pixi = pixClipRectangle(pixs, box, NULL);
    boxDestroy(&box);
    if (!pixi)
        return ERROR_INT("pixi not made", procName, 1);

    pixr = pixCreate(pixGetWidth(pixi), pixGetHeight(pixi), 1);
    mincount = 0x7fffffff;
    for (i = -1; i <= 1; i++) {
        for (j = -1; j <= 1; j++) {
          pixCopy(pixr, pixi);
          pixRasterop(pixr, j, i, w, h, PIX_SRC ^ PIX_DST, pixt, 0, 0);
          pixCountPixels(pixr, &count, sumtab);
          if (count < mincount) {
              minx = j;
            miny = i;
            mincount = count;
          }
      }
    }
    pixDestroy(&pixi);
    pixDestroy(&pixr);

    *pdx = minx;
    *pdy = miny;
    return 0;
}



Generated by  Doxygen 1.6.0   Back to index