Tag Archives: opencv python tutorial

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.

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.

Earth Mover’s Distance (EMD)

Leave a reply

In the previous blogs, we discussed various histogram comparison methods for image retrieval. Most of the methods we discussed were highly sensitive to blurring, local deformation or color shifts. etc. In this blog, we will discuss a more robust method for comparing the distributions known as Wasserstein metric or Earthmover’s distance. So, let’s get started.

In a formal sense, the notion of distance is more suitable to single elements as compared to distributions. For instance, if I say what is the distance from your house to the neighbor’s house? Most of you will come up with a number say x meters but where is this distance came from. Is it the distance between the centers of both the houses or the nearest distance between the two houses or any other form. Thus, the definition of distance becomes less apparent when we are dealing with distributions or sets of elements rather than single elements. So, in this blog, we will discuss the Earthmover’s distance also known as Wasserstein metric which is more suitable for finding distance or similarity between the distributions. This concept was first introduced by Gaspard Monge in 1781, in the context of transportation theory (Wikipedia). Let’s discuss the main concept behind this.

Let’s say we have two distributions A and B whose distance we want to calculate. This assumes one distribution to be a mass of earth or a pile of dirt and the other to be a collection of holes in that same space. The least amount of work done to fill the holes completely gives us the EMD. Filling the holes result in converting one distribution to another. The lesser the distance, the more similar will be the distributions and vice-versa.

Mathematically, we construct a matrix, say M, whose each element denotes the amount of weight transferred or matched between the distributions. For instance, M_ij denotes the weight transferred from the ith position in the first distribution to the jth position in the second distribution. The work done will be the weight transferred multiplied by the distance i.e. M_ij*d_ij. Thus the EMD is given by

There is an important terminology used in EMD known as a signature which is nothing but a way of representing any distribution. For instance, in this, we divide any distribution into clusters which are represented by the mean (or any other statistics) and the fraction of the distribution in that cluster. This representation by a set of clusters is called the signature.

Now, let’s see how to implement this. OpenCV provides a builtin function for calculating EMD as shown below.

cv2.EMD(signature1, signature2, distType[, cost[, lowerBound]])

1	cv2.EMD(signature1, signature2, distType[, cost[, lowerBound]])

Here, the signature is a matrix of size equal to the (total number of pixels x number of dimensions + 1). For greyscale, we have 2 dimensions, width, and height while for color image 3. Thus for greyscale, each row of signature represents (pixel value and the coordinates). To calculate the distance, you can use any metric such as L1 and L2 as cv2.DIST_L1 etc. You can pass the cost matrix using the cost argument. lower-bound is the distance between the center of mass of two signatures. This outputs the flow matrix (M discussed above), lower bound and the work.

Now, let’s take an example to understand this. First, you need to change the images to their corresponding signatures as shown below.

# image to signature for color image
def img_to_sig(img):
    sig = np.empty((img.size, 4), dtype=np.float32)
    idx = 0
    for i in range(img.shape[0]):
        for j in range(img.shape[1]):
            for k in range(img.shape[2]):
                sig[idx] = np.array([img[i,j,k], i, j,k])
                idx += 1
    return sig

# image to signature for color image

def img_to_sig(img):

sig = np.empty((img.size, 4), dtype=np.float32)

idx = 0

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

for j in range(img.shape[1]):

for k in range(img.shape[2]):

sig[idx] = np.array([img[i,j,k], i, j,k])

idx += 1

return sig

and then calculate the EMD as shown below.

import cv2
import numpy as np
img1 = cv2.imread('D:/downloads/app1.jpg')
img2 = cv2.imread('D:/downloads/app2.jpg')
sig1 = img_to_sig(img1)
sig2 = img_to_sig(img2)
distance, lowerbound, flow_matrix = cv2.EMD(sig1, sig2, cv2.DIST_L1,lowerBound=0)

import cv2

import numpy as np

img1 = cv2.imread('D:/downloads/app1.jpg')

img2 = cv2.imread('D:/downloads/app2.jpg')

sig1 = img_to_sig(img1)

sig2 = img_to_sig(img2)

distance, lowerbound, flow_matrix = cv2.EMD(sig1, sig2, cv2.DIST_L1,lowerBound=0)

Below is the output we got

Hope you enjoy reading.

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

Comparing Histograms using OpenCV-Python

1 Reply

In the previous blogs, we discussed a lot about histograms. We learned histogram equalization, making a histogram to match a specified histogram, back project a histogram to find regions of interest and even used a histogram for performing image thresholding. In this blog, we will learn how to compare the histograms for the notion of similarity. This comparison is possible because we can classify a number of things around us based on color. We will learn various single number evaluation metrics that tell how well two histograms match with each other. So, let’s get started.

