Skip to content

Improve ContourTracing performance#1520

Merged
petebankhead merged 5 commits intoqupath:mainfrom
petebankhead:contour-tracing
May 10, 2024
Merged

Improve ContourTracing performance#1520
petebankhead merged 5 commits intoqupath:mainfrom
petebankhead:contour-tracing

Conversation

@petebankhead
Copy link
Member

@petebankhead petebankhead commented May 9, 2024

This makes ContourTracing much faster in some circumstances - especially when labeled images were involved.

There are two main differences:

  1. Previously, the code would tend to loop through all pixels to generate the contour for each label; now it generates bounding boxes in a single loop, and then iterates only through the relevant bounding box for each label (when using createROIs)
  2. The tracing algorithm has been replaced by a reliance on JTS's Polygonizer class; this was already used before, but now we rely on it more heavily.

The second of these makes this slightly risky - I encountered exceptions and infinite loops along the way, so this needs to be tested very carefully.

@petebankhead
Faster ContourTracing
e7874f4 
Alternative approach that relies more heavily on JTS and Polygonize.
@petebankhead
Improve ContourTracing performance
a9e4c5c 
This makes `ContourTracing` much faster in some circumstances - especially when labeled images were involved.

There are two main differences:
1. Previously, the code would tend to loop through all pixels to generate the contour for each label; now it generates bounding boxes in a single loop, and then iterates only through the relevant bounding box for each label (when using `createROIs`)
2. The tracing algorithm has been replaced by a reliance on JTS's `Polygonizer` class; this was already used before, but now we rely on it more heavily.

The second of these makes this *slightly* risky - I encountered exceptions and infinite loops along the way, so this needs to be tested very carefully.
@petebankhead petebankhead added this to the v0.6.0 milestone May 9, 2024
@alanocallaghan
Copy link
Contributor

alanocallaghan commented May 10, 2024

Speed improvement is really noticable!

There is a non-zero chance that I'm misunderstanding this, but I strongly dislike this if/else block. First, I'd prefer to get the short block out of the way first by an early return.

qupath/qupath-core/src/main/java/qupath/lib/analysis/images/ContourTracing.java

Lines 608 to 647 in a9e4c5c

if (maxLabel > minLabel) {
var envelopes = new HashMap<Float, Envelope>();
for (int y = 0; y < image.getHeight(); y++) {
for (int x = 0; x < image.getWidth(); x++) {
float val = image.getValue(x, y);
if (val >= minLabel && val <= maxLabel) {
envelopes.computeIfAbsent(val, k -> new Envelope()).expandToInclude(x, y);
}
}
}
double xOffset = 0;
double yOffset = 0;
if (region != null && region.getDownsample() == 1) {
xOffset = region.getX();
yOffset = region.getY();
}
for (var entry : envelopes.entrySet()) {
var val = entry.getKey();
var envelope = entry.getValue();
var geom = traceGeometry(image, val, val, xOffset, yOffset, envelope);
if (geom != null && !geom.isEmpty()) {
// Handle rescaling if needed
if (region != null && region.getDownsample() != 1 && geom != null) {
double scale = region.getDownsample();
var transform = AffineTransformation.scaleInstance(scale, scale);
transform = transform.translate(region.getX(), region.getY());
if (!transform.isIdentity())
geom = transform.transform(geom);
}
var roi = GeometryTools.geometryToROI(geom, region == null ? ImagePlane.getDefaultPlane() : region.getImagePlane());
rois.put(val, roi);
}
}
} else {
for (int i = minLabel; i <= maxLabel; i++) {
var roi = createTracedROI(image, i, i, region);
if (roi != null && !roi.isEmpty())
rois.put(i, roi);
}
}

Second, is this for loop doing anything?

qupath/qupath-core/src/main/java/qupath/lib/analysis/images/ContourTracing.java

Lines 642 to 646 in a9e4c5c

for (int i = minLabel; i <= maxLabel; i++) {
var roi = createTracedROI(image, i, i, region);
if (roi != null && !roi.isEmpty())
rois.put(i, roi);
}

If maxLabel <= minLabel, then presumably maxLabel == minLabel, and either way
for (int i = minLabel; i <= maxLabel; i++) { is at most going to do one iteration.

@petebankhead
Copy link
Member Author

petebankhead commented May 10, 2024

Thanks! I've just pushed some changes that I was working on while you were reviewing... since it basically rewrites createROIs to make it simpler and less a hack-y adjustment of the original, I think it addresses your last comments.

@petebankhead
Copy link
Member Author

petebankhead commented May 10, 2024

The for (var entry : envelopes.entrySet()) loop in createROIs should be easily parallelizable - I'll check if that helps as well.

I was having trouble with locationtech/jts#874 but these problems seem to have disappeared... slightly concerningly as I'm not entirely sure what I changed to make them disappear. That's my main worry about this PR.

alanocallaghan
alanocallaghan reviewed May 10, 2024
View reviewed changes
qupath-core/src/main/java/qupath/lib/analysis/images/ContourTracing.java Outdated
if (p > maxValue)
maxValue = p;
var envelopes = new HashMap<Number, Envelope>();
if (minLabel != maxLabel) {
Copy link
Contributor

@alanocallaghan alanocallaghan May 10, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can we invert this if/else? Keeps the start of the two branches closer to the relevant condition

Copy link
Member Author

@petebankhead petebankhead May 10, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't mind. I thought it was easier to read to show the use of envelopes before showing their non-use in a special case.

@alanocallaghan
Copy link
Contributor

alanocallaghan commented May 10, 2024

Yeah, I didn't come across that myself yet trying a few images, are we using a version of JTS that at least has the exception code to avoid infinite loops?

Aside from style it all looks good and correct to me, but I wouldn't necessarily use that as strong evidence that it is :)

@petebankhead
Copy link
Member Author

petebankhead commented May 10, 2024

As far as I can tell, there isn't a version of JTS that has the exception bit merged - just a commit on a fork. An infinite loop was what I was seeing, unfortunately.

Was wondering if we should reinstate the old code and activate it via a system properly, but since the old code also uses Polygonizer it might not be immune from the problem anyway.

@petebankhead petebankhead marked this pull request as ready for review May 10, 2024 10:02
@petebankhead petebankhead merged commit 5066159 into qupath:main May 10, 2024
@petebankhead petebankhead deleted the contour-tracing branch May 10, 2024 11:48
@petebankhead petebankhead mentioned this pull request Mar 1, 2025
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@alanocallaghan alanocallaghan alanocallaghan left review comments

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

v0.6.0

Development

Successfully merging this pull request may close these issues.

2 participants

@petebankhead @alanocallaghan