UN SCHÉMA DE SUBDIVISION DE COURBE D'INTERPOLATION BASÉ SUR UNE DÉRIVÉE PREMIÈRE DISCRÈTE (2023)

UN SCHÉMA DE SUBDIVISION DE COURBE D'INTERPOLATION BASÉ SUR UNE DÉRIVÉE PREMIÈRE DISCRÈTE

UN SCHÉMA DE SUBDIVISION INTERPOLANT BASÉ SUR LA PREMIÈRE DÉRIVÉE DISCRÈTE

ALBEIRO ESPINOSA BEDOYA
M.Sc., Université nationale de Colombie - Campus Medellín, Colombie,aespinos@unal.edu.co

TORRES SANCHEZ ALLEMAND
doctorat Université de Magdalena - Santa Marta, Colombie,gsanchez@unimagdalena.edu.co

JOHN WILLIAN BRANCHE BEDOYA
Ph.D., Université nationale de Colombie - Campus Medellín, Colombie,jwbranch@unal.edu.co

Reçu pour révision le 29 janvier^e, 2013, accepté le 26 mars^e, 2013, version finale 15 juin^e, 2013

ABSTRAIT:Cet article développe un nouveau schéma de quatre points pour la subdivision de la courbe d'interpolation basée sur la dérivée première discrète (DFDS), qui réduit l'apparition d'oscillations indésirables qui peuvent se former sur la courbe limite lorsque les points de contrôle ne suivent pas une paramétrisation uniforme. Nous avons utilisé un ensemble de 3000 courbes dont les points de contrôle ont été générés aléatoirement. Des courbes lisses ont été obtenues après sept étapes de subdivision en utilisant cinq schémas DFDS, Four-Point (4P), New quatre points (N4P), Tight quatre points (T4P) et le schéma géométriquement contrôlé (GC4P). La propriété de tortuosité a été évaluée sur chaque courbe lisse. Une analyse des distributions de fréquence de cette propriété à l'aide du test de Kruskal-Wallis révèle que le schéma DFDS a les valeurs les plus basses dans une plage proche.

MOTS CLÉS:Subdivision de courbe, interpolation de courbe, schéma de subdivision à quatre points.

RÉSUMÉ:Dans cet article, un nouveau schéma à quatre points pour la subdivision interpolante des courbes basée sur la première dérivée discrète (DFDS) est développé, ce qui réduit la formation d'oscillations indésirables pouvant survenir dans la courbe limite lorsque les points de contrôle n'obéissent pas. à un paramétrage uniforme. Un ensemble de 3000 courbes dont les points de contrôle ont été générés aléatoirement a été utilisé. Des courbes lisses ont été obtenues après sept étapes de subdivision en utilisant les schémas DFDS, Four-Point (4P), New Four-Point (N4P), Fitted Four-Point (T4P) et Geometrically Controlled Interpolating (GC4P). Sur chaque courbe lisse la propriété de tortuosité a été évaluée. Une analyse des distributions de fréquences obtenues pour cette propriété, à l'aide du test de Kruskal-Wallis, révèle que le schéma DFDS présente les valeurs de tortuosité les plus faibles dans une plage plus étroite.

MOTS-CLÉS:Subdivision de courbe, interpolation de courbe, schéma de subdivision à quatre points.

1. INTRODUCTION

Les courbes sont un outil puissant utilisé en ingénierie pour interpoler ou approximer un ensemble de points, dans le but de fournir des formes agréables [1]. Splines, NURBS et Subdivision sont les techniques les plus courantes.

La subdivision est devenue une technique populaire en infographie pour créer des courbes et des surfaces lisses. Actuellement, c'est la norme de l'industrie pour l'animation de personnages. Il remonte aux travaux de Chaikin [2], où les coins d'un polygone de contrôle sont itérativement coupés jusqu'à ce qu'une courbe lisse soit obtenue à la limite. Il s'agit d'un schéma approximatif aveccontinuité.

Les schémas à quatre points pour l'interpolation de la subdivision des courbes présentent deux défis fondamentaux : premièrement, obtenircontinuité sur toute la courbe, et la seconde est d'empêcher l'apparition d'oscillations indésirables. Plusieurs schémas ont été proposés à ce jour à partir des travaux de Dubuc [3], qui se caractérisent par avoir au pluscontinuité interpolant les points donnés. Des techniques récentes ont permis d'obtenir des courbes aveccontinuité, mais n'interpolez pas correctement les données d'origine.

