V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
laoooo
V2EX  ›  问与答

需要一个高性能的图片相似度计算方案

  •  
  •   laoooo · 2023-03-31 11:56:20 +08:00 · 2893 次点击
    这是一个创建于 582 天前的主题,其中的信息可能已经有所发展或是发生改变。
    需求如下:

    1. 我有一个文件夹,里面有九千多张大小不一的图片,我需要对每张图进行相似度计算。
    2. 我希望通过我给定一个阈值,计算哪些图的相似度大于此阈值,复制至 result 目录中以“基准图”文件名命名的文件夹中。
    3. 高性能运行,多线程 /其他方案。要求计算一万张图片的耗时在一分钟左右。
    4. 要求以 Python 实现

    尝试了通过多线程计算哈希的方式来实现,效果还不错,但是一万张图的耗时在 3000 秒左右。求更高效的方案。
    20 条回复    2023-03-31 19:26:56 +08:00
    kop1989smurf
        1
    kop1989smurf  
       2023-03-31 11:57:55 +08:00
    一万张图的总大小是多大?
    laoooo
        2
    laoooo  
    OP
       2023-03-31 11:59:11 +08:00
    @kop1989smurf 40MB 左右,都是小图,分辨率在 128*128 的样子
    frankmdong
        3
    frankmdong  
       2023-03-31 12:56:58 +08:00
    首先要定义相似度具体是怎么计算,如果是单纯的比较相同位置的像素颜色是否相同,那可以多线程跑 compute shader ,在 gpu 对比两张图片对应的像素是否相同。可以参考 https://zhuanlan.zhihu.com/p/392448858 这篇文章中提到的资源优化工具,但是一分钟内几乎不可能跑完一万张图。
    oylinv
        4
    oylinv  
       2023-03-31 13:19:39 +08:00 via Android
    qq565425677
        5
    qq565425677  
       2023-03-31 13:39:44 +08:00
    我提供一个思路,不过具体我也不是太清楚

    有没有可能计算图片的奇异值分解,128*128 应该很快,然后基于奇异值定义距离来判断
    kzzhr
        6
    kzzhr  
       2023-03-31 13:44:50 +08:00
    我把这个问题丢给了 GPT ,以下是他的回答(还给了个代码,太长了不贴了。。。)

    要实现一个高性能的图片相似度计算方案,可以使用以下方法:

    1. 使用深度学习模型:使用预训练的深度学习模型,如 VGG, ResNet 等,可以更高效地提取图像特征。这些特征可以用于计算相似度。
    2. 特征向量降维:使用 PCA 或 t-SNE 等方法对特征向量进行降维,这样可以减少计算量,提高相似度计算速度。
    3. 近似最近邻搜索:对于相似度计算,可以使用近似最近邻搜索( Approximate Nearest Neighbors ,ANN )算法,如 Annoy 、Faiss 等库。它们可以在保持搜索质量的同时大大提高搜索速度。
    4. 多线程 /多进程:使用 Python 的 multiprocessing 或 concurrent.futures 模块来实现多线程 /多进程并行计算。
    kop1989smurf
        7
    kop1989smurf  
       2023-03-31 13:50:45 +08:00
    @laoooo #2 40MB ,一万张图,“基准图”有几张?也就是需要支持几个分组?
    需要抗翻转、裁切、偏移么?相似度的阈值大概是多少?

    如果需要抗偏移,感觉 1 分钟基本上做不到。
    horizon
        8
    horizon  
       2023-03-31 13:56:44 +08:00
    准备开始学深度学习了。。
    Donahue
        9
    Donahue  
       2023-03-31 14:19:45 +08:00
    可以问问 chatGPT
    NoOneNoBody
        10
    NoOneNoBody  
       2023-03-31 15:51:13 +08:00   ❤️ 2
    小图很快的,不需要 3000s ,但 1m 又基本不行
    不知道你的参照有多少,我 1000 vs 1000 ,5~10MB/pic ,也就 30 分钟内
    如果参照已经缓存了计算值,时间减半,小图(<1MB/pic),时间减 2/3

    方案 1. pyvips
    def viMse(vim, refvim)->float:
    '''计算 MSE 差异值,vim/refvim 都是 pyvips.Image 类型'''
    return ((vim - refvim) ** 2).avg()
    然后你按 mse 比较,网上有
    opencv 也有 mse 计算,但比 pyvips 慢

    方案 2 pyvips|opencv
    有些图片字节数相同或极度接近,但 md5/crc32 不同,它们可能只是 exif 或者文件头不同,图片内容是完全相同的
    可以用
    np.isclose((vim1-vim2).max(), 0, rtol=1e-9)

    cvim1.shape==cvim2.shape and not (numpy.bitwise_xor(cvim1, cvim2).any())
    vim 为 pyvips.Image 格式,cvim 为 opencv/numpy 格式,vips 较快且耗内存小,但大图有可能有未知错误,全自动的话 opencv 在保证内存足够的情况下比较保险

    方案 3 opencv.imgHash
    target 和 refer 分别计算 imgHash ,opencv 的 imgHash 有七八种,阙值是自定的,但网上有参考,自己选择

    无论哪种方案,应该做预匹配,不然就是 10000 * 10000 ,计算量大
    预匹配就是从字节、文件名相似、exif 日期时间一致,长宽比……这些很少计算能快速排除“完全不可能相似”
    如果很难做预匹配,例如上述参数都没有规律,那就只能硬着头皮按组合双循环计算了

    还有其他方案,但此题好像不适用,我主要目标是找有没有裁切水印把图变小了,和你需求略有不同

    PS: 如果 refer 经常使用的话,建议把上述计算的中间值保存,以后使用跳过计算,省时间,我是入库的
    NoOneNoBody
        11
    NoOneNoBody  
       2023-03-31 15:57:31 +08:00
    PS: 上述时间是 intel 12700 使用 16 个并发(因为我要留 CPU 做其他事情,用尽的话其他 app 会没响应,无奈)
    orangie
        12
    orangie  
       2023-03-31 16:31:39 +08:00
    插一句,python 的多线程还是单核性能,不能用来并行、提高计算速度,只能用来做异步、并发。
    faithid
        13
    faithid  
       2023-03-31 16:33:16 +08:00   ❤️ 1
    用深度学习模型提取 embedding ,用 milvus 计算相似度
    NoOneNoBody
        14
    NoOneNoBody  
       2023-03-31 16:46:45 +08:00
    再补充一个经验,做图片比较,耗时最大是生成上述各种中间值,因为不仅计算,还有 IO
    但如果已经有中间值,并发计算是很快的,如 imgHash ,千万对(就是两张)并发计算只是几分钟( i7 12700 16 并发)
    另一个好处是“离线”,不需要挂载 refer 图片所在硬盘就能比较
    这就是我把这些中间值入库的原因
    qiayue
        15
    qiayue  
       2023-03-31 16:53:00 +08:00
    基于 #13 @faithid 的回答,我补充下,使用 OpenAI 的 https://github.com/openai/CLIP 为每一张图片计算向量,之后存储到文本文件里。
    再写个程序,把所有图片的向量载入到内存中,循环计算任意一张图片的向量与其它图片的向量的距离,欧几里得距离( Euclidean distance )和余弦距离( cosine distance )都行,对于所得到的距离从小到大排序,就得到了每一张图片和其它所有图片的相似度。
    你再取一个阈值,如距离小于多少,就算你定义的很像近图片。把所有小于这个阈值的图片放一起。
    LuffyWong
        16
    LuffyWong  
       2023-03-31 17:34:27 +08:00   ❤️ 1
    如果相似度算法 ok 了的话, python 调用 pytorch 实现直接 cuda 跑更快
    yousabuk
        17
    yousabuk  
       2023-03-31 18:41:17 +08:00 via iPhone
    帖子内容和格式像极了甲方对楼主提的需求
    laoooo
        18
    laoooo  
    OP
       2023-03-31 19:21:15 +08:00
    @NoOneNoBody 谢谢,我之前问过 GPT ,尝试过第三种方案,和你说的一样,这些小图片没法做预匹配,现在就是卡在了计算量上。第二种方案有所启发,非常感谢。
    laoooo
        19
    laoooo  
    OP
       2023-03-31 19:24:25 +08:00
    @kop1989smurf 每一张图都需要作为基准图与其他图进行对比,你说的这些情况理论上都要考虑。阈值的范围需要通过参数指定,并不是固定值。
    laoooo
        20
    laoooo  
    OP
       2023-03-31 19:26:56 +08:00
    @LuffyWong 对,目前相似度算法部分已经解决,效果还不错,但是目前没想到怎么去优化计算量,想通过 GPU 来跑,看看能不能快一点。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2722 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 09:38 · PVG 17:38 · LAX 02:38 · JFK 05:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.