METRICS FOR IMAGE SURFACE APPROXIMATION BASED ON TRIANGULAR MESHES
DOI:
https://doi.org/10.5566/ias.1591Keywords:
accuracy metrics, point cloud, surface approximation, triangular meshesAbstract
Surface approximation plays an important role in several application fields, such as computer-aided design, computer graphics, remote sensing, computer vision, robotics, architecture, and manufacturing. A common problem present in these areas is to develop efficient methods for generating, processing, analyzing, and visualizing large amount of 3D data. Triangular meshes constitute a flexible representation of sampled points that are not regularly distributed in space, such that the model can be adaptively adjusted to the data density. The choice of metrics for building the triangular meshes is crucial to produce high quality models. This paper proposes and evaluates different measures to incrementally refine a Delaunay triangular mesh for image surface approximation until either a certain accuracy is obtained or a maximum number of iterations is achieved. Experiments on several data sets are performed to compare the quality of the resulting meshes.References
Alliez P, Desbrun M (2001). Progressive Compression for Lossless Transmission of Triangle Meshes. In: 28th Annual Conference on Computer Graphics and Interactive Techniques. ACM.
Araújo B, Lopes DS, Jepp P, Jorge JA, Wyvill B (2015). A Survey on Implicit Surface Polygonization. ACM Computing Surveys 47:60:1–60:39.
Barnsley MF, Hurd LP (1993). Fractal Image Compression. Wellesley, Massachusetts, USA: AK Peters.
Berg MD, Kreveld MV, Overmars M, Schwarzkopf OC (2000). Computational Geometry. Springer.
Berger M, Levine JA, Nonato LG, Taubin G, Silva CT (2013). A Benchmark for Surface Reconstruction. ACM Transactions on Graphics 32:20:1–20:17.
Boissonnat J, Pons J, Yvinec M (2009). From Segmented Images to Good Quality Meshes Using Delaunay Refinement. In: Emerging Trends in Visual Computing: LIX Fall Colloquium. Palaiseau, France.
Boissonnat JD, Shi KL, Tournois J, Yvinec M (2015). Anisotropic Delaunay Meshes of Surfaces. ACM Transactions on Graphics 34:14.
Bommes D, Lévy B, Pietroni N, Puppo E, Silva C, Tarini M, Zorin D (2013). Quad-Mesh Generation and Processing: A Survey. Computer Graphics Forum 32:51–76.
Botsch M, Kobbelt L, Pauly M, Alliez P, Lévy B (2010). Polygon Mesh Processing. CRC Press.
Brown JL (1991). Vertex Based Data Dependent Triangulations. Computer Aided Geometric Design 8:239–51.
Brown P (1997). A Fast Algorithm for Selective Refinement of Terrain Meshes. Computer Networks and ISDN Systems 29:1587–99.
Burt P, Adelson E (1983). The Laplacian Pyramid as a Compact Image Code. IEEE Transactions on Communications 31:532–40.
Chen H, Sun M, Steinbach E (2009). Compression of Bayer-pattern Video Sequences using Adjusted Chroma Subsampling. IEEE Transactions on Circuits and Systems for Video Technology 19:1891–6.
Cheng SW, Dey TK, Shewchuk J (2012). Delaunay Mesh Generation. CRC Press.
Chow MM (1997). Optimized Geometry Compression or Real-time Rendering. In: Press ICS, ed., IEEE Visualization. Phoenix, Arizona, USA.
Cignoni P, Montani C, Scopigno R (1998). A Comparison of Mesh Simplification Algorithms. Computers Graphics 22:37–54.
Cohen-Or D, Levin D, Remez O (1999). Progressive Compression of Arbitrary Triangular Meshes. In: IEEE Visualization, vol. 99.
de Berg M, Cheong O, van Kreveld M, Overmars M (2008). Computational Geometry: Algorithms and Applications. Springer-Verlag.
Deering M (1995). Geometry Compression. In: 22nd Annual Conference on Computer Graphics and Interactive Techniques. ACM.
DeVore RA, Jawerth B, Lucier BJ (1992). Image Compression through Wavelet Transform Coding. IEEE Transactions on Information Theory 38:719–46.
Dey T, Ray T (2010). Polygonal Surface Remeshing with Delaunay Refinement. Engineering with Computers 26:289–301.
Dyn N, Levin D, Rippa S (1990). Data Dependent Triangulations for Piecewise Linear Interpolation. IMA Journal on Numerical Analysis 10:137–54.
Evans F, Skiena S, Varshney A (1996). Optimizing Triangle Strips for Fast Rendering. In: Press ICS, ed., IEEE Visualization. San Francisco, California, USA.
Fisher Y (2012). Fractal Image Compression: Theory and Application. Springer Science & Business Media.
Garland M, Heckbert PS (1997). Surface Simplification Using Quadric Error Metrics. In: SIGGRAPH Conference Proceedings, Annual Conference Series. Los Angeles, California, USA.
Held G, Marshall TR (1996). Data and Image Compression: Tools and Techniques. John Wiley & Sons, Inc.
Hoppe H (1996). Progressive Meshes. In: 23rd Annual Conference on Computer Graphics and Interactive Techniques. ACM.
Hu L, Sander PV, Hoppe H (2009). Parallel View-Dependent Refinement of Progressive Meshes. In: Symposium on Interactive 3D Graphics and Games. ACM.
Keeler K, Westbrook J (1995). Short encodings of planar graphs and maps. Discrete Applied Mathematics 58:239–52.
Khodakovsky A, Schröder P, Sweldens W (2000). Progressive Geometry Compression. In: 27th Annual Conference on Computer Graphics and Interactive Techniques. ACM Press/Addison- Wesley Publishing Co.
Kim SJ, Kim CH, Levin D (2002). Surface Simplification Using a Discrete Curvature Norm. Computers Graphics 26:657–63.
Kolingerová I, Kohout J, Rulf M, Uher V (2010). A Proper Choice of Vertices for Triangulation Representation of Digital Images. Computer Vision and Graphics :41–8.
Lawson CL (1977). Software for C1 Surface Interpolation. In: Rice JR, ed., Mathematical Software III. New York: Academic Press, 161–94.
Lin T, Zhang P, Wang S, Zhou K, Chen X (2013). Mixed Chroma Sampling-rate High Efficiency Video Coding for Full-chroma Screen Content. IEEE Transactions on Circuits and Systems for Video Technology 23:173–85.
Lipman Y (2012). Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Transactions on Graphics 31:108.
Luebke D, Watson B, Cohen JD, Reddy M, Varshney A (2002). Level of Detail for 3D Graphics. New York, NY, USA: Elsevier Science Inc.
Ma J, Feng HY, Wang L (2013). Normal Vector Estimation for Point Clouds via Local Delaunay Triangle Mesh Matching. Computer Aided Design and Applications 10:399–411.
Maglo A, Courbet C, Alliez P, Hudelot C (2012). Progressive Compression of Manifold Polygon Meshes. Computers Graphics 36:349–59.
Meyer M, Desbrun M, Schröder P, Barr AH (2003). Discrete Differential-Geometry Operators for Triangulated 2-Manifolds. In: Visualization and Mathematics III. Springer, 35–57.
Moraes TF, Amorim PH, da Silva JV, Pedrini H (2017). Out-of-Core Progressive Web-Based Rendering of Triangle Meshes. In: VI ECCOMAS Thematic Conference on Computational Vision and Medical Image Processing. Porto, Portugal: Springer.
Morigi S, Rucci M (2013). Multilevel Mesh Simplification. The Visual Computer 30:479–92.
Mostafavian S, Adams MD (2015). An Optimization-based Mesh-generation Method for Image Representation. In: IEEE Pacific Rim Conference on Communications, Computers and Signal Processing. IEEE.
Nivoliers V, Yan DM, Lévy B (2012). Fitting Polynomial Surfaces to Triangular Meshes with Voronoi Squared Distance Minimization. Engineering with Computers 30:289–300.
Pedrini H (2000). An Adaptive Method for Terrain Surface Approximation based on Triangular Meshes. Ph.D. thesis, Electrical, Computer & Systems Engineering Department, Rensselaer Polytechnic Institute, Troy, NY, USA.
Peng J, Kim CS, Kuo CCJ (2005). Technologies for 3D Mesh Compression: A Survey. Journal of Visual Communication and Image Representation 16:688–733.
Polthier K, Schmies M (2006). Straightest Geodesics on Polyhedral Surfaces. ACM.
Preparata FP, Shamos M (2012). Computational Geometry: An Introduction. Springer Science & Business Media.
Quak E, Schumaker LL (1990). Cubic Spline Fitting Using Data Dependent Triangulations. Computer Aided Geometric Design 7:293–301.
Rabbani M, Jones PW (1991). Digital Image Compression Techniques, vol. 7. SPIE Press.
Ren M, Yang J, Sun H (2002). Tracing Boundary Contours in a Binary Image. Image and Vision Computing 20:125–31.
Rigler S, Bishop W, Kennings A (2007). FPGA-based Lossless Data Compression using Huffman and LZ77 Algorithms. In: Canadian Conference on Electrical and Computer Engineering. IEEE.
Rippa S (1992a). Adaptive Approximation by Piecewise Linear Polynomials on Triangulations of Subsets of Scattered Data. SIAM Journal on Scientific and Statistical Computing 13:1123–41.
Rippa S (1992b). Long and Thin Triangles Can Be Good for Linear Interpolation. IMA Journal on Numerical Analysis 29:257–70.
Rossignac J (1999). Edgebreaker: Connectivity Compression for Triangle Meshes. IEEE Transactions on Visualization and Computer Graphics 5:47–61.
Salinas D, Lafarge F, Alliez P (2015). Structure-Aware Mesh Decimation. Computer Graphics Forum 34:211–27.
Samet H (1990). The Design and Analysis of Spatial Data Structures. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.
Samet H (2006). Foundations of Multidimensional and Metric Data Structures. St. Louis, MO, USA: Morgan Kaufmann.
Sánchez-Cruz H, Bribiesca E, Rodríguez-Dagnino RM (2007). Efficiency of Chain Codes to Represent Binary Objects. Pattern Recognition 40:1660–74.
Scarlatos L (1992). Hierarchical Triangulation using Cartographic Coherence. Graphical Models and Image Processing 54:147–61.
Scholefield A, Dragotti PL (2014). Quadtree Structured Image Approximation for Denoising and Interpolation. IEEE Transactions on Image Processing 23:1226–39.
Shaffer E, Garland M (2001). Efficient Adaptive Simplification of Massive Meshes. In: IEEE Visualization. San Diego, CA, USA.
Silva MVG, van Kaick OM, Pedrini H (2002). Fast Mesh Rendering through Efficient Triangle Strip Generation. Journal of WSCG 10:127–34.
Skodras A, Christopoulos C, Ebrahimi T (2001). The JPEG 2000 Still Image Compression Standard. IEEE Signal Processing Magazine 18:36–58.
Sullivan GJ, Baker RL (1994). Efficient Quadtree Coding of Images and Video. IEEE Transactions on Image Processing 3:327–31.
Taubin G, Rossignac J (1998). Geometric Compression through Topological Surgery. ACM Transactions on Graphics 17:84–115.
Tóth Z, Viola I, Ferko A, Gröller E (2007). N-dimensional Data-Dependent Reconstruction Using Topological Changes. Topology based Methods in Visualization :183–98.
Tran A, Liu KM, Tzou KH, Vogel E (1987). An Efficient Pyramid Image Coding System. In: IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 12. IEEE.
Turán G (1984). On the Succinct Representation of Graphs. Discrete Applied Mathematics 8:289–94.
Van Aerschot W, Jansen M, Bultheel A (2009). Normal Mesh based Geometrical Image Compression. Image and Vision Computing 27:459–68.
van Kaick OM, Pedrini H (2006). Computer Vision and Graphics: International Conference. In: Wojciechowski K, Smolka B, Palus H, Kozera R, Skarbek W, Noakes L, eds., Assessment of Image Surface Approximation Accuracy given by Triangular Meshes. Warsaw, Poland: Springer Netherlands, 655–61.
van Kaick OM, Silva MVG, Pedrini H (2004). Efficient Generation of Triangle Strips from Triangulated Meshes. Journal of WSCG 12:475–81.
Wang K, Lo CP, Brook GA, Arabnia HR (2001). Comparison of Existing Triangulation Methods for Regularly and Irregularly Spaced Height Fields. International Journal of Geographical Information Science 15:743–62.
Xie YH, Tang XA, Sun MY (2008). Image Compression based on Classification Row by Row and LZW Encoding. In: Congress on Image and Signal Processing, vol. 1. IEEE.
Downloads
Published
Issue
Section
License
Copyright (c) 2018 Image Analysis & Stereology
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
