Near Duplicate Detection

Who this is for

This subskill is for Computer Vision Engineers who need to detect exact or near-duplicate images to clean datasets, improve search quality, and reduce labeling costs.

• Building or cleaning large image datasets
• De-duplicating e-commerce product photos or user uploads
• Preventing content spam and repetitive frames in video processing

Prerequisites

• Basic understanding of image features and embeddings (e.g., CNN or ViT/CLIP embeddings)
• Familiarity with cosine similarity, Euclidean distance, and Hamming distance
• Comfort with batching and simple data pipelines

Why this matters

• Dataset quality: Removes duplicate/near-duplicate samples that bias training and inflate metrics.
• Cost savings: Prevents labeling the same or trivially modified images multiple times.
• Product quality: Improves image search, recommendations, and user experience by reducing redundant results.
• Moderation and IP protection: Finds reused or slightly altered images (resized, cropped, filtered).

Concept explained simply

Near duplicate detection compares images via compact representations that are robust to small changes. Two common approaches:

• Perceptual hashing (aHash/dHash/pHash): Converts an image into a fixed-size bitstring. Near duplicates have small Hamming distance.
• Learned embeddings (e.g., CLIP/ResNet features): Represent images as vectors. Near duplicates have high cosine similarity (or small Euclidean distance on normalized vectors).

Mental model

Imagine mapping each image to a point. If two images are visually the same or very similar, their points sit close together. You choose a threshold that decides when two points are "close enough" to count as near duplicates.

Workflow at a glance

1. Choose a representation: Start with pHash for simple cases; use embeddings for robustness to crops, color shifts, and small edits.
2. Normalize (for embeddings): L2-normalize vectors so cosine similarity and Euclidean distance produce consistent rankings.
3. Compute similarity: Hamming distance for hashes; cosine similarity for embeddings.
4. Set a threshold: Calibrate using labeled pairs to balance precision/recall.
5. Scale up: Use indexing or blocking (e.g., approximate nearest neighbor for embeddings; hash buckets for pHash) to avoid O(N^2) comparisons.

Tip: Picking pHash vs embeddings

Use pHash if images differ only by mild compression or tiny edits. Use embeddings if you expect cropping, color filters, small rotations, or text overlays. Many production systems combine both: fast pHash prefilter, then embedding verification.

Worked examples

Example 1 — Dataset cleanup with pHash

You have 50k product photos. Compute a 64-bit pHash for each and group images whose Hamming distance ≤ 3. Review groups; keep one representative per group. Result: fewer redundant items, faster training, less label noise.

Example 2 — Robust matching with embeddings

Use a pretrained vision model to extract 512-D embeddings and L2-normalize them. For each new upload, find the nearest neighbor with cosine similarity. If similarity ≥ 0.96, flag as near duplicate for review. This catches resized or slightly filtered versions better than pHash alone.

Example 3 — Video frame dedup

Extract embeddings for frames every 0.5s. Within a sliding window of 10 seconds, merge frames with cosine similarity ≥ 0.98. This reduces redundant frames while keeping scene changes intact, speeding downstream tasks like captioning or OCR.

Threshold selection

Thresholds depend on your data and representation. A good practice:

1. Collect a small validation set of positive pairs (true near duplicates) and negative pairs.
2. Compute distances/similarities and plot simple counts or compute precision/recall at candidate thresholds.
3. Pick a threshold that meets your business goal: high precision for aggressive dedup, or higher recall to catch more near duplicates.

Quick heuristic

For L2-normalized embeddings from modern vision models, many teams start testing around cosine 0.95–0.98. For 64-bit pHash, Hamming thresholds of 2–6 are common depending on noise. Calibrate on your data.

Scaling up

• Block or bucket: With hashes, compare only within the same or similar buckets (e.g., same high-order bits).
• Approximate nearest neighbor for embeddings: Build an index to retrieve top-K similar items quickly.
• Batching and caching: Cache frequently queried embeddings; deduplicate in mini-batches to limit compute.
• Human-in-the-loop: For borderline scores near the threshold, schedule spot checks to refine thresholds.

Common mistakes

• Using raw pixel MSE/PSNR: Not robust to small shifts, crops, or color changes.
• Forgetting normalization: Euclidean distance on unnormalized embeddings can be misleading.
• Single global threshold for all categories: Different domains (logos vs landscapes) may need different thresholds.
• Ignoring class/cluster context: Backgrounds can dominate similarity; consider region-of-interest when relevant.
• No evaluation set: Thresholds chosen without labeled pairs often underperform in production.

Self-check

• Did you verify the threshold on labeled positives and negatives?
• Are your embeddings L2-normalized before computing cosine or Euclidean?
• Do you handle borderline scores with review or a secondary check?

Exercises

These mirror the practice tasks below. Work them here, then check the solutions at the end of each exercise.

Exercise 1 — Group near-duplicates with Hamming distance (pHash)

Given 8-bit pHashes and threshold T = 2, group images that are near duplicates (distance ≤ 2):

• A: 10101010
• B: 10101011
• C: 10101110
• D: 11110000
• E: 01010101

• [ ] Compute pairwise Hamming distances from A to others.
• [ ] Check B vs C distance for transitive grouping.
• [ ] List final groups.

Exercise 2 — Cosine similarity for embedding-based dedup

Let the query embedding q = [1, 0, 1]. Candidates:

• X1 = [0.9, 0.1, 0.9]
• X2 = [0.2, 0.0, 0.2]
• X3 = [0.8, -0.2, 0.2]

Use cosine similarity and threshold 0.96. Rank candidates by similarity and mark which are near duplicates.

• [ ] L2-normalize or compute cosine directly via dot/(||q||·||x||).
• [ ] Calculate cosine(q, X1), cosine(q, X2), cosine(q, X3).
• [ ] Apply threshold and state the final decision for each.

Practical projects

• Build a dataset deduper: pHash prefilter + embedding verification. Output groups and keep one representative per group with logs.
• Photo library near-duplicate finder: Index embeddings, show top-5 matches per image, allow user to merge or keep.
• Marketplace image moderation: Detect re-uploads of banned images using high-similarity alerts and a review queue.

Learning path

1. Start with pHash on a small folder to understand thresholds and false matches.
2. Extract normalized embeddings and compare with cosine similarity.
3. Combine: pHash to shortlist, embeddings to verify.
4. Scale: Add an approximate nearest neighbor index and batch processing.
5. Refine: Maintain a labeled validation set and periodically recalibrate thresholds.

Next steps

• Run the quick test to check your understanding. Everyone can take it; only logged-in users get saved progress.
• Apply the exercises to a real image folder and record your threshold, precision, and recall on a small labeled set.
• Plan your scaling strategy: blocking for pHash or an embedding index for millions of images.

Mini challenge

You have 5 million user images, frequent crops and color filters, and a hard requirement to avoid false positives. Propose a two-stage system (briefly): which representation for each stage, your target cosine/pHash thresholds, and how you will review borderline cases.