PCA for Image Registration

[fdncred]

What would you like to submit? (put an 'x' inside the bracket that applies)

• [x] question
• [ ] bug report
• [x] feature request

Issue description

@cesarsouza Do you have any samples of using PCA for image matching or registration? I was looking at these links below and was wishing Accord.Net did something like this.

https://sites.google.com/site/smfmproject/the-algorithms-2/principal-component-analysis---pca https://www.codeproject.com/Articles/42660/Matching-and-Analyzing-Using-Principal-Component-A

Thanks, Darren

[blaisexen]

@fdncred,

Hi, I have a demo of accord that may fit your needs, just to show you how good accord framework is: http://www.mediafire.com/file/crwb2bpmvopqquf/Blaise_Imager.exe

if your AV tells it's harmful program, it's a false alarm, it's accord framework.

[fdncred]

@blaisexen Thanks for the download. Unfortunately, when I extract it I just see another exe and some jpg files. The exe doesn't appear to be dotNet so I don't understand how it's using accord-net-framework. Please explain.

The link above and file from mediafire.com are suspicious and I wouldn't advise anyone downloading and running it. It appears to be c/c++ compiled, obfuscated and packed to prevent investigation. Thanks but no thanks.

[blaisexen]

hi, the accord.NET framework I used was protected by this: http://enigmaprotector.com/en/downloads.html

so anyone would like to use a decompiler to get how I did, can't get it!

[blaisexen]

But did you test it well, the temporary image I put for example is the cards, or poker cards.... you can find the comparing images under programfiles\blaiseimager\sampletest to proceed your testing and SEE how good is accord framework....

you can also change the images inside the "resources" folder so it can be train and compare another images.

I hope you like it and believed that accord framework is very good.

[blaisexen]

and for example for cards.... you can compare or search the image with a piece of area in that image...

for example the King Diamond.... you can just copy paste a part of the single King sign and the Diamond sign, not the whole image.

try it to believed it!

:dancer:

[fdncred]

@blaisexen I didn't test it at all. I'm not going to run an exe from an unknown source, especially mediafire.com. I extracted the files without installing it and investigated the exe before trying to run with IDA. It seems as if you're trying to help but without source code it's not really helpful.

[blaisexen]

I'm sorry I miss understand!

[cesarsouza]

Hi everyone,

@blaisexen Thanks a lot for trying to help! However I have to agree with @fdncred: offering people to download and run an executable they do not really know anything about is not that much helpful, and from their perspective it might look like you are trying to trick them into installing malware. As such, I think that providing code examples would be of more help. But thanks for the willingness to help, in any case!

@fdncred If I understood correctly, the article you linked is actually dealing with shape matching (i.e. matching sequences of (x,y) coordinate pairs) instead of image matching. Is this what you need? If yes, then I think it could be done using the existing PrincipalComponentAnalysis classes, but I do not know when I would be able to write a sample for this.

However, if you are indeed looking for examples using PCA for image matching and registration, then I think I might need some additional references. I think the method can be made to work with images if we extract interest points from them and consider those points as the image's "shape", but this is not something that I have seen before.

Regards, Cesar

[fdncred]

@blaisexen I understand your points and did not mean to offend you. If you notice my question, I asked @cesarsouza if he had a sample. Again, not trying to offend you, but providing an exe isn't really helpful. I already know that PCA can be used this way and I have other source code that demonstrates this, although I believe Accord's implementation would probably be better. It's great that you've figured out how to do this but you didn't give any hints or tips of how to do this. I think that you and I are mostly in agreement. Are there any tips you'd provide as a starting point for registration and image matching with Accord and PCA?

[fdncred]

@cesarsouza I agree that those links are talking about shape matching however, I see little difference between what I'd like to do and what these samples do. If you start with the assumption that I'm working with bitonal images and look at the attached source code. You'll see that it appears to be similar.

The author is taking a source and target image and "ExtractPoints()" is run that pulls out all the black pixels into a List< Point >(). Then turns that into source and target Matrices. Then applies his PCA algorithms to calculate and get results. The results object appears to have all the information needed to "register" an image. i.e. If I have an "anchor" image (50x50 pixels, for instance), I should be able to find that same "anchor" on a target image (8.5 x 11 inches) and understand the transformation needed to align the two images.

Another way to think of it is that I'm trying to align two 8.5x11 inch images on top of each other with an understanding that these images will be slightly different due to hardware scanners. If I can understand how these images could be precisely aligned then I can understand where all the other items on the image are relative to this "anchor" that I originally used for alignment. Does that make any sense?

ShapeMatchingFrameWork.zip

[cesarsouza]

Hi @fdncred,

If you are working with monochromatic images then yes, it should be straightforward to reproduce that code using CollectActivePixels and the default PCA. However, I do not have any samples on that at this moment.

Using CollectActivePixels, you can get the (x,y) coordinates of all white pixels in an image (if you need the black pixels, you can invert the image beforehand using the Invert filter). Then, you can transform those lists of IntPoint into double[][] arrays that you will be able to feed to PrincipalComponentAnalysis (posssibly using Matrix.Apply). Then you would need to create two PCA objects, one after each matrix, then retrieve the ComponentVectors matrix for each of them (they are the Eigenvector matrices) and perform the same computations performed in the linked article.

If this approach indeed works well, I would be glad to add it to the framework, but I am not sure when I would have time to add such feature in the near future. However, if you would like to, I could totally accept a pull request implementing this functionality if you would be willing to submit it as a contribution!

Regards, Cesar

[fdncred]

Hi @cesarsouza ,

Thanks for the tips. I tried to follow your instructions. When you have a minute I'd appreciate you looking at the attached solution. I couldn't get the Accord.Net PCA results to match the other source code. I ended up writing a lot of code (or copy-n-pasting) that I'm sure your framework supports but I couldn't figure out how to use it. For instance, your ComponentVectors didn't look anything like the Eigenvectors I was expecting. Because of that, I included an entirely separate EigenLib set of classes.

You'll notice in the CalculatePCA() method there are several images to compare and only one set it uncomments. The "A" and the "Square" seems to work with this code but the others do not work as well.

This is a very minimal app and not one to include anywhere but it's a start. I won't have a problem contributing code once things get working but at this point, I'm stuck with it working on some images and not working on others.

Update The difference between it working and not working comes down to the differences between ExtractPoints() and CollectActivePixels(). ExtractPoints() allows you to pass in a threshold of Color in order to collect all pixels above that threshold. It defaults to Color.FromArgb(200,200,200). Once I remove the CollectActivePixels(), there's very little Accord left in the project. :(

Thanks, Darren

PCAMatching.zip

[cesarsouza]

Hi Darren,

Thanks for attaching the code. From a first look, I think the main reason why the ComponentVectors matrix didn't look like the Eigenvectors you were expecting was because the source and target matrices are organized as having dimensions as rows and observations as columns. Normally, those matrices should be organized as having dimensions as columns and observations as rows.

For example, if we are dealing with pixel coordinates, the matrices that PrincipalComponentAnalysis would be expecting should have looked like

new double[][] 
{
  //             X  Y
  new double[] { 0, 1 },
  new double[] { 1, 5 },
  new double[] { 2, 7 },
  new double[] { 7, 1 },
  new double[] { 0, 3 }
}

I will continue taking a look and see if I have more suggestions.

Regards, Cesar

[cesarsouza]

Also, the .Multiply was not working because I think the method that should have been used there was .Dot instead of Multiply. Dot computes matrix multiplication (dot vectors), whereas multiply computes a elementwise multiplication (I've just realized that the documentation was not helping, sorry about that!)

[cesarsouza]

It is very likely that the first part of the code could have computed by something like this:

            var srcPts = srcGray.CollectActivePixels();
            var tgtPts = tgtGray.CollectActivePixels();

            var srcMatrix = srcPts.Apply(p => new double[] { p.X, p.Y });
            var tgtMatrix = tgtPts.Apply(p => new double[] { p.X, p.Y });

            Size commonSize = new Size(Math.Max(srcImg.Width, tgtImg.Width), Math.Max(srcImg.Height, tgtImg.Height));

            var srcPCA = new PrincipalComponentAnalysis();
            var tgtPCA = new PrincipalComponentAnalysis();

            srcPCA.Learn(srcMatrix);
            tgtPCA.Learn(tgtMatrix);

            //Calculate the EigenVectors
            double[][] srcEigenVectors = srcPCA.ComponentVectors;
            double[][] tgtEigenVectors = tgtPCA.ComponentVectors;

            double[] srcEigenValues = srcPCA.Eigenvalues;
            double[] tgtEigenValues = tgtPCA.Eigenvalues;

            double[] srcAvgByDim = srcPCA.Means;
            double[] tgtAvgByDim = tgtPCA.Means;

            double[][] srcCenterPoints = srcMatrix.Subtract(srcAvgByDim, dimension: 0);
            double[][] tgtCenterPoints = tgtMatrix.Subtract(tgtAvgByDim, dimension: 0);

            //Calculate the Angle
            double srcAngle = Math.Atan(srcEigenVectors[0][0] / srcEigenVectors[0][1]);
            double tgtAngle = Math.Atan(tgtEigenVectors[0][0] / tgtEigenVectors[0][1]);
            double angle = Math.Abs(tgtAngle - srcAngle);

            //Calculate the Scale
            double scaleXBy = Math.Sqrt(srcEigenValues[0] / tgtEigenValues[0]);
            double scaleYBy = Math.Sqrt(srcEigenValues[1] / tgtEigenValues[1]);

However, I couldn't get everything working yet because I didn't understand very well what the ShiftToPositives method and the MinMax methods were trying to achieve. I can try to take another look tomorrow!

Regards, Cesar

[fdncred]

@cesarsouza Looking at this now. Hoping for the best.

[fdncred]

With your code, things look mostly in order except the math must be wrong for calculating the angles. I've noticed a lot of the Eigen arrays are reversed. These results are from the Letter A bitmap (element 0).

Old Way

• srcEigenVectors {double[2, 2]} double[,] [0, 0] -0.99894638422938964 double [0, 1] -0.045892498679293334 double [1, 0] -0.045892498679293334 double [1, 1] 0.99894638422938964 double

• tgtEigenVectors {double[2, 2]} double[,] [0, 0] -0.98384209150482926 double [0, 1] -0.1790383729355339 double [1, 0] -0.1790383729355339 double [1, 1] 0.98384209150482926 double

• srcEigenValues {double[2]} double[] [0] 559.74168144768191 double [1] 1766.8760065746014 double

• tgtEigenValues {double[2]} double[] [0] 1071.6254491451341 double [1] 2225.0447358995661 double

• srcAngle 1.524887703633008 double tgtAngle 1.3907873827757042 double angle 0.13410032085730372 double

• scaleXBy 0.72272373004120238 double scaleYBy 0.89111481307720319 double

Accord Way

• srcEigenVectors {double[2][]} double[][] [0] {double[2]} double[] [0] -0.045892498679293244 double [1] 0.99894638422938953 double [1] {double[2]} double[] [0] -0.99894638422938953 double [1] -0.045892498679293244 double

• tgtEigenVectors {double[2][]} double[][] [0] {double[2]} double[] [0] -0.17903837293553485 double [1] 0.98384209150482915 double [1] {double[2]} double[] [0] -0.98384209150482915 double [1] -0.17903837293553485 double

• srcEigenValues {double[2]} double[] [0] 1766.8760065746021 double [1] 559.74168144768225 double

• tgtEigenValues {double[2]} double[] [0] 2225.0447358995571 double [1] 1071.6254491451305 double

• srcAngle -0.0459086231618886 double tgtAngle -0.18000894401919335 double angle 0.13410032085730475 double

• scaleXBy 0.89111481307720519 double scaleYBy 0.72272373004120383 double

[fdncred]

Yup. This straightens out the angles.

    double srcAngle = Math.Atan(srcEigenVectors[1][0] / srcEigenVectors[1][1]);
    double tgtAngle = Math.Atan(tgtEigenVectors[1][0] / tgtEigenVectors[1][1]);
    double angle = Math.Abs(tgtAngle - srcAngle);

So, up to this point, your code is matching, minus some rounding errors. Now on to the rest of the code.

[cesarsouza]

Hi @fdncred,

If I can, may I ask if you did manage to get the rest of the code working?

Regards, Cesar

[fdncred]

Hey @cesarsouza, I played with it for a while and couldn't get it to do what I wanted. I was wanting to use this technology to do a better template matching object location. Unfortunately, even though I had a working sample, all I could get it to do was scale the two items I was comparing.

Think of it like this, I have a needle to find in a haystack. The haystack is obviously much larger than the needle. All I could get this shape matching technology to do was to scale the needle to the haystack or vice-versa. I couldn't figure out how to get it to locate the needle in the haystack unfortunately.

I probably could've got your code to work like the shape matching demo code but that wasn't my goal.

My goal still was to register an image and my approach was trying to do a PCA-like template match. I'm still looking. Normal template matching is too slow unless you scale things and then not accurate enough when the scale changes. I think I really need some feature extractor and feature matching for my needle in a haystack registration. But I digress.

Darren

[cesarsouza]

How many sample images of your needle do you have? And how many samples do you have of the different haystacks it could have been lost into?

[fdncred]

My proof of concept is to start with 1 1600 x 1500 image for the haystack. I then crop out a rectangle from it at 50,50 and 100 wide and 100 high. This image is the needle. If I search for this needle in this haystack, it should find it at 50,50 with 100% accuracy.

The next step is to try it on another image that is offset with a black border on the left of the image. When I search for the needle in this new haystack, I should find it at 50 X + width of black border and 50 Y.

In actuality, when I'm doing automatic positive exemplar training. I have a hand full of the haystack images that are all different but from the same category. I take a reasonable sample and carve it up into around ~800 needles, all the same size. I test/find all needles on all the positive exemplars. The intersection of all the found needles becomes the model of location rectangles to use as templates.

At this point, I should be able to find the model needles in any like category haystack image. If I find it, I should be able to determine the offset X and Y and that gives me a way to register.

[blaisexen]

@fdncred can you send your sample images that your testing, please.

sorry to bother you again,

[fdncred]

@blaisexen No problem. Unfortunately I have to redact the images but you should get the point. These images are TIFF Group IV files. Image *77.tif is the one that I crop out the rectangle at 50,50,100,100 to use as the needle and I try to find it in all 3 images.

California1.zip

[mshdiefat]

@fdncred and @cesarsouza and @blaisexen thanks for your keeping up this very helpful conversation about PCA, so after i read the whole conversation can you show how i can use Accord to Create a Covariance Matrix (for image recognition purpose )???? thanks in advance

[fdncred]

@mshdiefat Look back a few threads and you'll see PCAMatching.zip. That has a working example of shape matching and warping. That is what I was trying to port to Accord and for the most part it is complete following @cesarsouza 9/21 comment. However, I never finished the Accord port to match the code in PCAMatching.zip. It shouldn't be too difficult but I want it to do matching, as in reporting where it found a template, but the code is warping whatever you give it to match the template. So that is why I haven't moved forward with this. It's possible but it's beyond me at this point.

[cesarsouza]

Hi @mshdiefat,

Sorry for replying this late, but if all you want is to create a covariance matrix you can just use any of the Accord.Statistics.Measures.Covariance method overloads. An example is shown below:

double[,] matrix = Matrix.Magic(5); // let's say you have a 5x5 matrix of data values
double[,] cov = Accord.Statistics.Measures.Covariance(matrix); // this will create a 5x5 cov matrix

Regards, Cesar