Identifying connected lines drawn free-hand by a user

Question

I have a series of 'images' described by a mixture of connected lines and curves. Users will draw on the screen, free hand, and my goal is to break their drawing down into a series of lines and curves that can be matched with the 'images' in my set.

For the sake of simplicity, let's assume this is occurring on a touch screen. These lines will be connected. Each time the user's finger moves, the dx and dy is recorded. The drawing is considered complete and analyzed when the user's finger leaves the screen.

I'm having trouble figuring out a good way to break the user's drawing down into lines. Is there any well known approach to this problem, a C++ library that solves it, or any good articles/technical papers on how to achieve this?

Answer 1

Recognising arbitrary shape vectors is hard!

A simpler technique is to use a grid and count the edges crossed by the stroke drawn by the user. This list of edges is used as a "signature" which is compared against a dictionary of signatures of pre-defined shapes.

Algorithm

1. Sub-divide the input area into a grid (eg: 3x3 with infinite edges), and give each edge a unique ID. The exact size and number of divisions depends on your implementation. More grid divisions leads to greater versatility at the cost of robustness.

2. The user draws a line over the grid to create a stroke. Note that the grid does not actually need to be visible on the screen, but doing so will assist in the usability of the interface.

3. The path taken by the stroke is analysed for intersections with grid edges. Each edge that the stroke intersects is added to a list of edges. This becomes the signature for the character. In this example, the "S" curve intersects with the edges Y12, Y7, X7, Y8, Y13, X14, Y14, Y9.

4. The signature is compared against a dictionary of pre-defined signatures and the closest match (or matches) is returned.

Usability considerations

1. The user input will not be perfect and the search needs to cater for inexact matches caused by extra or missing edges in the input. One way to deal with this problem is to build a directed graph of the input. This will record the relationship of the points to each other. It will tell you that X7 comes before Y8, but after Y12 for example. The search then compares this against the graph of each character in the dictionary. Each node that matches is assigned a percentage based on the exactness of the match. The node (or nodes) with the highest total percentage matches is used as the overall match.

2. Multiple variations of each character in the dictionary may also be helpful. In the example above, the signature is valid for the character when drawn from the upper-right quadrant, but it may be useful to have a signature for the same character drawn from the lower-left quadrant, which will essentially be the reverse of the example.

3. Characters may be made of multiple strokes. For example if the user draws and upside-down "U" and then a "-" the algorithm may match this to two separate characters such as "n-", or it could combine the two strokes and recognise an "A". A time based heuristic could be used as the differentiator, so that multiple strokes in quick succession will result in one character, whereas strokes drawn with more time in-between will result in multiple characters.

4. If the input system is to be used for hand-writing the number of potential characters and input styles can be large. A word dictionary and/or grammatical analysis could be used to find a set of characters which are most likely to occur next. This is intersected with the list of the matching character signatures to produce an likely candidate.

EDIT: Additional considerations

1. It may not always be desirable to show the grid during input. In this case it may be necessary to scale the stroke before applying it to the grid. Naive scaling would work but the results may be skewed by points which fall far outside the input region. A workaround is to find the centroid (the average x,y coordinate) of the input stroke, then calculate the average distance of each point in the stroke from this centroid. The stroke is then scaled based on this average distance.

2. I posted another answer with a different approach using vectors. That algorithm also used the Levenshtein distance to match the character signature. The same approach can be applied to this algorithm during the search phase.

Answer 2

To rephrase the original question:

You have a series of points which represent samples of a continuous (but not necessarily straight) line, and you want to represent that line using fewer samples.

Basically what you're trying to find is samples which don't contribute much to the overall shape of the line. The fastest way to do this, in my experience, is to, one at a time, calculate how much "error" would be introduced by removing each sample, and then actually remove the one which results in the least total error.

You then repeat this process, for each remaining point. You continue finding "what's the least bad point to remove" and removing it, as long as the total error induced in the line is less than some maximum "error" threshold.

Important that your error calculations need to be compared against the original line shape, NOT the progressively optimised shape, or else you can end up with the optimised line devolving away from the drawn shape.

I have sample code (from years ago) available here: http://www.vectorstorm.org/svn/repos/VectorStorm/trunk/Games/VectorPhysics/VP_Drawable.cpp

Look inside vpDrawable::OptimiseOutOneIndex() for my implementation of this process.

Answer 3

I think you can find good resources by searching for articles about OCR. as far as I could understand your question your problem is a one of OCR sub-problems. you can also search for pattern recognition.

after searching a little bit, I've found this article. I just looked at images (didn't read it at all) and it seems like it's providing algorithm to extract both curves and lines. and it's doing a good job!

Answer 4

Here's an implementation of another algorithm: http://www.bytearray.org/?p=91

It works by decomposing the input stroke into a set of vectors which are multiples of 45 degrees. This simplified representation is compared against a database using the Levenshtein distance.

* Note: the Levenshtein distance can also be applied to the other algorithm I posted here.

Answer 5

Maybe you can use the Douglas-Peucker algorithm to find corners of the lines and break the lines that form points.