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

У меня есть эта матрица A, представляющая сходство интенсивностей пикселей изображения. Например: Рассмотрим изображение 10 x 10. Матрица A в этом случае будет иметь размерность 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    
  }
}

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

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

9805401476911479666115491135488.000000  
-9805401476911479666115491135488.000000  
-89222871725331592641813413888.000000  
89222862280598626902522986496.000000  
5255391142666987110400.000000

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

ваше здоровье


person Arnkrishn    schedule 06.12.2009    source источник
comment
На самом деле не использовали eig/svd в openCV, но разве не правда, что возвращаемые собственные значения должны быть отсортированы?   -  person Amro    schedule 07.12.2009
comment
Да, это правильно. Я только что выложил 5 лучших собственных значений, и с точки зрения величины они расположены по порядку (от большего к меньшему). По знаку их нет. Но знак просто указывает ориентацию вектора, поэтому я предполагаю, что собственные значения в порядке. Просто обеспокоен собственными векторами.   -  person Arnkrishn    schedule 07.12.2009
comment
а про знак забыл! ну, согласно документации, достаточно значения эпсилон 1e-15 (вы используете eps=1e-300). Может ли это вызвать проблему? Также не правда ли, что мы обычно можем ожидать, что только первые несколько самых больших собственных векторов объясняют большую часть дисперсии данных?   -  person Amro    schedule 07.12.2009
comment
да, я начал с 1e-15, а затем перешел к текущему значению. Но не мог получить много изменений. Да, на самом деле моя конечная цель — сделать спектральную кластеризацию входного изображения. Для этого я передаю первые N собственных векторов алгоритму кластеризации k-средних. Но поскольку почти все становятся равными 0, почти все объединяются в один и тот же кластер.   -  person Arnkrishn    schedule 07.12.2009
comment
вы можете проверить результаты, выполнив те же вычисления в числовом пакете, таком как MATLAB или Octave. Могу я спросить, как именно вы вычисляете матрицу сходства между каждой парой пикселей? Я был бы рад попробовать это на примере изображения в MATLAB.   -  person Amro    schedule 07.12.2009
comment
ну, я бы с удовольствием это сделал, но, видимо, я не знаю MATLAB. Я использую Gaussian Kernel для вычисления сходства и ссылаюсь на алгоритм спектральной кластеризации Эндрю Нг. Его можно найти здесь eprints.kfupm.edu.sa/54643/1/54643. pdf . На странице 2 есть алгоритм. На шаге 1 алгоритма упоминается ядро ​​Гаусса, используемое для вычисления сходства между двумя пикселями. Я использовал интенсивность пикселей для Si, Sj и стандартное отклонение для знаменателя, то есть сигма ^ 2. Я исключил интенсивности пикселей i и j при вычислении сигмы.   -  person Arnkrishn    schedule 07.12.2009
comment
Я ничего не знаю об openCV, но похоже, что вы передаете два неинициализированных указателя (eigenVec и eigenVal) в cvEigenVV(). Но, возможно, вы пропустили код инициализации для краткости.   -  person quinmars    schedule 07.12.2009
comment
@Andriyev Сейчас я работаю над аналогичным проектом, и мне нужно найти собственные значения и собственные векторы матрицы. Я смотрел на функцию cvEigenVV, которую вы использовали в коде. К сожалению, мне необходимо использовать openCV и C++ в моем проекте, и у меня нет возможности переключиться на Matlab. Не могли бы вы просто объяснить мне, почему вы вставили этот фрагмент своего кода? ][j]; } } Какова была цель сделать это в первую очередь? Пожалуйста, свяжитесь со мной как можно скорее, если это возможно.   -  person sue-ling    schedule 15.03.2012


Ответы (3)


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

Ниже я пытаюсь реализовать алгоритм спектральной кластеризации, примененный к пикселей изображения в 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
......

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

person Amro    schedule 07.12.2009
comment
Это выглядит потрясающе. Да, я просто пропустил этапы лапласиана и нормализации в своем вопросе, чтобы не упустить суть. Что ж, теперь, возможно, у меня есть веская причина изучить MATLAB. Спасибо за руководство и усилия с вашей стороны. - person Arnkrishn; 07.12.2009
comment
Правда в том, что я сам читал на тему ядра PCA, который очень похож, и я нашел возможность лучше понять его, написав код... и это одна из вещей, которые мне нравятся в MATLAB; такой алгоритм можно реализовать довольно быстро и всего в несколько строк! (по сравнению с кодированием на C) - person Amro; 07.12.2009

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

person Janusz    schedule 07.12.2009
comment
Уважаемый Януш, я сейчас работаю над подобным проектом и, прочитав ваш ответ, я искал документацию для cvCalcEigenObjects. Однако при поиске как в справочном руководстве по openCV, так и в O'Reilly - Learning openCV этой функции там не было. Вы возможно знаете, если это устарело? - person sue-ling; 15.03.2012

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

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

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

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

С Уважением

Отметка

person High Performance Mark    schedule 07.12.2009