Using the Hausdorff distance algorithm to point out differences between two drawings

• Download source code - 47 KB

Introduction

The Hausdorff distance defines a value of a pixel (or location) to be the distance to the most nearest pixel (or location). This feature can be used when taking two binary maps, extracted from two images, and using Hausdorff distance to try and point on the differences between them.

Background

The Hausdorff – Distance based matching is part of the “Shape matching framework” designed to provide core support when building a drawing - similarity/difference software using .NET. The project uses a Matrix library implementation provided with the “Shape matching framework” solution and depends only on it. We can easily isolate those two projects/DLLs to get just the functionality of this algorithm.

The implementation includes a few conventions of usage: A ‘plain’ algorithm implements the basic algorithm ‘by the book’, and a matching algorithm uses that basic algorithm to take two pictures in order to point out the differences.

Using the code

This project differs from the other two algorithm projects in a way that it is not trying to bring the second (target) form to be closer to the first (source). The Hausdorff algorithm only has a few ways to point and mark the differences as well as to measure those differences in some way. Now, we will see a way to point out differences between two binary maps:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using LiniarAlgebra;
using Adaption;
using System.Drawing;
using System.Reflection;
using PCA;
using HausdorffDistance;

namespace New_Project
{
    static class Program
    {
        [STAThread]
        static void Main()
        {
            //Creating a 10x10 IntMatrix with blueprint of a plus ('+') drawing
            IntMatrix binaryMap1 = new IntMatrix(10);
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   1   1   0   0   0   0
            //  0   0   0   0   1   1   0   0   0   0
            //  0   0   1   1   1   1   1   1   0   0
            //  0   0   1   1   1   1   1   1   0   0
            //  0   0   0   0   1   1   0   0   0   0
            //  0   0   0   0   1   1   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0

            for (int i = 2; i < 8; i++)
        {
                //Vertical ribbon
        binaryMap1[i, 4] = 1;
                binaryMap1[i, 5] = 1;
                //Horizontal ribbon
                binaryMap1[4, i] = 1;
                binaryMap1[5, i] = 1;
        }

            //Creating a 10x10 IntMatrix with blueprint of a minus ('-') drawing
            IntMatrix binaryMap2 = new IntMatrix(10);
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   1   1   1   1   1   1   0   0
            //  0   0   1   1   1   1   1   1   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            for (int i = 2; i < 8; i++)
        {
                //Horizontal ribbon
                binaryMap2[4, i] = 1;
                binaryMap2[5, i] = 1;
        }

            //Creating an Hausdorff matching object with already prepared binary maps
            HausdorffMatching matching = new HausdorffMatching(binaryMap1, binaryMap2);
            //Next we will calculate for how much 
            //the first map is differ from the second
            IntMatrix oneOnTwo = matching.Calculate1on2(); 
            // oneOnTwo will be:
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   2   2   0   0   0   0
            //  0   0   0   0   1   1   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   1   1   0   0   0   0
            //  0   0   0   0   2   2   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //It is easyly can be seen that the vertical 
            //edges of the plus sign are 2 cells away 
            // from the closest cell of the minus sign.
            //There is a surface of the plus sign that the minus 
            //cannot cover, as far as the edges goes
            // from the minus sign, so the bigger cells values in the result.
            IntMatrix twoOnOne = matching.Calculate2on1();
            // twoOnOne will be:
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //  0   0   0   0   0   0   0   0   0   0
            //Here you may see that the plus sign completely covers the minus sign.
            //Which means that there are no outstanding edges, 
            //so the result will remain a mesh of zeroes.
        }
    }
}

There is another way that the example hasn’t covered, it is called CalculateTwoSides(). It is identical to taking both the results oneOnTwo and twoOnOne and adding one to the other so each cell is the sum of the cells from one side calculations from the examples.

Points of interest

It is more easy to spot the differences between two shapes; of course there is a limitation on one color. But hey, here is a way to enhance this, just split a colored picture to a binary maps of colors by ranges with your desired accuracy.

This article and the included projects are part of the Shape-Matching framework that can be found at http://sites.google.com/site/smfmproject/. As you can see, with some additional work, it can match shapes even greater: