Implement better jitter reduction

[danielzgtg]

This was split from https://github.com/linux-surface/intel-precise-touch/issues/4 as recommended. At least based on the comment there, this isn't implemented in iptsd yet.

The outcome is described at https://github.com/linux-surface/intel-precise-touch/issues/4#issuecomment-807622599 :

You can imagine it like the cursor is a hockey puck with no inertia, to which a rope of a fixed length is tied to your finger. The finger is imagined to be a fixed height above the puck, and the puck only moves when the rope is pulled taught. Shaking your hand a tiny bit will only move the puck once since the rope will become loose when you move your finger back, and scrolling in one direction will always move the puck just like a car pulling a trailer. Compared to the old friction algorithm, this one eliminates both the jitter and at the same time scrolls at a smooth 60 FPS

The algorithm is at https://github.com/danielzgtg/ipts-rust/blob/9d264ad1e629f8e17f96b5e44ac3dea28b7ec765/utils/src/pointers/mod.rs#L116-L137 :

            if min_dist > 256 {
                fn isqrt(num: i32) -> i32 {
                    let mut result = 3;
                    let mut square = 9;
                    while square < num {
                        result += 1;
                        square += result - 1;
                    }
                    result
                }

                let dx = pos.0 as i32 - old_pos.0 as i32;
                let dy = pos.1 as i32 - old_pos.1 as i32;
                let norm = isqrt((dx * dx) + (dy * dy));
                let dx_clip = (dx * 16) / norm;
                let dy_clip = (dy * 16) / norm;
                pos.0 = (pos.0 as i32 - dx_clip) as u32;
                pos.1 = (pos.1 as i32 - dy_clip) as u32;
            } else {
                pos = old_pos;
            }

Basically it doesn't move the cursor until the finger is sqrt(256)=16 pixels away. When it does, it moves the cursor along the displacement vector until it is 16 pixels away again.

This filtering algorithm is fast and numerically stable.

[bngo11]

@danielzgtg Hi, I was able to get your driver to work. The zoom worked where it would not snap back to previous position. But I found so other issues with it. During the zoom, the image would be shaky/jittery.

Occasionally it would register a different location. We have a login screen with a keypad, sometime pressing on the number one would have the key below it, in this case a 'clear' key, being pressed instead of the '1' key.

I went back to the iptsd driver and found the zoom would stay if I release one finger before releasing the other instead of snapping back to previous location.

We are using Xorg in our app.

[danielzgtg]

other issues with it

Can you post a video of the problems please?

It might be just that I need to change some constants to increase the noise reduction in the engine.

(The algorithm described here runs after the engine in my driver, and mathematically can only reduce shaking and will never increase it)

[bngo11]

I will try to get video of it. It might be a while, I have to figure out how to capture it.

[mklss]

Is there documentation on the driver (and where)? I'm not an experienced programmer, but willing to implement this feature if need be, because the twitching is headache inducing. The solution @danielzgtg suggests is probably the standard way to get rid of noise easily. I've implemented it, and it seems to work, but I have no idea what ev1, ev2, (Eigenvalues? of what?) and is_stable are meant to do, Nor do I understand what StabilityThreshold should be. (I thought it would be distance, but it's eigenvalues? And no fabs is used, so "direction" matters here?) Should a distance-based stability feature another config variable, PositionStabilityThreshold?

// In iptsd_finger_update_from_last
float dx = input->x - last.x; // This should probably be abs?
float dy = input->y - last.y;

// FIXME: Is the geometry even quadratic? Or is it stretched?
float position_stability_threshold = 10;
float sq_position_stability_threshold = position_stability_threshold * position_stability_threshold; // Cache to save superfluous recomputation
float sqdist = dx*dx + dy*dy + 1; // Make sure > 0, so we don't divide by zero later. (Actually, only needed if threshold is <<1)
bool pos_stable = sqdist < sq_position_stability_threshold;

if (pos_stable) {
    input->x = last.x;
    input->y = last.y;
} else {
    // Move in the direction, but just as much as necessary
    float dist = sqrt(sqdist);
    input->x = input->x - position_stability_threshold*(dx/dist);
    input->y = input->y - position_stability_threshold*(dy/dist);
}

Even though the implementation is just guesswork, it's a huge difference to have no twitching scroll and zoom.

[StollD]

There are two different versions of iptsd. The one in the master branch is the stable one that uses a very simple algorithm. Then we have the libqzed branch which uses a more complex algorithm developed by @qzed

The original issue came up in the context of getting touch to work on SP7. The changes for that were a bit complex and I only made them in the libqzed branch, because some refactoring there made everything easier (the data parsing and the calculations are more seperated than in master). So I am not sure if the master branch would show the same issues.

Also the issue appeared before finger tracking was implemented on the libqzed branch. No finger tracking would mean that if you put two fingers on the display to zoom, and then lifted the left one, the input handler would instead think you lifted the right one and move the left one across the entire display. This seemed to improve the behaviour on SP7, but I got a bit busy (and also a bit burnt out) and didnt manage to come back to this issue and check if its still neccessary.

What device are you on? If the master branch works for you, the libqzed branch should work too. Could you try that? Like I said, the algorithm there is completely different, so it might fix your issues already.

[qzed]

The solution @danielzgtg suggests is probably the standard way to get rid of noise easily. I've implemented it, and it seems to work, but I have no idea what ev1, ev2, (Eigenvalues? of what?) and is_stable are meant to do, Nor do I understand what StabilityThreshold should be. (I thought it would be distance, but it's eigenvalues? And no fabs is used, so "direction" matters here?)

