Abstract
In this article, we present an algorithm to compute the convex hull of a binary shape. Efficient algorithms to compute the convex hull of a set of points had been proposed long time ago. For a binary shape, the common practice is to rely on one of them: to compute the convex hull of binary shape, all pixels of the shape are first listed, and then the convex hull is computed on this list of points. The computed convex hull is finally rasterized to provide the final result as, for example, in the famous scikit-image library. To compute the convex hull of an arbitrary set of points, the points of the list that lie on the outline of the convex hull must be selected (to simplify, we call these points “extrema”). To find them, for an arbitrary set of points, it is necessary to browse all the points but not in the particular case of a binary shape. In this specific situation, the extrema necessarily belong to the inner boundary of the shape. It is a waste of time to browse all the pixels as it is possible to discard most of them when we search for these extrema. Based on this analysis, we propose a new method to compute the convex hull dedicated to binary shapes. This method browses as few pixels as possible to select a small subset of boundary pixels. Then it deduces the convex hull only from this subset. As the size of the subset is very small, the convex hull is computed in real time. We compare it with the commonly used methods and common functions from libraries to prove that our approach is faster. This comparison shows that, for a very small shape, the difference is acceptable, but when the area of the shape grows, this difference becomes significant. This leads us to conclude that substituting current functions to compute convex hull of binary shapes with our algorithm in frequently used libraries would lead to a great improvement.