4
$\begingroup$

I am working on an optical character recognition algorithm that takes vector data (i.e. polylines) as input rather than raster picture. E.g., we have N polyline samples, and when certain polyline is given as algorithm input we want to know which sample most likely it is.

My question is as follows: is there any metric of similarity between two polylines? I have an idea about it, but I wonder if that a form of some well-known method, or are there any alternative algorithms of recognizing curves in vector representation.

So my idea of similarity measurement:

  • Move two curves so that their "center" points match.

  • Measure the area formed by two curves (yellow on figure). The less area is - the more similar curves are.

  • We can also consider curves length as metric. E.g., the area can be about zero, but one curve can be much longer than another and thus not similar to it.

enter image description here

Is that idea correct? Are there any other algorithms? Thanks.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ For two sets $A,B\subset\mathbb R^2$, one possible metric would be $d(A,B)=\inf_fd_H(a,f(B))$, where $d_H$ is the Hausdorff metric and $I$ ranges through the isometries of the plane. (This resembles the Gromov-Hausdorff distance.) If you want, you can make $I$ include scaling (or other stuff) as well if it suits your purposes. Would something like this work for you? $\endgroup$
    – Joonas Ilmavirta
    Commented Mar 11, 2015 at 22:40
  • 1
    $\begingroup$ At this stage this is a scientific question, not mathematical. What kind of lines do you have? Printed? Hand written? Artistic? Do you assume that they are about the same size? Are they oriented in the same way? Do they appear as material items seen from different angles and with distortions (like on a page which is not flat, at the inside margins)? Once the nature of the characters (or similar) is known then the algorithm is a relatively easy issue. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Mar 11, 2015 at 22:52
  • 2
    $\begingroup$ I agree with @WłodzimierzHolsztyński that the problem is not a mathematical one. Asking for mathematical ideas for measuring the difference would be ok at math.stackexchange, I think, so I voted to migrate the question there. $\endgroup$
    – Joonas Ilmavirta
    Commented Mar 11, 2015 at 23:09
  • 4
    $\begingroup$ You may wish to compute the Frechet distance between curves, which can be computed in quadratic time. $\endgroup$
    – Suvrit
    Commented Mar 11, 2015 at 23:11
  • 2
    $\begingroup$ Tom Crimmins in late 1970s had written a paper about character recognition by applying the Fourier analysis. Perhaps he assumed a closed curve, and looked at the Fourier coefficients as invariants. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Mar 11, 2015 at 23:13

2 Answers 2

Reset to default
6
$\begingroup$

If I may just expand upon Suvrit's suggestion, here is an image illustrating the Fréchet distance, the minimum length of a leash allowing a dog and its owner to walk along the two curves without backtracking:

     
      (Image from Wouter Meulemans.)

Kevin Buchin, Maike Buchin, Wouter Meulemans, and Bettina Speckmann. "Locally Correct Fréchet Matchings." Proceedings of the 20th European Symposium on Algorithms (ESA 2012), LNCS 7501, pages 229-240, 2012. (arXiv abstract link)

Improve this answer
$\endgroup$
3
$\begingroup$

There are many ways to measure distances between curves, but I do not think you need it.

Instead I would play with some functionals say total turn, number of inflection points and so on and check which of them best for your recognition problem.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .