Calcul du vecteur propre en utilisant OpenCV

Question

J'ai cette matrice A, représentant les similitudes des intensités de pixels d'une image. Par exemple: Considérez une image 10 x 10. La matrice A dans ce cas serait de dimension 100 x 100, et l'élément A (i, j) aurait une valeur dans l'intervalle de 0 à 1, représentant la similarité des pixels i à j en termes d'intensité. J'utilise OpenCV pour le traitement d'image et l'environnement de développement est C sous Linux.

L'objectif est de calculer les vecteurs propres de la matrice A et je l'ai utilisé l'approche suivante:

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  
    } 
} 

Problème: Après l'exécution je reçois presque tous les composants de tous les vecteurs propres à zéro. J'ai essayé différentes images et j'ai aussi essayé de peupler A avec des valeurs aléatoires entre 0 et 1, mais le même résultat.

Peu de valeurs propres haut retournés se présenter comme suit:

9805401476911479666115491135488.000000 
-9805401476911479666115491135488.000000 
-89222871725331592641813413888.000000 
89222862280598626902522986496.000000 
5255391142666987110400.000000 

Je pense maintenant sur les lignes de l'utilisation cvSVD() qui effectue la décomposition en valeurs singulières de la matrice réelle à virgule flottante et pourrait me donner les vecteurs propres. Mais avant cela, j'ai pensé à le demander ici. Y a-t-il quelque chose d'absurde dans mon approche actuelle? Est-ce que j'utilise la bonne API, c'est-à-dire cvEigenVV() pour la bonne matrice d'entrée (ma matrice A est une matrice à virgule flottante)?

acclamations

Answer 1

Note aux lecteurs: Ce poste d'abord peut sembler sans rapport avec le sujet, mais s'il vous plaît se référer à la discussion dans les commentaires ci-dessus.

Voici ma tentative de mise en oeuvre de l'algorithme Spectral Clustering appliqué aux pixels d'image dans MATLAB. J'ai suivi exactement le paper mentionné par @Andriyev:

Andrew Ng, Michael Jordan et Yair Weiss (2002). Sur la classification spectrale: analyse et algorithme. Dans T. Dietterich, S. Becker et Z. Ghahramani (Eds.), Les progrès réalisés dans Neural Systèmes de traitement 14. MIT Press

Le 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)'}) 

...et en utilisant une image simple maison, je dessinais dans la peinture, les résultats étaient les suivants:

et par la manière, les 4 premiers valeurs propres utilisés étaient les suivants:

1.0000 
0.0014 
0.0004 
0.0002 

et les vecteurs propres correspondants [ colonnes de longueur 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 
...... 

Notez qu'il existe des étapes ci-dessus réalisées que vous ne l'avez pas mentionner dans votre question (matrice laplacienne, et normaliser ses rangées)

Answer 2

Je recommanderais ce article. L'auteur implémente des Eigenfaces pour la reconnaissance faciale. À la page 4, vous pouvez voir qu'il utilise cvCalcEigenObjects pour générer les vecteurs propres à partir d'une image. Dans l'article, toute l'étape de pré-traitement nécessaire pour ces calculs est montrée.

Answer 3

est ici un pas très utile réponse:

Qu'est-ce que la théorie (ou mathématiques griffonné sur un morceau de papier) vous dire les vecteurs propres devrait être? Approximativement.

Qu'est-ce qu'une autre bibliothèque vous dit que les vecteurs propres devraient être? Idéalement, qu'est-ce qu'un système tel que Mathematica ou Maple (qui peut être persuadé de calculer avec une précision arbitraire) vous dit que les vecteurs propres devraient être? Si ce n'est pas un problème de production-sixed au moins pour un problème de taille de test. Je ne suis pas un expert en traitement d'image, donc je ne peux pas être beaucoup plus utile, mais je passe beaucoup de temps avec les scientifiques et l'expérience m'a appris que beaucoup de larmes et de colère peuvent être évitées en faisant quelques les maths d'abord et formant une attente de quels résultats vous devriez obtenir avant de se demander pourquoi vous avez eu des 0 partout. Bien sûr, il pourrait s'agir d'une erreur dans la mise en œuvre d'un algorithme, il pourrait s'agir d'une perte de précision ou d'un autre problème numérique. Mais vous ne savez pas et ne devriez pas suivre ces pistes d'enquête pour le moment.

Cordialement

Mark