Geek Answers Handbook

Flood Fill Using Matlab

I am new to MATLAB, I am trying to implement flood filling using this algorithm in Matlab, I don’t know what I did wrong, maybe I didn’t use the recursive function correctly, but still I’m not mistaken, and this code forces my matlab to close I am using the following code, which I am trying to debug in the morning, but could not find the problem.

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

calling this function with

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

im is my 200 x 200 matrix image. I want my black color (0) to be gray (127), any help would be appreciated

+4
source share
4 answers

You are probably breaking the Matlab recursion limit. My computer does not crash, but generates this error:

The maximum recursion limit of 500 has been reached. Use set (0, 'RecursionLimit', N) to change the limit. Keep in mind that exceeding your available stack space may cause MATLAB and / or your computer to crash.

How to do this is to rewrite floodFill so that it doesn't use recursion. There are alternative algorithms on Wikipedia .

Also: aardvarkk's answer makes an important point regarding Matlab column-major indexing. You can fix your function by replacing all x and y variables.

+5
source

I believe that there are two things in this:

a) It seems you are indexing the image matrix in order (x,y) . MATLAB matrices are in column order, so you need to (unintuitily) index them in order (y,x) . So the line:

image(target_Loc_x,target_Loc_y)

should be:

image(target_Loc_y,target_Loc_x)

The same thing happens when you set a value in a color image. Note also that size(image,1) will give the size in the y direction, not x !

b) You use a recursive function to perform a very simple operation. It very quickly reaches MATLAB's recursion limit. In a 200x200 image, you will have a call stack 40,000 deep, and MATLAB allows a default recursion limit of 500. Why not try something like this:

 colored_image = image; colored_image(colored_image == targetColor) = replacementColor;
+3
source 
  % (assume your image is loaded into img and you are filling with 'value')

 function flood (x, y, img, value)

     % MATLAB doesnt have a friendly queue?  use java   
     import java.util.LinkedList
     q = LinkedList ();

     % flood fill image 
     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

Since Matlab has a very low recursion limit, I never managed to flood using recursive calls. Also, since it doesn't seem to have the correct queue (please correct me if I'm wrong) it is easier to just import from java.

It does not do any border checks (so it won’t succeed if the stream hits the edge ... An easy fix is ​​to put a border around your image or just check the x and y range before img indexing.

+2
source

A few corrections for @Jason's answer - I added border checking, guarding that the fill color is different from the initial color (otherwise, infinite recursion) and returns the result. It works slowly but more slowly.

 function img = flood(x,y,img,value) % http://stackoverflow.com/questions/14238083/flood-fill-using-matlab 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
+1
source

More articles:


All Articles