package {
    import __AS3__.vec.Vector;
    import flash.display.*;
    import flash.text.*;
    import flash.geom.*;
    import flash.utils.getTimer;
    import flash.net.URLRequest;
    import flash.events.Event;
    import flash.system.LoaderContext;
    import flash.system.Security;
    import flash.filters.ConvolutionFilter;

[SWF(backgroundColor = "#000000", frameRate = "12")]

public class FFTImg extends Sprite
    {
        private var loader:Loader;
        private var srcBmp:Bitmap;
        private var fftBmp:Bitmap;
        private var dstBmp:Bitmap;
        private var imgData:BitmapData;
        private var buffData:BitmapData;
        private var fftTest:FFT;
        private var re:Vector.<Number>;
        private var im:Vector.<Number>;
        private var retmp:Vector.<Number>;
        private var max:Number = 0.0;
        private var data:Number = 0.0;
        private var w:int = 0;
        private var h:int = 0;

public function FFTImg()
        {
            Security.loadPolicyFile("http://farm2.static.flickr.com/crossdomain.xml"); 
            var context:LoaderContext = new LoaderContext(true);
            loader = new Loader();
            loader.contentLoaderInfo.addEventListener(Event.COMPLETE, onComplete);
            loader.load(new URLRequest("http://farm4.static.flickr.com/3177/3079570874_e816f409e3_m.jpg"),context);
        }
        private function onComplete(event:Event):void
        {
            var loaderInfo:LoaderInfo = event.currentTarget as LoaderInfo;
            var loader:Loader = loaderInfo.loader;
            var bmp:BitmapData = new BitmapData(loader.width, loader.height, false, 0xFFFFFF);
            bmp.draw(loader);
            srcBmp = new Bitmap(bmp);
            srcBmp.x = 0;
            srcBmp.y = 0;
            addChild(srcBmp);
            main();
        }

public function main():void
        {
            imgData = srcBmp.bitmapData.clone();
            w = imgData.width;
            h = imgData.height;
            fftTest = new FFT(w);
            re = new Vector.<Number>(w*h, true);
            im = new Vector.<Number>(w*h, true);
            retmp = new Vector.<Number>(w*h, true);
            // 画像データの直列化
            for(var y:int=0; y<h; y++) {
              for(var x:int=0; x<w; x++) {
                re[x + y*w] = imgData.getPixel(x, y) & 0xFF;//1chだけ
              }
            }

// 2D-FFT
            fftTest.fft2d(re, im);
            // 空間周波数フィルタ
            //fftTest.applyFilter(re, im, w/16, FFT.LPF);

// スペクトルの振幅を計算
            for(var i:int=0; i<w*h; i++) {
              retmp[i] = Math.log(Math.sqrt(re[i]*re[i] + im[i]*im[i]));
              if(retmp[i] > max) max = retmp[i];
            }

// 8ビットに正規化 (表示用)
            for(var ibit:int=0; ibit<w*h; ibit++) {
              retmp[ibit] = retmp[ibit]/max*255;
            }

// 振幅画像の生成
            for(var ysp:int=0; ysp<h; ysp++) {
              for(var xx:int=0; xx<w; xx++) {
                data = retmp[xx + ysp*w];
                if(data>255) data = 255;
                if(data<0) data = 0;
                var color:uint = data<<16 | data<<8 | data;
                imgData.setPixel(xx, ysp, color);
              }
            }
             // 象限の入れ替え
             /*
            buffData = new BitmapData(w, h, false);
            buffData.copyPixels(imgData, new Rectangle(w/2, 0, w/2, h/2), new Point(0, h/2)); // 1 -> 3
            buffData.copyPixels(imgData, new Rectangle(0, 0, w/2, h/2), new Point(w/2, h/2)); // 2 -> 4
            buffData.copyPixels(imgData, new Rectangle(0, h/2, w/2, h/2), new Point(w/2, 0)); // 3 -> 1
            buffData.copyPixels(imgData, new Rectangle(w/2, h/2, w/2, h/2), new Point(0, 0)); // 4 -> 2
            imgData = buffData.clone();
            buffData.dispose();
            */
            fftBmp = new Bitmap(imgData);
            addChild(fftBmp);

// 逆2D-FFT
            //fftTest.fft2d(re, im, true);

// 8ビットに正規化 (表示用)
            /*
            max = 0.0;
            for(var i1:int=0; i1<w*h; i1++) {
              if(re[i1] > max) max = re[i1];
            }
            for(var i2:int=0; i2<w*h; i2++) {
              re[i2] = re[i2]/max*255;
            }

// 出力画像の生成
            for(var yout:int=0; yout < h; yout++) {
              for(var xout:int=0; xout < w; xout++) {
                data = re[xout + yout*w];
                if(data>255) data = 255;
                if(data<0) data = 0;
                color = data<<16 | data<<8 | data;
                imgData.setPixel(xout, yout, color);
              }
            }
            dstBmp = new Bitmap(imgData);
            */
            //addChild(dstBmp);
            srcBmp.x = 0;
            srcBmp.y = 0;
            fftBmp.x += w;
            //dstBmp.y += h;

/*
            var kernel2:Array = [
                            2, 2, 2, 
                            2, 0, 2, 
                            2, 2, 2
                        ];

var filter:ConvolutionFilter = new ConvolutionFilter( 3, 3, kernel2, 9 );
            var rect:Rectangle = new Rectangle(0,0, srcBmp.bitmapData.width, srcBmp.bitmapData.height);
            var point:Point    = new Point(0,0);
            srcBmp.bitmapData.applyFilter( srcBmp.bitmapData, rect, point, filter );
            */
        }
 
    }
}
    //内部クラス http://rest-term.com/archives/1289/
    class FFT{
        private var n:int; // データ数
        private var bitrev:Vector.<int>; // ビット反転テーブル
        private var cstb:Vector.<Number>; // 三角関数テーブル
        public static const HPF:String = "high";
        public static const LPF:String = "low";
        public static const BPF:String = "band"
 
        public function FFT(n:int) {
            if(n != 0 && (n & (n-1)) == 0) {
                this.n = n;
                this.cstb = new Vector.<Number>(n + (n>>2), true);
                this.bitrev = new Vector.<int>(n, true);
                makeCstb();
                makeBitrev();
            }
        }
        // 1D-FFT
        public function fft(re:Vector.<Number>, im:Vector.<Number>, inv:Boolean=false):Boolean {
            if(!inv) {
             return fftCore(re, im, 1);
            } else {
                if(fftCore(re, im, -1)) {
                    for(var i:int=0; i<n; i++) {
                        re[i] /= n;
                        im[i] /= n;
                    }
                }
            }
            return true;
        }
        // 2D-FFT
        public function fft2d(re:Vector.<Number>, im:Vector.<Number>, inv:Boolean=false):Boolean {
            var tre:Vector.<Number> = new Vector.<Number>(re.length, true);
            var tim:Vector.<Number> = new Vector.<Number>(im.length, true);
            if(inv) cvtSpectrum(re, im);
            // x軸方向のFFT
            for(var y0:int=0; y0<n; y0++) {
                for(var x1:int=0; x1<n; x1++) {
                    tre[x1] = re[x1 + y0*n];
                    tim[x1] = im[x1 + y0*n];
                }
                if(!inv) fft(tre, tim);
                else fft(tre, tim, true);
                for(var x2:int=0; x2<n; x2++) {
                    re[x2 + y0*n] = tre[x2];
                    im[x2 + y0*n] = tim[x2];
                }
            }
            // y軸方向のFFT
            for(var x3:int=0; x3<n; x3++) {
                for(var y1:int=0; y1<n; y1++) {
                    tre[y1] = re[x3 + y1*n];
                    tim[y1] = im[x3 + y1*n];
                }
                if(!inv) fft(tre, tim);
                else fft(tre, tim, true);
                for(var y2:int=0; y2<n; y2++) {
                    re[x3 + y2*n] = tre[y2];
                    im[x3 + y2*n] = tim[y2];
                }
            }
            if(!inv) cvtSpectrum(re, im);
            return true;
        }
        // 空間周波数フィルタ
        public function applyFilter(re:Vector.<Number>, im:Vector.<Number>, rad:uint, type:String, bandWidth:uint = 0):void {
            var r:int = 0; // 半径
            var n2:int = n>>1;
            for(var y:int=-n2; y<n2; y++) {
                for(var x:int=-n2; x<n2; x++) {
                    r = Math.sqrt(x*x + y*y);
                    if((type == HPF && r<rad) || (type == LPF && r>rad) || (type == BPF && (r<rad || r>(rad + bandWidth)))) {
                            re[x + n2 + (y + n2)*n] = im[x + n2 + (y + n2)*n] = 0;
                    }
                }
            }
        }
        private function fftCore(re:Vector.<Number>, im:Vector.<Number>, sign:int):Boolean {
            var h:int, d:int, wr:Number, wi:Number, ik:int, xr:Number, xi:Number, m:int, tmp:Number;
            for(var l:int=0; l<n; l++) { // ビット反転
                m = bitrev[l];
                if(l<m) {
                    tmp = re[l];
                    re[l] = re[m];
                    re[m] = tmp;
                    tmp = im[l];
                    im[l] = im[m];
                    im[m] = tmp;
                }
            }
            for(var k:int=1; k<n; k<<=1) { // バタフライ演算
                h = 0;
                d = n/(k<<1);
                for(var j:int=0; j<k; j++) {
                    wr = cstb[h + (n>>2)];
                    wi = sign*cstb[h];
                    for(var i:int=j; i<n; i+=(k<<1)) {
                        ik = i+k;
                        xr = wr*re[ik] + wi*im[ik]
                        xi = wr*im[ik] - wi*re[ik];
                        re[ik] = re[i] - xr;
                        re[i] += xr;
                        im[ik] = im[i] - xi;
                        im[i] += xi;
                    }
                    h += d;
                }
            }
            return true;
        }
        // スペクトル位置並び替え
        private function cvtSpectrum(re:Vector.<Number>, im:Vector.<Number>):void {
            var tmp:Number = 0.0, xn:int = 0, yn:int = 0;
            for(var y:int=0; y<(n>>1); y++) {
                for(var x:int=0; x<(n>>1); x++) {
                    xn = x + (n>>1);
                    yn = y + (n>>1);
                    tmp = re[x + y*n];
                    re[x + y*n] = re[xn + yn*n];
                    re[xn + yn*n] = tmp;
                    tmp = re[x + yn*n];
                    re[x + yn*n] = re[xn + y*n];
                    re[xn + y*n] = tmp;
                    tmp = im[x + y*n];
                    im[x + y*n] = im[xn + yn*n];
                    im[xn + yn*n] = tmp;
                    tmp = im[x + yn*n];
                    im[x + yn*n] = im[xn + y*n];
                    im[xn + y*n] = tmp;
                }
            }
        }
        // 三角関数テーブル作成
        private function makeCstb():void {
            var n2:int = n>>1, n4:int = n>>2, n8:int = n>>3;
            var t:Number = Math.sin(Math.PI/n);
            var dc:Number = 2*t*t;
            var ds:Number = Math.sqrt(dc*(2 - dc));
            var c:Number = cstb[n4] = 1;
            var s:Number = cstb[0] = 0;
            t = 2*dc;
            for(var i:int=1; i<n8; i++) {
                c -= dc;
                dc += t*c;
                s += ds;
                ds -= t*s;
                cstb[i] = s;
                cstb[n4 - i] = c;
            }
            if(n8 != 0) cstb[n8] = Math.sqrt(0.5);
            for(var j:int=0; j<n4; j++) cstb[n2 - j] = cstb[j];
            for(var k:int=0; k<(n2 + n4); k++) cstb[k + n2] = -cstb[k];
        }
        // ビット反転テーブル作成
        private function makeBitrev():void {
            var i:int = 0, j:int = 0, k:int = 0;
            bitrev[0] = 0;
            while(++i<n) {
                k= n >> 1;
                while(k<=j) {
                    j -= k;
                    k >>= 1 ;
                }
                j += k;
                bitrev[i] = j;
            }
        }

}

fftimg