使用 Hausdorff 距离算法找出两幅图画之间的差异

• 下载源代码 - 47 KB

引言

Hausdorff 距离定义了一个像素（或位置）的值为到最近像素（或位置）的距离。当从两张图像中提取二值图，并使用 Hausdorff 距离来尝试指出它们之间的差异时，可以使用此特性。

背景

基于 Hausdorff 距离的匹配是“形状匹配框架”的一部分，旨在为使用 .NET 构建图纸相似性/差异性软件提供核心支持。该项目使用了“形状匹配框架”解决方案提供的矩阵库实现，并且仅依赖于它。我们可以轻松地隔离这两个项目/DLL，以仅获得此算法的功能。

该实现包含一些使用约定：一个“纯粹”算法按照“书本”中的基本算法实现，而一个匹配算法使用该基本算法来获取两张图片，以便指出差异。

使用代码

该项目与其他两个算法项目不同之处在于，它不尝试使第二个（目标）形式更接近第一个（源）形式。Hausdorff 算法只有几种方法可以指出和标记差异，并以某种方式衡量这些差异。现在，我们将看到一种指出两张二值图之间差异的方法

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.
        }
    }
}

示例中未涵盖的另一种方法称为 CalculateTwoSides()。它与获取两个结果 oneOnTwo 和 twoOnOne 并将一个加到另一个上相同，因此每个单元格都是来自示例的一侧计算的单元格之和。

关注点

更容易发现两种形状之间的差异；当然，它限制为一种颜色。但是，这里有一种增强它的方法，只需将彩色图片拆分为按所需精度划分的颜色二值图即可。

本文和包含的项目是形状匹配框架的一部分，可以在 http://sites.google.com/site/smfmproject/ 找到。正如您所看到的，通过一些额外的努力，它可以更好地匹配形状