FFTが10倍速に！　フーリエ変換の新アルゴリズムをMITが開発

200年の歴史を持つ数学公式が改良されるなんて、めったにあることではない。フーリエ変換は最初、1811年にジョゼフ・フーリエというフランス人が提唱したが、
しかしその真価が認められたのは20世紀の半ばになってからだ。彼のテクニックは複雑な信号を複数の成分信号に分解してそのそれぞれを別々に送信ないし
処理し、それらを合成して元の信号を無傷で作り出せる、というものだ。

1965に、フーリエ変換が急にもてはやされる事件が起きた。それはJames CooleyとJohnが、この変換をコンピュータを使ってリアルタイムで行うやり方を発見したことだ。
そして今年、2012年には、また新たな重要な改良が提唱された。

フーリエ変換を理解するのは、難しくはない。たとえば、音楽を送信したくても、個々の楽器や個々の周波数成分を別々に送ることはできない。そこで、すべての
周波数成分を積み重ねて一つの信号にする。それは個々の周波数成分よりも複雑な形をしているが、受信側ではそれを解釈できる。複雑な信号をその
成分周波数に分解する処理を、フーリエの方法を使って行い、それらの成分周波数から元の信号を合成する処理はフーリエ逆変換で行う。こうやって
エンコード/デコードできるのは音声だけではなく、たとえば画素（ピクセル）が色などをビットの値で表している信号だと考えると、画像やビデオもこの方法で表現できる。
というわけで、今やフーリエ変換/逆変換は至るところで使われている。

しかし、歴史が古く、広範に使われているこの方法も、アルゴリズムには改良の余地がある、とMITの研究者たちは考えた。1965年に確立した、デジタルの、
つまり“離散的な”フーリエ変換は、効率がそれほど良くない。そして研究者たちは、8×8(==64)の数値ブロックのうち、57は無視できる、無視しても画像の質に
悪影響は現れないことを見つけた。
...

家畜に神はいないッッ！！

アルマッ！！！

人の夢と書いてぱんつはかない

ただしそれは、単純に要らないものを捨てるという話ではなく、その新しいテクニックは元の信号を複数の小さな信号に
分解する方法を変えることによって、重要な信号とそうでない信号を容易に選り分けられるようにしている。
そして信号を構成するビット数を削減して、必要な部分だけ残すのだ。

こんな話がなぜ、TechCrunchに載るのか？　それは、FaceTimeやSpotifyを支えているのも、このような研究だからだ。それは、
多くのスタートアップの誕生も、支えている。このような、信号処理のもっとも基本的な部分の改良は、数年後ないし数十年後に
実用のレベルに大きな影響が現れる。まだこの改良アルゴリズムは無名だが、信号の圧縮と送信の速度をこれまでの10倍は
速くするという。携帯電話で、4K(==4000×2000)のビデオを撮れる/送れるようになるかな？　また、オーディオやビデオの高速で
高品質なストリーミングを、狭い帯域でできるようになるかもしれない。それとも、Wi-Fi上で高速なビッグデータ処理ができる？　

今はまだ何とも言えないけど、ファンダメンタルの改良が実用レベルに影響を及ぼさないことは、ふつうありえないからね。

研究論文を書いたのは、MITコンピュータ科学人工知能研究所(MIT CSAIL)のDina KatabiとPiotr Indyk、
そして彼らの学生のEric PrinceとHaitham Hassaniehだ。まだ一般公開はされていないが、ここで読むことができる。
http://jp.techcrunch.com/archives/20120118improvement-on-age-old-mathematical-principle-could-yield-improved-images-video/
http://arxiv.org/abs/1201.2501v1
http://arxiv.org/PS_cache/arxiv/pdf/1201/1201.2501v1.pdf

はよ続き

盗める確率は０パーセントと表示されるがこのゲームでは小数点以下を切り捨てているため、
実際は小数点以下の確率で盗める。気が遠くなるほど低い確率だがゼロではない。
十分にレベルを上げ、即死や吸血を防ぐアイテム類を完璧に揃え、何度も何度も挑戦すれば盗むことが可能。
盾を壊すことができれば回避率が下がるため、盗める確率が多少上がる。

