Erik Miller's Masters Thesis Page

An Analysis of Surface Area Estimates of Binary Volumes Under Three Tilings


To represent images or volumes in a digital computer, they must be discretized. This discretization leads to errors in the computation of such fundamental properties of objects as perimeter, area, volume, and surface area. Not surprisingly, the magnitudes of these errors depend upon the particular discretization used. There are an infinite variety of discrete approximations for any figure, from the spatial frequency decompositions used in signal processing to parameterized NURB surfaces used in the CAD/CAM world. In my thesis, I focussed on a particular class of discretizations: the tessellation of planar figures and solid volumes. Tessellations are approximate representations particularly convenient in computer vision and graphics.

At right are three different ways of "tessellating" or "voxelizing" a sphere. Image A uses rhombic dodecahedra. Image B uses truncated octahedra. Image C uses regular rectangular prisms, also known as cubes. :)

I show in my thesis that for computing surface areas using local counting algorithms, estimates are more accurate and have less variance using the rhombic dodecahedron representations.

Counter-Intuitive Fact

Suppose we want to estimate the area of a smoothly bounded plane figure such as the circle shown at left. One way would be to scan it into a computer, count the number of pixels in the figure, and then multiply by the area of each pixel. The error in our area estimate would be related to how small the pixels are. That is, if we use large pixels, we will incur error on the boundary of our figure because the boundary is not well represented by the large pixels. It seems obvious that if we reduce the pixel size enough that this process, in the limit, will give us the true area of our plane figure.

However, suppose we want to compute the perimeter of a region by adding the length of the boundaries of all of the border pixels. While our perimeter estimate will improve to a certain extent as we make the pixels smaller, the surprising fact is that we cannot eliminate all of the error by making the pixels arbitrarily small. This is easily seen for the straight line example in the next image.

The "Manhattan Length" of a Line

At right we illustrate the local counting method for estimating the length of a 45 degree diagonal line. We merely add the length of the stairstep representations of the line. This clearly gives and overestimate of the true line length. Oddly enough, the estimate for the line length does not change (except for at the endpoints) as the pixel size is decreased. That is, the total length of the stairsteps remains constant with changes in pixel size.

This implies that using a local counting algorithm, we cannot obtain a more and more accurate perimeter estimate merely by increasing our resolution (at least in this case).

Hexagonal Grids

It turns out that by using hexagonal pixels, we can achieve a mean error in perimeter estimates that is the same as for a square grid, but with a much lower variance. Hence, local counting perimeter estimates of smooth figures on an hexagonal grid are more reliable if the pixels are "small."

3-D Tilings

In three dimensions, we have a situation very similar to that in two dimensions. We find that we can accurately estimate the volume of a smooth binary volume by merely making the voxels smaller and smaller. However, we run into the same problem with 3-D surface area as we did with perimeter in 2-D, i.e. we cannot accurately estimate surface area using local counting methods merely by making our voxels smaller.

Hence, I explored the benefits of using different voxel shapes. On the right are some examples of some planar patches represented with truncated octahedra.


On the left are six plots. The three on the far left show the error in surface area estimates of a plane as a function of the azimuth and declination of the plane.

A.The topmost of the far left plots is for cubic voxels. Notice the large errors (in red) for planes which are not near the principal cartesian planes (x-z, y-z, x-y).

C. The middle far left plot is for the truncated octahedron voxel. Notice that the maximum error is much smaller and that the variance in error is also smaller.

E. The lower left plot is for the rhombic dodecahedron voxel. This had the smallest errors of all three voxel shapes, and hence, is presumably better for computing surface areas using local counting algorithms.

B,D,F. The plots on the right show errors for the same three voxel shapes after using a "correction factor". The rhombic dodecahedron shows lower errors after the correction is made as well.