CHAPTER 03

Content Fingerprinting Techniques

Learn perceptual hashing algorithms and similarity detection for multimedia authentication

Introduction to Perceptual Hashing

Unlike cryptographic hashes that produce completely different outputs for even tiny input changes, perceptual hashes generate similar fingerprints for perceptually similar content. This makes them ideal for detecting modified, compressed, or reformatted copies of original content.

A good perceptual hash should be:

Robust: Resistant to common transformations (compression, resizing, rotation)
Discriminative: Different content produces different hashes
Efficient: Fast to compute and compare
Compact: Small fingerprint size for storage and transmission

ℹ️ Use Case Difference
Cryptographic hashes verify exact integrity (did this byte change?). Perceptual hashes detect semantic similarity (is this the same image after JPEG compression?). Both are essential for comprehensive content authentication.

Image Fingerprinting Algorithms

Several algorithms exist for generating image fingerprints, each with different trade-offs.

Average Hash (aHash)

The simplest perceptual hash compares each pixel to the average luminance:

// Example: Average Hash Implementation
import Jimp from 'jimp';

async function averageHash(imagePath, hashSize = 8) {
    // Load and resize image
    const image = await Jimp.read(imagePath);
    image.resize(hashSize, hashSize).greyscale();

    // Calculate average luminance
    let sum = 0;
    const pixels = [];

    image.scan(0, 0, hashSize, hashSize, (x, y, idx) => {
        const luminance = image.bitmap.data[idx];
        pixels.push(luminance);
        sum += luminance;
    });

    const average = sum / (hashSize * hashSize);

    // Generate hash: 1 if above average, 0 if below
    let hash = '';
    for (const pixel of pixels) {
        hash += pixel > average ? '1' : '0';
    }

    return {
        algorithm: 'aHash',
        hash: BigInt('0b' + hash).toString(16),
        size: hashSize * hashSize
    };
}

// Usage
const hash1 = await averageHash('original.jpg');
const hash2 = await averageHash('compressed.jpg');
console.log('Hash 1:', hash1.hash);
console.log('Hash 2:', hash2.hash);

Difference Hash (dHash)

dHash compares adjacent pixels to detect gradients, making it more robust to gamma correction:

async function differenceHash(imagePath, hashSize = 8) {
    const image = await Jimp.read(imagePath);
    image.resize(hashSize + 1, hashSize).greyscale();

    let hash = '';

    // Compare each pixel to its right neighbor
    for (let y = 0; y < hashSize; y++) {
        for (let x = 0; x < hashSize; x++) {
            const leftPixel = image.getPixelColor(x, y);
            const rightPixel = image.getPixelColor(x + 1, y);

            const leftLum = Jimp.intToRGBA(leftPixel).r;
            const rightLum = Jimp.intToRGBA(rightPixel).r;

            hash += leftLum > rightLum ? '1' : '0';
        }
    }

    return {
        algorithm: 'dHash',
        hash: BigInt('0b' + hash).toString(16),
        size: hashSize * hashSize
    };
}

Perceptual Hash (pHash)

pHash uses Discrete Cosine Transform (DCT) to capture frequency domain features:

// Example: pHash with DCT
function dct2D(matrix) {
    const N = matrix.length;
    const result = Array(N).fill(0).map(() => Array(N).fill(0));

    for (let u = 0; u < N; u++) {
        for (let v = 0; v < N; v++) {
            let sum = 0;
            for (let x = 0; x < N; x++) {
                for (let y = 0; y < N; y++) {
                    sum += matrix[x][y] *
                           Math.cos(Math.PI * u * (2 * x + 1) / (2 * N)) *
                           Math.cos(Math.PI * v * (2 * y + 1) / (2 * N));
                }
            }
            const cu = u === 0 ? 1 / Math.sqrt(2) : 1;
            const cv = v === 0 ? 1 / Math.sqrt(2) : 1;
            result[u][v] = 0.25 * cu * cv * sum;
        }
    }
    return result;
}

