li_recognizer.c

开放源码实时操作系统源码.

	dpts = allocate(1, point_list);
	dpts->pts = make_pen_point_array(npts);
	if (dpts->pts == NULL) goto failed;
	dpts->npts = npts;
	dpts->next = NULL;

	/* Read in each point. */
	for (j = 0; j < npts; j++) {
	    int x, y;

	    if (fscanf(fp, "%d %d", &x, &y) != 2) goto failed;
	    dpts->pts[j].x = x;
	    dpts->pts[j].y = y;
	}

	/* Compute the chain-code. */
	lialg_compute_chain_code(dpts);

	/* Store the list in the rec data structure. */
	rec->dompts[nclasses] = dpts;

	continue;

failed:
	fprintf(stderr, "read_classifier_digest failed...\n");
	for (; nclasses >= 0; nclasses--) {
	    if (rec->cnames[nclasses] != NULL) {
		free(rec->cnames[nclasses]);
		rec->cnames[nclasses] = NULL;
	    }
	    if (rec->dompts[nclasses] != NULL) {
		delete_examples(rec->dompts[nclasses]);
		rec->dompts[nclasses] = NULL;
	    }
	}
	if (dpts != NULL)
	    delete_examples(dpts);
	fclose(fp);
	return(-1);
    }

    fclose(fp);
    return(0);
}


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

  Canonicalization routines

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

