//
// This program takes an image which has already been aligned with the
// horizontal axis, using 'deskew', and attempts to determine the line
// spacing and character spacing within that image.
//
// This is specifically for images of fixed-pitch/fixed character width
// printouts such as old listings of computer printouts.
//
// Limitations: it does not explicitly handle underlined text.  It does
// not handle printers which can do a half-linefeed or characters at a
// half-character offset.
//
// It does not make any assumptions about the sort of OCR to be used, so
// it should support band printers as well as dot-matrix printers, and
// because the segmentation of the letters is independent of the
// letterforms itself, it should have no trouble with dot matrix prints
// where the dots are not touching.  I advise against image-processing
// the input before OCRing in order to leave the most data available
// for the OCR to work with.
//
// A future enhancement would be to use an image clustering algorithm to locate
// similar letters, which would then be merged using an image-stacking algorithm
// in order to recreate an ideal version of the letter to use in the OCR as the
// template to match against.
//
// If the image clustering were good enough, it could identify the entire
// character set, which could then be assigned to each ASCII code either
// by hand or by using cryptology software to effectively decrypt the OCR
// scan of the image, by assuming that the image is a code which is a 1:1
// mapping of the character set.
//
// Note that this would allow us to OCR documents containing non-standard
// characters (such as the IPA character set for phonetics).
//
// Accents should not be a problem as long as the input image is fixed pitch.
// They will fit within the segmentation box and the accented letter can be
// recognised as a complete unit rather than as a letter with a separate
// accent attached.
//
// Finally note that the segmentation into a box should enable easy
// distinguishing of identical glyphs at different positions, i.e. commas
// and apostrophes, or periods vs centered decimal points.
//
// My working theory for the actual OCR part is to generate a solid ideal
// version of each character, and subtract the test character from that
// mask.  Only characters completely within the mask can match, so we'll
// be counting pixels that match and pixels that don't.  Moving the target
// around in a small spiral centered on the initial position should find
// the optimum match position.
//
// Alternatively, or as a backup, I'ld like to also try a neural net to
// recognise text, similar to the many demo examples that recognise
// hand-drawn letters.
//
// You should be aware that the test data (a PDF of the Algol-W source code)
// came from a printer with two idiosyncrasies: 1) The top line of print,
// if present, is slightly offset from the grid of all the other lines.
// I suspect a mechanical issue; and 2) the letters are often very light
// and missing ink - effectively missing pixels in modern parlance.  Some
// letters are entirely missing their right hand side, eg a 0 may look like
// a C !  This problem has not been helped by the fact that the original
// scan appears to be 300x300 bi-level, no greys.
//
// (I do have some different test data but it came from a book that I scanned
// myself so I probably shouldn't include it here, at least not more than
// a few pages for 'fair use' purposes.)
//

// cc -o getlines getlines.c -L/usr/local/netpbm/lib -lnetpbm

// If you've just installed netpbm and are having problems, you may need
// to add LD_LIBRARY_PATH="/usr/local/netpbm/lib" to calls to ./getlines
// ./getlines --verbose \
              --grid \
              --lines \
              --tiles \
              --exact-line-spacing=66 \
              --exact-column-spacing 40.6 \
              --line-offset=12.3 \
              --column-offset=23.4 AW-001.pnm

// ./getlines --verbose \
              --grid \
              --lines \
              --tiles \
              --approx-line-spacing=66 \
              --approx-column-spacing 40.6 \
              AW-001.pnm
//
// This code to find line spacing in a horizontally-aligned image was based
// on my earlier program to determine the angle of rotation needed to straighten
// up a page (and then apply that rotation by using shears).  A lot of that code
// is still here, unused.  (I am using the 'deskew' program now which is better
// than my own code: https://github.com/galfar/deskew/ )

// Input comes from pnm files which are most easily created using ImageMagick's
// convert, e.g. convert image.png pnm:- | ./getlines

// On my home system my libraries are a bit messed up (I have two installations
// of netpbm) so I have to invoke this as:

//   convert image.png pnm:- | ./getlines
// or
//   ./getlines < image.pnm

// Note that if using gdb, you can't pipe data into it - it must be invoked as:

//   gdb ./getlines
//   run < image.pnm


// COMPILE TIME OPTIONS:
//
// Invoke Imagemagick 'convert' to extract the tiles from the aligned image
// rather than our code. #define IM_OUTPUT
//
// Ask for tiles in textual pnm/pgm format rather than .png.  ImageMagick
// 'convert' is used as a filter to create the .png files so avoiding the call
// to 'convert' *should* be faster. #define TEXTTILES
//
// Keeping the default of neither option being set is preferred.  There's little
// need for anyone other than me to tweak these, which is why they are
// compile-time options rather than runtime flags.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifndef FALSE
#define FALSE (0 != 0)
#endif
#ifndef TRUE
#define TRUE (0 == 0)
#endif

// based on pnmshear.c - read a portable anymap and shear it by some angle
//
// Copyright (C) 1989, 1991 by Jef Poskanzer.
//
// Permission to use, copy, modify, and distribute this software and its
// documentation for any purpose and without fee is hereby granted, provided
// that the above copyright notice appear in all copies and that both that
// copyright notice and this permission notice appear in supporting
// documentation.  This software is provided "as is" without express or
// implied warranty.
//

#include <netpbm/pnm.h>
#include <netpbm/shhopt.h>

struct cmdline_info {
  /* All the information the user supplied in the command line, in a form easy
   * for the program to use. */
  const char *infilename; /* Filespec of input file */
  char *basename;
  float row_spacingf, col_spacingf, force_row_spacingf, force_col_spacingf,
      row_offsetf, col_offsetf;
  int row_spacing100, col_spacing100, force_row_spacing100, force_col_spacing100,
      row_offset100, col_offset100;
  int help, linesp, colsp, force_linesp, force_colsp, lineoff, coloff, verbose,
      grid, tiles, linetiles;
};

FILE *ifp;
xel *xelrow;
xel **xelrows;
xel bgxel;
int rows, cols, format;
int row;
xelval maxval;

struct cmdline_info cmdline;

