Home | History | Annotate | Download | only in gesture
      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 
     17 package android.gesture;
     18 
     19 import android.graphics.RectF;
     20 import android.util.Log;
     21 
     22 import java.util.ArrayList;
     23 import java.util.Arrays;
     24 import java.io.Closeable;
     25 import java.io.IOException;
     26 
     27 import 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  */
     39 public 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.sqrt(deltaX * deltaX + deltaY * 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.sqrt(dx * dx + dy * 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.sqrt(dx * dx + dy * 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.sqrt(dx * dx + dy * 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