Shape Matching using Hu Moments (C++ / Python)

In this post, we will show how to use Hu Moments for shape matching. You will learn the following

What are image moments?
How are image moments calculated?
What are Hu moment invariants (or Hu Moments)?
How to calculate Hu Moments for an image using OpenCV?
How can Hu Moments be used for finding similarity between two shapes.

Let’s dive into the details

1. What are Image Moments?

Image moments are a weighted average of image pixel intensities. Let’s pick a simple example to understand the previous statement.

For simplicity, let us consider a single channel binary image $I$ . The pixel intensity at location $(x,y)$ is given by $I(x,y)$ . Note for a binary image $I(x,y)$ can take a value of 0 or 1.

The simplest kind of moment we can define is given below

(1) $\begin{align*}M = \sum_{x} \sum_{y} I(x,y)\end{align*}$

All we are doing in the above equation is calculating the sum of all pixel intensities. In other words, all pixel intensities are weighted only based on their intensity, but not based on their location in the image.

For a binary image, the above moment can be interpreted in a few different ways

It is the number of white pixels ( i.e. intensity = 1 ).
It is area of white region in the image.

So far you may not be impressed with image moments, but here is something interesting. Figure 1 contains three binary images — S ( S0.png ), rotated S ( S5.png ), and K ( K0.png ).

This image moment for S and rotated S will be very close, and the moment for K will be different.

For two shapes to be the same, the above image moment will necessarily be the same, but it is not a sufficient condition. We can easily construct two images where the above moment is the same, but they look very different.

Master Generative AI for CV

Get expert guidance, insider tips & tricks. Create stunning images, learn to fine tune diffusion models, advanced Image editing techniques like In-Painting, Instruct Pix2Pix and many more

2. How are image moments calculated?

Let’s look at some more complex moments.

(2) $\begin{align*}M_{ij} = \sum_{x} \sum_{y} x^{i} y^{j} I(x,y)\end{align*}$

where $i$ and $j$ are integers ( e.g. 0, 1, 2 ….). These moments are often referred to as raw moments to distinguish them from central moments mentioned later in this article.

Note the above moments depend on the intensity of pixels and their location in the image. So intuitively these moments are capturing some notion of shape.

TL;DR : Image moments capture information about the shape of a blob in a binary image because they contain information about the intensity $I(x,y)$

, as well as position $x$

and $y$

of the pixels.

Centroid using Image Moments

The centroid of a binary blob is simply its center of mass. The centroid $(\bar{x},\bar{y})$ is calculated using the following formula.

(3) $\begin{align*}\bar{x} &= \frac{M_{10}}{M_{00}}\\\bar{y} &= \frac{M_{01}}{M_{00}}\end{align*}$

We have explained this in a greater detail in our prev ious post.

2.1 Central Moments

Central moments are very similar to the raw image moments we saw earlier, except that we subtract off the centroid from the $x$ and $y$ in the moment formula.

(4) $\begin{align*}\mu_{ij} = \sum_{x} \sum_{y} \left ( x - \bar{x} \right)^{i} \left ( y - \bar{y} \right )^{j} I(x,y)\end{align*}$

Notice that the above central moments are translation invariant. In other words, no matter where the blob is in the image, if the shape is the same, the moments will be the same.

Won’t it be cool if we could also make the moment invariant to scale? Well, for that we need normalized central moments as shown below.

(5) $\begin{align*}\eta_{ij} = \frac{\mu_{i,j}}{\mu_{00}^{(i+j)/2 + 1}}\end{align*}$

TL;DR : Central moments are translations invariant, and normalized central moments are both translation and scale invariant.

3. What are Hu Moments?

It is great that central moments are translation invariant. But that is not enough for shape matching. We would like to calculate moments that are invariant to translation, scale, and rotation as shown in the Figure below.

Fortunately, we can in fact calculate such moments and they are called Hu Moments.

Definition

Hu Moments ( or rather Hu moment invariants ) are a set of 7 numbers calculated using central moments that are invariant to image transformations. The first 6 moments have been proved to be invariant to translation, scale, and rotation, and reflection. While the 7th moment’s sign changes for image reflection.

The 7 moments are calculated using the following formulae :