The histogram comparison methods can be classified into two categories

Bin-to-Bin comparison
Cross-bin comparison

Bin-to-Bin comparison methods include L1, L2 norm for calculating the bin distances or bin intersection, etc. These methods assume that the histogram domains are aligned but this condition is easily violated in most of the cases due to change in lighting conditions, quantization, etc. Cross bin comparison methods are more robust and discriminative but this can be computationally expensive. To circumvent this, one can reduce the cross bin comparison to bin-to-bin. Cross bin comparison methods include Earthmoving distance (EMD), quadratic form distances (taking into account the bin similarity matrix), etc.

OpenCV provides a builtin function for comparing the histograms as shown below.

cv2.compareHist(H1, H2, method)

1	cv2.compareHist(H1, H2, method)

Here, H1 and H2 are the histograms we want to compare and the “method” argument specifies the comparison method. OpenCV provides several built-in methods for histogram comparison as shown below

HISTCMP_CORREL: Correlation
HISTCMP _CHISQR: Chi-Square
HISTCMP _CHISQR_ALT: Alternative Chi-Square
HISTCMP _INTERSECT: Intersection
HISTCMP _BHATTACHARYYA: Bhattacharyya distance
HISTCMP _HELLINGER: Synonym for CV_COMP_BHATTACHARYYA
HISTCMP _KL_DIV: Kullback-Leibler divergence

For the Correlation and Intersection methods, the higher the metric, the more accurate the match. While for chi-square and Bhattacharyya, the lower metric value represents a more accurate match. Now, let’s take an example to understand how to use this function. Here, we will compare the two images as shown below.

Steps:

Load the images
Convert it into any suitable color model
Calculate the image histogram (2D or 3D histograms are better) and normalize it
Compare the histograms using the above function

import cv2

# Load the images
img1 = cv2.imread('D:/downloads/app1.jpg')
img2 = cv2.imread('D:/downloads/app2.jpg')

# Convert it to HSV
img1_hsv = cv2.cvtColor(img1, cv2.COLOR_BGR2HSV)
img2_hsv = cv2.cvtColor(img2, cv2.COLOR_BGR2HSV)

# Calculate the histogram and normalize it
hist_img1 = cv2.calcHist([img1_hsv], [0,1], None, [180,256], [0,180,0,256])
cv2.normalize(hist_img1, hist_img1, alpha=0, beta=1, norm_type=cv2.NORM_MINMAX);
hist_img2 = cv2.calcHist([img2_hsv], [0,1], None, [180,256], [0,180,0,256])
cv2.normalize(hist_img2, hist_img2, alpha=0, beta=1, norm_type=cv2.NORM_MINMAX);

# find the metric value
metric_val = cv2.compareHist(hist_img1, hist_img2, cv2.HISTCMP_BHATTACHARYYA)

import cv2

# Load the images

img1 = cv2.imread('D:/downloads/app1.jpg')

img2 = cv2.imread('D:/downloads/app2.jpg')

# Convert it to HSV

img1_hsv = cv2.cvtColor(img1, cv2.COLOR_BGR2HSV)

img2_hsv = cv2.cvtColor(img2, cv2.COLOR_BGR2HSV)

# Calculate the histogram and normalize it

hist_img1 = cv2.calcHist([img1_hsv], [0,1], None, [180,256], [0,180,0,256])

cv2.normalize(hist_img1, hist_img1, alpha=0, beta=1, norm_type=cv2.NORM_MINMAX);

hist_img2 = cv2.calcHist([img2_hsv], [0,1], None, [180,256], [0,180,0,256])

cv2.normalize(hist_img2, hist_img2, alpha=0, beta=1, norm_type=cv2.NORM_MINMAX);

# find the metric value

metric_val = cv2.compareHist(hist_img1, hist_img2, cv2.HISTCMP_BHATTACHARYYA)

The metric value comes out to be around 0.99 which seems to be pretty good. Try changing the bin sizes and the comparison methods and observe the change. In the next blog, we will discuss Earthmoving distance (EMD), a cross bin comparison method that is more robust as compared to these methods. Hope you enjoy reading.

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

Read, Write and Display Videos with OpenCV Python

TheAILearner

Mastering Artificial Intelligence

Tag Archives: opencv python tutorial

Finding Convex Hull OpenCV Python

What is a Convex Hull?

Steps:

Applications:

Earth Mover’s Distance (EMD)

Comparing Histograms using OpenCV-Python

Steps:

Read, Write and Display Videos with OpenCV Python