每日算法 — 使用java实现找不同：图像差异检测与感知哈希算法

找不同是深受各年龄段喜爱的经典益智游戏，要求玩家在两幅高度相似的图片中找出细微差异。从算法角度看，找不同问题本质上是图像差异检测（Image Difference Detection），涉及像素级比对、特征提取和相似度计算等多个计算机视觉基础课题。本文将使用Java实现一套多层级的图像差异检测系统，涵盖暴力像素比对、感知哈希快速筛选和结构化差异定位三种核心策略。

问题建模与算法策略

图像差异检测面临的核心挑战在于：两幅图片可能存在轻微的亮度变化、压缩噪声或位置偏移，导致直接像素相减会产生大量伪差异。因此，我们需要设计一个分层检测框架：

1. 粗筛层：使用感知哈希（Perceptual Hash）快速判断图片整体相似度，若差异过大则直接报告
2. 精检层：对像素矩阵进行差分运算，结合阈值过滤噪声
3. 聚类层：将离散差异像素聚合成连通区域，输出结构化差异位置

感知哈希算法原理

感知哈希不同于密码学哈希（如MD5/SHA），它的设计目标是：若两幅图片看起来相似，则哈希值的汉明距离（Hamming Distance）较小。最常用的平均哈希（aHash）步骤如下：

1. 将图片缩放到8×8像素（共64个像素）
2. 转换为灰度图
3. 计算所有像素的平均亮度
4. 每个像素与平均值比较，大于平均值为1，否则为0
5. 将64个比特组合成64位哈希值

两幅图片的相似度可通过汉明距离衡量：距离越小，图片越相似。

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

/**
 * 找不同：图像差异检测系统
 * 支持像素级比对、感知哈希快速筛选、连通区域聚类
 */
public class SpotTheDifference {

    // 差异像素的最小连通块面积，过滤噪声
    private static final int MIN_CLUSTER_SIZE = 8;
    // 像素差异阈值（RGB差值平方和）
    private static final int COLOR_DIFF_THRESHOLD = 1200;
    // 感知哈希汉明距离阈值
    private static final int HASH_DISTANCE_THRESHOLD = 10;

    /**
     * 计算平均感知哈希（aHash）
     * @param image 输入图像
     * @return 64位哈希值
     */
    public long computeAverageHash(BufferedImage image) {
        // 1. 缩放为8x8
        BufferedImage resized = new BufferedImage(8, 8, BufferedImage.TYPE_BYTE_GRAY);
        Graphics2D g = resized.createGraphics();
        g.drawImage(image.getScaledInstance(8, 8, Image.SCALE_SMOOTH), 0, 0, null);
        g.dispose();

        // 2. 计算平均亮度
        int sum = 0;
        int[] pixels = new int[64];
        for (int y = 0; y < 8; y++) {
            for (int x = 0; x < 8; x++) {
                int gray = resized.getRGB(x, y) & 0xFF;
                pixels[y * 8 + x] = gray;
                sum += gray;
            }
        }
        int avg = sum / 64;

        // 3. 生成哈希
        long hash = 0;
        for (int i = 0; i < 64; i++) {
            if (pixels[i] >= avg) {
                hash |= (1L << i);
            }
        }
        return hash;
    }

    /**
     * 计算两个64位哈希的汉明距离
     */
    public int hammingDistance(long hash1, long hash2) {
        long xor = hash1 ^ hash2;
        return Long.bitCount(xor);
    }

