引言
“找你妹”是一款风靡全球的找茬类游戏：两幅几乎完全相同的图片中隐藏着若干处细微差异，玩家需要在限定时间内找出所有不同点。从算法视角看，这是一个高效图像差异检测问题——既要求检测精度（不漏掉任何差异），又要求检测速度（满足实时性）。本文用Java实现找你妹差异检测引擎，核心讲解三种感知哈希算法（aHash、dHash、pHash）的原理与实现，以及基于汉明距离的快速差异筛选策略。
核心算法思路
1. 平均哈希（aHash）
将图像缩小为 8×8 的灰度图，计算所有像素的平均亮度值。每个像素若高于平均值记为1，否则记为0，生成64位哈希值。差异通过汉明距离衡量。
2. 差值哈希（dHash）
将图像缩小为 9×8 的灰度图，比较每一行相邻像素的亮度差异：若右侧像素更亮记为1，否则记为0。生成64位哈希值。差值哈希对亮度变化更敏感。
3. 感知哈希（pHash）
将图像缩小为 32×32 的灰度图，进行离散余弦变换（DCT），取左上角 8×8 的低频系数（排除直流分量），计算平均值并二值化。感知哈希对图像压缩和缩放具有更强的鲁棒性。
4. 差异区域定位
将两幅图像分割为若干个小块（如 16×16 像素），对每一块分别计算感知哈希，通过汉明距离快速筛选出差异块，再对差异块进行像素级精确比对。
Java实现
import java.awt.Graphics2D;
import java.awt.image.BufferedImage;
import java.util.*;
/**
* 找你妹差异检测引擎
* 核心算法：感知哈希(aHash/dHash/pHash)、汉明距离、分块比对
*/
public class SpotTheDifferenceEngine {
// 图像块结构
static class ImageBlock {
int x, y; // 块左上角坐标
int width, height; // 块尺寸
long aHash, dHash, pHash; // 三种哈希值
ImageBlock(int x, int y, int w, int h) {
this.x = x; this.y = y; this.width = w; this.height = h;
}
}
// 差异点
static class Difference {
int x, y;
double confidence; // 差异置信度
Difference(int x, int y, double conf) {
this.x = x; this.y = y; this.confidence = conf;
}
}
/**
* 核心算法1：平均哈希（aHash）
* 步骤：缩小→灰度化→计算均值→二值化
* 时间复杂度：O(w*h)，w,h为缩小后尺寸
*/
public static long computeAHash(BufferedImage img) {
// 缩小为 8x8
BufferedImage small = resizeAndGrayscale(img, 8, 8);
int[] pixels = new int[64];
int idx = 0;
long sum = 0;
for (int y = 0; y < 8; y++) {
for (int x = 0; x < 8; x++) {
int gray = small.getRGB(x, y) & 0xFF; // 灰度值
pixels[idx++] = gray;
sum += gray;
}
}
double avg = sum / 64.0;
long hash = 0;
for (int i = 0; i < 64; i++) {
if (pixels[i] > avg) {
hash |= (1L << i);
}
}
return hash;
}
/**
* 核心算法2：差值哈希（dHash）
* 步骤：缩小为 9x8→灰度化→比较每行相邻像素→生成64位哈希
* 对亮度渐变和边缘变化更敏感
*/
public static long computeDHash(BufferedImage img) {
BufferedImage small = resizeAndGrayscale(img, 9, 8);
long hash = 0;
int bitPos = 0;
for (int y = 0; y < 8; y++) {
for (int x = 0; x < 8; x++) {
int left = small.getRGB(x, y) & 0xFF;
int right = small.getRGB(x + 1, y) & 0xFF;
if (left > right) {
hash |= (1L << bitPos);
}
bitPos++;
}
}
return hash;
}
/**
* 核心算法3：感知哈希（pHash）
* 步骤：缩小为 32x32→灰度化→DCT变换→取低频系数→二值化
* 对图像压缩、缩放具有强鲁棒性
*/
public static long computePHash(BufferedImage img) {
BufferedImage small = resizeAndGrayscale(img, 32, 32);
double[][] matrix = new double[32][32];
// 转换为灰度矩阵
for (int y = 0; y < 32; y++) {
for (int x = 0; x < 32; x++) {
matrix[y][x] = small.getRGB(x, y) & 0xFF;
}
}
// 2D DCT变换
double[][] dct = applyDCT(matrix);
// 取左上角 8x8 低频系数（排除[0][0]直流分量）
double[] lowFreq = new double[64];
int idx = 0;
double sum = 0;
for (int y = 0; y < 8; y++) {
for (int x = 0; x < 8; x++) {
if (y == 0 && x == 0) continue; // 跳过直流分量
lowFreq[idx] = dct[y][x];
sum += dct[y][x];
idx++;
}
}
double avg = sum / 63.0; // 63个交流分量
long hash = 0;
for (int i = 0; i < 63; i++) {
if (lowFreq[i] > avg) {
hash |= (1L << i);
}
}
return hash;
}
// 二维DCT变换（简化实现，仅用于演示）
private static double[][] applyDCT(double[][] input) {
int N = input.length;
double[][] output = new double[N][N];
for (int u = 0; u < N; u++) {
for (int v = 0; v < N; v++) {
double sum = 0;
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
sum += input[x][y] *
Math.cos((2 * x + 1) * u * Math.PI / (2 * N)) *
Math.cos((2 * y + 1) * v * Math.PI / (2 * N));
}
}
double cu = (u == 0) ? 1 / Math.sqrt(2) : 1;
double cv = (v == 0) ? 1 / Math.sqrt(2) : 1;
output[u][v] = 2.0 / N * cu * cv * sum;
}
}
return output;
}
/**
* 核心算法4：汉明距离计算
* 计算两个64位哈希值不同位的数量
* 时间复杂度：O(1)（固定64位）
*/
public static int hammingDistance(long hash1, long hash2) {
long xor = hash1 ^ hash2;
int dist = 0;
while (xor != 0) {
dist += (xor & 1);
xor >>= 1;
}
return dist;
}
/**
* 核心算法5：分块差异检测
* 将图像分割为块，快速筛选差异区域，再精确比对
* 时间复杂度：O((W*wH)*B)，B为块数
*/
public static List<Difference> findDifferences(
BufferedImage img1, BufferedImage img2, int blockSize) {
int w = Math.min(img1.getWidth(), img2.getWidth());
int h = Math.min(img1.getHeight(), img2.getHeight());
List<Difference> differences = new ArrayList<>();
// 第一阶段：块级快速筛选（感知哈希）
List<ImageBlock> diffBlocks = new ArrayList<>();
for (int y = 0; y < h; y += blockSize) {
for (int x = 0; x < w; x += blockSize) {
int bw = Math.min(blockSize, w - x);
int bh = Math.min(blockSize, h - y);
BufferedImage block1 = img1.getSubimage(x, y, bw, bh);
BufferedImage block2 = img2.getSubimage(x, y, bw, bh);
long hash1 = computeDHash(block1);
long hash2 = computeDHash(block2);
int dist = hammingDistance(hash1, hash2);
// 汉明距离阈值：小于5认为相同，大于15认为明显不同
if (dist > 5) {
ImageBlock block = new ImageBlock(x, y, bw, bh);
block.dHash = hash1;
diffBlocks.add(block);
}
}
}
System.out.println("差异块数量：" + diffBlocks.size() + "/" +
((w / blockSize + 1) * (h / blockSize + 1)));
// 第二阶段：像素级精确比对（仅在差异块内进行）
for (ImageBlock block : diffBlocks) {
double maxDiff = 0;
int diffX = block.x, diffY = block.y;
for (int y = block.y; y < block.y + block.height && y < h; y++) {
for (int x = block.x; x < block.x + block.width && x < w; x++) {
int rgb1 = img1.getRGB(x, y);
int rgb2 = img2.getRGB(x, y);
// 计算像素差异（加权RGB）
double diff = pixelDifference(rgb1, rgb2);
if (diff > maxDiff) {
maxDiff = diff;
diffX = x;
diffY = y;
}
}
}
if (maxDiff > 30) { // 差异阈值
differences.add(new Difference(diffX, diffY, maxDiff / 255.0));
}
}
// 合并相近的差异点（去重）
return mergeNearbyDifferences(differences, blockSize / 2);
}
// 计算两个RGB像素的加权差异
private static double pixelDifference(int rgb1, int rgb2) {
int r1 = (rgb1 >> 16) & 0xFF, g1 = (rgb1 >> 8) & 0xFF, b1 = rgb1 & 0xFF;
int r2 = (rgb2 >> 16) & 0xFF, g2 = (rgb2 >> 8) & 0xFF, b2 = rgb2 & 0xFF;
// 使用感知亮度权重：0.299R + 0.587G + 0.114B
return Math.abs(0.299 * (r1 - r2) + 0.587 * (g1 - g2) + 0.114 * (b1 - b2));
}
// 合并距离相近的差异点
private static List<Difference> mergeNearbyDifferences(
List<Difference> diffs, int threshold) {
if (diffs.isEmpty()) return diffs;
boolean[] merged = new boolean[diffs.size()];
List<Difference> result = new ArrayList<>();
for (int i = 0; i < diffs.size(); i++) {
if (merged[i]) continue;
Difference base = diffs.get(i);
double sumX = base.x * base.confidence;
double sumY = base.y * base.confidence;
double weightSum = base.confidence;
int count = 1;
for (int j = i + 1; j < diffs.size(); j++) {
if (merged[j]) continue;
Difference other = diffs.get(j);
double dist = Math.sqrt(
Math.pow(base.x - other.x, 2) +
Math.pow(base.y - other.y, 2)
);
if (dist <= threshold) {
sumX += other.x * other.confidence;
sumY += other.y * other.confidence;
weightSum += other.confidence;
count++;
merged[j] = true;
}
}
if (count > 0) {
result.add(new Difference(
(int)(sumX / weightSum),
(int)(sumY / weightSum),
weightSum / count
));
}
}
return result;
}
// 辅助方法：缩放并灰度化图像
private static BufferedImage resizeAndGrayscale(BufferedImage src, int w, int h) {
BufferedImage dst = new BufferedImage(w, h, BufferedImage.TYPE_BYTE_GRAY);
Graphics2D g = dst.createGraphics();
g.drawImage(src.getScaledInstance(w, h, java.awt.Image.SCALE_SMOOTH), 0, 0, null);
g.dispose();
return dst;
}
/**
* 核心算法6：生成用于测试的"找你妹"图像对
* 创建两幅几乎相同的图像，在随机位置添加差异
*/
public static BufferedImage[] generateTestPair(int width, int height, int numDiffs) {
BufferedImage base = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
BufferedImage modified = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
Random rand = new Random(42);
// 填充基础图案（棋盘格）
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
int color = ((x / 20) + (y / 20)) % 2 == 0 ? 0xE0E0E0 : 0xC0C0C0;
base.setRGB(x, y, color);
modified.setRGB(x, y, color);
}
}
// 在modified上随机添加差异
for (int i = 0; i < numDiffs; i++) {
int cx = rand.nextInt(width - 20) + 10;
int cy = rand.nextInt(height - 20) + 10;
int r = rand.nextInt(5) + 3;
int diffColor = rand.nextBoolean() ? 0xFF0000 : 0x00FF00;
for (int dy = -r; dy <= r; dy++) {
for (int dx = -r; dx <= r; dx++) {
if (dx * dx + dy * dy <= r * r) {
int nx = cx + dx, ny = cy + dy;
if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
modified.setRGB(nx, ny, diffColor);
}
}
}
}
}
return new BufferedImage[]{base, modified};
}
public static void main(String[] args) {
System.out.println("=== 找你妹差异检测引擎 ===");
// 生成测试图像对
BufferedImage[] pair = generateTestPair(200, 200, 5);
BufferedImage img1 = pair[0];
BufferedImage img2 = pair[1];
System.out.println("图像尺寸：" + img1.getWidth() + "x" + img1.getHeight());
// 计算整图哈希
long hash1a = computeAHash(img1);
long hash2a = computeAHash(img2);
System.out.println("\naHash 汉明距离：" + hammingDistance(hash1a, hash2a));
long hash1d = computeDHash(img1);
long hash2d = computeDHash(img2);
System.out.println("dHash 汉明距离：" + hammingDistance(hash1d, hash2d));
// 分块差异检测
System.out.println("\n分块差异检测（块大小=20）：");
List<Difference> diffs = findDifferences(img1, img2, 20);
System.out.println("\n检测到的差异点：" + diffs.size());
for (Difference d : diffs) {
System.out.printf(" 位置(%d, %d), 置信度=%.2f%%n",
d.x, d.y, d.confidence * 100);
}
}
}
复杂度分析
| 算法模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| aHash计算 | O(64) = O(1) | O(1) |
| dHash计算 | O(72) = O(1) | O(1) |
| pHash/DCT | O(32² × 32²) = O(1M) | O(32²) |
| 汉明距离 | O(64) = O(1) | O(1) |
| 分块差异检测 | O(W×H) | O(W×H/B) |
总结
本文实现了找你妹游戏的完整差异检测引擎，通过三种感知哈希算法（aHash、dHash、pHash）实现快速图像特征提取，利用汉明距离进行高效比对，并通过”块级筛选+像素级精确比对”的两阶段策略兼顾速度与精度。该框架可扩展至图像查重、视频帧比对、医学影像差异分析等更广泛的领域。
