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


Introduction 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. 



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). 



3D 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 3D surface area as we did with perimeter in 2D, 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. 