static void parse_command_line(int argc, char **argv,
                               struct cmdline_info *cmdlineP) {
  char *endptr;
  optStruct3 opt;
  unsigned int option_def_index = 0;
  optEntry *option_def = malloc(100 * sizeof(optEntry));

  opt.opt_table = option_def;
  opt.short_allowed = FALSE;
  opt.allowNegNum = TRUE;

  cmdlineP->linesp = FALSE;
  cmdlineP->colsp = FALSE;
  cmdlineP->lineoff = FALSE;
  cmdlineP->coloff = FALSE;
  cmdlineP->verbose = FALSE;
  cmdlineP->help = FALSE;

  cmdlineP->row_spacingf = 0.0;
  cmdlineP->col_spacingf = 0.0;
  cmdlineP->force_row_spacingf = 00;
  cmdlineP->force_col_spacingf = 0.0;
  cmdlineP->row_offsetf = 0.0;
  cmdlineP->col_offsetf = 0.0;

  cmdlineP->row_spacing100 = 0;
  cmdlineP->col_spacing100 = 0;
  cmdlineP->force_row_spacing100 = 0;
  cmdlineP->force_col_spacing100 = 0;
  cmdlineP->row_offset100 = 0;
  cmdlineP->col_offset100 = 0;

  // default line spacing if none found or center of a range (+/-2) to override
  // detected spacing Note that although the spacing can be given as a float,

  OPTENT3('h', "help", OPT_FLAG, NULL,
          &cmdlineP->help, 0);
  OPTENT3(0, "info", OPT_FLAG, NULL,
          &cmdlineP->help, 0);
  OPTENT3('r', "approx-line-spacing", OPT_FLOAT, &cmdlineP->row_spacingf,
          &cmdlineP->linesp, 0);
  OPTENT3('c', "approx-column-spacing", OPT_FLOAT, &cmdlineP->col_spacingf,
          &cmdlineP->colsp, 0);
  OPTENT3('R', "exact-line-spacing", OPT_FLOAT, &cmdlineP->force_row_spacingf,
          &cmdlineP->force_linesp, 0);
  OPTENT3('C', "exact-column-spacing", OPT_FLOAT, &cmdlineP->force_col_spacingf,
          &cmdlineP->force_colsp, 0);
  OPTENT3('y', "line-offset", OPT_FLOAT, &cmdlineP->row_offsetf,
          &cmdlineP->lineoff, 0);
  OPTENT3('x', "column-offset", OPT_FLOAT, &cmdlineP->col_offsetf,
          &cmdlineP->coloff, 0);
  // generate pages with overlaid grid
  OPTENT3('g', "grid", OPT_FLAG, NULL,
          &cmdlineP->grid, 0);
  // generate individual tiles (one character per grid square)
  OPTENT3('t', "tiles", OPT_FLAG, NULL,
          &cmdlineP->tiles, 0);
  OPTENT3('l', "lines", OPT_FLAG, NULL,
          &cmdlineP->linetiles, 0);
  OPTENT3('v', "verbose", OPT_FLAG, NULL,
          &cmdlineP->verbose, 0);

  pm_optParseOptions3(&argc, argv, opt, sizeof(opt), 0);
  if (argc - 1 < 1) {
    cmdlineP->infilename = "-";
    if (cmdlineP->verbose)
      fprintf(stderr, "Processing /dev/stdin\n");
    cmdlineP->infilename = "temp";
    cmdlineP->basename = strdup("temp");
  } else {
    char *p;
    cmdlineP->infilename = argv[1];
    if ((p = strrchr(argv[1], '/')) != NULL) {
      cmdlineP->basename = strdup(p + 1);
    } else
      cmdlineP->basename = strdup(argv[1]);
    if ((p = strrchr(cmdlineP->basename, '.')) != NULL) {
      *p = '\0';
    }

    if (argc - 1 > 1) {
      pm_error("too many arguments (%d).  "
               "The only positional argument is the filespec.",
               argc - 1);
    }
    if (cmdlineP->verbose)
      fprintf(stderr, "Processing %s\n", cmdlineP->infilename);
  }
}

void read_image(int *maxx, int *maxy) {
  /* Read a bitmap, return its size;
     Numbers are inclusive, ie bounds are 0:maxx-1, 0:maxy-1 */

  ifp = pm_openr(cmdline.infilename);

  pnm_readpnminit(ifp, &cols, &rows, &maxval, &format);
  *maxx = cols;
  *maxy = rows;
  xelrows = malloc(rows * sizeof(xel *));

  for (row = 0; row < rows; row += 1) {
    xelrow = pnm_allocrow(cols);
    if (row == 0)
      bgxel = pnm_backgroundxelrow(xelrow, cols, maxval, format);
    pnm_readpnmrow(ifp, xelrow, cols, maxval, format);
    xelrows[row] = xelrow;
  }
}

unsigned int samplepixel(int x, int y) {
  xel *el = &xelrows[y][x];
  int rp = el->r & 255;
  int gp = el->g & 255;
  int bp = el->b & 255;
#ifdef PREV_VERSION
  int c = (rp + gp + bp) / 3;
  /* get the value of a pixel.  For now, apply threshholding and return 0/1 */
  if (c >= 64)
    return (1); /* white */
  return (0);   /* black */
  //  return(2); /* our drawn line for display purposes */
#endif
  return rp + gp + bp;
}

//
// The code below is a DDA trivially adapted from a line-drawing algorithm;
// I have faster algorithms than this - even an anti-aliased one - but
// this is rock-solid reliable code that can be trusted during the debugging
// phase (and also it appears to be fast enough already!)
//
// For this program we don't need a general purpose line - we only use horizontal
// and vertical lines.  However I might as well leave it in as I may decide at
// some futute date that I don't want to straighten the image externally first.
//

