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

Question

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

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

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

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 является матрицей с плавающей запятой)?

веселит

Answer 1

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

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

Andrew Ng, Michael Jordan и Yair Weiss (2002). О спектральной кластеризации: анализ и алгоритм. В Т. Dietterich, С. Беккер и З. Ghahramani (ред.), Достижения в Neural обработки информации системы 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, результаты были:

и, кстати, первые 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 
...... 

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

Answer 2

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

Answer 3

Вот не очень полезно ответ:

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

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

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

С уважением

Все