Finding duplicate images¶
A checksum finds only the files that are the same byte for byte. A picture saved again as JPEG, scaled down for the web or brightened a little is a different file with a different checksum, and to anyone who looks at it the same picture. A perceptual hash gives such copies hashes a few bits apart and unrelated pictures hashes about half the bits apart, so finding them takes four steps: choose an algorithm, hash every file, compare the hashes, and join the close ones into groups. This page goes through the four with one program that does them all, and links each step to the page that measures it.
flowchart LR
F[Image files] --> H["Hash every file<br/>pHash, on every CPU"]
H --> P["Compare every pair<br/>Hamming distance"]
P --> T{"Within the<br/>threshold?"}
T -->|yes| G[Join their groups]
T -->|no| X[Different pictures]
G --> R[Groups of copies]Which algorithm¶
For photographs whose copies are recompressed, scaled, or changed in brightness, contrast or gamma, pHash: of the nine algorithms it separates such copies from different photographs best, and it is among the cheapest four (Choosing an algorithm). Other copies call for another hash:
- Cropped copies: Radial, which a 5 % crop moves least of all.
- Copies turned a quarter or mirrored: no hash of the layout survives them; the two color hashes do not see the turn.
- A change of color that makes another picture, such as one product in two colors: ColorHash beside a layout hash, since a gray hash barely notices a turned hue.
- Flat shapes and patterns rather than photographs: BMH, which separates those best.
The program below uses pHash. aHash, dHash and wHash are one flag away, as they are 64-bit hashes compared the same way; a digest algorithm also needs its own comparison function (Which function for which hash).
Hashing the files¶
ph_hash_files() hashes every file on a pool of workers,
one per CPU when threads is 0, and stores each file's hash and status in its item. A
file that cannot be read or decoded fails alone, with its own status, and the others are
hashed as usual:
for (size_t i = 0; i < n; i++) {
items[i].path = argv[i + 2];
}
/* Every file hashed with pHash on all CPUs; a file that cannot be read fails alone. */
ph_error_t err = ph_hash_files(items, n, PH_HASH_PHASH, 0);
if (err != PH_SUCCESS) {
fprintf(stderr, "batch failed: %s\n", ph_get_error_string(err));
free(items);
free(parent);
free(members);
return 1;
}
Hashing many files has the options this call leaves at their defaults: a configuration for every file, progress, cancellation, the number of workers and the memory each of them holds.
Choosing the threshold¶
The threshold is the most bits two hashes of one picture may differ in. It is a property of the collection more than of the algorithm. Here is the threshold that accepts 95 % of the copies of each of the site's two corpora, 200 photographs and 24 synthetic images, each copy one moderate edit, and the share of pairs of different images that lets through as well:
| Algorithm | Synthetic images: threshold for 95% of copies | different images matched by mistake | Photographs: threshold for 95% of copies | different images matched by mistake |
|---|---|---|---|---|
| aHash | ≤ 8 of 64 bits (similarity ≥ 0.875) | 2.9% | ≤ 4 of 64 bits (similarity ≥ 0.938) | 9 of 19,900 |
| dHash | ≤ 15 of 64 bits (similarity ≥ 0.766) | 4.7% | ≤ 7 of 64 bits (similarity ≥ 0.891) | 4 of 19,900 |
| pHash | ≤ 17 of 64 bits (similarity ≥ 0.734) | 10.5% | ≤ 7 of 64 bits (similarity ≥ 0.891) | 0 of 19,900 |
| wHash | ≤ 16 of 64 bits (similarity ≥ 0.750) | 3.6% | ≤ 4 of 64 bits (similarity ≥ 0.938) | 4 of 19,900 |
| mHash | ≤ 255 of 576 bits (similarity ≥ 0.557) | 6.9% | ≤ 251 of 576 bits (similarity ≥ 0.564) | 0.7% |
| BMH | ≤ 43 of 256 bits (similarity ≥ 0.832) | 2.2% | ≤ 23 of 256 bits (similarity ≥ 0.910) | 0.2% |
| Radial | ≥ 0.751 | 14.7% | ≥ 0.956 | 4 of 19,900 |
| ColorHash | ≥ 0.615 | 6.2% | ≥ 0.775 | 1.0% |
| ColorMoments | ≤ 58.8 | 14.1% | ≤ 43.5 | 4.1% |
Each threshold accepts 95% of its corpus's copies. Beside it is how many pairs of different images fall within it as well, pairs it would wrongly call duplicates, out of every pair of different images in the corpus: 276 for the 24 synthetic images, 19,900 for the 200 photographs.
For pHash, the photographs' threshold lets no pair of different photographs through, while the synthetic images, checkerboards, stripes, rings and discs, need a much looser one and let many through. A collection's own threshold lies somewhere between, and the program helps find it: run it with a loose threshold over images whose duplicates are known, and read the pairs from the closest out. The distance at which the pairs stop being the same picture is where the threshold goes. Measuring a threshold on your own collection turns that into a share of copies accepted and a share of different pairs let through.
Pairs within the threshold¶
Every pair of files is compared once, with
ph_hamming_distance(), and a pair within the
threshold is kept; the pairs are printed closest first. A file that failed is left out of
every pair:
/* Every pair compared once: n * (n - 1) / 2 Hamming distances, a linear scan per file. */
size_t found = 0, room = 16;
pair_t *pairs = malloc(room * sizeof(*pairs));
for (size_t i = 0; i < n && pairs; i++) {
for (size_t j = i + 1; j < n; j++) {
if (items[i].status != PH_SUCCESS || items[j].status != PH_SUCCESS) {
continue;
}
int d = ph_hamming_distance(items[i].hashes[0], items[j].hashes[0]);
if (d > max_bits) {
continue;
}
if (found == room) {
pair_t *more = realloc(pairs, 2 * room * sizeof(*pairs));
if (!more) {
free(pairs);
pairs = NULL;
break;
}
pairs = more;
room *= 2;
}
pairs[found++] = (pair_t){d, i, j};
}
}
if (!pairs) {
free(items);
free(parent);
free(members);
return 1;
}
qsort(pairs, found, sizeof(*pairs), by_distance);
for (size_t k = 0; k < found; k++) {
printf("%2d bits %s %s\n", pairs[k].distance, items[pairs[k].a].path,
items[pairs[k].b].path);
}
printf("pairs within %ld bits: %zu\n", max_bits, found);
For \(n\) files that is \(n(n-1)/2\) comparisons, every one exact: no pair within the threshold is missed.
Groups of copies¶
A picture with three copies makes six pairs, and what a reader of the result wants is one line per picture: the files that are copies of each other. Each pair joins the groups of its two files, and the group of a file is found by following its parents to the group's first file, a union-find:
/* The group a file belongs to: the file its chain of parents ends at, the group's first. */
static size_t find(size_t *parent, size_t i) {
while (parent[i] != i) {
parent[i] = parent[parent[i]];
i = parent[i];
}
return i;
}
/* Each pair joins the groups of its two files, so a group holds every file a chain of
* pairs connects. Sorted by group, the files of each group sit together, the groups in the
* order of their first files. Two files of
* one group may be further apart than the threshold; its widest pair says how far. */
for (size_t i = 0; i < n; i++) {
parent[i] = i;
}
for (size_t k = 0; k < found; k++) {
size_t a = find(parent, pairs[k].a), b = find(parent, pairs[k].b);
parent[a > b ? a : b] = a < b ? a : b; /* a group is known by its first file */
}
for (size_t i = 0; i < n; i++) {
members[i] = (member_t){find(parent, i), i};
}
qsort(members, n, sizeof(*members), by_group);
size_t groups = 0;
for (size_t first = 0, last; first < n; first = last) {
for (last = first + 1; last < n && members[last].group == members[first].group;) {
last++;
}
if (last - first < 2) {
continue;
}
int widest = 0;
for (size_t i = first; i < last; i++) {
for (size_t j = i + 1; j < last; j++) {
int d = ph_hamming_distance(items[members[i].file].hashes[0],
items[members[j].file].hashes[0]);
widest = d > widest ? d : widest;
}
}
printf("group %zu: %zu files, widest pair %d bits\n", ++groups, last - first, widest);
for (size_t i = first; i < last; i++) {
printf(" %s\n", items[members[i].file].path);
}
}
printf("groups: %zu\n", groups);
A group holds every file that a chain of pairs connects, and a chain can reach further than the threshold: if A is within it of B and B of C, all three are one group, even when A and C are further apart. That joins a picture with copies of copies, each edited a little more, and it can join two different pictures through a file that sits between them. The program prints each group's widest pair for that reason: a group whose widest pair is well past the threshold is worth a look before a file of it is deleted. Which file of a group to keep, such as the largest or the oldest, is the program's choice; the hashes only say which files show the same picture.
The program¶
/* Finds the pictures that appear more than once among many files: hashes every file with
* pHash, prints each hash as it would be stored, then every pair within a threshold,
* closest first, and the groups those pairs join the files into. Build/run:
* cc find_duplicates.c -o find_duplicates $(pkg-config --cflags --libs libphash)
* ./find_duplicates 7 a.jpg b.jpg c.png ...
* The threshold is the most bits two hashes of one picture may differ in; measure it on
* your own images (docs/theory/comparing.md).
*/
#include <libphash.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int distance;
size_t a, b;
} pair_t;
static int by_distance(const void *x, const void *y) {
const pair_t *p = x, *q = y;
return p->distance - q->distance;
}
typedef struct {
size_t group, file;
} member_t;
static int by_group(const void *x, const void *y) {
const member_t *p = x, *q = y;
if (p->group != q->group) {
return p->group < q->group ? -1 : 1;
}
return p->file < q->file ? -1 : p->file > q->file;
}
/* The group a file belongs to: the file its chain of parents ends at, the group's first. */
static size_t find(size_t *parent, size_t i) {
while (parent[i] != i) {
parent[i] = parent[parent[i]];
i = parent[i];
}
return i;
}
int main(int argc, char **argv) {
if (argc < 3) {
fprintf(stderr, "usage: %s <max-bits> <image>...\n", argv[0]);
return 1;
}
char *end;
long max_bits = strtol(argv[1], &end, 10);
if (*end != '\0' || max_bits < 0 || max_bits > 64) {
fprintf(stderr, "max-bits must be a number from 0 to 64\n");
return 1;
}
size_t n = (size_t)(argc - 2);
ph_batch_item_t *items = calloc(n, sizeof(*items));
size_t *parent = malloc(n * sizeof(*parent));
member_t *members = malloc(n * sizeof(*members));
if (!items || !parent || !members) {
free(items);
free(parent);
free(members);
return 1;
}
for (size_t i = 0; i < n; i++) {
items[i].path = argv[i + 2];
}
/* Every file hashed with pHash on all CPUs; a file that cannot be read fails alone. */
ph_error_t err = ph_hash_files(items, n, PH_HASH_PHASH, 0);
if (err != PH_SUCCESS) {
fprintf(stderr, "batch failed: %s\n", ph_get_error_string(err));
free(items);
free(parent);
free(members);
return 1;
}
/* A stored hash carries what decides its value: the algorithm, the library version,
* and whether JPEG went through libjpeg-turbo or stb_image. The settings are the
* defaults here; a program that changes them stores them too. */
printf("# algorithm=%s version=%d native-jpeg=%d\n", ph_algorithm_name(PH_ALGO_PHASH),
ph_version_number(), ph_can_use_jpeg());
for (size_t i = 0; i < n; i++) {
char hex[17];
if (items[i].status != PH_SUCCESS) {
fprintf(stderr, "%s: %s\n", items[i].path, ph_get_error_string(items[i].status));
} else if (ph_hash_to_hex(items[i].hashes[0], hex, sizeof(hex)) == PH_SUCCESS) {
printf("%s %s\n", hex, items[i].path);
}
}
/* Every pair compared once: n * (n - 1) / 2 Hamming distances, a linear scan per file. */
size_t found = 0, room = 16;
pair_t *pairs = malloc(room * sizeof(*pairs));
for (size_t i = 0; i < n && pairs; i++) {
for (size_t j = i + 1; j < n; j++) {
if (items[i].status != PH_SUCCESS || items[j].status != PH_SUCCESS) {
continue;
}
int d = ph_hamming_distance(items[i].hashes[0], items[j].hashes[0]);
if (d > max_bits) {
continue;
}
if (found == room) {
pair_t *more = realloc(pairs, 2 * room * sizeof(*pairs));
if (!more) {
free(pairs);
pairs = NULL;
break;
}
pairs = more;
room *= 2;
}
pairs[found++] = (pair_t){d, i, j};
}
}
if (!pairs) {
free(items);
free(parent);
free(members);
return 1;
}
qsort(pairs, found, sizeof(*pairs), by_distance);
for (size_t k = 0; k < found; k++) {
printf("%2d bits %s %s\n", pairs[k].distance, items[pairs[k].a].path,
items[pairs[k].b].path);
}
printf("pairs within %ld bits: %zu\n", max_bits, found);
/* Each pair joins the groups of its two files, so a group holds every file a chain of
* pairs connects. Sorted by group, the files of each group sit together, the groups in the
* order of their first files. Two files of
* one group may be further apart than the threshold; its widest pair says how far. */
for (size_t i = 0; i < n; i++) {
parent[i] = i;
}
for (size_t k = 0; k < found; k++) {
size_t a = find(parent, pairs[k].a), b = find(parent, pairs[k].b);
parent[a > b ? a : b] = a < b ? a : b; /* a group is known by its first file */
}
for (size_t i = 0; i < n; i++) {
members[i] = (member_t){find(parent, i), i};
}
qsort(members, n, sizeof(*members), by_group);
size_t groups = 0;
for (size_t first = 0, last; first < n; first = last) {
for (last = first + 1; last < n && members[last].group == members[first].group;) {
last++;
}
if (last - first < 2) {
continue;
}
int widest = 0;
for (size_t i = first; i < last; i++) {
for (size_t j = i + 1; j < last; j++) {
int d = ph_hamming_distance(items[members[i].file].hashes[0],
items[members[j].file].hashes[0]);
widest = d > widest ? d : widest;
}
}
printf("group %zu: %zu files, widest pair %d bits\n", ++groups, last - first, widest);
for (size_t i = first; i < last; i++) {
printf(" %s\n", items[members[i].file].path);
}
}
printf("groups: %zu\n", groups);
free(pairs);
free(members);
free(parent);
free(items);
return 0;
}
cc find_duplicates.c -o find_duplicates $(pkg-config --cflags --libs libphash)
./find_duplicates 7 photos/*.jpg
The program prints every hash first, with the line that says what decided it: hashes stored for a later search need it beside them (Storing and searching hashes). Then come the pairs, closest first, and the groups.
Larger collections¶
Every pair of a collection grows with the square of its size: a hundred thousand files are five billion pairs. What a linear scan costs has the time of one comparison and what such a scan takes, measured. Past that size, two changes keep the search short:
- Compare each new file with the collection, not the collection with itself: \(n\) comparisons for one new file, and the stored hashes are compared once each.
- An index finds the stored hashes within the threshold of a query without comparing it with all of them, and finds exactly the ones the scan would. An index describes two, multi-index hashing and a BK-tree.
Files that are the same picture with nothing changed, the same hash to the bit, are found without comparing pairs at all: sorted by hash, they sit next to each other.
What it does not find¶
- Copies edited more than the corpora's copies. Each copy behind the thresholds is one moderate edit, a 2° rotation and a 5 % crop among them, and even at that strength the rotation and the crop are the copies a layout hash loses most often (What counts as a copy). How far each edit moves the hash as it grows is charted on each algorithm's page, for pHash under What changes the hash.
- Quarter turns and mirror images, as above: to a layout hash they are as far as an unrelated picture.
- Anyone trying not to be found. The hashes are deterministic and public, and a copy can be changed on purpose to land far from its original, or another picture to land near it. Finding duplicates in a collection you control is what they are for; What a perceptual hash is not has the reasons and the alternatives.
From Python, python-libphash calls the same library.