Eigenvector computação usando OpenCV

Question

Eu tenho essa matriz A, representando semelhanças de intensidade dos pixels de uma imagem. Por exemplo: Considere uma imagem de 10 x 10. Uma matriz, neste caso, seria de dimensão 100 x 100, e o elemento A (i, j) teria um valor na gama de 0-1, representando a semelhança de pixel de i a j em termos de intensidade.

Eu estou usando OpenCV para processamento de imagem e o ambiente de desenvolvimento é C em Linux.

O objetivo é calcular os vectores próprios da matriz A e eu usei a seguinte abordagem:

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

Problema: Após a execução eu recebo quase todos os componentes de todos os Autovetores ser zero. Tentei imagens diferentes e também tentou preencher um com valores aleatórios entre 0 e 1, mas o mesmo resultado.

a seguinte aparência alguns dos principais valores próprios devolvidos:

9805401476911479666115491135488.000000  
-9805401476911479666115491135488.000000  
-89222871725331592641813413888.000000  
89222862280598626902522986496.000000  
5255391142666987110400.000000

Agora estou pensando sobre as linhas de usar cvSVD () que realiza decomposição em valores singulares da matriz de ponto flutuante real e pode me deu os autovetores. Mas antes que eu pensei em pedir-lo aqui. Há algo absurdo na minha abordagem atual? Estou usando a API direito ie cvEigenVV () para a matriz de entrada direita (minha matriz a é uma matriz de ponto flutuante)? ??

aplausos

Answer 1

Nota aos leitores:. Este post à primeira vista pode parecer sem relação com o tema, mas por favor consulte a discussão nos comentários acima

A seguir é a minha tentativa de implementar o Spectral Clustering algoritmo aplicado a imagem pixels em MATLAB . Eu segui exatamente o papel mencionado por @Andriyev:

Andrew Ng, Michael Jordan, e Yair Weiss (2002). No agrupamento espectral: análise e um algoritmo. Em T. Dietterich, S. Becker, e Z. Ghahramani (Eds.), Avanços na Informação Neural dos Sistemas de Tratamento 14. MIT Press

O código:

%# 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)'})

... e utilizando uma imagem casa simples que eu desenhei no Paint, os resultados foram:

E, a propósito, os 4 primeiros valores próprios utilizados foram:

1.0000
0.0014
0.0004
0.0002

e os vectores eigen que correspondem [colunas de comprimento 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 que existem etapa realizada acima do qual você não mencionou na sua pergunta (matriz Laplacian, e normalizar suas linhas)

Answer 2

Gostaria de recomendar este artigo . Os implementos autor Eigenfaces para reconhecimento facial. Na página 4 você pode ver que ele usa cvCalcEigenObjects para gerar os vectores próprios de uma imagem. No artigo são apresentados a etapa de processamento pré inteiro necessário para esta computações.

Answer 3

Aqui está uma resposta não muito útil:

O que a teoria (ou matemática rabiscou em um pedaço de papel) dizer-lhe os vectores próprios deveria ser? Aproximadamente.

O que outra biblioteca de dizer-lhe os vectores próprios deveria ser? Idealmente o que um sistema como o Mathematica ou de bordo (que pode ser persuadido a computação de precisão arbitrária) dizer-lhe os vectores próprios deveria ser? Se não fosse por um problema sixed-produção pelo menos por um problema de teste de tamanho.

Eu não sou um especialista com processamento de imagem por isso não pode ser muito mais útil, mas eu gastar muito tempo com cientistas e experiência me ensinou que um monte de lágrimas e raiva pode ser evitada fazendo alguma matemática primeira e formando uma expectativa de que resultados você deve obter antes de se perguntando por que você tem 0s em todo o lugar. Claro que pode haver um erro na implementação de um algoritmo, pode ser perda de precisão ou algum outro problema numérico. Mas você não sabe e não deve acompanhar essas linhas de investigação ainda.

Saudações

Mark