async function perceptualHash(imagePath, hashSize = 8) {
    const image = await Jimp.read(imagePath);
    const size = 32; // DCT size
    image.resize(size, size).greyscale();

    // Extract luminance matrix
    const matrix = Array(size).fill(0).map(() => Array(size).fill(0));
    image.scan(0, 0, size, size, (x, y, idx) => {
        matrix[y][x] = image.bitmap.data[idx];
    });

    // Compute DCT
    const dct = dct2D(matrix);

    // Extract top-left 8x8 (low frequencies)
    const lowFreq = [];
    for (let y = 0; y < hashSize; y++) {
        for (let x = 0; x < hashSize; x++) {
            lowFreq.push(dct[y][x]);
        }
    }

    // Compute median
    const sorted = [...lowFreq].sort((a, b) => a - b);
    const median = sorted[Math.floor(sorted.length / 2)];

    // Generate hash
    let hash = '';
    for (const val of lowFreq) {
        hash += val > median ? '1' : '0';
    }

    return {
        algorithm: 'pHash',
        hash: BigInt('0b' + hash).toString(16),
        size: hashSize * hashSize
    };
}

Hamming Distance and Similarity

To compare perceptual hashes, we calculate Hamming distance - the number of differing bits:

function hammingDistance(hash1, hash2) {
    // Convert hex to binary
    const bin1 = BigInt('0x' + hash1).toString(2).padStart(64, '0');
    const bin2 = BigInt('0x' + hash2).toString(2).padStart(64, '0');

    // Count differing bits
    let distance = 0;
    for (let i = 0; i < bin1.length; i++) {
        if (bin1[i] !== bin2[i]) distance++;
    }

    return distance;
}

function calculateSimilarity(hash1, hash2, hashBits = 64) {
    const distance = hammingDistance(hash1, hash2);
    const similarity = ((hashBits - distance) / hashBits) * 100;
    return {
        distance,
        similarity: similarity.toFixed(2) + '%',
        isMatch: similarity >= 90 // 90% threshold
    };
}

// Usage
const result = calculateSimilarity(hash1.hash, hash2.hash);
console.log('Similarity:', result.similarity);
console.log('Match:', result.isMatch);

Hamming Distance	Interpretation	Use Case
0-5 bits	Identical or minimal difference	Same image, different compression
6-10 bits	Very similar	Slight edits, color adjustments
11-20 bits	Similar	Cropped or resized versions
21+ bits	Different content	Unrelated images

Video Fingerprinting

Video fingerprinting extracts hashes from keyframes and analyzes temporal patterns.

Keyframe Extraction

// Example: Video Fingerprinting
import ffmpeg from 'fluent-ffmpeg';

async function extractKeyframes(videoPath, interval = 1) {
    return new Promise((resolve, reject) => {
        const keyframes = [];

        ffmpeg(videoPath)
            .on('filenames', (filenames) => {
                keyframes.push(...filenames);
            })
            .on('end', () => resolve(keyframes))
            .on('error', reject)
            .screenshots({
                count: 10,
                folder: './temp',
                filename: 'frame-%i.png'
            });
    });
}

async function videoFingerprint(videoPath) {
    // Extract keyframes
    const frames = await extractKeyframes(videoPath);

    // Hash each frame
    const frameHashes = [];
    for (const frame of frames) {
        const hash = await perceptualHash(`./temp/${frame}`);
        frameHashes.push(hash.hash);
    }

    // Compute temporal hash
    const temporalHash = hashSequence(frameHashes);

    return {
        algorithm: 'video-pHash',
        keyframes: frameHashes.length,
        frameHashes: frameHashes,
        temporalHash: temporalHash,
        duration: await getVideoDuration(videoPath)
    };
}

function hashSequence(hashes) {
    // Create hash representing frame sequence
    const combined = hashes.join('');
    return createHash('sha256').update(combined).digest('hex');
}

Audio Fingerprinting

Audio fingerprinting analyzes spectral features to create robust acoustic signatures.

Chromaprint Algorithm

Chromaprint is widely used for audio fingerprinting:

// Example: Audio Fingerprinting with Chromaprint
import { exec } from 'child_process';
import { promisify } from 'util';

const execAsync = promisify(exec);

async function audioFingerprint(audioPath) {
    // Use fpcalc (Chromaprint command-line tool)
    const { stdout } = await execAsync(`fpcalc -json "${audioPath}"`);
    const result = JSON.parse(stdout);

    return {
        algorithm: 'Chromaprint',
        duration: result.duration,
        fingerprint: result.fingerprint,
        bitrate: await getAudioBitrate(audioPath)
    };
}

async function compareAudioFingerprints(fp1, fp2) {
    // Compute similarity score
    const similarity = computeChromaprintSimilarity(fp1, fp2);

    return {
        similarity: (similarity * 100).toFixed(2) + '%',
        isMatch: similarity >= 0.85,
        algorithm: 'Chromaprint'
    };
}

