Signature Comparison

Following the signature capture projects, I decided to make a program that analyzes the signature to see how close two different signatures match.

My first step was create an account on bitbucket.  The reason I chose bitbucket over github was because bitbucket allows for private repros.  Also, I wanted to try out Mercurial.  I installed the most recent version on my machine and then added the VisualHG extension to Visual Studio 2010.  Note that you have to change your source control plug in Visual Studio (Tools –> Source Control)

I then was pushing/pulling my repro to bitbucket.  There are still some small things I don’t like (for example, having to enter your credentials each push/pull), but on the whole Mercurial is easier to use in Visual Studio than git and bitbucket is much better than github.

In any event, once I set up my source control, I consolidated all of my projects having to do with this signature series and renamed from things.

The once thing I don’t like is that the word ’signature’ is in both the namespace and is a class name – so I get conflicts.  I am not sure what I want to rename the class so I left it ‘as is’ right now.  But as Bob Martin says “with these modern/fancy IDEs, renaming a class should take no time at all.”

I then refactored my object graph:

Note that I discarded using System.Drawing.Line and System.Drawing.Point from earlier projects so my analysis program would not have a dependency on System.Drawing.  I spun up the unit tests for line and class in a separate project:

and got pretty good code coverage:

Note that I didn’t write unit tests for things that the API handles – like the constructor.

With the support classes ready to go, I then tackled the signature analysis.  I first started doing a line analysis – basically starting with a base signature and then layering over a second signature to see how close the lines match.  Because the signatures might be different sizes and on different slopes, I thought I would have to adjust the second signature to match the base’s dimensions.  I would do this by matching the left and top point of both signatures and moving the second one’s lines over to that adjustment factor.

I then realized that I don’t know enough about signature analysis to have “THE” solution to code.  I then adjusted my project to reflect that there might be many different ways to analyze a signature and I should use the power of polymorphism to help me.  I then threw away all of the analysis code that I was working on to get to “THE” solution.

I created an interface called IComparisonFactory like so (note the fully qualified name – I really need to change that)

public interface IComparisonFactory
{
    double CompareSignatures(Tff.Signature.Support.Signature signature1, Tff.Signature.Support.Signature signature2, int levelOfFreedom);
}

I then created an abstract base class that has some functions that do the low level plumbing:

public abstract class BaseComparisonFactory
{

    protected List<Line> GetAllLinesInASignature(Tff.Signature.Support.Signature signature)
    {
        List<Line> lines = new List<Line>();
        List<Glyph> glyphs = signature.Glyphs;
        foreach (Glyph glyph in signature.Glyphs)
        {
            foreach (Line line in glyph.Lines)
            {
                lines.Add(line);
            }
        }

        return lines;
    }
    

    protected List<Point> GetAllPointsInASignature(Tff.Signature.Support.Signature signature)
    {
        List<Point> points = new List<Point>();
        List<Line> lines = GetAllLinesInASignature(signature);
        foreach (Line line in lines)
        {
            points.Add(line.StartPoint);
            points.Add(line.EndPoint);
        }
        return points;
    }
}

I then created my 1st attempt an analyzing two signatures by looking at the dispersal of their points – a scatterplot analysis.

public class ScatterplotComparisonFactory: BaseComparisonFactory, IComparisonFactory
{
    public Double CompareSignatures(Tff.Signature.Support.Signature signature1, Tff.Signature.Support.Signature signature2, Int32 levelOfFreedom)
    {

        Int32 pointTrys = 0;
        Int32 pointHits = 0;

        List<Point> basePoints = GetAllPointsInASignature(signature1);
        List<Point> comparePoints = GetAllPointsInASignature(signature2);

        List<Point> normalizedBasePoints = basePoints.Distinct().ToList<Point>();
        normalizedBasePoints.Sort(ComparePoints); 

        List<Point> normalizedComparePoints = NormalizePoints(comparePoints, levelOfFreedom);
        normalizedComparePoints.Sort(ComparePoints);

        foreach (Point basePoint in normalizedBasePoints)
        {
            foreach (Point comparePoint in normalizedComparePoints)
            {
                if (basePoint == comparePoint)
                {
                    pointHits++;
                    break;
                }
            }
            pointTrys++;
        }

        Double returnValue = ((Double)pointHits / (Double)pointTrys);
        return returnValue;
    }

