４分木と偏差を使って画像を分割する

**昔かいた記事ですが（ActionScript3）、発掘したので、ここに公開しておきます。**


４分木を使ったモザイク画をやってみます。
画像の平坦な領域（＝偏差が小さい）は大きな矩形、エッジの多い領域（＝偏差が大きい）は細かい矩形というような分割してみます。再帰的な処理でばんばん分割します。
偏差とは、サンプルの値と平均との差分です。そこから標準偏差とか求めるらしいですが、いまいちよくわからないので偏差の平均を基準値として用います。

![image.png](https://qiita-image-store.s3.amazonaws.com/0/17747/2573938c-dac8-83a2-451c-d7558ddb8645.png)

## やりかた

1. ある領域(x,y,w,h)の画像に対し、標準偏差的なものを求める。
2. 標準偏差が小さい場合(or 領域w,hが小さすぎる場合)は、平坦とみなし、領域内を平均色で塗りつぶし、終了。
3. 標準偏差が大きい場合は、エッジが多いとみなし、その領域を４分割し、その４つそれぞれに、また同じように計算をする。

##コード
Imgという画像処理用クラスをMainから呼んでます。

```as3:Main.as
package 
{
    import flash.display.Bitmap;
    import flash.display.BitmapData;
    import flash.display.MovieClip;
    import flash.display.PNGEncoderOptions;
    import flash.display.StageAlign;
    import flash.display.StageScaleMode;
    import flash.events.MouseEvent;
    import flash.net.FileReference;
    import flash.utils.getDefinitionByName;
    /**
     * ...
     * @author nabe
     */
    public class Main extends MovieClip
    {
        
        private var _img:Img;
        private var _b:BitmapData;
        
        public function Main() 
        {
        
            stage.align = StageAlign.TOP_LEFT;
            stage.scaleMode = StageScaleMode.NO_SCALE;
            
            var b:BitmapData = new (getDefinitionByName("mona"))();
            _img = new Img(b);
            _img.split(0, 0, b.width, b.height);
            
            addChild(new Bitmap(_img.out));
            
            stage.addEventListener(MouseEvent.CLICK, _save);
        }
        
        private function _save(e:MouseEvent):void 
        {
            var f:FileReference = new FileReference();
            f.save( _img.out.encode(_img.out.rect, new PNGEncoderOptions()), "mosaic.png");
        }
        
    }

}
```

```as3:Img.as
package 
{
    import com.greensock.TweenMax;
    import flash.display.BitmapData;
    import flash.geom.Rectangle;
    /**
     * ...
     * @author nabe
     */
    public class Img 
    {
        
        public var out:BitmapData;
        private var _src:BitmapData;
        
        public function Img(b:BitmapData) 
        {
            _src = b;
            out = b.clone();
        }
        
        /**
         * 
         * @param    x　始点x
         * @param    y　始点y
         * @param    w　幅
         * @param    h　高さ
         * @param    delay 重くならないようにdelay
         */
        public function split(
            x:int, y:int, w:int, h:int, delay:Number = 0
        ):void {
            //重くならないようにdelay
            TweenMax.delayedCall(delay, _split, [x, y, w, h]);
        }
        
        private function _split(x:int,y:int,w:int,h:int):void{
            
            //この領域の偏差の平均を計算する
            var hensa:Number = _getHensa( x, y, w, h);
            
            if (hensa < 20 ||  w * h < 2 ) {
                //hensaが小さいか、面積が小さいと色を塗って再帰的呼び出し終了
                var col:Number = _getHeikinColor(x, y, w, h);
                out.fillRect(new Rectangle(x, y, w, h), 0xff000000+col);
                return;
            }else{
                //4つに分割、再帰的な呼び出し
                var ww:Number = w / 2;
                var hh:Number = h / 2;
                split(x, y, ww, hh, Math.random());
                split(x+ww, y, ww, hh, Math.random());
                split(x, y+hh, ww, hh, Math.random());
                split(x+ww, y+hh, ww, hh, Math.random());
            }
                
        }
        
        //平均のrgb色をとる
        private function _getHeikinColor( x:int, y:int, w:int, h:int):Number {
            
            var sumR:Number = 0;
            var sumG:Number = 0;
            var sumB:Number = 0;
            for (var i:int = 0; i < w; i++) {
                for (var j:int = 0; j < h; j++) {
                    var rgb:Number = _src.getPixel(x+i, y+j);
                    var rr:Number = rgb >> 16 & 0xFF;
                    var gg:Number = rgb >> 8 & 0xFF;
                    var bb:Number = rgb & 0xFF;
                    sumR += rr/(w*h);
                    sumG += gg/(w*h);
                    sumB += bb/(w*h);
                }
            }
            
            return (sumR << 16 | sumG << 8 | sumB);
        }        
        
        //輝度の偏差の平均を取得
        private function _getHensa( x:int, y:int, w:int, h:int):Number {
            
            var heikin:Number = _getHeikin( x, y, w, h);
            var sub:Number = 0;
            for (var i:int = 0; i < w; i++) {
                for (var j:int = 0; j < h; j++) {
                    var rgb:Number = _src.getPixel(x+i, y+j);
                    var rr:Number = rgb >> 16 & 0xFF;
                    var gg:Number = rgb >> 8 & 0xFF;
                    var bb:Number = rgb & 0xFF;
                    var col:Number = (rr + bb + gg) / 3;
                    sub += Math.abs( heikin - col );
                }
            }        
            
            return sub/(w*h);
        }
        
        //平均の輝度を取得
        private function _getHeikin(x:int, y:int, w:int, h:int):Number {
            
            var sum:Number = 0;
            for (var i:int = 0; i < w; i++) {
                for (var j:int = 0; j < h; j++) {
                    var rgb:Number = _src.getPixel(x+i, y+j);
                    var rr:Number = rgb >> 16 & 0xFF;
                    var gg:Number = rgb >> 8 & 0xFF;
                    var bb:Number = rgb & 0xFF;
                    sum += (rr + gg + bb) / 3;
                }
            }
            return sum/(w*h);
        }        
    }

}
```


## おわりに
以上のように再帰的な処理を使うと（フラクタル的考え方？を使うと）割と簡単なコードでも、複雑な絵を作れる場合があります。繰り返し同じような処理をすることによって複雑な絵を作るというのはプログラミングらしい表現でしょう。
##その他の分割
* 三角形 → http://hackist.jp/?p=5191
* 文字 → http://levitated.net/daily/levEmotionFractal.html