任意画像の高速な輪郭追跡 for Run-Type Direction Code

click to change image

forked:0
favorite:39
lines:414
license : MIT License
modified : 2009-06-30 03:42:14

Embed: Tweet

// click to change image

package
{
  /*
   * ContourTracingTest is generate random image and contour tracing for image.
   * @auther heriet
   */
  
  import flash.display.Bitmap;
  import flash.display.BitmapData;
  import flash.display.Graphics;
  import flash.display.MovieClip;
  import flash.display.Sprite;
  import flash.events.Event;
  import flash.events.MouseEvent;
  import flash.geom.Point;
  
  public class ContourTracingTest extends MovieClip
  {
    
    private static const POINT_ZERO:Point = new Point();
    
    private var sourceImage:BitmapData;
    private var tracingImage:BitmapData;
    private var imageGenerator:Sprite;
    
    private var contourList:Vector.<Vector.<Point>>;
    private var isDrawing:Boolean;
    private var frame:int;
    private var contourIndex:int;
    private var pointIndex:int;
    private var isRunning:Boolean;
    
    [SWF(width="465", height="465", backgroundColor="0xFFFFFF")]
    public function ContourTracingTest() 
    {
      initialize();
      stage.addEventListener(MouseEvent.CLICK, onMouseClick);
    }
    private function onMouseClick(e:MouseEvent):void
    {
      if (isRunning) {
        removeEventListener(Event.ENTER_FRAME, onEnterFrame);
        initialize();
      }
    }
    private function initialize():void
    {
      imageGenerator = new Sprite();
      
      if (sourceImage != null)
        sourceImage.dispose();
      if (tracingImage != null){
        tracingImage.dispose();
      }
      while (numChildren > 0)
        removeChildAt(0);
      
      sourceImage = new BitmapData(116, 116, true, 0);
      tracingImage = new BitmapData(116, 116, true, 0);
      
      generateRandomGraphics(imageGenerator.graphics);
      tracingImage.copyPixels(sourceImage, sourceImage.rect, POINT_ZERO);
      var myBitmap:Bitmap = new Bitmap(tracingImage);
      isDrawing = true;
      frame = 0;
      contourIndex = 0;
      pointIndex = 0;
      isRunning = false;
      
      addEventListener(Event.ENTER_FRAME, waitFrame);
    }
    // tekito-
    private function generateRandomGraphics(g:Graphics):void
    {
      var i:int;
      var n:int;
      
      n = (int) (Math.random() * 8) + 1;
      
      for (i = 0; i < n; i++ ){
        g.beginFill(0x00FF00);
        g.drawEllipse((int) (Math.random() * 125 - 25), (int) (Math.random() * 125 - 25), (int) (Math.random() * 50 + 5), (int) (Math.random() * 75 + 5));
        g.endFill();
      }
      
      n = (int) (Math.random() * 8) + 1;
      for (i = 0; i < n; i++ ){
        g.beginFill(0x00FF00);
        g.drawRect((int) (Math.random() * 125 - 25), (int) (Math.random() * 125 - 25), (int) (Math.random() * 50 + 5), (int) (Math.random() * 75 + 5));
        g.endFill();
      }
      
      n = (int) (Math.random() * 8) + 1;
      for (i = 0; i < n; i++ ){
        g.beginFill(0x00FF00);
        var cx:int = (int) (Math.random() * 125 - 25);
        var cy:int = (int) (Math.random() * 125 - 25);
        var sx:int = (int) (Math.random() * 75);
        var sy:int = (int) (Math.random() * 75);
        g.moveTo(sx + cx, sy + cy);
        
        var m:int = (int) (Math.random() * 3) + 2;
        for (var j:int = 0; j < m;  j++){
          var dx:int = (int) (Math.random() * 75);
          var dy:int = (int) (Math.random() * 75);
          g.lineTo(dx + cx, dy + cy);
        }
        g.lineTo(sx + cx, sy + cy);
        g.endFill();
      }
    }
    // wait 2 frames for imageGenerator
    private function waitFrame(e:Event):void
    {
      removeEventListener(Event.ENTER_FRAME, waitFrame);
      addEventListener(Event.ENTER_FRAME, generateImage);
    }
    private function generateImage(e:Event):void
    {
      removeEventListener(Event.ENTER_FRAME, generateImage);
      
      sourceImage.draw(imageGenerator);
      sourceImage.threshold(sourceImage, sourceImage.rect, POINT_ZERO, '!=', 0, 0xFF00FF00);
      tracingImage.copyPixels(sourceImage, sourceImage.rect, POINT_ZERO);
      var myBitmap:Bitmap = new Bitmap(tracingImage);
      addChild(myBitmap);
      myBitmap.scaleX = 4;
      myBitmap.scaleY = 4;
      
      /* Main routine */
      var myContourTracer:ContourTracer = new ContourTracer();
      contourList = myContourTracer.findContourListForRun(sourceImage, 0x00000000, 0xFF000000, ContourTracer.TRACE_ALL);
      isRunning = true;
      
      addEventListener(Event.ENTER_FRAME, onEnterFrame);
    }
    private function onEnterFrame(e:Event):void
    {
      var contourPoint:Point = contourList[contourIndex][pointIndex];
      drawContourPoint(contourPoint);
      pointIndex++;
      
      if (pointIndex >= contourList[contourIndex].length) {
        pointIndex = 0;
        contourIndex++;
        
        if (contourIndex >= contourList.length) {
          contourIndex = 0;
          isDrawing = !isDrawing;
        }
      }
      
      frame++;
    }
    private function drawContourPoint(p:Point):void
    {
      var color:uint = tracingImage.getPixel(p.x, p.y);
      var sColor:uint = sourceImage.getPixel(p.x, p.y);
      if (isDrawing) {
        tracingImage.setPixel(p.x, p.y, 0xFF0000);
      }
      else {
        tracingImage.setPixel(p.x, p.y, sColor);
      }
    }
  }
}

