使用形状上下文算法查找形状之间的相似性和差异

• 下载源码 - 62.28 KB 

引言

形状上下文算法从两个绘图中采样点，并根据每个点与其他点的角度视图生成直方图。直方图现在代表了这些点，用于匹配第一个绘图和第二个绘图中最高度匹配的点，最初是为了找到完美匹配。为了改进匹配，可以修改以扩大范围（目标点的数量）并保持匹配过程的结果唯一，但这次不是完美匹配。

背景

形状上下文匹配算法是“形状匹配框架”的一部分，该框架旨在为使用 .NET 环境构建绘图 - 相似性/差异软件提供核心支持。该项目仅使用并依赖于“形状匹配框架”解决方案提供的 Matrix 库实现。可以轻松地隔离这两个项目/DLL 以获得该算法本身的功能。该库有两种使用方法：一种是使用包含的函数以形成经典算法（如书籍中所述），另一种是使用提供的实现，该实现经过轻微修改并针对特定需求进行了定制。

Using the Code

在我看来，这个项目可以分为两个主要逻辑

• 第一个是匹配逻辑——目前从两个绘图中随机抽取点，并根据完美配对原则匹配最佳配对。当目标集更大时，算法可以选择更好的配对，但此时完美配对原则已不复存在。可以选择随机点的部分，通过委托替换为自定义逻辑。
• 第二部分是尝试将目标形状变为源形状。这里可以应用许多技术，我选择实现薄板样条（TPS）变换，简而言之，这是一种非仿射变换。这意味着我们可以几乎独立控制每个像素。给定源点和目标点，算法就像拉动一张“薄片”（类似于绘图的画布），从源拉到目标。当有很多匹配点时，会向不同方向拉动“薄片”，试图满足这些匹配点。

我必须承认，将这两个部分结合起来时会出现问题，因为匹配是基于邻近度的。存在一些不合理的交叉匹配。这可能会导致 TPS 变得不稳定，并导致结果失控。因此，应该应用一些正则化或纠正，这部分开放征求建议。让我们看一个简单的使用示例

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

我想仔细研究算法中存在问题的部分，即薄板样条（TPS）。获取最后示例的坐标，尝试将目标坐标变为源坐标

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

兴趣点 

这是我目前实现中最复杂的算法。它可能不适用于形状对齐，但它为那些想从 .NET 实现开始的人提供了一个良好的基础。当然，在项目的网站上可以找到更多信息和示例。请参阅下一节。

历史 

这个算法在某些方面拓宽了我的思路。在开始编码之前，我没想到会有一个 O(n) 的匹配算法能完成这项工作。当然，它也有其缺点，但这是一个不错的开始。本文及附带的项目是形状匹配框架的一部分，可以在这里找到。正如您所见，经过一些额外的努力，它可以更好地匹配形状