am 26c80662: Use 2D normal distribution for gesture.

* commit '26c806620c26e048918624367ee624526613b0d2':
  Use 2D normal distribution for gesture.

8 files changed, 184 insertions, 77 deletions

diff --git a/native/jni/NativeFileList.mk b/native/jni/NativeFileList.mk
index a22497fd9..1230150ea 100644
--- a/native/jni/NativeFileList.mk
+++ b/native/jni/NativeFileList.mk
@@ -101,4 +101,5 @@ LATIN_IME_CORE_SRC_FILES := \
 
 LATIN_IME_CORE_TEST_FILES := \
     defines_test.cpp \
+    suggest/core/layout/normal_distribution_2d_test.cpp \
     utils/autocorrection_threshold_utils_test.cpp
diff --git a/native/jni/src/suggest/core/layout/normal_distribution_2d.h b/native/jni/src/suggest/core/layout/normal_distribution_2d.h
new file mode 100644
index 000000000..3bc0a0153
--- /dev/null
+++ b/native/jni/src/suggest/core/layout/normal_distribution_2d.h
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef LATINIME_NORMAL_DISTRIBUTION_2D_H
+#define LATINIME_NORMAL_DISTRIBUTION_2D_H
+
+#include <cmath>
+
+#include "defines.h"
+#include "suggest/core/layout/geometry_utils.h"
+#include "suggest/core/layout/normal_distribution.h"
+
+namespace latinime {
+
+// Normal distribution on a 2D plane. The covariance is always zero, but the distribution can be
+// rotated.
+class NormalDistribution2D {
+ public:
+    NormalDistribution2D(const float uX, const float sigmaX, const float uY, const float sigmaY,
+            const float theta)
+            : mXDistribution(0.0f, sigmaX), mYDistribution(0.0f, sigmaY), mUX(uX), mUY(uY),
+              mSinTheta(sinf(theta)), mCosTheta(cosf(theta)) {}
+
+    float getProbabilityDensity(const float x, const float y) const {
+        // Shift
+        const float shiftedX = x - mUX;
+        const float shiftedY = y - mUY;
+        // Rotate
+        const float rotatedShiftedX = mCosTheta * shiftedX + mSinTheta * shiftedY;
+        const float rotatedShiftedY = -mSinTheta * shiftedX + mCosTheta * shiftedY;
+        return mXDistribution.getProbabilityDensity(rotatedShiftedX)
+                * mYDistribution.getProbabilityDensity(rotatedShiftedY);
+    }
+
+ private:
+    DISALLOW_IMPLICIT_CONSTRUCTORS(NormalDistribution2D);
+
+    const NormalDistribution mXDistribution;
+    const NormalDistribution mYDistribution;
+    const float mUX;
+    const float mUY;
+    const float mSinTheta;
+    const float mCosTheta;
+};
+} // namespace latinime
+#endif // LATINIME_NORMAL_DISTRIBUTION_2D_H
diff --git a/native/jni/src/suggest/core/layout/proximity_info_params.cpp b/native/jni/src/suggest/core/layout/proximity_info_params.cpp
index 597518a4c..a70dd7e34 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_params.cpp
+++ b/native/jni/src/suggest/core/layout/proximity_info_params.cpp
@@ -76,8 +76,12 @@ const float ProximityInfoParams::MAX_SPEEDxANGLE_RATE_FOR_STANDARD_DEVIATION = 0
 const float ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION = 0.5f;
 const float ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION = 0.15f;
 const float ProximityInfoParams::MIN_STANDARD_DEVIATION = 0.37f;
-const float ProximityInfoParams::PREV_DISTANCE_WEIGHT = 0.5f;
-const float ProximityInfoParams::NEXT_DISTANCE_WEIGHT = 0.6f;
+const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST = 1.25f;
+const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST = 0.85f;
+const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_LAST = 1.4f;
+const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST = 0.95f;
+const float ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT = 1.1f;
+const float ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT = 0.95f;
 
 // Used by ProximityInfoStateUtils::suppressCharProbabilities()
 const float ProximityInfoParams::SUPPRESSION_LENGTH_WEIGHT = 1.5f;
