Re: [PATCH] input: Introduce light-weight contact tracking

[Henrik Rydberg]

On 11/08/2010 05:54 PM, Rafi Rubin wrote:

> On 11/08/2010 09:57 AM, Henrik Rydberg wrote:
>> Hi Rafi,
>>
>> what tree does this patch apply to?
> 
> It should apply to the torvalds/linux-2.6 master branch.


Odd, seems the patch was damaged somehow. Applies and compiles, thanks.

> The "complex" set of parameters was intended for more advanced users to give
> some feedback to help improve the driver.  Though given the lack of feedback, I
> guess you're right that there's little reason to expose them to users.


Sounds good. Would you agree that applying a modified version of the ubuntu
patch is the simplest way forward?

> The ubuntu 10.10 code does do filtering better than without filtering, but in
> trying it I've been seeing ghosts and have needed to calibrate multiple times
> per day (though that may be the result of a new screen being a little off).
> Furthermore while ripping out the filter code, you also ripped out single touch
> support for single touch firmwares, which apparently a few people still use.


Yes, thanks, I got a report regarding the single touch firmwares and was
planning to include it.


> Even without the ghost problem, it simply does not track as well.  The ntrig
> only reports every 8-24ms which is a long enough period to move quite a
> distance.


True, since it is using a greedy algorithm. This is what the exact in-kernel
tracking code is supposed to remedy. To be precise, the ubuntu version uses the
so-obtained assignment for filtering only - the tracking is still performed in
mtdev in userspace.

> In drawing up corner cases I realized that motion where two fingers
> are co-linear with the vector of motion require quite a bit of care to avoid
> perverting the tracking.


Yes, this is one example of why exact matching is needed.

> Greedily assigning matches based purely on distance
> can cause a flip.  Even global distance minimization is not reliable when we use
> linear distance as the cost.  A full analysis would require quadric distances
> and the global minimization tends to be an n^3 approach.  I'm sure we could
> reduce that a bit, but it just seems a bit heavy handed.


The patch that started this thread implements exact matching, which means
finding the optimal slot assignments that minimizes a measure of the distance of
all movements. The implementation is very fast, but still needs to be cut off at
some arbitrary number. Four seems to be a natural breakpoint. The fact that
matching scales badly is one of the major headaches, and the reason mtdev is
implemented in userspace. The middle-way proposed here is a balance that seems
to cater for existing hardware at the same time as expecting hardware to provide
their own tracking in the future.

> By contrast just a little bit of extra work to estimate the position based on
> the difference in position of the previous two points (which every algorithm
> discussed seems to do anyway) doesn't seem that egregious.


Using exact matching instead of greedy matching is what makes it work well. It
is very robust and parameter-free. On the eclectic side, one can certainly go
beyond that by optimizing for both position differences and speed differences
(maximum smoothness). However, I doubt it makes any difference on the
finger-tracking use case.

> The style of the code still assumes that we might want to adjust the
> aggressiveness of filtering ghosts and drops.  I agree it would be nice to be
> able to come up with a single value for each and hard code it, but I'm not
> willing to just assume that I can determine that value.


The ghost detection in the ubuntu version could probably be improved a bit, but
the biggest experience gain would probably come from automatic calibration.

> Also, for graceful
> degradation and repair, I would like to be able to code it so that those
> thresholds grow a little bit as a device drifts and then drop them again when
> calibration is run.


Tricky - perhaps a measure of the number of filtered ghosts could be used to
determine when it is time to recalibrate.

>
> Also, if you're going to criticize code for complexity, I would recommend some
> comments that explain your code beyond "this is a generated table, don't change
> it".


Hehe, the quote is actually wrong. ;-)

Of course you are right. More documentation is a good thing, and I will add more
of it. The code does at least refer to the generating program, and the commit
message tells where that program can be found. To discuss details, here is a
listing of some of that code:

/*
 * Combinatorial formulation
 *
 * x_ij = 1 if slot i and contact j are connected, zero otherwise
 *
 * sum_i x_ij <= 1 for all j; each contact picks at most one slot
 *
 * sum_j x_ij <= 1 for all i; each slot is picked by at most one contact
 *
 * sum_ij x_ij == min(nslot, npos); assign every contact possible
 *
 * Arrange x_ij as a bitmask; x_00 x_01 x_02.. x_10 x_11 x_12...
 *
 * Up to five slots, this is readily enumerable.
 */

static int illegal(int nslot, int npos, unsigned x)
{
	int i, j, sum;

	for (j = 0; j < npos; j++) {
		sum = 0;
		for (i = 0; i < nslot; i++)
			sum += GETBIT(x, i * npos + j);
		if (sum > 1)
			return 1;
	}
	for (i = 0; i < nslot; i++) {
		sum = 0;
		for (j = 0; j < npos; j++)
			sum += GETBIT(x, i * npos + j);
		if (sum > 1)
			return 1;
	}

	sum = bitcount(x);
	return sum != minval(nslot, npos);
}

static int generate_assignments(int nslot, int npos)
{
	static int ncol;
	unsigned x, nx = BITMASK(nslot * npos);
	int slots[SLOT_MAX];
	int i, n = 0;

	for (x = 0; x < nx; x++) {
		if (illegal(nslot, npos, x))
			continue;
		for (i = 0; i < nslot * npos; i++) {
			if (GETBIT(x, i)) {
				if (ncol++ % 16 == 0)
					printf("\n\t%d,", i);
				else
					printf(" %d,", i);
				n++;
			}
		}
		get_slots(slots, nslot, npos, x);
		for (i = 0; i < npos; i++) {
			if (ncol++ % 16 == 0)
				printf("\n\t%d,", slots[i]);
			else
				printf(" %d,", slots[i]);
			n++;
		}
	}

	return n;
}

For every (number of used slots, number of current contacts) pair, two
consecutive arrays of values are generated. The first contains the matrix
indices corresponding to a certain mapping from contacts to slots. The second
contains the actual slot assignment.

To find the optimal matching, one simply scans through the appropriate index
array, extracting the slot assignment corresponding to the minimum sum of matrix
elements. This process is combinatorial and in general scales much worse than
for instance the hungarian algorithm, but for small numbers, it can be
implemented with very good speed.

Cheers,
Henrik
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/