Histogram Backprojection

1 Reply

In this blog, we will discuss Histogram Backprojection, a technique that is used for image segmentation or finding objects of interest in an image. It was proposed by Michael J. Swain, Dana H. Ballard in their paper Indexing via color histograms, Third international conference on computer vision,1990.

This was one of the first works that use color to address the classic problem of Classification and Localisation in computer vision.

To understand this technique, knowledge of histograms (particularly 2-D histograms) is a must. If you haven’t encountered 2-d histograms yet, I suggest you to read What is a 2-D histogram?

Now, let’s see what is Histogram backprojection and how do we do it?

According to the authors, Histogram Backprojection answers the question

“Where are the colors in the image that belong to the object being looked for (the target)?”

So, this addresses the localization problem i.e. where is the object in an image. In this, we calculate the histogram model of a feature and then use it to find this feature in an image. To know why this is named as Histogram Backprojection, you need to know how this method works. So, let’s see how to do this

Suppose we want to find the green color in the target image. Let ‘roi’ be the image of the object we need to find and ‘target’ be the image where we are going to search that object.

Steps:

  • First, load the images, convert them into HSV and find the histograms as shown below

The 2-D histograms looks like this

This was expected, as roi image has shades of green so its histogram is mostly concentrated to the H and S values representing green. Similarly we can argue for the target image.

Now, what we want is to make ‘I’ look as similar to ‘M‘ as possible. Only then we will be able to extract the green color from the target image. So, let’s see how to do this.

One plausible solution is to divide “M” by “I”. This way the output will have values greater than 0, where both “M” and “I” are greater than 0. For all other cases, it will be either ‘0’ or ‘Nan’.

The output ‘R’ is shown below where cyan represents values greater than 0 (probably our roi), purple represents 0 and white represents Nan.

R, 2-D Histogram

Now the last thing to do is, find the pixels in the target image that corresponds to the cyan region shown above. In other words, we back project the 2-D histogram.

Because we know the “H” and “S” values for the cyan region (See R image above), we can easily find out the pixels with similar “H” and “S” values in the target image. Let’s see how to do this.

First, we will extract “H” and “S” channels from the target image.

For each pixel in the target image, using the “H” and “S” value for that pixel we will find the corresponding value in the 2-D histogram and save that value in ‘B’.

Note: “B” doesn’t contain “Nan” values. Remember, “Nan” occurs when both “M” and “I” equals to 0.

We keep the values between 0 and 1 so that the value can be treated as the probability of each pixel belonging to the target. After that, we resize “B”.

So, now we have created a new image “B” (size same as that of the target image) where every pixel value represents the corresponding probability of being the target. Brighter pixels are more probable of being the target. “B” is shown below

  • Now, the next step is just for fine-tuning this output. This varies from image to image.
  • Use thresholding to segment out the region and Overlay images using bitwise_and to produce the desired output.

The output looks like this

See how from a 2-D histogram we are able to extract the roi from the target image.

Backprojection in OpenCV

OpenCV provides an inbuilt function

cv2.calcBackProject( target_img, channels, roi_hist, ranges, scale )

  • target_img: image where you want to find the feature.
  • channels: The list of channels used to compute the back projection.
  • roi_hist: histogram of the feature you want to find.
  • ranges: histogram bin boundaries in each dimension.
  • scale: Optional scale factor for the output back projection.

This returns the probability image “B”.

So, we only need to calculate the roi histogram (M) and normalize it. No need of calculating “I” and “R”. This function directly output “B”.

After that apply all the fine-tuning steps that we did earlier.

That’s all about Histogram Backprojection. 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

Share
Tweet
Pin
0 Shares

1 thought on “Histogram Backprojection”

  1. Aastha Gupta

    I am using the same image as in the example and the exact same code but I am not getting the required output.
    Can anyone help?

    import cv2
    import numpy as np
    import matplotlib.pylab as plt

    #HISTOGRAM BACKPROJECTION

    roi = cv2.imread(‘…./roi backprojection.jpg’)
    roi_show = cv2.cvtColor(roi,cv2.COLOR_BGR2RGB)
    hsv = cv2.cvtColor(roi,cv2.COLOR_BGR2HSV)

    target = cv2.imread(‘…/target backprojection.jpg’)
    target_show = cv2.cvtColor(target,cv2.COLOR_BGR2RGB)
    hsvt = cv2.cvtColor(target,cv2.COLOR_BGR2HSV)

    plt.subplot(121)
    plt.imshow(roi_show)
    plt.subplot(122)
    plt.imshow(target_show)
    plt.show()

    hist_roi = cv2.calcHist(hsv,[0,1],None,[180,256],[0,180,0,256])
    hist_target = cv2.calcHist(hsvt,[0,1],None,[180,256],[0,180,0,256])

    plt.subplot(121)
    plt.imshow(hist_roi)
    plt.subplot(122)
    plt.imshow(hist_target)
    plt.show()

    R = hist_roi/hist_target
    plt.imshow(R)
    plt.show()

    h,s,v = cv2.split(hsvt)
    B = R[h.ravel(),s.ravel()]
    B = np.minimum(B,1)
    B = B.reshape(hsvt.shape[:2])

    cv2.namedWindow(‘B’,cv2.WINDOW_NORMAL)
    cv2.imshow(‘B’,B)
    cv2.waitKey()
    cv2.destroyAllWindows()

    This is the code I am using.

    Reply ↓

Leave a Reply