V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
moodasmood
V2EX  ›  程序员

图片找点算法优化

  •  
  •   moodasmood · 2019-06-22 16:51:22 +08:00 · 5544 次点击
    这是一个创建于 1963 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求: 实现按键精灵或者触摸精灵里面的多点找色功能(指定第一个点的颜色值,指定后续颜色值和相对于第一个点的 x,y 偏移值,在图片中找到某个点,这个点的颜色和第一个点的颜色相等,同时这个点的坐标加上后续坐标的偏移,后续坐标的颜色全部相等)

    入参示例:38CEE7,21|0|34D8EB,20|8|34D9EC,36|9|35D6EA,40|33|34D8EB,53|24|33D4E7,61|22|38D5E6,94|38|34D7E9,131|37|33CFE0,145|25|36D1E4 表示找颜色为 38CEE7 这个点的坐标,同时后续偏移位置的点颜色全部满足

    目前实现: 将图片转成二维数组,遍历全部点,检查每个点是否和指定颜色相符

    目前缺陷: 性能太差,1920*1080 的图片,输入 10 多个点,需要 14 至 20 秒才能找到点。请问大家有什么好的优化建议吗?

    第 1 条附言  ·  2019-06-23 01:16:19 +08:00
    感谢大家的建议,没找到什么太好的优化办法。最终实现还是遍历图片,不过根据输入调整了一下遍历规则,围绕图片的正中心点开始遍历(大部分需要找的点都不会在图片太边缘,所以从中心开始),另外,第一次遍历偶数序号的点,找到 return,没有找到再遍历奇数序号的点。最终虽然理论最大耗时还是那么多,但是结果平均处理时长降低了。
    第 2 条附言  ·  2019-06-23 01:26:56 +08:00
    第一次遍历偶数序号的点,如果第一个点的颜色匹配,但是后面颜色不匹配,再取这个点前后 2 个点测试,因为多数时候第一个点匹配了,就已经找到最终点附近了(一般一个颜色不可能一个像素大)。这样变向减少了取点对比次数
    第 3 条附言  ·  2019-06-23 09:56:38 +08:00

    测试图片:tt.png

    特征字符串:000000,-3|6|4D4D4D,-4|5|FFFFFF,0|12|08ADF9,-7|20|1010E8,16|27|000000,4|29|FFFFFF

    返回:腾讯qq的图标位置 (652,508)

    35 条回复    2019-06-24 13:55:10 +08:00
    wingkou
        1
    wingkou  
       2019-06-22 17:12:00 +08:00 via Android
    把图片压平成一维的,你要的匹配模式也压成一维,按行展开就好了吧,然后用变种正则什么的(视颜色为字符)?这样或许可以。
    nethard
        2
    nethard  
       2019-06-22 18:24:37 +08:00 via iPhone
    首先,做一个 unordered_map,key 是 color value 是 unordered_set。
    然后,初始化外层的 unordered_map,把待匹配的像素序列的颜色都加进去做 key,value 是新初始化的 unordered_set。同时,对于待匹配的像素序列里的每个节点,计算其累积 offset。
    然后,遍历一趟这个图片,把像素的坐标,根据像素的颜色,减去对应的累计 offset,都加到对应的 unordered_set 里
    最后,初始化一个坐标-累加器 map,遍历 unordered_map 里的每个 unordered_set,执行累加操作。最终,寻找 map 中值等于待匹配的像素序列的长度的 pair 的 key 即为输出。
    更优化的方案可以在这个基础上考虑位运算和向量操作。
    aguesuka
        3
    aguesuka  
       2019-06-22 18:57:07 +08:00 via Android
    kmp 算法,理论只要过一次
    nethard
        4
    nethard  
       2019-06-22 19:02:08 +08:00 via iPhone
    @aguesuka 他这个怎么 kmp ?模式是非连续的子序列,并且考虑到 24 位的 rgb 值,模式里很难有重复的部分。
    moodasmood
        5
    moodasmood  
    OP
       2019-06-22 19:29:49 +08:00
    @nethard 非常感谢您的建议。我之前是遍历图片,当某个点的颜色等于第一个点的时候就去判断后续是否满足,当全部满足的时候就 return 了,这样多数情况下并不会把图片遍历完。但是您这种得完全遍历图片,遍历数据更多了,反而速度更慢了。我目前消耗的主要时间是在遍历点上面,而不是比较,比较的话 10 多个点,做 10 多个==操作,速度并不慢
    jiejiss
        6
    jiejiss  
       2019-06-22 20:42:52 +08:00
    kmp 吧
    应该没有更快的办法了
    nethard
        7
    nethard  
       2019-06-22 20:47:06 +08:00 via iPhone
    @moodasmood 你有没有考虑过你这样做存在遍历的非连续性,进而导致的 cache 命中率降低?尤其是一个图片,好几 MB 呢。
    whileFalse
        8
    whileFalse  
       2019-06-22 21:16:16 +08:00 via iPhone
    试试把你的需求转为正则表达式 /大笑
    bilibilifi
        9
    bilibilifi  
       2019-06-22 21:43:59 +08:00 via iPhone
    写一个矩阵的 convolution 就可以了吧
    bilibilifi
        10
    bilibilifi  
       2019-06-22 21:44:39 +08:00 via iPhone
    用 cuda 写的话感觉可以很快
    moodasmood
        11
    moodasmood  
    OP
       2019-06-22 22:46:07 +08:00
    @bilibilifi 安卓,没有这些花里胡哨的东西
    keith1126
        12
    keith1126  
       2019-06-22 23:15:08 +08:00
    @moodasmood #11

    安卓没有 CUDA,但是应该有类似 GPU 加速的东西吧,或者用多线程并行搜索?

    (我不太了解安卓
    mixplugs
        13
    mixplugs  
       2019-06-23 00:29:14 +08:00
    估计得 GPU 加速,理论上复杂度下限应该就是 O(n)了。
    tiluo
        14
    tiluo  
       2019-06-23 01:14:57 +08:00
    请问你确定性能问题是因为算法吗?理论上来说,你的算法需要做 m*n*len(s)次操作,大概是这样 1920*1080*10*6=124,416,000 ‬. 如果是 in memory 的话,不需要 14-20s 吧?感觉上应该只需要 1s 不到
    https://blog.csdn.net/yangchenju/article/details/84306840
    moodasmood
        15
    moodasmood  
    OP
       2019-06-23 01:21:54 +08:00
    @tiluo 是的,遍历不需要那么久,但是对比颜色的时候还要计算颜色误差,还要排除某些特殊颜色(消除背景影响),所以导致速度很慢,另外,开发测试用的手机也有点差。我试了我 1 加 7pro,3120*1440 的图片才 4 秒左右,测试手机 1920*1080 要 20 秒左右
    txy3000
        16
    txy3000  
       2019-06-23 02:39:54 +08:00 via Android
    Google ac 自动机
    多字符串匹配 套路一样
    binux
        17
    binux  
       2019-06-23 03:03:08 +08:00 via iPhone
    不能降低精度吗?
    txy3000
        18
    txy3000  
       2019-06-23 03:12:19 +08:00 via Android
    只不过模式串个数是随间隔 指数级别增长
    比如 红××红 就有 256×256 个符合的模式串
    还要考虑二维坐标变换的边界条件
    可以试一试构建特殊字典树减少模式串
    反正要魔改
    shidenggui
        19
    shidenggui  
       2019-06-23 08:29:02 +08:00
    能不能给几个 testcases? 放几张图片和对应的匹配字符串以及结果?最近正在学 NFA,想尝试一下
    moodasmood
        20
    moodasmood  
    OP
       2019-06-23 09:58:20 +08:00
    @binux 怎么降精度?压缩图片?
    moodasmood
        21
    moodasmood  
    OP
       2019-06-23 09:58:30 +08:00
    @shidenggui 补充了
    smallpython
        22
    smallpython  
       2019-06-23 10:51:36 +08:00
    请问是做手游脚本吗?
    MengQuadra
        23
    MengQuadra  
       2019-06-23 11:07:53 +08:00
    分治+并行?
    moodasmood
        24
    moodasmood  
    OP
       2019-06-23 11:27:48 +08:00
    @smallpython 是的,自己写着玩,按键精灵这种广告太恶心,而且老出问题,就自己造轮子了
    guchengyehai1
        25
    guchengyehai1  
       2019-06-23 11:29:54 +08:00 via Android
    编写 opengl shader 并行计算
    JohnChiu
        26
    JohnChiu  
       2019-06-23 11:53:46 +08:00
    这个用目标检测多合适,SSD 训练一个模型就完事了
    Nicapoet
        27
    Nicapoet  
       2019-06-23 15:01:14 +08:00 via iPhone
    压缩图片,拿到坐标以后再把缩放比乘回去。
    (也可以考虑用图像处理相关算法,比如 surf 特征匹配配合颜色阈值化)
    bookit
        28
    bookit  
       2019-06-23 18:21:29 +08:00
    用 opencv 的图片查找函数呢,这么小的图片,应该非常快就能找到。

    我以前查的图片都是 2GB 的
    DejaVud
        29
    DejaVud  
       2019-06-23 19:48:03 +08:00
    直接用 opencv 或者类似的矩阵运算库,定义一个卷积核
    我自己写 eve 脚本,1920*1080 分辨率,一次找图操作在电脑端不超过 1s
    Windsooon
        30
    Windsooon  
       2019-06-23 20:01:45 +08:00
    1. 把要找的几个点的颜色以及相对位置理解成一个矩形。
    2. 然后遍历这张图片找到**符合条件**的矩形(矩形的最左点到最右点,最上点到最低点必须包含需要的颜色),这样可以筛选掉大部分的矩形。
    3. 接下来从结果的矩形中运用原本的算法来找点。
    shidenggui
        31
    shidenggui  
       2019-06-23 20:40:37 +08:00
    试了下你的例子,貌似 (652,508) 这个位置不太符合你给出的查找字符串。你能把图片转 hex 的代码也放下吗?
    hmzt
        32
    hmzt  
       2019-06-24 10:56:50 +08:00
    你这不涉及计算,第一个点也必须要遍历查找,没什么优化空间,既然是用来做脚本,应该在脚本里限制找图的范围来减少时间.
    aguesuka
        33
    aguesuka  
       2019-06-24 13:04:31 +08:00 via Android
    模式里没有的点就是通配符。
    aguesuka
        34
    aguesuka  
       2019-06-24 13:49:01 +08:00
    如果我没理解错的话。需求就是我知道了 p 个点的颜色和关于第一个点的相对坐标,在二维数组里面做匹配?实际上二维数组可以转为一维数组,用 kmp 的话时间复杂度是 O(m+n),n 是图片大小。m 是第一个点到最后一个点的距离。按照原来的算法时间复杂度是 O(np)实际上 p 只有 10 多,而且通常情况下不会达到 np,所以就算改了算法也要 1 秒左右。我想知道如果只找一个点要多久?
    moodasmood
        35
    moodasmood  
    OP
       2019-06-24 13:55:10 +08:00
    @aguesuka 1920*1080 的图片,遍历一次 16s 左右,主要想的优化方法就是减少第一个点的遍历次数
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5681 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 07:37 · PVG 15:37 · LAX 23:37 · JFK 02:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.