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

patternm_text.c

/* $Id: patternm_text.c,v 1.32 2009-01-27 16:27:03 potyra Exp $ 
 *
 * Copyright (C) 2007-2009 FAUmachine Team <info@faumachine.org>.
 * This program is free software. You can redistribute it and/or modify it
 * under the terms of the GNU General Public License, either version 2 of
 * the License, or (at your option) any later version. See COPYING.
 */


#include "config.h"

#ifdef DEFINITIONS

/* ******************** definitions **************************** */


#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <dirent.h>
#include <errno.h>
#include <string.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>

#include "glue-log.h"
#include "samples.h"
#include "ttf_samples.h"


/* the maximum number of hypotheses taken for a character if some classes have
 * equally high propability (e.g. '1' 'I' 'l') */
#define MAX_CHAR_HYPOTHESES         3
/* the maximum number characters per text_area for which memory is allocated */
#define MAX_CHARS_PER_TEXT_AREA           200
/* number of lines (removed from edge image) that can be stored */
#define MAX_EDGE_LINES              100
/* number of text areas. Each text area is 
 * A line (like this line) should be mapped to one area
 * A line        (like this line) will be two areas 
 */
#define MAX_TEXT_AREAS              1000
#define MAX_TEXT_LINES              75
/* number of characters that can be stored in one text-line */
#define MAX_CHARS_PER_TEXT_LINE           200

#define MAX_CHARS_PER_SEARCH_STRING 64
#define MAX_SEARCH_STRINGS          4


/* flags for text/edge lines */
enum line_state {
      TL_UNDEFINED =    0,
      TL_INUSE =  1
};

/* values for the binarized edge-image */
enum edge_state {
      /* no edge */
      E_FALSE =   0,
      /* edge detected */
      E_TRUE  =   1,
      /* edge detected and already assigned to an object */
      E_TRUE_DONE =     2,
      /* edge detected and assigned to a line */
      E_TRUE_LINE =     3
};

/* possible states for text_areas */
enum text_area_state {
      /* not in use */
      TA_UNDEFINED = 0,
      /* used as bounding box */
      TA_INUSE,
      /* created as bounding box, but seems to be a small noise 
       * (that is not a dot) */
      TA_TOOSMALL,
      /* bounding box too large */
      TA_TOOLARGE,
      /* when content of text area is already assigned to a text-line */
      TA_ASSIGNED_TO_TL
};

/* direction of a line, needed in remove_single_line */
enum line_direction {
      LINE_HORIZ =      0,
      LINE_VERT  =      1
};

/* definition of a single line (that was removed from the edge image) */
typedef struct {
      int x1,y1;              /* start point of line */
      int x2,y2;              /* end point */   
      enum line_state state;        /* state of the line ([not] in use) */
      enum line_direction direction;      /* LINE_HORIZ / LINE_VERT */
} single_edge_line;

/* definition of a single character */
typedef struct {
      int xmin, xmax;               /* remember position of char */
      int ymin, ymax;               
      unsigned char c[MAX_CHAR_HYPOTHESES];     /* one or more possible candi-
                                       dates what that character 
                                       might be */
      short num_hypotheses;
} single_char;

/* definition of a text area, i.e. a region on the screen which contains text */
typedef struct {
      int xmin, xmax, ymin, ymax;   /* the area */
      enum text_area_state state;   /* state of the ta (e.g. "in use") */
      int flags;
      /* the recognized characters in that area */
      single_char rec_char[MAX_CHARS_PER_TEXT_AREA];  
      unsigned char num_chars;      /* the number of chars */     
      float mean_char_width;        /* the average width of chars in that 
                                 text area. Used to detect stuck 
                                 together glyphs */
} single_text_area;

/* a single text line covers text areas that are in the same line
 * e.g. text areas "a" "single" "text" "line" 
 *    = textline "a single text line"
 */
typedef struct {
      int xmin, ymin, xmax, ymax;
      enum line_state state;
      unsigned char text[MAX_CHARS_PER_TEXT_LINE+1];  /* +1 for '\0' at end */
      int num_chars;
} single_text_line;

typedef struct {
      char text[MAX_CHARS_PER_SEARCH_STRING];
      /** search entry active */
      bool active;
      /** out signal for match results. */
      struct sig_boolean* result;
      /** link back to complete config struct */
      void *_cpssp;
} single_search_string;

#endif /* DEFINITIONS */

/* ********************** STATE ******************************* */

#ifdef STATE

struct {
#if 0 /* deprecated FIXME potyra */
      /* containing the current screen as [-|r|g|b] in an int */
      const uint32_t (*current_screen)[MAX_HEIGHT][MAX_WIDTH];
      /* current width and height of the screen that is used */
      const uint16_t *screen_w;
      const uint16_t *screen_h;
#endif
      /* edges found in the screen (value depending on edge strength) */
      unsigned char current_edges[MAX_HEIGHT][MAX_WIDTH];
      /* current_edges binarized according to threshold EDGE_THRESHOLD */
      enum edge_state current_edges_binarized[MAX_HEIGHT][MAX_WIDTH];
      /* current_screen binarized */
      unsigned char current_screen_binarized[MAX_HEIGHT][MAX_WIDTH];

      single_edge_line edge_line[MAX_EDGE_LINES];
      /* current number of lines removed from edge image */
      unsigned int num_edge_lines;

      single_text_area text_area[MAX_TEXT_AREAS];
      /* store the current position in the array */
      unsigned int num_text_areas;

      single_text_line text_line[MAX_TEXT_LINES];
      unsigned char num_text_lines;

      /** check necessary or did nothing change? */
      bool check_necessary;
      /** search strings */
      single_search_string search_string[MAX_SEARCH_STRINGS];
} NAME;

#endif /* STATE */

/* **************************** BEHAVIOR ************************ */

#ifdef BEHAVIOR

/* set to 1 to enable splitting of broad glyphs */
#define ENABLE_SPLITTING      0

/* Set this to '1' to enable debugging information */

#define DEBUG_ENABLE          0
#define WARNINGS        1

/* additional debug output on text areas, 
 * bitwise set 1 to enable, 
 * bitwise set 2 for really much output */
#define TEST_TA         (0)

/* additional debug output on character recognition
 * bitwise set 1 to turn on printing of every glyph that we attempt to recognize
 * bitwise set 2 to turn on output that is suitable to be pasted into
 *           font_info.dat (only from unrecognized glyphs)
 * bitwise set 4 to turn on LOTS of output: inspect even every splitting attempt
 *           use in combination with 1
 */
#define TEST_CHARREC    (0)
#define TEST_TTFCHARREC (0)

/* more debug output for long-line-removal 
 * bitwise set 1 to enable */ 
#define TEST_LINEREMOVE 0

/* more debug output for textlines
 * bitwise set 1 to enable, 
 * bitwise set 2 for really much output */
#define TEST_TL         0

/***********************************************************************/

/* debugging macro */
#if DEBUG_ENABLE
#define DEBUG(fmt, arg...) \
faum_log(FAUM_LOG_DEBUG, "image-processing", "0", "%33s:% 4d: " fmt , \
      __FUNCTION__, __LINE__, arg);
#else
#define DEBUG(fmt, arg...)
#endif

#if DEBUG_ENABLE
#define CDEBUG(fmt, arg...) \
faum_cont(FAUM_LOG_DEBUG, fmt, arg);
#else
#define CDEBUG(fmt, arg...)
#endif

/* same for warnings (if something is not being simulated correctly, but should
 * continue working without problems) */
#if WARNINGS
#define WARN(fmt, arg...) \
faum_log(FAUM_LOG_WARNING, "image-processing", "0", "%33s:% 4d: " fmt , \
      __FUNCTION__, __LINE__, arg);
#else
#define WARN(fmt, arg...)
#endif

/* same for errors (if something definitely went wrong, but the component,
 * continues working) */
#define ERROR(fmt, arg...) \
faum_log(FAUM_LOG_ERROR, "image-processing", "0", "%33s:% 4d: " fmt , \
      __FUNCTION__, __LINE__, arg);

/***********************************************************************/
/* defines (concerning the amount of certain objects)
 */
/***********************************************************************/

/* corresponding to -> unsigned int <- currentscreen */
#define DEPTH           32


/***********************************************************************/
/* aliases/definitions of some flags and similar stuff
 */
/***********************************************************************/

/* flags for text areas */
/* no flag set yet */
#define TAF_UNDEFINED         0
/* there is at least one recognized glyph in that text area */
#define TAF_RECCHAR           1
/* we need to invert that text area for recognition */
#define TAF_INVERT            2
/* is the text area already binarized and stored in current_screen_binarized? */
#define TAF_BINARIZED         4

/* the pixels in a text_area (PATTERN_0/1 defined in font_gen.h) */
#define TAP_0           PATTERN_0
#define TAP_1           PATTERN_1

/***********************************************************************/
/* thresholds (with direct impact on pattern-recognition)
 */
/***********************************************************************/

/* minimum length/height of a line to be counted as line */
#define LINE_MIN_LENGTH       25
#define LINE_MIN_HEIGHT       15

/* thresholds for sizes of bounding boxes (heuristic values) */
/* 240 = 24 8pixel chars incl spaces between -> probably not a word */
#define BB_MAX_TEXT_WIDTH     240
/* to high to be text (that we are looking for) */
#define BB_MAX_TEXT_HEIGHT    20

/* how large can the edge image of a dot be? 
 * largest dot at the moment: XP_Prof: 3x2 */
#define MAX_DOT_WIDTH         4
#define MAX_DOT_HEIGHT        3

/* threshold used to binarize edge-image [0..255] */
#define EDGE_THRESHOLD  95

/* treat colors varying in their intensity only a bit (col+-val) as the same
 * color -> color-gradient titlebars are handled correctly */
#define TEXT_COLOR_FUZZINESS        15


/***********************************************************************/
/* declarations
 */
/***********************************************************************/
static double NAME_(get_distance)(int, int);
static void NAME_(correct_boundaries)(struct cpssp*, int*, int*, int*, int*);
static void NAME_(reset_data)(struct cpssp*);
static void NAME_(invert_single_textarea)(struct cpssp*, int);
static void NAME_(remove_single_line)(
      struct cpssp*, 
      int, 
      int, 
      int, 
      enum line_direction
);


/*
 * looks for given string in all text areas 
 * returns 1 if findme is somewhere on the screen
 *         0 else
 */
static int
NAME_(find_string)(struct cpssp *cpssp, char *findme)
{
      int tlc;
      char* res;

      DEBUG("looking for string %s...", findme);

      /* look in each text_line */
      /* Note: \0 *is* always existing! -> str operations allowed */

      /* FIXME consider alternate hypothesis here! */
      for (tlc = 0; tlc < cpssp->NAME.num_text_lines; ++tlc) {
            res = strstr(cpssp->NAME.text_line[tlc].text, findme);
            if (res == NULL) {
                  /* not found */
                  continue;
            } else {
                  CDEBUG("%s","found!!\n");
                  return 1;
            }
      }
      
      CDEBUG("%s", "NOT found\n");
      return 0;
}


/***********************************************************************/
/* classification - string concatenation
 *
 * needed when we want to know whats printed next to a give spot
 * also makes localization of a given string easier
 */
/***********************************************************************/


/* 
 * adds the content off a single text area 'ta' to text-line 'tl'
 *
 */
