CV: Searching Similar Images

[TOC]

Checking if files are identical is an exceedingly-trivial task – it is possible to directly compare all their bytes or perhaps compute a hash of each file and compare those values -but trying to compare the similarity of files’ content is entirely more difficult.se, greatly reducing the space needed for evaluation.

How can a computer determine whether two photos contain the same content after getting resized or compressed several times?

Due to the lossy nature of most image compression algorithms, it is impossible to compare the bytes of images to determine whether they have the same content.

Every time a JPEG image is decoded and encoded, additional data is changed or lost. While formats like PNG are lossless, resizing images will also change their content, preventing direct comparisons.

There are a variety of image hashing algorithms, some of the most popular algorithms being:

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

Cryptographic hashing algorithms like the MD5 or SHA256 are designed to generate an unpredictable result. In order to do this, they are optimized to change as much as possible for similar inputs. Perceptual Hashes are the opposite —they are optimized to change as little as possible for similar inputs. pHash algorithm computes hashing on top of Discrete Cosine Transform (DCT) that transforms data from spatial domain to frequency domain.

As previously noted, this family of algorithms are designed to not change much when an image undergoes minor modifications such as compression, color correction and brightness. pHashes allows the comparison of two images by looking at the number of different bits between the input and the image it is being compared against. This difference is known as the Hamming distance.

A very simple way of using this algorithm would be to create a list of all known images and their perceptual hash. A hamming distance can be calculated with just a xor and popcnt instruction on modern CPUs. This approach would be fairly fast to start with. With tens of thousands of images, it could be possible to get results in a few seconds, which is likely acceptable performance.

When the amount of images starts growing to the millions, sequentially scanning and comparing against every image takes far too long. Because the hash has to be computed against the input each time, a conventional index would not be usable.

Thankfully, a BK-tree -a tree specifically designed for metric spaces like Hamming distance- can be used here instead of having to search against every image in the database, greatly reducing the space needed for evaluation.

timeline
    title pHash Process
    1 : Source
    2 : Greyscale
    3 : 32×32 factor
    4 : DCT per row
    5 : DCT per col
    6 : Top left 8×8
    7 : Median
    8 : Hash

Step	Name	Image
1	Source
2	Convert to greyscale
3	32×32 factor
4	DCT per row
5	DCT per col
6	Upper left 8×8 factor
7	Median
8	Hash	1010010010101101100110011011001101100010100100000111011010101110

Intellectual property rights protection and management of multimedia data is essential for the deployment of e-commerce systems involving transactions on such data.

Early detection of resources under copyright avoids complex and expensive legal issues.

pHash gives a metric about the similarity between two sources, which prevents duplication in the main dataset.

Optimizing the main dataset is not only an improvement in terms of curated contents, but also in terms of costs of infrastructure.

E-commerce is a growing industry that has become a notable part of many consumers’ habits; therefore, many sites are trying to bring new features to the filtering and comparison tools to improve the user experience. One such feature is allowing customers to find products by a photo in order to suggest the exact match in case of success or the most similar products in other cases. This is called a reverse image search engine.

Each nucleotide is encoded as a fixed gray level intensity pixel whose hash is calculated from its significant frequency characteristics. This results in a drastic data reduction between the sequence and the perceptual hash, allowing scientists and geneticists to perform massive searches and compare millions of combinations with low infrastructure impact.

Web Design for Coding: 7 steps checklist to have it ready for development

In the field of agriculture, there are many destructive diseases, for example leaf diseases that are the most frequent diseases where spots occur on the leaves. If these spots are not detected on time, they can cause severe losses. To detect leaf disease, image processing techniques are employed, many of them based on pHashes.

This overview is based on ImageHash, a well documented and tested PHP package to hash images.

<?php

[...]

use Jenssegers\ImageHash\ImageHash;
use Jenssegers\ImageHash\Implementations\DifferenceHash;

$hasher = new ImageHash(new DifferenceHash());

$hash1 = $hasher->hash('path/to/image1.jpg');
$hash2 = $hasher->hash('path/to/image2.jpg');

$distance = $hasher->distance($hash1, $hash2);

Image #1	Image #2

Image #1	Image #2

This use case is based on Nike.es, the Spanish branch of Nike.com.

Comparing the native application and the website we can see two different UX when looking for sneakers:

When using the native application you can find sneakers by navigating their catalog or just taking a photo of the desired one. If there is a coincidence, the application redirects the user to the matching product detail view but, in any other case, the catalog is sorted out to show the sneakers sorted by similarity.

But when visiting the web application this feature is missing. There is no any way to filter out sneakers by similarity.

This repository shows how to implement a this feature applying a reverse image search engine.

Remarked in purple you will find some new elements:

• Closed to the main search input field there is a camera icon from where the customer could upload some pictures (or capture some snapshots using the camera) to filter out the catalog. (To simplify the process some predefined photos are provided to filter out the catalog.)

• Once the photo is clicked the entire catalog is automatically sorted out by similarity.

A Makefile is provided with some predefined commands to improve the Development Experience.

╔════════════════════════════════════════════════════════════════════════════════════════════════╗
║                                                                                                ║
║                                    .: AVAILABLE COMMANDS :.                                    ║
║                                                                                                ║
╚════════════════════════════════════════════════════════════════════════════════════════════════╝
· DOMAIN(s) .... https://localhost
· SERVICE(s) ... caddy app1
· USER ......... (1000) alcidesramos
· GROUP ........ (1000) alcidesramos

· build                               Docker: builds the service <env=[dev|prod]>
· up                                  Docker: starts the service <env=[dev|prod]>
· restart                             Docker: restarts the service <env=[dev|prod]>
· down                                Docker: stops the service <env=[dev|prod]>
· logs                                Docker: exposes the service logs <env=[dev|prod]> <service=[app1|caddy]>
· shell                               Docker: establish a shell session into main container
· inspect                             Docker: inspect the health for specific service <service=[app1|caddy]>
· install-caddy-certificate           Setup: extracts the Caddy Local Authority certificate
· composer-dump                       Composer: runs <composer dump-auto>
· composer-install                    Composer: runs <composer install>
· composer-remove                     Composer: runs <composer remove>
· composer-require-dev                Composer: runs <composer require --dev>
· composer-require                    Composer: runs <composer require>
· composer-update                     Composer: runs <composer update>
· check-syntax                        Application: runs PHP linter
· check-style                         Application: runs PHP Code Sniffer
· fix-style                           Application: runs PHP Code Beautifier and Fixer
· phpstan                             Application: runs PHPStan
· phpmd                               Application: runs PHP Mess Detector
· tests                               Application: runs PHPUnit testsuite
· open-website                        Application: open the application website
· init                                Application: initializes the application

Application Service is based only on a Docker container based on php:8.3.12-fpm-alpine and some useful extensions used during the development process such as PCOV,xDebug, etc.

$ make init

Updated At: 2024-11-14