Implementing Perceptual Hashing for Duplicate Image Detection in the Browser

function aHash(imageData, hashSize = 8) {
  // 1. Resize to hashSize x hashSize
  const resized = resize(imageData, hashSize, hashSize);

  // 2. Convert to grayscale
  const gray = toGrayscale(resized);

  // 3. Calculate mean pixel value
  const mean = gray.reduce((sum, val) => sum + val, 0) / gray.length;

  // 4. Each pixel: 1 if above mean, 0 if below
  return gray.map(pixel => pixel >= mean ? 1 : 0);
}

function pHash(imageData, hashSize = 8, sampleSize = 32) {
  // 1. Resize to sampleSize x sampleSize (larger than final hash)
  const resized = resize(imageData, sampleSize, sampleSize);

  // 2. Grayscale
  const gray = toGrayscale(resized);

  // 3. Apply DCT
  const dctData = applyDCT2D(gray, sampleSize);

  // 4. Take top-left hashSize x hashSize (low frequency component)
  const lowFreq = extractTopLeft(dctData, sampleSize, hashSize);

  // 5. Median of low-frequency values (excluding DC component)
  const median = calculateMedian(lowFreq.slice(1)); // skip DC

  // 6. 1 if above median, 0 if below
  return lowFreq.map(val => val >= median ? 1 : 0);
}

function dHash(imageData, hashSize = 8) {
  // 1. Resize to (hashSize+1) x hashSize
  const resized = resize(imageData, hashSize + 1, hashSize);
  const gray = toGrayscale(resized);

  const hash = [];
  for (let row = 0; row < hashSize; row++) {
    for (let col = 0; col < hashSize; col++) {
      const idx = row * (hashSize + 1) + col;
      // 1 if pixel is brighter than next pixel in same row
      hash.push(gray[idx] > gray[idx + 1] ? 1 : 0);
    }
  }
  return hash;
}

function applyDCT2D(data, n) {
  // Apply 1D DCT to each row
  const rowDCT = [];
  for (let i = 0; i < n; i++) {
    const row = data.slice(i * n, (i + 1) * n);
    rowDCT.push(...dct1D(row));
  }

  // Apply 1D DCT to each column
  const result = new Array(n * n);
  for (let j = 0; j < n; j++) {
    const col = [];
    for (let i = 0; i < n; i++) {
      col.push(rowDCT[i * n + j]);
    }
    const colDCT = dct1D(col);
    for (let i = 0; i < n; i++) {
      result[i * n + j] = colDCT[i];
    }
  }
  return result;
}

function dct1D(signal) {
  const n = signal.length;
  return signal.map((_, k) => {
    let sum = 0;
    for (let i = 0; i < n; i++) {
      sum += signal[i] * Math.cos((Math.PI / n) * (i + 0.5) * k);
    }
    return sum * (k === 0 ? Math.sqrt(1 / n) : Math.sqrt(2 / n));
  });
}

function hammingDistance(hash1, hash2) {
  if (hash1.length !== hash2.length) throw new Error('Hash length mismatch');
  return hash1.reduce((count, bit, i) => count + (bit !== hash2[i] ? 1 : 0), 0);
}

function isSimilar(hash1, hash2, threshold = 10) {
  return hammingDistance(hash1, hash2) <= threshold;
}

async function getImageData(file) {
  return new Promise((resolve) => {
    const img = new Image();
    img.onload = () => {
      const canvas = document.createElement('canvas');
      canvas.width = img.width;
      canvas.height = img.height;
      const ctx = canvas.getContext('2d');
      ctx.drawImage(img, 0, 0);
      resolve(ctx.getImageData(0, 0, canvas.width, canvas.height));
    };
    img.src = URL.createObjectURL(file);
  });
}

function resize(imageData, targetW, targetH) {
  const canvas = document.createElement('canvas');
  canvas.width = targetW;
  canvas.height = targetH;
  const ctx = canvas.getContext('2d');

  // OffscreenCanvas approach for better performance
  const srcCanvas = document.createElement('canvas');
  srcCanvas.width = imageData.width;
  srcCanvas.height = imageData.height;
  srcCanvas.getContext('2d').putImageData(imageData, 0, 0);

  ctx.drawImage(srcCanvas, 0, 0, targetW, targetH);

  const resized = ctx.getImageData(0, 0, targetW, targetH);
  return Array.from(resized.data);
}

function toGrayscale(pixelArray) {
  const gray = [];
  for (let i = 0; i < pixelArray.length; i += 4) {
    // ITU-R BT.601 luminance formula
    gray.push(0.299 * pixelArray[i] + 0.587 * pixelArray[i+1] + 0.114 * pixelArray[i+2]);
  }
  return gray;
}

async function findDuplicates(imageFiles, onProgress) {
  const hashes = [];

  // Phase 1: Hash all images
  for (let i = 0; i < imageFiles.length; i++) {
    const imageData = await getImageData(imageFiles[i]);
    hashes.push({ file: imageFiles[i], hash: pHash(imageData) });
    onProgress({ phase: 'hashing', current: i + 1, total: imageFiles.length });
  }

  // Phase 2: Compare all pairs
  const duplicates = [];
  let compared = 0;
  const totalPairs = (hashes.length * (hashes.length - 1)) / 2;

  for (let i = 0; i < hashes.length; i++) {
    for (let j = i + 1; j < hashes.length; j++) {
      const dist = hammingDistance(hashes[i].hash, hashes[j].hash);
      if (dist <= 10) {
        duplicates.push({ a: hashes[i].file, b: hashes[j].file, distance: dist });
      }
      compared++;

      // Yield to browser every 500 comparisons
      if (compared % 500 === 0) {
        onProgress({ phase: 'comparing', current: compared, total: totalPairs });
        await new Promise(resolve => setTimeout(resolve, 0));
      }
    }
  }

  return duplicates;
}

function quickSimilarityCheck(hash1, hash2) {
  // aHash first (fast) — if very different, skip pHash
  const aHashDist = hammingDistance(hash1.aHash, hash2.aHash);
  if (aHashDist > 20) return false;

  // pHash for confirmation (slower but more accurate)
  const pHashDist = hammingDistance(hash1.pHash, hash2.pHash);
  return pHashDist <= 10;
}