li_recognizer.c

PIXIL is a small footprint operating environment, complete with PDA PIM applications, a browser and

    }
}


/*
 *  Main recognition routine -- called by HRE API.
 */
static char *
lialg_recognize_stroke(rClassifier * rec, point_list * stroke)
{
    int i;
    char *name = NULL;
    point_list *input_dompts = NULL;
    char *best_name = NULL;
    int best_score = WORST_SCORE;
    char *curr_name;
    point_list *curr_dompts = NULL;
    //struct timeval stv, etv;
    //int       elapsed;

    /*    (void)gettimeofday(&stv, NULL); */

    if (stroke->npts < 1)
	goto done;

    /* Check for tap. */
    {
/*
	pen_point *startpt = &stroke->pts[0];
	pen_point *endpt = &stroke->pts[stroke->npts - 1];
	int dt = endpt->time - startpt->time;
	int dx = endpt->x - startpt->x;
	int dy = endpt->y - startpt->y;
	int magsq = dx * dx + dy * dy;
*/

	/* First thing is to filter out ``close points.'' */
	if (lialg_filter_points(stroke) != 0)
	    return (NULL);

	/* Unfortunately, we don't have the actual time that each point */
	/* was recorded (i.e., dt is invalid).  Hence, we have to use a */
	/* heuristic based on total distance and the number of points. */
	if (stroke->npts == 1 || lialg_compute_pathlen(stroke) < TAP_PATHLEN)
	    return (TAP_CHAR);
    }

    /* Pre-process input stroke. */
    if (lialg_preprocess_stroke(stroke) != 0)
	goto done;

    /* Compute its dominant points. */
    input_dompts = lialg_compute_dominant_points(stroke);
    if (input_dompts == NULL)
	goto done;

    /* Score input stroke against every class in classifier. */
    for (i = 0, curr_name = rec->cnames[i], curr_dompts = rec->dompts[i];
	 i < MAXSCLASSES && curr_name != NULL && curr_dompts != NULL;
	 i++, curr_name = rec->cnames[i], curr_dompts = rec->dompts[i]) {
	int sim;
	int dist;
	int curr_score;

	lialg_score_stroke(input_dompts, curr_dompts, &sim, &dist);
	curr_score = dist;

	if (lidebug && curr_score < DIST_THLD)
	    fprintf(stderr, "(%s, %d, %d) ", curr_name, sim, dist);

	/* Is it the best so far? */
	if (curr_score < best_score && curr_score <= DIST_THLD) {
	    best_score = curr_score;
	    best_name = curr_name;
	}
    }

    if (lidebug)
	fprintf(stderr, "\n");

    /* No errors. */
    name = best_name;

  done:
    delete_examples(input_dompts);
    /*    (void)gettimeofday(&etv, NULL);
       elapsed = (1000 * (etv.tv_sec - stv.tv_sec)) + ((etv.tv_usec - stv.tv_usec + 500) / 1000);
       fprintf(stderr, "elapsed = %d\n", elapsed);
     */
    return (name);
}


static int
lialg_preprocess_stroke(point_list * points)
{
    int minx, miny, maxx, maxy, xrange, yrange, scale, xoff, yoff;

    /* Filter out points that are too close. */
    /* We did this earlier, when we checked for a tap. */
/*
    if (lialg_filter_points(points) != 0) return(-1);
*/

/*    assert(points->npts > 0);*/

    /* Scale up to avoid conversion errors. */
    lialg_get_bounding_box(points, &minx, &miny, &maxx, &maxy);
    xrange = maxx - minx;
    yrange = maxy - miny;
    scale = (((100 * xrange + CANONICAL_X / 2) / CANONICAL_X) >
	     ((100 * yrange + CANONICAL_Y / 2) / CANONICAL_Y))
	? (100 * CANONICAL_X + xrange / 2) / xrange
	: (100 * CANONICAL_Y + yrange / 2) / yrange;
    if (lialg_translate_points(points, minx, miny, scale, scale) != 0)
	return (-1);

    /* Center the stroke. */
    lialg_get_bounding_box(points, &minx, &miny, &maxx, &maxy);
    xrange = maxx - minx;
    yrange = maxy - miny;
    xoff = -((CANONICAL_X - xrange + 1) / 2);
    yoff = -((CANONICAL_Y - yrange + 1) / 2);
    if (lialg_translate_points(points, xoff, yoff, 100, 100) != 0)
	return (-1);

    /* Store the x and y ranges in the point list. */
    xrange = maxx - minx;
    yrange = maxy - miny;
    points->xrange = xrange;
    points->yrange = yrange;

    if (lidebug) {
	int i;
	fprintf(stderr, "After pre-processing:   %d %d %d %d\n",
		minx, miny, maxx, maxy);
	for (i = 0; i < points->npts; i++)
	    fprintf(stderr, "      (%d %d)\n",
		    points->pts[i].x, points->pts[i].y);
	fflush(stderr);
    }

    return (0);
}


