Régression parabolique non triviale

[sylvain231]

Bonjour,
J'ai en entrée un ensemble E de points (x,y) dans un repère orthonormé et le sommet de ma parabole S(x,y)
En sortie je veux une parabole qui passe obligatoirement par ce sommet et qui fitte au mieux les autres points de E. La difficulté est que la parabole peut avoir subie des rotations et translations aléatoires.
Si l'équation de la parabole est trop complexe je veux au pire une liste de points de cette parabole.
Ce que je veux dans tous les cas c'est les coefficients a, b et c de la parabole comme si elle n'avait pas été tournée.
J'ai conscience que c'est un problème très complexe et c'est pourquoi je pose la question ici.
Merci à vous
Bien cordialement

[leon1789]

Bonjour
comme on connait le sommet de la parabole recherchée, on peut opérer une translation (sur tous les points de E) pour ramener le sommet en (0,0).

L'équation cartésienne d'une parabole de sommet (0,0) peut se présenter comme ceci :
0 = a ( cos(t) * X + sin(t) * Y ) ^2 + sin(t) * X - cos(t) * Y
où t un angle de rotation à déterminer, et a un coefficient de "dilatation" de la parabole.

Les points donnés de E s'écrivent (après translation initiale) (x_i, y_i ) pour i = 1... n
Il reste à chercher t entre -Pi et Pi tel que toutes les valeurs
(- sin(t) *x_i + cos(t) * y_i ) / ( cos(t) * x_i + sin(t) * y_i ) ^2
soient aussi proches les unes des autres que possible.
Et cette valeur "presque commune" sera la constante a.

Vous avez combien de points dans l'ensemble E ?
On se donne un exemple pour voir ?

[leon1789]

"je veux une parabole qui passe obligatoirement par ce sommet "

J'ai compris que "ce sommet" doit être le sommet la parabole recherchée. Non seulement, la parabole passe par ce sommet (ce que vous dites), mais il est obligatoire que ce soit son sommet : ai-je bien compris ?

[sylvain231]

oui que S soit son sommet, désolé je me suis mal exprimé

[sylvain231]

OK merci beaucoup de vous intéresser à mon problème, j'aurai une centaine de points, difficile de vous donner un exemple de série de points, je pense qu'on peut tracer une parabole exemple tournée, en extraire des points, ajouter du bruit, puis dérouler notre algorithme pour retrouver la parabole initiale, vous avez Matlab ou Python pour les tests ?

[Ben314]

Salut,
L'idée que j'ai eu au départ, c'est fondamentalement la même chose que léon :
1) On translate pour que le somment soit (0,0).
2) On considère un angle theta fixé, on écrit (formellement) les coordonnées des images des points après rotation d'angle theta.
3) On applique (formellement) la méthode des moindre carrés pour trouver la valeur de donnant la parabole qui approxime au mieux les points et on regarde combien vaut la somme des carrés des écarts.
4) On obtient une fonction de l'angle theta (*) que l'on peut tenter de minimiser (sans doute pas de façon formelle, mais avec du calcul numérique, ça doit se faire)

(*) Une fraction rationnelle en cos(theta) et sin(théta) dont les coefficients sont des espérance de X^iY^j pour certains entiers i,j et donc qui sont des constantes calculables.

[sylvain231]

désolé mais je me sens incapable de coder cela pourriez-vous m'aider SVP (en pseudo-code, Python, Matlab, C++ ou autre) ? Merci beaucoup

[sylvain231]

est-ce que ce code est bon :

Code: Tout sélectionner

#include <opencv2/opencv.hpp>
#include <vector>
#include <cmath>
#include <iostream>
#include <limits>

struct Point2D {
    double x;
    double y;
};

std::vector<Point2D> translatePoints(const std::vector<Point2D>& points, const Point2D& sommet) {
    std::vector<Point2D> translatedPoints;
    for (const auto& point : points) {
        translatedPoints.push_back({point.x - sommet.x, point.y - sommet.y});
    }
    return translatedPoints;
}

std::vector<Point2D> rotatePoints(const std::vector<Point2D>& points, double theta) {
    std::vector<Point2D> rotatedPoints;
    for (const auto& point : points) {
        rotatedPoints.push_back({point.x * cos(theta) - point.y * sin(theta), point.x * sin(theta) + point.y * cos(theta)});
    }
    return rotatedPoints;
}

//renvoie a
float fitParabola(const std::vector<Point2D>& points, double& sumOfSquaredErrors) {
    int n = points.size();
    cv::Mat1f X(n, 2);
    cv::Mat1f Y(n, 1);

    for (int i = 0; i < n; i++) {
        float x = points[i].x;
        X(i, 0) = x*x;
        X(i, 1) = 1;
        Y(i) = points[i].y;
    }

    cv::Mat1f ab = (X.t() * X).inv() * X.t() * Y;

    sumOfSquaredErrors = 0;
    for (int i = 0; i < n; i++) {
        float error = Y(i) - (ab(0) * X(i, 0) + ab(1));
        sumOfSquaredErrors += error * error;
    }

    return ab(0);
}

