3

所以我玩了一下 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# 编写的，但是任何语言都足够了，因为它都是基本操作并且可以很容易地翻译。

4

2 回答 2

1

1.你有固定的输入大小

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

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 和子弹 2
  • 是 O((N^2).log(N)) 左右的复杂度

4.放弃FPU乘法

  • 您可以获取所有权重并将它们转换为 a1=a0*1024
  • 或任何其他面具

  • 所以：

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

  • 输入数据也可以这样做

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

4.抛弃整数乘法

  • 您可以通过移位和加法操作放弃所有乘法（查找二进制乘法）
  • 但是在现代机器上，这实际上会减慢速度
  • 当然，如果你在一些逻辑板/IO上接线，那么它有它的优点
于 2014-01-31T10:15:32.173 回答
0

我对应用矩阵的唯一理解与操纵 3D 向量有关，所以我不直接知道您的问题的答案。但是在环顾四周时，我确实找到了指向解决您的特定问题的博客的链接。底部的评论来自一群人，他们可能是一个很好的资源池，可以与在该领域有知识的人聊天。此外，如果您点击链接，就会有很多很好的图像压缩信息。

作者似乎大量参与了照片取证。他解释了 pHash 如何比平均散列更健壮，并提到使用 32 x 32 矩阵。

这可能是一个非常好的起点。小心。

http://www.hackerfactor.com/blog/?/archives/432-Looks-Like-It.html

于 2014-01-14T04:17:13.690 回答