What are Levenshtein distance algorithms, but for images?

I will have one static image (the target: what it should look like) and one variable image (actual: what the user has created)

For example,


"K" sample

The following should be classified as "close enough"


"K" from user

But the following should be classified as "incorrect" (even though it has 2 strokes and fills the '|' part)

"b" from user

I will be using this as a guide for users new to the English alphabet to practice on writing.

I will, of course, have other checks in place such as counting the number of strokes made (2 for 'K', 1 for '|', 1 for '<') and also checking to see if the area covered is reasonable (filling whole area should not be identified as "correct").

The user "drawing" will only be in black and white (not greyscale).

I suppose I could train a neural network (like handwriting recognition) but only to identify if it is "close enough". I think this is overkill as this only requires checking to see if it matches a single image and not selecting the best-matching image from a set.

  • $\begingroup$ The Levenshtein algorithm is an efficient way to compute the Levenshtein distance. I'm not sure which came first. Do you have any particular metric in mind, or are you looking for any reasonable metric which is efficiently computable? $\endgroup$ Jul 29 '18 at 10:55
  • $\begingroup$ Judging from your example, a reasonable metric which is easy to compute would be the number of differing pixels, though in practice you will probably have to handle geometric issues such as shifting, rotation and scaling. $\endgroup$ Jul 29 '18 at 10:56
  • $\begingroup$ I suggest looking up image alignment, a similar problem of interest in computer vision. $\endgroup$ Jul 29 '18 at 10:58
  • $\begingroup$ @YuvalFilmus I am looking for any reasonable metric. It doesn't need to be too efficient - this is only for learning purposes. If it is efficient, it would be a bonus. $\endgroup$
    – wzgudahzb
    Jul 29 '18 at 15:58

I think you're really asking for a distance metric on images. Based on your examples, I would suggest the L2 distance (sum of squares of differences in pixel intensities) or L1 distance; possibly after aligning the images. This looks like it should b effective for the examples you list.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.