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

By , 27 Sep 2009

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

namespace New_Project
{
static class Program
{
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:

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

Votes of 3 or less require a comment

 Search this forum Profile popups    Spacing RelaxedCompactTight   Noise Very HighHighMediumLowVery Low   Layout Open AllThread ViewNo JavascriptPreview   Per page 102550
 First Prev Next
 My vote of 4 Kanasz Robert 6 Nov '12 - 2:29
 My vote of 5 valiantljk 11 Sep '10 - 16:59
 Great uvik 2 Jul '10 - 2:53