1/* 2 * Copyright (C) 2008-2009 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.gesture; 18 19import android.graphics.RectF; 20import android.util.Log; 21 22import java.util.ArrayList; 23import java.util.Arrays; 24import java.io.Closeable; 25import java.io.IOException; 26 27import static android.gesture.GestureConstants.*; 28 29/** 30 * Utility functions for gesture processing & analysis, including methods for: 31 * <ul> 32 * <li>feature extraction (e.g., samplers and those for calculating bounding 33 * boxes and gesture path lengths); 34 * <li>geometric transformation (e.g., translation, rotation and scaling); 35 * <li>gesture similarity comparison (e.g., calculating Euclidean or Cosine 36 * distances between two gestures). 37 * </ul> 38 */ 39public final class GestureUtils { 40 41 private static final float SCALING_THRESHOLD = 0.26f; 42 private static final float NONUNIFORM_SCALE = (float) Math.sqrt(2); 43 44 private GestureUtils() { 45 } 46 47 /** 48 * Closes the specified stream. 49 * 50 * @param stream The stream to close. 51 */ 52 static void closeStream(Closeable stream) { 53 if (stream != null) { 54 try { 55 stream.close(); 56 } catch (IOException e) { 57 Log.e(LOG_TAG, "Could not close stream", e); 58 } 59 } 60 } 61 62 /** 63 * Samples the gesture spatially by rendering the gesture into a 2D 64 * grayscale bitmap. Scales the gesture to fit the size of the bitmap. 65 * The scaling does not necessarily keep the aspect ratio of the gesture. 66 * 67 * @param gesture the gesture to be sampled 68 * @param bitmapSize the size of the bitmap 69 * @return a bitmapSize x bitmapSize grayscale bitmap that is represented 70 * as a 1D array. The float at index i represents the grayscale 71 * value at pixel [i%bitmapSize, i/bitmapSize] 72 */ 73 public static float[] spatialSampling(Gesture gesture, int bitmapSize) { 74 return spatialSampling(gesture, bitmapSize, false); 75 } 76 77 /** 78 * Samples the gesture spatially by rendering the gesture into a 2D 79 * grayscale bitmap. Scales the gesture to fit the size of the bitmap. 80 * 81 * @param gesture the gesture to be sampled 82 * @param bitmapSize the size of the bitmap 83 * @param keepAspectRatio if the scaling should keep the gesture's 84 * aspect ratio 85 * 86 * @return a bitmapSize x bitmapSize grayscale bitmap that is represented 87 * as a 1D array. The float at index i represents the grayscale 88 * value at pixel [i%bitmapSize, i/bitmapSize] 89 */ 90 public static float[] spatialSampling(Gesture gesture, int bitmapSize, 91 boolean keepAspectRatio) { 92 final float targetPatchSize = bitmapSize - 1; 93 float[] sample = new float[bitmapSize * bitmapSize]; 94 Arrays.fill(sample, 0); 95 96 RectF rect = gesture.getBoundingBox(); 97 final float gestureWidth = rect.width(); 98 final float gestureHeight = rect.height(); 99 float sx = targetPatchSize / gestureWidth; 100 float sy = targetPatchSize / gestureHeight; 101 102 if (keepAspectRatio) { 103 float scale = sx < sy ? sx : sy; 104 sx = scale; 105 sy = scale; 106 } else { 107 108 float aspectRatio = gestureWidth / gestureHeight; 109 if (aspectRatio > 1) { 110 aspectRatio = 1 / aspectRatio; 111 } 112 if (aspectRatio < SCALING_THRESHOLD) { 113 float scale = sx < sy ? sx : sy; 114 sx = scale; 115 sy = scale; 116 } else { 117 if (sx > sy) { 118 float scale = sy * NONUNIFORM_SCALE; 119 if (scale < sx) { 120 sx = scale; 121 } 122 } else { 123 float scale = sx * NONUNIFORM_SCALE; 124 if (scale < sy) { 125 sy = scale; 126 } 127 } 128 } 129 } 130 float preDx = -rect.centerX(); 131 float preDy = -rect.centerY(); 132 float postDx = targetPatchSize / 2; 133 float postDy = targetPatchSize / 2; 134 final ArrayList<GestureStroke> strokes = gesture.getStrokes(); 135 final int count = strokes.size(); 136 int size; 137 float xpos; 138 float ypos; 139 for (int index = 0; index < count; index++) { 140 final GestureStroke stroke = strokes.get(index); 141 float[] strokepoints = stroke.points; 142 size = strokepoints.length; 143 final float[] pts = new float[size]; 144 for (int i = 0; i < size; i += 2) { 145 pts[i] = (strokepoints[i] + preDx) * sx + postDx; 146 pts[i + 1] = (strokepoints[i + 1] + preDy) * sy + postDy; 147 } 148 float segmentEndX = -1; 149 float segmentEndY = -1; 150 for (int i = 0; i < size; i += 2) { 151 float segmentStartX = pts[i] < 0 ? 0 : pts[i]; 152 float segmentStartY = pts[i + 1] < 0 ? 0 : pts[i + 1]; 153 if (segmentStartX > targetPatchSize) { 154 segmentStartX = targetPatchSize; 155 } 156 if (segmentStartY > targetPatchSize) { 157 segmentStartY = targetPatchSize; 158 } 159 plot(segmentStartX, segmentStartY, sample, bitmapSize); 160 if (segmentEndX != -1) { 161 // Evaluate horizontally 162 if (segmentEndX > segmentStartX) { 163 xpos = (float) Math.ceil(segmentStartX); 164 float slope = (segmentEndY - segmentStartY) / 165 (segmentEndX - segmentStartX); 166 while (xpos < segmentEndX) { 167 ypos = slope * (xpos - segmentStartX) + segmentStartY; 168 plot(xpos, ypos, sample, bitmapSize); 169 xpos++; 170 } 171 } else if (segmentEndX < segmentStartX){ 172 xpos = (float) Math.ceil(segmentEndX); 173 float slope = (segmentEndY - segmentStartY) / 174 (segmentEndX - segmentStartX); 175 while (xpos < segmentStartX) { 176 ypos = slope * (xpos - segmentStartX) + segmentStartY; 177 plot(xpos, ypos, sample, bitmapSize); 178 xpos++; 179 } 180 } 181 // Evaluate vertically 182 if (segmentEndY > segmentStartY) { 183 ypos = (float) Math.ceil(segmentStartY); 184 float invertSlope = (segmentEndX - segmentStartX) / 185 (segmentEndY - segmentStartY); 186 while (ypos < segmentEndY) { 187 xpos = invertSlope * (ypos - segmentStartY) + segmentStartX; 188 plot(xpos, ypos, sample, bitmapSize); 189 ypos++; 190 } 191 } else if (segmentEndY < segmentStartY) { 192 ypos = (float) Math.ceil(segmentEndY); 193 float invertSlope = (segmentEndX - segmentStartX) / 194 (segmentEndY - segmentStartY); 195 while (ypos < segmentStartY) { 196 xpos = invertSlope * (ypos - segmentStartY) + segmentStartX; 197 plot(xpos, ypos, sample, bitmapSize); 198 ypos++; 199 } 200 } 201 } 202 segmentEndX = segmentStartX; 203 segmentEndY = segmentStartY; 204 } 205 } 206 return sample; 207 } 208 209 private static void plot(float x, float y, float[] sample, int sampleSize) { 210 x = x < 0 ? 0 : x; 211 y = y < 0 ? 0 : y; 212 int xFloor = (int) Math.floor(x); 213 int xCeiling = (int) Math.ceil(x); 214 int yFloor = (int) Math.floor(y); 215 int yCeiling = (int) Math.ceil(y); 216 217 // if it's an integer 218 if (x == xFloor && y == yFloor) { 219 int index = yCeiling * sampleSize + xCeiling; 220 if (sample[index] < 1){ 221 sample[index] = 1; 222 } 223 } else { 224 final double xFloorSq = Math.pow(xFloor - x, 2); 225 final double yFloorSq = Math.pow(yFloor - y, 2); 226 final double xCeilingSq = Math.pow(xCeiling - x, 2); 227 final double yCeilingSq = Math.pow(yCeiling - y, 2); 228 float topLeft = (float) Math.sqrt(xFloorSq + yFloorSq); 229 float topRight = (float) Math.sqrt(xCeilingSq + yFloorSq); 230 float btmLeft = (float) Math.sqrt(xFloorSq + yCeilingSq); 231 float btmRight = (float) Math.sqrt(xCeilingSq + yCeilingSq); 232 float sum = topLeft + topRight + btmLeft + btmRight; 233 234 float value = topLeft / sum; 235 int index = yFloor * sampleSize + xFloor; 236 if (value > sample[index]){ 237 sample[index] = value; 238 } 239 240 value = topRight / sum; 241 index = yFloor * sampleSize + xCeiling; 242 if (value > sample[index]){ 243 sample[index] = value; 244 } 245 246 value = btmLeft / sum; 247 index = yCeiling * sampleSize + xFloor; 248 if (value > sample[index]){ 249 sample[index] = value; 250 } 251 252 value = btmRight / sum; 253 index = yCeiling * sampleSize + xCeiling; 254 if (value > sample[index]){ 255 sample[index] = value; 256 } 257 } 258 } 259 260 /** 261 * Samples a stroke temporally into a given number of evenly-distributed 262 * points. 263 * 264 * @param stroke the gesture stroke to be sampled 265 * @param numPoints the number of points 266 * @return the sampled points in the form of [x1, y1, x2, y2, ..., xn, yn] 267 */ 268 public static float[] temporalSampling(GestureStroke stroke, int numPoints) { 269 final float increment = stroke.length / (numPoints - 1); 270 int vectorLength = numPoints * 2; 271 float[] vector = new float[vectorLength]; 272 float distanceSoFar = 0; 273 float[] pts = stroke.points; 274 float lstPointX = pts[0]; 275 float lstPointY = pts[1]; 276 int index = 0; 277 float currentPointX = Float.MIN_VALUE; 278 float currentPointY = Float.MIN_VALUE; 279 vector[index] = lstPointX; 280 index++; 281 vector[index] = lstPointY; 282 index++; 283 int i = 0; 284 int count = pts.length / 2; 285 while (i < count) { 286 if (currentPointX == Float.MIN_VALUE) { 287 i++; 288 if (i >= count) { 289 break; 290 } 291 currentPointX = pts[i * 2]; 292 currentPointY = pts[i * 2 + 1]; 293 } 294 float deltaX = currentPointX - lstPointX; 295 float deltaY = currentPointY - lstPointY; 296 float distance = (float) Math.hypot(deltaX, deltaY); 297 if (distanceSoFar + distance >= increment) { 298 float ratio = (increment - distanceSoFar) / distance; 299 float nx = lstPointX + ratio * deltaX; 300 float ny = lstPointY + ratio * deltaY; 301 vector[index] = nx; 302 index++; 303 vector[index] = ny; 304 index++; 305 lstPointX = nx; 306 lstPointY = ny; 307 distanceSoFar = 0; 308 } else { 309 lstPointX = currentPointX; 310 lstPointY = currentPointY; 311 currentPointX = Float.MIN_VALUE; 312 currentPointY = Float.MIN_VALUE; 313 distanceSoFar += distance; 314 } 315 } 316 317 for (i = index; i < vectorLength; i += 2) { 318 vector[i] = lstPointX; 319 vector[i + 1] = lstPointY; 320 } 321 return vector; 322 } 323 324 /** 325 * Calculates the centroid of a set of points. 326 * 327 * @param points the points in the form of [x1, y1, x2, y2, ..., xn, yn] 328 * @return the centroid 329 */ 330 static float[] computeCentroid(float[] points) { 331 float centerX = 0; 332 float centerY = 0; 333 int count = points.length; 334 for (int i = 0; i < count; i++) { 335 centerX += points[i]; 336 i++; 337 centerY += points[i]; 338 } 339 float[] center = new float[2]; 340 center[0] = 2 * centerX / count; 341 center[1] = 2 * centerY / count; 342 343 return center; 344 } 345 346 /** 347 * Calculates the variance-covariance matrix of a set of points. 348 * 349 * @param points the points in the form of [x1, y1, x2, y2, ..., xn, yn] 350 * @return the variance-covariance matrix 351 */ 352 private static float[][] computeCoVariance(float[] points) { 353 float[][] array = new float[2][2]; 354 array[0][0] = 0; 355 array[0][1] = 0; 356 array[1][0] = 0; 357 array[1][1] = 0; 358 int count = points.length; 359 for (int i = 0; i < count; i++) { 360 float x = points[i]; 361 i++; 362 float y = points[i]; 363 array[0][0] += x * x; 364 array[0][1] += x * y; 365 array[1][0] = array[0][1]; 366 array[1][1] += y * y; 367 } 368 array[0][0] /= (count / 2); 369 array[0][1] /= (count / 2); 370 array[1][0] /= (count / 2); 371 array[1][1] /= (count / 2); 372 373 return array; 374 } 375 376 static float computeTotalLength(float[] points) { 377 float sum = 0; 378 int count = points.length - 4; 379 for (int i = 0; i < count; i += 2) { 380 float dx = points[i + 2] - points[i]; 381 float dy = points[i + 3] - points[i + 1]; 382 sum += Math.hypot(dx, dy); 383 } 384 return sum; 385 } 386 387 static float computeStraightness(float[] points) { 388 float totalLen = computeTotalLength(points); 389 float dx = points[2] - points[0]; 390 float dy = points[3] - points[1]; 391 return (float) Math.hypot(dx, dy) / totalLen; 392 } 393 394 static float computeStraightness(float[] points, float totalLen) { 395 float dx = points[2] - points[0]; 396 float dy = points[3] - points[1]; 397 return (float) Math.hypot(dx, dy) / totalLen; 398 } 399 400 /** 401 * Calculates the squared Euclidean distance between two vectors. 402 * 403 * @param vector1 404 * @param vector2 405 * @return the distance 406 */ 407 static float squaredEuclideanDistance(float[] vector1, float[] vector2) { 408 float squaredDistance = 0; 409 int size = vector1.length; 410 for (int i = 0; i < size; i++) { 411 float difference = vector1[i] - vector2[i]; 412 squaredDistance += difference * difference; 413 } 414 return squaredDistance / size; 415 } 416 417 /** 418 * Calculates the cosine distance between two instances. 419 * 420 * @param vector1 421 * @param vector2 422 * @return the distance between 0 and Math.PI 423 */ 424 static float cosineDistance(float[] vector1, float[] vector2) { 425 float sum = 0; 426 int len = vector1.length; 427 for (int i = 0; i < len; i++) { 428 sum += vector1[i] * vector2[i]; 429 } 430 return (float) Math.acos(sum); 431 } 432 433 /** 434 * Calculates the "minimum" cosine distance between two instances. 435 * 436 * @param vector1 437 * @param vector2 438 * @param numOrientations the maximum number of orientation allowed 439 * @return the distance between the two instances (between 0 and Math.PI) 440 */ 441 static float minimumCosineDistance(float[] vector1, float[] vector2, int numOrientations) { 442 final int len = vector1.length; 443 float a = 0; 444 float b = 0; 445 for (int i = 0; i < len; i += 2) { 446 a += vector1[i] * vector2[i] + vector1[i + 1] * vector2[i + 1]; 447 b += vector1[i] * vector2[i + 1] - vector1[i + 1] * vector2[i]; 448 } 449 if (a != 0) { 450 final float tan = b/a; 451 final double angle = Math.atan(tan); 452 if (numOrientations > 2 && Math.abs(angle) >= Math.PI / numOrientations) { 453 return (float) Math.acos(a); 454 } else { 455 final double cosine = Math.cos(angle); 456 final double sine = cosine * tan; 457 return (float) Math.acos(a * cosine + b * sine); 458 } 459 } else { 460 return (float) Math.PI / 2; 461 } 462 } 463 464 /** 465 * Computes an oriented, minimum bounding box of a set of points. 466 * 467 * @param originalPoints 468 * @return an oriented bounding box 469 */ 470 public static OrientedBoundingBox computeOrientedBoundingBox(ArrayList<GesturePoint> originalPoints) { 471 final int count = originalPoints.size(); 472 float[] points = new float[count * 2]; 473 for (int i = 0; i < count; i++) { 474 GesturePoint point = originalPoints.get(i); 475 int index = i * 2; 476 points[index] = point.x; 477 points[index + 1] = point.y; 478 } 479 float[] meanVector = computeCentroid(points); 480 return computeOrientedBoundingBox(points, meanVector); 481 } 482 483 /** 484 * Computes an oriented, minimum bounding box of a set of points. 485 * 486 * @param originalPoints 487 * @return an oriented bounding box 488 */ 489 public static OrientedBoundingBox computeOrientedBoundingBox(float[] originalPoints) { 490 int size = originalPoints.length; 491 float[] points = new float[size]; 492 for (int i = 0; i < size; i++) { 493 points[i] = originalPoints[i]; 494 } 495 float[] meanVector = computeCentroid(points); 496 return computeOrientedBoundingBox(points, meanVector); 497 } 498 499 private static OrientedBoundingBox computeOrientedBoundingBox(float[] points, float[] centroid) { 500 translate(points, -centroid[0], -centroid[1]); 501 502 float[][] array = computeCoVariance(points); 503 float[] targetVector = computeOrientation(array); 504 505 float angle; 506 if (targetVector[0] == 0 && targetVector[1] == 0) { 507 angle = (float) -Math.PI/2; 508 } else { // -PI<alpha<PI 509 angle = (float) Math.atan2(targetVector[1], targetVector[0]); 510 rotate(points, -angle); 511 } 512 513 float minx = Float.MAX_VALUE; 514 float miny = Float.MAX_VALUE; 515 float maxx = Float.MIN_VALUE; 516 float maxy = Float.MIN_VALUE; 517 int count = points.length; 518 for (int i = 0; i < count; i++) { 519 if (points[i] < minx) { 520 minx = points[i]; 521 } 522 if (points[i] > maxx) { 523 maxx = points[i]; 524 } 525 i++; 526 if (points[i] < miny) { 527 miny = points[i]; 528 } 529 if (points[i] > maxy) { 530 maxy = points[i]; 531 } 532 } 533 534 return new OrientedBoundingBox((float) (angle * 180 / Math.PI), centroid[0], centroid[1], maxx - minx, maxy - miny); 535 } 536 537 private static float[] computeOrientation(float[][] covarianceMatrix) { 538 float[] targetVector = new float[2]; 539 if (covarianceMatrix[0][1] == 0 || covarianceMatrix[1][0] == 0) { 540 targetVector[0] = 1; 541 targetVector[1] = 0; 542 } 543 544 float a = -covarianceMatrix[0][0] - covarianceMatrix[1][1]; 545 float b = covarianceMatrix[0][0] * covarianceMatrix[1][1] - covarianceMatrix[0][1] 546 * covarianceMatrix[1][0]; 547 float value = a / 2; 548 float rightside = (float) Math.sqrt(Math.pow(value, 2) - b); 549 float lambda1 = -value + rightside; 550 float lambda2 = -value - rightside; 551 if (lambda1 == lambda2) { 552 targetVector[0] = 0; 553 targetVector[1] = 0; 554 } else { 555 float lambda = lambda1 > lambda2 ? lambda1 : lambda2; 556 targetVector[0] = 1; 557 targetVector[1] = (lambda - covarianceMatrix[0][0]) / covarianceMatrix[0][1]; 558 } 559 return targetVector; 560 } 561 562 563 static float[] rotate(float[] points, float angle) { 564 float cos = (float) Math.cos(angle); 565 float sin = (float) Math.sin(angle); 566 int size = points.length; 567 for (int i = 0; i < size; i += 2) { 568 float x = points[i] * cos - points[i + 1] * sin; 569 float y = points[i] * sin + points[i + 1] * cos; 570 points[i] = x; 571 points[i + 1] = y; 572 } 573 return points; 574 } 575 576 static float[] translate(float[] points, float dx, float dy) { 577 int size = points.length; 578 for (int i = 0; i < size; i += 2) { 579 points[i] += dx; 580 points[i + 1] += dy; 581 } 582 return points; 583 } 584 585 static float[] scale(float[] points, float sx, float sy) { 586 int size = points.length; 587 for (int i = 0; i < size; i += 2) { 588 points[i] *= sx; 589 points[i + 1] *= sy; 590 } 591 return points; 592 } 593} 594