封面 《ジュエリー・ハーツ・アカデミア -We will wing wonder world-》
前言
因为我使用阿里云的 OSS 来保存每天在群里面看到的涩图，但是这里存在一个问题。有时候我会因为色图重复上传，这样难免会占据存储空间，虽然短时间看不多，但是就是让人不爽。因此写了一个简单的小软件来简单的排查重复的图片。
完整代码在 https://github.com/qxdn/image-sim
效果
技术选型
一个比较容易想到的方法是直接遍历每一张图，每张图之间计算相似度，但是这种方式的时间复杂度是O(N2)，而且图像相似度计算耗时长，当图片数量较大时耗时很长。经典的搜图引擎如 Yandex,SauceNAO 明显搜图速度很快，显然有更快的方案
还有一种方案是先将图片计算特征值，然后将特征值存入数据库中，当有图片需要计算时先计算该图片的特征值，然后对特征值进线相似度计算。如汉明距离、余弦相似度等
特征提取与相似度计算
一个比较容易能想到的特征提取以及相似度计算就是使用神经网络提取特征后，对特征向量求相似。不过考虑到我的图片重复的原因主要是由于重复上传，这里主要是图片的分辨率和完全重复导致的，考虑到量级也暂时用不上神经网络，采用哈希算法能够较快的开发和满足需求
常见的图像 hash 算法有 AHash、DHash 和 PHash
AHash
均值哈希算法 (Average Hash,AHash)，是一种基于平均值的哈希算法。其算法步骤如下所示
- 将图片缩放到 8*8 的尺寸
- 将图片进行灰度化
- 对灰度化后的图片进行平均值计算得到 avg
- 将灰度化图片中的每个像素与 avg 进行比较，大于 avg 的记为 1，小于 avg 的记为 0，拼接成长度为 64 的 01 字符串
Ahash 的优点如下
缺点如下
对应的 python 代码如下所示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def ahash(image_path: str):
img = cv2.imread(image_path)
img = cv2.resize(img, (8, 8))
img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
mean = np.mean(img)
temp = img.flatten()
hash_value = ""
for i in range(len(temp)):
if temp[i] > mean:
hash_value += "1"
else:
hash_value += "0"
return hash_value
|
测试图片，计算得到的 AHash 值为 0001110001111100000011100011101000110010010110010111001010110111
DHash
差异哈希算法 (Difference Hash,DHash)，是一种基于像素差值的哈希算法。其计算步骤如下所示
- 将图片缩放到 9*8 的尺寸
- 将图片转换为灰度图
- 对于每一行，比较相邻像素的值，如果左边像素小于右边像素值，则记录为 1，否则记录为 0
1
2
3
4
5
6
7
8
9
10
11
12
| def dhash(image_path:str):
img = cv2.imread(image_path)
img = cv2.resize(img,(9,8))
img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
hash_value = ""
for i in range(len(img)):
for j in range(len(img[i])-1):
if img[i][j] < img[i][j+1]:
hash_value += "1"
else:
hash_value += "0"
return hash_value
|
dHash 的优点如下
- 对图像的平移变化相对不敏感
- 保留了更多的结构信息，适用于检测图像的细微差别
dHash 的缺点如下
对于同样上述的测试图片，计算得到的 DHash 值为 0110100010111000111110001010101001101010101010011100101001001010
PHash
感知哈希算法 (Perceptual Hash,PHash)，是一种基于 DCT 变换的哈希算法。其计算步骤如下所示
- 将图片缩放到 32*32 的尺寸
- 将图片转换为灰度图
- 对图片进行 DCT 变换
- 取 DCT 变换后的左上角 8*8 的矩阵，计算矩阵的平均值
- 将矩阵中的每个值与平均值进行比较，大于平均值的记为 1，小于平均值的记为 0
pHash 的优点如下
- 更关注于图像的结构和纹理，对于旋转、缩放、轻微变形等变化具有较好的鲁棒性
- 适用于内容相似度判断，如查找相同内容的不同分辨率或格式的图片
pHash 的缺点如下
- 计算相对复杂，速度慢于 aHash 和 dHash
- 对于颜色变化敏感的图片处理效果可能不如预期
代码实现如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def phash(image_path:str,resize = 32):
img = cv2.imread(image_path)
img = cv2.resize(img,(resize,resize))
img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
img = cv2.dct(np.float32(img))
img = img[0:8,0:8]
mean = np.mean(img)
flatten = img.flatten()
hash_value = ""
for i in range(len(flatten)):
if flatten[i] > mean:
hash_value += "1"
else:
hash_value += "0"
return hash_value
|
对于上文中的测试图片，计算得到的 PHash 值为 1000001000010000000101100100100010100001010100101000000001000001
相似计算
对于哈希值的相似计算，最简单的一个方法就是使用汉明距离，其在数据库中也有之支持。
汉明距离是指两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如，1011101 和 1001001 之间的汉明距离是 2，具体如下所示。
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 |
对于两个数字的汉明距离计算可以使用如下代码实现
1
2
3
| def hamming_distance(hash1:int,hash2:int):
xor = hash1^hash2
return xor.bit_count()
|
对于大多数数据库都有 bit_count 函数，可以直接使用该函数计算汉明距离
对于 64 位哈希的相似度计算，可以使用如下代码实现
1
2
3
| def similarity(hash1:int,hash2:int):
distance = hamming_distance(hash1,hash2)
return 1 - distance/64
|
核心代码
刷新 OSS 文件 hash 值
主要流程为查询 OSS 文件，如果数据库中未含有或者 OSS 文件的修改时间大于数据库中的修改时间，则计算 OSS 文件的 hash 值，然后更新数据库中的 hash 值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
func ComputeSingle(object *model.OSSObject, client *oss.Client, db *gorm.DB) error {
dbImage := LoadImageFromDB(db, object.Key)
needSave := false
if dbImage == nil {
global.Logger.Info("Image not found with key:", object.Key)
needSave = true
} else {
global.Logger.Info("Image found with key:", object.Key)
if dbImage.LastModified.Before(object.LastModified) {
global.Logger.Infof("Image with key %v LastModified has changed need update, db time: %v, oss time: %v", object.Key, dbImage.LastModified, object.LastModified)
needSave = true
}
}
if needSave {
imageHash, err := ComputeOSSHash(object, client)
if err != nil {
global.Logger.Error("compute hash or image fail", err)
return err
}
err = db.Transaction(func(tx *gorm.DB) error {
dbImage := LoadImageFromDBWithLock(db, object.Key)
dbImage = CreateDBImage(dbImage, object, imageHash)
return SaveDBImage(dbImage, tx)
})
return err
}
return nil
}
|
查询相似图片
此处主要是使用 MySQL 的 bit_count 筛选图片，然后计算各个图片的相似度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| func main() {
config := global.ReadConfig()
global.InitGlobal()
db := global.Db
images := services.LoadAllImagesFromDB(db)
var queryResult []SimilarImage
for _, image := range *images {
result := services.LoadImagesByPHashDistance(db, image.PHash, config.Query.Distance)
for _, img := range *result {
if img.Key == image.Key {
continue
}
similar := util.ComputeSimilarity(image.PHash, img.PHash)
queryResult = append(queryResult, SimilarImage{
Key: image.Key,
Url: image.Url,
Other: img.Key,
OtherUrl: img.Url,
Similarity: similar,
})
}
}
global.Logger.Infof("Query finished find %v similar images", len(queryResult))
for _, result := range queryResult {
global.Logger.Info("Key:", result.Key, " , Url:", result.Url, " , Other:", result.Other, " , OtherUrl:", result.OtherUrl, " , Similarity:", result.Similarity)
}
}
|
1
2
3
4
5
6
7
8
| func LoadImagesByPHashDistance(db *gorm.DB, hash uint64, distance int) *[]dal.Image {
images := &[]dal.Image{}
result := db.Where("BIT_COUNT(p_hash ^ ?) < ?", hash, distance).Find(images)
if result.Error != nil {
panic(result.Error)
}
return images
}
|
效果
202410230115140.png
202410230115070.png
202410230115852.png
202410230115284.png
参考文献