(6) $\begin{align*}h_0 &= \eta_{20} + \eta_{02} \\h_1 &= (\eta_{20} - \eta_{02})^2 + 4 \eta_{11}^2 \\h_2 &= (\eta_{30} - 3 \eta_{12})^2 + (3 \eta_{21} - \eta_{03})^2 \\h_3 &= (\eta_{30} + \eta_{12})^2 + (\eta_{21} + \eta_{03})^2 \\h_4 &= (\eta_{30} - 3 \eta_{12})(\eta_{30} + \eta_{12})[(\eta_{30} + \eta_{12})^2 - 3 (\eta_{21} + \eta_{03})^2] + (3 \eta_{21} - \eta_{03})[3 (\eta_{30} + \eta_{12})^2 - (\eta_{21} + \eta_{03})^2] \\h_5 &= (\eta_{20} - \eta_{02})[(\eta_{30} + \eta_{12})^2 - (\eta_{21} + \eta_{03})^2 + 4 \eta_{11} (\eta_{30} + \eta_{12})(\eta_{21} + \eta_{03})] \\h_6 &= (3\eta_{21} - \eta_{03})(\eta_{30} + \eta_{12})[(\eta_{30} + \eta_{12})^2 - 3(\eta_{21} + \eta_{03})^2] + (\eta_{30} - 3\eta_{12})(\eta_{21} + \eta_{03})[3(\eta_{30} + \eta_{12})^2 - (\eta_{21} + \eta_{03})^2]\end{align*}$

Please refer to this paper if you are interested in understanding the theoretical foundation of Hu Moments.

4. How to calculate Hu Moments in OpenCV?

Next, we will show how to use OpenCV’s built-in functions

Fortunately, we don’t need to do all the calculations in OpenCV as we have a utility function for Hu Moments. In OpenCV, we use HuMoments() to calculate the Hu Moments of the shapes present in the input image.

Let us discuss step by step approach for calculation of Hu Moments in OpenCV.

Read in image as Grayscale

First, we read an image as a grayscale image. This can be done in a single line in Python or C++.

Python

# Read image as grayscale image 
im = cv2.imread(filename,cv2.IMREAD_GRAYSCALE

C++

// Read image as grayscale image 
Mat im = imread(filename,IMREAD_GRAYSCALE);

Binarize the image using thresholding : Since our data is simply white characters on a black background, we threshold the grayscale image to binary:

Download Code To easily follow along this tutorial, please download code by clicking on the button below. It's FREE!

Python

# Threshold image 
_,im = cv2.threshold(im, 128, 255, cv2.THRESH_BINARY)

C++

// Threshold image 
threshold(im, im, 128, 255, THRESH_BINARY);

Calculate Hu Moments

OpenCV has a built-in function for calculating Hu Moments. Not surprisingly it is called HuMoments. It takes as input the central moments of the image which can be calculated using the function moments

Python

# Calculate Moments 
moments = cv2.moments(im) 
# Calculate Hu Moments 
huMoments = cv2.HuMoments(moments)

C++

// Calculate Moments 
Moments moments = moments(im, false); 
// Calculate Hu Moments 
double huMoments[7]; 
HuMoments(moments, huMoments);

Log Transform

The Hu Moments obtained in the previous step have a large range. For example, the 7 Hu Moments of K ( K0.png ) shown above
h[0] = 0.00162663
h[1] = 3.11619e-07
h[2] = 3.61005e-10
h[3] = 1.44485e-10
h[4] = -2.55279e-20
h[5] = -7.57625e-14
h[6] = 2.09098e-20

Note that hu[0] is not comparable in magnitude as hu[6]. We can use use a log transform given below to bring them in the same range

(7) $\begin{align*}H_i = - \text{sign}(h_i) \log | h_i |\end{align*}$

After the above transformation, the moments are of comparable scale
H[0] = 2.78871
H[1] = 6.50638
H[2] = 9.44249
H[3] = 9.84018
H[4] = -19.593
H[5] = -13.1205
H[6] = 19.6797

The code for log scale transform is shown below.

Python

# Log scale hu moments 
for i in range(0,7):
   huMoments[i] = -1* copysign(1.0, huMoments[i]) * log10(abs(huMoments[i])))

C++

// Log scale hu moments 
for(int i = 0; i < 7; i++) {
    huMoments[i] = -1 * copysign(1.0, huMoments[i]) * log10(abs(huMoments[i])); 
}

5. Shape Matching using Hu Moments

As mentioned earlier, all 7 Hu Moments are invariant under translations (move in x or y direction), scale and rotation. If one shape is the mirror image of the other, the seventh Hu Moment flips in sign. Isn’t that beautiful?

Let’s look at an example. In the table below we have 6 images and their Hu Moments.

