One photograph, four questions

Begin with a photograph of a red chair. Produce five items:

1. the original file;
2. a byte-for-byte copy;
3. a recompressed and cropped copy;
4. a new photograph of the same physical chair; and
5. a drawing of a red chair.

Different questions select different pairs:

Calling every row “similar” erases the contract. The system can then pass a duplicate benchmark and be advertised as an object recognizer, or pass a semantic benchmark while failing to find a recompressed copy reliably.

Byte identity forms clean classes

Define (x\equiv_b y) when the finite byte sequences of files (x) and (y) are equal. Then:

• reflexivity: (x\equiv_b x);
• symmetry: (x\equiv_b y\Rightarrow y\equiv_b x); and
• transitivity: (x\equiv_b y\land y\equiv_b z\Rightarrow x\equiv_b z).

Thus byte identity is an equivalence relation and partitions files into disjoint classes. A cryptographic content digest is an efficient candidate key for those classes, but a digest match is not a mathematical proof that two arbitrary byte strings are equal. Hash functions have finite outputs and their domains are larger, so collisions exist. For adversarial or load-bearing identity, compare the bytes after a digest match or use a threat model that explicitly accepts the residual risk.

A cryptographic digest deliberately changes unpredictably after a tiny edit. That property makes it poor at recognizing recompressed or cropped copies.

A perceptual threshold is not identity

Let (h(x)\in\{0,1\}^n) be a perceptual fingerprint and let (d_H) be Hamming distance. A system may declare a candidate transformed copy when

$$x\sim_\tau y \quad\text{iff}\quad d_H(h(x),h(y))\leq\tau.$$

This relation is reflexive and symmetric, but it need not be transitive. With three two-bit hashes

$$h(a)=00,\qquad h(b)=01,\qquad h(c)=11$$

and (\tau=1), (a\sim_\tau b) and (b\sim_\tau c), yet (a\not\sim_\tau c). Thresholded proximity therefore does not create the same kind of stable quotient as byte identity. Connected-components clustering would add matches the pairwise rule itself rejected.

Increasing (\tau) catches more transformations but admits more unrelated pairs. For labeled positive pairs (P) and negative pairs (N), define

$$FNR(\tau)=\frac{|\{(x,y)\in P:d_H(h(x),h(y))>\tau\}|}{|P|}$$

and

$$FPR(\tau)=\frac{|\{(x,y)\in N:d_H(h(x),h(y))\leq\tau\}|}{|N|}.$$

Choose (\tau) from the declared loss and workload, not from a folklore value. Compression, crop, text overlays, screenshots, and adversarial edits deserve separate slices because their distance distributions differ.

Another view needs local evidence

A crop may remove the global arrangement that a perceptual fingerprint summarizes. A new viewpoint changes it further. Instance search instead finds local image features, matches distinctive descriptors, and asks whether enough correspondences agree on a plausible geometric transformation.

Suppose a candidate correspondence pairs point (p_i) in the query with (q_i) in the document. A geometric model (H) predicts (q_i\approx H(p_i)). An inlier satisfies

$$\|q_i-H(p_i)\|\leq\epsilon.$$

Several individually plausible descriptor matches become convincing only when one model explains them together. This is the same general pattern seen throughout search: cheap evidence generates candidates; a stricter shared constraint verifies them.

SIFT, introduced by David Lowe and developed in its 2004 journal formulation, constructs local descriptors designed to remain stable across scale and rotation and useful ranges of other image changes. It does not turn every viewpoint or object into a guaranteed match. Textureless surfaces, repeated patterns, occlusion, severe viewpoint changes, and domain shift remain hard.

MATCH-IMAGE(QUERY, CANDIDATE, RELATION, POLICY)
Input:  two bounded images, named RELATION, calibrated POLICY
Output: relation-specific decision with evidence

if RELATION = BYTE-IDENTITY
    if DIGEST(QUERY) ≠ DIGEST(CANDIDATE)
        return NO-MATCH
    return COMPARE-BYTES(QUERY, CANDIDATE)
if RELATION = TRANSFORMED-COPY
    distance ← HAMMING(PERCEPTUAL-HASH(QUERY), PERCEPTUAL-HASH(CANDIDATE))
    return THRESHOLD-RECEIPT(distance, POLICY.copyThreshold)
if RELATION = SAME-INSTANCE
    pairs ← MATCH-LOCAL-FEATURES(QUERY, CANDIDATE, POLICY.featureLimit)
    model ← VERIFY-GEOMETRY(pairs, POLICY.errorBound, POLICY.trialLimit)
    return GEOMETRY-RECEIPT(model, pairs)
return UNSUPPORTED-RELATION

The algorithm refuses to silently substitute one relation for another. Every branch has its own judgments, parameters, costs, and evidence receipt.

Wrong turns

The remaining relation is meaning

Two pictures can be relevant to the same request without sharing bytes, transformations, or physical objects. A photograph of a chair and a drawing of a chair may both answer “red seating.” To retrieve that relation, the system must choose a representation whose training objective or hand-built features place those items near each other.

The next chapter begins there. It defines the feature map before asking for nearest neighbors, because changing the map changes what “near” means.

Lessons

• Byte identity, transformed duplication, instance recurrence, and semantic relevance are different relations.
• Byte equality is an equivalence relation; a digest is its candidate key, not a universal perception mechanism.
• Thresholded perceptual distance need not be transitive.
• A larger perceptual threshold trades fewer missed copies for more false matches.
• Calibration requires representative transformations and hard negatives.
• Local feature matches gain force through geometric consistency.
• Instance evidence is not semantic relevance.
• Every result should name the relation that admitted it.

Practice

1. Prove byte equality is reflexive, symmetric, and transitive.
2. Construct a three-hash nontransitivity example for threshold two.
3. Explain why connected components change a pairwise threshold contract.
4. Design positive and hard-negative slices for screenshot duplicate detection.
5. Name a transformation that defeats a digest but should preserve duplication.
6. Name a scene where global perceptual hashing beats local features, and one where local geometry wins.
7. Give two semantically related images that share no instance.

References

• R. Venkatesan, S.-M. Koon, M. H. Jakubowski, and P. Moulin. “Robust Image Hashing.” Proceedings of ICIP, 2000, pp. 664–666.
• David G. Lowe. “Distinctive Image Features from Scale-Invariant Keypoints.” International Journal of Computer Vision 60.2, 2004, pp. 91–110.
• Josef Sivic and Andrew Zisserman. “Video Google: A Text Retrieval Approach to Object Matching in Videos.” Proceedings of ICCV, 2003.