int count_white(int x1, int y1, int x2, int y2) {
  /* calculate a DDA from (xl,yb) to (xr,yt). */
  /* instead of plotting pixels, add them up somehow */
  int temp, dx, dy, x, y, x_sign, y_sign, flag;
  int tot = 0;

  dx = abs(x2 - x1);               // Delta of X
  dy = abs(y2 - y1);               // Delta of Y
  if (((dx >= dy) && (x1 > x2)) || // Make sure that first coordinate
      ((dy > dx) && (y1 > y2)))    // is the one with least value
  {
    temp = x1;
    x1 = x2;
    x2 = temp;
    temp = y1;
    y1 = y2;
    y2 = temp;
  };

  if ((y2 - y1) < 0)
    y_sign = -1; // The direction into which Y-coord shall travel
  else
    y_sign = 1; // Same for X

  if ((x2 - x1) < 0)
    x_sign = -1; // ---- " ----
  else
    x_sign = 1; // ---- " ----

  if (dx >= dy) // Which one of the deltas is the greatest one
  {
    for (x = x1, y = y1, flag = 0; x <= x2; x++, flag += dy) // From x1 to x2
    {                 // Also increase the
      if (flag >= dx) // Increase/decrease     // flag (displacement value)
      {               // y!
        flag -= dx;
        y += y_sign;
      };
      tot += samplepixel(x, y); // Plot the pixel
    };
  } else {
    /* This is the same as above, just with x as y and vice versa.*/
    for (x = x1, y = y1, flag = 0; y <= y2; y++, flag += dx) {
      if (flag >= dy) {
        flag -= dy;
        x += x_sign;
      };
      tot += samplepixel(x, y);
    };
  };
  return (tot);
}

void extract(int linenum, int rownum, int x, int y, int dx, int dy,
             const char *fname) {
  //  fprintf(stdout, "Extracting @%d,%d (%d,%d) from %s\n", x, y, dx, dy, fname);
  int row, col;

#define WRITE_PGM 1

#ifdef WRITE_PGM
  // based on example at https://www.geeksforgeeks.org/c-program-to-write-an-image-in-pgm-format/
  
  int i, j, temp = 0;
  int width = dx, height = dy;

  FILE* pgmimg;
  static char file[1024], *filep;
  filep = file;
  filep += sprintf(filep, "tiles/%s", fname);
  filep -= 4;
  filep += sprintf(filep, "/line%03d/col%03d.pgm", linenum, rownum);
  pgmimg = fopen(file, "wb");
  //  fprintf(stderr, "Writing %s\n", file);

  // Writing Magic Number to the File
#ifdef TEXTTILES
  fprintf(pgmimg, "P2\n");  // text
#else
  fprintf(pgmimg, "P5\n");  // binary
#endif
  
  // Writing Width and Height, and maximum gray value
  fprintf(pgmimg, "%d %d\n255\n", width, height);

#ifndef NEVER
  int count = 0;
  for (i = 0; i < height; i++) {
    for (j = 0; j < width; j++) {
      xel *el = &xelrows[y+i][x+j];// remember to check files are the right orientation!
      temp = el->b; // temp = el->r; if (el->g > temp) temp = el->g; if (el->b > temp) temp = el->b;
      // Writing the gray values in the 2D array to the file
#ifdef TEXTTILES
      fprintf(pgmimg, "%d ", temp);
#else
      fputc(temp, pgmimg);
#endif
    }
#ifdef TEXTTILES
    fprintf(pgmimg, "\n");
#else
    // no newlines on binary files
    //fputc('\n', pgmimg);
#endif
  }

#else // !NEVER. I.e. ALWAYS.

  row = 0;
  for (;;) {
    if (dy <= 0)
      break;
    int ix = x, dx2 = dx;
    col = 0;
    for (;;) {
      if (dx2 <= 0)
        break;
      xel *el = &xelrows[y][ix];
      fprintf(pgmimg, "%d ", el->b);
      ix++;
      dx2--;
      col++;
    }
    y++;
    dy--;
    row++;
    fprintf(pgmimg, "\n");
  }
#endif
  fclose(pgmimg); 

#else
  
#ifdef TEXTTILES
  static char file[1024], *filep;
  filep = file;
  filep += sprintf(filep, "tiles/%s", fname);
  filep -= 4;
  filep += sprintf(filep, "/line%03d/col%03d.txt", linenum, rownum);
  FILE *png = fopen(file, "w");
  //  fprintf(stderr, "Writing %s\n", file);
#else
  static char command[1024], *commandp;
  commandp = command;
  commandp += sprintf(commandp, "convert txt: tiles/%s", fname);
  commandp -= 4;
  commandp += sprintf(commandp, "/line%03d/col%03d.png", linenum, rownum);
  FILE *png = popen(command, "w");
  //  fprintf(stderr, "%s\n", command);
#endif

  fprintf(png, "# ImageMagick pixel enumeration: %d,%d,255,rgb\n", dx, dy);

  row = 0;
  for (;;) {
    if (dy <= 0)
      break;
    int ix = x, dx2 = dx;
    col = 0;
    for (;;) {
      if (dx2 <= 0)
        break;
      xel *el = &xelrows[y][ix];
      fprintf(png, "%d,%d: (%d,%d,%d) #\n", col, row, el->b, el->b, el->b);
      ix++;
      dx2--;
      col++;
    }
    y++;
    dy--;
    row++;
  }
#ifdef TEXTTILES
  fclose(png);
#else
  pclose(png);
#endif

#endif // !WRITE_PGM
}