Could you provide some link what you're referring to? Eigenvalues/eigenvectors could maybe refer to the touch area, which is essentially described by an ellipse.

Should a distance-based stability feature another config variable, PositionStabilityThreshold?

Config variables are always a good idea, IMHO.

// In iptsd_finger_update_from_last
float dx = input->x - last.x; // This should probably be abs?

I assume that's the algorithm posted by @danielzgtg implemented in C? To me it looks like that's correct. dx and dy are used in two places:

1. For computing the distance sqdist = dx*dx + dy*dy + 1, so there the sign doesn't matter.
2. For updating positions input->x = input->x - position_stability_threshold*(dx/dist) where the sign does actually matter. Taking fabs(dx) here would change the update direction, i.e. you'd always update only into one quarter because the abs() maps everything there.

// FIXME: Is the geometry even quadratic? Or is it stretched?

That's definitely a valid point. Non-square pixels will skew things if not taken care of properly.

All in all, as far as I can tell the algorithm you posted checks if the touch point has moved a certain distance. If it has not, the touch point is set to the old one, and if it has, it is set to the point on a circle around the old touch point with radius position_stability_threshold that is closest to the newest touch point. Which matches @danielzgtg's algorithm.

[mklss]

@StollD: I'm on an SP5 (2017). The libqzed also has the twitching. More importantly, it's really sluggish. (Really smooth movement, but very noticable delay of maybe even a second.) To clarify: The twitching I mean appears when you let your finger rest on the device, to pause movement, or do slow fine adjustments. Faster movements "covers" up these artefacts. I have not had any problem with finger tracking (but mostly use zoom/pinch as the only multi-finger gesture).

(I assume, the libqzed branch is meant as a successor? Not a testing/playground stuff like neural nets, etc.)

@qzed

Could you provide some link what you're referring to? Eigenvalues/eigenvectors could maybe refer to the touch area, which is essentially described by an ellipse.

That sound like an explanation. The only thing I know is that ev1 is referred to as the "larger eigenvalue" here: https://github.com/linux-surface/iptsd/blob/42a48e87fe79c91d8a94263fef65496678be4ff8/src/touch-processing.c#L158-L161

Should a distance-based stability feature another config variable, PositionStabilityThreshold?

Config variables are always a good idea, IMHO.

I will add one then.

I assume that's the algorithm posted by @danielzgtg implemented in C? To me it looks like that's correct. dx and dy are used in two places:

1. For computing the distance `sqdist = dx*dx + dy*dy + 1`, so there the sign doesn't matter.

2. For updating positions `input->x = input->x - position_stability_threshold*(dx/dist)` where the sign does actually matter. Taking `fabs(dx)` here would change the update direction, i.e. you'd always update only into one quarter because the `abs()` maps everything there.

Yes, the algorithm should be a (slightly adapted) C implementation of @danielzgtg suggestion. My reference to what I don't understand was ambiguous. I meant to refer to is input->is_stable and it's computation (which lacks fabs). See https://github.com/linux-surface/iptsd/blob/42a48e87fe79c91d8a94263fef65496678be4ff8/src/finger.c#L14-L18

