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

[Miller, James V (Research)]

Peter, 

I did run a number of experiments:

1) Using Lookup, Add, and Flatten when each new equivalency is added.
2) Using RecursiveLookup with Add (but delaying a call Flatten until all
equivalencies are formed.
3) Using RecursiveLookup with the new AddAndFlatten routine
4) Using RecursiveLookup with Add and periodically calling Flatten()

Options 2,3,4 all ran in approximately the same amount of time. Option
4 ran about 10% slower if period of flattening was too short.

Options 2,3,4 were all approximately 50X faster than option 1
running on a 10000x10000 image with 100000 components of size 25px.

My image was synthetic, so there could still be a difference that
appears when running on real data (with a larger distribution of
object shapes and sizes). But my take away so far is that for a large
number of components, it is better to use RecursiveLookup than
Flatten.

Jim	




-----Original Message-----
From: Peter Cech [mailto:pcech at vision.ee.ethz.ch]
Sent: Thursday, May 26, 2005 6:26 PM
To: Sayan Pathak
Cc: Peter Cech; Miller, James V (Research)
Subject: Re: [Insight-users] RE: Speed of Connected Components Filter


Hi,

seems my formulation caused some confusion, I meant this patch for
scenarios 2 to 4 as a partial replacement for calling Flatten on each
new equivalence. Sorry for that.

Sayan, could you test with both Jim's and mine patches? Thanks!

Peter

PS: Another optimization idea: flatten element in RecursiveLookup. Cost
of doing so is small and successive lookups of the same element can be
faster. Seems I should start benchmarking myself to see wheter such
optimizations are really working. Any suggestions how to generate good
test-cases?

On Thu, May 26, 2005 at 13:52:02 -0700, Sayan Pathak wrote:
> Hi Peter/Jim,
> I am testing Scenario 1 that Peter suggested and provided the patch.
> 
> > add_flattened.patch
> > Test of the idea described above. Proper implementation should provide
> > another method (say AddFlattened) instead of changing Add, but it
> should
> > suffice for testing and benchmarking.
> 
> My preliminary testing is not giving me any glaring speedup compared to
> the RecursiveLookup patch that Jim provided. I am running more genes so
> as to get a more complete picture with dependencies on the number of
> objects with different size distributions. 
> 
> Sayan