li_recognizer.c

神龙卡开发原代码

	{
	    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) {
			int mid = curr_reg->start + (curr_reg->end - curr_reg->start) / 2;
			int end = curr_reg->end;
			region_list *saved_next = curr_reg->next;

			curr_reg->end = mid - 1;
			if (prev_reg == NULL)
			    regions = curr_reg;
			else
			    prev_reg->next = curr_reg;
			prev_reg = curr_reg;

			/* curr_reg = (region_list *)safe_malloc(sizeof(region_list));*/
			curr_reg = allocate(1, region_list);
			curr_reg->start = mid;
			curr_reg->end = mid;
			curr_reg->type = RGN_PSEUDO;
			curr_reg->next = NULL;
			prev_reg->next = curr_reg;
			prev_reg = curr_reg;

			/* curr_reg = (region_list *)safe_malloc(sizeof(region_list)); */
			curr_reg = allocate(1, region_list);
			curr_reg->start = mid + 1;
			curr_reg->end = end;
			curr_reg->type = RGN_PLAIN;
			curr_reg->next = NULL;
			prev_reg->next = curr_reg;
			prev_reg = curr_reg;

			curr_reg->next = saved_next;
			continue;
		    }
		}

		if (prev_reg == NULL)
		    regions = curr_reg;
		else
		    prev_reg->next = curr_reg;
		prev_reg = curr_reg;
	    }
	}
    }

    free(junk);
    return(regions);
}


static point_list *lialg_compute_dompts(point_list *pts, region_list *regions) {
    point_list *dpts = NULL;
    int ndpts;
    int *cas = NULL;
    int nonplain;
    region_list *r;

    /* Compute contour angle set. */
    cas = lialg_compute_contour_angle_set(pts, regions);
/*    assert(cas != NULL);*/

    /* Dominant points include:  start_pt, end_pt, extrema_of_non_plain_regions, midpts of the preceding. */
    nonplain = 0;
    for (r = regions; r != NULL; r = r->next)
	if (r->type != RGN_PLAIN) nonplain++;
    ndpts = 2 * (2 + nonplain) - 1;
    /* dpts = (point_list *)safe_malloc(sizeof(point_list)); */
    dpts = allocate(1, point_list);
    dpts->pts = make_pen_point_array(ndpts);
    if (dpts->pts == NULL) {
	free(dpts);
	return(NULL);
    }
    dpts->npts = ndpts;
    dpts->next = NULL;

    /* Pick out dominant points. */
    {
	region_list *curr;
	int dp;
	int previx;
	int currix;

	/* Record start point. */
	dp = 0;
	previx = 0;
	dpts->pts[dp++] = pts->pts[previx];

	for (curr = regions; curr != NULL; curr = curr->next)
	    if (curr->type != RGN_PLAIN) {
		int max_v = 0;
		int min_v = MAXINT;
		int max_ix = -1;
		int min_ix = -1;
		int i;

		for (i = curr->start; i <= curr->end; i++) {
		    int v = cas[i];
		    if (v > max_v) { max_v = v; max_ix = i; }
		    if (v < min_v) { min_v = v; min_ix = i; }
		    if (lidebug > 1)
			fprintf(stderr, "  %d\n", v);
		}

		currix = (curr->type == RGN_CONVEX ? max_ix : min_ix);

		/* Record midpoint. */
		dpts->pts[dp++] = pts->pts[previx + (currix - previx) / 2];

		/* Record extreme point. */
		dpts->pts[dp++] = pts->pts[currix];

		previx = currix;
	    }

	/* Record last mid-point and end point. */
	currix = pts->npts - 1;
	dpts->pts[dp++] = pts->pts[previx + (currix - previx) / 2];
	dpts->pts[dp++] = pts->pts[currix];
    }

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

    free(cas);
    return(dpts);
}


