pdollar0.d

   1 /*
   2  * The $P Point-Cloud Recognizer
   3  *
   4  *  Radu-Daniel Vatavu, Ph.D.
   5  *  University Stefan cel Mare of Suceava
   6  *  Suceava 720229, Romania
   7  *  vatavu@eed.usv.ro
   8  *
   9  *  Lisa Anthony, Ph.D.
  10  *      UMBC
  11  *      Information Systems Department
  12  *      1000 Hilltop Circle
  13  *      Baltimore, MD 21250
  14  *      lanthony@umbc.edu
  15  *
  16  *  Jacob O. Wobbrock, Ph.D.
  17  *  The Information School
  18  *  University of Washington
  19  *  Seattle, WA 98195-2840
  20  *  wobbrock@uw.edu
  21  *
  22  * The academic publication for the $P recognizer, and what should be
  23  * used to cite it, is:
  24  *
  25  *  Vatavu, R.-D., Anthony, L. and Wobbrock, J.O. (2012).
  26  *    Gestures as point clouds: A $P recognizer for user interface
  27  *    prototypes. Proceedings of the ACM Int'l Conference on
  28  *    Multimodal Interfaces (ICMI '12). Santa Monica, California
  29  *    (October 22-26, 2012). New York: ACM Press, pp. 273-280.
  30  *
  31  * This software is distributed under the "New BSD License" agreement:
  32  *
  33  * Copyright (c) 2012, Radu-Daniel Vatavu, Lisa Anthony, and
  34  * Jacob O. Wobbrock. All rights reserved.
  35  *
  36  * Redistribution and use in source and binary forms, with or without
  37  * modification, are permitted provided that the following conditions are met:
  38  *    * Redistributions of source code must retain the above copyright
  39  *      notice, this list of conditions and the following disclaimer.
  40  *    * Redistributions in binary form must reproduce the above copyright
  41  *      notice, this list of conditions and the following disclaimer in the
  42  *      documentation and/or other materials provided with the distribution.
  43  *    * Neither the names of the University Stefan cel Mare of Suceava,
  44  *  University of Washington, nor UMBC, nor the names of its contributors
  45  *  may be used to endorse or promote products derived from this software
  46  *  without specific prior written permission.
  47  *
  48  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
  49  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  50  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  51  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Radu-Daniel Vatavu OR Lisa Anthony
  52  * OR Jacob O. Wobbrock BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  53  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
  54  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  55  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  56  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  57  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  58  * SUCH DAMAGE.
  59  */
  60 module iv.pdollar0;
  61
  62 import iv.alice;
  63 import iv.cmdcon;
  64 import iv.vfs;
  65
  66
  67 // ////////////////////////////////////////////////////////////////////////// //
  68 alias DPFloat = float;
  69
  70
  71 // ////////////////////////////////////////////////////////////////////////// //
  72 struct DPResult {
  73   string name;
  74   DPFloat score;
  75   @property bool valid () const nothrow @safe @nogc { pragma(inline, true); import std.math : isNaN; return !score.isNaN; }
  76 }
  77
  78
  79 // ////////////////////////////////////////////////////////////////////////// //
  80 struct DPPoint {
  81   DPFloat x=0, y=0;
  82   uint id; // stroke ID to which this point belongs (1,2,...)
  83 }
  84
  85
  86 final class DPPointCloud {
  87 public:
  88   enum NumPoints = 32;
  89
  90 public:
  91   string mName;
  92   DPPoint[NumPoints] mPoints = DPPoint(0, 0, 0);
  93
  94 private:
  95   this () {}
  96
  97 public:
  98   this (string aname, const(DPPoint)[] pts...) nothrow @nogc {
  99     mName = aname;
 100     resample(mPoints, pts);
 101     scale(mPoints);
 102     translateTo(mPoints, DPPoint(0, 0));
 103   }
 104
 105   final @property const(DPPoint)[] points () const pure nothrow @safe @nogc { pragma(inline, true); return mPoints[]; }
 106   final @property string name () const pure nothrow @safe @nogc { pragma(inline, true); return mName; }
 107
 108   void save (VFile fl) const {
 109     string nn = mName;
 110     if (nn.length > 65535) nn = nn[0..65535]; // fuck you
 111     if (nn.length > 254) {
 112       fl.writeNum!ubyte(255);
 113       fl.writeNum!ushort(cast(ushort)nn.length);
 114     } else {
 115       fl.writeNum!ubyte(cast(ubyte)nn.length);
 116     }
 117     fl.rawWriteExact(nn);
 118     fl.writeNum!ubyte(NumPoints);
 119     foreach (const ref DPPoint pt; mPoints[]) {
 120       fl.writeNum!float(cast(float)pt.x);
 121       fl.writeNum!float(cast(float)pt.y);
 122       fl.writeNum!uint(pt.id);
 123     }
 124   }
 125
 126   void load (VFile fl) {
 127     char[] nn;
 128     ubyte len = fl.readNum!ubyte;
 129     if (len == 255) {
 130       ushort xlen = fl.readNum!ushort;
 131       nn.length = xlen;
 132     } else {
 133       nn.length = len;
 134     }
 135     fl.rawReadExact(nn);
 136     mName = cast(string)nn; // it is safe to cast here
 137     if (fl.readNum!ubyte != NumPoints) throw new Exception("invalid number of points in cloud");
 138     foreach (ref DPPoint pt; mPoints[]) {
 139       pt.x = cast(DPFloat)fl.readNum!float;
 140       pt.y = cast(DPFloat)fl.readNum!float;
 141       pt.id = fl.readNum!uint;
 142     }
 143   }
 144
 145   static DPPointCloud loadNew (VFile fl) {
 146     auto res = new DPPointCloud();
 147     res.load(fl);
 148     return res;
 149   }
 150 }
 151
 152
 153 // ////////////////////////////////////////////////////////////////////////// //
 154 final class DPGestureList {
 155 private:
 156   DPPointCloud[] mGestures;
 157
 158 public:
 159   this () nothrow @nogc {}
 160
 161   void clear () {
 162     delete mGestures;
 163   }
 164
 165   final @property const(DPPointCloud)[] gestures () const pure nothrow @safe @nogc { pragma(inline, true); return mGestures; }
 166
 167   string[] knownGestureNames () {
 168     string[] res;
 169     mainloop: foreach (DPPointCloud gst; mGestures) {
 170       foreach (string s; res) if (s == gst.mName) continue mainloop;
 171       res ~= gst.mName;
 172     }
 173     return res;
 174   }
 175
 176   void appendGesture (string aname, const(DPPoint)[] pts...) {
 177     appendGesture(new DPPointCloud(aname, pts));
 178   }
 179
 180   // you can add as many gestures with same name as you want to
 181   void appendGesture (DPPointCloud gg) {
 182     import core.memory : GC;
 183     if (gg is null) return;
 184     auto optr = mGestures.ptr;
 185     mGestures ~= gg;
 186     if (mGestures.ptr !is optr) {
 187       optr = mGestures.ptr;
 188       if (optr is GC.addrOf(optr)) GC.setAttr(optr, GC.BlkAttr.NO_INTERIOR);
 189     }
 190   }
 191
 192   // remove *ALL* gestures with the given name
 193   void removeGesture (const(char)[] name) {
 194     usize idx = 0;
 195     while (idx < mGestures.length) {
 196       if (mGestures[idx].mName == name) {
 197         foreach (immutable c; idx+1..mGestures.length) mGestures[c-1] = mGestures[c];
 198         mGestures[$-1] = null;
 199         mGestures.length -= 1;
 200         mGestures.assumeSafeAppend;
 201       } else {
 202         ++idx;
 203       }
 204     }
 205   }
 206
 207   // if you have more than one gesture with the same name, keep increasing `idx` to get more, until you'll get `null`
 208   DPPointCloud findGesture (const(char)[] name, uint idx=0) nothrow @nogc {
 209     foreach (DPPointCloud g; mGestures) {
 210       if (g.mName == name) {
 211         if (idx-- == 0) return g;
 212       }
 213     }
 214     return null;
 215   }
 216
 217   DPResult recognize (const(DPPoint)[] origpoints) nothrow @nogc {
 218     import std.algorithm : max;
 219     if (origpoints.length < 2) return DPResult.init;
 220     DPPoint[DPPointCloud.NumPoints] points;
 221     resample(points, origpoints);
 222     scale(points);
 223     translateTo(points, DPPoint(0, 0));
 224     DPFloat b = DPFloat.infinity;
 225     int u = -1;
 226     foreach (immutable idx, DPPointCloud gst; mGestures) {
 227       auto d = greedyCloudMatch(points, gst);
 228       if (d < b) {
 229         b = d; // best (least) distance
 230         u = cast(int)idx; // point-cloud
 231       }
 232     }
 233     if (u == -1) return DPResult();
 234     //{ import core.stdc.stdio; printf("b=%f (%f)\n", b, (b-2.0)/-2.0); }
 235     return (u != -1 ? DPResult(mGestures[u].mName, max((b-2.0)/-2.0, 0.0)) : DPResult.init);
 236   }
 237
 238 public:
 239   enum Signature = "DOLP8LB0";
 240
 241   void save (VFile fl) const {
 242     fl.rawWriteExact(Signature);
 243     fl.writeNum!uint(cast(uint)mGestures.length);
 244     foreach (const DPPointCloud gst; mGestures) gst.save(fl);
 245   }
 246
 247   void load (VFile fl) {
 248     delete mGestures;
 249     char[Signature.length] sign;
 250     fl.rawReadExact(sign);
 251     if (sign[0..$-1] != Signature[0..$-1]) throw new Exception("invalid $P library signature");
 252     if (sign[$-1] != Signature[$-1]) throw new Exception("invalid $P library version");
 253     uint count = fl.readNum!uint;
 254     if (count > uint.max/16) throw new Exception("too many gestures in library");
 255     mGestures.reserve(count);
 256     foreach (immutable idx; 0..count) appendGesture(DPPointCloud.loadNew(fl));
 257   }
 258 }
 259
 260
 261 // ////////////////////////////////////////////////////////////////////////// //
 262 private:
 263
 264 DPFloat greedyCloudMatch(usize n) (in ref DPPoint[n] points, in DPPointCloud P) nothrow @nogc {
 265   import std.algorithm : min;
 266   import std.math : floor, pow;
 267   enum e = cast(DPFloat)0.50;
 268   int step = cast(int)floor(pow(points.length, 1-e));
 269   assert(step > 0);
 270   DPFloat minv = DPFloat.infinity;
 271   for (int i = 0; i < points.length; i += step) {
 272     auto d1 = cloudDistance(points, P.mPoints, i);
 273     auto d2 = cloudDistance(P.mPoints, points, i);
 274     minv = min(minv, d1, d2);
 275   }
 276   return minv;
 277 }
 278
 279
 280 DPFloat cloudDistance(usize n) (in ref DPPoint[n] pts1, in ref DPPoint[n] pts2, int start) nothrow @nogc {
 281   import std.math : sqrt;
 282   bool[n] matched = false;
 283   DPFloat sum = 0;
 284   int i = start;
 285   do {
 286     int index = -1;
 287     DPFloat minv = DPFloat.infinity;
 288     foreach (immutable j, bool mtv; matched[]) {
 289       if (!mtv) {
 290         auto d = distanceSqr(pts1[i], pts2[j]);
 291         if (d < minv) { minv = d; index = cast(int)j; }
 292       }
 293     }
 294     assert(index >= 0);
 295     matched[index] = true;
 296     DPFloat weight = cast(DPFloat)1-((i-start+cast(int)pts1.length)%cast(int)pts1.length)/cast(DPFloat)pts1.length;
 297     sum += weight*sqrt(minv);
 298     i = (i+1)%cast(int)pts1.length;
 299   } while (i != start);
 300   return sum;
 301 }
 302
 303
 304 void resample(usize n) (ref DPPoint[n] newpoints, in DPPoint[] points) nothrow @nogc {
 305   import std.algorithm : max, min;
 306   import std.math : isNaN;
 307   assert(n > 0);
 308   assert(points.length > 1);
 309   immutable DPFloat I = pathLength(points)/(n-1); // interval length
 310   DPFloat D = 0;
 311   uint nppos = 0;
 312   newpoints[nppos++] = points[0];
 313   foreach (immutable idx; 1..points.length) {
 314     if (points[idx].id == points[idx-1].id) {
 315       auto d = distance(points[idx-1], points[idx]);
 316       if (D+d >= I) {
 317         DPPoint firstPoint = points[idx-1];
 318         while (D+d >= I) {
 319           // add interpolated point
 320           DPFloat t = min(max((I-D)/d, cast(DPFloat)0), cast(DPFloat)1);
 321           if (isNaN(t)) t = cast(DPFloat)0.5;
 322           newpoints[nppos++] = DPPoint((cast(DPFloat)1-t)*firstPoint.x+t*points[idx].x,
 323                                        (cast(DPFloat)1-t)*firstPoint.y+t*points[idx].y, points[idx].id);
 324           // update partial length
 325           d = D+d-I;
 326           D = 0;
 327           firstPoint = newpoints[nppos-1];
 328         }
 329         D = d;
 330       } else {
 331         D += d;
 332       }
 333     }
 334   }
 335   if (nppos == n-1) {
 336     // sometimes we fall a rounding-error short of adding the last point, so add it if so
 337     newpoints[nppos++] = DPPoint(points[$-1].x, points[$-1].y, points[$-1].id);
 338   }
 339   assert(nppos == n);
 340 }
 341
 342
 343 void scale(usize n) (ref DPPoint[n] points) nothrow @nogc {
 344   import std.algorithm : max, min;
 345   DPFloat minX = DPFloat.infinity;
 346   DPFloat minY = DPFloat.infinity;
 347   DPFloat maxX = -DPFloat.infinity;
 348   DPFloat maxY = -DPFloat.infinity;
 349   foreach (ref DPPoint p; points[]) {
 350     minX = min(minX, p.x);
 351     minY = min(minY, p.y);
 352     maxX = max(maxX, p.x);
 353     maxY = max(maxY, p.y);
 354   }
 355   DPFloat size = max(maxX-minX, maxY-minY);
 356   foreach (ref DPPoint p; points[]) {
 357     p.x = (p.x-minX)/size;
 358     p.y = (p.y-minY)/size;
 359   }
 360 }
 361
 362
 363 // translates points' centroid
 364 void translateTo(usize n) (ref DPPoint[n] points, DPPoint pt) nothrow @nogc {
 365   auto c = centroid(points);
 366   foreach (ref DPPoint p; points[]) {
 367     p.x = p.x+pt.x-c.x;
 368     p.y = p.y+pt.y-c.y;
 369   }
 370 }
 371
 372
 373 DPPoint centroid(usize n) (in ref DPPoint[n] points) nothrow @nogc {
 374   DPFloat x = 0, y = 0;
 375   foreach (const ref DPPoint p; points[]) {
 376     x += p.x;
 377     y += p.y;
 378   }
 379   immutable DPFloat pl = cast(DPFloat)1/cast(DPFloat)points.length;
 380   return DPPoint(x*pl, y*pl);
 381 }
 382
 383
 384 // length traversed by a point path
 385 DPFloat pathLength (const(DPPoint)[] points) nothrow @nogc {
 386   DPFloat d = 0;
 387   foreach (immutable idx; 1..points.length) {
 388     if (points[idx].id == points[idx-1].id) d += distance(points[idx-1], points[idx]);
 389   }
 390   return d;
 391 }
 392
 393
 394 // Euclidean distance between two points
 395 DPFloat distance() (in auto ref DPPoint p1, in auto ref DPPoint p2) nothrow @nogc {
 396   import std.math : sqrt;
 397   immutable DPFloat dx = p2.x-p1.x;
 398   immutable DPFloat dy = p2.y-p1.y;
 399   return cast(DPFloat)sqrt(dx*dx+dy*dy);
 400 }
 401
 402
 403 // Euclidean distance between two points
 404 DPFloat distanceSqr() (in auto ref DPPoint p1, in auto ref DPPoint p2) nothrow @nogc {
 405   immutable DPFloat dx = p2.x-p1.x;
 406   immutable DPFloat dy = p2.y-p1.y;
 407   return cast(DPFloat)(dx*dx+dy*dy);
 408 }