    private List<Point> NormalizePoints(List<Point> comparePoints, int levelOfFreedom)
    {
        List<Point> normalizedPoints = CreateNormalizedPoints(comparePoints, levelOfFreedom);
        normalizedPoints = RemoveNegativePoints(normalizedPoints);
        return normalizedPoints;
    }

    private List<Point> CreateNormalizedPoints(List<Point> comparePoints, int levelOfFreedom)
    {
        List<Point> normalizedPoints = new List<Point>();
        foreach (Point basePoint in comparePoints)
        {
            normalizedPoints.Add(basePoint);
            for (int i = 1; i <= levelOfFreedom; i++)
            {
                normalizedPoints.Add(new Point(basePoint.X - i, basePoint.Y - i));
                normalizedPoints.Add(new Point(basePoint.X - i, basePoint.Y));
                normalizedPoints.Add(new Point(basePoint.X - i, basePoint.Y + i));
                normalizedPoints.Add(new Point(basePoint.X, basePoint.Y + i));
                normalizedPoints.Add(new Point(basePoint.X + i, basePoint.Y + i));
                normalizedPoints.Add(new Point(basePoint.X + i, basePoint.Y));
                normalizedPoints.Add(new Point(basePoint.X + i, basePoint.Y - 1));
                normalizedPoints.Add(new Point(basePoint.X, basePoint.Y - 1));
            }
        }

        return normalizedPoints;
    }

    private List<Point> RemoveNegativePoints(List<Point> normalizedPoints)
    {
        List<Point> points = new List<Point>();

        foreach (Point point in normalizedPoints)
        {
            if (point.X >= 0 && point.Y >= 0)
            {
                points.Add(point);
            }
        }

        return points;
    }

    private static int ComparePoints(Point point01, Point point02)
    {
        if (point01 == point02)
        {
            return 0;
        }
        if(point01.X == point02.X)
        {
            if (point01.Y < point02.Y)
            {
                return -1;
            }
            else
            {
                return 1;
            }
        }

        if (point01.X < point02.X)
        {
            return -1;
        }
        else
        {
            return 1;
        }

    }

}

Note that the ComparePoints function allows me to call .Sort().

The levelOfFreedom argument takes the second signature’s points and increases them to all adjacent points.  I also remove duplicate points, sort them (first X than Y), and remove any point that is less than zero.

Instead of creating tests for each of the ComparisonFactories that I will create, I created a test class for ICompairisonFactory and injected in the implementation in the constructor.  I then ran the scatterplot though the tests to see if they pass basic analysis (same signature returns 1, etc…).

public class ScatterplotComparisonFactory: BaseComparisonFactory, IComparisonFactory
{
    public Double CompareSignatures(Tff.Signature.Support.Signature signature1, Tff.Signature.Support.Signature signature2, Int32 levelOfFreedom)
    {

        Int32 pointTrys = 0;
        Int32 pointHits = 0;

        List<Point> basePoints = GetAllPointsInASignature(signature1);
        List<Point> comparePoints = GetAllPointsInASignature(signature2);

        List<Point> normalizedBasePoints = basePoints.Distinct().ToList<Point>();
        normalizedBasePoints.Sort(ComparePoints); 

        List<Point> normalizedComparePoints = NormalizePoints(comparePoints, levelOfFreedom);
        normalizedComparePoints.Sort(ComparePoints);

        foreach (Point basePoint in normalizedBasePoints)
        {
            foreach (Point comparePoint in normalizedComparePoints)
            {
                if (basePoint == comparePoint)
                {
                    pointHits++;
                    break;
                }
            }
            pointTrys++;
        }

        Double returnValue = ((Double)pointHits / (Double)pointTrys);
        return returnValue;
    }

