Perceptual hashing and grouping

Why not just SHA-256

A WhatsApp export re-encodes the image: different size, different JPEG tables, no EXIF. Its SHA-256 shares nothing with the original. Perceptual hashes map "looks the same" to "bits are close", so duplicates can be found by Hamming distance.

photosift uses SHA-256 for exact duplicates and three 64-bit perceptual hashes for near duplicates. Only pHash drives grouping; aHash and dHash are stored for inspection and future use.

Pipeline

  1. Open the image and apply EXIF orientation (ImageOps.exif_transpose). A phone photo stored sideways with Orientation=6 must hash like its upright export.
  2. Convert to RGB, then to 8-bit grayscale.
  3. Downscale with Lanczos to a tiny grid. Everything the hash sees is therefore low-frequency content, which survives resizing and JPEG compression.

aHash (average hash)

Resize to 8x8, set bit = pixel > mean. Fast, but sensitive to global brightness changes.

dHash (difference hash)

Resize to 9x8, set bit = pixel is brighter than its left neighbour. Captures gradients, robust to brightness and contrast shifts.

pHash (DCT hash)

  1. Resize to 32x32 grayscale.
  2. Apply a 2-D DCT-II, built as D @ X @ D.T with an orthonormal 32x32 matrix.
  3. Keep the top-left 8x8 block: the 64 lowest spatial frequencies.
  4. Set bit = coefficient > median of the 63 AC coefficients (the DC term is just average brightness and would skew the median).

Higher frequencies (noise, compression artifacts, fine detail) are discarded. This is why a quality-40 re-encode usually differs from the original by 0-4 bits while unrelated images differ by about 32.

Worked example from the sample library: an original 1200x900 photo and its 800x600 q=60 WhatsApp copy have pHash distance 0 (one pair shows 2). A 1% crop plus 12% brightness boost lands between 0 and 8 bits across the 12 edited samples. Unrelated images are at 20+ bits, so the default threshold of 8 separates them cleanly. A 2% crop on a very smooth synthetic image already reached 10-12 bits, which is the point at which you raise --threshold.

BK-tree

Comparing every pair is O(n^2). A BK-tree indexes items by distance to their parent: each child edge is labelled with the Hamming distance from the node. To find everything within radius r of a query q, compute d = dist(q, node) and only descend into children whose edge label lies in [d - r, d + r], which the triangle inequality guarantees is sufficient. Identical hashes share a node. The tests compare results with brute force for several radii.

Union-find grouping

For every image, all neighbours within the threshold are unioned. Files with equal SHA-256 are also unioned (this is what groups videos). Each connected component with more than one file is a group, labelled exact if all members share one SHA-256 and near otherwise.

Caveat: grouping is transitive. If A is 6 bits from B and B is 6 bits from C, all three join even if A and C are 12 apart. That is usually what you want for a chain of progressively re-compressed copies, and the report shows each member's distance to the keeper so odd cases are visible.

Keeper policy

Members are sorted by this key and the first wins:

  1. Highest pixel count (after orientation).
  2. Has EXIF over stripped.
  3. Larger file at equal resolution.
  4. Earlier match in the --prefer list (default DCIM, Camera).
  5. Path, alphabetically, for determinism.

The loser's reason is the first criterion at which it differs from the keeper, e.g. lower resolution (800x600 vs 1200x900).

Bursts

A burst is a run of frames from the same camera and resolution, each less than 2 seconds after the previous one, with at least two distinct timestamps. Burst frames look nearly identical, so they would otherwise be merged as duplicates and all but one discarded.

Two frames are treated as burst mates (and so not unioned by pHash) only when the gap is strictly greater than 0 and under 2 seconds and the bytes differ. Gap 0 is excluded because a derived copy of a photo carries the same capture time. The same-resolution requirement stops a resized re-export, whose sub-second field was dropped, from looking like a second frame. Sub-second EXIF (SubSecTimeOriginal) is used when present. --include-bursts disables the exemption.

Example from the sample library: burst_0.jpg, burst_1.jpg and burst_2.jpg are 0.6 s apart with pHash distance 2 or less. By default they stay separate and appear in the report's burst section; with --include-bursts they form one group.

Date resolution

Priority: EXIF DateTimeOriginal (or MP4 mvhd) over a date parsed from the filename over file mtime. The cache keeps all three candidates, so stats can flag files where EXIF and filename disagree by more than a day, dates before 1990 (including 1970 and 1904 zeroed clocks), and dates in the future.

Filename patterns are tried most specific first: WhatsApp IMG-YYYYMMDD-WA####, YYYY-MM-DD<sep>HH-MM-SS, YYYYMMDD_HHMMSS, then date-only forms. Impossible dates (month 13) and years outside 1990-2100 are rejected, so IMG_20231399_101500.jpg is not mis-dated. Date-only names are placed at noon.