Is there an algorithm to measure the accuracy of a traced a path?

Question

I have an equation for an arbitrary shape (circles, spirals, squares, etc) that I am trying to trace on an ipad. Assuming that the ipad records my tracing lines as a set of x,y coordinates how do I measure how well I was able to trace the lines? I understand that there might be many different measures of "wellness", but I am having trouble thinking of an algorithm that can't be exploited. For example, originally I thought to calculate the closest distance from all the points to the shape and calculating the mean of the distance for a score, however I realized that I can just place one point very close to the circle and it can give you a high score.

For example, this trace would return a better score than this trace. Is there any known algorithms in literature that deals with this?

Answer 1

It depends a lot on what you consider to be accurate. I presume you don't care how the tracing is done; the score is supposed to be the same for the same trace regardless of the traced position over time. $ \def\lfrac#1#2{{\large\frac{#1}{#2}}} $

Now if you don't care about smoothness of the tracing, then you could use the following:

Let $S,T$ be the sets of pixels for the figures you wish to compare.

Let $d(S,T) = \lfrac1{\#(S)}\sum_{p \in S} d(p,T) + \lfrac1{\#(T)}\sum_{p \in T} d(p,S)$,

  where "$d(x,U)$" denotes the minimum distance from point $x$ to set $U$.

This measure penalizes deviations fairly, roughly proportional to the size of the average deviation rather than the maximum deviation. It also avoids being affected if you use too many or too few pixels to trace the figure. Also, it works equally well for figures with disjoint regions. Finally, it is stable with respect to human errors and preserved under translation and rotation and scaling, so one can use it to measure accuracy of a person and not just a particular tracing.

Answer 2

You might try the Hausdorff metric. Compute

1. The maximum of the distances from your points to the shape.
2. The maximum of the distances from the points of the shape to your points.

and then take the maximum of those.