Symmetry, Integrability and Geometry: Methods and Applications (SIGMA)

SIGMA 5 (2009), 075, 23 pages      arXiv:0907.3604      https://doi.org/10.3842/SIGMA.2009.075

Image Sampling with Quasicrystals

Mark Grundland a, Jirí Patera b, Zuzana Masáková c and Neil A. Dodgson a
a) Computer Laboratory, University of Cambridge, UK
b) Centre de Recherches Mathématiques, Université de Montréal, Canada
c) Department of Mathematics FNSPE, Czech Technical University in Prague, Czech Republic

Received December 15, 2008, in final form July 06, 2009; Published online July 20, 2009

Abstract
We investigate the use of quasicrystals in image sampling. Quasicrystals produce space-filling, non-periodic point sets that are uniformly discrete and relatively dense, thereby ensuring the sample sites are evenly spread out throughout the sampled image. Their self-similar structure can be attractive for creating sampling patterns endowed with a decorative symmetry. We present a brief general overview of the algebraic theory of cut-and-project quasicrystals based on the geometry of the golden ratio. To assess the practical utility of quasicrystal sampling, we evaluate the visual effects of a variety of non-adaptive image sampling strategies on photorealistic image reconstruction and non-photorealistic image rendering used in multiresolution image representations. For computer visualization of point sets used in image sampling, we introduce a mosaic rendering technique.

Key words: computer graphics; image sampling; image representation; cut-and-project quasicrystal; non-periodic tiling; golden ratio; mosaic rendering.

pdf (4704 kb)   ps (46836 kb)   tex (51906 kb)

