Matlab中的图割算法

Question

我正在尝试将图形割方法应用于我的分割任务中。我在Graph_Cut_Demo找到了一些示例代码。

以下是部分代码：

img = im2double( imread([ImageDir 'cat.jpg']) ); 
[ny,nx,nc] = size(img); 
d = reshape( img, ny*nx, nc );  
k = 2; % number of clusters 
[l0 c] = kmeans( d, k ); 
l0 = reshape( l0, ny, nx ); 

% For each class, the data term Dc measures the distance of 
% each pixel value to the class prototype. For simplicity, standard 
% Euclidean distance is used. Mahalanobis distance (weighted by class 
% covariances) might improve the results in some cases.  Note that the 
% image intensity values are in the [0,1] interval, which provides 
% normalization.   

Dc = zeros( ny, nx, k ); 
for i = 1:k 
  dif = d - repmat( c(i,:), ny*nx,1 ); 
  Dc(:,:,i) = reshape( sum(dif.^2,2), ny, nx ); 
end 

看起来这种方法使用k-means聚类来初始化图表并获取数据项Dc。然而，我不明白他们如何计算这个数据项。为什么要使用它？

dif = d - repmat( c(i,:), ny*nx,1 ); 

在评论中提到数据项Dc测量了每个像素值与类原型之间的距离。什么是类原型，为什么可以通过k-means标签确定？

在另一个实现Graph_Cut_Demo2中使用了

% calculate the data cost per cluster center
Dc = zeros([sz(1:2) k],'single');
for ci=1:k
    % use covariance matrix per cluster
    icv = inv(cov(d(l0==ci,:)));    
    dif = d- repmat(c(ci,:), [size(d,1) 1]);
    % data cost is minus log likelihood of the pixel to belong to each
    % cluster according to its RGB value
    Dc(:,:,ci) = reshape(sum((dif*icv).*dif./2,2),sz(1:2));
end

这让我很困惑。他们为什么要计算协方差矩阵，以及如何使用负对数似然形成数据项？是否有任何关于这些实现的论文或描述可用？

非常感谢。

- Samo Jerom

Answer 1

两个图像分割示例都有很强的相关性。图像处理、分析和机器视觉：MATLAB伴侣一书（第一个示例）使用了Shai Bagon的图形切割包装器代码（在作者的许可下自然）——第二个示例。

那么，数据项到底是什么？
数据项表示每个像素独立地可能属于每个标签的程度。这就是为什么使用对数似然项的原因。

更具体地说，在这些例子中，您尝试根据它们的颜色将图像分成k个部分。您假设图像中只有k种主要颜色（这不是非常实用的假设，但对于教育目的足够）。使用k均值算法，您尝试找到这两种颜色。 k均值算法的输出是RGB空间中的k个中心-即k个“代表性”颜色。每个像素属于任何一个k中心的可能性与该像素与代表性k中心之间的距离（在颜色空间中）成反比：距离越大，像素属于k中心的可能性就越小，必须“付出”更高的一元能量惩罚才能将该像素分配给k群集。
第二个例子进一步假定k个群集在颜色空间中可能具有不同的密度，并使用每个群集的协方差矩阵来建模这种二阶行为。

实际上，对于每个段落，人们通常会使用更复杂的颜色模型，通常是高斯混合模型。您可以在GrabCut（第3节）的开创性论文中了解更多信息。

附言：
下次您可以直接给Shai Bagon发送电子邮件并提出问题。

- Shai