[Insight-users] RE: Speed of Connected Components Filter

[Sayan Pathak]

Hi Jim,
Thanks for looking into the connected component analysis filter speed
issue. Looks like the replacement code significantly reduces execution
time of the connected component analysis filter for large data sets with
lots of components. 

At the Allen Institute, our team is looking into segmenting regions of
gene expression in high resolution tissue cross-section images of the
mouse brain (www.brain-map.org). I used 3 different image sets for this
test. Each image set comprises of a stack of about twenty 2D
cross-sectional images, each of size approximately (14k x 8k pixels). I
have an algorithm that segments regions of expression in these images.
In my 3 test sets, number of distinct connected components were about
800k, 1250k and 2500k. Using the recursive lookup, the computation time
reduced by 37%, 42% and 54% for the three test sets respectively. The
larger the number of objects in an image, the greater is the impact of
the recursive lookup.

Sayan

============


Date: Fri, 20 May 2005 17:07:45 -0400
From: "Miller, James V (Research)" <millerjv at crd.ge.com>
Subject: RE: [Insight-users] Speed of Connected Components Filter
To: "Ken Urish" <ken.urish at gmail.com>, <insight-users at itk.org>
Message-ID:
	
<FA26BEF1EA775E4584FB34B91E14A1C4C169AF at SCHMLVEM01.e2k.ad.ge.com>
Content-Type: text/plain;	charset="iso-8859-1"

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