[scilab-Users] Finding continuous parts in a mask (ie a binary matrix)

[jasper van baten]

Hi Antoine,

Flood fills are actually pretty efficient. The 
checking whether the points was checked already 
is a simple matrix element check. So the 
efficiency depends on the two lists (elements to 
check, should be a stack-type of list, and grain 
list). I suppose if you pre-allocate them to 
their maximum size (maximum size would be the sum 
of your original grid, e.g. the sum of all ones), 
this should be pretty efficient too.

You can do your grain calculations (e.g. size, 
average location, ...) upon finding a complete 
grain, you need not sure the grain list itself. 
If you can do these calculations on the fly you 
need not even store the grain list while you are finding them.

If you keep your 'checked elements' matrix the 
same as (a copy of) the original matrix (e.g. 
only keep ones for the points that are unchecked 
and part of a grain) you save yourself a matrix 
and finding the next start point could be a simple 'find'.

If your grains a few and far apart, you should consider using sparse matrices.

Good luck.

Jasper.

At 11:34 3/8/2011, Antoine Monmayrant wrote:
>Hi Jasper,
>
>Thanks for your proposition.
>I came to a similar conclusion (see my reply to Mike).
>I was wondering whether there was something more efficient to implement.
>I am sure this kind of problem as already been 
>solved in many areas but I don't have the right keywords to search for.
>If I don't find anything better, I'll implement 
>something along the lines of what you've proposed.
>I am just afraid that this approach will be too 
>slow given the size of my matrices.
>
>Thank you for your help,
>
>Antoine
>
>Le 08/03/2011 11:27, jasper van baten a écrit :
>>Hello Antoine,
>>
>>Use a flood fill. Make a matrix with the same 
>>size as your original to keep track of which elements you already checked.
>>
>>Loop until there are no more elements you did not check with a value of 1:
>>
>>  - make a list of elements to check, add the 
>> first unchecked element with value of 1
>>  - make a list of elements in the grain, initially empty.
>>  - while there are elements in the to-check list:
>>     - add this element to the grain list
>>     - mark this element as checked in the matrix
>>     - add all of its unchecked neighbours to the to-check list
>>  - the grain list now contains all elements in 
>> a grain. All elements in this grain are marked 
>> checked. Scan for the next grain.
>>
>>Hope that helps.
>>
>>Jasper.
>>
>>
>>At 11:21 3/8/2011, Mike Page wrote:
>>>Hi Antoine,
>>>
>>>You could use a Sobel transform to detect the edges where the value changes
>>>from 0 to 1 or 1 to 0.
>>>
>>>But maybe you were looking for something simpler?
>>>
>>>Mike.
>>>
>>>
>>>-----Original Message-----
>>>From: Antoine Monmayrant [mailto:antoine.monmayrant at laas.fr]
>>>Sent: 08 March 2011 09:58
>>>To: users at lists.scilab.org
>>>Subject: [scilab-Users] Finding continuous parts in a mask (ie a binary
>>>matrix)
>>>
>>>
>>>Hi everyone,
>>>
>>>I have question that is more about image filtering than scilab, but I
>>>haven't found any answer so far so I'm turning towards scilab users.
>>>I am looking for a way to determine continuous parts in a matrix made of
>>>1 or 0.
>>>Basically, this matrix is used as a mask to filter an image and I need
>>>to determine the number of isolated "grains" (ie continuous parts where
>>>the matrix is equal to 1) in this mask.
>>>As an example, here is a mask:
>>>
>>>-->mask
>>>   mask  =
>>>
>>>      0.    0.    0.    0.    0.    0.    0.    0.    0.    0.
>>>      0.    0.    0.    0.    0.    0.    1.    1.    1.    0.
>>>      0.    0.    0.    0.    0.    0.    1.    1.    1.    0.
>>>      0.    0.    0.    0.    0.    0.    1.    1.    1.    0.
>>>      0.    1.    1.    0.    0.    0.    0.    0.    0.    0.
>>>      0.    1.    1.    1.    0.    0.    0.    0.    0.    0.
>>>      0.    0.    1.    1.    0.    0.    0.    0.    0.    0.
>>>      0.    0.    0.    0.    0.    0.    0.    0.    0.    0.
>>>      0.    0.    0.    0.    0.    0.    0.    0.    0.    0.
>>>      0.    0.    0.    0.    0.    0.    0.    0.    0.    0.
>>>
>>>
>>>It contains 2 "grains", one in the upper-right corner, and one in the
>>>middle-left.
>>>I would like to be able to isolate them in order to determine their
>>>position in the matrix, size,...
>>>Do any of you know of a good algorithm to achieve this?
>>>Do any of you know what are the relevant names or keywords associated to
>>>this kind of algorithm?
>>>
>>>Thank you in advance,
>>>
>>>Antoin
>>>
>>>No virus found in this incoming message.
>>>Checked by AVG - www.avg.com
>>>Version: 9.0.872 / Virus Database: 271.1.1/3488 - Release Date: 03/07/11
>>>20:43:00
>
>
>--
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++
>
>  Antoine Monmayrant LAAS - CNRS
>  7 avenue du Colonel Roche
>  31077 TOULOUSE
>  Cedex 4 FRANCE
>
>  Tel:+33 5 61 33 64 59
>
>  email : antoine.monmayrant at laas.fr
>  permanent email : antoine.monmayrant at polytechnique.org
>
>+++++++++++++++++++++++++++++++++++++++++++++++++++++++