machine-learning - 如何结合光谱聚类的分裂运行以获得巨大的亲和矩阵

问题描述

引导问题

我有一个带有短系列值的 2D 复值图像。我想聚集相似的像素/分割图像。有一个或多或少带有叠加图像的静态图像，其中有一些斑点，这些斑点在短序列上具有变化的值（主要是复数的角度）。它们在图像的规范中也可以略微辨别。

我的第一次尝试是 k-means，但这确实是根据平均值进行聚类的（平均值存在差异，尤其是与周围像素相比，但时间和角度信息更大）。我的第二次尝试是 ICA，然后查看幅度最大的 k 个分量，这确实成功地将我图像中的某些区域识别为不同的，但没有识别出我感兴趣的像素组（视觉上不难认出它们，但它们很小）。

现在的情况

所以因为我的前两次尝试没有成功，我用谷歌搜索了一下，似乎光谱聚类可能是合适的。但是我在使用该方法时遇到了一些严重的问题，主要与有限的可用内存有关。然后我想，因为我有这么多像素，我可以应用光谱聚类来分离数据块。

这里有人建议先将板聚集然后组合它们，然后他说“最后你会遇到重新组合它们的问题，这个问题很容易解决”。在解释中被指定为“容易”的位当然很难做到。他链接到这篇论文，但该方法并未处理平板中的所有数据。它更确切地说排除了不接近主成分的向量。

问题

我的问题有两部分：

1 . 如何组合单独段的结果？特征向量不同，簇数不同。结果看起来像是在单独的板上工作。

2 . 不考虑单独平板中像素之间的距离/亲和性。我可以制作“板之间的板”吗？对于那些板 L 和 A 不对称，不知道如何执行该方法。也许我可以在最后以某种方式比较/合并所有特征向量？

（3.有没有类似或者更好的方法，不需要那么多内存。计算时间也是可以接受的，容易爆）

Matlab代码示例

%% generate data
% get some outer region without data
tempdisk = strel('disk',922/2); tempdisk = double(repmat((1+sqrt(-1)).*tempdisk.Neighborhood,[1 1 15]));
% make some noise
tempnoise = (rand(921,921,15)+sqrt(-1).*rand(921,921,15))./10;
% 'background signal'
tempim1 = double(imresize(mean(imread('cameraman.tif'),3),[921,921])); tempim1 = repmat(tempim1./max(tempim1(:)),[1 1 15]);
% 'target signal'
tempim2 = double(rgb2hsv(imread('fabric.png'))); tempim2 = imresize(tempim2(:,:,2),[921,921]); tempim2 = repmat(tempim2./max(tempim2(:)),[1 1 15]);
sin1 = repmat(permute(sin(2.*pi.*(0:14)./15),[1 3 2]),[921 921 1]);
% combine into data
complexdata = (sin1.*(1.0.*tempim1+0.5.*tempim2.^2).*exp(-sqrt(-1).*2.*pi.*sin1.*(tempim2.^2)).*tempdisk+tempnoise)./1.5;

%this is what the mean data looks like
meannorm = mean(abs(complexdata),3);
meanangle = mean(angle(complexdata),3);
figure; subplot(1,2,1); imshow(meannorm,[]); title('mean norm'); subplot(1,2,2); imshow(meanangle,[]); title('mean angle')

这是生成的数据的样子：

右图中的明亮斑点是我所追求的。它们也随着时间的推移具有最强的变化（并且在时间上是相关的）。

然后设置集群：

%% perform spectral clustering in seperate slabs 
% method from http://ai.stanford.edu/~ang/papers/nips01-spectral.pdf
%get all pixel vectors in a single matrix
complexrows = reshape(permute(complexdata, [3,1,2]), [15, 921*921]);
%k means and eigs dont accept complex, so convert to real here?
complexrowsTranspose = [real(complexrows);imag(complexrows)]'; 

%lets say 10000 by 10000 matrices are still ok
npix = 10000;
nslabpix = floor(length(complexrowsTranspose)/npix);
nrestpix = rem(length(complexrowsTranspose), npix);

在适合内存的平板中执行谱聚类：

