Introduction
The shape context algorithm samples points from both drawings and generates histograms based on the angular view of each point to others. The histograms, now representing the points, are used to match the most suited point from the first drawing and the second drawing, and are originally made to find a perfect match. In order to improve the matching, modification can be done to enlarge the range (the number of the target points) and keep the results of the matching process unique, but this time not a perfect match.
Background
The shape context matching algorithm is part of the “Shape matching framework” designed to provide core support when building a drawing - similarity/difference software using .NET environment. The project uses and depends only on the Matrix library implementation provided with “Shape matching framework” solution. One can easily isolate those two projects/DLLs to get the functionality of this algorithm alone. There are two methods of usage for this library: one is using the included functions in order to form a classic algorithm (as seen in books), the other is using the provided implementation which is slightly modified and tailored for specific needs.
Using the Code
From my point of view, this project can be divided into two main logics:
- The first is a matching logic – currently taking random points from both drawings and matching best suites according to perfect pairing principle. When the target set is bigger, the algorithm has the freedom to choose better suites but this time perfect pairing principle has vanished. The part that selects points randomly can be replaced by self created logic using delegates.
- The second part is trying to bring the target shape to be the source. There are many types of techniques that can be applied here, I chose to implement Thin Plate Spline (TPS) transformation which in short explanation is a non affine transformation. It means that we almost have a control on each pixel separately. Having source point and a target point, the algorithm is like pulling a ‘sheet’ (like a canvas of the drawing) from source to the target. Having many matches, pulling the ‘sheet’ to different directions, trying to satisfy the matches.
I'll make a confession, there is an issue when trying to get those parts to work together, since the matches are proximity based. There are cross matches that don't justify themselves. This probably causes TPS to be nervous and take the result out of control. So some regularization or correction should be applied, this part is open for suggestions. Let’s see a simple example of usage:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using LiniarAlgebra;
using Adaption;
using System.Drawing;
using System.Reflection;
using ShapeContext;
namespace New_Project
{
static class Program
{
[STAThread]
static void Main()
{
Point[] sources = {
new Point(1,1),
new Point(1,3),
new Point(1,6),
new Point(3,6),
new Point(6,6),
new Point(6,3),
new Point(6,1),
new Point(3,1)
};
Point[] targets = {
new Point(9,8),
new Point(9,3),
new Point(4,1),
new Point(4,3),
new Point(6,1),
new Point(6,6),
new Point(9,1),
new Point(4,6)
};
Size surfaceSize = new Size(15,15);
SelectSamplesDelegate selectionLogic = (points, numOfPoints) => points;
ShapeContextMatching matching =
new ShapeContextMatching(sources, targets, surfaceSize, selectionLogic);
matching.DistanceTreshold = 20;
matching.Calculate();
Point[] resultSamples = matching.LastTargetSamples;
Point[] TransformedResult = matching.ResultPoints;
}
}
}
I would like to examine the problematic part of the algorithm, the thin plate spline (TPS). Taking the coordinates of the last examples, trying to bring the target coordinates to the source:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using LiniarAlgebra;
using Adaption;
using System.Drawing;
using System.Reflection;
using ShapeContext;
namespace New_Project
{
static class Program
{
[STAThread]
static void Main()
{
DoubleMatrix sources = new DoubleMatrix(8,2);
sources[0,0] = 1; sources[0,1] = 1;
sources[1,0] = 1; sources[1,1] = 3;
sources[2,0] = 1; sources[2,1] = 6;
sources[3,0] = 3; sources[3,1] = 6;
sources[4,0] = 6; sources[4,1] = 6;
sources[5,0] = 6; sources[5,1] = 3;
sources[6,0] = 6; sources[6,1] = 1;
sources[7,0] = 3; sources[7,1] = 1;
DoubleMatrix targets = new DoubleMatrix(8,2);
targets[0, 0] = 4; targets[0, 1] = 1;
targets[1, 0] = 4; targets[1, 1] = 3;
targets[2, 0] = 4; targets[2, 1] = 6;
targets[3, 0] = 6; targets[3, 1] = 6;
targets[4, 0] = 9; targets[4, 1] = 9;
targets[5, 0] = 9; targets[5, 1] = 3;
targets[6, 0] = 9; targets[6, 1] = 1;
targets[7, 0] = 6; targets[7, 1] = 1;
Point[] targetPoints = {
new Point(9,9),
new Point(9,3),
new Point(4,1),
new Point(4,3),
new Point(6,1),
new Point(6,6),
new Point(9,1),
new Point(4,6)
};
Size surfaceSize = new Size(15, 15);
TPS tpsTransform = new TPS(surfaceSize);
tpsTransform.Calculate(targets, sources);
tpsTransform.Interpolate(ref targetPoints);
}
}
}
Points of Interest
This is a most complicated algorithm among my other implementations yet. Maybe it does not work perfectly with shape alignment, but it provides a good base for those who want to start with something using .NET implementation. Of course, more information and examples can be found at the project's site. See the next section for it.
History
This algorithm opened my mind in some ways. Before starting coding, I didn't imagine that there would be a matching algorithm that does the job with such great complexity (O(n)). Of course, it has its own disadvantages, but this is a good start. This article and the included projects are part of the Shape-Matching framework that can be found here. As you can see, with some additional work, it matches shapes even better:
