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.
1 ACCEPTED SOLUTION
Accepted Solutions
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
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
Hi Pan Kluska
The 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 regards
F. M.
Your goal was to speed up your fill routine, but when I try to run you file I get an error as of an invalid array index:
Trace points me to this position in your fill routine:
I am too lazy to debug the large program but I suspect that x wil be 0 and as ORIGIN is set to 0, there is no index -1.
What FM showed sure is better programming habit not to let the program do the same calculation (determine the size of the matrix m) over and over again. It may speed up the framing routine "ramka" but "ramka" has nothing to do with the fill routine, which seems to be the slow part. So to speed up your fill routine a little bit, you would have to apply similar modifications to that routine, too.
BTW, something like
really is bad programming and should be avoided. You have a lot similar constructs in your fill routine, too.
May I suggest something ORIGIN-independent like
To have no error, you have to click the right image, the one with all-black background. You can click on a closed domain, in which case the time required is much less than that required by clicking at any point of the image.
Excuse me, my recommendations are for those interested in the subject, certainly not for you that know the topic for a long time.
Greetings
F. M.
Thank you for replying,
I wrote my program from the beginning, using your advices and it is better.
I still use ramka(m), because it helps me avoid errors with pixels adjacent with mx,cols(m)-1/mx,0 and m0,y/mrows(m)-1,y.
Besides that, I have experimented a bit and I think that the part that is slowing down my program is:
Is there any other way to check "seed" coordinates?
Best Regards
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
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
Hi!
Thank you for your reply. Your algorithm works great. I have even tried it on matrix 2048x1242.
Your wrote it very clearly and thanks to the describtion, it’s easy to understand.
Thank you,
Kind Regards,
Pan Kluska