static point_list *
lialg_compute_dominant_points(point_list * points)
{
    point_list *ipts = NULL;
    region_list *regions = NULL;
    point_list *dpts = NULL;

    /* Interpolate points. */
    ipts = lialg_interpolate_points(points);
    if (ipts == NULL)
	return (NULL);
    if (lidebug) {
	int j;
	fprintf(stderr, "After interpolation:  %d ipts\n", ipts->npts);
	for (j = 0; j < ipts->npts; j++) {
	    fprintf(stderr, "  (%d, %d), %ld\n",
		    ipts->pts[j].x, ipts->pts[j].y, ipts->pts[j].chaincode);
	}
	fflush(stderr);
    }

    /* Compute regions. */
    regions = lialg_compute_regions(ipts);
/*    assert(regions != NULL);*/

    /* Compute dominant points. */
    dpts = lialg_compute_dompts(ipts, regions);
    if (lidebug) {
	int j;
	fprintf(stderr, "Dominant points:  ");
	for (j = 0; j < dpts->npts; j++) {
	    fprintf(stderr, "%d %d (%ld)  ",
		    dpts->pts[j].x, dpts->pts[j].y, dpts->pts[j].chaincode);
	}
	fprintf(stderr, "\n");
	fflush(stderr);
    }

    /* Delete region data structure. */
    {
	region_list *curr, *next;
	for (curr = regions; curr != NULL;) {
	    next = curr->next;
	    free(curr);
	    curr = next;
	}
    }
    delete_examples(ipts);
    return (dpts);
}


/* Input points are assumed to be integer-valued! */
static point_list *
lialg_interpolate_points(point_list * points)
{
    int i, j;
    int maxpts;
    point_list *newpts;

    /* Compute an upper-bound on the number of interpolated points. */
    maxpts = 0;
    for (i = 0; i < (points->npts - 1); i++) {
	pen_point *pta = &(points->pts[i]);
	pen_point *ptb = &(points->pts[i + 1]);
	maxpts += abs(pta->x - ptb->x) + abs(pta->y - ptb->y);
    }

    /* Allocate an array of the requisite size. */
    maxpts += points->npts;
    /* newpts = (point_list *)safe_malloc(sizeof(point_list)); */
    newpts = allocate(1, point_list);
    newpts->pts = make_pen_point_array(maxpts);
    if (newpts->pts == NULL) {
	free(newpts);
	return (NULL);
    }
    newpts->npts = maxpts;
    newpts->next = NULL;

    /* Interpolate each of the segments. */
    j = 0;
    for (i = 0; i < (points->npts - 1); i++) {
	pen_point *startpt = &(points->pts[i]);
	pen_point *endpt = &(points->pts[i + 1]);

	lialg_bresline(startpt, endpt, newpts, &j);

	j--;			/* end point gets recorded as start point of next segment! */
    }

    /* Add-in last point. */
    newpts->pts[j++] = points->pts[points->npts - 1];
    newpts->npts = j;

    /* Compute the chain code for P (the list of points). */
    lialg_compute_unit_chain_code(newpts);

    return (newpts);
}


