Verification methodology¶

What this project treats as correct and how it checks it, so that a disagreement about a hash value has somewhere to be resolved. Where each algorithm stands against its source, by the criteria on this page, is in algorithm-provenance.md.

The premise: what problem this library solves¶

Everything below follows from one premise: libphash is a deduplication library for a collection its operator controls. Finding copies and near-copies, clustering, cache keys. There is no adversary in its threat model.

This is not a disclaimer bolted on at the end. It determines what "correct" can mean here, and it resolves a question that otherwise looks like a gap in the library:

Why the well-founded algorithms in the literature do not fit. The rigorous, peer-reviewed work on image hashing is about authentication — a perceptual analogue of a message authentication code. Venkatesan et al. (2000) states the goal outright: "to make hash values on a set of distinct inputs pairwise independent […] even when inputs are generated by an adversary", and its hash is H(I, K) for a secret key K. Monga and Evans (2006) likewise quantizes probabilistically under a key. In both, the key and the randomization are load-bearing: Venkatesan calls randomized rounding "the crucial source of randomness (or entropy) in the hash function's output".

A keyed hash is the wrong tool for deduplication, and not by a little. Deduplication needs the same image to produce the same value on every machine that ever sees it, years apart, with no shared secret — which is exactly the property a perceptual MAC is designed to destroy. Taking such an algorithm and pinning its key to a public constant does not adapt it; it removes the thing the paper proves and leaves an unvalidated feature extractor wearing a citation. This repository does not do that.

What follows for the algorithms with no primary source. wHash and ColorHash are judged by measured properties rather than by conformance, and under this premise that is not a compromise. There is no paper describing an unkeyed deterministic wavelet hash because, in the security literature's terms, there is nothing to prove about one: no unforgeability claim to make, no adversary to bound. What remains to establish is that it is a good descriptor, and that is a measurement — which is what tests/src/test_hash_properties.c does. Judging by measurement is the right instrument here, not a fallback from a missing one.

What this premise forbids. No claim, anywhere in this repository, that any hash here resists deliberate manipulation. docs/theory/perceptual-hashing.md states the exclusion for users; Dolhansky and Canton Ferrer (2020) is cited there for the attack, and it covers learned hashes too, so the exclusion is not an argument for replacing these algorithms with neural embeddings. If the threat model ever changes, this section is what has to be reopened first — before any algorithm is chosen — because every choice below depends on it.

The criterion for a defect¶

A difference is a defect when it contradicts a formula or step stated by the primary source, or when it measurably worsens one of the properties below.

A difference from a third-party implementation is not, on its own, a defect. ImageHash, OpenCV and pHash are implementations; none of them is a specification, and none has been verified against the papers it implements. BMH is the worked example of why this matters: OpenCV's widely used implementation thresholds on the mean while the paper specifies the median, and a comparison against OpenCV could only have confirmed the departure.

Conforming to a source can put this library at odds with ImageHash; that is accepted. Cross-checking against ImageHash is a signal that something moved, never a criterion for whether it should have; this repository's build gates only on source conformance, formula checks and property measurements.

For the algorithm with no primary source — wHash — only the second half of the criterion can ever apply. It is judged by measurable properties alone, and its attribution header says so rather than implying a specification exists.

Checking formulas, not outputs¶

Where a source states a formula, the check is on the intermediate quantity, on synthetic input whose correct answer is computed by hand or by an independent definition. A mismatch there is unambiguous. A mismatch in the final bits of a hash of a photograph is not: it could be the resampler, the grayscale weights, rounding, or the algorithm.

Implemented as tests/src/test_formula_conformance.c:

• DCT (pHash). The type-II DCT matrix from Zauner's definition 3.3 is checked for orthonormality, and ph_dct2_partial() is checked against a direct O(N⁴) evaluation of the 2-D definition on a fixed pseudo-random 32×32 input, plus inputs whose transform is known in closed form (a constant image, where every AC coefficient is zero and DCT(0,0) = N·mean; and a single cosine at a known frequency, which must put all its energy in one coefficient).
• Haar (wHash). ph_haar_1d_float() is checked for orthonormality and against a step signal whose coefficients are known by hand, and the 2-D level is checked against a separable reference.
• Block means (BMH). Each output value must equal the arithmetic mean of its block, computed independently: checked on exact multiples of the grid and, against an exact area-weighted mean, on non-multiples (test_block_means_on_a_non_multiple).
• Color moments. Mean, standard deviation and skewness are checked against a distribution with hand-computed moments, including a deliberately skewed one where the third moment is negative — the case that needs the sign.

These tests are written against the sources' formulas. Where the code deliberately departs from a source, the test says so in a comment and asserts the implemented behavior.

Measurable properties¶

For everything a source does not specify, and for wHash, which has no source, correctness is replaced by three measurable properties:

• Robustness — the same image after a benign transformation must hash close by.
• Discrimination — different images must hash far apart.
• Separability — the two distributions above must not overlap. This is the property that actually matters; either of the first two is trivially satisfiable alone (a constant hash is perfectly robust).

Separability is reported as the gap between the two distributions in units of their spread, and a threshold is only ever set from a measurement, never chosen by eye.

The corpus¶

A generated synthetic corpus: 24 images produced deterministically from a fixed seed by make_base() in tests/src/synthetic_corpus.h. No external dataset, no manifest of URLs: it works with no network, adds nothing to the repository's size, reproduces identically in CI and on a developer's machine, and cannot rot.

The cost is accepted and stated here: synthetic images do not represent photographs. A number measured on this corpus describes the algorithm's behavior on the corpus. It is suitable for detecting a regression and for comparing two implementations of the same algorithm against each other — which is what these tests are for. It is not evidence about real-world recall, and no such claim should be made from it.

Resolution. Every feature size in make_base() — checkerboard cells, stripe widths, ring periods, disc radii — is a fraction of the corpus resolution (IMG_W/IMG_H, via BASE_RES), so resolution and structural fineness are independent knobs. The corpus is 160×160, deliberately not equal to any algorithm's normalization preset (8 for aHash/dHash, 16 for BMH's default block_size, 32 for pHash's default dct_size, 512 for mHash). mHash still upsamples it 3.2× to reach 512, which understates it somewhat — a corpus at or above 512 would not, but tests/src/test_hash_properties.c's radial-rotation assertions set a practical ceiling on how large this corpus can go before an unrelated property (ph_compute_radial_hash()'s default PH_RADIAL_SAMPLES sampling a larger disc more coarsely) starts failing; see the comment on IMG_W in tests/src/synthetic_corpus.h. Numbers measured on this corpus are comparable within one run of that file at one resolution, and nowhere else.

The documentation site's photographs¶

The site's charts are drawn over the synthetic corpus and over a second one: 200 photographs from Wikimedia Commons, each under CC0 or in the public domain, listed with its source, author, license and SHA-256 in tools/site/corpus_photos.tsv and on the site's photo corpus page. It exists for the claim the synthetic corpus cannot support: how an algorithm behaves on photographs.

It is the site's, not the tests'. No test reads it, and the build of the library never downloads it; only the site's build does, once, into a cache outside the repository, checking each file against its digest. It downloads them from a copy of the corpus at a fixed commit rather than from Commons, whose renditions carry each file's metadata and change their bytes when a description is edited. The tests keep every property of the synthetic corpus above, and the site's charts carry the name of the corpus each was drawn from.