The Marching Squares algorithm is a computer graphics algorithm introduced in the 1980s that can be used for contouring. We can use the Marching Squares algorithm to draw the lines of constant:
- altitude on a topographical map
- temperature on a temperature heat map
- pressure on a contour map for a pressure field
In this tutorial, we’ll learn how the Marching Squares algorithm determines the contour from a grid of sample points of the image.
2. Contour Curves and Level Curves
Let’s spend a brief moment understanding the mathematically precise definition of contour lines.
2.1. Mathematical Definition
We have been drawing graphs of functions of one-variable such as or implicit functions like for so long, that we give the matter little thought. Plotting functions of two variables is a much more difficult task.
The trick to putting together a reasonable graph of a function of two or more variables is to find a way to cut down on the dimensions involved. One way to achieve this is to draw certain special curves that lie on the surface . These special curves, called contour curves, are obtained by intersecting the surface with horizontal planes for various values of the constant .
These curves in the -plane are called the level curves of the original function .
The level curve at height of any function is the curve in defined by the equation , where is a constant. In mathematical notation,
Consider the function defined as:
By definition, the level curve at height is:
Thus, we see that the level curves for are circles centered at the origin of radius . They are summarized in the table below:
The family of level curves, the “topographic map” of the surface is shown in the figure below:
If we stack all level curves together, we can get a feeling for the complete graph of . It’s a surface that looks like an inverted dish and is called a paraboloid:
For our discussion, we require the output contour to possess the following properties:
- It must separate the interior points from the exterior points.
- Thus, it must be an orientable and closed curve.
3. Essentials of the Algorithm
Consider the simplistic image of a cloud given below. We are interested to trace the contours of the cloud:
For simplicity, let’s assume that the image of a cloud is represented by a square matrix of pixels. Each pixel value represents a single sample of light, carrying brightness information. It ranges between and . Black is represented by and white by .
3.1. Sampling the Image
We divide the entire image domain into squares. Each square has dimensions by . We sample the image at each of the grid points:
Next, we iterate through the grid to determine the vertex state in comparison to an iso-value . Each grid vertex is now assigned a binary state ( or ). An iso-value serves as a threshold for determining the vertex state. Suppose we choose as the threshold. The vertex state is determined as follows:
- – Pixel value less than the iso-value
- – Pixel value greater than the iso-value
The resulting binary grid , thus obtained is:
3.2. Configuration of Each Sub-Grid
Next, a subgrid can be associated with a configuration. We iterate through . At each sub-grid, we form a binary code based on the vertex value by iterating clockwise from the top-left corner to the bottom-left corner.
For example, if a given subgrid has four corners:
its binary code is said to be . The equivalent of the binary code in the decimal number system is called the configuration of the sub-grid. In the above example, the sub-grid has the configuration Thus, we have a configuration associated with each sub-grid as follows:
3.3. Lookup Table for the Contours
Imagine a single square with the contours of an object cutting through this square. That is, the square does not lie wholly in the interior or exterior of the object. A square has edges and for each edge, we have possible choices – either the contour(boundary) intersects this edge, or it does not. This results in possible configurations.
The configuration of each sub-grid is matched with one entry in the contours lookup table below:
The contours lookup table is intuitive. As mentioned before, there are possible configurations.
Let’s consider the configuration :
We think of the purple region as the interior of an object, and the blue region as the exterior of the object. We denote the state by a black vertex and the state by a white vertex. We define a bipolar pair to be two vertices in opposite states.
Intuitively, the contour of an object must intersect the edge of a bipolar pair. Thus, the configuration must correspond to an object whose contour intersects the top and left edges of the square. In this fashion, the contours in each sub-grid are approximated, as shown in the figure below:
The Marching Squares algorithm can be divided into two steps:
- Sampling the grid points and converting them to a binary matrix .
- March the squares in and build a set of edges .
Let’s see the pseudocode:
4.1. Sampling the Grid
The input to the Marching Squares algorithm is some sample of the original matrix . The parameters and control the resolution of the sample. For example, if and , we select the sequence of pixel-values:
The result of this operation should yield a matrix of size rows and columns.
Each selected pixel value is compared with the iso-value and converted to a bit-value or . is used to hold the bit matrix. The actual -coordinates of each pixel in the sample , concerning the original matrix is stored as a named tuple in a matrix .
For example, if , , we would find , .
Let’s see the pseudocode now:
4.2. Marching the Squares In
Next, we march the squares in the binary grid . Each square in , beginning with its top-left corner, has vertices, in clockwise order : , , and . We compute the reference value of each square. We also compute the mid-points of each square edge: north, east, south, and west. Finally, we determine the contour by searching the reference value in the contours lookup table:
Here’s a topographical map of the Mont Blanc region in the Swiss Alps. The Marching Squares algorithm when executed on this image produces nice contours around the mountain peaks:
In this article, we learned about an interesting Computer Graphics algorithm called the Marching Squares. To summarize, it is based on two core ideas. First, the contours can be constructed piecewise within each grid square, without reference to other squares. Second, each isocontour segment in a grid square can be retrieved from a lookup table.