How to find the bounding box Iterator<Localizable> efficiently

#1

I need to find the bounding box of an Iterator<Localizable> I have the following implementation ATM (only in 1D along a given dimension).

	private ValuePair<Integer,Integer> getComponentLimits(Iterator<Localizable> pixelPositionIterator, int dim){
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;

		while(pixelPositionIterator.hasNext()){
			Localizable location = pixelPositionIterator.next();
			final int pos =  location.getIntPosition( dim );
			min = Math.min( min, pos );
			max = Math.max( max, pos );
		}
		return new ValuePair<>(min, max);
	}

But the loop is killing performance (I need to run this very often).
So how can I optimize this?

#2

Hi @michaelmell,

With different sets of points each time, right? Stating the obvious (sorry, but gotta say it just in case), but don’t do this multiple times for a single set of points.

Besides that, it will be hard to give super constructive advice without more context-

  1. where do the points come from?
  2. Is there any structure to them?
  3. Why are you doing this many times /
  4. Is there any relationship between the points each time you do this?

Without that kind of information it will be hard to give great feedback. That being said, here are some thoughts.

John

General ideas

Idea 1 (easy, but probably not a huge benefit)

If you need the bounding box, compute the min/max over all dimensions in one loop.

Idea 2 (parallelize)

Have multiple threads, each finding and returning the bounding box of a subset of your points. It’s fast to find the smallest containing bounding box of several boxes.

Other (context dependent) ideas

Idea 3

If there’s some algorithm generating these points which itself probably has to loop over an image? If so - keep track of the bounding box from within that algorithm.

Idea 4 approximate (maybe not great idea)

If you have tons of points and don’t need an exact answer - randomly sample, and compute on a subset only. Obviously this works best on quantities that are not sensitive to single big values (like min and max are).

Idea 5 (really depends on what you’re doing)

Just saying this so I don’t forget -
Imgbli2 has a kd-tree implementation (see here), that I often use when need to search sets of points by distance.

1 Like
#3

Hi @bogovicj,

Thank you for the suggenstions.

I think, I just realized why, the code above kills my performance: It is called much more often than is necessary.

MoMA (the software I am working on) uses BuildComponentTree to generate a tree of possible segmentation hypotheses, where it overrides the emit method in PartialComponent.Handler.
I was using that overriden method to do the filtering (see code-snippet below).
However in the comment to the code calling emit it says:

   This is called whenever the current value is raised.

So it is being called a way to often, as I only want to call this on the finished components. Are you familiar with the ComponentTree and could give pointer on how to achieve this?

#4

MoMa = Mother machine analyzer right?

Are these the lines of code you mean?

#5

MoMa = Mother machine analyzer right?

Exactly.

private void processStack( final T value )

is the location, where the overriden emit method is called - at componentOutput.emit( component );.

You can find the class I am talking about at here (which overrides emit). That is where I currently do the filtering like so (the code below is not yet pushed to Github):

	@Override
	public void emit( final FilteredPartialComponent< T > intermediate ) {
		final long size = intermediate.pixelList.size();
		final ValuePair<Integer,Integer> componentLimits = getComponentLimits(intermediate.pixelList.iterator(), 0);
		int width = componentLimits.b - componentLimits.a;

		if ( size >= minComponentSize && size <= maxComponentSize && width <= maxComponentWidth && width >= minComponentWidth) {
                
                ...