java - 为什么这种洪水填充算法不起作用？

Question

对于这个问题:Is there a proper algorithm for detecting the background color of a figure? ，我需要创建一个 flood-fill algorithm能够将所有像素分成相同颜色的组。

我递归地执行了此操作，但它给了我一个堆栈溢出错误。所以我必须选择这里找到的迭代的、基于队列的算法:http://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations

首先，我开始搜索所有矩阵元素(元素是 Pixel 类的实例)。

private PixelGroup[] generatePixelGroupsFromMatrix(Pixel[][] matrix) {
    PixelGroup[] tempGroups = new PixelGroups[9999999]; // Nevermind the 9999999....
    int groupsFound = 0;
    Pixel pixel;

    for (int y = 0; y < matrix.length; ++y) {
        for (int x = 0; x < matrix[0].length; ++x) {
            pixel = matrix[y][x];
            if (!pixel.evaluated) {
                // This pixel has never been evaluated
                // Therefore, it belongs to a new group
                // First, we make a new group
                PixelGroup newGroup = new PixelGroup();
                // Begin search for connected pixels with the same color. All pixels found will belong to this new group.
                findPixelsConnectedWith(pixel,newGroup);
                tempGroups[groupsFound] = newGroup;
                ++groupsFound;
            }
        }
    }

    PixelGroup[] result = new PixelGroup[groupsFound];
    for (int i = 0; i < groupsFound; ++i) {
        result[i] = tempGroups[i];
    }

    return result;
}

因此，Pixel 具有以下值:x、y、评估值( boolean 值)和颜色(整数)。 然后，PixelGroup 只是一个能够保存像素的类(它可以工作)。

这就是给我带来麻烦的方法:

private void findPixelsConnectedWith(Pixel pixel, GroupOfPixels group) {
    QueueOfPixels queue = new QueueOfPixels();
    queue.add(pixel);

    Pixel currentPixel;
    int x,y;
    Pixel neighbor;
    while((currentPixel = queue.nextPixel()) != null) {
        if (currentPixel.color == pixel.color && !currentPixel.evaluated) {
            // This pixel has the required color, and has not been evaluated. It meets our needs.
            // Add to group.
            group.addPixel(currentPixel);
            // Flag it as evaluated. So in the future, it will be ignored.
            currentPixel.evaluated = true;
            // Evaluate all 8 possible directions to find neighbor pixels
            int[] xDirections = {0,1,1,1,0,-1,-1,-1};
            int[] yDirections = {-1,-1,0,1,1,1,0,-1};
            for (int i = 0; i < 8; ++i) {
                x = xDirections[i];
                y = yDirections[i];
                if (pixelExists(currentPixel.y + y,currentPixel.x + x)) {
                    // There exists a pixel in this direction!
                    neighbor = getPixel(currentPixel.y + y,currentPixel.x + x);
                    queue.add(neighbor);
                }
            }
        }
    }

}

如果您好奇，这是我的QueueOfPixels 类。我必须只用 vector 制作自己的 vector (学校作业要求):https://codereview.stackexchange.com/questions/17823/vector-based-flood-fill-algorithm-queue-class (据我所知，它确实有效)。

问题是什么？

好吧，我已经用这张 5x2 像素的图像进行了测试(您需要放大很多才能看到它):/image/xV0Lf.gif - 第一行只有黑色像素，第二行是白色。该程序告诉我它已找到 6 个像素组(实际上应该只有 2 个!)

我尝试过什么来调试问题？

首先，在调用 findPixelsConnectedWith 之前，我放置了这一行:

System.out.println("The pixel (" + x + "," + y + ") has not been evaluated. Evaluating now.");

这就是结果:

The pixel (0,0) has not been evaluated. Evaluating now.
The pixel (1,0) has not been evaluated. Evaluating now.
The pixel (2,0) has not been evaluated. Evaluating now.
The pixel (3,0) has not been evaluated. Evaluating now.
The pixel (4,0) has not been evaluated. Evaluating now.
The pixel (0,1) has not been evaluated. Evaluating now.

因此，正如您所看到的，代码似乎无法处理第一行(黑色像素)，因为它认为该行中的每个像素都没有被评估(我希望它会说(0， 0) 未评估并完成)。但是当它开始处理第二行时，它似乎确实按预期工作(找到(0,1)然后就结束了)。

但我仍然无法弄清楚发生了什么。有什么想法吗？

编辑: 我的 getPixel 和 pixelExists 函数:

private boolean pixelExists(int y, int x) {
    return (y > 0 && y < pixelMatrix.length) && (x > 0 && x < pixelMatrix[0].length);
}

private Pixel getPixel(int y, int x) {
    return pixelMatrix[y][x];
}

Answer 1

您的 PixelExists 方法应使用 y >= 0 和 x >= 0，而不是 y > 0 和 x > 0。

private boolean pixelExists(int y, int x) {
    return (y >= 0 && y < pixelMatrix.length) && (x >= 0 && x < pixelMatrix[0].length);
}

这可能不是唯一的问题，但它肯定会阻止您获得正确的答案。