Graphics: Marching Squares

After describing the principle of the Marching Squares algorithm in a previous post [Link], it is time to implement it...


W O R K  I N   P R O G R E S S

1- Strategy

The computation of isocontoured lines is divided in two steps:

(i) The computation of  all the line segments defined each, by two points.

(ii) The rendering with Blender software [Link].

ImageJ is powerful to deal with pixels and voxels ( images and volumes) but is definitely not a toolbox dedicated to points, lines, triangles, and all the other 2D and 3D geometric primitives. I decided to choose the Blender 3D software as a rendering engine because it is very popular and a lot of tutorials are available in the Internet. Moreover, it is easy to make small animations...
However, an extra step will be required to store all the vertices in a format suitable for Blender.

2- The core

2-1 The marching square

The marching square is defined by four vertices named v0 to v3 and four edges e0 to e3 as shown in Fig. 1.

Fig 1.: Marching square and numbering of its vertices and its edges.

The first step is to create a lookup table defining for all the 16 possible combinations, the number and location of the various lines to draw.
I chose to define each combination by a String of 4 characters corresponding to the TRUE and FALSE values of the vertices. Thus, the code is written as a 4-bit word in the order of v3|v2|v1|v0.
For example, the case in Fig. 2 corresponds to the code 1101 and the corresponding line segment connecting e0 to e1 is defined as a pair (0,1).

Fig.2: Encoding of a configuration of the marching square

Note: In a normal implementation, the 4-bit word is converted in a number (from 0 to 15), but here, I define the lookup table as a Javascript list with keys as strings and the values as arrays containing the line indexes.

+++ IJ Javascript snippet: Lookup Table +++

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]
};

+++ End of IJ Javascript snippet: Lookup Table +++

We need other features:

• The X,Y coordinates of the top left corner (aka v0) of the marching square.
• The pixel values of all the four vertices.
• The dimension in pixel unit of the square (by default 2, meaning that we skip one pixel over two).

2-2- Main loops

The marching square scans the input image with two loops. Then , for each marching square,...

1. The pixel values are extracted and thresholded  in order to calculate the code for the lookup table lines.
2. The vertices along the edges are calculated ...
3. They are finally stored in an array called vertices.

2-3- Interpolation

How can we calculate the X-,Y-coordinates of the vertices along the edges?
In the simplest method, we just compute the middle of the edge (in function interpolationNone(...) ). However, this kind of approach leads to a jagged contour lines. The best method is to apply a linear interpolation to compute the vertex. This is done in function interpolationLinear(...).

3- The Output in Wavefront - OBJ format

One of the simplest file format used in 3D software is the Wavefront - OBJ file format [Wikipedia]. This is a text file where each line starts with a single character as keyword and is followed by various parameters separated by space characters.

For example, the pyramid of Fig. 3 ...

Fig.3: Pyramid rendered in Blender from a OBJ file

... is defined in OBJ file format by the following lines of text.

# A comment
# Another comment

o pyramid

v -1.0 -1.0 0.0
v -1.0  1.0 0.0
v  1.0  1.0 0.0
v  1.0 -1.0 0.0
v  0.0  0.0 2.0

f 1 2 3 4
f 1 2 5
f 2 3 5
f 3 4 5
f 4 1 5

The output file is generated from the coordinates in the function saveAsOBJ() containing three parts:

• A header with various comments ('#') and the object name ('o').
• The list of all the vertices (v)
• The list of all the faces (f), here, defined as a pair of indexes.

<<  Previous: Principle Next: Javascript Implementation >>

4. Other crazybiocomputing posts

Further readings are available in ...

• Computer Graphics Series  [Link]
• Image Processing TOC [Link]