每日算法 — 使用java实现找茬：感知哈希与像素级差异检测算法

游戏简介与算法背景

找茬（Spot the Difference）是一款考验观察力的经典益智游戏：两幅看似相同的图片中隐藏着若干处细微差异，玩家需要在限定时间内找出所有不同点。从算法角度看，”找茬”本质上是图像差异检测问题，涉及像素级比较、特征提取和相似度度量。本文将用 Java 实现基于感知哈希（Perceptual Hash）与像素差异的混合检测算法。

核心算法设计

1. 感知哈希（pHash）算法

感知哈希通过提取图像的视觉特征生成指纹，对微小形变、亮度调整具有鲁棒性。标准流程：
1. 缩放为 32×32 灰度图
2. 离散余弦变换（DCT）提取低频成分
3. 取左上角 8×8 区域计算均值
4. 生成 64 位哈希值

2. 像素级差异检测

对两图逐像素比较差值，通过阈值过滤噪声，使用连通区域分析定位差异块。

3. 混合策略

• 先用 pHash 快速判断整体相似度
• 若整体相似则进行像素级精细检测
• 对差异区域做形态学处理消除噪点

Java 完整实现

import javax.imageio.ImageIO;
import java.awt.*;
import java.awt.image.BufferedImage;
import java.awt.image.DataBufferByte;
import java.io.File;
import java.io.IOException;
import java.util.*;

/**
 * 找茬游戏 — 感知哈希与像素差异检测算法
 * 
 * 核心算法：
 * 1. 感知哈希（DCT-based pHash）：快速全局相似度判断
 * 2. 像素级差分：精确定位差异区域
 * 3. 连通区域标记（BFS/Union-Find）：聚合差异像素为差异块
 * 4. 汉明距离：哈希相似度度量
 */
public class SpotDifference {

    private static final int PHASH_SIZE = 32;
    private static final int HASH_BITS = 64;
    private static final int DIFF_THRESHOLD = 30; // 像素差阈值
    private static final int MIN_DIFF_AREA = 50;  // 最小差异区域像素数

    /**
     * 离散余弦变换（DCT）一维实现
     * 用于感知哈希提取低频特征
     */
    public static double[] dct1d(double[] data) {
        int n = data.length;
        double[] result = new double[n];
        for (int k = 0; k < n; k++) {
            double sum = 0;
            for (int i = 0; i < n; i++) {
                sum += data[i] * Math.cos(Math.PI / n * (i + 0.5) * k);
            }
            result[k] = sum;
        }
        return result;
    }

    /**
     * 二维DCT：先对每行做DCT，再对每列做DCT
     */
    public static double[][] dct2d(double[][] matrix) {
        int n = matrix.length;
        double[][] temp = new double[n][n];
        double[][] result = new double[n][n];

        // 对每行做1D DCT
        for (int i = 0; i < n; i++) {
            temp[i] = dct1d(matrix[i]);
        }

        // 对每列做1D DCT
        for (int j = 0; j < n; j++) {
            double[] col = new double[n];
            for (int i = 0; i < n; i++) {
                col[i] = temp[i][j];
            }
            double[] dctCol = dct1d(col);
            for (int i = 0; i < n; i++) {
                result[i][j] = dctCol[i];
            }
        }

        return result;
    }

    /**
     * 计算感知哈希（pHash）
     * 对缩放、亮度变化具有鲁棒性
     */
    public static long perceptualHash(BufferedImage image) {
        // 1. 缩放为 PHASH_SIZE x PHASH_SIZE 并转灰度
        BufferedImage gray = new BufferedImage(PHASH_SIZE, PHASH_SIZE, BufferedImage.TYPE_BYTE_GRAY);
        Graphics2D g = gray.createGraphics();
        g.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR);
        g.drawImage(image, 0, 0, PHASH_SIZE, PHASH_SIZE, null);
        g.dispose();

        // 2. 提取像素值到二维数组
        double[][] pixels = new double[PHASH_SIZE][PHASH_SIZE];
        for (int y = 0; y < PHASH_SIZE; y++) {
            for (int x = 0; x < PHASH_SIZE; x++) {
                pixels[y][x] = gray.getRaster().getSample(x, y, 0);
            }
        }

        // 3. 二维DCT变换
        double[][] dct = dct2d(pixels);

        // 4. 取左上角 8x8 低频区域（排除直流分量 [0][0]）
        double[] lowFreq = new double[HASH_BITS];
        int idx = 0;
        for (int y = 0; y < 8; y++) {
            for (int x = 0; x < 8; x++) {
                if (x == 0 && y == 0) continue; // 跳过直流分量
                if (idx < HASH_BITS) {
                    lowFreq[idx++] = dct[y][x];
                }
            }
        }

