Speed up ellipsoid image creation

[mdoube]

Describe the bug Ellipsoid image creation takes about twice as long in EF2 as in EF1

Expected behavior EF2 should be faster than EF1

Additional context Each foreground pixel has to be given the EF value of the maximal ellipsoid that contains it.

In EF1 that was achieved by limiting search scope aggressively:

• the z bound (and y bound) of each ellipsoid was calculated so that a shortlist of potential ellipsoids was generated for each slice/row
• the ellipsoid list was sorted once and traversed from largest to smallest, so that the whole list did not need to be searched each time: the first positive contains() hit was guaranteed to be the biggest, no need to search the rest.
• the contains() method was optimised to exclude unlikely ellipsoids cheaply and early in its execution

EF2 does this:

    private Img<IntType> assignEllipsoidIDs(final Img<BitType> mask, final List<QuickEllipsoid> ellipsoids) {

        final Img<IntType> idImage = ArrayImgs.ints(mask.dimension(0), mask.dimension(1),weightedAverageN, mask.dimension(2));
        idImage.forEach(c -> c.setInteger(-1));

        for(int nn=0;nn<weightedAverageN;nn++) {
            final int n = nn;
            final Map<QuickEllipsoid, Integer> iDs = IntStream.range(0, ellipsoids.size()).boxed()
                    .collect(toMap(ellipsoids::get, Function.identity()));
            final LongStream zRange = LongStream.range(0, mask.dimension(2));
            zRange.parallel().forEach(z -> {
                // multiply by image unit? make more intelligent bounding box?
                final List<QuickEllipsoid> localEllipsoids = ellipsoids.stream()
                        .filter(e -> Math.abs(e.getCentre()[2] - z) < e.getSortedRadii()[2]).collect(toList());
                final long[] mins = {0, 0, z};
                final long[] maxs = {mask.dimension(0) - 1, mask.dimension(1) - 1, z};
                final Cursor<BitType> maskSlice = Views.interval(mask, mins, maxs).localizingCursor();
                colourSlice(idImage, maskSlice, localEllipsoids, iDs, n);
            });
        }
        return idImage;
    }

[alessandrofelder]

EF2 does at least conceptually the same steps as EF1.

Foreach z slice, the line listed above:

final List<QuickEllipsoid> localEllipsoids = ellipsoids.stream()
                        .filter(e -> Math.abs(e.getCentre()[2] - z) < e.getSortedRadii()[2]).collect(toList);

keeps only a list of those ellipsoids are possibly relevant for this z slice. The ellipsoids are already sorted at this point, so the same idea of finding the first contains() is used. Contains() uses ~the same way of excluding unlikely ellipsoids, IIRC.

I think ways of improving this are therefore refactoring the code (different way of parallelisation) or coming up with new ideas to the concept?

[mdoube]

keeps only a list of those ellipsoids are possibly relevant for this z slice.

OK. But it is not strict enough, limiting only to a bounding sphere (there is no guarantee that the longest axis is in z) and also needs to filter in y. See the axis aligned bounding box, which allows filtering in z and y.

Contains() uses ~the same way of excluding unlikely ellipsoids

I see that QuickEllipsoid has the same contains() method as EF1, but it seems not to be used.

[alessandrofelder]

Will have a look at the AABB when I can make some time - thanks.

QuickEllipsoid::contains used on line 506 of EllipsoidFactorWrapper.java