static int *lialg_compute_contour_angle_set(point_list *pts,
					       region_list *regions) {
    int *V = NULL;
    region_list *curr_reg, *prev_reg;
    int i;

    /*    V = (int *)safe_malloc(pts->npts * sizeof(int));*/
    V = allocate(pts->npts, int);

    V[0] = 18000;
    for (curr_reg = regions; curr_reg != NULL;
	    prev_reg = curr_reg, curr_reg = curr_reg->next) {
	for (i = curr_reg->start; i <= curr_reg->end; i++) {
	    if (curr_reg->type == RGN_PLAIN) {
		V[i] = 18000;
	    }
	    else {
#ifdef	notdef
		/* XXX - eliminate floating point */
		region_list *next_reg = curr_reg->next;
		int b = curr_reg->start;
		int h = prev_reg->start;
		int t = next_reg->end;
		int pts_before = i - h;
		int pts_after = t - i;
		int min_pts = (pts_before < pts_after)
		  ? pts_before
		  : pts_after;
		int k = (min_pts < T_ONE)
		  ? T_ONE
		  : (min_pts > T_TWO)
		  ? T_TWO
		  : min_pts;
		float sum = 0.0;

		for (j = 1; j <= k; j++) {
		    int ptA = i - j;
		    int ptB = i + j - 1;
		    int d_A = pts->pts[ptA].chaincode;
		    int d_B = pts->pts[ptB].chaincode;
		    int a_i;

		    if (d_A < d_B)
			d_A += 8;

		    a_i = (d_A - d_B) % 8;

		    /* convert to radians */
		    if (a_i == 4 && curr_reg->type == RGN_CONVEX)
			sum += M_2_PI;
		    else
			sum += (float)((12 - a_i) % 8) / 4.0 * M_PI;
		}
		V[i] = sum / (float)k;
#else
		/* For now, simply choose the mid-point. */
		int isMidPt = (i == (curr_reg->start +
				     (curr_reg->end - curr_reg->start) / 2));
		V[i] = (curr_reg->type == RGN_CONVEX)
		  ? (isMidPt ? 18000 : 0)
		  : (isMidPt ? 0 : 18000);
#endif
	    }
	}
    }
    V[pts->npts - 1] = 18000;

    return(V);
}


/*
 *  First compute the similarity between the two strings.
 *  If it's above a threshold, compute the distance between
 *  the two and return it as the ``score.''
 *  Otherwise, return the constant WORST_SCORE.
 *
 */
static void lialg_score_stroke(point_list *input_dompts, point_list *curr_dompts, int *sim, int *dist) {
    *sim = MIN_SIM;
    *dist = MAX_DIST;

    *sim = lialg_compute_similarity(input_dompts, curr_dompts);
    if (*sim < SIM_THLD) goto done;

    *dist = lialg_compute_distance(input_dompts, curr_dompts);

done:
    if (lidebug)
	fprintf(stderr, "%d, %d\n", *sim, *dist);
}


static int lialg_compute_similarity(point_list *input_dompts,
				     point_list *curr_dompts) {
    int sim = 0;
    point_list *A, *B;
    int N, M;
    int **G = NULL;
    int *junk = NULL;
    int i, j;

    /* A is the	longer sequence, length	N. */
    /* B is the shorter sequence, length M. */
    if (input_dompts->npts >= curr_dompts->npts) {
	A = input_dompts;
	N = input_dompts->npts;
	B = curr_dompts;
	M = curr_dompts->npts;
    }
    else {
	A = curr_dompts;
	N = curr_dompts->npts;
	B = input_dompts;
	M = input_dompts->npts;
    }

    /* Allocate and initialize the Gain matrix, G. */
    /* The size of G is M x (N + 1). */
    /* Note that row 0 is unused. */
    /* Similarities are x 10. */
    {
        /*	G = (int **)safe_malloc(M * sizeof(int *));*/
        G = allocate(M, int *);
        /*	junk = (int *)safe_malloc(M * (N + 1) * sizeof(int)); */
	junk = allocate(M * (N + 1), int);
	for (i = 0; i < M; i++)
	    G[i] = junk + (i * (N + 1));

	for (i = 1; i < M; i++) {
	    int bval = B->pts[i-1].chaincode;

	    /* Source column. */
	    G[i][0] = 0;

	    for (j = 1; j < N; j++) {
		int aval = A->pts[j-1].chaincode;
		int diff = abs(bval - aval);
		if (diff > 4) diff = 8 - diff;

		G[i][j] = (diff == 0)
		  ? 10
		  : (diff == 1)
		  ? 6
		  : 0;
	    }

	    /* Sink column. */
	    G[i][N] = 0;
	}
    }

    /* Do the DP algorithm. */
    /* Proceed in column order, from highest column to the lowest. */
    /* Within each column, proceed from the highest row to the lowest. */
    /* Skip the highest column. */
    {
	for (j = N - 1; j >= 0; j--)
	    for (i = M - 1; i > 0; i--) {
		int max = G[i][j + 1];

		if (i < (M - 1)) {
		    int tmp = G[i + 1][j + 1];
		    if (tmp > max) max = tmp;
		}

		G[i][j] += max;
	    }

	sim = (10 * G[1][0] + (N - 1) / 2) / (N - 1);
    }

    if (G != NULL) free(G);
    if (junk != NULL) free(junk);
    return(sim);
}