Cet article se concentre sur les oscillations indésirables qui peuvent apparaître dans la courbe limite après un processus de subdivision par interpolation. Ce problème a reçu peu d'attention. Récemment, Hernandez et al. [4] ont proposé un nouveau schéma de subdivision interpolatoire basé sur la subdivision incenter qui évite les oscillations indésirables.

2. TRAVAUX ANTÉRIEURS

Pour interpoler les subdivisions, il est courant d'utiliser des schémas locaux géométriques, tels que des schémas à quatre points ou à six points. Des travaux antérieurs tels que Dubuc [3] et Deslauriers et Dubuc [5] proposent des schémas d'interpolation à quatre points, qui insèrent un nouveau point en ajustant un polynôme cubique aux points voisins sur des valeurs de paramètres uniformément espacées. L'idée derrière ce schéma est que si les points de contrôle d'origine tombent sur un polynôme défini, alors les points de contrôle du niveau suivant doivent également se trouver sur le même polynôme. Ce schéma à quatre points est exact pour les polynômes cubiques. Les équations 1 et 2 décrivent les nouveaux points de contrôle en fonction des anciens points de contrôle.

Une généralisation est présentée par Dyn et al. dans [6], qui utilise un schéma basé sur quatre points avec un paramètre de tension; la courbe limite présentecontinuité lorsque. Hechler et al. [7] a montré que laparamètre de tension génère des courbes limites, si et seulement si,, où. Une amélioration est présentée par Nira Dyn et al. dans [8], où un nouveau schéma à quatre points est développé avec le paramètre de tension, où la courbe limite présentecontinuité, et la courbe résultante est proche de l'interpolation.

La caractéristique des travaux antérieurs a été que le paramètre de tension est toujours constant. Marinov et al. [9] présente un nouveau schéma avec un paramètre de tension variable, adapté localement en fonction de la géométrie du polygone de contrôle. Becari et al. [10] propose un schéma de lotissement qui prévoitcontinuité avec un seul paramètre de tension qui peut être augmenté arbitrairement ou choisi de manière appropriée. De la même manière, Floater [11] dérive un algorithme pour exprimer les différences divisées d'ordre n - du schéma au niveaucomme une combinaison affine de différences divisées d'ordre n - ième au niveau j. Cet algorithme pourrait être un outil utile pour analyser la régularité du schéma, en particulier lorsque les points de la grille sont irrégulièrement espacés.

Dans les travaux de Dubuc [3], des valeurs de paramètres uniformes ont été supposées. Nira Dyn et al. [12] ont remplacé ces valeurs par des valeurs cordales et centripètes puisque la paramétrisation est mise à jour à chaque niveau de raffinement. En relation avec cela, Floater [13] a dérivé une propriété d'approximation de la subdivision de courbe d'interpolation à quatre points, basée sur un ajustement polynomial cubique local.

Une étape de subdivision peut être considérée comme une séquence d'étapes simples et très locales. Dodson et al. [14] propose de créer des familles de schémas en manipulant les étapes d'un pas de subdivision. Des applications dans le domaine des éléments finis ou de la construction de fonctions sont fournies par Zhijie [15] et Floater [16].

Il existe quelques travaux sur la subdivision en quatre points pour les schémas binaires et ternaires. Ceci est montré dans Siddiqui [17-18] et Hassan et al., Hed, Beccari et al. et Ko et al. [19-22].

3. SUBDIVISION DE LA COURBE

Une subdivision est un processus itératif pour obtenir une courbe ou une surface lisse à partir d'un maillage grossier. Une définition simple est donnée par Augsdorfer : "Étant donné une séquence de sommets, la subdivision est un processus par lequel, à chaque étape de raffinement, de nouveaux sommets sont insérés sous forme de combinaisons linéaires d'anciens sommets. La répétition du processus conduit finalement à une courbe limite lisse" [ 14].

Une subdivision peut être interpolée ou approchée, selon que la courbe limite passe ou non par les points de contrôle. L'esprit de subdivision a été présenté par Chaikin dans [2].