    /**
     * 像素级差异检测
     * @return 差异像素的坐标列表
     */
    public List<Point> pixelDiff(BufferedImage img1, BufferedImage img2) {
        List<Point> diffPoints = new ArrayList<>();

        int width = Math.min(img1.getWidth(), img2.getWidth());
        int height = Math.min(img1.getHeight(), img2.getHeight());

        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, g1 = (rgb1 >> 8) & 0xFF, b1 = rgb1 & 0xFF;
                int r2 = (rgb2 >> 16) & 0xFF, g2 = (rgb2 >> 8) & 0xFF, b2 = rgb2 & 0xFF;

                int diff = (r1 - r2) * (r1 - r2) + (g1 - g2) * (g1 - g2) + (b1 - b2) * (b1 - b2);
                if (diff > COLOR_DIFF_THRESHOLD) {
                    diffPoints.add(new Point(x, y));
                }
            }
        }
        return diffPoints;
    }

    /**
     * 使用BFS将差异像素聚类为连通区域
     * @return 每个差异区域的边界矩形列表
     */
    public List<Rectangle> clusterDiffRegions(List<Point> diffPoints, int imageWidth, int imageHeight) {
        if (diffPoints.isEmpty()) return Collections.emptyList();

        boolean[][] visited = new boolean[imageHeight][imageWidth];
        for (Point p : diffPoints) {
            if (p.y >= 0 && p.y < imageHeight && p.x >= 0 && p.x < imageWidth) {
                visited[p.y][p.x] = true;
            }
        }

        List<Rectangle> regions = new ArrayList<>();
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};

        for (Point start : diffPoints) {
            if (!visited[start.y][start.x]) continue;

            Queue<Point> queue = new LinkedList<>();
            queue.offer(start);
            visited[start.y][start.x] = false;

            int minX = start.x, maxX = start.x;
            int minY = start.y, maxY = start.y;
            int count = 0;

            while (!queue.isEmpty()) {
                Point cur = queue.poll();
                count++;
                minX = Math.min(minX, cur.x);
                maxX = Math.max(maxX, cur.x);
                minY = Math.min(minY, cur.y);
                maxY = Math.max(maxY, cur.y);

                for (int[] d : dirs) {
                    int nx = cur.x + d[0], ny = cur.y + d[1];
                    if (nx >= 0 && nx < imageWidth && ny >= 0 && ny < imageHeight && visited[ny][nx]) {
                        visited[ny][nx] = false;
                        queue.offer(new Point(nx, ny));
                    }
                }
            }

            if (count >= MIN_CLUSTER_SIZE) {
                regions.add(new Rectangle(minX, minY, maxX - minX + 1, maxY - minY + 1));
            }
        }
        return regions;
    }

    /**
     * 完整的找不同分析流程
     */
    public DiffReport analyze(BufferedImage img1, BufferedImage img2) {
        DiffReport report = new DiffReport();

        // 步骤1：感知哈希粗筛
        long hash1 = computeAverageHash(img1);
        long hash2 = computeAverageHash(img2);
        report.hashDistance = hammingDistance(hash1, hash2);
        report.similar = report.hashDistance <= HASH_DISTANCE_THRESHOLD;

        if (!report.similar) {
            report.message = "图片整体差异过大，可能不是同一组找不同图片";
            return report;
        }

        // 步骤2：像素级差异检测
        report.diffPoints = pixelDiff(img1, img2);

        // 步骤3：连通区域聚类
        int w = Math.min(img1.getWidth(), img2.getWidth());
        int h = Math.min(img1.getHeight(), img2.getHeight());
        report.regions = clusterDiffRegions(report.diffPoints, w, h);

        report.message = String.format("检测到 %d 个差异区域，共 %d 个差异像素，哈希距离=%d",
                report.regions.size(), report.diffPoints.size(), report.hashDistance);
        return report;
    }

    /** 差异检测报告 */
    static class DiffReport {
        boolean similar;           // 是否足够相似
        int hashDistance;          // 汉明距离
        List<Point> diffPoints;    // 差异像素点
        List<Rectangle> regions;   // 差异区域
        String message;            // 描述信息
    }

    /** 生成差异可视化图像 */
    public BufferedImage createDiffVisualization(BufferedImage img1, BufferedImage img2,
                                                  List<Rectangle> regions) {
        int w = Math.min(img1.getWidth(), img2.getWidth());
        int h = Math.min(img1.getHeight(), img2.getHeight());
        BufferedImage result = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
        Graphics2D g = result.createGraphics();
        g.drawImage(img2, 0, 0, null);

        // 用红色半透明框标记差异区域
        g.setColor(new Color(255, 0, 0, 128));
        g.setStroke(new BasicStroke(3));
        for (Rectangle r : regions) {
            g.drawRect(r.x, r.y, r.width, r.height);
        }
        g.dispose();
        return result;
    }

    public static void main(String[] args) throws IOException {
        SpotTheDifference std = new SpotTheDifference();

        // 示例：生成两幅测试图（实际使用时替换为真实图片路径）
        BufferedImage img1 = generateTestImage(400, 300, false);
        BufferedImage img2 = generateTestImage(400, 300, true);

        System.out.println("=== 找不同图像差异检测系统 ===");
        DiffReport report = std.analyze(img1, img2);
        System.out.println(report.message);

        if (report.similar && !report.regions.isEmpty()) {
            System.out.println("差异区域详情:");
            for (int i = 0; i < report.regions.size(); i++) {
                Rectangle r = report.regions.get(i);
                System.out.printf("  区域 %d: [%d, %d, %d, %d]\n", i+1, r.x, r.y, r.width, r.height);
            }

            BufferedImage vis = std.createDiffVisualization(img1, img2, report.regions);
            ImageIO.write(vis, "png", new File("diff_result.png"));
            System.out.println("差异可视化已保存至 diff_result.png");
        }
    }

    /** 生成测试图：第二幅图会随机添加几个差异块 */
    static BufferedImage generateTestImage(int w, int h, boolean withDiff) {
        BufferedImage img = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
        Graphics2D g = img.createGraphics();
        g.setColor(new Color(240, 240, 240));
        g.fillRect(0, 0, w, h);

        // 绘制基础图案
        Random rand = new Random(42);
        for (int i = 0; i < 20; i++) {
            g.setColor(new Color(rand.nextInt(256), rand.nextInt(256), rand.nextInt(256)));
            g.fillOval(rand.nextInt(w-50), rand.nextInt(h-50), 40, 40);
        }

        if (withDiff) {
            // 添加3个差异矩形
            Random diffRand = new Random(99);
            for (int i = 0; i < 3; i++) {
                g.setColor(new Color(diffRand.nextInt(256), diffRand.nextInt(256), diffRand.nextInt(256)));
                g.fillRect(50 + i * 120, 100 + i * 40, 60, 60);
            }
        }
        g.dispose();
        return img;
    }
}