static int lialg_canonicalize_examples(rClassifier *rec) {
    int i;
    int nclasses;

    if (lidebug) {
        fprintf(stderr, "lialg_canonicalize_examples working on %s\n",
		rec->file_name);
    }
    /* Initialize canonical-example arrays. */
    for (i = 0; i < MAXSCLASSES; i++) {
	rec->canonex[i] = NULL;
    }

    /* Figure out number of classes. */
    for (nclasses = 0;
	  nclasses < MAXSCLASSES && rec->cnames[nclasses] != NULL;
	  nclasses++)
	;

    /* Canonicalize the examples for each class. */
    for (i = 0; i < nclasses; i++) {
	int j, k;
	int nex;
	point_list *pts, *tmp, *avg;
	int maxxrange, maxyrange;
	int minx, miny, maxx, maxy;
	int avgxrange, avgyrange, avgxoff, avgyoff, avgscale;

	
	if (lidebug) {
	    fprintf(stderr, "lialg_canonicalize_examples working on class %s\n",
		    rec->cnames[i]);
	}
	/* Make a copy of the examples. */
	pts = NULL;
	tmp = rec->ex[i];
	for (nex = 0; tmp != NULL; nex++, tmp = tmp->next) {
	    if ((pts = add_example(pts, tmp->npts, tmp->pts)) == NULL) {
		delete_examples(pts);
		return(-1);
	    }
	}

	/* Canonicalize each example, and derive the max x and y ranges. */
	maxxrange = 0;
	maxyrange = 0;
	for (j = 0, tmp = pts; j < nex; j++, tmp = tmp->next) {
	    if (lialg_canonicalize_example_stroke(tmp) != 0) {
  	        if (lidebug) {
		    fprintf(stderr, "lialg_canonicalize_example_stroke returned error\n");
		}
		return(-1);
	    }

	    if (tmp->xrange > maxxrange) maxxrange = tmp->xrange;
	    if (tmp->yrange > maxyrange) maxyrange = tmp->yrange;
	}

	/* Normalize max ranges. */
	if (((100 * maxxrange + CANONICAL_X / 2) / CANONICAL_X) >
	    ((100 * maxyrange + CANONICAL_Y / 2) / CANONICAL_Y)) {
	    maxyrange = (maxyrange * CANONICAL_X + maxxrange / 2) / maxxrange;
	    maxxrange = CANONICAL_X;
	}
	else {
	    maxxrange = (maxxrange * CANONICAL_Y + maxyrange / 2) / maxyrange;
	    maxyrange = CANONICAL_Y;
	}

	/* Re-scale each example to max ranges. */
	for (j = 0, tmp = pts; j < nex; j++, tmp = tmp->next) {
	    int scalex = (tmp->xrange == 0) ? 100 : (100 * maxxrange + tmp->xrange / 2) / tmp->xrange;
	    int scaley = (tmp->yrange == 0) ? 100 : (100 * maxyrange + tmp->yrange / 2) / tmp->yrange;
	    if (lialg_translate_points(tmp, 0, 0, scalex, scaley) != 0) {
		delete_examples(pts);
		return(-1);
	    }
	}

	/* Average the examples; leave average in first example. */
	avg = pts;				/* careful aliasing!! */
	for (k = 0; k < NCANONICAL; k++) {
	    int xsum = 0;
	    int ysum = 0;

	    for (j = 0, tmp = pts; j < nex; j++, tmp = tmp->next) {
		xsum += tmp->pts[k].x;
		ysum += tmp->pts[k].y;
	    }

	    avg->pts[k].x = (xsum + j / 2) / j;
	    avg->pts[k].y = (ysum + j / 2) / j;
	}

	/* Compute BB of averaged stroke and re-scale. */
	lialg_get_bounding_box(avg, &minx, &miny, &maxx, &maxy);
	avgxrange = maxx - minx;
	avgyrange = maxy - miny;
	avgscale = (((100 * avgxrange + CANONICAL_X / 2) / CANONICAL_X) >
		    ((100 * avgyrange + CANONICAL_Y / 2) / CANONICAL_Y))
	  ? (100 * CANONICAL_X + avgxrange / 2) / avgxrange
	  : (100 * CANONICAL_Y + avgyrange / 2) / avgyrange;
	if (lialg_translate_points(avg, minx, miny, avgscale, avgscale) != 0) {
	    delete_examples(pts);
	    return(-1);
	}

	/* Re-compute the x and y ranges and center the stroke. */
	lialg_get_bounding_box(avg, &minx, &miny, &maxx, &maxy);
	avgxrange = maxx - minx;
	avgyrange = maxy - miny;
	avgxoff = -((CANONICAL_X - avgxrange + 1) / 2);
	avgyoff = -((CANONICAL_Y - avgyrange + 1) / 2);
	if (lialg_translate_points(avg, avgxoff, avgyoff, 100, 100) != 0) {
	    delete_examples(pts);
	    return(-1);
	}

	/* Create a point list to serve as the ``canonical representation. */
	if ((rec->canonex[i] = add_example(NULL, avg->npts, avg->pts)) == NULL) {
	    delete_examples(pts);
	    return(-1);
	}
	(rec->canonex[i])->xrange = maxx - minx;
	(rec->canonex[i])->yrange = maxy - miny;

	if (lidebug) {
	    fprintf(stderr, "%s, avgpts = %d\n", rec->cnames[i], avg->npts);
	    for (j = 0; j < avg->npts; j++) {
		fprintf(stderr, "  (%d, %d)\n",
			avg->pts[j].x, avg->pts[j].y);
	    }
	}

	/* Compute dominant points of canonical representation. */
	rec->dompts[i] = lialg_compute_dominant_points(avg);

	/* Clean up. */
	delete_examples(pts);
    }

    /* Sanity check. */
    for (i = 0; i < nclasses; i++) {
	char *best_name = lialg_recognize_stroke(rec, rec->canonex[i]);

	if (best_name != rec->cnames[i])
	    fprintf(stderr, "%s, best = %s\n", rec->cnames[i], best_name);
    }

    return(0);
}


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

    /* Filter out points that are too close. */
    if (lialg_filter_points(points) != 0) return(-1);

    /* Must be at least two points! */
    if (points->npts < 2) {
        if (lidebug) {
	    fprintf(stderr, "lialg_canonicalize_example_stroke: npts=%d\n",
		    points->npts);
	}
        return(-1);
    }

    /* 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) {
        if (lidebug) {
	    fprintf(stderr, "lialg_translate_points (minx=%d,miny=%d,scale=%d) returned error\n", minx, miny, scale);
	}
	return(-1);
    }

    /* Compute an equivalent stroke with equi-distant points. */
    if (lialg_compute_equipoints(points) != 0) return(-1);

    /* Re-translate the points to the origin. */
    lialg_get_bounding_box(points, &minx, &miny, &maxx, &maxy);
    if (lialg_translate_points(points, minx, miny, 100, 100) != 0) {
        if (lidebug) {
	    fprintf(stderr, "lialg_translate_points (minx=%d,miny=%d) returned error\n", minx, miny);
	}
        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, "Canonicalized:   %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 int lialg_compute_equipoints(point_list *points) {
    pen_point *equipoints = make_pen_point_array(NCANONICAL);
    int nequipoints = 0;
    int pathlen = lialg_compute_pathlen(points);
    int equidist = (pathlen + (NCANONICAL - 1) / 2) / (NCANONICAL - 1);
    int i;
    int dist_since_last_eqpt;
    int remaining_seglen;
    int dist_to_next_eqpt;

    if (equipoints == NULL) {
	error("can't allocate memory in lialg_compute_equipoints");
	return(-1);
    }

    if (lidebug) {
	fprintf(stderr, "compute_equipoints:  npts = %d, pathlen = %d, equidist = %d\n",
		points->npts, pathlen, equidist);
	fflush(stderr);
    }

    /* First original point is an equipoint. */
    equipoints[0] = points->pts[0];
    nequipoints++;
    dist_since_last_eqpt = 0;

    for (i = 1; i < points->npts; i++) {
	int dx1 = points->pts[i].x - points->pts[i-1].x;
	int dy1 = points->pts[i].y - points->pts[i-1].y;
	int endx = 100 * points->pts[i-1].x;
	int endy = 100 * points->pts[i-1].y;
	remaining_seglen = isqrt(10000 * (dx1 * dx1 + dy1 * dy1));
	dist_to_next_eqpt = equidist - dist_since_last_eqpt;

	while (remaining_seglen >= dist_to_next_eqpt) {
	    if (dx1 == 0) {
		/* x-coordinate stays the same */
		if (dy1 >= 0)
		    endy += dist_to_next_eqpt;
		else
		    endy -= dist_to_next_eqpt;
	    }
	    else {
		int slope = (100 * dy1 + dx1 / 2) / dx1;
		int tmp = isqrt(10000 + slope * slope);
		int dx = (100 * dist_to_next_eqpt + tmp / 2) / tmp;
		int dy = (slope * dx + 50) / 100;

		if (dy < 0) dy = -dy;
		if (dx1 >= 0)
		    endx += dx;
		else
		    endx -= dx;
		if (dy1 >= 0)
		    endy += dy;
		else
		    endy -= dy;
	    }

	    equipoints[nequipoints].x = (endx + 50) / 100;
	    equipoints[nequipoints].y = (endy + 50) / 100;
	    nequipoints++;
/*	    assert(nequipoints <= NCANONICAL);*/
	    dist_since_last_eqpt = 0;
	    remaining_seglen -= dist_to_next_eqpt;
	    dist_to_next_eqpt = equidist;
	}

	dist_since_last_eqpt += remaining_seglen;
    }

    /* Take care of last equipoint. */
    if (nequipoints == NCANONICAL) {
	/* Good. */
    } else if (nequipoints == (NCANONICAL - 1)) {
	/* Make last original point the last equipoint. */
	equipoints[nequipoints] = points->pts[points->npts - 1];
    } else {
      if (lidebug) {
        fprintf(stderr,"lialg_compute_equipoints: nequipoints = %d\n", 
		nequipoints);
      }
/*	assert(false);*/
	return(-1);
    }

    points->npts = NCANONICAL;
    delete_pen_point_array(points->pts);
    points->pts = equipoints;
    return(0);
}


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

  Utility routines

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