3.1. Subdivision interpolatoire à quatre points
Il s'agit d'un schéma d'interpolation présenté par Nira Dyn et al. dans [6] qui insère un nouveau sommetà chaque étape de subdivision, étant donné un paramètre de tensionsans supprimer les anciens sommets. Les règles topologiques sont simples ; pour chaque arête d'un polygone de contrôle, un nouveau sommet préservant les anciens sommets est inséré, comme indiqué dansFigure 1.

Soit les points de contrôle spécifiés paroù. Les règles géométriques sont spécifiées par les équations 3 et 4.

Ce régime produit unecourbe de continuité.

3.2. Nouvelle subdivision en quatre points
A la recherche d'un lotissement aveccontinuité, Nira Dyn et al. présente dans [8] plusieurs schémas proches de l'interpolation. Dans cet article, seuls les schémas de subdivision à quatre points seront référencés. L'un d'eux est le nouveau schéma de subdivision en quatre points, qui est basé sur l'interpolation des données par un polynôme cubique (Eq. 5) évalué suret.

Les règles topologiques expriment que pour chaque arête, deux nouveaux sommets sont créés, et les anciens n'existent plus à l'étape de subdivision suivante. Ceci est montré dansFigure 2.

Les règles géométriques s'expriment par :

3.3 Subdivision serrée en quatre points
Nira Dyn et al. [8] considérer la nouvelle subdivision en quatre points comme une perturbation du schéma de Chaikin introduit un paramètre de tension, produisant un schéma étendu. Pource nouveau schéma est nommé subdivision serrée en quatre points, qui estcontinu. Les règles topologiques sont les mêmes que pour la nouvelle subdivision à quatre points. Les règles géométriques sont exprimées par les équations 8 et 9.

3.4 Schéma d'interpolation à quatre points contrôlé géométriquement
Marinov et al. [9] propose plusieurs schémas de subdivision à quatre points basés sur le schéma classique à quatre points utilisant les équations 10 et 11, avec des paramètres de tension variablesdéfini sur l'éq. 12, qui est ajusté en fonction de la géométrie du polygone de contrôle.

Expérimentalement, Marinov a découvert que le schéma à quatre points produit des courbes visuellement agréables lorsque la règle d'insertion comprend des arêtes équidistantes. Les fonctions proposées sont :

4. SCHÉMA DFDS

Une spline cubiqueest une courbe paramétrique à partir d'un ensemble de points de contrôleaveccontinuité, décrite par Eq. 17. Une bonne description de la manière dont cette formule est obtenue est donnée dans [23].figure 3montre une Spline typique.

Cette définition de spline est approximative. Pour une définition d'interpolation il est nécessaire de redéfinir l'Eq. 17, en termes d'ensemble de pointsoù. Une sélection pourest montré dansFigure 4.

L'équation 17 peut être exprimée de manière simple en termes d'Eq. 18 comme :

Afin de développer notre méthode, une courbe d'interpolation lisseest supposé tel que :

Résoudre les équations 20 et 21 simultanément :

Les valeurs et sont obtenues. Le nouveau point est indiqué dansFigure 5.

5. TORTUOSITÉ

La tortuosité est une propriété intrinsèque de la courbe d'avoir des rebondissements.

Une définition formelle de la tortuosité n'a pas été trouvée dans la littérature examinée, mais plusieurs critères ont été appliqués pour la mesurer, tels que présentés par Kalitzeos et al. [24], qui sont repris dansTableau 1.

Les principales applications de cette propriété se trouvent dans les milieux poreux et l'ophtalmologie, comme on peut le voir dans Bullit et al. et Dougherty et al. [24-26]. Pour tenter de mesurer cette propriété, plusieurs métriques ont été développées. LeTableau 1décrit le plus important.

Les indices de tortuosité les plus récents sont basés sur la courbure, qui s'est montrée plus robuste dans le calcul de cette propriété. Ce travail présente une forme discrète considérant l'existence d'une distanceuniformément espacés entre les points de données du polygone, ce qui est cohérent avec le concept de subdivision. L'équation 24 présente la version continue de la définition de la courbure.

Pour le cas discret de la courbure,Figure 6montre un schéma voisin du point à évaluer.

Les équations 25, 26 et 27 présentent une approximation de la dérivée première aux points,etrespectivement.

En utilisant ces résultats et le même concept, il est possible de calculer la valeur de, qui s'exprime dans l'Eq. 28.

