能量驱动采样(种子)提取的超像素

Question

我对通过能量驱动采样(SEEDS)提取的超像素感兴趣，这是一种基于超像素的图像分割方法。这也是OpenCV用来创建超级像素的地方。我很难找到种子算法背后的文档。OpenCV给出了一个非常普遍的描述，可以找到这里。

我正在寻找一个更深入的描述种子是如何运作的(一个一般的遍历或一个数学解释)。任何有关算法的链接或想法都将不胜感激！我似乎找不到任何好材料。谢谢!

Answer 1

首先，我将介绍一些一般的链接和资源，然后尝试描述算法的一般思想。

种子实现：

显然，您已经看到了文档这里。OpenCV的种子实现的一个用法示例可以在这里找到：Cont肋骨/模块/ximgproc/samples/育苗，并允许调整超像素的数量、级别数和其他参数，所以在阅读种子背后的想法之后，您一定应该尝试这个示例。最初的实现以及修改后的实现(我的学士论文的一部分)都可以在GitHub：种子和davidstutz/种子-修订本上找到。不过，实现应该是相当类似的。

出版物和其他资源：

论文发表在arxiv：arxiv.org/abs/1309.3848上。我的网站上有一个更简短的描述(可能更容易理解)：davidstutz.de/efficient-high-quality-superpixels-seeds-revised。所提供的算法描述应该易于跟踪，并且--在最好的情况下--允许实现种子(请参阅本文的“算法”部分)。更精确的描述也可以在我的学士论文中找到，特别是在3.1节中。

一般描述：

请注意，这个描述是基于以上提到的文章和我的学士论文。两者都提供了一个数学上简洁的描述。

给定宽度W和高度H的图像，种子首先将像素分组为大小为w x h的块。这些块被进一步排列成2 x 2的组。对于L级别重复此方案(这是levels参数)。所以在l级别，您有块大小

w*2^(l - 1) x h*2^(l - 1).

超像素的数目由L级的块决定，即让w_L和h_L表示在L级的块的宽度和高度，超级像素的数目是

S = W/w_L * H/h_L

这里我们使用整数除法。

初始超像素分割，现在通过在相邻的超像素之间交换像素块和单个像素来迭代细化。为此，计算超像素和所有块的颜色直方图(直方图由实现中的回收箱参数数确定)。这可以通过看到一个超像素的直方图仅仅是它所包含的2 x 2块的直方图之和来实现，而其中一个块的直方图就是2 x 2底层块的直方图之和(以此类推)。因此，让h_i是属于超像素j的像素块的直方图，h_j是这个超像素的直方图。然后，利用j和h_j的直方图交集计算块j与超像素j的相似性(方程见上述资源之一)。类似地，像素和超像素的相似性要么是像素颜色到超像素平均颜色的欧几里德距离(这是更好的执行选项)，要么是像素颜色所属的像素颜色的概率(这仅仅是像素颜色的超像素直方图的归一化条目)。在此背景下，该算法可归纳如下：

initialize block hierarchy and the initial superpixel segmentation
for l = L - 1 to 1 // go through all levels
    // for level l = L these are the initial superpixels
    for each block in level l
        initialize the color histogram of this block
        // as described this is done using the histograms of the level below
// now we start exchanging blocks between superpixels
for l = L - 1 to 1
    for each block at level l
        if the block lies at the border to a superpixel it does not belong to
            compute the histogram intersection with both superpixels
            assign the block to the superpixel with the highest intersection
// now we exchange individual pixels between superpixels
for all pixels
    if the pixel lies at the border to a superpixel it does not belong to
        compute the Euclidean distance of the pixel to both superpixel's mean color
        assign the pixel to the closest superpixel

在实践中，块更新和像素更新的迭代次数比迭代参数的迭代次数(即迭代参数的次数)要多，并且通常是每级迭代次数的两倍(即双步参数)。在原始分割中，由w、h、L和图像大小来计算超像素数。在OpenCV中，使用上述方程，w和h是根据所需的超像素数和电平数(由相应的参数决定)计算的。

有一个参数仍然不清楚:先前试图强制执行平滑的边界。在实践中，这是通过考虑要更新的像素周围的3 x 3邻域来实现的。如果该邻域中的大多数像素属于超像素j，则要更新的像素也更有可能属于超像素j (反之亦然)。OpenCV的实现以及我的实现(SEEDS修订版)都允许考虑在k x k的情况下使用k in {0,...,5}的更大的邻居OpenCV。