图片找点算法优化

[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 秒才能找到点。请问大家有什么好的优化建议吗？

[wingkou]

把图片压平成一维的，你要的匹配模式也压成一维，按行展开就好了吧，然后用变种正则什么的（视颜色为字符）？这样或许可以。

[nethard]

首先，做一个 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]

kmp 算法，理论只要过一次

[nethard]

@aguesuka 他这个怎么 kmp ？模式是非连续的子序列，并且考虑到 24 位的 rgb 值，模式里很难有重复的部分。

[moodasmood]

@nethard 非常感谢您的建议。我之前是遍历图片，当某个点的颜色等于第一个点的时候就去判断后续是否满足，当全部满足的时候就 return 了，这样多数情况下并不会把图片遍历完。但是您这种得完全遍历图片，遍历数据更多了，反而速度更慢了。我目前消耗的主要时间是在遍历点上面，而不是比较，比较的话 10 多个点，做 10 多个==操作，速度并不慢

[jiejiss]

kmp 吧
应该没有更快的办法了

[nethard]

@moodasmood 你有没有考虑过你这样做存在遍历的非连续性，进而导致的 cache 命中率降低？尤其是一个图片，好几 MB 呢。

[whileFalse]

试试把你的需求转为正则表达式 /大笑

[bilibilifi]

写一个矩阵的 convolution 就可以了吧

[bilibilifi]

用 cuda 写的话感觉可以很快

[moodasmood]

@bilibilifi 安卓，没有这些花里胡哨的东西

[keith1126]

@moodasmood #11

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

（我不太了解安卓

[mixplugs]

估计得 GPU 加速，理论上复杂度下限应该就是 O(n)了。

[tiluo]

请问你确定性能问题是因为算法吗？理论上来说，你的算法需要做 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]

@tiluo 是的，遍历不需要那么久，但是对比颜色的时候还要计算颜色误差，还要排除某些特殊颜色（消除背景影响），所以导致速度很慢，另外，开发测试用的手机也有点差。我试了我 1 加 7pro，3120*1440 的图片才 4 秒左右，测试手机 1920*1080 要 20 秒左右

[txy3000]

Google ac 自动机
多字符串匹配 套路一样

[binux]

不能降低精度吗？

[txy3000]

只不过模式串个数是随间隔 指数级别增长
比如 红××红 就有 256×256 个符合的模式串
还要考虑二维坐标变换的边界条件
可以试一试构建特殊字典树减少模式串
反正要魔改

[shidenggui]

能不能给几个 testcases? 放几张图片和对应的匹配字符串以及结果？最近正在学 NFA，想尝试一下

[moodasmood]

@binux 怎么降精度？压缩图片？