La prise de ces résultats dans l'équation 24 et la simplification conduisent à l'expression présentée dans l'équation 30.

6. RÉSULTATS

Dans cette section, nous comparons le schéma de subdivision proposé (DFDS) avec le schéma de subdivision à quatre points classique (4P), le nouveau schéma de subdivision à quatre points (N4P), le schéma de subdivision à quatre points serré (T4P) et le schéma de subdivision à contrôle géométrique. (GC4P), qui ont été décrits dans la section 2.Figure 7a, montre les points de contrôle pour le premier exemple.Figures 7-bpour7.fmontrent les courbes résultantes après sept étapes de subdivision.

Figure 8amontre les points de contrôle pour le deuxième exemple.Figures 8-bpour8.fmontrent les courbes résultantes après sept étapes de subdivision.

On peut voir qu'en présence de points de contrôle espacés de manière non homogène, des oscillations indésirables peuvent être présentes, comme le montreChiffres 8b,8cet8j.

Un ensemble de 3000 courbes a été généré aléatoirement, chacune ayant neuf points de contrôle. Les courbes ont été interpolées une à une avec chacune des méthodes d'interpolation. Dans tous les cas, il y avait sept étapes de subdivision. La courbure discrète a été évaluée à tous les points de chaque courbe, en prenant la mesure de la tortuosité comme sa valeur maximale.

Chiffres 9pour13montrent un histogramme pour chaque méthode de subdivision évaluée, la médiane est tracée sur chaque histogramme. Une analyse de normalité révèle qu'aucune des distributions n'est normale, l'analyse a été effectuée à l'aide d'un test non paramétrique, Kruskal-Wallis.

Une analyse comparative utilisant une boîte à moustaches entre ces distributions est présentée dansFigure 14, qui révèle que DFDS a une médiane de tortuosité inférieure à celle des autres méthodes de subdivision. Les valeurs des médianes sont indiquées dansTableau 2, où DFDS a une valeur inférieure.

Une analyse de Kruskal-Wallis montre que les données de tortuosité utilisant DFDS, 4-P, New 4-P, Tight 4-P et GC Subdivision proviennent de populations avec des médianes différentes. Étant donné que la valeur P du test F est inférieure à 0, 05, nous pouvons conclure que le nouveau schéma a une médiane de tortuosité inférieure à celle des autres méthodes, comme indiqué dansTableau 3.

6. CONCLUSION ET TRAVAUX FUTURS

Ce travail présente DFDS, un nouveau schéma de subdivision de courbe d'interpolation basé sur quatre points. L'avantage le plus important est la faible tendance à produire des artefacts, comme en témoigne l'analyse ANOVA, où elle est comparée aux autres méthodes. Un autre avantage est l'absence de poids ou de paramètres de tension pour l'interpolation. La forme de la courbe limite n'est fonction que de la géométrie voisine. Il est prévu d'avoircontinuité car elle est basée sur la dérivée première.

Les travaux futurs visent à étendre le nouveau schéma aux surfaces, à la subdivision des courbes inversées et à la subdivision des surfaces inversées.

LES RÉFÉRENCES

