Tag Archives: Convex Hull opencv

Convexity Defects OpenCV

In the previous blog, we discussed how to find the convex hull for a particular shape. In this blog, let’s extend our convex hull knowledge to understand another important function known as Convexity defects. You will find its use in many applications such as hand gesture recognition etc. So, let’s get started.

What are Convexity Defects?

Any deviation of the contour from its convex hull is known as the convexity defect. Let’s understand this with the help of the below image.

Here, the red line shows the convex hull, the grey line represents the contour and the black arrow shows the deviation of the hull from the contour (convexity defect). So, it’s obvious that the convex curve has no convexity defects. Now, let’s discuss how to find the convexity defects using OpenCV-Python.

OpenCV

OpenCV provides a function cv2.convexityDefects() for finding the convexity defects of a contour. This takes as input the contour and its corresponding hull indices and returns an array containing the convexity defects as output. The basic syntax is given below.

The output contains an array where each row contains 4 values [start point, endpoint, farthest point, approximate distance to the farthest point]. Note that the first three values returned are indices of contour.

Now, let’s understand the output returned by the cv2.convexityDefects() function in more detail using the below image. Here, the green line represents the hull while the red line shows the corresponding contour. Clearly, there are convexity defects.

OpenCV algorithm for finding Convexity Defects

  • for each pair (H[i], H[i+1]) of adjacent hull points
    • for each contour point (C[n]) that lies between [H[i], H[i+1])
      • Find the point with the maximum distance from the line joining (H[i], H[i+1])
    • store the index of (H[i], H[i+1], max distance point) and the max distance in an array
  • Return the array

Now, let’s take a part of the above image and understand how the above algorithm works. Suppose there are 3 contour points between the first pair of hull points (H[0], H[1]).

OpenCV calculates the distance (d1, d2, d3) as shown below.

  • Calculate the unit vector for (H[0], H[1]) and rotate it by 90 degrees
  • Then project the vectors formed by joining the contour points (C[1], C[2], C[3]) with H[0] onto the unit vector as shown below. The projection is equal to the distances (d1, d2, d3).

Similarly, repeat for each pair of hull points. The full code can be found here. Now, let’s visualize the convexity defects using OpenCV-Python and the image as shown below.

Steps

  • Read an image and find its contours. This can be done as
Image Contour

Now, find the convex hull for the particular contour as shown below. Remember to pass the returnPoints flag as False. This will give us the indices of the contour points that make the hull.

Convex Hull

After that, find the convexity defects as shown below. This will give us the array as discussed above.

Since the defects array contains the indices of the contour points so, in order to visualize the defects, we need to convert them to coordinates. Here, we iterate over the array rows and draw a line joining the start point and end point, then draw a circle at the farthest point. This is done as below.

Convexity Defects

I hope you understood the convexity defects and how OpenCV calculates these defects. Hope you enjoy reading.

If you have any doubts/suggestions please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.

Finding Convex Hull OpenCV Python

In the previous blog, we discussed how to perform simple shape detection using contour approximation. In this blog, we will discuss how to find the convex hull of a given shape/curve. So, let’s first discuss what is a convex hull?

What is a Convex Hull?

Any region/shape is said to be convex if the line joining any two points (selected from the region) is contained entirely in that region. Another way of saying this is, for a shape to be convex, all of its interior angles must be less than 180 degrees or all the vertices should open towards the center. Let’s understand this with the help of the image below.

Convex vs concave

Now, for a given shape or set of points, we can have many convex curves/boundaries. The smallest or the tight-fitting convex boundary is known as a convex hull.

Convex Hull

Now, the next question that comes to our mind is how to find the convex hull for a given shape or set of points? There are so many algorithms for finding the convex hull. Some of the most common algorithms with their associated time complexities are shown below. Here, n is the no. of input points and h is the number of points on the hull.

OpenCV provides a builtin function for finding the convex hull of a point set as shown below

  • points: any contour or Input 2D point set whose convex hull we want to find.
  • clockwise: If it is True, the output convex hull is oriented clockwise. Otherwise, counter-clockwise.
  • returnPoints: If True (default) then returns the coordinates of the hull points. Otherwise, returns the indices of contour points corresponding to the hull points. Thus to find the actual hull coordinates in the second(False) case, we need to do contour[indices].

Now, let’s take an example and understand how to find the convex hull for a given image using OpenCV-Python.

sample image for finding Convex Hull

Steps:

  • Load the image
  • Convert it to greyscale
  • Threshold the image
  • Find the contours
  • For each contour, find the convex hull and draw it.

Below is the output of the above code.

Convex Hull output

Applications:

  • Collision detection or avoidance.
  • Face Swap
  • Shape analysis and many more.

Hope you enjoy reading.

If you have any doubts/suggestion please feel free to ask and I will do my best to help or improve myself. Good-bye until next time.