thumb|Régression circulaire : méthode linéaire de Coope.
thumb|Régression sur des points décrivant un arc de cercle de centre (1 ; 1) et de rayon 4.
La régression circulaire consiste à trouver le « meilleur cercle » décrivant un ensemble de points, dans le sens où la position du cercle minimise une fonction de résidu, mesurant l'écart entre le cercle et l'ensemble des points, et que l'on cherche à minimiser cette fonction ; on utilise fréquemment la méthode des moindres carrés, mais d'autres solutions sont possibles. C'est un cas de régression géométrique, c'est-à-dire que la distance point-courbe modèle à laquelle on s'intéresse est une distance perpendiculaire à la courbe — méthode des moindres carrés totaux (TLS pour total least squares, ou FLS pour full least squares) —, et non une distance verticale (en y) ; plus particulièrement de régression elliptique.
C'est un problème de régression géométrique non linéaire. Cependant, un choix astucieux de la variable expliquée, et donc de la fonction d'erreur, permet de se ramener à un problème linéaire.
Historique
Les premières applications ont concerné l'archéologie, avec le problème des cercles de mégalithes, et la géodésie.
Le sujet a pris de l'importance avec la technologie des micro-ondes (en particulier dans les circuits passif hyperfréquence pour les télécommunications et les radars), qui nécessite de mesurer une charge glissante pour déterminer l'impédance. La régression circulaire est également utilisée pour la mesure des défauts géométriques de pièces fabriquées (par exemple avec une machine à mesurer tridimensionnelle), en particulier les défauts de circularité, de cylindricité, de battement.
Exposé du problème
Soient Ai(xi, yi) les n points à décrire, C(xc, yc) le centre du cercle et r son rayon ; soit O le centre du repère. L'équation cartésienne du cercle est
La distance entre un point expérimental Ai et le cercle s'écrit : . Le but de la régression est de minimiser l'écart quadratique total (moindres carrés totaux, MCT), ou facteur de fiabilité : . La fonction d'écart quadratique total S est donc une fonction non linéaire de trois variables qui caractérisent le cercle : xc, yc et r. Il faut donc au moins trois points pour effectuer la régression.
On peut aussi écrire l'équation cartésienne sous la forme :
avec
ou sous forme matricielle :
où tM désigne la matrice transposée de la matrice M.
On peut étendre cette écriture à des cas à m dimensions (m ≥ 2), en posant ai les vecteurs expérimentaux et c le vecteur position du centre : . Dans le cas m = 2, le modèle est un cercle ; pour m = 3, il s'agit d'une sphère, et pour m ≥ 4, il s'agit d'une hypersphère. La régression doit déterminer m + 1 variables (les m coordonnées du centre, et le rayon), il faut donc au moins m + 1 points. On a alors : l'équation cartésienne de l'hypersphère :
la distance du point i au cercle :
l'écart quadratique total : .
L'écriture matricielle reste alors
où ||…|| désigne la norme 2 (norme euclidienne).
Régression non linéaire
Méthode des moindres carrés totaux
thumb|300px|Cas « pathologique » pour la méthode des moindres carrés totaux : un des points est proche du centre, ce qui rend la convergence difficile et donne un cercle décalé.Haut : points expérimentaux et modèle.Bas : évolution de l'écart quadratique.
Comme pour toutes les régressions, on écrit que le minimum de S implique une nullité des dérivées partielles, soit à deux dimensions :
On peut appliquer une méthode de régression non linéaire sur la fonction SMCT, une méthode itérative comme une méthode de Gauss-Newton ou bien de Levenberg-Marquardt.
Gruntz ; voir aussi le code Matlab a proposé de réduire le nombre de variables de 1 en appliquant la démarche suivante. Le rayon peut se calculer simplement en fonction de la position du centre C et des points Ai, en calculant la moyenne des distances CA : . Ainsi, si l'on peut estimer les coordonnées de C, on peut en déduire une estimation de r. On peut donc éliminer la variable r, l'expression de l'écart quadratique devient . On se retrouve donc à minimiser S : . Le vecteur gradient s'écrit
En notation matricielle, cela donne :
On applique ensuite une méthode itérative sur S*. Cependant, les méthodes itératives sont très sensibles aux points aberrants, ce qui a un effet « esthétique » important : le cercle apparaît notablement décalé par rapport aux points « bien placés ». Par ailleurs, le gradient tend vers l'infini si un des points Ai est proche du centre (S* n'est pas différentiable en C), ce qui peut arriver en analyse d'image par exemple.
Méthode géométrique de la moyenne des intersections
thumb|La médiatrice d'une corde passe par le centre du cercle.
En reprenant l'idée de Gruntz, on peut utiliser pour cela les propriétés géométriques du cercle, en particulier le fait que les médiatrices de deux cordes d'un même cercle passe par le centre de ce cercle..
On peut donc prendre les points trois par trois, faire des triplets {Ai, Aj, Ak} (i ≠ j ≠ k), et déterminer l'intersection Cijk des médiatrices de [AiAj] et [AjAk], — à condition que les trois points ne soient pas alignés, puis faire la moyenne des coordonnées des Cijk. Le nombre de triplets est égal au coefficient binomial : . L'avantage de cette méthode est que le système d'équations que l'on obtient a une solution analytique exacte. En notant :
on a alors
. Cette méthode revient à déterminer le cercle passant exactement par chacun des triplets (qui existe pour chaque triplet de points non alignés, c'est alors le cercle circonscrit au triangle formé par le triplet), et à faire la moyenne des positions des centres.
Le principal inconvénient de cette méthode est qu'elle est très sensible à la dispersion : lorsque l'on considère des triplets de points proches, un petit déplacement d'un point produit une grande variation de l'orientation de la médiatrice ; si des points sont quasiment alignés, le centre estimé va se retrouver très loin, ce qui va avoir un poids énorme dans la moyenne ; la méthode ne consiste pas à minimiser une quantité, et la moyenne n'est pas une quantité « robuste » d'un point de vue des statistiques. On peut réduire ces inconvénients : en éliminant les triplets alignés ou presque alignés : pour chaque triplet (ijk), on calcule l'aire du triangle formé Δijk = (xk – xj)(yj – yi) – (xj – xi)(yk – yj), et l'on rejette les candidats dont |Δijk| est trop petit ; en utilisant la médiane plutôt que la moyenne pour estimer la position du centre. Cette méthode peut être utilisée pour initialiser une méthode itérative.
Méthode des moindres carrés réduits
Dans la continuité de l'idée développée supra, on peut prendre pour estimation du centre du cercle le point qui minimise la distance aux bissectrices. L'écart (moindres carrés réduits, MCR) vaut ainsi . La régression sur cet écart n'a pas de solution analytique, mais on peut appliquer une méthode de résolution numérique, itérative.
Le principal inconvénient de cette méthode est son instabilité lorsque deux points expérimentaux sont proches : le dénominateur (xj – xi)2 + (yj – yi)2 tend alors vers zéro.
Régression linéaire
Méthode des moindres carrés modifiés
Pour résoudre le problème de l'instabilité de la méthode précédente, on peut modifier l'écart en enlevant le dénominateur (moindres carrés modifiés, MCM) :
La différenciation mène à un système d'équations linéaires, dont la solution est :
avec
Cette solution s'exprime plus simplement avec les variances et covariances :
avec
.
Méthode de Kåsa et Coope
Problème plan
En posant l'équation cartésienne du cercle sous la forme :
soit
avec
On peut donc déterminer (e1, e2, e0) par régression linéaire multiple, puis relier ces paramètres aux caractéristiques géométriques du cercle.
Cette approche, qui n'utilise pas les moindres carrés totaux, mais permet d'avoir un problème linéaire, a été proposée par Kåsa.
Pour calculer l'écart, il utilise la différence des carrés :
soit . On retrouve là la forme de l'équation cartésienne proposée par Gander et :
en imposant α = 1 ; ceux-ci parlent de « minimisation de la distance algébrique ». C'est Coope qui a indiqué la démarche de résolution avec un modèle multilinéaire. Les paramètres du cercles sont alors :
. Le centre est identique à celui trouvé par la méthode précédente (moindres carrés modifiés), mais le rayon est différent (supérieur ou égal) :
Problème à m dimensions
On peut étendre aisément cette analyse à des dimensions plus élevées. L'écart peut encore s'écrire sous forme vectorielle . L'écriture matricielle devient : . L'expression de l'erreur peut se simplifier en utilisant des matrices de dimension m + 1 : on pose
et
ce que l'on écrit parfois et On a alors . .
On peut alors définir la matrice B dont les colonnes sont les matrices colonnes :
et la matrice d
La fonction d'écart s'écrit alors . Le problème est alors un problème de régression linéaire sur la variable explicative c*.
La solution (c, r) s'obtient alors en faisant le changement de variable inverse : (1 ≤ i ≤ m) ; .
Critique et interprétation géométrique
La première question qui se pose est la signification de la fonction d'écart S utilisée. On remarque que le résidu peut se factoriser de la manière suivante : . Le premier facteur est la fonction résidu classique, correspondant à la distance entre le point expérimental et le cercle modèle. Le second facteur est la distance entre le point expérimental et le point le plus éloigné du cercle modèle. Géométriquement, la démarche consiste donc à minimiser la somme du produit de ces deux distances.
Ce faisant, on n'est plus dans une démarche de moindres carrés totaux, ce qui peut poser problème, en particulier pour la métrologie par coordonnées. Si l'on désire travailler avec des moindres carrés totaux, on peut utiliser la méthode linéaire pour avoir une première estimation de la position de C et du rayon r. Puis, on utilise la méthode non linéaire ; le fait de partir d'une solution proche de la solution finale assure une convergence rapide de l'algorithme itératif (Gauss-Newton ou Levenberg-Marquardt).
Méthode de la distance algébrique
thumb | Régression circulaire par la méthode de la distance algébrique, les données étant bien réparties autour du centre.
thumb | Régression circulaire par la méthode de la distance algébrique, les données ne décrivant qu'un arc de cercle.
L'équation cartésienne du cercle est : α(x2 + y2) + β1x + β2y + γ = 0 On peut définir la distance algébrique : F(x, y) = α(x2 + y2) + β1x + β2y + γ Pour un point expérimental i légèrement à l'écart du cercle, on aura un résidu F(xi, yi) = εi, et l'on peut chercher à minimiser la somme des carrés des résidus. Sous forme matricielle, on définit les matrices
et l'on cherche donc à minimiser . Gander et proposent d'effectuer une décomposition en valeurs singulières de B : B = USV où U est une matrice unitaire n×n, V une matrice unitaire 4×4 et S est une matrice n×4 qui contient les valeurs singulières de B. On a alors α = V14 ; β1 = V24 ; β2 = V34 ; γ = V44 ; et toujours
On constate que le résultat n'est satisfaisant que si les données décrivent un « cercle complet ». En revanche, si les points ne correspondent qu'à un arc de cercle, le résultat n'est pas satisfaisant, ni d'un point de vue des moindres carrés, ni d'un point de vue esthétique.
Cette méthode simple et rapide peut par contre servir à initialiser le modèle pour une recherche itérative.
Bilan