Click here to Skip to main content
15,868,016 members
Articles / Desktop Programming / Win32

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

Rate me:
Please Sign up or sign in to vote.
4.28/5 (8 votes)
27 Sep 2009MIT2 min read 35.7K   1K   25   4
This algorithm provides a good way to know the location and difference factor of two drawings.

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

logo.jpg

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:

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

Hausdorffcap.JPG

License

This article, along with any associated source code and files, is licensed under The MIT License


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

Comments and Discussions

 
GeneralMy vote of 4 Pin
Kanasz Robert6-Nov-12 2:29
professionalKanasz Robert6-Nov-12 2:29 
GeneralMy vote of 5 Pin
valiantljk11-Sep-10 16:59
valiantljk11-Sep-10 16:59 
GeneralGreat Pin
uvik2-Jul-10 2:53
uvik2-Jul-10 2:53 
GeneralLinks Pin
fredmn6-Oct-09 23:17
fredmn6-Oct-09 23:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.