knot intervals and T-splines by Thomas W. Sederberg

knot intervals and T-splines by Thomas W. Sederberg

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

Recently Viewed Presentations

  • Complexity & Formality as Features of Academic Writing

    Complexity & Formality as Features of Academic Writing

    Written English generally has a much denser pattern of words, it is more lexically dense. If we define lexical density as the number of content words in a clause, then written English has a higher lexical density than spoken English...
  • The Value Of The Valley (2)

    The Value Of The Valley (2)

    Joshua 6 * There are some lessons to be learned, that are learned only in the valley. There are visions to be seen, that are seen only in the valley. There are some strengths to be gained, that are only...
  • The HEART - Ms. Davenport's Class

    The HEART - Ms. Davenport's Class

    Heart Sounds. Listenwith stethoscope on anterior wall of chest ( auscultate ) Rhythmic and repetitive sounds "Lub dub" First sound or lub-caused by vibration and abrupt closure of AV valves as ventricles contract. Longer sound with a lower pitch. Second...
  • Machine Learning Lecture 4

    Machine Learning Lecture 4

    A few things.. If you haven't starting using GPU server, please do it now! Kaggle competition ends in less than 1 month, please start it right now
  • Titre du Poster

    Titre du Poster

    Matériel - Méthodes ou observation. Congrès National de Chirurgie 2019. Il s'agit d'un patient de 70ans opéré il y a 4 ans pour un syndrome occlusif et qui présente suite à un accident de la voie publique un traumatisme au...
  • Exempt Organization Future LeadersTaxProgram:unrelated ...

    Exempt Organization Future LeadersTaxProgram:unrelated ...

    The Tax Court has placed the burden on the taxpayer to prove direct connection to deductions. CORE Special Purpose Fund v. Comm'r, TC Memo 1985-48 (Tax Court disallowed deductions - taxpayer did not prove actual incurrence of expenses, or that...
  • 2nd EPSA 2011 SC Meeting, 6. September 2011, Maastricht (NL)

    2nd EPSA 2011 SC Meeting, 6. September 2011, Maastricht (NL)

    European Institute of Public Administration (EIPA), Maastricht (NL) ... of government Limited knowledge of methods and lack of skills and ability to drive effective innovation processes in practice Insufficient generation and use of data to inform, drive, learn from and...
  • Freshman Seminar Daily Agenda

    Freshman Seminar Daily Agenda

    Objectives. Cite strong and thorough textual evidence to support analysis of what the text says explicitly as well as inferences drawn from the text, including determining where the text leaves matters uncertain.