[Insight-users] Speed of Connected Components Filter

[Miller, James V (Research)]

Ken, 

itkConnectedComponentImageFilter is a pretty standard 3 pass algorithm.
The first pass just initializes the output image.  The second pass
starts labeling components and establishes an equivalency table.
The third pass remaps the labels.

Here is something to try: The algorithm flattens the equivalency table
frequently.  Perhaps for your data, it would be better to flatten
the equivalency table less frequently.  Flattening takes times 
to compute but it reduces the amount of time it takes to lookup 
an equivalency. Given your description of your data, the execution
time may be being dominated by the flattening operation.

Look at lines 193-202 in itkConnectedComponentImageFilter.txx. The lines 
are included below.

          // else if current pixel has a label that is not already
          // equivalent to the label of the previous pixel, then setup
          // a new equivalence.  note the use of Lookup() and not
          // RecursiveLookup(). this is possible since we keep the
          // equivalence table flat.
          else if ((label != neighborLabel)
                && (eqTable->Lookup(label) != eqTable->Lookup(neighborLabel))) 
            {
            eqTable->Add(label, neighborLabel);

            // if we keep the equivalency table up to date, then we
            // can use straight calls to Lookup() instead of
            // RecursiveLookUp().  This works out to be 3X faster.
            eqTable->Flatten();
            }

Try changing the code to 

          else if ((label != neighborLabel)
                && (eqTable->RecursiveLookup(label) != eqTable->RecursiveLookup(neighborLabel))) 
            {
            eqTable->Add(label, neighborLabel);
            }

and see if this speeds things up.  (Note that the Lookup's in the if statement 
were changed to RecursiveLookup's and the equivalency table is not longer flattened).

Let me know if this helps.  If it does we'll need to decide whether to permanently 
change the code, or put in a mode to switch between these two operations, or put
in code to flatten the table after every N new equivalencies are added.

Jim



-----Original Message-----
From: insight-users-bounces+millerjv=crd.ge.com at itk.org
[mailto:insight-users-bounces+millerjv=crd.ge.com at itk.org]On Behalf Of
Ken Urish
Sent: Friday, May 20, 2005 4:40 PM
To: insight-users at itk.org
Subject: [Insight-users] Speed of Connected Components Filter


Im doing some work with the connected components filter. When I work
with a binary tiff image thats 1000x1000 pixels the connected
components filter is a little sluggish. When I do an image thats
5000x5000 the computer grinds to a halt (I need that resolution). Is
there a way to speed the filter up? Whats making it so slow? My other
thought was just to chop the image up into pieces - is there a filter
that would do this in itk?

My images have a few thousand connected components that have a rough
and complex topology so that they are not the easiest thing to run a
connected components on.

Muchos Gracias
--Ken--
_______________________________________________
Insight-users mailing list
Insight-users at itk.org
http://www.itk.org/mailman/listinfo/insight-users