Image Search Engine using Image Hashing technique in Python

`From Unsplash

Image searching is a type of information retrieval method in which similar images are retrieved based on the query which is also an image. Image searching is widely used in Forensics, Surveillance, etc.

Every modern browser provides an image searching feature to retrieve websites that have similar images asked in the query. These search engines are powered by heavy deep learning models processing and indexing billions of images daily. These search engines first index the images by extracting features from a deep learning model, and to retrieve the images, they calculate features for the query image and show similar images sorted based on the similarity rate. Also, some engines use a hybrid approach to search the images by indexing images based on both metadata and image content.

Before the popularity of deep learning, some search engines were using hashing techniques to index the images. In this tutorial, we discuss how to implement this image searching using the image hashing technique.

To build a search engine, we must implement the following steps

1. Setup an image database.
2. Index images using hashing.
3. Fetch similar images by comparing hash values of a query image and images in the database. Similar images are fetched based on the similarity score of hashes.

1. Setup Image database

The image database contains images of the top 5 tallest buildings of world images. For each building (Burj Khalifa, Shanghai Tower, Abraj Al-Bait Clock Tower, Ping An Finance Center, and Lotte World Tower), the image database contains 5 different images of that building and a total of 25 images in the database.

2. Image indexing

To index images, we use image hash values and store them in the database to compare images.

Image Hashing

Image hashing is the process of giving a unique hash code to an image.

As we can encode an image to a unique code, this code can be used to index the images. So we retrieve similar images by comparing hash codes and their similarity.

There are a variety of image hashing algorithms to hashing of images and most of the algorithms are simple and fast. Some of the popular algorithms are

• Average Hashing (aHash)
• Median Hashing (mHash)
• Perceptual Hashing (pHash)
• Difference Hashing (dHash)
• Block Hashing (bHash)
• Wavelet Hashing (wHash)
• ColorMoment Hashing

If you are not familiar with the image hashing concept, learn about image hashing in this famous blog.

For now, we hash images using Perceptual Hashing (pHash) algorithm which computes hashing on top of Discrete Cosine Transform (DCT) that transforms data from spatial domain to frequency domain.

pHash (Perceptual Hashing)

pHash is a simple algorithm that calculates image hash based on the DCT values of the image. The algorithm involves the following steps

• Re-scale image — Re-scale the image to multiples of 4 like 8*8, 32*32, etc.
• Convert to Gray-scale image.
• Calculate DCT block for 8*8 or 32*32 image.
• Compute average DCT value excluding the value at (0, 0) as it influences larger deviation in computing average.
• Compute binary DCT block by setting entries either 0 or 1 by comparing average value (if value > average then 1 else 0).
• Construct hash by traversing the binary DCT block from left to right and top to bottom. As values are only 0 or 1, the hash can be stored in a 64-bit integer for 8*8 DCT block.

For every image, we calculate the image hash from the above pHash algorithm and store these hashes as indices for images.

In the above snippet, image_names contains all image paths in the images directory, and for every image, we calculate the hash value and store it in image_hash_dict for future use.

Image names
images/abraj-al-bait-1.jpg
images/abraj-al-bait-2.jpg
images/abraj-al-bait-3.jpg
images/abraj-al-bait-4.jpg
images/abraj-al-bait-5.jpg
images/burj-khalifa-1.jpg
images/burj-khalifa-2.jpg
images/burj-khalifa-3.jpg
images/burj-khalifa-4.jpg
images/burj-khalifa-5.jpg
images/lotte-1.jpg
images/lotte-2.jpg
images/lotte-3.jpg
images/lotte-4.jpg
images/lotte-5.jpg
images/ping-an-1.jpg
images/ping-an-2.jpg
images/ping-an-3.jpg
images/ping-an-4.jpg
images/ping-an-5.jpg
images/shanghai-tower-1.jpg
images/shanghai-tower-2.jpg
images/shanghai-tower-3.jpg
images/shanghai-tower-4.jpg
images/shanghai-tower-5.jpg

hash_array_to_hash_hex() converts 1D binary array to hex string value and hash_hex_to_hash_array() hex string value to 1D binary array of data type float.

String hash values occupy less space and are flexible to store in a text or csv file. These values could be used for indexing images in the database.

Hash value for “images/shanghai-tower-1.jpg” is 0xb1934cf40a79140b

There are python libraries for calculating image hashes like ImageHash and Perception which provide different hash methods and other tools to implement image hashing.

3. Fetching similar images

Now for a query image, similar images are fetched as

• Calculate the image hash value for the query image.
• As we already stored hash values for images in the database, compare their hash values with the hash value of the query image. Metric functions like Hamming distance can be used to compare hashes.
• Now sort the images based on metric score.
• Show images having the metric score above the threshold.

As we already have image hash calculated, we can retrieve similar images by comparing hash values against query image hash value.

If the query image is “images/burj-khalifa-3.jpg”, to get similar images, calculate the hamming distance for all image hashes against query hash like

This gives distance scores for images as below

images/abraj-al-bait-1.jpg     0.46875
images/abraj-al-bait-2.jpg     0.609375
images/abraj-al-bait-3.jpg     0.640625
images/abraj-al-bait-4.jpg     0.578125
images/abraj-al-bait-5.jpg     0.5
images/burj-khalifa-1.jpg      0.53125
images/burj-khalifa-2.jpg      0.453125
images/burj-khalifa-3.jpg      0.0
images/burj-khalifa-4.jpg      0.390625
images/burj-khalifa-5.jpg      0.4375
images/lotte-1.jpg             0.453125
images/lotte-2.jpg             0.53125
images/lotte-3.jpg             0.625
images/lotte-4.jpg             0.4375
images/lotte-5.jpg             0.375
images/ping-an-1.jpg           0.453125
images/ping-an-2.jpg           0.609375
images/ping-an-3.jpg           0.484375
images/ping-an-4.jpg           0.484375
images/ping-an-5.jpg           0.453125
images/shanghai-tower-1.jpg    0.4375
images/shanghai-tower-2.jpg    0.328125
images/shanghai-tower-3.jpg    0.515625
images/shanghai-tower-4.jpg    0.359375
images/shanghai-tower-5.jpg    0.453125

These scores indicate the similarity of an image to query image. Lower the score then more it is similar to the query image. Scores for the Burj Khalifa images are in range of 0.3–0.5 and some other images also lie in this range as buildings have a similar structure and it is difficult to differentiate structures.

Image hashing results could be not accurate than Deep Learning methods but they are very fast to implement and require less storage. Image hashing methods can be used for detecting strict duplicate images in large databases. With some pre-processing images and tweaking the pHash algorithm, we can achieve better results for retrieving similar images.