/*
 * Contour tracer is find contour of image.
 * @author heriet
 */

import flash.display.BitmapData;
import flash.geom.Point;
  
class ContourTracer
{
  public static const TRACE_ALL:int = 0;
  public static const TRACE_OUTSIDE:int = 1;
  public static const TRACE_INSIDE:int = 2;
  
  private static const AUTOMATON_STATE_TABLE:Array = [
    [2, 4, 3],
    [1, 5, 4],
    [4, 6, 1],
    [5, 1, 6],
    [4, 6, 1],
    [1, 5, 4],
  ];
  
  private static const AUTOMATON_CODE_SET_TABLE:Array = [
    [0, 2, 0],
    [5, 4, 4],
    [3, 3, 1],
    [0, 6, 0],
    [10, 10, 8],
    [7, 9, 9],
  ];
  
  /*
   * Find contour points for Run-type Direction Coding algorithm.
   * 
   * Bibliography:
   *   T. Miyatake, H. Matsushima, M. Ejiri, "A Fast Algorithm for Contour Tracing of Binary Images Based on Run-Type Direction Coding Technique",
   *   The transactions of the Institute of Electronics, Information and Communication Engineers, J79-D-2(3), pp.341-350, 1996.
   * 
   * @param source Source image
   * @param backgroundColor Background color of source image. This function processes binary color of source image as a background color and other colors.
   * @param maskColor Mask of background color. (e.g. Alpha mask is maskColor = 0xFF000000. Red mask is maskColor = 0xFF0000)
   * @param mode Mode of Tracer. ContourTracer.TRACE_ALL or ContourTracer.TRACE_OUTSIDE or ContourTracer.TRACE_INSIDE.
   * 
   * @return Vector of contour. One contour is composed one object's edge points.
   */
  public function findContourListForRun(source:BitmapData, backgroundColor:uint = 0x00000000, maskColor:uint = 0xFFFFFFFF, mode:int = TRACE_ALL):Vector.<Vector.<Point>>
  {
    var rdDataList:Vector.<RunTypeDirectionData> = new Vector.<RunTypeDirectionData>();
    
    var prevLineBuffer:Vector.<int>;
    var currentLineBuffer:Vector.<int> = new Vector.<int>();
    
    var width:int = source.width;
    var height:int = source.height;
    var endOfLine:int = width + 1;
    
    currentLineBuffer.push(endOfLine);
    
    var entryIndex:int = 0;
    var topWaitIndex:int = 0;
    var lastWaitIndex:int = 0;
    
    var automatonState:int = 1; // Automaton state for RD code extraction
    
    var x:int, y:int;
    
    for (y = 0; y <= height; y++) {
      prevLineBuffer = currentLineBuffer;
      currentLineBuffer = new Vector.<int>();
      
      if(y < height){
        // read run(left and right edge) of image line
        // if x = -1 or x = width, set source.getPixel32(x, y) = backgroundColor
        var isBackgroundRun:Boolean = true;
        for (x = 0; x <= width; x++ ) {
          var color:uint = x < width ? source.getPixel32(x, y) : backgroundColor;
          var binaryColor:Boolean = (color & maskColor) == (backgroundColor & maskColor);
          if (isBackgroundRun != binaryColor) {
            currentLineBuffer.push(x);
            isBackgroundRun = binaryColor;
          }
        }
      }
      currentLineBuffer.push(endOfLine);
      
      var prevIndex:int = 0;
      var currentIndex:int = 0;
      var prevPrevRun:int = 0;
      var prevRun:int = prevLineBuffer[prevIndex];
      var prevCurrentRun:int = 0;
      var currentRun:int = currentLineBuffer[currentIndex];
      
      while (prevRun != endOfLine || currentRun != endOfLine) {
        
        // extract RD code
        var cmpState:int = cmpInt(prevRun, currentRun) + 1; // (prev <=> current) + 1
        var rdCode:int = AUTOMATON_CODE_SET_TABLE[automatonState-1][cmpState];
        automatonState = AUTOMATON_STATE_TABLE[automatonState-1][cmpState];
        
        // link RD data
        // this routine may be more smart
        if (rdCode != 0) {
          var rdData:RunTypeDirectionData = new RunTypeDirectionData(rdCode, prevPrevRun, prevRun, prevCurrentRun, currentRun, y);
          rdDataList.push(rdData);
          
          var myRDData:RunTypeDirectionData;
          if (rdCode == 1 || rdCode == 9) {
            myRDData = rdDataList[lastWaitIndex];
            myRDData.wLink = entryIndex;
            lastWaitIndex = entryIndex;
            
            var k:int;
            k = topWaitIndex;
            myRDData = rdDataList[k];
            var isLoop:Boolean = false;
            while (myRDData.link != -1) {
              k = myRDData.link;
              myRDData = rdDataList[k];
              if (k == topWaitIndex) {
                isLoop = true;
                break;
              }
            }
            if (isLoop)
              topWaitIndex = entryIndex;
          }
          else if (rdCode == 2 || rdCode == 3 || rdCode == 4) {
            // wait head
            myRDData = rdDataList[lastWaitIndex];
            myRDData.wLink = entryIndex;
            lastWaitIndex = entryIndex;
            // link tail
            myRDData = rdDataList[topWaitIndex];
            myRDData.link = entryIndex;
            rdData.isLinked = true;
            if(myRDData.isLinked && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
          }
          else if (rdCode == 5) {
            // link tail
            myRDData = rdDataList[topWaitIndex];
            myRDData.link = entryIndex;
            rdData.isLinked = true;
            if (myRDData.isLinked && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
            //　link head
            myRDData = rdDataList[topWaitIndex];
            rdData.link = topWaitIndex;
            myRDData.isLinked = true;
            if (myRDData.link != -1 && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
          }
          else if (rdCode == 6 || rdCode == 7 || rdCode == 8) {
            // link head
            myRDData = rdDataList[topWaitIndex];
            rdData.link = topWaitIndex;
            myRDData.isLinked = true;
            if(myRDData.link != -1 && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
            // wait tail
            myRDData = rdDataList[lastWaitIndex];
            myRDData.wLink = entryIndex;
            lastWaitIndex = entryIndex;
          }
          else { // rdCode == 10
            // link head
            myRDData = rdDataList[topWaitIndex];
            rdData.link = topWaitIndex;
            myRDData.isLinked = true;
            if(myRDData.link != -1 && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
            // link tail
            myRDData = rdDataList[topWaitIndex];
            myRDData.link = entryIndex;
            rdData.isLinked = true;
            if (myRDData.isLinked && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
          }
          
          entryIndex++;
        }
        
        // update next run data
        prevPrevRun = prevRun;
        prevCurrentRun = currentRun;
        
        if (cmpState == 0) {
          prevIndex++;
          prevRun = prevLineBuffer[prevIndex];
        }
        else if (cmpState == 1) {
          prevIndex++;
          prevRun = prevLineBuffer[prevIndex];
          currentIndex++;
          currentRun = currentLineBuffer[currentIndex];
        }
        else {
          currentIndex++;
          currentRun = currentLineBuffer[currentIndex];
        }
      }
    }
    
    // RD Data List to Coutour Points
    var contourList:Vector.<Vector.<Point>> = new Vector.<Vector.<Point>>();
    var searchedNum:int = 0;
    var nextFirstIndex:int = 0;
    var n:int = rdDataList.length;
    
    while (searchedNum < n) {
      var contour:Vector.<Point> = new Vector.<Point>();
      
      entryIndex = -1;
      for (var i:int = nextFirstIndex; i < n; i++ ) {
        myRDData = rdDataList[i];
        if (!myRDData.isChecked) {
          if ((mode == TRACE_ALL)
          || (mode == TRACE_OUTSIDE && myRDData.code == 1)
          || (mode == TRACE_INSIDE && myRDData.code == 9)) {
            entryIndex = i;
            nextFirstIndex = i + 1;
            break;
          }
          else {
            // ignore contour
            while (!myRDData.isChecked) {
              myRDData.isChecked = true;
              searchedNum++;
              if (myRDData.link < 0)
                break;
              myRDData = rdDataList[myRDData.link];
            }
          }
        }
      }
      if (entryIndex == -1)
        break;
      
      myRDData = rdDataList[entryIndex];
      
      /* 
       no use flag. First RD code is 1 or 9. 
       var isOutside:Boolean = myRDData.code == 1;
       var isInside:Boolean = myRDData.code == 9;
       */
       
      var myPoint:Point = new Point(myRDData.x, myRDData.y);
      var prevX:int = myPoint.x;
      var prevY:int = myPoint.y;
      var posX:int, posY:int, sucY:int;
      
      // First contour point pushed last of contour list. RD link is ring.
      if (!(myRDData.link == entryIndex || myRDData.link < 0)) {
        entryIndex = myRDData.link;
        myRDData = rdDataList[myRDData.link];
      }
      
      do {
        myRDData.isChecked = true;
        searchedNum++;
        
        if (myRDData.code == 2) {
          myPoint = new Point(prevX, prevY + 1);
          contour.push(myPoint);
        }
        else if (myRDData.code == 6) {
          myPoint = new Point(prevX, prevY - 1);
          contour.push(myPoint);
        }
        else {
          if (myRDData.code == 4 || myRDData.code == 9) {
            posX = 0; posY = -1; sucY = 1;
          }
          else if (myRDData.code == 5 || myRDData.code == 7) {
            posX = 0; posY = -1; sucY = 0;
          }
          else if (myRDData.code == 8 || myRDData.code == 10) {
            posX = -1; posY = 0; sucY = -1;
          }
          else { // myRDData.code == 1 or 3
            posX = 0; posY = 0; sucY = 0;
          }
          
          while (prevX != myRDData.x + posX) {
            prevX = prevX < myRDData.x + posX ? prevX + 1 : prevX - 1;
            myPoint = new Point(prevX, myRDData.y + posY);
            contour.push(myPoint);
          }
          myPoint.y += sucY;
        }
          
        prevX = myPoint.x;
        prevY = myPoint.y;
        
        if (myRDData.link == entryIndex || myRDData.link < 0)
          break;
        
        entryIndex = myRDData.link;
        
        myRDData = rdDataList[entryIndex];
      } while (!myRDData.isChecked)
      
      // Replace first Point
      contour.reverse();
      
      if(contour.length != 0)
        contourList.push(contour);
    }
    
    return contourList;
    
    // val1 <=> val2 
    function cmpInt(val1:int, val2:int):int {
      if (val1 < val2) {
        return -1;
      }
      else if (val1 == val2) {
        return 0;
      }
      else {
        return 1;
      }
    }
  }
}

/*
 * Run-type Direction data
 * @author heriet
 */

class RunTypeDirectionData 
{
  public var x:int = 0;
  public var y:int = 0;
  public var code:int = 0;
  public var link:int = -1;
  public var wLink:int = -1;
  public var isLinked:Boolean = false;
  public var isChecked:Boolean = false;
  
  public function RunTypeDirectionData(code:int, prevPrev:int, prev:int, prevCurrent:int, current:int, y:int) 
  {
    this.code = code;
    this.y = y;
    
    if (code == 1 || code == 3) {
      this.x = prevCurrent;
    }
    else if (code == 4 || code == 9) {
      this.x = current;
    }
    else if (code == 5 || code == 7) {
      this.x = prev - 1;
    }
    else if (code == 8 || code == 10) {
      this.x = prevPrev;
    }
    else { // code == 2, or 6
      this.x = -1;
      this.y = -1;
    }
  }
}

Code Fullscreen

Preview Fullscreen