Matlab中的泛洪填充算法

Question

我是MATLAB新手，尝试使用这个算法在MATLAB中实现泛洪填充。我不知道我做错了什么，可能是我没有正确使用递归函数，但我仍然不知道出了什么问题，这段代码使我的MATLAB关闭。 我正在使用以下代码，我尝试了整个早上调试它，但未能找到问题。

function [ colored_Image ] = floodFill( image, target_Loc_x, target_Loc_y, targetColor, replacementColor )
colored_Image = image;

if (target_Loc_x >= 1) && (target_Loc_x <= size(image,1)) && (target_Loc_y >= 1) && (target_Loc_y <= size(image,2))
    if image(target_Loc_x,target_Loc_y) == targetColor
        colored_Image(target_Loc_x,target_Loc_y) = replacementColor;
        colored_Image = floodFill(colored_Image,target_Loc_x ,target_Loc_y + 1, targetColor, replacementColor); 
        colored_Image = floodFill(colored_Image,target_Loc_x + 1,target_Loc_y, targetColor, replacementColor);
        colored_Image = floodFill(colored_Image,target_Loc_x,target_Loc_y - 1, targetColor, replacementColor);
        colored_Image = floodFill(colored_Image,target_Loc_x - 1,target_Loc_y, targetColor, replacementColor);
    end

end


end

调用此函数使用：

image = floodFill(im,1,1,0,127);
imshow(image);

我有一张200x200的矩阵图像im，我希望将其中的黑色（0）变成灰色（127），如果有帮助，感激不尽。

- Muaz Usmani

Answer 1

你可能触发了Matlab的递归限制。我的电脑不会崩溃，但会生成以下错误：

最大递归深度已达到500。使用 set(0,'RecursionLimit',N) 来更改限制。请注意，超过可用堆栈空间可能会导致MATLAB和/或计算机崩溃。

解决方法是重写floodFill，使其不使用递归。维基百科上有一些替代算法。

此外，aardvarkk的回答提到了Matlab的按列主索引的重要性。您可以通过交换所有x和y变量来修复函数。

- shoelzer

Answer 2

我认为以下两点存在问题：

a) 您似乎按照 (x,y) 的顺序索引了 image 矩阵。MATLAB 的矩阵是按列排序的，因此您必须按照不直观的 (y,x) 顺序进行索引。因此，以下行：

image(target_Loc_x,target_Loc_y)

可能应该改为：

image(target_Loc_y,target_Loc_x)

在设置彩色图像中的值时也是如此。还要注意 size(image,1) 给出的是 y 轴方向上的大小，而不是 x 轴！

b) 您使用递归函数执行非常简单的操作。它很快会达到 MATLAB 的递归限制。在一个 200x200 的图像中，您将有一个深度为 40,000 的调用栈，而 MATLAB 默认只允许递归限制为 500。为什么不尝试像这样的东西：

colored_image = image;
colored_image(colored_image == targetColor) = replacementColor;

- aardvarkk

---

代码片段末尾不适用于泛洪填充。它会更改所有目标颜色的像素，而不仅仅是连接的像素。 - shoelzer

@shoelzer 很好的观点。我误解了原始代码片段以填充整个图像，但你是对的 - 只有选择的第一个像素是目标颜色时，它才会真正起作用。 - aardvarkk

Answer 3

    %(假设图像加载到img中，填充值为'value')
函数flood(x,y,img,value)
%因为MATLAB没有友好的队列?使用java    
    import java.util.LinkedList
    q = LinkedList();
%填充图像 
    initial = img(y,x);
q.add([y, x]);
while q.size() > 0
 pt = q.removeLast();
        y = pt(1);
        x = pt(2);
if (img(y+1, x) == initial) 
            img(y+1,x) = value;
            q.add([y+1, x]); 
        end
        if (img(y-1, x) == initial) 
            img(y-1,x) = value;
            q.add([y-1, x]); 
        end
        if (img(y, x+1) == initial) 
            img(y,x+1) = value;
            q.add([y, x+1]); 
        end
        if (img(y, x-1) == initial) 
            img(y,x-1) = value;
            q.add([y, x-1]); 
        end
    end
end

由于matlab递归限制很低，我从来没有尝试使用递归调用进行泛洪填充。此外，因为它似乎没有一个适当的队列（如果我说错了，请纠正我），所以只需从java中导入一个。

这不会进行任何边界检查（因此如果泛洪遇到边缘，则会失败...容易的解决方法是在图像周围放置边框或仅在索引img之前对x和y进行范围检查。

- Jason

Answer 4

@Jason的回答有一些修复 - 我添加了边界检查，一个守卫来确保填充颜色与初始颜色不同（否则会无限递归），并返回结果。工作正常但速度较慢。

function img = flood(x,y,img,value)
    % https://dev59.com/j2zXa4cB1Zd3GeqPZ_9s
    import java.util.LinkedList
    q = LinkedList();

    initial = img(y,x);
    dims = size(img);
    if (value == initial) 
        error('cant flood fill as initial==value');
    end

    q.add([y, x]);

    while q.size() > 0

        pt = q.removeLast();
        y = pt(1);
        x = pt(2);

        if (y < dims(1) && img(y+1, x) == initial) % step down
            img(y+1,x) = value;
            q.add([y+1, x]); 
        end
        if (y > 1 && img(y-1, x) == initial) % step up
            img(y-1,x) = value;
            q.add([y-1, x]); 
        end
        if (x < dims(2) && img(y, x+1) == initial) % step right
            img(y,x+1) = value;
            q.add([y, x+1]); 
        end
        if (x > 1 && img(y, x-1) == initial) % step left
            img(y,x-1) = value;
            q.add([y, x-1]); 
        end
    end
end

- shuckc

---

我已经合并了来自匿名评论者的错误修复。谢谢。 - shuckc