感知哈希的进阶变体

除了平均哈希（aHash），实际工程中还常用以下两种感知哈希：

差值哈希（dHash）：缩放为9×8后，每行相邻像素比较生成比特。对图像梯度变化更敏感，抗亮度干扰能力更强。

感知哈希（pHash）：使用离散余弦变换（DCT）提取低频成分，保留更多图像结构信息。虽然计算量更大，但对缩放、对比度变化的鲁棒性最优。

对于找不同游戏，aHash已能满足粗筛需求；若需更高精度，可升级为dHash或pHash。

算法复杂度分析

其中 W、H 为图像宽高，D 为差异像素数量。

工程实践要点

在实际部署找不同检测系统时，还需注意以下几点：

1. 预处理对齐：若两幅图存在微小位移，需先进行图像配准（Image Registration），否则像素差分会 everywhere
2. 多尺度检测：对高分辨率图片，可先下采样进行粗定位，再在原图精细检测
3. 颜色空间选择：Lab颜色空间的欧氏距离比RGB更符合人眼感知，可降低亮度变化的误报
4. 形态学后处理：对差异掩膜进行开运算/闭运算，可消除孤立噪点、平滑区域边界

通过本项目的实现，读者可以系统掌握图像差异检测的完整流程：从感知哈希的快速粗筛，到像素级精确定位，再到连通区域聚类的结构化输出。这些技术不仅适用于找不同游戏，也是图像比对、视觉回归测试和视频内容审核等领域的核心基础。