/*  Date of this version: 9/11/2000

    LOCR - Optical Character Recognition
    Version: 0.1.0

    Copyright (C) 2000  <by Miguel A. Lerma>

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/
#define PROGNAME  "LOCR"
#define VER       "0.1.0"
#define COPYRIGHT "by Miguel A. Lerma Copyright (C) 2000"
/*

Examples:

- Recognize characters in "document.pnm" using data from "foo.dat"
(output goes to "document.out"):

     ./locr -d foo.dat document.pnm document.out

- Generate data file "foo.dat" from text file "foo.txt" and image
file "foo.pnm":

     ./locr -gt foo.txt foo.pnm foo.dat

- Same, but also merge data from "foo1.dat":

     ./locr -g -d foo1.dat -t foo.txt foo.pnm foo.dat

- Merge data from "foo1.dat" and "foo2.dat" into "foo3.dat":

     ./locr -g -d foo1.dat -d foo2.dat > foo3.dat

*/


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


#define	MAX(_a,_b) ((_a)<(_b)?(_b):(_a))
#define	MIN(_a,_b) ((_a)<(_b)?(_a):(_b))
#define ABS(_a)    ((_a)<0?-(_a):(_a))

#define TWO_BYTES_TYPE short int
#define IMAG_TYPE TWO_BYTES_TYPE

#define MAX_SCORE       65536
#define MAX_ACCEPTABLE_SCORE 128

#define MAX_IMAGSIZE    16777216
#define MAX_NBLOCKS     32766
#define MAX_NLINES      1000
#define MAX_NCOLS       16

/* fields in table of blocks */

#define TBLK_NFLDS 8  /* number of fields */
#define I1  0         /* i1 = i-coordinate of upper-left corner      */
#define J1  1         /* j1 = j-coordinate of upper-left corner      */
#define I2  2         /* i2 = i-coordinate of lower-right corner + 1 */
#define J2  3         /* j2 = j-coordinate of lower-right corner + 1 */
#define COL 4         /* column                                      */
#define LN  5         /* line                                        */
#define NH  6         /* number of holes                             */
#define HI  7         /* hi = i-coordinate of hot spot               */


/* fields in table of lines */

#define TLN_NFLDS 6   /* number of fields */
/* (fields 0-4 already defined above)
#define I1  0            i1 = i-coordinate of upper-left corner        
#define J1  1            j1 = j-coordinate of upper-left corner        
#define I2  2            i2 = i-coordinate of lower-right corner + 1   
#define J2  3            j2 = j-coordinate of lower-right corner + 1   
#define COL 4            column                                      */
#define FB 5          /* first block in sorted table                 */

/* number of pixels two consecutive lines are allowed to overlap */
#define LINE_OVERLAPPING 2


/* fields in table of columns */

#define TCOL_NFLDS 6  /* number of fields */
/* (fields 0-3,5 already defined above)
#define I1  0            i1 = i-coordinate of upper-left corner        
#define J1  1            j1 = j-coordinate of upper-left corner        
#define I2  2            i2 = i-coordinate of lower-right corner + 1 */
#define FL  4         /* first line                                  
#define FB  5            first block in sorted table                 */


#define MAX_CHAR_WIDTH_FACTOR           10
#define MAX_CHAR_HEIGHT_FACTOR          10
#define MAX_CHAR_HEIGHT_WIDTH_RELATION  20
#define MAX_CHAR_WIDTH_HEIGHT_RELATION  30

#define STD_WIDTH  16   /* standard size of a character */
#define STD_HEIGHT 16


/* fields in table of attributes */

#define NATTRIBS 8    /* number of attributes */
/* (fields 6, 8 already defined above) */
#define NSB   0       /* number of blocks (minus one)                  */
#define HW    1       /* STD_HEIGHT*char_hight/char_width              */
#define BVPOS 2       /* bottom position respect to baseline           */
#define RVPOS 3       /* top position respect to roofline              */
#define TVPOS 4       /* top position respect to top of line           */
#define NUS   5       /* not used                                      
#define NH    6          number of holes                               */
#define HOT   7       /* hot spot position respect to baseline         */


/* maximum number of characters in text file */
#define MAX_NCHARS 2000


/* global variables */

char *program_name;              /* name of this program */

IMAG_TYPE *imag;
int width, height, imagsize;     /* size of the image */

/* tables of data */
unsigned short int   nchars=0;   /* total number of chars in data table    */
unsigned short int   dfnchars=0; /* number of chars from datafile          */
unsigned char        data_ascii[MAX_NCHARS];
TWO_BYTES_TYPE       data_std_size_chars[MAX_NCHARS][STD_HEIGHT];
TWO_BYTES_TYPE       data_attr[MAX_NCHARS][NATTRIBS];

/* table of blocks */
int tblk[MAX_NBLOCKS+1][TBLK_NFLDS];
int lastblock=MAX_NBLOCKS-1;      /* last block (in the table of blocks)  */
int stblk[MAX_NBLOCKS];           /* sorted table of blocks (actually a 
				     table of pointers to the real table) */
int num_of_blocks;                /* number of blocks                     */
int ablkw, ablkh;                 /* average dimensions of a block        */

/* table of lines */
int tln[MAX_NLINES+1][TLN_NFLDS];
int num_of_lines=0;               /* number of lines                      */
int alnw, alnh;                   /* average dimensions of a line         */

/* table of columns */
int tcol[MAX_NCOLS+1][TLN_NFLDS];
int num_of_cols=0;                /* number of columns                    */
int top_i, bottom_i;              /* edges of text                        */

/* table of attributes */
TWO_BYTES_TYPE   tattr[MAX_NBLOCKS+1][NATTRIBS]; 


/* options */

int single_column=0;
int low_ascii=0;
int align_lines=0;
int generate_data=0;
int use_datafile=0;
int use_textfile=0;
int recog_level=9;
int showdata=0;


/* functions */

int  usage_and_exit();
int  getsampletext();
int  getdata();
int  getimag(); 
void process_image();
void cleanborder();
void remove_isolated_pixels();
void alignlines();
int  getblocks();
int  getcolumns();
int  getlines();
void average_all_blocks();
void average_blocks();
int  compactify_tblk();
int  remove_atypical_blocks();
int  clear_atypical_blocks();
void move_block();
void remove_block();
void clear_block();
void join_block();
void permute_block();
int  convert_to_ascii();
int  mk_std_size();
int  mk_std_size_bin();
void put_std_size_char();
void dump_std_size_char();
void dump_data_ascii();
void dump_data_std_size_chars();
void dump_data_attr();
int  fput_twobytes();
int  fget_twobytes();
char dummy();
char recognize_char();
int  compare_pos();
int  hamming_dist();


/* functions mainly for debugging purposes */

char show_char();
char show_std_size_char();
char show_std_size_char_bin();
void show_std_size_bk_bin();
void show_tblk();
void show_stblk();
void show_tln();
void show_tcol();
void show_data_ascii();
void show_data_std_size_chars();
void show_data_attr();
void show_data();
void show_data2();
void dumppic();
void cleanpic();
void display_blocks();


/* obsolete code */

void filter();
int  getlines_old();
int  hamming_dist2();



/********************* main function *********************/