References

  1. Amidror I., Scattered data interpolation methods for electronic imaging systems: a survey, J. Electronic Imaging 11 (2002), 157-176.
  2. Chen L., Moody R.V., Patera J., Non-crystallographic root systems, in Quasicrystals and Discrete Geometry (Toronto, ON, 1995), Fields Inst. Monogr., Vol. 10, Amer. Math. Soc., Providence, RI, 1998, 135-178.
  3. Cohen M.F., Shade J., Hiller S., Deussen O., Wang tiles for image and texture generation, in Proceedings of SIGGRAPH, 2003, 287-294.
  4. Cook R.L., Stochastic sampling in computer graphics, ACM Trans. Graphics 5 (1986), 51-72.
  5. Deussen O., Hiller S., van Overveld C., Strothotte T., Floating points: a method for computing stipple drawings, in Proceedings of EUROGRAPHICS, 2000, 41-50.
  6. Dippe M.A.Z., Wold E.H., Antialiasing through stochastic sampling, in Proceedings of SIGGRAPH, 1985, 69-78.
  7. Du Q., Faber V., Gunzburger M., Centroidal Voronoi tessellations: applications and algorithms, SIAM Rev. 41 (1999), 637-676.
  8. Dunbar D., Humphreys G., A spatial data structure for fast Poisson-disk sample generation, in Proceedings of SIGGRAPH, 2006, 503-508.
  9. Eldar Y., Lindenbaum M., Porat M., Zeevi Y.Y., The farthest point strategy for progressive image sampling, IEEE Trans. Image Process. 6 (1997), 1305-1315.
  10. Glassner A., Principles of digital image synthesis, Vol. 1, Morgan Kaufmann, 1995.
  11. Glassner A., Aperiodic tiling, IEEE Computer Graphics and Applications 18 (1998), no. 3, 83-90.
  12. Glassner A., Penrose tiling, IEEE Computer Graphics and Applications 18 (1998), no. 4, 78-86.
  13. Goodman-Strauss C., Aperiodic hierarchical tilings, in Foams, Emulsions, and Cellular Materials (Cargèse, 1997), NATO Adv. Sci. Inst. Ser. E Appl. Sci., Vol. 354, Kluwer Acad. Publ., Dordrecht, 1999, 481-496.
  14. Grunbaum B., Shephard G.C., Tilings and patterns, WH Freeman, 1987.
  15. Grundland M., Style and content in digital imaging: Reconciling aesthetics with efficiency in image representation, VDM, 2008.
  16. Grundland M., Gibbs C., Dodgson N.A., Stylized multiresolution image representation, J. Electronic Imaging 17 (2008), 013009, 1-17.
  17. Hausner A., Simulating decorative mosaics, in Proceedings of SIGGRAPH, 2001, 573-580.
  18. Hausner A., Pointillist halftoning, in Proceedings of the International Conference on Computer Graphics and Imaging, 2005, 134-139.
  19. Hiller S., Deussen O., Keller A., Tiled blue noise samples, in Proceedings of Vision, Modeling and Visualization, 2001, 265-271.
  20. Hiller S., Hellwig H., Deussen O., Beyond stippling - methods for distributing objects on the plane, in Proceedings of EUROGRAPHICS, 2003, 515-522.
  21. Jones T.R., Efficient generation of Poisson-disk sampling patterns, J. Graphics Tools 11 (2006), no. 2, 27-36.
  22. Klassen R.V., Filtered jitter, Computer Graphics Forum 19 (2000), no. 4, 223-230.
  23. Kopf J., Cohen-Or D., Deussen O., Lischinski D., Recursive Wang tiles for real-time blue noise, in Proceedings of SIGGRAPH, 2006, 509-518.
  24. Lagae A., Dutre P., A procedural object distribution function, ACM Trans. Graphics 24 (2005), 1442-1461.
  25. Lagae A., Dutre P., An alternative for Wang tiles: colored edges versus colored corners, ACM Trans. Graphics 25 (2006), 1442-1459.
  26. Lagae A., Dutre P., A comparison of methods for generating Poisson disk distributions, Computer Graphics Forum 27 (2008), no. 1, 114-129.
  27. Lagae A., Kaplan C.S., Fu C.-W., Ostromoukhov V., Deussen O., Tile-based methods for interactive applications, SIGGRAPH 2008 Class Notes, ACM, 2008.
  28. Lu P.J., Steinhardt P.J., Decagonal and quasi-crystalline tilings in medieval Islamic architecture, Science 315 (2007), no. 5815, 1106-1110.
  29. Masáková Z., Patera J., Zich J., Classification of Voronoi and Delone tiles of quasicrystals. III. Decagonal acceptance window of any size, J. Phys. A: Math. Gen. 38 (2005), 1947-1960.
  30. McCool M., Fiume E., Hierarchical Poisson disk sampling distributions, in Proceedings of Graphics Interface, 1992, 94-105.
  31. Meyer Y., Algebraic numbers and harmonic analysis, North-Holland, 1972.
  32. Mitchell D.P., Spectrally optimal sampling for distribution ray tracing, in Proceedings of SIGGRAPH, 1991, 157-164.
  33. Mojsilovic A., Soljanin E., Color quantization and processing by Fibonacci lattices, IEEE Trans. Image Process. 10 (2001), 1712-1725.
  34. Moody R.V., Patera J., Quasicrystals and icosians, J. Phys. A: Math. Gen. 26 (1993), 2829-2853.
  35. Moody R.V., Patera J., Dynamical generation of quasicrystals, Lett. Math. Phys. 36 (1996), 291-300.
  36. Ostromoukhov V., Mathematical tools for computer-generated ornamental patterns, Lecture Notes in Computer Science, Vol. 1375, 1998, 193-223.
  37. Ostromoukhov V., Donohue C., Jodoin P.M., Fast hierarchical importance sampling with blue noise properties, in Proceedings of SIGGRAPH, 2004, 488-495.
  38. Ostromoukhov V., Building 2D low-discrepancy sequences for hierarchical importance sampling using dodecagonal aperiodic tiling, in Proceedings of GRAPHICON, 2007, 139-142.
  39. Ostromoukhov V., Sampling with polyominoes, in Proceedings of SIGGRAPH, 2007, 078, 1-6.
  40. Patera J., Non-crystallographic root systems and quasicrystals. in The Mathematics of Long-Range Aperiodic Order (Waterloo, ON, 1995), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., Vol. 489, Kluwer Acad. Publ., Dordrecht, 1997, 443-465.
  41. Press W., Teukolsky S.A., Vetterling W.T., Flannery B.P., Numerical recipes in C, 2nd ed., Cambridge University Press, 1992.
  42. Rangel-Mondragon J., Abas S.J., Computer generation of Penrose tilings, Computer Graphics Forum 7 (1988), no. 1, 29-37.
  43. Secord A., Weighted Voronoi stippling, in Proceedings of the Second International Symposium on Non-Photorealistic Animation and Rendering, 2002, 37-43.
  44. Senechal M., Quasicrystals and geometry, Cambridge University Press, Cambridge, 1995.
  45. Sharma G., Digital color imaging handbook, CRC Press, 2003.
  46. Shechtman D., Blech I., Gratias D., Cahn J.W., Metallic phase with long-range orientational order and no translational symmetry, Phys. Rev. Lett. 53 (1984), 1951-1953.
  47. Shirley P., Discrepancy as a quality measure for sample distributions, in Proceedings of EUROGRAPHICS, 1991, 183-194.
  48. Stam J., Aperiodic texture mapping, European Research Consortium for Informatics and Mathematics, Technical Report ERCIM-01/97-R046, 1997.
  49. Wei L.-Y., Tile-based texture mapping on graphics hardware, in Proceedings of the ACM Conference on Graphics Hardware, 2004, 55-63.
  50. Wei L.-Y., Parallel Poisson disk sampling, in Proceedings of SIGGRAPH, 2008, 020, 1-10.
  51. White K.B., Cline D., Egbert P.K., Poisson disk point sets by hierarchical dart throwing, in Proceedings of the IEEE Symposium on Interactive Ray Tracing, 2007, 129-132.

Previous article   Next article   Contents of Volume 5 (2009)