lovelive研究部吧 关注:4,873贴子:36,256

【组队工具算法讨论】导出SIF中的所有队员 v0.1

只看楼主收藏回复

LLH这个工具相信大家都不会陌生。我们平时查找卡片数据,查找队伍强度等都要用到。前一段时间我在一个主题帖[1] 中看到了关于自动组队的探讨,@xuanyizhou 也提到了程序化组队会遇到效率低、录入数据难的问题。笔者读完后对程序自动组队产生了兴趣,也想到了一些快速的算法。但在进一步探讨、实现这些快速算法前,笔者打算先解决录入数据的问题,毕竟到目前为止SIF并没有有效导出队伍的方法,而面对动辄200人以上的SR以上卡组,一个个录入需要很大的时间成本[2]。

这里笔者并没有采用最有效的网络抓包的方式进行,而是用了最暴力的解决方案——在队伍一览中截图,程序直接读取图片。笔者没有采用tensorflow等CNN进行读取,而是采用了经典的自行建模的信号处理手段。原因是1、缺少training的样本,以及2、截图的模式是固定的,没有变化,且模型清晰。


[1] http://tieba.baidu.com/p/494633932110楼讨论串
[2] 虽然没有写这个程序的时间成本大…


IP属地:美国1楼2017-02-03 12:29回复




    这是一张手机版国际服的队伍截图,从图中我们可以找到抓取队员需要的一些信息。首先,我们可以观察到一页截图最多放4x8=32个队员。其次,我们可以观察到在每一行和每一列开始前,图片上都有一条白边。利用这个信息,我们可以找到队员头像的起始横、纵坐标。


    IP属地:美国2楼2017-02-03 12:30
    收起回复
      如何进行提取呢?在图片的每个坐标点上,都存有红绿蓝(RGB)的数值。黑色对应的是全部0,而白色对应的是全部满值。在苹果设备的截图中,每个颜色占1个Byte,满值就是255.


      我们先进行一次“横向扫描”——把每个横坐标上,所有纵向的点加起来。为了减少噪音(顶部和底部的无用信息),我们只扫描中间的一部分,舍去图像最顶端和最低端的数值。这时候我们得到了W个数值,W为图像宽度。我们可以看看这些数值长什么样(这个图不是上面的截图的扫描结果,但是大体的图像是一样的):




      IP属地:美国3楼2017-02-03 12:32
      回复
        没错,每一个极大值都对应了一个头像的横坐标起点。前八个极大值之间的宽度也相对恒定,也印证了这八个头像是等款的事实。


        在进行下一步之前,我们再看看纵向扫描的样子:




        纵向一共有四行,前四个极大值间的间距也是相对固定的。


        对于这些扫描结果,经过一些简单的处理(去噪音、找到极值点),我们就得到了每一个头像坐标的起始点。


        IP属地:美国4楼2017-02-03 12:33
        回复
          在进行图像比对前,我们先要把图像缩放到合适的大小。不同设备截出来的图大小、比例是不一样的,比如这是一张9.7吋Retina iPad,日服的截图(右下方经过处理):




          可以看出它更大,长宽比也不一样。我们的目标是把每个队员的头像缩小至128x128左右。为此,我们可以根据之前扫描得到的每个头像的起点坐标算出这个截图要被缩小多少——只要算出它的间距与被正确缩小的截图中的起始点间距之间的比例,就得出了整个截图要被缩小或放大的比例。

          在把截图缩放至正确比例后,由于分辨率有变,为保准确,我们再一次进行纵横向扫描,并计算出32个头像的坐标起始点。


          IP属地:美国5楼2017-02-03 12:36
          回复
            下一步就是对头像的比对了。首先,我们可以计算这个队员的主属性是什么。这里我们取每个头像左侧中央的边框上的几个点,并求出它们的平均RGB值。RGB中最大的便是它所对应的颜色,也就是smile、pure、cool。不过,如果RGB接近白色,我们应该判定这个地方没有卡。

            第二步是计算该卡是否已觉醒。觉醒的卡左上角是黄色的,而没觉醒的是主属性颜色。我们取左上角中间,“UR”左下方的4个数据点求其平均颜色,并与黄色作距离平方比较:
            dist = sqrt((R-Yr)^2 + (G-Yg)^2 + (B-Yb)^2),小于一定阈值则此卡已觉醒。


            IP属地:美国6楼2017-02-03 12:37
            回复
              第三步就是比较头像数据了。在数据站作者@jebwizoscar 的github上有这样一个源:
              https://github.com/iebb/SIFStatic
              这里面就含有了大多数队员的头像数据(注:db.loveliv.es上才是最新的)。这些头像都是128x128的,正好可以用于比较。

              这里我们先用LLH上的数据[3],过滤掉属性、是否觉醒这两点不符的头像。为了加快运算速度,我们再假设截图者使用游戏自带的过滤设定,一次只显示一种稀有度的队员,把不符合稀有度的也过滤掉。这个假设不是必须的,但是会大大加快运算速度。

              我们把剩下的所有头像都跟这32个目标头像进行比对,计算出每个目标与所有头像的距离差值。这里距离差值指每个点上与目标头像的距离值(见上与黄色比较的例子)的和。距离值最小的便是我们要找的队员。


              [3] 这里笔者在LLH的卡片数据查询工具的HTML中读取LLH上的卡片信息。LLH作者: @Glaceon31


              IP属地:美国7楼2017-02-03 12:41
              回复
                样例代码:






                运行测试与分析:
                笔者对上面给出iPad的截图进行了测试,其输出结果为:





                其中[0, 0]表示没有卡。
                在限定UR稀有度的条件下,共耗时118秒钟,26个队员头像,平均4.53秒一个。识别准确度100%。


                可以看出,这种识别方法很慢,但是准确度是很高的。


                IP属地:美国8楼2017-02-03 12:43
                收起回复
                  下一步:
                  这是笔者在学校图书馆随便敲出来的程序,并没有进行充分的测试,也很有可能出错。下一步应对改程序进行充分的测试。


                  这个算法速度较慢,还有很大的提升空间。由于每一点的提升都可能要付出很多时间,考虑到时间成本笔者暂时不考虑提速。如读者有提速的好主意,请评论留言。


                  本程序使用了@jebwizoscar @Glaceon31 的部分数据/代码。在征得他们同意并作出足够优化后,笔者会将程序开源发布在github上。


                  运行本程序需要:
                  Python 3.5+
                  Pillow (PIL)
                  Jupyter Notebook (可选)


                  IP属地:美国9楼2017-02-03 12:48
                  收起回复
                    后记:
                    笔者关注研究部有相当长时间了,一直没有发帖。这次做了一点研究,希望大家能喜欢。


                    最后打个无耻广告:笔者在 http://live.bilibili.com/1111968 上偶尔会直播国服、日服的活动,希望大家能捧场观看。


                    笔者的账号如下
                    国服ID:752348888
                    日服ID:864332344
                    加好友如无回复,请在游戏内发私信。


                    IP属地:美国10楼2017-02-03 12:51
                    回复
                      学习一下


                      IP属地:广东来自iPhone客户端11楼2017-02-03 13:50
                      回复


                        IP属地:广东来自iPhone客户端13楼2017-02-03 16:09
                        回复
                          膜。。。膜巨佬


                          来自手机贴吧15楼2017-02-03 19:19
                          回复
                            膜拜dalao


                            IP属地:浙江来自Android客户端16楼2017-02-03 19:57
                            回复