How do you calculate the Affinity Matrix of an image?

Question

I've been reading the formulas on how to compute the affinity matrix of an image and I'm a bit confused. Ideally, I would like to use color intensity as a distance metric.

I found this reference: http://spectrallyclustered.wordpress.com/2010/06/05/sprint-1-k-means-spectral-clustering/

Which seems to do a great job of explaining the general process. My question is with respect to the affinity matrix.

When constructing the affinity matrix (I'll call it A), they mention the affinity matrix should be KxK sized for a Kxn image. Other reference implementations say the affinity matrix for an MxN image should be (M*N) x (M*N):

http://www.mathworks.com/matlabcentral/fileexchange/26354-spectral-clustering-algorithms

Which one is the traditional approach?

When computing the affinity matrix, I wanted to know if each entry A(i,j) be a neighborhood computation (like the affinity of a 3x3 neighborhood or the pixels in the entire image)?

Or do I linearize the image into a 1 dimensional array.

Constructs an (m*n) x (m*n) matrix (the affinity matrix) and while iterating across the 1 dimensional image array, apply an affinity function to pixel i and every other pixel j. and stores the result into the affinity matrix.

(basically a double nested for loop)

am i off base? or is that about how it looks?

Thanks in advance,

ct

Answer 1

I think you are trying to use two distance metrics with a method that only supports one metric. An image has an implicit spatial metric between pixels, but the spectral clustering method does not handle this. It views an image as a bag of pixels.

Regarding M, N and K; M * N = K. Both expressions describe the number of objects that will be clustered, which in your case is the number of pixels.

The affinity matrix, A is a decimated version of the similarity matrix, S. E.g. if two objects/pixels are not similar enough, they are not adjacent.

One way tho construct the adjacency matrix is the following:

S(i, j) = color_intensity_distance( pixel(i), pixel(j) )

A(i, j) = exp( - S(i,j) ), if S(i,j) <= epsilon
A(i, j) = 0, otherwise

To improve your performance, you should search for a sparse matrix library. They are very efficient at handling matrices with many zeroes.

A link about spectral clustering.