April, 19th 2016
A good approximation of the convex skull
Gunilla Borgefors

Uppsala, Sweden
gunilla.borgefors@it.uu.se

We are all familiar with the convex hull of an object. It is easy to compute and the convex deficiencies can be a good help in describing the shape. It would be very nice to have a useful algorithm for the convex scull, which would enable the identification and use of the protrusions for shape description.

The convex scull of a shape is the largest enclosed convex subset of the shape. There exists an algorithm for computing the exact convex skull, but it is O(n^7) where n is the number of edge points [1]. There also exists a fast but bad approximation [1], which is useful for small shapes but as essentially computes the largest inscribed octagon the approximation can be very bad for large shapes. How to compute a good approximation that is not too time consuming? Or even better, an exact algorithm that is less than O(n^7).

[1] Chassery, J.M., Coeurjolly, D.: Optimal shape and inclusion. In Ronse, C., Najman, L., Decencière, E., eds.: Mathematical Morphology: 40 Years On. Computational Imaging and Vision, Springer, Dordrecht (2005) 229-248

[2] Borgefors, G., Strand R., An approximation of the maximal inscribed convex set of a digital object, In: Image Analysis and Processing (ICIAP 2005), Eds. F. Roli, S. Vitulano, Lecture Notes in Computer Science 3617, Springer-Verlag, Berlin 2005, pp. 438-445