static void
NAME_(add_ta_to_tl)(
      single_text_area *ta, 
      single_text_line *tl,
      unsigned char *ntl
)
{
      static bool alreadywarned = false;
      int i;
      unsigned char c;
      
      if (MAX_TEXT_LINES <= *ntl) {
            if (! alreadywarned) {
                  WARN("Maximum number (%d) of text_lines reached. "
                       "Recompile with higher MAX_TEXT_LINES\n", 
                       MAX_TEXT_LINES);
                  alreadywarned = true;
            }
            return;
      }
      
#if TEST_TL
      DEBUG("adding text area (%d/%d - %d/%d) to textline\n",
            ta->xmin, ta->ymin,
            ta->xmax, ta->ymax);
#endif

      ta->state=TA_ASSIGNED_TO_TL;

      if (tl->state==TL_UNDEFINED) {
            tl->state=TL_INUSE;
            
            tl->xmin = ta->xmin;
            tl->xmax = ta->xmax;
            tl->ymin = ta->ymin;
            tl->ymax = ta->ymax;
            
            (*ntl)++;
#if TEST_TL & 2
            DEBUG("creating new textline (%d tls), %d/%d - %d/%d\n", 
                  num_text_lines, 
                  tl->xmin, tl->ymin,
                  tl->xmax, tl->ymax);
#endif
      } else {
            tl->xmax = ta->xmax;

#if TEST_TL & 2
            DEBUG("extending textline (%d tls), %d/%d - %d/%d\n",
                        num_text_lines, tl->xmin, 
                        tl->ymin, tl->xmax, 
                        tl->ymax);
#endif
      }


      /* FIXME what about alternate hypotheses? also store them here! */
      for (i = 0; i < ta->num_chars; ++i) {
            if (tl->num_chars==MAX_CHARS_PER_TEXT_LINE) {
                  WARN("Maximum number (%d) of characters reached for "
                       "text_line. Recompile with higher "
                       "MAX_CHARS_PER_TEXT_LINE\n", 
                       MAX_CHARS_PER_TEXT_LINE);
                  return;
            }
            c = ta->rec_char[i].c[0];
            /* only store printable characters */
            if (('A' <= c && c <= 'Z')
             || ('a' <= c && c <= 'z')
             || ('0' <= c && c <= '9')
             || c == '_'
             || c == '-'
             || c == '['
             || c == ']'
             || c == '<'
             || c == '>'
             || c == '('
             || c == ')'
             || c == '{'
             || c == '}'
             || c == ':'
             || c == ';'
             || c == '/'
             || c == '\\'
             || c == '\''
             || c == '"'
             || c == '+'
             || c == '*'
             || c == '#'
             || c == '$'
             || c == '@'
             || c == '='
             || c == ','
             || c == '?'
             || c == '~'
             || c == '!'
             || c == ' '
             || c == '.') {
                  tl->text[tl->num_chars++] = c;
            } else if (c == 132) {
                  tl->text[tl->num_chars++] = 228; /* ae */
            } else if (c == 142) {
                  tl->text[tl->num_chars++] = 196; /* AE */
            } else if (c == 148) {
                  tl->text[tl->num_chars++] = 246; /* oe */
            } else if (c == 153) {
                  tl->text[tl->num_chars++] = 214; /* OE */
            } else if (c == 154) {
                  tl->text[tl->num_chars++] = 220; /* UE */
            } else if (c == 129) {
                  tl->text[tl->num_chars++] = 252; /* ue */
            }
      }
      
      alreadywarned=0;
}

/**
 * extends the text area ta1 to also cover the area of text area ta2 and append
 * the contents of ta2 to ta1
 */
static void 
NAME_(extend_text_area)(single_text_area *ta1, single_text_area *ta2)
{
      int i;
      int dist, num_spaces;
      assert(ta2 > ta1);

      dist=ta2->xmin - ta1->xmax - 1;
      
      /* dont check for xmin, thats not possible */   
      if (ta2->ymin < ta1->ymin) {
            ta1->ymin = ta2->ymin;
      }
      if (ta2->ymax > ta1->ymax) {
            ta1->ymax = ta2->ymax;
      }
      /* dont check for xmax, ta2 is always right to ta1 */
      ta1->xmax = ta2->xmax;

      
      if ( (6 <= dist) && (dist <= 9) ) {
            num_spaces=1;
      } else {
            num_spaces=abs(floor(dist / 8));
      }

      /* set ' ' in between according to distance */
      for (i = 0; i < num_spaces; ++i) {
            if (ta1->num_chars == MAX_CHARS_PER_TEXT_AREA) {
                  ERROR("Couldn't add character %d of text area to "
                        "text area, as the maximum number (%d) of "
                        "characters per text area is reached. "
                        "Recompile "
                        "with higher MAX_CHARS_PER_TEXT_AREA\n",
                        i, MAX_CHARS_PER_TEXT_AREA);
                  return;
            }
            ta1->rec_char[ta1->num_chars].c[0] = ' ';
            ta1->rec_char[ta1->num_chars].num_hypotheses = 1;
            ta1->num_chars++;
      }
      
      /* copy content */
      for (i = 0; i < ta2->num_chars; ++i) {
            if (ta1->num_chars==MAX_CHARS_PER_TEXT_AREA) {
                  ERROR("Couldn't add character %d of text area to "
                        "text area, as the maximum number (%d) of "
                        "characters per text area is reached. "
                        "Recompile "
                        "with higher MAX_CHARS_PER_TEXT_AREA\n",
                        i, MAX_CHARS_PER_TEXT_AREA);
                  return;
            }

            ta1->rec_char[ta1->num_chars].c[0] = ta2->rec_char[i].c[0];
            ta1->rec_char[ta1->num_chars].num_hypotheses=1;
            ta1->num_chars++;
      }

      ta2->state=TA_UNDEFINED;
}



/*
 * build words out of the text areas by connecting very nearby ones
 */
static void
NAME_(build_words)(struct cpssp *cpssp)
{
      int i, j;
      /* ymin/ymax, midpoint and height of text area 1 */
      int yl1, yh1, m1, h1;
      /* ymin/ymax, midpoint and height of text area 2 */
      int yl2, yh2, m2, h2;
      
      DEBUG("building words out of %d text areas\n", num_text_areas);

      for (i = 0; i < cpssp->NAME.num_text_areas; ++i) {
            if (cpssp->NAME.text_area[i].state != TA_INUSE) {
                  continue;
            }
            if (!(cpssp->NAME.text_area[i].flags & TAF_RECCHAR)) {
                  continue;
            }
      
            yl1 = cpssp->NAME.text_area[i].ymin;
            yh1 = cpssp->NAME.text_area[i].ymax;
            h1 = yh1 - yl1 + 1;
            m1 = abs((yl1 + yh1) / 2);

            for (j = i + 1; j < cpssp->NAME.num_text_areas; ++j) {
                  if (cpssp->NAME.text_area[j].state != TA_INUSE) {
                        continue;
                  }
                  if (!(cpssp->NAME.text_area[j].flags & TAF_RECCHAR)) {
                        continue;
                  }
                  
                  /* TODO FIXME optimization
                   * check if there is a vertical line in between -> if
                   * yes, stop here */
                  
                  yl2 = cpssp->NAME.text_area[j].ymin;
                  yh2 = cpssp->NAME.text_area[j].ymax;
                  h2 = yh2 - yl2;
                  m2 = abs((yl2 + yh2) / 2);
                  
                  /* check vertical proximity */
                  if (!(    ((yl1 <= m2) && (m2 <= yh1))
                         || ((yl2 <= m1) && (m1 <= yh2)) )) {
                        continue;
                  }

                  NAME_(extend_text_area)(&cpssp->NAME.text_area[i], 
                               &cpssp->NAME.text_area[j]);

                  yl1 = cpssp->NAME.text_area[i].ymin;
                  yh1 = cpssp->NAME.text_area[i].ymax;
                  h1 = yh1 - yl1 + 1;
                  m1 = abs((yl1 + yh1) / 2);
            }
      }
}


static int 
NAME_(compare_textlines)(const void *a, const void *b) 
{
      const single_text_line *s1;
      const single_text_line *s2;
      
      s1=(const single_text_line *)a;
      s2=(const single_text_line *)b;

      if (s1->ymin<s2->ymin) {
            return -1;
      }
      if (s1->ymin==s2->ymin) {
            return 0;
      }
      return 1;
}


/*
 * build text-line data structures out of text areas
 */
static void
NAME_(build_text_lines)(struct cpssp *cpssp)
{
      int i, j;
      /* y low/high ta 1/2     height ta 1/2  */
      int yl1=0, yh1=0, yl2=0, yh2=0, h1=0, h2=0;
        /* inited to suppres compiler warnings about "might be used
         * uninitialized" of yl1 yh1 and h1 */  
      int cur_tl=-1;

      DEBUG("going to build textlines out of %d text areas\n", 
            num_text_areas);

      NAME_(build_words)(cpssp);
      
      for (i = 0; i < cpssp->NAME.num_text_areas; ++i) {
            if (cpssp->NAME.text_area[i].state != TA_INUSE) {
                  continue;
            }
            if (!(cpssp->NAME.text_area[i].flags & TAF_RECCHAR)) {
                  continue;
            }
            
            yl1 = cpssp->NAME.text_area[i].ymin;
            yh1 = cpssp->NAME.text_area[i].ymax;
            h1 = yh1 - yl1;

            cur_tl++;
            
#if TEST_TL 
            DEBUG("text area %d: %d/%d - %d/%d creating textline %d\n",
                  i, cpssp->NAME.text_area[i].xmin, yl1, 
                  cpssp->NAME.text_area[i].xmax,
                  cpssp->NAME.text_area[i].ymax, cur_tl);
#endif
            
            /* create new text_line from that text_area */
            NAME_(add_ta_to_tl)(&cpssp->NAME.text_area[i], 
                        &cpssp->NAME.text_line[cur_tl], 
                        &cpssp->NAME.num_text_lines);
                  
            /* and append every text_area that is in that line, matching
             * required height/y-coordinates */
            for (j = i + 1; j < cpssp->NAME.num_text_areas; ++j) {
                  if (cpssp->NAME.text_area[j].state != TA_INUSE) {
                        continue;
                  }
                  if (!(cpssp->NAME.text_area[j].flags & TAF_RECCHAR)) {
                        continue;
                  }

#if TEST_TL & 2
                  DEBUG("considering TA %d (%3d/%3d-%3d/%3d)\n", j,
                        cpssp->NAME.text_area[j].xmin, 
                        cpssp->NAME.text_area[j].ymin, 
                        cpssp->NAME.text_area[j].xmax, 
                        cpssp->NAME.text_area[j].ymax);
#endif
                  
                  yl2 = cpssp->NAME.text_area[j].ymin;
                  yh2 = cpssp->NAME.text_area[j].ymax;
                  h2 = yh2 - yl2;

#if TEST_TL & 2
                  DEBUG("\ttest 2: %d <= %d & %d <= %d\n", abs(h2*0.5),
                        h1, h1, abs(h2*1.9));
                  DEBUG("\ttest 3a: %d <= %d & %d <= %d\n", 
                        abs(yl1+0.5*h1), yh2, yh2, yh1+abs(h1*0.5));
                  DEBUG("\ttest 3b: %d <= %d & %d <= %d\n", 
                        yl1-abs(h1*0.5), yl2, yl2, abs(yl1+0.5*h1));
#endif
                  
                  /* connecting text areas only if they have 
                   * approx same height */
                  /* 'o' 'O' 'p' 'Op' differ like 7/10/13  
                   * 10/14/18  17/23/29  23/32/42 in height (with
                   * different font sizes)
                   * I.e. a factor of 0.54/1.85 in worst case */
                  if (   ( abs(h2*0.5) <= h1 && h1 <= abs(h2*1.9))

                              /* and if they arent displaced 
                               * too much vertically */
                      && (   (  abs(yl1+0.5*h1) <= yh2 
                           && yh2 <= (yh1 + abs(h1*0.5))) 
                          || ( (yl1-abs(h1*0.5)) <= yl2 
                           && yl2 <= abs(yl1+0.5*h1)))) {                                 
#if TEST_TL & 2
                        DEBUG("%s", "\t\tPASSED, TAKE IT\n");
#endif
                        /* concat text from text_area to
                         * text-line */
                        NAME_(add_ta_to_tl)(
                              &cpssp->NAME.text_area[j], 
                              &cpssp->NAME.text_line[cur_tl],
                              &cpssp->NAME.num_text_lines);
                  }
            }
      }
      
#if TEST_TL
      DEBUG("done building textlines, got %d (system %d) now\n", 
            cur_tl + 1, 
            cpssp->NAME.num_text_lines);
#endif
      
      for (i=0; i < cpssp->NAME.num_text_lines; ++i) {
            cpssp->NAME.text_line[i].text[
                  cpssp->NAME.text_line[i].num_chars
                  ] = '\0';
      }

      qsort(&cpssp->NAME.text_line[0], cpssp->NAME.num_text_lines, 
            sizeof(single_text_line),
            NAME_(compare_textlines));
      
}

/* helper function for qsort */
static int 
NAME_(compare_samples)(const void *a, const void *b) 
{
      const sample_struct *s1;
      const sample_struct *s2;
      
      s1=(const sample_struct *)a;
      s2=(const sample_struct *)b;

      if (s1->size<s2->size) return -1;
      if (s1->size==s2->size) return 0;
      return 1;
}


/* helper function for qsort */
static int 
NAME_(compare_samples2)(const void *a, const void *b) 
{
      const ttf_sample_struct *s1;
      const ttf_sample_struct *s2;
      
      s1=(const ttf_sample_struct *)a;
      s2=(const ttf_sample_struct *)b;

      if (s1->size<s2->size) return -1;
      if (s1->size==s2->size) return 0;
      return 1;
}


