用于改进的 JPEG 解码器的 8 点 1d DCT 的快速实现
Fast implementation of an 8-point 1d DCT for modified JPEG decoder
我一直在研究用于网络的自定义视频编解码器。自定义编解码器将由 javascript 和 html5 Canvas 元素提供支持。
我想这样做有几个原因，我将在这个问题的底部列出，但首先我想解释一下到目前为止我做了什么以及为什么我正在寻找快速 DCT 变换。
所有视频压缩背后的主要思想是彼此相邻的帧有很多相似之处。所以我正在做的是发送压缩为 jpg 的第一帧。然后我发送另一个 Jpeg 图像，它是第一帧的 8 倍宽，在第一帧和接下来的 8 帧之间保持 "differences"。
这个包含 "differences" 的大 Jpeg 图像更容易压缩，因为它只有差异。
我用这个大的 jpeg 做了很多实验，我发现当转换为 YCbCr 颜色时 space "chroma" 通道几乎完全平坦，只有一些突出的例外。换句话说，视频中很少部分在色度通道中发生很大变化，但其中一些确实发生变化的部分非常重要。
有了这些知识，我查看了 JPEG 压缩的工作原理，发现除其他外，它使用 DCT 来压缩每个 8x8 块。这让我很感兴趣，因为我想如果我可以修改它，让它不仅压缩 "each" 8x8 块，而且还会检查 "next" 8x8 块是否与第一个块相似。如果足够接近，则只需发送第一个块并为两个块使用相同的数据。
这会提高解码速度，并提高比特率传输，因为要处理的数据会更少。
我认为这应该是一个很容易完成的任务。所以我尝试构建自己的 "modified" jpeg encoder/decoder。我构建了 RGB 到 YCbCr 转换器，我留下 "gzip" 压缩来进行霍夫曼编码，现在我剩下的唯一主要部分是进行 DCT 变换。
然而，这让我卡住了。我找不到快速的 8 点 1d dct 变换。我正在寻找这个特定的变换，因为根据我读过的许多文章，2d 8x8 dct 变换可以分成几个 1x8 id 变换。这是许多 jpeg 实现使用的方法，因为它处理起来更快。
所以我认为 Jpeg 是一个如此古老的众所周知的标准，一个快速的 8 点 1d dct 应该会突然出现在我面前，但经过数周的搜索我还没有找到一个。
我发现许多使用 O(N^2) 复杂度方法的算法。但这慢得令人眼花缭乱。我还找到了使用快速傅里叶变换的算法，并且我修改了它们以计算 DCT。比如下面这个link：
https://www.nayuki.io/page/free-small-fft-in-multiple-languages
理论上这应该具有 O(Nlog2(n)) 的 "fast" 复杂度，但是当我 运行 它需要我的 i7 计算机大约 12 秒才能 encode/decode "modified".jpeg.
我不明白为什么这么慢？还有其他 javascript jpeg 解码器可以更快地完成它，但是当我尝试查看它们的源代码时，我无法找出哪个部分正在执行 DCT/IDCT 转换。
https://github.com/notmasteryet/jpgjs
我唯一能想到的可能是 DCT 背后的数学运算已经被预先计算并存储在查找 table 之类的东西中。然而，我仔细研究了 google 并且找不到任何（至少我理解的）谈论这个的东西。
所以我的问题是我可以在哪里 find/how 建立一个快速的方法来计算这个 "modified" jpeg encoder/decoder 的 8 点 1d dct 变换。对此的任何帮助将不胜感激。
好吧，至于我为什么要这样做，主要的原因是我想在我的网站上有"interactive"手机视频。这无法完成，因为 iOS 每次开始播放视频时都会加载它的 "native" 快速播放器。此外，当您几乎无法控制视频的呈现方式（尤其是在移动设备上）时，也很难过渡到视频的另一个时间点 "smooth"。
再次感谢您提供的任何帮助！
So my question is where can I find/how can I build a fast way to compute an 8 point 1d dct transform for this "modified" jpeg encoder/decoder. Any help with this would be greatly appreciated.
看看 flash 世界和那里的 JPEG 编码器（在它被集成到引擎中之前）。
例如：http://www.bytearray.org/?p=1089（提供的来源）这段代码包含一个名为 fDCTQuant() 的函数，它执行 DCT，首先是行，然后是列，然后它量化块（所以基本上你有你的 8x1 DCT）。
So what I'm doing is I send the first frame compressed as a jpg. Then I send another Jpeg image ...
看看渐进式 JPEG。我认为一些事情是如何工作的，以及数据流是如何构建的，听起来有点熟悉这个描述（不一样，但它们都在相关的方向上。imo）
what if I could modify this so that it not only compresses "each" 8x8 block, but it also checks to see if the "next" 8x8 block is similar to the first one. If it is close enough then just send the first block and use the same data for both blocks.
表达式 "similar" 和 "close enough" 在这里引起了我的注意。看看通常使用的量化表。您知道，根据 8x8 块中的位置以及所应用的量词，将值更改 1 很容易导致该点的亮度值发生 15% 的变化（对于色度通道，通常甚至更多）。
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
所以你应该真正体贴"close enough"。
总结一下：基于 jpeg 的视频编解码器利用帧之间的差异来减少数据量。这对我来说也有点耳熟。
知道了：MPEG https://github.com/phoboslab/jsmpeg
*与参考代码或编码器没有联系
这本书展示了如何将 DCT 矩阵因式分解为高斯范式。那将是执行 DCT 的最快方法。
我在这里实现了各种大小的可分离整数 2D DCT（以及其他变换）：https://github.com/flanglet/kanzi/tree/master/java/src/kanzi/transform。代码在 Java 但实际上对于这种算法，它在任何语言中都几乎相同。 IMO 最有趣的部分是您在计算每个方向后进行的重新缩放。根据您的目标（最大精度、16 位计算、无缩放等），您可能想要更改每个步骤的缩放因子。在图像非常均匀的区域使用更大的块可以节省位。
我一直在研究用于网络的自定义视频编解码器。自定义编解码器将由 javascript 和 html5 Canvas 元素提供支持。
我想这样做有几个原因，我将在这个问题的底部列出，但首先我想解释一下到目前为止我做了什么以及为什么我正在寻找快速 DCT 变换。
所有视频压缩背后的主要思想是彼此相邻的帧有很多相似之处。所以我正在做的是发送压缩为 jpg 的第一帧。然后我发送另一个 Jpeg 图像，它是第一帧的 8 倍宽，在第一帧和接下来的 8 帧之间保持 "differences"。
这个包含 "differences" 的大 Jpeg 图像更容易压缩，因为它只有差异。
我用这个大的 jpeg 做了很多实验，我发现当转换为 YCbCr 颜色时 space "chroma" 通道几乎完全平坦，只有一些突出的例外。换句话说，视频中很少部分在色度通道中发生很大变化，但其中一些确实发生变化的部分非常重要。
有了这些知识，我查看了 JPEG 压缩的工作原理，发现除其他外，它使用 DCT 来压缩每个 8x8 块。这让我很感兴趣，因为我想如果我可以修改它，让它不仅压缩 "each" 8x8 块，而且还会检查 "next" 8x8 块是否与第一个块相似。如果足够接近，则只需发送第一个块并为两个块使用相同的数据。
这会提高解码速度，并提高比特率传输，因为要处理的数据会更少。
我认为这应该是一个很容易完成的任务。所以我尝试构建自己的 "modified" jpeg encoder/decoder。我构建了 RGB 到 YCbCr 转换器，我留下 "gzip" 压缩来进行霍夫曼编码，现在我剩下的唯一主要部分是进行 DCT 变换。
然而，这让我卡住了。我找不到快速的 8 点 1d dct 变换。我正在寻找这个特定的变换，因为根据我读过的许多文章，2d 8x8 dct 变换可以分成几个 1x8 id 变换。这是许多 jpeg 实现使用的方法，因为它处理起来更快。
所以我认为 Jpeg 是一个如此古老的众所周知的标准，一个快速的 8 点 1d dct 应该会突然出现在我面前，但经过数周的搜索我还没有找到一个。
我发现许多使用 O(N^2) 复杂度方法的算法。但这慢得令人眼花缭乱。我还找到了使用快速傅里叶变换的算法，并且我修改了它们以计算 DCT。比如下面这个link：
https://www.nayuki.io/page/free-small-fft-in-multiple-languages
理论上这应该具有 O(Nlog2(n)) 的 "fast" 复杂度，但是当我 运行 它需要我的 i7 计算机大约 12 秒才能 encode/decode "modified".jpeg.
我不明白为什么这么慢？还有其他 javascript jpeg 解码器可以更快地完成它，但是当我尝试查看它们的源代码时，我无法找出哪个部分正在执行 DCT/IDCT 转换。
https://github.com/notmasteryet/jpgjs
我唯一能想到的可能是 DCT 背后的数学运算已经被预先计算并存储在查找 table 之类的东西中。然而，我仔细研究了 google 并且找不到任何（至少我理解的）谈论这个的东西。
所以我的问题是我可以在哪里 find/how 建立一个快速的方法来计算这个 "modified" jpeg encoder/decoder 的 8 点 1d dct 变换。对此的任何帮助将不胜感激。
好吧，至于我为什么要这样做，主要的原因是我想在我的网站上有"interactive"手机视频。这无法完成，因为 iOS 每次开始播放视频时都会加载它的 "native" 快速播放器。此外，当您几乎无法控制视频的呈现方式（尤其是在移动设备上）时，也很难过渡到视频的另一个时间点 "smooth"。
再次感谢您提供的任何帮助！
So my question is where can I find/how can I build a fast way to compute an 8 point 1d dct transform for this "modified" jpeg encoder/decoder. Any help with this would be greatly appreciated.
看看 flash 世界和那里的 JPEG 编码器（在它被集成到引擎中之前）。
例如：http://www.bytearray.org/?p=1089（提供的来源）这段代码包含一个名为 fDCTQuant() 的函数，它执行 DCT，首先是行，然后是列，然后它量化块（所以基本上你有你的 8x1 DCT）。
So what I'm doing is I send the first frame compressed as a jpg. Then I send another Jpeg image ...
看看渐进式 JPEG。我认为一些事情是如何工作的，以及数据流是如何构建的，听起来有点熟悉这个描述（不一样，但它们都在相关的方向上。imo）
what if I could modify this so that it not only compresses "each" 8x8 block, but it also checks to see if the "next" 8x8 block is similar to the first one. If it is close enough then just send the first block and use the same data for both blocks.
表达式 "similar" 和 "close enough" 在这里引起了我的注意。看看通常使用的量化表。您知道，根据 8x8 块中的位置以及所应用的量词，将值更改 1 很容易导致该点的亮度值发生 15% 的变化（对于色度通道，通常甚至更多）。
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
所以你应该真正体贴"close enough"。
总结一下：基于 jpeg 的视频编解码器利用帧之间的差异来减少数据量。这对我来说也有点耳熟。
知道了：MPEG https://github.com/phoboslab/jsmpeg
*与参考代码或编码器没有联系
这本书展示了如何将 DCT 矩阵因式分解为高斯范式。那将是执行 DCT 的最快方法。
我在这里实现了各种大小的可分离整数 2D DCT（以及其他变换）：https://github.com/flanglet/kanzi/tree/master/java/src/kanzi/transform。代码在 Java 但实际上对于这种算法，它在任何语言中都几乎相同。 IMO 最有趣的部分是您在计算每个方向后进行的重新缩放。根据您的目标（最大精度、16 位计算、无缩放等），您可能想要更改每个步骤的缩放因子。在图像非常均匀的区域使用更大的块可以节省位。