int
main(int argc, char *argv[]) 
{
  int nfiles=0;
  FILE *fi=stdin, *fo=stdout, *fd, *ft;
  char *fni, *fno, *fnd, *fnt;
  int k, n, nn;  /* miscellaneous variables */
  char c, msg[80];

/* scan arguments */
  
  program_name=argv[0];

  fnd = calloc (sizeof(char),strlen(program_name) + 5);
  strcpy(fnd,program_name);
  strcat(fnd,".dat");  /* default data file name */

  for (n=1; n<argc; n++) {
    c=argv[n][0];
    if (c=='-') {      /* flags */
      k=1;
      c=argv[n][k];
      while ((c != '\0') && (k<256)) {
	switch (c) {
	case '0':      /* recognition levels */
	case '1':
	case '2':
	case '3':
	case '4':
	case '5':
	case '6':
	case '7':
	case '8':
	case '9':
	  recog_level=c;
	  break;
	case 'S':      /* show data (for debugging purposes) */
	  showdata=1;
	  break;
	case 'a':      /* realign lines */
	  align_lines=1;
	  break;
	case 'd':      /* use given datafile */
	  use_datafile=1;
	  break;
	case 'g':      /* generate data */
	  generate_data=1;
	  single_column=1;
	  break;
	case 'h':      /* print help */
	  printf("%s  Version %s  %s\n",PROGNAME,VER,COPYRIGHT);
	  usage_and_exit("");
	case 'l':      /* use only low ascii codes */
	  low_ascii=1;
	  break;
	case 'm':      /* input text is multicolumn */
	  single_column=0;
	  break;
	case 's':      /* input text is single column */
	  single_column=1;
	  break;
	case 't':      /* use given textfile */
	  use_textfile=1;
	  break;
	default:
	  sprintf(msg,"unrecognized flag \'%c\'",c);
	  usage_and_exit(msg);
	}
	k++;
	c=argv[n][k];
      }
    }
    else {
      if (use_datafile) {
	fnd = argv[n];
	if ((fd = fopen(fnd,"r")) == NULL) {
	  fprintf(stderr,"Cannot open %s\n",fnd);
	  exit(1);
	}
	getdata(fd);
	fclose(fd);
	use_datafile=0;
      }
      else if (use_textfile) {
	fnt = argv[n];
	if ((ft = fopen(fnt,"r")) == NULL) {
	  fprintf(stderr,"Cannot open %s\n",fnt);
	  exit(1);
	}
	getsampletext(ft);
	fclose(ft);
	use_textfile=0;
      }
      else if (nfiles==0) {       /* first file is input file */
	fni = argv[n];
	if ((fi = fopen(fni,"r")) == NULL) {
	  fprintf(stderr,"Cannot open %s\n",fni);
	  exit(1);
	}
	nfiles++;
      }
      else if (nfiles==1) {  /* second file is output file */
	fno = argv[n];
	if ((fo = fopen(fno,"w")) == NULL) {
	  fprintf(stderr,"Cannot open %s\n",fno);
	  exit(1);
	}
	nfiles++;
      }
      else {                 /* no more files are allowed */
	usage_and_exit("too many files invoked");
      }
    } 
  } /* end scanning arguments */

/* 
Unless we have already loaded data from an specified file,
load the data from the default data file.
*/

  if ((! generate_data) && (dfnchars == 0)) {
    if ((fd = fopen(fnd,"r")) == NULL) {
      fprintf(stderr,"Cannot open %s\n",fnd);
      exit(1);
    }
    getdata(fd);
    fclose(fd);
 }

/* 
Normally the input file 'fi' will contain the scanned text to be
converted to ascii, unless we are generating data, in which case it
will contain the scanned sample text.

The output file 'fo' is usually the destination for the ascii version
of the scanned text, unless we are generating data, in which case it
is the destination for the data.
*/

  if (generate_data) {
    if (nchars > dfnchars) {
      process_image(fi);
      nn = convert_to_ascii(fo,dummy);
      if (showdata) { 
	show_data2();
	exit(0);
      }      
      if (nn != nchars) {
	fprintf(stderr,
		"wrong number of characters in scanned text: %d/%d\n",
		nn,nchars);
	exit(1);
      }
    }                               /* structure of the data file      */
    fput_twobytes(nchars,fo);       /* number of characters            */
    dump_data_ascii(fo);            /* ascii codes of those characters */
    dump_data_std_size_chars(fo);   /* chars at their standard size    */
    dump_data_attr(fo);             /* attributes                     */
  }
  else {
    if (showdata) {
      show_data2();
      exit(0);
    }
    process_image(fi);
    convert_to_ascii(fo,recognize_char);
  }

  fclose(fo);

  return(0);
}



/********************* other functions *********************/


int
usage_and_exit(msg)
char *msg;
{
  if (msg[0]!='\0') fprintf(stderr,"Error: %s\n",msg);
  printf("Usage:\n%s",program_name);
  printf(" [-aghlms] [ -d <datafile> ... ] [ -t <textfile> ]");
  printf(" [<infile> [<outfile>]]\n");
  exit(0);
  return(0);
}



int
getsampletext(f)
FILE *f;
{
  int ic;

  while (((ic=fgetc(f)) != EOF) && (nchars < MAX_NCHARS)) {
    while ((ic == ' ') || 
	   (ic == '\n') || 
	   (ic == '\r') || 
	   (ic == '\t')) ic=fgetc(f);
    if (ic != EOF) {
      data_ascii[nchars++] = ic;
    }
  }
  if (nchars>=MAX_NCHARS) {
    fprintf(stderr,"sample text file is too large\n");
  }

  return(0);
}



int
getdata(f)
FILE *f;
{
  int n0, n, r, ic;

  n0=dfnchars;

  if ((ic=fget_twobytes(f))==EOF) {
    fprintf(stderr,"datafile is too short\n");
    exit(1);
  }
  else {
    dfnchars+=ic;
    if (dfnchars > MAX_NCHARS) {
      fprintf(stderr,"datafile is too large\n");
      exit(1);
    }
  }
  for (n=n0; n<dfnchars; n++) {
    if ((ic=fgetc(f))==EOF) {
      fprintf(stderr,"datafile is too short\n");
      exit(1);
    }
    else {
      data_ascii[n]=ic;
    }
  }
  for (n=n0; n<dfnchars; n++) {
    for (r=0; r<STD_HEIGHT; r++) {
      if ((ic=fget_twobytes(f))==EOF) {
	fprintf(stderr,"datafile is too short\n");
	exit(1);
      }
      else {
	data_std_size_chars[n][r]=ic;
      }
    }
  }
  for (n=n0; n<dfnchars; n++) {
    for (r=0; r<NATTRIBS; r++) {
      if ((ic=fget_twobytes(f))==EOF) {
	fprintf(stderr,"datafile is too short\n");
	exit(1);
      }
      else {
	data_attr[n][r]=ic;
      }
    }
  }
  nchars=dfnchars;
  return(nchars);
}


