Convex Hull opencv | TheAILearner

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.

convexityDefects = cv2.convexityDefects(contour, convexhull)

# contour: input contour
# convexhull: indices of the contour points that make the hull.
# convexityDefects: an array where each row contains these values - [start point, end point, farthest point, approximate distance to farthest point].

convexityDefects = cv2.convexityDefects(contour, convexhull)

# contour: input contour

# convexhull: indices of the contour points that make the hull.

# convexityDefects: an array where each row contains these values - [start point, end point, farthest point, approximate distance to farthest point].

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 (d₁, d₂, d₃) 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 (d₁, d₂, d₃).

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

import cv2
import numpy as np
img = cv2.imread('star.jpg')
img_gray = cv2.cvtColor(img,cv.COLOR_BGR2GRAY)
ret, thresh = cv2.threshold(img_gray, 127, 255,0)
contours, hierarchy = cv2.findContours(thresh,2,1)
cnt = contours[0]

import cv2

import numpy as np

img = cv2.imread('star.jpg')

img_gray = cv2.cvtColor(img,cv.COLOR_BGR2GRAY)

ret, thresh = cv2.threshold(img_gray, 127, 255,0)

contours, hierarchy = cv2.findContours(thresh,2,1)

cnt = contours[0]

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.

hull = cv2.convexHull(cnt, returnPoints = False)

1	hull = cv2.convexHull(cnt, returnPoints = False)

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

defects = cv2.convexityDefects(cnt, hull)

1	defects = cv2.convexityDefects(cnt, hull)

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.


for i in range(defects.shape[0]):
    s,e,f,d = defects[i,0]
    start = tuple(cnt[s][0])
    end = tuple(cnt[e][0])
    far = tuple(cnt[f][0])
    cv.line(img,start,end,[0,255,0],2)
    cv.circle(img,far,5,[0,0,255],-1)

cv2.imshow('final_img',img)
cv2.waitKey(0)

for i in range(defects.shape[0]):

s,e,f,d = defects[i,0]

start = tuple(cnt[s][0])

end = tuple(cnt[e][0])

far = tuple(cnt[f][0])

cv.line(img,start,end,[0,255,0],2)

cv.circle(img,far,5,[0,0,255],-1)

cv2.imshow('final_img',img)

cv2.waitKey(0)

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.

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

hull = cv2.convexHull(points [,clockwise [,returnPoints]])

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.

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)

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.

TheAILearner

Mastering Artificial Intelligence

Tag Archives: Convex Hull opencv

Convexity Defects OpenCV