/* 
 * classify ("recognize") a single character 
 * ta is index of text area, c is index of character in that text area
 *    *OR*
 * if pxmin!=-1 try recognizing area pxmin/pymin - pxmax/pymax
 *
 * returns number of hypotheses
 * i.e.    0 if character was not recognized
 *       >=1 else (=number of possible matches)
 */
static int
NAME_(recognize_single_char)(
      struct cpssp *cpssp,
      int ta, 
      int c, 
      int pxmin, int pymin, 
      int pxmax, int pymax
)
{
      int xmin, xmax, ymin, ymax;
      int size, s;
      int x, y;
      int hypo;
      int i;

      /* if already done, don't do it again */
      if (0 <= c) {
            if (0 < cpssp->NAME.text_area[ta].rec_char[c].num_hypotheses) {
                  return cpssp->NAME.text_area[ta].rec_char[c].num_hypotheses;
            }
      }
      
      if (pxmin == -1) {
            ymin = cpssp->NAME.text_area[ta].rec_char[c].ymin;
            ymax = cpssp->NAME.text_area[ta].rec_char[c].ymax;
            xmin = cpssp->NAME.text_area[ta].rec_char[c].xmin;
            xmax = cpssp->NAME.text_area[ta].rec_char[c].xmax;
      /* check area specified by args */
      } else {
            xmin = pxmin;
            ymin = pymin;
            xmax = pxmax;
            ymax = pymax;
      }

      size = (xmax - xmin + 1) * (ymax - ymin + 1);

#if !(TEST_CHARREC & 4)
      if (pxmin==-1) {
#endif
#if TEST_CHARREC & 1
            DEBUG("--- character to recognize: %d x %d = %d:\n", 
                  xmax-xmin+1, ymax-ymin+1, size);
#endif
#if !(TEST_CHARREC & 4)
      }
#endif

      /* lookup in samples.c and compare to each sample with
       * same size */   
      s=0;
      while ((s<NSAMPLES) && (sample[s].size<size)) {
            ++s;
      }
      /* at position 's' begin the samples with sizes >= size
       * of current segmentated char */

      /* count the number of hypotheses */
      hypo=0;
      while (sample[s].size==size) {
            /* char 249 and 250 are noise */
            if ( (sample[s].ord==249) || (sample[s].ord==250)) {
                  ++s;
                  continue;               
            }
            /* only check for same width, if width is same, height is same
             * as well */
            if (sample[s].width != (xmax-xmin+1)) {
                  ++s;
                  continue;
            }
            
            /* now compare each sample with same size with
             * segmentated char */
            int different=0;

            for (y=0; (y<sample[s].height) && (different==0); ++y) {
                  for (x=0; (x<sample[s].width) && (different==0); 
                        ++x) {
                        if (cpssp->NAME.current_screen_binarized[
                                          ymin + y][xmin + x]
                          != sample[s].pattern[y*sample[s].width+x]) {
                              different=1;
                              break;
                        }
                  }
            }

            if (different==1) {
                  ++s;
                  continue;
            }

#if TEST_TA & 1
            if (c==-1) {
                  DEBUG("\t  '-->\tFound matching character for ta %d "
                        "char %d: %c (%d) sample %d\n", ta, c, 
                        sample[s].ord, sample[s].ord, s);
            }
#endif
            
            ++hypo;
#if TEST_CHARREC & 1
            DEBUG("\t  '-->\tFound matching character for ta %d char %d: "
                  "%c (%d) sample %d\n", ta, c, sample[s].ord, 
                  sample[s].ord, s);
#endif

            /* only add pattern we found to char if we aren't just testing a
             * _possible_ recognition of that char */
            if ((pxmin==-1) && (0<=c)) {

                  /* found a pattern! -> add it as
                   * hypthesis of current character */
                  if (cpssp->NAME.text_area[ta].rec_char[c].num_hypotheses
                        < MAX_CHAR_HYPOTHESES) {
                        /* but only if that hypothesis isn't already
                         * stored */
                        int found=0;
                        for (i=0; 
                             i < cpssp->NAME.text_area[
                                    ta].rec_char[c].num_hypotheses;
                             ++i) {
                              if (cpssp->NAME.text_area[
                                    ta].rec_char[c].c[i]
                               == sample[s].ord) {
                                    found=1;
                                    break;
                              }
                        }
                        if (found == 0) {
                              cpssp->NAME.text_area[ta].rec_char[c].c[
                                    cpssp->NAME.text_area[ta].rec_char[
                                          c].num_hypotheses++
                                    ]=sample[s].ord;
                        }

                  } else {
                        int cc;
                        WARN("Found another matching hypothesis ('%c'"
                             "/Ord %d in addition to (", 
                             sample[s].ord, sample[s].ord);

                        for (cc=0; cc<MAX_CHAR_HYPOTHESES; ++cc) {
                              faum_cont(FAUM_LOG_WARNING, 
                                    "%c/Ord %d ",
                                    cpssp->NAME.text_area[ta].rec_char[
                                                c].c[cc],
                                    cpssp->NAME.text_area[ta].rec_char[
                                                c].c[cc]);

                        }
                        faum_cont(FAUM_LOG_WARNING, ") for "
                              "character %d in text area %d, "
                              "but there is no more space to "
                              "store it. Recompile with "
                              "higher MAX_CHAR_HYPOTHESES\n",
                              c, ta);
                  }
            }
            ++s;
      }
      
      if ((pxmin==-1) || (c==-1)) {
            /* we did check a text area, so remember that we recognized
             * something */
            if ((hypo) && (ta>=0)) {
                  cpssp->NAME.text_area[ta].flags |= TAF_RECCHAR;
            }
      }
      
      return hypo;
}




/* 
 * classify ("recognize") a single character THAT IS A TTF GLYPH
 * ta is index of text area, c is index of character in that text area
 *    *OR*
 * if pxmin!=-1 try recognizing area pxmin/pymin - pxmax/pymax
 *
 * returns number of hypotheses
 * i.e.    0 if character was not recognized
 *       >=1 else (=number of possible matches)
 */
static int
NAME_(recognize_single_ttfchar)(
      struct cpssp *cpssp,
      int ta, 
      int c, 
      int pxmin, int pymin, 
      int pxmax, int pymax
)
{
      int xmin, xmax, ymin, ymax;
      int size, s;
      int x, y;
      int hypo;
      int i;

      /* if already done, don't do it again */
      if (0 <= c) {
            if (0 < cpssp->NAME.text_area[ta].rec_char[c].num_hypotheses) {
                  return cpssp->NAME.text_area[
                              ta].rec_char[c].num_hypotheses;
            }
      }
      
#if TEST_TTFCHARREC
      DEBUG("recognizing ta %d c %d\n", ta, c);
#endif
      
      if (pxmin == -1) {
            ymin = cpssp->NAME.text_area[ta].rec_char[c].ymin;
            ymax = cpssp->NAME.text_area[ta].rec_char[c].ymax;
            xmin = cpssp->NAME.text_area[ta].rec_char[c].xmin;
            xmax = cpssp->NAME.text_area[ta].rec_char[c].xmax;
      /* check area specified by args */
      } else {
            xmin = pxmin;
            ymin = pymin;
            xmax = pxmax;
            ymax = pymax;
      }

      size=(xmax-xmin+1)*(ymax-ymin+1);

#if (TEST_TTFCHARREC & 4)
            DEBUG("--- character to recognize: %d x %d = %d:\n", 
                  xmax-xmin+1, ymax-ymin+1, size);
#endif

      /* lookup in samples.c and compare to each sample with
       * same size */   
      s=0;
      while ((s < NSAMPLES2) && (sample2[s].size < size)) {
            ++s;
      }
      /* at position 's' begin the samples with sizes >= size
       * of current segmentated char */
      
#if TEST_TTFCHARREC
      DEBUG("beginning at %d\n", s);
#endif


      /* count the number of hypotheses */
      hypo = 0;
      while (sample2[s].size == size) {
            /* now compare each sample with same size with
             * segmentated char */
            int different=0;
            int maybes=0, maxmaybes=0;

#if TEST_TTFCHARREC
            DEBUG("comparing to sample %d [%c]\n", s, sample2[s].ord);
#endif

            for (y=0; (y<sample2[s].height) && (different==0); ++y) {
                  for (x=0; (x<sample2[s].width) && (different==0); 
                        ++x) {
                        if ( (sample2[s].pattern[y*sample2[s].width+x]
                              ==MUSTHAVE)
                            &&
                             (cpssp->NAME.current_screen_binarized[ymin+y][
                                                xmin+x]
                              ==TAP_0) ) {

                              different=1; 
                              break;
                        } else if ( (sample2[s].pattern[y*sample2[s].width+x]
                                   ==MUSTNOT)
                                 &&
                                   (cpssp->NAME.current_screen_binarized[
                                          ymin+y][xmin+x]
                                   ==TAP_1) ) 
                        {
                              different=1; 
                              break;
                        } else if (sample2[s].pattern[y*sample2[s].width+x]
                                 ==MAYBE) {

                              maxmaybes++;
                              if (cpssp->NAME.current_screen_binarized[
                                          ymin+y][xmin+x]
                                  ==TAP_1) 
                              {
                                    ++maybes; 
                              }
                        }
                  }

            }

            if (different==1) {
                  ++s;
                  continue;
            }

            /* FIXME TODO optimization:
             * store maybes/maxmaybes for each hyopthesis and
             * take the one with best (as best candidate... not necessary
             * with alternate hypotheses */

#if (TEST_TTFCHARREC)
            if (c==-1) {
                  DEBUG("\t  '-->\tFound matching character for ta %d "
                        "char %d: %c (%d) sample %d\n", ta, c, 
                        sample[s].ord, sample[s].ord, s);
            }
#endif
            
            ++hypo;
#if (TEST_TTFCHARREC)
            DEBUG("\t  '-->\tFound matching character for ta %d char %d: "
                  "%c (%d) sample %d\n", ta, c, sample[s].ord, 
                  sample[s].ord, s);
#endif

            /* only add pattern we found to char if we aren't just testing a
             * _possible_ recognition of that char */
            if ((pxmin==-1) && (0<=c)) {

                  /* found a pattern! -> add it as
                   * hypthesis of current character */
                  if (  cpssp->NAME.text_area[ta].rec_char[c].num_hypotheses
                      < MAX_CHAR_HYPOTHESES) {
                        /* but only if that hypothesis isn't already
                         * stored */
                        int found=0;
                        for (i=0; 
                             i < cpssp->NAME.text_area[ta].rec_char[
                                    c].num_hypotheses;
                             ++i) {
                              if (cpssp->NAME.text_area[ta].rec_char[c].c[i]
                                ==sample[s].ord) {
                                    found=1;
                                    break;
                              }
                        }
                        if (found==0) {
                              cpssp->NAME.text_area[ta].rec_char[c].c[
                                    cpssp->NAME.text_area[ta].rec_char[
                                          c].num_hypotheses++
                                    ]=sample[s].ord;
                              
                        }

                  } else {
                        int cc;
                        WARN("Found another matching hypothesis ("
                             "'%c'/Ord %d in addition to (", 
                             sample[s].ord, sample[s].ord);

                        for (cc=0; cc<MAX_CHAR_HYPOTHESES; ++cc) {
                              faum_cont(FAUM_LOG_WARNING, 
                                    "%c/Ord %d ",
                                    cpssp->NAME.text_area[ta].rec_char[
                                                c].c[cc],
                                    cpssp->NAME.text_area[ta].rec_char[
                                                c].c[cc]);

                        }
                        faum_cont(FAUM_LOG_WARNING, ") for "
                              "character %d in text area %d, "
                              "but there is no more space to "
                              "store it. Recompile with "
                              "higher MAX_CHAR_HYPOTHESES\n",
                              c, ta);
                  }
            }
            ++s;
      }
      
      if ((pxmin==-1) || (c==-1)) {
            /* we did check a text area, so remember that we recognized
             * something */
            if ((hypo) && (ta>=0)) {
                  cpssp->NAME.text_area[ta].flags |= TAF_RECCHAR;
            }
      }
      
      return hypo;
}


/* 
 * classify all characters 
 * */
