Odzyskiwanie nachylenia cyfrowej linii

11

Czy były prace nad odzyskaniem nachylenia segmentu linii po digitalizacji? Oczywiście nie można tego zrobić z idealną dokładnością; to, czego się chce, to metoda wyprowadzenia z linii cyfrowej przedziału możliwych nachyleń.

(Pojęcie cyfrowej linii, której używam, to Rosenfelda: zbiór par gdzie rozciąga się na liczbach całkowitych (lub bloku kolejnych liczb całkowitych), a oznacza liczbę całkowitą najbliżej (jeśli , bierzemy ).) $(i,nint(ai+b))$ $i$ $nint(x)$ $x$ $x=k+1/2$ $nint(x)=k$

Pracowałem nad tym sam (patrz http://jamespropp.org/SeeSlope.nb ), ale nie mam formalnego zaplecza w geometrii obliczeniowej, więc podejrzewam, że mogę odkrywać koło, ponieważ pytanie wydaje się takie podstawowy.

W rzeczywistości wiem, że metoda regresji liniowej szacowania nachylenia jest w literaturze, ale nigdzie nie byłem w stanie znaleźć mojego wyniku . (Wynik ten stwierdza, że jeśli ktoś wybiera i równomiernie na losowo , to różnica pomiędzy nachylenia od linii i nachylenie linii regresji aproksymującej punktów ( ) ma odchylenie standardowe .) $O(1/n^{1.5})$ $a$ $b$ $[0,1]$ $a$ $y=ax+b$ $\overline{a}$ $n$ $(i,nint(ai+b))$ $1 \leq i \leq n$ $O(1/n^{1.5})$

Wszelkie wskazówki lub wskazówki do odpowiedniej literatury będą mile widziane.

Jim Propp (JamesPropp@ignorethis.gmail.com)

— Jim Propp
źródło

Czyli punktowa digitalizacja to z grubsza zbiór komórek z siatki ?

n

$n$

n \times n

$n \times n$

— Suresh Venkat

1

Co dokładnie masz na myśli przez linię cyfrową? Zakładałem, że masz na myśli coś w rodzaju prostej linii na zdjęciu lub zrasteryzowanego obrazu, ale z mówienia o regresji liniowej brzmi bardziej, jakbyś był zainteresowany znalezieniem linii najlepiej dopasowanej do niektórych próbkowanych danych.

— Joe Fitzsimons,

Więc model jesteś zainteresowany nie jest dokładną rozwiązanie i

, ale tylko przybliżeniem do nich? Uprościłbym ten problem, nie biorąc pod uwagę

(to tylko irytujące przesunięcie), i

przy

(okazuje się, że to tylko kolejna zmiana). A co tu jest

?

a

$a$

b

$b$

b

$b$

⌊ a x ⌋

$\lfloor a x \rfloor$

n

$n$

— Mitch

Przepraszam, Mitch; Zapomniałem wyjaśnić co

było! Dodałem to do oryginalnego postu. - Jim

n

$n$

— Jim Propp

1

Zobacz Random Generation of Finite Sturmian Words autorstwa Berstela i Pocchioli, aby uzyskać dowód, że wykonalny region twojego LP ma tylko trzy lub cztery boki, a także prosty algorytm znajdowania wielokąta o danym nachyleniu i przecięciu. (Zajmują się rozpoznawaniem Sturmian Words, ale problemy są ściśle powiązane).

Podają również wyraźne wyliczenie wielokątów, więc może być możliwe wyliczenie obszarów wielokątów i zakresów nachyleń, dzięki czemu można uzyskać oczekiwaną wartość zakresu nachyleń (a także wyższych momentów ) jako wyraźna suma.

— deinst
źródło

4

Podejście do geometrii obliczeniowej zastąpiłoby każdy piksel (i, j) segmentem pionowym (i, j + [- 1 / 2,1 / 2]), wziął wypukłe kadłuby górnego i dolnego zestawu punktów końcowych i obliczył wspólny wspólny styczne - ograniczają zasięg stoków tworzących tę cyfrową linię. To tylko geometryczna interpretacja programu liniowego, o którym wspominasz na slajdach. O (n) wystarcza czas na LP Meggiddo lub na kadłuby i styczne Grahama-Yao.

— Jacek
źródło

2

Co ze standardową metodą transformacji Hougha stosowaną do wykrywania linii w przetwarzaniu obrazu: http://en.wikipedia.org/wiki/Hough_transform ?

Jeśli chcesz zyskać trochę prędkości, możesz użyć losowej wersji HT.

— Marzio De Biasi
źródło

1

Nie znam żadnej pracy w cg (ani żadnej innej grupie w tej kwestii) nad uzyskaniem nachylenia z zestawu dyskretnych punktów, ale to bardziej odzwierciedla mój brak wiedzy.
$\Delta y$ $\Delta x$ $x$ $y$ $x$ $y$

— Mitch
źródło

O (1 / n)

$O(1/n)$