快速实现用于修改 JPEG 解码器的 8 点 1D DCT
Fast implementation of an 8-point 1d DCT for modified JPEG decoder
我一直在研究一个用于网络的自定义视频编解码器。自定义编解码器将由javascript和html5 Canvas元素提供支持。
我想这样做有几个原因，我将在这个问题的底部列出，但首先我想解释一下我到目前为止做了什么，以及为什么我正在寻找快速的DCT转换。
所有视频压缩背后的主要思想是彼此相邻的帧具有大量相似之处。所以我正在做的是发送压缩为 jpg 的第一帧。然后我发送另一个 Jpeg 图像，它的宽度是第一帧的 8 倍，其中包含第一帧和之后的 8 帧之间的"差异"。
这个包含"差异"的大型 Jpeg 图像更容易压缩，因为它只有差异。
我用这个大的jpeg做了很多实验，我发现当转换为YCbCr颜色空间时，"色度"通道几乎完全是平坦的，只有少数例外。换句话说，视频中很少有部分在色度通道中变化很大，但一些确实发生变化的部分非常重要。
有了这些知识，我查找了JPEG压缩的工作原理，并发现它使用DCT来压缩每个8x8块。这真的让我感兴趣，因为我想如果我可以修改它，以便它不仅可以压缩"每个"8x8 块，还可以检查"下一个"8x8 块是否与第一个相似。如果它足够接近，那么只需发送第一个块并对两个块使用相同的数据。
这将提高解码速度，并改善比特率传输，因为可以使用的数据更少。
我认为这应该是一项简单的任务。所以我尝试构建自己的"修改"jpeg编码器/解码器。我构建了 RGB 到 YCbCr 转换器，我留下了"gzip"压缩来进行霍夫曼编码，现在我剩下的唯一主要部分就是进行 DCT 转换。
然而，这让我陷入了困境。我找不到快速的 8 点 1d dct 转换。我正在寻找这个特定的转换，因为根据我读过的许多文章，2d 8x8 dct 转换可以分成几个 1x8 id 转换。这是许多 jpeg 实现使用的方法，因为它的处理速度更快。
所以我认为 Jpeg 是一个如此古老的众所周知的标准，一个快速的 8 点 1d dct 应该会跳出来，但经过数周的搜索，我还没有找到一个。
我发现许多使用 O(N^2( 复杂性方法的算法。然而，这是令人眼花缭乱的缓慢。我还发现了使用快速傅立叶变换的算法，并对其进行了修改以计算DCT。例如下面此链接中的那个：
https://www.nayuki.io/page/free-small-fft-in-multiple-languages
理论上，这应该具有O(Nlog2(n((的"快速"复杂性，但是当我运行它时，我的i7计算机需要大约12秒来编码/解码"修改后的"jpeg。
我不明白为什么这么慢？还有其他JavaScript jpeg解码器可以做得更快，但是当我尝试查看它们的源代码时，我无法提取哪个部分正在执行DCT/IDCT转换。
https://github.com/notmasteryet/jpgjs
我唯一能想到的是，DCT背后的数学可能已经预先计算并存储在查找表或其他东西中。但是，我在谷歌上仔细查看了一下，我找不到任何谈论这一点的东西(至少我理解(。
所以我的问题是我在哪里可以找到/如何构建一种快速方法来计算这个"修改后的"jpeg 编码器/解码器的 8 点 1d dct 转换。任何这方面的帮助将不胜感激。
好吧，至于我为什么要这样做，主要原因是我想在我的网站上为手机提供"交互式"视频。这是无法做到的，因为每次开始播放视频时，iOS都会加载它的"本机"快速播放器。此外，当您几乎无法控制视频的渲染方式时，很难使过渡到视频的另一个时间点看起来"流畅"，尤其是在移动设备上。
再次非常感谢您提供的任何帮助！
所以我的问题是我在哪里可以找到/如何构建一种快速方法来计算这个"修改后的"jpeg 编码器/解码器的 8 点 1d dct 转换。任何这方面的帮助将不胜感激。
看看闪存世界和那里的JPEG编码器(在它被整合到引擎之前(。
例如：http://www.bytearray.org/?p=1089(提供源代码(此代码包含一个名为 fDCTQuant() 的函数，该函数执行 DCT，首先用于行，然后用于列，然后量化块(所以基本上你有你的 8x1 DCT(。
所以我正在做的是发送压缩为 jpg 的第一帧。然后我发送另一个 Jpeg 图像...
看看渐进式 JPEG。我认为它是如何工作的，以及如何构建数据流的一些事情听起来有点熟悉这个描述(不一样，但它们都朝着相关的方向发展。
">如果我可以修改它，以便它不仅可以压缩"每个"8x8 块，还可以检查"下一个"8x8 块是否与第一个类似。如果它足够接近，那么只需发送第一个块并对两个块使用相同的数据。
相似"和"足够接近"的表达在这里引起了我的注意。 看看常用的量化表。 您知道，将值更改 1 很容易导致该点的亮度变化 15%(对于色度通道通常甚至更多(，具体取决于 8x8 块中的位置以及应用的量词。
calculation with quantifier 40
(may be included in the set even at the lowest compression rates
at lower compression rates some quantifier can go up to 100 and beyond)
change the input by 1 changes the output by 40.
since we are working on 1byte value-range it's a change of 40/255
that is about 15% of the total possible range
所以你应该真正深思熟虑你所谓的"足够接近"。
总结一下：基于jpeg的视频编解码器，它利用帧之间的差异来减少数据量。这听起来也有些熟悉。
知道了：MPEG https://github.com/phoboslab/jsmpeg
*没有连接到引用的代码或编码器<</p>
我在这里实现了各种大小的可分离整数 2D DCT(以及其他转换(：https://github.com/flanglet/kanzi/tree/master/java/src/kanzi/transform。代码是用Java编写的，但实际上对于这种算法，它在任何语言中都几乎相同。IMO最有趣的部分是您在计算每个方向后所做的重新缩放。根据您的目标(最大精度、16 位计算、无缩放等(，您可能需要更改每个步骤的比例因子。在图像非常均匀的区域使用较大的块可以节省位。
本书展示了如何将DCT矩阵分解为高斯范式。这将是进行DCT的最快方法。
http://www.amazon.com/Compressed-Image-File-Formats-JPEG/dp/0201604434/ref=pd_sim_14_1?ie=UTF8&dpID=41XJBED6RCL&dpSrc=sims&preST=_AC_UL160_SR127%2C160_&refRID=1Q0G2H5EFYCQW2TJCCJN