static int lialg_compute_distance(point_list *input_dompts,
				   point_list *curr_dompts) {
    int dist = MAX_DIST;
    point_list *A, *B;
    int N, M;
    int **C = NULL;
    int *junk = NULL;
    int *BE = NULL;
    int *TE = NULL;
    int i, j;

    /* A is the	longer sequence, length	N. */
    /* B is the shorter sequence, length M. */
    if (input_dompts->npts >= curr_dompts->npts) {
	A = input_dompts;
	N = input_dompts->npts;
	B = curr_dompts;
	M = curr_dompts->npts;
    }
    else {
	A = curr_dompts;
	N = curr_dompts->npts;
	B = input_dompts;
	M = input_dompts->npts;
    }

    /* Construct the helper vectors, BE and TE, which say for each column */
    /* what are the ``bottom'' and ``top'' rows of interest. */
    {
        /*	BE = (int *)safe_malloc((N + 1) * sizeof(int));*/
	BE = allocate((N + 1), int);
	/*	TE = (int *)safe_malloc((N + 1) * sizeof(int)); */
	TE = allocate((N + 1), int);

	for (j = 1; j <= N; j++) {
	    int bot, top;

	    bot = j + (M - DP_BAND);
	    if (bot > M) bot = M;
	    BE[j] = bot;

	    top = j - (N - DP_BAND);
	    if (top < 1) top = 1;
	    TE[j] = top;
	}
    }

    /* Allocate and initialize the Cost matrix, C. */
    /* The size of C is (M + 1) x (N + 1). */
    /* Note that row and column 0 are unused. */
    /* Costs are x 100. */
    {
        /*	C = (int **)safe_malloc((M + 1) * sizeof(int *)); */
	C = allocate((M + 1), int *);
	/*	junk = (int *)safe_malloc((M + 1) * (N + 1) * sizeof(int)); */
	junk = allocate((M + 1) * (N + 1), int);
	for (i = 0; i <= M; i++)
	    C[i] = junk + (i * (N + 1));

	for (i = 1; i <= M; i++) {
	    int bx = B->pts[i-1].x;
	    int by = B->pts[i-1].y;

	    for (j = 1; j <= N; j++) {
		int ax = A->pts[j-1].x;
		int ay = A->pts[j-1].y;
		int dx = bx - ax;
		int dy = by - ay;
		int dist = isqrt(10000 * (dx * dx + dy * dy));

		C[i][j] = dist;
	    }
	}
    }

    /* Do the DP algorithm. */
    /* Proceed in column order, from highest column to the lowest. */
    /* Within each column, proceed from the highest row to the lowest. */
    {
	for (j = N; j > 0; j--)
	    for (i = M; i > 0; i--) {
		int min = MAX_DIST;

		if (i > BE[j] || i < TE[j] || (j == N && i == M))
		    continue;

		if (j < N) {
		    if (i >= TE[j+1]) {
			int tmp = C[i][j+1];
			if (tmp < min) min = tmp;
		    }

		    if (i < M) {
			int tmp = C[i+1][j+1];
			if (tmp < min) min = tmp;
		    }
		}

		if (i < BE[j]) {
		    int tmp = C[i+1][j];
		    if (tmp < min) min = tmp;
		}

		C[i][j] += min;
	    }

	dist = (C[1][1] + N / 2) / N;
    }

    if (C != NULL) free(C);
    if (junk != NULL) free(junk);
    if (BE != NULL) free(BE);
    if (TE != NULL) free(TE);
    return(dist);
}


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

  Digest-processing routines

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

static int lialg_read_classifier_digest(rClassifier *rec) {
    int nclasses;
    FILE *fp = NULL;

    /* Try to open the corresponding digest file. */
    {
	char *clx_path;
	char *dot;

	/* Get a copy of the filename, with some room on the end. */
	/*	clx_path = safe_malloc(strlen(rec->file_name) + 5); */
	clx_path = allocate(strlen(rec->file_name) + 5, char);
	strcpy(clx_path, rec->file_name);

	/* Truncate the path after the last dot. */
	dot = strrchr(clx_path, '.');
	if (dot == NULL) { free(clx_path); return(-1); }
	*(dot + 1) = 0;

	/* Append the classifier-digest extension. */
	strcat(clx_path, "clx");

	fp = fopen(clx_path, "r");
	if (fp == NULL) { free(clx_path); return(-1); }

	free(clx_path);
    }

    /* Read-in the name and dominant points for each class. */
    for (nclasses = 0; !feof(fp); nclasses++) {
	point_list *dpts = NULL;
	char class[BUFSIZ];
	int npts;
	int j;

	if (fscanf(fp, "%s %d", class, &npts) != 2) {
	    if (feof(fp)) break;

	    goto failed;
	}
	rec->cnames[nclasses] = strdup(class);

	/* Allocate a dominant-points list. */
	/* dpts = (point_list *)safe_malloc(sizeof(point_list)); */
	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;