Background: I'm working on an application which is supposed to teach users how to write Japanese kanji. Each kanji is represented as an array of strokes. Each stroke is an array of 2d points.

Strokes (2d paths) are supposed to be drawn in certain order, so my question is limited to recognizing similarity b/w single drawn and sample paths. I don't need to search paths by their shape or anything like that, I just want to tell if a drawn path is "close" to a sample.

I also want to specify "accuracy" of drawing with these parameters:

  1. Distance - each stroke has a specific location in a kanji, but little offset is allowed.
  2. Angle - each stroke should be drawn in a specific direction. If it has a proper shape, but drawn backwards, that's an error. Ideally, I want to notify a user that (s)he draws a shape correct, but backwards. I might just run an algorithm a second time for reversed stroke just to tell that.
  3. Scale - little variation is allowed, especially for tiny strokes
  4. Shape - generally, strokes are simple, but some of them can have up to 3-4 "turns", and segments b/w those turns can be straight or curved. You can look at the list of radicals to see how much details there are. However, I don't need an extra precision, since users will draw strokes using mouse or touch screen, so drawn paths might have pretty major deformations. I just want to be able to distinguish shapes like "V", "N", and "W".

I've tried to use DTW, but it only works good for measuring distance, and fails to find major differences in shape - e.g., if I draw "N" shape and only draw first two segments ("|" and "\" connected), the result of calculating DTW distance can be OK with an error threshold I set, but the shape is obviously wrong, and DTW can't tell that.

I also tried to check angle with DTW, semi-successfully, and then gave up after I realized that this can't be used to deal with shapes. I saw DTW used in similar applications, and all of those suffer from telling that the long 2nd stroke in "え" is always wrong, and/or failing to tell the difference b/w vertical line and a "hook", which makes those apps either useless (any stroke goes) or unusable (can't get it right no matter how accurate you are).

Next, I found shape context algorithm, but I think it is not applicable to my task:

  1. It uses thin plate splines model, which does not preserve straight lines, which is desired. I know I can use affine transformations instead, but then I don't know how to impose limitations on that transformation. As I stated above, I want to limit differences in position, rotation, and scale.
  2. In my task, sample points from drawn and sample strokes are already "matched" to each other, 1-to-1, because I can just take N points from drawn stroke with equal steps, and match them to N points from sample stroke. So, initial steps of this algorithm are not even needed.
  3. I believe that in my task it is not ideal to use log-polar histograms as point descriptors. Instead, I can just use an array of N-1 vectors from current point to other points as a reach descriptor of each point.

Yet, this algorithm looks very promising for shape matching. Maybe there is something similar which is applicable to my task. I couldn't find anything better yet, so even the name of an algorithm would be very nice.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.