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.

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.

Earth Mover’s Distance (EMD)

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, Mij 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. Mij*dij. 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.

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.

and then calculate the EMD as shown below.

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

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.

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

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

In this blog, we will see how to Read, Write and Display Videos using OpenCV. Since a video is made up of images, most of the commands we learned in the previous blog also applies here.

Let’s see by an example how to capture video from the camera and display it.

cv2.VideoCapture(0) will open the default camera. You can select the second camera by passing 1, third by passing 2 and so on. This creates a VideoCapture object (“cap” here).

cap.read() capture frame by frame. This returns two values, frame and ret. If the frame is read correctly, ret will be True otherwise False.

cv2.waitKey(1) & 0xFF == ord(‘q’) will exit the video when ‘q’ is pressed.

cap.release() closes video file or capturing device.

If you want to play a video from a file, just change the cv2.VideoCapture(0) function in the above code by giving the file path as cv2.VideoCapture(‘F:/downloads/Python.mp4’). Also, use the appropriate time for cv2.waitKey() function (25 will be OK).

Saving a Video:

First, create a VideoWriter object with cv2.VideoWriter(output filename, fourcc, fps, frameSize). fourcc(4-character code of codec) is used to compress the frames. After creating this object, use object.write() to save the video. Let’s see an example

Now, you might have got some feeling about the basic video commands in OpenCV. 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.