草庐IT

c++ - 傅里叶变换浮点问题

coder 2024-02-26 原文

我正在为图像实现传统的(这意味着不快)分离傅立叶变换。我知道在浮点数中,等距样本中一个周期的 sin 或 cos 的总和并不完全为零,这对于传统变换来说更像是一个问题,而不是快速变换。

该算法适用于二维双数组并且是正确的。逆是在内部完成的(在使用不对称公式时通过双符号标志和条件检查),而不是在外部使用共轭。结果几乎 100% 像预期的那样,所以这是一个关于细节的问题:

当我执行正向变换、将对数幅度和角度保存到图像、重新加载它们并进行逆变换时,我会遇到不同类型的舍入误差和不同类型的实现公式:

  • F(u,v) = Sum(x=0->M-1) Sum(y=0->N-1) f(x,y) * e^(-i*2*pi*u*x/M) * e^(-i*2*pi*v*y/N)

    f(x,y) = 1/M*N *(同上)
  • F(u,v) = 1/sqrt(M*N) *(如上)

    f(x,y) = 1/sqrt(M*N) *(如上)

  • 所以第一个是非对称变换对,第二个是对称变换对。对于不对称对,舍入误差更多地出现在图像的亮点中(一些像素被舍入到略微超出值范围(例如 256))。对于对称对,在图像的恒定中间范围区域中误差更大(不超过值范围!)。总的来说,对称对似乎会产生更多的舍入误差。

    然后,它还取决于输入:当图像存储在 [0,255] 中时,舍入误差与在 [0,1] 中时不同。

    所以我的问题是:如何实现最佳、最准确的算法(理论上,没有代码):非对称/对称对? [0,255] 或 [0,1] 中输入的值范围?在将对数保存到文件之前如何线性放大结果?

    编辑 :

    我的算法只是计算分离的非对称或对称 DFT 公式。使用欧拉恒等式将因子分解为实部和虚部,然后分别展开并汇总为实部和虚部:
    sum_re += f_re * cos(-mode*pi*((2.0*v*y)/N)) - // mode = 1 for forward, -1
              f_im * sin(-mode*pi*((2.0*v*y)/N));  // for inverse transform
    // sum_im permutated in the known way and + instead of -
    

    这个值分组 indside cos 和 sin 在我看来应该给出最低的舍入误差(与例如 cos(-mode*2*pi*v*y/N) 相比),因为不是多次乘以/除以显着的错误舍入超越 pi,而是只有一次。不是吗?

    比例因子 1/M*N1/sqrt(M*N)在最里面的和之外的每次分离之后单独应用。里面更好?还是在两次分离结束时完全合并?

    为了更深入的分析,我已经退出了 input->transform->save-to-file->read-from-file->transform^-1->output工作流程并选择直接以 double 进行比较:input->transform->transform^-1->output .

    这里是现实生活中 704x528 8 位图像的结果(delta = 输入和输出实部之间的最大绝对差):
  • 输入在 [0,1] 和不对称公式中:delta = 2.6609e-13(对应于 [0,255] 范围的 6.785295e-11)。
  • 输入 insde [0,1] 和对称公式:delta = 2.65232e-13(对应于 [0,255] 范围的 6.763416e-11)。
  • 输入在 [0,255] 内且不对称公式:delta = 6.74731e-11。
  • 输入在 [0,255] 内,对称公式:delta = 6.7871e-11。

  • 这些都没有真正的显着差异,但是,具有非对称变换的全范围输入表现最佳。我认为 16 位输入的值可能会变得更糟。

    但总的来说,我看到,我遇到的问题更多是因为在保存到文件之前缩放(或逆)舍入错误,而不是真正的转换舍入错误。

    但是,我很好奇:傅里叶变换最常用的实现是什么:对称还是不对称?输入通常使用哪个值范围:[0,1] 或 [0,255]?通常以对数标度显示光谱:例如[0,M*N] 在 [0,1] 输入的非对称变换之后直接对数缩放到 [0,255] 或在线性缩放到 [0,255*M*N] 之前?

    最佳答案

    您报告的错误很小,很正常,通常可以忽略。只需缩放您的结果并将目标间隔之外的任何结果限制到端点。

    在 FFT 的库实现中(即,编写供不同应用程序普遍使用的 FFT 例程,而不是为单个应用程序定制设计),很少考虑缩放;该例程通常只返回由算术自然缩放的数据,不使用额外的乘法运算来调整缩放。这是因为尺度通常与应用无关(例如,无论尺度是什么,找到具有最大能量的频率都有效),或者尺度可能通过乘法运算分布并仅执行一次(例如,而不是缩放在正向变换和逆向变换中,应用程序可以通过显式缩放一次来获得相同的效果)。因此,由于通常不需要缩放,因此将其包含在库例程中毫无意义。

    数据缩放到的目标间隔取决于应用程序。

    关于使用什么变换(对数或线性)来显示光谱的问题,我不能建议;我不使用可视化光谱。

    关于c++ - 傅里叶变换浮点问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20551707/

    有关c++ - 傅里叶变换浮点问题的更多相关文章

    1. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

      我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库,所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

    2. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

      尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

    3. ruby-on-rails - 如何优雅地重启 thin + nginx? - 2

      我的瘦服务器配置了nginx,我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例,但找不到好的解决方案。有没有人能做到这一点? 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器,例如server{listen80;server

    4. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

      我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止,这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

    5. ruby - Fast-stemmer 安装问题 - 2

      由于fast-stemmer的问题,我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

    6. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

      当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

    7. java - 从 JRuby 调用 Java 类的问题 - 2

      我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java,并成功地将它与另一个Java包一起使用,但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

    8. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章? - 2

      我意识到这可能是一个非常基本的问题,但我现在已经花了几天时间回过头来解决这个问题,但出于某种原因,Google就是没有帮助我。(我认为部分问题在于我是一个初学者,我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI,但我仍然停留在这个问题上.我找到了一些关于多态关系的信息,但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

    9. 【高数】用拉格朗日中值定理解决极限问题 - 2

      首先回顾一下拉格朗日定理的内容:函数f(x)是在闭区间[a,b]上连续、开区间(a,b)上可导的函数,那么至少存在一个,使得:通过这个表达式我们可以知道,f(x)是函数的主体,a和b可以看作是主体函数f(x)中所取的两个值。那么可以有,  也就意味着我们可以用来替换 这种替换可以用在求某些多项式差的极限中。方法: 外层函数f(x)是一致的,并且h(x)和g(x)是等价无穷小。此时,利用拉格朗日定理,将原式替换为 ,再进行求解,往往会省去复合函数求极限的很多麻烦。使用要注意:1.要先找到主体函数f(x),即外层函数必须相同。2.f(x)找到后,复合部分是等价无穷小。3.要满足作差的形式。如果是加

    10. ruby - 使用 `+=` 和 `send` 方法 - 2

      如何将send与+=一起使用?a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法,而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

    随机推荐