A Novel Algorithm for Exact Concave Hull Extraction
This work addresses a bottleneck in region extraction for applications like autonomous driving and cell biology by providing an exact method for concave hulls, though it is incremental as it builds on existing approximate approaches.
The paper tackles the problem of extracting exact concave hulls from uniform grids, which previously lacked precise solutions, by introducing a novel algorithm that produces vertex-minimized, pixel-perfect concave hulls with tunable speed-efficiency tradeoffs, and demonstrates significant improvements in image compression, such as context-dependent encoding achieving gains across biomedical and natural images.
Region extraction is necessary in a wide range of applications, from object detection in autonomous driving to analysis of subcellular morphology in cell biology. There exist two main approaches: convex hull extraction, for which exact and efficient algorithms exist and concave hulls, which are better at capturing real-world shapes but do not have a single solution. Especially in the context of a uniform grid, concave hull algorithms are largely approximate, sacrificing region integrity for spatial and temporal efficiency. In this study, we present a novel algorithm that can provide vertex-minimized concave hulls with maximal (i.e. pixel-perfect) resolution and is tunable for speed-efficiency tradeoffs. Our method provides advantages in multiple downstream applications including data compression, retrieval, visualization, and analysis. To demonstrate the practical utility of our approach, we focus on image compression. We demonstrate significant improvements through context-dependent compression on disparate regions within a single image (entropy encoding for noisy and predictive encoding for the structured regions). We show that these improvements range from biomedical images to natural images. Beyond image compression, our algorithm can be applied more broadly to aid in a wide range of practical applications for data retrieval, visualization, and analysis.