static void
NAME_(recognize_characters)(struct cpssp *cpssp)
{
      int i, j;  /* current text area, character in that area */
      int h;     /* number of hypotheses for char */
      int rec;
      int ttf_first=0;

      DEBUG("%s", "Beginning to recognize characters\n");


      /* FIXME move prepare_char_recognition to this place, as elsewise all
       * characters are already recognized (with splitting enabled)
       */
      
      /* handle each text area */
      for (i = 0; i < cpssp->NAME.num_text_areas; ++i) {
            DEBUG("TA %d: ", i);
            if (cpssp->NAME.text_area[i].state != TA_INUSE) {
                  CDEBUG("%s","NO\n");
                  continue;
            }
            CDEBUG("YES (%d chars) ", cpssp->NAME.text_area[i].num_chars);

            rec=0;
            /* and each character */
            for (j = 0; j < cpssp->NAME.text_area[i].num_chars; ++j) {

                  /* look if char already has a hypothesis (which might
                   * have been constructed in prepare_char_recognition)
                   */
                  CDEBUG("char %d: ", j);
                  if (0 < cpssp->NAME.text_area[i].rec_char[j].num_hypotheses) {
                        rec=1;
                        CDEBUG("%s","NO\n");
                        continue;
                  }
                  CDEBUG("%s","YES\n");
                  
                  if (ttf_first) {
                        h = NAME_(recognize_single_ttfchar)(
                                          cpssp, i, j, 
                                          -1, -1, -1, -1);
                        if (h) {
                              rec=1;
                              continue;
                        }
                        h = NAME_(recognize_single_char)(
                                          cpssp, i, j, 
                                          -1, -1, -1, -1);
                        if (h) {
                              ttf_first=0;
                              rec=1;
                              continue;
                        }
                  } else {
                        h = NAME_(recognize_single_char)(
                                          cpssp, i, j, 
                                          -1, -1, -1, -1);
                        if (h) {
                              rec=1;
                              continue;
                        }
                        h = NAME_(recognize_single_ttfchar)(
                                          cpssp, i, j, 
                                          -1, -1, -1, -1);
                        if (h) {
                              ttf_first=1;
                              rec=1;
                              continue;
                        }
                  }
                  
                  
                  /* we didn't find any matching character */
#if TEST_CHARREC
                  DEBUG("No matching hypothesis found for character %d "
                        "in text area %d (%d/%d-%d/%d\n", 
                        j, i, 
                        cpssp->NAME.text_area[i].rec_char[j].xmin,
                        cpssp->NAME.text_area[i].rec_char[j].ymin,
                        cpssp->NAME.text_area[i].rec_char[j].xmax,
                        cpssp->NAME.text_area[i].rec_char[j].ymax );
#endif

            }

            /* discard if nothing was recognized */
            if (rec==0) {
                  cpssp->NAME.text_area[i].state=TA_UNDEFINED;
            }
      }
}


/* 
 * Prepares recognition of the characters in each text area by cutting of empty
 * lines at top and bottom. 
 * Additionally, look which characters have to be splitted up before they can be
 * recognized
 */
static void
NAME_(prepare_char_recognition)(struct cpssp *cpssp)
{
      /* loop vars text_areas / characters */
      int i, j;
      /* width and height of char */
      int cw, ch;

      DEBUG("%s", "Preparing characters for recognition\n");

      /* handle each text area */
      for (i = 0; i < cpssp->NAME.num_text_areas; ++i) {
            if (cpssp->NAME.text_area[i].state != TA_INUSE) {
                  continue;
            }

            /* and each character */
            for (j = 0; j < cpssp->NAME.text_area[i].num_chars; ++j) {
                  
                  /* remove empty lines at top and bottom */
                  NAME_(correct_boundaries)(
                              cpssp,
                              &cpssp->NAME.text_area[i].rec_char[j].xmin,
                              &cpssp->NAME.text_area[i].rec_char[j].ymin,
                              &cpssp->NAME.text_area[i].rec_char[j].xmax,
                              &cpssp->NAME.text_area[i].rec_char[j].ymax);

                  cw = cpssp->NAME.text_area[i].rec_char[j].xmax 
                       - cpssp->NAME.text_area[i].rec_char[j].xmin + 1;
                  ch = cpssp->NAME.text_area[i].rec_char[j].ymax 
                       - cpssp->NAME.text_area[i].rec_char[j].ymin + 1;

                  /* Keep it enabled as ttf fonts can't be recognized 
                   * else (some of them, that touch each other)
                   */
#if ENABLE_SPLITTING

                  /* Before splitting, check if we can recognize the 
                   * whole thing in the way it is already.
                   */
                  if (! (0 < NAME_(recognize_single_char)(
                              cpssp, i, j, -1, -1, -1, -1))) {
                        
                        /* FIXME check if width is big enough to 
                         * contain more then 2 chars -> if so, split up
                         * in more pieces */
                        if (cw > 1.7 * 
                                 cpssp->NAME.text_area[i].mean_char_width) {
                              /* split candidate */
                              NAME_(split_character)(i, j);
                        } else {
                              /* if height > width... try recognize,
                               * if not possible -> split
                               */
                              /* TODO */
                              NAME_(split_character)(i, j);
                        }
                  }
#endif
            }
      }
}



/***********************************************************************/
/* image segmentation - word segmentation / character related
 */
/***********************************************************************/


/*
 * cuts away empty lines at top and bottom of a given rectangle
 * stores 'real' beginning, that is first/last line which aren't empty in
 * parameters pymin/pymax
 *
 * Also removes the line from underline glyphs (as far as possible, which is not
 * the case with an underlined 'y'!!), and therefor rechecks the minimum width
 * of the glyph
 */
static void
NAME_(correct_boundaries)(
      struct cpssp *cpssp,
      int *pxmin, int *pymin, 
      int *pxmax, int *pymax
)
{
      int x,y;
      int xmin, xmax, ymin, ymax;
      int last_full, abovelast_empty;

      xmin=*pxmin;
      xmax=*pxmax;
      ymin=*pymin;
      ymax=*pymax;
      
      /* adjust y parameters: cut away empty lines at top&bottom */
      for (y=ymin; y<=ymax; ++y) {
            unsigned char empty;
            empty=1;

            for (x=xmin; x<=xmax; ++x) {
                  if (cpssp->NAME.current_screen_binarized[y][x]==TAP_1) {
                        empty=0;
                        break;
                  }
            }

            if (empty) {
                  /* line y is empty */
                  ymin++;
            } else {
                  break;
            }
      }
      
      /* Here we *could* check for ymin>ymax 
       * shoulnt be possible as */
      for (y=ymax; y>ymin; --y) {
            unsigned char empty;
            empty=1;

            for (x=xmin; x<=xmax; ++x) {
                  if (cpssp->NAME.current_screen_binarized[y][x]==TAP_1) {
                        empty=0;
                        break;
                  }
            }

            if (empty) {
                  ymax=y-1;
            } else {
                  break;
            }
      }

      /* check if last line is full of TAP_1 and one above full of TAP_0
       * meaning we have a line below a glyph */
      last_full=1;
      for (x=xmin; x<=xmax; ++x) {
            if (cpssp->NAME.current_screen_binarized[ymax][x]!=TAP_1) {
                  last_full=0;
                  break;
            }
      }
      /* dont do that if we only have an underscore */
      /* or generally: if height <= 2 */
      if ((ymax-ymin+1) <= 2 ) {
            last_full=0;
      }
      if (last_full) {
            abovelast_empty=1;
            for (x=xmin; x<=xmax; ++x) {
                  if (cpssp->NAME.current_screen_binarized[ymax-1][x]!=TAP_0) {
                        abovelast_empty=0;
                        break;
                  }
            }

            if (abovelast_empty) {
                  int ret;
                  /* check if we already can recognize that *without*
                   * removing the line (could be a '=') */

                  ret = NAME_(recognize_single_char)(
                                    cpssp, -1, -1, xmin, ymin,
                                    xmax, ymax);
                  if (!ret) {                   

                        /* FIXME there is not necessarily only ONE empty
                         * line above the line */
                        ymax=ymax-2;

                        /* check if glyph can get smaller */
                        for (x=xmin; x<=xmax; ++x) {
                              unsigned char empty;
                              empty=1;

                              for (y=ymin; y<=ymax; ++y) {
                                    if (cpssp->NAME.current_screen_binarized[
                                                y][x]==TAP_1) {
                                          empty=0;
                                          break;
                                    }
                              }

                              if (empty) {
                                    xmin++;
                              } else {
                                    break;
                              }
                        }
                        for (x=xmax; x>xmin; --x) {
                              unsigned char empty;
                              empty=1;

                              for (y=ymin; y<=ymax; ++y) {
                                    if (cpssp->NAME.current_screen_binarized[
                                                y][x]==TAP_1) {
                                          empty=0;
                                          break;
                                    }
                              }

                              if (empty) {
                                    xmax--;
                              } else {
                                    break;
                              }
                        }
                  }
                  
            }
      }


      
      /* write back results */
      *pxmin=xmin;
      *pxmax=xmax;
      *pymin=ymin;
      *pymax=ymax;
}


/* inverts a single text area */
static void
NAME_(invert_single_textarea)(struct cpssp *cpssp, int i)
{
      int x, y;

      if (cpssp->NAME.text_area[i].state != TA_INUSE) {
            return;
      }
      if (!(cpssp->NAME.text_area[i].flags & TAF_INVERT)) {
            return;
      }

      for (y = cpssp->NAME.text_area[i].ymin; 
            y <= cpssp->NAME.text_area[i].ymax; ++y) {

            for (x = cpssp->NAME.text_area[i].xmin; 
                  x <= cpssp->NAME.text_area[i].xmax; ++x) {

                  if (cpssp->NAME.current_screen_binarized[y][x]==TAP_0) {
                        cpssp->NAME.current_screen_binarized[y][x]=TAP_1;
                  } else {
                        cpssp->NAME.current_screen_binarized[y][x]=TAP_0;
                  }
            }
      }

      cpssp->NAME.text_area[i].flags ^= TAF_INVERT;
}

/* 
 * inverts all text areas which have their invert-flag set (so that e.g.
 * correct_boundaries works correctly)
 */
static void
NAME_(invert_text_areas)(struct cpssp *cpssp)
{
      int i;

      for (i = 0; i < cpssp->NAME.num_text_areas; ++i) {
            if (cpssp->NAME.text_area[i].state != TA_INUSE) {
                  continue;
            }
            if (!(cpssp->NAME.text_area[i].flags & TAF_INVERT)) {
                  return;
            }
            NAME_(invert_single_textarea)(cpssp, i);
      }
}


/* 
 * search for occurence of similar color to 'look' in 'arr' with fuzzyness 'fuz'
 * meaning any color that differs from 'look' in 'arr' to a degree of 'fuz' will
 * be a hit. 'size' is the number of elements in 'arr'
 */
static int
NAME_(color_in_array)(int *arr, int size, int look, unsigned char fuz)
{
      int i;
      for (i = 0; i < size; ++i) {
            if (NAME_(get_distance)(arr[i], look) < fuz) {
                  return 1;
            }
      }
      return 0;
}


#define ON_BG     0
#define ON_FG     1

/*
 * binarize a text-area: use fact that text areas start 1 pixel to the left/top
 * before the actual glyph (because of the edge image generation). Thus,
 * complete left and complete top row is background!!
 */