int
getimage(f)
FILE *f;
{
  char ic;
  char magic[80];
  int k, l, n;

  fscanf(f,"%3s ",magic);

  /* only P1 pbm and P4 pnm formats are recognized */
  if ((strcmp(magic,"P1") != 0) && (strcmp(magic,"P4")) != 0) {
    fprintf(stderr,"File format not recognized\n");
    fclose(f);
    exit(1);
  }

  ic = fgetc(f);

  if (ic == '#') {
    while ( (ic != '\n') && (ic != EOF) ) {
      ic = fgetc(f); 
    }
  }
  else {
    ungetc(ic,f);
  }

  fscanf(f,"%d %d ",&width,&height);

  width = 8*(((width-1)/8)+1);

  if (width*height > MAX_IMAGSIZE) {
    height = MAX_IMAGSIZE/width;
  }

  imagsize = width*height;

  imag = calloc (sizeof(IMAG_TYPE),imagsize); 


  if (strcmp(magic,"P1") == 0) {
    ungetc(' ',f); 
    for (k=0; k<imagsize; k++) { 
      fscanf(f," %d",&n);
      imag[k] = n;
    }
  }
  else if (strcmp(magic,"P4") == 0) {
    for (k=0; k<imagsize; k+=8) { 
      ic = fgetc(f);
      for (l=7; l>=0; l--) {
	imag[k+l] = (0x1 & ic);
	ic = (ic >> 1);
      }
    } 
  }
  else {
    fprintf(stderr,"File format not recognized\n");
    fclose(f);
    exit(1);
  }

  return(0);
}


void
process_image(f)
FILE * f;
{

  getimage(f); 
  fclose(f);

/* clean borders of image */

  cleanborder(0,width,height,imag);

/* remove dust and snow */

  remove_isolated_pixels(width,height,imag);

/* align lines */

  if (align_lines) alignlines();

/* find blocks (connected regions of pixels and boxes enclosing them) */

  getblocks();
  average_all_blocks();

  if (! generate_data) {
    clear_atypical_blocks();  /* this is to remove figures */
    average_all_blocks();     /* reaverage blocks */
  }

/* find columns */

  getcolumns();

/* find lines */

  getlines();

}



void
cleanborder(n,w,h,p)
IMAG_TYPE n;
int w, h;  /* size of rectangle */
IMAG_TYPE * p;  /* pointer to rectangle */
{
  int i, j;

  for (i=0, j=w*(h-1); i<w ; i++, j++) {
    p[i] = n;
    p[j] = n;
  }
  for (i=0, j=w-1; i<w*h ; i+=w, j+=w) {
    p[i]=n;
    p[j]=n;
  }
}


void
remove_isolated_pixels(w,h,p)
int w, h;        /* dimensions of picture */
IMAG_TYPE *p;    /* pointer to picture */
{
  int i, j, k, iw, s;

  for (i=1; i<h-1; i++) {
    iw=i*w;
    for (j=1; j<w-1; j++) {
      s=0;
      k = iw-w+j-1;
      s+=p[k++]; s+=p[k++]; s+=p[k]; 
      k+=w-2;
      s+=p[k++]; k++; s+=p[k]; 
      k+=w-2;
      s+=p[k++]; s+=p[k++]; s+=p[k]; 
      if (s==0) {
	p[iw+j]=0;
      }
      else if (s==8) {
	p[iw+j]=1;
      }
    }
  }
}


void
alignlines()
{
  int i, j, n, opt_n, count, max_count;
  int min_n, max_n;

  max_n=MIN(40,width/50);
  min_n=-max_n;

  /* find slope of near horizontal lines that best go through 
     the image without intersecting any occupied pixel */

  max_count=0;
  for (n=min_n; n<=max_n; n++) {
    count=0;
    for (i=-min_n; i<height-max_n; i++) {
      j=0;
	while ((j<width) && (imag[width*(i+(n*j)/width)+j]==0)) j++;
      if (j>=width) count++;
    }
    if (count > max_count) {
      max_count=count;
      opt_n=n;
    }
  }

  /* rotate picture */

  if (opt_n>0) {
    for (j=0; j<width; j++) {
      for (i=0; i<height-opt_n; i++) {
	imag[width*i+j] = imag[width*(i+(opt_n*j)/width)+j];
      }
    }
  }
  else if (opt_n<0) {
    for (j=0; j<width; j++) {
      for (i=height-1; i>=-opt_n; i--) {
	imag[width*i+j] = imag[width*(i+(opt_n*j)/width)+j];
      }
    }
  }
}


int
getblocks()
{
  int i, j, k, l, n, m, occ, t;


  /* clean table of blocks */

  for (i=0; i<=MAX_NBLOCKS; i++) {
    for(j=0; j<TBLK_NFLDS; j++) {
      tblk[i][j] = 0;
    }
  }

  n=2;     /* blocks 0 and 1 are reserved */
           /* 0 = empty pixel
	      1 = pixel is occupied but not allocated yet */

  /* scan for blocks */

  for (i=1; ((i<height-1) && (n<MAX_NBLOCKS)); i++) {
    k=width*i;
    for (j=1; ((j<width-1) && (n<MAX_NBLOCKS)); j++) {
      if (imag[k+j] > 0) {

	m = imag[k+j];

	if (m == 1) { /* pixel occupied but not assigned yet */
	  /* create a new entry in the table of blocks */
	  while ((tblk[n][I1] != 0) && (n<MAX_NBLOCKS)) n++; 
	  if (n >= MAX_NBLOCKS) {
	    n=2;
	    while (tblk[n][I1] != 0) n++; 
	  }
	  if (n >= MAX_NBLOCKS) {
	    break;
	  }
	  m=n;
	  imag[k+j]=m;
	  tblk[m][I1]=i;
	  tblk[m][J1]=j;
	  tblk[m][I2]=i+1;
	  tblk[m][J2]=j+1;
	}

	l=k+j-1;   /* left pixel */
	if (imag[l] > 1) {
	  if (imag[l] != m) {
	    join_block(m,imag[l]);
	    m=imag[l];
	  }
	}

	l-=width;  /* upper left pixel */
	if (imag[l] > 1) {
	  if (imag[l] != m) {
	    join_block(m,imag[l]);
	    m=imag[l];
	  }
	}

	l++;       /* upper pixel */
	if (imag[l] > 1) {
	  occ=1;  /* occupied (needed for detecting hole) */
	  if (imag[l] != m) {
	    join_block(m,imag[l]);
	    m=imag[l];
	  }
	}
	else {
	  occ=0;  /* not occupied */
	}

	l++;       /* upper right pixel */
	if (imag[l] > 1) {
	  if (imag[l] != m) {
	    join_block(m,imag[l]);
	    m=imag[l];
	  }
	  else if (occ==0) {
	    tblk[m][NH]++;  /* hole detected */
	    tblk[m][HI]=i;  /* i-coordinate of hot spot */
	  }
	}
      }
    }
  }

  /* compactify table of blocks */

  lastblock=MAX_NBLOCKS-1;
  t = compactify_tblk();
  return(t);
}


