谱聚类、图像分割与特征向量

Question

根据《计算机视觉：一种现代方法》这本书第425页的内容，我尝试使用特征向量来进行图像分割。

http://dl.dropbox.com/u/1570604/tmp/comp-vis-modern-segment.pdf

作者提到，图像的像素相似性可以用一个矩阵A来表示。接着，我们可以通过最大化w^T A w这个公式来进行处理，其中w是权重。经过一些数学运算，我们得到Aw = λw，这里的w就像是特征向量。然后，找到最佳的聚类就是找到具有最大特征值的特征向量，特征向量中的值代表了聚类的归属。于是我写了这段代码。

import matplotlib.pyplot as plt
import numpy as np

Img = plt.imread("twoObj.jpg")
(n,dummy) = Img.shape
Img2 = Img.flatten()
(nn,) = Img2.shape

A = np.zeros((nn,nn))

for i in range(nn):
    for j in range(nn):
        N=Img2[i]-Img2[j];
        A[i,j]=np.exp(-(N**2))

V,D = np.linalg.eig(A)
V = np.real(V)
a = np.real(D[1])

threshold = 1e-10 # filter
a = np.reshape(a, (n,n))
Img[a<threshold] = 255
plt.imshow(Img)
plt.show()

这是处理后的图像：

我能得到的最佳结果如下。我觉得结果还可以更好。

在Numpy中，特征值是从大到小排序的。我尝试了第一个特征值，但没有效果，然后我尝试了第二个特征值，得到了下面的结果。阈值是通过反复试验选出来的。有没有什么建议可以改进这个算法呢？

Answer 1

我刚在Mathematica上试了这个算法，结果在你的图片上运行得很好，所以你的代码里可能有个小bug。

这一部分：

V,D = np.linalg.eig(A)
V = np.real(V)
res = n_max(V,1) # take largest 
idx = res[0][1][0] 
a = np.real(D[idx]) # look at corresp eigv

看起来有点奇怪：我知道的所有线性代数包都返回排序好的特征值和特征向量，所以你只需要取列表中的第一个特征向量。这个特征向量对应的是最大的特征值。你可以试着画出特征值的列表来确认一下。

另外，你的固定阈值是从哪里来的？你有没有试过把图片归一化来显示一下？

顺便说一下，我得到的前三个特征向量的结果是：

这是我使用的Mathematica代码：

pixels = Flatten[image];
weights = Table[N[Exp[-(pixels[[i]] - pixels[[j]])^2]], {i, 1, 900}, {j, 1, 900}];
eigenVectors = Eigenvectors[weights];
ImageAdjust[Image[Partition[eigenVectors[[1]], 30]]]