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

[Todd Gable]

Just an FYI, I made the change just now and rebuilt. One of my runs with 16k components went from 36sec to 7sec. If I get time, I'll make two binaries and run a batch on both to get more than one sample. Thanks for the work on this guys.

Todd

-----Original Message-----
From: Miller, James V (Research) [mailto:millerjv at crd.ge.com]
Sent: Wednesday, May 25, 2005 5:23 AM
To: Sayan Pathak
Cc: insight-users at itk.org; ken.urish at gmail.com
Subject: [Insight-users] RE: Speed of Connected Components Filter


Sayan, 

Would you mind running a few more tests?

Keep the code as you now have it, using RecursiveLookup() instead of of 
Lookup().  But add a call to Flatten() every now and again.

Just set a counter to say 8000 or 16000 or 80000, and decrement
the counter for each visited pixel.  When the counter reaches zero, call
Flatten() and reset the counter to original value. (We may change the code
around later using a different iterator to help).

I want to see if on these large images, it would make sense to flatten
the equivalency table periodically.  If you could provide timings for 
different strategies (different periods of flattening), that would be 
great.

The choices for the algorithm may be:

1. Flatten every time an equivelence is generated (this is the current code)
2. Never flatten (this is what you just tested)
3. Flatten every N pixels
4. Flatten every N new equivalences

I originally had the code written as you now have it.  I ran timing tests at
the time and found most of the algorithm time was in RecursiveLookup.  So I 
changed the code to Flatten after every new equivalence which yielded a 30%
speedup.  But I was working on small images with a small number of components
(512x512 images with few hundred components).

Jim



-----Original Message-----
From: Sayan Pathak [mailto:SayanP at alleninstitute.org]
Sent: Tuesday, May 24, 2005 9:01 PM
To: Miller, James V (Research)
Cc: insight-users at itk.org; ken.urish at gmail.com
Subject: RE: Speed of Connected Components Filter


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


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