Using Shape Context Algorithm to Find Similarity and Difference Between Shapes

• Download source - 62.28 KB 

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),    // 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)
                                        
            //As about TPS based transformation 
            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 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;    //  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: