ref: 8a788aea84aad3bfbd5b39d78c1925654f3b9e14
dir: /appl/lib/strokes/strokes.b/
implement Strokes;
#
# this Limbo code is derived from C code that had the following
# copyright notice, which i reproduce as requested
#
# li_recognizer.c
#
# Copyright 2000 Compaq Computer Corporation.
# Copying or modifying this code for any purpose is permitted,
# provided that this copyright notice is preserved in its entirety
# in all copies or modifications.
# COMPAQ COMPUTER CORPORATION MAKES NO WARRANTIES, EXPRESSED OR
# IMPLIED, AS TO THE USEFULNESS OR CORRECTNESS OF THIS CODE OR
#
#
# Adapted from cmu_recognizer.c by Jay Kistler.
#
# Where is the CMU copyright???? Gotta track it down - Jim Gettys
#
# Credit to Dean Rubine, Jim Kempf, and Ari Rapkin.
#
#
# the copyright notice really did end in the middle of the sentence
#
#
# Limbo version for Inferno by forsyth@vitanuova.com, Vita Nuova, September 2001
#
#
# the code is reasonably close to the algorithms described in
# ``On-line Handwritten Alphanumeric Character Recognition Using Dominant Stroke in Strokes'',
# Xiaolin Li and Dit-Yan Yueng, Department of Computer Science,
# Hong Kong University of Science and Technology, Hong Kong (23 August 1996)
#
include "sys.m";
sys: Sys;
include "strokes.m";
MAXINT: con 16r7FFFFFFF;
# Dynamic programming parameters
DP_BAND: con 3;
SIM_THLD: con 60; # x100
#DIST_THLD: con 3200; # x100
DIST_THLD: con 3300; # x100
# Low-pass filter parameters -- empirically derived
LP_FILTER_WIDTH: con 6;
LP_FILTER_ITERS: con 8;
LP_FILTER_THLD: con 250; # x100
LP_FILTER_MIN: con 5;
# Pseudo-extrema parameters -- empirically derived
PE_AL_THLD: con 1500; # x100
PE_ATCR_THLD: con 135; # x100
# Pre-processing and canonicalization parameters
CANONICAL_X: con 108;
CANONICAL_Y: con 128;
DIST_SQ_THRESHOLD: con 3*3;
# direction-code table; indexed by dx, dy
dctbl := array[] of {array[] of {1, 0, 7}, array[] of {2, MAXINT, 6}, array[] of {3, 4, 5}};
# low-pass filter weights
lpfwts := array[2 * LP_FILTER_WIDTH + 1] of int;
lpfconst := -1;
lidebug: con 0;
stderr: ref Sys->FD;
# x := 0.04 * (i * i);
# wtvals[i] = floor(100.0 * exp(x));
wtvals := array[] of {100, 104, 117, 143, 189, 271, 422};
init()
{
sys = load Sys Sys->PATH;
if(lidebug)
stderr = sys->fildes(2);
for(i := LP_FILTER_WIDTH; i >= 0; i--){
wt := wtvals[i];
lpfwts[LP_FILTER_WIDTH - i] = wt;
lpfwts[LP_FILTER_WIDTH + i] = wt;
}
lpfconst = 0;
for(i = 0; i < (2 * LP_FILTER_WIDTH + 1); i++)
lpfconst += lpfwts[i];
}
Stroke.new(n: int): ref Stroke
{
return ref Stroke(n, array[n] of Penpoint, 0, 0);
}
Stroke.trim(ps: self ref Stroke, n: int)
{
ps.npts = n;
ps.pts = ps.pts[0:n];
}
Stroke.copy(ps: self ref Stroke): ref Stroke
{
n := ps.npts;
a := array[n] of Penpoint;
a[0:] = ps.pts[0:n];
return ref Stroke(n, a, ps.xrange, ps.yrange);
}
#
# return the bounding box of a set of points
# (note: unlike Draw->Rectangle, the region is closed)
#
Stroke.bbox(ps: self ref Stroke): (int, int, int, int)
{
minx := maxx := ps.pts[0].x;
miny := maxy := ps.pts[0].y;
for(i := 1; i < ps.npts; i++){
pt := ps.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;
}
return (minx, miny, maxx, maxy); # warning: closed interval
}
Stroke.center(ps: self ref Stroke)
{
(minx, miny, maxx, maxy) := ps.bbox();
ps.xrange = maxx-minx;
ps.yrange = maxy-miny;
avgxoff := -((CANONICAL_X - ps.xrange + 1) / 2);
avgyoff := -((CANONICAL_Y - ps.yrange + 1) / 2);
ps.translate(avgxoff, avgyoff, 100, 100);
}
Stroke.scaleup(ps: self ref Stroke): int
{
(minx, miny, maxx, maxy) := ps.bbox();
xrange := maxx - minx;
yrange := maxy - miny;
scale: int;
if(((100 * xrange + CANONICAL_X / 2) / CANONICAL_X) >
((100 * yrange + CANONICAL_Y / 2) / CANONICAL_Y))
scale = (100 * CANONICAL_X + xrange / 2) / xrange;
else
scale = (100 * CANONICAL_Y + yrange / 2) / yrange;
ps.translate(minx, miny, scale, scale);
return scale;
}
# scalex and scaley are x 100.
# Note that this does NOT update points.xrange and points.yrange!
Stroke.translate(ps: self ref Stroke, minx: int, miny: int, scalex: int, scaley: int)
{
for(i := 0; i < ps.npts; i++){
ps.pts[i].x = ((ps.pts[i].x - minx) * scalex + 50) / 100;
ps.pts[i].y = ((ps.pts[i].y - miny) * scaley + 50) / 100;
}
}
TAP_PATHLEN: con 10*100; # x100
Classifier.match(rec: self ref Classifier, stroke: ref Stroke): (int, string)
{
if(stroke.npts < 1)
return (-1, nil);
# Check for tap.
# First thing is to filter out ``close points.''
stroke = stroke.filter();
# 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 || stroke.length() < TAP_PATHLEN)
return (-1, "tap");
preprocess_stroke(stroke);
# Compute its dominant points.
dompts := stroke.interpolate().dominant();
best_dist := MAXDIST;
best_i := -1;
best_name: string;
# Score input stroke against every class in classifier.
for(i := 0; i < len rec.cnames; i++){
name := rec.cnames[i];
(sim, dist) := score_stroke(dompts, rec.dompts[i]);
if(dist < MAXDIST)
sys->fprint(stderr, " (%s, %d, %d)", name, sim, dist);
if(dist < DIST_THLD){
if(lidebug)
sys->fprint(stderr, " (%s, %d, %d)", name, sim, dist);
# Is it the best so far?
if(dist < best_dist){
best_dist = dist;
best_i = i;
best_name = name;
}
}
}
if(lidebug)
sys->fprint(stderr, "\n");
return (best_i, best_name);
}
preprocess_stroke(s: ref Stroke)
{
# Filter out points that are too close.
# We did this earlier, when we checked for a tap.
# s = s.filter();
# assert(s.npts > 0);
# Scale up to avoid conversion errors.
s.scaleup();
# Center the stroke.
s.center();
if(lidebug){
(minx, miny, maxx, maxy) := s.bbox();
sys->fprint(stderr, "After pre-processing: [ %d %d %d %d]\n",
minx, miny, maxx, maxy);
printpoints(stderr, s, "\n");
}
}
#
# return the dominant points of Stroke s, assuming s has been through interpolation
#
Stroke.dominant(s: self ref Stroke): ref Stroke
{
regions := s.regions();
# Dominant points are: start, end, extrema of non plain regions, and midpoints of the preceding.
nonplain := 0;
for(r := regions; r != nil; r = r.next)
if(r.rtype != Rplain)
nonplain++;
dom := Stroke.new(1 + 2*nonplain + 2);
# Pick out dominant points.
# start point
dp := 0;
previx := 0;
dom.pts[dp++] = s.pts[previx];
currix: int;
cas := s.contourangles(regions);
for(r = regions; r != nil; r = r.next)
if(r.rtype != Rplain){
max_v := 0;
min_v := MAXINT;
max_ix := -1;
min_ix := -1;
for(i := r.start; i <= r.end; i++){
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)
sys->fprint(stderr, " %d\n", v);
}
if(r.rtype == Rconvex)
currix = max_ix;
else
currix = min_ix;
dom.pts[dp++] = s.pts[(previx+currix)/2]; # midpoint
dom.pts[dp++] = s.pts[currix]; # extreme
previx = currix;
}
# last midpoint, and end point
lastp := s.npts - 1;
dom.pts[dp++] = s.pts[(previx+lastp)/2];
dom.pts[dp++] = s.pts[lastp];
dom.trim(dp);
# Compute chain-code.
compute_chain_code(dom);
return dom;
}
Stroke.contourangles(s: self ref Stroke, regions: ref Region): array of int
{
V := array[s.npts] of int;
V[0] = 18000;
for(r := regions; r != nil; r = r.next){
for(i := r.start; i <= r.end; i++){
if(r.rtype == Rplain){
V[i] = 18000;
}else{
# For now, simply choose the mid-point.
ismidpt := i == (r.start + r.end)/2;
if(ismidpt ^ (r.rtype!=Rconvex))
V[i] = 18000;
else
V[i] = 0;
}
}
}
V[s.npts - 1] = 18000;
return V;
}
Stroke.interpolate(s: self ref Stroke): ref Stroke
{
# Compute an upper-bound on the number of interpolated points
maxpts := s.npts;
for(i := 0; i < s.npts - 1; i++){
a := s.pts[i];
b := s.pts[i+1];
maxpts += abs(a.x - b.x) + abs(a.y - b.y);
}
# Allocate an array of the maximum size
newpts := Stroke.new(maxpts);
# Interpolate each of the segments.
j := 0;
for(i = 0; i < s.npts - 1; i++){
j = bresline(s.pts[i], s.pts[i+1], newpts, j);
j--; # end point gets recorded as start point of next segment!
}
# Add-in last point and trim
newpts.pts[j++] = s.pts[s.npts - 1];
newpts.trim(j);
if(lidebug){
sys->fprint(stderr, "After interpolation:\n");
printpoints(stderr, newpts, "\n");
}
# Compute the chain code for P (the list of points).
compute_unit_chain_code(newpts);
return newpts;
}
# This implementation is due to an anonymous page on the net
bresline(startpt: Penpoint, endpt: Penpoint, newpts: ref Stroke, j: int): int
{
x0 := startpt.x;
x1 := endpt.x;
y0 := startpt.y;
y1 := endpt.y;
stepx := 1;
dx := x1-x0;
if(dx < 0){
dx = -dx;
stepx = -1;
}
dx <<= 1;
stepy := 1;
dy := y1-y0;
if(dy < 0){
dy = -dy;
stepy = -1;
}
dy <<= 1;
newpts.pts[j++] = (x0, y0, 0);
if(dx >= dy){
e := dy - (dx>>1);
while(x0 != x1){
if(e >= 0){
y0 += stepy;
e -= dx;
}
x0 += stepx;
e += dy;
newpts.pts[j++] = (x0, y0, 0);
}
}else{
e := dx - (dy>>1);
while(y0 != y1){
if(e >= 0){
x0 += stepx;
e -= dy;
}
y0 += stepy;
e += dx;
newpts.pts[j++] = (x0, y0, 0);
}
}
return j;
}
compute_chain_code(pts: ref Stroke)
{
for(i := 0; i < pts.npts - 1; i++){
dx := pts.pts[i+1].x - pts.pts[i].x;
dy := pts.pts[i+1].y - pts.pts[i].y;
pts.pts[i].chaincode = (12 - quadr(likeatan(dy, dx))) % 8;
}
}
compute_unit_chain_code(pts: ref Stroke)
{
for(i := 0; i < pts.npts - 1; i++){
dx := pts.pts[i+1].x - pts.pts[i].x;
dy := pts.pts[i+1].y - pts.pts[i].y;
pts.pts[i].chaincode = dctbl[dx+1][dy+1];
}
}
Stroke.regions(pts: self ref Stroke): ref Region
{
# Allocate a 2 x pts.npts array for use in computing the (filtered) Angle set, A_n.
R := array[] of {0 to LP_FILTER_ITERS+1 => array[pts.npts] of int};
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++){
d_i := pts.pts[i].chaincode;
d_iminusone := pts.pts[i-1].chaincode;
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; ){
for(i = 0; i < pts.npts; i++){
next[i] = 0;
for(k := i - LP_FILTER_WIDTH; k <= i + LP_FILTER_WIDTH; k++){
oldval: int;
if(k < 0 || k >= pts.npts)
oldval = 18000;
else
oldval = curr[k];
next[i] += oldval * lpfwts[k - (i - LP_FILTER_WIDTH)]; # overflow?
}
next[i] /= lpfconst;
}
j++;
curr = R[j];
next = R[j+1];
}
# Do final thresholding around PI.
# curr and next are set-up correctly at end of previous loop!
for(i = 0; i < pts.npts; i++)
if(abs(curr[i] - 18000) < LP_FILTER_THLD)
next[i] = 18000;
else
next[i] = curr[i];
curr = next;
# Debugging.
if(lidebug > 1){
for(i = 0; i < pts.npts; i++){
p := pts.pts[i];
sys->fprint(stderr, "%3d: (%d %d) %ud ",
i, p.x, p.y, p.chaincode);
for(j = 0; j < 2 + LP_FILTER_ITERS; j++)
sys->fprint(stderr, "%d ", R[j][i]);
sys->fprint(stderr, "\n");
}
}
# Do the region segmentation.
r := regions := ref Region(regiontype(curr[0]), 0, 0, nil);
for(i = 1; i < pts.npts; i++){
t := regiontype(curr[i]);
if(t != r.rtype){
r.end = i-1;
if(lidebug > 1)
sys->fprint(stderr, " (%d, %d) %d\n", r.start, r.end, r.rtype);
r.next = ref Region(t, i, 0, nil);
r = r.next;
}
}
r.end = i-1;
if(lidebug > 1)
sys->fprint(stderr, " (%d, %d), %d\n", r.start, r.end, r.rtype);
# Filter out convex/concave regions that are too short.
for(r = regions; r != nil; r = r.next)
if(r.rtype == Rplain){
while((nr := r.next) != nil && (nr.end - nr.start) < LP_FILTER_MIN){
# nr must not be plain, and it must be followed by a plain
# assert(nr.rtype != Rplain);
# assert(nr.next != nil && (nr.next).rtype == Rplain);
if(nr.next == nil){
sys->fprint(stderr, "recog: nr.next==nil\n"); # can't happen
break;
}
r.next = nr.next.next;
r.end = nr.next.end;
}
}
# Add-in pseudo-extremes.
for(r = regions; r != nil; r = r.next)
if(r.rtype == Rplain){
arclen := pts.pathlen(r.start, r.end);
dx := pts.pts[r.end].x - pts.pts[r.start].x;
dy := pts.pts[r.end].y - pts.pts[r.start].y;
chordlen := sqrt(100*100 * (dx*dx + dy*dy));
atcr := 0;
if(chordlen)
atcr = (100*arclen + chordlen/2) / chordlen;
if(lidebug)
sys->fprint(stderr, "%d, %d, %d\n", arclen, chordlen, atcr);
# Split region if necessary.
if(arclen >= PE_AL_THLD && atcr >= PE_ATCR_THLD){
mid := (r.start + r.end)/2;
end := r.end;
r.end = mid - 1;
r = r.next = ref Region(Rpseudo, mid, mid,
ref Region(Rplain, mid+1, end, r.next));
}
}
return regions;
}
regiontype(val: int): int
{
if(val == 18000)
return Rplain;
if(val < 18000)
return Rconcave;
return Rconvex;
}
#
# return the similarity of two strokes and,
# if similar, the distance between them;
# if dissimilar, the distance is MAXDIST)
#
score_stroke(a: ref Stroke, b: ref Stroke): (int, int)
{
sim := compute_similarity(a, b);
if(sim < SIM_THLD)
return (sim, MAXDIST);
return (sim, compute_distance(a, b));
}
compute_similarity(A: ref Stroke, B: ref Stroke): int
{
# A is the longer sequence, length N.
# B is the shorter sequence, length M.
if(A.npts < B.npts){
t := A; A = B; B = t;
}
N := A.npts;
M := B.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 := array[M] of array of int;
for(i := 1; i < M; i++){
G[i] = array[N+1] of int;
bcode := B.pts[i-1].chaincode;
G[i][0] = 0; # source column
for(j := 1; j < N; j++){
diff := abs(bcode - A.pts[j-1].chaincode);
if(diff > 4)
diff = 8 - diff; # symmetry
v := 0;
if(diff == 0)
v = 10;
else if(diff == 1)
v = 6;
G[i][j] = v;
}
G[i][N] = 0; # sink column
}
# 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--){
max := G[i][j + 1];
if(i < M-1){
t := G[i + 1][j + 1];
if(t > max)
max = t;
}
G[i][j] += max;
}
return (10*G[1][0] + (N-1)/2) / (N-1);
}
compute_distance(A: ref Stroke, B: ref Stroke): int
{
# A is the longer sequence, length N.
# B is the shorter sequence, length M.
if(A.npts < B.npts){
t := A; A = B; B = t;
}
N := A.npts;
M := B.npts;
# Construct the helper vectors, BE and TE, which say for each column
# what are the ``bottom'' and ``top'' rows of interest.
BE := array[N+1] of int;
TE := array[N+1] of int;
for(j := 1; j <= N; j++){
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 := array[M+1] of array of int;
for(i := 1; i <= M; i++){
C[i] = array[N+1] of int;
bx := B.pts[i-1].x;
by := B.pts[i-1].y;
for(j = 1; j <= N; j++){
ax := A.pts[j-1].x;
ay := A.pts[j-1].y;
dx := bx - ax;
dy := by - ay;
dist := sqrt(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--){
min := MAXDIST;
if(i > BE[j] || i < TE[j] || (j == N && i == M))
continue;
if(j < N){
if(i >= TE[j+1]){
tmp := C[i][j+1];
if(tmp < min)
min = tmp;
}
if(i < M){
tmp := C[i+1][j+1];
if(tmp < min)
min = tmp;
}
}
if(i < BE[j]){
tmp := C[i+1][j];
if(tmp < min)
min = tmp;
}
C[i][j] += min;
}
return (C[1][1] + N / 2) / N; # dist
}
# Result is x 100.
Stroke.length(s: self ref Stroke): int
{
return s.pathlen(0, s.npts-1);
}
# Result is x 100.
Stroke.pathlen(s: self ref Stroke, first: int, last: int): int
{
l := 0;
for(i := first + 1; i <= last; i++){
dx := s.pts[i].x - s.pts[i-1].x;
dy := s.pts[i].y - s.pts[i-1].y;
l += sqrt(100*100 * (dx*dx + dy*dy));
}
return l;
}
# Note that this does NOT update points.xrange and points.yrange!
Stroke.filter(s: self ref Stroke): ref Stroke
{
pts := array[s.npts] of Penpoint;
pts[0] = s.pts[0];
npts := 1;
for(i := 1; i < s.npts; i++){
j := npts - 1;
dx := s.pts[i].x - pts[j].x;
dy := s.pts[i].y - pts[j].y;
magsq := dx * dx + dy * dy;
if(magsq >= DIST_SQ_THRESHOLD){
pts[npts] = s.pts[i];
npts++;
}
}
return ref Stroke(npts, pts[0:npts], 0, 0);
}
abs(a: int): int
{
if(a < 0)
return -a;
return a;
}
# Code from Joseph Hall (jnhall@sat.mot.com).
sqrt(n: int): int
{
nn := n;
k0 := 2;
for(i := n; i > 0; i >>= 2)
k0 <<= 1;
nn <<= 2;
k1: int;
for(;;){
k1 = (nn / k0 + k0) >> 1;
if(((k0 ^ k1) & ~1) == 0)
break;
k0 = k1;
}
return (k1 + 1) >> 1;
}
# Helper routines from Mark Hayter.
likeatan(tantop: int, tanbot: int): int
{
# Use tan(theta)=top/bot -. order for t
# t in range 0..16r40000
if(tantop == 0 && tantop == 0)
return 0;
t := (tantop << 16) / (abs(tantop) + abs(tanbot));
if(tanbot < 0)
t = 16r20000 - t;
else if(tantop < 0)
t = 16r40000 + t;
return t;
}
quadr(t: int): int
{
return (8 - (((t + 16r4000) >> 15) & 7)) & 7;
}
printpoints(fd: ref Sys->FD, pts: ref Stroke, sep: string)
{
for(j := 0; j < pts.npts; j++){
p := pts.pts[j];
sys->fprint(fd, " (%d %d) %ud%s", p.x, p.y, pts.pts[j].chaincode, sep);
}
}