二次元FFTを使ってぼかしフィルタをかけてみました。 128x128x(R,G,B)で、New3DSで17秒かかりました。

お絵かきツールのぼかしペンにするにはちょっと重いか。 プチコンの処理系は独特だから、アルゴリズムをそれに合わせて変更すればもう少し早くはなりそうだけどどこまでいけるのかねぇ

ほしい

れいさん 大浦FFTの速さにはビックリしましたが、さすがに二次元だと重いですね。ゼヒ 3.3 では(2Dまで)実装して欲しいです。 あと配列同士の演算(matlab の .* など)や配列のスラカ倍とか配列の総和があるといいなあ。配列もforも遅いんだからそのくらい組み込みでやっていただかないと。 ちくわさん フーリエ変換を使うメリットは、大きな画像全体にフィルタかける時、計算量が少なくて済むことなんですが、プチコンでそんなお殿様なコード書いたら、256x256でもメモリ不足エラーになってしまいました。それでもいいですか?

そ、そんなにメモリ食うんですか、それに速度面もあれだし、今更言うのもなんですが、やめときます、すみません。

おっと、試しに 16x16x3plain では 0.2sでした。 フィルタをフーリエ変換する分を除くと、0.17s です。 これならブラシとして使えないこともないですね。 正直に畳み込みするのとどっちが速いんだろう????

メモリをふんだんに使って実行速度を買うという、いわゆるお殿様スタイルですね。 複素数なんで 1 ピクセルあたり 16byte 使うし、フィルタの分も同じだけメモリ食うので大変です。

60/3=wait3、、、かなり重くなりそう、、、ペイントツールとかも速度重視の人にとってはイライラしそう、、、

え、フォトショって激遅なんじゃないの? 画像処理な人達は甘受してんじゃないの?? いや、詳しくは知らないけど。

フォトショ、使ったことがなi((((((

そりゃ遅いけどそれなりの速度はでるよ。 もともと速い環境でやるもんだし。 それにプチコンでも256x256でメモリ足りなくなるとかないと思うけど。

今256x256x3plainやったらできた。66s. 512x512は無理だった。前回はデバッグちゅうでリークがあったのかもね。

512x256x3plain 140s 400x240 全体を処理できました！

今更ながらぼかしフィルタが欲しくなってきました... まだプログラムは残ってますか？

これは FFT 使うんですけど、高度サウンドユニットは持ってますか? 持ってるならそれ使えばかなりはやくなるはず。 無ければ basic で書いた fft 使いますが、その場合は上記の時間(140秒)かかります。

持ってます。

それはよかった!! ただ高度SU用のプログラムは存在しないので、これから書かなければならないという・・・ ちくわさん、やりかた教えたら自分でかけますか?

やりかたを教えてください！後は何とかがんばりますので！

複素数って習いました? a + b*i (i=虚数単位 = √-1) まあ習ってなくても大丈夫。 数直線は習いましたよね? 1 とか 0 とか -√2 とか、全ての数は数直線上の一つの点で表せます。 複素数は、平面上の一つの点で表せる数です。 a + b*i という複素数は、平面座標のなかで x=a, y=b という一つの点で表せる数なのです。 面倒な理屈はどうでもいいのですが、一つの複素数を表すのに、二つの数a と b が必要だということを覚えてください。 プログラム言語によってはこの複素数を一つの変数で表せるものがあります。 でもプチコンでは複素数型という変数は無いので、 一つの複素数を表すには二つの実数型変数が必要になります。

うっ、頭が、、、

ちくわさんは中学生?? それとも小学生かな??

中2です。 さすがに数直線は中1でならいましたしわかりますが、配列とかあまりやってないので混乱しちゃうんですよね><

了解です。配列はコンピュータ用語だから数学では習いません。 では納得できなくてもいいから、以下を覚えてください。 1. FFT と IFFT は複素数の配列を入力として与えると、同じサイズの複素数の配列を返します。 FFT のヘルプ見ると FFT OWR, OWI, IWR, IWI とありますよね。この IWR, IWI が入力となる配列で、IWR[0] と IWI[0] が 0 番目の複素数 z0 を表します。IWR[1] と IWI[1] は 1 番目の複素数 z1 を表します。これは数学とは関係ないただの smilebasic での決まりなので、暗記事項となります。 同様に、FFTした結果は OWR と OWI 配列に返り、OWR[0] と OWI[0] が結果の複素数 z'0 を表し、 OWR[1]とOWI[1] がz'1を表します。

プチコンでの複素数の表し方が分かったところで次に進みます。 FFT は現実の配列をあの世送りし、 IFFT はあの世の配列をこの世に連れ戻す操作だと思ってください。 画像にフィルタを適用する方法は以下の通り。 1. 入力画像配列を FFT する(あの世送りする) 2. フィルタ係数配列(ガウシアンとかラプラシアンとか)をFFTする(あの世送りする) 3. 1であの世送りされた配列と、2であの世送りされた配列を、要素ごとに掛け算する(結果はやはりあの世の配列) 4. 3で計算したあの世の配列を IFFT でこの世に連れ戻します。 5. 4の結果の OWR が「入力画像にフィルタを適用した画像」になります。 なお、この世だけでちまちまちまちまちまちまと計算すれば同じ結果が得られます。ではなぜわざわざこんな面倒な手続きを踏んであの世この世を行き来するのかというと、

配列を格納するにはどうしたらいいんでしょうか? GSPOITですか？

あの世経由の方が圧倒的に速いからです。 メモリを多く使い速度を上げる手法。 gspoit でループをまわすと遅くなります。 var g%[0] gsave 0,0,400,240,g%,1 でいいんじゃないかなあ??

あ、ごめん FFT する都合で、幅も高さも2のべき乗じゃないとだめなんだった。 gsave 0,0,512,256,g%,1 でお願いします。

FFT入力でG%だけ入力して大丈夫ですかね...?

2次元FFTだと2個入力しないといけないのか....。

g% は IWR に入れます。 IWI には g% と同じ長さで、要素は全て 0 の配列を入れます。 でもまだ話は途中なんですよ。 高度SUについてくる FFT/IFFT は、一次元の複素数配列が対象なんですね。ところが画像というのは、二次元じゃないですか。 てことで、ちくわさんは 二次元版の FFT/IFFT を自作する必要があるのです。

...oh..no....

要素をすべて0にするということは、 G2%=G% FILL G2%,0 ですかね？

お、ちゃんと二次元FFTだってわかってましたね!! すばらしい!!! >G2%=G% これだとG2% とG%が同じ実体になってしまうのでは?? var g2%[len(g%)] で0に初期化された g2% が手に入るような気がします。

FILLをつかえるかと思ったのですが、、、 そんな方法があったとは...

うお、もうあのコメントから2週間か、、、 今更なんですが、2次元FFTの自作方法を教えてください。

自分がぼかしたい範囲は400×16で、使用メモリは102KBなのですが、足りますかね？？

もとのコード発掘したので、公開しますね。 file=fft2d key=j3n478ke load と gload してるのは、プロ生ちゃんの絵を表示してるだけなので、適宜書き換えてください。 M と N がフィルタかけるサイズです。 大浦fft なので、一つの複素数 z[i] を real = x[i * 2] imag = x[i * 2 + 1] で表しています。

ありがとうございます！