GestureDetectionApp/GestureRecognition/src/at/mus/recognition/Recognizer2D.java

   1 package at.mus.recognition;
   2
   3 import java.util.*;
   4
   5 public class Recognizer2D {
   6         private static final double Phi = 0.5 * (-1.0 + Math.sqrt(5.0)); // Golden Ratio
   7         private static final double AngleRange = deg2Rad(45.0);
   8         private static final double AnglePrecision = deg2Rad(2.0);
   9
  10         /* Step 1: Resample */
  11
  12         public List<Point> resample(List<Point> points, int n) {
  13                 List<Point> newPoints = new ArrayList<Point>();
  14                 double I = pathLength(points) / (n - 1);
  15                 double D = 0.0;
  16
  17                 newPoints.add(points.get(0));
  18                 for (int i = 1; i < points.size(); i++) {
  19                         Point pi_1 = points.get(i - 1);
  20                         Point pi = points.get(i);
  21                         double d = pi_1.distance(pi);
  22                         if (D + d >= I) {
  23                                 Point q = new Point(pi_1.x + ((I - D) / d) * (pi.x - pi_1.x),
  24                                                 pi_1.y + ((I - D) / d) * (pi.y - pi_1.y));
  25                                 newPoints.add(q);
  26                                 points.add(i, q);
  27                                 D = 0.0;
  28                         } else
  29                                 D += d;
  30                 }
  31                 // somtimes we fall a rounding-error short of adding the last point, so
  32                 // add it if so
  33                 if (newPoints.size() == (n - 1)) {
  34                         Point last = points.get(points.size() - 1);
  35                         newPoints.add(new Point(last.x, last.y));
  36                 }
  37                 return newPoints;
  38         }
  39
  40         private double pathLength(List<Point> points) {
  41                 double d = 0.0;
  42                 for (int i = 1; i < points.size(); i++)
  43                         d += points.get(i - 1).distance(points.get(i));
  44                 return d;
  45         }
  46
  47         /* Step 2: Rotate */
  48
  49         public List<Point> rotateToZero(List<Point> points) {
  50                 Point c = centroid(points);
  51                 Point p0 = points.get(0);
  52                 double radians = Math.atan2(c.y - p0.y, c.x - p0.x); // indicative angle
  53                 return rotateBy(points, c, radians);
  54         }
  55
  56         private List<Point> rotateBy(List<Point> points, Point c, double radians) {
  57                 double cos = Math.cos(radians);
  58                 double sin = Math.sin(radians);
  59
  60                 List<Point> newPoints = new ArrayList<Point>();
  61                 for (Point p : points) {
  62                         newPoints.add(new Point(
  63                                         (p.x - c.x) * cos - (p.y - c.y) * sin + c.x, (p.x - c.x)
  64                                                         * sin + (p.y - c.y) * cos + c.y));
  65                 }
  66                 return newPoints;
  67         }
  68
  69         private Point centroid(List<Point> points) {
  70                 double cx = 0.0, cy = 0.0;
  71                 for (Point p : points) {
  72                         cx += p.x;
  73                         cy += p.y;
  74                 }
  75                 cx /= points.size();
  76                 cy /= points.size();
  77                 return new Point(cx, cy);
  78         }
  79
  80         /* Step 3: Scale */
  81
  82         public List<Point> scaleAndTranslateTo(List<Point> points, double size, Point pt) {
  83                 List<Point> newPoints = new ArrayList<Point>();
  84
  85                 // scale
  86                 Rectangle rect = boundingBox(points);
  87                 for (Point p : points) {
  88                         newPoints.add(new Point(p.x * (size / rect.width), p.y
  89                                         * (size / rect.height)));
  90                 }
  91
  92                 // translate
  93                 Point c = centroid(newPoints);
  94                 for (Point p : newPoints) {
  95                         p.x = p.x + pt.x - c.x;
  96                         p.y = p.y + pt.y - c.y;
  97                 }
  98                 return newPoints;
  99         }
 100
 101         private Rectangle boundingBox(List<Point> points) {
 102                 double minX = Double.MAX_VALUE, maxX = Double.MIN_VALUE;
 103                 double minY = Double.MAX_VALUE, maxY = Double.MIN_VALUE;
 104                 for (Point p : points) {
 105                         if (p.x < minX)
 106                                 minX = p.x;
 107                         if (p.y < minY)
 108                                 minY = p.y;
 109                         if (p.x > maxX)
 110                                 maxX = p.x;
 111                         if (p.y > maxY)
 112                                 maxY = p.y;
 113                 }
 114                 return new Rectangle(minX, minY, maxX - minX, maxY - minY);
 115         }
 116
 117         /* Step 4: Recognition */
 118
 119         /**
 120          * @param rawPoints list of points to recognize
 121          * @param templates pre-defined list of templates
 122          * @param n number of points (resample)
 123          * @param size square size (scaleAndTranslateTo)
 124          * @param origin desired origin (scaleAndTranslateTo)
 125          */
 126         public Result recognize(List<Point> rawPoints, List<Template> templates, int n, double size, Point origin) {
 127                 List<Point> points = scaleAndTranslateTo(rotateToZero(resample(rawPoints, n)), size, origin);
 128
 129                 Point c = centroid(points);
 130                 double b = Double.MAX_VALUE, d;
 131                 Template tpl = null;
 132                 for (Template t : templates) {
 133                         d = distanceAtBestAngle(points, t, c, -AngleRange, +AngleRange, AnglePrecision);
 134                         if (d < b) {
 135                                 b = d; // best (least) distance
 136                                 tpl = t;
 137                         }
 138                 }
 139                 double halfDiagonal = Math.sqrt(size * size * 2) * 0.5;
 140                 return new Result(tpl, 1.0 - b / halfDiagonal);
 141         }
 142
 143         private double distanceAtBestAngle(List<Point> points, Template t, Point c, double a, double b, double threshold) {
 144                 double x1 = Phi * a + (1.0 - Phi) * b;
 145                 double f1 = distanceAtAngle(points, t, c, x1);
 146                 double x2 = (1.0 - Phi) * a + Phi * b;
 147                 double f2 = distanceAtAngle(points, t, c, x2);
 148
 149                 while (Math.abs(b - a) > threshold) {
 150                         if (f1 < f2) {
 151                                 b = x2;
 152                                 x2 = x1;
 153                                 f2 = f1;
 154                                 x1 = Phi * a + (1.0 - Phi) * b;
 155                                 f1 = distanceAtAngle(points, t, c, x1);
 156                         } else {
 157                                 a = x1;
 158                                 x1 = x2;
 159                                 f1 = f2;
 160                                 x2 = (1.0 - Phi) * a + Phi * b;
 161                                 f2 = distanceAtAngle(points, t, c, x2);
 162                         }
 163                 }
 164                 return Math.min(f1, f2);
 165         }
 166
 167         private double distanceAtAngle(List<Point> points, Template t, Point c,
 168                         double radians) {
 169                 List<Point> newPoints = rotateBy(points, c, radians);
 170
 171                 /* path distance */
 172                 double d = 0.0;
 173                 for (int i = 0; i < newPoints.size(); i++)
 174                         d += newPoints.get(i).distance(t.points[i]);
 175                 return d / newPoints.size();
 176         }
 177
 178         /* help methods */
 179         private static double deg2Rad(double d) {
 180                 return (d * Math.PI / 180.0);
 181         }
 182
 183         /*// not used
 184          private static double rad2Deg(double r) {
 185                 return (r * 180.0 / Math.PI);
 186         }*/
 187
 188         public static class Result {
 189                 private Template tpl;
 190                 private double match;
 191
 192                 public Result(Template tpl, double match) {
 193                         super();
 194                         this.tpl = tpl;
 195                         this.match = match;
 196                 }
 197
 198                 public Template getTemplate() {
 199                         return tpl;
 200                 }
 201
 202                 public void setTemplate(Template tpl) {
 203                         this.tpl = tpl;
 204                 }
 205
 206                 public double getMatch() {
 207                         return match;
 208                 }
 209
 210                 public void setMatch(double match) {
 211                         this.match = match;
 212                 }
 213         }
 214 }