Article
Incremental Labelling of Voronoi Vertices for Shape Reconstruction
J. Peethambaran,
A.D. Parakkat,
A. Tagliasacchi,
R. Wang,
R. Muthuganapathy,
J. Peethambaran
Department of Engineering Design, Indian Institute of Technology, Madras, India
Department of Mathematics and Computing Science, Saint Mary's University, Halifax, Nova Scotia, Canada
Search for more papers by this authorA.D. Parakkat
Department of Engineering Design, Indian Institute of Technology, Madras, India
Search for more papers by this authorA. Tagliasacchi
Department of Computer Science, University of Victoria, Victoria, British Columbia, Canada
Search for more papers by this authorR. Wang
Schulich School of Engineering, University of Calgary, Calgary, Alberta, Canada
Search for more papers by this authorR. Muthuganapathy
Department of Engineering Design, Indian Institute of Technology, Madras, India
Search for more papers by this authorJ. Peethambaran,
A.D. Parakkat,
A. Tagliasacchi,
R. Wang,
R. Muthuganapathy,
J. Peethambaran
Department of Engineering Design, Indian Institute of Technology, Madras, India
Department of Mathematics and Computing Science, Saint Mary's University, Halifax, Nova Scotia, Canada
Search for more papers by this authorA.D. Parakkat
Department of Engineering Design, Indian Institute of Technology, Madras, India
Search for more papers by this authorA. Tagliasacchi
Department of Computer Science, University of Victoria, Victoria, British Columbia, Canada
Search for more papers by this authorR. Wang
Schulich School of Engineering, University of Calgary, Calgary, Alberta, Canada
Search for more papers by this authorR. Muthuganapathy
Department of Engineering Design, Indian Institute of Technology, Madras, India
Search for more papers by this authorAbstract
We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece-wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non-uniformly (ε-sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non-uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm.
References
- [AB98] Amenta N., Bern M.: Surface reconstruction by Voronoi filtering. In Proceedings of the 14th Annual Symposium on Computational Geometry (New York, NY, USA, 1998), SCG '98, ACM, pp. 39–48.
10.1145/276884.276889 Google Scholar
- [ABE98] Amenta N., Bern M., Eppstein D.: The crust and the beta-skeleton: Combinatorial curve reconstruction. Graphical Models and Image Processing 60, 2 (1998), 125–135.
- [ACK01] Amenta N., Choi S., Kolluri R. K.: The power crust, unions of balls, and the medial axis transform. Computational Geometry 19, 2–3 (2001), 127–153.
- [AK01] Amenta N., Kolluri R. K.: The medial axis of a union of balls. Computational Geometry 20, 1–2 (2001), 25–37.
- [AM97] Attali D., Montanvert A.: Computing and simplifying 2D and 3D continuous skeletons. Computer Vision and Image Understanding 67, 3 (1997), 261–273.
- [AM01] Althaus E., Mehlhorn K.: Traveling salesman-based curve reconstruction in polynomial time. SIAM Journal on Computing 31, 1 (2001), 27–66.
- [AMNS00] Althaus E., Mehlohrn K., Naher S., Schirra S.: Experiments on curve reconstruction. In Proceedings of 2nd Workshop on Algorithms Engineering Experiments (2000), pp. 104–114.
- [Att54] Attneave F.: Some informational aspects of visual perception. Psychological Review 61, 3 (May1954), 183–193.
- [Att98] Attali D.: r-regular shape reconstruction from unorganized points. Computational Geometry 10, 4 (1998), 239–247.
- [BA92] Brandt J. W., Algazi V.: Continuous skeleton computation by Voronoi diagram. CVGIP: Image Understanding 55, 3 (1992), 329–338.
- [Bra94] Brandt J.: Convergence and continuity criteria for discrete approximations of the continuous planar skeleton. CVGIP: Image Understanding 59, 1 (1994), 116–124.
- [CFG*05] Cheng S.-W., Funke S., Golin M., Kumar P., Poon S.-H., Ramos E.: Curve reconstruction from noisy samples. Computational Geometry 31, 1–2 (2005), 63–100.
- [dGCSAD11] de Goes F., Cohen-Steiner D., Alliez P., Desbrun M.: An optimal transport approach to robust reconstruction and simplification of 2D shapes. Computer Graphics Forum 30, 5 (2011), 1593–1602.
- [DK99] Dey T. K., Kumar P.: A simple provable algorithm for curve reconstruction. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (1999), SODA '99, pp. 893–894.
- [DMR00] Dey T. K., Mehlhorn K., Ramos E. A.: Curve reconstruction: Connecting dots with good reason. Computational Geometry 15, 4 (2000), 229–244.
- [Dun86] Dunham J. G.: Optimum uniform piecewise linear approximation of planar curves. IEEE Transactions on Pattern Analysis and Machine Intelligence 8, 1 (1986), 67–75.
- [DW01] Dey T. K., Wenger R.: Reconstructing curves with sharp corners. Computational Geometry 19, 2–3 (2001), 89–99.
- [DW02] Dey T. K., Wenger R.: Fast reconstruction of curves with sharp corners. International Journal of Computational Geometry & Applications 12, 05 (2002), 353–400.
10.1142/S0218195902000931 Google Scholar
- [EKS83] Edelsbrunner H., Kirkpatrick D., Seidel R.: On the shape of a set of points in the plane. IEEE Transactions on Information Theory 29, 4 (July1983), 551–559.
- [FEC02] Fabbri R., Estrozi L. F., Costa L. F.: On Voronoi diagrams and medial axes. Journal of Mathematical Imaging and Vision 17, (2002), 27–40.
- [FR01] Funke S., Ramos E. A.: Reconstructing a collection of curves with corners and endpoints. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (2001), SODA '01, pp. 344–353.
- [GDN04] Guru D., Dinesh R., Nagabhushan P.: Boundary based corner detection and localization using new ‘cornerity’ index: A robust approach. In Proceedings of the 1st Canadian Conference on Computer and Robot Vision, 2004 (May 2004), pp. 417–423.
10.1109/CCCRV.2004.1301477 Google Scholar
- [Gie99] Giesen J.: Curve reconstruction, the traveling salesman problem and Menger's theorem on length. In Proceedings of the 15th Annual Symposium on Computational Geometry (New York, NY, USA, 1999), SCG '99, ACM, pp. 207–216.
10.1145/304893.304973 Google Scholar
- [GMP07a] Giesen J., Miklos B., Pauly M.: Medial axis approximation of planar shapes from union of balls: A simpler and more robust algorithm. In proceedings of Canadian Conference of Computational Geometry (CCCG) (Ottawa, Canada, 2007), P. Bose (Ed.), pp. 105–108.
- [GMP07b] Giesen J., Miklos B., Pauly M.: Medial axis approximation of planar shapes from union of balls: A simpler and more robust algorithm. In Proceedings of the 19th Annual Canadian Conference on Computational Geometry, CCCG 2007, August 20–22, 2007, Carleton University, Ottawa, Canada (2007), pp. 105–108.
- [Gol99] Gold C.: Crust and anti-crust: A one-step boundary and skeleton extraction algorithm. In Proceedings of the 15th Annual Symposium on Computational Geometry (New York, NY, USA, 1999), SCG '99, ACM, pp. 189–196.
10.1145/304893.304971 Google Scholar
- [HAA94] Held A., Abe K., Arcelli C.: Towards a hierarchical contour description via dominant point detection. IEEE Transactions on Systems, Man and Cybernetics 24, 6 (June 1994), 942–949.
10.1109/21.293514 Google Scholar
- [HS99] Huang S.-C., Sun Y.-N.: Polygonal approximation using genetic algorithms. Pattern Recognition 32, 8 (1999), 1409–1420.
- [KD82] Kurozumi Y., Davis W. A.: Polygonal approximation by the minimax method. Computer Graphics and Image Processing 19, 3 (1982), 248–264.
10.1016/0146-664X(82)90011-9 Google Scholar
- [Lee00] Lee I.-K.: Curve reconstruction from unorganized points. Computer Aided Geometric Design 17, 2 (2000), 161–177.
- [LWS*15] Li P., Wang B., Sun F., Guo X., Zhang C., Wang W.: Q-mat: Computing medial axis transform by quadratic error minimization. ACM Transactions on Graphics 35, 1 (December 2015), 8:1–8:16.
- [Mas08] Masood A.: Optimized polygonal approximation by dominant point deletion. Pattern Recognition 41, 1 (2008), 227–239.
- [MBS16] M. Berger Andrea Tagliasacchi L. S. P. A. G. G. J. L. A. S., Silva C.: A survey of surface reconstruction from point clouds. Computer Graphics Forum'16 (extended journal version of the EG STAR) 36, (2016), 301–329.
- [MGP07] Miklos B., Giesen J., Pauly M.: Medial axis approximation from inner Voronoi balls: A demo of the Mesecina tool. In Proceedings of the 23rd Annual Symposium on Computational Geometry (New York, NY, USA, 2007), SCG '07, ACM, pp. 123–124.
10.1145/1247069.1247090 Google Scholar
- [MPM15] Methirumangalath S., Parakkat A. D., Muthuganapathy R.: A unified approach towards reconstruction of a planar point set. Computer Graphics 51 C (October 2015), 90–97.
10.1016/j.cag.2015.05.025 Google Scholar
- [MS03] Marji M., Siy P.: A new algorithm for dominant points detection and polygonization of digital curves. Pattern Recognition 36, 10 (2003), 2239–2251.
- [OM13] Ohrhallinger S., Mudur S. P.: An efficient algorithm for determining an aesthetic shape connecting unorganized 2D points. Computer Graphics Forum 32, 8 (2013), 72–88.
- [OMW16] Ohrhallinger S., Mitchell S., Wimmer M.: Curve reconstruction with many fewer samples. Computer Graphics Forum 35, 5 (2016), 167–176.
- [O'R98]
O'Rourke J.: Computational Geometry in C, 2nd ed. Cambridge University Press, New York, 1998.
10.1017/CBO9780511804120 Google Scholar
- [OW18]
Ohrhallinger S., Wimmer M.: Fitconnect: Connecting noisy 2D samples by fitted neighborhoods. Computer Graphics Forum, Early view (April 2018) https://doi.org/10.1111/cgf.13395.
10.1111/cgf.13395 Google Scholar
- [PM15a] Peethambaran J., Muthuganapathy R.: A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering. Computer-Aided Design 62 (2015), 164–175.
- [PM15b] Peethambaran J., Muthuganapathy R.: Reconstruction of water-tight surfaces through Delaunay sculpting. Computer-Aided Design 58, 0 (2015), 62–72.
- [PM16] Parakkat A. D., Muthuganapathy R.: Crawl through neighbors: A simple curve reconstruction algorithm. Computer Graphics Forum 35, 5 (2016), 177–186.
- [PMM18] Parakkat A. D., Methirumangalath S., Muthuganapathy R.: Peeling the longest: A simple generalized curve reconstruction algorithm. Computers & Graphics 74, (2018), 191–201.
- [PNK98] Pal N. R., Nandi S., Kundu M. K.: Self-crossover-A new genetic operator and its application to feature selection. International Journal Systems of Science 29, 2 (1998), 207–212.
- [PPM15] Peethambaran J., Parakkat A., Muthuganapathy R.: A Voronoi based labeling approach to curve reconstruction and medial axis approximation. In Pacific Graphics 2015 (October 2015), Eurographics Digital Library.
- [Ram72] Ramer U.: An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing 1, 3 (1972), 244–256.
10.1016/S0146-664X(72)80017-0 Google Scholar
- [RR93] Ray B. K., Ray K. S.: Determination of optimal polygon from digital curve using {L1} norm. Pattern Recognition 26, 4 (1993), 505–509.
- [Sat92] Sato Y.: Piecewise linear approximation of plane curves by perimeter optimization. Pattern Recognition 25, 12 (1992), 1535–1543.
- [TC89] Teh C.-H., Chin R.: On the detection of dominant points on digital curves. IEEE Transactions on Pattern Analysis and Machine Intelligence 11, 8 (August 1989), 859–872.
- [TDS*16] Tagliasacchi A., Delame T., Spagnuolo M., Amenta N., Telea A.: 3D skeletons: A state-of-the-art report. Computer Graphics Forum (Proceedings of Eurographics) 35, (2016), 573–597.
- [Wan14] Jun W., Zeyun Y., Weizhong Z., Mingqiang W., Changbai T., Ning D., Xi Z.: Robust reconstruction of 2D curves from scattered noisy point data. Computer-Aided Design 50, 0 (2014), 27–40.
- [Wu02] Wu W.-Y.: A dynamic method for dominant point detection. Graphical Models 64, 5 (2002), 304–315.
- [Wu03] Wu W.-Y.: An adaptive method for detecting dominant points. Pattern Recognition 36, 10 (2003), 2231–2237.
- [YIN99] YIN P.-Y.: Genetic algorithms for polygonal approximation of digital curves. International Journal of Pattern Recognition and Artificial Intelligence 13, 07 (1999), 1061–1082.
- [ZC18] Zhong Y., Chen F.: Computing medial axis transformations of 2D point clouds. Graphical Models 97, (2018), 50–63.
- [ZSC*14] Zhu Y., Sun F., Choi Y.-K., Jüttler B., Wang W.: Computing a compact spline representation of the medial axis transform of a 2D shape. Graphical Models 76, 5 (2014), 252–262.