“悪事”というのか！？おまえは“悪事”というのかッ！！
おまえはベオルブ家の人間だ！ベオルブ家の人間には果たさねばならン責任がある！
その責務を、おまえは “悪事”というのかッ！！この愚か者めッ！

あ？ラムザ様に逆らうのか？

>>7
絶対に許さない

オルランドゥがさらに速くなるのか
胸が熱くなるな

オベェリア様あああああああ

きたか…！！

　　( ﾟдﾟ )　ｶﾞﾀｯ
　　.r　　ヾ
＿_|_|　/￣￣￣/＿
　　＼/＿＿＿/

目が疲れるから3行で教えろ

あたしのベーゼ

　　　　　　　　　　　　　　　.　　‐…　　　　‐-　 .
　　　　　　　　　 .　'ﾞ　　　　　　　　　　　　　　　　.　　　　　ヒック
　　　　　　　　　　　,″　,　　; 　,　　　　　　　　　　　　ヽ、
　　　　　　　　 /　 i/　　 i//　　　　　 ,'　　　　　　　　、　　}}
　　　　　　　　　　’　 ili　　　i/　　　　　 /　　　　ｯ'ｬ　 .
　　　　　　 .′i　iｌｉi　　　ｉ//　　　 /　　　 ,　　//公.　 !　　　__「 |__◎
　　　　　　　　//　l　iｌｉ|　　　ｉ//　　　/　　／　　//　　|ｉ￤　　[___　___]
.　　　　　　　//　 il　i|ﾘ　　ｉ i{//　 //　／　　／'/.　　 |ｌ￤　くイ　ト〉　　／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　 .　　　iｌ仙’　ｉｉｌｌﾚ　_/厶ィ'´　／ //　　　 |ｌ　| 　　 └┘　　　 |　　この身、貴公に預けると言ったはず。
　　　　　 :ｉ:　　ｉｌ/ |ｉ　　ｌｌｌ|___/'７i_ﾉ　／　 // ` ー‐ ﾘ　l　　　 ┌─‐┐　＼_　＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　　　ｉｌｉ　　i}{.( |!　　ｌｌ |㌃冖芹丐^ 　〈/　ﾃ丐㍉ｉｉ |　　　 │匸l　|　　　 }/
　　　　　 ||li　ｉｌ|人_|　　ili 北. _ 弋ｒっ　　　　　_ﾋｒっｨｌｌ |　　　 └─‐┘
　　　　　 |ｌｉ　 }iミ刈　　il　|Ⅳ/Xx　i　　　　　 xXx{ ! : l
.　　　　 /{i 　ﾘミiI{|　　ｉ　ｌ|　　　　ｉ　　　　 ,　　　φ　ｉ |　　　　　__「 |__◎
　　　　 fい　　ⅥＩi| 　ｉ　ｉｌ　　　　ｏ　　　　　　　　人　i/　　}}　　[___　___]
　　　　　　ﾘ }ﾊ.　　刄| 　 i　ｉ|＼　　　ｃ～ｰっ　 .o个ili　i{ 　　　くイ　ト〉
. 　　　〃/{　}ｉ　ｉ /i| 　 i　ｌ|＼｀　., 　　　　 .イ　　り|!　ｌ|　　　　　　└┘　┌─‐┐
　　　　ｉl {　Vｶi　i { ilii　 i　ｌ|i:i:ｉ＼＿｀T瓜__　厶≠…| 　ｌ|　　　　　　　　 │匸l　|

ガフ・ガフガリオン

つまりラムザが叫び続けてずっと俺のターン状態か

>>7
泣きながらやってたわー

友達が取れたーとかいうデマ言ってて必死になってやった。
その友達とはその事件以降口きいてない

港町で出会うランスロットが既に廃人

名にこの糞改行

＞今はまだ何とも言えないけど、ファンダメンタルの改良が実用レベルに影響を及ぼさないことは、ふつうありえないからね。

急にうざい

マジか
サクサク更新されるFFTあると周波数解析やり易いな

アグリアスよりアルテマだろうが糞が

フーリエ変換ってよく分からないんだけど、あれって多倍長整数の乗算でも使われたりするんだろ？
そうするとこれで更に速くなったりするの？

思っていた内容とソースが全然違った

さすがMITだ

自分の命が大切なのは分かる！だけどそういうものなのか！

>>16
かわいい

ＦＴＩＲが捗るな

キーワード：小数点以下の確率
抽出レス数：1>>1
お前がこっち来いよ
移動ついでに運営に県名表示させといてくれ

書いてることがわからない俺は低脳だと思い知った
記事は久々ｗ

エクスカリバーいらねえな

昔やったけど忘れちまった

ムスタディオをやっつけろ(ハート

ガフガフガフガフガフガリオン

フリアエ！フリアエ！フリアエ！フリアエ！

エミュでできますし

おお凄いと思ってスレ開いて唖然
まあそうだわな
FFTと聞いて高速フーリエ変換しか連想しない俺が異端なんだ

けんもう民なんて結局はアフィ速民
アホばっかだから
FFTといったらファイナルファンタジータクティクスだわな

圧縮率も上がるのか？
マルチメディア全般に影響与えそうだな

いやこれ結構凄いぞ
maxとかopenmusic用に誰か書き直してくれ

>>1
俺は昔から波形を縦読みすれば圧縮できると思ってた
横読みでしか圧縮してこなかったのに何を今さらって気がする

今やってるけど、負けまくり。
ジョブチェンジってどんどんやった方がいいの？

僕にこの手を汚せと言うのか

これで、午後のコーダでのｍｐ３変換がまた早くなるね。

>>16
ペロペロ

NMRが捗るな

げんじのこてがどんどん盗まれるな

今更、FFTが10倍速になってもゲームかグラフィックの専門家でもない限り
困っていないだろう。
解析結果の画像処理が早いと喜ぶ一部の理系はもしかすると狂喜乱舞？

おまえらが何の話してんのかさっぱりわからん
FFTが高速化ってことはモバイル機器や研究レベルのシミュに効果が出るのかな
送受信が速くなるっても容量は変わらんよね

10倍も試行回数増やせばさすがに盗めそうだな

一昔前のガチで低スペックな計算機上だったら歓喜だったろうけど
今のCPUやGPUの計算速度でそこまで喜ぶべき発見なのかは疑問

主人公以外全員赤チョコボ。それが最強パーティです

あーMP3で上のほうを削るというのはそういうわけだったの

FFFTになるのか

エクスカリバーでバランス崩壊してるのに１０倍速とかどんだけ

フーリエとかラプラスとかもっと真面目に勉強したほうが良かったですか？
いまからでもできないことはないが

アセンブリで書いたFFTライブラリを見た時はちょっと感動した

>>39
いやFFTはfast fourie transほにゃららでしょ
理工系なら絶対知ってるし
まさかFF10と思ってるやついるの？

ファイナルファイト・タフだろ

>>39
前にもスレ立ってたような…

リオファネス城のウィーグラフお前は許さん

これDCTとかにも応用できるの？
最近の圧縮方式からみると他の計算量のが多いからあんま役に立てそうにないな

FFTのライブラリとかCUDAとかにすでにあったはずだが、あれが速くなってひゃっほい状態になるのか

ヘイスガ何回重ねがけすればいいんですか？

そうかエロ画像にFFTかければいいのか

おいこれやべえんじゃねえか？すげえ研究が出てきたな

要するに割れが捗るのか

なんだロスレスじゃないのか
数値計算には向かないな

つまりこれ使ったらどういうプログラムが早くなるんだよ

DFTとFFTって何が違うの？教えてエロイ人

>>39
あいたたた…

>>39
うるせえグレバドス教会ぶつけんぞ

ラプラス変換でなんで微分方程式とけるのかいまだに理解できん
まぁ数学なんて暗記だし別にいいわ

長くてもソースURLはちゃんと>>1に入れてから2以降に続けてね

動画をフーリエ変換して送信するの？

高速フーリエ変換じゃないのか？

c13がすぐできるの？

フーリエ変換は出来るし
FFTも道具として使ってるけど
FFTのアルゴリズムはさっぱり理解できない
マジキチ

http://www.poverty.jeez.jp/loda/img/iyan18191.jpg

ムスタディオをやっつけろ♥

なんだ劣化させるだけか

> 8×8(==64)の数値ブロックのうち、57は無視できる、無視しても画像の質に
>悪影響は現れないことを見つけた。

これじゃ用途は限られるんじゃないか？

この形式のゲームって他になにがあんの？
これより後に出たやつで面白いのある？

>>83
どう読んでも映像用途前提

iPad版まだ？

（快適になるよう）努力はしている！

ファイナルファンタジータクティクスが今さら１０倍早くなったからなんだという感じ

やっと、ipadでてきるようになるのか

ｆｆｔｗつかってます

>>83
単純に10倍速くなったわけじゃないんだな。
映像の分野に限るってことですね

>>84
ゲームで使うのかな？
ゲームの中の動画とか静止画とか音楽っていうのは無しでｗ

上で10倍早くなってどうするんだって人いるけど、見方を変えれば
余計な処理を減らせるのでプロセッサを動かす時間を短くできる
つまり消費電力削減にもつながるんだけどな

まあ映像クオリティあげまくって相殺されるんだろうけどｗ

OFDM信号のサブキャリア数をさらに増やせたりするのかな

>>8
ガフガフガフガフガフガフガフガフガリオンは俺も好きなンだよなあ

つまり動画のエンコが早くなるのか？

よく見てないけど映像の非可逆圧縮からの輸入とかではないの？

係数0の周波数成分についてはそもそも変換する必要無いですよねー
ということっぽいけど、論文なげえ。ギブ。

早くミクの音源に入れろ

>>97
今までは係数0とか、影響の無い周波数成分を計算後に除外してたけど
計算する前に除外すればいいじゃん
って話っぽいな

適用できるのは周波数成分をわざとフィルタリングしてるような用途で
帯域全部見なくちゃならない計測とかには関係薄そう。

うーん？？？？

・n個の周波数軸があってもk個の周波数成分のみが係数をもつ（閑散―sparse)
・なら最初っからk個の成分だけ計算すれば早くなるよね
・じゃあ係数をもつk個の成分をどうやって見つけるか？
・位相スペクトルで判定する。
窓を通せばスペクトルのbroadingが変化するから、複数の窓を通したデータを作るのと、
時間遅延の異なる2サンプルの位相スペクトルをみて、
信号スペクトルのbroadingで位相スペクトルが変化したのか否かを判定して、
係数0の周波数成分を特定する？

>>16
俺の嫁は今日もかわいいな

こっちはＦＦＴスレにしてよ
本スレがあるじゃないか

フーリエ変換とファイナルファンタジータクティクスの間を反復横飛びしてスレがわけわからない

計算機のFFTスレなんて需要ないだろ。でも専門板で、と思ったけど専門板見ても話題なかった。
こういうのはスラッシュドットなりで詳しい人出てくるのを待つのが賢明だわ。

そもそもFTしてる時点でビットデータはある程度失われてるんだから
結局動画配信や再生が早くなるくらいだろうなぁ

>>5
論文を読んでみた
こりゃすげーわ

なんだ、10倍速いFFTアルゴリズム見つけたならスゲーけど、これ違うじゃん。

内容把握してないメルカトル状態だが
・信号帯域が未知で、信号と雑音が明確に分離されてる場合には有効
・信号帯域が既知なら、帯域削ってからFFTとフィルタリングすりゃええんじゃねえの？

でも、こんな特化して処理すらイイじゃんって考えてるから、
汎用な方法で楽にって考えの所で外人に負けちゃうんだろうなあ。

あーあ
先にやられたな

JPEGみたく、人間の感覚には影響少ない部分を間引くってことかな
全ての対象において有効ってことじゃなさそうだ
残念

うんたん♪が10倍速になるのか

送信するデータの量を減らすことができるというわけか
動画がこれで軽くなるといいんだが

PSP版の処理落ちは許さない