int
getcolumns()
{
  int col, j, k, n, m, s, ss, th, lth, hth, w, mrg;
  int *p, *q;


  /* find top and bottom edges of text */

  k=0;
  while ((imag[k] == 0) && (k < imagsize)) k++;
  top_i=k/width;
  k=imagsize-1;
  while ((imag[k] == 0) && (k > 0)) k--;
  bottom_i=k/width;


  if (single_column==1) {
    tcol[0][I1]=1;
    tcol[0][J1]=1;
    tcol[0][I2]=height-1;
    tcol[0][J2]=width-1;
    num_of_cols=1;
  }
  else { /* find columns */

    p = calloc(sizeof(int),width);
    q = calloc(sizeof(int),width);

    /* add pixels vertically (p contains the vertical totals) */
    ss=0;
    for (j=0; j<width; j++) {
      s=0;
      for (k=j; k<imagsize; k+=width) {
	if (imag[k]>0) {
	  s++;
	  ss++;
	}
      }
      p[j]=s;
    }

    /* blur results (q contains the blurred totals) */
    mrg=3*ablkw;  /* how much to blur */
    w=width-mrg;
    for (j=0; j<w; j++) {
      s=0;
      for (k=j; k<j+mrg; k++) {
	s+=p[k];
      }
      q[j]=s;
    }

    /* define thresholds */
    th = ss*mrg/width;
    lth=th/3;
    hth=th/2;

    /* separate columns */
    num_of_cols=-1;
    j=0;
    q[0]=0;
    q[width-1]=0;
    while ((j < width) && (num_of_cols <= MAX_NCOLS)) {
      num_of_cols++;
      th=hth;
      /* if vertical pixel count goes above high threshold,
	 then we are at the left edge of a column */
      while ((q[j] < th) && (j < width)) j++;
      while ((p[j] == 0) && (j < width)) j++; /* adjust left edge */
      tcol[num_of_cols][I1]=1;
      tcol[num_of_cols][J1]=j;
      th=lth;
      /* if vertical pixel count goes below low threshold, 
	 then we are at the right edge of a column */
       while ((q[j] > th) && (j < width)) j++;
      tcol[num_of_cols][I2]=height-1;
      tcol[num_of_cols][J2]=j;
    }

    free(p);
    free(q);

  }

  tcol[num_of_cols][I1]=1;
  tcol[num_of_cols][J1]=width;
  tcol[num_of_cols][I2]=height-1;
  tcol[num_of_cols][J1]=width;

  /* assign columns to blocks and sort by columns */

  m=0;

  for (col=0; col<num_of_cols; col++) {
    tcol[col][FB]=m;
    for (n=2; n<=lastblock; n++) {
      if (tblk[n][J1] >= tcol[col][J1]) {
	if (tblk[n][J1] < tcol[col+1][J1]) {
	  tblk[n][COL]=col;
	  stblk[m++]=n;
	}
      }
    }
  }

  tcol[col][FB]=m;

  num_of_blocks=m;

  for (n=2; n<=lastblock; n++) { /* assign columns to blocks */
    k=num_of_cols-1;
    while ((tblk[n][J1] < tcol[k][J1]) && (k >= 0)) k--;
    tblk[n][COL]=k;
  }

  return(num_of_cols);

}



int
getlines()
{
  int col, k, k1, k2, l, n, n1, n2, t;
  int min_line_height;
  int line=0;

  min_line_height=ablkh;


  /* clean table of lines */
  for (l=0; l<MAX_NLINES; l++) {
    for (k=0; k<TLN_NFLDS; k++) tln[l][k]=0;
  }


  for (col=0; ((col<num_of_cols) && (line<MAX_NLINES)); col++) {

    tcol[col][FL]=line;  /* first line in this column */

    /* sort blocks in this column by i-coordinate */

    n1=tcol[col][FB];    /* first block in this column */
    n2=tcol[col+1][FB];  /* first block in next column */
    for (k1=n1; k1<n2-1; k1++) {
      for (k2=k1+1; k2<n2; k2++) {
	if (tblk[stblk[k1]][I1] > tblk[stblk[k2]][I1]) {
	  t=stblk[k1];
	  stblk[k1]=stblk[k2];
	  stblk[k2]=t;
	}
      }
    }

    /* find lines in current column (detect reasonably 
       large jumps in i-coordinates of blocks) */

    tln[line][I1]=tblk[stblk[n1]][I1];
    tln[line][J1]=tcol[col][J1];
    tln[line][I2]=tblk[stblk[n1]][I1]+min_line_height;
    tln[line][J2]=tcol[col][J1];
    tln[line][COL]=col;
    tln[line][FB]=n1;

    for(n=n1; n<n2; n++) {
      if (tblk[stblk[n]][I1] + LINE_OVERLAPPING > tln[line][I2]) {
	line++;
	if (line+1 >= MAX_NLINES) {
	  fprintf(stderr,"Too many lines\n");
	  exit(1);
	}
	tln[line][I1]=tblk[stblk[n]][I1];
	tln[line][J1]=tcol[col][J1];
	tln[line][I2]=tblk[stblk[n]][I1]+min_line_height;
	tln[line][J2]=tcol[col][J1];
	tln[line][COL]=col;
	tln[line][FB]=n;
      }
      if (tln[line][I2] < tblk[stblk[n]][I2]) {
	tln[line][I2]=tblk[stblk[n]][I2];
      }
      if (tln[line][J2] < tblk[stblk[n]][J2]) {
	tln[line][J2]=tblk[stblk[n]][J2];
      }
      tblk[stblk[n]][LN]=line;
    }

    line++;

  }

  tln[line][FB]=num_of_blocks;

  tcol[col][FL]=line;

  num_of_lines=line;

  /* sort blocks in each line by j-coordinate */

  for (l=0; l<num_of_lines; l++) {
    n1=tln[l][FB];
    n2=tln[l+1][FB];
    for (k1=n1; k1<n2-1; k1++) {
      for (k2=k1+1; k2<n2; k2++) {
	if (tblk[stblk[k1]][J1] > tblk[stblk[k2]][J1]) {
	  t=stblk[k1];
	  stblk[k1]=stblk[k2];
	  stblk[k2]=t;
	}
      }
    } 
  }

  return(num_of_lines);

}



int 
compactify_tblk()
{
  int n, m;

  n=2;
  m=lastblock;

  while (n<m) {
    while ((tblk[m][I1] == 0) && (n<m)) { m--; }
    while ((tblk[n][I1] != 0) && (n<m)){ n++; }
    if (n<m) {
      move_block(m,n);
    }
  }

  /* recompute last block */

  while ((tblk[lastblock][I1] == 0) && (1<lastblock)) lastblock--;
  return(lastblock);

}


void
average_all_blocks()  /* average all blocks in the table of blocks */
{
  int w=0, h=0, n;

  for (n=2; n<=lastblock; n++) {
    w+=tblk[n][I2]-tblk[n][I1];
    h+=tblk[n][J2]-tblk[n][J1];
  }
  ablkw = w/(lastblock-1);
  ablkh = h/(lastblock-1);
}



void
average_blocks(n1,n2,paw,pah) /* average only a range of blocks */
int n1, n2;        /* range of blocks in sorted table     */
int *paw, *pah;    /* pointers to average width and height */
{
  int w=0, h=0, n;

  if (n1<n2) {
    for (n=n1; n<n2; n++) {
      w+=tblk[stblk[n]][I2]-tblk[stblk[n]][I1];
      h+=tblk[stblk[n]][J2]-tblk[stblk[n]][J1];
    }
    *paw = w/(n2-n1);
    *pah = h/(n2-n1);
  }
  else {
    *paw = ablkw;
    *pah = ablkh;
  }
}


void 
move_block(m,n)  /* move block m to position n (in the table of blocks) */
int m, n;
{
  int i, j, k, i1, j1, i2, j2;

  if (tblk[n][I1] != 0) {
    remove_block(n);
  }

  i1=tblk[m][I1];
  j1=tblk[m][J1];
  i2=tblk[m][I2];
  j2=tblk[m][J2];
  for (i=i1; i<i2; i++) {
    k=width*i;
    for (j=j1; j<j2; j++) {
      if (imag[k+j] == m) {
	imag[k+j]=n;
      }
    }
  }
  for (k=0; k<TBLK_NFLDS; k++) {
    tblk[n][k] = tblk[m][k];
    tblk[m][k] = 0;
  }
}