[1]Rojas, J. I., Fernandez-Sora, A., Serrano-Tierz, A. et Hernandez-Diaz, D. A., Revue historique : de l'ingénierie graphique à la conception technique., Dyna, 78, pp. 17-26, 2011. [Liens ]
[2]Chaikin, G. M., Un algorithme pour la génération de courbes à grande vitesse. Computer Graphics and Image Processing, 3, pp. 346 - 349, 1974. [Liens]
[3]Dubuc, S. Interpolation through an Iterative Scheme, Journal of Mathematical Analysis and Applications, 114, pp. 185 - 204, 1986. [Liens]
[4]Mederos, V. H., Sarlabous, J. E. et Ivrissimtzis, I., Generalization of the Incenter Subdivision Scheme. Modèles graphiques, 75, pp. 79 - 89, 2013. [Liens]
[5]Deslauriers G. et Dubuc S., Symmetric Iterative Interpolation Processes, Constructive Approximation, 5, pp. 49-68, 1989. [Liens]
[6]Dyn N., Levin D. et Gregory, J. A., A 4-Point Interpolatory Subdivision Scheme for Curve Design, Computer Aided Geometric Design, 4, pp. 257-268, 1987. [Liens]
[7]Hechler, J., Mobner, B. et Reif, U., C1 Continuité du schéma généralisé à quatre points, Algèbre linéaire et ses applications, 430, pp. 3019-3029, 2009. [Liens]
[8]Dyn, N., Floater, M.S. et Hormann K., A C2 Four-Point Subdivision Scheme with Fourth Order Accuracy and its Extensions, Analysis, 1, pp. 1-12, 2005. [Liens]
[9]Marinov, M., Dyn, N. et Levin, D., Geometrically Controlled 4-Point Interpolatory Schemes, In Advances in Multiresolution for Geometric Modelling, pp. 301-315, 2005. [Liens]
[dix]Beccari, C., Casciola, G. et Romani, L., A Non-Stationary Uniform Tension Controlled Interpolating 4-Point Scheme Reativity Conics, Computer Aided Geometric Design, 24, pp. 1 - 9, 2007. [Liens]
[11]Floater, M. S., Algorithm for Divided Differences of Dubuc-Deslauriers Subdivision, 2011. [Liens]
[12]Dyn, N., Floater, M. S. et Hormann, K., Subdivision de courbe à quatre points basée sur des paramétrisations chordales et centripètes itérées., Conception géométrique assistée par ordinateur, 26, pp. 279-286, 2009. [Liens]
[13]Floater, M. S., The Approximation Order of Four-Point Interpolatory Curve Subdivision., Journal of Computational and Applied Mathematics, 236, pp. 476-481, 2011. [Liens]
[14]Augsdorfer, U.H., Dodgson, N.A. et Sabin, M.A., Variations on the Four-Point Subdivision Scheme, Computer Aided Geometric Design, 27, pp. 78 - 95, 2010. [Liens]
[15]Zhijie, C., Modified Four-Point Scheme and its Application, Computer Aided Geometric Design, 15, pp. 251 - 260, 1998. [Liens]
[16]Floater, M.S., Notes on 4-Point Interpolatory Subdivision, 2009. [Liens]
[17]Siddiqi, S. S. et Rehan, K., Curve Subdivision Schemes for Geometric Modeling, International Journal of Computer Mathematics, 88, pp. 851-863, 2011. [Liens]
[18]Siddiqi, SS et Rehan, K. Schéma de subdivision binaire à quatre points amélioré et nouveau schéma de coupe d'angle, Informatique et mathématiques avec applications, 59, pp. 2647 - 2657, 2010. [Liens]
[19]Hassan, M. F, Ivrissimitzis, I. P., Dodgson, N. A. et Sabin, M. A., An Interpolating 4-Point C2 Ternary Stationary Subdivision Scheme, Computer Aided Geometric Design, 19, pp. 1 - 18, 2002. [Liens]
[20]Hed, Y., A New Interpolating Subdivision based on Approximating Subdivision Scheme, Journal of Information and Computational Science, 7, pp. 631-636, 2010. [Liens]
[21]Beccari, C., Casciola, G. et Romani, L., An Interpolating 4-Point C2 Ternary Non-Stationary Subdivision Scheme with Tension Control, Computer Aided Geometric Design, 24, pp. 210 - 219, 2007. [Liens]
[22]Ko, K. P., Lee, B. G. et Yoon, G. J., A Ternary 4-Point Approximating Subdivision Scheme, Applied Mathematics and Computation, 190, pp. 1563 - 1573, 2007. [Liens]
[23]Salomon, D., Curves and Surfaces for Computer Graphics, Springer-Verlag, New York Inc, 2006. [Liens]
[24]Kalitzeos, A., Lip, G.Y.H. et Heitmar, R., Retinal Vessel Tortuosity Measures and their Applications, Experimental Eye Research, 106, pp. 40-46, 2013. [Liens]
[25]Bullitt, E., Gerig, G., Pizer, S.M., Lin, W. et Aylward, S.R., Mesurer la tortuosité de la vascularisation intracérébrale à partir d'images MRA, Imagerie médicale, IEEE Transactions, 22, pp. 1163 -1171, 2003. [Liens]
[26]Dougherty, G., Johnson, M.J. et Wiers, M.D., Measurement of Retinal Vascular Tortuosity and its Application to Retinal Pathologies, Medical and Biological Engineering and Computing, 48, pp. 87-95, 2010. [Liens]