static void
NAME_(binarize_text_area)(struct cpssp *cpssp, int curta)
{
      int x, y;
      int cur_edge;
      single_text_area *ta;
      int *bgcol, maxbgsize, curbgcolsize=0;
      int *fgcol, maxfgsize, curfgcolsize=0;
      int lastfg=0;
      int lookfor=0;
      
      ta = &cpssp->NAME.text_area[curta];
      
      if ((ta->flags & TAF_BINARIZED)==TAF_BINARIZED) {
#if TEST_TA & 1
            DEBUG("text area %d (%d/%d-%d/%d) already binarized\n", curta,
                  ta->xmin, ta->ymin, ta->xmax, ta->ymax);
#endif
            return;
      }
      
      maxbgsize=ta->xmax-ta->xmin+1+ta->ymax-ta->ymin;
      bgcol=(int *) malloc(sizeof(int)*maxbgsize);
      maxfgsize=ta->xmax-ta->xmin;
      fgcol=(int *) malloc(sizeof(int)*maxfgsize);

      if (ta->ymin != 0) {
            for (x = ta->xmin; x <= ta->xmax; ++x) {        
                  bgcol[curbgcolsize++] = 
                        cpssp->current_screen[ta->ymin][x];
                  cpssp->NAME.current_screen_binarized[ta->ymin][x]=TAP_0;
            }
      }
      if (ta->xmin != 0) {
            /* dont count start point twice */
            for (y = ta->ymin + 1; y <= ta->ymax; ++y) {
                  bgcol[curbgcolsize++] = 
                        cpssp->current_screen[y][ta->xmin];
                  cpssp->NAME.current_screen_binarized[y][ta->xmin]=TAP_0;
            }
      }
            
      cur_edge=ON_BG;

      y=ta->ymin + abs((ta->ymax-ta->ymin+1)/2);
      
      for (;;) {

            for (x=ta->xmin; x<ta->xmax; ++x) {
                  unsigned char e1;
                  int newfgcol;

                  /* only react on changes in that line (!) 
                   * i.e. horizontal edges */
                  e1 = NAME_(get_distance)(cpssp->current_screen[y][x], 
                              cpssp->current_screen[y][x+1]);


                  /* there is no edge */
                  if (e1 < EDGE_THRESHOLD) {

                        /* second chance: change in relation to last 
                         * fg col? */
                        e1 = NAME_(get_distance)(
                              cpssp->current_screen[y][lastfg],
                              cpssp->current_screen[y][x+1]);
                        if (e1 < EDGE_THRESHOLD) {
                              continue;
                        }
                  }

                  newfgcol = cpssp->current_screen[y][x+1];

                  /* check if that color is already in bg-puffer -> 
                   * bg-bg edge */
                  if (NAME_(color_in_array)(bgcol, curbgcolsize, newfgcol,
                                    TEXT_COLOR_FUZZINESS)) {
                        continue;
                  }

                  /* there is an edge, so look if we are on background.
                   * If yes, we just changed to foreground */
                  if (cur_edge==ON_BG) {
                        cur_edge=ON_FG;
                        /* change from background to foreground, i.e.
                         * pixel is fg/text */
                        fgcol[curfgcolsize++]=newfgcol;
                        lastfg=x;
                  } else {
                        cur_edge=ON_BG;
                  }
            }

            /* if we have at least one foreground color by now, stop */
            if (0 < curfgcolsize) {
                  break;
            }

            /* else, look in a different line! */
            y++;
            if (y > ta->ymax) {
                  y=ta->ymin;
            }
            
            lookfor++;
            if (lookfor==(ta->ymax-ta->ymin+1)) {
                  break;
            }
            
            continue;

      }
      
      /* store result = binarized text */
      for (y=ta->ymin; y<=ta->ymax; ++y) {
            for (x=ta->xmin; x<=ta->xmax; ++x) {
                  unsigned char drawit;
                  
                  if (NAME_(color_in_array)(fgcol, curfgcolsize, 
                                 cpssp->current_screen[y][x],
                                 TEXT_COLOR_FUZZINESS)) {
                        drawit=TAP_1;
                  } else if (NAME_(color_in_array)(bgcol, curbgcolsize,
                                 cpssp->current_screen[y][x], 
                                 TEXT_COLOR_FUZZINESS)) {
                        drawit=TAP_0;
                  } else {
                        int nearval, near, newval;
                        int i;

                        nearval=255; 
                        near=-1;

                        /* find closest color */
                        for (i=0; i<curfgcolsize; ++i) {
                              newval=NAME_(get_distance)(fgcol[i], 
                                    cpssp->current_screen[y][x]);
                              if (newval<nearval) {
                                    nearval=newval;
                                    near=ON_FG;
                              }
                        }
                        for (i=0; i<curbgcolsize; ++i) {
                              newval=NAME_(get_distance)(bgcol[i], 
                                    cpssp->current_screen[y][x]);
                              if (newval<nearval) {
                                    nearval=newval;
                                    near=ON_BG;
                              }
                        }
                        
                        if (near==ON_BG) {
                              drawit=TAP_0;
                        } else if (near==ON_FG) {
                              drawit=TAP_1;
                        } else {
                              /* not reached */
                              WARN("color at %d/%d had no closest "
                                   "color in bg (%d) or fg (%d) "
                                   "array?!\n", x, y, curbgcolsize,
                                   curfgcolsize);

                              drawit=TAP_0;
                        }
                  }

                  cpssp->NAME.current_screen_binarized[y][x]=drawit;
            }
            /* on last line, look if we have a E_TRUE_LINE below us, if yes,
             * try greedy-recursive-search to find another fg_colored pixel
             * near to a TAP_1 pixel
             */
            if ((y==ta->ymax) && (y <= cpssp->screen_dimensions.h - 2)) {
                  int noline=0;
                  int incymax=0;
                  for (x=ta->xmin; x<=ta->xmax; ++x) {
                        if (cpssp->NAME.current_edges_binarized[y+1][x]
                            != E_TRUE_LINE) {
                              noline=1;
                              break;
                        }
                  }
                  if (!noline) {
                        for (x=ta->xmin; (x<=ta->xmax) 
                                      && (incymax==0); ++x) {
                              if (cpssp->NAME.current_screen_binarized[y][x]
                                  ==TAP_0) {
                                    continue;
                              }
                                    
                              if (NAME_(get_distance)(
                                    cpssp->current_screen[y][x],
                                    cpssp->current_screen[y+1][x])
                                    < TEXT_COLOR_FUZZINESS) {
                                    /* found one */
                                    incymax=1;
                                    break;
                              }
                              if (x>ta->xmin) {
                                    if (NAME_(get_distance)(
                                          cpssp->current_screen[y][x], 
                                          cpssp->current_screen[y+1][x-1]) 
                                       < TEXT_COLOR_FUZZINESS) {

                                          /* found one */
                                          incymax=1;
                                          break;
                                    }
                              }
                              if (x<ta->xmax) {
                                    if (NAME_(get_distance)(
                                          cpssp->current_screen[y][x], 
                                          cpssp->current_screen[y+1][x+1])
                                       < TEXT_COLOR_FUZZINESS) {

                                          /* found one */
                                          incymax=1;
                                          break;
                                    }
                              }
                        }
                        if (incymax) {
                              ta->ymax++;
                              continue;
                        }
                  }
            }
      }

      ta->flags |= TAF_BINARIZED;
      free(bgcol);
      free(fgcol);

}

#undef ON_BG
#undef ON_FG


/* segmentates the chars of one text area */
static void
NAME_(segmentate_chars)(struct cpssp *cpssp, int curta)
{
      int x, y, yrange;
      /* number of empty columns since last char */
      int linecnt;
      /* number of TAP0/1's in a column */
      int column0cnt, column1cnt;
      int curchar;
      int charopen;
      int closeit;      
      single_text_area *ta;
      
      ta = &cpssp->NAME.text_area[curta];
      
      closeit=0;
      charopen=0;
      curchar=-1;
      linecnt=0;
      yrange=ta->ymax-ta->ymin+1;
      
      
      /* words are seperated by at least 3 pixels */
      for (x=ta->xmin; x<=ta->xmax; ++x) {
            /* number of TAP_0/1's in a column */
            column0cnt=0;
            column1cnt=0;
            for (y=ta->ymin; y<=ta->ymax; ++y) {
                  if (cpssp->NAME.current_screen_binarized[y][x]==TAP_1) {
                        ++column1cnt;
                  } else if (cpssp->NAME.current_screen_binarized[y][x]
                           ==TAP_0) {
                        ++column0cnt;
                  }
            }

            if (column1cnt==yrange) {
                  /* we found a column completely set with TAP_1's */
                  /* assume, TAP_0 is background, TAP_1 is foreground.
                   * set invert=1 if a whole colum is in TAP_1. meaning
                   * we need to swap TAP_0/1 when classifying the chars 
                   */
                  /* Note: this works because text areas start (due to
                   * their building process out of the edge image) one
                   * pixel left and *one pixel above* the actual text!! */
                  closeit=charopen;
                  ++linecnt;
                  
                  ta->flags|=TAF_INVERT;
            } else if (column0cnt==yrange) {
                  closeit=charopen;
                  ++linecnt;
            } else {
                  if (charopen==0) {
                        linecnt=0;
                        ++curchar;
                        /* text starting again so we need to begin a new
                         * character */
                        if (curchar >= MAX_CHARS_PER_TEXT_AREA) {
                              ERROR("text area character count reached"
                              " maximum (%d), this means this character"
                              " will not be processed! Increase "
                              "MAX_CHARS_PER_TEXT_AREA and recompile!"
                              "\n", MAX_CHARS_PER_TEXT_AREA);
                        } else {
                              /* store the beginning */
                              ta->rec_char[curchar].xmin=x;
                              ta->rec_char[curchar].ymin=ta->ymin;
                              ta->rec_char[curchar].ymax=ta->ymax;

                              charopen=1;
                        }
                  }
                  /* TODO FIXME sistsigw: store linecnt (=empty columns
                   * after last char) for last char, in order to
                   * "recognize" blanks between words.
                   */
                  linecnt=0;
            }

            if (linecnt==8) {

                  ++curchar;
                  
                  linecnt=0;
                  
                  /* we got 8 columns of 'nothing' -> insert a space 
                   * (' ') into the text area
                   */
                  if (curchar >= MAX_CHARS_PER_TEXT_AREA) {
                        ERROR("text area character count reached"
                                    " maximum (%d), this means this character"
                                    " will not be processed! Increase "
                                    "MAX_CHARS_PER_TEXT_AREA and recompile!"
                                    "\n", MAX_CHARS_PER_TEXT_AREA);
                  } else {
                        ta->rec_char[curchar].num_hypotheses=1;
                        ta->rec_char[curchar].c[0]=' ';
                  }
            }
            
            if (closeit) {
                  closeit=0;
                  /* if we have a character open, close it by
                   * setting its end */
                  ta->rec_char[curchar].xmax=x-1;
                  charopen=0;

                  ta->mean_char_width=(  (ta->rec_char[curchar].xmax
                                      - ta->rec_char[curchar].xmin)
                                    + curchar*ta->mean_char_width)
                                  / (curchar+1);
            }
      }

      if (charopen==1) {
            /* close last char, if still open. ends with text area then */
            ta->rec_char[curchar].xmax=ta->xmax;
            ta->mean_char_width=(  (ta->rec_char[curchar].xmax
                                - ta->rec_char[curchar].xmin)
                              + curchar*ta->mean_char_width)
                            / (curchar+1);
      }

      if (0 <= curchar) {
            ta->num_chars=curchar+1;
      }
      
}


/* takes all text areas and tries to recognize the words in it by splitting the
 * text areas into single words, which will be splitted into single characters.
 * Those can be classified later on.
 */
static void
NAME_(segmentate_text_areas)(struct cpssp *cpssp)
{
      int curta;

      DEBUG("Segmentating %d textareas\n", num_text_areas);
      
      for (curta = 0; curta < cpssp->NAME.num_text_areas; ++curta) {
            /* if text area is not in use (or was tagged as too small)
             * -> dont care about  */
            if (cpssp->NAME.text_area[curta].state != TA_INUSE) {
                  continue;
            }
            /* if text area is already done, also do nothing */
            if ((cpssp->NAME.text_area[curta].flags & TAF_RECCHAR)
                 ==TAF_RECCHAR) {
                  continue;
            }

            /* binarize the area and store result*/
            NAME_(binarize_text_area)(cpssp, curta);
            
            /* then go build the words */
            NAME_(segmentate_chars)(cpssp, curta);
      }
      
      /* invert inverted text areas */
      NAME_(invert_text_areas)(cpssp);
}



/***********************************************************************/
/* image segmentation - text area related
 */
/***********************************************************************/

/*
 * recognizes '.'s (dots) in the text areas and tries to connect them to their
 * corresponding counterpart (if available). ("place the dot on top of the 'i'")
 *
 * also tags small, unrecognizable areas.
 */
