Graphics: Isocontoured Lines

In this series dedicated to 3D rendering, this is a preliminary post describing how to extract vectorial isocontoured lines from an image. One of the most popular algorithm is the Marching Squares algorithm.
The next step will be the computation of isosurfaces...

An image is composed of pixels and there are various techniques to extract edges like filters based on gradients (Process > Find Edges), mathematical morphology operators or the Analyze > Analyze Particles... (option 'Show Outlines'). But, the result is still an image composed of pixels and when you zoom in, jagged pixels appear (Fig.1).

Fig.1: Extraction of edges with the Analyze > Analyze Particles...

Another approach consists of converting the edges into a set of lines defined by their X,Y-coordinates and then to send this array of coordinates to a 2D/3D rendering software.
Even though there is no direct advantage in 2D, this vectorial approach is very powerful in 3D because most of the 3D rendering softwares are hardware-accelerated and can render thousands of vertices interactively.

1- We need vertices...

Here is a 5x5 test image...

Fig.2: 5x5 test image. For sake of clarity, the image was scaled to see the pixels.

 1-1 Grid conversion

Let us imagine that the pixel values are only centered in the middle of the pixels (Fig. 3B), the image may be described as a grid where each node contains the pixel value (Fig. 3C).

Fig. 3: 5x5 Test image and corresponding grid.

1-2- Thresholding

Then, we need to threshold the gray-level grid to get the binary of Fig. 4. The threshold value was chosen in such a way that the white pixels are TRUE and the others FALSE.

Fig.4: Thresholded image

2- The Marching Squares

This algorithm uses a square probe - the marching square - (Fig. 5) scanning the whole grid, then, locally creates zero, one or two lines depending of the pixel values located under the four vertices of the probe.

Fig. 5: The marching square

As a square contains 4 vertices and each vertex can be FALSE or TRUE, 16 different conformations are possible. But, due to symmetries, rotations and TRUE/FALSE complementarity, this number can be reduced to four patterns as shown in Fig. 6.

Fig. 6: Various patterns of the square probe. Top row: The four patterns and the lines generated in red. Bottom row: Equivalent patterns due to symmetries, rotations and TRUE/FALSE complementarity.

If all (or none of ) the vertices are TRUE (case #1), then no line is generated. If one or two adjacent vertices are TRUE (cases #2 and 3), one line is generated and in the case of two diagonal vertices  (case #4), two lines are drawn.

From the thresholded grid (Fig.4), the following configurations were found  :

Row#1: 1 2 2 1
Row#2: 2 2 3 1
Row#3: 2 2 3 1
Row#4: 1 2 2 1

and the result is ...

Fig. 7: Isocontoured line generated by the Marching Squares algorithm.

Now, we have seen the principle, it is time to implement the Marching Squares algorithm in ImageJ and this is the subject of the next post...

Next: JavaScript implementation >>

3- Links

Computer Graphics: TOC [Link]