function computeChromaprintSimilarity(fp1, fp2) {
    // Chromaprint uses compressed integer sequences
    // This is a simplified comparison
    const arr1 = fp1.split(',').map(Number);
    const arr2 = fp2.split(',').map(Number);

    let matches = 0;
    const minLength = Math.min(arr1.length, arr2.length);

    for (let i = 0; i < minLength; i++) {
        const xor = arr1[i] ^ arr2[i];
        const bits = countBits(xor);
        matches += (32 - bits) / 32; // Assuming 32-bit integers
    }

    return matches / minLength;
}

function countBits(n) {
    let count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

Text Fingerprinting

Text fingerprinting detects plagiarism, paraphrasing, and unauthorized copying.

N-gram Shingling

// Example: Text Fingerprinting with Shingling
function generateShingles(text, n = 3) {
    // Normalize text
    const normalized = text.toLowerCase()
        .replace(/[^\w\s]/g, '')
        .split(/\s+/);

    // Create n-grams
    const shingles = new Set();
    for (let i = 0; i <= normalized.length - n; i++) {
        const shingle = normalized.slice(i, i + n).join(' ');
        shingles.add(shingle);
    }

    return shingles;
}

function jaccardSimilarity(set1, set2) {
    const intersection = new Set([...set1].filter(x => set2.has(x)));
    const union = new Set([...set1, ...set2]);

    return intersection.size / union.size;
}

function textFingerprint(text) {
    const shingles = generateShingles(text, 3);

    // MinHash for efficient similarity estimation
    const minhash = computeMinHash(shingles, 128);

    return {
        algorithm: 'MinHash',
        shingleCount: shingles.size,
        signature: minhash,
        wordCount: text.split(/\s+/).length
    };
}

function computeMinHash(shingles, numHashes) {
    const signature = Array(numHashes).fill(Infinity);

    for (const shingle of shingles) {
        for (let i = 0; i < numHashes; i++) {
            const hash = hashWithSeed(shingle, i);
            signature[i] = Math.min(signature[i], hash);
        }
    }

    return signature;
}

function hashWithSeed(str, seed) {
    let hash = seed;
    for (let i = 0; i < str.length; i++) {
        hash = ((hash << 5) - hash) + str.charCodeAt(i);
        hash = hash & hash; // Convert to 32-bit integer
    }
    return Math.abs(hash);
}

// Usage
const fp1 = textFingerprint("This is original content about AI authentication.");
const fp2 = textFingerprint("This is original text about AI verification.");

const similarity = estimateSimilarity(fp1.signature, fp2.signature);
console.log('Text similarity:', (similarity * 100).toFixed(2) + '%');

Neural Hashing with Deep Learning

Modern neural networks can learn optimal hash functions for specific content types.

Siamese Networks for Similarity Learning

Siamese networks learn embeddings where similar content has nearby representations:

// Example: Neural Hash with TensorFlow.js
import * as tf from '@tensorflow/tfjs-node';

class NeuralHasher {
    constructor() {
        this.model = this.buildModel();
    }

    buildModel() {
        // CNN-based feature extractor
        const input = tf.input({ shape: [224, 224, 3] });

        let x = tf.layers.conv2d({
            filters: 32,
            kernelSize: 3,
            activation: 'relu'
        }).apply(input);

        x = tf.layers.maxPooling2d({ poolSize: 2 }).apply(x);
        x = tf.layers.conv2d({ filters: 64, kernelSize: 3, activation: 'relu' }).apply(x);
        x = tf.layers.maxPooling2d({ poolSize: 2 }).apply(x);
        x = tf.layers.flatten().apply(x);
        x = tf.layers.dense({ units: 256, activation: 'relu' }).apply(x);

        // Hash layer (binary output)
        const hash = tf.layers.dense({
            units: 64,
            activation: 'tanh',
            name: 'hash_layer'
        }).apply(x);

        return tf.model({ inputs: input, outputs: hash });
    }

    async computeHash(imageTensor) {
        // Forward pass
        const embedding = this.model.predict(imageTensor);

        // Binarize (threshold at 0)
        const binary = embedding.greater(0).asType('int32');

        // Convert to hex string
        const hashArray = await binary.data();
        let hashString = '';
        for (let i = 0; i < hashArray.length; i += 4) {
            const nibble = hashArray.slice(i, i + 4).reduce((acc, bit, idx) =>
                acc + (bit << idx), 0);
            hashString += nibble.toString(16);
        }

        return hashString;
    }

    async compareHashes(hash1, hash2) {
        const distance = hammingDistance(hash1, hash2);
        const similarity = (64 - distance) / 64;

        return {
            distance,
            similarity: (similarity * 100).toFixed(2) + '%',
            isMatch: similarity >= 0.9
        };
    }
}

// Usage
const hasher = new NeuralHasher();
const hash1 = await hasher.computeHash(imageTensor1);
const hash2 = await hasher.computeHash(imageTensor2);
const result = await hasher.compareHashes(hash1, hash2);

Robustness Testing

Fingerprinting algorithms must be tested against various transformations:

Common Transformations

Compression: JPEG quality 10-100, WebP, AVIF
Resizing: 50%-200% scaling
Rotation: -15° to +15°
Color adjustments: Brightness, contrast, saturation
Cropping: 10%-30% removal
Noise: Gaussian, salt-and-pepper
Blur: Gaussian, motion blur
Filters: Sharpen, edge detection

// Example: Robustness Testing Suite
async function testRobustness(originalImage) {
    const originalHash = await perceptualHash(originalImage);
    const results = [];

    // Test JPEG compression
    for (let quality = 10; quality <= 100; quality += 10) {
        const compressed = await compressJPEG(originalImage, quality);
        const hash = await perceptualHash(compressed);
        const similarity = calculateSimilarity(originalHash.hash, hash.hash);

        results.push({
            transformation: `JPEG Q${quality}`,
            similarity: similarity.similarity,
            passed: similarity.isMatch
        });
    }

    // Test resizing
    for (let scale of [0.5, 0.75, 1.25, 1.5, 2.0]) {
        const resized = await resizeImage(originalImage, scale);
        const hash = await perceptualHash(resized);
        const similarity = calculateSimilarity(originalHash.hash, hash.hash);

        results.push({
            transformation: `Resize ${scale}x`,
            similarity: similarity.similarity,
            passed: similarity.isMatch
        });
    }

    // Generate report
    const passRate = results.filter(r => r.passed).length / results.length;

    return {
        totalTests: results.length,
        passed: results.filter(r => r.passed).length,
        passRate: (passRate * 100).toFixed(2) + '%',
        results: results
    };
}

Distributed Fingerprint Databases

Large-scale content authentication requires efficient fingerprint storage and retrieval.

Locality-Sensitive Hashing (LSH)

LSH enables approximate nearest neighbor search in high-dimensional spaces:

// Example: LSH Index for Fast Similarity Search
class LSHIndex {
    constructor(numTables = 10, hashSize = 8) {
        this.numTables = numTables;
        this.hashSize = hashSize;
        this.tables = Array(numTables).fill(null).map(() => new Map());
        this.randomProjections = this.generateProjections();
    }

    generateProjections() {
        const projections = [];
        for (let i = 0; i < this.numTables; i++) {
            const projection = [];
            for (let j = 0; j < this.hashSize; j++) {
                projection.push(Math.floor(Math.random() * 64));
            }
            projections.push(projection);
        }
        return projections;
    }

    hash(fingerprint, tableIdx) {
        const projection = this.randomProjections[tableIdx];
        let hash = '';

        for (const bitPos of projection) {
            const bit = (BigInt('0x' + fingerprint) >> BigInt(bitPos)) & 1n;
            hash += bit.toString();
        }

        return hash;
    }

    insert(fingerprint, contentId) {
        for (let i = 0; i < this.numTables; i++) {
            const bucket = this.hash(fingerprint, i);

            if (!this.tables[i].has(bucket)) {
                this.tables[i].set(bucket, []);
            }

            this.tables[i].get(bucket).push({
                fingerprint,
                contentId
            });
        }
    }

    query(fingerprint, threshold = 10) {
        const candidates = new Map();

        // Check all tables
        for (let i = 0; i < this.numTables; i++) {
            const bucket = this.hash(fingerprint, i);
            const items = this.tables[i].get(bucket) || [];

            for (const item of items) {
                const distance = hammingDistance(fingerprint, item.fingerprint);

                if (distance <= threshold) {
                    if (!candidates.has(item.contentId) ||
                        candidates.get(item.contentId) > distance) {
                        candidates.set(item.contentId, distance);
                    }
                }
            }
        }

        // Return sorted results
        return Array.from(candidates.entries())
            .sort((a, b) => a[1] - b[1])
            .map(([contentId, distance]) => ({
                contentId,
                distance,
                similarity: ((64 - distance) / 64 * 100).toFixed(2) + '%'
            }));
    }
}

// Usage
const lsh = new LSHIndex(10, 8);

// Index content
lsh.insert(hash1, 'content-001');
lsh.insert(hash2, 'content-002');

// Search for similar content
const matches = lsh.query(queryHash, 5);
console.log('Similar content:', matches);

Real-World Implementation

Complete fingerprinting system combining multiple algorithms:

// Example: Production Fingerprinting Service
class ContentFingerprintService {
    constructor() {
        this.lshIndex = new LSHIndex();
        this.db = new Database();
    }

    async fingerprintContent(file, metadata) {
        const type = detectContentType(file);
        let fingerprints;

        switch (type) {
            case 'image':
                fingerprints = await this.fingerprintImage(file);
                break;
            case 'video':
                fingerprints = await this.fingerprintVideo(file);
                break;
            case 'audio':
                fingerprints = await this.fingerprintAudio(file);
                break;
            case 'text':
                fingerprints = await this.fingerprintText(file);
                break;
            default:
                throw new Error('Unsupported content type');
        }

        // Store in database
        const contentId = generateUUID();
        await this.db.insert({
            id: contentId,
            type: type,
            fingerprints: fingerprints,
            metadata: metadata,
            timestamp: new Date().toISOString()
        });

        // Index for similarity search
        for (const fp of fingerprints) {
            this.lshIndex.insert(fp.hash, contentId);
        }

        return {
            contentId,
            fingerprints,
            indexed: true
        };
    }

    async findSimilarContent(queryFile, threshold = 0.85) {
        const type = detectContentType(queryFile);
        const fingerprints = await this[`fingerprint${capitalize(type)}`](queryFile);

        const results = [];

        for (const fp of fingerprints) {
            const matches = this.lshIndex.query(fp.hash, 10);
            results.push(...matches);
        }

        // Deduplicate and filter by threshold
        const unique = new Map();
        for (const result of results) {
            const similarity = parseFloat(result.similarity) / 100;
            if (similarity >= threshold) {
                if (!unique.has(result.contentId) ||
                    unique.get(result.contentId) < similarity) {
                    unique.set(result.contentId, similarity);
                }
            }
        }

        // Fetch full metadata
        const finalResults = [];
        for (const [contentId, similarity] of unique.entries()) {
            const metadata = await this.db.get(contentId);
            finalResults.push({
                contentId,
                similarity: (similarity * 100).toFixed(2) + '%',
                metadata
            });
        }

        return finalResults.sort((a, b) =>
            parseFloat(b.similarity) - parseFloat(a.similarity));
    }

    async fingerprintImage(file) {
        return [
            await averageHash(file),
            await differenceHash(file),
            await perceptualHash(file)
        ];
    }

    async fingerprintVideo(file) {
        return await videoFingerprint(file);
    }

    async fingerprintAudio(file) {
        return await audioFingerprint(file);
    }

    async fingerprintText(file) {
        return textFingerprint(file);
    }
}

✅ Best Practices

Use multiple hash algorithms for robustness
Test against realistic transformations
Index fingerprints with LSH for scalability
Store original hashes alongside cryptographic hashes
Monitor false positive/negative rates in production

📌 Key Takeaways

Perceptual hashes detect similar content despite transformations
Different algorithms (aHash, dHash, pHash) have different robustness characteristics
Hamming distance measures similarity between binary hashes
Video and audio fingerprinting require specialized techniques
Neural hashing can learn optimal representations for specific domains
LSH enables efficient similarity search in large databases
Production systems should combine multiple fingerprinting methods

📝 Review Questions

What is the fundamental difference between cryptographic and perceptual hashing?
Explain how the pHash algorithm uses DCT for robustness.
Why is Hamming distance appropriate for comparing perceptual hashes?
How does video fingerprinting differ from image fingerprinting?
What is the purpose of Locality-Sensitive Hashing in content authentication?
Describe three transformations that a robust fingerprint should survive.
How do neural hashing approaches differ from traditional algorithms?
Why is it beneficial to use multiple fingerprinting algorithms together?

弘益人間 (홍익인간) · Benefit All Humanity