static void
NAME_(recognize_dots)(struct cpssp *cpssp) 
{
      int j, ret, i;
      int found;

      DEBUG("%s", "trying to recognize dots and connect them to their "
            "counterparts\n");

      for (j = 0; j < cpssp->NAME.num_text_areas; ++j) {
            if (cpssp->NAME.text_area[j].state!=TA_INUSE) {
                  continue;
            }
            
            /* possible dot ? */
            if ( ( (cpssp->NAME.text_area[j].xmax 
                    - cpssp->NAME.text_area[j].xmin + 1) <= MAX_DOT_WIDTH)
                &&
                 ( (cpssp->NAME.text_area[j].ymax
                    -cpssp->NAME.text_area[j].ymin + 1)
                    <= MAX_DOT_HEIGHT)) {

                  int xmin1, xmax1, ymin1, ymax1;
                  int xmin2, xmax2, ymin2, ymax2;

                  xmin1 = cpssp->NAME.text_area[j].xmin;
                  ymin1 = cpssp->NAME.text_area[j].ymin;
                  xmax1 = cpssp->NAME.text_area[j].xmax;
                  ymax1 = cpssp->NAME.text_area[j].ymax;
                  
                  found = 0;
                  for (i = 0; i < cpssp->NAME.num_text_areas; ++i) {
                        if (i==j) {
                              continue;
                        }
                        if (cpssp->NAME.text_area[i].state!=TA_INUSE) {
                              continue;
                        }
                        /* look for another TA max 3 pixels below */
                        xmin2=cpssp->NAME.text_area[i].xmin;
                        xmax2=cpssp->NAME.text_area[i].xmax;
                        ymin2=cpssp->NAME.text_area[i].ymin;
                        ymax2=cpssp->NAME.text_area[i].ymax;
                        if ((xmin2<=xmin1) && (xmax1<=xmax2)) {
                              if (   (ymin2<=(ymax1+3))
                                  && (ymin2>ymax1) ) {
                                    /* TODO maybe do this only, if
                                     * we really can recognize
                                     * something in such an extended
                                     * text area */
                                    cpssp->NAME.text_area[i].ymin =
                                                      ymin1;
                                    cpssp->NAME.text_area[j].state = 
                                                TA_UNDEFINED;
                                    found=1;
                                    break;
                              }
                        }
                  }
                  if (found) {
                        DEBUG("Merged TA %d into %d\n", j, i);
                        continue;
                  }

                  DEBUG("Couldn't find another nearby TA for TA %d\n", j);

                  /* if nothing was found, it could be a single '.' */
                  NAME_(binarize_text_area)(cpssp, j);
                  NAME_(segmentate_chars)(cpssp, j);
                  if ((cpssp->NAME.text_area[j].flags & TAF_INVERT) 
                        == TAF_INVERT) {

                        NAME_(invert_single_textarea)(cpssp, j);
                  }

                  NAME_(correct_boundaries)(
                              cpssp,
                              &cpssp->NAME.text_area[j].rec_char[0].xmin,
                              &cpssp->NAME.text_area[j].rec_char[0].ymin,
                              &cpssp->NAME.text_area[j].rec_char[0].xmax,
                              &cpssp->NAME.text_area[j].rec_char[0].ymax
                              );
                  /* correct boundaries of char 0 of that text area. 
                   * It is so small, there is no other glyph in
                   * it, anyway */
                  ret = NAME_(recognize_single_char)(cpssp, j, 0, 
                                          -1, -1, -1, -1);

                  if (!ret) {
                        /* small TA that contains nothing -> discard */
                        cpssp->NAME.text_area[j].state=TA_TOOSMALL;
                  }
            }
      }

      DEBUG("%s", "done\n");
}


/*
 * - recognize '.'s and try to extend that area in order to find a possible
 *   correspondence (i.e. assign the point of an 'i' to the 'i')
 * - try to recognize each text area
 * - discard unrecognized text areas (maybe connect nearby ones and try
 *   recognition again)
 * - connect nearby recognized areas to form words, connect words to form lines
 */
static void
NAME_(fill_text_areas)(struct cpssp *cpssp)
{
      NAME_(recognize_dots)(cpssp);
      NAME_(segmentate_text_areas)(cpssp);
      NAME_(prepare_char_recognition)(cpssp);
      NAME_(recognize_characters)(cpssp);
}


/***********************************************************************/
/* bounding-box-creation related
 */
/***********************************************************************/


/* 
 * tags all text areas which might contain text
 */
static void 
NAME_(reject_large_areas)(struct cpssp *cpssp)
{
      int i, w, h;
      
      for (i=0; i < cpssp->NAME.num_text_areas; ++i) {
            w=cpssp->NAME.text_area[i].xmax 
                  - cpssp->NAME.text_area[i].xmin + 1;
            h=cpssp->NAME.text_area[i].ymax 
                  - cpssp->NAME.text_area[i].ymin + 1;
            if (   (w > BB_MAX_TEXT_WIDTH) 
                || (h > BB_MAX_TEXT_HEIGHT) )  {
                  cpssp->NAME.text_area[i].state=TA_TOOLARGE;
            }
      }
}

/*
 * discard text areas that are completed contained in other areas 
 */
static void
NAME_(discard_double_areas)(struct cpssp *cpssp)
{
      int i, j;
      
      for (i = 0; i < cpssp->NAME.num_text_areas; ++i) {
            for (j=0; j < cpssp->NAME.num_text_areas; ++j) {
                  if (j==i) {
                        continue;
                  }

                  if (!(cpssp->NAME.text_area[i].xmin 
                        <= cpssp->NAME.text_area[j].xmin)) {
                        continue;
                  }
                  if (!(cpssp->NAME.text_area[i].xmax 
                        >= cpssp->NAME.text_area[j].xmax)) {
                        continue;
                  }
                  if (!(cpssp->NAME.text_area[i].ymin 
                        <= cpssp->NAME.text_area[j].ymin)) {
                        continue;
                  }
                  if (!(cpssp->NAME.text_area[i].ymax
                        >= cpssp->NAME.text_area[j].ymax)) {
                        continue;
                  }
                  
                  /* reached if j is completely contained in i */
                  cpssp->NAME.text_area[j].state=TA_UNDEFINED;
            }
      }
}


/* 
 * adds pixels which surround x,y to the text area tanum, thus increasing its
 * bounding box (if necessary)
 */
static void
NAME_(add_pixel)(struct cpssp *cpssp, int tanum, int x, int y)
{     
      /* second, mark current pixel as assigned to current object */
      cpssp->NAME.current_edges_binarized[y][x] = E_TRUE_DONE;
      
      /* set min/max x/y to be able to calculate width/height later */
      if (x < cpssp->NAME.text_area[tanum].xmin) {
            cpssp->NAME.text_area[tanum].xmin=x;
      }
      if (x > cpssp->NAME.text_area[tanum].xmax) {
            cpssp->NAME.text_area[tanum].xmax=x;
      }
      if (y < cpssp->NAME.text_area[tanum].ymin) {
            cpssp->NAME.text_area[tanum].ymin=y;
      }
      if (y > cpssp->NAME.text_area[tanum].ymax) {
            cpssp->NAME.text_area[tanum].ymax=y;
      }

      /* if there is a pixel above us */
      if (0 < y) {
            /* and we found an edge above */
            if (cpssp->NAME.current_edges_binarized[y-1][x]==E_TRUE) {
                  /* call add_pixel again */
                  NAME_(add_pixel)(cpssp, tanum, x, y-1);
            }
      }
      if (x < cpssp->screen_dimensions.w - 1) {
            if (cpssp->NAME.current_edges_binarized[y][x+1]==E_TRUE) {
                  NAME_(add_pixel)(cpssp, tanum, x+1, y);
            }
            if (0 < y) {
                  if (cpssp->NAME.current_edges_binarized[y-1][x+1]==E_TRUE) {
                        NAME_(add_pixel)(cpssp, tanum, x+1, y-1);
                  }
            }
            if (y < cpssp->screen_dimensions.h - 1) {
                  if (cpssp->NAME.current_edges_binarized[y+1][x+1]==E_TRUE) {
                        NAME_(add_pixel)(cpssp, tanum, x+1, y+1);
                  }
            }
      }
      if (y < cpssp->screen_dimensions.h - 1) {
            if (cpssp->NAME.current_edges_binarized[y+1][x]==E_TRUE) {
                  NAME_(add_pixel)(cpssp, tanum, x, y+1);
            }
      }
      if (0 < x) {
            if (cpssp->NAME.current_edges_binarized[y][x-1]==E_TRUE) {
                  NAME_(add_pixel)(cpssp, tanum, x-1, y);
            }
            if (0 < y) {
                  if (cpssp->NAME.current_edges_binarized[y-1][x-1]==E_TRUE) {
                        NAME_(add_pixel)(cpssp, tanum, x-1, y-1);
                  }
            }
            if (y < cpssp->screen_dimensions.h - 1) {
                  if (cpssp->NAME.current_edges_binarized[y+1][x-1]==E_TRUE) {
                        NAME_(add_pixel)(cpssp, tanum, x-1, y+1);
                  }
            }
      }
}


/* 
 * create a new object from one segment, starting at x,y and following the
 * edges
 */
static void
NAME_(begin_text_area)(struct cpssp *cpssp, int x, int y)
{
      int curta;
      
#ifdef TEST_CC
      DEBUG("adding new bounding box, beginning at %d, %d\n", x, y);
#endif

      curta = cpssp->NAME.num_text_areas;

      cpssp->NAME.text_area[curta].xmin = x;
      cpssp->NAME.text_area[curta].xmax = x;
      cpssp->NAME.text_area[curta].ymin = y;
      cpssp->NAME.text_area[curta].ymax = y;

      cpssp->NAME.text_area[curta].state = TA_INUSE;

      /* 
       * add all corresponding pixels to it
       */
      NAME_(add_pixel)(cpssp, curta, x, y);     
}


/*
 * segmentate edge image into single objects
 */
static void
NAME_(build_bounding_boxes)(struct cpssp *cpssp) 
{
      int x,y;
      int toomany=0;
      
      for (x = 0; (x < cpssp->screen_dimensions.w) && (!toomany); ++x) {
            for (y = 0; (y < cpssp->screen_dimensions.h) && (!toomany); ++y) {
                  if (cpssp->NAME.current_edges_binarized[y][x] == E_TRUE) {
                        NAME_(begin_text_area)(cpssp, x,y);
                        ++(cpssp->NAME.num_text_areas);

                        if (cpssp->NAME.num_text_areas == MAX_TEXT_AREAS) {
                              toomany=1;
                              break;
                        }
                  }
            }
      }

      if (toomany) {
            ERROR("Reached maximum number (%d) of text areas during build "
                  "process. Increase MAX_TEXT_AREAS and recompile!\n",
                  MAX_TEXT_AREAS);
      }

      NAME_(reject_large_areas)(cpssp);
      NAME_(discard_double_areas)(cpssp);
}


/* 
 * removes lines between start/end points of already removed lines (e.g. edge
 * lines around a block), that were too short to be removed in the step before -
 * but need to be removed as explained in the end of remove_lines() 
 */
