Примечание для читателей: этот пост сначала может показаться не связанным с темой, но, пожалуйста, обратитесь к обсуждению в комментариях выше.
Ниже представлена моя попытка реализовать Алгоритм спектральной кластеризации , примененный к пикселям изображения в MATLAB . Я в точности следовал статье , упомянутой @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, результаты были:
и, кстати, использовались первые 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
......
Обратите внимание, что есть шаг, выполненный выше, который вы не упомянули в своем вопросе (матрица лапласа и нормализация ее строк)
Я бы порекомендовал эту статью . Автор реализует Eigenfaces для распознавания лиц. На странице 4 вы можете видеть, что он использует cvCalcEigenObjects для генерации собственных векторов из изображения. В статье показан весь этап предварительной обработки, необходимый для этих вычислений.
Вот не очень полезный ответ:
Что теория (или математика, нацарапанная на листе бумаги) говорит вам, что должны быть собственные векторы? Приблизительно.
Что говорит вам другая библиотека о собственных векторах? В идеале, что система, такая как Mathematica или Maple (которую можно убедить вычислить с произвольной точностью), сообщит вам о собственных векторах? Если бы не проблема производственного уровня, по крайней мере, проблема тестового размера.
Я не эксперт в области обработки изображений, поэтому я ничем не могу помочь, но я провожу много времени с учеными и опытом научил меня, что многих слез и гнева можно избежать, если сначала посчитать и сформировать ожидание того, какие результаты вы должны получить, прежде чем задаться вопросом, почему у вас повсюду нули. Конечно, это может быть ошибка в реализации алгоритма, потеря точности или другая числовая проблема. Но вы не знаете, и вам пока не следует продолжать эти расследования.
С уважением
Марк