Tuesday, November 25, 2014

Graphics: Marching Squares - OOP Script



In this improved version of the Marching Squares algorithm - see description [Link] - I use an Object-Oriented Programming (OOP) approach...


For sake of convenience, this script uses OOP paradigm and I defined two classes named Square and Row to simplify the code of the main script.
These two classes are written in separate files and are included in the main script during the execution. A specific ImageJ Javascript function called load(<name-of-the-file.js>) is used.

Note: In ImageJ, it is possible to load external files in a JavaScript script since version 1.49k and only if you use the Sun/Oracle Java Virtual Machine ("HotSpot"). The other java implementations like OpenJDK don't use the Mozilla Rhino engine and can't load external files...
...

 1. Class Square

The class Square contains all we need to define a marching square.
  • Top left (X,Y) coordinates
  • Pixel values of the four vertices
  • Key defining the configuration and the lines to be drawn
  • Indexes of the vertices of the isocontoured lines


+++ Javascript:marchingSquare_Square.js +++
// class Square for marchingSquareNoDoubles.js
// Jean-Christophe Taveau
// http://crazybiocomputing.blogspot.com
// Nov. 2014
// Constructor
function Square(x,y,size) {
this.x=x;
this.y=y;
this.size=size;
this.edges=[-1,-1,-1,-1];
this.pixels=[0,0,0,0];
this.code="";
}
Square.prototype.getVertex = function (index) {
switch (index) {
case 0:
return {'x':this.x,'y':this.y,'pixel':this.pixels[0]};
case 1:
return {'x':this.x+this.size,'y':this.y,'pixel':this.pixels[1]};
case 2:
return {'x':this.x+this.size,'y':this.y+this.size,'pixel':this.pixels[2]};
case 3:
return {'x':this.x,'y':this.y+this.size,'pixel':this.pixels[3]};
default:
throw("ERROR: Wrong index");
break;
}
}
Square.prototype.setPixels = function (i) {
this.pixels[0]=ip.get(x,y);
this.pixels[1]=ip.get(x+this.size,y);
this.pixels[2]=ip.get(x+this.size,y+this.size);
this.pixels[3]=ip.get(x,y+this.size);
}
Square.prototype.calcKey = function (threshold) {
this.code = (this.pixels[3] > threshold) ? "1" : "0";
this.code += (this.pixels[2] > threshold) ? "1" : "0";
this.code += (this.pixels[1] > threshold) ? "1" : "0";
this.code += (this.pixels[0] > threshold) ? "1" : "0";
}
Square.prototype.toString = function () {
return square.x+ " "+square.y+" ("+square.edges[0]+"; "+square.edges[1]+"; "+square.edges[2]+"; "+square.edges[3]+")";
}
+++ End of Script: marchingSquare_Square.js +++

2. Class Row

The class row corresponds to a temporary array of marching squares (instances of the class Square) to keep track of the previously calculated squares. Two methods (or functions) previous() and above() allow to retrieve the squares of coordinates (X-1,Y) and (X,Y-1), respectively.

+++ Javascript:marchingSquareNoDoubles_Row.js +++
// class Row for marchingSquareNoDoubles.js
// Jean-Christophe Taveau
// http://crazybiocomputing.blogspot.com
// Nov. 2014
function Row() {
this.squares = [];
this.count = 0;
}
Row.prototype.reset_count = function () {
this.count=0;
}
Row.prototype.push = function (a_square) {
row[this.count++] = a_square;
}
Row.prototype.previous = function () {
return row[this.count - 1];
}
Row.prototype.above = function () {
return row[this.count];
}
+++ End of Script: marchingSquareNoDoubles_Row.js +++

3. Core

The skeleton of this script is the same as previously [Link].
  • First, the function dialog() is called to set the various parameters.
  • Second, the whole image (or slice) is scanned by two loops along the Y- and X-axes. For each iteration, ...
    1.  A new marching square is created
    2. Its code is generated
    3. The function createVertices() is called to compute the segment line(s) and its start and end points.
    4. The marching square is stored in an array.
  • Third, all the vertices and segment lines are saved in a file thanks to the function saveAsOBJ().
