Floodfill algorithm

Question

Hi!
 
I am working on a project regarding image analysis (object counting, area dimensions, etc..)
Using 'canny edge detector' I isolate edges and fill object or background which interests me.
I have tried using 'floodfill algorithm' from here:  https://community.ptc.com/t5/PTC-Mathcad/Objects-Counting/td-p/283337  but with bigger matrix, I have encountered 'not enough memory' issue.
 
So I wrote my own 'scanline floodfill algorythm'.
Algorithm is colouring next pixels until it reaches pixel with value '1', then depending on direction in which it colours, and free space, it leaves
seed with value 255(x+1) or 250(x-1). Then it checks the location of seeds and continues with colouring starting from this seed.

(image is stripy because when writing, it was easier for me to find the loop which leaved UNcolored pixels)
While I was writing my algorythm, it looked promising in terms of performance, but in final form it is very slow.
I have no experience in programming so If anyone would have any idea or advice how to make it faster, it would be perfect.

Werner_E · Accepted Answer

I tried my routine from the thread you referred to in your initial posting and I experienced no problems wrt memory (the pic obviously isn't large enough). While this floodfill was much faster than yours when it came to filling just one of the blobs, it was way slower than yours when it came to filling the space between the blobs. It seems to struggle when there are a lot of holes in the area to fill.

It was not fully clear to me what you algorithm does, but it looked a bit inefficient (nor sure, though). So I rather implemented a different floodfill algorithm according to

Flood fill - Wikipedia

which does not use the (self-implemented) stack that heavily as it uses loops for the left-right movements.

This algorithm is much faster than yours or my previous one (45 seconds vs 0,7 seconds on a slow machine) and I hope that it also works with your larger pictures.

EDIT: I just augmented your pic creating a picture with double width and the times were 191 sec vs 1.5 secs. So it looks that the time your algorithm need does not change linear with the picture area.

EDIT2: OK, couldn't resist. Picture with four times the size of yours -> 785 secs vs 3.5 secs

-MFra- · Answer

Hi Pan KluskaThe program with this simple modification seems already faster:When in a loop there is a conditional operator, the calculation slows. Just imagine the time required by your program with all conditional operators that are present in  several for loops.Doing that modification also  to "fill_up" program, the required time is 24.16 "Best regardsF. M.

Sign up

Please use your PTC eSupport account.

Welcome to the PTC Community

Please use your PTC eSupport account.

Scanning file for viruses.

This file cannot be downloaded