CMPT-767 Project Proposal

Comparison of sampling over BCC and CC latices and reconstruction of normal data along with noise.

Group Member:

Zahid Hossain (zha13@sfu.ca)


This falls under the type “Technique Project.” In this project I plan to study the quality and also efficiency (space and time) of the BCC latices over the more widely used CC latices for sampling and reconstruction. CC latices are more popular because of their simple construct and 1-D separability of operations. However, reconstruction techniques for BCC uses quasi-interpolations which are intrinsically higher in dimension. Recently, research on BCC latices have shown that it is not only the best sampling method but also reconstructs data faster and with lower number of samples. The fast aspect of BCC reconstruction may not be too intuitive but its property of being “best sampling method” comes as no big surprise because of the fact that hexagonal latices produce the densest packing of all latices. Intuitively one would imagine a denser packing in spatial domain will correspond to a larger period in the frequency domain and hence a much bigger frequency band can be captured for reconstruction. With that being said, I am curios to find out how BCC reconstruction performs under noise because the capability of capturing higher frequency also leads to the inherent property of reconstructing more noise! This is however an intuition and further study is required to verify this.


Hexagon is the only shape that covers a given 2D region using the least amount of perimeter, while other such optimal figures, for example, circle, fails to completely cover a 2D region. It is no surprise that hexagonal shapes can be found quite often in nature for example, honey comb, layout of of the fly’s compound eyes and etc.

Honey Comb

Honey Comb

Compound Eye

Compound Eye

As early as 1611 AD, Johannes Kepler conjectured that if cannon balls are arranged in hexagonal patters on 2D sheets and the sheets being stacked over one another then the whole arrangement, called Hexagonally Closed Packed (HCP) produces densest possible packing for any regular patterns. Interestingly this packing structure is the same as how oranges are stacked in grocery stores which is a Face Centric Cubic (FCC) structure. Another packing structure is Body Centric Cubic, where one extra lattice point is inserted in the center of the cubic lattice. Both FCC and BCC are the 3D counterparts of 2D hexagonal lattice.

A FCC lattice

A BCC lattice

Problem, Tasks and Scenario:

This project will investigate the performance of BCC lattices over CC lattices in terms of quality of reconstruction, speed and space for a volume’s normal data. A typical task of a researcher in the field of volume visualization is to find out which reconstruction technique is best for reproducing normals for a given arbitrary volume data. One scenario would be that the researcher is presented with a software tool that takes two arbitrary volume data, one that is sampled on CC grid and the other which has been sampled over BCC grid. The tool would provide the user with necessary interaction component whereby he/she can change the parameter of various reconstruction filters both on CC and BCC grids. Finally the tool would also provide the user a way to compare the results.

Result comparison:

Results can be compared both perceptually and numerically. However, numerical comparison is, perhaps, not possible unless the actual continuous function is available and only perceptual metric is used in this case. Perceptual metrics can be applied the way Ali Reza Entezari did in his studies [4], where volume data are under-sampled on both the CC and BCC grids and then reconstructed and finally observed for any visual artifacts. On the other hand, we can have a continuous function defined on a volume first and then sample that function both in CC and BCC grid and then reconstruct them respectively. Finally we can compare the results using numeric metrics, for example, absolute error [4]. Since we are focusing on reconstructing normals, i.e. the first partial derivatives of the volume data, numerical approach for comparison is more suitable with synthetic data.

Implementation Details:

For this project C/C++ and OpenGL will be used as the primary language and tool respectably. On a CC grid normals will be reconstructed using various known filters for example Tri-Cubic B-Spline. Quasi interpolation methods will be used to reconstruct normals over BCC. Reconstruction over BCC is however still an on going research and for this lots of literature review as well as research has to be done before settling on a reconstruction method.

Project Breakdown:

Oct 13th – Nov 1st: Literature Review:

Nov 2st – 8th: Implementation of Tri-Cubic B-Spline Over CC lattices

Nov 9th – Dec 1st: Implementation of Quasi Interpolation in BCC lattices

Dec 2nd – Dec 10th: Report Writing


[1] L. Condat, T. Blu, M. Unser, “Beyond Interpolation: Optimal Reconstruction by Quasi-Interpolation,” Proceedings of the 2005 IEEE International Conference on Image Processing (ICIP’05), Genova, Italy, September 11-14, 2005, pp. I-33-I-36.

[2] M. Unser, “Sampling – 50 years after Shannon,” Proceedings of the IEEE, vol. 88, no. 4, pp. 569-587, April 2000.

[3] L. Condat, D. Van De Ville,“Quasi-Interpolating Spline Models for Hexagonally-Sampled Data,” IEEE Transactions on Image Processing, vol. 16, no. 5, pp. 1195-1206, May 2007.

[4] Alireza Entezari, Dimitri Van De Ville, Torsten Möller, “Practical Box Splines for Reconstruction on the Body Centered Cubic Lattice,” IEEE Transactions on Visualization and Computer Graphics, TVCG 14(2): 313-328, 2008.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: