Sign in to follow this  
serratemplar

comparing matrices (little statistics experience)

Recommended Posts

Here is a gross simplification of my problem: I have two 3x3 matrices full of numbers. I need to determine how "close" these two matrices are to containing the same numbers in the same places. Right now I take 3rd dimension vectors that have the same x,y coords, I take the absolute values of the differences between each value in these vectors, them sum those differences up. I do that for every 3rd dim vector, and then sum them all up. It's sort of a hacked-Euclidean distance between the two of them. (I've tried squaring instead of absolute value and taking the squareroot of the entire thing at the end, which is more like the traditional distance formula; this also isn't producing the results I expect.) I don't suppose anyone could point me at a statistical method that I might try to learn and put to use? I admit I won't be taking statistics for another semester yet, however I've got quite a bit of other math under my belt (calc, linear algebra, and number theory); please don't feel the need to treat me gently. Thanks in advance.

Share this post


Link to post
Share on other sites
A matrix norm of the difference is the best you can do if you need to measure the similarity as a single number, but we can do better.

First, you need to tell us what you're comparing the matrices for. If they represent transformations, then some kind of eigen-decomposition would be appropriate, whereas if they simply store arrays of figures then all elements are born equal, and a statistical approach would be better.

Admiral

Share this post


Link to post
Share on other sites
This is a computer vision problem. I have a mask (my training data) that I'm comparing against regions within a large image in an effort to find what my training data represents.

I'm modeling both the training data and the testing data as color distribution vectors. Each pixel essentially becomes a normalized histogram containing counts of the instances of its color as well as the colors of the pixels around it (it's neighbors). I tally up the colors then divide by the number of them, leaving me with a local color distribution vector. The question I have is, given these two 3x3 matrices (one being the distribution field of the training data, the other a distribution field of the test data) I want to compare sub-regions of the test data to my training data...the one that is the "closest" (least distant) is very likely my target.

In case it is important, the images are arbitrarily sized (except of course that the training data/mask is significantly smaller than the test data/query image). Each histogram represents up to 64 "classes" of colors (down from 256^3...because keeping track of every individual color would be gross over-fitting).

I'm currently using an L1 norm comparison (the sum of the absolute values of the differences between each slot in these histograms - essentially the sum of Manhattan distances) to see how each pixel/distribution vector between the two images match up: a lesser difference (0 being ideal) meaning that they are very similar. I feel it stands to reason that if I sum up all of these L1 norms I would be left with a scalar that would represent the total comparison between my training and test data...and naturally that the region that produced the smallest would highly likely be my desired target.

This seems to be working, but it takes four hours.

I've pulled just about every trick out of the book that I know (interleaving bits into integers, bit shifting instead of dividing or multiplying everywhere I can, preprocessing as much as possible)...however when it comes down to it, the comparisons I can't optimize, because I don't know any math to do it. Distribution doesn't work over summing the absolute values of the differences, so far as I know.

I suppose I was hoping someone might suggest another metric I could use to compare these structures that might be more optimizable some how. (I've also considered trying to learn programmable shaders in OpenGL, so I could offload some of these comparisons onto my crazy gpu - I've heard that math software sometimes does this - but I felt if there was a simpler route I should explore that first instead.)

I hope that's more clear; if anyone has any more questions, please feel free to ask. I really appreciate whatever suggestions you might have. Thanks in advance.

Share this post


Link to post
Share on other sites
You lost me. You talk about distribution fields. Do you mean that you model a pixel so that the first random variable is the pixel itself and the second is the surrounding pixels and you form the 3x3 matrix by sampling the constructed probability distribution?

That doesn't sound right, so could you please elaborate what you mean by those 3x3 matrices..

Share this post


Link to post
Share on other sites
Have you profiled your code to see what's taking the longest? Don't optimize the comparison unless you need to; it seems like it's currently a fast, straightforward comparison method. Usually you'll get far better results trying to change your algorithm from O(n^4) to O(n^3) than from any amount of low-level bit twiddling, especially for computations like this.

Your current method of using the sum of absolute values of element-wise differences sounds like the fastest method to compare the two 3x3 matrices. Any method will have to include terms for each difference in some form or other; you'd likely only increase execution time by using a more advanced method. (You may be able to achieve higher accuracy according to some statistical measurements, but it won't be faster.)

In image processing, resolution makes a huge, huge difference. Cut the horizontal and vertical resolution in half, and suddenly your analysis is four times faster. In my experience with image processing (not extensive, but not trivial), it doesn't make a big difference in accuracy, either: usually every single pixel doesn't matter, and giving it way more data points than it needs will just make it take longer to calculate a result that isn't noticeably better. I imagine that could change if you're using input images that are highly detailed, such as text or small objects, though.

Also, GPU programming is crazy fast. I did a little bit of it (a fractal renderer), and even my modest laptop graphics card could render fractals at least an order of magnitude faster than my CPU. It wasn't that hard, either.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this