/* Result is x 100. */
static int lialg_compute_pathlen(point_list *points) {
    return(lialg_compute_pathlen_subset(points, 0, points->npts - 1));
}


/* Result is x 100. */
static int lialg_compute_pathlen_subset(point_list *points,
					   int start, int end) {
    int pathlen;
    int i;

    pathlen = 0;
    for (i = start + 1; i <= end; i++) {
	int dx = points->pts[i].x - points->pts[i-1].x;
	int dy = points->pts[i].y - points->pts[i-1].y;
	int dist = isqrt(10000 * (dx * dx + dy * dy));
	pathlen += dist;
    }

    return(pathlen);
}


/* Note that this does NOT update points->xrange and points->yrange! */
static int lialg_filter_points(point_list *points) {
    int filtered_npts;
    pen_point *filtered_pts = make_pen_point_array(points->npts);
    int i;

    if (filtered_pts == NULL) {
	error("can't allocate memory in lialg_filter_points");
	return(-1);
    }

    filtered_pts[0] = points->pts[0];
    filtered_npts = 1;
    for (i = 1; i < points->npts; i++) {
	int j = filtered_npts - 1;
	int dx = points->pts[i].x - filtered_pts[j].x;
	int dy = points->pts[i].y - filtered_pts[j].y;
	int magsq = dx * dx + dy * dy;

	if (magsq >= DIST_SQ_THRESHOLD) {
	    filtered_pts[filtered_npts] = points->pts[i];
	    filtered_npts++;
	}
    }

    points->npts = filtered_npts;
    delete_pen_point_array(points->pts);
    points->pts = filtered_pts;
    return(0);
}


