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.


Triple Booting the Neo FreeRunner

Hi everyone,

It's been a while since my last post, so I must apologize for that. Things have been very busy since November.

However, as some of you may already know, I was also experimenting with the Android operating system on my FreeRunner directly after the source code was released. In fact, I was arguably the first person to compile Android for the ARMv4T architecture. Thanks to the work of the community, it is now possible to run Android on the FreeRunner using KoolU's sources.

The private Android repository is to be merged with the official public repository sometime in Q4 2008, while the first release featuring an on-screen-keyboard will be Q1 2009. The areas I would like to concentrate on are WiFi, and Glamo improvements.

In any event, I'm currently triple-booting the FreeRunner with the latest OM image (or FDOM image), Android, and Gentoo. I'm planning using the Gentoo install for debugging things that will eventually go into the OM and Android images.

I'm using an 8GB uSD card with 4 primary partitions:

/dev/mmcblk0p1: MokoData (vfat) 5 GB
/dev/mmcblk0p2: AndroidData (ext2) 512 MB
/dev/mmcblk0p3: MokoRoot (ext2) 512 MB
/dev/mmcblk0p4: GentooRoot (ext2) 2 GB

Android is of course installed to the 'rootfs' partition in nand flash. MokoData contains uImage-android (from Sean McNeil), uImage-2008.9.bin, and uImage-2008.12.bin - the latter two are official OpenMoko kernels. I've updated the nand boot menu so that menu_2 boots OM 2008.9, menu_3 boots Android, and menu_4 boots Gentoo.

At some point in the near future, I'm hoping to create a torrent so that the configuration can be downloaded and shared by everyone in the community, but you may have guessed that Free Time(TM) is limited these days.