As you can see, the image K0.png is simply the letter K, and S0.png is the letter S. Next, we have moved the letter S in S1.png, and moved + scaled it in S2.png. We added some rotation to make S3.png and further flipped the image to make S4.png.

Notice that all the Hu Moments for S0, S1, S2, S3, and S4 are close to each other in value except the sign of last Hu moment of S4 is flipped. Also, note that they are all very different from K0.

5.1 Distance between two shapes using matchShapes

In this section, we will learn how to use Hu Moments to find the distance between two shapes. If the distance is small, the shapes are close in appearance and if the distance is large, the shapes are farther apart in appearance.

OpenCV provides an easy to use a utility function called matchShapes that takes in two images ( or contours ) and finds the distance between them using Hu Moments. So, you do not have to explicitly calculate the Hu Moments. Simply binarize the images and use matchShapes.

The usage is shown below.

Python

d1 = cv2.matchShapes(im1,im2,cv2.CONTOURS_MATCH_I1,0) 
d2 = cv2.matchShapes(im1,im2,cv2.CONTOURS_MATCH_I2,0) 
d3 = cv2.matchShapes(im1,im2,cv2.CONTOURS_MATCH_I3,0)

C++

double d1 = matchShapes(im1, im2, CONTOURS_MATCH_I1, 0); 
double d2 = matchShapes(im1, im2, CONTOURS_MATCH_I2, 0); 
double d3 = matchShapes(im1, im2, CONTOURS_MATCH_I3, 0);

Note that there are three kinds of distances that you can use via a third parameter ( CONTOURS_MATCH_I1, CONTOURS_MATCH_I2 or CONTOURS_MATCH_I3).

Two images (im1 and im2) are similar if the above distances are small. You can use any distance measure. They usually produce similar results. I personally prefer d2.

Let’s see how these three distances are defined.

Let $D(A, B)$ be the distance between shapes A and B, and $H^A_i$ and $H^B_i$ be the $i^{th}$ log transformed Hu Moments for shapes $A$ and $B$ . The distances corresponding to the three cases is defined as

CONTOURS_MATCH_I1
(8) $\begin{align*}D(A, B) = \sum^{6}_{i=0} \left | \frac{1}{H^B_i} - \frac{1}{H^A_i} \right |\end{align*}$
CONTOURS_MATCH_I2
(9) $\begin{align*}D(A, B) = \sum^{6}_{i=0} \left | H^B_i - H^A_i \right |\end{align*}$
CONTOURS_MATCH_I3
(10) $\begin{align*}D(A, B) = \sum^{6}_{i=0} \frac{\left | H^A_i - H^B_i \right |}{\left | H^A_i \right |}\end{align*}$
When we use the shape matching on the images : S0, K0 and S4 ( transformed and flipped version of S0 ), we get the following output : Shape Distances Between ————————-
S0.png and S0.png : 0.0
S0.png and K0.png : 0.10783054664091285
S0.png and S4.png : 0.008484870268973932 5.2 Custom distance measure In case you want to define you own custom distance measure between two shapes, you can easily do so. For example, you may want to use the Euclidean distance between the Hu Moments given by
(11) $\begin{align*}D(A, B) = \sqrt { \sum^{6}_{i=0} \left ( H^B_i - H^A_i \right )^2 }\end{align*}$
First, you calculate log transformed Hu Moments as mentioned in the previous section, and then calculate the distance yourself instead of using matchShapes. Acknowledgements : Code for this post was jointly written by Krutika Bapat and Vishwesh Shrimali

Comments

Mike Pelton says

December 11, 2018 at 5:08 am

Hi Satya – another fascinating piece – please keep them coming!

- Satya Mallick says
  
  December 11, 2018 at 9:14 am
  
  Thanks, Mike.
  
sumedha_1483959540 says

December 11, 2018 at 10:42 am

Simply Awesome and accurate!

- Satya Mallick says
  
  December 11, 2018 at 11:45 am
  
  Thanks, Sumedha.
  
penkesiva says

December 11, 2018 at 12:07 pm

Thanks again for ‘full of meat’ articles like these 🙂
[On a small note, found a compilation error while compiling HuMoments.cpp, got to rename file to huMoments.cpp]

- vishwesh shrimali says
  
  December 11, 2018 at 5:57 pm
  
  Hi!
  Thanks for pointing out the mistake. We will fix it very soon.
  
wbeaver says

December 11, 2018 at 12:30 pm

Hi Satya. Good stuff, per usual. Thank you. Btw, looks like typos in superscripts of Eqs (8), (9), and (11) Best.

