Similarity-based surface modelling using geodesic fans

ABSTRACT

We present several powerful new techniques for similarity-based modelling of surfaces using geodesic fans, a new framework for local surface comparison. Similarity-based surface modelling provides intelligent surface manipulation by simultaneously applying a modification to all similar areas of the surface. We demonstrate similarity-based painting, deformation, and filtering of surfaces, and show how to vary our similarity measure to encompass geometry, textures, or other arbitrary signals. Geodesic fans are neighbourhoods uniformly sampled in the geodesic polar coordinates of a point on a surface. We show how geodesic fans offer fast approximate alignment and comparison of surface neighbourhoods using simple spoke reordering. As geodesic fans offer a a structurally equivalent definition of neighbourhoods everywhere on a surface, they are amenable to standard acceleration techniques and are well-suited to extending image domain methods for modelling by example to surfaces.

REFERENCES

• 1: Michael Ashikhmin, Synthesizing natural textures, Proceedings of the 2001 symposium on Interactive 3D graphics, p.217-226, March 2001 [doi>10.1145/364338.364405]
• 2: Stephen Brooks , Neil Dodgson, Self-similarity based texture editing, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 3: Henning Biermann , Ioana Martin , Fausto Bernardini , Denis Zorin, Cut-and-paste editing of multiresolution surfaces, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 4: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558]
• 5: Alexei A. Efros , Thomas K. Leung, Texture Synthesis by Non-Parametric Sampling, Proceedings of the International Conference on Computer Vision-Volume 2, p.1033, September 20-25, 1999
• 6: Shachar Fleishman , Iddo Drori , Daniel Cohen-Or, Bilateral mesh denoising, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 7: {FJP01} Freeman W. T., Jones T. R., Pasztor E. C.: Example-based Super-resolution. Tech. rep., Mitsubishi Electric Research Laboratories, July 2001. TR2001-30.
• 8: Kurt W. Fleischer , David H. Laidlaw , Bena L. Currin , Alan H. Barr, Cellular texture generation, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.239-248, September 1995 [doi>10.1145/218380.218447]
• 9: Thomas Funkhouser , Patrick Min , Michael Kazhdan , Joyce Chen , Alex Halderman , David Dobkin , David Jacobs, A search engine for 3D models, ACM Transactions on Graphics (TOG), v.22 n.1, p.83-105, January 2003 [doi>10.1145/588272.588279]
• 10: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• 11: {Goe70} Goetz A.: Introduction to Differential Geometry. Addison-Wesley, 1970.
• 12: 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]
• 13: Aaron Hertzmann , Charles E. Jacobs , Nuria Oliver , Brian Curless , David H. Salesin, Image analogies, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.327-340, August 2001 [doi>10.1145/383259.383295]
• 14: {HK03} Hamza A. B., Krim H.: Geodesic object representation and recognition. In DGCI 2003 (2003), Nystroöm I., de Baja G. S., Svensson S., (Eds.), vol. 2886 of Lecture Notes in Computer Science, Springer-Verlag, pp. 378--387.
• 15: Aaron Hertzmann , Nuria Oliver , Brian Curless , Steven M. Seitz, Curve analogies, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 16: Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001 [doi>10.1145/383259.383282]
• 17: Thouis R. Jones , Frédo Durand , Mathieu Desbrun, Non-iterative, feature-preserving mesh smoothing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 18: Andrew E. Johnson , Martial Hebert, Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.433-449, May 1999 [doi>10.1109/34.765655]
• 19: {KPNK03} Körtgen M., Park G.-J., Novotni M., Klein R.: 3d shape matching with 3d shape contexts. In Proceedings of the 7th Central European Seminar on Computer Graphics (2003).
• 20: {KS98} Kimmel R., Sethian J.: Computed geodesic paths on manifolds. Proceedings of the National Academy of Sciences 95, 15 (July 1998), 8431--8435.
• 21: Justin Legakis , Julie Dorsey , Steven Gortler, Feature-based cellular texturing for architectural models, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.309-316, August 2001 [doi>10.1145/383259.383293]
• 22: {LSZ01} Liu C., Shum H.-Y., Zhang C.-S.: A two-step approach to hallucinating faces: Global parametric model and local non-parametric model. In IEEE Conference on Computer Vision and Pattern Recognition (2001), IEEE, pp. 192--198.
• 23: Sebastian Magda , David Kriegman, Fast texture synthesis on arbitrary meshes, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium
• 24: {MKY98} Mokhtarian F., Khalili N., Yuen P.: Multi-scale 3d free-from surface smoothing. In Proceedings of the Ninth British Machine Vision Conference (1998), British Machine Vision Association, pp. 730--739.
• 25: {PS98} Polthier K., Schmies M.: Straightest geodesics on polyhedral surfaces. Mathematical Visualization (1998), 135--150.
• 26: Cyril Soler , Marie-Paule Cani , Alexis Angelidis, Hierarchical pattern mapping, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 27: Shigeo Takahashi , Yoshihisa Shinagawa , Tosiyasu L. Kunii, Curve and Surface Design Using Multiresolution Constraints, Proceedings of the 1997 Conference on Computer Graphics International, p.121, June 23-27, 1997
• 28: Greg Turk, Texture synthesis on surfaces, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.347-354, August 2001 [doi>10.1145/383259.383297]
• 29: Xin Tong , Jingdan Zhang , Ligang Liu , Xi Wang , Baining Guo , Heung-Yeung Shum, Synthesis of bidirectional texture functions on arbitrary surfaces, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 30: Tomihisa Welsh , Michael Ashikhmin , Klaus Mueller, Transferring color to greyscale images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 31: Li-Yi Wei , Marc Levoy, Fast texture synthesis using tree-structured vector quantization, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.479-488, July 2000 [doi>10.1145/344779.345009]
• 32: Li-Yi Wei , Marc Levoy, Texture synthesis over arbitrary manifold surfaces, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.355-360, August 2001 [doi>10.1145/383259.383298]
• 33: William Welch , Andrew Witkin, Free-form shape design using triangulated surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.247-256, July 1994 [doi>10.1145/192161.192216]
• 34: Lexing Ying , Aaron Hertzmann , Henning Biermann , Denis Zorin, Texture and Shape Synthesis on Surfaces, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.301-312, June 25-27, 2001
• 35: Steve Zelinka , Michael Garland, Interactive texture synthesis on surfaces using jump maps, Proceedings of the 14th Eurographics workshop on Rendering, June 25-27, 2003, Leuven, Belgium

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement