Marching squares

Marching squares is a computer graphics algorithm that generates contour lines for a two-dimensional scalar field. It is similar to the three-dimensional marching cubes algorithm.

How it works

The Marching Squares algorithm consist of the same step as marching cubes in 3D . A basic description of the steps:

1. First step is to apply a threshold the 2D matrix (image) to make a binary image with all pixels above the iso-treshold set to true (1) and the other pixels to false (0)
2. Now every 2x2 pixels values in the binary image form a cell, thus the image is represented by a grid of cells
3. Every cell has 4 binary-pixel-values [b1,b2,b3,b4], these are used to calculate a number from 0 to 15 which describes these values. The following equation is used N = b1 + b2*2+b3*4+b4*8
4. Then the cell-number is used to look up which lines are needed to represent the cell, using an lines-database with all the 16 cases.
5. After placing the lines from the database into the cells, you have found the contour geometry.
6. Now linear-interpolation between the original pixel values is used to move the end-points of every line from the center of a cell-edge to the exact iso-treshold on the cell-edge.

Links

• Marching Square Matlab algorithm - An easy to understand open-source marching square algorithm.