Shape-Writing or "Swyping"

Shape-writing, or "swyping" (instead of typing) seems to be the newest trend among touchscreen enabled devices. Of course, along with any new idea comes a slew of conflicting software patents that were accepted (where else?) at the United States Patent Office.

I believe that Apple, the original T9 creator, and Shape Writer Inc each have patents for what is essentially the same 'technology'. Please humor my quoted use of the word technology, because I am one of several billions of people who do not believe that software (which is what this is) should be patented.

This technology is very interesting in that it uses 'intelligent algorithms' to determine what word the user is trying to write. I thought that I would outline the fundamentals of these intelligent algorithms, just in case anyone in the FLOSS universe would like to implement them for a fun project in their spare time.

First of all, let's define the path that the users' finger or stylus traces on the touch screen. There exists 1) a starting point, 2) a finite number of 'corners'. If we assume that such a trace or path lies atop a coordinate system, for example, the imaginary plane, then the sequence of 'corners' simply become ordered coordinates in the complex domain.

Let's use a box, for example.

[ (0 + 0j), (0 + 11j), (11 + 11j), (11 + 11j), (0 + 0j) ]

The above set of ordered coordinates traces a box, starting at the origin, and continuing clockwise. The area of the box is (11x11) units squared.

In fact, the sequence of ordered coordinates comprimises a signal in the complex spatial domain (i.e. a 1-D signal), and as such (making several rudimentary assumptions), it can be mapped to a different coordinate space (the frequency domain), using the DFT (discrete fourier transform).

The most interesting part of this, I find anyway, is that taking the IDFT (inverse discrete fourier transform) of the 0-frequency component of such a signal, actually the 'mean', results in a single point lying at the geometric center of the box (i.e. the center of mass). Furthermore, the IDFT of the first two components result in a ellipse containing all points defined in the signal. As one would expect from summing successive components of a fourier representation, IDFTs of the next successive components result in a shape that increasingly resembles the original signal (i.e. a box).

It's pretty cool, at any rate. I had a lab excercise in Grundlagen der Geometrische Signalverarbeitung (Introduction to Geometric Signal Processing) in my first year at Uni-Kiel, which used a Christmas tree as an example.

In any event, if you define several points of interest in the complex domain, by overlaying the center-points of an on-screen-keyboard, then by careful application of Z-domain filtering, it's possible to determine the exact word that a person is trying to 'swype'. The Z-domain filtering is linear, and also unfortunately non-linear in nature. Why? Well, if you consider that corners represent signal components, then if a letter included in the signal just happens to be underneath the path, where no corner exists, then it's as if a component in the signal has been 'lost' during 'transmission'. It's as if higher frequency components are actually filtered out, so the 'intelligent' part of this algorithm is trying to associate a signal with another signal containing higher frequency components. This can be done, for example, by maximum likelihood or MMSE methods.

Alternatively, given a large enough sample group of input / output pairs, this problem can be solved quite easily using a lexicon or word association database. Given a path with a certain number of components, or corners, one should be able to do a very fast search to look up associated words in order of decreasing probability.

Ta Da!

I'm fairly certain that this 'technology' will be implemented in Android. However, I would also like to see it in the OpenMoko project.

Maybe such an app has already existed in the open-source world for some time. If not, or if anyone would like to volounteer to write such an app, then I would be very open to further explaination. Just submit a comment below.

Update (20100412): It appears that Samsung has integrated the idea of 'swyping' into Android on their new(ish) Galaxy S devices, as you can see from the video below. Very Cool.