/* This implementation is due to Kenny Hoff. */
static void
lialg_bresline(pen_point * startpt, pen_point * endpt,
	       point_list * newpts, int *j)
{
    int Ax, Ay, Bx, By, dX, dY, Xincr, Yincr;

    Ax = startpt->x;
    Ay = startpt->y;
    Bx = endpt->x;
    By = endpt->y;

    /* INITIALIZE THE COMPONENTS OF THE ALGORITHM THAT ARE NOT AFFECTED */
    /* BY THE SLOPE OR DIRECTION OF THE LINE */
    dX = abs(Bx - Ax);		/* store the change in X and Y of the line endpoints */
    dY = abs(By - Ay);

    /* DETERMINE "DIRECTIONS" TO INCREMENT X AND Y (REGARDLESS OF DECISION) */
    if (Ax > Bx) {
	Xincr = -1;
    } else {
	Xincr = 1;
    }				/* which direction in X? */
    if (Ay > By) {
	Yincr = -1;
    } else {
	Yincr = 1;
    }				/* which direction in Y? */

    /* DETERMINE INDEPENDENT VARIABLE (ONE THAT ALWAYS INCREMENTS BY 1 (OR -1) ) */
    /* AND INITIATE APPROPRIATE LINE DRAWING ROUTINE (BASED ON FIRST OCTANT */
    /* ALWAYS). THE X AND Y'S MAY BE FLIPPED IF Y IS THE INDEPENDENT VARIABLE. */
    if (dX >= dY) {		/* if X is the independent variable */
	int dPr = dY << 1;	/* amount to increment decision if right is chosen (always) */
	int dPru = dPr - (dX << 1);	/* amount to increment decision if up is chosen */
	int P = dPr - dX;	/* decision variable start value */

	/* process each point in the line one at a time (just use dX) */
	for (; dX >= 0; dX--) {
	    newpts->pts[*j].x = Ax;
	    newpts->pts[*j].y = Ay;
	    (*j)++;

	    if (P > 0) {	/* is the pixel going right AND up? */
		Ax += Xincr;	/* increment independent variable */
		Ay += Yincr;	/* increment dependent variable */
		P += dPru;	/* increment decision (for up) */
	    } else {		/* is the pixel just going right? */
		Ax += Xincr;	/* increment independent variable */
		P += dPr;	/* increment decision (for right) */
	    }
	}
    } else {			/* if Y is the independent variable */
	int dPr = dX << 1;	/* amount to increment decision if right is chosen (always) */
	int dPru = dPr - (dY << 1);	/* amount to increment decision if up is chosen */
	int P = dPr - dY;	/* decision variable start value */

	/* process each point in the line one at a time (just use dY) */
	for (; dY >= 0; dY--) {
	    newpts->pts[*j].x = Ax;
	    newpts->pts[*j].y = Ay;
	    (*j)++;

	    if (P > 0) {	/* is the pixel going up AND right? */
		Ax += Xincr;	/* increment dependent variable */
		Ay += Yincr;	/* increment independent variable */
		P += dPru;	/* increment decision (for up) */
	    } else {		/* is the pixel just going up? */
		Ay += Yincr;	/* increment independent variable */
		P += dPr;	/* increment decision (for right) */
	    }
	}
    }
}


static void
lialg_compute_chain_code(point_list * pts)
{
    int i;

    for (i = 0; i < (pts->npts - 1); i++) {
	pen_point *startpt = &(pts->pts[i]);
	pen_point *endpt = &(pts->pts[i + 1]);
	int dx = endpt->x - startpt->x;
	int dy = endpt->y - startpt->y;
/*
	int tmp	= rint(4.0 * atan2((double)dx, (double)dy) / M_PI);
	int dircode = (10 + tmp) % 8;
*/
	int tmp = quadr(likeatan(dy, dx));
	int dircode = (12 - tmp) % 8;

	startpt->chaincode = dircode;
    }
}


static void
lialg_compute_unit_chain_code(point_list * pts)
{
    int i;

    for (i = 0; i < (pts->npts - 1); i++) {
	pen_point *startpt = &(pts->pts[i]);
	pen_point *endpt = &(pts->pts[i + 1]);
	int dx = endpt->x - startpt->x;
	int dy = endpt->y - startpt->y;
	int dircode = lialg_dctbl[dx + 1][dy + 1];

/*	assert(dircode < 8);*/
	startpt->chaincode = dircode;
    }
}


