// 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; } } } 任意画像の高速な輪郭追跡 for Run-Type Direction Code