1implement Buildstrokes; 2 3# 4# this Limbo code is derived from C code that had the following 5# copyright notice, which i reproduce as requested 6# 7# li_strokesnizer.c 8# 9# Copyright 2000 Compaq Computer Corporation. 10# Copying or modifying this code for any purpose is permitted, 11# provided that this copyright notice is preserved in its entirety 12# in all copies or modifications. 13# COMPAQ COMPUTER CORPORATION MAKES NO WARRANTIES, EXPRESSED OR 14# IMPLIED, AS TO THE USEFULNESS OR CORRECTNESS OF THIS CODE OR 15# 16# 17# Adapted from cmu_strokesnizer.c by Jay Kistler. 18# 19# Where is the CMU copyright???? Gotta track it down - Jim Gettys 20# 21# Credit to Dean Rubine, Jim Kempf, and Ari Rapkin. 22# 23 24include "sys.m"; 25 sys: Sys; 26 27include "strokes.m"; 28 strokes: Strokes; 29 Classifier, Penpoint, Stroke, Region: import strokes; 30 Rconvex, Rconcave, Rplain, Rpseudo: import Strokes; 31 32lidebug: con 0; 33stderr: ref Sys->FD; 34 35init(r: Strokes) 36{ 37 sys = load Sys Sys->PATH; 38 if(lidebug) 39 stderr = sys->fildes(2); 40 strokes = r; 41} 42 43# 44# Implementation of the Li/Yeung recognition algorithm 45# 46 47# Pre-processing and canonicalization parameters 48CANONICAL_X: con 108; 49CANONICAL_Y: con 128; 50NCANONICAL: con 50; 51 52 53# 54# calculate canonical forms 55# 56 57canonical_example(nclasses: int, cnames: array of string, examples: array of list of ref Stroke): (string, array of ref Stroke, array of ref Stroke) 58{ 59 canonex := array[nclasses] of ref Stroke; 60 dompts := array[nclasses] of ref Stroke; 61 62 # make canonical examples for each class. 63 for(i := 0; i < nclasses; i++){ 64 if(lidebug) 65 sys->fprint(stderr, "canonical_example: class %s\n", cnames[i]); 66 67 # Make a copy of the examples. 68 pts: list of ref Stroke = nil; 69 nex := 0; 70 for(exl := examples[i]; exl != nil; exl = tl exl){ 71 t := hd exl; 72 pts = t.copy() :: pts; 73 nex++; 74 } 75 76 # Canonicalize each example, and derive the max x and y ranges. 77 maxxrange := 0; 78 maxyrange := 0; 79 for(exl = pts; exl != nil; exl = tl exl){ 80 e := hd exl; 81 ce := canonical_stroke(e); 82 if(ce == nil){ 83 if(lidebug) 84 sys->fprint(stderr, "example discarded: can't make canonical form\n"); 85 continue; # try the next one 86 } 87 *e = *ce; 88 if(e.xrange > maxxrange) 89 maxxrange = e.xrange; 90 if(e.yrange > maxyrange) 91 maxyrange = e.yrange; 92 } 93 94 # Normalise max ranges. 95 (maxxrange, maxyrange) = normalise(maxxrange, maxyrange, CANONICAL_X, CANONICAL_Y); 96 97 # Re-scale each example to max ranges. 98 for(exl = pts; exl != nil; exl = tl exl){ 99 t := hd exl; 100 scalex, scaley: int; 101 if(t.xrange == 0) 102 scalex = 100; 103 else 104 scalex = (100*maxxrange + t.xrange/2) / t.xrange; 105 if(t.yrange == 0) 106 scaley = 100; 107 else 108 scaley = (100*maxyrange + t.yrange/2) / t.yrange; 109 t.translate(0, 0, scalex, scaley); 110 } 111 112 # Average the examples; leave average in first example. 113 avg := hd pts; # careful, aliasing 114 for(k := 0; k < NCANONICAL; k++){ 115 xsum := 0; 116 ysum := 0; 117 for(exl = pts; exl != nil; exl = tl exl){ 118 t := hd exl; 119 xsum += t.pts[k].x; 120 ysum += t.pts[k].y; 121 } 122 avg.pts[k].x = (xsum + nex/2) / nex; 123 avg.pts[k].y = (ysum + nex/2) / nex; 124 } 125 126 # rescale averaged stroke 127 avg.scaleup(); 128 129 # Re-compute the x and y ranges and center the stroke. 130 avg.center(); 131 132 canonex[i] = avg; # now it's the canonical representation 133 134 if(lidebug){ 135 sys->fprint(stderr, "%s, avgpts = %d\n", cnames[i], avg.npts); 136 for(j := 0; j < avg.npts; j++){ 137 p := avg.pts[j]; 138 sys->fprint(stderr, " (%d %d)\n", p.x, p.y); 139 } 140 } 141 142 dompts[i] = avg.interpolate().dominant(); # dominant points of canonical representation 143 } 144 145 return (nil, canonex, dompts); 146} 147 148normalise(x, y: int, xrange, yrange: int): (int, int) 149{ 150 if((100*x + xrange/2)/xrange > (100*y + yrange/2)/yrange){ 151 y = (y*xrange + x/2)/x; 152 x = xrange; 153 }else{ 154 x = (x*yrange + y/2)/y; 155 y = yrange; 156 } 157 return (x, y); 158} 159 160canonical_stroke(points: ref Stroke): ref Stroke 161{ 162 points = points.filter(); 163 if(points.npts < 2) 164 return nil; 165 166 # Scale up to avoid conversion errors. 167 points.scaleup(); 168 169 # Compute an equivalent stroke with equi-distant points 170 points = compute_equipoints(points); 171 if(points == nil) 172 return nil; 173 174 # Re-translate the points to the origin. 175 (minx, miny, maxx, maxy) := points.bbox(); 176 points.translate(minx, miny, 100, 100); 177 178 # Store the x and y ranges in the point list. 179 points.xrange = maxx - minx; 180 points.yrange = maxy - miny; 181 182 if(lidebug){ 183 sys->fprint(stderr, "Canonical stroke: %d, %d, %d, %d\n", minx, miny, maxx, maxy); 184 for(i := 0; i < points.npts; i++){ 185 p := points.pts[i]; 186 sys->fprint(stderr, " (%d %d)\n", p.x, p.y); 187 } 188 } 189 190 return points; 191} 192 193compute_equipoints(points: ref Stroke): ref Stroke 194{ 195 pathlen := points.length(); 196 equidist := (pathlen + (NCANONICAL-1)/2) / (NCANONICAL-1); 197 equipoints := array[NCANONICAL] of Penpoint; 198 if(lidebug) 199 sys->fprint(stderr, "compute_equipoints: npts = %d, pathlen = %d, equidist = %d\n", 200 points.npts, pathlen, equidist); 201 202 # First original point is an equipoint. 203 equipoints[0] = points.pts[0]; 204 nequipoints := 1; 205 dist_since_last_eqpt := 0; 206 207 for(i := 1; i < points.npts; i++){ 208 dx1 := points.pts[i].x - points.pts[i-1].x; 209 dy1 := points.pts[i].y - points.pts[i-1].y; 210 endx := points.pts[i-1].x*100; 211 endy := points.pts[i-1].y*100; 212 remaining_seglen := strokes->sqrt(100*100 * (dx1*dx1 + dy1*dy1)); 213 dist_to_next_eqpt := equidist - dist_since_last_eqpt; 214 while(remaining_seglen >= dist_to_next_eqpt){ 215 if(dx1 == 0){ 216 # x-coordinate stays the same 217 if(dy1 >= 0) 218 endy += dist_to_next_eqpt; 219 else 220 endy -= dist_to_next_eqpt; 221 }else{ 222 slope := (100*dy1 + dx1/2) / dx1; 223 tmp := strokes->sqrt(100*100 + slope*slope); 224 dx := (100*dist_to_next_eqpt + tmp/2) / tmp; 225 dy := (slope*dx + 50)/100; 226 if(dy < 0) 227 dy = -dy; 228 if(dx1 >= 0) 229 endx += dx; 230 else 231 endx -= dx; 232 if(dy1 >= 0) 233 endy += dy; 234 else 235 endy -= dy; 236 } 237 equipoints[nequipoints].x = (endx + 50) / 100; 238 equipoints[nequipoints].y = (endy + 50) / 100; 239 nequipoints++; 240 #assert(nequipoints <= NCANONICAL); 241 dist_since_last_eqpt = 0; 242 remaining_seglen -= dist_to_next_eqpt; 243 dist_to_next_eqpt = equidist; 244 } 245 dist_since_last_eqpt += remaining_seglen; 246 } 247 248 # Take care of last equipoint. 249 if(nequipoints == NCANONICAL-1){ 250 # Make last original point the last equipoint. 251 equipoints[nequipoints++] = points.pts[points.npts - 1]; 252 } 253 if(nequipoints != NCANONICAL){ # fell short 254 if(lidebug) 255 sys->fprint(stderr,"compute_equipoints: nequipoints = %d\n", nequipoints); 256 # assert(false); 257 return nil; 258 } 259 return ref Stroke(NCANONICAL, equipoints, 0, 0); 260} 261