Passer à la navigation principale Passer à la recherche Passer au contenu principal

Two Plane-Probing Algorithms for the Computation of the Normal Vector to a Digital Plane

  • Université Savoie Mont Blanc
  • Institut national des sciences appliquées Lyon

Résultats de recherche: Contribution à un journal › Article publié dans une revue, révisé par les pairs › Revue par des pairs

13 Citations (Scopus)

Résumé

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 to classical recognition algorithm, this algorithm decides on-the-fly which points to test in order to output at the end the exact surface characteristics of the plane. We present two variants: the H-algorithm, which is purely local, and the R-algorithm which probes further along rays coming out from the local neighborhood tested by the H-algorithm. Both algorithms are shown to output the correct normal to the digital planes if the starting point is a lower leaning point. The worst-case time complexity is in O(ω) for the H-algorithm and O(ωlog ω) for the R-algorithm, where ω is the arithmetic thickness of the digital plane. In practice, the H-algorithm often outputs a reduced basis of the digital plane while the R-algorithm always returns a reduced basis. Both variants perform much better than the theoretical bound, with an average behavior close to O(log ω). Finally, we show 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. This paper is an extension of Lachaud et al. (Proceedings of 19th IAPR international conference discrete geometry for computer imagery (DGCI’2016), Nantes, France. Springer, Cham, 2016).

Langue originaleAnglais
Pages (de - à)23-39
Nombre de pages17
RevueJournal of Mathematical Imaging and Vision
Volume59
Numéro de publication1
Les DOIs
ÉtatPublié - 1 sept. 2017
Modification externeOui

Classification disciplinaire ASJC Scopus

  • Statistiques et probabilités
  • Modélisation et simulation
  • Physique de la matière condensée
  • Vision par ordinateur et reconnaissance de formes
  • Géométrie et topologie
  • Mathématiques appliquées

Empreinte digitale

Voici les principaux termes ou expressions associés à « Two Plane-Probing Algorithms for the Computation of the Normal Vector to a Digital Plane ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource