任意画像の高速な輪郭追跡 for Run-Type Direction Code
click to change image
/**
* Copyright heriet ( http://wonderfl.net/user/heriet )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/16Oc
*/
// 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;
}
}
}