Assignment #3: Multi-Touch Tracking

Due: March 18 by 11:30 (Extension of 2 days)

This assignment is to be done individually.

Academic Integrity

The following is offered with apologies to the vast majority of students who do their work honestly and take their university learning seriously:

Your instructor takes academic integrity seriously and has no tolerance for plagiarism or any other form of academic misconduct. Failure to respect these guidelines will result in you receiving a grade of zero on this assignment.

Acceptable collaboration between students, provided it is acknowledged explicitly in your report and code, might include:

1. discussing some aspect of the assignment specifications in attempting to understand a particular point
2. discussing high-level aspects of Expectation-Maximization

Unacceptable collaboration and violations of academic integrity include, but are not limited to:

1. including any code that was not your own and failing to indicate so
2. copying parts of the solutions to any question from other students

If you are uncertain about any of these guidelines, please discuss with your instructor as soon as possible.

Background

A multi-touch screen is sensitive to finger pressure applied to the surface, possibly at multiple positions in parallel. The finger contacts are sensed by an array of 1D row accumulators and an array of 1D column accumulators, which are read at a rate of 40 Hz. Finger positions are estimated by the intersections of these 1D accumulators, i.e., an active row and active column. However, the contact of two fingers in parallel leads to ambiguous interpretations. For example, as shown in the figure to the right, the input could be interpreted as points A and D, or points C and B.

This problem is resolved by assuming that two fingers will not both make initial contact with the surface at exactly the same time. We can then track the movement of each finger between readouts and avoid the ambiguity. However, another problem, "shadowing", occurs if the paths of two fingers intersect, as illustrated here. In this case, we are uncertain whether the fingers continue moving in their original directions ("crossed") or whether they flip directions ("bounced").

In this assignment, you will apply Expectation Maximization (EM) to solve the multi-touch finger tracking problem, using a Mixture of Gaussians to model the system. You are to implement the algorithm described above and experiment with this sample data, acquired during a shadowing event. The file contains a sequence of 222 frames (observations) consisting of the signal strength accumulated along each row and column.

In your report, answer the following questions, making sure to explain your reasoning and procedure, and illustrating your results graphically. Justify any assumptions or value assignments you made.

Part 1

Questions

1. Since EM is an iterative algorithm, its results can depend on initialization parameters. Using the columns of frames 47 and 130, show the initial and final arrangement of the Gaussians and indicate the number of iterations required to achieve convergence of EM with the following initialization parameters:
   1. One Gaussian at the center of the axis, with a standard deviation of half the signal width.
   2. Two Gaussians, each having its mean at the lower end of the axis, a standard deviation of 4 accumulators, and a weight of half the total signal strength along the axis.
   3. Four Gaussians, each having its mean at the middle of successive quarters of the axis, all having equal weights, and a standard deviation of one eight of the signal width.
   4. One Gaussian per peak, with the means at the ends of the axis, a constant standard deviation of 4 accumulators, and a weight of the total signal strength along the axis, divided by the number of peaks. Every odd Gaussian should be added at the low end of the respective axis.
   5. One Gaussian per peak, with the mean at the centroid of the peak, the standard deviation calculated as half the peak width, and a weight of the total signal strength along the axis, divided by the number of peaks.
   6. Same as (e), but with standard deviation as half the width of the peak and weights proportional to the signal strength of each peak.
   7. Same as (f), but adding one more Gaussian to model noise, with its mean at the middle of the axis, standard deviation as half its length, and with weight equal to the remainder of the total signal strength after subtracting the sum of weights from (f).

   Explain your observations, commenting on the impact of the number of Gaussians and their initial parameters on the results of EM.

2. Rerun the scenario from question 1.g using a few different values of convergence conditions, and comment on their effect on the output of EM. Try different combinations based on the change in position, standard deviation, and weight.

Part 2

We now perform tracking on the sequence of frames as a precursor to gesture recognition.

1-D Tracking