        // 5. 计算均值并生成哈希
        double mean = 0;
        for (double v : lowFreq) mean += v;
        mean /= HASH_BITS;

        long hash = 0;
        for (int i = 0; i < HASH_BITS; i++) {
            if (lowFreq[i] > mean) {
                hash |= (1L << i);
            }
        }

        return hash;
    }

    /**
     * 计算两个哈希的汉明距离
     * 距离越小表示图像越相似
     */
    public static int hammingDistance(long hash1, long hash2) {
        long xor = hash1 ^ hash2;
        int distance = 0;
        while (xor != 0) {
            distance += (xor & 1);
            xor >>>= 1;
        }
        return distance;
    }

    /**
     * 像素级差异检测
     * 返回标记了差异区域的图像和差异块列表
     */
    public static DifferenceResult detectPixelDiff(BufferedImage img1, BufferedImage img2) {
        int width = Math.min(img1.getWidth(), img2.getWidth());
        int height = Math.min(img1.getHeight(), img2.getHeight());

        // 创建差异标记图
        BufferedImage diffMap = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        boolean[][] diffMask = new boolean[height][width];

        // 逐像素比较
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                int rgb1 = img1.getRGB(x, y);
                int rgb2 = img2.getRGB(x, y);

                int r1 = (rgb1 >> 16) & 0xFF;
                int g1 = (rgb1 >> 8) & 0xFF;
                int b1 = rgb1 & 0xFF;
                int r2 = (rgb2 >> 16) & 0xFF;
                int g2 = (rgb2 >> 8) & 0xFF;
                int b2 = rgb2 & 0xFF;

                // 计算欧几里得色差
                double colorDiff = Math.sqrt(
                    Math.pow(r1 - r2, 2) + 
                    Math.pow(g1 - g2, 2) + 
                    Math.pow(b1 - b2, 2)
                );

                if (colorDiff > DIFF_THRESHOLD) {
                    diffMask[y][x] = true;
                    diffMap.setRGB(x, y, Color.RED.getRGB()); // 标记差异为红色
                } else {
                    diffMap.setRGB(x, y, img1.getRGB(x, y));
                }
            }
        }

        // 连通区域标记（BFS），聚合差异像素为差异块
        List<Rectangle> diffRegions = findConnectedRegions(diffMask, width, height);

        // 在差异图上绘制矩形框
        Graphics2D g = diffMap.createGraphics();
        g.setColor(Color.GREEN);
        g.setStroke(new BasicStroke(3));
        for (Rectangle r : diffRegions) {
            g.drawRect(r.x, r.y, r.width, r.height);
        }
        g.dispose();

        return new DifferenceResult(diffMap, diffRegions, diffRegions.size());
    }

    /**
     * BFS连通区域标记，找出所有独立的差异块
     */
    private static List<Rectangle> findConnectedRegions(boolean[][] mask, int width, int height) {
        boolean[][] visited = new boolean[height][width];
        List<Rectangle> regions = new ArrayList<>();

        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}, {-1,-1}, {-1,1}, {1,-1}, {1,1}};

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                if (mask[y][x] && !visited[y][x]) {
                    // BFS 遍历整个连通块
                    List<Point> pixels = new ArrayList<>();
                    Queue<Point> queue = new LinkedList<>();
                    queue.offer(new Point(x, y));
                    visited[y][x] = true;

                    while (!queue.isEmpty()) {
                        Point p = queue.poll();
                        pixels.add(p);

                        for (int[] d : dirs) {
                            int nx = p.x + d[0];
                            int ny = p.y + d[1];
                            if (nx >= 0 && nx < width && ny >= 0 && ny < height 
                                && mask[ny][nx] && !visited[ny][nx]) {
                                visited[ny][nx] = true;
                                queue.offer(new Point(nx, ny));
                            }
                        }
                    }

                    // 过滤小噪点
                    if (pixels.size() >= MIN_DIFF_AREA) {
                        int minX = width, minY = height, maxX = 0, maxY = 0;
                        for (Point p : pixels) {
                            minX = Math.min(minX, p.x);
                            minY = Math.min(minY, p.y);
                            maxX = Math.max(maxX, p.x);
                            maxY = Math.max(maxY, p.y);
                        }
                        regions.add(new Rectangle(minX, minY, maxX - minX + 1, maxY - minY + 1));
                    }
                }
            }
        }

        return regions;
    }

    /**
     * 主检测流程：先pHash快速筛选，再像素级精细检测
     */
    public static void findDifferences(String path1, String path2, String outputPath) throws IOException {
        BufferedImage img1 = ImageIO.read(new File(path1));
        BufferedImage img2 = ImageIO.read(new File(path2));

        System.out.println("=== 找茬算法检测开始 ===");

        // Step 1: 感知哈希快速比较
        long hash1 = perceptualHash(img1);
        long hash2 = perceptualHash(img2);
        int hamming = hammingDistance(hash1, hash2);
        System.out.printf("图像1 pHash: %016X%n", hash1);
        System.out.printf("图像2 pHash: %016X%n", hash2);
        System.out.printf("汉明距离: %d (阈值: 10)%n", hamming);

        if (hamming == 0) {
            System.out.println("两图完全相同，无需精细检测。");
            return;
        }

        // Step 2: 像素级差异检测
        DifferenceResult result = detectPixelDiff(img1, img2);
        System.out.printf("发现 %d 处差异区域%n", result.regionCount);

        for (int i = 0; i < result.regions.size(); i++) {
            Rectangle r = result.regions.get(i);
            System.out.printf("差异 #%d: 位置(%d,%d), 大小(%dx%d)%n", 
                i + 1, r.x, r.y, r.width, r.height);
        }

        // 保存差异标记图
        ImageIO.write(result.diffImage, "PNG", new File(outputPath));
        System.out.println("差异标记图已保存至: " + outputPath);
    }

    static class DifferenceResult {
        BufferedImage diffImage;
        List<Rectangle> regions;
        int regionCount;

        DifferenceResult(BufferedImage img, List<Rectangle> regions, int count) {
            this.diffImage = img;
            this.regions = regions;
            this.regionCount = count;
        }
    }

    /**
     * 生成测试用找茬图片（带随机差异）
     */
    public static void generateTestImages(String basePath, String diffPath) throws IOException {
        int width = 400, height = 300;
        BufferedImage base = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        BufferedImage diff = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);

        Graphics2D g1 = base.createGraphics();
        Graphics2D g2 = diff.createGraphics();

        // 绘制相同背景
        g1.setColor(new Color(135, 206, 235)); // 天蓝
        g1.fillRect(0, 0, width, height);
        g2.setColor(new Color(135, 206, 235));
        g2.fillRect(0, 0, width, height);

        // 绘制相同的房子
        g1.setColor(new Color(139, 69, 19));
        g1.fillRect(150, 150, 100, 100);
        g2.setColor(new Color(139, 69, 19));
        g2.fillRect(150, 150, 100, 100);

        // 相同的屋顶
        int[] xPoints = {140, 200, 260};
        int[] yPoints = {150, 100, 150};
        g1.setColor(Color.RED);
        g1.fillPolygon(xPoints, yPoints, 3);
        g2.setColor(Color.RED);
        g2.fillPolygon(xPoints, yPoints, 3);

        // 相同的太阳
        g1.setColor(Color.YELLOW);
        g1.fillOval(50, 50, 60, 60);
        g2.setColor(Color.YELLOW);
        g2.fillOval(50, 50, 60, 60);

        // 差异1：图1有云朵，图2没有
        g1.setColor(Color.WHITE);
        g1.fillOval(280, 60, 80, 40);
        g1.fillOval(300, 50, 60, 40);

        // 差异2：图1窗户蓝色，图2窗户黄色
        g1.setColor(Color.CYAN);
        g1.fillRect(170, 170, 25, 25);
        g2.setColor(Color.YELLOW);
        g2.fillRect(170, 170, 25, 25);

        // 差异3：图1有树，图2树的位置不同
        g1.setColor(new Color(34, 139, 34));
        g1.fillOval(80, 180, 50, 80);
        g2.setColor(new Color(34, 139, 34));
        g2.fillOval(320, 180, 50, 80); // 树移到了右边

        g1.dispose();
        g2.dispose();

        ImageIO.write(base, "PNG", new File(basePath));
        ImageIO.write(diff, "PNG", new File(diffPath));
        System.out.println("测试图片已生成");
    }

    public static void main(String[] args) throws IOException {
        // 生成测试图片
        generateTestImages("/tmp/test_base.png", "/tmp/test_diff.png");

        // 执行找茬检测
        findDifferences("/tmp/test_base.png", "/tmp/test_diff.png", "/tmp/result.png");
    }
}

算法复杂度分析

扩展思考

1. 尺度不变性：感知哈希对缩放鲁棒，但对旋转敏感。可结合 Radon 变换或特征点匹配（SIFT/ORB）增强旋转鲁棒性。
2. 颜色感知哈希：标准 pHash 基于灰度，可分别在 Y、Cb、Cr 通道计算哈希以捕捉颜色差异。
3. 深度学习方案：使用 Siamese 网络或差异图分割网络（Change Detection）可获得更高的检测精度，但计算成本显著增加。

总结

找茬游戏的算法实现融合了信号处理（DCT）、图论（连通区域）和计算机视觉的基础技术。感知哈希提供了高效的”粗筛”能力，而像素级差异检测确保了定位精度。这种”由粗到精”的分层策略是计算机视觉领域的经典范式，也适用于图像去重、视频镜头检测等实际场景。