box spline reconstruction filters on BCC lattice Alireza Entezari Ramsay Dyer Torsten Mller Minho Kim problem Whats the optimal sampling pattern in 3D

and which reconstruction filter can we use for it? sampling theory in 1D Fourier transform one-to-one mapping between spatial and Fourier domains (image courtesy of [1])

multiplication and convolution are dual operations: F(fg)=F(f)F(g) F(fg)=F(f)F(g) Dirac comb function (c) infinite series of equidistant Dirac impulses Fourier transform has the same shape (image courtesy of [1])

sampling F(fc)=F(f)F(c) (image courtesy of [1]) reconstruction to remove all the replicated spectra except the primary spectrum requires >2BB (B: highest frequency of f) requires low-pass filter b/

F-1(b/)(t) = sinc(t) = sin(t)/t (image courtesy of [1]) recontruction (contd) F-1(b/F(fg))=F-1(b/)(fg) weighted sum of basis functions, sinc (image courtesy of [1])

reconstruction (contd) (image courtesy of [2]) aliasing happens when the condition >2BBis not met cannot reconstruct the original signal (image courtesy of [5])

reconstruction filters Ideal low-pass filter (sinc function) is impractical since it has infinite support in spatial domain. We need alternative filters but they may have defects such as post-aliasing, smoothing (blur), ringing (overshoot), anisotropy. examples: Barlett filter (linear filter), cubic

filter, truncated sinc filter, etc. defects due to filters post-aliasing - sample frequency ripple (image courtesy of [5]) ringing (overshoot) (image courtesy of [5])

sampling theory in higher dimensions reconstruction filters two ways of extending filters separable (tensor-product) extension for Cartesian lattice only spherical extension

doesnt guarantee zero-crossings of frequency responses at all replicas of the spectrum optimal sampling pattern in 3D sparsest pattern in spatial domain tightest arrangement of the replicas of the spectrum in Fourier domain densest sphere packing lattice FCC (Face Centered Cubic) lattice

dual of FCC lattice BCC (Body Centered Cubic) lattice dual lattice Fourier transform of a sampling lattice with sampling matrix T has sampling matrix T-T ([6], Theorem 1.) example: for BCC lattice, T=[T1,T2,T3], T1=[2 0 0]T, T2=[0 2 0]T, T3=[1 1 1]T

T-T=1/2[T1 T2 T3], T1=[1 0 -1], T2=[0 1 -1], T3=[-1 -1 2], which is the sampling matrix of FCC lattice BCC and FCC lattices FCC lattice BCC lattice (image courtesy of Wikipedia)

reconstruction filters Ideally, the reconstruction filter is the inverse Fourier transform of the characteristic function of the Voronoi cell of FCC lattice, which is impractical. Alternatively, we use linear or cubic box spline filters of which support is rhombic dodecahedron, (3D shadow of a 4D hypercube) the first neighbor cell of BCC

lattice. rhombic dodecahedron the first neighbor cell of BCC lattice (image courtesy of [7]) animated version (from MathWorld): http:// mathworld.wolfram.com/RhombicDodecahedron.html

linear box spline filter Fourier transform of a linear box spline filter can be obtained by projection-slice theorem. 4D hypercube T(x,y,z,w) projection F

linear box spline on BBC lattice LRD(x,y,z) F F(T) slicing F(LRD) zero-crossings at all the frequencies of

replicas ([7]) no sampling frequency ripple ([5]) cubic box spline filter 4D hypercube tensor product of self-convolution four 1D triangle functions projection

linear box spline on BBC lattice self-convolution projection cubic box spline on BBC lattice cubic box spline filter (contd) 1D-2D analogy

self-convolution projection self-convolution (image courtesy of [7],[8]) projection references

[1] Oliver Kreylos, Sampling Theory 101, http://graphics.cs.ucdavis.edu/~okreylos/PhDStudies/Winter2000/SamplingTheory.html , 2000 [2] Rebecca Willett, Sampling Theory and Spline Interpolation, http://cnx.org/content/m11126/latest [3] truncated octahedron, http://mathworld.wolfram.com/TruncatedOctahedron.html,

MathWorld [4] rhombic dodecahedron, http://mathworld.wolfram.com/RhombicDodecahedron.html, MathWorld [5] Stephen R. Marschner and Richard J. Lobb, An Evaluation of Reconstruction Filters for Volume Rendering, Proceedings of Visualization '94 [6] Alireza Entezari, Ramsay Dyer, and Torsten Mller, From Sphere Packing to the Theory of Optimal Lattice Sampling, PIMS/BIRS Workshop, May 22-27, 2004 [7] Alireza Entezari, Ramsay Dyer, Torsten Mller, Linear and Cubic Box Splines for the Body Centered Cubic Lattice,, Proceedings of IEEE Visualization 2B004 [8] Hartmut Prautzsch and Wolfgang Boehm, Box Splines, 2002