Much faster creation & rendering of complex ROIs #1777
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Inspired by CoverageUnion not quite working... it was very fast, but gave invalid results. This code (still needs cleaned up!) avoids unioning many polygons by instead delaying polygonization until the final step. This allows us to remove duplicates along tile boundaries before passing *everything* to a `Polygonizer`. There is probably still scope for some optimizations (e.g. replacing `LineDissolver`) and a need to clean up the code and update the comments. But currently it shortens the time to trace ~8 million vertices to ~25 seconds on my laptop, rather than >> 100 seconds. So committing this code now, lest I break it too badly...
This is especially important when displaying complex polygons in the viewer.
Squeezing out a bit more performance. Readability suffering further...
Calculate sequentially across downsamples & also improve caching. Drop small regions/holes that aren't visible.
Also faster
This speeds up the responsiveness of object lists
This was referenced Mar 2, 2025
Rylern
reviewed
Mar 3, 2025
qupath-core/src/main/java/qupath/lib/analysis/images/ContourTracing.java
Show resolved
Hide resolved
| * @param lines | ||
| * @return | ||
| */ | ||
| static Collection<CoordinatePair> removeDuplicatesCompletely(Collection<CoordinatePair> lines) { |
There was a problem hiding this comment.
These kind of functions could be unit tested
qupath-core/src/main/java/qupath/lib/analysis/images/CoordinatePair.java
Show resolved
Hide resolved
qupath-core/src/main/java/qupath/lib/analysis/images/ContourTracingUtils.java
Show resolved
Hide resolved
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Major performance improvements when creating complex ROIs (e.g. from a pixel classifier) and rendering them in the viewer.
ContourTracer improvements
Building on #1520, generating complex annotations can now be much faster.
For example, I applied a moderately high-resolution thresholder to
OS-2.ndpito generate a monster multipolygon with millions of vertices.On the same MacBook Pro:
The key step is to avoid creating polygons for each individual tile and unioning them at the end, because unioning is too expensive.
Instead, we trace all the lines across all the tiles and then pass them all in one big go to a
Polygonizerat the end.Some extra tricks and optimizations are used to speed this up, and also to reduce the number of vertices in the final result, without changing the shape.
The annotation above had about 7-8 million coordinates, while with this PR it is just under 5 million.
Faster rendering
Generating huge ROIs is one thing, rendering them is another.
This PR also makes this much more efficient using 2 tricks... and then a 3rd trick that renders one of the first two moot.
The tricks are:
ShapeSimplifierby replacing Java's built inPriorityQueuewith something smaller & faster to handle removals and insertionsShapeSimplifierentirely in the viewer, and instead introduceDownsampledShapeCache. This uses a much simpler method of shape simplification, while also discarding very small fragments or holes.The end result looks a bit different. I don't think it's worse, but the rendering might benefit from some tweaks in the future.
More critically, it is far more responsive. Previously, rendering the ROI might take up to a minute and it would be sluggish when zooming in & out until the simplified shapes were built. Viewing the image at a low resolution was slower than at a high resolution.
Now viewing at a low resolution should be fast, and the lag when zooming should be much less. Images with complex ROIs should also open much faster.