Doodhout/match gesture path with vector direction too

[doodhout]

This is a new feature to improve matching word paths with user gesture paths.

High-level explanation

Current way this method works

Currently the method calculateDistanceBetweenUserPathAndWord() only goes over each user gesture path corner (i.e. coordinate) and calculates the distance between it and the current word path corner, or the next word path corner if that one is closer.

Because the user gesture path is very "verbose", i.e. a lot of unnecessary corners are in the path, it's logical to iterate over the gesture path corners and try matching the word path corners via a ratchet-system.

Problem with how this method currently works

The problem is that, unless the next word path corner is closer to the gesture path corner, it keeps iterating over the gesture path corners and comparing it with the same word path corner.

This causes a false-close-match whenever the gesture path contains multiple corners close to the actual word path corner.

For example: the word paths for the words protector and profile hover around the same clusters of letters on the keyboard in roughly the same order, thus they will both match each other's user gesture path quite closely.

Solution

The idea is to not only match path corners based on their relative distance, but also based on the vector directions: when you take the current corner and the previous corner for the user gesture path, you will be able to calculate the vector direction. Do the same for the word path corners and you will have two vectors for which you can compare direction.

Users might not be very accurate at hitting the precise middle of a key while gesturing, but the direction of the movements should be almost perfectly aligned with the theoretical ideal path over the middle of each correct key, i.e. the word path.

Practical implementation of solution

The vector direction is used to calculate a penalty factor for the distance that was already being calculated.

The penalty factor is calculated like this: 1.0 + DIRECTION_PENALTY_FACTOR × (1 - cosine of the corner between the two vectors)

• Cosine for same direction (i.e. corner of 0°) = 1
• Cosine for perpendicular direction (i.e. corner of 90°) = 0
• Cosine for opposite direction (i.e. corner of 180°) = -1

DIRECTION_PENALTY_FACTOR is currently fixed to a value of 1.0, but could be modified if that proves useful during testing.

This gives the following penalty factors:

• for same direction (0°) = 1
• for perpendicular direction (90°) = 2
• for opposite direction (180°) = 3

That means two corners that are close to each other, but whose vector goes the opposite way, have their distance multiplied by 3, to try and avoid these kind of matches by increasing their "distance".

Test coverage

Happy path, unhappy path and edge cases are covered by unit-tests added to GestureTypingDetectorTest. Is this the best place to put those tests?

I have also built my own AnySoftKeyboard APK to test on my phone and so far gesture typing seems to be working fine and (I think) noticeably more accurate than before this change. I will continue testing this in real-life to gather more evidence.

Feedback

Do you have any questions? Remarks? Other feedback?

And yes, I typed this whole wall of text all by myself! :-D

Thanks for reviewing this.

[menny]

this is beautiful! That's a very good observation. Have you experiment with different values of penalty (for directionPenaltyMultiplier = 1.0 + DIRECTION_PENALTY_FACTOR * (1.0 - cosAngle);) - for example, adding a factor here to increase or decrease the penalty.

I'll test this and review. Thank you so much.

[codecov[bot]]

Codecov Report

:x: Patch coverage is 98.14815% with 1 line in your changes missing coverage. Please review. :white_check_mark: Project coverage is 75.81%. Comparing base (87bb4be) to head (caf91b0).

Files with missing lines	Patch %	Lines
...tkeyboard/gesturetyping/GestureTypingDetector.java	98.14%	0 Missing and 1 partial :warning:

Additional details and impacted files

@@             Coverage Diff              @@
##               main    #4554      +/-   ##
============================================
+ Coverage     75.74%   75.81%   +0.07%     
- Complexity     3719     3731      +12     
============================================
  Files           289      289              
  Lines         18325    18367      +42     
  Branches       2315     2321       +6     
============================================
+ Hits          13880    13925      +45     
+ Misses         3584     3581       -3     
  Partials        861      861              

Flag	Coverage Δ
android-unit-test	75.50% <98.14%> (+0.08%)	:arrow_up:
tooling-unit-test	78.72% <ø> (ø)

Flags with carried forward coverage won't be shown. Click here to find out more.

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
• :package: JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

[kurahaupo]

Question: do the vector chains take timing into account? (Either by sampling at a consistent rate, or by recording time as a component of each vector, or by any other means?)

[doodhout]

@menny: Thanks!

Have you experiment with different values of penalty (for directionPenaltyMultiplier = 1.0 + DIRECTION_PENALTY_FACTOR * (1.0 - cosAngle);) - for example, adding a factor here to increase or decrease the penalty.

I have tested with the current formula, i.e. 1.0 + DIRECTION_PENALTY_FACTOR × (1 - cos(arcdiff)).

I have also tried the following: 0.0 + DIRECTION_PENALTY_FACTOR × (1 - cos(arcdiff)) where the factor reaches 0 (zero) for a perfect direction match and reaches 2 for a 180° difference -> so instead of only penalising direction differences, it also rewards vectors having a similar direction, since a perfect direction match will give a factor of zero thus ignoring the distance for that corner, while an opposite direction would double the distance.

It worked ok, but I found that this gives very low cumulative (i.e. total) distances, causing the word frequency to have a relative much bigger weight in the end result, messing up the order of matches, so I abandoned this idea instead of trying to tweak the word frequency factor.

@kurahaupo: No, I've re-used the trimmed gesture path as it is provided by the original code. But that might be a good idea, yes. I will try and see if this data is available, and if so, think about how that data can be used to further improve gesture path matching.