int
remove_atypical_blocks()  /* remove blocks with unreasonable dimensions */
{
  int n;

  for (n=2; n<=lastblock; n++) {
    if ((tblk[n][I2]-tblk[n][I1] > ablkw*MAX_CHAR_WIDTH_FACTOR) || 
        (tblk[n][J2]-tblk[n][J1] > ablkh*MAX_CHAR_HEIGHT_FACTOR)) {
      remove_block(n);
    }
  }

  compactify_tblk();

  return(0);
}


int
clear_atypical_blocks()  /* remove atypical blocks and all blocks inside */
{
  int n, w, h;

  for (n=2; n<=lastblock; n++) {
    if (tblk[n][I1]==0) continue;
    h = tblk[n][I2]-tblk[n][I1];
    w = tblk[n][J2]-tblk[n][J1];
    if ((h > ablkh*MAX_CHAR_HEIGHT_FACTOR) || 
        (w > ablkw*MAX_CHAR_WIDTH_FACTOR) ||
	(h > w*MAX_CHAR_HEIGHT_WIDTH_RELATION) ||
	(w > h*MAX_CHAR_WIDTH_HEIGHT_RELATION)) {
      clear_block(n);
    }
  }

  compactify_tblk();

  return(0);
}


void
remove_block(n)   /* remove block n from the table of blocks */
int n;
{
  int i, j, k, i1, j1, i2, j2;

  i1=tblk[n][I1];
  j1=tblk[n][J1];
  i2=tblk[n][I2];
  j2=tblk[n][J2];
  for (i=i1; i<i2; i++) {
    k=width*i;
    for (j=j1; j<j2; j++) {
      if (imag[k+j] == n) {
	imag[k+j]=0;
      }
    }
  }
  for (k=0; k<TBLK_NFLDS; k++) {
    tblk[n][k] = 0;
  }
}


void
clear_block(n)    /* remove block n and all blocks inside it */
int n;
{
  int i, j, k, i1, j1, i2, j2;

  i1=tblk[n][I1];
  j1=tblk[n][J1];
  i2=tblk[n][I2];
  j2=tblk[n][J2];
  for (i=i1; i<i2; i++) {
    k=width*i;
    for (j=j1; j<j2; j++) {
      if (imag[k+j] == n) {
	imag[k+j]=0;
      }
      if (imag[k+j] > 0) {
	clear_block(imag[k+j]);
      }
    }
  }
  for (k=0; k<TBLK_NFLDS; k++) {
    tblk[n][k] = 0;
  }
}


void
join_block(m,n)  /* join block m to n */
int m, n;
{
  int i, j, k, i1, j1, i2, j2;

  if (n != m) {
    i1=tblk[m][I1];
    j1=tblk[m][J1];
    i2=tblk[m][I2];
    j2=tblk[m][J2];
    for (i=i1; i<i2; i++) {
      k=width*i;
      for (j=j1; j<j2; j++) {
	if (imag[k+j] == m) {
	  imag[k+j]=n;
	}
      }
    }
    tblk[n][I1]=MIN(tblk[n][I1],tblk[m][I1]);
    tblk[n][J1]=MIN(tblk[n][J1],tblk[m][J1]);
    tblk[n][I2]=MAX(tblk[n][I2],tblk[m][I2]);
    tblk[n][J2]=MAX(tblk[n][J2],tblk[m][J2]);
    if (tblk[m][NH] > 0) {
      tblk[n][NH]+=tblk[m][NH];
      tblk[n][HI]=MAX(tblk[n][HI],tblk[m][HI]);
    }
    for (k=0; k<TBLK_NFLDS; k++) {
      tblk[m][k] = 0;
    } 
  }
}


void
join_sblock(m,n)  /* join block m to n (in the sorted table) */
int m, n;
{
  tattr[stblk[n]][NSB]+=tattr[stblk[m]][NSB]+1;
  tattr[stblk[n]][NH]+=tattr[stblk[m]][NH];
  join_block(stblk[m],stblk[n]);
}


void
permute_block(m,n) /* permute blocks m and n (in the table of blocks) */
int m, n;
{
  move_block(m,MAX_NBLOCKS);
  move_block(n,m);
  move_block(MAX_NBLOCKS,m);
}




int
convert_to_ascii(f,recog_func)
FILE *f;                  /* file to write to */
char (* recog_func)();    /* recognizing function */
{
  int it, ib, im, i1, i2, ii1, ii2, j1, j2, jj1, jj2, t1, t2, t3;
  int k, l, n, n1, n2, nc, m;
  int aw, ah, gap;
  int hl, bl, rl, ss1, ss2, s1[STD_HEIGHT], s2[STD_HEIGHT];
  char c;
  int nn=dfnchars;  /* position in data tables */

  ib=top_i;
  for (l=0; l<num_of_lines; l++) {
    n1=tln[l][FB];
    n2=tln[l+1][FB];
    average_blocks(n1,n2,&aw,&ah);  /* average blocks in this line */
    it=tln[l][I1]; /* top of current line */
    if (! generate_data) {
      if ((2*(ib-it)+ah)/(2*ah) != 0) {
	/* add blank lines if vertical gap between lines */
	if (! generate_data) fprintf(f,"\n");    
      }
    }
    ib=tln[l][I2];   /* bottom of current line */
    im=(it+ib)/2;    /* middle of current line */
    hl=ib-it;        /* height of current line */
    /* add diacritical signs */
    m=stblk[n1];
    j1=tblk[m][J1];
    j2=tblk[m][J2];
    i1=tblk[m][I1];
    i2=tblk[m][I2];
    for (n=n1+1; n<n2; n++) { /* join horizontally overlapped blocks */
      m=stblk[n];
      jj1=tblk[m][J1];
      jj2=tblk[m][J2];
      ii1=tblk[m][I1];
      ii2=tblk[m][I2];
      if (jj2+jj1 <= 2*j2+2) {
	join_sblock(n-1,n);
      } 
      else if (2*jj1 <= j2+j1+2) {
	join_sblock(n-1,n);
      } /* detect double quote */
      else if ((i2<im) && (ii2<im) && (jj2-j1<=aw)) { 
	join_sblock(n-1,n);
      } /* detect double angle */
      else if (low_ascii == 0) {
	t1=i1-ii1;
	t2=i2-ii2;
	t3=j2-j1-jj2+jj1;
	if ((ABS(t1) <= 1) && (ABS(t2) <= 1) && (ABS(t3) <= 1)) {
	  if (jj2-j1 <= 10*(j2-jj1)) {
	    join_sblock(n-1,n);
	  }
	}
      }
      j1=tblk[m][J1];
      j2=tblk[m][J2];
      i1=tblk[m][I1];
      i2=tblk[m][I2];
    }
    /* find baseline and roofline */
    nc=0;  /* counter for number of characters in current line */
    for (k=0; k<STD_HEIGHT; k++) {
      s1[k]=0;
      s2[k]=0;
    }
    for (n=n1; n<n2; n++) {
      m=stblk[n];
      i1=tblk[m][I1];
      if (i1 == 0) continue;  /* jump over empty blocks */
      i2=tblk[m][I2];
      nc++;                   /* count no. of chars at each position */
      s1[STD_HEIGHT*(ib-i1-1)/hl]++; 
      s2[STD_HEIGHT*(ib-i2)/hl]++; 
    }
    rl=0;              /* roofline */
    ss1=s1[rl];
    /* roofline = median of top positions of characters in current line */
    while ((ss1<<1) < nc) ss1+=s1[++rl];
    bl=0;              /* baseline */
    ss2=s2[bl];
    /* baseline = median of bottom positions of characters in current line */
    while ((ss2<<1) < nc) ss2+=s2[++bl];
    rl=MIN(rl,(3*STD_HEIGHT+bl)/4); /* max value of roof */

    /* recognize characters in the current line */
    j1=tln[l][J1];
    for (n=n1; n<n2; n++) {
      m=stblk[n];
      j2=tblk[m][J1];
      if (j2 == 0) continue;  /* jump over empty blocks */

      /* compute attributes */

      tattr[m][NH] = tblk[m][NH];          /* number of holes    */

      tattr[m][HW] = STD_HEIGHT*(tblk[m][I2] - tblk[m][I1])
	/(tblk[m][J2] - tblk[m][J1]);      /* height/width ratio */

      /* bottom position respect to baseline */
      tattr[m][BVPOS] = STD_HEIGHT*(ib-tblk[m][I2])/hl - bl;

      /* top position respect to roofline */
      tattr[m][RVPOS] = STD_HEIGHT*(ib-tblk[m][I1])/hl - rl;

      /* top position respect to top of line */
      tattr[m][TVPOS] = STD_HEIGHT*(it-tblk[m][I1])/hl;

      /* hot spot position respect to bottom of character */
      if (tblk[m][NH]>0) {
	tattr[m][HOT] = STD_HEIGHT*(tblk[m][I2]-tblk[m][HI])
	  /(tblk[m][I2] - tblk[m][I1]);
      }
      else {
	tattr[m][HOT] = 0;
      }


      if (generate_data) {     /* copy attributes */
	for (k=0; k<NATTRIBS; k++) data_attr[nn][k] = tattr[m][k];
	/* put character at its standard size in the data table */
	put_std_size_char(n,nn);
	/* write character at its standard size 
	   dump_std_size_char(n,f); */
	nn++; 
      }
      else {
	gap=(3*(j2-j1)+2*aw)/(3*aw);
	for (k=0; k<gap; k++) {
	  fprintf(f," ");  /* add spaces if horizontal gap between chars */
	}                  /* print character unless empty */
	if ((c=recog_func(n,recog_level))) fputc(c,f);
      }
      j1=tblk[m][J2];
    }
    if (! generate_data) fprintf(f,"\n");
  }

  return(nn);

}


