Eigenvector computation using OpenCV

Question

I have this matrix A, representing similarities of pixel intensities of an image. For example: Consider a 10 x 10 image. Matrix A in this case would be of dimension 100 x 100, and element A(i,j) would have a value in the range 0 to 1, representing the similarity of pixel i to j in terms of intensity.

I am using OpenCV for image processing and the development environment is C on Linux.

Objective is to compute the Eigenvectors of matrix A and I have used the following approach:

static CvMat mat, *eigenVec, *eigenVal;
static double A[100][100]={}, Ain1D[10000]={};
int cnt=0;

//Converting matrix A into a one dimensional array
//Reason: That is how cvMat requires it
for(i = 0;i < affnDim;i++){
  for(j = 0;j < affnDim;j++){
 Ain1D[cnt++] = A[i][j];
  }
}

mat = cvMat(100, 100, CV_32FC1, Ain1D); 

cvEigenVV(&mat, eigenVec, eigenVal, 1e-300);

for(i=0;i < 100;i++){
  val1 = cvmGet(eigenVal,i,0); //Fetching Eigen Value

  for(j=0;j < 100;j++){   
 matX[i][j] = cvmGet(eigenVec,i,j); //Fetching each component of Eigenvector i    
  }
}

Problem: After execution I get nearly all components of all the Eigenvectors to be zero. I tried different images and also tried populating A with random values between 0 and 1, but the same result.

Few of the top eigenvalues returned look like the following:

9805401476911479666115491135488.000000  
-9805401476911479666115491135488.000000  
-89222871725331592641813413888.000000  
89222862280598626902522986496.000000  
5255391142666987110400.000000

I am now thinking on the lines of using cvSVD() which performs singular value decomposition of real floating-point matrix and might yield me the eigenvectors. But before that I thought of asking it here. Is there anything absurd in my current approach? Am I using the right API i.e. cvEigenVV() for the right input matrix (my matrix A is a floating point matrix)?

cheers

Hurwitz

Haven't really used eig/svd in openCV but isn't it true that the eigenvalues returned should be sorted? – Holocene

Yes, that is correct. I have just put up the top 5 eigenvalues returned and in terms of magnitude they are in order (largest to smallest). In terms of sign they are not. But the sign just indicates the orientation of the vector, so I presume the eigenvalues are ok. Just concerned about the eigenvectors. – Hurwitz

oh forgot about the sign! well according to the documentation, an epsilon value of 1e-15 is enough (you are using eps=1e-300). Could that cause the problem? Also isnt it true that we can usually expect that only the first few largest eigenvectors account for much of the variance of the data? – Holocene

yep, I started off with 1e-15 and then meandered to the current value. But couldn't get much of a change. Yes, in fact my ultimate objective is to do spectral clustering of the input image. To do that I'm feeding the top N eigenvectors to k-means clustering algorithm. But as almost all are coming to be 0, almost all get clustered to the same cluster. – Hurwitz

you might want to check the results by doing the same calculation in a numerical package like MATLAB or Octave. Can I ask how exactly do you compute the similarity matrix between each pair of pixels? I would be happy to try this on a sample image in MATLAB.. – Holocene

well, I would have loved to do that but apparently I don't know MATLAB. I'm using Gaussian Kernel to compute the similarity and referring to the Spectral Clustering algorithm by Andrew Ng. Please find it here eprints.kfupm.edu.sa/54643/1/54643.pdf . Page 2 has the algorithm. Step 1 of the algorithm mentions the Gaussian kernel used to compute the similarity between two pixels. I have used pixel intensities for Si, Sj and standard deviation for the denominator i.e. sigma^2. I have excluded intensities of pixel i and j while computing sigma. – Hurwitz

I don't know anything about openCV, but it looks like you're passing two uninitialized pointers (eigenVec and eigenVal) to cvEigenVV(). But maybe you skipped the init code for shortness. – Waylonwayman

@Andriyev I am currently working on a similar project and I am required to find the eigenvalues and eigenvectors of a matrix. I have been looking at the cvEigenVV function that you used in the code. Unfortunately, I am required to use openCV and C++ in my project and do not have the option of switching to Matlab. Can you just explain to me why you put in this piece of your code?for(i = 0;i < affnDim;i++){ for(j = 0;j < affnDim;j++){ Ain1D[cnt++] = A[i][j]; } } What was the purpose of doing this first? Please get back to me asap if possible. – Bays

Answer 1

Note to readers: This post at first may seem unrelated to the topic, but please refer to the discussion in the comments above.

The following is my attempt at implementing the Spectral Clustering algorithm applied to image pixels in MATLAB. I followed exactly the paper mentioned by @Andriyev:

Andrew Ng, Michael Jordan, and Yair Weiss (2002). On spectral clustering: analysis and an algorithm. In T. Dietterich, S. Becker, and Z. Ghahramani (Eds.), Advances in Neural Information Processing Systems 14. MIT Press

