Two years ago I worked on a subsequence matching algorithm, to solve a difficult data monitoring problem with tight algorithmic time and space complexity requirements. I went back to restart documenting this case. Now, instead of publishing my old results, I decided to make up a new challenge, to test and improve my findings. I created this task around a little web project, in order to show and use it as an interactive example: Sketch Recognition.

First of all, feel free to look into the demo.

eight

Task

Create an interactive website to arbitrarily draw lines and curves. An algorithm shall recognize predefined forms and shapes while they are being drawn. It should give assumptions on known figures and words while they are being written.

Requirements:

  • A figure can be freely drawn in a different size and varying rotation.
  • For every additional point being drawn, use O(c) space/time, where c=const

About the solution

I’m not able give you a finished solution yet. This might happen during the upcoming weeks and months. There are some extensive routines to implement, even with my previous project in mind.

Currently the websites features only the required JavaScript and CSS resources to max out any performance regulations. This project will not be done with any JQuery library or alike.

Tackle the requirements

Of course without the additional requirement you could simply use 2d coordinate system to save and compute polygons in. But infact the requirement makes this task so interesting.

Angular velocity

So instead of operating on coordinates, I decided to calculate the angular velocity at every point during drawing. It describes the change of the cursor’s movement angle, not over time, but over the distance passed. This leads to some advantages:

  • ignorable coordinate starting location
  • ignorable initial and continous scaling
  • ignorable initial and continous rotation
  • substituted plane coordinates to discrete angular information
  • numerical reduction of input data dimensions, from 2 to 1
  • thus more accessible to classic sequence algorithms

On the side of disadvantages we have:

  • unable to retrieve the original image with correct rotation and scale
  • some characters appear very similar when obsevering the angular velocity, e.g. 6, 0, c, o.
  • every person draws differently, this could yield individual issues

Illustration:

descr

Subsequence Matching

As of today, the demo shows matching sequences by using an online DTW variant, which does not save any matrices but two vectors of constant sizes for every pattern. This is the most basic approach to give a decision on matchable figures.

I recorded the single numbers, some words and a figure with various success rates. Since the algorithm is not trained or configured by any means, it will often give false-positives. But even in its primitive state it works surprisingly well on some of the characters. There will be much greater achievements, once additional features have been implemented: thresholds, conditionings, graduations and associations.

Look out for some upcoming posts!

More screenshots…

eight1

one

two

four