Wiederherstellen der Steigung einer digitalisierten Linie

Wurde daran gearbeitet, die Steigung eines Liniensegments nach seiner Digitalisierung wiederherzustellen? Das kann man natürlich nicht mit perfekter Genauigkeit machen; Was man will, ist eine Methode, aus einer digitalisierten Linie ein Intervall möglicher Steigungen abzuleiten.

(Der Begriff einer digitalisierten Linie, den ich verwende, ist Rosenfelds: die Menge von Paaren wobei i über die ganzen Zahlen (oder einen Block aufeinanderfolgender ganzer Zahlen) und n i n reicht t ( x ) bezeichnet die ganze Zahl am nächsten zu x (wenn x = k + 1 / 2 , nehmen wir n i n t ( x ) = k )).$(i,nint(ai+b))$$i$$nint(x)$$x$$x=k+1/2$$nint(x)=k$

Ich habe selbst daran gearbeitet (siehe http://jamespropp.org/SeeSlope.nb ), aber ich habe keinen formalen Hintergrund in der Computergeometrie, daher vermute ich, dass ich das Rad möglicherweise neu erfinde, da die Frage so aussieht eine grundlegende.

Tatsächlich weiß ich, dass die lineare Regressionsmethode zur Schätzung der Steigung in der Literatur enthalten ist, aber ich konnte mein -Ergebnis nirgendwo finden. (Dieses Ergebnis besagt, dass, wenn man a und b in [ 0 , 1 ] gleichmäßig zufällig wählt , die Differenz zwischen der Steigung a der Linie y = a x + b und der Steigung a der Regressionslinie, die sich den n Punkten annähert, ist ( i , $O(1/n^{1.5})$$a$$b$$[0,1]$$a$$y=ax+b$$\overline{a}$$n$ ( 1 ≤ i ≤ n ) hat die Standardabweichung O ( 1 / n 1,5 ) .)$(i,nint(ai+b))$$1 \leq i \leq n$$O(1/n^{1.5})$

Hinweise oder Hinweise auf relevante Literatur werden sehr geschätzt.

Jim Propp ([email protected])

Unter Zufällige Erzeugung endlicher Sturm-Wörter von Berstel und Pocchiola finden Sie einen Beweis dafür, dass der realisierbare Bereich Ihrer LP nur drei oder vier Seiten hat, sowie einen einfachen Algorithmus zum Ermitteln des Polygons bei gegebener Steigung und Achsenabschnitt. (Sie haben es mit dem Erkennen von Sturm-Wörtern zu tun, aber die Probleme hängen stark zusammen.)

Sie geben auch eine explizite Aufzählung der Polygone an, sodass möglicherweise die Bereiche der Polygone und die Bereiche der Steigungen aufgelistet werden können, sodass Sie möglicherweise den erwarteten Wert des Bereichs der Steigungen (sowie höhere Momente) erhalten können ) als explizite Summe.

Der Ansatz der rechnerischen Geometrie würde jedes Pixel (i, j) durch ein vertikales Segment (i, j + [- 1 / 2,1 / 2]) ersetzen, die konvexen Hüllen des oberen und unteren Satzes von Endpunkten nehmen und die innere Gemeinsamkeit berechnen Tangenten - diese begrenzen den Bereich der Steigungen, die diese digitale Linie erzeugen. Dies ist nur die geometrische Interpretation des linearen Programms, das Sie in Ihren Folien erwähnen. O (n) Zeit reicht für die LP von Meggiddo oder für die Rümpfe und Tangenten von Graham-Yao.

Was ist mit der Standard-Hough-Transformationsmethode, die zur Linienerkennung in der Bildverarbeitung verwendet wird: http://en.wikipedia.org/wiki/Hough_transform ?

Wenn Sie etwas Geschwindigkeit gewinnen möchten, können Sie die zufällige Version von HT verwenden.

• Ich kenne keine Arbeit in CG (oder einer anderen Gruppe) zur Ableitung der Steigung aus der Menge der diskreten Punkte, aber das spiegelt eher meinen Mangel an Wissen wider.

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