static region_list *
lialg_compute_regions(point_list * pts)
{
    region_list *regions = NULL;
    region_list *curr_reg = NULL;
    int *R[2 + LP_FILTER_ITERS];
    int *junk;
    int *curr, *next;
    int i, j;

    /* Initialize low-pass filter parameters if necessary. */
    if (lialg_lpfconst == -1)
	lialg_compute_lpf_parameters();

    /* Allocate a 2 x pts->npts array for use in computing the (filtered) Angle set, A_n. */
    /*    junk = (int *)safe_malloc((2 + LP_FILTER_ITERS) * pts->npts * sizeof(int)); */
    junk = allocate((2 + LP_FILTER_ITERS) * pts->npts, int);
    for (i = 0; i < (2 + LP_FILTER_ITERS); i++)
	R[i] = junk + (i * pts->npts);
    curr = R[0];

    /* Compute the Angle set, A, in the first element of array R. */
    /* Values in R are in degrees, x 100. */
    curr[0] = 18000;		/* a_0 */
    for (i = 1; i < (pts->npts - 1); i++) {
	int d_i = pts->pts[i].chaincode;
	int d_iminusone = pts->pts[i - 1].chaincode;
	int a_i;

	if (d_iminusone < d_i)
	    d_iminusone += 8;

	a_i = (d_iminusone - d_i) % 8;

	/* convert to degrees, x 100 */
	curr[i] = ((12 - a_i) % 8) * 45 * 100;
    }
    curr[pts->npts - 1] = 18000;	/* a_L-1 */

    /* Perform a number of filtering iterations. */
    next = R[1];
    for (j = 0; j < LP_FILTER_ITERS; j++, curr = R[j], next = R[j + 1]) {
	for (i = 0; i < pts->npts; i++) {
	    int k;

	    next[i] = 0;

	    for (k = i - LP_FILTER_WIDTH; k <= i + LP_FILTER_WIDTH; k++) {
		int oldval = (k < 0 || k >= pts->npts) ? 18000 : curr[k];
		next[i] += oldval * lialg_lpfwts[k - (i - LP_FILTER_WIDTH)];	/* overflow? */
	    }

	    next[i] /= lialg_lpfconst;
	}
    }

    /* Do final thresholding around PI. */
    /* curr and next are set-up correctly at end of previous loop! */
    for (i = 0; i < pts->npts; i++) {
	next[i] = (abs(curr[i] - 18000) < LP_FILTER_THLD)
	    ? 18000 : curr[i];
    }
    curr = next;

    /* Debugging. */
    if (lidebug > 1) {
	for (i = 0; i < pts->npts; i++) {
	    fprintf(stderr, "%3d:  (%3d, %3d)  %ld  ",
		    i, pts->pts[i].x, pts->pts[i].y, pts->pts[i].chaincode);
	    for (j = 0; j < 2 + LP_FILTER_ITERS; j++)
		fprintf(stderr, "%d  ", R[j][i]);
	    fprintf(stderr, "\n");
	}
    }

    /* Do the region segmentation. */
    {
	int start, end;
	int currtype;

#define	RGN_TYPE(val)\
    (((val) == 18000)\
	? RGN_PLAIN\
	: ((val) < 18000 ? RGN_CONCAVE : RGN_CONVEX))

	start = 0;
	currtype = RGN_TYPE(curr[0]);
	/*      regions = (region_list *)safe_malloc(sizeof(region_list)); */
	regions = allocate(1, region_list);
	curr_reg = regions;
	curr_reg->start = start;
	curr_reg->end = 0;
	curr_reg->type = currtype;
	curr_reg->next = NULL;
	for (i = 1; i < pts->npts; i++) {
	    int nexttype = RGN_TYPE(curr[i]);

	    if (nexttype != currtype) {
		region_list *next_reg = NULL;

		end = i - 1;
		curr_reg->end = end;
		if (lidebug > 1)
		    fprintf(stderr, "  (%d, %d), %d\n", start, end, currtype);

		start = i;
		currtype = nexttype;
		/* next_reg = (region_list *)safe_malloc(sizeof(region_list)); */
		next_reg = allocate(1, region_list);
		next_reg->start = start;
		next_reg->end = 0;
		next_reg->type = nexttype;
		next_reg->next = NULL;

		curr_reg->next = next_reg;
		curr_reg = next_reg;
	    }
	}
	end = i - 1;
	curr_reg->end = end;
	if (lidebug > 1)
	    fprintf(stderr, "  (%d, %d), %d\n", start, end, currtype);

	/* Filter out convex/concave regions that are too short. */
	for (curr_reg = regions; curr_reg; curr_reg = curr_reg->next)
	    if (curr_reg->type == RGN_PLAIN) {
		region_list *next_reg;

		for (next_reg = curr_reg->next;
		     next_reg != NULL &&
		     (next_reg->end - next_reg->start) < LP_FILTER_MIN;
		     next_reg = curr_reg->next) {
		    /* next_reg must not be plain, and it must be followed by a plain */
		    /* assert(next_reg->type != RGN_PLAIN); */
		    /* assert(next_reg->next != NULL && (next_reg->next)->type == RGN_PLAIN); */

		    curr_reg->next = (next_reg->next)->next;
		    curr_reg->end = (next_reg->next)->end;

		    free(next_reg->next);
		    free(next_reg);
		}
	    }

	/* Add-in pseudo-extremes. */
	{
	    region_list *tmp, *prev_reg;

	    tmp = regions;
	    regions = NULL;
	    prev_reg = NULL;
	    for (curr_reg = tmp; curr_reg; curr_reg = curr_reg->next) {
		if (curr_reg->type == RGN_PLAIN) {
		    int arclen = lialg_compute_pathlen_subset(pts,
							      curr_reg->start,
							      curr_reg->end);
		    int dx = pts->pts[curr_reg->end].x -
			pts->pts[curr_reg->start].x;
		    int dy = pts->pts[curr_reg->end].y -
			pts->pts[curr_reg->start].y;
		    int chordlen = isqrt(10000 * (dx * dx + dy * dy));
		    int atcr =
			(chordlen ==
			 0) ? 0 : (100 * arclen + chordlen / 2) / chordlen;

		    if (lidebug)
			fprintf(stderr, "%d, %d, %d\n", arclen, chordlen,
				atcr);

		    /* Split region if necessary. */
		    if (arclen >= PE_AL_THLD && atcr >= PE_ATCR_THLD) {