图片找点算法优化

[moodasmood]

需求： 实现按键精灵或者触摸精灵里面的多点找色功能（指定第一个点的颜色值，指定后续颜色值和相对于第一个点的 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 秒才能找到点。请问大家有什么好的优化建议吗？

[moodasmood]

@shidenggui 补充了

[smallpython]

请问是做手游脚本吗?

[MengQuadra]

分治+并行？

[moodasmood]

@smallpython 是的，自己写着玩，按键精灵这种广告太恶心，而且老出问题，就自己造轮子了

[guchengyehai1]

编写 opengl shader 并行计算

[JohnChiu]

这个用目标检测多合适，SSD 训练一个模型就完事了

[Nicapoet]

压缩图片，拿到坐标以后再把缩放比乘回去。
（也可以考虑用图像处理相关算法，比如 surf 特征匹配配合颜色阈值化）

[bookit]

用 opencv 的图片查找函数呢，这么小的图片，应该非常快就能找到。

我以前查的图片都是 2GB 的

[DejaVud]

直接用 opencv 或者类似的矩阵运算库,定义一个卷积核
我自己写 eve 脚本,1920*1080 分辨率,一次找图操作在电脑端不超过 1s

[Windsooon]

1. 把要找的几个点的颜色以及相对位置理解成一个矩形。
2. 然后遍历这张图片找到**符合条件**的矩形（矩形的最左点到最右点，最上点到最低点必须包含需要的颜色），这样可以筛选掉大部分的矩形。
3. 接下来从结果的矩形中运用原本的算法来找点。

[shidenggui]

试了下你的例子，貌似 (652,508) 这个位置不太符合你给出的查找字符串。你能把图片转 hex 的代码也放下吗？

[hmzt]

你这不涉及计算,第一个点也必须要遍历查找,没什么优化空间,既然是用来做脚本,应该在脚本里限制找图的范围来减少时间.

[aguesuka]

模式里没有的点就是通配符。

[aguesuka]

如果我没理解错的话。需求就是我知道了 p 个点的颜色和关于第一个点的相对坐标，在二维数组里面做匹配？实际上二维数组可以转为一维数组，用 kmp 的话时间复杂度是 O(m+n)，n 是图片大小。m 是第一个点到最后一个点的距离。按照原来的算法时间复杂度是 O(np)实际上 p 只有 10 多，而且通常情况下不会达到 np，所以就算改了算法也要 1 秒左右。我想知道如果只找一个点要多久？

[moodasmood]

@aguesuka 1920*1080 的图片，遍历一次 16s 左右，主要想的优化方法就是减少第一个点的遍历次数