diff --git a/native/jni/src/suggest/core/layout/proximity_info_params.h b/native/jni/src/suggest/core/layout/proximity_info_params.h
index ae1f82c22..b8e9f5daf 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_params.h
+++ b/native/jni/src/suggest/core/layout/proximity_info_params.h
@@ -78,8 +78,13 @@ class ProximityInfoParams {
     static const float SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION;
     static const float MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION;
     static const float MIN_STANDARD_DEVIATION;
-    static const float PREV_DISTANCE_WEIGHT;
-    static const float NEXT_DISTANCE_WEIGHT;
+    // X means gesture's direction. Y means gesture's orthogonal direction.
+    static const float STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST;
+    static const float STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST;
+    static const float STANDARD_DEVIATION_X_WEIGHT_FOR_LAST;
+    static const float STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST;
+    static const float STANDARD_DEVIATION_X_WEIGHT;
+    static const float STANDARD_DEVIATION_Y_WEIGHT;
 
     // Used by ProximityInfoStateUtils::suppressCharProbabilities()
     static const float SUPPRESSION_LENGTH_WEIGHT;
diff --git a/native/jni/src/suggest/core/layout/proximity_info_state.cpp b/native/jni/src/suggest/core/layout/proximity_info_state.cpp
index 2919904e5..b75c2ef67 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_state.cpp
+++ b/native/jni/src/suggest/core/layout/proximity_info_state.cpp
@@ -134,7 +134,7 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi
                     mProximityInfo->getKeyCount(), lastSavedInputSize, mSampledInputSize,
                     &mSampledInputXs, &mSampledInputYs, &mSpeedRates, &mSampledLengthCache,
                     &mSampledNormalizedSquaredLengthCache, &mSampledNearKeySets,
-                    &mCharProbabilities);
+                    mProximityInfo, &mCharProbabilities);
             ProximityInfoStateUtils::updateSampledSearchKeySets(mProximityInfo,
                     mSampledInputSize, lastSavedInputSize, &mSampledLengthCache,
                     &mSampledNearKeySets, &mSampledSearchKeySets,
diff --git a/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp b/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp
index 5a3ff7384..638297eb1 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp
+++ b/native/jni/src/suggest/core/layout/proximity_info_state_utils.cpp
@@ -24,7 +24,7 @@
 
 #include "defines.h"
 #include "suggest/core/layout/geometry_utils.h"
-#include "suggest/core/layout/normal_distribution.h"
+#include "suggest/core/layout/normal_distribution_2d.h"
 #include "suggest/core/layout/proximity_info.h"
 #include "suggest/core/layout/proximity_info_params.h"
 
@@ -627,6 +627,7 @@ namespace latinime {
         const std::vector<int> *const sampledLengthCache,
         const std::vector<float> *const sampledNormalizedSquaredLengthCache,
         std::vector<NearKeycodesSet> *sampledNearKeySets,
+        const ProximityInfo *const proximityInfo,
         std::vector<hash_map_compat<int, float> > *charProbabilities) {
     charProbabilities->resize(sampledInputSize);
     // Calculates probabilities of using a point as a correlated point with the character
@@ -709,89 +710,57 @@ namespace latinime {
         // (1.0f - skipProbability).
         const float inputCharProbability = 1.0f - skipProbability;
 
-        const float speedxAngleRate = std::min(speedRate * currentAngle / M_PI_F
+        const float speedMultipliedByAngleRate = std::min(speedRate * currentAngle / M_PI_F
                 * ProximityInfoParams::SPEEDxANGLE_WEIGHT_FOR_STANDARD_DEVIATION,
                         ProximityInfoParams::MAX_SPEEDxANGLE_RATE_FOR_STANDARD_DEVIATION);
-        const float speedxNearestKeyDistanceRate = std::min(speedRate * nearestKeyDistance
-                * ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION,
-                        ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION);
-        const float sigma = speedxAngleRate + speedxNearestKeyDistanceRate
-                + ProximityInfoParams::MIN_STANDARD_DEVIATION;
-
-        NormalDistribution distribution(
-                ProximityInfoParams::CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION, sigma);
+        const float speedMultipliedByNearestKeyDistanceRate = std::min(
+                speedRate * nearestKeyDistance
+                        * ProximityInfoParams::SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DEVIATION,
+                                ProximityInfoParams::MAX_SPEEDxNEAREST_RATE_FOR_STANDARD_DEVIATION);
+        const float sigma = (speedMultipliedByAngleRate + speedMultipliedByNearestKeyDistanceRate
+                + ProximityInfoParams::MIN_STANDARD_DEVIATION) * mostCommonKeyWidth;
+        float theta = 0.0f;
+        // TODO: Use different metrics to compute sigmas.
+        float sigmaX = sigma;
+        float sigmaY = sigma;
+        if (i == 0 && i != sampledInputSize - 1) {
+            // First point
+            theta = getDirection(sampledInputXs, sampledInputYs, i + 1, i);
+            sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_FIRST;
+            sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_FIRST;
+        } else {
+            if (i == sampledInputSize - 1) {
+                // Last point
+                sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT_FOR_LAST;
+                sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT_FOR_LAST;
+            } else {
+                sigmaX *= ProximityInfoParams::STANDARD_DEVIATION_X_WEIGHT;
+                sigmaY *= ProximityInfoParams::STANDARD_DEVIATION_Y_WEIGHT;
+            }
+            theta = getDirection(sampledInputXs, sampledInputYs, i, i - 1);
+        }
+        NormalDistribution2D distribution((*sampledInputXs)[i], sigmaX, (*sampledInputYs)[i],
+                sigmaY, theta);
         // Summing up probability densities of all near keys.
         float sumOfProbabilityDensities = 0.0f;
         for (int j = 0; j < keyCount; ++j) {
             if ((*sampledNearKeySets)[i].test(j)) {
-                float distance = sqrtf(getPointToKeyByIdLength(
-                        maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j));
-                if (i == 0 && i != sampledInputSize - 1) {
-                    // For the first point, weighted average of distances from first point and the
-                    // next point to the key is used as a point to key distance.
-                    const float nextDistance = sqrtf(getPointToKeyByIdLength(
-                            maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount,
-                            i + 1, j));
-                    if (nextDistance < distance) {
-                        // The distance of the first point tends to bigger than continuing
-                        // points because the first touch by the user can be sloppy.
-                        // So we promote the first point if the distance of that point is larger
-                        // than the distance of the next point.
-                        distance = (distance
-                                + nextDistance * ProximityInfoParams::NEXT_DISTANCE_WEIGHT)
-                                        / (1.0f + ProximityInfoParams::NEXT_DISTANCE_WEIGHT);
-                    }
-                } else if (i != 0 && i == sampledInputSize - 1) {
-                    // For the first point, weighted average of distances from last point and
-                    // the previous point to the key is used as a point to key distance.
-                    const float previousDistance = sqrtf(getPointToKeyByIdLength(
-                            maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount,
-                            i - 1, j));
-                    if (previousDistance < distance) {
-                        // The distance of the last point tends to bigger than continuing points
-                        // because the last touch by the user can be sloppy. So we promote the
-                        // last point if the distance of that point is larger than the distance of
-                        // the previous point.
-                        distance = (distance
-                                + previousDistance * ProximityInfoParams::PREV_DISTANCE_WEIGHT)
-                                        / (1.0f + ProximityInfoParams::PREV_DISTANCE_WEIGHT);
-                    }
-                }
-                // TODO: Promote the first point when the extended line from the next input is near
-                // from a key. Also, promote the last point as well.
-                sumOfProbabilityDensities += distribution.getProbabilityDensity(distance);
+                sumOfProbabilityDensities += distribution.getProbabilityDensity(
+                        proximityInfo->getKeyCenterXOfKeyIdG(j,
+                                NOT_A_COORDINATE /* referencePointX */, true /* isGeometric */),
+                        proximityInfo->getKeyCenterYOfKeyIdG(j,
+                                NOT_A_COORDINATE /* referencePointY */, true /* isGeometric */));
             }
         }
 
         // Split the probability of an input point to keys that are close to the input point.
         for (int j = 0; j < keyCount; ++j) {
             if ((*sampledNearKeySets)[i].test(j)) {
-                float distance = sqrtf(getPointToKeyByIdLength(
-                        maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount, i, j));
-                if (i == 0 && i != sampledInputSize - 1) {
-                    // For the first point, weighted average of distances from the first point and
-                    // the next point to the key is used as a point to key distance.
-                    const float prevDistance = sqrtf(getPointToKeyByIdLength(
-                            maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount,
-                            i + 1, j));
-                    if (prevDistance < distance) {
-                        distance = (distance
-                                + prevDistance * ProximityInfoParams::NEXT_DISTANCE_WEIGHT)
-                                        / (1.0f + ProximityInfoParams::NEXT_DISTANCE_WEIGHT);
-                    }
-                } else if (i != 0 && i == sampledInputSize - 1) {
-                    // For the first point, weighted average of distances from last point and
-                    // the previous point to the key is used as a point to key distance.
-                    const float prevDistance = sqrtf(getPointToKeyByIdLength(
-                            maxPointToKeyLength, sampledNormalizedSquaredLengthCache, keyCount,
-                            i - 1, j));
-                    if (prevDistance < distance) {
-                        distance = (distance
-                                + prevDistance * ProximityInfoParams::PREV_DISTANCE_WEIGHT)
-                                        / (1.0f + ProximityInfoParams::PREV_DISTANCE_WEIGHT);
-                    }
-                }
-                const float probabilityDensity = distribution.getProbabilityDensity(distance);
+                const float probabilityDensity = distribution.getProbabilityDensity(
+                        proximityInfo->getKeyCenterXOfKeyIdG(j,
+                                NOT_A_COORDINATE /* referencePointX */, true /* isGeometric */),
+                        proximityInfo->getKeyCenterYOfKeyIdG(j,
+                                NOT_A_COORDINATE /* referencePointY */, true /* isGeometric */));
                 const float probability = inputCharProbability * probabilityDensity
                         / sumOfProbabilityDensities;
                 (*charProbabilities)[i][j] = probability;
diff --git a/native/jni/src/suggest/core/layout/proximity_info_state_utils.h b/native/jni/src/suggest/core/layout/proximity_info_state_utils.h
index ea0cd1149..5d7a9c589 100644
--- a/native/jni/src/suggest/core/layout/proximity_info_state_utils.h
+++ b/native/jni/src/suggest/core/layout/proximity_info_state_utils.h
@@ -72,6 +72,7 @@ class ProximityInfoStateUtils {
             const std::vector<int> *const sampledLengthCache,
             const std::vector<float> *const sampledNormalizedSquaredLengthCache,
             std::vector<NearKeycodesSet> *sampledNearKeySets,
+            const ProximityInfo *const proximityInfo,
             std::vector<hash_map_compat<int, float> > *charProbabilities);
     static void updateSampledSearchKeySets(const ProximityInfo *const proximityInfo,
             const int sampledInputSize, const int lastSavedInputSize,
diff --git a/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp b/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp
new file mode 100644
index 000000000..1d6a27c4f
--- /dev/null
+++ b/native/jni/tests/suggest/core/layout/normal_distribution_2d_test.cpp
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "suggest/core/layout/normal_distribution_2d.h"
+
+#include <gtest/gtest.h>
+
+#include <vector>
+
+namespace latinime {
+namespace {
+
+static const float ORIGIN_X = 0.0f;
+static const float ORIGIN_Y = 0.0f;
+static const float LARGE_STANDARD_DEVIATION = 100.0f;
+static const float SMALL_STANDARD_DEVIATION = 10.0f;
+static const float ZERO_RADIAN = 0.0f;
+
+TEST(NormalDistribution2DTest, ProbabilityDensity) {
+    const NormalDistribution2D distribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y,
+            SMALL_STANDARD_DEVIATION, ZERO_RADIAN);
+
+    static const float SMALL_COORDINATE = 10.0f;
+    static const float LARGE_COORDINATE = 20.0f;
+    // The probability density of the point near the distribution center is larger than the
+    // probability density of the point that is far from distribution center.
+    EXPECT_GE(distribution.getProbabilityDensity(SMALL_COORDINATE, SMALL_COORDINATE),
+            distribution.getProbabilityDensity(LARGE_COORDINATE, LARGE_COORDINATE));
+    // The probability density of the point shifted toward the direction that has larger standard
+    // deviation is larger than the probability density of the point shifted towards another
+    // direction.
+    EXPECT_GE(distribution.getProbabilityDensity(LARGE_COORDINATE, SMALL_COORDINATE),
+            distribution.getProbabilityDensity(SMALL_COORDINATE, LARGE_COORDINATE));
+}
+
+TEST(NormalDistribution2DTest, Rotate) {
+    static const float COORDINATES[] = {0.0f, 10.0f, 100.0f, -20.0f};
+    static const float EPSILON = 0.01f;
+    const NormalDistribution2D distribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y,
+            SMALL_STANDARD_DEVIATION, ZERO_RADIAN);
+    const NormalDistribution2D rotatedDistribution(ORIGIN_X, LARGE_STANDARD_DEVIATION, ORIGIN_Y,
+            SMALL_STANDARD_DEVIATION, M_PI_4);
+    for (const float x : COORDINATES) {
+        for (const float y : COORDINATES) {
+            // The probability density of the rotated distribution at the point and the probability
+            // density of the original distribution at the rotated point are the same.
+            const float probabilityDensity0 = distribution.getProbabilityDensity(x, y);
+            const float probabilityDensity1 = rotatedDistribution.getProbabilityDensity(-y, x);
+            EXPECT_NEAR(probabilityDensity0, probabilityDensity1, EPSILON);
+        }
+    }
+}
+
+}  // namespace
+}  // namespace latinime