int main(int argc, char **argv) {
  int i, g, x, y, maxx, maxy, group;
  int *xscore, *yscore, *start, *end, *weight, *midpoint, *step;
  long long int *total;
  float rowf, colf, row_offsetf, col_offsetf;
  int rowgap_low, rowgap_high, colgap_low, colgap_high, col_low, col_high;
  float gap;
  int best_gap = -1, best_row_gap_index = 0, best_col_gap_index = 0;

  int smallest_gap, largest_gap;
  int verbose = 0;
  int prev;
  int this, last;
  int highest, lowest;
  int *gapfreq;

  pnm_init(&argc, argv);
  parse_command_line(argc, argv, &cmdline);

  if (cmdline.help) {
    fprintf(stdout, "syntax: getlines [options] filename.png\n\n");
    fprintf(stdout, "options:\n");
    fprintf(stdout, "    --grid                            generate "
                    "grid/filename.png for manual inspection\n");
    fprintf(stdout, "    --lines                           generate "
                    "tiles/filename/line<nnn>.png for manual inspection\n");
    fprintf(stdout,
            "    --tiles                           generate tiles/filename.zip "
            "containing tiles/filename/line<nnn>/col<nnn>.png\n");
    fprintf(stdout, "    --approx-line-spacing <pixels>    limit line spacing "
                    "detection to between +/- 2 of <pixels>\n");
    fprintf(stdout, "    --approx-column-spacing <pixels>  ditto for "
                    "horizontal character spacing within a line\n");
    fprintf(stdout, "    --exact-line-spacing <pixels>     force line spacing "
                    "to exactly nn.n pixels \n");
    fprintf(stdout, "    --exact-column-spacing <pixels>   ditto character "
                    "spacing within a line\n");
    fprintf(stdout, "    --line-offset <pixels>            No. of pixels down "
                    "from top where grid starts\n");
    fprintf(stdout, "    --column-offset <pixels>          No. of pixels in "
                    "from left edge where text starts\n\n");
    fprintf(stdout, "description:\n");
    fprintf(stdout, "    This utility takes an aligned image file and "
                    "determines the line and character spacing\n");
    fprintf(stdout, "    of the text within that file.  It should be "
                    "reasonably independent of the scanning resolution.\n");
    fprintf(stdout, "\n");
    fprintf(stdout, "    It generates an image of the page with a grid "
                    "superimposed, for visual checking, as well as\n");
    fprintf(stdout, "    every character within the page saved separately to "
                    "individual image files, which are returned\n");
    fprintf(stdout, "    as a single .zip file.\n");
    fprintf(stdout, "    Sometimes the automatic detection of line spacing can "
                    "fail, especially on pages containing\n");
    fprintf(stdout, "    very few lines.  In those cases try to limit "
                    "detection to the expected range by looking at the\n");
    fprintf(stdout, "    spacing of other pages within the same document, and "
                    "using the --approx-line-spacing option.\n");
    fprintf(stdout, "    If that fails too, you can resort to forcing an exact "
                    "line spacing with --exact-line-spacing\n");
    fprintf(stdout, "\n");
    fprintf(stdout, "    Note that all pixel dimensions can be given as "
                    "decimals, with tenth of a pixel resolution,\n");
    fprintf(stdout, "    such as --exact-line-spacing 65.3\n");
    fprintf(stdout, "\n");
    fprintf(stdout, "    line offsets and column offsets are treated as exact "
                    "numbers.\n\n");
    exit(0);
  }

  read_image(&maxx, &maxy); /* get width and height of image */
  pm_close(ifp);

  if (cmdline.verbose) {
    fprintf(stderr, "I will be verbose\n");
    if (cmdline.grid)
      fprintf(stderr,
              "I will generate a one-page image with the grid superimposed in "
              "grid/%s.png\n",
              cmdline.basename);
    if (cmdline.linetiles)
      fprintf(stderr,
              "I will save the individual lines in tiles/%s/line*.png\n",
              cmdline.basename);
    if (cmdline.tiles)
      fprintf(stderr, "I will save the individual glyphs in tiles/%s.zip\n",
              cmdline.basename);
  }

  cmdline.row_spacing100 = (int)((cmdline.row_spacingf + 0.001) * 100);
  cmdline.col_spacing100 = (int)((cmdline.col_spacingf + 0.001) * 100);
  cmdline.force_row_spacing100 = (int)((cmdline.force_row_spacingf + 0.001) * 100);
  cmdline.force_col_spacing100 = (int)((cmdline.force_col_spacingf + 0.001) * 100);
  cmdline.row_offset100 = (int)((cmdline.row_offsetf + 0.001) * 100);
  cmdline.col_offset100 = (int)((cmdline.col_offsetf + 0.001) * 100);

  if (cmdline.verbose) {
    if (cmdline.linesp)
      fprintf(stderr, "--approx-line-spacing=%d.%02d\n",
              cmdline.row_spacing100 / 100, cmdline.row_spacing100 % 100);
    if (cmdline.colsp)
      fprintf(stderr, "--approx-column-spacing=%d.%02d\n",
              cmdline.col_spacing100 / 100, cmdline.col_spacing100 % 100);
    if (cmdline.force_linesp)
      fprintf(stderr, "--exact-line-spacing=%d.%02d\n",
              cmdline.force_row_spacing100 / 100,
              cmdline.force_row_spacing100 % 100);
    if (cmdline.force_colsp)
      fprintf(stderr, "--exact-column-spacing=%d.%02d\n",
              cmdline.force_col_spacing100 / 100,
              cmdline.force_col_spacing100 % 100);
    if (cmdline.lineoff)
      fprintf(stderr, "--line-offset=%d.%02d\n", cmdline.row_offset100 / 100,
              cmdline.row_offset100 % 100);
    if (cmdline.coloff)
      fprintf(stderr, "--column-offset=%d.%02d\n", cmdline.col_offset100 / 100,
              cmdline.col_offset100 % 100);

    fprintf(stderr, "%s %dx%d\n", cmdline.infilename, maxx, maxy);
  }

  // I have deliberately duplicated the code below so that X and Y are handled
  // separately. They *could* be merged into one by adding another dimension to
  // most arrays for [x] and [y] indicies, but I thought it more readable to
  // keep them separate, and also I'm expecting that some tweaking might be
  // necessary for handling rows that is not applicable to handling colums, in
  // the future.

  // ============================================================================================================
  // ROUGHLY LOCATE Y SEPARATION

  // This goes wrong in roughly 1 in 40 pages, where it can find a line
  // separation that is 200% of what it should be. This can be corrected on a
  // second pass after generated the majority of the pages - we can go back and
  // regenerate any pages whose separations were far from the mean. These errors
  // tend to happen on pages with only a few lines (eg 3 to 5) *or* on pages
  // that are mostly or completely double-spaced.  In the case of double
  // spacing, you'll get the correct OCR anyway but it is still worth fixing up
  // on a second pass as suggested above.

  xscore = malloc((maxx + 1) * sizeof(int));
  yscore = malloc((maxy + 1) * sizeof(int));
  start = malloc((maxy + 1) * sizeof(int));
  end = malloc((maxy + 1) * sizeof(int));
  weight = malloc((maxy + 1) * sizeof(int));
  midpoint = malloc((maxy + 1) * sizeof(int));
  step = malloc((maxy + 1) * sizeof(int));

  prev = yscore[0];
  last = '=';
  highest = -1;
  lowest = 0x7FFFFFFF;
  gapfreq = NULL;

  for (y = 0; y < maxy; y++) {
    /* draw a line from 0,0 to maxx,y for all y */
    yscore[y] = count_white(0, y, maxx - 1, y);
    // if (cmdline.verbose) fprintf(stderr, "yscore[%d] = %d\n", y, yscore[y]);
    last = this;
    this = yscore[y] < prev ? '/' : (yscore[y] > prev ? '\\' : '=');
    prev = yscore[y];
    if (yscore[y] > highest)
      highest = yscore[y];
    if (yscore[y] < lowest)
      lowest = yscore[y];
  }
  if (cmdline.verbose)
    fprintf(stderr, "lowest = %d\n", lowest);
  for (y = 0; y < maxy; y++) {
    yscore[y] -= lowest;
    yscore[y] = (yscore[y] * 80) / (highest - lowest);
    yscore[y] -= 70;
    if (yscore[y] < 0)
      yscore[y] = 0;
  }

  // Identify groups
  group = 0;
  y = 0;
  for (;;) {
    if (y == maxy)
      break;
    if (yscore[y] > 0) {
      // Start of a group
      start[group] = y;
      for (;;) {
        y += 1;
        if (y == maxy) {
          break;
        }
        if (yscore[y] == 0) {
          break;
        }
      }
      end[group] = y;
      weight[group] = 0;
      for (y = start[group]; y < end[group]; y++) {
        weight[group] += yscore[y];
      }
      y -= 1;
      group += 1;
    }
    y += 1;
  }

  if (group == 0) {
    fprintf(stderr, "Cannot find obvious lines in %s\n", cmdline.infilename);
    exit(1);
  }

  for (g = 0; g < group; g++) {
    midpoint[g] = start[g] / 2 + end[g] / 2;
    if (g > 0)
      step[g] = midpoint[g] - midpoint[g - 1];
  }

  smallest_gap = 0x7FFFFFFF;
  largest_gap = -1;
  gap = 0.0;
  for (g = group == 4 ? 3 : 0; g < (group > 0 ? group : 1) - 1; g++) {
    if (step[g] < smallest_gap)
      smallest_gap = step[g];
    if (step[g] > largest_gap)
      largest_gap = step[g];
    gap += step[g];
  }
  gap /= (group - 1 - 3 + 1);

  if (!cmdline.linesp) { // Hint?

    gapfreq = malloc(sizeof(int) * (largest_gap - smallest_gap + 1));
    for (i = smallest_gap; i <= largest_gap; i++) {
      gapfreq[i - smallest_gap] = 0;
    }

    for (g = 3; g < group - 1; g++) {
      if (step[g] < smallest_gap)
        smallest_gap = step[g];
      if (step[g] > largest_gap)
        largest_gap = step[g];
      gap += step[g];
    }

    for (g = 3; g < group - 1; g++) {
      int gp = step[g];
      gapfreq[gp - smallest_gap] += 1;
    }

    if (cmdline.verbose) {
      fprintf(stderr, "Smallest gap = %d\n", smallest_gap);
      fprintf(stderr, "Largest gap = %d\n", largest_gap);
    }

    for (i = smallest_gap; i <= largest_gap; i++) {
      if (gapfreq[i - smallest_gap] > best_gap) {
        best_gap = gapfreq[i - smallest_gap];
        best_row_gap_index = i;
      }
    }
    rowgap_low = (best_row_gap_index - 1);
    rowgap_high = (best_row_gap_index + 1);
    if (cmdline.verbose)
      printf("We shall use a line spacing between %d and %d pixels\n",
             rowgap_low, rowgap_high);

  } else {

    rowgap_low = (cmdline.row_spacing100 - 200) / 100;
    rowgap_high = (cmdline.row_spacing100 + 290) / 100;
    best_row_gap_index = cmdline.row_spacing100 / 100;
    if (cmdline.verbose)
      printf("We shall use a line spacing between %d and %d (%d.%02d and "
             "%d.%02d) pixels\n",
             rowgap_low, rowgap_high, (cmdline.row_spacing100 / 100) - 2,
             (cmdline.row_spacing100 % 100), (cmdline.row_spacing100 / 100) + 2,
             (cmdline.row_spacing100 % 100));
    /*
      NOTE: if the page is essentially blank (eg only 3 lines of text) then all
      the gaps are the same and the returned 'best' is the lowest value of the
      range.  I think it would be better to use the median of the two extremes,
      especially when using the --approx-line/column-spacing options.
     */
  }

  // ------------------------------------------------------------------------------------------------------------
  // NOW DO THE SAME FOR X!

  // This goes wrong in roughly 1 in 40 pages, where it usually finds a column
  // separation that is 50% or 33% of what it should be. This can be corrected
  // on a second pass after generated the majority of the pages - we can go back
  // and regenerate any pages whose separations were far from the mean.

  if (start) {
    free(start);
    start = NULL;
  }
  if (end) {
    free(end);
    end = NULL;
  }
  if (weight) {
    free(weight);
    weight = NULL;
  }
  if (midpoint) {
    free(midpoint);
    midpoint = NULL;
  }
  if (step) {
    free(step);
    step = NULL;
  }

  start = malloc((maxx + 1) * sizeof(int));
  end = malloc((maxx + 1) * sizeof(int));
  weight = malloc((maxx + 1) * sizeof(int));
  midpoint = malloc((maxx + 1) * sizeof(int));
  step = malloc((maxx + 1) * sizeof(int));

  prev = xscore[0];
  this = 0;
  last = '=';
  highest = -1;
  lowest = 0x7FFFFFFF;

  for (x = 0; x < maxx; x++) {
    /* draw a line from x,0 to x,maxy for all x */
    xscore[x] = count_white(x, 0, x, maxy - 1);
    // if (cmdline.verbose) fprintf(stderr, "xscore[%d] = %d\n", x, xscore[x]);
    last = this;
    this = xscore[x] < prev ? '/' : (xscore[x] > prev ? '\\' : '=');
    prev = xscore[x];
    if (xscore[x] > highest)
      highest = xscore[x];
    if (xscore[x] < lowest)
      lowest = xscore[x];
  }
  for (x = 0; x < maxx; x++) {
    xscore[x] -= lowest;
    xscore[x] = (xscore[x] * 80) / (highest - lowest);
    xscore[x] -= 70;
    if (xscore[x] < 0)
      xscore[x] = 0;
  }

  // Identify groups
  group = 0;
  x = 0;
  for (;;) {
    if (x == maxx)
      break;
    if (xscore[x] > 0) {
      // Start of a group
      start[group] = x;
      for (;;) {
        x += 1;
        if (x == maxx) {
          break;
        }
        if (xscore[x] == 0) {
          break;
        }
      }
      end[group] = x;
      weight[group] = 0;
      for (x = start[group]; x < end[group]; x++) {
        weight[group] += xscore[x];
      }
      x -= 1;
      group += 1;
    }
    x += 1;
  }

  for (g = 0; g < group; g++) {
    midpoint[g] = start[g] / 2 + end[g] / 2;
    if (g > 0)
      step[g] = midpoint[g] - midpoint[g - 1];
  }

  smallest_gap = 0x7FFFFFFF;
  largest_gap = -1;
  gap = 0.0;
  for (g = 3; g < group - 1; g++) {
    if (step[g] < smallest_gap)
      smallest_gap = step[g];
    if (step[g] > largest_gap)
      largest_gap = step[g];
    gap += step[g];
  }
  gap /= (group - 1 - 3 + 1);

  if (gapfreq) {
    free(gapfreq);
    gapfreq = NULL;
  }

  if (!cmdline.colsp) { // Hint?

    gapfreq = malloc(sizeof(int) * (largest_gap - smallest_gap + 1));
    for (i = smallest_gap; i <= largest_gap; i++) {
      gapfreq[i - smallest_gap] = 0;
    }

    for (g = 3; g < group - 1; g++) {
      if (step[g] < smallest_gap)
        smallest_gap = step[g];
      if (step[g] > largest_gap)
        largest_gap = step[g];
      gap += step[g];
    }

    for (g = 3; g < group - 1; g++) {
      int gp = step[g];
      gapfreq[gp - smallest_gap] += 1;
    }

    best_gap = -1;
    best_col_gap_index = 0;
    for (i = smallest_gap; i <= largest_gap; i++) {
      if (gapfreq[i - smallest_gap] > best_gap) {
        best_gap = gapfreq[i - smallest_gap];
        best_col_gap_index = i;
      }
    }

    colgap_low = (best_col_gap_index - 1);
    colgap_high = (best_col_gap_index + 1);
    if (cmdline.verbose)
      printf("We shall use a column spacing between %d and %d pixels\n",
             colgap_low, colgap_high);

  } else {

    best_col_gap_index = cmdline.col_spacing100 / 100;
    colgap_low = (cmdline.col_spacing100 - 200) / 100;
    colgap_high = (cmdline.col_spacing100 + 290) / 100;
    if (cmdline.verbose)
      printf("We shall use a column spacing between %d and %d (%d.%02d and "
             "%d.%02d) pixels\n",
             colgap_low, colgap_high, (cmdline.col_spacing100 / 100) - 2,
             cmdline.col_spacing100 % 100, (cmdline.col_spacing100 / 100) + 2,
             cmdline.col_spacing100 % 100);
  }

  // ============================================================================================================

  // ------------------------------------------------------------------------------------------------------------
  // Now fine-tune the row separation to sub-pixel (1/100th of a pixel)
  // precision.

  int row_separation100, row_offset100, actual_row100;
  int actual_row;
  float actual_rowf;

  int rowtot100[(rowgap_high - rowgap_low) * 100 + 1][(rowgap_high)*100 + 1];

  for (row_separation100 = rowgap_low * 100; row_separation100 <= rowgap_high * 100;
       row_separation100 += 1) {
    for (row_offset100 = 0; row_offset100 < row_separation100; row_offset100 += 1) {
      rowtot100[row_separation100 - rowgap_low * 100][row_offset100] = 0;
    }
  }

  for (row_separation100 = rowgap_low * 100; row_separation100 <= rowgap_high * 100;
       row_separation100 += 1) {
    rowf = (float)row_separation100 / 100.0;
    // find the best separation between lines from rowf offset by row_offsetf
    // truncate for now though rounding would be better.
    for (row_offset100 = 0; row_offset100 < row_separation100; row_offset100 += 1) {
      row_offsetf = (float)row_offset100 / 100.0;
      // having got both a row gap and an offset, add up the cost of the entire
      // page using those parameters

      actual_rowf = row_offsetf;
      actual_row100 = row_offset100;
      for (;;) {
        actual_rowf = (float)actual_row100 / 100.0;
        actual_row = actual_row100 / 100;
        if (actual_row >= maxy)
          break;
        rowtot100[row_separation100 - (rowgap_low * 100)][row_offset100] +=
            yscore[actual_row];
        actual_row100 += row_separation100;
      }
    }
  }

  int best_row_score = 0;
  int best_row_separation100 = 0;
  int best_row_offset100 = 0;

  for (row_separation100 = rowgap_low * 100; row_separation100 <= rowgap_high * 100;
       row_separation100 += 1) {
    for (row_offset100 = 0; row_offset100 < row_separation100; row_offset100 += 1) {
      if (rowtot100[row_separation100 - rowgap_low * 100][row_offset100] >
          best_row_score) {
        best_row_score =
            rowtot100[row_separation100 - rowgap_low * 100][row_offset100];
        best_row_separation100 = row_separation100;
        best_row_offset100 = row_offset100;
      }
    }
  }

  if (best_row_offset100 >= best_row_separation100) {
    // correct an earlier fencepost error :-/
    best_row_offset100 -= best_row_separation100;
  }

  // ------------------------------------------------------------------------------------------------------------
  // And fine-tune the more important column separation to sub-pixel (1/10th of
  // a pixel) precision.

  int col_separation100, col_offset100, actual_col100;
  int actual_col;
  float actual_colf;
  // shrink this by adding -colgap_low to every array access *after this test
  // works*
  //int coltot100[(colgap_high - colgap_low) * 100 + 1][colgap_high * 100 + 1];
  int **coltot100;
  coltot100 = malloc(((colgap_high - colgap_low) * 100 + 1) * sizeof(int *));
  if (coltot100 == NULL) {
    fprintf(stderr, "malloc failed at line %d\n", __LINE__-2); exit(EXIT_FAILURE);
  }
  for (i = 0; i < (colgap_high - colgap_low) * 100 + 1; i++) {
    coltot100[i] = malloc((colgap_high * 100 + 1) * sizeof(int));
    if (coltot100[i] == NULL) {
      fprintf(stderr, "malloc failed at line %d\n", __LINE__-2); exit(EXIT_FAILURE);
    }
  }

  for (col_separation100 = colgap_low * 100; col_separation100 <= colgap_high * 100;
       col_separation100 += 1) {
    for (col_offset100 = 0; col_offset100 < col_separation100; col_offset100 += 1) {
      coltot100[col_separation100 - colgap_low * 100][col_offset100] = 0;
    }
  }

  for (col_separation100 = colgap_low * 100; col_separation100 <= colgap_high * 100;
       col_separation100 += 1) {
    colf = (float)col_separation100 / 100.0;
    // find the best separation between lines from colf offset by col_offsetf
    // truncate for now though rounding would be better.
    for (col_offset100 = 0; col_offset100 < col_separation100; col_offset100 += 1) {
      col_offsetf = (float)col_offset100 / 100.0;
      // having got both a col gap and an offset, add up the cost of the entire
      // page using those parameters

      actual_colf = col_offsetf;
      actual_col100 = col_offset100;
      for (;;) {
        actual_colf = (float)actual_col100 / 100.0;
        actual_col = actual_col100 / 100;
        if (actual_col >= maxx)
          break;
        coltot100[col_separation100 - (colgap_low * 100)][col_offset100] +=
            xscore[actual_col];
        actual_col100 += col_separation100;
      }
    }
  }

  int best_col_score = 0;
  int best_col_separation100 = 0;
  int best_col_offset100 = 0;

  for (col_separation100 = colgap_low * 100; col_separation100 <= colgap_high * 100;
       col_separation100 += 1) {
    for (col_offset100 = 0; col_offset100 < col_separation100; col_offset100 += 1) {
      if (coltot100[col_separation100 - colgap_low * 100][col_offset100] >
          best_col_score) {
        best_col_score =
            coltot100[col_separation100 - colgap_low * 100][col_offset100];
        best_col_separation100 = col_separation100;
        best_col_offset100 = col_offset100;
      }
    }
  }

#define HUGE_STRING (2 * 1024 * 1024)
  char *command, *commandp;
  command = malloc(HUGE_STRING);
  if (command == NULL) {
    fprintf(stderr, "getlines: failed to malloc %d bytes for command\n", HUGE_STRING);
    exit(EXIT_FAILURE);
  }
  
  if (best_col_offset100 >= best_col_separation100) {
    // correct an earlier fencepost error :-/
    best_col_offset100 -= best_col_separation100;
  }

  // printf("We shall look for a line spacing between %d and %d pixels\n",
  // best_row_gap_index-1, best_row_gap_index+1);
  if (cmdline.force_linesp) {
    best_row_separation100 = (int)((cmdline.force_row_spacingf + 0.001) * 100);
  }
  if (cmdline.force_colsp) {
    best_col_separation100 = (int)((cmdline.force_col_spacingf + 0.001) * 100);
  }
  if (cmdline.lineoff) {
    best_row_offset100 = (int)((cmdline.row_offsetf + 0.001) * 100);
  }
  if (cmdline.coloff) {
    best_col_offset100 = (int)((cmdline.col_offsetf + 0.001) * 100);
  }
  if (cmdline.verbose)
    printf("Best row separation is %d.%02d pixels, best offset is %d.%02d\n",
           best_row_separation100 / 100, best_row_separation100 % 100,
           best_row_offset100 / 100, best_row_offset100 % 100);
  // printf("We shall look for a column spacing between %d and %d pixels\n",
  // best_col_gap_index-1, best_col_gap_index+1);
  if (cmdline.verbose)
    printf("Best col separation is %d.%02d pixels, best offset is %d.%02d\n",
           best_col_separation100 / 100, best_col_separation100 % 100,
           best_col_offset100 / 100, best_col_offset100 % 100);

  if (!cmdline.grid && !cmdline.linetiles &&
      !cmdline.tiles) { // --grid --lines --tiles
    fprintf(
        stderr,
        "Warning: unless one of --grid, --lines, or --tiles is specified,\n");
    fprintf(stderr, "         nothing of interest will be done!\n\n");
    exit(0);
  }

  // ============================================================================================================
  // DRAW GRID.  Later we will extract the individual letters here.

  if (cmdline.grid) {
    commandp = command;
    if ((commandp - command) > HUGE_STRING - 512) {
      fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
              __LINE__);
    }
    commandp += sprintf(command,
                        "convert %s -fill none -stroke black -strokewidth 1 "
                        "-draw \"stroke-opacity 1 path '",
                        cmdline.infilename);

    // vertical lines first
    actual_col100 = best_col_offset100;
    for (;;) {
      actual_col = actual_col100 / 100;
      if (actual_col >= maxx)
        break;
      if ((commandp - command) > HUGE_STRING - 512) {
        fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
                __LINE__);
      }
      commandp += sprintf(commandp, "M %0d,0 L %0d,%0d ", actual_col100 / 100,
                          actual_col100 / 100, maxy);
      actual_col100 += best_col_separation100;
    }

    // then horizontals
    actual_row100 = best_row_offset100;
    for (;;) {
      actual_row = actual_row100 / 100;
      if (actual_row >= maxy) break;
      if ((commandp - command) > HUGE_STRING - 512) {
        fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
                __LINE__);
      }
      commandp += sprintf(commandp, "M 0,%0d L %0d,%0d ", actual_row100 / 100,
                          maxx, actual_row100 / 100);
      actual_row100 += best_row_separation100;
    }

    if ((commandp - command) > HUGE_STRING - 512) {
      fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
              __LINE__);
    }
    commandp += sprintf(commandp, "'\" grid/%s",
                        cmdline.basename); // hard-coded for now. Fix later.
    if ((commandp - command) > HUGE_STRING - 512) {
      fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
              __LINE__);
    }
    commandp +=
        sprintf(commandp, "@%d,%d@%d,%d", best_col_separation100,
                best_row_separation100, best_col_offset100, best_row_offset100);
    if ((commandp - command) > HUGE_STRING - 512) {
      fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
              __LINE__);
    }
    commandp += sprintf(commandp, ".png");
    if (cmdline.verbose)
      fprintf(stderr, "%s\n", command);
    system(command);
    if (!cmdline.linetiles && !cmdline.tiles) { // --grid --lines --tiles
      exit(0);
    }
  }

  if ((best_row_separation100 + 9) / 100 < 10) {
    fprintf(stderr,
            "Error: auto-detected line separation (%d pixels) is implausibly "
            "low -\n",
            (best_row_separation100 + 9) / 100);
    fprintf(stderr,
            "       I suggest re-running with --approx-line-spacing=<nn> or "
            "--exact-line-spacing=<nn.n> option.\n");
    fprintf(stderr, "\n");
    fprintf(stderr, "       You can find a plausible spacing by looking at "
                    "other pages in the grid/ directory - if you\n");
    fprintf(stderr, "       see filenames like AW-009@399,661@0,20.png, then "
                    "that suggests a column spacing of 39.9 and\n");
    fprintf(stderr, "       a row spacing of 66.1.  You could try "
                    "--approx-line-spacing=66 or --exact-line-spacing=66.1\n");
    fprintf(stderr, "\n");
    fprintf(stderr, "       If you use the --exact-line-spacing= option, "
                    "you'll need to work out the --line-offset=\n");
    fprintf(stderr, "       parameter manually, by trial and error.  If "
                    "--approx-line-spacing= works OK, the line offset\n");
    fprintf(stderr, "       ought to discoverable automatically.\n\n");
    exit(1);
  }

  // To extract the individual characters, first split into rows (in a
  // subdirectory) and then take each of the row files and split into columns
  // (in a sub-sub-directory). Note we'll need a *fast* way of eliminating white
  // space characters...

  // *** THIS IS NOT FAST *** :-(  Should be rewritten to extract from image
  // already in store.  This implementation is really only here as a placeholder
  // during development...

  // ============================================================================================================
  // First, loop over lines...
  actual_row100 = best_row_offset100;
  int line = 1;
  for (;;) {
    actual_row = actual_row100 / 100;
    if ((actual_row100 + best_row_separation100 + 100) / 100 >= maxy)
      break;

    commandp = command;
    if ((commandp - command) > HUGE_STRING - 512) {
      fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
              __LINE__);
    }
    commandp += sprintf(commandp, "mkdir -p tiles/%s", cmdline.basename);

    if (cmdline.linetiles) {
      if ((commandp - command) > HUGE_STRING - 512) {
        fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
                __LINE__);
      }
      commandp += sprintf(
          commandp,
          "/line%03d ; convert -extract %dx%d+%d+%d +repage %s tiles/%s", line,
          maxx - 1, (best_row_separation100 + 9) / 100, /* round up */
          0, actual_row100 / 100,                       /* round down */
          cmdline.infilename, cmdline.basename);
      if ((commandp - command) > HUGE_STRING - 512) {
        fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
                __LINE__);
      }
      commandp += sprintf(commandp, "/line%03d.png", line);
      if (cmdline.verbose)
        fprintf(stderr, "%s\n", command);
      system(command);
    }

    // chars next
    actual_col100 = best_col_offset100;
    int column = 1;
    for (;;) {
      actual_col = actual_col100 / 100;
      if ((actual_col100 + best_col_separation100 + 100) / 100 >= maxx)
        break;

      commandp = command;
      commandp += sprintf(commandp, "mkdir -p tiles/%s", cmdline.basename);
      if ((commandp - command) > HUGE_STRING - 512) {
        fprintf(stderr, "I think we\'re about to go \'Boom!' at line %d...\n",
                __LINE__);
      }
      commandp += sprintf(commandp, "/line%03d", line);

#ifdef IM_OUTPUT // direct extraction using ImageMagick convert, rather than
                 // extraction using local code with possible conversion to png
                 // by ImageMagick
                 // - simple writing of the tiles directly as ImageMagick format
                 // text files with no calls to ImageMagick involved (which
                 // should be faster).
      commandp += sprintf(commandp,
                          " ; convert -extract %dx%d+%d+%d +repage %s tiles/%s",
                          (best_col_separation100 + 9) / 100,
                          (best_row_separation100 + 9) / 100,     /* round up */
                          actual_col100 / 100, actual_row100 / 100, /* round down */
                          cmdline.infilename, cmdline.basename);
      commandp -= 4;
      commandp += sprintf(commandp, "/line%03d/col%03d.png", line, column);
      fprintf(stderr, "%s\n", command);
      if (cmdline.verbose)
        if (column == 1)
          fprintf(stderr, "%s\n", command);
#endif
      system(command);

      if (cmdline.grid)
        extract(line, column, actual_col100 / 100, actual_row100 / 100,
                (best_col_separation100 + 9) / 100,
                (best_row_separation100 + 9) / 100, cmdline.infilename);

      actual_col100 += best_col_separation100;
      column += 1;
    }

    actual_row100 += best_row_separation100;
    line += 1;
  }

  exit(0);
  return 0;
}