Computation of the Normal Vector to a Digital Plane by Sampling Significant Points

详细信息    查看全文

• 关键词：Digital geometry ; Digital plane ; Recognition ; Normal vector estimation ; Lattice reduction
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9647
• 期：1
• 页码：194-205
• 全文大小：1,892 KB
• 参考文献：1.Charrier, E., Buzer, L.: An efficient and quasi linear worst-case time algorithm for digital plane recognition. In: Coeurjolly, D., Sivignon, I., Tougne, L., Dupont, F. (eds.) DGCI 2008. LNCS, vol. 4992, pp. 346–357. Springer, Heidelberg (2008)CrossRef
  2.Charrier, E., Lachaud, J.-O.: Maximal planes and multiscale tangential cover of 3D digital objects. In: Aggarwal, J.K., Barneva, R.P., Brimkov, V.E., Koroutchev, K.N., Korutcheva, E.R. (eds.) IWCIA 2011. LNCS, vol. 6636, pp. 132–143. Springer, Heidelberg (2011)CrossRef
  3.de Vieilleville, F., Lachaud, J.-O., Feschet, F.: Maximal digital straight segments and convergence of discrete geometric estimators. J. Math. Image Vis. 27(2), 471–502 (2007)
  4.Doerksen-Reiter, H., Debled-Rennesson, I.: Convex and concave parts of digital curves. In: Klette, R., Kozera, R., Noakes, L., Weickert, J. (eds.) Geometric Properties for Incomplete Data. Computational Imaging and Vision, vol. 31, pp. 145–160. Springer, The Netherlands (2006)CrossRef
  5.Gérard, Y., Debled-Rennesson, I., Zimmermann, P.: An elementary digital plane recognition algorithm. Discrete Appl. Math. 151(1), 169–183 (2005)MathSciNet CrossRef MATH
  6.Kim, C.E., Stojmenović, I.: On the recognition of digital planes in three-dimensional space. Pattern Recogn. Lett. 12(11), 665–669 (1991)CrossRef
  7.Lachaud, J.-O., Provençal, X., Roussillon, T.: An output-sensitive algorithm to compute the normal vector of a digital plane. Theoretical Computer Science (2015, to appear)
  8.Veelaert, P.: Digital planarity of rectangular surface segments. IEEE Trans. Pattern Anal. Mach. Intell. 16(6), 647–652 (1994)CrossRef
  
• 作者单位：Jacques-Olivier Lachaud (16)
  Xavier Provençal (16)
  Tristan Roussillon (17)
  
  16. Université Savoie Mont Blanc, LAMA, UMR5127, 73376, Le Bourget-du-Lac, France
  17. Université de Lyon, CNRS INSA-Lyon, LIRIS, UMR5205, 69622, Villeurbanne, France
  
• 丛书名：Discrete Geometry for Computer Imagery
• ISBN：978-3-319-32360-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Digital planes are sets of integer points located between two parallel planes. We present a new algorithm that computes the normal vector of a digital plane given only a predicate “is a point x in the digital plane or not”. In opposition with the algorithm presented in [7], the algorithm is fully local and does not explore the plane. Furthermore its worst-case complexity bound is \(O(\omega )\), where \(\omega \) is the arithmetic thickness of the digital plane. Its only restriction is that the algorithm must start just below a Bezout point of the plane in order to return the exact normal vector. In practice, our algorithm performs much better than the theoretical bound, with an average behavior close to \(O(\log \omega )\). We show further how this algorithm can be used to analyze the geometry of arbitrary digital surfaces, by computing normals and identifying convex, concave or saddle parts of the surface.