Introduction
Have you ever wondered how we can compare images according to their content? That is, given an image, how to find images similar to it. You may have seen this functionality implemented by Google. Just visit https://images.google.com/, enter an input image (either by uploading it or by linking to it) and click "Search by image":
Google searches the web and displays a list of similar images. In fact, this search for similar images is a subject of scientific research since early 2000s. It is called Content Based Image Retrieval or shortly CBIR. If you search for CBIR on the Internet, you will find numerous papers for it.
Next question is: "How do i compare images?". The majority of scientific papers propose methods of comparing images. And "what are the main requirements for such a method?":
Google searches the web and displays a list of similar images. In fact, this search for similar images is a subject of scientific research since early 2000s. It is called Content Based Image Retrieval or shortly CBIR. If you search for CBIR on the Internet, you will find numerous papers for it.
So, how do we compare images?
You may ask yourself: "Why do i need such a system?. If i want to search for an image, i use the keyword search". Yes, but there are occasions where search by keyword is meaningless. One such occasion is crime investigation. In this case, I have an image (fingerprint) and I want to match it against other images (fingerprints) from a large database. There are also other fields where this "pattern matching" is essential.Next question is: "How do i compare images?". The majority of scientific papers propose methods of comparing images. And "what are the main requirements for such a method?":
- Accuracy
- Speed
I want my method (or algorithm) to be both accurate and fast, and this is not always easy. Basically, all methods try to extract a short description of an image. Let's say that we have a car picture. The ideal method should recognize the car object and describe the picture with the word "car". Unfortunately, there are not many accurate and quick methods for describing a picture. And even if there are for simple pictures (like the picture of a car), they fail for more complex pictures. So, keep in mind that when we design such a method, we usually need to know the specific application. In the example of fingerprints, color information will be disregarded as we have to deal with gray-scale images.
The simplest case - Color histogram
This article is only an introduction to the subject of content-based image retrieval. I will only refer to the simplest method of describing a color image: color histogram. Consider a digital image as a series of pixels. An 800 x 600 image contains 480000 pixels. Each pixel is 24 bits (or 3 bytes), one byte for each of the 3 basic colors: Red, Green, Blue or RGB. So, put it simply each pixel is represented as a mixture of red, green and blue color intensities. Color histogram is a way of describing the color content of a picture. For example, consider the following picture:
Here we have 4 x 4 = 16 pixels and only 3 colors (red, green, yellow). 8 pixels are yellow, 4 pixels are red and 4 pixels are green. The color histogram depicts the color frequency of an image. In this case, 50% of pixels are yellow, 25% are red and 25% are green:
The reality is a little more complex but that's the idea.
C# - Comparing images using color histogram
I developed a simple C# application to demonstrate the use of color histogram in content-based image retrieval. Here is the graphical user interface:
Remember what we need for such an application:
- An input image: In this case the input image is a red bus.
- A database to search for similar images: In this case we use the image collection of Wang http://wang.ist.psu.edu/docs/related/. It contains 1000 test images of different categories (buses, animals, sea, sky, people, food etc).
Implementation
The C# implementation was of interest to me because it freshened or improved my WPF, Threading skills. This is the code for calculating the color histogram of an image:
The interesting point here is that the image is reduced to 512 colors, a process known as color quantization. This is important for large image collections, where the image descriptor's size should be small enough to speed-up the comparison process. A descriptor with size 512 (like this color histogram) is considered prohibitive for large collections. So, a descriptor should be smart in order to capture the image information in a small signature (perhaps 10 or 20 numbers totally).
The distance between 2 color histograms is calculated by the Manhattan formula (in essence it is a single difference):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | private double[] Histogram1(Bitmap sourceImage) { double[] RGBColor = new double[512]; int width = sourceImage.Width, height = sourceImage.Height; byte Red, Green, Blue; Color pixelColor; for (int i = 0, j; i < width; ++i) { for (j = 0; j < height; ++j) { pixelColor = sourceImage.GetPixel(i, j); Red = pixelColor.R; Green = pixelColor.G; Blue = pixelColor.B; int quantColor = ((Red / 32) * 64) + ((Green / 32) * 8) + (Blue / 32); ++RGBColor[quantColor]; } } double normalizationFactor = width * height; for (int i = 0; i < RGBColor.Length; i++) { RGBColor[i] = RGBColor[i] / normalizationFactor; } return RGBColor; } |
The interesting point here is that the image is reduced to 512 colors, a process known as color quantization. This is important for large image collections, where the image descriptor's size should be small enough to speed-up the comparison process. A descriptor with size 512 (like this color histogram) is considered prohibitive for large collections. So, a descriptor should be smart in order to capture the image information in a small signature (perhaps 10 or 20 numbers totally).
The distance between 2 color histograms is calculated by the Manhattan formula (in essence it is a single difference):
1 2 3 4 | for (int i = 0; i < histogram1.Length; i++) { distance += Math.Abs(histogram1[i] - histogram2[i]); } |
Conclusion
Personally, i find the subject of content-based image retrieval very interesting. It is a fertile ground for research. In this article, I showed the simplest application of image retrieval.