The tracked 1-D (horizontal or vertical) coordinates of a finger are maintained by the p_t. These values are estimated initially as p_t, described below.

• For each sampling period, the prediction of the finger position in each axis at time t is estimated from its position and speed from the previous frame: p_t = p_t-1 + v_t-1 Δt
  where v_t-1 is the finger velocity measured from the previous two samples and Δt is 25 ms.
• Finger contacts typically span multiple adjacent rows or columns, as sensed by accumulators S_p. Because the accumulators are imperfect, some noise is always present, so the observed signal values must be thresholded to determine which accumulators are reporting valid contacts. A list of peaks, S_p, is obtained by calculating the centroids over every set of adjacent accumulators that report values above threshold.
• Each S_p is matched with its closest p_t. However, only those matches that are within a distance bound determined by the maximum possible speed of the finger are considered valid. The S_p values may be associated with zero, one, or more p_t, as follows:
  • A peak S_p that is not associated with any p_t is considered to be a new finger contact, with a new Gaussian associated. The velocity associated with this peak, v_t is set to 0.
  • A S_p associated with a single p_t is simply used to update the initial parameters of the Gaussian associated with p_t.
  • If S_p is associated with more than one p_t, this indicates shadowing.
• We then run the EM algorithm with the Gaussians initialized as described [above?] to obtain the new positions of the Mixture of Gaussians.
• The 1-D tracked p_t positions are determined by associating the predicted p_t and the means of the Gaussians following EM, so as to minimize the sum of distances between the p_t and the means of the Gaussians. However, if the distance between two Gaussians is less than one accumulator row or column, the p_t retain their original predicted values, p_t.
• Finally, we calculate the new velocity, v_t = p_t - p_t-1.

2-D Tracking

The tracking model works as follows:

• If both a row and a column p_t, exist, and are not currently associated with any tracked finger, they are used together to describe the 2-D position of a new finger contact with the surface.
• If at least one of the row or column p_t differs from p_t-1, this indicates movement of a tracked finger.
• If a p_t is not associated with any S_p, this indicates that the corresponding finger has been removed.

Run the tracking algorithms described above using the initialization scheme from question 1.g.

Questions

3. Provide the output as a 2D map showing the motion of the finger(s).
4. Show the Mixture of Gaussians for both axes for frames 10, 45, 59, 82, 114, 119, 121, 125, 134, and 163, indicating, for each frame, the parameters and velocities of each tracked finger.

Additional notes

You may program your assignment in any computer language of your preference, provided it can be compiled and run on the Trottier Engineering Linux machines (TR5130GU-<x>.ece.mcgill.ca where x ∈ [1,16]). To login, use your McGill UEA (first.last@mail.mcgill.ca) and your regular MCF password.

You are allowed to use Matlab or a library of your choice for graphics purposes only; however, you should not be using a library or other third-party software implementation of EM.

Submitting your assignment

The hardcopy should explain the design decisions you made and address the items noted above. Remember that your report is the main method of communicating what you have accomplished to the reader. Therefore, make sure that it is well organized and well written; you will lose marks for spelling errors and poor grammar. The report should be a maximum of three pages in length, exclusive of any appendices as relevant. You are welcome to include illustrations as useful to elucidate the text. These are not considered as part of the three-page limit. No printout of program code is required.

In addition to the hardcopy submission, you must submit, through myCourses/WebCT (yes, we are using myCourses, but only for this purpose), an electronic version of your assignment in zip or UNIX tar format, which includes:

• all of the source code ready to be compiled under the Trottier Engineering Linux machines
• a Makefile for compiling your source code

Please do not include with your submission any other items, such as object code (*.o) files or your executable program. or marks will be deducted.

The hardcopy and electronic versions may be submitted at different times prior to the assigned deadline. Assignments will not be considered complete until both components have been received.

Marking scheme

Last updated on 10 March 2011
by Mohannad Elhamod, Jeremy Cooperstock, and a to-be-named colleague