Image Sampling with Quasicrystals

Mark Grundland ; Jirí Patera ; Zuzana Masáková ; Neil A. Dodgson

Symmetry, integrability and geometry: methods and applications, Tome 5 (2009)

Résumé

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.

Détail

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

Bibliographie

[1] Amidror I., “Scattered data interpolation methods for electronic imaging systems: a survey”, J. Electronic Imaging, 11 (2002), 157–176 | DOI

[2] Chen L., Moody R. V., Patera J., “Non-crystallographic root systems”, Quasicrystals and Discrete Geometry (Toronto, ON, 1995), Fields Inst. Monogr., 10, Amer. Math. Soc., Providence, RI, 1998, 135–178 | MR | Zbl

[3] Cohen M. F., Shade J., Hiller S., Deussen O., “Wang tiles for image and texture generation”, Proceedings of SIGGRAPH, ACM Trans. Graph., 22:3 (2003), 287–294 | DOI

[4] Cook R. L., “Stochastic sampling in computer graphics”, ACM Trans. Graphics, 5 (1986), 51–72 | DOI

[5] Deussen O., Hiller S., van Overveld C., Strothotte T., “Floating points: a method for computing stipple drawings”, Proceedings of EUROGRAPHICS, Computer Graphics Forum, 19:3 (2000), 41–50 | DOI

[6] Dippe M. A. Z., Wold E. H., “Antialiasing through stochastic sampling”, Proceedings of SIGGRAPH, Computer Graphics, 19:3 (1985), 69–78 | DOI

[7] Du Q., Faber V., Gunzburger M., “Centroidal Voronoi tessellations: applications and algorithms”, SIAM Rev., 41 (1999), 637–676 | DOI | MR | Zbl

[8] Dunbar D., Humphreys G., “A spatial data structure for fast Poisson-disk sample generation”, Proceedings of SIGGRAPH, ACM Trans. Graph., 25:3 (2006), 503–508 | DOI | MR

[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 | DOI

[10] Glassner A., Principles of digital image synthesis, Vol. 1, Morgan Kaufmann, 1995

[11] Glassner A., “Aperiodic tiling”, IEEE Computer Graphics and Applications, 18:3 (1998), 83–90 | DOI

[12] Glassner A., “Penrose tiling”, IEEE Computer Graphics and Applications, 18:4 (1998), 78–86 | DOI

[13] Goodman-Strauss C., “Aperiodic hierarchical tilings”, Foams, Emulsions, and Cellular Materials (Cargèse, 1997), NATO Adv. Sci. Inst. Ser. E Appl. Sci., 354, Kluwer Acad. Publ., Dordrecht, 1999, 481–496 | MR

[14] Grunbaum B., Shephard G.C., Tilings and patterns, WH Freeman, 1987 | MR

[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 | DOI

[17] Hausner A., “Simulating decorative mosaics”, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM, New York, 2001, 573–580

[18] Hausner A., “Pointillist halftoning”, Proceedings of the International Conference on Computer Graphics and Imaging, 2005, 134–139

[19] Hiller S., Deussen O., Keller A., “Tiled blue noise samples”, Proceedings of Vision, Modeling and Visualization Conference, 2001, 265–272

[20] Hiller S., Hellwig H., Deussen O., “Beyond stippling – methods for distributing objects on the plane”, Proceedings of SIGGRAPH, Computer Graphics Forum, 22:3 (2003), 515–522 | DOI

[21] Jones T. R., “Efficient generation of Poisson-disk sampling patterns”, J. Graphics Tools, 11:2 (2006), 27–36

[22] Klassen R. V., “Filtered jitter”, Proceedings of SIGGRAPH, Computer Graphics Forum, 19:4 (2000), 223–230 | DOI | MR

[23] Kopf J., Cohen-Or D., Deussen O., Lischinski D., “Recursive Wang tiles for real-time blue noise”, ACM Transactions on Graphics, 25:3 (2006), 509–518 | DOI

[24] Lagae A., Dutre P., “A procedural object distribution function”, ACM Trans. Graphics, 24 (2005), 1442–1461 | DOI

[25] Lagae A., Dutre P., “An alternative for Wang tiles: colored edges versus colored corners”, ACM Trans. Graphics, 25 (2006), 1442–1459 | DOI

[26] Lagae A., Dutre P., “A comparison of methods for generating Poisson disk distributions”, Computer Graphics Forum, 27:1 (2008), 114–129 | DOI

[27] Lagae A., Kaplan C. S., Fu C.-W., Ostromoukhov V., Deussen O., Tile-based methods for interactive applications, International Conference on Computer Graphics and Interactive Techniques, ACM, New York, 2008

[28] Lu P. J., Steinhardt P. J., “Decagonal and quasi-crystalline tilings in medieval Islamic architecture”, Science, 315:5815 (2007), 1106–1110 | DOI | MR

[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 | DOI | MR | Zbl

[30] McCool M., Fiume E., “Hierarchical Poisson disk sampling distributions”, Proceedings of Graphics Interface, 1992, 94–105

[31] Meyer Y., Algebraic numbers and harmonic analysis, North-Holland, 1972 | MR | Zbl

[32] Moody R. V., Patera J., “Quasicrystals and icosians”, J. Phys. A: Math. Gen., 26 (1993), 2829–2853 | DOI | MR | Zbl

[33] Moody R. V., Patera J., “Dynamical generation of quasicrystals”, Lett. Math. Phys., 36 (1996), 291–300 | DOI | MR | Zbl

[34] Ostromoukhov V., “Building 2D low-discrepancy sequences for hierarchical importance sampling using dodecagonal aperiodic tiling”, Proceedings of SIGGRAPH, 2007, 139–142

[35] Ostromoukhov V., “Sampling with polyominoes,”, Proceedings of SIGGRAPH, ACM Transactions on Graphics, 26:3 (2007), 078, 1–6 | DOI

[36] Press W., Teukolsky S. A., Vetterling W. T., Flannery B. P., Numerical recipes in $C$, 2nd ed., Cambridge University Press, 1992 | MR

[37] Rangel-Mondragon J., Abas S. J., “Computer generation of Penrose tilings”, Computer Graphics Forum, 7:1 (1988), 29–37 | DOI

[38] Secord A., “Weighted Voronoi stippling”, Proceedings of the Second International Symposium on Non-Photorealistic Animation and Rendering, 2002, 37–43

[39] Senechal M., Quasicrystals and geometry, Cambridge University Press, Cambridge, 1995 | MR | Zbl

[40] Sharma G., Digital color imaging handbook, CRC Press, 2003

[41] 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 | DOI

[42] Stam J., Aperiodic texture mapping, Technical Report ERCIM-01/97-R046, European Research Consortium for Informatics and Mathematics, 1997

[43] Wei L.-Y., “Tile-based texture mapping on graphics hardware”, Proceedings of the ACM Conference on Graphics Hardware, 2004, 55–63

[44] Wei L.-Y., “Parallel Poisson disk sampling”, Proceedings of SIGGRAPH, ACM Transactions on Graphics, 27:3 (2008), Article No. 20, 1–10