int
mk_std_size(m,bk)   /* zoom block m to standard size and put it in bk */
int m;
char bk[STD_HEIGHT][STD_WIDTH]; /* matrix of 0 and 1 */
{
  int i, i1, i2, j, j1, j2, k, h, w, a, b;

  i1=tblk[m][I1];
  j1=tblk[m][J1];
  i2=tblk[m][I2];
  j2=tblk[m][J2];
  h=i2-i1;
  w=j2-j1;

  for (a=0; a<STD_HEIGHT; a++) {
    for (b=0; b<STD_WIDTH; b++) {
      bk[a][b]=0;
    }
  }

  for (a=0; a<STD_HEIGHT; a++) {
    for (b=0; b<STD_WIDTH; b++) {
      for (i=i1+(a*h)/STD_HEIGHT; (i-i1)*STD_HEIGHT<(a+1)*h; i++) {
	k = width*i;
	for (j=j1+(b*w)/STD_WIDTH; (j-j1)*STD_WIDTH<(b+1)*w; j++) {
	  if (imag[k+j]==m) bk[a][b]=1;
	}
      }
    }
  }

  return(0);
}


int
mk_std_size_bin(m,bbk) /* same as mk_std_size(), but data are binary */
int m;
TWO_BYTES_TYPE bbk[STD_HEIGHT]; /* array of double bytes */
{
  int i, i1, i2, j, j1, j2, k, h, w, a, b;
  TWO_BYTES_TYPE r;

  i1=tblk[m][I1];
  j1=tblk[m][J1];
  i2=tblk[m][I2];
  j2=tblk[m][J2];
  h=i2-i1;
  w=j2-j1;

  for (a=0; a<STD_HEIGHT; a++) {
    r=0;
    for (b=0; b<STD_WIDTH; b++) {
      r = ( r << 1);
      for (i=i1+(a*h)/STD_HEIGHT; (i-i1)*STD_HEIGHT<(a+1)*h; i++) {
	k = width*i;
	for (j=j1+(b*w)/STD_WIDTH; (j-j1)*STD_WIDTH<(b+1)*w; j++) {
	  if (imag[k+j]==m) r|=1;
	}
      }
    }
    bbk[a]=r;
  }

  return(0);
}



void
put_std_size_char(n,nn)  /* put char at its standard size in data table */
int n, nn;
{
  int k;
  TWO_BYTES_TYPE bbk[STD_HEIGHT];

  mk_std_size_bin(stblk[n],bbk);
  for (k=0; k<STD_HEIGHT; k++) data_std_size_chars[nn][k]=bbk[k];
}


void
dump_std_size_char(n,f)  /* write char to file at its standard size */
FILE * f;
int n;
{
  int k;
  TWO_BYTES_TYPE bbk[STD_HEIGHT];

  mk_std_size_bin(stblk[n],bbk);
  for (k=0; k<STD_HEIGHT; k++) fput_twobytes(bbk[k],f);
}


void
dump_data_ascii(f)  /* write ascii part of data table to file */
FILE * f;
{
  int n;

  for (n=0; n<nchars; n++) fputc(data_ascii[n],f);
}


void
dump_data_std_size_chars(f) /* write char bitmaps from data table to file */
FILE * f;
{
  int n, a;

  for (n=0; n<nchars; n++) {
    for (a=0; a<STD_HEIGHT; a++) {
      fput_twobytes(data_std_size_chars[n][a],f);
    }
  }
}




void
dump_data_attr(f)   /* write attributes from data table to file */
FILE * f;
{
  int k1, k2;

  for (k1=0; k1<nchars; k1++) {
    for (k2=0; k2<NATTRIBS; k2++) {
      fput_twobytes(data_attr[k1][k2],f);
    }
  }
}



int
fput_twobytes(n,f)
FILE * f;
TWO_BYTES_TYPE n;
{
  fputc((n >> 8),f); /* first high */
  fputc(n,f);        /* then low */
  return(0);
}



int
fget_twobytes(f)
FILE * f;
{
  int high, low;

  if ((high=fgetc(f))==EOF) return(EOF);
  if ((low=fgetc(f))==EOF) return(EOF);
  return((high << 8) | low);
}



char
dummy()   /* dummy recognition function */
{
  return(0);
}