The code was modified in the function createVertices(). In this modified function, we test two cases:
  1. If the point of the line segment is located in edges e1 or e2, segment line(s) is(are) created and and the corresponding coordinates of the vertices are computed using the function interpolate(...).
  2. If the point is located in edges e0 or e3, it is already calculated in a previous marching square. The methods previous() or above() of the row object are used to get the index of the corresponding vertex.


To run this script, first download the three files in the same directory and in ImageJ, go to File > Open... and choose the file marchingSquareNoDoubles.js. Then, run this script with Ctrl+R.
If this error message appears in the Log window, ...

ERROR: Too old version. Please, update your ImageJ version
-- End of the script --

... update your ImageJ version by going to Help > Update ImageJ


+++ Javascript:marchingSquareNoDoubles.js +++
// Marching squares No Doubles
// Improved version to remove doubles
// Jean-Christophe Taveau
// http://crazybiocomputing.blogspot.com
// Nov 2014
// v0----e0----v1
// | |
// | |
// e3 e1
// | |
// | |
// v3----e2----v2
//
// key = v3|v2|v1|v0
//
// I N C L U D E C L A S S
var LOAD_AVAILABLE = true;
// Check availability of the load(...) function
if (IJ.versionLessThan("1.49k") ) {
IJ.log("Please, update your ImageJ version");
throw("-- End of the script --");
}
else if (LOAD_AVAILABLE && System.getProperty("java.vm.name").indexOf("HotSpot") != -1) {
load('marchingSquareNoDoubles_Square.js');
load('marchingSquareNoDoubles_Row.js');
}
else if (LOAD_AVAILABLE) {
IJ.log("This JVM doesn't support the IJ/Javascript load(...) function.");
IJ.log("Please, install the Sun/Oracle JVM or...");
IJ.log("(i ) Set the variable LOAD_AVAILABLE to 'false'");
IJ.log("(ii) Copy and paste in the 'I N C L U D E C L A S S' section above the contents of the two files:");
IJ.log("- marchingSquareNoDoubles_Square.js");
IJ.log("- marchingSquareNoDoubles_Row.js");
throw("-- End of the script --");
}
// M A R C H I N G S Q U A R E S
var lines={
"0000":[],
"1111":[],
"0001":[0,3],
"0010":[0,1],
"0100":[1,2],
"1000":[2,3],
"1110":[0,3],
"1101":[0,1],
"1011":[1,2],
"0111":[2,3],
"0011":[1,3],
"0110":[0,2],
"1100":[1,3],
"1001":[0,2],
"0101":[0,1,2,3],
"1010":[0,3,1,2]
};
// Marching Squares Parameters
var threshold=128;
var SIZE=2;
var filename='';
var interpolate = null;
var row= new Row();
// Output vertices
var mesh = {};
mesh.vertices=[];
mesh.squares={};
mesh.faces=[];
// Get information about the active image
var imp=IJ.getImage();
var ip=imp.getProcessor();
var w=imp.getWidth();
var h=imp.getHeight();
var nz=imp.getStackSize();
var center = {'x':w/2.0,'y':h/2.0,'z':nz/2.0};
// M A I N
// Small GUI to set parameters
dialog();
// Main loop(s)
for (var y=0;y<h-SIZE;y+=SIZE) {
row.reset_count();
for (var x=0;x<w-SIZE;x+=SIZE) {
// 1- Create a new marching square
var square = new Square(x,y,SIZE);
// 2- Set pixel values to vertices of this square
square.setPixels(ip);
// 3- Compute key
square.calcKey(threshold);
// 4- Create vertices
if (square.code !="0000" && square.code !="1111") {
createVertices(square);
}
// 5- Store this square in row.
row.push(square);
}
}
// Save contour lines as OBJ file
saveAsOBJ();
throw("-- End of Script -- ");
// F U N C T I O N S
function dialog() {
var gd = new GenericDialog("Marching Squares");
gd.addNumericField("Threshold: ", threshold, 0);
gd.addNumericField("Square Size: ", SIZE, 0);
gd.addChoice("Interpolation: ", ["None","Bilinear"], 0);
gd.showDialog();
if (gd.wasCanceled()) {
throw("-- End of Script --");
return;
}
threshold = gd.getNextNumber();
SIZE = gd.getNextNumber();
var mode = gd.getNextChoiceIndex();
if (mode == 0) {
interpolate = function (v0,v1) {
return interpolateNone(v0,v1);
}
}
else {
interpolate = function (v0,v1) {
return interpolateBilinear(v0,v1);
}
}
var saveDialog = new SaveDialog("Save OBJ File As ...","Untitled",".obj");
filename=saveDialog.getDirectory()+saveDialog.getFileName();
}
function createVertices(squ) {
var edges = lines[squ.code];
for (var i=0;i<edges.length;i++) {
var index=-1;
var edge = edges[i];
switch (edge) {
case 0:
if (squ.y != 0) {
squ.edges[0] = row.above().edges[2];
index = squ.edges[0];
}
else {
vertex = interpolate(squ.getVertex(0),squ.getVertex(1) );
mesh.vertices.push(vertex);
index = mesh.vertices.length-1;
squ.edges[edge]= index;
}
break;
case 1:
vertex = interpolate(squ.getVertex(1),squ.getVertex(2) );
mesh.vertices.push(vertex);
index = mesh.vertices.length-1;
squ.edges[edge]= index;
break;
case 2:
vertex = interpolate(squ.getVertex(2),squ.getVertex(3) );
mesh.vertices.push(vertex);
index = mesh.vertices.length-1;
squ.edges[edge]= index;
break;
case 3:
if (squ.x != 0) {
squ.edges[3] = row.previous().edges[1];
index = squ.edges[3];
}
else {
vertex = interpolate(squ.getVertex(0),squ.getVertex(3) );
mesh.vertices.push(vertex); // Add vertex
index = mesh.vertices.length-1; // Update square
squ.edges[edge]= index;
}
break;
}
mesh.faces.push(index);
}
}
function interpolateNone(v0,v1) {
var x = (v0.x + v1.x)/2.0;
var y = (v0.y + v1.y)/2.0;
var z = 0.0;
return {"x":x,"y":y,"z":z};
}
function interpolateBilinear(v0,v1) {
var k = (threshold - v0.pixel)/(v1.pixel - v0.pixel)
var x = v0.x + (v1.x - v0.x) * k;
var y = v0.y + (v1.y - v0.y) * k;
var z = 0.0;
return {"x":x,"y":y,"z":z};
}
function saveAsOBJ() {
// Create/Open output text in file
var file = new java.io.File(filename);
var printWriter = new java.io.PrintWriter(filename);
// Header
var text='';
text+="# Marching Squares\n";
text+="# Jean-Christophe Taveau\n";
text+="# CrazyBioComputing\n";
text+="# WaveFront OBJ\n";
text+="# Vertices: "+mesh.vertices.length+"\n";
text+="\n";
text+="o "+imp.getTitle()+"\n";
text+="\n";
printWriter.println(text);
// Vertices
for (var i=0;i<mesh.vertices.length;i++) {
printWriter.println("v "+(mesh.vertices[i].x - center.x) + " " + (mesh.vertices[i].y - center.y) + " " + mesh.vertices[i].z );
}
printWriter.println(" ");
// Faces (aka lines)
// *Note*: The first vertex in OBJ format has the index 1 (and not 0).
for (var i=0; i<mesh.faces.length;i+=2) {
printWriter.println("f "+ (mesh.faces[i]+1) +" "+ (mesh.faces[i+1]+1) );
}
// Close file
printWriter.close ();
}
+++ End of Script: marchingSquareNoDoubles.js +++


Hope that helps.


4. Other crazybiocomputing posts

Further readings are available in ...
  • Computer Graphics Series  [Link]
  • Image Processing TOC [Link]





No comments:

Post a Comment