int main() {
    std::vector<Point2D> points = {/* vos points ici */};
    Point2D sommet = {/* sommet ici */};
   
    std::vector<Point2D> translatedPoints = translatePoints(points, sommet);
   
    double bestTheta = 0;
    double minSumOfSquaredErrors = std::numeric_limits<double>::infinity();
    float bestCoefficient;
   
    for (int i = 0; i < 360; ++i) {
        double theta = i * CV_PI / 180.0; // Convertir en radians
        std::vector<Point2D> rotatedPoints = rotatePoints(translatedPoints, theta);
       
        double sumOfSquaredErrors;
        float coefficient = fitParabola(rotatedPoints, sumOfSquaredErrors);
       
        if (sumOfSquaredErrors < minSumOfSquaredErrors) {
            minSumOfSquaredErrors = sumOfSquaredErrors;
            bestCoefficient = coefficient;
            bestTheta = theta;
        }
    }
   
    std::cout << "Meilleur angle theta (en radians) : " << bestTheta << std::endl;
    std::cout << "Le coefficient de la parabole est : " << bestCoefficient << std::endl;

    return 0;
}

en C++ avec OpenCV ?

[lyceen95]

Ce que je veux dans tous les cas c'est les coefficients a, b et c de la parabole comme si elle n'avait pas été tournée.

Cette phrase là me pose problème.

Une parabole est de la forme y=ax²+bx+c, si et seulement si son axe est parallèle à l'axe des y.

Donc soit tu envisages des changements de repères, puis dans tel nouveau repère, tu cherches les a,b,c en question.
Soit tu envisages autre chose.
Mais dans ce cas, ce qui définit ta parabole, c'est une équation ( donc les fameux a,b,c) plus une direction du repère. Tu cherches 4 variables, et non 3.

On peut voir le problème sous forme géométrique. Une parabole, c'est l'ensemble des points équidistants d'un point F(le Foyer) et d'une droite D(la Directrice). Une parabole est donc définie par les coordonnées de ce Foyer (xF et yF) , et par l'équation de la droite (2 réels)

Ce qui confirme que tu cherches 4 variables, et non 3.

[sylvain231]

en effet il y a un quatrième paramètre qui est l'angle de rotation, b et c ne sont valables que pour une parabole droite, mais comme on a fait une translation du sommet en (0,0), b et c on s'en fiche. Si j'ai bien compris une parabole tournée centrée en (0,0) a pour équation :
0 = a ( cos(t) * X + sin(t) * Y ) ^2 + sin(t) * X - cos(t) * Y où t est l'angle de rotation c'est bien cela ?

[sylvain231]

Ben314 >> tu cherches une parabole d'équation y = ax^2 il ne faut pas plutôt prendre y = ax^2 +b x ?

[Ben314]

En rentrant un peu plus dans les détails :
Si et sont les listes de coordonnées après avoir translaté pour que le centre de la parabole doive être en (0,0) alors :
Les coordonnées après rotation sont et où et .

Le qui minimise est qui donne
dont on cherche le minimum (en )
Avec, par exemple,

[Ben314]

Ben314 >> tu cherches une parabole d'équation y = ax^2 il ne faut pas plutôt prendre y = ax^2 +b x ?

Si tu veut effectivement que le sommet soit en (0,0), c'est bien uniquement y = ax^2 qu'il faut prendre.

[sylvain231]

oui mais b est important aussi non ? je ne comprends pas pourquoi on l'élimine

[sylvain231]

ah je viens de comprendre c'est que si b est non nul c'est qu'il y a un décalage horizontal de la parabole

[leon1789]

Lycéen95 :
"Ce qui confirme que tu cherches 4 variables, et non 3."

Une parabole générale demande 4 variables, ok. Mais ici, le sommet est imposé, ce qui impose 2 contraintes supplémentaires sur les coefficients, donc il reste donc 4-2 = 2 coefficients à déterminer pour ce problème.

[leon1789]

Sylvain231 :
une parabole tournée centrée en (0,0) a pour équation : "0 = a ( cos(t) * X + sin(t) * Y ) ^2 + sin(t) * X - cos(t) * Y où t est l'angle de rotation c'est bien cela ?"

oui, exactement, c'est l'équation d'une parabole y =a. x^2 tournée d'un angle t.

[sylvain231]

autre question comment je trace ma fonction 0 = a (cos(theta)*(X-sommet.X)+sin(theta)*(Y-sommet.Y))^2 + sin(theta)*(X-sommet.X)-cos(theta)*(Y-sommet.Y) car ce n'est pas simple à première vue ?

[leon1789]

"Si tu veux effectivement que le sommet soit en (0,0), c'est bien uniquement y = ax^2 qu'il faut prendre."

oui, est après une rotation d'angle t, on tombe sur l'équation ci-dessus (j'ai eu la même démarche que Ben314).



PS. C'est marrant tous ces pseudos qui terminent par des nombres ...

[leon1789]

sylvain231 :
"comment je trace ma fonction 0 = ..."

pour un X donné ,cela donne une équation de degré 2 (ou 1 exceptionnellement) en Y .
pour un Y donné ,cela donne une équation de degré 2 (ou 1 exceptionnellement) en X .