static void
NAME_(remove_intermediate_lines)(struct cpssp *cpssp)
{
      int x, y, el1, el2;

      DEBUG("Removing intermediate lines, having %d long lines\n", 
            num_edge_lines);

      for (el1=0; el1 < cpssp->NAME.num_edge_lines; ++el1) {
            if (cpssp->NAME.edge_line[el1].state != TL_INUSE) {
                  continue;
            }
            
            if (cpssp->NAME.edge_line[el1].direction == LINE_HORIZ) {

            } else if (cpssp->NAME.edge_line[el1].direction == LINE_VERT) {
                  int foundstart=0, foundend=0;

                  DEBUG("Have vertical line %d (%d/%d-%d/%d) state %d, "
                        "direction %d, looking for line with same "
                        "start/end\n",
                        el1,
                        cpssp->NAME.edge_line[el1].x1,
                        cpssp->NAME.edge_line[el1].y1,
                        cpssp->NAME.edge_line[el1].x2,
                        cpssp->NAME.edge_line[el1].y2,
                        cpssp->NAME.edge_line[el1].state,
                        cpssp->NAME.edge_line[el1].direction
                  );
                  
                  /* look for vertical lines that start one pixel above or
                   * end at same height */
                  for (el2 = el1 + 1; el2 < cpssp->NAME.num_edge_lines; 
                        ++el2) {

                        int foundy=0;
                        int isline=1;

                        DEBUG("  checking line %d (%d/%d-%d/%d) state "
                              "%d direction %d\n",
                                    el2,
                                    cpssp->NAME.edge_line[el2].x1,
                                    cpssp->NAME.edge_line[el2].y1,
                                    cpssp->NAME.edge_line[el2].x2,
                                    cpssp->NAME.edge_line[el2].y2,
                                    cpssp->NAME.edge_line[el2].state,
                                    cpssp->NAME.edge_line[el2].direction
                             );
                        
                        if (cpssp->NAME.edge_line[el2].direction 
                            != LINE_VERT) {

                              continue;
                        }
                        if (cpssp->NAME.edge_line[el2].state != TL_INUSE) {
                              continue;
                        }
                        
                        /********************************
                         * start comparing start points *
                         ********************************/
                        DEBUG("%s", "  start points:\n");
                        
                        if (   (foundstart==0)
                            && (   (cpssp->NAME.edge_line[el2].y1
                                    == cpssp->NAME.edge_line[el1].y1-1) 
                                || (cpssp->NAME.edge_line[el2].y1
                                  == cpssp->NAME.edge_line[el1].y1)  )) {

                              foundy=cpssp->NAME.edge_line[el2].y1;

                              DEBUG("    for line %d (%d/%d-%d/%d) "
                                    "found line %d (%d/%d-%d/%d)\n",
                                    el1,
                                    cpssp->NAME.edge_line[el1].x1,
                                    cpssp->NAME.edge_line[el1].y1,
                                    cpssp->NAME.edge_line[el1].x2,
                                    cpssp->NAME.edge_line[el1].y2,
                                    el2,
                                    cpssp->NAME.edge_line[el2].x1,
                                    cpssp->NAME.edge_line[el2].y1,
                                    cpssp->NAME.edge_line[el2].x2,
                                    cpssp->NAME.edge_line[el2].y2
                                   );


                              /* if distance between lines is too
                               * high, there can't be a 'forgotten'
                               * line in between */
                              if (   (cpssp->NAME.edge_line[el2].x1
                                    - cpssp->NAME.edge_line[el1].x1)
                                  >= LINE_MIN_LENGTH) {
                                    DEBUG("%s", "    -> distance "
                                          "too big, stopping\n");
                                    continue;
                              }

                              /* look if there are pixels between */
                              y=foundy;
                              DEBUG("    checking %d-%d in line %d\n",
                                    cpssp->NAME.edge_line[el1].x1 + 1,
                                    cpssp->NAME.edge_line[el2].x1 - 1,
                                    y
                                    );
                              for (x = cpssp->NAME.edge_line[el1].x1 + 1;
                                   x < cpssp->NAME.edge_line[el2].x1; 
                                   ++x) {
                                    if (cpssp->NAME.current_edges_binarized[y][x]
                                        != E_TRUE) {
                                          isline=0;
                                          break;
                                    }
                              }

                              if (isline) {
                                    DEBUG("    -> additionally "
                                          "removing %d/%d - "
                                          "%d/%d\n",
                                          cpssp->NAME.edge_line[el1].x1 
                                                + 1,
                                          y,
                                          cpssp->NAME.edge_line[el2].x1,
                                          y
                                      );
                                    NAME_(remove_single_line)(
                                                cpssp,
                                                cpssp->NAME.edge_line[el1].x1 
                                                      + 1,
                                                y, 
                                                cpssp->NAME.edge_line[el2].x1
                                                      - cpssp->NAME.edge_line[el1].x1
                                                      - 1,
                                                LINE_HORIZ);
                                    foundstart = 1;
                              } else {
                                    DEBUG("%s", "    -> there was no"
                                                " continuous line in "
                                                "between\n");
                              }
                        }

                        /**********************************
                         * now the same for the endpoints *
                         **********************************/
                        DEBUG("%s", "  end points:\n");
                        isline=1;
                        if (   (foundend==0)
                            && (cpssp->NAME.edge_line[el2].y2 
                                == cpssp->NAME.edge_line[el1].y2)) {

                              foundy = cpssp->NAME.edge_line[el2].y2;

                              DEBUG("    for line %d (%d/%d-%d/%d) "
                                    "found line %d (%d/%d-%d/%d)\n",
                                    el1,
                                    cpssp->NAME.edge_line[el1].x1,
                                    cpssp->NAME.edge_line[el1].y1,
                                    cpssp->NAME.edge_line[el1].x2,
                                    cpssp->NAME.edge_line[el1].y2,
                                    el2,
                                    cpssp->NAME.edge_line[el2].x1,
                                    cpssp->NAME.edge_line[el2].y1,
                                    cpssp->NAME.edge_line[el2].x2,
                                    cpssp->NAME.edge_line[el2].y2
                                   );

                              /* if distance between lines is too
                               * high, there can't be a 'forgotten'
                               * line in between */
                              if (   (cpssp->NAME.edge_line[el2].x1 
                                      - cpssp->NAME.edge_line[el1].x1)
                                  >= LINE_MIN_LENGTH) {
                                    DEBUG("%s", "    -> distance "
                                          "too big, stopping\n");
                                    continue;
                              }

                              /* look if there are pixels between */
                              y = foundy;
                              DEBUG("    checking %d-%d in line %d\n",
                                    cpssp->NAME.edge_line[el1].x1+1,
                                    cpssp->NAME.edge_line[el2].x1-1,
                                    y
                                    );
                              for (x = cpssp->NAME.edge_line[el1].x1 + 1;
                                   x < cpssp->NAME.edge_line[el2].x1; 
                                   ++x) {
                                    if (cpssp->NAME.current_edges_binarized[y][x]
                                        !=E_TRUE) {

                                          isline=0;
                                          break;
                                    }
                              }

                              if (isline) {
                                    DEBUG("    -> additionally "
                                          "removing %d/%d - "
                                          "%d/%d\n",
                                          cpssp->NAME.edge_line[el1].x1 
                                                + 1,
                                          y,
                                          cpssp->NAME.edge_line[el2].x1,
                                          y
                                      );
                                    NAME_(remove_single_line)(
                                                cpssp,
                                                cpssp->NAME.edge_line[el1].x1
                                                      + 1, 
                                                y, 
                                                cpssp->NAME.edge_line[el2].x1 
                                                     - cpssp->NAME.edge_line[el1].x1
                                                     - 1, 
                                                LINE_HORIZ);
                                    foundend=1;
                              } else {
                                    DEBUG("%s", "    -> there was no"
                                                " continuous line in "
                                                "between\n");
                              }
                        }
                  }
            } else {
                  /* shouldnt happen (there is no other direction then
                   * LINE_HORIZ or LINE_VERT!!) */
                  assert(false);
            }
      }
}


/*
 * stores info about a single line in an own data structure and removes line
 * from current_edges_binarized
 */
static void
NAME_(remove_single_line)(
      struct cpssp *cpssp,
      int startx, int starty, 
      int length, 
      enum line_direction direction
) 
{
      int endx, endy;
      int i;
      int doit=1;
      
      if (cpssp->NAME.num_edge_lines >= MAX_EDGE_LINES) {
            WARN("Cannot store more then %d lines from edge image. Going "
                 "to remove line from edge image, but won't be able to "
                 "reference it later! Increase MAX_EDGE_LINES if "
                 "necessary"
                 "\n", MAX_EDGE_LINES);
            doit=0;
      }

      if (doit) {
            cpssp->NAME.edge_line[cpssp->NAME.num_edge_lines].x1 = 
                                                startx;
            cpssp->NAME.edge_line[cpssp->NAME.num_edge_lines].y1 = 
                                                starty;
            cpssp->NAME.edge_line[cpssp->NAME.num_edge_lines].direction = 
                                                direction;
            cpssp->NAME.edge_line[cpssp->NAME.num_edge_lines].state = 
                                                TL_INUSE;
      }
      
      if (direction == LINE_HORIZ) {
            endx = startx + length - 1;
#if TEST_LINEREMOVE
            DEBUG("Removing horizontal line %d-%d in line %d\n", startx, 
                  endx, starty);
#endif
            for (i=startx; i<=endx; ++i) {
                  cpssp->NAME.current_edges_binarized[starty][i]=E_TRUE_LINE;
            }
            if (doit) {
                  cpssp->NAME.edge_line[cpssp->NAME.num_edge_lines].x2 = 
                                                      endx;
                  cpssp->NAME.edge_line[cpssp->NAME.num_edge_lines].y2 = 
                                                      starty;
            }
            
      } else if (direction==LINE_VERT) {
            endy=starty+length-1;
#if TEST_LINEREMOVE
            DEBUG("Removing vertical line %d-%d in column %d\n", starty, 
                  endy, startx);
#endif
            for (i=starty; i<=endy; ++i) {
                  cpssp->NAME.current_edges_binarized[i][startx]=E_TRUE_LINE;
            }
            if (doit) {
                  cpssp->NAME.edge_line[cpssp->NAME.num_edge_lines].x2 =
                                                      startx;
                  cpssp->NAME.edge_line[cpssp->NAME.num_edge_lines].y2 =
                                                      endy;
            }
      } else {
            assert(false);
      }

      if (doit) {
            cpssp->NAME.num_edge_lines++;
      }
}


/*
 * "eats" lines away from edge-image
 */
static void
NAME_(remove_lines)(struct cpssp *cpssp)
{
      int x,y;
      int startx, endx;
      int starty, endy;

      DEBUG("%s", "Removing long lines from edge image\n");

      startx=0;
      endx=0;
      starty=0;
      endy=0;

      /* look for horizontal lines */
      for (y = 0; y < cpssp->screen_dimensions.h; ++y) {
            for (x = 0; x < cpssp->screen_dimensions.w; ++x) {
                  /* scan each line for an edge */
                  if (cpssp->NAME.current_edges_binarized[y][x]==E_TRUE) {
                        /* if found, look if there could be a line */
                        startx=x;
                        starty=y;
                        endy=y;

                        while (cpssp->NAME.current_edges_binarized[y][x]
                               ==E_TRUE) {
                              /* its ok to skip these loop passes 
                               * count with loopvar x*/
                              ++x;
                              if (x == cpssp->screen_dimensions.w) {
                                    break;
                              }
                        }
                        endx = x - 1;

                        if (LINE_MIN_LENGTH <= (endx-startx+1)) {
                              /* a new line was found from startx to
                               * endx with length (endx-startx+1)
                               */
#if TEST_LINEREMOVE
                              DEBUG("Found a horizontal line from "
                                    "%d to %d in line %d\n", 
                                    startx, endx, y);
#endif
                              NAME_(remove_single_line)(cpssp, 
                                          startx, 
                                          starty,
                                          (endx-startx+1), 
                                          LINE_HORIZ);
                        }
                  }

            }
      }
      
      /* look for vertical lines */
      for (x = 0; x < cpssp->screen_dimensions.w; ++x) {
            for (y = 0; y < cpssp->screen_dimensions.h; ++y) {
                  /* scan each line for an edge */
                  /* Note: also start from edges that are already counted
                   * as part of a horizontal line */
                  if ((cpssp->NAME.current_edges_binarized[y][x]==E_TRUE)
                      || (cpssp->NAME.current_edges_binarized[y][x]
                        ==E_TRUE_LINE) ) {
                        /* if found, look if there could be a line */
                        startx=x;
                        starty=y;
                        endx=x;

                        /* also go over parts of horizontal lines! */
                        while ((cpssp->NAME.current_edges_binarized[y][x]
                                 ==E_TRUE)
                                 || (cpssp->NAME.current_edges_binarized[y][x]
                                       ==E_TRUE_LINE) ) {
                              /* its ok to skip these loop passes 
                               * count with loopvar y*/
                              ++y;
                              if (y == cpssp->screen_dimensions.h) {
                                    break;
                              }
                        }
                        endy=y-1;

                        if (LINE_MIN_HEIGHT <= (endy-starty+1)) {
                              /* a new line was found from starty to
                               * endy with length (endy-starty+1)
                               */
#if TEST_LINEREMOVE
                              DEBUG("Found a vertical line from %d "
                                    "to %d in column %d\n", 
                                    starty, endy, x);
#endif
                              NAME_(remove_single_line)(
                                          cpssp,
                                          startx, starty, 
                                          (endy-starty+1), 
                                          LINE_VERT);
                        }
                  }

            }
      }

      /* Now we have stored info about lines that are longer then a certain
       * threshold. Problem that needs to be solved:
       * If we have e.g. a 2 pixel broad line (a), edge image will look like
       * (b), after line removal like (c):
       *
       *                 xx          x.
       *    xx          x x         . .
       *    xx          x x         . .
       *    xx          x x         . .
       *    xx          x x         . .
       *    xx          x x         . .
       *    xx          xxx         .x.
       *
       *    (a)         (b)         (c)
       *
       * So there will remain 2 pixels at the top and the bottom of the line.
       * This is a problem when there is a letter below that bottom pixel, as
       * it will be merged with it, then (assuming, its the point of an 'i' or
       * similar)
       *
       * This is fixed by following function, which checks if there are
       * continues lines between start/end points of lines.
       */
      NAME_(remove_intermediate_lines)(cpssp);

}


/***********************************************************************/
/* edge detection related functions
 */
/***********************************************************************/


/* 
 * calculates "distance" between two color values
 */
