From Binary to Grey Scale Convex Hulls

Article type: Research Article

Authors: Soille, Pierre

Affiliations: Image Analysis and Control Group, Silsoe Research Institute, Wrest Park, Silsoe, Bedford, MK45 4HS, U.K. [email protected]

Note: [] Address for correspondence: Advanced Methods Sector JRC-Space Applications Institute TP 441, 1-21020 Ispra, Italy

Abstract: The convex hull of a set is the smallest convex set containing this set. In ℜ2, this definition is equivalent to the intersection of all half-planes containing the set. We show that this latter definition is nothing but an algebraic closing that can be applied to 2-D grey scale images. The resulting grey scale image is convex, in the sense that all its cross-sections are convex. An efficient translation-invariant implementation, leading to a decreasing family of convex sets that converges to an exact discrete convex hull, is proposed.

Keywords: convex hull, pattern recognition, shape description, image analysis, discrete geometry, mathematical morphology, algorithms, half-plane closing

DOI: 10.3233/FI-2000-411205

Journal: Fundamenta Informaticae, vol. 41, no. 1-2, pp. 131-146, 2000