## Introduction

The PCA matching algorithm analyzes data coordinates from n dimensions, and returns an orthogonal coordinate representing the main deviation of the data.

The coordinate of the main deviation of the data represents the direction of the given coordinate's density. This information can be useful to minimize the amount of dimensions with minimal loss of data, for lossy compression.

Another use is to align two sets of data that parametrically differ, like aligned, back rotated/scaled/placed shapes.

## Background

The Principal Components Analysis (a.k.a. PCA algorithm) 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 and depends only on the Matrix library implementation provided with the “Shape matching framework” solution. We can easily isolate those two projects/DLLs to get just the functionality of this algorithm.

There are two methods of usage for this library: One is using the ‘plain’ PCA algorithm to extract drawings’ coordinate’s properties. The other is using the provided matching algorithm to optimize the target drawing closer to the source.

## Using the code

In the PCA project, there is a PCAtransform implementation which is the plain, by-the-book implementation. This gives us a set of Eigen values and corresponding set of Eigenvectors returned as a `DoubleMatrix`

. From those two parameters, we can deduce the relative angle and the relative density of the two calculated inputs.

In the following example, we will find that two rotated sets of coordinates can be identified as rotated, using two PCA transforms.

We’ll also see that density (same as scaling) factors are identical for both inputs, which will point to the fact that both inputs shouldn’t be scaled in order to be consolidated.

Note, if scaling needed, use the square roots of the scaling factors that the PCA transform finds.

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;
namespace New_Project
{
static class Program
{
[STAThread]
static void Main()
{
double angle = Math.PI/180 * 30; DoubleMatrix rotationMatrix = PrepareRotationMatrix(angle);
DoubleMatrix matrix1 = new DoubleMatrix(2, 3);
matrix1[0, 0] = 1;
matrix1[0, 1] = 2;
matrix1[0, 2] = 3;
matrix1[1, 0] = 4;
matrix1[1, 1] = 5;
matrix1[1, 2] = 6;
DoubleMatrix matrix2 = new DoubleMatrix((Matrix<double>)matrix1.Clone());
matrix2 = rotationMatrix * matrix2;
PCAtransform transform1 = new PCAtransform(matrix1);
PCAtransform transform2 = new PCAtransform(matrix2);
DoubleMatrix eigenVects1 = transform1.Calculate();
DoubleMatrix eigenVects2 = transform2.Calculate();
double absAngle1 = Math.Atan(eigenVects1[1, 0] / eigenVects1[0, 0]);
double absAngle2 = Math.Atan(eigenVects2[1, 0] / eigenVects2[0, 0]);
double relativeAngle = absAngle2 - absAngle1; double anglesDiff = relativeAngle - angle;
double[] eigenVals1 = transform1.EigenValues;
double[] eigenVals2 = transform2.EigenValues;
}
private static DoubleMatrix PrepareRotationMatrix(double angle)
{
DoubleMatrix rotationMatrix = new DoubleMatrix(2);
rotationMatrix[0, 0] = Math.Cos(angle);
rotationMatrix[0, 1] = -1 * Math.Sin(angle);
rotationMatrix[1, 0] = Math.Sin(angle);
rotationMatrix[1, 1] = Math.Cos(angle);
return rotationMatrix;
}
}
}

The PCA transform is also good for data analysis and lossy compression. Since that was not the aim of my work, that will not be explained here. More information about such usages can be found in the internet. Suppose we only want to match a drawing or a coordinates set to a given source set; it can be more easily done using PCA matching. The data we use will be from the previous example.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using LiniarAlgebra;
using System.Drawing;
using System.Reflection;
using PCA;
namespace New_Project
{
static class Program
{
[STAThread]
static void Main()
{
double angle = Math.PI / 180 * 30; DoubleMatrix rotationMatrix = PrepareRotationMatrix(angle);
DoubleMatrix matrix1 = new DoubleMatrix(2, 3);
matrix1[0, 0] = 1;
matrix1[0, 1] = 2;
matrix1[0, 2] = 3;
matrix1[1, 0] = 4;
matrix1[1, 1] = 5;
matrix1[1, 2] = 6;
DoubleMatrix matrix2 = new DoubleMatrix((Matrix<double>)matrix1.Clone());
matrix2 = rotationMatrix * matrix2;
PCAMatching matching = new PCAMatching(matrix1, matrix2);
matching.Calculate();
DoubleMatrix result = matching.Result;
double calculatedAngle = matching.AngleFromSource;
}
}
}

## Points of interest

This algorithm opened my mind in some ways. Before starting coding, I didn't imagine that there would be a matching algorithm that does the job with such great complexity (O(n)). Of course, it has its own disadvantages, but this is a good start.

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 matches shapes even greater: