Spectral processing of point-sampled geometry

ABSTRACT

We present a new framework for processing point-sampled objects using spectral methods. By establishing a concept of local frequencies on geometry, we introduce a versatile spectral representation that provides a rich repository of signal processing algorithms. Based on an adaptive tesselation of the model surface into regularly resampled displacement fields, our method computes a set of windowed Fourier transforms creating a spectral decomposition of the model. Direct analysis and manipulation of the spectral coefficients supports effective filtering, resampling, power spectrum analysis and local error control. Our algorithms operate directly on points and normals, requiring no vertex connectivity information. They are computationally efficient, robust and amenable to hardware acceleration. We demonstrate the performance of our framework on a selection of example applications including noise removal, enhancement, restoration and subsampling.

REFERENCES

• 1: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 2: Bracewell, R.N. The Fourier Transform and Its Applications. McGraw-Hill, New York, 2nd rev. ed., 1986.
• 3: Bernd Gärtner, Fast and Robust Smallest Enclosing Balls, Proceedings of the 7th Annual European Symposium on Algorithms, p.325-338, July 16-18, 1999
• 4: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 5: Dan E. Dudgeon , Russell M. Mersereau, Multidimensional Digital Signal Processing, Prentice Hall Professional Technical Reference, 1990
• 6: H. Freeman , R. Shapira, Determining the minimum-area encasing rectangle for an arbitrary closed curve, Communications of the ACM, v.18 n.7, p.409-413, July 1975 [doi>10.1145/360881.360919]
• 7: Rafael C. Gonzalez , Richard E. Woods, Digital Image Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 8: Steven J. Gortler , Radek Grzeszczuk , Richard Szeliski , Michael F. Cohen, The lumigraph, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.43-54, August 1996 [doi>10.1145/237170.237200]
• 9: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 10: Igor Guskov , Kiril Vidimče , Wim Sweldens , Peter Schröder, Normal meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.95-102, July 2000 [doi>10.1145/344779.344831]
• 11: Anil K. Jain, Fundamentals of digital image processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 12: Zachi Karni , Craig Gotsman, Spectral compression of mesh geometry, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.279-286, July 2000 [doi>10.1145/344779.344924]
• 13: Kobbelt, L. Discrete Fairing. Proc. of the 7th IMA Conference on the Mathematics of Surfaces '97, 1997.
• 14: Aaron Lee , Henry Moreton , Hugues Hoppe, Displaced subdivision surfaces, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.85-94, July 2000 [doi>10.1145/344779.344829]
• 15: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 16: Don P. Mitchell, Generating antialiased images at low sampling densities, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.65-72, August 1987
• 17: Papoulis, A. Signal Analysis, McGraw Hill, 1977.
• 18: Hanspeter Pfister , Matthias Zwicker , Jeroen van Baar , Markus Gross, Surfels: surface elements as rendering primitives, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.335-342, July 2000 [doi>10.1145/344779.344936]
• 19: Szymon Rusinkiewicz , Marc Levoy, QSplat: a multiresolution point rendering system for large meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.343-352, July 2000 [doi>10.1145/344779.344940]
• 20: Gabriel Taubin, A signal processing approach to fair surface design, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.351-358, September 1995 [doi>10.1145/218380.218473]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Design, Experimentation, Theory

Keywords:
Fourier transform, point-based representations, signal processing, spectral filtering, subsampling