文章首发于：Java 实现图片类似度比拟 – 色彩散布法
0. 本文中实现的思路来自于以下博客：
类似图片搜寻的原理（二）
类似图片搜寻的原理
1. 如何判断两张图片的相似性有多少
本文的代码实现曾经上传到 github，须要的能够自行获取，地址：calculate-pic-looklike
想看具体版的，请看这篇文章：类似图片搜寻的原理。
太长不看的简略版如下：
人类比拟两张图片是否相似的时候，咱们其实会根据图片中图形的轮廓是否在脑海中曾经存在过进行联想，而后大脑主动帮咱们关联到看到的记忆上。
而对于计算机来说，判断两张图片的类似度靠的是“感知哈希算法”。它会给每一张图片生成一个“指纹”，而后比拟两张图片的指纹，后果越靠近就阐明图片越类似。
怎么比拟两个指纹的类似度，下面的文章中提到有：皮尔逊相关系数或者余弦类似度
Pearson 相关系数（Pearson Correlation Coefficient）是用来掂量两个数据汇合是否在一条线下面，它用来掂量定距变量间的线性关系。
pearson 相关系数掂量的是线性相关关系。若 r =0，只能说 x 与 y 之间无线性相关关系，不能说无相干关系。相关系数的绝对值越大，相关性越强：相关系数越靠近于 1 或 -1，相关度越强，相关系数越靠近于 0，相关度越弱。
通常状况下通过以下取值范畴判断变量的相干强度：
相关系数 0.8-1.0 极强相干0.6-0.8 强相干
0.4-0.6 中等水平相干
0.2-0.4 弱相干
0.0-0.2 极弱相干或无相干
对于 x,y 之间的相关系数 r：
当 r 大于 0 小于 1 时示意 x 和 y 正相干关系
当 r 大于 - 1 小于 0 时示意 x 和 y 负相关关系
当 r = 1 时示意 x 和 y 齐全正相干，r=- 1 示意 x 和 y 齐全负相关
当 r = 0 时示意 x 和 y 不相干
所以，比拟两个图片的类似度在于得出图片指纹（数据汇合），用这两个数据汇合代入皮尔逊相关系数就能够失去。
那么怎么从图片失去图片指纹呢？
1.1 图片到图片指纹
咱们都晓得任何图片在电子屏幕上显示都由光学三原色形成（红绿蓝），在计算机中咱们对三原色用 RGB 来进行示意，比方：
(255 ,180, 0) 示意的色彩是：
那么咱们能够通过代码获取到一张图片的所有的像素点，而后把每个像素点进行拆分都能够失去 RGB 数值，把这些 RGB 数值计数，那么就会失去：
(0,0,0) 呈现次数 10000 次
(0,0,1) 呈现次数 25 次
...
(0,0,1) 呈现次数 90 次把这些用次数收集起来，失去汇合 {10000,25,...,90} 就是 图片指纹。
别离对两个图片都这样操作，而后失去这个数据汇合，再通过下面说到的皮尔逊相关系数或者余弦类似度 进行比照，就晓得这两张图片的类似度了。
然而如果咱们对 R,G,B 都采纳 0 -255 的范畴进行比拟，那么产生的可能性就有：$256^{3}=16777216$
为了咱们简化计算，个别采纳的是这样的形式：将 0～255 分成四个区：0～63 为第 0 区，64～127 为第 1 区，128～191 为第 2 区，192～255 为第 3 区。这意味着红绿蓝别离有 4 个区，总共能够形成 64 种组合（4 的 3 次方）。
如下图所示：
将表中最初一栏提取进去，组成一个 64 维向量(7414, 230, 0, 0, 8, …, 109, 0, 0, 3415, 53929)。这个向量就是这张图片的特征值或者叫 ” 指纹 ”。
而后代入皮尔逊相关系数进行计算
2. 代码实现局部
对原理咱们理解时候，通过 Java 代码实现有 X 局部：
- 获取一张图片所有的像素点，并且获取到这个像素点的 RGB 数值
- 对所有的像素点进行统计，失去图片指纹
- 代入皮尔逊相关系数
2.1 获取一张图片的所有像素点以及 RGB 数值
BufferedImage bimg = ImageIO.read(new File(path));
for(int i = 0; i < bimg.getWidth(); i++){for(int j = 0; j < bimg.getHeight(); j++){Color color = new Color( bimg.getRGB(i, j));
int r = color.getRed();
int g = color.getGreen();
int b = color.getBlue();}
}
2.2 对像素点统计，失去图片指纹
这一步就比拟要害了，咱们拿到像素点之后，察看下图标黄的这三列，能够看到红绿蓝组成的数字正好是从001～333，合乎四进制的法则。
那就意味着咱们在上面对像素点进行遍历的时候，计算一个像素点属于哪个区（0-3），就把值放入四进制的容量大小的数组。
所以咱们在对图片进行遍历前，创立一个 $ 分区数 ^{3}=List 容量数 $ 的汇合，而后对汇合进行初始化。
// 比拟等级，也就是 256 个像素点分区后的区块数
public static int compareLevel = 4;
public static List<Double> getPicArrayData(String path) throws IOException {BufferedImage image = ImageIO.read(new File(path));
// 初始化汇合
final List<Double> picFingerprint = new ArrayList<>(compareLevel*compareLevel*compareLevel);
IntStream.range(0, compareLevel*compareLevel*compareLevel).forEach(i->{picFingerprint.add(i, 0.0);
});
// 遍历像素点
for(int i = 0; i < image.getWidth(); i++){for(int j = 0; j < image.getHeight(); j++){Color color = new Color(image.getRGB(i, j));
// 对像素点进行计算
putIntoFingerprintList(picFingerprint, color.getRed(), color.getGreen(), color.getBlue());
}
}
return picFingerprint;
}
/**
* 放入像素的三原色进行计算，失去 List 的地位
* @param picFingerprintList picFingerprintList
* @param r r
* @param g g
* @param b b
* @return
*/
public static List<Double> putIntoFingerprintList(List<Double> picFingerprintList, int r, int g, int b){final Integer index = getBlockLocation(r) + getBlockLocation(g) + getBlockLocation(b);
final Double origin = picFingerprintList.get(index);
picFingerprintList.set(index, origin + 1);
return picFingerprintList;
}
/**
* 计算 以后原色应该分在哪个区块，并转成 10 进制
* @param colorPoint colorPoint
* @return
*/
public static Integer getBlockLocation(int colorPoint){return IntStream.range(0, compareLevel)
// 计算分在哪个区块
.filter(i -> {int areaStart = (256 / compareLevel) * i;
int areaEnd = (256 / compareLevel) * (i + 1) - 1;
return colorPoint >= areaStart && colorPoint <= areaEnd;
})
// 转 10 进制
.map(location -> Integer.parseInt(location+"", compareLevel))
.findFirst()
.orElseThrow() ;}其中代码中 compareLevel 就是 256 的因数，可能应用的数字有：1,2,4,8,16,32,64,128,256。每个数字代表的是 256 个像素会被均分成多少份。
在办法 putIntoFingerprintList 中，别离对这个像素点的 R G B 原色进行计算，计算过程便是办法getBlockLocation，计算的原理如下:
2.2.1 获取应该放入区块的地位
假如原色的值为：x，区块数为：n
第一个区块的范畴为：
第二个区块的范畴为：
那么第 i 次的区块范畴为：
那么：
此时这个 i 就是 x 应该放入区块的地位。
这里举个例子：
假如原色的值为 235
那么带入下面的公式：
0～63 为第 0 区，64～127 为第 1 区，128～191 为第 2 区，192～255 为第 3 区
那么 235 属于第 3 区
转变为代码的话就是：
public static Integer getBlockLocation(int colorPoint){return IntStream.range(0, compareLevel)
// 计算分在哪个区块
.filter(i -> {int areaStart = (256 / compareLevel) * i;
int areaEnd = (256 / compareLevel) * (i + 1) - 1;
return colorPoint >= areaStart && colorPoint <= areaEnd;
})
// 转 10 进制
.map(location -> Integer.parseInt(location+"", compareLevel))
.findFirst()
.orElseThrow() ;}在这个办法中：return colorPoint >= areaStart && colorPoint <= areaEnd;
这一行代码代表的意思就是：
如果：且
那么为 true，示意合乎咱们要的数据
最初放入 List 中，此时失去的这个 List 就是图片指纹
2.3 代入皮尔逊相关系数
这一步网上曾经有很多 Java 实现的代码，就不反复造轮子了。贴一下网上找到的代码：
package run.runnable.calculatepiclooklike.utils;
import java.util.ArrayList;
import java.util.List;
/**
* 皮尔逊相关系数
*/
public class PearsonDemo {public static Double getPearsonBydim(List<Double> ratingOne, List<Double> ratingTwo) {
try {if(ratingOne.size() != ratingTwo.size()) {// 两个变量的观测值是成对的，每对观测值之间互相独立。if(ratingOne.size() > ratingTwo.size()) {// 保留小的解决大
List<Double> temp = ratingOne;
ratingOne = new ArrayList<>();
for(int i=0;i<ratingTwo.size();i++) {ratingOne.add(temp.get(i));
}
}else {
List<Double> temp = ratingTwo;
ratingTwo = new ArrayList<>();
for(int i=0;i<ratingOne.size();i++) {ratingTwo.add(temp.get(i));
}
}
}
double sim = 0D;// 最初的皮尔逊相关度系数
double commonItemsLen = ratingOne.size();// 操作数的个数
double oneSum = 0D;// 第一个相干数的和
double twoSum = 0D;// 第二个相干数的和
double oneSqSum = 0D;// 第一个相干数的平方和
double twoSqSum = 0D;// 第二个相干数的平方和
double oneTwoSum = 0D;// 两个相干数的乘积和
for(int i=0;i<ratingOne.size();i++) {// 计算
double oneTemp = ratingOne.get(i);
double twoTemp = ratingTwo.get(i);
// 求和
oneSum += oneTemp;
twoSum += twoTemp;
oneSqSum += Math.pow(oneTemp, 2);
twoSqSum += Math.pow(twoTemp, 2);
oneTwoSum += oneTemp*twoTemp;
}
double num = (commonItemsLen*oneTwoSum) - (oneSum*twoSum);
double den = Math.sqrt((commonItemsLen * oneSqSum - Math.pow(oneSum, 2)) * (commonItemsLen * twoSqSum - Math.pow(twoSum, 2)));
sim = (den == 0) ? 1 : num / den;
return sim;
} catch (Exception e) {return null;}
}
public static double getPearsonCorrelationScore(List<Double> x, List<Double> y) {if (x.size() != y.size())
throw new RuntimeException("数据不正确！");
double[] xData = new double[x.size()];
double[] yData = new double[x.size()];
for (int i = 0; i < x.size(); i++) {xData[i] = x.get(i);
yData[i] = y.get(i);
}
return getPearsonCorrelationScore(xData,yData);
}
public static double getPearsonCorrelationScore(double[] xData, double[] yData) {if (xData.length != yData.length)
throw new RuntimeException("数据不正确！");
double xMeans;
double yMeans;
double numerator = 0;// 求解皮尔逊的分子
double denominator = 0;// 求解皮尔逊系数的分母
double result = 0;
// 拿到两个数据的平均值
xMeans = getMeans(xData);
yMeans = getMeans(yData);
// 计算皮尔逊系数的分子
numerator = generateNumerator(xData, xMeans, yData, yMeans);
// 计算皮尔逊系数的分母
denominator = generateDenomiator(xData, xMeans, yData, yMeans);
// 计算皮尔逊系数
result = numerator / denominator;
return result;
}
/**
* 计算分子
*
* @param xData
* @param xMeans
* @param yData
* @param yMeans
* @return
*/
private static double generateNumerator(double[] xData, double xMeans, double[] yData, double yMeans) {
double numerator = 0.0;
for (int i = 0; i < xData.length; i++) {numerator += (xData[i] - xMeans) * (yData[i] - yMeans);
}
return numerator;
}
/**
* 生成分母
*
* @param yMeans
* @param yData
* @param xMeans
* @param xData
* @return 分母
*/
private static double generateDenomiator(double[] xData, double xMeans, double[] yData, double yMeans) {
double xSum = 0.0;
for (int i = 0; i < xData.length; i++) {xSum += (xData[i] - xMeans) * (xData[i] - xMeans);
}
double ySum = 0.0;
for (int i = 0; i < yData.length; i++) {ySum += (yData[i] - yMeans) * (yData[i] - yMeans);
}
return Math.sqrt(xSum) * Math.sqrt(ySum);
}
/**
* 依据给定的数据集进行平均值计算
*
* @param
* @return 给定数据集的平均值
*/
private static double getMeans(double[] datas) {
double sum = 0.0;
for (int i = 0; i < datas.length; i++) {sum += datas[i];
}
return sum / datas.length;
}
}2.4 实现成果
计算得出的后果咱们能够参考这个：
通常状况下通过以下取值范畴判断变量的相干强度：
相关系数 0.8-1.0 极强相干
0.6-0.8 强相干
0.4-0.6 中等水平相干
0.2-0.4 弱相干
0.0-0.2 极弱相干或无相干
不类似图片计算
应用图片 1，如下：
图片 2，如下：
compareLevel 设置为 4，进行类似度比拟，失去的值为：0.36759562778230137
类似图片计算
应用图片 3，如下：
应用图片 4，如下：
compareLevel 设置为 16，进行类似度比拟，失去的值为：0.787010979764144
代码实现曾经上传到 github，须要的能够自行获取，地址：calculate-pic-looklike
2.5 能不能不用 list，而是用 Map 进行实现
在实现了上述的内容之后，这是我脑海中冒出来的一个想法。
在 Map 中这样进行寄存 Map< 像素计算失去的下标，总计 >
实现后发现是不行的，因为一张图片外面常常不会存在所有色彩像素点，如果不存在这个像素点，那么 Map 中的 key 是不残缺的，那么失去的这个图片指纹也是不残缺的。
比方身份证：
比方要有 地址码 + 出生日期码 +(程序及性别码)+ 校验和 才组成一个残缺的身份证
而应用 Map 的实现就相当于拿取的身份证是 地址码 +(程序及性别码)+ 校验和，缺失了其中一部分。
附上 Map 局部的实现代码：
public static List<Double> getPicArrayDataByMap(String path) throws IOException {BufferedImage bimg = ImageIO.read(new File(path));
final Map<Integer, Integer> picFingerprintMap = new HashMap<>();
for(int i = 0; i < bimg.getWidth(); i++){for(int j = 0; j < bimg.getHeight(); j++){
// 输入一列数据比对
Color color = new Color(bimg.getRGB(i, j));
int r = color.getRed();
int g = color.getGreen();
int b = color.getBlue();
putIntoFingerprintMap(picFingerprintMap, r, g, b);
}
}
final List<Integer> keys = picFingerprintMap.keySet().stream().sorted().collect(Collectors.toList());
final ArrayList<Double> picFingerprintList = new ArrayList<>(keys.size());
keys.forEach(key->{picFingerprintList.add(Double.valueOf(picFingerprintMap.get(key)));
});
return picFingerprintList;
}
public static void putIntoFingerprintMap(Map<Integer, Integer> picFingerprintMap, int r, int g, int b){final Integer picFingerprint = getBlockLocation(r) + getBlockLocation(g) + getBlockLocation(b);
Integer value = picFingerprintMap.containsKey(Integer.valueOf(picFingerprint)) ? picFingerprintMap.get(Integer.valueOf(picFingerprint)) + 1 : 1;
picFingerprintMap.put(Integer.valueOf(picFingerprint), value);
}
3. 博客中信息的起源
类似图片搜寻的原理（二）
类似图片搜寻的原理
协同过滤算法