Вычисление собственных векторов с использованием OpenCV

У меня есть эта матрица A, представляющая сходство интенсивностей пикселей изображения. Например: Рассмотрим образ 10 x 10. Матрица А в этом случае будет иметь размерность 100 x 100, а элемент A (i, j) будет иметь значение в диапазоне от 0 до 1, представляя подобие пикселя i-j по интенсивности.

Я использую OpenCV для обработки изображений, а среда разработки - C на Linux.

Цель состоит в том, чтобы вычислить собственные векторы матрицы A, и я использовал следующий подход:

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

Проблема: После выполнения я получаю почти все компоненты всех собственных векторов равными нулю. Я пробовал разные изображения, а также пытался заселить А со случайными значениями от 0 до 1, но тот же результат.

Немногие верные исходные значения выглядят следующим образом:

9805401476911479666115491135488.000000  
-9805401476911479666115491135488.000000  
-89222871725331592641813413888.000000  
89222862280598626902522986496.000000  
5255391142666987110400.000000

Теперь я размышляю о том, как использовать cvSVD(), который выполняет декомпозицию по разным значениям реальной матрицы с плавающей запятой и может дать мне собственные векторы. Но до этого я подумал спросить об этом здесь. Есть ли что-то абсурдное в моем нынешнем подходе? Я использую правый API, т.е. cvEigenVV() для правильной матрицы ввода (моя матрица A является матрицей с плавающей запятой)?

веселит

Ответы

Ответ 1

Примечание для читателей: это сообщение сначала может показаться не связанным с темой, но, пожалуйста, обратитесь к обсуждению в комментариях выше.

Ниже приведена моя попытка реализовать алгоритм Spectral Clustering, применяемый к пикселям изображения в MATLAB. Я следовал точно paper, упомянутым @Andriyev:

Эндрю Нг, Майкл Джордан и Яир Вайс (2002). О спектральной кластеризации: анализ и алгоритм. У Т. Дитериха, С. Беккера и З. Гахрамани (Ред.), Достижения в системах обработки нейронной информации 14. MIT Press

Код:

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

... и используя простой образ дома, я рисовал Paint, результаты были:

laplacian matriximage clustered

и, кстати, первые 4 собственных значения:

1.0000
0.0014
0.0004
0.0002

и соответствующие собственные векторы [столбцы длины 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
......

Обратите внимание, что вы выполнили шаг выше, о котором вы не упомянули в своем вопросе (матрица Лапласа и нормализация его строк)

Ответ 2

Я бы рекомендовал эту статью статью. Автор реализует собственные функции распознавания лиц. На странице 4 вы можете видеть, что он использует cvCalcEigenObjects для генерации собственных векторов из изображения. В статье показан весь этап предварительной обработки, необходимый для этих вычислений.

Ответ 3

Здесь не очень полезный ответ:

Что теория (или математика, написанная на листе бумаги) говорит вам, что собственные векторы должны быть? Примерно.

Что еще скажет вам библиотека, что должны быть собственные векторы? В идеале, какая система, такая как Mathematica или Maple (которую можно убедить вычислить произвольной точности), говорит вам, что собственные векторы должны быть? Если это не проблема, связанная с производством, по крайней мере, проблема с размером теста.

Я не специалист по обработке изображений, поэтому я не могу быть более полезным, но я много времени провожу с учеными, и опыт научил меня, что многие слезы и гнев можно избежать, выполняя математику прежде всего, и рассчитывать на то, какие результаты вы должны получить, прежде чем задаваться вопросом, почему вы получили 0s повсюду. Конечно, это может быть ошибка при реализации алгоритма, это может быть потеря точности или какая-либо другая численная проблема. Но вы не знаете и не должны отслеживать эти линии дознания.

Привет

Марк