- vishwesh shrimali says
  
  December 11, 2018 at 5:59 pm
  
  Thanks for pointing out the mistakes! I will fix them 🙂
  
Stephen Meschke says

December 11, 2018 at 12:33 pm

I wonder if I can use HuMoments to classify circle, square, triangle, and star? Good thing I have 16,000 shapes to practice on: https://www.kaggle.com/smeschke/four-shapes.

- Satya Mallick says
  
  December 11, 2018 at 11:12 pm
  
  Can you please attach the shape files here so I can look at them?
  
  - Stephen Meschke says
    
    December 12, 2018 at 10:22 am
    
    Here are 20 (of 16,000) images: https://imgur.com/a/Cjro3d3
    The entire dataset is available here: https://www.kaggle.com/smeschke/four-shapes.
    
    The image below shows the results that Vishwesh Shrimali explained in a previous comment. Each row shows two shapes and cv2.matchShapes(). The star and the circle have the greatest distance, which means that star/circle match very poorly. Star/square matches better than the star/circle, but not as well as star/star or star/triangle. Star/triangle actually matches slightly better than star/star, but this is understandable and forgivable because star and triangle look similar in that they both have pointy bits. https://uploads.disquscdn.com/images/4f7d12afbb2b2531dbb656423bdd70a067f8c476a476b61d382ebb5c57485c63.png
    
- vishwesh shrimali says
  
  December 12, 2018 at 6:48 am
  
  Hi Stephen! I went through your code. The results are correct and let me quickly explain them to you.
  You are using the following piece of code to match the shapes:
  
  m1 = cv2.matchShapes(img_a, img_b,cv2.CONTOURS_MATCH_I2,0)
  
  Now what this means is that you are using equation (9) for shape matching. Thus, lower the value, lower will be the “distance”, and thus the better will be the match.
  
  - Stephen Meschke says
    
    December 12, 2018 at 10:51 am
    
    Thank you for the good explanation. Now the results make sense, and cv2.matchShapes() correctly matches the shapes most of the time.
    
    - vishwesh shrimali says
      
      December 12, 2018 at 10:52 am
      
      Glad to be of help and happy to know that you enjoyed the post 😀
      
      - Stephen Meschke says
        
        December 12, 2018 at 12:15 pm
        
        I did enjoy this post very much, but I am left with one burning question: Why bother? Using the Four Shapes Dataset, I have trained a Keras model that is .999 accurate. Making classifications (1.0 milliseconds) does take longer than cv2.matchShapes (0.15 milliseconds), but the NN is far more accurate at classification than Hu Moments. Are Hu Moments just some 1960’s era mathematics that were made obsolete by neural nets? How can Hu Moments be utilized in today’s computer vision?
XMC.pl says

June 7, 2022 at 9:49 am

Bardzo chciałbym założyć bloga, ale… Nie jestem pewien, jaki rodzaj blogów ma największy ruch? Jakie blogi przeglądasz? Najczęściej przeglądam blogi fotograficzne, kulinarne i blogi modowe. i Właśnie twego bloga dopiero zaczynam “obserwować” ps. Dobrze, że jest aktywne RSS.

LearnOpenCV

Shape Matching using Hu Moments (C++/Python)

1. What are Image Moments?

Master Generative AI for CV

2. How are image moments calculated?

Centroid using Image Moments

2.1 Central Moments

3. What are Hu Moments?

4. How to calculate Hu Moments in OpenCV?

Read in image as Grayscale

Python

C++

Python

C++

Calculate Hu Moments

Python

C++

Log Transform

Python

C++

5. Shape Matching using Hu Moments

5.1 Distance between two shapes using matchShapes

Python

C++

Get Started with OpenCV

Subscribe to receive the download link, receive updates, and be notified of bug fixes

Which email should I send you the download link?

LearnOpenCV

1. What are Image Moments?

Master Generative AI for CV

2. How are image moments calculated?

Centroid using Image Moments

2.1 Central Moments

3. What are Hu Moments?

4. How to calculate Hu Moments in OpenCV?

Read in image as Grayscale

Python

C++

Python

C++

Calculate Hu Moments

Python

C++

Log Transform

Python

C++

5. Shape Matching using Hu Moments

5.1 Distance between two shapes using matchShapes

Python

C++

Subscribe & Download Code

Comments

Leave a Reply Cancel reply

Get Started with OpenCV

Subscribe to receive the download link, receive updates, and be notified of bug fixes

Which email should I send you the download link?