c# - 32x32 矩阵的 BinDCT 实现

Question

因此，我尝试了一些 DCT 实现，并注意到由于必要的乘数计算，它们(相对)较慢。

在谷歌搜索了一下之后，我遇到了 BinDCT，它产生了非常好的 DCT 近似值，并且只使用位移位。

在浏览有关它的论文(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.834&rep=rep1&type=pdf 和 http://www.docstoc.com/docs/130118150/Image-Compression-Using-BinDCT)并阅读我在 ohlo(http://code.ohloh.net/file?fid=vz-HijUWVLFS65NRaGZpLZwZFq8&cid=mt_ZjvIU0Us&s=&fp=461906&projSelected=true#L0)上找到的一些代码时，我注意到只有 8x8 矩阵的实现。

我正在为 32x32 矩阵寻找此 BinDCT 的实现，以便我可以将其用于感知哈希算法 (phash) 的更快变体。

我不是数学家，虽然我试图理解论文中发生的事情和我发现的 C 代码，但我还是无法理解如何转换此实现以应用于 32x32 矩阵。

有人写过吗？有可能吗？

我知道扩展实现需要更多的移位和 tmp 变量。但是，虽然我可以尝试和错误地尝试，但我连理论都不懂，所以我永远不知道我是否得到了正确的结果。

我是用 C# 写的，但是任何语言都可以，因为它都是基本操作，而且很容易翻译。

Answer 1

1.你有固定的输入大小

• 所以你一直乘以相同的权重
• 预先计算一次，然后只使用它们
• 这个沟渠所有的罪恶，因果操作

2.2D DCT 可以计算为 1D DCT(类似于 FFT)

• 首先对行进行 DCT
• 然后在 DCTed 行的列上
• 乘以归一化常数
• 所以这将 O(N^4) 转换为 O(N^3)

3.使用FastDCT

• 这很棘手
• 快速算法是 (I)DST 和 (I)DCT 的融合
• 关于它的论文很少
• 但是有模糊的(而且所有的方程在不同的论文中都是不同的而不是完整的)
• 实际上我最近看到了一个函数方程式，也没有为它编程
• 唯一几乎可行的方法是使用 FFT
• 但是对于小 N 来说，因为切换到复杂域没有任何好处
• 并且这些值并不是真正的 DCT，而是非常接近它。
• 当然我不是这个领域的专家所以我可以忽略一些东西
• 在所有数百页纸的方程式中
• 无论如何在快速算法实现 2D (I)DCT 和 bullet 2 之后
• 复杂度为 O((N^2).log(N))

4.放弃 FPU 乘法

• 你可以把所有的权重转换成a1=a0*1024
• 或任何其他面具

• 所以:

  x*a0 = (x*a1)/1024 = (x*a1)>>10
  

• 输入数据也可以这样做

• 所以现在只剩下整数运算了
• 但在现代机器上，这种方法可能比 FPU 使用速度慢(取决于平台和实现)

4.放弃整数乘法

• 您可以通过移位和加法运算(寻找二进制乘法)放弃所有乘法
• 但是在现代机器上这实际上会减慢速度吗
• 当然，如果您将其连接到某些逻辑板/IO 上，那么它有其优点