% spectral clustering 
keig = 50;%how many eigenvectors needed? more is better
affinity_sigma = 1;% i dont understand how to calculate this from the paper
tic
% start with last slab (dynamically preallocate)
for islabpix = (nslabpix+1):-1:1;
    %print progress
    islabpix/nslabpix
    toc
    if islabpix>nslabpix
        pixrange = (1:nrestpix) + ((islabpix-1)*npix);;
    else
        pixrange = (1:npix) + ((islabpix-1)*npix);
    end
    %calculate affinity between all voxels in slab
    Aff = exp( -squareform(pdist(complexrowsTranspose(pixrange,:))).^2/(2*affinity_sigma^2) ); % affinity matrix
    %calculate degree matrix for normalization
    Dsq = sparse(size(Aff,1),size(Aff,2)); %degree matrix
    for idiag=1:size(Aff,1)
        Dsq(idiag,idiag) = sum(Aff(idiag,:))^(1/2);
    end
    %normalize affinity matrix
    Lap = Dsq * Aff * Dsq; %normalize affinity matrix
    %calculate eigenvectors of affinity matrix
    [eigVectors(pixrange,1:keig), eigValues] = eigs(Lap, keig); %eigenvectors of normalized aff mat
    normEigVectors(pixrange,1:keig) = eigVectors(pixrange,1:keig)./repmat(sqrt(sum(abs(eigVectors(pixrange,1:keig)).^2,2)), [1 keig]); %normalize rows of eigen vectors, normr only works on real numbers
    % perform k means clustering on weights for eigenvectors
    [idx,C,sumd,D] = kmeans([real(normEigVectors(pixrange,1:keig)),imag(normEigVectors(pixrange,1:keig))], 5); %k means on normalized eigenvecotrs

    idxval(pixrange) = idx;
end
%reshape into image
idxim = reshape(idxval, [921, 921]);
figure; imshow(idxim,[])
toc

结果聚类：

结果看起来该方法在每个平板中都在某种程度上起作用。目标是聚集所有具有稍高范数和更强角度变化的斑点（来自的高饱和度斑点tempim2），这在结果中似乎可以识别。现在主要是单独的板是问题并且没有跨板集群。这花了我的电脑大约 15 分钟。我减少了此示例的特征值数量和图像大小，使其在可接受的时间内运行。我认为这说明了我的部分问题。

标签： machine-learningcomputer-visioncluster-analysislinear-algebraimage-segmentation

解决方案

在Shai 的回答之后，我切换到仅计算相邻像素之间的亲和力（在 4 个像素的半径内）并使用稀疏矩阵。然后我得到整个图像的相等聚类。为了制作稀疏邻接矩阵，我使用 Shai 的函数sparse_adj_matrix，否则内存仅由邻接矩阵填充。

tic
complexrowsTranspose = [real(complexrows);imag(complexrows)]';
indexnonzero = find(mean(tempdisk,3) > 0);
idxval = zeros(size(complexrowsTranspose, 1),1);

[irow jcol] = sparse_adj_matrix([size(meannorm,1), size(meannorm,2)], 4, 2);
keep = ismember(irow, indexnonzero);
irow(~keep) = [];
jcol(~keep) = [];
clear keep

sigma = 1;
Avect = exp(-sum((complexrowsTranspose(irow,:)-complexrowsTranspose(jcol,:)).^2,2)/(2*sigma^2));
iAval = find([Avect>0].*[Avect<Inf]);
Aff = sparse(irow(iAval),jcol(iAval),Avect(iAval),length(complexrowsTranspose),length(complexrowsTranspose));
Dvector = sum(Aff,2).^(1/2);
Dindex = find(Dvector);
D = sparse(Dindex, Dindex, Dvector(Dindex),size(Aff,1),size(Aff,2));
L = D * Aff * D;

keig = 25;
[Vect, Val] = eigs(L, keig);
normVect = Vect./repmat(sqrt(sum(abs(Vect).^2,2)), [1 keig]);
[kidx,kC,ksumd,kD] = kmeans(normVect, 5);

kmeansim = reshape(kidx, [921, 921]);
figure; imshow(kmeansim,[])
toc

这是生成的集群的样子：

看起来好多了。然而，我感兴趣的集群没有出现（在“角度”图像中具有高值的斑点，在摄影师的深色外套内）。特别是具有相似平均范数值的像素被聚集在一起，在短序列中没有相似的变化，也没有相似的角度（复数值）。

我将尝试调整输入值和邻接半径来计算亲和力。

更新

我尝试只输入角度、整个复数值（并调整代码以适用于复数值）、更改计算亲和力的半径、输入 1 相关而不是距离，但我没有得到小亮角摄影师外套上的斑点聚集在一起。

然后我下载了这段代码并尝试如下：

complexrowsTranspose = complexrows';
[icol irow] = sparse_adj_matrix([921, 921], 1, Inf);

complexrowsTminmean = complexrowsTranspose -repmat(mean(complexrowsTranspose , 2), [1, 15]);
complexrowsTstd = sqrt( std(real(complexrowsTranspose), [], 2).^2+std(imag(complexrowsT), [], 2).^2 );
complexrowsTcorr = sum(real(complexrowsTminmean(icol).*complexrowsTminmean(irow)), 2)./complexrowsTstd(irow)./complexrowsTstd(icol)./(15-1);

Asparse = sparse(irow, icol, 1-complexrowsTcorr, 921*921, 921*921);
Asparse(isnan(Asparse)) = 0;

K = AL_ICM(Asparse);

但我没有让它超越第一次迭代。我计算这些复杂向量的相关性的方式可能无法满足函数的要求。

machine-learning - 如何结合光谱聚类的分裂运行以获得巨大的亲和矩阵

问题描述

解决方案

推荐阅读