NAME

Similarity1.pm - calculate a similarity measure between two strokes

SYNOPSIS

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

DESCRIPTION

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

FUNCTIONS

sub similarity

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}]

sub rectarea

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)

sub timing

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.

LICENSE

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