static double
NAME_(get_distance)(int c1, int c2)
{
      unsigned char r0,g0,b0,r1,g1,b1;
      double res;

      r0=(c1>>16)&0xff;
      g0=(c1>>8)&0xff;
      b0=c1&0xff;

      r1=(c2>>16)&0xff;
      g1=(c2>>8)&0xff;
      b1=c2&0xff;
      
      res=(1 / sqrt(3)) * sqrt( (r1-r0) * (r1-r0) + (g1-g0) * (g1-g0)
                        + (b1-b0) * (b1-b0) );

      return res;
}

/*
 * calculates edges
 *
 * different methods:
 *          squareroot of sum of ( diff r/g/b )^2           [1]
 *         OR sum of abs ( diff r/g/b )               [2]
 *         OR MAX abs ( diff r/g/b )                        [3]
 * 
 * Memo sistsigw: see paulus / amer script pg. 450:
 * TODO roberts cross?
 * TODO optimization: dont use [1] but [2] or [3] for better speed
 *
 * TODO maybe better (gonzales pg 234), because color edge detector:
 *    F = sqrt( 0.5*( (gxx + gyy) + (gxx-gyy)*cos(2*theta)
 *        + 2*gxy*sin(2*theta) );
 *
 *    where gxx = u*u, gyy = v*v, gxy = u*v
 *    and   u = (dR/dx)*r + (dG/dx)*g + (dB/dx)*b
 *          v same with /dy
 *    i.e.  gxx = u*u = |dR/dx|^2 + |dG/dx|^2 + |dB/dx|^2
 *
 *    and   (dF/dx) = Sobel on F in x-direction [-1|0|1]
 *    with  F = R/G/B plane
 *
 *    and theta = 0.5*(1/tan( (2*gxy) / (gxx=gyy) ))
 *
 * TODO or also better: edge detection in HSI-room on I(ntensity) component
 */
static void 
NAME_(compute_edges)(struct cpssp *cpssp) 
{
      int x,y; /* loop */
      unsigned char e1, e2;

      for (y = 0; y < cpssp->screen_dimensions.h - 1; y++) {
            for (x = 0; x < cpssp->screen_dimensions.w - 1; x++) {
                  /* Calculate edge as difference in r/g/b values between
                   * 2 pixels as described above.
                   * First do it horizontally, then, if no edge detected
                   * try to find an edge vertically.
                   * 
                   * Normalize result to 0..255
                   * 
                   * now 0 means no edge detected
                   *   255 means very strong edge
                   * 
                   * TODO maybe better algorithm - see above
                   */
                  
                  e1=NAME_(get_distance)(
                              cpssp->current_screen[y][x], 
                              cpssp->current_screen[y][x+1]);
                  e2=NAME_(get_distance)(
                              cpssp->current_screen[y][x], 
                              cpssp->current_screen[y+1][x]);

                  /* take the strongest edge */
                  if (e1 < e2) {
                        cpssp->NAME.current_edges[y][x]=e2;
                  } else {
                        cpssp->NAME.current_edges[y][x]=e1;
                  }
                  
                  /* now store the binarized version */
                  if (cpssp->NAME.current_edges[y][x] < EDGE_THRESHOLD) {
                        cpssp->NAME.current_edges_binarized[y][x]=E_FALSE;
                  } else {
                        cpssp->NAME.current_edges_binarized[y][x]=E_TRUE;
                  }
            }
      }
}


/***********************************************************************/
/* The magic section
 * uses functions from above to find patterns on the screen
 */
/***********************************************************************/

/* 
 * try to find buttons and tell about them on stdout
 *
 * called from ext-patternm run_check
 */
static void
NAME_(find_patterns)(struct cpssp *cpssp)
{
      DEBUG("%s", "looking for patterns...\n");

      /* reset data structures */
      NAME_(reset_data)(cpssp);
      NAME_(compute_edges)(cpssp);
      NAME_(remove_lines)(cpssp);
      NAME_(build_bounding_boxes)(cpssp);
      NAME_(fill_text_areas)(cpssp);
      NAME_(build_text_lines)(cpssp);
}

/***********************************************************************/
/* General Stuff, initialization, screen-update
 * TODO cleanup on shutdown? FIXME sistsigw
 */
/***********************************************************************/

/** initialize global font data (needed only once)
 * FIXME potyra: move to definitions area
 */
static void
patternm_text_static_init(void)
{
      static bool seen = false;

      if (seen) {
            return;
      }
      seen = true;

      /* sort the array saved in samples.c according to size of font, for 
       * faster lookup and classification of segmentated characters */
      qsort(&sample[0], NSAMPLES, sizeof(sample_struct), 
            NAME_(compare_samples));
      qsort(&sample2[0], NSAMPLES2, sizeof(ttf_sample_struct), 
            NAME_(compare_samples2));
}

/* 
 * reset data structures and initialize them
 *
 * TODO: possible optimization: reset structures from (0..num_elements), reset
 *       num_elements *thereafter* to 0. Saves resetting elements that did not
 *       contain anything previously!
 *
 *     On very first run reset everything, do that in a seperate init function
 *
 */
static void
NAME_(reset_data)(struct cpssp *cpssp) 
{
      int i, j;
      
      DEBUG("%s", "resetting data\n");

      for (i = 0; i < MAX_EDGE_LINES; ++i) {
            cpssp->NAME.edge_line[i].x1 = -1;
            cpssp->NAME.edge_line[i].y1 = -1;
            cpssp->NAME.edge_line[i].x2 = -1;
            cpssp->NAME.edge_line[i].y2 = -1;
            cpssp->NAME.edge_line[i].state = TL_UNDEFINED;
      }
      cpssp->NAME.num_edge_lines=0;
      
      /* dont reset current_screen here! */
      memset(cpssp->NAME.current_edges, 0, 
            sizeof(unsigned char)*MAX_WIDTH*MAX_HEIGHT);
      memset(cpssp->NAME.current_edges_binarized, E_FALSE, 
            sizeof(unsigned char)*MAX_WIDTH*MAX_HEIGHT);
      memset(cpssp->NAME.current_screen_binarized, 0, 
            sizeof(unsigned char)*MAX_WIDTH*MAX_HEIGHT);

      for (i=0; i < MAX_TEXT_AREAS; ++i) {
            cpssp->NAME.text_area[i].xmin = -1;
            cpssp->NAME.text_area[i].xmax = -1;
            cpssp->NAME.text_area[i].ymin = -1;
            cpssp->NAME.text_area[i].ymax = -1;
            cpssp->NAME.text_area[i].flags = TAF_UNDEFINED;
            cpssp->NAME.text_area[i].state = TA_UNDEFINED;
            cpssp->NAME.text_area[i].mean_char_width = -1.0;
            cpssp->NAME.text_area[i].num_chars = 0;
            for (j = 0; j < MAX_CHARS_PER_TEXT_AREA; ++j) {
                  cpssp->NAME.text_area[i].rec_char[j].xmin = 0;
                  cpssp->NAME.text_area[i].rec_char[j].xmax = 0;
                  cpssp->NAME.text_area[i].rec_char[j].ymin = 0;
                  cpssp->NAME.text_area[i].rec_char[j].ymax = 0;
                  cpssp->NAME.text_area[i].rec_char[j].num_hypotheses = 0;
                  memset(cpssp->NAME.text_area[i].rec_char[j].c, 0,
                        sizeof(char)*MAX_CHAR_HYPOTHESES);
                  
            }
      }
      cpssp->NAME.num_text_areas=0;

      for (i = 0; i < MAX_TEXT_LINES; ++i) {
            cpssp->NAME.text_line[i].xmin=-1;
            cpssp->NAME.text_line[i].ymin=-1;
            cpssp->NAME.text_line[i].xmax=-1;
            cpssp->NAME.text_line[i].ymax=-1;
            cpssp->NAME.text_line[i].state=TL_UNDEFINED;
            cpssp->NAME.text_line[i].num_chars=0;
            memset(cpssp->NAME.text_line[i].text, 0, 
                  sizeof(char)*(MAX_CHARS_PER_TEXT_LINE+1));
      }
      cpssp->NAME.num_text_lines = 0;
      cpssp->NAME.check_necessary = true;
}

#undef ENABLE_SPLITTING
#undef DEBUG_ENABLE
#undef WARNINGS
#undef TEST_TA
#undef TEST_CHARREC
#undef TEST_TTFCHARREC
#undef TEST_LINEREMOVE
#undef TEST_TL
#undef CDEBUG
#undef WARN
#undef ERROR
#undef DEPTH
#undef TAF_UNDEFINED
#undef TAF_RECCHAR
#undef TAF_INVERT
#undef TAF_BINARIZED
#undef TAP_0
#undef TAP_1
#undef LINE_MIN_LENGTH
#undef LINE_MIN_HEIGHT
#undef BB_MAX_TEXT_WIDTH
#undef BB_MAX_TEXT_HEIGHT
#undef MAX_DOT_WIDTH
#undef MAX_DOT_HEIGHT
#undef EDGE_THRESHOLD
#undef TEXT_COLOR_FUZZINESS

/**********************************************************************/
/* 
 * a new check of the screen is necessary:
 * - do all the fancy stuff in here (pattern recognition)
 * - call expect_text if you found something
 *   (-1 on nothing found i.e. PATTERN_NOT_FOUND
 *     1 if found i.e. PATTERN_FOUND
 * 
 */
static void
NAME_(run_check)(struct cpssp *cpssp)
{
      int i, res;
      bool searched = false;

      for (i = 0; i < MAX_SEARCH_STRINGS; i++) {
            if (! cpssp->NAME.search_string[i].active) {
                  continue;
            }

            if (! searched) {
                  NAME_(find_patterns)(cpssp);
                  searched = true;
            }

            res = NAME_(find_string)(
                        cpssp, 
                        cpssp->NAME.search_string[i].text);
            
            if (res) {
                  sig_boolean_set(cpssp->NAME.search_string[i].result,
                        &cpssp->NAME.search_string[i], 1);
            } else {
                  sig_boolean_set(cpssp->NAME.search_string[i].result,
                        &cpssp->NAME.search_string[i], 0);
            }
      }
}

/**********************************************************************/

static void
NAME_(buffer_event)(struct cpssp *cpssp)
{
      cpssp->NAME.check_necessary = true;
}

static void
NAME_(sync)(struct cpssp *cpssp)
{
      if (cpssp->NAME.check_necessary) {
            cpssp->NAME.check_necessary = false;
            NAME_(run_check)(cpssp);
      }
}

static void
NAME_(add_entry)(single_search_string *s, const char *str)
{
      struct cpssp *cpssp = (struct cpssp*)s->_cpssp;

      if (strlen(str) > sizeof(s->text) - 1) {
            faum_log(FAUM_LOG_ERROR, "patternm", "text", 
                  "watch entry string '%s' too long.\n", str);

            s->active = false;
            return;
      }

      strncpy(s->text, str, sizeof(s->text));
      s->active = true;
      cpssp->NAME.check_necessary = true;
}

static void
NAME_(remove_entry)(single_search_string *s)
{
      s->active = false;
}

static void
NAME_(string_set)(void *_s, const char* str)
{
      single_search_string *s = (single_search_string*)_s;

      if (*str) {
            /* add entry */
            NAME_(add_entry)(s, str);
      } else {
            /* disable entry */
            NAME_(remove_entry)(s);
      }
      sig_boolean_set(s->result, s, 0);
}

#define SETUP_SLOT(nr) \
      assert(port_text##nr != NULL); \
      assert(nr < MAX_SEARCH_STRINGS); \
      cpssp->NAME.search_string[nr].result = port_text##nr##_state; \
      sig_string_connect(port_text##nr, &cpssp->NAME.search_string[nr], &f);

static void
NAME_(init)(
      int nr,
        struct sig_string *port_text0,
        struct sig_boolean *port_text0_state,
        struct sig_string *port_text1,
        struct sig_boolean *port_text1_state,
        struct sig_string *port_text2,
        struct sig_boolean *port_text2_state,
        struct sig_string *port_text3,
        struct sig_boolean *port_text3_state,
      struct cpssp *cpssp
)
{
      int i;

      static const struct sig_string_funcs f = {
            .set = NAME_(string_set)
      };

      SETUP_SLOT(0);
      SETUP_SLOT(1);
      SETUP_SLOT(2);
      SETUP_SLOT(3);

      for (i = 0; i < MAX_SEARCH_STRINGS; i++) {
            cpssp->NAME.search_string[i].active = false;
            cpssp->NAME.search_string[i]._cpssp = cpssp;
      }
      
      /* FIXME potyra (see function defintion) */
      patternm_text_static_init();
}
#undef SETUP_SLOT
#undef DEBUG

#endif /* BEHAVIOR */

Generated by  Doxygen 1.6.0   Back to index