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

Uppsala, Sweden

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