几年前,波兰计算机科学家 Jarek Duda 发明了一种叫做不对称数字系统(ANS)的重要新型压缩技术。在发明这项技术之初,他就想保证所有人都可以使用,因此他没有为这项技术申请专利,而是将其公开。自 2014 年以来,Facebook、苹果和谷歌都基于 Duda 的突破开发了软件。
图丨 Jarek Duda
但现在,谷歌却在申请一项专利,该专利试图在视频压缩时使用 ANS 技术。Duda 对此表示不满。
谷歌则否认了其试图为 Duda 的发明申请专利。谷歌的一位发言人说,Duda 提出了一个不能直接获得专利的理论概念,而谷歌申请的专利,是谷歌工程师经过额外工作,基于该理论的具体化应用。
但 Duda 提交了他在 2014 年与谷歌工程师的交流邮件,他当时的技术就是谷歌现在要申请的技术专利,这一观点在 2 月很大程度上得到了欧洲专利局初步裁决的支持。
尽管欧洲的诉讼尚未结束,谷歌则依然正在美国申请专利。
从 3 月份开始 Duda 向媒体求助,媒体开始调查这个问题。经过几周的反复讨论,谷歌终于提供了一份针对这一专利的正式声明——一份非常乏味的声明。它声明,谷歌在其应用中包含了 Duda 先前的工作成果,但“我们依然在等并将尊重美国专利商标局(USPTO)的裁定。”
图丨 Facebook 基于 ANS 开发了一个压缩库
但几天后,谷歌就以不同的语气发了后续声明。
“谷歌承诺,长期且持续开源编解码器 (如 VP8、VP9 和 AV1),并免版税。所有这些编解码器都可免版税获得许可,本专利也将如此。”
然而,Duda 不相信他们。“我们可以期待谷歌的善意,然而,这并不能保证什么。以‘免版税许可条款’获得许可的专利通常会有问题。”
Duda 希望谷歌承认他是最初的发明者,并在法律上保证所有人都可以使用这项专利。最好,谷歌完全停止申请这项专利。
计算机使用字符串 1 和 0 表示数据。例如,ASCII 编码方案使用一个 7 位字符串来表示字母数字字符。
通常,符号会以不同的频率出现,数据压缩技术正是利用这个来表示数据。例如,在英文文本中,字母“e”出现的频率比“z”或“x”要高得多。因此,用 7 位来表示所有字符可能不是高效的方案,而使用 3 或 4 位来表示常见的字母、使用 7 位来表示不常见的字母会更高效。
有一种标准的方法叫做霍夫曼编码(Huffman coding),当处理概率为 2 的倒数的符号时,这种方法很有效。信息理论认为,最优编码使每个符号的长度 (以位为单位) 与其概率的负对数成正比。例如,假设你要对符号 A (P=1/2)、B (P=1/4)、C (P=1/8) 和 D (P=1/8) 进行编码。在这种情况下,最优编码可能是 A=0, B=10, C=110, D=111。
图丨霍夫曼树
这样编码是最优的,因为 log2(1/2) = -1,所以 A 应该有 1 位表示,log2(1/4) = -2,所以 B 应该有 2 位表示,log2(1/8)=-3,所以 C 和 D 应该有 3 位表示。
但当符号概率不是 2 的幂的倒数时,霍夫曼编码就没有那么好了。例如,符号 E (P=1/3)、F (P=1/3)、G (P=1/6) 和 H (P=1/6),霍夫曼编码就不是那么有效了。信息论认为,E 和 F 应该用 1.584 位字符串来表示,而 G 和 H 应该用 2.584 位字符串表示。
使用霍夫曼编码时,有些符号需要用很多位来表示,而有些符号却很少。因此,使用霍夫曼编码技术压缩数据通常会需要更长的时间。这不可能实现高效编码。但是,如果放宽每个符号由特定离散位字符串表示的要求,则可以有效地表示非整数位的符号。
例如,一种称为算术编码的技术将实数行细分为 0 和 1 之间的数字,每个符号的间隔份额与该符号预计出现在数据中的频率成正比。编码首先识别与第一符号对应的区域,然后对剩下的区域进行细分(同样,每个符号的份额与其频率成正比),编码第二符号,以此类推。
当所有的符号都被编码后,系统就会使用一个长二进制字符串 (比如 0.1010010111010110…) 来表示与编码字符串对应的数轴上的精确点。这种方法实现了接近理论最大值的压缩。但是因为它涉及到任意精度分数值的乘法,编码和解码步骤在计算上代价很大。
Duda 的突破是开发了一种新的编码方案,称为非对称数字系统 (ANS),它结合了这两种方法的最佳特性。它可以像算术编码一样简洁地表示一串符号,但编码和解码步骤像霍夫曼编码一样都很快。
这一技术已经被各大软件公司迅速掌握。Facebook 基于 Duda 2016 年的工作成果推出了一种新的压缩算法,名为 ZStandard。苹果公司在其 LZFSE 压缩算法中同时加入了 ANS。谷歌已经将 ANS 合并到其用于压缩 3D 点云的 Draco 库,以及一种名为 Pik 的新图像压缩格式中。
压缩图像和视频的方式与压缩文本的方式基本相同。例如,压缩软件会查找图像中比平均出现频率更高的颜色或形状的统计模型,然后,用较短字符串表示频繁出现的模型,实现压缩图像。视频编码器通常使用数据的数学转换来识别这一微妙的规律,然后就像处理一串字母数字符号一样,使用基于 ANS 的算法对来自视频的图像数据进行编码。
Duda 不仅仅是开发了 ANS,他也是该技术的传道者。2014 年 1 月,他给许多视频编解码器开发人员发了电子邮件,推荐 ANS 算法,可用于类似 Google VP9 等视频编码格式。
参与开发 VP9 的高级技术专家 Paul Wilkins 曾回复说:“这不是现阶段可以应用到 VP9 的东西,但未来的编解码器值得关注这一技术。”
几年后,谷歌提交了一项名为“混合布尔令牌 ANS 系数编码”(mixed boolean-token ANS coefficient coding)的专利申请。就像任何专利申请一样,这个专利申请里塞满了法律术语。但专利中最重要的部分在法律方面的表述是相当清楚的。这是第一个主张使用熵解码器状态机概念的专利,该状态机包括一个布尔 ANS 解码器和一个字符 ANS 解码器(这两个版本的 ANS 解码器都是 Duda 发明的),来解码符号流。视频被分解为“具有像素块的视频帧”,像素块又由一系列变换系数表示,然后用这些符号来表示像素块。
Duda 认为,这个“发明”只是将 ANS 应用于传统的视频解码流水线。大多数有效的视频压缩方案都是将视频帧表示为像素块,并通过数学变换,使用可被高效压缩的符号来表示那些像素块。Duda 认为唯一重要的创新是该专利声称使用 ANS 来编码这些符号。
在过去的几个月里,外界多次要求谷歌联系一位技术专家,以准确地解释谷歌的新专利究竟是什么,以及它对比 Duda 的发明有哪些优势。但谷歌一直没有照办,所以我们无法解释谷歌是如何将自己的发明与 Duda 的原创发明区分开来的。这样看来,似乎 Duda 认为谷歌的专利只适用于传统视频解码器的说法就很说得通了。
事实上,这也是欧洲专利局在初步裁决中得出的结论。欧洲专利局 2 月份的一项裁决称:“专利声明 1 的主题事项中不涉及创造性步骤”,Duda 在 2014 年 1 月的邮件中提供的信息“足以使技术人员无需任何技能就能获得新发明”。
这显然是不利于谷歌的迹象。但欧洲的专利程序还没有结束,外界也在等美国专利商标局的裁决。
ANS 被看作是算术编码方案的快速替代品。这些方案是在 20 世纪 70 年代发明的,但很快就被专利阻碍,限制了其早期的使用。Duda 说,他决定不让 ANS 发生这种情况。他希望通过公开自己的成果而不申请自己的专利,阻止其他人为这项技术申请专利,让所有人都可以自由使用它。
图丨美国专利商标局
专利系统可能最终会满足 Jarek Duda 的愿望:美国和欧洲的专利机构可能会拒绝谷歌的专利申请,让所有人都可以免费使用 ANS。如果是这样的话,这要归功于 Duda 数月来的努力。
从理论上讲,公开一项发明而不申请专利,足以使其进入公共领域。在授予专利之前,专利审查员会先搜寻现有技术,而现有技术都可以在出版物中找到。因此,如果一项发明之前已经向公众公开,审查员应该发现这一披露,并利用它来拒绝专利申请。
问题是审查员不是无所不知的。他们没有可以搜索所有已经发布的文档的工具。即使有,他们找到的同一发明的出版物,也可能是用不同语言描述的。
专利审查员的时间也有限。在美国,一个典型的审查员总共应该在审查过程的所有阶段花费 19 个小时。要理解一项复杂的技术,然后尝试搜索每个曾经发布的文档,查看是否有引用,这样的时间并不够。
在实践中,美国审查人员经常严重依赖专利数据库本身来寻找现有技术。专利数据库是一种便于专利审查者使用的模式,而且它们已经经过技术类型分组,使得查找相关专利变得容易。因此,如果你申请了专利,专利局可能会阻止其他人提出与你的发明相似的专利申请。但如果你像 Duda 一样,选择不为发明申请专利,专利局可能不知道到你曾公开过这项发明,所以他们可能会授予其他人这一专利。
欧洲专利体系在审查过程中为 Duda 这样的第三方提供了一种信息提交机制。Duda 利用这一机制在去年 10 月提交了一封信,指出他自己之前的工作与谷歌的专利有相似之处。美国专利局最近也推出了类似的机制,但这一机制让发明者有责任监督专利申请,并反对为自己的工作成果申请专利。
Duda 说:“有很多像我这样的人都希望自己的专利能被他人无限制地使用。”专利局通常只是检查专利而不检查那些文献。如果某些东西没有写在专利里,他们就不太可能找到。
Duda 说:“如果这项专利获得批准,就很难摆脱它了。他们可以以数百万美元的价格起诉你,为了摆脱现有的专利,这需要花费数十万美元。”
公平地说,谷歌一直主张保持视频标准不受专利限制。早在 2011 年,谷歌就表示将不再支持 Chrome 的 H.264 编解码器,并与 Firefox 的开放标准一致。谷歌推出了自己的 VP8 编解码器作为一个更开放的选择。最近,谷歌推出了免版税的 VP9 编解码器,并宣布支持免版税的 AV1 格式。
谷歌认为申请专利没有改变什么——它仍然致力于开放视频格式并免版税。
那么,为什么谷歌还要尝试为 ANS 基础的视频申请专利呢?谷歌拒绝讨论这个问题,我们也只能猜测。一个可能的原因是,为了防止其他拥有大量专利组合的公司申请专利。专利的界限从来都不是很清楚,所以即使谷歌试图完全使用开放的、免版税的编解码器,它也要担心有人会用适用于谷歌自身视频的技术申请专利。
谷歌公司申请 ANS 专利也可能是一个简单的官僚疏忽行为。谷歌拥有大量的专利律师,他们的工作就是尽可能多地获得专利。沉浸在专利文化的熏陶下,他们可能根本没有想到会有 Duda 这样的人故意不为发明申请专利,而且可能会阻止谷歌试图这么做。
无论如何,Duda 不相信谷歌的意图。他指出了最近谷歌自动驾驶汽车公司 Waymo 与 Uber 之间的诉讼。该案主要是涉嫌盗窃商业机密,但 Waymo 在诉讼中也包含了一些专利声明(专利声明在几个月后被撤销)。在 Duda 看来,这表明谷歌只会利用专利来报复起诉谷歌侵犯专利权的其他人。
联系客服