# A Novel Algorithm for Exact Concave Hull Extraction

arXiv: https://arxiv.org/abs/2206.11481 · HTML: https://mlsanity.com/paper/2206.11481/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 50 references that are in the map.
- First posted on arXiv 23 Jun 2022.

## Builds on (most cited first, 5 of 5)

- [fastMRI: An Open Dataset and Benchmarks for Accelerated MRI](https://mlsanity.com/paper/1811.08839/) (2018)
- [PadChest: A large chest x-ray image dataset with multi-label annotated reports](https://mlsanity.com/paper/1901.07441/) (2019)
- [Underwater Single Image Color Restoration Using Haze-Lines and a New Quantitative Dataset](https://mlsanity.com/paper/1811.01343/) (2018)
- [Multiview RGB-D Dataset for Object Instance Detection](https://mlsanity.com/paper/1609.07826/) (2016)
- [Adaptive Mesh Representation and Restoration of Biomedical Images](https://mlsanity.com/paper/1406.7062/) (2014)

## Abstract (arXiv)

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.