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.
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.
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.
- Gift wrapping, a.k.a. Jarvis march — O(nh)
- Graham scan — O(nlogn)
- Chan’s algorithm — O(nlogh)
- Sklansky (1982) — O(nlogn) ( OpenCV uses this algorithm)
OpenCV provides a builtin function for finding the convex hull of a point set as shown below
|
1 |
hull = cv2.convexHull(points [,clockwise [,returnPoints]]) |
- 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.
Steps:
- Load the image
- Convert it to greyscale
- Threshold the image
- Find the contours
- For each contour, find the convex hull and draw it.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
import cv2 # Load the image img1 = cv2.imread('D:/downloads/cars.JPG') # Convert it to greyscale img = cv2.cvtColor(img1, cv2.COLOR_BGR2GRAY) # Threshold the image ret, thresh = cv2.threshold(img,50,255,0) # Find the contours contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE) # For each contour, find the convex hull and draw it # on the original image. for i in range(len(contours)): hull = cv2.convexHull(contours[i]) cv2.drawContours(img1, [hull], -1, (255, 0, 0), 2) # Display the final convex hull image cv2.imshow('ConvexHull', img1) cv2.waitKey(0) |
Below is the output of the above code.
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.