Similarity1.pm - calculate a similarity measure between two strokes

use Similarity1; @vector1=qw(x0 y0 dx1 dy1 ...); @vector2=qw(x0 y0 dx1 dy1 ...); $dist=Similarity1::similarity(\@vector1,\@vector2);

This modules implements a similarity measure between strokes, given as list of vectors with base point, i.e.:

the first two elements are absolute coordinates

each other pair of elements is relative to the previous one

This function returns a measure of distance between two vector sequences, as described above.

The following formulas are used:

`A(t)`

is a function such that`A(0)`

is the first point in the first sequence,`A(1)`

is the last point, and`|A(t)-A(t+dt)| =prop dt`

(i.e. it moves with costant speed along the vectors) (see sub timing)`B(t)`

is the same for the second sequence`distance = Integrate[|A(t)-B(t)|^2,{t,0,1}]`

This function calculates the integral `Integrate[|A(t)-B(t)|^2,{t,0,1}]`

for the simple case of single-vector sequences.

Here's the math:

the two sequences are (a,b) and (c,d) (absolute coordinates for the extremes)

Int[|A(t)-B(t)|^2,{t,0,1}] A(t)=(b-a)*t+a=A'*t+a B(t)=(d-c)*t+c=B'*t+c

==

Int[|A'*t+a-B'*t-c|^2] = Int[|t*(A'-B')+a-c|^2] X=A'-B' Y=a-c

==

Int[|t*X+Y|^2] X=(Xx,Xy) Y=(Yx,Yy)

==

Int[(t*Xx+Yx)^2+(t*Xy+Yy)^2] = Int[t^2 Xx^2 + Yx^2 + 2 Xx Yx t + t^2 Xy^2 + Yy^2 + 2 Xy Yy t] = Int[t^2*(Xx^2+Xy^2) + 2t(Xx Yx + Xy Yy) + Yx^2 + Yy^2 , {t,0,1}] = [(Xx^2+Xy^2)/3*t^3 + (Xx Yx + Xy Yy)*t^2 + (Yx^2 + Yy^2)*t][0,1] = (Xx^2+Xy^2)/3 + (Xx Yx + Xy Yy) + (Yx^2 + Yy^2)

This function adds "timing" information to a sequence of vectors. It calculates the length of the entire sequence, then inserts after each pair of coordinates the fraction of length up to that point relative to the total length.

This code is copyright (C) 2002 Gianni Ceccarelli Released under the GNU LGPL, version 2.1