What is a convex hull?

A convex hull of a set of points is defined as the smallest convex polygon containing all the points. In other words, it is the outer boundary of the set of points that forms a shape with no indentations or concave portions.

The convex hull can be represented as a polygon formed by connecting the outermost points counterclockwise or clockwise. It can also be described as the intersection of all convex sets containing the given points.

The following slides illustrate the points and their convex hull.

Applications

The convex hull has various applications, such as:

• Computational geometry: It is used in algorithms for solving problems like finding the closest pair of points or solving linear programming problems.

• Image processing: Convex hulls can be used to analyze and recognize image shapes, particularly for object recognition or tracking.

• Robotics: Convex hulls are useful for collision detection and path planning in robotics applications.

• Game development: Convex hulls are employed in physics engines for collision detection and response between objects in games.

Convex hull in image processing

In image processing, the convex hull is used as a technique to analyze and extract shape information from images. It helps identify and represent the outer boundaries of objects or regions within an image.

Here’s how the convex hull is applied in image processing:

1. Object segmentation: The convex hull can be utilized to segment objects from the background in an image. By identifying the outermost points of an object and constructing its convex hull, it is possible to separate the object from the surrounding area.

2. Shape analysis: The convex hull can provide valuable information about the shape and geometry of an object within an image. Encapsulating its outer boundary helps determine an object’s overall size, orientation, and extent.

3. Object recognition: Convex hulls can be employed as features for object recognition and classification. By extracting the convex hull of an object and comparing it with predefined templates or models, it becomes possible to identify and classify objects in an image.

4. Contour approximation: The convex hull can be used to approximate the contour of an object or region. By connecting the outermost points of the object’s contour, a simplified representation of the shape can be obtained, which is useful for further analysis or processing.

Let’s understand the working example of the convex hull in image processing below.

Code explanation

• Line 1: We import the pyplot module from the matplotlib library. This module provides an interface for creating plots and visualizations.
• Line 2: We import the convex_hull_image function from the skimage.morphology module. This function calculates the convex hull of a binary image.
• Line 3: We import the data and img_as_float modules from the skimage library. These modules provide utility functions for working with images.
• Line 4: We import the invert function from the skimage.util module. This function inverts the pixel values of an image.
• Line 5: We import the threshold_otsu function from the skimage.filters module. This function calculates the optimal threshold value for image segmentation using Otsu’s method.
• Line 6: We import the skio module from the skimage.io library. This module provides functions for reading and writing images.
• Line 7: We load an image named “points.png” and convert it to grayscale using the skio.imread function. The resulting image is stored in the image variable.
• Line 8: We calculate the optimal threshold value for image segmentation using Otsu’s method and store it in the thresh variable.
• Line 9: We threshold the image using the calculated threshold value and store the result in the image variable.
• Line 10: We calculate the convex hull of the inverted thresholded image using the convex_hull_image function and store the result in the chull variable.

The following lines involve plotting and visualization:

• Line 12: We create a figure with two subplots using the subplots function from pyplot. The subplots will be arranged in a 1x2 grid, and the figure size is set to (12, 6) inches. The resulting figure and axes are stored in the fig and axes variables.
• Line 13: We extract the individual axes from the axes variable and store them in the ax variable.
• Line 15: We set the title of the first subplot to “Points” using the set_title function of the first axis (ax[0]).
• Line 16: We display the thresholded image in the first subplot using the imshow function of the first axis. The colormap plt.cm.gray is used to display the image in grayscale.
• Line 17: We turn off the axis labels for the first subplot using the set_axis_off function of the first axis.
• Line 19: We set the title of the second subplot to “Convex Hull” using the set_title function of the second axis (ax[1]).
• Line 20: We display the convex hull image in the second subplot using the imshow function of the second axis. The colormap plt.cm.gray is used to display the image in grayscale.
• Line 21: We turn off the axis labels for the second subplot using the set_axis_off function of the second axis.
• Line 23: We adjust the spacing between subplots and labels using the tight_layout function.
• Line 24: We display the figure with the subplots using the show function from pyplot.