13,094,732 members (97,289 online)
alternative version

#### Stats

32.6K views
36 bookmarked
Posted 29 Sep 2009

# Using Shape Context Algorithm to Find Similarity and Difference Between Shapes

, 29 Sep 2009
 Rate this:
Using provided Shape context algorithm and infrastructure, there is a wide base to match shapes.

## 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 System.Drawing;
using System.Reflection;
using ShapeContext;

namespace New_Project
{
static class Program
{
static void Main()
{
Point[] sources = {
new Point(1,1),    // We creating something like
// this shape
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),    //  We creating something
//  like the previous but
new Point(9,3),    //  with some displacements
//  and order mess
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); //Choosing big enough
//canvas size to see the result

//Creating identity function 1 to 1 selection, no reduction is made here
SelectSamplesDelegate selectionLogic = (points, numOfPoints) => points;

//Creating a matching object with all necessary data
ShapeContextMatching matching =
new ShapeContextMatching(sources, targets, surfaceSize, selectionLogic);

//setting euclid restriction for TPS transformation
matching.DistanceTreshold = 20;
//Now calculating
matching.Calculate();

Point[] resultSamples = matching.LastTargetSamples;
//We can see that the algorithm placed the points
//in matching order corresponding to sources
//resultSamples(debug print as column)  ,  and the sources (as column)
//    {X = 4 Y = 1}                                <--(1,1)
//    {X = 4 Y = 3}                                <--(1,3)
//    {X = 9 Y = 1}                                <--(1,6)
//    {X = 6 Y = 1}                                <--(3,6)
//    {X = 9 Y = 8}                                <--(6,6)
//    {X = 9 Y = 3}                                <--(6,3)
//    {X = 6 Y = 6}                                <--(6,1)
//    {X = 4 Y = 6}                                <--(3,1)

Point[] TransformedResult = matching.ResultPoints;

//There was some improvement but also unwanted effect of (5,5)
//in wrong direction
//{X = 7 Y = 6}
//{X = 8 Y = 3}
//{X = 4 Y = 2}         *
//{X = 4 Y = 3}      *
//{X = 6 Y = 2}    *
//{X = 5 Y = 5}    *     *
//{X = 8 Y = 2}    *  *  *
//{X = 4 Y = 4}
}
}
}```

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 System.Drawing;
using System.Reflection;
using ShapeContext;

namespace New_Project
{
static class Program
{
static void Main()
{
DoubleMatrix sources = new DoubleMatrix(8,2);
sources[0,0] = 1; sources[0,1] = 1;    //  We creating something
//  like this shape
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;    //  We creating something
//  like the first but
targets[1, 0] = 4; targets[1, 1] = 3;    //  with a some displacements
//  and order mess
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); //Choosing big enough canvas
//size to see the result

TPS tpsTransform = new TPS(surfaceSize);
tpsTransform.Calculate(targets, sources);

tpsTransform.Interpolate(ref targetPoints);
//The result (targetPoints) is
//{X = 6 Y = 6}
//{X = 8 Y = 0}
//{X = 4 Y = 0}
//{X = 5 Y = 0}
//{X = 6 Y = 0}
//{X = 6 Y = 3}
//{X = 8 Y = 0}
//{X = 4 Y = 3}
//There is no point to try and draw what we got
//This is very aggressive transformation,
//since there are a lot of points that
//pull to the left.
}
}
}```

## 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:

## Share

 Software Developer Israel
A student for a first degree (BSC) in Computer Science.
Working as software developer in a local software company.

## You may also be interested in...

 Pro Pro

 First Prev Next
 Code does not work phucborso116-Sep-13 18:08 phucborso1 16-Sep-13 18:08
 My vote of 4 Kanasz Robert6-Nov-12 0:03 Kanasz Robert 6-Nov-12 0:03
 My vote of 5 alifellod19-Sep-10 1:45 alifellod 19-Sep-10 1:45
 Linear Algebra and Not Liniar uvik2-Jul-10 3:22 uvik 2-Jul-10 3:22
 Re: Linear Algebra and Not Liniar yanirta3-Jul-10 2:22 yanirta 3-Jul-10 2:22
 No client GUI, how to call the dll? Thanks. rufj20-Apr-10 22:42 rufj 20-Apr-10 22:42
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Aug-17 8:59 Refresh 1