    private List<Point> NormalizePoints(List<Point> comparePoints, int levelOfFreedom)
    {
        List<Point> normalizedPoints = CreateNormalizedPoints(comparePoints, levelOfFreedom);
        normalizedPoints = RemoveNegativePoints(normalizedPoints);
        return normalizedPoints;
    }

    private List<Point> CreateNormalizedPoints(List<Point> comparePoints, int levelOfFreedom)
    {
        List<Point> normalizedPoints = new List<Point>();
        foreach (Point basePoint in comparePoints)
        {
            normalizedPoints.Add(basePoint);
            for (int i = 1; i <= levelOfFreedom; i++)
            {
                normalizedPoints.Add(new Point(basePoint.X - i, basePoint.Y - i));
                normalizedPoints.Add(new Point(basePoint.X - i, basePoint.Y));
                normalizedPoints.Add(new Point(basePoint.X - i, basePoint.Y + i));
                normalizedPoints.Add(new Point(basePoint.X, basePoint.Y + i));
                normalizedPoints.Add(new Point(basePoint.X + i, basePoint.Y + i));
                normalizedPoints.Add(new Point(basePoint.X + i, basePoint.Y));
                normalizedPoints.Add(new Point(basePoint.X + i, basePoint.Y - 1));
                normalizedPoints.Add(new Point(basePoint.X, basePoint.Y - 1));
            }
        }

        return normalizedPoints;
    }

    private List<Point> RemoveNegativePoints(List<Point> normalizedPoints)
    {
        List<Point> points = new List<Point>();

        foreach (Point point in normalizedPoints)
        {
            if (point.X >= 0 && point.Y >= 0)
            {
                points.Add(point);
            }
        }

        return points;
    }

    private static int ComparePoints(Point point01, Point point02)
    {
        if (point01 == point02)
        {
            return 0;
        }
        if(point01.X == point02.X)
        {
            if (point01.Y < point02.Y)
            {
                return -1;
            }
            else
            {
                return 1;
            }
        }

        if (point01.X < point02.X)
        {
            return -1;
        }
        else
        {
            return 1;
        }

    }

}

Here is the full suite:

Finally, I had everything in place to do an integration test.  I loaded some signatures into XML files and ran them through the integration tests.  Interestingly, the scatterplot seemed to work.

Case #1: Same Signature Compared To Itself (Same Person, Same Signature)

returns

0 = 1.0

1= 1.0

2= 1.0

3= 1.0

4= 1.0

5= 1.0

6= 1.0

7= 1.0

8= 1.0

9= 1.0

 

Case #2: Two Signatures That Are Close To Each Other (Same Person, Different Times)

0 = 0.0131578947368421

1 = 0.177631578947368

2 = 0.266447368421053

3 = 0.391447368421053

4 = 0.463815789473684

5 = 0.542763157894737

6 = 0.628289473684211

7 = 0.661184210526316

8 = 0.700657894736842

9 = 0.753289473684211

 

Case #3: Two Signatures That Are Not Close (Different People)

 

0 = 0

1 = 0.111842105263158

2 = 0.154605263157895

3 = 0.180921052631579

4 = 0.213815789473684

5 = 0.220394736842105

6 = 0.299342105263158

7 = 0.305921052631579

8 = 0.319078947368421

9 = 0.345394736842105

Note that using a 9 point degree of freedom, the same person signature is at 75% matching, but the different person ones are at 35%….

Pretty cool.  Next steps will be the adjust for slope and location on the canvas.  Also, Rob Seder suggested that the Line should include a DateTime stamp, because the meter/pace of someone’s signature is also important.  I’ll add that analysis in too – as well as a line comparison….