A Digital-Geometric Algorithm for Generating a Complete Spherical Surface in??sup class="a-plus-plus">3

详细信息    查看全文

• 作者：Sahadev Bera (18)
  Partha Bhowmick (19)
  Bhargab B. Bhattacharya (18)
  
• 关键词：Digital circle ; Digital sphere ; Digital geometry ; Geometry of numbers ; Number theory
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8321
• 期：1
• 页码：49-61
• 全文大小：1,216 KB
• 参考文献：1. Brimkov, V.E., Barneva, R.P., Brimkov, B., de Vieilleville, F.: Offset approach to defining 3D digital lines. In: Bebis, G., et al. (eds.) ISVC 2008, Part I. LNCS, vol.?5358, pp. 678-87. Springer, Heidelberg (2008) CrossRef
  2. Feschet, F., Reveillès, J.-P.: A Generic Approach for n-Dimensional Digital Lines. In: Kuba, A., Nyúl, L.G., Palágyi, K. (eds.) DGCI 2006. LNCS, vol.?4245, pp. 29-0. Springer, Heidelberg (2006) CrossRef
  3. Kenmochi, Y., Buzer, L., Sugimoto, A., Shimizu, I.: Digital planar surface segmentation using local geometric patterns. In: Coeurjolly, D., Sivignon, I., Tougne, L., Dupont, F. (eds.) DGCI 2008. LNCS, vol.?4992, pp. 322-33. Springer, Heidelberg (2008) CrossRef
  4. Woo, D.M., Han, S.S., Park, D.C., Nguyen, Q.D.: Extraction of 3D Line Segment Using Digital Elevation Data. In: Proceedings of the 2008 Congress on Image and Signal Processing, CISP 2008, vol.?2, pp. 734-38. IEEE Computer Society, Washington, DC (2008) CrossRef
  5. Chan, Y.T., Thomas, S.M.: Cramer-Rao lower bounds for estimation of a circular arc center and its radius. Graphical Models and Image Processing?57, 527-32 (1995) CrossRef
  6. Davies, E.R.: A hybrid sequential-parallel approach to accurate circle centre location. Pattern Recognition Letters?7, 279-90 (1988) CrossRef
  7. Doros, M.: On some properties of the generation of discrete circular arcs on a square grid. Computer Vision, Graphics, and Image Processing?28, 377-83 (1984) CrossRef
  8. Haralick, R.M.: A measure for circularity of digital figures. IEEE Trans. Sys., Man & Cybern.?4, 394-96 (1974) CrossRef
  9. Nagy, B.: Characterization of digital circles in triangular grid. Pattern Recognition Letters?25, 1231-242 (2004) CrossRef
  10. Pal, S., Bhowmick, P.: Determining digital circularity using integer intervals. Journal of Mathematical Imaging and Vision?42, 1-4 (2012) CrossRef
  11. Thomas, S.M., Chan, Y.T.: A simple approach for the estimation of circular arc center and its radius. Computer Vision, Graphics, and Image Processing?45, 362-70 (1989) CrossRef
  12. Yuen, P.C., Feng, G.C.: A novel method for parameter estimation of digital arc. Pattern Recognition Letters?17, 929-38 (1996) CrossRef
  13. Nakamura, A., Aizawa, K.: Digital circles. Computer Vision, Graphics, and Image Processing?26, 242-55 (1984) CrossRef
  14. Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann Series in Computer Graphics and Geometric Modeling. Morgan Kaufmann, San Francisco (2004)
  15. Klette, R., Rosenfeld, A.: Digital straightness: A review. Discrete Applied Mathematics?139, 197-30 (2004) CrossRef
  16. Mignosi, F.: On the number of factors of Sturmian words. Theoretical Computer Science?82, 71-4 (1991) CrossRef
  17. Brimkov, V.E., Barneva, R.P.: On the polyhedral complexity of the integer points in a hyperball. Theoretical Computer Science?406, 24-0 (2008) CrossRef
  18. Heath-Brown, D.R.: Lattice points in the sphere. Number theory in progress, vol.?II, pp. 883-92. Walter de Gruyter, Berlin (1999)
  19. Chamizo, F., Cristóbal, E., Ubis, A.: Visible lattice points in the sphere. Journal of Number Theory?126, 200-11 (2007) CrossRef
  20. Chamizo, F., Cristobal, E.: The sphere problem and the / L-functions. Acta Mathematica Hungarica?135, 97-15 (2012) CrossRef
  21. Fomenko, O.: Distribution of lattice points over the four-dimensional sphere. Journal of Mathematical Sciences?110, 3164-170 (2002) CrossRef
  22. Magyar, A.: On the distribution of lattice points on spheres and level surfaces of polynomials. Journal of Number Theory?122, 69-3 (2007) CrossRef
  23. Ewell, J.A.: Counting lattice points on spheres. The Mathematical Intelligencer?22, 51-3 (2000) CrossRef
  24. Tsang, K.M.: Counting lattice points in the sphere. Bulletin of the London Mathematical Society?32, 679-88 (2000) CrossRef
  25. Maehara, H.: On a sphere that passes through / n lattice points. European Journal of Combinatorics?31, 617-21 (2010) CrossRef
  26. Cappell, S.E., Shaneson, J.L.: Some Problems in Number Theory I: The Circle Problem (2007), http://arxiv.org/abs/math.NT/0702613
  27. Honsberger, R.: Circles, Squares, and Lattice Points. Mathematical Gems?I, 117-27 (1973)
  28. Kühleitner, M.: On lattice points in rational ellipsoids: An omega estimate for the error term. Abhandlungen Aus Dem Mathematischen Seminar Der Universitat Hamburg?70, 105-11 (2000) CrossRef
  29. Chamizo, F., Cristbal, E., Ubis, A.: Lattice points in rational ellipsoids. Journal of Mathematical Analysis and Applications?350, 283-89 (2009) CrossRef
  30. Chamizo, F.: Lattice points in bodies of revolution. Acta Arithmetica?85, 265-77 (1998)
  31. Andres, E., Jacob, M.: The discrete analytical hyperspheres. IEEE Trans. Visualization and Computer Graphics?3, 75-6 (1997) CrossRef
  32. Fiorio, C., Jamet, D., Toutant, J.L.: Discrete circles: an arithmetical approach with non-constant thickness. In: Latecki, L.J., Mount, D.M., Wu, A.Y. (eds.) Vision Geometry XIV, Electronic Imaging, San Jose (CA), USA. SPIE, vol.?6066, p. 60660C (2006)
  33. Fiorio, C., Toutant, J.-L.: Arithmetic discrete hyperspheres and separatingness. In: Kuba, A., Nyúl, L.G., Palágyi, K. (eds.) DGCI 2006. LNCS, vol.?4245, pp. 425-36. Springer, Heidelberg (2006) CrossRef
  34. Montani, C., Scopigno, R.: Spheres-to-voxels conversion. In: Glassner, A.S. (ed.) Graphics Gems, pp. 327-34. Academic Press Professional, Inc., San Diego (1990) CrossRef
  35. Stelldinger, P.: Image Digitization and its Influence on Shape Properties in Finite Dimensions. IOS Press (2007)
  36. Foley, J.D., van Dam, A., Feiner, S.K., Hughes, J.F.: Computer Graphics -Principles and Practice. Addison-Wesley, Reading (1993)
  37. Bera, S., Bhowmick, P., Stelldinger, P., Bhattacharya, B.B.: On covering a digital disc with concentric circles in ?sup class="a-plus-plus">2. Theoretical Computer Science?506, 1-6 (2013) CrossRef
  38. Bhowmick, P., Bhattacharya, B.B.: Number theoretic interpretation and construction of a digital circle. Discrete Applied Mathematics?156, 2381-399 (2008) CrossRef
  39. Kumar, G., Sharma, N., Bhowmick, P.: Wheel-throwing in digital space using number-theoretic approach. International Journal of Arts and Technology?4, 196-15 (2011) CrossRef
  
• 作者单位：Sahadev Bera (18)
  Partha Bhowmick (19)
  Bhargab B. Bhattacharya (18)
  
  18. Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India
  19. Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, India
  
• ISSN：1611-3349

文摘

We show that the construction of a digital sphere by circularly sweeping a digital semicircle (generatrix) around its diameter results in appearance of some holes (absentee voxels) in its spherical surface of revolution. This incompleteness calls for a proper characterization of the absentee voxels whose restoration in the surface of revolution can ensure the required completeness. In this paper, we present a characterization of the absentee voxels using certain techniques of digital geometry and show that their count varies quadratically with the radius of the semicircular generatrix. Next, we design an algorithm to fill up the absentee voxels so as to generate a spherical surface of revolution, which is complete and realistic from the viewpoint of visual perception. Test results have also been furnished to substantiate our theoretical findings. The proposed technique will find many potential applications in computer graphics and 3D imaging.