/* scalex and scaley are x 100. */
/* Note that this does NOT update points->xrange and points->yrange! */
static int lialg_translate_points(point_list *points,
				   int minx, int miny,
				   int scalex, int scaley) {
    int i;

    for (i = 0; i < points->npts; i++) {
	points->pts[i].x = ((points->pts[i].x - minx) * scalex + 50) / 100;
	points->pts[i].y = ((points->pts[i].y - miny) * scaley + 50) / 100;
    }

    return(0);
}


static void lialg_get_bounding_box(point_list *points,
				    int *pminx, int *pminy,
				    int *pmaxx, int *pmaxy) {
    int minx, miny, maxx, maxy;
    int i;

    minx = maxx = points->pts[0].x;
    miny = maxy = points->pts[0].y;
    for (i = 1; i < points->npts; i++) {
	pen_point *pt = &(points->pts[i]);
	if (pt->x < minx) minx = pt->x;
	if (pt->x > maxx) maxx = pt->x;
	if (pt->y < miny) miny = pt->y;
	if (pt->y > maxy) maxy = pt->y;
    }

    *pminx = minx;
    *pminy = miny;
    *pmaxx = maxx;
    *pmaxy = maxy;
}

#ifdef __ECOS
float
expf(float x)
{
    return exp((double)x);
}
#endif


static void lialg_compute_lpf_parameters() {
    int i;

    for (i = LP_FILTER_WIDTH; i >= 0; i--) {
	float x = 0.04 * (i * i);
#if defined(ARM_LINUX) || !defined(__GLIBC__)
	double tmp = 100.0 * exp((double)x);
#else
	float tmp = 100.0 * expf(x);
#endif
	int wt = rint((double)tmp);

	lialg_lpfwts[LP_FILTER_WIDTH - i] = wt;
	lialg_lpfwts[LP_FILTER_WIDTH + i] = wt;
    }
    lialg_lpfconst = 0;
    for (i = 0; i < (2 * LP_FILTER_WIDTH + 1); i++) {
	lialg_lpfconst += lialg_lpfwts[i];
    }
}


/* Code from Joseph Hall ([e-mail]). */
static int isqrt(int n) {
    register int i;
    register long k0, k1, nn;

    for (nn = i = n, k0 = 2; i > 0; i >>= 2, k0 <<= 1)
	;
    nn <<= 2;
    for (;;) {
	k1 = (nn / k0 + k0) >> 1;
	if (((k0 ^ k1) & ~1) == 0)
	    break;
	k0 = k1;
    }
    return (int) ((k1 + 1) >> 1);
}


/* Helper routines