proximity_info_state.cpp revision 952ec4977d772607140773ae7d8868f86a7e0097
1/* 2 * Copyright (C) 2012 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#include <cstring> // for memset() 18#include <stdint.h> 19 20#define LOG_TAG "LatinIME: proximity_info_state.cpp" 21 22#include "defines.h" 23#include "geometry_utils.h" 24#include "proximity_info.h" 25#include "proximity_info_state.h" 26 27namespace latinime { 28void ProximityInfoState::initInputParams(const int pointerId, const float maxPointToKeyLength, 29 const ProximityInfo *proximityInfo, const int32_t *const inputCodes, const int inputSize, 30 const int *const xCoordinates, const int *const yCoordinates, const int *const times, 31 const int *const pointerIds, const bool isGeometric) { 32 33 if (isGeometric) { 34 mIsContinuationPossible = checkAndReturnIsContinuationPossible( 35 inputSize, xCoordinates, yCoordinates, times); 36 } else { 37 mIsContinuationPossible = false; 38 } 39 40 mProximityInfo = proximityInfo; 41 mHasTouchPositionCorrectionData = proximityInfo->hasTouchPositionCorrectionData(); 42 mMostCommonKeyWidthSquare = proximityInfo->getMostCommonKeyWidthSquare(); 43 mLocaleStr = proximityInfo->getLocaleStr(); 44 mKeyCount = proximityInfo->getKeyCount(); 45 mCellHeight = proximityInfo->getCellHeight(); 46 mCellWidth = proximityInfo->getCellWidth(); 47 mGridHeight = proximityInfo->getGridWidth(); 48 mGridWidth = proximityInfo->getGridHeight(); 49 50 memset(mInputCodes, 0, sizeof(mInputCodes)); 51 52 if (!isGeometric && pointerId == 0) { 53 // Initialize 54 // - mInputCodes 55 // - mNormalizedSquaredDistances 56 // TODO: Merge 57 for (int i = 0; i < inputSize; ++i) { 58 const int32_t primaryKey = inputCodes[i]; 59 const int x = xCoordinates[i]; 60 const int y = yCoordinates[i]; 61 int *proximities = &mInputCodes[i * MAX_PROXIMITY_CHARS_SIZE_INTERNAL]; 62 mProximityInfo->calculateNearbyKeyCodes(x, y, primaryKey, proximities); 63 } 64 65 if (DEBUG_PROXIMITY_CHARS) { 66 for (int i = 0; i < inputSize; ++i) { 67 AKLOGI("---"); 68 for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE_INTERNAL; ++j) { 69 int icc = mInputCodes[i * MAX_PROXIMITY_CHARS_SIZE_INTERNAL + j]; 70 int icfjc = inputCodes[i * MAX_PROXIMITY_CHARS_SIZE_INTERNAL + j]; 71 icc += 0; 72 icfjc += 0; 73 AKLOGI("--- (%d)%c,%c", i, icc, icfjc); AKLOGI("--- A<%d>,B<%d>", icc, icfjc); 74 } 75 } 76 } 77 } 78 79 /////////////////////// 80 // Setup touch points 81 int pushTouchPointStartIndex = 0; 82 int lastSavedInputSize = 0; 83 mMaxPointToKeyLength = maxPointToKeyLength; 84 if (mIsContinuationPossible && mInputIndice.size() > 1) { 85 // Just update difference. 86 // Two points prior is never skipped. Thus, we pop 2 input point data here. 87 pushTouchPointStartIndex = mInputIndice[mInputIndice.size() - 2]; 88 popInputData(); 89 popInputData(); 90 lastSavedInputSize = mInputXs.size(); 91 } else { 92 // Clear all data. 93 mInputXs.clear(); 94 mInputYs.clear(); 95 mTimes.clear(); 96 mInputIndice.clear(); 97 mLengthCache.clear(); 98 mDistanceCache.clear(); 99 mNearKeysVector.clear(); 100 } 101 mInputSize = 0; 102 103 if (xCoordinates && yCoordinates) { 104 const bool proximityOnly = !isGeometric && (xCoordinates[0] < 0 || yCoordinates[0] < 0); 105 int lastInputIndex = pushTouchPointStartIndex; 106 for (int i = lastInputIndex; i < inputSize; ++i) { 107 const int pid = pointerIds ? pointerIds[i] : 0; 108 if (pointerId == pid) { 109 lastInputIndex = i; 110 } 111 } 112 // Working space to save near keys distances for current, prev and prevprev input point. 113 NearKeysDistanceMap nearKeysDistances[3]; 114 // These pointers are swapped for each inputs points. 115 NearKeysDistanceMap *currentNearKeysDistances = &nearKeysDistances[0]; 116 NearKeysDistanceMap *prevNearKeysDistances = &nearKeysDistances[1]; 117 NearKeysDistanceMap *prevPrevNearKeysDistances = &nearKeysDistances[2]; 118 119 for (int i = pushTouchPointStartIndex; i <= lastInputIndex; ++i) { 120 // Assuming pointerId == 0 if pointerIds is null. 121 const int pid = pointerIds ? pointerIds[i] : 0; 122 if (pointerId == pid) { 123 const int c = isGeometric ? NOT_A_COORDINATE : getPrimaryCharAt(i); 124 const int x = proximityOnly ? NOT_A_COORDINATE : xCoordinates[i]; 125 const int y = proximityOnly ? NOT_A_COORDINATE : yCoordinates[i]; 126 const int time = times ? times[i] : -1; 127 if (pushTouchPoint(i, c, x, y, time, isGeometric /* do sampling */, 128 i == lastInputIndex, currentNearKeysDistances, prevNearKeysDistances, 129 prevPrevNearKeysDistances)) { 130 // Previous point information was popped. 131 NearKeysDistanceMap *tmp = prevNearKeysDistances; 132 prevNearKeysDistances = currentNearKeysDistances; 133 currentNearKeysDistances = tmp; 134 } else { 135 NearKeysDistanceMap *tmp = prevPrevNearKeysDistances; 136 prevPrevNearKeysDistances = prevNearKeysDistances; 137 prevNearKeysDistances = currentNearKeysDistances; 138 currentNearKeysDistances = tmp; 139 } 140 } 141 } 142 mInputSize = mInputXs.size(); 143 } 144 145 if (mInputSize > 0) { 146 const int keyCount = mProximityInfo->getKeyCount(); 147 mNearKeysVector.resize(mInputSize); 148 mDistanceCache.resize(mInputSize * keyCount); 149 for (int i = lastSavedInputSize; i < mInputSize; ++i) { 150 mNearKeysVector[i].reset(); 151 static const float NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD = 4.0f; 152 for (int k = 0; k < keyCount; ++k) { 153 const int index = i * keyCount + k; 154 const int x = mInputXs[i]; 155 const int y = mInputYs[i]; 156 const float normalizedSquaredDistance = 157 mProximityInfo->getNormalizedSquaredDistanceFromCenterFloat(k, x, y); 158 mDistanceCache[index] = normalizedSquaredDistance; 159 if (normalizedSquaredDistance < NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD) { 160 mNearKeysVector[i].set(k, 1); 161 } 162 } 163 } 164 165 static const float READ_FORWORD_LENGTH_SCALE = 0.95f; 166 const int readForwordLength = static_cast<int>( 167 hypotf(mProximityInfo->getKeyboardWidth(), mProximityInfo->getKeyboardHeight()) 168 * READ_FORWORD_LENGTH_SCALE); 169 for (int i = 0; i < mInputSize; ++i) { 170 for (int j = max(i + 1, lastSavedInputSize); j < mInputSize; ++j) { 171 if (mLengthCache[j] - mLengthCache[i] >= readForwordLength) { 172 break; 173 } 174 mNearKeysVector[i] |= mNearKeysVector[j]; 175 } 176 } 177 } 178 179 // end 180 /////////////////////// 181 182 memset(mNormalizedSquaredDistances, NOT_A_DISTANCE, sizeof(mNormalizedSquaredDistances)); 183 memset(mPrimaryInputWord, 0, sizeof(mPrimaryInputWord)); 184 mTouchPositionCorrectionEnabled = mInputSize > 0 && mHasTouchPositionCorrectionData 185 && xCoordinates && yCoordinates && !isGeometric; 186 if (!isGeometric && pointerId == 0) { 187 for (int i = 0; i < inputSize; ++i) { 188 mPrimaryInputWord[i] = getPrimaryCharAt(i); 189 } 190 191 for (int i = 0; i < mInputSize && mTouchPositionCorrectionEnabled; ++i) { 192 const int *proximityChars = getProximityCharsAt(i); 193 const int primaryKey = proximityChars[0]; 194 const int x = xCoordinates[i]; 195 const int y = yCoordinates[i]; 196 if (DEBUG_PROXIMITY_CHARS) { 197 int a = x + y + primaryKey; 198 a += 0; 199 AKLOGI("--- Primary = %c, x = %d, y = %d", primaryKey, x, y); 200 } 201 for (int j = 0; j < MAX_PROXIMITY_CHARS_SIZE_INTERNAL && proximityChars[j] > 0; ++j) { 202 const int currentChar = proximityChars[j]; 203 const float squaredDistance = 204 hasInputCoordinates() ? calculateNormalizedSquaredDistance( 205 mProximityInfo->getKeyIndexOf(currentChar), i) : 206 NOT_A_DISTANCE_FLOAT; 207 if (squaredDistance >= 0.0f) { 208 mNormalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE_INTERNAL + j] = 209 (int) (squaredDistance * NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR); 210 } else { 211 mNormalizedSquaredDistances[i * MAX_PROXIMITY_CHARS_SIZE_INTERNAL + j] = 212 (j == 0) ? EQUIVALENT_CHAR_WITHOUT_DISTANCE_INFO : 213 PROXIMITY_CHAR_WITHOUT_DISTANCE_INFO; 214 } 215 if (DEBUG_PROXIMITY_CHARS) { 216 AKLOGI("--- Proximity (%d) = %c", j, currentChar); 217 } 218 } 219 } 220 } 221 222 if (DEBUG_GEO_FULL) { 223 AKLOGI("ProximityState init finished: %d points out of %d", mInputSize, inputSize); 224 } 225} 226 227bool ProximityInfoState::checkAndReturnIsContinuationPossible(const int inputSize, 228 const int *const xCoordinates, const int *const yCoordinates, const int *const times) { 229 for (int i = 0; i < mInputSize; ++i) { 230 const int index = mInputIndice[i]; 231 if (index > inputSize || xCoordinates[index] != mInputXs[i] || 232 yCoordinates[index] != mInputYs[i] || times[index] != mTimes[i]) { 233 return false; 234 } 235 } 236 return true; 237} 238 239// Calculating point to key distance for all near keys and returning the distance between 240// the given point and the nearest key position. 241float ProximityInfoState::updateNearKeysDistances(const int x, const int y, 242 NearKeysDistanceMap *const currentNearKeysDistances) { 243 static const float NEAR_KEY_THRESHOLD = 4.0f; 244 245 currentNearKeysDistances->clear(); 246 const int keyCount = mProximityInfo->getKeyCount(); 247 float nearestKeyDistance = mMaxPointToKeyLength; 248 for (int k = 0; k < keyCount; ++k) { 249 const float dist = mProximityInfo->getNormalizedSquaredDistanceFromCenterFloat(k, x, y); 250 if (dist < NEAR_KEY_THRESHOLD) { 251 currentNearKeysDistances->insert(std::pair<int, float>(k, dist)); 252 } 253 if (nearestKeyDistance > dist) { 254 nearestKeyDistance = dist; 255 } 256 } 257 return nearestKeyDistance; 258} 259 260// Check if previous point is at local minimum position to near keys. 261bool ProximityInfoState::isPrevLocalMin(const NearKeysDistanceMap *const currentNearKeysDistances, 262 const NearKeysDistanceMap *const prevNearKeysDistances, 263 const NearKeysDistanceMap *const prevPrevNearKeysDistances) const { 264 static const float MARGIN = 0.01f; 265 266 for (NearKeysDistanceMap::const_iterator it = prevNearKeysDistances->begin(); 267 it != prevNearKeysDistances->end(); ++it) { 268 NearKeysDistanceMap::const_iterator itPP = prevPrevNearKeysDistances->find(it->first); 269 NearKeysDistanceMap::const_iterator itC = currentNearKeysDistances->find(it->first); 270 if ((itPP == prevPrevNearKeysDistances->end() || itPP->second > it->second + MARGIN) 271 && (itC == currentNearKeysDistances->end() || itC->second > it->second + MARGIN)) { 272 return true; 273 } 274 } 275 return false; 276} 277 278// Calculating a point score that indicates usefulness of the point. 279float ProximityInfoState::getPointScore( 280 const int x, const int y, const int time, const bool lastPoint, const float nearest, 281 const NearKeysDistanceMap *const currentNearKeysDistances, 282 const NearKeysDistanceMap *const prevNearKeysDistances, 283 const NearKeysDistanceMap *const prevPrevNearKeysDistances) const { 284 static const float BASE_SAMPLE_RATE_SCALE = 0.1f; 285 static const float SAVE_DISTANCE_SCALE = 20.0f; 286 static const float SAVE_DISTANCE_SCORE = 2.0f; 287 static const float SKIP_DISTANCE_SCALE = 2.5f; 288 static const float SKIP_DISTANCE_SCORE = -1.0f; 289 static const float CHECK_LOCALMIN_DISTANCE_THRESHOLD_SCALE = 4.0f; 290 static const float CHECK_LOCALMIN_DISTANCE_SCORE = -1.0f; 291 static const float STRAIGHT_ANGLE_THRESHOLD = M_PI_F / 36.0f; 292 static const float STRAIGHT_SKIP_DISTANCE_THRESHOLD_SCALE = 5.0f; 293 static const float STRAIGHT_SKIP_NEAREST_DISTANCE_THRESHOLD = 0.5f; 294 static const float STRAIGHT_SKIP_SCORE = -1.0f; 295 static const float CORNER_ANGLE_THRESHOLD = M_PI_F / 2.0f; 296 static const float CORNER_CHECK_DISTANCE_THRESHOLD_SCALE = 2.7f; 297 static const float CORNER_SCORE = 1.0f; 298 299 const std::size_t size = mInputXs.size(); 300 if (size <= 1) { 301 return 0; 302 } 303 const float baseSampleRate = mProximityInfo->getMostCommonKeyWidth() * BASE_SAMPLE_RATE_SCALE; 304 const float distNext = getDistanceFloat(x, y, mInputXs.back(), mInputYs.back()); 305 const float distPrev = getDistanceFloat(mInputXs.back(), mInputYs.back(), 306 mInputXs[size - 2], mInputYs[size - 2]); 307 float score = 0.0f; 308 309 // Sum of distances 310 if (distPrev + distNext > baseSampleRate * SAVE_DISTANCE_SCALE) { 311 score += SAVE_DISTANCE_SCORE; 312 } 313 // Distance 314 if (distPrev < baseSampleRate * SKIP_DISTANCE_SCALE) { 315 score += SKIP_DISTANCE_SCORE; 316 } 317 // Location 318 if (distPrev < baseSampleRate * CHECK_LOCALMIN_DISTANCE_THRESHOLD_SCALE) { 319 if (!isPrevLocalMin(currentNearKeysDistances, prevNearKeysDistances, 320 prevPrevNearKeysDistances)) { 321 score += CHECK_LOCALMIN_DISTANCE_SCORE; 322 } 323 } 324 // Angle 325 const float angle1 = getAngle(x, y, mInputXs.back(), mInputYs.back()); 326 const float angle2 = getAngle(mInputXs.back(), mInputYs.back(), 327 mInputXs[size - 2], mInputYs[size - 2]); 328 const float angleDiff = getAngleDiff(angle1, angle2); 329 // Skip straight 330 if (nearest > STRAIGHT_SKIP_NEAREST_DISTANCE_THRESHOLD 331 && distPrev < baseSampleRate * STRAIGHT_SKIP_DISTANCE_THRESHOLD_SCALE 332 && angleDiff < STRAIGHT_ANGLE_THRESHOLD) { 333 score += STRAIGHT_SKIP_SCORE; 334 } 335 // Save corner 336 if (distPrev > baseSampleRate * CORNER_CHECK_DISTANCE_THRESHOLD_SCALE 337 && angleDiff > CORNER_ANGLE_THRESHOLD) { 338 score += CORNER_SCORE; 339 } 340 return score; 341} 342 343// Sampling touch point and pushing information to vectors. 344// Returning if previous point is popped or not. 345bool ProximityInfoState::pushTouchPoint(const int inputIndex, const int nodeChar, int x, int y, 346 const int time, const bool sample, const bool isLastPoint, 347 NearKeysDistanceMap *const currentNearKeysDistances, 348 const NearKeysDistanceMap *const prevNearKeysDistances, 349 const NearKeysDistanceMap *const prevPrevNearKeysDistances) { 350 static const float LAST_POINT_SKIP_DISTANCE_SCALE = 0.25f; 351 352 size_t size = mInputXs.size(); 353 bool popped = false; 354 if (nodeChar < 0 && sample) { 355 const float nearest = updateNearKeysDistances(x, y, currentNearKeysDistances); 356 const float score = getPointScore(x, y, time, isLastPoint, nearest, 357 currentNearKeysDistances, prevNearKeysDistances, prevPrevNearKeysDistances); 358 if (score < 0) { 359 // Pop previous point because it would be useless. 360 popInputData(); 361 size = mInputXs.size(); 362 popped = true; 363 } else { 364 popped = false; 365 } 366 // Check if the last point should be skipped. 367 if (isLastPoint) { 368 if (size > 0 && getDistanceFloat(x, y, mInputXs.back(), mInputYs.back()) 369 < mProximityInfo->getMostCommonKeyWidth() * LAST_POINT_SKIP_DISTANCE_SCALE) { 370 return popped; 371 } else if (size > 1) { 372 int minChar = 0; 373 float minDist = mMaxPointToKeyLength; 374 for (NearKeysDistanceMap::const_iterator it = currentNearKeysDistances->begin(); 375 it != currentNearKeysDistances->end(); ++it) { 376 if (minDist > it->second) { 377 minChar = it->first; 378 minDist = it->second; 379 } 380 } 381 NearKeysDistanceMap::const_iterator itPP = 382 prevNearKeysDistances->find(minChar); 383 if (itPP != prevNearKeysDistances->end() && minDist > itPP->second) { 384 return popped; 385 } 386 } 387 } 388 } 389 390 if (nodeChar >= 0 && (x < 0 || y < 0)) { 391 const int keyId = mProximityInfo->getKeyIndexOf(nodeChar); 392 if (keyId >= 0) { 393 x = mProximityInfo->getKeyCenterXOfKeyIdG(keyId); 394 y = mProximityInfo->getKeyCenterYOfKeyIdG(keyId); 395 } 396 } 397 398 // Pushing point information. 399 if (size > 0) { 400 mLengthCache.push_back( 401 mLengthCache.back() + getDistanceInt(x, y, mInputXs.back(), mInputYs.back())); 402 } else { 403 mLengthCache.push_back(0); 404 } 405 mInputXs.push_back(x); 406 mInputYs.push_back(y); 407 mTimes.push_back(time); 408 mInputIndice.push_back(inputIndex); 409 if (DEBUG_GEO_FULL) { 410 AKLOGI("pushTouchPoint: x = %03d, y = %03d, time = %d, index = %d, popped ? %01d", 411 x, y, time, inputIndex, popped); 412 } 413 return popped; 414} 415 416float ProximityInfoState::calculateNormalizedSquaredDistance( 417 const int keyIndex, const int inputIndex) const { 418 if (keyIndex == NOT_AN_INDEX) { 419 return NOT_A_DISTANCE_FLOAT; 420 } 421 if (!mProximityInfo->hasSweetSpotData(keyIndex)) { 422 return NOT_A_DISTANCE_FLOAT; 423 } 424 if (NOT_A_COORDINATE == mInputXs[inputIndex]) { 425 return NOT_A_DISTANCE_FLOAT; 426 } 427 const float squaredDistance = calculateSquaredDistanceFromSweetSpotCenter( 428 keyIndex, inputIndex); 429 const float squaredRadius = square(mProximityInfo->getSweetSpotRadiiAt(keyIndex)); 430 return squaredDistance / squaredRadius; 431} 432 433int ProximityInfoState::getDuration(const int index) const { 434 if (mInputSize > 0 && index > 0 && index < mInputSize - 1) { 435 return mTimes[index + 1] - mTimes[index - 1]; 436 } 437 return 0; 438} 439 440float ProximityInfoState::getPointToKeyLength(const int inputIndex, const int codePoint, 441 const float scale) const { 442 const int keyId = mProximityInfo->getKeyIndexOf(codePoint); 443 if (keyId != NOT_AN_INDEX) { 444 const int index = inputIndex * mProximityInfo->getKeyCount() + keyId; 445 return min(mDistanceCache[index] * scale, mMaxPointToKeyLength); 446 } 447 // TODO: Do not hardcode here 448 // No penalty to ' and - 449 if (codePoint == '\'' || codePoint == '-') { 450 return 0; 451 } 452 // If the char is not a key on the keyboard then return the max length. 453 return MAX_POINT_TO_KEY_LENGTH; 454} 455 456int ProximityInfoState::getSpaceY() const { 457 const int keyId = mProximityInfo->getKeyIndexOf(' '); 458 return mProximityInfo->getKeyCenterYOfKeyIdG(keyId); 459} 460 461float ProximityInfoState::calculateSquaredDistanceFromSweetSpotCenter( 462 const int keyIndex, const int inputIndex) const { 463 const float sweetSpotCenterX = mProximityInfo->getSweetSpotCenterXAt(keyIndex); 464 const float sweetSpotCenterY = mProximityInfo->getSweetSpotCenterYAt(keyIndex); 465 const float inputX = static_cast<float>(mInputXs[inputIndex]); 466 const float inputY = static_cast<float>(mInputYs[inputIndex]); 467 return square(inputX - sweetSpotCenterX) + square(inputY - sweetSpotCenterY); 468} 469 470// Puts possible characters into filter and returns new filter size. 471int32_t ProximityInfoState::getAllPossibleChars( 472 const size_t index, int32_t *const filter, const int32_t filterSize) const { 473 if (index >= mInputXs.size()) { 474 return filterSize; 475 } 476 int i = filterSize; 477 for (int j = 0; j < mProximityInfo->getKeyCount(); ++j) { 478 if (mNearKeysVector[index].test(j)) { 479 const int32_t keyCodePoint = mProximityInfo->getCodePointOf(j); 480 bool insert = true; 481 // TODO: Avoid linear search 482 for (int k = 0; k < filterSize; ++k) { 483 if (filter[k] == keyCodePoint) { 484 insert = false; 485 break; 486 } 487 } 488 if (insert) { 489 filter[i++] = keyCodePoint; 490 } 491 } 492 } 493 return i; 494} 495 496float ProximityInfoState::getAveragePointDuration() const { 497 if (mInputSize == 0) { 498 return 0.0f; 499 } 500 return static_cast<float>(mTimes[mInputSize - 1] - mTimes[0]) / static_cast<float>(mInputSize); 501} 502 503void ProximityInfoState::popInputData() { 504 mInputXs.pop_back(); 505 mInputYs.pop_back(); 506 mTimes.pop_back(); 507 mLengthCache.pop_back(); 508 mInputIndice.pop_back(); 509} 510 511} // namespace latinime 512