// FIXME: Is the geometry even quadratic? Or is it stretched?

That's definitely a valid point. Non-square pixels will skew things if not taken care of properly.

That may be. I suppose it's mostly fine-tuning though, and things work acceptable well without.

All in all, as far as I can tell the algorithm you posted checks if the touch point has moved a certain distance. If it has not, the touch point is set to the old one, and if it has, it is set to the point on a circle around the old touch point with radius position_stability_threshold that is closest to the newest touch point. Which matches @danielzgtg's algorithm.

That precisely what's intended. I would expect that is_stableand pos_stable should be connected though. But it totally fails when I set is_stable = pos_stable, so is_stable does something different but very important (but I don't understand what).

[qzed]

That sound like an explanation. The only thing I know is that ev1 is referred to as the "larger eigenvalue" here:

https://github.com/linux-surface/iptsd/blob/42a48e87fe79c91d8a94263fef65496678be4ff8/src/touch-processing.c#L158-L161

Right, yes that's the orientation/angle of the major axis of the ellipse and spread along major and minor axes, which here gets calculated from the eigenvalues of a covariance matrix (IIRC).

My reference to what I don't understand was ambiguous. I meant to refer to is input->is_stable and it's computation (which lacks fabs). See

https://github.com/linux-surface/iptsd/blob/42a48e87fe79c91d8a94263fef65496678be4ff8/src/finger.c#L14-L18

Ah, I see. Those indeed looks like they should have an fabs() around it.

That may be. I suppose it's mostly fine-tuning though, and things work acceptable well without.

Someone should probably try to figure out what the geometry looks like, but I'd advocate to add config options for that anyways, based on the grounds that IPTSd should probably strive to be general and applicable to not just Surface devices if other manufacturers decide to implement HID based touch heatmaps or stuff like that. It's easier to do that now when implementing the algorithm than later (although large parts already have been implemented, so it's probably already too late for that).

That precisely what's intended. I would expect that is_stableand pos_stable should be connected though. But it totally fails when I set is_stable = pos_stable, so is_stable does something different but very important (but I don't understand what).

Haven't written that part, so I'll have to guess based on the code what is_stable does: Since it's derived from eigenvalues, it's not a "position stable" thing, but I rather think it's a "numerically stable" thing. So I think that's used here to skip touchpoints where the eigenvalues are numerically unstable:

https://github.com/linux-surface/iptsd/blob/42a48e87fe79c91d8a94263fef65496678be4ff8/src/touch.c#L55-L56

Meaning those should be completely different things (assuming I'm right). I'm not sure though why there are differences calculated against the old eigenvalues.

[StollD]

More importantly, it's really sluggish. (Really smooth movement, but very noticable delay of maybe even a second.)

The code heavily relies on optimization, which are disabled by default. Additionally, it has debugging (access checks) enabled by default. I will update the README to reflect that.

(I assume, the libqzed branch is meant as a successor? Not a testing/playground stuff like neural nets, etc.)

Yeah its supposed to succeed the current implementation, once all the quirks are ironed out.

Haven't written that part, so I'll have to guess based on the code what is_stable does: Since it's derived from eigenvalues, it's not a "position stable" thing, but I rather think it's a "numerically stable" thing. So I think that's used here to skip touchpoints where the eigenvalues are numerically unstable:

It was added to counter the noise that appears when you put your palm onto the display. Sometimes the algorithm wont detect one big contact but multiple small ones. The is_stable filters out touch points that are rapidly changing their size.

[qzed]

It was added to counter the noise that appears when you put your palm onto the display. Sometimes the algorithm wont detect one big contact but multiple small ones. The is_stable filters out touch points that are rapidly changing their size.

Ah, that makes sense, thanks!

[tmarkov]

Ah, I see. Those indeed looks like they should have an fabs() around it.

IIRC, the reason this doesn't have 'fabs()' is that we want to ignore new touches that are rapidly increasing in size, but not ones decreasing in size. This was targeted at when putting a palm on the screen, and at first it's small enough to be indistinguishable from a finger. So we wait until the size has stopped increasing before we accept the touch.

(the confusing is_stable name is because it had fabs() initially)

[qzed]

Ah yeah, that would explain it.