diff options
Diffstat (limited to 'native/jni/src/proximity_info_state.cpp')
| -rw-r--r-- | native/jni/src/proximity_info_state.cpp | 560 |
1 files changed, 362 insertions, 198 deletions
diff --git a/native/jni/src/proximity_info_state.cpp b/native/jni/src/proximity_info_state.cpp index 90e3671eb..0f7e4d65f 100644 --- a/native/jni/src/proximity_info_state.cpp +++ b/native/jni/src/proximity_info_state.cpp @@ -105,6 +105,7 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi mLengthCache.clear(); mDistanceCache.clear(); mNearKeysVector.clear(); + mSearchKeysVector.clear(); mRelativeSpeeds.clear(); mCharProbabilities.clear(); } @@ -132,6 +133,10 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi NearKeysDistanceMap *currentNearKeysDistances = &nearKeysDistances[0]; NearKeysDistanceMap *prevNearKeysDistances = &nearKeysDistances[1]; NearKeysDistanceMap *prevPrevNearKeysDistances = &nearKeysDistances[2]; + // "sumAngle" is accumulated by each angle of input points. And when "sumAngle" exceeds + // the threshold we save that point, reset sumAngle. This aims to keep the figure of + // the curve. + float sumAngle = 0.0f; for (int i = pushTouchPointStartIndex; i <= lastInputIndex; ++i) { // Assuming pointerId == 0 if pointerIds is null. @@ -144,9 +149,18 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi const int x = proximityOnly ? NOT_A_COORDINATE : xCoordinates[i]; const int y = proximityOnly ? NOT_A_COORDINATE : yCoordinates[i]; const int time = times ? times[i] : -1; + + if (i > 1) { + const float prevAngle = getAngle(xCoordinates[i - 2], yCoordinates[i - 2], + xCoordinates[i - 1], yCoordinates[i - 1]); + const float currentAngle = + getAngle(xCoordinates[i - 1], yCoordinates[i - 1], x, y); + sumAngle += getAngleDiff(prevAngle, currentAngle); + } + if (pushTouchPoint(i, c, x, y, time, isGeometric /* do sampling */, - i == lastInputIndex, currentNearKeysDistances, prevNearKeysDistances, - prevPrevNearKeysDistances)) { + i == lastInputIndex, sumAngle, currentNearKeysDistances, + prevNearKeysDistances, prevPrevNearKeysDistances)) { // Previous point information was popped. NearKeysDistanceMap *tmp = prevNearKeysDistances; prevNearKeysDistances = currentNearKeysDistances; @@ -156,6 +170,7 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi prevPrevNearKeysDistances = prevNearKeysDistances; prevNearKeysDistances = currentNearKeysDistances; currentNearKeysDistances = tmp; + sumAngle = 0.0f; } } } @@ -163,6 +178,7 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi } if (mInputSize > 0 && isGeometric) { + // Relative speed calculation. const int sumDuration = mTimes.back() - mTimes.front(); const int sumLength = mLengthCache.back() - mLengthCache.front(); const float averageSpeed = static_cast<float>(sumLength) / static_cast<float>(sumDuration); @@ -174,7 +190,7 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi // Calculate velocity by using distances and durations of // NUM_POINTS_FOR_SPEED_CALCULATION points for both forward and backward. - static const int NUM_POINTS_FOR_SPEED_CALCULATION = 1; + static const int NUM_POINTS_FOR_SPEED_CALCULATION = 2; for (int j = index; j < min(inputSize - 1, index + NUM_POINTS_FOR_SPEED_CALCULATION); ++j) { if (i < mInputSize - 1 && j >= mInputIndice[i + 1]) { @@ -202,12 +218,21 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi } } + if (DEBUG_GEO_FULL) { + for (int i = 0; i < mInputSize; ++i) { + AKLOGI("Sampled(%d): x = %d, y = %d, time = %d", i, mInputXs[i], mInputYs[i], + mTimes[i]); + } + } + if (mInputSize > 0) { const int keyCount = mProximityInfo->getKeyCount(); mNearKeysVector.resize(mInputSize); + mSearchKeysVector.resize(mInputSize); mDistanceCache.resize(mInputSize * keyCount); for (int i = lastSavedInputSize; i < mInputSize; ++i) { mNearKeysVector[i].reset(); + mSearchKeysVector[i].reset(); static const float NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD = 4.0f; for (int k = 0; k < keyCount; ++k) { const int index = i * keyCount + k; @@ -217,25 +242,28 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi mProximityInfo->getNormalizedSquaredDistanceFromCenterFloatG(k, x, y); mDistanceCache[index] = normalizedSquaredDistance; if (normalizedSquaredDistance < NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD) { - mNearKeysVector[i].set(k, 1); + mNearKeysVector[i][k] = true; } } } - - static const float READ_FORWORD_LENGTH_SCALE = 0.95f; - const int readForwordLength = static_cast<int>( - hypotf(mProximityInfo->getKeyboardWidth(), mProximityInfo->getKeyboardHeight()) - * READ_FORWORD_LENGTH_SCALE); - for (int i = 0; i < mInputSize; ++i) { - if (DEBUG_GEO_FULL) { - AKLOGI("Sampled(%d): x = %d, y = %d, time = %d", i, mInputXs[i], mInputYs[i], - mTimes[i]); - } - for (int j = max(i + 1, lastSavedInputSize); j < mInputSize; ++j) { - if (mLengthCache[j] - mLengthCache[i] >= readForwordLength) { - break; + if (isGeometric) { + // updates probabilities of skipping or mapping each key for all points. + updateAlignPointProbabilities(lastSavedInputSize); + + static const float READ_FORWORD_LENGTH_SCALE = 0.95f; + const int readForwordLength = static_cast<int>( + hypotf(mProximityInfo->getKeyboardWidth(), mProximityInfo->getKeyboardHeight()) + * READ_FORWORD_LENGTH_SCALE); + for (int i = 0; i < mInputSize; ++i) { + if (i >= lastSavedInputSize) { + mSearchKeysVector[i].reset(); + } + for (int j = max(i, lastSavedInputSize); j < mInputSize; ++j) { + if (mLengthCache[j] - mLengthCache[i] >= readForwordLength) { + break; + } + mSearchKeysVector[i] |= mNearKeysVector[j]; } - mNearKeysVector[i] |= mNearKeysVector[j]; } } } @@ -307,10 +335,6 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi if (DEBUG_GEO_FULL) { AKLOGI("ProximityState init finished: %d points out of %d", mInputSize, inputSize); } - if (isGeometric && mInputSize > 0) { - // updates probabilities of skipping or mapping each key for all points. - updateAlignPointProbabilities(); - } } bool ProximityInfoState::checkAndReturnIsContinuationPossible(const int inputSize, @@ -329,7 +353,7 @@ bool ProximityInfoState::checkAndReturnIsContinuationPossible(const int inputSiz // the given point and the nearest key position. float ProximityInfoState::updateNearKeysDistances(const int x, const int y, NearKeysDistanceMap *const currentNearKeysDistances) { - static const float NEAR_KEY_THRESHOLD = 1.7f; + static const float NEAR_KEY_THRESHOLD = 2.0f; currentNearKeysDistances->clear(); const int keyCount = mProximityInfo->getKeyCount(); @@ -350,7 +374,7 @@ float ProximityInfoState::updateNearKeysDistances(const int x, const int y, bool ProximityInfoState::isPrevLocalMin(const NearKeysDistanceMap *const currentNearKeysDistances, const NearKeysDistanceMap *const prevNearKeysDistances, const NearKeysDistanceMap *const prevPrevNearKeysDistances) const { - static const float MARGIN = 0.03f; + static const float MARGIN = 0.01f; for (NearKeysDistanceMap::const_iterator it = prevNearKeysDistances->begin(); it != prevNearKeysDistances->end(); ++it) { @@ -367,69 +391,49 @@ bool ProximityInfoState::isPrevLocalMin(const NearKeysDistanceMap *const current // Calculating a point score that indicates usefulness of the point. float ProximityInfoState::getPointScore( const int x, const int y, const int time, const bool lastPoint, const float nearest, - const NearKeysDistanceMap *const currentNearKeysDistances, + const float sumAngle, const NearKeysDistanceMap *const currentNearKeysDistances, const NearKeysDistanceMap *const prevNearKeysDistances, const NearKeysDistanceMap *const prevPrevNearKeysDistances) const { static const int DISTANCE_BASE_SCALE = 100; - static const int SAVE_DISTANCE_SCALE = 500; - static const int SKIP_DISTANCE_SCALE = 10; - static const float NEAR_KEY_THRESHOLD = 1.0f; - static const int CHECK_LOCALMIN_DISTANCE_THRESHOLD_SCALE = 100; - static const int STRAIGHT_SKIP_DISTANCE_THRESHOLD_SCALE = 200; - static const int CORNER_CHECK_DISTANCE_THRESHOLD_SCALE = 20; - static const float SAVE_DISTANCE_SCORE = 2.0f; - static const float SKIP_DISTANCE_SCORE = -1.0f; + static const float NEAR_KEY_THRESHOLD = 0.6f; + static const int CORNER_CHECK_DISTANCE_THRESHOLD_SCALE = 25; static const float NOT_LOCALMIN_DISTANCE_SCORE = -1.0f; - static const float LOCALMIN_DISTANCE_AND_NEAR_TO_KEY_SCORE = 2.0f; - static const float STRAIGHT_ANGLE_THRESHOLD = M_PI_F / 36.0f; - static const float STRAIGHT_SKIP_NEAREST_DISTANCE_THRESHOLD = 0.5f; - static const float STRAIGHT_SKIP_SCORE = -1.0f; - static const float CORNER_ANGLE_THRESHOLD = M_PI_F / 6.0f; + static const float LOCALMIN_DISTANCE_AND_NEAR_TO_KEY_SCORE = 1.0f; + static const float CORNER_ANGLE_THRESHOLD = M_PI_F * 2.0f / 3.0f; + static const float CORNER_SUM_ANGLE_THRESHOLD = M_PI_F / 4.0f; static const float CORNER_SCORE = 1.0f; - const std::size_t size = mInputXs.size(); - if (size <= 1) { + const size_t size = mInputXs.size(); + // If there is only one point, add this point. Besides, if the previous point's distance map + // is empty, we re-compute nearby keys distances from the current point. + // Note that the current point is the first point in the incremental input that needs to + // be re-computed. + if (size <= 1 || prevNearKeysDistances->empty()) { return 0.0f; } + const int baseSampleRate = mProximityInfo->getMostCommonKeyWidth(); - const int distNext = getDistanceInt(x, y, mInputXs.back(), mInputYs.back()) - * DISTANCE_BASE_SCALE; const int distPrev = getDistanceInt(mInputXs.back(), mInputYs.back(), mInputXs[size - 2], mInputYs[size - 2]) * DISTANCE_BASE_SCALE; float score = 0.0f; - // Sum of distances - if (distPrev + distNext > baseSampleRate * SAVE_DISTANCE_SCALE) { - score += SAVE_DISTANCE_SCORE; - } - // Distance - if (distPrev < baseSampleRate * SKIP_DISTANCE_SCALE) { - score += SKIP_DISTANCE_SCORE; - } // Location - if (distPrev < baseSampleRate * CHECK_LOCALMIN_DISTANCE_THRESHOLD_SCALE) { - if (!isPrevLocalMin(currentNearKeysDistances, prevNearKeysDistances, - prevPrevNearKeysDistances)) { - score += NOT_LOCALMIN_DISTANCE_SCORE; - } else if (nearest < NEAR_KEY_THRESHOLD) { - // Promote points nearby keys - score += LOCALMIN_DISTANCE_AND_NEAR_TO_KEY_SCORE; - } + if (!isPrevLocalMin(currentNearKeysDistances, prevNearKeysDistances, + prevPrevNearKeysDistances)) { + score += NOT_LOCALMIN_DISTANCE_SCORE; + } else if (nearest < NEAR_KEY_THRESHOLD) { + // Promote points nearby keys + score += LOCALMIN_DISTANCE_AND_NEAR_TO_KEY_SCORE; } // Angle const float angle1 = getAngle(x, y, mInputXs.back(), mInputYs.back()); const float angle2 = getAngle(mInputXs.back(), mInputYs.back(), mInputXs[size - 2], mInputYs[size - 2]); const float angleDiff = getAngleDiff(angle1, angle2); - // Skip straight - if (nearest > STRAIGHT_SKIP_NEAREST_DISTANCE_THRESHOLD - && distPrev < baseSampleRate * STRAIGHT_SKIP_DISTANCE_THRESHOLD_SCALE - && angleDiff < STRAIGHT_ANGLE_THRESHOLD) { - score += STRAIGHT_SKIP_SCORE; - } + // Save corner if (distPrev > baseSampleRate * CORNER_CHECK_DISTANCE_THRESHOLD_SCALE - && angleDiff > CORNER_ANGLE_THRESHOLD) { + && (sumAngle > CORNER_SUM_ANGLE_THRESHOLD || angleDiff > CORNER_ANGLE_THRESHOLD)) { score += CORNER_SCORE; } return score; @@ -438,18 +442,17 @@ float ProximityInfoState::getPointScore( // Sampling touch point and pushing information to vectors. // Returning if previous point is popped or not. bool ProximityInfoState::pushTouchPoint(const int inputIndex, const int nodeChar, int x, int y, - const int time, const bool sample, const bool isLastPoint, + const int time, const bool sample, const bool isLastPoint, const float sumAngle, NearKeysDistanceMap *const currentNearKeysDistances, const NearKeysDistanceMap *const prevNearKeysDistances, const NearKeysDistanceMap *const prevPrevNearKeysDistances) { static const int LAST_POINT_SKIP_DISTANCE_SCALE = 4; - static const int LAST_AND_NOT_NEAREST_POINT_SKIP_DISTANCE_SCALE = 2; size_t size = mInputXs.size(); bool popped = false; if (nodeChar < 0 && sample) { const float nearest = updateNearKeysDistances(x, y, currentNearKeysDistances); - const float score = getPointScore(x, y, time, isLastPoint, nearest, + const float score = getPointScore(x, y, time, isLastPoint, nearest, sumAngle, currentNearKeysDistances, prevNearKeysDistances, prevPrevNearKeysDistances); if (score < 0) { // Pop previous point because it would be useless. @@ -461,9 +464,8 @@ bool ProximityInfoState::pushTouchPoint(const int inputIndex, const int nodeChar } // Check if the last point should be skipped. if (isLastPoint && size > 0) { - const int lastPointsDistance = getDistanceInt(x, y, mInputXs.back(), mInputYs.back()); - if (lastPointsDistance * LAST_POINT_SKIP_DISTANCE_SCALE - < mProximityInfo->getMostCommonKeyWidth()) { + if (getDistanceInt(x, y, mInputXs.back(), mInputYs.back()) + * LAST_POINT_SKIP_DISTANCE_SCALE < mProximityInfo->getMostCommonKeyWidth()) { // This point is not used because it's too close to the previous point. if (DEBUG_GEO_FULL) { AKLOGI("p0: size = %zd, x = %d, y = %d, lx = %d, ly = %d, dist = %d, " @@ -473,28 +475,6 @@ bool ProximityInfoState::pushTouchPoint(const int inputIndex, const int nodeChar / LAST_POINT_SKIP_DISTANCE_SCALE); } return popped; - } else if (lastPointsDistance * LAST_AND_NOT_NEAREST_POINT_SKIP_DISTANCE_SCALE - < mProximityInfo->getMostCommonKeyWidth()) { - int nearestChar = 0; - float nearestCharDistance = mMaxPointToKeyLength; - for (NearKeysDistanceMap::const_iterator it = currentNearKeysDistances->begin(); - it != currentNearKeysDistances->end(); ++it) { - if (nearestCharDistance > it->second) { - nearestChar = it->first; - nearestCharDistance = it->second; - } - } - NearKeysDistanceMap::const_iterator itPP = - prevNearKeysDistances->find(nearestChar); - if (itPP != prevNearKeysDistances->end() && nearestCharDistance > itPP->second) { - // The nearest key of the penultimate point is same as the nearest key of the - // last point. So, we don't need to use the last point. - if (DEBUG_GEO_FULL) { - AKLOGI("p1: char = %c, minDist = %f, prevNear key minDist = %f", - nearestChar, itPP->second, nearestCharDistance); - } - return popped; - } } } } @@ -550,11 +530,16 @@ int ProximityInfoState::getDuration(const int index) const { } float ProximityInfoState::getPointToKeyLength(const int inputIndex, const int codePoint) const { + const int keyId = mProximityInfo->getKeyIndexOf(codePoint); + if (keyId != NOT_AN_INDEX) { + const int index = inputIndex * mProximityInfo->getKeyCount() + keyId; + return min(mDistanceCache[index], mMaxPointToKeyLength); + } if (isSkippableChar(codePoint)) { return 0.0f; } - const int keyId = mProximityInfo->getKeyIndexOf(codePoint); - return getPointToKeyByIdLength(inputIndex, keyId); + // If the char is not a key on the keyboard then return the max length. + return MAX_POINT_TO_KEY_LENGTH; } float ProximityInfoState::getPointToKeyByIdLength(const int inputIndex, const int keyId) const { @@ -587,8 +572,9 @@ int32_t ProximityInfoState::getAllPossibleChars( return filterSize; } int newFilterSize = filterSize; - for (int j = 0; j < mProximityInfo->getKeyCount(); ++j) { - if (mNearKeysVector[index].test(j)) { + const int keyCount = mProximityInfo->getKeyCount(); + for (int j = 0; j < keyCount; ++j) { + if (mSearchKeysVector[index].test(j)) { const int32_t keyCodePoint = mProximityInfo->getCodePointOf(j); bool insert = true; // TODO: Avoid linear search @@ -606,6 +592,12 @@ int32_t ProximityInfoState::getAllPossibleChars( return newFilterSize; } +bool ProximityInfoState::isKeyInSerchKeysAfterIndex(const int index, const int keyId) const { + ASSERT(keyId >= 0); + ASSERT(index >= 0 && index < mInputSize); + return mSearchKeysVector[index].test(keyId); +} + void ProximityInfoState::popInputData() { mInputXs.pop_back(); mInputYs.pop_back(); @@ -614,18 +606,26 @@ void ProximityInfoState::popInputData() { mInputIndice.pop_back(); } +float ProximityInfoState::getDirection(const int index0, const int index1) const { + if (index0 < 0 || index0 > mInputSize - 1) { + return 0.0f; + } + if (index1 < 0 || index1 > mInputSize - 1) { + return 0.0f; + } + const int x1 = mInputXs[index0]; + const int y1 = mInputYs[index0]; + const int x2 = mInputXs[index1]; + const int y2 = mInputYs[index1]; + return getAngle(x1, y1, x2, y2); +} + float ProximityInfoState::getPointAngle(const int index) const { if (index <= 0 || index >= mInputSize - 1) { return 0.0f; } - const int x = mInputXs[index]; - const int y = mInputYs[index]; - const int nextX = mInputXs[index + 1]; - const int nextY = mInputYs[index + 1]; - const int previousX = mInputXs[index - 1]; - const int previousY = mInputYs[index - 1]; - const float previousDirection = getAngle(previousX, previousY, x, y); - const float nextDirection = getAngle(x, y, nextX, nextY); + const float previousDirection = getDirection(index - 1, index); + const float nextDirection = getDirection(index, index + 1); const float directionDiff = getAngleDiff(previousDirection, nextDirection); return directionDiff; } @@ -641,190 +641,354 @@ float ProximityInfoState::getPointsAngle( if (index2 < 0 || index2 > mInputSize - 1) { return 0.0f; } - const int x0 = mInputXs[index0]; - const int y0 = mInputYs[index0]; - const int x1 = mInputXs[index1]; - const int y1 = mInputYs[index1]; - const int x2 = mInputXs[index2]; - const int y2 = mInputYs[index2]; - const float previousDirection = getAngle(x0, y0, x1, y1); - const float nextDirection = getAngle(x1, y1, x2, y2); - const float directionDiff = getAngleDiff(previousDirection, nextDirection); - return directionDiff; + const float previousDirection = getDirection(index0, index1); + const float nextDirection = getDirection(index1, index2); + return getAngleDiff(previousDirection, nextDirection); +} + +float ProximityInfoState::getLineToKeyDistance( + const int from, const int to, const int keyId, const bool extend) const { + if (from < 0 || from > mInputSize - 1) { + return 0.0f; + } + if (to < 0 || to > mInputSize - 1) { + return 0.0f; + } + const int x0 = mInputXs[from]; + const int y0 = mInputYs[from]; + const int x1 = mInputXs[to]; + const int y1 = mInputYs[to]; + + const int keyX = mProximityInfo->getKeyCenterXOfKeyIdG(keyId); + const int keyY = mProximityInfo->getKeyCenterYOfKeyIdG(keyId); + + return pointToLineSegSquaredDistanceFloat(keyX, keyY, x0, y0, x1, y1, extend); } // Updates probabilities of aligning to some keys and skipping. // Word suggestion should be based on this probabilities. -void ProximityInfoState::updateAlignPointProbabilities() { - static const float MIN_PROBABILITY = 0.00001f; +void ProximityInfoState::updateAlignPointProbabilities(const int start) { + static const float MIN_PROBABILITY = 0.000001f; + static const float MAX_SKIP_PROBABILITY = 0.95f; static const float SKIP_FIRST_POINT_PROBABILITY = 0.01f; static const float SKIP_LAST_POINT_PROBABILITY = 0.1f; - static const float ANGLE_RATE = 0.8f; - static const float DEEP_CORNER_ANGLE_THRESHOLD = M_PI_F * 0.5f; - static const float SKIP_DEEP_CORNER_PROBABILITY = 0.3f; - static const float CORNER_ANGLE_THRESHOLD = M_PI_F * 35.0f / 180.0f; + static const float MIN_SPEED_RATE_FOR_SKIP_PROBABILITY = 0.15f; + static const float SPEED_WEIGHT_FOR_SKIP_PROBABILITY = 0.9f; + static const float SLOW_STRAIGHT_WEIGHT_FOR_SKIP_PROBABILITY = 0.6f; + static const float NEAREST_DISTANCE_WEIGHT = 0.5f; + static const float NEAREST_DISTANCE_BIAS = 0.5f; + static const float NEAREST_DISTANCE_WEIGHT_FOR_LAST = 0.6f; + static const float NEAREST_DISTANCE_BIAS_FOR_LAST = 0.4f; + + static const float ANGLE_WEIGHT = 0.90f; + static const float DEEP_CORNER_ANGLE_THRESHOLD = M_PI_F * 60.0f / 180.0f; + static const float SKIP_DEEP_CORNER_PROBABILITY = 0.1f; + static const float CORNER_ANGLE_THRESHOLD = M_PI_F * 30.0f / 180.0f; static const float STRAIGHT_ANGLE_THRESHOLD = M_PI_F * 15.0f / 180.0f; - static const float SKIP_CORNER_PROBABILITY = 0.5f; - static const float SLOW_STRAIGHT_WEIGHT = 0.8f; + static const float SKIP_CORNER_PROBABILITY = 0.4f; + static const float SPEED_MARGIN = 0.1f; static const float CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION = 0.0f; + const int keyCount = mProximityInfo->getKeyCount(); mCharProbabilities.resize(mInputSize); // Calculates probabilities of using a point as a correlated point with the character // for each point. - for (int i = 0; i < mInputSize; ++i) { - // First, calculates skip probability. Starts form 100%. + for (int i = start; i < mInputSize; ++i) { + mCharProbabilities[i].clear(); + // First, calculates skip probability. Starts form MIN_SKIP_PROBABILITY. // Note that all values that are multiplied to this probability should be in [0.0, 1.0]; - float skipProbability = 1.0f; - const float speed = getRelativeSpeed(i); + float skipProbability = MAX_SKIP_PROBABILITY; + + const float currentAngle = getPointAngle(i); + const float relativeSpeed = getRelativeSpeed(i); + + float nearestKeyDistance = static_cast<float>(MAX_POINT_TO_KEY_LENGTH); + for (int j = 0; j < keyCount; ++j) { + if (mNearKeysVector[i].test(j)) { + const float distance = getPointToKeyByIdLength(i, j); + if (distance < nearestKeyDistance) { + nearestKeyDistance = distance; + } + } + } - // Adjusts skip probability by a rate depending on speed. - skipProbability *= min(1.0f, speed); if (i == 0) { + skipProbability *= min(1.0f, nearestKeyDistance * NEAREST_DISTANCE_WEIGHT + + NEAREST_DISTANCE_BIAS); + // Promote the first point skipProbability *= SKIP_FIRST_POINT_PROBABILITY; } else if (i == mInputSize - 1) { + skipProbability *= min(1.0f, nearestKeyDistance * NEAREST_DISTANCE_WEIGHT_FOR_LAST + + NEAREST_DISTANCE_BIAS_FOR_LAST); + // Promote the last point skipProbability *= SKIP_LAST_POINT_PROBABILITY; } else { - const float currentAngle = getPointAngle(i); + // If the current speed is relatively slower than adjacent keys, we promote this point. + if (getRelativeSpeed(i - 1) - SPEED_MARGIN > relativeSpeed + && relativeSpeed < getRelativeSpeed(i + 1) - SPEED_MARGIN) { + if (currentAngle < CORNER_ANGLE_THRESHOLD) { + skipProbability *= min(1.0f, relativeSpeed + * SLOW_STRAIGHT_WEIGHT_FOR_SKIP_PROBABILITY); + } else { + // If the angle is small enough, we promote this point more. (e.g. pit vs put) + skipProbability *= min(1.0f, relativeSpeed * SPEED_WEIGHT_FOR_SKIP_PROBABILITY + + MIN_SPEED_RATE_FOR_SKIP_PROBABILITY); + } + } + + skipProbability *= min(1.0f, relativeSpeed * nearestKeyDistance * + NEAREST_DISTANCE_WEIGHT + NEAREST_DISTANCE_BIAS); // Adjusts skip probability by a rate depending on angle. // ANGLE_RATE of skipProbability is adjusted by current angle. - skipProbability *= max((M_PI_F - currentAngle) / M_PI_F, 0.0f) * ANGLE_RATE + - (1.0f - ANGLE_RATE); + skipProbability *= (M_PI_F - currentAngle) / M_PI_F * ANGLE_WEIGHT + + (1.0f - ANGLE_WEIGHT); if (currentAngle > DEEP_CORNER_ANGLE_THRESHOLD) { skipProbability *= SKIP_DEEP_CORNER_PROBABILITY; } - const float prevAngle = getPointsAngle(i, i - 1, i - 2); - if (prevAngle < STRAIGHT_ANGLE_THRESHOLD && currentAngle > CORNER_ANGLE_THRESHOLD) { + // We assume the angle of this point is the angle for point[i], point[i - 2] + // and point[i - 3]. The reason why we don't use the angle for point[i], point[i - 1] + // and point[i - 2] is this angle can be more affected by the noise. + const float prevAngle = getPointsAngle(i, i - 2, i - 3); + if (i >= 3 && prevAngle < STRAIGHT_ANGLE_THRESHOLD + && currentAngle > CORNER_ANGLE_THRESHOLD) { skipProbability *= SKIP_CORNER_PROBABILITY; } - if (currentAngle < STRAIGHT_ANGLE_THRESHOLD) { - // Adjusts skip probability by speed. - skipProbability *= min(1.0f, speed * SLOW_STRAIGHT_WEIGHT); - } } - // probabilities must be in [0.0, 1.0]; + // probabilities must be in [0.0, MAX_SKIP_PROBABILITY]; ASSERT(skipProbability >= 0.0f); - ASSERT(skipProbability <= 1.0f); - + ASSERT(skipProbability <= MAX_SKIP_PROBABILITY); mCharProbabilities[i][NOT_AN_INDEX] = skipProbability; + // Second, calculates key probabilities by dividing the rest probability // (1.0f - skipProbability). const float inputCharProbability = 1.0f - skipProbability; - // Summing up probability densities of all near keys. - float sumOfProbabilityDensityOfNearKeys = 0.0f; - const float sigma = speed; + + // TODO: The variance is critical for accuracy; thus, adjusting these parameter by machine + // learning or something would be efficient. + static const float SPEEDxANGLE_WEIGHT_FOR_STANDARD_DIVIATION = 0.3f; + static const float MAX_SPEEDxANGLE_RATE_FOR_STANDERD_DIVIATION = 0.25f; + static const float SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DIVIATION = 0.5f; + static const float MAX_SPEEDxNEAREST_RATE_FOR_STANDERD_DIVIATION = 0.15f; + static const float MIN_STANDERD_DIVIATION = 0.37f; + + const float speedxAngleRate = min(relativeSpeed * currentAngle / M_PI_F + * SPEEDxANGLE_WEIGHT_FOR_STANDARD_DIVIATION, + MAX_SPEEDxANGLE_RATE_FOR_STANDERD_DIVIATION); + const float speedxNearestKeyDistanceRate = min(relativeSpeed * nearestKeyDistance + * SPEEDxNEAREST_WEIGHT_FOR_STANDARD_DIVIATION, + MAX_SPEEDxNEAREST_RATE_FOR_STANDERD_DIVIATION); + const float sigma = speedxAngleRate + speedxNearestKeyDistanceRate + MIN_STANDERD_DIVIATION; + NormalDistribution distribution(CENTER_VALUE_OF_NORMALIZED_DISTRIBUTION, sigma); - for (int j = 0; j < mProximityInfo->getKeyCount(); ++j) { + static const float PREV_DISTANCE_WEIGHT = 0.5f; + static const float NEXT_DISTANCE_WEIGHT = 0.6f; + // Summing up probability densities of all near keys. + float sumOfProbabilityDensities = 0.0f; + for (int j = 0; j < keyCount; ++j) { if (mNearKeysVector[i].test(j)) { - const float distance = sqrtf(getPointToKeyByIdLength(i, j)); - sumOfProbabilityDensityOfNearKeys += distribution.getProbabilityDensity(distance); + float distance = sqrtf(getPointToKeyByIdLength(i, j)); + if (i == 0 && i != mInputSize - 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(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 * NEXT_DISTANCE_WEIGHT) + / (1.0f + NEXT_DISTANCE_WEIGHT); + } + } else if (i != 0 && i == mInputSize - 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(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 * PREV_DISTANCE_WEIGHT) + / (1.0f + 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); } } - for (int j = 0; j < mProximityInfo->getKeyCount(); ++j) { + + // Split the probability of an input point to keys that are close to the input point. + for (int j = 0; j < keyCount; ++j) { if (mNearKeysVector[i].test(j)) { - const float distance = sqrtf(getPointToKeyByIdLength(i, j)); - const float probabilityDessity = distribution.getProbabilityDensity(distance); - // inputCharProbability divided to the probability for each near key. - const float probability = inputCharProbability * probabilityDessity - / sumOfProbabilityDensityOfNearKeys; - if (probability > MIN_PROBABILITY) { - mCharProbabilities[i][j] = probability; + float distance = sqrtf(getPointToKeyByIdLength(i, j)); + if (i == 0 && i != mInputSize - 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(i + 1, j)); + if (prevDistance < distance) { + distance = (distance + prevDistance * NEXT_DISTANCE_WEIGHT) + / (1.0f + NEXT_DISTANCE_WEIGHT); + } + } else if (i != 0 && i == mInputSize - 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(i - 1, j)); + if (prevDistance < distance) { + distance = (distance + prevDistance * PREV_DISTANCE_WEIGHT) + / (1.0f + PREV_DISTANCE_WEIGHT); + } } + const float probabilityDensity = distribution.getProbabilityDensity(distance); + const float probability = inputCharProbability * probabilityDensity + / sumOfProbabilityDensities; + mCharProbabilities[i][j] = probability; } } } + + if (DEBUG_POINTS_PROBABILITY) { + for (int i = 0; i < mInputSize; ++i) { + std::stringstream sstream; + sstream << i << ", "; + sstream << "("<< mInputXs[i] << ", "; + sstream << ", "<< mInputYs[i] << "), "; + sstream << "Speed: "<< getRelativeSpeed(i) << ", "; + sstream << "Angle: "<< getPointAngle(i) << ", \n"; + + for (hash_map_compat<int, float>::iterator it = mCharProbabilities[i].begin(); + it != mCharProbabilities[i].end(); ++it) { + if (it->first == NOT_AN_INDEX) { + sstream << it->first + << "(skip):" + << it->second + << "\n"; + } else { + sstream << it->first + << "(" + << static_cast<char>(mProximityInfo->getCodePointOf(it->first)) + << "):" + << it->second + << "\n"; + } + } + AKLOGI("%s", sstream.str().c_str()); + } + } + // Decrease key probabilities of points which don't have the highest probability of that key // among nearby points. Probabilities of the first point and the last point are not suppressed. - for (int i = 1; i < mInputSize - 1; ++i) { - // forward + for (int i = max(start, 1); i < mInputSize; ++i) { for (int j = i + 1; j < mInputSize; ++j) { - if (suppressCharProbabilities(i, j)) { + if (!suppressCharProbabilities(i, j)) { break; } } - // backward - for (int j = i - 1; j >= 0; --j) { - if (suppressCharProbabilities(i, j)) { + for (int j = i - 1; j >= max(start, 0); --j) { + if (!suppressCharProbabilities(i, j)) { break; } } } - if (DEBUG_POINTS_PROBABILITY) { - for (int i = 0; i < mInputSize; ++i) { - std::stringstream sstream; - sstream << i << ", "; - for (hash_map_compat<int, float>::iterator it = mCharProbabilities[i].begin(); - it != mCharProbabilities[i].end(); ++it) { - sstream << it->first - << "(" - << static_cast<char>(mProximityInfo->getCodePointOf(it->first)) - << "):" - << it->second - << ", "; + // Converting from raw probabilities to log probabilities to calculate spatial distance. + for (int i = start; i < mInputSize; ++i) { + for (int j = 0; j < keyCount; ++j) { + hash_map_compat<int, float>::iterator it = mCharProbabilities[i].find(j); + if (it == mCharProbabilities[i].end()){ + mNearKeysVector[i].reset(j); + } else if(it->second < MIN_PROBABILITY) { + // Erases from near keys vector because it has very low probability. + mNearKeysVector[i].reset(j); + mCharProbabilities[i].erase(j); + } else { + it->second = -logf(it->second); } - AKLOGI("%s", sstream.str().c_str()); } + mCharProbabilities[i][NOT_AN_INDEX] = -logf(mCharProbabilities[i][NOT_AN_INDEX]); } } -// Decreases char probabilities of index0 by checking probabilities of a near point (index1). +// Decreases char probabilities of index0 by checking probabilities of a near point (index1) and +// increases char probabilities of index1 by checking probabilities of index0. bool ProximityInfoState::suppressCharProbabilities(const int index0, const int index1) { ASSERT(0 <= index0 && index0 < mInputSize); ASSERT(0 <= index1 && index1 < mInputSize); + static const float SUPPRESSION_LENGTH_WEIGHT = 1.5f; + static const float MIN_SUPPRESSION_RATE = 0.1f; + static const float SUPPRESSION_WEIGHT = 0.5f; + static const float SUPPRESSION_WEIGHT_FOR_PROBABILITY_GAIN = 0.1f; + static const float SKIP_PROBABALITY_WEIGHT_FOR_PROBABILITY_GAIN = 0.3f; + const float keyWidthFloat = static_cast<float>(mProximityInfo->getMostCommonKeyWidth()); const float diff = fabsf(static_cast<float>(mLengthCache[index0] - mLengthCache[index1])); if (diff > keyWidthFloat * SUPPRESSION_LENGTH_WEIGHT) { return false; } - // Summing up decreased amount of probabilities from 0%. - float sumOfAdjustedProbabilities = 0.0f; - const float suppressionRate = diff / keyWidthFloat / SUPPRESSION_LENGTH_WEIGHT; + const float suppressionRate = MIN_SUPPRESSION_RATE + + diff / keyWidthFloat / SUPPRESSION_LENGTH_WEIGHT * SUPPRESSION_WEIGHT; for (hash_map_compat<int, float>::iterator it = mCharProbabilities[index0].begin(); it != mCharProbabilities[index0].end(); ++it) { - hash_map_compat<int, float>::const_iterator it2 = - mCharProbabilities[index1].find(it->first); + hash_map_compat<int, float>::iterator it2 = mCharProbabilities[index1].find(it->first); if (it2 != mCharProbabilities[index1].end() && it->second < it2->second) { const float newProbability = it->second * suppressionRate; - sumOfAdjustedProbabilities += it->second - newProbability; + const float suppression = it->second - newProbability; it->second = newProbability; + // mCharProbabilities[index0][NOT_AN_INDEX] is the probability of skipping this point. + mCharProbabilities[index0][NOT_AN_INDEX] += suppression; + + // Add the probability of the same key nearby index1 + const float probabilityGain = min(suppression * SUPPRESSION_WEIGHT_FOR_PROBABILITY_GAIN, + mCharProbabilities[index1][NOT_AN_INDEX] + * SKIP_PROBABALITY_WEIGHT_FOR_PROBABILITY_GAIN); + it2->second += probabilityGain; + mCharProbabilities[index1][NOT_AN_INDEX] -= probabilityGain; } } - // All decreased amount of probabilities are added to the probability of skipping. - mCharProbabilities[index0][NOT_AN_INDEX] += sumOfAdjustedProbabilities; return true; } // Get a word that is detected by tracing highest probability sequence into charBuf and returns // probability of generating the word. float ProximityInfoState::getHighestProbabilitySequence(uint16_t *const charBuf) const { - int buf[mInputSize]; - // Maximum probabilities of each point are multiplied to 100%. - float probability = 1.0f; + static const float LOG_PROBABILITY_MARGIN = 0.2f; + int index = 0; + float sumLogProbability = 0.0f; // TODO: Current implementation is greedy algorithm. DP would be efficient for many cases. - for (int i = 0; i < mInputSize; ++i) { - float maxProbability = 0.0f; + for (int i = 0; i < mInputSize && index < MAX_WORD_LENGTH_INTERNAL - 1; ++i) { + float minLogProbability = static_cast<float>(MAX_POINT_TO_KEY_LENGTH); + int character = NOT_AN_INDEX; for (hash_map_compat<int, float>::const_iterator it = mCharProbabilities[i].begin(); it != mCharProbabilities[i].end(); ++it) { - if (it->second > maxProbability) { - maxProbability = it->second; - buf[i] = it->first; + const float logProbability = (it->first != NOT_AN_INDEX) + ? it->second + LOG_PROBABILITY_MARGIN : it->second; + if (logProbability < minLogProbability) { + minLogProbability = logProbability; + character = it->first; } } - probability *= maxProbability; - } - int index = 0; - for (int i = 0; i < mInputSize && index < MAX_WORD_LENGTH_INTERNAL - 1; ++i) { - if (buf[i] != NOT_AN_INDEX) { - charBuf[index] = mProximityInfo->getCodePointOf(buf[i]); + if (character != NOT_AN_INDEX) { + charBuf[index] = mProximityInfo->getCodePointOf(character); index++; } + sumLogProbability += minLogProbability; } charBuf[index] = '\0'; - return probability; + return sumLogProbability; +} + +// Returns a probability of mapping index to keyIndex. +float ProximityInfoState::getProbability(const int index, const int keyIndex) const { + ASSERT(0 <= index && index < mInputSize); + hash_map_compat<int, float>::const_iterator it = mCharProbabilities[index].find(keyIndex); + if (it != mCharProbabilities[index].end()) { + return it->second; + } + return static_cast<float>(MAX_POINT_TO_KEY_LENGTH); } } // namespace latinime |