Récupérer la pente d'une ligne numérisée

Y a-t-il eu des travaux pour récupérer la pente d'un segment de ligne de sa numérisation? On ne peut pas le faire avec une précision parfaite, bien sûr; ce que l'on veut, c'est une méthode pour dériver d'une ligne numérisée un intervalle de pentes possibles.

(La notion de ligne numérisée que j'utilise est celle de Rosenfeld: l'ensemble des paires où i s'étend sur les entiers (ou un bloc d'entiers consécutifs) et n i n t ( x ) représente le nombre entier le plus proche de x (si x = k + une / 2 , on prend n i n t ( x ) = k )).$(i,nint(ai+b))$$i$$nint(x)$$x$$x=k+1/2$$nint(x)=k$

J'ai fait un peu de travail sur ce sujet par moi-même (voir http://jamespropp.org/SeeSlope.nb ) mais je n'ai aucune formation formelle en géométrie computationnelle, donc je soupçonne que je réinvente la roue, car la question semble telle un élémentaire.

En fait, je sais que la méthode de régression linéaire pour estimer la pente est dans la littérature, mais je n'ai pu trouver mon résultat nulle part. (Ce résultat dit que si l'on choisit a et b uniformément au hasard dans [ 0 , 1 ] , alors la différence entre la pente a de la droite y = a x + b et la pente ¯ a de la droite de régression se rapprochant des n points ( i , $O(1/n^{1.5})$$a$$b$$[0,1]$$a$$y=ax+b$$\overline{a}$$n$ ( 1 ≤ i ≤ n ) a l'écart type O ( 1 / n 1,5 ) .)$(i,nint(ai+b))$$1 \leq i \leq n$$O(1/n^{1.5})$

Toute piste ou référence à la littérature pertinente sera grandement appréciée.

Jim Propp ([email protected])

Voir Génération aléatoire de mots sturmiens finis par Berstel et Pocchiola pour une preuve que la région réalisable de votre LP n'a que trois ou quatre côtés, ainsi qu'un algorithme simple pour trouver le polygone donné en pente et en interception. (Ils traitent de la reconnaissance des mots sturmiens, mais les problèmes sont fortement liés.)

Ils donnent également une énumération explicite des polygones, il peut donc être possible d'énumérer les zones des polygones et les plages des pentes, afin que vous puissiez obtenir la valeur attendue de la plage des pentes (ainsi que les moments supérieurs). ) comme somme explicite.

L'approche de la géométrie de calcul remplacerait chaque pixel (i, j) par un segment vertical (i, j + [- 1 / 2,1 / 2]), prendrait les coques convexes des ensembles supérieur et inférieur de points d'extrémité et calculerait le commun intérieur tangentes - elles délimitent la gamme de pentes qui produisent cette ligne numérique. Ceci est juste l'interprétation géométrique du programme linéaire que vous mentionnez dans vos diapositives. O (n) le temps suffit pour le LP de Meggiddo, ou pour les coques et tangentes de Graham-Yao.

Qu'en est-il de la méthode de transformation Hough standard utilisée pour la détection de ligne dans le traitement d'image: http://en.wikipedia.org/wiki/Hough_transform ?

Si vous souhaitez gagner en vitesse, vous pouvez utiliser la version aléatoire de HT.

• Je ne connais aucun travail en cg (ou tout autre groupe d'ailleurs) sur la dérivation de la pente à partir de l'ensemble de points discrets, mais c'est plus un reflet de mon manque de connaissances.

• $\Delta y$$\Delta x$$x$$y$$x$$y$