char
recognize_char(n,level)
int n, level;
{
  int m, nn;
  int t, t1, t2;
  int ham=0;
  int score, best_nn, best_score;
  TWO_BYTES_TYPE bbk[STD_HEIGHT];

  if (level < 0) return('?');

  m=stblk[n];
  mk_std_size_bin(m,bbk);

  best_nn = 0;
  best_score = MAX_SCORE;

  for (nn=0; nn<nchars; nn++) {

    if (low_ascii) {
      if ((data_ascii[nn]>126) || (data_ascii[nn]<33)) continue;
    }

    if (level >= 1) {
      if (data_attr[nn][NSB] != tattr[m][NSB]) continue;
    }

    if (level >= 2) {
      if (data_attr[nn][NH] != tattr[m][NH]) continue;
      else if (level >= 3) {
	t = data_attr[nn][HOT] - tattr[m][HOT];
	if (ABS(t) > 2) continue;
      }
    }

    if (level >= 4) {
      if (compare_pos(data_attr[nn][BVPOS],tattr[m][BVPOS])) continue;
    }

    if (level >= 9) {
      if (compare_pos(data_attr[nn][RVPOS],tattr[m][RVPOS])) continue;
    }

    if (level >= 6) {
      if (compare_pos(data_attr[nn][TVPOS],tattr[m][TVPOS])) continue;
    }
 
    if (level >= 8) {
      t1 = tattr[m][HW];
      t1 = MAX(t1,4);
      t1 = MIN(t1,96);
      t2 = data_attr[nn][HW];
      t2 = MAX(t2,4);
      t2 = MIN(t2,96);
      if (4*t1 < 3*t2) continue;
      if (3*t1 > 4*t2) continue;
    }

    ham = hamming_dist(bbk,data_std_size_chars[nn]);
    score = ham;

    if (score < best_score) {
      best_nn=nn;
      best_score=score;
    }

  }

/* this piece of code shows in real time how the characters 
   are recognized (only for debugging purposes) */
/*
  printf("%c %d %d\n",data_ascii[best_nn],best_score,level);
  for (k=0; k<NATTRIBS; k++) {
    printf("%3d ",data_attr[best_nn][k]);
  }
  printf("\n");

  for (k=0; k<NATTRIBS; k++) {
    printf("%3d ",tattr[m][k]);
  }
  printf("\n\n");
*/

  /* if the score is low enough, return the guessed character */
  if (best_score <= MAX_ACCEPTABLE_SCORE ){
    return(data_ascii[best_nn]);
  }
  else { /* otherwise, lower level and try again */
    return(recognize_char(n,level-1));
  }
}


int
compare_pos(pos1,pos2)  /* compare two positions and return 0 if */
int pos1, pos2;		/* they are close enough or if they have */
{			/* the same sign beyond some threshold   */
  int t;

  t = pos1-pos2;
  if (ABS(t) < 3) return(0);
  if ((pos1 > 1) && (pos2 > 1)) return(0);
  if ((pos1 < -1) && (pos2 < -1)) return(0);
  return(1);
}


int
hamming_dist(bbk1,bbk2)            /* compute Hamming distance */
TWO_BYTES_TYPE bbk1[STD_HEIGHT];   /* between two characters   */
TWO_BYTES_TYPE bbk2[STD_HEIGHT];
{
  int a, b, r, s;

  s=0;
  for (a=0; a<STD_HEIGHT; a++) {
    r = bbk1[a] ^ bbk2[a];
    for (b=0; b<STD_WIDTH; b++) {
      if (r & 0x1) s++;
      r = (r >> 1);
    }
  }
  return(s);   /* return number of pixels where they differ */
}




/************** functions mainly for debugging purposes *************/


char 
show_char(n)
int n;
{
  int i, i1, i2, j, j1, j2, k, m;

  m=stblk[n];

  if (tblk[m][I1] == 0) return(0);  /* if block is empty return no character */

  i1=tblk[m][I1];
  j1=tblk[m][J1];
  i2=tblk[m][I2];
  j2=tblk[m][J2];

  printf("\n");
  for (i=i1; i<i2; i++) {
    k=width*i;
    for (j=j1; j<j2; j++) {
      if (imag[k+j]==m) {
	printf("O ");
      }
      else {
	printf(". ");
      }
    }
    printf("\n");
  }
  printf("\n");

  return(0);
}



char 
show_std_size_char(n)
int n;
{
  int m, i, j;
  char bk[STD_HEIGHT][STD_WIDTH];

  m=stblk[n];

  if (tblk[m][I1] == 0) return(0);  /* if block is empty return no character */

  mk_std_size(m,bk);

  printf("\n");
  for (i=0; i<STD_HEIGHT; i++) {
    for (j=0; j<STD_WIDTH; j++) {
      if (bk[i][j]) {
	printf("O ");
      }
      else {
	printf(". ");
      }
    }
    printf("\n");
  }
  printf("\n");

  return(0);
}

char
show_std_size_char_bin(n)
int n;
{
  int m;
  TWO_BYTES_TYPE bbk[STD_HEIGHT];

  m=stblk[n];

  if (tblk[m][I1] == 0) return(0);  /* if block is empty return no character */

  mk_std_size_bin(m,bbk);

  show_std_size_bk_bin(bbk);

  return(0);
}

void
show_std_size_bk_bin(bbk)
TWO_BYTES_TYPE bbk[STD_HEIGHT];
{
  int i, j, r;

  printf("\n");
  for (i=0; i<STD_HEIGHT; i++) {
    r=bbk[i];
    for (j=STD_WIDTH-1; j>=0; j--) {
      if ((r >> j) & 0x1) {
	printf("O ");
      }
      else {
	printf(". ");
      }
    }
    printf("\n");
  }
  printf("\n");
}




void
show_tblk()
{
  int n, k;

  for (n=0; n<=lastblock; n++) {
    printf("%-5d ",n);
    for(k=0; k<TBLK_NFLDS; k++) {
      printf("%5d ",tblk[n][k]);
    }
    printf("\n");
  }
}

void
show_stblk()
{
  int n, k;

  for (n=0; n<num_of_blocks; n++) {
    printf("%-5d %-5d ",n,stblk[n]);
    for(k=0; k<TBLK_NFLDS; k++) {
      printf("%5d ",tblk[stblk[n]][k]);
    }
    printf("\n");
  }
}


void
show_tln()
{
  int n, k;

  for (n=0; n<=num_of_lines; n++) {
    printf("%-5d ",n);
    for(k=0; k<TLN_NFLDS; k++) {
      printf("%5d ",tln[n][k]);
    }
    printf("\n");
  }
}


void
show_tcol()
{
  int n, k;

  for (n=0; n<=num_of_cols; n++) {
    printf("%-5d ",n);
    for(k=0; k<TCOL_NFLDS; k++) {
      printf("%5d ",tcol[n][k]);
    }
    printf("\n");
  }
}


void
show_data_ascii()
{
  int n;

  for (n=0; n<nchars; n++) printf("%c\n",data_ascii[n]);
  printf("\n");
}


void
show_data_std_size_chars()
{
  int n, r, a, b;

  for (n=0; n<nchars; n++) {
    for (a=0; a<STD_HEIGHT; a++) {
      r = data_std_size_chars[n][a];
      for (b=STD_WIDTH-1; b>=0; b--) {
	if ((r>>b)&0x1) {
	  printf("O ");
	}
	else {
	  printf(". ");
	}
      }
      printf("\n");
    }
    printf("\n");
  }
  printf("\n");
}


void
show_data_attr()
{
  int k1, k2;

  for (k1=0; k1<nchars; k1++) {
    for (k2=0; k2<NATTRIBS; k2++) {
      printf("%d ",data_attr[k1][k2]);
    }
    printf("\n");
  }
  printf("\n");
}