The code:

%# parameters to tune
SIGMA = 2e-3;       %# controls Gaussian kernel width
NUM_CLUSTERS = 4;   %# specify number of clusters

%% Loading and preparing a sample image
%# read RGB image, and make it smaller for fast processing
I0 = im2double(imread('house.png'));
I0 = imresize(I0, 0.1);
[r,c,~] = size(I0);

%# reshape into one row per-pixel: r*c-by-3
%# (with pixels traversed in columwise-order)
I = reshape(I0, [r*c 3]);

%% 1) Compute affinity matrix
%# for each pair of pixels, apply a Gaussian kernel
%# to obtain a measure of similarity
A = exp(-SIGMA * squareform(pdist(I,'euclidean')).^2);

%# and we plot the matrix obtained
imagesc(A)
axis xy; colorbar; colormap(hot)

%% 2) Compute the Laplacian matrix L
D = diag( 1 ./ sqrt(sum(A,2)) );
L = D*A*D;

%% 3) perform an eigen decomposition of the laplacian marix L
[V,d] = eig(L);

%# Sort the eigenvalues and the eigenvectors in descending order.
[d,order] = sort(real(diag(d)), 'descend');
V = V(:,order);

%# kepp only the largest k eigenvectors
%# In this case 4 vectors are enough to explain 99.999% of the variance
NUM_VECTORS = sum(cumsum(d)./sum(d) < 0.99999) + 1;
V = V(:, 1:NUM_VECTORS);

%% 4) renormalize rows of V to unit length
VV = bsxfun(@rdivide, V, sqrt(sum(V.^2,2)));

%% 5) cluster rows of VV using K-Means
opts = statset('MaxIter',100, 'Display','iter');
[clustIDX,clusters] = kmeans(VV, NUM_CLUSTERS, 'options',opts, ...
    'distance','sqEuclidean', 'EmptyAction','singleton');

%% 6) assign pixels to cluster and show the results
%# assign for each pixel the color of the cluster it belongs to
clr = lines(NUM_CLUSTERS);
J = reshape(clr(clustIDX,:), [r c 3]);

%# show results
figure('Name',sprintf('Clustering into K=%d clusters',NUM_CLUSTERS))
subplot(121), imshow(I0), title('original image')
subplot(122), imshow(J), title({'clustered pixels' '(color-coded classes)'})

... and using a simple house image I drew in Paint, the results were:

and by the way, the first 4 eigenvalues used were:

1.0000
0.0014
0.0004
0.0002

and the corresponding eigenvectors [columns of length r*c=400]:

-0.0500    0.0572   -0.0112   -0.0200
-0.0500    0.0553    0.0275    0.0135
-0.0500    0.0560    0.0130    0.0009
-0.0500    0.0572   -0.0122   -0.0209
-0.0500    0.0570   -0.0101   -0.0191
-0.0500    0.0562   -0.0094   -0.0184
......

Note that there are step performed above which you didn't mention in your question (Laplacian matrix, and normalizing its rows)

Holocene

That looks awesome. Yeah, I just skipped the Laplacian and normalization steps from my question just to keep it to the point. Well, now may be I have a good reason to learn MATLAB. Thanks for the guidance and effort on your part. – Hurwitz

The truth is I was reading on the subject of kernel PCA myself which is very similar, and I found this an opportunity to understand it better by coding it.. and that's one of the things I love about MATLAB; you can implement an algorithm like this rather quickly and in only a few lines! (compared to coding in C) – Holocene

Answer 2

I would recommend this article. The author implements Eigenfaces for face recognition. On page 4 you can see that he uses cvCalcEigenObjects to generate the eigenvectors from an image. In the article the whole pre processing step necessary for this computations are shown.

Palp

Dear Janusz, I am working on a similar project at the moment and after reading your answer, I looked for the documentation forcvCalcEigenObjects. However, when both the openCV reference manual and the O'Reilly - Learning openCV was searched, that function was not in there. Do you possible know if it it outdated? – Bays

Answer 3

Here's a not very helpful answer:

What does theory (or maths scribbled on a piece of paper) tell you the eigenvectors ought to be ? Approximately.

What does another library tell you the eigenvectors ought to be ? Ideally what does a system such as Mathematica or Maple (which can be persuaded to compute to arbitrary precision) tell you the eigenvectors ought to be ? If not for a production-sixed problem at least for a test-sized problem.

I'm not an expert with image processing so I can't be much more helpful, but I spend a lot of time with scientists and experience has taught me that a lot of tears and anger can be avoided by doing some maths first and forming an expectation of what results you ought to get before wondering why you got 0s all over the place. Sure it might be an error in the implementation of an algorithm, it might be loss of precision or some other numerical problem. But you don't know and shouldn't follow up those lines of inquiry yet.

Regards

Mark

Thumb