【GAD翻译馆】细剖HQX缩放过滤器

发表于2017-11-08
评论0 783浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594

翻译:赵菁菁(轩语轩缘)审校:李笑达(DDBC4747

HQX过滤器,也叫hq2xhq3xhq4x,是著名的像素艺术,主要是旧的控制台(如NES)模拟器使用这些过滤器,用于提供流畅的游戏渲染,由Maxim Stepin2003年左右开发完成。

目前有更好的像素艺术放大算法,比如xBR。微软也做了一些研究去生产另一个缩放器。HQX一直都是稳定的参照对象,曾在FFmpeg bug跟踪器上被请求。我决定仔细研究一下我们能否实现。毕竟我们已经有Super2xSaI了,人们看来挺喜欢编码他们相当规模的旧学校视频游戏会话记录的想法。

不幸的是,参考代码超过展开C代码的12.000行。在每一个项目中,这个代码基本上没有重复。而且,似乎没有人对算法有任何了解。我不想在FFmpeg重现该错误。

关于过滤器的常识

      让我们开始了解这些滤波器的常识。有3个过滤器拥有类似的算法:hq2xhq3xhq4x,分别以2, 34倍比例输入图像。没有时间插值,只是个一比一的帧缩放。

      3种算法都在当前像素周围使用一个3x3区域,用于确定使用的插值。因此,对于每个像素,构建一个8位模式:算法会检查周围8个像素中的每一个是否与当前像素(中心)存在差异。这种差异采用YUV阈值定义:亮度48, 蓝色色度7,红色色度6:如果一个平面上的一个差异是在阈值之上,在模式中该位将为1,否则为0

      然后展开代码。基本上,代码有几千个switch-case结构,8位模式的所有256个组合。采用不同的插值方法,每种情况都有代码填充一个2x2hq2x),3x3hq3x)或4x4的块(hq4x)。有每像素10次插值,它们实际上是带有不同因子的23像素插值。

这就是我们知道的关于算法本身的全部。

首次尝试

起初我很天真,我认为通过使用C预处理器来减少行数是可能的。毕竟,代码是非常冗余的。这是一个巨大的错误,我在这浪费了大量的时间。我可能保存了像30004000行的东西,但是我在过程中碰了几次壁。通常,在某些模式情况下,存在额外的差异条件,这些条件不存储在模式中(switch-case结构会更大……),这些条件也是是非常复杂的东西。

所以我想真正理解算法,手动地。就像,你知道,有笔和纸。我为一些模式这么做是为了深入了解,但这是一个非常缓慢的过程,它实际上并没有帮助我很多。

hq2x的可视化表示形式

      那么,我们有了hq2x3个过滤器中最简单的。我们知道对于一个像素,会产生2x2的块。我们可以安心假设一个像素的算法与其他三个带有一些对称性的像素的算法是一样的。

      对于10种插值方法有256种模式。表示一个方法是检查触发每个插值的全部模式是什么。

      所以我写了一些Python代码,为的是从参考代码提取我所需要的全部信息,我用Cairo来表示:

      在左边(蓝色渐变的3x3块),是当右边组合之一匹配时选择的插值。蓝色更多意味着系数更重要,白色意味着系数不太重要。中心点是当前的那个。

右边的是各种触发插值的不同组合的列表:

这些绿色行对应于我们在原始代码中一些模式案例中发现的额外的if检查。这里警告一下:我们只显示if为真情况,这意味着其他情况不显示。因此,这些绿色行必须在无条件的任何模式之前处理。

在各种情况下,我们可以观察到组合中的通用模式。例如,对于第一个插值(实际上不是,我们只选择当前像素),我们可以用一些“可选”差异区分相同的模式。

不幸的是,分解组合并不像听起来那么容易。为了确定像素值是否会影响选定的插值,我使用了一个非常愚蠢和缓慢的算法,可以总结为下面的伪代码:

1
2
3
4
5
6
对于一个给定插值:
      每一个组合互相比较:
        确定两者间的差异
        生成所有需要在子集中满足的组合,假设它们是可选的组合
        如果可以发现所有的组合,把模式添加到列表中
保存最佳的模式(基本上是除去那些存在父集的模式)

所以就产生了这个:

语义和之前的图片一样,除了现在的灰色像素代表像素值不重要的像素。

从中获取代码

现在这张最新图片可以很容易翻译成代码。我们必须遵守两条规则:

你会得到以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
if ((P(0xbf,0x37) || P(0xdb,0x13)) && WDIFF(w1, w5))
    return interp_2px(w4, 3, w3, 1, 2);
if ((P(0xdb,0x49) || P(0xef,0x6d)) && WDIFF(w7, w3))
    return interp_2px(w4, 3, w1, 1, 2);
if ((P(0x0b,0x0b) || P(0xfe,0x4a) || P(0xfe,0x1a)) && WDIFF(w3, w1))
    return w4;
if ((P(0x6f,0x2a) || P(0x5b,0x0a) || P(0xbf,0x3a) || P(0xdf,0x5a) ||
     P(0x9f,0x8a) || P(0xcf,0x8a) || P(0xef,0x4e) || P(0x3f,0x0e) ||
     P(0xfb,0x5a) || P(0xbb,0x8a) || P(0x7f,0x5a) || P(0xaf,0x8a) ||
     P(0xeb,0x8a)) && WDIFF(w3, w1))
    return interp_2px(w4, 3, w0, 1, 2);
if (P(0x0b,0x08))
    return interp_3px(w4, 2, w0, 1, w1, 1, 2);
if (P(0x0b,0x02))
    return interp_3px(w4, 2, w0, 1, w3, 1, 2);
if (P(0x2f,0x2f))
    return interp_3px(w4, 14, w3, 1, w1, 1, 4);
if (P(0xbf,0x37) || P(0xdb,0x13))
    return interp_3px(w4, 5, w1, 2, w3, 1, 3);
if (P(0xdb,0x49) || P(0xef,0x6d))
    return interp_3px(w4, 5, w3, 2, w1, 1, 3);
if (P(0x1b,0x03) || P(0x4f,0x43) || P(0x8b,0x83) || P(0x6b,0x43))
    return interp_2px(w4, 3, w3, 1, 2);
if (P(0x4b,0x09) || P(0x8b,0x89) || P(0x1f,0x19) || P(0x3b,0x19))
    return interp_2px(w4, 3, w1, 1, 2);
if (P(0x7e,0x2a) || P(0xef,0xab) || P(0xbf,0x8f) || P(0x7e,0x0e))
    return interp_3px(w4, 2, w3, 3, w1, 3, 3);
if (P(0xfb,0x6a) || P(0x6f,0x6e) || P(0x3f,0x3e) || P(0xfb,0xfa) ||
    P(0xdf,0xde) || P(0xdf,0x1e))
    return interp_2px(w4, 3, w0, 1, 2);
if (P(0x0a,0x00) || P(0x4f,0x4b) || P(0x9f,0x1b) || P(0x2f,0x0b) ||
    P(0xbe,0x0a) || P(0xee,0x0a) || P(0x7e,0x0a) || P(0xeb,0x4b) ||
    P(0x3b,0x1b))
    return interp_3px(w4, 2, w3, 1, w1, 1, 2);
return interp_3px(w4, 6, w3, 1, w1, 1, 3);

      P()宏观检查模式是否匹配。第一个操作数过滤重要的像素差异,第二个操作数是预期结果。WDIFF ()允许检查一个额外的差异。interp_[23]px()函数是插值函数,带有值和系数。

      用一些宏观的魔法,你可以很容易地得到该函数其他三个像素的版本。

      利用相同的方法,你可以得到生成以下函数的代码:hq3x2x1像素,hq4x2x2像素。

最终代码

      全部过滤器的完整最终hqx代码可以在这里查看

      信息提取、图像调试和代码生成器可以在我的hqxGitHub查看。利用hq2x.png来获取图片,让代码2生成上面的代码。

      在写帖子的时候,libavfilter/vf_hqx.c560行代码。比较起来,来自(现代)参考实现的代码约12000行:

1
2
3
4
5
6
7
8
9
% wc -l hqx-read-only/src/*.[ch]
   141 hqx-read-only/src/common.h
  2809 hqx-read-only/src/hq2x.c
  3787 hqx-read-only/src/hq3x.c
  5233 hqx-read-only/src/hq4x.c
   138 hqx-read-only/src/hqx.c
    55 hqx-read-only/src/hqx.h
    38 hqx-read-only/src/init.c
总共12201行

      所以基本上,FFmpeg中的代码不到1/21。参考代码的速度可能更快,但这样就放弃FFmpeg的代码太痛苦了,而且我觉得那不重要:人们会使用这种方法去缩放任天堂游戏机,像分辨率游戏似的(160x144像素)。就是说,我仍然好奇,所以随意去做基准程序吧,然后告诉世界。

      总之,代码看起来没那么慢。利用线程,在桌面上我用hq4x,输入320x240(老一代i7),速度为110 FPS。我认为目前这是够好了。

接下来

现在我相信代码可以更加简化。如果你看看hq2x图片,不知何故,你会发现有一个水平/垂直对称。这种表示方法也没有显示出差异的其他情况,这可能有助于给出更有意义的代码。我们可以用更合乎逻辑的方式猜测单个插值的系数,而不是做一些模式匹配。

如果你对这项工作感兴趣,请随意和我讨论。我不打算再在过滤器上花时间了,但我会很乐于听到关于它的进一步研究。

呃,在你提问之前,我要说:不,我没有联系Maxim Stepin询问关于他算法的事情,我想玩得开心些,那可能是作弊;)


【版权声明】

原文作者未做权利声明,视为共享知识产权进入公共领域,自动获得授权;

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

标签:

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台