void
show_data()
{
  printf("%d\n",nchars);
  show_data_ascii();
  show_data_std_size_chars();
  show_data_attr();
}

void
show_data2()
{
  int n, a, b, r, k;

  printf("%d\n\n",nchars);

  for (n=0; n<nchars; n++) {

    printf("%c\n",data_ascii[n]);
    printf("\n");

    for (a=0; a<STD_HEIGHT; a++) {
      r = data_std_size_chars[n][a];
      for (b=STD_WIDTH-1; b>=0; b--) {
	if ((r>>b)&0x1) {
	  printf("O ");
	}
	else {
	  printf(". ");
	}
      }
      printf("\n");
    }
    printf("\n");

    printf("%-5d ",n);
    for (k=0; k<NATTRIBS; k++) {
      printf("%d ",data_attr[n][k]);
    }
    printf("\n\n\n");
  }
}



void
dumppic(w,h,p)
int w, h;       /* size of rectangle     */
IMAG_TYPE * p;  /* pointer to rectangle */
{
  int i, j, k;

  printf("P1\n# my program\n");

  printf("%d %d\n",w,h);
  for (i=0; i<h; i++) {
    k = i*w;
    for (j=0; j<w; j++) {
      printf("%d ",p[k+j]);
    }
    printf("\n");
  }

}



void
cleanpic(w,h,p)
int w, h;
IMAG_TYPE * p;
{
  int i, j, k;

  for (i=0; i<h; i++) {
    k=w*i;
    for (j=0; j<w; j++) {
      p[k+j]=0;
    }
  }
}


void
display_blocks()
{
  int n, i, j, k, i1, j1, i2, j2;
  IMAG_TYPE * p;

  p = calloc (sizeof(IMAG_TYPE),imagsize);

  for (n=2; n<MAX_NBLOCKS; n++) {
    if (tblk[n][I1] != 0) {
      i1=tblk[n][I1];
      j1=tblk[n][J1];
      i2=tblk[n][I2];
      j2=tblk[n][J2];
      for (i=i1; i < i2; i++) { 
	p[width*i+j1]=1;
	p[width*i+j2-1]=1;
      }
       for (j=j1; j < j2; j++) { 
	p[width*i1+j]=1;
	p[width*(i2-1)+j]=1;
      }
    }
  }

  for (k=0; k<num_of_cols; k++) {
    for (i=0; i<height; i++) {
      p[width*i+tcol[k][J1]]=1;
    }
  }

  for (k=0; k<num_of_lines; k++) {
    i1=tln[k][I1];
    i2=tln[k][I2];
    for (j=tln[k][J1]; j<tln[k][J2]; j++) {
      p[width*i1+j]=1;
      p[width*i2+j]=1;
    }
  }

  dumppic(width,height,p);

  free(p);

}  




/********************* obsolete code *********************/


void
filter(a,n,w,h,p)
int a;           /* coefficient           */
int n;           /* threshold             */
int w, h;        /* dimensions of picture */
IMAG_TYPE *p;    /* pointer to picture    */
{
  int i, j, k, iw, s;
  IMAG_TYPE *q;

  q = calloc (sizeof(IMAG_TYPE),w*h);

  for (i=0; i<h; i++) {
    iw=i*w;
    for (j=0; j<w; j++) {
      q[iw+j]=p[iw+j];
    }
  }

  for (i=1; i<h-1; i++) {
    iw=i*w;
    for (j=1; j<w-1; j++) {
      s=0;
      k = iw-w+j-1;
      s+=q[k++]; s+=q[k++]; s+=q[k]; 
      k+=w-2;
      s+=q[k++]; s+=a*q[k++]; s+=q[k]; 
      k+=w-2;
      s+=q[k++]; s+=q[k++]; s+=q[k]; 
      if (s<n) { p[iw+j]=0; } else { p[iw+j]=1; }
    }
  }

  free(q);

}


int
getlines_old()
{
  int col, i, j1, j2, j, k, k1, k2, l, n, n1, n2, t;
  int min_line_height;
  int line=0, lh=0;
  int in_line=0;

  min_line_height=ablkh;

  for (col=0; ((col<num_of_cols) && (line<MAX_NLINES)); col++) {
    tcol[col][FL]=line;  /* first line in this column */
    j1=tcol[col][J1];
    j2=tcol[col+1][J1];
    for (i=0; ((i<height) && (line<MAX_NLINES)); i++, lh++) {
      k=width*i;
      j=j1;
      while ((imag[k+j]==0) && (j<j2)) j++;
      if (!(in_line) && (j<j2)) {
	tln[line][I1]=i;
	tln[line][J1]=j1;
	tln[line][J2]=j2;
	tln[line][COL]=col;
	in_line=1;
	lh=1;
      }
      else if ((in_line) && (j==j2) && (lh>min_line_height)) {
	tln[line][I2]=i;
	in_line=0;
	line++;
      }
    }

    /* assign lines to blocks */

    n1=tcol[col][FB];    /* first block in this column */
    n2=tcol[col+1][FB];  /* first block in next column */
    for (n=n1; n<n2; n++) {
      l=tcol[col][FL];   /* first line in this column */
      while ((tblk[stblk[n]][I2] > tln[l][I2]) && (l<line)) l++;
      tblk[stblk[n]][LN]=l;  /* assign line to block */
    }

    /* sort blocks by line */

    k1=n1;
    for (l=tcol[col][FL]; ((l<line) && (k1<n2)); l++) {
      tln[l][FB]=k1;
      k2=n2-1;
      while (k1<k2) {
	while ((tblk[stblk[k1]][LN]==l) && (k1<k2)) k1++;
	while ((tblk[stblk[k2]][LN]!=l) && (k1<k2)) k2--;
	if (k1<k2) {
	  t=stblk[k1];
	  stblk[k1]=stblk[k2];
	  stblk[k2]=t;
	}
      }
    }
    
  }

  tln[line][FB]=num_of_blocks;

  tcol[col][FL]=line;

  num_of_lines=line;

  /* sort blocks in each line by j-coordinate */

  for (l=0; l<num_of_lines; l++) {
    n1=tln[l][FB];
    n2=tln[l+1][FB];
    for (k1=n1; k1<n2-1; k1++) {
      for (k2=k1+1; k2<n2; k2++) {
	if (tblk[stblk[k1]][J1] > tblk[stblk[k2]][J1]) {
	  t=stblk[k1];
	  stblk[k1]=stblk[k2];
	  stblk[k2]=t;
	}
      }
    } 
  }

  return(num_of_lines);

}



int 
hamming_dist2(bbk1,bbk2)          /* best Hamming distance between 
				     slightly displaced characters */
TWO_BYTES_TYPE bbk1[STD_HEIGHT];
TWO_BYTES_TYPE bbk2[STD_HEIGHT];
{
  int i, a, b, r, s, bs;

  bs = 65536;
  for (i=-1; i<=1; i++) {
    s=0;
    for (a=MAX(0,-i); a<STD_HEIGHT-MAX(0,i); a++) {
      r = bbk1[a] ^ bbk2[a+i];
      for (b=0; b<STD_WIDTH; b++) {
	if (r & 0x1) s++;
	r = (r >> 1);
      }
    }
    bs=MIN(s,bs);
  }
  return(bs);
}